1 //===- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ----------===// 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 meta-engine for path-sensitive dataflow analysis that 10 // is built on CoreEngine, but provides the boilerplate to execute transfer 11 // functions and build the ExplodedGraph at the expression level. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 16 #include "PrettyStackTraceLocationContext.h" 17 #include "clang/AST/ASTContext.h" 18 #include "clang/AST/Decl.h" 19 #include "clang/AST/DeclBase.h" 20 #include "clang/AST/DeclCXX.h" 21 #include "clang/AST/DeclObjC.h" 22 #include "clang/AST/Expr.h" 23 #include "clang/AST/ExprCXX.h" 24 #include "clang/AST/ExprObjC.h" 25 #include "clang/AST/ParentMap.h" 26 #include "clang/AST/PrettyPrinter.h" 27 #include "clang/AST/Stmt.h" 28 #include "clang/AST/StmtCXX.h" 29 #include "clang/AST/StmtObjC.h" 30 #include "clang/AST/Type.h" 31 #include "clang/Analysis/AnalysisDeclContext.h" 32 #include "clang/Analysis/CFG.h" 33 #include "clang/Analysis/ConstructionContext.h" 34 #include "clang/Analysis/ProgramPoint.h" 35 #include "clang/Basic/IdentifierTable.h" 36 #include "clang/Basic/JsonSupport.h" 37 #include "clang/Basic/LLVM.h" 38 #include "clang/Basic/LangOptions.h" 39 #include "clang/Basic/PrettyStackTrace.h" 40 #include "clang/Basic/SourceLocation.h" 41 #include "clang/Basic/SourceManager.h" 42 #include "clang/Basic/Specifiers.h" 43 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" 44 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 45 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 46 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 47 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 48 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 49 #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" 50 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 51 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 52 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" 53 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h" 54 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 55 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 56 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 57 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 58 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 59 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 60 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 61 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 62 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 63 #include "llvm/ADT/APSInt.h" 64 #include "llvm/ADT/DenseMap.h" 65 #include "llvm/ADT/ImmutableMap.h" 66 #include "llvm/ADT/ImmutableSet.h" 67 #include "llvm/ADT/Optional.h" 68 #include "llvm/ADT/SmallVector.h" 69 #include "llvm/ADT/Statistic.h" 70 #include "llvm/Support/Casting.h" 71 #include "llvm/Support/Compiler.h" 72 #include "llvm/Support/DOTGraphTraits.h" 73 #include "llvm/Support/ErrorHandling.h" 74 #include "llvm/Support/GraphWriter.h" 75 #include "llvm/Support/SaveAndRestore.h" 76 #include "llvm/Support/raw_ostream.h" 77 #include <cassert> 78 #include <cstdint> 79 #include <memory> 80 #include <string> 81 #include <tuple> 82 #include <utility> 83 #include <vector> 84 85 using namespace clang; 86 using namespace ento; 87 88 #define DEBUG_TYPE "ExprEngine" 89 90 STATISTIC(NumRemoveDeadBindings, 91 "The # of times RemoveDeadBindings is called"); 92 STATISTIC(NumMaxBlockCountReached, 93 "The # of aborted paths due to reaching the maximum block count in " 94 "a top level function"); 95 STATISTIC(NumMaxBlockCountReachedInInlined, 96 "The # of aborted paths due to reaching the maximum block count in " 97 "an inlined function"); 98 STATISTIC(NumTimesRetriedWithoutInlining, 99 "The # of times we re-evaluated a call without inlining"); 100 101 //===----------------------------------------------------------------------===// 102 // Internal program state traits. 103 //===----------------------------------------------------------------------===// 104 105 namespace { 106 107 // When modeling a C++ constructor, for a variety of reasons we need to track 108 // the location of the object for the duration of its ConstructionContext. 109 // ObjectsUnderConstruction maps statements within the construction context 110 // to the object's location, so that on every such statement the location 111 // could have been retrieved. 112 113 /// ConstructedObjectKey is used for being able to find the path-sensitive 114 /// memory region of a freshly constructed object while modeling the AST node 115 /// that syntactically represents the object that is being constructed. 116 /// Semantics of such nodes may sometimes require access to the region that's 117 /// not otherwise present in the program state, or to the very fact that 118 /// the construction context was present and contained references to these 119 /// AST nodes. 120 class ConstructedObjectKey { 121 using ConstructedObjectKeyImpl = 122 std::pair<ConstructionContextItem, const LocationContext *>; 123 const ConstructedObjectKeyImpl Impl; 124 125 public: 126 explicit ConstructedObjectKey(const ConstructionContextItem &Item, 127 const LocationContext *LC) 128 : Impl(Item, LC) {} 129 130 const ConstructionContextItem &getItem() const { return Impl.first; } 131 const LocationContext *getLocationContext() const { return Impl.second; } 132 133 ASTContext &getASTContext() const { 134 return getLocationContext()->getDecl()->getASTContext(); 135 } 136 137 void printJson(llvm::raw_ostream &Out, PrinterHelper *Helper, 138 PrintingPolicy &PP) const { 139 const Stmt *S = getItem().getStmtOrNull(); 140 const CXXCtorInitializer *I = nullptr; 141 if (!S) 142 I = getItem().getCXXCtorInitializer(); 143 144 if (S) 145 Out << "\"stmt_id\": " << S->getID(getASTContext()); 146 else 147 Out << "\"init_id\": " << I->getID(getASTContext()); 148 149 // Kind 150 Out << ", \"kind\": \"" << getItem().getKindAsString() 151 << "\", \"argument_index\": "; 152 153 if (getItem().getKind() == ConstructionContextItem::ArgumentKind) 154 Out << getItem().getIndex(); 155 else 156 Out << "null"; 157 158 // Pretty-print 159 Out << ", \"pretty\": "; 160 161 if (S) { 162 S->printJson(Out, Helper, PP, /*AddQuotes=*/true); 163 } else { 164 Out << '\"' << I->getAnyMember()->getDeclName() << '\"'; 165 } 166 } 167 168 void Profile(llvm::FoldingSetNodeID &ID) const { 169 ID.Add(Impl.first); 170 ID.AddPointer(Impl.second); 171 } 172 173 bool operator==(const ConstructedObjectKey &RHS) const { 174 return Impl == RHS.Impl; 175 } 176 177 bool operator<(const ConstructedObjectKey &RHS) const { 178 return Impl < RHS.Impl; 179 } 180 }; 181 } // namespace 182 183 typedef llvm::ImmutableMap<ConstructedObjectKey, SVal> 184 ObjectsUnderConstructionMap; 185 REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction, 186 ObjectsUnderConstructionMap) 187 188 // This trait is responsible for storing the index of the element that is to be 189 // constructed in the next iteration. As a result a CXXConstructExpr is only 190 // stored if it is array type. Also the index is the index of the continous 191 // memory region, which is important for multi-dimensional arrays. E.g:: int 192 // arr[2][2]; assume arr[1][1] will be the next element under construction, so 193 // the index is 3. 194 typedef llvm::ImmutableMap< 195 std::pair<const CXXConstructExpr *, const LocationContext *>, unsigned> 196 IndexOfElementToConstructMap; 197 REGISTER_TRAIT_WITH_PROGRAMSTATE(IndexOfElementToConstruct, 198 IndexOfElementToConstructMap) 199 //===----------------------------------------------------------------------===// 200 // Engine construction and deletion. 201 //===----------------------------------------------------------------------===// 202 203 static const char* TagProviderName = "ExprEngine"; 204 205 ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU, 206 AnalysisManager &mgr, SetOfConstDecls *VisitedCalleesIn, 207 FunctionSummariesTy *FS, InliningModes HowToInlineIn) 208 : CTU(CTU), IsCTUEnabled(mgr.getAnalyzerOptions().IsNaiveCTUEnabled), 209 AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), 210 Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()), 211 StateMgr(getContext(), mgr.getStoreManagerCreator(), 212 mgr.getConstraintManagerCreator(), G.getAllocator(), this), 213 SymMgr(StateMgr.getSymbolManager()), MRMgr(StateMgr.getRegionManager()), 214 svalBuilder(StateMgr.getSValBuilder()), ObjCNoRet(mgr.getASTContext()), 215 BR(mgr, *this), VisitedCallees(VisitedCalleesIn), 216 HowToInline(HowToInlineIn) { 217 unsigned TrimInterval = mgr.options.GraphTrimInterval; 218 if (TrimInterval != 0) { 219 // Enable eager node reclamation when constructing the ExplodedGraph. 220 G.enableNodeReclamation(TrimInterval); 221 } 222 } 223 224 //===----------------------------------------------------------------------===// 225 // Utility methods. 226 //===----------------------------------------------------------------------===// 227 228 ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { 229 ProgramStateRef state = StateMgr.getInitialState(InitLoc); 230 const Decl *D = InitLoc->getDecl(); 231 232 // Preconditions. 233 // FIXME: It would be nice if we had a more general mechanism to add 234 // such preconditions. Some day. 235 do { 236 if (const auto *FD = dyn_cast<FunctionDecl>(D)) { 237 // Precondition: the first argument of 'main' is an integer guaranteed 238 // to be > 0. 239 const IdentifierInfo *II = FD->getIdentifier(); 240 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) 241 break; 242 243 const ParmVarDecl *PD = FD->getParamDecl(0); 244 QualType T = PD->getType(); 245 const auto *BT = dyn_cast<BuiltinType>(T); 246 if (!BT || !BT->isInteger()) 247 break; 248 249 const MemRegion *R = state->getRegion(PD, InitLoc); 250 if (!R) 251 break; 252 253 SVal V = state->getSVal(loc::MemRegionVal(R)); 254 SVal Constraint_untested = evalBinOp(state, BO_GT, V, 255 svalBuilder.makeZeroVal(T), 256 svalBuilder.getConditionType()); 257 258 Optional<DefinedOrUnknownSVal> Constraint = 259 Constraint_untested.getAs<DefinedOrUnknownSVal>(); 260 261 if (!Constraint) 262 break; 263 264 if (ProgramStateRef newState = state->assume(*Constraint, true)) 265 state = newState; 266 } 267 break; 268 } 269 while (false); 270 271 if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) { 272 // Precondition: 'self' is always non-null upon entry to an Objective-C 273 // method. 274 const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 275 const MemRegion *R = state->getRegion(SelfD, InitLoc); 276 SVal V = state->getSVal(loc::MemRegionVal(R)); 277 278 if (Optional<Loc> LV = V.getAs<Loc>()) { 279 // Assume that the pointer value in 'self' is non-null. 280 state = state->assume(*LV, true); 281 assert(state && "'self' cannot be null"); 282 } 283 } 284 285 if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) { 286 if (!MD->isStatic()) { 287 // Precondition: 'this' is always non-null upon entry to the 288 // top-level function. This is our starting assumption for 289 // analyzing an "open" program. 290 const StackFrameContext *SFC = InitLoc->getStackFrame(); 291 if (SFC->getParent() == nullptr) { 292 loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC); 293 SVal V = state->getSVal(L); 294 if (Optional<Loc> LV = V.getAs<Loc>()) { 295 state = state->assume(*LV, true); 296 assert(state && "'this' cannot be null"); 297 } 298 } 299 } 300 } 301 302 return state; 303 } 304 305 ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded( 306 ProgramStateRef State, const LocationContext *LC, 307 const Expr *InitWithAdjustments, const Expr *Result, 308 const SubRegion **OutRegionWithAdjustments) { 309 // FIXME: This function is a hack that works around the quirky AST 310 // we're often having with respect to C++ temporaries. If only we modelled 311 // the actual execution order of statements properly in the CFG, 312 // all the hassle with adjustments would not be necessary, 313 // and perhaps the whole function would be removed. 314 SVal InitValWithAdjustments = State->getSVal(InitWithAdjustments, LC); 315 if (!Result) { 316 // If we don't have an explicit result expression, we're in "if needed" 317 // mode. Only create a region if the current value is a NonLoc. 318 if (!isa<NonLoc>(InitValWithAdjustments)) { 319 if (OutRegionWithAdjustments) 320 *OutRegionWithAdjustments = nullptr; 321 return State; 322 } 323 Result = InitWithAdjustments; 324 } else { 325 // We need to create a region no matter what. Make sure we don't try to 326 // stuff a Loc into a non-pointer temporary region. 327 assert(!isa<Loc>(InitValWithAdjustments) || 328 Loc::isLocType(Result->getType()) || 329 Result->getType()->isMemberPointerType()); 330 } 331 332 ProgramStateManager &StateMgr = State->getStateManager(); 333 MemRegionManager &MRMgr = StateMgr.getRegionManager(); 334 StoreManager &StoreMgr = StateMgr.getStoreManager(); 335 336 // MaterializeTemporaryExpr may appear out of place, after a few field and 337 // base-class accesses have been made to the object, even though semantically 338 // it is the whole object that gets materialized and lifetime-extended. 339 // 340 // For example: 341 // 342 // `-MaterializeTemporaryExpr 343 // `-MemberExpr 344 // `-CXXTemporaryObjectExpr 345 // 346 // instead of the more natural 347 // 348 // `-MemberExpr 349 // `-MaterializeTemporaryExpr 350 // `-CXXTemporaryObjectExpr 351 // 352 // Use the usual methods for obtaining the expression of the base object, 353 // and record the adjustments that we need to make to obtain the sub-object 354 // that the whole expression 'Ex' refers to. This trick is usual, 355 // in the sense that CodeGen takes a similar route. 356 357 SmallVector<const Expr *, 2> CommaLHSs; 358 SmallVector<SubobjectAdjustment, 2> Adjustments; 359 360 const Expr *Init = InitWithAdjustments->skipRValueSubobjectAdjustments( 361 CommaLHSs, Adjustments); 362 363 // Take the region for Init, i.e. for the whole object. If we do not remember 364 // the region in which the object originally was constructed, come up with 365 // a new temporary region out of thin air and copy the contents of the object 366 // (which are currently present in the Environment, because Init is an rvalue) 367 // into that region. This is not correct, but it is better than nothing. 368 const TypedValueRegion *TR = nullptr; 369 if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) { 370 if (Optional<SVal> V = getObjectUnderConstruction(State, MT, LC)) { 371 State = finishObjectConstruction(State, MT, LC); 372 State = State->BindExpr(Result, LC, *V); 373 return State; 374 } else { 375 StorageDuration SD = MT->getStorageDuration(); 376 // If this object is bound to a reference with static storage duration, we 377 // put it in a different region to prevent "address leakage" warnings. 378 if (SD == SD_Static || SD == SD_Thread) { 379 TR = MRMgr.getCXXStaticTempObjectRegion(Init); 380 } else { 381 TR = MRMgr.getCXXTempObjectRegion(Init, LC); 382 } 383 } 384 } else { 385 TR = MRMgr.getCXXTempObjectRegion(Init, LC); 386 } 387 388 SVal Reg = loc::MemRegionVal(TR); 389 SVal BaseReg = Reg; 390 391 // Make the necessary adjustments to obtain the sub-object. 392 for (const SubobjectAdjustment &Adj : llvm::reverse(Adjustments)) { 393 switch (Adj.Kind) { 394 case SubobjectAdjustment::DerivedToBaseAdjustment: 395 Reg = StoreMgr.evalDerivedToBase(Reg, Adj.DerivedToBase.BasePath); 396 break; 397 case SubobjectAdjustment::FieldAdjustment: 398 Reg = StoreMgr.getLValueField(Adj.Field, Reg); 399 break; 400 case SubobjectAdjustment::MemberPointerAdjustment: 401 // FIXME: Unimplemented. 402 State = State->invalidateRegions(Reg, InitWithAdjustments, 403 currBldrCtx->blockCount(), LC, true, 404 nullptr, nullptr, nullptr); 405 return State; 406 } 407 } 408 409 // What remains is to copy the value of the object to the new region. 410 // FIXME: In other words, what we should always do is copy value of the 411 // Init expression (which corresponds to the bigger object) to the whole 412 // temporary region TR. However, this value is often no longer present 413 // in the Environment. If it has disappeared, we instead invalidate TR. 414 // Still, what we can do is assign the value of expression Ex (which 415 // corresponds to the sub-object) to the TR's sub-region Reg. At least, 416 // values inside Reg would be correct. 417 SVal InitVal = State->getSVal(Init, LC); 418 if (InitVal.isUnknown()) { 419 InitVal = getSValBuilder().conjureSymbolVal(Result, LC, Init->getType(), 420 currBldrCtx->blockCount()); 421 State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false); 422 423 // Then we'd need to take the value that certainly exists and bind it 424 // over. 425 if (InitValWithAdjustments.isUnknown()) { 426 // Try to recover some path sensitivity in case we couldn't 427 // compute the value. 428 InitValWithAdjustments = getSValBuilder().conjureSymbolVal( 429 Result, LC, InitWithAdjustments->getType(), 430 currBldrCtx->blockCount()); 431 } 432 State = 433 State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false); 434 } else { 435 State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false); 436 } 437 438 // The result expression would now point to the correct sub-region of the 439 // newly created temporary region. Do this last in order to getSVal of Init 440 // correctly in case (Result == Init). 441 if (Result->isGLValue()) { 442 State = State->BindExpr(Result, LC, Reg); 443 } else { 444 State = State->BindExpr(Result, LC, InitValWithAdjustments); 445 } 446 447 // Notify checkers once for two bindLoc()s. 448 State = processRegionChange(State, TR, LC); 449 450 if (OutRegionWithAdjustments) 451 *OutRegionWithAdjustments = cast<SubRegion>(Reg.getAsRegion()); 452 return State; 453 } 454 455 ProgramStateRef ExprEngine::setIndexOfElementToConstruct( 456 ProgramStateRef State, const CXXConstructExpr *E, 457 const LocationContext *LCtx, unsigned Idx) { 458 auto Key = std::make_pair(E, LCtx->getStackFrame()); 459 460 assert(!State->contains<IndexOfElementToConstruct>(Key) || Idx > 0); 461 462 return State->set<IndexOfElementToConstruct>(Key, Idx); 463 } 464 465 Optional<unsigned> 466 ExprEngine::getIndexOfElementToConstruct(ProgramStateRef State, 467 const CXXConstructExpr *E, 468 const LocationContext *LCtx) { 469 470 return Optional<unsigned>::create( 471 State->get<IndexOfElementToConstruct>({E, LCtx->getStackFrame()})); 472 } 473 474 ProgramStateRef 475 ExprEngine::removeIndexOfElementToConstruct(ProgramStateRef State, 476 const CXXConstructExpr *E, 477 const LocationContext *LCtx) { 478 auto Key = std::make_pair(E, LCtx->getStackFrame()); 479 480 assert(E && State->contains<IndexOfElementToConstruct>(Key)); 481 return State->remove<IndexOfElementToConstruct>(Key); 482 } 483 484 ProgramStateRef 485 ExprEngine::addObjectUnderConstruction(ProgramStateRef State, 486 const ConstructionContextItem &Item, 487 const LocationContext *LC, SVal V) { 488 ConstructedObjectKey Key(Item, LC->getStackFrame()); 489 490 const CXXConstructExpr *E = nullptr; 491 492 if (auto DS = dyn_cast_or_null<DeclStmt>(Item.getStmtOrNull())) { 493 if (auto VD = dyn_cast_or_null<VarDecl>(DS->getSingleDecl())) 494 E = dyn_cast<CXXConstructExpr>(VD->getInit()); 495 } 496 497 if (!E && !Item.getStmtOrNull()) { 498 auto CtorInit = Item.getCXXCtorInitializer(); 499 E = dyn_cast<CXXConstructExpr>(CtorInit->getInit()); 500 } 501 502 // FIXME: Currently the state might already contain the marker due to 503 // incorrect handling of temporaries bound to default parameters. 504 // The state will already contain the marker if we construct elements 505 // in an array, as we visit the same statement multiple times before 506 // the array declaration. The marker is removed when we exit the 507 // constructor call. 508 assert((!State->get<ObjectsUnderConstruction>(Key) || 509 Key.getItem().getKind() == 510 ConstructionContextItem::TemporaryDestructorKind || 511 State->contains<IndexOfElementToConstruct>({E, LC})) && 512 "The object is already marked as `UnderConstruction`, when it's not " 513 "supposed to!"); 514 return State->set<ObjectsUnderConstruction>(Key, V); 515 } 516 517 Optional<SVal> 518 ExprEngine::getObjectUnderConstruction(ProgramStateRef State, 519 const ConstructionContextItem &Item, 520 const LocationContext *LC) { 521 ConstructedObjectKey Key(Item, LC->getStackFrame()); 522 return Optional<SVal>::create(State->get<ObjectsUnderConstruction>(Key)); 523 } 524 525 ProgramStateRef 526 ExprEngine::finishObjectConstruction(ProgramStateRef State, 527 const ConstructionContextItem &Item, 528 const LocationContext *LC) { 529 ConstructedObjectKey Key(Item, LC->getStackFrame()); 530 assert(State->contains<ObjectsUnderConstruction>(Key)); 531 return State->remove<ObjectsUnderConstruction>(Key); 532 } 533 534 ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State, 535 const CXXBindTemporaryExpr *BTE, 536 const LocationContext *LC) { 537 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC); 538 // FIXME: Currently the state might already contain the marker due to 539 // incorrect handling of temporaries bound to default parameters. 540 return State->set<ObjectsUnderConstruction>(Key, UnknownVal()); 541 } 542 543 ProgramStateRef 544 ExprEngine::cleanupElidedDestructor(ProgramStateRef State, 545 const CXXBindTemporaryExpr *BTE, 546 const LocationContext *LC) { 547 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC); 548 assert(State->contains<ObjectsUnderConstruction>(Key)); 549 return State->remove<ObjectsUnderConstruction>(Key); 550 } 551 552 bool ExprEngine::isDestructorElided(ProgramStateRef State, 553 const CXXBindTemporaryExpr *BTE, 554 const LocationContext *LC) { 555 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC); 556 return State->contains<ObjectsUnderConstruction>(Key); 557 } 558 559 bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State, 560 const LocationContext *FromLC, 561 const LocationContext *ToLC) { 562 const LocationContext *LC = FromLC; 563 while (LC != ToLC) { 564 assert(LC && "ToLC must be a parent of FromLC!"); 565 for (auto I : State->get<ObjectsUnderConstruction>()) 566 if (I.first.getLocationContext() == LC) 567 return false; 568 569 LC = LC->getParent(); 570 } 571 return true; 572 } 573 574 575 //===----------------------------------------------------------------------===// 576 // Top-level transfer function logic (Dispatcher). 577 //===----------------------------------------------------------------------===// 578 579 /// evalAssume - Called by ConstraintManager. Used to call checker-specific 580 /// logic for handling assumptions on symbolic values. 581 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 582 SVal cond, bool assumption) { 583 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 584 } 585 586 ProgramStateRef 587 ExprEngine::processRegionChanges(ProgramStateRef state, 588 const InvalidatedSymbols *invalidated, 589 ArrayRef<const MemRegion *> Explicits, 590 ArrayRef<const MemRegion *> Regions, 591 const LocationContext *LCtx, 592 const CallEvent *Call) { 593 return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 594 Explicits, Regions, 595 LCtx, Call); 596 } 597 598 static void 599 printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State, 600 const char *NL, const LocationContext *LCtx, 601 unsigned int Space = 0, bool IsDot = false) { 602 PrintingPolicy PP = 603 LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy(); 604 605 ++Space; 606 bool HasItem = false; 607 608 // Store the last key. 609 const ConstructedObjectKey *LastKey = nullptr; 610 for (const auto &I : State->get<ObjectsUnderConstruction>()) { 611 const ConstructedObjectKey &Key = I.first; 612 if (Key.getLocationContext() != LCtx) 613 continue; 614 615 if (!HasItem) { 616 Out << "[" << NL; 617 HasItem = true; 618 } 619 620 LastKey = &Key; 621 } 622 623 for (const auto &I : State->get<ObjectsUnderConstruction>()) { 624 const ConstructedObjectKey &Key = I.first; 625 SVal Value = I.second; 626 if (Key.getLocationContext() != LCtx) 627 continue; 628 629 Indent(Out, Space, IsDot) << "{ "; 630 Key.printJson(Out, nullptr, PP); 631 Out << ", \"value\": \"" << Value << "\" }"; 632 633 if (&Key != LastKey) 634 Out << ','; 635 Out << NL; 636 } 637 638 if (HasItem) 639 Indent(Out, --Space, IsDot) << ']'; // End of "location_context". 640 else { 641 Out << "null "; 642 } 643 } 644 645 static void printIndicesOfElementsToConstructJson( 646 raw_ostream &Out, ProgramStateRef State, const char *NL, 647 const LocationContext *LCtx, const ASTContext &Context, 648 unsigned int Space = 0, bool IsDot = false) { 649 using KeyT = std::pair<const Expr *, const LocationContext *>; 650 651 PrintingPolicy PP = 652 LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy(); 653 654 ++Space; 655 bool HasItem = false; 656 657 // Store the last key. 658 KeyT LastKey; 659 for (const auto &I : State->get<IndexOfElementToConstruct>()) { 660 const KeyT &Key = I.first; 661 if (Key.second != LCtx) 662 continue; 663 664 if (!HasItem) { 665 Out << "[" << NL; 666 HasItem = true; 667 } 668 669 LastKey = Key; 670 } 671 672 for (const auto &I : State->get<IndexOfElementToConstruct>()) { 673 const KeyT &Key = I.first; 674 unsigned Value = I.second; 675 if (Key.second != LCtx) 676 continue; 677 678 Indent(Out, Space, IsDot) << "{ "; 679 680 // Expr 681 const Expr *E = Key.first; 682 Out << "\"stmt_id\": " << E->getID(Context); 683 684 // Kind - hack to display the current index 685 Out << ", \"kind\": \"Cur: " << Value - 1 << "\""; 686 687 // Pretty-print 688 Out << ", \"pretty\": "; 689 Out << "\"" << E->getStmtClassName() << " " 690 << E->getSourceRange().printToString(Context.getSourceManager()) << " '" 691 << QualType::getAsString(E->getType().split(), PP); 692 Out << "'\""; 693 694 Out << ", \"value\": \"Next: " << Value << "\" }"; 695 696 if (Key != LastKey) 697 Out << ','; 698 Out << NL; 699 } 700 701 if (HasItem) 702 Indent(Out, --Space, IsDot) << ']'; // End of "location_context". 703 else { 704 Out << "null "; 705 } 706 } 707 708 void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State, 709 const LocationContext *LCtx, const char *NL, 710 unsigned int Space, bool IsDot) const { 711 Indent(Out, Space, IsDot) << "\"constructing_objects\": "; 712 713 if (LCtx && !State->get<ObjectsUnderConstruction>().isEmpty()) { 714 ++Space; 715 Out << '[' << NL; 716 LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) { 717 printObjectsUnderConstructionJson(Out, State, NL, LC, Space, IsDot); 718 }); 719 720 --Space; 721 Indent(Out, Space, IsDot) << "]," << NL; // End of "constructing_objects". 722 } else { 723 Out << "null," << NL; 724 } 725 726 Indent(Out, Space, IsDot) << "\"index_of_element\": "; 727 if (LCtx && !State->get<IndexOfElementToConstruct>().isEmpty()) { 728 ++Space; 729 730 auto &Context = getContext(); 731 Out << '[' << NL; 732 LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) { 733 printIndicesOfElementsToConstructJson(Out, State, NL, LC, Context, Space, 734 IsDot); 735 }); 736 737 --Space; 738 Indent(Out, Space, IsDot) << "]," << NL; // End of "index_of_element". 739 } else { 740 Out << "null," << NL; 741 } 742 743 getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space, 744 IsDot); 745 } 746 747 void ExprEngine::processEndWorklist() { 748 // This prints the name of the top-level function if we crash. 749 PrettyStackTraceLocationContext CrashInfo(getRootLocationContext()); 750 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 751 } 752 753 void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, 754 unsigned StmtIdx, NodeBuilderContext *Ctx) { 755 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 756 currStmtIdx = StmtIdx; 757 currBldrCtx = Ctx; 758 759 switch (E.getKind()) { 760 case CFGElement::Statement: 761 case CFGElement::Constructor: 762 case CFGElement::CXXRecordTypedCall: 763 ProcessStmt(E.castAs<CFGStmt>().getStmt(), Pred); 764 return; 765 case CFGElement::Initializer: 766 ProcessInitializer(E.castAs<CFGInitializer>(), Pred); 767 return; 768 case CFGElement::NewAllocator: 769 ProcessNewAllocator(E.castAs<CFGNewAllocator>().getAllocatorExpr(), 770 Pred); 771 return; 772 case CFGElement::AutomaticObjectDtor: 773 case CFGElement::DeleteDtor: 774 case CFGElement::BaseDtor: 775 case CFGElement::MemberDtor: 776 case CFGElement::TemporaryDtor: 777 ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred); 778 return; 779 case CFGElement::LoopExit: 780 ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred); 781 return; 782 case CFGElement::LifetimeEnds: 783 case CFGElement::ScopeBegin: 784 case CFGElement::ScopeEnd: 785 return; 786 } 787 } 788 789 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, 790 const Stmt *S, 791 const ExplodedNode *Pred, 792 const LocationContext *LC) { 793 // Are we never purging state values? 794 if (AMgr.options.AnalysisPurgeOpt == PurgeNone) 795 return false; 796 797 // Is this the beginning of a basic block? 798 if (Pred->getLocation().getAs<BlockEntrance>()) 799 return true; 800 801 // Is this on a non-expression? 802 if (!isa<Expr>(S)) 803 return true; 804 805 // Run before processing a call. 806 if (CallEvent::isCallStmt(S)) 807 return true; 808 809 // Is this an expression that is consumed by another expression? If so, 810 // postpone cleaning out the state. 811 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap(); 812 return !PM.isConsumedExpr(cast<Expr>(S)); 813 } 814 815 void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, 816 const Stmt *ReferenceStmt, 817 const LocationContext *LC, 818 const Stmt *DiagnosticStmt, 819 ProgramPoint::Kind K) { 820 assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind || 821 ReferenceStmt == nullptr || isa<ReturnStmt>(ReferenceStmt)) 822 && "PostStmt is not generally supported by the SymbolReaper yet"); 823 assert(LC && "Must pass the current (or expiring) LocationContext"); 824 825 if (!DiagnosticStmt) { 826 DiagnosticStmt = ReferenceStmt; 827 assert(DiagnosticStmt && "Required for clearing a LocationContext"); 828 } 829 830 NumRemoveDeadBindings++; 831 ProgramStateRef CleanedState = Pred->getState(); 832 833 // LC is the location context being destroyed, but SymbolReaper wants a 834 // location context that is still live. (If this is the top-level stack 835 // frame, this will be null.) 836 if (!ReferenceStmt) { 837 assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind && 838 "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext"); 839 LC = LC->getParent(); 840 } 841 842 const StackFrameContext *SFC = LC ? LC->getStackFrame() : nullptr; 843 SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager()); 844 845 for (auto I : CleanedState->get<ObjectsUnderConstruction>()) { 846 if (SymbolRef Sym = I.second.getAsSymbol()) 847 SymReaper.markLive(Sym); 848 if (const MemRegion *MR = I.second.getAsRegion()) 849 SymReaper.markLive(MR); 850 } 851 852 getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper); 853 854 // Create a state in which dead bindings are removed from the environment 855 // and the store. TODO: The function should just return new env and store, 856 // not a new state. 857 CleanedState = StateMgr.removeDeadBindingsFromEnvironmentAndStore( 858 CleanedState, SFC, SymReaper); 859 860 // Process any special transfer function for dead symbols. 861 // A tag to track convenience transitions, which can be removed at cleanup. 862 static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node"); 863 // Call checkers with the non-cleaned state so that they could query the 864 // values of the soon to be dead symbols. 865 ExplodedNodeSet CheckedSet; 866 getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper, 867 DiagnosticStmt, *this, K); 868 869 // For each node in CheckedSet, generate CleanedNodes that have the 870 // environment, the store, and the constraints cleaned up but have the 871 // user-supplied states as the predecessors. 872 StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx); 873 for (const auto I : CheckedSet) { 874 ProgramStateRef CheckerState = I->getState(); 875 876 // The constraint manager has not been cleaned up yet, so clean up now. 877 CheckerState = 878 getConstraintManager().removeDeadBindings(CheckerState, SymReaper); 879 880 assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) && 881 "Checkers are not allowed to modify the Environment as a part of " 882 "checkDeadSymbols processing."); 883 assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) && 884 "Checkers are not allowed to modify the Store as a part of " 885 "checkDeadSymbols processing."); 886 887 // Create a state based on CleanedState with CheckerState GDM and 888 // generate a transition to that state. 889 ProgramStateRef CleanedCheckerSt = 890 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); 891 Bldr.generateNode(DiagnosticStmt, I, CleanedCheckerSt, &cleanupTag, K); 892 } 893 } 894 895 void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) { 896 // Reclaim any unnecessary nodes in the ExplodedGraph. 897 G.reclaimRecentlyAllocatedNodes(); 898 899 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 900 currStmt->getBeginLoc(), 901 "Error evaluating statement"); 902 903 // Remove dead bindings and symbols. 904 ExplodedNodeSet CleanedStates; 905 if (shouldRemoveDeadBindings(AMgr, currStmt, Pred, 906 Pred->getLocationContext())) { 907 removeDead(Pred, CleanedStates, currStmt, 908 Pred->getLocationContext()); 909 } else 910 CleanedStates.Add(Pred); 911 912 // Visit the statement. 913 ExplodedNodeSet Dst; 914 for (const auto I : CleanedStates) { 915 ExplodedNodeSet DstI; 916 // Visit the statement. 917 Visit(currStmt, I, DstI); 918 Dst.insert(DstI); 919 } 920 921 // Enqueue the new nodes onto the work list. 922 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 923 } 924 925 void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) { 926 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 927 S->getBeginLoc(), 928 "Error evaluating end of the loop"); 929 ExplodedNodeSet Dst; 930 Dst.Add(Pred); 931 NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 932 ProgramStateRef NewState = Pred->getState(); 933 934 if(AMgr.options.ShouldUnrollLoops) 935 NewState = processLoopEnd(S, NewState); 936 937 LoopExit PP(S, Pred->getLocationContext()); 938 Bldr.generateNode(PP, NewState, Pred); 939 // Enqueue the new nodes onto the work list. 940 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 941 } 942 943 void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit, 944 ExplodedNode *Pred) { 945 const CXXCtorInitializer *BMI = CFGInit.getInitializer(); 946 const Expr *Init = BMI->getInit()->IgnoreImplicit(); 947 const LocationContext *LC = Pred->getLocationContext(); 948 949 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 950 BMI->getSourceLocation(), 951 "Error evaluating initializer"); 952 953 // We don't clean up dead bindings here. 954 const auto *stackFrame = cast<StackFrameContext>(Pred->getLocationContext()); 955 const auto *decl = cast<CXXConstructorDecl>(stackFrame->getDecl()); 956 957 ProgramStateRef State = Pred->getState(); 958 SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame)); 959 960 ExplodedNodeSet Tmp; 961 SVal FieldLoc; 962 963 // Evaluate the initializer, if necessary 964 if (BMI->isAnyMemberInitializer()) { 965 // Constructors build the object directly in the field, 966 // but non-objects must be copied in from the initializer. 967 if (getObjectUnderConstruction(State, BMI, LC)) { 968 // The field was directly constructed, so there is no need to bind. 969 // But we still need to stop tracking the object under construction. 970 State = finishObjectConstruction(State, BMI, LC); 971 NodeBuilder Bldr(Pred, Tmp, *currBldrCtx); 972 PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr); 973 Bldr.generateNode(PS, State, Pred); 974 } else { 975 const ValueDecl *Field; 976 if (BMI->isIndirectMemberInitializer()) { 977 Field = BMI->getIndirectMember(); 978 FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal); 979 } else { 980 Field = BMI->getMember(); 981 FieldLoc = State->getLValue(BMI->getMember(), thisVal); 982 } 983 984 SVal InitVal; 985 if (Init->getType()->isArrayType()) { 986 // Handle arrays of trivial type. We can represent this with a 987 // primitive load/copy from the base array region. 988 const ArraySubscriptExpr *ASE; 989 while ((ASE = dyn_cast<ArraySubscriptExpr>(Init))) 990 Init = ASE->getBase()->IgnoreImplicit(); 991 992 SVal LValue = State->getSVal(Init, stackFrame); 993 if (!Field->getType()->isReferenceType()) 994 if (Optional<Loc> LValueLoc = LValue.getAs<Loc>()) 995 InitVal = State->getSVal(*LValueLoc); 996 997 // If we fail to get the value for some reason, use a symbolic value. 998 if (InitVal.isUnknownOrUndef()) { 999 SValBuilder &SVB = getSValBuilder(); 1000 InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame, 1001 Field->getType(), 1002 currBldrCtx->blockCount()); 1003 } 1004 } else { 1005 InitVal = State->getSVal(BMI->getInit(), stackFrame); 1006 } 1007 1008 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame); 1009 evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP); 1010 } 1011 } else { 1012 assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer()); 1013 Tmp.insert(Pred); 1014 // We already did all the work when visiting the CXXConstructExpr. 1015 } 1016 1017 // Construct PostInitializer nodes whether the state changed or not, 1018 // so that the diagnostics don't get confused. 1019 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame); 1020 ExplodedNodeSet Dst; 1021 NodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 1022 for (const auto I : Tmp) { 1023 ProgramStateRef State = I->getState(); 1024 Bldr.generateNode(PP, State, I); 1025 } 1026 1027 // Enqueue the new nodes onto the work list. 1028 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 1029 } 1030 1031 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 1032 ExplodedNode *Pred) { 1033 ExplodedNodeSet Dst; 1034 switch (D.getKind()) { 1035 case CFGElement::AutomaticObjectDtor: 1036 ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst); 1037 break; 1038 case CFGElement::BaseDtor: 1039 ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst); 1040 break; 1041 case CFGElement::MemberDtor: 1042 ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst); 1043 break; 1044 case CFGElement::TemporaryDtor: 1045 ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst); 1046 break; 1047 case CFGElement::DeleteDtor: 1048 ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst); 1049 break; 1050 default: 1051 llvm_unreachable("Unexpected dtor kind."); 1052 } 1053 1054 // Enqueue the new nodes onto the work list. 1055 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 1056 } 1057 1058 void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE, 1059 ExplodedNode *Pred) { 1060 ExplodedNodeSet Dst; 1061 AnalysisManager &AMgr = getAnalysisManager(); 1062 AnalyzerOptions &Opts = AMgr.options; 1063 // TODO: We're not evaluating allocators for all cases just yet as 1064 // we're not handling the return value correctly, which causes false 1065 // positives when the alpha.cplusplus.NewDeleteLeaks check is on. 1066 if (Opts.MayInlineCXXAllocator) 1067 VisitCXXNewAllocatorCall(NE, Pred, Dst); 1068 else { 1069 NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 1070 const LocationContext *LCtx = Pred->getLocationContext(); 1071 PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx); 1072 Bldr.generateNode(PP, Pred->getState(), Pred); 1073 } 1074 Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); 1075 } 1076 1077 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, 1078 ExplodedNode *Pred, 1079 ExplodedNodeSet &Dst) { 1080 const VarDecl *varDecl = Dtor.getVarDecl(); 1081 QualType varType = varDecl->getType(); 1082 1083 ProgramStateRef state = Pred->getState(); 1084 SVal dest = state->getLValue(varDecl, Pred->getLocationContext()); 1085 const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion(); 1086 1087 if (varType->isReferenceType()) { 1088 const MemRegion *ValueRegion = state->getSVal(Region).getAsRegion(); 1089 if (!ValueRegion) { 1090 // FIXME: This should not happen. The language guarantees a presence 1091 // of a valid initializer here, so the reference shall not be undefined. 1092 // It seems that we're calling destructors over variables that 1093 // were not initialized yet. 1094 return; 1095 } 1096 Region = ValueRegion->getBaseRegion(); 1097 varType = cast<TypedValueRegion>(Region)->getValueType(); 1098 } 1099 1100 // FIXME: We need to run the same destructor on every element of the array. 1101 // This workaround will just run the first destructor (which will still 1102 // invalidate the entire array). 1103 EvalCallOptions CallOpts; 1104 Region = makeElementRegion(state, loc::MemRegionVal(Region), varType, 1105 CallOpts.IsArrayCtorOrDtor) 1106 .getAsRegion(); 1107 1108 VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(), 1109 /*IsBase=*/false, Pred, Dst, CallOpts); 1110 } 1111 1112 void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor, 1113 ExplodedNode *Pred, 1114 ExplodedNodeSet &Dst) { 1115 ProgramStateRef State = Pred->getState(); 1116 const LocationContext *LCtx = Pred->getLocationContext(); 1117 const CXXDeleteExpr *DE = Dtor.getDeleteExpr(); 1118 const Stmt *Arg = DE->getArgument(); 1119 QualType DTy = DE->getDestroyedType(); 1120 SVal ArgVal = State->getSVal(Arg, LCtx); 1121 1122 // If the argument to delete is known to be a null value, 1123 // don't run destructor. 1124 if (State->isNull(ArgVal).isConstrainedTrue()) { 1125 QualType BTy = getContext().getBaseElementType(DTy); 1126 const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl(); 1127 const CXXDestructorDecl *Dtor = RD->getDestructor(); 1128 1129 PostImplicitCall PP(Dtor, DE->getBeginLoc(), LCtx); 1130 NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 1131 Bldr.generateNode(PP, Pred->getState(), Pred); 1132 return; 1133 } 1134 1135 EvalCallOptions CallOpts; 1136 const MemRegion *ArgR = ArgVal.getAsRegion(); 1137 if (DE->isArrayForm()) { 1138 // FIXME: We need to run the same destructor on every element of the array. 1139 // This workaround will just run the first destructor (which will still 1140 // invalidate the entire array). 1141 CallOpts.IsArrayCtorOrDtor = true; 1142 // Yes, it may even be a multi-dimensional array. 1143 while (const auto *AT = getContext().getAsArrayType(DTy)) 1144 DTy = AT->getElementType(); 1145 if (ArgR) 1146 ArgR = getStoreManager().GetElementZeroRegion(cast<SubRegion>(ArgR), DTy); 1147 } 1148 1149 VisitCXXDestructor(DTy, ArgR, DE, /*IsBase=*/false, Pred, Dst, CallOpts); 1150 } 1151 1152 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 1153 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 1154 const LocationContext *LCtx = Pred->getLocationContext(); 1155 1156 const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 1157 Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor, 1158 LCtx->getStackFrame()); 1159 SVal ThisVal = Pred->getState()->getSVal(ThisPtr); 1160 1161 // Create the base object region. 1162 const CXXBaseSpecifier *Base = D.getBaseSpecifier(); 1163 QualType BaseTy = Base->getType(); 1164 SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy, 1165 Base->isVirtual()); 1166 1167 EvalCallOptions CallOpts; 1168 VisitCXXDestructor(BaseTy, BaseVal.getAsRegion(), CurDtor->getBody(), 1169 /*IsBase=*/true, Pred, Dst, CallOpts); 1170 } 1171 1172 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 1173 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 1174 const FieldDecl *Member = D.getFieldDecl(); 1175 QualType T = Member->getType(); 1176 ProgramStateRef State = Pred->getState(); 1177 const LocationContext *LCtx = Pred->getLocationContext(); 1178 1179 const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl()); 1180 Loc ThisStorageLoc = 1181 getSValBuilder().getCXXThis(CurDtor, LCtx->getStackFrame()); 1182 Loc ThisLoc = State->getSVal(ThisStorageLoc).castAs<Loc>(); 1183 SVal FieldVal = State->getLValue(Member, ThisLoc); 1184 1185 // FIXME: We need to run the same destructor on every element of the array. 1186 // This workaround will just run the first destructor (which will still 1187 // invalidate the entire array). 1188 EvalCallOptions CallOpts; 1189 FieldVal = makeElementRegion(State, FieldVal, T, CallOpts.IsArrayCtorOrDtor); 1190 1191 VisitCXXDestructor(T, FieldVal.getAsRegion(), CurDtor->getBody(), 1192 /*IsBase=*/false, Pred, Dst, CallOpts); 1193 } 1194 1195 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 1196 ExplodedNode *Pred, 1197 ExplodedNodeSet &Dst) { 1198 const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr(); 1199 ProgramStateRef State = Pred->getState(); 1200 const LocationContext *LC = Pred->getLocationContext(); 1201 const MemRegion *MR = nullptr; 1202 1203 if (Optional<SVal> V = 1204 getObjectUnderConstruction(State, D.getBindTemporaryExpr(), 1205 Pred->getLocationContext())) { 1206 // FIXME: Currently we insert temporary destructors for default parameters, 1207 // but we don't insert the constructors, so the entry in 1208 // ObjectsUnderConstruction may be missing. 1209 State = finishObjectConstruction(State, D.getBindTemporaryExpr(), 1210 Pred->getLocationContext()); 1211 MR = V->getAsRegion(); 1212 } 1213 1214 // If copy elision has occurred, and the constructor corresponding to the 1215 // destructor was elided, we need to skip the destructor as well. 1216 if (isDestructorElided(State, BTE, LC)) { 1217 State = cleanupElidedDestructor(State, BTE, LC); 1218 NodeBuilder Bldr(Pred, Dst, *currBldrCtx); 1219 PostImplicitCall PP(D.getDestructorDecl(getContext()), 1220 D.getBindTemporaryExpr()->getBeginLoc(), 1221 Pred->getLocationContext()); 1222 Bldr.generateNode(PP, State, Pred); 1223 return; 1224 } 1225 1226 ExplodedNodeSet CleanDtorState; 1227 StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx); 1228 StmtBldr.generateNode(D.getBindTemporaryExpr(), Pred, State); 1229 1230 QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType(); 1231 // FIXME: Currently CleanDtorState can be empty here due to temporaries being 1232 // bound to default parameters. 1233 assert(CleanDtorState.size() <= 1); 1234 ExplodedNode *CleanPred = 1235 CleanDtorState.empty() ? Pred : *CleanDtorState.begin(); 1236 1237 EvalCallOptions CallOpts; 1238 CallOpts.IsTemporaryCtorOrDtor = true; 1239 if (!MR) { 1240 // If we have no MR, we still need to unwrap the array to avoid destroying 1241 // the whole array at once. Regardless, we'd eventually need to model array 1242 // destructors properly, element-by-element. 1243 while (const ArrayType *AT = getContext().getAsArrayType(T)) { 1244 T = AT->getElementType(); 1245 CallOpts.IsArrayCtorOrDtor = true; 1246 } 1247 } else { 1248 // We'd eventually need to makeElementRegion() trick here, 1249 // but for now we don't have the respective construction contexts, 1250 // so MR would always be null in this case. Do nothing for now. 1251 } 1252 VisitCXXDestructor(T, MR, D.getBindTemporaryExpr(), 1253 /*IsBase=*/false, CleanPred, Dst, CallOpts); 1254 } 1255 1256 void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, 1257 NodeBuilderContext &BldCtx, 1258 ExplodedNode *Pred, 1259 ExplodedNodeSet &Dst, 1260 const CFGBlock *DstT, 1261 const CFGBlock *DstF) { 1262 BranchNodeBuilder TempDtorBuilder(Pred, Dst, BldCtx, DstT, DstF); 1263 ProgramStateRef State = Pred->getState(); 1264 const LocationContext *LC = Pred->getLocationContext(); 1265 if (getObjectUnderConstruction(State, BTE, LC)) { 1266 TempDtorBuilder.markInfeasible(false); 1267 TempDtorBuilder.generateNode(State, true, Pred); 1268 } else { 1269 TempDtorBuilder.markInfeasible(true); 1270 TempDtorBuilder.generateNode(State, false, Pred); 1271 } 1272 } 1273 1274 void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE, 1275 ExplodedNodeSet &PreVisit, 1276 ExplodedNodeSet &Dst) { 1277 // This is a fallback solution in case we didn't have a construction 1278 // context when we were constructing the temporary. Otherwise the map should 1279 // have been populated there. 1280 if (!getAnalysisManager().options.ShouldIncludeTemporaryDtorsInCFG) { 1281 // In case we don't have temporary destructors in the CFG, do not mark 1282 // the initialization - we would otherwise never clean it up. 1283 Dst = PreVisit; 1284 return; 1285 } 1286 StmtNodeBuilder StmtBldr(PreVisit, Dst, *currBldrCtx); 1287 for (ExplodedNode *Node : PreVisit) { 1288 ProgramStateRef State = Node->getState(); 1289 const LocationContext *LC = Node->getLocationContext(); 1290 if (!getObjectUnderConstruction(State, BTE, LC)) { 1291 // FIXME: Currently the state might also already contain the marker due to 1292 // incorrect handling of temporaries bound to default parameters; for 1293 // those, we currently skip the CXXBindTemporaryExpr but rely on adding 1294 // temporary destructor nodes. 1295 State = addObjectUnderConstruction(State, BTE, LC, UnknownVal()); 1296 } 1297 StmtBldr.generateNode(BTE, Node, State); 1298 } 1299 } 1300 1301 ProgramStateRef ExprEngine::escapeValues(ProgramStateRef State, 1302 ArrayRef<SVal> Vs, 1303 PointerEscapeKind K, 1304 const CallEvent *Call) const { 1305 class CollectReachableSymbolsCallback final : public SymbolVisitor { 1306 InvalidatedSymbols &Symbols; 1307 1308 public: 1309 explicit CollectReachableSymbolsCallback(InvalidatedSymbols &Symbols) 1310 : Symbols(Symbols) {} 1311 1312 const InvalidatedSymbols &getSymbols() const { return Symbols; } 1313 1314 bool VisitSymbol(SymbolRef Sym) override { 1315 Symbols.insert(Sym); 1316 return true; 1317 } 1318 }; 1319 InvalidatedSymbols Symbols; 1320 CollectReachableSymbolsCallback CallBack(Symbols); 1321 for (SVal V : Vs) 1322 State->scanReachableSymbols(V, CallBack); 1323 1324 return getCheckerManager().runCheckersForPointerEscape( 1325 State, CallBack.getSymbols(), Call, K, nullptr); 1326 } 1327 1328 void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, 1329 ExplodedNodeSet &DstTop) { 1330 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 1331 S->getBeginLoc(), "Error evaluating statement"); 1332 ExplodedNodeSet Dst; 1333 StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx); 1334 1335 assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens()); 1336 1337 switch (S->getStmtClass()) { 1338 // C++, OpenMP and ARC stuff we don't support yet. 1339 case Stmt::CXXDependentScopeMemberExprClass: 1340 case Stmt::CXXTryStmtClass: 1341 case Stmt::CXXTypeidExprClass: 1342 case Stmt::CXXUuidofExprClass: 1343 case Stmt::CXXFoldExprClass: 1344 case Stmt::MSPropertyRefExprClass: 1345 case Stmt::MSPropertySubscriptExprClass: 1346 case Stmt::CXXUnresolvedConstructExprClass: 1347 case Stmt::DependentScopeDeclRefExprClass: 1348 case Stmt::ArrayTypeTraitExprClass: 1349 case Stmt::ExpressionTraitExprClass: 1350 case Stmt::UnresolvedLookupExprClass: 1351 case Stmt::UnresolvedMemberExprClass: 1352 case Stmt::TypoExprClass: 1353 case Stmt::RecoveryExprClass: 1354 case Stmt::CXXNoexceptExprClass: 1355 case Stmt::PackExpansionExprClass: 1356 case Stmt::SubstNonTypeTemplateParmPackExprClass: 1357 case Stmt::FunctionParmPackExprClass: 1358 case Stmt::CoroutineBodyStmtClass: 1359 case Stmt::CoawaitExprClass: 1360 case Stmt::DependentCoawaitExprClass: 1361 case Stmt::CoreturnStmtClass: 1362 case Stmt::CoyieldExprClass: 1363 case Stmt::SEHTryStmtClass: 1364 case Stmt::SEHExceptStmtClass: 1365 case Stmt::SEHLeaveStmtClass: 1366 case Stmt::SEHFinallyStmtClass: 1367 case Stmt::OMPCanonicalLoopClass: 1368 case Stmt::OMPParallelDirectiveClass: 1369 case Stmt::OMPSimdDirectiveClass: 1370 case Stmt::OMPForDirectiveClass: 1371 case Stmt::OMPForSimdDirectiveClass: 1372 case Stmt::OMPSectionsDirectiveClass: 1373 case Stmt::OMPSectionDirectiveClass: 1374 case Stmt::OMPSingleDirectiveClass: 1375 case Stmt::OMPMasterDirectiveClass: 1376 case Stmt::OMPCriticalDirectiveClass: 1377 case Stmt::OMPParallelForDirectiveClass: 1378 case Stmt::OMPParallelForSimdDirectiveClass: 1379 case Stmt::OMPParallelSectionsDirectiveClass: 1380 case Stmt::OMPParallelMasterDirectiveClass: 1381 case Stmt::OMPParallelMaskedDirectiveClass: 1382 case Stmt::OMPTaskDirectiveClass: 1383 case Stmt::OMPTaskyieldDirectiveClass: 1384 case Stmt::OMPBarrierDirectiveClass: 1385 case Stmt::OMPTaskwaitDirectiveClass: 1386 case Stmt::OMPTaskgroupDirectiveClass: 1387 case Stmt::OMPFlushDirectiveClass: 1388 case Stmt::OMPDepobjDirectiveClass: 1389 case Stmt::OMPScanDirectiveClass: 1390 case Stmt::OMPOrderedDirectiveClass: 1391 case Stmt::OMPAtomicDirectiveClass: 1392 case Stmt::OMPTargetDirectiveClass: 1393 case Stmt::OMPTargetDataDirectiveClass: 1394 case Stmt::OMPTargetEnterDataDirectiveClass: 1395 case Stmt::OMPTargetExitDataDirectiveClass: 1396 case Stmt::OMPTargetParallelDirectiveClass: 1397 case Stmt::OMPTargetParallelForDirectiveClass: 1398 case Stmt::OMPTargetUpdateDirectiveClass: 1399 case Stmt::OMPTeamsDirectiveClass: 1400 case Stmt::OMPCancellationPointDirectiveClass: 1401 case Stmt::OMPCancelDirectiveClass: 1402 case Stmt::OMPTaskLoopDirectiveClass: 1403 case Stmt::OMPTaskLoopSimdDirectiveClass: 1404 case Stmt::OMPMasterTaskLoopDirectiveClass: 1405 case Stmt::OMPMaskedTaskLoopDirectiveClass: 1406 case Stmt::OMPMasterTaskLoopSimdDirectiveClass: 1407 case Stmt::OMPMaskedTaskLoopSimdDirectiveClass: 1408 case Stmt::OMPParallelMasterTaskLoopDirectiveClass: 1409 case Stmt::OMPParallelMaskedTaskLoopDirectiveClass: 1410 case Stmt::OMPParallelMasterTaskLoopSimdDirectiveClass: 1411 case Stmt::OMPParallelMaskedTaskLoopSimdDirectiveClass: 1412 case Stmt::OMPDistributeDirectiveClass: 1413 case Stmt::OMPDistributeParallelForDirectiveClass: 1414 case Stmt::OMPDistributeParallelForSimdDirectiveClass: 1415 case Stmt::OMPDistributeSimdDirectiveClass: 1416 case Stmt::OMPTargetParallelForSimdDirectiveClass: 1417 case Stmt::OMPTargetSimdDirectiveClass: 1418 case Stmt::OMPTeamsDistributeDirectiveClass: 1419 case Stmt::OMPTeamsDistributeSimdDirectiveClass: 1420 case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass: 1421 case Stmt::OMPTeamsDistributeParallelForDirectiveClass: 1422 case Stmt::OMPTargetTeamsDirectiveClass: 1423 case Stmt::OMPTargetTeamsDistributeDirectiveClass: 1424 case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass: 1425 case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass: 1426 case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass: 1427 case Stmt::OMPTileDirectiveClass: 1428 case Stmt::OMPInteropDirectiveClass: 1429 case Stmt::OMPDispatchDirectiveClass: 1430 case Stmt::OMPMaskedDirectiveClass: 1431 case Stmt::OMPGenericLoopDirectiveClass: 1432 case Stmt::OMPTeamsGenericLoopDirectiveClass: 1433 case Stmt::OMPTargetTeamsGenericLoopDirectiveClass: 1434 case Stmt::OMPParallelGenericLoopDirectiveClass: 1435 case Stmt::OMPTargetParallelGenericLoopDirectiveClass: 1436 case Stmt::CapturedStmtClass: 1437 case Stmt::OMPUnrollDirectiveClass: 1438 case Stmt::OMPMetaDirectiveClass: { 1439 const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState()); 1440 Engine.addAbortedBlock(node, currBldrCtx->getBlock()); 1441 break; 1442 } 1443 1444 case Stmt::ParenExprClass: 1445 llvm_unreachable("ParenExprs already handled."); 1446 case Stmt::GenericSelectionExprClass: 1447 llvm_unreachable("GenericSelectionExprs already handled."); 1448 // Cases that should never be evaluated simply because they shouldn't 1449 // appear in the CFG. 1450 case Stmt::BreakStmtClass: 1451 case Stmt::CaseStmtClass: 1452 case Stmt::CompoundStmtClass: 1453 case Stmt::ContinueStmtClass: 1454 case Stmt::CXXForRangeStmtClass: 1455 case Stmt::DefaultStmtClass: 1456 case Stmt::DoStmtClass: 1457 case Stmt::ForStmtClass: 1458 case Stmt::GotoStmtClass: 1459 case Stmt::IfStmtClass: 1460 case Stmt::IndirectGotoStmtClass: 1461 case Stmt::LabelStmtClass: 1462 case Stmt::NoStmtClass: 1463 case Stmt::NullStmtClass: 1464 case Stmt::SwitchStmtClass: 1465 case Stmt::WhileStmtClass: 1466 case Expr::MSDependentExistsStmtClass: 1467 llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 1468 case Stmt::ImplicitValueInitExprClass: 1469 // These nodes are shared in the CFG and would case caching out. 1470 // Moreover, no additional evaluation required for them, the 1471 // analyzer can reconstruct these values from the AST. 1472 llvm_unreachable("Should be pruned from CFG"); 1473 1474 case Stmt::ObjCSubscriptRefExprClass: 1475 case Stmt::ObjCPropertyRefExprClass: 1476 llvm_unreachable("These are handled by PseudoObjectExpr"); 1477 1478 case Stmt::GNUNullExprClass: { 1479 // GNU __null is a pointer-width integer, not an actual pointer. 1480 ProgramStateRef state = Pred->getState(); 1481 state = state->BindExpr( 1482 S, Pred->getLocationContext(), 1483 svalBuilder.makeIntValWithWidth(getContext().VoidPtrTy, 0)); 1484 Bldr.generateNode(S, Pred, state); 1485 break; 1486 } 1487 1488 case Stmt::ObjCAtSynchronizedStmtClass: 1489 Bldr.takeNodes(Pred); 1490 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 1491 Bldr.addNodes(Dst); 1492 break; 1493 1494 case Expr::ConstantExprClass: 1495 case Stmt::ExprWithCleanupsClass: 1496 // Handled due to fully linearised CFG. 1497 break; 1498 1499 case Stmt::CXXBindTemporaryExprClass: { 1500 Bldr.takeNodes(Pred); 1501 ExplodedNodeSet PreVisit; 1502 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1503 ExplodedNodeSet Next; 1504 VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), PreVisit, Next); 1505 getCheckerManager().runCheckersForPostStmt(Dst, Next, S, *this); 1506 Bldr.addNodes(Dst); 1507 break; 1508 } 1509 1510 case Stmt::ArrayInitLoopExprClass: 1511 Bldr.takeNodes(Pred); 1512 VisitArrayInitLoopExpr(cast<ArrayInitLoopExpr>(S), Pred, Dst); 1513 Bldr.addNodes(Dst); 1514 break; 1515 // Cases not handled yet; but will handle some day. 1516 case Stmt::DesignatedInitExprClass: 1517 case Stmt::DesignatedInitUpdateExprClass: 1518 case Stmt::ArrayInitIndexExprClass: 1519 case Stmt::ExtVectorElementExprClass: 1520 case Stmt::ImaginaryLiteralClass: 1521 case Stmt::ObjCAtCatchStmtClass: 1522 case Stmt::ObjCAtFinallyStmtClass: 1523 case Stmt::ObjCAtTryStmtClass: 1524 case Stmt::ObjCAutoreleasePoolStmtClass: 1525 case Stmt::ObjCEncodeExprClass: 1526 case Stmt::ObjCIsaExprClass: 1527 case Stmt::ObjCProtocolExprClass: 1528 case Stmt::ObjCSelectorExprClass: 1529 case Stmt::ParenListExprClass: 1530 case Stmt::ShuffleVectorExprClass: 1531 case Stmt::ConvertVectorExprClass: 1532 case Stmt::VAArgExprClass: 1533 case Stmt::CUDAKernelCallExprClass: 1534 case Stmt::OpaqueValueExprClass: 1535 case Stmt::AsTypeExprClass: 1536 case Stmt::ConceptSpecializationExprClass: 1537 case Stmt::CXXRewrittenBinaryOperatorClass: 1538 case Stmt::RequiresExprClass: 1539 // Fall through. 1540 1541 // Cases we intentionally don't evaluate, since they don't need 1542 // to be explicitly evaluated. 1543 case Stmt::PredefinedExprClass: 1544 case Stmt::AddrLabelExprClass: 1545 case Stmt::AttributedStmtClass: 1546 case Stmt::IntegerLiteralClass: 1547 case Stmt::FixedPointLiteralClass: 1548 case Stmt::CharacterLiteralClass: 1549 case Stmt::CXXScalarValueInitExprClass: 1550 case Stmt::CXXBoolLiteralExprClass: 1551 case Stmt::ObjCBoolLiteralExprClass: 1552 case Stmt::ObjCAvailabilityCheckExprClass: 1553 case Stmt::FloatingLiteralClass: 1554 case Stmt::NoInitExprClass: 1555 case Stmt::SizeOfPackExprClass: 1556 case Stmt::StringLiteralClass: 1557 case Stmt::SourceLocExprClass: 1558 case Stmt::ObjCStringLiteralClass: 1559 case Stmt::CXXPseudoDestructorExprClass: 1560 case Stmt::SubstNonTypeTemplateParmExprClass: 1561 case Stmt::CXXNullPtrLiteralExprClass: 1562 case Stmt::OMPArraySectionExprClass: 1563 case Stmt::OMPArrayShapingExprClass: 1564 case Stmt::OMPIteratorExprClass: 1565 case Stmt::SYCLUniqueStableNameExprClass: 1566 case Stmt::TypeTraitExprClass: { 1567 Bldr.takeNodes(Pred); 1568 ExplodedNodeSet preVisit; 1569 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 1570 getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this); 1571 Bldr.addNodes(Dst); 1572 break; 1573 } 1574 1575 case Stmt::CXXDefaultArgExprClass: 1576 case Stmt::CXXDefaultInitExprClass: { 1577 Bldr.takeNodes(Pred); 1578 ExplodedNodeSet PreVisit; 1579 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1580 1581 ExplodedNodeSet Tmp; 1582 StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx); 1583 1584 const Expr *ArgE; 1585 if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S)) 1586 ArgE = DefE->getExpr(); 1587 else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S)) 1588 ArgE = DefE->getExpr(); 1589 else 1590 llvm_unreachable("unknown constant wrapper kind"); 1591 1592 bool IsTemporary = false; 1593 if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) { 1594 ArgE = MTE->getSubExpr(); 1595 IsTemporary = true; 1596 } 1597 1598 Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE); 1599 if (!ConstantVal) 1600 ConstantVal = UnknownVal(); 1601 1602 const LocationContext *LCtx = Pred->getLocationContext(); 1603 for (const auto I : PreVisit) { 1604 ProgramStateRef State = I->getState(); 1605 State = State->BindExpr(S, LCtx, *ConstantVal); 1606 if (IsTemporary) 1607 State = createTemporaryRegionIfNeeded(State, LCtx, 1608 cast<Expr>(S), 1609 cast<Expr>(S)); 1610 Bldr2.generateNode(S, I, State); 1611 } 1612 1613 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 1614 Bldr.addNodes(Dst); 1615 break; 1616 } 1617 1618 // Cases we evaluate as opaque expressions, conjuring a symbol. 1619 case Stmt::CXXStdInitializerListExprClass: 1620 case Expr::ObjCArrayLiteralClass: 1621 case Expr::ObjCDictionaryLiteralClass: 1622 case Expr::ObjCBoxedExprClass: { 1623 Bldr.takeNodes(Pred); 1624 1625 ExplodedNodeSet preVisit; 1626 getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); 1627 1628 ExplodedNodeSet Tmp; 1629 StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx); 1630 1631 const auto *Ex = cast<Expr>(S); 1632 QualType resultType = Ex->getType(); 1633 1634 for (const auto N : preVisit) { 1635 const LocationContext *LCtx = N->getLocationContext(); 1636 SVal result = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx, 1637 resultType, 1638 currBldrCtx->blockCount()); 1639 ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result); 1640 1641 // Escape pointers passed into the list, unless it's an ObjC boxed 1642 // expression which is not a boxable C structure. 1643 if (!(isa<ObjCBoxedExpr>(Ex) && 1644 !cast<ObjCBoxedExpr>(Ex)->getSubExpr() 1645 ->getType()->isRecordType())) 1646 for (auto Child : Ex->children()) { 1647 assert(Child); 1648 SVal Val = State->getSVal(Child, LCtx); 1649 State = escapeValues(State, Val, PSK_EscapeOther); 1650 } 1651 1652 Bldr2.generateNode(S, N, State); 1653 } 1654 1655 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); 1656 Bldr.addNodes(Dst); 1657 break; 1658 } 1659 1660 case Stmt::ArraySubscriptExprClass: 1661 Bldr.takeNodes(Pred); 1662 VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 1663 Bldr.addNodes(Dst); 1664 break; 1665 1666 case Stmt::MatrixSubscriptExprClass: 1667 llvm_unreachable("Support for MatrixSubscriptExpr is not implemented."); 1668 break; 1669 1670 case Stmt::GCCAsmStmtClass: 1671 Bldr.takeNodes(Pred); 1672 VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst); 1673 Bldr.addNodes(Dst); 1674 break; 1675 1676 case Stmt::MSAsmStmtClass: 1677 Bldr.takeNodes(Pred); 1678 VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst); 1679 Bldr.addNodes(Dst); 1680 break; 1681 1682 case Stmt::BlockExprClass: 1683 Bldr.takeNodes(Pred); 1684 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 1685 Bldr.addNodes(Dst); 1686 break; 1687 1688 case Stmt::LambdaExprClass: 1689 if (AMgr.options.ShouldInlineLambdas) { 1690 Bldr.takeNodes(Pred); 1691 VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst); 1692 Bldr.addNodes(Dst); 1693 } else { 1694 const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState()); 1695 Engine.addAbortedBlock(node, currBldrCtx->getBlock()); 1696 } 1697 break; 1698 1699 case Stmt::BinaryOperatorClass: { 1700 const auto *B = cast<BinaryOperator>(S); 1701 if (B->isLogicalOp()) { 1702 Bldr.takeNodes(Pred); 1703 VisitLogicalExpr(B, Pred, Dst); 1704 Bldr.addNodes(Dst); 1705 break; 1706 } 1707 else if (B->getOpcode() == BO_Comma) { 1708 ProgramStateRef state = Pred->getState(); 1709 Bldr.generateNode(B, Pred, 1710 state->BindExpr(B, Pred->getLocationContext(), 1711 state->getSVal(B->getRHS(), 1712 Pred->getLocationContext()))); 1713 break; 1714 } 1715 1716 Bldr.takeNodes(Pred); 1717 1718 if (AMgr.options.ShouldEagerlyAssume && 1719 (B->isRelationalOp() || B->isEqualityOp())) { 1720 ExplodedNodeSet Tmp; 1721 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 1722 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S)); 1723 } 1724 else 1725 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 1726 1727 Bldr.addNodes(Dst); 1728 break; 1729 } 1730 1731 case Stmt::CXXOperatorCallExprClass: { 1732 const auto *OCE = cast<CXXOperatorCallExpr>(S); 1733 1734 // For instance method operators, make sure the 'this' argument has a 1735 // valid region. 1736 const Decl *Callee = OCE->getCalleeDecl(); 1737 if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) { 1738 if (MD->isInstance()) { 1739 ProgramStateRef State = Pred->getState(); 1740 const LocationContext *LCtx = Pred->getLocationContext(); 1741 ProgramStateRef NewState = 1742 createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0)); 1743 if (NewState != State) { 1744 Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr, 1745 ProgramPoint::PreStmtKind); 1746 // Did we cache out? 1747 if (!Pred) 1748 break; 1749 } 1750 } 1751 } 1752 // FALLTHROUGH 1753 LLVM_FALLTHROUGH; 1754 } 1755 1756 case Stmt::CallExprClass: 1757 case Stmt::CXXMemberCallExprClass: 1758 case Stmt::UserDefinedLiteralClass: 1759 Bldr.takeNodes(Pred); 1760 VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 1761 Bldr.addNodes(Dst); 1762 break; 1763 1764 case Stmt::CXXCatchStmtClass: 1765 Bldr.takeNodes(Pred); 1766 VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst); 1767 Bldr.addNodes(Dst); 1768 break; 1769 1770 case Stmt::CXXTemporaryObjectExprClass: 1771 case Stmt::CXXConstructExprClass: 1772 Bldr.takeNodes(Pred); 1773 VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst); 1774 Bldr.addNodes(Dst); 1775 break; 1776 1777 case Stmt::CXXInheritedCtorInitExprClass: 1778 Bldr.takeNodes(Pred); 1779 VisitCXXInheritedCtorInitExpr(cast<CXXInheritedCtorInitExpr>(S), Pred, 1780 Dst); 1781 Bldr.addNodes(Dst); 1782 break; 1783 1784 case Stmt::CXXNewExprClass: { 1785 Bldr.takeNodes(Pred); 1786 1787 ExplodedNodeSet PreVisit; 1788 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1789 1790 ExplodedNodeSet PostVisit; 1791 for (const auto i : PreVisit) 1792 VisitCXXNewExpr(cast<CXXNewExpr>(S), i, PostVisit); 1793 1794 getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this); 1795 Bldr.addNodes(Dst); 1796 break; 1797 } 1798 1799 case Stmt::CXXDeleteExprClass: { 1800 Bldr.takeNodes(Pred); 1801 ExplodedNodeSet PreVisit; 1802 const auto *CDE = cast<CXXDeleteExpr>(S); 1803 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1804 ExplodedNodeSet PostVisit; 1805 getCheckerManager().runCheckersForPostStmt(PostVisit, PreVisit, S, *this); 1806 1807 for (const auto i : PostVisit) 1808 VisitCXXDeleteExpr(CDE, i, Dst); 1809 1810 Bldr.addNodes(Dst); 1811 break; 1812 } 1813 // FIXME: ChooseExpr is really a constant. We need to fix 1814 // the CFG do not model them as explicit control-flow. 1815 1816 case Stmt::ChooseExprClass: { // __builtin_choose_expr 1817 Bldr.takeNodes(Pred); 1818 const auto *C = cast<ChooseExpr>(S); 1819 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 1820 Bldr.addNodes(Dst); 1821 break; 1822 } 1823 1824 case Stmt::CompoundAssignOperatorClass: 1825 Bldr.takeNodes(Pred); 1826 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 1827 Bldr.addNodes(Dst); 1828 break; 1829 1830 case Stmt::CompoundLiteralExprClass: 1831 Bldr.takeNodes(Pred); 1832 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 1833 Bldr.addNodes(Dst); 1834 break; 1835 1836 case Stmt::BinaryConditionalOperatorClass: 1837 case Stmt::ConditionalOperatorClass: { // '?' operator 1838 Bldr.takeNodes(Pred); 1839 const auto *C = cast<AbstractConditionalOperator>(S); 1840 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 1841 Bldr.addNodes(Dst); 1842 break; 1843 } 1844 1845 case Stmt::CXXThisExprClass: 1846 Bldr.takeNodes(Pred); 1847 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 1848 Bldr.addNodes(Dst); 1849 break; 1850 1851 case Stmt::DeclRefExprClass: { 1852 Bldr.takeNodes(Pred); 1853 const auto *DE = cast<DeclRefExpr>(S); 1854 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 1855 Bldr.addNodes(Dst); 1856 break; 1857 } 1858 1859 case Stmt::DeclStmtClass: 1860 Bldr.takeNodes(Pred); 1861 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 1862 Bldr.addNodes(Dst); 1863 break; 1864 1865 case Stmt::ImplicitCastExprClass: 1866 case Stmt::CStyleCastExprClass: 1867 case Stmt::CXXStaticCastExprClass: 1868 case Stmt::CXXDynamicCastExprClass: 1869 case Stmt::CXXReinterpretCastExprClass: 1870 case Stmt::CXXConstCastExprClass: 1871 case Stmt::CXXFunctionalCastExprClass: 1872 case Stmt::BuiltinBitCastExprClass: 1873 case Stmt::ObjCBridgedCastExprClass: 1874 case Stmt::CXXAddrspaceCastExprClass: { 1875 Bldr.takeNodes(Pred); 1876 const auto *C = cast<CastExpr>(S); 1877 ExplodedNodeSet dstExpr; 1878 VisitCast(C, C->getSubExpr(), Pred, dstExpr); 1879 1880 // Handle the postvisit checks. 1881 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this); 1882 Bldr.addNodes(Dst); 1883 break; 1884 } 1885 1886 case Expr::MaterializeTemporaryExprClass: { 1887 Bldr.takeNodes(Pred); 1888 const auto *MTE = cast<MaterializeTemporaryExpr>(S); 1889 ExplodedNodeSet dstPrevisit; 1890 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this); 1891 ExplodedNodeSet dstExpr; 1892 for (const auto i : dstPrevisit) 1893 CreateCXXTemporaryObject(MTE, i, dstExpr); 1894 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this); 1895 Bldr.addNodes(Dst); 1896 break; 1897 } 1898 1899 case Stmt::InitListExprClass: 1900 Bldr.takeNodes(Pred); 1901 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 1902 Bldr.addNodes(Dst); 1903 break; 1904 1905 case Stmt::MemberExprClass: 1906 Bldr.takeNodes(Pred); 1907 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 1908 Bldr.addNodes(Dst); 1909 break; 1910 1911 case Stmt::AtomicExprClass: 1912 Bldr.takeNodes(Pred); 1913 VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst); 1914 Bldr.addNodes(Dst); 1915 break; 1916 1917 case Stmt::ObjCIvarRefExprClass: 1918 Bldr.takeNodes(Pred); 1919 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 1920 Bldr.addNodes(Dst); 1921 break; 1922 1923 case Stmt::ObjCForCollectionStmtClass: 1924 Bldr.takeNodes(Pred); 1925 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 1926 Bldr.addNodes(Dst); 1927 break; 1928 1929 case Stmt::ObjCMessageExprClass: 1930 Bldr.takeNodes(Pred); 1931 VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst); 1932 Bldr.addNodes(Dst); 1933 break; 1934 1935 case Stmt::ObjCAtThrowStmtClass: 1936 case Stmt::CXXThrowExprClass: 1937 // FIXME: This is not complete. We basically treat @throw as 1938 // an abort. 1939 Bldr.generateSink(S, Pred, Pred->getState()); 1940 break; 1941 1942 case Stmt::ReturnStmtClass: 1943 Bldr.takeNodes(Pred); 1944 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 1945 Bldr.addNodes(Dst); 1946 break; 1947 1948 case Stmt::OffsetOfExprClass: { 1949 Bldr.takeNodes(Pred); 1950 ExplodedNodeSet PreVisit; 1951 getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); 1952 1953 ExplodedNodeSet PostVisit; 1954 for (const auto Node : PreVisit) 1955 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Node, PostVisit); 1956 1957 getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this); 1958 Bldr.addNodes(Dst); 1959 break; 1960 } 1961 1962 case Stmt::UnaryExprOrTypeTraitExprClass: 1963 Bldr.takeNodes(Pred); 1964 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 1965 Pred, Dst); 1966 Bldr.addNodes(Dst); 1967 break; 1968 1969 case Stmt::StmtExprClass: { 1970 const auto *SE = cast<StmtExpr>(S); 1971 1972 if (SE->getSubStmt()->body_empty()) { 1973 // Empty statement expression. 1974 assert(SE->getType() == getContext().VoidTy 1975 && "Empty statement expression must have void type."); 1976 break; 1977 } 1978 1979 if (const auto *LastExpr = 1980 dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 1981 ProgramStateRef state = Pred->getState(); 1982 Bldr.generateNode(SE, Pred, 1983 state->BindExpr(SE, Pred->getLocationContext(), 1984 state->getSVal(LastExpr, 1985 Pred->getLocationContext()))); 1986 } 1987 break; 1988 } 1989 1990 case Stmt::UnaryOperatorClass: { 1991 Bldr.takeNodes(Pred); 1992 const auto *U = cast<UnaryOperator>(S); 1993 if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) { 1994 ExplodedNodeSet Tmp; 1995 VisitUnaryOperator(U, Pred, Tmp); 1996 evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U); 1997 } 1998 else 1999 VisitUnaryOperator(U, Pred, Dst); 2000 Bldr.addNodes(Dst); 2001 break; 2002 } 2003 2004 case Stmt::PseudoObjectExprClass: { 2005 Bldr.takeNodes(Pred); 2006 ProgramStateRef state = Pred->getState(); 2007 const auto *PE = cast<PseudoObjectExpr>(S); 2008 if (const Expr *Result = PE->getResultExpr()) { 2009 SVal V = state->getSVal(Result, Pred->getLocationContext()); 2010 Bldr.generateNode(S, Pred, 2011 state->BindExpr(S, Pred->getLocationContext(), V)); 2012 } 2013 else 2014 Bldr.generateNode(S, Pred, 2015 state->BindExpr(S, Pred->getLocationContext(), 2016 UnknownVal())); 2017 2018 Bldr.addNodes(Dst); 2019 break; 2020 } 2021 2022 case Expr::ObjCIndirectCopyRestoreExprClass: { 2023 // ObjCIndirectCopyRestoreExpr implies passing a temporary for 2024 // correctness of lifetime management. Due to limited analysis 2025 // of ARC, this is implemented as direct arg passing. 2026 Bldr.takeNodes(Pred); 2027 ProgramStateRef state = Pred->getState(); 2028 const auto *OIE = cast<ObjCIndirectCopyRestoreExpr>(S); 2029 const Expr *E = OIE->getSubExpr(); 2030 SVal V = state->getSVal(E, Pred->getLocationContext()); 2031 Bldr.generateNode(S, Pred, 2032 state->BindExpr(S, Pred->getLocationContext(), V)); 2033 Bldr.addNodes(Dst); 2034 break; 2035 } 2036 } 2037 } 2038 2039 bool ExprEngine::replayWithoutInlining(ExplodedNode *N, 2040 const LocationContext *CalleeLC) { 2041 const StackFrameContext *CalleeSF = CalleeLC->getStackFrame(); 2042 const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame(); 2043 assert(CalleeSF && CallerSF); 2044 ExplodedNode *BeforeProcessingCall = nullptr; 2045 const Stmt *CE = CalleeSF->getCallSite(); 2046 2047 // Find the first node before we started processing the call expression. 2048 while (N) { 2049 ProgramPoint L = N->getLocation(); 2050 BeforeProcessingCall = N; 2051 N = N->pred_empty() ? nullptr : *(N->pred_begin()); 2052 2053 // Skip the nodes corresponding to the inlined code. 2054 if (L.getStackFrame() != CallerSF) 2055 continue; 2056 // We reached the caller. Find the node right before we started 2057 // processing the call. 2058 if (L.isPurgeKind()) 2059 continue; 2060 if (L.getAs<PreImplicitCall>()) 2061 continue; 2062 if (L.getAs<CallEnter>()) 2063 continue; 2064 if (Optional<StmtPoint> SP = L.getAs<StmtPoint>()) 2065 if (SP->getStmt() == CE) 2066 continue; 2067 break; 2068 } 2069 2070 if (!BeforeProcessingCall) 2071 return false; 2072 2073 // TODO: Clean up the unneeded nodes. 2074 2075 // Build an Epsilon node from which we will restart the analyzes. 2076 // Note that CE is permitted to be NULL! 2077 ProgramPoint NewNodeLoc = 2078 EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE); 2079 // Add the special flag to GDM to signal retrying with no inlining. 2080 // Note, changing the state ensures that we are not going to cache out. 2081 ProgramStateRef NewNodeState = BeforeProcessingCall->getState(); 2082 NewNodeState = 2083 NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE)); 2084 2085 // Make the new node a successor of BeforeProcessingCall. 2086 bool IsNew = false; 2087 ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew); 2088 // We cached out at this point. Caching out is common due to us backtracking 2089 // from the inlined function, which might spawn several paths. 2090 if (!IsNew) 2091 return true; 2092 2093 NewNode->addPredecessor(BeforeProcessingCall, G); 2094 2095 // Add the new node to the work list. 2096 Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(), 2097 CalleeSF->getIndex()); 2098 NumTimesRetriedWithoutInlining++; 2099 return true; 2100 } 2101 2102 /// Block entrance. (Update counters). 2103 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, 2104 NodeBuilderWithSinks &nodeBuilder, 2105 ExplodedNode *Pred) { 2106 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 2107 // If we reach a loop which has a known bound (and meets 2108 // other constraints) then consider completely unrolling it. 2109 if(AMgr.options.ShouldUnrollLoops) { 2110 unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath; 2111 const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt(); 2112 if (Term) { 2113 ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(), 2114 Pred, maxBlockVisitOnPath); 2115 if (NewState != Pred->getState()) { 2116 ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred); 2117 if (!UpdatedNode) 2118 return; 2119 Pred = UpdatedNode; 2120 } 2121 } 2122 // Is we are inside an unrolled loop then no need the check the counters. 2123 if(isUnrolledState(Pred->getState())) 2124 return; 2125 } 2126 2127 // If this block is terminated by a loop and it has already been visited the 2128 // maximum number of times, widen the loop. 2129 unsigned int BlockCount = nodeBuilder.getContext().blockCount(); 2130 if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 && 2131 AMgr.options.ShouldWidenLoops) { 2132 const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt(); 2133 if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt>(Term)) 2134 return; 2135 // Widen. 2136 const LocationContext *LCtx = Pred->getLocationContext(); 2137 ProgramStateRef WidenedState = 2138 getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term); 2139 nodeBuilder.generateNode(WidenedState, Pred); 2140 return; 2141 } 2142 2143 // FIXME: Refactor this into a checker. 2144 if (BlockCount >= AMgr.options.maxBlockVisitOnPath) { 2145 static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded"); 2146 const ExplodedNode *Sink = 2147 nodeBuilder.generateSink(Pred->getState(), Pred, &tag); 2148 2149 // Check if we stopped at the top level function or not. 2150 // Root node should have the location context of the top most function. 2151 const LocationContext *CalleeLC = Pred->getLocation().getLocationContext(); 2152 const LocationContext *CalleeSF = CalleeLC->getStackFrame(); 2153 const LocationContext *RootLC = 2154 (*G.roots_begin())->getLocation().getLocationContext(); 2155 if (RootLC->getStackFrame() != CalleeSF) { 2156 Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); 2157 2158 // Re-run the call evaluation without inlining it, by storing the 2159 // no-inlining policy in the state and enqueuing the new work item on 2160 // the list. Replay should almost never fail. Use the stats to catch it 2161 // if it does. 2162 if ((!AMgr.options.NoRetryExhausted && 2163 replayWithoutInlining(Pred, CalleeLC))) 2164 return; 2165 NumMaxBlockCountReachedInInlined++; 2166 } else 2167 NumMaxBlockCountReached++; 2168 2169 // Make sink nodes as exhausted(for stats) only if retry failed. 2170 Engine.blocksExhausted.push_back(std::make_pair(L, Sink)); 2171 } 2172 } 2173 2174 //===----------------------------------------------------------------------===// 2175 // Branch processing. 2176 //===----------------------------------------------------------------------===// 2177 2178 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used 2179 /// to try to recover some path-sensitivity for casts of symbolic 2180 /// integers that promote their values (which are currently not tracked well). 2181 /// This function returns the SVal bound to Condition->IgnoreCasts if all the 2182 // cast(s) did was sign-extend the original value. 2183 static SVal RecoverCastedSymbol(ProgramStateRef state, 2184 const Stmt *Condition, 2185 const LocationContext *LCtx, 2186 ASTContext &Ctx) { 2187 2188 const auto *Ex = dyn_cast<Expr>(Condition); 2189 if (!Ex) 2190 return UnknownVal(); 2191 2192 uint64_t bits = 0; 2193 bool bitsInit = false; 2194 2195 while (const auto *CE = dyn_cast<CastExpr>(Ex)) { 2196 QualType T = CE->getType(); 2197 2198 if (!T->isIntegralOrEnumerationType()) 2199 return UnknownVal(); 2200 2201 uint64_t newBits = Ctx.getTypeSize(T); 2202 if (!bitsInit || newBits < bits) { 2203 bitsInit = true; 2204 bits = newBits; 2205 } 2206 2207 Ex = CE->getSubExpr(); 2208 } 2209 2210 // We reached a non-cast. Is it a symbolic value? 2211 QualType T = Ex->getType(); 2212 2213 if (!bitsInit || !T->isIntegralOrEnumerationType() || 2214 Ctx.getTypeSize(T) > bits) 2215 return UnknownVal(); 2216 2217 return state->getSVal(Ex, LCtx); 2218 } 2219 2220 #ifndef NDEBUG 2221 static const Stmt *getRightmostLeaf(const Stmt *Condition) { 2222 while (Condition) { 2223 const auto *BO = dyn_cast<BinaryOperator>(Condition); 2224 if (!BO || !BO->isLogicalOp()) { 2225 return Condition; 2226 } 2227 Condition = BO->getRHS()->IgnoreParens(); 2228 } 2229 return nullptr; 2230 } 2231 #endif 2232 2233 // Returns the condition the branch at the end of 'B' depends on and whose value 2234 // has been evaluated within 'B'. 2235 // In most cases, the terminator condition of 'B' will be evaluated fully in 2236 // the last statement of 'B'; in those cases, the resolved condition is the 2237 // given 'Condition'. 2238 // If the condition of the branch is a logical binary operator tree, the CFG is 2239 // optimized: in that case, we know that the expression formed by all but the 2240 // rightmost leaf of the logical binary operator tree must be true, and thus 2241 // the branch condition is at this point equivalent to the truth value of that 2242 // rightmost leaf; the CFG block thus only evaluates this rightmost leaf 2243 // expression in its final statement. As the full condition in that case was 2244 // not evaluated, and is thus not in the SVal cache, we need to use that leaf 2245 // expression to evaluate the truth value of the condition in the current state 2246 // space. 2247 static const Stmt *ResolveCondition(const Stmt *Condition, 2248 const CFGBlock *B) { 2249 if (const auto *Ex = dyn_cast<Expr>(Condition)) 2250 Condition = Ex->IgnoreParens(); 2251 2252 const auto *BO = dyn_cast<BinaryOperator>(Condition); 2253 if (!BO || !BO->isLogicalOp()) 2254 return Condition; 2255 2256 assert(B->getTerminator().isStmtBranch() && 2257 "Other kinds of branches are handled separately!"); 2258 2259 // For logical operations, we still have the case where some branches 2260 // use the traditional "merge" approach and others sink the branch 2261 // directly into the basic blocks representing the logical operation. 2262 // We need to distinguish between those two cases here. 2263 2264 // The invariants are still shifting, but it is possible that the 2265 // last element in a CFGBlock is not a CFGStmt. Look for the last 2266 // CFGStmt as the value of the condition. 2267 CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend(); 2268 for (; I != E; ++I) { 2269 CFGElement Elem = *I; 2270 Optional<CFGStmt> CS = Elem.getAs<CFGStmt>(); 2271 if (!CS) 2272 continue; 2273 const Stmt *LastStmt = CS->getStmt(); 2274 assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition)); 2275 return LastStmt; 2276 } 2277 llvm_unreachable("could not resolve condition"); 2278 } 2279 2280 using ObjCForLctxPair = 2281 std::pair<const ObjCForCollectionStmt *, const LocationContext *>; 2282 2283 REGISTER_MAP_WITH_PROGRAMSTATE(ObjCForHasMoreIterations, ObjCForLctxPair, bool) 2284 2285 ProgramStateRef ExprEngine::setWhetherHasMoreIteration( 2286 ProgramStateRef State, const ObjCForCollectionStmt *O, 2287 const LocationContext *LC, bool HasMoreIteraton) { 2288 assert(!State->contains<ObjCForHasMoreIterations>({O, LC})); 2289 return State->set<ObjCForHasMoreIterations>({O, LC}, HasMoreIteraton); 2290 } 2291 2292 ProgramStateRef 2293 ExprEngine::removeIterationState(ProgramStateRef State, 2294 const ObjCForCollectionStmt *O, 2295 const LocationContext *LC) { 2296 assert(State->contains<ObjCForHasMoreIterations>({O, LC})); 2297 return State->remove<ObjCForHasMoreIterations>({O, LC}); 2298 } 2299 2300 bool ExprEngine::hasMoreIteration(ProgramStateRef State, 2301 const ObjCForCollectionStmt *O, 2302 const LocationContext *LC) { 2303 assert(State->contains<ObjCForHasMoreIterations>({O, LC})); 2304 return *State->get<ObjCForHasMoreIterations>({O, LC}); 2305 } 2306 2307 /// Split the state on whether there are any more iterations left for this loop. 2308 /// Returns a (HasMoreIteration, HasNoMoreIteration) pair, or None when the 2309 /// acquisition of the loop condition value failed. 2310 static Optional<std::pair<ProgramStateRef, ProgramStateRef>> 2311 assumeCondition(const Stmt *Condition, ExplodedNode *N) { 2312 ProgramStateRef State = N->getState(); 2313 if (const auto *ObjCFor = dyn_cast<ObjCForCollectionStmt>(Condition)) { 2314 bool HasMoreIteraton = 2315 ExprEngine::hasMoreIteration(State, ObjCFor, N->getLocationContext()); 2316 // Checkers have already ran on branch conditions, so the current 2317 // information as to whether the loop has more iteration becomes outdated 2318 // after this point. 2319 State = ExprEngine::removeIterationState(State, ObjCFor, 2320 N->getLocationContext()); 2321 if (HasMoreIteraton) 2322 return std::pair<ProgramStateRef, ProgramStateRef>{State, nullptr}; 2323 else 2324 return std::pair<ProgramStateRef, ProgramStateRef>{nullptr, State}; 2325 } 2326 SVal X = State->getSVal(Condition, N->getLocationContext()); 2327 2328 if (X.isUnknownOrUndef()) { 2329 // Give it a chance to recover from unknown. 2330 if (const auto *Ex = dyn_cast<Expr>(Condition)) { 2331 if (Ex->getType()->isIntegralOrEnumerationType()) { 2332 // Try to recover some path-sensitivity. Right now casts of symbolic 2333 // integers that promote their values are currently not tracked well. 2334 // If 'Condition' is such an expression, try and recover the 2335 // underlying value and use that instead. 2336 SVal recovered = 2337 RecoverCastedSymbol(State, Condition, N->getLocationContext(), 2338 N->getState()->getStateManager().getContext()); 2339 2340 if (!recovered.isUnknown()) { 2341 X = recovered; 2342 } 2343 } 2344 } 2345 } 2346 2347 // If the condition is still unknown, give up. 2348 if (X.isUnknownOrUndef()) 2349 return None; 2350 2351 DefinedSVal V = X.castAs<DefinedSVal>(); 2352 2353 ProgramStateRef StTrue, StFalse; 2354 return State->assume(V); 2355 } 2356 2357 void ExprEngine::processBranch(const Stmt *Condition, 2358 NodeBuilderContext& BldCtx, 2359 ExplodedNode *Pred, 2360 ExplodedNodeSet &Dst, 2361 const CFGBlock *DstT, 2362 const CFGBlock *DstF) { 2363 assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) && 2364 "CXXBindTemporaryExprs are handled by processBindTemporary."); 2365 const LocationContext *LCtx = Pred->getLocationContext(); 2366 PrettyStackTraceLocationContext StackCrashInfo(LCtx); 2367 currBldrCtx = &BldCtx; 2368 2369 // Check for NULL conditions; e.g. "for(;;)" 2370 if (!Condition) { 2371 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 2372 NullCondBldr.markInfeasible(false); 2373 NullCondBldr.generateNode(Pred->getState(), true, Pred); 2374 return; 2375 } 2376 2377 if (const auto *Ex = dyn_cast<Expr>(Condition)) 2378 Condition = Ex->IgnoreParens(); 2379 2380 Condition = ResolveCondition(Condition, BldCtx.getBlock()); 2381 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 2382 Condition->getBeginLoc(), 2383 "Error evaluating branch"); 2384 2385 ExplodedNodeSet CheckersOutSet; 2386 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 2387 Pred, *this); 2388 // We generated only sinks. 2389 if (CheckersOutSet.empty()) 2390 return; 2391 2392 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 2393 for (ExplodedNode *PredN : CheckersOutSet) { 2394 if (PredN->isSink()) 2395 continue; 2396 2397 ProgramStateRef PrevState = PredN->getState(); 2398 2399 ProgramStateRef StTrue, StFalse; 2400 if (const auto KnownCondValueAssumption = assumeCondition(Condition, PredN)) 2401 std::tie(StTrue, StFalse) = *KnownCondValueAssumption; 2402 else { 2403 assert(!isa<ObjCForCollectionStmt>(Condition)); 2404 builder.generateNode(PrevState, true, PredN); 2405 builder.generateNode(PrevState, false, PredN); 2406 continue; 2407 } 2408 if (StTrue && StFalse) 2409 assert(!isa<ObjCForCollectionStmt>(Condition)); 2410 2411 // Process the true branch. 2412 if (builder.isFeasible(true)) { 2413 if (StTrue) 2414 builder.generateNode(StTrue, true, PredN); 2415 else 2416 builder.markInfeasible(true); 2417 } 2418 2419 // Process the false branch. 2420 if (builder.isFeasible(false)) { 2421 if (StFalse) 2422 builder.generateNode(StFalse, false, PredN); 2423 else 2424 builder.markInfeasible(false); 2425 } 2426 } 2427 currBldrCtx = nullptr; 2428 } 2429 2430 /// The GDM component containing the set of global variables which have been 2431 /// previously initialized with explicit initializers. 2432 REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet, 2433 llvm::ImmutableSet<const VarDecl *>) 2434 2435 void ExprEngine::processStaticInitializer(const DeclStmt *DS, 2436 NodeBuilderContext &BuilderCtx, 2437 ExplodedNode *Pred, 2438 ExplodedNodeSet &Dst, 2439 const CFGBlock *DstT, 2440 const CFGBlock *DstF) { 2441 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 2442 currBldrCtx = &BuilderCtx; 2443 2444 const auto *VD = cast<VarDecl>(DS->getSingleDecl()); 2445 ProgramStateRef state = Pred->getState(); 2446 bool initHasRun = state->contains<InitializedGlobalsSet>(VD); 2447 BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF); 2448 2449 if (!initHasRun) { 2450 state = state->add<InitializedGlobalsSet>(VD); 2451 } 2452 2453 builder.generateNode(state, initHasRun, Pred); 2454 builder.markInfeasible(!initHasRun); 2455 2456 currBldrCtx = nullptr; 2457 } 2458 2459 /// processIndirectGoto - Called by CoreEngine. Used to generate successor 2460 /// nodes by processing the 'effects' of a computed goto jump. 2461 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 2462 ProgramStateRef state = builder.getState(); 2463 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); 2464 2465 // Three possibilities: 2466 // 2467 // (1) We know the computed label. 2468 // (2) The label is NULL (or some other constant), or Undefined. 2469 // (3) We have no clue about the label. Dispatch to all targets. 2470 // 2471 2472 using iterator = IndirectGotoNodeBuilder::iterator; 2473 2474 if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) { 2475 const LabelDecl *L = LV->getLabel(); 2476 2477 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 2478 if (I.getLabel() == L) { 2479 builder.generateNode(I, state); 2480 return; 2481 } 2482 } 2483 2484 llvm_unreachable("No block with label."); 2485 } 2486 2487 if (isa<UndefinedVal, loc::ConcreteInt>(V)) { 2488 // Dispatch to the first target and mark it as a sink. 2489 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 2490 // FIXME: add checker visit. 2491 // UndefBranches.insert(N); 2492 return; 2493 } 2494 2495 // This is really a catch-all. We don't support symbolics yet. 2496 // FIXME: Implement dispatch for symbolic pointers. 2497 2498 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) 2499 builder.generateNode(I, state); 2500 } 2501 2502 void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC, 2503 ExplodedNode *Pred, 2504 ExplodedNodeSet &Dst, 2505 const BlockEdge &L) { 2506 SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC); 2507 getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this); 2508 } 2509 2510 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 2511 /// nodes when the control reaches the end of a function. 2512 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC, 2513 ExplodedNode *Pred, 2514 const ReturnStmt *RS) { 2515 ProgramStateRef State = Pred->getState(); 2516 2517 if (!Pred->getStackFrame()->inTopFrame()) 2518 State = finishArgumentConstruction( 2519 State, *getStateManager().getCallEventManager().getCaller( 2520 Pred->getStackFrame(), Pred->getState())); 2521 2522 // FIXME: We currently cannot assert that temporaries are clear, because 2523 // lifetime extended temporaries are not always modelled correctly. In some 2524 // cases when we materialize the temporary, we do 2525 // createTemporaryRegionIfNeeded(), and the region changes, and also the 2526 // respective destructor becomes automatic from temporary. So for now clean up 2527 // the state manually before asserting. Ideally, this braced block of code 2528 // should go away. 2529 { 2530 const LocationContext *FromLC = Pred->getLocationContext(); 2531 const LocationContext *ToLC = FromLC->getStackFrame()->getParent(); 2532 const LocationContext *LC = FromLC; 2533 while (LC != ToLC) { 2534 assert(LC && "ToLC must be a parent of FromLC!"); 2535 for (auto I : State->get<ObjectsUnderConstruction>()) 2536 if (I.first.getLocationContext() == LC) { 2537 // The comment above only pardons us for not cleaning up a 2538 // temporary destructor. If any other statements are found here, 2539 // it must be a separate problem. 2540 assert(I.first.getItem().getKind() == 2541 ConstructionContextItem::TemporaryDestructorKind || 2542 I.first.getItem().getKind() == 2543 ConstructionContextItem::ElidedDestructorKind); 2544 State = State->remove<ObjectsUnderConstruction>(I.first); 2545 } 2546 LC = LC->getParent(); 2547 } 2548 } 2549 2550 // Perform the transition with cleanups. 2551 if (State != Pred->getState()) { 2552 ExplodedNodeSet PostCleanup; 2553 NodeBuilder Bldr(Pred, PostCleanup, BC); 2554 Pred = Bldr.generateNode(Pred->getLocation(), State, Pred); 2555 if (!Pred) { 2556 // The node with clean temporaries already exists. We might have reached 2557 // it on a path on which we initialize different temporaries. 2558 return; 2559 } 2560 } 2561 2562 assert(areAllObjectsFullyConstructed(Pred->getState(), 2563 Pred->getLocationContext(), 2564 Pred->getStackFrame()->getParent())); 2565 2566 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 2567 2568 ExplodedNodeSet Dst; 2569 if (Pred->getLocationContext()->inTopFrame()) { 2570 // Remove dead symbols. 2571 ExplodedNodeSet AfterRemovedDead; 2572 removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead); 2573 2574 // Notify checkers. 2575 for (const auto I : AfterRemovedDead) 2576 getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS); 2577 } else { 2578 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS); 2579 } 2580 2581 Engine.enqueueEndOfFunction(Dst, RS); 2582 } 2583 2584 /// ProcessSwitch - Called by CoreEngine. Used to generate successor 2585 /// nodes by processing the 'effects' of a switch statement. 2586 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 2587 using iterator = SwitchNodeBuilder::iterator; 2588 2589 ProgramStateRef state = builder.getState(); 2590 const Expr *CondE = builder.getCondition(); 2591 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); 2592 2593 if (CondV_untested.isUndef()) { 2594 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 2595 // FIXME: add checker 2596 //UndefBranches.insert(N); 2597 2598 return; 2599 } 2600 DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>(); 2601 2602 ProgramStateRef DefaultSt = state; 2603 2604 iterator I = builder.begin(), EI = builder.end(); 2605 bool defaultIsFeasible = I == EI; 2606 2607 for ( ; I != EI; ++I) { 2608 // Successor may be pruned out during CFG construction. 2609 if (!I.getBlock()) 2610 continue; 2611 2612 const CaseStmt *Case = I.getCase(); 2613 2614 // Evaluate the LHS of the case value. 2615 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 2616 assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType())); 2617 2618 // Get the RHS of the case, if it exists. 2619 llvm::APSInt V2; 2620 if (const Expr *E = Case->getRHS()) 2621 V2 = E->EvaluateKnownConstInt(getContext()); 2622 else 2623 V2 = V1; 2624 2625 ProgramStateRef StateCase; 2626 if (Optional<NonLoc> NL = CondV.getAs<NonLoc>()) 2627 std::tie(StateCase, DefaultSt) = 2628 DefaultSt->assumeInclusiveRange(*NL, V1, V2); 2629 else // UnknownVal 2630 StateCase = DefaultSt; 2631 2632 if (StateCase) 2633 builder.generateCaseStmtNode(I, StateCase); 2634 2635 // Now "assume" that the case doesn't match. Add this state 2636 // to the default state (if it is feasible). 2637 if (DefaultSt) 2638 defaultIsFeasible = true; 2639 else { 2640 defaultIsFeasible = false; 2641 break; 2642 } 2643 } 2644 2645 if (!defaultIsFeasible) 2646 return; 2647 2648 // If we have switch(enum value), the default branch is not 2649 // feasible if all of the enum constants not covered by 'case:' statements 2650 // are not feasible values for the switch condition. 2651 // 2652 // Note that this isn't as accurate as it could be. Even if there isn't 2653 // a case for a particular enum value as long as that enum value isn't 2654 // feasible then it shouldn't be considered for making 'default:' reachable. 2655 const SwitchStmt *SS = builder.getSwitch(); 2656 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 2657 if (CondExpr->getType()->getAs<EnumType>()) { 2658 if (SS->isAllEnumCasesCovered()) 2659 return; 2660 } 2661 2662 builder.generateDefaultCaseNode(DefaultSt); 2663 } 2664 2665 //===----------------------------------------------------------------------===// 2666 // Transfer functions: Loads and stores. 2667 //===----------------------------------------------------------------------===// 2668 2669 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 2670 ExplodedNode *Pred, 2671 ExplodedNodeSet &Dst) { 2672 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2673 2674 ProgramStateRef state = Pred->getState(); 2675 const LocationContext *LCtx = Pred->getLocationContext(); 2676 2677 if (const auto *VD = dyn_cast<VarDecl>(D)) { 2678 // C permits "extern void v", and if you cast the address to a valid type, 2679 // you can even do things with it. We simply pretend 2680 assert(Ex->isGLValue() || VD->getType()->isVoidType()); 2681 const LocationContext *LocCtxt = Pred->getLocationContext(); 2682 const Decl *D = LocCtxt->getDecl(); 2683 const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D); 2684 const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex); 2685 Optional<std::pair<SVal, QualType>> VInfo; 2686 2687 if (AMgr.options.ShouldInlineLambdas && DeclRefEx && 2688 DeclRefEx->refersToEnclosingVariableOrCapture() && MD && 2689 MD->getParent()->isLambda()) { 2690 // Lookup the field of the lambda. 2691 const CXXRecordDecl *CXXRec = MD->getParent(); 2692 llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields; 2693 FieldDecl *LambdaThisCaptureField; 2694 CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField); 2695 2696 // Sema follows a sequence of complex rules to determine whether the 2697 // variable should be captured. 2698 if (const FieldDecl *FD = LambdaCaptureFields[VD]) { 2699 Loc CXXThis = 2700 svalBuilder.getCXXThis(MD, LocCtxt->getStackFrame()); 2701 SVal CXXThisVal = state->getSVal(CXXThis); 2702 VInfo = std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType()); 2703 } 2704 } 2705 2706 if (!VInfo) 2707 VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType()); 2708 2709 SVal V = VInfo->first; 2710 bool IsReference = VInfo->second->isReferenceType(); 2711 2712 // For references, the 'lvalue' is the pointer address stored in the 2713 // reference region. 2714 if (IsReference) { 2715 if (const MemRegion *R = V.getAsRegion()) 2716 V = state->getSVal(R); 2717 else 2718 V = UnknownVal(); 2719 } 2720 2721 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2722 ProgramPoint::PostLValueKind); 2723 return; 2724 } 2725 if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) { 2726 assert(!Ex->isGLValue()); 2727 SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 2728 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 2729 return; 2730 } 2731 if (const auto *FD = dyn_cast<FunctionDecl>(D)) { 2732 SVal V = svalBuilder.getFunctionPointer(FD); 2733 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2734 ProgramPoint::PostLValueKind); 2735 return; 2736 } 2737 if (isa<FieldDecl, IndirectFieldDecl>(D)) { 2738 // Delegate all work related to pointer to members to the surrounding 2739 // operator&. 2740 return; 2741 } 2742 if (const auto *BD = dyn_cast<BindingDecl>(D)) { 2743 const auto *DD = cast<DecompositionDecl>(BD->getDecomposedDecl()); 2744 2745 SVal Base = state->getLValue(DD, LCtx); 2746 if (DD->getType()->isReferenceType()) { 2747 Base = state->getSVal(Base.getAsRegion()); 2748 } 2749 2750 SVal V = UnknownVal(); 2751 2752 // Handle binding to data members 2753 if (const auto *ME = dyn_cast<MemberExpr>(BD->getBinding())) { 2754 const auto *Field = cast<FieldDecl>(ME->getMemberDecl()); 2755 V = state->getLValue(Field, Base); 2756 } 2757 // Handle binding to arrays 2758 else if (const auto *ASE = dyn_cast<ArraySubscriptExpr>(BD->getBinding())) { 2759 SVal Idx = state->getSVal(ASE->getIdx(), LCtx); 2760 2761 // Note: the index of an element in a structured binding is automatically 2762 // created and it is a unique identifier of the specific element. Thus it 2763 // cannot be a value that varies at runtime. 2764 assert(Idx.isConstant() && "BindingDecl array index is not a constant!"); 2765 2766 V = state->getLValue(BD->getType(), Idx, Base); 2767 } 2768 // Handle binding to tuple-like strcutures 2769 else if (BD->getHoldingVar()) { 2770 // FIXME: handle tuples 2771 return; 2772 } else 2773 llvm_unreachable("An unknown case of structured binding encountered!"); 2774 2775 if (BD->getType()->isReferenceType()) 2776 V = state->getSVal(V.getAsRegion()); 2777 2778 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2779 ProgramPoint::PostLValueKind); 2780 2781 return; 2782 } 2783 2784 llvm_unreachable("Support for this Decl not implemented."); 2785 } 2786 2787 /// VisitArrayInitLoopExpr - Transfer function for array init loop. 2788 void ExprEngine::VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex, 2789 ExplodedNode *Pred, 2790 ExplodedNodeSet &Dst) { 2791 ExplodedNodeSet CheckerPreStmt; 2792 getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, Ex, *this); 2793 2794 ExplodedNodeSet EvalSet; 2795 StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx); 2796 2797 const Expr *Arr = Ex->getCommonExpr()->getSourceExpr(); 2798 2799 for (auto *Node : CheckerPreStmt) { 2800 const LocationContext *LCtx = Node->getLocationContext(); 2801 ProgramStateRef state = Node->getState(); 2802 2803 SVal Base = UnknownVal(); 2804 2805 // As in case of this expression the sub-expressions are not visited by any 2806 // other transfer functions, they are handled by matching their AST. 2807 2808 // Case of implicit copy or move ctor of object with array member 2809 // 2810 // Note: ExprEngine::VisitMemberExpr is not able to bind the array to the 2811 // environment. 2812 // 2813 // struct S { 2814 // int arr[2]; 2815 // }; 2816 // 2817 // 2818 // S a; 2819 // S b = a; 2820 // 2821 // The AST in case of a *copy constructor* looks like this: 2822 // ArrayInitLoopExpr 2823 // |-OpaqueValueExpr 2824 // | `-MemberExpr <-- match this 2825 // | `-DeclRefExpr 2826 // ` ... 2827 // 2828 // 2829 // S c; 2830 // S d = std::move(d); 2831 // 2832 // In case of a *move constructor* the resulting AST looks like: 2833 // ArrayInitLoopExpr 2834 // |-OpaqueValueExpr 2835 // | `-MemberExpr <-- match this first 2836 // | `-CXXStaticCastExpr <-- match this after 2837 // | `-DeclRefExpr 2838 // ` ... 2839 if (const auto *ME = dyn_cast<MemberExpr>(Arr)) { 2840 Expr *MEBase = ME->getBase(); 2841 2842 // Move ctor 2843 if (auto CXXSCE = dyn_cast<CXXStaticCastExpr>(MEBase)) { 2844 MEBase = CXXSCE->getSubExpr(); 2845 } 2846 2847 auto ObjDeclExpr = cast<DeclRefExpr>(MEBase); 2848 SVal Obj = state->getLValue(cast<VarDecl>(ObjDeclExpr->getDecl()), LCtx); 2849 2850 Base = state->getLValue(cast<FieldDecl>(ME->getMemberDecl()), Obj); 2851 } 2852 2853 // Case of lambda capture and decomposition declaration 2854 // 2855 // int arr[2]; 2856 // 2857 // [arr]{ int a = arr[0]; }(); 2858 // auto[a, b] = arr; 2859 // 2860 // In both of these cases the AST looks like the following: 2861 // ArrayInitLoopExpr 2862 // |-OpaqueValueExpr 2863 // | `-DeclRefExpr <-- match this 2864 // ` ... 2865 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Arr)) 2866 Base = state->getLValue(cast<VarDecl>(DRE->getDecl()), LCtx); 2867 2868 // Create a lazy compound value to the original array 2869 if (const MemRegion *R = Base.getAsRegion()) 2870 Base = state->getSVal(R); 2871 else 2872 Base = UnknownVal(); 2873 2874 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, Base)); 2875 } 2876 2877 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, Ex, *this); 2878 } 2879 2880 /// VisitArraySubscriptExpr - Transfer function for array accesses 2881 void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A, 2882 ExplodedNode *Pred, 2883 ExplodedNodeSet &Dst){ 2884 const Expr *Base = A->getBase()->IgnoreParens(); 2885 const Expr *Idx = A->getIdx()->IgnoreParens(); 2886 2887 ExplodedNodeSet CheckerPreStmt; 2888 getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this); 2889 2890 ExplodedNodeSet EvalSet; 2891 StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx); 2892 2893 bool IsVectorType = A->getBase()->getType()->isVectorType(); 2894 2895 // The "like" case is for situations where C standard prohibits the type to 2896 // be an lvalue, e.g. taking the address of a subscript of an expression of 2897 // type "void *". 2898 bool IsGLValueLike = A->isGLValue() || 2899 (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus); 2900 2901 for (auto *Node : CheckerPreStmt) { 2902 const LocationContext *LCtx = Node->getLocationContext(); 2903 ProgramStateRef state = Node->getState(); 2904 2905 if (IsGLValueLike) { 2906 QualType T = A->getType(); 2907 2908 // One of the forbidden LValue types! We still need to have sensible 2909 // symbolic locations to represent this stuff. Note that arithmetic on 2910 // void pointers is a GCC extension. 2911 if (T->isVoidType()) 2912 T = getContext().CharTy; 2913 2914 SVal V = state->getLValue(T, 2915 state->getSVal(Idx, LCtx), 2916 state->getSVal(Base, LCtx)); 2917 Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr, 2918 ProgramPoint::PostLValueKind); 2919 } else if (IsVectorType) { 2920 // FIXME: non-glvalue vector reads are not modelled. 2921 Bldr.generateNode(A, Node, state, nullptr); 2922 } else { 2923 llvm_unreachable("Array subscript should be an lValue when not \ 2924 a vector and not a forbidden lvalue type"); 2925 } 2926 } 2927 2928 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this); 2929 } 2930 2931 /// VisitMemberExpr - Transfer function for member expressions. 2932 void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 2933 ExplodedNodeSet &Dst) { 2934 // FIXME: Prechecks eventually go in ::Visit(). 2935 ExplodedNodeSet CheckedSet; 2936 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this); 2937 2938 ExplodedNodeSet EvalSet; 2939 ValueDecl *Member = M->getMemberDecl(); 2940 2941 // Handle static member variables and enum constants accessed via 2942 // member syntax. 2943 if (isa<VarDecl, EnumConstantDecl>(Member)) { 2944 for (const auto I : CheckedSet) 2945 VisitCommonDeclRefExpr(M, Member, I, EvalSet); 2946 } else { 2947 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx); 2948 ExplodedNodeSet Tmp; 2949 2950 for (const auto I : CheckedSet) { 2951 ProgramStateRef state = I->getState(); 2952 const LocationContext *LCtx = I->getLocationContext(); 2953 Expr *BaseExpr = M->getBase(); 2954 2955 // Handle C++ method calls. 2956 if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) { 2957 if (MD->isInstance()) 2958 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 2959 2960 SVal MDVal = svalBuilder.getFunctionPointer(MD); 2961 state = state->BindExpr(M, LCtx, MDVal); 2962 2963 Bldr.generateNode(M, I, state); 2964 continue; 2965 } 2966 2967 // Handle regular struct fields / member variables. 2968 const SubRegion *MR = nullptr; 2969 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr, 2970 /*Result=*/nullptr, 2971 /*OutRegionWithAdjustments=*/&MR); 2972 SVal baseExprVal = 2973 MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx); 2974 2975 const auto *field = cast<FieldDecl>(Member); 2976 SVal L = state->getLValue(field, baseExprVal); 2977 2978 if (M->isGLValue() || M->getType()->isArrayType()) { 2979 // We special-case rvalues of array type because the analyzer cannot 2980 // reason about them, since we expect all regions to be wrapped in Locs. 2981 // We instead treat these as lvalues and assume that they will decay to 2982 // pointers as soon as they are used. 2983 if (!M->isGLValue()) { 2984 assert(M->getType()->isArrayType()); 2985 const auto *PE = 2986 dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M)); 2987 if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) { 2988 llvm_unreachable("should always be wrapped in ArrayToPointerDecay"); 2989 } 2990 } 2991 2992 if (field->getType()->isReferenceType()) { 2993 if (const MemRegion *R = L.getAsRegion()) 2994 L = state->getSVal(R); 2995 else 2996 L = UnknownVal(); 2997 } 2998 2999 Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr, 3000 ProgramPoint::PostLValueKind); 3001 } else { 3002 Bldr.takeNodes(I); 3003 evalLoad(Tmp, M, M, I, state, L); 3004 Bldr.addNodes(Tmp); 3005 } 3006 } 3007 } 3008 3009 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this); 3010 } 3011 3012 void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred, 3013 ExplodedNodeSet &Dst) { 3014 ExplodedNodeSet AfterPreSet; 3015 getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this); 3016 3017 // For now, treat all the arguments to C11 atomics as escaping. 3018 // FIXME: Ideally we should model the behavior of the atomics precisely here. 3019 3020 ExplodedNodeSet AfterInvalidateSet; 3021 StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx); 3022 3023 for (const auto I : AfterPreSet) { 3024 ProgramStateRef State = I->getState(); 3025 const LocationContext *LCtx = I->getLocationContext(); 3026 3027 SmallVector<SVal, 8> ValuesToInvalidate; 3028 for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) { 3029 const Expr *SubExpr = AE->getSubExprs()[SI]; 3030 SVal SubExprVal = State->getSVal(SubExpr, LCtx); 3031 ValuesToInvalidate.push_back(SubExprVal); 3032 } 3033 3034 State = State->invalidateRegions(ValuesToInvalidate, AE, 3035 currBldrCtx->blockCount(), 3036 LCtx, 3037 /*CausedByPointerEscape*/true, 3038 /*Symbols=*/nullptr); 3039 3040 SVal ResultVal = UnknownVal(); 3041 State = State->BindExpr(AE, LCtx, ResultVal); 3042 Bldr.generateNode(AE, I, State, nullptr, 3043 ProgramPoint::PostStmtKind); 3044 } 3045 3046 getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this); 3047 } 3048 3049 // A value escapes in four possible cases: 3050 // (1) We are binding to something that is not a memory region. 3051 // (2) We are binding to a MemRegion that does not have stack storage. 3052 // (3) We are binding to a top-level parameter region with a non-trivial 3053 // destructor. We won't see the destructor during analysis, but it's there. 3054 // (4) We are binding to a MemRegion with stack storage that the store 3055 // does not understand. 3056 ProgramStateRef ExprEngine::processPointerEscapedOnBind( 3057 ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals, 3058 const LocationContext *LCtx, PointerEscapeKind Kind, 3059 const CallEvent *Call) { 3060 SmallVector<SVal, 8> Escaped; 3061 for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) { 3062 // Cases (1) and (2). 3063 const MemRegion *MR = LocAndVal.first.getAsRegion(); 3064 if (!MR || !MR->hasStackStorage()) { 3065 Escaped.push_back(LocAndVal.second); 3066 continue; 3067 } 3068 3069 // Case (3). 3070 if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion())) 3071 if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame()) 3072 if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl()) 3073 if (!RD->hasTrivialDestructor()) { 3074 Escaped.push_back(LocAndVal.second); 3075 continue; 3076 } 3077 3078 // Case (4): in order to test that, generate a new state with the binding 3079 // added. If it is the same state, then it escapes (since the store cannot 3080 // represent the binding). 3081 // Do this only if we know that the store is not supposed to generate the 3082 // same state. 3083 SVal StoredVal = State->getSVal(MR); 3084 if (StoredVal != LocAndVal.second) 3085 if (State == 3086 (State->bindLoc(loc::MemRegionVal(MR), LocAndVal.second, LCtx))) 3087 Escaped.push_back(LocAndVal.second); 3088 } 3089 3090 if (Escaped.empty()) 3091 return State; 3092 3093 return escapeValues(State, Escaped, Kind, Call); 3094 } 3095 3096 ProgramStateRef 3097 ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc, 3098 SVal Val, const LocationContext *LCtx) { 3099 std::pair<SVal, SVal> LocAndVal(Loc, Val); 3100 return processPointerEscapedOnBind(State, LocAndVal, LCtx, PSK_EscapeOnBind, 3101 nullptr); 3102 } 3103 3104 ProgramStateRef 3105 ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, 3106 const InvalidatedSymbols *Invalidated, 3107 ArrayRef<const MemRegion *> ExplicitRegions, 3108 const CallEvent *Call, 3109 RegionAndSymbolInvalidationTraits &ITraits) { 3110 if (!Invalidated || Invalidated->empty()) 3111 return State; 3112 3113 if (!Call) 3114 return getCheckerManager().runCheckersForPointerEscape(State, 3115 *Invalidated, 3116 nullptr, 3117 PSK_EscapeOther, 3118 &ITraits); 3119 3120 // If the symbols were invalidated by a call, we want to find out which ones 3121 // were invalidated directly due to being arguments to the call. 3122 InvalidatedSymbols SymbolsDirectlyInvalidated; 3123 for (const auto I : ExplicitRegions) { 3124 if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>()) 3125 SymbolsDirectlyInvalidated.insert(R->getSymbol()); 3126 } 3127 3128 InvalidatedSymbols SymbolsIndirectlyInvalidated; 3129 for (const auto &sym : *Invalidated) { 3130 if (SymbolsDirectlyInvalidated.count(sym)) 3131 continue; 3132 SymbolsIndirectlyInvalidated.insert(sym); 3133 } 3134 3135 if (!SymbolsDirectlyInvalidated.empty()) 3136 State = getCheckerManager().runCheckersForPointerEscape(State, 3137 SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits); 3138 3139 // Notify about the symbols that get indirectly invalidated by the call. 3140 if (!SymbolsIndirectlyInvalidated.empty()) 3141 State = getCheckerManager().runCheckersForPointerEscape(State, 3142 SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits); 3143 3144 return State; 3145 } 3146 3147 /// evalBind - Handle the semantics of binding a value to a specific location. 3148 /// This method is used by evalStore and (soon) VisitDeclStmt, and others. 3149 void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 3150 ExplodedNode *Pred, 3151 SVal location, SVal Val, 3152 bool atDeclInit, const ProgramPoint *PP) { 3153 const LocationContext *LC = Pred->getLocationContext(); 3154 PostStmt PS(StoreE, LC); 3155 if (!PP) 3156 PP = &PS; 3157 3158 // Do a previsit of the bind. 3159 ExplodedNodeSet CheckedSet; 3160 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 3161 StoreE, *this, *PP); 3162 3163 StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx); 3164 3165 // If the location is not a 'Loc', it will already be handled by 3166 // the checkers. There is nothing left to do. 3167 if (!isa<Loc>(location)) { 3168 const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr, 3169 /*tag*/nullptr); 3170 ProgramStateRef state = Pred->getState(); 3171 state = processPointerEscapedOnBind(state, location, Val, LC); 3172 Bldr.generateNode(L, state, Pred); 3173 return; 3174 } 3175 3176 for (const auto PredI : CheckedSet) { 3177 ProgramStateRef state = PredI->getState(); 3178 3179 state = processPointerEscapedOnBind(state, location, Val, LC); 3180 3181 // When binding the value, pass on the hint that this is a initialization. 3182 // For initializations, we do not need to inform clients of region 3183 // changes. 3184 state = state->bindLoc(location.castAs<Loc>(), 3185 Val, LC, /* notifyChanges = */ !atDeclInit); 3186 3187 const MemRegion *LocReg = nullptr; 3188 if (Optional<loc::MemRegionVal> LocRegVal = 3189 location.getAs<loc::MemRegionVal>()) { 3190 LocReg = LocRegVal->getRegion(); 3191 } 3192 3193 const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr); 3194 Bldr.generateNode(L, state, PredI); 3195 } 3196 } 3197 3198 /// evalStore - Handle the semantics of a store via an assignment. 3199 /// @param Dst The node set to store generated state nodes 3200 /// @param AssignE The assignment expression if the store happens in an 3201 /// assignment. 3202 /// @param LocationE The location expression that is stored to. 3203 /// @param state The current simulation state 3204 /// @param location The location to store the value 3205 /// @param Val The value to be stored 3206 void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 3207 const Expr *LocationE, 3208 ExplodedNode *Pred, 3209 ProgramStateRef state, SVal location, SVal Val, 3210 const ProgramPointTag *tag) { 3211 // Proceed with the store. We use AssignE as the anchor for the PostStore 3212 // ProgramPoint if it is non-NULL, and LocationE otherwise. 3213 const Expr *StoreE = AssignE ? AssignE : LocationE; 3214 3215 // Evaluate the location (checks for bad dereferences). 3216 ExplodedNodeSet Tmp; 3217 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false); 3218 3219 if (Tmp.empty()) 3220 return; 3221 3222 if (location.isUndef()) 3223 return; 3224 3225 for (const auto I : Tmp) 3226 evalBind(Dst, StoreE, I, location, Val, false); 3227 } 3228 3229 void ExprEngine::evalLoad(ExplodedNodeSet &Dst, 3230 const Expr *NodeEx, 3231 const Expr *BoundEx, 3232 ExplodedNode *Pred, 3233 ProgramStateRef state, 3234 SVal location, 3235 const ProgramPointTag *tag, 3236 QualType LoadTy) { 3237 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc."); 3238 assert(NodeEx); 3239 assert(BoundEx); 3240 // Evaluate the location (checks for bad dereferences). 3241 ExplodedNodeSet Tmp; 3242 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true); 3243 if (Tmp.empty()) 3244 return; 3245 3246 StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 3247 if (location.isUndef()) 3248 return; 3249 3250 // Proceed with the load. 3251 for (const auto I : Tmp) { 3252 state = I->getState(); 3253 const LocationContext *LCtx = I->getLocationContext(); 3254 3255 SVal V = UnknownVal(); 3256 if (location.isValid()) { 3257 if (LoadTy.isNull()) 3258 LoadTy = BoundEx->getType(); 3259 V = state->getSVal(location.castAs<Loc>(), LoadTy); 3260 } 3261 3262 Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag, 3263 ProgramPoint::PostLoadKind); 3264 } 3265 } 3266 3267 void ExprEngine::evalLocation(ExplodedNodeSet &Dst, 3268 const Stmt *NodeEx, 3269 const Stmt *BoundEx, 3270 ExplodedNode *Pred, 3271 ProgramStateRef state, 3272 SVal location, 3273 bool isLoad) { 3274 StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx); 3275 // Early checks for performance reason. 3276 if (location.isUnknown()) { 3277 return; 3278 } 3279 3280 ExplodedNodeSet Src; 3281 BldrTop.takeNodes(Pred); 3282 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx); 3283 if (Pred->getState() != state) { 3284 // Associate this new state with an ExplodedNode. 3285 // FIXME: If I pass null tag, the graph is incorrect, e.g for 3286 // int *p; 3287 // p = 0; 3288 // *p = 0xDEADBEEF; 3289 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 3290 // instead "int *p" is noted as 3291 // "Variable 'p' initialized to a null pointer value" 3292 3293 static SimpleProgramPointTag tag(TagProviderName, "Location"); 3294 Bldr.generateNode(NodeEx, Pred, state, &tag); 3295 } 3296 ExplodedNodeSet Tmp; 3297 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, 3298 NodeEx, BoundEx, *this); 3299 BldrTop.addNodes(Tmp); 3300 } 3301 3302 std::pair<const ProgramPointTag *, const ProgramPointTag*> 3303 ExprEngine::geteagerlyAssumeBinOpBifurcationTags() { 3304 static SimpleProgramPointTag 3305 eagerlyAssumeBinOpBifurcationTrue(TagProviderName, 3306 "Eagerly Assume True"), 3307 eagerlyAssumeBinOpBifurcationFalse(TagProviderName, 3308 "Eagerly Assume False"); 3309 return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue, 3310 &eagerlyAssumeBinOpBifurcationFalse); 3311 } 3312 3313 void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, 3314 ExplodedNodeSet &Src, 3315 const Expr *Ex) { 3316 StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx); 3317 3318 for (const auto Pred : Src) { 3319 // Test if the previous node was as the same expression. This can happen 3320 // when the expression fails to evaluate to anything meaningful and 3321 // (as an optimization) we don't generate a node. 3322 ProgramPoint P = Pred->getLocation(); 3323 if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) { 3324 continue; 3325 } 3326 3327 ProgramStateRef state = Pred->getState(); 3328 SVal V = state->getSVal(Ex, Pred->getLocationContext()); 3329 Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>(); 3330 if (SEV && SEV->isExpression()) { 3331 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 3332 geteagerlyAssumeBinOpBifurcationTags(); 3333 3334 ProgramStateRef StateTrue, StateFalse; 3335 std::tie(StateTrue, StateFalse) = state->assume(*SEV); 3336 3337 // First assume that the condition is true. 3338 if (StateTrue) { 3339 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 3340 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 3341 Bldr.generateNode(Ex, Pred, StateTrue, tags.first); 3342 } 3343 3344 // Next, assume that the condition is false. 3345 if (StateFalse) { 3346 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 3347 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 3348 Bldr.generateNode(Ex, Pred, StateFalse, tags.second); 3349 } 3350 } 3351 } 3352 } 3353 3354 void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, 3355 ExplodedNodeSet &Dst) { 3356 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 3357 // We have processed both the inputs and the outputs. All of the outputs 3358 // should evaluate to Locs. Nuke all of their values. 3359 3360 // FIXME: Some day in the future it would be nice to allow a "plug-in" 3361 // which interprets the inline asm and stores proper results in the 3362 // outputs. 3363 3364 ProgramStateRef state = Pred->getState(); 3365 3366 for (const Expr *O : A->outputs()) { 3367 SVal X = state->getSVal(O, Pred->getLocationContext()); 3368 assert(!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef. 3369 3370 if (Optional<Loc> LV = X.getAs<Loc>()) 3371 state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext()); 3372 } 3373 3374 Bldr.generateNode(A, Pred, state); 3375 } 3376 3377 void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, 3378 ExplodedNodeSet &Dst) { 3379 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 3380 Bldr.generateNode(A, Pred, Pred->getState()); 3381 } 3382 3383 //===----------------------------------------------------------------------===// 3384 // Visualization. 3385 //===----------------------------------------------------------------------===// 3386 3387 namespace llvm { 3388 3389 template<> 3390 struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits { 3391 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} 3392 3393 static bool nodeHasBugReport(const ExplodedNode *N) { 3394 BugReporter &BR = static_cast<ExprEngine &>( 3395 N->getState()->getStateManager().getOwningEngine()).getBugReporter(); 3396 3397 const auto EQClasses = 3398 llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end()); 3399 3400 for (const auto &EQ : EQClasses) { 3401 for (const auto &I : EQ.getReports()) { 3402 const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get()); 3403 if (!PR) 3404 continue; 3405 const ExplodedNode *EN = PR->getErrorNode(); 3406 if (EN->getState() == N->getState() && 3407 EN->getLocation() == N->getLocation()) 3408 return true; 3409 } 3410 } 3411 return false; 3412 } 3413 3414 /// \p PreCallback: callback before break. 3415 /// \p PostCallback: callback after break. 3416 /// \p Stop: stop iteration if returns @c true 3417 /// \return Whether @c Stop ever returned @c true. 3418 static bool traverseHiddenNodes( 3419 const ExplodedNode *N, 3420 llvm::function_ref<void(const ExplodedNode *)> PreCallback, 3421 llvm::function_ref<void(const ExplodedNode *)> PostCallback, 3422 llvm::function_ref<bool(const ExplodedNode *)> Stop) { 3423 while (true) { 3424 PreCallback(N); 3425 if (Stop(N)) 3426 return true; 3427 3428 if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc(), nullptr)) 3429 break; 3430 PostCallback(N); 3431 3432 N = N->getFirstSucc(); 3433 } 3434 return false; 3435 } 3436 3437 static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) { 3438 return N->isTrivial(); 3439 } 3440 3441 static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){ 3442 std::string Buf; 3443 llvm::raw_string_ostream Out(Buf); 3444 3445 const bool IsDot = true; 3446 const unsigned int Space = 1; 3447 ProgramStateRef State = N->getState(); 3448 3449 Out << "{ \"state_id\": " << State->getID() 3450 << ",\\l"; 3451 3452 Indent(Out, Space, IsDot) << "\"program_points\": [\\l"; 3453 3454 // Dump program point for all the previously skipped nodes. 3455 traverseHiddenNodes( 3456 N, 3457 [&](const ExplodedNode *OtherNode) { 3458 Indent(Out, Space + 1, IsDot) << "{ "; 3459 OtherNode->getLocation().printJson(Out, /*NL=*/"\\l"); 3460 Out << ", \"tag\": "; 3461 if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag()) 3462 Out << '\"' << Tag->getTagDescription() << "\""; 3463 else 3464 Out << "null"; 3465 Out << ", \"node_id\": " << OtherNode->getID() << 3466 ", \"is_sink\": " << OtherNode->isSink() << 3467 ", \"has_report\": " << nodeHasBugReport(OtherNode) << " }"; 3468 }, 3469 // Adds a comma and a new-line between each program point. 3470 [&](const ExplodedNode *) { Out << ",\\l"; }, 3471 [&](const ExplodedNode *) { return false; }); 3472 3473 Out << "\\l"; // Adds a new-line to the last program point. 3474 Indent(Out, Space, IsDot) << "],\\l"; 3475 3476 State->printDOT(Out, N->getLocationContext(), Space); 3477 3478 Out << "\\l}\\l"; 3479 return Out.str(); 3480 } 3481 }; 3482 3483 } // namespace llvm 3484 3485 void ExprEngine::ViewGraph(bool trim) { 3486 std::string Filename = DumpGraph(trim); 3487 llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT); 3488 } 3489 3490 void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode *> Nodes) { 3491 std::string Filename = DumpGraph(Nodes); 3492 llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT); 3493 } 3494 3495 std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) { 3496 if (trim) { 3497 std::vector<const ExplodedNode *> Src; 3498 3499 // Iterate through the reports and get their nodes. 3500 for (BugReporter::EQClasses_iterator 3501 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 3502 const auto *R = 3503 dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get()); 3504 if (!R) 3505 continue; 3506 const auto *N = const_cast<ExplodedNode *>(R->getErrorNode()); 3507 Src.push_back(N); 3508 } 3509 return DumpGraph(Src, Filename); 3510 } 3511 3512 return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false, 3513 /*Title=*/"Exploded Graph", 3514 /*Filename=*/std::string(Filename)); 3515 } 3516 3517 std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode *> Nodes, 3518 StringRef Filename) { 3519 std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes)); 3520 3521 if (!TrimmedG.get()) { 3522 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 3523 return ""; 3524 } 3525 3526 return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine", 3527 /*ShortNames=*/false, 3528 /*Title=*/"Trimmed Exploded Graph", 3529 /*Filename=*/std::string(Filename)); 3530 } 3531 3532 void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() { 3533 static int index = 0; 3534 return &index; 3535 } 3536 3537 void ExprEngine::anchor() { } 3538