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