1 //==- WorkList.h - Worklist class used by CoreEngine ---------------*- C++ -*-// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines WorkList, a pure virtual class that represents an opaque 11 // worklist used by CoreEngine to explore the reachability state space. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H 16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H 17 18 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 19 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 20 #include <cassert> 21 22 namespace clang { 23 24 class CFGBlock; 25 26 namespace ento { 27 28 class WorkListUnit { 29 ExplodedNode *node; 30 BlockCounter counter; 31 const CFGBlock *block; 32 unsigned blockIdx; // This is the index of the next statement. 33 34 public: WorkListUnit(ExplodedNode * N,BlockCounter C,const CFGBlock * B,unsigned idx)35 WorkListUnit(ExplodedNode *N, BlockCounter C, 36 const CFGBlock *B, unsigned idx) 37 : node(N), 38 counter(C), 39 block(B), 40 blockIdx(idx) {} 41 WorkListUnit(ExplodedNode * N,BlockCounter C)42 explicit WorkListUnit(ExplodedNode *N, BlockCounter C) 43 : node(N), 44 counter(C), 45 block(nullptr), 46 blockIdx(0) {} 47 48 /// Returns the node associated with the worklist unit. getNode()49 ExplodedNode *getNode() const { return node; } 50 51 /// Returns the block counter map associated with the worklist unit. getBlockCounter()52 BlockCounter getBlockCounter() const { return counter; } 53 54 /// Returns the CFGblock associated with the worklist unit. getBlock()55 const CFGBlock *getBlock() const { return block; } 56 57 /// Return the index within the CFGBlock for the worklist unit. getIndex()58 unsigned getIndex() const { return blockIdx; } 59 }; 60 61 class WorkList { 62 BlockCounter CurrentCounter; 63 public: 64 virtual ~WorkList(); 65 virtual bool hasWork() const = 0; 66 67 virtual void enqueue(const WorkListUnit& U) = 0; 68 enqueue(ExplodedNode * N,const CFGBlock * B,unsigned idx)69 void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) { 70 enqueue(WorkListUnit(N, CurrentCounter, B, idx)); 71 } 72 enqueue(ExplodedNode * N)73 void enqueue(ExplodedNode *N) { 74 assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); 75 enqueue(WorkListUnit(N, CurrentCounter)); 76 } 77 78 virtual WorkListUnit dequeue() = 0; 79 setBlockCounter(BlockCounter C)80 void setBlockCounter(BlockCounter C) { CurrentCounter = C; } getBlockCounter()81 BlockCounter getBlockCounter() const { return CurrentCounter; } 82 83 class Visitor { 84 public: Visitor()85 Visitor() {} 86 virtual ~Visitor(); 87 virtual bool visit(const WorkListUnit &U) = 0; 88 }; 89 virtual bool visitItemsInWorkList(Visitor &V) = 0; 90 91 static WorkList *makeDFS(); 92 static WorkList *makeBFS(); 93 static WorkList *makeBFSBlockDFSContents(); 94 }; 95 96 } // end GR namespace 97 98 } // end clang namespace 99 100 #endif 101