datumesh-engine 0.3.2

The Datumesh engine: the value of a cell as of a time, from stored receipts or by evaluating functions; memoised, and signed for computed cells.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
//! What a function's language plugs into: [`Runtime`], the [`Inputs`] it reads through and
//! the [`Budget`] it charges.

use std::collections::BTreeMap;
use std::fmt;
use std::sync::{Arc, Mutex, MutexGuard};

use datumesh_core::{Args, Cell, FunctionDescriptor, Scalar};

use crate::error::EvalError;

/// The evaluator of one function language (`code.lang` of a descriptor).
///
/// `evaluate` computes the value of `cell` (a cell of the function `descriptor` describes;
/// `cell.fn_hash` is the descriptor's hash) from the cell's arguments and from the values of
/// other cells, which it reads through `inputs`. It must be a pure function of those (and of
/// [`Inputs::asof`] for an asof-dependent function): no clock, no randomness, no I/O. It
/// charges its work to `budget` and propagates every error `inputs` and `budget` return (see
/// [`EvalError`]); it may catch an [`EvalError::Fault`] its language lets it catch.
///
/// It may be called more than once for one cell in one request: when it reads an input that
/// is not available yet, the read returns [`EvalError::Suspended`], the engine evaluates the
/// input, then calls `evaluate` again from the start (reads already made are then answered at
/// once). So `evaluate` must not have side effects either. Each call is an attempt with a
/// budget meter of its own: the fuel of a cell's evaluation is that of its last, completed
/// call ([`Budget`]).
pub trait Runtime: Send + Sync {
    /// The language this runtime evaluates: a name (SPEC 2.2), e.g. `formula`. `stored` is
    /// the engine's own (a lookup) and cannot be configured.
    fn lang(&self) -> &str;

    /// The value of `cell`, whose type must be the descriptor's declared return type; or
    /// [`EvalError::Fault`]: the cell has no value (SPEC 15.12).
    fn evaluate(
        &self,
        descriptor: &FunctionDescriptor,
        cell: &Cell,
        inputs: &mut dyn Inputs,
        budget: &mut Budget,
    ) -> Result<Scalar, EvalError>;

    /// Whether the function is **asof-dependent** (SPEC 15.12: its body uses `asof()` or a
    /// bounded `latest`), derived from the descriptor alone. Its receipts then have the
    /// evaluation asof as their `asof`, one per requested asof, and the engine never reuses
    /// one for another asof, from the memo or from the store. Provided: `false`.
    ///
    /// A function that reads [`Inputs::asof`] is treated as asof-dependent for that
    /// evaluation even when this says `false`; its receipt is then not kept as a computed
    /// version (a later request could not tell it apart), so declaring it is cheaper.
    fn asof_dependent(&self, descriptor: &FunctionDescriptor) -> bool {
        let _ = descriptor;
        false
    }
}

/// What a read gave: the value and the receipt stating it.
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Input {
    /// The value.
    pub value: Scalar,
    /// The hash of the receipt stating it (SPEC 8.3).
    pub receipt_hash: String,
    /// The receipt's `tx`.
    pub tx: String,
    /// The receipt's `asof`.
    pub asof: String,
}

impl Input {
    /// An input (for a runtime's own tests).
    pub fn new(
        value: Scalar,
        receipt_hash: impl Into<String>,
        tx: impl Into<String>,
        asof: impl Into<String>,
    ) -> Input {
        Input { value, receipt_hash: receipt_hash.into(), tx: tx.into(), asof: asof.into() }
    }
}

/// A member of a slice ([`Inputs::read_slice`]): the member cell's arguments and its input.
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Member {
    /// Every argument of the member cell.
    pub args: Args,
    /// Its value and receipt.
    pub input: Input,
}

impl Member {
    /// A member (for a runtime's own tests).
    pub fn new(args: Args, input: Input) -> Member {
        Member { args, input }
    }
}

/// One argument of a slice pattern ([`Inputs::read_slice`]).
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Pattern {
    /// Bound to a value.
    Value(Scalar),
    /// Open (`*`): any value.
    Open,
    /// Within `[lo..hi]`, both ends inclusive, in the type's order (SPEC 15.13); `lo` after
    /// `hi` is empty. Both ends are of the argument's type: `number`, `date`, `instant` or
    /// `string`.
    Range {
        /// The low end.
        lo: Scalar,
        /// The high end.
        hi: Scalar,
    },
}

/// A slice pattern: every argument of the function, by name.
pub type SlicePattern = BTreeMap<String, Pattern>;

/// A function name's binding ([`Inputs::binding`]).
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct FnBinding {
    /// The function hash the name means.
    pub fn_hash: String,
    /// When the binding began (an instant).
    pub start: String,
    /// The function's descriptor.
    pub descriptor: Arc<FunctionDescriptor>,
}

impl FnBinding {
    /// A binding (for a runtime's own tests, without a store). Since 0.3.1.
    pub fn new(fn_hash: impl Into<String>, start: impl Into<String>, descriptor: Arc<FunctionDescriptor>) -> FnBinding {
        FnBinding { fn_hash: fn_hash.into(), start: start.into(), descriptor }
    }
}

/// How a runtime reads the cells its function depends on, and the evaluation's asof.
///
/// Every read checks that the function read is in the descriptor's `inputs`
/// ([`EvalError::UndeclaredInput`]) and resolves its name ([`EvalError::NameUnresolved`]),
/// and is recorded: it becomes one of the computed receipt's `inputs` entries, and the name's
/// binding is relied on (its start is a candidate for the receipt's `asof`, SPEC 8.2) as soon
/// as the read is attempted. The fuel each costs is SPEC 15.12's.
///
/// Errors a runtime must propagate (with `?`): [`EvalError::Suspended`] (an input not
/// evaluated yet: the engine evaluates it and calls the runtime again),
/// [`EvalError::InputNotCovered`] (an input with no value: neither has the cell, whatever the
/// runtime returns next), [`EvalError::BudgetExceeded`] and the engine's failures. A
/// [`EvalError::Fault`] it may catch where its language allows (SPEC 15.12: `otherwise`
/// catches `E_FORMULA_EMPTY` and `E_FORMULA_ABSENT`).
pub trait Inputs {
    /// The value of the cell of function `fn_name` (fully qualified, `<namespace>/<name>`)
    /// with arguments `args`, as of the evaluation's asof: [`read_cell`](Inputs::read_cell)'s
    /// value. Costs 1.
    fn read(&mut self, fn_name: &str, args: &Args) -> Result<Scalar, EvalError>;

    /// The cell of `fn_name` with `args` as of the evaluation's asof: its value and the
    /// receipt that answers (hash, `tx`, `asof`). A computed cell is evaluated by the engine;
    /// its fault, if it has one, is returned ([`EvalError::Fault`]). Costs 1.
    fn read_cell(&mut self, fn_name: &str, args: &Args) -> Result<Input, EvalError>;

    /// The cell of `fn_name` with `args` as of the transaction time `t` (SPEC 15.13,
    /// `asof(cell, T)`): the name resolved as of `t`, the version answering as of `t`; an
    /// ordinary single-cell input, and `t` a candidate for the receipt's `asof`. `t` after the
    /// evaluation's asof is the fault `E_FORMULA_FUTURE`, before anything is read. Costs 1.
    fn read_asof(&mut self, fn_name: &str, args: &Args, t: &str) -> Result<Input, EvalError>;

    /// The members of the slice of `fn_name` with `pattern` (every declared argument; at least
    /// one open or ranged) as of the evaluation's asof, in SPEC 15.13 key order: for a stored
    /// function, its cells matching the pattern with a version answering then; for any other,
    /// the cells of the declared `extent` (or, for a range over a `date` or integer `number`
    /// argument without one, every day or integer in it) within the pattern, each evaluated
    /// by the engine, and every one must have a value: else the read is the fault
    /// `E_FORMULA_ABSENT`. One `inputs` entry `slice:<slice id>:<members hash>`, whose
    /// manifest the engine stores. Costs 1 + members, charged once the members are obtained.
    fn read_slice(&mut self, fn_name: &str, pattern: &SlicePattern) -> Result<Vec<Member>, EvalError>;

    /// The versions of the stored cell of `fn_name` with `args` whose `tx` is in `[from, to]`,
    /// as known as of the evaluation's asof, ascending by `tx` (SPEC 15.13 `versions`): a
    /// version slice, one `inputs` entry, `to` a candidate for the receipt's `asof`. `to` after
    /// the evaluation's asof is `E_FORMULA_FUTURE`. Costs 1 + versions.
    fn read_versions(&mut self, fn_name: &str, args: &Args, from: &str, to: &str) -> Result<Vec<Input>, EvalError>;

    /// The binding of `fn_name` as of the evaluation's asof, or as of `at`: its function hash,
    /// when it began and the descriptor; `None` when it has none then. Relied on as a read's
    /// name is. Free.
    fn binding(&mut self, fn_name: &str, at: Option<&str>) -> Result<Option<FnBinding>, EvalError>;

    /// The evaluation's asof (SPEC 15.12 `asof()`). Reading it makes the evaluation
    /// asof-dependent (see [`Runtime::asof_dependent`]). Free.
    fn asof(&mut self) -> String;

    /// The binding of `fn_name` as of the evaluation's asof, or as of `at`, looked up without
    /// being relied on: no asof candidate, no dependency of the answer on the name. For a
    /// runtime that needs to know what a name means (to check a body against it, say) before,
    /// or without, reading it; a read of the name still relies on it. Free. Since 0.3.1.
    ///
    /// Provided: [`binding`](Inputs::binding), which relies on it (the engine's inputs
    /// override it).
    fn binding_peek(&mut self, fn_name: &str, at: Option<&str>) -> Result<Option<FnBinding>, EvalError> {
        self.binding(fn_name, at)
    }

    /// The content of the blob whose SHA-256 is `sha256` (64 lowercase hex digits) and whose
    /// length is `length` bytes, as a blob value states them (`<sha256>:<length>:<media
    /// type>`, SPEC 3.7). Since 0.3.2, for `text_of` (SPEC 15.7).
    ///
    /// The engine reads it from the store (`Store::blob`) and checks its length and SHA-256
    /// against `length` and `sha256`. Content it cannot obtain, or that does not match, is
    /// [`EvalError::BlobUnavailable`]: the evaluator's failure, not a fault of the cell; the
    /// request fails with it whatever the runtime does next. The content adds no `inputs`
    /// entry (the blob is an input already, as an argument or an input's value, and its
    /// hash fixes the content), and it is free: the runtime charges what its language says
    /// (SPEC 15.12: `text_of` 1 + bytes / 64, once the content is obtained), knowing the
    /// length. The runtime checks the media type, before asking.
    ///
    /// Provided: [`EvalError::BlobUnavailable`] (an `Inputs` with no content to offer).
    fn read_blob(&mut self, sha256: &str, length: u64) -> Result<Vec<u8>, EvalError> {
        let _ = length;
        Err(EvalError::BlobUnavailable {
            sha256: sha256.to_string(),
            reason: "these inputs offer no blob content".into(),
        })
    }

    /// How the instant `t` compares with the evaluation's asof (`t.cmp(asof)`), without
    /// making the evaluation asof-dependent when the answer cannot change at a later asof.
    /// Free. Since 0.3.1.
    ///
    /// What the engine records: when `t` is at or before the asof (`Less` or `Equal`), `t` is
    /// a candidate for the receipt's `asof` (as `T` of a transaction-time read is), so every
    /// asof the receipt answers or is validated at is at or after `t` and the comparison gives
    /// the same there; the receipt recomputes at its own asof. When `t` is after it
    /// (`Greater`), the answer would change once the asof reaches `t`: the evaluation is then
    /// asof-dependent, as by [`asof`](Inputs::asof) (and a runtime may report
    /// `E_FORMULA_FUTURE` for it, even after an input without a value). A `t` that is not an
    /// instant is [`EvalError::InvalidInput`].
    ///
    /// Provided: by [`asof`](Inputs::asof), which always makes the evaluation asof-dependent
    /// (the engine's inputs override it).
    fn asof_compare(&mut self, t: &str) -> Result<std::cmp::Ordering, EvalError> {
        datumesh_core::lexical::check_instant(t, "$.t").map_err(EvalError::InvalidInput)?;
        Ok(t.cmp(self.asof().as_str()))
    }
}

/// The fuel of an evaluation attempt, on the request's meter.
///
/// Fuel is normative (SPEC 15.12): the fuel of a cell's evaluation is what its last,
/// completed attempt charges ([`used`](Budget::used)), whatever number of times the engine
/// restarted it. A request's normative fuel is the sum of the evaluations it completes, and
/// its limit ([`limit`](Budget::limit)) is checked at every charge against a lower bound of
/// that sum (each suspended evaluation will charge at least what its last attempt did), so a
/// request fails with `BudgetExceeded` exactly when its normative fuel exceeds the limit.
/// Separately the request's **work** (every attempt, those discarded by a restart included,
/// and the engine's validation reads) has a limit of its own, which bounds the total cost.
/// When either runs out, the request fails and stores nothing.
pub struct Budget {
    meter: Arc<Mutex<Meter>>,
}

#[derive(Debug)]
pub(crate) struct Meter {
    limit: u64,
    work_limit: u64,
    /// The normative fuel of the evaluations completed.
    committed: u64,
    /// The lower bounds of the suspended evaluations on the stack.
    pending: u64,
    /// The running attempt: its charges and its lower bound (its earlier attempt's charges).
    attempt: u64,
    floor: u64,
    work: u64,
    pub(crate) exhausted: Exhausted,
}

/// What ran out.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Exhausted {
    No,
    Fuel,
    Work,
}

impl Meter {
    fn bound(&self) -> u64 {
        self.committed.saturating_add(self.pending).saturating_add(self.attempt.max(self.floor))
    }
}

impl Budget {
    /// A budget of `fuel` units, with no work limit (for a runtime's own tests; the engine
    /// makes the budget of a request from its configuration).
    pub fn new(fuel: u64) -> Budget {
        Budget::with_work(fuel, u64::MAX)
    }

    pub(crate) fn with_work(fuel: u64, work_limit: u64) -> Budget {
        Budget {
            meter: Arc::new(Mutex::new(Meter {
                limit: fuel,
                work_limit,
                committed: 0,
                pending: 0,
                attempt: 0,
                floor: 0,
                work: 0,
                exhausted: Exhausted::No,
            })),
        }
    }

    fn lock(&self) -> MutexGuard<'_, Meter> {
        self.meter.lock().unwrap_or_else(|p| p.into_inner())
    }

    /// Charges `steps` units of work to this attempt. [`EvalError::BudgetExceeded`] when the
    /// request's fuel (or its work) runs out: the budget is then exhausted for the rest of the
    /// request.
    pub fn charge(&mut self, steps: u64) -> Result<(), EvalError> {
        self.charge_shared(steps)
    }

    /// The fuel this attempt has charged so far: at the end of a completed attempt, the
    /// normative fuel of the evaluation.
    pub fn used(&self) -> u64 {
        self.lock().attempt
    }

    /// The fuel left: the limit less the lower bound of the request's normative fuel.
    pub fn remaining(&self) -> u64 {
        let m = self.lock();
        if m.exhausted != Exhausted::No {
            return 0;
        }
        m.limit.saturating_sub(m.bound())
    }

    /// The request's fuel limit.
    pub fn limit(&self) -> u64 {
        self.lock().limit
    }

    /// Whether a charge has failed.
    pub fn is_exhausted(&self) -> bool {
        self.lock().exhausted != Exhausted::No
    }

    pub(crate) fn exhausted(&self) -> Exhausted {
        self.lock().exhausted
    }

    pub(crate) fn work_limit(&self) -> u64 {
        self.lock().work_limit
    }

    /// Another handle on the same meter.
    pub(crate) fn share(&self) -> Budget {
        Budget { meter: Arc::clone(&self.meter) }
    }

    /// A normative charge of the running attempt.
    pub(crate) fn charge_shared(&self, steps: u64) -> Result<(), EvalError> {
        let mut m = self.lock();
        if m.exhausted != Exhausted::No {
            return Err(EvalError::BudgetExceeded { fuel: m.limit });
        }
        // The normative limit first: a charge exceeding both is BudgetExceeded.
        m.work = m.work.saturating_add(steps);
        m.attempt = m.attempt.saturating_add(steps);
        if m.bound() > m.limit {
            m.exhausted = Exhausted::Fuel;
            return Err(EvalError::BudgetExceeded { fuel: m.limit });
        }
        if m.work > m.work_limit {
            m.exhausted = Exhausted::Work;
            return Err(EvalError::BudgetExceeded { fuel: m.limit });
        }
        Ok(())
    }

    /// Work that is not normative (validation reads, rechecks).
    pub(crate) fn work(&self, steps: u64) -> Result<(), EvalError> {
        let mut m = self.lock();
        if m.exhausted != Exhausted::No {
            return Err(EvalError::BudgetExceeded { fuel: m.limit });
        }
        m.work = m.work.saturating_add(steps);
        if m.work > m.work_limit {
            m.exhausted = Exhausted::Work;
            return Err(EvalError::BudgetExceeded { fuel: m.limit });
        }
        Ok(())
    }

    /// Starts an attempt of a frame whose earlier attempts charged at most `floor` (0 for a
    /// first attempt); the frame's floor is no longer pending.
    pub(crate) fn begin_attempt(&self, floor: u64) {
        let mut m = self.lock();
        m.pending = m.pending.saturating_sub(floor);
        m.attempt = 0;
        m.floor = floor;
    }

    /// The running attempt suspended: returns the frame's new floor, now pending.
    pub(crate) fn suspend_attempt(&self) -> u64 {
        let mut m = self.lock();
        let floor = m.attempt.max(m.floor);
        m.pending = m.pending.saturating_add(floor);
        m.attempt = 0;
        m.floor = 0;
        floor
    }

    /// The running attempt completed: its fuel is the evaluation's.
    pub(crate) fn finish_attempt(&self) -> u64 {
        let mut m = self.lock();
        let used = m.attempt;
        m.committed = m.committed.saturating_add(used);
        m.attempt = 0;
        m.floor = 0;
        used
    }
}

impl fmt::Debug for Budget {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let m = self.lock();
        f.debug_struct("Budget")
            .field("limit", &m.limit)
            .field("used", &m.attempt)
            .field("committed", &m.committed)
            .field("exhausted", &(m.exhausted != Exhausted::No))
            .finish()
    }
}