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