<!-- Canonical: https://lucioduran.com/blog/incremental-computation-salsa-adapton-frameworks
Language: en
Content-SHA256: 1ab7e469c31a01a6e98600672bf480d471ecf7ce390fad57f50f129a3f4eeb7a
-->

Compilers

# Incremental Computation with Salsa and Adapton Frameworks

2025-10-068 min read

Lucio Durán
Engineering Manager & AI Solutions Architect

Also available in: [Español](<https://lucioduran.com/es/blog/incremental-computation-salsa-adapton-frameworks>)

## 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](<https://github.com/salsa-rs/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:

```rust
#[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:

```rust
#[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](<http://adapton.org/>) 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:

```typescript
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.

## Frequently asked questions

### What is incremental computation?

Incremental computation is a programming paradigm where computations automatically reuse previous results when inputs change partially. Instead of recomputing everything from scratch, the system identifies what changed and only recomputes the affected portions of the result.

### How does Salsa differ from regular memoization?

Regular memoization caches results by input but has no invalidation mechanism, stale entries persist forever. Salsa tracks dependencies between computations, so when an input changes, it knows exactly which cached results are affected and invalidates only those, while preserving all unaffected cached results.

### Can I use Salsa outside of compiler tooling?

Yes, Salsa is a general-purpose incremental computation framework. Any workload where you repeatedly compute derived data from slowly-changing inputs benefits, build systems, data pipelines, reactive UIs, and configuration management are all viable use cases.

## Tips

1. **Tip:** When modeling incremental computations, make your input granularity match your invalidation granularity. If you track changes per-file but compute per-function, you'll recompute entire files when a single function changes, defeating the purpose.
2. **Tip:** Always separate ` reads ` from ` writes ` in your query definitions. A query that both reads and mutates state breaks the incremental DAG and forces full recomputation downstream.
3. **Tip:** Use ` salsa::accumulator ` for diagnostics collection instead of side-effecting during queries. Accumulators integrate cleanly with the dependency graph and get invalidated properly.
4. **Tip:** Profile query hit rates with ` salsa::DebugQueryTable ` before optimizing. Teams have been observed spending weeks optimizing a query that was already 99.8% cached, the bottleneck was somewhere else entirely.

- incremental-computation
- salsa
- adapton
- rust-analyzer
- compilers
- ide
- demand-driven
- memoization

[Back to Blog](<https://lucioduran.com/blog>)