WorkList.h revision 355940
11590Srgrimes//==- WorkList.h - Worklist class used by CoreEngine ---------------*- C++ -*-// 21590Srgrimes// 31590Srgrimes// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 496196Sdes// See https://llvm.org/LICENSE.txt for license information. 596196Sdes// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 61590Srgrimes// 796196Sdes//===----------------------------------------------------------------------===// 896196Sdes// 996196Sdes// This file defines WorkList, a pure virtual class that represents an opaque 1096196Sdes// worklist used by CoreEngine to explore the reachability state space. 1196196Sdes// 121590Srgrimes//===----------------------------------------------------------------------===// 131590Srgrimes 141590Srgrimes#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H 151590Srgrimes#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H 161590Srgrimes 171590Srgrimes#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 181590Srgrimes#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 191590Srgrimes#include <cassert> 201590Srgrimes 211590Srgrimesnamespace clang { 221590Srgrimes 231590Srgrimesclass CFGBlock; 241590Srgrimes 251590Srgrimesnamespace ento { 261590Srgrimes 271590Srgrimesclass WorkListUnit { 281590Srgrimes ExplodedNode *node; 291590Srgrimes BlockCounter counter; 301590Srgrimes const CFGBlock *block; 311590Srgrimes unsigned blockIdx; // This is the index of the next statement. 321590Srgrimes 331590Srgrimespublic: 341590Srgrimes WorkListUnit(ExplodedNode *N, BlockCounter C, 351590Srgrimes const CFGBlock *B, unsigned idx) 361590Srgrimes : node(N), 371590Srgrimes counter(C), 381590Srgrimes block(B), 391590Srgrimes blockIdx(idx) {} 401590Srgrimes 411590Srgrimes explicit WorkListUnit(ExplodedNode *N, BlockCounter C) 4227919Scharnier : node(N), 431590Srgrimes counter(C), 441590Srgrimes block(nullptr), 451590Srgrimes blockIdx(0) {} 461590Srgrimes 47105235Scharnier /// Returns the node associated with the worklist unit. 481590Srgrimes ExplodedNode *getNode() const { return node; } 4929922Smarkm 501590Srgrimes /// Returns the block counter map associated with the worklist unit. 51105235Scharnier BlockCounter getBlockCounter() const { return counter; } 521590Srgrimes 53105235Scharnier /// Returns the CFGblock associated with the worklist unit. 54105235Scharnier const CFGBlock *getBlock() const { return block; } 55105235Scharnier 561590Srgrimes /// Return the index within the CFGBlock for the worklist unit. 571590Srgrimes unsigned getIndex() const { return blockIdx; } 581590Srgrimes}; 5995621Smarkm 601590Srgrimesclass WorkList { 61120547Stjr BlockCounter CurrentCounter; 621590Srgrimespublic: 631590Srgrimes virtual ~WorkList(); 641590Srgrimes virtual bool hasWork() const = 0; 651590Srgrimes 661590Srgrimes virtual void enqueue(const WorkListUnit& U) = 0; 671590Srgrimes 681590Srgrimes void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) { 691590Srgrimes enqueue(WorkListUnit(N, CurrentCounter, B, idx)); 708232Sdg } 711590Srgrimes 7227919Scharnier void enqueue(ExplodedNode *N) { 731590Srgrimes assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); 741590Srgrimes enqueue(WorkListUnit(N, CurrentCounter)); 751590Srgrimes } 76200462Sdelphij 771590Srgrimes virtual WorkListUnit dequeue() = 0; 781590Srgrimes 79120547Stjr void setBlockCounter(BlockCounter C) { CurrentCounter = C; } 801590Srgrimes BlockCounter getBlockCounter() const { return CurrentCounter; } 811590Srgrimes 821590Srgrimes static std::unique_ptr<WorkList> makeDFS(); 831590Srgrimes static std::unique_ptr<WorkList> makeBFS(); 841590Srgrimes static std::unique_ptr<WorkList> makeBFSBlockDFSContents(); 851590Srgrimes static std::unique_ptr<WorkList> makeUnexploredFirst(); 861590Srgrimes static std::unique_ptr<WorkList> makeUnexploredFirstPriorityQueue(); 871590Srgrimes static std::unique_ptr<WorkList> makeUnexploredFirstPriorityLocationQueue(); 881590Srgrimes}; 891590Srgrimes 901590Srgrimes} // end ento namespace 911590Srgrimes 921590Srgrimes} // end clang namespace 931590Srgrimes 941590Srgrimes#endif 95120547Stjr