Redo: A recursive, general-purpose build system

make doesn't really understand C or C dependencies, but the compilers usually do. Here is a minimal example that will take care of dependencies by passing -MD -MP to gcc or clang. The dependencies (*.d files) get generated as part of the normal gcc/clang invocations. There is no separate dependency generation step.

  $ cat Makefile
  CFLAGS := -MD -MP   
  hello: hello.o x.o y.o
  -include *.d

  $ echo '#include "x.h"' > x.c
  $ echo '#include "y.h"' > y.c
  $ touch x.h y.h
  $ echo 'int main(void) {}' > hello.c

  $ make
  cc -MD -MP   -c -o hello.o hello.c
  cc -MD -MP   -c -o x.o x.c
  cc -MD -MP   -c -o y.o y.c
  cc   hello.o x.o y.o   -o hello

  $ touch x.h

  $ make
  cc -MD -MP   -c -o x.o x.c
  cc   hello.o x.o y.o   -o hello

As I have been saying for years: make is the worst build system, except for all the others.

Also Bazel is very "corporate", it's not designed for projects that want to be good FOSS unix citizens.

Very telling: "common c++ use cases" https://docs.bazel.build/versions/4.2.2/cpp-use-cases.html includes pulling googletest source from the web and linking a random shared object blob. Zero mentions of pkg-config.

Bazel is alright (read: generally better than the competition) as long as you're not doing something uncommon with your toolchain or hitting one of its many shortcomings, otherwise it can quickly become a nightmare. It doesn't even make it easy to access the darn executable you just compiled (!) which always baffles me—if I compiled a binary I don't want it hidden away in some random folder, I want it right there so I can distribute it. And with Python, etc. you hit more obstacles. Make degrades more "gradually" in a sense: it's easy to do arbitrary things in a 1-line recipe, but then it becomes harder to generalize and make it modular. Overall, Bazel definitely wins as the scale of your project grows, and it has tons of useful features, but it's got some ways to go before I'd regard it as "nice".

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 . To solve , a new build system should have .' 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.

[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...