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 
18 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
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:
WorkListUnit(ExplodedNode * N,BlockCounter C,const CFGBlock * B,unsigned idx)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 
WorkListUnit(ExplodedNode * N,BlockCounter C)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.
getNode()49   ExplodedNode *getNode() const { return node; }
50 
51   /// Returns the block counter map associated with the worklist unit.
getBlockCounter()52   BlockCounter getBlockCounter() const { return counter; }
53 
54   /// Returns the CFGblock associated with the worklist unit.
getBlock()55   const CFGBlock *getBlock() const { return block; }
56 
57   /// Return the index within the CFGBlock for the worklist unit.
getIndex()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 
enqueue(ExplodedNode * N,const CFGBlock * B,unsigned idx)69   void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) {
70     enqueue(WorkListUnit(N, CurrentCounter, B, idx));
71   }
72 
enqueue(ExplodedNode * N)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 
setBlockCounter(BlockCounter C)80   void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
getBlockCounter()81   BlockCounter getBlockCounter() const { return CurrentCounter; }
82 
83   class Visitor {
84   public:
Visitor()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