ExplodedGraph.h revision 6bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89
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." 12b2213dc3dd8f58b611b91d2fce4834a767efcba7Jeffrey Yasskin// See "Precise interprocedural dataflow analysis via graph reachability" 13b2213dc3dd8f58b611b91d2fce4834a767efcba7Jeffrey Yasskin// by Reps, Horwitz, and Sagiv 14b2213dc3dd8f58b611b91d2fce4834a767efcba7Jeffrey Yasskin// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 15b2213dc3dd8f58b611b91d2fce4834a767efcba7Jeffrey Yasskin// exploded graph. 164241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek// 174241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek//===----------------------------------------------------------------------===// 184241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 195a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis#ifndef LLVM_CLANG_GR_EXPLODEDGRAPH 205a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis#define LLVM_CLANG_GR_EXPLODEDGRAPH 214241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 2263bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek#include "clang/AST/Decl.h" 2330a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "clang/Analysis/AnalysisContext.h" 2430a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "clang/Analysis/ProgramPoint.h" 2530a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "clang/Analysis/Support/BumpVector.h" 2630a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 2730a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/ADT/DepthFirstIterator.h" 284241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/ADT/FoldingSet.h" 2930a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/ADT/GraphTraits.h" 30f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek#include "llvm/ADT/SmallPtrSet.h" 3130a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/ADT/SmallVector.h" 324241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#include "llvm/Support/Allocator.h" 3363bbe5312cd89ce0ceb684bff68c5baef636e93cTed Kremenek#include "llvm/Support/Casting.h" 34651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines#include <memory> 35626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek#include <vector> 364241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 374241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremeneknamespace clang { 384a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3911062b118476368fa5b294954713e5df97d8599fTed Kremenekclass CFG; 405a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 419ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento { 425a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 435fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekclass ExplodedGraph; 4411062b118476368fa5b294954713e5df97d8599fTed Kremenek 45cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek//===----------------------------------------------------------------------===// 46cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek// ExplodedGraph "implementation" classes. These classes are not typed to 47cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek// contain a specific kind of state. Typed-specialized versions are defined 48cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek// on top of these classes. 49cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek//===----------------------------------------------------------------------===// 501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 51bda1efd0daf6fca9f515c6ce38d1ed71a3cca5b7Zhongxing Xu// ExplodedNode is not constified all over the engine because we need to add 52bda1efd0daf6fca9f515c6ce38d1ed71a3cca5b7Zhongxing Xu// successors to it at any time after creating it. 53bda1efd0daf6fca9f515c6ce38d1ed71a3cca5b7Zhongxing Xu 54c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xuclass ExplodedNode : public llvm::FoldingSetNode { 5538b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu friend class ExplodedGraph; 56d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CoreEngine; 57a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks friend class NodeBuilder; 58d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class BranchNodeBuilder; 59d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 60d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 61e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek friend class EndOfFunctionNodeBuilder; 621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 631833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// Efficiently stores a list of ExplodedNodes, or an optional flag. 641833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// 651833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing 661833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// for the case when there is only one node in the group. This is a fairly 671833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// common case in an ExplodedGraph, where most nodes have only one 681833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// predecessor and many have only one successor. It can also be used to 691833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// store a flag rather than a node list, which ExplodedNode uses to mark 701833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// whether a node is a sink. If the flag is set, the group is implicitly 711833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// empty and no nodes may be added. 724c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek class NodeGroup { 7346e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose // Conceptually a discriminated union. If the low bit is set, the node is 7446e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose // a sink. If the low bit is not set, the pointer refers to the storage 7546e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose // for the nodes in the group. 761833d284346b9fa11aae4e6aa07381347c04745cJordan Rose // This is not a PointerIntPair in order to keep the storage type opaque. 774c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek uintptr_t P; 78d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 794c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek public: 8046e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose NodeGroup(bool Flag = false) : P(Flag) { 8146e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose assert(getFlag() == Flag); 8246e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose } 831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8446e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose ExplodedNode * const *begin() const; 851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8646e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose ExplodedNode * const *end() const; 871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 885d5480380d7b7c3590a0283ddf239220e514e576Ted Kremenek unsigned size() const; 891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 9046e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose bool empty() const { return P == 0 || getFlag() != 0; } 911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 921833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// Adds a node to the list. 931833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// 941833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// The group must not have been created with its flag set. 959c378f705405d37f49795d5e915989de774fe11fTed Kremenek void addNode(ExplodedNode *N, ExplodedGraph &G); 961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 971833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// Replaces the single node in this group with a new node. 981833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// 991833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// Note that this should only be used when you know the group was not 1001833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// created with its flag set, and that the group is empty or contains 1011833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// only a single node. 102d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void replaceNode(ExplodedNode *node); 103d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 1041833d284346b9fa11aae4e6aa07381347c04745cJordan Rose /// Returns whether this group was created with its flag set. 105b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek bool getFlag() const { 10646e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose return (P & 1); 107f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 1081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump }; 1091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1104a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Location - The program location (within a function body) associated 1114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// with this node. 1124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const ProgramPoint Location; 1131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1144323a57627e796dcfdfdb7d47672dc09ed308edaTed Kremenek /// State - The state associated with this node. 1158bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef State; 1161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Preds - The predecessors of this node. 1184c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Preds; 1191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1204a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// Succs - The successors of this node. 1214c4cb527a44037d076da82ad9d12b4e655e64dbbTed Kremenek NodeGroup Succs; 122c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenekpublic: 124c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1255204d9e2fe0ea4e4b9c85087e355021c93221764Jordan Rose explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, 1266800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks bool IsSink) 12746e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose : Location(loc), State(state), Succs(IsSink) { 12846e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose assert(isSink() == IsSink); 129e40b69de464bc695afcaf7ef9602ad727d77b981Ted Kremenek } 130e40b69de464bc695afcaf7ef9602ad727d77b981Ted Kremenek 131a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ~ExplodedNode() {} 132c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1334a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek /// getLocation - Returns the edge associated with the given node. 1340f9063c116b7c3b05d8042b5976463c2dae04861Ted Kremenek ProgramPoint getLocation() const { return Location; } 135c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const LocationContext *getLocationContext() const { 1371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return getLocation().getLocationContext(); 13825e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu } 13925e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu 140955cd444f445bcdbade1cdd3926254c8ee7890d8Anna Zaks const StackFrameContext *getStackFrame() const { 141955cd444f445bcdbade1cdd3926254c8ee7890d8Anna Zaks return getLocationContext()->getCurrentStackFrame(); 142955cd444f445bcdbade1cdd3926254c8ee7890d8Anna Zaks } 143955cd444f445bcdbade1cdd3926254c8ee7890d8Anna Zaks 1445032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 1455032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu 1465032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu CFG &getCFG() const { return *getLocationContext()->getCFG(); } 1475032ffe4259e7d436f2eb19e5a29fdae559e7c12Zhongxing Xu 148b317f8f5ca8737a5bbad97a3f7566a2dbd2ed61bZhongxing Xu ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} 149b317f8f5ca8737a5bbad97a3f7566a2dbd2ed61bZhongxing Xu 150a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek template <typename T> 151a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek T &getAnalysis() const { 152a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenek return *getLocationContext()->getAnalysis<T>(); 153c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu } 154c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1550a6e09f67c719c318856be19d57e19972101f62cJordan Rose const ProgramStateRef &getState() const { return State; } 156b317f8f5ca8737a5bbad97a3f7566a2dbd2ed61bZhongxing Xu 15752c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek template <typename T> 1587a95de68c093991047ed8d339479ccad51b88663David Blaikie Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { 1597a95de68c093991047ed8d339479ccad51b88663David Blaikie return Location.getAs<T>(); 160dcd42fbb418cf662c136cb035e235a44b58ad91eJordan Rose } 161dcd42fbb418cf662c136cb035e235a44b58ad91eJordan Rose 1621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump static void Profile(llvm::FoldingSetNodeID &ID, 1636800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks const ProgramPoint &Loc, 1641831bd29572b6a7243da73d9606209190c0217deBenjamin Kramer const ProgramStateRef &state, 1656800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks bool IsSink) { 1665fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ID.Add(Loc); 167a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ID.AddPointer(state.getPtr()); 1686800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks ID.AddBoolean(IsSink); 1695fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 170c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 171c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu void Profile(llvm::FoldingSetNodeID& ID) const { 172fbe4d36f1f83ca12b532e0a946cbffcdb54f904cJordan Rose // We avoid copy constructors by not using accessors. 173fbe4d36f1f83ca12b532e0a946cbffcdb54f904cJordan Rose Profile(ID, Location, State, isSink()); 174c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu } 175c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump /// addPredeccessor - Adds a predecessor to the current node, and 177c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu /// in tandem add this node as a successor of the other node. 1789c378f705405d37f49795d5e915989de774fe11fTed Kremenek void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 179c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 1804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned succ_size() const { return Succs.size(); } 1814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned pred_size() const { return Preds.size(); } 1824a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek bool succ_empty() const { return Succs.empty(); } 1830e8a3c743b9b3e3039e329a1736122d3b5b5fed9Ted Kremenek bool pred_empty() const { return Preds.empty(); } 1841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 185ffe0f43806d4823271c2406c1fccc2373115c36aTed Kremenek bool isSink() const { return Succs.getFlag(); } 1864a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 187cacdbc97d11d2bbde00a63dace6ac26f4b12ed88Craig Topper bool hasSinglePred() const { 1885903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks return (pred_size() == 1); 1895903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks } 1905903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks 1919c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getFirstPred() { 1926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return pred_empty() ? nullptr : *(pred_begin()); 19352c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek } 1941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1959c378f705405d37f49795d5e915989de774fe11fTed Kremenek const ExplodedNode *getFirstPred() const { 19652c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek return const_cast<ExplodedNode*>(this)->getFirstPred(); 19752c3196a89a26cebcf069dd140c3396b743b8e33Ted Kremenek } 1981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1990f8579274a010f360a371b53101859d9d6052314Anna Zaks const ExplodedNode *getFirstSucc() const { 2006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return succ_empty() ? nullptr : *(succ_begin()); 2010f8579274a010f360a371b53101859d9d6052314Anna Zaks } 2020f8579274a010f360a371b53101859d9d6052314Anna Zaks 2034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek // Iterators over successor and predecessor vertices. 20446e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose typedef ExplodedNode* const * succ_iterator; 2053148eb4a75f70f2636075c364d03104223f004d3Ted Kremenek typedef const ExplodedNode* const * const_succ_iterator; 20646e778145c56cd9b42cb399795a294b29cb78b62Jordan Rose typedef ExplodedNode* const * pred_iterator; 2073148eb4a75f70f2636075c364d03104223f004d3Ted Kremenek typedef const ExplodedNode* const * const_pred_iterator; 2084a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 209c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu pred_iterator pred_begin() { return Preds.begin(); } 210c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu pred_iterator pred_end() { return Preds.end(); } 2114a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2124a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_begin() const { 2134a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_begin(); 2141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 2154a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_pred_iterator pred_end() const { 2164a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->pred_end(); 2174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 2184a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 219c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu succ_iterator succ_begin() { return Succs.begin(); } 220c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu succ_iterator succ_end() { return Succs.end(); } 2214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 2224a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_begin() const { 2234a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_begin(); 2244a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 2254a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek const_succ_iterator succ_end() const { 2264a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return const_cast<ExplodedNode*>(this)->succ_end(); 2274a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 228c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 229c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu // For debugging. 2301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 231c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xupublic: 2321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 233c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu class Auditor { 234c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu public: 235c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu virtual ~Auditor(); 2369c378f705405d37f49795d5e915989de774fe11fTed Kremenek virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; 237c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu }; 2381eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 239c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu static void SetAuditor(Auditor* A); 240d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 241d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenekprivate: 242d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } 243d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 244c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu}; 245c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 246c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rosetypedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *> 247c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose InterExplodedGraphMap; 2484a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 24938b02b912e1a55c912f603c4369431264d36a381Zhongxing Xuclass ExplodedGraph { 2504241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenekprotected: 251d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CoreEngine; 252e96de2dfde487211fb52f9139cdcae64d051a406Zhongxing Xu 2534241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Type definitions. 254626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek typedef std::vector<ExplodedNode *> NodeVector; 2551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 256626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek /// The roots of the simulation graph. Usually there will be only 2574241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// one, but clients are free to establish multiple subgraphs within a single 2584241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// SimulGraph. Moreover, these subgraphs can often merge when paths from 2594241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// different roots reach the same state at the same program location. 260626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek NodeVector Roots; 2614241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 262626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek /// The nodes in the simulation graph which have been 263626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek /// specially marked as the endpoint of an abstract simulation path. 264626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek NodeVector EndNodes; 26538b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 26638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu /// Nodes - The nodes in the graph. 26738b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::FoldingSet<ExplodedNode> Nodes; 26838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 2695fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// BVC - Allocator and context for allocating nodes and their predecessor 2705fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// and successor groups. 2715fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek BumpVectorContext BVC; 2721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 27339b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek /// NumNodes - The number of nodes in the graph. 27439b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned NumNodes; 275d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 276d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// A list of recently allocated nodes that can potentially be recycled. 2772ac58b7c09938bb28c51c7cd2deada609b75f94cTed Kremenek NodeVector ChangedNodes; 278d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 279d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// A list of nodes that can be reused. 280626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek NodeVector FreeNodes; 281d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 2824d9e497a2b1eab3b1214848216050c64fc3acfd6Jordan Rose /// Determines how often nodes are reclaimed. 2834d9e497a2b1eab3b1214848216050c64fc3acfd6Jordan Rose /// 2844d9e497a2b1eab3b1214848216050c64fc3acfd6Jordan Rose /// If this is 0, nodes will never be reclaimed. 2854d9e497a2b1eab3b1214848216050c64fc3acfd6Jordan Rose unsigned ReclaimNodeInterval; 2862ac58b7c09938bb28c51c7cd2deada609b75f94cTed Kremenek 2872ac58b7c09938bb28c51c7cd2deada609b75f94cTed Kremenek /// Counter to determine when to reclaim nodes. 2884d9e497a2b1eab3b1214848216050c64fc3acfd6Jordan Rose unsigned ReclaimCounter; 2894241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 29038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xupublic: 2916800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks 2926800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks /// \brief Retrieve the node associated with a (Location,State) pair, 29338b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu /// where the 'Location' is a ProgramPoint in the CFG. If no node for 2946800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks /// this pair exists, it is created. IsNew is set to true if 29538b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu /// the node was freshly created. 2968bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, 2976800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks bool IsSink = false, 2986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool* IsNew = nullptr); 2991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 30038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu ExplodedGraph* MakeEmptyGraph() const { 301c77a55126fcad66fb086f8e100a494caa2496a2dZhongxing Xu return new ExplodedGraph(); 30238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu } 3034a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 3044241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addRoot - Add an untyped node to the set of roots. 3059c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *addRoot(ExplodedNode *V) { 306ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek Roots.push_back(V); 307ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 308ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 3094241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 3104241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek /// addEndOfPath - Add an untyped node to the set of EOP nodes. 3119c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *addEndOfPath(ExplodedNode *V) { 312ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek EndNodes.push_back(V); 313ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek return V; 314ede5a4ba111f0590879670b6cb07f4d6d0bd9075Ted Kremenek } 31538b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 3169d0064e802e81d0833e8ccab8978b17c0bac3625Ted Kremenek ExplodedGraph(); 3174a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 318d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek ~ExplodedGraph(); 319d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 3204241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek unsigned num_roots() const { return Roots.size(); } 3214a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek unsigned num_eops() const { return EndNodes.size(); } 3221eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 32339b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek bool empty() const { return NumNodes == 0; } 32439b4c6c98d391b25c376782cf92346aa88c96f7eTed Kremenek unsigned size() const { return NumNodes; } 325c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu 3264241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek // Iterators. 32738b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef ExplodedNode NodeTy; 32838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef llvm::FoldingSet<ExplodedNode> AllNodesTy; 329626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek typedef NodeVector::iterator roots_iterator; 330626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek typedef NodeVector::const_iterator const_roots_iterator; 331626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek typedef NodeVector::iterator eop_iterator; 332626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek typedef NodeVector::const_iterator const_eop_iterator; 33338b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef AllNodesTy::iterator node_iterator; 33438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef AllNodesTy::const_iterator const_node_iterator; 3351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu node_iterator nodes_begin() { return Nodes.begin(); } 3377ebde953bb050caa69f791fc1de449d435c6a36fTed Kremenek 33838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu node_iterator nodes_end() { return Nodes.end(); } 3391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34038b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_node_iterator nodes_begin() const { return Nodes.begin(); } 3411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_node_iterator nodes_end() const { return Nodes.end(); } 3431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu roots_iterator roots_begin() { return Roots.begin(); } 3451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu roots_iterator roots_end() { return Roots.end(); } 3471eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_roots_iterator roots_begin() const { return Roots.begin(); } 3491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const_roots_iterator roots_end() const { return Roots.end(); } 3514241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 35238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu eop_iterator eop_begin() { return EndNodes.begin(); } 3531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 35438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu eop_iterator eop_end() { return EndNodes.end(); } 3551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 35638b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_eop_iterator eop_begin() const { return EndNodes.begin(); } 3571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 35838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const_eop_iterator eop_end() const { return EndNodes.end(); } 35938b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 3605fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } 3615fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek BumpVectorContext &getNodeAllocator() { return BVC; } 36238b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 36338b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap; 36438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu 365c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// Creates a trimmed version of the graph that only contains paths leading 366c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// to the given nodes. 367c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// 368c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// \param Nodes The nodes which must appear in the final graph. Presumably 369c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// these are end-of-path nodes (i.e. they have no successors). 370c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in 371c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// the returned graph. 372c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// \param[out] InverseMap An optional map from nodes in the returned graph to 373c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// nodes in this graph. 374c9963132736782d0c9178c744b3e2307cfb98a08Jordan Rose /// \returns The trimmed graph 3750f3a34fb7fea37ebfbcba8b400ccb697b9559b49Jordan Rose ExplodedGraph *trim(ArrayRef<const NodeTy *> Nodes, 3766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines InterExplodedGraphMap *ForwardMap = nullptr, 3776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines InterExplodedGraphMap *InverseMap = nullptr) const; 378d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 379d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// Enable tracking of recently allocated nodes for potential reclamation 3802ac58b7c09938bb28c51c7cd2deada609b75f94cTed Kremenek /// when calling reclaimRecentlyAllocatedNodes(). 3814d9e497a2b1eab3b1214848216050c64fc3acfd6Jordan Rose void enableNodeReclamation(unsigned Interval) { 3824d9e497a2b1eab3b1214848216050c64fc3acfd6Jordan Rose ReclaimCounter = ReclaimNodeInterval = Interval; 3834d9e497a2b1eab3b1214848216050c64fc3acfd6Jordan Rose } 384d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek 385d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// Reclaim "uninteresting" nodes created since the last time this method 386d767d81290288c030f3be0be1d3e62b9c8df51dcTed Kremenek /// was called. 3872ac58b7c09938bb28c51c7cd2deada609b75f94cTed Kremenek void reclaimRecentlyAllocatedNodes(); 388841c96a885789afea9d32d1d842033768c6d2b19Ted Kremenek 3894e9c0854382d37325771b50f6cf899a75119fa24Ted Kremenek /// \brief Returns true if nodes for the given expression kind are always 3904e9c0854382d37325771b50f6cf899a75119fa24Ted Kremenek /// kept around. 3914e9c0854382d37325771b50f6cf899a75119fa24Ted Kremenek static bool isInterestingLValueExpr(const Expr *Ex); 3924e9c0854382d37325771b50f6cf899a75119fa24Ted Kremenek 393841c96a885789afea9d32d1d842033768c6d2b19Ted Kremenekprivate: 394841c96a885789afea9d32d1d842033768c6d2b19Ted Kremenek bool shouldCollect(const ExplodedNode *node); 395841c96a885789afea9d32d1d842033768c6d2b19Ted Kremenek void collectNode(ExplodedNode *node); 3964241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek}; 397cf118d41f7930a18dce97416ef7834a62642f587Ted Kremenek 398f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekclass ExplodedNodeSet { 399c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy; 400f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ImplTy Impl; 4011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 402f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenekpublic: 4039c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNodeSet(ExplodedNode *N) { 404c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu assert (N && !static_cast<ExplodedNode*>(N)->isSink()); 405f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek Impl.insert(N); 406f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 4071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 408f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek ExplodedNodeSet() {} 4091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4109c378f705405d37f49795d5e915989de774fe11fTed Kremenek inline void Add(ExplodedNode *N) { 411c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); 412f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek } 4131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 414c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef ImplTy::iterator iterator; 415c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef ImplTy::const_iterator const_iterator; 416f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek 417fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek unsigned size() const { return Impl.size(); } 418fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek bool empty() const { return Impl.empty(); } 4191aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks bool erase(ExplodedNode *N) { return Impl.erase(N); } 420fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek 421fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek void clear() { Impl.clear(); } 422fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek void insert(const ExplodedNodeSet &S) { 4232d950b15b2b2b650b102ecf0c6b50b45e0cb6a8aAnna Zaks assert(&S != this); 424fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek if (empty()) 425fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek Impl = S.Impl; 426fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek else 427fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek Impl.insert(S.begin(), S.end()); 428fee96e043108b6e24e7d4c5464bf89ac970a7f81Ted Kremenek } 4291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 430f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator begin() { return Impl.begin(); } 431f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline iterator end() { return Impl.end(); } 4321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 433f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator begin() const { return Impl.begin(); } 434f6f5ef4aaa66b60270e84d1fe1292886369d2f38Ted Kremenek inline const_iterator end() const { return Impl.end(); } 4351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump}; 4361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4375a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 4385a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 4394241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek} // end clang namespace 4404241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek 4414a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek// GraphTraits 4424a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4434a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremeneknamespace llvm { 4449ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek template<> struct GraphTraits<clang::ento::ExplodedNode*> { 4459ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek typedef clang::ento::ExplodedNode NodeType; 446c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef NodeType::succ_iterator ChildIteratorType; 4474a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4494a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4504a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4514a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4534a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4544a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4554a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4574a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4584a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4594a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4614a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4624a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4634a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4654a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4664a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4674a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4684a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4709ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek template<> struct GraphTraits<const clang::ento::ExplodedNode*> { 4719ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenek typedef const clang::ento::ExplodedNode NodeType; 472c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef NodeType::const_succ_iterator ChildIteratorType; 4734a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek typedef llvm::df_iterator<NodeType*> nodes_iterator; 4741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4754a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline NodeType* getEntryNode(NodeType* N) { 4764a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N; 4774a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4794a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) { 4804a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_begin(); 4814a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4834a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) { 4844a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return N->succ_end(); 4854a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4874a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_begin(NodeType* N) { 4884a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_begin(N); 4894a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4914a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek static inline nodes_iterator nodes_end(NodeType* N) { 4924a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek return df_end(N); 4934a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek } 4944a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek }; 4951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4964a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek} // end llvm namespace 4974a0f5f1646637fcf90eb236b5a46f40e5a5dd739Ted Kremenek 4984241b3d1ad87e9a593bbc6cdf0f49435d5aec235Ted Kremenek#endif 499