As an intensive (and reluctant) user of GNU Make, I keep looking for a more modern replacement. Redo is not it.
Make is really a complicated combination of these components:
- a dependency definition language with in-place evaluation and half-assed wildcards
- A functional language with extremely limited datatypes (effectively just space-separated strings)
- a clunky macro system
- A "distributed" topological execution engine (did you know Make can coordinate job slots across recursive executions of Make? It's impressive! And shouldn't have to exist!) [1]
All the alternative build systems wisely choose to tackle only some of these features. Redo is interesting in that it's a minimal system that leans on existing Unix tools to fill the gaps, but I can't say I'm impressed with using Shell as the scripting language, though it is arguably more useful than Make's home-grown language that too few people know. Edit: actually, redo's doesn't enforce Shell, it can be any executable. That's more interesting, maybe (flexibility also introduces complexity!)
The most interesting development in this space is the paper "Build Systems A La Carte" [2] by Mokhov, Mitchell, & Peyton Jones, who did a great job of breaking down build systems to their fundamental concepts, and along the way found one particular point of the design space that wasn't fulfilled (Table 2, p79:16). Unfortunately, I fear it'll be some years before something production-ready emerges from that research, (and I'm sure I'll be grumpy about some of their implementation details anyhow! Build systems do not a happy developer make)
Not just a functional language -- I found that my ability to write maintainable (and performance) Makefiles drastically improved when I began to think of Make as a Prolog/Datalog variant with particularly heinous syntax and very limited constraint resolution.
I second Bazel. People keep on mentioning how steep the learning curve is, but the conceptual model is really simple, elegant, and intuitive.
What is steep is the technical know-hows:
1. When things don't work as expected. For example, while it worked flawlessly with languages that it natively support such as Java, that wasn't the case for other languages such as Javascript or Python.
2. When you have to do something advanced such as building custom Bazel rule. You'll need to understand Bazel internals and unfortunately the documentation isn't very intuitive and also somewhat sparse.
I see GNU Make as sitting on the opposite end of a spectrum than Git. Git is fascinating as a sophisticated, featureful system emerging from a simple fundamental concept (Merkle tree of file hashes), whereas Make is a mish-mash of concepts cobbled together to expose a particular set of user features (describe and execute a graph of executions in a factorized way).
Git emerged decades after other version control systems were first invented, and found a neat abstraction that covered the space.
That's why I have such hope for the BSalC paper and what can emerge from it.
I think not adding an arbitrary new declarative language is good design feature of redo. I think redo has other issues but personally redo with bash as the underlying glue works a lot better than make (in terms of maintaining more complete DAGs). Now I'm not saying it wouldn't be nice to get a declarative language which works WITH redo, but it would be important to keep it separate.
One thing redo is missing for me is support for building things in a different directory. It's a nice-to-have feature but it's difficult to envision how such a redo would work. Really overlays actually solve this problem, although a fuse based overlayfs would also be nice (so you can use it without needing to escalate privileges).
Have you given bazel a serious look? It hits quite a few of the points you mention. There's a steep learning curve and you kind of have to go all in with it, but once you're there it's quite nice.
I skimmed the paper. I use Make, extensively, but in a way I generally don’t see in the wild (for C/++):
1. I convert all paths to abspaths;
2. All intermediate products go into a temp dir;
3. All recipes are functions;
4. The set of objects are defined by a “find . -name ‘…’” for C sources;
5. Every C file depends on every header file in the repo;
6. Use ccache; and,
7. Deterministic build.
My big work project is ~20mm loc, including ~65 FW images (embedded OSes). Incremental compilation is ~300ms. Clean rebuilds are 30-40s; scratch builds are 8m. (All of this on ~4 year old MBP.)
Obviously, there are some design tricks to get raw compilation speed up — naive C++ only compiles at ~3kloc/s; it’s possible to get that up to 100kloc/s.
"As an intensive (and reluctant) user of GNU Make, I keep looking for a more modern replacement."
Unless I am mistaken, the author of https://cr.yp.to/redo.html never implemented the idea. He has since used only the Bourne shell and standard UNIX utilties as a build system instead of make. For example, consider the "do" script in this project: https://nacl.cr.yp.to
The "do" script was written circa 2011. The idea for "redo" was published circa 2003. The idea for "make" dates back to 1976. GNU Make was written around 1989.
For the avoidance of doubt, I am not suggesting any of these build system ideas or implementations are better or worse than the others. That is for the reader to decide. I am only pointing out which one is the most recent, or most modern, if we use the word "modern" according to its dictionary definition.
I’m quite happy with ruby’s rake for my needs. I mostly use it to define pipelines, often involving data downloads and transformations into datasets for ML. It works well when you work with files, preferably containing a single or few entities each. Have been meaning to wrap some tools to make it handle databases into an extension.
I don't like using tabs in Makefile syntax. Tabs are in many cases (especially on print) indistinguishable from spaces.
Also, any "make" program for C should automatically detect dependencies between files because this information is present in the code and it doesn't make sense to duplicate it.
Gradle is a good make replacement as well. The kotlin DSL is much more readable and easier to follow than makefiles and has a lot of additional features.
> All the alternative build systems wisely choose to tackle only some of these features.
But why should all of these features be tackled by a single piece of software? Especially seeing how Make, in itself, has proven wildly insufficient already... what, 30 years ago, when GNU autotools came onto the scene?
More specifically, why do you find combinations such as meson + ninja, or CMake + ninja, or even CMake + make as superior to just-Make?
Please someone mention Tup and how it can be a reasonable build system. I’ve heard the Fuse dependency is not ideal, though I felt it had a nice UX experience with the Lua config.
Plus it’s worth considering that you can potentially use Fennel to configure the builds (since Fennel compiles to Lua).
I have encountered Tup in the past and could not figure out how to define a "generator". As in: a function that defines how some output can be generated from a certain input running multiple commands. I don't want to copy those commands for every input I need to process.
Edit: Generator is a term typically used in CMake and Meson for this, in Make I'd use a pattern rule mostly.
Chris Forno (jekor) made an implementation of djb's redo in Haskell. The videos of him live coding it are on YouTube, and I recommended it for anyone wanting to learn Haskell.
Not impressed by shell incantations. What would sell such a tool to me is a feature to replace those with new and more intuitive syntax. And a terser one, too.
Holding on to how things are done in the shell is not a thing to be proud of. I think a lot of us around here stopped counting the times we got tripped by globbing, forgetting or misplacing one special character in a ${} block, or quoting.
Let those monstrosities die already. Please.
There's this tool -- https://github.com/ejholmes/walk -- that is pretty good and I liked it but dropped it for the same reasons: it leaves the heavy lifting to you and it depends on your mastery in the black arts.
Now obviously I'm not managing huge projects but nowadays https://github.com/casey/just serves me just fine for everything I need.
Nobody forces you to use any kind of shell with redo. Its .do files can be anything you want: ELF object files, shell scripts, Perl, Python, whatever, just make it executable and obey trivial simple rules (stdout and three arguments).
Did you try https://pydoit.org/, it's a build tool in similar spirit, which allows the actions to be either python-functions or external programs. Try to look past their tutorial 1, I don't know why they mixed in module_imports there, making it look a lot more complicated than what it really is.
Just like tup, redo keeps popping up as a nice conceptual thing, but none of these take off in practice.
For most projects the winning build system is not the most conceptually interesting one, nor the most flexible one. It's the most "convention over configuration" one. This is why Meson has taken the freedesktop/gnome/etc world by storm.
It's not hard to "take over the freedesktop/gnome" world by storm since it's basically the same small group of people who have any power in that world.
File system time stamps are an unreliable way to decide if a target needs to be rebuilt. It doesn't work with distributed builds, it doesn't allow instant rebuilds to help with bisections, various file systems might not have not store the same time attributes, even on the same OS, etc. In my experience (large, mono-repo builds) hashes are the way to go and offer the most portable way to map an artefact to a tree of dependencies.
Another problem which is not discussed and is a very important feature for a modern build engine is "sandboxing" - forcing a build rule to declare all inputs, all outputs and to prevent any other kind of FS access and network access during the run of that command. BuildXL from Microsoft does that. Without sandboxing it's pretty hard to enforce a sane set of rules for building your large project.
The sandboxing restriction is one that merits care for (or not supporting) some use cases. Tup requires declaring all outputs (but not all inputs), which can be inconvenient when a build process creates intermediate or derived files that are tedious to anticipate. [0]
Using filesystem timestamps is a misfeature of THIS particular redo implementation. Almost all the other redo implementations I know of (which are generally also much faster than apenwarr's redo) use a hash if the timestamp has changed.
Also, redo only lets a given .do file produce ONE output from a set of specified inputs. If you want to enforce this, nothing stops you from writing some declarative tool on top of redo (meaning you would replace the shebangs) which implements the sandboxing. Other than that, it's outside of the scope of concerns of a tool such as redo, and adding it would be a misfeature in my opinion (since it's not directly related to handling of the dependency graph).
1. How does redo compare with lower-level build tools such as ninja?
2. Why is it important/worthwhile to create a simplified/elegant version of Make, when for a few decades already, it is customary to write something higher-level that generates Makefiles (or builds in ways other than through Make, like scons or again via ninja)?
3. Is there a redo generator for CMake, and does it have advantages over Makefile generation?
0. I would recommend you actually read about redo yourself. Redo is not just the implementation posted here (which personally I don't like for multiple reasons). Redo is a very simple idea envisioned by DJB a while ago which was never implemented by him properly. You can read more about it here: http://cr.yp.to/redo.html it won't take long.
1. Ninja is not meant to be hand written, redo can be hand written. Ninja verbosely describes your build as flat file containing the description of a DAG and the rules required to traverse it. Redo is a recursive definition, intended to be mostly hand written, which describes your build process. Redo can and should be split up across multiple files.
2. It may be customary to you, but not everyone agrees that the correct solution to building a project is to have a gigantic software suite consume a confusing and abstract configuration file and spit out a bunch of buggy makefiles. There are in fact plenty of people who hand write makefiles, redo fits in that same space. It's easier to hand write, it's easier to fully describe the DAG of your project, it's easier to reason about the build process and it's easier to make sure it is correct.
3. No. It would make no sense to have a redo generator for CMake as it would be severely missing the point of redo. The only reason CMake has generators for anything but ninja is because some people worry about portability to other systems and as such having make is better than nothing.
Not all redo implementations treat $2 the same. Specifically JDEBP's redo differs in that $2 is the extension rather than the part with the extension removed (it's unspecified what $2 is for non default*.do files).
I feel like DJB's ideas behind redo are actually some of his most poorly thought-out ideas. It seems that he thought, 'Make has <problem>. To solve <problem>, a new build system should have <solution>.' In other words, he seems to just used additive solutions instead of subtractive ones. [1]
Most build systems seem to be like that, adding features on top of features. The end result is usually complicated and finicky.
I think that's why build systems are among the software developers hate most. And I do mean hate. (The first time and only time I saw an acquaintance, a normally calm person, have an outburst was talking about a build system.)
I think the ideal build system will be subtractive, not additive.
So I guess this is as good a time as any to talk about my current project, a build system. :)
(Most of this will be copied from two comments I made on lobste.rs.)
First, there is a paper that already lays out the features needed for an optimal build system: A Sound and Optimal Incremental Build System with Dynamic Dependencies. [2] The features are:
1. Dynamic dependencies.
2. Flexible "file stamps."
3. Targets and build scripts are Turing-compete.
That's it. Really.
The first item is needed based on the fact that dependencies can change based on the configuration needed for the build of a package. Say you have a package that needs libcurl, but only if users enable network features.
It is also needed to import targets from another build. I’ll use the libcurl example above. If your package’s build target has libcurl as a dependency, then it should be able to import libcurl’s build files and then continue the build making the dependencies of libcurl’s build target dependencies of your package’s build targets.
In other words, dynamic dependencies allow a build to properly import the builds of its dependencies.
The second item is the secret sauce and is, I believe, the greatest idea from the paper. The paper calls them “file stamps,” and I call them “stampers.” They are basically arbitrary code that returns a Boolean showing whether or not a target needs updating or not.
A Make-like target’s stampers would check if the file mtime is less than any of its dependencies. A more sophisticated one might check that any file attributes of a target’s dependencies have changed. Another might hash a file.
The third is needed because otherwise, you can’t express some builds, but tying it with dynamic dependencies is also the bridge between building in the large (package managers) and building in the small (“normal” build systems).
Why does this tie it all together? Well, first consider trying to implement a network-based caching system. In most build systems, it’s a special thing, but in a build system with the above the things, you just need write a target that:
1. Uses a custom stamper that checks the hash of a file, and if it is changed, checks the network for a cached built version of the new version of the file.
2. If such a cache version exists, make updating that target mean downloading the cache version; otherwise, make updating the target mean building it as normal.
Voila! Caching in the build system with no special code.
That, plus being able to import targets from other build files is what ties packages together and what allows the build system to tie package management and software building together.
I’ll leave it as an exercise to the reader to figure out how such a design could be used to implement a Nix-like package manager.
(By the way, the paper uses special code and a special algorithm for handling circular dependencies. I think this is a bad idea. I think this problem is neatly solved by being able to run arbitrary code. Just put mutually dependent targets into the same target, which means targets need to allow multiple outputs, and loop until they reach a fixed point.)
So how would this build system fit into the table (page 27, Table 2) of the "Build Systems a la Carte" paper?
It fits 8 of the 12 slots.
This is done with another feature: power-limiting. It will be possible to tell my build system to restrict itself, and any attempt to go beyond would result in an error. (This is useful in many situations, but especially to help new people in a team.) My build system can restrict itself along three axes: dependencies, stampers, and code.
To implement dynamic dependencies, you need a suspending scheduler, so obviously, my build system
The stampers are actually what defines the rebuilding strategy (and it can be different for each and every target), so there could be stampers for all of the rebuilding strategies.
This, technically, my build system could fill all four slots under the “Suspending” scheduler strategy in the far right column in table 2 on page 27.
In fact, packages will probably be build files that use deep constructive traces, thus making my build system act like Nix for packages, while in-project build files will use any of the other three strategies as appropriate. For example, a massive project run by Google would probably use “Constructive Traces” for caching and farming out to a build farm, medium projects would probably use “Verifying Traces” to ensure the flakiness of mtime didn’t cause unnecessary cleans, and small projects would use “Dirty Bit” because the build would be fast enough that flakiness wouldn’t matter.
This will be what makes my build system solve the problem of scaling from the smallest builds [3] to medium builds [4] to the biggest builds [5]. That is, if it actually does solve the scaling problem, which is a BIG “if”. I hope and think it will, but ideas are cheap; execution is everything.
Additionally, you can turn off dynamic dependencies, which would effectively make my build system use the “Topological” scheduler strategy. Combine that with the ability to fill all four rebuilder strategy slots, and my build system will be able to fill 8 out of the 12.
Filling the other four is not necessary because anything you can do with a “Restarting” scheduler you can do with a “Suspending” scheduler and Turing-complete code. (Just use a loop or a stamper recheck as necessary to simulate restarting.) And restarting can be more complicated to implement. So in essence, my build system will fill every category in the BSalC paper.
And I could do that because I took things away instead of adding more.
Aside from the fact that DJB barely specified redo to the point where you could make accusations claiming it did or did not do something, I think there are implementations of redo which are capable of fitting the requirements you specify.
1. Redo doesn't give you the tools to have dynamic dependencies for example, but it also doesn't concern itself with those and doesn't prevent you from having them. I have a small project which has dynamic dependencies (not system dependencies but just configuration options) and handles them gracefully with redo (without ever needing a make clean).
2. Flexible file stamps are something which you can implement on some redo implementation using a combination of redo-always and redo-stamp.
3. The targets and build scripts being turing complete is something which redo doesn't specify but that is the intentional use of redo.
That being said, I think there is a place for something even more BASIC than redo which can be used more directly to implement what you've described while also being flexible enough to build redo on top of. It has given me things to think about.
[+] [-] AceJohnny2|4 years ago|reply
Make is really a complicated combination of these components:
- a dependency definition language with in-place evaluation and half-assed wildcards
- A functional language with extremely limited datatypes (effectively just space-separated strings)
- a clunky macro system
- A "distributed" topological execution engine (did you know Make can coordinate job slots across recursive executions of Make? It's impressive! And shouldn't have to exist!) [1]
All the alternative build systems wisely choose to tackle only some of these features. Redo is interesting in that it's a minimal system that leans on existing Unix tools to fill the gaps, but I can't say I'm impressed with using Shell as the scripting language, though it is arguably more useful than Make's home-grown language that too few people know. Edit: actually, redo's doesn't enforce Shell, it can be any executable. That's more interesting, maybe (flexibility also introduces complexity!)
The most interesting development in this space is the paper "Build Systems A La Carte" [2] by Mokhov, Mitchell, & Peyton Jones, who did a great job of breaking down build systems to their fundamental concepts, and along the way found one particular point of the design space that wasn't fulfilled (Table 2, p79:16). Unfortunately, I fear it'll be some years before something production-ready emerges from that research, (and I'm sure I'll be grumpy about some of their implementation details anyhow! Build systems do not a happy developer make)
[1] https://www.gnu.org/software/make/manual/html_node/Job-Slots...
[2] https://www.microsoft.com/en-us/research/uploads/prod/2018/0...
[+] [-] woodruffw|4 years ago|reply
[+] [-] lolski|4 years ago|reply
What is steep is the technical know-hows:
1. When things don't work as expected. For example, while it worked flawlessly with languages that it natively support such as Java, that wasn't the case for other languages such as Javascript or Python.
2. When you have to do something advanced such as building custom Bazel rule. You'll need to understand Bazel internals and unfortunately the documentation isn't very intuitive and also somewhat sparse.
[+] [-] AceJohnny2|4 years ago|reply
Git emerged decades after other version control systems were first invented, and found a neat abstraction that covered the space.
That's why I have such hope for the BSalC paper and what can emerge from it.
[+] [-] Arch-TK|4 years ago|reply
One thing redo is missing for me is support for building things in a different directory. It's a nice-to-have feature but it's difficult to envision how such a redo would work. Really overlays actually solve this problem, although a fuse based overlayfs would also be nice (so you can use it without needing to escalate privileges).
[+] [-] qbasic_forever|4 years ago|reply
[+] [-] thechao|4 years ago|reply
1. I convert all paths to abspaths;
2. All intermediate products go into a temp dir;
3. All recipes are functions;
4. The set of objects are defined by a “find . -name ‘…’” for C sources;
5. Every C file depends on every header file in the repo;
6. Use ccache; and,
7. Deterministic build.
My big work project is ~20mm loc, including ~65 FW images (embedded OSes). Incremental compilation is ~300ms. Clean rebuilds are 30-40s; scratch builds are 8m. (All of this on ~4 year old MBP.)
Obviously, there are some design tricks to get raw compilation speed up — naive C++ only compiles at ~3kloc/s; it’s possible to get that up to 100kloc/s.
[+] [-] eddieh|4 years ago|reply
[+] [-] 1vuio0pswjnm7|4 years ago|reply
Unless I am mistaken, the author of https://cr.yp.to/redo.html never implemented the idea. He has since used only the Bourne shell and standard UNIX utilties as a build system instead of make. For example, consider the "do" script in this project: https://nacl.cr.yp.to
The "do" script was written circa 2011. The idea for "redo" was published circa 2003. The idea for "make" dates back to 1976. GNU Make was written around 1989. For the avoidance of doubt, I am not suggesting any of these build system ideas or implementations are better or worse than the others. That is for the reader to decide. I am only pointing out which one is the most recent, or most modern, if we use the word "modern" according to its dictionary definition.
[+] [-] KarlKemp|4 years ago|reply
[+] [-] codedokode|4 years ago|reply
Also, any "make" program for C should automatically detect dependencies between files because this information is present in the code and it doesn't make sense to duplicate it.
[+] [-] tn1|4 years ago|reply
[1] http://makepp.sourceforge.net/
[+] [-] hv42|4 years ago|reply
[+] [-] agumonkey|4 years ago|reply
[+] [-] einpoklum|4 years ago|reply
But why should all of these features be tackled by a single piece of software? Especially seeing how Make, in itself, has proven wildly insufficient already... what, 30 years ago, when GNU autotools came onto the scene?
More specifically, why do you find combinations such as meson + ninja, or CMake + ninja, or even CMake + make as superior to just-Make?
[+] [-] seanstrom|4 years ago|reply
Plus it’s worth considering that you can potentially use Fennel to configure the builds (since Fennel compiles to Lua).
Tup: https://github.com/gittup/tup
Fennel: https://fennel-lang.org/
[+] [-] w4rh4wk5|4 years ago|reply
Edit: Generator is a term typically used in CMake and Meson for this, in Make I'd use a pattern rule mostly.
[+] [-] mavelikara|4 years ago|reply
https://www.youtube.com/watch?v=zZ_nI9E9g0I&list=PLxj9UAX4Em...
[+] [-] pdimitar|4 years ago|reply
Holding on to how things are done in the shell is not a thing to be proud of. I think a lot of us around here stopped counting the times we got tripped by globbing, forgetting or misplacing one special character in a ${} block, or quoting.
Let those monstrosities die already. Please.
There's this tool -- https://github.com/ejholmes/walk -- that is pretty good and I liked it but dropped it for the same reasons: it leaves the heavy lifting to you and it depends on your mastery in the black arts.
Now obviously I'm not managing huge projects but nowadays https://github.com/casey/just serves me just fine for everything I need.
[+] [-] stargrave|4 years ago|reply
[+] [-] melony|4 years ago|reply
[+] [-] Too|4 years ago|reply
[+] [-] floatboth|4 years ago|reply
For most projects the winning build system is not the most conceptually interesting one, nor the most flexible one. It's the most "convention over configuration" one. This is why Meson has taken the freedesktop/gnome/etc world by storm.
[+] [-] Arch-TK|4 years ago|reply
[+] [-] redleader55|4 years ago|reply
Another problem which is not discussed and is a very important feature for a modern build engine is "sandboxing" - forcing a build rule to declare all inputs, all outputs and to prevent any other kind of FS access and network access during the run of that command. BuildXL from Microsoft does that. Without sandboxing it's pretty hard to enforce a sane set of rules for building your large project.
[+] [-] Nzen|4 years ago|reply
[0] https://groups.google.com/g/tup-users/c/umW73zR5JKc?pli=1 . ex java creates numbered .class files for anonymous classes declared in a larger java file. In fairness, while looking, they may have relaxed some of that since I last looked with a transient flag https://github.com/gittup/tup/issues/405
[+] [-] Arch-TK|4 years ago|reply
Also, redo only lets a given .do file produce ONE output from a set of specified inputs. If you want to enforce this, nothing stops you from writing some declarative tool on top of redo (meaning you would replace the shebangs) which implements the sandboxing. Other than that, it's outside of the scope of concerns of a tool such as redo, and adding it would be a misfeature in my opinion (since it's not directly related to handling of the dependency graph).
[+] [-] einpoklum|4 years ago|reply
1. How does redo compare with lower-level build tools such as ninja?
2. Why is it important/worthwhile to create a simplified/elegant version of Make, when for a few decades already, it is customary to write something higher-level that generates Makefiles (or builds in ways other than through Make, like scons or again via ninja)?
3. Is there a redo generator for CMake, and does it have advantages over Makefile generation?
[+] [-] Arch-TK|4 years ago|reply
1. Ninja is not meant to be hand written, redo can be hand written. Ninja verbosely describes your build as flat file containing the description of a DAG and the rules required to traverse it. Redo is a recursive definition, intended to be mostly hand written, which describes your build process. Redo can and should be split up across multiple files.
2. It may be customary to you, but not everyone agrees that the correct solution to building a project is to have a gigantic software suite consume a confusing and abstract configuration file and spit out a bunch of buggy makefiles. There are in fact plenty of people who hand write makefiles, redo fits in that same space. It's easier to hand write, it's easier to fully describe the DAG of your project, it's easier to reason about the build process and it's easier to make sure it is correct.
3. No. It would make no sense to have a redo generator for CMake as it would be severely missing the point of redo. The only reason CMake has generators for anything but ninja is because some people worry about portability to other systems and as such having make is better than nothing.
[+] [-] stargrave|4 years ago|reply
[+] [-] Arch-TK|4 years ago|reply
[+] [-] gavinhoward|4 years ago|reply
Most build systems seem to be like that, adding features on top of features. The end result is usually complicated and finicky.
I think that's why build systems are among the software developers hate most. And I do mean hate. (The first time and only time I saw an acquaintance, a normally calm person, have an outburst was talking about a build system.)
I think the ideal build system will be subtractive, not additive.
So I guess this is as good a time as any to talk about my current project, a build system. :)
(Most of this will be copied from two comments I made on lobste.rs.)
First, there is a paper that already lays out the features needed for an optimal build system: A Sound and Optimal Incremental Build System with Dynamic Dependencies. [2] The features are:
1. Dynamic dependencies.
2. Flexible "file stamps."
3. Targets and build scripts are Turing-compete.
That's it. Really.
The first item is needed based on the fact that dependencies can change based on the configuration needed for the build of a package. Say you have a package that needs libcurl, but only if users enable network features.
It is also needed to import targets from another build. I’ll use the libcurl example above. If your package’s build target has libcurl as a dependency, then it should be able to import libcurl’s build files and then continue the build making the dependencies of libcurl’s build target dependencies of your package’s build targets.
In other words, dynamic dependencies allow a build to properly import the builds of its dependencies.
The second item is the secret sauce and is, I believe, the greatest idea from the paper. The paper calls them “file stamps,” and I call them “stampers.” They are basically arbitrary code that returns a Boolean showing whether or not a target needs updating or not.
A Make-like target’s stampers would check if the file mtime is less than any of its dependencies. A more sophisticated one might check that any file attributes of a target’s dependencies have changed. Another might hash a file.
The third is needed because otherwise, you can’t express some builds, but tying it with dynamic dependencies is also the bridge between building in the large (package managers) and building in the small (“normal” build systems).
Why does this tie it all together? Well, first consider trying to implement a network-based caching system. In most build systems, it’s a special thing, but in a build system with the above the things, you just need write a target that:
1. Uses a custom stamper that checks the hash of a file, and if it is changed, checks the network for a cached built version of the new version of the file.
2. If such a cache version exists, make updating that target mean downloading the cache version; otherwise, make updating the target mean building it as normal.
Voila! Caching in the build system with no special code.
That, plus being able to import targets from other build files is what ties packages together and what allows the build system to tie package management and software building together.
I’ll leave it as an exercise to the reader to figure out how such a design could be used to implement a Nix-like package manager.
(By the way, the paper uses special code and a special algorithm for handling circular dependencies. I think this is a bad idea. I think this problem is neatly solved by being able to run arbitrary code. Just put mutually dependent targets into the same target, which means targets need to allow multiple outputs, and loop until they reach a fixed point.)
So how would this build system fit into the table (page 27, Table 2) of the "Build Systems a la Carte" paper?
It fits 8 of the 12 slots.
This is done with another feature: power-limiting. It will be possible to tell my build system to restrict itself, and any attempt to go beyond would result in an error. (This is useful in many situations, but especially to help new people in a team.) My build system can restrict itself along three axes: dependencies, stampers, and code.
To implement dynamic dependencies, you need a suspending scheduler, so obviously, my build system
The stampers are actually what defines the rebuilding strategy (and it can be different for each and every target), so there could be stampers for all of the rebuilding strategies.
This, technically, my build system could fill all four slots under the “Suspending” scheduler strategy in the far right column in table 2 on page 27.
In fact, packages will probably be build files that use deep constructive traces, thus making my build system act like Nix for packages, while in-project build files will use any of the other three strategies as appropriate. For example, a massive project run by Google would probably use “Constructive Traces” for caching and farming out to a build farm, medium projects would probably use “Verifying Traces” to ensure the flakiness of mtime didn’t cause unnecessary cleans, and small projects would use “Dirty Bit” because the build would be fast enough that flakiness wouldn’t matter.
This will be what makes my build system solve the problem of scaling from the smallest builds [3] to medium builds [4] to the biggest builds [5]. That is, if it actually does solve the scaling problem, which is a BIG “if”. I hope and think it will, but ideas are cheap; execution is everything.
Additionally, you can turn off dynamic dependencies, which would effectively make my build system use the “Topological” scheduler strategy. Combine that with the ability to fill all four rebuilder strategy slots, and my build system will be able to fill 8 out of the 12.
Filling the other four is not necessary because anything you can do with a “Restarting” scheduler you can do with a “Suspending” scheduler and Turing-complete code. (Just use a loop or a stamper recheck as necessary to simulate restarting.) And restarting can be more complicated to implement. So in essence, my build system will fill every category in the BSalC paper.
And I could do that because I took things away instead of adding more.
[1]: https://www.nature.com/articles/d41586-021-00592-0
[2]: https://www.informatik.uni-marburg.de/~seba/publications/plu...
[3]: https://neilmitchell.blogspot.com/2021/09/small-project-buil...
[4]: https://neilmitchell.blogspot.com/2021/09/reflecting-on-shak...
[5]: https://neilmitchell.blogspot.com/2021/09/huge-project-build...
[+] [-] Arch-TK|4 years ago|reply
1. Redo doesn't give you the tools to have dynamic dependencies for example, but it also doesn't concern itself with those and doesn't prevent you from having them. I have a small project which has dynamic dependencies (not system dependencies but just configuration options) and handles them gracefully with redo (without ever needing a make clean).
2. Flexible file stamps are something which you can implement on some redo implementation using a combination of redo-always and redo-stamp.
3. The targets and build scripts being turing complete is something which redo doesn't specify but that is the intentional use of redo.
That being said, I think there is a place for something even more BASIC than redo which can be used more directly to implement what you've described while also being flexible enough to build redo on top of. It has given me things to think about.
[+] [-] ghoward|4 years ago|reply