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
21namespace clang {
22
23class CFGBlock;
24
25namespace ento {
26
27class WorkListUnit {
28  ExplodedNode *node;
29  BlockCounter counter;
30  const CFGBlock *block;
31  unsigned blockIdx; // This is the index of the next statement.
32
33public:
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
60class WorkList {
61  BlockCounter CurrentCounter;
62public:
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