Skip to main content

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//! # Blob content (spec-0.4.2)
76//!
77//! [`Inputs::read_blob`] gives a blob's content (for `text_of`, SPEC 15.7) from the store,
78//! checked against the blob's length and SHA-256. Content the engine cannot obtain or check
79//! is [`EngineError::BlobUnavailable`], the evaluator's failure (`E_EVAL_UNAVAILABLE`), never
80//! `not_covered`. The content is no `inputs` entry; the runtime charges its fuel. Recomputing
81//! through [`Engine`] as a resolver obtains it again from the store.
82//!
83//! # Faults
84//!
85//! A runtime's [`EvalError::Fault`] (`E_FORMULA_DIV_ZERO`, `E_FORMULA_DOMAIN`,
86//! `E_FORMULA_RANGE`, `E_FORMULA_EMPTY`, `E_FORMULA_ABSENT`, `E_FORMULA_FUTURE`) gives the cell
87//! no value: [`Answer::NotCovered`] with the fault, no receipt, nothing stored for the cell
88//! (what the request computed before it is kept, as for an input with no value). A reader of
89//! a faulted cell gets the same fault, which it may catch. A value that rests on a caught
90//! fault is signed, but its version is not kept for validation, nor in the memo: no receipt
91//! lists what the fault rested on.
92//!
93//! # Asof-dependent functions
94//!
95//! A function whose value may change with the asof alone (SPEC 15.12: `asof()`, a bounded
96//! `latest`), as its runtime declares ([`Runtime::asof_dependent`]) or as it shows by reading
97//! [`Inputs::asof`], has the evaluation asof as its receipt's `asof`: one receipt per
98//! requested asof. The memo keeps it for that asof only, and a stored version is reused only
99//! as of its own asof (SPEC 5.5: a mesh MUST NOT serve it as `ok` for another). A function
100//! that reads the asof without declaring it is not kept as a computed version at all. A
101//! reader of such a cell is not itself asof-dependent: its version validates by its inputs.
102//!
103//! [`Inputs::asof_compare`] compares a time with the asof without that dependence when the
104//! answer cannot change later (a time at or before the asof becomes an asof candidate of the
105//! receipt; a time after it makes the evaluation asof-dependent), and
106//! [`Inputs::binding_peek`] looks a binding up without relying on it (since 0.3.1).
107//!
108//! A function that reads nothing has `tx` = `asof` = `0001-01-01T00:00:00.000000Z`: its value
109//! does not depend on time.
110//!
111//! ## Receipt identity
112//!
113//! Receipt identity is per computed version, keyed on (cell, `tx`, `asof`). Two valid
114//! receipts for the same value may exist with different lineage: when an input changes and
115//! changes back, validation by value (early cutoff) can accept either version, so which one
116//! answers depends on which versions earlier requests stored. The value is always the same.
117//!
118//! A backdated correction (an input superseded at a `tx` earlier than the receipt's own `tx`)
119//! would give a second version under an existing key, which the store refuses. The engine
120//! keeps the stored version, which answers correctly, and reuses a receipt it signed before
121//! for exactly the current inputs. The old receipt stays signature-valid and answers the
122//! asofs it was issued for; it no longer recomputes, because one of its inputs has been
123//! superseded. Recomputation verifies "given these exact inputs", and the inputs it cites are
124//! still the ones it used: the receipt is historical, not wrong.
125//!
126//! # Memo, validation and early cutoff
127//!
128//! A version is valid as of A when every input receipt it lists, its name still resolving to
129//! its function, gives as of A the same receipt or the same value (early cutoff), and every
130//! slice entry, its function's name still resolving to the slice's function, has as of A the
131//! same members hash, or members that are the same cells with the same values. Validation
132//! reads only the store (manifests included), so it is always available, and correctness
133//! rests on it alone. Versions whose receipts do not say all validation needs are not kept as
134//! computed versions: those resting on a caught fault, on a read at a transaction time (which
135//! a receipt does not mark), or on the asof read by a function not declared
136//! asof-dependent; they are evaluated again by later requests (their inputs memoised).
137//!
138//! The memo keeps each answer with the interval of asofs it holds for (a stored version from
139//! its asof to the next version's; a computed answer the intersection of its inputs') and the
140//! names it depends on, which are resolved again on every use. Adding a stored version must be
141//! reported with [`Engine::stored_version_added`]: it drops the cell's answers and those of
142//! every cell that read them (the dirty set, through the memo's own index of the cell-level
143//! dependents of the answers it holds), and those of every answer that read a slice the cell
144//! falls into (a correction of a member, a late sample, a new member), matched by the slice's
145//! pattern: a correction to day ten of a running total drops days ten onwards only. Dropped answers are rechecked from memory before the
146//! store is asked, so after a change that early cutoff stops, the unchanged part of a graph
147//! costs no store query. Evaluations running across an invalidation cannot keep what they
148//! read (revision marks). A process that writes versions without telling the engine leaves its
149//! memo stale until [`Engine::clear_memo`]; [`EngineBuilder::memo_capacity`]`(0)` validates
150//! every request through the store instead.
151//!
152//! Early-cutoff records need not be persisted: a version kept because its recomputed value is
153//! the same stays the version in the store, so a fresh engine (after a restart) validates the
154//! readers above it by receipt hash and recomputes only the cell whose inputs changed, as the
155//! first engine did (`tests/early_cutoff.rs`).
156//!
157//! # Recursion and suspension
158//!
159//! A function may read its own name with other arguments (fib(n) reads fib(n - 1)).
160//! Evaluation runs on an explicit stack of frames on the heap, never native recursion. When a
161//! runtime reads a computed input not answered yet, [`Inputs::read`] returns
162//! [`EvalError::Suspended`]; the engine pushes a frame for the input and, once it is answered,
163//! runs the suspended function again from the start, its earlier reads now answered at once
164//! from the request. A cell reappearing on the stack is [`EngineError::Cycle`]; more frames
165//! than the depth limit (default 10,000) is [`EngineError::DepthExceeded`].
166//!
167//! The cost of the restart scheme: a function whose k computed inputs are all missing when it
168//! starts runs up to k + 1 times and re-reads its earlier inputs each time (O(k^2) reads at
169//! worst). A chain runs each link twice; fib(n) runs fib(2) three times and every other fib(k)
170//! twice. Validating a stored version first makes its inputs available before the function
171//! runs, so a recomputation after a change usually runs once.
172//!
173//! A slice read over a computed function whose members are not answered yet suspends once:
174//! the engine evaluates every missing member in turn, then runs the reader again.
175//!
176//! # Budget and single-flight
177//!
178//! Fuel is normative (SPEC 15.12): each read costs what the fuel table says (a single-cell
179//! read 1, a slice read 1 + members once the members are obtained, a version read 1 +
180//! versions) and the runtime charges its own steps ([`Budget::charge`]). Each run of a
181//! runtime is an attempt with a meter of its own; the fuel of a cell's evaluation is that of
182//! its last, completed attempt ([`Budget::used`]), so it does not depend on how many times
183//! the engine restarted it. A request's fuel ([`EngineBuilder::fuel`], default 10,000,000)
184//! bounds the sum over the evaluations it completes; at every charge the engine checks a
185//! lower bound of that sum (a suspended attempt's re-run charges at least as much), so the
186//! request fails with [`EngineError::BudgetExceeded`] exactly when its normative fuel exceeds
187//! the limit. The total work, discarded attempts and validation reads included, has its own
188//! limit ([`EngineBuilder::work_limit`], default 16 times the fuel:
189//! [`EngineError::WorkExceeded`]). When either runs out nothing is stored: new receipts,
190//! manifests and versions are written only after a request has succeeded.
191//!
192//! Evaluations run one at a time per engine, so concurrent requests for the same uncomputed
193//! cell evaluate it once: the second finds the first's answer. Answers from the memo and of
194//! stored cells do not wait.
195//!
196//! # For the HTTP layer
197//!
198//! | `Engine::get` result | Meaning | Envelope (SPEC 5.5), in spirit |
199//! |---|---|---|
200//! | `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 |
201//! | `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` |
202//! | `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`, ...) |
203//! | `Err(Invalid(e))` | a malformed request (asof, slice, arguments against the signature) | `bad_request`, `error` = `e.code()` |
204//! | `Err(NameUnresolved { .. })` | an input's name has no binding as of A | `error`, `E_FN_UNAVAILABLE` |
205//! | `Err(UndeclaredInput { .. })` | a function read a name it does not declare | `error`, `E_INPUT_UNDECLARED` |
206//! | `Err(NoRuntime { .. })`, `Runtime`, `Cycle`, `DepthExceeded`, `BudgetExceeded`, `WorkExceeded`, `BlobUnavailable` | 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) |
207//! | `Err(Sign(e))` | an input's `asof` is later than the clock (`E_TIME_ORDER`) | `error`, `E_TIME_ORDER` |
208//! | `Err(Store(e))` | the store failed | `error`, `E_INPUT_UNAVAILABLE` (or `stale`) |
209//!
210//! Since spec-0.4.2: a request pinned to a function hash (`fn_hash=`) is
211//! [`Engine::get_cell`] with that hash (an unknown hash is plain `not_covered`); an unbound
212//! name (`not_covered` with `E_NAME_UNBOUND`) is told apart with [`Engine::resolve`], which
213//! gives the cell `get` would answer, or `None`; `trust` for a receipt this mesh computed and
214//! signed is `computed` (the HTTP layer's to say: the receipt's `computed_by` is the mesh).
215//! Before spec-0.4.2, `trust` for an engine-computed receipt was `verified`. A receipt of an asof-dependent
216//! function answers only the asof it was made for, which is what `get` returns.
217//!
218//! [`Engine`] is also a time-aware [`datumesh_core::Resolver`], with the answering rule above:
219//! `descriptor`, `receipt` and `manifest` from the store; `evaluate` looks a stored cell up
220//! and evaluates a computed cell's function (never reading its own receipts back), and
221//! `evaluation` gives that value with its lineage (the entries read), so that a verifier can
222//! report `E_INPUT_SUPERSEDED` (SPEC 10.1 step 7.6).
223//!
224//! # Example
225//!
226//! ```no_run
227//! use std::sync::Arc;
228//!
229//! use datumesh_core::{CellRef, SigningKey};
230//! use datumesh_engine::{Answer, Engine};
231//! use datumesh_store::{PgStore, Store};
232//!
233//! let store: Arc<dyn Store + Send + Sync> = Arc::new(PgStore::connect("postgres://localhost/datumesh").unwrap());
234//! // The store must hold the mesh's key document: it verifies every receipt stored.
235//! let engine = Engine::builder(store, "mesh.example.com").signing_key(SigningKey::from_seed(&[2; 32])).build().unwrap();
236//! let cell = CellRef::from_json(br#"{"args":{},"fn":"total","ns":"shop.example.com"}"#).unwrap();
237//! match engine.get(&cell, None).unwrap() {
238//!     Answer::Receipt(bytes) => println!("{}", String::from_utf8_lossy(&bytes)),
239//!     Answer::NotCovered { fault: Some(f) } => println!("no value: {f}"),
240//!     _ => println!("not covered"),
241//! }
242//! ```
243//!
244//! Feature `native-test` adds `native_test::NativeTest`, a runtime of Rust closures keyed by
245//! function hash, for tests.
246
247#![forbid(unsafe_code)]
248#![deny(missing_docs)]
249
250mod cache;
251mod check;
252mod clock;
253mod engine;
254mod error;
255mod eval;
256mod memo;
257#[cfg(feature = "native-test")]
258pub mod native_test;
259mod runtime;
260mod sign;
261mod slice;
262
263pub use clock::{Clock, SystemClock};
264pub use engine::{
265    Answer, Engine, EngineBuilder, MemoStats, SummaryFn, DEFAULT_DEPTH_LIMIT, DEFAULT_FUEL, DEFAULT_MEMO_CAPACITY,
266    DEFAULT_WORK_FACTOR,
267};
268pub use error::{ConfigError, EngineError, EvalError, StoreError};
269pub use runtime::{Budget, FnBinding, Input, Inputs, Member, Pattern, Runtime, SlicePattern};