From 001e040b55064721c4decd8d7e1be3b566b2693d Mon Sep 17 00:00:00 2001
From: Ted Kremenek <kremenek@apple.com>
Date: Sat, 13 Nov 2010 05:04:49 +0000
Subject: [PATCH] Add GRWorkList::VisitItemsInWorkList() to allow a client to
 introspect the contents of a worklist. This API required changing the BFS
 worklist to use a deque instead of a queue, but that is better for
 performance reasons anyway.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@118982 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/clang/Checker/PathSensitive/GRWorkList.h |  8 ++++
 lib/Checker/GRCoreEngine.cpp                     | 48 ++++++++++++++++++++----
 2 files changed, 48 insertions(+), 8 deletions(-)

diff --git a/include/clang/Checker/PathSensitive/GRWorkList.h b/include/clang/Checker/PathSensitive/GRWorkList.h
index 315b61404..6400dae2c 100644
--- a/include/clang/Checker/PathSensitive/GRWorkList.h
+++ b/include/clang/Checker/PathSensitive/GRWorkList.h
@@ -71,6 +71,14 @@ public:
   void setBlockCounter(GRBlockCounter C) { CurrentCounter = C; }
   GRBlockCounter getBlockCounter() const { return CurrentCounter; }
 
+  class Visitor {
+  public:
+    Visitor() {}
+    virtual ~Visitor();
+    virtual bool Visit(const GRWorkListUnit &U) = 0;
+  };
+  virtual bool VisitItemsInWorkList(Visitor &V) = 0;
+  
   static GRWorkList *MakeDFS();
   static GRWorkList *MakeBFS();
   static GRWorkList *MakeBFSBlockDFSContents();
diff --git a/lib/Checker/GRCoreEngine.cpp b/lib/Checker/GRCoreEngine.cpp
index 4bcac4d16..50aa563c6 100644
--- a/lib/Checker/GRCoreEngine.cpp
+++ b/lib/Checker/GRCoreEngine.cpp
@@ -36,6 +36,8 @@ GRTransferFuncs* MakeCFRefCountTF(ASTContext& Ctx, bool GCEnabled,
 // Worklist classes for exploration of reachable states.
 //===----------------------------------------------------------------------===//
 
+GRWorkList::Visitor::~Visitor() {}
+
 namespace {
 class DFS : public GRWorkList {
   llvm::SmallVector<GRWorkListUnit,20> Stack;
@@ -54,26 +56,42 @@ public:
     Stack.pop_back(); // This technically "invalidates" U, but we are fine.
     return U;
   }
+  
+  virtual bool VisitItemsInWorkList(Visitor &V) {
+    for (llvm::SmallVectorImpl<GRWorkListUnit>::iterator
+         I = Stack.begin(), E = Stack.end(); I != E; ++I) {
+      if (V.Visit(*I))
+        return true;
+    }
+    return false;
+  }
 };
 
 class BFS : public GRWorkList {
-  std::queue<GRWorkListUnit> Queue;
+  std::deque<GRWorkListUnit> Queue;
 public:
   virtual bool hasWork() const {
     return !Queue.empty();
   }
 
   virtual void Enqueue(const GRWorkListUnit& U) {
-    Queue.push(U);
+    Queue.push_front(U);
   }
 
   virtual GRWorkListUnit Dequeue() {
-    // Don't use const reference.  The subsequent pop_back() might make it
-    // unsafe.
     GRWorkListUnit U = Queue.front();
-    Queue.pop();
+    Queue.pop_front();
     return U;
   }
+  
+  virtual bool VisitItemsInWorkList(Visitor &V) {
+    for (std::deque<GRWorkListUnit>::iterator
+         I = Queue.begin(), E = Queue.end(); I != E; ++I) {
+      if (V.Visit(*I))
+        return true;
+    }
+    return false;
+  }
 };
 
 } // end anonymous namespace
@@ -87,7 +105,7 @@ GRWorkList *GRWorkList::MakeBFS() { return new BFS(); }
 
 namespace {
   class BFSBlockDFSContents : public GRWorkList {
-    std::queue<GRWorkListUnit> Queue;
+    std::deque<GRWorkListUnit> Queue;
     llvm::SmallVector<GRWorkListUnit,20> Stack;
   public:
     virtual bool hasWork() const {
@@ -96,7 +114,7 @@ namespace {
 
     virtual void Enqueue(const GRWorkListUnit& U) {
       if (isa<BlockEntrance>(U.getNode()->getLocation()))
-        Queue.push(U);
+        Queue.push_front(U);
       else
         Stack.push_back(U);
     }
@@ -113,9 +131,23 @@ namespace {
       // Don't use const reference.  The subsequent pop_back() might make it
       // unsafe.
       GRWorkListUnit U = Queue.front();
-      Queue.pop();
+      Queue.pop_front();
       return U;
     }
+    virtual bool VisitItemsInWorkList(Visitor &V) {
+      for (llvm::SmallVectorImpl<GRWorkListUnit>::iterator
+           I = Stack.begin(), E = Stack.end(); I != E; ++I) {
+        if (V.Visit(*I))
+          return true;
+      }
+      for (std::deque<GRWorkListUnit>::iterator
+           I = Queue.begin(), E = Queue.end(); I != E; ++I) {
+        if (V.Visit(*I))
+          return true;
+      }
+      return false;
+    }
+
   };
 } // end anonymous namespace
 
-- 
2.11.4.GIT