contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

   1 //=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- C++ -*-------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines the template classes ExplodedNode and ExplodedGraph,
  11 //  which represent a path-sensitive, intra-procedural "exploded graph."
  12 //  See "Precise interprocedural dataflow analysis via graph reachability"
  13 //  by Reps, Horwitz, and Sagiv
  14 //  (http://portal.acm.org/citation.cfm?id=199462) for the definition of an
  15 //  exploded graph.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
  20 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
  21
  22 #include "clang/AST/Decl.h"
  23 #include "clang/Analysis/AnalysisContext.h"
  24 #include "clang/Analysis/ProgramPoint.h"
  25 #include "clang/Analysis/Support/BumpVector.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  27 #include "llvm/ADT/DepthFirstIterator.h"
  28 #include "llvm/ADT/FoldingSet.h"
  29 #include "llvm/ADT/GraphTraits.h"
  30 #include "llvm/ADT/SmallPtrSet.h"
  31 #include "llvm/ADT/SmallVector.h"
  32 #include "llvm/Support/Allocator.h"
  33 #include "llvm/Support/Casting.h"
  34 #include <memory>
  35 #include <vector>
  36
  37 namespace clang {
  38
  39 class CFG;
  40
  41 namespace ento {
  42
  43 class ExplodedGraph;
  44
  45 //===----------------------------------------------------------------------===//
  46 // ExplodedGraph "implementation" classes.  These classes are not typed to
  47 // contain a specific kind of state.  Typed-specialized versions are defined
  48 // on top of these classes.
  49 //===----------------------------------------------------------------------===//
  50
  51 // ExplodedNode is not constified all over the engine because we need to add
  52 // successors to it at any time after creating it.
  53
  54 class ExplodedNode : public llvm::FoldingSetNode {
  55   friend class ExplodedGraph;
  56   friend class CoreEngine;
  57   friend class NodeBuilder;
  58   friend class BranchNodeBuilder;
  59   friend class IndirectGotoNodeBuilder;
  60   friend class SwitchNodeBuilder;
  61   friend class EndOfFunctionNodeBuilder;
  62
  63   /// Efficiently stores a list of ExplodedNodes, or an optional flag.
  64   ///
  65   /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
  66   /// for the case when there is only one node in the group. This is a fairly
  67   /// common case in an ExplodedGraph, where most nodes have only one
  68   /// predecessor and many have only one successor. It can also be used to
  69   /// store a flag rather than a node list, which ExplodedNode uses to mark
  70   /// whether a node is a sink. If the flag is set, the group is implicitly
  71   /// empty and no nodes may be added.
  72   class NodeGroup {
  73     // Conceptually a discriminated union. If the low bit is set, the node is
  74     // a sink. If the low bit is not set, the pointer refers to the storage
  75     // for the nodes in the group.
  76     // This is not a PointerIntPair in order to keep the storage type opaque.
  77     uintptr_t P;
  78
  79   public:
  80     NodeGroup(bool Flag = false) : P(Flag) {
  81       assert(getFlag() == Flag);
  82     }
  83
  84     ExplodedNode * const *begin() const;
  85
  86     ExplodedNode * const *end() const;
  87
  88     unsigned size() const;
  89
  90     bool empty() const { return P == 0 || getFlag() != 0; }
  91
  92     /// Adds a node to the list.
  93     ///
  94     /// The group must not have been created with its flag set.
  95     void addNode(ExplodedNode *N, ExplodedGraph &G);
  96
  97     /// Replaces the single node in this group with a new node.
  98     ///
  99     /// Note that this should only be used when you know the group was not
 100     /// created with its flag set, and that the group is empty or contains
 101     /// only a single node.
 102     void replaceNode(ExplodedNode *node);
 103
 104     /// Returns whether this group was created with its flag set.
 105     bool getFlag() const {
 106       return (P & 1);
 107     }
 108   };
 109
 110   /// Location - The program location (within a function body) associated
 111   ///  with this node.
 112   const ProgramPoint Location;
 113
 114   /// State - The state associated with this node.
 115   ProgramStateRef State;
 116
 117   /// Preds - The predecessors of this node.
 118   NodeGroup Preds;
 119
 120   /// Succs - The successors of this node.
 121   NodeGroup Succs;
 122
 123 public:
 124
 125   explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
 126                         bool IsSink)
 127     : Location(loc), State(state), Succs(IsSink) {
 128     assert(isSink() == IsSink);
 129   }
 130
 131   /// getLocation - Returns the edge associated with the given node.
 132   ProgramPoint getLocation() const { return Location; }
 133
 134   const LocationContext *getLocationContext() const {
 135     return getLocation().getLocationContext();
 136   }
 137
 138   const StackFrameContext *getStackFrame() const {
 139     return getLocationContext()->getCurrentStackFrame();
 140   }
 141
 142   const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
 143
 144   CFG &getCFG() const { return *getLocationContext()->getCFG(); }
 145
 146   ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
 147
 148   template <typename T>
 149   T &getAnalysis() const {
 150     return *getLocationContext()->getAnalysis<T>();
 151   }
 152
 153   const ProgramStateRef &getState() const { return State; }
 154
 155   template <typename T>
 156   Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
 157     return Location.getAs<T>();
 158   }
 159
 160   static void Profile(llvm::FoldingSetNodeID &ID,
 161                       const ProgramPoint &Loc,
 162                       const ProgramStateRef &state,
 163                       bool IsSink) {
 164     ID.Add(Loc);
 165     ID.AddPointer(state.get());
 166     ID.AddBoolean(IsSink);
 167   }
 168
 169   void Profile(llvm::FoldingSetNodeID& ID) const {
 170     // We avoid copy constructors by not using accessors.
 171     Profile(ID, Location, State, isSink());
 172   }
 173
 174   /// addPredeccessor - Adds a predecessor to the current node, and
 175   ///  in tandem add this node as a successor of the other node.
 176   void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
 177
 178   unsigned succ_size() const { return Succs.size(); }
 179   unsigned pred_size() const { return Preds.size(); }
 180   bool succ_empty() const { return Succs.empty(); }
 181   bool pred_empty() const { return Preds.empty(); }
 182
 183   bool isSink() const { return Succs.getFlag(); }
 184
 185   bool hasSinglePred() const {
 186     return (pred_size() == 1);
 187   }
 188
 189   ExplodedNode *getFirstPred() {
 190     return pred_empty() ? nullptr : *(pred_begin());
 191   }
 192
 193   const ExplodedNode *getFirstPred() const {
 194     return const_cast<ExplodedNode*>(this)->getFirstPred();
 195   }
 196
 197   const ExplodedNode *getFirstSucc() const {
 198     return succ_empty() ? nullptr : *(succ_begin());
 199   }
 200
 201   // Iterators over successor and predecessor vertices.
 202   typedef ExplodedNode*       const *       succ_iterator;
 203   typedef const ExplodedNode* const * const_succ_iterator;
 204   typedef ExplodedNode*       const *       pred_iterator;
 205   typedef const ExplodedNode* const * const_pred_iterator;
 206
 207   pred_iterator pred_begin() { return Preds.begin(); }
 208   pred_iterator pred_end() { return Preds.end(); }
 209
 210   const_pred_iterator pred_begin() const {
 211     return const_cast<ExplodedNode*>(this)->pred_begin();
 212   }
 213   const_pred_iterator pred_end() const {
 214     return const_cast<ExplodedNode*>(this)->pred_end();
 215   }
 216
 217   succ_iterator succ_begin() { return Succs.begin(); }
 218   succ_iterator succ_end() { return Succs.end(); }
 219
 220   const_succ_iterator succ_begin() const {
 221     return const_cast<ExplodedNode*>(this)->succ_begin();
 222   }
 223   const_succ_iterator succ_end() const {
 224     return const_cast<ExplodedNode*>(this)->succ_end();
 225   }
 226
 227   // For debugging.
 228
 229 public:
 230
 231   class Auditor {
 232   public:
 233     virtual ~Auditor();
 234     virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0;
 235   };
 236
 237   static void SetAuditor(Auditor* A);
 238
 239 private:
 240   void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
 241   void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
 242 };
 243
 244 typedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>
 245         InterExplodedGraphMap;
 246
 247 class ExplodedGraph {
 248 protected:
 249   friend class CoreEngine;
 250
 251   // Type definitions.
 252   typedef std::vector<ExplodedNode *> NodeVector;
 253
 254   /// The roots of the simulation graph. Usually there will be only
 255   /// one, but clients are free to establish multiple subgraphs within a single
 256   /// SimulGraph. Moreover, these subgraphs can often merge when paths from
 257   /// different roots reach the same state at the same program location.
 258   NodeVector Roots;
 259
 260   /// The nodes in the simulation graph which have been
 261   /// specially marked as the endpoint of an abstract simulation path.
 262   NodeVector EndNodes;
 263
 264   /// Nodes - The nodes in the graph.
 265   llvm::FoldingSet<ExplodedNode> Nodes;
 266
 267   /// BVC - Allocator and context for allocating nodes and their predecessor
 268   /// and successor groups.
 269   BumpVectorContext BVC;
 270
 271   /// NumNodes - The number of nodes in the graph.
 272   unsigned NumNodes;
 273
 274   /// A list of recently allocated nodes that can potentially be recycled.
 275   NodeVector ChangedNodes;
 276
 277   /// A list of nodes that can be reused.
 278   NodeVector FreeNodes;
 279
 280   /// Determines how often nodes are reclaimed.
 281   ///
 282   /// If this is 0, nodes will never be reclaimed.
 283   unsigned ReclaimNodeInterval;
 284
 285   /// Counter to determine when to reclaim nodes.
 286   unsigned ReclaimCounter;
 287
 288 public:
 289
 290   /// \brief Retrieve the node associated with a (Location,State) pair,
 291   ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
 292   ///  this pair exists, it is created. IsNew is set to true if
 293   ///  the node was freshly created.
 294   ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
 295                         bool IsSink = false,
 296                         bool* IsNew = nullptr);
 297
 298   std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
 299     return llvm::make_unique<ExplodedGraph>();
 300   }
 301
 302   /// addRoot - Add an untyped node to the set of roots.
 303   ExplodedNode *addRoot(ExplodedNode *V) {
 304     Roots.push_back(V);
 305     return V;
 306   }
 307
 308   /// addEndOfPath - Add an untyped node to the set of EOP nodes.
 309   ExplodedNode *addEndOfPath(ExplodedNode *V) {
 310     EndNodes.push_back(V);
 311     return V;
 312   }
 313
 314   ExplodedGraph();
 315
 316   ~ExplodedGraph();
 317
 318   unsigned num_roots() const { return Roots.size(); }
 319   unsigned num_eops() const { return EndNodes.size(); }
 320
 321   bool empty() const { return NumNodes == 0; }
 322   unsigned size() const { return NumNodes; }
 323
 324   // Iterators.
 325   typedef ExplodedNode                        NodeTy;
 326   typedef llvm::FoldingSet<ExplodedNode>      AllNodesTy;
 327   typedef NodeVector::iterator                roots_iterator;
 328   typedef NodeVector::const_iterator          const_roots_iterator;
 329   typedef NodeVector::iterator                eop_iterator;
 330   typedef NodeVector::const_iterator          const_eop_iterator;
 331   typedef AllNodesTy::iterator                node_iterator;
 332   typedef AllNodesTy::const_iterator          const_node_iterator;
 333
 334   node_iterator nodes_begin() { return Nodes.begin(); }
 335
 336   node_iterator nodes_end() { return Nodes.end(); }
 337
 338   const_node_iterator nodes_begin() const { return Nodes.begin(); }
 339
 340   const_node_iterator nodes_end() const { return Nodes.end(); }
 341
 342   roots_iterator roots_begin() { return Roots.begin(); }
 343
 344   roots_iterator roots_end() { return Roots.end(); }
 345
 346   const_roots_iterator roots_begin() const { return Roots.begin(); }
 347
 348   const_roots_iterator roots_end() const { return Roots.end(); }
 349
 350   eop_iterator eop_begin() { return EndNodes.begin(); }
 351
 352   eop_iterator eop_end() { return EndNodes.end(); }
 353
 354   const_eop_iterator eop_begin() const { return EndNodes.begin(); }
 355
 356   const_eop_iterator eop_end() const { return EndNodes.end(); }
 357
 358   llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
 359   BumpVectorContext &getNodeAllocator() { return BVC; }
 360
 361   typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap;
 362
 363   /// Creates a trimmed version of the graph that only contains paths leading
 364   /// to the given nodes.
 365   ///
 366   /// \param Nodes The nodes which must appear in the final graph. Presumably
 367   ///              these are end-of-path nodes (i.e. they have no successors).
 368   /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
 369   ///                        the returned graph.
 370   /// \param[out] InverseMap An optional map from nodes in the returned graph to
 371   ///                        nodes in this graph.
 372   /// \returns The trimmed graph
 373   std::unique_ptr<ExplodedGraph>
 374   trim(ArrayRef<const NodeTy *> Nodes,
 375        InterExplodedGraphMap *ForwardMap = nullptr,
 376        InterExplodedGraphMap *InverseMap = nullptr) const;
 377
 378   /// Enable tracking of recently allocated nodes for potential reclamation
 379   /// when calling reclaimRecentlyAllocatedNodes().
 380   void enableNodeReclamation(unsigned Interval) {
 381     ReclaimCounter = ReclaimNodeInterval = Interval;
 382   }
 383
 384   /// Reclaim "uninteresting" nodes created since the last time this method
 385   /// was called.
 386   void reclaimRecentlyAllocatedNodes();
 387
 388   /// \brief Returns true if nodes for the given expression kind are always
 389   ///        kept around.
 390   static bool isInterestingLValueExpr(const Expr *Ex);
 391
 392 private:
 393   bool shouldCollect(const ExplodedNode *node);
 394   void collectNode(ExplodedNode *node);
 395 };
 396
 397 class ExplodedNodeSet {
 398   typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy;
 399   ImplTy Impl;
 400
 401 public:
 402   ExplodedNodeSet(ExplodedNode *N) {
 403     assert (N && !static_cast<ExplodedNode*>(N)->isSink());
 404     Impl.insert(N);
 405   }
 406
 407   ExplodedNodeSet() {}
 408
 409   inline void Add(ExplodedNode *N) {
 410     if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
 411   }
 412
 413   typedef ImplTy::iterator       iterator;
 414   typedef ImplTy::const_iterator const_iterator;
 415
 416   unsigned size() const { return Impl.size();  }
 417   bool empty()    const { return Impl.empty(); }
 418   bool erase(ExplodedNode *N) { return Impl.erase(N); }
 419
 420   void clear() { Impl.clear(); }
 421   void insert(const ExplodedNodeSet &S) {
 422     assert(&S != this);
 423     if (empty())
 424       Impl = S.Impl;
 425     else
 426       Impl.insert(S.begin(), S.end());
 427   }
 428
 429   inline iterator begin() { return Impl.begin(); }
 430   inline iterator end()   { return Impl.end();   }
 431
 432   inline const_iterator begin() const { return Impl.begin(); }
 433   inline const_iterator end()   const { return Impl.end();   }
 434 };
 435
 436 } // end GR namespace
 437
 438 } // end clang namespace
 439
 440 // GraphTraits
 441
 442 namespace llvm {
 443   template<> struct GraphTraits<clang::ento::ExplodedNode*> {
 444     typedef clang::ento::ExplodedNode NodeType;
 445     typedef NodeType::succ_iterator  ChildIteratorType;
 446     typedef llvm::df_iterator<NodeType*>      nodes_iterator;
 447
 448     static inline NodeType* getEntryNode(NodeType* N) {
 449       return N;
 450     }
 451
 452     static inline ChildIteratorType child_begin(NodeType* N) {
 453       return N->succ_begin();
 454     }
 455
 456     static inline ChildIteratorType child_end(NodeType* N) {
 457       return N->succ_end();
 458     }
 459
 460     static inline nodes_iterator nodes_begin(NodeType* N) {
 461       return df_begin(N);
 462     }
 463
 464     static inline nodes_iterator nodes_end(NodeType* N) {
 465       return df_end(N);
 466     }
 467   };
 468
 469   template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
 470     typedef const clang::ento::ExplodedNode NodeType;
 471     typedef NodeType::const_succ_iterator   ChildIteratorType;
 472     typedef llvm::df_iterator<NodeType*>       nodes_iterator;
 473
 474     static inline NodeType* getEntryNode(NodeType* N) {
 475       return N;
 476     }
 477
 478     static inline ChildIteratorType child_begin(NodeType* N) {
 479       return N->succ_begin();
 480     }
 481
 482     static inline ChildIteratorType child_end(NodeType* N) {
 483       return N->succ_end();
 484     }
 485
 486     static inline nodes_iterator nodes_begin(NodeType* N) {
 487       return df_begin(N);
 488     }
 489
 490     static inline nodes_iterator nodes_end(NodeType* N) {
 491       return df_end(N);
 492     }
 493   };
 494
 495 } // end llvm namespace
 496
 497 #endif