CoreEngine.h revision a19f4af7a94835ce4693bfe12d6270754e79eb56
1d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis//==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- C++ -*-//
21eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump//
3f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//                     The LLVM Compiler Infrastructure
4f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//
5f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// This file is distributed under the University of Illinois Open Source
6f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// License. See LICENSE.TXT for details.
7f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//
8f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//===----------------------------------------------------------------------===//
9f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//
10f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//  This file defines a generic engine for intraprocedural, path-sensitive,
118e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek//  dataflow analysis via graph reachability.
12f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//
13f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//===----------------------------------------------------------------------===//
14f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
15d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis#ifndef LLVM_CLANG_GR_COREENGINE
16d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis#define LLVM_CLANG_GR_COREENGINE
17f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
1899c6ad3f22b865d0f4cce52bc36904403c9ed4c4Ted Kremenek#include "clang/AST/Expr.h"
199b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
209b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
219b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
22f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#include "llvm/ADT/OwningPtr.h"
23f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
24f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremeneknamespace clang {
250111f575b968e423dccae439e501225b8314b257Zhongxing Xu
26ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenekclass ProgramPointTag;
27ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek
289ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento {
295a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
30a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaksclass NodeBuilder;
31a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks
3224f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek//===----------------------------------------------------------------------===//
33d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// CoreEngine - Implements the core logic of the graph-reachability
34922059dec59c7bed235da01aff75ae522a369811Ted Kremenek///   analysis. It traverses the CFG and generates the ExplodedGraph.
35922059dec59c7bed235da01aff75ae522a369811Ted Kremenek///   Program "states" are treated as opaque void pointers.
36d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis///   The template class CoreEngine (which subclasses CoreEngine)
37922059dec59c7bed235da01aff75ae522a369811Ted Kremenek///   provides the matching component to the engine that knows the actual types
38922059dec59c7bed235da01aff75ae522a369811Ted Kremenek///   for states.  Note that this engine only dispatches to transfer functions
39922059dec59c7bed235da01aff75ae522a369811Ted Kremenek///   at the statement and block-level.  The analyses themselves must implement
40922059dec59c7bed235da01aff75ae522a369811Ted Kremenek///   any transfer function logic and the sub-expression level (if any).
41d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CoreEngine {
42f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  friend class CommonNodeBuilder;
43f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  friend class NodeBuilder;
44d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  friend class StmtNodeBuilder;
4527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  friend class GenericNodeBuilderImpl;
46d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  friend class BranchNodeBuilder;
47d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  friend class IndirectGotoNodeBuilder;
48d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  friend class SwitchNodeBuilder;
49e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek  friend class EndOfFunctionNodeBuilder;
50d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  friend class CallEnterNodeBuilder;
51d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  friend class CallExitNodeBuilder;
520111f575b968e423dccae439e501225b8314b257Zhongxing Xu
53a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Carepublic:
54a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care  typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> >
5566750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek            BlocksExhausted;
56422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek
57422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> >
58422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek            BlocksAborted;
59422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek
60a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Careprivate:
61a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care
62d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  SubEngine& SubEng;
630111f575b968e423dccae439e501225b8314b257Zhongxing Xu
64f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  /// G - The simulation graph.  Each node is a (location,state) pair.
6538b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu  llvm::OwningPtr<ExplodedGraph> G;
661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
67f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  /// WList - A set of queued nodes that need to be processed by the
68f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  ///  worklist algorithm.  It is up to the implementation of WList to decide
69f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  ///  the order that nodes are processed.
70d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  WorkList* WList;
711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
72d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  /// BCounterFactory - A factory object for created BlockCounter objects.
738e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek  ///   These are used to record for key nodes in the ExplodedGraph the
748e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek  ///   number of times different CFGBlocks have been visited along a path.
75d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  BlockCounter::Factory BCounterFactory;
76f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek
77f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek  /// The locations where we stopped doing work because we visited a location
78f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek  ///  too many times.
7966750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek  BlocksExhausted blocksExhausted;
80422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek
81422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  /// The locations where we stopped because the engine aborted analysis,
82422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  /// usually because it could not reason about something.
83422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  BlocksAborted blocksAborted;
841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
8518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  void generateNode(const ProgramPoint &Loc,
8618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                    const ProgramState *State,
879c378f705405d37f49795d5e915989de774fe11fTed Kremenek                    ExplodedNode *Pred);
881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
899c378f705405d37f49795d5e915989de774fe11fTed Kremenek  void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
909c378f705405d37f49795d5e915989de774fe11fTed Kremenek  void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
919c378f705405d37f49795d5e915989de774fe11fTed Kremenek  void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
929c378f705405d37f49795d5e915989de774fe11fTed Kremenek  void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
949c378f705405d37f49795d5e915989de774fe11fTed Kremenek  void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
959c378f705405d37f49795d5e915989de774fe11fTed Kremenek                    ExplodedNode *Pred);
96102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  void HandleCallEnter(const CallEnter &L, const CFGBlock *Block,
97102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor                       unsigned Index, ExplodedNode *Pred);
98102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  void HandleCallExit(const CallExit &L, ExplodedNode *Pred);
990111f575b968e423dccae439e501225b8314b257Zhongxing Xu
100f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekprivate:
101d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CoreEngine(const CoreEngine&); // Do not implement.
102d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CoreEngine& operator=(const CoreEngine&);
1031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
104f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic:
105d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  /// Construct a CoreEngine object to analyze the provided CFG using
1060111f575b968e423dccae439e501225b8314b257Zhongxing Xu  ///  a DFS exploration of the exploded graph.
107d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CoreEngine(SubEngine& subengine)
108d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis    : SubEng(subengine), G(new ExplodedGraph()),
10955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek      WList(WorkList::makeBFS()),
110f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek      BCounterFactory(G->getAllocator()) {}
1110111f575b968e423dccae439e501225b8314b257Zhongxing Xu
112d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  /// Construct a CoreEngine object to analyze the provided CFG and to
1130111f575b968e423dccae439e501225b8314b257Zhongxing Xu  ///  use the provided worklist object to execute the worklist algorithm.
114d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  ///  The CoreEngine object assumes ownership of 'wlist'.
115d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CoreEngine(WorkList* wlist, SubEngine& subengine)
116d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis    : SubEng(subengine), G(new ExplodedGraph()), WList(wlist),
117f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek      BCounterFactory(G->getAllocator()) {}
1180111f575b968e423dccae439e501225b8314b257Zhongxing Xu
119d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  ~CoreEngine() {
1200111f575b968e423dccae439e501225b8314b257Zhongxing Xu    delete WList;
1210111f575b968e423dccae439e501225b8314b257Zhongxing Xu  }
1220111f575b968e423dccae439e501225b8314b257Zhongxing Xu
1230111f575b968e423dccae439e501225b8314b257Zhongxing Xu  /// getGraph - Returns the exploded graph.
124031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  ExplodedGraph& getGraph() { return *G.get(); }
1251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
1260111f575b968e423dccae439e501225b8314b257Zhongxing Xu  /// takeGraph - Returns the exploded graph.  Ownership of the graph is
127fc8f0e14ad142ed811e90fbd9a30e419e301c717Chris Lattner  ///  transferred to the caller.
128031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  ExplodedGraph* takeGraph() { return G.take(); }
1290111f575b968e423dccae439e501225b8314b257Zhongxing Xu
130f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
131f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  ///  steps.  Returns true if there is still simulation state on the worklist.
1322ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu  bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
13318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                       const ProgramState *InitState);
13418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  void ExecuteWorkListWithInitialState(const LocationContext *L,
13518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                                       unsigned Steps,
13618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                                       const ProgramState *InitState,
1372ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu                                       ExplodedNodeSet &Dst);
138bc42c533e7d3d946704a49e242939dd232f33072Tom Care
139bc42c533e7d3d946704a49e242939dd232f33072Tom Care  // Functions for external checking of whether we have unfinished work
140422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  bool wasBlockAborted() const { return !blocksAborted.empty(); }
141422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
142422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  bool hasWorkRemaining() const { return wasBlocksExhausted() ||
143422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek                                         WList->hasWork() ||
144422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek                                         wasBlockAborted(); }
145422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek
146422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  /// Inform the CoreEngine that a basic block was aborted because
147422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  /// it could not be completely analyzed.
148422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
149422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek    blocksAborted.push_back(std::make_pair(block, node));
150422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  }
151422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek
152d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  WorkList *getWorkList() const { return WList; }
153f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek
154422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  BlocksExhausted::const_iterator blocks_exhausted_begin() const {
15566750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek    return blocksExhausted.begin();
156f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek  }
157422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  BlocksExhausted::const_iterator blocks_exhausted_end() const {
15866750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek    return blocksExhausted.end();
159f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek  }
160422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  BlocksAborted::const_iterator blocks_aborted_begin() const {
161422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek    return blocksAborted.begin();
162422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  }
163422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  BlocksAborted::const_iterator blocks_aborted_end() const {
164422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek    return blocksAborted.end();
165422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek  }
166a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks
167a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  /// Enqueue the results of the node builder onto the work list.
168a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  void enqueue(NodeBuilder &NB);
169a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks};
170a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks
171a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaksstruct NodeBuilderContext {
172a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  CoreEngine &Eng;
173a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  ExplodedNode *Pred;
174a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  const CFGBlock *Block;
175a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  NodeBuilderContext(CoreEngine &E, ExplodedNode *N, const CFGBlock *B)
176a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    : Eng(E), Pred(N), Block(B) { assert(B); assert(!N->isSink()); }
177f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek};
1781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
179f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks/// This is the simplest builder which generates nodes in the ExplodedGraph.
180f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass NodeBuilder {
181a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaksprotected:
182f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  friend class StmtNodeBuilder;
183f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
184a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  NodeBuilderContext &C;
185f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  bool Finalized;
186f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
187f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  /// \brief The frontier set - a set of nodes which need to be propagated after
188f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  /// the builder dies.
189f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy;
190f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  DeferredTy Deferred;
19171fdf469a3b6d7d557b0bfba36e8659f4966c565Anna Zaks
192a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  BlockCounter getBlockCounter() const { return C.Eng.WList->getBlockCounter();}
193a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks
194a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  bool checkResults() {
195a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    if (!Finalized)
196a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks      return false;
197a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
198a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks      if ((*I)->isSink())
199a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks        return false;
200a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    return true;
201a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  }
202f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
203f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  virtual void finalizeResults() {
204f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks    if (!Finalized) {
205f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks      Finalized = true;
206f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks    }
207f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  }
208f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
209f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
210f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks                                 const ProgramState *State,
211f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks                                 ExplodedNode *Pred,
212f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks                                 bool MarkAsSink = false);
213f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
214f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zakspublic:
215a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  NodeBuilder(NodeBuilderContext &Ctx)
216a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    : C(Ctx), Finalized(false) { Deferred.insert(C.Pred); }
217a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks
218a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  virtual ~NodeBuilder() {}
219f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
220f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  /// \brief Generates a node in the ExplodedGraph.
221f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  ///
222f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  /// When a node is marked as sink, the exploration from the node is stopped -
223f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  /// the node becomes the last node on the path.
224f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  ExplodedNode *generateNode(const ProgramPoint &PP,
225f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks                             const ProgramState *State,
226f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks                             ExplodedNode *Pred,
227f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks                             bool MarkAsSink = false) {
228f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks    return generateNodeImpl(PP, State, Pred, MarkAsSink);
229f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  }
230f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
231f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  // \brief Get the builder's predecessor - the parent to all the other nodes.
232a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  const ExplodedNode *getPred() const { return C.Pred; }
233f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
234f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  bool hasGeneratedNodes() const {
235a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    return (!Deferred.count(C.Pred));
236f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  }
237f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
238f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  typedef DeferredTy::iterator iterator;
239f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  /// \brief Iterators through the results frontier.
240a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  inline iterator results_begin() {
241a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    finalizeResults();
242a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    assert(checkResults());
243a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    return Deferred.begin();
244a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  }
245a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  inline iterator results_end() {
246a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    finalizeResults();
247a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    return Deferred.end();
248a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  }
249f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
250a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  /// \brief Returns the number of times the current basic block has been
251a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  /// visited on the exploded graph path.
252a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  unsigned getCurrentBlockCount() const {
253a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    return getBlockCounter().getNumVisited(
254a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks                         C.Pred->getLocationContext()->getCurrentStackFrame(),
255a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks                         C.Block->getBlockID());
256a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  }
257a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks
258a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  ExplodedNode *getPredecessor() const { return C.Pred; }
259f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks};
260f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
261f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass CommonNodeBuilder {
262f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksprotected:
263f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  ExplodedNode *Pred;
264f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zakspublic:
265f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  // TODO: make protected.
266f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  CoreEngine& Eng;
267f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
268f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  CommonNodeBuilder(CoreEngine* E, ExplodedNode *P) : Pred(P), Eng(*E) {}
269f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); }
270f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks};
271f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
272f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
273f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass StmtNodeBuilder: public CommonNodeBuilder {
274f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  const CFGBlock &B;
275f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  const unsigned Idx;
276031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
277031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xupublic:
278031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  bool PurgingDeadSymbols;
279031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  bool BuildSinks;
280b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek  bool hasGeneratedNode;
281031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  ProgramPoint::Kind PointKind;
282ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek  const ProgramPointTag *Tag;
2831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
284c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu  typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy;
285f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  DeferredTy Deferred;
2861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
2879c378f705405d37f49795d5e915989de774fe11fTed Kremenek  void GenerateAutoTransition(ExplodedNode *N);
2881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
289f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic:
29018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  StmtNodeBuilder(const CFGBlock *b,
29118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                  unsigned idx,
29218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                  ExplodedNode *N,
29371fdf469a3b6d7d557b0bfba36e8659f4966c565Anna Zaks                  CoreEngine* e);
2941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
295d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  ~StmtNodeBuilder();
2961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
2979c378f705405d37f49795d5e915989de774fe11fTed Kremenek  ExplodedNode *getPredecessor() const { return Pred; }
298f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
29900a3a5f024ac54088ab887712b292171188064f0Ted Kremenek  unsigned getCurrentBlockCount() const {
300d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu    return getBlockCounter().getNumVisited(
301d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu                            Pred->getLocationContext()->getCurrentStackFrame(),
302d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu                                           B.getBlockID());
3031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump  }
304031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
30518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateNode(const Stmt *S,
30618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             const ProgramState *St,
30718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             ExplodedNode *Pred,
30818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             ProgramPoint::Kind K,
309ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek                             const ProgramPointTag *tag = 0) {
310b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek    hasGeneratedNode = true;
311031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
3121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump    if (PurgingDeadSymbols)
3131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump      K = ProgramPoint::PostPurgeDeadSymbolsKind;
314031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
3154bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek    return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag);
316031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  }
3171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
31818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateNode(const Stmt *S,
31918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             const ProgramState *St,
320ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek                             ExplodedNode *Pred,
321ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek                             const ProgramPointTag *tag = 0) {
3224bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek    return generateNode(S, St, Pred, PointKind, tag);
323031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  }
324031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
32518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateNode(const ProgramPoint &PP,
32618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             const ProgramState *State,
3279c378f705405d37f49795d5e915989de774fe11fTed Kremenek                             ExplodedNode *Pred) {
328b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek    hasGeneratedNode = true;
329102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor    return generateNodeInternal(PP, State, Pred);
330102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  }
331102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
332c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu  ExplodedNode*
33318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  generateNodeInternal(const ProgramPoint &PP,
33418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                       const ProgramState *State,
3359c378f705405d37f49795d5e915989de774fe11fTed Kremenek                       ExplodedNode *Pred);
3361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
337c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu  ExplodedNode*
33818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  generateNodeInternal(const Stmt *S,
33918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                       const ProgramState *State,
34018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                       ExplodedNode *Pred,
34115e24065a4a8b6b9d58e138969f8f6ac7495d837Anna Zaks                       ProgramPoint::Kind K,
34218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                       const ProgramPointTag *tag = 0);
3431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
344331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek  /// getStmt - Return the current block-level expression associated with
345331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek  ///  this builder.
3469c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const Stmt *getStmt() const {
3473c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek    const CFGStmt *CS = B[Idx].getAs<CFGStmt>();
3483c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek    return CS ? CS->getStmt() : 0;
349b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu  }
3501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
351331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek  /// getBlock - Return the CFGBlock associated with the block-level expression
352331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek  ///  of this builder.
3539c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock *getBlock() const { return &B; }
354bdb435ddaafd5069becd543d638112f68825b89dTed Kremenek
355598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu  unsigned getIndex() const { return Idx; }
356598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu
35718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *MakeNode(ExplodedNodeSet &Dst,
35818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                         const Stmt *S,
35918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                         ExplodedNode *Pred,
36018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                         const ProgramState *St) {
361bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek    return MakeNode(Dst, S, Pred, St, PointKind);
362bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek  }
3631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
36418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *MakeNode(ExplodedNodeSet &Dst,
36518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                         const Stmt *S,
36618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                         ExplodedNode *Pred,
36718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                         const ProgramState *St,
36818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                         ProgramPoint::Kind K);
3691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
37018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst,
37118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             const Stmt *S,
37218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             ExplodedNode *Pred,
37318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             const ProgramState *St) {
37470a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek    bool Tmp = BuildSinks;
37570a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek    BuildSinks = true;
3769c378f705405d37f49795d5e915989de774fe11fTed Kremenek    ExplodedNode *N = MakeNode(Dst, S, Pred, St);
37770a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek    BuildSinks = Tmp;
37870a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek    return N;
37970a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek  }
380f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks
381f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  void importNodesFromBuilder(const NodeBuilder &NB) {
382f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks    ExplodedNode *NBPred = const_cast<ExplodedNode*>(NB.getPred());
383f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks    if (NB.hasGeneratedNodes()) {
384f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks      Deferred.erase(NBPred);
385f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks      Deferred.insert(NB.Deferred.begin(), NB.Deferred.end());
386f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks      hasGeneratedNode = true;
387f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks    }
388f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  }
389f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek};
3901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
391a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaksclass BranchNodeBuilder: public NodeBuilder {
3929c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock *DstT;
3939c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock *DstF;
39452a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek
39571c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek  bool GeneratedTrue;
39671c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek  bool GeneratedFalse;
397520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek  bool InFeasibleTrue;
398520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek  bool InFeasibleFalse;
3991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
400a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  void finalizeResults() {
401a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    if (Finalized)
402a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks      return;
403a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    if (!GeneratedTrue) generateNode(C.Pred->State, true);
404a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    if (!GeneratedFalse) generateNode(C.Pred->State, false);
405a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    Finalized = true;
406a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  }
407a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks
4087d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekpublic:
409a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  BranchNodeBuilder(NodeBuilderContext &C, const CFGBlock *dstT,
410a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks                    const CFGBlock *dstF)
411a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  : NodeBuilder(C), DstT(dstT), DstF(dstF),
412520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek    GeneratedTrue(false), GeneratedFalse(false),
413a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks    InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
414a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  }
415031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
416a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  /// This function generate a new ExplodedNode but not a new
417a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  /// branch(block edge). Creates a transition from the Builder's top
418a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  /// predecessor.
419f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks  ExplodedNode *generateNode(const Stmt *Condition, const ProgramState *State,
420a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks                             const ProgramPointTag *Tag = 0,
421a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks                             bool MarkAsSink = false);
4228083414ee7cc8f5c807ed6a4e120fb4e0ab50ff8Ted Kremenek
423a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks  ExplodedNode *generateNode(const ProgramState *State, bool branch,
424a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks                             ExplodedNode *Pred = 0);
4251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
4269c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock *getTargetBlock(bool branch) const {
4278e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek    return branch ? DstT : DstF;
4281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump  }
4291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
43052a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek  void markInfeasible(bool branch) {
431520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek    if (branch)
432520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek      InFeasibleTrue = GeneratedTrue = true;
433520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek    else
434520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek      InFeasibleFalse = GeneratedFalse = true;
435520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek  }
4361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
437520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek  bool isFeasible(bool branch) {
438520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek    return branch ? !InFeasibleTrue : !InFeasibleFalse;
43952a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek  }
4401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
44118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  const ProgramState *getState() const {
442b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek    return getPredecessor()->getState();
443b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek  }
4447d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek};
445031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
446d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass IndirectGotoNodeBuilder {
447d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CoreEngine& Eng;
4489c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock *Src;
4499c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock &DispatchBlock;
4509c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const Expr *E;
4519c378f705405d37f49795d5e915989de774fe11fTed Kremenek  ExplodedNode *Pred;
452031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
453754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekpublic:
4549c378f705405d37f49795d5e915989de774fe11fTed Kremenek  IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
4559c378f705405d37f49795d5e915989de774fe11fTed Kremenek                    const Expr *e, const CFGBlock *dispatch, CoreEngine* eng)
45603509aea098772644bf4662dc1c88634818ceeccZhongxing Xu    : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
457754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek
458031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  class iterator {
45903509aea098772644bf4662dc1c88634818ceeccZhongxing Xu    CFGBlock::const_succ_iterator I;
4601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
461d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis    friend class IndirectGotoNodeBuilder;
46203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu    iterator(CFGBlock::const_succ_iterator i) : I(i) {}
463754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek  public:
4641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
4659c378f705405d37f49795d5e915989de774fe11fTed Kremenek    iterator &operator++() { ++I; return *this; }
4669c378f705405d37f49795d5e915989de774fe11fTed Kremenek    bool operator!=(const iterator &X) const { return I != X.I; }
4671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
468ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner    const LabelDecl *getLabel() const {
469ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner      return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl();
47024f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek    }
4711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
472ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner    const CFGBlock *getBlock() const {
47324f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek      return *I;
47424f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek    }
475754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek  };
4761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
477031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  iterator begin() { return iterator(DispatchBlock.succ_begin()); }
478031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  iterator end() { return iterator(DispatchBlock.succ_end()); }
4791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
48018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateNode(const iterator &I,
48118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             const ProgramState *State,
482031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu                             bool isSink = false);
4831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
4849c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const Expr *getTarget() const { return E; }
485754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek
48618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  const ProgramState *getState() const { return Pred->State; }
487754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek};
4881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
489d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass SwitchNodeBuilder {
490d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CoreEngine& Eng;
4919c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock *Src;
4929c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const Expr *Condition;
4939c378f705405d37f49795d5e915989de774fe11fTed Kremenek  ExplodedNode *Pred;
494031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
495daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekpublic:
4969c378f705405d37f49795d5e915989de774fe11fTed Kremenek  SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
4979c378f705405d37f49795d5e915989de774fe11fTed Kremenek                    const Expr *condition, CoreEngine* eng)
498daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek  : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
4991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
500031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  class iterator {
50103509aea098772644bf4662dc1c88634818ceeccZhongxing Xu    CFGBlock::const_succ_reverse_iterator I;
5021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
503d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis    friend class SwitchNodeBuilder;
50403509aea098772644bf4662dc1c88634818ceeccZhongxing Xu    iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
505031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu
506daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek  public:
5079c378f705405d37f49795d5e915989de774fe11fTed Kremenek    iterator &operator++() { ++I; return *this; }
50834feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek    bool operator!=(const iterator &X) const { return I != X.I; }
50934feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek    bool operator==(const iterator &X) const { return I == X.I; }
5101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
5119c378f705405d37f49795d5e915989de774fe11fTed Kremenek    const CaseStmt *getCase() const {
512daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek      return llvm::cast<CaseStmt>((*I)->getLabel());
513daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek    }
5141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
5159c378f705405d37f49795d5e915989de774fe11fTed Kremenek    const CFGBlock *getBlock() const {
516daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek      return *I;
517daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek    }
518daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek  };
5191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
520031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  iterator begin() { return iterator(Src->succ_rbegin()+1); }
521031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu  iterator end() { return iterator(Src->succ_rend()); }
5221eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
5234d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek  const SwitchStmt *getSwitch() const {
5244d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek    return llvm::cast<SwitchStmt>(Src->getTerminator());
5254d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek  }
5264d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek
52718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateCaseStmtNode(const iterator &I,
52818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                                     const ProgramState *State);
5291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
53018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateDefaultCaseNode(const ProgramState *State,
531031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu                                        bool isSink = false);
5321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
5339c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const Expr *getCondition() const { return Condition; }
534daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek
53518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  const ProgramState *getState() const { return Pred->State; }
536daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek};
53711062b118476368fa5b294954713e5df97d8599fTed Kremenek
53827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilderImpl {
53927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekprotected:
54027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  CoreEngine &engine;
54127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  ExplodedNode *pred;
54227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  ProgramPoint pp;
543686775deca8b8685eb90801495880e3abdd844c2Chris Lattner  SmallVector<ExplodedNode*, 2> sinksGenerated;
54427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
54518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateNodeImpl(const ProgramState *state,
54618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                                 ExplodedNode *pred,
54718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                                 ProgramPoint programPoint,
54818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                                 bool asSink);
54927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
55027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p)
551b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek    : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {}
55227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
55327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic:
554b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek  bool hasGeneratedNode;
55527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
55627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  WorkList &getWorkList() { return *engine.WList; }
55727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
5589c378f705405d37f49795d5e915989de774fe11fTed Kremenek  ExplodedNode *getPredecessor() const { return pred; }
55927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
56027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  BlockCounter getBlockCounter() const {
56127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek    return engine.WList->getBlockCounter();
56227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  }
56327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
564686775deca8b8685eb90801495880e3abdd844c2Chris Lattner  const SmallVectorImpl<ExplodedNode*> &sinks() const {
56527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek    return sinksGenerated;
56627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  }
56727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek};
56827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
569b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenektemplate <typename PP_T>
57027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilder : public GenericNodeBuilderImpl {
57127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic:
572b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek  GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p)
57327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek    : GenericNodeBuilderImpl(eng, pr, p) {}
57427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
57518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred,
576ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek                             const ProgramPointTag *tag, bool asSink) {
577b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek    return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag),
578b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek                            asSink);
57927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek  }
58027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
581b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek  const PP_T &getProgramPoint() const { return cast<PP_T>(pp); }
58227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek};
58327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek
584f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass EndOfFunctionNodeBuilder : public CommonNodeBuilder {
5859c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock &B;
586ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek  const ProgramPointTag *Tag;
587f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xu
588f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xupublic:
589b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek  bool hasGeneratedNode;
5901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
59111062b118476368fa5b294954713e5df97d8599fTed Kremenekpublic:
5929c378f705405d37f49795d5e915989de774fe11fTed Kremenek  EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e,
593ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek                           const ProgramPointTag *tag = 0)
594f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks    : CommonNodeBuilder(e, N), B(*b), Tag(tag), hasGeneratedNode(false) {}
5951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
596e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek  ~EndOfFunctionNodeBuilder();
5971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
598ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek  EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) {
599f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis    return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag);
600f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis  }
601f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis
602d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  WorkList &getWorkList() { return *Eng.WList; }
603598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu
6049c378f705405d37f49795d5e915989de774fe11fTed Kremenek  ExplodedNode *getPredecessor() const { return Pred; }
6051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
60611062b118476368fa5b294954713e5df97d8599fTed Kremenek  unsigned getCurrentBlockCount() const {
607d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu    return getBlockCounter().getNumVisited(
608d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu                            Pred->getLocationContext()->getCurrentStackFrame(),
609d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu                                           B.getBlockID());
6101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump  }
6111eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
61218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  ExplodedNode *generateNode(const ProgramState *State,
61318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek                             ExplodedNode *P = 0,
614ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek                             const ProgramPointTag *tag = 0);
6151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
61618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  void GenerateCallExitNode(const ProgramState *state);
617102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
6189c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock *getBlock() const { return &B; }
61911062b118476368fa5b294954713e5df97d8599fTed Kremenek
62018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  const ProgramState *getState() const {
62111062b118476368fa5b294954713e5df97d8599fTed Kremenek    return getPredecessor()->getState();
62211062b118476368fa5b294954713e5df97d8599fTed Kremenek  }
62311062b118476368fa5b294954713e5df97d8599fTed Kremenek};
624754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek
625d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallEnterNodeBuilder {
626d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CoreEngine &Eng;
627102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
628102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  const ExplodedNode *Pred;
629102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
63019b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu  // The call site. For implicit automatic object dtor, this is the trigger
63119b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu  // statement.
632102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  const Stmt *CE;
633102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
63419b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu  // The context of the callee.
63519b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu  const StackFrameContext *CalleeCtx;
636102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
637102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  // The parent block of the CallExpr.
638102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  const CFGBlock *Block;
639102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
640102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  // The CFGBlock index of the CallExpr.
641102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  unsigned Index;
642102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
643102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic:
644d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred,
64519b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu                         const Stmt *s, const StackFrameContext *callee,
646102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor                         const CFGBlock *blk, unsigned idx)
647c6238d2786cfd961b94580b3d3675a1b3ff0721cZhongxing Xu    : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {}
648102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
64918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  const ProgramState *getState() const { return Pred->getState(); }
650102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
651102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  const LocationContext *getLocationContext() const {
652102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor    return Pred->getLocationContext();
653102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  }
654102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
655102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  const Stmt *getCallExpr() const { return CE; }
656102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
65719b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu  const StackFrameContext *getCalleeContext() const { return CalleeCtx; }
658102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
659102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  const CFGBlock *getBlock() const { return Block; }
660102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
661102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  unsigned getIndex() const { return Index; }
662102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
66318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  void generateNode(const ProgramState *state);
664102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor};
665102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
666d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallExitNodeBuilder {
667d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CoreEngine &Eng;
668102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  const ExplodedNode *Pred;
669102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
670102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic:
671d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred)
672102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor    : Eng(eng), Pred(pred) {}
673102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
674102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor  const ExplodedNode *getPredecessor() const { return Pred; }
675102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
67618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  const ProgramState *getState() const { return Pred->getState(); }
677102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor
67818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek  void generateNode(const ProgramState *state);
679102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor};
6805a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
6815a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace
6825a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
683f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} // end clang namespace
684f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
685f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#endif
686