Adding a to_graph method to TransBuckets, so that the buckets can directly generate a graph, rather than having to first convert to RAL types and then have them convert to a graph. This allows us to make it so components do not need a @children array at all. This was all done because I am having the "already a parent of" problem again, and I have gotten far enough that it is relatively easy to just make this problem go away once and for all.

10 files changed, 629 insertions, 337 deletions

diff --git a/lib/puppet/dsl.rb b/lib/puppet/dsl.rb
index 793578bca..795358e83 100644
--- a/lib/puppet/dsl.rb
+++ b/lib/puppet/dsl.rb
@@ -255,8 +255,7 @@ module Puppet
         def scope
             unless defined?(@scope)
                 @interp = Puppet::Parser::Interpreter.new :Code => ""
-                # Load the class, so the node object class is available.
-                require 'puppet/network/handler/node'
+                require 'puppet/node'
                 @node = Puppet::Node.new(Facter.value(:hostname))
                 @node.parameters = Facter.to_hash
                 @interp = Puppet::Parser::Interpreter.new :Code => ""
diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb
index 07bdff4bb..ddecc731d 100644
--- a/lib/puppet/pgraph.rb
+++ b/lib/puppet/pgraph.rb
@@ -19,6 +19,20 @@ class Puppet::PGraph < GRATR::Digraph
         super
     end
 
+    # Add a resource to our graph and to our resource table.
+    def add_resource(resource)
+        unless resource.respond_to?(:ref)
+            raise ArgumentError, "Can only add objects that respond to :ref"
+        end
+
+        ref = resource.ref
+        if @resource_table.include?(ref)
+            raise ArgumentError, "Resource %s is already defined" % ref
+        else
+            @resource_table[ref] = resource
+        end
+    end
+
     def add_vertex!(*args)
         @reversal = nil
         super
@@ -26,6 +40,7 @@ class Puppet::PGraph < GRATR::Digraph
     
     def clear
         @vertex_dict.clear
+        #@resource_table.clear
         if defined? @edge_number
             @edge_number.clear
         end
@@ -71,6 +86,12 @@ class Puppet::PGraph < GRATR::Digraph
     def edge_class()
         Puppet::Relationship
     end
+
+    def initialize(*args)
+        super
+        # Create a table to keep references to all of our resources.
+        @resource_table = {}
+    end
     
     # Determine all of the leaf nodes below a given vertex.
     def leaves(vertex, type = :dfs)
@@ -97,6 +118,11 @@ class Puppet::PGraph < GRATR::Digraph
             end
         end.flatten
     end
+
+    # Look a resource up by its reference (e.g., File["/etc/passwd"]).
+    def resource(ref)
+        @resource_table[ref]
+    end
     
     # Take container information from another graph and use it
     # to replace any container vertices with their respective leaves.
@@ -209,5 +235,3 @@ class Puppet::PGraph < GRATR::Digraph
         end
     end
 end
-
-# $Id$
diff --git a/lib/puppet/transportable.rb b/lib/puppet/transportable.rb
index aa7eb92f7..7a04e1f63 100644
--- a/lib/puppet/transportable.rb
+++ b/lib/puppet/transportable.rb
@@ -60,6 +60,17 @@ module Puppet
             instance_variables
         end
 
+        def to_ref
+            unless defined? @ref
+                if self.type and self.name
+                    @ref = "%s[%s]" % [self.type, self.name]
+                else
+                    @ref = nil
+                end
+            end
+            @ref
+        end
+
         def to_type(parent = nil)
             retobj = nil
             if typeklass = Puppet::Type.type(self.type)
@@ -188,6 +199,43 @@ module Puppet
             instance_variables
         end
 
+        # Create a resource graph from our structure.
+        def to_graph
+            graph = Puppet::PGraph.new
+            
+            delver = proc do |obj|
+                obj.each do |child|
+                    unless container = graph.resource(obj.to_ref)
+                        container = obj.to_type
+                        graph.add_resource container
+                    end
+                    unless resource = graph.resource(child.to_ref)
+                        resource = child.to_type
+                        graph.add_resource resource
+                    end
+                    graph.add_edge!(container, resource)
+                    if child.is_a?(self.class)
+                        delver.call(child)
+                    end
+                end
+            end
+            
+            delver.call(self)
+            
+            return graph
+        end
+
+        def to_ref
+            unless defined? @ref
+                if self.type and self.name
+                    @ref = "%s[%s]" % [self.type, self.name]
+                else
+                    @ref = nil
+                end
+            end
+            @ref
+        end
+
         def to_type(parent = nil)
             # this container will contain the equivalent of all objects at
             # this level
@@ -287,7 +335,5 @@ module Puppet
         end
 
     end
-    #------------------------------------------------------------
 end
 
-# $Id$
diff --git a/lib/puppet/type/component.rb b/lib/puppet/type/component.rb
index 5905d85ab..79afa95a7 100644
--- a/lib/puppet/type/component.rb
+++ b/lib/puppet/type/component.rb
@@ -169,6 +169,10 @@ Puppet::Type.newtype(:component) do
         end
     end
 
+    def ref
+        title
+    end
+
     # Remove an object.  The argument determines whether the object's
     # subscriptions get eliminated, too.
     def remove(rmdeps = true)
diff --git a/spec/unit/other/pgraph.rb b/spec/unit/other/pgraph.rb
new file mode 100755
index 000000000..d4af87ba0
--- /dev/null
+++ b/spec/unit/other/pgraph.rb
@@ -0,0 +1,310 @@
+#!/usr/bin/env ruby
+#
+#  Created by Luke Kanies on 2007-9-12.
+#  Copyright (c) 2006. All rights reserved.
+
+require File.dirname(__FILE__) + '/../../spec_helper'
+
+require 'puppet/util/graph'
+
+class Container
+    include Puppet::Util::Graph
+    include Enumerable
+    attr_accessor :name
+    def each
+        @children.each do |c| yield c end
+    end
+    
+    def initialize(name, ary)
+        @name = name
+        @children = ary
+    end
+    
+    def push(*ary)
+        ary.each { |c| @children.push(c)}
+    end
+    
+    def to_s
+        @name
+    end
+end
+
+describe Puppet::PGraph do
+    before do
+        @graph = Puppet::PGraph.new
+    end
+
+    it "should correctly clear vertices and edges when asked" do
+	    @graph.add_edge!("a", "b")
+	    @graph.add_vertex! "c"
+        @graph.clear
+        @graph.vertices.should be_empty
+        @graph.edges.should be_empty
+    end
+end
+
+describe Puppet::PGraph, " when matching edges" do
+    before do
+        @graph = Puppet::PGraph.new
+	    @event = Puppet::Event.new(:source => "a", :event => :yay)
+	    @none = Puppet::Event.new(:source => "a", :event => :NONE)
+
+	    @edges = {}
+	    @edges["a/b"] = Puppet::Relationship["a", "b", {:event => :yay, :callback => :refresh}]
+	    @edges["a/c"] = Puppet::Relationship["a", "c", {:event => :yay, :callback => :refresh}]
+	    @graph.add_edge!(@edges["a/b"])
+    end
+
+    it "should match edges whose source matches the source of the event" do
+	    @graph.matching_edges([@event]).should == [@edges["a/b"]]
+    end
+
+    it "should match always match nothing when the event is :NONE" do
+	    @graph.matching_edges([@none]).should be_empty
+    end
+
+    it "should match multiple edges" do
+	    @graph.add_edge!(@edges["a/c"])
+        @graph.matching_edges([@event]).sort.should == [@edges["a/b"], @edges["a/c"]].sort
+    end
+end
+
+describe Puppet::PGraph, " when determining dependencies" do
+    before do
+        @graph = Puppet::PGraph.new
+        
+        @graph.add_edge!("a", "b")
+        @graph.add_edge!("a", "c")
+        @graph.add_edge!("b", "d")
+    end
+
+    it "should find all dependents when they are on multiple levels" do
+        @graph.dependents("a").sort.should == %w{b c d}.sort
+    end
+
+    it "should find single dependents" do
+        @graph.dependents("b").sort.should == %w{d}.sort
+    end
+
+    it "should return an empty array when there are no dependents" do
+        @graph.dependents("c").sort.should == [].sort
+    end
+
+    it "should find all dependencies when they are on multiple levels" do
+        @graph.dependencies("d").sort.should == %w{a b}
+    end
+
+    it "should find single dependencies" do
+        @graph.dependencies("c").sort.should == %w{a}
+    end
+    
+    it "should return an empty array when there are no dependencies" do
+        @graph.dependencies("a").sort.should == []
+    end
+end
+
+describe Puppet::PGraph, " when splicing the relationship graph" do
+    def container_graph
+        @one = Container.new("one", %w{a b})
+        @two = Container.new("two", ["c", "d"])
+        @three = Container.new("three", ["i", "j"])
+        @middle = Container.new("middle", ["e", "f", @two])
+        @top = Container.new("top", ["g", "h", @middle, @one, @three])
+        @empty = Container.new("empty", [])
+
+        @contgraph = @top.to_graph
+
+        # 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 dependency_graph
+        @depgraph = Puppet::PGraph.new
+        @contgraph.vertices.each do |v|
+            @depgraph.add_vertex(v)
+        end
+
+        # 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|
+            @depgraph.add_edge!(source, target, :callback => :refresh)
+        end
+    end
+
+    def splice
+        @depgraph.splice!(@contgraph, Container)
+    end
+
+    before do
+        container_graph
+        dependency_graph
+        splice
+    end
+
+    it "should not create a cyclic graph" do
+        @depgraph.should_not be_cyclic
+    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.
+    it "should remove all Container objects from the dependency graph" do
+        @depgraph.vertices.find_all { |v| v.is_a?(Container) }.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 no longer contain anything but the non-container objects" do
+        @depgraph.vertices.find_all { |v| ! v.is_a?(String) }.should be_empty
+    end
+
+    it "should copy labels" do
+        @depgraph.edges.each do |edge|
+            edge.label.should == {:callback => :refresh}
+        end
+    end
+
+    it "should not add labels to edges that have none" do
+        @depgraph.add_edge!(@two, @three)
+        splice
+        @depgraph.edge_label("c", "i").should == {}
+    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.edge_label("c", "i").should == {:callback => :refresh}
+    end
+
+    it "should not replace a label with a nil label" do
+        # Lastly, add some new label-less edges and make sure the label stays.
+        @depgraph.add_edge!(@middle, @three)
+        @depgraph.add_edge!("c", @three, {:callback => :refresh})
+        splice
+        @depgraph.edge_label("c", "i").should == {:callback => :refresh}
+    end
+
+    it "should copy labels to all created edges" do
+        @depgraph.add_edge!(@middle, @three)
+        @depgraph.add_edge!("c", @three, {:callback => :refresh})
+        splice
+        @three.each do |child|
+            edge = @depgraph.edge_class.new("c", child)
+            @depgraph.should be_edge(edge)
+            @depgraph[edge].should == {:callback => :refresh}
+        end
+    end
+end
+
+# Labels in this graph are used for managing relationships,
+# including callbacks, so they're quite important.
+describe Puppet::PGraph, " when managing labels" do
+    before do
+        @graph = Puppet::PGraph.new
+        @label = {:callback => :yay}
+    end
+
+    it "should return nil for edges with no label" do
+        @graph.add_edge!(:a, :b)
+        @graph.edge_label(:a, :b).should be_nil
+    end
+
+    it "should just return empty label hashes" do
+        @graph.add_edge!(:a, :b, {})
+        @graph.edge_label(:a, :b).should == {}
+    end
+
+    it "should consider empty label hashes to be nil when copying" do
+        @graph.add_edge!(:a, :b)
+        @graph.copy_label(:a, :b, {})
+        @graph.edge_label(:a, :b).should be_nil
+    end
+
+    it "should return label hashes" do
+        @graph.add_edge!(:a, :b, @label)
+        @graph.edge_label(:a, :b).should == @label
+    end
+
+    it "should replace nil labels with real labels" do
+        @graph.add_edge!(:a, :b)
+        @graph.copy_label(:a, :b, @label)
+        @graph.edge_label(:a, :b).should == @label
+    end
+
+    it "should not replace labels with nil labels" do
+        @graph.add_edge!(:a, :b, @label)
+        @graph.copy_label(:a, :b, {})
+        @graph.edge_label(:a, :b).should == @label
+    end
+end
+
+describe Puppet::PGraph, " when sorting the graph" do
+    before do
+        @graph = Puppet::PGraph.new
+    end
+
+    def add_edges(hash)
+        hash.each do |a,b|
+            @graph.add_edge!(a, b)
+        end
+    end
+
+    it "should fail on two-vertex loops" do
+        add_edges :a => :b, :b => :a
+        proc { @graph.topsort }.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)
+    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)
+    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
+    end
+end
+
+describe Puppet::PGraph, " functioning as a resource container" do
+    before do
+        @graph = Puppet::PGraph.new
+        @one = stub 'resource1', :ref => "Me[you]"
+        @two = stub 'resource2', :ref => "Me[him]"
+        @dupe = stub 'resource3', :ref => "Me[you]"
+    end
+
+    it "should make all vertices available by resource reference" do
+        @graph.add_vertex!(@one)
+        @graph.resource(@one.ref).should equal(@one)
+    end
+
+    it "should not allow two resources with the same resource reference" do
+        @graph.add_vertex!(@one)
+        proc { @graph.add_vertex!(@dupe) }.should raise_error(ArgumentError)
+    end
+
+    it "should not store objects that do not respond to :ref" do
+        str = "thing"
+        @graph.add_vertex!(str)
+        @graph.resource(str).should be_nil
+    end
+end
diff --git a/spec/unit/other/transbucket.rb b/spec/unit/other/transbucket.rb
new file mode 100755
index 000000000..c013973ee
--- /dev/null
+++ b/spec/unit/other/transbucket.rb
@@ -0,0 +1,123 @@
+#!/usr/bin/env ruby
+
+require File.dirname(__FILE__) + '/../../spec_helper'
+
+describe Puppet::TransBucket do
+    before do
+        @bucket = Puppet::TransBucket.new
+    end
+
+    it "should be able to produce a RAL component" do
+        @bucket.name = "luke"
+        @bucket.type = "user"
+
+        resource = nil
+        proc { resource = @bucket.to_type }.should_not raise_error
+        resource.should be_instance_of(Puppet::Type::Component)
+        resource.title.should == "user[luke]"
+    end
+
+    it "should accept TransObjects into its children list" do
+        object = Puppet::TransObject.new("luke", "user")
+        proc { @bucket.push(object) }.should_not raise_error
+        @bucket.each do |o|
+            o.should equal(object)
+        end
+    end
+
+    it "should accept TransBuckets into its children list" do
+        object = Puppet::TransBucket.new()
+        proc { @bucket.push(object) }.should_not raise_error
+        @bucket.each do |o|
+            o.should equal(object)
+        end
+    end
+
+    it "should refuse to accept any children that are not TransObjects or TransBuckets" do
+        proc { @bucket.push "a test" }.should raise_error
+    end
+
+    it "should return nil as its reference when type or name is missing" do
+        @bucket.to_ref.should be_nil
+    end
+
+    it "should return the title as its reference" do
+        @bucket.name = "luke"
+        @bucket.type = "user"
+        @bucket.to_ref.should == "user[luke]"
+    end
+end
+
+describe Puppet::TransBucket, " when generating a resource graph" do
+    before do
+        @bottom = Puppet::TransBucket.new
+        @bottom.type = "fake"
+        @bottom.name = "bottom"
+        @bottomobj = Puppet::TransObject.new("bottom", "user")
+        @bottom.push @bottomobj
+
+        @middle = Puppet::TransBucket.new
+        @middle.type = "fake"
+        @middle.name = "middle"
+        @middleobj = Puppet::TransObject.new("middle", "user")
+        @middle.push(@middleobj)
+        @middle.push(@bottom)
+
+        @top = Puppet::TransBucket.new
+        @top.type = "fake"
+        @top.name = "top"
+        @topobj = Puppet::TransObject.new("top", "user")
+        @top.push(@topobj)
+        @top.push(@middle)
+
+        @graph = @top.to_graph
+
+        @users = %w{top middle bottom}
+        @fakes = %w{fake[bottom] fake[middle] fake[top]}
+    end
+
+    it "should convert all transportable objects to RAL resources" do
+        @users.each do |name|
+            @graph.vertices.find { |r| r.class.name == :user and r.title == name }.should be_instance_of(Puppet::Type.type(:user))
+        end
+    end
+
+    it "should convert all transportable buckets to RAL components" do
+        @fakes.each do |name|
+            @graph.vertices.find { |r| r.class.name == :component and r.title == name }.should be_instance_of(Puppet::Type.type(:component))
+        end
+    end
+
+    it "should add all resources to the graph's resource table" do
+        @graph.resource("fake[top]").should equal(@top)
+    end
+
+    after do
+        Puppet::Type.allclear
+    end
+end
+
+describe Puppet::TransBucket, " when serializing" do
+    before do
+        @bucket = Puppet::TransBucket.new(%w{one two})
+        @bucket.name = "one"
+        @bucket.type = "two"
+    end
+
+    it "should be able to be dumped to yaml" do
+        proc { YAML.dump(@bucket) }.should_not raise_error
+    end
+
+    it "should dump YAML that produces an equivalent object" do
+        result = YAML.dump(@bucket)
+
+        newobj = YAML.load(result)
+        newobj.name.should == "one"
+        newobj.type.should == "two"
+        children = []
+        newobj.each do |o|
+            children << o
+        end
+        children.should == %w{one two}
+    end
+end
diff --git a/spec/unit/other/transobject.rb b/spec/unit/other/transobject.rb
new file mode 100755
index 000000000..07c9dc761
--- /dev/null
+++ b/spec/unit/other/transobject.rb
@@ -0,0 +1,116 @@
+#!/usr/bin/env ruby
+
+require File.dirname(__FILE__) + '/../../spec_helper'
+
+describe Puppet::TransObject, " when building its search path" do
+end
+
+describe Puppet::TransObject, " when building its search path" do
+end
+#!/usr/bin/env ruby
+
+$:.unshift("../lib").unshift("../../lib") if __FILE__ =~ /\.rb$/
+
+require 'puppet'
+require 'puppet/transportable'
+require 'puppettest'
+require 'puppettest/parsertesting'
+require 'yaml'
+
+class TestTransportable < Test::Unit::TestCase
+    include PuppetTest::ParserTesting
+
+    def test_yamldumpobject
+        obj = mk_transobject
+        obj.to_yaml_properties
+        str = nil
+        assert_nothing_raised {
+            str = YAML.dump(obj)
+        }
+
+        newobj = nil
+        assert_nothing_raised {
+            newobj = YAML.load(str)
+        }
+
+        assert(newobj.name, "Object has no name")
+        assert(newobj.type, "Object has no type")
+    end
+
+    def test_yamldumpbucket
+        objects = %w{/etc/passwd /etc /tmp /var /dev}.collect { |d|
+            mk_transobject(d)
+        }
+        bucket = mk_transbucket(*objects)
+        str = nil
+        assert_nothing_raised {
+            str = YAML.dump(bucket)
+        }
+
+        newobj = nil
+        assert_nothing_raised {
+            newobj = YAML.load(str)
+        }
+
+        assert(newobj.name, "Bucket has no name")
+        assert(newobj.type, "Bucket has no type")
+    end
+
+    # Verify that we correctly strip out collectable objects, since they should
+    # not be sent to the client.
+    def test_collectstrip
+        top = mk_transtree do |object, depth, width|
+            if width % 2 == 1
+                object.collectable = true
+            end
+        end
+
+        assert(top.flatten.find_all { |o| o.collectable }.length > 0,
+            "Could not find any collectable objects")
+
+        # Now strip out the collectable objects
+        top.collectstrip!
+
+        # And make sure they're actually gone
+        assert_equal(0, top.flatten.find_all { |o| o.collectable }.length,
+            "Still found collectable objects")
+    end
+
+    # Make sure our 'delve' command is working
+    def test_delve
+        top = mk_transtree do |object, depth, width|
+            if width % 2 == 1
+                object.collectable = true
+            end
+        end
+
+        objects = []
+        buckets = []
+        collectable = []
+
+        count = 0
+        assert_nothing_raised {
+            top.delve do |object|
+                count += 1
+                if object.is_a? Puppet::TransBucket
+                    buckets << object
+                else
+                    objects << object
+                    if object.collectable
+                        collectable << object
+                    end
+                end
+            end
+        }
+
+        top.flatten.each do |obj|
+            assert(objects.include?(obj), "Missing obj %s[%s]" % [obj.type, obj.name])
+        end
+
+        assert_equal(collectable.length,
+            top.flatten.find_all { |o| o.collectable }.length,
+            "Found incorrect number of collectable objects")
+    end
+end
+
+# $Id$
diff --git a/test/lib/puppettest.rb b/test/lib/puppettest.rb
index 06b85f147..33e3b2daf 100755
--- a/test/lib/puppettest.rb
+++ b/test/lib/puppettest.rb
@@ -265,6 +265,7 @@ module PuppetTest
         Puppet::Util::Storage.clear
         Puppet.clear
         Puppet.config.clear
+        Puppet::Indirector::Indirection.clear_cache
 
         @memoryatend = Puppet::Util.memory
         diff = @memoryatend - @memoryatstart
diff --git a/test/lib/puppettest/graph.rb b/test/lib/puppettest/graph.rb
deleted file mode 100644
index db77889bd..000000000
--- a/test/lib/puppettest/graph.rb
+++ /dev/null
@@ -1,41 +0,0 @@
-#!/usr/bin/env ruby
-#
-#  Created by Luke A. Kanies on 2006-11-24.
-#  Copyright (c) 2006. All rights reserved.
-
-require 'puppet/util/graph'
-
-class Container
-    include Puppet::Util::Graph
-    include Enumerable
-    attr_accessor :name
-    def each
-        @children.each do |c| yield c end
-    end
-    
-    def initialize(name, ary)
-        @name = name
-        @children = ary
-    end
-    
-    def push(*ary)
-        ary.each { |c| @children.push(c)}
-    end
-    
-    def to_s
-        @name
-    end
-end
-    
-module PuppetTest::Graph
-    def build_tree
-        one = Container.new("one", %w{a b})
-        two = Container.new("two", ["c", "d"])
-        three = Container.new("three", ["i", "j"])
-        middle = Container.new("middle", ["e", "f", two])
-        top = Container.new("top", ["g", "h", middle, one, three])
-        return one, two, three, middle, top
-    end
-end
-
-# $Id$
diff --git a/test/other/pgraph.rb b/test/other/pgraph.rb
deleted file mode 100755
index 34ba0e18c..000000000
--- a/test/other/pgraph.rb
+++ /dev/null
@@ -1,290 +0,0 @@
-#!/usr/bin/env ruby
-#
-#  Created by Luke Kanies on 2006-11-16.
-#  Copyright (c) 2006. All rights reserved.
-
-$:.unshift("../lib").unshift("../../lib") if __FILE__ =~ /\.rb$/
-
-require 'puppettest'
-require 'puppettest/graph'
-
-class TestPGraph < Test::Unit::TestCase
-	include PuppetTest
-	include PuppetTest::Graph
-	
-	Edge = Puppet::Relationship
-	
-	def test_clear
-	    graph = Puppet::PGraph.new
-	    graph.add_edge!("a", "b")
-	    graph.add_vertex! "c"
-	    assert_nothing_raised do
-	        graph.clear
-        end
-        assert(graph.vertices.empty?, "Still have vertices after clear")
-        assert(graph.edges.empty?, "still have edges after clear")
-    end
-	    
-	
-	def test_matching_edges
-	    graph = Puppet::PGraph.new
-	    
-	    event = Puppet::Event.new(:source => "a", :event => :yay)
-	    none = Puppet::Event.new(:source => "a", :event => :NONE)
-	    
-	    edges = {}
-	    
-	    edges["a/b"] = Edge["a", "b", {:event => :yay, :callback => :refresh}]
-	    edges["a/c"] = Edge["a", "c", {:event => :yay, :callback => :refresh}]
-	    
-	    graph.add_edge!(edges["a/b"])
-	    
-	    # Try it for the trivial case of one target and a matching event
-	    assert_equal([edges["a/b"]], graph.matching_edges([event]))
-	    
-	    # Make sure we get nothing with a different event
-	    assert_equal([], graph.matching_edges([none]))
-	    
-	    # Set up multiple targets and make sure we get them all back
-	    graph.add_edge!(edges["a/c"])
-	    assert_equal([edges["a/b"], edges["a/c"]].sort, graph.matching_edges([event]).sort)
-	    assert_equal([], graph.matching_edges([none]))
-    end
-    
-    def test_dependencies
-        graph = Puppet::PGraph.new
-        
-        graph.add_edge!("a", "b")
-        graph.add_edge!("a", "c")
-        graph.add_edge!("b", "d")
-        
-        assert_equal(%w{b c d}.sort, graph.dependents("a").sort)
-        assert_equal(%w{d}.sort, graph.dependents("b").sort)
-        assert_equal([].sort, graph.dependents("c").sort)
-        
-        assert_equal(%w{a b}, graph.dependencies("d").sort)
-        assert_equal(%w{a}, graph.dependencies("b").sort)
-        assert_equal(%w{a}, graph.dependencies("c").sort)
-        assert_equal([], graph.dependencies("a").sort)
-        
-    end
-    
-    # Test that we can take a containment graph and rearrange it by dependencies
-    def test_splice
-        one, two, three, middle, top = build_tree
-        empty = Container.new("empty", [])
-        # Also, add an empty container to top
-        top.push empty
-
-        contgraph = top.to_graph
-
-        # Now add a couple of child files, so that we can test whether all
-        # containers get spliced, rather than just components.
-
-        # Now make a dependency graph
-        deps = Puppet::PGraph.new
-
-        contgraph.vertices.each do |v|
-            deps.add_vertex(v)
-        end
-
-        # 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|
-            deps.add_edge!(source, target, :callback => :refresh)
-        end
-        
-        #contgraph.to_jpg(File.expand_path("~/Desktop/pics"), "main")
-        #deps.to_jpg(File.expand_path("~/Desktop/pics"), "before")
-        assert_nothing_raised { deps.splice!(contgraph, Container) }
-        
-        assert(! deps.cyclic?, "Created a cyclic graph")
-
-        # Make sure there are no container objects remaining
-        #deps.to_jpg(File.expand_path("~/Desktop/pics"), "after")
-        c = deps.vertices.find_all { |v| v.is_a?(Container) }
-        assert(c.empty?, "Still have containers %s" % c.inspect)
-        
-        # Now make sure the containers got spliced correctly.
-        contgraph.leaves(middle).each do |leaf|
-            assert(deps.edge?("h", leaf), "no edge for h => %s" % leaf)
-        end
-        one.each do |oobj|
-            two.each do |tobj|
-                assert(deps.edge?(oobj, tobj), "no %s => %s edge" % [oobj, tobj])
-            end
-        end
-        
-        nons = deps.vertices.find_all { |v| ! v.is_a?(String) }
-        assert(nons.empty?,
-            "still contain non-strings %s" % nons.inspect)
-        
-        deps.edges.each do |edge|
-            assert_equal({:callback => :refresh}, edge.label,
-                "Label was not copied for %s => %s" % [edge.source, edge.target])
-        end
-
-        # Now add some relationships to three, but only add labels to one of
-        # the relationships.
-
-        # Add a simple, label-less relationship
-        deps.add_edge!(two, three)
-        assert_nothing_raised { deps.splice!(contgraph, Container) }
-
-        # And make sure it stuck, with no labels.
-        assert_equal({}, deps.edge_label("c", "i"),
-            "label was created for c => i")
-
-        # Now add some edges with labels, in a way that should overwrite
-        deps.add_edge!("c", three, {:callback => :refresh})
-        assert_nothing_raised { deps.splice!(contgraph, Container) }
-
-        # And make sure the label got copied.
-        assert_equal({:callback => :refresh}, deps.edge_label("c", "i"),
-            "label was not copied for c => i")
-
-        # Lastly, add some new label-less edges and make sure the label stays.
-        deps.add_edge!(middle, three)
-        assert_nothing_raised { deps.splice!(contgraph, Container) }
-        assert_equal({:callback => :refresh}, deps.edge_label("c", "i"),
-            "label was lost for c => i")
-        
-        # Now make sure the 'three' edges all have the label we've used.
-        # Note that this will not work when we support more than one type of
-        # subscription.
-        three.each do |child|
-            edge = deps.edge_class.new("c", child)
-            assert(deps.edge?(edge), "no c => %s edge" % child)
-            assert_equal({:callback => :refresh}, deps[edge],
-                "label was not retained for c => %s" % child)
-        end
-    end
-
-    def test_copy_label
-        graph = Puppet::PGraph.new
-
-        # First make an edge with no label
-        graph.add_edge!(:a, :b)
-        assert_nil(graph.edge_label(:a, :b), "Created a label")
-
-        # Now try to copy an empty label in.
-        graph.copy_label(:a, :b, {})
-
-        # It should just do nothing, since we copied an empty label.
-        assert_nil(graph.edge_label(:a, :b), "Created a label")
-
-        # Now copy in a real label.
-        graph.copy_label(:a, :b, {:callback => :yay})
-        assert_equal({:callback => :yay},
-            graph.edge_label(:a, :b), "Did not copy label")
-
-        # Now copy in a nil label
-        graph.copy_label(:a, :b, nil)
-        assert_equal({:callback => :yay},
-            graph.edge_label(:a, :b), "lost label")
-
-        # And an empty one.
-        graph.copy_label(:a, :b, {})
-        assert_equal({:callback => :yay},
-            graph.edge_label(:a, :b), "lost label")
-    end
-
-    def test_fail_on_cycle
-        {
-            {:a => :b, :b => :a, :c => :a, :d => :c} => true, # larger tree involving a smaller cycle
-            {:a => :b, :b => :c, :c => :a} => true,
-            {:a => :b, :b => :a, :c => :d, :d => :c} => true,
-            {:a => :b, :b => :c} => false,
-        }.each do |hash, result|
-            graph = Puppet::PGraph.new
-            hash.each do |a,b|
-                graph.add_edge!(a, b)
-            end
-
-            if result
-                assert_raise(Puppet::Error, "%s did not fail" % hash.inspect) do
-                   graph.topsort
-                end
-            else
-                assert_nothing_raised("%s failed" % hash.inspect) do
-                    graph.topsort
-                end
-            end
-        end
-    end
-
-    # This isn't really a unit test, it's just a way to do some graphing with
-    # tons of relationships so we can see how it performs.
-    def disabled_test_lots_of_relationships
-        containers = Puppet::PGraph.new
-        relationships = Puppet::PGraph.new
-        labels = %w{a b c d e}
-        conts = {}
-        vertices = {}
-        labels.each do |label|
-            vertices[label] = []
-        end
-        num = 100
-        num.times do |i|
-            labels.each do |label|
-                vertices[label] << ("%s%s" % [label, i])
-            end
-        end
-        labels.each do |label|
-            conts[label] = Container.new(label, vertices[label])
-        end
-
-        conts.each do |label, cont|
-            cont.each do |child|
-                containers.add_edge!(cont, child)
-            end
-        end
-        prev = nil
-        labels.inject(nil) do |prev, label|
-            if prev
-                containers.add_edge!(conts[prev], conts[label])
-            end
-            label
-        end
-
-        containers.to_jpg(File.expand_path("~/Desktop/pics/lots"), "start")
-
-        # Now create the relationship graph
-
-        # Make everything in both b and c require d1
-        %w{b c}.each do |label|
-            conts[label].each do |v|
-                relationships.add_edge!(v, "d1")
-                #relationships.add_edge!(v, conts["d"])
-            end
-        end
-
-        # Make most in b also require the appropriate thing in c
-        conts["b"].each do |v|
-            i = v.split('')[1]
-
-            relationships.add_edge!(v, "c%s" % i)
-        end
-
-        # And make d1 require most of e
-        num.times do |i|
-            relationships.add_edge!("d1", "e%s" % i)
-        end
-
-        containers.vertices.each do |v|
-            relationships.add_vertex!(v)
-        end
-        relationships.to_jpg(File.expand_path("~/Desktop/pics/lots"), "relationships")
-
-        time = Benchmark.realtime do
-            relationships.splice!(containers, Container)
-        end
-        relationships.to_jpg(File.expand_path("~/Desktop/pics/lots"), "final")
-        puts time
-        time = Benchmark.realtime do
-            relationships.topsort
-        end
-    end
-end
-
-# $Id$