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_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:
  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
  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) {
  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   static std::unique_ptr<WorkList> makeDFS();
  84   static std::unique_ptr<WorkList> makeBFS();
  85   static std::unique_ptr<WorkList> makeBFSBlockDFSContents();
  86   static std::unique_ptr<WorkList> makeUnexploredFirst();
  87   static std::unique_ptr<WorkList> makeUnexploredFirstPriorityQueue();
  88   static std::unique_ptr<WorkList> makeUnexploredFirstPriorityLocationQueue();
  89 };
  90
  91 } // end ento namespace
  92
  93 } // end clang namespace
  94
  95 #endif