Make mutable generic collection interfaces implement read-only collection interfaces

[TylerBrinkley]

Rationale

It's long been a source of confusion that the mutable generic collection interfaces don't implement their respective read-only collection interfaces. This was of course due to the read-only collection interfaces being added after the fact and thus would cause breaking changes by changing a published interface API.

With the addition of default interface implementations in C#8/.NET Core 3.0 I think the mutable generic collection interfaces, ICollection<T>, IList<T>, IDictionary<K, V>, and ISet<T> should now implicitly inherit their respective read-only collection interfaces. This can now be done without causing breaking changes.

While it would have been nice for these interfaces to share members, I think the proposed API below is the best we can possibly do with the read-only interfaces being added after the fact.

As an added bonus, this should allow some simplification of the type checking in LINQ code to check for the read-only interfaces instead of the mutable interfaces.

Proposed API

 namespace System.Collections.Generic {
-    public interface ICollection<T> : IEnumerable<T> {
+    public interface ICollection<T> : IReadOnlyCollection<T> {
-        int Count { get; }
+        new int Count { get; }
+        int IReadOnlyCollection<T>.Count => Count;
     }
-    public interface IList<T> : ICollection<T> {
+    public interface IList<T> : ICollection<T>, IReadOnlyList<T> {
-        T this[int index] { get; set; }
+        new T this[int index] { get; set; }
+        T IReadOnlyList<T>.this[int index] => this[index];
     }
-    public interface IDictionary<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>> {
+    public interface IDictionary<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>>, IReadOnlyDictionary<TKey, TValue> {
-        TValue this[TKey key] { get; set; }
+        new TValue this[TKey key] { get; set; }
-        ICollection<TKey> Keys { get; }
+        new ICollection<TKey> Keys { get; }
-        ICollection<TValue> Values { get; }
+        new ICollection<TValue> Values { get; }
-        bool ContainsKey(TKey key);
+        new bool ContainsKey(TKey key);
-        bool TryGetValue(TKey key, out TValue value);
+        new bool TryGetValue(TKey key, out TValue value);
+        TValue IReadOnlyDictionary<TKey, TValue>.this[TKey key] => this[key];
+        IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys => Keys;
+        IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values => Values;
+        bool IReadOnlyDictionary<TKey, TValue>.ContainsKey(TKey key) => ContainsKey(key);
+        bool IReadOnlyDictionary<TKey, TValue>.TryGetValue(TKey key, out TValue value) => TryGetValue(key, out value);
     }
-    public interface ISet<T> : ICollection<T> {
+    public interface ISet<T> : ICollection<T>, IReadOnlySet<T> {
-        bool IsProperSubsetOf(IEnumerable<T> other);
+        new bool IsProperSubsetOf(IEnumerable<T> other);
-        bool IsProperSupersetOf(IEnumerable<T> other);
+        new bool IsProperSupersetOf(IEnumerable<T> other);
-        bool IsSubsetOf(IEnumerable<T> other);
+        new bool IsSubsetOf(IEnumerable<T> other);
-        bool IsSupersetOf(IEnumerable<T> other);
+        new bool IsSupersetOf(IEnumerable<T> other);
-        bool Overlaps(IEnumerable<T> other);
+        new bool Overlaps(IEnumerable<T> other);
-        bool SetEquals(IEnumerable<T> other);
+        new bool SetEquals(IEnumerable<T> other);
// Adding this new member is required so that there's a most specific Contains method on ISet<T> since ICollection<T> and IReadOnlySet<T> define it too
+        new bool Contains(T value) => ((ICollection<T>)this).Contains(value); 
+        bool IReadOnlySet<T>.Contains(T value) => ((ICollection<T>)this).Contains(value);
+        bool IReadOnlySet<T>.IsProperSubsetOf(IEnumerable<T> other) => IsProperSubsetOf(other);
+        bool IReadOnlySet<T>.IsProperSupersetOf(IEnumerable<T> other) => IsProperSupersetOf(other);
+        bool IReadOnlySet<T>.IsSubsetOf(IEnumerable<T> other) => IsSubsetOf(other);
+        bool IReadOnlySet<T>.IsSupersetOf(IEnumerable<T> other) => IsSupersetOf(other);
+        bool IReadOnlySet<T>.Overlaps(IEnumerable<T> other) => Overlaps(other);
+        bool IReadOnlySet<T>.SetEquals(IEnumerable<T> other) => SetEquals(other);
+    }
 }

Binary Compatibility Test

I was able to test that this change doesn't break existing implementers with the following custom interfaces and by simply dropping the new interfaces dll to the publish folder without recompiling the consuming code, the IMyReadOnlyList<T> interface was automatically supported without breaking the code.

Original Interfaces DLL code

namespace InterfaceTest
{
    public interface IMyReadOnlyList<T>
    {
        int Count { get; }
        T this[int index] { get; }
    }

    public interface IMyList<T>
    {
        int Count { get; }
        T this[int index] { get; set; }
    }
}

New Interfaces DLL code

namespace InterfaceTest
{
    public interface IMyReadOnlyList<T>
    {
        int Count { get; }
        T this[int index] { get; }
    }

    public interface IMyList<T> : IMyReadOnlyList<T>
    {
        new int Count { get; }
        new T this[int index] { get; set; }
        int IMyReadOnlyList<T>.Count => Count;
        T IMyReadOnlyList<T>.this[int index] => this[index];
    }
}

Consuming Code

using System;
using System.Collections.Generic;

namespace InterfaceTest
{
    class Program
    {
        static void Main()
        {
            var myList = new MyList<int>();
            Console.WriteLine($"MyList<int>.Count: {myList.Count}");
            Console.WriteLine($"IMyList<int>.Count: {((IMyList<int>)myList).Count}");
            Console.WriteLine($"IMyReadOnlyList<int>.Count: {(myList as IMyReadOnlyList<int>)?.Count}");
            Console.WriteLine($"MyList<int>[1]: {myList[1]}");
            Console.WriteLine($"IMyList<int>[1]: {((IMyList<int>)myList)[1]}");
            Console.WriteLine($"IMyReadOnlyList<int>[1]: {(myList as IMyReadOnlyList<int>)?[1]}");
        }
    }

    public class MyList<T> : IMyList<T>
    {
        private readonly List<T> _list = new List<T> { default, default };

        public T this[int index] { get => _list[index]; set => _list[index] = value; }

        public int Count => _list.Count;
    }
}

Original Output

MyList<int>.Count: 2
IMyList<int>.Count: 2
IMyReadOnlyList<int>.Count:
MyList<int>[1]: 0
IMyList<int>[1]: 0
IMyReadOnlyList<int>[1]:

New Output

MyList<int>.Count: 2
IMyList<int>.Count: 2
IMyReadOnlyList<int>.Count: 2
MyList<int>[1]: 0
IMyList<int>[1]: 0
IMyReadOnlyList<int>[1]: 0

Moved from #16151

Updates

• Added ISet<T> implementing IReadOnlySet<T> since Please add interface IReadOnlySet and make HashSet, SortedSet implement it #2293 has been implemented.

[safern]

@terrajobst I would like to have your input on these w.r.t new default implementations and adding new interfaces or new members to interfaces.

[GrabYourPitchforks]

For folks confused as to why this would be a breaking change without default interface implementations, consider three separate assemblies defined as such:

namespace MyClassLib
{
    public interface IFoo
    {
        void PrintHello();
    }
}

namespace MyOtherClassLib
{
    public interface IBar
    {
        void PrintHello();
    }
}

namespace MyApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            object myFoo = MakeNewMyFoo();

            IFoo foo = myFoo as IFoo;
            if (foo is null)
            {
                Console.WriteLine("IFoo not implemented.");
            }
            foo?.PrintHello();

            IBar bar = myFoo as IBar;
            if (bar is null)
            {
                Console.WriteLine("IBar not implemented.");
            }
            bar?.PrintHello();
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        private static object MakeNewMyFoo()
        {
            return new MyFoo();
        }

        class MyFoo : IFoo
        {
            void IFoo.PrintHello()
            {
                Console.WriteLine("Hello from MyFoo.IFoo.PrintHello!");
            }
        }
    }
}

Compile and run the main application, and you'll see the following output.

Hello from MyFoo.IFoo.PrintHello!
IBar not implemented.

Now change the assembly which contains IFoo to have the following code, and recompile and redeploy that assembly while not recompiling the assembly which contains MyApplication.

namespace MyClassLib
{
    public interface IFoo : IBar
    {
    }
}

The main application will crash upon launch with the following exception.

Unhandled exception. System.MissingMethodException: Method not found: 'Void MyClassLib.IFoo.PrintHello()'.
   at MyApplication.Program.Main(String[] args)

The reason for this is that the method that would normally be at the slot IFoo.PrintHello was removed and instead there's a new method at the slot IBar.PrintHello. However, this now prevents the type loader from loading the previously-compiled MyFoo type, as it's trying to implement an interface method for which there's no longer a method entry on the original interface slot. See https://stackoverflow.com/a/35940240 for further discussion.

As OP points out, adding default interface implementations works around the issue by ensuring that an appropriate method exists in the expected slot.

[TylerBrinkley]

@terrajobst any input on this collection interface change as well?

[TylerBrinkley]

@safern @GrabYourPitchforks @terrajobst Is this something we could get triaged soon? I'd love for this to make it into .NET 5.

[safern]

@eiriktsarpalis and @layomia are the new System.Collections owners so I'll defer to them.

[TylerBrinkley]

@terrajobst

We can't make ISet<T> extend IReadOnlySet<T> (for the same reason that we couldn't do for the other mutable interfaces).

Is this still true even with default interface methods? Does that mean dotnet/corefx#41409 should be closed?

We discussed this. We used to think that that DIMs would work, but when we walked the solution we concluded that it would result commonly in a shard diamond which would result in an ambiguous match. However, this was recently challenged so I think I have to write it down and make sure it's actually working or not working.

Here's a comment @terrajobst had about this in a separate issue, #2293 (comment)

Hoping for some more insight.

[TylerBrinkley]

I updated the proposal to add a Contains DIM to ISet<T> as the current Contains method is defined on ICollection<T> and so if you tried to call Contains on an ISet<T> the call would be ambiguous with the ICollection<T> and IReadOnlySet<T> versions.

The new method would take precedence in this case and it's implementation if not overridden would delegate to ICollection<T>'s implementation as IReadOnlySet<T>'s does. It's not ideal but this is the only incidence of such a solution where this is required for the proposal.

[TylerBrinkley]

As an alternative since IReadOnlySet<T> hasn't released yet, instead of adding another Contains method to the list including ICollection<T>, IReadOnlySet<T>, and now ISet<T> we could instead add an invariant read-only collection interface as proposed in #30661 and have it implement a Contains method and then have IReadOnlySet<T> implement this new invariant interface and remove it's Contains method.

With that change then ICollection<T> could implement this new invariant read-only collection interface.

So instead of this.

namespace System.Collections.Generic {
    public interface ICollection<T> : IReadOnlyCollection<T> {
        bool Contains(T value);
        ...
    }
    public interface IReadOnlySet<T> : IReadOnlyCollection<T> {
        bool Contains(T value);
        ...
    }
    public interface ISet<T> : IReadOnlySet<T> {
        new bool Contains(T value) => ((ICollection<T>)this).Contains(value);
        bool ICollection<T>.Contains(T value);
        bool IReadOnlySet<T>.Contains(T value) => ((ICollection<T>)this).Contains(value);
        ...
    }
}

it would be this.

namespace System.Collections.Generic {
    public interface IReadOnlyCollectionInvariant<T> : IReadOnlyCollection<T> {
        bool Contains(T value);
        ...
    }
    public interface ICollection<T> : IReadOnlyCollectionInvariant<T> {
        new bool Contains(T value);
        bool IReadOnlyCollectionInvariant<T>.Contains(T value) => Contains(value);
        ...
    }
    public interface IReadOnlySet<T> : IReadOnlyCollectionInvariant<T> {
        ...
    }
}

[mikernet]

As a follow-up to this:

Perhaps LINQ methods that have optimized execution paths on interfaces like IList<T> could be updated to optimize on IReadOnlyList<T> instead since all IList<T> will now implement IReadOnlyList<T> and then new code can begin moving to a sane development model where custom read-only collections don't need to extraneously implement the writable interfaces as well. I recall the justifications for optimizing LINQ on writable interfaces instead of read-only interfaces were:

1. IReadOnlyList<T> is covariant and thus slower.
2. IReadOnlyList<T> hasn't been around as long as List<T> so some code may not implement it and thus not get the optimizations.
3. It is "standard" to implement both IList<T> and IReadOnlyList<T> on all list-like collections anyway, I believe mostly because of the perf/optimization issues above?

I could be wrong but I believe there have been runtime updates to address point 1. Point 2 would be addressed by this issue. Point 3 is something that we could move away from with these changes to make read-only collection interfaces real first-class citizens in the framework that are actually widely usable.

A remaining sore point would be the annoying lack of support for read-only interfaces in many places where they should be supported as inputs and adding overloads that accept read-only interfaces is problematic because many collections currently implement both IList<T> and IReadOnlyList<T> directly so overload resolution would fail. This could be addressed in the BCL by updating writable collections to only directly implement the writable interface but might be confusing if people's code no longer compiles after updating to a new runtime version when using third-party collections that haven't been updated as such.

The above issues combined with the inability to pass an IList<T> into a method that accepts an IReadOnlyList<T> almost aways prevents me from using read-only collection interfaces in my code. Collections are easily one of the most poorly designed areas of the BCL and so fundamental to development that cleaning this up as much as possible with a bit of help from DIMs would be really nice.

[vpenades]

I would like to propose an alternative solution:

For example, for a List we have this:

IList<T>
IReadOnlyList<T>
List<T> : IList<T> , IReadOnlyList<T>

What I propose is this:

IList<T>
IReadOnlyList<T>
IWriteableList<T> : IList<T>, IReadOnlyList<T>
List<T> : IWriteableList<T>

So, from the point of view of the runtime, it would just require introducing a new interface, so I don't think it would break any compatibility. And developers would progressively move from using IList to IWriteableList

[jhudsoncedaron]

So it turns out this is a very peanut-buttery performance optimization as well. There are a number of places in Linq that check for IEnumerable for ICollection or IList for performance improvements and the report is that these can't be changed to check both for performance reasons; yet I found place after place in my own code where only IReadOnlyCollection/List is provided and a mutable collection would be meaningless. I also found many places where ICollection/List is dynamically downcast to its ReadOnly variant with an actual synthesis if the downcast fails.

Particularly to the implemenation of .Select, I found that making this change to that all ICollection/List also provide their IReadOnly variants yields 33-50% performance improvement at only the cost of JIT time (to provide the interfaces where they are not). I also found that adding an IReadOnlyCollection.CopyTo() is a possible improvement but the gains aren't needed because implementing IListSource on the projection returned by Select() on an IReadOnlyCollection yields more gain than that ever could.

Synthetic benchmark attached showing the component changes. The first number is garbage (ensures the memory is paged in); the second and third numbers show the baseline, and the last number shows the gains. (It's approximately equal to the second number, which means I found all the performance gains). I found on my machine about every third run is garbage due to disturbance, so run it three times and keep the closest two numbers.
selectbenchmarks.zip

[jhudsoncedaron]

Update: Saying that IReadOnlyCollection.CopyTo() was not needed because of a better implementation involving IListSource() proved to be overfitting to the test.

It turns out that there is more cheap (but not free) performance improvements lying around for direct invocation of .ToList() and .ToArray() (commonly used for shallow copies of arrays), List.AddRange(), List.InsertRange(), and List's own Constructor to the point where adding IReadOnlyCollection<T>.CopyTo(T array, int offset); is worthwhile. There is no gain for the default implementation but a custom implementation providing .CopyTo() yields cheap performance gains.

The default implementation would be:

public partial interface IReadOnlyCollection<T> {
    void CopyTo(T[] target, int offset) {
        if (this is ICollection<T> coll)  { coll.CopyTo(target, offset); return ; }
        foreach (var item in this) target[offset++] = item;
        return;
    }
}

[eiriktsarpalis]

Potential alternative design: #23337.

Please also see this comment demonstrating the potential for compile-time and runtime diamond errors when adding DIMs to existing interfaces. Would need to investigate if the current proposal is susceptible to the same issue (I suspect it might not be as long as we're not adding new methods).

[jhudsoncedaron]

@eiriktsarpalis : I found that to be not an alternative design but a different design defect that could be fixed independently. ICollection<T> : IReadOnlyCollection<T> is not the heart of this one but rather IList<T> : IReadOnlyList<T>, IDictionary<T> : IReadOnlyDictionary<T>, and ISet<T> => IReadOnlySet<T>.

[jhudsoncedaron]

Not implementing this is slowly causing us more and more problems. The root is IList<T> and IReadOnlyList<T> are conflicting overloads (along with ICollection<T> and IReadOnlyCollection<T>). We have a large number of implementations of these interfaces and a decent number of extension methods on lists. The conflicting overloads are causing chronic problems.

It almost feels like a dumb compiler, but it's not. It doesn't matter which way half of the the overloads are resolved. The implementations are copy/paste of each other.

Latest trigger. One of our programmers really likes calling .Any() for readability as opposed to .Count > 0. In theory I could go and make some stupidly-fast extension methods but I actually can't because of the overload conflict, so we're stuck with Any<T>(IEnumerable<T>) and a dynamic downcast and as often as not an enumeration.

[mikernet]

@jhudsoncedaron This could potentially alleviate some of those issues:

dotnet/csharplang#4867

Would still be nice to fix collections though.

[jhudsoncedaron]

@mikernet : It won't. To work I need it to do exactly what it says it won't do: "Overload priorities should only be considered when disambiguating methods within the same assembly". I need to win (or in one case lose) against overloads shipped with .NET itself.

[bartonjs]

How often will people have signatures from members in the IReadOnlyXxx interfaces that are virtual but unrelated to the semantics of the collection type?

Presumably that's analyzable. At least in the linked case, since it's a) it has explicitly implemented ICollection.Count, and b) has a (different) public member named Count. In that case, IReadOnlyCollection.Count will be considered implicitly implemented, and not lifted from the DIM on ICollection.

[terrajobst]

@bartonjs

Presumably that's analyzable.

Maybe but I'll struggle with writing down what I would be looking for. There are many ways one could share the logic/semantics without necessarily binding to the same method across all v-table slots.

[joshudson]

Incidentally it's also fixable. Define a new attribute for default interface mehods that means "do not look for public methods to replace this with, but only methods declared to implement the interface.

I can tell that random public methods of the same name as interface methods don't necessarily impute themselves onto newly added interface methods because the opposite behavior exists in VB.NET; adding a (non-default) interface method results in a load error in VB.NET until the method is implemented in the class implementing the interface.

[MichalStrehovsky]

Maybe but I'll struggle with writing down what I would be looking for. There are many ways one could share the logic/semantics without necessarily binding to the same method across all v-table slots.

The low tech approach could be just about looking at the list of methods. This would have to be explicit interface method implementation and the C# compiler mangles them in a distinct way.

If there's a method with name System.Collections.Generic.ICollection\<.*\>.get_Count in the base hierarchy, and another method with name get_Count (without the prefix) that returns an int, the class is likely susceptible to this problem. One could restrict to just virtual method (if get_Count is not virtual, it would not be a binary breaking change, but it would still be a source breaking change because the C# compiler is going to "helpfully" mark the method virtual if it sees it could implement an interface).

Incidentally it's also fixable. Define a new attribute for default interface mehods that means "do not look for public methods to replace this with, but only methods declared to implement the interface.

If I understand it right, the fix would cause class Foo : ICollection<T> { public int Count { ... } } to not have IReadOnlyCollection.Count implemented by Foo, but by the default method on ICollection even in the future when we already shipped ICollection : IReadOnlyCollection. That sounds like a worse problem than the original problem. The default implementations are sub-optimal. They cause double interface call in spots that could just be one interface call. They also create an interface dispatch hotspot in the default implementation. Dynamic PGO is going to have a difficult time getting rid of them (because the callsite will likely be superpolymorphic). We want to run the convenience default implementations as little as possible.

[eiriktsarpalis]

If we want to run this experiment this year it would probably need to be merged before the end of January in time for Preview 1. Any volunteers willing to source an implementation?

[joshudson]

If nobody else steps up by Jan 2, I'll try it; but an earlier attempt would be better. Sorry, I cannot do it this month.

[terrajobst]

@joshudson

Sorry, I cannot do it this month.

No need to apologize for not being able to volunteer your time to an OSS project, especially over the holiday period :-)

[TylerBrinkley]

I'll try my hand at it with #95830.

[eiriktsarpalis]

Change got reverted in #101644, reopening to keep track of next steps.

[mikernet]

😭

What are the next steps?

[RenderMichael]

With respect to C++/CLI (I’ve never used it but it sounds neat), this change is not a breaking change in any meaningful way, and is only breaking on C++/CLI due to a limitation in their type system.

I’m not sure if it’s considered a bug to be fixed or a new feature that requires some cycles to design and implement, but I do hope this can be resolved on C++/CLI’s side and the change go through again. It would be a colossal disappointment if this change gets denied.

[huoyaoyuan]

Previously DIM in static interface method were blocked by C++/CLI too and temporarily reverted until RTM.
Hopefully C++/CLI can unblock on this too. I'm OK to see this change delayed to .NET 10, but unwilling to see it blocked forever.

[joshudson]

On considering the failure mode in C++/CLR; I am reasonably convinced it is not an ABI breaking change but only an API breaking change (that is, it only fails at compile time). That being said, the required source fix is ugly and something should be done.

On further analysis, this seems to be a bug in the C++/CLR compiler. The problem happened upon adding IList : IReadOnlyList and a type was found that implements IList but doesn't expose a public method called getCount itself.

If the type follows CLR rules, it doesn't have a public method called getCount; therefore the type must follow C++ rules. On synthesizing the C++ view of the combined type I got:

#include <iostream>

class IEnumerable {
};

class IReadOnlyList: public virtual IEnumerable {
public:
	int getCount() { return 3; }
};

class IList: public virtual IEnumerable {
public:
	int getCount() { return 3; }
};

class MyList: public virtual IList {};

int main()
{
	MyList l;
	std::cout << l.getCount() << "\n";
}

Which builds and runs; the C++/CLR compiler is behaving as though the change imputed the following change to the code: class MyList: public virtual IList, public virtual IReadOnlyList {}; where MyList only declares an implementation of IList

[kasperk81]

it's about a simple static cast dotnet/wpf#9055 (comment)

[TylerBrinkley]

@eiriktsarpalis Any next steps on this yet? Is the path to fix the incompatibilities in C++/CLI in a general solution or perhaps just target the API's where this change causes issues? Thanks.

[KennethHoff]

Is there intention to try to get this back in time for a .Net 9 Preview? Is it being delayed to .Net 10+, or is it dead?

The various discussions I've seen/heard seem to indicate that this is just a temporary issue when C++/CLI, but how temporary are we talking? I hope it's not as temporary as the lack of adoption for C++ modules 😅

[terrajobst]

It's not dead yet but it depends on whether or not we can control the failure cases. At this point .NET 9 is extremely unlikely.