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" 199946fc735d7285f2195f89635370f534afd9877eDmitri Gribenko#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 209946fc735d7285f2195f89635370f534afd9877eDmitri Gribenko#include <cassert> 218e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 221eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpnamespace clang { 23539e9b18e64479e1092e0cd52efdb2ad41b4d07dDouglas Gregor 24539e9b18e64479e1092e0cd52efdb2ad41b4d07dDouglas Gregorclass CFGBlock; 255a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 269ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento { 275a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 28d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass WorkListUnit { 299c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *node; 3055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek BlockCounter counter; 319c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *block; 3255825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek unsigned blockIdx; // This is the index of the next statement. 331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 34f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 359c378f705405d37f49795d5e915989de774fe11fTed Kremenek WorkListUnit(ExplodedNode *N, BlockCounter C, 369c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *B, unsigned idx) 3755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek : node(N), 3855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek counter(C), 3955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek block(B), 4055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek blockIdx(idx) {} 411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 429c378f705405d37f49795d5e915989de774fe11fTed Kremenek explicit WorkListUnit(ExplodedNode *N, BlockCounter C) 4355825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek : node(N), 4455825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek counter(C), 4555825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek block(NULL), 4655825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek blockIdx(0) {} 4755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek 4855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek /// Returns the node associated with the worklist unit. 4955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek ExplodedNode *getNode() const { return node; } 5055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek 5155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek /// Returns the block counter map associated with the worklist unit. 5255825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek BlockCounter getBlockCounter() const { return counter; } 5355825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek 5455825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek /// Returns the CFGblock associated with the worklist unit. 5555825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek const CFGBlock *getBlock() const { return block; } 5655825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek 5755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek /// Return the index within the CFGBlock for the worklist unit. 5855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek unsigned getIndex() const { return blockIdx; } 59f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 60f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 61d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass WorkList { 62d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter CurrentCounter; 63f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 64d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis virtual ~WorkList(); 65f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek virtual bool hasWork() const = 0; 661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual void enqueue(const WorkListUnit& U) = 0; 68f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 6955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) { 7055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek enqueue(WorkListUnit(N, CurrentCounter, B, idx)); 718e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek } 721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7355825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek void enqueue(ExplodedNode *N) { 74cdcc653642d4ac9255c574fabe74a48149e06733Anna Zaks assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); 7555825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek enqueue(WorkListUnit(N, CurrentCounter)); 76f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual WorkListUnit dequeue() = 0; 791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 80d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis void setBlockCounter(BlockCounter C) { CurrentCounter = C; } 81d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter getBlockCounter() const { return CurrentCounter; } 821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 833e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek class Visitor { 843e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek public: 853e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek Visitor() {} 863e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek virtual ~Visitor(); 8755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual bool visit(const WorkListUnit &U) = 0; 883e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek }; 8955825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual bool visitItemsInWorkList(Visitor &V) = 0; 903e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek 9155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek static WorkList *makeDFS(); 9255825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek static WorkList *makeBFS(); 9355825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek static WorkList *makeBFSBlockDFSContents(); 94f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 955a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 965a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace 975a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump} // end clang namespace 995a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis 100f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#endif 101