Collected · dequal · MIT

Temporary exhibition · Hall of the Commons

Are These the Same?

JavaScript·2019·84 lines·1909 bytes

var has = Object.prototype.hasOwnProperty;

function find(iter, tar, key) {
	for (key of iter.keys()) {
		if (dequal(key, tar)) return key;
	}
}

export function dequal(foo, bar) {
	var ctor, len, tmp;
	if (foo === bar) return true;

	if (foo && bar && (ctor=foo.constructor) === bar.constructor) {
		if (ctor === Date) return foo.getTime() === bar.getTime();
		if (ctor === RegExp) return foo.toString() === bar.toString();

		if (ctor === Array) {
			if ((len=foo.length) === bar.length) {
				while (len-- && dequal(foo[len], bar[len]));
			}
			return len === -1;
		}

		if (ctor === Set) {
			if (foo.size !== bar.size) {
				return false;
			}
			for (len of foo) {
				tmp = len;
				if (tmp && typeof tmp === 'object') {
					tmp = find(bar, tmp);
					if (!tmp) return false;
				}
				if (!bar.has(tmp)) return false;
			}
			return true;
		}

		if (ctor === Map) {
			if (foo.size !== bar.size) {
				return false;
			}
			for (len of foo) {
				tmp = len[0];
				if (tmp && typeof tmp === 'object') {
					tmp = find(bar, tmp);
					if (!tmp) return false;
				}
				if (!dequal(len[1], bar.get(tmp))) {
					return false;
				}
			}
			return true;
		}

		if (ctor === ArrayBuffer) {
			foo = new Uint8Array(foo);
			bar = new Uint8Array(bar);
		} else if (ctor === DataView) {
			if ((len=foo.byteLength) === bar.byteLength) {
				while (len-- && foo.getInt8(len) === bar.getInt8(len));
			}
			return len === -1;
		}

		if (ArrayBuffer.isView(foo)) {
			if ((len=foo.byteLength) === bar.byteLength) {
				while (len-- && foo[len] === bar[len]);
			}
			return len === -1;
		}

		if (!ctor || typeof foo === 'object') {
			len = 0;
			for (ctor in foo) {
				if (has.call(foo, ctor) && ++len && !has.call(bar, ctor)) return false;
				if (!(ctor in bar) || !dequal(foo[ctor], bar[ctor])) return false;
			}
			return Object.keys(bar).length === len;
		}
	}

	return foo !== foo && bar !== bar;
}

Curator’s note

A function that answers the question every program asks and almost no language answers well: are these two values the same?

JavaScript offers ===, which compares references for objects, so two identical arrays are not equal to each other. Everything past that is left to you, and this is what "everything past that" actually costs — eighty lines, and they are not padding.

Read what it has to know about. Dates compare by their time value, not their fields. Regular expressions compare by their source text. Sets are unordered, so a member of one has to be *searched for* in the other rather than looked up, which is why find exists at the top and why comparing two sets of objects is quadratic. Maps need the same treatment for their keys and then a recursive comparison of their values. Typed arrays compare bytes. And an ArrayBuffer is converted to a Uint8Array first, because you cannot index into a buffer directly.

Notice while (len-- && dequal(foo[len], bar[len])); — an empty loop body, walking backwards, whose exit condition is the answer. The line after it, return len === -1, is true only if the loop ran all the way down. It is dense and it is exactly right, which is a combination this hall sees often.

The last line is the one to take away. return foo !== foo && bar !== bar is true for precisely one pair of values in the language: two NaNs. Having walked every structure JavaScript has, the function ends by admitting that the only remaining case is the value that is famously not equal to itself — and deciding, reasonably, that two of them are the same.

Elsewhere in the museum