Skip to main content

datumesh_engine/
engine.rs

1//! [`Engine`], [`EngineBuilder`] and [`Answer`].
2
3use std::borrow::Cow;
4use std::collections::HashMap;
5use std::fmt;
6use std::path::PathBuf;
7use std::sync::{Arc, Mutex};
8
9use datumesh_core::{
10    lexical, Cell, CellRef, Evaluation, Fault, FunctionDescriptor, KeyDoc, Resolver, Scalar, SigningKey,
11};
12use datumesh_store::Store;
13
14use crate::cache::{Cache, Parsed};
15use crate::check::{check_args, check_no_slice};
16use crate::clock::{Clock, SystemClock};
17use crate::error::{ConfigError, EngineError, EvalError, StoreError};
18use crate::eval::{is_instant, parse_stored, Done, Req};
19use crate::memo::Memo;
20use crate::runtime::Runtime;
21
22/// The default depth limit: frames on the evaluation stack.
23pub const DEFAULT_DEPTH_LIMIT: usize = 10_000;
24/// The default fuel of a request: runtime steps plus input reads.
25pub const DEFAULT_FUEL: u64 = 10_000_000;
26/// The default work limit of a request, as a multiple of its fuel.
27pub const DEFAULT_WORK_FACTOR: u64 = 16;
28/// The default memo capacity, in entries.
29pub const DEFAULT_MEMO_CAPACITY: usize = 1_000_000;
30
31/// The answer to "the value of this cell as of A".
32#[non_exhaustive]
33#[derive(Clone, Debug, PartialEq, Eq)]
34pub enum Answer {
35    /// The receipt that answers, canonical JSON text: for a stored cell the publisher's
36    /// receipt as the store holds it; for a computed cell one signed by the engine.
37    Receipt(Vec<u8>),
38    /// Nothing answers as of A, and no receipt is given.
39    ///
40    /// `fault: None`: the function is unknown then, a stored cell has no version answering
41    /// then, or a computed cell reads such an input. `fault: Some(code)`: the cell is a
42    /// computed cell whose evaluation faulted (SPEC 15.12): it has no value, deterministically
43    /// (the envelope's `fault`, SPEC 5.5). Since 0.3.0 the variant carries `fault`.
44    NotCovered {
45        /// The evaluation fault, if the cell has no value because of one.
46        fault: Option<Fault>,
47    },
48}
49
50impl Answer {
51    /// `NotCovered` without a fault.
52    pub const NOT_COVERED: Answer = Answer::NotCovered { fault: None };
53}
54
55/// The function computing a computed receipt's `summary`.
56pub type SummaryFn = dyn Fn(&Cell) -> String + Send + Sync;
57
58/// Builds an [`Engine`]: [`Engine::builder`].
59pub struct EngineBuilder {
60    pub(crate) store: Arc<dyn Store + Send + Sync>,
61    pub(crate) host: String,
62    pub(crate) key: Option<SigningKey>,
63    pub(crate) key_file: Option<PathBuf>,
64    pub(crate) runtimes: Vec<Arc<dyn Runtime>>,
65    pub(crate) depth_limit: usize,
66    pub(crate) fuel: u64,
67    pub(crate) work_limit: Option<u64>,
68    pub(crate) memo_capacity: usize,
69    pub(crate) licence: String,
70    pub(crate) summary: Option<Arc<SummaryFn>>,
71    pub(crate) clock: Arc<dyn Clock>,
72}
73
74impl EngineBuilder {
75    /// The mesh's signing key.
76    pub fn signing_key(mut self, key: SigningKey) -> Self {
77        self.key = Some(key);
78        self.key_file = None;
79        self
80    }
81
82    /// The mesh's signing key, from a file holding its 32-byte seed: the 32 bytes, or 64 hex
83    /// digits (an optional final newline). The only file the engine reads.
84    pub fn signing_key_file(mut self, path: impl Into<PathBuf>) -> Self {
85        self.key_file = Some(path.into());
86        self.key = None;
87        self
88    }
89
90    /// Adds a runtime, for the language its [`Runtime::lang`] names.
91    pub fn runtime(mut self, runtime: Arc<dyn Runtime>) -> Self {
92        self.runtimes.push(runtime);
93        self
94    }
95
96    /// The depth limit: frames on the evaluation stack (default 10,000).
97    pub fn depth_limit(mut self, limit: usize) -> Self {
98        self.depth_limit = limit;
99        self
100    }
101
102    /// The fuel of each request: runtime steps plus input reads (default 10,000,000).
103    pub fn fuel(mut self, fuel: u64) -> Self {
104        self.fuel = fuel;
105        self
106    }
107
108    /// The work limit of each request: every evaluation attempt (those discarded by a restart
109    /// included) and the engine's validation reads, in fuel units (default 16 times the
110    /// fuel). It bounds the total cost of a request beyond its normative fuel
111    /// ([`EngineError::WorkExceeded`](crate::EngineError::WorkExceeded)). Since 0.3.0.
112    pub fn work_limit(mut self, units: u64) -> Self {
113        self.work_limit = Some(units);
114        self
115    }
116
117    /// How many answers the memo keeps (default 1,000,000); when full it starts afresh. 0
118    /// turns the memo off: every request then validates through the store.
119    pub fn memo_capacity(mut self, entries: usize) -> Self {
120        self.memo_capacity = entries;
121        self
122    }
123
124    /// The `licence` of computed receipts: an SPDX identifier or an https URL (default
125    /// `CC-BY-4.0`).
126    pub fn licence(mut self, licence: impl Into<String>) -> Self {
127        self.licence = licence.into();
128        self
129    }
130
131    /// The `summary` of a computed receipt, from its cell. The default says which function
132    /// the mesh computed: `"<namespace>/<function> computed by <mesh host>."`.
133    pub fn summary(mut self, f: impl Fn(&Cell) -> String + Send + Sync + 'static) -> Self {
134        self.summary = Some(Arc::new(f));
135        self
136    }
137
138    /// The clock (default [`SystemClock`]).
139    pub fn clock(mut self, clock: Arc<dyn Clock>) -> Self {
140        self.clock = clock;
141        self
142    }
143
144    /// Checks the configuration and builds the engine.
145    pub fn build(self) -> Result<Engine, ConfigError> {
146        lexical::check_dns_name(&self.host, "$.host").map_err(ConfigError::Host)?;
147        let key = match (self.key, &self.key_file) {
148            (Some(k), _) => k,
149            (None, Some(path)) => read_seed(path)?,
150            (None, None) => return Err(ConfigError::NoSigningKey),
151        };
152        lexical::check_licence(&self.licence, "$.licence").map_err(ConfigError::Licence)?;
153        let mut runtimes: HashMap<String, Arc<dyn Runtime>> = HashMap::new();
154        for rt in self.runtimes {
155            let lang = rt.lang().to_string();
156            if lang == STORED {
157                return Err(ConfigError::Runtime("stored is answered by the engine, not a runtime".into()));
158            }
159            if runtimes.insert(lang.clone(), rt).is_some() {
160                return Err(ConfigError::Runtime(format!("two runtimes for {lang}")));
161            }
162        }
163        let published = match self.store.namespace(&self.host) {
164            Ok(Some(ns)) => KeyDoc::from_json(&self.host, &ns.keydoc)
165                .ok()
166                .and_then(|doc| doc.key(key.key_id()).map(|k| k.public == key.public_key()))
167                .unwrap_or(false),
168            Ok(None) => false,
169            Err(e) => return Err(ConfigError::Store(StoreError::new("namespace", e))),
170        };
171        if !published {
172            return Err(ConfigError::KeyNotPublished { host: self.host, key_id: key.key_id().to_string() });
173        }
174        Ok(Engine {
175            store: self.store,
176            host: self.host,
177            key,
178            runtimes,
179            depth_limit: self.depth_limit,
180            fuel: self.fuel,
181            work_limit: self.work_limit.unwrap_or(self.fuel.saturating_mul(DEFAULT_WORK_FACTOR)),
182            licence: self.licence,
183            summary: self.summary,
184            clock: self.clock,
185            memo: Memo::new(self.memo_capacity),
186            descriptors: Cache::new(DESCRIPTOR_CACHE),
187            receipts: Cache::new(RECEIPT_CACHE),
188            asof_dependent: Cache::new(DESCRIPTOR_CACHE),
189            evaluator: Mutex::new(()),
190        })
191    }
192}
193
194impl fmt::Debug for EngineBuilder {
195    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
196        f.debug_struct("EngineBuilder").field("host", &self.host).finish_non_exhaustive()
197    }
198}
199
200/// The engine: answers the value of a cell as of a time. See the crate documentation.
201pub struct Engine {
202    pub(crate) store: Arc<dyn Store + Send + Sync>,
203    pub(crate) host: String,
204    pub(crate) key: SigningKey,
205    pub(crate) runtimes: HashMap<String, Arc<dyn Runtime>>,
206    pub(crate) depth_limit: usize,
207    pub(crate) fuel: u64,
208    pub(crate) work_limit: u64,
209    pub(crate) licence: String,
210    pub(crate) summary: Option<Arc<SummaryFn>>,
211    pub(crate) clock: Arc<dyn Clock>,
212    pub(crate) memo: Memo,
213    /// Parsed descriptors by function hash (immutable: content-addressed).
214    pub(crate) descriptors: Cache<Arc<FunctionDescriptor>>,
215    /// Parsed receipts by hash (immutable: content-addressed).
216    pub(crate) receipts: Cache<Arc<Parsed>>,
217    /// Whether a function is asof-dependent, by function hash: a pure function of the
218    /// descriptor, which a runtime may take long to derive (it is asked on every frame).
219    pub(crate) asof_dependent: Cache<bool>,
220    /// Evaluations run one at a time (single-flight); answers from the memo do not wait.
221    pub(crate) evaluator: Mutex<()>,
222}
223
224/// The language of stored functions, answered by the engine itself.
225pub(crate) const STORED: &str = "stored";
226const DESCRIPTOR_CACHE: usize = 10_000;
227const RECEIPT_CACHE: usize = 100_000;
228
229/// The seed in a key file: 32 bytes, or 64 lowercase hex digits and an optional newline.
230fn read_seed(path: &std::path::Path) -> Result<SigningKey, ConfigError> {
231    let bytes = std::fs::read(path).map_err(|e| ConfigError::KeyFile(format!("{}: {e}", path.display())))?;
232    if let Ok(seed) = <[u8; 32]>::try_from(bytes.as_slice()) {
233        return Ok(SigningKey::from_seed(&seed));
234    }
235    let text = bytes.strip_suffix(b"\n").unwrap_or(&bytes);
236    let hex = |c: u8| match c {
237        b'0'..=b'9' => Some(c - b'0'),
238        b'a'..=b'f' => Some(c - b'a' + 10),
239        _ => None,
240    };
241    if text.len() == 64 {
242        let mut seed = [0u8; 32];
243        let mut ok = true;
244        for (i, pair) in text.chunks(2).enumerate() {
245            match (hex(pair[0]), hex(pair[1])) {
246                (Some(h), Some(l)) => seed[i] = h << 4 | l,
247                _ => ok = false,
248            }
249        }
250        if ok {
251            return Ok(SigningKey::from_seed(&seed));
252        }
253    }
254    Err(ConfigError::KeyFile(format!("{}: not a seed (32 bytes, or 64 lowercase hex digits)", path.display())))
255}
256
257impl fmt::Debug for Engine {
258    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
259        f.debug_struct("Engine").finish_non_exhaustive()
260    }
261}
262
263/// Sizes of the memo and of the dirty set ([`Engine::memo_stats`]).
264#[non_exhaustive]
265#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
266pub struct MemoStats {
267    /// Answers held.
268    pub entries: usize,
269    /// Cells with at least one answer held.
270    pub cells: usize,
271    /// Edges of the in-memory dependents index (input cell to reading cell).
272    pub dependent_edges: usize,
273    /// Cells marked dirty and kept to refuse answers of evaluations already running.
274    pub dirty: usize,
275    /// Answers dropped because a stored version they rested on changed, kept to be rechecked
276    /// from memory (early cutoff without store queries for the unchanged part of a graph).
277    pub stale: usize,
278    /// Slices over stored functions read by answers held (matched by pattern against new
279    /// stored versions). Since 0.3.0.
280    pub slice_patterns: usize,
281    /// An estimate of the bytes these take.
282    pub approx_bytes: usize,
283}
284
285impl Engine {
286    /// A builder for an engine on `store`, signing as the mesh `host`.
287    pub fn builder(store: Arc<dyn Store + Send + Sync>, host: impl Into<String>) -> EngineBuilder {
288        EngineBuilder {
289            store,
290            host: host.into(),
291            key: None,
292            key_file: None,
293            runtimes: Vec::new(),
294            depth_limit: DEFAULT_DEPTH_LIMIT,
295            fuel: DEFAULT_FUEL,
296            work_limit: None,
297            memo_capacity: DEFAULT_MEMO_CAPACITY,
298            licence: "CC-BY-4.0".into(),
299            summary: None,
300            clock: Arc::new(SystemClock),
301        }
302    }
303
304    /// The value of the cell `cell` denotes, as of `asof` (else `cell.asof`, else now).
305    ///
306    /// The function name resolves as of the asof; with no binding then, the answer is
307    /// [`Answer::NotCovered`]. See the crate documentation for the answers and errors.
308    pub fn get(&self, cell: &CellRef, asof: Option<&str>) -> Result<Answer, EngineError> {
309        let now = self.clock.now();
310        let a = asof.or(cell.asof.as_deref()).unwrap_or(&now).to_string();
311        lexical::check_instant(&a, "$.asof").map_err(EngineError::Invalid)?;
312        check_no_slice(&cell.args)?;
313        let fn_name = format!("{}/{}", cell.ns, cell.fn_name);
314        let Some(fn_hash) = self.store.resolve_name(&fn_name, &a).map_err(|e| StoreError::new("resolve_name", e))?
315        else {
316            return Ok(Answer::NOT_COVERED);
317        };
318        let resolved = cell.resolve(&fn_hash).map_err(EngineError::Invalid)?;
319        self.answer(&resolved, &a, &now)
320    }
321
322    /// The value of `cell` (its function pinned by `fn_hash`), as of `asof` (else now). The
323    /// form for a reference that already carries the function hash. An unknown function
324    /// hash is [`Answer::NotCovered`].
325    pub fn get_cell(&self, cell: &Cell, asof: Option<&str>) -> Result<Answer, EngineError> {
326        let now = self.clock.now();
327        let a = asof.unwrap_or(&now).to_string();
328        lexical::check_instant(&a, "$.asof").map_err(EngineError::Invalid)?;
329        check_no_slice(&cell.args)?;
330        self.answer(cell, &a, &now)
331    }
332
333    /// The answer for a resolved cell as of `a`; `now` is the request's clock reading.
334    fn answer(&self, cell: &Cell, a: &str, now: &str) -> Result<Answer, EngineError> {
335        let Some(desc) = self.descriptor_of(&cell.fn_hash)? else {
336            return Ok(Answer::NOT_COVERED);
337        };
338        check_args(cell, &desc).map_err(EngineError::Invalid)?;
339        let id = cell.id();
340        let store_err = |e: EvalError| match e {
341            EvalError::Store(e) => EngineError::Store(e),
342            other => EngineError::Runtime { cell_id: id.clone(), message: other.to_string() },
343        };
344        // From the memo, without waiting for the evaluator.
345        if let Some(ans) = Req::new(self, a, now).memo_hit(&id, a).map_err(store_err)? {
346            return Ok(Answer::Receipt(ans.bytes.to_vec()));
347        }
348        let done = if desc.lang == STORED {
349            let start = self.memo.begin();
350            let mut req = Req::new(self, a, now);
351            match req.stored(cell, &id, a) {
352                Ok(d) => {
353                    self.memo.end(start, &req.learned);
354                    d
355                }
356                Err(e) => {
357                    self.memo.abort(start);
358                    return Err(store_err(e));
359                }
360            }
361        } else {
362            let _single = self.evaluator.lock().unwrap_or_else(|p| p.into_inner());
363            self.evaluate_cell(cell, desc, a, now, false)?
364        };
365        Ok(match done {
366            Done::Value(ans) => Answer::Receipt(ans.bytes.to_vec()),
367            Done::Fault(fault, _) => Answer::NotCovered { fault: Some(fault) },
368            Done::NotCovered | Done::Unsigned(..) => Answer::NOT_COVERED,
369        })
370    }
371
372    /// Evaluates a computed cell in a request of its own (the caller holds the evaluator):
373    /// memo first, then the store's version validated, else the function; writes what is new
374    /// and keeps the answers in the memo.
375    fn evaluate_cell(
376        &self,
377        cell: &Cell,
378        desc: Arc<FunctionDescriptor>,
379        a: &str,
380        now: &str,
381        unsigned: bool,
382    ) -> Result<Done, EngineError> {
383        let start = self.memo.begin();
384        let mut req = Req::new(self, a, now);
385        let result = (|| {
386            if !unsigned {
387                if let Some(ans) =
388                    req.memo_hit(&cell.id(), &req.asof()).map_err(|e| crate::eval::engine_error(e, &cell.id()))?
389                {
390                    return Ok(Done::Value(ans));
391                }
392            }
393            let done = req.run(cell.clone(), desc, unsigned)?;
394            req.flush()?;
395            Ok(done)
396        })();
397        match &result {
398            Ok(_) => self.memo.end(start, &req.learned),
399            Err(_) => self.memo.abort(start),
400        }
401        result
402    }
403
404    /// A receipt the store returned, parsed (cached by hash).
405    pub(crate) fn parsed(&self, hash: &str, bytes: &[u8]) -> Result<Arc<Parsed>, StoreError> {
406        if let Some(p) = self.receipts.get(hash) {
407            return Ok(p);
408        }
409        let p = Arc::new(parse_stored(hash, bytes)?);
410        self.receipts.insert(hash.to_string(), p.clone());
411        Ok(p)
412    }
413
414    /// The value of `cell` as of `asof`, evaluated (a computed cell's function is run, not
415    /// looked up); for `Resolver::evaluate`.
416    fn evaluate_value(&self, cell: &Cell, asof: &str) -> Result<Option<Evaluation>, EngineError> {
417        if !is_instant(asof) || cell.is_slice() {
418            return Ok(None);
419        }
420        let Some(desc) = self.descriptor_of(&cell.fn_hash)? else { return Ok(None) };
421        if check_args(cell, &desc).is_err() {
422            return Ok(None);
423        }
424        let now = self.clock.now();
425        let done = if desc.lang == STORED {
426            Req::new(self, asof, &now)
427                .stored(cell, &cell.id(), asof)
428                .map_err(|e| EngineError::Runtime { cell_id: cell.id(), message: e.to_string() })?
429        } else {
430            let _single = self.evaluator.lock().unwrap_or_else(|p| p.into_inner());
431            self.evaluate_cell(cell, desc, asof, &now, true)?
432        };
433        Ok(match done {
434            Done::Value(ans) => Some(Evaluation::new(ans.value.clone())),
435            Done::Unsigned(v, lineage) => Some(Evaluation::with_lineage(v, lineage)),
436            Done::NotCovered | Done::Fault(..) => None,
437        })
438    }
439
440    /// Whether the function `fn_hash` (descriptor `desc`) is declared asof-dependent by its
441    /// runtime, cached by hash.
442    pub(crate) fn asof_dependent(&self, fn_hash: &str, desc: &FunctionDescriptor) -> bool {
443        if let Some(b) = self.asof_dependent.get(fn_hash) {
444            return b;
445        }
446        let b = self.runtimes.get(&desc.lang).is_some_and(|rt| rt.asof_dependent(desc));
447        self.asof_dependent.insert(fn_hash.to_string(), b);
448        b
449    }
450
451    /// The parsed descriptor of `fn_hash`, cached.
452    pub(crate) fn descriptor_of(&self, fn_hash: &str) -> Result<Option<Arc<FunctionDescriptor>>, EngineError> {
453        if let Some(d) = self.descriptors.get(fn_hash) {
454            return Ok(Some(d));
455        }
456        let Some(bytes) = self.store.descriptor(fn_hash) else { return Ok(None) };
457        let d = Arc::new(FunctionDescriptor::from_json(&bytes).map_err(EngineError::Invalid)?);
458        self.descriptors.insert(fn_hash.to_string(), d.clone());
459        Ok(Some(d))
460    }
461
462    /// Tells the engine that a stored version of `cell_id` was added: the memoised answers
463    /// that depend on the cell are dropped.
464    ///
465    /// Since 0.3.0 also the answers that read a slice the cell falls into (a late sample, a
466    /// correction, a new member), and nothing else: when some memoised answer read a slice
467    /// over a stored function (or an evaluation is running), the engine reads the cell's
468    /// latest receipt from the store to match it against their patterns. If that read fails,
469    /// every answer that read such a slice is dropped.
470    pub fn stored_version_added(&self, cell_id: &str) {
471        let receipt = if self.memo.wants_receipts() {
472            self.store
473                .latest(cell_id)
474                .ok()
475                .flatten()
476                .and_then(|v| self.store.receipt(&v.receipt_hash).map(|b| b.into_owned()))
477                .and_then(|b| datumesh_core::Receipt::from_json(&b).ok())
478                .map(Arc::new)
479        } else {
480            None
481        };
482        self.memo.invalidate(cell_id, receipt);
483    }
484
485    /// Drops every memoised answer.
486    pub fn clear_memo(&self) {
487        self.memo.clear();
488    }
489
490    /// Sizes of the memo and of the dirty set.
491    pub fn memo_stats(&self) -> MemoStats {
492        self.memo.stats()
493    }
494}
495
496impl Resolver for Engine {
497    fn descriptor(&self, fn_hash: &str) -> Option<Cow<'_, [u8]>> {
498        self.store.descriptor(fn_hash)
499    }
500
501    fn receipt(&self, hash: &str) -> Option<Cow<'_, [u8]>> {
502        self.store.receipt(hash)
503    }
504
505    /// The manifest of a slice entry, from the store (the engine stores the manifest of every
506    /// slice its receipts and evaluations read).
507    fn manifest(&self, entry: &str) -> Option<Cow<'_, [u8]>> {
508        self.store.manifest(entry)
509    }
510
511    /// The value of `cell` as of `asof` by the engine's answering rule (a receipt answers at
512    /// A when its tx and its asof are both at or before A): a stored cell's is looked up; a
513    /// computed cell's function is evaluated (its inputs answered as for `get`, and stored
514    /// when new), never read back from its own receipts. `None` when there is none or the
515    /// evaluation fails (logged with `tracing`, target `datumesh_engine`).
516    fn evaluate(&self, cell: &Cell, asof: &str) -> Option<Scalar> {
517        self.evaluation(cell, asof).map(|e| e.value)
518    }
519
520    /// [`evaluate`](Resolver::evaluate)'s value with, for a computed cell, its lineage: the
521    /// `inputs` entries the evaluation read (receipt hashes and slice entries, whose receipts
522    /// and manifests the engine serves), so that a verifier can report `E_INPUT_SUPERSEDED`
523    /// (SPEC 10.1 step 7.6). A stored cell's has none.
524    fn evaluation(&self, cell: &Cell, asof: &str) -> Option<Evaluation> {
525        match self.evaluate_value(cell, asof) {
526            Ok(v) => v,
527            Err(e) => {
528                tracing::debug!(target: "datumesh_engine", cell_id = %cell.id(), asof, error = %e, "evaluate failed");
529                None
530            }
531        }
532    }
533}