1218887Sdim//==- WorkList.h - Worklist class used by CoreEngine ---------------*- C++ -*-// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines WorkList, a pure virtual class that represents an opaque 11218887Sdim// worklist used by CoreEngine to explore the reachability state space. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#ifndef LLVM_CLANG_GR_WORKLIST 16218887Sdim#define LLVM_CLANG_GR_WORKLIST 17218887Sdim 18218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 19249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 20249423Sdim#include <cassert> 21218887Sdim 22218887Sdimnamespace clang { 23218887Sdim 24218887Sdimclass CFGBlock; 25218887Sdim 26218887Sdimnamespace ento { 27218887Sdim 28218887Sdimclass WorkListUnit { 29226633Sdim ExplodedNode *node; 30218887Sdim BlockCounter counter; 31226633Sdim const CFGBlock *block; 32218887Sdim unsigned blockIdx; // This is the index of the next statement. 33218887Sdim 34218887Sdimpublic: 35226633Sdim WorkListUnit(ExplodedNode *N, BlockCounter C, 36226633Sdim const CFGBlock *B, unsigned idx) 37218887Sdim : node(N), 38218887Sdim counter(C), 39218887Sdim block(B), 40218887Sdim blockIdx(idx) {} 41218887Sdim 42226633Sdim explicit WorkListUnit(ExplodedNode *N, BlockCounter C) 43218887Sdim : node(N), 44218887Sdim counter(C), 45218887Sdim block(NULL), 46218887Sdim blockIdx(0) {} 47218887Sdim 48218887Sdim /// Returns the node associated with the worklist unit. 49218887Sdim ExplodedNode *getNode() const { return node; } 50218887Sdim 51218887Sdim /// Returns the block counter map associated with the worklist unit. 52218887Sdim BlockCounter getBlockCounter() const { return counter; } 53218887Sdim 54218887Sdim /// Returns the CFGblock associated with the worklist unit. 55218887Sdim const CFGBlock *getBlock() const { return block; } 56218887Sdim 57218887Sdim /// Return the index within the CFGBlock for the worklist unit. 58218887Sdim unsigned getIndex() const { return blockIdx; } 59218887Sdim}; 60218887Sdim 61218887Sdimclass WorkList { 62218887Sdim BlockCounter CurrentCounter; 63218887Sdimpublic: 64218887Sdim virtual ~WorkList(); 65218887Sdim virtual bool hasWork() const = 0; 66218887Sdim 67218887Sdim virtual void enqueue(const WorkListUnit& U) = 0; 68218887Sdim 69218887Sdim void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) { 70218887Sdim enqueue(WorkListUnit(N, CurrentCounter, B, idx)); 71218887Sdim } 72218887Sdim 73218887Sdim void enqueue(ExplodedNode *N) { 74234353Sdim assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); 75218887Sdim enqueue(WorkListUnit(N, CurrentCounter)); 76218887Sdim } 77218887Sdim 78218887Sdim virtual WorkListUnit dequeue() = 0; 79218887Sdim 80218887Sdim void setBlockCounter(BlockCounter C) { CurrentCounter = C; } 81218887Sdim BlockCounter getBlockCounter() const { return CurrentCounter; } 82218887Sdim 83218887Sdim class Visitor { 84218887Sdim public: 85218887Sdim Visitor() {} 86218887Sdim virtual ~Visitor(); 87218887Sdim virtual bool visit(const WorkListUnit &U) = 0; 88218887Sdim }; 89218887Sdim virtual bool visitItemsInWorkList(Visitor &V) = 0; 90218887Sdim 91218887Sdim static WorkList *makeDFS(); 92218887Sdim static WorkList *makeBFS(); 93218887Sdim static WorkList *makeBFSBlockDFSContents(); 94218887Sdim}; 95218887Sdim 96218887Sdim} // end GR namespace 97218887Sdim 98218887Sdim} // end clang namespace 99218887Sdim 100218887Sdim#endif 101