Does Java's `AbstractImmutableList` violate Liskov's Substitution Principle? [duplicate]

Solution 1:

LSP says that every subclass must obey the same contracts as the superclass. Wether or not this is the case for Collections.unmodifiableXXX() thus depends on how this contract reads.

The objects returned by Collections.unmodifiableXXX() throw an exception if one tries to call any modifying method upon them. For instance, if add() is called, an UnsupportedOperationException will be thrown.

What is the general contract of add()? According to the API documentation it is:

Ensures that this collection contains the specified element (optional operation). Returns true if this collection changed as a result of the call. (Returns false if this collection does not permit duplicates and already contains the specified element.)

If this was the full contract, then indeed the unmodifiable variant could not be used in all places where a collection can be used. However, the specification continues and also says that:

If a collection refuses to add a particular element for any reason other than that it already contains the element, it must throw an exception (rather than returning false). This preserves the invariant that a collection always contains the specified element after this call returns.

This explicitly allows an implementation to have code which does not add the argument of add to the collection but results in an exception. Of course this includes the obligation for the client of the collection that they take that (legal) possibility into account.

Thus behavioural subtyping (or the LSP) is still fulfilled. But this shows that if one plans to have different behaviours in subclasses that must also be foreseen in the specification of the toplevel class.

Good question, by the way.

Solution 2:

Yes, I believe you have it correct. Essentially, to fulfill the LSP you have to be able to do anything with a subtype that you could do with the supertype. This is also why the Ellipse/Circle problem comes up with the LSP. If an Ellipse has a setEccentricity method, and a Circle is a subclass of Ellipse, and the objects are supposed to be mutable, there is no way that Circle can implement the setEccentricity method. Thus, there is something you can do with an Ellipse that you can't do with a Circle, so LSP is violated.† Similarly, there is something you can do with a regular List that you can't do with one wrapped by Collections.unmodifiableList, so that's an LSP violation.

The problem is that there is something here that we want (an immutable, unmodifiable, read-only list) that is not captured by the type system. In C# you could use IEnumerable which captures the idea of a sequence you can iterate over and read from, but not write to. But in Java there is only List, which is often used for a mutable list, but which we would sometimes like to use for an immutable list.

Now, some might say that Circle can implement setEccentricity and simply throw an exception, and similarly an unmodifiable list (or an immutable one from Guava) throws an exception when you try to modify it. But that doesn't really mean that it is-a List from the point of view of the LSP. First of all, it at least violates the principle of least surprise. If the caller gets an unexpected exception when trying to add an item to a list, that is quite surprising. And if the calling code needs to take steps to distinguish between a list it can modify and one it can't (or a shape whose eccentricity it can set, and one it can't), then one is not really substitutable for the other.

It would be better if the Java type system had a type for a sequence or collection that only allowed iterating over, and another one that allowed modification. Perhaps Iterable can be used for this, but I suspect it lacks some features (like size()) that one would really want. Unfortunately, I think this is a limitation of the current Java collections API.

Several people have noted that the documentation for Collection allows an implementation to throw an exception from the add method. I suppose that this does mean that a List that cannot be modified is obeying the letter of the law when it comes to the contract for add but I think that one should examine one's code and see how many places there are that protect calls to mutating methods of List (add, addAll, remove, clear) with try/catch blocks before arguing that the LSP is not violated. Perhaps it isn't, but that means that all code that calls List.add on a List it received as a parameter is broken.

That would certainly be saying a lot.

(Similar arguments can show that the idea that null is a member of every type is also a violation of the Liskov Substitution Principle.)

† I know that there are other ways of addressing the Ellipse/Circle problem, such as making them immutable, or removing the setEccentricity method. I'm talking here only about the most common case, as an analogy.

Solution 3:

I don't believe it's a violation because the contract (i.e. the List interface) says that the mutation operations are optional.