clang  16.0.0git
CoreEngine.h
Go to the documentation of this file.
1 //===- CoreEngine.h - Path-Sensitive Dataflow Engine ------------*- C++ -*-===//
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.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
16 
17 #include "clang/AST/Stmt.h"
19 #include "clang/Analysis/CFG.h"
21 #include "clang/Basic/LLVM.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/Support/Casting.h"
29 #include <cassert>
30 #include <memory>
31 #include <utility>
32 #include <vector>
33 
34 namespace clang {
35 
36 class AnalyzerOptions;
37 class CXXBindTemporaryExpr;
38 class Expr;
39 class LabelDecl;
40 
41 namespace ento {
42 
43 class FunctionSummariesTy;
44 class ExprEngine;
45 
46 //===----------------------------------------------------------------------===//
47 /// CoreEngine - Implements the core logic of the graph-reachability
48 /// analysis. It traverses the CFG and generates the ExplodedGraph.
49 /// Program "states" are treated as opaque void pointers.
50 /// The template class CoreEngine (which subclasses CoreEngine)
51 /// provides the matching component to the engine that knows the actual types
52 /// for states. Note that this engine only dispatches to transfer functions
53 /// at the statement and block-level. The analyses themselves must implement
54 /// any transfer function logic and the sub-expression level (if any).
55 class CoreEngine {
56  friend class CommonNodeBuilder;
58  friend class ExprEngine;
60  friend class NodeBuilder;
61  friend struct NodeBuilderContext;
62  friend class SwitchNodeBuilder;
63 
64 public:
65  using BlocksExhausted =
66  std::vector<std::pair<BlockEdge, const ExplodedNode *>>;
67 
68  using BlocksAborted =
69  std::vector<std::pair<const CFGBlock *, const ExplodedNode *>>;
70 
71 private:
72  ExprEngine &ExprEng;
73 
74  /// G - The simulation graph. Each node is a (location,state) pair.
75  mutable ExplodedGraph G;
76 
77  /// WList - A set of queued nodes that need to be processed by the
78  /// worklist algorithm. It is up to the implementation of WList to decide
79  /// the order that nodes are processed.
80  std::unique_ptr<WorkList> WList;
81  std::unique_ptr<WorkList> CTUWList;
82 
83  /// BCounterFactory - A factory object for created BlockCounter objects.
84  /// These are used to record for key nodes in the ExplodedGraph the
85  /// number of times different CFGBlocks have been visited along a path.
86  BlockCounter::Factory BCounterFactory;
87 
88  /// The locations where we stopped doing work because we visited a location
89  /// too many times.
90  BlocksExhausted blocksExhausted;
91 
92  /// The locations where we stopped because the engine aborted analysis,
93  /// usually because it could not reason about something.
94  BlocksAborted blocksAborted;
95 
96  /// The information about functions shared by the whole translation unit.
97  /// (This data is owned by AnalysisConsumer.)
98  FunctionSummariesTy *FunctionSummaries;
99 
100  /// Add path tags with some useful data along the path when we see that
101  /// something interesting is happening. This field is the allocator for such
102  /// tags.
103  DataTag::Factory DataTags;
104 
105  void setBlockCounter(BlockCounter C);
106 
107  void generateNode(const ProgramPoint &Loc,
109  ExplodedNode *Pred);
110 
111  void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
112  void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
113  void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
114 
115  void HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred);
116 
117  void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
118 
119  void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
120  ExplodedNode *Pred);
121  void HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
122  const CFGBlock *B, ExplodedNode *Pred);
123 
124  /// Handle conditional logic for running static initializers.
125  void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
126  ExplodedNode *Pred);
127 
128  void HandleVirtualBaseBranch(const CFGBlock *B, ExplodedNode *Pred);
129 
130 private:
131  ExplodedNode *generateCallExitBeginNode(ExplodedNode *N,
132  const ReturnStmt *RS);
133 
134 public:
135  /// Construct a CoreEngine object to analyze the provided CFG.
136  CoreEngine(ExprEngine &exprengine,
138  AnalyzerOptions &Opts);
139 
140  CoreEngine(const CoreEngine &) = delete;
141  CoreEngine &operator=(const CoreEngine &) = delete;
142 
143  /// getGraph - Returns the exploded graph.
144  ExplodedGraph &getGraph() { return G; }
145 
146  /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
147  /// steps. Returns true if there is still simulation state on the worklist.
148  bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
149  ProgramStateRef InitState);
150 
151  /// Returns true if there is still simulation state on the worklist.
153  unsigned Steps,
154  ProgramStateRef InitState,
155  ExplodedNodeSet &Dst);
156 
157  /// Dispatch the work list item based on the given location information.
158  /// Use Pred parameter as the predecessor state.
160  const WorkListUnit& WU);
161 
162  // Functions for external checking of whether we have unfinished work
163  bool wasBlockAborted() const { return !blocksAborted.empty(); }
164  bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
165  bool hasWorkRemaining() const { return wasBlocksExhausted() ||
166  WList->hasWork() ||
167  wasBlockAborted(); }
168 
169  /// Inform the CoreEngine that a basic block was aborted because
170  /// it could not be completely analyzed.
171  void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
172  blocksAborted.push_back(std::make_pair(block, node));
173  }
174 
175  WorkList *getWorkList() const { return WList.get(); }
176  WorkList *getCTUWorkList() const { return CTUWList.get(); }
177 
178  BlocksExhausted::const_iterator blocks_exhausted_begin() const {
179  return blocksExhausted.begin();
180  }
181 
182  BlocksExhausted::const_iterator blocks_exhausted_end() const {
183  return blocksExhausted.end();
184  }
185 
186  BlocksAborted::const_iterator blocks_aborted_begin() const {
187  return blocksAborted.begin();
188  }
189 
190  BlocksAborted::const_iterator blocks_aborted_end() const {
191  return blocksAborted.end();
192  }
193 
194  /// Enqueue the given set of nodes onto the work list.
195  void enqueue(ExplodedNodeSet &Set);
196 
197  /// Enqueue nodes that were created as a result of processing
198  /// a statement onto the work list.
199  void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
200 
201  /// enqueue the nodes corresponding to the end of function onto the
202  /// end of path / work list.
203  void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS);
204 
205  /// Enqueue a single node created as a result of statement processing.
206  void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
207 
208  DataTag::Factory &getDataTags() { return DataTags; }
209 };
210 
211 // TODO: Turn into a class.
213  const CoreEngine &Eng;
214  const CFGBlock *Block;
216 
218  const LocationContext *L)
219  : Eng(E), Block(B), LC(L) {
220  assert(B);
221  }
222 
224  : NodeBuilderContext(E, B, N->getLocationContext()) {}
225 
226  /// Return the CFGBlock associated with this builder.
227  const CFGBlock *getBlock() const { return Block; }
228 
229  /// Returns the number of times the current basic block has been
230  /// visited on the exploded graph path.
231  unsigned blockCount() const {
232  return Eng.WList->getBlockCounter().getNumVisited(
233  LC->getStackFrame(),
234  Block->getBlockID());
235  }
236 };
237 
238 /// \class NodeBuilder
239 /// This is the simplest builder which generates nodes in the
240 /// ExplodedGraph.
241 ///
242 /// The main benefit of the builder is that it automatically tracks the
243 /// frontier nodes (or destination set). This is the set of nodes which should
244 /// be propagated to the next step / builder. They are the nodes which have been
245 /// added to the builder (either as the input node set or as the newly
246 /// constructed nodes) but did not have any outgoing transitions added.
247 class NodeBuilder {
248  virtual void anchor();
249 
250 protected:
252 
253  /// Specifies if the builder results have been finalized. For example, if it
254  /// is set to false, autotransitions are yet to be generated.
255  bool Finalized;
256 
257  bool HasGeneratedNodes = false;
258 
259  /// The frontier set - a set of nodes which need to be propagated after
260  /// the builder dies.
262 
263  /// Checks if the results are ready.
264  virtual bool checkResults() {
265  return Finalized;
266  }
267 
269  for (const auto I : Frontier)
270  if (I->isSink())
271  return false;
272  return true;
273  }
274 
275  /// Allow subclasses to finalize results before result_begin() is executed.
276  virtual void finalizeResults() {}
277 
280  ExplodedNode *Pred,
281  bool MarkAsSink = false);
282 
283 public:
285  const NodeBuilderContext &Ctx, bool F = true)
286  : C(Ctx), Finalized(F), Frontier(DstSet) {
287  Frontier.Add(SrcNode);
288  }
289 
291  const NodeBuilderContext &Ctx, bool F = true)
292  : C(Ctx), Finalized(F), Frontier(DstSet) {
293  Frontier.insert(SrcSet);
294  assert(hasNoSinksInFrontier());
295  }
296 
297  virtual ~NodeBuilder() = default;
298 
299  /// Generates a node in the ExplodedGraph.
302  ExplodedNode *Pred) {
303  return generateNodeImpl(
304  PP, State, Pred,
305  /*MarkAsSink=*/State->isPosteriorlyOverconstrained());
306  }
307 
308  /// Generates a sink in the ExplodedGraph.
309  ///
310  /// When a node is marked as sink, the exploration from the node is stopped -
311  /// the node becomes the last node on the path and certain kinds of bugs are
312  /// suppressed.
315  ExplodedNode *Pred) {
316  return generateNodeImpl(PP, State, Pred, true);
317  }
318 
320  finalizeResults();
321  assert(checkResults());
322  return Frontier;
323  }
324 
326 
327  /// Iterators through the results frontier.
329  finalizeResults();
330  assert(checkResults());
331  return Frontier.begin();
332  }
333 
335  finalizeResults();
336  return Frontier.end();
337  }
338 
339  const NodeBuilderContext &getContext() { return C; }
341 
342  void takeNodes(const ExplodedNodeSet &S) {
343  for (const auto I : S)
344  Frontier.erase(I);
345  }
346 
348  void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); }
350 };
351 
352 /// \class NodeBuilderWithSinks
353 /// This node builder keeps track of the generated sink nodes.
355  void anchor() override;
356 
357 protected:
360 
361 public:
363  const NodeBuilderContext &Ctx, ProgramPoint &L)
364  : NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
365 
367  ExplodedNode *Pred,
368  const ProgramPointTag *Tag = nullptr) {
369  const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
370  return NodeBuilder::generateNode(LocalLoc, State, Pred);
371  }
372 
374  const ProgramPointTag *Tag = nullptr) {
375  const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
376  ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred);
377  if (N && N->isSink())
378  sinksGenerated.push_back(N);
379  return N;
380  }
381 
383  return sinksGenerated;
384  }
385 };
386 
387 /// \class StmtNodeBuilder
388 /// This builder class is useful for generating nodes that resulted from
389 /// visiting a statement. The main difference from its parent NodeBuilder is
390 /// that it creates a statement specific ProgramPoint.
392  NodeBuilder *EnclosingBldr;
393 
394 public:
395  /// Constructs a StmtNodeBuilder. If the builder is going to process
396  /// nodes currently owned by another builder(with larger scope), use
397  /// Enclosing builder to transfer ownership.
399  const NodeBuilderContext &Ctx,
400  NodeBuilder *Enclosing = nullptr)
401  : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
402  if (EnclosingBldr)
403  EnclosingBldr->takeNodes(SrcNode);
404  }
405 
407  const NodeBuilderContext &Ctx,
408  NodeBuilder *Enclosing = nullptr)
409  : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
410  if (EnclosingBldr)
411  for (const auto I : SrcSet)
412  EnclosingBldr->takeNodes(I);
413  }
414 
415  ~StmtNodeBuilder() override;
416 
419 
421  ExplodedNode *Pred,
422  ProgramStateRef St,
423  const ProgramPointTag *tag = nullptr,
426  Pred->getLocationContext(), tag);
427  return NodeBuilder::generateNode(L, St, Pred);
428  }
429 
431  ExplodedNode *Pred,
432  ProgramStateRef St,
433  const ProgramPointTag *tag = nullptr,
436  Pred->getLocationContext(), tag);
437  return NodeBuilder::generateSink(L, St, Pred);
438  }
439 };
440 
441 /// BranchNodeBuilder is responsible for constructing the nodes
442 /// corresponding to the two branches of the if statement - true and false.
444  const CFGBlock *DstT;
445  const CFGBlock *DstF;
446 
447  bool InFeasibleTrue;
448  bool InFeasibleFalse;
449 
450  void anchor() override;
451 
452 public:
454  const NodeBuilderContext &C,
455  const CFGBlock *dstT, const CFGBlock *dstF)
456  : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
457  InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
458  // The branch node builder does not generate autotransitions.
459  // If there are no successors it means that both branches are infeasible.
460  takeNodes(SrcNode);
461  }
462 
464  const NodeBuilderContext &C,
465  const CFGBlock *dstT, const CFGBlock *dstF)
466  : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
467  InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
468  takeNodes(SrcSet);
469  }
470 
472  ExplodedNode *Pred);
473 
474  const CFGBlock *getTargetBlock(bool branch) const {
475  return branch ? DstT : DstF;
476  }
477 
478  void markInfeasible(bool branch) {
479  if (branch)
480  InFeasibleTrue = true;
481  else
482  InFeasibleFalse = true;
483  }
484 
485  bool isFeasible(bool branch) {
486  return branch ? !InFeasibleTrue : !InFeasibleFalse;
487  }
488 };
489 
491  CoreEngine& Eng;
492  const CFGBlock *Src;
493  const CFGBlock &DispatchBlock;
494  const Expr *E;
495  ExplodedNode *Pred;
496 
497 public:
499  const Expr *e, const CFGBlock *dispatch, CoreEngine* eng)
500  : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
501 
502  class iterator {
504 
506 
508 
509  public:
510  iterator &operator++() { ++I; return *this; }
511  bool operator!=(const iterator &X) const { return I != X.I; }
512 
513  const LabelDecl *getLabel() const {
514  return cast<LabelStmt>((*I)->getLabel())->getDecl();
515  }
516 
517  const CFGBlock *getBlock() const {
518  return *I;
519  }
520  };
521 
522  iterator begin() { return iterator(DispatchBlock.succ_begin()); }
523  iterator end() { return iterator(DispatchBlock.succ_end()); }
524 
525  ExplodedNode *generateNode(const iterator &I,
527  bool isSink = false);
528 
529  const Expr *getTarget() const { return E; }
530 
531  ProgramStateRef getState() const { return Pred->State; }
532 
534  return Pred->getLocationContext();
535  }
536 };
537 
539  CoreEngine& Eng;
540  const CFGBlock *Src;
541  const Expr *Condition;
542  ExplodedNode *Pred;
543 
544 public:
546  const Expr *condition, CoreEngine* eng)
547  : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
548 
549  class iterator {
550  friend class SwitchNodeBuilder;
551 
553 
555 
556  public:
557  iterator &operator++() { ++I; return *this; }
558  bool operator!=(const iterator &X) const { return I != X.I; }
559  bool operator==(const iterator &X) const { return I == X.I; }
560 
561  const CaseStmt *getCase() const {
562  return cast<CaseStmt>((*I)->getLabel());
563  }
564 
565  const CFGBlock *getBlock() const {
566  return *I;
567  }
568  };
569 
570  iterator begin() { return iterator(Src->succ_rbegin()+1); }
571  iterator end() { return iterator(Src->succ_rend()); }
572 
573  const SwitchStmt *getSwitch() const {
574  return cast<SwitchStmt>(Src->getTerminator());
575  }
576 
577  ExplodedNode *generateCaseStmtNode(const iterator &I,
579 
581  bool isSink = false);
582 
583  const Expr *getCondition() const { return Condition; }
584 
585  ProgramStateRef getState() const { return Pred->State; }
586 
588  return Pred->getLocationContext();
589  }
590 };
591 
592 } // namespace ento
593 
594 } // namespace clang
595 
596 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
clang::ento::CoreEngine::BlocksAborted
std::vector< std::pair< const CFGBlock *, const ExplodedNode * > > BlocksAborted
Definition: CoreEngine.h:69
clang::CFGBlock::getTerminator
CFGTerminator getTerminator() const
Definition: CFG.h:1050
clang::ento::StmtNodeBuilder::generateSink
ExplodedNode * generateSink(const Stmt *S, ExplodedNode *Pred, ProgramStateRef St, const ProgramPointTag *tag=nullptr, ProgramPoint::Kind K=ProgramPoint::PostStmtKind)
Definition: CoreEngine.h:430
clang::ento::SwitchNodeBuilder::SwitchNodeBuilder
SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, const Expr *condition, CoreEngine *eng)
Definition: CoreEngine.h:545
clang::ento::NodeBuilderWithSinks::NodeBuilderWithSinks
NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, ProgramPoint &L)
Definition: CoreEngine.h:362
clang::ento::CoreEngine::BlocksExhausted
std::vector< std::pair< BlockEdge, const ExplodedNode * > > BlocksExhausted
Definition: CoreEngine.h:66
clang::CaseStmt
CaseStmt - Represent a case statement.
Definition: Stmt.h:1603
clang::ProgramPoint::withTag
ProgramPoint withTag(const ProgramPointTag *tag) const
Create a new ProgramPoint object that is the same as the original except for using the specified tag ...
Definition: ProgramPoint.h:131
clang::ento::ExplodedNode::getLocationContext
const LocationContext * getLocationContext() const
Definition: ExplodedGraph.h:146
clang::ento::SwitchNodeBuilder::getLocationContext
const LocationContext * getLocationContext() const
Definition: CoreEngine.h:587
clang::ento::BranchNodeBuilder::getTargetBlock
const CFGBlock * getTargetBlock(bool branch) const
Definition: CoreEngine.h:474
clang::LocationContext
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
Definition: AnalysisDeclContext.h:215
clang::LocationContext::getStackFrame
const StackFrameContext * getStackFrame() const
Definition: AnalysisDeclContext.cpp:463
clang::SwitchStmt
SwitchStmt - This represents a 'switch' stmt.
Definition: Stmt.h:2186
clang::CFGBlock::succ_rbegin
succ_reverse_iterator succ_rbegin()
Definition: CFG.h:962
clang::ento::WorkList
Definition: WorkList.h:60
clang::ento::ExplodedNodeSet::iterator
ImplTy::iterator iterator
Definition: ExplodedGraph.h:477
clang::ProgramPointTag
ProgramPoints can be "tagged" as representing points specific to a given analysis entity.
Definition: ProgramPoint.h:38
clang::ento::SwitchNodeBuilder::getCondition
const Expr * getCondition() const
Definition: CoreEngine.h:583
clang::CFGBlock::succ_begin
succ_iterator succ_begin()
Definition: CFG.h:957
clang::ento::SwitchNodeBuilder::iterator
Definition: CoreEngine.h:549
AnalysisDeclContext.h
llvm::SmallVector
Definition: LLVM.h:38
clang::ento::NodeBuilder::iterator
ExplodedNodeSet::iterator iterator
Definition: CoreEngine.h:325
clang::ento::IndirectGotoNodeBuilder::getTarget
const Expr * getTarget() const
Definition: CoreEngine.h:529
clang::ento::IndirectGotoNodeBuilder::begin
iterator begin()
Definition: CoreEngine.h:522
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1076
clang::ento::IndirectGotoNodeBuilder::iterator::operator!=
bool operator!=(const iterator &X) const
Definition: CoreEngine.h:511
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:56
clang::ento::ExplodedNode
Definition: ExplodedGraph.h:65
clang::ento::CoreEngine::EndOfFunctionNodeBuilder
friend class EndOfFunctionNodeBuilder
Definition: CoreEngine.h:57
clang::ento::NodeBuilderContext::LC
const LocationContext * LC
Definition: CoreEngine.h:215
ProgramState_Fwd.h
clang::ento::CoreEngine::CoreEngine
CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts)
Construct a CoreEngine object to analyze the provided CFG.
Definition: CoreEngine.cpp:75
clang::ento::StmtNodeBuilder::StmtNodeBuilder
StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, NodeBuilder *Enclosing=nullptr)
Constructs a StmtNodeBuilder.
Definition: CoreEngine.h:398
clang::ento::ExplodedNodeSet::Add
void Add(ExplodedNode *N)
Definition: ExplodedGraph.h:473
clang::ento::WorkListUnit
Definition: WorkList.h:27
clang::ento::BranchNodeBuilder
BranchNodeBuilder is responsible for constructing the nodes corresponding to the two branches of the ...
Definition: CoreEngine.h:443
clang::tooling::X
static ToolExecutorPluginRegistry::Add< AllTUsToolExecutorPlugin > X("all-TUs", "Runs FrontendActions on all TUs in the compilation database. " "Tool results are stored in memory.")
clang::ento::StmtNodeBuilder
Definition: CoreEngine.h:391
clang::ento::CoreEngine::blocks_exhausted_end
BlocksExhausted::const_iterator blocks_exhausted_end() const
Definition: CoreEngine.h:182
clang::ento::StmtNodeBuilder::StmtNodeBuilder
StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, NodeBuilder *Enclosing=nullptr)
Definition: CoreEngine.h:406
clang::CFGBlock::const_succ_iterator
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:933
clang::ento::NodeBuilderContext::Block
const CFGBlock * Block
Definition: CoreEngine.h:214
clang::ento::NodeBuilderContext::NodeBuilderContext
NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
Definition: CoreEngine.h:223
clang::ento::IndirectGotoNodeBuilder::IndirectGotoNodeBuilder
IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, const Expr *e, const CFGBlock *dispatch, CoreEngine *eng)
Definition: CoreEngine.h:498
clang::ento::CoreEngine::CommonNodeBuilder
friend class CommonNodeBuilder
Definition: CoreEngine.h:56
BlockCounter.h
clang::ento::NodeBuilder::Frontier
ExplodedNodeSet & Frontier
The frontier set - a set of nodes which need to be propagated after the builder dies.
Definition: CoreEngine.h:261
clang::ento::CoreEngine::addAbortedBlock
void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block)
Inform the CoreEngine that a basic block was aborted because it could not be completely analyzed.
Definition: CoreEngine.h:171
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:578
clang::ento::SwitchNodeBuilder::getSwitch
const SwitchStmt * getSwitch() const
Definition: CoreEngine.h:573
clang::ento::NodeBuilder::takeNodes
void takeNodes(const ExplodedNodeSet &S)
Definition: CoreEngine.h:342
clang::ento::NodeBuilder::Finalized
bool Finalized
Specifies if the builder results have been finalized.
Definition: CoreEngine.h:255
clang::ento::NodeBuilder::end
iterator end()
Definition: CoreEngine.h:334
clang::ento::CoreEngine::blocks_exhausted_begin
BlocksExhausted::const_iterator blocks_exhausted_begin() const
Definition: CoreEngine.h:178
clang::ento::SwitchNodeBuilder::iterator::operator!=
bool operator!=(const iterator &X) const
Definition: CoreEngine.h:558
ProgramPoint.h
clang::ento::CoreEngine::dispatchWorkItem
void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)
Dispatch the work list item based on the given location information.
Definition: CoreEngine.cpp:182
clang::ento::NodeBuilder::finalizeResults
virtual void finalizeResults()
Allow subclasses to finalize results before result_begin() is executed.
Definition: CoreEngine.h:276
clang::ento::BranchNodeBuilder::generateNode
ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)
Definition: CoreEngine.cpp:664
clang::ento::NodeBuilder
Definition: CoreEngine.h:247
clang::CXXBindTemporaryExpr
Represents binding an expression to a temporary.
Definition: ExprCXX.h:1419
clang::ento::NodeBuilder::generateSink
ExplodedNode * generateSink(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred)
Generates a sink in the ExplodedGraph.
Definition: CoreEngine.h:313
clang::ento::BranchNodeBuilder::BranchNodeBuilder
BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, const NodeBuilderContext &C, const CFGBlock *dstT, const CFGBlock *dstF)
Definition: CoreEngine.h:463
BugReporter.h
clang::ento::CoreEngine::ExecuteWorkListWithInitialState
bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, ProgramStateRef InitState, ExplodedNodeSet &Dst)
Returns true if there is still simulation state on the worklist.
Definition: CoreEngine.cpp:225
clang::ento::ExplodedNode::isSink
bool isSink() const
Definition: ExplodedGraph.h:202
clang::ento::SwitchNodeBuilder::getState
ProgramStateRef getState() const
Definition: CoreEngine.h:585
clang::ento::NodeBuilderWithSinks::sinksGenerated
SmallVector< ExplodedNode *, 2 > sinksGenerated
Definition: CoreEngine.h:358
clang::ento::IndirectGotoNodeBuilder::end
iterator end()
Definition: CoreEngine.h:523
clang::ento::CoreEngine::enqueueStmtNode
void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)
Enqueue a single node created as a result of statement processing.
Definition: CoreEngine.cpp:543
clang::LabelDecl
Represents the declaration of a label.
Definition: Decl.h:496
clang::ento::NodeBuilder::getResults
const ExplodedNodeSet & getResults()
Definition: CoreEngine.h:319
clang::ento::ExplodedNodeSet::end
iterator end()
Definition: ExplodedGraph.h:495
clang::ento::NodeBuilderWithSinks::generateNode
ExplodedNode * generateNode(ProgramStateRef State, ExplodedNode *Pred, const ProgramPointTag *Tag=nullptr)
Definition: CoreEngine.h:366
clang::ento::NodeBuilder::generateNodeImpl
ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)
Definition: CoreEngine.cpp:635
clang::ento::NodeBuilder::hasNoSinksInFrontier
bool hasNoSinksInFrontier()
Definition: CoreEngine.h:268
clang::ento::NodeBuilder::addNodes
void addNodes(ExplodedNode *N)
Definition: CoreEngine.h:349
clang::ento::BlockCounter::Factory
Definition: BlockCounter.h:40
clang::ento::NodeBuilderContext::blockCount
unsigned blockCount() const
Returns the number of times the current basic block has been visited on the exploded graph path.
Definition: CoreEngine.h:231
clang::ento::IndirectGotoNodeBuilder
Definition: CoreEngine.h:490
clang::ento::BranchNodeBuilder::markInfeasible
void markInfeasible(bool branch)
Definition: CoreEngine.h:478
clang::ento::BranchNodeBuilder::BranchNodeBuilder
BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, const NodeBuilderContext &C, const CFGBlock *dstT, const CFGBlock *dstF)
Definition: CoreEngine.h:453
clang::ento::ExplodedGraph
Definition: ExplodedGraph.h:302
clang::ento::IndirectGotoNodeBuilder::iterator::getBlock
const CFGBlock * getBlock() const
Definition: CoreEngine.h:517
clang::ento::SwitchNodeBuilder
Definition: CoreEngine.h:538
clang::ento::CoreEngine
CoreEngine - Implements the core logic of the graph-reachability analysis.
Definition: CoreEngine.h:55
clang::ento::NodeBuilderWithSinks::getSinks
const SmallVectorImpl< ExplodedNode * > & getSinks() const
Definition: CoreEngine.h:382
clang::ento::NodeBuilder::~NodeBuilder
virtual ~NodeBuilder()=default
ExplodedGraph.h
clang::ento::IndirectGotoNodeBuilder::getLocationContext
const LocationContext * getLocationContext() const
Definition: CoreEngine.h:533
clang::ento::Loc
Definition: SVals.h:282
clang::ento::SwitchNodeBuilder::begin
iterator begin()
Definition: CoreEngine.h:570
clang::ento::NodeBuilder::getContext
const NodeBuilderContext & getContext()
Definition: CoreEngine.h:339
clang::BlockEntrance
Definition: ProgramPoint.h:224
clang::ento::NodeBuilderWithSinks::Location
ProgramPoint & Location
Definition: CoreEngine.h:359
clang::ento::BranchNodeBuilder::isFeasible
bool isFeasible(bool branch)
Definition: CoreEngine.h:485
clang::ento::StmtNodeBuilder::~StmtNodeBuilder
~StmtNodeBuilder() override
Definition: CoreEngine.cpp:656
clang::ento::NodeBuilder::checkResults
virtual bool checkResults()
Checks if the results are ready.
Definition: CoreEngine.h:264
clang::CFGBlock::succ_end
succ_iterator succ_end()
Definition: CFG.h:958
clang::ento::SwitchNodeBuilder::end
iterator end()
Definition: CoreEngine.h:571
clang::ento::NodeBuilder::HasGeneratedNodes
bool HasGeneratedNodes
Definition: CoreEngine.h:257
clang::ento::CoreEngine::enqueueEndOfFunction
void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS)
enqueue the nodes corresponding to the end of function onto the end of path / work list.
Definition: CoreEngine.cpp:618
clang::ento::CoreEngine::getCTUWorkList
WorkList * getCTUWorkList() const
Definition: CoreEngine.h:176
clang::ProgramPoint::Kind
Kind
Definition: ProgramPoint.h:60
clang::ento::FunctionSummariesTy
Definition: FunctionSummary.h:33
clang::ento::CoreEngine::hasWorkRemaining
bool hasWorkRemaining() const
Definition: CoreEngine.h:165
LLVM.h
clang::AnalyzerOptions
Stores options for the analyzer from the command line.
Definition: AnalyzerOptions.h:150
clang::CFGBlock::succ_rend
succ_reverse_iterator succ_rend()
Definition: CFG.h:963
clang::ento::NodeBuilderWithSinks::generateSink
ExplodedNode * generateSink(ProgramStateRef State, ExplodedNode *Pred, const ProgramPointTag *Tag=nullptr)
Definition: CoreEngine.h:373
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1147
clang::ento::NodeBuilderContext::NodeBuilderContext
NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, const LocationContext *L)
Definition: CoreEngine.h:217
clang::ProgramPoint::PostStmtKind
@ PostStmtKind
Definition: ProgramPoint.h:66
clang::ento::CoreEngine::blocks_aborted_begin
BlocksAborted::const_iterator blocks_aborted_begin() const
Definition: CoreEngine.h:186
clang::ento::IndirectGotoNodeBuilder::generateNode
ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:678
clang::ento::CoreEngine::wasBlocksExhausted
bool wasBlocksExhausted() const
Definition: CoreEngine.h:164
clang::ento::ExplodedNodeSet::begin
iterator begin()
Definition: ExplodedGraph.h:494
clang::ento::IndirectGotoNodeBuilder::iterator::operator++
iterator & operator++()
Definition: CoreEngine.h:510
clang::DeclStmt
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1303
clang::ento::ExprEngine
Definition: ExprEngine.h:123
clang::ento::CoreEngine::enqueue
void enqueue(ExplodedNodeSet &Set)
Enqueue the given set of nodes onto the work list.
Definition: CoreEngine.cpp:607
clang::ento::CoreEngine::getWorkList
WorkList * getWorkList() const
Definition: CoreEngine.h:175
clang::ento::IndirectGotoNodeBuilder::iterator::getLabel
const LabelDecl * getLabel() const
Definition: CoreEngine.h:513
clang::ento::SwitchNodeBuilder::iterator::operator++
iterator & operator++()
Definition: CoreEngine.h:557
clang::ento::CoreEngine::wasBlockAborted
bool wasBlockAborted() const
Definition: CoreEngine.h:163
clang::ento::NodeBuilder::C
const NodeBuilderContext & C
Definition: CoreEngine.h:251
WorkList.h
clang
Definition: CalledOnceCheck.h:17
clang::ento::NodeBuilder::takeNodes
void takeNodes(ExplodedNode *N)
Definition: CoreEngine.h:347
CFG.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:71
clang::ProgramPoint::getProgramPoint
static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K, const LocationContext *LC, const ProgramPointTag *tag)
Definition: ProgramPoint.cpp:22
clang::ento::NodeBuilder::generateNode
ExplodedNode * generateNode(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred)
Generates a node in the ExplodedGraph.
Definition: CoreEngine.h:300
clang::ento::CoreEngine::operator=
CoreEngine & operator=(const CoreEngine &)=delete
clang::DeclaratorContext::Condition
@ Condition
clang::ento::NodeBuilderContext::getBlock
const CFGBlock * getBlock() const
Return the CFGBlock associated with this builder.
Definition: CoreEngine.h:227
clang::ento::ExplodedNodeSet::insert
void insert(const ExplodedNodeSet &S)
Definition: ExplodedGraph.h:486
clang::ento::IndirectGotoNodeBuilder::iterator
Definition: CoreEngine.h:502
clang::ento::ExplodedNodeSet::erase
bool erase(ExplodedNode *N)
Definition: ExplodedGraph.h:482
clang::ento::NodeBuilderContext
Definition: CoreEngine.h:212
clang::CallEnter
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:629
clang::ento::BlockCounter
Definition: BlockCounter.h:29
clang::BlockEdge
Definition: ProgramPoint.h:502
clang::ento::NodeBuilder::NodeBuilder
NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, bool F=true)
Definition: CoreEngine.h:290
clang::ento::CoreEngine::getDataTags
DataTag::Factory & getDataTags()
Definition: CoreEngine.h:208
clang::ento::CoreEngine::getGraph
ExplodedGraph & getGraph()
getGraph - Returns the exploded graph.
Definition: CoreEngine.h:144
clang::ento::NodeBuilderWithSinks
Definition: CoreEngine.h:354
clang::ento::SwitchNodeBuilder::generateDefaultCaseNode
ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:712
clang::CFGBlock::const_succ_reverse_iterator
AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator
Definition: CFG.h:935
clang::transformer::node
RangeSelector node(std::string ID)
Selects a node, including trailing semicolon, if any (for declarations and non-expression statements)...
Definition: RangeSelector.cpp:141
Stmt.h
clang::ento::NodeBuilder::addNodes
void addNodes(const ExplodedNodeSet &S)
Definition: CoreEngine.h:348
clang::ento::SwitchNodeBuilder::iterator::getCase
const CaseStmt * getCase() const
Definition: CoreEngine.h:561
llvm::SmallVectorImpl
Definition: Randstruct.h:18
clang::ento::CoreEngine::blocks_aborted_end
BlocksAborted::const_iterator blocks_aborted_end() const
Definition: CoreEngine.h:190
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::ento::NodeBuilderContext::Eng
const CoreEngine & Eng
Definition: CoreEngine.h:213
clang::ento::NodeBuilder::hasGeneratedNodes
bool hasGeneratedNodes()
Definition: CoreEngine.h:340
clang::ento::IndirectGotoNodeBuilder::getState
ProgramStateRef getState() const
Definition: CoreEngine.h:531
clang::ento::SwitchNodeBuilder::iterator::operator==
bool operator==(const iterator &X) const
Definition: CoreEngine.h:559
clang::ento::StmtNodeBuilder::generateNode
ExplodedNode * generateNode(const Stmt *S, ExplodedNode *Pred, ProgramStateRef St, const ProgramPointTag *tag=nullptr, ProgramPoint::Kind K=ProgramPoint::PostStmtKind)
Definition: CoreEngine.h:420
clang::ento::ExplodedNodeSet
Definition: ExplodedGraph.h:461
clang::ProgramPoint
Definition: ProgramPoint.h:58
clang::ento::DataTag::Factory
Definition: BugReporter.h:743
clang::ento::NodeBuilder::NodeBuilder
NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, bool F=true)
Definition: CoreEngine.h:284
clang::ento::SwitchNodeBuilder::generateCaseStmtNode
ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)
Definition: CoreEngine.cpp:697
clang::ento::CoreEngine::ExecuteWorkList
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
Definition: CoreEngine.cpp:88
llvm::IntrusiveRefCntPtr< const ProgramState >
clang::ReturnStmt
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Definition: Stmt.h:2796
clang::ento::SwitchNodeBuilder::iterator::getBlock
const CFGBlock * getBlock() const
Definition: CoreEngine.h:565
clang::ento::NodeBuilder::begin
iterator begin()
Iterators through the results frontier.
Definition: CoreEngine.h:328