Riker: Always-Correct and Fast Incremental Builds from Simple Specifications

Build systems are responsible for building software correctly and quickly. Unfortunately, traditional build tools like make are correct and fast only when developers precisely enumerate dependencies for every incremental build step. Forward build systems improve correctness over traditional build tools by discovering dependencies automatically, but existing forward build tools have two fundamental flaws. First, they are incorrect; existing forward build tools miss dependencies because their models of system state are incomplete. Second, they rely on users to manually specify incremental build steps, increasing the programmer burden for fast builds.

This paper introduces RIKER, a forward build system that guarantees fast, correct builds. RIKER builds are easy to specify; in many cases a single command such as gcc *.c suffices. From these simple specifications, RIKER automatically discovers fast incremental rebuild opportunities. RIKER models the entire POSIX filesystem-not just files, but directories, pipes, and so on. This model guarantees that every dependency is checked on every build so every output is correct.

We use RIKER to build 14 open source packages including LLVM and memcached. RIKER incurs a median overhead of 8.8% on the initial full build. On average, RIKER's incremental builds realize 94% of make's incremental speedup with no manual effort and no risk of errors.