ExplodedGraph.h revision 2e287540c90255e14208e7e5f43f07cb752a1fd7
151125a21eafc29c925cac3655b46cfd8ef55f764Ted Kremenek//=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- C++ -*-------==//
24241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//
34241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//                     The LLVM Compiler Infrastructure
44241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//
54241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// This file is distributed under the University of Illinois Open Source
64241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// License. See LICENSE.TXT for details.
74241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//
84241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//===----------------------------------------------------------------------===//
94241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//
1051125a21eafc29c925cac3655b46cfd8ef55f764Ted Kremenek//  This file defines the template classes ExplodedNode and ExplodedGraph,
1151125a21eafc29c925cac3655b46cfd8ef55f764Ted Kremenek//  which represent a path-sensitive, intra-procedural "exploded graph."
124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//
134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//===----------------------------------------------------------------------===//
144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#ifndef LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH
164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#define LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH
174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "clang/Analysis/ProgramPoint.h"
1963bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek#include "clang/AST/Decl.h"
204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/SmallVector.h"
214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/FoldingSet.h"
22f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek#include "llvm/ADT/SmallPtrSet.h"
234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/Support/Allocator.h"
24ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek#include "llvm/ADT/OwningPtr.h"
254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/GraphTraits.h"
264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/DepthFirstIterator.h"
2763bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek#include "llvm/Support/Casting.h"
284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
294241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremeneknamespace clang {
304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
314d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenekclass GRCoreEngineImpl;
3237d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenekclass ExplodedNodeImpl;
3311062b118476368fa5b294954713e5df97d8599fTed Kremenekclass CFG;
3411062b118476368fa5b294954713e5df97d8599fTed Kremenekclass ASTContext;
3511062b118476368fa5b294954713e5df97d8599fTed Kremenek
36f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenekclass GRStmtNodeBuilderImpl;
377d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekclass GRBranchNodeBuilderImpl;
38754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekclass GRIndirectGotoNodeBuilderImpl;
39daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekclass GRSwitchNodeBuilderImpl;
4011062b118476368fa5b294954713e5df97d8599fTed Kremenekclass GREndPathNodebuilderImpl;
414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNodeImpl : public llvm::FoldingSetNode {
434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekprotected:
444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  friend class ExplodedGraphImpl;
454d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek  friend class GRCoreEngineImpl;
46f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenek  friend class GRStmtNodeBuilderImpl;
477d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek  friend class GRBranchNodeBuilderImpl;
48754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek  friend class GRIndirectGotoNodeBuilderImpl;
49daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek  friend class GRSwitchNodeBuilderImpl;
5011062b118476368fa5b294954713e5df97d8599fTed Kremenek  friend class GREndPathNodeBuilderImpl;
514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
524c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek  class NodeGroup {
53b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek    enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 };
544c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek    uintptr_t P;
554c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
56ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek    unsigned getKind() const {
57596f0a1e54f610926e8bfded9efa1c639f824dedTed Kremenek      return P & 0x1;
58ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek    }
59ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek
60ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek    void* getPtr() const {
61ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek      assert (!getFlag());
62b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek      return reinterpret_cast<void*>(P & ~Mask);
63ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek    }
64ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek
65ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek    ExplodedNodeImpl* getNode() const {
66ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek      return reinterpret_cast<ExplodedNodeImpl*>(getPtr());
67ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek    }
684c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
694c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek  public:
704c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek    NodeGroup() : P(0) {}
714c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
729eb49a40df510313132eef147419c5abefff23ebTed Kremenek    ~NodeGroup();
734c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
745d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek    ExplodedNodeImpl** begin() const;
754c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
765d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek    ExplodedNodeImpl** end() const;
774c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
785d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek    unsigned size() const;
794c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
80ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek    bool empty() const { return size() == 0; }
814c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
829eb49a40df510313132eef147419c5abefff23ebTed Kremenek    void addNode(ExplodedNodeImpl* N);
83f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
84b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek    void setFlag() {
85ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek      assert (P == 0);
86ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek      P = AuxFlag;
87f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek    }
88f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
89b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek    bool getFlag() const {
90b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek      return P & AuxFlag ? true : false;
91f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek    }
92b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek  };
934c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek
944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  /// Location - The program location (within a function body) associated
954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  ///  with this node.
964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  const ProgramPoint Location;
974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
984323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek  /// State - The state associated with this node.
994323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek  const void* State;
1004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  /// Preds - The predecessors of this node.
1024c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek  NodeGroup Preds;
1034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  /// Succs - The successors of this node.
1054c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek  NodeGroup Succs;
1064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  /// Construct a ExplodedNodeImpl with the provided location and state.
1084323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek  explicit ExplodedNodeImpl(const ProgramPoint& loc, const void* state)
1094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  : Location(loc), State(state) {}
1104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  /// addPredeccessor - Adds a predecessor to the current node, and
112f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  ///  in tandem add this node as a successor of the other node.
11345b8789258b282769b03cbeb68e9f5b0308f067bTed Kremenek  void addPredecessor(ExplodedNodeImpl* V);
1144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic:
116d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek
1174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  /// getLocation - Returns the edge associated with the given node.
1180f9063c116b7c3b05d8042b5976463c2dae04861Ted Kremenek  ProgramPoint getLocation() const { return Location; }
1194a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1204a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  unsigned succ_size() const { return Succs.size(); }
1214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  unsigned pred_size() const { return Preds.size(); }
1224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  bool succ_empty() const { return Succs.empty(); }
1230e8a3c743b9b3e3039e329a1736122d3b5b5fed9Ted Kremenek  bool pred_empty() const { return Preds.empty(); }
124f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
125ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  bool isSink() const { return Succs.getFlag(); }
1262e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek  void markAsSink() { Succs.setFlag(); }
1272e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek
1282e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek  // For debugging.
1292e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek
1302e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenekpublic:
1312e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek
1322e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek  class Auditor {
1332e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek  public:
1342e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek    virtual ~Auditor();
1352e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek    virtual void AddEdge(ExplodedNodeImpl* Src, ExplodedNodeImpl* Dst) = 0;
1362e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek  };
1372e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek
1382e287540c90255e14208e7e5f43f07cb752a1fd7Ted Kremenek  static void SetAuditor(Auditor* A);
1394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek};
1404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy>
1434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekstruct GRTrait {
144e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek  static inline void Profile(llvm::FoldingSetNodeID& ID, const StateTy* St) {
145e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek    St->Profile(ID);
1464a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  }
1474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek};
1484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy>
1514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNode : public ExplodedNodeImpl {
1524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic:
1534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  /// Construct a ExplodedNodeImpl with the given node ID, program edge,
1544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  ///  and state.
1554323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek  explicit ExplodedNode(const ProgramPoint& loc, const StateTy* St)
156e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek    : ExplodedNodeImpl(loc, St) {}
1574a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  /// getState - Returns the state associated with the node.
1594323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek  inline const StateTy* getState() const {
1604323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek    return static_cast<const StateTy*>(State);
1614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  }
1624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  // Profiling (for FoldingSet).
1647fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek
1657fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek  static inline void Profile(llvm::FoldingSetNodeID& ID,
1667fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek                             const ProgramPoint& Loc,
1674323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek                             const StateTy* state) {
1687fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek    ID.Add(Loc);
1697fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek    GRTrait<StateTy>::Profile(ID, state);
1707fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek  }
1717fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek
1724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  inline void Profile(llvm::FoldingSetNodeID& ID) const {
1737fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek    Profile(ID, getLocation(), getState());
1744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  }
1754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
176a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek  void addPredecessor(ExplodedNode* V) {
177a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek    ExplodedNodeImpl::addPredecessor(V);
178a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek  }
179a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek
1804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  // Iterators over successor and predecessor vertices.
1814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  typedef ExplodedNode**       succ_iterator;
1824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  typedef const ExplodedNode** const_succ_iterator;
1834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  typedef ExplodedNode**       pred_iterator;
18437d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek  typedef const ExplodedNode** const_pred_iterator;
1854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
18637d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek  pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); }
18737d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek  pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); }
1884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  const_pred_iterator pred_begin() const {
1904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    return const_cast<ExplodedNode*>(this)->pred_begin();
1914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  }
1924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  const_pred_iterator pred_end() const {
1934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    return const_cast<ExplodedNode*>(this)->pred_end();
1944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  }
1954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
19637d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek  succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); }
19737d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek  succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); }
1984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
1994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  const_succ_iterator succ_begin() const {
2004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    return const_cast<ExplodedNode*>(this)->succ_begin();
2014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  }
2024a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  const_succ_iterator succ_end() const {
2034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    return const_cast<ExplodedNode*>(this)->succ_end();
2044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  }
2054a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek};
2064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
2074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
2084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraphImpl {
2094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected:
2104d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek  friend class GRCoreEngineImpl;
211f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenek  friend class GRStmtNodeBuilderImpl;
2127d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek  friend class GRBranchNodeBuilderImpl;
213754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek  friend class GRIndirectGotoNodeBuilderImpl;
214daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek  friend class GRSwitchNodeBuilderImpl;
21511062b118476368fa5b294954713e5df97d8599fTed Kremenek  friend class GREndPathNodeBuilderImpl;
2164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
2174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  // Type definitions.
2184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  typedef llvm::SmallVector<ExplodedNodeImpl*,2>    RootsTy;
2194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  typedef llvm::SmallVector<ExplodedNodeImpl*,10>   EndNodesTy;
220ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek
2214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// Roots - The roots of the simulation graph. Usually there will be only
2224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// one, but clients are free to establish multiple subgraphs within a single
2234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// SimulGraph. Moreover, these subgraphs can often merge when paths from
2244241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// different roots reach the same state at the same program location.
2254241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  RootsTy Roots;
2264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
2274241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// EndNodes - The nodes in the simulation graph which have been
2284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  ///  specially marked as the endpoint of an abstract simulation path.
2294241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  EndNodesTy EndNodes;
2304241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
2314241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// Allocator - BumpPtrAllocator to create nodes.
2324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  llvm::BumpPtrAllocator Allocator;
233cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek
234cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek  /// cfg - The CFG associated with this analysis graph.
235cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek  CFG& cfg;
236cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek
23763bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  /// CodeDecl - The declaration containing the code being analyzed.  This
23863bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  ///  can be a FunctionDecl or and ObjCMethodDecl.
23963bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  Decl& CodeDecl;
240cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek
24163bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  /// Ctx - The ASTContext used to "interpret" CodeDecl.
242cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek  ASTContext& Ctx;
24339b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek
24439b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek  /// NumNodes - The number of nodes in the graph.
24539b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek  unsigned NumNodes;
2464241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
2474241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// getNodeImpl - Retrieve the node associated with a (Location,State)
2484241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  ///  pair, where 'State' is represented as an opaque void*.  This method
2494d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek  ///  is intended to be used only by GRCoreEngineImpl.
2504323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek  virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L,
2514323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek                                        const void* State,
252974c676306758c8c84f5c25e3708186557a678bdTed Kremenek                                        bool* IsNew) = 0;
253ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
254ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  virtual ExplodedGraphImpl* MakeEmptyGraph() const = 0;
2554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
2564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// addRoot - Add an untyped node to the set of roots.
257ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek  ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) {
258ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek    Roots.push_back(V);
259ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek    return V;
260ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek  }
2614241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
2624241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
263ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek  ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) {
264ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek    EndNodes.push_back(V);
265ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek    return V;
266ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek  }
267cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek
268cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek  // ctor.
26963bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  ExplodedGraphImpl(CFG& c, Decl& cd, ASTContext& ctx)
27063bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek    : cfg(c), CodeDecl(cd), Ctx(ctx), NumNodes(0) {}
2714241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
2724241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic:
2735226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek  virtual ~ExplodedGraphImpl() {}
2744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
2754241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  unsigned num_roots() const { return Roots.size(); }
2764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  unsigned num_eops() const { return EndNodes.size(); }
277cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek
27839b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek  bool empty() const { return NumNodes == 0; }
27939b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek  unsigned size() const { return NumNodes; }
28039b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek
281768ad16a4ab79fbc52f6f3bdc9362fd4e1d51d53Ted Kremenek  llvm::BumpPtrAllocator& getAllocator() { return Allocator; }
282cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek  CFG& getCFG() { return cfg; }
283cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek  ASTContext& getContext() { return Ctx; }
284a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek
285a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek  Decl& getCodeDecl() { return CodeDecl; }
28663bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  const Decl& getCodeDecl() const { return CodeDecl; }
28763bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek
28863bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  const FunctionDecl* getFunctionDecl() const {
28963bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek    return llvm::dyn_cast<FunctionDecl>(&CodeDecl);
29063bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  }
291ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
292ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  ExplodedGraphImpl* Trim(ExplodedNodeImpl** NBeg,
293ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek                          ExplodedNodeImpl** NEnd) const;
294ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
2954241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek};
2964241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
29750a6d0ce344c02782e0207574005c3b2aaa5077cTed Kremenektemplate <typename STATE>
2984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraph : public ExplodedGraphImpl {
2994241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic:
30050a6d0ce344c02782e0207574005c3b2aaa5077cTed Kremenek  typedef STATE                       StateTy;
3015226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek  typedef ExplodedNode<StateTy>       NodeTy;
3025226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek  typedef llvm::FoldingSet<NodeTy>    AllNodesTy;
303ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek
304cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenekprotected:
3055226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek  /// Nodes - The nodes in the graph.
3065226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek  AllNodesTy Nodes;
3075226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek
3084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected:
309ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L,
3104323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek                                        const void* State,
3114323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek                                        bool* IsNew) {
312ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
3134323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek    return getNode(L, static_cast<const StateTy*>(State), IsNew);
3144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
315ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
316ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  virtual ExplodedGraphImpl* MakeEmptyGraph() const {
31763bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek    return new ExplodedGraph(cfg, CodeDecl, Ctx);
318ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  }
3194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic:
32163bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek  ExplodedGraph(CFG& c, Decl& cd, ASTContext& ctx)
32250a6d0ce344c02782e0207574005c3b2aaa5077cTed Kremenek    : ExplodedGraphImpl(c, cd, ctx) {}
323ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek
3244241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  /// getNode - Retrieve the node associated with a (Location,State) pair,
32537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek  ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
3264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  ///  this pair exists, it is created.  IsNew is set to true if
3274241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  ///  the node was freshly created.
3284323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek  NodeTy* getNode(const ProgramPoint& L, const StateTy* State,
3294323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek                  bool* IsNew = NULL) {
3304241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3314241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    // Profile 'State' to determine if we already have an existing node.
3324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    llvm::FoldingSetNodeID profile;
3334241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    void* InsertPos = 0;
3344241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3357fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek    NodeTy::Profile(profile, L, State);
3365226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek    NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
3374241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3384241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    if (!V) {
3394241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek      // Allocate a new node.
3404241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek      V = (NodeTy*) Allocator.Allocate<NodeTy>();
341ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek      new (V) NodeTy(L, State);
3424241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3434241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek      // Insert the node into the node set and return it.
3445226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek      Nodes.InsertNode(V, InsertPos);
3454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
34639b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek      ++NumNodes;
34739b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek
3484241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek      if (IsNew) *IsNew = true;
3494241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    }
3504241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    else
3514241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek      if (IsNew) *IsNew = false;
3524241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3534241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    return V;
3544241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
3554241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  // Iterators.
3577ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  typedef NodeTy**                            roots_iterator;
3587ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  typedef const NodeTy**                      const_roots_iterator;
3597ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  typedef NodeTy**                            eop_iterator;
3607ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  typedef const NodeTy**                      const_eop_iterator;
3617ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  typedef typename AllNodesTy::iterator       node_iterator;
3627ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  typedef typename AllNodesTy::const_iterator const_node_iterator;
3637ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek
3647ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  node_iterator nodes_begin() {
3657ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek    return Nodes.begin();
3667ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  }
3677ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek
3687ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  node_iterator nodes_end() {
3697ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek    return Nodes.end();
3707ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  }
3714241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3727ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  const_node_iterator nodes_begin() const {
3737ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek    return Nodes.begin();
3747ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  }
3757ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek
3767ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  const_node_iterator nodes_end() const {
3777ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek    return Nodes.end();
3787ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek  }
3794241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3804241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  roots_iterator roots_begin() {
3811501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek    return reinterpret_cast<roots_iterator>(Roots.begin());
3824241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
3834241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3844241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  roots_iterator roots_end() {
3851501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek    return reinterpret_cast<roots_iterator>(Roots.end());
3864241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
3874241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3884241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  const_roots_iterator roots_begin() const {
3894241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    return const_cast<ExplodedGraph>(this)->roots_begin();
3904241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
3914241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3924241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  const_roots_iterator roots_end() const {
3934241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    return const_cast<ExplodedGraph>(this)->roots_end();
3944241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
3954241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
3964241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  eop_iterator eop_begin() {
3971501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek    return reinterpret_cast<eop_iterator>(EndNodes.begin());
3984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
3994241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
4004241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  eop_iterator eop_end() {
4011501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek    return reinterpret_cast<eop_iterator>(EndNodes.end());
4024241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
4034241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
4044241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  const_eop_iterator eop_begin() const {
4054241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    return const_cast<ExplodedGraph>(this)->eop_begin();
4064241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
4074241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
4084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  const_eop_iterator eop_end() const {
4094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek    return const_cast<ExplodedGraph>(this)->eop_end();
4104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek  }
411ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
412ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  // Utility.
413ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
414ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  ExplodedGraph* Trim(NodeTy** NBeg, NodeTy** NEnd) const {
415ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
416ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek    if (NBeg == NEnd)
417ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek      return NULL;
418ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
419ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek    assert (NBeg < NEnd);
420ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
421ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek    ExplodedNodeImpl** NBegImpl = (ExplodedNodeImpl**) NBeg;
422ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek    ExplodedNodeImpl** NEndImpl = (ExplodedNodeImpl**) NEnd;
423ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek
424ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek    return static_cast<ExplodedGraph*>(ExplodedGraphImpl::Trim(NBegImpl,
425ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek                                                               NEndImpl));
426ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek  }
4274241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek};
4284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
429f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
430330dddd19406f9cc227e59e0bb0a36ecdc52915eTed Kremenektemplate <typename StateTy>
431f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekclass ExplodedNodeSet {
432f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
433330dddd19406f9cc227e59e0bb0a36ecdc52915eTed Kremenek  typedef ExplodedNode<StateTy>        NodeTy;
434f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  typedef llvm::SmallPtrSet<NodeTy*,5> ImplTy;
435f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  ImplTy Impl;
436f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
437f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekpublic:
438f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  ExplodedNodeSet(NodeTy* N) {
439f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek    assert (N && !static_cast<ExplodedNodeImpl*>(N)->isSink());
440f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek    Impl.insert(N);
441f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  }
442f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
443f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  ExplodedNodeSet() {}
444f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
445f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  inline void Add(NodeTy* N) {
446f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek    if (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()) Impl.insert(N);
447f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  }
448f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
449f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  typedef typename ImplTy::iterator       iterator;
450f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  typedef typename ImplTy::const_iterator const_iterator;
451f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
452f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  inline unsigned size() const { return Impl.size();  }
453f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  inline bool empty()    const { return Impl.empty(); }
4544bf38da038cebf9396470630c3c39519e41706daTed Kremenek
4554bf38da038cebf9396470630c3c39519e41706daTed Kremenek  inline void clear() { Impl.clear(); }
456f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
457f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  inline iterator begin() { return Impl.begin(); }
458f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  inline iterator end()   { return Impl.end();   }
459f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
460f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  inline const_iterator begin() const { return Impl.begin(); }
461f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek  inline const_iterator end()   const { return Impl.end();   }
462f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek};
463f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek
4644241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek} // end clang namespace
4654241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek
4664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek// GraphTraits
4674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
4684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremeneknamespace llvm {
4694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  template<typename StateTy>
4704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  struct GraphTraits<clang::ExplodedNode<StateTy>*> {
4714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    typedef clang::ExplodedNode<StateTy>      NodeType;
4724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    typedef typename NodeType::succ_iterator  ChildIteratorType;
4734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    typedef llvm::df_iterator<NodeType*>      nodes_iterator;
4744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
4754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline NodeType* getEntryNode(NodeType* N) {
4764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return N;
4774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
4784a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
4794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline ChildIteratorType child_begin(NodeType* N) {
4804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return N->succ_begin();
4814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
4824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
4834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline ChildIteratorType child_end(NodeType* N) {
4844a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return N->succ_end();
4854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
4864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
4874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline nodes_iterator nodes_begin(NodeType* N) {
4884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return df_begin(N);
4894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
4904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
4914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline nodes_iterator nodes_end(NodeType* N) {
4924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return df_end(N);
4934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
4944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  };
4954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
4964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  template<typename StateTy>
4974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  struct GraphTraits<const clang::ExplodedNode<StateTy>*> {
4984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    typedef const clang::ExplodedNode<StateTy> NodeType;
4994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    typedef typename NodeType::succ_iterator   ChildIteratorType;
5004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    typedef llvm::df_iterator<NodeType*>       nodes_iterator;
5014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
5024a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline NodeType* getEntryNode(NodeType* N) {
5034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return N;
5044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
5054a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
5064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline ChildIteratorType child_begin(NodeType* N) {
5074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return N->succ_begin();
5084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
5094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
5104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline ChildIteratorType child_end(NodeType* N) {
5114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return N->succ_end();
5124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
5134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
5144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline nodes_iterator nodes_begin(NodeType* N) {
5154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return df_begin(N);
5164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
5174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
5184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    static inline nodes_iterator nodes_end(NodeType* N) {
5194a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek      return df_end(N);
5204a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek    }
5214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek  };
5224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
5234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek} // end llvm namespace
5244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek
5254241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#endif
526