Skip to main content

Module persistent

spg_storage

Module persistent 

Source
Expand description

Persistent (structural-sharing) vector — the v4.38 building block for the v4.39 cheap-Catalog::clone migration.

PersistentVec<T> is a Bitmapped Vector Trie (Clojure persistent vector shape): 32-way branching trie with a tail buffer at the open end. Every mutating operation produces a new handle that shares interior nodes with the old handle via Arc. Clone is O(1); push and get are O(log₃₂ N); a CoW path touches only the spine of the affected leaf.

Hard rules (do not relax in later milestones):

  • no_std compatible (alloc::sync::Arc, alloc::vec::Vec).
  • Zero unsafe. Workspace lint unsafe_code = "deny" stays in force here.
  • Zero external deps. Pure std + alloc.

Layout:

  • root: Arc<Node<T>> — the persistent trie. Node::Internal(Vec<Arc<Node>>) for non-leaf levels, Node::Leaf(Vec<T>) for the bottom.
  • tail: Arc<Vec<T>> — the open-end buffer (≤ 32 elements). Lives outside the trie so push to a non-full tail avoids walking the spine.
  • len: usize — total element count (trie_size + tail.len()).
  • shift: u32 — distance from the root to the leaf level, in bits, in multiples of SHIFT. An empty PV has shift = SHIFT and an empty root so the first incorporate doesn’t have to special-case the root type.

Invariants (debug-asserted in hot paths):

  • tail.len() ≤ BRANCH.
  • When tail.len() == BRANCH we incorporate it into the trie before the next push (so post-condition is tail.len() < BRANCH, except briefly in the middle of push).
  • shift is always a multiple of SHIFT and ≥ SHIFT.
  • trie_size = len - tail.len() always fits in 1 << (shift + SHIFT).

Structs§

Iter
Sequential &T iterator. v4.38 implementation is get(i)-driven — simple and correct, but O(N log N) over the whole vector. Profile in v4.39 / v4.40 and upgrade if it shows up in flamegraphs.
PersistentVec
A persistent vector with structural sharing. Clone is O(1) (bumps the root Arc); push is amortised O(log₃₂ N) and only allocates fresh nodes along the spine from the root to the affected leaf.
RunCursor
v7.39 (round 567) — see PersistentVec::run_cursor.