EIC code displayed by LXR master/​include/​clang/​StaticAnalyzer/​Core/​PathSensitive/​ExplodedGraph.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:37:08

 //===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines the template classes ExplodedNode and ExplodedGraph,
 //  which represent a path-sensitive, intra-procedural "exploded graph."
 //  See "Precise interprocedural dataflow analysis via graph reachability"
 //  by Reps, Horwitz, and Sagiv
 //  (http://portal.acm.org/citation.cfm?id=199462) for the definition of an
 //  exploded graph.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
 
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/ProgramPoint.h"
 #include "clang/Analysis/Support/BumpVector.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Compiler.h"
 #include <cassert>
 #include <cstdint>
 #include <memory>
 #include <optional>
 #include <utility>
 #include <vector>
 
 namespace clang {
 
 class CFG;
 class Decl;
 class Expr;
 class ParentMap;
 class Stmt;
 
 namespace ento {
 
 class ExplodedGraph;
 
 //===----------------------------------------------------------------------===//
 // ExplodedGraph "implementation" classes.  These classes are not typed to
 // contain a specific kind of state.  Typed-specialized versions are defined
 // on top of these classes.
 //===----------------------------------------------------------------------===//
 
 // ExplodedNode is not constified all over the engine because we need to add
 // successors to it at any time after creating it.
 
 class ExplodedNode : public llvm::FoldingSetNode {
   friend class BranchNodeBuilder;
   friend class CoreEngine;
   friend class EndOfFunctionNodeBuilder;
   friend class ExplodedGraph;
   friend class IndirectGotoNodeBuilder;
   friend class NodeBuilder;
   friend class SwitchNodeBuilder;
 
   /// Efficiently stores a list of ExplodedNodes, or an optional flag.
   ///
   /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
   /// for the case when there is only one node in the group. This is a fairly
   /// common case in an ExplodedGraph, where most nodes have only one
   /// predecessor and many have only one successor. It can also be used to
   /// store a flag rather than a node list, which ExplodedNode uses to mark
   /// whether a node is a sink. If the flag is set, the group is implicitly
   /// empty and no nodes may be added.
   class NodeGroup {
     // Conceptually a discriminated union. If the low bit is set, the node is
     // a sink. If the low bit is not set, the pointer refers to the storage
     // for the nodes in the group.
     // This is not a PointerIntPair in order to keep the storage type opaque.
     uintptr_t P;
 
   public:
     NodeGroup(bool Flag = false) : P(Flag) {
       assert(getFlag() == Flag);
     }
 
     ExplodedNode * const *begin() const;
 
     ExplodedNode * const *end() const;
 
     unsigned size() const;
 
     bool empty() const { return P == 0 || getFlag() != 0; }
 
     /// Adds a node to the list.
     ///
     /// The group must not have been created with its flag set.
     void addNode(ExplodedNode *N, ExplodedGraph &G);
 
     /// Replaces the single node in this group with a new node.
     ///
     /// Note that this should only be used when you know the group was not
     /// created with its flag set, and that the group is empty or contains
     /// only a single node.
     void replaceNode(ExplodedNode *node);
 
     /// Returns whether this group was created with its flag set.
     bool getFlag() const {
       return (P & 1);
     }
   };
 
   /// Location - The program location (within a function body) associated
   ///  with this node.
   const ProgramPoint Location;
 
   /// State - The state associated with this node.
   ProgramStateRef State;
 
   /// Preds - The predecessors of this node.
   NodeGroup Preds;
 
   /// Succs - The successors of this node.
   NodeGroup Succs;
 
   int64_t Id;
 
 public:
   explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
                         int64_t Id, bool IsSink)
       : Location(loc), State(std::move(state)), Succs(IsSink), Id(Id) {
     assert(isSink() == IsSink);
   }
 
   /// getLocation - Returns the edge associated with the given node.
   ProgramPoint getLocation() const { return Location; }
 
   const LocationContext *getLocationContext() const {
     return getLocation().getLocationContext();
   }
 
   const StackFrameContext *getStackFrame() const {
     return getLocation().getStackFrame();
   }
 
   const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
 
   CFG &getCFG() const { return *getLocationContext()->getCFG(); }
 
   const CFGBlock *getCFGBlock() const;
 
   const ParentMap &getParentMap() const {
     return getLocationContext()->getParentMap();
   }
 
   template <typename T> T &getAnalysis() const {
     return *getLocationContext()->getAnalysis<T>();
   }
 
   const ProgramStateRef &getState() const { return State; }
 
   template <typename T> std::optional<T> getLocationAs() const & {
     return Location.getAs<T>();
   }
 
   /// Get the value of an arbitrary expression at this node.
   SVal getSVal(const Stmt *S) const {
     return getState()->getSVal(S, getLocationContext());
   }
 
   static void Profile(llvm::FoldingSetNodeID &ID,
                       const ProgramPoint &Loc,
                       const ProgramStateRef &state,
                       bool IsSink) {
     ID.Add(Loc);
     ID.AddPointer(state.get());
     ID.AddBoolean(IsSink);
   }
 
   void Profile(llvm::FoldingSetNodeID& ID) const {
     // We avoid copy constructors by not using accessors.
     Profile(ID, Location, State, isSink());
   }
 
   /// addPredeccessor - Adds a predecessor to the current node, and
   ///  in tandem add this node as a successor of the other node.
   void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
 
   unsigned succ_size() const { return Succs.size(); }
   unsigned pred_size() const { return Preds.size(); }
   bool succ_empty() const { return Succs.empty(); }
   bool pred_empty() const { return Preds.empty(); }
 
   bool isSink() const { return Succs.getFlag(); }
 
   bool hasSinglePred() const {
     return (pred_size() == 1);
   }
 
   ExplodedNode *getFirstPred() {
     return pred_empty() ? nullptr : *(pred_begin());
   }
 
   const ExplodedNode *getFirstPred() const {
     return const_cast<ExplodedNode*>(this)->getFirstPred();
   }
 
   ExplodedNode *getFirstSucc() {
     return succ_empty() ? nullptr : *(succ_begin());
   }
 
   const ExplodedNode *getFirstSucc() const {
     return const_cast<ExplodedNode*>(this)->getFirstSucc();
   }
 
   // Iterators over successor and predecessor vertices.
   using succ_iterator = ExplodedNode * const *;
   using succ_range = llvm::iterator_range<succ_iterator>;
 
   using const_succ_iterator = const ExplodedNode * const *;
   using const_succ_range = llvm::iterator_range<const_succ_iterator>;
 
   using pred_iterator = ExplodedNode * const *;
   using pred_range = llvm::iterator_range<pred_iterator>;
 
   using const_pred_iterator = const ExplodedNode * const *;
   using const_pred_range = llvm::iterator_range<const_pred_iterator>;
 
   pred_iterator pred_begin() { return Preds.begin(); }
   pred_iterator pred_end() { return Preds.end(); }
   pred_range preds() { return {Preds.begin(), Preds.end()}; }
 
   const_pred_iterator pred_begin() const {
     return const_cast<ExplodedNode*>(this)->pred_begin();
   }
   const_pred_iterator pred_end() const {
     return const_cast<ExplodedNode*>(this)->pred_end();
   }
   const_pred_range preds() const { return {Preds.begin(), Preds.end()}; }
 
   succ_iterator succ_begin() { return Succs.begin(); }
   succ_iterator succ_end() { return Succs.end(); }
   succ_range succs() { return {Succs.begin(), Succs.end()}; }
 
   const_succ_iterator succ_begin() const {
     return const_cast<ExplodedNode*>(this)->succ_begin();
   }
   const_succ_iterator succ_end() const {
     return const_cast<ExplodedNode*>(this)->succ_end();
   }
   const_succ_range succs() const { return {Succs.begin(), Succs.end()}; }
 
   int64_t getID() const { return Id; }
 
   /// The node is trivial if it has only one successor, only one predecessor,
   /// it's predecessor has only one successor,
   /// and its program state is the same as the program state of the previous
   /// node.
   /// Trivial nodes may be skipped while printing exploded graph.
   bool isTrivial() const;
 
   /// If the node's program point corresponds to a statement, retrieve that
   /// statement. Useful for figuring out where to put a warning or a note.
   /// If the statement belongs to a body-farmed definition,
   /// retrieve the call site for that definition.
   const Stmt *getStmtForDiagnostics() const;
 
   /// Find the next statement that was executed on this node's execution path.
   /// Useful for explaining control flow that follows the current node.
   /// If the statement belongs to a body-farmed definition, retrieve the
   /// call site for that definition.
   const Stmt *getNextStmtForDiagnostics() const;
 
   /// Find the statement that was executed immediately before this node.
   /// Useful when the node corresponds to a CFG block entrance.
   /// If the statement belongs to a body-farmed definition, retrieve the
   /// call site for that definition.
   const Stmt *getPreviousStmtForDiagnostics() const;
 
   /// Find the statement that was executed at or immediately before this node.
   /// Useful when any nearby statement will do.
   /// If the statement belongs to a body-farmed definition, retrieve the
   /// call site for that definition.
   const Stmt *getCurrentOrPreviousStmtForDiagnostics() const;
 
 private:
   void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
   void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
 };
 
 using InterExplodedGraphMap =
     llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
 
 class ExplodedGraph {
 protected:
   friend class CoreEngine;
 
   // Type definitions.
   using NodeVector = std::vector<ExplodedNode *>;
 
   /// The roots of the simulation graph. Usually there will be only
   /// one, but clients are free to establish multiple subgraphs within a single
   /// SimulGraph. Moreover, these subgraphs can often merge when paths from
   /// different roots reach the same state at the same program location.
   NodeVector Roots;
 
   /// The nodes in the simulation graph which have been
   /// specially marked as the endpoint of an abstract simulation path.
   NodeVector EndNodes;
 
   /// Nodes - The nodes in the graph.
   llvm::FoldingSet<ExplodedNode> Nodes;
 
   /// BVC - Allocator and context for allocating nodes and their predecessor
   /// and successor groups.
   BumpVectorContext BVC;
 
   /// NumNodes - The number of nodes in the graph.
   int64_t NumNodes = 0;
 
   /// A list of recently allocated nodes that can potentially be recycled.
   NodeVector ChangedNodes;
 
   /// A list of nodes that can be reused.
   NodeVector FreeNodes;
 
   /// Determines how often nodes are reclaimed.
   ///
   /// If this is 0, nodes will never be reclaimed.
   unsigned ReclaimNodeInterval = 0;
 
   /// Counter to determine when to reclaim nodes.
   unsigned ReclaimCounter;
 
 public:
   ExplodedGraph();
   ~ExplodedGraph();
 
   /// Retrieve the node associated with a (Location,State) pair,
   ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
   ///  this pair exists, it is created. IsNew is set to true if
   ///  the node was freshly created.
   ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
                         bool IsSink = false,
                         bool* IsNew = nullptr);
 
   /// Create a node for a (Location, State) pair,
   ///  but don't store it for deduplication later.  This
   ///  is useful when copying an already completed
   ///  ExplodedGraph for further processing.
   ExplodedNode *createUncachedNode(const ProgramPoint &L,
     ProgramStateRef State,
     int64_t Id,
     bool IsSink = false);
 
   std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
     return std::make_unique<ExplodedGraph>();
   }
 
   /// addRoot - Add an untyped node to the set of roots.
   ExplodedNode *addRoot(ExplodedNode *V) {
     Roots.push_back(V);
     return V;
   }
 
   /// addEndOfPath - Add an untyped node to the set of EOP nodes.
   ExplodedNode *addEndOfPath(ExplodedNode *V) {
     EndNodes.push_back(V);
     return V;
   }
 
   unsigned num_roots() const { return Roots.size(); }
   unsigned num_eops() const { return EndNodes.size(); }
 
   bool empty() const { return NumNodes == 0; }
   unsigned size() const { return NumNodes; }
 
   void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
 
   // Iterators.
   using NodeTy = ExplodedNode;
   using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
   using roots_iterator = NodeVector::iterator;
   using const_roots_iterator = NodeVector::const_iterator;
   using eop_iterator = NodeVector::iterator;
   using const_eop_iterator = NodeVector::const_iterator;
   using node_iterator = AllNodesTy::iterator;
   using const_node_iterator = AllNodesTy::const_iterator;
 
   llvm::iterator_range<node_iterator> nodes() { return Nodes; }
 
   llvm::iterator_range<const_node_iterator> nodes() const { return Nodes; }
 
   roots_iterator roots_begin() { return Roots.begin(); }
 
   roots_iterator roots_end() { return Roots.end(); }
 
   const_roots_iterator roots_begin() const { return Roots.begin(); }
 
   const_roots_iterator roots_end() const { return Roots.end(); }
 
   eop_iterator eop_begin() { return EndNodes.begin(); }
 
   eop_iterator eop_end() { return EndNodes.end(); }
 
   const_eop_iterator eop_begin() const { return EndNodes.begin(); }
 
   const_eop_iterator eop_end() const { return EndNodes.end(); }
 
   llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
   BumpVectorContext &getNodeAllocator() { return BVC; }
 
   using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
 
   /// Creates a trimmed version of the graph that only contains paths leading
   /// to the given nodes.
   ///
   /// \param Nodes The nodes which must appear in the final graph. Presumably
   ///              these are end-of-path nodes (i.e. they have no successors).
   /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
   ///                        the returned graph.
   /// \param[out] InverseMap An optional map from nodes in the returned graph to
   ///                        nodes in this graph.
   /// \returns The trimmed graph
   std::unique_ptr<ExplodedGraph>
   trim(ArrayRef<const NodeTy *> Nodes,
        InterExplodedGraphMap *ForwardMap = nullptr,
        InterExplodedGraphMap *InverseMap = nullptr) const;
 
   /// Enable tracking of recently allocated nodes for potential reclamation
   /// when calling reclaimRecentlyAllocatedNodes().
   void enableNodeReclamation(unsigned Interval) {
     ReclaimCounter = ReclaimNodeInterval = Interval;
   }
 
   /// Reclaim "uninteresting" nodes created since the last time this method
   /// was called.
   void reclaimRecentlyAllocatedNodes();
 
   /// Returns true if nodes for the given expression kind are always
   ///        kept around.
   static bool isInterestingLValueExpr(const Expr *Ex);
 
 private:
   bool shouldCollect(const ExplodedNode *node);
   void collectNode(ExplodedNode *node);
 };
 
 class ExplodedNodeSet {
   using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
   ImplTy Impl;
 
 public:
   ExplodedNodeSet(ExplodedNode *N) {
     assert(N && !static_cast<ExplodedNode*>(N)->isSink());
     Impl.insert(N);
   }
 
   ExplodedNodeSet() = default;
 
   void Add(ExplodedNode *N) {
     if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
   }
 
   using iterator = ImplTy::iterator;
   using const_iterator = ImplTy::const_iterator;
 
   unsigned size() const { return Impl.size();  }
   bool empty()    const { return Impl.empty(); }
   bool erase(ExplodedNode *N) { return Impl.remove(N); }
 
   void clear() { Impl.clear(); }
 
   void insert(const ExplodedNodeSet &S) {
     assert(&S != this);
     if (empty())
       Impl = S.Impl;
     else
       Impl.insert(S.begin(), S.end());
   }
 
   iterator begin() { return Impl.begin(); }
   iterator end() { return Impl.end(); }
 
   const_iterator begin() const { return Impl.begin(); }
   const_iterator end() const { return Impl.end(); }
 };
 
 } // namespace ento
 
 } // namespace clang
 
 // GraphTraits
 
 namespace llvm {
   template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
     using GraphTy = clang::ento::ExplodedGraph *;
     using NodeRef = clang::ento::ExplodedNode *;
     using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
     using nodes_iterator = llvm::df_iterator<GraphTy>;
 
     static NodeRef getEntryNode(const GraphTy G) {
       return *G->roots_begin();
     }
 
     static bool predecessorOfTrivial(NodeRef N) {
       return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
     }
 
     static ChildIteratorType child_begin(NodeRef N) {
       if (predecessorOfTrivial(N))
         return child_begin(*N->succ_begin());
       return N->succ_begin();
     }
 
     static ChildIteratorType child_end(NodeRef N) {
       if (predecessorOfTrivial(N))
         return child_end(N->getFirstSucc());
       return N->succ_end();
     }
 
     static nodes_iterator nodes_begin(const GraphTy G) {
       return df_begin(G);
     }
 
     static nodes_iterator nodes_end(const GraphTy G) {
       return df_end(G);
     }
   };
 } // namespace llvm
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team