fix(lualib): support Map/Set entry deletion during iteration#1728
Open
pilaoda wants to merge 1 commit into
Open
fix(lualib): support Map/Set entry deletion during iteration#1728pilaoda wants to merge 1 commit into
pilaoda wants to merge 1 commit into
Conversation
There was a problem hiding this comment.
Pull request overview
Note
Copilot was unable to run its full agentic suite in this review.
This PR refactors the Lua-lib Map/Set implementations to use insertion-ordered “flat array + tombstones” storage with compaction, and adds extensive iterator-mutation and memory-retention tests to validate behavior against JS/V8 semantics.
Changes:
- Replaced linked-list style key ordering with array-backed ordered storage for
MapandSet, including tombstone deletion and lazy iterator transition on compaction. - Added many new mutation tests for
for-ofandforEachiteration when deleting/re-adding entries. - Added “memory leak” regression tests that force Lua table rehashing and compare GC memory deltas.
Reviewed changes
Copilot reviewed 4 out of 4 changed files in this pull request and generated 6 comments.
| File | Description |
|---|---|
| test/unit/builtins/set.spec.ts | Adds iterator-mutation cases, V8-style iterator stress tests, and a Set GC-retention regression test. |
| test/unit/builtins/map.spec.ts | Adds iterator-mutation cases, V8-style iterator stress tests, and a Map GC-retention regression test with detailed Lua rehash rationale. |
| src/lualib/Set.ts | Reimplements Set ordering via array-like tables with tombstones + compaction and iterator lazy-transition logic. |
| src/lualib/Map.ts | Reimplements Map ordering via array-like tables with tombstones + compaction and iterator lazy-transition logic; adds design doc comment. |
| public forEach(callback: (value: V, key: K, map: Map<K, V>) => any): void { | ||
| for (const key of this.keys()) { | ||
| callback(this.items.get(key), key, this); | ||
| callback(this.orderedValues.get(this.keyIndex.get(key)), key, this); |
Comment on lines
+137
to
+139
| const val = keys.get(idx); | ||
| idx++; | ||
| return { done: false, value: [val, val] as [T, T] }; |
Comment on lines
+107
to
+108
| holeCount++; | ||
| oldKeys.set(-holeCount, i as any); |
Comment on lines
+112
to
+113
| oldKeys.set(0, newKeys as any); | ||
| oldValues.set(0, newValues as any); |
| }; | ||
| `.getLuaExecutionResult(); | ||
| expect(result.size).toBe(0); | ||
| expect(result.retained).toBe(0); |
| }; | ||
| `.getLuaExecutionResult(); | ||
| expect(result.size).toBe(0); | ||
| expect(result.retained).toBe(0); |
dfb31e5 to
908b802
Compare
…on during deletion Replace linked list (nextKey/previousKey) with flat arrays + V8-style version chain compaction. Deleted entries become tombstones (nil slots); iterators skip them via idx++. Compaction creates new arrays and links old → new; iterators transition lazily by adjusting their index. Changes: - Map/Set use keyIndex (hash), orderedKeys/orderedValues (arrays) - delete() marks tombstone, triggers compact when deletedCount > size - compact() records hole positions, links old arrays to new via index 0 - Iterator transitions through version chain (V8 Transition algorithm) - has() uses keyIndex (works correctly with null/undefined values) Based on V8's OrderedHashTable: https://chromium.googlesource.com/v8/v8/+/main/src/objects/ordered-hash-table.cc Tests: 166 Map/Set tests including V8 stress tests, memory leak tests, delete-during-iteration, re-add, and consecutive delete scenarios. Adapted from V8's collection-iterator.js: https://chromium.googlesource.com/v8/v8/+/main/test/mjsunit/es6/collection-iterator.js
908b802 to
66c2d6d
Compare
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Problem
Deleting Map/Set entries during iteration breaks the iterator —
delete()clearsnextKey[key], the pointer the iterator relies on to advance. This violates the ES spec.Solution
Rewrite Map/Set internals from linked list to flat arrays with tombstone deletion and V8-style version chain compaction:
orderedKeys/orderedValues: 1-based integer arrays (leverages Lua's contiguous array part for fast iteration)keyIndex: hash table for O(1) lookupidx++deletedCount > size, creates new arrays linked via version chainAlso fixes
has()returningfalsefor keys withnull/undefinedvalues (now useskeyIndexinstead ofnextKey).