Crate rindle 

rindle — an incremental view maintenance (IVM) engine

Build a query, hydrate its result, and push source changes to update that result incrementally. This crate provides the raw graph, query builder, memory source, and optional WebAssembly bindings. It is based on Zero’s ZQL dataflow engine.

Applications that need SQLite persistence and automatic SQL change capture should start with rindle-replica. Custom SQLite sources live in the separate rindle-sqlite crate. This core crate does not link SQLite or require a C toolchain with its default features.

Public entry points

• Build a query — Query / table (fluent) or an Ast (Zero’s wire JSON, via serde), then build_pipeline to lower it into a wired arena Graph.
• Run it — hydrate the Graph over a MemorySource, push SourceChanges, and read the maintained View / ViewData. A rindle-sqlite::TableSource can supply a SQLite leaf.
• Import core types — use rindle::graph::{Graph, NodeId}, rindle::change::SourceChange, and rindle::value::{OwnedRow, OwnedValue}. The fluent table builder is re-exported at the crate root.
• Errors — fallible paths return RindleError (see Fault model below).

Feature flags

memory is enabled by default and required by this crate. There is no sqlite feature; use the rindle-sqlite crate for that backend. serde enables AST serialization, and wasm adds the JavaScript bindings plus memory and serde. observe enables tracing, metrics enables process counters, and testkit exposes the test oracle. fast-alloc opts into mimalloc and its native toolchain.

Design

The arena + NodeId operator graph, RAII (Drop) cursor cleanup, the COW Arc<Node> B+tree, and the reentrant-fetch-during-push thesis that motivates them are written up in docs/DESIGN.md.

Fault model (productionization WS02)

The engine is built to be survivable in a server: no data-reachable input or transient backend error should abort the process or silently corrupt view state.

• Use the try_* entry points in production — Graph::try_source_push, Graph::try_hydrate, Graph::try_add_source — which return RindleError. Their infallible peers (Graph::source_push / Graph::hydrate / Graph::add_source) .expect the result and are for tests/prototyping.
• Strict change validation (Graph::set_validate_changes, WS02.2): off by default (hot-path parity). When on, a malformed change stream (ADD of an existing row, REMOVE/EDIT of an absent row) returns RindleError::ConsistencyViolation — in release, not a stripped debug_assert!.
• Ingest validation (WS02.4): Graph::try_add_source rejects a wrong-width row with RindleError::SchemaViolation before it reaches an unchecked index.
• Predicates never crash on a column/literal type mismatch (WS02.4).
• SQLite operator-storage errors (the spill backend) park a RindleError on the graph’s runtime-error sink and surface via take_runtime_error instead of .expect-aborting; spilled blobs carry a format-version byte and a mismatch is a typed error (rebuild-from-source), not a panic (WS02.3 / WS09.3).
• Panic taxonomy (the invariant module, WS02.1): every remaining panic is a build-time / internal invariant; data-reachable failures are RindleError.
• Server fault isolation (WS02.5): build the server with --profile release-server (panic = "unwind") and drive mutations through Graph::source_push_isolated to contain a residual panic to one mutation (then discard + rebuild the view — never reuse a torn one). The wasm client keeps panic = "abort" plus a console panic hook.

Client (wasm/JS)

With the wasm feature, wasm::RindleView drives the engine from JavaScript over a 5-call lifecycle (the wasm module has the full rustdoc):

1. RindleView.build(astJson, schemas, data) — lower an AST (Zero’s wire JSON) + a { table: SchemaSpec } map (+ optional { table: row[][] } initial data), hydrate, return a handle. BuildError/RindleError throw as a JS Error with a .kind tag — never a wasm abort.
2. view.data() — the materialized tree as a JS value: { <col>: v, …, <relName>: [child…] | child | null }, in-view relationships only.
3. view.push(table, { type: 'add'|'remove'|'edit', row, old? }) — one source change (does not flush).
4. view.flush() — notify subscribers if the view changed. This is a notification boundary, not a durable SQL transaction.
5. view.subscribe((data, resultType) => …) — fired once immediately, then when a changed view flushes or its result type changes. Release the generated JS handle with .free() when finished.

JavaScript numbers enter the number domain; the boundary rejects bigint and outgoing exact integers outside the JS safe-integer range. Strings stay strings; objects and arrays become JSON cells. Build the artifact with pnpm run build:wasm from the repository root. Concurrency: one Graph/RindleView per thread (it is !Send); scale with N independent graphs and message passing, never a shared Arc<Mutex<Graph>>.

Modules

btree

Primitive #4 — the COW B+tree (the clean win). Spike for spec 04-sources-memory-and-btree.md §4.4 (the M3 milestone) and the two open questions it flags as the #1 implementation risk:

canon

The canonical value-equivalence key (CanonVal / CanonKey) — the join family’s grouping key, the limiters’ partition identity, and a parameterized query family’s binding (design 310, D1). Lives in rindle-value (below the engine, so rindle-wire can name it) and is re-exported here as the rindle::canon namespace. The canonical value-equivalence key — CanonVal / CanonKey — one Hash + Eq encoding of the engine’s exact equality class, shared by every consumer that must agree on “these two cells are the same value”:

change

The dataflow value types: Node, the lazy relationship stream, Change, SourceChange, Constraint, FetchRequest, and the overlay snapshots.

family

Parameterized query families (design 310 §4): BindingSet — the binding-set handle a family root connection’s membership predicate reads — and FamilyPipeline, what build_family_pipeline returns and what Graph::bind_family_partition / unbind_family_partition / hydrate_family drive. See src/family.rs. Parameterized query families — the engine half of design 310 (designs/310-PARAMETERIZED-QUERY-FAMILIES-DESIGN.md §4).

graph

Primitive #1: the operator graph as an arena + NodeId, NOT Rc<RefCell<dyn Operator>>.

journal_frame

The cross-process journal frame envelope (FrameHeader + FrameKind): the typed header (kind / committed_at / run identity + totals) in front of an opaque change payload wherever journal entries live — the hctree master’s hct_journal payload column and the S3 archival segments (rindle-backup). Pure bytes, no deps. See src/journal_frame.rs, designs-implemented/211-HCTREE-LEADER-CDC-DESIGN.md §4.1, and designs-implemented/212-JOURNAL-S3-SHIPPING-DESIGN.md §2.2. The cross-process journal frame envelope — the typed header in front of every opaque change payload (designs-implemented/211-HCTREE-LEADER-CDC-DESIGN.md §4.1).

js_safe

JS-boundary safe-integer walkers (productionization 09.8, design 226 Stage A): the opt-in strict_i64 check that refuses an out-of-Number.MAX_SAFE_INTEGER Int crossing to JS with a typed error instead of silently rounding it. JS-boundary safe-integer enforcement (productionization 09.8; design 226 Stage A).

metrics

Build-gated process metrics (WS03, the metrics feature): metric_inc!/… fold each seam into a relaxed atomic add on a process-global registry the daemon’s Prometheus endpoint reads, and to argument-consuming no-ops (no global linked) otherwise. The scrape-path sibling of observe; see src/metrics.rs. Build-gated process metrics (the metrics feature) — the scrape-path sibling of the observe shim.

op

Spec 06/07 operators implemented outside graph.rs — the operator fan-out seam.

push_index

The guarded push fan-out reverse index (designs/205-GUARDED-PUSH-FANOUT-DESIGN.md): prunes a source write’s per-connection fan-out to the connections whose equality-shaped where guard could match. A conservative superset index — never under-approximates — so filter_push stays the exact gate. Guarded push fan-out: a reverse predicate index over source connections (designs/205-GUARDED-PUSH-FANOUT-DESIGN.md).

source_common

Backend-agnostic source machinery, shared by the memory (BTree) and SQLite leaves. This module references no BTree, no rusqlite, AND no Node — it is generic over S: RowStream and deals only in rows (OwnedRow) and source changes (SourceChange). It is the seam the spec calls source_common (04 §4.6): the two leaves differ only in the concrete S they pass in.

storage

Spec 10 — operator scratch state: the small, sorted, string-keyed side-table a stateful operator (Take, Cap) keeps bookkeeping in across fetch/push calls. Ports zql/src/ivm/operator.ts:132 Storage and zql/src/ivm/memory-storage.ts.

value

The value vocabulary — moved to the dependency-free rindle-value crate and re-exported here, so rindle::value::… is unchanged for every consumer. Crates that need only cells (the write plane, the CDC apply plane) depend on rindle-value directly and therefore cannot reach the engine at all. The canonical value/row model — the union that graduates into 01-foundations §2–§3, refined by the SQLite step-buffer lifetime (the forcing function). One model serves BOTH leaf backends:

Structs

Ast

The query AST (Ast, ast.ts:217-243). table is the only required field; every other wire field is optional. Default enables struct-update syntax for hand-written test expectations. Deserializes from the JS wire JSON (camelCase keys; absent ⇒ None/empty).

Batch

One transaction’s flat changes (or the seq-0 hydrate snapshot). events apply in order; the receiver renders only after the whole batch (FLAT-CHANGES-DESIGN.md §5.4).

Bound

A paging lower bound (Bound, ast.ts:199-202). row is a partial wire row — the bound columns by name (a BTreeMap for deterministic key order, matching the wire object). exclusive maps to the runtime Basis (false ⇒ At/inclusive, true ⇒ After/exclusive) at lowering, in the builder/Skip (spec 03 §3.5).

CaughtNode

A fully-materialized node: the row cells plus eagerly drained relationships. The comparison unit for a fetch/push assertion, and the owned node a Graph::add_change_sink consumer receives.

Cond

A boolean condition group under construction — the building block for nested AND/OR filter trees. You don’t make one directly; a fresh Cond is handed to the closure of Query::where_any / Query::where_all (and the nested Cond::any / Cond::all). Add clauses by chaining, just like Query.

CorrelatedSubquery

A child query joined to its parent by a key Correlation (CorrelatedSubquery, ast.ts:250-265). Used both as a materialized relationship (Ast::related) and inside a CorrelatedSubqueryCondition.

CorrelatedSubqueryCondition

A (NOT) EXISTS condition (CorrelatedSubqueryCondition, ast.ts:324-331).

Correlation

The join key pair (Correlation, ast.ts:245-248). parent_field[i] on the parent correlates with child_field[i] on the child; both non-empty, same length.

Entry

One materialized node in the view tree (ports MetaEntry). Arc-shared so unchanged subtrees keep pointer identity across an immutable [apply_change].

ExistsOpts

Options for a where_exists / where_not_exists correlated subquery — an extensible struct so the common case stays where_exists(f) and opt-in behaviors ride a ..Default::default() struct via the _with variants.

FlatChange

One flat change: the root→leaf parent path, then the op applied at the reached level. An empty path means the op applies at the top level.

Hello

The subscription handshake, sent once before any Batch.

LikeMatcher

A compiled SQL LIKE pattern (07 §4 / filter.ts). % matches any byte run, _ matches exactly one byte. Compiled once (the builder lowers the literal pattern) and matched per row with a classic backtracking glob walk.

MemorySource

The in-memory source. fetch seeks a BTreeCursor over a COW snapshot and drives it through source_common; write_change path-copies via Rc::make_mut so in-flight cursors keep their snapshot (the load-bearing COW property — §6).

OrderPart

One (field, direction) of an ordering (OrderPart, ast.ts:208). A wire 2-tuple — serializes as the JSON array ["field", "asc"].

Parent

A reference to a parent-row column (see ParentRow::col). As a where value it defines a Correlation, not a filter.

ParentRow

A handle to the parent row, handed to a sub / where_exists closure. row.col("creatorID") yields a Parent reference to that parent column.

PathSeg

One hop of a FlatChange path: descend relationship rel, locating the parent at the current level by parent_row (the full sort-key locator).

Publisher

Sender side: stamps batches with the subscription epoch + schema_fp and drives the gap-free seq. Graph-agnostic — the caller drains the change-sink and hands the CaughtChanges here.

Query

The fluent builder. Holds the Ast under construction plus a pending correlation — the (child, parent) field pairs siphoned from where(child, row.col(parent)) calls, which the enclosing sub / where_exists drains.

Receiver

The reference receiver: holds the hierarchical view Schema (the shipped query schema) and the reconstructed top-level list (root[""]).

RecvNode

A reconstructed node: row + multi-path refcount + per-slot child lists.

SimpleCondition

A single comparison (SimpleCondition, ast.ts:302-312). right is wire-typed to exclude a column (Exclude<ValuePosition, ColumnReference>); the builder validates “not a column” at its boundary.

SnapshotChunk

One frame of a chunked hydrate snapshot (FLAT-CHANGES-DESIGN.md §5.4). The initial snapshot is O(full result) — the whole tree as top-level Adds (each with its inline subtree) — so it is paged across SnapshotChunks rather than one giant batch. adds is a slice of those top-level Adds; index is gap-free within the snapshot; last is the snapshot_complete marker (the receiver renders only after it). All chunks carry the subscription epoch + schema_fp so a mid-snapshot drift is caught. A chunk’s adds apply atomically (each carries its full subtree).

Subscriber

Receiver side: a Receiver plus the protocol state, enforcing the §2.3/§5.4 rules. The baseline is established by either a single-shot apply of the seq-0 snapshot batch or a sequence of apply_snapshot_chunk calls; then incremental batches flow.

View

The materialization sink (ports ArrayView). Lives in the arena as Operator::View; its graph-touching halves (hydrate/view_push) are Graph methods that delegate the pure folding to [apply_change].

WireNode

A materialized node on the wire: its row plus slot-keyed, pre-sorted child subtrees — the wire-shaped twin of CaughtNode (Vec rows; relationships as a sorted Vec<(slot, children)> rather than a BTreeMap).

WireRel

A relationship slot on a WireSchema: its name, its slot index, either the child level’s schema (in-view) or None (gating / out-of-view — the receiver’s in-view gate drops Child changes addressed at it, FLAT-CHANGES-DESIGN.md §6), and an optional scalar-projection annotation (REDUCE-DESIGN.md §9).

WireSchema

One level of the hierarchical view schema, wire-shaped. See the module docs.

Enums

Aggregate

An aggregate over a (correlated) subquery’s rows (REDUCE-DESIGN.md).

Applied

The outcome of applying a Batch.

BuildError

Errors raised while lowering an Ast into pipeline pieces (spec 08). Introduced for create_predicate; the build_pipeline spine grows it.

CaughtChange

A caught downstream change. Mirrors catch.ts expandChange output: an Edit carries only the two rows (no node, catch.ts:104-109); a Child carries the parent row, the relationship slot, and the nested change (catch.ts:110-118).

Condition

The filter tree (Condition, ast.ts:296-300). Wire-tagged by "type"; recursive through the Vecs (heap-boxed elements) and the boxed subquery.

Dir

Sort direction for an OrderPart. Wire 'asc' | 'desc' (ast.ts:24).

ExistsOp

'EXISTS' | 'NOT EXISTS' (CorrelatedSubqueryConditionOperator, ast.ts:333).

FlatOp

The op at the end of a flat change’s path (the reached level).

Lit

An AST literal value (LiteralValue, ast.ts:284-289). Its own type — distinct from the runtime crate::value::OwnedValue — so the AST derives PartialEq (OwnedValue forbids derived comparison; you must pick compare_values vs values_equal). The two are bridged at lowering time (builder, 08).

Op

A simple comparison operator — the wire SimpleOperator set (ast.ts:211-215). Serializes as the exact SQL-ish string ("=", "!=", "IS NOT", "NOT IN", …).

ProtocolError

A protocol violation a Subscriber surfaces. All but a duplicate are fatal to the current subscription — the consumer must discard its tree and re-subscribe (the sender re-hydrates under a new epoch).

ResultType

The query’s completion state (typed-view.ts).

RindleError

SnapStatus

The outcome of applying a SnapshotChunk.

System

Subquery provenance (System, ast.ts:28). Shared with the runtime layer.

ValuePosition

A value position in a SimpleCondition — a column reference or a literal (ValuePosition, ast.ts:267, minus the deprecated static parameter form). Wire-tagged by "type".

Constants

COMPARATOR_VERSION

The compare_values/compare_rows algorithm-contract version (§4/§5.5). Bump this whenever the total order changes (null handling, float/total_cmp, the bytewise BINARY string order, cross-type rules). A receiver MUST refuse a subscription whose comparator_version differs — its reconstruction would silently corrupt.

Traits

ScalarCatalog

Maps a table name to its ScalarSource. The resolver only ever looks up the child (subquery) table — the parent is never read.

ScalarSource

The per-table read seam the resolver uses to fold a statically-unique subquery. One impl per source backend; MemorySource provides the PK-only slice impl.

Functions

build_family_pipeline

Lower a parameterized query family (design 310 §4) into graph: one pipeline over the family’s stripped template (rindle-wire’s FamilyTemplate::stripped — the number-canonicalized AST with its holed root-equality conjuncts removed) whose params columns are a partition dimension. Compared with build_pipeline over a concrete member, the compiled pipeline differs in exactly three places:

build_pipeline

Lower an Ast into a wired pipeline in graph, returning the top operator (the one a sink attaches to via Graph::set_sink_edge). The port of JS buildPipeline/buildPipelineInternal (builder.ts:256) for the built operator subset: a source connection carrying its pushed-down where (ConnectionFilters) plus a chain of parent-driven relationship joins.

canon_of_lit

The binding-value class of a scalar literal (design 310 §3.1 / impl plan §3.2): Some iff lit is a scalar a parameterized query family may bind on — Bool/Int/ Str directly, Number through the same number coercion the predicate lowering applies (lit_to_scalar → number_to_owned) and then CanonVal::of, so Int(1) and Number(1.0) are one binding exactly when values_equal says so, and a binding agrees cell-for-cell with the col = lit predicate it stands in for. Null (SQL never-match — the predicate folds it to false), Array (an IN list), and a non-finite Number (no wire token; [canonicalize_wire_number_lits] folds it to Null) are None — ineligible.

flatten

Linearize one CaughtChange into a FlatChange: peel each CaughtChange::Child into a PathSeg until a non-Child op is reached.

flatten_all

Linearize a batch of CaughtChanges (e.g. one transaction’s drained sink), preserving order. The order is significant — the receiver must apply the resulting flat changes in exactly this order (FLAT-CHANGES-DESIGN.md §5.4).

has_scalar_subquery

True if ast contains any scalar-flagged correlated subquery (anywhere in its WHERE tree or a nested/related subquery). A cheap gate so a caller can skip the resolve_scalars clone when there is nothing to fold — the peer of the planner’s has_flippable_exists.

resolve_scalars

Resolve every scalar-flagged correlated subquery in ast (its WHERE tree and, recursively, every nested subquery and related child) against catalog, returning a rewritten AST in which each fold has replaced its EXISTS/NOT EXISTS condition with a plain Simple condition (so the builder emits no join for it). Conditions without the flag are untouched, so an AST with no scalar: true anywhere round-trips unchanged.

schema_fp

Fingerprint a resolved WireSchema. The PK and sort are hashed by column name (resolved through columns), so the fingerprint is a semantic identity independent of any internal ColId numbering (§5.5).

table

Start a query for table. The entry point: table("issue").select("title")….

to_schema

Rebuild an engine Schema from a WireSchema (the receiver side). The inverse of to_wire for every field the receiver uses (columns, PK, sort, singular, each relationship’s name + child schema, and any scalar-projection annotation). A child: None relationship becomes a join-only RelDef::new (out-of-view) slot.

to_wire

Lower an engine Schema (the hierarchical view schema) to its WireSchema. Recurses into each relationship’s child schema; a join-only / gating slot (no child schema) becomes child: None.

view_schema

Derive the production-View hierarchical schema for ast, resolving table names through the same resolve closure that build_pipeline uses. build_pipeline returns only the top NodeId, so the View’s tree shape is reconstructed here from the Ast. The schema is the view shape: a relationship slot carries a child schema iff it is in view (a join-only RelDef::new is out of view).

Type Aliases

EntryList

The reference-counted, copy-on-write child list.

Listener

A flush listener (Listener, typed-view.ts:9). Fired on flush and once immediately on registration.

ViewData

The top-level result the consumer sees (root[""]): the sorted list of root entries. An Arc-shared EntryList, so a consumer can Arc::ptr_eq the snapshot to detect an unchanged top level.

WireRow

A row on the wire: positional cells, aligned to the level’s Schema.columns.