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