ExplodedGraph.h revision f6f5ef4aaa66b60270e84d1fe1292886369d2f38
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" 21f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek#include "llvm/ADT/SmallPtrSet.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 294d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenekclass GRCoreEngineImpl; 3037d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenekclass ExplodedNodeImpl; 31f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenekclass GRStmtNodeBuilderImpl; 327d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekclass GRBranchNodeBuilderImpl; 33754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekclass GRIndirectGotoNodeBuilderImpl; 34daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekclass GRSwitchNodeBuilderImpl; 35cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenekclass CFG; 36cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenekclass ASTContext; 37cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenekclass FunctionDecl; 384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 39cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNodeImpl : public llvm::FoldingSetNode { 414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekprotected: 424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek friend class ExplodedGraphImpl; 434d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek friend class GRCoreEngineImpl; 44f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenek friend class GRStmtNodeBuilderImpl; 457d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek friend class GRBranchNodeBuilderImpl; 46754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek friend class GRIndirectGotoNodeBuilderImpl; 47daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek friend class GRSwitchNodeBuilderImpl; 484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 494c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek class NodeGroup { 50b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 }; 514c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek uintptr_t P; 524c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 53ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek unsigned getKind() const { 54b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return P & Mask; 55ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 56ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 57ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek void* getPtr() const { 58b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return reinterpret_cast<void*>(P & ~Mask); 59ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 60ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 61ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek ExplodedNodeImpl* getNode() const { 62ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek return reinterpret_cast<ExplodedNodeImpl*>(getPtr()); 63ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 644c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 654c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek public: 664c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup() : P(0) {} 674c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 689eb49a40df510313132eef147419c5abefff23ebTed Kremenek ~NodeGroup(); 694c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 705d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek ExplodedNodeImpl** begin() const; 714c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 725d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek ExplodedNodeImpl** end() const; 734c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 745d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek unsigned size() const; 754c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 765d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek bool empty() const; 774c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 789eb49a40df510313132eef147419c5abefff23ebTed Kremenek void addNode(ExplodedNodeImpl* N); 79f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 80b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek void setFlag() { 81b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek P |= AuxFlag; 82f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 83f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 84b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek bool getFlag() const { 85b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return P & AuxFlag ? true : false; 86f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 87b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek }; 884c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Location - The program location (within a function body) associated 904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// with this node. 914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint Location; 924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// State - The state associated with this node. Normally this value 944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// is immutable, but we anticipate there will be times when algorithms 954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// that directly manipulate the analysis graph will need to change it. 964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void* State; 974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Preds - The predecessors of this node. 994c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Preds; 1004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Succs - The successors of this node. 1024c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Succs; 1034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the provided location and state. 10537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek explicit ExplodedNodeImpl(const ProgramPoint& loc, void* state) 1064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek : Location(loc), State(state) {} 1074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// addPredeccessor - Adds a predecessor to the current node, and 109f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// in tandem add this node as a successor of the other node. 1104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void addPredecessor(ExplodedNodeImpl* V) { 111b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek assert (!V->isSink()); 1124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek Preds.addNode(V); 1134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek V->Succs.addNode(this); 1144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 117d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // This method is only defined so that we can cast a 118d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // void* to FoldingSet<ExplodedNodeImpl> so that we can iterate 119d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // over the vertices of EdgeNodeSetMap in ExplodeGraphImpl. 120d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // The actual profiling of vertices will be done in the derived 121d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // class, ExplodedNode<>. Nodes will NEVER be INSERTED into the 122d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek // FoldingSet using this Profile method (since it doesn't do anything). 123d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek inline void Profile(llvm::FoldingSetNodeID& ID) const { 124d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek assert (false && "Needs to be implemented in derived class."); 125d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek } 126d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek 1274a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getLocation - Returns the edge associated with the given node. 1284a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint& getLocation() const { return Location; } 1294a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned succ_size() const { return Succs.size(); } 1314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned pred_size() const { return Preds.size(); } 1324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool succ_empty() const { return Succs.empty(); } 1334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool pred_empty() const { return Preds.size(); } 134f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 135b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek bool isSink() const { return Preds.getFlag(); } 136b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek void markAsSink() { Preds.setFlag(); } 1374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekstruct GRTrait { 1424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline void* toPtr(StateTy S) { 1434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return reinterpret_cast<void*>(S); 1444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1454a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline StateTy toState(void* P) { 1464a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return reinterpret_cast<StateTy>(P); 1474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNode : public ExplodedNodeImpl { 1534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 1544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the given node ID, program edge, 1554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// and state. 156ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek explicit ExplodedNode(const ProgramPoint& loc, StateTy state) 157ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek : ExplodedNodeImpl(loc, GRTrait<StateTy>::toPtr(state)) {} 1584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getState - Returns the state associated with the node. 1604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek inline StateTy getState() const { 1614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return GRTrait<StateTy>::toState(State); 1624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Profiling (for FoldingSet). 1657fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek 1667fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek static inline void Profile(llvm::FoldingSetNodeID& ID, 1677fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek const ProgramPoint& Loc, 1687fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek StateTy state) { 1697fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek ID.Add(Loc); 1707fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek GRTrait<StateTy>::Profile(ID, state); 1717fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek } 1727fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek 1734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek inline void Profile(llvm::FoldingSetNodeID& ID) const { 1747fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek Profile(ID, getLocation(), getState()); 1754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Iterators over successor and predecessor vertices. 1784a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** succ_iterator; 1794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const ExplodedNode** const_succ_iterator; 1804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** pred_iterator; 18137d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek typedef const ExplodedNode** const_pred_iterator; 1824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 18337d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); } 18437d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); } 1854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_begin() const { 1874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_begin(); 1884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_end() const { 1904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_end(); 1914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 19337d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); } 19437d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); } 1954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_begin() const { 1974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_begin(); 1984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_end() const { 2004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_end(); 2014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 2024a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 2034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2054241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraphImpl { 2064241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 2074d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek friend class GRCoreEngineImpl; 208f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenek friend class GRStmtNodeBuilderImpl; 2097d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek friend class GRBranchNodeBuilderImpl; 210754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek friend class GRIndirectGotoNodeBuilderImpl; 211daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek friend class GRSwitchNodeBuilderImpl; 2124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Type definitions. 2144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; 2154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; 216ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 2174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Roots - The roots of the simulation graph. Usually there will be only 2184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// one, but clients are free to establish multiple subgraphs within a single 2194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// SimulGraph. Moreover, these subgraphs can often merge when paths from 2204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// different roots reach the same state at the same program location. 2214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek RootsTy Roots; 2224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// EndNodes - The nodes in the simulation graph which have been 2244241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// specially marked as the endpoint of an abstract simulation path. 2254241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek EndNodesTy EndNodes; 2264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2274241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Allocator - BumpPtrAllocator to create nodes. 2284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::BumpPtrAllocator Allocator; 229cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 230cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek /// cfg - The CFG associated with this analysis graph. 231cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek CFG& cfg; 232cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 233cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek /// FD - The function declaration of the function being analyzed. 234cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek FunctionDecl& FD; 235cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 236cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek /// Ctx - The ASTContext used to "interpret" FD. 237cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ASTContext& Ctx; 23839b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek 23939b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek /// NumNodes - The number of nodes in the graph. 24039b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned NumNodes; 2414241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2424241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNodeImpl - Retrieve the node associated with a (Location,State) 2434241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// pair, where 'State' is represented as an opaque void*. This method 2444d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek /// is intended to be used only by GRCoreEngineImpl. 24537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, void* State, 246974c676306758c8c84f5c25e3708186557a678bdTed Kremenek bool* IsNew) = 0; 2474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2484241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addRoot - Add an untyped node to the set of roots. 249ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { 250ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek Roots.push_back(V); 251ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 252ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 2534241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2544241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addEndOfPath - Add an untyped node to the set of EOP nodes. 255ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { 256ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek EndNodes.push_back(V); 257ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 258ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 259cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 260cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek // ctor. 261cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ExplodedGraphImpl(CFG& c, FunctionDecl& f, ASTContext& ctx) 26239b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek : cfg(c), FD(f), Ctx(ctx), NumNodes(0) {} 2634241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2644241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 2655226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek virtual ~ExplodedGraphImpl() {} 2664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2674241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned num_roots() const { return Roots.size(); } 2684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned num_eops() const { return EndNodes.size(); } 269cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 27039b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek bool empty() const { return NumNodes == 0; } 27139b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned size() const { return NumNodes; } 27239b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek 273768ad16a4ab79fbc52f6f3bdc9362fd4e1d51d53Ted Kremenek llvm::BumpPtrAllocator& getAllocator() { return Allocator; } 274cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek CFG& getCFG() { return cfg; } 275cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ASTContext& getContext() { return Ctx; } 276cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek FunctionDecl& getFunctionDecl() { return FD; } 2774241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 2784241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 279ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenektemplate <typename CHECKER> 2804241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraph : public ExplodedGraphImpl { 2814241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 282ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef CHECKER CheckerTy; 283ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef typename CHECKER::StateTy StateTy; 2845226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek typedef ExplodedNode<StateTy> NodeTy; 2855226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek typedef llvm::FoldingSet<NodeTy> AllNodesTy; 286ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 287cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenekprotected: 288ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek llvm::OwningPtr<CheckerTy> CheckerState; 2894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2905226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek /// Nodes - The nodes in the graph. 2915226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek AllNodesTy Nodes; 2925226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek 2934241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 2944241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek virtual ExplodedNodeImpl* 29537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek getNodeImpl(const ProgramPoint& L, void* State, bool* IsNew) { 296ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek return getNode(L, GRTrait<StateTy>::toState(State), IsNew); 2974241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2994241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 300cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ExplodedGraph(CFG& c, FunctionDecl& fd, ASTContext& ctx) 301cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek : ExplodedGraphImpl(c, fd, ctx), CheckerState(new CheckerTy(*this)) {} 302b2d763a7987a2c5854d302f82f8b3c7ac5b92e20Ted Kremenek 303ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// getCheckerState - Returns the internal checker state associated 304ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// with the exploded graph. Ownership remains with the ExplodedGraph 305ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// objecct. 306ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek CheckerTy* getCheckerState() const { return CheckerState.get(); } 307ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 3084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNode - Retrieve the node associated with a (Location,State) pair, 30937d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek /// where the 'Location' is a ProgramPoint in the CFG. If no node for 3104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// this pair exists, it is created. IsNew is set to true if 3114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// the node was freshly created. 31237d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek NodeTy* getNode(const ProgramPoint& L, StateTy State, bool* IsNew = NULL) { 3134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Profile 'State' to determine if we already have an existing node. 3154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::FoldingSetNodeID profile; 3164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek void* InsertPos = 0; 3174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3187fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek NodeTy::Profile(profile, L, State); 3195226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos); 3204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (!V) { 3224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Allocate a new node. 3234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek V = (NodeTy*) Allocator.Allocate<NodeTy>(); 324ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek new (V) NodeTy(L, State); 3254241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Insert the node into the node set and return it. 3275226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek Nodes.InsertNode(V, InsertPos); 3284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 32939b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek ++NumNodes; 33039b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek 3314241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = true; 3324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3334241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek else 3344241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = false; 3354241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3364241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return V; 3374241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3384241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3394241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Iterators. 3401501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek typedef NodeTy** roots_iterator; 3411501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek typedef const NodeTy** const_roots_iterator; 3421501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek typedef NodeTy** eop_iterator; 3431501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek typedef const NodeTy** const_eop_iterator; 3444241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3464241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_begin() { 3471501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<roots_iterator>(Roots.begin()); 3484241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3494241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3504241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_end() { 3511501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<roots_iterator>(Roots.end()); 3524241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3534241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3544241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_begin() const { 3554241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_begin(); 3564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3574241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3584241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_end() const { 3594241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_end(); 3604241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3614241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3624241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_begin() { 3631501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<eop_iterator>(EndNodes.begin()); 3644241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3654241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3664241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_end() { 3671501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<eop_iterator>(EndNodes.end()); 3684241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3694241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3704241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_begin() const { 3714241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_begin(); 3724241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3734241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3744241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_end() const { 3754241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_end(); 3764241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3774241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 3784241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 379f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 380f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenektemplate <typename NodeTy> 381f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekclass ExplodedNodeSet { 382f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 383f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef llvm::SmallPtrSet<NodeTy*,5> ImplTy; 384f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ImplTy Impl; 385f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 386f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekpublic: 387f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ExplodedNodeSet(NodeTy* N) { 388f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek assert (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()); 389f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek Impl.insert(N); 390f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 391f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 392f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ExplodedNodeSet() {} 393f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 394f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline void Add(NodeTy* N) { 395f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek if (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()) Impl.insert(N); 396f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 397f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 398f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef typename ImplTy::iterator iterator; 399f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef typename ImplTy::const_iterator const_iterator; 400f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 401f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline unsigned size() const { return Impl.size(); } 402f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline bool empty() const { return Impl.empty(); } 403f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 404f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator begin() { return Impl.begin(); } 405f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator end() { return Impl.end(); } 406f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 407f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator begin() const { return Impl.begin(); } 408f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator end() const { return Impl.end(); } 409f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek}; 410f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 4114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek} // end clang namespace 4124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 4134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek// GraphTraits 4144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremeneknamespace llvm { 4164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 4174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<clang::ExplodedNode<StateTy>*> { 4184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef clang::ExplodedNode<StateTy> NodeType; 4194a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 4204a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4274a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4284a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4294a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4354a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4364a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 4444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<const clang::ExplodedNode<StateTy>*> { 4454a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const clang::ExplodedNode<StateTy> NodeType; 4464a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 4474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4564a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4574a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek} // end llvm namespace 4714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4724241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#endif 473