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