1 files changed, 122 insertions, 8 deletions

diff --git a/Analysis/ExplodedGraph.cpp b/Analysis/ExplodedGraph.cpp
index 274565bf6c..421b9e3846 100644
--- a/Analysis/ExplodedGraph.cpp
+++ b/Analysis/ExplodedGraph.cpp
@@ -13,6 +13,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/PathSensitive/ExplodedGraph.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include <vector>
 
 using namespace clang;
@@ -25,6 +28,7 @@ static inline std::vector<ExplodedNodeImpl*>& getVector(void* P) {
 void ExplodedNodeImpl::NodeGroup::addNode(ExplodedNodeImpl* N) {
   
   assert ((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
+  assert (!getFlag());
   
   if (getKind() == Size1) {
     if (ExplodedNodeImpl* NOld = getNode()) {
@@ -47,14 +51,11 @@ void ExplodedNodeImpl::NodeGroup::addNode(ExplodedNodeImpl* N) {
   }
 }
 
-bool ExplodedNodeImpl::NodeGroup::empty() const {
-  if (getKind() == Size1)
-    return getNode() ? false : true;
-  else
-    return getVector(getPtr()).empty();
-}
 
 unsigned ExplodedNodeImpl::NodeGroup::size() const {
+  if (getFlag())
+    return 0;
+  
   if (getKind() == Size1)
     return getNode() ? 1 : 0;
   else
@@ -62,15 +63,21 @@ unsigned ExplodedNodeImpl::NodeGroup::size() const {
 }
 
 ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::begin() const {
+  if (getFlag())
+    return NULL;
+  
   if (getKind() == Size1)
-    return (ExplodedNodeImpl**) &P;
+    return (ExplodedNodeImpl**) (getPtr() ? &P : NULL);
   else
     return const_cast<ExplodedNodeImpl**>(&*(getVector(getPtr()).begin()));
 }
 
 ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::end() const {
+  if (getFlag())
+    return NULL;
+  
   if (getKind() == Size1)
-    return (ExplodedNodeImpl**) (P ? &P+1 : &P);
+    return (ExplodedNodeImpl**) (getPtr() ? &P+1 : NULL);
   else
     return const_cast<ExplodedNodeImpl**>(&*(getVector(getPtr()).end()));
 }
@@ -78,3 +85,110 @@ ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::end() const {
 ExplodedNodeImpl::NodeGroup::~NodeGroup() {
   if (getKind() == SizeOther) delete &getVector(getPtr());
 }
+
+ExplodedGraphImpl* ExplodedGraphImpl::Trim(ExplodedNodeImpl** BeginSources,
+                                           ExplodedNodeImpl** EndSources) const{
+  
+  typedef llvm::DenseSet<ExplodedNodeImpl*> Pass1Ty;
+  typedef llvm::DenseMap<ExplodedNodeImpl*, ExplodedNodeImpl*> Pass2Ty;
+  
+  Pass1Ty Pass1;
+  Pass2Ty Pass2;
+  
+  llvm::SmallVector<ExplodedNodeImpl*, 10> WL2;
+
+  { // ===- Pass 1 (reverse BFS) -===
+    
+    // Enqueue the source nodes to the first worklist. 
+    
+    llvm::SmallVector<ExplodedNodeImpl*, 10> WL1;
+  
+    for (ExplodedNodeImpl** I = BeginSources; I != EndSources; ++I)
+      WL1.push_back(*I);
+    
+    // Process the worklist.
+
+    while (!WL1.empty()) {
+      
+      ExplodedNodeImpl* N = WL1.back();
+      WL1.pop_back();
+      
+      if (Pass1.count(N))
+        continue;
+      
+      Pass1.insert(N);
+      
+      if (N->Preds.empty()) {
+        WL2.push_back(N);
+        continue;      
+      }
+      
+      for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I)
+        WL1.push_back(*I);
+    }
+  }
+  
+  if (WL2.empty())
+    return NULL;
+    
+  ExplodedGraphImpl* G = MakeEmptyGraph();
+  
+  // ===- Pass 2 (forward DFS to construct the new graph) -===
+  
+  while (!WL2.empty()) {
+    
+    ExplodedNodeImpl* N = WL2.back();
+    WL2.pop_back();
+    
+    // Skip this node if we have already processed it.
+    
+    if (Pass2.find(N) != Pass2.end())
+      continue;
+    
+    // Create the corresponding node in the new graph.
+    
+    ExplodedNodeImpl* NewN = G->getNodeImpl(N->getLocation(), N->State, NULL);
+    Pass2[N] = NewN;
+    
+    if (N->Preds.empty())
+      G->addRoot(NewN);
+    
+    // In the case that some of the intended predecessors of NewN have already
+    // been created, we should hook them up as predecessors.
+    
+    for (ExplodedNodeImpl **I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I) {
+        
+      Pass2Ty::iterator PI = Pass2.find(*I);
+
+      if (PI == Pass2.end())
+        continue;
+      
+      NewN->addPredecessor(PI->second);
+    }
+
+    // In the case that some of the intended successors of NewN have already
+    // been created, we should hook them up as successors.  Otherwise, enqueue
+    // the new nodes from the original graph that should have nodes created
+    // in the new graph.
+   
+    for (ExplodedNodeImpl **I=N->Succs.begin(), **E=N->Succs.end(); I!=E; ++I) {
+      
+      Pass2Ty::iterator PI = Pass2.find(*I);
+      
+      if (PI != Pass2.end()) {
+        PI->second->addPredecessor(NewN);
+        continue;
+      }
+
+      // Enqueue nodes to the worklist that were marked during pass 1.
+      
+      if (Pass1.count(*I))
+        WL2.push_back(*I);
+    }
+    
+    if (N->isSink())
+      NewN->markAsSink();
+  }
+    
+  return G;
+}