// Derived from Node.js v24.16.0 (MIT; Copyright Node.js contributors, and Joyent, Inc. and
// other Node contributors). See LICENSE-node.
// util.isDeepStrictEqual / util.isDeepEqual and assert's partial-deep-equal, after Node
// v24's lib/internal/util/comparisons.js. Line-for-line where TypeScript allows; the
// primordial snapshots and internal bindings it leans on become plain JS:
//  - internalBinding('buffer').compare -> byteCompare below, a byte-by-byte loop over
//    Uint8Array views of each side's buffer (works for typed arrays and DataViews alike,
//    same as the native binding does).
//  - internal/url's isURL -> `instanceof URL`.
//  - internal/util's isError -> isErrorLike below (Node's own isError is exactly this:
//    an Error instance, or anything tagged "[object Error]" by a foreign realm).
//  - internal/util/types -> ./types, this kernel's own predicates.
//  - internalBinding('util')'s getOwnNonIndexProperties/ONLY_ENUMERABLE/SKIP_SYMBOLS ->
//    getOwnNonIndexProperties below: Reflect.ownKeys filtered to non-index keys, then to
//    enumerable keys when ONLY_ENUMERABLE is set and symbols dropped when SKIP_SYMBOLS is.
//  - internal/crypto's KeyObject/CryptoKey equality (kKeyObject, kAlgorithm,
//    kExtractable, kKeyUsages) -> this kernel's own crypto surface. KeyObject's
//    `isKeyObject` predicate (src/runtime/util/types.ts) always answers false today, so
//    that branch below is unreachable for now; CryptoKey is the kernel's real Web Crypto
//    CryptoKey, compared on its public fields (extractable, type, algorithm, usages)
//    since nothing here can see the raw key material Node's internal symbols hold.
import { Buffer } from "../buffer";
import { types } from "./types";

const {
  isAnyArrayBuffer, isArrayBufferView, isDate, isMap, isRegExp, isSet, isNativeError,
  isBoxedPrimitive, isNumberObject, isStringObject, isBooleanObject, isBigIntObject,
  isSymbolObject, isFloat16Array, isFloat32Array, isFloat64Array, isKeyObject, isCryptoKey,
  isPromise, isWeakMap, isWeakSet,
} = types;

/* eslint-disable @typescript-eslint/no-explicit-any -- deep equality is inherently untyped recursion */

const wellKnownConstructors = new Set<unknown>([
  Array, ArrayBuffer, BigInt, BigInt64Array, BigUint64Array, Boolean, Buffer, DataView, Date,
  Error, Float32Array, Float64Array, Function, Int16Array, Int32Array, Int8Array, Map, Number,
  Object, Promise, RegExp, Set, String, Symbol, Uint16Array, Uint32Array, Uint8Array,
  Uint8ClampedArray, WeakMap, WeakSet,
]);
// TODO(BridgeAR, upstream): remove when the flag is gone from V8.
if (typeof (globalThis as { Float16Array?: unknown }).Float16Array !== "undefined") {
  wellKnownConstructors.add((globalThis as { Float16Array: unknown }).Float16Array);
}

const kStrict = 2;
const kStrictWithoutPrototypes = 3;
const kLoose = 0;
const kPartial = 1;
type Mode = 0 | 1 | 2 | 3;

const kNoIterator = 0;
const kIsArray = 1;
const kIsSet = 2;
const kIsMap = 3;
type IterationType = 0 | 1 | 2 | 3;

/** internalBinding('util')'s ONLY_ENUMERABLE / SKIP_SYMBOLS flags, as local bit values:
 *  nothing outside this module needs the real binding's numeric encoding. */
const ONLY_ENUMERABLE = 1;
const SKIP_SYMBOLS = 2;

const isIndexKey = (key: string): boolean => /^(?:0|[1-9]\d*)$/.test(key) && Number(key) < 2 ** 32 - 1;

/** internalBinding('util').getOwnNonIndexProperties. */
function getOwnNonIndexProperties(obj: object, filter: number): Array<string | symbol> {
  let keys = Reflect.ownKeys(obj);
  if (filter & SKIP_SYMBOLS) keys = keys.filter((k) => typeof k !== "symbol");
  keys = keys.filter((k) => typeof k === "symbol" || !isIndexKey(k));
  if (filter & ONLY_ENUMERABLE) {
    keys = keys.filter((k) => Object.getOwnPropertyDescriptor(obj, k)?.enumerable === true);
  }
  return keys;
}

/** internal/util's isError: an Error, or anything a foreign realm tags as one. Also
 *  used by ../assert/assertion_error.ts, which needs the exact same predicate. */
export function isErrorLike(v: unknown): boolean {
  return v instanceof Error || Object.prototype.toString.call(v) === "[object Error]";
}

const TYPED_ARRAY_TAGS = new Set([
  "Int8Array", "Uint8Array", "Uint8ClampedArray", "Int16Array", "Uint16Array", "Int32Array",
  "Uint32Array", "Float16Array", "Float32Array", "Float64Array", "BigInt64Array", "BigUint64Array",
]);

/** TypedArrayPrototypeGetSymbolToStringTag: the %TypedArray%.prototype[Symbol.toStringTag]
 *  getter is spec'd to answer `undefined` for any receiver without a typed-array slot
 *  (including a DataView), never to throw — so this is safe to call on anything. */
function typedArrayTag(v: unknown): string | undefined {
  if (!ArrayBuffer.isView(v) || v instanceof DataView) return undefined;
  const tag = Object.prototype.toString.call(v).slice(8, -1);
  return TYPED_ARRAY_TAGS.has(tag) ? tag : undefined;
}

/** internalBinding('buffer').compare: a plain byte loop over each side's bytes. */
function byteCompare(a: ArrayBufferView, b: ArrayBufferView): -1 | 0 | 1 {
  const ua = new Uint8Array(a.buffer as ArrayBuffer, a.byteOffset, a.byteLength);
  const ub = new Uint8Array(b.buffer as ArrayBuffer, b.byteOffset, b.byteLength);
  const len = Math.min(ua.length, ub.length);
  for (let i = 0; i < len; i++) {
    if (ua[i] !== ub[i]) return ua[i]! < ub[i]! ? -1 : 1;
  }
  return ua.length === ub.length ? 0 : ua.length < ub.length ? -1 : 1;
}

interface Memos {
  set: Set<unknown> | undefined;
  a: unknown;
  b: unknown;
  c: unknown;
  d: unknown;
  deep: boolean;
}
type MemoState = Memos | null | undefined;

// Check if they have the same source and flags
function areSimilarRegExps(a: RegExp, b: RegExp): boolean {
  return a.source === b.source && a.flags === b.flags && a.lastIndex === b.lastIndex;
}

function isPartialUint8Array(a: ArrayBufferView, b: ArrayBufferView): boolean {
  const lenA = a.byteLength;
  const lenB = b.byteLength;
  if (lenA < lenB) return false;
  const ua = new Uint8Array(a.buffer as ArrayBuffer, a.byteOffset, a.byteLength);
  const ub = new Uint8Array(b.buffer as ArrayBuffer, b.byteOffset, b.byteLength);
  let offsetA = 0;
  for (let offsetB = 0; offsetB < lenB; offsetB++) {
    while (ua[offsetA] !== ub[offsetB]) {
      offsetA++;
      if (offsetA > lenA - lenB + offsetB) return false;
    }
    offsetA++;
  }
  return true;
}

function isPartialArrayBufferView(a: ArrayBufferView, b: ArrayBufferView): boolean {
  if (a.byteLength < b.byteLength) return false;
  return isPartialUint8Array(
    new Uint8Array(a.buffer as ArrayBuffer, a.byteOffset, a.byteLength),
    new Uint8Array(b.buffer as ArrayBuffer, b.byteOffset, b.byteLength),
  );
}

function areSimilarFloatArrays(a: any, b: any): boolean {
  const len = a.byteLength;
  if (len !== b.byteLength) return false;
  for (let offset = 0; offset < len; offset++) {
    if (a[offset] !== b[offset]) return false;
  }
  return true;
}

function areSimilarTypedArrays(a: ArrayBufferView, b: ArrayBufferView): boolean {
  return a.byteLength === b.byteLength && byteCompare(a, b) === 0;
}

function areEqualArrayBuffers(buf1: ArrayBufferLike, buf2: ArrayBufferLike): boolean {
  return buf1.byteLength === buf2.byteLength &&
    byteCompare(new Uint8Array(buf1), new Uint8Array(buf2)) === 0;
}

function isEqualBoxedPrimitive(val1: any, val2: any): boolean {
  if (isNumberObject(val1)) {
    return isNumberObject(val2) && Object.is(Number.prototype.valueOf.call(val1), Number.prototype.valueOf.call(val2));
  }
  if (isStringObject(val1)) {
    return isStringObject(val2) && String.prototype.valueOf.call(val1) === String.prototype.valueOf.call(val2);
  }
  if (isBooleanObject(val1)) {
    return isBooleanObject(val2) && Boolean.prototype.valueOf.call(val1) === Boolean.prototype.valueOf.call(val2);
  }
  if (isBigIntObject(val1)) {
    return isBigIntObject(val2) && BigInt.prototype.valueOf.call(val1) === BigInt.prototype.valueOf.call(val2);
  }
  if (isSymbolObject(val1)) {
    return isSymbolObject(val2) && Symbol.prototype.valueOf.call(val1) === Symbol.prototype.valueOf.call(val2);
  }
  /* c8 ignore next */
  throw new Error(`Unknown boxed type ${val1}`);
}

function isEnumerableOrIdentical(val1: any, val2: any, prop: string, mode: Mode, memos: MemoState): boolean {
  return Object.prototype.propertyIsEnumerable.call(val2, prop) || // This is handled by Object.keys()
    (mode === kPartial && (val2[prop] === undefined || (prop === "message" && val2[prop] === ""))) ||
    innerDeepEqual(val1[prop], val2[prop], mode, memos);
}

function innerDeepEqual(val1: unknown, val2: unknown, mode: Mode, memos: MemoState): boolean {
  // All identical values are equivalent, as determined by ===.
  if (val1 === val2) {
    return val1 !== 0 || Object.is(val1, val2) || mode === kLoose;
  }

  // Check more closely if val1 and val2 are equal.
  if (mode !== kLoose) {
    if (typeof val1 === "number") {
      // Check for NaN
      return val1 !== val1 && (val2 as number) !== val2;
    }
    if (typeof val2 !== "object" || typeof val1 !== "object" || val1 === null || val2 === null) {
      return false;
    }
  } else {
    if (val1 === null || typeof val1 !== "object") {
      return (val2 === null || typeof val2 !== "object") &&
        // Check for NaN
        // eslint-disable-next-line eqeqeq
        (val1 == val2 || (val1 !== val1 && val2 !== val2));
    }
    if (val2 === null || typeof val2 !== "object") return false;
  }
  return objectComparisonStart(val1 as object, val2 as object, mode, memos);
}

function hasUnequalTag(val1: any, val2: any): boolean {
  return val1[Symbol.toStringTag] !== val2[Symbol.toStringTag];
}

function slowHasUnequalTag(val1Tag: string, val1: any, val2: any): boolean {
  if (val1[Symbol.toStringTag] !== undefined && val2[Symbol.toStringTag] !== undefined) {
    return val1[Symbol.toStringTag] !== val2[Symbol.toStringTag];
  }
  return val1Tag !== Object.prototype.toString.call(val2);
}

function objectComparisonStart(val1: any, val2: any, mode: Mode, memos: MemoState): boolean {
  if (mode === kStrict) {
    if (wellKnownConstructors.has(val1.constructor) ||
      (val1.constructor !== undefined && !Object.hasOwn(val1, "constructor"))) {
      if (val1.constructor !== val2.constructor) return false;
    } else if (Object.getPrototypeOf(val1) !== Object.getPrototypeOf(val2)) {
      return false;
    }
  }

  if (Array.isArray(val1)) {
    if (!Array.isArray(val2) ||
      (val1.length !== val2.length && (mode !== kPartial || val1.length < val2.length)) ||
      hasUnequalTag(val1, val2)) {
      return false;
    }

    const filter = mode !== kLoose ? ONLY_ENUMERABLE : ONLY_ENUMERABLE | SKIP_SYMBOLS;
    const keys2 = getOwnNonIndexProperties(val2, filter);
    if (mode !== kPartial && keys2.length !== getOwnNonIndexProperties(val1, filter).length) {
      return false;
    }
    return keyCheck(val1, val2, mode, memos, kIsArray, keys2);
  }

  let val1Tag: string | undefined;
  if (val1[Symbol.toStringTag] === undefined && (val1Tag = Object.prototype.toString.call(val1)) === "[object Object]") {
    if (slowHasUnequalTag(val1Tag, val1, val2)) return false;
    return keyCheck(val1, val2, mode, memos, kNoIterator);
  } else if (isSet(val1)) {
    if (!isSet(val2) ||
      (val1.size !== val2.size && (mode !== kPartial || val1.size < val2.size)) ||
      hasUnequalTag(val1, val2)) {
      return false;
    }
    return keyCheck(val1, val2, mode, memos, kIsSet);
  } else if (isMap(val1)) {
    if (!isMap(val2) ||
      (val1.size !== val2.size && (mode !== kPartial || val1.size < val2.size)) ||
      hasUnequalTag(val1, val2)) {
      return false;
    }
    return keyCheck(val1, val2, mode, memos, kIsMap);
  } else if (isArrayBufferView(val1)) {
    if (typedArrayTag(val1) !== typedArrayTag(val2)) return false;
    if (mode === kPartial && val1.byteLength !== val2.byteLength) {
      if (!isPartialArrayBufferView(val1, val2)) return false;
    } else if (mode === kLoose && (isFloat32Array(val1) || isFloat64Array(val1) || isFloat16Array(val1))) {
      if (!areSimilarFloatArrays(val1, val2)) return false;
    } else if (!areSimilarTypedArrays(val1, val2)) {
      return false;
    }
    // Buffer.compare returns true, so val1.length === val2.length. If they both
    // only contain numeric keys, we don't need to exam further than checking
    // the symbols.
    const filter = mode !== kLoose ? ONLY_ENUMERABLE : ONLY_ENUMERABLE | SKIP_SYMBOLS;
    const keys2 = getOwnNonIndexProperties(val2, filter);
    if (mode !== kPartial && keys2.length !== getOwnNonIndexProperties(val1, filter).length) {
      return false;
    }
    return keyCheck(val1, val2, mode, memos, kNoIterator, keys2);
  } else if (isDate(val1)) {
    if (!isDate(val2) || hasUnequalTag(val1, val2)) return false;
    const time1 = val1.getTime();
    const time2 = val2.getTime();
    // eslint-disable-next-line no-self-compare
    if (time1 !== time2 && (time1 === time1 || time2 === time2)) return false;
  } else if (isRegExp(val1)) {
    if (!isRegExp(val2) || !areSimilarRegExps(val1, val2) || hasUnequalTag(val1, val2)) return false;
  } else if (isAnyArrayBuffer(val1)) {
    if (!isAnyArrayBuffer(val2) || hasUnequalTag(val1, val2)) return false;
    if (mode !== kPartial || val1.byteLength === val2.byteLength) {
      if (!areEqualArrayBuffers(val1, val2)) return false;
    } else if (!isPartialUint8Array(new Uint8Array(val1), new Uint8Array(val2))) {
      return false;
    }
  } else if (slowHasUnequalTag(val1Tag ?? Object.prototype.toString.call(val1), val1, val2) ||
    Array.isArray(val2) || isArrayBufferView(val2) || isSet(val2) || isMap(val2) ||
    isDate(val2) || isRegExp(val2) || isAnyArrayBuffer(val2)) {
    return false;
  } else if (isErrorLike(val1)) {
    // Do not compare the stack as it might differ even though the error itself
    // is otherwise identical.
    if (!isErrorLike(val2) ||
      !isEnumerableOrIdentical(val1, val2, "message", mode, memos) ||
      !isEnumerableOrIdentical(val1, val2, "name", mode, memos) ||
      !isEnumerableOrIdentical(val1, val2, "cause", mode, memos) ||
      !isEnumerableOrIdentical(val1, val2, "errors", mode, memos)) {
      return false;
    }
    const hasOwnVal2Cause = Object.hasOwn(val2, "cause");
    if (hasOwnVal2Cause !== Object.hasOwn(val1, "cause") && (mode !== kPartial || hasOwnVal2Cause)) {
      return false;
    }
  } else if (isBoxedPrimitive(val1)) {
    if (!isEqualBoxedPrimitive(val1, val2)) return false;
  } else if (val1 instanceof URL) {
    if (!(val2 instanceof URL) || val1.href !== val2.href) return false;
  } else if (isKeyObject(val1)) {
    // Unreachable today: src/runtime/util/types.ts's isKeyObject always answers false.
    if (!isKeyObject(val2) || !val1.equals(val2)) return false;
  } else if (isCryptoKey(val1)) {
    if (!isEqualCryptoKey(val1, val2, mode, memos)) return false;
  } else if (isBoxedPrimitive(val2) || isNativeError(val2) || val2 instanceof Error ||
    isWeakMap(val1) || isWeakSet(val1) || isPromise(val1)) {
    return false;
  }

  return keyCheck(val1, val2, mode, memos, kNoIterator);
}

/** CryptoKey equality: Node compares its own internal key-material symbols
 *  (kKeyObject/kAlgorithm/kExtractable/kKeyUsages), which don't exist on this kernel's
 *  real Web Crypto CryptoKey. We compare the public fields Web Crypto exposes instead;
 *  see the file header for the resulting divergence. */
function isEqualCryptoKey(val1: CryptoKey, val2: unknown, mode: Mode, memos: MemoState): boolean {
  if (!isCryptoKey(val2)) return false;
  const k2 = val2 as CryptoKey;
  if (val1.extractable !== k2.extractable || val1.type !== k2.type) return false;
  if (!innerDeepEqual(val1.algorithm, k2.algorithm, mode, memos)) return false;
  return innerDeepEqual([...val1.usages].sort(), [...k2.usages].sort(), mode, memos);
}

function partialSymbolEquiv(val1: any, val2: any, keys2: Array<string | symbol>): boolean {
  const symbolKeys = Object.getOwnPropertySymbols(val2);
  if (symbolKeys.length !== 0) {
    for (const key of symbolKeys) {
      if (Object.prototype.propertyIsEnumerable.call(val2, key)) keys2.push(key);
    }
  }
  return true;
}

function keyCheck(
  val1: any, val2: any, mode: Mode, memos: MemoState, iterationType: IterationType,
  keys2In?: Array<string | symbol>,
): boolean {
  // For all remaining Object pairs, including Array, objects and Maps,
  // equivalence is determined by having:
  // a) The same number of owned enumerable properties
  // b) The same set of keys/indexes (although not necessarily the same order)
  // c) Equivalent values for every corresponding key/index
  // d) For Sets and Maps, equal contents
  // Note: this accounts for both named and indexed properties on Arrays.
  const isArrayLikeObject = keys2In !== undefined;
  let keys2 = keys2In ?? Object.keys(val2);
  let keys1: Array<string | symbol> | undefined;

  if (!isArrayLikeObject) {
    // The pair must have the same number of owned properties.
    if (mode === kPartial) {
      if (!partialSymbolEquiv(val1, val2, keys2)) return false;
    } else if (keys2.length !== (keys1 = Object.keys(val1)).length) {
      return false;
    } else if (mode === kStrict || mode === kStrictWithoutPrototypes) {
      for (const key of Object.getOwnPropertySymbols(val1)) {
        if (Object.prototype.propertyIsEnumerable.call(val1, key)) keys1.push(key);
      }
      for (const key of Object.getOwnPropertySymbols(val2)) {
        if (Object.prototype.propertyIsEnumerable.call(val2, key)) keys2.push(key);
      }
      if (keys1.length !== keys2.length) return false;
    }
  }

  if (keys2.length === 0 &&
    (iterationType === kNoIterator || (iterationType === kIsArray && val2.length === 0) || val2.size === 0)) {
    return true;
  }

  if (memos === null) {
    return objEquiv(val1, val2, mode, keys1, keys2, memos, iterationType);
  }
  return handleCycles(val1, val2, mode, keys1, keys2, memos, iterationType);
}

/** Narrowing `memos.set` inline (as Node's original does) pins TS's flow analysis to
 *  `undefined` across the `objEquiv` call below, since nothing in this scope visibly
 *  reassigns it; a separate function gets a fresh, unnarrowed look at the same field. */
function clearRecursionPair(memos: Memos): void {
  memos.set?.delete(memos.c);
  memos.set?.delete(memos.d);
}

function handleCycles(
  val1: any, val2: any, mode: Mode, keys1: Array<string | symbol> | undefined,
  keys2: Array<string | symbol>, memos: Memos | undefined, iterationType: IterationType,
): boolean {
  // Use memos to handle cycles.
  if (memos === undefined) {
    const next: Memos = { set: undefined, a: val1, b: val2, c: undefined, d: undefined, deep: false };
    return objEquiv(val1, val2, mode, keys1, keys2, next, iterationType);
  }

  if (memos.set === undefined) {
    if (memos.deep === false) {
      if (memos.a === val1) return memos.b === val2;
      if (memos.b === val2) return false;
      memos.c = val1;
      memos.d = val2;
      memos.deep = true;
      const result = objEquiv(val1, val2, mode, keys1, keys2, memos, iterationType);
      memos.deep = false;
      clearRecursionPair(memos);
      return result;
    }
    memos.set = new Set([memos.a, memos.b, memos.c, memos.d]);
  }

  const { set } = memos;

  const originalSize = set.size;
  set.add(val1);
  set.add(val2);
  if (originalSize !== set.size - 2) {
    return originalSize === set.size;
  }

  const areEq = objEquiv(val1, val2, mode, keys1, keys2, memos, iterationType);

  set.delete(val1);
  set.delete(val2);

  return areEq;
}

// 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: unknown): unknown {
  switch (typeof prim) {
    case "undefined":
      return null;
    case "object": // Only pass in null as object!
      return undefined;
    case "symbol":
      return false;
    case "string": {
      const n = +(prim as string);
      // Loose equal entries exist only if the string is possible to convert to
      // a regular number and not NaN.
      // eslint-disable-next-line no-self-compare
      if (n !== n) return false;
      return true;
    }
    case "number":
      // Check for NaN
      // eslint-disable-next-line no-self-compare
      if ((prim as number) !== prim) return false;
      return true;
    default:
      return true;
  }
}

function setMightHaveLoosePrim(a: Set<unknown>, b: Set<unknown>, prim: unknown): boolean {
  const altValue = findLooseMatchingPrimitives(prim);
  if (altValue != null) return altValue as boolean;
  return !b.has(altValue) && a.has(altValue);
}

function mapMightHaveLoosePrim(a: Map<unknown, unknown>, b: Map<unknown, unknown>, prim: unknown, item2: unknown, memo: MemoState): boolean {
  const altValue = findLooseMatchingPrimitives(prim);
  if (altValue != null) return altValue as boolean;
  const item1 = a.get(altValue);
  if ((item1 === undefined && !a.has(altValue)) || !innerDeepEqual(item1, item2, kLoose, memo)) {
    return false;
  }
  return !b.has(altValue) && innerDeepEqual(item1, item2, kLoose, memo);
}

function partialObjectSetEquiv(array: unknown[], a: Set<unknown>, b: Set<unknown>, mode: Mode, memo: MemoState): boolean {
  let aPos = 0;
  let direction = 1;
  let start = 0;
  let end = array.length - 1;
  for (const val1 of a) {
    aPos++;
    if (!b.has(val1)) {
      let innerStart = start;
      if (direction === 1) {
        if (innerDeepEqual(val1, array[start], mode, memo)) {
          if (start === end) return true;
          start += 1;
          continue;
        }
        if (start === end) {
          // The last element of set b might match a later element in set a.
          continue;
        }
        direction = -1;
        innerStart += 1;
      }
      let matched = true;
      if (!innerDeepEqual(val1, array[end], mode, memo)) {
        direction = 1;
        matched = arrayHasEqualElement(array, val1, mode, memo, innerDeepEqual, innerStart, end);
      }
      if (matched) {
        if (start === end) return true;
        end -= 1;
      }
    }
    if (a.size - aPos <= end - start) return false;
  }
  return false;
}

function arrayHasEqualElement(
  array: unknown[], val1: unknown, mode: Mode, memo: MemoState,
  comparator: (a: unknown, b: unknown, mode: Mode, memo: MemoState) => boolean, start: number, end: number,
): boolean {
  for (let i = end - 1; i >= start; i--) {
    if (comparator(val1, array[i], mode, memo)) {
      // Move the matching element to make sure we do not check that again.
      array[i] = array[end];
      return true;
    }
  }
  return false;
}

function setObjectEquiv(array: unknown[], a: Set<unknown>, b: Set<unknown>, mode: Mode, memo: MemoState): boolean {
  let direction = 1;
  let start = 0;
  let end = array.length - 1;
  const comparator = mode !== kLoose ? objectComparisonStart : innerDeepEqual;
  const extraChecks = mode === kLoose || array.length !== a.size;
  for (const val1 of a) {
    if (extraChecks) {
      if (typeof val1 === "object") {
        if (b.has(val1)) continue;
      } else if (b.has(val1)) {
        continue;
      } else if (mode !== kLoose) {
        return false;
      }
    }

    let innerStart = start;
    if (direction === 1) {
      if ((comparator as any)(val1, array[start], mode, memo)) {
        start += 1;
        continue;
      }
      if (start === end) return false;
      direction = -1;
      innerStart += 1;
    }
    if (!(comparator as any)(val1, array[end], mode, memo)) {
      direction = 1;
      if (!arrayHasEqualElement(array, val1, mode, memo, comparator as any, innerStart, end)) return false;
    }
    end -= 1;
  }
  return true;
}

function compareSmallSets(a: Set<unknown>, b: Set<unknown>, val: unknown, iteratorB: Iterator<unknown>, mode: Mode, memo: MemoState): boolean {
  const iteratorA = a.values();
  const firstA = iteratorA.next().value;
  const first = innerDeepEqual(firstA, val, mode, memo);
  if (first) {
    if (b.size === 1) return true; // Partial mode && a.size === 1 || b.size === 1
    const secondA = iteratorA.next().value;
    return b.has(secondA) || innerDeepEqual(secondA, iteratorB.next().value, mode, memo);
  }
  return a.size !== 1 && innerDeepEqual(iteratorA.next().value, val, mode, memo) && (
    b.size === 1 || // Partial mode
    b.has(firstA) || // Primitive or reference equal
    innerDeepEqual(firstA, iteratorB.next().value, mode, memo)
  );
}

function setEquiv(a: Set<unknown>, b: Set<unknown>, mode: Mode, memo: MemoState): boolean {
  // This is a lazily initiated Set of entries which have to be compared
  // pairwise.
  let array: unknown[] | undefined;

  const iteratorB = b.values();
  for (const val of iteratorB) {
    if (!a.has(val)) {
      if ((typeof val !== "object" || val === null) &&
        (mode !== kLoose || !setMightHaveLoosePrim(a, b, val))) {
        return false;
      }

      if (array === undefined) {
        if (a.size < 3) return compareSmallSets(a, b, val, iteratorB, mode, memo);
        array = [];
      }
      // If the specified value doesn't exist in the second set it's a object
      // (or in loose mode: a non-matching primitive). Find the
      // deep-(mode-)equal element in a set copy to reduce duplicate checks.
      array.push(val);
    }
  }

  if (array === undefined) return true;
  if (mode === kPartial) return partialObjectSetEquiv(array, a, b, mode, memo);
  return setObjectEquiv(array, a, b, mode, memo);
}

function partialObjectMapEquiv(array: unknown[], a: Map<unknown, unknown>, b: Map<unknown, unknown>, mode: Mode, memo: MemoState): boolean {
  let aPos = 0;
  let direction = 1;
  let start = 0;
  let end = array.length - 1;
  for (const [key1, item1] of a) {
    aPos++;
    if (typeof key1 === "object" && key1 !== null) {
      let innerStart = start;
      if (direction === 1) {
        const key2 = array[start];
        if (objectComparisonStart(key1, key2, mode, memo) && innerDeepEqual(item1, b.get(key2), mode, memo)) {
          if (start === end) return true;
          start += 1;
          continue;
        }
        if (start === end) {
          // The last element of map b might match a later element in map a.
          continue;
        }
        direction = -1;
        innerStart += 1;
      }
      let matched = true;
      const key2 = array[end];
      if (!objectComparisonStart(key1, key2, mode, memo) || !innerDeepEqual(item1, b.get(key2), mode, memo)) {
        direction = 1;
        matched = arrayHasEqualMapElement(array, key1, item1, b, mode, memo, objectComparisonStart, innerStart, end);
      }
      if (matched) {
        if (start === end) return true;
        end -= 1;
      }
    }
    if (a.size - aPos <= end - start) return false;
  }
  return false;
}

function arrayHasEqualMapElement(
  array: unknown[], key1: unknown, item1: unknown, b: Map<unknown, unknown>, mode: Mode, memo: MemoState,
  comparator: (a: unknown, b: unknown, mode: Mode, memo: MemoState) => boolean, start: number, end: number,
): boolean {
  for (let i = end - 1; i >= start; i--) {
    const key2 = array[i];
    if (comparator(key1, key2, mode, memo) && innerDeepEqual(item1, b.get(key2), mode, memo)) {
      // Move the matching element to make sure we do not check that again.
      array[i] = array[end];
      return true;
    }
  }
  return false;
}

function mapObjectEquiv(array: unknown[], a: Map<unknown, unknown>, b: Map<unknown, unknown>, mode: Mode, memo: MemoState): boolean {
  let direction = 1;
  let start = 0;
  let end = array.length - 1;
  const comparator = mode !== kLoose ? objectComparisonStart : innerDeepEqual;
  const extraChecks = mode === kLoose || array.length !== a.size;

  for (const [key1, item1] of a) {
    if (extraChecks && (typeof key1 !== "object" || key1 === null)) {
      if (b.has(key1)) {
        if (mode !== kLoose || innerDeepEqual(item1, b.get(key1), mode, memo)) continue;
      } else if (mode !== kLoose) {
        return false;
      }
    }

    let innerStart = start;
    if (direction === 1) {
      const key2 = array[start];
      if ((comparator as any)(key1, key2, mode, memo) && innerDeepEqual(item1, b.get(key2), mode, memo)) {
        start += 1;
        continue;
      }
      if (start === end) return false;
      direction = -1;
      innerStart += 1;
    }
    const key2 = array[end];
    if (!(comparator as any)(key1, key2, mode, memo) || !innerDeepEqual(item1, b.get(key2), mode, memo)) {
      direction = 1;
      if (!arrayHasEqualMapElement(array, key1, item1, b, mode, memo, comparator as any, innerStart, end)) return false;
    }
    end -= 1;
  }
  return true;
}

function mapEquiv(a: Map<unknown, unknown>, b: Map<unknown, unknown>, mode: Mode, memo: MemoState): boolean {
  let array: unknown[] | undefined;

  for (const [key2, item2] of b) {
    if (typeof key2 === "object" && key2 !== null) {
      if (array === undefined) {
        if (a.size === 1) {
          const [key1, item1] = a.entries().next().value as [unknown, unknown];
          return innerDeepEqual(key1, key2, mode, memo) && innerDeepEqual(item1, item2, mode, memo);
        }
        array = [];
      }
      array.push(key2);
    } else {
      // By directly retrieving the value we prevent another b.has(key2) check in
      // almost all possible cases.
      const item1 = a.get(key2);
      if ((item1 === undefined && !a.has(key2)) || !innerDeepEqual(item1, item2, mode, memo)) {
        if (mode !== kLoose) return false;
        // Fast path to detect missing string, symbol, undefined and null
        // keys.
        if (!mapMightHaveLoosePrim(a, b, key2, item2, memo)) return false;
        array ??= [];
        array.push(key2);
      }
    }
  }

  if (array === undefined) return true;
  if (mode === kPartial) return partialObjectMapEquiv(array, a, b, mode, memo);
  return mapObjectEquiv(array, a, b, mode, memo);
}

function partialSparseArrayEquiv(a: any, b: any, mode: Mode, memos: MemoState, startA: number, startB: number): boolean {
  let aPos = startA;
  const keysA = Object.keys(a);
  const keysB = Object.keys(b);
  const lenA = keysA.length - startA;
  const lenB = keysB.length - startB;
  if (lenA < lenB) return false;
  for (let i = 0; i < lenB; i++) {
    const keyB = keysB[startB + i]!;
    while (!innerDeepEqual(a[keysA[aPos]!], b[keyB], mode, memos)) {
      aPos++;
      if (aPos > keysA.length - lenB + i) return false;
    }
    aPos++;
  }
  return true;
}

function partialArrayEquiv(a: any, b: any[], mode: Mode, memos: MemoState): boolean {
  let aPos = 0;
  for (let i = 0; i < b.length; i++) {
    let isSparse = b[i] === undefined && !Object.hasOwn(b, i);
    if (isSparse) return partialSparseArrayEquiv(a, b, mode, memos, aPos, i);
    while (!(isSparse = a[aPos] === undefined && !Object.hasOwn(a, aPos)) &&
      !innerDeepEqual(a[aPos], b[i], mode, memos)) {
      aPos++;
      if (aPos > a.length - b.length + i) return false;
    }
    if (isSparse) return partialSparseArrayEquiv(a, b, mode, memos, aPos, i);
    aPos++;
  }
  return true;
}

function sparseArrayEquiv(a: any, b: any, mode: Mode, memos: MemoState, i: number): boolean {
  const keysA = Object.keys(a);
  const keysB = Object.keys(b);
  if (keysA.length !== keysB.length) return false;
  for (; i < keysB.length; i++) {
    const key = keysB[i]!;
    if ((a[key] === undefined && !Object.hasOwn(a, key)) || !innerDeepEqual(a[key], b[key], mode, memos)) {
      return false;
    }
  }
  return true;
}

function objEquiv(
  a: any, b: any, mode: Mode, keys1: Array<string | symbol> | undefined, keys2: Array<string | symbol>,
  memos: MemoState, iterationType: IterationType,
): boolean {
  // The pair must have equivalent values for every corresponding key.
  if (keys2.length > 0) {
    let i = 0;
    // Ordered keys
    if (keys1 !== undefined) {
      for (; i < keys2.length; i++) {
        const key = keys2[i]!;
        if (keys1[i] !== key) break;
        if (!innerDeepEqual(a[key], b[key], mode, memos)) return false;
      }
    }
    // Unordered keys
    for (; i < keys2.length; i++) {
      const key = keys2[i]!;
      // It is faster to get the whole descriptor and to check it's enumerable
      // property in V8 13.0 compared to calling Object.propertyIsEnumerable()
      // and accessing the property regularly.
      const descriptor = Object.getOwnPropertyDescriptor(a, key);
      if (descriptor === undefined || descriptor.enumerable !== true) return false;
      const value = descriptor.writable !== undefined ? descriptor.value : a[key];
      if (!innerDeepEqual(value, b[key], mode, memos)) return false;
    }
  }

  if (iterationType === kIsArray) {
    if (mode === kPartial) return partialArrayEquiv(a, b, mode, memos);
    for (let i = 0; i < a.length; i++) {
      if (b[i] === undefined) {
        if (!Object.hasOwn(b, i)) return sparseArrayEquiv(a, b, mode, memos, i);
        if ((a[i] !== undefined || !Object.hasOwn(a, i)) && (mode !== kLoose || a[i] !== null)) return false;
      } else if ((a[i] === undefined || !innerDeepEqual(a[i], b[i], mode, memos)) && (mode !== kLoose || b[i] !== null)) {
        return false;
      }
    }
  } else if (iterationType === kIsSet) {
    if (!setEquiv(a, b, mode, memos)) return false;
  } else if (iterationType === kIsMap) {
    if (!mapEquiv(a, b, mode, memos)) return false;
  }

  return true;
}

// Only handle cycles when they are detected.
let detectCycles = function (val1: unknown, val2: unknown, mode: Mode): boolean {
  try {
    return innerDeepEqual(val1, val2, mode, null);
  } catch {
    detectCycles = innerDeepEqual as unknown as typeof detectCycles;
    return innerDeepEqual(val1, val2, mode, undefined);
  }
};

export function isDeepEqual(val1: unknown, val2: unknown): boolean {
  return detectCycles(val1, val2, kLoose);
}

export function isDeepStrictEqual(val1: unknown, val2: unknown, skipPrototype?: boolean): boolean {
  return detectCycles(val1, val2, skipPrototype ? kStrictWithoutPrototypes : kStrict);
}

export function isPartialStrictEqual(val1: unknown, val2: unknown): boolean {
  return detectCycles(val1, val2, kPartial);
}