Struct Database 

pub struct Database<S: System> { /* private fields */ }

An incremental query database: the store of inputs and the cache of derived results, with automatic dependency tracking and invalidation.

This is the engine. A consumer defines its queries once by implementing System, hands the system to new, seeds the base facts with set, and asks for results with get. Everything between — remembering what each query read, noticing when an input makes a cached result stale, recomputing only what actually changed — is the database’s job.

How it stays correct and fast

The database holds a Revision clock that advances by one each time an input takes a new value. Every cached query records two stamps: when it was last verified against the clock, and when its value last changed. Asking for a query takes one of three paths, counted in Stats:

• Hit — the query was already verified at the current revision; its value is returned without touching its dependencies.
• Validated — the query is stale, but re-examining its recorded dependencies shows none of them changed since the query was last verified, so the cached value is reused. When a dependency did recompute but to the same value, its change stamp stays old and dependents are validated rather than recomputed. This early cutoff is what stops a local edit from cascading through the whole graph.
• Computed — a genuine miss, or a dependency that truly changed; the query’s compute runs and the new value is cached.

Because dependencies are recorded during computation rather than declared up front, a query that branches on its inputs is tracked exactly: it depends on what it actually read on the last run, and nothing more.

Single-threaded by design

A Database is not Sync: query resolution walks a shared cache and a dependency stack through interior mutability, which is correct and allocation- light on one thread and carries no atomic overhead. Drive one database from one thread; run independent databases on separate threads for parallelism.

Examples

A three-layer computation — an input, a query over it, and a query over that — recomputes only along the path an edit touches:

use query_lang::{Database, System, QueryError};

#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
enum Key {
    Width,       // an input
    Doubled,     // = Width * 2
    Labeled,     // = "w=" + Doubled
}

struct Layout;
impl System for Layout {
    type Key = Key;
    type Value = String;
    fn compute(&self, db: &Database<Self>, key: &Key) -> Result<String, QueryError> {
        match key {
            Key::Width => Ok("0".into()),
            Key::Doubled => {
                let w: i64 = db.get(&Key::Width)?.parse().unwrap_or(0);
                Ok((w * 2).to_string())
            }
            Key::Labeled => Ok(format!("w={}", db.get(&Key::Doubled)?)),
        }
    }
}

let mut db = Database::new(Layout);
db.set(Key::Width, "10".into());
assert_eq!(db.get(&Key::Labeled)?, "w=20");
assert_eq!(db.stats().computed, 2); // Width is a set input; Doubled and Labeled ran

// Re-ask without changing anything: a free hit, no recomputation.
assert_eq!(db.get(&Key::Labeled)?, "w=20");
assert_eq!(db.stats().hits, 1);

Implementations

impl<S: System> Database<S>

pub fn new(system: S) -> Self

Create an empty database for the given query system.

The database starts at the initial revision with no inputs and an empty cache. Seed inputs with set before asking for derived queries.

Examples

use query_lang::{Database, System, QueryError};

struct S;
impl System for S {
    type Key = u32;
    type Value = u32;
    fn compute(&self, _db: &Database<Self>, k: &u32) -> Result<u32, QueryError> { Ok(*k) }
}

let db = Database::new(S);
assert_eq!(db.stats().total(), 0);

pub fn set(&mut self, key: S::Key, value: S::Value)

Set an input to a value, advancing the revision if the value changed.

This is the only way a value enters the database from outside. Once set, a key is an input: get returns the stored value directly and compute is never called for it. Setting the same value a key already holds is a no-op — the revision does not advance, and nothing that depends on the input is invalidated, so re-feeding unchanged facts costs nothing downstream. Setting a different value advances the revision, which is what later marks dependent queries stale.

Setting a key that previously held a derived (computed) value promotes it to an input and discards the stale cached result.

Taking &mut self is deliberate: mutating an input is the one operation that can invalidate cached results, so it is kept distinct from the shared &self reads that get performs.

Examples

use query_lang::{Database, System, QueryError};

struct Echo;
impl System for Echo {
    type Key = u32;
    type Value = i64;
    fn compute(&self, db: &Database<Self>, k: &u32) -> Result<i64, QueryError> {
        Ok(db.get(&(k + 1))? + 1) // reads input at k+1
    }
}

let mut db = Database::new(Echo);
db.set(1, 41);
let r0 = db.revision();

db.set(1, 41);              // same value
assert_eq!(db.revision(), r0); // no change, clock still

db.set(1, 99);              // new value
assert!(db.revision() > r0);   // clock advanced

pub fn get(&self, key: &S::Key) -> Result<S::Value, QueryError>

Resolve a query to its value, computing and caching it as needed.

If key is a set input, its value is returned directly. Otherwise the query is derived: a valid cached value is reused (a hit or an early-cutoff validation), and only a real miss or a genuinely changed dependency runs compute. Call this both from application code and, from inside a compute, to read the queries a result depends on — reads through get are exactly what the engine records as dependencies.

Errors

Returns QueryError::Cycle if resolving key requires a value that is still being computed further up the call chain — that is, if the query graph has a cycle.

Examples

use query_lang::{Database, System, QueryError};

struct Fib;
impl System for Fib {
    type Key = u64;
    type Value = u64;
    fn compute(&self, db: &Database<Self>, n: &u64) -> Result<u64, QueryError> {
        // Memoized Fibonacci: each fib(n) is computed once and cached.
        if *n < 2 { return Ok(*n); }
        Ok(db.get(&(n - 1))?.wrapping_add(db.get(&(n - 2))?))
    }
}

let db = Database::new(Fib);
assert_eq!(db.get(&50)?, 12586269025);

pub const fn revision(&self) -> Revision

The current revision of the database.

Advances by one each time set gives an input a new value. Useful for asserting in tests that an operation did (or did not) change any input, and for correlating cache behaviour with input edits in logs.

pub fn stats(&self) -> Stats

A snapshot of the cumulative resolution counters.

See Stats for what each counter means. Snapshot before and after an operation and subtract to measure exactly what that operation cost.

Examples

use query_lang::{Database, System, QueryError};

struct S;
impl System for S {
    type Key = u32;
    type Value = u32;
    fn compute(&self, _db: &Database<Self>, k: &u32) -> Result<u32, QueryError> { Ok(*k) }
}

let db = Database::new(S);
let before = db.stats();
let _ = db.get(&5)?;
let after = db.stats();
assert_eq!(after.computed - before.computed, 1);

pub const fn system(&self) -> &S

A shared reference to the query system backing this database.

Trait Implementations

impl<S: System> Debug for Database<S>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.