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