v9.0.11 introduces sparse array regression

[bever1337]

🐛 Bug Report

#879 looks like an awesome fix -- thank you! -- but it has a side-effect of breaking sparse arrays created with delete.

I'm a comfortable immer user but relatively new to contributions. If someone has the time to coach, I would be glad to iterate on #879. My "hunch" is that immer should revert to actually deleting instead of setting the index to undefined, but the patch generation will need to be different for arrays and objects so the actual fix from #879 isn't reverted. At first glance, the es5 plugin changes look compatible with sparse arrays. Thanks for your time

To Reproduce

const produce10 = require("immer-v9.0.10").default;
const produce19 = require("immer-v9.0.19").default;

/**
 * @returns {number[]}
 */
const initialState = () => [];

[
  ["v9.0.10", produce10],
  ["v9.0.19", produce19],
].forEach(([version, produce]) => {
  console.log(`Testing ${version}`);

  console.log("Produces [<empty>, 42]");
  // Create sparse array with insertion
  const stateA = produce(initialState(), (draft) => {
    draft[1] = 42;
  });
  console.info(stateA);
  expect(stateA[0], undefined, "Panic!"); // actually empty, but we expect undefined
  expect(stateA[1], 42, "Panic!");

  let iterateForEach = 0;
  stateA.forEach(() => {
    iterateForEach += 1;
  });
  expect(iterateForEach, 1, "Array.forEach does not iterate empty elements");

  let iterateForLoop = 0;
  for (let i = 0; i < stateA.length; i++) {
    iterateForLoop += 1;
  }
  expect(iterateForLoop, 2, "Delete does not alter array length");

  console.log("Produces [<empty>, <empty>]");
  // Create sparse array with delete
  const stateB = produce(stateA, (draft) => {
    delete draft[1];
  });
  console.info(stateB);
  expect(stateB[0], undefined, "Panic!"); // actually empty, but we expect undefined
  expect(stateB[1], undefined, "Panic!"); // actually empty, but we expect undefined

  iterateForEach = 0;
  stateB.forEach(() => {
    iterateForEach += 1;
  });
  expect(iterateForEach, 0, "Array.forEach does not iterate empty elements");

  iterateForLoop = 0;
  for (let i = 0; i < stateB.length; i++) {
    iterateForLoop += 1;
  }
  expect(iterateForLoop, 2, "Delete does not alter array length");

  console.log(`${version} success`);
});

/**
 * @param {any} left
 * @param {any} right
 * @param {string} reason
 * @returns {void}
 */
function expect(left, right, reason) {
  if (left !== right) {
    throw new Error(reason);
  }
}

{
  "name": "sparse-test",
  "version": "1.0.0",
  "description": "Sparse array regression in ImmerJS",
  "main": "index.js",
  "scripts": {
    "test": "node index.js"
  },
  "author": "Bever1337 <bever1337@posteo.net>",
  "license": "MIT",
  "dependencies": {
    "immer-v9.0.10": "npm:immer@9.0.10",
    "immer-v9.0.19": "npm:immer@9.0.19"
  }
}

Observed behavior

delete creates dense arrays with undefined values

Expected behavior

delete creates sparse arrays

Environment

We only accept bug reports against the latest Immer version.

• Immer version:
• I filed this report against the latest version of Immer
• Occurs with setUseProxies(true)
• Occurs with setUseProxies(false) (ES5 only)

[bever1337]

Random thoughts I had about sparse arrays/elisions that might inform this request:

1. Immer does not cast elisions when creating sparse arrays
2. elisions are primitive/immutable/non-referential
3. redux serializability middleware does not complain about elisions.
4. elisions can be cloned with structured clone algorithm
5. JSON parsing will cast elisions to null (interesting but only relevant as an example). Developers using redux devtools with immer will always observe dense arrays in the monitor.
6. testing for elisions requires Array prototype iterators. Some iterators skip elisions (filter, forEach) and some do not (findIndex). Since length is never affected, standard for loops can iterate over elisions, but there's no way to discern an elision from undefined
7. elisions can be tested at a specific index with Object.hasOwnProperty.
8. neither undefined nor holes are allowed in JSON, so patches aren't technically compliant with JSON patch spec (ignoring the schema differences with the paths). IMO immer is more interested in JS than strictly JSON, so I'm not immediately concerned that developers need to handle patches that can include undefined or holes.

[mweststrate]

To be fair I don't think Immer very intentionally supports sparse arrays. Especially not as something to be distinguished from undefined entries. Likewise we don't support assigning arbitrary fields to an array like array["hello"] = "world" even though that is technically valid JS.

Imho using delete on an array is an anti-pattern, and just happenstancily "works" because an array is an object under the hood. But as you noticed yourself, it behaves quite inconsistently in the rest of the language.

I recommend to use a more idiomatic alternative instead to remove elements from arrays, like assigning undefined / null, splicing, or if your data structure is intentionally very sparse and acts more like a lookup map, you should probably be using Map instead.

[bever1337]

@mweststrate That makes a lot of sense, and thank you for your time! I commented on the other PR that also extends array patches for adding and removing items. Unfortunately for me 😉, it is a much better direction and I'm excited for it to land. Sparse arrays are uncommon, can't be represented with JSON/JSON patches, and don't work in ReduxJS. As an immer user, I'm not strictly tied to ReduxJS or a state that can be serialized into JSON, but the common use-case is better here.

Imho using delete on an array is an anti-pattern, and just happenstancily "works" because an array is an object under the hood.

I wouldn't call it happenstance that an array is an object 😛 Everything is an object in JS! What's the justification for claiming all sparse arrays are anti-pattern? I'm not sure I see how that fits into the conversation.

[mweststrate]

anti-pattern

Anti pattern, because it doesn't solve any problem that isn't solved more idiomatically otherwise, behaves unpredictable with other standard functions and libraries, and afaik de-opts from a lot of performance optimisations (that is true for delete on objects as well, but for objects there are valid use cases, although I'd still consider it something that is very rarely needed)