Skip to content

Set/Map forEach stops early when a callback delete triggers mid-iteration compaction #9082

Description

@proggeramlug

Set.prototype.forEach / Map.prototype.forEach stop early when the callback deletes enough entries to trigger the delete path's self-healing compaction mid-iteration. Every not-yet-deleted entry past that point is skipped, in violation of ECMA-262 24.1.3.5 / 24.2.3.6.

Split out of #9076, which fixed the larger half of this area (the walk yielding raw tombstone markers to the callback, and bounding by size instead of used). This residual is not introduced by that PR — main is wrong on these rows too, and more severely.

Mechanism

js_set_delete self-heals a holey backing store:

let used = (*set).used;
if used >= 16 && (*set).size < used / 2 {
    compact_set_elements(set);
}

compact_set_elements shifts survivors left and resets used to size. js_set_foreach_impl walks a raw index i over used, re-reading the extent each step — but its cursor is not rebased, so after a mid-iteration compaction i refers to slots that have moved. js_map_foreach_impl / compact_map_entries have the identical shape.

Repro

const s = new Set<number>();
for (let i = 0; i < 20; i++) s.add(i);
const seen: number[] = [];
s.forEach((v) => { seen.push(v); s.delete(v); });
console.log(seen.join(","), s.size);
node v26.5.1  0,1,2,...,19   0
perry         0,1,...,10     9

The arithmetic lines up exactly: after the 11th delete size=9, used=20, so 9 < 10 && 20 >= 16 compacts and sets used=9; the loop resumes at i=11, sees 11 >= 9, and breaks with 9 live entries unvisited.

Scope

Reproduces on Set and Map, for both "delete the entry being visited" and "delete an earlier entry", at any size that reaches the threshold. It does not reproduce below 16 elements — used >= 16 is never satisfied — which is why #9076's 3-element unit tests are green. Confirmed at n=20 and n=40:

collection mutation node perry
Set 20 delete self visits 20, size 0 visits 11, size 9
Set 20 delete earlier visits 20, size 1 visits 12, size 9
Set 40 delete self visits 40, size 0 visits 21, size 19
Map 20 delete self visits 20, size 0 visits 11, size 9

delete-ahead and add-during-iteration are correct at every size tested.

Likely fix

Either rebase the walker's cursor when it observes that a compaction happened (e.g. an iteration-generation counter on the header, bumped by compact_*), or suppress self-healing compaction while an iteration is in flight and let the walk's existing hole-skipping absorb the tombstones. The second is simpler but needs an active-iteration depth counter that is exception-safe.

Whichever lands should add a delete-during-forEach case at ≥16 elements — the existing coverage cannot reach the threshold.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugConfirmed defect or regression

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions