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 assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); 77 enqueue(WorkListUnit(N, CurrentCounter)); 78 } 79 80 virtual WorkListUnit dequeue() = 0; 81 setBlockCounter(BlockCounter C)82 void setBlockCounter(BlockCounter C) { CurrentCounter = C; } getBlockCounter()83 BlockCounter getBlockCounter() const { return CurrentCounter; } 84 85 class Visitor { 86 public: Visitor()87 Visitor() {} 88 virtual ~Visitor(); 89 virtual bool visit(const WorkListUnit &U) = 0; 90 }; 91 virtual bool visitItemsInWorkList(Visitor &V) = 0; 92 93 static WorkList *makeDFS(); 94 static WorkList *makeBFS(); 95 static WorkList *makeBFSBlockDFSContents(); 96 }; 97 98 } // end GR namespace 99 100 } // end clang namespace 101 102 #endif 103