(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

1 files changed, 63 insertions, 1 deletions

diff --git a/lib/puppet/resource/catalog.rb b/lib/puppet/resource/catalog.rb
index fed0f46da..98c29657e 100644
--- a/lib/puppet/resource/catalog.rb
+++ b/lib/puppet/resource/catalog.rb
@@ -331,13 +331,75 @@ class Puppet::Resource::Catalog < Puppet::SimpleGraph
       @relationship_graph.write_graph(:relationships) if host_config?
 
       # Then splice in the container information
-      @relationship_graph.splice!(self, Puppet::Type::Component)
+      splice!(@relationship_graph)
 
       @relationship_graph.write_graph(:expanded_relationships) if host_config?
     end
     @relationship_graph
   end
 
+  # Impose our container information on another graph by using it 
+  # to replace any container vertices X with a pair of verticies 
+  # { 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 depens 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, but has the advantage
+  # that the number of new edges created scales linearly with the number
+  # of contained verticies regardless of how containers are related; 
+  # alternatives such as replacing container-edges with content-edges 
+  # scale as the product of the number of external dependences, which is
+  # to say geometrically in the case of nested / chained containers.
+  #
+  Default_label = { :callback => :refresh, :event => :ALL_EVENTS }
+  def splice!(other)
+    stage_class      = Puppet::Type.type(:stage)
+    whit_class       = Puppet::Type.type(:whit)
+    component_class  = Puppet::Type.type(:component)
+    containers = vertices.find_all { |v| (v.is_a?(component_class) or v.is_a?(stage_class)) and vertex?(v) }
+    #
+    # These two hashes comprise the aforementioned attention to the possible
+    #   case of containers that contain / depend on other containers; they map
+    #   containers to their sentinals but pass other verticies through.  Thus we
+    #   can "do the right thing" for references to other verticies that may or
+    #   may not be containers.
+    #
+    admissible = Hash.new { |h,k| k }
+    completed  = Hash.new { |h,k| k }
+    containers.each { |x|
+      admissible[x] = whit_class.new(:name => "admissible_#{x.name}", :catalog => self)
+      completed[x]  = whit_class.new(:name => "completed_#{x.name}",  :catalog => self)
+    }
+    #
+    # Implement the six requierments listed above
+    #
+    containers.each { |x|
+      contents = adjacent(x, :direction => :out)
+      other.add_edge(admissible[x],completed[x]) if contents.empty? # (0)
+      contents.each { |v|
+        other.add_edge(admissible[x],admissible[v],Default_label) # (1)
+        other.add_edge(completed[v], completed[x], Default_label) # (2)
+      }
+      # (3) & (5)
+      other.adjacent(x,:direction => :in,:type => :edges).each { |e|
+        other.add_edge(completed[e.source],admissible[x],e.label)
+        other.remove_edge! e
+      }
+      # (4) & (5)
+      other.adjacent(x,:direction => :out,:type => :edges).each { |e|
+        other.add_edge(completed[x],admissible[e.target],e.label)
+        other.remove_edge! e
+      }
+    }
+    containers.each { |x| other.remove_vertex! x } # (5)
+  end
+
   # Remove the resource from our catalog.  Notice that we also call
   # 'remove' on the resource, at least until resource classes no longer maintain
   # references to the resource instances.