ExplodedGraph.h revision 72e93068c9f2a2f05f5932cdd917c0d2961f11d9
143dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis//=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- C++ -*-------==// 243dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 343dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// The LLVM Compiler Infrastructure 443dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 543dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// This file is distributed under the University of Illinois Open Source 643dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// License. See LICENSE.TXT for details. 743dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 843dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis//===----------------------------------------------------------------------===// 943dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 1043dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// This file defines the template classes ExplodedNode and ExplodedGraph, 1143dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// which represent a path-sensitive, intra-procedural "exploded graph." 1243dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// See "Precise interprocedural dataflow analysis via graph reachability" 1343dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// by Reps, Horwitz, and Sagiv 1443dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 1555fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth// exploded graph. 1655fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth// 17ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek//===----------------------------------------------------------------------===// 18f540c54701e3eeb34cb619a3a4eb18f1ac70ef2dJordan Rose 1955fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#ifndef LLVM_CLANG_GR_EXPLODEDGRAPH 2043dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#define LLVM_CLANG_GR_EXPLODEDGRAPH 2143dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis 2243dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#include "clang/Analysis/ProgramPoint.h" 2343dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#include "clang/Analysis/AnalysisContext.h" 24d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include "clang/AST/Decl.h" 25d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include "llvm/ADT/SmallVector.h" 26d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include "llvm/ADT/FoldingSet.h" 27d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include "llvm/ADT/SmallPtrSet.h" 2896479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose#include "llvm/Support/Allocator.h" 2996479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose#include "llvm/ADT/OwningPtr.h" 30d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include "llvm/ADT/GraphTraits.h" 31d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include "llvm/ADT/DepthFirstIterator.h" 32d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include "llvm/Support/Casting.h" 33344c77aac25e5d960aced3f45fbaa09853383f6dAnna Zaks#include "clang/Analysis/Support/BumpVector.h" 34d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 35d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis 36d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidisnamespace clang { 37d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis 38d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidisclass CFG; 3942e95acef35f4633119be1c1381e88878c966502Jordan Rose 40d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidisnamespace ento { 41d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis 42deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidisclass ExplodedGraph; 43deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis 44deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis//===----------------------------------------------------------------------===// 45deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis// ExplodedGraph "implementation" classes. These classes are not typed to 46deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis// contain a specific kind of state. Typed-specialized versions are defined 47deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis// on top of these classes. 48deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis//===----------------------------------------------------------------------===// 49deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis 50deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis// ExplodedNode is not constified all over the engine because we need to add 51deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis// successors to it at any time after creating it. 52769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 53769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidisclass ExplodedNode : public llvm::FoldingSetNode { 54769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis friend class ExplodedGraph; 55769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis friend class CoreEngine; 569fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis friend class NodeBuilder; 579fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis friend class BranchNodeBuilder; 589fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 599fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis friend class SwitchNodeBuilder; 609fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis friend class EndOfFunctionNodeBuilder; 619fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 629fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis class NodeGroup { 639fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 }; 649fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis uintptr_t P; 659fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 669fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis unsigned getKind() const { 679fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis return P & 0x1; 689fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis } 699fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 709fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis void *getPtr() const { 71769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis assert (!getFlag()); 729fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis return reinterpret_cast<void*>(P & ~Mask); 739fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis } 749fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 759fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis ExplodedNode *getNode() const { 769fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis return reinterpret_cast<ExplodedNode*>(getPtr()); 77769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 78769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 799fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis public: 809fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis NodeGroup() : P(0) {} 819fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 829fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis ExplodedNode **begin() const; 839fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 849fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis ExplodedNode **end() const; 85769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 86769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis unsigned size() const; 87769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 88769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis bool empty() const { return (P & ~Mask) == 0; } 89769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 90769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis void addNode(ExplodedNode *N, ExplodedGraph &G); 91769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 92769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis void replaceNode(ExplodedNode *node); 93769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 94c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis void setFlag() { 95c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis assert(P == 0); 96cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis P = AuxFlag; 978ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks } 988ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks 998ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks bool getFlag() const { 100769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return P & AuxFlag ? true : false; 101e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis } 102e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis }; 103e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 104769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// Location - The program location (within a function body) associated 105769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// with this node. 106769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const ProgramPoint Location; 107769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 108cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis /// State - The state associated with this node. 109cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis ProgramStateRef State; 110769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 111e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis /// Preds - The predecessors of this node. 112769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis NodeGroup Preds; 113769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 114769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// Succs - The successors of this node. 115769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis NodeGroup Succs; 116cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis 117769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidispublic: 118769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 119769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, 1208ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks bool IsSink) 121769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis : Location(loc), State(state) { 1228ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks if (IsSink) 1238ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks Succs.setFlag(); 1248ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks } 1258ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks 1268ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks ~ExplodedNode() {} 1278ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks 1288ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks /// getLocation - Returns the edge associated with the given node. 1298ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks ProgramPoint getLocation() const { return Location; } 130769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 131769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const LocationContext *getLocationContext() const { 1329fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis return getLocation().getLocationContext(); 1339fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis } 1349fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 135769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 136769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 1375f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner CFG &getCFG() const { return *getLocationContext()->getCFG(); } 138769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 139769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} 140769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 141769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis template <typename T> 14257c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose T &getAnalysis() const { 143769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return *getLocationContext()->getAnalysis<T>(); 144e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis } 145e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 146e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis ProgramStateRef getState() const { return State; } 147769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 148514f2c9dcb9e04b52929c5b141a6fe88bd68b33fTed Kremenek template <typename T> 149514f2c9dcb9e04b52929c5b141a6fe88bd68b33fTed Kremenek const T* getLocationAs() const { return llvm::dyn_cast<T>(&Location); } 15057c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose 151769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis static void Profile(llvm::FoldingSetNodeID &ID, 152769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const ProgramPoint &Loc, 1538ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks ProgramStateRef state, 154769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis bool IsSink) { 1553f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks ID.Add(Loc); 1563f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks ID.AddPointer(state.getPtr()); 1573f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks ID.AddBoolean(IsSink); 1583f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks } 15957c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose 160769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis void Profile(llvm::FoldingSetNodeID& ID) const { 161769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis Profile(ID, getLocation(), getState(), isSink()); 162769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 163769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 164769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// addPredeccessor - Adds a predecessor to the current node, and 165769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// in tandem add this node as a successor of the other node. 166769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 167769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 168cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis unsigned succ_size() const { return Succs.size(); } 169769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis unsigned pred_size() const { return Preds.size(); } 170514f2c9dcb9e04b52929c5b141a6fe88bd68b33fTed Kremenek bool succ_empty() const { return Succs.empty(); } 17157c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose bool pred_empty() const { return Preds.empty(); } 172e9a906b99286b44dcf5eb896f17df74d588e4ce9Benjamin Kramer 17357c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose bool isSink() const { return Succs.getFlag(); } 174c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis 175769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis ExplodedNode *getFirstPred() { 176769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return pred_empty() ? NULL : *(pred_begin()); 177769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 178769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 179769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const ExplodedNode *getFirstPred() const { 18057c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose return const_cast<ExplodedNode*>(this)->getFirstPred(); 181769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 182de507eaf3cb54d3cb234dc14499c10ab3373d15fJordan Rose 183769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis // Iterators over successor and predecessor vertices. 184769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typedef ExplodedNode** succ_iterator; 185e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis typedef const ExplodedNode* const * const_succ_iterator; 186e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis typedef ExplodedNode** pred_iterator; 187e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis typedef const ExplodedNode* const * const_pred_iterator; 188769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 18957c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose pred_iterator pred_begin() { return Preds.begin(); } 19057c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose pred_iterator pred_end() { return Preds.end(); } 19157c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose 19257c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose const_pred_iterator pred_begin() const { 193769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return const_cast<ExplodedNode*>(this)->pred_begin(); 194769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 1958ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks const_pred_iterator pred_end() const { 196d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose return const_cast<ExplodedNode*>(this)->pred_end(); 19757c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose } 1983f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks 199d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose succ_iterator succ_begin() { return Succs.begin(); } 200769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis succ_iterator succ_end() { return Succs.end(); } 201769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 202769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const_succ_iterator succ_begin() const { 203769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return const_cast<ExplodedNode*>(this)->succ_begin(); 204769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 205769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const_succ_iterator succ_end() const { 206769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return const_cast<ExplodedNode*>(this)->succ_end(); 207cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis } 208de507eaf3cb54d3cb234dc14499c10ab3373d15fJordan Rose 20957c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose // For debugging. 21057c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose 2113f8212787d9bd620930817177fbba5f32659377fArgyrios Kyrtzidispublic: 2123f8212787d9bd620930817177fbba5f32659377fArgyrios Kyrtzidis 2133f8212787d9bd620930817177fbba5f32659377fArgyrios Kyrtzidis class Auditor { 21457c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose public: 215c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis virtual ~Auditor(); 216769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; 217769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis }; 218769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 21996479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose static void SetAuditor(Auditor* A); 22096479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose 22196479da6ad9d921d875e7be29fe1bfa127be8069Jordan Roseprivate: 22296479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } 22357c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 22496479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose}; 22596479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose 22696479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose// FIXME: Is this class necessary? 22796479da6ad9d921d875e7be29fe1bfa127be8069Jordan Roseclass InterExplodedGraphMap { 22896479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose virtual void anchor(); 22996479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose llvm::DenseMap<const ExplodedNode*, ExplodedNode*> M; 23096479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose friend class ExplodedGraph; 23196479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose 23257c033621dacd8720ac9ff65a09025f14f70e22fJordan Rosepublic: 23357c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose ExplodedNode *getMappedNode(const ExplodedNode *N) const; 23457c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose 23557c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose InterExplodedGraphMap() {} 23696479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose virtual ~InterExplodedGraphMap() {} 23796479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose}; 23896479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose 239d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Roseclass ExplodedGraph { 24057c033621dacd8720ac9ff65a09025f14f70e22fJordan Roseprotected: 24196479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose friend class CoreEngine; 242d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose 24396479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose // Type definitions. 24496479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose typedef SmallVector<ExplodedNode*,2> RootsTy; 24596479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose typedef SmallVector<ExplodedNode*,10> EndNodesTy; 24696479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose 24796479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose /// Roots - The roots of the simulation graph. Usually there will be only 24896479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose /// one, but clients are free to establish multiple subgraphs within a single 24996479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose /// SimulGraph. Moreover, these subgraphs can often merge when paths from 25096479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose /// different roots reach the same state at the same program location. 25196479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose RootsTy Roots; 25257c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose 25357c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose /// EndNodes - The nodes in the simulation graph which have been 25496479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose /// specially marked as the endpoint of an abstract simulation path. 25596479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose EndNodesTy EndNodes; 25696479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose 25757c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose /// Nodes - The nodes in the graph. 25896479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose llvm::FoldingSet<ExplodedNode> Nodes; 25996479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose 26096479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose /// BVC - Allocator and context for allocating nodes and their predecessor 26196479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose /// and successor groups. 262769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis BumpVectorContext BVC; 263769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 264769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// NumNodes - The number of nodes in the graph. 265769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis unsigned NumNodes; 266769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 267bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek /// A list of recently allocated nodes that can potentially be recycled. 268bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek void *recentlyAllocatedNodes; 269769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 270769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// A list of nodes that can be reused. 271e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis void *freeNodes; 272e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 273e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis /// A flag that indicates whether nodes should be recycled. 274769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis bool reclaimNodes; 275bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek 276bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek /// Counter to determine when to reclaim nodes. 277bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek unsigned reclaimCounter; 278bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek 279bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenekpublic: 280769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 281769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// \brief Retrieve the node associated with a (Location,State) pair, 2828ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks /// where the 'Location' is a ProgramPoint in the CFG. If no node for 2833f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks /// this pair exists, it is created. IsNew is set to true if 2843f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks /// the node was freshly created. 285bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, 286bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek bool IsSink = false, 287bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek bool* IsNew = 0); 288bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek 289063e0887ad65d666d23ee3178436ad6507abbd1bAnna Zaks ExplodedGraph* MakeEmptyGraph() const { 290bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek return new ExplodedGraph(); 291769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 292769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 2939fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis /// addRoot - Add an untyped node to the set of roots. 2949fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis ExplodedNode *addRoot(ExplodedNode *V) { 295769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis Roots.push_back(V); 296ebae6d0209e1ec3d5ea14f9e63bd0d740218ed14Anna Zaks return V; 297769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 298cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis 299769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// addEndOfPath - Add an untyped node to the set of EOP nodes. 300bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek ExplodedNode *addEndOfPath(ExplodedNode *V) { 301bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek EndNodes.push_back(V); 302bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek return V; 303bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek } 304bd613137499b1d4c3b63dccd0aa21f6add243f4fTed Kremenek 305c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis ExplodedGraph(); 3069fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 3079fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis ~ExplodedGraph(); 308312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 309312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis unsigned num_roots() const { return Roots.size(); } 310312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis unsigned num_eops() const { return EndNodes.size(); } 311312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 312312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis bool empty() const { return NumNodes == 0; } 313312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis unsigned size() const { return NumNodes; } 314312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 315312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // Iterators. 3163682f1ea9c7fddc7dcbc590891158ba40f7fca16Jordan Rose typedef ExplodedNode NodeTy; 317312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis typedef llvm::FoldingSet<ExplodedNode> AllNodesTy; 318312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis typedef NodeTy** roots_iterator; 319312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis typedef NodeTy* const * const_roots_iterator; 320312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis typedef NodeTy** eop_iterator; 321312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis typedef NodeTy* const * const_eop_iterator; 322ebae6d0209e1ec3d5ea14f9e63bd0d740218ed14Anna Zaks typedef AllNodesTy::iterator node_iterator; 3233682f1ea9c7fddc7dcbc590891158ba40f7fca16Jordan Rose typedef AllNodesTy::const_iterator const_node_iterator; 3243682f1ea9c7fddc7dcbc590891158ba40f7fca16Jordan Rose 325312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis node_iterator nodes_begin() { return Nodes.begin(); } 326312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 3278ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks node_iterator nodes_end() { return Nodes.end(); } 3283682f1ea9c7fddc7dcbc590891158ba40f7fca16Jordan Rose 329063e0887ad65d666d23ee3178436ad6507abbd1bAnna Zaks const_node_iterator nodes_begin() const { return Nodes.begin(); } 3303f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks 331390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks const_node_iterator nodes_end() const { return Nodes.end(); } 332312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 333312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis roots_iterator roots_begin() { return Roots.begin(); } 334312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 335312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis roots_iterator roots_end() { return Roots.end(); } 336312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 337312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis const_roots_iterator roots_begin() const { return Roots.begin(); } 338312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 339312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis const_roots_iterator roots_end() const { return Roots.end(); } 340ebae6d0209e1ec3d5ea14f9e63bd0d740218ed14Anna Zaks 3413682f1ea9c7fddc7dcbc590891158ba40f7fca16Jordan Rose eop_iterator eop_begin() { return EndNodes.begin(); } 3423682f1ea9c7fddc7dcbc590891158ba40f7fca16Jordan Rose 343312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis eop_iterator eop_end() { return EndNodes.end(); } 344312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 345312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis const_eop_iterator eop_begin() const { return EndNodes.begin(); } 34630726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis 34730726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis const_eop_iterator eop_end() const { return EndNodes.end(); } 34830726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis 34930726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } 35030726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis BumpVectorContext &getNodeAllocator() { return BVC; } 35130726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis 35230726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap; 353af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis 354af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks std::pair<ExplodedGraph*, InterExplodedGraphMap*> 355af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd, 356344c77aac25e5d960aced3f45fbaa09853383f6dAnna Zaks llvm::DenseMap<const void*, const void*> *InverseMap = 0) const; 357344c77aac25e5d960aced3f45fbaa09853383f6dAnna Zaks 358344c77aac25e5d960aced3f45fbaa09853383f6dAnna Zaks ExplodedGraph* TrimInternal(const ExplodedNode* const * NBeg, 359344c77aac25e5d960aced3f45fbaa09853383f6dAnna Zaks const ExplodedNode* const * NEnd, 360af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks InterExplodedGraphMap *M, 361af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks llvm::DenseMap<const void*, const void*> *InverseMap) const; 362af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks 363af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks /// Enable tracking of recently allocated nodes for potential reclamation 364af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks /// when calling reclaimRecentlyAllocatedNodes(). 365344c77aac25e5d960aced3f45fbaa09853383f6dAnna Zaks void enableNodeReclamation() { reclaimNodes = true; } 366344c77aac25e5d960aced3f45fbaa09853383f6dAnna Zaks 367af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks /// Reclaim "uninteresting" nodes created since the last time this method 368af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks /// was called. 369af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks void reclaimRecentlyAllocatedNodes(); 370af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaks}; 371063e0887ad65d666d23ee3178436ad6507abbd1bAnna Zaks 372af498a28797c075c48d7e943df5f5a8e78ed8eb0Anna Zaksclass ExplodedNodeSet { 373af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy; 374af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis ImplTy Impl; 375af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis 376f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zakspublic: 377f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks ExplodedNodeSet(ExplodedNode *N) { 378f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks assert (N && !static_cast<ExplodedNode*>(N)->isSink()); 379f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks Impl.insert(N); 380f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks } 381f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks 382f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks ExplodedNodeSet() {} 383f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks 384f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks inline void Add(ExplodedNode *N) { 385f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); 386f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks } 387f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks 388f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks typedef ImplTy::iterator iterator; 389f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks typedef ImplTy::const_iterator const_iterator; 390f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks 391f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks unsigned size() const { return Impl.size(); } 392f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks bool empty() const { return Impl.empty(); } 393f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks bool erase(ExplodedNode *N) { return Impl.erase(N); } 394063e0887ad65d666d23ee3178436ad6507abbd1bAnna Zaks 395f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks void clear() { Impl.clear(); } 396f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks void insert(const ExplodedNodeSet &S) { 397f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks assert(&S != this); 398f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks if (empty()) 399f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks Impl = S.Impl; 400cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis else 401f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks Impl.insert(S.begin(), S.end()); 402f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks } 4034e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks 404cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis inline iterator begin() { return Impl.begin(); } 405f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks inline iterator end() { return Impl.end(); } 406f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks 407f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks inline const_iterator begin() const { return Impl.begin(); } 408f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks inline const_iterator end() const { return Impl.end(); } 409cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis}; 410cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis 411183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis} // end GR namespace 4128bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek 413183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis} // end clang namespace 414183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 415183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis// GraphTraits 416183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 417183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidisnamespace llvm { 418183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis template<> struct GraphTraits<clang::ento::ExplodedNode*> { 419183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis typedef clang::ento::ExplodedNode NodeType; 420183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis typedef NodeType::succ_iterator ChildIteratorType; 421183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis typedef llvm::df_iterator<NodeType*> nodes_iterator; 422183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 423183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis static inline NodeType* getEntryNode(NodeType* N) { 424183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis return N; 4250b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks } 426183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 427183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis static inline ChildIteratorType child_begin(NodeType* N) { 428183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis return N->succ_begin(); 429183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 430183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 4310b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks static inline ChildIteratorType child_end(NodeType* N) { 4320b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks return N->succ_end(); 4330b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks } 434183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 435183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis static inline nodes_iterator nodes_begin(NodeType* N) { 4368ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks return df_begin(N); 4370b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks } 4383f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks 439063e0887ad65d666d23ee3178436ad6507abbd1bAnna Zaks static inline nodes_iterator nodes_end(NodeType* N) { 4403f5e8d87dbf449d8b39fe96068415428594d370eAnna Zaks return df_end(N); 4410b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks } 4420b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks }; 4430b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 444183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis template<> struct GraphTraits<const clang::ento::ExplodedNode*> { 445183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis typedef const clang::ento::ExplodedNode NodeType; 446183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis typedef NodeType::const_succ_iterator ChildIteratorType; 447183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis typedef llvm::df_iterator<NodeType*> nodes_iterator; 448183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 449183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis static inline NodeType* getEntryNode(NodeType* N) { 450183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis return N; 451183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 452183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 453183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis static inline ChildIteratorType child_begin(NodeType* N) { 4540b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks return N->succ_begin(); 4550b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks } 4560b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 457183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis static inline ChildIteratorType child_end(NodeType* N) { 458183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis return N->succ_end(); 459183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 460183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 4618bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 462183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis return df_begin(N); 463183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 464183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 465183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis static inline nodes_iterator nodes_end(NodeType* N) { 466183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis return df_end(N); 467183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 468183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis }; 469183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 4708bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek} // end llvm namespace 4718bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek 472bf53dfac8195835028bd6347433f7dbebcc29fc1Anna Zaks#endif 473537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose