Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

deepEqual should not infinitely recurse an infinite lazy getter chain #1325

Open
Turbo87 opened this issue Oct 24, 2018 · 5 comments · May be fixed by #1326
Open

deepEqual should not infinitely recurse an infinite lazy getter chain #1325

Turbo87 opened this issue Oct 24, 2018 · 5 comments · May be fixed by #1326
Labels

Comments

@Turbo87
Copy link
Member

Turbo87 commented Oct 24, 2018

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
Copy link
Contributor

rwjblue commented Oct 24, 2018

Should be fixed by #1326.

@Krinkle Krinkle added Category: API Type: Bug Something isn't working right. Component: Assert labels Dec 22, 2018
@Krinkle Krinkle changed the title deepEqual goes into infinite recursion deepEqual should not infinitely recurse a getter-based lazy infinite chain Jun 27, 2020
@Krinkle Krinkle changed the title deepEqual should not infinitely recurse a getter-based lazy infinite chain deepEqual should not infinitely recurse an infinite lazy getter chain Jun 27, 2020
@Krinkle
Copy link
Member

Krinkle commented Jun 27, 2020

Per #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 #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
Copy link
Member

Krinkle commented Sep 19, 2021

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
Copy link
Member

gibson042 commented Sep 20, 2021

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
Copy link
Member

Krinkle commented Mar 3, 2024

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Development

Successfully merging a pull request may close this issue.

4 participants