assert: Added and fixed more failing test cases comparing maps and sets

nodejs · josephg · Jun 3, 2017 · Jun 3, 2017 · Jun 3, 2017 · Jun 3, 2017
commit 957d61088b3ed7671920ed7f1bf59d35172da9c3
diff --git a/lib/assert.js b/lib/assert.js
@@ -286,8 +286,11 @@ function _deepEqual(actual, expected, strict, memos) {
 }
 
 function setHasSimilarElement(set, val1, usedEntries, strict, memo) {
-  if (set.has(val1))
+  if (set.has(val1)) {
+    if (usedEntries)
+      usedEntries.add(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).
@@ -321,22 +324,26 @@ function setEquiv(a, b, strict, memo) {
     return false;
 
   // This is a set of the entries in b which have been consumed in our pairwise
-  // comparison. Initialized lazily so sets which only have value types can
-  // skip an extra allocation.
+  // comparison.
+  //
+  // When the sets contain only value types (eg, lots of numbers), and we're in
+  // strict mode, we don't need to match off the entries in a pairwise way. In
+  // that case this initialization is done lazily to avoid the allocation &
+  // bookkeeping cost. Unfortunately, we can't get away with that in non-strict
+  // mode.
   let usedEntries = null;
 
   for (const val1 of a) {
+    if (usedEntries == null && (!strict || typeof val1 === 'object'))
+      usedEntries = new Set();
+
     // 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 (usedEntries == null && typeof val1 === 'object')
-      usedEntries = new Set();
-
-    if (!setHasSimilarElement(b, val1, usedEntries, strict, memo)) {
+    if (!setHasSimilarElement(b, val1, usedEntries, strict, memo))
       return false;
-    }
   }
 
   return true;
@@ -352,8 +359,11 @@ function mapHasSimilarEntry(map, key1, item1, usedEntries, strict, memo) {
   // 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))
+  if (map.has(key1) && _deepEqual(item1, map.get(key1), strict, memo)) {
+    if (usedEntries)
+      usedEntries.add(key1);
     return true;
+  }
 
   if (strict && (util.isPrimitive(key1) || util.isFunction(key1)))
     return false;
@@ -388,7 +398,7 @@ function mapEquiv(a, b, strict, memo) {
   let usedEntries = null;
 
   for (const [key1, item1] of a) {
-    if (usedEntries == null && typeof key1 === 'object')
+    if (usedEntries == null && (!strict || typeof key1 === 'object'))
       usedEntries = new Set();
 
     // Just like setEquiv above, this hunt makes this function O(n^2) when

diff --git a/test/parallel/test-assert-deep.js b/test/parallel/test-assert-deep.js
@@ -201,6 +201,14 @@ assertNotDeepOrStrict(
   new Map([[{x: 1}, 5], [{x: 2}, 5]])
 );
 
+assertNotDeepOrStrict(new Set([3, '3']), new Set([3, 4]));
+assertNotDeepOrStrict(new Map([[3, 0], ['3', 0]]), new Map([[3, 0], [4, 0]]));
+
+assertNotDeepOrStrict(
+  new Set([{a:1}, {a:1}, {a:2}]),
+  new Set([{a:1}, {a:2}, {a:2}])
+);
+
 // This is an awful case, where a map contains multiple equivalent keys:
 assertOnlyDeepEqual(
   new Map([[1, 'a'], ['1', 'b']]),