Re: Dependency tree resolver in Lua?

[David Given <dg@...>]

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.

Note that this is not how Prime Mover's dependency analysis works; it
just does a crude depth-first search of the dependency tree, checking
timestamps for each node and building the node if necessary. (Prime
Mover's requirements are a bit weird because each build node can be
visited multiple times, and some dependency information is only
available after the node is built --- dynamically generated C files, for
example.)

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│ "Thou who might be our Father, who perhaps may be in Heaven, hallowed
│ be Thy Name, if Name Thou hast and any desire to see it hallowed..."
│ --- _Creatures of Light and Darkness_, Roger Zelazny

Attachment: signature.asc
Description: OpenPGP digital signature