SameValueZero-keyed ordered store for Map and Set

Date: 2026-06-27 Area: data-structures / engine Issue: #807

Strong Map and Set stored their entries in a flat list and located keys by a linear SameValueZero scan, so every get/set/has/delete was O(n) and any build-or-probe loop was O(n²); set-algebra (union/intersection/…) was O(n·m). WeakMap/WeakSet already use THashMap keyed by pointer identity, but strong collections cannot reuse it: their keys compare by SameValueZero (ES2026 §7.2.11) — NaN equals NaN, -0 equals +0, strings and BigInts compare by content, and only objects/functions/symbols compare by reference. Identity hashing would split equal primitives across buckets. The distinction is therefore content-hash (strong Map/Set) vs identity-hash (weak collections), and the two stores stay separate.

We back both Map and Set with a single new type, TGocciaOrderedValueMap (source/units/Goccia.Values.OrderedValueMap.pas) — the first production consumer of the generic insertion-ordered TOrderedMap (ADR 0019). It overrides the map's protected HashKey/KeysEqual with a hash that is exactly consistent with IsSameValueZero (number with NaN- and signed-zero canonicalization over the IEEE-754 bits, string/BigInt by content, primitives by category, objects by pointer — the GC never relocates, so pointers are stable) and IsSameValueZero itself for equality. Set reuses the same type with the element stored as both key and value, so there is one store, one hash, and one set of tests rather than a per-collection subclass or a parallel structure. Operations become O(1) amortized and set-algebra O(n+m). The hash/equality pair is the load-bearing invariant — an inconsistent hash silently loses entries — so it is guarded by a Pascal invariant test (Goccia.Values.OrderedValueMap.Test.pas) in addition to the JavaScript suite.

Live-iterator semantics follow the spec's [[MapData]] model: the entry list is append-only and delete writes a tombstone rather than shifting, so a Map/Set iterator (and forEach) holds a physical cursor that skips tombstones and sees entries appended mid-iteration (ES2026 §24.1.3.5). The one hazard is the inherited tombstone-reclaiming compaction, which renumbers entries; we add a CanCompact virtual to TOrderedMap (default unchanged) and gate it on a per-store live-iterator counter (RetainIterator/ReleaseIterator), so while any iteration is in flight the store only grows (which preserves indices) and never renumbers, then reclaims tombstones once no iteration is active. This is the same shape as engines that only shrink a keyed collection's storage once no iterator references it. The residual gap is an iterator that is partially consumed and then abandoned (never exhausted or closed) before being garbage-collected: it leaves the gate held, so that store stops reclaiming tombstones until it is cleared, and sustained set+delete churn on it grows storage meanwhile. That is a safe degradation, not a correctness bug — the common cases (full for...of, spread, forEach, an exhausted or return()-closed iterator) always release the gate — and releasing it for abandoned iterators needs GC-driven notification (the iterator cannot safely touch its source store from a sweep-time destructor), which is left as a follow-up. Insertion also applies CanonicalizeKeyedCollectionKey (ES2026 §24.5.1), storing -0 as +0.

Adopting the spec model fixed four pre-existing conformance bugs the flat-list implementation carried (none covered by the prior suite): -0 keys were stored un-normalized; forEach/iterators did not visit entries appended during iteration; deleting during forEach threw RangeError: Argument out of range; and deleting the current key during for...of skipped the next entry and left size wrong. Regression tests for all four ship with this change.

Alternatives rejected: extending THashMap with SameValueZero — it is unordered, tombstone-free, and identity-tuned, so it would need insertion ordering and content equality bolted on, i.e. effectively this store; a purpose-built standalone store modelled on TOrderedStringMap — avoids virtual HashKey dispatch but adds a fourth map implementation to maintain and leaves TOrderedMap with no production user; keeping the flat list with a side hash index — leaves delete O(n) and does not fix the live-iteration bugs; and compacting eagerly always (renumbers live cursors) or never (unbounded growth under sustained set+delete churn). See ADR 0019 and docs/value-system.md.