Query-Based Compilation: From First Principles to a Working Engine#

Metadata#

• Part: 1, Fundamentals and a safe learning engine
• Language: Rust
• Running compiler: TinyLox, a small expression-and-function language
• Destination: a query engine that can eventually reuse work across edits
• Scope: dependency discovery, identity, transactions, and first-stage memoization

Learning outcomes#

By the end of this part, you will be able to:

1. Explain why a query graph is different from a fixed compiler pipeline.
2. Distinguish on-demand, memoized, incremental, and parallel execution.
3. State incremental correctness as equivalence with a clean rebuild.
4. Identify a query's kind, key, value, and invocation.
5. Explain why dependencies must be recorded where values are fetched.
6. Choose a useful query granularity with a simple cost model.
7. Separate stable identity from mutable source location.
8. Build a safe Rust engine that discovers dynamic dependency edges.
9. Add single-revision memoization without claiming cross-revision reuse.
10. Explain verified_at and changed_at as different facts.

Prerequisites#

You should be comfortable with Rust structs, enums, traits, Result, and collections. You should recognize compiler terms such as token, syntax tree, and type checking. No prior knowledge of incremental computation is required. The code favors explicit ownership over advanced lifetime techniques.

How to study this chapter#

Read each invariant before its implementation. An invariant is a condition that must remain true whenever public engine code returns. Trace the small examples by hand before checking the supplied answer. Type the sketches into a scratch crate if you want executable versions. The sketches form one design, but some omit routine derives or error formatting for focus. Treat every cache hit as a correctness claim, not merely a speed trick.

Glossary#

• Query: a named computation from a key to a value.
• Query kind: the operation, such as “parse this file.”
• Key: the identity of the requested subject, such as FileId(2).
• Value: the result produced for that key, such as an AST.
• Invocation: one query kind paired with one particular key.
• Dependency: an invocation whose value was fetched while evaluating another invocation.
• Root: an invocation explicitly demanded by the outside world.
• Memo: a stored query result plus metadata used to judge reuse.
• Revision: a logical snapshot of all compiler inputs.
• Durability: an estimate of how often an input changes; it is not used in part 1.
• HIR: high-level intermediate representation, syntax normalized for semantic analysis.
• MIR: mid-level intermediate representation, control flow made explicit.
• RAII: Rust's resource cleanup pattern in which Drop restores state automatically.
• Backdating: marking a recomputed value as unchanged since an older revision.

1. From batch pipeline to query graph#

A batch driver fixes the schedule: source -> tokens -> AST -> HIR -> types -> MIR -> codegen. Stage order hides dependencies, and a small edit can rerun whole-program stages. A query compiler instead names computations and lets each computation fetch what it needs.

emit(App)
  +--> mir(main) --> type_of(main) --> hir(main) --> parse(app.lox)
  |                    +--> signature(print)
  +--> runtime_abi(target)

An arrow means the query at its tail fetched the invocation at its head. The driver asks for roots, invocations demanded by a build or editor action. Recursive fetches schedule only work reachable from those roots.

Prediction checkpoint 1#

If the only root is tokens(FileId(0)), do parsing and type checking run? Answer: No; lexing answers the root without fetching them.

2. Four independent properties#

On-demand execution avoids unrequested work but may recompute every request. Memoized execution reuses an invocation inside some validity domain, perhaps one snapshot. Incremental execution validates and reuses work across changed snapshots, called revisions. Parallel execution overlaps independent work; it does not imply any kind of reuse. Our engine is single-threaded so synchronization and deadlocks do not hide the fundamentals.

3. Correctness: clean rebuild equivalence#

For inputs I and root R, let Clean(I, R) use an empty cache. For any prior history, correctness requires:

Inc(history, I, R) == Clean(I, R)

Equality covers code, diagnostics, and specified ordering, not timing or allocation addresses. Today's answer must not depend on what happened to be compiled yesterday. TinyLox can stabilize diagnostics by sorting on file ID, span, and diagnostic code.

Prediction checkpoint 2#

Code matches a clean build, but a new type error is omitted. Is the build correct? Answer: No; diagnostics are observable output.

4. Query anatomy and dynamic edges#

For parse(FileId(7)) -> Ast, Parse is the kind, FileId(7) the key, and Ast the value. The kind-key pair is one invocation; changing either member names another cache entry. Inputs are queries too: source_text(FileId(7)) exposes the actual boundary of change. Edges are dynamic because source determines which names, functions, and modules are fetched.

fun area(r) { return pi * r * r; }
fun unused() { return mystery + 1; }
print area(3);

Checking area fetches pi; it need not fetch mystery. At every fetch of B, record A -> B when A is active, on both hits and misses. Manual dependency reports are unsafe because one forgotten report permits stale reuse.

push TypeOf(1)
  fetch Hir(1); record TypeOf(1) -> Hir(1)
    fetch Parse(0); record Hir(1) -> Parse(0)
      fetch SourceText(0); record Parse(0) -> SourceText(0)
  fetch Signature(4); record TypeOf(1) -> Signature(4)
pop TypeOf(1)

5. Graphs, cycles, and roots#

A DAG is a directed acyclic graph, but a compiler graph is not necessarily one. Mutual recursion and module imports can form cycles; accidental query recursion can too. Some language cycles require a fixed point, a result stable under repeated computation. Others are user errors or bad query decomposition; part 1 reports any active-key cycle. Roots express policy as well as runtime reachability.

build(App)
  +--> codegen(reachable functions)
  +--> diagnostics(all declarations)
          +--> type_of(unused) --> resolve(mystery) --> error

TinyLox requires all declared functions to be valid, even unreachable ones. Thus root forcing still checks unused; on-demand does not mean “ignore dead source.”

Prediction checkpoint 3#

Can codegen(main) alone succeed despite the error in unused? Answer: Possibly, but a conforming build also forces all-declaration diagnostics and fails.

6. The TinyLox ladder#

SourceText(FileId) -> Tokens(FileId) -> Ast(FileId)
 -> HirBody(FnId) -> TypeTable(FnId) -> MirBody(FnId)
 -> ObjectCode(FnId, TargetId)

Tokens classify characters and retain spans; the AST preserves syntax and parse errors. HIR normalizes syntax, type tables annotate HIR, and MIR makes control flow explicit. Code generation lowers MIR to target instructions; side edges fetch names, options, and ABI data.

7. Granularity and cost#

Program-grained queries minimize overhead but lose all semantic reuse after most edits. File granularity fits lexing and parsing; function granularity often balances semantic reuse and cost. Expression granularity maximizes precision but can create millions of memos and edges. Choose separately per stage and measure realistic edits. For N requests, compute cost C, hit cost H, validation cost V, and reusable fraction p:

T_clean = N * C
T_inc = N * H + p * N * V + (1 - p) * N * C

Include memo bytes, dependency edges, retained values, and synchronization in the decision. Instrument requested, executed, cache_hits, validated, and value_changed per kind. Record exclusive time without children, inclusive time with children, and dependency counts. Benchmark whitespace, body, signature, and option edits; clean builds cannot measure incrementality.

8. Identity is not location#

A byte span is a location and shifts when earlier text is inserted. A stable ID should continue naming the same declaration after ordinary movement. Our table indices are type-safe but not yet stable across reparsing; production engines match trees or intern declaration paths.

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct FileId(u32);
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct FnId(u32);
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct SymbolId(u32);

FnId(3) and FileId(3) differ despite equal integers. Typed IDs prevent accidental interchange but do not alone provide cross-revision stability.

Prediction checkpoint 4#

A function moves from line 4 to line 40 unchanged. Should its semantic key change? Answer: Ideally no; location changed, identity did not.

9. Engine zero: correct, on-demand, uncached#

We now build from a baseline that has no reuse. This is important because its output becomes our clean-rebuild oracle.

The first invariant is simple:

Every query fetch computes from current input tables and returns that result.

Our input table owns source text by typed ID.

#[derive(Default)]
struct Inputs {
	files: Vec<String>,
}

impl Inputs {
	fn add_file(&mut self, text: impl Into<String>) -> FileId {
		let id = FileId(self.files.len() as u32);
		self.files.push(text.into());
		id
	}

	fn source(&self, id: FileId) -> &str {
		&self.files[id.0 as usize]
	}
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct Tokens(Vec<String>);
#[derive(Clone, Debug, PartialEq, Eq)]
struct Ast {
	forms: Vec<String>,
}
struct Engine0 {
	inputs: Inputs,
}
impl Engine0 {
	fn parse(&self, file: FileId) -> Ast {
		let forms = self.inputs.source(file)
			.split_whitespace().map(str::to_owned).collect();
		Ast { forms }
	}
}

Calling parse(file) twice recomputes twice: this is on-demand but not memoized.

10. A typed facade over erased storage#

Rust callers should see methods such as tokens(FileId) -> Tokens. The cache, however, needs one heterogeneous namespace for all invocations. We erase invocation identity into an enum while keeping values typed at the facade.

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
enum QueryKey {
	SourceText(FileId),
	Tokens(FileId),
	Parse(FileId),
	HirBody(FnId),
	TypeTable(FnId),
}

#[derive(Clone, Debug, PartialEq, Eq)]
enum QueryValue {
	Text(String),
	Tokens(Tokens),
	Ast(Ast),
}

The invariant is that each QueryKey variant always maps to its matching value variant. Only the typed facade constructs and decodes these pairs. A mismatched variant indicates an engine bug, not a user program error.

One typed cache per kind avoids erasure but complicates generic traversal; Any is another, less explicit option.

11. The active query stack#

The stack invariant is:

On every exit path, successful or not, the stack equals its state before the query began.

RAII cleanup handles early returns and ?; RefCell permits nested single-threaded fetches.

use std::cell::RefCell;
use std::collections::{HashMap, HashSet};

#[derive(Default)]
struct Runtime {
	stack: RefCell<Vec<QueryKey>>,
	edges: RefCell<HashMap<QueryKey, HashSet<QueryKey>>>,
}

struct ActiveGuard<'a> {
	runtime: &'a Runtime,
	expected: QueryKey,
}

impl Drop for ActiveGuard<'_> {
	fn drop(&mut self) {
		let actual = self.runtime.stack.borrow_mut().pop();
		debug_assert_eq!(actual, Some(self.expected));
	}
}

#[derive(Clone, Debug, PartialEq, Eq)]
enum QueryError {
	Cycle(Vec<QueryKey>),
	WrongValue(QueryKey),
}

impl Runtime {
	fn enter(&self, key: QueryKey) -> Result<ActiveGuard<'_>, QueryError> {
		if let Some(parent) = self.stack.borrow().last().copied() {
			self.edges.borrow_mut().entry(parent).or_default().insert(key);
		}

		let stack = self.stack.borrow();
		if let Some(start) = stack.iter().position(|item| *item == key) {
			let mut cycle = stack[start..].to_vec();
			cycle.push(key);
			return Err(QueryError::Cycle(cycle));
		}
		drop(stack);

		self.stack.borrow_mut().push(key);
		Ok(ActiveGuard { runtime: self, expected: key })
	}
}

Prediction checkpoint 5#

Parse(0) fetches Tokens(0), which is already memoized. Should the parse-to-tokens edge be recorded?

Answer: Yes. Parse used that value regardless of whether tokens executed or hit a cache.

12. Fetch boundaries and an uncached typed engine#

Every public typed query routes through one internal fetch operation. That operation enters the runtime before dispatching computation. Input reads are also fetched, so Tokens depends on SourceText explicitly.

struct Engine1 {
	inputs: Inputs,
	runtime: Runtime,
}

impl Engine1 {
	fn fetch(&self, key: QueryKey) -> Result<QueryValue, QueryError> {
		let _guard = self.runtime.enter(key)?;
		match key {
			QueryKey::SourceText(file) =>
				Ok(QueryValue::Text(self.inputs.source(file).to_owned())),
			QueryKey::Tokens(file) => self.compute_tokens(file),
			QueryKey::Parse(file) => self.compute_parse(file),
			_ => unreachable!("later TinyLox query"),
		}
	}

	fn source_text(&self, file: FileId) -> Result<String, QueryError> {
		match self.fetch(QueryKey::SourceText(file))? {
			QueryValue::Text(value) => Ok(value),
			_ => Err(QueryError::WrongValue(QueryKey::SourceText(file))),
		}
	}

	fn tokens(&self, file: FileId) -> Result<Tokens, QueryError> {
		match self.fetch(QueryKey::Tokens(file))? {
			QueryValue::Tokens(value) => Ok(value),
			_ => Err(QueryError::WrongValue(QueryKey::Tokens(file))),
		}
	}
}

The compute methods call typed facade methods rather than reading inputs directly. That rule is the dependency-recording discipline.

impl Engine1 {
	fn compute_tokens(&self, file: FileId) -> Result<QueryValue, QueryError> {
		let text = self.source_text(file)?;
		let words = text.split_whitespace().map(str::to_owned).collect();
		Ok(QueryValue::Tokens(Tokens(words)))
	}

	fn compute_parse(&self, file: FileId) -> Result<QueryValue, QueryError> {
		let tokens = self.tokens(file)?;
		Ok(QueryValue::Ast(Ast { forms: tokens.0 }))
	}
}

fetch(Parse) leaves Parse active while nested fetch(Tokens) records the correct edge. The following failure-path test proves RAII cleanup:

#[test]
fn cycle_error_restores_the_stack() {
	let runtime = Runtime::default();
	let key = QueryKey::Parse(FileId(0));
	let outer = runtime.enter(key).unwrap();
	let error = match runtime.enter(key) {
		Ok(_) => panic!("expected a cycle"),
		Err(error) => error,
	};
	assert!(matches!(error, QueryError::Cycle(_)));
	drop(outer);
	assert!(runtime.stack.borrow().is_empty());
}

13. Revision transactions#

Incremental state must describe coherent snapshots. Changing three inputs one at a time while queries run could expose a mixed revision. A revision transaction groups edits and advances the revision once.

#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
struct Revision(u64);

struct Transaction<'a> {
	inputs: &'a mut Inputs,
	dirty: bool,
}

impl Transaction<'_> {
	fn set_source(&mut self, file: FileId, text: impl Into<String>) {
		let slot = &mut self.inputs.files[file.0 as usize];
		let text = text.into();
		if *slot != text {
			*slot = text;
			self.dirty = true;
		}
	}
}

Commit increments a checked Revision once only when dirty is true. An exclusive &mut Engine transaction prevents fetches during edits. Production code should stage writes for panic-atomic commit; this sketch mutates eagerly.

Prediction checkpoint 6#

A transaction sets a file to byte-for-byte identical text. Must the revision advance?

Answer: No. Keeping the revision is safe because the logical input snapshot did not change. Advancing would also be correct, but less efficient.

14. Single-revision memoization#

Before cross-revision validation, add a deliberately limited cache. Its invariant is:

A memo may be reused only when it was computed in the current revision.

This cache prevents duplicate work during one build or editor request sequence. After any committed input change, every old memo is treated as unavailable. That is memoization, not yet incremental computation.

The memo stores the value and direct dependencies discovered during execution. It also carries two revision fields whose full use arrives in part 2.

#[derive(Clone, Debug)]
struct Memo {
	value: QueryValue,
	dependencies: Vec<QueryKey>,
	verified_at: Revision,
	changed_at: Revision,
}

#[derive(Default)]
struct MemoTable {
	entries: HashMap<QueryKey, Memo>,
}

Store direct edges only and replace them on recomputation so removed dependencies do not linger.

15. Cache lookup order#

A safe conceptual order is:

1. Record parent -> requested key.
2. Reject the key if it is active.
3. Return a memo only if memo.verified_at == current revision.
4. Push the key and clear its old outgoing dependencies.
5. Compute through typed fetches.
6. Snapshot direct dependencies.
7. Store the memo and pop through RAII.

Split the earlier enter so a hit records an edge and checks cycles without pushing.

impl Runtime {
	fn observe_request(&self, child: QueryKey) {
		if let Some(parent) = self.stack.borrow().last().copied() {
			self.edges.borrow_mut().entry(parent).or_default().insert(child);
		}
	}

	fn is_active(&self, key: QueryKey) -> bool {
		self.stack.borrow().contains(&key)
	}

	fn activate(&self, key: QueryKey) -> ActiveGuard<'_> {
		self.edges.borrow_mut().remove(&key);
		self.stack.borrow_mut().push(key);
		ActiveGuard { runtime: self, expected: key }
	}

	fn direct_dependencies(&self, key: QueryKey) -> Vec<QueryKey> {
		self.edges.borrow().get(&key)
			.into_iter().flatten().copied().collect()
	}
}

Sort HashSet dependencies before deterministic traces or tests.

16. The memoized fetch skeleton#

Values are cloned to release RefCell borrows; real values are usually cheap Arc handles.

struct RevisionState { current: Revision }
struct Engine2 {
	inputs: Inputs,
	runtime: Runtime,
	revisions: RevisionState,
	memos: RefCell<MemoTable>,
}

impl Engine2 {
	fn fetch(&self, key: QueryKey) -> Result<QueryValue, QueryError> {
		self.runtime.observe_request(key);
		if self.runtime.is_active(key) {
			return Err(QueryError::Cycle(vec![key]));
		}

		let now = self.revisions.current;
		if let Some(value) = self.memos.borrow().entries.get(&key)
			.filter(|memo| memo.verified_at == now)
			.map(|memo| memo.value.clone()) {
			return Ok(value);
		}

		let guard = self.runtime.activate(key);
		let value = self.compute(key)?;
		let dependencies = self.runtime.direct_dependencies(key);
		drop(guard);

		let memo = Memo {
			value: value.clone(),
			dependencies,
			verified_at: now,
			changed_at: now,
		};
		self.memos.borrow_mut().entries.insert(key, memo);
		Ok(value)
	}
}

A same-revision trace#

revision 0: fetch Parse(0)       miss
revision 0:   fetch Tokens(0)    miss
revision 0:     fetch Source(0)  miss
revision 0: fetch Parse(0)       hit; still record caller -> Parse(0)
commit changed source
revision 1: fetch Parse(0)       old memo rejected because verified_at is 0

Revision 1 recomputes even after an unrelated edit; part 2 will validate instead.

17. Testing the memoization boundary#

Instrumentation makes the intended limit testable. Assume executions[key] increments immediately before compute(key).

#[test]
fn repeated_fetch_hits_within_one_revision() {
	let engine = tinylox_engine("print 1;");
	let file = FileId(0);
	engine.fetch(QueryKey::Parse(file)).unwrap();
	engine.fetch(QueryKey::Parse(file)).unwrap();
	assert_eq!(engine.execution_count(QueryKey::Parse(file)), 1);
}

#[test]
fn old_revision_memo_is_not_trusted_yet() {
	let mut engine = tinylox_engine("print 1;");
	engine.fetch(QueryKey::Parse(FileId(0))).unwrap();
	engine.set_source_in_transaction(FileId(0), "print 2;");
	engine.fetch(QueryKey::Parse(FileId(0))).unwrap();
	assert_eq!(engine.execution_count(QueryKey::Parse(FileId(0))), 2);
}

18. Why two revision numbers?#

verified_at answers:

In which newest revision did the engine establish that this memo is valid?

changed_at answers:

In which revision did this query's observable value most recently change?

Suppose whitespace changes in app.lox:

revision 4: Tokens(0) value = normalized token sequence A
revision 5: SourceText(0) changes only in spacing
revision 5: Tokens(0) is recomputed and still produces A

After a future validation algorithm completes, the token memo can say:

verified_at = 5
changed_at  = 4

In the part 1 skeleton, every recomputation sets both fields to now. That is safe but misses the optimization called backdating. Part 2 will compare recomputed values, preserve older changed_at when equal, and validate red or green dependencies.

Final prediction checkpoint#

At revision 9, a query is validated and returns the same value it had at revision 6. What should the two fields eventually be?

Answer: verified_at should become 9, while changed_at should remain 6. The first records freshness of proof; the second records freshness of value.

19. Part 1 invariants collected#

1. Typed facade methods are the only way query code fetches values.
2. Every fetch records an edge from the active parent, including cache hits.
3. Input-table reads are represented as query fetches.
4. Active stack entries are removed on every exit path through RAII.
5. A repeated active invocation is a cycle, not a cache hit.
6. Outgoing dependencies are replaced on recomputation, not accumulated forever.
7. A part 1 memo is reusable only when verified_at equals the current revision.
8. A committed transaction advances the revision at most once.
9. Incremental output must equal a clean rebuild for the same inputs and roots.
10. verified_at describes a proof; changed_at describes a value transition.

We now have a correct clean baseline, dynamic dependency discovery, transaction-shaped input changes, and safe single-revision memoization. We do not yet have permission to reuse an old-revision memo. That permission requires the red-green validation and backdating rules developed in part 2.

Part II: Making Reuse Correct Across Edits#

The previous part ended with a compact record:

Memo { value, dependencies, verified_at, changed_at }

Those four fields are not yet an algorithm. They are evidence from which an algorithm can prove that reuse is safe. This part derives that proof, then follows its consequences into compiler architecture and production engineering.

1. The contract before the cache#

Let Q(k, S) mean running query kind Q with key k against logical state S. An incremental engine is correct when every requested result is observationally equal to Q(k, S_now) from a clean build. It may skip work, but it may not weaken that rule. “Observationally equal” includes more than the returned Rust value. Diagnostics, generated files, indexed symbols, and declared errors may all be observable. If the clean computation would retract an old observation, reuse must retract it too. We number committed states with monotonically increasing revisions. A revision is a logical timestamp, not wall-clock time. Several input changes may be committed together under one revision. For each memo:

• value is the last published result.
• dependencies records exactly what that execution observed.
• verified_at is the newest revision at which the memo was proved valid.
• changed_at is the newest revision at which its observable result changed.

The distinction between the last two timestamps powers reuse.

2. Fetch, validate, execute#

A request follows three conceptual phases.

1. Fetch locates the memo for (query, key).
2. Validate tries to prove the memo still denotes the clean result.
3. Execute recomputes when no proof is available.

The hot path is deliberately tiny. If memo.verified_at == current_revision, return the value immediately. No dependency walk is needed because this revision already has a proof.

fetch(Q, key):
    memo = table[Q].lookup(key)
    if memo exists and memo.verified_at == revision:
        record_dependency(Q, key, memo.changed_at)
        return memo.value

    if memo exists and validate(Q, key, memo):
        record_dependency(Q, key, memo.changed_at)
        return memo.value

    value = execute(Q, key, memo)
    record_dependency(Q, key, table[Q][key].changed_at)
    return value

Dependency recording occurs even on a hot hit. The caller depends on the callee's semantic value, not on whether the callee happened to run. Validation asks each old dependency for its current changed_at. That request recursively pulls validation through the reachable graph. The parent remains valid if none of those timestamps moved beyond the version it observed.

validate(Q, key, memo):
    for observed in memo.dependencies:
        current = fetch_changed_at(observed.dep)
        if current > observed.changed_at_when_read:
            return false
    memo.verified_at = revision
    return true

The update to verified_at publishes a new proof, not a new answer. This is why validation can make later requests in the same revision constant-time.

3. Inputs anchor recursive validation#

Input queries terminate the recursion. Setting an input compares the newly committed value with the old value. If unequal, its changed_at becomes the new revision. If equal, its changed_at remains where it was.

set_input(I, key, new):
    old = inputs[I].get(key)
    if old is absent or old.value != new:
        inputs[I][key] = Input { value: new, changed_at: revision }
    else:
        inputs[I][key].value = new
    inputs[I][key].verified_at = revision

Repeatedly setting opt_level = 2 must not redden the graph. Conversely, mutating input storage without moving changed_at is silent under-invalidation. Consider a TinyLox pipeline:

file_text(FileId) -> tokens(FileId) -> parse(FileId)
parse(FileId) + flags() -> lower(FunctionId) -> bytecode(FunctionId)

The first request at revision 1 computes every reachable node.

A second bytecode(f) request in revision 1 takes the hot path. Only a memo lookup and revision comparison are required.

4. Red, green, and recursive pull#

“Green” means validated as observably unchanged in this revision. “Red” means its observable result changed. Neither color says whether code executed.

At revision 2, edit a comment inside main.lox. The file input changes, so file_text(main).changed_at = 2.

Suppose tokens preserve comments for formatting. Then tokens(main) really changes and becomes red. That forces parse(main) to execute. If parsing discards comments, its new AST equals its old AST.

5. Equal-output backdating and early cutoff#

After execution, compare the new complete observation with the old one. If equal, retain the old changed_at even though the query just ran. This is backdating.

execute(Q, key, old_memo):
    frame = push_dependency_frame(Q, key)
    outcome = run_query_body(Q, key)
    observed = pop_dependency_frame(frame)

    if old_memo exists and observably_equal(outcome, old_memo.value):
        changed = old_memo.changed_at
    else:
        changed = revision

    publish Memo {
        value: outcome,
        dependencies: observed,
        verified_at: revision,
        changed_at: changed,
    }

The unchanged AST stays green with changed_at = 1. Its parents see no semantic change and need not execute. The red wave stops at parse; this is early cutoff.

changed_at must not mean recomputed_at. If it did, every executed child would force every ancestor to execute. The engine would remain correct but lose semantic cutoff.

Backdating is sound only when equality covers every observation. Comparing an AST while ignoring attached diagnostics is unsound if diagnostics are externally visible.

6. A semantic edit trace#

At revision 3, change print 1 + 2; to print 1 + 3;.

Every node executes because every direct observation changes. Unrelated bytecode(helper) remains untouched until requested. Demand, not revision advance, decides what is validated.

At revision 4, rename a local from subtotal to sum. Name resolution changes its symbol spelling, but MIR may use a stable local ID.

Granularity determines where such a cutoff is possible. A monolithic compile_crate query cannot preserve function-level reuse. Thousands of microscopic queries, however, may cost more bookkeeping than they save.

7. Dynamic dependencies replace, never accumulate#

Dependencies describe one execution, not all historical executions. Suppose TinyLox selects a prelude from a flag.

fn active_prelude(db: &Db, package: PackageId) -> Ast {
	if db.flag(package, "strict") {
		db.parse(db.strict_prelude(package))
	} else {
		db.parse(db.compat_prelude(package))
	}
}

Revision 1 observes flag(strict) and compat_prelude. Revision 2 flips the flag and observes flag(strict) and strict_prelude. The newly published dependency list must replace the old list atomically.

Keeping the compat edge causes over-invalidation when that dead branch changes. Dropping the flag edge causes under-invalidation when branch selection changes. Appending forever also leaks memory and makes validation increasingly expensive.

Recording begins before the body and ends only after its whole outcome is assembled. Dependencies from an aborted execution must not replace a previously valid set.

8. Outputs, deletions, and retractable facts#

Some computations publish multiple entities. Parsing may return an AST and emit syntax diagnostics. Code generation may return an artifact and publish auxiliary source maps.

Treat outputs as part of the memoized observation:

Outcome<T> {
    value: T,
    diagnostics: ordered set DiagnosticId,
    generated: ordered set ArtifactId,
}

When execution replaces {error E} with {}, the engine must retract E. When a generated function disappears, its old entity must be deleted or tombstoned. Merely inserting new outputs leaves ghosts from earlier revisions.

Stable output IDs permit consumers to observe replacement precisely. An ID derived from “third diagnostic emitted” is unstable under insertion. A structural owner plus local semantic key is usually better.

Side effects that cannot be replayed or retracted should not happen inside ordinary queries. Writing a file, logging billing events, or sending network requests on recomputation violates referential transparency. Instead, return a declarative output and let a committed outer phase apply it once.

Diagnostics are data, not print statements. Their equality must include message, severity, primary span, relevant labels, and fix-its. Presentation-only ordering can be normalized at the root if order has no semantics.

9. Errors and partial values#

Failure is often a valid query result. Result<T, E> can be cached, compared, and backdated like any other outcome. A parser may instead return Parsed { tree, errors } so later IDE stages can use a partial tree.

Do not confuse a language error with an engine failure. An undefined variable is stable user-facing data. A panic, violated invariant, or poisoned dependency frame is not a cacheable language result.

Choose installation rules explicitly:

• Install successful complete outcomes.
• Install deterministic language errors when their dependencies were completely observed.
• Install partial values only when their recovery contract is stable and complete.
• Do not install cancellation.
• Do not install panic-produced values.
• Do not replace an old memo with a half-recorded dependency set.

If an execution returns Err(TypeError) and emits a diagnostic, both belong to equality. Otherwise an equal error with a changed span could be incorrectly backdated.

10. Equality, hashes, and fingerprints#

Equality is a semantic boundary, not a convenience derive. Ignoring source spans may be correct for optimization but wrong for “go to definition.” Split semantic structure from location metadata or expose separate queries when consumers differ. Hashes accelerate comparison but cannot abolish collisions; a 64-bit fingerprint is not proof of equality. Compare full values after matching hashes, adopt an explicit collision-risk policy, or conservatively report changed. Pointer identity and allocation order are not content equality, and randomized map iteration needs canonical ordering before hashing. NaNs, signed zero, path and Unicode normalization, and case-folding all require deliberate semantics. If equality is not an equivalence relation, backdating can become history-dependent. A test should compare independently allocated equal results, then perturb ignored metadata and prove no downstream observer exposes it.

11. Tracked and untracked reality#

The dependency graph sees only reads routed through tracked queries. An untracked ambient read creates a hidden edge and can make stale reuse look valid.

Common hidden inputs include:

• filesystem contents, existence, directory listings, symlink targets, and permissions;
• environment variables and current working directory;
• wall-clock time, locale, timezone, and process identity;
• random seeds and nondeterministic iteration order;
• command-line flags, target configuration, and feature selection;
• dependency package metadata, tool versions, and generated manifests.

Tracking read_file(path) is insufficient when resolution also depends on whether sibling paths exist. Track the directory listing or model each existence probe. Tracking a file's timestamp alone is unsafe when timestamp precision or restoration can hide content changes.

Time and randomness usually belong outside pure queries. If semantics require them, inject a clock value or seed as an explicit input. Tests can then reproduce revisions exactly.

Flags should be keyed at the narrowest honest scope. Making one global Options value a dependency of every query causes avoidable fanout. Splitting options is safe only when every relevant read is routed to the right tracked field.

12. Immutable publication#

A published value must not change behind the memo's timestamps. Returning Arc<T> is safe only if T is effectively immutable. An Arc<Mutex<Vec<_>>> can mutate while changed_at remains old.

Interior mutability is especially dangerous when used for lazy caches inside values. It is acceptable only if the mutation is unobservable to equality and all query consumers. That claim must include serialization, debugging, hashing, and concurrent readers.

Build new values privately, finalize them, then atomically publish the memo. Readers should observe either the old complete memo or the new complete memo. Never publish the value before its dependency and output metadata.

Persistent immutable collections can reduce cloning cost. They do not replace revision bookkeeping; structural sharing says nothing about hidden inputs.

13. Stable IDs and interning#

Compiler values frequently refer to files, functions, symbols, and types. Raw pointers and vector indices are poor identities across recomputation. Stable IDs prevent harmless allocation changes from reddening everything. Interning maps an equal key to one canonical compact handle. It gives within-process identity, not automatically persistent identity. Insertion-order handles can differ after restart. Persistent caches need stable keys derived from canonical content or a durable mapping. Identity should represent semantic ownership. FunctionId(package, module, name, disambiguator) survives unrelated syntax insertion better than an AST node offset. Duplicate names require a deterministic disambiguation policy. Too-stable identity is also wrong. Reusing an ID after an entity was deleted can attach stale outputs to a new entity. Generation counters or tombstones can distinguish reincarnations.

14. Over- and under-invalidation#

Over-invalidation marks unaffected nodes changed or forces needless execution. It hurts latency but normally preserves correctness. Under-invalidation misses a real dependency or change and returns a stale answer. It is a correctness defect.

Typical over-invalidation sources are coarse keys, unstable IDs, nondeterministic ordering, broad option structs, and equality that is too strict. Typical under-invalidation sources are hidden inputs, equality that is too weak, mutable published values, missing outputs, and unsound fingerprints.

Optimize only after measuring both execution and validation. A query saved from recomputation may still traverse ten thousand dependencies. Sometimes a cheap recomputation is faster than proving reuse.

15. Tests that defend the algorithm#

Unit tests should assert work as well as answers.

#[test]
fn comment_edit_stops_at_equal_ast() {
	let db = tinylox_db("print 1 + 2; // old");
	assert_eq!(db.run_main(), Value::Nil);
	db.counters().reset();
	db.set_text("print 1 + 2; // new");
	assert_eq!(db.run_main(), Value::Nil);
	assert_eq!(db.counters().parse, 1);
	assert_eq!(db.counters().lower, 0);
	assert_eq!(db.counters().codegen, 0);
}

A branch test flips strict mode, edits the now-dead compat prelude, and verifies no strict result recomputes. An output test fixes a syntax error and verifies the old diagnostic disappears. A cancellation test aborts midway and verifies the previous memo remains intact.

The strongest practical oracle is differential clean rebuilding. Generate an edit sequence, evaluate roots incrementally, and compare each observation with a fresh database built from current inputs.

for edit in generated_edits:
    model.apply(edit)
    incremental.apply(edit)
    for root in selected_roots:
        expected = CleanDatabase::from(model).observe(root)
        actual = incremental.observe(root)
        assert canonical(actual) == canonical(expected)

Compare returned values, diagnostics, artifacts, and deletions. Vary root order to expose accidental dependence on evaluation history. Occasionally request no root for several revisions to test lazy catch-up.

16. Accidental recursion#

A query may request itself directly or through a chain. Without detection, recursive pull overflows the stack or deadlocks.

Maintain an active stack per execution context. Before executing (Q, k), check whether it is already active. If so, report the slice from its earlier occurrence to the top.

type_of(a) -> type_of(b) -> resolve(c) -> type_of(a)

This path is much more useful than “cycle detected.” Include query kinds, stable keys, and source locations when available. Do not dump sensitive source contents into telemetry by default.

An accidental cycle is usually a decomposition bug or invalid source program. Return a deterministic recoverable error if the language permits recovery. Otherwise stop that root without publishing partial ordinary memos.

17. Semantic cycles and fixed points#

Some languages intentionally define recursive facts. Mutually recursive functions, import groups, and dataflow analyses can be cyclic. Rejecting every cycle would reject valid programs.

A fixed point is a state that no longer changes when rules are applied. To compute one safely, facts need an ordering that means “contains no less information.” A lattice supplies that ordering and a join operation for combining facts.

For reachable blocks, the facts are sets. The bottom value is the empty set. Joining means set union. Each iteration can only add blocks, so a finite control-flow graph eventually stops changing.

facts = bottom
repeat:
    next = join(facts, transfer(facts))
    if next == facts: return facts
    facts = next

Monotonicity means more input information never produces less output information under the chosen ordering. It prevents an iteration from undoing facts and then adding them again forever. Finite height, or another convergence argument, is also required.

Not every recursive query has such semantics. Type inference with ad hoc “guess then retract” rules may oscillate between states. An iteration limit detects non-convergence but does not make the answer sound. Report the cycle and limit, and avoid caching the arbitrary last guess as final.

Fixed-point groups need dependency and revision semantics at group boundaries. Publishing each unstable intermediate value lets outside queries observe history-dependent states. Publish only the converged group outcome.

18. Cross-thread wait cycles#

Active-stack checks catch recursion within one thread. Parallel execution adds another graph: who is waiting for whom.

Thread A may own query X and wait for Y. Thread B may own Y and wait for X. Neither local stack contains a duplicate, yet the system deadlocks.

Represent in-flight ownership and waiter edges explicitly. Before blocking, detect whether adding a wait edge closes a cycle. Diagnostics should combine query stacks from all participants.

Alternatives include helping execute the awaited work, imposing a global acquisition order, or falling back to cycle recovery. No strategy is universally best; nested dynamic dependencies make a simple lock order difficult. Never hold a memo-table shard lock while executing arbitrary query code or waiting.

19. Compiler ownership boundaries#

Incrementality improves when representations have clear owners. The AST is usually owned by a source file and preserves syntax and spans. HIR can be owned by a module or item and resolves surface-language structure. MIR-like control flow is often owned by a function.

These are design roles, not mandatory names. The key is to choose keys that match likely edits and consumers. File-owned type checking may be simple; function-owned type checking may reuse more but require explicit module facts.

Symbols and canonical types are strong candidates for interning. Spans should refer to stable file IDs plus ranges, not borrowed source buffers. Source maps are observable outputs and must update when generated positions move.

Separating semantic identity from spans enables semantic cutoff after whitespace edits. IDE queries that display locations still depend on span-bearing queries. Do not globally erase locations merely to improve reuse.

20. Roots differ by product#

A batch compiler roots “build this package” and demands complete artifacts and deterministic diagnostics. An IDE roots the currently visible file, completion at one position, references for one symbol, or a workspace index slice.

The same query graph can serve both, but root policy controls work. Eagerly validating the entire workspace after every keystroke defeats pull-based latency. Never requesting background roots can leave search indexes stale.

Prioritize interactive roots and schedule broad indexing separately. Cancellation should stop obsolete low-priority work when a newer edit arrives. Batch mode may disable cancellation and favor throughput.

21. Snapshots and cancellation#

A snapshot is a consistent read view of one committed revision. All dependencies observed by a query should belong to that view. Mixing old file text with new flags can produce a result that matches no real state.

Copy-on-write inputs or multiversion storage can support readers while a writer commits a new revision. Alternatively, serialize commits and require old readers to cancel. The memory and latency tradeoff should be explicit.

Cancellation checks belong at query boundaries and in long loops. They should unwind through guards that release ownership, wake waiters, pop stacks, and discard provisional outputs. Cancellation is control flow, not a memoized error.

A waiter on cancelled work may retry under its own snapshot or receive cancellation. It must never receive an incompletely initialized value.

22. LRU and retention semantics#

LRU eviction is not simply deleting a map entry. Dropping all metadata forces recomputation but remains correct if no stale proof survives. Pinned in-flight values and snapshot-visible values cannot be evicted immediately. Interners may require stronger retention because handles appear throughout other values. Evicting an interned entry while handles survive can corrupt identity. Account separately for values, dependencies, outputs, reverse edges, interners, and persistent blobs. “Cache has 10,000 entries” says little about memory pressure. LRU changes performance, not semantics. Tests should run with capacities zero, one, and a comfortable size and obtain equal observations.

23. Persistence and stable hashes#

Cross-process reuse adds a trust boundary. In-memory IDs, randomized hashes, pointer addresses, and revision numbers do not survive restart. A persistent key should include canonical query identity, stable key encoding, relevant compiler version, target configuration, and schema version. Dependency fingerprints must represent the same observations used by clean execution. Deserialize defensively. Corrupt or incompatible entries should become cache misses, not compiler crashes or unsound hits. Content-addressed blobs need atomic writes and validation before publication. Stable hashing requires deterministic traversal. Sort unordered collections, normalize platform-sensitive paths only according to language semantics, and version every encoding rule. A compiler upgrade may invalidate all entries; correctness is more important than hit rate. Remote caches introduce confidentiality and authenticity concerns. Source-derived diagnostics or paths may leak through keys and telemetry. Untrusted artifacts may require signatures or local recomputation.

24. Pull, push, and hybrid invalidation#

Pull validation starts from demanded roots and recursively proves what matters. It avoids touching dormant subgraphs but can create latency spikes on first request.

Push invalidation follows reverse edges when an input changes. It can mark affected nodes eagerly, making later reads cheap. It may traverse enormous fanout for roots nobody requests.

Static edges are known from query definitions and are simple to index. Dynamic edges reflect actual branches and provide precision. Many compiler dependencies are inherently dynamic: imports, overload candidates, and selected configuration.

Reverse edges speed push invalidation and diagnostics about fanout. They must be replaced consistently when forward dynamic dependencies change. Stale extra reverse edges cause over-invalidation; missing reverse edges can be unsound in a push-only design.

A hybrid may push a coarse dirty bit and pull exact validation on demand. The clean-rebuild contract remains the judge, regardless of scheduling strategy.

25. Locks, shards, and waiters#

A single global mutex is easy to reason about and often sufficient for a learning engine. Production contention may justify sharding by query kind or hashed key.

Shard locks protect table structure, not query execution. Acquire, inspect or install an in-flight marker, release, then compute. Waiters subscribe to that marker and are awakened on completion, cancellation, or panic.

Duplicate computation can be acceptable if values are pure and publication resolves races safely. It trades CPU for simpler waiting and lower contention. Side effects would make this choice unsafe, another reason to keep bodies pure.

Rust mutex poisoning after panic is a policy signal, not automatic semantic recovery. The engine must restore in-flight state and either rebuild affected metadata or fail the database. Blindly publishing through a poisoned invariant risks stale answers.

Avoid callbacks while holding internal locks. User formatting, equality, hashing, allocation, and destructors can re-enter or panic. Keep critical sections short and define a lock order for unavoidable nesting.

26. Telemetry that answers design questions#

Measure requests, hot hits, validations, executions, backdates, cancellations, and evictions per query kind. Separate validation time from execution time. A high hit rate can hide expensive recursive proof walks. Record dependency and reverse-fanout distributions, because one hub can dominate tail latency. Contention metrics include lock wait time, waiter counts, duplicate work, and cross-thread wait depth. Track value bytes and metadata bytes separately. Track executed queries per edit, dependencies checked per root, cancellation CPU, and p50/p95/p99 latency. Sample long active stacks and validation chains using privacy-safe keys. Telemetry should not perturb query semantics. Counters must not become hidden inputs, and tracing must not alter ordering relied upon by buggy code.

27. Testing beyond examples#

Property tests generate databases, edit sequences, and root orders. The central property is equality with a clean rebuild after every committed edit. Shrink failures to the shortest history that produces divergence. Fuzz query keys, malformed source, cancellation points, persistence bytes, and cycle shapes. Inject panic at each publication step and verify no partial memo becomes visible. Run with deliberate hash collisions if the design uses fingerprint shortcuts. Miri can expose undefined behavior, invalid aliasing, and misuse of interior mutability in unsafe optimizations. It cannot prove the incremental algorithm correct. Loom can explore small concurrent schedules around ownership, waiters, cancellation, and publication. Keep Loom models tiny enough to exhaust meaningful interleavings. Determinism tests vary thread count, hash seeds, request order, and cache capacity. Persistence tests restart between every edit. Cycle tests distinguish same-thread recursion, semantic fixed points, and cross-thread waits. Performance regression tests need stable workloads and work counters in addition to wall time. Assert that a comment edit executes parsing but not lowering in the intended architecture. Do not encode optimizations as correctness requirements unless the API promises them.

28. When batch compilation is better#

Incrementality has fixed costs: memo storage, dependency recording, equality, validation, synchronization, testing, and conceptual complexity. A batch compiler is often better for tiny programs, one-shot commands, highly volatile whole-program analyses, or stages cheaper than their tracking overhead.

Batch execution is also easier to make deterministic and memory-bounded. If nearly every edit changes a global fact with enormous fanout, reuse may be negligible. If outputs cannot be made pure or retractable, wrapping them in queries can create more bugs than speed.

A hybrid compiler can batch cheap front-end work and incrementally cache expensive function-level analyses. Measure realistic edit traces before choosing granularity. The goal is not maximal caching; it is predictable correct performance.

The essential algorithm is now precise: fetch a current proof when one exists, recursively validate old evidence when it may still hold, and otherwise execute against one consistent snapshot. Publish complete immutable observations, backdate only under sound equality, and replace dynamic history rather than accumulating it. Everything else—parallelism, persistence, eviction, and sophisticated compiler representations—must preserve that proof.

Part III: How rustc Uses Its Own Query System#

rustc does NOT use Salsa.
It has its own compiler-specific query engine, generated interfaces, dependency graph, incremental cache, and recovery rules.

This distinction matters because “query-based” names an architecture, not a library. Salsa is useful for learning the architecture, but importing Salsa terminology into rustc can produce subtly wrong explanations. rustc's system is shaped by batch compilation, stable cross-session hashing, crate metadata, diagnostics, and code generation. It is not a stable API promised to Rust users, and its internal details continue to change.

1. The map before the machinery#

A query looks like a memoized function from a typed key to a typed result. For example, a caller can ask for the declared type of one definition or the optimized MIR of one body. The provider that computes the answer may ask other queries for their answers. Those nested calls dynamically build a dependency graph while ordinary Rust code runs.

The second and third operations are separate. Knowing that a node is green does not imply that its value was serialized. Conversely, bytes on disk are usable only after the dependency machinery proves that they correspond to a green node.

The compiler is demand-driven at query boundaries, but compilation itself has required outputs and required checks. Drivers therefore request roots eagerly: analyze the crate, check every relevant body, collect mono items, or emit code. Demand determines the transitive work below each root; orchestration determines which roots must be demanded. This hybrid avoids processing every possible artifact while still diagnosing errors in unreachable source.

2. A representative journey through rustc#

The following picture is intentionally a map, not a literal call graph.

source files
    |
    v
lexing + parsing -> AST -> macro expansion + name resolution
                              |
                              v
                    per-owner HIR lowering
                              |
                  +-----------+-----------+
                  |                       |
                  v                       v
              type_of(owner)       typeck_root(body owner)
                                             |
                                             v
                                            THIR
                                             |
                                             v
                                      mir_built(body)
                                             |
                                             v
                                     borrow checking
                                             |
                                             v
                                      optimized_mir
                                             |
                                             v
                               monomorphization collection
                                             |
                                             v
                                codegen units -> backend

Lexing, parsing, expansion, and resolution still contain coarse orchestration and mutable algorithms. They should not be imagined as a perfectly item-granular query pipeline. HIR lowering is substantially organized per owner, which gives later work useful identity and invalidation boundaries. An owner is roughly an item or body-owning definition, not every HIR node.

type_of answers the type attached to a definition; it is not “run all type checking.” Body type checking is organized around a type-checking root and produces collections of results for that root. THIR is a typed, high-level body representation used by several analyses and MIR construction paths. mir_built denotes built MIR before the later transformations implied by optimized MIR. Borrow checking consumes MIR-related facts and must run for bodies that require checking, including code that codegen never reaches.

Monomorphization discovers concrete instances reachable for code generation. That discovery requests optimized MIR and other semantic facts as needed, then partitions work into codegen units. The backend and linker are not transformed into one tiny query per machine instruction. Options such as check-only compilation also stop before parts of this path. The simplification is nevertheless useful: later products pull on earlier semantic facts rather than receiving one giant pass result. Fine keys can keep an edit to one owner from invalidating unrelated owners. Coarse roots preserve whole-crate obligations and amortize algorithms that do not divide cheaply.

3. TyCtxt is the front door#

Most compiler code reaches a query as a method on TyCtxt<'tcx>:

let declared = tcx.type_of(def_id);
let body = tcx.optimized_mir(def_id);

TyCtxt means “type context” historically, but it is really the central handle to compiler-session state. It carries access to interners, the session, definitions, query machinery, and many compiler services. The 'tcx lifetime ties interned and arena-owned values to that context.

These query methods are generated rather than handwritten hundreds of times. The generated method converts the argument into the query's canonical key, chooses its machinery, and records the call correctly. That uniform path is what makes an innocent-looking method call participate in memoization and incremental tracking.

TyCtxtAt<'tcx> is the location-bearing sibling of TyCtxt. A caller obtains it with a diagnostic span and invokes the same generated query surface through it. The span supplies context for query descriptions, cycle reports, and other diagnostics without changing the semantic key. A source location should not fragment the cache merely because two callers ask the same semantic question at different spans.

Conceptually, the split is:

tcx.some_query(key)          semantic request with a default/current location
tcx.at(span).some_query(key) semantic request plus diagnostic location

There are also generated “ensure” paths for callers that need a query to run but do not need its value. They are important for eager checking roots: forcing validation should not require retaining a bulky result at the call site. The exact generated API is internal and should be read from the current source, not treated as a public language feature.

4. Where queries are declared now#

On current rust-lang/rust, the central declarations are in:

compiler/rustc_middle/src/queries.rs

Do not follow an old guide directly to a formerly monolithic query/mod.rs declaration list. The declarations describe each query's name, key, result, human-readable description, and modifiers. They are input to rustc's procedural-macro generation rather than runtime registration code.

The real list is the authority for exact types and currently accepted syntax. The modifiers have hoverable documentation in:

compiler/rustc_middle/src/query/modifiers.rs

That file's dummy marker items make modifier documentation and find-all-references useful in compiler development. Macro parsing and expansion live under compiler/rustc_macros, including its query macro implementation. Generated and handwritten runtime plumbing is centered in compiler/rustc_middle/src/query/, especially plumbing.rs.

Older rustc-dev-guide text may show a Salsa-like declaration syntax. That syntax is historical, and rustc still does not use Salsa. Use historical chapters for concepts, then verify names and paths against current source.

5. What generation supplies#

The declaration macro connects several layers that must agree on one query's types.

• It exposes methods on TyCtxt and TyCtxtAt.
• It defines or connects the query cache and state for key/result types.
• It builds query vtables used by generic execution plumbing.
• It associates query names with dependency kinds and key fingerprint behavior.
• It generates provider table fields with concrete function-pointer signatures.
• It wires descriptions, hashing, disk decoding, cycle policy, and optional forcing.

Generation standardizes the shell; domain crates supply the meaning.

The central runtime aggregate is QuerySystem in compiler/rustc_middle/src/query/plumbing.rs. It owns or references the structures needed to execute queries, including caches, active states, vtables, providers, and incremental hooks. This is rustc-specific machinery inside today's rustc_middle architecture. Do not describe the old standalone rustc_query_system crate as the current home of the architecture.

6. Providers are tables, not traits#

Providers and ExternProviders are generated structs whose fields are function pointers. They are not traits implemented once by every compiler phase. For a schematic query, the local slot resembles:

pub example: for<'tcx> fn(TyCtxt<'tcx>, SomeKey) -> SomeValue<'tcx>

Each compiler crate exposes a registration function that overwrites the relevant default slots. Initialization collects these registration functions before normal query execution begins. The resulting tables provide direct, statically typed calls without dynamic trait-object lookup.

Local providers compute facts for the crate currently being compiled. For example, MIR-building code registers the provider responsible for local bodies. The implementation can call tcx queries normally, so its dependencies are discovered from actual execution.

External providers answer applicable questions about dependency crates. Most such answers come through rustc_metadata, whose decoder reads the dependency's encoded crate metadata. The registration path for metadata-backed extern providers includes:

compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs

For a key that identifies a definition, local-versus-external identity selects the appropriate table when the query has separate extern provision. separate_provide_extern requests this split rather than assuming one implementation handles both worlds. Not every key has a DefId, and generated key logic determines the applicable dispatch; “check DefId.krate” is a useful example, not the universal algorithm.

Crate metadata dispatch is not incremental-cache reuse. An .rmeta file is the published semantic interface of another crate for downstream compilation. An incremental query cache is private reuse data for rebuilding a compilation session. Confusing them hides why external values normally come from metadata even when local query results may be disk-cached.

7. One in-session request#

Consider a request for optimized_mir(F) during monomorphization. The generated method identifies the query kind and canonical key. It first consults the in-memory cache for a completed value. On a hit, it returns that value and records the dependency from the current parent query.

On a miss, query state is consulted for the same key. If nobody is computing it, the request installs an active QueryJob and becomes its owner. The job records stack and dependency context needed for diagnostics, cycle handling, and parallel coordination. The provider then runs, possibly invoking mir_borrowck(F) and many smaller queries.

Each nested invocation creates an edge from the active parent node to the child node. These are dynamic edges: the graph reflects the branch and data choices that actually occurred. A static phase graph could not precisely represent “this body used that trait impl only after normalization chose this path.”

When the provider succeeds, rustc fingerprints the result when required, completes dependency-node bookkeeping, fills the cache, and wakes waiters. The active job is removed or transitioned so future requests see the completed value. If computation fails catastrophically, state must not masquerade as a valid cache entry.

The in-memory cache lasts only for this compiler session. It avoids duplicate work even when incremental compilation is disabled. This distinction explains why eval_always can still be cached in memory after its first evaluation in a session.

8. DepGraph, DepNode, and DepKind#

The dependency graph is the cross-query change-tracking model. A DepNode identifies a unit of tracked computation by a DepKind plus a fingerprint-like identity payload. The DepKind says what class of computation this is, such as a particular generated query kind or an input kind. The remaining identity says which instance of that kind is meant.

DepNode = (DepKind, stable identity fingerprint)

parent node  --read during evaluation-->  child node

Edges point from a computation to facts it read. If a child changes, its parents may need reevaluation. If a reevaluated child produces the same result fingerprint, parents can remain reusable: that is early cutoff.

The graph stores compact session-local indices for speed. An index is meaningful only in the graph that allocated it and must not be serialized as semantic identity. Across sessions, rustc uses stable identities derived under a stable hashing context. For definitions, stable def paths or their hashes stand in for allocation-order-sensitive DefId components.

This is why “hash the query key” needs qualification. The key fingerprint identifies which query instance an old node represents. The result fingerprint summarizes what value that instance produced. The former supports matching and, for forceable nodes, recovering a key; the latter supports red/green comparison. Equal key fingerprints do not mean equal results, and equal result fingerprints do not identify the same query.

Stable hashing deliberately excludes unstable accidents such as current arena addresses and session numbering. Collapsing everything to raw in-process IDs would be faster to design but useless after rustc exits. Serializing rich keys directly everywhere would consume more space and bind the cache tightly to ephemeral layouts.

9. Red, green, and try_mark_green#

At the start of an incremental session, an old graph and fingerprints are available, while current inputs establish changed leaves. A node is green when rustc proves its old result remains valid. A node is red when it must be considered changed for dependents. Unknown means the proof has not yet been attempted or completed.

try_mark_green is recursive in spirit:

try_mark_green(node):
    if current color is known:
        return it
    find the corresponding node in the previous graph
    if there is no usable previous node:
        return unknown/not-green
    for each previous dependency:
        recursively try to mark that dependency green
        if it cannot be proven green:
            try to force/recompute it when its kind permits forcing
        if the dependency is red or cannot be validated:
            stop proving this node green
    mark this node green and map old index to current index
    return green

The real implementation has synchronization, input handling, side effects, and richer return states. The crucial idea is proof by validating the old dependency set, not blindly trusting timestamps. An unchanged result may preserve dependents even when its provider had to rerun.

Forcing bridges a missing current dependency node. If the dependency's DepKind knows how to reconstruct its query key from the stable identity, rustc invokes that query now. The forced evaluation computes a current result fingerprint and colors the node by comparison with its old result. If the value differs, the node is red; if the value matches, it can be green despite the recomputation.

Not every node is forceable. Some stable fingerprints are intentionally one-way, some keys cannot be reconstructed, and some cycle policies need all relevant calls visibly on the stack. The no_force modifier prevents forcing for such a query. Its cost is less opportunity to validate a dependent through recursive forcing; its benefit is preserving correctness or cycle-reporting invariants.

Early cutoff is the reason result hashing pays for itself. Suppose an edit causes name-resolution machinery to rerun but yields the same resolved definition for a use. The resolution node's equal result fingerprint can become green, so type checking that depends only on that result need not rerun. Without early cutoff, every touched input would dirty the entire transitive reverse dependency cone.

10. Modifier design choices#

Modifiers are compiler implementation controls, not stable attributes available to ordinary Rust programs. Their exact set and spelling can change, so the current query/modifiers.rs and declarations win over summaries.

cache_on_disk permits selected return values to be encoded in the incremental query cache and loaded in a later session when green. Serialization has compile-time, compatibility, and space costs, so rustc does not persist every result. With separate external provision, external values belong in crate metadata rather than duplicating them as local incremental values.

no_hash says not to compute a meaningful incremental fingerprint for the returned value. If such a query must be recomputed, its node is treated as red rather than benefiting from equal-result cutoff. This can avoid expensive or impossible stable hashing, at the price of wider invalidation.

eval_always is appropriate when a provider observes state the dependency graph does not model, or when tracking would cost more than reevaluation. It does not mean “run on every call”: its answer can still be memoized for the rest of the current session. Across incremental validation, however, its untracked dependencies prevent the usual green proof.

no_force forbids reconstructing and evaluating the node merely to validate an old dependent. It is particularly relevant where custom cycle handling requires the natural stack of calls. Choosing it trades incremental reach for execution-order and recovery guarantees.

feedable generates a way for trusted compiler code to supply a query value from another computation. Feeding models values whose authoritative production occurs outside the ordinary provider entry. It requires strict invariants because a second inconsistent value would undermine memoization and dependency tracking.

separate_provide_extern creates distinct local and external provider slots. It expresses a semantic storage boundary: compute current-crate facts from local structures, decode dependency facts from metadata. Using one universal provider would simplify the table but spread local/external branching through implementations.

Other current modifiers cover concerns such as arena allocation, descriptions, recursion depth, and custom cycle handling. Do not infer semantics from a name alone; read its doc marker and generated expansion. In particular, these controls are not a compatibility contract for tools embedding stable rustc APIs.

11. Three kinds of persisted artifact#

The disk query cache stores serialized results of specifically cacheable local queries for incremental rebuilding. Its consumer is another rustc session proving nodes green under compatible compiler and option conditions. Deleting it costs time, not source-level meaning.

An .rmeta artifact stores crate metadata for downstream crates. It carries exported semantic information such as item identities, signatures, predicates, and other encoded facts needed to compile dependents. It is part of the crate-compilation boundary, not merely a replay of one process's memo table.

Codegen work products are backend-oriented outputs associated with codegen units. Incremental compilation can reuse object-like products when their controlling nodes remain valid. They are not decoded as arbitrary typed query return values and are not the semantic interface represented by .rmeta.

incremental query cache -> selected typed compiler answers
.rmeta                  -> semantic facts offered to downstream crates
codegen work products   -> reusable backend outputs for codegen units

Keeping these stores distinct allows each to choose suitable granularity and encoding. A single universal cache would couple downstream compatibility, frontend values, and backend artifacts unnecessarily.

12. Diagnostics and other side effects#

A provider can emit diagnostics while producing its semantic result. Loading only the value from disk would otherwise make a warning or error disappear on the second build. rustc therefore tracks replayable side effects associated with dependency nodes and re-emits them when a green node is reused.

The dependency graph must also account for diagnostic conditions that change. If an edit removes the cause, validation should not replay a stale message. If the cause remains and computation is skipped, replay preserves user-visible behavior. This makes incremental correctness broader than “the generated machine code matches.”

The best provider is observationally query-like: same tracked inputs, same value and replayable effects.

13. Cycles, placeholders, and poisoning#

A cycle occurs when an active query eventually requests the same active query instance again. Some cycles indicate an invalid Rust program, while others expose a compiler architecture error or a domain that has an intentional fixed-point-like recovery. The default cannot simply recurse until the stack overflows.

Cycle diagnostics use the active query stack, descriptions, and TyCtxtAt spans to explain the chain. Many cycles emit an error and return a typed error placeholder or recovery value so additional useful diagnostics can be produced. Queries with specialized semantics can use a custom cycle handler; this is internal policy, not permission to return arbitrary fabricated values.

An error placeholder must be contagious enough to prevent unsound code generation. Compiler types often carry ErrorGuaranteed or an error-marked semantic value that records that a diagnostic already exists. Recovery aims to continue analysis without pretending the program was valid.

Poisoning addresses failed computation and panics. An active cache slot cannot be left looking complete if its provider unwinds or aborts its normal path. Waiters must be awakened or compilation must terminate, and later code must not consume partially initialized state. This is the query analogue of poisoning a lock after an invariant may have been broken.

14. Parallel requests and deadlock cycles#

When two threads request the same key, one owns the active QueryJob and the other waits on its latch. The latch avoids duplicate expensive provider execution and publishes completion to all waiters. Independent query jobs can proceed in parallel when compiler configuration and data structures permit it.

Thread-local stack cycle detection is insufficient in parallel execution. Thread A may own query X and wait for Y, while thread B owns Y and waits for X. Neither stack alone contains a direct recursive call, but the wait-for graph contains a cycle.

rustc's job and waiter bookkeeping supports detection of these cross-thread deadlock cycles. Once detected, cycle recovery or fatal handling must break the wait rather than allowing both latches to sleep forever. The same mechanism needs careful ownership transfer and wake-up rules under cancellation or failure.

Parallelism raises the implementation price of transparent memoization. Cache lookup, active-state installation, dependency recording, and completion must appear atomic enough to preserve one logical result. A simpler single-thread engine avoids these races but leaves independent item work unable to overlap.

15. A full edit trace#

Assume a crate contains a generic helper and two unrelated functions:

fn id<T>(x: T) -> T { x }
fn answer() -> u32 { id(41) + 1 }
fn unrelated() -> &'static str { "steady" }

The first build parses and expands the crate, lowers owners, checks each required body, builds MIR, runs borrow checking, and records dependencies. Codegen collection discovers id::<u32> from answer, requests its optimized MIR, and creates work products. Selected query values, graph fingerprints, side effects, and codegen products are persisted in their distinct stores.

Now edit 41 to 42 without changing any signature. The source input fingerprint changes, so every dependent is initially suspect rather than automatically recomputed. Parsing and some coarse expansion/resolution roots may run because their current boundaries encompass the changed file or crate.

Per-owner stable identity lets the old unrelated owner correspond to the new one even if session-local indices differ. Its HIR-related result fingerprints and dependencies can be proven unchanged. Queries below that owner become green and their diagnostics, if any, can be replayed without body analysis.

The answer owner has changed body content, so body-dependent nodes cannot all be marked green. Its declared type_of may nevertheless retain the same result fingerprint, because -> u32 did not change. Dependents that read only the signature can stop invalidation there.

Type checking for answer may rerun and again infer that id is instantiated with u32. If the type-check result's stable fingerprint is unchanged, downstream consumers of only that semantic result can remain green. MIR containing the literal changes, so built and optimized MIR for answer become red.

Borrow checking may be forced as part of validating a later node or eagerly requested by the analysis driver. It can produce the same “accepted, no diagnostics” semantic outcome, permitting cutoff where its hashed result and graph policy support it. No stale borrow error is replayed because the side-effect set is tied to the validated node.

Monomorphization still discovers id::<u32>. The generic helper's own optimized MIR is unchanged and can remain green. The codegen unit containing answer is invalidated because its generated constant changes; a separate unit containing only unaffected code may reuse its work product.

Finally, linking or final artifact assembly runs as required by the requested output. The exact partition and reused units depend on compiler options, inlining, optimization, and codegen-unit layout. This trace illustrates boundaries; it does not promise one query or one object file per source function.

If the edit instead changed id<T> to return a different type, type_of(id) would be red. Its reverse dependency cone could include call-site type checking, trait obligations, mono-item selection, and metadata. Stable result hashing still cuts off branches that recompute to equal answers; it cannot erase a genuinely changed interface.

16. Generic query engine versus rustc#

A generic engine often prioritizes a reusable API and simple revision semantics. rustc prioritizes batch throughput, precise stable invalidation, compact compiler types, and compatibility with its existing phase architecture. The specialization buys performance and diagnostic control but makes the system harder to extract or explain as one clean abstraction.

Salsa offers its own revisions, ingredients, inputs, accumulators, and cycle facilities. Those are valuable comparison points, not names for rustc internals unless current rustc source uses them independently. Saying “rustc is like Salsa” is acceptable only at the broad level of demand-driven memoized dependency tracking.

17. Limits and coarse boundaries#

Queries do not make every compiler operation pure. Macro expansion and name resolution have global ordering and mutation concerns; whole-crate analyses sometimes genuinely need whole-crate views. LLVM and linking have their own stateful pipelines and caching economics.

Granularity is a trade-off rather than a race toward the smallest key. Tiny queries increase hash traffic, graph edges, allocations, synchronization, and declaration complexity. Huge queries invalidate too much and suppress parallelism. Per-owner HIR and body-oriented semantic results are practical compromises, not a proof that the optimum has been reached.

Demand-driven execution can also duplicate orchestration if no root guarantees coverage. rustc explicitly walks bodies for checks whose diagnostics are required even when those bodies are unreachable from codegen. Dead-code elimination is not permission to skip rejecting ill-typed or borrow-invalid Rust items.

Incremental compilation is conservative. When rustc cannot establish stable identity, hash a value, reconstruct a forceable key, or trust an input, it recomputes and propagates red. Doing extra work is preferable to reusing a stale answer.

Compiler version, target, options, environment inputs, and unstable implementation formats can invalidate caches broadly. The incremental directory is an optimization artifact, not a durable database format. A clean build remains the semantic baseline.

18. Reading the live implementation#

Start with the official query overview:

• https://rustc-dev-guide.rust-lang.org/query.html
• https://rustc-dev-guide.rust-lang.org/queries/incremental-compilation-in-detail.html
• https://rustc-dev-guide.rust-lang.org/queries/query-evaluation-model-in-detail.html

Then inspect current source on the default branch rather than trusting an old line number:

• https://github.com/rust-lang/rust/blob/HEAD/compiler/rustc_middle/src/queries.rs — query declarations.
• https://github.com/rust-lang/rust/blob/HEAD/compiler/rustc_middle/src/query/modifiers.rs — current modifier documentation.
• https://github.com/rust-lang/rust/blob/HEAD/compiler/rustc_middle/src/query/plumbing.rs — QuerySystem, generated plumbing support, providers, and execution paths.
• https://github.com/rust-lang/rust/blob/HEAD/compiler/rustc_middle/src/query/job.rs — active jobs, latches, and waiters.
• https://github.com/rust-lang/rust/tree/HEAD/compiler/rustc_middle/src/dep_graph — dependency nodes, graph operations, and incremental state.
• https://github.com/rust-lang/rust/tree/HEAD/compiler/rustc_macros/src — procedural macro generation for declarations.
• https://github.com/rust-lang/rust/blob/HEAD/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs — external metadata providers.
• https://github.com/rust-lang/rust/blob/HEAD/compiler/rustc_interface/src/passes.rs — provider assembly and eager compilation orchestration.

Search queries.rs for a concrete query such as type_of, mir_built, or optimized_mir. Read its key, result, and modifiers before locating its provider registration. Then follow the provider's nested tcx calls to see dynamic dependency edges at their source.

Next, search for that query's assignment in provide functions. Check whether it has separate extern provision and whether rustc_metadata encodes the corresponding information. This prevents mistaking a local implementation for cross-crate behavior.

Finally, read try_mark_green together with forcing and result loading. Reading only the cache lookup makes incremental compilation look like memoization across processes. Reading only the dependency graph misses how a typed value is recovered after the proof succeeds.

Documentation can lag a fast-moving compiler. When a guide presents old paths or Salsa-flavored syntax, preserve the concept but follow current source. Exact internals described here are a 2026 snapshot, not a stability guarantee.

Part IV: Using Modern Salsa in a Compiler#

1. Version, scope, and provenance#

This part turns the query model from the first three parts into a small, working compiler architecture. The library is Salsa, pinned here to 0.28.1. The API and links in this chapter were verified on 2026-08-03. Salsa describes itself as experimental, and its public API is still evolving. Pin the version, read release notes before upgrading, and expect migrations. Authoritative references for this chapter are:

• the 0.28.1 crate documentation;
• the Salsa book;
• the 0.28.1 crate page;
• and the upstream repository.

The examples deliberately use the current public macros rather than old tutorials. query_group is obsolete history, not an API to copy. #[salsa::database(...)] is likewise from an older generation. Tutorials that ask users to declare a public #[salsa::jar] are also historical. Modern user code declares Salsa structs, tracked free functions, and a #[salsa::db] database. Salsa grew from incremental-compilation techniques developed around Rust. That does not mean rustc embeds this public crate as its query engine. rustc has a separate, compiler-internal query system with different APIs and constraints. Treat rustc as related design experience, not as documentation for Salsa 0.28.1.

We will build TinyLox, a deliberately small compiler for functions and integer expressions. Its pipeline is source text → parsed syntax → lowered functions → type checking. The same database also serves diagnostics and an IDE-style edit loop.

2. The dependency and the database#

Start a normal Rust package and pin the exact release.

[package]
name = "tinylox"
version = "0.1.0"
edition = "2024"

[dependencies]
salsa = "=0.28.1"

The exact pin matters in instructional code because a broad requirement can silently select a new API. Our database trait is the view accepted by every compiler query.

#[salsa::db]
pub trait Db: salsa::Database {}

#[salsa::db]
#[derive(Clone, Default)]
pub struct CompilerDatabase {
    storage: salsa::Storage<Self>,
}

#[salsa::db]
impl salsa::Database for CompilerDatabase {}

#[salsa::db]
impl Db for CompilerDatabase {}

salsa::Storage<Self> owns Salsa's database state. Clone creates another database handle suitable for independent work with shared underlying state. Default gives tests and command-line entry points a convenient empty database. The #[salsa::db] annotations generate the plumbing connecting the trait and concrete type. Additional ordinary fields may hold configuration or services, but reads of those fields are not automatically tracked.

Do not put mutable compiler inputs in an untracked HashMap and expect invalidation. Salsa observes only operations represented through its ingredients and query calls. Filesystem reads, environment variables, time, random numbers, network state, and hidden global mutation are invisible. Read such state at the application boundary and copy it into Salsa inputs.

3. Source files are inputs#

An input is mutable state supplied by the world outside the query graph. Each call to SourceFile::new creates a distinct identity, even when both fields are equal.

use std::path::PathBuf;

#[salsa::input]
pub struct SourceFile {
    path: PathBuf,
    text: String,
}

Field getters return references by default. Thus file.path(db) is &PathBuf, and file.text(db) is &String. The borrowed values remain tied to the immutable borrow of db.

use salsa::Setter;

fn load_example() -> (CompilerDatabase, SourceFile) {
    let db = CompilerDatabase::default();
    let file = SourceFile::new(
        &db,
        PathBuf::from("example.lox"),
        "fun answer() { 40 + 2 }".to_owned(),
    );
    (db, file)
}

fn apply_edit(db: &mut CompilerDatabase, file: SourceFile, new_text: String) {
    file.set_text(db).to(new_text);
}

Importing salsa::Setter makes .to(...) available. The setter takes a mutable database because changing an input begins a new revision. The canonical spelling is file.set_text(&mut db).to(text) when db is a local value. A setter always records a change, even if the new value compares equal to the old value. Avoid sending redundant editor updates when that cost matters.

Input dependencies are field-sensitive. A query that reads only text is unaffected by a path update. A diagnostic formatter that reads path will depend on it.

An input handle such as SourceFile has no 'db lifetime parameter. It is a compact Copy identity and can be retained across revisions. It must still be used only with the database that created it. Dropping all copies does not remove its data; input storage lasts until the database is dropped.

The database lifetime is also an enforcement mechanism. This fails for a good reason:

let old_text = file.text(&db);
file.set_text(&mut db).to("new text".to_owned());
println!("{old_text}");

old_text borrows the database immutably while the setter needs a mutable borrow. The type system prevents a reference into one revision from being observed after a mutation.

4. Plain syntax values and diagnostics#

Small immutable products can be ordinary Rust values. They need equality because a tracked query normally compares an old result with a recomputed result.

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ParsedProgram {
    pub functions: Vec<ParsedFunction>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ParsedFunction {
    pub name: String,
    pub body: String,
    pub offset: usize,
}

#[salsa::accumulator]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Diagnostic {
    pub offset: usize,
    pub message: String,
}

An accumulator is an auxiliary output channel. Diagnostics do not have to contaminate every main return type. They are retained with the query execution that emitted them.

Here is a minimal parser for our restricted fun name() { expression } form. It is intentionally simple enough that the incremental architecture remains visible.

use salsa::Accumulator;

#[salsa::tracked]
pub fn parse(db: &dyn Db, file: SourceFile) -> ParsedProgram {
    let text = file.text(db);
    let mut functions = Vec::new();
    for (line_start, line) in line_offsets(text) {
        let line = line.trim();
        if line.is_empty() { continue; }
        let Some(after_fun) = line.strip_prefix("fun ") else {
            emit(db, line_start, "expected `fun`");
            continue;
        };
        let Some((name, after_name)) = after_fun.split_once("()") else {
            emit(db, line_start, "expected `name()`");
            continue;
        };
        let Some(body) = after_name.trim().strip_prefix('{') else {
            emit(db, line_start, "expected `{`");
            continue;
        };
        let Some(body) = body.strip_suffix('}') else {
            emit(db, line_start, "expected `}`");
            continue;
        };
        functions.push(ParsedFunction {
            name: name.trim().to_owned(),
            body: body.trim().to_owned(),
            offset: line_start,
        });
    }
    ParsedProgram { functions }
}

fn emit(db: &dyn Db, offset: usize, message: &str) {
    Diagnostic { offset, message: message.to_owned() }.accumulate(db);
}

fn line_offsets(text: &str) -> impl Iterator<Item = (usize, &str)> {
    let mut offset = 0;
    text.lines().map(move |line| {
        let result = (offset, line);
        offset += line.len() + 1;
        result
    })
}

The body may perform ordinary Rust work. Only Salsa reads and tracked calls become dependency edges. Invalid syntax is data, not a reason to abort the whole database. The parser emits a diagnostic and recovers at the next line.

parse is a modern tracked free function. Its key is the pair “function parse, argument file.” Calls with the same key share one memoized result. Its database parameter is not part of the key.

Retrieve all diagnostics from parse and anything it called transitively like this:

let diagnostics: Vec<&Diagnostic> = parse::accumulated::<Diagnostic>(&db, file);

The generated parse::accumulated first brings parse(file) up to date. The returned references borrow the database. Accumulating outside a tracked function panics. Accumulator values are not part of the main result's equality.

5. Return modes are an ownership decision#

Tracked-function results, like Salsa struct fields, are borrowed by default. Although the source declaration says -> ParsedProgram, calling parse(db, file) yields a database-tied reference. That default avoids cloning a potentially large syntax tree.

Use the generated result immediately or clone only at an ownership boundary:

let count = parse(&db, file).functions.len();
let owned_snapshot = parse(&db, file).clone();

The public return modes are ref, copy, clone, deref, as_ref, and as_deref. ref is the default and returns &T from stored T. copy returns T by copying a Copy stored value. clone returns T by cloning a Clone stored value. deref returns a reference to <T as Deref>::Target. as_ref uses Salsa's SalsaAsRef conversion. as_deref uses Salsa's SalsaAsDeref conversion.

The attribute sits on an input or struct field:

#[salsa::input]
pub struct BuildOptions {
    #[returns(copy)]
    optimize: bool,
    #[returns(deref)]
    target: String,
    #[returns(as_deref)]
    sysroot: Option<String>,
}

It is an option on a tracked function:

#[salsa::tracked(returns(copy))]
pub fn function_count(db: &dyn Db, file: SourceFile) -> usize {
    parse(db, file).functions.len()
}

Do not use the modes by guesswork. For String, default ref produces &String, while deref follows Deref and produces &str. For Option<String>, as_ref produces Option<&String> and as_deref produces Option<&str>. Those optional modes use Salsa's SalsaAsRef and SalsaAsDeref conversion traits. Consult the return-mode reference for the supported type shapes.

Owned copy and clone results can survive the database borrow when their own types allow it. Borrowed modes cannot cross the mutable borrow that starts another revision. Choose modes for API ergonomics and cost, not to silence lifetime errors blindly.

6. Interned names and tracked functions#

Names recur throughout a compiler. Interning makes equal spelling share one database-wide identity and makes equality a cheap handle comparison.

#[salsa::interned]
pub struct Name<'db> {
    #[returns(deref)]
    text: String,
}

By default, modern interned handles carry 'db. The lifetime says their database-backed identity may not cross a revision. Interning the same field values in a revision returns the same handle. Interned fields are immutable; changing spelling means interning another Name.

Lowering creates tracked entities owned by a tracked query invocation. Fields are identity fields by default. Mark changing payload fields individually with #[tracked].

#[salsa::tracked]
pub struct Function<'db> {
    pub name: Name<'db>,
    pub ordinal: u32,
    #[tracked]
    #[returns(deref)]
    pub body: String,
    #[tracked]
    #[returns(copy)]
    pub offset: usize,
}

#[salsa::tracked]
pub struct Module<'db> {
    pub file: SourceFile,
    #[tracked]
    #[returns(clone)]
    pub functions: Vec<Function<'db>>,
}

name and ordinal define a Function's identity within its producer. body and offset are values that may change while that identity survives. file is the identity field of Module; its function vector is a tracked value field. Field-level #[tracked] means “exclude from identity and track reads,” not “memoize this field.”

The producer, identity fields, and occurrence disambiguate tracked structs. If one invocation constructs two values with identical identity fields, occurrence order distinguishes them. Changing construction order can therefore destabilize IDs. Use explicit stable identity data such as a source key or ordinal, and emit in deterministic order.

#[salsa::tracked]
pub fn lower<'db>(db: &'db dyn Db, file: SourceFile) -> Module<'db> {
    let functions = parse(db, file)
        .functions
        .iter()
        .enumerate()
        .map(|(ordinal, parsed)| {
            let name = Name::new(db, parsed.name.clone());
            Function::new(
                db,
                name,
                ordinal as u32,
                parsed.body.clone(),
                parsed.offset,
            )
        })
        .collect();

    Module::new(db, file, functions)
}

The explicit 'db connects the database borrow to tracked and interned handles. Tracked handles carry 'db by default and must be reacquired after an edit. The producer owns its tracked outputs. When it re-executes, matching identities preserve IDs and changed tracked fields invalidate only their readers. An old output not recreated becomes stale and may be reclaimed.

Output ownership is why returning tracked handles is different from returning arbitrary arena references. Salsa knows which query produced each entity and can validate, replace, or remove that output coherently.

SalsaValue is not a routine derive for every AST node. Plain 'static values such as String, usize, and vectors of suitable handles need no custom implementation. Derive salsa::SalsaValue only for a custom stored type that itself carries 'db and must be lifetime-erased safely for retention. Never write the unsafe trait implementation casually; follow its safety documentation.

7. Type checking and fine-grained keys#

A function-level query lets one body change without making every sibling's type check execute again.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Type {
    Int,
    Error,
}

#[salsa::tracked(returns(copy))]
pub fn type_of_function<'db>(db: &'db dyn Db, function: Function<'db>) -> Type {
    let body = function.body(db);
    if body
        .split('+')
        .map(str::trim)
        .all(|term| term.parse::<i64>().is_ok())
    {
        Type::Int
    } else {
        Diagnostic {
            offset: function.offset(db),
            message: format!("`{body}` is not an integer expression"),
        }
        .accumulate(db);
        Type::Error
    }
}

#[salsa::tracked]
pub fn check_file<'db>(db: &'db dyn Db, file: SourceFile) -> Vec<Type> {
    let module = lower(db, file);
    module
        .functions(db)
        .iter()
        .map(|function| type_of_function(db, *function))
        .collect()
}

type_of_function reads body and offset, so those accesses become dependencies. It does not read the function's name, so renaming alone need not rerun this query if identity remains stable. In this tiny design name is an identity field, however, so renaming creates a different tracked entity. That trade-off is a schema decision, not magic Salsa can infer.

A tracked function's non-database arguments form its key. With no non-database arguments, there is one key per database. With one Salsa struct argument, Salsa can use that struct's ID directly. With multiple arguments, Salsa interns the argument tuple into a synthetic ID. Those argument types therefore need appropriate equality and hashing.

#[salsa::tracked(returns(copy))]
pub fn is_assignable<'db>(
    _db: &'db dyn Db,
    function: Function<'db>,
    expected: Type,
) -> bool {
    let _key_component = function;
    expected == Type::Int
}

The arguments select the memo; they are not automatically dependency reads. This is the hidden tracking boundary that surprises newcomers. Passing SourceFile as a key does not mean “depend on every field of that file.” Dependencies arise when the body calls file.text(db), file.path(db), or another tracked query. Conversely, reading data behind an ordinary pointer or global cannot create an edge.

8. Equality, backdating, and no_eq#

When dependencies change, Salsa may re-execute a query. Normally it compares the new result with the old result using PartialEq. If equal, it backdates the memo's change revision, stopping needless propagation. This is why semantic result equality matters more than allocation identity.

Do not include timestamps, random IDs, or unstable map iteration in a result's equality. Normalize unordered data or use deterministic collections where output order is not semantic. Cheap equality often saves much more downstream work than it costs.

#[salsa::tracked(no_eq)] disables result comparison for a query. Use it only when equality is impossible, incorrect, or disproportionately expensive. Without equality Salsa cannot prove an unchanged recomputed result, so invalidation propagates farther. no_eq is a performance and semantics choice, not a blanket fix for a missing derive.

Inputs differ: their setters always record a change. There is no input-side “equal value means no revision” optimization. Deduplicate writes in the host if necessary.

9. The IDE revision loop#

An editor retains input handles, mutates one, then asks only for demanded outputs.

fn ide_demo() {
    let (mut db, file) = load_example();
    show_revision(&db, file);
    file.set_text(&mut db).to(
        "fun answer() { 40 + nope }\nfun two() { 1 + 1 }".to_owned(),
    );
    show_revision(&db, file);
}

fn show_revision(db: &CompilerDatabase, file: SourceFile) {
    let types = check_file(db, file);
    let diagnostics = check_file::accumulated::<Diagnostic>(db, file);
    println!("types: {types:?}");
    for d in diagnostics { println!("{}: {}", d.offset, d.message); }
}

Every database mutation ends outstanding immutable borrows. After the edit, call lower again to obtain fresh 'db-bound tracked handles. Never cache a Function<'db> in long-lived editor state. Cache durable input handles and ordinary owned identifiers instead.

The first request computes the demanded graph. The second request validates old memos and executes only what changed semantically. Salsa is on-demand: an edit alone does not eagerly compile every file.

10. Advanced controls, used deliberately#

Durability#

Durability classifies how likely an input field is to change. Higher-durability dependencies can sometimes skip validation after a revision containing only lower-durability changes. Source text is usually low durability; a target specification or standard library may be higher. Wrong durability can compromise invalidation, so begin with defaults and use the pinned durability reference only after profiling.

LRU memo eviction#

By default, a tracked function retains one current result for each retained key. An lru option evicts least-recently-used values at revision start while retaining memo metadata; later demand recomputes them. This trades memory for CPU, so measure and consult cache tuning.

Specified results#

specify supports a query that normally computes one tracked entity's property on demand but can also receive batch-produced answers. A specifiable function has exactly one non-database argument, and that key must be a tracked struct. Its creating tracked query may call FUNCTION::specify(db, key, value) for a key created in that invocation; the memo becomes an owned output. It cannot currently be combined with lru. TinyLox does not need it, but a batch resolver might; follow the 0.28.1 contract.

Cancellation#

Interactive systems should abandon work made obsolete by a newer edit. Salsa cancellation points let running queries observe cancellation; it is control flow, not a diagnostic or cached result. Catch it at a task boundary, discard partial presentation state, and retry against the new revision. See Cancelled and CancellationToken for the pinned API.

Cycles and recovery#

A dependency cycle means a query recursively demands itself through the active graph. Model away or report accidental cycles; configured recovery is for algorithms with deterministic cyclic semantics and convergence. Follow pinned Cycle documentation rather than old syntax; fixpoint processing also restricts accumulators. Get the basic model correct before tuning any of these controls.

11. Debugging the graph#

Salsa's database event hook reveals query execution, memo validation, and cycle activity. Use Event and EventKind rather than parsing debug strings. A custom database may record selected events for tests or tracing, but the hook must remain observational and not re-enter arbitrary queries. For excess execution, check redundant setters, actual field reads, identity order, unstable equality or no_eq, LRU, and external state. For missing execution, find the missing tracked read: a handle key does not read its fields, and a tracked wrapper does not make Salsa watch files.

12. Testing TinyLox#

Test semantic answers first, then focused incrementality properties.

#[test]
fn invalid_body_reports_a_diagnostic() {
    let db = CompilerDatabase::default();
    let file = SourceFile::new(
        &db,
        PathBuf::from("bad.lox"),
        "fun bad() { 1 + false }".to_owned(),
    );

    assert_eq!(check_file(&db, file).as_slice(), &[Type::Error]);
    let diagnostics = check_file::accumulated::<Diagnostic>(&db, file);
    assert_eq!(diagnostics.len(), 1);
    assert!(diagnostics[0].message.contains("integer expression"));
}

Keep the borrow scopes short in tests, just as production edit loops must. Test setter-driven revisions, invalid-syntax recovery, root accumulated diagnostics, and stable unaffected identities. With an event-recording database, assert meaningful boundaries such as an unchanged sibling not executing, not every internal event. Run tests under the exact pinned dependency and include cargo check in CI.

13. Cost model and architectural limits#

Salsa is strongest when work is expensive, demand is sparse, and dependencies are precise. Compilers, language servers, configuration analyzers, and build-like tools fit well. It is less useful for cheap one-shot transforms with no repeated revisions. Each key, memo, and dependency consumes resources; tiny queries can cost more to track than recompute, while coarse queries retain large values and invalidate too much. Choose boundaries around semantic reuse: file parsing, item lowering, function typing, and cross-file resolution. Interning costs hashing, coordination, and storage, so use it when canonical identity materially simplifies comparison or sharing. Do not intern every token merely because the macro exists. Tracked structs demand deterministic production; ordinary immutable Rust values are often better for local trees consumed together. Accumulators are ideal for auxiliary observations, not hidden inputs or required return values. Salsa cannot infer arbitrary-memory dependencies, purify functions, stabilize lowering, define semantic equality, or replace cancellation, profiling, and recovery design.

14. Migrating old Salsa code#

The presence of query_group, #[salsa::database(...)], or a user-visible #[salsa::jar] marks old code. Do not mechanically mix those declarations with 0.28.1 macros. A practical migration sequence is:

1. Pin salsa = "=0.28.1" and read the release documentation.
2. Replace old database declarations with #[salsa::db] traits and implementations.
3. Model externally mutable roots as #[salsa::input] structs.
4. Convert derived queries to #[salsa::tracked] free functions.
5. Choose ordinary, tracked, or interned result data by identity semantics.
6. Audit every getter and query call for its modern return mode.
7. Replace old diagnostics patterns with an accumulator where appropriate.
8. Rewrite setters using salsa::Setter and .set_field(&mut db).to(value).
9. Add edit-loop tests before applying durability, LRU, specify, or cycle features.

Lifetime errors often expose a real revision bug: retain inputs or owned keys, not default tracked/interned handles, and never erase 'db unsafely. For confusing macro errors, reduce to one input, one tracked function, and the database skeleton, then restore options incrementally.

15. Exercises#

Exercise 1: A path-sensitive diagnostic#

Add tracked display_diagnostics, reading the borrowed path and parser diagnostics; explain why a path edit invalidates it but not parse.

Exercise 2: A copied option#

Add input BuildOptions with copied optimize; key a query by it and Function, then identify its tuple key and actual field dependency.

Exercise 3: Stable lowering identity#

Edit whitespace, then prepend a function; predict identity/value changes and explain ordinal identity's weakness.

Exercise 4: Interning#

Intern Name::new(db, "answer".to_owned()) twice, compare handles and borrowed text, then explain why neither crosses set_text.

Exercise 5: Accumulated errors#

Collect root diagnostics for a malformed declaration and bad expression; explain transitivity and independence from Vec<Type> equality.

Exercise 6: Return ownership#

Remove then restore function_count's copy mode; compare the borrow with explicitly cloning ParsedProgram.

Exercise 7: Hidden dependencies#

Use events on a constant query keyed by SourceFile, then add let _ = file.text(db); and explain the changed dependency.

Exercise 8: Equality#

After a whitespace edit, show a sorted-name result backdating and explain what adding no_eq loses.

Exercise 9: Revision-safe editor state#

Store CompilerDatabase and SourceFile, not Function<'db>, and reacquire Module<'db> in each short read.

Exercise 10: Choose an advanced feature#

Choose and justify durability, LRU, specify, cancellation, cycle recovery, or none for target data, cold completions, batch bindings, stale requests, and import recursion.

16. Review answers#

1. display_diagnostics reads accumulated parser errors and file.path(db); only presentation owns the path edge, and its borrow ends before mutation.
2. Mark optimize #[returns(copy)]; the arguments form a synthetic tuple key, while options.optimize(db) records the field edge and returns an owned bool.
3. Producer, name, ordinal, and occurrence form identity; whitespace may update tracked body, but prepending shifts weak ordinal identities.
4. Equal fields yield equal Names and name.text(db) is &str; reacquire default 'db handles after a setter.
5. check_file::accumulated::<Diagnostic> gathers parser and type errors transitively, independently of main Vec<Type> equality.
6. Default mode yields a database-borrowing &usize; copy yields usize, while cloning ParsedProgram owns but copies a tree.
7. A handle argument selects a key without a field edge; file.text(db) adds that edge, and events separate validation from execution.
8. Equal sorted names are backdated and keep dependents green; no_eq saves comparison but loses that propagation barrier.
9. Long-lived state owns the database and SourceFile, then calls lower(&db, file) for fresh short-lived Function<'db> handles.
10. Choose durability for target data, measured LRU for cold memos, contract-valid specify for batch bindings, cancellation for stale work, and redesign accidental cycles.

17. Closing model#

The TinyLox database is a versioned semantic graph, not a bag of cached functions. Inputs name mutable facts. Tracked functions define demand-driven transformations and dependency boundaries. Tracked structs give producer-owned derived entities stable identity when lowering is deterministic. Interned structs canonicalize immutable values such as names. Accumulators carry diagnostics beside, rather than inside, semantic results.

Keys answer “which computation?” Tracked reads answer “what did it depend on?” Equality answers “did its observable result really change?” Return modes answer “who owns this value, and for how long?” The 'db lifetime prevents values backed by one revision from leaking into the next.

Begin with correct dependencies and stable identity. Observe execution with events and tests. Only then tune durability, memo retention, batch specification, cancellation, or cycles. That sequence keeps Salsa an explicit compiler architecture rather than mysterious cache machinery.

Part V: Salsa Internals and Building Your Own Engine#

Parts I–IV developed the red–green model from observable behavior. This part opens the machine, then builds a deliberately smaller one. The first half maps Salsa 0.28.1-era source concepts. The second half derives a safe learning engine in Rust. Every concrete Salsa name below is non-semver-stable implementation detail unless explicitly called public API. Source layouts and private types may change between patch releases. The durable lesson is the invariant, not the spelling.

1. Two contracts: behavior and mechanism#

Salsa's public promise is incremental, demand-driven computation that behaves like a clean rebuild. Inputs may be changed through the supported mutation interface. Tracked computations observe dependencies dynamically. Unchanged results can stop change propagation. Interned values have structural identity. Tracked values have identity tied to the computation that creates them. Accumulated values are retrieved as side outputs of a query. Cancellation and cycles have documented public effects where APIs expose them. The following are current implementation choices, not public promises:

• the names Zalsa, ZalsaLocal, Ingredient, and JarImpl;
• how memo records are paged, locked, or atomically claimed;
• edge vector order and deduplication strategy;
• the waiter and wait-for-graph representation;
• the exact integer packing of IDs and generations;
• when values are evicted or reclaimed;
• whether validation recursively calls a particular private method.

A compatible engine may use a different graph, lock strategy, or ID encoding. It must still return results observationally equivalent to a clean execution.

2. The current object graph#

A user database embeds Storage<Db>. That public-looking concrete storage is the entry into two execution domains. The names in this diagram are non-semver-stable implementation names.

user Database implementation
    |
    +-- Storage<Db>
         |
         +-- StorageHandle ----------------------+
         |    shared ownership / cloning         |
         |                                       v
         |                                  shared Zalsa
         |                                  ingredients
         |                                  revisions
         |                                  tables
         |                                  synchronization
         |
         +-- local state ----------------------> ZalsaLocal
                                                  Runtime
                                                  active QueryStack
                                                  per-thread execution data

StorageHandle makes shared database state independently referenceable. The shared Zalsa owns data that must agree across database handles and workers. ZalsaLocal owns state associated with one local execution context. Runtime coordinates a local participant with global revisions and cancellation. Do not infer that these exact ownership boundaries are API guarantees. Shared data naturally includes ingredient registration and memoized records. Shared data also includes synchronization needed to claim a query key. Local data naturally includes the active stack and transient dependency capture. Keeping active execution local avoids putting every stack push behind a global lock. Sharing memo state allows different workers to reuse the same completed result. The separation answers two different questions:

1. What is true for the database as a whole?
2. What is this worker currently computing?

Conflating them is a common clone-design mistake. A single mutex around both is correct for milestone one, but scales poorly.

3. Ingredients, generated registration, and addresses#

Current macros generate internal registration machinery. The generated implementation contributes Ingredient implementations through a JarImpl-style registration path. Both names are non-semver-stable implementation details. This is not the obsolete public jar API described by old Salsa tutorials. Users declare inputs, tracked functions, tracked structs, interned structs, and accumulators. Generated code turns those declarations into runtime ingredients. An IngredientIndex identifies an ingredient within one database. An Id identifies a row within that ingredient's storage. Together they form a complete database key. Current source equates that pair with DatabaseKeyIndex conceptually:

DatabaseKeyIndex
  = IngredientIndex × Id
  = which table/operation × which row/key

IngredientIndex alone cannot identify parse(file_a). Id alone cannot say whether row 7 is a file, symbol, or function memo. The pair can be used in erased dependency edges. Typed facades convert typed keys to this erased address at the boundary. IDs are not merely forever-growing vector offsets in every table. Current designs use paged storage and generational ID concepts. Paging permits stable chunks and avoids relocating all records on growth. A generation distinguishes a reused slot from its former occupant.

packed/logical Id
    page     slot     generation
      |        |          |
      +--------+----------+
               |
        lookup validates generation

Generation checks prevent an old handle from silently naming a new value. The exact bit widths and table policy are non-semver-stable. The semantic requirement is stale-handle detection or prevention.

4. Memo tables and function memos#

Each memoized function ingredient maps argument identity to a memo record. The current function Memo is a non-semver-stable implementation type. Conceptually a memo contains more than a cached value:

Memo
  value: optional V
  verified_at: Revision
  changed_at: Revision
  durability: Durability
  inputs: QueryEdges
  outputs: QueryEdges
  accumulated: side-output references/data
  execution metadata: synchronization, origin, or bookkeeping

Fields may be split across structures in real source. The essential distinction is value versus metadata. Evicting the value does not necessarily erase dependency history. That distinction enables LRU value eviction while metadata remains. verified_at says the memo was proven valid in a revision. changed_at says when its observable result last changed. Those timestamps answer different questions. Backdating changes changed_at, not the fact that execution just occurred. Memo tables must support these states:

• absent: no execution has established a memo;
• ready with value: reusable result and metadata;
• ready without value: metadata survived LRU eviction;
• claimed: one worker is validating or executing;
• poisoned or unwound: a failed computation released ownership safely.

5. Active execution and edge capture#

QueryStack and ActiveQuery are non-semver-stable implementation names. The stack represents nested dynamic execution. Each active frame captures dependencies read and outputs produced.

QueryStack
  ActiveQuery compile(crate)
    input edge -> options(crate)
    input edge -> parse(file 1)
    output edge -> diagnostic 9
    output edge -> tracked item 31
      ActiveQuery parse(file 1)
        input edge -> file_text(file 1)
        output edge -> syntax node 44

An input QueryEdge points from the active query to something it observed. An output QueryEdge points to something the active query created or specified. These are logical directions, not necessarily graph adjacency lists. The precise edge representation is non-semver-stable. When a nested query returns, the parent depends on the nested query's result. The parent need not inherit every transitive leaf dependency. That boundary is what permits early cutoff after a child backdates. Some cycle strategies flatten selected dependency information. Flattening is policy-driven, not permission to indiscriminately copy all edges. Dynamic tracking must deduplicate edges. Reading one input in a loop should not create a million identical dependencies. Order can still be retained for deterministic dumps and accumulator behavior.

6. The fetch hot path#

The public operation looks like an ordinary function call. Internally, a tracked-function fetch follows a state machine. Private function names mentioned here are non-semver-stable.

fetch(key)
  |
  +-- memo verified this revision? -- yes --> record dependency --> return
  |
  +-- claim key or join waiter
          |
          +-- another worker owns it --> wait / cycle check --> retry
          |
          +-- this worker owns it
                  |
                  +-- old memo exists?
                  |       |
                  |       +-- validate inputs with maybe_changed_after
                  |       |       |
                  |       |       +-- all green and value present --> verify
                  |       |       +-- changed or value absent ------> execute
                  |       |
                  |       +-- no memo ------------------------------> execute
                  |
                  +-- publish, release claim, wake waiters

The first check must be cheap because it dominates steady-state workloads. Claiming ensures at most one worker computes a database key at a time. A waiter does not compute duplicate work unless the implementation deliberately permits it. Waiters retry after wakeup because the state may have changed again. Validation asks each dependency whether it maybe changed after the memo's reference revision. maybe_changed_after is a current internal operation name and non-semver-stable. An input can answer from its own changed_at metadata. A derived dependency may first need validation or execution.

validate M last verified at r10
  ask A: maybe_changed_after(r10)? -> false
  ask B: maybe_changed_after(r10)?
      validate B
      B recomputes but equals old B
      B backdates changed_at to r7
      answer false
  all inputs green
  mark M verified at current revision

If every dependency remains unchanged and the value is resident, execution is skipped. If the value was evicted, valid metadata cannot reconstruct it; execution is required. If any dependency may have changed, execution is required. Execution installs a fresh active frame. The query function runs and records new input and output edges. The new result is compared with the old result using the generated update/equality policy. If observably equal, changed_at is backdated to the old memo's timestamp. If different, changed_at becomes the current revision. Backdating is the red–green cutoff mechanism. It does not claim that no work happened. It claims downstream observers cannot distinguish the new value from the old one. Before publishing, old and new output sets are reconciled. Outputs still present retain ownership and may update tracked fields. New outputs are registered to the current producer. Old outputs not reproduced become stale and are reclaimed or invalidated. Only after coherent publication may claim waiters wake. Unwinding must also release the claim and wake waiters. Otherwise one panic turns into a permanent hang.

7. Revisions and durability#

A revision is a logical database epoch, not a wall-clock timestamp. Input writes advance revision under the database's mutation protocol. Readers use revisions to ask whether prior observations remain valid. Multiple internal counters may coexist; their exact layout is non-semver-stable. Durability estimates how likely an input is to change. High-durability configuration might survive many low-durability edits. Memo durability is bounded by the least durable dependency it observed. Revision tracking can therefore skip broad classes of impossible changes.

durability LOW changed at r21
durability MEDIUM changed at r12
durability HIGH changed at r3
memo verified r20, minimum durability HIGH
=> low change at r21 cannot invalidate it

Durability is an optimization contract around mutation classification. Misclassifying a changing input as unaffected can make reuse unsound. A clone should omit durability until basic revision correctness is proven.

8. Tracked-struct identity and ownership#

A tracked struct is not structurally interned by all fields. Its stable identity originates in the active producer query. Current implementation details are non-semver-stable, but the model combines:

• producer database key;
• tracked-struct ingredient or type;
• declared identity fields;
• occurrence or disambiguator among equal creations.

TrackedId = f(
  producer = parse(file 1),
  ingredient = FunctionItem,
  identity = name "main",
  occurrence = 0
)

Identity fields match an entity across producer re-executions. Fields marked tracked are payload, not identity. When matched, tracked fields can change independently. Reading a tracked field creates a dependency on that field's ingredient/key. If only body changes, a query depending only on name can remain green. Occurrence handles repeated equal identities from one producer. It must be deterministic relative to a deterministic execution. Changing iteration order can therefore disturb identity. Good domain identity fields reduce dependence on occurrence ordering. Creation records an output edge from producer to tracked value. On re-execution, the new output set is diffed against the old set. Unreproduced tracked values become stale. Their fields and dependent specified values must not remain silently valid. This is output ownership and stale reclamation.

9. Interning, reclamation, and generations#

Interned identity is structural rather than producer-relative. Equal field tuples map to the same live ID. The reverse table resolves an ID to immutable fields.

("Vec", [T]) --hash/equality--> Interner table --> Id(page, slot, generation)
                                              ^
second equal tuple ---------------------------+

An implementation may retain interned values forever. Current engines can reclaim entries that are no longer reachable by tracked outputs. Slot reuse requires a new generation. An old Id must fail validation rather than resolve to unrelated fields. Structural equality alone does not define lifetime. The database must know what owns or references an interned entry. Reclamation can be conservative without harming semantic correctness. Premature reuse without generation checks is unsound.

10. Accumulators as query outputs#

An accumulator emits zero or more side values during execution. Public behavior lets callers obtain values accumulated by a query. Internally, accumulator records participate in output tracking. Their exact ingredient and storage types are non-semver-stable. An accumulator is not an untracked logging callback. Re-execution must replace old emissions with the new logical set or sequence. Validation reuse must make prior emissions available without rerunning the query. Nested query emissions must be attributed consistently for retrieval.

type_check(item)
  result: Type
  accumulated Diagnostics:
    [unknown name at span 8, mismatched type at span 21]

A learning clone can model diagnostics as owned memo outputs first. General typed accumulators can be added after ownership reconciliation works.

11. Cycles and fixed points#

A direct recursive fetch finds its database key already active. A parallel cycle may appear only in the wait-for graph. Salsa supports cycle policies beyond unconditional panic. The implementation names and recovery plumbing are non-semver-stable.

Fixed-point recovery begins with a provisional value. Queries in the cycle execute against provisional cycle results. The cycle iterates until values stop changing or a policy limit is reached. Dependencies may be flattened so the stabilized result depends on the external causes of the cycle.

A -> B -> C -> A
|              |
+-- external X-+

iteration 0: seed(A), seed(B), seed(C)
iteration 1: A1, B1, C1
iteration 2: A2, B2, C2
iteration n: unchanged => publish fixed point
dependency boundary includes X

Termination requires an appropriate lattice or convergent user operation. Equality alone detects convergence but cannot guarantee it. A minimal clone should reject cycles first. Fixed points are a later, explicit query policy.

12. Cancellation, synchronization, and eviction#

Cancellation is commonly delivered as a special unwind payload. Current Cancelled representation is implementation-specific where not public. Runtime checks at query boundaries and strategic points make old work stop. RAII cleanup must pop frames, abandon partial outputs, release claims, and wake waiters. Cancellation must never publish a half-built memo.

SyncTable is a non-semver-stable implementation name for coordinating in-progress keys. It tracks ownership, waiters, and enough wait-for information to detect deadlock cycles.

worker W1 owns A, waits for B
worker W2 owns B, waits for C
worker W3 owns C, waits for A

wait-for graph: W1 -> W2 -> W3 -> W1

Cycle handling must happen before all workers sleep forever. Wakeups are hints; state is checked in a loop. Lock ordering must not require holding a memo lock while recursively fetching dependencies.

LRU policies may remove expensive memo values. Dependency edges, timestamps, and output ownership metadata can remain. Metadata retention preserves validation and cleanup knowledge. A missing value forces execution even if validation proves inputs green. Eviction changes performance, never results.

13. Alternatives hidden by the public contract#

An engine could use reverse edges and eager dirty propagation. Salsa's model favors demand-driven validation with forward dependencies. An engine could hash dependency values rather than store changed_at revisions. An engine could permit redundant racing execution and publish one winner. An engine could serialize all work under one lock. An engine could never reclaim IDs.

These choices trade memory, latency, complexity, and parallelism. None excuse violating clean-rebuild equivalence. We now choose intentionally conservative alternatives for a learning clone.

Building a Safe Learning Clone#

14. Architecture specification#

Call the clone pepper, not Salsa. Its first release supports inputs and memoized typed queries. It uses no unsafe. It uses immutable query results behind Arc. It serializes writes against reads. It dynamically records direct dependencies. It validates on demand. It backdates equal results. It rejects cycles with a structured error. It treats diagnostics as owned query outputs.

Core invariants:

1. A returned memo equals a clean execution against the same input snapshot.
2. At most one published memo exists per (QueryId, KeyId) and revision history.
3. A ready memo's edges came from the same successful execution as its value.
4. verified_at <= current_revision.
5. changed_at <= verified_at after publication.
6. Backdating occurs only after semantic equality.
7. An active frame is popped on success, error, cancellation, and panic.
8. A claim is released on every exit path.
9. A dependency is recorded in the caller, not in the callee's frame.
10. Outputs not reproduced by a successful re-execution are retired.
11. No stale generational ID resolves to a new occupant.
12. Cache eviction cannot alter observable values or diagnostics.

15. Module layout#

src/
  lib.rs             public Database and typed facade
  id.rs              QueryId, KeyId, DatabaseKey, generations
  query.rs           Query trait and registration descriptor
  registry.rs        safe erased Any adapters
  interner.rs        typed key and value interning
  memo.rs            Memo, MemoState, dependency metadata
  runtime.rs         local stack, frames, cancellation checks
  revision.rs        Revision and write transaction
  engine.rs          fetch, validate, execute, publish
  output.rs          diagnostics and owned output reconciliation
  cycle.rs           cycle error and later policies
  sync.rs            claims, waiters, wait-for graph
  lru.rs             resident-value budget
  metrics.rs         counters and timings
  dump.rs            deterministic debugging views

Do not begin with procedural macros. Handwritten registrations keep every type transition visible. Macros become optional syntax generation after the engine is tested.

16. Typed queries over an erased registry#

The user-facing trait preserves key and value types.

pub trait Query: Send + Sync + 'static {
    type Key: Eq + Hash + Clone + Send + Sync + Debug + 'static;
    type Value: Eq + Send + Sync + Debug + 'static;

    const NAME: &'static str;

    fn execute(db: &Database, key: Self::Key) -> Result<Self::Value, QueryError>;
}

The facade interns a typed key, enters the erased engine, and downcasts the result.

impl Database {
    pub fn get<Q: Query>(&self, key: Q::Key) -> Result<Arc<Q::Value>, QueryError> {
        let query = self.shared.registry.id_of::<Q>()?;
        let key = self.shared.keys.intern::<Q>(query, key)?;
        let erased = self.fetch(DatabaseKey { query, key })?;
        Arc::downcast::<Q::Value>(erased)
            .map_err(|_| QueryError::RegistryTypeMismatch(Q::NAME))
    }
}

The registry stores safe erased adapters. Any downcasts replace pointer casts and type-layout assumptions.

trait ErasedQuery: Send + Sync {
    fn name(&self) -> &'static str;
    fn execute_erased(
        &self,
        db: &Database,
        key: &(dyn Any + Send + Sync),
    ) -> Result<Arc<dyn Any + Send + Sync>, QueryError>;
    fn values_equal(&self, a: &dyn Any, b: &dyn Any) -> Result<bool, QueryError>;
}

struct Adapter<Q>(PhantomData<Q>);

Adapter<Q> downcasts the key to Q::Key. It calls Q::execute. It wraps Q::Value in Arc<dyn Any + Send + Sync>. Its equality method downcasts both values before ==. A mismatch is an engine bug reported as an error, never undefined behavior.

Production systems may use audited unsafe for compact tables, erased function pointers, and zero-cost references. Those optimizations can avoid Any, hashing, and repeated dynamic checks. Our clone buys auditability with allocation and dispatch overhead. Do not copy unsafe until profiling identifies a boundary and tests can defend it.

17. IDs and key interning#

Use explicit newtypes.

#[derive(Copy, Clone, Eq, PartialEq, Hash, Ord, PartialOrd, Debug)]
pub struct QueryId(u32);

#[derive(Copy, Clone, Eq, PartialEq, Hash, Ord, PartialOrd, Debug)]
pub struct KeyId { slot: u32, generation: u32 }

#[derive(Copy, Clone, Eq, PartialEq, Hash, Ord, PartialOrd, Debug)]
pub struct DatabaseKey { query: QueryId, key: KeyId }

Each query owns a typed key interner behind an erased interface. Milestone one never reclaims query keys, so generation remains zero. Keeping the field now prevents APIs from assuming a bare vector index.

typed Q::Key
   |
   v
HashMap<Q::Key, KeyId> <--> Vec<Arc<Q::Key>>
   |
   v
DatabaseKey { QueryId, KeyId }

Registration assigns stable-for-this-process QueryId values. Never persist those numeric IDs without a schema mapping. Duplicate registration of the same Rust TypeId is rejected.

18. Memo store#

Start with one RwLock<HashMap<DatabaseKey, Memo>>. This is slow but establishes semantics.

struct Memo {
    value: Option<Arc<dyn Any + Send + Sync>>,
    verified_at: Revision,
    changed_at: Revision,
    dependencies: Arc<[DatabaseKey]>,
    outputs: Arc<[OutputId]>,
    diagnostics: Arc<[Diagnostic]>,
    last_access: u64,
}

Never hold the store lock while running user code. Clone Arc metadata into a snapshot, release the lock, then validate. Publication reacquires a write lock and checks claim ownership.

The initial single-threaded version can omit claims. The first concurrent version adds a separate state per database key. Keep memo contents separate from execution state.

19. Shared database and local runtime#

pub struct Database {
    shared: Arc<Shared>,
    local: Runtime,
}

struct Shared {
    revision: AtomicU64,
    registry: Registry,
    keys: KeyInterners,
    memos: RwLock<HashMap<DatabaseKey, Memo>>,
    inputs: RwLock<InputStore>,
    write_gate: RwLock<()>,
    cancel_epoch: AtomicU64,
    metrics: Metrics,
}

struct Runtime {
    stack: RefCell<Vec<ActiveFrame>>,
    observed_cancel_epoch: Cell<u64>,
}

Database clones share Shared but receive independent local runtimes. If handles can cross threads, make the runtime thread-local rather than RefCell in a Sync object. An easy rule is that a handle is thread-confined and Database::fork() creates another handle.

20. RAII active frames#

An execution frame gathers provisional edges and outputs.

struct ActiveFrame {
    key: DatabaseKey,
    dependencies: Vec<DatabaseKey>,
    seen_dependencies: HashSet<DatabaseKey>,
    outputs: Vec<OutputId>,
    diagnostics: Vec<Diagnostic>,
}

Use a guard whose Drop removes or aborts the frame. Because borrowing a RefCell<Vec<_>> across user execution is impossible, push first and borrow only for short updates. The guard stores expected depth and key. On success, finish() pops and returns the frame. On drop without finish, it pops and discards provisional state.

struct FrameGuard<'a> {
    runtime: &'a Runtime,
    depth: usize,
    finished: bool,
}

impl Drop for FrameGuard<'_> {
    fn drop(&mut self) {
        if !self.finished {
            self.runtime.abort_frame(self.depth);
        }
    }
}

After a child fetch succeeds, call record_dependency(child_key) on the now-current parent. Do not record self-edges for top-level calls. Use HashSet for membership and Vec for stable first-observation order.

21. Input writes as transactions#

Readers take a shared write_gate guard for the duration of a top-level request. Writers take the exclusive guard. This gives each request a coherent input snapshot.

pub struct WriteTxn<'db> {
    db: &'db Database,
    _gate: RwLockWriteGuard<'db, ()>,
    staged: Vec<InputChange>,
}

impl WriteTxn<'_> {
    pub fn commit(mut self) -> Revision {
        let next = self.db.shared.revision.fetch_add(1, SeqCst) + 1;
        self.db.shared.inputs.write().apply(next.into(), &mut self.staged);
        self.db.shared.cancel_epoch.fetch_add(1, SeqCst);
        next.into()
    }
}

Real code should apply values before publishing the revision, under the same exclusion protocol. No-op writes compare old and new input values. They may avoid advancing revision. Changed inputs set their own changed_at to the committed revision. A transaction groups multiple changes into one revision.

22. Fetch pseudocode#

FETCH(dbkey):
  check cancellation
  revision = current revision
  if dbkey occurs on local stack: return Cycle(stack slice)
  if memo exists and memo.verified_at == revision and value exists:
      record dbkey in caller
      touch LRU
      return value
  claim dbkey
  recheck memo after claim
  if memo exists and value exists and VALIDATE(memo, revision):
      publish verified_at = revision
      release claim and wake waiters
      record dbkey in caller
      return value
  result = EXECUTE(dbkey, old memo, revision)
  publish result atomically
  release claim and wake waiters
  record dbkey in caller
  return result.value

The recheck after claiming closes a race with another worker's publication. The caller edge is recorded only after successful completion. Errors can be memoized only if error equality and invalidation semantics are explicit. For the first clone, return errors without memoizing them.

23. Validation and maybe_changed_after#

VALIDATE(memo, current):
  for dependency in memo.dependencies:
      if MAYBE_CHANGED_AFTER(dependency, memo.verified_at):
          return false
  return true

MAYBE_CHANGED_AFTER(key, revision):
  if key is input:
      return input.changed_at > revision
  FETCH(key) to bring dependency current
  return dependency.memo.changed_at > revision

Validation must not accidentally add each dependency to the original query's new execution frame. It runs before that frame exists. Its nested fetches may record into a validator context only if the architecture requires one. The old dependency list remains authoritative when validation succeeds.

A substantial safe sketch:

fn validate(&self, memo: &MemoSnapshot, now: Revision) -> Result<bool, QueryError> {
    for &dep in memo.dependencies.iter() {
        self.check_cancelled()?;
        self.fetch_erased(dep)?;
        let changed_at = self.memo_changed_at(dep)
            .ok_or(QueryError::MissingMemo(dep))?;
        if changed_at > memo.verified_at {
            return Ok(false);
        }
    }
    debug_assert!(memo.verified_at <= now);
    Ok(true)
}

Inputs can bypass fetch_erased through a unified ingredient operation or explicit branch. Prefer one erased maybe_changed_after registry method once multiple ingredient kinds exist.

24. Execute, compare, and backdate#

fn execute_claimed(
    &self,
    key: DatabaseKey,
    old: Option<MemoSnapshot>,
    now: Revision,
) -> Result<PendingMemo, QueryError> {
    let guard = self.local.push_frame(key)?;
    let adapter = self.shared.registry.get(key.query)?;
    let typed_key = self.shared.keys.lookup(key)?;
    let value = adapter.execute_erased(self, typed_key.as_ref())?;
    let frame = guard.finish();

    let equal = match old.as_ref().and_then(|m| m.value.as_ref()) {
        Some(previous) => adapter.values_equal(previous.as_ref(), value.as_ref())?,
        None => false,
    };
    let changed_at = if equal {
        old.as_ref().unwrap().changed_at
    } else {
        now
    };
    Ok(PendingMemo::new(value, frame, now, changed_at))
}

Equality must correspond to public observability. If diagnostics are observable, include them in change comparison or track them as separate outputs. Do not backdate merely because hashes match. Hashes may accelerate an equality check but cannot replace it without collision handling.

Publishing performs output reconciliation before replacing the old memo. The entire transition appears atomic to other fetchers.

25. Output and diagnostic ownership#

Give every created output an OutputId and owner DatabaseKey. During execution, creation appends the ID to the active frame. On publication, compare old and new output sets.

kept    = old ∩ new  -> update payload, preserve identity
created = new - old  -> install with owner
stale   = old - new  -> retire and bump generation

Diagnostics can initially be plain immutable values in the memo. On cache reuse, return the stored diagnostic slice. On execution, replace it with the frame's slice. Diagnostic equality should be deterministic and include stable spans and codes.

Later, represent diagnostics as an output ingredient if callers query them independently. Never append new diagnostics to old ones across revisions. Never publish diagnostics emitted before a cancelled unwind.

26. A safe interner#

struct Interner<T> {
    by_value: HashMap<Arc<T>, KeyId>,
    slots: Vec<Slot<T>>,
    free: Vec<u32>,
}

struct Slot<T> {
    generation: u32,
    value: Option<Arc<T>>,
    owners: usize,
}

Interning probes by hash and equality. A hit returns the existing live ID. A miss uses a free slot or appends one. Reusing a free slot preserves its incremented generation. Lookup checks slot bounds, generation equality, and presence.

Reclamation starts conservatively. Count ownership from live memo outputs, not temporary stack references. Retirement decrements ownership. Zero owners permits removal from by_value, clearing the slot, and generation increment. Overflow retires the slot forever rather than wrapping.

The safe clone returns Arc<T> from lookup. Production may return database-tied references using carefully audited storage stability and unsafe code. Our extra reference count avoids manufacturing lifetimes.

27. Cancellation#

Each top-level request snapshots cancel_epoch. A committed write increments the epoch. Long-running queries call db.unwind_if_cancelled() at bounded intervals.

fn check_cancelled(&self) -> Result<(), QueryError> {
    let current = self.shared.cancel_epoch.load(Acquire);
    if current != self.local.observed_cancel_epoch.get() {
        return Err(QueryError::Cancelled);
    }
    Ok(())
}

An error return is easier to teach than a panic payload. RAII must still handle arbitrary user panics with catch_unwind at worker boundaries. Never catch a panic and publish its partial frame. After cancellation, a new top-level request snapshots the new epoch.

28. Cycle policy#

Milestone one detects a local stack repetition. Return the shortest cycle path for debugging.

stack: root -> infer(A) -> normalize(B) -> infer(A)
cycle: infer(A) -> normalize(B) -> infer(A)

Declare policies per query:

pub enum CyclePolicy<V> {
    Reject,
    FixedPoint { seed: V, max_iterations: usize },
}

Do not implement the generic enum until a real monotone domain exists. A fixed-point implementation executes a strongly connected component as a unit. It compares each iteration's vector of values. It publishes only after convergence. It flattens dependencies to external edges of the component. Non-convergence returns an error and publishes nothing.

29. LRU without semantic damage#

Track resident value bytes approximately. Touch a monotonic access counter on successful fetch. Evict only unclaimed memos. Set memo.value = None while retaining revisions, dependencies, outputs, and diagnostics.

Do not reclaim owned outputs merely because a value was evicted. They describe the last successful execution. The next fetch validates metadata, then executes because the value is absent. Equality cannot backdate against an absent old value unless a trustworthy retained fingerprint plus reconstruction policy exists. The safe first rule marks the re-executed result changed at now when old value is absent. This loses some cutoff performance but preserves correctness.

30. Metrics and debugging dumps#

Collect counters before optimizing:

• fetches and same-revision hits;
• validations attempted and passed;
• executions and backdates;
• dependency edges observed and deduplicated;
• claim waits and wait duration;
• cancellations and cycles;
• resident bytes and evictions;
• stale outputs reclaimed;
• maximum stack depth.

Provide deterministic dumps sorted by (query name, key debug form).

parse(File(1))
  value: resident
  verified_at: r18
  changed_at: r12
  deps: [file_text(File(1))@r12]
  outputs: [SyntaxNode(7:g2), SyntaxNode(8:g0)]
  diagnostics: 1

A graph dump should distinguish observed input edges from owned output edges. A trace should show claim, validate, execute, backdate, publish, and wake events. Redact or hash large user values by default.

31. Concurrency progression#

Do not jump directly to lock-free tables.

Stage A: global execution lock#

One mutex surrounds all fetch execution. This proves revision, dependency, and backdating semantics. Recursive calls require reentrant architecture, not a reentrant mutex. The engine lock must be released around nested/user execution or replaced by explicit single-thread ownership.

Stage B: per-key state#

enum KeyState {
    Idle,
    Running { owner: WorkerId },
}

struct KeySync {
    state: Mutex<KeyState>,
    ready: Condvar,
}

One worker changes Idle to Running. Others wait in a condition-variable loop. The owner publishes or aborts, changes to Idle, then notify_all. Never wait while holding the memo table write lock.

Stage C: waiters and a wait-for graph#

Before sleeping, record waiting_worker -> owner_worker. Search for a path back to the waiter. If found, report a parallel cycle or invoke explicit recovery. Remove the wait edge with RAII after wakeup or unwind.

claim table: DatabaseKey -> WorkerId
wait graph:  WorkerId -> WorkerId
local stack: WorkerId -> [DatabaseKey]

Use stable worker IDs, not recycled thread IDs without generations. Spurious wakeups require a loop. Poisoned standard locks should become structured engine errors or be deliberately recovered.

Stage D: sharded stores#

Shard memo maps by database-key hash. Keep recursive fetches outside shard guards. Acquire multiple shard locks in numeric order for reconciliation. Measure contention before introducing atomics or unsafe cells.

Production Salsa may use audited unsafe to provide stable references and reduce lock/dispatch overhead. Its safety argument spans macro-generated types, tables, and runtime protocols. Our clone intentionally pays with Arc, lock guards, and downcasts.

32. Optional persistence layer#

Persistence is the final layer, not milestone one. Persist only values with an explicit stable codec and schema version. Do not serialize process-local QueryId or KeyId as durable identity. Map queries by stable names plus schema hashes. Map keys and values through query-defined codecs.

A persisted memo needs dependency fingerprints that can be resolved after restart. It also needs engine version, target/configuration identity, and durability assumptions. Treat every decode or mismatch as a cache miss. Never let cache corruption become semantic corruption. An atomic manifest swap avoids exposing a partially written cache.

33. Optional procedural macros#

After handwritten registration is stable, a macro may generate:

• a marker type implementing Query;
• typed facade functions;
• registration descriptors;
• key tuple types;
• debug names and source locations;
• equality/update adapters.

The macro must generate ordinary safe calls into the same engine. It should not become a second runtime. Use compile-fail tests for invalid signatures and missing bounds. Keep expanded-code snapshots readable.

34. Milestones and focused tests#

Milestone 1: inputs and revisions#

• setting a changed input advances one revision;
• a no-op write does not change changed_at;
• a transaction with three writes advances once;
• readers never observe half a transaction.

Milestone 2: memoization#

• two same-revision fetches execute once;
• distinct keys have distinct memos;
• errors do not leave ready memos;
• recursive self-fetch reports a cycle path.

Milestone 3: dynamic dependencies#

• changing an unread input does not execute the query;
• branch changes replace the old dependency set;
• repeated reads yield one edge;
• nested queries record direct, not flattened, edges.

Milestone 4: validation and backdating#

• a changed leaf re-executes its direct consumer;
• equal consumer output preserves old changed_at;
• downstream work stops at the backdated consumer;
• changed output propagates to downstream execution.

Milestone 5: outputs and interning#

• structurally equal intern requests return one ID;
• stale generation lookup fails;
• unreproduced outputs are retired;
• cancelled executions retire no previously live outputs;
• diagnostics are replaced rather than appended.

Milestone 6: eviction#

• evicted values execute when requested;
• retained metadata remains dumpable;
• eviction never changes clean-rebuild output;
• outputs survive value-only eviction.

Milestone 7: concurrency#

• twenty threads requesting one cold key execute it once;
• panic releases claims and wakes all waiters;
• cancellation releases claims;
• parallel wait cycles return errors rather than hang;
• randomized scheduling produces deterministic values.

35. Differential, property, fuzz, and concurrency testing#

For every generated edit sequence, compare incremental results with a fresh database.

incremental_db.apply(edit)
incremental = incremental_db.get(root)

clean_db = Database::from_inputs(current_inputs)
clean = clean_db.get(root)

assert incremental == clean
assert incremental diagnostics == clean diagnostics

Property generators should vary graph shape, branch-dependent reads, equal-output transformations, and no-op writes. Generate query DAGs first, then deliberately inject cycles. Shrink failures to the smallest edit and graph.

Fuzz erased registry operations with wrong IDs and stale generations. The expected result is a structured error, never panic or memory unsafety. Fuzz cancellation at every instrumented yield point. Fuzz output reconciliation with duplicate and reordered creations.

Use a deterministic scheduler model for claim and wait transitions. Model-check tiny two-worker, three-key scenarios. Run stress tests under ThreadSanitizer where the toolchain permits. Add timeouts only to detect hangs; do not use sleeps as synchronization assertions.

36. Failure-mode table#

37. Architecture defense questions#

Before calling the clone complete, defend these answers in writing:

1. Where is the clean-rebuild equivalence argument for each reuse path?
2. Which lock establishes an input snapshot, and when is it held?
3. What linearization point publishes a memo?
4. How does a waiter distinguish wakeup, cancellation, and cycle recovery?
5. Why can no user callback run while an internal map lock is held?
6. How are caller dependencies recorded after a cache hit?
7. Why does validation not mutate the old dependency set?
8. What exactly participates in semantic equality?
9. What survives LRU eviction, and why?
10. How does panic unwind remove frames and claims?
11. How are stale outputs found if a producer emits nothing on rerun?
12. What prevents ABA when a slot is reclaimed?
13. Which IDs are process-local, and which names are persistent?
14. Why are diagnostics deterministic under parallel execution?
15. What cycle domains are guaranteed to converge?
16. What metric would justify replacing Any with unsafe erasure?
17. Which tests would detect an incorrect unsafe optimization?
18. Can a query observe time, randomness, or mutable global state?
19. If so, where is that observation represented as an input?
20. How does the trace explain one surprising recomputation?

38. What the clone deliberately does not copy#

It does not reproduce Salsa's private type graph line for line. It does not expose ingredients as a user configuration API. It does not promise database-borrowed result references. It does not begin with paged lock-free storage. It does not reclaim every unreachable object immediately. It does not infer a fixed-point domain from Eq. It does not make persisted cache hits authoritative.

Those omissions are teaching choices, not claims that production complexity is accidental. Salsa's current Storage, StorageHandle, Zalsa, ZalsaLocal, Runtime, Ingredient, JarImpl, Memo, QueryStack, ActiveQuery, and SyncTable names remain non-semver-stable implementation details. The reusable ideas are typed boundaries, erased addresses, revisioned evidence, dynamic edges, ownership reconciliation, and unwind-safe synchronization.

At this point the clone has an architecture, a correctness oracle, and a staged path to concurrency. Part VI can place that work into the overall study plan and consolidate the shared glossary.

Part VI: From Understanding to Mastery#

Mastery is not remembering an engine's vocabulary. It is being able to predict a trace, expose the evidence behind reuse, and prove that every incremental answer equals a clean rebuild. Use this part as a workbook. Write predictions before running code, keep traces beside tests, and explain every design choice in terms of correctness before performance.

Version note: the examples in this textbook target Salsa 0.28.1 as checked on 2026-08-03. Salsa is experimental; verify current documentation and examples before copying signatures. The concepts are more durable than the API.

A staged thirty-day practice plan#

Work in a small TinyLox repository. Preserve each day's artifact in a commit so later measurements can be compared with an honest baseline.

Day 1 — Establish the oracle#

• Build artifact: A batch compiler function that accepts an explicit ProgramInputs value and returns code, diagnostics, and semantic facts.
• Reasoning goal: Define observable equivalence; caches may change execution, never the answer.
• Verification: Run a corpus twice from fresh processes and snapshot all observable outputs, including diagnostic order and spans.

Day 2 — Draw the pipeline as requests#

• Build artifact: A graph of source → parse → resolve → infer → lower → codegen, with candidate keys on every node.
• Reasoning goal: Distinguish a stage name from one keyed invocation and a possible edge from an observed dependency.
• Verification: Explain which roots a build, hover, and go-to-definition request force; have a peer challenge one unnecessary edge.

Day 3 — Inventory the world#

• Build artifact: An input ledger covering files, flags, target data, environment, generated sources, and tool versions.
• Reasoning goal: Recognize that filesystem reads, clocks, randomness, and process environment are untracked unless modeled.
• Verification: Search computation code for ambient reads and either remove each one or route it through the ledger.

Day 4 — Choose identities#

• Build artifact: Typed FileId, FunctionId, and NameId keys plus a written lifetime and stability policy.
• Reasoning goal: Separate human names, in-memory handles, and cross-session stable identities.
• Verification: Reorder file discovery and confirm equivalent source entities retain the intended identity—or document why they should not.

Day 5 — Instrument the baseline#

• Build artifact: Per-stage invocation counts, wall time, output sizes, and a reproducible edit script.
• Reasoning goal: Treat counts as algorithmic evidence and timing as noisy experimental evidence.
• Verification: Record five clean runs and report dispersion rather than selecting the fastest run.

Day 6 — Add same-revision memoization#

• Build artifact: A typed cache for parse(FileId) with hit, miss, and execution trace events.
• Reasoning goal: Understand that same-key memoization alone says nothing about validity after an edit.
• Verification: Two reads in one revision execute once; a deliberately changed input cannot silently reuse the old answer.

Day 7 — Record dynamic dependencies#

• Build artifact: An active query-frame stack that records child reads and replaces the parent's edge set after success.
• Reasoning goal: Derive edges from actual control flow, including conditional calls.
• Verification: Toggle a branch and assert the trace contains the new dependency set, not a union accumulated forever.

Day 8 — Make unwind safe#

• Build artifact: An RAII frame guard that restores stack state on success, error, cancellation, and panic.
• Reasoning goal: See execution context as transactional state rather than convenient logging.
• Verification: Inject a panic, catch it at the test boundary, and prove the next independent query records the correct parent.

Day 9 — Separate revision facts#

• Build artifact: Memos with verified_at and changed_at fields and a trace printer for both.
• Reasoning goal: Distinguish “checked this revision” from “last produced a different observable value.”
• Verification: Create an equal recomputation whose verified_at advances while changed_at remains old.

Day 10 — Implement validation#

• Build artifact: Pull-based recursive validation that executes only when dependency evidence cannot prove reuse.
• Reasoning goal: Explain green as a proof outcome, not as “present in cache.”
• Verification: Change an unrelated input; the root validates without executing, and a clean database returns the same result.

Day 11 — Publish revisions atomically#

• Build artifact: An edit transaction that applies related input changes before exposing one new revision.
• Reasoning goal: Prevent readers from observing impossible mixtures of old and new inputs.
• Verification: A concurrency test repeatedly updates two correlated values and never observes a half-applied pair.

Day 12 — Add backdating#

• Build artifact: Equality-based early cutoff that retains old changed_at only when complete observable output is equal.
• Reasoning goal: Identify equality as a correctness boundary, not a convenient optimization hook.
• Verification: A comment edit reruns lexing as needed but stops propagation when tokens and diagnostics are unchanged.

Day 13 — Treat errors as values#

• Build artifact: Parse and type results that cache deterministic failures with structured diagnostics.
• Reasoning goal: Avoid side channels whose outputs disappear on a cache hit or duplicate on recomputation.
• Verification: Repeated invalid input returns one stable diagnostic set; fixing it removes stale diagnostics.

Day 14 — Reconcile produced entities#

• Build artifact: Ownership metadata connecting generated HIR items and diagnostics to their producing invocation.
• Reasoning goal: Understand that outputs can be collections with identity, not merely one return value.
• Verification: Delete one function and prove its tracked entity and diagnostic do not survive.

Day 15 — Differentially test edit sequences#

• Build artifact: A harness applying edits to an incremental database and a new clean database in parallel.
• Reasoning goal: Make clean-rebuild equivalence the primary correctness oracle.
• Verification: Compare results after every prefix of at least fifty generated edit sequences.

Day 16 — Refine compiler granularity#

• Build artifact: File-level parsing, item-level signatures, and function-level inference with measured fanout.
• Reasoning goal: Balance validation overhead, key stability, duplicated work, and invalidation precision.
• Verification: Compare a function-body edit and a public-signature edit; explain every executed consumer.

Day 17 — Intern canonical names#

• Build artifact: A safe name interner with canonical lookup and typed handles.
• Reasoning goal: Separate deduplication from tracked identity and persistence identity.
• Verification: Equal names intern identically within a database; randomized insertion order does not alter semantic results.

Day 18 — Trace red-green behavior#

• Build artifact: A visual trace marking validated, executed, changed, and backdated invocations.
• Reasoning goal: Explain why a changed input need not make every transitive consumer red.
• Verification: Predict the complete trace for three edits, then annotate every mismatch between prediction and observation.

Day 19 — Handle accidental cycles#

• Build artifact: Same-thread cycle detection that reports the shortest useful query path.
• Reasoning goal: Distinguish recursion in the implementation from recursion accepted by the source language.
• Verification: Direct and indirect cycles terminate with deterministic paths and leave no poisoned active frame.

Day 20 — Model semantic fixed points#

• Build artifact: A separate monotone effect analysis over a finite lattice.
• Reasoning goal: State the ordering, join, transfer monotonicity, and termination argument before iterating.
• Verification: Mutually recursive functions converge independent of visitation order; a non-monotone test is rejected or bounded explicitly.

Day 21 — Build with current Salsa#

• Build artifact: A minimal Salsa 0.28.1 database using #[salsa::input], #[salsa::interned], #[salsa::tracked], and #[salsa::db] as current docs require.
• Reasoning goal: Map inputs, identities, and tracked computations to APIs without mistaking macros for the algorithm.
• Verification: Compile against a pinned version and reject obsolete query_group, jar-list, and old database examples in review.

Day 22 — Explore Salsa outputs#

• Build artifact: A tracked struct with deliberate identity fields, a #[tracked] value field, and an accumulator for diagnostics.
• Reasoning goal: Explain producer identity, occurrence disambiguation, and why Result still suits control-flow errors.
• Verification: Reorder duplicate productions, inspect identity effects, and test diagnostics through the intended root.

Day 23 — Compare three architectures#

• Build artifact: A table contrasting the safe clone, current Salsa, and rustc's independent query system.
• Reasoning goal: Transfer principles without claiming implementation equivalence.
• Verification: State aloud: rustc does not use Salsa; identify rustc providers and DepGraph as rustc-specific machinery.

Day 24 — Add cancellation#

• Build artifact: Cooperative cancellation checkpoints and cleanup-safe publication rules.
• Reasoning goal: Ensure cancelled work publishes neither partial values nor incomplete dependency evidence.
• Verification: Cancel at every injected checkpoint; subsequent uncancelled requests equal a clean rebuild.

Day 25 — Bound memory#

• Build artifact: Value eviction policy that preserves or reconstructs the metadata required for sound validation.
• Reasoning goal: Separate cache residency from logical validity.
• Verification: Run under a small memory budget, force evictions, and compare answers and traces with eviction disabled.

Day 26 — Harden concurrency#

• Build artifact: Per-key job coordination, a documented lock order, and waiter-cycle detection or prevention.
• Reasoning goal: Distinguish duplicate-work suppression, deadlock freedom, snapshots, and incremental correctness.
• Verification: Stress hot keys with many readers; use Loom where practical to explore small synchronization schedules.

Day 27 — Prototype persistence#

• Build artifact: A versioned cache envelope containing schema, compiler, target, input, and stable-key fingerprints.
• Reasoning goal: Treat disk bytes as untrusted hints whose acceptance requires complete compatibility evidence.
• Verification: Corrupt, truncate, reorder, and version-skew cache files; safely reject them and produce clean-build answers.

Day 28 — Attack the implementation#

• Build artifact: Property tests, malformed-program fuzz targets, and Miri checks for unsafe assumptions—ideally none in the clone.
• Reasoning goal: Search for counterexamples to invariants rather than examples that merely exercise code.
• Verification: Minimize one discovered failure or document seeded faults that each tool detects.

Day 29 — Run controlled performance experiments#

• Build artifact: A benchmark report with workload, machine, revision sequence, warmup, samples, and raw traces.
• Reasoning goal: Replace “incremental is faster” with conditional claims tied to measured scenarios and costs.
• Verification: Reproduce the report from one command and include a workload where query overhead loses.

Day 30 — Defend the design#

• Build artifact: A ten-minute demo, architecture decision record, correctness dossier, and known-limits list.
• Reasoning goal: Teach the chain of evidence so another engineer can reason without copying your code.
• Verification: Survive a review in which someone proposes an untracked read, unstable key, cycle, cancellation, and stale disk entry.

Progressive exercises with answer sketches#

Do each exercise on paper first. An answer sketch names the core argument; your implementation or trace should supply the evidence.

Exercise 1 — Query vocabulary#

For type_of(FunctionId(7)), identify query kind, key, invocation, and value. Answer sketch: type_of is the kind, FunctionId(7) the key, their pair the invocation, and the returned type result—including modeled errors—the value.

Exercise 2 — Memoization boundary#

Why can a hash map keyed only by FileId be correct within one immutable run but stale after an edit? Answer sketch: Same-run inputs are fixed; after mutation the key is unchanged while its answer-affecting source differs. Revision and dependency validation are missing.

Exercise 3 — Ambient input#

Code generation reads TARGET_CPU directly from the environment. Repair the design. Answer sketch: Snapshot the environment at the application boundary, store the relevant value as a tracked input, and make codegen read that input.

Exercise 4 — Dynamic trace#

layout(T) reads fields(T) only for structs. Trace dependencies before and after T becomes an integer. Answer sketch: The first successful run records layout → kind and layout → fields; the second records only layout → kind. Replace edges rather than append forever.

Exercise 5 — Revision meanings#

An input changes at revision 9; parsing executes and returns an equal tree. What happens to parse's two revision fields? Answer sketch: verified_at becomes 9. With sound equality over all observable parse output, changed_at remains its earlier value.

Exercise 6 — Red-green chain#

Source changes, tokens remain equal, and typecheck depends on parse. Which nodes execute and which may validate green? Answer sketch: The input is changed; lex/parse may execute according to boundaries and backdate equal outputs. typecheck can validate through unchanged changed_at evidence without executing.

Exercise 7 — Equality trap#

An AST equality implementation ignores source spans, but diagnostics expose spans. Is backdating sound? Answer sketch: No. Spans are observable through diagnostics. Include them in equality/output evidence or split semantic structure from tracked location data.

Exercise 8 — Error caching#

Should a deterministic parse error bypass the cache? Answer sketch: Usually no. Model the error and diagnostics as query output so reuse is stable; bypass only for explicitly transient, tracked conditions.

Exercise 9 — Identity under insertion#

Two equal generated items appear in one producer. Why can occurrence order matter? Answer sketch: Identity needs to distinguish duplicates; producer, ingredient/type, identity fields, and occurrence disambiguation can participate. Reordering duplicates may therefore change handles.

Exercise 10 — Hash/equality contract#

Two keys compare equal but hash differently. Predict the damage. Answer sketch: Cache lookup may create logically duplicate invocations, splitting dependency history and violating map assumptions. Equal keys must hash equally.

Exercise 11 — Accidental cycle#

type_of(A) requests type_of(B), which requests type_of(A). What should the default engine do? Answer sketch: Detect the active-path recurrence, report the cycle with keys, unwind safely, and publish no partial memo. Do not silently invent a fixed point.

Exercise 12 — Valid fixed point#

Effect sets only grow by union across callees. Give the convergence argument. Answer sketch: Subset order forms a finite lattice, union is the join, and monotone transfer can ascend only finitely many times before stabilization.

Exercise 13 — Granularity choice#

Compare one infer(FileId) query with infer(FunctionId) for an IDE workload. Answer sketch: Function granularity may reduce body-edit fanout and increase keys, edges, validation, and identity work. Measure edit distribution and costs; neither is universally best.

Exercise 14 — Public signature edit#

Why may editing one function invalidate queries in unchanged files? Answer sketch: Consumers depend on the changed signature fact, not file modification status. Dynamic edges follow semantic fanout across files.

Exercise 15 — Salsa handle lifetimes#

Why should you consult current Salsa docs rather than generalize from an old tutorial's handle types? Answer sketch: Current inputs and database-bound tracked/interned handles have API-specific lifetime and return-mode rules; Salsa remains experimental and old group/jar APIs are obsolete.

Exercise 16 — Salsa accumulator or Result#

A missing name prevents type inference and also needs a diagnostic. Choose representations. Answer sketch: Return a structured Result for control flow and use an accumulator when diagnostics must be collected through a root; test cache-hit behavior and avoid duplicate emission.

Exercise 17 — rustc separation#

A slide says “rustc uses Salsa's red-green algorithm.” Correct it. Answer sketch: Say rustc has its own query engine, providers, DepGraph, fingerprints, and cache/work-product policies. Red-green is shared conceptual language, not proof of Salsa reuse.

Exercise 18 — Clone registry#

Design a safe erased storage boundary for heterogeneous query values. Answer sketch: Keep typed wrappers around a registry using Arc<dyn Any + Send + Sync>, checked downcasts, and unique query-kind IDs. Prefer clear allocation costs to unjustified unsafe.

Exercise 19 — Panic during execution#

A provider panics after recording two children. May those edges or a value be installed? Answer sketch: No partial result should publish. An unwind guard removes the active frame; installation commits only a complete successful execution.

Exercise 20 — Concurrent duplicate request#

Two threads request the same cold key. What are correct policy choices? Answer sketch: Coordinate one owner and waiters, or permit duplicate pure computation then publish consistently. Either needs deadlock, panic, cancellation, and output-duplication semantics.

Exercise 21 — Snapshot consistency#

A reader starts at revision 4 while a writer commits revision 5. What must be specified? Answer sketch: The reader sees one coherent revision, blocks, or is cancelled/retried. It must not combine revision-4 dependencies with revision-5 inputs.

Exercise 22 — Disk key#

Why is serialized FileId(12) insufficient for persistence? Answer sketch: Allocation order is process-local. Use stable source identity plus compiler, schema, target, and relevant option fingerprints; reject ambiguity conservatively.

Exercise 23 — Eviction#

Can an LRU remove a large value while retaining its memo metadata? Answer sketch: Yes, if the engine represents value absence explicitly and can recompute safely. Validity evidence and residency are separate, but retrieval must never return a missing value as a hit.

Exercise 24 — Differential property#

State a property stronger than “a second request hits the cache.” Answer sketch: For every generated input and edit sequence, each incremental root result and observable diagnostic set equal those from a newly constructed database at that step.

Exercise 25 — Performance claim#

A benchmark shows one 40% improvement after a function-body edit. What may you claim? Answer sketch: Only that this measured workload/run improved under stated conditions. Report samples and variance; do not infer all projects, edits, machines, or clean builds become faster.

Debugging playbook: evidence before fixes#

Start every incident by reproducing the same root on a fresh database. If clean and incremental outputs differ, preserve both traces before modifying invalidation.

Symptom: stale answer after an edit#

• Inspect: Input revision events, dependency edges, key identity, equality decisions, verified_at, and changed_at.
• Likely hypotheses: An ambient read escaped tracking; a conditional edge was absent; key equality is wrong; backdating ignored observable output.
• Fix only after evidence: Model the missing input, repair edge recording or equality, then add the smallest differential regression sequence.

Symptom: almost everything reruns#

• Inspect: First red node, fanout by query kind, coarse keys, output equality, and edges to broad configuration inputs.
• Likely hypotheses: Granularity is too coarse, equality is conservative, or dependencies read a large aggregate unnecessarily.
• Fix only after evidence: Split a fact or key where measured avoided work exceeds added validation and memory cost.

Symptom: cache hit but diagnostics vanish or duplicate#

• Inspect: Whether diagnostics are returned, accumulated, globally emitted, and reconciled by producer identity.
• Likely hypotheses: Side effects occur only during execution or stale produced outputs were never removed.
• Fix only after evidence: Make diagnostics query-owned observable output and test first run, hit, correction, and deletion.

Symptom: nondeterministic identities#

• Inspect: Discovery order, hash iteration, intern insertion, duplicate occurrence order, and cross-session key derivation.
• Likely hypotheses: Process-local allocation leaked into semantic or persistent identity.
• Fix only after evidence: Canonicalize ordering or define stable keys; do not paper over the issue by sorting user-visible output alone.

Symptom: recursion overflow or cycle hang#

• Inspect: Active query stacks, wait-for graph, keys in the recurrence, thread ownership, and cancellation state.
• Likely hypotheses: Same-thread cycle detection is missing, or multiple jobs form a cross-thread wait cycle.
• Fix only after evidence: Add path-aware detection; implement fixed-point recovery only when language semantics justify it.

Symptom: deadlock under load#

• Inspect: Lock acquisition trace, job owner/waiter states, callbacks while locks are held, and revision-commit boundaries.
• Likely hypotheses: Lock-order inversion, waiting while owning a required lock, or cross-thread query cycles.
• Fix only after evidence: Establish one lock order or narrow critical sections, then model small schedules with Loom.

Symptom: panic or cancellation poisons later requests#

• Inspect: Active frames, in-progress markers, waiter notifications, partially installed values, and output ownership.
• Likely hypotheses: Cleanup is not RAII-safe or publication occurs before completion.
• Fix only after evidence: Make installation a commit point and test interruption at every state transition.

Symptom: persistent cache causes wrong answers#

• Inspect: Envelope versions, stable-key construction, compiler/target/options fingerprints, deserialization errors, and source identity.
• Likely hypotheses: Compatibility evidence is incomplete or corrupt entries are trusted.
• Fix only after evidence: Reject uncertain entries and fall back to recomputation; disk reuse is optional, correctness is not.

Symptom: memory grows without bound#

• Inspect: Value sizes, memo counts, produced-entity retention, interner growth, roots, snapshots, and eviction reachability.
• Likely hypotheses: Heavy values never evict, old outputs remain owned, or snapshots pin revisions.
• Fix only after evidence: Set explicit budgets and preserve enough metadata to keep post-eviction validation sound.

Symptom: benchmark result flips between runs#

• Inspect: Warm/cold state, process reuse, CPU frequency, background load, edit mix, sample distribution, and tracing overhead.
• Likely hypotheses: Noise dominates the effect or workloads differ.
• Fix only after evidence: Control conditions, increase samples, report uncertainty, and withdraw unsupported speed claims.

Production code-review checklist#

• [ ] Every answer-affecting read is tracked. Missing one can return a cleanly cached wrong answer.
• [ ] Root outputs define observability. Equality and clean-rebuild comparisons need a precise target, including diagnostics.
• [ ] Keys have documented scope and stability. Confusing database-local and persistent identity corrupts reuse.
• [ ] Hashing and equality are coherent. Equal keys must address one logical invocation.
• [ ] Published values are immutable or safely versioned. Mutation behind a memo bypasses dependency evidence.
• [ ] Conditional dependencies are replaced after successful execution. Stale extras waste work; missing current edges are unsound.
• [ ] verified_at and changed_at remain distinct. Validation freshness does not imply observable change.
• [ ] Backdating compares complete outputs. Ignoring spans, diagnostics, or produced entities can stop necessary propagation.
• [ ] Errors have deterministic ownership. Cache hits must neither erase nor duplicate failures.
• [ ] Frames unwind on every exit. Panic and cancellation cannot leak active-query state.
• [ ] Publication is atomic. Readers must never see a value without its complete dependencies and outputs.
• [ ] Input edits form coherent transactions. Related changes should expose one revision, not torn state.
• [ ] Accidental and semantic cycles use different policies. Recovery requires a language-level convergence argument.
• [ ] Wait-for cycles and lock order are addressed. Same-thread stack checks alone do not prevent parallel deadlock.
• [ ] Cancellation leaves no reusable partial work. Responsiveness must not compromise future correctness.
• [ ] Eviction distinguishes metadata from values. Memory control cannot turn absence into false validity.
• [ ] Persistence is versioned and defensive. Stale or hostile bytes must degrade to recomputation.
• [ ] Salsa code cites a tested version. Current APIs evolve; obsolete group and jar examples mislead maintainers.
• [ ] rustc is described as separate from Salsa. Shared concepts do not imply shared code or exact semantics.
• [ ] The clone favors safe, inspectable machinery. Production-style unsafe without measured need obscures learning and risk.
• [ ] Differential clean rebuilds cover edit sequences. Isolated unit tests rarely expose stale cross-revision state.
• [ ] Concurrency tests exercise failures, not only success. Panics, cancellation, and wait cycles define hard cases.
• [ ] Performance claims name workload and uncertainty. No architecture earns an unsupported universal speed claim.
• [ ] Comments explain invariants and proof obligations. Future changes need reasoning, not copy/paste recipes.

Designing performance experiments#

Questions before measurement#

Choose one question: “Does function-granularity inference reduce work for body edits?” is testable; “Are queries fast?” is not. State the expected mechanism and a result that would falsify it. Define workloads separately: clean build, no-change request, local body edit, public-signature edit, widespread configuration edit, IDE single-root request, and memory-pressure run. Use real projects plus controlled synthetic fanout.

Experimental controls#

• Pin compiler, dependencies, target, build mode, machine, power policy, and benchmark command.
• Decide whether filesystem and persistent caches are cold or warm; report both when relevant.
• Separate tracing builds from timing builds and validate that instrumentation does not dominate.
• Randomize or counterbalance variant order, warm up deliberately, and retain raw samples.
• Repeat complete edit sequences, not merely one cached call in a loop.
• Include the batch baseline and a clean rebuild correctness check after each sequence.

Metrics worth collecting#

• End-to-end latency at median and tail percentiles for user-visible roots.
• Query executions, validations, cache hits, backdates, and dependency edges by kind.
• First red node, transitive fanout, critical-path time, and available parallelism.
• Time in lookup, hashing, equality, validation, execution, waiting, serialization, and deserialization.
• Peak resident memory, retained value bytes, metadata bytes, eviction count, and recomputation after eviction.
• Lock wait time, duplicate computations, cancelled jobs, and waiter-cycle events.
• Persistent cache hit rate, bytes read/written, rejection reasons, and cross-session startup cost.
• Output hashes and diagnostics compared with clean databases; a fast wrong run is a failed experiment.

Reporting conclusions#

Show distributions and confidence intervals or robust spread, not one best number. Explain anomalies and negative results. A valid conclusion can be: “On this corpus, fine granularity saved inference executions after local edits but increased clean-build time and metadata memory.” Never promise that query-based compilation is inherently faster. It trades execution for tracking, validation, synchronization, and storage; workload and implementation decide the outcome.

Glossary for precise conversation#

• Accumulator: A Salsa mechanism associating collected outputs, such as diagnostics, with query execution and retrieval from a root.
• Active frame: Temporary execution context recording the current invocation and dependencies it reads.
• Ambient input: Answer-affecting state read outside the tracked model, such as environment variables or the filesystem.
• Backdating: Keeping an older changed_at after recomputation proves the complete observable output equal.
• Cache hit: Retrieval of a resident value; it is sound only after applicable validity checks.
• Cancellation: Cooperative termination of work without publishing partial state.
• Changed-at revision: Most recent logical revision at which an invocation's observable output changed.
• Clean rebuild: Evaluation in a new database from current inputs, used as the correctness oracle.
• Cycle: A dependency path that returns to an invocation already active or waiting in that path.
• Database: Owner of inputs, memoized values, dependency evidence, revisions, and runtime coordination.
• Dependency: Recorded fact that one invocation read another while producing its output.
• Durability: Optimization classification based on expected input change frequency; not permission to ignore changes.
• Dynamic dependency: Edge discovered from calls actually made during one execution.
• Early cutoff: Prevention of downstream execution after an upstream result is proven observably unchanged.
• Fingerprint: Compact digest used as evidence for identity or equality, with collision and stability assumptions made explicit.
• Fixed point: State unchanged by another analysis iteration; useful only with defined semantics and convergence.
• Green: Proven valid or observably unchanged for the revision under the engine's rules.
• Ingredient: Salsa-internal runtime unit backing a generated kind; an explanatory term, not a stable public contract.
• Input: Explicit externally supplied fact whose update participates in revision tracking.
• Interner: Canonical table mapping equal values to one compact handle within a defined scope.
• Invocation: One query kind paired with one key.
• Key: Value identifying which instance of a query is requested.
• Lattice: Ordered domain with joins used to reason about monotone accumulation and fixed points.
• Memo: Stored value plus the revisions, dependencies, outputs, and state needed to reason about reuse.
• Memoization: Reusing a result for a repeated key; cross-revision soundness requires more than memoization.
• Monotone: Moving only forward in a chosen information ordering, preventing oscillation in finite fixed-point iteration.
• On-demand: Computed because a requested root reaches it, rather than scheduled as an unconditional stage.
• Persistence: Reuse of validated artifacts across process lifetimes through versioned storage.
• Provider: In rustc, the function implementation selected for a query; it is not a Salsa term implying shared machinery.
• Publication: Atomic installation that makes a complete value and its evidence visible to readers.
• Pull validation: Checking validity when a root requests a value, recursively consulting dependencies as needed.
• Query: Named, keyed computation whose answer should depend only on modeled observations.
• Red: Known or conservatively assumed to have changed observably in the relevant revision.
• Revision: Logical edit epoch, not a timestamp or count of query executions.
• Root: Top-level request that forces the reachable portion of the query graph.
• Snapshot: Coherent read view tied to one revision or consistency boundary.
• Stable identity: Identifier designed to denote the same logical entity across a stated scope, potentially across sessions.
• Tracked struct: Salsa value with runtime-managed identity and tracked fields according to the current API's rules.
• Transaction: Group of related input updates published as one coherent revision.
• Validation: Proof process deciding whether old output can be reused under current inputs.
• Verified-at revision: Latest revision in which an invocation was checked and found valid.
• Wait-for graph: Directed relation among concurrent jobs showing which job is blocked on which other job.
• Work product: Reusable produced artifact such as object code; in rustc it has policies distinct from graph validity and query-value storage.

Preparing talks that teach reasoning#

Beginner audience: “Why remember the reasons?”#

• Promise: Explain keyed computations, dependency edges, and why same answer as a clean rebuild is the rule.
• Diagram: Draw a five-node pipeline, then replace it with a small hover-root graph and highlight only reached nodes.
• Demo: Edit a comment; show lex/parse activity and an unchanged semantic result stopping downstream work.
• Reasoning checkpoint: Ask the audience to predict whether reading an environment variable creates an edge.
• Avoid: Macro syntax, internal Salsa names, and speed guarantees. End with explicit inputs as the correctness boundary.

Intermediate audience: “How does reuse become proof?”#

• Promise: Derive memo fields, dynamic traces, red-green validation, equality, identity, and cycle handling.
• Diagram: Show each memo as {value, deps, verified_at, changed_at} across two revisions, with one backdated node.
• Demo: Toggle a conditional dependency, display edge replacement, then compare incremental output with a clean database.
• Reasoning checkpoint: Ask which equality fields are observable when diagnostics include source spans.
• Comparison slide: Put safe clone, Salsa 0.28.1, and rustc in separate columns; state prominently that rustc does not use Salsa.

Expert audience: “Where do the proof obligations break?”#

• Promise: Defend consistency, publication, identity, contention, eviction, persistence, and test strategy with evidence.
• Diagram: Combine revision transaction, per-key job states, lock order, and wait-for edges; mark cancellation commit boundaries.
• Demo: Inject cancellation and cache corruption, then show recovery and clean-rebuild equivalence; present raw performance distributions.
• Reasoning checkpoint: Invite a counterexample involving a green node whose heavy value was evicted.
• Disclosure: Label Salsa internals unstable, name the tested release, and separate measured outcomes from architectural hypotheses.

For every audience, provide a prediction worksheet rather than a repository to copy blindly. The transferable skill is reconstructing why reuse is safe.

Adversarial audience questions#

“Isn't this just memoization with extra bookkeeping?”

Memoization answers repeated keys under unchanged assumptions. An incremental engine records those assumptions, validates them across revisions, replaces dynamic edges, and may backdate equal recomputation. The bookkeeping is the evidence that makes cross-edit reuse sound.

“If clean rebuilds are the oracle, why not always rebuild?”

Sometimes you should. Queries are justified when demand and edit patterns make selective work valuable enough to pay tracking costs. Clean rebuilds remain the reference for tests even when they are too expensive for every interactive request.

“Can you guarantee my compiler gets faster?”

No. Granularity, fanout, workload, memory, synchronization, and validation cost determine results. I can offer a reproducible experiment and bounded claims, not an unsupported universal speedup.

“Why not mark everything dirty and stay simple?”

That is a correct baseline and often a useful fallback. Precision should be added only where measurements justify complexity, while differential tests preserve correctness.

“Does Salsa automatically notice files changing?”

No. Application code must observe files and set explicit inputs. The same applies to environment, target discovery, clocks, and network state.

“Which Salsa API should I memorize?”

Memorize the model, not signatures. For this text, check 0.28.1's input, interned, tracked, accumulator, and database documentation; on upgrade, compile against current examples because Salsa is experimental.

“So rustc is a large Salsa database?”

No. rustc has an independent engine with providers, TyCtxt query access, DepGraph, fingerprints, on-disk cache decisions, metadata, and work products. Similar vocabulary reflects shared problems, not shared implementation.

“Why not serialize every memo?”

Some keys are not stable, values may be cheap, formats evolve, validation can exceed recomputation, and bytes can be corrupt. Persistence needs selective policy and complete compatibility evidence.

“Can equality safely ignore formatting?”

Only if formatting cannot affect any observable consumer or diagnostic. Split representations when semantic equality and source-location equality serve different dependents; do not weaken equality by intuition alone.

“Why retain metadata when the value is evicted?”

Dependency and revision evidence may still avoid unnecessary downstream execution or guide safe recomputation. The design must represent absent residency explicitly; green does not mean bytes are currently in memory.

“A cycle is legal in my language, so why report it?”

Source recursion does not require query recursion. If the analysis itself is cyclic, define a domain, ordering, join, and convergence or recovery semantics. Otherwise reporting the accidental implementation cycle is safer.

“Can locks make a correct single-threaded engine parallel?”

Locks alone do not define snapshots, duplicate execution, waiter cycles, cancellation, panic publication, or output ownership. Parallelism is a separate design problem from incremental validity.

“Why build a clone when Salsa exists?”

A safe clone makes revisions, edges, and publication inspectable and teaches the algorithm. Use Salsa for maintained production machinery when it fits; do not present the clone as API-compatible or performance-equivalent.

“Why should I trust your benchmark?”

You should inspect the workload, raw samples, machine controls, correctness hashes, variance, and reproduction command. Trust should attach to evidence and scope, not to a polished percentage.

Final mastery project: TinyLox Live#

Build an incremental compiler and IDE core that supports file edits, diagnostics, hover, references, and object generation. Implement a safe learning engine first, then port one vertical slice to current Salsa and document the mapping.

Required capabilities#

1. Explicit inputs for source, project graph, flags, target, and relevant environment snapshots.
2. Justified file-, item-, or function-level keys for parse, signatures, resolution, inference, lowering, and codegen.
3. Dynamic dependency recording, separate revision fields, validation, edge replacement, and sound backdating.
4. Structured errors and query-owned diagnostics that survive hits and disappear when producers vanish.
5. Stable in-session identities, interned names, and a documented cross-session identity policy.
6. Useful direct and indirect cycle reports plus one separately justified monotone fixed-point analysis.
7. Atomic edit transactions, coherent snapshots, cancellation-safe frames, and per-key concurrent coordination.
8. Bounded memory with explicit eviction semantics and an optional defensively versioned persistence prototype.
9. Differential, property, fuzz, panic, cancellation, concurrency, and corruption tests.
10. A Salsa 0.28.1 comparison that uses current APIs, notes version risk, and contains no obsolete group/jar code.
11. A rustc comparison that clearly states rustc does not use Salsa and identifies rustc-specific layers.
12. A reproducible benchmark report containing both wins and costs without unsupported speed claims.

Submission evidence#

Include architecture diagrams, query and input inventories, three annotated red-green traces, one cycle trace, one cancellation trace, the clean-rebuild oracle, raw benchmark data, and a limitations document. Record a demo in which an evaluator chooses an unseen edit.

Rubric: 100 points#

• Correctness model — 20: Observable outputs and clean-rebuild equivalence are explicit; generated edit sequences pass after every step.
• Dependency and revision reasoning — 15: Traces correctly explain dynamic edges, both revision fields, execution, validation, and backdating.
• Compiler decomposition — 10: Granularity and identities fit demand patterns and are defended with fanout evidence.
• Errors, outputs, and cycles — 10: Diagnostics reconcile correctly; accidental cycles fail safely; fixed-point semantics are justified.
• Robust runtime — 15: Transactions, publication, cancellation, panic cleanup, snapshots, waits, and lock order have focused tests.
• Memory and persistence — 10: Eviction is sound; persisted entries are stable, versioned, validated, and safely rejected.
• Ecosystem accuracy — 10: Current Salsa usage carries a version caveat; clone, Salsa, and rustc remain clearly separate.
• Performance method — 5: Experiments are reproducible, scoped, statistically honest, and correctness checked.
• Communication — 5: Diagrams and demos teach prediction and evidence rather than encouraging copy/paste.

Automatic failure conditions are a reproducible stale answer, torn revision, silent accidental cycle, trusted corrupt cache entry, claim that rustc uses Salsa, or performance conclusion unsupported by the submitted data.

Final checklist#

• [ ] I can define the observable result and compare every edit step with a clean database.
• [ ] I can trace a root through hits, validation, execution, edge replacement, and backdating.
• [ ] I can explain why verified_at and changed_at answer different questions.
• [ ] I have modeled files, flags, targets, environment, generated data, errors, and diagnostics explicitly.
• [ ] I know the scope and stability promise of every key and fingerprint.
• [ ] I can justify granularity using demand, fanout, cost, identity, and measurements.
• [ ] I test equality over complete observable outputs, not convenient subsets.
• [ ] I distinguish source recursion, accidental query cycles, and semantic fixed points.
• [ ] I publish atomically and unwind safely after error, panic, and cancellation.
• [ ] I can explain snapshot consistency, lock order, wait cycles, and duplicate requests.
• [ ] I treat eviction and persistence as optional mechanisms that cannot weaken correctness.
• [ ] I run differential, property, fuzz, concurrency, and corruption tests where their risks apply.
• [ ] I verify Salsa's current API and state the tested version instead of copying old tutorials.
• [ ] I state without qualification that rustc does not use Salsa.
• [ ] I keep the safe clone, Salsa, and rustc architecturally distinct in code and explanation.
• [ ] I report performance by workload, samples, uncertainty, and tradeoffs—never unsupported speed claims.
• [ ] I can teach another engineer to predict evidence, not merely reproduce syntax.

Mastery is disciplined skepticism: model every observation, preserve every proof boundary, compare with a clean rebuild, and measure before claiming. A query engine is trustworthy not because it remembers, but because it can explain why remembering is still correct.