Deep equality utility takes very long for certain types of deeply nested objects

[yangshun]

Describe the bug

Not much to say here, Vitest just doesn't complete when I have a certain test case for an algo question, it hangs indefinitely.

No async operations involved.

I don't think it's a bug with my algo because I'm migrating from Jest which is able to successfully run all the test cases.

> jest "algo/graph-clone"

 PASS  algo/graph-clone/setup/src/graph-clone.test.ts

Test Suites: 2 passed, 2 total
Tests:       103 passed, 103 total
Snapshots:   0 total
Time:        1.786 s

With Vite it doesn't complete:

~/projects/vitejs-vite-jtzpyjuo 5s
❯ npm t

> [email protected] test
> vitest run


 RUN  v3.0.5 /home/projects/vitejs-vite-jtzpyjuo


 ❯ src/graph-clone.test.ts 0/8

 Test Files 0 passed (1)
      Tests 0 passed (8)
   Start at 08:44:17
   Duration 83.05s

Reproduction

https://stackblitz.com/edit/vitejs-vite-jtzpyjuo

This is a minimal repro with 8 test cases (tests.json). My original code has 100 test cases (tests.all.json).

If the last test case in tests.json is removed (L240-L384), the tests can complete.

System Info

❯ npx envinfo --system --npmPackages '{vitest*,@vitest/*,vite,@vitejs/*,playwright,webdriverio}' --binaries --browsers
Need to install the following packages:
[email protected]
Ok to proceed? (y) y

  System:
    OS: Linux 5.0 undefined
    CPU: (8) x64 Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
    Memory: 0 Bytes / 0 Bytes
    Shell: 1.0 - /bin/jsh
  Binaries:
    Node: 18.20.3 - /usr/local/bin/node
    Yarn: 1.22.19 - /usr/local/bin/yarn
    npm: 10.2.3 - /usr/local/bin/npm
    pnpm: 8.15.6 - /usr/local/bin/pnpm
  npmPackages:
    vite: ^6.0.11 => 6.0.11 
    vitest: ^3.0.5 => 3.0.5

Used Package Manager

npm

Validations

• Follow our Code of Conduct
• Read the Contributing Guidelines.
• Read the docs.
• Check that there isn't already an issue that reports the same bug to avoid creating a duplicate.
• Check that this is a concrete bug. For Q&A open a GitHub Discussion or join our Discord Chat Server.
• The provided reproduction is a minimal reproducible example of the bug.

[hi-ogawa]

Just in case, can you confirm it's not your algo getting stuck in while loop or recursion?

[hi-ogawa]

As explained in #1405, if synchronous code is taking over, then timeout doesn't kick in. You can try --disableConsoleIntercept + console.log("debug") to see if synchronous code is running in loop.

[yangshun]

Just in case, can you confirm it's not your algo getting stuck in while loop or recursion?

Yes it should not be, I am currently using Jest and it passes fine. I encountered the hanging issue while migrating to Vitest.

I did further debugging and narrowed down the issue to this line expect(clonedGraph).not.toBe(originalGraph). Commenting out this line will let the test end.

I suspect the implementation of the toBe assertion could be buggy.

[hi-ogawa]

I did further debugging and narrowed down the issue to this line expect(clonedGraph).not.toBe(originalGraph). Commenting out this line will let the test end.

I suspect the implementation of the toBe assertion could be buggy.

Okay, that's likely a bug of printing/diffing a cyclic object getting stuck in the loop.

[yangshun]

Thanks. As a workaround I've changed my code to expect(Object.is(clonedGraph, originalGraph)).toBe(false);

Updated StackBlitz repro to the minimal test case: https://stackblitz.com/edit/vitejs-vite-jtzpyjuo?file=src%2Fgraph.test.ts

[hi-ogawa]

I took a look and I'm not sure if we can say this is actually a bug. It appears that cyclic structure isn't necessary a cause, but Vitest's deep equality utility is too expensive for certain types of deeply nested objects. Interestingly, Node's assert.deepStrictEqual also exhibits similar behavior in terms of computational cost.

Here is one such structure, which shows exponential cost with respect to the number of graph nodes/edges
https://stackblitz.com/edit/vitejs-vite-5waxbkvr?file=src%2Frepro.test.ts

 ✓ src/repro.test.ts (20 tests) 3635ms
   ✓ expect().toEqual (20) 27ms
   ✓ expect().toEqual (21) 23ms
   ✓ expect().toEqual (22) 35ms
   ✓ expect().toEqual (23) 59ms
   ✓ expect().toEqual (24) 91ms
   ✓ expect().toEqual (25) 148ms
   ✓ expect().toEqual (26) 244ms
   ✓ expect().toEqual (27) 387ms
   ✓ expect().toEqual (28) 664ms
   ✓ expect().toEqual (29) 1018ms
   ✓ assert.deepStrictEqual (20) 6ms
   ✓ assert.deepStrictEqual (21) 8ms
   ✓ assert.deepStrictEqual (22) 13ms
   ✓ assert.deepStrictEqual (23) 20ms
   ✓ assert.deepStrictEqual (24) 32ms
   ✓ assert.deepStrictEqual (25) 54ms
   ✓ assert.deepStrictEqual (26) 85ms
   ✓ assert.deepStrictEqual (27) 139ms
   ✓ assert.deepStrictEqual (28) 222ms

The graph here is a fairly simple DAG with (number of nodes) = n, (number of edges) = 2n. For n = 6, it looks like this:

---

The above example uses toEqual, but something similar happens when using .not.toBe. Another thing worth noting is that two graphs are essentially same, so deep equality check cannot bail out early.

---

Speaking of large cyclic or nested structure, there is also a separate issue with error diff generation such as #7092. Mentioning it here just in case since that's technically a different part of the logic and error diff output might be something we can "heuristically" improve.

Let me remove a bug label for now. Fixing deep equality computation issue might not be possible to fix.

[yangshun]

@hi-ogawa Thanks for your hard work! Updated the title to reflect the issue better