[ANN] Rant 0.3.2

ruby-talk
21

Nikolai Weibull a écrit :

Lionel Thiry, April 7:

SCons main design doc claims its cornerstone is the management of
explicit file dependency DAG.

Where are you reading this?

I've read this one or two years ago, when I interested in SCons. Where? Scons organisation has changed much since that time...

Found one:
http://www.scons.org/doc/PDF/scons-design.pdf
This is the design doc of SCons 0.96, the latest version. Look in chapter 3, see architecture.

What it does differently from make(1) is
that it creates a complete DAG of all dependencies, i.e., it doesn't
rely on recursive invocations (like make(1) does). That's the only
difference I know of,
        nikolai

Mmm, I fell it hard to tell where is the difference between your statement and mine.

···

--
Lionel Thiry

22

Jim Weirich a écrit :

You seem to imply there would be advantages to a more explicit DAG
implementation.

Not exactly. SCons main design doc claims its cornerstone is the management
of explicit file dependency DAG. As SCons is one of the source of
inspiration for Rant, I asked if it was based on the same cornerstone.

I scanned the Scons web site and googled for DAG. The only references to DAG that I found were referencing the one makefile/universal DAG approach recommended in the "Recursive Make Considered Harmful" article. I too prefer the universal DAG approach and Rake certainly supports that way of doing things.

If I missed something, fill me in.

http://www.scons.org/doc/PDF/scons-design.pdf

I would be interested in hearing what you think those
advantages might be.

I have forgotten one, the way tasks are executed. You can execute the TDG in such a way that you don't have to check repeatedly each task to know if it has already been executed. You just begin at the right starting nodes and follows the arrows.

Well, that's what I thought until I tried to code that myself. What a nightmare! :slight_smile:

>>For Rake, the advantages of a Task Dependency Graph (TDG) _might_ be:
>>1) better decoupling between inner mechanisms of Rake and its interface,
>>the Rakefile. It would allow the development of other interfaces.
>>2) Easier to play with several TDG at the same time, merge them, split
>>them, and so on. Probably not doable with Rakefile as there is usually only
>>one such TDG.
>>3) Easier to add multithreaded task execution.
>>4) easier to develop event listening (for example: once this target is
>>build and passed unit tests, send me a mail)
>>5) easier to develop error & exception management
>>6) probably a lot of other features that I haven't sight of
>
> (2) I might grant, but even so I'm considering how to do something very
> similar to (2) in order to support task suites.
> As for the others, I'm not
> convinced it makes a big difference one way or another.

Do you mean that every thing in the list above can already be done with rake? Or will be added to rake? Will you really add all these features?

Especially about (1), would you plan to decouple Rake interface (the Rakefiles) and Rake internals? Said another way, would you plan to make rake usable through a standard ruby script?

  require 'rake'
  # do rake stuff but more explicitly
  # no more implicit tasks or rules
  # no more implicit management of options

Not being able to do this is what disturbs me the most about rake.

>>The disadvantages are:
>>1) the advantages listed above are mostly suppositions
>>2) DAG management code may be heavy
>>3) task generation on the fly as the TDG is executed may be delicate to
>>implement
>>4) not sure the concept of rule can be applied easily with a TDG
>
> Hmmm ... (3) leads me to suspect you are really talking about marshalling or
> serializing the DAG into external storage and reloading it. Is that what you
> are getting at?

No.

I've already thought about that, but I don't know how to solve the problem of serializing ruby blocks.

> Or am I still missing the point.

I was thinking about tasks that create tasks.

For example, let's say task1 generate a source file. But then, you want to compile that source file too and you may don't know in advance how to do that until you know exactly what kind of source file has been generated.

A possible solution is that when task1 has generated its target, it checks the type of the result and then generates, on the fly, a task2 in charge of compiling that file.

Another solution could be to have a kind of task template ready for instanciation with the right parameters from another task.

···

On Wednesday 06 April 2005 05:44 pm, Lionel Thiry wrote:

>
> As always, thanks for the feedback.
>

--
Lionel Thiry

23

> If I missed something, fill me in.

http://www.scons.org/doc/PDF/scons-design.pdf

Yeah, that's the same one I found.

I have forgotten one, the way tasks are executed. You can execute the TDG
in such a way that you don't have to check repeatedly each task to know if
it has already been executed. You just begin at the right starting nodes
and follows the arrows.

Well, that's what I thought until I tried to code that myself. What a
nightmare! :slight_smile:

Hmmm ... I suppose you could do a topological sort on the nodes of the DAG and
execute them in reverse order. There might be some dynamic behavior that is
lost with that approach. And I'm not sure you would do any /less/ checking
doing the sort.

Do you mean that every thing in the list above can already be done with
rake? Or will be added to rake? Will you really add all these features?

If there is interest in any of those features, I would consider implementing
them. Patches and source code contributions are always welcome too. I
remain the final decision maker, but I try to keep an open mind to
suggestions.

Especially about (1), would you plan to decouple Rake interface (the
Rakefiles) and Rake internals? Said another way, would you plan to make
rake usable through a standard ruby script?

  require 'rake'
  # do rake stuff but more explicitly
  # no more implicit tasks or rules
  # no more implicit management of options

See, you half way convinced me already. Actually, you /can/ do this today.
In fact, that's how the unit tests work. But there is some cleanup that
could be done to make the interface better. If you have specific
suggestions, I'm listening.

For example, let's say task1 generate a source file. But then, you want to
compile that source file too and you may don't know in advance how to do
that until you know exactly what kind of source file has been generated.

A possible solution is that when task1 has generated its target, it checks
the type of the result and then generates, on the fly, a task2 in charge of
compiling that file.

file "source_file.c" do
  open("source_file.c", "w") do |f|
    f.puts '#include <stdio.h>'
    f.puts 'int main() { printf("HI\n"); return 0; }'
  end
  puts "Enter name of compiler: "
  compiler = gets.chomp
  file "prog" do |t|
    sh "#{compiler} -o prog source_file.c"
  end
end

file "prog" => ["source_file.c"]

task :default => "prog" do
  sh "prog"
end

···

On Wednesday 06 April 2005 09:09 pm, Lionel Thiry wrote:

--
-- Jim Weirich jim@weirichhouse.org http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

24

Lionel Thiry, April 7:

Nikolai Weibull a écrit :

> Lionel Thiry, April 7:

> > SCons main design doc claims its cornerstone is the management of
> > explicit file dependency DAG.

> Where are you reading this?

http://www.scons.org/doc/PDF/scons-design.pdf
This is the design doc of SCons 0.96, the latest version. Look in chapter
3, see architecture.

Yes, that's what I've read as well.

> What it does differently from make(1) is that it creates a complete
> DAG of all dependencies, i.e., it doesn't rely on recursive
> invocations (like make(1) does). That's the only difference I know
> of,

Mmm, I fell it hard to tell where is the difference between your
statement and mine.

Eh, you were saying that there was a difference between SCons and
make(1) when there really is none. The only difference is the one I
stated above and that difference is only true because most people
misuse make(1) by invoking it recursively. Make(1) can be used without
recursive invocations and then works in the same manner as SCons.

So, as I stated about 10-20 mails back in this thread, there is no
diffence between what SCons does and what make(1) does,
        nikolai

P.S.
You can always check out
http://www.canb.auug.org.au/~millerp/rmch/recu-make-cons-harm.html
for a discussion about how to not use make(1). (Some would still argue
that this doesn't matter much and that recursive invocations are
fine...they are wrong.)
D.S.

···

--
Nikolai Weibull: now available free of charge at http://bitwi.se/\!
Born in Chicago, IL USA; currently residing in Gothenburg, Sweden.
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

25

You can do this with Rant. Short example:

    require 'rant/rantlib'

    rac = Rant::RantApp.new
    cx = rac.context

    # you can call all methods on cx which you'd call
    # directly in an Rantfile
    cx.gen Rant::Generators::Rule, '.o' => '.c' do |t|
        cx.sys "cc -c -o #{t.name} #{t.source}"
    end

    tasks_a = rac.resolve 'a.o'
    # run all tasks for 'a.o', in this case it will be only one task
    tasks_a.each { |t| t.invoke }

    cx.task :clean do
        cx.rm_f Dir["*.o"]
    end

    # rac2 runs in directory
    rac2 = Rant::RantApp.new
    rac2.rootdir = "directory"
    # since we didn't define any task, it looks for an Rantfile
    # in directory
    if rac2.run == 0
       # success
    else
       # failure
    end

    # We defined tasks for rac, so it doesn't look for an Rantfile.
    # We could explicitely load one:
    # cx.source "Rantfile"
    rac.run

In this manner, you can manipulate Rant in many different ways and adopt it
for your current needs.

Stefan

···

On Thursday 07 April 2005 03:09, Lionel Thiry wrote:

require 'rake'
# do rake stuff but more explicitly
# no more implicit tasks or rules
# no more implicit management of options

Not being able to do this is what disturbs me the most about rake.

26

(I'm sorry, I deleted earlier messages in this thread and suddenly spotted these lines, so ignore me if what I'm about to say has nothing to do with the above context.)

It sounds like you may be trying to solve something I worked on for another project long ago - how to traverse a directed graph of dependencies with minimal visitation. (If I know that I'm going to have to visit another node later on anyhow, don't do it now.)

For example, if "A->B" means that B depends on A and should be re-evaluated if A changes, and you have a dependency list like:

A->D
B->C
A->B
C->D

Then a naive traversal when A changes might be:
D, B, C, D

...which would be inefficient.

My solution to this problem was to pre-crawl the graph (and my graph allowed for cyclic sections, so I had to detect them) and create, for each node, an "update chain" of all the nodes that need to be visited for each node that may change. You can then walk that chain from back to front and throw out any nodes which have already been seen.

The end result are simple pre-computed chains that are fast to traverse when the time comes to change a node. (In my case, the problem was for Excel-like functionality in web pages, running and re-running multiple dependent formulae as values change in various fields.)

I have more information on the problem while I was solving it here:
http://phrogz.net/nodes/traversingdirectedgraph.asp
and had been thinking of porting the solution to Ruby anyhow.

···

On Apr 6, 2005, at 10:56 PM, Jim Weirich wrote:

On Wednesday 06 April 2005 09:09 pm, Lionel Thiry wrote:

I have forgotten one, the way tasks are executed. You can execute the TDG
in such a way that you don't have to check repeatedly each task to know if
it has already been executed. You just begin at the right starting nodes
and follows the arrows.

Well, that's what I thought until I tried to code that myself. What a
nightmare! :slight_smile:

Hmmm ... I suppose you could do a topological sort on the nodes of the DAG and
execute them in reverse order. There might be some dynamic behavior that is
lost with that approach. And I'm not sure you would do any /less/ checking
doing the sort.

--
"When I am working on a problem I never think about beauty. I only think about how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong."
- R. Buckminster Fuller

27

Jim Weirich a écrit :

I have forgotten one, the way tasks are executed. You can execute the TDG
in such a way that you don't have to check repeatedly each task to know if
it has already been executed. You just begin at the right starting nodes
and follows the arrows.

Well, that's what I thought until I tried to code that myself. What a
nightmare! :slight_smile:

Hmmm ... I suppose you could do a topological sort on the nodes of the DAG and execute them in reverse order.

Not a good idea when combined with multithreading. (or I haven't found how to do)

There might be some dynamic behavior that is lost with that approach.

And I personnaly wouldn't like to lose that "some dynamic behavior".

And I'm not sure you would do any /less/ checking doing the sort.

I'm slowly thinking the same as you.

Do you mean that every thing in the list above can already be done with
rake? Or will be added to rake? Will you really add all these features?

If there is interest in any of those features, I would consider implementing them. Patches and source code contributions are always welcome too. I remain the final decision maker, but I try to keep an open mind to suggestions.

Ok. I'll think about it. :slight_smile:

Especially about (1), would you plan to decouple Rake interface (the
Rakefiles) and Rake internals? Said another way, would you plan to make
rake usable through a standard ruby script?

require 'rake'
# do rake stuff but more explicitly
# no more implicit tasks or rules
# no more implicit management of options

See, you half way convinced me already. Actually, you /can/ do this today. In fact, that's how the unit tests work. But there is some cleanup that could be done to make the interface better. If you have specific suggestions, I'm listening.

Ok. I'll think about suggestions (and patches) and propose them to you on the Rake mailing list whenever I have one.

···

On Wednesday 06 April 2005 09:09 pm, Lionel Thiry wrote:

--
Lionel Thiry

28

Gavin Kistner said:

(I'm sorry, I deleted earlier messages in this thread and suddenly
spotted these lines, so ignore me if what I'm about to say has nothing
to do with the above context.)

No, it sounds like you are right on context.

It sounds like you may be trying to solve something I worked on for
another project long ago - how to traverse a directed graph of
dependencies with minimal visitation. (If I know that I'm going to have
to visit another node later on anyhow, don't do it now.)

[...]

My solution to this problem was to pre-crawl the graph (and my graph
allowed for cyclic sections, so I had to detect them) and create, for
each node, an "update chain" of all the nodes that need to be visited
for each node that may change. You can then walk that chain from back
to front and throw out any nodes which have already been seen.

[...]

I have more information on the problem while I was solving it here:
Traversing a Directed Graph

Thanks Gavin. I took a look at your reference. Indeed, it looks like you
are doing a topological sort of the nodes before executing (cf.
http://www.cs.sunysb.edu/~algorith/files/topological-sorting.shtml\). The
algorithm is a bit different than what I have used in the past, but the
result is the same: an ordering of nodes where all the dependents of node
x are to the right of node x.

(Aside: Rubygems uses a topological sort to determine the best order to
remove a set of installed gems. Look at the dependency_order method here:
http://rubyurl.com/wRkVa [1])

The key is that you have to pre-crawl the graph (i.e. sort the nodes)
before using the resulting ordered node list.

Rake does not do a pre-crawl, but marks nodes as visited as it traverses
the DAG. This is similar to the topological sort, except that Rake does
it depth-first rather than breadth-first. The end amount of overall work
is about the same, its just that Rake interweaves the two phases into one.

···

--
-- Jim Weirich jim@weirichhouse.org http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

[1]
http://rubyforge.org/cgi-bin/viewcvs.cgi/rubygems/lib/rubygems/dependency_list.rb?rev=1.3&cvsroot=rubygems&content-type=text/vnd.viewcvs-markup\).

29

Lionel Thiry wrote:

Jim Weirich a écrit :

Hmmm ... I suppose you could do a topological sort on the nodes of the DAG and execute them in reverse order.

Not a good idea when combined with multithreading. (or I haven't found how to do)

Some "make" implementations already supports multi-threaded execution just fine. You just have to finish all the dependent tasks, i.e. join all the threads, before proceding with the next higher level of dependencies.

···

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/&gt;