core.collections — Lists, Maps, Sets, Deques

Semantic-honest data structures. You talk to the protocol; the compiler chooses the implementation.

Module status

Each core.collections.* module carries an explicit conformance status so you know what you can rely on today versus what is still in flight. The status is the truth-table over the module's API surface as exercised by core-tests/collections/<module>/ under both verum test --interp (Tier 0 VBC interpreter) and verum test --aot (Tier 2 LLVM AOT).

Current conformance snapshot — 2026-06-13

The per-module rows further down carry detailed historical notes (2026-05) and may lag the current numbers. The live state:

• Tier-0 interpreter — GREEN across all 20 submodules. Roughly 790 active @test pass; the only non-passing tests are @ignore'd pins that lock specific cross-tier / stdlib defects (see below). The earlier regression-only gates (CSPRNG-keyed construction for bloom / count_min / hyperloglog, the cross-module name table, the BTreeMap record-storage corruption) are resolved on the interpreter path.
• Tier-1 AOT — partial. Fully green: alias_sampler, hyperloglog, consistent_hash, count_min. The large mutable collections (deque, heap, lru, map, btree, adjacency_list) still fail under --aot: their compiled stdlib mutation bodies (push / insert / grow → realloc of a self pointer field) null-deref at Tier-1. This is a cross-tier codegen defect, not an interpreter or API problem — the same sources pass on Tier-0.

Two fundamental AOT fixes (branch collections-aot-fixes):

1. Text.from_utf8_unchecked / Text.from_utf8_lossy were empty VBC stubs intercepted by name on the interpreter but not at LLVM lowering, so every AOT caller of Text.from(text) trapped (brk #1). The LLVM intercept now routes the byte slice through the canonical verum_text_alloc. This unblocked AOT construction of every error / value type carrying a Text payload — count_min AOT 2→6, consistent_hash 19→23, bloom 11→12.
2. List.with_capacity(n) now honours its argument as a capacity guarantee in both tiers (it previously dropped the hint, so capacity() reported the runtime default). The interpreter already honoured the hint; AOT gained a capacity-aware NewList lowering.

The with_capacity fix correctly surfaced a pre-existing resize_buffer realloc-self.ptr SIGABRT on the List reserve / shrink_to / shrink_to_fit path (previously masked because with_capacity never reserved); those four tests are @ignore'd together pending the realloc fix.

Status	Meaning
stable	Every public method is conformance-tested. Algebraic laws are pinned by exhaustive or large-domain property tests. Cross-stdlib integration is verified. Interpreter and AOT agree on every test. Safe to depend on in production.
partial	Subset of the public API is conformance-tested and stable. The rest is exercised in regression_test.vr via @ignored tests pinning the specific defects that block coverage. The non-ignored API surface is safe; everything else is documented per-module under "Open defects".
regression-only	Module is gated by upstream stdlib / language-level defects. Public-API tests do not pass yet — only @ignored regressions exist to lock the bug shapes. Avoid in production until promoted.
undocumented	Documentation in this reference is authoritative, but the module has not yet been routed through the core-tests/ conformance suite. The current page is a best-effort snapshot of the source; it may drift from runtime behaviour.

Module	Status	Conformance suite
list.vr	partial	core-tests/collections/list — 137 unit (128 active + 9 @ignore) + 11 property + 8 integration + 9 pinned regressions, 129/129 active green on --interp validated 2026-05-27. Round 12 (2026-05-27, completed): 14 stdlib method-body migrations to runtime-intercepted self.get(i) / self.set(i, v) / self.truncate(at) surface: (a) raw ptr_read/write class — get_mut / pop_front / split_off / binary_search / binary_search_by / partition_point / try_push / append; (b) for/range iterator-closure remap class — position / rposition / find_by / position_by / any / all / starts_with / ends_with / windows / chunks / partition_by / chunk_by / dedup_by / split_at. Bi-modal position runtime intercept (closure vs value-form per arg0.is_func_ref()). §E for/range defect class FULLY CLOSED. Remaining @ignore: closure-dispatch (sort_unstable populated / sorted / fill Clone / is_sorted ref-deref); resize_buffer SIGABRT (reserve / shrink); cross-module bare-name (try_with_capacity). List.from / List.of / List.from_elem CLOSED 2026-05-24 (commit 0360a343e). 4 runtime intercepts added (contains-needle CBGR deref, set, get_or, swap_remove, truncate).
map.vr	partial	core-tests/collections/map — 46 unit (39 active + 8 @ignore: 7 keys_list/values_list + 1 with_capacity-then-fill) + 6 property + 5 integration + 5 pinned regressions, 39/46 active green on --interp validated 2026-05-27. Round 12 expansion: Sections 10–16 added (get_or / with_capacity / insert overwrite contract / remove return contract / many-keys preserved + half-remove / keys_list-values_list / is_empty + capacity invariants). MapIter.next NullPointerAt wrapper-iter dispatch class gates keys_list/values_list (same root as slice §D). Cap=0 bootstrap guard added on insert.
set.vr	partial	core-tests/collections/set — 23 unit + 10 property + 5 integration + 4 pinned regressions. Set.insert returns Bool (was Unit); Set.union / Set.intersection auto-deref CBGR ref needle.
multiset.vr	partial	core-tests/collections/multiset — 21 unit + 10 property + 5 integration + 12 regressions. Construction / insert / remove / count / contains / clear / cardinality / distinct_len / is_subset / with-empty algebraic ops green; per-element-correct union/intersection/sum/difference and direct iter() pinned (gated on MultisetIter wrapping Map.iter() — wrapper-type dispatch defect, same class as slice §D).
deque.vr	stable	core-tests/collections/deque — 44 unit + 8 property + 5 integration + 2 pinned regressions (44/44 active green on --interp validated 2026-05-27). Round 12 expansion: Sections 8–14 added (get / get_mut after wrap-around / contains / clear+refill / with_capacity / singleton edge cases / repeated push_front / drain-to-empty refill / alternating push-pop). Stdlib type-decl field order matches runtime intercept allocation.
heap.vr	partial	core-tests/collections/heap — 32 unit + 5 property + 4 integration + 5 regressions, 51/52 green on --interp validated 2026-05-27 (1 pre-existing fail). Round 12 (completed): Sections 6–14 added (with_capacity / push_pop 3 variants / replace 2 variants / try_push / singleton / inserted-in-both-orders / duplicates / to_list-into_list / clear / 16-elem drain). Migrated push_pop and replace from raw unsafe { ptr_read(as_mut_slice().as_mut_ptr()); ... } to safe self.data.get(0) + self.data.set(0, value) (commit 383ea7278). Eliminated the List.swap dispatch panic on receiver mis-classified as InterruptCell(Int). Earlier branch: Heap.into_inner CBGR runtime intercept (commit bd2553407); array-dispatch polarity defect closed.
btree.vr	regression-only	core-tests/collections/btree — 6 unit + 5 property + 2 integration + 17 regressions. Pattern-match ref-deref CLOSED 2026-05-24 (commit 9d39011e1 — IsVar/GetVariantData/AsVar handlers now auto-deref heap-interior pointers in cbgr_mutable_ptrs). Stdlib refactored BTreeMap.get/get_mut/insert/remove from .as_ref().expect() to match &self.root { Some(node) => … }. Residual: end-to-end m.insert(1,100); m.get(&1) still hits field index 3 OOB on size 24 inside search_node chain — &Heap<BTreeNode<K,V>> argument-passing through generic methods loses inner T type (sister defect tracked separately). Empty-state surface remains green.
slice.vr	partial	core-tests/collections/slice — 47 unit + 10 property + 5 integration + 17 regressions (5 PASS-GUARDs + 12 defect-pins), 56/56 (test_slice_* filter) green on --interp validated 2026-05-27. Round 12 expansion: Sections 7–11 added (index_of / rindex_of value-search; contains via full + subrange; get/first + get/last Maybe-destructure coherence; slice-of-slice nesting independence; split_at boundary cases zero/one/full). index_of/rindex_of CLOSED 2026-05-24 (commit d05ffd479). Slice-only methods (eq_slice/cmp_slice/to_list/binary_search/partition_point/chunks/windows) still unreachable via CallM because &[T] shares the List runtime kind.
lru.vr	stable	core-tests/collections/lru — 21 unit + 9 property + 5 integration + 5 PASS-GUARDs (41/41 green on --interp validated 2026-05-23). Construction with capacity clamp, insert prior-value return, get/peek/remove/contains, clear, capacity-pressure eviction, LRU order tracking via touch-on-get, stats (size/hits/misses/evicted), peek-no-touch invariant — all conformance-tested.
ttl_cache.vr	regression-only	core-tests/collections/ttl_cache — 6 unit + 5 property + 3 integration + 11 regressions (4 PASS-GUARDs on the working surface + 7 @ignore'd insert-path pins). Fundamental source-level defect closed in this branch: ttl_cache.vr:109 called the non-existent Instant.add_duration(Duration); fixed to use the canonical Instant.checked_add(Duration) -> Maybe<Instant> API. Same fix landed at the parallel QUIC PMTU site (path_mtu.vr:138). Promotes to stable after cargo build --release refreshes the embedded precompiled stdlib in the verum binary.
bloom.vr	partial	core-tests/collections/bloom — 4/4 non-@ignore'd regressions green on --interp validated 2026-05-24. Task #47 CLOSED: cross-module Call name-encoding via stage-3 stub pre-register (pre_register_unique_public_free_functions in pipeline/stdlib_bootstrap.rs) + finalize-time emit_missing_stub_descriptors_with_callm(false) descriptor synthesis. BloomFilter.try_new body compiles cleanly; at archive load, ArchiveBodyRemap's Tier-2b name fallback resolves stub_id → real user-side FunctionId via the archive-wide archive_func_by_name index. 4 @ignore'd §B pins remaining are gated on a SEPARATE defect class (HMAC-SHA256 [Byte; 64] IndexOutOfBounds in core.mac.hmac.HmacSha256.finalize).
hyperloglog.vr	partial	core-tests/collections/hyperloglog — 14/15 green on --interp validated 2026-05-24. Task #47 unblock spread here automatically: all HLL constructors + precision constants + HllError variant + merge precision-mismatch all green. 1 @ignore'd for add_then_estimate semantic (separate defect class).
count_min.vr	partial	core-tests/collections/count_min — 6/8 green on --interp validated 2026-05-24. Task #47 unblock spread here automatically: all construction tests + CountMinError variant algebra green. 2 @ignore'd for add_increments_total / estimate_non_negative populated-state semantic (same HMAC-SHA256 class as bloom §B).
reservoir.vr	partial	core-tests/collections/reservoir — 14 unit + 7 property + 4 integration + 4 pinned regressions (CSPRNG-gated replacement phase)
consistent_hash.vr	partial	core-tests/collections/consistent_hash — 5 unit + 5 property + 2 integration + 4 PASS-GUARDs + 1 @ignore'd populated-ring pin. Empty-ring surface (new / with_virtual_nodes / node_count / position_count / node_for_key-on-empty / nodes_for_key-on-empty / DEFAULT_VIRTUAL_NODES) green; add_node integration deferred pending Text.from reachability.
adjacency_list.vr	partial	core-tests/collections/adjacency_list — 4 unit + 3 property + 2 integration + 5 regressions (3 PASS-GUARDs + 2 @ignore'd edge-mutator pins). add_edge panics with field-write-out-of-bounds (same layout-drift class as BTreeMap §A but for the inner edge-Map). Vertex-only surface green.
alias_sampler.vr	regression-only	core-tests/collections/alias_sampler — 1 unit + 1 property + 1 integration + 4 regressions. AliasSampler construction gated on RNG + wrapper-record layout. Working surface: AliasError variant.
toposort.vr	partial	core-tests/collections/toposort — 4 unit + 13 property (9 active + 4 @ignore) + 6 integration + 6 regressions, 29/29 active green on --interp validated 2026-05-29. Acyclic path fully covered: topological-order invariant (dep precedes dependent ∀ edges), permutation/totality, stable tie-break, determinism, duplicate-edge in-degree counting, add_node idempotence; cross-stdlib build-order / install-order / incremental-constraint scenarios. Open: TOPO-CYCLE-1 (HIGH) — toposort() PANICS instead of returning Err(Cycle) for any cyclic graph: the cycle branch calls the generic free fn node_label(n) from inside the generic implement<N> TopoGraph<N> method and VBC codegen mislays the call frame (field write out of bounds: field index 80 … type_id=0). 4 cycle property tests @ignore'd; fix = thread the monomorphisation frame for generic-free-fn-from-generic-method calls (or stdlib workaround: inline Text.from("<node>"), drop node_label). See audit.md §1.
trie.vr	partial	core-tests/collections/trie — 3 unit + 3 property + 2 integration + 6 regressions. Map.get_mut UNBLOCKED 2026-05-24 (commit 997f53352): added Map.get_mut(&mut self, key: &K) -> Maybe<&mut V> (was missing — fn not declared on Map). Trie mutator path (insert/remove) now structurally unblocked; regression tests pending re-validation under un-ignore. Empty-state surface remains green.
union_find.vr	partial	core-tests/collections/union_find — 31 unit + 14 property + 7 integration + 11 pinned regressions

Core data structures

File	What's in it
list.vr	List<T> + adapters (ListIter, Drain, Chunks, Windows, …)
map.vr	Map<K,V> + MapEntry<K,V>, OccupiedEntry, VacantEntry, MapIter, Keys, Values, Drain
set.vr	Set<T> + SetIter, SetDrain
multiset.vr	Multiset<T> (hash bag with strictly-positive multiplicities) + MultisetIter, MultisetDistinctIter
deque.vr	Deque<T> + DequeIter, DequeDrain
heap.vr	BinaryHeap<T>, MinHeap<T>, HeapDrainSorted, Reverse<T>
btree.vr	BTreeMap<K,V>, BTreeSet<T>, BTreeEntry, range iterators
slice.vr	slice utilities — slice_iter, chunks, windows, split_at

Caches + probabilistic sketches

File	What's in it
lru.vr	LruCache<K,V> — pure capacity-bounded LRU
ttl_cache.vr	TtlCache<K,V> — LRU + per-entry TTL
bloom.vr	BloomFilter — "is X present?" probabilistic set
hyperloglog.vr	HyperLogLog — "how many distinct?" cardinality
count_min.vr	CountMinSketch — "how often was X seen?" frequency
reservoir.vr	Reservoir<T> — Algorithm R uniform streaming sample
consistent_hash.vr	ConsistentHashRing — Ketama-compatible distribution

Every core data structure implements Iterator, IntoIterator, Clone, Debug, Display, Eq, Hash, Default. Hash is always consistent with Eq under the structure's equality semantics — for order-independent collections (Set, Map, BinaryHeap) hashing is deliberately order-independent (XOR-fold over element hashes for Set/Map, sort-then-fold for BinaryHeap) so the a == b → hash(a) == hash(b) contract holds across distinct internal arrangements of the same multiset.

Caches and sketches carry stats counters (hits/misses/evicted) instead of the Iterator shape since they're lossy or ordered by workload rather than enumeration.

---

List<T> — dynamic array

O(1) amortised push/pop at the end; O(1) random access; O(n) insert- in-middle.

public type List<T> is { ptr: &unsafe T, len: Int, cap: Int };

Construction

List.new() -> List<T>
List.with_capacity(capacity: Int) -> List<T>
List.from_slice(slice: &[T]) -> List<T>    // T: Clone
List.from(iter)                            // from any Iterator<Item=T>

let xs = [1, 2, 3];                    // macro — array of items
let ys = [0; 10];                           // repeat form — 10 copies of 0

Capacity & size

xs.len() -> Int
xs.is_empty() -> Bool
xs.capacity() -> Int
xs.reserve(additional)        xs.reserve_exact(additional)
xs.shrink_to_fit()            xs.shrink_to(min_capacity)

Access

xs[i]                 // panics on OOB
xs.get(i) -> Maybe<T>
xs.get_mut(i) -> Maybe<T>
xs.first() / xs.last() -> Maybe<T>
xs.first_mut() / xs.last_mut() -> Maybe<T>

These return the element BY VALUE, not a reference

This block previously read Maybe<&T> and Maybe<&mut T>, matching the Rust API it is modelled on. core/collections/list.vr returns Maybe<T> from all six — checked against the declarations at lines 350, 360, 396, 402, 412 and 418.

Two things follow, and both bite in practice:

• get_mut cannot mutate. Its body is self.get(idx), and the comment above it says "returns copy of element value". So xs.get_mut(i).field = v writes to a copy; where the element is a record the compiler rejects it outright with E103: Cannot access field on non-record type. Use xs.set(i, value), or get_unchecked_mut inside unsafe when you need a reference. It is the only get_mut in the standard library that does not return &mut T — the ones on RenderCell, File, BufWriter and Mutex all do.

• Do not dereference the unwrapped element. xs.get(i) already yields the value, so xs.get(i).unwrap() is a T. Writing *xs.get(i).unwrap() dereferences a value; in generic code that binds the function's own type parameter to a reference and produces a cascade of "ambiguous type" errors on lines that are perfectly well annotated.

  *xs.get(i) on its own IS valid — implement<T> Deref for Maybe<T> in core/base/maybe.vr makes the dereference unwrap the Maybe. That is exactly why the extra .unwrap() is easy to miss.

The by-value signature is not an oversight. list.vr records that the raw *self.ptr.offset(idx) form returned bytes from the heap object header, because codegen resolves self.ptr to the start of the backing object rather than past the header; returning a copy is the retreat from that.

Mutation

xs.push(value)
xs.pop() -> Maybe<T>
xs.insert(index, value)
xs.remove(index) -> T
xs.swap_remove(index) -> T         // O(1); destroys order
xs.swap(i, j)
xs.clear()
xs.truncate(len)
xs.extend(other)                   // extend from an iterator
xs.retain(|x| pred(x))             // keep only matching elements
xs.dedup()                         // remove consecutive duplicates (T: PartialEq)
xs.dedup_by(|a, b| same(a, b))
xs.dedup_by_key(|x| key(x))
xs.sort()                          // T: Ord
xs.sort_by(|a, b| a.cmp(b))
xs.sort_by_key(|x| key(x))
xs.sort_unstable()                 // T: Ord, faster, not stable
xs.reverse()
xs.fill(value)                     // T: Clone
xs.fill_with(|| make())
xs.resize(new_len, value)          // T: Clone

Slicing

xs[a..b]              // panics on OOB range
xs.slice(a, b)        xs.slice_mut(a, b)
xs.split_at(i) -> (&[T], &[T])
xs.split_first() -> Maybe<(&T, &[T])>
xs.split_last()  -> Maybe<(&T, &[T])>

Iteration

xs.iter()                 // Iterator<&T>
xs.iter_mut()             // Iterator<&mut T>
xs.into_iter()            // consumes xs
xs.drain(a..b)            // removes and yields a range
xs.chunks(n)              // non-overlapping windows; ChunksIter
xs.chunks_exact(n)        // exact-sized chunks + remainder
xs.windows(n)             // sliding window of n; WindowsIter
xs.enumerate()            // convenience (.iter().enumerate() also works)

Searching

xs.contains(&value) -> Bool                 // T: PartialEq
xs.position(|x| pred(x)) -> Maybe<Int>
xs.rposition(|x| pred(x)) -> Maybe<Int>
xs.binary_search(&value) -> Result<Int, Int>   // T: Ord
xs.binary_search_by(|probe| cmp)
xs.binary_search_by_key(&target, |x| key(x))
xs.partition_point(|x| pred(x)) -> Int

Conversion

xs.as_slice() -> &[T]
xs.as_mut_slice() -> &mut [T]
xs.clone()      // clone into a new List

Example

let mut words = ["hello", "world", "verum"];
words.sort();
words.dedup();
for (i, w) in words.iter().enumerate() {
    print(f"{i}: {w}");
}

let counts: Map<Int, Int> = words.iter()
    .map(|w| w.len())
    .fold(Map.new(), |mut m, len| {
        *m.entry(len).or_insert(0) += 1;
        m
    });

Pitfall — swap_remove destroys order

swap_remove(i) is O(1) because it swaps with the last element. If order matters, use remove(i) (O(n)).

---

Map<K, V> — hash map

Swiss-table-style flat hash map. K: Hash + Eq.

Construction

Map.new() -> Map<K, V>
Map.with_capacity(capacity) -> Map<K, V>
Map.from(pairs: [(K, V); _])
let m: Map<Text, Int> = Map.from([("a", 1), ("b", 2)]);

Size

m.len()    m.is_empty()    m.capacity()
m.reserve(additional)      m.shrink_to_fit()

Access

m.get(&key) -> Maybe<&V>
m.get_mut(&key) -> Maybe<&mut V>
m.get_key_value(&key) -> Maybe<(&K, &V)>
m.contains_key(&key) -> Bool
m[&key]                   // panics on missing

Mutation

m.insert(key, value) -> Maybe<V>       // returns old value if any
m.remove(&key) -> Maybe<V>
m.remove_entry(&key) -> Maybe<(K, V)>
m.clear()
m.retain(|k, v| pred(k, v))
m.extend(iter)                         // iter yields (K, V)

Entry API — insert-or-update without double lookup

type MapEntry<K: Hash + Eq, V> is
    | Occupied(OccupiedEntry<K, V>)
    | Vacant(VacantEntry<K, V>);

m.entry(key) -> MapEntry<K, V>

entry.or_insert(default) -> &mut V
entry.or_insert_with(|| compute()) -> &mut V
entry.or_insert_with_key(|k| compute(k)) -> &mut V
entry.or_default() -> &mut V           // V: Default
entry.and_modify(|v| mutate(v)) -> MapEntry<K, V>
entry.key() -> &K

// On Occupied only:
occ.get() / occ.get_mut() / occ.into_mut()
occ.insert(value) -> V             // returns old
occ.remove() -> V
occ.remove_entry() -> (K, V)

Iteration

m.iter()        // Iterator<(&K, &V)>
m.iter_mut()    // Iterator<(&K, &mut V)>
m.into_iter()   // consumes m
m.keys()        // Iterator<&K>
m.values()      // Iterator<&V>
m.values_mut()  // Iterator<&mut V>
m.drain()       // consuming drain — Iterator<(K, V)>

Examples

// count words
let mut freq: Map<Text, Int> = Map.new();
for w in text.split_whitespace() {
    *freq.entry(w.to_string()).or_insert(0) += 1;
}

// group by key
let mut groups: Map<Int, List<User>> = Map.new();
for u in users {
    groups.entry(u.dept).or_insert_with(List.new).push(u);
}

// atomic upsert
match map.entry(key) {
    MapEntry.Occupied(mut e) => *e.get_mut() += 1,
    MapEntry.Vacant(e) => { e.insert(1); }
}

Pitfall — mutating while iterating

Inserting or removing entries while iterating with iter/iter_mut is undefined. Collect the changes and apply after, or use retain.

---

Set<T> — hash set

T: Hash + Eq.

Construction

Set.new()      Set.with_capacity(cap)      Set.from(values)
let s: Set<Int> = Set.from([1, 2, 3]);

Size & access

s.len()  s.is_empty()  s.capacity()
s.contains(&v) -> Bool
s.get(&v) -> Maybe<&T>         // returns the stored value

Mutation

s.insert(value) -> Bool        // true if it was new
s.remove(&value) -> Bool
s.take(&value) -> Maybe<T>     // remove + return the stored value
s.replace(value) -> Maybe<T>   // replace if present
s.clear()
s.retain(|v| pred(v))

Set algebra

a.union(&b)         // Iterator<&T>
a.intersection(&b)  // Iterator<&T>
a.difference(&b)    // Iterator<&T>
a.symmetric_difference(&b)  // Iterator<&T>

a.is_disjoint(&b)   a.is_subset(&b)   a.is_superset(&b)

Example

let a: Set<Int> = Set.from([1, 2, 3, 4]);
let b: Set<Int> = Set.from([3, 4, 5, 6]);

let union: Set<Int>      = a.union(&b).copied().collect();     // {1..6}
let intersect: Set<Int>  = a.intersection(&b).copied().collect(); // {3,4}
let diff: Set<Int>       = a.difference(&b).copied().collect();   // {1,2}

Protocol implementations

implement<T: Hash + Eq + Clone>     Clone   for Set<T>;
implement<T: Hash + Eq>             Default for Set<T>;
implement<T: Hash + Eq + Debug>     Eq      for Set<T>;  // delegates to inner Map
implement<T: Hash + Eq>             Hash    for Set<T>;  // order-independent
implement<T: Hash + Eq + Debug>     Debug   for Set<T>;  // {a, b, c}
implement<T: Hash + Eq + Display>   Display for Set<T>;  // {a, b, c}

The Eq and Hash impls are order-independent — two sets with the same elements but different insertion order compare equal and hash identically. Implementation delegates to the underlying Map<T, ()> so set semantics fall out for free from map's order-independent invariants.

---

Multiset<T> — hash bag with multiplicities

T: Hash + Eq. Generalisation of Set<T>: every element carries an integer multiplicity ≥ 1. Insert a value already present → multiplicity increments; remove → decrement; reaching zero evicts the entry.

Backed by Map<T, Int> exactly the way Set<T> is backed by Map<T, ()> — same Robin-Hood hashing, same amortised O(1) per- element ops.

Two distinct sizes

Multisets have two natural "size" notions, both exposed:

Method	Returns	Cost
distinct_len()	number of unique elements (= |support|)	O(1)
cardinality()	sum of multiplicities (Σ counts)	O(1) — cached

The deprecated len() is not provided to force the choice — Set.len() has one answer, Multiset.len() would have two; making the caller pick prevents silent wrong-size bugs.

Construction

Multiset.new()      Multiset.with_capacity(cap)
let m = Multiset.from([1, 2, 2, 3, 3, 3]);
let m = Multiset.from_counts([(1, 1), (2, 2), (3, 3)]);  // (element, multiplicity)

Access

m.distinct_len() -> Int        // |support|
m.cardinality()  -> Int        // Σ multiplicities
m.is_empty()                   // cardinality == 0
m.count(&v) -> Int             // multiplicity of v (0 if absent)
m.contains(&v) -> Bool         // count(v) > 0

Mutation

m.insert(value)            -> Int      // returns new multiplicity
m.insert_n(value, n)       -> Int      // increment by n; n ≤ 0 is a no-op
m.remove(&value)           -> Int      // decrement by 1; saturates at 0
m.remove_n(&value, n)      -> Int      // decrement by n; saturates
m.remove_all(&value)       -> Int      // evict entirely; returns evicted count
m.clear()
m.retain(|v, count| pred(v, count))    // keeps `cardinality` consistent

Fallible counterparts (try_insert, try_insert_n, try_reserve) return Result<_, AllocError> instead of panicking on growth.

Algebraic operations

Standard multiset algebra (Knuth TAOCP §4.6.3) over (ℕ, +, max, min):

Op	Per-element semantics	Notation
union(&other)	max(count_a, count_b)	A ∪ B
intersection(&other)	min(count_a, count_b)	A ∩ B
sum(&other)	count_a + count_b	A ⊎ B (multiset disjoint sum)
difference(&other)	max(0, count_a − count_b)	A − B

is_subset / is_superset / is_disjoint follow the multiset definitions (every-element multiplicity ≤, ≥, share-no-support respectively).

Iteration

m.iter()                       // Iterator<(&T, Int)>           — distinct + multiplicity
m.distinct_iter()              // Iterator<&T>                  — distinct only
m.to_list()       -> List<T>   // expand by multiplicity (cardinality entries)
m.to_count_list() -> List<(T, Int)>   // (element, count) without expansion

Statistics

m.mode() -> Maybe<&T>          // element with largest multiplicity (ties broken arbitrarily)

When to choose Multiset vs Set

• Set — identity / membership only; "is x present?".
• Multiset — frequency counting; "how many times has x occurred?". Statistical aggregations, deduplication-with-counts, MVCC bag semantics, simplicial-multiset structures, fractal-holon sub-holon multisets.

Protocol implementations

implement<T: Hash + Eq + Clone> Clone for Multiset<T>;
implement<T: Hash + Eq>         Eq    for Multiset<T>;   // every element same multiplicity
implement<T: Hash + Eq + Debug> Debug for Multiset<T>;   // Multiset {a×2, b×3}

Multiset equality is structural — same support, same per-element multiplicity. Two multisets with the same elements but different insertion order compare equal.

---

Deque<T> — double-ended queue

Ring buffer. O(1) push/pop at both ends.

Deque.new()     Deque.with_capacity(cap)
let q = [1, 2, 3];

q.len()  q.is_empty()  q.capacity()
q.push_front(v)   q.push_back(v)
q.pop_front() -> Maybe<T>
q.pop_back()  -> Maybe<T>
q.front() / q.back() -> Maybe<&T>
q.front_mut() / q.back_mut()

q.get(i) / q.get_mut(i)   // 0 = front
q[i]                      // panics on OOB
q.iter() / q.iter_mut() / q.into_iter() / q.drain(range)
q.rotate_left(n)  q.rotate_right(n)
q.clear()  q.retain(|x| pred(x))  q.extend(iter)

Use as FIFO (push_back + pop_front) or LIFO (push_back + pop_back).

---

BinaryHeap<T> / MinHeap<T> — priority queue

Max-heap: BinaryHeap<T>. Min-heap: MinHeap<T>. T: Ord.

let mut pq: BinaryHeap<Int> = [3, 1, 4, 1, 5, 9, 2, 6];
pq.push(7);
pq.peek();              // Maybe.Some(&9)
let top = pq.pop();     // Maybe.Some(9)
let all_sorted: List<Int> = pq.into_sorted_list();  // ascending

BinaryHeap.new()  BinaryHeap.with_capacity(cap)
BinaryHeap.from(list)        // heapify in O(n)

h.len()  h.is_empty()  h.capacity()
h.push(v)       h.pop() -> Maybe<T>
h.peek() -> Maybe<&T>
h.peek_mut() -> Maybe<PeekMut<T>>
h.clear()
h.drain()                 // unordered drain; HeapDrain
h.drain_sorted()          // yields in heap order; HeapDrainSorted
h.into_sorted_list() -> List<T>   // ascending; `to_list` keeps heap order
h.iter()                  // unordered

Min-heap via wrapping

For "min by custom key", wrap values in Reverse<T>:

let mut h: BinaryHeap<Reverse<(Int, Text)>> = BinaryHeap.new();
h.push(Reverse((3, "three".to_string())));
h.push(Reverse((1, "one".to_string())));
let Reverse((k, v)) = h.pop().unwrap();  // (1, "one")

Protocol implementations

implement<T: Ord>                       IntoIterator for BinaryHeap<T>;
implement<T: Ord + Eq>                  Eq           for BinaryHeap<T>;  // sorts then compares
implement<T: Ord + Clone>               Clone        for BinaryHeap<T>;
implement<T: Ord>                       Default      for BinaryHeap<T>;
implement<T: Ord + Debug>               Debug        for BinaryHeap<T>;
implement<T: Ord + Display>             Display      for BinaryHeap<T>;
implement<T: Ord + Hash + Clone>        Hash         for BinaryHeap<T>;  // sorts then hashes
implement<T: Ord>                       FromIterator for BinaryHeap<T>;
implement<T: Ord>                       Extend       for BinaryHeap<T>;

Eq and Hash both sort the contents before comparing/hashing so the a == b → hash(a) == hash(b) invariant holds across distinct internal heap arrangements of the same multiset of elements. Two heaps built from the same input list, even via different push orders, are interchangeable as keys in a Map<BinaryHeap<T>, V> or as elements of a Set<BinaryHeap<T>>.

---

BTreeMap<K, V> / BTreeSet<T> — ordered

Red-black tree (B-factor 12 internally, cache-friendly). K: Ord.

Common operations (BTreeMap/BTreeSet both)

.new() / .from_iter(iter)
.len()   .is_empty()
.insert(k, v) / .insert(v)
.remove(&k) -> Maybe<V>
.get(&k) / .get_mut(&k)
.contains_key(&k) / .contains(&v)
.iter()                   // sorted ascending
.keys() / .values() / .values_mut()     // map only
.into_iter()     .drain(range)
.retain(|k, v| pred) / |v| pred
.clear()

Ordered operations

m.first_key_value() -> Maybe<(&K, &V)>    // smallest
m.last_key_value()  -> Maybe<(&K, &V)>    // largest
m.pop_first() -> Maybe<(K, V)>
m.pop_last()  -> Maybe<(K, V)>

m.range(lo..hi)                  // iterator in range (shared refs)
m.iter_mut()  m.values_mut()     // mutable iteration is whole-map
m.split_off(&key) -> BTreeMap<K,V>   // split into two halves

Entry API

Same shape as Map's entry API (or_insert, or_insert_with, and_modify, or_default).

Example — windowed metrics

let mut by_ts: BTreeMap<Instant, Metric> = BTreeMap.new();
// … populate …

let now = Instant.now();
let last_minute: List<&Metric> = by_ts
    .range((now - 1.mins())..=now)
    .map(|(_, m)| m)
    .collect();

let recent_total: Float = last_minute.iter().map(|m| m.value).sum();

Choice guide

Need	Use
key lookup, any order	Map<K,V> (hash)
key lookup + ordered iteration	BTreeMap<K,V>
set membership, any order	Set<T>
set membership + ordered iteration / range queries	BTreeSet<T>
FIFO/LIFO queue	Deque<T>
priority queue	BinaryHeap<T> (or wrap in Reverse for min-heap)
"just a list"	List<T>

---

Slice utilities (slice.vr)

Status: regression-only. &[T] is the source-level type for "borrowed view of a contiguous run of T", but at the VBC runtime slice receivers carry a List kind, so methods declared in implement<T> [T] { ... } that are not ALSO present on List<T> dispatch through CallM and panic with method 'List.<name>' not found. The working surface — methods with a parallel List<T> implementation — is conformance-tested on --interp:

Method	Conformance
len, is_empty, first, last, get	green
slice(a,b), slice_from, slice_to, split_at	green
min, max, contains	green
iter() → SliceIter::next()	green

The slice-only surface — eq_slice, cmp_slice, to_list, binary_search, partition_point, position / rposition, is_sorted, starts_with / ends_with, chunks, windows — is gated on the architectural fix to give &[T] a distinct runtime kind (or to teach codegen to emit Call(Slice.<m>_fid) rather than CallM when the receiver's static type is &[T]). Defects pinned in core-tests/collections/slice/regression_test.vr §A–§E.

&[T] is the shared type for "borrowed view of a contiguous run of T". All collections' .iter() and indexing yield slices where it makes sense.

s.len()  s.is_empty()
s.first() / s.last() / s.split_first() / s.split_last()
s.iter() / s.iter_mut()
s.chunks(n) / s.chunks_exact(n)
s.windows(n)                     // sliding, size-n, WindowsIter
s.split_at(i) -> (&[T], &[T])
s.split(|x| pred(x))             // iterator of sub-slices
s.partition_point(|x| pred(x))
s.binary_search(&v)              // T: Ord
s.contains(&v) -> Bool           // T: PartialEq
s.starts_with(&prefix) / s.ends_with(&suffix)
s.as_ptr() / s.as_mut_ptr() -> *const/mut T    // unsafe bridge

List<T>.as_slice() and List<T>.as_mut_slice() give you &[T] / &mut [T] for interop with slice-accepting functions.

---

Implementation summary

Collection	Default implementation	Notes
List<T>	growable contiguous buffer, factor = 2	@repr(contiguous, growth = N) overrideable
Map<K,V>	Swiss-table flat hash map	linear probing, tombstones on delete
Set<T>	Swiss-set	same as Map
BTreeMap<K,V>	red-black tree, B = 12	cache-friendly node layout
BTreeSet<T>	red-black tree	same engine
BinaryHeap<T>	array-backed binary heap	4-ary pending evaluation
Deque<T>	ring buffer	rotation is pointer-update only

---

See also

• base — Iterator protocol and adapters.
• text — Text (semantic "collection of Unicode scalars").
• sync — locking wrappers (Mutex<List<T>>, etc.).
• Language → patterns — slice, record, rest patterns over these types.

---

Caches

LruCache<K, V>

let mut cache: LruCache<Text, User> = LruCache.new(1024);
let prev = cache.insert(key.clone(), user);
match cache.get(&key) { Some(u) => ..., None => ... }

Capacity-bounded hash map with LRU eviction on full. insert returns the prior value when the key was already present (useful for refcount bookkeeping). peek inspects without touching LRU order; remove / clear / contains cover the usual surface. stats() returns { size, hits, misses, evicted }.

TtlCache<K, V>

let cfg = TtlCacheConfig { capacity: 1024, default_ttl: Duration.from_secs(300) };
let mut cache: TtlCache<Text, Session> = TtlCache.new(cfg);

cache.insert(key.clone(), session);                               // default TTL
cache.insert_with_ttl(key2, session2, Duration.from_secs(60));   // override
cache.purge_expired();                                            // periodic sweep

Combines capacity-based LRU eviction with per-entry time-based expiration. Expiry is lazy on read (hot-path cost = one compare) — callers schedule purge_expired for idle reclamation. TtlCacheStats surfaces hit/miss/expired/evicted counts for scraping.

Use LruCache when only capacity matters; use TtlCache when freshness windows also apply (session cache, JWT replay cache, DNS cache).

---

Probabilistic sketches

The Bloom / HLL / Count-Min trio — bounded-memory answers to "is X there?", "how many distinct?", "how often?". HMAC-SHA256 keyed hashing with per-filter CSPRNG-sourced keys; adversarial inputs cannot skew past the theoretical error bound.

BloomFilter

let mut bf = BloomFilter.with_target(
    100_000,   // expected items
    1000,      // target FP rate × 1,000,000 (0.1%)
);

bf.insert(key);
if bf.contains(key) { ... }
let was_present = bf.check_and_set(key);   // atomic check-and-set
bf.clear();                                 // new HMAC key generated

Kirsch-Mitzenmacher double hashing: one HMAC call → two 64-bit halves → k probe offsets via h1 + i × h2 mod m. Typical operation: ~150 ns end-to-end.

HyperLogLog

let mut hll = HyperLogLog.new(DEFAULT_PRECISION);   // p=14 ≈ 12 KiB, 0.81% error
hll.add(b"user:alice");
hll.add(b"user:bob");
let approx_distinct: UInt64 = hll.estimate();

// Mergeable sketches across processes share a 32-byte key.
let merged = HyperLogLog.new_with_key(p, shared_key);
merged.merge(&other)?;

Flajolet et al. 2007 with small-range linear-counting correction. Precision p ∈ [4, 16] controls memory/accuracy: p=14 is the Redis PFCOUNT default.

CountMinSketch

let mut cms = CountMinSketch.with_target(0.001, 0.001);
// ≤ 0.1% error (ε) at 99.9% confidence (1 - δ) — 76 KiB.

cms.add(b"user:alice");
cms.add_n(b"bulk-import", 500);
let upper_bound = cms.estimate(b"user:alice");   // may over- but never under-report

Cormode & Muthukrishnan 2005. Width w = ⌈e / ε⌉, depth d = ⌈ln(1/δ)⌉. Saturating u32 cells — no wraparound even at hot items past 4 billion observations.

Reservoir<T>

Status: partial. Fill-phase API (new, offer while len < capacity, len, capacity, seen, take, reset) is conformance-tested on --interp and --aot. The replacement-phase path (offer after len == capacity) is currently gated on the missing core.sys.common.random_bytes intrinsic in the VBC dispatch table — tests pinned in core-tests/collections/reservoir/regression_test.vr.

public type Reservoir<T> is {
    samples:  List<T>,
    capacity: Int,
    seen:     UInt64,
};

let mut res: Reservoir<TraceId> = Reservoir.new(1000);
while let Some(trace) = stream.next() {
    let _ = res.offer(trace);   // Bool: true iff item retained.
}
let sample: List<TraceId> = res.take();

API:

Reservoir.new(capacity: Int) -> Reservoir<T>     // capacity < 1 clamped to 1
res.offer(item: T) -> Bool                       // true iff item retained
res.take(self) -> List<T>                        // consumes
res.len() -> Int                                 // current sample count
res.capacity() -> Int                            // configured cap
res.seen() -> UInt64                             // total items observed
res.reset()                                      // drop samples + zero seen

Behavioural laws (pinned by property_test.vr):

• Capacity clamping: new(n).capacity() = max(n, 1).
• Seen counter: seen() advances exactly once per offer.
• Fill-phase retention: every offer returns true while seen ≤ capacity.
• Length ceiling: len() ≤ capacity() at all times.
• Reset round-trip: reset() ⇒ len = 0 ∧ seen = 0; capacity is preserved.
• Reset idempotency: repeated reset() calls leave the same observable state.
• Capacity invariance: no public API call besides construction changes capacity().

Vitter 1985 Algorithm R — uniform sampling from a stream of unknown length. Every item has marginal probability capacity / stream_length of surviving. Used by tail-sampling tracers, streaming analytics, ML out-of-core shuffling.

Conformance suite: core-tests/collections/reservoir/ — 14 unit + 7 property + 4 integration + 4 pinned regressions.

---

ConsistentHashRing

let mut ring = ConsistentHashRing.new();    // 160 vnodes default (Ketama)
ring.add_node(Text.from("cache-a"));
ring.add_node(Text.from("cache-b"));
ring.add_node(Text.from("cache-c"));

let primary: Maybe<Text> = ring.node_for_key(b"session:42");
let replicas: List<Text> = ring.nodes_for_key(b"key", 3);

Ketama-compatible position derivation — virtual-node positions are sha256(node_name + "-" + decimal(vnode_idx))[..8] as LE u64. Wire-compatible with memcached Ketama, Redis ring_hash, Envoy ring_hash load balancer.

Adding/removing one node moves only key_count / node_count entries (the consistent-hashing property). nodes_for_key(key, N) returns N distinct nodes in preference order — primary first, then replicas.

---

UnionFindInt and UnionFind<T> — Disjoint-Set Union

Status: partial. UnionFindInt (Int-keyed dense path) is conformance-tested end-to-end on both --interp and --aot. Generic UnionFind<T: Hash + Eq> is tested along the working axis (distinct-key make, find on unregistered keys, union creates keys, len tracking) and @ignored in regression_test.vr for the broken axis (idempotent make on duplicate keys, component_size after union). Every defect that gates the remaining coverage is reproduced in the regression suite and tracked.

DSU — Tarjan 1975, with both path compression and union-by-rank, giving amortised inverse-Ackermann (O(α(n)) ≈ O(1)) cost per operation.

Two APIs. Pick the dense one when keys are densely-indexed integers (graph nodes 0..n-1, slot indices, etc.); pick the generic one for strings, UUIDs, or any Hash + Eq carrier.

UnionFindInt — dense Int-keyed (array-backed)

public type UnionFindInt is {
    parent:     List<Int>,
    rank:       List<Int>,
    components: Int,
    size:       List<Int>,
};

let mut uf = UnionFindInt.new(n);

uf.find(x: Int) -> Int                 // canonical root, path-compressed
uf.union(a: Int, b: Int) -> Bool       // true iff this call merged distinct sets
uf.same_set(a: Int, b: Int) -> Bool
uf.component_size(x: Int) -> Int
uf.component_count() -> Int            // O(1) — cached
uf.len() -> Int                        // total elements (== n)
uf.clear()                             // restore initial singleton state

Behavioural contract (laws pinned by property_test.vr):

• Reflexivity: same_set(x, x)
• Symmetry: same_set(a, b) = same_set(b, a)
• Transitivity: same_set(a, b) ∧ same_set(b, c) ⇒ same_set(a, c)
• Union introduces equivalence: union(a, b) ⇒ same_set(a, b)
• Union return-value partition: union(a, b) = true iff a and b were in distinct sets at call entry.
• Idempotent union: a second union(a, b) is a no-op; state and component_count() are unchanged.
• Component-count invariant: each successful union decrements the count by exactly 1; failed unions leave it unchanged.
• Component-size sum: Σ component_size(root_i) = n over distinct roots.
• Find idempotency: find(find(x)) = find(x).
• same_set definition: same_set(a, b) = (find(a) == find(b)).
• Clear restores singletons: post-clear(), every element is its own root and component_count() = n.

Use cases (industry-standard DSU territory):

• Kruskal MST — sort edges by weight, union endpoints, accept the edge iff the union returned true.
• CRDT add-wins set reconciliation — per-key DSU over causal-set representatives.
• Static-analyser equivalence classes — variable aliasing, escape analysis, type-variable bands.
• Image-segmentation connected-component labelling — 4/8-connected pixels via two raster passes.
• Cycle detection in incremental graph construction — same_set(u, v) before adding edge (u, v).

UnionFind<T: Hash + Eq> — generic, map-backed

public type UnionFind<T: Hash + Eq> is {
    parent:     Map<T, T>,
    rank:       Map<T, Int>,
    size:       Map<T, Int>,
    components: Int,
};

let mut uf: UnionFind<Text> = UnionFind.new();

uf.make(x: T)                          // ensure x is known; idempotent
uf.find(x: &T) -> T                    // canonical root, path-compressed
uf.union(a: T, b: T) -> Bool           // true iff merge happened
uf.same_set(a: &T, b: &T) -> Bool
uf.component_size(x: &T) -> Int
uf.component_count() -> Int
uf.len() -> Int                        // distinct keys ever introduced

Same algebraic laws as UnionFindInt. The "make is idempotent on duplicate keys" axis is currently blocked by upstream Map.contains_key(&K) defect (see Open defects).

Length protocol

Both types implement Length, so the free-function form works:

assert_eq(uf.len(), len(&uf));

Performance

• find: amortised O(α(n)) ≈ O(1). α is the inverse Ackermann function — bounded by 4 for any conceivable input size.
• union: amortised O(α(n)).
• component_count: O(1). The counter is maintained in-line, not recomputed.
• component_size: O(α(n)) (one find).
• clear (UnionFindInt only): O(n) on the dense backing arrays.

Conformance suite

core-tests/collections/union_find/ — 52 non-ignored tests, 11 pinned regressions. Run with verum test --interp --filter test_uf_ and verum test --interp --filter property_int_.

---

Open defects in collections

Tracked across the conformance suite under core-tests/collections/<module>/regression_test.vr. Each entry below links to the regression-pinned reproducer.

#	Defect	Surface	Status
1	Map.get(K) -> V returns zero-value on miss instead of Maybe<V>	core/collections/map.vr:457; ~666 call sites	tracked, fix is a cross-cutting migration
2	Map.contains_key(&K) silently returns false (type mismatch)	core/collections/map.vr:614; reachable from union_find.vr:183	tracked
3	Map.get_optional / Map.get_key_value lenient-skipped at runtime	core/collections/map.vr:504, 579	tracked, requires compiler-side investigation
4	Text.from_utf8_unchecked heap-allocated Text has zero-length as_bytes() despite correct len field	core/text/text.vr:439; surfaces in every Map<Text, V> populated via Text.from(...)	tracked, requires interpreter-side RefSliceRaw fix
5	Text.eq(&self, &Text) method dispatch returns false for byte-identical literal Texts	core/text/text.vr:3370; method-resolution lands on the wrong impl	tracked
6	core.sys.common.random_bytes intrinsic missing from VBC dispatch table	reachable from core/collections/reservoir.vr:148; gates Reservoir.offer replacement phase, plus any core.base.random.* use site (Bloom, HyperLogLog HMAC keys)	tracked

These defects are not specific to the UnionFind types — they are foundational stdlib / language-level gaps that cascade into every module that touches Map<Text, V> or Map<&K, V>. Closing any of them unlocks coverage in multiple downstream modules at once.

Architectural snapshot 2026-05-23

A full re-audit of the --interp test surface across every core-tests/collections/<module>/regression_test.vr was completed on 2026-05-23. Snapshot of the regression-suite pass rates:

Module	Regression suite	Notes
lru	full unit + regression green (41/41)	stable
deque	29/29 green	stable (uplifted from partial)
set	8/10 (2 @ignored)	into_list / extract_if pinned
map	6/8 (2 @ignored)	Map.from / get_key_value pinned
heap	10/11 (1 fail)	Heap.into_inner generic-receiver dispatch
list	5/11 (6 @ignored)	List.of / from_elem / fill / sort_by / is_sorted pinned
slice	6/14 (1 fail + 7 @ignored)	position misdispatch
multiset	0/7 (all @ignored)	iter() wrapper-dispatch class
reservoir	4/4 green	partial (sample-phase tests outside regression file)
toposort	5/6 (1 @ignored)	Text.from error-payload pinned
trie	0/3 (all @ignored)	Map.get_mut dispatch
btree	all @ignored	record-storage corruption on SetF of Maybe<Heap<T>>
bloom	3 fail + 8 @ignored	cross-module fill_secure (task #47)
hyperloglog	similar to bloom	task #47
count_min	similar to bloom	task #47
alias_sampler	construction-gated	task #47 + record-layout

Architectural close-outs (single root cause clusters)

Six of the regression-only modules above share two architectural root causes, not the per-module defects the original audit suggested:

1. Task #47 — cross-module Call name-encoding (4 modules: bloom, hyperloglog, count_min, partially alias_sampler). The stdlib's bytecode format currently encodes cross-module function calls as raw Call(func_id). At archive load time, the per-module remap resolves the id within the producer module only; transitively- loaded stdlib bodies whose home isn't directly mounted by the user fall through Tier-3 identity fallback and land on whatever unrelated function happens to occupy the resolved id (live failure: DequeIntoIter.zip_longest, DequeDrain.map). Documented in crates/verum_vbc/src/codegen/mod.rs:5687-5750 with historical experiments showing per-module extern-stub synthesis explodes runtime.vbca from 12.9 MB to 110-134 MB. The fundamental fix is to change the bytecode encoding to embed the function name as a StringId so the user-side merge resolves by name once per Call site, not once per (module × imported-function) pair.

2. BTreeMap record-storage corruption (2 modules: btree, partially adjacency_list). SetF of a Maybe<Heap<T>>-typed field somehow resets the record's data area to 0 bytes. Reproduced minimally: let mut m: BTreeMap<Int,Int> = BTreeMap.new(); m.insert(1,100); m.get(&1); → Panic: field access out of bounds: field index 0 exceeds object data size 0. No Rust-side intercept for BTreeMap exists (only for iterator wrappers), so this is pure codegen + runtime SetF behaviour for nested-Heap fields. Fix path: audit the SetF handling for record fields holding Maybe<Heap<T>> / Maybe<Shared<T>>, OR add an explicit BTreeMap runtime intercept that controls the allocation slot count.

Closing either of these architectural defects promotes multiple collection modules from regression-only to partial or stable in one fix. The per-module audit files under core-tests/collections/<module>/audit.md carry the full per-defect inventory for each.