1 //==- WorkList.h - Worklist class used by CoreEngine ---------------*- C++ -*-//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines WorkList, a pure virtual class that represents an opaque
10 // worklist used by CoreEngine to explore the reachability state space.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H
15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H
17 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
30 const CFGBlock *block;
31 unsigned blockIdx; // This is the index of the next statement.
34 WorkListUnit(ExplodedNode *N, BlockCounter C,
35 const CFGBlock *B, unsigned idx)
41 explicit WorkListUnit(ExplodedNode *N, BlockCounter C)
47 /// Returns the node associated with the worklist unit.
48 ExplodedNode *getNode() const { return node; }
50 /// Returns the block counter map associated with the worklist unit.
51 BlockCounter getBlockCounter() const { return counter; }
53 /// Returns the CFGblock associated with the worklist unit.
54 const CFGBlock *getBlock() const { return block; }
56 /// Return the index within the CFGBlock for the worklist unit.
57 unsigned getIndex() const { return blockIdx; }
61 BlockCounter CurrentCounter;
64 virtual bool hasWork() const = 0;
66 virtual void enqueue(const WorkListUnit& U) = 0;
68 void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) {
69 enqueue(WorkListUnit(N, CurrentCounter, B, idx));
72 void enqueue(ExplodedNode *N) {
73 assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind);
74 enqueue(WorkListUnit(N, CurrentCounter));
77 virtual WorkListUnit dequeue() = 0;
79 void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
80 BlockCounter getBlockCounter() const { return CurrentCounter; }
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();
90 } // end ento namespace
92 } // end clang namespace