Against Query Based Compilers

Against Query Based Compilers

Query based compilers are all the rage these days, so it feels only appropriate to chart some treacherous shoals in those waters.

A query-based compiler is a straightforward application of the idea of incremental computations to, you guessed it, compiling. A compiler is just a simple text transformation program, implemented as a lot of functions. You could visualize a run of a compiler on a particular input source code as a graph of function calls:

Here, schematically, squares are inputs like file text or compiler’s command line arguments, g is an intermediate function (e.g, type checking), which is called twice, with different arguments, and f and h are top-level functions (compile executable, or compute completions for LSP).

Looking at this picture, it’s obvious how to make our compiler “incremental” — if an input changes, it’s enough to re-compute only the results on path from the changed input to the root “query”:

A little more thinking, and you can derive “early cutoff” optimization:

If an input to the function changes, but its result doesn’t (e.g, function type is not affected by whitespace change), you can stop change propagation early.

And that’s … basically it. The beauty of the scheme is its silvery-bullety hue — it can be applied without thinking to any computation, and, with a touch of meta programming, you won’t even have to change code of the compiler significantly.

Build Systems à la Carte is the canonical paper to read here. In a build system, a query is an opaque process whose inputs and outputs are file. In a query-based compiler, queries are just functions.

The reason why we want this in the first place is incremental compilation — in IDE context specifically, the compiler needs to react to a stream of tiny edits, and its time budget is about 100ms. Big-O thinking is useful here: the time to react to the change should be proportional to the size of the change, and not the overall size of the codebase. O(1) change leads to O(1) update of the O(N) codebase.

... continue reading