CoreEngine.h revision f05aac8472d8ed081a361a218fd14d59ddc91b85
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 3024f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek//===----------------------------------------------------------------------===// 31d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// CoreEngine - Implements the core logic of the graph-reachability 32922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// analysis. It traverses the CFG and generates the ExplodedGraph. 33922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// Program "states" are treated as opaque void pointers. 34d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis/// The template class CoreEngine (which subclasses CoreEngine) 35922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// provides the matching component to the engine that knows the actual types 36922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// for states. Note that this engine only dispatches to transfer functions 37922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// at the statement and block-level. The analyses themselves must implement 38922059dec59c7bed235da01aff75ae522a369811Ted Kremenek/// any transfer function logic and the sub-expression level (if any). 39d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CoreEngine { 40f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks friend class CommonNodeBuilder; 41f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks friend class NodeBuilder; 42d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class StmtNodeBuilder; 4327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek friend class GenericNodeBuilderImpl; 44d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class BranchNodeBuilder; 45d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 46d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 47e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek friend class EndOfFunctionNodeBuilder; 48d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CallEnterNodeBuilder; 49d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class CallExitNodeBuilder; 500111f575b968e423dccae439e501225b8314b257Zhongxing Xu 51a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Carepublic: 52a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 5366750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek BlocksExhausted; 54422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 55422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> > 56422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted; 57422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 58a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Careprivate: 59a7a8a450d908b34fa5f569f2e694ebd4b61aae2fTom Care 60d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis SubEngine& SubEng; 610111f575b968e423dccae439e501225b8314b257Zhongxing Xu 62f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// G - The simulation graph. Each node is a (location,state) pair. 6338b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu llvm::OwningPtr<ExplodedGraph> G; 641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 65f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// WList - A set of queued nodes that need to be processed by the 66f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// worklist algorithm. It is up to the implementation of WList to decide 67f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// the order that nodes are processed. 68d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList* WList; 691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 70d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// BCounterFactory - A factory object for created BlockCounter objects. 718e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek /// These are used to record for key nodes in the ExplodedGraph the 728e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek /// number of times different CFGBlocks have been visited along a path. 73d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter::Factory BCounterFactory; 74f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek 75f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek /// The locations where we stopped doing work because we visited a location 76f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek /// too many times. 7766750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek BlocksExhausted blocksExhausted; 78422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 79422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// The locations where we stopped because the engine aborted analysis, 80422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// usually because it could not reason about something. 81422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted blocksAborted; 821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void generateNode(const ProgramPoint &Loc, 8418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 859c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred); 861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 879c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); 889c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); 899c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); 909c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); 911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 929c378f705405d37f49795d5e915989de774fe11fTed Kremenek void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B, 939c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred); 94102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 95102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index, ExplodedNode *Pred); 96102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor void HandleCallExit(const CallExit &L, ExplodedNode *Pred); 970111f575b968e423dccae439e501225b8314b257Zhongxing Xu 98f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekprivate: 99d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(const CoreEngine&); // Do not implement. 100d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& operator=(const CoreEngine&); 1011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 102f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 103d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// Construct a CoreEngine object to analyze the provided CFG using 1040111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// a DFS exploration of the exploded graph. 105d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(SubEngine& subengine) 106d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis : SubEng(subengine), G(new ExplodedGraph()), 10755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek WList(WorkList::makeBFS()), 108f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BCounterFactory(G->getAllocator()) {} 1090111f575b968e423dccae439e501225b8314b257Zhongxing Xu 110d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// Construct a CoreEngine object to analyze the provided CFG and to 1110111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// use the provided worklist object to execute the worklist algorithm. 112d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis /// The CoreEngine object assumes ownership of 'wlist'. 113d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine(WorkList* wlist, SubEngine& subengine) 114d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), 115f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek BCounterFactory(G->getAllocator()) {} 1160111f575b968e423dccae439e501225b8314b257Zhongxing Xu 117d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~CoreEngine() { 1180111f575b968e423dccae439e501225b8314b257Zhongxing Xu delete WList; 1190111f575b968e423dccae439e501225b8314b257Zhongxing Xu } 1200111f575b968e423dccae439e501225b8314b257Zhongxing Xu 1210111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// getGraph - Returns the exploded graph. 122031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedGraph& getGraph() { return *G.get(); } 1231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1240111f575b968e423dccae439e501225b8314b257Zhongxing Xu /// takeGraph - Returns the exploded graph. Ownership of the graph is 125fc8f0e14ad142ed811e90fbd9a30e419e301c717Chris Lattner /// transferred to the caller. 126031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedGraph* takeGraph() { return G.take(); } 1270111f575b968e423dccae439e501225b8314b257Zhongxing Xu 128f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 129f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek /// steps. Returns true if there is still simulation state on the worklist. 1302ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 13118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *InitState); 13218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void ExecuteWorkListWithInitialState(const LocationContext *L, 13318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek unsigned Steps, 13418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *InitState, 1352ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu ExplodedNodeSet &Dst); 136bc42c533e7d3d946704a49e242939dd232f33072Tom Care 137bc42c533e7d3d946704a49e242939dd232f33072Tom Care // Functions for external checking of whether we have unfinished work 138422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool wasBlockAborted() const { return !blocksAborted.empty(); } 139422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } 140422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek bool hasWorkRemaining() const { return wasBlocksExhausted() || 141422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek WList->hasWork() || 142422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek wasBlockAborted(); } 143422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 144422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// Inform the CoreEngine that a basic block was aborted because 145422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek /// it could not be completely analyzed. 146422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) { 147422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek blocksAborted.push_back(std::make_pair(block, node)); 148422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 149422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek 150d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList *getWorkList() const { return WList; } 151f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek 152422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksExhausted::const_iterator blocks_exhausted_begin() const { 15366750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek return blocksExhausted.begin(); 154f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek } 155422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksExhausted::const_iterator blocks_exhausted_end() const { 15666750fa464ace9f8c41666c8585ec71a248c1ccaTed Kremenek return blocksExhausted.end(); 157f598087b4adfea164acdd5b53ea2951bde740a2dTed Kremenek } 158422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted::const_iterator blocks_aborted_begin() const { 159422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek return blocksAborted.begin(); 160422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 161422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek BlocksAborted::const_iterator blocks_aborted_end() const { 162422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek return blocksAborted.end(); 163422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek } 164f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 1651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 166f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks/// This is the simplest builder which generates nodes in the ExplodedGraph. 167f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass NodeBuilder { 168f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks friend class StmtNodeBuilder; 169f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 170d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 1719c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 172f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool Finalized; 173f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 174f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// \brief The frontier set - a set of nodes which need to be propagated after 175f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// the builder dies. 176f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 177f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks DeferredTy Deferred; 17871fdf469a3b6d7d557b0bfba36e8659f4966c565Anna Zaks 179f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); } 180f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 181f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks virtual void finalizeResults() { 182f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks if (!Finalized) { 183f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks // TODO: Remove assert after refactoring is complete? 184f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) 185f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks assert(!(*I)->isSink()); 186f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks Finalized = true; 187f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 188f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 189f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 190f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 191f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const ProgramState *State, 192f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *Pred, 193f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool MarkAsSink = false); 194f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 195f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zakspublic: 196f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks NodeBuilder(CoreEngine& e, ExplodedNode *pred); 197f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ~NodeBuilder() {} 198f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 199f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// \brief Generates a node in the ExplodedGraph. 200f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// 201f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// When a node is marked as sink, the exploration from the node is stopped - 202f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// the node becomes the last node on the path. 203f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *generateNode(const ProgramPoint &PP, 204f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const ProgramState *State, 205f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *Pred, 206f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool MarkAsSink = false) { 207f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks return generateNodeImpl(PP, State, Pred, MarkAsSink); 208f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 209f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 210f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks // \brief Get the builder's predecessor - the parent to all the other nodes. 211f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const ExplodedNode* getPred() const { return Pred; } 212f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 213f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool hasGeneratedNodes() const { 214f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks return (!Deferred.count(Pred)); 215f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 216f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 217f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks typedef DeferredTy::iterator iterator; 218f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks /// \brief Iterators through the results frontier. 219f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks inline iterator results_begin() { finalizeResults(); return Deferred.begin();} 220f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks inline iterator results_end() { finalizeResults(); return Deferred.end(); } 221f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 222f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks}; 223f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 224f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass CommonNodeBuilder { 225f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksprotected: 226f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *Pred; 227f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zakspublic: 228f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks // TODO: make protected. 229f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks CoreEngine& Eng; 230f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 231f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks CommonNodeBuilder(CoreEngine* E, ExplodedNode *P) : Pred(P), Eng(*E) {} 232f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); } 233f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks}; 234f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 235f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 236f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass StmtNodeBuilder: public CommonNodeBuilder { 237f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const CFGBlock &B; 238f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const unsigned Idx; 239031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 240031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xupublic: 241031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool PurgingDeadSymbols; 242031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool BuildSinks; 243b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 244031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ProgramPoint::Kind PointKind; 245ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *Tag; 2461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 247c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; 248f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek DeferredTy Deferred; 2491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2509c378f705405d37f49795d5e915989de774fe11fTed Kremenek void GenerateAutoTransition(ExplodedNode *N); 2511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 252f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 25318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek StmtNodeBuilder(const CFGBlock *b, 25418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek unsigned idx, 25518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *N, 25671fdf469a3b6d7d557b0bfba36e8659f4966c565Anna Zaks CoreEngine* e); 2571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 258d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~StmtNodeBuilder(); 2591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2609c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return Pred; } 261f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 26200a3a5f024ac54088ab887712b292171188064f0Ted Kremenek unsigned getCurrentBlockCount() const { 263d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return getBlockCounter().getNumVisited( 264d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 265d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu B.getBlockID()); 2661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 267031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 26818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const Stmt *S, 26918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 27018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 27118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint::Kind K, 272ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0) { 273b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 274031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 2751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (PurgingDeadSymbols) 2761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump K = ProgramPoint::PostPurgeDeadSymbolsKind; 277031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 2784bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); 279031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 2801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 28118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const Stmt *S, 28218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 283ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek ExplodedNode *Pred, 284ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0) { 2854bac726dadb09ee38bab8147f1e706380368b362Ted Kremenek return generateNode(S, St, Pred, PointKind, tag); 286031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu } 287031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 28818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramPoint &PP, 28918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 2909c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred) { 291b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek hasGeneratedNode = true; 292102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return generateNodeInternal(PP, State, Pred); 293102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 294102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 295c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* 29618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek generateNodeInternal(const ProgramPoint &PP, 29718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 2989c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred); 2991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 300c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* 30118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek generateNodeInternal(const Stmt *S, 30218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 30318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 30415e24065a4a8b6b9d58e138969f8f6ac7495d837Anna Zaks ProgramPoint::Kind K, 30518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramPointTag *tag = 0); 3061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 307331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getStmt - Return the current block-level expression associated with 308331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// this builder. 3099c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Stmt *getStmt() const { 3103c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek const CFGStmt *CS = B[Idx].getAs<CFGStmt>(); 3113c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek return CS ? CS->getStmt() : 0; 312b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu } 3131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 314331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// getBlock - Return the CFGBlock associated with the block-level expression 315331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek /// of this builder. 3169c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getBlock() const { return &B; } 317bdb435ddaafd5069becd543d638112f68825b89dTed Kremenek 318598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu unsigned getIndex() const { return Idx; } 319598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 32018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 32118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 32218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 32318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St) { 324bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek return MakeNode(Dst, S, Pred, St, PointKind); 325bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek } 3261eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 32718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeNode(ExplodedNodeSet &Dst, 32818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 32918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 33018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St, 33118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint::Kind K); 3321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 33318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, 33418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const Stmt *S, 33518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred, 33618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *St) { 33770a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek bool Tmp = BuildSinks; 33870a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = true; 3399c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *N = MakeNode(Dst, S, Pred, St); 34070a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek BuildSinks = Tmp; 34170a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek return N; 34270a733e64e2379a654631a14fa29e46761d5f80dTed Kremenek } 343f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 344f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks void importNodesFromBuilder(const NodeBuilder &NB) { 345f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *NBPred = const_cast<ExplodedNode*>(NB.getPred()); 346f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks if (NB.hasGeneratedNodes()) { 347f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks Deferred.erase(NBPred); 348f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks Deferred.insert(NB.Deferred.begin(), NB.Deferred.end()); 349f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks hasGeneratedNode = true; 350f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 351f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks } 352f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 3531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 354f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass BranchNodeBuilder: public CommonNodeBuilder { 3559c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Src; 3569c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *DstT; 3579c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *DstF; 35852a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek 359686775deca8b8685eb90801495880e3abdd844c2Chris Lattner typedef SmallVector<ExplodedNode*,3> DeferredTy; 3603b4f6702860208692f6ef28401e68de4e3ff9af9Ted Kremenek DeferredTy Deferred; 3611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 36271c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek bool GeneratedTrue; 36371c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek bool GeneratedFalse; 364520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleTrue; 365520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool InFeasibleFalse; 3661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3677d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenekpublic: 3689c378f705405d37f49795d5e915989de774fe11fTed Kremenek BranchNodeBuilder(const CFGBlock *src, const CFGBlock *dstT, 3699c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *dstF, ExplodedNode *pred, CoreEngine* e) 370f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks : CommonNodeBuilder(e, pred), Src(src), DstT(dstT), DstF(dstF), 371520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek GeneratedTrue(false), GeneratedFalse(false), 372520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} 3731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 374d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis ~BranchNodeBuilder(); 3751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3769c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return Pred; } 377031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 37838b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const ExplodedGraph& getGraph() const { return *Eng.G; } 379031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 3801e9775d36de8edbc665c0f0bf4dae1400e3d2112Anna Zaks /// This function generates a new ExplodedNode but not a new 3811e9775d36de8edbc665c0f0bf4dae1400e3d2112Anna Zaks /// branch(block edge). 382f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks ExplodedNode *generateNode(const Stmt *Condition, const ProgramState *State, 383f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks const ProgramPointTag *Tag = 0); 3848083414ee7cc8f5c807ed6a4e120fb4e0ab50ff8Ted Kremenek 38518c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramState *State, bool branch); 3861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3879c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getTargetBlock(bool branch) const { 3888e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek return branch ? DstT : DstF; 3891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 3901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 39152a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek void markInfeasible(bool branch) { 392520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek if (branch) 393520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleTrue = GeneratedTrue = true; 394520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek else 395520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek InFeasibleFalse = GeneratedFalse = true; 396520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek } 3971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 398520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek bool isFeasible(bool branch) { 399520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek return branch ? !InFeasibleTrue : !InFeasibleFalse; 40052a16499df87730c0252b431abdf2b2e32d756a6Ted Kremenek } 4011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 40218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { 403b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return getPredecessor()->getState(); 404b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek } 4057d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek}; 406031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 407d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass IndirectGotoNodeBuilder { 408d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 4099c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Src; 4109c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock &DispatchBlock; 4119c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *E; 4129c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 413031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 414754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenekpublic: 4159c378f705405d37f49795d5e915989de774fe11fTed Kremenek IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 4169c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 41703509aea098772644bf4662dc1c88634818ceeccZhongxing Xu : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 418754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 419031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 42003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_iterator I; 4211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 422d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class IndirectGotoNodeBuilder; 42303509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_iterator i) : I(i) {} 424754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek public: 4251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4269c378f705405d37f49795d5e915989de774fe11fTed Kremenek iterator &operator++() { ++I; return *this; } 4279c378f705405d37f49795d5e915989de774fe11fTed Kremenek bool operator!=(const iterator &X) const { return I != X.I; } 4281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 429ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const LabelDecl *getLabel() const { 430ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); 43124f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 4321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 433ad8dcf4a9df0e24051dc31bf9e6f3cd138a34298Chris Lattner const CFGBlock *getBlock() const { 43424f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek return *I; 43524f1a967741ff9f8025ee23be12ba6feacc31f77Ted Kremenek } 436754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek }; 4371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 438031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(DispatchBlock.succ_begin()); } 439031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(DispatchBlock.succ_end()); } 4401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 44118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const iterator &I, 44218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State, 443031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 4441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4459c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *getTarget() const { return E; } 446754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 44718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->State; } 448754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek}; 4491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 450d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass SwitchNodeBuilder { 451d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine& Eng; 4529c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Src; 4539c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *Condition; 4549c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred; 455031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 456daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenekpublic: 4579c378f705405d37f49795d5e915989de774fe11fTed Kremenek SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 4589c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *condition, CoreEngine* eng) 459daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 4601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 461031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu class iterator { 46203509aea098772644bf4662dc1c88634818ceeccZhongxing Xu CFGBlock::const_succ_reverse_iterator I; 4631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 464d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis friend class SwitchNodeBuilder; 46503509aea098772644bf4662dc1c88634818ceeccZhongxing Xu iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 466031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 467daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek public: 4689c378f705405d37f49795d5e915989de774fe11fTed Kremenek iterator &operator++() { ++I; return *this; } 46934feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator!=(const iterator &X) const { return I != X.I; } 47034feff654c6304e0a59ceb1376989d28dbc956ffTed Kremenek bool operator==(const iterator &X) const { return I == X.I; } 4711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4729c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CaseStmt *getCase() const { 473daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return llvm::cast<CaseStmt>((*I)->getLabel()); 474daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 4751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4769c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getBlock() const { 477daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return *I; 478daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 479daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek }; 4801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 481031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator begin() { return iterator(Src->succ_rbegin()+1); } 482031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu iterator end() { return iterator(Src->succ_rend()); } 4831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4844d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek const SwitchStmt *getSwitch() const { 4854d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek return llvm::cast<SwitchStmt>(Src->getTerminator()); 4864d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek } 4874d3175c1e5a44251ea97b0c81e80f060629d9c08Ted Kremenek 48818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateCaseStmtNode(const iterator &I, 48918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *State); 4901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 49118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateDefaultCaseNode(const ProgramState *State, 492031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink = false); 4931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4949c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *getCondition() const { return Condition; } 495daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 49618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->State; } 497daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek}; 49811062b118476368fa5b294954713e5df97d8599fTed Kremenek 49927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilderImpl { 50027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekprotected: 50127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek CoreEngine &engine; 50227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNode *pred; 50327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ProgramPoint pp; 504686775deca8b8685eb90801495880e3abdd844c2Chris Lattner SmallVector<ExplodedNode*, 2> sinksGenerated; 50527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 50618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNodeImpl(const ProgramState *state, 50718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *pred, 50818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ProgramPoint programPoint, 50918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek bool asSink); 51027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 51127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) 512b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} 51327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 51427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 515b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 51627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 51727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek WorkList &getWorkList() { return *engine.WList; } 51827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 5199c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return pred; } 52027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 52127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek BlockCounter getBlockCounter() const { 52227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return engine.WList->getBlockCounter(); 52327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 52427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 525686775deca8b8685eb90801495880e3abdd844c2Chris Lattner const SmallVectorImpl<ExplodedNode*> &sinks() const { 52627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek return sinksGenerated; 52727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 52827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 52927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 530b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenektemplate <typename PP_T> 53127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekclass GenericNodeBuilder : public GenericNodeBuilderImpl { 53227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenekpublic: 533b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) 53427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek : GenericNodeBuilderImpl(eng, pr, p) {} 53527c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 53618c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred, 537ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag, bool asSink) { 538b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), 539b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek asSink); 54027c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 54127c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 542b6a2b08a6b3fbce1a6a4b69d4185165de970696cTed Kremenek const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } 54327c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek}; 54427c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 545f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaksclass EndOfFunctionNodeBuilder : public CommonNodeBuilder { 5469c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock &B; 547ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *Tag; 548f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xu 549f605aae3227ffa3a5dae8eb34fdd79ba0a0d19d1Zhongxing Xupublic: 550b4857264b8d3d861f688cdaa174aab30e0729a73Ted Kremenek bool hasGeneratedNode; 5511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 55211062b118476368fa5b294954713e5df97d8599fTed Kremenekpublic: 5539c378f705405d37f49795d5e915989de774fe11fTed Kremenek EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, 554ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0) 555f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks : CommonNodeBuilder(e, N), B(*b), Tag(tag), hasGeneratedNode(false) {} 5561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 557e36de1fe51c39d9161915dd3dbef880954af6476Ted Kremenek ~EndOfFunctionNodeBuilder(); 5581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 559ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { 560f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); 561f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis } 562f178ac8b68b29e44867777232ba8fee59edc4037Argyrios Kyrtzidis 563d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkList &getWorkList() { return *Eng.WList; } 564598278bee8e5797bc73d24d6ac8a1d6ff6413caeZhongxing Xu 5659c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *getPredecessor() const { return Pred; } 5661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 56711062b118476368fa5b294954713e5df97d8599fTed Kremenek unsigned getCurrentBlockCount() const { 568d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return getBlockCounter().getNumVisited( 569d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 570d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu B.getBlockID()); 5711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 5721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 57318c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *generateNode(const ProgramState *State, 57418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *P = 0, 575ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek const ProgramPointTag *tag = 0); 5761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 57718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void GenerateCallExitNode(const ProgramState *state); 578102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 5799c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *getBlock() const { return &B; } 58011062b118476368fa5b294954713e5df97d8599fTed Kremenek 58118c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { 58211062b118476368fa5b294954713e5df97d8599fTed Kremenek return getPredecessor()->getState(); 58311062b118476368fa5b294954713e5df97d8599fTed Kremenek } 58411062b118476368fa5b294954713e5df97d8599fTed Kremenek}; 585754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 586d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallEnterNodeBuilder { 587d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 588102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 589102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 590102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 59119b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The call site. For implicit automatic object dtor, this is the trigger 59219b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // statement. 593102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *CE; 594102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 59519b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu // The context of the callee. 59619b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *CalleeCtx; 597102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 598102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The parent block of the CallExpr. 599102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *Block; 600102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 601102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // The CFGBlock index of the CallExpr. 602102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index; 603102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 604102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 605d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, 60619b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const Stmt *s, const StackFrameContext *callee, 607102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *blk, unsigned idx) 608c6238d2786cfd961b94580b3d3675a1b3ff0721cZhongxing Xu : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} 609102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 61018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->getState(); } 611102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 612102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const LocationContext *getLocationContext() const { 613102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return Pred->getLocationContext(); 614102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 615102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 616102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *getCallExpr() const { return CE; } 617102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 61819b78d9e3dbbc27bbcbdd8c3017a00fe88849ecdZhongxing Xu const StackFrameContext *getCalleeContext() const { return CalleeCtx; } 619102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 620102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *getBlock() const { return Block; } 621102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 622102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned getIndex() const { return Index; } 623102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 62418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void generateNode(const ProgramState *state); 625102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 626102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 627d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass CallExitNodeBuilder { 628d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CoreEngine &Eng; 629102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *Pred; 630102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 631102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorpublic: 632d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) 633102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor : Eng(eng), Pred(pred) {} 634102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 635102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const ExplodedNode *getPredecessor() const { return Pred; } 636102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 63718c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek const ProgramState *getState() const { return Pred->getState(); } 638102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 63918c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek void generateNode(const ProgramState *state); 640102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor}; 6415a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 6425a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 6435a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 644f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} // end clang namespace 645f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 646f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#endif 647