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