How to properly do deep clone and deep compare with JavaScript variables

Published on
Updated on

Cloning and comparing
Cloning and comparing

Introduction

Object cloning and deep comparison in JavaScript is an important topic because they are commonly used, while the developers oftentimes do this incorrectly (and even giving advice to inexperienced developers!) which can even lead to nasty and hard to debug bugs. So knowing how to properly clone and deeply compare is a thing that every JS developer must know.

Object cloning

Let's start with the object cloning since it's a more common problem.

What's wrong with JSON.stringify() / JSON.parse() approach?

The most common problem I see is that people oftentimes clone objects by converting it into JSON and parsing it back. This works most of the time and might even be appropriate in certain trivial situations. However, people oftentimes don't think about the potential problems of this approach.

This is where things can go wrong when doing JSON.stringify() / JSON.parse():

  1. JSON.stringify() doesn't support some values, such as NaN or undefined. They can be skipped or converted into null. For some data types, such as bigint, it will even throw exception.
  2. JSON.stringify() cannot work with objects that contain cyclic references: 
    const obj = {};
obj.selfReference = obj;
console.log(JSON.stringify(obj)); // exception
  3. Although usually not as serious as the first 2, but I must say it's not efficient for larger objects. It's slow and wastes a lot of memory.

The better approach with structuredClone()

Nowadays object cloning mostly become a much easier problem especially with the introduction of structuredClone(). All mainstream browsers have supported structuredClone() from 2022. structuredClone() is useful and very efficient for regular objects and most primitive data. It automatically handles self referencing structures as well. 

const obj = {};
obj.selfReference = obj;
const clonedObj = structuredClone(obj);
console.log(obj === clonedObj); // false, because it's a cloned object with a different memory address
console.log(clonedObj.selfReference === clonedObj); // true, because it has the same structure as obj (isomorphic to obj, i.e. as a graph)

That being said, structuredClone() has some limitations when you want to clone not so regular data structures:

  1. It can't copy functions or DOM nodes. Will throw DataCloneError if encounters such thing.
  2. The object prototype (__proto__) will be replaced with the standard prototype for custom classes.
  3. Object private fields are not cloned.
  4. Setters are lost and getters are converted into regular properties.
  5. Other smaller things listed here,

Custom cloning

It's recommended to use structuredClone() as much as possible because it has built-in support for most data structures, including Set and Map. However beyond regular data structures (for example, for the already mentioned functions) structuredClone() will not work, and I would even say rightfully, because there is no universally correct way to do that.

But let's say, you want to support custom class objects (with no private properties) and DOM nodes while avoiding structuredClone() errors.

It can be done like this:

function customClone(obj) {
	const clonedObjects = new WeakMap();

	function cloneRecursively(obj) {
		// Return if it's a non object type
		if (typeof obj !== 'object' || obj === null) {
			return obj;
		}

		let clonedObject = clonedObjects.get(obj);

		if (clonedObject) {
			// Return the associated cloned object if exists to ensure that the structure
			// is isomorphic to the original object and avoid infinite recursion
			return clonedObject;
		}

		// structuredClone() can handle these types
		const canBeClonedWithStructuredClone = 
			ArrayBuffer.isView(obj) || obj instanceof ArrayBuffer ||
			obj instanceof RegExp || obj instanceof Date || obj instanceof Number ||
			obj instanceof Boolean || obj instanceof String || obj instanceof Error;

		if (canBeClonedWithStructuredClone) {
			clonedObject = structuredClone(obj);
		} else if (Array.isArray(obj)) {
			clonedObject = [];
		} else if (obj instanceof Map) {
			clonedObject = new Map();
		} else if (obj instanceof Set) {
			clonedObject = new Set();
		} else if (globalThis.Node && obj instanceof Node) {
			clonedObject = obj.cloneNode(true);
		} else {
			// When creating, copy the prototype in order to make it the same instance
			clonedObject = Object.create(Object.getPrototypeOf(obj));
		}

		// We need to associate the clonedObject with obj before filling
		// clonedObject to ensure that no infinite recursion will occur
		// if obj is encountered again somewhere deeper
		clonedObjects.set(obj, clonedObject);

		if (Array.isArray(obj)) {
			for (const x of obj) {
				clonedObject.push(cloneRecursively(x));
			}
		} else if (obj instanceof Map) {
			for (const x of obj) {
				clonedObject.set(cloneRecursively(x[0]), cloneRecursively(x[1]));
			}
		} else if (obj instanceof Set) {
			for (const x of obj) {
				clonedObject.add(cloneRecursively(x));
			}
		} else if (!(globalThis.Node && obj instanceof Node || canBeClonedWithStructuredClone)) {
			const descriptors = Object.getOwnPropertyDescriptors(obj);

			for (const key in descriptors) {
				// Cloning only values if they exist, if 
				// we add the value property an error will occur
				if ('value' in descriptors[key]) {
					descriptors[key].value = cloneRecursively(descriptors[key].value);
				}
			}

			Object.defineProperties(clonedObject, descriptors);
		}

		return clonedObject;
	}

	return cloneRecursively(obj);
}

This won't work ideally for any type (for example, some native classes like WeakMap will become corrupted, or private fields will not be copied), but it's good enough for adding support for most regular class objects and DOM nodes. There are some libraries that also support deep cloning, such as Lodash. But as I stated, there is no perfect clone function.

Keep in mind, there is no way to perfectly clone functions (fine to reuse the ones from prototype since they are not attached to one particular instance object, but in reality, functions might be attached to some data, so, just copying the references will not solve the problem) or private fields. Again, this isn't an ideal general purpose cloner, there are tons of unhandled / ignored cases (such as symbols, array holes, etc), you might need to change / extend it, depending on your project specifics.

Deep compare

Okay, we've sorted out deep copying. Now what about deep comparison? It's also an important thing, although slightly less commonly used. Unlike deep cloning, there is no built-in function for that. There are only libraries, like the already mentioned Lodash. As with deep cloning, there is absolutely no 100% right way to do that. Some variations might work well for specific cases. We'll try to implement a generic one that also checks if the compared objects are isomorphic (have the same structure as a graph).

This is how it will probably look like: 

function customCompare(objA, objB) {
	const matchingObjectsAtoB = new WeakMap();
	const matchingObjectsBtoA = new WeakMap();

	function compareRecursively(objA, objB) {
		// If types mismatch return false 
		// Note, this doesn't yet handle null where typeof null is also "object"
		// null is handled in the next comparison below
		if (typeof objA !== typeof objB) {
			return false;
		}

		// If some of the arguments is non object just compare the values
		// Note, NaN === NaN is false, so this is handled in a special way
		if (typeof objA !== 'object' || objA === null || objB === null) {
			return objA === objB || (typeof objA === 'number' && isNaN(objA) && isNaN(objB));
		}

		const matchingObjB = matchingObjectsAtoB.get(objA);
		const matchingObjA = matchingObjectsBtoA.get(objB);

		if (matchingObjB || matchingObjA) {
			// If objA matched with objB, objA should always match with objB, and vice versa
			return objB === matchingObjB && objA === matchingObjA;
		}

		// We need to associate objA with objB (and vice versa) before checking deeper to
		// ensure that no infinite recursion will occur in the case of objA
		// reoccurrence when checking deeper
		matchingObjectsAtoB.set(objA, objB);
		matchingObjectsBtoA.set(objB, objA);

		// Check if prototypes match to ensure that they are the same class instances
		if (Object.getPrototypeOf(objA) !== Object.getPrototypeOf(objB)) {
			return false;
		} else if (objA instanceof RegExp) {
			return objA.toString() === objB.toString();
		} else if (objA instanceof Boolean || objA instanceof Number || objA instanceof String) {
			return objA.valueOf() === objB.valueOf();
		} else if (globalThis.HTMLElement && objA instanceof HTMLElement) {
			return objA.outerHTML === objB.outerHTML;
		} else if (globalThis.Node && objA instanceof Node) {
			return objA.textContent === objB.textContent;
		} else if (objA instanceof Date) {
			return objA.getTime() === objB.getTime();
		} else if (Array.isArray(objA)) {
			if (objA.length !== objB.length) {
				return false;
			}

			for (let i = 0; i < objA.length; ++i) {
				if (!compareRecursively(objA[i], objB[i])) {
					return false;
				}
			}
		} else if (objA instanceof Set) {
			if (objA.size !== objB.size) {
				return false;
			}

			const keysA = objA.keys();
			const keysB = objB.keys();

			while (true) {
				// For sets the order of keys should also match
				// Since keys can be objects, it's much more complicated
				// to match them (requires checking each pair)
				const resA = keysA.next(), resB = keysB.next();

				if (resA.done) {
					break;
				}


				if (!compareRecursively(resA.value, resB.value)) {
					return false;
				}
			}
		} else if (objA instanceof Map) {
			if (objA.size !== objB.size) {
				return false;
			}

			const entriesA = objA.entries();
			const entriesB = objB.entries();

			while (true) {
				// For maps the order of keys should also match
				// Since keys can be objects, it's much more complicated
				// to match them (requires checking each pair)
				const resA = entriesA.next(), resB = entriesB.next();

				if (resA.done) {
					break;
				}


				if (!compareRecursively(resA.value, resB.value)) {
					return false;
				}
			}
		} else {
			const descriptorsA = Object.getOwnPropertyDescriptors(objA);
			const descriptorsB = Object.getOwnPropertyDescriptors(objB);

			for (const key in descriptorsB) {
				if (!Object.hasOwn(descriptorsA, key)) {
					return false;
				}
			}

			for (const key in descriptorsA) {
				if (!Object.hasOwn(descriptorsB, key)) {
					return false;
				}

				const descriptorA = descriptorsA[key];
				const descriptorB = descriptorsB[key];

				// The descriptors should match 
				if (
					descriptorA.configurable !== descriptorB.configurable ||
					descriptorA.enumerable !== descriptorB.enumerable ||
					descriptorA.writable !== descriptorB.writable ||
					descriptorA.get !== descriptorB.get ||
					descriptorA.set !== descriptorB.set ||
					!compareRecursively(descriptorA.value, descriptorB.value)
				) {
					return false;
				}
			}
		}

		return true;
	}

	return compareRecursively(objA, objB);
}

As with cloning, it's not perfect, but it's fine in most cases. It also supports wrapper objects, Set, Map, RegExp, Node, Date and HTMLElement.

Again, this isn't an ideal general purpose comparator, there are tons of unhandled / ignored cases (such as symbols, array holes, etc), you might need to change / extend it, depending on your project specifics.

Proposal for Records & Tuples (withdrawn)

There was a proposal for Records & Tuples, which reached to stage 2. It could create a native mechanism for deep comparisons which meant a lot of potentials for optimizations. Unfortunately, it was withdrawn for several reasons. However there is a new alternative proposal for Composites. Let's see where it goes.



Read previous


UP
This site uses cookies. By continuing to use this website, you agree to their use. To find out more, including how to control cookies, see here: Privacy & cookies.