clang  15.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> T &getAnalysis() const {
165  return *getLocationContext()->getAnalysis<T>();
166  }
167 
168  const ProgramStateRef &getState() const { return State; }
169 
170  template <typename T> Optional<T> getLocationAs() const & {
171  return Location.getAs<T>();
172  }
173 
174  /// Get the value of an arbitrary expression at this node.
175  SVal getSVal(const Stmt *S) const {
176  return getState()->getSVal(S, getLocationContext());
177  }
178 
179  static void Profile(llvm::FoldingSetNodeID &ID,
180  const ProgramPoint &Loc,
181  const ProgramStateRef &state,
182  bool IsSink) {
183  ID.Add(Loc);
184  ID.AddPointer(state.get());
185  ID.AddBoolean(IsSink);
186  }
187 
188  void Profile(llvm::FoldingSetNodeID& ID) const {
189  // We avoid copy constructors by not using accessors.
190  Profile(ID, Location, State, isSink());
191  }
192 
193  /// addPredeccessor - Adds a predecessor to the current node, and
194  /// in tandem add this node as a successor of the other node.
196 
197  unsigned succ_size() const { return Succs.size(); }
198  unsigned pred_size() const { return Preds.size(); }
199  bool succ_empty() const { return Succs.empty(); }
200  bool pred_empty() const { return Preds.empty(); }
201 
202  bool isSink() const { return Succs.getFlag(); }
203 
204  bool hasSinglePred() const {
205  return (pred_size() == 1);
206  }
207 
209  return pred_empty() ? nullptr : *(pred_begin());
210  }
211 
212  const ExplodedNode *getFirstPred() const {
213  return const_cast<ExplodedNode*>(this)->getFirstPred();
214  }
215 
217  return succ_empty() ? nullptr : *(succ_begin());
218  }
219 
220  const ExplodedNode *getFirstSucc() const {
221  return const_cast<ExplodedNode*>(this)->getFirstSucc();
222  }
223 
224  // Iterators over successor and predecessor vertices.
225  using succ_iterator = ExplodedNode * const *;
226  using succ_range = llvm::iterator_range<succ_iterator>;
227 
228  using const_succ_iterator = const ExplodedNode * const *;
229  using const_succ_range = llvm::iterator_range<const_succ_iterator>;
230 
231  using pred_iterator = ExplodedNode * const *;
232  using pred_range = llvm::iterator_range<pred_iterator>;
233 
234  using const_pred_iterator = const ExplodedNode * const *;
235  using const_pred_range = llvm::iterator_range<const_pred_iterator>;
236 
237  pred_iterator pred_begin() { return Preds.begin(); }
238  pred_iterator pred_end() { return Preds.end(); }
239  pred_range preds() { return {Preds.begin(), Preds.end()}; }
240 
242  return const_cast<ExplodedNode*>(this)->pred_begin();
243  }
245  return const_cast<ExplodedNode*>(this)->pred_end();
246  }
247  const_pred_range preds() const { return {Preds.begin(), Preds.end()}; }
248 
249  succ_iterator succ_begin() { return Succs.begin(); }
250  succ_iterator succ_end() { return Succs.end(); }
251  succ_range succs() { return {Succs.begin(), Succs.end()}; }
252 
254  return const_cast<ExplodedNode*>(this)->succ_begin();
255  }
257  return const_cast<ExplodedNode*>(this)->succ_end();
258  }
259  const_succ_range succs() const { return {Succs.begin(), Succs.end()}; }
260 
261  int64_t getID() const { return Id; }
262 
263  /// The node is trivial if it has only one successor, only one predecessor,
264  /// it's predecessor has only one successor,
265  /// and its program state is the same as the program state of the previous
266  /// node.
267  /// Trivial nodes may be skipped while printing exploded graph.
268  bool isTrivial() const;
269 
270  /// If the node's program point corresponds to a statement, retrieve that
271  /// statement. Useful for figuring out where to put a warning or a note.
272  /// If the statement belongs to a body-farmed definition,
273  /// retrieve the call site for that definition.
274  const Stmt *getStmtForDiagnostics() const;
275 
276  /// Find the next statement that was executed on this node's execution path.
277  /// Useful for explaining control flow that follows the current node.
278  /// If the statement belongs to a body-farmed definition, retrieve the
279  /// call site for that definition.
280  const Stmt *getNextStmtForDiagnostics() const;
281 
282  /// Find the statement that was executed immediately before this node.
283  /// Useful when the node corresponds to a CFG block entrance.
284  /// If the statement belongs to a body-farmed definition, retrieve the
285  /// call site for that definition.
286  const Stmt *getPreviousStmtForDiagnostics() const;
287 
288  /// Find the statement that was executed at or immediately before this node.
289  /// Useful when any nearby statement will do.
290  /// If the statement belongs to a body-farmed definition, retrieve the
291  /// call site for that definition.
293 
294 private:
295  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
296  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
297 };
298 
299 using InterExplodedGraphMap =
300  llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
301 
303 protected:
304  friend class CoreEngine;
305 
306  // Type definitions.
307  using NodeVector = std::vector<ExplodedNode *>;
308 
309  /// The roots of the simulation graph. Usually there will be only
310  /// one, but clients are free to establish multiple subgraphs within a single
311  /// SimulGraph. Moreover, these subgraphs can often merge when paths from
312  /// different roots reach the same state at the same program location.
314 
315  /// The nodes in the simulation graph which have been
316  /// specially marked as the endpoint of an abstract simulation path.
318 
319  /// Nodes - The nodes in the graph.
320  llvm::FoldingSet<ExplodedNode> Nodes;
321 
322  /// BVC - Allocator and context for allocating nodes and their predecessor
323  /// and successor groups.
325 
326  /// NumNodes - The number of nodes in the graph.
327  int64_t NumNodes = 0;
328 
329  /// A list of recently allocated nodes that can potentially be recycled.
331 
332  /// A list of nodes that can be reused.
334 
335  /// Determines how often nodes are reclaimed.
336  ///
337  /// If this is 0, nodes will never be reclaimed.
338  unsigned ReclaimNodeInterval = 0;
339 
340  /// Counter to determine when to reclaim nodes.
341  unsigned ReclaimCounter;
342 
343 public:
344  ExplodedGraph();
345  ~ExplodedGraph();
346 
347  /// Retrieve the node associated with a (Location,State) pair,
348  /// where the 'Location' is a ProgramPoint in the CFG. If no node for
349  /// this pair exists, it is created. IsNew is set to true if
350  /// the node was freshly created.
352  bool IsSink = false,
353  bool* IsNew = nullptr);
354 
355  /// Create a node for a (Location, State) pair,
356  /// but don't store it for deduplication later. This
357  /// is useful when copying an already completed
358  /// ExplodedGraph for further processing.
361  int64_t Id,
362  bool IsSink = false);
363 
364  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
365  return std::make_unique<ExplodedGraph>();
366  }
367 
368  /// addRoot - Add an untyped node to the set of roots.
370  Roots.push_back(V);
371  return V;
372  }
373 
374  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
376  EndNodes.push_back(V);
377  return V;
378  }
379 
380  unsigned num_roots() const { return Roots.size(); }
381  unsigned num_eops() const { return EndNodes.size(); }
382 
383  bool empty() const { return NumNodes == 0; }
384  unsigned size() const { return NumNodes; }
385 
386  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
387 
388  // Iterators.
390  using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
391  using roots_iterator = NodeVector::iterator;
392  using const_roots_iterator = NodeVector::const_iterator;
393  using eop_iterator = NodeVector::iterator;
394  using const_eop_iterator = NodeVector::const_iterator;
395  using node_iterator = AllNodesTy::iterator;
396  using const_node_iterator = AllNodesTy::const_iterator;
397 
398  node_iterator nodes_begin() { return Nodes.begin(); }
399 
400  node_iterator nodes_end() { return Nodes.end(); }
401 
402  const_node_iterator nodes_begin() const { return Nodes.begin(); }
403 
404  const_node_iterator nodes_end() const { return Nodes.end(); }
405 
406  roots_iterator roots_begin() { return Roots.begin(); }
407 
408  roots_iterator roots_end() { return Roots.end(); }
409 
410  const_roots_iterator roots_begin() const { return Roots.begin(); }
411 
412  const_roots_iterator roots_end() const { return Roots.end(); }
413 
414  eop_iterator eop_begin() { return EndNodes.begin(); }
415 
416  eop_iterator eop_end() { return EndNodes.end(); }
417 
418  const_eop_iterator eop_begin() const { return EndNodes.begin(); }
419 
420  const_eop_iterator eop_end() const { return EndNodes.end(); }
421 
422  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
424 
425  using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
426 
427  /// Creates a trimmed version of the graph that only contains paths leading
428  /// to the given nodes.
429  ///
430  /// \param Nodes The nodes which must appear in the final graph. Presumably
431  /// these are end-of-path nodes (i.e. they have no successors).
432  /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
433  /// the returned graph.
434  /// \param[out] InverseMap An optional map from nodes in the returned graph to
435  /// nodes in this graph.
436  /// \returns The trimmed graph
437  std::unique_ptr<ExplodedGraph>
439  InterExplodedGraphMap *ForwardMap = nullptr,
440  InterExplodedGraphMap *InverseMap = nullptr) const;
441 
442  /// Enable tracking of recently allocated nodes for potential reclamation
443  /// when calling reclaimRecentlyAllocatedNodes().
444  void enableNodeReclamation(unsigned Interval) {
445  ReclaimCounter = ReclaimNodeInterval = Interval;
446  }
447 
448  /// Reclaim "uninteresting" nodes created since the last time this method
449  /// was called.
451 
452  /// Returns true if nodes for the given expression kind are always
453  /// kept around.
454  static bool isInterestingLValueExpr(const Expr *Ex);
455 
456 private:
457  bool shouldCollect(const ExplodedNode *node);
458  void collectNode(ExplodedNode *node);
459 };
460 
463  ImplTy Impl;
464 
465 public:
467  assert(N && !static_cast<ExplodedNode*>(N)->isSink());
468  Impl.insert(N);
469  }
470 
471  ExplodedNodeSet() = default;
472 
473  void Add(ExplodedNode *N) {
474  if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
475  }
476 
477  using iterator = ImplTy::iterator;
478  using const_iterator = ImplTy::const_iterator;
479 
480  unsigned size() const { return Impl.size(); }
481  bool empty() const { return Impl.empty(); }
482  bool erase(ExplodedNode *N) { return Impl.remove(N); }
483 
484  void clear() { Impl.clear(); }
485 
486  void insert(const ExplodedNodeSet &S) {
487  assert(&S != this);
488  if (empty())
489  Impl = S.Impl;
490  else
491  Impl.insert(S.begin(), S.end());
492  }
493 
494  iterator begin() { return Impl.begin(); }
495  iterator end() { return Impl.end(); }
496 
497  const_iterator begin() const { return Impl.begin(); }
498  const_iterator end() const { return Impl.end(); }
499 };
500 
501 } // namespace ento
502 
503 } // namespace clang
504 
505 // GraphTraits
506 
507 namespace llvm {
508  template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
512  using nodes_iterator = llvm::df_iterator<GraphTy>;
513 
514  static NodeRef getEntryNode(const GraphTy G) {
515  return *G->roots_begin();
516  }
517 
518  static bool predecessorOfTrivial(NodeRef N) {
519  return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
520  }
521 
523  if (predecessorOfTrivial(N))
524  return child_begin(*N->succ_begin());
525  return N->succ_begin();
526  }
527 
529  if (predecessorOfTrivial(N))
530  return child_end(N->getFirstSucc());
531  return N->succ_end();
532  }
533 
535  return df_begin(G);
536  }
537 
538  static nodes_iterator nodes_end(const GraphTy G) {
539  return df_end(G);
540  }
541  };
542 } // namespace llvm
543 
544 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
clang::ento::ExplodedNode::pred_begin
pred_iterator pred_begin()
Definition: ExplodedGraph.h:237
clang::ento::ExplodedGraph::eop_begin
eop_iterator eop_begin()
Definition: ExplodedGraph.h:414
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:235
llvm
YAML serialization mapping.
Definition: Dominators.h:30
llvm::GraphTraits< clang::ento::ExplodedGraph * >::getEntryNode
static NodeRef getEntryNode(const GraphTy G)
Definition: ExplodedGraph.h:514
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:391
clang::ento::ExplodedNode::succ_size
unsigned succ_size() const
Definition: ExplodedGraph.h:197
SVals.h
llvm::GraphTraits< clang::ento::ExplodedGraph * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: ExplodedGraph.h:528
clang::ento::ExplodedGraph::Nodes
llvm::FoldingSet< ExplodedNode > Nodes
Nodes - The nodes in the graph.
Definition: ExplodedGraph.h:320
clang::ento::ExplodedNode::preds
pred_range preds()
Definition: ExplodedGraph.h:239
llvm::GraphTraits< clang::ento::ExplodedGraph * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ExplodedGraph.h:522
clang::ento::ExplodedNodeSet::iterator
ImplTy::iterator iterator
Definition: ExplodedGraph.h:477
clang::ento::ExplodedNode::succ_end
succ_iterator succ_end()
Definition: ExplodedGraph.h:250
clang::ento::ExplodedGraph::const_eop_iterator
NodeVector::const_iterator const_eop_iterator
Definition: ExplodedGraph.h:394
AnalysisDeclContext.h
clang::ento::ExplodedGraph::eop_iterator
NodeVector::iterator eop_iterator
Definition: ExplodedGraph.h:393
clang::ento::ExplodedGraph::roots_begin
const_roots_iterator roots_begin() const
Definition: ExplodedGraph.h:410
clang::ento::ExplodedGraph::nodes_end
const_node_iterator nodes_end() const
Definition: ExplodedGraph.h:404
llvm::GraphTraits< clang::ento::ExplodedGraph * >::nodes_begin
static nodes_iterator nodes_begin(const GraphTy G)
Definition: ExplodedGraph.h:534
clang::ento::ExplodedNode::succs
const_succ_range succs() const
Definition: ExplodedGraph.h:259
clang::ento::ExplodedGraph::size
unsigned size() const
Definition: ExplodedGraph.h:384
clang::ento::ExplodedNode::EndOfFunctionNodeBuilder
friend class EndOfFunctionNodeBuilder
Definition: ExplodedGraph.h:68
clang::ento::ExplodedNodeSet::empty
bool empty() const
Definition: ExplodedGraph.h:481
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:327
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:200
ProgramState_Fwd.h
clang::ento::ExplodedGraph::const_node_iterator
AllNodesTy::const_iterator const_node_iterator
Definition: ExplodedGraph.h:396
clang::ento::ExplodedNodeSet::Add
void Add(ExplodedNode *N)
Definition: ExplodedGraph.h:473
clang::ento::ExplodedNode::pred_begin
const_pred_iterator pred_begin() const
Definition: ExplodedGraph.h:241
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:317
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:400
clang::ento::BranchNodeBuilder
BranchNodeBuilder is responsible for constructing the nodes corresponding to the two branches of the ...
Definition: CoreEngine.h:433
clang::ento::ExplodedGraph::AllNodesTy
llvm::FoldingSet< ExplodedNode > AllNodesTy
Definition: ExplodedGraph.h:390
clang::ento::ExplodedNode::pred_iterator
ExplodedNode *const * pred_iterator
Definition: ExplodedGraph.h:231
clang::ento::ExplodedGraph::num_eops
unsigned num_eops() const
Definition: ExplodedGraph.h:381
llvm::GraphTraits< clang::ento::ExplodedGraph * >::ChildIteratorType
clang::ento::ExplodedNode::succ_iterator ChildIteratorType
Definition: ExplodedGraph.h:511
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:518
clang::ProgramPoint::getLocationContext
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:178
clang::ento::ExplodedNode::Profile
void Profile(llvm::FoldingSetNodeID &ID) const
Definition: ExplodedGraph.h:188
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:512
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:225
clang::ento::ExplodedNode::getFirstSucc
ExplodedNode * getFirstSucc()
Definition: ExplodedGraph.h:216
V
#define V(N, I)
Definition: ASTContext.h:3176
clang::ento::ExplodedNode::getState
const ProgramStateRef & getState() const
Definition: ExplodedGraph.h:168
ProgramPoint.h
clang::ento::ExplodedNode::getCFG
CFG & getCFG() const
Definition: ExplodedGraph.h:156
clang::ento::ExplodedNodeSet::clear
void clear()
Definition: ExplodedGraph.h:484
clang::ento::ExplodedNode::succ_end
const_succ_iterator succ_end() const
Definition: ExplodedGraph.h:256
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:251
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:204
clang::ento::ExplodedNode::isSink
bool isSink() const
Definition: ExplodedGraph.h:202
clang::ento::ExplodedNode::pred_end
const_pred_iterator pred_end() const
Definition: ExplodedGraph.h:244
clang::ento::ExplodedGraph::NodeVector
std::vector< ExplodedNode * > NodeVector
Definition: ExplodedGraph.h:307
clang::ento::ExplodedNodeSet::ExplodedNodeSet
ExplodedNodeSet(ExplodedNode *N)
Definition: ExplodedGraph.h:466
clang::ento::ExplodedNodeSet::end
const_iterator end() const
Definition: ExplodedGraph.h:498
clang::ento::ExplodedNodeSet::end
iterator end()
Definition: ExplodedGraph.h:495
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:138
clang::ento::ExplodedGraph::ReclaimNodeInterval
unsigned ReclaimNodeInterval
Determines how often nodes are reclaimed.
Definition: ExplodedGraph.h:338
BumpVector.h
clang::ento::ExplodedGraph::getNodeAllocator
BumpVectorContext & getNodeAllocator()
Definition: ExplodedGraph.h:423
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:341
clang::ento::ExplodedGraph::enableNodeReclamation
void enableNodeReclamation(unsigned Interval)
Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAll...
Definition: ExplodedGraph.h:444
clang::ento::ExplodedGraph::BVC
BumpVectorContext BVC
BVC - Allocator and context for allocating nodes and their predecessor and successor groups.
Definition: ExplodedGraph.h:324
clang::ento::ExplodedGraph::MakeEmptyGraph
std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const
Definition: ExplodedGraph.h:364
clang::ento::IndirectGotoNodeBuilder
Definition: CoreEngine.h:480
clang::ento::ExplodedGraph
Definition: ExplodedGraph.h:302
clang::ento::ExplodedGraph::ChangedNodes
NodeVector ChangedNodes
A list of recently allocated nodes that can potentially be recycled.
Definition: ExplodedGraph.h:330
clang::ento::SwitchNodeBuilder
Definition: CoreEngine.h:528
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:383
clang::ento::ExplodedNode::succ_begin
succ_iterator succ_begin()
Definition: ExplodedGraph.h:249
clang::ento::ExplodedNodeSet::size
unsigned size() const
Definition: ExplodedGraph.h:480
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:326
clang::ento::ExplodedNode::pred_size
unsigned pred_size() const
Definition: ExplodedGraph.h:198
clang::ento::ExplodedGraph::node_iterator
AllNodesTy::iterator node_iterator
Definition: ExplodedGraph.h:395
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:478
clang::ento::ExplodedGraph::nodes_begin
node_iterator nodes_begin()
Definition: ExplodedGraph.h:398
clang::ento::ExplodedNode::getFirstSucc
const ExplodedNode * getFirstSucc() const
Definition: ExplodedGraph.h:220
llvm::GraphTraits< clang::ento::ExplodedGraph * >::nodes_end
static nodes_iterator nodes_end(const GraphTy G)
Definition: ExplodedGraph.h:538
clang::ento::ExplodedNode::const_succ_iterator
const ExplodedNode *const * const_succ_iterator
Definition: ExplodedGraph.h:228
clang::ento::ExplodedNode::getFirstPred
ExplodedNode * getFirstPred()
Definition: ExplodedGraph.h:208
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:234
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
clang::ento::ExplodedGraph::Roots
NodeVector Roots
The roots of the simulation graph.
Definition: ExplodedGraph.h:313
clang::ento::ExplodedGraph::~ExplodedGraph
~ExplodedGraph()
clang::ento::ExplodedNode::succ_empty
bool succ_empty() const
Definition: ExplodedGraph.h:199
clang::ento::ExplodedNode::pred_range
llvm::iterator_range< pred_iterator > pred_range
Definition: ExplodedGraph.h:232
clang::ento::ExplodedNode::pred_end
pred_iterator pred_end()
Definition: ExplodedGraph.h:238
LLVM.h
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1089
clang::BumpVectorContext::getAllocator
llvm::BumpPtrAllocator & getAllocator()
Definition: BumpVector.h:55
clang::ento::ExplodedGraph::nodes_begin
const_node_iterator nodes_begin() const
Definition: ExplodedGraph.h:402
clang::ento::ExplodedNode::succ_range
llvm::iterator_range< succ_iterator > succ_range
Definition: ExplodedGraph.h:226
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:179
clang::ento::ExplodedGraph::eop_begin
const_eop_iterator eop_begin() const
Definition: ExplodedGraph.h:418
clang::ento::ExplodedGraph::roots_end
roots_iterator roots_end()
Definition: ExplodedGraph.h:408
clang::ento::ExplodedNodeSet::begin
iterator begin()
Definition: ExplodedGraph.h:494
clang::ento::ExplodedGraph::roots_begin
roots_iterator roots_begin()
Definition: ExplodedGraph.h:406
ProgramState.h
std
Definition: Format.h:4296
clang::ento::ExplodedGraph::reserve
void reserve(unsigned NodeCount)
Definition: ExplodedGraph.h:386
clang::ento::ExplodedGraph::addEndOfPath
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
Definition: ExplodedGraph.h:375
clang::Builtin::ID
ID
Definition: Builtins.h:49
clang::ento::ExplodedGraph::eop_end
const_eop_iterator eop_end() const
Definition: ExplodedGraph.h:420
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::ento::ExplodedNode::getLocationAs
Optional< T > getLocationAs() const &
Definition: ExplodedGraph.h:170
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:69
clang::ento::ExplodedNode::getAnalysis
T & getAnalysis() const
Definition: ExplodedGraph.h:164
clang::ento::ExplodedNode::const_succ_range
llvm::iterator_range< const_succ_iterator > const_succ_range
Definition: ExplodedGraph.h:229
clang::ento::ExplodedNodeSet::insert
void insert(const ExplodedNodeSet &S)
Definition: ExplodedGraph.h:486
clang::ento::ExplodedGraph::num_roots
unsigned num_roots() const
Definition: ExplodedGraph.h:380
clang::ento::ExplodedGraph::FreeNodes
NodeVector FreeNodes
A list of nodes that can be reused.
Definition: ExplodedGraph.h:333
clang::ento::ExplodedNode::getSVal
SVal getSVal(const Stmt *S) const
Get the value of an arbitrary expression at this node.
Definition: ExplodedGraph.h:175
clang::ento::ExplodedNodeSet::erase
bool erase(ExplodedNode *N)
Definition: ExplodedGraph.h:482
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:74
clang::LocationContext::getCFG
CFG * getCFG() const
Definition: AnalysisDeclContext.h:249
clang::ento::ExplodedNode::getFirstPred
const ExplodedNode * getFirstPred() const
Definition: ExplodedGraph.h:212
clang::ento::ExplodedNode::succ_begin
const_succ_iterator succ_begin() const
Definition: ExplodedGraph.h:253
clang::ento::ExplodedGraph::getAllocator
llvm::BumpPtrAllocator & getAllocator()
Definition: ExplodedGraph.h:422
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:392
clang::ProgramPoint::getStackFrame
const StackFrameContext * getStackFrame() const
Definition: ProgramPoint.h:182
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::ento::ExplodedNode::preds
const_pred_range preds() const
Definition: ExplodedGraph.h:247
clang::ento::ExplodedNode::ExplodedGraph
friend class ExplodedGraph
Definition: ExplodedGraph.h:69
clang::ento::InterExplodedGraphMap
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
Definition: ExplodedGraph.h:300
clang::ento::ExplodedNode::getID
int64_t getID() const
Definition: ExplodedGraph.h:261
clang::ento::ExplodedGraph::roots_end
const_roots_iterator roots_end() const
Definition: ExplodedGraph.h:412
clang::LocationContext::getDecl
const Decl * getDecl() const
Definition: AnalysisDeclContext.h:247
clang::ento::ExplodedNodeSet
Definition: ExplodedGraph.h:461
clang::ento::ExplodedGraph::eop_end
eop_iterator eop_end()
Definition: ExplodedGraph.h:416
clang::ProgramPoint
Definition: ProgramPoint.h:58
clang::ento::ExplodedGraph::addRoot
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
Definition: ExplodedGraph.h:369
llvm::IntrusiveRefCntPtr< const ProgramState >
clang::ento::ExplodedGraph::NodeMap
llvm::DenseMap< const ExplodedNode *, ExplodedNode * > NodeMap
Definition: ExplodedGraph.h:425
clang::LocationContext::getParentMap
const ParentMap & getParentMap() const
Definition: AnalysisDeclContext.h:253
clang::ento::ExplodedNodeSet::begin
const_iterator begin() const
Definition: ExplodedGraph.h:497