assert: fix loose set and map comparison

The fast path did not anticipate different ways to express a loose
equal string value (e.g., 1n == '+0001'). This is now fixed with the
downside that all primitives that could theoretically have equal
entries must go through a full comparison.

Only some strings, symbols, undefined, null and NaN can be detected
in a fast path as those entries have a strictly limited set of
possible equal entries.

PR-URL: https://github.com/nodejs/node/pull/22495
Reviewed-By: Benjamin Gruenbaum <benjamingr@gmail.com>
Reviewed-By: Rich Trott <rtrott@gmail.com>
Reviewed-By: John-David Dalton <john.david.dalton@gmail.com>

1 files changed, 77 insertions, 104 deletions

diff --git a/lib/internal/util/comparisons.js b/lib/internal/util/comparisons.js
index 1cde5502ca..bcbe12181b 100644
--- a/lib/internal/util/comparisons.js
+++ b/lib/internal/util/comparisons.js
@@ -374,23 +374,52 @@ function setHasEqualElement(set, val1, strict, memo) {
   return false;
 }
 
-// Note: we currently 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;
+// See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness#Loose_equality_using
+// Sadly it is not possible to detect corresponding values properly in case the
+// type is a string, number, bigint or boolean. The reason is that those values
+// can match lots of different string values (e.g., 1n == '+00001').
+function findLooseMatchingPrimitives(prim) {
+  switch (typeof prim) {
+    case 'undefined':
+      return null;
+    case 'object': // Only pass in null as object!
+      return undefined;
+    case 'symbol':
+      return false;
+    case 'string':
+      prim = +prim;
+      // Loose equal entries exist only if the string is possible to convert to
+      // a regular number and not NaN.
+      // Fall through
+    case 'number':
+      if (Number.isNaN(prim)) {
+        return false;
+      }
+  }
+  return true;
+}
 
-  let matches = 1;
-  for (var i = 0; i < altValues.length; i++) {
-    if (b.has(altValues[i])) {
-      matches--;
-    }
-    if (a.has(altValues[i])) {
-      matches++;
-    }
+function setMightHaveLoosePrim(a, b, prim) {
+  const altValue = findLooseMatchingPrimitives(prim);
+  if (altValue != null)
+    return altValue;
+
+  return b.has(altValue) && !a.has(altValue);
+}
+
+function mapMightHaveLoosePrim(a, b, prim, item, memo) {
+  const altValue = findLooseMatchingPrimitives(prim);
+  if (altValue != null) {
+    return altValue;
+  }
+  const curB = b.get(altValue);
+  if (curB === undefined && !b.has(altValue) ||
+      !innerDeepEqual(item, curB, false, memo)) {
+    return false;
   }
-  return matches === 0;
+  const curA = a.get(altValue);
+  return curA === undefined && a.has(altValue) ||
+         innerDeepEqual(item, curA, false, memo);
 }
 
 function setEquiv(a, b, strict, memo) {
@@ -410,8 +439,19 @@ function setEquiv(a, b, strict, memo) {
       // 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;
+    } else if (!b.has(val)) {
+      if (strict)
+        return false;
+
+      // Fast path to detect missing string, symbol, undefined and null values.
+      if (!setMightHaveLoosePrim(a, b, val)) {
+        return false;
+      }
+
+      if (set === null) {
+        set = new Set();
+      }
+      set.add(val);
     }
   }
 
@@ -422,96 +462,18 @@ function setEquiv(a, b, strict, memo) {
       if (typeof val === 'object' && val !== null) {
         if (!setHasEqualElement(set, val, strict, memo))
           return false;
-      } else if (!a.has(val) && (strict || !setHasLoosePrim(b, a, val))) {
+      } else if (!strict &&
+                 !a.has(val) &&
+                 !setHasEqualElement(set, val, strict, memo)) {
         return false;
       }
     }
+    return set.size === 0;
   }
 
   return true;
 }
 
-// See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness#Loose_equality_using
-function findLooseMatchingPrimitives(prim) {
-  switch (typeof prim) {
-    case 'number':
-      if (prim === 0) {
-        return ['', '0', false];
-      }
-      if (prim === 1) {
-        return ['1', true];
-      }
-      return ['' + prim];
-    case 'string':
-      if (prim === '' || prim === '0') {
-        return [0, false];
-      }
-      if (prim === '1') {
-        return [1, true];
-      }
-      const number = +prim;
-      if ('' + number === prim) {
-        return [number];
-      }
-      return;
-    case 'undefined':
-      return [null];
-    case 'object': // Only pass in null as object!
-      return [undefined];
-    case 'boolean':
-      if (prim === false) {
-        return ['', '0', 0];
-      }
-      return ['1', 1];
-  }
-}
-
-// This is a ugly but relatively fast way to determine if a loose equal entry
-// currently has a correspondent matching entry. Otherwise checking for such
-// values would be way more expensive (O(n^2)).
-// Note: we currently 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();
-
-  let keyCount = 1;
-
-  setA.add(item1);
-  if (b.has(key1)) {
-    keyCount--;
-    setB.add(item2);
-  }
-
-  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 val of setA) {
-    if (typeof val === 'object' && val !== null) {
-      if (!setHasEqualElement(setB, val, false, memo))
-        return false;
-    } else if (!setB.has(val) && !setHasLoosePrim(setA, setB, val)) {
-      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']])
@@ -541,9 +503,17 @@ function mapEquiv(a, b, strict, memo) {
       // almost all possible cases.
       const item2 = b.get(key);
       if ((item2 === undefined && !b.has(key) ||
-        !innerDeepEqual(item1, item2, strict, memo)) &&
-        (strict || !mapHasLoosePrim(a, b, key, memo, item1, item2))) {
-        return false;
+          !innerDeepEqual(item1, item2, strict, memo))) {
+        if (strict)
+          return false;
+        // Fast path to detect missing string, symbol, undefined and null
+        // keys.
+        if (!mapMightHaveLoosePrim(a, b, key, item1, memo))
+          return false;
+        if (set === null) {
+          set = new Set();
+        }
+        set.add(key);
       }
     }
   }
@@ -553,11 +523,14 @@ function mapEquiv(a, b, strict, memo) {
       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))) {
+      } else if (!strict &&
+                 (!a.has(key) ||
+                   !innerDeepEqual(a.get(key), item, false, memo)) &&
+                 !mapHasEqualEntry(set, a, key, item, false, memo)) {
         return false;
       }
     }
+    return set.size === 0;
   }
 
   return true;