Implement the build process as an incremental computation graph

[hllhnd]

To avoid hardcoding the build process, Loki should use a directed acyclic graph (DAG) for incrementally computing the build's flow.

This should allow the build process to be highly flexible and parallelizable.

There exist many frameworks for this task, but none of them are ideal for Loki. A home-rolled solution would be best.

Help with this would be very much appreciated!

[cndofx]

Could you list some of the existing frameworks and explain why they aren't ideal?

[hllhnd]

salsa - Salsa does not seem to be oriented towards dependency graphs (or graphs in general), and from what I can see does not support parallelism, which is essential to achieve optimal build performance. Anything that Loki can run in parallel should be run in parallel.

Salsa seems to be more geared towards reusing computations rather than optimizing the execution of these computations. Even if parallelism and graph support were added it would be at odds with Salsa's purpose.

DICE - This is pretty close to what Loki needs, being made for a build system and supporting graph-like structures and parallelism.

Unfortunately it's pinned to a relatively old nightly version which prevents it from being compiled as a dependency on any other version. It has no stable releases, being available exclusively in the buck2 repository.

The documentation is surprisingly good given that it is A. from a for-profit company and B. clearly only made a separate crate for the sake of making it a separate crate. They detail what went into making it in the docs, which may be useful for Loki to learn from.

depends - This library is pretty new and also seems to do what a build system needs, but the API does not seem appropriate for Loki.

The book has two articles on coping with boilerplate.

The religious use of Rc<T> and use of hashing for tracking recomputations make it very "extra" for what Loki is accomplishing. There's also no mention of support for parallelism to my knowledge.

petgraph - I'm obligated to mention petgraph as it's a very popular library for general purpose graph work.

Unfortunately using it would provide nothing in terms of incremental computation--the parallelism and incremental computation bits would have to be done manually--and, at that point, why not roll the graph ourselves?