Switching the graph base class from GRATR::Digraph

to Puppet::SimpleGraph, which should dramatically enhance
performance.  It should be largely functionally equivalent,
with the only difference being that edges are no longer deduplicated.

8 files changed, 136 insertions, 92 deletions

diff --git a/CHANGELOG b/CHANGELOG
index 83b6710e2..5a7103403 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,3 +1,8 @@
+    Replaced GRATR::Digraph with Puppet::SimpleGraph as
+    the base class for Puppet's graphing.  Functionality
+    should be equivalent but with dramatically better
+    performance.
+
     The --use-nodes and --no-nodes options are now obsolete.
     Puppet automatically detects when nodes are defined, and if
     they are defined it will require that a node be found,
diff --git a/lib/puppet/node/configuration.rb b/lib/puppet/node/configuration.rb
index 1365767b6..e49090d70 100644
--- a/lib/puppet/node/configuration.rb
+++ b/lib/puppet/node/configuration.rb
@@ -83,6 +83,7 @@ class Puppet::Node::Configuration < Puppet::PGraph
 
         transaction.addtimes :config_retrieval => @retrieval_duration
 
+
         begin
             transaction.evaluate
         rescue Puppet::Error => detail
@@ -304,7 +305,7 @@ class Puppet::Node::Configuration < Puppet::PGraph
             # Lastly, add in any autorequires
             @relationship_graph.vertices.each do |vertex|
                 vertex.autorequire.each do |edge|
-                    unless @relationship_graph.edge?(edge)
+                    unless @relationship_graph.edge?(edge.source, edge.target) # don't let automatic relationships conflict with manual ones.
                         unless @relationship_graph.edge?(edge.target, edge.source)
                             vertex.debug "Autorequiring %s" % [edge.source]
                             @relationship_graph.add_edge!(edge)
diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb
index ca45aa2b3..49fd21401 100644
--- a/lib/puppet/pgraph.rb
+++ b/lib/puppet/pgraph.rb
@@ -4,11 +4,13 @@
 require 'puppet/external/gratr/digraph'
 require 'puppet/external/gratr/import'
 require 'puppet/external/gratr/dot'
+
 require 'puppet/relationship'
+require 'puppet/simple_graph'
 
 # This class subclasses a graph class in order to handle relationships
 # among resources.
-class Puppet::PGraph < GRATR::Digraph
+class Puppet::PGraph < Puppet::SimpleGraph
     # This is the type used for splicing.
     attr_accessor :container_type
 
@@ -23,13 +25,6 @@ class Puppet::PGraph < GRATR::Digraph
         @reversal = nil
         super
     end
-    
-    def clear
-        @vertex_dict.clear
-        if defined? @edge_number
-            @edge_number.clear
-        end
-    end
 
     # Make sure whichever edge has a label keeps the label
     def copy_label(source, target, label)
@@ -149,7 +144,7 @@ class Puppet::PGraph < GRATR::Digraph
                     # Now get rid of the edge, so remove_vertex! works correctly.
                     remove_edge!(edge)
                     Puppet.debug "%s: %s => %s: %s" % [container,
-                        edge.source, edge.target, edge?(edge)]
+                        edge.source, edge.target, edge?(edge.source, edge.target)]
                 end
             end
             remove_vertex!(container)
diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index c8fa40e06..48bf4991e 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -54,8 +54,11 @@ class Puppet::SimpleGraph
 
         # The other vertex in the edge.
         def other_vertex(direction, edge)
-            method = direction == :in ? :source : :target
-            edge.send(method)
+            case direction
+            when :in: edge.source
+            else
+                edge.target
+            end
         end
 
         # Remove an edge from our list.  Assumes that we've already checked
@@ -82,6 +85,17 @@ class Puppet::SimpleGraph
         true
     end
 
+    # Return a reversed version of this graph.
+    def reversal
+        result = self.class.new
+        vertices.each { |vertex| result.add_vertex!(vertex) }
+        edges.each do |edge|
+            newedge = edge.class.new(edge.target, edge.source, edge.label)
+            result.add_edge!(newedge)
+        end
+        result
+    end
+
     # Return the size of the graph. Used by GRATR.
     def size
         @vertices.length
@@ -119,9 +133,9 @@ class Puppet::SimpleGraph
 
     # Add a new edge.  The graph user has to create the edge instance,
     # since they have to specify what kind of edge it is.
-    def add_edge!(source, target = nil)
+    def add_edge!(source, target = nil, label = nil)
         if target
-            edge = Puppet::Relationship.new(source, target)
+            edge = Puppet::Relationship.new(source, target, label)
         else
             edge = source
         end
@@ -138,6 +152,11 @@ class Puppet::SimpleGraph
         @edges.each_with_index { |test_edge, index| return test_edge if test_edge.source == source and test_edge.target == target }
     end
 
+    def edge_label(source, target)
+        return nil unless edge = edge(source, target)
+        edge.label
+    end
+
     # Is there an edge between the two vertices?
     def edge?(source, target)
         return false unless vertex?(source) and vertex?(target)
@@ -174,4 +193,59 @@ class Puppet::SimpleGraph
     def setup_vertex(vertex)
         @vertices[vertex] = VertexWrapper.new(vertex)
     end
+ 
+    public
+
+    # LAK:FIXME This is just a paste of the GRATR code with slight modifications.
+
+    # Return a DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph for an
+    # undirected Graph.  _params_ can contain any graph property specified in
+    # rdot.rb. If an edge or vertex label is a kind of Hash then the keys
+    # which match +dot+ properties will be used as well.
+    def to_dot_graph (params = {})
+      params['name'] ||= self.class.name.gsub(/:/,'_')
+      fontsize   = params['fontsize'] ? params['fontsize'] : '8'
+      graph      = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params)
+      edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge
+      vertices.each do |v|
+        name = v.to_s
+        params = {'name'     => '"'+name+'"',
+                  'fontsize' => fontsize,
+                  'label'    => name}
+        v_label = vertex_label(v)
+        params.merge!(v_label) if v_label and v_label.kind_of? Hash
+        graph << DOT::DOTNode.new(params)
+      end
+      edges.each do |e|
+        params = {'from'     => '"'+ e.source.to_s + '"',
+                  'to'       => '"'+ e.target.to_s + '"',
+                  'fontsize' => fontsize }
+        e_label = edge_label(e)
+        params.merge!(e_label) if e_label and e_label.kind_of? Hash
+        graph << edge_klass.new(params)
+      end
+      graph
+    end
+    
+    # Output the dot format as a string
+    def to_dot (params={}) to_dot_graph(params).to_s; end
+
+    # Call +dotty+ for the graph which is written to the file 'graph.dot'
+    # in the # current directory.
+    def dotty (params = {}, dotfile = 'graph.dot')
+      File.open(dotfile, 'w') {|f| f << to_dot(params) }
+      system('dotty', dotfile)
+    end
+
+    # Use +dot+ to create a graphical representation of the graph.  Returns the
+    # filename of the graphics file.
+    def write_to_graphic_file (fmt='png', dotfile='graph')
+      src = dotfile + '.dot'
+      dot = dotfile + '.' + fmt
+      
+      File.open(src, 'w') {|f| f << self.to_dot << "\n"}
+      
+      system( "dot -T#{fmt} #{src} -o #{dot}" )
+      dot
+    end
 end
diff --git a/lib/puppet/transaction.rb b/lib/puppet/transaction.rb
index e30159c24..c8fc2f199 100644
--- a/lib/puppet/transaction.rb
+++ b/lib/puppet/transaction.rb
@@ -294,7 +294,7 @@ class Transaction
     # necessary events.
     def evaluate
         @count = 0
-        
+
         # Start logging.
         Puppet::Util::Log.newdestination(@report)
         
@@ -478,7 +478,7 @@ class Transaction
     # types, just providers.
     def prefetch
         prefetchers = {}
-        @configuration.each do |resource|
+        @configuration.vertices.each do |resource|
             if provider = resource.provider and provider.class.respond_to?(:prefetch)
                 prefetchers[provider.class] ||= {}
                 prefetchers[provider.class][resource.title] = resource
diff --git a/spec/unit/other/pgraph.rb b/spec/unit/other/pgraph.rb
index 19809ac1e..9446a8371 100755
--- a/spec/unit/other/pgraph.rb
+++ b/spec/unit/other/pgraph.rb
@@ -122,7 +122,7 @@ describe Puppet::PGraph, " when splicing the relationship graph" do
     def dependency_graph
         @depgraph = Puppet::PGraph.new
         @contgraph.vertices.each do |v|
-            @depgraph.add_vertex(v)
+            @depgraph.add_vertex!(v)
         end
 
         # We have to specify a relationship to our empty container, else it
@@ -204,54 +204,12 @@ describe Puppet::PGraph, " when splicing the relationship graph" do
         splice
         @three.each do |child|
             edge = @depgraph.edge_class.new("c", child)
-            @depgraph.should be_edge(edge)
-            @depgraph[edge].should == {:callback => :refresh}
+            @depgraph.should be_edge(edge.source, edge.target)
+            @depgraph.edge_label(edge.source, edge.target).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
diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb
index e5afdf746..1be29c0dc 100755
--- a/spec/unit/simple_graph.rb
+++ b/spec/unit/simple_graph.rb
@@ -17,6 +17,12 @@ describe Puppet::SimpleGraph do
     it "should consider itself a directed graph" do
         Puppet::SimpleGraph.new.directed?.should be_true
     end
+
+    it "should provide a method for reversing the graph" do
+        @graph = Puppet::SimpleGraph.new
+        @graph.add_edge!(:one, :two)
+        @graph.reversal.edge?(:two, :one).should be_true
+    end
 end
 
 describe Puppet::SimpleGraph, " when managing vertices" do
@@ -80,6 +86,17 @@ describe Puppet::SimpleGraph, " when managing edges" do
         @graph.edge?(:one, :two).should be_true
     end
 
+    it "should provide a method to add an edge by specifying the two vertices and a label" do
+        @graph.add_edge!(:one, :two, :stuff => :awesome)
+        @graph.edge?(:one, :two).should be_true
+    end
+
+    it "should provide a method for retrieving an edge label" do
+        edge = Puppet::Relationship.new(:one, :two, :stuff => :awesome)
+        @graph.add_edge!(edge)
+        @graph.edge_label(:one, :two).should == {:stuff => :awesome}
+    end
+
     it "should provide a method for retrieving an edge" do
         edge = Puppet::Relationship.new(:one, :two)
         @graph.add_edge!(edge)
@@ -181,3 +198,28 @@ describe Puppet::SimpleGraph, " when clearing" do
         @graph.edges.should be_empty
     end
 end
+
+describe Puppet::SimpleGraph, " when reversing graphs" do
+    before do
+        @graph = Puppet::SimpleGraph.new
+    end
+
+    it "should provide a method for reversing the graph" do
+        @graph.add_edge!(:one, :two)
+        @graph.reversal.edge?(:two, :one).should be_true
+    end
+
+    it "should add all vertices to the reversed graph" do
+    end
+    
+    it "should retain labels on edges" do
+        @graph.add_edge!(:one, :two, :stuff => :awesome)
+        edge = @graph.reversal.edge(:two, :one)
+        edge.label.should == {:stuff => :awesome}
+    end
+end
+
+describe Puppet::SimpleGraph, " when making DOT files" do
+    # LAK:FIXME yay
+    it "should have tests"
+end
diff --git a/test/other/transactions.rb b/test/other/transactions.rb
index fb5cf4018..8156ba478 100755
--- a/test/other/transactions.rb
+++ b/test/other/transactions.rb
@@ -1006,37 +1006,6 @@ class TestTransactions < Test::Unit::TestCase
         end
     end
 
-    def test_labeled_deps_beat_unlabeled
-        one = Puppet::Type.type(:exec).create :command => "/bin/echo one"
-        two = Puppet::Type.type(:exec).create :command => "/bin/echo two"
-
-        one[:require] = two
-        one[:subscribe] = two
-
-        comp = mk_configuration(one, two)
-        trans = Puppet::Transaction.new(comp)
-        graph = trans.relationship_graph
-
-        label = graph.edge_label(two, one)
-        assert(label, "require beat subscribe")
-        assert_equal(:refresh, label[:callback],
-            "did not get correct callback from subscribe")
-
-        one.delete(:require)
-        one.delete(:subscribe)
-
-        two[:before] = one
-        two[:notify] = one
-
-        trans = Puppet::Transaction.new(comp)
-        graph = trans.relationship_graph
-
-        label = graph.edge_label(two, one)
-        assert(label, "before beat notify")
-        assert_equal(:refresh, label[:callback],
-            "did not get correct callback from notify")
-    end
-
     # #542 - make sure resources in noop mode still notify their resources,
     # so that users know if a service will get restarted.
     def test_noop_with_notify