1d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis//==- WorkList.h - Worklist class used by CoreEngine ---------------*- C++ -*-//
21eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump//
3f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//                     The LLVM Compiler Infrastructure
4f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//
5f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// This file is distributed under the University of Illinois Open Source
6f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// License. See LICENSE.TXT for details.
7f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//
8f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//===----------------------------------------------------------------------===//
9f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//
10d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis//  This file defines WorkList, a pure virtual class that represents an opaque
11d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis//  worklist used by CoreEngine to explore the reachability state space.
12f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//
13f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//===----------------------------------------------------------------------===//
14f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
15d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis#ifndef LLVM_CLANG_GR_WORKLIST
16d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis#define LLVM_CLANG_GR_WORKLIST
17f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
189b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
19539e9b18e64479e1092e0cd52efdb2ad41b4d07dDouglas Gregor#include <cstddef>
208e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek
211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpnamespace clang {
22539e9b18e64479e1092e0cd52efdb2ad41b4d07dDouglas Gregor
23539e9b18e64479e1092e0cd52efdb2ad41b4d07dDouglas Gregorclass CFGBlock;
245a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
259ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento {
265a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
27539e9b18e64479e1092e0cd52efdb2ad41b4d07dDouglas Gregorclass ExplodedNode;
28f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekclass ExplodedNodeImpl;
291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
30d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass WorkListUnit {
319c378f705405d37f49795d5e915989de774fe11fTed Kremenek  ExplodedNode *node;
3255825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  BlockCounter counter;
339c378f705405d37f49795d5e915989de774fe11fTed Kremenek  const CFGBlock *block;
3455825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  unsigned blockIdx; // This is the index of the next statement.
351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
36f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic:
379c378f705405d37f49795d5e915989de774fe11fTed Kremenek  WorkListUnit(ExplodedNode *N, BlockCounter C,
389c378f705405d37f49795d5e915989de774fe11fTed Kremenek               const CFGBlock *B, unsigned idx)
3955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  : node(N),
4055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    counter(C),
4155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    block(B),
4255825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    blockIdx(idx) {}
431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
449c378f705405d37f49795d5e915989de774fe11fTed Kremenek  explicit WorkListUnit(ExplodedNode *N, BlockCounter C)
4555825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  : node(N),
4655825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    counter(C),
4755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    block(NULL),
4855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    blockIdx(0) {}
4955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek
5055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  /// Returns the node associated with the worklist unit.
5155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  ExplodedNode *getNode() const { return node; }
5255825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek
5355825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  /// Returns the block counter map associated with the worklist unit.
5455825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  BlockCounter getBlockCounter() const { return counter; }
5555825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek
5655825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  /// Returns the CFGblock associated with the worklist unit.
5755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  const CFGBlock *getBlock() const { return block; }
5855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek
5955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  /// Return the index within the CFGBlock for the worklist unit.
6055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  unsigned getIndex() const { return blockIdx; }
61f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek};
62f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
63d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass WorkList {
64d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  BlockCounter CurrentCounter;
65f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic:
66d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  virtual ~WorkList();
67f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  virtual bool hasWork() const = 0;
681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
6955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  virtual void enqueue(const WorkListUnit& U) = 0;
70f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek
7155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) {
7255825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    enqueue(WorkListUnit(N, CurrentCounter, B, idx));
738e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek  }
741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
7555825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  void enqueue(ExplodedNode *N) {
76a1e0540a051174d029401a7eb373cca295c4b9f9Anna Zaks    assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind);
7755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    enqueue(WorkListUnit(N, CurrentCounter));
78f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek  }
791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
8055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  virtual WorkListUnit dequeue() = 0;
811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
82d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  void setBlockCounter(BlockCounter C) { CurrentCounter = C; }
83d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis  BlockCounter getBlockCounter() const { return CurrentCounter; }
841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
853e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek  class Visitor {
863e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek  public:
873e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek    Visitor() {}
883e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek    virtual ~Visitor();
8955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek    virtual bool visit(const WorkListUnit &U) = 0;
903e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek  };
9155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  virtual bool visitItemsInWorkList(Visitor &V) = 0;
923e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek
9355825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  static WorkList *makeDFS();
9455825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  static WorkList *makeBFS();
9555825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek  static WorkList *makeBFSBlockDFSContents();
96f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek};
975a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
985a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace
995a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
1001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump} // end clang namespace
1015a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
102f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#endif
103