📖Build systems a la carte

September 27, 2020

authors: Mokhov, Andrey and Mitchell, Neil and Peyton Jones, Simon
year: 2018
url: https://www.microsoft.com/en-us/research/publication/build-systems-la-carte/

Build systems:
- minimality
- build order
Excel is a build system in disguise
Build systems are kinda incremental/adaptive/self-adjusting computations
Bazel uses content-addressable cache of builds (cloud build system)
store = key → value
- filename → contents
- cell → cell value (excel)
expanded version is available at https://www.microsoft.com/en-us/research/publication/build-systems-a-la-carte/
Build system can be split into two parts
- scheduler: to determine the order in which to execute the tasks
  - topological: sort tasks in topological order (e.g., Make), only static dependencies
  - restarting: start building tasks, but stop if new dependency needs a rebuild (Excel)
  - suspending: suspend the task if dependency needs to be built (Shake)
- rebuilder: to determine if key is out-of-date and needs rebuilding
  - dirty bit (e.g., Make, Excel)
  - verifying traces: store output hash and hash of all direct dependencies
  - constructive traces: store output (not hash) and hash of all direct dependencies (can cache multiple results per key)
  - deep constructive traces: store output + hashes of all terminal inputs (e.g., Nix)
    - allows skipping intermediate steps and download the result (shallow builds), but does not support early cutoff
    - the builds must be deterministic