blob: 3e41e61ff6065d55c972ba2c89fbdf76a81c428e [file] [log] [blame]
/**
* @license
* Copyright 2021 Google LLC
* SPDX-License-Identifier: Apache-2.0
*/
// NOTE: This algorithm has the following limitations:
// It does not support deep-value-equality of values in sets that are not
// `===`. The same applies for keys in a map.
export function deepEqual<T>(a: T, b: T): boolean {
// The pairs of objects that are currently being compared. If a pair is
// encountered again while on the stack, we shouldn't go any deeper, as we
// would only be walking through same pairs again infinitely. Such pairs are
// equal as long as all non-recursive pairs are equal, ie. given an infinite
// traversal we would've never reached a pair of values that are not equal to
// each other.
const onStackValuePair = new Map<unknown, Set<unknown>>();
// Cache of compared object instances. This allows as to avoid comparing same
// pair of large objects repeatedly in cases where the reference to the same
// object is stored in many different attributes in the tree.
const equalValues = new Map<unknown, Set<unknown>>();
function deepEqualImpl(a: unknown, b: unknown) {
if (a === b) return true;
if (a === undefined || b === undefined) return false;
if (a === null || b === null) return false;
if (a instanceof Date || b instanceof Date) {
if (!(a instanceof Date && b instanceof Date)) return false;
return a.getTime() === b.getTime();
}
// Check cache first for container types.
if (equalValues?.get(a)?.has(b)) return true;
if (a instanceof Set || b instanceof Set) {
if (!(a instanceof Set && b instanceof Set)) return false;
if (a.size !== b.size) return false;
for (const ai of a) if (!b.has(ai)) return false;
equalValues.set(a, (equalValues.get(a) ?? new Set()).add(b));
return true;
}
if (a instanceof Map || b instanceof Map) {
if (!(a instanceof Map && b instanceof Map)) return false;
if (a.size !== b.size) return false;
if (onStackValuePair.get(a)?.has(b)) return true;
onStackValuePair.set(a, (onStackValuePair.get(a) ?? new Set()).add(b));
for (const [aKey, aValue] of a.entries()) {
if (!b.has(aKey) || !deepEqualImpl(aValue, b.get(aKey))) return false;
}
onStackValuePair.get(a)!.delete(b);
equalValues.set(a, (equalValues.get(a) ?? new Set()).add(b));
return true;
}
if (typeof a === 'object') {
if (typeof b !== 'object') return false;
if (onStackValuePair.get(a)?.has(b)) return true;
onStackValuePair.set(a, (onStackValuePair.get(a) ?? new Set()).add(b));
const aObj = a as Record<string, unknown>;
const bObj = b as Record<string, unknown>;
const aKeys = Object.keys(aObj);
const bKeys = Object.keys(bObj);
if (aKeys.length !== bKeys.length) return false;
for (const key of aKeys) {
if (!deepEqualImpl(aObj[key], bObj[key])) return false;
}
onStackValuePair.get(a)!.delete(b);
equalValues.set(a, (equalValues.get(a) ?? new Set()).add(b));
return true;
}
return false;
}
return deepEqualImpl(a, b);
}
export function notDeepEqual<T>(a: T, b: T): boolean {
return !deepEqual(a, b);
}
/**
* @param obj Object
*/
export function deepClone<T>(obj: T): T {
if (!obj) throw new Error('undefined object for deepClone');
return JSON.parse(JSON.stringify(obj)) as T;
}