DJB Redo in Just

[casey]

This is something that I've been thinking about for a while. I'm unlikely to work on it, but someone else might be interested.

Redo is a build system, first described in notes by Daniel J. Bernstein. There are now a bunch of implementations, the most popular of which, as far as I can tell, is apenwarr/redo.

Redo is elegant and minimal, and not specific to any particular language, much like make, but avoids many of make's issues.

Many redo implementations exist, but they suffer from, in my opinion, a serious usability issue, they require the creation of many files.

I've thought for a while that it might be interesting to add redo-like build system functionality to Just. The use-case for me would be projects where I'm rebuilding resources, like images for a blog, and I want to avoid re-building resources when possible.

Additionally, I think an implementation of Redo with build commands in a single file would be useful.

The major con is that it would complicate Just, and would kind of be a shark-jumping moment, in that Just benefits from not having any build-system-like functionality.

[casey]

I think the cleanest implementation of this would be a new type of recipe whose name is a string and can have dependencies that are strings:

"hello": "hello.c"
  cc -o $OUTPUT hello.c -Wall

This is a recipe that creates "hello" using "hello.c" as a dependency. If you do just hello it runs it only if hello does not exist, or, if it does exist, if hello.c is newer thanhello.

Redo implementations allow you to declare dependencies in the middle of a .do file, so we'd also have to figure out a way to do this, I guess with a recursive invocation of just:

"hello":
  cc -o $OUTPUT hello.c -Wall
  just --redo dependency hello.c

This doesn't make sense in this example, but makes sense in other examples where you don't know your dependencies up front.

[runeimp]

I love the concept of Redo! But wouldn't the major difference between Just and Redo simply be the fact that Redo keeps track of files via hashing or some such to check state instead of relying on file modification times? If so, couldn't you add file hashing to just and have the hash checking handled automatically or enforced by --redo? Sorry, it's been a year or more since I last looked into Redo. So I'm probably overlooking some other aspect of its architecture that is critical to consider.

[casey]

I actually think that redo uses timestamps: https://redo.readthedocs.io/en/latest/FAQImpl/#why-not-always-use-checksum-based-dependencies-instead-of-timestamps

[runeimp]

Oh, yeah! I was thinking specifically of redo-stamp. Been a year or more. 👼

That link and the link it recommends are great discussions on the topic of mtime vs hash. It really just comes down to the best tool for the given job. As usual there is no silver bullet.

None-the-less hashing does still fix the problem with tracking the status of dependency files without the need to check shebang recipes or potentially unknowable target file mtimes. Or a modification that stores the mtime instead of a hash for source files to know if its mtime has changed since the last processing time.

[sogaiu]

I had run up against some issues using a Makefile to express certain types of situations (e.g. multiple output files where "stems" (non-file-extension portions) of inputs and outputs don't match) [1] and started looking into some redo implementations.

From what I can tell, redo (or at least the implementations I came across) doesn't seem to handle this (well) either. There's a claim I came across here that suggests it may be inherent in the design:

Like make, redo assumes a 1:M relationship between targets and dependencies. And like make, it is quite difficult to deal with a project where one build instruction generates multiple targets all together in one go. (An example of this is a parser generator, which generates multiple .cpp and header files from a single grammar file.)

I was surprised to find out recently that apparently the Ninja build system does handle this sort of thing:

A build edge may have multiple outputs.

(from the 2nd bullet point of this)

It also appears the designer / author appreciated redo's design:

There are many other build systems that are more user-friendly or featureful than Ninja itself. For some recommendations: the Ninja author found the tup build system influential in Ninja’s design, and thinks redo's design is quite clever.

(from 3rd paragraph of this)

I had initially not looked into Ninja much as it seems to be "marketed" for its speed, and I was more interested in accuracy. So far though, it seems like it might be pretty good at that as well.

I've focused above on one particular point but as I look more at Ninja I keep finding bits that seem to make it worth trying / studying.

Perhaps it has already been studied / considered, but in case it wasn't on the radar I wanted to mention it.

(Ah, I see it has been mentioned a few times -- should have searched first -- sorry about that :) )

---

[1] Apparently it is possible since make 4.3:

New feature: Grouped explicit targets
Pattern rules have always had the ability to generate multiple targets with
a single invocation of the recipe. It's now possible to declare that an
explicit rule generates multiple targets with a single invocation. To use
this, replace the ":" token with "&:" in the rule. To detect this feature
search for 'grouped-target' in the .FEATURES special variable.

via: https://lists.gnu.org/archive/html/info-gnu/2020-01/msg00004.html

[casey]

I think that #1906 is a better approach, so I'm going to close this.