Skip to content

fix(lualib): support Map/Set entry deletion during iteration #1728

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
pilaoda wants to merge 1 commit into
base: master
Choose a base branch
from
+746 −155
Open

fix(lualib): support Map/Set entry deletion during iteration #1728

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
248 changes: 167 additions & 81 deletions src/lualib/Map.ts
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,15 +1,28 @@
// Insertion-ordered Map using flat arrays with tombstone deletion and
// V8-style version chain compaction. Deleted entries become nil (tombstones);
// iterators skip them via idx++. Compaction creates new arrays and links
// old → new at index 0; iterators transition lazily by adjusting their
// index (subtracting holes before current position).
//
// Using integer-indexed arrays (orderedKeys/orderedValues) for the insertion
// order leverages Lua's array part: sequential integer keys are stored in
// contiguous memory, making iteration a simple pointer offset (~2-3 cycles)
// rather than a hash table lookup (~15-50 cycles per step).
//
// Based on V8's OrderedHashTable (ordered-hash-table.cc: Rehash, Transition):
// https://chromium.googlesource.com/v8/v8/+/main/src/objects/ordered-hash-table.cc
export class Map<K extends AnyNotNil, V> {
public static [Symbol.species] = Map;
public [Symbol.toStringTag] = "Map";

private items = new LuaTable<K, V>();
public size = 0;

// Key-order variables
private firstKey: K | undefined;
private lastKey: K | undefined;
private nextKey = new LuaTable<K, K>();
private previousKey = new LuaTable<K, K>();
// Flat array storage (1-based indices for Lua)
private keyIndex = new LuaTable<K, number>();
private orderedKeys = new LuaTable<number, K>();
private orderedValues = new LuaTable<number, V>();
private nextSlot = 1;
private deletedCount = 0;

constructor(entries?: Iterable<readonly [K, V]> | Array<readonly [K, V]>) {
if (entries === undefined) return;
Expand All @@ -36,141 +49,214 @@ export class Map<K extends AnyNotNil, V> {
}

public clear(): void {
this.items = new LuaTable();
this.nextKey = new LuaTable();
this.previousKey = new LuaTable();
this.firstKey = undefined;
this.lastKey = undefined;
this.keyIndex = new LuaTable();
this.orderedKeys = new LuaTable();
this.orderedValues = new LuaTable();
this.nextSlot = 1;
this.size = 0;
this.deletedCount = 0;
}

public delete(key: K): boolean {
const contains = this.has(key);
if (contains) {
this.size--;

// Do order bookkeeping
const next = this.nextKey.get(key);
const previous = this.previousKey.get(key);
if (next !== undefined && previous !== undefined) {
this.nextKey.set(previous, next);
this.previousKey.set(next, previous);
} else if (next !== undefined) {
this.firstKey = next;
this.previousKey.set(next, undefined!);
} else if (previous !== undefined) {
this.lastKey = previous;
this.nextKey.set(previous, undefined!);
const idx = this.keyIndex.get(key);
if (idx === undefined) return false;
this.size--;
this.deletedCount++;
this.keyIndex.delete(key);
this.orderedKeys.delete(idx);
this.orderedValues.delete(idx);

if (this.deletedCount > this.size) {
this.compact();
}
return true;
}

// Compaction is needed because nextSlot grows monotonically — deleted
// entries leave nil tombstones but Lua tables don't shrink on nil
// assignment. Lua only resizes a table during rehash, and rehash only
// triggers when a hash-part insert exhausts free nodes (ltable.c:
// luaH_newkey → getfreepos → rehash). Since orderedKeys uses sequential
// integer indices (array part), normal inserts rarely touch the hash
// part, so rehash won't trigger naturally to reclaim the space.
//
// V8-style: copy live entries to new arrays, record hole positions in
// the old array at negative indices, link old[0] → new. Active iterators
// hold old arrays and transition lazily on next() by adjusting their
// index (subtracting holes before current position).
//
// Index 0 and negative indices go to Lua's hash part (not array part),
// so they don't conflict with the 1-based data entries.
private compact(): void {
const oldKeys = this.orderedKeys;
const oldValues = this.orderedValues;
const oldNextSlot = this.nextSlot;
const newKeys = new LuaTable<number, K>();
const newValues = new LuaTable<number, V>();
let newSlot = 1;
let holeCount = 0;

for (let i = 1; i < oldNextSlot; i++) {
const k = oldKeys.get(i);
if (k !== undefined) {
newKeys.set(newSlot, k);
newValues.set(newSlot, oldValues.get(i));
this.keyIndex.set(k, newSlot);
newSlot++;
} else {
this.firstKey = undefined;
this.lastKey = undefined;
holeCount++;
oldKeys.set(-holeCount, i as any);
Comment on lines +107 to +108
}

this.nextKey.set(key, undefined!);
this.previousKey.set(key, undefined!);
}
this.items.set(key, undefined!);

return contains;
oldKeys.set(0, newKeys as any);
oldValues.set(0, newValues as any);
Comment on lines +112 to +113

this.orderedKeys = newKeys;
this.orderedValues = newValues;
this.nextSlot = newSlot;
this.deletedCount = 0;
}

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);
}
}

public get(key: K): V | undefined {
return this.items.get(key);
const idx = this.keyIndex.get(key);
if (idx === undefined) return undefined;
return this.orderedValues.get(idx);
}

public has(key: K): boolean {
return this.nextKey.get(key) !== undefined || this.lastKey === key;
return this.keyIndex.get(key) !== undefined;
}

public set(key: K, value: V): this {
const isNewValue = !this.has(key);
if (isNewValue) {
const existingIdx = this.keyIndex.get(key);
if (existingIdx !== undefined) {
this.orderedValues.set(existingIdx, value);
} else {
this.size++;
const idx = this.nextSlot;
this.nextSlot = idx + 1;
this.keyIndex.set(key, idx);
this.orderedKeys.set(idx, key);
this.orderedValues.set(idx, value);
}
this.items.set(key, value);

// Do order bookkeeping
if (this.firstKey === undefined) {
this.firstKey = key;
this.lastKey = key;
} else if (isNewValue) {
this.nextKey.set(this.lastKey!, key);
this.previousKey.set(key, this.lastKey!);
this.lastKey = key;
}

return this;
}

public [Symbol.iterator](): IterableIterator<[K, V]> {
return this.entries();
}

// entries/keys/values are intentionally kept inline (not refactored into
// a shared helper) to avoid per-step function call overhead on this hot path.
public entries(): IterableIterator<[K, V]> {
const getFirstKey = () => this.firstKey;
const { items, nextKey } = this;
let key: K | undefined;
let started = false;
let keys = this.orderedKeys;
let vals = this.orderedValues;
const map = this; // eslint-disable-line @typescript-eslint/no-this-alias
let idx = 1;
return {
[Symbol.iterator](): IterableIterator<[K, V]> {
return this;
},
next(): IteratorResult<[K, V]> {
if (!started) {
started = true;
key = getFirstKey();
} else {
key = nextKey.get(key!);
while (keys.get(0) !== undefined) {
let adj = 0;
let h = 1;
while (true) {
const holePos = keys.get(-h) as any as number | undefined;
if (holePos === undefined || holePos >= idx) break;
adj++;
h++;
}
idx -= adj;
vals = vals.get(0) as any;
keys = keys.get(0) as any;
}
while (idx < map.nextSlot && keys.get(idx) === undefined) {
idx++;
}
if (idx >= map.nextSlot) {
return { done: true, value: undefined! };
}
return { done: !key, value: [key!, items.get(key!)] as [K, V] };
const i = idx;
idx++;
return { done: false, value: [keys.get(i), vals.get(i)] as [K, V] };
},
};
}

public keys(): IterableIterator<K> {
const getFirstKey = () => this.firstKey;
const nextKey = this.nextKey;
let key: K | undefined;
let started = false;
let keys = this.orderedKeys;
const map = this; // eslint-disable-line @typescript-eslint/no-this-alias
let idx = 1;
return {
[Symbol.iterator](): IterableIterator<K> {
return this;
},
next(): IteratorResult<K> {
if (!started) {
started = true;
key = getFirstKey();
} else {
key = nextKey.get(key!);
while (keys.get(0) !== undefined) {
let adj = 0;
let h = 1;
while (true) {
const holePos = keys.get(-h) as any as number | undefined;
if (holePos === undefined || holePos >= idx) break;
adj++;
h++;
}
idx -= adj;
keys = keys.get(0) as any;
}
return { done: !key, value: key! };
while (idx < map.nextSlot && keys.get(idx) === undefined) {
idx++;
}
if (idx >= map.nextSlot) {
return { done: true, value: undefined! };
}
const i = idx;
idx++;
return { done: false, value: keys.get(i) };
},
};
}

public values(): IterableIterator<V> {
const getFirstKey = () => this.firstKey;
const { items, nextKey } = this;
let key: K | undefined;
let started = false;
let keys = this.orderedKeys;
let vals = this.orderedValues;
const map = this; // eslint-disable-line @typescript-eslint/no-this-alias
let idx = 1;
return {
[Symbol.iterator](): IterableIterator<V> {
return this;
},
next(): IteratorResult<V> {
if (!started) {
started = true;
key = getFirstKey();
} else {
key = nextKey.get(key!);
while (keys.get(0) !== undefined) {
let adj = 0;
let h = 1;
while (true) {
const holePos = keys.get(-h) as any as number | undefined;
if (holePos === undefined || holePos >= idx) break;
adj++;
h++;
}
idx -= adj;
vals = vals.get(0) as any;
keys = keys.get(0) as any;
}
while (idx < map.nextSlot && keys.get(idx) === undefined) {
idx++;
}
if (idx >= map.nextSlot) {
return { done: true, value: undefined! };
}
return { done: !key, value: items.get(key!) };
const i = idx;
idx++;
return { done: false, value: vals.get(i) };
},
};
}
Expand Down
Loading
Loading