clang  6.0.0svn
WorkList.h
Go to the documentation of this file.
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_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H
16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H
17 
20 #include <cassert>
21 
22 namespace clang {
23 
24 class CFGBlock;
25 
26 namespace ento {
27 
28 class WorkListUnit {
29  ExplodedNode *node;
30  BlockCounter counter;
31  const CFGBlock *block;
32  unsigned blockIdx; // This is the index of the next statement.
33 
34 public:
36  const CFGBlock *B, unsigned idx)
37  : node(N),
38  counter(C),
39  block(B),
40  blockIdx(idx) {}
41 
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 
61 class WorkList {
62  BlockCounter CurrentCounter;
63 public:
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) {
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
void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx)
Definition: WorkList.h:69
An abstract data type used to count the number of times a given block has been visited along a path a...
Definition: BlockCounter.h:30
void setBlockCounter(BlockCounter C)
Definition: WorkList.h:80
BlockCounter getBlockCounter() const
Returns the block counter map associated with the worklist unit.
Definition: WorkList.h:52
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:401
unsigned getIndex() const
Return the index within the CFGBlock for the worklist unit.
Definition: WorkList.h:58
Kind getKind() const
Definition: ProgramPoint.h:160
WorkListUnit(ExplodedNode *N, BlockCounter C, const CFGBlock *B, unsigned idx)
Definition: WorkList.h:35
ExplodedNode * getNode() const
Returns the node associated with the worklist unit.
Definition: WorkList.h:49
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:55
WorkListUnit(ExplodedNode *N, BlockCounter C)
Definition: WorkList.h:42
BlockCounter getBlockCounter() const
Definition: WorkList.h:81
void enqueue(ExplodedNode *N)
Definition: WorkList.h:73