moonbitlang / core / 6296

91%

push

github

fix(hashset): make `copy` independent of the original (#4130)

`HashSet::copy` allocated a fresh `entries` array and then blitted the
old one into it. `FixedArray[Entry[K]?]` holds references, so both sets
came away sharing the same `Entry` objects -- and `Entry::psl` is
mutable, decremented by `shift_back` whenever a removal shifts a run
back.

So a removal on either set silently corrupted the other's probe
sequences. Emptying a copy of a 32-element set leaves all but two of the
original's keys unreachable by `contains`, while `length` still reports
32, because `size` is a separate field on each set.

Rebuild each occupied slot instead, which is what `HashMap::copy`,
`Map::copy` and `Set::copy` already do -- `HashSet` was the only
container blitting. Slots are copied position for position, so the
copy's iteration order still matches the original's.

`copy` gets slower, because it now actually copies: 241 us -> 455 us on
native and 281 us -> 430 us on js for 50000 elements. That is the cost
of the operation being correct, and it brings `HashSet` in line with
what the other three containers already pay.

The regression test uses a key type whose hash maps into eight buckets,
so the collisions that make removal reach `shift_back` are deterministic
rather than dependent on how `Int` hashing happens to mix -- the same
`Collide` pattern `hashmap` already uses for its coverage tests.

Found while benchmarking removal for the struct-of-arrays work: a
copy-then-remove benchmark gave results that could not be explained
until the shallow copy came to light.

Co-authored-by: Claude Opus 5 (1M context) <noreply@anthropic.com>

2 of 2 new or added lines in 1 file covered. (100.0%)

16764 of 18447 relevant lines covered (90.88%)

306079.1 hits per line