A Sound and Optimal Incremental Build System with Dynamic Dependencies – Erdweg et al. 2015
Back to OOPSLA papers again today.
Does anybody really love their build system?
Software developers struggle with build systems on a regular basis. Previous studies show that on average 12% of development effort is not spent on developing software but on maintaining build scripts. Another study finds that build scripts in existing software projects continuously change and grow in complexity in sync with changes to the project’s source code. These studies show that the development and maintenance of build scripts is an essential part of software development.
In today’s paper, Erdweg et al. introduce a build system called pluto, based on a model that they demonstrate is both sound (always produces the correct output) and optimal (never does more work than it has to).
A builder can execute any number of build operations, read and write files, and trigger other builders. pluto tracks the dependencies of a builder dynamically and organizes them in a single dependency graph. To enable sound incremental rebuilding, pluto interleaves dependency analysis and builder execution and uses a dynamic analysis to enforce invariants on the dependency graph, such as builder A must trigger builder B before A may read any file generated by B. These invariants are essential to correctly determine in which order to execute builders after a file changed and whether a builder can be skipped. We provide a formal model of pluto’s dependency graph and prove the soundness and optimality of pluto’s rebuild algorithm relative to the previous dependency graph.
Pluto has four mechanisms for fine-grained dependency tracking:
- Builders register file dependencies dynamically at build time
- Builder can choose custom time stamps instead of file last-modified times to more precisely capture their dependencies
- Pluto automatically injects a dependency on a builder’s implementation, so that if the builder is changed the necessary rebuilds will occur
- Pluto supports cyclic dependencies with custom cycle-breakers
In Make, and many Make-inspired build systems, all file and build dependencies must be declared statically as part of a build rule. Examples of the need for dynamic dependencies include the set of header files needed to build a C file (which can be determined by running the C preprocessor), and the set of dependencies (such as an included graphics file) needed to build a latex document.
Dependencies that are evaluated solely based on timestamps may cause more work than necessary (and thus not be optimal). For example, a JavaDoc builder is invariant with respect to changes in method bodies. Pluto addresses this by supporting custom timestamps that are provided by the client builders (since different builders of the same file may need different forms of ‘timestamp’).
…note that sophisticated file stamps are more expensive to check than simple ones. For example, the last-modified time is much faster to compute than a file’s hash. In practical applications, build-script developers need to trade a stamp’s cost off against the potential incremental speedup.
Cyclic dependencies may be undesirable, but they do happen – for example, the Latex builder illustrated in the paper actually forms a cycle with itself since it both reads and writes the same aux file!
When pluto detects a build cycle, it queries all builders in the cycle for a cycle handler. If none of the builders provides a cycle handler, the cycle cannot be built and building is aborted. Otherwise, pluto asks each cycle handler whether it can build this particular cycle (method canBuildCycle). If at least one cycle handler can build the cycle, pluto invokes its method buildCycle. This method takes the build cycle and an instance of the currently running build manager. It produces a set of build units (cf. Section 4), one for each member of the cycle.Method buildCycle can call method build of the involved builders and needs to resolve the cyclic dependencies.
Two cycle breakers are provided out-of-the-box: the fixpoint cycle handler simply invokes all builders in the cycle repeatedly until the outputs stabilise on a fixpoint (all dependencies are up to date); the build all at once cycle handler collects all of the inputs and builds them simultaneousy – for example, this is used in pluto’s Java builder when a cycle is detected.
The builder takes multiple source files as input. If they do not depend on each other cyclicly, we invoke the java compiler on each source file separately. But if there is a cyclic dependency between files, we pass them to the Java compiler together.
In the paper’s case studies, pluto is used to support incremental building of three different projects, and to implement Java-style separate and incremental compilation for two existing languages: Stratego and SugarJ.
Previously, Stratego did not feature separate compilation and performed a global compilation with all source files at once. SugarJ did feature file-level incremental compilation before, implementing its own dependency tracking and suboptimal rebuild algorithm. Based on pluto, we were able to eliminate this code, relying instead on the more general, sound, and optimal dependency tracking and rebuilding of pluto.
I’ve previously implemented incremental compilation support in the AspectJ compiler and weaver, and I can attest that it adds considerable effort over the simple creation of a batch compiler.
The Stratego and SugarJ case studies show that pluto is applicable to different application scenarios, including the development of file-level incremental compilers. In particular, it is possible to reuse the dependency tracking and rebuild algorithm of pluto, which typically is a complicated subsystem
of a compiler that now can be eliminated.
Pluto today relies on regular Java code for build scripts. The emphasis of the work is on demonstrating the soundness and optimality of the build process, “the development of a concise DSL on top of pluto is out of scope for this paper.” The closest related work to Pluto is probably Google’s Bazel:
Bazel is a new build system developed by Google that advertises incrementality and correctness. While Bazel did not influence the design of pluto, Bazel’s dependency graphs turned out to have the same form as the dependency graphs of pluto: Builders require other builders, and builders require and provide files. In contrast to pluto, Bazel does not support dynamically discovered dependencies. Instead, Bazel operates in three phases, where it first loads the build configurations, then constructs the complete dependency graph, and finally triggers builders as required. pluto interleaves dependency analysis and builder execution to allow the latter to influence the former.
Pluto’s model
Sections 4 and 5 of the paper present a formal model of pluto’s build system, and prove that pluto’s incremental build algorithm on top of that model is both sound and optimal.
At the heart of the model is a two-layered dependency graph together with a model of a file system:
pluto represents dependencies in a two-layered dependency graph. The file layer of a dependency graph contains nodes that represent required and provided files. File nodes are never connected. The build layer of a dependency graph contains nodes that represent the result of a builder. We call such nodes build units. pluto connects build units to those nodes in the build layer that the unit required to be built. In addition, pluto connects a build unit to all nodes in the file layer that represent files required or provided by the build unit.
A dependency graph is well-formed under four conditions:
- All required build units are part of the dependency graph (it is closed).
- Different builders must provide distinct paths for storing their build unit
- Each output file is produced by one and only one builder
- All file dependencies must be governed by builder dependencies
We consider a build unit to be consistent if all required build units are consistent as well as all required and generated files.
The author’s differentiate between internal consistency and total consistency. Internal consistency just considers a build unit’s immediate dependencies, whereas total consistency also includes their transitive closure.
A build unit requires rebuilding if it is not totally consistent. Conversely, a totally consistent build unit does not require rebuilding. It is the job of a build system to produce a set of totally consistent build units that do not require rebuilding. For soundness, it does not matter if the build system performs a clean build or incrementally rebuilds some build units.
A build system is modeled as a function that takes as input a sequence of (Builder, Builder Input) pairs and a file system, and produces as output a totally consistent set of build units.
We consider incremental building at the level of build units. That is, if we execute a builder, we execute it completely. Therefore, our model of builders as a function from build input to build unit is sufficient. Users can realize incremental computations at different granularities by splitting or merging builders.
We call a sound build system incremental if it optimizes for the following two incrementality properties: (I1) Minimize the number of builder-function executions; (I2) Minimize the number of internal-consistency checks.
An optimal incremental builder executes the minimal number of builders (I1), and checks internal consistency as infrequently as possible (I2)…
There are many more details, including pseudo-code for a sound and optimal incremental build algorithm, in the paper itself.