📖Build systems a 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