clang  14.0.0git
ExplodedGraph.h
Go to the documentation of this file.
1 //===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- 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 the template classes ExplodedNode and ExplodedGraph,
10 // which represent a path-sensitive, intra-procedural "exploded graph."
11 // See "Precise interprocedural dataflow analysis via graph reachability"
12 // by Reps, Horwitz, and Sagiv
13 // (http://portal.acm.org/citation.cfm?id=199462) for the definition of an
14 // exploded graph.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
19 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
20 
24 #include "clang/Basic/LLVM.h"
28 #include "llvm/ADT/ArrayRef.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/DepthFirstIterator.h"
31 #include "llvm/ADT/FoldingSet.h"
32 #include "llvm/ADT/GraphTraits.h"
33 #include "llvm/ADT/Optional.h"
34 #include "llvm/ADT/STLExtras.h"
35 #include "llvm/ADT/SetVector.h"
36 #include "llvm/Support/Allocator.h"
37 #include "llvm/Support/Compiler.h"
38 #include <cassert>
39 #include <cstdint>
40 #include <memory>
41 #include <utility>
42 #include <vector>
43 
44 namespace clang {
45 
46 class CFG;
47 class Decl;
48 class Expr;
49 class ParentMap;
50 class Stmt;
51 
52 namespace ento {
53 
54 class ExplodedGraph;
55 
56 //===----------------------------------------------------------------------===//
57 // ExplodedGraph "implementation" classes. These classes are not typed to
58 // contain a specific kind of state. Typed-specialized versions are defined
59 // on top of these classes.
60 //===----------------------------------------------------------------------===//
61 
62 // ExplodedNode is not constified all over the engine because we need to add
63 // successors to it at any time after creating it.
64 
65 class ExplodedNode : public llvm::FoldingSetNode {
66  friend class BranchNodeBuilder;
67  friend class CoreEngine;
69  friend class ExplodedGraph;
71  friend class NodeBuilder;
72  friend class SwitchNodeBuilder;
73 
74  /// Efficiently stores a list of ExplodedNodes, or an optional flag.
75  ///
76  /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
77  /// for the case when there is only one node in the group. This is a fairly
78  /// common case in an ExplodedGraph, where most nodes have only one
79  /// predecessor and many have only one successor. It can also be used to
80  /// store a flag rather than a node list, which ExplodedNode uses to mark
81  /// whether a node is a sink. If the flag is set, the group is implicitly
82  /// empty and no nodes may be added.
83  class NodeGroup {
84  // Conceptually a discriminated union. If the low bit is set, the node is
85  // a sink. If the low bit is not set, the pointer refers to the storage
86  // for the nodes in the group.
87  // This is not a PointerIntPair in order to keep the storage type opaque.
88  uintptr_t P;
89 
90  public:
91  NodeGroup(bool Flag = false) : P(Flag) {
92  assert(getFlag() == Flag);
93  }
94 
95  ExplodedNode * const *begin() const;
96 
97  ExplodedNode * const *end() const;
98 
99  unsigned size() const;
100 
101  bool empty() const { return P == 0 || getFlag() != 0; }
102 
103  /// Adds a node to the list.
104  ///
105  /// The group must not have been created with its flag set.
106  void addNode(ExplodedNode *N, ExplodedGraph &G);
107 
108  /// Replaces the single node in this group with a new node.
109  ///
110  /// Note that this should only be used when you know the group was not
111  /// created with its flag set, and that the group is empty or contains
112  /// only a single node.
113  void replaceNode(ExplodedNode *node);
114 
115  /// Returns whether this group was created with its flag set.
116  bool getFlag() const {
117  return (P & 1);
118  }
119  };
120 
121  /// Location - The program location (within a function body) associated
122  /// with this node.
123  const ProgramPoint Location;
124 
125  /// State - The state associated with this node.
126  ProgramStateRef State;
127 
128  /// Preds - The predecessors of this node.
129  NodeGroup Preds;
130 
131  /// Succs - The successors of this node.
132  NodeGroup Succs;
133 
134  int64_t Id;
135 
136 public:
138  int64_t Id, bool IsSink)
139  : Location(loc), State(std::move(state)), Succs(IsSink), Id(Id) {
140  assert(isSink() == IsSink);
141  }
142 
143  /// getLocation - Returns the edge associated with the given node.
144  ProgramPoint getLocation() const { return Location; }
145 
147  return getLocation().getLocationContext();
148  }
149 
151  return getLocation().getStackFrame();
152  }
153 
154  const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
155 
156  CFG &getCFG() const { return *getLocationContext()->getCFG(); }
157 
158  const CFGBlock *getCFGBlock() const;
159 
160  const ParentMap &getParentMap() const {
161  return getLocationContext()->getParentMap();
162  }
163 
164  template <typename T>
165  T &getAnalysis() const {
166  return *getLocationContext()->getAnalysis<T>();
167  }
168 
169  const ProgramStateRef &getState() const { return State; }
170 
171  template <typename T>
172  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
173  return Location.getAs<T>();
174  }
175 
176  /// Get the value of an arbitrary expression at this node.
177  SVal getSVal(const Stmt *S) const {
178  return getState()->getSVal(S, getLocationContext());
179  }
180 
181  static void Profile(llvm::FoldingSetNodeID &ID,
182  const ProgramPoint &Loc,
183  const ProgramStateRef &state,
184  bool IsSink) {
185  ID.Add(Loc);
186  ID.AddPointer(state.get());
187  ID.AddBoolean(IsSink);
188  }
189 
190  void Profile(llvm::FoldingSetNodeID& ID) const {
191  // We avoid copy constructors by not using accessors.
192  Profile(ID, Location, State, isSink());
193  }
194 
195  /// addPredeccessor - Adds a predecessor to the current node, and
196  /// in tandem add this node as a successor of the other node.
198 
199  unsigned succ_size() const { return Succs.size(); }
200  unsigned pred_size() const { return Preds.size(); }
201  bool succ_empty() const { return Succs.empty(); }
202  bool pred_empty() const { return Preds.empty(); }
203 
204  bool isSink() const { return Succs.getFlag(); }
205 
206  bool hasSinglePred() const {
207  return (pred_size() == 1);
208  }
209 
211  return pred_empty() ? nullptr : *(pred_begin());
212  }
213 
214  const ExplodedNode *getFirstPred() const {
215  return const_cast<ExplodedNode*>(this)->getFirstPred();
216  }
217 
219  return succ_empty() ? nullptr : *(succ_begin());
220  }
221 
222  const ExplodedNode *getFirstSucc() const {
223  return const_cast<ExplodedNode*>(this)->getFirstSucc();
224  }
225 
226  // Iterators over successor and predecessor vertices.
227  using succ_iterator = ExplodedNode * const *;
228  using succ_range = llvm::iterator_range<succ_iterator>;
229 
230  using const_succ_iterator = const ExplodedNode * const *;
231  using const_succ_range = llvm::iterator_range<const_succ_iterator>;
232 
233  using pred_iterator = ExplodedNode * const *;
234  using pred_range = llvm::iterator_range<pred_iterator>;
235 
236  using const_pred_iterator = const ExplodedNode * const *;
237  using const_pred_range = llvm::iterator_range<const_pred_iterator>;
238 
239  pred_iterator pred_begin() { return Preds.begin(); }
240  pred_iterator pred_end() { return Preds.end(); }
241  pred_range preds() { return {Preds.begin(), Preds.end()}; }
242 
244  return const_cast<ExplodedNode*>(this)->pred_begin();
245  }
247  return const_cast<ExplodedNode*>(this)->pred_end();
248  }
249  const_pred_range preds() const { return {Preds.begin(), Preds.end()}; }
250 
251  succ_iterator succ_begin() { return Succs.begin(); }
252  succ_iterator succ_end() { return Succs.end(); }
253  succ_range succs() { return {Succs.begin(), Succs.end()}; }
254 
256  return const_cast<ExplodedNode*>(this)->succ_begin();
257  }
259  return const_cast<ExplodedNode*>(this)->succ_end();
260  }
261  const_succ_range succs() const { return {Succs.begin(), Succs.end()}; }
262 
263  int64_t getID() const { return Id; }
264 
265  /// The node is trivial if it has only one successor, only one predecessor,
266  /// it's predecessor has only one successor,
267  /// and its program state is the same as the program state of the previous
268  /// node.
269  /// Trivial nodes may be skipped while printing exploded graph.
270  bool isTrivial() const;
271 
272  /// If the node's program point corresponds to a statement, retrieve that
273  /// statement. Useful for figuring out where to put a warning or a note.
274  /// If the statement belongs to a body-farmed definition,
275  /// retrieve the call site for that definition.
276  const Stmt *getStmtForDiagnostics() const;
277 
278  /// Find the next statement that was executed on this node's execution path.
279  /// Useful for explaining control flow that follows the current node.
280  /// If the statement belongs to a body-farmed definition, retrieve the
281  /// call site for that definition.
282  const Stmt *getNextStmtForDiagnostics() const;
283 
284  /// Find the statement that was executed immediately before this node.
285  /// Useful when the node corresponds to a CFG block entrance.
286  /// If the statement belongs to a body-farmed definition, retrieve the
287  /// call site for that definition.
288  const Stmt *getPreviousStmtForDiagnostics() const;
289 
290  /// Find the statement that was executed at or immediately before this node.
291  /// Useful when any nearby statement will do.
292  /// If the statement belongs to a body-farmed definition, retrieve the
293  /// call site for that definition.
295 
296 private:
297  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
298  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
299 };
300 
301 using InterExplodedGraphMap =
302  llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
303 
305 protected:
306  friend class CoreEngine;
307 
308  // Type definitions.
309  using NodeVector = std::vector<ExplodedNode *>;
310 
311  /// The roots of the simulation graph. Usually there will be only
312  /// one, but clients are free to establish multiple subgraphs within a single
313  /// SimulGraph. Moreover, these subgraphs can often merge when paths from
314  /// different roots reach the same state at the same program location.
316 
317  /// The nodes in the simulation graph which have been
318  /// specially marked as the endpoint of an abstract simulation path.
320 
321  /// Nodes - The nodes in the graph.
322  llvm::FoldingSet<ExplodedNode> Nodes;
323 
324  /// BVC - Allocator and context for allocating nodes and their predecessor
325  /// and successor groups.
327 
328  /// NumNodes - The number of nodes in the graph.
329  int64_t NumNodes = 0;
330 
331  /// A list of recently allocated nodes that can potentially be recycled.
333 
334  /// A list of nodes that can be reused.
336 
337  /// Determines how often nodes are reclaimed.
338  ///
339  /// If this is 0, nodes will never be reclaimed.
340  unsigned ReclaimNodeInterval = 0;
341 
342  /// Counter to determine when to reclaim nodes.
343  unsigned ReclaimCounter;
344 
345 public:
346  ExplodedGraph();
347  ~ExplodedGraph();
348 
349  /// Retrieve the node associated with a (Location,State) pair,
350  /// where the 'Location' is a ProgramPoint in the CFG. If no node for
351  /// this pair exists, it is created. IsNew is set to true if
352  /// the node was freshly created.
354  bool IsSink = false,
355  bool* IsNew = nullptr);
356 
357  /// Create a node for a (Location, State) pair,
358  /// but don't store it for deduplication later. This
359  /// is useful when copying an already completed
360  /// ExplodedGraph for further processing.
363  int64_t Id,
364  bool IsSink = false);
365 
366  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
367  return std::make_unique<ExplodedGraph>();
368  }
369 
370  /// addRoot - Add an untyped node to the set of roots.
372  Roots.push_back(V);
373  return V;
374  }
375 
376  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
378  EndNodes.push_back(V);
379  return V;
380  }
381 
382  unsigned num_roots() const { return Roots.size(); }
383  unsigned num_eops() const { return EndNodes.size(); }
384 
385  bool empty() const { return NumNodes == 0; }
386  unsigned size() const { return NumNodes; }
387 
388  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
389 
390  // Iterators.
392  using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
393  using roots_iterator = NodeVector::iterator;
394  using const_roots_iterator = NodeVector::const_iterator;
395  using eop_iterator = NodeVector::iterator;
396  using const_eop_iterator = NodeVector::const_iterator;
397  using node_iterator = AllNodesTy::iterator;
398  using const_node_iterator = AllNodesTy::const_iterator;
399 
400  node_iterator nodes_begin() { return Nodes.begin(); }
401 
402  node_iterator nodes_end() { return Nodes.end(); }
403 
404  const_node_iterator nodes_begin() const { return Nodes.begin(); }
405 
406  const_node_iterator nodes_end() const { return Nodes.end(); }
407 
408  roots_iterator roots_begin() { return Roots.begin(); }
409 
410  roots_iterator roots_end() { return Roots.end(); }
411 
412  const_roots_iterator roots_begin() const { return Roots.begin(); }
413 
414  const_roots_iterator roots_end() const { return Roots.end(); }
415 
416  eop_iterator eop_begin() { return EndNodes.begin(); }
417 
418  eop_iterator eop_end() { return EndNodes.end(); }
419 
420  const_eop_iterator eop_begin() const { return EndNodes.begin(); }
421 
422  const_eop_iterator eop_end() const { return EndNodes.end(); }
423 
424  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
426 
427  using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
428 
429  /// Creates a trimmed version of the graph that only contains paths leading
430  /// to the given nodes.
431  ///
432  /// \param Nodes The nodes which must appear in the final graph. Presumably
433  /// these are end-of-path nodes (i.e. they have no successors).
434  /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
435  /// the returned graph.
436  /// \param[out] InverseMap An optional map from nodes in the returned graph to
437  /// nodes in this graph.
438  /// \returns The trimmed graph
439  std::unique_ptr<ExplodedGraph>
441  InterExplodedGraphMap *ForwardMap = nullptr,
442  InterExplodedGraphMap *InverseMap = nullptr) const;
443 
444  /// Enable tracking of recently allocated nodes for potential reclamation
445  /// when calling reclaimRecentlyAllocatedNodes().
446  void enableNodeReclamation(unsigned Interval) {
447  ReclaimCounter = ReclaimNodeInterval = Interval;
448  }
449 
450  /// Reclaim "uninteresting" nodes created since the last time this method
451  /// was called.
453 
454  /// Returns true if nodes for the given expression kind are always
455  /// kept around.
456  static bool isInterestingLValueExpr(const Expr *Ex);
457 
458 private:
459  bool shouldCollect(const ExplodedNode *node);
460  void collectNode(ExplodedNode *node);
461 };
462 
465  ImplTy Impl;
466 
467 public:
469  assert(N && !static_cast<ExplodedNode*>(N)->isSink());
470  Impl.insert(N);
471  }
472 
473  ExplodedNodeSet() = default;
474 
475  void Add(ExplodedNode *N) {
476  if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
477  }
478 
479  using iterator = ImplTy::iterator;
480  using const_iterator = ImplTy::const_iterator;
481 
482  unsigned size() const { return Impl.size(); }
483  bool empty() const { return Impl.empty(); }
484  bool erase(ExplodedNode *N) { return Impl.remove(N); }
485 
486  void clear() { Impl.clear(); }
487 
488  void insert(const ExplodedNodeSet &S) {
489  assert(&S != this);
490  if (empty())
491  Impl = S.Impl;
492  else
493  Impl.insert(S.begin(), S.end());
494  }
495 
496  iterator begin() { return Impl.begin(); }
497  iterator end() { return Impl.end(); }
498 
499  const_iterator begin() const { return Impl.begin(); }
500  const_iterator end() const { return Impl.end(); }
501 };
502 
503 } // namespace ento
504 
505 } // namespace clang
506 
507 // GraphTraits
508 
509 namespace llvm {
510  template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
514  using nodes_iterator = llvm::df_iterator<GraphTy>;
515 
516  static NodeRef getEntryNode(const GraphTy G) {
517  return *G->roots_begin();
518  }
519 
520  static bool predecessorOfTrivial(NodeRef N) {
521  return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
522  }
523 
525  if (predecessorOfTrivial(N))
526  return child_begin(*N->succ_begin());
527  return N->succ_begin();
528  }
529 
531  if (predecessorOfTrivial(N))
532  return child_end(N->getFirstSucc());
533  return N->succ_end();
534  }
535 
537  return df_begin(G);
538  }
539 
540  static nodes_iterator nodes_end(const GraphTy G) {
541  return df_end(G);
542  }
543  };
544 } // namespace llvm
545 
546 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
clang::ento::ExplodedNode::pred_begin
pred_iterator pred_begin()
Definition: ExplodedGraph.h:239
clang::ento::ExplodedGraph::eop_begin
eop_iterator eop_begin()
Definition: ExplodedGraph.h:416
clang::ento::ExplodedGraph::createUncachedNode
ExplodedNode * createUncachedNode(const ProgramPoint &L, ProgramStateRef State, int64_t Id, bool IsSink=false)
Create a node for a (Location, State) pair, but don't store it for deduplication later.
Definition: ExplodedGraph.cpp:431
clang::ento::ExplodedNode::const_pred_range
llvm::iterator_range< const_pred_iterator > const_pred_range
Definition: ExplodedGraph.h:237
llvm
Definition: Dominators.h:30
llvm::GraphTraits< clang::ento::ExplodedGraph * >::getEntryNode
static NodeRef getEntryNode(const GraphTy G)
Definition: ExplodedGraph.h:516
clang::ento::ExplodedNodeSet::ExplodedNodeSet
ExplodedNodeSet()=default
clang::ento::ExplodedNode::getLocationContext
const LocationContext * getLocationContext() const
Definition: ExplodedGraph.h:146
clang::LocationContext
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
Definition: AnalysisDeclContext.h:215
clang::ento::ExplodedGraph::roots_iterator
NodeVector::iterator roots_iterator
Definition: ExplodedGraph.h:393
clang::ento::ExplodedNode::succ_size
unsigned succ_size() const
Definition: ExplodedGraph.h:199
SVals.h
llvm::GraphTraits< clang::ento::ExplodedGraph * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: ExplodedGraph.h:530
clang::ento::ExplodedGraph::Nodes
llvm::FoldingSet< ExplodedNode > Nodes
Nodes - The nodes in the graph.
Definition: ExplodedGraph.h:322
clang::ento::ExplodedNode::preds
pred_range preds()
Definition: ExplodedGraph.h:241
llvm::GraphTraits< clang::ento::ExplodedGraph * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ExplodedGraph.h:524
clang::ento::ExplodedNodeSet::iterator
ImplTy::iterator iterator
Definition: ExplodedGraph.h:479
clang::ento::ExplodedNode::succ_end
succ_iterator succ_end()
Definition: ExplodedGraph.h:252
clang::ento::ExplodedGraph::const_eop_iterator
NodeVector::const_iterator const_eop_iterator
Definition: ExplodedGraph.h:396
AnalysisDeclContext.h
clang::ento::ExplodedGraph::eop_iterator
NodeVector::iterator eop_iterator
Definition: ExplodedGraph.h:395
clang::ento::ExplodedGraph::roots_begin
const_roots_iterator roots_begin() const
Definition: ExplodedGraph.h:412
clang::ento::ExplodedGraph::nodes_end
const_node_iterator nodes_end() const
Definition: ExplodedGraph.h:406
llvm::GraphTraits< clang::ento::ExplodedGraph * >::nodes_begin
static nodes_iterator nodes_begin(const GraphTy G)
Definition: ExplodedGraph.h:536
clang::ento::ExplodedNode::succs
const_succ_range succs() const
Definition: ExplodedGraph.h:261
clang::ento::ExplodedGraph::size
unsigned size() const
Definition: ExplodedGraph.h:386
clang::ento::ExplodedNode::EndOfFunctionNodeBuilder
friend class EndOfFunctionNodeBuilder
Definition: ExplodedGraph.h:68
clang::ento::ExplodedNodeSet::empty
bool empty() const
Definition: ExplodedGraph.h:483
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
clang::ento::ExplodedGraph::NumNodes
int64_t NumNodes
NumNodes - The number of nodes in the graph.
Definition: ExplodedGraph.h:329
clang::ento::ExplodedNode::getStackFrame
const StackFrameContext * getStackFrame() const
Definition: ExplodedGraph.h:150
clang::ento::ExplodedNode
Definition: ExplodedGraph.h:65
clang::ento::ExplodedNode::pred_empty
bool pred_empty() const
Definition: ExplodedGraph.h:202
ProgramState_Fwd.h
clang::ento::ExplodedGraph::const_node_iterator
AllNodesTy::const_iterator const_node_iterator
Definition: ExplodedGraph.h:398
clang::ento::ExplodedNodeSet::Add
void Add(ExplodedNode *N)
Definition: ExplodedGraph.h:475
clang::ento::ExplodedNode::pred_begin
const_pred_iterator pred_begin() const
Definition: ExplodedGraph.h:243
clang::ento::ExplodedGraph::EndNodes
NodeVector EndNodes
The nodes in the simulation graph which have been specially marked as the endpoint of an abstract sim...
Definition: ExplodedGraph.h:319
llvm::Optional
Definition: LLVM.h:40
clang::StackFrameContext
It represents a stack frame of the call stack (based on CallEvent).
Definition: AnalysisDeclContext.h:295
clang::ento::ExplodedGraph::nodes_end
node_iterator nodes_end()
Definition: ExplodedGraph.h:402
clang::ento::BranchNodeBuilder
BranchNodeBuilder is responsible for constructing the nodes corresponding to the two branches of the ...
Definition: CoreEngine.h:431
clang::ento::ExplodedGraph::AllNodesTy
llvm::FoldingSet< ExplodedNode > AllNodesTy
Definition: ExplodedGraph.h:392
clang::ento::ExplodedNode::pred_iterator
ExplodedNode *const * pred_iterator
Definition: ExplodedGraph.h:233
clang::ento::ExplodedGraph::num_eops
unsigned num_eops() const
Definition: ExplodedGraph.h:383
llvm::GraphTraits< clang::ento::ExplodedGraph * >::ChildIteratorType
clang::ento::ExplodedNode::succ_iterator ChildIteratorType
Definition: ExplodedGraph.h:513
clang::LocationContext::getAnalysis
T * getAnalysis() const
Definition: AnalysisDeclContext.h:251
clang::CFG
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1225
llvm::GraphTraits< clang::ento::ExplodedGraph * >::predecessorOfTrivial
static bool predecessorOfTrivial(NodeRef N)
Definition: ExplodedGraph.h:520
clang::ProgramPoint::getLocationContext
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:179
clang::ento::ExplodedNode::Profile
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: ExplodedGraph.h:190
clang::CodeGen::AlignmentSource::Decl
@ Decl
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
llvm::GraphTraits< clang::ento::ExplodedGraph * >::nodes_iterator
llvm::df_iterator< GraphTy > nodes_iterator
Definition: ExplodedGraph.h:514
clang::ento::ExplodedGraph::reclaimRecentlyAllocatedNodes
void reclaimRecentlyAllocatedNodes()
Reclaim "uninteresting" nodes created since the last time this method was called.
Definition: ExplodedGraph.cpp:169
clang::ento::ExplodedNode::succ_iterator
ExplodedNode *const * succ_iterator
Definition: ExplodedGraph.h:227
clang::ento::ExplodedNode::getFirstSucc
ExplodedNode * getFirstSucc()
Definition: ExplodedGraph.h:218
V
#define V(N, I)
Definition: ASTContext.h:3127
clang::ento::ExplodedNode::getState
const ProgramStateRef & getState() const
Definition: ExplodedGraph.h:169
ProgramPoint.h
clang::ento::ExplodedNode::getCFG
CFG & getCFG() const
Definition: ExplodedGraph.h:156
clang::ento::ExplodedNodeSet::clear
void clear()
Definition: ExplodedGraph.h:486
clang::ento::ExplodedNode::succ_end
const_succ_iterator succ_end() const
Definition: ExplodedGraph.h:258
clang::ento::NodeBuilder
Definition: CoreEngine.h:237
clang::ento::ExplodedNode::getCFGBlock
const CFGBlock * getCFGBlock() const
Definition: ExplodedGraph.cpp:290
clang::ento::ExplodedGraph::getNode
ExplodedNode * getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink=false, bool *IsNew=nullptr)
Retrieve the node associated with a (Location,State) pair, where the 'Location' is a ProgramPoint in ...
Definition: ExplodedGraph.cpp:393
Id
int Id
Definition: ASTDiff.cpp:191
clang::ento::ExplodedNode::ExplodedNode
ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, int64_t Id, bool IsSink)
Definition: ExplodedGraph.h:137
clang::ento::ExplodedNode::succs
succ_range succs()
Definition: ExplodedGraph.h:253
clang::ento::ExplodedNode::addPredecessor
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
Definition: ExplodedGraph.cpp:204
clang::ento::ExplodedNode::hasSinglePred
bool hasSinglePred() const
Definition: ExplodedGraph.h:206
clang::ento::ExplodedNode::isSink
bool isSink() const
Definition: ExplodedGraph.h:204
clang::ento::ExplodedNode::pred_end
const_pred_iterator pred_end() const
Definition: ExplodedGraph.h:246
clang::ento::ExplodedGraph::NodeVector
std::vector< ExplodedNode * > NodeVector
Definition: ExplodedGraph.h:309
clang::ento::ExplodedNodeSet::ExplodedNodeSet
ExplodedNodeSet(ExplodedNode *N)
Definition: ExplodedGraph.h:468
clang::ento::ExplodedNodeSet::end
const_iterator end() const
Definition: ExplodedGraph.h:500
clang::ento::ExplodedNodeSet::end
iterator end()
Definition: ExplodedGraph.h:497
uintptr_t
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
Definition: opencl-c-base.h:124
clang::ento::ExplodedGraph::ReclaimNodeInterval
unsigned ReclaimNodeInterval
Determines how often nodes are reclaimed.
Definition: ExplodedGraph.h:340
BumpVector.h
clang::ento::ExplodedGraph::getNodeAllocator
BumpVectorContext & getNodeAllocator()
Definition: ExplodedGraph.h:425
clang::ento::ExplodedNode::getPreviousStmtForDiagnostics
const Stmt * getPreviousStmtForDiagnostics() const
Find the statement that was executed immediately before this node.
Definition: ExplodedGraph.cpp:378
clang::ento::ExplodedGraph::ReclaimCounter
unsigned ReclaimCounter
Counter to determine when to reclaim nodes.
Definition: ExplodedGraph.h:343
clang::ento::ExplodedGraph::enableNodeReclamation
void enableNodeReclamation(unsigned Interval)
Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAll...
Definition: ExplodedGraph.h:446
clang::ento::ExplodedNode::getLocationAs
Optional< T > getLocationAs() const LLVM_LVALUE_FUNCTION
Definition: ExplodedGraph.h:172
clang::ento::ExplodedGraph::BVC
BumpVectorContext BVC
BVC - Allocator and context for allocating nodes and their predecessor and successor groups.
Definition: ExplodedGraph.h:326
clang::ento::ExplodedGraph::MakeEmptyGraph
std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const
Definition: ExplodedGraph.h:366
clang::ento::IndirectGotoNodeBuilder
Definition: CoreEngine.h:478
clang::ento::ExplodedGraph
Definition: ExplodedGraph.h:304
clang::ento::ExplodedGraph::ChangedNodes
NodeVector ChangedNodes
A list of recently allocated nodes that can potentially be recycled.
Definition: ExplodedGraph.h:332
clang::ento::SwitchNodeBuilder
Definition: CoreEngine.h:526
clang::ento::CoreEngine
CoreEngine - Implements the core logic of the graph-reachability analysis.
Definition: CoreEngine.h:55
clang::ento::ExplodedGraph::empty
bool empty() const
Definition: ExplodedGraph.h:385
clang::ento::ExplodedNode::succ_begin
succ_iterator succ_begin()
Definition: ExplodedGraph.h:251
clang::ento::ExplodedNodeSet::size
unsigned size() const
Definition: ExplodedGraph.h:482
clang::ento::ExplodedGraph::ExplodedGraph
ExplodedGraph()
state
and static some checkers Checker The latter are built on top of the former via the Checker and CheckerVisitor and attempts to isolate them from much of the gore of the internal analysis the analyzer is basically a source code simulator that traces out possible paths of execution The state of the and the combination of state and program point is a node in an exploded which has the entry program point and initial state
Definition: README.txt:30
clang::ento::Loc
Definition: SVals.h:327
clang::ento::ExplodedNode::pred_size
unsigned pred_size() const
Definition: ExplodedGraph.h:200
clang::ento::ExplodedGraph::node_iterator
AllNodesTy::iterator node_iterator
Definition: ExplodedGraph.h:397
clang::ento::ExplodedNode::isTrivial
bool isTrivial() const
The node is trivial if it has only one successor, only one predecessor, it's predecessor has only one...
Definition: ExplodedGraph.cpp:284
clang::ento::ExplodedGraph::isInterestingLValueExpr
static bool isInterestingLValueExpr(const Expr *Ex)
Returns true if nodes for the given expression kind are always kept around.
Definition: ExplodedGraph.cpp:50
clang::ParentMap
Definition: ParentMap.h:20
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::ento::ExplodedNodeSet::const_iterator
ImplTy::const_iterator const_iterator
Definition: ExplodedGraph.h:480
GraphTraits
clang::ento::ExplodedGraph::nodes_begin
node_iterator nodes_begin()
Definition: ExplodedGraph.h:400
clang::ento::ExplodedNode::getFirstSucc
const ExplodedNode * getFirstSucc() const
Definition: ExplodedGraph.h:222
llvm::GraphTraits< clang::ento::ExplodedGraph * >::nodes_end
static nodes_iterator nodes_end(const GraphTy G)
Definition: ExplodedGraph.h:540
clang::ento::ExplodedNode::const_succ_iterator
const ExplodedNode *const * const_succ_iterator
Definition: ExplodedGraph.h:230
clang::ento::ExplodedNode::getFirstPred
ExplodedNode * getFirstPred()
Definition: ExplodedGraph.h:210
clang::ento::ExplodedNode::getNextStmtForDiagnostics
const Stmt * getNextStmtForDiagnostics() const
Find the next statement that was executed on this node's execution path.
Definition: ExplodedGraph.cpp:351
llvm::ArrayRef
Definition: LLVM.h:34
clang::ento::ExplodedGraph::trim
std::unique_ptr< ExplodedGraph > trim(ArrayRef< const NodeTy * > Nodes, InterExplodedGraphMap *ForwardMap=nullptr, InterExplodedGraphMap *InverseMap=nullptr) const
Creates a trimmed version of the graph that only contains paths leading to the given nodes.
Definition: ExplodedGraph.cpp:441
clang::ento::ExplodedNode::const_pred_iterator
const ExplodedNode *const * const_pred_iterator
Definition: ExplodedGraph.h:236
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
clang::ento::ExplodedGraph::Roots
NodeVector Roots
The roots of the simulation graph.
Definition: ExplodedGraph.h:315
clang::ento::ExplodedGraph::~ExplodedGraph
~ExplodedGraph()
clang::ento::ExplodedNode::succ_empty
bool succ_empty() const
Definition: ExplodedGraph.h:201
clang::ento::ExplodedNode::pred_range
llvm::iterator_range< pred_iterator > pred_range
Definition: ExplodedGraph.h:234
clang::ento::ExplodedNode::pred_end
pred_iterator pred_end()
Definition: ExplodedGraph.h:240
LLVM.h
State
LineState State
Definition: UnwrappedLineFormatter.cpp:987
clang::BumpVectorContext::getAllocator
llvm::BumpPtrAllocator & getAllocator()
Definition: BumpVector.h:55
clang::ento::ExplodedGraph::nodes_begin
const_node_iterator nodes_begin() const
Definition: ExplodedGraph.h:404
clang::ento::ExplodedNode::succ_range
llvm::iterator_range< succ_iterator > succ_range
Definition: ExplodedGraph.h:228
clang::ento::ExplodedNode::getParentMap
const ParentMap & getParentMap() const
Definition: ExplodedGraph.h:160
clang::ento::ExplodedNode::Profile
static void Profile(llvm::FoldingSetNodeID &ID, const ProgramPoint &Loc, const ProgramStateRef &state, bool IsSink)
Definition: ExplodedGraph.h:181
clang::ento::ExplodedGraph::eop_begin
const_eop_iterator eop_begin() const
Definition: ExplodedGraph.h:420
clang::ento::ExplodedGraph::roots_end
roots_iterator roots_end()
Definition: ExplodedGraph.h:410
clang::ento::ExplodedNodeSet::begin
iterator begin()
Definition: ExplodedGraph.h:496
clang::ento::ExplodedGraph::roots_begin
roots_iterator roots_begin()
Definition: ExplodedGraph.h:408
ProgramState.h
std
Definition: Format.h:4125
clang::ento::ExplodedGraph::reserve
void reserve(unsigned NodeCount)
Definition: ExplodedGraph.h:388
clang::ento::ExplodedGraph::addEndOfPath
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
Definition: ExplodedGraph.h:377
clang::Builtin::ID
ID
Definition: Builtins.h:48
clang::ento::ExplodedGraph::eop_end
const_eop_iterator eop_end() const
Definition: ExplodedGraph.h:422
clang
Definition: CalledOnceCheck.h:17
clang::ento::ExplodedNode::getLocation
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
Definition: ExplodedGraph.h:144
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:69
clang::ento::ExplodedNode::getAnalysis
T & getAnalysis() const
Definition: ExplodedGraph.h:165
clang::ento::ExplodedNode::const_succ_range
llvm::iterator_range< const_succ_iterator > const_succ_range
Definition: ExplodedGraph.h:231
clang::ento::ExplodedNodeSet::insert
void insert(const ExplodedNodeSet &S)
Definition: ExplodedGraph.h:488
clang::ento::ExplodedGraph::num_roots
unsigned num_roots() const
Definition: ExplodedGraph.h:382
clang::ento::ExplodedGraph::FreeNodes
NodeVector FreeNodes
A list of nodes that can be reused.
Definition: ExplodedGraph.h:335
clang::ento::ExplodedNode::getSVal
SVal getSVal(const Stmt *S) const
Get the value of an arbitrary expression at this node.
Definition: ExplodedGraph.h:177
clang::ento::ExplodedNodeSet::erase
bool erase(ExplodedNode *N)
Definition: ExplodedGraph.h:484
clang::ento::ExplodedNode::getStmtForDiagnostics
const Stmt * getStmtForDiagnostics() const
If the node's program point corresponds to a statement, retrieve that statement.
Definition: ExplodedGraph.cpp:320
clang::ento::ExplodedNode::getCurrentOrPreviousStmtForDiagnostics
const Stmt * getCurrentOrPreviousStmtForDiagnostics() const
Find the statement that was executed at or immediately before this node.
Definition: ExplodedGraph.cpp:386
clang::ento::SVal
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:75
clang::LocationContext::getCFG
CFG * getCFG() const
Definition: AnalysisDeclContext.h:249
clang::ento::ExplodedNode::getFirstPred
const ExplodedNode * getFirstPred() const
Definition: ExplodedGraph.h:214
clang::ento::ExplodedNode::succ_begin
const_succ_iterator succ_begin() const
Definition: ExplodedGraph.h:255
clang::ento::ExplodedGraph::getAllocator
llvm::BumpPtrAllocator & getAllocator()
Definition: ExplodedGraph.h:424
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
clang::ento::ExplodedNode::getCodeDecl
const Decl & getCodeDecl() const
Definition: ExplodedGraph.h:154
clang::BumpVectorContext
Definition: BumpVector.h:32
llvm::SmallSetVector< ExplodedNode *, 4 >
clang::ento::ExplodedGraph::const_roots_iterator
NodeVector::const_iterator const_roots_iterator
Definition: ExplodedGraph.h:394
clang::ProgramPoint::getStackFrame
const StackFrameContext * getStackFrame() const
Definition: ProgramPoint.h:183
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::ento::ExplodedNode::preds
const_pred_range preds() const
Definition: ExplodedGraph.h:249
clang::ento::ExplodedNode::ExplodedGraph
friend class ExplodedGraph
Definition: ExplodedGraph.h:69
clang::ento::InterExplodedGraphMap
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
Definition: ExplodedGraph.h:302
clang::ento::ExplodedNode::getID
int64_t getID() const
Definition: ExplodedGraph.h:263
clang::ento::ExplodedGraph::roots_end
const_roots_iterator roots_end() const
Definition: ExplodedGraph.h:414
clang::LocationContext::getDecl
const Decl * getDecl() const
Definition: AnalysisDeclContext.h:247
clang::ento::ExplodedNodeSet
Definition: ExplodedGraph.h:463
clang::ento::ExplodedGraph::eop_end
eop_iterator eop_end()
Definition: ExplodedGraph.h:418
clang::ProgramPoint
Definition: ProgramPoint.h:59
clang::ento::ExplodedGraph::addRoot
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
Definition: ExplodedGraph.h:371
llvm::IntrusiveRefCntPtr< const ProgramState >
clang::ento::ExplodedGraph::NodeMap
llvm::DenseMap< const ExplodedNode *, ExplodedNode * > NodeMap
Definition: ExplodedGraph.h:427
clang::LocationContext::getParentMap
const ParentMap & getParentMap() const
Definition: AnalysisDeclContext.h:253
clang::ento::ExplodedNodeSet::begin
const_iterator begin() const
Definition: ExplodedGraph.h:499