contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h

   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
  21 namespace clang {
  22
  23 class CFGBlock;
  24
  25 namespace ento {
  26
  27 class ExplodedNode;
  28 class ExplodedNodeImpl;
  29
  30 class WorkListUnit {
  31   ExplodedNode *node;
  32   BlockCounter counter;
  33   const CFGBlock *block;
  34   unsigned blockIdx; // This is the index of the next statement.
  35
  36 public:
  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
  63 class WorkList {
  64   BlockCounter CurrentCounter;
  65 public:
  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     assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind);
  77     enqueue(WorkListUnit(N, CurrentCounter));
  78   }
  79
  80   virtual WorkListUnit dequeue() = 0;
  81
  82   void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
  83   BlockCounter getBlockCounter() const { return CurrentCounter; }
  84
  85   class Visitor {
  86   public:
  87     Visitor() {}
  88     virtual ~Visitor();
  89     virtual bool visit(const WorkListUnit &U) = 0;
  90   };
  91   virtual bool visitItemsInWorkList(Visitor &V) = 0;
  92
  93   static WorkList *makeDFS();
  94   static WorkList *makeBFS();
  95   static WorkList *makeBFSBlockDFSContents();
  96 };
  97
  98 } // end GR namespace
  99
 100 } // end clang namespace
 101
 102 #endif