Go to the documentation of this file.
18 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
19 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_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/STLExtras.h"
34 #include "llvm/ADT/SetVector.h"
35 #include "llvm/Support/Allocator.h"
36 #include "llvm/Support/Compiler.h"
91 NodeGroup(
bool Flag =
false) :
P(Flag) {
92 assert(getFlag() == Flag);
99 unsigned size()
const;
101 bool empty()
const {
return P == 0 || getFlag() != 0; }
116 bool getFlag()
const {
123 const ProgramPoint Location;
139 : Location(loc), State(
std::move(
state)), Succs(IsSink),
Id(
Id) {
140 assert(
isSink() == IsSink);
171 return Location.getAs<T>();
185 ID.AddBoolean(IsSink);
202 bool isSink()
const {
return Succs.getFlag(); }
300 llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
320 llvm::FoldingSet<ExplodedNode>
Nodes;
353 bool* IsNew =
nullptr);
362 bool IsSink =
false);
365 return std::make_unique<ExplodedGraph>();
425 using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
437 std::unique_ptr<ExplodedGraph>
474 if (N && !
static_cast<ExplodedNode*
>(N)->isSink()) Impl.insert(N);
480 unsigned size()
const {
return Impl.size(); }
481 bool empty()
const {
return Impl.empty(); }
491 Impl.insert(S.begin(), S.end());
508 template <>
struct GraphTraits<
clang::ento::ExplodedGraph *> {
523 if (predecessorOfTrivial(N))
529 if (predecessorOfTrivial(N))
544 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
pred_iterator pred_begin()
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.
llvm::iterator_range< const_pred_iterator > const_pred_range
YAML serialization mapping.
static NodeRef getEntryNode(const GraphTy G)
ExplodedNodeSet()=default
const LocationContext * getLocationContext() const
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
NodeVector::iterator roots_iterator
unsigned succ_size() const
static ChildIteratorType child_end(NodeRef N)
llvm::FoldingSet< ExplodedNode > Nodes
Nodes - The nodes in the graph.
static ChildIteratorType child_begin(NodeRef N)
ImplTy::iterator iterator
NodeVector::const_iterator const_eop_iterator
NodeVector::iterator eop_iterator
const_roots_iterator roots_begin() const
const_node_iterator nodes_end() const
static nodes_iterator nodes_begin(const GraphTy G)
const_succ_range succs() const
friend class EndOfFunctionNodeBuilder
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
int64_t NumNodes
NumNodes - The number of nodes in the graph.
const StackFrameContext * getStackFrame() const
AllNodesTy::const_iterator const_node_iterator
void Add(ExplodedNode *N)
const_pred_iterator pred_begin() const
NodeVector EndNodes
The nodes in the simulation graph which have been specially marked as the endpoint of an abstract sim...
It represents a stack frame of the call stack (based on CallEvent).
std::optional< T > getLocationAs() const &
node_iterator nodes_end()
BranchNodeBuilder is responsible for constructing the nodes corresponding to the two branches of the ...
llvm::FoldingSet< ExplodedNode > AllNodesTy
ExplodedNode *const * pred_iterator
unsigned num_eops() const
clang::ento::ExplodedNode::succ_iterator ChildIteratorType
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
static bool predecessorOfTrivial(NodeRef N)
const LocationContext * getLocationContext() const
void Profile(llvm::FoldingSetNodeID &ID) const
@ Decl
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
Represents a single basic block in a source-level CFG.
llvm::df_iterator< GraphTy > nodes_iterator
void reclaimRecentlyAllocatedNodes()
Reclaim "uninteresting" nodes created since the last time this method was called.
ExplodedNode *const * succ_iterator
ExplodedNode * getFirstSucc()
const ProgramStateRef & getState() const
const_succ_iterator succ_end() const
const CFGBlock * getCFGBlock() const
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 ...
ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, int64_t Id, bool IsSink)
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
bool hasSinglePred() const
const_pred_iterator pred_end() const
std::vector< ExplodedNode * > NodeVector
ExplodedNodeSet(ExplodedNode *N)
const_iterator end() const
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
unsigned ReclaimNodeInterval
Determines how often nodes are reclaimed.
BumpVectorContext & getNodeAllocator()
const Stmt * getPreviousStmtForDiagnostics() const
Find the statement that was executed immediately before this node.
unsigned ReclaimCounter
Counter to determine when to reclaim nodes.
void enableNodeReclamation(unsigned Interval)
Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAll...
BumpVectorContext BVC
BVC - Allocator and context for allocating nodes and their predecessor and successor groups.
std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const
NodeVector ChangedNodes
A list of recently allocated nodes that can potentially be recycled.
CoreEngine - Implements the core logic of the graph-reachability analysis.
succ_iterator succ_begin()
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
unsigned pred_size() const
AllNodesTy::iterator node_iterator
bool isTrivial() const
The node is trivial if it has only one successor, only one predecessor, it's predecessor has only one...
static bool isInterestingLValueExpr(const Expr *Ex)
Returns true if nodes for the given expression kind are always kept around.
ImplTy::const_iterator const_iterator
node_iterator nodes_begin()
const ExplodedNode * getFirstSucc() const
static nodes_iterator nodes_end(const GraphTy G)
const ExplodedNode *const * const_succ_iterator
ExplodedNode * getFirstPred()
const Stmt * getNextStmtForDiagnostics() const
Find the next statement that was executed on this node's execution path.
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.
const ExplodedNode *const * const_pred_iterator
Decl - This represents one declaration (or definition), e.g.
NodeVector Roots
The roots of the simulation graph.
llvm::iterator_range< pred_iterator > pred_range
llvm::BumpPtrAllocator & getAllocator()
const_node_iterator nodes_begin() const
llvm::iterator_range< succ_iterator > succ_range
const ParentMap & getParentMap() const
static void Profile(llvm::FoldingSetNodeID &ID, const ProgramPoint &Loc, const ProgramStateRef &state, bool IsSink)
const_eop_iterator eop_begin() const
roots_iterator roots_end()
roots_iterator roots_begin()
void reserve(unsigned NodeCount)
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
const_eop_iterator eop_end() const
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
Stmt - This represents one statement.
llvm::iterator_range< const_succ_iterator > const_succ_range
void insert(const ExplodedNodeSet &S)
unsigned num_roots() const
NodeVector FreeNodes
A list of nodes that can be reused.
SVal getSVal(const Stmt *S) const
Get the value of an arbitrary expression at this node.
bool erase(ExplodedNode *N)
const Stmt * getStmtForDiagnostics() const
If the node's program point corresponds to a statement, retrieve that statement.
const Stmt * getCurrentOrPreviousStmtForDiagnostics() const
Find the statement that was executed at or immediately before this node.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
const ExplodedNode * getFirstPred() const
const_succ_iterator succ_begin() const
llvm::BumpPtrAllocator & getAllocator()
const Decl & getCodeDecl() const
NodeVector::const_iterator const_roots_iterator
const StackFrameContext * getStackFrame() const
This represents one expression.
const_pred_range preds() const
friend class ExplodedGraph
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
const_roots_iterator roots_end() const
const Decl * getDecl() const
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
llvm::DenseMap< const ExplodedNode *, ExplodedNode * > NodeMap
const ParentMap & getParentMap() const
const_iterator begin() const