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