1
// Copyright (c) 2017-2022 Cloudflare, Inc.
2
// Licensed under the Apache 2.0 license found in the LICENSE file or at:
3
//     https://opensource.org/licenses/Apache-2.0
4
//
5
// Adapted from Node.js. Copyright Joyent, Inc. and other Node contributors.
6
//
7
// Permission is hereby granted, free of charge, to any person obtaining a
8
// copy of this software and associated documentation files (the
9
// "Software"), to deal in the Software without restriction, including
10
// without limitation the rights to use, copy, modify, merge, publish,
11
// distribute, sublicense, and/or sell copies of the Software, and to permit
12
// persons to whom the Software is furnished to do so, subject to the
13
// following conditions:
14
//
15
// The above copyright notice and this permission notice shall be included
16
// in all copies or substantial portions of the Software.
17
//
18
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
21
// NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
22
// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
23
// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
24
// USE OR OTHER DEALINGS IN THE SOFTWARE.
25
 
26
/* TODO: the following is adopted code, enabling linting one day */
27
/* eslint-disable */
28
 
29
import { compare } from 'node-internal:internal_buffer';
30
 
31
import {
32
  isAnyArrayBuffer,
33
  isArrayBufferView,
34
  isDate,
35
  isMap,
36
  isRegExp,
37
  isSet,
38
  isNativeError,
39
  isBoxedPrimitive,
40
  isNumberObject,
41
  isStringObject,
42
  isBooleanObject,
43
  isBigIntObject,
44
  isSymbolObject,
45
  isFloat16Array,
46
  isFloat32Array,
47
  isFloat64Array,
48
} from 'node-internal:internal_types';
49
 
50
import {
51
  ONLY_ENUMERABLE,
52
  SKIP_SYMBOLS,
53
  getOwnNonIndexProperties,
54
} from 'node-internal:internal_utils';
55
 
56
const kStrict = true;
57
 
58
const kNoIterator = 0;
59
const kIsArray = 1;
60
const kIsSet = 2;
61
const kIsMap = 3;
62
 
63
function areSimilarRegExps(a: RegExp, b: RegExp) {
64
  return (
65
    a.source === b.source && a.flags === b.flags && a.lastIndex === b.lastIndex
66
  );
67
}
68
 
69
type FloatArray = Float16Array | Float32Array | Float64Array;
70
type AnyArrayBuffer = ArrayBuffer | SharedArrayBuffer;
71
 
72
type Memos = {
73
  val1: Map<unknown, unknown>;
74
  val2: Map<unknown, unknown>;
75
  position: number;
76
};
77
 
78
function areSimilarFloatArrays(a: FloatArray, b: FloatArray) {
79
  if (a.byteLength !== b.byteLength) {
80
    return false;
81
  }
82
  for (let offset = 0; offset < a.byteLength; offset++) {
83
    if (a[offset] !== b[offset]) {
84
      return false;
85
    }
86
  }
87
  return true;
88
}
89
 
90
function areSimilarTypedArrays(a: ArrayBufferView, b: ArrayBufferView) {
91
  if (a.byteLength !== b.byteLength) {
92
    return false;
93
  }
94
  return (
95
    compare(
96
      new Uint8Array(a.buffer, a.byteOffset, a.byteLength),
97
      new Uint8Array(b.buffer, b.byteOffset, b.byteLength)
98
    ) === 0
99
  );
100
}
101
 
102
function areEqualArrayBuffers(buf1: AnyArrayBuffer, buf2: AnyArrayBuffer) {
103
  return (
104
    buf1.byteLength === buf2.byteLength &&
105
    compare(new Uint8Array(buf1), new Uint8Array(buf2)) === 0
106
  );
107
}
108
 
109
function areEqualBoxedPrimitives(val1: unknown, val2: unknown) {
110
  if (isNumberObject(val1)) {
111
    return (
112
      isNumberObject(val2) &&
113
      Object.is(
114
        Number.prototype.valueOf.call(val1),
115
        Number.prototype.valueOf.call(val2)
116
      )
117
    );
118
  }
119
  if (isStringObject(val1)) {
120
    return (
121
      isStringObject(val2) &&
122
      String.prototype.valueOf.call(val1) ===
123
        String.prototype.valueOf.call(val2)
124
    );
125
  }
126
  if (isBooleanObject(val1)) {
127
    return (
128
      isBooleanObject(val2) &&
129
      Boolean.prototype.valueOf.call(val1) ===
130
        Boolean.prototype.valueOf.call(val2)
131
    );
132
  }
133
  if (isBigIntObject(val1)) {
134
    return (
135
      isBigIntObject(val2) &&
136
      BigInt.prototype.valueOf.call(val1) ===
137
        BigInt.prototype.valueOf.call(val2)
138
    );
139
  }
140
  if (isSymbolObject(val1)) {
141
    return (
142
      isSymbolObject(val2) &&
143
      Symbol.prototype.valueOf.call(val1) ===
144
        Symbol.prototype.valueOf.call(val2)
145
    );
146
  }
147
 
148
  // Should be unreachable, here just as a backup.
149
  throw new Error(`Unknown boxed type ${val1}`);
150
}
151
 
152
function innerDeepEqual(
153
  val1: unknown,
154
  val2: unknown,
155
  strict: boolean,
156
  memos?: Memos
157
) {
158
  // All identical values are equivalent, as determined by ===.
159
  if (val1 === val2) {
160
    if (val1 !== 0) return true;
161
    return strict ? Object.is(val1, val2) : true;
162
  }
163
 
164
  // Check more closely if val1 and val2 are equal.
165
  if (strict) {
166
    if (typeof val1 !== 'object') {
167
      return (
168
        typeof val1 === 'number' && Number.isNaN(val1) && Number.isNaN(val2)
169
      );
170
    }
171
    if (typeof val2 !== 'object' || val1 === null || val2 === null) {
172
      return false;
173
    }
174
    if (Object.getPrototypeOf(val1) !== Object.getPrototypeOf(val2)) {
175
      return false;
176
    }
177
  } else {
178
    if (val1 === null || typeof val1 !== 'object') {
179
      if (val2 === null || typeof val2 !== 'object') {
180
        // TODO: eslint-disable-next-line eqeqeq
181
        return val1 == val2 || (Number.isNaN(val1) && Number.isNaN(val2));
182
      }
183
      return false;
184
    }
185
    if (val2 === null || typeof val2 !== 'object') {
186
      return false;
187
    }
188
  }
189
  const val1Tag = Object.prototype.toString.call(val1);
190
  const val2Tag = Object.prototype.toString.call(val2);
191
 
192
  if (val1Tag !== val2Tag) {
193
    return false;
194
  }
195
 
196
  if (Array.isArray(val1)) {
197
    // Check for sparse arrays and general fast path
198
    if (!Array.isArray(val2) || val1.length !== val2.length) {
199
      return false;
200
    }
201
    const filter = strict ? ONLY_ENUMERABLE : ONLY_ENUMERABLE | SKIP_SYMBOLS;
202
    const keys1 = getOwnNonIndexProperties(val1, filter);
203
    const keys2 = getOwnNonIndexProperties(val2, filter);
204
    if (keys1.length !== keys2.length) {
205
      return false;
206
    }
207
    return keyCheck(val1, val2, strict, memos, kIsArray, keys1);
208
  } else if (val1Tag === '[object Object]') {
209
    return keyCheck(val1, val2, strict, memos, kNoIterator);
210
  } else if (isDate(val1)) {
211
    if (
212
      !isDate(val2) ||
213
      Date.prototype.getTime.call(val1) !== Date.prototype.getTime.call(val2)
214
    ) {
215
      return false;
216
    }
217
  } else if (isRegExp(val1)) {
218
    if (!isRegExp(val2) || !areSimilarRegExps(val1 as RegExp, val2 as RegExp)) {
219
      return false;
220
    }
221
  } else if (isNativeError(val1) || val1 instanceof Error) {
222
    // Do not compare the stack as it might differ even though the error itself
223
    // is otherwise identical.
224
    if (
225
      (!isNativeError(val2) && !(val2 instanceof Error)) ||
226
      (val1 as Error).message !== (val2 as Error).message ||
227
      (val1 as Error).name !== (val2 as Error).name
228
    ) {
229
      return false;
230
    }
231
  } else if (isArrayBufferView(val1)) {
232
    if (!isArrayBufferView(val2)) return false;
233
    if (
234
      (val1 as any)[Symbol.toStringTag] !== (val2 as any)[Symbol.toStringTag]
235
    ) {
236
      return false;
237
    }
238
    if (
239
      !strict &&
240
      (isFloat16Array(val1) || isFloat32Array(val1) || isFloat64Array(val1))
241
    ) {
242
      if (!areSimilarFloatArrays(val1 as FloatArray, val2 as FloatArray)) {
243
        return false;
244
      }
245
    } else if (
246
      !areSimilarTypedArrays(val1 as ArrayBufferView, val2 as ArrayBufferView)
247
    ) {
248
      return false;
249
    }
250
    // Buffer.compare returns true, so val1.length === val2.length. If they both
251
    // only contain numeric keys, we don't need to exam further than checking
252
    // the symbols.
253
    const filter = strict ? ONLY_ENUMERABLE : ONLY_ENUMERABLE | SKIP_SYMBOLS;
254
    const keys1 = getOwnNonIndexProperties(val1, filter);
255
    const keys2 = getOwnNonIndexProperties(val2, filter);
256
    if (keys1.length !== keys2.length) {
257
      return false;
258
    }
259
    return keyCheck(val1, val2, strict, memos, kNoIterator, keys1);
260
  } else if (isSet(val1)) {
261
    if (
262
      !isSet(val2) ||
263
      (val1 as Set<unknown>).size !== (val2 as Set<unknown>).size
264
    ) {
265
      return false;
266
    }
267
    return keyCheck(val1, val2, strict, memos, kIsSet);
268
  } else if (isMap(val1)) {
269
    if (
270
      !isMap(val2) ||
271
      (val1 as Map<unknown, unknown>).size !==
272
        (val2 as Map<unknown, unknown>).size
273
    ) {
274
      return false;
275
    }
276
    return keyCheck(val1, val2, strict, memos, kIsMap);
277
  } else if (isAnyArrayBuffer(val1)) {
278
    if (
279
      !isAnyArrayBuffer(val2) ||
280
      !areEqualArrayBuffers(val1 as ArrayBuffer, val2 as ArrayBuffer)
281
    ) {
282
      return false;
283
    }
284
  } else if (isBoxedPrimitive(val1)) {
285
    if (!areEqualBoxedPrimitives(val1, val2)) {
286
      return false;
287
    }
288
  } else if (
289
    Array.isArray(val2) ||
290
    isArrayBufferView(val2) ||
291
    isSet(val2) ||
292
    isMap(val2) ||
293
    isDate(val2) ||
294
    isRegExp(val2) ||
295
    isAnyArrayBuffer(val2) ||
296
    isBoxedPrimitive(val2) ||
297
    isNativeError(val2) ||
298
    val2 instanceof Error
299
  ) {
300
    return false;
301
  }
302
  return keyCheck(val1, val2, strict, memos, kNoIterator);
303
}
304
 
305
function getEnumerables(val: Object, keys: (string | symbol)[]) {
306
  return keys.filter((k) => val.propertyIsEnumerable(k));
307
}
308
 
309
function keyCheck(
310
  val1: Object,
311
  val2: Object,
312
  strict: boolean,
313
  memos?: Memos,
314
  iterationType?: number,
315
  aKeys?: (string | symbol)[]
316
) {
317
  // For all remaining Object pairs, including Array, objects and Maps,
318
  // equivalence is determined by having:
319
  // a) The same number of owned enumerable properties
320
  // b) The same set of keys/indexes (although not necessarily the same order)
321
  // c) Equivalent values for every corresponding key/index
322
  // d) For Sets and Maps, equal contents
323
  // Note: this accounts for both named and indexed properties on Arrays.
324
  if (arguments.length === 5) {
325
    aKeys = Object.keys(val1 as Object);
326
    const bKeys = Object.keys(val2 as Object);
327
 
328
    // The pair must have the same number of owned properties.
329
    if (aKeys.length !== bKeys.length) {
330
      return false;
331
    }
332
  }
333
 
334
  // Cheap key test
335
  let i = 0;
336
  for (; i < aKeys!.length; i++) {
337
    if (!val2.propertyIsEnumerable(aKeys![i]!)) {
338
      return false;
339
    }
340
  }
341
 
342
  if (strict && arguments.length === 5) {
343
    const symbolKeysA = Object.getOwnPropertySymbols(val1);
344
    if (symbolKeysA.length !== 0) {
345
      let count = 0;
346
      for (i = 0; i < symbolKeysA.length; i++) {
347
        const key = symbolKeysA[i];
348
        if (val1.propertyIsEnumerable(key!)) {
349
          if (!val2.propertyIsEnumerable(key!)) {
350
            return false;
351
          }
352
          aKeys!.push(key!);
353
          count++;
354
        } else if (val2.propertyIsEnumerable(key!)) {
355
          return false;
356
        }
357
      }
358
      const symbolKeysB = Object.getOwnPropertySymbols(val2);
359
      if (
360
        symbolKeysA.length !== symbolKeysB.length &&
361
        getEnumerables(val2, symbolKeysB).length !== count
362
      ) {
363
        return false;
364
      }
365
    } else {
366
      const symbolKeysB = Object.getOwnPropertySymbols(val2);
367
      if (
368
        symbolKeysB.length !== 0 &&
369
        getEnumerables(val2, symbolKeysB).length !== 0
370
      ) {
371
        return false;
372
      }
373
    }
374
  }
375
 
376
  if (
377
    aKeys!.length === 0 &&
378
    (iterationType === kNoIterator ||
379
      (iterationType === kIsArray && (val1 as any[]).length === 0) ||
380
      (val1 as any).size === 0)
381
  ) {
382
    return true;
383
  }
384
 
385
  // Use memos to handle cycles.
386
  if (memos === undefined) {
387
    memos = {
388
      val1: new Map(),
389
      val2: new Map(),
390
      position: 0,
391
    };
392
  } else {
393
    // We prevent up to two map.has(x) calls by directly retrieving the value
394
    // and checking for undefined. The map can only contain numbers, so it is
395
    // safe to check for undefined only.
396
    const val2MemoA = memos.val1.get(val1);
397
    if (val2MemoA !== undefined) {
398
      const val2MemoB = memos.val2.get(val2);
399
      if (val2MemoB !== undefined) {
400
        return val2MemoA === val2MemoB;
401
      }
402
    }
403
    memos.position++;
404
  }
405
 
406
  memos.val1.set(val1, memos.position);
407
  memos.val2.set(val2, memos.position);
408
 
409
  const areEq = objEquiv(val1, val2, strict, aKeys!, memos, iterationType);
410
 
411
  memos.val1.delete(val1);
412
  memos.val2.delete(val2);
413
 
414
  return areEq;
415
}
416
 
417
function setHasEqualElement(
418
  set: Set<unknown>,
419
  val1: unknown,
420
  strict: boolean,
421
  memo: Memos
422
) {
423
  // Go looking.
424
  for (const val2 of set) {
425
    if (innerDeepEqual(val1, val2, strict, memo)) {
426
      // Remove the matching element to make sure we do not check that again.
427
      set.delete(val2);
428
      return true;
429
    }
430
  }
431
 
432
  return false;
433
}
434
 
435
function findLooseMatchingPrimitives(prim: unknown) {
436
  switch (typeof prim) {
437
    case 'undefined':
438
      return null;
439
    case 'object': // Only pass in null as object!
440
      return undefined;
441
    case 'symbol':
442
      return false;
443
    case 'string':
444
      return !Number.isNaN(+prim);
445
    // Loose equal entries exist only if the string is possible to convert to
446
    // a regular number and not NaN.
447
    case 'number':
448
      return !Number.isNaN(prim);
449
  }
450
  return true;
451
}
452
 
453
function setMightHaveLoosePrim(
454
  a: Set<unknown>,
455
  b: Set<unknown>,
456
  prim: unknown
457
) {
458
  const altValue = findLooseMatchingPrimitives(prim);
459
  if (altValue != null) return altValue;
460
 
461
  return b.has(altValue) && !a.has(altValue);
462
}
463
 
464
function mapMightHaveLoosePrim(
465
  a: Map<unknown, unknown>,
466
  b: Map<unknown, unknown>,
467
  prim: unknown,
468
  item: unknown,
469
  memo: Memos
470
) {
471
  const altValue = findLooseMatchingPrimitives(prim);
472
  if (altValue != null) {
473
    return altValue;
474
  }
475
  const curB = b.get(altValue);
476
  if (
477
    (curB === undefined && !b.has(altValue)) ||
478
    !innerDeepEqual(item, curB, false, memo)
479
  ) {
480
    return false;
481
  }
482
  return !a.has(altValue) && innerDeepEqual(item, curB, false, memo);
483
}
484
 
485
function setEquiv(
486
  a: Set<unknown>,
487
  b: Set<unknown>,
488
  strict: boolean,
489
  memo: Memos
490
) {
491
  // This is a lazily initiated Set of entries which have to be compared
492
  // pairwise.
493
  let set = null;
494
  for (const val of a) {
495
    // Note: Checking for the objects first improves the performance for object
496
    // heavy sets but it is a minor slow down for primitives. As they are fast
497
    // to check this improves the worst case scenario instead.
498
    if (typeof val === 'object' && val !== null) {
499
      if (set === null) {
500
        set = new Set();
501
      }
502
      // If the specified value doesn't exist in the second set it's a non-null
503
      // object (or non strict only: a not matching primitive) we'll need to go
504
      // hunting for something that's deep-(strict-)equal to it. To make this
505
      // O(n log n) complexity we have to copy these values in a new set first.
506
      set.add(val);
507
    } else if (!b.has(val)) {
508
      if (strict) return false;
509
 
510
      // Fast path to detect missing string, symbol, undefined and null values.
511
      if (!setMightHaveLoosePrim(a, b, val)) {
512
        return false;
513
      }
514
 
515
      if (set === null) {
516
        set = new Set();
517
      }
518
      set.add(val);
519
    }
520
  }
521
 
522
  if (set !== null) {
523
    for (const val of b) {
524
      // We have to check if a primitive value is already
525
      // matching and only if it's not, go hunting for it.
526
      if (typeof val === 'object' && val !== null) {
527
        if (!setHasEqualElement(set, val, strict, memo)) return false;
528
      } else if (
529
        !strict &&
530
        !a.has(val) &&
531
        !setHasEqualElement(set, val, strict, memo)
532
      ) {
533
        return false;
534
      }
535
    }
536
    return set.size === 0;
537
  }
538
 
539
  return true;
540
}
541
 
542
function mapHasEqualEntry(
543
  set: Set<unknown>,
544
  map: Map<unknown, unknown>,
545
  key1: unknown,
546
  item1: unknown,
547
  strict: boolean,
548
  memo: Memos
549
) {
550
  // To be able to handle cases like:
551
  //   Map([[{}, 'a'], [{}, 'b']]) vs Map([[{}, 'b'], [{}, 'a']])
552
  // ... we need to consider *all* matching keys, not just the first we find.
553
  for (const key2 of set) {
554
    if (
555
      innerDeepEqual(key1, key2, strict, memo) &&
556
      innerDeepEqual(item1, map.get(key2), strict, memo)
557
    ) {
558
      set.delete(key2);
559
      return true;
560
    }
561
  }
562
 
563
  return false;
564
}
565
 
566
function mapEquiv(
567
  a: Map<unknown, unknown>,
568
  b: Map<unknown, unknown>,
569
  strict: boolean,
570
  memo: Memos
571
) {
572
  let set = null;
573
 
574
  for (const { 0: key, 1: item1 } of a) {
575
    if (typeof key === 'object' && key !== null) {
576
      if (set === null) {
577
        set = new Set();
578
      }
579
      set.add(key);
580
    } else {
581
      // By directly retrieving the value we prevent another b.has(key) check in
582
      // almost all possible cases.
583
      const item2 = b.get(key);
584
      if (
585
        (item2 === undefined && !b.has(key)) ||
586
        !innerDeepEqual(item1, item2, strict, memo)
587
      ) {
588
        if (strict) return false;
589
        // Fast path to detect missing string, symbol, undefined and null
590
        // keys.
591
        if (!mapMightHaveLoosePrim(a, b, key, item1, memo)) return false;
592
        if (set === null) {
593
          set = new Set();
594
        }
595
        set.add(key);
596
      }
597
    }
598
  }
599
 
600
  if (set !== null) {
601
    for (const { 0: key, 1: item } of b) {
602
      if (typeof key === 'object' && key !== null) {
603
        if (!mapHasEqualEntry(set, a, key, item, strict, memo)) return false;
604
      } else if (
605
        !strict &&
606
        (!a.has(key) || !innerDeepEqual(a.get(key), item, false, memo)) &&
607
        !mapHasEqualEntry(set, a, key, item, false, memo)
608
      ) {
609
        return false;
610
      }
611
    }
612
    return set.size === 0;
613
  }
614
 
615
  return true;
616
}
617
 
618
function objEquiv(
619
  a: Object,
620
  b: Object,
621
  strict: boolean,
622
  keys: (string | symbol)[],
623
  memos: Memos,
624
  iterationType?: number
625
) {
626
  // Sets and maps don't have their entries accessible via normal object
627
  // properties.
628
  let i = 0;
629
 
630
  if (iterationType === kIsSet) {
631
    if (!setEquiv(a as Set<unknown>, b as Set<unknown>, strict, memos)) {
632
      return false;
633
    }
634
  } else if (iterationType === kIsMap) {
635
    if (
636
      !mapEquiv(
637
        a as Map<unknown, unknown>,
638
        b as Map<unknown, unknown>,
639
        strict,
640
        memos
641
      )
642
    ) {
643
      return false;
644
    }
645
  } else if (iterationType === kIsArray) {
646
    for (; i < (a as [any]).length; i++) {
647
      if (a.hasOwnProperty(i)) {
648
        if (
649
          !b.hasOwnProperty(i) ||
650
          !innerDeepEqual((a as [any])[i], (b as [any])[i], strict, memos)
651
        ) {
652
          return false;
653
        }
654
      } else if (b.hasOwnProperty(i)) {
655
        return false;
656
      } else {
657
        // Array is sparse.
658
        const keysA = Object.keys(a);
659
        for (; i < keysA.length; i++) {
660
          const key = keysA[i];
661
          if (
662
            !b.hasOwnProperty(key!) ||
663
            !innerDeepEqual((a as any)[key!], (b as any)[key!], strict, memos)
664
          ) {
665
            return false;
666
          }
667
        }
668
        if (keysA.length !== Object.keys(b).length) {
669
          return false;
670
        }
671
        return true;
672
      }
673
    }
674
  }
675
 
676
  // The pair must have equivalent values for every corresponding key.
677
  // Possibly expensive deep test:
678
  for (i = 0; i < keys.length; i++) {
679
    const key = keys[i];
680
    if (!innerDeepEqual((a as any)[key!], (b as any)[key!], strict, memos)) {
681
      return false;
682
    }
683
  }
684
  return true;
685
}
686
 
687
export function isDeepStrictEqual(val1: unknown, val2: unknown) {
688
  return innerDeepEqual(val1, val2, kStrict);
689
}