assert: improve deepEqual Set and Map worst case

This change improves the algorithm for the worst case from O(n^2)
to O(n log n) by using a lazily initiated set with object or
not strict equal primitives keys.

In addition a few comments got fixed and a statement simplified.

PR-URL: https://github.com/nodejs/node/pull/14258
Reviewed-By: Refael Ackermann <refack@gmail.com>

1 files changed, 170 insertions, 85 deletions

diff --git a/lib/assert.js b/lib/assert.js
index a948028501..e224118e1d 100644
--- a/lib/assert.js
+++ b/lib/assert.js
@@ -33,11 +33,6 @@ const errors = require('internal/errors');
 
 const assert = module.exports = ok;
 
-// At present only the three keys mentioned above are used and
-// understood by the spec. Implementations or sub modules can pass
-// other keys to the AssertionError's constructor - they will be
-// ignored.
-
 // All of the following functions must throw an AssertionError
 // when a corresponding condition is not met, with a message that
 // may be undefined if not provided. All assertion methods provide
@@ -120,9 +115,9 @@ function areSimilarRegExps(a, b) {
   return a.source === b.source && a.flags === b.flags;
 }
 
-// For small buffers it's faster to compare the buffer in a loop.
-// The c++ barrier takes the advantage of the faster compare otherwise.
-// 300 was the number after which compare became faster.
+// For small buffers it's faster to compare the buffer in a loop. The c++
+// barrier including the Buffer.from operation takes the advantage of the faster
+// compare otherwise. 300 was the number after which compare became faster.
 function areSimilarTypedArrays(a, b) {
   const len = a.byteLength;
   if (len !== b.byteLength) {
@@ -229,21 +224,15 @@ function looseDeepEqual(actual, expected) {
     return false;
   }
   if (util.isDate(actual) && util.isDate(expected)) {
-    if (actual.getTime() !== expected.getTime()) {
-      return false;
-    }
-    return true;
+    return actual.getTime() === expected.getTime();
   }
   if (util.isRegExp(actual) && util.isRegExp(expected)) {
-    if (!areSimilarRegExps(actual, expected)) {
-      return false;
-    }
-    return true;
+    return areSimilarRegExps(actual, expected);
   }
   const actualTag = objectToString(actual);
   const expectedTag = objectToString(expected);
   if (actualTag === expectedTag) {
-    if (!isFloatTypedArrayTag(actualTag) && !isObjectOrArrayTag(actualTag) &&
+    if (!isObjectOrArrayTag(actualTag) && !isFloatTypedArrayTag(actualTag) &&
       ArrayBuffer.isView(actual)) {
       return areSimilarTypedArrays(actual, expected);
     }
@@ -322,22 +311,12 @@ function innerDeepEqual(actual, expected, strict, memos) {
   return areEq;
 }
 
-function setHasSimilarElement(set, val1, usedEntries, strict, memo) {
-  if (set.has(val1)) {
-    if (usedEntries !== null)
-      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).
-  if (strict && (typeof val1 !== 'object' || val1 === null))
-    return false;
-
-  // Otherwise go looking.
+function setHasEqualElement(set, val1, strict, memo) {
+  // Go looking.
   for (const val2 of set) {
-    if (!usedEntries.has(val2) && innerDeepEqual(val1, val2, strict, memo)) {
-      usedEntries.add(val2);
+    if (innerDeepEqual(val1, val2, strict, memo)) {
+      // Remove the matching element to make sure we do not check that again.
+      set.delete(val2);
       return true;
     }
   }
@@ -345,6 +324,25 @@ function setHasSimilarElement(set, val1, usedEntries, strict, memo) {
   return false;
 }
 
+// Note: we actually run this multiple times for each loose key!
+// This is done to prevent slowing down the average case.
+function setHasLoosePrim(a, b, val) {
+  const altValues = findLooseMatchingPrimitives(val);
+  if (altValues === undefined)
+    return false;
+
+  var matches = 1;
+  for (var i = 0; i < altValues.length; i++) {
+    if (b.has(altValues[i])) {
+      matches--;
+    }
+    if (a.has(altValues[i])) {
+      matches++;
+    }
+  }
+  return matches === 0;
+}
+
 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]))
@@ -356,59 +354,124 @@ function setEquiv(a, b, strict, memo) {
   if (a.size !== b.size)
     return false;
 
-  // This is a set of the entries in b which have been consumed in our pairwise
-  // comparison.
-  //
+  // This is a lazily initiated Set of entries which have to be compared
+  // pairwise.
+  var set = null;
   // 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 = strict === true ? null : new Set();
-
-  for (const val1 of a) {
-    if (usedEntries === null && 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 (!setHasSimilarElement(b, val1, usedEntries, strict, memo))
+  // strict mode or if all entries strictly match, we don't need to match the
+  // entries in a pairwise way. In that case this initialization is done lazily
+  // to avoid the allocation & bookkeeping cost.
+  for (const val of a) {
+    // Note: Checking for the objects first improves the performance for object
+    // heavy sets but it is a minor slow down for primitives. As they are fast
+    // to check this improves the worst case scenario instead.
+    if (typeof val === 'object' && val !== null) {
+      if (set === null) {
+        set = new Set();
+      }
+      // If the specified value doesn't exist in the second set its an not null
+      // object (or non strict only: a not matching primitive) we'll need to go
+      // hunting for something thats deep-(strict-)equal to it. To make this
+      // O(n log n) complexity we have to copy these values in a new set first.
+      set.add(val);
+    } else if (!b.has(val) && (strict || !setHasLoosePrim(a, b, val))) {
       return false;
+    }
+  }
+
+  if (set !== null) {
+    for (const val of b) {
+      // In non-strict-mode we have to check if a primitive value is already
+      // matching and only if it's not, go hunting for it.
+      if (typeof val === 'object' && val !== null) {
+        if (!setHasEqualElement(set, val, strict, memo))
+          return false;
+      } else if (!a.has(val) && (strict || !setHasLoosePrim(b, a, val))) {
+        return false;
+      }
+    }
   }
 
   return true;
 }
 
-function mapHasSimilarEntry(map, key1, item1, usedEntries, 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.
+function findLooseMatchingPrimitives(prim) {
+  var values, number;
+  switch (typeof prim) {
+    case 'number':
+      values = ['' + prim];
+      if (prim === 1 || prim === 0)
+        values.push(Boolean(prim));
+      return values;
+    case 'string':
+      number = +prim;
+      if ('' + number === prim) {
+        values = [number];
+        if (number === 1 || number === 0)
+          values.push(Boolean(number));
+      }
+      return values;
+    case 'undefined':
+      return [null];
+    case 'object': // Only pass in null as object!
+      return [undefined];
+    case 'boolean':
+      number = +prim;
+      return [number, '' + number];
+  }
+}
 
-  // 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) && innerDeepEqual(item1, map.get(key1), strict, memo)) {
-    if (usedEntries !== null)
-      usedEntries.add(key1);
-    return true;
+// This is a ugly but relatively fast way to determine if a loose equal entry
+// actually has a correspondent matching entry. Otherwise checking for such
+// values would be way more expensive (O(n^2)).
+// Note: we actually run this multiple times for each loose key!
+// This is done to prevent slowing down the average case.
+function mapHasLoosePrim(a, b, key1, memo, item1, item2) {
+  const altKeys = findLooseMatchingPrimitives(key1);
+  if (altKeys === undefined)
+    return false;
+
+  const setA = new Set();
+  const setB = new Set();
+
+  var keyCount = 1;
+
+  setA.add(item1);
+  if (b.has(key1)) {
+    keyCount--;
+    setB.add(item2);
   }
 
-  if (strict && (typeof key1 !== 'object' || key1 === null))
+  for (var i = 0; i < altKeys.length; i++) {
+    const key2 = altKeys[i];
+    if (a.has(key2)) {
+      keyCount++;
+      setA.add(a.get(key2));
+    }
+    if (b.has(key2)) {
+      keyCount--;
+      setB.add(b.get(key2));
+    }
+  }
+  if (keyCount !== 0 || setA.size !== setB.size)
     return false;
 
-  for (const [key2, item2] of map) {
-    // The first part is checked above.
-    if (key2 === key1 || usedEntries.has(key2))
-      continue;
+  for (const val of setA) {
+    if (!setHasEqualElement(setB, val, false, memo))
+      return false;
+  }
+
+  return true;
+}
 
+function mapHasEqualEntry(set, map, key1, item1, strict, memo) {
+  // To be able to handle cases like:
+  //   Map([[{}, 'a'], [{}, 'b']]) vs Map([[{}, 'b'], [{}, 'a']])
+  // ... we need to consider *all* matching keys, not just the first we find.
+  for (const key2 of set) {
     if (innerDeepEqual(key1, key2, strict, memo) &&
-        innerDeepEqual(item1, item2, strict, memo)) {
-      usedEntries.add(key2);
+      innerDeepEqual(item1, map.get(key2), strict, memo)) {
+      set.delete(key2);
       return true;
     }
   }
@@ -419,21 +482,45 @@ function mapHasSimilarEntry(map, key1, item1, usedEntries, strict, memo) {
 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;
 
-  let usedEntries = strict === true ? null : new Set();
-
-  for (const [key, item] of a) {
-    if (usedEntries === null && typeof key === 'object')
-      usedEntries = new Set();
-
-    // Just like setEquiv above, this hunt makes this function O(n^2) when
-    // using objects and lists as keys
-    if (!mapHasSimilarEntry(b, key, item, usedEntries, strict, memo))
+  var set = null;
+
+  for (const [key, item1] of a) {
+    // By directly retrieving the value we prevent another b.has(key) check in
+    // almost all possible cases.
+    const item2 = b.get(key);
+    if (item2 === undefined) {
+      // Just like setEquiv above but in addition we have to make sure the
+      // values are also equal.
+      if (typeof key === 'object' && key !== null) {
+        if (set === null) {
+          set = new Set();
+        }
+        set.add(key);
+      // Note: we do not have to pass memo in this case as at least one item
+      // is undefined.
+      } else if ((!innerDeepEqual(item1, item2, strict) || !b.has(key)) &&
+        (strict || !mapHasLoosePrim(a, b, key, memo, item1))) {
+        return false;
+      }
+    } else if (!innerDeepEqual(item1, item2, strict, memo) &&
+      (strict || !mapHasLoosePrim(a, b, key, memo, item1, item2))) {
       return false;
+    }
+  }
+
+  if (set !== null) {
+    for (const [key, item] of b) {
+      if (typeof key === 'object' && key !== null) {
+        if (!mapHasEqualEntry(set, a, key, item, strict, memo))
+          return false;
+      } else if (!a.has(key) &&
+        (strict || !mapHasLoosePrim(b, a, key, memo, item))) {
+        return false;
+      }
+    }
   }
 
   return true;
@@ -445,12 +532,10 @@ function objEquiv(a, b, strict, keys, memos) {
   if (isSet(a)) {
     if (!isSet(b) || !setEquiv(a, b, strict, memos))
       return false;
-  } else if (isSet(b)) {
-    return false;
   } else if (isMap(a)) {
     if (!isMap(b) || !mapEquiv(a, b, strict, memos))
       return false;
-  } else if (isMap(b)) {
+  } else if (isSet(b) || isMap(b)) {
     return false;
   }