commit c1da441bb4df44c08a43591059bdfa1e5d044dc0
author Ted Kremenek <kremenek@apple.com> Tue Jun 17 19:14:06 2008 +0000
committer Ted Kremenek <kremenek@apple.com> Tue Jun 17 19:14:06 2008 +0000
tree 1e7f08aa85a91edb7ddb709daa4dff80a55adfad
parent 4111024be81e7c0525e42dadcc126d27e5bf2425

Fix non-termination bug reported by Thomas Clement!


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@52426 91177308-0d34-0410-b5e6-96231b3b80d8

lib/Analysis/BugReporter.cpp

diff --git a/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp
index cccd71b..141ee48 100644
--- a/lib/Analysis/BugReporter.cpp
+++ b/lib/Analysis/BugReporter.cpp
@@ -21,6 +21,7 @@
 #include "clang/AST/Expr.h"
 #include "clang/Analysis/ProgramPoint.h"
 #include "clang/Analysis/PathDiagnostic.h"
+#include "llvm/ADT/DenseSet.h"
 #include <sstream>
 
 using namespace clang;
@@ -205,8 +206,15 @@
                                      
                                      
   ExplodedNode<ValueState> *Last = 0, *First = 0;
+  
+  // Sometimes TrimGraph can contain a cycle because there are multiple BFS
+  // paths with the same length.  We mark the nodes we visit so that we
+  // don't get stuck in a cycle.
+  llvm::DenseSet<void*> Visited;
 
   while (N) {
+    Visited.insert(N);
+    
     ExplodedNode<ValueState>* NewN =
       G->getNode(N->getLocation(), N->getState());
     
@@ -214,7 +222,23 @@
     if (Last) Last->addPredecessor(NewN);
     
     Last = NewN;
-    N = N->pred_empty() ? 0 : *(N->pred_begin());
+    
+    if (N->pred_empty())
+      break;
+    
+    ExplodedNode<ValueState>::pred_iterator PI = N->pred_begin();
+    ExplodedNode<ValueState>::pred_iterator PE = N->pred_end();   
+    N = 0;
+    
+    // Look for the first predecessor that we have not already visited.
+
+    for (; PI != PE; ++PI)      
+      if (!Visited.count(*PI)) {
+        N = *PI;
+        break;
+      }
+    
+    assert (N && "All predecessors involved in a cycle!");    
   }
   
   return std::make_pair(G, First);