Home | History | Annotate | Download | only in PathSensitive 
      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 "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   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
    101