From: ara.t.howard@...
Date: 2006-04-27T02:07:42+09:00
Subject: Re: Rake task dependeny vs. method call

On Wed, 26 Apr 2006, Joel VanderWerf wrote:

> He (OP) already did the t-sort, implicitly.

not really, what it does is a kind of
global-short-circuit-based-on-dependancy-sort.  consider:

     harp:~ > cat a.rb
     require 'tasklib'

     task :uidgen do |*argv| (seed = argv.shift) ? rand(seed) : $UID||=uidgen(42) end

     task :a => :uidgen do y "a" => $UID end
     task :b => :a do y "b" => uidgen(42) end
     task :c => :a do y "c" => uidgen(42) end
     task :d => [:b, :c] do y "d" end

     d()


     harp:~ > ruby a.rb
     ---
     a: 12
     ---
     b: 12
     ---
     c: 12
     --- d


so this fails horribly (rand is called only a single time) because the
topology is determined via a mechanism (short circuit caching) in addition and
outside of the defined relationships.  in otherwords the topological sort
should only __enable__ the call graph not __prevent__ all routes through it.
otherwise it's way too fragile and any outside calls can break the chain as
this contrived example shows.


as far as i can tell it also fails to detect cycles:

   harp:~ > cat b.rb
   require 'tasklib'

   task :b => :a and task :a => :b

   b()


   harp:~ > ruby b.rb
   ./tasklib.rb:21:in `a': stack level too deep (SystemStackError)
      from (eval):8:in `a'
      from ./tasklib.rb:21:in `b'
      from ./tasklib.rb:21:in `b'
      from (eval):8:in `b'
      from ./tasklib.rb:21:in `a'
      from ./tasklib.rb:21:in `a'
      from (eval):8:in `a'
      from ./tasklib.rb:21:in `b'
       ... 2219 levels...
      from ./tasklib.rb:21:in `b'
      from ./tasklib.rb:21:in `b'
      from (eval):8:in `b'
      from b.rb:5




but by redefining tasklib.rb to use tsort both task lists function correctly:


     harp:~ > cat a.rb
     require 'tasklib2'

     task :uidgen do |*argv| (seed = argv.shift) ? rand(seed) : $UID||=uidgen(42) end

     task :a => :uidgen do y "a" => $UID end
     task :b => :a do y "b" => uidgen(42) end
     task :c => :a do y "c" => uidgen(42) end
     task :d => [:b, :c] do y "d" end

     d()


     harp:~ > ruby a.rb
     ---
     a: 5
     ---
     b: 15
     ---
     a: 5
     ---
     c: 3
     --- d


and cycles are detected at declaration time:


     harp:~ > cat b.rb
     require 'tasklib2'

     task :b => :a and task :a => :b

     b()


     harp:~ > ruby b.rb
     /home/ahoward//lib/ruby/1.8/tsort.rb:152:in `tsort_each': topological sort failed: [:b, :a] (TSort::Cyclic)
        from /home/ahoward//lib/ruby/1.8/tsort.rb:183:in `each_strongly_connected_component'
        from /home/ahoward//lib/ruby/1.8/tsort.rb:219:in `each_strongly_connected_component_from'
        from /home/ahoward//lib/ruby/1.8/tsort.rb:182:in `each_strongly_connected_component'
        from /home/ahoward//lib/ruby/1.8/tsort.rb:180:in `each_strongly_connected_component'
        from /home/ahoward//lib/ruby/1.8/tsort.rb:148:in `tsort_each'
        from /home/ahoward//lib/ruby/1.8/tsort.rb:135:in `tsort'
        from ./tasklib2.rb:35:in `task'
        from b.rb:3



i'm not saying my impl is perfect - just that using tsort ensures only the
topology declared is enforced and that no other implied topology created by
short circuiting operations via caching prevents 'normal' routes through this
call graph.


here are both impls:


   harp:~ > cat tasklib2.rb
   require 'cache'
   require 'yaml'
   require 'tsort'
   module Task
     class TSortHash < Hash
       include TSort
       alias_method 'tsort_each_node', 'each_key'
       def tsort_each_child(node, &block) fetch(node).each(&block) end
       def initialize(hash={}) update hash end
       def [](key) super || [] end
       def fetch(key) super rescue [] end
     end

     TH = TSortHash.new

     def task_dependencies() @task_dependencies ||= {} end
     def task_descriptions() @task_descriptions ||= {} end
     def desc(line) @last_description = line.gsub("\n",'') end

     def task(args, &action)
       if Hash === args
         raise ArgumentError, "#{args.size} for 1" if args.size != 1
         name, *deps = *(args.to_a.flatten)
         name = name.to_sym
         deps = deps.compact.collect{ |e| e.to_sym }
       else
         name, deps = args.to_sym, []
       end

       # ensure no cycles in this graph and extract call graph
       th = TSortHash.new name => deps
       dag = th.tsort

       # ensure no cycles in global graph
       TH.update(th).tsort

       task_dependencies[ name ] = deps
       task_descriptions[ name ] = @last_description
       @last_description = nil

       (class<<self;self;end).module_eval do
         define_method( name ) do |*__a__|
           dag.each{|d| send(d) unless name == d }
           action.call(*__a__) if action
         end
       end
     end
     class ::Object; include Task; end
   end


   harp:~ > cat tasklib.rb
   require 'cache'
   require 'yaml'
   module Task
     def task_dependencies() @task_dependencies ||= {} end
     def task_descriptions() @task_descriptions ||= {} end
     def desc(line) @last_description = line.gsub("\n",'') end
     def task(args, &action)
       if Hash === args
         raise ArgumentError, "#{args.size} for 1" if args.size != 1
         name, *deps = *(args.to_a.flatten)
         name = name.to_sym
         deps = deps.compact.collect{ |e| e.to_sym }
       else
         name, deps = args.to_sym, []
       end
       task_dependencies[ name ] = deps
       task_descriptions[ name ] = @last_description
       @last_description = nil
       (class<<self;self;end).module_eval do
         define_method( name ) do |*__a__|
           deps.each{ |d| send(d) }
           action.call(*__a__) if action
         end
         cache name
       end
     end
     class ::Object; include Task; end
   end


   harp:~ > cat cache.rb
   class Object
     def singleton_class() class<<self;self;end end
     def cache m = nil
       if m
         (Module === self ? self : singleton_class).module_eval <<-code
           alias_method '__#{ m }__', '#{ m }'
           def #{ m }(*__a__,&__b__)
             c = cache['#{ m }']
             k = [__a__,__b__]
             if c.has_key? k
               c[k]
             else
               c[k] = __#{ m }__(*__a__,&__b__)
             end
           end
         code
       end
       @cache ||= Hash::new{|h,k| h[k]={}}
     end
   end



kind regards.


-a
-- 
be kind whenever possible... it is always possible.
- h.h. the 14th dali lama