/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
Line | Count | Source |
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 | 1.36M | : node(N), |
37 | 1.36M | counter(C), |
38 | 1.36M | block(B), |
39 | 1.36M | blockIdx(idx) {} |
40 | | |
41 | | explicit WorkListUnit(ExplodedNode *N, BlockCounter C) |
42 | 482k | : node(N), |
43 | 482k | counter(C), |
44 | 482k | block(nullptr), |
45 | 482k | blockIdx(0) {} |
46 | | |
47 | | /// Returns the node associated with the worklist unit. |
48 | 3.54M | ExplodedNode *getNode() const { return node; } |
49 | | |
50 | | /// Returns the block counter map associated with the worklist unit. |
51 | 1.83M | BlockCounter getBlockCounter() const { return counter; } |
52 | | |
53 | | /// Returns the CFGblock associated with the worklist unit. |
54 | 1.36M | const CFGBlock *getBlock() const { return block; } |
55 | | |
56 | | /// Return the index within the CFGBlock for the worklist unit. |
57 | 1.36M | 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 | 1.36M | void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) { |
69 | 1.36M | enqueue(WorkListUnit(N, CurrentCounter, B, idx)); |
70 | 1.36M | } |
71 | | |
72 | 482k | void enqueue(ExplodedNode *N) { |
73 | 482k | assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); |
74 | 482k | enqueue(WorkListUnit(N, CurrentCounter)); |
75 | 482k | } |
76 | | |
77 | | virtual WorkListUnit dequeue() = 0; |
78 | | |
79 | 2.00M | void setBlockCounter(BlockCounter C) { CurrentCounter = C; } |
80 | 502k | 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 |