deep-equal-ident

Deep comparison with object identity checks 

This function performs a deep comparison between the two values a and b. It
has the same signature and functionality as lodash's isEqual function,
with one difference: It also tracks the identity of nested objects.

This function is intended to be used for unit tests (see below how to use it
with chai.js).

$3

npm install -S deep-equal-ident

and use it as

``javascript
var deepEqualIdent = require('deep-equal-ident');
// ...
if (deepEqualIdent(foo, bar)) {
// deep equal
}
`

$3

This module provides integration with the chai.js assertion framework
(for Node.js at least).
Enable the extensions with

chai.use(require('deep-equal-ident/chai'));

Then you can use either the expect or assert interface:

`javascript
// expect
expect(foo).to.deep.identically.equal(bar);
expect(foo).to.identically.equal(bar);

// assert
assert.deepEqualIdent(foo, bar);
assert.NotDeepEqualIdent(foo, bar);
`

---

$3

Most deep equality tests (including _.isEqual) consider the following
structures as equal:

`javascript
var a = [1,2,3];
var b = [1,2,3];
var foo = [a, a];
var bar = [a, b];
_.isEqual(foo , bar): // => true
`

Here, foo contains two reference to the same object, but bar contains
references to two different (not identical) objects. a and b might be itself
considered as equal (they do after all contain the same values), but the
structures of foo and bar are different.

deepEqualIdent will consider these values as not equal:

`javascript
deepEqualIdent(foo, bar); // => false
`

The following slightly different structures would be considered equal:

`javascript
var a = [1,2,3];
var b = [1,2,3];
var foo = [a, a];
var bar = [b, b];
deepEqualIdent(foo, bar); // => true
`

$3

Let's have a look at another procedure to answer that question: deep cloning.
Given

`javascript
var a = [1,2,3];
var foo = [a, a];
`

a good deep cloning algorithm would recognize that both elements in foo
refer to the same object and thus would create a single copy of a:

`javascript
var a_copy = [1,2,3];
var foo_copy = [a_copy, a_copy];
`

This is desired because we want foo_copy behave exactly like foo when we
process it. I.e. if the first element is mutated, the second element should
mutate as well:

`javascript
foo_copy[0][0] += 1;
console.log(foo_copy); // => [[2,2,3], [2,2,3]]
`

If the deep copy algorithm would produce separate copies for each element in foo
instead

`javascript
var a_copy_1 = [1,2,3];
var a_copy_2 = [1,2,3];
var foo_copy = [a_copy_1, a_copy_2];
`

then mutating the first element of foo_copy would not produce the same result
as mutation the first element of foo, and thus it would not be an exact copy
of foo.

---

I hope this makes it clearer why considering the identity of objects during
comparison is important: To preserve the structural integrity. If two nested
structures are said to be equal, they should behave exactly the same for all
intends and purposes.

Another way to look at it is to visualize the relationship between the values as
graphs. Let's change the structure a bit:

`javascript
var a = [1,2,3];
var b = [1,2,3];
var foo = [a, {x: a}];
var bar = [a, {x: b}];
`

Graph representations:

`
- foo - - bar -
| | | |
v v v v
a <--- { } a { }
|
v
b
`

I think this makes it very obvious that the structure of foo and bar are
different and thus would produce different results when processed.

$3

It's really straightforward. Just like with deep cloning, we have to keep
track of which objects we already encountered in a and associate it with the
corresponding value in b. Interestingly, deep cloning methods that can handle
cycles are already doing this, but only vertically, not horizontally. It shouldn't
be too much effort to modify them to support this out of the box.

There are a couple of ways to do it, each with its advantages and disadvantages.
I implemented two of them and choose to build them on top of lodash's isEqual
function, since it allows me to pass a callback and utilize all of the other
comparison logic that isEqual provides.

#### Tags

One way is to "tag" objects we have already seen and associate them with the
corresponding other object (creating some kind of bijective relationship). For
this I just added a new, not enumerable property to the object and setting the other
object as value, e.g.

`javascript
Object.defineProperty(a, '____', {value: b});
Object.defineProperty(b, '____', {value: a});
`

Now whenever we encounter an object (a1) that already has the property, we check
whether it has a reference to b1. We also have to check the other direction,
i.e. if b1 refers to a1. Overall this allows for the following outcomes:

- a1 and b1 not tagged: Not seen before => tag
- Either a1 or b1 not tagged: not equal
- a1 tagged but does not refer to b1: not equal
- b1 tagged but does not refer to a1: not equal

It's important to note that we can't detect equality. While the overall structure
might be the same, e.g. we have [a, a] and [b, b], a and b might still be
different. So we have to let the actual comparison algorithm determine equality
of these two values.

#### Stack

The previous solution has the advantage that determining the "not equality" is
quick, but it doesn't work for immutable objects. As alternative, we can push
each of the objects onto a stack and whenever we encounter another object, we
iterate over the stack and check whether it is already contained in the stack.
The result is the same as with tags.

The disadvantage is that performance decreases the more objects have to be
compared.

#### Maps

The solution to the immutability and performance problems could be ES6 Maps,
assuming they are supported they are supported by the environment this code
runs in.

An implementation using Maps is included and is used if global.Map is
available.

$3

deep-equal-ident incorrectly assumes the following structures to be
equal:

`javascript
var a = [[]];
var foo = [a, a[0]];
var bar = [a, []];
deepEqualIdent(foo, bar); // true
`

That's because lodash doesn't traverse deeper into the first element (because
foo[0] === bar[0], so the algorithm doesn't know about the objects inside
foo[0] (and bar[0]`) and therefore cannot detect whether they repeat
elsewhere in the data structure.