[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Dependency tree resolver in Lua?
- From: Anatol Pomozov <anatol.pomozov@...>
- Date: Mon, 7 Feb 2011 09:23:19 -0800
On Mon, Feb 7, 2011 at 3:58 AM, David Given <firstname.lastname@example.org> 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  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
, and the result at this page