clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp

   1 //===-- UncheckedOptionalAccessModel.cpp ------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines a dataflow analysis that detects unsafe uses of optional
  10 //  values.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h"
  15 #include "clang/AST/ASTContext.h"
  16 #include "clang/AST/DeclCXX.h"
  17 #include "clang/AST/Expr.h"
  18 #include "clang/AST/ExprCXX.h"
  19 #include "clang/AST/Stmt.h"
  20 #include "clang/ASTMatchers/ASTMatchers.h"
  21 #include "clang/ASTMatchers/ASTMatchersMacros.h"
  22 #include "clang/Analysis/CFG.h"
  23 #include "clang/Analysis/FlowSensitive/CFGMatchSwitch.h"
  24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
  25 #include "clang/Analysis/FlowSensitive/Formula.h"
  26 #include "clang/Analysis/FlowSensitive/NoopLattice.h"
  27 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
  28 #include "clang/Analysis/FlowSensitive/Value.h"
  29 #include "clang/Basic/SourceLocation.h"
  30 #include "llvm/ADT/StringRef.h"
  31 #include "llvm/Support/Casting.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include <cassert>
  34 #include <memory>
  35 #include <optional>
  36 #include <utility>
  37
  38 namespace clang {
  39 namespace dataflow {
  40
  41 static bool isTopLevelNamespaceWithName(const NamespaceDecl &NS,
  42                                         llvm::StringRef Name) {
  43   return NS.getDeclName().isIdentifier() && NS.getName() == Name &&
  44          NS.getParent() != nullptr && NS.getParent()->isTranslationUnit();
  45 }
  46
  47 static bool hasOptionalClassName(const CXXRecordDecl &RD) {
  48   if (!RD.getDeclName().isIdentifier())
  49     return false;
  50
  51   if (RD.getName() == "optional") {
  52     if (const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext()))
  53       return N->isStdNamespace() || isTopLevelNamespaceWithName(*N, "absl");
  54     return false;
  55   }
  56
  57   if (RD.getName() == "Optional") {
  58     // Check whether namespace is "::base" or "::folly".
  59     const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext());
  60     return N != nullptr && (isTopLevelNamespaceWithName(*N, "base") ||
  61                             isTopLevelNamespaceWithName(*N, "folly"));
  62   }
  63
  64   return false;
  65 }
  66
  67 namespace {
  68
  69 using namespace ::clang::ast_matchers;
  70 using LatticeTransferState = TransferState<NoopLattice>;
  71
  72 AST_MATCHER(CXXRecordDecl, hasOptionalClassNameMatcher) {
  73   return hasOptionalClassName(Node);
  74 }
  75
  76 DeclarationMatcher optionalClass() {
  77   return classTemplateSpecializationDecl(
  78       hasOptionalClassNameMatcher(),
  79       hasTemplateArgument(0, refersToType(type().bind("T"))));
  80 }
  81
  82 auto optionalOrAliasType() {
  83   return hasUnqualifiedDesugaredType(
  84       recordType(hasDeclaration(optionalClass())));
  85 }
  86
  87 /// Matches any of the spellings of the optional types and sugar, aliases, etc.
  88 auto hasOptionalType() { return hasType(optionalOrAliasType()); }
  89
  90 auto isOptionalMemberCallWithNameMatcher(
  91     ast_matchers::internal::Matcher<NamedDecl> matcher,
  92     const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
  93   auto Exception = unless(Ignorable ? expr(anyOf(*Ignorable, cxxThisExpr()))
  94                                     : cxxThisExpr());
  95   return cxxMemberCallExpr(
  96       on(expr(Exception,
  97               anyOf(hasOptionalType(),
  98                     hasType(pointerType(pointee(optionalOrAliasType())))))),
  99       callee(cxxMethodDecl(matcher)));
 100 }
 101
 102 auto isOptionalOperatorCallWithName(
 103     llvm::StringRef operator_name,
 104     const std::optional<StatementMatcher> &Ignorable = std::nullopt) {
 105   return cxxOperatorCallExpr(
 106       hasOverloadedOperatorName(operator_name),
 107       callee(cxxMethodDecl(ofClass(optionalClass()))),
 108       Ignorable ? callExpr(unless(hasArgument(0, *Ignorable))) : callExpr());
 109 }
 110
 111 auto isMakeOptionalCall() {
 112   return callExpr(callee(functionDecl(hasAnyName(
 113                       "std::make_optional", "base::make_optional",
 114                       "absl::make_optional", "folly::make_optional"))),
 115                   hasOptionalType());
 116 }
 117
 118 auto nulloptTypeDecl() {
 119   return namedDecl(hasAnyName("std::nullopt_t", "absl::nullopt_t",
 120                               "base::nullopt_t", "folly::None"));
 121 }
 122
 123 auto hasNulloptType() { return hasType(nulloptTypeDecl()); }
 124
 125 auto inPlaceClass() {
 126   return recordDecl(hasAnyName("std::in_place_t", "absl::in_place_t",
 127                                "base::in_place_t", "folly::in_place_t"));
 128 }
 129
 130 auto isOptionalNulloptConstructor() {
 131   return cxxConstructExpr(
 132       hasOptionalType(),
 133       hasDeclaration(cxxConstructorDecl(parameterCountIs(1),
 134                                         hasParameter(0, hasNulloptType()))));
 135 }
 136
 137 auto isOptionalInPlaceConstructor() {
 138   return cxxConstructExpr(hasOptionalType(),
 139                           hasArgument(0, hasType(inPlaceClass())));
 140 }
 141
 142 auto isOptionalValueOrConversionConstructor() {
 143   return cxxConstructExpr(
 144       hasOptionalType(),
 145       unless(hasDeclaration(
 146           cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))),
 147       argumentCountIs(1), hasArgument(0, unless(hasNulloptType())));
 148 }
 149
 150 auto isOptionalValueOrConversionAssignment() {
 151   return cxxOperatorCallExpr(
 152       hasOverloadedOperatorName("="),
 153       callee(cxxMethodDecl(ofClass(optionalClass()))),
 154       unless(hasDeclaration(cxxMethodDecl(
 155           anyOf(isCopyAssignmentOperator(), isMoveAssignmentOperator())))),
 156       argumentCountIs(2), hasArgument(1, unless(hasNulloptType())));
 157 }
 158
 159 auto isOptionalNulloptAssignment() {
 160   return cxxOperatorCallExpr(hasOverloadedOperatorName("="),
 161                              callee(cxxMethodDecl(ofClass(optionalClass()))),
 162                              argumentCountIs(2),
 163                              hasArgument(1, hasNulloptType()));
 164 }
 165
 166 auto isStdSwapCall() {
 167   return callExpr(callee(functionDecl(hasName("std::swap"))),
 168                   argumentCountIs(2), hasArgument(0, hasOptionalType()),
 169                   hasArgument(1, hasOptionalType()));
 170 }
 171
 172 auto isStdForwardCall() {
 173   return callExpr(callee(functionDecl(hasName("std::forward"))),
 174                   argumentCountIs(1), hasArgument(0, hasOptionalType()));
 175 }
 176
 177 constexpr llvm::StringLiteral ValueOrCallID = "ValueOrCall";
 178
 179 auto isValueOrStringEmptyCall() {
 180   // `opt.value_or("").empty()`
 181   return cxxMemberCallExpr(
 182       callee(cxxMethodDecl(hasName("empty"))),
 183       onImplicitObjectArgument(ignoringImplicit(
 184           cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
 185                             callee(cxxMethodDecl(hasName("value_or"),
 186                                                  ofClass(optionalClass()))),
 187                             hasArgument(0, stringLiteral(hasSize(0))))
 188               .bind(ValueOrCallID))));
 189 }
 190
 191 auto isValueOrNotEqX() {
 192   auto ComparesToSame = [](ast_matchers::internal::Matcher<Stmt> Arg) {
 193     return hasOperands(
 194         ignoringImplicit(
 195             cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))),
 196                               callee(cxxMethodDecl(hasName("value_or"),
 197                                                    ofClass(optionalClass()))),
 198                               hasArgument(0, Arg))
 199                 .bind(ValueOrCallID)),
 200         ignoringImplicit(Arg));
 201   };
 202
 203   // `opt.value_or(X) != X`, for X is `nullptr`, `""`, or `0`. Ideally, we'd
 204   // support this pattern for any expression, but the AST does not have a
 205   // generic expression comparison facility, so we specialize to common cases
 206   // seen in practice.  FIXME: define a matcher that compares values across
 207   // nodes, which would let us generalize this to any `X`.
 208   return binaryOperation(hasOperatorName("!="),
 209                          anyOf(ComparesToSame(cxxNullPtrLiteralExpr()),
 210                                ComparesToSame(stringLiteral(hasSize(0))),
 211                                ComparesToSame(integerLiteral(equals(0)))));
 212 }
 213
 214 auto isCallReturningOptional() {
 215   return callExpr(hasType(qualType(anyOf(
 216       optionalOrAliasType(), referenceType(pointee(optionalOrAliasType()))))));
 217 }
 218
 219 template <typename L, typename R>
 220 auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) {
 221   return cxxOperatorCallExpr(
 222       anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")),
 223       argumentCountIs(2), hasArgument(0, lhs_arg_matcher),
 224       hasArgument(1, rhs_arg_matcher));
 225 }
 226
 227 /// Ensures that `Expr` is mapped to a `BoolValue` and returns its formula.
 228 const Formula &forceBoolValue(Environment &Env, const Expr &Expr) {
 229   auto *Value = Env.get<BoolValue>(Expr);
 230   if (Value != nullptr)
 231     return Value->formula();
 232
 233   Value = &Env.makeAtomicBoolValue();
 234   Env.setValue(Expr, *Value);
 235   return Value->formula();
 236 }
 237
 238 StorageLocation &locForHasValue(const RecordStorageLocation &OptionalLoc) {
 239   return OptionalLoc.getSyntheticField("has_value");
 240 }
 241
 242 StorageLocation &locForValue(const RecordStorageLocation &OptionalLoc) {
 243   return OptionalLoc.getSyntheticField("value");
 244 }
 245
 246 /// Sets `HasValueVal` as the symbolic value that represents the "has_value"
 247 /// property of the optional at `OptionalLoc`.
 248 void setHasValue(RecordStorageLocation &OptionalLoc, BoolValue &HasValueVal,
 249                  Environment &Env) {
 250   Env.setValue(locForHasValue(OptionalLoc), HasValueVal);
 251 }
 252
 253 /// Creates a symbolic value for an `optional` value at an existing storage
 254 /// location. Uses `HasValueVal` as the symbolic value of the "has_value"
 255 /// property.
 256 RecordValue &createOptionalValue(RecordStorageLocation &Loc,
 257                                  BoolValue &HasValueVal, Environment &Env) {
 258   auto &OptionalVal = Env.create<RecordValue>(Loc);
 259   Env.setValue(Loc, OptionalVal);
 260   setHasValue(Loc, HasValueVal, Env);
 261   return OptionalVal;
 262 }
 263
 264 /// Returns the symbolic value that represents the "has_value" property of the
 265 /// optional at `OptionalLoc`. Returns null if `OptionalLoc` is null.
 266 BoolValue *getHasValue(Environment &Env, RecordStorageLocation *OptionalLoc) {
 267   if (OptionalLoc == nullptr)
 268     return nullptr;
 269   StorageLocation &HasValueLoc = locForHasValue(*OptionalLoc);
 270   auto *HasValueVal = Env.get<BoolValue>(HasValueLoc);
 271   if (HasValueVal == nullptr) {
 272     HasValueVal = &Env.makeAtomicBoolValue();
 273     Env.setValue(HasValueLoc, *HasValueVal);
 274   }
 275   return HasValueVal;
 276 }
 277
 278 /// Returns true if and only if `Type` is an optional type.
 279 bool isOptionalType(QualType Type) {
 280   if (!Type->isRecordType())
 281     return false;
 282   const CXXRecordDecl *D = Type->getAsCXXRecordDecl();
 283   return D != nullptr && hasOptionalClassName(*D);
 284 }
 285
 286 /// Returns the number of optional wrappers in `Type`.
 287 ///
 288 /// For example, if `Type` is `optional<optional<int>>`, the result of this
 289 /// function will be 2.
 290 int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) {
 291   if (!isOptionalType(Type))
 292     return 0;
 293   return 1 + countOptionalWrappers(
 294                  ASTCtx,
 295                  cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl())
 296                      ->getTemplateArgs()
 297                      .get(0)
 298                      .getAsType()
 299                      .getDesugaredType(ASTCtx));
 300 }
 301
 302 StorageLocation *getLocBehindPossiblePointer(const Expr &E,
 303                                              const Environment &Env) {
 304   if (E.isPRValue()) {
 305     if (auto *PointerVal = dyn_cast_or_null<PointerValue>(Env.getValue(E)))
 306       return &PointerVal->getPointeeLoc();
 307     return nullptr;
 308   }
 309   return Env.getStorageLocation(E);
 310 }
 311
 312 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
 313                         LatticeTransferState &State) {
 314   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
 315           getLocBehindPossiblePointer(*ObjectExpr, State.Env))) {
 316     if (State.Env.getStorageLocation(*UnwrapExpr) == nullptr)
 317       State.Env.setStorageLocation(*UnwrapExpr, locForValue(*OptionalLoc));
 318   }
 319 }
 320
 321 void transferArrowOpCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
 322                          LatticeTransferState &State) {
 323   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
 324           getLocBehindPossiblePointer(*ObjectExpr, State.Env)))
 325     State.Env.setValue(
 326         *UnwrapExpr, State.Env.create<PointerValue>(locForValue(*OptionalLoc)));
 327 }
 328
 329 void transferMakeOptionalCall(const CallExpr *E,
 330                               const MatchFinder::MatchResult &,
 331                               LatticeTransferState &State) {
 332   State.Env.setValue(
 333       *E, createOptionalValue(State.Env.getResultObjectLocation(*E),
 334                               State.Env.getBoolLiteralValue(true), State.Env));
 335 }
 336
 337 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
 338                                   const MatchFinder::MatchResult &,
 339                                   LatticeTransferState &State) {
 340   if (auto *HasValueVal = getHasValue(
 341           State.Env, getImplicitObjectLocation(*CallExpr, State.Env))) {
 342     State.Env.setValue(*CallExpr, *HasValueVal);
 343   }
 344 }
 345
 346 /// `ModelPred` builds a logical formula relating the predicate in
 347 /// `ValueOrPredExpr` to the optional's `has_value` property.
 348 void transferValueOrImpl(
 349     const clang::Expr *ValueOrPredExpr, const MatchFinder::MatchResult &Result,
 350     LatticeTransferState &State,
 351     const Formula &(*ModelPred)(Environment &Env, const Formula &ExprVal,
 352                                 const Formula &HasValueVal)) {
 353   auto &Env = State.Env;
 354
 355   const auto *MCE =
 356       Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID);
 357
 358   auto *HasValueVal =
 359       getHasValue(State.Env, getImplicitObjectLocation(*MCE, State.Env));
 360   if (HasValueVal == nullptr)
 361     return;
 362
 363   Env.assume(ModelPred(Env, forceBoolValue(Env, *ValueOrPredExpr),
 364                        HasValueVal->formula()));
 365 }
 366
 367 void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
 368                                     const MatchFinder::MatchResult &Result,
 369                                     LatticeTransferState &State) {
 370   return transferValueOrImpl(ComparisonExpr, Result, State,
 371                              [](Environment &Env, const Formula &ExprVal,
 372                                 const Formula &HasValueVal) -> const Formula & {
 373                                auto &A = Env.arena();
 374                                // If the result is *not* empty, then we know the
 375                                // optional must have been holding a value. If
 376                                // `ExprVal` is true, though, we don't learn
 377                                // anything definite about `has_value`, so we
 378                                // don't add any corresponding implications to
 379                                // the flow condition.
 380                                return A.makeImplies(A.makeNot(ExprVal),
 381                                                     HasValueVal);
 382                              });
 383 }
 384
 385 void transferValueOrNotEqX(const Expr *ComparisonExpr,
 386                            const MatchFinder::MatchResult &Result,
 387                            LatticeTransferState &State) {
 388   transferValueOrImpl(ComparisonExpr, Result, State,
 389                       [](Environment &Env, const Formula &ExprVal,
 390                          const Formula &HasValueVal) -> const Formula & {
 391                         auto &A = Env.arena();
 392                         // We know that if `(opt.value_or(X) != X)` then
 393                         // `opt.hasValue()`, even without knowing further
 394                         // details about the contents of `opt`.
 395                         return A.makeImplies(ExprVal, HasValueVal);
 396                       });
 397 }
 398
 399 void transferCallReturningOptional(const CallExpr *E,
 400                                    const MatchFinder::MatchResult &Result,
 401                                    LatticeTransferState &State) {
 402   if (State.Env.getValue(*E) != nullptr)
 403     return;
 404
 405   RecordStorageLocation *Loc = nullptr;
 406   if (E->isPRValue()) {
 407     Loc = &State.Env.getResultObjectLocation(*E);
 408   } else {
 409     Loc = State.Env.get<RecordStorageLocation>(*E);
 410     if (Loc == nullptr) {
 411       Loc = &cast<RecordStorageLocation>(State.Env.createStorageLocation(*E));
 412       State.Env.setStorageLocation(*E, *Loc);
 413     }
 414   }
 415
 416   RecordValue &Val =
 417       createOptionalValue(*Loc, State.Env.makeAtomicBoolValue(), State.Env);
 418   if (E->isPRValue())
 419     State.Env.setValue(*E, Val);
 420 }
 421
 422 void constructOptionalValue(const Expr &E, Environment &Env,
 423                             BoolValue &HasValueVal) {
 424   RecordStorageLocation &Loc = Env.getResultObjectLocation(E);
 425   Env.setValue(E, createOptionalValue(Loc, HasValueVal, Env));
 426 }
 427
 428 /// Returns a symbolic value for the "has_value" property of an `optional<T>`
 429 /// value that is constructed/assigned from a value of type `U` or `optional<U>`
 430 /// where `T` is constructible from `U`.
 431 BoolValue &valueOrConversionHasValue(const FunctionDecl &F, const Expr &E,
 432                                      const MatchFinder::MatchResult &MatchRes,
 433                                      LatticeTransferState &State) {
 434   assert(F.getTemplateSpecializationArgs() != nullptr);
 435   assert(F.getTemplateSpecializationArgs()->size() > 0);
 436
 437   const int TemplateParamOptionalWrappersCount =
 438       countOptionalWrappers(*MatchRes.Context, F.getTemplateSpecializationArgs()
 439                                                    ->get(0)
 440                                                    .getAsType()
 441                                                    .getNonReferenceType());
 442   const int ArgTypeOptionalWrappersCount = countOptionalWrappers(
 443       *MatchRes.Context, E.getType().getNonReferenceType());
 444
 445   // Check if this is a constructor/assignment call for `optional<T>` with
 446   // argument of type `U` such that `T` is constructible from `U`.
 447   if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount)
 448     return State.Env.getBoolLiteralValue(true);
 449
 450   // This is a constructor/assignment call for `optional<T>` with argument of
 451   // type `optional<U>` such that `T` is constructible from `U`.
 452   auto *Loc = State.Env.get<RecordStorageLocation>(E);
 453   if (auto *HasValueVal = getHasValue(State.Env, Loc))
 454     return *HasValueVal;
 455   return State.Env.makeAtomicBoolValue();
 456 }
 457
 458 void transferValueOrConversionConstructor(
 459     const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes,
 460     LatticeTransferState &State) {
 461   assert(E->getNumArgs() > 0);
 462
 463   constructOptionalValue(*E, State.Env,
 464                          valueOrConversionHasValue(*E->getConstructor(),
 465                                                    *E->getArg(0), MatchRes,
 466                                                    State));
 467 }
 468
 469 void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal,
 470                         LatticeTransferState &State) {
 471   assert(E->getNumArgs() > 0);
 472
 473   if (auto *Loc = State.Env.get<RecordStorageLocation>(*E->getArg(0))) {
 474     createOptionalValue(*Loc, HasValueVal, State.Env);
 475
 476     // Assign a storage location for the whole expression.
 477     State.Env.setStorageLocation(*E, *Loc);
 478   }
 479 }
 480
 481 void transferValueOrConversionAssignment(
 482     const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes,
 483     LatticeTransferState &State) {
 484   assert(E->getNumArgs() > 1);
 485   transferAssignment(E,
 486                      valueOrConversionHasValue(*E->getDirectCallee(),
 487                                                *E->getArg(1), MatchRes, State),
 488                      State);
 489 }
 490
 491 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
 492                                const MatchFinder::MatchResult &,
 493                                LatticeTransferState &State) {
 494   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
 495 }
 496
 497 void transferSwap(RecordStorageLocation *Loc1, RecordStorageLocation *Loc2,
 498                   Environment &Env) {
 499   // We account for cases where one or both of the optionals are not modeled,
 500   // either lacking associated storage locations, or lacking values associated
 501   // to such storage locations.
 502
 503   if (Loc1 == nullptr) {
 504     if (Loc2 != nullptr)
 505       createOptionalValue(*Loc2, Env.makeAtomicBoolValue(), Env);
 506     return;
 507   }
 508   if (Loc2 == nullptr) {
 509     createOptionalValue(*Loc1, Env.makeAtomicBoolValue(), Env);
 510     return;
 511   }
 512
 513   // Both expressions have locations, though they may not have corresponding
 514   // values. In that case, we create a fresh value at this point. Note that if
 515   // two branches both do this, they will not share the value, but it at least
 516   // allows for local reasoning about the value. To avoid the above, we would
 517   // need *lazy* value allocation.
 518   // FIXME: allocate values lazily, instead of just creating a fresh value.
 519   BoolValue *BoolVal1 = getHasValue(Env, Loc1);
 520   if (BoolVal1 == nullptr)
 521     BoolVal1 = &Env.makeAtomicBoolValue();
 522
 523   BoolValue *BoolVal2 = getHasValue(Env, Loc2);
 524   if (BoolVal2 == nullptr)
 525     BoolVal2 = &Env.makeAtomicBoolValue();
 526
 527   createOptionalValue(*Loc1, *BoolVal2, Env);
 528   createOptionalValue(*Loc2, *BoolVal1, Env);
 529 }
 530
 531 void transferSwapCall(const CXXMemberCallExpr *E,
 532                       const MatchFinder::MatchResult &,
 533                       LatticeTransferState &State) {
 534   assert(E->getNumArgs() == 1);
 535   auto *OtherLoc = State.Env.get<RecordStorageLocation>(*E->getArg(0));
 536   transferSwap(getImplicitObjectLocation(*E, State.Env), OtherLoc, State.Env);
 537 }
 538
 539 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
 540                          LatticeTransferState &State) {
 541   assert(E->getNumArgs() == 2);
 542   auto *Arg0Loc = State.Env.get<RecordStorageLocation>(*E->getArg(0));
 543   auto *Arg1Loc = State.Env.get<RecordStorageLocation>(*E->getArg(1));
 544   transferSwap(Arg0Loc, Arg1Loc, State.Env);
 545 }
 546
 547 void transferStdForwardCall(const CallExpr *E, const MatchFinder::MatchResult &,
 548                             LatticeTransferState &State) {
 549   assert(E->getNumArgs() == 1);
 550
 551   if (auto *Loc = State.Env.getStorageLocation(*E->getArg(0)))
 552     State.Env.setStorageLocation(*E, *Loc);
 553 }
 554
 555 const Formula &evaluateEquality(Arena &A, const Formula &EqVal,
 556                                 const Formula &LHS, const Formula &RHS) {
 557   // Logically, an optional<T> object is composed of two values - a `has_value`
 558   // bit and a value of type T. Equality of optional objects compares both
 559   // values. Therefore, merely comparing the `has_value` bits isn't sufficient:
 560   // when two optional objects are engaged, the equality of their respective
 561   // values of type T matters. Since we only track the `has_value` bits, we
 562   // can't make any conclusions about equality when we know that two optional
 563   // objects are engaged.
 564   //
 565   // We express this as two facts about the equality:
 566   // a) EqVal => (LHS & RHS) v (!RHS & !LHS)
 567   //    If they are equal, then either both are set or both are unset.
 568   // b) (!LHS & !RHS) => EqVal
 569   //    If neither is set, then they are equal.
 570   // We rewrite b) as !EqVal => (LHS v RHS), for a more compact formula.
 571   return A.makeAnd(
 572       A.makeImplies(EqVal, A.makeOr(A.makeAnd(LHS, RHS),
 573                                     A.makeAnd(A.makeNot(LHS), A.makeNot(RHS)))),
 574       A.makeImplies(A.makeNot(EqVal), A.makeOr(LHS, RHS)));
 575 }
 576
 577 void transferOptionalAndOptionalCmp(const clang::CXXOperatorCallExpr *CmpExpr,
 578                                     const MatchFinder::MatchResult &,
 579                                     LatticeTransferState &State) {
 580   Environment &Env = State.Env;
 581   auto &A = Env.arena();
 582   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
 583   auto *Arg0Loc = Env.get<RecordStorageLocation>(*CmpExpr->getArg(0));
 584   if (auto *LHasVal = getHasValue(Env, Arg0Loc)) {
 585     auto *Arg1Loc = Env.get<RecordStorageLocation>(*CmpExpr->getArg(1));
 586     if (auto *RHasVal = getHasValue(Env, Arg1Loc)) {
 587       if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
 588         CmpValue = &A.makeNot(*CmpValue);
 589       Env.assume(evaluateEquality(A, *CmpValue, LHasVal->formula(),
 590                                   RHasVal->formula()));
 591     }
 592   }
 593 }
 594
 595 void transferOptionalAndValueCmp(const clang::CXXOperatorCallExpr *CmpExpr,
 596                                  const clang::Expr *E, Environment &Env) {
 597   auto &A = Env.arena();
 598   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
 599   auto *Loc = Env.get<RecordStorageLocation>(*E);
 600   if (auto *HasVal = getHasValue(Env, Loc)) {
 601     if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
 602       CmpValue = &A.makeNot(*CmpValue);
 603     Env.assume(
 604         evaluateEquality(A, *CmpValue, HasVal->formula(), A.makeLiteral(true)));
 605   }
 606 }
 607
 608 void transferOptionalAndNulloptCmp(const clang::CXXOperatorCallExpr *CmpExpr,
 609                                    const clang::Expr *E, Environment &Env) {
 610   auto &A = Env.arena();
 611   auto *CmpValue = &forceBoolValue(Env, *CmpExpr);
 612   auto *Loc = Env.get<RecordStorageLocation>(*E);
 613   if (auto *HasVal = getHasValue(Env, Loc)) {
 614     if (CmpExpr->getOperator() == clang::OO_ExclaimEqual)
 615       CmpValue = &A.makeNot(*CmpValue);
 616     Env.assume(evaluateEquality(A, *CmpValue, HasVal->formula(),
 617                                 A.makeLiteral(false)));
 618   }
 619 }
 620
 621 std::optional<StatementMatcher>
 622 ignorableOptional(const UncheckedOptionalAccessModelOptions &Options) {
 623   if (Options.IgnoreSmartPointerDereference) {
 624     auto SmartPtrUse = expr(ignoringParenImpCasts(cxxOperatorCallExpr(
 625         anyOf(hasOverloadedOperatorName("->"), hasOverloadedOperatorName("*")),
 626         unless(hasArgument(0, expr(hasOptionalType()))))));
 627     return expr(
 628         anyOf(SmartPtrUse, memberExpr(hasObjectExpression(SmartPtrUse))));
 629   }
 630   return std::nullopt;
 631 }
 632
 633 StatementMatcher
 634 valueCall(const std::optional<StatementMatcher> &IgnorableOptional) {
 635   return isOptionalMemberCallWithNameMatcher(hasName("value"),
 636                                              IgnorableOptional);
 637 }
 638
 639 StatementMatcher
 640 valueOperatorCall(const std::optional<StatementMatcher> &IgnorableOptional) {
 641   return expr(anyOf(isOptionalOperatorCallWithName("*", IgnorableOptional),
 642                     isOptionalOperatorCallWithName("->", IgnorableOptional)));
 643 }
 644
 645 auto buildTransferMatchSwitch() {
 646   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
 647   // lot of duplicated work (e.g. string comparisons), consider providing APIs
 648   // that avoid it through memoization.
 649   return CFGMatchSwitchBuilder<LatticeTransferState>()
 650       // make_optional
 651       .CaseOfCFGStmt<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)
 652
 653       // optional::optional (in place)
 654       .CaseOfCFGStmt<CXXConstructExpr>(
 655           isOptionalInPlaceConstructor(),
 656           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
 657              LatticeTransferState &State) {
 658             constructOptionalValue(*E, State.Env,
 659                                    State.Env.getBoolLiteralValue(true));
 660           })
 661       // optional::optional(nullopt_t)
 662       .CaseOfCFGStmt<CXXConstructExpr>(
 663           isOptionalNulloptConstructor(),
 664           [](const CXXConstructExpr *E, const MatchFinder::MatchResult &,
 665              LatticeTransferState &State) {
 666             constructOptionalValue(*E, State.Env,
 667                                    State.Env.getBoolLiteralValue(false));
 668           })
 669       // optional::optional (value/conversion)
 670       .CaseOfCFGStmt<CXXConstructExpr>(isOptionalValueOrConversionConstructor(),
 671                                        transferValueOrConversionConstructor)
 672
 673       // optional::operator=
 674       .CaseOfCFGStmt<CXXOperatorCallExpr>(
 675           isOptionalValueOrConversionAssignment(),
 676           transferValueOrConversionAssignment)
 677       .CaseOfCFGStmt<CXXOperatorCallExpr>(isOptionalNulloptAssignment(),
 678                                           transferNulloptAssignment)
 679
 680       // optional::value
 681       .CaseOfCFGStmt<CXXMemberCallExpr>(
 682           valueCall(std::nullopt),
 683           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
 684              LatticeTransferState &State) {
 685             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
 686           })
 687
 688       // optional::operator*
 689       .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("*"),
 690                                [](const CallExpr *E,
 691                                   const MatchFinder::MatchResult &,
 692                                   LatticeTransferState &State) {
 693                                  transferUnwrapCall(E, E->getArg(0), State);
 694                                })
 695
 696       // optional::operator->
 697       .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("->"),
 698                                [](const CallExpr *E,
 699                                   const MatchFinder::MatchResult &,
 700                                   LatticeTransferState &State) {
 701                                  transferArrowOpCall(E, E->getArg(0), State);
 702                                })
 703
 704       // optional::has_value, optional::hasValue
 705       // Of the supported optionals only folly::Optional uses hasValue, but this
 706       // will also pass for other types
 707       .CaseOfCFGStmt<CXXMemberCallExpr>(
 708           isOptionalMemberCallWithNameMatcher(
 709               hasAnyName("has_value", "hasValue")),
 710           transferOptionalHasValueCall)
 711
 712       // optional::operator bool
 713       .CaseOfCFGStmt<CXXMemberCallExpr>(
 714           isOptionalMemberCallWithNameMatcher(hasName("operator bool")),
 715           transferOptionalHasValueCall)
 716
 717       // optional::emplace
 718       .CaseOfCFGStmt<CXXMemberCallExpr>(
 719           isOptionalMemberCallWithNameMatcher(hasName("emplace")),
 720           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
 721              LatticeTransferState &State) {
 722             if (RecordStorageLocation *Loc =
 723                     getImplicitObjectLocation(*E, State.Env)) {
 724               createOptionalValue(*Loc, State.Env.getBoolLiteralValue(true),
 725                                   State.Env);
 726             }
 727           })
 728
 729       // optional::reset
 730       .CaseOfCFGStmt<CXXMemberCallExpr>(
 731           isOptionalMemberCallWithNameMatcher(hasName("reset")),
 732           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
 733              LatticeTransferState &State) {
 734             if (RecordStorageLocation *Loc =
 735                     getImplicitObjectLocation(*E, State.Env)) {
 736               createOptionalValue(*Loc, State.Env.getBoolLiteralValue(false),
 737                                   State.Env);
 738             }
 739           })
 740
 741       // optional::swap
 742       .CaseOfCFGStmt<CXXMemberCallExpr>(
 743           isOptionalMemberCallWithNameMatcher(hasName("swap")),
 744           transferSwapCall)
 745
 746       // std::swap
 747       .CaseOfCFGStmt<CallExpr>(isStdSwapCall(), transferStdSwapCall)
 748
 749       // std::forward
 750       .CaseOfCFGStmt<CallExpr>(isStdForwardCall(), transferStdForwardCall)
 751
 752       // opt.value_or("").empty()
 753       .CaseOfCFGStmt<Expr>(isValueOrStringEmptyCall(),
 754                            transferValueOrStringEmptyCall)
 755
 756       // opt.value_or(X) != X
 757       .CaseOfCFGStmt<Expr>(isValueOrNotEqX(), transferValueOrNotEqX)
 758
 759       // Comparisons (==, !=):
 760       .CaseOfCFGStmt<CXXOperatorCallExpr>(
 761           isComparisonOperatorCall(hasOptionalType(), hasOptionalType()),
 762           transferOptionalAndOptionalCmp)
 763       .CaseOfCFGStmt<CXXOperatorCallExpr>(
 764           isComparisonOperatorCall(hasOptionalType(), hasNulloptType()),
 765           [](const clang::CXXOperatorCallExpr *Cmp,
 766              const MatchFinder::MatchResult &, LatticeTransferState &State) {
 767             transferOptionalAndNulloptCmp(Cmp, Cmp->getArg(0), State.Env);
 768           })
 769       .CaseOfCFGStmt<CXXOperatorCallExpr>(
 770           isComparisonOperatorCall(hasNulloptType(), hasOptionalType()),
 771           [](const clang::CXXOperatorCallExpr *Cmp,
 772              const MatchFinder::MatchResult &, LatticeTransferState &State) {
 773             transferOptionalAndNulloptCmp(Cmp, Cmp->getArg(1), State.Env);
 774           })
 775       .CaseOfCFGStmt<CXXOperatorCallExpr>(
 776           isComparisonOperatorCall(
 777               hasOptionalType(),
 778               unless(anyOf(hasOptionalType(), hasNulloptType()))),
 779           [](const clang::CXXOperatorCallExpr *Cmp,
 780              const MatchFinder::MatchResult &, LatticeTransferState &State) {
 781             transferOptionalAndValueCmp(Cmp, Cmp->getArg(0), State.Env);
 782           })
 783       .CaseOfCFGStmt<CXXOperatorCallExpr>(
 784           isComparisonOperatorCall(
 785               unless(anyOf(hasOptionalType(), hasNulloptType())),
 786               hasOptionalType()),
 787           [](const clang::CXXOperatorCallExpr *Cmp,
 788              const MatchFinder::MatchResult &, LatticeTransferState &State) {
 789             transferOptionalAndValueCmp(Cmp, Cmp->getArg(1), State.Env);
 790           })
 791
 792       // returns optional
 793       .CaseOfCFGStmt<CallExpr>(isCallReturningOptional(),
 794                                transferCallReturningOptional)
 795
 796       .Build();
 797 }
 798
 799 llvm::SmallVector<SourceLocation> diagnoseUnwrapCall(const Expr *ObjectExpr,
 800                                                      const Environment &Env) {
 801   if (auto *OptionalLoc = cast_or_null<RecordStorageLocation>(
 802           getLocBehindPossiblePointer(*ObjectExpr, Env))) {
 803     auto *Prop = Env.getValue(locForHasValue(*OptionalLoc));
 804     if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
 805       if (Env.proves(HasValueVal->formula()))
 806         return {};
 807     }
 808   }
 809
 810   // Record that this unwrap is *not* provably safe.
 811   // FIXME: include either the name of the optional (if applicable) or a source
 812   // range of the access for easier interpretation of the result.
 813   return {ObjectExpr->getBeginLoc()};
 814 }
 815
 816 auto buildDiagnoseMatchSwitch(
 817     const UncheckedOptionalAccessModelOptions &Options) {
 818   // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
 819   // lot of duplicated work (e.g. string comparisons), consider providing APIs
 820   // that avoid it through memoization.
 821   auto IgnorableOptional = ignorableOptional(Options);
 822   return CFGMatchSwitchBuilder<const Environment,
 823                                llvm::SmallVector<SourceLocation>>()
 824       // optional::value
 825       .CaseOfCFGStmt<CXXMemberCallExpr>(
 826           valueCall(IgnorableOptional),
 827           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
 828              const Environment &Env) {
 829             return diagnoseUnwrapCall(E->getImplicitObjectArgument(), Env);
 830           })
 831
 832       // optional::operator*, optional::operator->
 833       .CaseOfCFGStmt<CallExpr>(valueOperatorCall(IgnorableOptional),
 834                                [](const CallExpr *E,
 835                                   const MatchFinder::MatchResult &,
 836                                   const Environment &Env) {
 837                                  return diagnoseUnwrapCall(E->getArg(0), Env);
 838                                })
 839       .Build();
 840 }
 841
 842 } // namespace
 843
 844 ast_matchers::DeclarationMatcher
 845 UncheckedOptionalAccessModel::optionalClassDecl() {
 846   return optionalClass();
 847 }
 848
 849 static QualType valueTypeFromOptionalType(QualType OptionalTy) {
 850   auto *CTSD =
 851       cast<ClassTemplateSpecializationDecl>(OptionalTy->getAsCXXRecordDecl());
 852   return CTSD->getTemplateArgs()[0].getAsType();
 853 }
 854
 855 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx,
 856                                                            Environment &Env)
 857     : DataflowAnalysis<UncheckedOptionalAccessModel, NoopLattice>(Ctx),
 858       TransferMatchSwitch(buildTransferMatchSwitch()) {
 859   Env.getDataflowAnalysisContext().setSyntheticFieldCallback(
 860       [&Ctx](QualType Ty) -> llvm::StringMap<QualType> {
 861         if (!isOptionalType(Ty))
 862           return {};
 863         return {{"value", valueTypeFromOptionalType(Ty)},
 864                 {"has_value", Ctx.BoolTy}};
 865       });
 866 }
 867
 868 void UncheckedOptionalAccessModel::transfer(const CFGElement &Elt,
 869                                             NoopLattice &L, Environment &Env) {
 870   LatticeTransferState State(L, Env);
 871   TransferMatchSwitch(Elt, getASTContext(), State);
 872 }
 873
 874 UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser(
 875     UncheckedOptionalAccessModelOptions Options)
 876     : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {}
 877
 878 } // namespace dataflow
 879 } // namespace clang