Note that Nix doesn't use a shell to execute things, it uses raw `exec` calls (each .drv file specifies the absolute path to an executable, a list of argument strings, and a set of environment variable strings). Though in practice, most .drv files specify a bash executable ;)
Yeah, well, it's a little bit more than that.
Two things come to mind that don't neatly fit the DAG mental framework:
- dynamically generated dependencies (e.g. when you compile a C++ file only to discover that it #includes something and therefore has a dependency on that thing, and therefore the DAG has to be updated on the fly). Creating them by hand is horribly tedious, and/or borderline impossible (#includes that #include other #include ad infinitum)
- reproducible builds, where a build system is capable of rebuilding a binary from scratch down to having not a single different bit in the final output assuming the leaves of the DAG haven't changed. A desirable feature that is darn near impossible to do unless you pair the DAG with something else.- defining different build types (debug/release)
- optionally building and running tests
- incremental builds (detecting what has changed)
That doesn't necessarily run counter to the concept of a DAG, but the organizational structures to manage this is what makes the build system. Topologically sorting the dependencies isn't the hard part. That's why make isn't a build system. It is the generic DAG runner, but that's not sufficient.
True in the broadest sense, but there are choices to be done regarding the possibility of discovering what the graph is or has become on the fly and the propagation directions. See “Build systems à la carte”[1,2] for a systematic exploration.
(See also a neighbouring comment[3] re how the discourse structure[4] of the build script might be important in a way orthogonal to these execution-engine issue. The boundary between the build system and the build tool can be drawn in very different places here.)
[1] https://dx.doi.org/10.1145/3236774
[2] https://youtu.be/BQVT6wiwCxM
[3] https://news.ycombinator.com/item?id=36749885
[4] https://brenocon.com/blog/2009/09/dont-mawk-awk-the-fastest-...
There is: tsort. It's a POSIX utility, even, not just a GNU or BSD utility.
0001 GOTO 0002
0002 GOTO 0001
(begin
(0001 GOTO 0002)
(0002 GOTO 0001))
V: (0001, 0002) E: ([0001, 0002], [0002, 0001])
But really I was just being sarcastic. Builds are "just" DAGs with syntactic sugar just like programs are "just" DAGs with syntactic sugar. That's one possible abstraction and one that is inherently lossy, because what "sugar" is available is the actual meat that makes one build system useful and another terrible. And one actually awful limitation is acylicity, since any build system will eventually deal with it (and outright forbidding of it makes your build system incapable of representing certain builds, just like acyclicity fundamentally limits a program's execution)
You can represent pretty much any data model as a graph, that doesn't really address the problem.
A build system modelling itself as a DAG, on the other hand, is very consciously taking on acyclicity as a feature.
I am curious what builds would need to be cyclic. Artifact A is built from B and C, where C is built from D and A? Does that happen in any well-designed build?
> I am curious what builds would need to be cyclic.
Compilers, interpreters, kernels, and the things that depend on them. So lots.
> Does that happen in any well-designed build?
Whether or not it's 'well designed' is irrelevant, the question is 'does it need to be possible' because even if it's rare it's still present in a lot of foundational software, notably GCC.
For an excellent synthesis of what Makes a build system, I can't recommend the 2018 paper "Build Systems A La Carte" enough:
https://www.microsoft.com/en-us/research/uploads/prod/2018/0...
By Andrey Mokhov, Neil Mitchell (now working at Meta on the Buck2 build system) and Simon Peyton Jones (one of the founders of Haskell)