Please add interface IReadOnlySet and make HashSet, SortedSet implement it

[dsaf]

Original

Since IReadOnlyList was added the parity between sets and lists has declined. It would be great to re-establish it.

Using it would be an implementation-agnostic way of saying: "here is this read-only collection where items are unique".

Clearly it's needed by many people:

SQL Server: https://msdn.microsoft.com/en-us/library/gg503096.aspx
Roslyn: https://github.com/dotnet/roslyn/blob/master/src/Compilers/Core/Portable/InternalUtilities/IReadOnlySet.cs
Some Guy In Comments: http://blogs.msdn.com/b/bclteam/archive/2013/03/06/update-to-immutable-collections.aspx

I found this discussion when working on a real world problem where I wanted to use the key collection of a dictionary for read only set operations. In order to support that case here's the API I propose.

Edit

Rationale

Proposed API

 namespace System.Collections.Generic {
+    public interface IReadOnlySet<out T> : IReadOnlyCollection<T>, IEnumerable, IEnumerable<T> {
+        bool Contains(T value);
+        bool IsProperSubsetOf(IEnumerable<T> other);
+        bool IsProperSupersetOf(IEnumerable<T> other);
+        bool IsSubsetOf(IEnumerable<T> other);
+        bool IsSupersetOf(IEnumerable<T> other);
+        bool Overlaps(IEnumerable<T> other);
+        bool SetEquals(IEnumerable<T> other);
+    }
-    public class HashSet<T> : ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T> {
+    public class HashSet<T> : ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T>, IReadOnlySet<T> {
     }
-    public class SortedSet<T> : ICollection, ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T> {
+    public class SortedSet<T> : ICollection, ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T>, IReadOnlySet<T> {
     }
+    public class ReadOnlySet<T> : ICollection<T>, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, IReadOnlySet<T>, ISet<T> {
+        public int Count { get; }
+        public ReadOnlySet(ISet<T> set);
+        public bool Contains(T value);
+        public bool IsProperSubsetOf(IEnumerable<T> other);
+        public bool IsProperSupersetOf(IEnumerable<T> other);
+        public bool IsSubsetOf(IEnumerable<T> other);
+        public bool IsSupersetOf(IEnumerable<T> other);
+        public bool Overlaps(IEnumerable<T> other);
+        public bool SetEquals(IEnumerable<T> other);
+    }
     public class Dictionary<TKey, TValue> {
-        public sealed class KeyCollection : ICollection, ICollection<TKey>, IEnumerable, IEnumerable<TKey>, IReadOnlyCollection<TKey> {
+        public sealed class KeyCollection : ICollection, ICollection<TKey>, IEnumerable, IEnumerable<TKey>, IReadOnlyCollection<TKey>, IReadOnlySet<TKey> {
+            public bool IsProperSubsetOf(IEnumerable<TKey> other);
+            public bool IsProperSupersetOf(IEnumerable<TKey> other);
+            public bool IsSubsetOf(IEnumerable<TKey> other);
+            public bool IsSupersetOf(IEnumerable<TKey> other);
+            public bool Overlaps(IEnumerable<TKey> other);
+            public bool SetEquals(IEnumerable<TKey> other);
         }
     }
 }

Open Questions

• Is adding these methods to Dictionary<TKey, TValue>.KeyCollection acceptable given the code size cost for a commonly instantiated generic type? See here.
• Should IReadOnlySet<T> be implemented in other Dictionary KeyCollections such as SortedDictionary or ImmutableDictionary?

Updates

• Removed TryGetValue as it's not in ISet<T> and as such would prevent potentially ever rebasing ISet<T> to implement IReadOnlySet<T>.
• Added ReadOnlySet<T> class which is similar to ReadOnlyCollection<T>.

[whoisj]

Wouldn't be nice if we just had some language construct to make things immutable? Then we would not have to have these magic interfaces.

[HaloFour]

@whoisj Which language? The CLR has dozens of them.

Even as a potential language feature it would require a metadata representation. For this case a marker interface (or behavioral interface) is as good as any. Trying to convey the immutability of a collection type through a new metadata entry doesn't seem appropriate since the CLR shouldn't be making assumptions as to how an arbitrary class functions internally (and the CLR has no concept of collection classes at all aside for arrays).

[dsaf]

@whoisj I think this is at least considered for one of the future C# versions. But that decision doesn't affect the need for symmetrical interfaces across all collections. Furthermore I can imagine scenarios where a readonly list of mutable items could be useful, e.g. in games that care about both code quality and performance.

Also immutable collections are already available:

https://msdn.microsoft.com/en-us/library/system.collections.immutable(v=vs.111).aspx

To achieve a fully immutable collection we just need a way of defining an immutable T and then use it to declare an Immutable...<T> collection.

[whoisj]

@HaloFour we've been down this road before 😏 but I still believe the CLR needs a way to say "here's a handle, read from it but all actions that cause any kind of write through it will fail; oh and this immutability is contagious so any handle reached from the immutable handle is also immutable (including this)".

@dsaf absolutely! In another issue I proposed that we have a writable anti-term for readdonly to enable the use of readonly collection of writeble elements. Something along the lines of readonly Bag<writable Element>.

I suggested that any reference marked with a & be treated as immutable by the compiler. I still feel it only need be a compile time check, and necessarily enforced by the CLR itself as I'm mostly seeking compile time verification of logic and not run-time guarantees. This would cover any reference which developers wanted to be immutable, but on a per call basis.

[HaloFour]

@whoisj Perhaps, but that's pretty tangential and it turns this request from something dsaf could branch/PR this afternoon into something that involves effort across three different teams.

You're also treating this as a compiler concern. At this point there isn't a compiler involved (beyond the JIT compiler) and only the verifier can attempt to prevent "improper" code from executing. Even the existing runtime mechanisms of immutability, initonly fields, can be easily defeated if verification is skipped (or via reflection).

I do agree that it would be nice if the C# language and compiler can have better support for "pure" methods. The attribute PureAttribute already exists but it's used sporadically and there really isn't any language support for it. And even if C# did support it through compiler errors (pure can only call pure, etc.), it's very easily defeated by using a different language. But these methods have to announce themselves and enforce themselves as once compiled to IL all bets are basically off and none of the compilers can bend how an existing assembly executes.

[whoisj]

@HaloFour fair.

Assuming we don't have a general way to support "pure" or "const" references, then I suppose the proposed is the best alternative.

[yanggujun]

If you need it now, my Commons library (Commons.Collections https://github.com/yanggujun/commonsfornet/tree/master/src/Commons.Collections/Set ) has the readonly set support. Admin please delete this post if this is thought as an advert... My suggestion is to look around for some open source implementation.

[dsaf]

@yanggujun Thank you for suggestion, that seems like a nice library, but I will roll my own to avoid extra dependencies.

My suggestion is to look around for some open source implementation.

This is a work-around, fundamental interfaces like IReadOnlySet should really be a part of .NET Framework itself.

[ashmind]

Does this need a speclet to become "ready for api review"?

[GiottoVerducci]

And while we're at it, consider naming it something different than "ReadOnly" (see interesting post: http://stackoverflow.com/questions/15262981/why-does-listt-implement-ireadonlylistt-in-net-4-5)
"Readable" seems fine.

[dsaf]

@GiottoVerducci No. I would prefer to keep a consistent naming pattern even if it is imperfect. You are free to raise a separate issue to rename existing interfaces though.

[ashmind]

Proposed API design:

public interface IReadOnlySet<T> : IReadOnlyCollection<T> {    
    bool Contains(T item);
    bool IsSubsetOf(IEnumerable<T> other);
    bool IsSupersetOf(IEnumerable<T> other);
    bool IsProperSupersetOf(IEnumerable<T> other);
    bool IsProperSubsetOf(IEnumerable<T> other);
    bool Overlaps(IEnumerable<T> other);
    bool SetEquals(IEnumerable<T> other);
}

This is based on ISet<> API (except mutation methods obviously).

It's a pity Comparer does not fit in this, but then neither ISet<> nor IReadOnlyDictionary<> expose comparers, so it's too late to fix now.

[binki]

    bool Contains(T item);

Shouldn’t this be in IReadOnlyCollection<T> instead since ICollection<T> has Contains(T item)?

[adamt06]

The immutable collections package has been unlisted from nuget while still beta.
I think this is a pretty common use case and should be handled in standard libs.

[drewnoakes]

Is there more work to do on the API here, as the tag suggests? I'm happy to spend some time on this if it'd be helpful and someone can point out what's needed.

The API @ashmind proposed looks great.

Can ISet<T> be made to extend IReadOnlySet<T>? This didn't happen IList<T>/IReadOnlyList<T>?

If not, then I suppose the other changes to consider are adding IReadOnlySet<T> to the interface list for all ISet<T> implementations in corefx including HashSet<T>, SortedSet<T> and their immutable counterparts in System.Collections.Immutable.

[HaloFour]

I have to agree with @GiottoVerducci . Using a name like IReadOnlySet<T> doesn't declare the contracts capabilities, it declares the contracts limitations. To then use that same contract combined with another that contradicts those limitations is confusing. I believe that the contract name should describe a positive assertion pertaining to what the implementer supports. A name like IReadableSet<T> isn't great, admittedly, but it at least better describes what the implementer does.

[drewnoakes]

@HaloFour I agree in principle, but we have the same situation now with IReadOnlyList<T>. Maintaining consistency trumps the increase in precision here, IMHO.

[HaloFour]

@drewnoakes

I understand, and consistency is important. I think that also answers why ISet<T> shouldn't extend IReadOnlySet<T>, though.

[binki]

Maintaining consistency trumps the increase in precision here, IMHO.

I think that also answers why ISet<T> shouldn't extend IReadOnlySet<T>, though.

I think you’re missing the point. That’s the reason that IList<T>, ICollection<T>, IDictionary<TKey, TValue> should, in addition to ISet<T>, also be fixed to implement read-only view interfaces. Otherwise everyone has to continue to be confused when working around the unintuitive design of the BCL.

[HaloFour]

@binki

I don't disagree. What I don't like about that is having a contract that stipulates read-only behavior being extended by a contract that stipulates read-write behavior. The naming is wrong and the composition is wrong. But here we are. I'd love to vote to change both, but I doubt such is on the table.

[binki]

@HaloFour

When you get an interface into something, it’s a view into something. The view itself is read-only. Assuming you wrote type-safe code and won’t go around upcasting, if you receive something that is read-only, it is, for all intents and purposes, read-only. That’s no guarantee that the data won’t change. It’s just like opening a file read-only. A file opened read-only can be mutated by another process. Or like read-only access to pages on a website where an administrator would have a read-write view into the data and can change it out from under you.

I’m not sure why read-only is considered the wrong term here. Read-only does not imply immutable. There’s a whole nuget package/different API (where adding/removing generates a new object and the current instance is guaranteed to never mutate—thus being immutable) for that if that’s what you require.

[drewnoakes]

I was thinking something similar. "Read only" in .NET is a pretty weak guarantee for fields too. Given a do-over, I'm sure all this would make more sense. For now it's worth being pragmatic.

So in general, if a method accepts an IReadOnlySomething<T> you can, in general, assume that it won't modify it. There's no guarantee the receiving method won't upcast the reference, and there's no guarantee that the interface's implementation won't internally modify itself when accessed either.

In C++, const_cast weakens the guarantees of const too, which is a shame (esp nowadays with the mutable modifier) but in practice it doesn't take away from how useful const is as an feature. You just have to know what you're dealing with.

@binki makes a good distinction. Immutable in the name implies a hard guarantee of stability over time for all involved.

Does anyone have an authoritative source as to why IList<T> doesn't extend IReadOnlyList<T>?

[HaloFour]

@binki

An interface isn't a view, it's a contract. That contract declares the capabilities of the implementer. If the implementer doesn't actually implement those capabilities I would consider that a contract violation. That List<T> class claims that it "is-a" IReadOnlyList<T>, but it's not. It lacks that capability.

There are multiple schools of thought on this subject. I clearly belong to the school where interface inheritance more strictly follows "is-a" relationships between types. I certainly support a more granular approach to composition with interfaces and think that List<T> and its kin could probably benefit from implementing some 3-4 additional interfaces (read, write, append, etc.) But I certainly think that the name of an interface should describe what a type can do, not what it can't do. Negative capability assertions don't make much sense for contracts.

@drewnoakes

For now it's worth being pragmatic.

I agree. We are where we are. If IList<T> were to be changed to extend IReadOnlyList<T> then it makes sense for ISet<T> to be changed to extend IReadOnlySet<T>, etc.

Is it being too redundant to also push for IReadableX<T>, IWritableX<T>, etc. interfaces to live alongside IReadOnlyX<T>?

[binki]

Does anyone have an authoritative source as to why IList<T> doesn't extend IReadOnlyList<T>?

Apparently it would be an ABI-breaking change when loading assemblies that were compiled against older .net frameworks. Because when implementing an interface, most compilers will automatically generate explicit interface implementations when the source code relies on implicit interface implementation, if you compiled your class implementing IList<T> against a BCL that doesn’t have IList<T> implementing IReadOnlyList<T>, the compiler won’t automatically create the explicit IReadOnlyList<T> implementations. If I’m reading this right: http://stackoverflow.com/a/35940240/429091

[jnm2]

@HaloFour Since List<> and HashSet<> implement ICollection<> and IReadOnlyCollection<>, we've already embraced a path where IReadOnly refers to access and not capability. Based on that, having IAnything extend IReadOnlyAnything makes perfect sense. I agree that IReadable is better than IReadOnly but at this point everyone understands IReadOnly to mean IReadable and uses it as such. In fact, I'm perpetuating that intentionally in my own codebase because having two ways of thinking about things is more cognitive load than anything in my opinion.

We're stuck with the name, but the concept behind it is powerful enough that I truly wish it was possible for all interfaces to extend IReadOnly going forward, just like we do with concrete classes.

[jnm2]

@ashmind I think it's perfect that none of the methods take comparers. In sets and dictionaries, comparers aren't something you can easy swap out because they determine the structure of the entire object. Also, it wouldn't make sense to pass a comparer to a CaseInsensitiveStringCollection or any collection that implies a certain comparison.

(In the case of a weird collection that does implement Contains(T, IEqualityComparer<T>) more efficiently than the extension method that's already available, it would probably be a one-off class method. It's hard to imagine Contains(T, IEqualityComparer<T>) being common enough to end up in a specialized interface, but there's nothing stopping even that from happening.)

[ashmind]

@jnm2

I think it's perfect that none of the methods take comparers.

Just to clarify, I wanted to say that it should expose comparer, not take one. Since every Set or Dictionary must have some equality algorithm, this could have been exposed on the interface. But I don't remember my use case for that now -- something like creating a set using the same comparer as in an externally provided one.

[aaron-meyers]

While this discussion brings up lots of interesting points, it seems to be straying far from the simple and obvious suggestion that started this thread. And that is discouraging because I would really like to see this issue addressed.

As the OP said, the failure to maintain parity among collection types when IReadOnlyList was added without IReadOnlySet is unfortunate and many people have implemented their own versions of IReadOnlySet interface as workarounds (my own team has a similar workaround). Those workaround interfaces are not ideal because the corefx classes can't implement them. This is the key reason for providing this in the framework: if I have a HashSet I would like to be able to use it as an IReadOnlySet without copying or wrapping the object I already have. For performance at least this is often desirable.

The name of the interface should clearly be IReadOnlySet. Consistency trumps any concerns with the IReadOnlyXXX names. That ship has sailed.

None of the existing interfaces (IReadOnlyCollection) can be changed. The back-compat requirements for .NET don't allow changes like that. It is unfortunate that Comparers aren't exposed in the existing IReadOnlyXXX interfaces (I've run into this as well) but again the ship has sailed.

The only question that seems to remain from a practical standpoint is between these two potential definitions of the interface.

Previously proposed by @ashmind :

public interface IReadOnlySet<T> : IReadOnlyCollection<T> {    
    bool Contains(T item);
    bool IsSubsetOf(IEnumerable<T> other);
    bool IsSupersetOf(IEnumerable<T> other);
    bool IsProperSupersetOf(IEnumerable<T> other);
    bool IsProperSubsetOf(IEnumerable<T> other);
    bool Overlaps(IEnumerable<T> other);
    bool SetEquals(IEnumerable<T> other);
}

Minimal proposal:

public interface IReadOnlySet<T> : IReadOnlyCollection<T> {    
    bool Contains(T item);
}

Personally I prefer this minimal proposal since the other methods can be derived; ideally there would be a standard implementation of those as extension methods over the IReadOnlySet interface so the implementors of IReadOnlySet don't need to provide them. I also feel this minimal proposal is more in line with the other minimal IReadOnlyXXX interfaces.

[NickRedwood]

It seems like our best bet may be to wait a while longer for the Shapes proposal to be (hopefully) implemented. Then you'd be able to build whatever group of shapes to represent Set types that you wanted, and provide implementations so that existing sets like HashSet<T> conform to them.

A community library to do exactly this could then emerge, covering all the various types of sets (intensional (predicates) and extensional (listed), ordered, partially ordered, unordered, countable, countably infinite, uncountable infinite, possibly mathematic domains too like Rational, Natural numbers etc) as different shapes, with all the union, intersection, cardinality methods defined for and between these sets.

[oliverjanik]

That's sounds to me like 5 years down the road. Why should a simple change that can be implemented in a day wait for some 1000x larger not-yet-specified feature that might not even happen?

[NickRedwood]

That's sounds to me like 5 years down the road. Why should a simple change that can be implemented in a day wait for some 1000x larger not-yet-specified feature that might not even happen?

I'm just responding to the lack of progress on IReadOnlySet<T> - this issue has already been open 4 years after all.

[CodeAngry]

The Microsoft way: The most simple and useful things take decades. It's mind blowing. 5 years and counting.

What's even more funny is that they have it in here
https://docs.microsoft.com/en-us/dotnet/api/microsoft.sqlserver.management.sdk.sfc.ireadonlyset-1

[danmoseley]

@terrajobst thoughts?

[terrajobst]

• We generally believe that this indeed a hole in our interface hierarchy. We suggest to focus on just adding the interface and implementing it on the existing set implementations. We can't make ISet<T> extend IReadOnlySet<T> (for the same reason that we couldn't do for the other mutable interfaces). We can add an ReadOnlySet<T> at a later stage. We should double check that IReadOnlySet<T> is just ISet<T> minus the mutable APIs.
• We should also implement IReadOnlySet<T> on ImmutableSortedSet<T> and ImmutableHashSet<T> (and their builders)
• We should scan for other implementations of ISet<T>.

 namespace System.Collections.Generic {
+    public interface IReadOnlySet<out T> : IReadOnlyCollection<T>, IEnumerable, IEnumerable<T> {
+        bool Contains(T value);
+        bool IsProperSubsetOf(IEnumerable<T> other);
+        bool IsProperSupersetOf(IEnumerable<T> other);
+        bool IsSubsetOf(IEnumerable<T> other);
+        bool IsSupersetOf(IEnumerable<T> other);
+        bool Overlaps(IEnumerable<T> other);
+        bool SetEquals(IEnumerable<T> other);
+    }
-    public class HashSet<T> : ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T> {
+    public class HashSet<T> : ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T>, IReadOnlySet<T> {
     }
-    public class SortedSet<T> : ICollection, ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T> {
+    public class SortedSet<T> : ICollection, ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T>, IReadOnlySet<T> {
     }
 }

[MatthewLymer]

Do it, I dare you!

[svick]

@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 https://github.com/dotnet/corefx/issues/41409 should be closed?

[terrajobst]

@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.

[Jlalond]

@terrajobst / @danmosemsft Has Anyone been assigned to this?

And, @terrajobst to clarify the work we want to achieve is:

We should also implement IReadOnlySet<T> on ImmutableSortedSet<T> and ImmutableHashSet<T> (and their builders)
We should scan for other implementations of ISet<T>.

As well as implementing the above interfaces on HashSet, SortedSet.

The scanning being just look for anything and bring it up if it looks questionable.

If this is still up for grabs I'd be interested

[danmoseley]

@Jlalond nope, assigned to you. Thanks for the offer.

[Jlalond]

@danmosemsft @terrajobst
Just an update. I'm working on this, added the interface to private core Lib, just stumbling my way through having collections.generic and immutable pick up on this.

Last question if you know off your head Dan, do I need to make any changes to Mono for this? I'm not insightful on where corefx ends and mono starts. So if you know it could save me from some independent research

[danmoseley]

@Jlalond you should not need to make changes to Mono. Part of the reason for moving the Mono runtime into this repo is to make it seamless to use the same exact libraries with either CoreCLR or the Mono runtime. There is only a small part of the core library that diverges:
coreclr\src\System.Private.CoreLib vs mono\netcore\System.Private.CoreLib. (Most of the core library is shared out of libraries\System.Private.CoreLib). So unless you touch that - you are not affected.

[Jlalond]

@danmosemsft Thanks for the clarification, I hope to have this done shortly.

[Jlalond]

Hey @danmosemsft just follow up on this. CoreLib is building in the src assemblies I can see the referenced changes. However the ref assemblies seem to not be detecting any changes. This is all that's holding me up, but I can't find any info in the docs. Any people or pointers you can give me so I can get this done (I mean, 5 years later)

[eiriktsarpalis]

Addressed by #32488