Alternative assertion for unordered deep comparisons

[goteguru]

deepEqual take insertation order in account for Sets and Maps but not for Objects. Therefore t.deepEqual(new Set([1,2]), new Set([2,1]) will fail while t.deepEqual({a:1, b:2}, {b:2, a:1}) succeed. Container classes should obey the same rules, same assertations should work the same for all containers.

I understand object iteration order is undefined (arbitrary) according to MDN, while Sets and Maps are OrderedSets and OrderedMaps in javascript. Probably this is the basis of the current implementation, but please be aware that order of Object.getOwnPropertyNames, Object.getOwnPropertySymbols and Reflect.ownKeys return values are defined in ES6 therefore elements of objects are pretty much ordered.

The current assertation rules are unfortunately inconsistent for containers, and there is no (easy) way to test (unordered) Sets and Maps.

Sets are usually used as mathematical sets, where ordering shouldn't matter. Also Maps are used as generic containers, trees, caches where failing on order difference is more like a bug than a feature. To be honest there are very few, rare edge-cases where one would like to test for Map/Set ordering (eliminating duplicates from arrays is the only one came into my mind). If one would need ordering, insertion order is almost certainly won't suffice and some more advanced structure like red-black tree or alike will be implemented instead anyway).

Ideal solution would be if ES would have both Sets and OrderedSets, but unfortunately this is not the case. Changing deepEqual implementation certainly would break some existing test cases, which is very unfortunate. Therefore probably the only viable way is to add a new assertation rule for unordered cases and document the fact Object are not considered ordered collections.

[novemberborn]

Therefore probably the only viable way is to add a new assertation rule for unordered cases

This sounds good. Would this be a deep or shallow comparison? Shallow will be easier to implement.

[goteguru]

Nomen est omen. Given the name I don't think we have a choice. But we can have a distinct unorderedDeepEqual and unorderedEqual, however I'd prefer a much simpler api like eq, ordEq where eq defined as logical equality (following haskell's nomeclature), similar to deepEqual but unordered for Set and Map by default (ordEq is the ordered variant). Logical equality is foreign to JS, but (I believe) very useful for testing. In case of testing it's very improbable I'd like to test actual and expected are the exact same object (t.is) it's much more likely I'd like to know they contain the same (expected) values or not.

[novemberborn]

The comparisons are implemented in a separate library, adding an unordered mode will be a lot of work. A shallow algorithm could be implemented in AVA itself, more easily. Perhaps t.sameOrder()?

[goteguru]

The comparisons are implemented in a separate library, adding an unordered mode will be a lot of work. A shallow algorithm could be implemented in AVA itself, more easily. Perhaps t.sameOrder()?

Yes. It's using concordance. I thought that is a sideproject of ava. (It would be nice if concordance would have an option to change equality criteria, but it have not). Recursive (deep) comparison is not that difficult. Creating (good) diffs is cumbersome. If shallow equality implemented in AVA itself we'll lose the diffs.

Recursively reordering keys before comparison would be an option, but destroys memory in case of large objects (and probably slow). Still, it might be useful for smaller sets. What do you think?

[novemberborn]

If shallow equality implemented in AVA itself we'll lose the diffs.

We could still print well-formatted extraneous and missing entries. And for maps a diff of equal keys with unequal values.

Recursively reordering keys before comparison would be an option, but destroys memory in case of large objects (and probably slow). Still, it might be useful for smaller sets. What do you think?

We'd have to copy both sides of the comparison, which we can't if it involves non-native object instances (custom classes, subclasses etc).

[goteguru]

We'd have to copy both sides of the comparison, which we can't if it involves non-native object instances (custom classes, subclasses etc).

We can't? Why? There are no (real) classes in JS. A custom class is just a tuple of a constructor function and a prototype object. Functions are native objects and the prototype is just a hierarchic collection of native objects and primitives. It wouldn't be a problem to copy them by running their constructor and copy the props, but I think it's not even necessary. Logical equality certainly fails if the two objects have different prototypes. They are different "type" then. Therefore the logical eq could be something like this:

1. compare the prototype -> if not equal the objects are trivially not equal.
2. compare enumerable props recursively.

We must reorder only one of the objects not both. Reordering don't have to be alphanumeric. However side effect during testing is undesirable therefore it should be a deep clone.

However a shallow unordered comparison is much better than no comparison. It could be used for sets and maps. But what should be the name? t.sameOrder() doesn't seem to be fitting since the order will be ignored (and not the same).

[novemberborn]

Deeply copying instances so we can hand them to Concordance seems like an approach that would fail in surprising ways, depending on how the code under test is constructed. So I'd rather focus on maps/sets/objects/arrays.

And yes sameOrder is the wrong name, ha! unorderedEqual?

[tommy-mitchell]

@novemberborn I'd like to help get a t.unorderedEqual assertion added, do you remember what you were thinking of for the shallow equal?

[novemberborn]

Re-reading this I think there are two use cases over deepEqual(): when called with a Map instance, and with a Set instance.

For an unordered comparison, both actual and expected values must have the same size and the same keys, but the order of those keys does not matter.

Keys and values themselves should be compared using Concordance's comparison method, in line with the other assertion methods. However this is an ordered comparison (which is the problem!).

By shallow I mean that only the map keys, or array / set values, are compared without respect for their order.

[tommy-mitchell]

Here's a dirty first draft of this (only supports comparing maps to maps, or sets to sets or arrays):

unordered-equal.js

This is a helper file (like like-selector.js) that gets info about actual and expected regardless of their type:

export const checkValueForUnorderedEqual = value => {
	const type = (
		value instanceof Map ? 'map' :
		value instanceof Set ? 'set' :
		Array.isArray(value) ? 'array' :
		'invalid'
	);

	if (type === 'invalid') {
		return {isValid: false};
	}

	return {
		isValid: true,
		type: type === 'map' ? 'map' : 'set-like',
		size: type === 'map' || type === 'set'
			? value.size
			: value.length,
	};
};

assert.js

this.unorderedEqual = withSkip((actual, expected, message) => {
	if (!checkMessage('unorderedEqual', message)) {
		return false;
	}

	const actualInfo = checkValueForUnorderedEqual(actual);

	if (!actualInfo.isValid) {
		fail(new AssertionError({
			assertion: 'unorderedEqual',
			improperUsage: true,
			message: '`t.unorderedEqual` only compares Maps, Sets, and arrays',
			values: [formatWithLabel('Called with:', actual)],
		}));
		return false;
	}

	const expectedInfo = checkValueForUnorderedEqual(expected);

	if (!expectedInfo.isValid) {
		fail(new AssertionError({
			assertion: 'unorderedEqual',
			improperUsage: true,
			message: '`t.unorderedEqual` only compares Maps, Sets, and arrays',
			values: [formatWithLabel('Called with:', expected)],
		}));
		return false;
	}

	if (actualInfo.size !== expectedInfo.size) {
		fail(new AssertionError({
			assertion: 'unorderedEqual',
			message: 'size must be equal',
		}));
		return false;
	}

	if (actualInfo.type === 'map') {
		if (expectedInfo.type !== 'map') {
			fail(new AssertionError({
				assertion: 'unorderedEqual',
				message: 'both must be maps',
			}));
			return false;
		}

		const comparedKeysResult = concordance.compare(actual.keys, expected.keys, concordanceOptions);
		if (!comparedKeysResult.pass) {
			fail(new AssertionError({
				assertion: 'unorderedEqual',
				message: 'keys must be equal',
			}));
			return false;
		}

		for (const [key, value] of actual.entries()) {
			const result = concordance.compare(value, expected.get(key), concordanceOptions);
			if (!result.pass) {
				fail(new AssertionError({
					assertion: 'unorderedEqual',
					message: 'all values must be equal',
				}));
				return false;
			}
		}

		pass();
		return true;
	}

	// Assume set/array

	if (expectedInfo.type === 'map') {
		fail(new AssertionError({
			assertion: 'unorderedEqual',
			message: 'both must be set-likes',
		}));
		return false;
	}

	// Set-set can be compared w concordance
	// what ab array-array or array-set?
});

I'm not super familiar with formatting AssertionErrors or working with concordance, but I've mostly focused on the rough shape of the algorithm.

Thoughts? Especially in regards to comparing set-like values.

[novemberborn]

@tommy-mitchell looks good. The detail is which value you print in the assertion error but that's secondary to having the assertion logic itself.