deepStrictEqual fails for Sets that contain both object references and equivalent object values

[chharvey]

Version

v20.0.0

Platform

Darwin MacBookPro2019.local 22.6.0 Darwin Kernel Version 22.6.0: Wed Oct 4 21:25:26 PDT 2023; root:xnu-8796.141.3.701.17~4/RELEASE_X86_64 x86_64

Subsystem

No response

What steps will reproduce the bug?

Run the following JavaScript in Node v20:

const x = ['x'];
assert.deepStrictEqual(new Set([x, ['y']]), new Set([x, ['y']])); // AssertionError

An AssertionError is reported, which is unexpected.

How often does it reproduce? Is there a required condition?

It is reproducible 100% of the time. It is not reproducible in v18.20.2, but reproducible starting in v20. No required condition.

What is the expected behavior? Why is that the expected behavior?

The expected behavior is that the assertion should pass. Both sets contain a reference to x (reference-equal) and also a new object ['y'] (deep-equal), so the sets should be deeply equal.

What do you see instead?

An assertion error is reported:

AssertionError [ERR_ASSERTION]: Values have same structure but are not reference-equal:

Set(2) {
  [
    'x'
  ],
  [
    'y'
  ]
}

Additional information

The bug occurs only when comparing Set objects, with a mix of elements where some elements are objects compared by reference (===) and other elements are objects compared by deep equality.

I believe it was introduced by #46593. Looking at the changed code, a new "SafeSet" is created only containing the values (of type 'object') in a that are not in b. So this SafeSet only contains ['y']. But then on line 468 of comparisons.js, for (const val of b), every value of b is checked, including the reference x, which causes the failure because the SafeSet does not contain it.

[lemire]

I have verified that the issue does not occur with Node 18 and yet it occurs systematically with Node 20 and up.

[lemire]

@chharvey Please review #53431

[DanielBelz1997]

it seems like it has somthing to do with x being an array saved in constant. example:

const x = ["x"];

const a = new Set([x, ["y"]]);
const b = new Set([x, ["y"]]);

assert.deepStrictEqual(a, b); // AssertionError

but:

const a = new Set([["x"], ["y"]]);
const b = new Set([["x"], ["y"]]);

assert.deepStrictEqual(a, b); // null

can i work on this?

[lemire]

can i work on this?

Yes!!! Have a look at #53431

[chharvey]

@DanielBelz1997 Yup, your analysis is correct. Take a look at the setEquiv function here.

Starting on line 447, a new "SafeSet" is created that contains all the values in a that are not in b (as determined by b.has(), whch checks by reference). When you create a reference const x = ['x'], it doesn’t get put into that SafeSet since it’s in both sets. Whereas a newly constructed object would be put in since it can’t be in both sets.

The bug lies on line 468, where we loop over the values in b. Since the reference x is in b but not in the SafeSet, the call on line 471, setHasEqualElement(‹SafeSet›, ‹x›, ...), fails. In your second example you have no references, so all the values in a get put into that SafeSet when it’s created. Then when we loop over b, the call setHasEqualElement(...) passes for all those values.

[DanielBelz1997]

@chharvey thank you for the direction! I will get on that as soon as possible.

[BridgeAR]

This is a great catch! The bug seems to only occur for sets where both contain a reference identical object and another non-reference identical object.

To fix it, it should be enough to add a check here to verify the reference identical one does not exist in the other set

node/lib/internal/util/comparisons.js

Line 505 in 1839eb2

if (!setHasEqualElement(set, val, strict, memo))

        if (!a.has(val) && !setHasEqualElement(set, val, strict, memo))

An alternative would be to undo some of the set changes from #46593. It was not an issue before due to always adding all objects to the intermediate set.

I would just run the benchmark on both options and see what has less impact.

[lemire]

@BridgeAR I have added your simple fix to #53431