clang  9.0.0svn
WorkList.h
Go to the documentation of this file.
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 
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:
35  const CFGBlock *B, unsigned idx)
36  : node(N),
37  counter(C),
38  block(B),
39  blockIdx(idx) {}
40 
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) {
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
void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx)
Definition: WorkList.h:68
An abstract data type used to count the number of times a given block has been visited along a path a...
Definition: BlockCounter.h:29
void setBlockCounter(BlockCounter C)
Definition: WorkList.h:79
BlockCounter getBlockCounter() const
Returns the block counter map associated with the worklist unit.
Definition: WorkList.h:51
Represents a single basic block in a source-level CFG.
Definition: CFG.h:570
unsigned getIndex() const
Return the index within the CFGBlock for the worklist unit.
Definition: WorkList.h:57
Kind getKind() const
Definition: ProgramPoint.h:160
WorkListUnit(ExplodedNode *N, BlockCounter C, const CFGBlock *B, unsigned idx)
Definition: WorkList.h:34
ExplodedNode * getNode() const
Returns the node associated with the worklist unit.
Definition: WorkList.h:48
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
Dataflow Directional Tag Classes.
const CFGBlock * getBlock() const
Returns the CFGblock associated with the worklist unit.
Definition: WorkList.h:54
WorkListUnit(ExplodedNode *N, BlockCounter C)
Definition: WorkList.h:41
BlockCounter getBlockCounter() const
Definition: WorkList.h:80
void enqueue(ExplodedNode *N)
Definition: WorkList.h:72