assert: add support for Map and Set in deepEqual

assert.deepEqual and assert.deepStrictEqual currently return true for
any pair of Maps and Sets regardless of content. This patch adds
support in deepEqual and deepStrictEqual to verify the contents of Maps
and Sets.

Deeo equivalence checking is currently an
O(n^2) operation, and worse, it gets slower exponentially if maps
and sets were nested.

Note that this change breaks compatibility with previous versions of
deepEqual and deepStrictEqual if consumers were depending on all maps
and sets to be seen as equivalent. The old behaviour was never
documented, but nevertheless there are certainly some tests out there
which depend on it.

Support has stalled because the assert API was frozen, but was recently
unfrozen in CTC#63.

---

Later squashed in:

This change updates the checks for deep equality checking on Map and Set
to check all set values / all map keys to see if any of them match the
expected result.

This change is much slower, but based on the conversation in the pull
request its probably the right approach.

Fixes: https://github.com/nodejs/node/issues/2309
Refs: https://github.com/substack/tape/issues/342
Refs: https://github.com/nodejs/node/pull/2315
Refs: https://github.com/nodejs/CTC/issues/63
PR-URL: https://github.com/nodejs/node/pull/12142
Reviewed-By: Anna Henningsen <anna@addaleax.net>
Reviewed-By: Rich Trott <rtrott@gmail.com>
Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
Reviewed-By: Joyee Cheung <joyeec9h3@gmail.com>

1 files changed, 110 insertions, 1 deletions

diff --git a/lib/assert.js b/lib/assert.js
index df575c0f16..303a00e8ae 100644
--- a/lib/assert.js
+++ b/lib/assert.js
@@ -23,6 +23,7 @@
 // UTILITY
 const compare = process.binding('buffer').compare;
 const util = require('util');
+const { isSet, isMap } = process.binding('util');
 const objectToString = require('internal/util').objectToString;
 const Buffer = require('buffer').Buffer;
 
@@ -262,11 +263,12 @@ function _deepEqual(actual, expected, strict, memos) {
     }
   }
 
-  // For all other Object pairs, including Array objects,
+  // For all other Object pairs, including Array objects and Maps,
   // equivalence is determined by having:
   // a) The same number of owned enumerable properties
   // b) The same set of keys/indexes (although not necessarily the same order)
   // c) Equivalent values for every corresponding key/index
+  // d) For Sets and Maps, equal contents
   // Note: this accounts for both named and indexed properties on Arrays.
 
   // Use memos to handle cycles.
@@ -283,6 +285,97 @@ function _deepEqual(actual, expected, strict, memos) {
   return objEquiv(actual, expected, strict, memos);
 }
 
+function setHasSimilarElement(set, val1, strict, memo) {
+  if (set.has(val1))
+    return true;
+
+  // In strict mode the only things which can match a primitive or a function
+  // will already be detected by set.has(val1).
+  if (strict && (util.isPrimitive(val1) || util.isFunction(val1)))
+    return false;
+
+  // Otherwise go looking.
+  for (const val2 of set) {
+    if (_deepEqual(val1, val2, strict, memo))
+      return true;
+  }
+
+  return false;
+}
+
+function setEquiv(a, b, strict, memo) {
+  // This code currently returns false for this pair of sets:
+  //   assert.deepEqual(new Set(['1', 1]), new Set([1]))
+  //
+  // In theory, all the items in the first set have a corresponding == value in
+  // the second set, but the sets have different sizes. Its a silly case,
+  // and more evidence that deepStrictEqual should always be preferred over
+  // deepEqual.
+  if (a.size !== b.size)
+    return false;
+
+  for (const val1 of a) {
+    // If the value doesn't exist in the second set by reference, and its an
+    // object or an array we'll need to go hunting for something thats
+    // deep-equal to it. Note that this is O(n^2) complexity, and will get
+    // slower if large, very similar sets / maps are nested inside.
+    // Unfortunately there's no real way around this.
+    if (!setHasSimilarElement(b, val1, strict, memo)) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+function mapHasSimilarEntry(map, key1, item1, strict, memo) {
+  // To be able to handle cases like:
+  //   Map([[1, 'a'], ['1', 'b']]) vs Map([['1', 'a'], [1, 'b']])
+  // or:
+  //   Map([[{}, 'a'], [{}, 'b']]) vs Map([[{}, 'b'], [{}, 'a']])
+  // ... we need to consider *all* matching keys, not just the first we find.
+
+  // This check is not strictly necessary. The loop performs this check, but
+  // doing it here improves performance of the common case when reference-equal
+  // keys exist (which includes all primitive-valued keys).
+  if (map.has(key1) && _deepEqual(item1, map.get(key1), strict, memo))
+    return true;
+
+  if (strict && (util.isPrimitive(key1) || util.isFunction(key1)))
+    return false;
+
+  for (const [key2, item2] of map) {
+    // This case is checked above.
+    if (key2 === key1)
+      continue;
+
+    if (_deepEqual(key1, key2, strict, memo) &&
+        _deepEqual(item1, item2, strict, memo)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+function mapEquiv(a, b, strict, memo) {
+  // Caveat: In non-strict mode, this implementation does not handle cases
+  // where maps contain two equivalent-but-not-reference-equal keys.
+  //
+  // For example, maps like this are currently considered not equivalent:
+  if (a.size !== b.size)
+    return false;
+
+  for (const [key1, item1] of a) {
+    // Just like setEquiv above, this hunt makes this function O(n^2) when
+    // using objects and lists as keys
+    if (!mapHasSimilarEntry(b, key1, item1, strict, memo))
+      return false;
+  }
+
+  return true;
+}
+
 function objEquiv(a, b, strict, actualVisitedObjects) {
   // If one of them is a primitive, the other must be the same.
   if (util.isPrimitive(a) || util.isPrimitive(b))
@@ -307,6 +400,22 @@ function objEquiv(a, b, strict, actualVisitedObjects) {
       return false;
   }
 
+  // Sets and maps don't have their entries accessible via normal object
+  // properties.
+  if (isSet(a)) {
+    if (!isSet(b) || !setEquiv(a, b, strict, actualVisitedObjects))
+      return false;
+  } else if (isSet(b)) {
+    return false;
+  }
+
+  if (isMap(a)) {
+    if (!isMap(b) || !mapEquiv(a, b, strict, actualVisitedObjects))
+      return false;
+  } else if (isMap(b)) {
+    return false;
+  }
+
   // The pair must have equivalent values for every corresponding key.
   // Possibly expensive deep test:
   for (i = aKeys.length - 1; i >= 0; i--) {