v0.2.0 — Foundation

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.

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.

# 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:

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

[dependencies]
query-lang = "0.2"

MSRV: Rust 1.85.

Documentation

• README
• API Reference
• CHANGELOG

---

Full diff: v0.1.0...v0.2.0.
Changelog: CHANGELOG.md.