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:
- gcc, clang, MSVC (any C/C++ compiler which produces object files, since unmodified source files don't need to be recompiled)
- C# compiler
- javac (Java compiler)
- zinc (Scala's incremental compiler)
- Kotlin compiler
- Various compilers for SML including MLkit and SML/NJ (StandardMLImplementations)
- rustc (Rust compiler)
- Go is incremental, albeit only at the package level (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 (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:
- merlin (OCaml)
- TypeScript language server (able to incrementally type-check, tsc is not incremental)
- rust-analyzer via salsa
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?