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 #include <vector> 38 39 namespace clang { 40 namespace dataflow { 41 42 static bool isTopLevelNamespaceWithName(const NamespaceDecl &NS, 43 llvm::StringRef Name) { 44 return NS.getDeclName().isIdentifier() && NS.getName() == Name && 45 NS.getParent() != nullptr && NS.getParent()->isTranslationUnit(); 46 } 47 48 static bool hasOptionalClassName(const CXXRecordDecl &RD) { 49 if (!RD.getDeclName().isIdentifier()) 50 return false; 51 52 if (RD.getName() == "optional") { 53 if (const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext())) 54 return N->isStdNamespace() || isTopLevelNamespaceWithName(*N, "absl"); 55 return false; 56 } 57 58 if (RD.getName() == "Optional") { 59 // Check whether namespace is "::base" or "::folly". 60 const auto *N = dyn_cast_or_null<NamespaceDecl>(RD.getDeclContext()); 61 return N != nullptr && (isTopLevelNamespaceWithName(*N, "base") || 62 isTopLevelNamespaceWithName(*N, "folly")); 63 } 64 65 return false; 66 } 67 68 namespace { 69 70 using namespace ::clang::ast_matchers; 71 using LatticeTransferState = TransferState<NoopLattice>; 72 73 AST_MATCHER(CXXRecordDecl, hasOptionalClassNameMatcher) { 74 return hasOptionalClassName(Node); 75 } 76 77 DeclarationMatcher optionalClass() { 78 return classTemplateSpecializationDecl( 79 hasOptionalClassNameMatcher(), 80 hasTemplateArgument(0, refersToType(type().bind("T")))); 81 } 82 83 auto optionalOrAliasType() { 84 return hasUnqualifiedDesugaredType( 85 recordType(hasDeclaration(optionalClass()))); 86 } 87 88 /// Matches any of the spellings of the optional types and sugar, aliases, etc. 89 auto hasOptionalType() { return hasType(optionalOrAliasType()); } 90 91 auto isOptionalMemberCallWithNameMatcher( 92 ast_matchers::internal::Matcher<NamedDecl> matcher, 93 const std::optional<StatementMatcher> &Ignorable = std::nullopt) { 94 auto Exception = unless(Ignorable ? expr(anyOf(*Ignorable, cxxThisExpr())) 95 : cxxThisExpr()); 96 return cxxMemberCallExpr( 97 on(expr(Exception, 98 anyOf(hasOptionalType(), 99 hasType(pointerType(pointee(optionalOrAliasType())))))), 100 callee(cxxMethodDecl(matcher))); 101 } 102 103 auto isOptionalOperatorCallWithName( 104 llvm::StringRef operator_name, 105 const std::optional<StatementMatcher> &Ignorable = std::nullopt) { 106 return cxxOperatorCallExpr( 107 hasOverloadedOperatorName(operator_name), 108 callee(cxxMethodDecl(ofClass(optionalClass()))), 109 Ignorable ? callExpr(unless(hasArgument(0, *Ignorable))) : callExpr()); 110 } 111 112 auto isMakeOptionalCall() { 113 return callExpr(callee(functionDecl(hasAnyName( 114 "std::make_optional", "base::make_optional", 115 "absl::make_optional", "folly::make_optional"))), 116 hasOptionalType()); 117 } 118 119 auto nulloptTypeDecl() { 120 return namedDecl(hasAnyName("std::nullopt_t", "absl::nullopt_t", 121 "base::nullopt_t", "folly::None")); 122 } 123 124 auto hasNulloptType() { return hasType(nulloptTypeDecl()); } 125 126 // `optional` or `nullopt_t` 127 auto hasAnyOptionalType() { 128 return hasType(hasUnqualifiedDesugaredType( 129 recordType(hasDeclaration(anyOf(nulloptTypeDecl(), optionalClass()))))); 130 } 131 132 auto inPlaceClass() { 133 return recordDecl(hasAnyName("std::in_place_t", "absl::in_place_t", 134 "base::in_place_t", "folly::in_place_t")); 135 } 136 137 auto isOptionalNulloptConstructor() { 138 return cxxConstructExpr( 139 hasOptionalType(), 140 hasDeclaration(cxxConstructorDecl(parameterCountIs(1), 141 hasParameter(0, hasNulloptType())))); 142 } 143 144 auto isOptionalInPlaceConstructor() { 145 return cxxConstructExpr(hasOptionalType(), 146 hasArgument(0, hasType(inPlaceClass()))); 147 } 148 149 auto isOptionalValueOrConversionConstructor() { 150 return cxxConstructExpr( 151 hasOptionalType(), 152 unless(hasDeclaration( 153 cxxConstructorDecl(anyOf(isCopyConstructor(), isMoveConstructor())))), 154 argumentCountIs(1), hasArgument(0, unless(hasNulloptType()))); 155 } 156 157 auto isOptionalValueOrConversionAssignment() { 158 return cxxOperatorCallExpr( 159 hasOverloadedOperatorName("="), 160 callee(cxxMethodDecl(ofClass(optionalClass()))), 161 unless(hasDeclaration(cxxMethodDecl( 162 anyOf(isCopyAssignmentOperator(), isMoveAssignmentOperator())))), 163 argumentCountIs(2), hasArgument(1, unless(hasNulloptType()))); 164 } 165 166 auto isNulloptConstructor() { 167 return cxxConstructExpr(hasNulloptType(), argumentCountIs(1), 168 hasArgument(0, hasNulloptType())); 169 } 170 171 auto isOptionalNulloptAssignment() { 172 return cxxOperatorCallExpr(hasOverloadedOperatorName("="), 173 callee(cxxMethodDecl(ofClass(optionalClass()))), 174 argumentCountIs(2), 175 hasArgument(1, hasNulloptType())); 176 } 177 178 auto isStdSwapCall() { 179 return callExpr(callee(functionDecl(hasName("std::swap"))), 180 argumentCountIs(2), hasArgument(0, hasOptionalType()), 181 hasArgument(1, hasOptionalType())); 182 } 183 184 auto isStdForwardCall() { 185 return callExpr(callee(functionDecl(hasName("std::forward"))), 186 argumentCountIs(1), hasArgument(0, hasOptionalType())); 187 } 188 189 constexpr llvm::StringLiteral ValueOrCallID = "ValueOrCall"; 190 191 auto isValueOrStringEmptyCall() { 192 // `opt.value_or("").empty()` 193 return cxxMemberCallExpr( 194 callee(cxxMethodDecl(hasName("empty"))), 195 onImplicitObjectArgument(ignoringImplicit( 196 cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))), 197 callee(cxxMethodDecl(hasName("value_or"), 198 ofClass(optionalClass()))), 199 hasArgument(0, stringLiteral(hasSize(0)))) 200 .bind(ValueOrCallID)))); 201 } 202 203 auto isValueOrNotEqX() { 204 auto ComparesToSame = [](ast_matchers::internal::Matcher<Stmt> Arg) { 205 return hasOperands( 206 ignoringImplicit( 207 cxxMemberCallExpr(on(expr(unless(cxxThisExpr()))), 208 callee(cxxMethodDecl(hasName("value_or"), 209 ofClass(optionalClass()))), 210 hasArgument(0, Arg)) 211 .bind(ValueOrCallID)), 212 ignoringImplicit(Arg)); 213 }; 214 215 // `opt.value_or(X) != X`, for X is `nullptr`, `""`, or `0`. Ideally, we'd 216 // support this pattern for any expression, but the AST does not have a 217 // generic expression comparison facility, so we specialize to common cases 218 // seen in practice. FIXME: define a matcher that compares values across 219 // nodes, which would let us generalize this to any `X`. 220 return binaryOperation(hasOperatorName("!="), 221 anyOf(ComparesToSame(cxxNullPtrLiteralExpr()), 222 ComparesToSame(stringLiteral(hasSize(0))), 223 ComparesToSame(integerLiteral(equals(0))))); 224 } 225 226 auto isCallReturningOptional() { 227 return callExpr(hasType(qualType(anyOf( 228 optionalOrAliasType(), referenceType(pointee(optionalOrAliasType())))))); 229 } 230 231 template <typename L, typename R> 232 auto isComparisonOperatorCall(L lhs_arg_matcher, R rhs_arg_matcher) { 233 return cxxOperatorCallExpr( 234 anyOf(hasOverloadedOperatorName("=="), hasOverloadedOperatorName("!=")), 235 argumentCountIs(2), hasArgument(0, lhs_arg_matcher), 236 hasArgument(1, rhs_arg_matcher)); 237 } 238 239 /// Ensures that `Expr` is mapped to a `BoolValue` and returns its formula. 240 const Formula &forceBoolValue(Environment &Env, const Expr &Expr) { 241 auto *Value = cast_or_null<BoolValue>(Env.getValue(Expr)); 242 if (Value != nullptr) 243 return Value->formula(); 244 245 Value = &Env.makeAtomicBoolValue(); 246 Env.setValue(Expr, *Value); 247 return Value->formula(); 248 } 249 250 /// Sets `HasValueVal` as the symbolic value that represents the "has_value" 251 /// property of the optional value `OptionalVal`. 252 void setHasValue(Value &OptionalVal, BoolValue &HasValueVal) { 253 OptionalVal.setProperty("has_value", HasValueVal); 254 } 255 256 /// Creates a symbolic value for an `optional` value at an existing storage 257 /// location. Uses `HasValueVal` as the symbolic value of the "has_value" 258 /// property. 259 StructValue &createOptionalValue(AggregateStorageLocation &Loc, 260 BoolValue &HasValueVal, Environment &Env) { 261 auto &OptionalVal = Env.create<StructValue>(Loc); 262 Env.setValue(Loc, OptionalVal); 263 setHasValue(OptionalVal, HasValueVal); 264 return OptionalVal; 265 } 266 267 /// Returns the symbolic value that represents the "has_value" property of the 268 /// optional value `OptionalVal`. Returns null if `OptionalVal` is null. 269 BoolValue *getHasValue(Environment &Env, Value *OptionalVal) { 270 if (OptionalVal != nullptr) { 271 auto *HasValueVal = 272 cast_or_null<BoolValue>(OptionalVal->getProperty("has_value")); 273 if (HasValueVal == nullptr) { 274 HasValueVal = &Env.makeAtomicBoolValue(); 275 OptionalVal->setProperty("has_value", *HasValueVal); 276 } 277 return HasValueVal; 278 } 279 return nullptr; 280 } 281 282 /// Returns true if and only if `Type` is an optional type. 283 bool isOptionalType(QualType Type) { 284 if (!Type->isRecordType()) 285 return false; 286 const CXXRecordDecl *D = Type->getAsCXXRecordDecl(); 287 return D != nullptr && hasOptionalClassName(*D); 288 } 289 290 /// Returns the number of optional wrappers in `Type`. 291 /// 292 /// For example, if `Type` is `optional<optional<int>>`, the result of this 293 /// function will be 2. 294 int countOptionalWrappers(const ASTContext &ASTCtx, QualType Type) { 295 if (!isOptionalType(Type)) 296 return 0; 297 return 1 + countOptionalWrappers( 298 ASTCtx, 299 cast<ClassTemplateSpecializationDecl>(Type->getAsRecordDecl()) 300 ->getTemplateArgs() 301 .get(0) 302 .getAsType() 303 .getDesugaredType(ASTCtx)); 304 } 305 306 /// Tries to initialize the `optional`'s value (that is, contents), and return 307 /// its location. Returns nullptr if the value can't be represented. 308 StorageLocation *maybeInitializeOptionalValueMember(QualType Q, 309 Value &OptionalVal, 310 Environment &Env) { 311 // The "value" property represents a synthetic field. As such, it needs 312 // `StorageLocation`, like normal fields (and other variables). So, we model 313 // it with a `PointerValue`, since that includes a storage location. Once 314 // the property is set, it will be shared by all environments that access the 315 // `Value` representing the optional (here, `OptionalVal`). 316 if (auto *ValueProp = OptionalVal.getProperty("value")) { 317 auto *ValuePtr = clang::cast<PointerValue>(ValueProp); 318 auto &ValueLoc = ValuePtr->getPointeeLoc(); 319 if (Env.getValue(ValueLoc) != nullptr) 320 return &ValueLoc; 321 322 // The property was previously set, but the value has been lost. This can 323 // happen in various situations, for example: 324 // - Because of an environment merge (where the two environments mapped the 325 // property to different values, which resulted in them both being 326 // discarded). 327 // - When two blocks in the CFG, with neither a dominator of the other, 328 // visit the same optional value. (FIXME: This is something we can and 329 // should fix -- see also the lengthy FIXME below.) 330 // - Or even when a block is revisited during testing to collect 331 // per-statement state. 332 // FIXME: This situation means that the optional contents are not shared 333 // between branches and the like. Practically, this lack of sharing 334 // reduces the precision of the model when the contents are relevant to 335 // the check, like another optional or a boolean that influences control 336 // flow. 337 if (ValueLoc.getType()->isRecordType()) { 338 refreshStructValue(cast<AggregateStorageLocation>(ValueLoc), Env); 339 return &ValueLoc; 340 } else { 341 auto *ValueVal = Env.createValue(ValueLoc.getType()); 342 if (ValueVal == nullptr) 343 return nullptr; 344 Env.setValue(ValueLoc, *ValueVal); 345 return &ValueLoc; 346 } 347 } 348 349 auto Ty = Q.getNonReferenceType(); 350 auto &ValueLoc = Env.createObject(Ty); 351 auto &ValuePtr = Env.create<PointerValue>(ValueLoc); 352 // FIXME: 353 // The change we make to the `value` property below may become visible to 354 // other blocks that aren't successors of the current block and therefore 355 // don't see the change we made above mapping `ValueLoc` to `ValueVal`. For 356 // example: 357 // 358 // void target(optional<int> oo, bool b) { 359 // // `oo` is associated with a `StructValue` here, which we will call 360 // // `OptionalVal`. 361 // 362 // // The `has_value` property is set on `OptionalVal` (but not the 363 // // `value` property yet). 364 // if (!oo.has_value()) return; 365 // 366 // if (b) { 367 // // Let's assume we transfer the `if` branch first. 368 // // 369 // // This causes us to call `maybeInitializeOptionalValueMember()`, 370 // // which causes us to set the `value` property on `OptionalVal` 371 // // (which had not been set until this point). This `value` property 372 // // refers to a `PointerValue`, which in turn refers to a 373 // // StorageLocation` that is associated to an `IntegerValue`. 374 // oo.value(); 375 // } else { 376 // // Let's assume we transfer the `else` branch after the `if` branch. 377 // // 378 // // We see the `value` property that the `if` branch set on 379 // // `OptionalVal`, but in the environment for this block, the 380 // // `StorageLocation` in the `PointerValue` is not associated with any 381 // // `Value`. 382 // oo.value(); 383 // } 384 // } 385 // 386 // This situation is currently "saved" by the code above that checks whether 387 // the `value` property is already set, and if, the `ValueLoc` is not 388 // associated with a `ValueVal`, creates a new `ValueVal`. 389 // 390 // However, what we should really do is to make sure that the change to the 391 // `value` property does not "leak" to other blocks that are not successors 392 // of this block. To do this, instead of simply setting the `value` property 393 // on the existing `OptionalVal`, we should create a new `Value` for the 394 // optional, set the property on that, and associate the storage location that 395 // is currently associated with the existing `OptionalVal` with the newly 396 // created `Value` instead. 397 OptionalVal.setProperty("value", ValuePtr); 398 return &ValueLoc; 399 } 400 401 void initializeOptionalReference(const Expr *OptionalExpr, 402 const MatchFinder::MatchResult &, 403 LatticeTransferState &State) { 404 if (auto *OptionalVal = State.Env.getValue(*OptionalExpr)) { 405 if (OptionalVal->getProperty("has_value") == nullptr) { 406 setHasValue(*OptionalVal, State.Env.makeAtomicBoolValue()); 407 } 408 } 409 } 410 411 /// Returns true if and only if `OptionalVal` is initialized and known to be 412 /// empty in `Env`. 413 bool isEmptyOptional(const Value &OptionalVal, const Environment &Env) { 414 auto *HasValueVal = 415 cast_or_null<BoolValue>(OptionalVal.getProperty("has_value")); 416 return HasValueVal != nullptr && 417 Env.flowConditionImplies(Env.arena().makeNot(HasValueVal->formula())); 418 } 419 420 /// Returns true if and only if `OptionalVal` is initialized and known to be 421 /// non-empty in `Env`. 422 bool isNonEmptyOptional(const Value &OptionalVal, const Environment &Env) { 423 auto *HasValueVal = 424 cast_or_null<BoolValue>(OptionalVal.getProperty("has_value")); 425 return HasValueVal != nullptr && 426 Env.flowConditionImplies(HasValueVal->formula()); 427 } 428 429 Value *getValueBehindPossiblePointer(const Expr &E, const Environment &Env) { 430 Value *Val = Env.getValue(E); 431 if (auto *PointerVal = dyn_cast_or_null<PointerValue>(Val)) 432 return Env.getValue(PointerVal->getPointeeLoc()); 433 return Val; 434 } 435 436 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr, 437 LatticeTransferState &State) { 438 if (auto *OptionalVal = 439 getValueBehindPossiblePointer(*ObjectExpr, State.Env)) { 440 if (State.Env.getStorageLocation(*UnwrapExpr) == nullptr) 441 if (auto *Loc = maybeInitializeOptionalValueMember( 442 UnwrapExpr->getType(), *OptionalVal, State.Env)) 443 State.Env.setStorageLocation(*UnwrapExpr, *Loc); 444 } 445 } 446 447 void transferArrowOpCall(const Expr *UnwrapExpr, const Expr *ObjectExpr, 448 LatticeTransferState &State) { 449 if (auto *OptionalVal = 450 getValueBehindPossiblePointer(*ObjectExpr, State.Env)) { 451 if (auto *Loc = maybeInitializeOptionalValueMember( 452 UnwrapExpr->getType()->getPointeeType(), *OptionalVal, State.Env)) { 453 State.Env.setValue(*UnwrapExpr, State.Env.create<PointerValue>(*Loc)); 454 } 455 } 456 } 457 458 void transferMakeOptionalCall(const CallExpr *E, 459 const MatchFinder::MatchResult &, 460 LatticeTransferState &State) { 461 createOptionalValue(State.Env.getResultObjectLocation(*E), 462 State.Env.getBoolLiteralValue(true), State.Env); 463 } 464 465 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr, 466 const MatchFinder::MatchResult &, 467 LatticeTransferState &State) { 468 if (auto *HasValueVal = getHasValue( 469 State.Env, getValueBehindPossiblePointer( 470 *CallExpr->getImplicitObjectArgument(), State.Env))) { 471 State.Env.setValue(*CallExpr, *HasValueVal); 472 } 473 } 474 475 /// `ModelPred` builds a logical formula relating the predicate in 476 /// `ValueOrPredExpr` to the optional's `has_value` property. 477 void transferValueOrImpl( 478 const clang::Expr *ValueOrPredExpr, const MatchFinder::MatchResult &Result, 479 LatticeTransferState &State, 480 const Formula &(*ModelPred)(Environment &Env, const Formula &ExprVal, 481 const Formula &HasValueVal)) { 482 auto &Env = State.Env; 483 484 const auto *ObjectArgumentExpr = 485 Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID) 486 ->getImplicitObjectArgument(); 487 488 auto *HasValueVal = getHasValue( 489 State.Env, getValueBehindPossiblePointer(*ObjectArgumentExpr, State.Env)); 490 if (HasValueVal == nullptr) 491 return; 492 493 Env.addToFlowCondition(ModelPred(Env, forceBoolValue(Env, *ValueOrPredExpr), 494 HasValueVal->formula())); 495 } 496 497 void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr, 498 const MatchFinder::MatchResult &Result, 499 LatticeTransferState &State) { 500 return transferValueOrImpl(ComparisonExpr, Result, State, 501 [](Environment &Env, const Formula &ExprVal, 502 const Formula &HasValueVal) -> const Formula & { 503 auto &A = Env.arena(); 504 // If the result is *not* empty, then we know the 505 // optional must have been holding a value. If 506 // `ExprVal` is true, though, we don't learn 507 // anything definite about `has_value`, so we 508 // don't add any corresponding implications to 509 // the flow condition. 510 return A.makeImplies(A.makeNot(ExprVal), 511 HasValueVal); 512 }); 513 } 514 515 void transferValueOrNotEqX(const Expr *ComparisonExpr, 516 const MatchFinder::MatchResult &Result, 517 LatticeTransferState &State) { 518 transferValueOrImpl(ComparisonExpr, Result, State, 519 [](Environment &Env, const Formula &ExprVal, 520 const Formula &HasValueVal) -> const Formula & { 521 auto &A = Env.arena(); 522 // We know that if `(opt.value_or(X) != X)` then 523 // `opt.hasValue()`, even without knowing further 524 // details about the contents of `opt`. 525 return A.makeImplies(ExprVal, HasValueVal); 526 }); 527 } 528 529 void transferCallReturningOptional(const CallExpr *E, 530 const MatchFinder::MatchResult &Result, 531 LatticeTransferState &State) { 532 if (State.Env.getValue(*E) != nullptr) 533 return; 534 535 AggregateStorageLocation *Loc = nullptr; 536 if (E->isPRValue()) { 537 Loc = &State.Env.getResultObjectLocation(*E); 538 } else { 539 Loc = cast_or_null<AggregateStorageLocation>( 540 State.Env.getStorageLocation(*E)); 541 if (Loc == nullptr) { 542 Loc = 543 &cast<AggregateStorageLocation>(State.Env.createStorageLocation(*E)); 544 State.Env.setStorageLocation(*E, *Loc); 545 } 546 } 547 548 createOptionalValue(*Loc, State.Env.makeAtomicBoolValue(), State.Env); 549 } 550 551 void constructOptionalValue(const Expr &E, Environment &Env, 552 BoolValue &HasValueVal) { 553 AggregateStorageLocation &Loc = Env.getResultObjectLocation(E); 554 Env.setValue(E, createOptionalValue(Loc, HasValueVal, Env)); 555 } 556 557 /// Returns a symbolic value for the "has_value" property of an `optional<T>` 558 /// value that is constructed/assigned from a value of type `U` or `optional<U>` 559 /// where `T` is constructible from `U`. 560 BoolValue &valueOrConversionHasValue(const FunctionDecl &F, const Expr &E, 561 const MatchFinder::MatchResult &MatchRes, 562 LatticeTransferState &State) { 563 assert(F.getTemplateSpecializationArgs() != nullptr); 564 assert(F.getTemplateSpecializationArgs()->size() > 0); 565 566 const int TemplateParamOptionalWrappersCount = 567 countOptionalWrappers(*MatchRes.Context, F.getTemplateSpecializationArgs() 568 ->get(0) 569 .getAsType() 570 .getNonReferenceType()); 571 const int ArgTypeOptionalWrappersCount = countOptionalWrappers( 572 *MatchRes.Context, E.getType().getNonReferenceType()); 573 574 // Check if this is a constructor/assignment call for `optional<T>` with 575 // argument of type `U` such that `T` is constructible from `U`. 576 if (TemplateParamOptionalWrappersCount == ArgTypeOptionalWrappersCount) 577 return State.Env.getBoolLiteralValue(true); 578 579 // This is a constructor/assignment call for `optional<T>` with argument of 580 // type `optional<U>` such that `T` is constructible from `U`. 581 if (auto *HasValueVal = getHasValue(State.Env, State.Env.getValue(E))) 582 return *HasValueVal; 583 return State.Env.makeAtomicBoolValue(); 584 } 585 586 void transferValueOrConversionConstructor( 587 const CXXConstructExpr *E, const MatchFinder::MatchResult &MatchRes, 588 LatticeTransferState &State) { 589 assert(E->getNumArgs() > 0); 590 591 constructOptionalValue(*E, State.Env, 592 valueOrConversionHasValue(*E->getConstructor(), 593 *E->getArg(0), MatchRes, 594 State)); 595 } 596 597 void transferAssignment(const CXXOperatorCallExpr *E, BoolValue &HasValueVal, 598 LatticeTransferState &State) { 599 assert(E->getNumArgs() > 0); 600 601 if (auto *Loc = cast<AggregateStorageLocation>( 602 State.Env.getStorageLocation(*E->getArg(0)))) { 603 createOptionalValue(*Loc, HasValueVal, State.Env); 604 605 // Assign a storage location for the whole expression. 606 State.Env.setStorageLocation(*E, *Loc); 607 } 608 } 609 610 void transferValueOrConversionAssignment( 611 const CXXOperatorCallExpr *E, const MatchFinder::MatchResult &MatchRes, 612 LatticeTransferState &State) { 613 assert(E->getNumArgs() > 1); 614 transferAssignment(E, 615 valueOrConversionHasValue(*E->getDirectCallee(), 616 *E->getArg(1), MatchRes, State), 617 State); 618 } 619 620 void transferNulloptAssignment(const CXXOperatorCallExpr *E, 621 const MatchFinder::MatchResult &, 622 LatticeTransferState &State) { 623 transferAssignment(E, State.Env.getBoolLiteralValue(false), State); 624 } 625 626 void transferSwap(AggregateStorageLocation *Loc1, 627 AggregateStorageLocation *Loc2, Environment &Env) { 628 // We account for cases where one or both of the optionals are not modeled, 629 // either lacking associated storage locations, or lacking values associated 630 // to such storage locations. 631 632 if (Loc1 == nullptr) { 633 if (Loc2 != nullptr) 634 createOptionalValue(*Loc2, Env.makeAtomicBoolValue(), Env); 635 return; 636 } 637 if (Loc2 == nullptr) { 638 createOptionalValue(*Loc1, Env.makeAtomicBoolValue(), Env); 639 return; 640 } 641 642 // Both expressions have locations, though they may not have corresponding 643 // values. In that case, we create a fresh value at this point. Note that if 644 // two branches both do this, they will not share the value, but it at least 645 // allows for local reasoning about the value. To avoid the above, we would 646 // need *lazy* value allocation. 647 // FIXME: allocate values lazily, instead of just creating a fresh value. 648 BoolValue *BoolVal1 = getHasValue(Env, Env.getValue(*Loc1)); 649 if (BoolVal1 == nullptr) 650 BoolVal1 = &Env.makeAtomicBoolValue(); 651 652 BoolValue *BoolVal2 = getHasValue(Env, Env.getValue(*Loc2)); 653 if (BoolVal2 == nullptr) 654 BoolVal2 = &Env.makeAtomicBoolValue(); 655 656 createOptionalValue(*Loc1, *BoolVal2, Env); 657 createOptionalValue(*Loc2, *BoolVal1, Env); 658 } 659 660 void transferSwapCall(const CXXMemberCallExpr *E, 661 const MatchFinder::MatchResult &, 662 LatticeTransferState &State) { 663 assert(E->getNumArgs() == 1); 664 auto *OtherLoc = cast_or_null<AggregateStorageLocation>( 665 State.Env.getStorageLocation(*E->getArg(0))); 666 transferSwap(getImplicitObjectLocation(*E, State.Env), OtherLoc, State.Env); 667 } 668 669 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &, 670 LatticeTransferState &State) { 671 assert(E->getNumArgs() == 2); 672 auto *Arg0Loc = cast_or_null<AggregateStorageLocation>( 673 State.Env.getStorageLocation(*E->getArg(0))); 674 auto *Arg1Loc = cast_or_null<AggregateStorageLocation>( 675 State.Env.getStorageLocation(*E->getArg(1))); 676 transferSwap(Arg0Loc, Arg1Loc, State.Env); 677 } 678 679 void transferStdForwardCall(const CallExpr *E, const MatchFinder::MatchResult &, 680 LatticeTransferState &State) { 681 assert(E->getNumArgs() == 1); 682 683 if (auto *Loc = State.Env.getStorageLocation(*E->getArg(0))) 684 State.Env.setStorageLocation(*E, *Loc); 685 } 686 687 const Formula &evaluateEquality(Arena &A, const Formula &EqVal, 688 const Formula &LHS, const Formula &RHS) { 689 // Logically, an optional<T> object is composed of two values - a `has_value` 690 // bit and a value of type T. Equality of optional objects compares both 691 // values. Therefore, merely comparing the `has_value` bits isn't sufficient: 692 // when two optional objects are engaged, the equality of their respective 693 // values of type T matters. Since we only track the `has_value` bits, we 694 // can't make any conclusions about equality when we know that two optional 695 // objects are engaged. 696 // 697 // We express this as two facts about the equality: 698 // a) EqVal => (LHS & RHS) v (!RHS & !LHS) 699 // If they are equal, then either both are set or both are unset. 700 // b) (!LHS & !RHS) => EqVal 701 // If neither is set, then they are equal. 702 // We rewrite b) as !EqVal => (LHS v RHS), for a more compact formula. 703 return A.makeAnd( 704 A.makeImplies(EqVal, A.makeOr(A.makeAnd(LHS, RHS), 705 A.makeAnd(A.makeNot(LHS), A.makeNot(RHS)))), 706 A.makeImplies(A.makeNot(EqVal), A.makeOr(LHS, RHS))); 707 } 708 709 void transferOptionalAndOptionalCmp(const clang::CXXOperatorCallExpr *CmpExpr, 710 const MatchFinder::MatchResult &, 711 LatticeTransferState &State) { 712 Environment &Env = State.Env; 713 auto &A = Env.arena(); 714 auto *CmpValue = &forceBoolValue(Env, *CmpExpr); 715 if (auto *LHasVal = getHasValue(Env, Env.getValue(*CmpExpr->getArg(0)))) 716 if (auto *RHasVal = getHasValue(Env, Env.getValue(*CmpExpr->getArg(1)))) { 717 if (CmpExpr->getOperator() == clang::OO_ExclaimEqual) 718 CmpValue = &A.makeNot(*CmpValue); 719 Env.addToFlowCondition(evaluateEquality(A, *CmpValue, LHasVal->formula(), 720 RHasVal->formula())); 721 } 722 } 723 724 void transferOptionalAndValueCmp(const clang::CXXOperatorCallExpr *CmpExpr, 725 const clang::Expr *E, Environment &Env) { 726 auto &A = Env.arena(); 727 auto *CmpValue = &forceBoolValue(Env, *CmpExpr); 728 if (auto *HasVal = getHasValue(Env, Env.getValue(*E))) { 729 if (CmpExpr->getOperator() == clang::OO_ExclaimEqual) 730 CmpValue = &A.makeNot(*CmpValue); 731 Env.addToFlowCondition( 732 evaluateEquality(A, *CmpValue, HasVal->formula(), A.makeLiteral(true))); 733 } 734 } 735 736 std::optional<StatementMatcher> 737 ignorableOptional(const UncheckedOptionalAccessModelOptions &Options) { 738 if (Options.IgnoreSmartPointerDereference) { 739 auto SmartPtrUse = expr(ignoringParenImpCasts(cxxOperatorCallExpr( 740 anyOf(hasOverloadedOperatorName("->"), hasOverloadedOperatorName("*")), 741 unless(hasArgument(0, expr(hasOptionalType())))))); 742 return expr( 743 anyOf(SmartPtrUse, memberExpr(hasObjectExpression(SmartPtrUse)))); 744 } 745 return std::nullopt; 746 } 747 748 StatementMatcher 749 valueCall(const std::optional<StatementMatcher> &IgnorableOptional) { 750 return isOptionalMemberCallWithNameMatcher(hasName("value"), 751 IgnorableOptional); 752 } 753 754 StatementMatcher 755 valueOperatorCall(const std::optional<StatementMatcher> &IgnorableOptional) { 756 return expr(anyOf(isOptionalOperatorCallWithName("*", IgnorableOptional), 757 isOptionalOperatorCallWithName("->", IgnorableOptional))); 758 } 759 760 auto buildTransferMatchSwitch() { 761 // FIXME: Evaluate the efficiency of matchers. If using matchers results in a 762 // lot of duplicated work (e.g. string comparisons), consider providing APIs 763 // that avoid it through memoization. 764 return CFGMatchSwitchBuilder<LatticeTransferState>() 765 // Attach a symbolic "has_value" state to optional values that we see for 766 // the first time. 767 .CaseOfCFGStmt<Expr>( 768 expr(anyOf(declRefExpr(), memberExpr()), hasOptionalType()), 769 initializeOptionalReference) 770 771 // make_optional 772 .CaseOfCFGStmt<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall) 773 774 // optional::optional (in place) 775 .CaseOfCFGStmt<CXXConstructExpr>( 776 isOptionalInPlaceConstructor(), 777 [](const CXXConstructExpr *E, const MatchFinder::MatchResult &, 778 LatticeTransferState &State) { 779 constructOptionalValue(*E, State.Env, 780 State.Env.getBoolLiteralValue(true)); 781 }) 782 // nullopt_t::nullopt_t 783 .CaseOfCFGStmt<CXXConstructExpr>( 784 isNulloptConstructor(), 785 [](const CXXConstructExpr *E, const MatchFinder::MatchResult &, 786 LatticeTransferState &State) { 787 constructOptionalValue(*E, State.Env, 788 State.Env.getBoolLiteralValue(false)); 789 }) 790 // optional::optional(nullopt_t) 791 .CaseOfCFGStmt<CXXConstructExpr>( 792 isOptionalNulloptConstructor(), 793 [](const CXXConstructExpr *E, const MatchFinder::MatchResult &, 794 LatticeTransferState &State) { 795 constructOptionalValue(*E, State.Env, 796 State.Env.getBoolLiteralValue(false)); 797 }) 798 // optional::optional (value/conversion) 799 .CaseOfCFGStmt<CXXConstructExpr>(isOptionalValueOrConversionConstructor(), 800 transferValueOrConversionConstructor) 801 802 // optional::operator= 803 .CaseOfCFGStmt<CXXOperatorCallExpr>( 804 isOptionalValueOrConversionAssignment(), 805 transferValueOrConversionAssignment) 806 .CaseOfCFGStmt<CXXOperatorCallExpr>(isOptionalNulloptAssignment(), 807 transferNulloptAssignment) 808 809 // optional::value 810 .CaseOfCFGStmt<CXXMemberCallExpr>( 811 valueCall(std::nullopt), 812 [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &, 813 LatticeTransferState &State) { 814 transferUnwrapCall(E, E->getImplicitObjectArgument(), State); 815 }) 816 817 // optional::operator* 818 .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("*"), 819 [](const CallExpr *E, 820 const MatchFinder::MatchResult &, 821 LatticeTransferState &State) { 822 transferUnwrapCall(E, E->getArg(0), State); 823 }) 824 825 // optional::operator-> 826 .CaseOfCFGStmt<CallExpr>(isOptionalOperatorCallWithName("->"), 827 [](const CallExpr *E, 828 const MatchFinder::MatchResult &, 829 LatticeTransferState &State) { 830 transferArrowOpCall(E, E->getArg(0), State); 831 }) 832 833 // optional::has_value, optional::hasValue 834 // Of the supported optionals only folly::Optional uses hasValue, but this 835 // will also pass for other types 836 .CaseOfCFGStmt<CXXMemberCallExpr>( 837 isOptionalMemberCallWithNameMatcher( 838 hasAnyName("has_value", "hasValue")), 839 transferOptionalHasValueCall) 840 841 // optional::operator bool 842 .CaseOfCFGStmt<CXXMemberCallExpr>( 843 isOptionalMemberCallWithNameMatcher(hasName("operator bool")), 844 transferOptionalHasValueCall) 845 846 // optional::emplace 847 .CaseOfCFGStmt<CXXMemberCallExpr>( 848 isOptionalMemberCallWithNameMatcher(hasName("emplace")), 849 [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &, 850 LatticeTransferState &State) { 851 if (AggregateStorageLocation *Loc = 852 getImplicitObjectLocation(*E, State.Env)) { 853 createOptionalValue(*Loc, State.Env.getBoolLiteralValue(true), 854 State.Env); 855 } 856 }) 857 858 // optional::reset 859 .CaseOfCFGStmt<CXXMemberCallExpr>( 860 isOptionalMemberCallWithNameMatcher(hasName("reset")), 861 [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &, 862 LatticeTransferState &State) { 863 if (AggregateStorageLocation *Loc = 864 getImplicitObjectLocation(*E, State.Env)) { 865 createOptionalValue(*Loc, State.Env.getBoolLiteralValue(false), 866 State.Env); 867 } 868 }) 869 870 // optional::swap 871 .CaseOfCFGStmt<CXXMemberCallExpr>( 872 isOptionalMemberCallWithNameMatcher(hasName("swap")), 873 transferSwapCall) 874 875 // std::swap 876 .CaseOfCFGStmt<CallExpr>(isStdSwapCall(), transferStdSwapCall) 877 878 // std::forward 879 .CaseOfCFGStmt<CallExpr>(isStdForwardCall(), transferStdForwardCall) 880 881 // opt.value_or("").empty() 882 .CaseOfCFGStmt<Expr>(isValueOrStringEmptyCall(), 883 transferValueOrStringEmptyCall) 884 885 // opt.value_or(X) != X 886 .CaseOfCFGStmt<Expr>(isValueOrNotEqX(), transferValueOrNotEqX) 887 888 // Comparisons (==, !=): 889 .CaseOfCFGStmt<CXXOperatorCallExpr>( 890 isComparisonOperatorCall(hasAnyOptionalType(), hasAnyOptionalType()), 891 transferOptionalAndOptionalCmp) 892 .CaseOfCFGStmt<CXXOperatorCallExpr>( 893 isComparisonOperatorCall(hasOptionalType(), 894 unless(hasAnyOptionalType())), 895 [](const clang::CXXOperatorCallExpr *Cmp, 896 const MatchFinder::MatchResult &, LatticeTransferState &State) { 897 transferOptionalAndValueCmp(Cmp, Cmp->getArg(0), State.Env); 898 }) 899 .CaseOfCFGStmt<CXXOperatorCallExpr>( 900 isComparisonOperatorCall(unless(hasAnyOptionalType()), 901 hasOptionalType()), 902 [](const clang::CXXOperatorCallExpr *Cmp, 903 const MatchFinder::MatchResult &, LatticeTransferState &State) { 904 transferOptionalAndValueCmp(Cmp, Cmp->getArg(1), State.Env); 905 }) 906 907 // returns optional 908 .CaseOfCFGStmt<CallExpr>(isCallReturningOptional(), 909 transferCallReturningOptional) 910 911 .Build(); 912 } 913 914 std::vector<SourceLocation> diagnoseUnwrapCall(const Expr *ObjectExpr, 915 const Environment &Env) { 916 if (auto *OptionalVal = getValueBehindPossiblePointer(*ObjectExpr, Env)) { 917 auto *Prop = OptionalVal->getProperty("has_value"); 918 if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) { 919 if (Env.flowConditionImplies(HasValueVal->formula())) 920 return {}; 921 } 922 } 923 924 // Record that this unwrap is *not* provably safe. 925 // FIXME: include either the name of the optional (if applicable) or a source 926 // range of the access for easier interpretation of the result. 927 return {ObjectExpr->getBeginLoc()}; 928 } 929 930 auto buildDiagnoseMatchSwitch( 931 const UncheckedOptionalAccessModelOptions &Options) { 932 // FIXME: Evaluate the efficiency of matchers. If using matchers results in a 933 // lot of duplicated work (e.g. string comparisons), consider providing APIs 934 // that avoid it through memoization. 935 auto IgnorableOptional = ignorableOptional(Options); 936 return CFGMatchSwitchBuilder<const Environment, std::vector<SourceLocation>>() 937 // optional::value 938 .CaseOfCFGStmt<CXXMemberCallExpr>( 939 valueCall(IgnorableOptional), 940 [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &, 941 const Environment &Env) { 942 return diagnoseUnwrapCall(E->getImplicitObjectArgument(), Env); 943 }) 944 945 // optional::operator*, optional::operator-> 946 .CaseOfCFGStmt<CallExpr>(valueOperatorCall(IgnorableOptional), 947 [](const CallExpr *E, 948 const MatchFinder::MatchResult &, 949 const Environment &Env) { 950 return diagnoseUnwrapCall(E->getArg(0), Env); 951 }) 952 .Build(); 953 } 954 955 } // namespace 956 957 ast_matchers::DeclarationMatcher 958 UncheckedOptionalAccessModel::optionalClassDecl() { 959 return optionalClass(); 960 } 961 962 UncheckedOptionalAccessModel::UncheckedOptionalAccessModel(ASTContext &Ctx) 963 : DataflowAnalysis<UncheckedOptionalAccessModel, NoopLattice>(Ctx), 964 TransferMatchSwitch(buildTransferMatchSwitch()) {} 965 966 void UncheckedOptionalAccessModel::transfer(const CFGElement &Elt, 967 NoopLattice &L, Environment &Env) { 968 LatticeTransferState State(L, Env); 969 TransferMatchSwitch(Elt, getASTContext(), State); 970 } 971 972 ComparisonResult UncheckedOptionalAccessModel::compare( 973 QualType Type, const Value &Val1, const Environment &Env1, 974 const Value &Val2, const Environment &Env2) { 975 if (!isOptionalType(Type)) 976 return ComparisonResult::Unknown; 977 bool MustNonEmpty1 = isNonEmptyOptional(Val1, Env1); 978 bool MustNonEmpty2 = isNonEmptyOptional(Val2, Env2); 979 if (MustNonEmpty1 && MustNonEmpty2) 980 return ComparisonResult::Same; 981 // If exactly one is true, then they're different, no reason to check whether 982 // they're definitely empty. 983 if (MustNonEmpty1 || MustNonEmpty2) 984 return ComparisonResult::Different; 985 // Check if they're both definitely empty. 986 return (isEmptyOptional(Val1, Env1) && isEmptyOptional(Val2, Env2)) 987 ? ComparisonResult::Same 988 : ComparisonResult::Different; 989 } 990 991 bool UncheckedOptionalAccessModel::merge(QualType Type, const Value &Val1, 992 const Environment &Env1, 993 const Value &Val2, 994 const Environment &Env2, 995 Value &MergedVal, 996 Environment &MergedEnv) { 997 if (!isOptionalType(Type)) 998 return true; 999 // FIXME: uses same approach as join for `BoolValues`. Requires non-const 1000 // values, though, so will require updating the interface. 1001 auto &HasValueVal = MergedEnv.makeAtomicBoolValue(); 1002 bool MustNonEmpty1 = isNonEmptyOptional(Val1, Env1); 1003 bool MustNonEmpty2 = isNonEmptyOptional(Val2, Env2); 1004 if (MustNonEmpty1 && MustNonEmpty2) 1005 MergedEnv.addToFlowCondition(HasValueVal.formula()); 1006 else if ( 1007 // Only make the costly calls to `isEmptyOptional` if we got "unknown" 1008 // (false) for both calls to `isNonEmptyOptional`. 1009 !MustNonEmpty1 && !MustNonEmpty2 && isEmptyOptional(Val1, Env1) && 1010 isEmptyOptional(Val2, Env2)) 1011 MergedEnv.addToFlowCondition( 1012 MergedEnv.arena().makeNot(HasValueVal.formula())); 1013 setHasValue(MergedVal, HasValueVal); 1014 return true; 1015 } 1016 1017 Value *UncheckedOptionalAccessModel::widen(QualType Type, Value &Prev, 1018 const Environment &PrevEnv, 1019 Value &Current, 1020 Environment &CurrentEnv) { 1021 switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { 1022 case ComparisonResult::Same: 1023 return &Prev; 1024 case ComparisonResult::Different: 1025 if (auto *PrevHasVal = 1026 cast_or_null<BoolValue>(Prev.getProperty("has_value"))) { 1027 if (isa<TopBoolValue>(PrevHasVal)) 1028 return &Prev; 1029 } 1030 if (auto *CurrentHasVal = 1031 cast_or_null<BoolValue>(Current.getProperty("has_value"))) { 1032 if (isa<TopBoolValue>(CurrentHasVal)) 1033 return &Current; 1034 } 1035 return &createOptionalValue(cast<StructValue>(Current).getAggregateLoc(), 1036 CurrentEnv.makeTopBoolValue(), CurrentEnv); 1037 case ComparisonResult::Unknown: 1038 return nullptr; 1039 } 1040 llvm_unreachable("all cases covered in switch"); 1041 } 1042 1043 UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser( 1044 UncheckedOptionalAccessModelOptions Options) 1045 : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {} 1046 1047 } // namespace dataflow 1048 } // namespace clang 1049