(5200) -- replace containers with sentinals

This commit removes the last remaining use of topsort (in SimpleGraph#splice!) by
fixing #5200 in a way that is compatible with graph fontiers.  Instead of replacing
containers with many-to-many relationships, we now replace them with a pair of
sentinals (whits) that bracket them.

Thus a graph consisting of two containers, each containing ten resources, and a
dependency between the containers, which would have gone from 21 edges to 100
edges will instead have only 43, and a graph consisting of two containers (e.g.
stages) each containing a similar graph, which would have gone from 45 edges to
400 will only go to 95.

This change had minor consequences on many parts of the system and required lots
of small changes for consistancy, but the core of it is in Catelog#splice! (which
replaces SimpleGraph#splice!) and Transaction#eval_generate.  Everything else is
just adjustments to the fact that some one-step edges are now two-step edges and
tests, event propagation, etc. need to reflect that.

Paired-with: Jesse Wolfe

5 files changed, 125 insertions, 84 deletions

diff --git a/spec/unit/parser/functions/create_resources_spec.rb b/spec/unit/parser/functions/create_resources_spec.rb
index d4095b777..366fb536c 100755
--- a/spec/unit/parser/functions/create_resources_spec.rb
+++ b/spec/unit/parser/functions/create_resources_spec.rb
@@ -51,11 +51,12 @@ describe 'function for dynamically creating resources' do
     it 'should be able to add edges' do
       @scope.function_create_resources(['notify', {'foo'=>{'require' => 'Notify[test]'}}])
       @scope.compiler.compile
-      edge = @scope.compiler.catalog.to_ral.relationship_graph.edges.detect do |edge|
-        edge.source.title == 'test'
-      end
-      edge.source.title.should == 'test'
-      edge.target.title.should == 'foo'
+      rg = @scope.compiler.catalog.to_ral.relationship_graph
+      test  = rg.vertices.find { |v| v.title == 'test' }
+      foo   = rg.vertices.find { |v| v.title == 'foo' }
+      test.should be
+      foo.should be
+      rg.path_between(test,foo).should be
     end
   end
   describe 'when dynamically creating resource types' do
@@ -93,11 +94,13 @@ notify{test:}
     it 'should be able to add edges' do
       @scope.function_create_resources(['foo', {'blah'=>{'one'=>'two', 'require' => 'Notify[test]'}}])
       @scope.compiler.compile
-      edge = @scope.compiler.catalog.to_ral.relationship_graph.edges.detect do |edge|
-        edge.source.title == 'test'
-      end
-      edge.source.title.should == 'test'
-      edge.target.title.should == 'blah'
+      rg = @scope.compiler.catalog.to_ral.relationship_graph
+      test = rg.vertices.find { |v| v.title == 'test' }
+      blah = rg.vertices.find { |v| v.title == 'blah' }
+      test.should be
+      blah.should be
+      # (Yoda speak like we do)
+      rg.path_between(test,blah).should be
       @compiler.catalog.resource(:notify, "blah")['message'].should == 'two'
     end
   end
@@ -123,13 +126,12 @@ notify{tester:}
     it 'should be able to add edges' do
       @scope.function_create_resources(['class', {'bar'=>{'one'=>'two', 'require' => 'Notify[tester]'}}])
       @scope.compiler.compile
-      edge = @scope.compiler.catalog.to_ral.relationship_graph.edges.detect do |e|
-        e.source.title == 'tester'
-      end
-      edge.source.title.should == 'tester'
-      edge.target.title.should == 'test'
-      #@compiler.catalog.resource(:notify, "blah")['message'].should == 'two'
+      rg = @scope.compiler.catalog.to_ral.relationship_graph
+      test   = rg.vertices.find { |v| v.title == 'test' }
+      tester = rg.vertices.find { |v| v.title == 'tester' }
+      test.should be
+      tester.should be
+      rg.path_between(tester,test).should be
     end
-
   end
 end
diff --git a/spec/unit/resource/catalog_spec.rb b/spec/unit/resource/catalog_spec.rb
index 411d10b32..78d1b3223 100755
--- a/spec/unit/resource/catalog_spec.rb
+++ b/spec/unit/resource/catalog_spec.rb
@@ -734,7 +734,7 @@ describe Puppet::Resource::Catalog, "when compiling" do
     end
 
     it "should copy component relationships to all contained resources" do
-      @relationships.edge?(@one, @two).should be_true
+      @relationships.path_between(@one, @two).should be
     end
 
     it "should add automatic relationships to the relationship graph" do
diff --git a/spec/unit/simple_graph_spec.rb b/spec/unit/simple_graph_spec.rb
index c106f550b..99db2a55c 100755
--- a/spec/unit/simple_graph_spec.rb
+++ b/spec/unit/simple_graph_spec.rb
@@ -267,7 +267,7 @@ describe Puppet::SimpleGraph do
     end
   end
 
-  describe "when sorting the graph" do
+  describe "when reporting cycles in the graph" do
     before do
       @graph = Puppet::SimpleGraph.new
     end
@@ -278,29 +278,24 @@ describe Puppet::SimpleGraph do
       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)
+      proc { @graph.report_cycles_in_graph }.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)
+      proc { @graph.report_cycles_in_graph }.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)
+      proc { @graph.report_cycles_in_graph }.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
+      proc { @graph.report_cycles_in_graph }.should_not raise_error
     end
 
     it "should produce the correct relationship text" do
@@ -308,7 +303,7 @@ describe Puppet::SimpleGraph do
       # 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}
-      expect { @graph.topsort }.to raise_error(Puppet::Error, want)
+      expect { @graph.report_cycles_in_graph }.to raise_error(Puppet::Error, want)
     end
 
     it "cycle discovery should be the minimum cycle for a simple graph" do
@@ -405,17 +400,6 @@ describe Puppet::SimpleGraph do
       paths = @graph.paths_in_cycle(cycles.first, 21)
       paths.length.should be == 20
     end
-
-    # Our graph's add_edge method is smart enough not to add
-    # duplicate edges, so we use the objects, which it doesn't
-    # check.
-    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
@@ -521,7 +505,7 @@ describe Puppet::SimpleGraph do
 
   require 'puppet/util/graph'
 
-  class Container
+  class Container < Puppet::Type::Component
     include Puppet::Util::Graph
     include Enumerable
     attr_accessor :name
@@ -543,6 +527,7 @@ describe Puppet::SimpleGraph do
     end
   end
 
+  require "puppet/resource/catalog"
   describe "when splicing the graph" do
     def container_graph
       @one = Container.new("one", %w{a b})
@@ -555,13 +540,21 @@ describe Puppet::SimpleGraph do
       @whit  = Puppet::Type.type(:whit)
       @stage = Puppet::Type.type(:stage).new(:name => "foo")
 
-      @contgraph = @top.to_graph
+      @contgraph = @top.to_graph(Puppet::Resource::Catalog.new)
 
       # 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 containers
+      @contgraph.vertices.select { |x| !x.is_a? String }
+    end
+
+    def contents_of(x)
+      @contgraph.direct_dependents_of(x)
+    end
+
     def dependency_graph
       @depgraph = Puppet::SimpleGraph.new
       @contgraph.vertices.each do |v|
@@ -570,13 +563,34 @@ describe Puppet::SimpleGraph do
 
       # 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|
+      @explicit_dependencies = {@one => @two, "f" => "c", "h" => @middle, "c" => @empty}
+      @explicit_dependencies.each do |source, target|
         @depgraph.add_edge(source, target, :callback => :refresh)
       end
     end
 
     def splice
-      @depgraph.splice!(@contgraph, Container)
+      @contgraph.splice!(@depgraph)
+    end
+
+    def whit_called(name)
+      x = @depgraph.vertices.find { |v| v.is_a?(@whit) && v.name =~ /#{name}/ }
+      x.should_not be_nil
+      def x.to_s
+        "Whit[#{name}]"
+      end
+      def x.inspect
+        to_s
+      end
+      x
+    end
+
+    def admissible_sentinal_of(x)
+      @depgraph.vertex?(x) ? x : whit_called("admissible_#{x.name}")
+    end
+
+    def completed_sentinal_of(x)
+      @depgraph.vertex?(x) ? x : whit_called("completed_#{x.name}")
     end
 
     before do
@@ -585,63 +599,87 @@ describe Puppet::SimpleGraph do
       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.
+    # This is the real heart of splicing -- replacing all containers X in our
+    # relationship graph with a pair of whits { admissible_X and completed_X }
+    # such that that
+    #
+    #    0) completed_X depends on admissible_X
+    #    1) contents of X each depend on admissible_X
+    #    2) completed_X depends on each on the contents of X
+    #    3) everything which depended on X depends on completed_X
+    #    4) admissible_X depends on everything X depended on
+    #    5) the containers and their edges must be removed
+    #
+    # Note that this requires attention to the possible case of containers
+    # which contain or depend on other containers.
+    #
+    # Point by point:
+
+    #    0) completed_X depends on admissible_X
+    #
+    it "every container's completed sentinal should depend on its admissible sentinal" do
+      containers.each { |container| 
+        @depgraph.path_between(admissible_sentinal_of(container),completed_sentinal_of(container)).should be
+      }
+    end
+
+    #    1) contents of X each depend on admissible_X
+    #
+    it "all contained objects should depend on their container's admissible sentinal" do
+      containers.each { |container| 
+        contents_of(container).each { |leaf|
+          @depgraph.should be_edge(admissible_sentinal_of(container),admissible_sentinal_of(leaf))
+        }
+      }
+    end
+
+    #    2) completed_X depends on each on the contents of X
+    #
+    it "completed sentinals should depend on their container's contents" do
+      containers.each { |container| 
+        contents_of(container).each { |leaf|
+          @depgraph.should be_edge(completed_sentinal_of(leaf),completed_sentinal_of(container))
+        }
+      }
+    end
+
+    #
+    #    3) everything which depended on X depends on completed_X
+
+    #
+    #    4) admissible_X depends on everything X depended on
+
+    #    5) the containers and their edges must be removed
+    #
     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
+    it "should retain labels on non-containment edges" do
+      @explicit_dependencies.each { |f,t|
+        @depgraph.edges_between(completed_sentinal_of(f),admissible_sentinal_of(t))[0].label.should == {:callback => :refresh}
+      }
     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 == {}
+      @depgraph.path_between("c", "i").any? {|segment| segment.all? {|e| e.label == {} }}.should be
     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}
+      @depgraph.path_between("c", "i").flatten.select {|e| e.label == {:callback => :refresh} }.should_not be_empty
     end
 
     it "should not replace a label with a nil label" do
@@ -649,7 +687,7 @@ describe Puppet::SimpleGraph do
       @depgraph.add_edge(@middle, @three)
       @depgraph.add_edge("c", @three, {:callback => :refresh})
       splice
-      @depgraph.edges_between("c", "i")[0].label.should == {:callback => :refresh}
+      @depgraph.path_between("c","i").flatten.select {|e| e.label == {:callback => :refresh} }.should_not be_empty
     end
 
     it "should copy labels to all created edges" do
@@ -658,8 +696,9 @@ describe Puppet::SimpleGraph do
       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}
+        (path = @depgraph.path_between(edge.source, edge.target)).should be
+        path.should_not be_empty
+        path.flatten.select {|e| e.label == {:callback => :refresh} }.should_not be_empty
       end
     end
   end
diff --git a/spec/unit/transaction_spec.rb b/spec/unit/transaction_spec.rb
index 8d40136fb..ab76130e3 100755
--- a/spec/unit/transaction_spec.rb
+++ b/spec/unit/transaction_spec.rb
@@ -223,7 +223,7 @@ describe Puppet::Transaction do
       resource.expects(:finish).never
       resource.expects(:info) # log that it's skipped
 
-      @transaction.generate_additional_resources(generator).should be_empty
+      @transaction.generate_additional_resources(generator)
     end
 
     it "should copy all tags to the newly generated resources" do
diff --git a/spec/unit/type/whit_spec.rb b/spec/unit/type/whit_spec.rb
index 46eb0ab6e..0a3324afa 100644
--- a/spec/unit/type/whit_spec.rb
+++ b/spec/unit/type/whit_spec.rb
@@ -5,7 +5,7 @@ require File.expand_path(File.dirname(__FILE__) + '/../../spec_helper')
 whit = Puppet::Type.type(:whit).new(:name => "Foo::Bar")
 
 describe whit do
-  it "should stringify as though it were the class it represents" do
-    whit.to_s.should == "Class[Foo::Bar]"
+  it "should stringify in a way that users will regognise" do
+    whit.to_s.should == "(Foo::Bar)"
   end
 end