Skip to main content

decl_lang/qengine/
db.rs

1//! The incremental, memoized query core of the query engine (qengine/DESIGN.md);
2//! the faithful port of decl-ts/src/qengine/db.ts.
3//
4//! A demand-driven database of queries. Some keys are *inputs* (set from
5//! outside); the rest are *derived* — computed by a resolver-supplied function
6//! that reads other queries through the database, so its dependencies are
7//! recorded automatically. Results are memoized with a global revision and two
8//! stamps per entry, giving early cutoff on both axes. The verify cutoff: if
9//! none of an entry's dependencies changed since it was verified, it is reused
10//! without recomputing. The value cutoff: a recompute that yields an equal
11//! value does not advance the entry's changed-revision, so its dependents cut
12//! off in turn. This is Salsa/Adapton-shaped, generic over the value it stores,
13//! and
14//! independent of the decl language; the decl layer (compiled expressions as
15//! derived queries) is built on top.
16use crate::semantics::{value_eq, EvalErr, Fail, Value};
17use rustc_hash::FxHashMap;
18use std::cell::{Cell, RefCell};
19
20/// a query key — an opaque string; the decl layer defines the grammar of keys
21pub type Key = String;
22
23/// the failure a query may produce: a dependency cycle the core itself detects
24/// (§7.6/§9.3), or a failure raised by a compute (a value-layer error/taint)
25pub enum DbErr {
26    /// a query that (transitively) reads itself, with the path it walked
27    Cycle(Vec<Key>),
28    /// a failure raised by a compute (a value-layer error or taint)
29    Fail(Fail),
30}
31/// a query's result: its value or a [`DbErr`]
32pub type DResult = Result<Value, DbErr>;
33
34/// compute a derived query's value, reading other queries through the database
35pub type Compute = Box<dyn Fn(&Db) -> DResult>;
36/// map a derived key to its compute; `None` for an unknown key
37pub type Resolve = Box<dyn Fn(&str) -> Option<Compute>>;
38
39struct Entry {
40    value: Value,
41    deps: Vec<Key>,
42    changed_rev: u64,  // last revision the value actually changed
43    verified_rev: u64, // last revision the value was confirmed current
44}
45
46/// a query currently (re)computing: its key, and the deps it reads meanwhile
47struct Frame {
48    key: Key,
49    deps: RefCell<Vec<Key>>,
50}
51
52/// the incremental, memoized query database (see the module comment)
53pub struct Db {
54    rev: Cell<u64>,
55    memo: RefCell<FxHashMap<Key, Entry>>,
56    inputs: RefCell<FxHashMap<Key, Value>>,
57    input_rev: RefCell<FxHashMap<Key, u64>>,
58    resolve: Resolve,
59    // the queries currently (re)computing, innermost last — dependency capture
60    // and cycle detection
61    stack: RefCell<Vec<Frame>>,
62}
63
64impl Db {
65    /// a fresh database whose derived keys are computed by `resolve`
66    pub fn new(resolve: Resolve) -> Db {
67        Db {
68            rev: Cell::new(0),
69            memo: RefCell::new(FxHashMap::default()),
70            inputs: RefCell::new(FxHashMap::default()),
71            input_rev: RefCell::new(FxHashMap::default()),
72            resolve,
73            stack: RefCell::new(Vec::new()),
74        }
75    }
76
77    /// Drop memoized results when the owning value context advances.
78    pub fn clear(&self) {
79        self.memo.borrow_mut().clear();
80        self.rev.set(self.rev.get() + 1);
81    }
82
83    /// the current revision (advances when an input changes)
84    pub fn revision(&self) -> u64 {
85        self.rev.get()
86    }
87
88    /// Set an input's value. If it differs from the current value the revision
89    /// advances and dependents recompute on demand; an equal value is a no-op.
90    pub fn set_input(&self, key: &str, value: Value) {
91        if let Some(old) = self.inputs.borrow().get(key) {
92            if value_eq(old, &value) {
93                return;
94            }
95        }
96        self.rev.set(self.rev.get() + 1);
97        self.inputs.borrow_mut().insert(key.to_string(), value);
98        self.input_rev
99            .borrow_mut()
100            .insert(key.to_string(), self.rev.get());
101    }
102
103    /// read a query's value, recording it as a dependency of the caller (if any)
104    pub fn query(&self, key: &str) -> DResult {
105        if let Some(top) = self.stack.borrow().last() {
106            top.deps.borrow_mut().push(key.to_string());
107        }
108        self.evaluate(key)
109    }
110
111    /// bring a query up to date and return its value, recording no dependency
112    fn evaluate(&self, key: &str) -> DResult {
113        if let Some(v) = self.inputs.borrow().get(key) {
114            return Ok(v.clone());
115        }
116        let cur = self.rev.get();
117        // already current, or memoized with a known set of deps to re-verify
118        let (has_memo, verified, deps) = {
119            let memo = self.memo.borrow();
120            match memo.get(key) {
121                Some(m) if m.verified_rev == cur => return Ok(m.value.clone()),
122                Some(m) => (true, m.verified_rev, m.deps.clone()),
123                None => (false, 0, Vec::new()),
124            }
125        };
126        if has_memo && self.deps_unchanged(&deps, verified)? {
127            // verify cutoff: no dependency changed since this was verified
128            if let Some(m) = self.memo.borrow_mut().get_mut(key) {
129                m.verified_rev = cur;
130            }
131            return Ok(self.memo.borrow().get(key).unwrap().value.clone());
132        }
133        self.recompute(key, has_memo)
134    }
135
136    fn deps_unchanged(&self, deps: &[Key], verified: u64) -> Result<bool, DbErr> {
137        for d in deps {
138            self.evaluate(d)?; // bring the dependency current (may recompute it)
139            if self.changed_rev_of(d) > verified {
140                return Ok(false);
141            }
142        }
143        Ok(true)
144    }
145
146    fn recompute(&self, key: &str, has_prev: bool) -> DResult {
147        if self.stack.borrow().iter().any(|f| f.key == key) {
148            let mut cyc: Vec<Key> = self.stack.borrow().iter().map(|f| f.key.clone()).collect();
149            cyc.push(key.to_string());
150            return Err(DbErr::Cycle(cyc));
151        }
152        let compute = (self.resolve)(key).ok_or_else(|| {
153            DbErr::Fail(Fail::Eval(EvalErr {
154                msg: format!("no such query: {key}"),
155                code: None,
156            }))
157        })?;
158        self.stack.borrow_mut().push(Frame {
159            key: key.to_string(),
160            deps: RefCell::new(Vec::new()),
161        });
162        let result = compute(self);
163        let frame = self.stack.borrow_mut().pop().unwrap();
164        let value = result?; // propagate after popping the frame
165        let deps = frame.deps.into_inner();
166        // value cutoff: an equal recompute keeps the old changed-revision, so
167        // dependents that only read this query need not recompute
168        let cur = self.rev.get();
169        let prev_changed = if has_prev {
170            self.memo
171                .borrow()
172                .get(key)
173                .filter(|m| value_eq(&value, &m.value))
174                .map(|m| m.changed_rev)
175        } else {
176            None
177        };
178        let changed_rev = prev_changed.unwrap_or(cur);
179        self.memo.borrow_mut().insert(
180            key.to_string(),
181            Entry {
182                value: value.clone(),
183                deps,
184                changed_rev,
185                verified_rev: cur,
186            },
187        );
188        Ok(value)
189    }
190
191    fn changed_rev_of(&self, key: &str) -> u64 {
192        if let Some(r) = self.input_rev.borrow().get(key) {
193            return *r;
194        }
195        self.memo
196            .borrow()
197            .get(key)
198            .map(|m| m.changed_rev)
199            .unwrap_or(0)
200    }
201}