Record proposal: collection members

[Timovzl]

The proposal for records does not address collections.

At some point, however, people are going to use records that contain collections, wanting recursive structural equality on their elements. If such an implementation is not covered by records, people will start rolling their own. In fact, this might be tricky for a developer to retrofit onto records, so people may even substitute records entirely.

Special-casing collections seems to me like an important part of a successful record type.

Having been working extensively on a library for structural equality (such as to implement Domain-Driven Design's "Value Objects"), I have studied this case quite thoroughly. I propose the following special cases (code samples further below):

• Fields whose compile-time type is or implements IReadOnlyCollection<TKey, TValue> or IDictionary<TKey, TValue> for a single set or generic type parameters are special-cased.
  • For each key in the left dictionary, the right dictionary must contain it (honoring its equality comparer), and the values must be equal recursively (which means they are essentially treated just like the record's fields, and might even recursively follow the special cases here).
  • The same must be true with left and right reversed. (Note how a case-sensitive dictionary containing a and A is structurally equal to a case-insensitive dictionary containing only a!)
• Fields whose compile-time type is or implements ILookup<TKey, TElement> for a single set of generic type parameters are special-cased.
  • The lookups are compared in the same way as dictionaries.
  • Instead of values, a lookup has elements under a key, and they are enumerable. Enumerate each enumerable once. Compare them recursively according to the special case for enumerables below.
• Fields whose compile-time type is or implements IGrouping<TKey, TElement> for a single set of generic type parameters are special-cased
  • Compare the keys recursively, just like a record's fields.
  • The grouping's elements are enumerable. Enumerate each enumerable once. Compare them recursively according to the special case for enumerables below.
• Fields whose compile-time type is or implements IEnumerable are special-cased.
  • If the runtime objects implement IReadOnlyList<T> for exactly one T, the Count properties must match, and we index directly to the elements, recursing, comparing them in the same way we compare fields. The elements must be equal. (Note how this avoids the allocation of an enumerator. It is good to avoid allocations during equality comparisons.)
  • If the left runtime object implements ISet<T>, then we could call SetEquals(right) on it. We might need to call the method in the other direction as well. (TODO: Check.) However, this makes the implementation different than the other cases described here, since the set elements aren't treated the same way as the record's fields. Instead, it might be better to treat the set's elements the same way as dictionary keys (described above). This does risk a quadratic-time implementation for sets with linear-time Contains.
  • If the runtime object implements IReadOnlyCollection<T> (i.e. it is materialized) for exactly one T, the Count properties must match, and we enumerate the elements, recursing, comparing them in the same way we compare a record's fields. The elements must be equal.
  • If the runtime object implements IEnumerable<T> (i.e. it is generic) for exactly one T, we enumerate the elements, recursing, comparing them in the same way we compare fields. The elements must be equal, and the enumerables must contain the same number of elements.
  • Otherwise, we enumerate the elements as objects and call Object.Equals(leftElement, rightElement) on each pair. The elements must be equal, and the enumerables must contain the same number of elements. (Since we do not know the element type at compile time, we cannot recurse and treat the elements the same way as the record's field. As an alternative, we could throw, since we cannot treat this case in a way analogous to other collections.)
• Fields whose compile-time type is Memory<T>, ReadOnlyMemory<T>, Memory<T>?, or ReadOnlyMemory<T>? are special-cased, similar to IEnumerables, and indexing directly to the elements.

Custom overrides. An additional consideration is to ignore the above rules if the compile-time type of one of the above has a more specific override of Equals and GetHashCode than the one inherited from Object. This keeps the developer able to customize the equation, even though this is likely a rare requirement. It would be cleaner, but more difficult/expensive to check the runtime type instead.

Same generic interface for multiple type parameters. The above remarks "for exactly one T" and "for a single set of type parameters" are needed to determine what to do for types that implement a generic collection interface for multiple types. We prefer the most specific or most strongly materialized interface that is implemented for only a single [set of] generic type parameter[s]. This can (and even needs to) be determined at compile time. All the other type checks on IEnumerable types should be done at runtime, as clarified by the code sample below.

Hash codes. Clearly, the hash code implementations should follow the same rules. However, they can take shortcuts by allowing false positives in the uncommon case. For example, the hash code of an IReadOnlyList<T> can be comprised of its Count combined with its first and last element's hash codes (if present). This keeps it fairly likely for the hash code to change if the collection changes, while making the implementation cheaper.

Non-indexable but materialized collections (IReadOnlyCollection<T> in the absence of IReadOnlyList<T>) could simply base the hash code on their count properties. This is likely to yield more false positives than the case above, though.

Unmaterialized collections (IEnumerable<T>) are tricky, since their elements can only be accessed by allocating an enumerator. For equality this is a necessity, but for hash codes it is possible to return a constant. This is likely to yield more false positive than the case above, though.

Strings. Strings already have the desired equality and hash code calculation. For long strings, it might be beneficial to optimize the hash code calculation, e.g. similar to how we optimize it for IReadOnlyList<T>.

Code samples

The code samples show the runtime decisions. Other decisions described above can and probably should be made at compile time.

/// <param name="nullSafeEquals">A function that returns the equality between two given elements.</param>
public static bool EnumerableEquals(IEnumerable? left, IEnumerable? right, Func<TElement, TElement, bool> nullSafeEquals)
{
	if (ReferenceEquals(left, right)) return true;
	if (left is null || right is null) return false;

	// Prefer to index directly, to avoid allocation of an enumerator
	if (left is IReadOnlyList<TElement> leftIndexable && right is IReadOnlyList<TElement> rightIndexable)
		return IndexableEquals(leftIndexable, rightIndexable, nullSafeEquals);
	// Honor sets, which may be order-agnostic or dictate the equality comparer (the left side is leading, matching the asymmetry in HashSet<T>.SetEquals and our dictionary and lookup implementations)
	else if (left is ISet<TElement> leftSet && right is IEnumerable<TElement> rightSetComparand)
		return leftSet.SetEquals(rightSetComparand);
	else if (left is IReadOnlyCollection<TElement> leftCollection && right is IReadOnlyCollection<TElement> rightCollection)
		return CollectionEquals(leftCollection, rightCollection, nullSafeEquals);
	else if (left is IEnumerable<TElement> leftEnumerable && right is IEnumerable<TElement> rightEnumerable)
		return GenericEnumerableEquals(leftEnumerable, rightEnumerable, nullSafeEquals);
	else
	{
		System.Diagnostics.Debug.Assert(typeof(TElement) == typeof(object)); // For non-generic IEnumerables, we always use object as the type param for this internal method
		return EnumerableEquals(left, right, nullSafeEquals);
	}

	// Local function that compares key-value indexable collections
	static bool IndexableEquals(IReadOnlyList<TElement> leftIndexable, IReadOnlyList<TElement> rightIndexable, Func<TElement, TElement, bool> nullSafeElementEqualsFunction)
	{
		if (leftIndexable.Count != rightIndexable.Count) return false;
		for (var i = 0; i < leftIndexable.Count; i++)
			if (!nullSafeElementEqualsFunction(leftIndexable[i], rightIndexable[i])) return false;
		return true;
	}

	// Local function that compares materialized collections
	static bool CollectionEquals(IReadOnlyCollection<TElement> leftCollection, IReadOnlyCollection<TElement> rightCollection, Func<TElement, TElement, bool> nullSafeElementEqualsFunction)
	{
		if (leftCollection.Count != rightCollection.Count) return false;
		var rightEnumerator = rightCollection.GetEnumerator();
		using (rightEnumerator as IDisposable)
		{
			foreach (var leftElement in leftCollection)
			{
				rightEnumerator.MoveNext();
				if (!nullSafeElementEqualsFunction(leftElement, rightEnumerator.Current)) return false;
			}
			return true;
		}
	}

	// Local function that compares generic enumerables
	static bool GenericEnumerableEquals(IEnumerable<TElement> leftEnumerable, IEnumerable<TElement> rightEnumerable, Func<TElement, TElement, bool> nullSafeElementEqualsFunction)
	{
		var rightEnumerator = rightEnumerable.GetEnumerator();
		using (rightEnumerator as IDisposable)
		{
			foreach (var leftElement in leftEnumerable)
				if (!rightEnumerator.MoveNext() || !nullSafeElementEqualsFunction(leftElement, rightEnumerator.Current)) return false;
			if (rightEnumerator.MoveNext()) return false;
			return true;
		}
	}

	// Local function that compares non-generic enumerables
	static bool EnumerableEquals(IEnumerable leftEnumerable, IEnumerable rightEnumerable, Func<TElement, TElement, bool> nullSafeElementEqualsFunction)
	{
		System.Diagnostics.Debug.Assert(typeof(TElement) == typeof(object));

		var rightEnumerator = rightEnumerable.GetEnumerator();
		using (rightEnumerator as IDisposable)
		{
			foreach (var leftElement in leftEnumerable)
				if (!rightEnumerator.MoveNext() || !Object.Equals(leftElement, rightEnumerator.Current)) return false;
			if (rightEnumerator.MoveNext()) return false;
			return true;
		}
	}
}

/// <param name="nullSafeGetHashCode">A function that returns the hash code for a given element. Invoked only for types that implement <see cref="IReadOnlyList{T}"/>.</param>
public static int GetEnumerableHashCode(IEnumerable? enumerable, Func<TElement, int> nullSafeGetHashCode)
{
	// Prefer to use the count, first element, and last element (if IReadOnlyList, without string elements, to avoid casing complications)
	if (enumerable is IReadOnlyList<TElement> list && list.Count > 0)
	{
		unchecked
		{
			return ((ComparisonConstants.HashCodeInitialValue
				** ComparisonConstants.HashCodeMultiplier + list.Count)
				** ComparisonConstants.HashCodeMultiplier + nullSafeGetHashCode(list[0]))
				** ComparisonConstants.HashCodeMultiplier + nullSafeGetHashCode(list[^1]);
		}
	}
	// Prefer to use the count (if IReadOnlyCollection)
	else if (enumerable is IReadOnlyCollection<TElement> collection)
	{
		unchecked
		{
			return 1 + collection.Count; // Keep 0 available for null
		}
	}
	// Otherwise, use a constant
	else
	{
		return -1;
	}
}

/// <param name="nullSafeValueEquals">A function that returns the equality between two given values from the dictionaries.</param>
public static bool DictionaryEquals(IReadOnlyDictionary<TKey, TValue>? left, IReadOnlyDictionary<TKey, TValue>? right, Func<TValue, TValue, bool> nullSafeValueEquals)
{
	if (ReferenceEquals(left, right)) return true;
	if (left is null || right is null) return false;

	foreach (var rightPair in right)
	{
		if (!left.TryGetValue(rightPair.Key, out var leftValue) || !nullSafeValueEquals(leftValue, rightPair.Value))
			return false;
	}
	foreach (var leftPair in left)
	{
		if (!right.TryGetValue(leftPair.Key, out var rightValue) || !nullSafeValueEquals(rightValue, leftPair.Value))
			return false;
	}
	return true;
}

/// <param name="nullSafeValueEquals">A function that returns the equality between two given values from the dictionaries.</param>
public static bool DictionaryEquals(IDictionary<TKey, TValue>? left, IDictionary<TKey, TValue>? right, Func<TValue, TValue, bool> nullSafeValueEquals)
{
	if (ReferenceEquals(left, right)) return true;
	if (left is null || right is null) return false;

	foreach (var rightPair in right)
	{
		if (!left.TryGetValue(rightPair.Key, out var leftValue) || !nullSafeValueEquals(leftValue, rightPair.Value))
			return false;
	}
	foreach (var leftPair in left)
	{
		if (!right.TryGetValue(leftPair.Key, out var rightValue) || !nullSafeValueEquals(rightValue, leftPair.Value))
			return false;
	}
	return true;
}

/// <param name="nullSafeValueEquals">A function that returns the equality between two given values from matching groups in the lookups.</param>
public static bool LookupEquals(ILookup<TKey, TElement>? left, ILookup<TKey, TElement>? right, Func<TElement, TElement, bool> nullSafeValueEquals)
{
	if (ReferenceEquals(left, right)) return true;
	if (left is null || right is null) return false;
	
	foreach (var rightGroup in right)
	{
		using var rightGroupEnumerator = rightGroup.GetEnumerator();
		foreach (var leftElement in left[rightGroup.Key])
			if (!rightGroupEnumerator.MoveNext() || !nullSafeValueEquals(rightGroupEnumerator.Current, leftElement))
			return false;
	}
	foreach (var leftGroup in left)
	{
		using var leftGroupEnumerator = leftGroup.GetEnumerator();
		foreach (var rightElement in right[leftGroup.Key])
			if (!leftGroupEnumerator.MoveNext() || !nullSafeValueEquals(leftGroupEnumerator.Current, rightElement))
				return false;
	}
	return true;
}

[HaloFour]

This sounds like it belongs on the csharplang repo since it impacts the language specification.

IMO, records will consider the equality of its members based on how the types of those members determine equality. If you want value equality based on collections, use collections that are based on value equality and implement their own Equals/GetHashCode methods. Having the compiler specifically recognize and generate alternate semantics for specific collection types not only means that the compiler would have to have intimate knowledge of a large quantity of types, it also makes it awkward for the compiler to recognize and support overridden equality semantics for a member of one of those types, e.g. your own Dictionary<string, TValue> that might handle the keys in a case-insensitive manner. It also makes the language asymmetric if the records consider those collections as equivalent but those collections themselves don't.

[CyrusNajmabadi]

Hi @Timovzl I've transferred this issue to the right repo. Thanks!

[Timovzl]

@HaloFour You make a valid point. I had considered it, except for the last part: "It also makes the language asymmetric if the records consider those collections as equivalent but those collections themselves don't."

In any case, I'm wondering out loud if that solution is sufficient, in practice. Do you know of any collection types that implement structural equality? Would most developers you know of be aware that adding an array or list member stops their record from showing the desired equality behavior?

[YairHalberstadt]

Records have already shipped, so it's too late to change this. However you can implement your own version of records with whatever equality you want using Source Generators