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