CoreEngine.h revision 6b6152ba96c164a292cc0b8d8b1d4cecbec27a60
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. 1681aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks void enqueue(ExplodedNodeSet &NB); 169a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks}; 170a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks 171a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaksstruct NodeBuilderContext { 172a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks CoreEngine &Eng; 173a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks const CFGBlock *Block; 174c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks ExplodedNode *ContextPred; 175c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks NodeBuilderContext(CoreEngine &E, const CFGBlock *B, ExplodedNode *N) 176c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks : Eng(E), Block(B), ContextPred(N) { 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 184cd656cab3fa3dd4b0c974c6ae1c0e60880b18c22Anna Zaks const NodeBuilderContext &C; 185319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks 1863152b3cb5b6a2f797d0972c81a5eb3fd69c0d620Anna Zaks /// Specifies if the builder results have been finalized. For example, if it 1873152b3cb5b6a2f797d0972c81a5eb3fd69c0d620Anna Zaks /// is set to false, autotransitions are yet to be generated. 188f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool Finalized; 189f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 1904e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks bool HasGeneratedNodes; 1914e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks 192f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// \brief The frontier set - a set of nodes which need to be propagated after 193f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// the builder dies. 1941aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks ExplodedNodeSet &Frontier; 19571fdf469a3b6d7d557b0bfba36e8659f4966c565Anna Zaks 196a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks BlockCounter getBlockCounter() const { return C.Eng.WList->getBlockCounter();} 197a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks 1983152b3cb5b6a2f797d0972c81a5eb3fd69c0d620Anna Zaks /// Checkes if the results are ready. 1993152b3cb5b6a2f797d0972c81a5eb3fd69c0d620Anna Zaks virtual bool checkResults() { 200a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks if (!Finalized) 201a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks return false; 202a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks return true; 203a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks } 204f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 2058ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks bool haveNoSinksInFrontier() { 2068ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) { 2078ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks if ((*I)->isSink()) 2088ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks return false; 2098ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks } 2108ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks return true; 2118ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks } 2128ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks 2133152b3cb5b6a2f797d0972c81a5eb3fd69c0d620Anna Zaks /// Allow subclasses to finalize results before result_begin() is executed. 2143152b3cb5b6a2f797d0972c81a5eb3fd69c0d620Anna Zaks virtual void finalizeResults() {} 215f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 216f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 217f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const ProgramState *State, 218f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *Pred, 219f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool MarkAsSink = false); 220f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 221f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zakspublic: 2221aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 2231aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks const NodeBuilderContext &Ctx, bool F = true) 2241aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 2258ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks // assert(DstSet.empty()); 2268ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks Frontier.Add(SrcNode); 227ad62deeb70e97da6bd514dd390ea1ce6af6ad81dAnna Zaks } 228a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks 2291aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 2301aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks const NodeBuilderContext &Ctx, bool F = true) 2311aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 2328ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks //assert(DstSet.empty()); 2338ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks //assert(!SrcSet.empty()); 2341aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks Frontier.insert(SrcSet); 2358ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks assert(haveNoSinksInFrontier()); 236cd656cab3fa3dd4b0c974c6ae1c0e60880b18c22Anna Zaks } 237cd656cab3fa3dd4b0c974c6ae1c0e60880b18c22Anna Zaks 238a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks virtual ~NodeBuilder() {} 239f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 240f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// \brief Generates a node in the ExplodedGraph. 241f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// 242f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// When a node is marked as sink, the exploration from the node is stopped - 243f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// the node becomes the last node on the path. 244f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *generateNode(const ProgramPoint &PP, 245f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const ProgramState *State, 246f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *Pred, 247f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool MarkAsSink = false) { 248f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks return generateNodeImpl(PP, State, Pred, MarkAsSink); 249f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 250f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 2514e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks // TODO: will get removed. 252f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool hasGeneratedNodes() const { 2534e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks return HasGeneratedNodes; 254f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 255f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 2561aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks const ExplodedNodeSet &getResults() { 2571aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks finalizeResults(); 2581aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks assert(checkResults()); 2591aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks return Frontier; 2601aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks } 2611aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks 2621aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks typedef ExplodedNodeSet::iterator iterator; 263f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// \brief Iterators through the results frontier. 2641aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks inline iterator begin() { 265a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks finalizeResults(); 266a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks assert(checkResults()); 2671aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks return Frontier.begin(); 268a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks } 2691aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks inline iterator end() { 270a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks finalizeResults(); 2711aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks return Frontier.end(); 272a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks } 273f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 274319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks /// \brief Return the CFGBlock associated with this builder. 275319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks const CFGBlock *getBlock() const { return C.Block; } 276319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks 2771aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks const NodeBuilderContext &getContext() { return C; } 2781aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks 279a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks /// \brief Returns the number of times the current basic block has been 280a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks /// visited on the exploded graph path. 281a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks unsigned getCurrentBlockCount() const { 282a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks return getBlockCounter().getNumVisited( 283c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks C.ContextPred->getLocationContext()->getCurrentStackFrame(), 284c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks C.Block->getBlockID()); 285a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks } 286f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks}; 287f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 288f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass CommonNodeBuilder { 289f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksprotected: 290f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *Pred; 291f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks CoreEngine& Eng; 292f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 293f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks CommonNodeBuilder(CoreEngine* E, ExplodedNode *P) : Pred(P), Eng(*E) {} 294f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); } 295f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks}; 296f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 297f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 2988ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaksclass PureStmtNodeBuilder: public NodeBuilder { 2998ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zakspublic: 3008ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks PureStmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 3018ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks const NodeBuilderContext &Ctx) 3028ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks : NodeBuilder(SrcNode, DstSet, Ctx) {} 3038ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks 3046b6152ba96c164a292cc0b8d8b1d4cecbec27a60Anna Zaks PureStmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 3056b6152ba96c164a292cc0b8d8b1d4cecbec27a60Anna Zaks const NodeBuilderContext &Ctx) 3066b6152ba96c164a292cc0b8d8b1d4cecbec27a60Anna Zaks : NodeBuilder(SrcSet, DstSet, Ctx) {} 3076b6152ba96c164a292cc0b8d8b1d4cecbec27a60Anna Zaks 3088ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks ExplodedNode *generateNode(const Stmt *S, 3098ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks ExplodedNode *Pred, 3108ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks const ProgramState *St, 3118ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks ProgramPoint::Kind K = ProgramPoint::PostStmtKind, 3128ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks bool MarkAsSink = false, 3138ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks const ProgramPointTag *tag = 0, 3148ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks bool Purging = false) { 3158ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks if (Purging) { 3168ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks assert(K == ProgramPoint::PostStmtKind); 3178ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks K = ProgramPoint::PostPurgeDeadSymbolsKind; 3188ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks } 3198ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks 3208ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 3218ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks Pred->getLocationContext(), tag); 3228ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks return generateNodeImpl(L, St, Pred, MarkAsSink); 3238ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks } 3248ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks}; 3258ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks 3268ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaksclass StmtNodeBuilder : public NodeBuilder { 327f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const unsigned Idx; 328031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 329031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xupublic: 330031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool PurgingDeadSymbols; 331031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool BuildSinks; 332319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks // TODO: Remove the flag. We should be able to use the method in the parent. 333b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 334031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ProgramPoint::Kind PointKind; 335ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *Tag; 3361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3379c378f705405d37f49795d5e915989de774fe11fTed Kremenek void GenerateAutoTransition(ExplodedNode *N); 3381eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3391aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 3401aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks unsigned idx, const NodeBuilderContext &Ctx) 3411aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks : NodeBuilder(SrcNode, DstSet, Ctx), Idx(idx), 3421aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks PurgingDeadSymbols(false), BuildSinks(false), hasGeneratedNode(false), 3431aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks PointKind(ProgramPoint::PostStmtKind), Tag(0) {} 3441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3458ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks virtual ~StmtNodeBuilder(); 3468ad8c546372fe602708cb7ceeaf0ebbb866735c6Anna Zaks 34718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const Stmt *S, 34818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 34918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 35018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint::Kind K, 351319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks const ProgramPointTag *tag = 0, 352319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks bool MarkAsSink = false) { 3531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (PurgingDeadSymbols) 3541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump K = ProgramPoint::PostPurgeDeadSymbolsKind; 355031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 356319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 357319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks Pred->getLocationContext(), tag ? tag : Tag); 358319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks return generateNodeImpl(L, St, Pred, MarkAsSink); 359031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 3601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 36118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const Stmt *S, 36218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 363ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek ExplodedNode *Pred, 364ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0) { 3654bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNode(S, St, Pred, PointKind, tag); 366031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 367031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 36818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramPoint &PP, 36918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 3709c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred) { 371319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks return generateNodeImpl(PP, State, Pred, false); 372102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 373102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 374331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getStmt - Return the current block-level expression associated with 375331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// this builder. 3769c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Stmt *getStmt() const { 377319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks const CFGStmt *CS = (*C.Block)[Idx].getAs<CFGStmt>(); 3783c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek return CS ? CS->getStmt() : 0; 379b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu } 3801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 381598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu unsigned getIndex() const { return Idx; } 382598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 38318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 38418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 38518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 38618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St) { 387bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek return MakeNode(Dst, S, Pred, St, PointKind); 388bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek } 3891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 39018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 39118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 39218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 39318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 39418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint::Kind K); 3951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 39618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, 39718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 39818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 39918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St) { 40070a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek bool Tmp = BuildSinks; 40170a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = true; 4029c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *N = MakeNode(Dst, S, Pred, St); 40370a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = Tmp; 40470a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek return N; 40570a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek } 406f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 4078ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks void takeNodes(const ExplodedNodeSet &S) { 4088ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I ) 4098ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks Frontier.erase(*I); 410f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 4118ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks 4128ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks void takeNodes(ExplodedNode *N) { 4138ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks Frontier.erase(N); 4148ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks } 4158ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks 4168ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks void addNodes(const ExplodedNodeSet &S) { 4178ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks Frontier.insert(S); 4188ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks } 4198ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks 4208ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks void addNodes(ExplodedNode *N) { 4218ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks Frontier.Add(N); 4228ff5c41f2bde7ebbe568b4c15e59f14b8befae66Anna Zaks } 423f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 4241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 425a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaksclass BranchNodeBuilder: public NodeBuilder { 4269c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *DstT; 4279c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *DstF; 42852a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek 429520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleTrue; 430520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleFalse; 4311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4327d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekpublic: 4331aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 4341aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks const NodeBuilderContext &C, 435ad62deeb70e97da6bd514dd390ea1ce6af6ad81dAnna Zaks const CFGBlock *dstT, const CFGBlock *dstF) 4361aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF), 4374e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 438031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 4391aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 4401aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks const NodeBuilderContext &C, 4411aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks const CFGBlock *dstT, const CFGBlock *dstF) 4421aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF), 4434e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 4448083414ee7cc8f5c807ed6a4e120fb4e0ab50ff8Ted Kremenek 445a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks ExplodedNode *generateNode(const ProgramState *State, bool branch, 446c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks ExplodedNode *Pred); 4471eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4489c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getTargetBlock(bool branch) const { 4498e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek return branch ? DstT : DstF; 4501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 4511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 45252a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek void markInfeasible(bool branch) { 453520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek if (branch) 4544e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks InFeasibleTrue = true; 455520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek else 4564e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks InFeasibleFalse = true; 457520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek } 4581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 459520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool isFeasible(bool branch) { 460520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek return branch ? !InFeasibleTrue : !InFeasibleFalse; 46152a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek } 4627d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek}; 463031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 464d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass IndirectGotoNodeBuilder { 465d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 4669c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Src; 4679c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock &DispatchBlock; 4689c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *E; 4699c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 470031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 471754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekpublic: 4729c378f705405d37f49795d5e915989de774fe11fTed Kremenek IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 4739c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 47403509aea098772644bf4662dc1c88634818ceeccZhongxing Xu : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 475754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 476031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 47703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_iterator I; 4781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 479d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 48003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_iterator i) : I(i) {} 481754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek public: 4821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4839c378f705405d37f49795d5e915989de774fe11fTed Kremenek iterator &operator++() { ++I; return *this; } 4849c378f705405d37f49795d5e915989de774fe11fTed Kremenek bool operator!=(const iterator &X) const { return I != X.I; } 4851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 486ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const LabelDecl *getLabel() const { 487ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 48824f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 4891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 490ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const CFGBlock *getBlock() const { 49124f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek return *I; 49224f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 493754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek }; 4941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 495031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(DispatchBlock.succ_begin()); } 496031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(DispatchBlock.succ_end()); } 4971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 49818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const iterator &I, 49918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 500031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 5011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5029c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *getTarget() const { return E; } 503754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 50418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->State; } 505754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek}; 5061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 507d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass SwitchNodeBuilder { 508d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 5099c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Src; 5109c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *Condition; 5119c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 512031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 513daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekpublic: 5149c378f705405d37f49795d5e915989de774fe11fTed Kremenek SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 5159c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *condition, CoreEngine* eng) 516daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 5171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 518031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 51903509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_reverse_iterator I; 5201eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 521d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 52203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 523031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 524daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek public: 5259c378f705405d37f49795d5e915989de774fe11fTed Kremenek iterator &operator++() { ++I; return *this; } 52634feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator!=(const iterator &X) const { return I != X.I; } 52734feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator==(const iterator &X) const { return I == X.I; } 5281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5299c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CaseStmt *getCase() const { 530daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return llvm::cast<CaseStmt>((*I)->getLabel()); 531daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 5321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5339c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getBlock() const { 534daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return *I; 535daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 536daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek }; 5371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 538031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(Src->succ_rbegin()+1); } 539031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(Src->succ_rend()); } 5401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5414d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek const SwitchStmt *getSwitch() const { 5424d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek return llvm::cast<SwitchStmt>(Src->getTerminator()); 5434d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek } 5444d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek 54518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateCaseStmtNode(const iterator &I, 54618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State); 5471eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 54818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 549031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 5501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5519c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *getCondition() const { return Condition; } 552daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 55318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->State; } 554daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek}; 55511062b118476368fa5b294954713e5df97d8599fTed Kremenek 55627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilderImpl { 55727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekprotected: 55827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek CoreEngine &engine; 55927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *pred; 56027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ProgramPoint pp; 561686775deca8b8685eb90801495880e3abdd844c2Chris Lattner SmallVector<ExplodedNode*, 2> sinksGenerated; 56227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 56318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNodeImpl(const ProgramState *state, 56418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *pred, 56518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint programPoint, 56618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek bool asSink); 56727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 56827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 569b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 57027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 57127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 572b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 57327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 57427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek WorkList &getWorkList() { return *engine.WList; } 57527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 5769c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return pred; } 57727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 57827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek BlockCounter getBlockCounter() const { 57927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return engine.WList->getBlockCounter(); 58027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 58127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 582686775deca8b8685eb90801495880e3abdd844c2Chris Lattner const SmallVectorImpl<ExplodedNode*> &sinks() const { 58327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return sinksGenerated; 58427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 58527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 58627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 587b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenektemplate <typename PP_T> 58827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilder : public GenericNodeBuilderImpl { 58927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 590b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 59127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek : GenericNodeBuilderImpl(eng, pr, p) {} 59227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 59318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred, 594ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag, bool asSink) { 595b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 596b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek asSink); 59727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 59827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 599b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 60027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 60127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 602f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass EndOfFunctionNodeBuilder : public CommonNodeBuilder { 6039c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock &B; 604ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *Tag; 605f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xu 606f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xupublic: 607b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 6081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 60911062b118476368fa5b294954713e5df97d8599fTed Kremenekpublic: 6109c378f705405d37f49795d5e915989de774fe11fTed Kremenek EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, 611ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0) 612f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks : CommonNodeBuilder(e, N), B(*b), Tag(tag), hasGeneratedNode(false) {} 6131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 614e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek ~EndOfFunctionNodeBuilder(); 6151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 616ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { 617f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 618f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis } 619f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis 620d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList &getWorkList() { return *Eng.WList; } 621598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 6229c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return Pred; } 6231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 62411062b118476368fa5b294954713e5df97d8599fTed Kremenek unsigned getCurrentBlockCount() const { 625d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return getBlockCounter().getNumVisited( 626d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 627d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu B.getBlockID()); 6281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 6291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 63018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramState *State, 63118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *P = 0, 632ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0); 6331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 63418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void GenerateCallExitNode(const ProgramState *state); 635102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 6369c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getBlock() const { return &B; } 63711062b118476368fa5b294954713e5df97d8599fTed Kremenek 63818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { 63911062b118476368fa5b294954713e5df97d8599fTed Kremenek return getPredecessor()->getState(); 64011062b118476368fa5b294954713e5df97d8599fTed Kremenek } 64111062b118476368fa5b294954713e5df97d8599fTed Kremenek}; 642754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 643d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallEnterNodeBuilder { 644d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 645102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 646102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 647102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 64819b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The call site. For implicit automatic object dtor, this is the trigger 64919b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // statement. 650102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *CE; 651102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 65219b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The context of the callee. 65319b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *CalleeCtx; 654102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 655102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The parent block of the CallExpr. 656102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *Block; 657102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 658102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The CFGBlock index of the CallExpr. 659102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index; 660102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 661102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 662d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 66319b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const Stmt *s, const StackFrameContext *callee, 664102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *blk, unsigned idx) 665c6238d2786cfd961b94580b3d3675a1b3ff0721cZhongxing Xu : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 666102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 66718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->getState(); } 668102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 669102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const LocationContext *getLocationContext() const { 670102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return Pred->getLocationContext(); 671102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 672102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 673102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *getCallExpr() const { return CE; } 674102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 67519b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 676102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 677102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *getBlock() const { return Block; } 678102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 679102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned getIndex() const { return Index; } 680102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 68118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void generateNode(const ProgramState *state); 682102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 683102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 684d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallExitNodeBuilder { 685d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 686102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 687102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 688102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 689d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 690102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor : Eng(eng), Pred(pred) {} 691102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 692102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *getPredecessor() const { return Pred; } 693102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 69418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->getState(); } 695102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 69618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void generateNode(const ProgramState *state); 697102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 6985a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 6995a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 7005a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 701f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} // end clang namespace 702f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 703f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#endif 704