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 85using namespace clang; 86using namespace ento; 87 88#define DEBUG_TYPE "ExprEngine" 89 90STATISTIC(NumRemoveDeadBindings, 91 "The # of times RemoveDeadBindings is called"); 92STATISTIC(NumMaxBlockCountReached, 93 "The # of aborted paths due to reaching the maximum block count in " 94 "a top level function"); 95STATISTIC(NumMaxBlockCountReachedInInlined, 96 "The # of aborted paths due to reaching the maximum block count in " 97 "an inlined function"); 98STATISTIC(NumTimesRetriedWithoutInlining, 99 "The # of times we re-evaluated a call without inlining"); 100 101//===----------------------------------------------------------------------===// 102// Internal program state traits. 103//===----------------------------------------------------------------------===// 104 105namespace { 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. 120class 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 133public: 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()->getNameAsString() << '\"'; 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 191typedef llvm::ImmutableMap<ConstructedObjectKey, SVal> 192 ObjectsUnderConstructionMap; 193REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction, 194 ObjectsUnderConstructionMap) 195 196//===----------------------------------------------------------------------===// 197// Engine construction and deletion. 198//===----------------------------------------------------------------------===// 199 200static const char* TagProviderName = "ExprEngine"; 201 202ExprEngine::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 232ProgramStateRef 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 309ProgramStateRef 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 460ProgramStateRef 461ExprEngine::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 473Optional<SVal> 474ExprEngine::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 481ProgramStateRef 482ExprEngine::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 490ProgramStateRef 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 499ProgramStateRef 500ExprEngine::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 508bool 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 515bool 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. 537ProgramStateRef ExprEngine::processAssume(ProgramStateRef state, 538 SVal cond, bool assumption) { 539 return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 540} 541 542ProgramStateRef 543ExprEngine::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 554static void 555printObjectsUnderConstructionJson(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 601void 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 623void ExprEngine::processEndWorklist() { 624 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 625} 626 627void 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 663static 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 689void 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 769void 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 799void 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 817void 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 905void 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 932void 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 951void 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 985void 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 1025void 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 1045void 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 1069void 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 1130void 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 1148void 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 1175ProgramStateRef 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 1202void 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 1890bool 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). 1954void 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. 2035static 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 2073static 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. 2099static 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 2132void ExprEngine::processBranch(const Stmt *Condition, 2133 NodeBuilderContext& BldCtx, 2134 ExplodedNode *Pred, 2135 ExplodedNodeSet &Dst, 2136 const CFGBlock *DstT, 2137 const CFGBlock *DstF) { 2138 assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) && 2139 "CXXBindTemporaryExprs are handled by processBindTemporary."); 2140 const LocationContext *LCtx = Pred->getLocationContext(); 2141 PrettyStackTraceLocationContext StackCrashInfo(LCtx); 2142 currBldrCtx = &BldCtx; 2143 2144 // Check for NULL conditions; e.g. "for(;;)" 2145 if (!Condition) { 2146 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF); 2147 NullCondBldr.markInfeasible(false); 2148 NullCondBldr.generateNode(Pred->getState(), true, Pred); 2149 return; 2150 } 2151 2152 if (const auto *Ex = dyn_cast<Expr>(Condition)) 2153 Condition = Ex->IgnoreParens(); 2154 2155 Condition = ResolveCondition(Condition, BldCtx.getBlock()); 2156 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 2157 Condition->getBeginLoc(), 2158 "Error evaluating branch"); 2159 2160 ExplodedNodeSet CheckersOutSet; 2161 getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet, 2162 Pred, *this); 2163 // We generated only sinks. 2164 if (CheckersOutSet.empty()) 2165 return; 2166 2167 BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF); 2168 for (const auto PredI : CheckersOutSet) { 2169 if (PredI->isSink()) 2170 continue; 2171 2172 ProgramStateRef PrevState = PredI->getState(); 2173 SVal X = PrevState->getSVal(Condition, PredI->getLocationContext()); 2174 2175 if (X.isUnknownOrUndef()) { 2176 // Give it a chance to recover from unknown. 2177 if (const auto *Ex = dyn_cast<Expr>(Condition)) { 2178 if (Ex->getType()->isIntegralOrEnumerationType()) { 2179 // Try to recover some path-sensitivity. Right now casts of symbolic 2180 // integers that promote their values are currently not tracked well. 2181 // If 'Condition' is such an expression, try and recover the 2182 // underlying value and use that instead. 2183 SVal recovered = RecoverCastedSymbol(PrevState, Condition, 2184 PredI->getLocationContext(), 2185 getContext()); 2186 2187 if (!recovered.isUnknown()) { 2188 X = recovered; 2189 } 2190 } 2191 } 2192 } 2193 2194 // If the condition is still unknown, give up. 2195 if (X.isUnknownOrUndef()) { 2196 builder.generateNode(PrevState, true, PredI); 2197 builder.generateNode(PrevState, false, PredI); 2198 continue; 2199 } 2200 2201 DefinedSVal V = X.castAs<DefinedSVal>(); 2202 2203 ProgramStateRef StTrue, StFalse; 2204 std::tie(StTrue, StFalse) = PrevState->assume(V); 2205 2206 // Process the true branch. 2207 if (builder.isFeasible(true)) { 2208 if (StTrue) 2209 builder.generateNode(StTrue, true, PredI); 2210 else 2211 builder.markInfeasible(true); 2212 } 2213 2214 // Process the false branch. 2215 if (builder.isFeasible(false)) { 2216 if (StFalse) 2217 builder.generateNode(StFalse, false, PredI); 2218 else 2219 builder.markInfeasible(false); 2220 } 2221 } 2222 currBldrCtx = nullptr; 2223} 2224 2225/// The GDM component containing the set of global variables which have been 2226/// previously initialized with explicit initializers. 2227REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet, 2228 llvm::ImmutableSet<const VarDecl *>) 2229 2230void ExprEngine::processStaticInitializer(const DeclStmt *DS, 2231 NodeBuilderContext &BuilderCtx, 2232 ExplodedNode *Pred, 2233 ExplodedNodeSet &Dst, 2234 const CFGBlock *DstT, 2235 const CFGBlock *DstF) { 2236 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 2237 currBldrCtx = &BuilderCtx; 2238 2239 const auto *VD = cast<VarDecl>(DS->getSingleDecl()); 2240 ProgramStateRef state = Pred->getState(); 2241 bool initHasRun = state->contains<InitializedGlobalsSet>(VD); 2242 BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF); 2243 2244 if (!initHasRun) { 2245 state = state->add<InitializedGlobalsSet>(VD); 2246 } 2247 2248 builder.generateNode(state, initHasRun, Pred); 2249 builder.markInfeasible(!initHasRun); 2250 2251 currBldrCtx = nullptr; 2252} 2253 2254/// processIndirectGoto - Called by CoreEngine. Used to generate successor 2255/// nodes by processing the 'effects' of a computed goto jump. 2256void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 2257 ProgramStateRef state = builder.getState(); 2258 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); 2259 2260 // Three possibilities: 2261 // 2262 // (1) We know the computed label. 2263 // (2) The label is NULL (or some other constant), or Undefined. 2264 // (3) We have no clue about the label. Dispatch to all targets. 2265 // 2266 2267 using iterator = IndirectGotoNodeBuilder::iterator; 2268 2269 if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) { 2270 const LabelDecl *L = LV->getLabel(); 2271 2272 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 2273 if (I.getLabel() == L) { 2274 builder.generateNode(I, state); 2275 return; 2276 } 2277 } 2278 2279 llvm_unreachable("No block with label."); 2280 } 2281 2282 if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) { 2283 // Dispatch to the first target and mark it as a sink. 2284 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 2285 // FIXME: add checker visit. 2286 // UndefBranches.insert(N); 2287 return; 2288 } 2289 2290 // This is really a catch-all. We don't support symbolics yet. 2291 // FIXME: Implement dispatch for symbolic pointers. 2292 2293 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) 2294 builder.generateNode(I, state); 2295} 2296 2297void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC, 2298 ExplodedNode *Pred, 2299 ExplodedNodeSet &Dst, 2300 const BlockEdge &L) { 2301 SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC); 2302 getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this); 2303} 2304 2305/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 2306/// nodes when the control reaches the end of a function. 2307void ExprEngine::processEndOfFunction(NodeBuilderContext& BC, 2308 ExplodedNode *Pred, 2309 const ReturnStmt *RS) { 2310 ProgramStateRef State = Pred->getState(); 2311 2312 if (!Pred->getStackFrame()->inTopFrame()) 2313 State = finishArgumentConstruction( 2314 State, *getStateManager().getCallEventManager().getCaller( 2315 Pred->getStackFrame(), Pred->getState())); 2316 2317 // FIXME: We currently cannot assert that temporaries are clear, because 2318 // lifetime extended temporaries are not always modelled correctly. In some 2319 // cases when we materialize the temporary, we do 2320 // createTemporaryRegionIfNeeded(), and the region changes, and also the 2321 // respective destructor becomes automatic from temporary. So for now clean up 2322 // the state manually before asserting. Ideally, this braced block of code 2323 // should go away. 2324 { 2325 const LocationContext *FromLC = Pred->getLocationContext(); 2326 const LocationContext *ToLC = FromLC->getStackFrame()->getParent(); 2327 const LocationContext *LC = FromLC; 2328 while (LC != ToLC) { 2329 assert(LC && "ToLC must be a parent of FromLC!"); 2330 for (auto I : State->get<ObjectsUnderConstruction>()) 2331 if (I.first.getLocationContext() == LC) { 2332 // The comment above only pardons us for not cleaning up a 2333 // temporary destructor. If any other statements are found here, 2334 // it must be a separate problem. 2335 assert(I.first.getItem().getKind() == 2336 ConstructionContextItem::TemporaryDestructorKind || 2337 I.first.getItem().getKind() == 2338 ConstructionContextItem::ElidedDestructorKind); 2339 State = State->remove<ObjectsUnderConstruction>(I.first); 2340 } 2341 LC = LC->getParent(); 2342 } 2343 } 2344 2345 // Perform the transition with cleanups. 2346 if (State != Pred->getState()) { 2347 ExplodedNodeSet PostCleanup; 2348 NodeBuilder Bldr(Pred, PostCleanup, BC); 2349 Pred = Bldr.generateNode(Pred->getLocation(), State, Pred); 2350 if (!Pred) { 2351 // The node with clean temporaries already exists. We might have reached 2352 // it on a path on which we initialize different temporaries. 2353 return; 2354 } 2355 } 2356 2357 assert(areAllObjectsFullyConstructed(Pred->getState(), 2358 Pred->getLocationContext(), 2359 Pred->getStackFrame()->getParent())); 2360 2361 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); 2362 2363 ExplodedNodeSet Dst; 2364 if (Pred->getLocationContext()->inTopFrame()) { 2365 // Remove dead symbols. 2366 ExplodedNodeSet AfterRemovedDead; 2367 removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead); 2368 2369 // Notify checkers. 2370 for (const auto I : AfterRemovedDead) 2371 getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS); 2372 } else { 2373 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS); 2374 } 2375 2376 Engine.enqueueEndOfFunction(Dst, RS); 2377} 2378 2379/// ProcessSwitch - Called by CoreEngine. Used to generate successor 2380/// nodes by processing the 'effects' of a switch statement. 2381void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 2382 using iterator = SwitchNodeBuilder::iterator; 2383 2384 ProgramStateRef state = builder.getState(); 2385 const Expr *CondE = builder.getCondition(); 2386 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); 2387 2388 if (CondV_untested.isUndef()) { 2389 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 2390 // FIXME: add checker 2391 //UndefBranches.insert(N); 2392 2393 return; 2394 } 2395 DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>(); 2396 2397 ProgramStateRef DefaultSt = state; 2398 2399 iterator I = builder.begin(), EI = builder.end(); 2400 bool defaultIsFeasible = I == EI; 2401 2402 for ( ; I != EI; ++I) { 2403 // Successor may be pruned out during CFG construction. 2404 if (!I.getBlock()) 2405 continue; 2406 2407 const CaseStmt *Case = I.getCase(); 2408 2409 // Evaluate the LHS of the case value. 2410 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); 2411 assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType())); 2412 2413 // Get the RHS of the case, if it exists. 2414 llvm::APSInt V2; 2415 if (const Expr *E = Case->getRHS()) 2416 V2 = E->EvaluateKnownConstInt(getContext()); 2417 else 2418 V2 = V1; 2419 2420 ProgramStateRef StateCase; 2421 if (Optional<NonLoc> NL = CondV.getAs<NonLoc>()) 2422 std::tie(StateCase, DefaultSt) = 2423 DefaultSt->assumeInclusiveRange(*NL, V1, V2); 2424 else // UnknownVal 2425 StateCase = DefaultSt; 2426 2427 if (StateCase) 2428 builder.generateCaseStmtNode(I, StateCase); 2429 2430 // Now "assume" that the case doesn't match. Add this state 2431 // to the default state (if it is feasible). 2432 if (DefaultSt) 2433 defaultIsFeasible = true; 2434 else { 2435 defaultIsFeasible = false; 2436 break; 2437 } 2438 } 2439 2440 if (!defaultIsFeasible) 2441 return; 2442 2443 // If we have switch(enum value), the default branch is not 2444 // feasible if all of the enum constants not covered by 'case:' statements 2445 // are not feasible values for the switch condition. 2446 // 2447 // Note that this isn't as accurate as it could be. Even if there isn't 2448 // a case for a particular enum value as long as that enum value isn't 2449 // feasible then it shouldn't be considered for making 'default:' reachable. 2450 const SwitchStmt *SS = builder.getSwitch(); 2451 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 2452 if (CondExpr->getType()->getAs<EnumType>()) { 2453 if (SS->isAllEnumCasesCovered()) 2454 return; 2455 } 2456 2457 builder.generateDefaultCaseNode(DefaultSt); 2458} 2459 2460//===----------------------------------------------------------------------===// 2461// Transfer functions: Loads and stores. 2462//===----------------------------------------------------------------------===// 2463 2464void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 2465 ExplodedNode *Pred, 2466 ExplodedNodeSet &Dst) { 2467 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 2468 2469 ProgramStateRef state = Pred->getState(); 2470 const LocationContext *LCtx = Pred->getLocationContext(); 2471 2472 if (const auto *VD = dyn_cast<VarDecl>(D)) { 2473 // C permits "extern void v", and if you cast the address to a valid type, 2474 // you can even do things with it. We simply pretend 2475 assert(Ex->isGLValue() || VD->getType()->isVoidType()); 2476 const LocationContext *LocCtxt = Pred->getLocationContext(); 2477 const Decl *D = LocCtxt->getDecl(); 2478 const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D); 2479 const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex); 2480 Optional<std::pair<SVal, QualType>> VInfo; 2481 2482 if (AMgr.options.ShouldInlineLambdas && DeclRefEx && 2483 DeclRefEx->refersToEnclosingVariableOrCapture() && MD && 2484 MD->getParent()->isLambda()) { 2485 // Lookup the field of the lambda. 2486 const CXXRecordDecl *CXXRec = MD->getParent(); 2487 llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields; 2488 FieldDecl *LambdaThisCaptureField; 2489 CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField); 2490 2491 // Sema follows a sequence of complex rules to determine whether the 2492 // variable should be captured. 2493 if (const FieldDecl *FD = LambdaCaptureFields[VD]) { 2494 Loc CXXThis = 2495 svalBuilder.getCXXThis(MD, LocCtxt->getStackFrame()); 2496 SVal CXXThisVal = state->getSVal(CXXThis); 2497 VInfo = std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType()); 2498 } 2499 } 2500 2501 if (!VInfo) 2502 VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType()); 2503 2504 SVal V = VInfo->first; 2505 bool IsReference = VInfo->second->isReferenceType(); 2506 2507 // For references, the 'lvalue' is the pointer address stored in the 2508 // reference region. 2509 if (IsReference) { 2510 if (const MemRegion *R = V.getAsRegion()) 2511 V = state->getSVal(R); 2512 else 2513 V = UnknownVal(); 2514 } 2515 2516 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2517 ProgramPoint::PostLValueKind); 2518 return; 2519 } 2520 if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) { 2521 assert(!Ex->isGLValue()); 2522 SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 2523 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V)); 2524 return; 2525 } 2526 if (const auto *FD = dyn_cast<FunctionDecl>(D)) { 2527 SVal V = svalBuilder.getFunctionPointer(FD); 2528 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2529 ProgramPoint::PostLValueKind); 2530 return; 2531 } 2532 if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D)) { 2533 // FIXME: Compute lvalue of field pointers-to-member. 2534 // Right now we just use a non-null void pointer, so that it gives proper 2535 // results in boolean contexts. 2536 // FIXME: Maybe delegate this to the surrounding operator&. 2537 // Note how this expression is lvalue, however pointer-to-member is NonLoc. 2538 SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy, 2539 currBldrCtx->blockCount()); 2540 state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true); 2541 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, 2542 ProgramPoint::PostLValueKind); 2543 return; 2544 } 2545 if (isa<BindingDecl>(D)) { 2546 // FIXME: proper support for bound declarations. 2547 // For now, let's just prevent crashing. 2548 return; 2549 } 2550 2551 llvm_unreachable("Support for this Decl not implemented."); 2552} 2553 2554/// VisitArraySubscriptExpr - Transfer function for array accesses 2555void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A, 2556 ExplodedNode *Pred, 2557 ExplodedNodeSet &Dst){ 2558 const Expr *Base = A->getBase()->IgnoreParens(); 2559 const Expr *Idx = A->getIdx()->IgnoreParens(); 2560 2561 ExplodedNodeSet CheckerPreStmt; 2562 getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this); 2563 2564 ExplodedNodeSet EvalSet; 2565 StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx); 2566 2567 bool IsVectorType = A->getBase()->getType()->isVectorType(); 2568 2569 // The "like" case is for situations where C standard prohibits the type to 2570 // be an lvalue, e.g. taking the address of a subscript of an expression of 2571 // type "void *". 2572 bool IsGLValueLike = A->isGLValue() || 2573 (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus); 2574 2575 for (auto *Node : CheckerPreStmt) { 2576 const LocationContext *LCtx = Node->getLocationContext(); 2577 ProgramStateRef state = Node->getState(); 2578 2579 if (IsGLValueLike) { 2580 QualType T = A->getType(); 2581 2582 // One of the forbidden LValue types! We still need to have sensible 2583 // symbolic locations to represent this stuff. Note that arithmetic on 2584 // void pointers is a GCC extension. 2585 if (T->isVoidType()) 2586 T = getContext().CharTy; 2587 2588 SVal V = state->getLValue(T, 2589 state->getSVal(Idx, LCtx), 2590 state->getSVal(Base, LCtx)); 2591 Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr, 2592 ProgramPoint::PostLValueKind); 2593 } else if (IsVectorType) { 2594 // FIXME: non-glvalue vector reads are not modelled. 2595 Bldr.generateNode(A, Node, state, nullptr); 2596 } else { 2597 llvm_unreachable("Array subscript should be an lValue when not \ 2598a vector and not a forbidden lvalue type"); 2599 } 2600 } 2601 2602 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this); 2603} 2604 2605/// VisitMemberExpr - Transfer function for member expressions. 2606void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 2607 ExplodedNodeSet &Dst) { 2608 // FIXME: Prechecks eventually go in ::Visit(). 2609 ExplodedNodeSet CheckedSet; 2610 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this); 2611 2612 ExplodedNodeSet EvalSet; 2613 ValueDecl *Member = M->getMemberDecl(); 2614 2615 // Handle static member variables and enum constants accessed via 2616 // member syntax. 2617 if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) { 2618 for (const auto I : CheckedSet) 2619 VisitCommonDeclRefExpr(M, Member, I, EvalSet); 2620 } else { 2621 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx); 2622 ExplodedNodeSet Tmp; 2623 2624 for (const auto I : CheckedSet) { 2625 ProgramStateRef state = I->getState(); 2626 const LocationContext *LCtx = I->getLocationContext(); 2627 Expr *BaseExpr = M->getBase(); 2628 2629 // Handle C++ method calls. 2630 if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) { 2631 if (MD->isInstance()) 2632 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); 2633 2634 SVal MDVal = svalBuilder.getFunctionPointer(MD); 2635 state = state->BindExpr(M, LCtx, MDVal); 2636 2637 Bldr.generateNode(M, I, state); 2638 continue; 2639 } 2640 2641 // Handle regular struct fields / member variables. 2642 const SubRegion *MR = nullptr; 2643 state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr, 2644 /*Result=*/nullptr, 2645 /*OutRegionWithAdjustments=*/&MR); 2646 SVal baseExprVal = 2647 MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx); 2648 2649 const auto *field = cast<FieldDecl>(Member); 2650 SVal L = state->getLValue(field, baseExprVal); 2651 2652 if (M->isGLValue() || M->getType()->isArrayType()) { 2653 // We special-case rvalues of array type because the analyzer cannot 2654 // reason about them, since we expect all regions to be wrapped in Locs. 2655 // We instead treat these as lvalues and assume that they will decay to 2656 // pointers as soon as they are used. 2657 if (!M->isGLValue()) { 2658 assert(M->getType()->isArrayType()); 2659 const auto *PE = 2660 dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M)); 2661 if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) { 2662 llvm_unreachable("should always be wrapped in ArrayToPointerDecay"); 2663 } 2664 } 2665 2666 if (field->getType()->isReferenceType()) { 2667 if (const MemRegion *R = L.getAsRegion()) 2668 L = state->getSVal(R); 2669 else 2670 L = UnknownVal(); 2671 } 2672 2673 Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr, 2674 ProgramPoint::PostLValueKind); 2675 } else { 2676 Bldr.takeNodes(I); 2677 evalLoad(Tmp, M, M, I, state, L); 2678 Bldr.addNodes(Tmp); 2679 } 2680 } 2681 } 2682 2683 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this); 2684} 2685 2686void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred, 2687 ExplodedNodeSet &Dst) { 2688 ExplodedNodeSet AfterPreSet; 2689 getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this); 2690 2691 // For now, treat all the arguments to C11 atomics as escaping. 2692 // FIXME: Ideally we should model the behavior of the atomics precisely here. 2693 2694 ExplodedNodeSet AfterInvalidateSet; 2695 StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx); 2696 2697 for (const auto I : AfterPreSet) { 2698 ProgramStateRef State = I->getState(); 2699 const LocationContext *LCtx = I->getLocationContext(); 2700 2701 SmallVector<SVal, 8> ValuesToInvalidate; 2702 for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) { 2703 const Expr *SubExpr = AE->getSubExprs()[SI]; 2704 SVal SubExprVal = State->getSVal(SubExpr, LCtx); 2705 ValuesToInvalidate.push_back(SubExprVal); 2706 } 2707 2708 State = State->invalidateRegions(ValuesToInvalidate, AE, 2709 currBldrCtx->blockCount(), 2710 LCtx, 2711 /*CausedByPointerEscape*/true, 2712 /*Symbols=*/nullptr); 2713 2714 SVal ResultVal = UnknownVal(); 2715 State = State->BindExpr(AE, LCtx, ResultVal); 2716 Bldr.generateNode(AE, I, State, nullptr, 2717 ProgramPoint::PostStmtKind); 2718 } 2719 2720 getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this); 2721} 2722 2723// A value escapes in four possible cases: 2724// (1) We are binding to something that is not a memory region. 2725// (2) We are binding to a MemRegion that does not have stack storage. 2726// (3) We are binding to a top-level parameter region with a non-trivial 2727// destructor. We won't see the destructor during analysis, but it's there. 2728// (4) We are binding to a MemRegion with stack storage that the store 2729// does not understand. 2730ProgramStateRef ExprEngine::processPointerEscapedOnBind( 2731 ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals, 2732 const LocationContext *LCtx, PointerEscapeKind Kind, 2733 const CallEvent *Call) { 2734 SmallVector<SVal, 8> Escaped; 2735 for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) { 2736 // Cases (1) and (2). 2737 const MemRegion *MR = LocAndVal.first.getAsRegion(); 2738 if (!MR || !MR->hasStackStorage()) { 2739 Escaped.push_back(LocAndVal.second); 2740 continue; 2741 } 2742 2743 // Case (3). 2744 if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion())) 2745 if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame()) 2746 if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl()) 2747 if (!RD->hasTrivialDestructor()) { 2748 Escaped.push_back(LocAndVal.second); 2749 continue; 2750 } 2751 2752 // Case (4): in order to test that, generate a new state with the binding 2753 // added. If it is the same state, then it escapes (since the store cannot 2754 // represent the binding). 2755 // Do this only if we know that the store is not supposed to generate the 2756 // same state. 2757 SVal StoredVal = State->getSVal(MR); 2758 if (StoredVal != LocAndVal.second) 2759 if (State == 2760 (State->bindLoc(loc::MemRegionVal(MR), LocAndVal.second, LCtx))) 2761 Escaped.push_back(LocAndVal.second); 2762 } 2763 2764 if (Escaped.empty()) 2765 return State; 2766 2767 return escapeValues(State, Escaped, Kind, Call); 2768} 2769 2770ProgramStateRef 2771ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc, 2772 SVal Val, const LocationContext *LCtx) { 2773 std::pair<SVal, SVal> LocAndVal(Loc, Val); 2774 return processPointerEscapedOnBind(State, LocAndVal, LCtx, PSK_EscapeOnBind, 2775 nullptr); 2776} 2777 2778ProgramStateRef 2779ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, 2780 const InvalidatedSymbols *Invalidated, 2781 ArrayRef<const MemRegion *> ExplicitRegions, 2782 const CallEvent *Call, 2783 RegionAndSymbolInvalidationTraits &ITraits) { 2784 if (!Invalidated || Invalidated->empty()) 2785 return State; 2786 2787 if (!Call) 2788 return getCheckerManager().runCheckersForPointerEscape(State, 2789 *Invalidated, 2790 nullptr, 2791 PSK_EscapeOther, 2792 &ITraits); 2793 2794 // If the symbols were invalidated by a call, we want to find out which ones 2795 // were invalidated directly due to being arguments to the call. 2796 InvalidatedSymbols SymbolsDirectlyInvalidated; 2797 for (const auto I : ExplicitRegions) { 2798 if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>()) 2799 SymbolsDirectlyInvalidated.insert(R->getSymbol()); 2800 } 2801 2802 InvalidatedSymbols SymbolsIndirectlyInvalidated; 2803 for (const auto &sym : *Invalidated) { 2804 if (SymbolsDirectlyInvalidated.count(sym)) 2805 continue; 2806 SymbolsIndirectlyInvalidated.insert(sym); 2807 } 2808 2809 if (!SymbolsDirectlyInvalidated.empty()) 2810 State = getCheckerManager().runCheckersForPointerEscape(State, 2811 SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits); 2812 2813 // Notify about the symbols that get indirectly invalidated by the call. 2814 if (!SymbolsIndirectlyInvalidated.empty()) 2815 State = getCheckerManager().runCheckersForPointerEscape(State, 2816 SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits); 2817 2818 return State; 2819} 2820 2821/// evalBind - Handle the semantics of binding a value to a specific location. 2822/// This method is used by evalStore and (soon) VisitDeclStmt, and others. 2823void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, 2824 ExplodedNode *Pred, 2825 SVal location, SVal Val, 2826 bool atDeclInit, const ProgramPoint *PP) { 2827 const LocationContext *LC = Pred->getLocationContext(); 2828 PostStmt PS(StoreE, LC); 2829 if (!PP) 2830 PP = &PS; 2831 2832 // Do a previsit of the bind. 2833 ExplodedNodeSet CheckedSet; 2834 getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, 2835 StoreE, *this, *PP); 2836 2837 StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx); 2838 2839 // If the location is not a 'Loc', it will already be handled by 2840 // the checkers. There is nothing left to do. 2841 if (!location.getAs<Loc>()) { 2842 const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr, 2843 /*tag*/nullptr); 2844 ProgramStateRef state = Pred->getState(); 2845 state = processPointerEscapedOnBind(state, location, Val, LC); 2846 Bldr.generateNode(L, state, Pred); 2847 return; 2848 } 2849 2850 for (const auto PredI : CheckedSet) { 2851 ProgramStateRef state = PredI->getState(); 2852 2853 state = processPointerEscapedOnBind(state, location, Val, LC); 2854 2855 // When binding the value, pass on the hint that this is a initialization. 2856 // For initializations, we do not need to inform clients of region 2857 // changes. 2858 state = state->bindLoc(location.castAs<Loc>(), 2859 Val, LC, /* notifyChanges = */ !atDeclInit); 2860 2861 const MemRegion *LocReg = nullptr; 2862 if (Optional<loc::MemRegionVal> LocRegVal = 2863 location.getAs<loc::MemRegionVal>()) { 2864 LocReg = LocRegVal->getRegion(); 2865 } 2866 2867 const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr); 2868 Bldr.generateNode(L, state, PredI); 2869 } 2870} 2871 2872/// evalStore - Handle the semantics of a store via an assignment. 2873/// @param Dst The node set to store generated state nodes 2874/// @param AssignE The assignment expression if the store happens in an 2875/// assignment. 2876/// @param LocationE The location expression that is stored to. 2877/// @param state The current simulation state 2878/// @param location The location to store the value 2879/// @param Val The value to be stored 2880void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, 2881 const Expr *LocationE, 2882 ExplodedNode *Pred, 2883 ProgramStateRef state, SVal location, SVal Val, 2884 const ProgramPointTag *tag) { 2885 // Proceed with the store. We use AssignE as the anchor for the PostStore 2886 // ProgramPoint if it is non-NULL, and LocationE otherwise. 2887 const Expr *StoreE = AssignE ? AssignE : LocationE; 2888 2889 // Evaluate the location (checks for bad dereferences). 2890 ExplodedNodeSet Tmp; 2891 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false); 2892 2893 if (Tmp.empty()) 2894 return; 2895 2896 if (location.isUndef()) 2897 return; 2898 2899 for (const auto I : Tmp) 2900 evalBind(Dst, StoreE, I, location, Val, false); 2901} 2902 2903void ExprEngine::evalLoad(ExplodedNodeSet &Dst, 2904 const Expr *NodeEx, 2905 const Expr *BoundEx, 2906 ExplodedNode *Pred, 2907 ProgramStateRef state, 2908 SVal location, 2909 const ProgramPointTag *tag, 2910 QualType LoadTy) { 2911 assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc."); 2912 assert(NodeEx); 2913 assert(BoundEx); 2914 // Evaluate the location (checks for bad dereferences). 2915 ExplodedNodeSet Tmp; 2916 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true); 2917 if (Tmp.empty()) 2918 return; 2919 2920 StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx); 2921 if (location.isUndef()) 2922 return; 2923 2924 // Proceed with the load. 2925 for (const auto I : Tmp) { 2926 state = I->getState(); 2927 const LocationContext *LCtx = I->getLocationContext(); 2928 2929 SVal V = UnknownVal(); 2930 if (location.isValid()) { 2931 if (LoadTy.isNull()) 2932 LoadTy = BoundEx->getType(); 2933 V = state->getSVal(location.castAs<Loc>(), LoadTy); 2934 } 2935 2936 Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag, 2937 ProgramPoint::PostLoadKind); 2938 } 2939} 2940 2941void ExprEngine::evalLocation(ExplodedNodeSet &Dst, 2942 const Stmt *NodeEx, 2943 const Stmt *BoundEx, 2944 ExplodedNode *Pred, 2945 ProgramStateRef state, 2946 SVal location, 2947 bool isLoad) { 2948 StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx); 2949 // Early checks for performance reason. 2950 if (location.isUnknown()) { 2951 return; 2952 } 2953 2954 ExplodedNodeSet Src; 2955 BldrTop.takeNodes(Pred); 2956 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx); 2957 if (Pred->getState() != state) { 2958 // Associate this new state with an ExplodedNode. 2959 // FIXME: If I pass null tag, the graph is incorrect, e.g for 2960 // int *p; 2961 // p = 0; 2962 // *p = 0xDEADBEEF; 2963 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 2964 // instead "int *p" is noted as 2965 // "Variable 'p' initialized to a null pointer value" 2966 2967 static SimpleProgramPointTag tag(TagProviderName, "Location"); 2968 Bldr.generateNode(NodeEx, Pred, state, &tag); 2969 } 2970 ExplodedNodeSet Tmp; 2971 getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, 2972 NodeEx, BoundEx, *this); 2973 BldrTop.addNodes(Tmp); 2974} 2975 2976std::pair<const ProgramPointTag *, const ProgramPointTag*> 2977ExprEngine::geteagerlyAssumeBinOpBifurcationTags() { 2978 static SimpleProgramPointTag 2979 eagerlyAssumeBinOpBifurcationTrue(TagProviderName, 2980 "Eagerly Assume True"), 2981 eagerlyAssumeBinOpBifurcationFalse(TagProviderName, 2982 "Eagerly Assume False"); 2983 return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue, 2984 &eagerlyAssumeBinOpBifurcationFalse); 2985} 2986 2987void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, 2988 ExplodedNodeSet &Src, 2989 const Expr *Ex) { 2990 StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx); 2991 2992 for (const auto Pred : Src) { 2993 // Test if the previous node was as the same expression. This can happen 2994 // when the expression fails to evaluate to anything meaningful and 2995 // (as an optimization) we don't generate a node. 2996 ProgramPoint P = Pred->getLocation(); 2997 if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) { 2998 continue; 2999 } 3000 3001 ProgramStateRef state = Pred->getState(); 3002 SVal V = state->getSVal(Ex, Pred->getLocationContext()); 3003 Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>(); 3004 if (SEV && SEV->isExpression()) { 3005 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = 3006 geteagerlyAssumeBinOpBifurcationTags(); 3007 3008 ProgramStateRef StateTrue, StateFalse; 3009 std::tie(StateTrue, StateFalse) = state->assume(*SEV); 3010 3011 // First assume that the condition is true. 3012 if (StateTrue) { 3013 SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); 3014 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); 3015 Bldr.generateNode(Ex, Pred, StateTrue, tags.first); 3016 } 3017 3018 // Next, assume that the condition is false. 3019 if (StateFalse) { 3020 SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); 3021 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); 3022 Bldr.generateNode(Ex, Pred, StateFalse, tags.second); 3023 } 3024 } 3025 } 3026} 3027 3028void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, 3029 ExplodedNodeSet &Dst) { 3030 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 3031 // We have processed both the inputs and the outputs. All of the outputs 3032 // should evaluate to Locs. Nuke all of their values. 3033 3034 // FIXME: Some day in the future it would be nice to allow a "plug-in" 3035 // which interprets the inline asm and stores proper results in the 3036 // outputs. 3037 3038 ProgramStateRef state = Pred->getState(); 3039 3040 for (const Expr *O : A->outputs()) { 3041 SVal X = state->getSVal(O, Pred->getLocationContext()); 3042 assert(!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef. 3043 3044 if (Optional<Loc> LV = X.getAs<Loc>()) 3045 state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext()); 3046 } 3047 3048 Bldr.generateNode(A, Pred, state); 3049} 3050 3051void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, 3052 ExplodedNodeSet &Dst) { 3053 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 3054 Bldr.generateNode(A, Pred, Pred->getState()); 3055} 3056 3057//===----------------------------------------------------------------------===// 3058// Visualization. 3059//===----------------------------------------------------------------------===// 3060 3061#ifndef NDEBUG 3062namespace llvm { 3063 3064template<> 3065struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits { 3066 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} 3067 3068 static bool nodeHasBugReport(const ExplodedNode *N) { 3069 BugReporter &BR = static_cast<ExprEngine &>( 3070 N->getState()->getStateManager().getOwningEngine()).getBugReporter(); 3071 3072 const auto EQClasses = 3073 llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end()); 3074 3075 for (const auto &EQ : EQClasses) { 3076 for (const auto &I : EQ.getReports()) { 3077 const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get()); 3078 if (!PR) 3079 continue; 3080 const ExplodedNode *EN = PR->getErrorNode(); 3081 if (EN->getState() == N->getState() && 3082 EN->getLocation() == N->getLocation()) 3083 return true; 3084 } 3085 } 3086 return false; 3087 } 3088 3089 /// \p PreCallback: callback before break. 3090 /// \p PostCallback: callback after break. 3091 /// \p Stop: stop iteration if returns {@code true} 3092 /// \return Whether {@code Stop} ever returned {@code true}. 3093 static bool traverseHiddenNodes( 3094 const ExplodedNode *N, 3095 llvm::function_ref<void(const ExplodedNode *)> PreCallback, 3096 llvm::function_ref<void(const ExplodedNode *)> PostCallback, 3097 llvm::function_ref<bool(const ExplodedNode *)> Stop) { 3098 while (true) { 3099 PreCallback(N); 3100 if (Stop(N)) 3101 return true; 3102 3103 if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc())) 3104 break; 3105 PostCallback(N); 3106 3107 N = N->getFirstSucc(); 3108 } 3109 return false; 3110 } 3111 3112 static bool isNodeHidden(const ExplodedNode *N) { 3113 return N->isTrivial(); 3114 } 3115 3116 static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){ 3117 std::string Buf; 3118 llvm::raw_string_ostream Out(Buf); 3119 3120 const bool IsDot = true; 3121 const unsigned int Space = 1; 3122 ProgramStateRef State = N->getState(); 3123 3124 Out << "{ \"state_id\": " << State->getID() 3125 << ",\\l"; 3126 3127 Indent(Out, Space, IsDot) << "\"program_points\": [\\l"; 3128 3129 // Dump program point for all the previously skipped nodes. 3130 traverseHiddenNodes( 3131 N, 3132 [&](const ExplodedNode *OtherNode) { 3133 Indent(Out, Space + 1, IsDot) << "{ "; 3134 OtherNode->getLocation().printJson(Out, /*NL=*/"\\l"); 3135 Out << ", \"tag\": "; 3136 if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag()) 3137 Out << '\"' << Tag->getTagDescription() << "\""; 3138 else 3139 Out << "null"; 3140 Out << ", \"node_id\": " << OtherNode->getID() << 3141 ", \"is_sink\": " << OtherNode->isSink() << 3142 ", \"has_report\": " << nodeHasBugReport(OtherNode) << " }"; 3143 }, 3144 // Adds a comma and a new-line between each program point. 3145 [&](const ExplodedNode *) { Out << ",\\l"; }, 3146 [&](const ExplodedNode *) { return false; }); 3147 3148 Out << "\\l"; // Adds a new-line to the last program point. 3149 Indent(Out, Space, IsDot) << "],\\l"; 3150 3151 State->printDOT(Out, N->getLocationContext(), Space); 3152 3153 Out << "\\l}\\l"; 3154 return Out.str(); 3155 } 3156}; 3157 3158} // namespace llvm 3159#endif 3160 3161void ExprEngine::ViewGraph(bool trim) { 3162#ifndef NDEBUG 3163 std::string Filename = DumpGraph(trim); 3164 llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT); 3165#endif 3166 llvm::errs() << "Warning: viewing graph requires assertions" << "\n"; 3167} 3168 3169 3170void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) { 3171#ifndef NDEBUG 3172 std::string Filename = DumpGraph(Nodes); 3173 llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT); 3174#endif 3175 llvm::errs() << "Warning: viewing graph requires assertions" << "\n"; 3176} 3177 3178std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) { 3179#ifndef NDEBUG 3180 if (trim) { 3181 std::vector<const ExplodedNode *> Src; 3182 3183 // Iterate through the reports and get their nodes. 3184 for (BugReporter::EQClasses_iterator 3185 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 3186 const auto *R = 3187 dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get()); 3188 if (!R) 3189 continue; 3190 const auto *N = const_cast<ExplodedNode *>(R->getErrorNode()); 3191 Src.push_back(N); 3192 } 3193 return DumpGraph(Src, Filename); 3194 } else { 3195 return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false, 3196 /*Title=*/"Exploded Graph", 3197 /*Filename=*/std::string(Filename)); 3198 } 3199#else 3200 llvm::errs() << "Warning: dumping graph requires assertions" << "\n"; 3201 return ""; 3202#endif 3203} 3204 3205std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode*> Nodes, 3206 StringRef Filename) { 3207#ifndef NDEBUG 3208 std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes)); 3209 3210 if (!TrimmedG.get()) { 3211 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 3212 } else { 3213 return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine", 3214 /*ShortNames=*/false, 3215 /*Title=*/"Trimmed Exploded Graph", 3216 /*Filename=*/std::string(Filename)); 3217 } 3218#endif 3219 llvm::errs() << "Warning: dumping graph requires assertions" << "\n"; 3220 return ""; 3221} 3222 3223void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() { 3224 static int index = 0; 3225 return &index; 3226} 3227 3228void ExprEngine::anchor() { } 3229