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