From: Daniel Pittman <[email protected]>
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.)
---
lib/puppet/simple_graph.rb | 48 +++++++++++++++++++++++++++++++++++++--
spec/unit/simple_graph_spec.rb | 48 +++++++++++++++++++++++++++++++++++++++-
2 files changed, 92 insertions(+), 4 deletions(-)
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.
--
1.7.3.5
--
You received this message because you are subscribed to the Google Groups
"Puppet Developers" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/puppet-dev?hl=en.
