ExplodedGraph.h revision ffe0f43806d4823271c2406c1fccc2373115c36a
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 { 54596f0a1e54f610926e8bfded9efa1c639f824dedTed Kremenek return P & 0x1; 55ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 56ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 57ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek void* getPtr() const { 58ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek assert (!getFlag()); 59b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return reinterpret_cast<void*>(P & ~Mask); 60ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 61ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 62ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek ExplodedNodeImpl* getNode() const { 63ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek return reinterpret_cast<ExplodedNodeImpl*>(getPtr()); 64ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 654c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 664c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek public: 674c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup() : P(0) {} 684c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 699eb49a40df510313132eef147419c5abefff23ebTed Kremenek ~NodeGroup(); 704c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 715d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek ExplodedNodeImpl** begin() const; 724c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 735d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek ExplodedNodeImpl** end() const; 744c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 755d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek unsigned size() const; 764c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 77ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek bool empty() const { return size() == 0; } 784c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 799eb49a40df510313132eef147419c5abefff23ebTed Kremenek void addNode(ExplodedNodeImpl* N); 80f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 81b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek void setFlag() { 82ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek assert (P == 0); 83ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek P = AuxFlag; 84f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 85f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 86b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek bool getFlag() const { 87b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return P & AuxFlag ? true : false; 88f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 89b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek }; 904c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Location - The program location (within a function body) associated 924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// with this node. 934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint Location; 944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// State - The state associated with this node. Normally this value 964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// is immutable, but we anticipate there will be times when algorithms 974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// that directly manipulate the analysis graph will need to change it. 984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void* State; 994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Preds - The predecessors of this node. 1014c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Preds; 1024a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Succs - The successors of this node. 1044c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Succs; 1054a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the provided location and state. 10737d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek explicit ExplodedNodeImpl(const ProgramPoint& loc, void* state) 1084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek : Location(loc), State(state) {} 1094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// addPredeccessor - Adds a predecessor to the current node, and 111f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// in tandem add this node as a successor of the other node. 1124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void addPredecessor(ExplodedNodeImpl* V) { 113b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek assert (!V->isSink()); 1144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek Preds.addNode(V); 1154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek V->Succs.addNode(this); 1164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 119d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek 1204a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getLocation - Returns the edge associated with the given node. 1214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint& getLocation() const { return Location; } 1224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned succ_size() const { return Succs.size(); } 1244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned pred_size() const { return Preds.size(); } 1254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool succ_empty() const { return Succs.empty(); } 1264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool pred_empty() const { return Preds.size(); } 127f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 128ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek bool isSink() const { return Succs.getFlag(); } 129ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek void markAsSink() { Succs.setFlag(); } 1304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekstruct GRTrait { 135e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek static inline void Profile(llvm::FoldingSetNodeID& ID, const StateTy* St) { 136e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek St->Profile(ID); 1374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNode : public ExplodedNodeImpl { 1434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 1444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the given node ID, program edge, 1454a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// and state. 146e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek explicit ExplodedNode(const ProgramPoint& loc, StateTy* St) 147e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek : ExplodedNodeImpl(loc, St) {} 1484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getState - Returns the state associated with the node. 150e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek inline StateTy* getState() const { 151e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek return static_cast<StateTy*>(State); 1524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Profiling (for FoldingSet). 1557fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek 1567fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek static inline void Profile(llvm::FoldingSetNodeID& ID, 1577fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek const ProgramPoint& Loc, 158e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek StateTy* state) { 1597fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek ID.Add(Loc); 1607fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek GRTrait<StateTy>::Profile(ID, state); 1617fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek } 1627fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek 1634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek inline void Profile(llvm::FoldingSetNodeID& ID) const { 1647fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek Profile(ID, getLocation(), getState()); 1654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Iterators over successor and predecessor vertices. 1684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** succ_iterator; 1694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const ExplodedNode** const_succ_iterator; 1704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** pred_iterator; 17137d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek typedef const ExplodedNode** const_pred_iterator; 1724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 17337d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); } 17437d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); } 1754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_begin() const { 1774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_begin(); 1784a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_end() const { 1804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_end(); 1814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 18337d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); } 18437d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); } 1854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_begin() const { 1874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_begin(); 1884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_end() const { 1904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_end(); 1914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1954241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraphImpl { 1964241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 1974d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek friend class GRCoreEngineImpl; 198f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenek friend class GRStmtNodeBuilderImpl; 1997d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek friend class GRBranchNodeBuilderImpl; 200754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek friend class GRIndirectGotoNodeBuilderImpl; 201daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek friend class GRSwitchNodeBuilderImpl; 2024241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2034241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Type definitions. 2044241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; 2054241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; 206ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 2074241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Roots - The roots of the simulation graph. Usually there will be only 2084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// one, but clients are free to establish multiple subgraphs within a single 2094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// SimulGraph. Moreover, these subgraphs can often merge when paths from 2104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// different roots reach the same state at the same program location. 2114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek RootsTy Roots; 2124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// EndNodes - The nodes in the simulation graph which have been 2144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// specially marked as the endpoint of an abstract simulation path. 2154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek EndNodesTy EndNodes; 2164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Allocator - BumpPtrAllocator to create nodes. 2184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::BumpPtrAllocator Allocator; 219cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 220cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek /// cfg - The CFG associated with this analysis graph. 221cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek CFG& cfg; 222cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 223cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek /// FD - The function declaration of the function being analyzed. 224cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek FunctionDecl& FD; 225cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 226cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek /// Ctx - The ASTContext used to "interpret" FD. 227cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ASTContext& Ctx; 22839b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek 22939b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek /// NumNodes - The number of nodes in the graph. 23039b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned NumNodes; 2314241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNodeImpl - Retrieve the node associated with a (Location,State) 2334241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// pair, where 'State' is represented as an opaque void*. This method 2344d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek /// is intended to be used only by GRCoreEngineImpl. 23537d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, void* State, 236974c676306758c8c84f5c25e3708186557a678bdTed Kremenek bool* IsNew) = 0; 237ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 238ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek virtual ExplodedGraphImpl* MakeEmptyGraph() const = 0; 2394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2404241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addRoot - Add an untyped node to the set of roots. 241ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { 242ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek Roots.push_back(V); 243ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 244ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 2454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2464241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addEndOfPath - Add an untyped node to the set of EOP nodes. 247ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { 248ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek EndNodes.push_back(V); 249ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 250ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 251cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 252cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek // ctor. 253cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ExplodedGraphImpl(CFG& c, FunctionDecl& f, ASTContext& ctx) 25439b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek : cfg(c), FD(f), Ctx(ctx), NumNodes(0) {} 2554241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 2575226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek virtual ~ExplodedGraphImpl() {} 2584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2594241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned num_roots() const { return Roots.size(); } 2604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned num_eops() const { return EndNodes.size(); } 261cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 26239b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek bool empty() const { return NumNodes == 0; } 26339b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned size() const { return NumNodes; } 26439b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek 265768ad16a4ab79fbc52f6f3bdc9362fd4e1d51d53Ted Kremenek llvm::BumpPtrAllocator& getAllocator() { return Allocator; } 266cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek CFG& getCFG() { return cfg; } 267cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ASTContext& getContext() { return Ctx; } 268cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek FunctionDecl& getFunctionDecl() { return FD; } 269ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 270ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedGraphImpl* Trim(ExplodedNodeImpl** NBeg, 271ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedNodeImpl** NEnd) const; 272ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 2734241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 2744241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 275ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenektemplate <typename CHECKER> 2764241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraph : public ExplodedGraphImpl { 2774241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 278ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef CHECKER CheckerTy; 279ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef typename CHECKER::StateTy StateTy; 2805226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek typedef ExplodedNode<StateTy> NodeTy; 2815226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek typedef llvm::FoldingSet<NodeTy> AllNodesTy; 282ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 283cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenekprotected: 284ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek llvm::OwningPtr<CheckerTy> CheckerState; 2854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2865226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek /// Nodes - The nodes in the graph. 2875226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek AllNodesTy Nodes; 2885226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek 2894241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 290ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, 291ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek void* State, bool* IsNew) { 292ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 293e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek return getNode(L, static_cast<StateTy*>(State), IsNew); 2944241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 295ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 296ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek virtual ExplodedGraphImpl* MakeEmptyGraph() const { 297ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek return new ExplodedGraph(cfg, FD, Ctx); 298ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek } 2994241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3004241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 301cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ExplodedGraph(CFG& c, FunctionDecl& fd, ASTContext& ctx) 302cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek : ExplodedGraphImpl(c, fd, ctx), CheckerState(new CheckerTy(*this)) {} 303b2d763a7987a2c5854d302f82f8b3c7ac5b92e20Ted Kremenek 304ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// getCheckerState - Returns the internal checker state associated 305ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// with the exploded graph. Ownership remains with the ExplodedGraph 306ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// objecct. 307ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek CheckerTy* getCheckerState() const { return CheckerState.get(); } 308ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 3094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNode - Retrieve the node associated with a (Location,State) pair, 31037d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek /// where the 'Location' is a ProgramPoint in the CFG. If no node for 3114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// this pair exists, it is created. IsNew is set to true if 3124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// the node was freshly created. 313e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek NodeTy* getNode(const ProgramPoint& L, StateTy* State, bool* IsNew = NULL) { 3144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Profile 'State' to determine if we already have an existing node. 3164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::FoldingSetNodeID profile; 3174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek void* InsertPos = 0; 3184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3197fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek NodeTy::Profile(profile, L, State); 3205226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos); 3214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (!V) { 3234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Allocate a new node. 3244241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek V = (NodeTy*) Allocator.Allocate<NodeTy>(); 325ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek new (V) NodeTy(L, State); 3264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3274241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Insert the node into the node set and return it. 3285226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek Nodes.InsertNode(V, InsertPos); 3294241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 33039b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek ++NumNodes; 33139b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek 3324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = true; 3334241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3344241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek else 3354241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = false; 3364241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3374241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return V; 3384241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3394241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3404241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Iterators. 3411501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek typedef NodeTy** roots_iterator; 3421501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek typedef const NodeTy** const_roots_iterator; 3431501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek typedef NodeTy** eop_iterator; 3441501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek typedef const NodeTy** const_eop_iterator; 3454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3464241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3474241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_begin() { 3481501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<roots_iterator>(Roots.begin()); 3494241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3504241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3514241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_end() { 3521501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<roots_iterator>(Roots.end()); 3534241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3544241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3554241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_begin() const { 3564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_begin(); 3574241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3584241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3594241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_end() const { 3604241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_end(); 3614241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3624241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3634241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_begin() { 3641501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<eop_iterator>(EndNodes.begin()); 3654241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3664241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3674241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_end() { 3681501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<eop_iterator>(EndNodes.end()); 3694241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3704241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3714241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_begin() const { 3724241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_begin(); 3734241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3744241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3754241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_end() const { 3764241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_end(); 3774241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 378ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 379ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek // Utility. 380ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 381ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedGraph* Trim(NodeTy** NBeg, NodeTy** NEnd) const { 382ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 383ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek if (NBeg == NEnd) 384ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek return NULL; 385ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 386ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek assert (NBeg < NEnd); 387ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 388ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedNodeImpl** NBegImpl = (ExplodedNodeImpl**) NBeg; 389ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedNodeImpl** NEndImpl = (ExplodedNodeImpl**) NEnd; 390ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 391ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek return static_cast<ExplodedGraph*>(ExplodedGraphImpl::Trim(NBegImpl, 392ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek NEndImpl)); 393ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek } 3944241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 3954241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 396f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 397330dddd19406f9cc227e59e0bb0a36ecdc52915eTed Kremenektemplate <typename StateTy> 398f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekclass ExplodedNodeSet { 399f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 400330dddd19406f9cc227e59e0bb0a36ecdc52915eTed Kremenek typedef ExplodedNode<StateTy> NodeTy; 401f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef llvm::SmallPtrSet<NodeTy*,5> ImplTy; 402f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ImplTy Impl; 403f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 404f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekpublic: 405f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ExplodedNodeSet(NodeTy* N) { 406f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek assert (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()); 407f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek Impl.insert(N); 408f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 409f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 410f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ExplodedNodeSet() {} 411f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 412f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline void Add(NodeTy* N) { 413f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek if (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()) Impl.insert(N); 414f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 415f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 416f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef typename ImplTy::iterator iterator; 417f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef typename ImplTy::const_iterator const_iterator; 418f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 419f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline unsigned size() const { return Impl.size(); } 420f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline bool empty() const { return Impl.empty(); } 4214bf38da038cebf9396470630c3c39519e41706daTed Kremenek 4224bf38da038cebf9396470630c3c39519e41706daTed Kremenek inline void clear() { Impl.clear(); } 423f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 424f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator begin() { return Impl.begin(); } 425f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator end() { return Impl.end(); } 426f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 427f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator begin() const { return Impl.begin(); } 428f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator end() const { return Impl.end(); } 429f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek}; 430f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 4314241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek} // end clang namespace 4324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 4334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek// GraphTraits 4344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4354a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremeneknamespace llvm { 4364a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 4374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<clang::ExplodedNode<StateTy>*> { 4384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef clang::ExplodedNode<StateTy> NodeType; 4394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 4404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4454a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4464a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4564a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4574a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 4644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<const clang::ExplodedNode<StateTy>*> { 4654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const clang::ExplodedNode<StateTy> NodeType; 4664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 4674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4784a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4844a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek} // end llvm namespace 4914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4924241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#endif 493