diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb index f9a665d3c..b90079329 100644 --- a/lib/puppet/simple_graph.rb +++ b/lib/puppet/simple_graph.rb @@ -1,457 +1,498 @@ -# Created by Luke A. Kanies on 2007-11-07. -# Copyright (c) 2007. All rights reserved. +# Created by Luke A. Kanies on 2007-11-07. +# Cycle detection and reporting by Daniel Pittman 2011-01-22 +# Copyright (c) 2007, 2010. All rights reserved. require 'puppet/external/dot' require 'puppet/relationship' require 'set' +require 'ostruct' # A hopefully-faster graph class to replace the use of GRATR. class Puppet::SimpleGraph # # All public methods of this class must maintain (assume ^ ensure) the following invariants, where "=~=" means # equiv. up to order: # # @in_to.keys =~= @out_to.keys =~= all vertices # @in_to.values.collect { |x| x.values }.flatten =~= @out_from.values.collect { |x| x.values }.flatten =~= all edges # @in_to[v1][v2] =~= @out_from[v2][v1] =~= all edges from v1 to v2 # @in_to [v].keys =~= vertices with edges leading to v # @out_from[v].keys =~= vertices with edges leading from v # no operation may shed reference loops (for gc) # recursive operation must scale with the depth of the spanning trees, or better (e.g. no recursion over the set # of all vertices, etc.) # # This class is intended to be used with DAGs. However, if the # graph has a cycle, it will not cause non-termination of any of the # algorithms. The topsort method detects and reports cycles. # def initialize @in_to = {} @out_from = {} @upstream_from = {} @downstream_from = {} end # Clear our graph. def clear @in_to.clear @out_from.clear @upstream_from.clear @downstream_from.clear end # Which resources depend upon the given resource. def dependencies(resource) vertex?(resource) ? upstream_from_vertex(resource).keys : [] end def dependents(resource) vertex?(resource) ? downstream_from_vertex(resource).keys : [] end # Whether our graph is directed. Always true. Used to produce dot files. def directed? true end # Determine all of the leaf nodes below a given vertex. def leaves(vertex, direction = :out) tree_from_vertex(vertex, direction).keys.find_all { |c| adjacent(c, :direction => direction).empty? } end # Collect all of the edges that the passed events match. Returns # an array of edges. def matching_edges(event, base = nil) source = base || event.resource unless vertex?(source) Puppet.warning "Got an event from invalid vertex #{source.ref}" return [] end # Get all of the edges that this vertex should forward events # to, which is the same thing as saying all edges directly below # This vertex in the graph. @out_from[source].values.flatten.find_all { |edge| edge.match?(event.name) } end # Return a reversed version of this graph. def reversal result = self.class.new vertices.each { |vertex| result.add_vertex(vertex) } edges.each do |edge| result.add_edge edge.class.new(edge.target, edge.source, edge.label) end result end # Return the size of the graph. def size vertices.size end def to_a vertices end - # Provide a topological sort with cycle reporting - def topsort_with_cycles - degree = {} - zeros = [] - result = [] - - # Collect each of our vertices, with the number of in-edges each has. - vertices.each do |v| - edges = @in_to[v].dup - zeros << v if edges.empty? - degree[v] = edges + # This is a simple implementation of Tarjan's algorithm to find strongly + # connected components in the graph; this is a fairly ugly implementation, + # because I can't just decorate the vertices themselves. + # + # This method has an unhealthy relationship with the find_cycles_in_graph + # method below, which contains the knowledge of how the state object is + # maintained. + def tarjan(v, s) + s.index[v] = s.n + s.lowlink[v] = s.n + s.n = s.n + 1 + + s.s.push v + + @out_from[v].each do |edge| + to = edge[0] + + if ! s.index[to] then + tarjan(to, s) + s.lowlink[v] = [s.lowlink[v], s.lowlink[to]].min + elsif s.s.member? to then + # Performance note: the stack membership test *should* be done with a + # constant time check, but I was lazy and used something that is + # likely to be O(N) where N is the stack depth; this will bite us + # eventually, and should be improved before the change lands. + # + # OTOH, this is only invoked on a very cold path, when things have + # gone wrong anyhow, right now. I feel that getting the code out is + # worth more than that final performance boost. --daniel 2011-01-22 + s.lowlink[v] = [s.lowlink[v], s.index[to]].min + end end - # Iterate over each 0-degree vertex, decrementing the degree of - # each of its out-edges. - while v = zeros.pop - result << v - @out_from[v].each { |v2,es| - degree[v2].delete(v) - zeros << v2 if degree[v2].empty? - } + if s.lowlink[v] == s.index[v] then + # REVISIT: Surely there must be a nicer way to partition this around an + # index, but I don't know what it is. This works. :/ --daniel 2011-01-22 + # + # Performance note: this might also suffer an O(stack depth) performance + # hit, better replaced with something that is O(1) for splitting the + # stack into parts. + tmp = s.s.slice!(0, s.s.index(v)) + s.scc.push s.s + s.s = tmp end + end - # If we have any vertices left with non-zero in-degrees, then we've found a cycle. - if cycles = degree.values.reject { |ns| ns.empty? } and cycles.length > 0 - message = cycles.collect { |edges| - '(' + edges.collect { |e| e[1].to_s }.join(", ") + ')' - }.join("\n") - raise Puppet::Error, "Found dependency cycles in the following relationships:\n" + - message + "\n" + - "Try the '--graph' option and opening the '.dot' file in OmniGraffle or GraphViz" + # Find all cycles in the graph by detecting all the strongly connected + # components, then eliminating everything with a size of one as + # uninteresting - which it is, because it can't be a cycle. :) + # + # This has an unhealthy relationship with the 'tarjan' method above, which + # it uses to implement the detection of strongly connected components. + def find_cycles_in_graph + state = OpenStruct.new :n => 0, :index => {}, :lowlink => {}, :s => [], :scc => [] + + # we usually have a disconnected graph, must walk all possible roots + vertices.each do |vertex| + if ! state.index[vertex] then + tarjan vertex, state + end end - result + return state.scc.select { |c| c.length > 1 } + 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" end # Provide a topological sort. def topsort degree = {} zeros = [] result = [] # Collect each of our vertices, with the number of in-edges each has. vertices.each do |v| edges = @in_to[v] zeros << v if edges.empty? degree[v] = edges.length end # Iterate over each 0-degree vertex, decrementing the degree of # each of its out-edges. while v = zeros.pop result << v @out_from[v].each { |v2,es| zeros << v2 if (degree[v2] -= 1) == 0 } end # If we have any vertices left with non-zero in-degrees, then we've found a cycle. if cycles = degree.values.reject { |ns| ns == 0 } and cycles.length > 0 - topsort_with_cycles + report_cycles_in_graph end result end # Add a new vertex to the graph. def add_vertex(vertex) @in_to[vertex] ||= {} @out_from[vertex] ||= {} end # Remove a vertex from the graph. def remove_vertex!(v) return unless vertex?(v) @upstream_from.clear @downstream_from.clear (@in_to[v].values+@out_from[v].values).flatten.each { |e| remove_edge!(e) } @in_to.delete(v) @out_from.delete(v) end # Test whether a given vertex is in the graph. def vertex?(v) @in_to.include?(v) end # Return a list of all vertices. def vertices @in_to.keys end # Add a new edge. The graph user has to create the edge instance, # since they have to specify what kind of edge it is. def add_edge(e,*a) return add_relationship(e,*a) unless a.empty? @upstream_from.clear @downstream_from.clear add_vertex(e.source) add_vertex(e.target) @in_to[ e.target][e.source] ||= []; @in_to[ e.target][e.source] |= [e] @out_from[e.source][e.target] ||= []; @out_from[e.source][e.target] |= [e] end def add_relationship(source, target, label = nil) add_edge Puppet::Relationship.new(source, target, label) end # Find all matching edges. def edges_between(source, target) (@out_from[source] || {})[target] || [] end # Is there an edge between the two vertices? def edge?(source, target) vertex?(source) and vertex?(target) and @out_from[source][target] end def edges @in_to.values.collect { |x| x.values }.flatten end def each_edge @in_to.each { |t,ns| ns.each { |s,es| es.each { |e| yield e }}} end # Remove an edge from our graph. def remove_edge!(e) if edge?(e.source,e.target) @upstream_from.clear @downstream_from.clear @in_to [e.target].delete e.source if (@in_to [e.target][e.source] -= [e]).empty? @out_from[e.source].delete e.target if (@out_from[e.source][e.target] -= [e]).empty? end end # Find adjacent edges. def adjacent(v, options = {}) return [] unless ns = (options[:direction] == :in) ? @in_to[v] : @out_from[v] (options[:type] == :edges) ? ns.values.flatten : ns.keys end # Take container information from another graph and use it # to replace any container vertices with their respective leaves. # This creates direct relationships where there were previously # indirect relationships through the containers. def splice!(other, type) # We have to get the container list via a topological sort on the # configuration graph, because otherwise containers that contain # other containers will add those containers back into the # graph. We could get a similar affect by only setting relationships # to container leaves, but that would result in many more # relationships. stage_class = Puppet::Type.type(:stage) whit_class = Puppet::Type.type(:whit) containers = other.topsort.find_all { |v| (v.is_a?(type) or v.is_a?(stage_class)) and vertex?(v) } containers.each do |container| # Get the list of children from the other graph. children = other.adjacent(container, :direction => :out) # MQR TODO: Luke suggests that it should be possible to refactor the system so that # container nodes are retained, thus obviating the need for the whit. children = [whit_class.new(:name => container.name, :catalog => other)] if children.empty? # First create new edges for each of the :in edges [:in, :out].each do |dir| edges = adjacent(container, :direction => dir, :type => :edges) edges.each do |edge| children.each do |child| if dir == :in s = edge.source t = child else s = child t = edge.target end add_edge(s, t, edge.label) end # Now get rid of the edge, so remove_vertex! works correctly. remove_edge!(edge) end end remove_vertex!(container) end end # Just walk the tree and pass each edge. def walk(source, direction) # Use an iterative, breadth-first traversal of the graph. One could do # this recursively, but Ruby's slow function calls and even slower # recursion make the shorter, recursive algorithm cost-prohibitive. stack = [source] seen = Set.new until stack.empty? node = stack.shift next if seen.member? node connected = adjacent(node, :direction => direction) connected.each do |target| yield node, target end stack.concat(connected) seen << node end end # A different way of walking a tree, and a much faster way than the # one that comes with GRATR. def tree_from_vertex(start, direction = :out) predecessor={} walk(start, direction) do |parent, child| predecessor[child] = parent end predecessor end def downstream_from_vertex(v) return @downstream_from[v] if @downstream_from[v] result = @downstream_from[v] = {} @out_from[v].keys.each do |node| result[node] = 1 result.update(downstream_from_vertex(node)) end result end def upstream_from_vertex(v) return @upstream_from[v] if @upstream_from[v] result = @upstream_from[v] = {} @in_to[v].keys.each do |node| result[node] = 1 result.update(upstream_from_vertex(node)) end result end # LAK:FIXME This is just a paste of the GRATR code with slight modifications. # Return a DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph for an # undirected Graph. _params_ can contain any graph property specified in # rdot.rb. If an edge or vertex label is a kind of Hash then the keys # which match +dot+ properties will be used as well. def to_dot_graph (params = {}) params['name'] ||= self.class.name.gsub(/:/,'_') fontsize = params['fontsize'] ? params['fontsize'] : '8' graph = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params) edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge vertices.each do |v| name = v.to_s params = {'name' => '"'+name+'"', 'fontsize' => fontsize, 'label' => name} v_label = v.to_s params.merge!(v_label) if v_label and v_label.kind_of? Hash graph << DOT::DOTNode.new(params) end edges.each do |e| params = {'from' => '"'+ e.source.to_s + '"', 'to' => '"'+ e.target.to_s + '"', 'fontsize' => fontsize } e_label = e.to_s params.merge!(e_label) if e_label and e_label.kind_of? Hash graph << edge_klass.new(params) end graph end # Output the dot format as a string def to_dot (params={}) to_dot_graph(params).to_s; end # Call +dotty+ for the graph which is written to the file 'graph.dot' # in the # current directory. def dotty (params = {}, dotfile = 'graph.dot') File.open(dotfile, 'w') {|f| f << to_dot(params) } system('dotty', dotfile) end # Produce the graph files if requested. def write_graph(name) return unless Puppet[:graph] Puppet.settings.use(:graphing) file = File.join(Puppet[:graphdir], "#{name}.dot") File.open(file, "w") { |f| f.puts to_dot("name" => name.to_s.capitalize) } end # This flag may be set to true to use the new YAML serialzation # format (where @vertices is a simple list of vertices rather than a # list of VertexWrapper objects). Deserialization supports both # formats regardless of the setting of this flag. class << self attr_accessor :use_new_yaml_format end self.use_new_yaml_format = false # Stub class to allow graphs to be represented in YAML using the old # (version 2.6) format. class VertexWrapper attr_reader :vertex, :adjacencies def initialize(vertex, adjacencies) @vertex = vertex @adjacencies = adjacencies end def inspect { :@adjacencies => @adjacencies, :@vertex => @vertex.to_s }.inspect end end # instance_variable_get is used by Object.to_zaml to get instance # variables. Override it so that we can simulate the presence of # instance variables @edges and @vertices for serialization. def instance_variable_get(v) case v.to_s when '@edges' then edges when '@vertices' then if self.class.use_new_yaml_format vertices else result = {} vertices.each do |vertex| adjacencies = {} [:in, :out].each do |direction| adjacencies[direction] = {} adjacent(vertex, :direction => direction, :type => :edges).each do |edge| other_vertex = direction == :in ? edge.source : edge.target (adjacencies[direction][other_vertex] ||= Set.new).add(edge) end end result[vertex] = Puppet::SimpleGraph::VertexWrapper.new(vertex, adjacencies) end result end else super(v) end end def to_yaml_properties other_vars = instance_variables.reject { |v| %w{@in_to @out_from @upstream_from @downstream_from}.include?(v) } (other_vars + %w{@vertices @edges}).sort.uniq end def yaml_initialize(tag, var) initialize() vertices = var.delete('vertices') edges = var.delete('edges') if vertices.is_a?(Hash) # Support old (2.6) format vertices = vertices.keys end vertices.each { |v| add_vertex(v) } edges.each { |e| add_edge(e) } var.each do |varname, value| instance_variable_set("@#{varname}", value) end end end diff --git a/spec/unit/simple_graph_spec.rb b/spec/unit/simple_graph_spec.rb index 58978f2ba..a8e0c4434 100755 --- a/spec/unit/simple_graph_spec.rb +++ b/spec/unit/simple_graph_spec.rb @@ -1,768 +1,817 @@ #!/usr/bin/env ruby # # Created by Luke Kanies on 2007-11-1. # Copyright (c) 2006. All rights reserved. require File.expand_path(File.dirname(__FILE__) + '/../spec_helper') require 'puppet/simple_graph' describe Puppet::SimpleGraph do it "should return the number of its vertices as its length" do @graph = Puppet::SimpleGraph.new @graph.add_vertex("one") @graph.add_vertex("two") @graph.size.should == 2 end it "should consider itself a directed graph" do Puppet::SimpleGraph.new.directed?.should be_true end it "should provide a method for reversing the graph" do @graph = Puppet::SimpleGraph.new @graph.add_edge(:one, :two) @graph.reversal.edge?(:two, :one).should be_true end it "should be able to produce a dot graph" do @graph = Puppet::SimpleGraph.new @graph.add_edge(:one, :two) proc { @graph.to_dot_graph }.should_not raise_error end describe "when managing vertices" do before do @graph = Puppet::SimpleGraph.new end it "should provide a method to add a vertex" do @graph.add_vertex(:test) @graph.vertex?(:test).should be_true end it "should reset its reversed graph when vertices are added" do rev = @graph.reversal @graph.add_vertex(:test) @graph.reversal.should_not equal(rev) end it "should ignore already-present vertices when asked to add a vertex" do @graph.add_vertex(:test) proc { @graph.add_vertex(:test) }.should_not raise_error end it "should return true when asked if a vertex is present" do @graph.add_vertex(:test) @graph.vertex?(:test).should be_true end it "should return false when asked if a non-vertex is present" do @graph.vertex?(:test).should be_false end it "should return all set vertices when asked" do @graph.add_vertex(:one) @graph.add_vertex(:two) @graph.vertices.length.should == 2 @graph.vertices.should include(:one) @graph.vertices.should include(:two) end it "should remove a given vertex when asked" do @graph.add_vertex(:one) @graph.remove_vertex!(:one) @graph.vertex?(:one).should be_false end it "should do nothing when a non-vertex is asked to be removed" do proc { @graph.remove_vertex!(:one) }.should_not raise_error end end describe "when managing edges" do before do @graph = Puppet::SimpleGraph.new end it "should provide a method to test whether a given vertex pair is an edge" do @graph.should respond_to(:edge?) end it "should reset its reversed graph when edges are added" do rev = @graph.reversal @graph.add_edge(:one, :two) @graph.reversal.should_not equal(rev) end it "should provide a method to add an edge as an instance of the edge class" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge(edge) @graph.edge?(:one, :two).should be_true end it "should provide a method to add an edge by specifying the two vertices" do @graph.add_edge(:one, :two) @graph.edge?(:one, :two).should be_true end it "should provide a method to add an edge by specifying the two vertices and a label" do @graph.add_edge(:one, :two, :callback => :awesome) @graph.edge?(:one, :two).should be_true end describe "when retrieving edges between two nodes" do it "should handle the case of nodes not in the graph" do @graph.edges_between(:one, :two).should == [] end it "should handle the case of nodes with no edges between them" do @graph.add_vertex(:one) @graph.add_vertex(:two) @graph.edges_between(:one, :two).should == [] end it "should handle the case of nodes connected by a single edge" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge(edge) @graph.edges_between(:one, :two).length.should == 1 @graph.edges_between(:one, :two)[0].should equal(edge) end it "should handle the case of nodes connected by multiple edges" do edge1 = Puppet::Relationship.new(:one, :two, :callback => :foo) edge2 = Puppet::Relationship.new(:one, :two, :callback => :bar) @graph.add_edge(edge1) @graph.add_edge(edge2) Set.new(@graph.edges_between(:one, :two)).should == Set.new([edge1, edge2]) end end it "should add the edge source as a vertex if it is not already" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge(edge) @graph.vertex?(:one).should be_true end it "should add the edge target as a vertex if it is not already" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge(edge) @graph.vertex?(:two).should be_true end it "should return all edges as edge instances when asked" do one = Puppet::Relationship.new(:one, :two) two = Puppet::Relationship.new(:two, :three) @graph.add_edge(one) @graph.add_edge(two) edges = @graph.edges edges.should be_instance_of(Array) edges.length.should == 2 edges.should include(one) edges.should include(two) end it "should remove an edge when asked" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge(edge) @graph.remove_edge!(edge) @graph.edge?(edge.source, edge.target).should be_false end it "should remove all related edges when a vertex is removed" do one = Puppet::Relationship.new(:one, :two) two = Puppet::Relationship.new(:two, :three) @graph.add_edge(one) @graph.add_edge(two) @graph.remove_vertex!(:two) @graph.edge?(:one, :two).should be_false @graph.edge?(:two, :three).should be_false @graph.edges.length.should == 0 end end describe "when finding adjacent vertices" do before do @graph = Puppet::SimpleGraph.new @one_two = Puppet::Relationship.new(:one, :two) @two_three = Puppet::Relationship.new(:two, :three) @one_three = Puppet::Relationship.new(:one, :three) @graph.add_edge(@one_two) @graph.add_edge(@one_three) @graph.add_edge(@two_three) end it "should return adjacent vertices" do adj = @graph.adjacent(:one) adj.should be_include(:three) adj.should be_include(:two) end it "should default to finding :out vertices" do @graph.adjacent(:two).should == [:three] end it "should support selecting :in vertices" do @graph.adjacent(:two, :direction => :in).should == [:one] end it "should default to returning the matching vertices as an array of vertices" do @graph.adjacent(:two).should == [:three] end it "should support returning an array of matching edges" do @graph.adjacent(:two, :type => :edges).should == [@two_three] end # Bug #2111 it "should not consider a vertex adjacent just because it was asked about previously" do @graph = Puppet::SimpleGraph.new @graph.add_vertex("a") @graph.add_vertex("b") @graph.edge?("a", "b") @graph.adjacent("a").should == [] end end describe "when clearing" do before do @graph = Puppet::SimpleGraph.new one = Puppet::Relationship.new(:one, :two) two = Puppet::Relationship.new(:two, :three) @graph.add_edge(one) @graph.add_edge(two) @graph.clear end it "should remove all vertices" do @graph.vertices.should be_empty end it "should remove all edges" do @graph.edges.should be_empty end end describe "when reversing graphs" do before do @graph = Puppet::SimpleGraph.new end it "should provide a method for reversing the graph" do @graph.add_edge(:one, :two) @graph.reversal.edge?(:two, :one).should be_true end it "should add all vertices to the reversed graph" do @graph.add_edge(:one, :two) @graph.vertex?(:one).should be_true @graph.vertex?(:two).should be_true end it "should retain labels on edges" do @graph.add_edge(:one, :two, :callback => :awesome) edge = @graph.reversal.edges_between(:two, :one)[0] edge.label.should == {:callback => :awesome} end end describe "when sorting the graph" do before do @graph = Puppet::SimpleGraph.new end def add_edges(hash) hash.each do |a,b| @graph.add_edge(a, b) end end it "should sort the graph topologically" do add_edges :a => :b, :b => :c @graph.topsort.should == [:a, :b, :c] end it "should fail on two-vertex loops" do add_edges :a => :b, :b => :a proc { @graph.topsort }.should raise_error(Puppet::Error) end it "should fail on multi-vertex loops" do add_edges :a => :b, :b => :c, :c => :a proc { @graph.topsort }.should raise_error(Puppet::Error) end it "should fail when a larger tree contains a small cycle" do add_edges :a => :b, :b => :a, :c => :a, :d => :c proc { @graph.topsort }.should raise_error(Puppet::Error) end it "should succeed on trees with no cycles" do add_edges :a => :b, :b => :e, :c => :a, :d => :c proc { @graph.topsort }.should_not raise_error end it "should produce the correct relationship text" do add_edges :a => :b, :b => :a - want = %r{following relationships:\n\(b => a\)\n\(a => b\)} + want = %r{Found 1 dependency cycle:\n\(a, b\)\nTry} expect { @graph.topsort }.to raise_error(Puppet::Error, want) end + it "cycle discovery should be the minimum cycle for a simple graph" do + add_edges "a" => "b" + add_edges "b" => "a" + add_edges "b" => "c" + + cycles = nil + expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error + cycles.should be == [["a", "b"]] + end + + it "cycle discovery should handle two distinct cycles" do + add_edges "a" => "a1", "a1" => "a" + 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"]] + end + + it "cycle discovery should handle two cycles in a connected graph" do + add_edges "a" => "b", "b" => "c", "c" => "d" + add_edges "a" => "a1", "a1" => "a" + 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}] + end + + it "cycle discovery should handle a complicated cycle" do + add_edges "a" => "b", "b" => "c" + add_edges "a" => "c" + add_edges "c" => "c1", "c1" => "a" + 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}] + end + + it "cycle discovery should not fail with large data sets" do + limit = 1000 + (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 == [] + 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. it "should be able to sort graphs with duplicate edges" do one = Puppet::Relationship.new(:a, :b) @graph.add_edge(one) two = Puppet::Relationship.new(:a, :b) @graph.add_edge(two) proc { @graph.topsort }.should_not raise_error end end describe "when writing dot files" do before do @graph = Puppet::SimpleGraph.new @name = :test @file = File.join(Puppet[:graphdir], @name.to_s + ".dot") end it "should only write when graphing is enabled" do File.expects(:open).with(@file).never Puppet[:graph] = false @graph.write_graph(@name) end it "should write a dot file based on the passed name" do File.expects(:open).with(@file, "w").yields(stub("file", :puts => nil)) @graph.expects(:to_dot).with("name" => @name.to_s.capitalize) Puppet[:graph] = true @graph.write_graph(@name) end after do Puppet.settings.clear end end describe Puppet::SimpleGraph do before do @graph = Puppet::SimpleGraph.new end it "should correctly clear vertices and edges when asked" do @graph.add_edge("a", "b") @graph.add_vertex "c" @graph.clear @graph.vertices.should be_empty @graph.edges.should be_empty end end describe "when matching edges" do before do @graph = Puppet::SimpleGraph.new @event = Puppet::Transaction::Event.new(:name => :yay, :resource => "a") @none = Puppet::Transaction::Event.new(:name => :NONE, :resource => "a") @edges = {} @edges["a/b"] = Puppet::Relationship.new("a", "b", {:event => :yay, :callback => :refresh}) @edges["a/c"] = Puppet::Relationship.new("a", "c", {:event => :yay, :callback => :refresh}) @graph.add_edge(@edges["a/b"]) end it "should match edges whose source matches the source of the event" do @graph.matching_edges(@event).should == [@edges["a/b"]] end it "should match always match nothing when the event is :NONE" do @graph.matching_edges(@none).should be_empty end it "should match multiple edges" do @graph.add_edge(@edges["a/c"]) edges = @graph.matching_edges(@event) edges.should be_include(@edges["a/b"]) edges.should be_include(@edges["a/c"]) end end describe "when determining dependencies" do before do @graph = Puppet::SimpleGraph.new @graph.add_edge("a", "b") @graph.add_edge("a", "c") @graph.add_edge("b", "d") end it "should find all dependents when they are on multiple levels" do @graph.dependents("a").sort.should == %w{b c d}.sort end it "should find single dependents" do @graph.dependents("b").sort.should == %w{d}.sort end it "should return an empty array when there are no dependents" do @graph.dependents("c").sort.should == [].sort end it "should find all dependencies when they are on multiple levels" do @graph.dependencies("d").sort.should == %w{a b} end it "should find single dependencies" do @graph.dependencies("c").sort.should == %w{a} end it "should return an empty array when there are no dependencies" do @graph.dependencies("a").sort.should == [] end end require 'puppet/util/graph' class Container include Puppet::Util::Graph include Enumerable attr_accessor :name def each @children.each do |c| yield c end end def initialize(name, ary) @name = name @children = ary end def push(*ary) ary.each { |c| @children.push(c)} end def to_s @name end end describe "when splicing the graph" do def container_graph @one = Container.new("one", %w{a b}) @two = Container.new("two", ["c", "d"]) @three = Container.new("three", ["i", "j"]) @middle = Container.new("middle", ["e", "f", @two]) @top = Container.new("top", ["g", "h", @middle, @one, @three]) @empty = Container.new("empty", []) @whit = Puppet::Type.type(:whit) @stage = Puppet::Type.type(:stage).new(:name => "foo") @contgraph = @top.to_graph # We have to add the container to the main graph, else it won't # be spliced in the dependency graph. @contgraph.add_vertex(@empty) end def dependency_graph @depgraph = Puppet::SimpleGraph.new @contgraph.vertices.each do |v| @depgraph.add_vertex(v) end # We have to specify a relationship to our empty container, else it # never makes it into the dep graph in the first place. {@one => @two, "f" => "c", "h" => @middle, "c" => @empty}.each do |source, target| @depgraph.add_edge(source, target, :callback => :refresh) end end def splice @depgraph.splice!(@contgraph, Container) end before do container_graph dependency_graph splice end # This is the real heart of splicing -- replacing all containers in # our relationship and exploding their relationships so that each # relationship to a container gets copied to all of its children. it "should remove all Container objects from the dependency graph" do @depgraph.vertices.find_all { |v| v.is_a?(Container) }.should be_empty end # This is a bit hideous, but required to make stages work with relationships - they're # the top of the graph. it "should remove all Stage resources from the dependency graph" do @depgraph.vertices.find_all { |v| v.is_a?(Puppet::Type.type(:stage)) }.should be_empty end it "should add container relationships to contained objects" do @contgraph.leaves(@middle).each do |leaf| @depgraph.should be_edge("h", leaf) end end it "should explode container-to-container relationships, making edges between all respective contained objects" do @one.each do |oobj| @two.each do |tobj| @depgraph.should be_edge(oobj, tobj) end end end it "should contain a whit-resource to mark the place held by the empty container" do @depgraph.vertices.find_all { |v| v.is_a?(@whit) }.length.should == 1 end it "should replace edges to empty containers with edges to their residual whit" do emptys_whit = @depgraph.vertices.find_all { |v| v.is_a?(@whit) }.first @depgraph.should be_edge("c", emptys_whit) end it "should no longer contain anything but the non-container objects" do @depgraph.vertices.find_all { |v| ! v.is_a?(String) and ! v.is_a?(@whit)}.should be_empty end it "should copy labels" do @depgraph.edges.each do |edge| edge.label.should == {:callback => :refresh} end end it "should not add labels to edges that have none" do @depgraph.add_edge(@two, @three) splice @depgraph.edges_between("c", "i")[0].label.should == {} end it "should copy labels over edges that have none" do @depgraph.add_edge("c", @three, {:callback => :refresh}) splice # And make sure the label got copied. @depgraph.edges_between("c", "i")[0].label.should == {:callback => :refresh} end it "should not replace a label with a nil label" do # Lastly, add some new label-less edges and make sure the label stays. @depgraph.add_edge(@middle, @three) @depgraph.add_edge("c", @three, {:callback => :refresh}) splice @depgraph.edges_between("c", "i")[0].label.should == {:callback => :refresh} end it "should copy labels to all created edges" do @depgraph.add_edge(@middle, @three) @depgraph.add_edge("c", @three, {:callback => :refresh}) splice @three.each do |child| edge = Puppet::Relationship.new("c", child) @depgraph.should be_edge(edge.source, edge.target) @depgraph.edges_between(edge.source, edge.target)[0].label.should == {:callback => :refresh} end end end it "should serialize to YAML using the old format by default" do Puppet::SimpleGraph.use_new_yaml_format.should == false end describe "(yaml tests)" do def empty_graph(graph) end def one_vertex_graph(graph) graph.add_vertex(:a) end def graph_without_edges(graph) [:a, :b, :c].each { |x| graph.add_vertex(x) } end def one_edge_graph(graph) graph.add_edge(:a, :b) end def many_edge_graph(graph) graph.add_edge(:a, :b) graph.add_edge(:a, :c) graph.add_edge(:b, :d) graph.add_edge(:c, :d) end def labeled_edge_graph(graph) graph.add_edge(:a, :b, :callback => :foo, :event => :bar) end def overlapping_edge_graph(graph) graph.add_edge(:a, :b, :callback => :foo, :event => :bar) graph.add_edge(:a, :b, :callback => :biz, :event => :baz) end def self.all_test_graphs [:empty_graph, :one_vertex_graph, :graph_without_edges, :one_edge_graph, :many_edge_graph, :labeled_edge_graph, :overlapping_edge_graph] end def object_ids(enumerable) # Return a sorted list of the object id's of the elements of an # enumerable. enumerable.collect { |x| x.object_id }.sort end def graph_to_yaml(graph, which_format) previous_use_new_yaml_format = Puppet::SimpleGraph.use_new_yaml_format Puppet::SimpleGraph.use_new_yaml_format = (which_format == :new) ZAML.dump(graph) ensure Puppet::SimpleGraph.use_new_yaml_format = previous_use_new_yaml_format end # Test serialization of graph to YAML. [:old, :new].each do |which_format| all_test_graphs.each do |graph_to_test| it "should be able to serialize #{graph_to_test} to YAML (#{which_format} format)" do graph = Puppet::SimpleGraph.new send(graph_to_test, graph) yaml_form = graph_to_yaml(graph, which_format) # Hack the YAML so that objects in the Puppet namespace get # changed to YAML::DomainType objects. This lets us inspect # the serialized objects easily without invoking any # yaml_initialize hooks. yaml_form.gsub!('!ruby/object:Puppet::', '!hack/object:Puppet::') serialized_object = YAML.load(yaml_form) # Check that the object contains instance variables @edges and # @vertices only. @reversal is also permitted, but we don't # check it, because it is going to be phased out. serialized_object.type_id.should == 'object:Puppet::SimpleGraph' serialized_object.value.keys.reject { |x| x == 'reversal' }.sort.should == ['edges', 'vertices'] # Check edges by forming a set of tuples (source, target, # callback, event) based on the graph and the YAML and make sure # they match. edges = serialized_object.value['edges'] edges.should be_a(Array) expected_edge_tuples = graph.edges.collect { |edge| [edge.source, edge.target, edge.callback, edge.event] } actual_edge_tuples = edges.collect do |edge| edge.type_id.should == 'object:Puppet::Relationship' %w{source target}.each { |x| edge.value.keys.should include(x) } edge.value.keys.each { |x| ['source', 'target', 'callback', 'event'].should include(x) } %w{source target callback event}.collect { |x| edge.value[x] } end Set.new(actual_edge_tuples).should == Set.new(expected_edge_tuples) actual_edge_tuples.length.should == expected_edge_tuples.length # Check vertices one by one. vertices = serialized_object.value['vertices'] if which_format == :old vertices.should be_a(Hash) Set.new(vertices.keys).should == Set.new(graph.vertices) vertices.each do |key, value| value.type_id.should == 'object:Puppet::SimpleGraph::VertexWrapper' value.value.keys.sort.should == %w{adjacencies vertex} value.value['vertex'].should equal(key) adjacencies = value.value['adjacencies'] adjacencies.should be_a(Hash) Set.new(adjacencies.keys).should == Set.new([:in, :out]) [:in, :out].each do |direction| adjacencies[direction].should be_a(Hash) expected_adjacent_vertices = Set.new(graph.adjacent(key, :direction => direction, :type => :vertices)) Set.new(adjacencies[direction].keys).should == expected_adjacent_vertices adjacencies[direction].each do |adj_key, adj_value| # Since we already checked edges, just check consistency # with edges. desired_source = direction == :in ? adj_key : key desired_target = direction == :in ? key : adj_key expected_edges = edges.select do |edge| edge.value['source'] == desired_source && edge.value['target'] == desired_target end adj_value.should be_a(Set) if object_ids(adj_value) != object_ids(expected_edges) raise "For vertex #{key.inspect}, direction #{direction.inspect}: expected adjacencies #{expected_edges.inspect} but got #{adj_value.inspect}" end end end end else vertices.should be_a(Array) Set.new(vertices).should == Set.new(graph.vertices) vertices.length.should == graph.vertices.length end end end # Test deserialization of graph from YAML. This presumes the # correctness of serialization to YAML, which has already been # tested. all_test_graphs.each do |graph_to_test| it "should be able to deserialize #{graph_to_test} from YAML (#{which_format} format)" do reference_graph = Puppet::SimpleGraph.new send(graph_to_test, reference_graph) yaml_form = graph_to_yaml(reference_graph, which_format) recovered_graph = YAML.load(yaml_form) # Test that the recovered vertices match the vertices in the # reference graph. expected_vertices = reference_graph.vertices.to_a recovered_vertices = recovered_graph.vertices.to_a Set.new(recovered_vertices).should == Set.new(expected_vertices) recovered_vertices.length.should == expected_vertices.length # Test that the recovered edges match the edges in the # reference graph. expected_edge_tuples = reference_graph.edges.collect do |edge| [edge.source, edge.target, edge.callback, edge.event] end recovered_edge_tuples = recovered_graph.edges.collect do |edge| [edge.source, edge.target, edge.callback, edge.event] end Set.new(recovered_edge_tuples).should == Set.new(expected_edge_tuples) recovered_edge_tuples.length.should == expected_edge_tuples.length # We ought to test that the recovered graph is self-consistent # too. But we're not going to bother with that yet because # the internal representation of the graph is about to change. end end it "should be able to serialize a graph where the vertices contain backreferences to the graph (#{which_format} format)" do reference_graph = Puppet::SimpleGraph.new vertex = Object.new vertex.instance_eval { @graph = reference_graph } reference_graph.add_edge(vertex, :other_vertex) yaml_form = graph_to_yaml(reference_graph, which_format) recovered_graph = YAML.load(yaml_form) recovered_graph.vertices.length.should == 2 recovered_vertex = recovered_graph.vertices.reject { |x| x.is_a?(Symbol) }[0] recovered_vertex.instance_eval { @graph }.should equal(recovered_graph) recovered_graph.edges.length.should == 1 recovered_edge = recovered_graph.edges[0] recovered_edge.source.should equal(recovered_vertex) recovered_edge.target.should == :other_vertex end end it "should serialize properly when used as a base class" do class Puppet::TestDerivedClass < Puppet::SimpleGraph attr_accessor :foo end derived = Puppet::TestDerivedClass.new derived.add_edge(:a, :b) derived.foo = 1234 recovered_derived = YAML.load(YAML.dump(derived)) recovered_derived.class.should equal(Puppet::TestDerivedClass) recovered_derived.edges.length.should == 1 recovered_derived.edges[0].source.should == :a recovered_derived.edges[0].target.should == :b recovered_derived.vertices.length.should == 2 recovered_derived.foo.should == 1234 end end end