query-lang 1.0.0

The model

Three pieces, and the whole surface fits in your head:

• A System is the definition of your queries: a Key type that names a query, a Value type it produces, and a compute function that derives one from the other.
• A Database holds the System, stores your inputs, and caches the derived results. You set inputs and get results; it handles caching, dependency tracking, and invalidation.
• A get resolves a query. From application code it returns a result; from inside a compute it 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:

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.

Installation

[dependencies]
query-lang = "1"

Or from the terminal:

cargo add query-lang

MSRV: Rust 1.85 (Rust 2024 edition).

Quick start

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>(())

Values that are expensive to clone

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>(())

Examples

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
  

Performance

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

Run them yourself:

cargo bench --bench bench

Criterion writes per-benchmark reports to target/criterion/. Numbers vary by CPU; use the trend across runs, not a single absolute.

Design notes

• 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_std and dependency-free. The engine uses only alloc and wires no first-party crate — keys live in a BTreeMap, so the requirement is Key: Ord rather than a hashing dependency.

Testing

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 bench

Property 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.

Cross-platform support

• 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.

Contributing

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.