ExplodedGraph.h revision 6800ba622e4edf287801ac69c42c61e7e294b06b
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." 12b2213dc3dd8f58b611b91d2fce4834a767efcba7Jeffrey Yasskin// See "Precise interprocedural dataflow analysis via graph reachability" 13b2213dc3dd8f58b611b91d2fce4834a767efcba7Jeffrey Yasskin// by Reps, Horwitz, and Sagiv 14b2213dc3dd8f58b611b91d2fce4834a767efcba7Jeffrey Yasskin// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 15b2213dc3dd8f58b611b91d2fce4834a767efcba7Jeffrey Yasskin// exploded graph. 164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// 174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//===----------------------------------------------------------------------===// 184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 195a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis#ifndef LLVM_CLANG_GR_EXPLODEDGRAPH 205a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis#define LLVM_CLANG_GR_EXPLODEDGRAPH 214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "clang/Analysis/ProgramPoint.h" 231309f9a3b225ea846e5822691c39a77423125505Ted Kremenek#include "clang/Analysis/AnalysisContext.h" 2463bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek#include "clang/AST/Decl.h" 254241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/SmallVector.h" 264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/FoldingSet.h" 27f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek#include "llvm/ADT/SmallPtrSet.h" 284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/Support/Allocator.h" 29ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek#include "llvm/ADT/OwningPtr.h" 304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/GraphTraits.h" 314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/DepthFirstIterator.h" 3263bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek#include "llvm/Support/Casting.h" 335fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#include "clang/Analysis/Support/BumpVector.h" 3418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 354241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 364241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremeneknamespace clang { 374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3811062b118476368fa5b294954713e5df97d8599fTed Kremenekclass CFG; 395a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 409ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento { 415a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 425fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekclass ExplodedGraph; 4311062b118476368fa5b294954713e5df97d8599fTed Kremenek 44cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek//===----------------------------------------------------------------------===// 45cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek// ExplodedGraph "implementation" classes. These classes are not typed to 46cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek// contain a specific kind of state. Typed-specialized versions are defined 47cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek// on top of these classes. 48cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek//===----------------------------------------------------------------------===// 491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 50bda1efd0daf6fca9f515c6ce38d1ed71a3cca5b7Zhongxing Xu// ExplodedNode is not constified all over the engine because we need to add 51bda1efd0daf6fca9f515c6ce38d1ed71a3cca5b7Zhongxing Xu// successors to it at any time after creating it. 52bda1efd0daf6fca9f515c6ce38d1ed71a3cca5b7Zhongxing Xu 53c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xuclass ExplodedNode : public llvm::FoldingSetNode { 5438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu friend class ExplodedGraph; 55d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CoreEngine; 56a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks friend class NodeBuilder; 57d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class BranchNodeBuilder; 58d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 59d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 60e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek friend class EndOfFunctionNodeBuilder; 611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 624c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek class NodeGroup { 63b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 }; 644c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek uintptr_t P; 651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 66ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek unsigned getKind() const { 67596f0a1e54f610926e8bfded9efa1c639f824dedTed Kremenek return P & 0x1; 68ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 709c378f705405d37f49795d5e915989de774fe11fTed Kremenek void *getPtr() const { 71ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek assert (!getFlag()); 72b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return reinterpret_cast<void*>(P & ~Mask); 73ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 74ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 75c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode *getNode() const { 76c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu return reinterpret_cast<ExplodedNode*>(getPtr()); 77ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 78d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 794c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek public: 804c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup() : P(0) {} 811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 825fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ExplodedNode **begin() const; 831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 845fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ExplodedNode **end() const; 851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 865d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek unsigned size() const; 871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 885fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek bool empty() const { return (P & ~Mask) == 0; } 891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 909c378f705405d37f49795d5e915989de774fe11fTed Kremenek void addNode(ExplodedNode *N, ExplodedGraph &G); 911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 92d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void replaceNode(ExplodedNode *node); 93d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 94b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek void setFlag() { 955fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek assert(P == 0); 96ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek P = AuxFlag; 97f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 99b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek bool getFlag() const { 100b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return P & AuxFlag ? true : false; 101f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 1021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump }; 1031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Location - The program location (within a function body) associated 1054a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// with this node. 1064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint Location; 1071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1084323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek /// State - The state associated with this node. 10918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State; 1101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Preds - The predecessors of this node. 1124c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Preds; 1131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Succs - The successors of this node. 1154c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Succs; 116c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 118c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1196800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks explicit ExplodedNode(const ProgramPoint &loc, const ProgramState *state, 1206800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks bool IsSink) 121e3115e257163321ecde429aeae75f1702f099d4cTed Kremenek : Location(loc), State(state) { 12218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const_cast<ProgramState*>(State)->incrementReferenceCount(); 1236800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks if (IsSink) 1246800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks Succs.setFlag(); 125e40b69de464bc695afcaf7ef9602ad727d77b981Ted Kremenek } 126e40b69de464bc695afcaf7ef9602ad727d77b981Ted Kremenek 127e40b69de464bc695afcaf7ef9602ad727d77b981Ted Kremenek ~ExplodedNode() { 12818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const_cast<ProgramState*>(State)->decrementReferenceCount(); 129e3115e257163321ecde429aeae75f1702f099d4cTed Kremenek } 130c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getLocation - Returns the edge associated with the given node. 1320f9063c116b7c3b05d8042b5976463c2dae04861Ted Kremenek ProgramPoint getLocation() const { return Location; } 133c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const LocationContext *getLocationContext() const { 1351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return getLocation().getLocationContext(); 13625e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu } 13725e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu 1385032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 1395032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu 1405032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu CFG &getCFG() const { return *getLocationContext()->getCFG(); } 1415032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu 142b317f8f5ca8737a5bbad97a3f7566a2dbd2ed61bZhongxing Xu ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} 143b317f8f5ca8737a5bbad97a3f7566a2dbd2ed61bZhongxing Xu 144a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek template <typename T> 145a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek T &getAnalysis() const { 146a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek return *getLocationContext()->getAnalysis<T>(); 147c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu } 148c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 14918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return State; } 150b317f8f5ca8737a5bbad97a3f7566a2dbd2ed61bZhongxing Xu 15152c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek template <typename T> 15252c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek const T* getLocationAs() const { return llvm::dyn_cast<T>(&Location); } 153c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump static void Profile(llvm::FoldingSetNodeID &ID, 1556800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks const ProgramPoint &Loc, 1566800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks const ProgramState *state, 1576800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks bool IsSink) { 1585fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ID.Add(Loc); 1595fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ID.AddPointer(state); 1606800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks ID.AddBoolean(IsSink); 1615fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 162c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 163c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu void Profile(llvm::FoldingSetNodeID& ID) const { 1646800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks Profile(ID, getLocation(), getState(), isSink()); 165c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu } 166c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump /// addPredeccessor - Adds a predecessor to the current node, and 168c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu /// in tandem add this node as a successor of the other node. 1699c378f705405d37f49795d5e915989de774fe11fTed Kremenek void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 170c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned succ_size() const { return Succs.size(); } 1724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned pred_size() const { return Preds.size(); } 1734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool succ_empty() const { return Succs.empty(); } 1740e8a3c743b9b3e3039e329a1736122d3b5b5fed9Ted Kremenek bool pred_empty() const { return Preds.empty(); } 1751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 176ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek bool isSink() const { return Succs.getFlag(); } 1774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1789c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getFirstPred() { 17952c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek return pred_empty() ? NULL : *(pred_begin()); 18052c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek } 1811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1829c378f705405d37f49795d5e915989de774fe11fTed Kremenek const ExplodedNode *getFirstPred() const { 18352c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek return const_cast<ExplodedNode*>(this)->getFirstPred(); 18452c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek } 1851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Iterators over successor and predecessor vertices. 1874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** succ_iterator; 1883148eb4a75f70f2636075c364d03104223f004d3Ted Kremenek typedef const ExplodedNode* const * const_succ_iterator; 1894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** pred_iterator; 1903148eb4a75f70f2636075c364d03104223f004d3Ted Kremenek typedef const ExplodedNode* const * const_pred_iterator; 1914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 192c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu pred_iterator pred_begin() { return Preds.begin(); } 193c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu pred_iterator pred_end() { return Preds.end(); } 1944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_begin() const { 1964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_begin(); 1971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 1984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_end() const { 1994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_end(); 2004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 2014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 202c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu succ_iterator succ_begin() { return Succs.begin(); } 203c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu succ_iterator succ_end() { return Succs.end(); } 2044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2054a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_begin() const { 2064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_begin(); 2074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 2084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_end() const { 2094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_end(); 2104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 211c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 212c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu // For debugging. 2131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 214c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xupublic: 2151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 216c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu class Auditor { 217c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu public: 218c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu virtual ~Auditor(); 2199c378f705405d37f49795d5e915989de774fe11fTed Kremenek virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; 220c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu }; 2211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 222c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu static void SetAuditor(Auditor* A); 223d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 224d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenekprivate: 225d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } 226d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 227c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu}; 228c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 22938b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu// FIXME: Is this class necessary? 23038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xuclass InterExplodedGraphMap { 23138b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::DenseMap<const ExplodedNode*, ExplodedNode*> M; 2321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump friend class ExplodedGraph; 233c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 23438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xupublic: 2359c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getMappedNode(const ExplodedNode *N) const; 2361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2377177dee8aee4b432911c91f1b788963bec0cac9fDaniel Dunbar InterExplodedGraphMap() {} 23838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu virtual ~InterExplodedGraphMap() {} 2394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 2404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 24138b02b912e1a55c912f603c4369431264d36a381Zhongxing Xuclass ExplodedGraph { 2424241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 243d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CoreEngine; 244e96de2dfde487211fb52f9139cdcae64d051a406Zhongxing Xu 2454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Type definitions. 246686775deca8b8685eb90801495880e3abdd844c2Chris Lattner typedef SmallVector<ExplodedNode*,2> RootsTy; 247686775deca8b8685eb90801495880e3abdd844c2Chris Lattner typedef SmallVector<ExplodedNode*,10> EndNodesTy; 2481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2494241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Roots - The roots of the simulation graph. Usually there will be only 2504241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// one, but clients are free to establish multiple subgraphs within a single 2514241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// SimulGraph. Moreover, these subgraphs can often merge when paths from 2524241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// different roots reach the same state at the same program location. 2534241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek RootsTy Roots; 2544241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2554241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// EndNodes - The nodes in the simulation graph which have been 2564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// specially marked as the endpoint of an abstract simulation path. 2574241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek EndNodesTy EndNodes; 25838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 25938b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu /// Nodes - The nodes in the graph. 26038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::FoldingSet<ExplodedNode> Nodes; 26138b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 2625fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// BVC - Allocator and context for allocating nodes and their predecessor 2635fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// and successor groups. 2645fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek BumpVectorContext BVC; 2651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 26639b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek /// NumNodes - The number of nodes in the graph. 26739b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned NumNodes; 268d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 269d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// A list of recently allocated nodes that can potentially be recycled. 270d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void *recentlyAllocatedNodes; 271d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 272d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// A list of nodes that can be reused. 273d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void *freeNodes; 274d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 275d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// A flag that indicates whether nodes should be recycled. 276d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek bool reclaimNodes; 2774241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 27838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xupublic: 2796800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks 2806800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks /// \brief Retrieve the node associated with a (Location,State) pair, 28138b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu /// where the 'Location' is a ProgramPoint in the CFG. If no node for 2826800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks /// this pair exists, it is created. IsNew is set to true if 28338b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu /// the node was freshly created. 28418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *getNode(const ProgramPoint &L, const ProgramState *State, 2856800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks bool IsSink = false, 28638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu bool* IsNew = 0); 2871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 28838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu ExplodedGraph* MakeEmptyGraph() const { 289c77a55126fcad66fb086f8e100a494caa2496a2dZhongxing Xu return new ExplodedGraph(); 29038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu } 2914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2924241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addRoot - Add an untyped node to the set of roots. 2939c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *addRoot(ExplodedNode *V) { 294ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek Roots.push_back(V); 295ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 296ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 2974241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addEndOfPath - Add an untyped node to the set of EOP nodes. 2999c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *addEndOfPath(ExplodedNode *V) { 300ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek EndNodes.push_back(V); 301ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 302ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 30338b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 304824c547dc5d4451b9dbacc56621592fa010878f4Ted Kremenek ExplodedGraph() 305824c547dc5d4451b9dbacc56621592fa010878f4Ted Kremenek : NumNodes(0), recentlyAllocatedNodes(0), 306824c547dc5d4451b9dbacc56621592fa010878f4Ted Kremenek freeNodes(0), reclaimNodes(false) {} 3074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 308d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek ~ExplodedGraph(); 309d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 3104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned num_roots() const { return Roots.size(); } 3114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned num_eops() const { return EndNodes.size(); } 3121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 31339b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek bool empty() const { return NumNodes == 0; } 31439b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned size() const { return NumNodes; } 315c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 3164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Iterators. 31738b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef ExplodedNode NodeTy; 31838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef llvm::FoldingSet<ExplodedNode> AllNodesTy; 3197ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek typedef NodeTy** roots_iterator; 32038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef NodeTy* const * const_roots_iterator; 3217ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek typedef NodeTy** eop_iterator; 32238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef NodeTy* const * const_eop_iterator; 32338b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef AllNodesTy::iterator node_iterator; 32438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef AllNodesTy::const_iterator const_node_iterator; 3251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 32638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu node_iterator nodes_begin() { return Nodes.begin(); } 3277ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek 32838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu node_iterator nodes_end() { return Nodes.end(); } 3291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_node_iterator nodes_begin() const { return Nodes.begin(); } 3311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_node_iterator nodes_end() const { return Nodes.end(); } 3331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu roots_iterator roots_begin() { return Roots.begin(); } 3351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu roots_iterator roots_end() { return Roots.end(); } 3371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_roots_iterator roots_begin() const { return Roots.begin(); } 3391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const_roots_iterator roots_end() const { return Roots.end(); } 3414241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 34238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu eop_iterator eop_begin() { return EndNodes.begin(); } 3431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu eop_iterator eop_end() { return EndNodes.end(); } 3451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_eop_iterator eop_begin() const { return EndNodes.begin(); } 3471eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_eop_iterator eop_end() const { return EndNodes.end(); } 34938b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 3505fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } 3515fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek BumpVectorContext &getNodeAllocator() { return BVC; } 35238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 35338b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap; 35438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 355c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu std::pair<ExplodedGraph*, InterExplodedGraphMap*> 356fe9e543a2a363df7fcaa899367d3b2580b63b27cTed Kremenek Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd, 35738b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::DenseMap<const void*, const void*> *InverseMap = 0) const; 358cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek 35938b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu ExplodedGraph* TrimInternal(const ExplodedNode* const * NBeg, 36038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const ExplodedNode* const * NEnd, 36138b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu InterExplodedGraphMap *M, 36238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::DenseMap<const void*, const void*> *InverseMap) const; 363d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 364d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// Enable tracking of recently allocated nodes for potential reclamation 365d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// when calling reclaimRecentlyAllocatedNodes(). 366d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void enableNodeReclamation() { reclaimNodes = true; } 367d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 368d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// Reclaim "uninteresting" nodes created since the last time this method 369d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// was called. 370d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void reclaimRecentlyAllocatedNodes(); 3714241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 372cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek 373f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekclass ExplodedNodeSet { 374c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy; 375f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ImplTy Impl; 3761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 377f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekpublic: 3789c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNodeSet(ExplodedNode *N) { 379c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu assert (N && !static_cast<ExplodedNode*>(N)->isSink()); 380f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek Impl.insert(N); 381f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 3821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 383f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ExplodedNodeSet() {} 3841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3859c378f705405d37f49795d5e915989de774fe11fTed Kremenek inline void Add(ExplodedNode *N) { 386c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); 387f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 3881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 389c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef ImplTy::iterator iterator; 390c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef ImplTy::const_iterator const_iterator; 391f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 392fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek unsigned size() const { return Impl.size(); } 393fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek bool empty() const { return Impl.empty(); } 3941aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks bool erase(ExplodedNode *N) { return Impl.erase(N); } 395fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek 396fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek void clear() { Impl.clear(); } 397fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek void insert(const ExplodedNodeSet &S) { 3982d950b15b2b2b650b102ecf0c6b50b45e0cb6a8aAnna Zaks assert(&S != this); 399fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek if (empty()) 400fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek Impl = S.Impl; 401fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek else 402fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek Impl.insert(S.begin(), S.end()); 403fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek } 4041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 405f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator begin() { return Impl.begin(); } 406f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator end() { return Impl.end(); } 4071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 408f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator begin() const { return Impl.begin(); } 409f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator end() const { return Impl.end(); } 4101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump}; 4111eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4125a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 4135a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 4144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek} // end clang namespace 4154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 4164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek// GraphTraits 4174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremeneknamespace llvm { 4199ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek template<> struct GraphTraits<clang::ento::ExplodedNode*> { 4209ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek typedef clang::ento::ExplodedNode NodeType; 421c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef NodeType::succ_iterator ChildIteratorType; 4224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4284a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4294a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4364a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4459ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek template<> struct GraphTraits<const clang::ento::ExplodedNode*> { 4469ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek typedef const clang::ento::ExplodedNode NodeType; 447c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef NodeType::const_succ_iterator ChildIteratorType; 4484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4564a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek} // end llvm namespace 4724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4734241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#endif 474