A quick introduction to redo

[pozorvlak]

[This is a cleaned-up version of the notes from my Glasgow.pm tech talk last night. The central example is lifted wholesale from apenwarr's excellent README for redo; any errors are of course my own.]

Redo is a replacement for make designed by djb and written by Avery Pennarun.

You may have heard of djb - he's the author of the mail transport agent qmail and the DNS software djbdns. His code is famous for its uncompromising brilliance and very very low defect rate. Djb has been described as "the greatest programmer in the history of the world" - even if you disagree, how many people ever receive such an accolade?

Back to redo. Make has three major problems:

1. It's Yet Another Goddamn Syntax to remember; one with its own set of stupid whitespace-handling and quoting issues. Worse, it's not even well-standardised, with every version of make expecting something slightly different.
2. Recursive make sucks, for well-known reasons.
3. Nonrecursive make sucks, because of make's poor support for modular coding and the need to parse a giant Makefile every time you build the smallest thing.

Most proposed replacements have focused on problem 1, by replacing make syntax with something more familiar but less well suited to the problem domain.

"Yes, we know all that," you cry, "get to the point!" Well, the point is that redo fixes all three of these problems:

1. No new syntax - do-files are ordinary shell scripts.
2. Recursive redo works properly.
3. There is no nonrecursive redo.

Make has some more subtle problems:

1. Your build also depends on the Makefile (suppose you change your CFLAGS? Now you have to rebuild all your programs), but how many people remember to declare that?
2. Actually, each target only depends on some parts of the Makefile (suppose you change your CFLAGS: you don't now need to rebuild the documentation). Have fun tracking that.
3. Building is not atomic - if the compiler crashes halfway through generating foobar.o, you'll be left with a broken object file in your tree.
4. Complex Makefiles are a bitch to read and debug.

Redo fixes these too.

Time for an example!

I'm going to create a basic Hello World example. Here's hello.c:

#include <stdio.h>
#include "resources.h"
int main(char argc, char** argv)
{
    printf("%s\n", message);
}

resources.c:

char* message = "Hello, world!";

and resources.h:

extern char* message;

Note that hello.o depends on hello.c and resources.h, but resources.o only depends on resources.c.

Now to create our do-files. Redo wants each target in its own file, for reasons I'll explain later.

all.do:

redo-ifchange hello

redo-ifchange is an ordinary program that tells the redo system that the current target depends on the targets specified.

hello.do:

OBJS=hello.o resources.o
redo-ifchange $OBJS
gcc -o $3 $OBJS

$3 is the name of a temporary file created by redo: if the build succeeds, this is copied over the file we're building.

default.o.do:

redo-ifchange $1.c
gcc $CFLAGS -MD -MF $3.deps.tmp -o $3 -c $1.c
DEPS=$(sed -e "s/^$3://" -e 's/\\//g' <$3.deps.tmp)
rm -f $3.deps.tmp
redo-ifchange $DEPS

If redo can't find a specific do-file for the target it wants to build, it will look for a default one with the right extension. $1 is the name of the file being built, without its extension; the first line declares that the .o file depends on the corresponding .c file. The -MD and -MF flags to gcc tell gcc to output information about the dependencies of the file being compiled; we then do some sed magic to process that list and (in the final line) declare a dependency on what we found.

The key insight here is that the first time you build something it doesn't matter what its dependencies are: clearly it needs to be built, because it doesn't exist! Hence, we can use that first build run to capture dependencies. Redo allows you to add dependencies at any point of the build script, making this kind of thing easy; apparently it's possible with make, but it's a total pain.

clean.do:

rm *.o hello

Now, let's build the whole thing:

pozorvlak@delight:~/src/redo-talk
0 $ redo
redo  all
redo    hello
redo      hello.o
redo      resources.o

Isn't that pretty? The level of indentation shows you the structure of the recursive calls. Note, by the way, that the redos in the left margin mean that you can just copy-and-paste from the terminal to re-try a failing part of the build.

Redo's got some nice debugging options available:

pozorvlak@delight:~/src/redo-talk
0 $ redo clean && redo -x
redo  clean

redo  all
* sh -ex all.do all  all.redo2.tmp
+ redo-ifchange hello

redo    hello
* sh -ex hello.do hello  hello.redo2.tmp
+ OBJS=hello.o resources.o
+ redo-ifchange hello.o resources.o

redo      hello.o
* sh -ex default.o.do hello .o hello.o.redo2.tmp
+ redo-ifchange hello.c
+ gcc -MD -MF hello.o.redo2.tmp.deps.tmp -o hello.o.redo2.tmp -c hello.c
+ sed -e s/^hello.o.redo2.tmp:// -e s/\\//g
+ DEPS= hello.c /usr/include/stdio.h /usr/include/features.h 
 /usr/include/bits/predefs.h /usr/include/sys/cdefs.h 
 /usr/include/bits/wordsize.h /usr/include/gnu/stubs.h 
 /usr/include/gnu/stubs-32.h 
[snip]

Let's try updating resources.h and rebuilding:

pozorvlak@delight:~/src/redo-talk
0 $ touch resources.h && redo
redo  all
redo    hello
redo      hello.o

Exactly the right amount of work is done to get the build up-to-date. As one would hope :-)

I mentioned changing the Makefile earlier and the problems it can cause. Let's try that:

pozorvlak@delight:~/src/redo-talk
0 $ touch default.o.do && redo
redo  all
redo    hello
redo      hello.o
redo      resources.o

Every target has an implicit dependency on the do-file used to build it. This, by the way, is the reason why every target gets its own do-file: that way, you get fine-grained build-script dependencies for free. But where are these dependencies held?

pozorvlak@delight:~/src/redo-talk
0 $ cd .redo && ls
db.sqlite3          lock.18  lock.22  lock.27  lock.32  lock.38  lock.48
db.sqlite3-journal  lock.19  lock.23  lock.28  lock.33  lock.4   lock.7
lock.10             lock.2   lock.24  lock.29  lock.34  lock.40
lock.11             lock.20  lock.25  lock.30  lock.35  lock.42
lock.16             lock.21  lock.26  lock.31  lock.36  lock.45

Redo keeps all its dependency information in a SQLite database in your project's toplevel directory, which also contains information about when each target's dependencies were last checked. This means that

1. Every invocation of redo has access to full dependency information.
2. Redo doesn't have to parse a big text file every time it builds every tiny thing.
3. You don't need to stat the same files over and over in a single build.

Hence, recursive redo is efficient and accurate.

The .redo directory also contains lockfiles to prevent parallel invocations from stomping on each other. Redo supports a -j option for parallel builds, and even supports jobserver's protocol, so make -j and redo -j can coexist.

Let's try the atomicity feature. Let's create a file called fred.do:

echo "Yabba-dabba-doo!"

Redo redirects standard output to the tempfile, so we don't need to pipe our output to $3.

Now let's try building it:

pozorvlak@delight:~/src/redo-talk
0 $ redo fred && cat fred
redo  fred
Yabba-dabba-doo!

OK, that worked. Now let's make fred.do fail:

echo "Yabba-dabba-don't!"
exit 1

pozorvlak@delight:~/src/redo-talk
0 $ redo fred; cat fred
redo  fred
redo  fred: exit code 1
Yabba-dabba-doo!

Hurrah!

How does redo handle subdirectories?

subdir/fred.c:

int main(char argc, char** argv)
{
    return 0;
}

pozorvlak@delight:~/src/redo-talk
0 $ redo subdir/fred.o
redo  no rule to make 'subdir/fred.o'

Redo requires the do-file to be in the same directory as the file you're building. There's a fork of the project which searches up through the tree looking for appropriate default.*.do files, but it's not clear whether that's the Right Thing: as it is, you can see what you can redo in a given directory with a simple ls. Compare the mess that you can create with included Makefiles!

Oh, one more thing:

barney.do:

#!/usr/bin/perl
use 5.010;
say "Whatever you say, Fred!"

pozorvlak@delight:~/src/redo-talk
1 $ redo barney && cat barney
redo  barney
Whatever you say, Fred!

You can write your do-files in any language that supports the #! convention :-)

So, in summary:

1. Redo is a new build system
2. It has a very simple design which solves many of the problems of make
3. You should consider using it for your next project.

Comments

[elvum.livejournal.com]

Colour me unconvinced that letting people write do-files in practically any language isn't almost as much a bug as a feature. :-)

Also, I have a totally unfair question: can redo elegantly handle situations where the ratio of input files to output files is a ratio other than 1:1? ISTR that I never managed to get GNU make to deal elegantly with all ratios.

[pozorvlak.livejournal.com]

Yeah, the "which language should do-files be in" argument is currently raging (http://groups.google.com/group/redo-list/browse_thread/thread/ecdf63082235bc42) on the mailing list. I think supporting multiple languages is probably the right decision: some projects are going to want to be Language X And No Other, but most people will just go with the default. The bigger problem is shell portability.

A ratio of n:1 is easy for any n >=1: just add the extra dependencies. For n < 1, see the README (https://github.com/apenwarr/redo/blob/master/README.md), and search for "Can a single .do script generate multiple outputs?". AIUI, it works provided that you can choose a representative of each set of output files. Suppose you're generating 1.foo, 1.bar, 1.baz, 2.foo, 2.bar, 2.baz, ... , 10.foo, 10.bar, 10.baz, and that the same build stage that generates n.foo also generates n.bar and n.baz. Then you add rules for [1-10].foo, and for any file which really depends on n.bar or n.baz, you specify a dependency on n.foo.

This isn't very elegant, but it's no worse than make.

[pozorvlak.livejournal.com]

Actually, it would probably make more sense to specify correct dependency information, and then add default.bar.do and default.baz.do files which just contained the line redo-ifchange $1.foo.

[pozorvlak.livejournal.com]

OK, here's a workaround for the multiple-outputs problem that appears to actually work. Create a default.dummy.do file containing the following:

redo-ifchange [input files]
if [ ! -d $1.build ]; then
	mkdir $1.build
fi
cd $1.build
compile ../input_1 ../input_2 ../input 3 ...
cd ..
touch $3

Now for every type of input file created by your compile step, create a default.foo.do file containing

redo-ifchange $1.dummy
mv $1.build/$1$2 $3

Now you can declare honest dependencies on the various outputs of the compile step.

Thanks to wnoise and spliznork on Reddit (http://www.reddit.com/r/programming/comments/f2cko/djb_redo_could_be_the_git_of_build_systems/c1cs6dy) for this solution.

[elvum.livejournal.com]

Thanks! :-)

[pozorvlak.livejournal.com]

Interestingly, Schwern (maintainer of the ExtUtils::MakeMaker (http://search.cpan.org/~mschwern/ExtUtils-MakeMaker-6.56/lib/ExtUtils/MakeMaker.pm) build system used for most Perl modules) thinks that the ability to write do-files in any language may turn out to be redo's killer feature (http://groups.google.com/group/redo-list/browse_thread/thread/c9e070c5c5ef9bc7)...

[elvum.livejournal.com]

If I was inclined to be unfair, I would suggest that a Perl programmer coming out in favour of there being more than one way to do it was not the most surprising thing in the world. ;-)

I suspect the thread has grown since earlier this evening, because several respondents now highlight my biggest issue with his logic; namely the assumption that every project will either be written in a scripting language with filesystem manipulation functions, or will have a single obvious choice of such a language with wide familiarity amongst the project's developers.

I'm sure that there *are* lots of projects for which one of those conditions is true, but I'd hesitate to say that the majority of programming projects in the world currently fall into one of those categories. (Indeed, I'd hesitate to say that the majority of programming projects in the world that currently use GNU make fall into one of those categories.)

I'm tempted to suggest that if a project picks a general purpose scripting language for its .do files that you don't already know, you could even end up in a situation where the barrier to modifying them was *higher* than learning Makefile syntax, given the much greater potential for complexity afforded by their general-purpose nature. That's not necessarily an issue with redo, of course. :-)

(FWIW, I currently use GNU make exclusively for building LaTeX documents. The previous time I used GNU make was to do video editing and frame-rate conversion, hence the question about input-to-output file ratios. Neither of those had/has an obvious choice of scripting language. I suspect my usage is unlikely to be representative, however...)

[elvum.livejournal.com]

Did I omit to mention how much I hate the GNU make, and the autotools in general, btw? They are certainly ripe for replacement...

[elvum.livejournal.com]

Oh, CMake is worth a look too - from your perspective you could consider it to be SVN to GNU make's CVS, if you get my drift...

[pozorvlak.livejournal.com]

That's certainly the impression I'd got (macros generating macros generating shell script: yeah, that sounds like a great idea...), but the autotools have their defenders. What problems did you encounter with them?

[rm445.livejournal.com]

Thank you for this, I came to your blog via google and had a play with redo after reading. One thing to note is that, as you say, .do files must be in the same directory as the thing they're building, but not necessarily the source files. So one alternative layout is to put all your build scripts except all.do in a build/ directory, and have your object files built there.

# build/progname.do
OBJS="a.o b.o"
redo-ifchange $OBJS
gcc -o $3 $OBJS

# build/a.o.do
SRC="../src/a.c"
redo-ifchange $SRC
gcc -o $3 -c $SRC

- and so on. Not sure this is the Right Thing but it might suit some people.