ExplodedGraph.h revision 4323a57627e796dcfdfdb7d47672dc09ed308eda
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" 1963bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek#include "clang/AST/Decl.h" 204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/SmallVector.h" 214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/FoldingSet.h" 22f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek#include "llvm/ADT/SmallPtrSet.h" 234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/Support/Allocator.h" 24ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek#include "llvm/ADT/OwningPtr.h" 254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/GraphTraits.h" 264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/DepthFirstIterator.h" 2763bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek#include "llvm/Support/Casting.h" 284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 294241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremeneknamespace clang { 304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 314d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenekclass GRCoreEngineImpl; 3237d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenekclass ExplodedNodeImpl; 3311062b118476368fa5b294954713e5df97d8599fTed Kremenekclass CFG; 3411062b118476368fa5b294954713e5df97d8599fTed Kremenekclass ASTContext; 3511062b118476368fa5b294954713e5df97d8599fTed Kremenek 36f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenekclass GRStmtNodeBuilderImpl; 377d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekclass GRBranchNodeBuilderImpl; 38754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekclass GRIndirectGotoNodeBuilderImpl; 39daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekclass GRSwitchNodeBuilderImpl; 4011062b118476368fa5b294954713e5df97d8599fTed Kremenekclass GREndPathNodebuilderImpl; 414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNodeImpl : public llvm::FoldingSetNode { 434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekprotected: 444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek friend class ExplodedGraphImpl; 454d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek friend class GRCoreEngineImpl; 46f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenek friend class GRStmtNodeBuilderImpl; 477d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek friend class GRBranchNodeBuilderImpl; 48754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek friend class GRIndirectGotoNodeBuilderImpl; 49daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek friend class GRSwitchNodeBuilderImpl; 5011062b118476368fa5b294954713e5df97d8599fTed Kremenek friend class GREndPathNodeBuilderImpl; 514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 524c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek class NodeGroup { 53b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 }; 544c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek uintptr_t P; 554c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 56ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek unsigned getKind() const { 57596f0a1e54f610926e8bfded9efa1c639f824dedTed Kremenek return P & 0x1; 58ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 59ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 60ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek void* getPtr() const { 61ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek assert (!getFlag()); 62b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return reinterpret_cast<void*>(P & ~Mask); 63ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 64ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 65ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek ExplodedNodeImpl* getNode() const { 66ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek return reinterpret_cast<ExplodedNodeImpl*>(getPtr()); 67ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek } 684c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 694c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek public: 704c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup() : P(0) {} 714c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 729eb49a40df510313132eef147419c5abefff23ebTed Kremenek ~NodeGroup(); 734c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 745d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek ExplodedNodeImpl** begin() const; 754c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 765d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek ExplodedNodeImpl** end() const; 774c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 785d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek unsigned size() const; 794c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 80ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek bool empty() const { return size() == 0; } 814c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 829eb49a40df510313132eef147419c5abefff23ebTed Kremenek void addNode(ExplodedNodeImpl* N); 83f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 84b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek void setFlag() { 85ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek assert (P == 0); 86ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek P = AuxFlag; 87f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 88f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 89b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek bool getFlag() const { 90b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return P & AuxFlag ? true : false; 91f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 92b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek }; 934c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Location - The program location (within a function body) associated 954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// with this node. 964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint Location; 974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 984323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek /// State - The state associated with this node. 994323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek const void* State; 1004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Preds - The predecessors of this node. 1024c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Preds; 1034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Succs - The successors of this node. 1054c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Succs; 1064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the provided location and state. 1084323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek explicit ExplodedNodeImpl(const ProgramPoint& loc, const void* state) 1094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek : Location(loc), State(state) {} 1104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// addPredeccessor - Adds a predecessor to the current node, and 112f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// in tandem add this node as a successor of the other node. 1134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void addPredecessor(ExplodedNodeImpl* V) { 114b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek assert (!V->isSink()); 1154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek Preds.addNode(V); 1164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek V->Succs.addNode(this); 1174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1194a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 120d880c1829395f55129fee31e2df542a475ec3cd7Ted Kremenek 1214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getLocation - Returns the edge associated with the given node. 1220f9063c116b7c3b05d8042b5976463c2dae04861Ted Kremenek ProgramPoint getLocation() const { return Location; } 1234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned succ_size() const { return Succs.size(); } 1254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned pred_size() const { return Preds.size(); } 1264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool succ_empty() const { return Succs.empty(); } 1270e8a3c743b9b3e3039e329a1736122d3b5b5fed9Ted Kremenek bool pred_empty() const { return Preds.empty(); } 128f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 129ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek bool isSink() const { return Succs.getFlag(); } 130ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek void markAsSink() { Succs.setFlag(); } 1314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1354a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekstruct GRTrait { 136e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek static inline void Profile(llvm::FoldingSetNodeID& ID, const StateTy* St) { 137e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek St->Profile(ID); 1384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNode : public ExplodedNodeImpl { 1444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 1454a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the given node ID, program edge, 1464a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// and state. 1474323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek explicit ExplodedNode(const ProgramPoint& loc, const StateTy* St) 148e5f4dcb6bd73a10df6eb6c3cfe057c88cb2362ccTed Kremenek : ExplodedNodeImpl(loc, St) {} 1494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getState - Returns the state associated with the node. 1514323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek inline const StateTy* getState() const { 1524323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek return static_cast<const StateTy*>(State); 1534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Profiling (for FoldingSet). 1567fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek 1577fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek static inline void Profile(llvm::FoldingSetNodeID& ID, 1587fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek const ProgramPoint& Loc, 1594323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek const StateTy* state) { 1607fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek ID.Add(Loc); 1617fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek GRTrait<StateTy>::Profile(ID, state); 1627fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek } 1637fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek 1644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek inline void Profile(llvm::FoldingSetNodeID& ID) const { 1657fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek Profile(ID, getLocation(), getState()); 1664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 168a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek void addPredecessor(ExplodedNode* V) { 169a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek ExplodedNodeImpl::addPredecessor(V); 170a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek } 171a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek 1724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Iterators over successor and predecessor vertices. 1734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** succ_iterator; 1744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const ExplodedNode** const_succ_iterator; 1754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** pred_iterator; 17637d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek typedef const ExplodedNode** const_pred_iterator; 1774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 17837d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); } 17937d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); } 1804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_begin() const { 1824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_begin(); 1834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1844a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_end() const { 1854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_end(); 1864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 18837d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); } 18937d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); } 1904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_begin() const { 1924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_begin(); 1934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_end() const { 1954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_end(); 1964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2004241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraphImpl { 2014241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 2024d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek friend class GRCoreEngineImpl; 203f4b7a6940070f04d7845ac55f0d1e300a8bee0d9Ted Kremenek friend class GRStmtNodeBuilderImpl; 2047d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek friend class GRBranchNodeBuilderImpl; 205754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek friend class GRIndirectGotoNodeBuilderImpl; 206daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek friend class GRSwitchNodeBuilderImpl; 20711062b118476368fa5b294954713e5df97d8599fTed Kremenek friend class GREndPathNodeBuilderImpl; 2084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Type definitions. 2104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; 2114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; 212ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 2134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Roots - The roots of the simulation graph. Usually there will be only 2144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// one, but clients are free to establish multiple subgraphs within a single 2154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// SimulGraph. Moreover, these subgraphs can often merge when paths from 2164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// different roots reach the same state at the same program location. 2174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek RootsTy Roots; 2184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// EndNodes - The nodes in the simulation graph which have been 2204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// specially marked as the endpoint of an abstract simulation path. 2214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek EndNodesTy EndNodes; 2224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Allocator - BumpPtrAllocator to create nodes. 2244241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::BumpPtrAllocator Allocator; 225cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 226cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek /// cfg - The CFG associated with this analysis graph. 227cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek CFG& cfg; 228cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 22963bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek /// CodeDecl - The declaration containing the code being analyzed. This 23063bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek /// can be a FunctionDecl or and ObjCMethodDecl. 23163bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek Decl& CodeDecl; 232cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek 23363bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek /// Ctx - The ASTContext used to "interpret" CodeDecl. 234cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek ASTContext& Ctx; 23539b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek 23639b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek /// NumNodes - The number of nodes in the graph. 23739b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned NumNodes; 2384241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2394241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNodeImpl - Retrieve the node associated with a (Location,State) 2404241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// pair, where 'State' is represented as an opaque void*. This method 2414d4dd85923ecfc9c38ac0e94fb2602e1cce4406bTed Kremenek /// is intended to be used only by GRCoreEngineImpl. 2424323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, 2434323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek const void* State, 244974c676306758c8c84f5c25e3708186557a678bdTed Kremenek bool* IsNew) = 0; 245ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 246ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek virtual ExplodedGraphImpl* MakeEmptyGraph() const = 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. 26163bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek ExplodedGraphImpl(CFG& c, Decl& cd, ASTContext& ctx) 26263bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek : cfg(c), CodeDecl(cd), 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; } 276a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek 277a43a1eb6e7c773b79898541794bf819601719493Ted Kremenek Decl& getCodeDecl() { return CodeDecl; } 27863bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek const Decl& getCodeDecl() const { return CodeDecl; } 27963bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek 28063bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek const FunctionDecl* getFunctionDecl() const { 28163bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek return llvm::dyn_cast<FunctionDecl>(&CodeDecl); 28263bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek } 283ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 284ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedGraphImpl* Trim(ExplodedNodeImpl** NBeg, 285ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedNodeImpl** NEnd) const; 286ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 2874241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 2884241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 28950a6d0ce344c02782e0207574005c3b2aaa5077cTed Kremenektemplate <typename STATE> 2904241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraph : public ExplodedGraphImpl { 2914241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 29250a6d0ce344c02782e0207574005c3b2aaa5077cTed Kremenek typedef STATE StateTy; 2935226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek typedef ExplodedNode<StateTy> NodeTy; 2945226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek typedef llvm::FoldingSet<NodeTy> AllNodesTy; 295ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 296cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenekprotected: 2975226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek /// Nodes - The nodes in the graph. 2985226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek AllNodesTy Nodes; 2995226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek 3004241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 301ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, 3024323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek const void* State, 3034323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek bool* IsNew) { 304ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 3054323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek return getNode(L, static_cast<const StateTy*>(State), IsNew); 3064241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 307ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 308ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek virtual ExplodedGraphImpl* MakeEmptyGraph() const { 30963bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek return new ExplodedGraph(cfg, CodeDecl, Ctx); 310ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek } 3114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 31363bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek ExplodedGraph(CFG& c, Decl& cd, ASTContext& ctx) 31450a6d0ce344c02782e0207574005c3b2aaa5077cTed Kremenek : ExplodedGraphImpl(c, cd, ctx) {} 315ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 3164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNode - Retrieve the node associated with a (Location,State) pair, 31737d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek /// where the 'Location' is a ProgramPoint in the CFG. If no node for 3184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// this pair exists, it is created. IsNew is set to true if 3194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// the node was freshly created. 3204323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek NodeTy* getNode(const ProgramPoint& L, const StateTy* State, 3214323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek bool* IsNew = NULL) { 3224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Profile 'State' to determine if we already have an existing node. 3244241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::FoldingSetNodeID profile; 3254241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek void* InsertPos = 0; 3264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3277fa6a4079fd68344e4d38c30f7681b3a7d30fbd1Ted Kremenek NodeTy::Profile(profile, L, State); 3285226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos); 3294241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3304241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (!V) { 3314241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Allocate a new node. 3324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek V = (NodeTy*) Allocator.Allocate<NodeTy>(); 333ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek new (V) NodeTy(L, State); 3344241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3354241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Insert the node into the node set and return it. 3365226755ab5ce6346f98b5f41cdcffbe84c5bb484Ted Kremenek Nodes.InsertNode(V, InsertPos); 3374241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 33839b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek ++NumNodes; 33939b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek 3404241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = true; 3414241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3424241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek else 3434241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = false; 3444241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return V; 3464241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3474241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3484241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Iterators. 3497ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek typedef NodeTy** roots_iterator; 3507ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek typedef const NodeTy** const_roots_iterator; 3517ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek typedef NodeTy** eop_iterator; 3527ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek typedef const NodeTy** const_eop_iterator; 3537ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek typedef typename AllNodesTy::iterator node_iterator; 3547ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek typedef typename AllNodesTy::const_iterator const_node_iterator; 3557ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek 3567ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek node_iterator nodes_begin() { 3577ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek return Nodes.begin(); 3587ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek } 3597ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek 3607ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek node_iterator nodes_end() { 3617ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek return Nodes.end(); 3627ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek } 3634241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3647ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek const_node_iterator nodes_begin() const { 3657ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek return Nodes.begin(); 3667ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek } 3677ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek 3687ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek const_node_iterator nodes_end() const { 3697ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek return Nodes.end(); 3707ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek } 3714241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3724241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_begin() { 3731501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<roots_iterator>(Roots.begin()); 3744241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3754241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3764241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_end() { 3771501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<roots_iterator>(Roots.end()); 3784241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3794241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3804241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_begin() const { 3814241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_begin(); 3824241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3834241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3844241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_end() const { 3854241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_end(); 3864241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3874241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3884241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_begin() { 3891501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<eop_iterator>(EndNodes.begin()); 3904241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3914241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3924241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_end() { 3931501c82ecb0a853f7e6bb9622e49bfc2f0413c0eTed Kremenek return reinterpret_cast<eop_iterator>(EndNodes.end()); 3944241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3954241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3964241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_begin() const { 3974241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_begin(); 3984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3994241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 4004241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_end() const { 4014241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_end(); 4024241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 403ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 404ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek // Utility. 405ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 406ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedGraph* Trim(NodeTy** NBeg, NodeTy** NEnd) const { 407ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 408ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek if (NBeg == NEnd) 409ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek return NULL; 410ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 411ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek assert (NBeg < NEnd); 412ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 413ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedNodeImpl** NBegImpl = (ExplodedNodeImpl**) NBeg; 414ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek ExplodedNodeImpl** NEndImpl = (ExplodedNodeImpl**) NEnd; 415ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek 416ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek return static_cast<ExplodedGraph*>(ExplodedGraphImpl::Trim(NBegImpl, 417ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek NEndImpl)); 418ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek } 4194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 4204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 421f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 422330dddd19406f9cc227e59e0bb0a36ecdc52915eTed Kremenektemplate <typename StateTy> 423f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekclass ExplodedNodeSet { 424f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 425330dddd19406f9cc227e59e0bb0a36ecdc52915eTed Kremenek typedef ExplodedNode<StateTy> NodeTy; 426f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef llvm::SmallPtrSet<NodeTy*,5> ImplTy; 427f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ImplTy Impl; 428f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 429f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekpublic: 430f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ExplodedNodeSet(NodeTy* N) { 431f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek assert (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()); 432f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek Impl.insert(N); 433f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 434f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 435f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ExplodedNodeSet() {} 436f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 437f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline void Add(NodeTy* N) { 438f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek if (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()) Impl.insert(N); 439f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 440f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 441f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef typename ImplTy::iterator iterator; 442f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek typedef typename ImplTy::const_iterator const_iterator; 443f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 444f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline unsigned size() const { return Impl.size(); } 445f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline bool empty() const { return Impl.empty(); } 4464bf38da038cebf9396470630c3c39519e41706daTed Kremenek 4474bf38da038cebf9396470630c3c39519e41706daTed Kremenek inline void clear() { Impl.clear(); } 448f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 449f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator begin() { return Impl.begin(); } 450f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator end() { return Impl.end(); } 451f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 452f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator begin() const { return Impl.begin(); } 453f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator end() const { return Impl.end(); } 454f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek}; 455f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 4564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek} // end clang namespace 4574241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 4584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek// GraphTraits 4594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremeneknamespace llvm { 4614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 4624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<clang::ExplodedNode<StateTy>*> { 4634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef clang::ExplodedNode<StateTy> NodeType; 4644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 4654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4784a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4844a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 4894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<const clang::ExplodedNode<StateTy>*> { 4904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const clang::ExplodedNode<StateTy> NodeType; 4914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 4924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 5004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 5014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 5024a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 5034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 5044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 5054a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 5064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 5074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 5084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 5094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 5104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 5114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 5124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 5134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 5144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 5154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek} // end llvm namespace 5164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 5174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#endif 518