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