record types with collection properties & collections with value semantics

Question

In c# 9, we now (finally) have record types:

public record SomeRecord(int SomeInt, string SomeString);

This gives us goodies like value semantics:

var r1 = new SomeRecord(0, "zero");
var r2 = new SomeRecord(0, "zero");
Console.WriteLine(r1 == r2); // true - property based equality

While experimenting with this feature, I realized that defining a property of a (non-string) reference type may lead to counter-intuitive (albeit perfectly explainable if you think it through) behaviour:

public record SomeRecord(int SomeInt, string SomeString, int[] SomeArray);

var r1 = new SomeRecord(0, "test", new[] {1,2});
var r2 = new SomeRecord(0, "test", new[] {1,2});
Console.WriteLine(r1 == r2); // false, since int[] is a non-record reference type

Are there collection types with value semantics in .Net (or 3rd party) that may be used in this scenario? I looked at ImmutableArray and the likes, but these don't provide this feature either.

Answer 1

Our team faced a similar problem and started implementing based on the idea from @jeroenh. However, we ran into the issue of records that could no longer be deserialized from json with System.Text.Json. Here's the gist (posted below as well) with everything we had to create in order to support this deep equality on records.

ImmutableArrayWithDeepEquality

using System.Collections.Generic;
using System.Linq;

namespace System.Collections.Immutable
{
    [System.Text.Json.Serialization.JsonConverter(typeof(JsonConverterForImmutableArrayWithDeepEqualityFactory))]
    public struct ImmutableArrayWithDeepEquality<T> : IEquatable<ImmutableArrayWithDeepEquality<T>>, IEnumerable, IEnumerable<T>
    {
        private readonly ImmutableArray<T> _list;

        public ImmutableArrayWithDeepEquality(ImmutableArray<T> list) => _list = list;

        #region ImmutableArray Implementation

        public T this[int index] => _list[index];

        public int Count => _list.Length;

        public ImmutableArrayWithDeepEquality<T> Add(T value) => _list.Add(value).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> AddRange(IEnumerable<T> items) => _list.AddRange(items).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> Clear() => _list.Clear().WithDeepEquality();
        public ImmutableArray<T>.Enumerator GetEnumerator() => _list.GetEnumerator();
        public int IndexOf(T item, int index, int count, IEqualityComparer<T> equalityComparer) => _list.IndexOf(item, index, count, equalityComparer);
        public ImmutableArrayWithDeepEquality<T> Insert(int index, T element) => _list.Insert(index, element).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> InsertRange(int index, IEnumerable<T> items) => _list.InsertRange(index, items).WithDeepEquality();
        public int LastIndexOf(T item, int index, int count, IEqualityComparer<T> equalityComparer) => _list.LastIndexOf(item, index, count, equalityComparer);
        public ImmutableArrayWithDeepEquality<T> Remove(T value, IEqualityComparer<T> equalityComparer) => _list.Remove(value, equalityComparer).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> RemoveAll(Predicate<T> match) => _list.RemoveAll(match).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> RemoveAt(int index) => _list.RemoveAt(index).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> RemoveRange(IEnumerable<T> items, IEqualityComparer<T> equalityComparer) => _list.RemoveRange(items, equalityComparer).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> RemoveRange(int index, int count) => _list.RemoveRange(index, count).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> Replace(T oldValue, T newValue, IEqualityComparer<T> equalityComparer) => _list.Replace(oldValue, newValue, equalityComparer).WithDeepEquality();
        public ImmutableArrayWithDeepEquality<T> SetItem(int index, T value) => _list.SetItem(index, value).WithDeepEquality();
        public bool IsDefaultOrEmpty => _list.IsDefaultOrEmpty;

        public static ImmutableArrayWithDeepEquality<T> Empty = new(ImmutableArray<T>.Empty);

        #endregion

        #region IEnumerable

        IEnumerator IEnumerable.GetEnumerator() => (_list as IEnumerable).GetEnumerator();
        IEnumerator<T> IEnumerable<T>.GetEnumerator() => (_list as IEnumerable<T>).GetEnumerator();

        #endregion

        #region IEquatable

        public bool Equals(ImmutableArrayWithDeepEquality<T> other) => _list.SequenceEqual(other);

        public override bool Equals(object obj) => obj is ImmutableArrayWithDeepEquality<T> other && Equals(other);

        public static bool operator ==(ImmutableArrayWithDeepEquality<T>? left, ImmutableArrayWithDeepEquality<T>? right) => left is null ? right is null : left.Equals(right);

        public static bool operator !=(ImmutableArrayWithDeepEquality<T>? left, ImmutableArrayWithDeepEquality<T>? right) => !(left == right);

        public override int GetHashCode()
        {
            unchecked
            {
                return _list.Aggregate(19, (h, i) => h * 19 + i!.GetHashCode());
            }
        }


        #endregion
    }

    public static class ImmutableArrayWithDeepEqualityEx
    {
        public static ImmutableArrayWithDeepEquality<T> WithDeepEquality<T>(this ImmutableArray<T> list) => new(list);

        public static ImmutableArrayWithDeepEquality<T> ToImmutableArrayWithDeepEquality<T>(this IEnumerable<T> list) => new(list.ToImmutableArray());
    }
}

ImmutableArrayWithDeepEquality JsonConverter

using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text.Json;
using System.Text.Json.Serialization;

namespace System.Collections.Immutable
{
    public class JsonConverterForImmutableArrayWithDeepEqualityFactory : JsonConverterFactory
    {
        public override bool CanConvert(Type typeToConvert)
            => typeToConvert.IsGenericType
            && typeToConvert.GetGenericTypeDefinition() == typeof(ImmutableArrayWithDeepEquality<>);

        public override JsonConverter CreateConverter(Type typeToConvert, JsonSerializerOptions options)
        {
            var elementType = typeToConvert.GetGenericArguments()[0];

            var arrayType = typeof(JsonConverterForImmutableArrayWithDeepEquality<>);

            var converter = (JsonConverter)Activator.CreateInstance(
                arrayType.MakeGenericType(elementType),
                BindingFlags.Instance | BindingFlags.Public,
                binder: null,
                args: null,
                culture: null)!;

            return converter;
        }

        private class JsonConverterForImmutableArrayWithDeepEquality<T> : JsonConverter<ImmutableArrayWithDeepEquality<T>>
        {
            public override ImmutableArrayWithDeepEquality<T> Read(ref Utf8JsonReader reader, Type typeToConvert, JsonSerializerOptions options)
            {
                if (reader.TokenType != JsonTokenType.StartArray)
                {
                    throw new JsonException();
                }

                reader.Read();

                List<T> elements = new();

                while (reader.TokenType != JsonTokenType.EndArray)
                {
                    var value = JsonSerializer.Deserialize<T>(ref reader, options);

                    if (value is not null)
                    {
                        elements.Add(value);
                    }

                    reader.Read();
                }

                return elements.ToImmutableArrayWithDeepEquality();
            }

            public override void Write(Utf8JsonWriter writer, ImmutableArrayWithDeepEquality<T> value, JsonSerializerOptions options)
            {
                JsonSerializer.Serialize(writer, value.AsEnumerable(), options);
            }
        }
    }
}

ImmutableDictionaryWithDeepEquality

using System.Collections.Generic;
using System.Linq;
using System.Text.Json.Serialization;

namespace System.Collections.Immutable
{
    [JsonConverter(typeof(JsonConverterForImmutableDictionaryWithDeepEqualityFactory))]
    public class ImmutableDictionaryWithDeepEquality<TKey, TValue> : IEquatable<ImmutableDictionaryWithDeepEquality<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable, IReadOnlyCollection<KeyValuePair<TKey, TValue>> where TKey : notnull
    {
        private readonly ImmutableDictionary<TKey, TValue> _dictionary;

        public ImmutableDictionaryWithDeepEquality(ImmutableDictionary<TKey, TValue> dictionary) => _dictionary = dictionary;

        #region ImmutableArray Implementation

        public TValue this[TKey index] => _dictionary[index];

        public int Count => _dictionary.Count;

        public ImmutableDictionaryWithDeepEquality<TKey, TValue> Add(TKey key, TValue value) => _dictionary.Add(key, value).WithDeepEquality();
        public ImmutableDictionaryWithDeepEquality<TKey, TValue> AddRange(IEnumerable<KeyValuePair<TKey, TValue>> pairs) => _dictionary.AddRange(pairs).WithDeepEquality();
        public ImmutableDictionaryWithDeepEquality<TKey, TValue> Clear() => _dictionary.Clear().WithDeepEquality();
        public ImmutableDictionary<TKey, TValue>.Enumerator GetEnumerator() => _dictionary.GetEnumerator();
        public ImmutableDictionaryWithDeepEquality<TKey, TValue> Remove(TKey key) => _dictionary.Remove(key).WithDeepEquality();
        public ImmutableDictionaryWithDeepEquality<TKey, TValue> RemoveRange(IEnumerable<TKey> keys) => _dictionary.RemoveRange(keys).WithDeepEquality();
        public ImmutableDictionaryWithDeepEquality<TKey, TValue> SetItem(TKey key, TValue value) => _dictionary.SetItem(key, value).WithDeepEquality();
        public bool IsEmpty => _dictionary.IsEmpty;

        public static ImmutableDictionaryWithDeepEquality<TKey, TValue> Empty = new(ImmutableDictionary<TKey, TValue>.Empty);

        #endregion

        #region IEnumerable

        IEnumerator IEnumerable.GetEnumerator() => (_dictionary as IEnumerable).GetEnumerator();
        IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() => (_dictionary as IEnumerable<KeyValuePair<TKey, TValue>>).GetEnumerator();

        #endregion

        #region IEquatable

        public bool Equals(ImmutableDictionaryWithDeepEquality<TKey, TValue> other) => _dictionary.SequenceEqual(other);

        public override bool Equals(object obj) => obj is ImmutableDictionaryWithDeepEquality<TKey, TValue> other && Equals(other);

        public static bool operator ==(ImmutableDictionaryWithDeepEquality<TKey, TValue>? left, ImmutableDictionaryWithDeepEquality<TKey, TValue>? right) => left is null ? right is null : right is not null && left.Equals(right);

        public static bool operator !=(ImmutableDictionaryWithDeepEquality<TKey, TValue>? left, ImmutableDictionaryWithDeepEquality<TKey, TValue>? right) => !(left == right);

        public override int GetHashCode()
        {
            unchecked
            {
                return _dictionary.Aggregate(19, (h, i) => h * 19 + i.Key.GetHashCode() + (i.Value?.GetHashCode() ?? 0));
            }
        }

        #endregion
    }

    public static class ImmutableDictionaryWithDeepEqualityEx
    {
        public static ImmutableDictionaryWithDeepEquality<TKey, TValue> WithDeepEquality<TKey, TValue>(this ImmutableDictionary<TKey, TValue> dictionary) where TKey : notnull => new(dictionary);

        public static ImmutableDictionaryWithDeepEquality<TKey, TValue> ToImmutableDictionaryWithDeepEquality<TKey, TValue>(this IEnumerable<KeyValuePair<TKey, TValue>> list) where TKey : notnull => new(list.ToImmutableDictionary());
    }
}

ImmutableDictionaryWithDeepEquality JsonConverter

using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text.Json;
using System.Text.Json.Serialization;

namespace System.Collections.Immutable
{
    public class JsonConverterForImmutableDictionaryWithDeepEqualityFactory : JsonConverterFactory
    {
        public override bool CanConvert(Type typeToConvert) =>
            typeToConvert.IsGenericType
            && typeToConvert.GetGenericTypeDefinition() == typeof(ImmutableDictionaryWithDeepEquality<,>);

        public override JsonConverter CreateConverter(Type typeToConvert, JsonSerializerOptions options)
        {
            var keyType = typeToConvert.GetGenericArguments()[0];
            var valueType = typeToConvert.GetGenericArguments()[1];

            var dictionaryType = typeof(JsonConverterForImmutableDictionaryWithDeepEquality<,>);

            var converter = (JsonConverter)Activator.CreateInstance(
                dictionaryType.MakeGenericType(keyType, valueType),
                BindingFlags.Instance | BindingFlags.Public,
                binder: null,
                args: null,
                culture: null)!;

            return converter;
        }

        private class JsonConverterForImmutableDictionaryWithDeepEquality<TKey, TValue> : JsonConverter<ImmutableDictionaryWithDeepEquality<TKey, TValue>> where TKey : notnull
        {
            public override ImmutableDictionaryWithDeepEquality<TKey, TValue> Read(ref Utf8JsonReader reader, Type typeToConvert, JsonSerializerOptions options)
            {
                if (reader.TokenType != JsonTokenType.StartArray)
                {
                    throw new JsonException();
                }

                reader.Read();

                Dictionary<TKey, TValue> elements = new();

                while (reader.TokenType != JsonTokenType.EndArray)
                {
                    var value = JsonSerializer.Deserialize<KeyValuePair<TKey, TValue>>(ref reader, options);

                    elements.Add(value.Key, value.Value);

                    reader.Read();
                }

                return elements.ToImmutableDictionaryWithDeepEquality();
            }

            public override void Write(Utf8JsonWriter writer, ImmutableDictionaryWithDeepEquality<TKey, TValue> value, JsonSerializerOptions options)
            {
                JsonSerializer.Serialize(writer, value.AsEnumerable(), options);
            }
        }
    }
}

ImmutableDeepEqualityTests

using System.Collections.Generic;
using Xunit;

namespace System.Collections.Immutable.Tests
{
    public class ImmutableDeepEqualityTests
    {
        [Fact]
        public void ArraysWithSameValues_AreConsideredEqual()
        {
            var array1 = new int[] { 1, 2, 3 }.ToImmutableArrayWithDeepEquality();
            var array1Copy = new int[] { 1, 2, 3 }.ToImmutableArrayWithDeepEquality();

            Assert.Equal(array1, array1Copy);
            Assert.True(array1 == array1Copy);
            Assert.False(array1 != array1Copy);
            Assert.True(array1.Equals(array1Copy));
        }

        [Fact]
        public void ArraysWithDifferentValues_AreConsideredNotEqual()
        {
            var array1 = new int[] { 1, 2, 3 }.ToImmutableArrayWithDeepEquality();
            var array2 = new int[] { 4, 5, 6 }.ToImmutableArrayWithDeepEquality();

            Assert.NotEqual(array1, array2);
            Assert.False(array1 == array2);
            Assert.True(array1 != array2);
            Assert.False(array1.Equals(array2));
        }

        [Fact]
        public void DictionariesWithSameValues_AreConsideredEqual()
        {
            var dict1 = new Dictionary<string, string> { { "Key1", "1" }, { "Key2", "2" } }.ToImmutableDictionaryWithDeepEquality();
            var dict1Copy = new Dictionary<string, string> { { "Key1", "1" }, { "Key2", "2" } }.ToImmutableDictionaryWithDeepEquality();

            Assert.Equal(dict1, dict1Copy);
            Assert.True(dict1 == dict1Copy);
            Assert.False(dict1 != dict1Copy);
            Assert.True(dict1.Equals(dict1Copy));
        }

        [Fact]
        public void DictionariesWithDifferentKeys_AreConsideredNotEqual()
        {
            var dict1 = new Dictionary<string, string> { { "Key1", "1" }, { "Key2", "2" } }.ToImmutableDictionaryWithDeepEquality();
            var dict2 = new Dictionary<string, string> { { "KeyA", "1" }, { "KeyB", "2" } }.ToImmutableDictionaryWithDeepEquality();

            Assert.NotEqual(dict1, dict2);
            Assert.False(dict1 == dict2);
            Assert.True(dict1 != dict2);
            Assert.False(dict1.Equals(dict2));
        }

        [Fact]
        public void DictionariesWithDifferentValues_AreConsideredNotEqual()
        {
            var dict1 = new Dictionary<string, string> { { "Key1", "1" }, { "Key2", "2" } }.ToImmutableDictionaryWithDeepEquality();
            var dict2 = new Dictionary<string, string> { { "Key1", "A" }, { "Key2", "B" } }.ToImmutableDictionaryWithDeepEquality();

            Assert.NotEqual(dict1, dict2);
            Assert.False(dict1 == dict2);
            Assert.True(dict1 != dict2);
            Assert.False(dict1.Equals(dict2));
        }

        [Fact]
        public void RecordsUseDeepEquality()
        {
            var array1 = new int[] { 1, 2, 3 }.ToImmutableArrayWithDeepEquality();
            var array1Copy = new int[] { 1, 2, 3 }.ToImmutableArrayWithDeepEquality();

            var dict1 = new Dictionary<string, string> { { "Key1", "1" }, { "Key2", "2" } }.ToImmutableDictionaryWithDeepEquality();
            var dict1Copy = new Dictionary<string, string> { { "Key1", "1" }, { "Key2", "2" } }.ToImmutableDictionaryWithDeepEquality();

            var model1 = new TestModel(array1, dict1);
            var model1Copy = new TestModel(array1Copy, dict1Copy);

            Assert.Equal(model1, model1Copy);
            Assert.True(model1 == model1Copy);
            Assert.False(model1 != model1Copy);
            Assert.True(model1.Equals(model1Copy));
        }

        [Fact]
        public void Records_ThatUseDeepEquality_CanSerialize()
        {
            var array1 = new int[] { 1, 2, 3 }.ToImmutableArrayWithDeepEquality();

            var dict1 = new Dictionary<string, string> { { "Key1", "1" } }.ToImmutableDictionaryWithDeepEquality();

            var model1 = new TestModel(array1, dict1);

            var json = System.Text.Json.JsonSerializer.Serialize(model1);

            Assert.Equal("{\"Ints\":[1,2,3],\"Dictionary\":[{\"Key\":\"Key1\",\"Value\":\"1\"}]}", json);
        }

        [Fact]
        public void Records_ThatUseDeepEquality_CanDeserialize()
        {
            var json = "{\"Ints\":[1,2,3],\"Dictionary\":[{\"Key\":\"Key1\",\"Value\":\"1\"}]}";

            var modelFromJson = System.Text.Json.JsonSerializer.Deserialize<TestModel>(json);

            var array1 = new int[] { 1, 2, 3 }.ToImmutableArrayWithDeepEquality();

            var dict1 = new Dictionary<string, string> { { "Key1", "1" } }.ToImmutableDictionaryWithDeepEquality();

            var model1 = new TestModel(array1, dict1);

            Assert.Equal(model1, modelFromJson);
        }

        private sealed record TestModel(
            ImmutableArrayWithDeepEquality<int> Ints,
            ImmutableDictionaryWithDeepEquality<string, string> Dictionary);
    }
}

Conclusion

As you can see it's no small task to implement, support, and maintain. After looking at are own needs we found deep equality was only needed to mask upstream issues that produced duplicate values when duplicate values never needed to be created in the first place.

Answer 2

There is no out-of-the-box solution. You could try however derive out of Collection. Microsoft made it specifically for such cases where you do not want to create whole boilerplate (adding, removing etc.). You could use our approach to the same concept: ValueCollection.cs

Now it's also available via convenient package