ExplodedGraph.h revision 4c4cb527a44037d076da82ad9d12b4e655e64dbb
151125a21eafc29c925cac3655b46cfd8ef55f764Ted Kremenek//=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- C++ -*-------==// 24241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// 34241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// The LLVM Compiler Infrastructure 44241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// 54241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// This file is distributed under the University of Illinois Open Source 64241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// License. See LICENSE.TXT for details. 74241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// 84241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//===----------------------------------------------------------------------===// 94241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// 1051125a21eafc29c925cac3655b46cfd8ef55f764Ted Kremenek// This file defines the template classes ExplodedNode and ExplodedGraph, 1151125a21eafc29c925cac3655b46cfd8ef55f764Ted Kremenek// which represent a path-sensitive, intra-procedural "exploded graph." 124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// 134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//===----------------------------------------------------------------------===// 144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#ifndef LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH 164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#define LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH 174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "clang/Analysis/ProgramPoint.h" 194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/SmallVector.h" 204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/FoldingSet.h" 214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/DenseMap.h" 224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/Support/Allocator.h" 23ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek#include "llvm/ADT/OwningPtr.h" 244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/GraphTraits.h" 254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include "llvm/ADT/DepthFirstIterator.h" 264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek#include <vector> 274241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremeneknamespace clang { 294a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 30974c676306758c8c84f5c25e3708186557a678bdTed Kremenekclass GREngineImpl; 3137d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenekclass ExplodedNodeImpl; 324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNodeImpl : public llvm::FoldingSetNode { 344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekprotected: 354a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek friend class ExplodedGraphImpl; 364a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 374c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek class NodeGroup { 384c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek enum { Size1 = 0x0, SizeOther = 0x1, Flags = 0x1 }; 394c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek uintptr_t P; 404c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 414c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek unsigned getKind() const { return P & Flags; } 424c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 434c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek std::vector<ExplodedNodeImpl*>& getVector() { 444c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek assert (getKind() == SizeOther); 454c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return *reinterpret_cast<std::vector<ExplodedNodeImpl*>*>(P & ~Flags); 464c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 474c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek const std::vector<ExplodedNodeImpl*>& getVector() const { 484c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek assert (getKind() == SizeOther); 494c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return *reinterpret_cast<std::vector<ExplodedNodeImpl*>*>(P & ~Flags); 504c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 514c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 524c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek ExplodedNodeImpl* getNode() const { 534c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek assert (getKind() == Size1); 544c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return reinterpret_cast<ExplodedNodeImpl*>(P); 554c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 564c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 574c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek public: 584c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup() : P(0) {} 594c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 604c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek ~NodeGroup() { if (getKind() == SizeOther) delete &getVector(); } 614c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 624c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek inline ExplodedNodeImpl** begin() const { 634c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek if (getKind() == Size1) 644c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return (ExplodedNodeImpl**) &P; 654c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek else 664c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return const_cast<ExplodedNodeImpl**>(&*(getVector().begin())); 674c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 684c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 694c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek inline ExplodedNodeImpl** end() const { 704c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek if (getKind() == Size1) 714c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return ((ExplodedNodeImpl**) &P)+1; 724c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek else 734c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return const_cast<ExplodedNodeImpl**>(&*(getVector().rbegin())+1); 744c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 754c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 764c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek inline unsigned size() const { 774c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek if (getKind() == Size1) 784c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return getNode() ? 1 : 0; 794c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek else 804c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return getVector().size(); 814c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 824c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 834c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek inline bool empty() const { 844c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek if (getKind() == Size1) 854c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return getNode() ? false : true; 864c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek else 874c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek return getVector().empty(); 884c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 894c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 904c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek inline void addNode(ExplodedNodeImpl* N) { 914c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek if (getKind() == Size1) { 924c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek if (ExplodedNodeImpl* NOld = getNode()) { 934c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek std::vector<ExplodedNodeImpl*>* V = new std::vector<ExplodedNodeImpl*>(); 944c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek V->push_back(NOld); 954c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek V->push_back(N); 964c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek P = reinterpret_cast<uintptr_t>(V) & SizeOther; 974c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 984c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek else 994c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek P = reinterpret_cast<uintptr_t>(N); 1004c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 1014c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek else 1024c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek getVector().push_back(N); 1034c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek } 1044c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek }; 1054c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 1064c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek 1074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Location - The program location (within a function body) associated 1084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// with this node. 1094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint Location; 1104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// State - The state associated with this node. Normally this value 1124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// is immutable, but we anticipate there will be times when algorithms 1134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// that directly manipulate the analysis graph will need to change it. 1144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void* State; 1154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Preds - The predecessors of this node. 1174c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Preds; 1184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1194a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Succs - The successors of this node. 1204c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Succs; 1214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the provided location and state. 12337d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek explicit ExplodedNodeImpl(const ProgramPoint& loc, void* state) 1244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek : Location(loc), State(state) {} 1254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// addPredeccessor - Adds a predecessor to the current node, and 1274a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// in tandem add this node as a successor of the other node. This 1284a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// method is intended to be used only by ExplodedGraphImpl. 1294a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek void addPredecessor(ExplodedNodeImpl* V) { 1304a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek Preds.addNode(V); 1314a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek V->Succs.addNode(this); 1324a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1344a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 1354a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getLocation - Returns the edge associated with the given node. 1364a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint& getLocation() const { return Location; } 1374a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned succ_size() const { return Succs.size(); } 1394a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned pred_size() const { return Preds.size(); } 1404a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool succ_empty() const { return Succs.empty(); } 1414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool pred_empty() const { return Preds.size(); } 1424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1444a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1454a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1464a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekstruct GRTrait { 1474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline void* toPtr(StateTy S) { 1484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return reinterpret_cast<void*>(S); 1494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline StateTy toState(void* P) { 1514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return reinterpret_cast<StateTy>(P); 1524a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 1544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1564a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenektemplate <typename StateTy> 1574a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekclass ExplodedNode : public ExplodedNodeImpl { 1584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 1594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Construct a ExplodedNodeImpl with the given node ID, program edge, 1604a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// and state. 16137d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek explicit ExplodedNode(unsigned ID, const ProgramPoint& loc, StateTy state) 1624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek : ExplodedNodeImpl(ID, loc, GRTrait<StateTy>::toPtr(state)) {} 1634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1644a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getState - Returns the state associated with the node. 1654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek inline StateTy getState() const { 1664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return GRTrait<StateTy>::toState(State); 1674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Profiling (for FoldingSet). 1704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek inline void Profile(llvm::FoldingSetNodeID& ID) const { 1714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek StateTy::Profile(ID, getState()); 1724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Iterators over successor and predecessor vertices. 1754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** succ_iterator; 1764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const ExplodedNode** const_succ_iterator; 1774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef ExplodedNode** pred_iterator; 17837d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek typedef const ExplodedNode** const_pred_iterator; 1794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 18037d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); } 18137d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); } 1824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_begin() const { 1844a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_begin(); 1854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_end() const { 1874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_end(); 1884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 19037d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); } 19137d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); } 1924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 1934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_begin() const { 1944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_begin(); 1954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_end() const { 1974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_end(); 1984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 1994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek}; 2004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2024241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraphImpl { 2034241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 204974c676306758c8c84f5c25e3708186557a678bdTed Kremenek friend class GREngineImpl; 2054241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2064241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Type definitions. 20737d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek typedef llvm::DenseMap<ProgramPoint,void*> EdgeNodeSetMap; 2084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; 2094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; 2104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// NodeCounter - The number of nodes that have been created, although 2124241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// this need not be the current number of nodes in the graph that 2134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// are reachable from the roots. This counter is used to assign a unique 2144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// number to each node (which is useful for debugging). 2154241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned NodeCounter; 2164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted 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 /// Nodes - A mapping from edges to nodes. 2284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek EdgeNodeSetMap Nodes; 2294241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2304241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// Allocator - BumpPtrAllocator to create nodes. 2314241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::BumpPtrAllocator Allocator; 2324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2334241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNodeImpl - Retrieve the node associated with a (Location,State) 2344241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// pair, where 'State' is represented as an opaque void*. This method 235974c676306758c8c84f5c25e3708186557a678bdTed Kremenek /// is intended to be used only by GREngineImpl. 23637d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, void* State, 237974c676306758c8c84f5c25e3708186557a678bdTed Kremenek bool* IsNew) = 0; 2384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2394241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addRoot - Add an untyped node to the set of roots. 240ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { 241ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek Roots.push_back(V); 242ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 243ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 2444241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addEndOfPath - Add an untyped node to the set of EOP nodes. 246ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { 247ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek EndNodes.push_back(V); 248ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 249ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 2504241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2514241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 2524241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek virtual ~ExplodedGraphImpl() {}; 2534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2544241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned num_roots() const { return Roots.size(); } 2554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned num_eops() const { return EndNodes.size(); } 2564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned getCounter() const { return NodeCounter; } 2574241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 2584241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 259ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenektemplate <typename CHECKER> 2604241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekclass ExplodedGraph : public ExplodedGraphImpl { 2614241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 262ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef CHECKER CheckerTy; 263ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef typename CHECKER::StateTy StateTy; 264ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek typedef ExplodedNode<StateTy> NodeTy; 265ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 266ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenekprotected: 267ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek llvm::OwningPtr<CheckerTy> CheckerState; 2684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2694241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 2704241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek virtual ExplodedNodeImpl* 27137d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek getNodeImpl(const ProgramPoint& L, void* State, bool* IsNew) { 272974c676306758c8c84f5c25e3708186557a678bdTed Kremenek return getNode(L,GRTrait<StateTy>::toState(State),IsNew); 2734241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2744241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2754241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekpublic: 2764241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek virtual ~ExplodedGraph() { 2774241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Delete the FoldingSet's in Nodes. Note that the contents 2784241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // of the FoldingSets are nodes allocated from the BumpPtrAllocator, 2794241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // so all of those will get nuked when that object is destroyed. 2804241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek for (EdgeNodeSetMap::iterator I=Nodes.begin(), E=Nodes.end(); I!=E; ++I) 2814241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek delete reinterpret_cast<llvm::FoldingSet<NodeTy>*>(I->second); 2824241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 2834241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 284ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// getCheckerState - Returns the internal checker state associated 285ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// with the exploded graph. Ownership remains with the ExplodedGraph 286ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek /// objecct. 287ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek CheckerTy* getCheckerState() const { return CheckerState.get(); } 288ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek 2894241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// getNode - Retrieve the node associated with a (Location,State) pair, 29037d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek /// where the 'Location' is a ProgramPoint in the CFG. If no node for 2914241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// this pair exists, it is created. IsNew is set to true if 2924241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// the node was freshly created. 29337d887c6c8e3c653fc581183d012a646d1653f57Ted Kremenek NodeTy* getNode(const ProgramPoint& L, StateTy State, bool* IsNew = NULL) { 2944241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2954241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Retrieve the node set associated with Loc. 2964241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::FoldingSet<NodeTy>*& VSet = 2974241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek reinterpret_cast<llvm::FoldingSet<NodeTy>*&>(Nodes[L]); 2984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2994241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Create the FoldingSet for the nodes if it does not exist yet. 3004241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (!VSet) VSet = new llvm::FoldingSet<NodeTy>(); 3014241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3024241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Profile 'State' to determine if we already have an existing node. 3034241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek llvm::FoldingSetNodeID profile; 3044241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek void* InsertPos = 0; 3054241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3064241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek StateTy::Profile(profile, State); 307974c676306758c8c84f5c25e3708186557a678bdTed Kremenek NodeTy* V = VSet.FindNodeOrInsertPos(profile, InsertPos); 3084241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (!V) { 3104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Allocate a new node. 3114241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek V = (NodeTy*) Allocator.Allocate<NodeTy>(); 312974c676306758c8c84f5c25e3708186557a678bdTed Kremenek new (V) NodeTy(NodeCounter++, L, State); 3134241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3144241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Insert the node into the node set and return it. 315974c676306758c8c84f5c25e3708186557a678bdTed Kremenek VSet.InsertNode(V, InsertPos); 3164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = true; 3184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3194241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek else 3204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek if (IsNew) *IsNew = false; 3214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3224241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return V; 3234241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3244241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3254241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Iterators. 3264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef NodeTy* roots_iterator; 3274241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef const NodeTy* const_roots_iterator; 3284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef NodeTy* eop_iterator; 3294241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek typedef const NodeTy* const_eop_iterator; 3304241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3314241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_begin() { 3334241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return static_cast<NodeTy*>(Roots.begin()); 3344241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3354241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3364241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek roots_iterator roots_end() { 3374241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return static_cast<NodeTy*>(Roots.end()); 3384241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3394241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3404241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_begin() const { 3414241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_begin(); 3424241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3434241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3444241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_roots_iterator roots_end() const { 3454241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->roots_end(); 3464241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3474241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3484241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_begin() { 3494241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return static_cast<NodeTy*>(EndNodes.begin()); 3504241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3514241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3524241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek eop_iterator eop_end() { 3534241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return static_cast<NodeTy*>(EndNodes.end()); 3544241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3554241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3564241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_begin() const { 3574241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_begin(); 3584241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3594241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3604241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek const_eop_iterator eop_end() const { 3614241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek return const_cast<ExplodedGraph>(this)->eop_end(); 3624241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek } 3634241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 3644241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3654241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek} // end clang namespace 3664241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek// GraphTraits 3684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3694a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremeneknamespace llvm { 3704a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 3714a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<clang::ExplodedNode<StateTy>*> { 3724a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef clang::ExplodedNode<StateTy> NodeType; 3734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 3744a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 3754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 3774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 3784a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 3814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 3824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3844a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 3854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 3864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 3894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 3904a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 3934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 3944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 3954a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 3964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek template<typename StateTy> 3984a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek struct GraphTraits<const clang::ExplodedNode<StateTy>*> { 3994a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef const clang::ExplodedNode<StateTy> NodeType; 4004a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef typename NodeType::succ_iterator ChildIteratorType; 4014a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4024a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4044a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4054a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4064a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4074a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4094a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4144a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4194a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4204a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek} // end llvm namespace 4254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#endif 427