<p>An <a href="https://en.wikipedia.org/wiki/Incremental_compiler" rel="noreferrer"><strong>incremental</strong> compiler</a> 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:</p>
<ul>
<li><a href="https://gcc.gnu.org/" rel="noreferrer">gcc</a>, <a href="https://clang.llvm.org/" rel="noreferrer">clang</a>, <a href="https://en.wikipedia.org/wiki/Microsoft_Visual_C%2B%2B" rel="noreferrer">MSVC</a> (any C/C++ compiler which produces <a href="https://en.wikipedia.org/wiki/Object_file" rel="noreferrer">object files</a>, since unmodified source files don't need to be recompiled)</li>
<li><a href="https://stackoverflow.com/a/34590342">C# compiler</a></li>
<li><a href="https://docs.oracle.com/en/java/javase/17/docs/specs/man/javac.html" rel="noreferrer">javac</a> (Java compiler)</li>
<li><a href="https://github.com/sbt/zinc" rel="noreferrer">zinc</a> (Scala's incremental compiler)</li>
<li><a href="https://kotlinlang.org/docs/gradle-compilation-and-caches.html#incremental-compilation" rel="noreferrer">Kotlin compiler</a></li>
<li>Various compilers for SML including <a href="https://sourceforge.net/projects/mlkit/" rel="noreferrer">MLkit</a> and <a href="https://www.smlnj.org/smlnj.html" rel="noreferrer">SML/NJ</a> (<a href="http://mlton.org/StandardMLImplementations" rel="noreferrer">StandardMLImplementations</a>)</li>
<li><a href="https://doc.rust-lang.org/rustc/what-is-rustc.html" rel="noreferrer">rustc</a> (Rust compiler)</li>
<li><a href="https://www.reddit.com/r/golang/comments/2b8mhx/does_go_have_incremental_build/" rel="noreferrer">Go is incremental, albeit only at the package level</a> (I believe OCaml is too but not 100% sure)</li>
</ul>
<p>However, some compilers are &quot;less&quot; 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 <em>implementation</em> of a Haskell function will force recompilation of every symbol in every module which recursively imports the function.</p>
<p>On the opposite end, some incremental compilers can track dependencies and dependents at the symbol level, like <a href="https://github.com/salsa-rs/salsa" rel="noreferrer">salsa</a> (used by some extent in <a href="https://rust-analyzer.github.io/" rel="noreferrer">rust-analyzer</a>), or <a href="https://github.com/typst/typst" rel="noreferrer">typst</a> (a LaTeX alternative with a sort of live preview, which uses a technique called <a href="https://github.com/typst/comemo" rel="noreferrer">&quot;Constrained Memoization&quot;</a>). In the extreme case, compilers like <a href="https://www.unison-lang.org/learn/the-big-idea/#structured-refactoring" rel="noreferrer">Unison</a> can do updates such as renames, which affect the source (but <em>not</em> semantics) of some symbols, without recompiling said symbols.</p>
<p>Faster incremental compilation is particularly important when it's required for live-editing. In this case, full-fledged &quot;compilation&quot; usually isn't required (unless you need to expand compile-time macros), but what <em>is</em> 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:</p>
<ul>
<li><a href="https://github.com/ocaml/merlin" rel="noreferrer">merlin</a> (OCaml)</li>
<li><a href="https://github.com/typescript-language-server/typescript-language-server" rel="noreferrer">TypeScript language server</a> (able to incrementally type-check, tsc is not incremental)</li>
<li><a href="https://rust-analyzer.github.io/" rel="noreferrer">rust-analyzer</a> via <a href="https://salsa-rs.github.io/salsa/overview.html" rel="noreferrer">salsa</a></li>
</ul>
<p>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, <strong>what are some techniques various compilers, language servers, and other tools which use static analysis use, for faster, finer-grained incremental updates</strong>?</p>

<compilers><type-checker><ide>
What are some techniques for faster, fine-grained incremental compilation and static analysis?
CC BY-SA 4.0
2023-09-07T08:17:01.623Z
see: 'incrementalizing abstract interpretation' (https://ceur-ws.org/Vol-2047/BENEVOL_2017_paper_9.pdf https://cris.vub.be/ws/portalfiles/portal/35598203/BENEVOL_incrementalAAM.pdf) and 'demanded abstract interpretation' (https://arxiv.org/pdf/2104.01270.pdf)
Moonchild
<p><strong>TL;DR: Lazy, on-demand, pull resolution.</strong></p>
<p>You already mentioned <a href="https://github.com/salsa-rs/salsa" rel="noreferrer">salsa</a>, its README mentions that it was inspired from <a href="http://adapton.org/" rel="noreferrer">adapton</a> and <a href="https://github.com/glimmerjs/glimmer-vm" rel="noreferrer">glimmer</a>.</p>
<p>The key idea behind salsa is to switch things up: pulling instead of pushing. That is, salsa is <strong>Goals Oriented</strong>: it does not attempt to re-compute everything, but only what matters to reach the stated goal.</p>
<p>The infrastructure behind it is (relatively) simple:</p>
<ul>
<li>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.</li>
<li>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 &quot;stop&quot; propagating a change if the result of a query with the new inputs is the same as the result with the previous inputs.</li>
</ul>
<p>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:</p>
<ol>
<li>You need a &quot;split&quot; query, on the CST of your module/translation unit, which will isolate the various items into &quot;results&quot; 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.</li>
<li>You likely want <em>relative</em> source locations, if you track it, as otherwise a single character insertion/deletion will affect the location of every token further down the file:
<ul>
<li>The location of tokens within an item should be relative to the start location of the item.</li>
<li>The start location of an item is best tracked with a separate query.</li>
<li>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.</li>
</ul>
</li>
</ol>
<p>How to efficiently implement such a system, and the inevitable persistence layer, is left as an exercise to the reader. A non-trivial exercise.</p>

CC BY-SA 4.0
2023-09-08T09:28:22.480Z
2023-09-08T09:28:22.480Z
Matthieu M.
<p>This sounds like something <a href="https://egraphs-good.github.io/" rel="nofollow noreferrer">e-graphs</a> could be good for. An e-graph is an intermediate representation in which nodes (representing program terms) are grouped together into &quot;e-classes&quot; 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.</p>
<p>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.</p>
<p>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).</p>
<p>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.</p>
<p>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 <a href="https://langdev.stackexchange.com/questions/2710/how-can-type-systems-be-a-useful-formal-framework-for-modeling-things-other-than">other things which can be represented as type systems</a>. It won't work for e.g. reachability analysis, because whether or not a term like <code>x + 1</code> is reachable doesn't depend on the term itself, but rather where it appears.</p>

CC BY-SA 4.0
2023-09-07T18:35:31.387Z
2023-09-07T18:35:31.387Z
kaya3
<h2>Cache invalidation of <em>all</em> state</h2>
<p>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.</p>
<p>In other extreme, consider a compiler capable to:</p>
<ul>
<li><p>Serialize and store all artifacts, of every stage, at every file source read;</p>
</li>
<li><p>Load and restore these artifacts, if:</p>
<ul>
<li><p>All compiler parameters, all internal state, and source file read are identical;</p>
</li>
<li><p>Discard the cached data and continue compiling.</p>
</li>
</ul>
</li>
</ul>
<p>This is, of course, a tall order to implement. But is, in theory, what is necessary to cover all cases</p>
<h2>Cache invalidation of <em>some</em> state</h2>
<p>The real utility lies between these two extremes, between memorizing nothing and everything.</p>
<ul>
<li><p>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.</p>
</li>
<li><p>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.</p>
</li>
</ul>
<h2>Cache invalidation of visible artifacts</h2>
<p>Consider, for example, the code:</p>
<pre><code>def PrintDiagnostic( str text )
    io.print( &quot;DEBUG:&quot; + str );
</code></pre>
<p>Changing any letter inside the string does not change any aspect of any <em>other</em> part of compilation. Thus, it would be possible in a case like this, to compile <em>only</em> the visible artifacts, <em>compare</em> its generated artifacts with a previous run, and then, if identical, <em>avoid</em> further compiling any dependence of this compilation unit.</p>

CC BY-SA 4.0
2023-09-07T13:38:22.037Z
2023-09-07T17:59:45.817Z
2023-09-07T17:59:45.817Z
André L F S Bacci
CC BY-SA 4.0
2023-09-07T19:02:49.893Z
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!
Jon Purdy
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-09-07T21:28:14.917Z
2023-09-07T21:28:14.917Z
supercat
CC BY-SA 4.0
2023-09-08T03:42:44.690Z
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.
tarzh
CC BY-SA 4.0
2023-09-08T14:49:38.297Z
@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.
supercat
CC BY-SA 4.0
2023-10-03T11:24:56.423Z
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.
occipita
CC BY-SA 4.0
2023-10-03T15:19:20.313Z
@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.
supercat
CC BY-SA 4.0
2023-10-04T19:25:28.033Z
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.
occipita
CC BY-SA 4.0
2023-10-04T20:11:16.277Z
@occipita: If the function it calls gets expanded in-line, then machine code for that function will be incorporated within machine code for the function that invoked it, and debug information should reflect that.  If one subscribes to the theory that any change to a source file should require fully regenerating everything "downstream" of it, simply regenerating everything downstream wouldn't be a problem.  In many cases, however, a change will only affect a small portion of a source file, which is only used by a few clients, and the portions used by most clients will be unmodified.
supercat
CC BY-SA 4.0
2023-10-04T20:12:53.677Z
@occipita: If a few lines were added to the source file above a function which is *otherwise* unchanged, and a module uses that function but nothing else, the only thing in that module which would change as a result of the source file modification would be the line numbers within that function.
supercat
<blockquote>
<p>What are some of these techniques used by language servers?</p>
</blockquote>
<p>I can speak to the &quot;Roslyn&quot; C# compiler as I was on the design and implementation team for it.  Briefly:</p>
<p><strong>Lexical and grammatical analysis</strong></p>
<p>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:</p>
<ul>
<li><p>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!</p>
</li>
<li><p>Syntax trees are &quot;full fidelity&quot; concrete syntax trees where we track both tokens and &quot;trivia&quot; -- spaces, comments, and so on. The syntax colorizer and code formatter need to know where the comments and spaces are.</p>
</li>
<li><p>Tokens and parse trees are immutable and &quot;persistent&quot; -- 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 <a href="https://ericlippert.com/2012/06/08/red-green-trees/" rel="noreferrer">https://ericlippert.com/2012/06/08/red-green-trees/</a> for some thoughts on the data structure.</p>
</li>
</ul>
<p>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 &quot;the blender&quot; and it makes my head hurt when I read the code.</p>
<ul>
<li>The language service also supports tricks like &quot;only syntax colorize this region of the code&quot;, so that for example the IDE can choose to only compute colors for the code that is currently visible.</li>
</ul>
<p><strong>Semantic analysis</strong></p>
<ul>
<li><p>Semantic analysis for libraries is done once and cached; reading metadata tables and turning them into Roslyn's internal symbol representation is expensive.</p>
</li>
<li><p>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.</p>
</li>
</ul>
<p>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.</p>
<ul>
<li><p>We can do obvious tricks like &quot;don't analyze method bodies if all you need is a method's signature&quot;. (The pre-Roslyn compilers also used this technique.)</p>
</li>
<li><p>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.</p>
</li>
</ul>
<p>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.</p>

CC BY-SA 4.0
2023-09-07T15:46:58.780Z
2023-09-07T15:46:58.780Z
Eric Lippert
CC BY-SA 4.0
2023-09-08T03:27:32.293Z
The lexer and parser sound a lot like tree-sitter (https://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
tarzh
# What are some techniques for faster, fine-grained incremental compilation and static analysis?
Posted by: username_0 on 2023-09-07
An [**incremental** compiler](https://en.wikipedia.org/wiki/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:

* [gcc](https://gcc.gnu.org/), [clang](https://clang.llvm.org/), [MSVC](https://en.wikipedia.org/wiki/Microsoft_Visual_C%2B%2B) (any C/C++ compiler which produces [object files](https://en.wikipedia.org/wiki/Object_file), since unmodified source files don't need to be recompiled)
* [C# compiler](https://stackoverflow.com/a/34590342)
* [javac](https://docs.oracle.com/en/java/javase/17/docs/specs/man/javac.html) (Java compiler)
* [zinc](https://github.com/sbt/zinc) (Scala's incremental compiler)
* [Kotlin compiler](https://kotlinlang.org/docs/gradle-compilation-and-caches.html#incremental-compilation)
* Various compilers for SML including [MLkit](https://sourceforge.net/projects/mlkit/) and [SML/NJ](https://www.smlnj.org/smlnj.html) ([StandardMLImplementations](http://mlton.org/StandardMLImplementations))
* [rustc](https://doc.rust-lang.org/rustc/what-is-rustc.html) (Rust compiler)
* [Go is incremental, albeit only at the package level](https://www.reddit.com/r/golang/comments/2b8mhx/does_go_have_incremental_build/) (I believe OCaml is too but not 100% sure)

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](https://github.com/salsa-rs/salsa) (used by some extent in [rust-analyzer](https://rust-analyzer.github.io/)), or [typst](https://github.com/typst/typst) (a LaTeX alternative with a sort of live preview, which uses a technique called ["Constrained Memoization"](https://github.com/typst/comemo)). In the extreme case, compilers like [Unison](https://www.unison-lang.org/learn/the-big-idea/#structured-refactoring) 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:

* [merlin](https://github.com/ocaml/merlin) (OCaml)
* [TypeScript language server](https://github.com/typescript-language-server/typescript-language-server) (able to incrementally type-check, tsc is not incremental)
* [rust-analyzer](https://rust-analyzer.github.io/) via [salsa](https://salsa-rs.github.io/salsa/overview.html)

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**?
**Tags:** compilers type-checker ide
> **Comments:**
> **username_1**: see: 'incrementalizing abstract interpretation' (https://ceur-ws.org/Vol-2047/BENEVOL_2017_paper_9.pdf https://cris.vub.be/ws/portalfiles/portal/35598203/BENEVOL_incrementalAAM.pdf) and 'demanded abstract interpretation' (https://arxiv.org/pdf/2104.01270.pdf)  
---
## 5 answers
### Answer by username_8 on 2023-09-07. Score: 23
> 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.
> **Comments:**
> **username_0** (2023-09-08): The lexer and parser sound a lot like tree-sitter (https://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  
---
### Answer by username_2 on 2023-09-08. Score: 5
**TL;DR: Lazy, on-demand, pull resolution.**

You already mentioned [salsa](https://github.com/salsa-rs/salsa), its README mentions that it was inspired from [adapton](http://adapton.org/) and [glimmer](https://github.com/glimmerjs/glimmer-vm).

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.
---
### Answer by username_3 on 2023-09-07. Score: 4
This sounds like something [e-graphs](https://egraphs-good.github.io/) 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](https://langdev.stackexchange.com/questions/2710/how-can-type-systems-be-a-useful-formal-framework-for-modeling-things-other-than). 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.
---
### Answer by username_4 on 2023-09-07. Score: 3
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.
> **Comments:**
> **username_5** (2023-09-07): 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!  
---
### Answer by username_6 on 2023-09-07. Score: 2
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.
> **Comments:**
> **username_0** (2023-09-08): 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.  
> **username_6** (2023-09-08): @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.  
> **username_7** (2023-10-03): 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.  
> **username_6** (2023-10-03): @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.  
> **username_7** (2023-10-04): 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.  
> **username_6** (2023-10-04): @occipita: If the function it calls gets expanded in-line, then machine code for that function will be incorporated within machine code for the function that invoked it, and debug information should reflect that.  If one subscribes to the theory that any change to a source file should require fully regenerating everything "downstream" of it, simply regenerating everything downstream wouldn't be a problem.  In many cases, however, a change will only affect a small portion of a source file, which is only used by a few clients, and the portions used by most clients will be unmodified.  
> **username_6** (2023-10-04): @occipita: If a few lines were added to the source file above a function which is *otherwise* unchanged, and a module uses that function but nothing else, the only thing in that module which would change as a result of the source file modification would be the line numbers within that function.  
---
