[Pkg-puppet-devel] [SCM] Puppet packaging for Debian branch, experimental, updated. debian/2.6.8-1-844-g7ec39d5

[Daniel Pittman]

The following commit has been merged in the experimental branch:
commit 9ea74ccd8c875f0d222874746f6b904883faf1d1
Author: Daniel Pittman <daniel at rimspace.net>
Date:   Sun Jan 23 23:31:44 2011 -0800

    Feature #2597 -- report all paths in each cycle found.
    
    Rather than reporting the cluster of vertexes in the dependency graph, which
    is interesting but not entirely informative, we now calculate and report the
    paths through the graph that form cycles.
    
    This returns the most useful information, which is the exact path that the
    dependency cycle has, allowing the user to (hopefully) immediately target it
    and start to work out why the cycle has formed there.
    
    We strongly prefer short paths through the dependency graph within the cycle,
    which should report the most useful loops to target first; extended loops
    involving more items will show up later if they are independently created.
    
    We also limit the number of paths reported (default: 10) to avoid overwhelming
    the error report with the combinatorial explosion that can easily result
    from a large scale cycle.  (eg: Package => User => Package or something.)

diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index c91d878..d081b4c 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -179,14 +179,56 @@ class Puppet::SimpleGraph
     return state.scc.select { |c| c.length > 1 }
   end
 
+  # Perform a BFS on the sub graph representing the cycle, with a view to
+  # generating a sufficient set of paths to report the cycle meaningfully, and
+  # ideally usefully, for the end user.
+  #
+  # BFS is preferred because it will generally report the shortest paths
+  # through the graph first, which are more likely to be interesting to the
+  # user.  I think; it would be interesting to verify that. --daniel 2011-01-23
+  def all_paths_in_cycle(cycle, max_paths = 10)
+    raise ArgumentError, "negative or zero max_paths" if max_paths < 1
+
+    # Calculate our filtered outbound vertex lists...
+    adj = {}
+    cycle.each do |vertex|
+      adj[vertex] = adjacent(vertex).select{|s| cycle.member? s}
+    end
+
+    found = []
+
+    stack = [OpenStruct.new :vertex => cycle.first, :path => []]
+    while frame = stack.shift do
+      if frame.path.member? frame.vertex then
+        found << frame.path + [frame.vertex]
+
+        # REVISIT: This should be an O(1) test, but I have no idea if Ruby
+        # specifies Array#length to be O(1), O(n), or allows the implementer
+        # to pick either option.  Should answer that. --daniel 2011-01-23
+        break if found.length >= max_paths
+      else
+        adj[frame.vertex].each do |to|
+          stack.push OpenStruct.new :vertex => to, :path => frame.path + [frame.vertex]
+        end
+      end
+    end
+
+    return found
+  end
+
   def report_cycles_in_graph
     cycles = find_cycles_in_graph
     n = cycles.length           # where is "pluralize"? --daniel 2011-01-22
     s = n == 1 ? '' : 's'
 
-    raise Puppet::Error, "Found #{n} dependency cycle#{s}:\n" +
-      cycles.collect { |c| '(' + c.join(", ") + ')' }.join("\n") + "\n" +
-      "Try the '--graph' option and opening the '.dot' file in OmniGraffle or GraphViz"
+    message = "Found #{n} dependency cycle#{s}:\n"
+    cycles.each do |cycle|
+      paths = all_paths_in_cycle(cycle)
+      message += paths.map{ |path| '(' + path.join(" => ") + ')'}.join("\n") + "\n"
+    end
+    message += "Try the '--graph' option and opening the '.dot' file in OmniGraffle or GraphViz"
+
+    raise Puppet::Error, message
   end
 
   # Provide a topological sort.
diff --git a/spec/unit/simple_graph_spec.rb b/spec/unit/simple_graph_spec.rb
index 3b0fe9a..e7c875f 100755
--- a/spec/unit/simple_graph_spec.rb
+++ b/spec/unit/simple_graph_spec.rb
@@ -305,7 +305,7 @@ describe Puppet::SimpleGraph do
 
     it "should produce the correct relationship text" do
       add_edges :a => :b, :b => :a
-      want = %r{Found 1 dependency cycle:\n\(a, b\)\nTry}
+      want = %r{Found 1 dependency cycle:\n\(a => b => a\)\nTry}
       expect { @graph.topsort }.to raise_error(Puppet::Error, want)
     end
 
@@ -358,6 +358,52 @@ describe Puppet::SimpleGraph do
       cycles.should be == []
     end
 
+    it "path finding should work with a simple cycle" do
+      add_edges "a" => "b", "b" => "c", "c" => "a"
+
+      cycles = @graph.find_cycles_in_graph.sort
+      paths = @graph.all_paths_in_cycle(cycles.first)
+      paths.should be == [%w{a b c a}]
+    end
+
+    it "path finding should work with two independent cycles" do
+      add_edges "a" => "b1"
+      add_edges "a" => "b2"
+      add_edges "b1" => "a", "b2" => "a"
+
+      cycles = @graph.find_cycles_in_graph.sort
+      cycles.length.should be == 1
+
+      paths = @graph.all_paths_in_cycle(cycles.first)
+      paths.sort.should be == [%w{a b1 a}, %w{a b2 a}]
+    end
+
+    it "path finding should prefer shorter paths in cycles" do
+      add_edges "a" => "b", "b" => "c", "c" => "a"
+      add_edges "b" => "a"
+
+      cycles = @graph.find_cycles_in_graph.sort
+      cycles.length.should be == 1
+
+      paths = @graph.all_paths_in_cycle(cycles.first)
+      paths.should be == [%w{a b a}, %w{a b c a}]
+    end
+
+    it "path finding should respect the max_path value" do
+      (1..20).each do |n| add_edges "a" => "b#{n}", "b#{n}" => "a" end
+
+      cycles = @graph.find_cycles_in_graph.sort
+      cycles.length.should be == 1
+
+      (1..20).each do |n|
+        paths = @graph.all_paths_in_cycle(cycles.first, n)
+        paths.length.should be == n
+      end
+
+      paths = @graph.all_paths_in_cycle(cycles.first, 21)
+      paths.length.should be == 20
+    end
+
     # Our graph's add_edge method is smart enough not to add
     # duplicate edges, so we use the objects, which it doesn't
     # check.

-- 
Puppet packaging for Debian