# query-lang v0.2.0 — The Incremental Engine
**The core, and the hard part of the roadmap.** v0.2.0 turns the scaffold into a
working incremental computation engine: a query database that caches derived
results, records what each result was computed from, and recomputes only what a
change actually affects. The surface is deliberately small — one trait, one
database, and three supporting types — and it is generic over the queries a
consumer defines, so the engine binds to no concrete compiler and wires no
first-party dependency.
## What is query-lang?
An incremental computation engine, the model behind Rust's own `salsa` and
rust-analyzer, distilled to a small dependency-free core. A compiler runs the
same work over and over as source is edited — parse, resolve names, type-check,
lower to IR — and most edits touch only a fraction of it. The query model turns
each step into a memoized function whose dependencies are tracked as it runs;
when an input changes, the engine invalidates only the queries that transitively
read it and reuses everything else. query-lang is that engine and nothing more —
it owns no compiler, no IR, no syntax. It is one of the FEAT-tier crates of the
`-lang` language-construction family.
## What's new in 0.2.0
### `System` — the query definition
A consumer implements `System` once to describe an entire incremental
computation: a `Key` type that names a query, a `Value` type it produces, and a
`compute` function that derives one from the other. Reading a dependency through
the database handle is what the engine records as the dependency graph — nothing
is declared up front, so a query that branches on its inputs depends only on the
branch it actually took.
```rust
use query_lang::{Database, System, QueryError};
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
enum Key { Source, Parsed, Squared }
struct Pipeline;
impl System for Pipeline {
type Key = Key;
type Value = i64;
fn compute(&self, db: &Database<Self>, key: &Key) -> Result<i64, QueryError> {
match key {
Key::Source => Ok(0),
Key::Parsed => Ok(db.get(&Key::Source)?),
Key::Squared => { let n = db.get(&Key::Parsed)?; Ok(n * n) }
}
}
}
```
### `Database<S>` — the engine
The database stores inputs and caches derived results. `set` seeds an input and
`get` resolves a query, computing and caching it as needed. Every resolution
takes one of three paths — a **hit** (already current), a **validation** (stale
but no input actually changed, so the cached value is reused), or a
**recomputation** — and only the last runs `compute`.
```rust
# use query_lang::{Database, System, QueryError};
# #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
# enum Key { Source, Parsed, Squared }
# struct Pipeline;
# impl System for Pipeline {
# type Key = Key;
# type Value = i64;
# fn compute(&self, db: &Database<Self>, key: &Key) -> Result<i64, QueryError> {
# match key {
# Key::Source => Ok(0),
# Key::Parsed => Ok(db.get(&Key::Source)?),
# Key::Squared => { let n = db.get(&Key::Parsed)?; Ok(n * n) }
# }
# }
# }
let mut db = Database::new(Pipeline);
db.set(Key::Source, 12);
assert_eq!(db.get(&Key::Squared)?, 144);
assert_eq!(db.stats().computed, 2); // Source is an input; Parsed and Squared ran
assert_eq!(db.get(&Key::Squared)?, 144);
assert_eq!(db.stats().hits, 1); // no edit — a free hit
# Ok::<(), QueryError>(())
```
### Early cutoff — the property that pays for the engine
When a query recomputes to the same value it already had, its change stamp stays
old, so queries that depend on it are *validated* rather than recomputed. A local
edit that leaves an intermediate result unchanged stops there instead of
cascading through the whole graph. The `build_pipeline` example makes this
concrete: reformatting source reruns the tokenizer, sees the same tokens, and
reuses the symbol count and the report.
### `Revision` and `Stats` — validation and observability
`Revision` is the monotonic clock that advances on every real input change;
validity is decided by comparing revisions, a single integer compare regardless
of how large a cached value is. `Stats` counts the three resolution paths
(`computed`, `validated`, `hits`) so a caller can measure exactly what an
operation cost — and a test can assert that an edit recomputed only what it
should.
### `QueryError` — contained failure
A query graph must be acyclic. When it is not, the query that closes the cycle
resolves to `QueryError::Cycle`; the resolution chain unwinds cleanly and the
database stays usable, never a panic and never an unbounded recursion. The type
is `#[non_exhaustive]`, so new resolution failure modes can be added later
without breaking a `match`.
### Examples, benchmarks, and property tests
Two runnable examples ship: `spreadsheet` (cells as inputs, formulas as derived
queries, edits recomputing only affected formulas) and `build_pipeline` (a
miniature `source → tokens → symbol count → report` front end demonstrating early
cutoff). Criterion benchmarks cover the hit, cold-build, and recompute paths.
Property tests hold the engine to its core invariants: an incrementally
maintained result always equals a from-scratch computation, the revision is
monotonic, and an unchanged input never recomputes.
### Dependency wiring — none, by design
No first-party dependency is wired, and none is planned. A query engine is a
generic caching and invalidation machine; coupling it to one concrete IR would
bind it to a single layer and pull in a dependency it never reads. Keys live in a
`BTreeMap`, so the only requirement is `Key: Ord` — no hashing dependency, and
the crate stays `no_std`-compatible on `alloc` alone.
## Breaking changes
**None.** v0.1.0 exposed no public API; everything in 0.2.0 is new surface.
## Verification
Run on Windows x86_64 and Linux (WSL2 Ubuntu), Rust stable and the 1.85 MSRV;
identical commands run in the configured CI matrix:
```bash
cargo fmt --all -- --check
cargo clippy --all-targets -- -D warnings
cargo clippy --all-targets --all-features -- -D warnings
cargo clippy --no-default-features --all-targets -- -D warnings
cargo test
cargo test --all-features
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
cargo build --examples
cargo build --no-default-features
cargo +1.85 build --all-features
cargo deny check
cargo audit
```
All green. Counts at this tag:
- Default features: 28 unit + 6 integration + 4 property + 31 doctests. The
doctests include every `rust` example in `README.md` and `docs/API.md`, wired
into `cargo test` so the published examples cannot drift from the API.
- `--all-features`: adds 3 `serde` serialization tests exercising the `Revision`
and `Stats` derivations.
Benchmark baselines (release profile): re-resolving an already-current query is a
~19–38 ns cache hit; a first build of a 256-deep query chain is ~55 µs; editing
the leaf and rebuilding that chain is ~46 µs; editing one input of a 256-wide sum
recomputes one branch and validates the other 255 in ~42 µs. The engine's own
per-query overhead is a `BTreeMap` lookup and a revision compare — the figures
are dominated by that bookkeeping, since the benchmarked queries do trivial work.
## What's next
- **1.0.0 — API freeze.** Freeze the 0.2.0 surface as the 1.0 contract, mark
`docs/API.md` stable with a SemVer promise, and confirm the full test and
benchmark suite on all three platforms. Interned-key helpers, durability tiers
(marking some inputs as rarely-changing to skip revalidation), and a
query-trace/debug hook are additive later-minor work, not a 1.0 requirement.
## Installation
```toml
[dependencies]
query-lang = "0.2"
```
MSRV: Rust 1.85.
## Documentation
- [README](https://github.com/jamesgober/query-lang/blob/main/README.md)
- [API Reference](https://github.com/jamesgober/query-lang/blob/main/docs/API.md)
- [CHANGELOG](https://github.com/jamesgober/query-lang/blob/main/CHANGELOG.md)
---
**Full diff:** [`v0.1.0...v0.2.0`](https://github.com/jamesgober/query-lang/compare/v0.1.0...v0.2.0).
**Changelog:** [`CHANGELOG.md`](https://github.com/jamesgober/query-lang/blob/main/CHANGELOG.md#020---2026-07-08).