diff options
| -rw-r--r-- | lib/puppet/node/catalog.rb | 29 | ||||
| -rw-r--r-- | lib/puppet/pgraph.rb | 121 | ||||
| -rw-r--r-- | lib/puppet/simple_graph.rb | 103 | ||||
| -rw-r--r-- | lib/puppet/transaction.rb | 4 | ||||
| -rw-r--r-- | lib/puppet/util/graph.rb | 4 | ||||
| -rwxr-xr-x | spec/unit/node/catalog.rb | 22 | ||||
| -rwxr-xr-x | spec/unit/other/pgraph.rb | 210 | ||||
| -rwxr-xr-x | spec/unit/simple_graph.rb | 643 |
8 files changed, 545 insertions, 591 deletions
diff --git a/lib/puppet/node/catalog.rb b/lib/puppet/node/catalog.rb index 39b3fdfdc..0138fd8cb 100644 --- a/lib/puppet/node/catalog.rb +++ b/lib/puppet/node/catalog.rb @@ -1,5 +1,5 @@ require 'puppet/indirector' -require 'puppet/pgraph' +require 'puppet/simple_graph' require 'puppet/transaction' require 'puppet/util/tagging' @@ -8,7 +8,7 @@ require 'puppet/util/tagging' # meant to be passed from server to client, and it contains all # of the information in the catalog, including the resources # and the relationships between them. -class Puppet::Node::Catalog < Puppet::PGraph +class Puppet::Node::Catalog < Puppet::SimpleGraph extend Puppet::Indirector indirects :catalog, :terminus_class => :compiler @@ -321,17 +321,13 @@ class Puppet::Node::Catalog < Puppet::PGraph # Create a graph of all of the relationships in our catalog. def relationship_graph - raise(Puppet::DevError, "Tried get a relationship graph for a relationship graph") if self.is_relationship_graph - unless defined? @relationship_graph and @relationship_graph # It's important that we assign the graph immediately, because # the debug messages below use the relationships in the # relationship graph to determine the path to the resources # spitting out the messages. If this is not set, # then we get into an infinite loop. - @relationship_graph = Puppet::Node::Catalog.new - @relationship_graph.host_config = host_config? - @relationship_graph.is_relationship_graph = true + @relationship_graph = Puppet::SimpleGraph.new # First create the dependency graph self.vertices.each do |vertex| @@ -355,12 +351,12 @@ class Puppet::Node::Catalog < Puppet::PGraph end end - @relationship_graph.write_graph(:relationships) + @relationship_graph.write_graph(:relationships) if host_config? # Then splice in the container information @relationship_graph.splice!(self, Puppet::Type::Component) - @relationship_graph.write_graph(:expanded_relationships) + @relationship_graph.write_graph(:expanded_relationships) if host_config? end @relationship_graph end @@ -391,11 +387,7 @@ class Puppet::Node::Catalog < Puppet::PGraph # Reference class canonizes for us. ref = Puppet::ResourceReference.new(nil, type).to_s end - if resource = @resource_table[ref] - return resource - elsif defined?(@relationship_graph) and @relationship_graph - @relationship_graph.resource(ref) - end + @resource_table[ref] end # Return an array of all resources. @@ -417,15 +409,8 @@ class Puppet::Node::Catalog < Puppet::PGraph def write_graph(name) # We only want to graph the main host catalog. return unless host_config? - - return unless Puppet[:graph] - - Puppet.settings.use(:graphing) - file = File.join(Puppet[:graphdir], "%s.dot" % name.to_s) - File.open(file, "w") { |f| - f.puts to_dot("name" => name.to_s.capitalize) - } + super end # LAK:NOTE We cannot yaml-dump the class in the edgelist_class, because classes cannot be diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb deleted file mode 100644 index 55ad7d2c1..000000000 --- a/lib/puppet/pgraph.rb +++ /dev/null @@ -1,121 +0,0 @@ -# Created by Luke A. Kanies on 2006-11-24. -# Copyright (c) 2006. All rights reserved. - -require 'puppet/relationship' -require 'puppet/simple_graph' - -# This class subclasses a graph class in order to handle relationships -# among resources. -class Puppet::PGraph < Puppet::SimpleGraph - include Puppet::Util - - def add_edge(*args) - @reversal = nil - super - end - - def add_vertex(*args) - @reversal = nil - super - end - - # Which resources a given resource depends upon. - def dependents(resource) - tree_from_vertex(resource).keys - end - - # Which resources depend upon the given resource. - def dependencies(resource) - # Cache the reversal graph, because it's somewhat expensive - # to create. - unless defined? @reversal and @reversal - @reversal = reversal - end - # Strangely, it's significantly faster to search a reversed - # tree in the :out direction than to search a normal tree - # in the :in direction. - @reversal.tree_from_vertex(resource, :out).keys - end - - # Determine all of the leaf nodes below a given vertex. - def leaves(vertex, direction = :out) - tree = tree_from_vertex(vertex, direction) - l = tree.keys.find_all { |c| adjacent(c, :direction => direction).empty? } - return l - end - - # Collect all of the edges that the passed events match. Returns - # an array of edges. - def matching_edges(events, base = nil) - events.collect do |event| - source = base || event.source - - unless vertex?(source) - Puppet.warning "Got an event from invalid vertex %s" % source.ref - next - 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. - adjacent(source, :direction => :out, :type => :edges).find_all do |edge| - edge.match?(event.name) - end - end.compact.flatten - 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. - containers = other.topsort.find_all { |v| v.is_a?(type) and vertex?(v) } - containers.each do |container| - # Get the list of children from the other graph. - children = other.adjacent(container, :direction => :out) - - # Just remove the container if it's empty. - if children.empty? - remove_vertex!(container) - next - end - - # 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 - - # 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 -end diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb index c926258ca..73a6bdfed 100644 --- a/lib/puppet/simple_graph.rb +++ b/lib/puppet/simple_graph.rb @@ -94,10 +94,47 @@ class Puppet::SimpleGraph @edges.clear end + # Which resources a given resource depends upon. + def dependents(resource) + tree_from_vertex(resource).keys + end + + # Which resources depend upon the given resource. + def dependencies(resource) + # Cache the reversal graph, because it's somewhat expensive + # to create. + unless defined? @reversal and @reversal + @reversal = reversal + end + # Strangely, it's significantly faster to search a reversed + # tree in the :out direction than to search a normal tree + # in the :in direction. + @reversal.tree_from_vertex(resource, :out).keys + end + # Whether our graph is directed. Always true. Used to produce dot files. def directed? true end + + # Collect all of the edges that the passed events match. Returns + # an array of edges. + def matching_edges(events, base = nil) + events.collect do |event| + source = base || event.source + + unless vertex?(source) + Puppet.warning "Got an event from invalid vertex %s" % source.ref + next + 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. + adjacent(source, :direction => :out, :type => :edges).find_all do |edge| + edge.match?(event.name) + end + end.compact.flatten + end # Return a reversed version of this graph. def reversal @@ -154,6 +191,7 @@ class Puppet::SimpleGraph # Add a new vertex to the graph. def add_vertex(vertex) + @reversal = nil return false if vertex?(vertex) setup_vertex(vertex) true # don't return the VertexWrapper instance. @@ -180,6 +218,7 @@ class Puppet::SimpleGraph # 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(source, target = nil, label = nil) + @reversal = nil if target edge = Puppet::Relationship.new(source, target, label) else @@ -250,6 +289,52 @@ class Puppet::SimpleGraph # induced_subgraph(gv).write_to_graphic_file('jpg', name) # end # 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. + containers = other.topsort.find_all { |v| v.is_a?(type) and vertex?(v) } + containers.each do |container| + # Get the list of children from the other graph. + children = other.adjacent(container, :direction => :out) + + # Just remove the container if it's empty. + if children.empty? + remove_vertex!(container) + next + end + + # 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 def to_yaml_properties instance_variables @@ -263,6 +348,16 @@ class Puppet::SimpleGraph 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 + # 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 @@ -304,6 +399,14 @@ class Puppet::SimpleGraph system('dotty', dotfile) end + # Just walk the tree and pass each edge. + def walk(source, direction, &block) + adjacent(source, :direction => direction).each do |target| + yield source, target + walk(target, direction, &block) + end + end + # Use +dot+ to create a graphical representation of the graph. Returns the # filename of the graphics file. def write_to_graphic_file (fmt='png', dotfile='graph') diff --git a/lib/puppet/transaction.rb b/lib/puppet/transaction.rb index e6dc60681..86467a5b4 100644 --- a/lib/puppet/transaction.rb +++ b/lib/puppet/transaction.rb @@ -431,8 +431,8 @@ class Transaction def initialize(resources) if resources.is_a?(Puppet::Node::Catalog) @catalog = resources - elsif resources.is_a?(Puppet::PGraph) - raise "Transactions should get catalogs now, not PGraph" + elsif resources.is_a?(Puppet::SimpleGraph) + raise "Transactions should get catalogs now, not SimpleGraph" else raise "Transactions require catalogs" end diff --git a/lib/puppet/util/graph.rb b/lib/puppet/util/graph.rb index d1ef36f8e..fc05cafd9 100644 --- a/lib/puppet/util/graph.rb +++ b/lib/puppet/util/graph.rb @@ -2,7 +2,7 @@ # Copyright (c) 2006. All rights reserved. require 'puppet' -require 'puppet/pgraph' +require 'puppet/simple_graph' # A module that handles the small amount of graph stuff in Puppet. module Puppet::Util::Graph @@ -12,7 +12,7 @@ module Puppet::Util::Graph def to_graph(graph = nil, &block) # Allow our calling function to send in a graph, so that we # can call this recursively with one graph. - graph ||= Puppet::PGraph.new + graph ||= Puppet::SimpleGraph.new self.each do |child| unless block_given? and ! yield(child) diff --git a/spec/unit/node/catalog.rb b/spec/unit/node/catalog.rb index 68b8af347..6451632d5 100755 --- a/spec/unit/node/catalog.rb +++ b/spec/unit/node/catalog.rb @@ -685,12 +685,8 @@ describe Puppet::Node::Catalog, " when creating a relationship graph" do @relationships = @catalog.relationship_graph end - it "should fail when trying to create a relationship graph for a relationship graph" do - proc { @relationships.relationship_graph }.should raise_error(Puppet::DevError) - end - it "should be able to create a relationship graph" do - @relationships.should be_instance_of(Puppet::Node::Catalog) + @relationships.should be_instance_of(Puppet::SimpleGraph) end it "should copy its host_config setting to the relationship graph" do @@ -810,6 +806,7 @@ describe Puppet::Node::Catalog, " when writing dot files" do @name = :test @file = File.join(Puppet[:graphdir], @name.to_s + ".dot") end + it "should only write when it is a host catalog" do File.expects(:open).with(@file).never @catalog.host_config = false @@ -817,21 +814,6 @@ describe Puppet::Node::Catalog, " when writing dot files" do @catalog.write_graph(@name) end - it "should only write when graphing is enabled" do - File.expects(:open).with(@file).never - @catalog.host_config = true - Puppet[:graph] = false - @catalog.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)) - @catalog.expects(:to_dot).with("name" => @name.to_s.capitalize) - @catalog.host_config = true - Puppet[:graph] = true - @catalog.write_graph(@name) - end - after do Puppet.settings.clear end diff --git a/spec/unit/other/pgraph.rb b/spec/unit/other/pgraph.rb deleted file mode 100755 index cad0832a5..000000000 --- a/spec/unit/other/pgraph.rb +++ /dev/null @@ -1,210 +0,0 @@ -#!/usr/bin/env ruby -# -# Created by Luke Kanies on 2007-9-12. -# Copyright (c) 2006. All rights reserved. - -require File.dirname(__FILE__) + '/../../spec_helper' - -require 'puppet/pgraph' -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 Puppet::PGraph do - before do - @graph = Puppet::PGraph.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 Puppet::PGraph, " when matching edges" do - before do - @graph = Puppet::PGraph.new - @event = Puppet::Transaction::Event.new(:yay, "a") - @none = Puppet::Transaction::Event.new(:NONE, "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 Puppet::PGraph, " when determining dependencies" do - before do - @graph = Puppet::PGraph.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 - -describe Puppet::PGraph, " when splicing the relationship 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", []) - - @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::PGraph.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 - - 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 no longer contain anything but the non-container objects" do - @depgraph.vertices.find_all { |v| ! v.is_a?(String) }.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.edge_label("c", "i").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.edge_label("c", "i").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.edge_label("c", "i").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.edge_label(edge.source, edge.target).should == {:callback => :refresh} - end - end -end diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb index 322a527f1..a73e75a42 100755 --- a/spec/unit/simple_graph.rb +++ b/spec/unit/simple_graph.rb @@ -30,276 +30,491 @@ describe Puppet::SimpleGraph do proc { @graph.to_dot_graph }.should_not raise_error end -end -describe Puppet::SimpleGraph, " when managing vertices" do - before do - @graph = Puppet::SimpleGraph.new - 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 provide a method to add a vertex" do + @graph.add_vertex(:test) + @graph.vertex?(:test).should be_true + 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 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 return true when asked if a vertex is present" do - @graph.add_vertex(:test) - @graph.vertex?(:test).should be_true - 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 false when asked if a non-vertex is present" do - @graph.vertex?(:test).should be_false - 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 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 return false when asked if a non-vertex is present" do + @graph.vertex?(:test).should be_false + 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 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 do nothing when a non-vertex is asked to be removed" do - proc { @graph.remove_vertex!(:one) }.should_not raise_error - end -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 -describe Puppet::SimpleGraph, " when managing edges" do - before do - @graph = Puppet::SimpleGraph.new + 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 - it "should provide a method to test whether a given vertex pair is an edge" do - @graph.should respond_to(:edge?) - end + describe "when managing edges" do + before do + @graph = Puppet::SimpleGraph.new + 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 test whether a given vertex pair is an edge" do + @graph.should respond_to(:edge?) + 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 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 by specifying the two vertices and a label" do - @graph.add_edge(:one, :two, :stuff => :awesome) - @graph.edge?(:one, :two).should be_true - 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 for retrieving an edge label" do - edge = Puppet::Relationship.new(:one, :two, :stuff => :awesome) - @graph.add_edge(edge) - @graph.edge_label(:one, :two).should == {:stuff => :awesome} - 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 for retrieving an edge" do - edge = Puppet::Relationship.new(:one, :two) - @graph.add_edge(edge) - @graph.edge(:one, :two).should equal(edge) - end + it "should provide a method to add an edge by specifying the two vertices and a label" do + @graph.add_edge(:one, :two, :stuff => :awesome) + @graph.edge?(:one, :two).should be_true + 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 provide a method for retrieving an edge label" do + edge = Puppet::Relationship.new(:one, :two, :stuff => :awesome) + @graph.add_edge(edge) + @graph.edge_label(:one, :two).should == {:stuff => :awesome} + 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 provide a method for retrieving an edge" do + edge = Puppet::Relationship.new(:one, :two) + @graph.add_edge(edge) + @graph.edge(:one, :two).should equal(edge) + 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.length.should == 2 - edges.should include(one) - edges.should include(two) - 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 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 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 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 + 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.length.should == 2 + edges.should include(one) + edges.should include(two) + end -describe Puppet::SimpleGraph, " 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 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 return adjacent vertices" do - adj = @graph.adjacent(:one) - adj.should be_include(:three) - adj.should be_include(:two) + 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 - it "should default to finding :out vertices" do - @graph.adjacent(:two).should == [:three] - 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 support selecting :in vertices" do - @graph.adjacent(:two, :direction => :in).should == [:one] - 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 returning the matching vertices as an array of vertices" do - @graph.adjacent(:two).should == [:three] - end + it "should default to finding :out 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 -end + it "should support selecting :in vertices" do + @graph.adjacent(:two, :direction => :in).should == [:one] + end -describe Puppet::SimpleGraph, " 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) + it "should default to returning the matching vertices as an array of vertices" do + @graph.adjacent(:two).should == [:three] + end - @graph.clear + it "should support returning an array of matching edges" do + @graph.adjacent(:two, :type => :edges).should == [@two_three] + end end - it "should remove all vertices" do - @graph.vertices.should be_empty - 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) - it "should remove all edges" do - @graph.edges.should be_empty - end -end + @graph.clear + end -describe Puppet::SimpleGraph, " when reversing graphs" do - before do - @graph = Puppet::SimpleGraph.new - end + it "should remove all vertices" do + @graph.vertices.should be_empty + end - it "should provide a method for reversing the graph" do - @graph.add_edge(:one, :two) - @graph.reversal.edge?(:two, :one).should be_true + it "should remove all edges" do + @graph.edges.should be_empty + end 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, :stuff => :awesome) - edge = @graph.reversal.edge(:two, :one) - edge.label.should == {:stuff => :awesome} - end -end + describe "when reversing graphs" do + before do + @graph = Puppet::SimpleGraph.new + end -describe Puppet::SimpleGraph, " when sorting the graph" 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 - def add_edges(hash) - hash.each do |a,b| - @graph.add_edge(a, b) + 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, :stuff => :awesome) + edge = @graph.reversal.edge(:two, :one) + edge.label.should == {:stuff => :awesome} end end - it "should sort the graph topologically" do - add_edges :a => :b, :b => :c - @graph.topsort.should == [:a, :b, :c] - end + describe "when sorting the graph" do + before do + @graph = Puppet::SimpleGraph.new + end - it "should fail on two-vertex loops" do - add_edges :a => :b, :b => :a - proc { @graph.topsort }.should raise_error(Puppet::Error) - end + def add_edges(hash) + hash.each do |a,b| + @graph.add_edge(a, b) + end + 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 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 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) + # 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 - 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 + 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 - # 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 + 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 -end -describe Puppet::SimpleGraph, " when writing dot files" do - before do - @graph = Puppet::SimpleGraph.new - @name = :test - @file = File.join(Puppet[:graphdir], @name.to_s + ".dot") + describe "when matching edges" do + before do + @graph = Puppet::SimpleGraph.new + @event = Puppet::Transaction::Event.new(:yay, "a") + @none = Puppet::Transaction::Event.new(:NONE, "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 - it "should only write when graphing is enabled" do - File.expects(:open).with(@file).never - Puppet[:graph] = false - @graph.write_graph(@name) + 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 - 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) + 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 - after do - Puppet.settings.clear + 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", []) + + @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 + + 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 no longer contain anything but the non-container objects" do + @depgraph.vertices.find_all { |v| ! v.is_a?(String) }.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.edge_label("c", "i").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.edge_label("c", "i").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.edge_label("c", "i").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.edge_label(edge.source, edge.target).should == {:callback => :refresh} + end + end end end |