C# Read-Only Collections and LSP

November 22, 2014

I often see programmers saying that .NET read-only collections violate Liskov Substitution Principle (LSP). Do they? The quick answer is no, they don’t, because IList interface has IsReadOnly flag. The exception is the Array class, it does violate LSP since version 2.0 of .NET. But let’s go through the whole story first.

C# Read-Only Collections: the history

Let’s look at how the read-only collection interfaces evolved in .NET (click to enlarge).

As you can see at this diagram, the IList interface contains the IsReadOnly and IsFixedSize flags. The initial idea was to split these two notions. A collection might be read-only, which means it can’t be changed in any way. Also, it might be of fixed size, which means it doesn’t allow items addition or removal, but it allows to change existing items. In other words, IsReadOnly collections are always IsFixedSize, but IsFixedSize collections are not always IsReadOnly.

So, if you want to create, say, a MyReadOnlyCollection class you’ll need to implement these properties – IsReadOnly and IsFixedSize – so that both of them return true. BCL didn’t have read-only collections at the time of .NET 1.0, but the BCL architects laid the foundation for future implementations. The intention was that you’d be able to work with such collections polymorphically using code like this:

public void AddAndUpdate(IList list)
{
    if (list.IsReadOnly)
    {
        // No action
        return;
    }

    if (list.IsFixedSize)
    {
        // Update only
        list[0] = 1;
        return;
    }

    // Both add and update
    list[0] = 1;
    list.Add(1);
}

Of course, this is not a great way to work with collections, but it allows you to avoid exceptions without checking the actual type. Thus, this design doesn’t violate LSP. Of course, nobody does this checks when they work with IList (neither do I). That’s why there’re so many complaints against collections saying that they violate LSP.

.NET 2.0

After generics had been introduced in .NET 2.0, BCL team got a chance to build a new version of the interface hierarchy. They did some work making collections more coherent. Besides pulling some members up to ICollection<T>, they decided to remove IsFixedSize flag.

It was made because Array was the only class which needed it. Array was the only class which forbids addition and removal of items, but allows modification of existing items. The BCL team decided that IsFixedSize flag brought too much of complexity. The interesting thing here is that they changed implementation of IsReadOnly flag for the Array class so that it no longer returns the actual state of affairs:

public void Test()
{
    int[] array = { 1 };
    bool isReadOnly1 = ((IList)array).IsReadOnly; // isReadOnly1 is false
    bool isReadOnly2 = ((ICollection<int>)array).IsReadOnly; // isReadOnly2 is true
}

IsReadOnly is true for Array, but it still can be changed. That is where the LSP violation takes its place. If we have a method that accepts IList<int>, we can’t just write code like the following:

public void AddAndUpdate(IList<int> list)
{
    if (list.IsReadOnly)
    {
        // No action
        return;
    }

    // Both add and update
    list[0] = 1;
    list.Add(1);
}

If we pass ReadOnlyCollection<int> object to this method, then - just as designed - no action will occur, because the collection is read-only. On the other hand, List<int> object will be changed with both update and addition. But if we pass an array, nothing will happen because it returns true for ICollection<T>.IsReadOnly. And there’s no way to check whether we can update items in a collection other than checking its type:

public void AddAndUpdate(IList<int> list)
{
    if (list is int[])
    {
        // Update only
        list[0] = 1;
        return;
    }

    if (list.IsReadOnly)
    {
        // No action
        return;
    }

    // Both add and update
    list[0] = 1;
    list.Add(1);
}

Thus, arrays violate LSP. Note that arrays violate this principle in case of generic interfaces only.

Did Microsoft go wrong with this? Well, it was a trade-off. It was a conscious decision: such design is simpler than before, but it breaks LSP in one particular case.

.NET 4.5

Despite the design became simpler, it still had a significant disadvantage: you had to check the IsReadOnly flag in order to find out whether a collection could be changed. That’s not how programmers used to do such work. Actually, nobody did it. This property was used for scenarios with data binding only: data binding is one-way if IsReadOnly is true and two-way otherwise.

For other scenarios everyone just used IEnumerable<T> interface or ReadOnlyCollection<T> class. That’s why two new interfaces were added in .NET 4.5: IReadOnlyCollection<T> and IReadOnlyList<T>. These interfaces were added to an existing ecosystem, so they shouldn’t introduce any breaking changes. That’s why ReadOnlyCollection<T> implements IList, IList<T> and IReadOnlyList<T> interfaces and not just IReadOnlyList<T>. Also, that’s why IList<T> doesn’t inherit from IReadOnlyList<T>. Such changes would break existing assemblies, compiled with the older versions of .NET. In order to make them work, you’d need to recompile them with the new version.

Rewriting everything from scratch

Although the actual state of affairs can’t be changed because of backward comparability, it is interesting to think of the way it would look like if they were implemented today.

I suppose the class diagram would look like this (click to enlarge):

Here is what I did:

Non-generic interfaces were removed as they don’t add any value to the whole picture.
IFixedList<T> interface was added so that Array doesn’t have to implement IList<T> anymore.
ReadOnlyCollection<T> class was renamed to ReadOnlyList<T> because this name seems more applicable for it. Also, it implements IReadOnlyList<T> only.
No IsReadOnly and IsFixedSize flags. They can be added for scenarios with data binding, but I removed them to show that they are no longer required for working with collections polymorphically.

LSP question

There’s an interesting code example in .NET:

public static int Count<T>(this IEnumerable<T> source)
{
    ICollection<T> collection1 = source as ICollection<T>;
    if (collection1 != null)
        return collection1.Count;

    ICollection collection2 = source as ICollection;
    if (collection2 != null)
        return collection2.Count;

    int count = 0;
    using (IEnumerator<T> enumerator = source.GetEnumerator())
    {
        while (enumerator.MoveNext())
            checked { ++count; }
    }

    return count;
}

It’s an implementation of Count extension method for LINQ-to-objects from Enumerable class. The input object is tested for comparability with ICollection interfaces in order to calculate items count. Does this implementation violate LSP? Think a minute before reading the answer.

No, it doesn’t. Although this method iterate through the subtypes of IEnumerable<T>, they all have coherent implementations. In other words, ICollection.Count and ICollection<T>.Count properties have the same postconditions as the statement that counts the items with the while expression.

Summary

.NET BCL suffers from backward comparability requirements just like the most of the other popular libraries. It would be much easier if it could be rewritten from scratch with all the knowledge we got for the past years. Although it can’t be done, we can mitigate the pain using IReadOnlyCollection<T> and IReadOnlyList<T> in places where IEnumerable<T> is not enough.