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);
167ef8225444452a1486bd721f3285301fe84643b00Stephen Hines    ID.AddPointer(state.get());
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