query-lang is an incremental computation engine: a database that caches the results of derived queries, records what each result was computed from, and recomputes only what a change actually affects. It is the model behind Rust's own salsa and rust-analyzer, distilled to a small, dependency-free core that is generic over the queries you define.
A compiler runs the same work over and over as source is edited — parse, resolve names, type-check, lower to IR. Most edits touch a fraction of that work, yet a naive compiler redoes all of it on every keystroke. 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. That is what keeps an editor responsive on a large project, and it is all query-lang does — it owns no compiler, no IR, no syntax.
MSRV is 1.85+ (Rust 2024 edition). no_std-compatible (needs only alloc), #![forbid(unsafe_code)], and wires no first-party dependency.
1.0.0 is the API freeze. The public surface is stable and follows Semantic Versioning — no breaking changes before2.0. Seedocs/API.mdfor the frozen-surface list and the SemVer promise, andCHANGELOG.md.
Three pieces, and the whole surface fits in your head:
- A
Systemis the definition of your queries: aKeytype that names a query, aValuetype it produces, and acomputefunction that derives one from the other. - A
Databaseholds theSystem, stores your inputs, and caches the derived results. You set inputs and get results; it handles caching, dependency tracking, and invalidation. - A
getresolves a query. From application code it returns a result; from inside acomputeit reads a dependency — and the engine records that edge automatically.
An input is any key whose value you set directly; every other key is derived through compute. One Key type names both, so a query reads an input and another query the same way.
Every resolution takes one of three paths, and the engine counts each in Stats:
| Path | When | Cost |
|---|---|---|
| Hit | The query was already verified at the current revision. | A revision compare; the cached value is returned without touching dependencies. |
| Validated | The query is stale, but no dependency actually changed its inputs. | The dependencies are re-examined; the cached value is reused. This is early cutoff. |
| Computed | A genuine miss, or a dependency that truly changed. | compute runs and the new value is cached. |
Early cutoff is the property that makes the engine worth its complexity: when a recomputed query produces the same value it had before, queries that depend on it are validated rather than recomputed, so a local edit does not cascade through the whole graph.
[dependencies]
query-lang = "1"Or from the terminal:
cargo add query-langMSRV: Rust 1.85 (Rust 2024 edition).
An input, a query that parses it, and a query that squares the result. Editing the input recomputes the chain; asking again with no edit is a free hit.
use query_lang::{Database, System, QueryError};
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
enum Key {
Source, // an input: the raw value
Parsed, // = Source
Squared, // = Parsed * Parsed
}
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), // default if the input was never set
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 a set input; Parsed and Squared ran
// Ask again with no edit: a cache hit, nothing recomputes.
assert_eq!(db.get(&Key::Squared)?, 144);
assert_eq!(db.stats().hits, 1);
# Ok::<(), QueryError>(())The engine clones a value to hand it back and compares old against new for early cutoff. Wrap a large result in an Arc so a clone bumps a refcount rather than copying, and the comparison stays cheap:
use std::sync::Arc;
use query_lang::{Database, System, QueryError};
struct Ast;
impl System for Ast {
type Key = u32;
type Value = Arc<Vec<String>>; // a big parsed tree, shared not copied
fn compute(&self, db: &Database<Self>, file: &u32) -> Result<Arc<Vec<String>>, QueryError> {
// ... parse file `file` into tokens ...
Ok(Arc::new(vec![format!("tokens-of-{file}")]))
}
}
let db = Database::new(Ast);
let a = db.get(&1)?;
let b = db.get(&1)?; // second call is a hit
assert!(Arc::ptr_eq(&a, &b)); // and hands back the very same allocation
# Ok::<(), QueryError>(())Two runnable examples ship in examples/:
- Spreadsheet — cells are inputs, formulas are derived queries; editing a cell recomputes only the formulas that transitively read it.
cargo run --example spreadsheet
- Build pipeline — a miniature compiler front end (
source → tokens → symbol count → report) that shows early cutoff: reformatting the source reruns only the tokenizer; the rest is reused.cargo run --example build_pipeline
The engine's own per-query overhead is a BTreeMap lookup and a revision compare. The benchmarks in benches/ exercise the three resolution paths directly (Windows x86_64 and Linux/WSL2, Rust stable, release profile):
| Benchmark | What it measures | Time |
|---|---|---|
chain/cache_hit |
Re-resolving an already-current query (a hit). | ~19–38 ns |
chain/cold_build/256 |
First resolution of a 256-deep query chain. | ~55 µs |
chain/edit_rebuild/256 |
Editing the leaf input, rebuilding a 256-deep chain. | ~46 µs |
wide/edit_one_of/256 |
Editing one input in a 256-wide sum (one branch recomputes, 255 validate). | ~42 µs |
Run them yourself:
cargo bench --bench benchCriterion writes per-benchmark reports to target/criterion/. Numbers vary by CPU; use the trend across runs, not a single absolute.
- Dependencies are recorded, not declared. A query's dependency set is whatever it read on its last run, so a query that branches on its inputs is tracked exactly — it depends on the branch it actually took, and nothing more.
- Revisions, not value diffs, drive validation. Validity is a single integer compare regardless of how large a cached value is; values are compared only once, at the point a query recomputes, to decide early cutoff.
- Single-threaded by design. Resolution walks a shared cache and a dependency stack through interior mutability — correct and allocation-light on one thread, with no atomic overhead. Run independent databases on separate threads for parallelism.
- Cycles are an error, never a panic or a hang. A query that depends on itself resolves to
QueryError::Cycle; the resolution chain unwinds cleanly and the database stays usable. no_stdand dependency-free. The engine uses onlyallocand wires no first-party crate — keys live in aBTreeMap, so the requirement isKey: Ordrather than a hashing dependency.
The suite runs on Windows, Linux (WSL2 Ubuntu), and macOS through the CI matrix, on stable and the 1.85 MSRV:
cargo test # unit + integration + doctests
cargo test --all-features # adds serde coverage
cargo clippy --all-targets --all-features -- -D warnings
cargo bench --bench benchProperty tests in tests/proptests.rs hold the engine to its core invariants over a wide space of edit sequences: an incrementally maintained result always equals a from-scratch computation, the revision is monotonic, and an unchanged input never recomputes. Every rust example in this README and in docs/API.md is compiled and run as a doctest, so the published examples cannot drift from the API.
- Linux (x86_64, aarch64)
- macOS (x86_64, Apple Silicon)
- Windows (x86_64)
The engine uses no operating-system facilities and no platform-specific code; behaviour is identical on every target.
See dev/DIRECTIVES.md for engineering standards and the definition of done. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.
Licensed under either of
- Apache License, Version 2.0 — LICENSE-APACHE
- MIT License — LICENSE-MIT
at your option.