1//==- WorkList.h - Worklist class used by CoreEngine ---------------*- C++ -*-//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines WorkList, a pure virtual class that represents an opaque
11//  worklist used by CoreEngine to explore the reachability state space.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_GR_WORKLIST
16#define LLVM_CLANG_GR_WORKLIST
17
18#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
20#include <cassert>
21
22namespace clang {
23
24class CFGBlock;
25
26namespace ento {
27
28class WorkListUnit {
29  ExplodedNode *node;
30  BlockCounter counter;
31  const CFGBlock *block;
32  unsigned blockIdx; // This is the index of the next statement.
33
34public:
35  WorkListUnit(ExplodedNode *N, BlockCounter C,
36               const CFGBlock *B, unsigned idx)
37  : node(N),
38    counter(C),
39    block(B),
40    blockIdx(idx) {}
41
42  explicit WorkListUnit(ExplodedNode *N, BlockCounter C)
43  : node(N),
44    counter(C),
45    block(nullptr),
46    blockIdx(0) {}
47
48  /// Returns the node associated with the worklist unit.
49  ExplodedNode *getNode() const { return node; }
50
51  /// Returns the block counter map associated with the worklist unit.
52  BlockCounter getBlockCounter() const { return counter; }
53
54  /// Returns the CFGblock associated with the worklist unit.
55  const CFGBlock *getBlock() const { return block; }
56
57  /// Return the index within the CFGBlock for the worklist unit.
58  unsigned getIndex() const { return blockIdx; }
59};
60
61class WorkList {
62  BlockCounter CurrentCounter;
63public:
64  virtual ~WorkList();
65  virtual bool hasWork() const = 0;
66
67  virtual void enqueue(const WorkListUnit& U) = 0;
68
69  void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) {
70    enqueue(WorkListUnit(N, CurrentCounter, B, idx));
71  }
72
73  void enqueue(ExplodedNode *N) {
74    assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind);
75    enqueue(WorkListUnit(N, CurrentCounter));
76  }
77
78  virtual WorkListUnit dequeue() = 0;
79
80  void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
81  BlockCounter getBlockCounter() const { return CurrentCounter; }
82
83  class Visitor {
84  public:
85    Visitor() {}
86    virtual ~Visitor();
87    virtual bool visit(const WorkListUnit &U) = 0;
88  };
89  virtual bool visitItemsInWorkList(Visitor &V) = 0;
90
91  static WorkList *makeDFS();
92  static WorkList *makeBFS();
93  static WorkList *makeBFSBlockDFSContents();
94};
95
96} // end GR namespace
97
98} // end clang namespace
99
100#endif
101