`deepEqual` is incorrect when there are inherited properties

[jordanhendricks]

I used deepEqual to compare two objects with the same constructor, with the same arguments (which in this constructor, would result in the same keys on the instantiated object). To my surprise, deepEqual returned false for these objects.

The problem was that deepEqual saw a toString function on one object, but not the other. The toString function lives on the prototype chain of the constructor, and given that the objects had the same constructor, I would expect them to be the same.

The problem seems to be in this code:

...
	for (k in obj1) {
		if (!obj2.hasOwnProperty(k))
			return (false);
...

The for (k in obj1) loop will iterate over all keys on obj1 all the way up its prototype chain. But the next statement checks if a key is found on obj2 via hasOwnProperty, which only checks against keys on the bottom level of the chain. The set of keys being compared in these two objects is not the same.

Here is a simplified version of the program I ran that illustrates this issue:

var jsprim = require('jsprim');

function Foo(arg) {
    this.arg = arg;
};
Foo.prototype.toString = function toString() {
    return (this.args.toString());
}

function Bar(arg) {
    this.arg = arg;
};

var f1 = new Foo('foo');
var f2 = new Foo('foo');
var b1 = new Bar('bar');
var b2 = new Bar('bar');

console.log('f1 and f2 equal?: ', jsprim.deepEqual(f1, f2));
console.log('f1.toString and f2.toString equal?: ', jsprim.deepEqual(f1.toString,
    f2.toString));

console.log('b1 and b2 equal?: ', jsprim.deepEqual(b1, b2));

When run, this program outputs:

$ node deepequal-test.js
f1 and f2 equal?:  false
f1.toString and f2.toString equal?:  true
b1 and b2 equal?:  true

I think this can be fixed by iterating over the keys returned by Object.keys instead. The Object.keys method only returns an object's own enumerable properties, excluding those higher in the prototype chain. Given that deepEqual also checks that two objects were created with the same constructor, this is sufficient for verifying equality.

[davepacheco]

Thanks for debugging that. deepEqual was initially intended for plain objects, and it sounds like it doesn't handle various levels of properties on prototypes very well.

I think the first thing would be to decide what semantics we want: if two objects' own properties are identical, but properties along the prototype chain are different, do we want those to be deepEqual? I would think not. In that case, I don't think we want to check only the properties in Object.keys(). Maybe we want to use k in obj2 instead?

Also, just because two objects have the same constructor doesn't necessarily mean they have the same prototype chain, unfortunately.

[jordanhendricks]

@davepacheco thanks for replying. I would certainly expect that if the two objects' properties differ either in their own properties or those on the prototype chain, deepEqual would return false.

Could you give an example of an instance where having the same constructor results in a different prototype chain? It would be good to add something like that to the tests in this change (I have a CR in progress for it).

[jordanhendricks]

After some offline discussion, we decided the best way forward was to iterate over all own properties and inherited properties on each object using for (x in obj)... and checking for the existence of a property on an object using in.

CR is at: https://cr.joyent.us/2640.

Testing Notes
This change is make prepush clean. I added some additional test cases resembling the simplified test program. Additionally, I manually tested my original program that hit this bug with my change.

[davepacheco]

For the record, the reason we got to the result that deepEqual should cover the enumerable properties (both own and inherited) is that in general, and especially in the contexts in which this function is often used, it seems like consumers don't (and shouldn't) care where properties were specified -- only that they're specified on the object. For example, when using an args or options object as the argument to a function F (as we often do to provide named parameters), the caller G may have used one flat object, or it may have constructed an object whose prototype was passed to it, or use any complicated prototype chain it wants. After all that, when F looks at args, it doesn't care where the properties came from.

Put differently, if a consumer does care which object on the prototype chain provided the property, the prototype chain doesn't seem like a great data structure for that, since it doesn't provide a direct way to get that information.

[jordanhendricks]

Patchset 5 on the CR is the newest version. I repeated the testing notes above: make prepush and testing with my original program.