Core/PathSensitive/WorkList.h

0001 //==- WorkList.h - Worklist class used by CoreEngine ---------------*- C++ -*-//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file defines WorkList, a pure virtual class that represents an opaque
0010 //  worklist used by CoreEngine to explore the reachability state space.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H
0015 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_WORKLIST_H
0016
0017 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
0018 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
0019 #include <cassert>
0020
0021 namespace clang {
0022
0023 class CFGBlock;
0024
0025 namespace ento {
0026
0027 class WorkListUnit {
0028   ExplodedNode *node;
0029   BlockCounter counter;
0030   const CFGBlock *block;
0031   unsigned blockIdx; // This is the index of the next statement.
0032
0033 public:
0034   WorkListUnit(ExplodedNode *N, BlockCounter C,
0035                const CFGBlock *B, unsigned idx)
0036   : node(N),
0037     counter(C),
0038     block(B),
0039     blockIdx(idx) {}
0040
0041   explicit WorkListUnit(ExplodedNode *N, BlockCounter C)
0042   : node(N),
0043     counter(C),
0044     block(nullptr),
0045     blockIdx(0) {}
0046
0047   /// Returns the node associated with the worklist unit.
0048   ExplodedNode *getNode() const { return node; }
0049
0050   /// Returns the block counter map associated with the worklist unit.
0051   BlockCounter getBlockCounter() const { return counter; }
0052
0053   /// Returns the CFGblock associated with the worklist unit.
0054   const CFGBlock *getBlock() const { return block; }
0055
0056   /// Return the index within the CFGBlock for the worklist unit.
0057   unsigned getIndex() const { return blockIdx; }
0058 };
0059
0060 class WorkList {
0061   BlockCounter CurrentCounter;
0062 public:
0063   virtual ~WorkList();
0064   virtual bool hasWork() const = 0;
0065
0066   virtual void enqueue(const WorkListUnit& U) = 0;
0067
0068   void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) {
0069     enqueue(WorkListUnit(N, CurrentCounter, B, idx));
0070   }
0071
0072   void enqueue(ExplodedNode *N) {
0073     assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind);
0074     enqueue(WorkListUnit(N, CurrentCounter));
0075   }
0076
0077   virtual WorkListUnit dequeue() = 0;
0078
0079   void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
0080   BlockCounter getBlockCounter() const { return CurrentCounter; }
0081
0082   static std::unique_ptr<WorkList> makeDFS();
0083   static std::unique_ptr<WorkList> makeBFS();
0084   static std::unique_ptr<WorkList> makeBFSBlockDFSContents();
0085   static std::unique_ptr<WorkList> makeUnexploredFirst();
0086   static std::unique_ptr<WorkList> makeUnexploredFirstPriorityQueue();
0087   static std::unique_ptr<WorkList> makeUnexploredFirstPriorityLocationQueue();
0088 };
0089
0090 } // end ento namespace
0091
0092 } // end clang namespace
0093
0094 #endif