ReadOnlyCollection vs Liskov - How to correctly model immutable representations of a mutable collection

Question

Liskov-substitution principle requires that subtypes must satisfy the contracts of super-types. In my understanding, this would entail that ReadOnlyCollection<T> violates Liskov. ICollection<T>'s contract exposes Add and Remove operations, but the read only subtype does not satisfy this contract. For example,

IList<object> collection = new List<object>();
collection = new System.Collections.ObjectModel.ReadOnlyCollection<object>(collection);
collection.Add(new object());

    -- not supported exception

There is clearly a need for immutable collections. Is there something broken about .NET's way of modeling them? What would be the better way to do it? IEnumerable<T> does a good job of exposing a collection while, at least, appearing to be immutable. However, the semantics are very different, primarily because IEnumerable doesn't explicitly expose any of state.

In my particular case, I am trying to build an immutable DAG class to support an FSM. I will obviously need AddNode / AddEdge methods at the beginning but I don't want it to be possible to change the state machine once it is already running. I'm having difficulty representing the similarity between the immutable and mutable representations of the DAG.

Right now, my design involves using a DAG Builder up front, and then creating the immutable graph once, at which point it is no longer editable. The only common interface between the Builder and the concrete immutable DAG is an Accept(IVisitor visitor). I'm concerned that this may be over-engineered / too abstract in the face of possibly simpler options. At the same time, I'm having trouble accepting that I can expose methods on the my graph interface that may throw NotSupportedException if the client gets a particular implementation. What is the right way to handle this?

Answer 1

You could always have a (read-only) graph interface, and extend it with a read/write modifiable-graph interface:

public interface IDirectedAcyclicGraph
{
    int GetNodeCount();
    bool GetConnected(int from, int to);
}

public interface IModifiableDAG : IDirectedAcyclicGraph
{
    void SetNodeCount(int nodeCount);
    void SetConnected(int from, int to, bool connected);
}

(I can't figure out how to split these methods into get/set halves of a property.)

// Rubbish implementation
public class ConcreteModifiableDAG : IModifiableDAG
{
    private int nodeCount;
    private Dictionary<int, Dictionary<int, bool>> connections;

    public void SetNodeCount(int nodeCount) {
        this.nodeCount = nodeCount;
    }

    public void SetConnected(int from, int to, bool connected) {
        connections[from][to] = connected;
    }

    public int GetNodeCount() {
        return nodeCount;
    }

    public bool GetConnected(int from, int to) {
        return connections[from][to];
    }
}

// Create graph
IModifiableDAG mdag = new ConcreteModifiableDAG();
mdag.SetNodeCount(5);
mdag.SetConnected(1, 5, true);

// Pass fixed graph
IDirectedAcyclicGraph dag = (IDirectedAcyclicGraph)mdag;
dag.SetNodeCount(5);          // Doesn't exist
dag.SetConnected(1, 5, true); // Doesn't exist

This is what I wish Microsoft had done with their read-only collection classes - made one interface for get-count, get-by-index behaviour etc., and extend it with an interface to add, change values etc.

Answer 2

I don't think that your current solution with the builder is overengineered.

It solves two problems:

1. Violation of LSP
   You have an editable interface whose implementations will never throw NotSupportedExceptions on AddNode / AddEdge and you have a non-editable interface that doesn't have these methods at all.

2. Temporal coupling
   If you would go with one interface instead of two, that one interface would need to somehow support the "initialization phase" and the "immutable phase", most likely by some methods marking the start and possibly end of those phases.