possible issues with circular references

[jokeyrhyme]

I've checked with Node.js 0.12.0, and their assert.deepEqual() is able to compare objects with circular references, without running on forever or hitting stack limits.

var assert = require('assert');
var a = {}, b = {};
a.b = b; b.a = a;
assert.deepEqual(a, b);
// throws assertion

Node.js 0.10.36 throws:

TypeError: Converting circular structure to JSON

This isn't as good as actually performing some comparison, but at least it doesn't loop infinitely or anything.

The same thing in tape v3.5.0 with deep-equal v0.2.2 throws:

RangeError: Maximum call stack size exceeded

This might be more of a tape problem, but it actually throws instead of being caught as a failed assertion.

Would it be possible to at least have this return false in this sort of case?

Cheers. Love your work. :)

[kuraga]

👍

var deepEqual = require('deep-equal');

var a = { prop: 'val' };
a.special = a;
var b = { prop: 'val' };
b.special = b;

deepEqual(a, b, {strict: true});

node_modules/deep-equal/index.js:80
  ka.sort();
     ^
RangeError: Maximum call stack size exceeded

[kuraga]

@substack don't you know how to fix that?..

[jokeyrhyme]

@kuraga that's not a very helpful thing to suggest. If you are in urgent need for a fix, you could always submit a PR that includes the fix yourself, or find an alternative project that has the functionality you need.

[kuraga]

@jokeyrhyme you're right but maybe, do you (or Substack) know some approach to handle circular deps? I say about an advice not code...

[jokeyrhyme]

There's probably a better approach, but I would probably keep track the objects I have visited whilst traversing the structure. If I ever encounter the same object twice, then I would stop early.

Alternatively, a simpler approach could be to just have a maximum depth, stopping if traversal reaches a depth of maybe 50 or 100 (or some other reasonable number). This isn't a guarantee that the structure is circular, but would stop the stack errors.

[jokeyrhyme]

Also, I came across this, but I haven't tested it to see if it has the same problem: https://github.com/chaijs/deep-eql

[kuraga]

Thanks!

deep-eql hasn't an exception there but it returns a wrong result.

[kuraga]

Huh! NodeJS itself isn't exception, too! nodejs/node#6416

[kuraga]

Update: Solved in NodeJS, nodejs/node@d3aafd0

[jokeyrhyme]

This may or may not change again once we have tail call optimisation in v8.

[kuraga]

@jokeyrhyme what do you mean?

[jokeyrhyme]

It'll mean we might be able to adjust the algorithm to take advantage of tail calls, so we won't have stack overflow issues with deep recursion. Probably still don't want to have infinite loops, of course.

[kuraga]

Why NodeJS solution is not good?

[jokeyrhyme]

@kuraga it's probably fine, and possible the best. I'm just highlighting that we'll have new techniques available to us in the near future that may help for this sort of thing.

[ljharb]

The solution to this issue is to implement nodejs/node@d3aafd0, which will fix both this issue and tape-testing/tape#434.