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(U: WorkListUnit(N, CurrentCounter, B, idx)); |
70 | } |
71 | |
72 | void enqueue(ExplodedNode *N) { |
73 | assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); |
74 | enqueue(U: 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 | |