Set order is not always maintained when modifying with produce

[chrissantamaria]

🐛 Bug Report

When adding to a Set with produce, the insertion order is not maintained when the original Set contains a draftable object.

Link to repro

See #820 for a failing test (copied below)

it("maintains order when adding", () => {
  const objs = [
    {
      id: "a"
    },
    {
      id: "b"
    }
  ]

  const set = new Set([objs[0]])
  const newSet = produce(set, draft => {
    draft.add(objs[1])
  })

  expect(Array.from(newSet)).toEqual([objs[0], objs[1]])
})

To Reproduce

Run the "maintains order when adding" test in the "set drafts" section of __tests__/base.js.

Observed behavior

After adding a second object to the Set with produce, it is ordered before the original first object in the Set.

Expected behavior

{ id: 'b' } should appear after { id: 'a' } when iterating through newSet, matching the behavior of a normal mutation-based update.

Debugging Observations

As mentioned above, I've only noticed this in the situation where the original Set (pre-produce) contains a draftable object. For example, this test passes:

it("maintains order when adding", () => {
  const objs = [
    "a",
    {
      id: "b"
    }
  ]

  const set = new Set([objs[0]])
  const newSet = produce(set, draft => {
    draft.add(objs[1])
  })

  // passes
  expect(Array.from(newSet)).toEqual([objs[0], objs[1]])
})

but the opposite does not:

it("maintains order when adding", () => {
  const objs = [
    {
      id: "a"
    },
    "b"
  ]

  const set = new Set([objs[0]])
  const newSet = produce(set, draft => {
    draft.add(objs[1])
  })

  // does not pass
  expect(Array.from(newSet)).toEqual([objs[0], objs[1]])
})

Possible Root Cause

(take all of this with a grain of salt - my first time digging into the repo 😅 )

After a bit of digging, this function seems to be causing the order change during finalize: https://github.com/immerjs/immer/blob/dc3f66cdea53fd5a8c814924bfafa9f6b53c9c62/src/utils/common.ts#L131-L138

finalizeProperty is called on both objects (Draft of { id: 'a' } and vanilla object { id: 'b' }). On the first call, the Draft is converted back to a vanilla object and the Set value is replaced: https://github.com/immerjs/immer/blob/dc3f66cdea53fd5a8c814924bfafa9f6b53c9c62/src/core/finalize.ts#L130-L131

Since Set values can't be directly updated, set deletes the previous version (Draft of { id: 'a' }) and adds the new version (vanilla object), ultimately breaking the original order.

Environment

We only accept bug reports against the latest Immer version.

• Immer version: v9.0.3
• [x] I filed this report against the latest version of Immer
• [x] Occurs with setUseProxies(true)
• [x] Occurs with setUseProxies(false) (ES5 only)

This appears to have been introduced in v5.2.0 which contains a rewrite of the Map and Set implementations, though I've only been able to test on v5.2.1 due to #502

[glompix]

Is this a reasonable expectation? My expectation is that Sets and Maps are unordered.

[chrissantamaria]

I originally thought that as well, though according to MDN Sets and Maps indeed should maintain order:

Set objects are collections of values. You can iterate through the elements of a set in insertion order.

imo this is something Immer should either try to adhere to or explicitly make a note of.

[fantasticsoul]

hey, bro, check this online example https://codesandbox.io/s/limu-case-3-b1i32w?file=/src/index.js it shows what you want ^_^

btw, limu is a faster immutable lib

[jdip]

I'm not sure this is an issue since immer doesn't guarantee "optimal" patches, but I found some weirdness with patch output that may be related to the problematic set replacement you found.

When you have a set inside of a set, and add to the deeper set, instead of a single patch reflecting the add to the deeper set, you get two patches, one removing the deeper set, and one adding it back with the new value appended.

   it("creates a single add op when adding to a set", () => {
        const originalSet = new Set(["a", "b"])

        const [newSet, patches,] = produceWithPatches(originalSet, draft => {
            draft.add("c")
        })

        const expectedResultingSet = new Set(["a", "b", "c"])
        
        // passes
        expect(newSet).to.deep.equal(expectedResultingSet)

        const expectedPatches = [{ op: "add", path: [2], value: "c" }]

        // passes
        expect(patches).to.deep.equal(expectedPatches)
    })

    it("creates a single add op when adding to a set inside a set", () => {
        const originalSetOfSets = new Set([
            new Set(["a", "b"]),
        ])


        const [newSetOfSets, patches,] = produceWithPatches(originalSetOfSets, draft => {
            [...draft][0].add("c")
        })

        const expectedResultingSetOfSets = new Set([
            new Set(["a", "b", "c"]),
        ])

        // passes
        expect(newSetOfSets).to.deep.equal(expectedResultingSetOfSets)


        // Given the patch the previous test produced
        // I would expect this one to produce the following patch but it doesn't

        const expectedPatches = [{ op: "add", path: [0, 2], value: "c" }]

        // fails
        expect(patches).to.deep.equal(expectedPatches)

        /* Actual patches produced
            [
                { op: "remove", path: [0], value: Set(["a", "b"]) },
                { op: "add", path: [0], value: Set(["a", "b", "c"]) }
            ]
        */
    })

[github-actions[bot]]

:tada: This issue has been resolved in version 9.0.18 :tada:

The release is available on:

• npm package (@latest dist-tag)
• GitHub release

Your semantic-release bot :package::rocket: