Please review pull request #425: (#12269) multiple cycles in graph fail on sort opened by (daniel-pittman)
Description:
This fixes up code that handled the randomized hash ordering in Ruby 1.8.7 after a CVE fix:
At the time I felt it was safer to avoid changes to core classes, and instead to use an externally generated key for sorting. This turned out not to be the case - as so often the "safe" choice turns out t be worse that the "right" fix would have been.
This redresses that by extending the core Puppet::Type and Puppet::Provider classes to support ordering (against other instances of the same class, or subclasses), and then uses that everywhere that we need to express a natural ordering over sets of the same type.
It also adds an acceptance test, moves away from fake input data to tests, and generally improves our chances of detecting a similar problem next time through.
- Opened: Mon Jan 30 01:01:57 UTC 2012
- Based on: puppetlabs:2.7.x (5f23429c7b81d0cdb7166904649a8bcd8df350ae)
- Requested merge: daniel-pittman:bug/2.7.x/12269-multiple-cycles-in-graph-fail-on-sort (f8d4be615a2eef5a70a27dd9dc8f360ab0641d06)
Diff follows:
diff --git a/acceptance/tests/cycle_detection.rb b/acceptance/tests/cycle_detection.rb
new file mode 100644
index 0000000..c59ca9e
--- /dev/null
+++ b/acceptance/tests/cycle_detection.rb
@@ -0,0 +1,26 @@
+test_name "cycle detection and reporting"
+
+step "check we report a simple cycle"
+manifest = <<EOT
+notify { "a1": require => Notify["a2"] }
+notify { "a2": require => Notify["a1"] }
+EOT
+
+apply_manifest_on(agents, manifest) do
+ assert_match(/Found 1 dependency cycle/, stdout,
+ "found and reported the cycle correctly")
+end
+
+step "report multiple cycles in the same graph"
+manifest = <<EOT
+notify { "a1": require => Notify["a2"] }
+notify { "a2": require => Notify["a1"] }
+
+notify { "b1": require => Notify["b2"] }
+notify { "b2": require => Notify["b1"] }
+EOT
+
+apply_manifest_on(agents, manifest) do
+ assert_match(/Found 2 dependency cycles/, stdout,
+ "found and reported the cycle correctly")
+end
diff --git a/lib/puppet/module_tool/contents_description.rb b/lib/puppet/module_tool/contents_description.rb
index f6a94e2..6a59074 100644
--- a/lib/puppet/module_tool/contents_description.rb
+++ b/lib/puppet/module_tool/contents_description.rb
@@ -73,7 +73,7 @@ def attr_doc(type, kind)
# containing :name and :doc.
def provider_doc(type)
[].tap do |providers|
- type.providers.sort_by{ |o| o.to_s }.each do |prov|
+ type.providers.sort.each do |prov|
providers.push(:name => prov, :doc => type.provider(prov).doc)
end
end
diff --git a/lib/puppet/provider.rb b/lib/puppet/provider.rb
index 295ae83..87741e5 100644
--- a/lib/puppet/provider.rb
+++ b/lib/puppet/provider.rb
@@ -277,5 +277,14 @@ def set(params)
def to_s
"#{@resource}(provider=#{self.class.name})"
end
+
+ # Make providers comparable.
+ include Comparable
+ def <=>(other)
+ # We can only have ordering against other providers.
+ return nil unless other.is_a? Puppet::Provider
+ # Otherwise, order by the providers class name.
+ return self.class.name <=> other.class.name
+ end
end
diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index 6d9365f..fd38bb2 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -178,9 +178,7 @@ def find_cycles_in_graph
# Given we are in a failure state here, any extra cost is more or less
# irrelevant compared to the cost of a fix - which is on a human
# time-scale.
- state[:scc].select { |c| c.length > 1 }.map do |x|
- x.sort_by {|a| a.to_s }
- end.sort
+ state[:scc].select { |c| c.length > 1 }.map {|x| x.sort }.sort
end
# Perform a BFS on the sub graph representing the cycle, with a view to
@@ -214,7 +212,7 @@ def paths_in_cycle(cycle, max_paths = 1)
end
end
- return found
+ return found.sort
end
def report_cycles_in_graph
diff --git a/lib/puppet/type.rb b/lib/puppet/type.rb
index f1c8912..dfcbced 100644
--- a/lib/puppet/type.rb
+++ b/lib/puppet/type.rb
@@ -24,6 +24,17 @@ class Type
include Puppet::Util::Tagging
###############################
+ # Comparing type instances.
+ include Comparable
+ def <=>(other)
+ # We only order against other types, not arbitrary objects.
+ return nil unless other.is_a? Puppet::Type
+ # Our natural order is based on the reference name we use when comparing
+ # against other type instances.
+ self.ref <=> other.ref
+ end
+
+ ###############################
# Code related to resource type attributes.
class << self
include Puppet::Util::ClassGen
diff --git a/spec/unit/provider_spec.rb b/spec/unit/provider_spec.rb
index 4eb5e12..eeda5df 100755
--- a/spec/unit/provider_spec.rb
+++ b/spec/unit/provider_spec.rb
@@ -27,4 +27,36 @@
two.specificity.should > one.specificity
end
+
+ it "should be Comparable" do
+ res = Puppet::Type.type(:notify).new(:name => "res")
+
+ # Normally I wouldn't like the stubs, but the only way to name a class
+ # otherwise is to assign it to a constant, and that hurts more here in
+ # testing world. --daniel 2012-01-29
+ a = Class.new(Puppet::Provider).new(res)
+ a.class.stubs(:name).returns "Puppet::Provider::Notify::A"
+
+ b = Class.new(Puppet::Provider).new(res)
+ b.class.stubs(:name).returns "Puppet::Provider::Notify::B"
+
+ c = Class.new(Puppet::Provider).new(res)
+ c.class.stubs(:name).returns "Puppet::Provider::Notify::C"
+
+ [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].each do |this|
+ this.sort.should == [a, b, c]
+ end
+
+ a.should be < b
+ a.should be < c
+ b.should be > a
+ b.should be < c
+ c.should be > a
+ c.should be > b
+
+ [a, b, c].each {|x| a.should be <= x }
+ [a, b, c].each {|x| c.should be >= x }
+
+ b.should be_between(a, c)
+ end
end
diff --git a/spec/unit/simple_graph_spec.rb b/spec/unit/simple_graph_spec.rb
index 7c7add5..2cd00bd 100755
--- a/spec/unit/simple_graph_spec.rb
+++ b/spec/unit/simple_graph_spec.rb
@@ -268,9 +268,24 @@
@graph = Puppet::SimpleGraph.new
end
+ # This works with `add_edges` to auto-vivify the resource instances.
+ let :vertex do
+ Hash.new do |hash, key|
+ hash[key] = Puppet::Type.type(:notify).new(:name => key.to_s)
+ end
+ end
+
def add_edges(hash)
hash.each do |a,b|
- @graph.add_edge(a, b)
+ @graph.add_edge(vertex[a], vertex[b])
+ end
+ end
+
+ def simplify(cycles)
+ cycles.map do |x|
+ x.map do |y|
+ y.to_s.match(/^Notify\[(.*)\]$/)[1]
+ end
end
end
@@ -298,7 +313,7 @@ def add_edges(hash)
add_edges :a => :b, :b => :a
# cycle detection starts from a or b randomly
# so we need to check for either ordering in the error message
- want = %r{Found 1 dependency cycle:\n\((a => b => a|b => a => b)\)\nTry}
+ want = %r{Found 1 dependency cycle:\n\((Notify\[a\] => Notify\[b\] => Notify\[a\]|Notify\[b\] => Notify\[a\] => Notify\[b\])\)\nTry}
expect { @graph.report_cycles_in_graph }.to raise_error(Puppet::Error, want)
end
@@ -308,8 +323,8 @@ def add_edges(hash)
add_edges "b" => "c"
cycles = nil
- expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
- cycles.should be == [["a", "b"]]
+ expect { cycles = @graph.find_cycles_in_graph }.should_not raise_error
+ simplify(cycles).should be == [["a", "b"]]
end
it "cycle discovery should handle two distinct cycles" do
@@ -317,8 +332,8 @@ def add_edges(hash)
add_edges "b" => "b1", "b1" => "b"
cycles = nil
- expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
- cycles.should be == [["a", "a1"], ["b", "b1"]]
+ expect { cycles = @graph.find_cycles_in_graph }.should_not raise_error
+ simplify(cycles).should be == [["a1", "a"], ["b1", "b"]]
end
it "cycle discovery should handle two cycles in a connected graph" do
@@ -327,8 +342,8 @@ def add_edges(hash)
add_edges "c" => "c1", "c1" => "c2", "c2" => "c3", "c3" => "c"
cycles = nil
- expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
- cycles.should be == [%w{a a1}, %w{c c1 c2 c3}]
+ expect { cycles = @graph.find_cycles_in_graph }.should_not raise_error
+ simplify(cycles).should be == [%w{a1 a}, %w{c1 c2 c3 c}]
end
it "cycle discovery should handle a complicated cycle" do
@@ -338,8 +353,8 @@ def add_edges(hash)
add_edges "c" => "c2", "c2" => "b"
cycles = nil
- expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
- cycles.should be == [%w{a b c c1 c2}]
+ expect { cycles = @graph.find_cycles_in_graph }.should_not raise_error
+ simplify(cycles).should be == [%w{a b c1 c2 c}]
end
it "cycle discovery should not fail with large data sets" do
@@ -347,16 +362,16 @@ def add_edges(hash)
(1..(limit - 1)).each do |n| add_edges n.to_s => (n+1).to_s end
cycles = nil
- expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
- cycles.should be == []
+ expect { cycles = @graph.find_cycles_in_graph }.should_not raise_error
+ simplify(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
+ cycles = @graph.find_cycles_in_graph
paths = @graph.paths_in_cycle(cycles.first, 100)
- paths.should be == [%w{a b c a}]
+ simplify(paths).should be == [%w{a b c a}]
end
it "path finding should work with two independent cycles" do
@@ -364,28 +379,28 @@ def add_edges(hash)
add_edges "a" => "b2"
add_edges "b1" => "a", "b2" => "a"
- cycles = @graph.find_cycles_in_graph.sort
+ cycles = @graph.find_cycles_in_graph
cycles.length.should be == 1
paths = @graph.paths_in_cycle(cycles.first, 100)
- paths.sort.should be == [%w{a b1 a}, %w{a b2 a}]
+ simplify(paths).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 = @graph.find_cycles_in_graph
cycles.length.should be == 1
paths = @graph.paths_in_cycle(cycles.first, 100)
- paths.should be == [%w{a b a}, %w{a b c a}]
+ simplify(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 = @graph.find_cycles_in_graph
cycles.length.should be == 1
(1..20).each do |n|
diff --git a/spec/unit/type_spec.rb b/spec/unit/type_spec.rb
index 5fa9f45..10fe474 100755
--- a/spec/unit/type_spec.rb
+++ b/spec/unit/type_spec.rb
@@ -4,6 +4,28 @@
describe Puppet::Type, :fails_on_windows => true do
include PuppetSpec::Files
+ it "should be Comparable" do
+ a = Puppet::Type.type(:notify).new(:name => "a")
+ b = Puppet::Type.type(:notify).new(:name => "b")
+ c = Puppet::Type.type(:notify).new(:name => "c")
+
+ [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].each do |this|
+ this.sort.should == [a, b, c]
+ end
+
+ a.should be < b
+ a.should be < c
+ b.should be > a
+ b.should be < c
+ c.should be > a
+ c.should be > b
+
+ [a, b, c].each {|x| a.should be <= x }
+ [a, b, c].each {|x| c.should be >= x }
+
+ b.should be_between(a, c)
+ end
+
it "should consider a parameter to be valid if it is a valid parameter" do
Puppet::Type.type(:mount).should be_valid_parameter(:path)
end
-- 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.
