(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

15 files changed, 280 insertions, 283 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
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
diff --git a/test/lib/puppettest/support/assertions.rb b/test/lib/puppettest/support/assertions.rb
index 31fa3f1da..758c126ce 100644
--- a/test/lib/puppettest/support/assertions.rb
+++ b/test/lib/puppettest/support/assertions.rb
@@ -46,7 +46,12 @@ module PuppetTest
     config = resources2catalog(*resources)
     transaction = Puppet::Transaction.new(config)
 
-    run_events(:evaluate, transaction, events, msg)
+    transaction.evaluate
+    newevents = transaction.events.
+      reject { |e| ['failure', 'audit'].include? e.status }.
+      collect { |e| e.name }
+
+    assert_equal(events, newevents, "Incorrect evaluate #{msg} events")
 
     transaction
   end
diff --git a/test/lib/puppettest/support/utils.rb b/test/lib/puppettest/support/utils.rb
index bca5d9634..4ecc3819e 100644
--- a/test/lib/puppettest/support/utils.rb
+++ b/test/lib/puppettest/support/utils.rb
@@ -82,25 +82,6 @@ module PuppetTest::Support::Utils
     @mygroup = group
   end
 
-  def run_events(type, trans, events, msg)
-    case type
-    when :evaluate, :rollback # things are hunky-dory
-    else
-      raise Puppet::DevError, "Incorrect run_events type"
-    end
-
-    method = type
-
-    trans.send(method)
-    newevents = trans.events.reject { |e| ['failure', 'audit'].include? e.status }.collect { |e|
-      e.name
-    }
-
-    assert_equal(events, newevents, "Incorrect #{type} #{msg} events")
-
-    trans
-  end
-
   def fakefile(name)
     ary = [basedir, "test"]
     ary += name.split("/")
diff --git a/test/other/relationships.rb b/test/other/relationships.rb
index 717353c02..e36dcda71 100755
--- a/test/other/relationships.rb
+++ b/test/other/relationships.rb
@@ -14,11 +14,8 @@ class TestRelationships < Test::Unit::TestCase
 
   def newfile
     assert_nothing_raised {
-
-            return Puppet::Type.type(:file).new(
-                
+      return Puppet::Type.type(:file).new(
         :path => tempfile,
-        
         :check => [:mode, :owner, :group]
       )
     }
@@ -58,18 +55,14 @@ class TestRelationships < Test::Unit::TestCase
   def test_autorequire
     # We know that execs autorequire their cwd, so we'll use that
     path = tempfile
-
-
-          file = Puppet::Type.type(:file).new(
-        :title => "myfile", :path => path,
-        
-      :ensure => :directory)
-
-          exec = Puppet::Type.newexec(
-        :title => "myexec", :cwd => path,
-        
-      :command => "/bin/echo")
-
+    file = Puppet::Type.type(:file).new(
+      :title => "myfile", :path => path,
+      :ensure => :directory
+    )
+    exec = Puppet::Type.newexec(
+      :title => "myexec", :cwd => path,
+      :command => "/bin/echo"
+    )
     catalog = mk_catalog(file, exec)
     reqs = nil
     assert_nothing_raised do
@@ -82,7 +75,7 @@ class TestRelationships < Test::Unit::TestCase
     # Now make sure that these relationships are added to the
     # relationship graph
     catalog.apply do |trans|
-      assert(catalog.relationship_graph.edge?(file, exec), "autorequire edge was not created")
+      assert(catalog.relationship_graph.path_between(file, exec), "autorequire edge was not created")
     end
   end
 
diff --git a/test/other/transactions.rb b/test/other/transactions.rb
index be8cef483..812e519ab 100755
--- a/test/other/transactions.rb
+++ b/test/other/transactions.rb
@@ -114,39 +114,6 @@ class TestTransactions < Test::Unit::TestCase
     assert_equal({inst.title => inst}, $prefetched, "evaluate did not call prefetch")
   end
 
-  # We need to generate resources before we prefetch them, else generated
-  # resources that require prefetching don't work.
-  def test_generate_before_prefetch
-    config = mk_catalog
-    trans = Puppet::Transaction.new(config)
-
-    generate = nil
-    prefetch = nil
-    trans.expects(:generate).with { |*args| generate = Time.now; true }
-    trans.expects(:prefetch).with { |*args| ! generate.nil? }
-    trans.prepare
-    return
-
-    resource = Puppet::Type.type(:file).new :ensure => :present, :path => tempfile
-    other_resource = mock 'generated'
-    def resource.generate
-      [other_resource]
-    end
-
-
-    config = mk_catalog(yay, rah)
-    trans = Puppet::Transaction.new(config)
-
-    assert_nothing_raised do
-      trans.generate
-    end
-
-    %w{ya ra y r}.each do |name|
-      assert(trans.catalog.vertex?(Puppet::Type.type(:generator)[name]), "Generated #{name} was not a vertex")
-      assert($finished.include?(name), "#{name} was not finished")
-    end
-  end
-
   def test_ignore_tags?
     config = Puppet::Resource::Catalog.new
     config.host_config = true
@@ -235,7 +202,7 @@ class TestTransactions < Test::Unit::TestCase
     config = mk_catalog(one, two)
     trans = Puppet::Transaction.new(config)
     assert_raise(Puppet::Error) do
-      trans.prepare
+      trans.evaluate
     end
   end
 
diff --git a/test/ral/type/file/target.rb b/test/ral/type/file/target.rb
index 272128586..d778f2891 100755
--- a/test/ral/type/file/target.rb
+++ b/test/ral/type/file/target.rb
@@ -24,12 +24,9 @@ class TestFileTarget < Test::Unit::TestCase
 
     file = nil
     assert_nothing_raised {
-
-            file = Puppet::Type.type(:file).new(
-                
+      file = Puppet::Type.type(:file).new(
         :title => "somethingelse",
         :ensure => path,
-        
         :path => link
       )
     }
@@ -102,12 +99,9 @@ class TestFileTarget < Test::Unit::TestCase
 
     link = nil
     assert_nothing_raised {
-
-            link = Puppet::Type.type(:file).new(
-                
+      link = Puppet::Type.type(:file).new(
         :ensure => source,
         :path => dest,
-        
         :recurse => true
       )
     }
@@ -140,11 +134,8 @@ class TestFileTarget < Test::Unit::TestCase
 
     link = nil
     assert_nothing_raised {
-
-            link = Puppet::Type.type(:file).new(
-                
+      link = Puppet::Type.type(:file).new(
         :path => dest,
-        
         :ensure => "source"
       )
     }
@@ -161,20 +152,16 @@ class TestFileTarget < Test::Unit::TestCase
 
     resources = []
 
-          resources << Puppet::Type.type(:exec).new(
-                
+    resources << Puppet::Type.type(:exec).new(
       :command => "mkdir #{source}; touch #{source}/file",
       :title => "yay",
-        
       :path => ENV["PATH"]
     )
 
-          resources << Puppet::Type.type(:file).new(
-                
+    resources << Puppet::Type.type(:file).new(
       :ensure => source,
       :path => dest,
       :recurse => true,
-        
       :require => resources[0]
     )