Overlord for Redoers

Redo	Overlord
redo	build
redo-ifchange	depends-on
redo-ifcreate	depends-not

Build systems manage state in the file system. In Common Lisp, we have a bundle of state which, in many ways, resembles a file system: a set of persistent, mutable locations with first-class, hierarchical addresses. Symbols have value cells and function cells (mutable locations); they have property lists; they are used as keys in arbitrary namespaces (more locations); they can be persisted, in fasl files and in saved images; and they are each uniquely addressed with a path (a tuple of package name and symbol name).

The obvious difference between Overlord and Redo in practice is that Redo uses shell scripts, while Overlord’s “scripts” are written in Lisp. (It is unimportant because, after all, you can run shell commands from Lisp, or somehow call Lisp from the shell.) On the one hand, embedding shell syntax in Lisp is clumsy; on the other hand, Lisp special variables are much superior to any shell-based means for passing information between parent and child scripts. (See §5.4.2 in Grosskurth 2007.)

The important thing to remember about Overlord is that, because the goal of Overlord is to maintain the consistency of the whole Lisp system, there is only one project. Targets are resolved (i.e. relative pathnames are made absolute) at compile time, not run time, relative to the base inferred for the package which is current at the time they are defined. And because all targets are absolute, the directory which is current at the time the build takes place does not matter.

The fact that there is only one project also changes how patterns are handled. Since patterns do not belong to a particular project, they need another form of namespacing. Accordingly patterns are given names (when they are defined with defpattern) and must be invoked by name.

All that said, Overlord is a surprisingly faithful implementation of Redo, as can be seen in redo.lisp. It differs from Redo principally in that its idea of a target is based on a protocol, rather than being wedded to files.

1. Like most practical Redo implementations, Overlord does not (by default) hash targets to determine if they have changed. The timestamp of the target, however, is treated as a hash-like value: the target is rebuilt whenever its timestamp changes. This avoids both the drawbacks of hashing (slow) and the drawbacks of timestamp ordering (unreliable clocks). Actually the stamp of a file incorporates both its mtime and its size.
2. Overlord deviates from the Redo model in how it decides what is a target. In Redo, this depends on the state of the file system – a prerequisite is a target under two conditions: it does not exist, or it exists and has an entry in the database. In Overlord, however, the database is discarded every time the version of Overlord is incremented. The same goes for the Lisp implementation. You could easily end up in a condition where a target is treated as a source file because it exists, and has no entry in the newly created database. So, instead of relying on the database to determine what is or is not a target, Overlord treats an existing X as a target only if there is a build script for X.
3. Overlord deviates from the Redo model in how it writes file targets to disk. Redo-like behavior – writing to a temp file that is atomically renamed to replace the target – is encouraged, but a script can also choose to overwrite its target directly. This allows the script to choose not to write to the file if its output has not changed (e.g. using overlord:write-file-if-changed). In this way we achieve the same result as redo-stamp – the ability of a target to declare itself unchanged – without complicating the underlying model. (It also simplifies working with external tools that do not let you specify an output file – a bad design, but unfortunately a common one.)