1 //===- CoreEngine.cpp - Path-Sensitive Dataflow Engine --------------------===// 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 generic engine for intraprocedural, path-sensitive, 10 // dataflow analysis via graph reachability engine. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 15 #include "clang/AST/Expr.h" 16 #include "clang/AST/ExprCXX.h" 17 #include "clang/AST/Stmt.h" 18 #include "clang/AST/StmtCXX.h" 19 #include "clang/Analysis/AnalysisDeclContext.h" 20 #include "clang/Analysis/CFG.h" 21 #include "clang/Analysis/ProgramPoint.h" 22 #include "clang/Basic/LLVM.h" 23 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" 28 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 29 #include "llvm/ADT/Optional.h" 30 #include "llvm/ADT/STLExtras.h" 31 #include "llvm/ADT/Statistic.h" 32 #include "llvm/Support/Casting.h" 33 #include "llvm/Support/ErrorHandling.h" 34 #include <algorithm> 35 #include <cassert> 36 #include <memory> 37 #include <utility> 38 39 using namespace clang; 40 using namespace ento; 41 42 #define DEBUG_TYPE "CoreEngine" 43 44 STATISTIC(NumSteps, 45 "The # of steps executed."); 46 STATISTIC(NumReachedMaxSteps, 47 "The # of times we reached the max number of steps."); 48 STATISTIC(NumPathsExplored, 49 "The # of paths explored by the analyzer."); 50 51 //===----------------------------------------------------------------------===// 52 // Core analysis engine. 53 //===----------------------------------------------------------------------===// 54 55 static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) { 56 switch (Opts.getExplorationStrategy()) { 57 case ExplorationStrategyKind::DFS: 58 return WorkList::makeDFS(); 59 case ExplorationStrategyKind::BFS: 60 return WorkList::makeBFS(); 61 case ExplorationStrategyKind::BFSBlockDFSContents: 62 return WorkList::makeBFSBlockDFSContents(); 63 case ExplorationStrategyKind::UnexploredFirst: 64 return WorkList::makeUnexploredFirst(); 65 case ExplorationStrategyKind::UnexploredFirstQueue: 66 return WorkList::makeUnexploredFirstPriorityQueue(); 67 case ExplorationStrategyKind::UnexploredFirstLocationQueue: 68 return WorkList::makeUnexploredFirstPriorityLocationQueue(); 69 } 70 llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind"); 71 } 72 73 CoreEngine::CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS, 74 AnalyzerOptions &Opts) 75 : ExprEng(exprengine), WList(generateWorkList(Opts)), 76 BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {} 77 78 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. 79 bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, 80 ProgramStateRef InitState) { 81 if (G.num_roots() == 0) { // Initialize the analysis by constructing 82 // the root if none exists. 83 84 const CFGBlock *Entry = &(L->getCFG()->getEntry()); 85 86 assert(Entry->empty() && "Entry block must be empty."); 87 88 assert(Entry->succ_size() == 1 && "Entry block must have 1 successor."); 89 90 // Mark the entry block as visited. 91 FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(), 92 L->getDecl(), 93 L->getCFG()->getNumBlockIDs()); 94 95 // Get the solitary successor. 96 const CFGBlock *Succ = *(Entry->succ_begin()); 97 98 // Construct an edge representing the 99 // starting location in the function. 100 BlockEdge StartLoc(Entry, Succ, L); 101 102 // Set the current block counter to being empty. 103 WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); 104 105 if (!InitState) 106 InitState = ExprEng.getInitialState(L); 107 108 bool IsNew; 109 ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew); 110 assert(IsNew); 111 G.addRoot(Node); 112 113 NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node); 114 ExplodedNodeSet DstBegin; 115 ExprEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc); 116 117 enqueue(DstBegin); 118 } 119 120 // Check if we have a steps limit 121 bool UnlimitedSteps = Steps == 0; 122 // Cap our pre-reservation in the event that the user specifies 123 // a very large number of maximum steps. 124 const unsigned PreReservationCap = 4000000; 125 if(!UnlimitedSteps) 126 G.reserve(std::min(Steps,PreReservationCap)); 127 128 while (WList->hasWork()) { 129 if (!UnlimitedSteps) { 130 if (Steps == 0) { 131 NumReachedMaxSteps++; 132 break; 133 } 134 --Steps; 135 } 136 137 NumSteps++; 138 139 const WorkListUnit& WU = WList->dequeue(); 140 141 // Set the current block counter. 142 WList->setBlockCounter(WU.getBlockCounter()); 143 144 // Retrieve the node. 145 ExplodedNode *Node = WU.getNode(); 146 147 dispatchWorkItem(Node, Node->getLocation(), WU); 148 } 149 ExprEng.processEndWorklist(); 150 return WList->hasWork(); 151 } 152 153 void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 154 const WorkListUnit& WU) { 155 // Dispatch on the location type. 156 switch (Loc.getKind()) { 157 case ProgramPoint::BlockEdgeKind: 158 HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred); 159 break; 160 161 case ProgramPoint::BlockEntranceKind: 162 HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred); 163 break; 164 165 case ProgramPoint::BlockExitKind: 166 assert(false && "BlockExit location never occur in forward analysis."); 167 break; 168 169 case ProgramPoint::CallEnterKind: 170 HandleCallEnter(Loc.castAs<CallEnter>(), Pred); 171 break; 172 173 case ProgramPoint::CallExitBeginKind: 174 ExprEng.processCallExit(Pred); 175 break; 176 177 case ProgramPoint::EpsilonKind: { 178 assert(Pred->hasSinglePred() && 179 "Assume epsilon has exactly one predecessor by construction"); 180 ExplodedNode *PNode = Pred->getFirstPred(); 181 dispatchWorkItem(Pred, PNode->getLocation(), WU); 182 break; 183 } 184 default: 185 assert(Loc.getAs<PostStmt>() || 186 Loc.getAs<PostInitializer>() || 187 Loc.getAs<PostImplicitCall>() || 188 Loc.getAs<CallExitEnd>() || 189 Loc.getAs<LoopExit>() || 190 Loc.getAs<PostAllocatorCall>()); 191 HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred); 192 break; 193 } 194 } 195 196 bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 197 unsigned Steps, 198 ProgramStateRef InitState, 199 ExplodedNodeSet &Dst) { 200 bool DidNotFinish = ExecuteWorkList(L, Steps, InitState); 201 for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E; 202 ++I) { 203 Dst.Add(*I); 204 } 205 return DidNotFinish; 206 } 207 208 void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { 209 const CFGBlock *Blk = L.getDst(); 210 NodeBuilderContext BuilderCtx(*this, Blk, Pred); 211 212 // Mark this block as visited. 213 const LocationContext *LC = Pred->getLocationContext(); 214 FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(), 215 LC->getDecl(), 216 LC->getCFG()->getNumBlockIDs()); 217 218 // Display a prunable path note to the user if it's a virtual bases branch 219 // and we're taking the path that skips virtual base constructors. 220 if (L.getSrc()->getTerminator().isVirtualBaseBranch() && 221 L.getDst() == *L.getSrc()->succ_begin()) { 222 ProgramPoint P = L.withTag(getDataTags().make<NoteTag>( 223 [](BugReporterContext &, PathSensitiveBugReport &) -> std::string { 224 // TODO: Just call out the name of the most derived class 225 // when we know it. 226 return "Virtual base initialization skipped because " 227 "it has already been handled by the most derived class"; 228 }, 229 /*IsPrunable=*/true)); 230 // Perform the transition. 231 ExplodedNodeSet Dst; 232 NodeBuilder Bldr(Pred, Dst, BuilderCtx); 233 Pred = Bldr.generateNode(P, Pred->getState(), Pred); 234 if (!Pred) 235 return; 236 } 237 238 // Check if we are entering the EXIT block. 239 if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 240 assert(L.getLocationContext()->getCFG()->getExit().empty() && 241 "EXIT block cannot contain Stmts."); 242 243 // Get return statement.. 244 const ReturnStmt *RS = nullptr; 245 if (!L.getSrc()->empty()) { 246 CFGElement LastElement = L.getSrc()->back(); 247 if (Optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) { 248 RS = dyn_cast<ReturnStmt>(LastStmt->getStmt()); 249 } else if (Optional<CFGAutomaticObjDtor> AutoDtor = 250 LastElement.getAs<CFGAutomaticObjDtor>()) { 251 RS = dyn_cast<ReturnStmt>(AutoDtor->getTriggerStmt()); 252 } 253 } 254 255 // Process the final state transition. 256 ExprEng.processEndOfFunction(BuilderCtx, Pred, RS); 257 258 // This path is done. Don't enqueue any more nodes. 259 return; 260 } 261 262 // Call into the ExprEngine to process entering the CFGBlock. 263 ExplodedNodeSet dstNodes; 264 BlockEntrance BE(Blk, Pred->getLocationContext()); 265 NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); 266 ExprEng.processCFGBlockEntrance(L, nodeBuilder, Pred); 267 268 // Auto-generate a node. 269 if (!nodeBuilder.hasGeneratedNodes()) { 270 nodeBuilder.generateNode(Pred->State, Pred); 271 } 272 273 // Enqueue nodes onto the worklist. 274 enqueue(dstNodes); 275 } 276 277 void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 278 ExplodedNode *Pred) { 279 // Increment the block counter. 280 const LocationContext *LC = Pred->getLocationContext(); 281 unsigned BlockId = L.getBlock()->getBlockID(); 282 BlockCounter Counter = WList->getBlockCounter(); 283 Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(), 284 BlockId); 285 WList->setBlockCounter(Counter); 286 287 // Process the entrance of the block. 288 if (Optional<CFGElement> E = L.getFirstElement()) { 289 NodeBuilderContext Ctx(*this, L.getBlock(), Pred); 290 ExprEng.processCFGElement(*E, Pred, 0, &Ctx); 291 } 292 else 293 HandleBlockExit(L.getBlock(), Pred); 294 } 295 296 void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 297 if (const Stmt *Term = B->getTerminatorStmt()) { 298 switch (Term->getStmtClass()) { 299 default: 300 llvm_unreachable("Analysis for this terminator not implemented."); 301 302 case Stmt::CXXBindTemporaryExprClass: 303 HandleCleanupTemporaryBranch( 304 cast<CXXBindTemporaryExpr>(Term), B, Pred); 305 return; 306 307 // Model static initializers. 308 case Stmt::DeclStmtClass: 309 HandleStaticInit(cast<DeclStmt>(Term), B, Pred); 310 return; 311 312 case Stmt::BinaryOperatorClass: // '&&' and '||' 313 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 314 return; 315 316 case Stmt::BinaryConditionalOperatorClass: 317 case Stmt::ConditionalOperatorClass: 318 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 319 Term, B, Pred); 320 return; 321 322 // FIXME: Use constant-folding in CFG construction to simplify this 323 // case. 324 325 case Stmt::ChooseExprClass: 326 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 327 return; 328 329 case Stmt::CXXTryStmtClass: 330 // Generate a node for each of the successors. 331 // Our logic for EH analysis can certainly be improved. 332 for (CFGBlock::const_succ_iterator it = B->succ_begin(), 333 et = B->succ_end(); it != et; ++it) { 334 if (const CFGBlock *succ = *it) { 335 generateNode(BlockEdge(B, succ, Pred->getLocationContext()), 336 Pred->State, Pred); 337 } 338 } 339 return; 340 341 case Stmt::DoStmtClass: 342 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 343 return; 344 345 case Stmt::CXXForRangeStmtClass: 346 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred); 347 return; 348 349 case Stmt::ForStmtClass: 350 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 351 return; 352 353 case Stmt::SEHLeaveStmtClass: 354 case Stmt::ContinueStmtClass: 355 case Stmt::BreakStmtClass: 356 case Stmt::GotoStmtClass: 357 break; 358 359 case Stmt::IfStmtClass: 360 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 361 return; 362 363 case Stmt::IndirectGotoStmtClass: { 364 // Only 1 successor: the indirect goto dispatch block. 365 assert(B->succ_size() == 1); 366 367 IndirectGotoNodeBuilder 368 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 369 *(B->succ_begin()), this); 370 371 ExprEng.processIndirectGoto(builder); 372 return; 373 } 374 375 case Stmt::ObjCForCollectionStmtClass: 376 // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 377 // 378 // (1) inside a basic block, which represents the binding of the 379 // 'element' variable to a value. 380 // (2) in a terminator, which represents the branch. 381 // 382 // For (1), ExprEngine will bind a value (i.e., 0 or 1) indicating 383 // whether or not collection contains any more elements. We cannot 384 // just test to see if the element is nil because a container can 385 // contain nil elements. 386 HandleBranch(Term, Term, B, Pred); 387 return; 388 389 case Stmt::SwitchStmtClass: { 390 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 391 this); 392 393 ExprEng.processSwitch(builder); 394 return; 395 } 396 397 case Stmt::WhileStmtClass: 398 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 399 return; 400 401 case Stmt::GCCAsmStmtClass: 402 assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels"); 403 // TODO: Handle jumping to labels 404 return; 405 } 406 } 407 408 if (B->getTerminator().isVirtualBaseBranch()) { 409 HandleVirtualBaseBranch(B, Pred); 410 return; 411 } 412 413 assert(B->succ_size() == 1 && 414 "Blocks with no terminator should have at most 1 successor."); 415 416 generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 417 Pred->State, Pred); 418 } 419 420 void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) { 421 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred); 422 ExprEng.processCallEnter(BuilderCtx, CE, Pred); 423 } 424 425 void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 426 const CFGBlock * B, ExplodedNode *Pred) { 427 assert(B->succ_size() == 2); 428 NodeBuilderContext Ctx(*this, B, Pred); 429 ExplodedNodeSet Dst; 430 ExprEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()), 431 *(B->succ_begin() + 1)); 432 // Enqueue the new frontier onto the worklist. 433 enqueue(Dst); 434 } 435 436 void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, 437 const CFGBlock *B, 438 ExplodedNode *Pred) { 439 assert(B->succ_size() == 2); 440 NodeBuilderContext Ctx(*this, B, Pred); 441 ExplodedNodeSet Dst; 442 ExprEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()), 443 *(B->succ_begin() + 1)); 444 // Enqueue the new frontier onto the worklist. 445 enqueue(Dst); 446 } 447 448 void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B, 449 ExplodedNode *Pred) { 450 assert(B->succ_size() == 2); 451 NodeBuilderContext Ctx(*this, B, Pred); 452 ExplodedNodeSet Dst; 453 ExprEng.processStaticInitializer(DS, Ctx, Pred, Dst, 454 *(B->succ_begin()), *(B->succ_begin()+1)); 455 // Enqueue the new frontier onto the worklist. 456 enqueue(Dst); 457 } 458 459 void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 460 ExplodedNode *Pred) { 461 assert(B); 462 assert(!B->empty()); 463 464 if (StmtIdx == B->size()) 465 HandleBlockExit(B, Pred); 466 else { 467 NodeBuilderContext Ctx(*this, B, Pred); 468 ExprEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx); 469 } 470 } 471 472 void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B, 473 ExplodedNode *Pred) { 474 const LocationContext *LCtx = Pred->getLocationContext(); 475 if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>( 476 LCtx->getStackFrame()->getCallSite())) { 477 switch (CallerCtor->getConstructionKind()) { 478 case CXXConstructExpr::CK_NonVirtualBase: 479 case CXXConstructExpr::CK_VirtualBase: { 480 BlockEdge Loc(B, *B->succ_begin(), LCtx); 481 HandleBlockEdge(Loc, Pred); 482 return; 483 } 484 default: 485 break; 486 } 487 } 488 489 // We either don't see a parent stack frame because we're in the top frame, 490 // or the parent stack frame doesn't initialize our virtual bases. 491 BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx); 492 HandleBlockEdge(Loc, Pred); 493 } 494 495 /// generateNode - Utility method to generate nodes, hook up successors, 496 /// and add nodes to the worklist. 497 void CoreEngine::generateNode(const ProgramPoint &Loc, 498 ProgramStateRef State, 499 ExplodedNode *Pred) { 500 bool IsNew; 501 ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew); 502 503 if (Pred) 504 Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor. 505 else { 506 assert(IsNew); 507 G.addRoot(Node); // 'Node' has no predecessor. Make it a root. 508 } 509 510 // Only add 'Node' to the worklist if it was freshly generated. 511 if (IsNew) WList->enqueue(Node); 512 } 513 514 void CoreEngine::enqueueStmtNode(ExplodedNode *N, 515 const CFGBlock *Block, unsigned Idx) { 516 assert(Block); 517 assert(!N->isSink()); 518 519 // Check if this node entered a callee. 520 if (N->getLocation().getAs<CallEnter>()) { 521 // Still use the index of the CallExpr. It's needed to create the callee 522 // StackFrameContext. 523 WList->enqueue(N, Block, Idx); 524 return; 525 } 526 527 // Do not create extra nodes. Move to the next CFG element. 528 if (N->getLocation().getAs<PostInitializer>() || 529 N->getLocation().getAs<PostImplicitCall>()|| 530 N->getLocation().getAs<LoopExit>()) { 531 WList->enqueue(N, Block, Idx+1); 532 return; 533 } 534 535 if (N->getLocation().getAs<EpsilonPoint>()) { 536 WList->enqueue(N, Block, Idx); 537 return; 538 } 539 540 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) { 541 WList->enqueue(N, Block, Idx+1); 542 return; 543 } 544 545 // At this point, we know we're processing a normal statement. 546 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>(); 547 PostStmt Loc(CS.getStmt(), N->getLocationContext()); 548 549 if (Loc == N->getLocation().withTag(nullptr)) { 550 // Note: 'N' should be a fresh node because otherwise it shouldn't be 551 // a member of Deferred. 552 WList->enqueue(N, Block, Idx+1); 553 return; 554 } 555 556 bool IsNew; 557 ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew); 558 Succ->addPredecessor(N, G); 559 560 if (IsNew) 561 WList->enqueue(Succ, Block, Idx+1); 562 } 563 564 ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N, 565 const ReturnStmt *RS) { 566 // Create a CallExitBegin node and enqueue it. 567 const auto *LocCtx = cast<StackFrameContext>(N->getLocationContext()); 568 569 // Use the callee location context. 570 CallExitBegin Loc(LocCtx, RS); 571 572 bool isNew; 573 ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew); 574 Node->addPredecessor(N, G); 575 return isNew ? Node : nullptr; 576 } 577 578 void CoreEngine::enqueue(ExplodedNodeSet &Set) { 579 for (const auto I : Set) 580 WList->enqueue(I); 581 } 582 583 void CoreEngine::enqueue(ExplodedNodeSet &Set, 584 const CFGBlock *Block, unsigned Idx) { 585 for (const auto I : Set) 586 enqueueStmtNode(I, Block, Idx); 587 } 588 589 void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) { 590 for (auto I : Set) { 591 // If we are in an inlined call, generate CallExitBegin node. 592 if (I->getLocationContext()->getParent()) { 593 I = generateCallExitBeginNode(I, RS); 594 if (I) 595 WList->enqueue(I); 596 } else { 597 // TODO: We should run remove dead bindings here. 598 G.addEndOfPath(I); 599 NumPathsExplored++; 600 } 601 } 602 } 603 604 void NodeBuilder::anchor() {} 605 606 ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, 607 ProgramStateRef State, 608 ExplodedNode *FromN, 609 bool MarkAsSink) { 610 HasGeneratedNodes = true; 611 bool IsNew; 612 ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew); 613 N->addPredecessor(FromN, C.Eng.G); 614 Frontier.erase(FromN); 615 616 if (!IsNew) 617 return nullptr; 618 619 if (!MarkAsSink) 620 Frontier.Add(N); 621 622 return N; 623 } 624 625 void NodeBuilderWithSinks::anchor() {} 626 627 StmtNodeBuilder::~StmtNodeBuilder() { 628 if (EnclosingBldr) 629 for (const auto I : Frontier) 630 EnclosingBldr->addNodes(I); 631 } 632 633 void BranchNodeBuilder::anchor() {} 634 635 ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, 636 bool branch, 637 ExplodedNode *NodePred) { 638 // If the branch has been marked infeasible we should not generate a node. 639 if (!isFeasible(branch)) 640 return nullptr; 641 642 ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, 643 NodePred->getLocationContext()); 644 ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); 645 return Succ; 646 } 647 648 ExplodedNode* 649 IndirectGotoNodeBuilder::generateNode(const iterator &I, 650 ProgramStateRef St, 651 bool IsSink) { 652 bool IsNew; 653 ExplodedNode *Succ = 654 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 655 St, IsSink, &IsNew); 656 Succ->addPredecessor(Pred, Eng.G); 657 658 if (!IsNew) 659 return nullptr; 660 661 if (!IsSink) 662 Eng.WList->enqueue(Succ); 663 664 return Succ; 665 } 666 667 ExplodedNode* 668 SwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 669 ProgramStateRef St) { 670 bool IsNew; 671 ExplodedNode *Succ = 672 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), 673 St, false, &IsNew); 674 Succ->addPredecessor(Pred, Eng.G); 675 if (!IsNew) 676 return nullptr; 677 678 Eng.WList->enqueue(Succ); 679 return Succ; 680 } 681 682 ExplodedNode* 683 SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, 684 bool IsSink) { 685 // Get the block for the default case. 686 assert(Src->succ_rbegin() != Src->succ_rend()); 687 CFGBlock *DefaultBlock = *Src->succ_rbegin(); 688 689 // Sanity check for default blocks that are unreachable and not caught 690 // by earlier stages. 691 if (!DefaultBlock) 692 return nullptr; 693 694 bool IsNew; 695 ExplodedNode *Succ = 696 Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()), 697 St, IsSink, &IsNew); 698 Succ->addPredecessor(Pred, Eng.G); 699 700 if (!IsNew) 701 return nullptr; 702 703 if (!IsSink) 704 Eng.WList->enqueue(Succ); 705 706 return Succ; 707 } 708