deepEqual should not infinitely recurse an infinite lazy getter chain

[Turbo87]

Tell us about your runtime:

• QUnit version: 2.7.1
• What environment are you running QUnit in? (e.g., browser, Node): Browser
• How are you running QUnit? (e.g., script, testem, Grunt): Script

What are you trying to do?

Code that reproduces the problem:

https://jsfiddle.net/bzomqak8/11/

class Foo {
  constructor(a = 1) {
    this.a = a;
  }
}

Object.defineProperty(Foo.prototype, 'b', {
  enumerable: true,
  get() {
    return new Foo(this.a + 1);
  }
})

QUnit.test("hello test", function(assert) {
  assert.deepEqual(new Foo(), new Foo());
});

If you have any relevant configuration information, please include that here:

What did you expect to happen?

I expected QUnit to not compare computed properties.

What actually happened?

QUnit compares computed properties by using a for..in loop which (due to BFS) recurses infinitely without ever hitting a stack limit.

This is a minimal reproduction extracted from one of our Ember apps. In the actual app we use an Ember.Object and a computed property instead of the code above, but the effect is the same.

[rwjblue]

Should be fixed by #1326.

[Krinkle]

Per https://github.com/qunitjs/qunit/pull/1326, I don't think is is feasible for QUnit to solve the problem of predicting whether infinite getter chains will be considered equivalent by some definition. @gibson042 pointed there to https://github.com/qunitjs/qunit/issues/1327, and indeed an QUnit assertion plugin could work here.

Having said that, I do think that this ticket still represents a bug we should solve. Namely that QUnit should not infinitely recurse or timeout without some meaningful feedback.

Two ideas come to mind, not mutually exclusive:

1. Limit the depth deepEqual/equiv will traverse. For example, we could set it to 1000 (configurable) and stop if the structure is deeper than that, displaying an error.
2. Detect the use of property getters, and stop if the same getter is encountered N times within the same traversal stack, displaying an error.

[Krinkle]

For comparison to Node.js, the following passes on Node.js 10 and Node.js 16:

class Foo {
    constructor(a = 1) {
        this.a = a;
    }
}

Object.defineProperty(Foo.prototype, 'b', {
    enumerable: true,
    get() {
        return new Foo(Math.random());
    }
});

const assert = require('assert');

assert.deepEqual(new Foo(), new Foo());

[gibson042]

Sure, but Node.js assert.deepEqual also ignores prototypes (among many other differences between it and QUnit). They also document comparison details, although this particular detail seems to be absent. But regardless, I guess adding an operational theory to our documentation would be the first step for addressing both this and #1327.

[Krinkle]

Counter-example, unaffected by the lack of prototype comparison in Node.js' assert module:

Ostensibly equal (non-random):

class Foo {
    constructor(a = 1) {
        this.a = a;
        Object.defineProperty(this, 'b', {
            enumerable: true,
            get() {
                return new Foo(a + 1);
            }
        });
    }
}

const assert = require('assert');
assert.deepEqual(new Foo(), new Foo());

node:internal/util/comparisons:556
function objEquiv(a, b, strict, keys, memos, iterationType) {
                 ^
RangeError: Maximum call stack size exceeded
    at objEquiv (node:internal/util/comparisons:556:18)
    at keyCheck (node:internal/util/comparisons:371:17)
    at innerDeepEqual (node:internal/util/comparisons:183:12)
    at objEquiv (node:internal/util/comparisons:560:12)
    at keyCheck (node:internal/util/comparisons:371:17)
    at innerDeepEqual (node:internal/util/comparisons:183:12)
    at objEquiv (node:internal/util/comparisons:560:12)
    at keyCheck (node:internal/util/comparisons:371:17)
    at innerDeepEqual (node:internal/util/comparisons:183:12)
    at objEquiv (node:internal/util/comparisons:560:12)

Node.js v21.1.0

Ostensibly non-equal (random):

class Foo {
    constructor(a = 1) {
        this.a = a;
        Object.defineProperty(this, 'b', {
            enumerable: true,
            get() {
                return new Foo(Math.random());
            }
        });
    }
}

const assert = require('assert');
assert.deepEqual(new Foo(), new Foo());

node:assert:125
  throw new AssertionError(obj);
  ^

AssertionError [ERR_ASSERTION]: Expected values to be loosely deep-equal:
Foo {
    a: 1,
    b: [Getter] Foo {
      a: 0.9591963333045572,
      b: [Getter] Foo {
        a: 0.77349...

should loosely deep-equal

Foo {
    a: 1,
    b: [Getter] Foo {
      a: 0.8048445179986612,
      b: [Getter] Foo {
        a: 0.5683552614371483,
        b: [Getter] Foo {
          a: 0.28933585686210317,
          b: [Getter] Foo {
            a: 0.1394501891286133,
            b: [Getter] Foo {
              a: 0.39536226381580586,
              b: [Getter] Foo {
                a: 0.861707878353112,
                b: [Getter] Foo {
                  a: 0.5315356486179443,
                  b: [Getter] Foo {
               ...

at Module._compile (node:internal/modules/cjs/loader:1376:14)
at Module._extensions..js (node:internal/modules/cjs/loader:1435:10)
at Module.load (node:internal/modules/cjs/loader:1207:32)
at Module._load (node:internal/modules/cjs/loader:1023:12)
at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:135:12)
at node:internal/main/run_main_module:28:49 {
  generatedMessage: true,
  code: 'ERR_ASSERTION',
  actual: Foo { a: 1, b: [Getter] },
  expected: Foo { a: 1, b: [Getter] },
  operator: 'deepEqual'
}

Node.js v21.1.0