WorkList.h revision 218887 
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 <cstddef>
20
21namespace clang {
22
23class CFGBlock;
24
25namespace ento {
26
27class ExplodedNode;
28class ExplodedNodeImpl;
29
30class WorkListUnit {
31  ExplodedNode* node;
32  BlockCounter counter;
33  const CFGBlock* block;
34  unsigned blockIdx; // This is the index of the next statement.
35
36public:
37  WorkListUnit(ExplodedNode* N, BlockCounter C,
38               const CFGBlock* B, unsigned idx)
39  : node(N),
40    counter(C),
41    block(B),
42    blockIdx(idx) {}
43
44  explicit WorkListUnit(ExplodedNode* N, BlockCounter C)
45  : node(N),
46    counter(C),
47    block(NULL),
48    blockIdx(0) {}
49
50  /// Returns the node associated with the worklist unit.
51  ExplodedNode *getNode() const { return node; }
52
53  /// Returns the block counter map associated with the worklist unit.
54  BlockCounter getBlockCounter() const { return counter; }
55
56  /// Returns the CFGblock associated with the worklist unit.
57  const CFGBlock *getBlock() const { return block; }
58
59  /// Return the index within the CFGBlock for the worklist unit.
60  unsigned getIndex() const { return blockIdx; }
61};
62
63class WorkList {
64  BlockCounter CurrentCounter;
65public:
66  virtual ~WorkList();
67  virtual bool hasWork() const = 0;
68
69  virtual void enqueue(const WorkListUnit& U) = 0;
70
71  void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) {
72    enqueue(WorkListUnit(N, CurrentCounter, B, idx));
73  }
74
75  void enqueue(ExplodedNode *N) {
76    enqueue(WorkListUnit(N, CurrentCounter));
77  }
78
79  virtual WorkListUnit dequeue() = 0;
80
81  void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
82  BlockCounter getBlockCounter() const { return CurrentCounter; }
83
84  class Visitor {
85  public:
86    Visitor() {}
87    virtual ~Visitor();
88    virtual bool visit(const WorkListUnit &U) = 0;
89  };
90  virtual bool visitItemsInWorkList(Visitor &V) = 0;
91
92  static WorkList *makeDFS();
93  static WorkList *makeBFS();
94  static WorkList *makeBFSBlockDFSContents();
95};
96
97} // end GR namespace
98
99} // end clang namespace
100
101#endif
102