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_GR_WORKLIST 16 #define LLVM_CLANG_GR_WORKLIST 17 18 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 19 #include <cstddef> 20 21 namespace clang { 22 23 class CFGBlock; 24 25 namespace ento { 26 27 class ExplodedNode; 28 class ExplodedNodeImpl; 29 30 class WorkListUnit { 31 ExplodedNode* node; 32 BlockCounter counter; 33 const CFGBlock* block; 34 unsigned blockIdx; // This is the index of the next statement. 35 36 public: WorkListUnit(ExplodedNode * N,BlockCounter C,const CFGBlock * B,unsigned idx)37 WorkListUnit(ExplodedNode* N, BlockCounter C, 38 const CFGBlock* B, unsigned idx) 39 : node(N), 40 counter(C), 41 block(B), 42 blockIdx(idx) {} 43 WorkListUnit(ExplodedNode * N,BlockCounter C)44 explicit WorkListUnit(ExplodedNode* N, BlockCounter C) 45 : node(N), 46 counter(C), 47 block(NULL), 48 blockIdx(0) {} 49 50 /// Returns the node associated with the worklist unit. getNode()51 ExplodedNode *getNode() const { return node; } 52 53 /// Returns the block counter map associated with the worklist unit. getBlockCounter()54 BlockCounter getBlockCounter() const { return counter; } 55 56 /// Returns the CFGblock associated with the worklist unit. getBlock()57 const CFGBlock *getBlock() const { return block; } 58 59 /// Return the index within the CFGBlock for the worklist unit. getIndex()60 unsigned getIndex() const { return blockIdx; } 61 }; 62 63 class WorkList { 64 BlockCounter CurrentCounter; 65 public: 66 virtual ~WorkList(); 67 virtual bool hasWork() const = 0; 68 69 virtual void enqueue(const WorkListUnit& U) = 0; 70 enqueue(ExplodedNode * N,const CFGBlock * B,unsigned idx)71 void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) { 72 enqueue(WorkListUnit(N, CurrentCounter, B, idx)); 73 } 74 enqueue(ExplodedNode * N)75 void enqueue(ExplodedNode *N) { 76 enqueue(WorkListUnit(N, CurrentCounter)); 77 } 78 79 virtual WorkListUnit dequeue() = 0; 80 setBlockCounter(BlockCounter C)81 void setBlockCounter(BlockCounter C) { CurrentCounter = C; } getBlockCounter()82 BlockCounter getBlockCounter() const { return CurrentCounter; } 83 84 class Visitor { 85 public: Visitor()86 Visitor() {} 87 virtual ~Visitor(); 88 virtual bool visit(const WorkListUnit &U) = 0; 89 }; 90 virtual bool visitItemsInWorkList(Visitor &V) = 0; 91 92 static WorkList *makeDFS(); 93 static WorkList *makeBFS(); 94 static WorkList *makeBFSBlockDFSContents(); 95 }; 96 97 } // end GR namespace 98 99 } // end clang namespace 100 101 #endif 102