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