deep-equal-ident - npm Package Compare versions

Comparing version 0.0.1 to 0.0.2

package.json

		{
		"name": "deep-equal-ident",
		"version": "0.0.1",
		"version": "0.0.2",
		"description": "A function to test for identical deep equality (based on lodash's isEqual).",
		@@ -5,0 +5,0 @@ "main": "index.js",

164

README.md

		@@ -1,6 +0,3 @@
		deep-equal-ident
		================
		##Deep comparison with object identity checks

		Deep comparison with object identity checks.

		This function performs a deep comparison between the two values `a` and `b`. It
		@@ -10,5 +7,5 @@ has the same signature and functionality as [lodash's isEqual function](http://lodash.com/docs#isEqual),

		---
		This function is intended to be used for unit tests.

		Example:
		### So, what is this really about?

		@@ -19,10 +16,13 @@ Most deep equality tests (including `_.isEqual`) consider the following
		```javascript
		var a = [1,2,3];
		var x = [1,2,3];
		var y = [1,2,3];
		var foo = [a, a];
		var bar = [[1,2,3], [1,2,3]]
		var bar = [a, b];
		_.isEqual(foo , bar): // => true
		```

		However, it should be obvious that `foo` contains two reference to the same
		object whereas `bar` contains two different (not identical) objects.
		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.

		@@ -45,5 +45,145 @@ `deepEqualIdent` will consider these values as not equal:

		### Why does it matter?

		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`.

		---

		This function should primarily be used in unit tests. A chai extension will
		follow.
		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.

		### OK, so how did you implement it?

		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, '__<random prop>__', {value: b});
		Object.defineProperty(b, '__<random prop>__', {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.

		#### Alternatively: Maps

		The solution to the immutability and performance problems could be ES6 `Map`s,
		once they are supported by Node.js (and other engines) by default.

		---

		### Installation

		npm install deep-equal-ident

		and use it as

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

		### Run tests

		npm test

deep-equal-ident - npm Package Compare versions

New alerts

Fixed alerts

Improved metrics