Infinite loop when both arguments have cycles

[justinfagnani]

If both arguments have cycles, like if you're trying to compare doubly-linked lists, dequal goes into an infinite loop.

repro:

const a: any = {}, b: any = {};
a.next = b;
b.previous = a;

const c: any = {}, d: any = {};
c.next = d;
d.previous = c;

dequal(a, c);

[caijinyc]

I have the same problem.

[yuri-scarbaci-lenio]

I think this also effect me in React

 <StyledReferenceElement ref={setReferenceElement}>
        I am the reference element
        <SomeComponent referenceElement={referenceElement}>
            <div>hello<div>
        </SomeComponent>
 </StyledReferenceElement>

SomeComponent ---> using dequal for comparing changes to the props

[yuri-scarbaci-lenio]

The exact same implementation (on my side) done using 'fast-deep-equal/react' instead works without hiccups/infinite-loops

from 'fast-deep-equal' library

To use with React (avoiding the traversal of React elements' _owner property that contains circular references and is not needed when comparing the elements - borrowed from react-fast-compare):

Probably we need a /react version of dequal that implements this too?

[justinfagnani]

You shouldn't need React-specific libraries for deep equals. Just a visited object set to keep from entering cycles.

[yuri-scarbaci-lenio]

You shouldn't need React-specific libraries for deep equals. Just a visited object set to keep from entering cycles.

strictly speaking, yes, I should not "need" it

but my point is,

the best part of dequal is that it's faster than other deep equality checks libraries.

I wonder if that still stands true in a react context where other libraries have "per react" optimisation, would that optimisation result in a faster algorithm vs the generic "dequal for all context" implementation?

react is "big enough" to be worthy a "dequal/react" with the per-react optimisation imho, or at the very least considering the idea at all...

[lukeed]

I may add a dequal/circular mode so that users opt into the added checks only when necessary. While my use case is certainly not everyone's use case, I've never run into this IRL because generally I avoid circular references, especially in something like a UI Component's state, where "is expensive-X the same as expensive-Y" comes up.

Offering it as a module means that it's an easy import (or import alias) away. There'd be no API changes. Would be the same pattern as dequal vs dequal/lite now.

Also, re: React. @justinfagnani is right here; there definitely should not be a React-specific offering here. A solution for all circulars is a solution for React. But on that note, fast-deep-equal/react might not do what you think @yuri-scarbaci-lenio ... it just skips/avoids the problem.

[yuri-scarbaci-lenio]

Ty for sharing the link

this actually does what I think it does, skipping the whole key === '_owner' check, this "skip" make sense in a react context, and this would effectively enhance the performance in a react context, because the whole key === '_owner' object can be skipped without any issues

checking it in a way that doesn't breaks (as I understand you are planning for dequal/circular ) would still work, but not skipping this particular circular dependency (whose equality check is never expected to be deep-ly done via compare in a react context, as per general consenus, it's something used by the tree-structure of the react renderer and developers should not rely on it from the start, it's not officially avaiable for using in react, any implementation relying on it is kind of an hack and should be avoided because the owner key may be subject to change if react renderer wants to optimize the tree-model internally...) is effectively making the overall process slower, because, of course, you don't skip it...

in the end, I would understand why you would be against the idea of adding a module dequal/react, it would add edge-cases you never intended to provide support to, and I understand the idea behind this lib is to be really vanilla-javascript oriented and un-opinionated...

But I also see why fast-deep-equal/react provided the "skip of the comparison" in their dedicated version...

I may add a dequal/circular ... Offering it as a module means that it's an easy import (or import alias) away. There'd be no API changes. Would be the same pattern as dequal vs dequal/lite now.

would that implies you will also have the permutations? as in

• dequal
• dequal/lite
• dequal/circular
• dequal/lite-circular

... I've never run into this IRL because generally I avoid circular references ...

I generally stand on your same ground on this, but sometimes we are forced by third-party choices to implement circular references, this is my case with a really specific implementation in react of popper-js which requires me to send over the DOM reference to the element containing my trigger and my popper content, this coupled with the react key === '_owner' receiving the parent DOM node, there I have the circular DOM dependency...

[yuri-scarbaci-lenio]

Also, just because I happened to notice this https://github.com/storybookjs/storybook/pull/12451

and since storybook is not as un-opinionated (as in storybook is actually widely used in react-environments, so much so infact that their homepage -> docs link brings you to a "storybook for react" documentation page), probably could lead to someone else providing a similar performance enhancer PR switching from your (in the near future) merged dequal with fast-deep-equal/react if what I suspect ( fast-deep-equal/react being faster than dequal/circular when dealing with react) stands true...

[lukeed]

Don't quite have the bandwidth to get into everything you brought up right now, but I will later. For now:

would that implies you will also have the permutations?

It would just be dequal, dequal/lite, and dequal/circular. Initially, I almost broke out a dequal/json (supports less than /lite), but IIRC it was only about 80b smaller and not mega-significantly faster than dequal/lite on its own.

I know this might seem unrelated, but it's to say that I don't think of these as "permutations" – instead, they're expanding scopes/feature sets. The scope coverage depends on the size of the umbrella you pick.

Supporting circular references already implies complex objects, which needs to include dequal by default anyway, and so Circulars is an additive, opt-in feature to that.

[Hexagon]

I have experienced this in real life, while testing a deep cloning library which handles circular references, using uvu.

Created an issue in uvu

https://github.com/lukeed/uvu/issues/203

I'm working on modernising my library 'klon', to include it in another library. This work includes replacing mocha and should with uvu (which is way more bang for the buck:) )

https://github.com/Hexagon/klon

I also stumbled upon this issue

https://github.com/lukeed/uvu/issues/202