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