[Pkg-puppet-devel] [SCM] Puppet packaging for Debian branch, experimental, updated. debian/2.6.8-1-844-g7ec39d5

[Markus Roberts]

The following commit has been merged in the experimental branch:
commit 8af29c8f9a4da0d9e4a1c15f032f9c0bb9348d62
Author: Markus Roberts <Markus at reality.com>
Date:   Fri Apr 1 17:49:37 2011 -0700

    (6911) Core change -- replace topsort with frontier ordered by salted SHA1
    
    This is the core change of the ticket; rather than using a topological sort to statically
    determine the order in which resources should be applied, we use the graph wrapper
    introduced in the prior commit to dynamically determine the order in which to apply
    resources based on 1) the status of the resource (ready, done) 2) the explicit &
    implied dependencies, 3) the salted SHA1 of the title (for stability).
    
    Further work is needed:
    
    1) Resolving the handling of failed resources
    2) Tests of the new behavior, to the extent posible
    3) Newly-dead-code removal in simple_graph & transaction
    4) Fix the name-prefix ordering hack in eval_generate by either:
        a) Moving the logic into file
        b) Refactoring Type#eval_generate to return a tree
        c) ....?
    5) Rough performace testing to look for hotspots
    6) Investigation of possible interaction with #3788, #5351, #5414, #5876, #6020, #6810,
       and #6944 which may simplify or complicate their resolution.
    
    Paired-with: Jesse Wolfe

diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index 27e068e..31858f1 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -453,6 +453,10 @@ class Puppet::SimpleGraph
     result
   end
 
+  def direct_dependents_of(v)
+    @out_from[v].keys 
+  end
+
   def upstream_from_vertex(v)
     return @upstream_from[v] if @upstream_from[v]
     result = @upstream_from[v] = {}
@@ -463,6 +467,10 @@ class Puppet::SimpleGraph
     result
   end
 
+  def direct_dependencies_of(v)
+    @in_to[v].keys 
+  end
+
   # 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
diff --git a/lib/puppet/transaction.rb b/lib/puppet/transaction.rb
index 928a1b4..79fdb04 100644
--- a/lib/puppet/transaction.rb
+++ b/lib/puppet/transaction.rb
@@ -4,6 +4,7 @@
 require 'puppet'
 require 'puppet/util/tagging'
 require 'puppet/application'
+require 'sha1'
 
 class Puppet::Transaction
   require 'puppet/transaction/event'
@@ -103,7 +104,7 @@ class Puppet::Transaction
     Puppet.info "Applying configuration version '#{catalog.version}'" if catalog.version
 
     begin
-      visit_resources do |resource|
+      relationship_graph.traverse do |resource|
         next if stop_processing?
         if resource.is_a?(Puppet::Type::Component)
           Puppet.warning "Somehow left a component in the relationship graph"
@@ -262,20 +263,6 @@ class Puppet::Transaction
     prefetch
   end
 
-  def visit_resources(&block)
-    eval_generated = {}
-    while r = relationship_graph.topsort.find { |r| !applied_resources.include?(r) }
-      #p relationship_graph.topsort.collect { |r0| r0.title[/(-0.*)/,1] }
-      if !eval_generated[r]
-        #p [:generate,r.title]
-        eval_generate(r)
-        eval_generated[r] = true
-      else
-        #p [:apply,r.title]
-        yield r
-      end
-    end
-  end
 
   # We want to monitor changes in the relationship graph of our
   # catalog but this is complicated by the fact that the catalog
@@ -293,18 +280,41 @@ class Puppet::Transaction
   # except via the Transaction#relationship_graph
 
   class Relationship_graph_wrapper
+    attr_reader :real_graph,:transaction,:ready,:generated,:done
     def initialize(real_graph,transaction)
       @real_graph = real_graph
       @transaction = transaction
+      @ready = {}
+      @generated = {}
+      @done = {}
+      vertices.each { |v| check_if_now_ready(v) }
     end
     def method_missing(*args,&block)
-      @real_graph.send(*args,&block)
+      real_graph.send(*args,&block)
     end
     def add_vertex(v)
-      @real_graph.add_vertex(v)
+      real_graph.add_vertex(v)
     end
     def add_edge(f,t)
-      @real_graph.add_edge(f,t)
+      ready.delete(t)
+      real_graph.add_edge(f,t)
+    end
+    def check_if_now_ready(r)
+      ready[r] = true if direct_dependencies_of(r).all? { |r2| done[r2] }
+    end  
+    def traverse(&block)
+      unguessable_deterministic_key = Hash.new { |h,k| h[k] = Digest::SHA1.hexdigest("NaCl, MgSO4 (salts) and then #{k.title}") }
+      while r = ready.keys.sort_by { |r0| unguessable_deterministic_key[r0] }.first
+        if !generated[r]
+          transaction.eval_generate(r)
+          generated[r] = true
+        else
+          ready.delete(r)
+          yield r
+          done[r] = true
+          direct_dependents_of(r).each { |v| check_if_now_ready(v) }
+        end
+      end
     end
   end
 
diff --git a/spec/unit/transaction_spec.rb b/spec/unit/transaction_spec.rb
index 57bf800..076b626 100755
--- a/spec/unit/transaction_spec.rb
+++ b/spec/unit/transaction_spec.rb
@@ -390,9 +390,11 @@ describe Puppet::Transaction do
     describe 'within an evaluate call' do
       before do
         @resource = stub 'resource', :ref => 'some_ref'
+        @relationship_graph = stub 'relationship_graph'
         @catalog.add_resource @resource
         @transaction.stubs(:prepare)
-        @transaction.stubs(:visit_resources).yields(@resource)
+        @transaction.stubs(:relationship_graph).returns @relationship_graph
+        @relationship_graph.stubs(:traverse).yields @resource
       end
 
       it 'should stop processing if :stop_processing? is true' do

-- 
Puppet packaging for Debian