1218887Sdim//==- WorkList.h - Worklist class used by CoreEngine ---------------*- C++ -*-// 2218887Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6218887Sdim// 7218887Sdim//===----------------------------------------------------------------------===// 8218887Sdim// 9218887Sdim// This file defines WorkList, a pure virtual class that represents an opaque 10218887Sdim// worklist used by CoreEngine to explore the reachability state space. 11218887Sdim// 12218887Sdim//===----------------------------------------------------------------------===// 13218887Sdim 14280031Sdim#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H 15280031Sdim#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H 16218887Sdim 17218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 18249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 19249423Sdim#include <cassert> 20218887Sdim 21218887Sdimnamespace clang { 22341825Sdim 23218887Sdimclass CFGBlock; 24218887Sdim 25218887Sdimnamespace ento { 26218887Sdim 27218887Sdimclass WorkListUnit { 28226633Sdim ExplodedNode *node; 29218887Sdim BlockCounter counter; 30226633Sdim const CFGBlock *block; 31218887Sdim unsigned blockIdx; // This is the index of the next statement. 32218887Sdim 33218887Sdimpublic: 34226633Sdim WorkListUnit(ExplodedNode *N, BlockCounter C, 35226633Sdim const CFGBlock *B, unsigned idx) 36218887Sdim : node(N), 37218887Sdim counter(C), 38218887Sdim block(B), 39218887Sdim blockIdx(idx) {} 40218887Sdim 41226633Sdim explicit WorkListUnit(ExplodedNode *N, BlockCounter C) 42218887Sdim : node(N), 43218887Sdim counter(C), 44276479Sdim block(nullptr), 45218887Sdim blockIdx(0) {} 46218887Sdim 47218887Sdim /// Returns the node associated with the worklist unit. 48218887Sdim ExplodedNode *getNode() const { return node; } 49341825Sdim 50218887Sdim /// Returns the block counter map associated with the worklist unit. 51218887Sdim BlockCounter getBlockCounter() const { return counter; } 52218887Sdim 53218887Sdim /// Returns the CFGblock associated with the worklist unit. 54218887Sdim const CFGBlock *getBlock() const { return block; } 55341825Sdim 56218887Sdim /// Return the index within the CFGBlock for the worklist unit. 57218887Sdim unsigned getIndex() const { return blockIdx; } 58218887Sdim}; 59218887Sdim 60218887Sdimclass WorkList { 61218887Sdim BlockCounter CurrentCounter; 62218887Sdimpublic: 63218887Sdim virtual ~WorkList(); 64218887Sdim virtual bool hasWork() const = 0; 65218887Sdim 66218887Sdim virtual void enqueue(const WorkListUnit& U) = 0; 67218887Sdim 68218887Sdim void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) { 69218887Sdim enqueue(WorkListUnit(N, CurrentCounter, B, idx)); 70218887Sdim } 71218887Sdim 72218887Sdim void enqueue(ExplodedNode *N) { 73234353Sdim assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); 74218887Sdim enqueue(WorkListUnit(N, CurrentCounter)); 75218887Sdim } 76218887Sdim 77218887Sdim virtual WorkListUnit dequeue() = 0; 78218887Sdim 79218887Sdim void setBlockCounter(BlockCounter C) { CurrentCounter = C; } 80218887Sdim BlockCounter getBlockCounter() const { return CurrentCounter; } 81218887Sdim 82341825Sdim static std::unique_ptr<WorkList> makeDFS(); 83341825Sdim static std::unique_ptr<WorkList> makeBFS(); 84341825Sdim static std::unique_ptr<WorkList> makeBFSBlockDFSContents(); 85341825Sdim static std::unique_ptr<WorkList> makeUnexploredFirst(); 86341825Sdim static std::unique_ptr<WorkList> makeUnexploredFirstPriorityQueue(); 87344779Sdim static std::unique_ptr<WorkList> makeUnexploredFirstPriorityLocationQueue(); 88218887Sdim}; 89218887Sdim 90341825Sdim} // end ento namespace 91218887Sdim 92218887Sdim} // end clang namespace 93218887Sdim 94218887Sdim#endif 95