Module common 

Types and methods generally useful for differential computation.

The contents operate on (id, time, diff) update streams and lattice operations, with key and value representation left to the caller: replaying histories in time order with meet-advanced buffers (ValueHistory, TimeHistory), determining the times at which a key’s reduction must be re-evaluated (discover_times), producing the join of two histories in time order (bilinear_wave), and cutting an output interval into batch descriptions along held capabilities (tile_descriptions).

Each item’s correctness is a property of its own inputs and outputs, so they can be used and tested in isolation; sequencing obligations that span calls (for example, where interesting-time seeds must come from) are stated at the item that imposes them and are the caller’s responsibility.

Re-exports

pub use crate::operators::ValueHistory;

Structs

DiscoverScratch

Reusable per-key scratch for discover_times: held once and threaded through every key, so replays and time buffers are cleared and refilled rather than reallocated per key.

KeyView

A one-key view into an input presentation: the read-only arguments discover_times needs about a single key — its slice [i0, i1) of the merged (id, time, diff) run p_in and the carried pending times.

TimeHistory

Replays a set of times in ascending order, maintaining the meet of the times not yet replayed and a deduplicated buffer of replayed times advanced by that meet. A cheaper ValueHistory for callers that need time structure only (no values, no cancellation).

Functions

bilinear_wave

Produces the join of two histories: every pair of edits, diffs multiplied and times joined, visited in time order. Repeatedly steps the history with the earlier un-replayed edit and multiplies it against the other’s buffer, which is consolidated under the meet of its remaining times as the wave advances — so work is bounded by the netted accumulation sizes rather than the raw history lengths.

discover_times

Determines the times in [lower, upper) at which a key’s reduction must be re-evaluated (moments), and the times at or beyond upper to carry into the next invocation (pended). Replays the key’s seed_times and pending times in ascending order, marking those that carry updates and closing the set under joins with the input and output histories’ times and with each other. No input collection is materialized, so peak memory is O(times); buffers are advanced by the meet of the times still to come, keeping a key with many distinct times linear rather than quadratic.

tile_descriptions

Cuts the interval [lower, upper) into consecutive batch descriptions along held, which must be sorted: the i-th cut point is the frontier formed by inserting held[i+1..] into upper, so description i covers the part of the interval not greater-or-equal any held time after held[i] (and not covered by an earlier description). Descriptions whose interval is empty are skipped. Returns the descriptions, the held time associated with each, and, per held index, the index of its description (None if skipped). A batch built to description i can be committed at the capability held[i].