Skip to main content

datumesh_engine/
runtime.rs

1//! What a function's language plugs into: [`Runtime`], the [`Inputs`] it reads through and
2//! the [`Budget`] it charges.
3
4use std::collections::BTreeMap;
5use std::fmt;
6use std::sync::{Arc, Mutex, MutexGuard};
7
8use datumesh_core::{Args, Cell, FunctionDescriptor, Scalar};
9
10use crate::error::EvalError;
11
12/// The evaluator of one function language (`code.lang` of a descriptor).
13///
14/// `evaluate` computes the value of `cell` (a cell of the function `descriptor` describes;
15/// `cell.fn_hash` is the descriptor's hash) from the cell's arguments and from the values of
16/// other cells, which it reads through `inputs`. It must be a pure function of those (and of
17/// [`Inputs::asof`] for an asof-dependent function): no clock, no randomness, no I/O. It
18/// charges its work to `budget` and propagates every error `inputs` and `budget` return (see
19/// [`EvalError`]); it may catch an [`EvalError::Fault`] its language lets it catch.
20///
21/// It may be called more than once for one cell in one request: when it reads an input that
22/// is not available yet, the read returns [`EvalError::Suspended`], the engine evaluates the
23/// input, then calls `evaluate` again from the start (reads already made are then answered at
24/// once). So `evaluate` must not have side effects either. Each call is an attempt with a
25/// budget meter of its own: the fuel of a cell's evaluation is that of its last, completed
26/// call ([`Budget`]).
27pub trait Runtime: Send + Sync {
28    /// The language this runtime evaluates: a name (SPEC 2.2), e.g. `formula`. `stored` is
29    /// the engine's own (a lookup) and cannot be configured.
30    fn lang(&self) -> &str;
31
32    /// The value of `cell`, whose type must be the descriptor's declared return type; or
33    /// [`EvalError::Fault`]: the cell has no value (SPEC 15.12).
34    fn evaluate(
35        &self,
36        descriptor: &FunctionDescriptor,
37        cell: &Cell,
38        inputs: &mut dyn Inputs,
39        budget: &mut Budget,
40    ) -> Result<Scalar, EvalError>;
41
42    /// Whether the function is **asof-dependent** (SPEC 15.12: its body uses `asof()` or a
43    /// bounded `latest`), derived from the descriptor alone. Its receipts then have the
44    /// evaluation asof as their `asof`, one per requested asof, and the engine never reuses
45    /// one for another asof, from the memo or from the store. Provided: `false`.
46    ///
47    /// A function that reads [`Inputs::asof`] is treated as asof-dependent for that
48    /// evaluation even when this says `false`; its receipt is then not kept as a computed
49    /// version (a later request could not tell it apart), so declaring it is cheaper.
50    fn asof_dependent(&self, descriptor: &FunctionDescriptor) -> bool {
51        let _ = descriptor;
52        false
53    }
54}
55
56/// What a read gave: the value and the receipt stating it.
57#[non_exhaustive]
58#[derive(Clone, Debug, PartialEq, Eq)]
59pub struct Input {
60    /// The value.
61    pub value: Scalar,
62    /// The hash of the receipt stating it (SPEC 8.3).
63    pub receipt_hash: String,
64    /// The receipt's `tx`.
65    pub tx: String,
66    /// The receipt's `asof`.
67    pub asof: String,
68}
69
70impl Input {
71    /// An input (for a runtime's own tests).
72    pub fn new(
73        value: Scalar,
74        receipt_hash: impl Into<String>,
75        tx: impl Into<String>,
76        asof: impl Into<String>,
77    ) -> Input {
78        Input { value, receipt_hash: receipt_hash.into(), tx: tx.into(), asof: asof.into() }
79    }
80}
81
82/// A member of a slice ([`Inputs::read_slice`]): the member cell's arguments and its input.
83#[non_exhaustive]
84#[derive(Clone, Debug, PartialEq, Eq)]
85pub struct Member {
86    /// Every argument of the member cell.
87    pub args: Args,
88    /// Its value and receipt.
89    pub input: Input,
90}
91
92impl Member {
93    /// A member (for a runtime's own tests).
94    pub fn new(args: Args, input: Input) -> Member {
95        Member { args, input }
96    }
97}
98
99/// One argument of a slice pattern ([`Inputs::read_slice`]).
100#[non_exhaustive]
101#[derive(Clone, Debug, PartialEq, Eq)]
102pub enum Pattern {
103    /// Bound to a value.
104    Value(Scalar),
105    /// Open (`*`): any value.
106    Open,
107    /// Within `[lo..hi]`, both ends inclusive, in the type's order (SPEC 15.13); `lo` after
108    /// `hi` is empty. Both ends are of the argument's type: `number`, `date`, `instant` or
109    /// `string`.
110    Range {
111        /// The low end.
112        lo: Scalar,
113        /// The high end.
114        hi: Scalar,
115    },
116}
117
118/// A slice pattern: every argument of the function, by name.
119pub type SlicePattern = BTreeMap<String, Pattern>;
120
121/// A function name's binding ([`Inputs::binding`]).
122#[non_exhaustive]
123#[derive(Clone, Debug)]
124pub struct FnBinding {
125    /// The function hash the name means.
126    pub fn_hash: String,
127    /// When the binding began (an instant).
128    pub start: String,
129    /// The function's descriptor.
130    pub descriptor: Arc<FunctionDescriptor>,
131}
132
133impl FnBinding {
134    /// A binding (for a runtime's own tests, without a store). Since 0.3.1.
135    pub fn new(fn_hash: impl Into<String>, start: impl Into<String>, descriptor: Arc<FunctionDescriptor>) -> FnBinding {
136        FnBinding { fn_hash: fn_hash.into(), start: start.into(), descriptor }
137    }
138}
139
140/// How a runtime reads the cells its function depends on, and the evaluation's asof.
141///
142/// Every read checks that the function read is in the descriptor's `inputs`
143/// ([`EvalError::UndeclaredInput`]) and resolves its name ([`EvalError::NameUnresolved`]),
144/// and is recorded: it becomes one of the computed receipt's `inputs` entries, and the name's
145/// binding is relied on (its start is a candidate for the receipt's `asof`, SPEC 8.2) as soon
146/// as the read is attempted. The fuel each costs is SPEC 15.12's.
147///
148/// Errors a runtime must propagate (with `?`): [`EvalError::Suspended`] (an input not
149/// evaluated yet: the engine evaluates it and calls the runtime again),
150/// [`EvalError::InputNotCovered`] (an input with no value: neither has the cell, whatever the
151/// runtime returns next), [`EvalError::BudgetExceeded`] and the engine's failures. A
152/// [`EvalError::Fault`] it may catch where its language allows (SPEC 15.12: `otherwise`
153/// catches `E_FORMULA_EMPTY` and `E_FORMULA_ABSENT`).
154pub trait Inputs {
155    /// The value of the cell of function `fn_name` (fully qualified, `<namespace>/<name>`)
156    /// with arguments `args`, as of the evaluation's asof: [`read_cell`](Inputs::read_cell)'s
157    /// value. Costs 1.
158    fn read(&mut self, fn_name: &str, args: &Args) -> Result<Scalar, EvalError>;
159
160    /// The cell of `fn_name` with `args` as of the evaluation's asof: its value and the
161    /// receipt that answers (hash, `tx`, `asof`). A computed cell is evaluated by the engine;
162    /// its fault, if it has one, is returned ([`EvalError::Fault`]). Costs 1.
163    fn read_cell(&mut self, fn_name: &str, args: &Args) -> Result<Input, EvalError>;
164
165    /// The cell of `fn_name` with `args` as of the transaction time `t` (SPEC 15.13,
166    /// `asof(cell, T)`): the name resolved as of `t`, the version answering as of `t`; an
167    /// ordinary single-cell input, and `t` a candidate for the receipt's `asof`. `t` after the
168    /// evaluation's asof is the fault `E_FORMULA_FUTURE`, before anything is read. Costs 1.
169    fn read_asof(&mut self, fn_name: &str, args: &Args, t: &str) -> Result<Input, EvalError>;
170
171    /// The members of the slice of `fn_name` with `pattern` (every declared argument; at least
172    /// one open or ranged) as of the evaluation's asof, in SPEC 15.13 key order: for a stored
173    /// function, its cells matching the pattern with a version answering then; for any other,
174    /// the cells of the declared `extent` (or, for a range over a `date` or integer `number`
175    /// argument without one, every day or integer in it) within the pattern, each evaluated
176    /// by the engine, and every one must have a value: else the read is the fault
177    /// `E_FORMULA_ABSENT`. One `inputs` entry `slice:<slice id>:<members hash>`, whose
178    /// manifest the engine stores. Costs 1 + members, charged once the members are obtained.
179    fn read_slice(&mut self, fn_name: &str, pattern: &SlicePattern) -> Result<Vec<Member>, EvalError>;
180
181    /// The versions of the stored cell of `fn_name` with `args` whose `tx` is in `[from, to]`,
182    /// as known as of the evaluation's asof, ascending by `tx` (SPEC 15.13 `versions`): a
183    /// version slice, one `inputs` entry, `to` a candidate for the receipt's `asof`. `to` after
184    /// the evaluation's asof is `E_FORMULA_FUTURE`. Costs 1 + versions.
185    fn read_versions(&mut self, fn_name: &str, args: &Args, from: &str, to: &str) -> Result<Vec<Input>, EvalError>;
186
187    /// The cell of the function `fn_name` **at the function hash** `fn_hash`, with `args`, as
188    /// of the evaluation's asof: `P/m@<fn_hash>(...)` (SPEC 16.3 `super`). The cell is
189    /// evaluated with the descriptor stored under `fn_hash` and relies on no binding: the
190    /// name is not resolved, so no binding start is a candidate for the receipt's `asof` and
191    /// a later rebinding of `fn_name` does not change the answer. Otherwise it is an
192    /// ordinary read ([`read_cell`](Inputs::read_cell)): the receipt becomes an `inputs`
193    /// entry, an evaluation is suspended and restarted, a fault is returned, and it costs 1.
194    /// `fn_name` must be declared in the descriptor's `inputs` ([`EvalError::UndeclaredInput`]);
195    /// a `fn_hash` with no stored descriptor is a store failure ([`EvalError::Store`],
196    /// `NotFound`). Since 0.4.2.
197    ///
198    /// Provided: [`EvalError::Runtime`] (an `Inputs` with no pinned reads to offer; the
199    /// engine's inputs override it). Being a provided method of a trait implemented by the
200    /// engine and by runtimes' test doubles, it adds no obligation to an implementor.
201    fn read_pinned(&mut self, fn_name: &str, fn_hash: &str, args: &Args) -> Result<Input, EvalError> {
202        let _ = (fn_name, fn_hash, args);
203        Err(EvalError::Runtime("these inputs offer no pinned reads".into()))
204    }
205
206    /// The binding of `fn_name` as of the evaluation's asof, or as of `at`: its function hash,
207    /// when it began and the descriptor; `None` when it has none then. Relied on as a read's
208    /// name is. Free.
209    fn binding(&mut self, fn_name: &str, at: Option<&str>) -> Result<Option<FnBinding>, EvalError>;
210
211    /// The evaluation's asof (SPEC 15.12 `asof()`). Reading it makes the evaluation
212    /// asof-dependent (see [`Runtime::asof_dependent`]). Free.
213    fn asof(&mut self) -> String;
214
215    /// The binding of `fn_name` as of the evaluation's asof, or as of `at`, looked up without
216    /// being relied on: no asof candidate, no dependency of the answer on the name. For a
217    /// runtime that needs to know what a name means (to check a body against it, say) before,
218    /// or without, reading it; a read of the name still relies on it. Free. Since 0.3.1.
219    ///
220    /// Provided: [`binding`](Inputs::binding), which relies on it (the engine's inputs
221    /// override it).
222    fn binding_peek(&mut self, fn_name: &str, at: Option<&str>) -> Result<Option<FnBinding>, EvalError> {
223        self.binding(fn_name, at)
224    }
225
226    /// The content of the blob whose SHA-256 is `sha256` (64 lowercase hex digits) and whose
227    /// length is `length` bytes, as a blob value states them (`<sha256>:<length>:<media
228    /// type>`, SPEC 3.7). Since 0.3.2, for `text_of` (SPEC 15.7).
229    ///
230    /// The engine reads it from the store (`Store::blob`) and checks its length and SHA-256
231    /// against `length` and `sha256`. Content it cannot obtain, or that does not match, is
232    /// [`EvalError::BlobUnavailable`]: the evaluator's failure, not a fault of the cell; the
233    /// request fails with it whatever the runtime does next. The content adds no `inputs`
234    /// entry (the blob is an input already, as an argument or an input's value, and its
235    /// hash fixes the content), and it is free: the runtime charges what its language says
236    /// (SPEC 15.12: `text_of` 1 + bytes / 64, once the content is obtained), knowing the
237    /// length. The runtime checks the media type, before asking.
238    ///
239    /// Provided: [`EvalError::BlobUnavailable`] (an `Inputs` with no content to offer).
240    fn read_blob(&mut self, sha256: &str, length: u64) -> Result<Vec<u8>, EvalError> {
241        let _ = length;
242        Err(EvalError::BlobUnavailable {
243            sha256: sha256.to_string(),
244            reason: "these inputs offer no blob content".into(),
245        })
246    }
247
248    /// How the instant `t` compares with the evaluation's asof (`t.cmp(asof)`), without
249    /// making the evaluation asof-dependent when the answer cannot change at a later asof.
250    /// Free. Since 0.3.1.
251    ///
252    /// What the engine records: when `t` is at or before the asof (`Less` or `Equal`), `t` is
253    /// a candidate for the receipt's `asof` (as `T` of a transaction-time read is), so every
254    /// asof the receipt answers or is validated at is at or after `t` and the comparison gives
255    /// the same there; the receipt recomputes at its own asof. When `t` is after it
256    /// (`Greater`), the answer would change once the asof reaches `t`: the evaluation is then
257    /// asof-dependent, as by [`asof`](Inputs::asof) (and a runtime may report
258    /// `E_FORMULA_FUTURE` for it, even after an input without a value). A `t` that is not an
259    /// instant is [`EvalError::InvalidInput`].
260    ///
261    /// Provided: by [`asof`](Inputs::asof), which always makes the evaluation asof-dependent
262    /// (the engine's inputs override it).
263    fn asof_compare(&mut self, t: &str) -> Result<std::cmp::Ordering, EvalError> {
264        datumesh_core::lexical::check_instant(t, "$.t").map_err(EvalError::InvalidInput)?;
265        Ok(t.cmp(self.asof().as_str()))
266    }
267}
268
269/// The fuel of an evaluation attempt, on the request's meter.
270///
271/// Fuel is normative (SPEC 15.12): the fuel of a cell's evaluation is what its last,
272/// completed attempt charges ([`used`](Budget::used)), whatever number of times the engine
273/// restarted it. A request's normative fuel is the sum of the evaluations it completes, and
274/// its limit ([`limit`](Budget::limit)) is checked at every charge against a lower bound of
275/// that sum (each suspended evaluation will charge at least what its last attempt did), so a
276/// request fails with `BudgetExceeded` exactly when its normative fuel exceeds the limit.
277/// Separately the request's **work** (every attempt, those discarded by a restart included,
278/// and the engine's validation reads) has a limit of its own, which bounds the total cost.
279/// When either runs out, the request fails and stores nothing.
280pub struct Budget {
281    meter: Arc<Mutex<Meter>>,
282}
283
284#[derive(Debug)]
285pub(crate) struct Meter {
286    limit: u64,
287    work_limit: u64,
288    /// The normative fuel of the evaluations completed.
289    committed: u64,
290    /// The lower bounds of the suspended evaluations on the stack.
291    pending: u64,
292    /// The running attempt: its charges and its lower bound (its earlier attempt's charges).
293    attempt: u64,
294    floor: u64,
295    work: u64,
296    pub(crate) exhausted: Exhausted,
297}
298
299/// What ran out.
300#[derive(Clone, Copy, Debug, PartialEq, Eq)]
301pub(crate) enum Exhausted {
302    No,
303    Fuel,
304    Work,
305}
306
307impl Meter {
308    fn bound(&self) -> u64 {
309        self.committed.saturating_add(self.pending).saturating_add(self.attempt.max(self.floor))
310    }
311}
312
313impl Budget {
314    /// A budget of `fuel` units, with no work limit (for a runtime's own tests; the engine
315    /// makes the budget of a request from its configuration).
316    pub fn new(fuel: u64) -> Budget {
317        Budget::with_work(fuel, u64::MAX)
318    }
319
320    pub(crate) fn with_work(fuel: u64, work_limit: u64) -> Budget {
321        Budget {
322            meter: Arc::new(Mutex::new(Meter {
323                limit: fuel,
324                work_limit,
325                committed: 0,
326                pending: 0,
327                attempt: 0,
328                floor: 0,
329                work: 0,
330                exhausted: Exhausted::No,
331            })),
332        }
333    }
334
335    fn lock(&self) -> MutexGuard<'_, Meter> {
336        self.meter.lock().unwrap_or_else(|p| p.into_inner())
337    }
338
339    /// Charges `steps` units of work to this attempt. [`EvalError::BudgetExceeded`] when the
340    /// request's fuel (or its work) runs out: the budget is then exhausted for the rest of the
341    /// request.
342    pub fn charge(&mut self, steps: u64) -> Result<(), EvalError> {
343        self.charge_shared(steps)
344    }
345
346    /// The fuel this attempt has charged so far: at the end of a completed attempt, the
347    /// normative fuel of the evaluation.
348    pub fn used(&self) -> u64 {
349        self.lock().attempt
350    }
351
352    /// The fuel left: the limit less the lower bound of the request's normative fuel.
353    pub fn remaining(&self) -> u64 {
354        let m = self.lock();
355        if m.exhausted != Exhausted::No {
356            return 0;
357        }
358        m.limit.saturating_sub(m.bound())
359    }
360
361    /// The request's fuel limit.
362    pub fn limit(&self) -> u64 {
363        self.lock().limit
364    }
365
366    /// Whether a charge has failed.
367    pub fn is_exhausted(&self) -> bool {
368        self.lock().exhausted != Exhausted::No
369    }
370
371    pub(crate) fn exhausted(&self) -> Exhausted {
372        self.lock().exhausted
373    }
374
375    pub(crate) fn work_limit(&self) -> u64 {
376        self.lock().work_limit
377    }
378
379    /// Another handle on the same meter.
380    pub(crate) fn share(&self) -> Budget {
381        Budget { meter: Arc::clone(&self.meter) }
382    }
383
384    /// A normative charge of the running attempt.
385    pub(crate) fn charge_shared(&self, steps: u64) -> Result<(), EvalError> {
386        let mut m = self.lock();
387        if m.exhausted != Exhausted::No {
388            return Err(EvalError::BudgetExceeded { fuel: m.limit });
389        }
390        // The normative limit first: a charge exceeding both is BudgetExceeded.
391        m.work = m.work.saturating_add(steps);
392        m.attempt = m.attempt.saturating_add(steps);
393        if m.bound() > m.limit {
394            m.exhausted = Exhausted::Fuel;
395            return Err(EvalError::BudgetExceeded { fuel: m.limit });
396        }
397        if m.work > m.work_limit {
398            m.exhausted = Exhausted::Work;
399            return Err(EvalError::BudgetExceeded { fuel: m.limit });
400        }
401        Ok(())
402    }
403
404    /// Work that is not normative (validation reads, rechecks).
405    pub(crate) fn work(&self, steps: u64) -> Result<(), EvalError> {
406        let mut m = self.lock();
407        if m.exhausted != Exhausted::No {
408            return Err(EvalError::BudgetExceeded { fuel: m.limit });
409        }
410        m.work = m.work.saturating_add(steps);
411        if m.work > m.work_limit {
412            m.exhausted = Exhausted::Work;
413            return Err(EvalError::BudgetExceeded { fuel: m.limit });
414        }
415        Ok(())
416    }
417
418    /// Starts an attempt of a frame whose earlier attempts charged at most `floor` (0 for a
419    /// first attempt); the frame's floor is no longer pending.
420    pub(crate) fn begin_attempt(&self, floor: u64) {
421        let mut m = self.lock();
422        m.pending = m.pending.saturating_sub(floor);
423        m.attempt = 0;
424        m.floor = floor;
425    }
426
427    /// The running attempt suspended: returns the frame's new floor, now pending.
428    pub(crate) fn suspend_attempt(&self) -> u64 {
429        let mut m = self.lock();
430        let floor = m.attempt.max(m.floor);
431        m.pending = m.pending.saturating_add(floor);
432        m.attempt = 0;
433        m.floor = 0;
434        floor
435    }
436
437    /// The running attempt completed: its fuel is the evaluation's.
438    pub(crate) fn finish_attempt(&self) -> u64 {
439        let mut m = self.lock();
440        let used = m.attempt;
441        m.committed = m.committed.saturating_add(used);
442        m.attempt = 0;
443        m.floor = 0;
444        used
445    }
446}
447
448impl fmt::Debug for Budget {
449    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
450        let m = self.lock();
451        f.debug_struct("Budget")
452            .field("limit", &m.limit)
453            .field("used", &m.attempt)
454            .field("committed", &m.committed)
455            .field("exhausted", &(m.exhausted != Exhausted::No))
456            .finish()
457    }
458}