query_lang/
system.rs

1//! The trait a consumer implements to define its derived queries.
2
3use crate::database::Database;
4use crate::error::QueryError;
5
6/// The definition of a query system: how every derived query is computed.
7///
8/// A consumer implements `System` once to describe an entire incremental
9/// computation. It ties together three things: the [`Key`](Self::Key) that names
10/// a query, the [`Value`](Self::Value) a query produces, and the
11/// [`compute`](Self::compute) function that turns one into the other. The
12/// [`Database`](crate::Database) supplies everything else — caching, dependency
13/// tracking, and invalidation — and calls `compute` only when it must.
14///
15/// # Keys, inputs, and derived queries
16///
17/// A single `Key` type names every query in the system, usually an `enum` with
18/// one variant per kind of query (`Key::Source(FileId)`, `Key::Ast(FileId)`,
19/// `Key::TypeOf(DefId)`, …). A key is an **input** once its value is placed into
20/// the database with [`Database::set`](crate::Database::set); every other key is
21/// **derived**, and its value comes from `compute`. The same key type covers
22/// both, so a query reads an input and another derived query the same way —
23/// through [`Database::get`](crate::Database::get) — and the engine records the
24/// dependency either way.
25///
26/// # The contract on `compute`
27///
28/// `compute` must be a pure function of the queries it reads. It may read inputs
29/// and other derived queries through the `db` handle it is given, and it must
30/// read *every* value it depends on through that handle — a value pulled in from
31/// outside (a global, the clock, the filesystem read directly) is invisible to
32/// the engine and will not trigger invalidation when it changes, leaving the
33/// cache serving stale results. Given the same inputs, `compute` must return the
34/// same value; the engine relies on that to reuse cached results safely.
35///
36/// # Requirements on the associated types
37///
38/// - `Key: Clone + Ord` — keys are stored in the dependency graph and the memo
39///   table (a `BTreeMap`, so `Ord` rather than `Hash`; this keeps the engine
40///   `no_std`- and dependency-free). Cloning a key should be cheap; prefer small
41///   copyable keys or interned identifiers over owned strings.
42/// - `Value: Clone + Eq` — the engine clones a value to hand it back and compares
43///   the new value against the old one to decide whether a recomputation actually
44///   changed anything. That comparison is *early cutoff*: when a recomputed value
45///   equals its predecessor, queries that depend on it are not recomputed. Make
46///   values cheap to clone and compare — wrap large results in an
47///   [`Arc`](std::sync::Arc) so a clone bumps a refcount rather than copying.
48///
49/// # Examples
50///
51/// A two-layer system: an input number, and a derived query that squares it.
52///
53/// ```
54/// use query_lang::{Database, System, QueryError};
55///
56/// // One enum names every query. `Base` values are set as inputs; `Squared`
57/// // values are computed from a `Base`.
58/// #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
59/// enum Key {
60///     Base,
61///     Squared,
62/// }
63///
64/// struct Arithmetic;
65/// impl System for Arithmetic {
66///     type Key = Key;
67///     type Value = i64;
68///     fn compute(&self, db: &Database<Self>, key: &Key) -> Result<i64, QueryError> {
69///         match key {
70///             Key::Base => Ok(0), // a default if `Base` was never set as an input
71///             Key::Squared => {
72///                 let base = db.get(&Key::Base)?;
73///                 Ok(base * base)
74///             }
75///         }
76///     }
77/// }
78///
79/// let mut db = Database::new(Arithmetic);
80/// db.set(Key::Base, 9);
81/// assert_eq!(db.get(&Key::Squared)?, 81);
82/// # Ok::<(), QueryError>(())
83/// ```
84pub trait System: Sized {
85    /// The identifier that names a query. Usually an `enum` with one variant per
86    /// kind of query. Must be cheap to clone and totally ordered.
87    type Key: Clone + Ord;
88
89    /// The value a query produces. Cloned to return and compared for early
90    /// cutoff, so it should be cheap to clone and compare (wrap large payloads in
91    /// an [`Arc`](std::sync::Arc)).
92    type Value: Clone + Eq;
93
94    /// Compute the value of a derived query.
95    ///
96    /// The engine calls this only on a cache miss or when a dependency has
97    /// genuinely changed — never for a key that is currently a set input, and
98    /// never when a cached value is still valid. Read every dependency through
99    /// `db` so the engine can track it; see the [trait
100    /// contract](Self#the-contract-on-compute).
101    ///
102    /// # Errors
103    ///
104    /// Returns [`QueryError::Cycle`] if resolving a dependency closes a cycle
105    /// back onto a query still being computed. Propagate it with `?`; do not
106    /// attempt to recover from it inside `compute`, as the whole resolution
107    /// chain is already unwinding.
108    fn compute(&self, db: &Database<Self>, key: &Self::Key) -> Result<Self::Value, QueryError>;
109}
query_lang/system.rs

query_lang/
system.rs
