The CAS model of incremental build systems [01IP]

I have continued on my quest to understand and compare different architectures for demand-based/query-based compilation and elaboration. This week I have been exploring the llbuild2fx library from Apple, which its authors describe as a fresh take on low-level build system API. I’m incredibly grateful to Nima Johari for taking the time to answer my many questions about it, and to Cameron Zwarich for some very useful discussions about the incrementalisation of elaboration.

It seems that there are two major approaches to demand-based build systems. The first, which is better known, is incremental computation based on dirtying of inputs which ripple outward in the form of cache invalidations. To my knowledge, this style is represented in Adapton, Shake, Rock, Incremental, and Salsa. Incremental computation in this sense is built up from a network of pure functions operating on stateful inputs at the edges.

A second approach, which is being explored by Apple’s build team, is completely stateless; rather than input nodes being subject to update and inducing cache invalidation, inputs are instead ingested into content-addressed storage (CAS). The entire input to a build process (the source tree and the configuration) is then referred to (via a content-address) in the query nodes. The CAS-based approach, therefore, is not really involving cache invalidation: instead the data of a query contains a stable reference to CAS that can be narrowed to smaller fragments of the CAS in subsequent queries. When input state changes, it is ingested into the CAS and new queries are made that refer to the new data; naturally, child queries will narrow their reference to CAS and this will result in cache hits when the scope has narrowed to something that has already been computed.

There are trade-offs between the two approaches. The first (which I will call stateful incremental computation) is easier to use, because dependency on stateful edge nodes is dynamic and determined in the process of query evaluation automatically. In contrast, the stateless CAS approach requires you to think very carefully about how to narrow the CAS keys referenced in queries. On the other hand, the stateless approach is more flexible in terms of the execution models it supports, which includes distributed builds. (I have a feeling distributed builds are going to be very important for large mathematical libraries in the future, or maybe even in the present if you look at the resources needed to build Mathlib.)

Apple uses (or aims to use) llbuild2fx to coordinate internal builds of their software and its complex dependencies, and I believe they also plan for this (or something like it) to eventually be used in Xcode and the Swift compiler. I am, however, apparently the first person to be attempting to use llbuild2fx on the interior of a compiler, which is of course a potential risk. But a fun risk that I expect to learn a lot from either way.