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 cell `cell` denotes, its function name resolved as of `asof` (else `cell.asof`,
323    /// else now), as [`get`](Engine::get) resolves it; `None` when the name has no binding
324    /// then (SPEC 5.5 `E_NAME_UNBOUND`: it may be bound later), where `get` answers
325    /// [`Answer::NotCovered`]. With the cell, [`get_cell`](Engine::get_cell) answers as `get`
326    /// would. Malformed requests are the errors `get` gives. Since 0.3.2.
327    pub fn resolve(&self, cell: &CellRef, asof: Option<&str>) -> Result<Option<Cell>, EngineError> {
328        let now;
329        let a = match asof.or(cell.asof.as_deref()) {
330            Some(a) => a,
331            None => {
332                now = self.clock.now();
333                &now
334            }
335        };
336        lexical::check_instant(a, "$.asof").map_err(EngineError::Invalid)?;
337        check_no_slice(&cell.args)?;
338        let fn_name = format!("{}/{}", cell.ns, cell.fn_name);
339        let Some(fn_hash) = self.store.resolve_name(&fn_name, a).map_err(|e| StoreError::new("resolve_name", e))?
340        else {
341            return Ok(None);
342        };
343        cell.resolve(&fn_hash).map(Some).map_err(EngineError::Invalid)
344    }
345
346    /// The value of `cell` (its function pinned by `fn_hash`), as of `asof` (else now). The
347    /// form for a reference that already carries the function hash. An unknown function
348    /// hash is [`Answer::NotCovered`].
349    pub fn get_cell(&self, cell: &Cell, asof: Option<&str>) -> Result<Answer, EngineError> {
350        let now = self.clock.now();
351        let a = asof.unwrap_or(&now).to_string();
352        lexical::check_instant(&a, "$.asof").map_err(EngineError::Invalid)?;
353        check_no_slice(&cell.args)?;
354        self.answer(cell, &a, &now)
355    }
356
357    /// The answer for a resolved cell as of `a`; `now` is the request's clock reading.
358    fn answer(&self, cell: &Cell, a: &str, now: &str) -> Result<Answer, EngineError> {
359        let Some(desc) = self.descriptor_of(&cell.fn_hash)? else {
360            return Ok(Answer::NOT_COVERED);
361        };
362        check_args(cell, &desc).map_err(EngineError::Invalid)?;
363        let id = cell.id();
364        let store_err = |e: EvalError| match e {
365            EvalError::Store(e) => EngineError::Store(e),
366            other => EngineError::Runtime { cell_id: id.clone(), message: other.to_string() },
367        };
368        // From the memo, without waiting for the evaluator.
369        if let Some(ans) = Req::new(self, a, now).memo_hit(&id, a).map_err(store_err)? {
370            return Ok(Answer::Receipt(ans.bytes.to_vec()));
371        }
372        let done = if desc.lang == STORED {
373            let start = self.memo.begin();
374            let mut req = Req::new(self, a, now);
375            match req.stored(cell, &id, a) {
376                Ok(d) => {
377                    self.memo.end(start, &req.learned);
378                    d
379                }
380                Err(e) => {
381                    self.memo.abort(start);
382                    return Err(store_err(e));
383                }
384            }
385        } else {
386            let _single = self.evaluator.lock().unwrap_or_else(|p| p.into_inner());
387            self.evaluate_cell(cell, desc, a, now, false)?
388        };
389        Ok(match done {
390            Done::Value(ans) => Answer::Receipt(ans.bytes.to_vec()),
391            Done::Fault(fault, _) => Answer::NotCovered { fault: Some(fault) },
392            Done::NotCovered | Done::Unsigned(..) => Answer::NOT_COVERED,
393        })
394    }
395
396    /// Evaluates a computed cell in a request of its own (the caller holds the evaluator):
397    /// memo first, then the store's version validated, else the function; writes what is new
398    /// and keeps the answers in the memo.
399    fn evaluate_cell(
400        &self,
401        cell: &Cell,
402        desc: Arc<FunctionDescriptor>,
403        a: &str,
404        now: &str,
405        unsigned: bool,
406    ) -> Result<Done, EngineError> {
407        let start = self.memo.begin();
408        let mut req = Req::new(self, a, now);
409        let result = (|| {
410            if !unsigned {
411                if let Some(ans) =
412                    req.memo_hit(&cell.id(), &req.asof()).map_err(|e| crate::eval::engine_error(e, &cell.id()))?
413                {
414                    return Ok(Done::Value(ans));
415                }
416            }
417            let done = req.run(cell.clone(), desc, unsigned)?;
418            req.flush()?;
419            Ok(done)
420        })();
421        match &result {
422            Ok(_) => self.memo.end(start, &req.learned),
423            Err(_) => self.memo.abort(start),
424        }
425        result
426    }
427
428    /// A receipt the store returned, parsed (cached by hash).
429    pub(crate) fn parsed(&self, hash: &str, bytes: &[u8]) -> Result<Arc<Parsed>, StoreError> {
430        if let Some(p) = self.receipts.get(hash) {
431            return Ok(p);
432        }
433        let p = Arc::new(parse_stored(hash, bytes)?);
434        self.receipts.insert(hash.to_string(), p.clone());
435        Ok(p)
436    }
437
438    /// The value of `cell` as of `asof`, evaluated (a computed cell's function is run, not
439    /// looked up); for `Resolver::evaluate`.
440    fn evaluate_value(&self, cell: &Cell, asof: &str) -> Result<Option<Evaluation>, EngineError> {
441        if !is_instant(asof) || cell.is_slice() {
442            return Ok(None);
443        }
444        let Some(desc) = self.descriptor_of(&cell.fn_hash)? else { return Ok(None) };
445        if check_args(cell, &desc).is_err() {
446            return Ok(None);
447        }
448        let now = self.clock.now();
449        let done = if desc.lang == STORED {
450            Req::new(self, asof, &now)
451                .stored(cell, &cell.id(), asof)
452                .map_err(|e| EngineError::Runtime { cell_id: cell.id(), message: e.to_string() })?
453        } else {
454            let _single = self.evaluator.lock().unwrap_or_else(|p| p.into_inner());
455            self.evaluate_cell(cell, desc, asof, &now, true)?
456        };
457        Ok(match done {
458            Done::Value(ans) => Some(Evaluation::new(ans.value.clone())),
459            Done::Unsigned(v, lineage) => Some(Evaluation::with_lineage(v, lineage)),
460            Done::NotCovered | Done::Fault(..) => None,
461        })
462    }
463
464    /// Whether the function `fn_hash` (descriptor `desc`) is declared asof-dependent by its
465    /// runtime, cached by hash.
466    pub(crate) fn asof_dependent(&self, fn_hash: &str, desc: &FunctionDescriptor) -> bool {
467        if let Some(b) = self.asof_dependent.get(fn_hash) {
468            return b;
469        }
470        let b = self.runtimes.get(&desc.lang).is_some_and(|rt| rt.asof_dependent(desc));
471        self.asof_dependent.insert(fn_hash.to_string(), b);
472        b
473    }
474
475    /// The parsed descriptor of `fn_hash`, cached.
476    pub(crate) fn descriptor_of(&self, fn_hash: &str) -> Result<Option<Arc<FunctionDescriptor>>, EngineError> {
477        if let Some(d) = self.descriptors.get(fn_hash) {
478            return Ok(Some(d));
479        }
480        let Some(bytes) = self.store.descriptor(fn_hash) else { return Ok(None) };
481        let d = Arc::new(FunctionDescriptor::from_json(&bytes).map_err(EngineError::Invalid)?);
482        self.descriptors.insert(fn_hash.to_string(), d.clone());
483        Ok(Some(d))
484    }
485
486    /// Tells the engine that a stored version of `cell_id` was added: the memoised answers
487    /// that depend on the cell are dropped.
488    ///
489    /// Since 0.3.0 also the answers that read a slice the cell falls into (a late sample, a
490    /// correction, a new member), and nothing else: when some memoised answer read a slice
491    /// over a stored function (or an evaluation is running), the engine reads the cell's
492    /// latest receipt from the store to match it against their patterns. If that read fails,
493    /// every answer that read such a slice is dropped.
494    pub fn stored_version_added(&self, cell_id: &str) {
495        let receipt = if self.memo.wants_receipts() {
496            self.store
497                .latest(cell_id)
498                .ok()
499                .flatten()
500                .and_then(|v| self.store.receipt(&v.receipt_hash).map(|b| b.into_owned()))
501                .and_then(|b| datumesh_core::Receipt::from_json(&b).ok())
502                .map(Arc::new)
503        } else {
504            None
505        };
506        self.memo.invalidate(cell_id, receipt);
507    }
508
509    /// Drops every memoised answer.
510    pub fn clear_memo(&self) {
511        self.memo.clear();
512    }
513
514    /// Sizes of the memo and of the dirty set.
515    pub fn memo_stats(&self) -> MemoStats {
516        self.memo.stats()
517    }
518}
519
520impl Resolver for Engine {
521    fn descriptor(&self, fn_hash: &str) -> Option<Cow<'_, [u8]>> {
522        self.store.descriptor(fn_hash)
523    }
524
525    fn receipt(&self, hash: &str) -> Option<Cow<'_, [u8]>> {
526        self.store.receipt(hash)
527    }
528
529    /// The manifest of a slice entry, from the store (the engine stores the manifest of every
530    /// slice its receipts and evaluations read).
531    fn manifest(&self, entry: &str) -> Option<Cow<'_, [u8]>> {
532        self.store.manifest(entry)
533    }
534
535    /// The value of `cell` as of `asof` by the engine's answering rule (a receipt answers at
536    /// A when its tx and its asof are both at or before A): a stored cell's is looked up; a
537    /// computed cell's function is evaluated (its inputs answered as for `get`, and stored
538    /// when new), never read back from its own receipts. `None` when there is none or the
539    /// evaluation fails (logged with `tracing`, target `datumesh_engine`).
540    fn evaluate(&self, cell: &Cell, asof: &str) -> Option<Scalar> {
541        self.evaluation(cell, asof).map(|e| e.value)
542    }
543
544    /// [`evaluate`](Resolver::evaluate)'s value with, for a computed cell, its lineage: the
545    /// `inputs` entries the evaluation read (receipt hashes and slice entries, whose receipts
546    /// and manifests the engine serves), so that a verifier can report `E_INPUT_SUPERSEDED`
547    /// (SPEC 10.1 step 7.6). A stored cell's has none.
548    fn evaluation(&self, cell: &Cell, asof: &str) -> Option<Evaluation> {
549        match self.evaluate_value(cell, asof) {
550            Ok(v) => v,
551            Err(e) => {
552                tracing::debug!(target: "datumesh_engine", cell_id = %cell.id(), asof, error = %e, "evaluate failed");
553                None
554            }
555        }
556    }
557}