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 and the start of every name binding it relied on
34//! (SPEC 8.2 rule 2 for the inputs), so that the receipt is true as of its own `asof` and
35//! recomputes there:
36//!
37//! * an input's asof is where its answer starts: its receipt's `asof`, except for an input
38//! answered by a version that was kept or validated across a change of its own inputs,
39//! which counts from where its value was established again;
40//! * the names relied on are the function names read, transitively (an input's own inputs'
41//! names included, and a function's own name when it reads itself, as fib does); each
42//! binding's start is when the binding answering as of A began
43//! ([`Store::resolve_binding`](datumesh_store::Store::resolve_binding)): a name bound
44//! again, even to the same function, begins again. The requested cell's own name is not
45//! among them: its receipt pins the function hash.
46//!
47//! The asof is never later than A. Between it and A the inputs and the bindings are those
48//! read, so the one receipt answers every request in between (and later ones, after
49//! validation).
50//!
51//! A function that reads nothing has `tx` = `asof` = `0001-01-01T00:00:00.000000Z`: its value
52//! does not depend on time.
53//!
54//! ## Receipt identity
55//!
56//! Receipt identity is per computed version, keyed on (cell, `tx`, `asof`). Two valid
57//! receipts for the same value may exist with different lineage: when an input changes and
58//! changes back, validation by value (early cutoff) can accept either version, so which one
59//! answers depends on which versions earlier requests stored. The value is always the same.
60//!
61//! A backdated correction (an input superseded at a `tx` earlier than the receipt's own `tx`)
62//! would give a second version under an existing key, which the store refuses. The engine
63//! keeps the stored version, which answers correctly, and reuses a receipt it signed before
64//! for exactly the current inputs. The old receipt stays signature-valid and answers the
65//! asofs it was issued for; it no longer recomputes, because one of its inputs has been
66//! superseded. Recomputation verifies "given these exact inputs", and the inputs it cites are
67//! still the ones it used: the receipt is historical, not wrong.
68//!
69//! # Memo, validation and early cutoff
70//!
71//! A version is valid as of A when every input receipt it lists, its name still resolving to
72//! its function, gives as of A the same receipt or the same value (early cutoff). Validation
73//! reads only the store, so it is always available, and correctness rests on it alone.
74//!
75//! The memo keeps each answer with the interval of asofs it holds for (a stored version from
76//! its asof to the next version's; a computed answer the intersection of its inputs') and the
77//! names it depends on, which are resolved again on every use. Adding a stored version must be
78//! reported with [`Engine::stored_version_added`]: it drops the cell's answers and those of
79//! every cell that read them (the dirty set, through the memo's own index of the cell-level
80//! dependents of the answers it holds). Dropped answers are rechecked from memory before the
81//! store is asked, so after a change that early cutoff stops, the unchanged part of a graph
82//! costs no store query. Evaluations running across an invalidation cannot keep what they
83//! read (revision marks). A process that writes versions without telling the engine leaves its
84//! memo stale until [`Engine::clear_memo`]; [`EngineBuilder::memo_capacity`]`(0)` validates
85//! every request through the store instead.
86//!
87//! Early-cutoff records need not be persisted: a version kept because its recomputed value is
88//! the same stays the version in the store, so a fresh engine (after a restart) validates the
89//! readers above it by receipt hash and recomputes only the cell whose inputs changed, as the
90//! first engine did (`tests/early_cutoff.rs`).
91//!
92//! # Recursion and suspension
93//!
94//! A function may read its own name with other arguments (fib(n) reads fib(n - 1)).
95//! Evaluation runs on an explicit stack of frames on the heap, never native recursion. When a
96//! runtime reads a computed input not answered yet, [`Inputs::read`] returns
97//! [`EvalError::Suspended`]; the engine pushes a frame for the input and, once it is answered,
98//! runs the suspended function again from the start, its earlier reads now answered at once
99//! from the request. A cell reappearing on the stack is [`EngineError::Cycle`]; more frames
100//! than the depth limit (default 10,000) is [`EngineError::DepthExceeded`].
101//!
102//! The cost of the restart scheme: a function whose k computed inputs are all missing when it
103//! starts runs up to k + 1 times and re-reads its earlier inputs each time (O(k^2) reads at
104//! worst). A chain runs each link twice; fib(n) runs fib(2) three times and every other fib(k)
105//! twice. Validating a stored version first makes its inputs available before the function
106//! runs, so a recomputation after a change usually runs once.
107//!
108//! # Budget and single-flight
109//!
110//! Each request has a fuel ([`EngineBuilder::fuel`], default 10,000,000): runtime steps
111//! ([`Budget::charge`]) plus input reads, validation's included. When it runs out the request
112//! is [`EngineError::BudgetExceeded`] and nothing is stored: new receipts and versions are
113//! written only after a request has succeeded.
114//!
115//! Evaluations run one at a time per engine, so concurrent requests for the same uncomputed
116//! cell evaluate it once: the second finds the first's answer. Answers from the memo and of
117//! stored cells do not wait.
118//!
119//! # For the HTTP layer
120//!
121//! | `Engine::get` result | Meaning | Envelope (SPEC 5.5), in spirit |
122//! |---|---|---|
123//! | `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 |
124//! | `Ok(Answer::NotCovered)` | 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` |
125//! | `Err(Invalid(e))` | a malformed request (asof, slice, arguments against the signature) | `bad_request`, `error` = `e.code()` |
126//! | `Err(NameUnresolved { .. })` | an input's name has no binding as of A | `error`, `E_FN_UNAVAILABLE` |
127//! | `Err(UndeclaredInput { .. })` | a function read a name it does not declare | `error`, `E_INPUT_UNDECLARED` |
128//! | `Err(NoRuntime { .. })`, `Runtime`, `Cycle`, `DepthExceeded`, `BudgetExceeded` | the mesh could not evaluate the function | `error`, `E_EVAL_UNAVAILABLE` (or `stale` with an earlier receipt) |
129//! | `Err(Sign(e))` | an input's `asof` is later than the clock (`E_TIME_ORDER`) | `error`, `E_TIME_ORDER` |
130//! | `Err(Store(e))` | the store failed | `error`, `E_INPUT_UNAVAILABLE` (or `stale`) |
131//!
132//! [`Engine`] is also a time-aware [`datumesh_core::Resolver`], with the answering rule above:
133//! `descriptor` and `receipt` from the store; `evaluate` looks a stored cell up and evaluates
134//! a computed cell's function (never reading its own receipts back).
135//!
136//! # Example
137//!
138//! ```no_run
139//! use std::sync::Arc;
140//!
141//! use datumesh_core::{CellRef, SigningKey};
142//! use datumesh_engine::{Answer, Engine};
143//! use datumesh_store::{PgStore, Store};
144//!
145//! let store: Arc<dyn Store + Send + Sync> = Arc::new(PgStore::connect("postgres://localhost/datumesh").unwrap());
146//! // The store must hold the mesh's key document: it verifies every receipt stored.
147//! let engine = Engine::builder(store, "mesh.example.com").signing_key(SigningKey::from_seed(&[2; 32])).build().unwrap();
148//! let cell = CellRef::from_json(br#"{"args":{},"fn":"total","ns":"shop.example.com"}"#).unwrap();
149//! match engine.get(&cell, None).unwrap() {
150//! Answer::Receipt(bytes) => println!("{}", String::from_utf8_lossy(&bytes)),
151//! Answer::NotCovered => println!("not covered"),
152//! }
153//! ```
154//!
155//! Feature `native-test` adds `native_test::NativeTest`, a runtime of Rust closures keyed by
156//! function hash, for tests.
157
158#![forbid(unsafe_code)]
159#![deny(missing_docs)]
160
161mod cache;
162mod check;
163mod clock;
164mod engine;
165mod error;
166mod eval;
167mod memo;
168#[cfg(feature = "native-test")]
169pub mod native_test;
170mod runtime;
171mod sign;
172
173pub use clock::{Clock, SystemClock};
174pub use engine::{
175 Answer, Engine, EngineBuilder, MemoStats, SummaryFn, DEFAULT_DEPTH_LIMIT, DEFAULT_FUEL, DEFAULT_MEMO_CAPACITY,
176};
177pub use error::{ConfigError, EngineError, EvalError, StoreError};
178pub use runtime::{Budget, Inputs, Runtime};