Building OCaml with Redo

[pozorvlak]

Context.

Calculating the dependency graph of your build ahead-of-time can be fiendishly difficult, or even impossible. Redo brings two, I think brilliant, insights to bear on this problem.

1. If you have to build the target in the course of calculating its dependencies, that's totally OK, because that's what you really wanted to do in the first place.
2. You don't actually have to know the entire build graph when you start building; you only need to know enough dependencies such that
   • if a given target T needs to be rebuilt, at least one of the dependencies you know about for T will have been affected;
   • in the course of building T, you will discover the remaining dependencies of T and rebuild any stale ones.

Let's try to write do-files for building OCaml modules.

In default.cmi.do:

redo-ifchange $2.mli
ocamlc $2.mli

In default.cmo.do:

redo-ifchange $2.cmi $2.ml
redo-ifchange `ocamldep $2.mli $2.ml`
ocamlc $2.ml

Note: these do-files will not actually work, because redo insists that you write your output to a temporary file called $3 so it can atomically rename the newly-built file into place, and ocamlc is equally insistent that it knows better than you what its output files should be called. However, this annoying interaction of their limitations is irrelevant to the dependency-checking algorithm, so I'll pretend that they do work :-) I'll try to construct a workaround and post it on GitHub. Update: I have now done so!

The redo-ifchange command says "if you know how to build my arguments, then build them; if any of them changes in the future, then the target built by this script will be out-of-date". So to build X.cmi, we observe that it depends on X.mli (which probably won't need building), and then build it. To build X.cmo, we observe that it depends on both X.ml and X.cmi (which will be rebuilt if need be). Then we invoke ocamldep to get a list of other files imported by X.ml, build those if any are out of date, and finally invoke ocamlc on X.ml to produce X.cmo.

Let's see how this plays out in the following scenario:

1. We build X.cmo.
2. We try to build it again.
3. We edit X.ml, adding a new dependency Y.
4. We rebuild X.cmo.

First, redo runs default.cmo.do, discovers that X.cmo depends on X.ml and X.cmi, recursively builds X.cmi (determining that it depends on X.mli), and finally compiles X.ml, producing X.cmo.

When we run redo-ifchange X.cmo again, redo will check its database of dependencies and observe that X.cmo depends transitively on X.cmi, X.ml and X.mli but that none of them have changed; hence, it will correctly do nothing.

Then we add the dependency, and run redo-ifchange X.cmo. Redo will again check its database of dependencies and note that X.ml has changed, so it must re-run default.cmo.do. First it notes that X.cmo depends on X.cmi and X.ml: it checks its database and sees that X.cmi depends on X.mli, which hasn't changed, so it leaves X.cmi alone. Next it re-runs ocamldep X.mli X.ml and hands the output to redo-ifchange: this tells redo that X.cmo now depends on Y.cmi. Y.cmi doesn't exist yet, so it builds it using the rules in default.cmi.do. Finally it compiles X.ml into X.cmo.

This system should work provided that all your dependencies live within the filesystem, or can be brought within it; however, if this is not the case then you probably have bigger problems :-)