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]
     )