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

4 files changed, 34 insertions, 27 deletions

diff --git a/CHANGELOG b/CHANGELOG
index dca71a9de..00b38153b 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,3 +1,6 @@
+    Changed the topological sort algorithm (#507) so it will always
+    fail on cycles.
+
     Added a 'dynamicfacts' configuration option; any facts in that
     comma-separated list will be ignored when comparing facts to 
     see if they have changed and thus whether a recompile is necessary.
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.
diff --git a/test/other/pgraph.rb b/test/other/pgraph.rb
index b61241087..34ba0e18c 100755
--- a/test/other/pgraph.rb
+++ b/test/other/pgraph.rb
@@ -189,10 +189,11 @@ class TestPGraph < Test::Unit::TestCase
             graph.edge_label(:a, :b), "lost label")
     end
 
-    def test_check_cycle
+    def test_fail_on_cycle
         {
-            {:a => :b, :b => :a} => true,
+            {:a => :b, :b => :a, :c => :a, :d => :c} => true, # larger tree involving a smaller cycle
             {:a => :b, :b => :c, :c => :a} => true,
+            {:a => :b, :b => :a, :c => :d, :d => :c} => true,
             {:a => :b, :b => :c} => false,
         }.each do |hash, result|
             graph = Puppet::PGraph.new
@@ -202,11 +203,11 @@ class TestPGraph < Test::Unit::TestCase
 
             if result
                 assert_raise(Puppet::Error, "%s did not fail" % hash.inspect) do
-                    graph.check_cycle(graph.topsort)
+                   graph.topsort
                 end
             else
                 assert_nothing_raised("%s failed" % hash.inspect) do
-                    graph.check_cycle(graph.topsort)
+                    graph.topsort
                 end
             end
         end