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