Skip to content

Commit be5e396

Browse files
BridgeARBridgeAR
committed
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: #22495 Reviewed-By: Benjamin Gruenbaum <[email protected]> Reviewed-By: Rich Trott <[email protected]> Reviewed-By: John-David Dalton <[email protected]>
1 parent 9be1555 commit be5e396

2 files changed

Lines changed: 81 additions & 108 deletions

File tree

‎lib/internal/util/comparisons.js‎

Lines changed: 77 additions & 104 deletions
Original file line numberDiff line numberDiff line change
@@ -374,23 +374,52 @@ function setHasEqualElement(set, val1, strict, memo) {
374374
return false;
375375
}
376376

377-
// Note: we currently run this multiple times for each loose key!
378-
// This is done to prevent slowing down the average case.
379-
function setHasLoosePrim(a, b, val) {
380-
const altValues = findLooseMatchingPrimitives(val);
381-
if (altValues === undefined)
382-
return false;
377+
// See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness#Loose_equality_using
378+
// Sadly it is not possible to detect corresponding values properly in case the
379+
// type is a string, number, bigint or boolean. The reason is that those values
380+
// can match lots of different string values (e.g., 1n == '+00001').
381+
function findLooseMatchingPrimitives(prim) {
382+
switch (typeof prim) {
383+
case 'undefined':
384+
return null;
385+
case 'object': // Only pass in null as object!
386+
return undefined;
387+
case 'symbol':
388+
return false;
389+
case 'string':
390+
prim = +prim;
391+
// Loose equal entries exist only if the string is possible to convert to
392+
// a regular number and not NaN.
393+
// Fall through
394+
case 'number':
395+
if (Number.isNaN(prim)) {
396+
return false;
397+
}
398+
}
399+
return true;
400+
}
383401

384-
let matches = 1;
385-
for (var i = 0; i < altValues.length; i++) {
386-
if (b.has(altValues[i])) {
387-
matches--;
388-
}
389-
if (a.has(altValues[i])) {
390-
matches++;
391-
}
402+
function setMightHaveLoosePrim(a, b, prim) {
403+
const altValue = findLooseMatchingPrimitives(prim);
404+
if (altValue != null)
405+
return altValue;
406+
407+
return b.has(altValue) && !a.has(altValue);
408+
}
409+
410+
function mapMightHaveLoosePrim(a, b, prim, item, memo) {
411+
const altValue = findLooseMatchingPrimitives(prim);
412+
if (altValue != null) {
413+
return altValue;
414+
}
415+
const curB = b.get(altValue);
416+
if (curB === undefined && !b.has(altValue) ||
417+
!innerDeepEqual(item, curB, false, memo)) {
418+
return false;
392419
}
393-
return matches === 0;
420+
const curA = a.get(altValue);
421+
return curA === undefined && a.has(altValue) ||
422+
innerDeepEqual(item, curA, false, memo);
394423
}
395424

396425
function setEquiv(a, b, strict, memo) {
@@ -410,8 +439,19 @@ function setEquiv(a, b, strict, memo) {
410439
// hunting for something thats deep-(strict-)equal to it. To make this
411440
// O(n log n) complexity we have to copy these values in a new set first.
412441
set.add(val);
413-
} else if (!b.has(val) && (strict || !setHasLoosePrim(a, b, val))) {
414-
return false;
442+
} else if (!b.has(val)) {
443+
if (strict)
444+
return false;
445+
446+
// Fast path to detect missing string, symbol, undefined and null values.
447+
if (!setMightHaveLoosePrim(a, b, val)) {
448+
return false;
449+
}
450+
451+
if (set === null) {
452+
set = new Set();
453+
}
454+
set.add(val);
415455
}
416456
}
417457

@@ -422,96 +462,18 @@ function setEquiv(a, b, strict, memo) {
422462
if (typeof val === 'object' && val !== null) {
423463
if (!setHasEqualElement(set, val, strict, memo))
424464
return false;
425-
} else if (!a.has(val) && (strict || !setHasLoosePrim(b, a, val))) {
465+
} else if (!strict &&
466+
!a.has(val) &&
467+
!setHasEqualElement(set, val, strict, memo)) {
426468
return false;
427469
}
428470
}
471+
return set.size === 0;
429472
}
430473

431474
return true;
432475
}
433476

434-
// See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness#Loose_equality_using
435-
function findLooseMatchingPrimitives(prim) {
436-
switch (typeof prim) {
437-
case 'number':
438-
if (prim === 0) {
439-
return ['', '0', false];
440-
}
441-
if (prim === 1) {
442-
return ['1', true];
443-
}
444-
return ['' + prim];
445-
case 'string':
446-
if (prim === '' || prim === '0') {
447-
return [0, false];
448-
}
449-
if (prim === '1') {
450-
return [1, true];
451-
}
452-
const number = +prim;
453-
if ('' + number === prim) {
454-
return [number];
455-
}
456-
return;
457-
case 'undefined':
458-
return [null];
459-
case 'object': // Only pass in null as object!
460-
return [undefined];
461-
case 'boolean':
462-
if (prim === false) {
463-
return ['', '0', 0];
464-
}
465-
return ['1', 1];
466-
}
467-
}
468-
469-
// This is a ugly but relatively fast way to determine if a loose equal entry
470-
// currently has a correspondent matching entry. Otherwise checking for such
471-
// values would be way more expensive (O(n^2)).
472-
// Note: we currently run this multiple times for each loose key!
473-
// This is done to prevent slowing down the average case.
474-
function mapHasLoosePrim(a, b, key1, memo, item1, item2) {
475-
const altKeys = findLooseMatchingPrimitives(key1);
476-
if (altKeys === undefined)
477-
return false;
478-
479-
const setA = new Set();
480-
const setB = new Set();
481-
482-
let keyCount = 1;
483-
484-
setA.add(item1);
485-
if (b.has(key1)) {
486-
keyCount--;
487-
setB.add(item2);
488-
}
489-
490-
for (var i = 0; i < altKeys.length; i++) {
491-
const key2 = altKeys[i];
492-
if (a.has(key2)) {
493-
keyCount++;
494-
setA.add(a.get(key2));
495-
}
496-
if (b.has(key2)) {
497-
keyCount--;
498-
setB.add(b.get(key2));
499-
}
500-
}
501-
if (keyCount !== 0 || setA.size !== setB.size)
502-
return false;
503-
504-
for (const val of setA) {
505-
if (typeof val === 'object' && val !== null) {
506-
if (!setHasEqualElement(setB, val, false, memo))
507-
return false;
508-
} else if (!setB.has(val) && !setHasLoosePrim(setA, setB, val)) {
509-
return false;
510-
}
511-
}
512-
return true;
513-
}
514-
515477
function mapHasEqualEntry(set, map, key1, item1, strict, memo) {
516478
// To be able to handle cases like:
517479
// Map([[{}, 'a'], [{}, 'b']]) vs Map([[{}, 'b'], [{}, 'a']])
@@ -541,9 +503,17 @@ function mapEquiv(a, b, strict, memo) {
541503
// almost all possible cases.
542504
const item2 = b.get(key);
543505
if ((item2 === undefined && !b.has(key) ||
544-
!innerDeepEqual(item1, item2, strict, memo)) &&
545-
(strict || !mapHasLoosePrim(a, b, key, memo, item1, item2))) {
546-
return false;
506+
!innerDeepEqual(item1, item2, strict, memo))) {
507+
if (strict)
508+
return false;
509+
// Fast path to detect missing string, symbol, undefined and null
510+
// keys.
511+
if (!mapMightHaveLoosePrim(a, b, key, item1, memo))
512+
return false;
513+
if (set === null) {
514+
set = new Set();
515+
}
516+
set.add(key);
547517
}
548518
}
549519
}
@@ -553,11 +523,14 @@ function mapEquiv(a, b, strict, memo) {
553523
if (typeof key === 'object' && key !== null) {
554524
if (!mapHasEqualEntry(set, a, key, item, strict, memo))
555525
return false;
556-
} else if (!a.has(key) &&
557-
(strict || !mapHasLoosePrim(b, a, key, memo, item))) {
526+
} else if (!strict &&
527+
(!a.has(key) ||
528+
!innerDeepEqual(a.get(key), item, false, memo)) &&
529+
!mapHasEqualEntry(set, a, key, item, false, memo)) {
558530
return false;
559531
}
560532
}
533+
return set.size === 0;
561534
}
562535

563536
return true;

‎test/parallel/test-assert-deep.js‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -369,13 +369,13 @@ assertDeepAndStrictEqual(
369369
new Map([[null, 3]])
370370
);
371371
assertOnlyDeepEqual(
372-
new Map([[null, undefined]]),
373-
new Map([[undefined, null]])
372+
new Map([[undefined, null], ['+000', 2n]]),
373+
new Map([[null, undefined], [false, '2']]),
374374
);
375375

376376
assertOnlyDeepEqual(
377-
new Set([null, '']),
378-
new Set([undefined, 0])
377+
new Set([null, '', 1n, 5, 2n, false]),
378+
new Set([undefined, 0, 5n, true, '2', '-000'])
379379
);
380380
assertNotDeepOrStrict(
381381
new Set(['']),

0 commit comments

Comments
 (0)