Proposal: Add full family of Immutable collection contracts.

[dmitriyse]

public interface IImmutableEnumerable<T>: IEnumerable<T> {}

public interface IImmutableCollection<T>: IReadOnlyCollection<T>, IImmutableEnumerable<T>()

public interface IImmutableListSlim<T>: IReadOnlyList<T>, IImmutableCollection<T>{}

public interface IImmutableSetSlim<T>: IReadOnlySet<T>, IImmutableCollection<T>()

public interface IImmutableDictionarySlim<TKey, TValue>: IReadOnlyDictionary<TKey, TValue>, 
IImmutableCollection<KeyValuePair<TKey,TValue>>{}

// also improve

public interface IImmutableList<T>: IImmutableListSlim<T>{}
public interface IImmutableArray<T>: IImmutableListSlim<T>{}
public interface IImmutableSet<T>: IImmutableSetSlim<T>{}
public interface IImmutableDictionary<TKey, TValue>: IImmutableDictionarySlim<TKey, TValue>{}

Motivation:

public class MyClass
{
    public MyClass(IReadOnlyList<string> someIds)
    {
        // Currently I cannot rely that someIds will never change.
        // I every time think: should I copy this collection or I can use it as-is.
        // Ok, it's not a trouble I can copy, but stop, what if this place will be performance critical ???
        // no I don't want to copy. 
        // Let assume nobody will never change this collection. <== TOTALLY WRONG!
        SomIds = someIds;
        // also I performed some loading based on this ids.
        // and store result in the instance.
        // ids list will be hardly used by this component and consumers of this components.
    }
  
    public IReadOnlyList<string> SomeIds {get;}
}

// Some other place, some newbie developer... 
public void SomeCreationPlace()
{ 
       // ...

       // Some algorithm with bugs.
       var ids = new List<string>();
       while (someCondition)
       {    
            for(int i = 0; i++; i <myVar)
            {
                ids.Add("test"+i);
            }
            // ids always changes but MyClass think that IReadOnlyList will never be changed.
            var myComp = new MyClass(ids);
            myComponents.Add(myCom);
            // Some other actions
            // Ids should be cleared here, but WE PUT SOME STUPID BUG HERE
       }
}

Final bug can be found in totally different place where consumers of consumer of consumer of MyComponent received KeyNotFound exception (for example).

According to this logic we can say, no no no, better I will make the copies.

Imagine we have deep call chain. Every time we cannot rely on IReadOnly** and make copies.
Again it's no so C# way to write stupid boilerplate.

What about IImmutableList ??? - it exactly gives guaranty of immutability.
Ok. but now try to implement custom component that implement it:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace ClrCoder.Collections.Immutable.Polyfill
{
    using System.Collections.Immutable;

    public class test: IImmutableList<int>
    {
        public IEnumerator GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public int Count
        {
            get
            {
                throw new NotImplementedException();
            }
        }

        public int this[int index]
        {
            get
            {
                throw new NotImplementedException();
            }
        }

        public IImmutableList<int> Clear()
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> Add(int value)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> Replace(int oldValue, int newValue, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> SetItem(int index, int value)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> RemoveAt(int index)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> RemoveRange(int index, int count)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> RemoveRange(IEnumerable items, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> RemoveAll(Predicate match)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> Remove(int value, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> InsertRange(int index, IEnumerable items)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> Insert(int index, int element)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> AddRange(IEnumerable items)
        {
            throw new NotImplementedException();
        }

        public int LastIndexOf(int item, int index, int count, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }

        public int IndexOf(int item, int index, int count, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }
    }
}

Really too heavy. I do not want Add(), Remove(). I just what IReadOnlyList + Immutability guaranty.

CURRENTLY WE HAVE NOTHING.

We can introduce slim immutable contracts (with usual hierarchy):

public class MyClass
{
    // No comments all clear.
    public MyClass(IImmutableListSlim<string> someIds)
    {
        SomIds = someIds;
    }
   
    // This collection instance can travel across components, threads, call chains safely. 
    public IImmutableListSlim<string> SomeIds {get;}
}

[dmitriyse]

I know that IReadOnlySet currently not exists but I home sometime this proposal will be implemented https://github.com/dotnet/corefx/issues/1973

[svick]

1. I don't understand, what is the difference between IImmutableList<T> and IFrozenList<T>?
2. IImmutableCollection does not actually exist.
3. Implicit operators should never throw. And you can't have conversion operators to interfaces.

[dmitriyse]

1. IImmutableList have too many method for immutable modifications (for example Add()) that is not required in most cases where IFrozenList will be used. Thread IFrozenList just like IReadOnlyList but with guaranty of immutability.

2. IImmutableCollection/IFrozenCollection is required! This is exactly reason to have full inheritance chain of IFrozen*** that corresponds to IReadOnly***

3. This is proposal and if operator is not supported, we will create method.

[karelz]

Why do I need to distinguish between ReadOnly vs. Frozen?
What are real-world scenarios?
How common is it?
Can IReadOnly or IImmutable be used as a workaround?

[dmitriyse]

One improvement:
I found more suitable naming scheme:
IEnumerable< | IImmutableEnumerable<
ICollection<T> | IReadOnlyCollection<T> | IImmutableCollection<T>
IList<T> | IReadOnlyList<T> | IImmutableListSlim<T> | IImmutableList<T>
ISet<T> | IReadOnlySet<T> | IImmutableSetSlim<T> | IImmutableSet<T>

I am writing polyfill library that implements this proposal.
Probably I will publish it tomorrow and we will have nearly all answers.
Also tomorrow I will re-render this issue according to naming and other changes.

And yes I found how we can re-use IImmutable**

Stay tuned.

[safern]

I have the same question as @karelz, what is the difference between doing this and using ReadOnly property?

[dmitriyse]

Unfortunately this deep is question. I still working on a library with new proposed API preview. Code is better that 1000 words. Solution consist from multiple parts:

1. Interfaces Upgrade
2. List/Dictionary/HashSet collections upgrade
3. Linq Upgrade
4. new Immutable Slim API (was Frozen)
5. Missed IReadOnlySet improvement
6. Immutable Collections upgrade
   And hardly depends on implementation Champion "default interface methods" (16.3, Core 3) csharplang#52 (was !Lightweight! Default interface members implementation. Primary for backward compatibility of improved BCL interfaces. MINIMAL CLR CHANGES ARE REQUIRED. csharplang#222)

Current code will be useful wihout dotnet/csharplang#52 but with some amount of contract mangling.

[karelz]

@dmitriyse we will need a "short" description of the problem your code is trying to solve. Why don't you start with the questions I asked above?

Having complex library with new API proposed is unlikely going to help or answer any questions of WHY. Solution is second step. Problem description and agreement it is a problem worth solving needs to be the first step. Quantification of the problem is usually part of the problem discussion.

I just want to make sure you don't waste time building API proposal which we won't consider until we understand (and agree with) the problem it is trying to solve.

[dmitriyse]

I need this features in my project firstly. Secondly I wish that this improvements to become in BCL. It's seem enough general and useful.

1. We needs some guaranty more than IsReadOnly e.g Immutable. At runtime and at compile time. (IImmutable** types) So when I put property type to IReadOnly* and IImmutable** I instantly know what i have
2. We needs consistent collection contracts, for example IReadOnlySet gives not only access to data but also informs that variable contains some unique set
3. Inheritance of ICollection** from IReadOnly*** saves from headache with inheritance and in some places with contravariance.

[dmitriyse]

Please wait another day and I share class diagram.

[karelz]

I am not sure how class diagram can help explain WHY you need it. It will explain more HOW to solve it. Isn't it that case? ... Anyway, we can wait.

Why do you need the guarantee of Immutable? What kind of SW needs it? -- that is the basic question which needs to be thoroughly explained first.

[dmitriyse]

Finally I established how to combine all ideas together. First commit with very raw preview is published here https://github.com/dmitriyse/ClrCoder/tree/master/src/ClrCoder.Polyfill
(IEnumerableEx, IReadOnlyCollectionEx, ICollectionEx, etc. contracts are polyfills for future base contract upgrades)

The problem:

public class MyClass
{
    public MyClass(IReadOnlyList<string> someIds)
    {
        // Currently I cannot rely that someIds will never change.
        // I every time think: should I copy this collection or I can use it as-is.
        // Ok, it's not a trouble I can copy, but stop, what if this place will be performance critical ???
        // no I don't want to copy. 
        // Let assume nobody will never change this collection. <== TOTALLY WRONG!
        SomIds = someIds;
        // also I performed some loading based on this ids.
        // and store result in the instance.
        // ids list will be hardly used by this component and consumers of this components.
    }
  
    public IReadOnlyList<string> SomeIds {get;}
}

// Some other place, some newbie developer... 
public void SomeCreationPlace()
{ 
       // ...

       // Some algorithm with bugs.
       var ids = new List<string>();
       while (someCondition)
       {    
            for(int i = 0; i++; i <myVar)
            {
                ids.Add("test"+i);
            }
            // ids always changes but MyClass think that IReadOnlyList will never be changed.
            var myComp = new MyClass(ids);
            myComponents.Add(myCom);
            // Some other actions
            // Ids should be cleared here, but WE PUT SOME STUPID BUG HERE
       }
}

Final bug can be found in totally different place where consumers of consumer of consumer of MyComponent received KeyNotFound exception (for example).

According to this logic we can say, no no no, better I will make the copies.

Imagine we have deep call chain. Every time we cannot rely on IReadOnly** and make copies.
Again it's no so C# way to write stupid boilerplate.

What about IImmutableList ??? - it exactly gives guaranty of immutability.
Ok. but now try to implement custom component that implement it:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace ClrCoder.Collections.Immutable.Polyfill
{
    using System.Collections.Immutable;

    public class test: IImmutableList<int>
    {
        public IEnumerator GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public int Count
        {
            get
            {
                throw new NotImplementedException();
            }
        }

        public int this[int index]
        {
            get
            {
                throw new NotImplementedException();
            }
        }

        public IImmutableList<int> Clear()
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> Add(int value)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> Replace(int oldValue, int newValue, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> SetItem(int index, int value)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> RemoveAt(int index)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> RemoveRange(int index, int count)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> RemoveRange(IEnumerable items, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> RemoveAll(Predicate match)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> Remove(int value, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> InsertRange(int index, IEnumerable items)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> Insert(int index, int element)
        {
            throw new NotImplementedException();
        }

        public IImmutableList<int> AddRange(IEnumerable items)
        {
            throw new NotImplementedException();
        }

        public int LastIndexOf(int item, int index, int count, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }

        public int IndexOf(int item, int index, int count, IEqualityComparer equalityComparer)
        {
            throw new NotImplementedException();
        }
    }
}

Really too heavy. I do not want Add(), Remove(). I just what IReadOnlyList + Immutability guaranty.

CURRENTLY WE HAVE NOTHING.

We can introduce slim immutable contracts (with usual hierarchy):

public class MyClass
{
    // No comments all clear.
    public MyClass(IImmutableListSlim<string> someIds)
    {
        SomIds = someIds;
    }
   
    // This collection instance can travel across components, threads, call chains safely. 
    public IImmutableListSlim<string> SomeIds {get;}
}

This is only about why we needs IImutable*** slim collections.

Another big question how to inject this features effectively.
I will describe it in the next posts in this or next week.

[karelz]

OK, now I understand what you're trying to achieve high level.
The question is: How common is the pattern and how badly is it needed? Therefore does it belong to CoreFX?

[dmitriyse]

Let's scare a little bit. I added IsImmutable into IEnumerable, sounds crazy. Just because of that like changes we hardly needs implementation of dotnet/csharplang#52 (was dotnet/csharplang#222).
IsImmutable by default false. Also we needs to add freezable logic to standard collections. Plus we needs additional Linq for working with effective casting with normal/readonly/immutable.
For example:

public void Test()
{
       var mySet = new HashSet<string>(){"Id","abc", "dfdf"};
       var a = mySet.ToImmutable(); // Perform clone and returns IImmutableSetSlim<string>
       mySet.Freeze();        // mySet.IsImmutable now becomes true. (Actually IEnumerable<T>.IsImmutable)

       var b = mySet.ToImmutable(); // Returns light wrapper with IImmutableSetSlim<string> contract.
}

[dmitriyse]

OK, now I understand what you're trying to achieve high level.
The question is: How common is the pattern and how badly is it needed? Therefore does it belong to CoreFX?

There multiple ways to solve this problem:

1. API level, most effective benefits/efforts.
   We have clear contracts and semantics + we have runtime checks.

2. Language/ CLR level with for example immutable, readonly keywords like it was described here http://joeduffyblog.com/2016/11/30/15-years-of-concurrency/
   This is true way, but very hard

3. Annotations and analyzers, tools like R#
   Limited capabilities in runtime.

[karelz]

Even if it is API level, you can consider solving it on top of BCL, not necessarily in CoreFX (e.g. create FrozenCollection wrappers with IFrozenCollection).

[dmitriyse]

Enumeration, collections, collection contracts it's whole ecosystem (currently immutability unaware). Possibly it's time to improve, we also have inheritance inconsistency, missing of IReadOnlySet, miss of Comparable property on ISet, IDictionary. Probably something else.
With dotnet/csharplang#52 we can do those improvements without loosing backward compatibility.

So I am trying to design one solution BCL collections 2017+

Of course I can do it on top of BCL, but it will be new collections ecosystem with bridges to old.
(actually I go on this way. But I try to write it in polyfill style with ability for the future merge to CoreFX).

[karelz]

I see that you are very excited and motivated - that is great! However, I would like you to apply caution. Think things through first. Split them into separate isolated problems. Suggest APIs in small batches which logically belong together. Write down justifications and reasons for each API addition, list use cases. Get everyone on board with the direction and plan first.
And mainly, prepare for a long, long ride. Significant API design doesn't happen overnight - and from a good reason. It is very easy to miss details and optimize for the wrong thing. And there is never way back - because, once you ship it, you are stuck with it forever due to compatibility.

If you mix up all proposals together, then either the issue will not get any traction because it will be hard to grasp. And if it is truly necessary (not just easier) to do it all at once (you will need to convince everyone that's the case), we will likely need another place to have a very solid and lengthy design discussion, before we jump into such endeavor. GitHub issues are bad for lengthy design discussions.

[dmitriyse]

Thank you for your support.
Any ideas really should be long-time staged and maximally improved before become BCL. Also amount of consumers of the BCL code now becomes fantastically large (as you mentioned CoreFX is also used for Xamarin , UWP and Desktop) and will continue to grow.

So probably it's a wrong place to discuss improvement ideas and form them as a feature request.
It's more likely to be staged in some nuget package/ CLR fork like some other project was born for example by "Microsoft Research" department.

Also I found that is possible to compile all CLR/dotnet and try to play with S.P. CoreLib. Only after that we can talk here.

[dmitriyse]

We can close this issue, I found a way how to build useful nuget packages without BCL modifications (but with some restrictions and workarounds).
If this new API become popular, than it can be pulled to BCL with greater integration level.

[karelz]

Sounds good. Let us know when you are ready to start the discussion again - we can find the right place for it.