datumesh_engine/lib.rs
1//! The [Datumesh](https://datumesh.com) engine: the value of a cell as of a time.
2//!
3//! [`Engine::get`] answers "the value of this cell as of A" with a receipt: for a stored
4//! cell, the publisher's receipt from the store, unchanged; for a computed cell, a receipt the
5//! engine signs with the mesh's key after evaluating the cell's function through a
6//! [`Runtime`], from the receipts of the cells it reads. Answers are memoised; computed
7//! versions are kept in the store (`put_computed`) and validated before they are reused. The
8//! store is a [`datumesh_store::Store`] (a `PgStore`: the trait is sealed); the API is
9//! synchronous and [`Engine`] is `Send + Sync`.
10//!
11//! # Answering as of A
12//!
13//! A receipt answers as of A only when its `tx` and its `asof` are both at or before A. A
14//! stored cell's answer is `stored_asof(cell, A)`. A computed cell's is its computed version
15//! with the greatest `asof <= A` (`computed_asof`), once it is validated as of A; when none
16//! validates, the function is evaluated as of A and, unless the value equals that version's
17//! (which is then kept), a new receipt is signed and stored. No asof means now: the clock
18//! reading taken once at the start of the request, which is also the `issued` of every
19//! receipt the request signs.
20//!
21//! Function names resolve (`resolve_name`) as of A: the requested reference's name, and every
22//! input name a function reads. [`Engine::get_cell`] takes a cell whose function hash is
23//! already pinned (the core's [`CellRef`](datumesh_core::CellRef) carries no hash).
24//!
25//! # Computed receipts
26//!
27//! `computed_by` is `<mesh host>#<key id>`, `publisher` the cell's namespace, `inputs` the
28//! hashes of the receipts read, `tx` the latest input `tx` (SPEC 8.2), `issued` the request's
29//! clock reading, `valid` the cell's valid-time arguments, `licence` and `summary` from the
30//! engine's configuration ([`EngineBuilder::licence`], [`EngineBuilder::summary`]): the
31//! descriptor has neither, and adding them would change function hashes.
32//!
33//! `asof` is the latest of its input asofs (slice members included), the start of every name
34//! binding it relied on, every `T` of a transaction-time read and every `to` of a version
35//! read (SPEC 8.2 rule 2), so that the receipt is true as of its own `asof` and recomputes
36//! there; for an asof-dependent function, the evaluation asof (below). `tx` is the latest
37//! input `tx`, members included (the earliest instant when there is none, as when the only
38//! inputs are empty slices):
39//!
40//! * an input's asof is where its answer starts: its receipt's `asof`, except for an input
41//! answered by a version that was kept or validated across a change of its own inputs,
42//! which counts from where its value was established again;
43//! * the names relied on are the function names read, transitively (an input's own inputs'
44//! names included, and a function's own name when it reads itself, as fib does); each
45//! binding's start is when the binding answering as of A began
46//! ([`Store::resolve_binding`](datumesh_store::Store::resolve_binding)): a name bound
47//! again, even to the same function, begins again. The requested cell's own name is not
48//! among them: its receipt pins the function hash.
49//!
50//! * a value that rests on a fault a read returned and the runtime caught (SPEC 15.12:
51//! `otherwise` over a computed slice with a faulting member) counts from where that fault
52//! holds: the latest input asof and binding start of the faulted evaluation. (SPEC 8.2
53//! names no candidate for it; without one the receipt would not recompute at its asof.)
54//!
55//! The asof is never later than A. Between it and A the inputs and the bindings are those
56//! read, so the one receipt answers every request in between (and later ones, after
57//! validation).
58//!
59//! # Slices and transaction-time reads (spec-0.4.0)
60//!
61//! [`Inputs::read_slice`] reads the members of a slice as of A, in SPEC 15.13 key order: of a
62//! stored function, its cells matching the pattern with a version answering then
63//! (`Store::slice_members`); of a computed one, the cells of its declared `extent` within the
64//! pattern (a range over a `date` or integer `number` argument without an extent: every day
65//! or integer), each a computed cell the engine answers like any input, memoised, with the
66//! cycle and depth rules (a member on the evaluation stack is a [`EngineError::Cycle`]),
67//! evaluated in key order up to the first without a value, which makes the read the fault
68//! `E_FORMULA_ABSENT` (later members are neither evaluated nor charged). A slice read is one `inputs`
69//! entry `slice:<slice id>:<members hash>`; its manifest is stored (`put_manifest`) with the
70//! receipts, and served by [`Engine`] as a resolver. [`Inputs::read_versions`] reads a
71//! version slice of a stored cell, [`Inputs::read_asof`] a cell as of a transaction time `T`
72//! (its name resolved as of `T`; a computed cell evaluated as of `T`), `E_FORMULA_FUTURE` when
73//! `T` (or `to`) is after A.
74//!
75//! # Faults
76//!
77//! A runtime's [`EvalError::Fault`] (`E_FORMULA_DIV_ZERO`, `E_FORMULA_DOMAIN`,
78//! `E_FORMULA_RANGE`, `E_FORMULA_EMPTY`, `E_FORMULA_ABSENT`, `E_FORMULA_FUTURE`) gives the cell
79//! no value: [`Answer::NotCovered`] with the fault, no receipt, nothing stored for the cell
80//! (what the request computed before it is kept, as for an input with no value). A reader of
81//! a faulted cell gets the same fault, which it may catch. A value that rests on a caught
82//! fault is signed, but its version is not kept for validation, nor in the memo: no receipt
83//! lists what the fault rested on.
84//!
85//! # Asof-dependent functions
86//!
87//! A function whose value may change with the asof alone (SPEC 15.12: `asof()`, a bounded
88//! `latest`), as its runtime declares ([`Runtime::asof_dependent`]) or as it shows by reading
89//! [`Inputs::asof`], has the evaluation asof as its receipt's `asof`: one receipt per
90//! requested asof. The memo keeps it for that asof only, and a stored version is reused only
91//! as of its own asof (SPEC 5.5: a mesh MUST NOT serve it as `ok` for another). A function
92//! that reads the asof without declaring it is not kept as a computed version at all. A
93//! reader of such a cell is not itself asof-dependent: its version validates by its inputs.
94//!
95//! [`Inputs::asof_compare`] compares a time with the asof without that dependence when the
96//! answer cannot change later (a time at or before the asof becomes an asof candidate of the
97//! receipt; a time after it makes the evaluation asof-dependent), and
98//! [`Inputs::binding_peek`] looks a binding up without relying on it (since 0.3.1).
99//!
100//! A function that reads nothing has `tx` = `asof` = `0001-01-01T00:00:00.000000Z`: its value
101//! does not depend on time.
102//!
103//! ## Receipt identity
104//!
105//! Receipt identity is per computed version, keyed on (cell, `tx`, `asof`). Two valid
106//! receipts for the same value may exist with different lineage: when an input changes and
107//! changes back, validation by value (early cutoff) can accept either version, so which one
108//! answers depends on which versions earlier requests stored. The value is always the same.
109//!
110//! A backdated correction (an input superseded at a `tx` earlier than the receipt's own `tx`)
111//! would give a second version under an existing key, which the store refuses. The engine
112//! keeps the stored version, which answers correctly, and reuses a receipt it signed before
113//! for exactly the current inputs. The old receipt stays signature-valid and answers the
114//! asofs it was issued for; it no longer recomputes, because one of its inputs has been
115//! superseded. Recomputation verifies "given these exact inputs", and the inputs it cites are
116//! still the ones it used: the receipt is historical, not wrong.
117//!
118//! # Memo, validation and early cutoff
119//!
120//! A version is valid as of A when every input receipt it lists, its name still resolving to
121//! its function, gives as of A the same receipt or the same value (early cutoff), and every
122//! slice entry, its function's name still resolving to the slice's function, has as of A the
123//! same members hash, or members that are the same cells with the same values. Validation
124//! reads only the store (manifests included), so it is always available, and correctness
125//! rests on it alone. Versions whose receipts do not say all validation needs are not kept as
126//! computed versions: those resting on a caught fault, on a read at a transaction time (which
127//! a receipt does not mark), or on the asof read by a function not declared
128//! asof-dependent; they are evaluated again by later requests (their inputs memoised).
129//!
130//! The memo keeps each answer with the interval of asofs it holds for (a stored version from
131//! its asof to the next version's; a computed answer the intersection of its inputs') and the
132//! names it depends on, which are resolved again on every use. Adding a stored version must be
133//! reported with [`Engine::stored_version_added`]: it drops the cell's answers and those of
134//! every cell that read them (the dirty set, through the memo's own index of the cell-level
135//! dependents of the answers it holds), and those of every answer that read a slice the cell
136//! falls into (a correction of a member, a late sample, a new member), matched by the slice's
137//! pattern: a correction to day ten of a running total drops days ten onwards only. Dropped answers are rechecked from memory before the
138//! store is asked, so after a change that early cutoff stops, the unchanged part of a graph
139//! costs no store query. Evaluations running across an invalidation cannot keep what they
140//! read (revision marks). A process that writes versions without telling the engine leaves its
141//! memo stale until [`Engine::clear_memo`]; [`EngineBuilder::memo_capacity`]`(0)` validates
142//! every request through the store instead.
143//!
144//! Early-cutoff records need not be persisted: a version kept because its recomputed value is
145//! the same stays the version in the store, so a fresh engine (after a restart) validates the
146//! readers above it by receipt hash and recomputes only the cell whose inputs changed, as the
147//! first engine did (`tests/early_cutoff.rs`).
148//!
149//! # Recursion and suspension
150//!
151//! A function may read its own name with other arguments (fib(n) reads fib(n - 1)).
152//! Evaluation runs on an explicit stack of frames on the heap, never native recursion. When a
153//! runtime reads a computed input not answered yet, [`Inputs::read`] returns
154//! [`EvalError::Suspended`]; the engine pushes a frame for the input and, once it is answered,
155//! runs the suspended function again from the start, its earlier reads now answered at once
156//! from the request. A cell reappearing on the stack is [`EngineError::Cycle`]; more frames
157//! than the depth limit (default 10,000) is [`EngineError::DepthExceeded`].
158//!
159//! The cost of the restart scheme: a function whose k computed inputs are all missing when it
160//! starts runs up to k + 1 times and re-reads its earlier inputs each time (O(k^2) reads at
161//! worst). A chain runs each link twice; fib(n) runs fib(2) three times and every other fib(k)
162//! twice. Validating a stored version first makes its inputs available before the function
163//! runs, so a recomputation after a change usually runs once.
164//!
165//! A slice read over a computed function whose members are not answered yet suspends once:
166//! the engine evaluates every missing member in turn, then runs the reader again.
167//!
168//! # Budget and single-flight
169//!
170//! Fuel is normative (SPEC 15.12): each read costs what the fuel table says (a single-cell
171//! read 1, a slice read 1 + members once the members are obtained, a version read 1 +
172//! versions) and the runtime charges its own steps ([`Budget::charge`]). Each run of a
173//! runtime is an attempt with a meter of its own; the fuel of a cell's evaluation is that of
174//! its last, completed attempt ([`Budget::used`]), so it does not depend on how many times
175//! the engine restarted it. A request's fuel ([`EngineBuilder::fuel`], default 10,000,000)
176//! bounds the sum over the evaluations it completes; at every charge the engine checks a
177//! lower bound of that sum (a suspended attempt's re-run charges at least as much), so the
178//! request fails with [`EngineError::BudgetExceeded`] exactly when its normative fuel exceeds
179//! the limit. The total work, discarded attempts and validation reads included, has its own
180//! limit ([`EngineBuilder::work_limit`], default 16 times the fuel:
181//! [`EngineError::WorkExceeded`]). When either runs out nothing is stored: new receipts,
182//! manifests and versions are written only after a request has succeeded.
183//!
184//! Evaluations run one at a time per engine, so concurrent requests for the same uncomputed
185//! cell evaluate it once: the second finds the first's answer. Answers from the memo and of
186//! stored cells do not wait.
187//!
188//! # For the HTTP layer
189//!
190//! | `Engine::get` result | Meaning | Envelope (SPEC 5.5), in spirit |
191//! |---|---|---|
192//! | `Ok(Answer::Receipt(bytes))` | the receipt answering as of A (`asof <= A`) | `ok`; `trust` `primary` when the host of `computed_by` is the host of `cell.ns` and `inputs` is empty, `verified` for a receipt the engine computed |
193//! | `Ok(Answer::NotCovered { fault: None })` | the name has no binding as of A, the function hash is unknown, a stored cell has no version answering as of A, or a computed cell read an input with none | `not_covered` |
194//! | `Ok(Answer::NotCovered { fault: Some(f) })` | the cell's evaluation faulted (SPEC 15.12): it has no value, deterministically | `not_covered`, `fault` = `f.as_str()` (`E_FORMULA_DIV_ZERO`, ...) |
195//! | `Err(Invalid(e))` | a malformed request (asof, slice, arguments against the signature) | `bad_request`, `error` = `e.code()` |
196//! | `Err(NameUnresolved { .. })` | an input's name has no binding as of A | `error`, `E_FN_UNAVAILABLE` |
197//! | `Err(UndeclaredInput { .. })` | a function read a name it does not declare | `error`, `E_INPUT_UNDECLARED` |
198//! | `Err(NoRuntime { .. })`, `Runtime`, `Cycle`, `DepthExceeded`, `BudgetExceeded`, `WorkExceeded` | the mesh could not evaluate the function | `error`, `E_EVAL_UNAVAILABLE` (or `stale` with an earlier receipt; never for an asof-dependent cell's receipt of another asof) |
199//! | `Err(Sign(e))` | an input's `asof` is later than the clock (`E_TIME_ORDER`) | `error`, `E_TIME_ORDER` |
200//! | `Err(Store(e))` | the store failed | `error`, `E_INPUT_UNAVAILABLE` (or `stale`) |
201//!
202//! `trust` for an engine-computed receipt is `verified`. A receipt of an asof-dependent
203//! function answers only the asof it was made for, which is what `get` returns.
204//!
205//! [`Engine`] is also a time-aware [`datumesh_core::Resolver`], with the answering rule above:
206//! `descriptor`, `receipt` and `manifest` from the store; `evaluate` looks a stored cell up
207//! and evaluates a computed cell's function (never reading its own receipts back), and
208//! `evaluation` gives that value with its lineage (the entries read), so that a verifier can
209//! report `E_INPUT_SUPERSEDED` (SPEC 10.1 step 7.6).
210//!
211//! # Example
212//!
213//! ```no_run
214//! use std::sync::Arc;
215//!
216//! use datumesh_core::{CellRef, SigningKey};
217//! use datumesh_engine::{Answer, Engine};
218//! use datumesh_store::{PgStore, Store};
219//!
220//! let store: Arc<dyn Store + Send + Sync> = Arc::new(PgStore::connect("postgres://localhost/datumesh").unwrap());
221//! // The store must hold the mesh's key document: it verifies every receipt stored.
222//! let engine = Engine::builder(store, "mesh.example.com").signing_key(SigningKey::from_seed(&[2; 32])).build().unwrap();
223//! let cell = CellRef::from_json(br#"{"args":{},"fn":"total","ns":"shop.example.com"}"#).unwrap();
224//! match engine.get(&cell, None).unwrap() {
225//! Answer::Receipt(bytes) => println!("{}", String::from_utf8_lossy(&bytes)),
226//! Answer::NotCovered { fault: Some(f) } => println!("no value: {f}"),
227//! _ => println!("not covered"),
228//! }
229//! ```
230//!
231//! Feature `native-test` adds `native_test::NativeTest`, a runtime of Rust closures keyed by
232//! function hash, for tests.
233
234#![forbid(unsafe_code)]
235#![deny(missing_docs)]
236
237mod cache;
238mod check;
239mod clock;
240mod engine;
241mod error;
242mod eval;
243mod memo;
244#[cfg(feature = "native-test")]
245pub mod native_test;
246mod runtime;
247mod sign;
248mod slice;
249
250pub use clock::{Clock, SystemClock};
251pub use engine::{
252 Answer, Engine, EngineBuilder, MemoStats, SummaryFn, DEFAULT_DEPTH_LIMIT, DEFAULT_FUEL, DEFAULT_MEMO_CAPACITY,
253 DEFAULT_WORK_FACTOR,
254};
255pub use error::{ConfigError, EngineError, EvalError, StoreError};
256pub use runtime::{Budget, FnBinding, Input, Inputs, Member, Pattern, Runtime, SlicePattern};