The problem: recomputation is everywhere

Consider what happens when a character is typed in an IDE. The language server needs to:

  1. Re-lex the modified file (or at least the modified region)
  2. Re-parse the affected syntax tree nodes
  3. Re-resolve names in the modified scope
  4. Re-typecheck expressions that depend on any changed types
  5. Regenerate diagnostics, completions, hover info

For a naive implementation, every keystroke triggers a full pipeline rerun. In a 100K-line codebase with complex type inference, that's easily 2-5 seconds. Users notice anything above 100ms. Something has to give.

The traditional answer is "cache everything and invalidate carefully." But manual cache invalidation in a compiler pipeline is a nightmare. Dependencies are deep, circular, and change shape depending on the input. Miss one invalidation edge and you get stale results. Over-invalidate and you're back to full recomputation.

Incremental computation frameworks automate this. You describe your computation as a graph of queries, the framework tracks dependencies at runtime, and when an input changes, it recomputes exactly what's needed, nothing more.

Salsa: demand-driven incremental computation

Salsa is a Rust framework developed by the rust-analyzer team (originally by Niko Matsakis). It implements demand-driven incremental computation with automatic dependency tracking.

The core model has three concepts:

  1. Inputs, mutable values you set from outside (file contents, configuration)
  2. Tracked functions, pure computations that read inputs and other tracked functions
  3. The database, holds all inputs, cached results, and dependency metadata

The following is a minimal example, a system that parses files and computes a symbol index:

#[salsa::input]
pub struct SourceFile {
 #[return_ref]
 pub name: String,
 #[return_ref]
 pub contents: String,
}

#[salsa::tracked]
pub struct ParsedFile<'db> {
 #[return_ref]
 pub ast: Ast,
 #[return_ref]
 pub errors: Vec<ParseError>,
}

#[salsa::tracked]
fn parse_file<'db>(db: &'db dyn Db, file: SourceFile) -> ParsedFile<'db> {
 let contents = file.contents(db);
 let (ast, errors) = parser::parse(&contents);
 ParsedFile::new(db, ast, errors)
}

#[salsa::tracked]
fn file_symbols<'db>(db: &'db dyn Db, file: SourceFile) -> Vec<Symbol> {
 let parsed = parse_file(db, file);
 let ast = parsed.ast(db);
 extract_symbols(ast)
}

#[salsa::tracked]
fn all_symbols<'db>(db: &'db dyn Db, files: &[SourceFile]) -> SymbolIndex {
 let mut index = SymbolIndex::new();
 for &file in files {
 for symbol in file_symbols(db, file) {
 index.insert(symbol);
 }
 }
 index
}

When you call all_symbols, Salsa executes the full computation and records that all_symbols depends on file_symbols for each file, which depends on parse_file, which depends on the file's contents input.

Now change one file's contents. On the next call to all_symbols, Salsa:

  1. Notices the contents input changed for one file
  2. Checks if parse_file's result actually changed (maybe you only changed a comment)
  3. If the parse result changed, checks if file_symbols changed
  4. Only recomputes all_symbols if the actual symbol list for that file changed

This is the key insight: early cutoff. Even if an input changes, if the intermediate result is the same as before, downstream computations don't need to re-run. In practice, this means changing a function body doesn't invalidate the symbol index, the symbols didn't change.

The revision counter

Internally, Salsa uses a global revision counter. Every time an input changes, the revision increments. Each cached value stores two things:

  • verified_at: the last revision where this value was confirmed valid
  • changed_at: the last revision where this value actually changed

When you access a cached value, Salsa checks if verified_at == current_revision. If not, it walks the dependency graph backward to see if any input that this value (transitively) depends on has changed_at > verified_at. If no dependency changed, the value is still valid, update verified_at and return the cached result without recomputing.

Revision 1: Initial computation
 file.contents changed_at=1
 parse_file changed_at=1 verified_at=1
 file_symbols changed_at=1 verified_at=1
 all_symbols changed_at=1 verified_at=1

Revision 2: Edit file A (comment only)
 file_A.contents changed_at=2
 parse_file(A) → recompute → AST identical → changed_at=1 verified_at=2
 file_symbols(A) → dependency unchanged → changed_at=1 verified_at=2
 all_symbols → dependency unchanged → changed_at=1 verified_at=2
 // Total work: re-parsed one file. Everything else was free.

Revision 3: Edit file B (add a function)
 file_B.contents changed_at=3
 parse_file(B) → recompute → AST different → changed_at=3 verified_at=3
 file_symbols(B) → recompute → new symbol → changed_at=3 verified_at=3
 all_symbols → recompute (one dep changed) → changed_at=3 verified_at=3
 // parse_file(A), file_symbols(A) untouched, still verified_at=2, valid.

Cycle handling

Compilers often have circular dependencies, a trait implementation might reference a type that references the trait. Salsa handles cycles explicitly:

#[salsa::tracked(cycle_fn=recover_type_cycle)]
fn infer_type<'db>(db: &'db dyn Db, expr: ExprId) -> Type {
 // ... may call infer_type on other expressions
}

fn recover_type_cycle<'db>(
 db: &'db dyn Db,
 _cycle: &salsa::Cycle,
 expr: ExprId,
) -> Type {
 Type::Error // Break the cycle with an error type
}

When Salsa detects a cycle (the same query is called recursively with the same key), it invokes the recovery function. The recovery function determines the behavior, error types, fixed-point iteration, or any domain-appropriate strategy.

Adapton: the academic foundation

Adapton predates Salsa and provides the theoretical framework. The core paper (Hammer et al., 2014) introduces "demanded computation graphs", a model where computations are nodes, data dependencies are edges, and the system lazily propagates changes through the graph.

The key contribution is the distinction between two strategies:

From-scratch consistency: verify the entire graph is consistent before returning any result. Expensive upfront but guarantees correctness.

Demanded consistency: only verify the portions of the graph that the current query touches. Lazy, efficient, but requires careful ordering.

Salsa uses demanded consistency. When you query all_symbols, it doesn't verify every cached value in the system, only the ones in the dependency chain of all_symbols.

The following is a simplified Adapton-style implementation in TypeScript to make the concepts concrete:

type CellId = number;
type ThunkId = number;

let currentRevision = 0;
let activeThunk: ThunkId | null = null;

interface Cell<T> {
 value: T;
 changedAt: number;
 dependents: Set<ThunkId>;
}

interface Thunk<T> {
 fn: () => T;
 value: T | undefined;
 verifiedAt: number;
 changedAt: number;
 dependencies: Set<CellId | ThunkId>;
 dependents: Set<ThunkId>;
}

const cells = new Map<CellId, Cell<any>>();
const thunks = new Map<ThunkId, Thunk<any>>();

function createCell<T>(value: T): CellId {
 const id = cells.size;
 cells.set(id, { value, changedAt: currentRevision, dependents: new Set() });
 return id;
}

function setCell<T>(id: CellId, value: T): void {
 const cell = cells.get(id)!;
 if (Object.is(cell.value, value)) return; // Early cutoff
 currentRevision++;
 cell.value = value;
 cell.changedAt = currentRevision;
}

function readCell<T>(id: CellId): T {
 const cell = cells.get(id)!;
 if (activeThunk !== null) {
 const thunk = thunks.get(activeThunk)!;
 thunk.dependencies.add(id);
 cell.dependents.add(activeThunk);
 }
 return cell.value;
}

function createThunk<T>(fn: () => T): ThunkId {
 const id = thunks.size + 10000; // Offset to distinguish from cells
 thunks.set(id, {
 fn,
 value: undefined,
 verifiedAt: -1,
 changedAt: -1,
 dependencies: new Set(),
 dependents: new Set(),
 });
 return id;
}

function queryThunk<T>(id: ThunkId): T {
 const thunk = thunks.get(id)!;

 if (thunk.verifiedAt === currentRevision) {
 return thunk.value!; // Already verified this revision
 }

 // Check if any dependency changed since last verification
 let needsRecompute = thunk.value === undefined;
 if (!needsRecompute) {
 for (const dep of thunk.dependencies) {
 if (dep < 10000) {
 // Cell dependency
 const cell = cells.get(dep)!;
 if (cell.changedAt > thunk.verifiedAt) {
 needsRecompute = true;
 break;
 }
 } else {
 // Thunk dependency, recursively verify
 queryThunk(dep);
 const depThunk = thunks.get(dep)!;
 if (depThunk.changedAt > thunk.verifiedAt) {
 needsRecompute = true;
 break;
 }
 }
 }
 }

 if (needsRecompute) {
 thunk.dependencies.clear();
 const prevActive = activeThunk;
 activeThunk = id;
 const newValue = thunk.fn();
 activeThunk = prevActive;

 if (!Object.is(newValue, thunk.value)) {
 thunk.changedAt = currentRevision;
 thunk.value = newValue;
 }
 }

 thunk.verifiedAt = currentRevision;
 return thunk.value!;
}

This is ~80 lines that capture the essential algorithm. Real frameworks add garbage collection of unused cache entries, parallel execution, durability, and proper cycle detection, but the core idea is dependency tracking plus early cutoff.

Applying this outside compilers

Incremental computation patterns apply effectively in non-compiler contexts. Consider a dashboard that aggregates data from 15 microservices, as a representative example. Each service updates at different frequencies, some every second, some every hour. The dashboard computes derived metrics from combinations of these sources.

Before: every render fetches all 15 sources and recomputes all metrics. Latency: 800ms.

After: modeling each data source as an input cell, each metric as a tracked computation, and using a lightweight Adapton-style framework. On most renders, only 1-2 sources have changed, so only the affected metrics recompute. Latency drops to 30-80ms depending on what changed.

The pattern works anywhere you have: slowly-changing inputs, expensive derived computations, and repeated queries. Build systems (Bazel's action graph), reactive UI frameworks (Solid.js signals), spreadsheet engines, they all use variations of the same idea.

Practical takeaways

For any system that repeatedly derives data from changing inputs, it is worth considering whether incremental computation fits. The upfront investment in modeling computation as a query graph pays dividends when the dataset grows. Salsa is a natural starting point for Rust projects, and the concepts port to other languages (the TypeScript sketch above serves as a starting point). The mental model, inputs, tracked functions, dependency graphs, early cutoff, is the valuable part, not any specific framework.

As a concrete example, restructuring a language server around proper Salsa query boundaries brought autocompletion from 400ms down to 8ms. The computation was the same. The only difference was defining where the query boundaries were.