Fixing #507 (behaviour in cycles) by changing the topsort algorithm.

git-svn-id: https://reductivelabs.com/svn/puppet/trunk@2521 980ebf18-57e1-0310-9a29-db15c13687c0

2 files changed, 26 insertions, 23 deletions

diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb
index ce6c1e411..07bdff4bb 100644
--- a/lib/puppet/pgraph.rb
+++ b/lib/puppet/pgraph.rb
@@ -48,26 +48,6 @@ class Puppet::PGraph < GRATR::Digraph
         end
     end
 
-    # Fail in a somewhat informative way if the graph has become cyclic.
-    def check_cycle(sorted)
-        return true if sorted.size == size()
-
-        bad = []
-        vertices.each do |v|
-            bad << v unless sorted.include?(v)
-        end
-
-        if bad.length > 0
-            raise Puppet::Error,
-                "Found dependency cycle involving %s" % bad.collect do |v|
-                    v.to_s
-            end.join(", ")
-        else
-            raise Puppet::Error,
-                "Found dependency cycle but could not find the cause"
-        end
-    end
-
     # Which resources a given resource depends upon.
     def dependents(resource)
         tree_from_vertex2(resource).keys
@@ -185,6 +165,31 @@ class Puppet::PGraph < GRATR::Digraph
         end
     end
 
+    # Replace the default method, because we want to throw errors on back edges,
+    # not just skip them.
+    def topsort(start = nil, &block)
+        result  = []
+        go      = true 
+        cycles = []
+        back    = Proc.new { |e|
+            cycles << e
+            go = false
+        }
+        push    = Proc.new { |v| result.unshift(v) if go}
+        start   ||= vertices[0]
+        dfs({:exit_vertex => push, :back_edge => back, :start => start})
+        if block_given?
+            result.each {|v| yield(v) }
+        end
+
+        if cycles.length > 0
+            msg = "Found cycles in the following relationships:"
+            cycles.each { |edge| msg += " %s => %s" % [edge.source, edge.target] }
+            raise Puppet::Error, msg
+        end
+        return result
+    end
+
     # A different way of walking a tree, and a much faster way than the
     # one that comes with GRATR.
     def tree_from_vertex2(start, direction = :out)
diff --git a/lib/puppet/transaction.rb b/lib/puppet/transaction.rb
index 86d4bfc6e..7c046c898 100644
--- a/lib/puppet/transaction.rb
+++ b/lib/puppet/transaction.rb
@@ -497,10 +497,8 @@ class Transaction
         # Create a relationship graph from our resource graph
         @relgraph = relationship_graph
         
+        # This will throw an error if there are cycles in the graph.
         @sorted_resources = @relgraph.topsort
-
-        # Now make sure no cycles crept into our graph.
-        @relgraph.check_cycle(@sorted_resources)
     end
     
     # Create a graph of all of the relationships in our resource graph.