(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, 133 insertions, 110 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.
diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index 31858f136..671eef150 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -19,7 +19,7 @@ class Puppet::SimpleGraph
   #
   # 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.
+  # algorithms.  
   #
   def initialize
     @in_to = {}
@@ -221,6 +221,7 @@ class Puppet::SimpleGraph
   def report_cycles_in_graph
     cycles = find_cycles_in_graph
     n = cycles.length           # where is "pluralize"? --daniel 2011-01-22
+    return if n == 0
     s = n == 1 ? '' : 's'
 
     message = "Found #{n} dependency cycle#{s}:\n"
@@ -262,36 +263,6 @@ class Puppet::SimpleGraph
     return filename
   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
-      report_cycles_in_graph
-    end
-
-    result
-  end
-
   # Add a new vertex to the graph.
   def add_vertex(vertex)
     @in_to[vertex]    ||= {}
@@ -368,52 +339,6 @@ class Puppet::SimpleGraph
     (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
@@ -454,7 +379,7 @@ class Puppet::SimpleGraph
   end
 
   def direct_dependents_of(v)
-    @out_from[v].keys 
+    (@out_from[v] || {}).keys 
   end
 
   def upstream_from_vertex(v)
@@ -468,7 +393,33 @@ class Puppet::SimpleGraph
   end
 
   def direct_dependencies_of(v)
-    @in_to[v].keys 
+    (@in_to[v] || {}).keys 
+  end
+
+  # Return an array of the edge-sets between a series of n+1 vertices (f=v0,v1,v2...t=vn)
+  #   connecting the two given verticies.  The ith edge set is an array containing all the
+  #   edges between v(i) and v(i+1); these are (by definition) never empty.
+  #
+  #     * if f == t, the list is empty
+  #     * if they are adjacent the result is an array consisting of
+  #       a single array (the edges from f to t)
+  #     * and so on by induction on a vertex m between them
+  #     * if there is no path from f to t, the result is nil
+  #
+  # This implementation is not particularly efficient; it's used in testing where clarity
+  #   is more important than last-mile efficiency. 
+  #
+  def path_between(f,t)
+    if f==t
+      []
+    elsif direct_dependents_of(f).include?(t)
+      [edges_between(f,t)]
+    elsif dependents(f).include?(t)
+      m = (dependents(f) & direct_dependencies_of(t)).first
+      path_between(f,m) + path_between(m,t)
+    else
+      nil
+    end
   end
 
   # LAK:FIXME This is just a paste of the GRATR code with slight modifications.
diff --git a/lib/puppet/transaction.rb b/lib/puppet/transaction.rb
index c502fc627..8118178c3 100644
--- a/lib/puppet/transaction.rb
+++ b/lib/puppet/transaction.rb
@@ -65,13 +65,13 @@ class Puppet::Transaction
 
   # Copy an important relationships from the parent to the newly-generated
   # child resource.
-  def make_parent_child_relationship(parent, child)
+  def add_conditional_directed_dependency(parent, child, label=nil)
     relationship_graph.add_vertex(child)
     edge = parent.depthfirst? ? [child, parent] : [parent, child]
     if relationship_graph.edge?(*edge.reverse)
       parent.debug "Skipping automatic relationship to #{child}"
     else
-      relationship_graph.add_edge(*edge)
+      relationship_graph.add_edge(edge[0],edge[1],label)
     end
   end
 
@@ -141,66 +141,65 @@ class Puppet::Transaction
   end
 
   def eval_generate(resource)
-    return [] unless resource.respond_to?(:eval_generate)
+    raise Puppet::DevError,"Depthfirst resources are not supported by eval_generate" if resource.depthfirst?
     begin
-      made = resource.eval_generate
+      made = resource.eval_generate.uniq.reverse
     rescue => detail
       puts detail.backtrace if Puppet[:trace]
       resource.err "Failed to generate additional resources using 'eval_generate: #{detail}"
+      return
     end
-    parents = [resource]
-    [made].flatten.compact.uniq.each do |res|
+    made.each do |res|
       begin
         res.tag(*resource.tags)
         @catalog.add_resource(res)
         res.finish
-        make_parent_child_relationship(parents.reverse.find { |r| r.name == res.name[0,r.name.length]}, res)
-        parents << res
       rescue Puppet::Resource::Catalog::DuplicateResourceError
         res.info "Duplicate generated resource; skipping"
       end
     end
+    sentinal = Puppet::Type::Whit.new(:name => "completed_#{resource.title}", :catalog => resource.catalog)
+    relationship_graph.adjacent(resource,:direction => :out,:type => :edges).each { |e|
+      add_conditional_directed_dependency(sentinal, e.target, e.label)
+      relationship_graph.remove_edge! e
+    }
+    default_label = Puppet::Resource::Catalog::Default_label
+    made.each do |res|
+      add_conditional_directed_dependency(made.find { |r| r != res && r.name == res.name[0,r.name.length]} || resource, res)
+      add_conditional_directed_dependency(res, sentinal, default_label)
+    end
+    add_conditional_directed_dependency(resource, sentinal, default_label)
   end
 
   # A general method for recursively generating new resources from a
   # resource.
   def generate_additional_resources(resource)
-    return [] unless resource.respond_to?(:generate)
+    return unless resource.respond_to?(:generate)
     begin
       made = resource.generate
     rescue => detail
       puts detail.backtrace if Puppet[:trace]
       resource.err "Failed to generate additional resources using 'generate': #{detail}"
     end
-    return [] unless made
+    return unless made
     made = [made] unless made.is_a?(Array)
-    made.uniq.find_all do |res|
+    made.uniq.each do |res|
       begin
         res.tag(*resource.tags)
         @catalog.add_resource(res)
         res.finish
-        make_parent_child_relationship(resource, res)
+        add_conditional_directed_dependency(resource, res)
         generate_additional_resources(res)
-        true
       rescue Puppet::Resource::Catalog::DuplicateResourceError
         res.info "Duplicate generated resource; skipping"
-        false
       end
     end
   end
 
   # Collect any dynamically generated resources.  This method is called
   # before the transaction starts.
-  def generate
-    list = @catalog.vertices
-    newlist = []
-    while ! list.empty?
-      list.each do |resource|
-        newlist += generate_additional_resources(resource)
-      end
-      list = newlist
-      newlist = []
-    end
+  def xgenerate
+    @catalog.vertices.each { |resource| generate_additional_resources(resource) }
   end
 
   # Should we ignore tags?
@@ -246,7 +245,7 @@ class Puppet::Transaction
   # Prepare to evaluate the resources in a transaction.
   def prepare
     # Now add any dynamically generated resources
-    generate
+    xgenerate
 
     # Then prefetch.  It's important that we generate and then prefetch,
     # so that any generated resources also get prefetched.
@@ -285,10 +284,11 @@ class Puppet::Transaction
     end
     def add_vertex(v)
       real_graph.add_vertex(v)
+      check_if_now_ready(v) # ?????????????????????????????????????????
     end
-    def add_edge(f,t)
+    def add_edge(f,t,label=nil)
       ready.delete(t)
-      real_graph.add_edge(f,t)
+      real_graph.add_edge(f,t,label)
     end
     def check_if_now_ready(r)
       ready[r] = true if direct_dependencies_of(r).all? { |r2| done[r2] }
@@ -297,8 +297,9 @@ class Puppet::Transaction
       ready.keys.sort_by { |r0| unguessable_deterministic_key[r0] }.first
     end
     def traverse(&block)
+      real_graph.report_cycles_in_graph
       while (r = next_resource) && !transaction.stop_processing?
-        if !generated[r]
+        if !generated[r] && r.respond_to?(:eval_generate)
           transaction.eval_generate(r)
           generated[r] = true
         else
diff --git a/lib/puppet/transaction/event_manager.rb b/lib/puppet/transaction/event_manager.rb
index 3ebb0a9d3..a21bbf892 100644
--- a/lib/puppet/transaction/event_manager.rb
+++ b/lib/puppet/transaction/event_manager.rb
@@ -31,7 +31,7 @@ class Puppet::Transaction::EventManager
   # Queue events for other resources to respond to.  All of these events have
   # to be from the same resource.
   def queue_events(resource, events)
-    @events += events
+    #@events += events
 
     # Do some basic normalization so we're not doing so many
     # graph queries for large sets of events.
@@ -47,12 +47,15 @@ class Puppet::Transaction::EventManager
       # Collect the targets of any subscriptions to those events.  We pass
       # the parent resource in so it will override the source in the events,
       # since eval_generated children can't have direct relationships.
+      received = (event.name != :restarted)
       relationship_graph.matching_edges(event, resource).each do |edge|
+        received ||= true unless edge.target.is_a?(Puppet::Type::Whit)
         next unless method = edge.callback
         next unless edge.target.respond_to?(method)
 
         queue_events_for_resource(resource, edge.target, method, list)
       end
+      @events << event if received
 
       queue_events_for_resource(resource, resource, :refresh, [event]) if resource.self_refresh? and ! resource.deleting?
     end
diff --git a/lib/puppet/type/whit.rb b/lib/puppet/type/whit.rb
index 55bfcfb46..55ed0386e 100644
--- a/lib/puppet/type/whit.rb
+++ b/lib/puppet/type/whit.rb
@@ -6,6 +6,12 @@ Puppet::Type.newtype(:whit) do
   end
 
   def to_s
-    "Class[#{name}]"
+    "(#{name})"
+  end
+
+  def refresh
+    # We don't do anything with them, but we need this to
+    #   show that we are "refresh aware" and not break the
+    #   chain of propogation.
   end
 end