Collections

Arrays, lists, queues, sets and dictionaries, with their iterators.

Generated by bin/build_library_doc.py from the kernel sources. Do not edit by hand: change the generator, or the doc comments in kernel/src/, and re-run it.

Sequences

CLASS Array

IMPLEMENTS Cloneable, Collection, Shuffleable

Opaque-size, ordered, indexable collection.

The foundation collection class. Stack, Queue, Deque, LinkedList, Set, and SortedList all compose on top of Array's storage; the hash-based collections (Dictionary) keep their own backing.

Element access is by integer index in 0..length-1. Out-of-bounds reads throw IndexOutOfBoundsError; out-of-bounds writes throw the same. Mutation methods come in move and copy pairs:

For class-typed T, COPY routes through Cloneable.clone(); T must implement Cloneable for any *Copy method to be reachable.

Removal:

Inspection without removal:

Iteration:

Sorting and search:

Functional transforms (map / filter / reduce) are pure-Envzn loops over the element domain and return new Arrays.

The storage shorthand T[] is the same physical layout as Array[T]; the difference is API surface. T[] exposes only the minimal value-array surface (subscript read + HWM write proxy, .length, .capacity, clear(), remove(i), iterator()); Array[T] does the richer work (append / insertAt / count / sort …) on top of that surface and maintains a public length field. The sole developer-visible difference between int32[] and an object T[] is that object elements must relocate with := (a move), never a plain =.

kernel/src/Array.ev:71

Constructors

INIT()

Default constructor

INIT(int64 presized)

Presized constructor to reduce the malloc activity

Methods

METHOD iterator() RETURNS ArrayIterator[T]

Returns a fresh ArrayIterator[T] at position 0 — the FINAL concrete iterator class (covariant against the inherited Iterable.iterator() shape). Each call returns an independent iterator; multiple may exist concurrently on the same Array. The concrete return type lets the emitter inline hasNext() / next() on FOR/IN loops over Array; callers binding to BidirectionalIterator OF T still typecheck via class-to- interface upcast.

METHOD size() RETURNS int64

Number of elements currently stored. Read-only, O(1).

METHOD isEmpty() RETURNS boolean

Countable — the other half of size(). Array carries the whole Collection contract now (size, isEmpty, iterator), and none of the three asks anything of T: that is what lets Array join Collection while keeping its qualifier at Cloneable-or-primitive.

METHOD clone() RETURNS Array[T]

Deep copy. Each element is cloned via T->clone(); T must implement Cloneable when T is a class type. For T IMPLEMENTS Inoperative (opaque only today): returns an empty Array — Inoperative values are opaque so we can't preserve them on clone.

MODIFY METHOD append(T value) RETURNS STATUS

Append value to the end. Per §10.2 the bare-named form consumes the source — value is moved into the array and the caller's source is poisoned (post-call use is a compile error). For a deep-copy variant that leaves the caller's source valid, use appendCopy. O(1) amortised.

EMPTY-reject (class-typed T only): an EMPTY class-handle value is refused with FAILURE before any state change — the collection only ever holds real owned objects, so every subsequent peek/pop/at sees a populated slot. Per §9.3 IS VALID is meaningful only on class handles; the check is gated via WHEN T IMPLEMENTS Cloneable (the kernel's proxy for "class-shaped T") and elided for primitive / struct T.

MODIFY METHOD appendCopy(REFERENCE T value) RETURNS STATUS

Append a deep copy of value to the end. value stays fully valid for the caller after the call. For class-typed T, the copy goes through T->clone(); T must implement Cloneable. For primitive/struct T, value-copy. O(1) amortised. Returns SUCCESS, or FAILURE if backing storage rejected the insert.

METHOD __op_index__(int64 index) RETURNS MUTABLE REFERENCE T

Reference to element at index i. Throws IndexOutOfBoundsError if i is out of range — bounds check lives in _EvArray<char32_t>::operator[]. A borrow-propagating ("mirror") accessor: the result mirrors the receiver's mutability (mutable array -> MUTABLE REFERENCE, const -> read-only REFERENCE).

METHOD subscript(int64 index) RETURNS | MUTABLE REFERENCE T

Bounds-checked reference into the element at index — the lowering target for arr[idx] syntax on Array[T] receivers, and a borrow- propagating ("mirror") accessor: SUCCESS populates result with a reference that mirrors the receiver's mutability (a mutable array yields a MUTABLE REFERENCE for in-place modification, a const array a read-only REFERENCE); out-of-bounds populates s with FAILURE. Caller pattern: IF arr[i] THEN { use($RETURNED) } ELSE { log($!) }. The reference is valid only while the Array is not mutated (mutation lock). Replaces the former at / subscript / mutableAt accessor set.

MODIFY METHOD setAt(int64 index, T value) RETURNS STATUS

Replace the element at index. Per §10.2 the bare-named form consumes the source — value is moved into the array and the caller's source is poisoned. The previous element is destroyed. Returns FAILURE on out-of-bounds.

MODIFY METHOD setAtCopy(int64 index, REFERENCE T value) RETURNS STATUS

Replace the element at index with a deep copy of value. value stays valid for the caller. Throws IndexOutOfBoundsError on bad index.

MODIFY METHOD insertAt(int64 index, T value) RETURNS STATUS

Insert value at index, shifting subsequent elements right by one. Per §10.2 the bare-named form consumes the source — value is moved into the array and the caller's source is poisoned. Valid index is 0..length inclusive (index == length appends). Returns FAILURE on out-of-bounds. O(n) — shifts everything to the right of the insertion point.

MODIFY METHOD insertAtCopy(int64 index, REFERENCE T value) RETURNS STATUS

Insert a deep copy of value at index. value stays valid. Same index rules and complexity as insertAt.

MODIFY METHOD swap(int64 i, int64 j) RETURNS STATUS

Exchange the elements at i and j in place. Nothing is copied and no slot is ever empty — this is how an element moves WITHIN an array, since arr[k] := arr[j] is E6040 (a subscript is a reference to a slot the array keeps owning). Returns FAILURE if either index is out of bounds.

MODIFY METHOD replace(int64 index, T value) RETURNS | T

Put value at index and hand back the element it displaced. Per §10.2 value is consumed. Unlike setAt, which destroys the previous element, this returns it — the owned counterpart of reading arr[i]. Pipe-XOR: FAILURE on out-of-bounds. O(1): the new element is parked at the tail, swapped into place, and the old one is removed from the tail, where removal shifts nothing.

MODIFY METHOD remove(int64 index) RETURNS | T

Remove the element at index and return it. Pipe-XOR: SUCCESS populates removed with the value moved out of the array; FAILURE populates status with the bounds violation. Subsequent elements shift down. O(n). index is int64.

MODIFY METHOD clear() RETURNS void

Remove all elements; the array becomes empty.

METHOD map(LAMBDA func) RETURNS Array[T]

Apply func to every element; return a new Array with the transformed values, in the same order. (Bug #59 / I.J.iii — unblocked 2026-06-26 when LAMBDA-param invocation landed.)

METHOD filter(LAMBDA pred) RETURNS Array[T]

Return a new Array containing only the elements for which pred(elem) is TRUE, in their original order.

MODIFY METHOD reduce(REFERENCE T initial, LAMBDA acc) RETURNS T

Fold left: starting with initial, repeatedly apply acc(accumulator, elem) for each element in order. Returns the final accumulator value.

MODIFY METHOD shuffle(MUTABLE REFERENCE Shuffler rng) RETURNS void

Shuffleable OF T — in-place Fisher-Yates.

Lives on Array, not OrderedArray, so every subclass inherits it. It costs Array nothing: the storage's swap works for every T Array's qualifier admits, so no interface requirement is added by its being here. It was also the one method whose presence on OrderedArray contradicted that class: shuffling destroys exactly the ordering the name promises. Walks from the last index down, swapping each element with a uniformly-chosen earlier-or-equal slot drawn from rng. The exchange is the storage's own swap: no clones, one form for every T. (It used to clone both elements of a class T and move the clones back in — two deep copies per step.)

CLASS ArrayIterator

IMPLEMENTS BidirectionalIterator

Concrete BidirectionalIterator OF T for Array[T].

An Array[T]'s ->iterator() method yields a fresh ArrayIterator[T] at position 0. Multiple iterators on the same Array are independent (each has its own cursor); the source Array is locked against mutation while any iterator is held (per §Iterator's mutation-lock rule).

Notable: The iterator holds a REFERENCE T[] source directly into the source Array's data storage (collection storage shorthand) — validated under §REFERENCE structural condition 2 (mutation-locked at INIT). All element access goes through the T[] implicit methods (->size(), [i]).

kernel/src/ArrayIterator.ev:35

Constructors

INIT(REFERENCE T[] source)

constructor that requires a REFERENCE The iterator never owns the vector — .source is a REFERENCE field, not an owning copy — so a const reference is the correct shape and accepts both const-source (Array's iterator() is non- mutating) and non-const-source call sites.

Methods

METHOD hasNext() RETURNS boolean

returns TRUE if we've not reached the end

MODIFY METHOD next() RETURNS | REFERENCE T

Pipe-XOR: SUCCESS populates the value slot with a non-owning reference; end-of-iteration populates STATUS with FAILURE. a REFERENCE is non-owning, so referencing it is harmless; only the by-value lift (popFirst/popLast) rejects opaque. This matches Array.at, which has never guarded opaque.

METHOD peek() RETURNS | REFERENCE T

peek at the next item without advancing the iterator

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE T

skip(n) — moves cursor forward by n positions. Parameter is unsigned per spec §Iterator (forward-only contract). Pipe-XOR: SUCCESS with the element at the new position, or FAILURE if out of bounds. skip(0) is equivalent to peek().

METHOD hasPrevious() RETURNS boolean

returns TRUE if the iterator is not at the first element

MODIFY METHOD previous() RETURNS | REFERENCE T

mirror of next: on SUCCESS, it returns a REFERENCE to the value and decrements the iterator's cursor; on FAILURE it returns only the status message

MODIFY METHOD skipBack(uint64 n) RETURNS | REFERENCE T

skipBack(n) — moves cursor backward by n positions. Symmetric counterpart to skip(n) on BidirectionalIterator. Pipe-XOR: SUCCESS with the element at the new position, or FAILURE if start is reached. skipBack(0) is equivalent to peek().

CLASS OrderedArray

EXTENDS Array · IMPLEMENTS Comparable>, Equatable>

Opaque-size, ordered, indexable collection.

The foundation collection class. Stack, Queue, Deque, LinkedList, Set, and SortedList all compose on top of Array's storage; the hash-based collections (Dictionary) keep their own backing.

Element access is by integer index in 0..length-1. Out-of-bounds reads throw IndexOutOfBoundsError; out-of-bounds writes throw the same. Mutation methods come in move and copy pairs:

For class-typed T, COPY routes through Cloneable.clone(); T must implement Cloneable for any *Copy method to be reachable.

Removal:

Inspection without removal:

Iteration:

Sorting and search:

Functional transforms (map / filter / reduce) are pure-Envzn loops over the element domain and return new Arrays.

The storage shorthand T[] is the same physical layout as Array[T]; the difference is API surface. T[] exposes only the minimal value-array surface (subscript read + HWM write proxy, .length, .capacity, clear(), remove(i), iterator()); Array[T] does the richer work (append / insertAt / count / sort …) on top of that surface and maintains a public length field. The sole developer-visible difference between int32[] and an object T[] is that object elements must relocate with := (a move), never a plain =.

kernel/src/OrderedArray.ev:71

Constructors

INIT()

Default constructor

INIT(int64 presized)

for presized Stack allocation

Methods

OVERRIDE METHOD clone() RETURNS OrderedArray[T]

Deep copy. Each element is cloned via T->clone(); T must implement Cloneable when T is a class type. For T IMPLEMENTS Inoperative (opaque only today): returns an empty Array — Inoperative values are opaque so we can't preserve them on clone.

MODIFY METHOD sort() RETURNS void

In-place insertion sort using T->isLessThan(other). T must implement Comparable[T] — the compiler emits a clear "T does not implement Comparable" diagnostic at instantiation otherwise. Each element is walked down by swapping it with its left neighbour while it is strictly smaller, so equal elements keep their order (stable). No element is copied and no slot is ever empty: the old form lifted the element out with T key := .data[i], which is a move from a reference (E6040) and silently deep-cloned every key. O(n^2) worst case; acceptable for the small-N collections this V1 kernel typically holds. A heap-or-merge-sort upgrade is a V2 candidate if profiling demands it.

METHOD contains(REFERENCE T value) RETURNS boolean

Linear scan for an element equal to value. T must implement Equatable[T] for class T. O(n).

METHOD equals(REFERENCE OrderedArray[T] other) RETURNS boolean

Element-wise equality. Two arrays are equal when they are the same length and every element at the same index is equal — which makes two EMPTY arrays equal, the case the previous form got wrong: it seeded result = FALSE and only ever set it TRUE from inside the element loop, so a pair of empty arrays passed the length test, never entered the loop, and were reported UNEQUAL.

METHOD isLessThan(REFERENCE OrderedArray[T] other) RETURNS boolean

LEXICOGRAPHIC, the same order String.isLessThan settled on and for the same reason. The first differing element decides; if neither array differs through the shorter one's length, the shorter is less — so a prefix sorts before what extends it.

This returned .length < other.length. Length-first is a different total order, not a cheaper route to this one: it ranks [9] below [1,1] and calls every pair of same-length arrays equal-or-greater regardless of content, which silently reorders any OrderedArray-keyed RedBlackTreeDictionary and makes sort() over arrays-of-arrays wrong.

CLASS Deque

IMPLEMENTS Cloneable, Collection

Defines the Deque[T] class per ENVZN_CONSTITUTION §Deque (L659–680).

Deque[T] is a double-ended queue: O(1) push and pop at either end, no random-access indexing, no mid-list operations. The contract is intentionally narrower than LinkedList[T] — Deque is a LinkedList with a constrained API surface that names the ends as "front" and "back" rather than "first" and "last."

Composes on LinkedList[T], which provides exactly Deque's contract: - O(1) at both ends (LinkedList.prepend / append / popFirst / popLast / peekFirst / peekLast). - BidirectionalIterator OF T. - Cascading clone() via Cloneable. So Deque is pure delegation — no new storage, no new iterator, just a renamed-and-narrowed view over LinkedList.

kernel/src/Deque.ev:29

Constructors

INIT()

Methods

METHOD clone() RETURNS Deque[T]

Hand-written clone() — AUTO refused for the same cascade reason as Queue / Stack / LinkedList: the synthesis walker can't see T's Cloneable status from this instantiation site through the LinkedList[T] composition. Walk the underlying LinkedList's iterator and pushBack a deep clone of each element — ordering preserved (front-to-back).

METHOD iterator() RETURNS LinkedListIterator[T]

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

Number of elements currently stored. Read-only, O(1).

MODIFY METHOD clear() RETURNS void

MODIFY METHOD pushFront(T value) RETURNS STATUS

FRONT-SIDE OPERATIONS — pushFront / popFront / peekFront

MODIFY METHOD pushFrontCopy(REFERENCE T value) RETURNS STATUS

MODIFY METHOD popFront() RETURNS | T

METHOD peekFront() RETURNS | REFERENCE T

MODIFY METHOD pushBack(T value) RETURNS STATUS

BACK-SIDE OPERATIONS — pushBack / popBack / peekBack

MODIFY METHOD pushBackCopy(REFERENCE T value) RETURNS STATUS

MODIFY METHOD popBack() RETURNS | T

METHOD peekBack() RETURNS | REFERENCE T

CLASS Queue

EXTENDS Stack

Defines the Queue[T] class per ENVZN_CONSTITUTION §Queue.

Queue[T] is a FIFO collection implemented as a thin layer over Array[T] (a.k.a. T[]). All storage and per-element ownership semantics live in Array[T]; Queue contributes the FIFO discipline and the public count field. Front is index 0, back is the last element — enqueue appends, dequeue removes from index 0.

Performance note (Path B-pragmatic tradeoff): - enqueue / enqueueCopy are O(1) amortised — same as Stack push - dequeue is O(n) — removes from index 0; Array shifts elements down - peek is O(1) Callers who need O(1) dequeue should use Deque[T], which gets its own std::deque backing (per Path B-pragmatic split — see project_kernel_demagic_stage22.md memory). Queue-on-Array eats the dequeue cost in exchange for a single backing storage shape shared with Stack and SortedList.

kernel/src/Queue.ev:31

Constructors

INIT()

default constructor

INIT(int64 presized)

for presized Stack allocation

Methods

OVERRIDE METHOD clone() RETURNS Queue[T]

Deep copy. Each element is cloned via T->clone(); T must implement Cloneable when T is a class type. For T IMPLEMENTS Inoperative (opaque only today): returns an empty Array — Inoperative values are opaque so we can't preserve them on clone.

MODIFY METHOD enqueue(T value) RETURNS STATUS

Add value at the back of the queue. Per §10.2 the bare-named form consumes the source — value is moved through Array's owning append into the queue's backing.

MODIFY METHOD enqueueCopy(REFERENCE T value) RETURNS STATUS

Deep-copy form of enqueue. value stays valid for the caller; the clone is what the backing array stores.

OVERRIDE METHOD peek() RETURNS | REFERENCE T

Remove and return the front element. Pipe-XOR: SUCCESS populates value; FAILURE when the queue is empty. O(n) — depends on Array providing popFirst() with move-out semantics for class T. FIFO peek — the FRONT element, which is NOT what Stack.peek() returns.

Queue EXTENDS Stack, and Stack's peek() is LIFO: it forwards to peekLast(). Inherited unchanged, a Queue reported its most recently ENQUEUED element as its front — dequeue() (which uses popFirst) and peek() disagreed about which end the queue's head is. queueSmoke caught it as "expected 11, got 22".

OVERRIDE is required here (W7020): this reimplements a CONCRETE inherited method rather than fulfilling an abstract contract.

MODIFY METHOD dequeue() RETURNS | T

CLASS Stack

EXTENDS Array

Defines the Stack[T] class per ENVZN_CONSTITUTION §Stack.

Stack[T] is a LIFO collection implemented as a thin layer over Array[T] (a.k.a. T[]). All storage and per-element ownership semantics live in Array[T]; Stack contributes the LIFO discipline and the public count field.

Design philosophy: by building Stack on Array[T], all the FOREIGN/T-substitution/ownership questions surfaced by the original Stack.ev preview are relocated to Array[T] — exactly once, instead of once per collection. See Array.ev (forthcoming) for those questions resolved.

kernel/src/Stack.ev:25

Constructors

INIT()

default constructor

INIT(int64 presized)

for presized Stack allocation

Methods

OVERRIDE METHOD clone() RETURNS Stack[T]

Deep copy. Each element is cloned via T->clone(); T must implement Cloneable when T is a class type. For T IMPLEMENTS Inoperative (opaque only today): returns an empty Array — Inoperative values are opaque so we can't preserve them on clone.

MODIFY METHOD push(T value) RETURNS STATUS

Push value onto the top. Per §10.2 the bare-named form consumes the source — value is moved through Array's owning append onto the stack's backing.

MODIFY METHOD pushCopy(REFERENCE T value) RETURNS STATUS

Deep-copy form of push. value stays valid for the caller; the clone is what the backing array stores.

MODIFY METHOD pop() RETURNS | T

Remove and return the top element. Pipe-XOR: SUCCESS populates value; FAILURE when the stack is empty. Depends on Array providing popLast() with move-out semantics for class T.

METHOD peek() RETURNS | REFERENCE T

Return (without removing) the top element as a REFERENCE handle. Multi-return per the kernel peek contract — STATUS == FAILURE when empty, SUCCESS otherwise. Delegates to Array.peekLast.

MODIFY METHOD popLast() RETURNS | T

Remove and return the last element. FAILURE if empty. Ownership of the returned element transfers to the caller. O(1). For T IMPLEMENTS Inoperative (opaque): always returns FAILURE — the stored payload is opaque and can't be lifted out by-value.

MODIFY METHOD popFirst() RETURNS | T

Remove and return the first element. FAILURE if empty. O(n) — shifts every remaining element down by one. For T IMPLEMENTS Inoperative: always returns FAILURE (see popLast).

METHOD peekLast() RETURNS | REFERENCE T

Read the last element without removing it. STATUS is FAILURE when the array is empty (value is EMPTY); SUCCESS otherwise with value referencing the element in place. The REFERENCE handle is valid only while no mutation occurs on the Array.

METHOD peekFirst() RETURNS | REFERENCE T

Read the first element without removing it. Same pipe-XOR shape as peekLast.

CLASS SortedList

IMPLEMENTS Cloneable, Collection

Defines the SortedList[T] class per ENVZN_CONSTITUTION §SortedList (L703–716).

SortedList[T] is a collection that maintains its elements in ascending order (per T->isLessThan) at all times. Insertion walks to the sort position and splices; the order is invariant across the public API — there is no operation that produces an out-of-order sequence.

Composes on LinkedList[T], as do Stack and Queue — one backing store shared across the composed collections. LinkedList provides mid-chain insert/remove via its insertAt / removeAt methods; SortedList drives them with a Comparable-aware position search.

────────────────────────────────────────────────────────────────── ORDER INVARIANT ──────────────────────────────────────────────────────────────────

At every public-API boundary, for any two indices i < j in the list, the element at i is isLessThan the element at j OR isEqualTo the element at j. Duplicates (per Equatable.isEqualTo, inherited via Comparable[T] EXTENDS Equatable[T]) are allowed and stored adjacently.

────────────────────────────────────────────────────────────────── SHORT-CIRCUIT SEARCH ──────────────────────────────────────────────────────────────────

Because the list is always sorted, contains and remove walk from the front and stop early when they cross the value's expected position:

Mean-case work is O(n/2) for both; worst-case is O(n). A real production version could replace LinkedList with a balanced tree (red-black, AVL) for O(log n), but that's a much larger implementation. This V1 form trades sorted-search complexity for implementation simplicity.

kernel/src/SortedList.ev:62

Fields

Constructors

INIT()

Methods

METHOD clone() RETURNS SortedList[T]

Hand-written clone() — AUTO refused for the same cascade reason as Queue / Stack / Deque / LinkedList: the synthesis walker can't see T's Cloneable status from this instantiation site through the LinkedList[T] composition. Walk the underlying LinkedList's iterator and append a deep clone of each element. Sort order is preserved because the source list is already sorted and we visit front-to-back; we use data->append (which adds to tail) rather than going through SortedList.add's per-insert binary scan.

METHOD iterator() RETURNS LinkedListIterator[T]

ITERATOR — delegate to LinkedList's BidirectionalIterator

The element order is insertion order, which by the order invariant is also ascending. Callers iterate front-to-back for ascending traversal; back-to-front via previous() for descending.

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

Number of elements currently stored. Read-only, O(1).

MODIFY METHOD clear() RETURNS void

MODIFY METHOD insert(T value) RETURNS STATUS

INSERT

Walks the iterator to find the first position where value->isLessThan(elem) becomes TRUE — that's where value belongs in the sorted order. The iterator is held in a nested block so it drops (releasing the mutation lock on _data) before the call to _data->insertAt. Insert value at the position that keeps the list sorted. Per §10.2 the bare-named form consumes the source — value is moved into the list. The walk reads value for comparison (read-only, doesn't consume) before the final .data->insertAt call which performs the move.

MODIFY METHOD insertCopy(REFERENCE T value) RETURNS STATUS

Deep-copy form of insert. value stays valid for the caller; the clone is the one moved into the list.

METHOD contains(REFERENCE T value) RETURNS boolean

CONTAINS / REMOVE — short-circuit on Comparable order

MODIFY METHOD remove(REFERENCE T value) RETURNS boolean

Remove the first element equal to value. Returns TRUE if a match was found and removed, FALSE otherwise.

METHOD peekFirst() RETURNS | REFERENCE T

FRONT / BACK ACCESS — convenience wrappers over LinkedList

peekFirst returns the smallest element; peekLast the largest. popFirst / popLast remove and return them. All four are O(1) by virtue of LinkedList's existing front/back operations.

METHOD peekLast() RETURNS | REFERENCE T

MODIFY METHOD popFirst() RETURNS | T

MODIFY METHOD popLast() RETURNS | T

CLASS Set

IMPLEMENTS Cloneable, Collection

Set is a thin pure-Envzn wrapper over a Dictionary

STORAGE Set[V, H] holds Dictionary[V, int64, H] data (the interface), backed by a ChainedHashDictionary. The element is the dictionary KEY (collision-safe: distinct elements that hash equal land in the same bucket and are told apart by Equatable, never merged); the value is an unused int64 dummy (0). A boolean value is impossible — the Dictionary qualifier bans boolean V — so a small int is the minimal placeholder.

TWO TYPE PARAMETERS Set[V, H]: - V — element type. Hashable + Equatable (the dict's key contract). - H — the Hasher OF V. Callers name a concrete hasher (e.g. Set[int32, DefaultHasher[int32]]); the no-arg INIT lets the backing dictionary CREATE a DefaultHasher[V], a hasher-taking INIT threads a supplied one through. H is phantom in the body (the dict stores the hasher as the Hasher OF V interface).

ITERATION yields the elements (the dict's keys), forward-only, order unspecified. iterator() returns the backing dictionary's key iterator directly — there is no separate SetIterator.

.length is kept in sync by hand: the Dictionary surface has no count(), and insert() is replace-or-add (SUCCESS either way), so add/remove gate on a prior contains to keep the count exact. Set[V, H] — unordered set of unique elements over a Dictionary.

kernel/src/Set.ev:43

Fields

Constructors

INIT()

No hasher — the backing dictionary CREATEs a DefaultHasher[V].

INIT(Hasher[V] h)

Caller-supplied hasher, threaded into the backing dictionary.

INIT(GrowthHint hint, int64 initialCapacity)

Default hasher + sizing hints (forwarded to the dictionary).

INIT(Hasher[V] h, GrowthHint hint, int64 initialCapacity)

Caller hasher + sizing hints.

Methods

METHOD clone() RETURNS Set[V, H]

Deep copy — the backing dictionary clones every key.

METHOD iterator() RETURNS ReferenceIterator[V]

ITERATOR — yields the elements (the dictionary's keys).

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

Number of elements currently stored. Read-only, O(1).

MODIFY METHOD clear() RETURNS void

MODIFY METHOD add(V value) RETURNS STATUS

ADD / REMOVE / CONTAINS Add value (consumed). If already present, the element stays and the moved-in value is dropped; .length is unchanged.

MODIFY METHOD addCopy(REFERENCE V value) RETURNS STATUS

Deep-copy form of add. value stays valid for the caller.

METHOD contains(REFERENCE V value) RETURNS boolean

MODIFY METHOD remove(REFERENCE V value) RETURNS STATUS

Remove value. SUCCESS if it was a member, FAILURE otherwise.

METHOD unionWith(REFERENCE Set[V, H] other) RETURNS Set[V, H]

SET ALGEBRA — |+| / |&| / |-| bind to these. Union — every element from either input (deduped).

METHOD intersectionWith(REFERENCE Set[V, H] other) RETURNS Set[V, H]

Intersection — elements present in BOTH inputs.

METHOD differenceWith(REFERENCE Set[V, H] other) RETURNS Set[V, H]

Difference — elements in SELF but NOT in other (asymmetric).

CLASS Box

IMPLEMENTS Cloneable

Defines the Box[T] class per ENVZN_CONSTITUTION §Box (L602–616).

Box[T] is a heap-allocating transparent wrapper around a single T. Its primary purpose is to break the type cycle that would otherwise make a self-recursive GROUP infinite-sized:

GROUP Expr {
    Number n
    BinaryExpr        // contains Box[Expr] — the recursion
                       // through Box's heap pointer breaks
                       // the cycle for std::variant
}

CLASS BinaryExpr {
    Box[Expr] left
    Box[Expr] right
    String op
}

At the C++ emission layer, Box[T] is std::unique_ptr<T> — single owner, heap-indirected, fixed-size at the variant level. The transparency promised by the spec (reading a Box field yields T, not Box[T]; writing a T to a Box field auto-wraps) is compiler sugar above this class, not anything the class itself implements. The methods below are the explicit surface that the sugar desugars to.

Compiler features (transparency sugar — not in this class): - Auto-wrap on assignment. A class field declared Box[T] foo accepts a T-typed RHS; the compiler emits the equivalent of .foo = CREATE Box[T](rhs) for fresh INITs and .foo->set(rhs) for reassignments. - Auto-unwrap on read. Reading instance.foo where .foo is a Box[T] field yields T (specifically a REFERENCE T handle via the equivalent of .foo->value()); the user never sees the Box wrapper. - MATCH transparency. When a GROUP variant arm contains a boxed type, MATCH dispatches on the inner T, not on Box[T].

None of those three features live inside this file — they're compiler-side rewrites. They reduce every user-facing interaction with Box to an Envzn-side method call on the surface declared below.

kernel/src/Box.ev:58

Constructors

INIT(T value)

The only constructor. value is consumed (a plain parameter owns). The compiler's auto-wrap rewrite produces CREATE Box[T](rhs) when initialising a Box[T] field from a T-typed expression.

Methods

METHOD clone() RETURNS Box[T]

Hand-written rather than AUTO: Box has no zero-arg INIT (the user-facing model has no "empty box" state), so the cascade synthesis path doesn't apply. T must implement Cloneable when T is a class type; the explicit ->clone() call below surfaces the requirement as a compile error on the Box[T] instantiation that triggers it.

METHOD value() RETURNS REFERENCE T

── value — return a non-owning handle ──────────────────────── The auto-unwrap rewrite for reads of a Box[T] field. Returns a non-optional REFERENCE T into SELF's owned .inner. .inner is always populated (set by INIT and never cleared), so the reference is always valid; the reference checker proves it without runtime infrastructure.

METHOD valueClone() RETURNS T

── valueClone — return an owned copy ───────────────────────── The path callers take when they need an owning T (e.g. to store elsewhere, to mutate independently). T must be Cloneable; the cascade-failure rule fires at instantiation otherwise.

MODIFY METHOD set(T value) RETURNS void

── set — replace the wrapped value ─────────────────────────── Drops the previous inner and installs value (owned). Bug #32: := to a populated non-Optional owning field drops the previous owner via its destructor, then installs the new owner from the RHS. Box never enters a "moved-out" state observable to the user — the drop and the install happen as a single operator step.

ENUM GrowthHint

GrowthHint — advisory sizing hint for hash-based collections (Dictionary impls, Set). Passed at construction alongside an initial capacity so an implementation can tune its backing storage.

V1: the hint is accepted and stored but only initialCapacity drives behavior (ChainedHashDictionary pre-sizes its bucket array). GrowthHint-driven tuning (shrink policy, load-factor selection) is a future performance pass.

kernel/src/enums.ev:207

Case Description
? —
? —
? —

Lists

CLASS LinkedList

IMPLEMENTS Cloneable, Collection

Defines the LinkedList[T] class per ENVZN_CONSTITUTION §LinkedList.

LinkedList[T] is a doubly-linked list with O(1) push/pop at both ends and O(n) traversal/lookup. The forward chain is owning; back-pointers are explicit REFERENCE, re-bound with =@.

LinkedList is the foundation for Deque (composes on LinkedList for O(1) both-end ops) and SortedList (composes on LinkedList; insert walks to the sort spot via Comparable[T]). Together with Array, this reduces the kernel to two backing stores.

────────────────────────────────────────────────────────────────── STRUCTURE — sentinels + chain ──────────────────────────────────────────────────────────────────

Every list always contains two sentinel nodes — a "starter" at the head and an "ender" at the tail. They exist on construction and are never removed. User nodes live strictly between them.

_head (id=0) ⇄ user1 ⇄ user2 ⇄ ... ⇄ userN ⇄ _tail_ref (id=1)

Forward arrows (→ in the diagram, next field) are owning unique_ptrs. Backward arrows (← in the diagram, prev_ref field) are non-owning REFERENCEs.

The list class holds: - _head — owning non-Optional sentinel; this owns the entire forward chain transitively through .next. - _tail_ref — non-owning REFERENCE to the ender sentinel; needed for O(1) end-side operations without traversing the whole chain. The ender is itself owned (via the forward chain) by the node that immediately precedes it. - _nextId — counter for new user-node IDs (starts at 2). - length — public count of user nodes (excludes sentinels).

Empty list: _head → ender (head.next owns ender; head.prev_ref is EMPTY; ender.prev_ref REFERENCEs head; ender.next is EMPTY).

────────────────────────────────────────────────────────────────── SPLICE PATTERN ──────────────────────────────────────────────────────────────────

Each insert/remove follows a consistent shape: (a) move owning links via := (always taking the existing value out of an Optional owning field BEFORE overwriting the field — otherwise the unique_ptr destructor frees the value mid-splice); (b) REBIND back-pointers via =@ (REFERENCE rewires; structural conditions checked); (c) move the new owning link into the predecessor's .next slot last, completing the splice.

Optional unwraps use IF X IS NOT VALID { PANIC } to convert statically-unreachable EMPTY branches (e.g. _tail_ref.prev_ref is always set after INIT) into explicit kernel-invariant THROWs — making "this can't happen" auditable instead of hiding behind silent fallbacks.

kernel/src/LinkedList.ev:72

Fields

Constructors

INIT()

Constructs both sentinels and wires them. After this returns, head → ender (head.next owns the ender), and the list is empty.

Methods

METHOD clone() RETURNS LinkedList[T]

Hand-written clone() — required because LinkedList carries a REFERENCE field (.last_node_ref) that AUTO clone cannot rewire onto the cloned topology. Builds a fresh empty list, walks the current chain directly (no heap iterator), and appends a deep-clone of each user value. The new list owns its own sentinel chain with correctly-wired last_node_ref (set by append() on every push).

METHOD iterator() RETURNS LinkedListIterator[T]

Per spec L767, LinkedList exposes BidirectionalIterator OF T. Concrete class is LinkedListIterator (separate file). Pass .head by-& so the iterator's REFERENCE binding satisfies §REFERENCE condition 2 (mutation-locked at INIT) without moving ownership of .head out of SELF.

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

Number of elements currently stored. Read-only, O(1).

MODIFY METHOD prepend(T value) RETURNS STATUS

FRONT-SIDE OPERATIONS (right after head sentinel) Insert value at the front. value is cloned in via LinkedListNode's INIT (const-ref param-passing, LOCKED 2026-05-12).

Splice ordering (Bug #32 move-out-before-overwrite): step 1: newNode.next := .head.next (move old first into newNode.next; .head.next is now EMPTY) step 2: .head.next := newNode (move newNode into .head.next; local poisoned) step 3: bump last_node_ref if list was empty

MODIFY METHOD prependCopy(REFERENCE T value) RETURNS STATUS

Deep-copy form of prepend. value stays valid for the caller; the clone is the one moved into the new node.

MODIFY METHOD popFirst() RETURNS | T

Remove and return the front user value. EMPTY if empty.

Splice ordering (Bug #32 move-out-before-overwrite): step 1: popped := .head.next (move; .head.next now EMPTY) step 2: .head.next := popped.next (move the new-first into .head.next) step 3: if popped was the only user node, last_node_ref bumps back to .head

METHOD peekFirst() RETURNS | REFERENCE T

Read (without removing) the front user value. Pipe-XOR shape: SUCCESS populates value with the reference; empty / invariant violation populates s with FAILURE. Never throws.

METHOD at(int32 index) RETURNS | REFERENCE T

Non-owning reference to the value at index (0-based), or FAILURE if out of bounds. O(index) forward walk from the first user node — backs index-based external walkers that cannot hold a LinkedListIterator field (iterator Rule A), e.g. ChainedHashDictionaryIterator. Read-only; the source list stays mutation-locked while the returned reference is held.

MODIFY METHOD append(T value) RETURNS STATUS

BACK-SIDE OPERATIONS (right before ender sentinel) Insert value at the back. value is cloned in via LinkedListNode's INIT (const-ref param-passing, LOCKED 2026-05-12). O(n) — walks .head's owning chain to find the node whose .next is the ender (id 1), then splices newNode in front of the ender.

MODIFY METHOD appendCopy(REFERENCE T value) RETURNS STATUS

Deep-copy form of append. value stays valid for the caller; the clone is the one moved into the new node.

MODIFY METHOD popLast() RETURNS | T

Remove and return the back user value. EMPTY if empty. O(n) walk from .head to find the second-to-last user node so we can splice the ender into its .next slot. Single-element case short-circuits to popFirst().

Splice ordering (Bug #32 move-out-before-overwrite): step 1: popped := wasSecondToLast.next (move popped out of the predecessor's next slot) step 2: wasSecondToLast.next := popped.next (move ender into the predecessor's next slot)

METHOD peekLast() RETURNS | REFERENCE T

Read (without removing) the back user value. Pipe-XOR shape: SUCCESS populates value with the reference; empty list populates s with FAILURE. O(n) walk from .head.

MODIFY METHOD insertAt(int32 index, T value) RETURNS STATUS

MID-CHAIN OPERATIONS (insertAt / removeAt)

Used by SortedList[T] and any other consumer that needs to splice at an arbitrary position. O(index) walk to the target node, then O(1) splice via the same move-out-before-overwrite pattern as prepend/append/popFirst/popLast.

Index 0 and index .length (or .length - 1 for removeAt) delegate to the existing front/back methods to avoid duplicating splice logic. Insert value at position index. Valid range is 0..length (inclusive — index == length appends, equivalent to append). Per §10.2 the bare-named form consumes value (poisoned at the call site). STATUS == FAILURE on out-of-bounds index or kernel-invariant violation; SUCCESS otherwise.

MODIFY METHOD insertAtCopy(int32 index, REFERENCE T value) RETURNS STATUS

Deep-copy form of insertAt. value stays valid for the caller; the clone is the one moved into the new node.

MODIFY METHOD removeAt(int32 index) RETURNS | T

Remove and return the user value at position index. STATUS == FAILURE on out-of-bounds index or kernel-invariant violation (paired with EMPTY in the value slot); SUCCESS otherwise (paired with the removed value).

CLASS LinkedListIterator

IMPLEMENTS ReferenceIterator

Concrete BidirectionalIterator OF T for LinkedList[T].

A LinkedList[T]'s ->iterator() method yields a fresh LinkedListIterator[T] positioned at the first user node (or at the ender sentinel if the list is empty). Multiple iterators on the same list are independent (each has its own cursor REFERENCE); the source list is locked against mutation while any iterator is held (per §Iterator's mutation-lock rule).

────────────────────────────────────────────────────────────────── CURSOR MODEL ──────────────────────────────────────────────────────────────────

The cursor REFERENCEs the node "about to be read" by the next forward operation. Valid cursor positions:

The cursor never sits at the head sentinel (id = 0). Stepping backward stops at the first user node — going further would land at head (which has no readable value), so hasPrevious returns false there and previous/skipBack return EMPTY without moving.

For an empty list, the cursor starts at the ender; both hasNext and hasPrevious are false.

────────────────────────────────────────────────────────────────── SAFETY ──────────────────────────────────────────────────────────────────

────────────────────────────────────────────────────────────────── SKIP / SKIP-BACK BOUNDS ──────────────────────────────────────────────────────────────────

No local REFERENCE-typed variables are used (REFERENCE is restricted to class instance fields per Bug #29 V1; non-owning local handles use Bug #30's =@ operator instead). The cursor field is the walker.

kernel/src/LinkedListIterator.ev:75

Constructors

INIT(REFERENCE LinkedListNode[T] source_head_node)

Methods

METHOD hasNext() RETURNS boolean

MODIFY METHOD next() RETURNS | REFERENCE T

METHOD peek() RETURNS | REFERENCE T

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE T

skip(n) — moves cursor forward by n positions. skip(0) is equivalent to peek(). On overshoot, the cursor lands on the ender sentinel and FAILURE is returned.

CLASS OwnedList

IMPLEMENTS Collection

Owning, move-only, non-Cloneable list.

────────────────────────────────────────────────────────────────── WHAT IT IS ──────────────────────────────────────────────────────────────────

OwnedList[T] is a singly-linked list that OWNS its elements and only ever MOVES them — it never copies or clones. Because it is not itself Cloneable, it imposes no Cloneable requirement on T; its bound is T IS Shareable, so it can hold non-Cloneable kernel concurrency primitives (Channel, Mutex, Future, …) that the standard collections (Array / Dictionary / LinkedList / Set, all IMPLEMENTS Cloneable) reject.

It is the registry behind Broker[T] (a list of per-subscriber Channels), and is reusable for any "hold a set of owned, non-copyable objects, walk them, add/remove by id" need.

────────────────────────────────────────────────────────────────── API (minimal) ──────────────────────────────────────────────────────────────────

Structure mirrors LinkedList: a head sentinel (id 0) and an ender sentinel (id 1) bracket the user nodes (id ≥ 2). Splices use the move-out-before-overwrite ordering. Singly-linked, owning- forward; dropping .head cascade-frees the chain.

Built to back Broker[T].

kernel/src/OwnedList.ev:48

Fields

Constructors

INIT()

Methods

MODIFY METHOD add(T value) RETURNS uint64

Take ownership of value and prepend it (right after the head sentinel). O(1). Returns the new node's stable id, which the caller passes to removeById later.

Splice ordering (Bug #32 move-out-before-overwrite): step 1: newNode.next := .head.next (move old first into newNode.next) step 2: .head.next := newNode (move newNode into .head.next)

MODIFY METHOD removeById(uint64 id) RETURNS boolean

Remove the user node with the given id. Returns TRUE if found and removed; FALSE if no live node carries that id. Walks from the head sentinel tracking the predecessor, then splices the target out (its owned element is dropped as popped leaves scope).

METHOD findById(uint64 id) RETURNS | REFERENCE T

Return a REFERENCE to the element of the node with the given id. Pipe-XOR: SUCCESS yields the reference; FAILURE if no live node carries that id. Used by Broker.subscribe to hand a Subscription a non-owning handle to its just-added channel.

METHOD size() RETURNS int64

Countable — the count of user nodes (sentinels excluded). .length is the int32 field; size() is the int64 contract, and int32 -> int64 is a widening, so the assignment carries it with no stated conversion.

METHOD isEmpty() RETURNS boolean

METHOD iterator() RETURNS OwnedListIterator[T]

Fresh forward cursor positioned at the first user node (or the ender if empty). Pass .head by-& so the iterator's REFERENCE binding is mutation-locked at INIT without moving .head out.

CLASS OwnedListIterator

IMPLEMENTS ReferenceIterator

Forward cursor over OwnedList[T].

A fresh iterator from OwnedList.iterator() is positioned at the first user node (or the ender sentinel if the list is empty). Drive it with the pipe-XOR loop:

OwnedListIterator[T] it := list->iterator()
WHILE it->next() DO {
    REFERENCE T value =@ $RETURNED
    ... use value in place (no copy) ...
}

Mirrors LinkedListIterator (the proven cursor model), bound to T IS Shareable so it can walk a chain of non-Cloneable elements. next() yields a REFERENCE to the element — the consumer operates on it in place; the element is never copied out of the list.

Plain FINAL class (not IMPLEMENTS ReferenceIterator): OwnedList's consumers drive next() directly, and the for-in / ReferenceIterator protocol carries a Cloneable-shaped contract we don't want here.

kernel/src/OwnedListIterator.ev:33

Constructors

INIT(REFERENCE OwnedListNode[T] sourceHeadNode)

Methods

METHOD hasNext() RETURNS boolean

Iterator — TRUE while the cursor still sits on a user node. The ender sentinel is id 1, which is exactly the condition next() refuses on, so the two agree by construction.

This class implemented NO interface at all until now, which is why it alone of the iterators could not satisfy Collection.iterator() — ArrayIterator and the rest were already BidirectionalIterator OF T.

METHOD peek() RETURNS | REFERENCE T

ReferenceIterator — the reference at the current cursor WITHOUT advancing. Same pipe-XOR shape as next() and the same refusal at the ender sentinel; it simply does not move cursorRef.

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE T

ReferenceIterator — advance n positions and yield what lands under the cursor. skip(0) is next(); running off the ender fails exactly as next() does, so a short list refuses rather than walking past the sentinel.

MODIFY METHOD next() RETURNS | REFERENCE T

Advance and yield the next element by REFERENCE. Pipe-XOR: SUCCESS populates value; FAILURE once the cursor reaches the ender sentinel (end of iteration).

Dictionaries

INTERFACE Dictionary

Dictionary is a pure INTERFACE, not a concrete class, and is no longer special-cased by the compiler. It is an ordinary parametric interface the compiler treats like any other.

THREE TYPE PARAMETERS Dictionary[K, V, H]: - K — key type. Hashable + Equatable (primitives, String, or a class implementing both). - V — value type. Cloneable / primitive (the clone()-bearing surface requires it; see EXTENDS Cloneable below). - H — the Hasher OF K used to hash keys. Callers name a concrete hasher here (e.g. Dictionary[String, int32, StringHasher]); the hidden impls store it as the Hasher OF K interface type and, when constructed without one, CREATE a DefaultHasher[K].

IMPLEMENTATIONS (both HIDDEN, pure Envzn, no FOREIGN / std::): - ChainedHashDictionary[K,V,H] — bucket array + chaining; unordered. - SkipListDictionary[K,V,H] — skip list; sorted iteration (K also Comparable). (lands in a later #16 phase.)

Callers construct an impl and hold the interface: Dictionary[String, int32, StringHasher] scores := CREATE ChainedHashDictionaryString, int32, StringHasher

EXTENDS Cloneable — every Dictionary deep-copies.

ITERATION yields KEYS (forward-only), per spec §Iterator. Order is unspecified for the chained-hash impl; the skip-list impl iterates in sorted key order. Dictionary[K, V, H] — unordered key→value map interface. Keys are hashed by the H hasher; values are Cloneable. Construct a concrete impl (ChainedHashDictionary / SkipListDictionary) and hold this interface type.

kernel/src/Dictionary.ev:49

Methods

METHOD clone() RETURNS Dictionary[K, V, H]

Deep copy. (Cloneable contract; covariant return — an impl returns its own concrete type.)

METHOD iterator() RETURNS ReferenceIterator[K]

Forward-only iterator over the keys. FOR/IN over a Dictionary visits each key once.

METHOD keys() RETURNS LinkedList[K]

Snapshot of all keys in a fresh LinkedList (each key cloned).

METHOD isEmpty() RETURNS boolean

check if the dictionary is empty

METHOD size() RETURNS int64

Number of key→value pairs currently stored. All three impls already provide it; declaring it here makes it callable through a Dictionary interface handle (Bug #179).

MODIFY METHOD clear() RETURNS void

MODIFY METHOD insert(K key, V value) RETURNS STATUS

insert (key, value). BOTH are MOVEd in (consumed) — the dictionary owns what it stores, so there is nothing for it to clone. Replacing an existing key destroys the old value and leaves the count unchanged. SUCCESS always (FAILURE only on an EMPTY key/value where the type is Cloneable). Use insertCopy to keep your own key and value.

MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUS

Deep-copy insert — both key and value stay valid for the caller.

METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE V

Lookup — a reference into the stored value, or FAILURE if the key is absent. Gate on STATUS, not on the returned V. A borrow-propagating ("mirror") accessor: the returned reference mirrors the receiver's mutability — a mutable dictionary yields a MUTABLE REFERENCE (modify the value in place), a const one a read-only REFERENCE. Valid while the dictionary is not mutated (iterator mutation lock).

There is deliberately NO value-cloning lookup: borrowing is the default and owning is explicit. To own a copy, clone the borrow; to own the value itself, remove it.

METHOD lookupFast(REFERENCE K key) RETURNS boolean

Allocation-free lookup — found plus the value, no pipe and no STATUS.

This is not a faster lookup; it is a lookup with a different COST on the miss. lookup builds a FAILURE("...key not found") when the key is absent, so a loop that misses once per distinct key — a group-by, a join, a dedupe — allocates a formatted String per miss, a cost the pipe hides completely at the call site. Every implementation already knows whether the key is present before it decides what to return, so making this part of the interface costs nothing and is what lets a consumer stay on the interface instead of reaching for the concrete class.

On a miss value is the type's absent form (EMPTY for a class V, zero for a primitive) and MUST NOT be read: found is the only valid discriminator. C# spells the same contract TryGetValue.

MODIFY METHOD remove(REFERENCE K key) RETURNS | K

remove — MOVES both halves out, or FAILURE if the key is absent. Nothing is cloned: the stored key and value are handed to the caller rather than copied and destroyed. The returned key is the STORED one, which is equal to — but not necessarily the same object as — the probe key, which is why it is worth returning.

METHOD contains(REFERENCE K key) RETURNS boolean

contains - like lookup() but only returns a boolean if the key-value pair is found

CLASS ChainedHashDictionary

IMPLEMENTS Dictionary

ChainedHashDictionary STORAGE: - buckets : HashBucket[K,V][] — a RAW value-array of lean value-class buckets, one per slot. Each HashBucket stores its entries INLINE (2 CollisionNode slots + a lazy spill), so there is NO per-bucket heap object and NO per-entry heap node — the LinkedList-per-bucket + ChainedHashEntry + per-lookup heap iterator of the old design are gone (that iterator alloc was the measured 174 ns/lookup S4 bug). An empty bucket is a zero-count HashBucket (no nullable-slot problem). - In-place bucket mutation binds a MUTABLE REFERENCE into .buckets[idx] (reads bind a plain REFERENCE); the bucket's own MODIFY methods do the work. - count : int64; hasher : Hasher OF K (interface-typed, decision 5); bucketLevel : int64 (power-of-two growth level); growth : GrowthHint (advisory, stored-unused for V1).

BUCKET INDEX: hash & (bucketCount - 1) over a POWER-OF-TWO bucket count (HashConstants.pow2CountAtLevel / indexForHash) — replaces the old prime %. RESIZE: load factor > 0.79 (count100 > bucketCount79) → double the bucket count (one pow2 level) and rehash every entry by its CACHED hash (no key re-hash).

IMPLEMENTS Dictionary[K, V, H] — Cloneable comes transitively (Dictionary EXTENDS Cloneable); a redundant explicit Cloneable would create an ambiguous C++ double base and break clone() covariance. H is phantom in the body; the stored hasher is the Hasher OF K interface (no-arg INIT CREATEs the DefaultHasher). ChainedHashDictionary[K, V, H] — separate-chaining hash table over lean inline value-class buckets. HIDDEN: constructed via CREATE, held through the Dictionary interface.

kernel/src/ChainedHashDictionary.ev:45

Constructors

INIT()

No hasher, default sizing — CREATE a DefaultHasher[K].

INIT(Hasher[K] h)

Caller-supplied hasher, default sizing.

INIT(GrowthHint hint, int64 initialCapacity)

Default hasher + sizing hints (initialCapacity ignored for V1 — the pow2 ladder governs bucket count; GrowthHint stored, unused).

INIT(Hasher[K] h, GrowthHint hint, int64 initialCapacity)

Caller hasher + sizing hints.

Methods

METHOD clone() RETURNS Dictionary[K, V, H]

METHOD iterator() RETURNS ReferenceIterator[K]

METHOD keys() RETURNS LinkedList[K]

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

Number of key-value pairs currently stored. Read-only, O(1).

MODIFY METHOD clear() RETURNS void

MODIFY METHOD insert(K key, V value) RETURNS STATUS

MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUS

METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE V

METHOD lookupFast(REFERENCE K key) RETURNS boolean

Dictionary.lookupFast — same probe as lookup, without the STATUS that lookup must allocate on a miss.

MODIFY METHOD remove(REFERENCE K key) RETURNS | K

METHOD contains(REFERENCE K key) RETURNS boolean

METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS boolean

Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.

Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so two "equal" dictionaries would answer lookup(a) differently and neither could stand in for the other — which is the whole point of an equivalence. Keys-AND-values is what C++ (map and unordered_map), Rust, Swift, Julia, Python and Java all specify. Keyset equality is a perfectly good relation, but it is equality of the DOMAIN rather than of the dictionary, and it deserves its own name (hasSameKeys) rather than this one.

Equal sizes plus a one-way walk is sufficient: with the counts already equal, other cannot carry a key this one lacks unless this one also carries a key other lacks — and the walk would have found that.

CLASS HashBucket

IMPLEMENTS Cloneable, Comparable>, Equatable>

PARAMETERISED OVER HASH: uint64 for ChainedHashDictionary (FNV), uint128 for ProHashDictionary (SipHash-2-4-128). Every scan rejects on the cached HASH before the key compare (CollisionNode.matches). Equal cached hashes form a contiguous run the scans walk for the key match.

The lookup returns a TRIVIAL (boolean found, V value) multi-return — NOT a (V|STATUS) pipe-XOR — so the hot path never constructs an _EvStatus (whose _ValueArray member is non-trivially destructible). The dictionary builds the interface-mandated (V|STATUS) once at its public boundary.

A method may not be chained off an indexed SELF field (.data[i]->m() is a parse error), so an element is bound to a local reference before the call; counted iteration uses WHILE.

See: CollisionNode.ev, HashConstants.ev, ChainedHashDictionary.ev / ProHashDictionary.ev, ENVZN_CONSTITUTION.md §I.J.vi (VALUE CLASS). HashBucket[K, V, HASH] — one sorted array of CollisionNodes (2 inline).

kernel/src/HashBucket.ev:35

Constructors

INIT()

Methods

METHOD size() RETURNS int64

Number of entries in this bucket.

MODIFY METHOD insert(K key, V value, HASH hash) RETURNS boolean

Insert key→value (with cached hash). TRUE if a new entry was added, FALSE if an existing key's value was replaced in place.

METHOD lookup(HASH hash, REFERENCE K key) RETURNS boolean

Look up key (with cached hash) — TRIVIAL (found, value) multi-return, so the hot path never builds an _EvStatus. value is the type default on a miss.

HYBRID (measured crossover at depth ~24, 2026-06-25): the common shallow bucket (≤ LINEAR_SCAN_MAX entries) is a plain linear scan from 0 — no lowerBound binary search, and one matches() per node (no redundant outer hash pre-check). Only a deep/flooded bucket (> LINEAR_SCAN_MAX) pays the O(log n) sorted path. The sorted invariant is kept by insert, so the deep path stays valid.

METHOD lookupRef(HASH hash, REFERENCE K key) RETURNS | MUTABLE REFERENCE V

Look up key — a non-owning reference into the stored value, or FAILURE. A borrow-propagating ("mirror") accessor: the returned reference mirrors the receiver's mutability (a mutable bucket yields a MUTABLE REFERENCE, a const bucket a read-only REFERENCE). Binds directly to the matched node's INTERNAL value field.

METHOD containsKey(HASH hash, REFERENCE K key) RETURNS boolean

TRUE if key is present.

METHOD keyCloneAt(int64 i) RETURNS K

A clone of the i-th node's key.

METHOD valueCloneAt(int64 i) RETURNS V

A clone of the i-th node's value.

METHOD hashAt(int64 i) RETURNS HASH

The cached hash of the i-th node — backs growAndRehash re-bucketing.

MODIFY METHOD removeEntry(HASH hash, REFERENCE K key) RETURNS | K

Remove key — returns the cloned-out key, or FAILURE. Shift-removes from the sorted live region (the tail slides left, count--; the physical array is not shrunk — the freed tail slot is reused by the next insert). Evict the entry for key and hand BOTH halves back, moved — never cloned. Replaces the former removeKey, which was written as read-then-delete (keyCloneAt(pos) followed by the shift) and so deep-copied the very key it was about to destroy — the Array.popLast defect shape fixed in 3003ed5f, in its dictionary form.

The survivors still shift down and data's physical length is left alone: it is a non-shrinking high-water mark and the vacated tail slot is reused by the next insert (see the header note).

MODIFY METHOD placeNew(K key, V value, HASH hash) RETURNS void

Build a node from (key, value, hash) and sorted shift-insert it. No update scan; the caller guarantees the key is new (rehash re-place / known-fresh).

METHOD clone() RETURNS HashBucket[K, V, HASH]

Deep copy — every live node cloned, in sorted order (so the clone stays sorted).

METHOD equals(REFERENCE HashBucket[K, V, HASH] other) RETURNS boolean

METHOD isLessThan(REFERENCE HashBucket[K, V, HASH] other) RETURNS boolean

CLASS HashBucketIterator

IMPLEMENTS ReferenceIterator

HashBucketIterator walks the dictionary's HashBucket[K,V,HASH][] buckets (a raw value-array of inline buckets) in bucket order, yielding a non-owning REFERENCE to each entry's key. Holds a mutation-locked REFERENCE to the buckets array (set in INIT from a by-reference parameter — §REFERENCE condition 2); the lock pins the source dictionary against mutation for the iterator's declaring-block lifetime.

CURSOR MODEL: (bi, ei) is the NEXT position to read — bucket bi, entry ei within that bucket (0→slot0, 1→slot1, k≥2→spill[k-2]). advanceToValid() normalises the pair so it either names a live entry (bi < nbuckets, ei < bucket.size()) or sits at end (bi >= nbuckets). hasNext is bi < nbuckets. Iteration order is unspecified (bucket order, and within a bucket the 2 slots then the hash-sorted spill) — the Dictionary interface promises no order for the hash impls.

The per-entry key is reached by binding directly to the bucket's / node's INTERNAL fields (same ENVZN module) — =@ node.key — rather than via a value-class accessor method, whose inlining into a =@ bind would drop the reference and copy the move-only key (the long-standing key-bind gotcha). The bucket count is read through size().

Parameterised over [K, V, HASH] — the dictionary's hasher type is not needed here (the iterator never hashes), so it is left off the iterator's contract; HASH is carried only to name the bucket/node types. HashBucketIterator[K, V, HASH] — forward-only key iterator over a bucket array.

kernel/src/HashBucketIterator.ev:43

Constructors

INIT(REFERENCE HashBucket[K, V, HASH][] buckets)

Methods

METHOD hasNext() RETURNS boolean

MODIFY METHOD next() RETURNS | REFERENCE K

METHOD peek() RETURNS | REFERENCE K

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE K

CLASS CollisionNode

IMPLEMENTS Cloneable, Comparable>, Equatable>

CollisionNode.ev — one (key, value, cachedHash) cell, as a VALUE CLASS so the hash bucket stores it INLINE (no per-entry heap node). This is the Phase-1 dict- rebuild substrate replacing the heap-allocated ChainedHashEntry: a HashBucket holds CollisionNodes by value (two inline slots + a contiguous spill), and an Array[CollisionNode[K,V]] lowers to inline storage — _ValueArray when K,V are primitive (the trivially-copyable C-class path), _ObjectArray-by-value when K is a class (e.g. a String key → owning handle field, the managed value-class form the compiler deep-copies).

The key's hash is cached at insert (idea from libdict): a resize re-buckets via the cached hash without re-hashing keys, and a lookup rejects on the uint64 hash before the (possibly expensive) key compare.

K IS (Hashable AND Equatable); V is Cloneable / primitive. IMPLEMENTS Cloneable so a node can be an Array[CollisionNode] element (whose clone() the bucket needs).

See: HashBucket.ev (the holder), ChainedHashDictionary.ev (the consumer), ENVZN_CONSTITUTION.md §I.J.vi (VALUE CLASS). (Replaces the old heap-class ChainedHashEntry, removed in the Phase-2 dict rebuild.) CollisionNode[K, V, HASH] — a (key, value, cachedHash) bucket cell, value-typed. HASH is the cached-hash width: uint64 for ChainedHashDictionary (FNV), uint128 for ProHashDictionary (SipHash-2-4-128). Parameterising the width keeps the common int-key node tight (16 B at uint64 — 4 nodes/cache line) while letting the Pro table keep its full 128-bit digest for the cheap pre-compare reject.

kernel/src/CollisionNode.ev:41

Constructors

INIT(K k, V v, HASH h)

Methods

METHOD hashValue() RETURNS HASH

The cached hash of this node's key (used by resize re-bucketing and the pre-compare reject in lookup).

METHOD matches(HASH h, REFERENCE K other) RETURNS boolean

TRUE if this node matches both the query hash and the query key. The cached HASH is checked first (cheap reject); only on a hash hit is identity confirmed via Equatable (class keys) or == (primitive keys) — the design doc's "compare hash first, confirm key" step. Backs every lookup/insert/remove scan.

MODIFY METHOD setValue(V v) RETURNS void

Replace the stored value in place — backs insert-over-existing-key (the key and cached hash are unchanged).

METHOD valueClone() RETURNS V

A clone of the stored value — backs by-value lookup.

METHOD keyClone() RETURNS K

A clone of the stored key — backs keys().

MODIFY METHOD takeKey() RETURNS K

move the stored key out — backs remove(). The node is being evicted, so the key is handed to the caller rather than copied and destroyed ("move in => move out"). Reading .key afterward is a use-after-move; the only caller evicts the node in the same operation.

MODIFY METHOD takeValue() RETURNS V

move the stored value out — the twin of takeKey, same contract.

METHOD clone() RETURNS CollisionNode[K, V, HASH]

Deep copy — key and value cloned, cached hash carried across.

METHOD equals(REFERENCE CollisionNode[K, V, HASH] other) RETURNS boolean

METHOD isLessThan(REFERENCE CollisionNode[K, V, HASH] other) RETURNS boolean

CLASS IntKeyedDictionary

IMPLEMENTS Dictionary

HIDDEN concrete Dictionary impl specialised for INTEGER keys: linear-probe open-addressing over a STRUCT-OF-ARRAYS (K[] keys + V[] vals), with a hash & mask home index. The TRUSTED-KEY FAST TIER. Pure Envzn, zero-dep.

WHY it is fast (the s04 envzn_oa prototype — ~1.1x C for int32->int64, the fastest s04 result; verified by benchmarks/s04_dict/envzn_intkeyed): - STRUCT-OF-ARRAYS, not chained buckets: one flat array level, so the hot probe is a direct keys[s] read (C's own layout) — no bucket->node indirection, no per-node binary search, no redundant hash+key re-compare. - hash & mask index (the LOW bits): with an identity hasher on dense/sequential integer keys this maps sequential keys to SEQUENTIAL slots — cache-line locality + prefetch, the effect that made envzn_oa (1.04x C) beat multiply-shift's scatter (envzn_lpint, 1.38x). Distribution is the pluggable HASHER's job: identity for trusted/dense keys (fastest), a mixing hasher (DefaultHasher/ SipHasher) for adversarial keys. The key-set-aware multiply-shift + prime fallback for the robust general case lives in ShallowDictionary, NOT here. - A non-pipe-XOR fast read: operator[] (d[key]) and lookupFast return by value / (found,value), skipping the (V | STATUS) tuple the interface lookup builds per call — the s04 IntDict lever ("no pipe-XOR on the hot path"). Held CONCRETELY (not behind the Dictionary interface) the whole lookup inlines to C-class code (~1.1x C vs ~3x through the interface + pipe-XOR). - ONE compare per probe: keys[s] == key (a primitive ==), then a field read of vals[s]. No cached-hash pre-check (integer keys are their own cheap hash).

STORAGE — two parallel value-arrays. Empty/tombstone slots are marked in keys[] by two RESERVED sentinel key values: -1 = EMPTY (probe stops) -2 = TOMBSTONE (probe continues; slot reusable) vals[] in a non-live slot holds 0 and is never read. This mirrors LpInt's -1 sentinel, extended with a tombstone so the full Dictionary remove surface works.

KEY DOMAIN (documented precondition): keys must not equal the two reserved sentinels (-1, -2). In practice IntKeyedDictionary is for NON-NEGATIVE / trusted integer keys — the fast opt-in tier (as FastIntHasher is the fast opt-in hasher). Full-range or untrusted keys → ChainedHashDictionary. A dev-build ASSERT guards the precondition.

HASHER — stored CONCRETELY as the type parameter H hasher (a VALUE-CLASS hasher such as InlineIntHasher lives inline, no _ev_unique handle), so .hasher->hash(key) can inline. (Measured: the hasher is a minor factor — the dominant lever is the shape, i.e. concrete-hold + non-pipe-XOR read, not the hash call.) Because a type parameter cannot be default-constructed generically (CREATE H() mis-codegens — envzn-internals defect), the hasher is REQUIRED at construction: CREATE IntKeyedDictionary[K,V,H](CREATE InlineIntHasher[K]()) — the caller-passes-the-hasher pattern ChainedHashDictionary uses.

IMPLEMENTS Dictionary[K, V, H] — Cloneable comes transitively (Dictionary EXTENDS Cloneable). Full interface surface (rehash / tombstones / iterator / clone) PLUS the concrete fast path (operator[] / lookupFast) for callers holding the concrete type.

kernel/src/IntKeyedDictionary.ev:62

Fields

Constructors

INIT(H h)

Methods

MODIFY METHOD insert(K key, V value) RETURNS STATUS

MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUS

METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE V

METHOD __op_index__(REFERENCE K key) RETURNS V

Direct value read — d[key]. Returns the stored value on a hit, or the V default (0) on a miss. NO pipe-XOR (V | STATUS) tuple on the hot path: the s04 experiments (IntDict) showed the pipe-XOR construction is a real per-lookup cost, and operator[] returns V by value like ByteBuffer/String subscript. Use contains/lookup when a miss must be distinguished from a stored 0.

METHOD lookupFast(REFERENCE K key) RETURNS boolean

Comma-return lookup — boolean f, V v := d->lookupFast(key). No pipe-XOR (V | STATUS) tuple; the trivial (found, value) return the s04 prototypes (IntDict/OADict) used to stay C-class. found distinguishes a miss from a stored default.

METHOD contains(REFERENCE K key) RETURNS boolean

MODIFY METHOD remove(REFERENCE K key) RETURNS | K

Remove — hands back the stored key and value.

NOTE: unlike ChainedHashDictionary, this cannot move the halves out. The storage is a struct-of-arrays open-addressed table, and reading a slot (.vals[s]) is a subscript READ, which by rule clones rather than moves (cxx_emit stmt_assign.py:149 — "the subscript is a read accessor, never a move-out"). HashBucket escapes this because it can evict a whole CollisionNode and take its fields; an SoA table has no move-out-at-index primitive to call. So this pays one DUPLICATE per half, and the census pins it at that rather than at 0. K is an integer here, so the key half is a bit copy; only a class-typed V costs a real clone.

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

MODIFY METHOD clear() RETURNS void

METHOD iterator() RETURNS ReferenceIterator[K]

METHOD keys() RETURNS LinkedList[K]

METHOD clone() RETURNS Dictionary[K, V, H]

METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS boolean

for Equatable Interface Dictionary is equal if all keys between the two dictionaries are equal Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.

Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so two "equal" dictionaries would answer lookup(a) differently and neither could stand in for the other — which is the whole point of an equivalence. Keys-AND-values is what C++ (map and unordered_map), Rust, Swift, Julia, Python and Java all specify. Keyset equality is a perfectly good relation, but it is equality of the DOMAIN rather than of the dictionary, and it deserves its own name (hasSameKeys) rather than this one.

Equal sizes plus a one-way walk is sufficient: with the counts already equal, other cannot carry a key this one lacks unless this one also carries a key other lacks — and the walk would have found that.

CLASS IntKeyedDictionaryIterator

IMPLEMENTS ReferenceIterator

The ReferenceIterator OF K returned by IntKeyedDictionary.iterator(). Walks the struct-of-arrays K[] keys, yielding a REFERENCE K per live slot (a slot whose key is neither the EMPTY sentinel -1 nor the TOMBSTONE sentinel -2).

Holds a mutation-locking REFERENCE to the dictionary's keys value-array (bound with =@ in INIT); the lock pins the source dictionary against mutation for the iterator's declaring-block lifetime. Cursor pos is the next slot to examine; advanceToValid() skips empty (-1) and tombstone (-2) slots.

Parameterised over [K, V] to match the dictionary's arity (the vals array is not walked and V is otherwise unused, but keeping the pair mirrors ShallowDictionaryIterator and leaves room for a key+value iterator later). The hasher H is not needed — the iterator never hashes.

kernel/src/IntKeyedDictionaryIterator.ev:29

Constructors

INIT(REFERENCE K[] keyArr, int64 capacity)

Methods

METHOD hasNext() RETURNS boolean

MODIFY METHOD next() RETURNS | REFERENCE K

METHOD peek() RETURNS | REFERENCE K

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE K

CLASS ProHashDictionary

IMPLEMENTS Dictionary

The DoS-RESISTANT dictionary, rebuilt (2026-07-13) on the byte-keyed substrate that made StringKeyedDictionary beat C. Pure Envzn, zero-dep beyond the SipHash key shim.

WHY THE REBUILD (the measurement that forced it): The old ProHash — Dictionary[BinaryWord,V,H] over char32 String keys, interface dispatch, pipe-XOR returns, heap-node chains — ran the s05 word-dict at 1505 ms, 32x C. The s05 experiment envzn_strkeyed_sip then ran the SAME SipHash-2-4 over the byte-keyed open-addressing substrate at 49 ms — a 30x speedup at IDENTICAL DoS-resistance. So ProHash's cost was never SipHash; it was the SHAPE. This class keeps everything that made it "Pro" and rebuilds the shape underneath it.

WHAT MAKES IT "PRO" (both properties retained): 1. SipHash-2-4 keying. A process-global 16-byte secret (OS entropy, the same FOREIGN key shim SipHasher uses), so an attacker cannot predict bucket distribution — hash-flooding DoS defence by construction. 2. ADAPTIVE deep tier: chain -> RED-BLACK TREE. A bucket starts as a linear CHAIN (optimal when shallow — the overwhelmingly common case). If a bucket's depth exceeds TREEIFY_THRESHOLD (8) it is TREEIFIED into a red-black tree ordered by (cached hash, then key bytes) — a total order — so even a bucket an attacker somehow manages to overfill degrades to O(log n), never O(n). This is the belt-and-suspenders behind the SipHash keying: SipHash makes deep buckets unforceable; the tree bounds the damage if one ever occurs anyway.

THE SPEED LEVERS (carried over from StringKeyedDictionary): - char8[] BYTE keys, not String. String stores char32 code points and hashes / compares them one handle-indirected, bounds-checked element at a time — that was the dominant cost. The caller transcodes ONCE (s INTO ByteBuffer -> bytes). (Byte keys also mean this cannot be a Dictionary[BinaryWord,V,H] impl: the interface cannot fix a type parameter (E2103) and an array key is not PRIMITIVE. It is a standalone CLASS, as StringKeyedDictionary is.) - System->memoryWord absorbs the SipHash message 8 BYTES PER ROUND (one wide load) instead of eight bounds-checked byte reads. - HOTLOOP hoists the per-byte bounds check out of the tail/compare loops. - System->memoryCompare confirms a key with one std::memcmp, not a per-byte loop. - No pipe-XOR on the hot path: lookupFast returns a trivial (found, value) and operator[] returns V by value — neither builds the (V | STATUS) tuple. The pipe-XOR lookup remains for the kernel idiom, off the hot path.

STORAGE — a flat byte pool + a flat ENTRY ARENA (SoA), no per-entry heap node: - keyPool : char8[] — every key's bytes, contiguous. - per-bucket: bucketList (the member CHAIN head — kept intact in BOTH modes, so enumeration is always a chain walk), bucketRoot (the red-black index root when treeified; -1 otherwise), bucketMode (0 chain / 1 tree), bucketDepth. The tree is an ADDITIONAL lookup index over the same entries, never the sole structure — that is what keeps rehash/remove/clone simple. - per-entry: entHash, entOff/entLen (slice into keyPool), entVal, entNext (chain link, doubles as the free-list link), entLeft/entRight/ entParent/entRed (red-black links, tree mode), entLive. Freed entries are recycled through freeHead.

REMOVE — a deliberate, bounded simplification (labelled, not hidden): removing from a TREEIFIED bucket does not run the CLRS red-black delete-fixup. It collects the bucket's live entries, drops the target, and REBUILDS the bucket (re-chained if the remaining depth <= UNTREEIFY_THRESHOLD, else re-treeified). That is O(depth) — bounded, correct, and it keeps ~150 lines of the most bug-prone code in a red-black tree out of the kernel. Lookup and insert — the hot paths — use the real red-black tree.

kernel/src/ProHashDictionary.ev:78

Constructors

INIT()

Methods

MODIFY METHOD insertSlice(REFERENCE binary[] buf, int64 off, int64 len, V value) RETURNS STATUS

METHOD lookupFastSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean

Comma-return lookup — no pipe-XOR (V | STATUS) tuple on the hot path.

METHOD containsSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean

MODIFY METHOD removeSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean

Remove. Unlinks the entry from the bucket's member chain, then RE-INDEXES the bucket: a treeified bucket that has fallen to the untreeify threshold drops its red-black index and reverts to a plain chain (hysteresis: treeify at >8, untreeify at <=6, so churn around the boundary cannot thrash); one still above it rebuilds the index. Rebuilding rather than running the CLRS red-black delete-fixup is a deliberate, bounded simplification (O(depth)) — labelled, not hidden. It keeps the single most bug-prone routine in a red-black tree out of the kernel, and remove is not the hot path; lookup and insert use the real tree.

MODIFY METHOD insert(REFERENCE binary[] key, V value) RETURNS STATUS

METHOD lookupFast(REFERENCE binary[] key) RETURNS boolean

METHOD __op_index__(REFERENCE binary[] key) RETURNS V

Direct value read — d[key]. V default (0) on a miss. No pipe-XOR.

METHOD lookup(REFERENCE binary[] key) RETURNS | V

Pipe-XOR lookup — the kernel idiom, kept OFF the hot path.

METHOD lookupRef(REFERENCE binary[] key) RETURNS | MUTABLE REFERENCE V

METHOD contains(REFERENCE binary[] key) RETURNS boolean

MODIFY METHOD remove(REFERENCE binary[] key) RETURNS boolean

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

MODIFY METHOD clear() RETURNS void

METHOD bucketIndexOf(REFERENCE binary[] key) RETURNS int64

The bucket a key currently maps to.

Exposed for TESTABILITY of the adaptive tier. SipHash keying means an attacker cannot force colliding keys — which also means a TEST cannot, so the chain->tree escalation would otherwise be unreachable, untested kernel code. This lets a test group keys that share a bucket and drive the escalation deterministically.

It does NOT weaken the DoS guarantee: hash-flooding's threat model is "the attacker supplies KEYS (data) that the victim hashes", not "the attacker calls methods on the victim's dictionary". Anyone able to invoke this already has code execution in-process, at which point the hash is not the weak link. Do not, however, echo the result across a trust boundary — that WOULD hand out a collision oracle.

METHOD maxBucketDepth() RETURNS int64

Deepest bucket in the table — the clustering metric the adaptive tier bounds.

METHOD treeifiedBuckets() RETURNS int64

How many buckets have escalated to a red-black tree. Zero under normal load — non-zero means collisions got deep (the adaptive tier is doing its job). Exposed so the escalation is TESTABLE and observable, not a silent internal.

METHOD iterator() RETURNS ReferenceIterator[BinaryWord]

One BinaryWord per live entry, borrowed from this dictionary's key pool. Valid only while the dictionary is unmodified: an insert may grow the pool and a rehash may move it.

METHOD keys() RETURNS LinkedList[BinaryWord]

MODIFY METHOD insertCopy(REFERENCE BinaryWord key, REFERENCE V value) RETURNS STATUS

MODIFY METHOD insert(BinaryWord key, V value) RETURNS STATUS

METHOD lookupFast(REFERENCE BinaryWord key) RETURNS boolean

Dictionary.lookupFast — the interface-shaped (BinaryWord-keyed) peer of the binary[] slice form above. K is BinaryWord for this class, so this is the overload that satisfies the interface; the slice form stays for the zero-copy call sites that already hold a buffer and a range.

METHOD lookup(REFERENCE BinaryWord key) RETURNS | MUTABLE REFERENCE V

METHOD contains(REFERENCE BinaryWord key) RETURNS boolean

MODIFY METHOD remove(REFERENCE BinaryWord key) RETURNS | BinaryWord

The removed key is a word over this dictionary's own pool. A freed entry is recycled through freeHead but its BYTES stay in the pool, so the returned word reads correctly until the pool is next compacted.

METHOD equals(REFERENCE Dictionary[BinaryWord, V, H] other) RETURNS boolean

Equal when both hold the same keys mapped to the same values. Walks the smaller surface — this dictionary's entries — and asks the other by lookup, so the cost is one hash per key rather than a cross product. Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.

Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so two "equal" dictionaries would answer lookup(a) differently and neither could stand in for the other — which is the whole point of an equivalence. Keys-AND-values is what C++ (map and unordered_map), Rust, Swift, Julia, Python and Java all specify. Keyset equality is a perfectly good relation, but it is equality of the DOMAIN rather than of the dictionary, and it deserves its own name (hasSameKeys) rather than this one.

Equal sizes plus a one-way walk is sufficient: with the counts already equal, other cannot carry a key this one lacks unless this one also carries a key other lacks — and the walk would have found that.

METHOD clone() RETURNS Dictionary[BinaryWord, V, H]

Deep copy. Returns the Dictionary INTERFACE, not the concrete class — the class is HIDDEN, so its name may appear only as a CREATE target. The copy goes in through the interface's own insert, since insertSlice is this class's and not the interface's.

CLASS ProHashDictionaryIterator

IMPLEMENTS ReferenceIterator

Walks the ENTRY ARENA, yielding one BinaryWord per live entry.

WHY THE ARENA AND NOT THE BUCKETS. ProHash stores entries in flat parallel arrays and threads them into buckets — a chain when shallow, a red-black tree once a bucket passes the treeify threshold. Walking the buckets would mean two traversal shapes and a recursion for the tree tier; walking the arena is one linear pass that is correct for both, and it touches each array in order rather than chasing indices. Iteration order is arena order, which is neither insertion nor hash order — a dictionary promises no order, and this one says so rather than implying one it would have to keep.

Freed entries are recycled through freeHead, so a dead slot may sit anywhere in the arena; entLive is the only thing that decides.

Like its StringKeyed sibling, the window is one VALUE field re-assigned per step — no allocation per key.

kernel/src/ProHashDictionaryIterator.ev:32

Constructors

INIT(REFERENCE binary[] pool, REFERENCE int64[] offs, REFERENCE int64[] lens, REFERENCE int8[] live, int64 arenaSize)

Methods

METHOD hasNext() RETURNS boolean

MODIFY METHOD next() RETURNS | REFERENCE BinaryWord

METHOD peek() RETURNS | REFERENCE BinaryWord

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE BinaryWord

CLASS RedBlackTreeDictionary

IMPLEMENTS Dictionary

An ORDERED Dictionary[K, V, H] backed by a left-leaning red-black tree (Sedgewick LLRB), ARENA form. Guaranteed O(log n) lookup / insert / remove; iteration yields keys in Comparable order.

── Phase-4 arena rewrite (2026-06-24) ──────────────────────────────────────── Nodes live inline in ONE RBNode[K, V][] arena value-array; child links are int64 arena indices (-1 = null), not owning handles. The owning-handle design's per-node heap allocation (one _ev_unique<RBNode> per key) collapses to a single growable array. rootIdx is a plain int64 (no RBRoot holder — index assignment can't trip the move-out/EMPTY-consume rules that forced the holder). A free-list (freeHead, threaded through a dead slot's left) reclaims slots on delete. The iterator walks an explicit index stack (O(n) total), retiring the subSize/nthKeyRef rank machinery.

THE ARENA DISCIPLINE (load-bearing — proved by kernel_probe/rbArenaProbe): appending a node (alloc) can REALLOCATE the arena and dangle any live reference into it. So: indices are stable, references are NOT. Every node access is wrapped in a tiny index-helper (leftOf, setLeftAt, …) that binds a fresh =@ .arena[i], touches the node, and drops the ref before returning — so no reference is ever held across an alloc()/insertNode() that might grow the arena. Insert allocs exactly one leaf at the bottom of the recursion; delete never allocs (only frees), so the delete path is realloc-free.

(The helpers also sidestep a parser limitation: a bare { … } block whose first statement declares a comma-bearing type — REFERENCE RBNode[K, V] n — is misparsed as a set literal. Encapsulating each bind in a method avoids the bare block entirely and reads better.)

K must additionally be Comparable (the tree orders by key). The hasher type H is part of the Dictionary interface but UNUSED here — an ordered tree compares keys, it does not hash — so no hasher is ever constructed (H bound satisfied vacuously). Comparison goes through the WHEN K IMPLEMENTS Comparable[K] split (the SortedList idiom): the compiler lowers built-in Comparable (primitives, String) under that guard; a bare a->isLessThan(b) emits a literal method clang rejects for primitives.

kernel/src/RedBlackTreeDictionary.ev:52

Fields

Constructors

INIT()

INIT(Hasher[K] h)

INIT(GrowthHint hint, int64 initialCapacity)

INIT(Hasher[K] h, GrowthHint hint, int64 initialCapacity)

Methods

MODIFY METHOD insert(K key, V value) RETURNS STATUS

MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUS

METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE V

METHOD lookupFast(REFERENCE K key) RETURNS boolean

Dictionary.lookupFast — the same descent as lookup, without the STATUS that lookup must allocate on a miss.

MODIFY METHOD remove(REFERENCE K key) RETURNS | K

Remove — hands back the STORED key and value (not the probe key, which is what the old key-only remove returned).

Like the SoA dictionaries and unlike ChainedHashDictionary, the halves are cloned rather than moved: the arena node is reached by index and a subscript read clones by rule (stmt_assign.py:149), and the LLRB delete rebalances the tree, so the node cannot simply be evicted first. Census pins this at one DUPLICATE per half.

METHOD contains(REFERENCE K key) RETURNS boolean

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

Number of key-value pairs currently stored. Read-only, O(1).

MODIFY METHOD clear() RETURNS void

METHOD keys() RETURNS LinkedList[K]

METHOD iterator() RETURNS ReferenceIterator[K]

METHOD clone() RETURNS Dictionary[K, V, H]

METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS boolean

for Equatable Interface Dictionary is equal if all keys between the two dictionaries are equal Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.

Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so two "equal" dictionaries would answer lookup(a) differently and neither could stand in for the other — which is the whole point of an equivalence. Keys-AND-values is what C++ (map and unordered_map), Rust, Swift, Julia, Python and Java all specify. Keyset equality is a perfectly good relation, but it is equality of the DOMAIN rather than of the dictionary, and it deserves its own name (hasSameKeys) rather than this one.

Equal sizes plus a one-way walk is sufficient: with the counts already equal, other cannot carry a key this one lacks unless this one also carries a key other lacks — and the walk would have found that.

CLASS RedBlackTreeDictionaryIterator

IMPLEMENTS ReferenceIterator

Forward, in-order key iterator for RedBlackTreeDictionary (ARENA form). Yields keys in Comparable order (the tree's natural order), each as a non-owning REFERENCE into the live arena.

This holds an explicit index stack of the un-visited left spine and advances ONE step per next(): pop the top (the next in-order node), then push the left spine of its right child. O(n) total, O(h) space.

Per the iterator rules it holds NEITHER an iterator-typed field (Rule A / E1112) NOR an owning class field (Rule B / E1113); a mutation-locked REFERENCE to the arena array plus primitive cursors and an int64[] stack (a value-typed storage shorthand — exempt from Rule B) are all permitted. The per-node key is bound DIRECTLY to the node's INTERNAL key field (value =@ nd.key), never via an accessor (whose inlining into a =@ bind would copy the move-only key — the key-bind gotcha shared with HashBucketIterator).

Parameterised over [K, V] (V needed to name RBNode[K, V]); H is irrelevant.

kernel/src/RedBlackTreeDictionaryIterator.ev:34

Constructors

INIT(REFERENCE RBNode[K, V][] arena, int64 root, int64 count)

Methods

METHOD hasNext() RETURNS boolean

MODIFY METHOD next() RETURNS | REFERENCE K

METHOD peek() RETURNS | REFERENCE K

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE K

CLASS ShallowDictionary

IMPLEMENTS Dictionary

A Dictionary[K,V,H] with a WHOLE-KEY-SET-AWARE multiply-shift index and a prime-modulus fallback tier: linear-probe open-addressing over a STRUCT-OF-ARRAYS. Pure Envzn, zero-dep.

STATUS — PARKED as a narrow, documented option, NOT the default. A measurement-driven finding (2026-07-13) settled its role: a dictionary lookup is memory-bound, and cache-fast access requires either an IDENTITY hash on dense keys (IntKeyedDictionary's key & mask, ~1.1x C) or INLINE byte-dense slots (StringKeyedDictionary). A MIXING index — FNV, SipHash, OR this class's multiply-shift — scatters adjacent keys to random slots by design, eating a cache miss per probe, which floors any such dict at ~3-4x C. Measured here: ~4.6x C for int keys, SLOWER than ChainedHashDictionary (~3.3x). So multiply-shift is robust-but-slow; it does NOT unify "fast + robust" (the two are physically opposed). Its one distinct property — structural (bit-pattern) attack resistance without a keyed hasher — is better served by ProHashDictionary (SipHasher, which also stops hash-collision attacks). Kept correct + tested as an explicit option; use IntKeyedDictionary / StringKeyedDictionary for speed, ChainedHashDictionary as the general default, ProHashDictionary for DoS.

WHY "SHALLOW": at each rehash it holds the whole live key set, SEARCHES a few candidate 64-bit multipliers, and adopts the one that keeps home-slot depth shallowest for THIS key set — a hash chosen for the actual keys, not blind. If no pow2 multiplier can tame a pathological set (keys whose entropy is trapped in a few low bits — e.g. all multiples of a power of two), it falls back to a PRIME-sized table with mod-prime indexing, which is coprime to any 2^k stride and breaks those structural collisions. This is the robustness IntKeyedDictionary's hash & mask deliberately trades away for cache speed — ShallowDictionary is the safe default; IntKeyedDictionary is the trusted-key fast tier.

INDEX — two composed layers (slotFor): - pow2 (common): slot = (mult * hash) >> shift, probe (s+1) & mask. - prime (fallback): slot = (mult * hash) % p, probe s+1 wrap-at-p. The multiply-shift mixes ALL bits of the hasher output, so it rescues a weak/cheap hasher (FastIntHasher's identity) and is harmless for a strong one (FNV/SipHash is already uniform → the search converges on the first candidate). Full hasher pluggability AND a whole-key-set-aware low-collision index, together.

STORAGE — four parallel value-arrays (SoA, blittable → flat _ValueArray; the hot probe touches only the dense slotState/slotHash, then one keys[s]): - slotState : int8[] — 0 empty / 1 full / 2 tombstone. Liveness lives here, so ANY key value is valid (no reserved sentinels — unlike IntKeyedDictionary). - slotHash : uint64[] — cached full hash per slot; the slotHash[s]==h fast-reject skips the key compare on almost all non-matches (crucial once String keys land — a mismatched hash never calls equals). - keys : K[], vals : V[] — parallel per-slot key/value.

DoS: hash-flooding resistance comes from the pluggable hasher H — construct as ShallowDictionary[K,V,SipHasher[K]] for a keyed, attacker-proof hash; the prime fallback additionally bounds structural (bit-pattern) attacks. Default (DefaultHasher / FNV) is the fast general-purpose choice.

V1 SCOPE: primitive K/V (the blittable fast path — SoA _ValueArray). String keys (the design's 5x-over-chained headline) are the next step; they need object-array slot handling (empty-slot placeholders + the cached-hash reject to gate equals), which the cached-hash column above is already laid out for.

IMPLEMENTS Dictionary[K, V, H] — Cloneable comes transitively (Dictionary EXTENDS Cloneable). H is the interface hasher slot; the stored hasher is the Hasher OF K interface (no-arg INIT CREATEs DefaultHasher). Plus the non-pipe-XOR fast path (operator[] / lookupFast) for callers holding the concrete type.

kernel/src/ShallowDictionary.ev:76

Fields

Constructors

INIT()

INIT(Hasher[K] h)

Methods

MODIFY METHOD insert(K key, V value) RETURNS STATUS

MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUS

METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE V

METHOD __op_index__(REFERENCE K key) RETURNS V

Direct value read — d[key]. Returns the stored value on a hit, or the V default (0) on a miss. No pipe-XOR (V | STATUS) tuple on the hot path.

METHOD lookupFast(REFERENCE K key) RETURNS boolean

Comma-return lookup — boolean f, V v := d->lookupFast(key). No pipe-XOR; found distinguishes a miss from a stored default.

METHOD contains(REFERENCE K key) RETURNS boolean

MODIFY METHOD remove(REFERENCE K key) RETURNS | K

Remove — hands back the stored key and value. Like IntKeyedDictionary and unlike ChainedHashDictionary, an SoA open-addressed table has no move-out-at-index primitive, so a subscript read clones rather than moves (stmt_assign.py:149). Census pins this at one DUPLICATE per half.

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

MODIFY METHOD clear() RETURNS void

METHOD iterator() RETURNS ReferenceIterator[K]

METHOD keys() RETURNS LinkedList[K]

METHOD clone() RETURNS Dictionary[K, V, H]

METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS boolean

for Equatable Interface Dictionary is equal if all keys between the two dictionaries are equal Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.

Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so two "equal" dictionaries would answer lookup(a) differently and neither could stand in for the other — which is the whole point of an equivalence. Keys-AND-values is what C++ (map and unordered_map), Rust, Swift, Julia, Python and Java all specify. Keyset equality is a perfectly good relation, but it is equality of the DOMAIN rather than of the dictionary, and it deserves its own name (hasSameKeys) rather than this one.

Equal sizes plus a one-way walk is sufficient: with the counts already equal, other cannot carry a key this one lacks unless this one also carries a key other lacks — and the walk would have found that.

CLASS ShallowDictionaryIterator

IMPLEMENTS ReferenceIterator

The ReferenceIterator OF K returned by ShallowDictionary.iterator(). Walks the struct-of-arrays slots, yielding a REFERENCE K per live slot (slotState[pos] == 1).

Holds mutation-locking REFERENCEs to the dictionary's keys value-array and its slotState liveness array (bound with =@ in INIT); the lock pins the source dictionary against mutation for the iterator's declaring-block lifetime. Cursor pos is the next slot to examine; advanceToValid() skips empty (0) and tombstone (2) slots.

Parameterised over [K, V] to match the dictionary's arity; V is unused (the values are not walked), the hasher H is not needed (the iterator never hashes).

kernel/src/ShallowDictionaryIterator.ev:28

Constructors

INIT(REFERENCE K[] keyArr, REFERENCE int8[] stateArr, int64 capacity)

Methods

METHOD hasNext() RETURNS boolean

MODIFY METHOD next() RETURNS | REFERENCE K

METHOD peek() RETURNS | REFERENCE K

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE K

CLASS StringKeyedDictionary

IMPLEMENTS Dictionary

A byte-keyed dictionary: linear-probe open-addressing over a STRUCT-OF-ARRAYS with BYTE-DENSE keys held in ONE FLAT binary[] pool, a byte-FNV hash, and a memcmp confirm. The STRING FAST TIER. Pure Envzn, zero-dep.

WHY the key is a byte array, NOT Dictionary[String, V, H]: Two compiler realities, met head-on, shaped this class (2026-07-13): 1. The Dictionary[BinaryWord,V,H] INTERFACE cannot fix one of its type parameters — an impl must be parameterised over the SAME type variables as the interface (a ... IMPLEMENTS Dictionary[String, V, H] is rejected E2103: the interface body still references BinaryWord, unbound in the impl's scope). So there is no way to write a String-SPECIALISED Dictionary impl; a generic [BinaryWord,V,H] one (ChainedHashDictionary) is the only shape, and it must hash/compare keys through the pluggable Hasher + Equatable == — the SLOW char32 path (String stores char32 code points; each hash/equals iterates them through handle-indirected, bounds-checked accessors). 2. The s05 word-dict study (FINDINGS.md #5/#9/#17) proved the fast form is BYTE-DENSE keys read by DIRECT FLAT-ARRAY INDEXING — "byte-dense IS faster; the slowness was ByteBuffer method dispatch, not byte-density." So this class takes the KEY AS binary[] bytes (the caller transcodes its String once, key INTO ByteBuffer → bytes, UNTIMED — exactly the s05 benchmark's contract), sidestepping BOTH the interface-fix wall and the per-lookup String→bytes transcode. It is a standalone CLASS, constructed directly. The "relocate cost inward" tier for string/byte keys.

MODELLED ON benchmarks/s05_worddict/envzn_shimopt/native/native.hpp — the shim's open-addressing map (byte-FNV + linear probe + stored-hash reject + length reject + memcmp confirm), REBUILT PURE: what the inline C++ shim did with libc, the new language performance levers do in-language — - HOTLOOP → the byte-FNV hash loop (hoists the per-byte bounds check to one up-front range check; the constitution I.H.iii(f) example IS this hash). - System->memoryCompare → the key confirm (std::memcmp, one bounds-checked call per probe instead of a per-byte Envzn loop). The HOT-path lever. - System->memoryWord → available for a word-wise long-key hash (not exercised by the short Shakespeare words; a length-gated follow-up).

STORAGE — a FLAT byte pool + five parallel per-slot arrays (SoA; the hot probe touches only the dense slotState/slotHash, then the pooled key bytes): - keyBytes : binary[] — ONE flat, append-only pool; every key's bytes live here, contiguous — the cache-dense form the s05 study crowned (#17). A removed key's bytes linger until clear() (no compaction in V1 — a bounded, documented cost; memoryCopy-based compaction on high-tombstone rehash is the follow-up). - slotOff : int32[], slotLen : int32[] — each slot's key start + length in the pool. - slotState : int8[] — 0 empty / 1 full / 2 tombstone (liveness; any byte content is a valid key). - slotHash : uint64[] — cached full FNV hash; the slotHash[s]==h fast-reject skips the length + memcmp on almost every non-match (the crucial gate for byte keys). - vals : V[] — parallel per-slot value.

INDEX — hash & mask (pow2), probe (s+1) & mask — native.hpp's index exactly. FNV is a MIXING hash so this scatters, but for arbitrary string keys there is no dense-key structure to exploit; the byte-dense pool + cached-hash reject is the cache lever here, not index locality (the s05 finding, distinct from IntKeyedDictionary's key & mask).

SURFACE — a byte-array analogue of the Dictionary fast tier: insert/lookupFast/ lookup (pipe-XOR)/lookupRef/contains/remove/size/isEmpty/clear/clone. Each comes in a whole-array form (insert(binary[] key, ...), key IS the array) and a zero-copy SLICE form (insertSlice(buf, off, len, ...)) for the s05 flat-query loop that never allocates per lookup. Iteration over pooled keys is a deferred follow-up.

kernel/src/StringKeyedDictionary.ev:73

Fields

Constructors

INIT()

Methods

MODIFY METHOD insertSlice(REFERENCE binary[] buf, int64 off, int64 len, V value) RETURNS STATUS

Insert the key slice buf[off .. off+len) → value (value MOVEd in). New keys are interned into the flat pool. Replacing an existing key leaves count unchanged.

METHOD lookupFastSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean

Comma-return lookup over a slice — boolean f, V v := d->lookupFastSlice(buf,off,len). No pipe-XOR tuple on the hot path.

METHOD lookupSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS | V

METHOD containsSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean

MODIFY METHOD removeSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean

MODIFY METHOD insert(REFERENCE binary[] key, V value) RETURNS STATUS

METHOD lookupFast(REFERENCE binary[] key) RETURNS boolean

METHOD lookup(REFERENCE binary[] key) RETURNS | V

METHOD lookupRef(REFERENCE binary[] key) RETURNS | MUTABLE REFERENCE V

METHOD contains(REFERENCE binary[] key) RETURNS boolean

MODIFY METHOD remove(REFERENCE binary[] key) RETURNS boolean

METHOD isEmpty() RETURNS boolean

METHOD size() RETURNS int64

MODIFY METHOD clear() RETURNS void

MODIFY METHOD insert(BinaryWord key, V value) RETURNS STATUS

METHOD lookupFast(REFERENCE BinaryWord key) RETURNS boolean

Dictionary.lookupFast — the interface-shaped (BinaryWord-keyed) peer of the binary[] slice form above. K is BinaryWord for this class, so this is the overload that satisfies the interface; the slice form stays for the zero-copy call sites that already hold a buffer and a range.

METHOD lookup(REFERENCE BinaryWord key) RETURNS | MUTABLE REFERENCE V

METHOD contains(REFERENCE BinaryWord key) RETURNS boolean

MODIFY METHOD remove(REFERENCE BinaryWord key) RETURNS | BinaryWord

The removed key is returned as a word over THIS dictionary's pool, and the pool outlives the slot — a tombstone does not reclaim the bytes — so the returned word stays readable until the next rehash compacts them.

METHOD iterator() RETURNS ReferenceIterator[BinaryWord]

One BinaryWord per live key, borrowed from this dictionary's pool. Valid only while the dictionary is: the words point INTO its storage, and a rehash moves that storage.

METHOD keys() RETURNS LinkedList[BinaryWord]

Every live key, as borrowed words. Same lifetime caveat as iterator().

MODIFY METHOD insertCopy(REFERENCE BinaryWord key, REFERENCE V value) RETURNS STATUS

METHOD clone() RETURNS Dictionary[BinaryWord, V, H]

Returns the Dictionary INTERFACE, not the concrete class — the class is HIDDEN, so its name may appear only as a CREATE target, and this is the shape ProHashDictionary.clone() already had. The copy goes in through the interface's own insert, since insertSlice is this class's and not the interface's.

METHOD equals(REFERENCE Dictionary[BinaryWord, V, H] other) RETURNS boolean

for Equatable Interface Dictionary is equal if all keys between the two dictionaries are equal Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.

Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so two "equal" dictionaries would answer lookup(a) differently and neither could stand in for the other — which is the whole point of an equivalence. Keys-AND-values is what C++ (map and unordered_map), Rust, Swift, Julia, Python and Java all specify. Keyset equality is a perfectly good relation, but it is equality of the DOMAIN rather than of the dictionary, and it deserves its own name (hasSameKeys) rather than this one.

Equal sizes plus a one-way walk is sufficient: with the counts already equal, other cannot carry a key this one lacks unless this one also carries a key other lacks — and the walk would have found that.

CLASS StringKeyedDictionaryIterator

IMPLEMENTS ReferenceIterator

Walks the open-addressed slot table, yielding one BinaryWord per OCCUPIED slot — a borrowed window onto that key's bytes in the shared pool.

NO ALLOCATION PER KEY, and that is the whole reason this class exists rather than materialising keys. The window is a VALUE class held in one field, .cur, re-assigned at each step; next() hands back a reference to that field. So a walk of a million keys performs one assignment per key and no heap traffic at all — which is what keeps the dictionary's measured advantage intact while it satisfies the Dictionary contract.

Slot states match the dictionary's own encoding: 0 empty, 1 occupied, 2 tombstone. Only 1 is yielded.

kernel/src/StringKeyedDictionaryIterator.ev:28

Constructors

INIT(REFERENCE binary[] pool, REFERENCE int64[] offs, REFERENCE int64[] lens, REFERENCE int8[] states, int64 capacity)

Methods

METHOD hasNext() RETURNS boolean

MODIFY METHOD next() RETURNS | REFERENCE BinaryWord

METHOD peek() RETURNS | REFERENCE BinaryWord

MODIFY METHOD skip(uint64 n) RETURNS | REFERENCE BinaryWord

CLASS BinaryWord

IMPLEMENTS Cloneable, Hashable, Equatable, Comparable

A BORROWED window onto a run of bytes: the array, where the run starts, and how long it is. Value-copied and inline — copying a BinaryWord copies three machine words, never the bytes.

WHY IT EXISTS. A byte-keyed dictionary stores every key end-to-end in one pool and remembers each key as an (offset, length) pair, because that is what makes it fast: one allocation for all the keys instead of one per key. But a key so stored is not a value the language can hand back — binary is a single byte, and an iterator yielding bytes cannot say where one key ends and the next begins. BinaryWord is that missing value: the pair the dictionary already holds, given a type.

It BORROWS. The bytes belong to whatever pool the window was opened on, and a BinaryWord is valid exactly as long as that pool is. It is the byte-axis sibling of StringView/ByteBufferView, and differs from them in being a VALUE class: a view is an object reached through a handle, while a word is copied inline, which is what lets an iterator yield one per step without allocating.

kernel/src/BinaryWord.ev:30

Constructors

INIT(REFERENCE binary[] src, int64 off, int64 len)

Methods

METHOD length() RETURNS int64

Bytes in the window.

METHOD offset() RETURNS int64

Where the window opens in the underlying pool. A caller holding the pool can use this with length() to reach the bytes directly — which is how the slice fast paths avoid going through the window at all.

METHOD at(int64 i) RETURNS | binary

The byte at i within the window, or FAILURE when i is outside it.

METHOD clone() RETURNS BinaryWord

METHOD hash() RETURNS uint64

METHOD equals(REFERENCE BinaryWord other) RETURNS boolean

Equal when the windows hold the same bytes — not when they name the same place. Two words over different pools are equal if their bytes match.

METHOD isLessThan(REFERENCE BinaryWord other) RETURNS boolean

Lexicographic by bytes, shorter-is-less on a shared prefix — the order a byte-keyed tree needs to stay total.