ExplodedGraph.h revision 5d5480380d7b7c3590a0283ddf239220e514e576
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" 194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/SmallVector.h" 204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/FoldingSet.h" 214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/DenseMap.h" 224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/Support/Allocator.h" 23ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek#include "llvm/ADT/OwningPtr.h" 244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/GraphTraits.h" 254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/DepthFirstIterator.h" 264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 274241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremeneknamespace clang { 284a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 29974c676306758c8c84f5c25e3708186557a678bdTed Kremenekclass GREngineImpl; 3037d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenekclass ExplodedNodeImpl; 314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNodeImpl : public llvm::FoldingSetNode { 334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekprotected: 344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek friend class ExplodedGraphImpl; 354a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 364c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek class NodeGroup { 374c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek enum { Size1 = 0x0, SizeOther = 0x1, Flags = 0x1 }; 384c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek uintptr_t P; 394c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 404c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek unsigned getKind() const { return P & Flags; } 419eb49a40df510313132eef147419c5abefff23ebTed Kremenek void* getPtr() const { return reinterpret_cast<void*>(P & ~Flags); } 429eb49a40df510313132eef147419c5abefff23ebTed Kremenek ExplodedNodeImpl* getNode() const; 434c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 444c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek public: 454c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup() : P(0) {} 464c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 479eb49a40df510313132eef147419c5abefff23ebTed Kremenek ~NodeGroup(); 484c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 495d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek ExplodedNodeImpl** begin() const; 504c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 515d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek ExplodedNodeImpl** end() const; 524c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 535d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek unsigned size() const; 544c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 555d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek bool empty() const; 564c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 579eb49a40df510313132eef147419c5abefff23ebTed Kremenek void addNode(ExplodedNodeImpl* N); 584c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek }; 594c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 604c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Location - The program location (within a function body) associated 624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// with this node. 634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint Location; 644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// State - The state associated with this node. Normally this value 664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// is immutable, but we anticipate there will be times when algorithms 674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// that directly manipulate the analysis graph will need to change it. 684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void* State; 694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Preds - The predecessors of this node. 714c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Preds; 724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Succs - The successors of this node. 744c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Succs; 754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the provided location and state. 7737d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek explicit ExplodedNodeImpl(const ProgramPoint& loc, void* state) 784a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek : Location(loc), State(state) {} 794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// addPredeccessor - Adds a predecessor to the current node, and 814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// in tandem add this node as a successor of the other node. This 824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// method is intended to be used only by ExplodedGraphImpl. 834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void addPredecessor(ExplodedNodeImpl* V) { 844a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek Preds.addNode(V); 854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek V->Succs.addNode(this); 864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 89d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // This method is only defined so that we can cast a 90d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // void* to FoldingSet<ExplodedNodeImpl> so that we can iterate 91d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // over the vertices of EdgeNodeSetMap in ExplodeGraphImpl. 92d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // The actual profiling of vertices will be done in the derived 93d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // class, ExplodedNode<>. Nodes will NEVER be INSERTED into the 94d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // FoldingSet using this Profile method (since it doesn't do anything). 95d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek inline void Profile(llvm::FoldingSetNodeID& ID) const { 96d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek assert (false && "Needs to be implemented in derived class."); 97d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek } 98d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek 994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getLocation - Returns the edge associated with the given node. 1004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint& getLocation() const { return Location; } 1014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1024a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned succ_size() const { return Succs.size(); } 1034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned pred_size() const { return Preds.size(); } 1044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool succ_empty() const { return Succs.empty(); } 1054a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool pred_empty() const { return Preds.size(); } 1064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekstruct GRTrait { 1114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline void* toPtr(StateTy S) { 1124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return reinterpret_cast<void*>(S); 1134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline StateTy toState(void* P) { 1154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return reinterpret_cast<StateTy>(P); 1164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1194a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1204a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNode : public ExplodedNodeImpl { 1224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 1234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the given node ID, program edge, 1244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// and state. 12537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek explicit ExplodedNode(unsigned ID, const ProgramPoint& loc, StateTy state) 1264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek : ExplodedNodeImpl(ID, loc, GRTrait<StateTy>::toPtr(state)) {} 1274a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1284a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getState - Returns the state associated with the node. 1294a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek inline StateTy getState() const { 1304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return GRTrait<StateTy>::toState(State); 1314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Profiling (for FoldingSet). 1344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek inline void Profile(llvm::FoldingSetNodeID& ID) const { 1354a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek StateTy::Profile(ID, getState()); 1364a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Iterators over successor and predecessor vertices. 1394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** succ_iterator; 1404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const ExplodedNode** const_succ_iterator; 1414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** pred_iterator; 14237d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek typedef const ExplodedNode** const_pred_iterator; 1434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 14437d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); } 14537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); } 1464a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_begin() const { 1484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_begin(); 1494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_end() const { 1514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_end(); 1524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 15437d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); } 15537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); } 1564a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1574a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_begin() const { 1584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_begin(); 1594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_end() const { 1614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_end(); 1624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1664241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraphImpl { 1674241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 168974c676306758c8c84f5c25e3708186557a678bdTed Kremenek friend class GREngineImpl; 1694241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 1704241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Type definitions. 17190e2280fd242b02d9829365570ba3966217cb0e0Ted Kremenek typedef llvm::DenseMap<ProgramPoint,void*> EdgeNodeSetMap; 1724241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; 1734241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; 1744241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 1754241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// NodeCounter - The number of nodes that have been created, although 1764241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// this need not be the current number of nodes in the graph that 1774241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// are reachable from the roots. This counter is used to assign a unique 1784241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// number to each node (which is useful for debugging). 1794241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned NodeCounter; 1804241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 1814241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Roots - The roots of the simulation graph. Usually there will be only 1824241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// one, but clients are free to establish multiple subgraphs within a single 1834241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// SimulGraph. Moreover, these subgraphs can often merge when paths from 1844241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// different roots reach the same state at the same program location. 1854241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek RootsTy Roots; 1864241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 1874241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// EndNodes - The nodes in the simulation graph which have been 1884241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// specially marked as the endpoint of an abstract simulation path. 1894241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek EndNodesTy EndNodes; 1904241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 1914241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Nodes - A mapping from edges to nodes. 1924241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek EdgeNodeSetMap Nodes; 1934241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 1944241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Allocator - BumpPtrAllocator to create nodes. 1954241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::BumpPtrAllocator Allocator; 1964241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 1974241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNodeImpl - Retrieve the node associated with a (Location,State) 1984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// pair, where 'State' is represented as an opaque void*. This method 199974c676306758c8c84f5c25e3708186557a678bdTed Kremenek /// is intended to be used only by GREngineImpl. 20037d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, void* State, 201974c676306758c8c84f5c25e3708186557a678bdTed Kremenek bool* IsNew) = 0; 2024a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2034241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addRoot - Add an untyped node to the set of roots. 204ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { 205ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek Roots.push_back(V); 206ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 207ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 2084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addEndOfPath - Add an untyped node to the set of EOP nodes. 210ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { 211ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek EndNodes.push_back(V); 212ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 213ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 2144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 21690e2280fd242b02d9829365570ba3966217cb0e0Ted Kremenek virtual ~ExplodedGraphImpl(); 2174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned num_roots() const { return Roots.size(); } 2194a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned num_eops() const { return EndNodes.size(); } 2204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned getCounter() const { return NodeCounter; } 2214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 2224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 223ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenektemplate <typename CHECKER> 2244241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraph : public ExplodedGraphImpl { 2254241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 226ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef CHECKER CheckerTy; 227ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef typename CHECKER::StateTy StateTy; 228ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef ExplodedNode<StateTy> NodeTy; 229ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 230ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenekprotected: 231ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek llvm::OwningPtr<CheckerTy> CheckerState; 2324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2334241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 2344241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek virtual ExplodedNodeImpl* 23537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek getNodeImpl(const ProgramPoint& L, void* State, bool* IsNew) { 236974c676306758c8c84f5c25e3708186557a678bdTed Kremenek return getNode(L,GRTrait<StateTy>::toState(State),IsNew); 2374241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2384241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2394241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 240ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// getCheckerState - Returns the internal checker state associated 241ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// with the exploded graph. Ownership remains with the ExplodedGraph 242ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// objecct. 243ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek CheckerTy* getCheckerState() const { return CheckerState.get(); } 244ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 2454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNode - Retrieve the node associated with a (Location,State) pair, 24637d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek /// where the 'Location' is a ProgramPoint in the CFG. If no node for 2474241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// this pair exists, it is created. IsNew is set to true if 2484241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// the node was freshly created. 24937d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek NodeTy* getNode(const ProgramPoint& L, StateTy State, bool* IsNew = NULL) { 2504241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2514241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Retrieve the node set associated with Loc. 2524241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::FoldingSet<NodeTy>*& VSet = 2534241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek reinterpret_cast<llvm::FoldingSet<NodeTy>*&>(Nodes[L]); 2544241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2554241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Create the FoldingSet for the nodes if it does not exist yet. 2564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (!VSet) VSet = new llvm::FoldingSet<NodeTy>(); 2574241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2584241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Profile 'State' to determine if we already have an existing node. 2594241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::FoldingSetNodeID profile; 2604241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek void* InsertPos = 0; 2614241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2624241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek StateTy::Profile(profile, State); 263974c676306758c8c84f5c25e3708186557a678bdTed Kremenek NodeTy* V = VSet.FindNodeOrInsertPos(profile, InsertPos); 2644241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2654241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (!V) { 2664241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Allocate a new node. 2674241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek V = (NodeTy*) Allocator.Allocate<NodeTy>(); 268974c676306758c8c84f5c25e3708186557a678bdTed Kremenek new (V) NodeTy(NodeCounter++, L, State); 2694241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2704241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Insert the node into the node set and return it. 271974c676306758c8c84f5c25e3708186557a678bdTed Kremenek VSet.InsertNode(V, InsertPos); 2724241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2734241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = true; 2744241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2754241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek else 2764241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = false; 2774241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2784241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return V; 2794241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2804241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2814241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Iterators. 2824241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef NodeTy* roots_iterator; 2834241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef const NodeTy* const_roots_iterator; 2844241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef NodeTy* eop_iterator; 2854241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef const NodeTy* const_eop_iterator; 2864241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2874241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2884241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_begin() { 2894241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return static_cast<NodeTy*>(Roots.begin()); 2904241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2914241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2924241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_end() { 2934241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return static_cast<NodeTy*>(Roots.end()); 2944241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2954241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2964241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_begin() const { 2974241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_begin(); 2984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2994241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3004241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_end() const { 3014241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_end(); 3024241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3034241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3044241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_begin() { 3054241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return static_cast<NodeTy*>(EndNodes.begin()); 3064241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3074241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_end() { 3094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return static_cast<NodeTy*>(EndNodes.end()); 3104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_begin() const { 3134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_begin(); 3144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_end() const { 3174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_end(); 3184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 3204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek} // end clang namespace 3224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek// GraphTraits 3244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremeneknamespace llvm { 3264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 3274a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<clang::ExplodedNode<StateTy>*> { 3284a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef clang::ExplodedNode<StateTy> NodeType; 3294a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 3304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 3314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 3334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 3344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3354a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3364a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 3374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 3384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 3414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 3424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 3454a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 3464a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 3494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 3504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 3524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 3544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<const clang::ExplodedNode<StateTy>*> { 3554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const clang::ExplodedNode<StateTy> NodeType; 3564a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 3574a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 3584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 3604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 3614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 3644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 3654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 3684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 3694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 3724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 3734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 3764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 3774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3784a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 3794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek} // end llvm namespace 3814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3824241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#endif 383