Skip to main content

Crate datumesh_engine

Crate datumesh_engine 

Source
Expand description

The Datumesh engine: the value of a cell as of a time.

Engine::get answers “the value of this cell as of A” with a receipt: for a stored cell, the publisher’s receipt from the store, unchanged; for a computed cell, a receipt the engine signs with the mesh’s key after evaluating the cell’s function through a Runtime, from the receipts of the cells it reads. Answers are memoised; computed versions are kept in the store (put_computed) and validated before they are reused. The store is a datumesh_store::Store (a PgStore: the trait is sealed); the API is synchronous and Engine is Send + Sync.

§Answering as of A

A receipt answers as of A only when its tx and its asof are both at or before A. A stored cell’s answer is stored_asof(cell, A). A computed cell’s is its computed version with the greatest asof <= A (computed_asof), once it is validated as of A; when none validates, the function is evaluated as of A and, unless the value equals that version’s (which is then kept), a new receipt is signed and stored. No asof means now: the clock reading taken once at the start of the request, which is also the issued of every receipt the request signs.

Function names resolve (resolve_name) as of A: the requested reference’s name, and every input name a function reads. Engine::get_cell takes a cell whose function hash is already pinned (the core’s CellRef carries no hash).

§Computed receipts

computed_by is <mesh host>#<key id>, publisher the cell’s namespace, inputs the hashes of the receipts read, tx the latest input tx (SPEC 8.2), issued the request’s clock reading, valid the cell’s valid-time arguments, summary from the engine’s configuration (EngineBuilder::summary: the descriptor has none, and adding one would change function hashes), and licence by licence inheritance (below; since 0.4.1).

asof is the latest of its input asofs (slice members included), the start of every name binding it relied on, every T of a transaction-time read and every to of a version read (SPEC 8.2 rule 2), so that the receipt is true as of its own asof and recomputes there; for an asof-dependent function, the evaluation asof (below). tx is the latest input tx, members included (the earliest instant when there is none, as when the only inputs are empty slices):

  • an input’s asof is where its answer starts: its receipt’s asof, except for an input answered by a version that was kept or validated across a change of its own inputs, which counts from where its value was established again;

  • the names relied on are the function names read, transitively (an input’s own inputs’ names included, and a function’s own name when it reads itself, as fib does); each binding’s start is when the binding answering as of A began (Store::resolve_binding): a name bound again, even to the same function, begins again. The requested cell’s own name is not among them: its receipt pins the function hash.

  • a value that rests on a fault a read returned and the runtime caught (SPEC 15.12: otherwise over a computed slice with a faulting member) counts from where that fault holds: the latest input asof and binding start of the faulted evaluation. (SPEC 8.2 names no candidate for it; without one the receipt would not recompute at its asof.)

The asof is never later than A. Between it and A the inputs and the bindings are those read, so the one receipt answers every request in between (and later ones, after validation).

§Licence inheritance (spec-0.4.3, since 0.4.1)

A computed receipt’s licence is the result of SPEC 8.5 (datumesh_core::inherit_licence) over the licences of the input receipts it lists, one per receipt, every member of a slice entry included, at its issued: no inputs, the mesh’s own licence (EngineBuilder::licence); open inputs only, the highest tier and within it the identifier listed last; one restricted licence, only if the function’s publisher declared it for the function, open at issued. The declarations are those of the key document of the host of cell.ns (even when the mesh signing is another host), read from the store (Store::namespace) and only when a restricted input needs them; a host whose key document the store does not hold declares nothing. Stored receipts are untouched.

A refusal (share_alike_conflict, restricted_conflict, not_declared, declaration_not_open) is EngineError::Unlicensed, with the refused cell and the reason: nothing is signed or stored for the request, and a cell that reads a refused cell is refused too (the same error). The HTTP layer answers unlicensed (403).

A computed version from the store (or the memo) is reused only while its licence is allowed: the rule over the input licences now read, judged at the version’s own issued (as the entitlement check, SPEC 10.3, judges it: a declaration closed since does not matter), or giving that licence now. Otherwise the function is evaluated again and the cell is signed again with the rule’s licence (a receipt signed before for exactly these inputs with an allowed licence is reused), or refused: a receipt signed before 0.4.1 under the configured licence over inputs that give another, or an input republished with the same value under another licence (early cutoff keeps the value, not the licence). Recomputation for a verifier (Resolver::evaluation) signs nothing and does not apply the rule to the cell it evaluates (SPEC 8.5: never in verification).

Cost: the licences of a stored slice’s members come from their receipts, read from the store (cached by hash) when a receipt over the slice is signed or validated.

§Slices and transaction-time reads (spec-0.4.0)

Inputs::read_slice reads the members of a slice as of A, in SPEC 15.13 key order: of a stored function, its cells matching the pattern with a version answering then (Store::slice_members); of a computed one, the cells of its declared extent within the pattern (a range over a date or integer number argument without an extent: every day or integer), each a computed cell the engine answers like any input, memoised, with the cycle and depth rules (a member on the evaluation stack is a EngineError::Cycle), evaluated in key order up to the first without a value, which makes the read the fault E_FORMULA_ABSENT (later members are neither evaluated nor charged). A slice read is one inputs entry slice:<slice id>:<members hash>; its manifest is stored (put_manifest) with the receipts, and served by Engine as a resolver. Inputs::read_versions reads a version slice of a stored cell, Inputs::read_asof a cell as of a transaction time T (its name resolved as of T; a computed cell evaluated as of T), E_FORMULA_FUTURE when T (or to) is after A.

§Blob content (spec-0.4.2)

Inputs::read_blob gives a blob’s content (for text_of, SPEC 15.7) from the store, checked against the blob’s length and SHA-256. Content the engine cannot obtain or check is EngineError::BlobUnavailable, the evaluator’s failure (E_EVAL_UNAVAILABLE), never not_covered. The content is no inputs entry; the runtime charges its fuel. Recomputing through Engine as a resolver obtains it again from the store.

§Faults

A runtime’s EvalError::Fault (E_FORMULA_DIV_ZERO, E_FORMULA_DOMAIN, E_FORMULA_RANGE, E_FORMULA_EMPTY, E_FORMULA_ABSENT, E_FORMULA_FUTURE) gives the cell no value: Answer::NotCovered with the fault, no receipt, nothing stored for the cell (what the request computed before it is kept, as for an input with no value). A reader of a faulted cell gets the same fault, which it may catch. A value that rests on a caught fault is signed, but its version is not kept for validation, nor in the memo: no receipt lists what the fault rested on.

A fault is memoised as the cell’s answer is (SPEC 15.12, since 0.4.2): the cell is evaluated once while nothing it read has changed, and a reader of a faulted cell is answered from the memo too. A fault that rests on an absent slice member or on an input with no value is not memoised.

§Suspension

A request that must sign a receipt under a suspended mesh namespace (SPEC 9.9) fails with EngineError::NamespaceSuspended before any write: nothing is signed or stored. Reads, verification and the receipts already stored go on, and datumesh_core::Resolver::evaluate gives no value where a new receipt would be needed. Since 0.4.2.

§Asof-dependent functions

A function whose value may change with the asof alone (SPEC 15.12: asof(), a bounded latest), as its runtime declares (Runtime::asof_dependent) or as it shows by reading Inputs::asof, has the evaluation asof as its receipt’s asof: one receipt per requested asof. The memo keeps it for that asof only, and a stored version is reused only as of its own asof (SPEC 5.5: a mesh MUST NOT serve it as ok for another). A function that reads the asof without declaring it is not kept as a computed version at all. A reader of such a cell is not itself asof-dependent: its version validates by its inputs.

Inputs::asof_compare compares a time with the asof without that dependence when the answer cannot change later (a time at or before the asof becomes an asof candidate of the receipt; a time after it makes the evaluation asof-dependent), and Inputs::binding_peek looks a binding up without relying on it (since 0.3.1).

A function that reads nothing has tx = asof = 0001-01-01T00:00:00.000000Z: its value does not depend on time.

§Receipt identity

Receipt identity is per computed version, keyed on (cell, tx, asof). Two valid receipts for the same value may exist with different lineage: when an input changes and changes back, validation by value (early cutoff) can accept either version, so which one answers depends on which versions earlier requests stored. The value is always the same.

A backdated correction (an input superseded at a tx earlier than the receipt’s own tx) would give a second version under an existing key, which the store refuses. The engine keeps the stored version, which answers correctly, and reuses a receipt it signed before for exactly the current inputs. The old receipt stays signature-valid and answers the asofs it was issued for; it no longer recomputes, because one of its inputs has been superseded. Recomputation verifies “given these exact inputs”, and the inputs it cites are still the ones it used: the receipt is historical, not wrong.

§Memo, validation and early cutoff

A version is valid as of A when every input receipt it lists, its name still resolving to its function, gives as of A the same receipt or the same value (early cutoff), and every slice entry, its function’s name still resolving to the slice’s function, has as of A the same members hash, or members that are the same cells with the same values. Validation reads only the store (manifests included), so it is always available, and correctness rests on it alone. Versions whose receipts do not say all validation needs are not kept as computed versions: those resting on a caught fault, on a read at a transaction time (which a receipt does not mark), or on the asof read by a function not declared asof-dependent; they are evaluated again by later requests (their inputs memoised).

The memo keeps each answer with the interval of asofs it holds for (a stored version from its asof to the next version’s; a computed answer the intersection of its inputs’) and the names it depends on, which are resolved again on every use. Adding a stored version must be reported with Engine::stored_version_added: it drops the cell’s answers and those of every cell that read them (the dirty set, through the memo’s own index of the cell-level dependents of the answers it holds), and those of every answer that read a slice the cell falls into (a correction of a member, a late sample, a new member), matched by the slice’s pattern: a correction to day ten of a running total drops days ten onwards only. Dropped answers are rechecked from memory before the store is asked, so after a change that early cutoff stops, the unchanged part of a graph costs no store query. Evaluations running across an invalidation cannot keep what they read (revision marks). A process that writes versions without telling the engine leaves its memo stale until Engine::clear_memo; EngineBuilder::memo_capacity(0) validates every request through the store instead.

Early-cutoff records need not be persisted: a version kept because its recomputed value is the same stays the version in the store, so a fresh engine (after a restart) validates the readers above it by receipt hash and recomputes only the cell whose inputs changed, as the first engine did (tests/early_cutoff.rs).

§Recursion and suspension

A function may read its own name with other arguments (fib(n) reads fib(n - 1)). Evaluation runs on an explicit stack of frames on the heap, never native recursion. When a runtime reads a computed input not answered yet, Inputs::read returns EvalError::Suspended; the engine pushes a frame for the input and, once it is answered, runs the suspended function again from the start, its earlier reads now answered at once from the request. A cell reappearing on the stack is EngineError::Cycle, which names its path (since 0.5.0). Past the depth limit (default 10,000) the evaluation does not fail: it evaluates the deepest pending cell first as a root of its own, within the same request (since 0.5.0), so the answer and its receipts are those of a shallow evaluation; fuel and work still bound it (EngineError::BudgetExceeded, EngineError::WorkExceeded).

§Scenarios

Engine::whatif (since 0.5.0) evaluates a cell with overrides in place, as a labelled scenario: nothing is written, signed or memoised, and the answer has no receipt. A solve (Solve) finds the value of one number cell by bisection.

The cost of the restart scheme: a function whose k computed inputs are all missing when it starts runs up to k + 1 times and re-reads its earlier inputs each time (O(k^2) reads at worst). A chain runs each link twice; fib(n) runs fib(2) three times and every other fib(k) twice. Validating a stored version first makes its inputs available before the function runs, so a recomputation after a change usually runs once.

A slice read over a computed function whose members are not answered yet suspends once: the engine evaluates every missing member in turn, then runs the reader again.

§Budget and single-flight

Fuel is normative (SPEC 15.12): each read costs what the fuel table says (a single-cell read 1, a slice read 1 + members once the members are obtained, a version read 1 + versions) and the runtime charges its own steps (Budget::charge). Each run of a runtime is an attempt with a meter of its own; the fuel of a cell’s evaluation is that of its last, completed attempt (Budget::used), so it does not depend on how many times the engine restarted it. A request’s fuel (EngineBuilder::fuel, default 10,000,000) bounds the sum over the evaluations it completes; at every charge the engine checks a lower bound of that sum (a suspended attempt’s re-run charges at least as much), so the request fails with EngineError::BudgetExceeded exactly when its normative fuel exceeds the limit. The total work, discarded attempts and validation reads included, has its own limit (EngineBuilder::work_limit, default 16 times the fuel: EngineError::WorkExceeded). When either runs out nothing is stored: new receipts, manifests and versions are written only after a request has succeeded.

Evaluations run one at a time per engine, so concurrent requests for the same uncomputed cell evaluate it once: the second finds the first’s answer. Answers from the memo and of stored cells do not wait.

§For the HTTP layer

Engine::get resultMeaningEnvelope (SPEC 5.5), in spirit
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
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 nonenot_covered
Ok(Answer::NotCovered { fault: Some(f) })the cell’s evaluation faulted (SPEC 15.12): it has no value, deterministicallynot_covered, fault = f.as_str() (E_FORMULA_DIV_ZERO, …)
Err(Invalid(e))a malformed request (asof, slice, arguments against the signature)bad_request, error = e.code()
Err(NameUnresolved { .. })an input’s name has no binding as of Aerror, E_FN_UNAVAILABLE
Err(UndeclaredInput { .. })a function read a name it does not declareerror, E_INPUT_UNDECLARED
Err(NoRuntime { .. }), Runtime, Cycle, DepthExceeded, BudgetExceeded, WorkExceeded, BlobUnavailablethe mesh could not evaluate the functionerror, E_EVAL_UNAVAILABLE (or stale with an earlier receipt; never for an asof-dependent cell’s receipt of another asof)
Err(Unlicensed { .. })licence inheritance refuses the cell, or a cell it reads (SPEC 8.5; since 0.4.1)unlicensed (403)
Err(Sign(e))an input’s asof is later than the clock (E_TIME_ORDER)error, E_TIME_ORDER
Err(Store(e))the store failederror, E_INPUT_UNAVAILABLE (or stale)

Since spec-0.4.2: a request pinned to a function hash (fn_hash=) is Engine::get_cell with that hash (an unknown hash is plain not_covered); an unbound name (not_covered with E_NAME_UNBOUND) is told apart with Engine::resolve, which gives the cell get would answer, or None; trust for a receipt this mesh computed and signed is computed (the HTTP layer’s to say: the receipt’s computed_by is the mesh). Before spec-0.4.2, trust for an engine-computed receipt was verified. A receipt of an asof-dependent function answers only the asof it was made for, which is what get returns.

Engine is also a time-aware datumesh_core::Resolver, with the answering rule above: descriptor, receipt and manifest from the store; evaluate looks a stored cell up and evaluates a computed cell’s function (never reading its own receipts back), and evaluation gives that value with its lineage (the entries read), so that a verifier can report E_INPUT_SUPERSEDED (SPEC 10.1 step 7.6).

§Example

use std::sync::Arc;

use datumesh_core::{CellRef, SigningKey};
use datumesh_engine::{Answer, Engine};
use datumesh_store::{PgStore, Store};

let store: Arc<dyn Store + Send + Sync> = Arc::new(PgStore::connect("postgres://localhost/datumesh").unwrap());
// The store must hold the mesh's key document: it verifies every receipt stored.
let engine = Engine::builder(store, "mesh.example.com").signing_key(SigningKey::from_seed(&[2; 32])).build().unwrap();
let cell = CellRef::from_json(br#"{"args":{},"fn":"total","ns":"shop.example.com"}"#).unwrap();
match engine.get(&cell, None).unwrap() {
    Answer::Receipt(bytes) => println!("{}", String::from_utf8_lossy(&bytes)),
    Answer::NotCovered { fault: Some(f) } => println!("no value: {f}"),
    _ => println!("not covered"),
}

Feature native-test adds native_test::NativeTest, a runtime of Rust closures keyed by function hash, for tests.

Modules§

native_test
NativeTest (feature native-test): a runtime of Rust closures keyed by function hash, for tests and benchmarks. Its language is native_test.

Structs§

Budget
The fuel of an evaluation attempt, on the request’s meter.
Engine
The engine: answers the value of a cell as of a time. See the crate documentation.
EngineBuilder
Builds an Engine: Engine::builder.
FnBinding
A function name’s binding (Inputs::binding).
Input
What a read gave: the value and the receipt stating it.
Member
A member of a slice (Inputs::read_slice): the member cell’s arguments and its input.
MemoStats
Sizes of the memo and of the dirty set (Engine::memo_stats).
Overrides
The overrides of a scenario: value overrides and slice overrides, in the order given.
ScenarioAnswer
A scenario’s answer (Engine::whatif): the value of the cell as of the asof, with the overrides in place. It is labelled a scenario: it has no receipt and is never stored.
Solve
A solve for Engine::whatif: find the value of vary (a number cell) in [lo, hi] at which target (a number cell) equals equals. All four are number scalars. The value found carries 15 significant digits (rounded half-even), and the answer is the requested cell’s value under it: the target’s, when the requested cell is the target.
StoreError
A store failure, as the engine reports it.
SystemClock
The system clock (UTC, microseconds).

Enums§

Answer
The answer to “the value of this cell as of A”.
ConfigError
Why an engine could not be built (EngineBuilder::build).
EngineError
What Engine::get can fail with. For how each maps to a response envelope, see the crate documentation.
EvalError
What evaluating a function can fail with: returned by Inputs::read and Budget::charge, and by a Runtime.
Pattern
One argument of a slice pattern (Inputs::read_slice).
ScenarioOverride
An override of a scenario, as its answer lists it.

Constants§

DEFAULT_DEPTH_LIMIT
The default depth limit: frames on the evaluation stack.
DEFAULT_FUEL
The default fuel of a request: runtime steps plus input reads.
DEFAULT_MEMO_CAPACITY
The default memo capacity, in entries.
DEFAULT_WORK_FACTOR
The default work limit of a request, as a multiple of its fuel.

Traits§

Clock
Where the engine reads the time. It reads it once per request: that reading is the issued of every receipt the request signs, and the request’s asof when none is given.
Inputs
How a runtime reads the cells its function depends on, and the evaluation’s asof.
Runtime
The evaluator of one function language (code.lang of a descriptor).

Type Aliases§

SlicePattern
A slice pattern: every argument of the function, by name.
SummaryFn
The function computing a computed receipt’s summary.