Re: Dependency tree resolver in Lua?

[Anatol Pomozov <anatol.pomozov@...>]

On Mon, Feb 7, 2011 at 3:58 AM, David Given <dg@cowlark.com> wrote:
> On 07/02/11 11:27, Alexander Gladysh wrote:
> [...]
>> All that talk about build systems reminded me to ask a question :-)
>>
>> Is there a generic-enough dependency tree resolver module for Lua?
>
> Oddly enough, I just wrote one --- I don't know whether it's *right*,
> but it appears to do the job I need.
>
> The code is trivial: construct a directed graph of dependencies, where
> each node has edges pointing at the nodes it depends on. Now search the
> graph for a node with no parents. Remove the node (while building,
> logging, outputting it, or whatever). Repeat until there are no nodes
> left. For extra credit check the graph for cycles first.

Slightly off-topic. Almost every build tool uses depth-search
algorithm you described. They build full project's graph then visit
all nodes and find those ones that need to be rebuilt. And it might be
a problem for incremental builds on large projects. Incremental builds
usually change only small portion of a graph and there is no need to
manipulate whole graph of dependencies.

There is an interesting build tool called Tup [1] that uses reverse
algorithm. First it finds all files has been changed and then
constructs subgraph that needs to be rebuild. It is a huge time-saver
for incremental builds in large projects. See more info in this paper
[2], and the result at this page [3]

1] http://gittup.org/tup/
2] http://gittup.org/tup/build_system_rules_and_algorithms.pdf
3] http://gittup.org/tup/make_vs_tup.html