Module engine 

The incremental view engine: the thing that flows deltas through a crate::plan::Plan.

docs/03-type-and-effect-system.md §3.8: “remaining updates by ±1 per event, never by recount.” Until now that sentence described an intention. This is the machine that makes it true, and docs/24-incremental-views-report.md is the measurement.

The one hard problem, and where it is solved

A Beck program’s state is a value: todos = durable(fold(apply_event, empty, events)) produces a whole new accumulator per event. A dataflow plan consumes changes. Something has to convert one into the other, and doing it by comparing the old and new accumulator entry by entry would be O(n) per event — which is the recount §3.8 exists to abolish, moved one level down where it is harder to see.

crate::pmap::PMap::diff is the conversion, and it is O(δ log n) because Map[K, V] is a persistent tree: two versions that differ by one insert share every subtree the insert did not pass through, by pointer, and the diff skips a shared subtree whole. So the delta at the source costs what the delta is worth. Everything downstream of that is ordinary differential dataflow.

Correctness before speed

The engine’s output must be identical to recomputing the view — not close, identical, because the rendered page is diffed into a patch stream and replayed bit for bit (§4.8). Three things make that checkable rather than hoped for:

1. Every operator the plan cannot decompose is a full recompute (Op::Pointwise), so a program the analysis does not understand is slow, never wrong.
2. Order is a key, not a sort. Each arrangement is a BTreeMap whose key reproduces the order the recompute would have produced (crate::plan), so map_values order, sort_by stability and concat_lists position all fall out of the key rather than out of a final pass.
3. An error resets the engine. A per-element function that fails leaves an arrangement half-updated, so Engine::render discards everything and the next call rebuilds. A stale arrangement is the one failure mode that would be invisible.

beck-cli/tests/incremental_engine.rs is the harness: every corpus program, every event of a generated log, engine against recompute, byte for byte.

What “changed” means, and why it is never a deep comparison

A pointwise operator re-runs when an input changed. Deciding that by structural equality would reintroduce the O(n) this module exists to remove, so same is a conservative test: scalars compare by value, collections and rendered trees by pointer. It answers “unchanged” only when it is certain, and “changed” costs a recompute that the old runtime did unconditionally.

Structs

Change

One entry’s fate at an operator’s output.

Engine

One subscriber’s arrangements over a Prepared plan.

Footprint

A deterministic byte estimate for the memory a subscription’s engine retains.

Prepared

A plan with every operator’s code prepared: one per program, shared by every subscription.

Reader

A reader of a SharedDataflow’s arrangements that renders nothing.

Retention

How long a shared dataflow keeps what a subscriber might still ask for.

SharedDataflow

The operators of a plan that do not read the session, arranged once for every subscriber.

Work

What one Engine::render cost, in units that do not depend on the machine.

Functions

fanout_footprint

What a whole fanout retains: the accumulator once, the shared dataflow once, and each subscriber’s own operators — with every shared allocation counted exactly once across all of them.

html_footprint

The same estimate for a rendered page, so “what the engine added” has a baseline.

Type Aliases

Key

What orders an entry inside an arrangement. See crate::plan for where each operator’s key comes from.