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