Module 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:

• OQ-1 — BTreeCursor self-reference / snapshot wiring (§4.4.4, §12 Q1). The cursor must hold its Rc<BNode> snapshot and vend a borrowed &OwnedRow out of it. The naive &'t BNode field that borrows another field of the same struct is a self-referential struct — not expressible in safe Rust. This spike locks in the recommended shape: the cursor owns Rc<BNode> clones along the spine (no &'t self-borrows) and next_row returns &self.leaf.keys[pos], a borrow of self valid only until the next call — exactly the lending RowStream contract. Result: the cursor needs no lifetime parameter at all.

• OQ-2 — owning a row at the node boundary without a deep copy (§8.2, §12 Q2). Node construction needs the stored Arc<[OwnedValue]> to bump (refcount++), not deep-copy. A bare borrowed slice has lost its Arc identity, so Arc::from(slice) would re-allocate. Resolution — folded into the shared trait: the cursor’s RowStream::Row<'a> is &'a OwnedRow (not a slice), so RowRef::to_owned_row is just Arc::clone of the stored row — a refcount bump, never a copy (proven by Arc::ptr_eq in the tests). No concrete current_arc escape hatch is needed: the same to_owned_row the SQLite leaf uses to copy out of its step buffer is, here, a bump.

What Rc<BNode> + Rc::make_mut deletes (§4.4.1): the JS BNode.isShared transitive flag (btree-set.ts:384-396) — the hardest hand-port artifact — vanishes. Sharing is Arc::strong_count > 1 (tracked by the runtime); “clone before mutate if shared” is precisely Rc::make_mut; transitivity falls out because make_mut is called lazily per node as the mutation descends, copying only the root→leaf path and only the nodes that are actually aliased. fork()/clone() is one Arc bump — O(1).

Scope note: this uses the spike crate’s existing owned Value/Row (value.rs); the production Value<'a>/OwnedValue split is Step 2 (a mechanical type swap — the algorithm here is the production one). add, delete (with the JS opportunistic tryMerge rebalancing), from_sorted, the forward/reverse bounded cursor, and fork/make_mut COW are all faithful ports of shared/src/btree-set.ts and differential-tested against it (tests/btree_diff.rs). The one deliberate divergence from JS is the set “shift-to-avoid-split” sibling rebalance (btree-set.ts:558-583): it is a pure micro-optimization (never changes contents, and is never triggered by ascending inserts or from_sorted, so it affects no benchmark), and it carries the most bug surface of any path — omitted on purpose, documented in node_set. In production this module is #[cfg(feature = "memory")].

Structs

BTree

A copy-on-write B+tree set of OwnedRows, ordered by a Sort comparator passed per call (no stored closure — foundations §11.6). Replaces BTreeSet<Row> (btree-set.ts:7) with Rc<BNode> + Rc::make_mut. The comparator lives with the enclosing Index in the real source; the spike threads &Sort.

BTreeCursor

A forward-or-reverse ordered cursor over a BTree. No lifetime parameter (the OQ-1 result): it OWNS Rc<BNode> clones along the spine + the root snapshot, so it borrows nothing externally; the only borrow is the one next_row lends out of self per call. Holding the _snapshot root Arc keeps the entire pre-write tree alive and immutable for the cursor’s life — a concurrent BTree::add/delete make_muts a fresh path (because the snapshot pins strong_count > 1) and never touches these nodes. That is what makes reentrant fetch-during-push safe (§6, foundations §6.3).

DiffStats

Work counters for the structural diff — the performance oracle (design §2.2.2). A fork + N point-mutations diff must show O(N·height) visits and O(N) value compares; a regression (lost node sharing, or ptr_eq not firing on some target) surfaces as visits proportional to tree size instead.

Enums

Bound

A scan-start cell: a concrete value or a type-extreme sentinel that sorts below/above every real value (including Null, the lowest real value). Mirrors JS Bound = Value | minValue | maxValue (memory-source.ts:967). The spike uses one owned form (the production Bound<'a>/OwnedBound split is the zero-copy concern of Step 2).

Traits

DiffSink

Sink for BTree::diff_visit: one callback per difference, emitted in descending sort order. “this” is self; “other” is the argument tree.

RowRef

A borrowed view of one row; columns addressed by ColId. The returned Value borrows self, so it is valid only as long as the row reference — for the SQLite leaf that means until the next next_row.

RowStream

A lending stream of rows. next_row reborrows self, so the row it returns is invalidated by the next call — exactly the SQLite cursor contract, now a compile-time invariant. This is the leaf source’s output shape; it is not std::iter::Iterator (which hands out owned items and cannot express the borrow). GAT-based lending, stable since Rust 1.65.

Functions

row_bound_of

Build an all-Val RowBound from a concrete lower-bound row.

Type Aliases

RowBound

A scan-start key: each index-sort column pinned to a Bound. Empty / absent columns are treated as Min (a safety default — a real seek pins every sort column). Index-addressed; a small Vec, not a map (04 §4.3).