Skip to content

runtime: preserve Map and Set insertion order after delete #2831

Description

@andrewtdiz

Summary

Map and Set iteration must preserve insertion order of the remaining entries after deletion. Perry's current delete helpers use swap-remove, moving the last entry into the deleted slot, so subsequent keys(), values(), entries(), forEach, Array.from, spread, and for...of-style lowering can observe reordered collections.

Node behavior

console.log(Array.from((() => {
  const s = new Set([1, 2, 3, 4]);
  s.delete(2);
  return s;
})()));
// [1, 3, 4]

console.log(Array.from((() => {
  const m = new Map([[1, "a"], [2, "b"], [3, "c"], [4, "d"]]);
  m.delete(2);
  return m.keys();
})()));
// [1, 3, 4]

console.log(Array.from((() => {
  const m = new Map([[1, "a"], [2, "b"]]);
  m.delete(1);
  m.set(1, "z");
  return m.entries();
})()));
// [[2, "b"], [1, "z"]]

Updating an existing key keeps its position, while deleting and re-adding appends it at the end.

Current Perry evidence

  • crates/perry-runtime/src/map.rs::js_map_delete() captures the last key/value and writes them into the deleted index before decrementing size. The comments call this swap-and-pop / swap-remove, and the side-table maintenance rewrites the swapped key's stored index to the removed index.
  • crates/perry-runtime/src/set.rs::js_set_delete() uses the same swap-remove strategy: when the removed value is not the last element, it writes the last element into the removed index and updates that element's index.
  • crates/perry-runtime/src/map.rs::js_map_entries(), js_map_keys(), js_map_values(), js_map_foreach(), and crates/perry-runtime/src/set.rs::js_set_to_array(), js_set_value_at(), js_set_foreach() all iterate the compacted backing storage from index 0..size, so the swap becomes user-visible order.
  • crates/perry-runtime/src/set.rs::js_set_value_at() explicitly documents a direct read of the i-th element in insertion order, but the delete path breaks that invariant.

Suggested test surface

Add node-suite coverage for:

console.log("set delete first:", JSON.stringify(Array.from((() => {
  const s = new Set([1, 2, 3]);
  s.delete(1);
  return s;
})())));

console.log("set delete middle:", JSON.stringify(Array.from((() => {
  const s = new Set([1, 2, 3, 4]);
  s.delete(2);
  return s;
})())));

console.log("map delete middle:", JSON.stringify(Array.from((() => {
  const m = new Map([[1, "a"], [2, "b"], [3, "c"], [4, "d"]]);
  m.delete(2);
  return m.keys();
})())));

console.log("map delete readd:", JSON.stringify(Array.from((() => {
  const m = new Map([[1, "a"], [2, "b"]]);
  m.delete(1);
  m.set(1, "z");
  return m.entries();
})())));

Expected output preserves the original relative order of survivors and appends re-added keys/values at the end.

Scope / non-goals

This issue is only about insertion-order preservation across delete and re-add for existing Map/Set implementations. It does not require changing the constructor iterable protocol (#2770/#2771) or callback arity / thisArg semantics (#2830).

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions