15
$\begingroup$

An incremental compiler is one which only needs to recompile the parts of a program which changed since the last output, as opposed to a batch compiler which must re-compile everything. Incremental compilers are important for large code-bases, where a clean build may take minutes or even hours. As a result, almost all commonly-used compilers are incremental in some form or another, including:

However, some compilers are "less" incremental than others. By which I mean, in some compilers a single change can still force many symbols to be recompiled, including ones which should have been unaffected. For example, in gcc/clang (C/C++), changing a function signature in a header requires every symbol in every source file which recursively imports that header to be recompiled, regardless of whether the symbol/file actually uses the changed function. Sometimes this can be an issue: ghc (Haskell) has it even worse, because there is no separation between header and implementation, so merely changing the implementation of a Haskell function will force recompilation of every symbol in every module which recursively imports the function.

On the opposite end, some incremental compilers can track dependencies and dependents at the symbol level, like salsa (used by some extent in rust-analyzer), or typst (a LaTeX alternative with a sort of live preview, which uses a technique called "Constrained Memoization"). In the extreme case, compilers like Unison can do updates such as renames, which affect the source (but not semantics) of some symbols, without recompiling said symbols.

Faster incremental compilation is particularly important when it's required for live-editing. In this case, full-fledged "compilation" usually isn't required (unless you need to expand compile-time macros), but what is required is static analysis which requires some form of translate from syntax to IR, which can be considered a form of compilation. As a result, language servers almost always implement finer-grained caching than their compiler counterparts, as well as other techniques like storing prior output in-memory, including:

What are some of these techniques used by language servers? And what do some compilers use to provide finer-grained recompilation, so that a single change in a header doesn't cause a large cascade of invalidations? Ultimately, what are some techniques various compilers, language servers, and other tools which use static analysis use, for faster, finer-grained incremental updates?

$\endgroup$
1

5 Answers 5

22
$\begingroup$

What are some of these techniques used by language servers?

I can speak to the "Roslyn" C# compiler as I was on the design and implementation team for it. Briefly:

Lexical and grammatical analysis

The lexer and parser are designed to be incremental because they are heavily used in the IDE, and the IDE has to be responsive to fast typing. We used all kinds of tricks to stay within our tight performance budget:

  • Data structures for tracking project state are optimized for the case where a single file is changing. People don't type in two files at the same time!

  • Syntax trees are "full fidelity" concrete syntax trees where we track both tokens and "trivia" -- spaces, comments, and so on. The syntax colorizer and code formatter need to know where the comments and spaces are.

  • Tokens and parse trees are immutable and "persistent" -- that is, when an edit arrives at the language service from the editor, we rebuild only the spine of the syntax tree on the vast majority of the edits. See https://ericlippert.com/2012/06/08/red-green-trees/ for some thoughts on the data structure.

Moreover, the lexer and parser take as their inputs the current parse tree and the edit. They then identify which portion of the parse tree is being edited and only re-lex and re-parse enough tokens to make the necessary patch to produce the new immutable parse tree. That algorithm is called "the blender" and it makes my head hurt when I read the code.

  • The language service also supports tricks like "only syntax colorize this region of the code", so that for example the IDE can choose to only compute colors for the code that is currently visible.

Semantic analysis

  • Semantic analysis for libraries is done once and cached; reading metadata tables and turning them into Roslyn's internal symbol representation is expensive.

  • Semantic analysis for source code does NOT reuse past state plus an edit. We considered it. The parser blender was hard enough, and we had Neal Gafter on the team at the time who had written his thesis on this kind of parser, so we had confidence that it would work. We didn't want to try to solve the same problem for semantic analysis; our confidence was a lot lower for that.

Semantic properties of the code are re-analyzed from the parse tree on every edit, but they are analyzed entirely on-demand, lazily. When the IDE requests a tooltip showing the type of the expression at this location, the language service does the minimum work possible to get a type for that expression.

  • We can do obvious tricks like "don't analyze method bodies if all you need is a method's signature". (The pre-Roslyn compilers also used this technique.)

  • Semantic analysis must be robust and accurate even when the program is badly malformed; if the program were perfect, it wouldn't be open in the editor! There was a lot of work put into ensuring that analysis terminates quickly. For example, base types being already known to be acyclic is a precondition of the algorithm that checks whether an expression of one type is convertible to another type.

There is a lot more I could say here but I think I will leave it there. Do leave a comment if you want more details.

$\endgroup$
1
  • 2
    $\begingroup$ The lexer and parser sound a lot like tree-sitter (tree-sitter.github.io/tree-sitter), which is also designed to be super-fast and takes the prior parse tree as input. Though I'm sure C#'s handwritten "blender" is more optimal than tree-sitter's generated GLR parsers $\endgroup$
    – tarzh
    Sep 8, 2023 at 3:27
4
$\begingroup$

This sounds like something e-graphs could be good for. An e-graph is an intermediate representation in which nodes (representing program terms) are grouped together into "e-classes" by equivalence. If you retain the e-graph for the code, then when it's updated, all the nodes for the parts that weren't changed will still be present, and if new code reuses parts of existing code then the e-graph will reuse those nodes.

Static analyses can be represented by attaching labels to e-classes (sets of equivalent nodes), for example type analysis might attach type information to each expression term. The key point is that all analysis or transformation of code is non-destructive: the nodes and labels themselves are immutable, and the graph only changes by adding new nodes, or joining nodes that are discovered to be equivalent.

So there is no possibility of cache invalidation, but if the e-graph is kept in memory and updated over many edits, the cache might contain many unused nodes. Depending on the implementation, this might already be handled by the host language's garbage collector, or otherwise some kind of GC algorithm might have to be implemented manually (using the current program as the GC root).

A couple of other potential issues: generally the e-graph nodes don't represent the AST directly, rather they are a different intermediate representation. Either you will have to translate from the AST to the IR for the whole source file on each edit (this translation is generally much faster than what you use the IR for), or that translation must be done incrementally too somehow (I'm not sure if there is prior work on this). You will also need a way of ensuring that unique IDs for e.g. variables will be relatively stable across edits, so that all the terms which make use of some variable will compile to equivalent nodes across edits.

Note that analyses can only be represented as labels if they depend only on the node itself; this works for e.g. types, effects or other things which can be represented as type systems. It won't work for e.g. reachability analysis, because whether or not a term like x + 1 is reachable doesn't depend on the term itself, but rather where it appears.

$\endgroup$
4
$\begingroup$

TL;DR: Lazy, on-demand, pull resolution.

You already mentioned salsa, its README mentions that it was inspired from adapton and glimmer.

The key idea behind salsa is to switch things up: pulling instead of pushing. That is, salsa is Goals Oriented: it does not attempt to re-compute everything, but only what matters to reach the stated goal.

The infrastructure behind it is (relatively) simple:

  • A query system: each pure transformation is described as a query, and performing any query in the context of another will automatically track the dependency.
  • A cache system: the result of each query is aggressively cached -- or, for space reasons, a cryptographic hash of the result -- so that it is possible to use the result without re-computing it, and it is possible to "stop" propagating a change if the result of a query with the new inputs is the same as the result with the previous inputs.

The difficulty, then is composing the queries in an efficient manner. Going from a raw file to entities amenable for incremental compilation in particular requires a few tricks:

  1. You need a "split" query, on the CST of your module/translation unit, which will isolate the various items into "results" of their own. This way, any change to a single item will leave the others unaffected, which is detected and leaves their downstream dependencies unaffected.
  2. You likely want relative source locations, if you track it, as otherwise a single character insertion/deletion will affect the location of every token further down the file:
    • The location of tokens within an item should be relative to the start location of the item.
    • The start location of an item is best tracked with a separate query.
    • If the language allows querying the source location, the resolution of said source location is best deferred as long as possible -- you don't need it in the syntax tree, but may need it for compile-time function execution.

How to efficiently implement such a system, and the inevitable persistence layer, is left as an exercise to the reader. A non-trivial exercise.

$\endgroup$
3
$\begingroup$

Cache invalidation of all state

Consider that the first compiler of this language has no caching facilities. That is, it doesn't remember anything. In this case it will have to recompile everything every time.

In other extreme, consider a compiler capable to:

  • Serialize and store all artifacts, of every stage, at every file source read;

  • Load and restore these artifacts, if:

    • All compiler parameters, all internal state, and source file read are identical;

    • Discard the cached data and continue compiling.

This is, of course, a tall order to implement. But is, in theory, what is necessary to cover all cases

Cache invalidation of some state

The real utility lies between these two extremes, between memorizing nothing and everything.

  • Parsed AST and CST of source files can be cached, as one file is changed at a time, but potentially thousands of files do not change, and need not be re-parsed every time.

  • Compiler parameters and file inclusion order of a full compilation can be cached, and compared afterwards with the new file system state. With this information, the compiler can determine what leaf files do not need recompilation, and where to start recompiling.

Cache invalidation of visible artifacts

Consider, for example, the code:

def PrintDiagnostic( str text )
    io.print( "DEBUG:" + str );

Changing any letter inside the string does not change any aspect of any other part of compilation. Thus, it would be possible in a case like this, to compile only the visible artifacts, compare its generated artifacts with a previous run, and then, if identical, avoid further compiling any dependence of this compilation unit.

$\endgroup$
1
  • $\begingroup$ In a magical ideal world, changing DEBUG to Debug should only need to update the data segment of the binary, since the code is otherwise the same. Of course, the cost of doing so may not be worthwhile, both in implementation complexity, and in the overhead of incrementalising a data structure, which is usually logarithmic in space and/or time. There are close analogies to overdraw in graphics: sure, avoid drawing the same pixel multiple times per frame, but not if it makes you miss your target frame rate! $\endgroup$
    – Jon Purdy
    Sep 7, 2023 at 19:02
2
$\begingroup$

One common difficulty with incremental compilation is that debug information usually describes code locations as line numbers within a source file. Thus, even if only a tiny bit of the source code within a file is changed (or even if all of the changes are within comments), it will generally be necessary to rebuild all of the code within a file even if 99% of it has stayed the same.

This difficulty might be alleviated by having debug information from the compiler report line numbers relative to the start of the containing function, as well having the compiler output a list of all functions' starting line numbers. A post-compilation step could then use the compiler's debug data from each function (whether recompiled or not) to produce a debug-information file which contains source-relative line numbers. If two functions are changed, it would be necessary to recompile those functions, and to rebuild the file's debug info, but compiled code from other functions would not need to be rebuilt.

$\endgroup$
7
  • $\begingroup$ More generally, you could have debug information refer to syntax node ids, and implement recompilation so that if a node is re-used (wasn't edited) it gets the same id. Then, syntax node ids' source locations are relative to their parents, so when a syntax node is inserted/removed/modified, only its siblings need to be changed. $\endgroup$
    – tarzh
    Sep 8, 2023 at 3:42
  • $\begingroup$ @tarzh: Many existing debuggers are designed to work with line-number information. If one has a debugger that can work with some kind of node ID, keeping information in that form may be better than function-relative line numbers, but if the final form will be line numbers, I think function-relative line numbers would facilitate post-processing. In any case, my main point was to re-articulate a solution to what someone else told me was otherwise a major obstacle to partial compilation. $\endgroup$
    – supercat
    Sep 8, 2023 at 14:49
  • $\begingroup$ If you have a hashtable of all nodes and backlinks to parent nodes along with position-within-parent information, then getting line number from node id is trivial. Although all of this depends on keeping backlinks up the tree, so duplicated nodes cannot be merged which is a useful optimisation. Maybe debugging information (which is generally easy and quick to produce) should be produced as a post-processing step when required, i.e. during debugger startup (in an IDE) or as the last step of an external debug build. $\endgroup$
    – occipita
    Oct 3, 2023 at 11:24
  • $\begingroup$ @occipita: A change to a source file will often cause line numbers of all nodes in all following functions to change, even if nothing else about those functions would change. In existing designs, if the line numbers associated with an inline-expanded function change, that would cause all modules that call that function to have erroneous line-number information, and fixing it would require rebuilding all of those modules even if nothing about the behavior of the function changed. $\endgroup$
    – supercat
    Oct 3, 2023 at 15:19
  • $\begingroup$ Not sure why a module would depend on the location in the source file of a function it calls. Surely that information is resolved when the function is called, rather than ahead of time? TBH, I've never worked with debug information on a low level so am not entirely sure, but I don't see why this dependency would exist. $\endgroup$
    – occipita
    Oct 4, 2023 at 19:25

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .