Why does List.of() in Java not return a typed immutable list?

Question

The list returned by the method List.of(E... elements) in java does return an immutable list, but this is not visible at all by looking at the created list. The created list simply throws an Exception instead of not showing the possiblity to change the list at all. My point is, that List.of(E... elements) should return a ImmutableList that extends List. This way the user can decide if he cares to show this fact of immutability or not.

But I don't find anybody complaining or showing alternative solutions. Even Guava and Apache Commons don't do this by default. Only Guava gives the possibilty to create it (albeit with a lot of code):

List<String> list = new ArrayList<String>(Arrays.asList("one", "two", "three"));
ImmutableList<String> unmodifiableList = ImmutableList.<String>builder().addAll(list).build();

But even this class has a (deprecated) add and remove method.

Can anyone tell me why nobody cares about this (seemingly fundamental) issue?

Answer 1

It's not that nobody cares; it's that this is a problem of considerable subtlety.

The original reason there isn't a family of "immutable" collection interfaces is because of a concern about interface proliferation. There could potentially be interfaces not only for immutability, but synchronized and runtime type-checked collections, and also collections that can have elements set but not added or removed (e.g., Arrays.asList) or collections from which elements can be removed but not added (e.g., Map.keySet).

But it could also be argued that immutability is so important that it should be special-cased, and that there be support in the type hierarchy for it even if there isn't support for all those other characteristics. Fair enough.

The initial suggestion is to have an ImmutableList interface extend List, as

ImmutableList <: List <: Collection

(Where <: means "is a subtype of".)

This can certainly be done, but then ImmutableList would inherit all of the methods from List, including all the mutator methods. Something would have to be done with them; a sub-interface can't "disinherit" methods from a super-interface. The best that could be done is to specify that these methods throw an exception, provide default implementations that do so, and perhaps mark the methods as deprecated so that programmers get a warning at compile time.

This works, but it doesn't help much. An implementation of such an interface cannot be guaranteed to be immutable at all. A malicious or buggy implementation could override the mutator methods, or it could simply add more methods that mutate the state. Any programs that used ImmutableList couldn't make any assumptions that the list was, in fact, immutable.

A variation on this is to make ImmutableList be a class instead of an interface, to define its mutator methods to throw exceptions, to make them final, and to provide no public constructors, in order to restrict implementations. In fact, this is exactly what Guava's ImmutableList has done. If you trust the Guava developers (I think they're pretty reputable) then if you have a Guava ImmutableList instance, you're assured that it is in fact immutable. For example, you could store it in a field with the knowledge that it won't change out from under you unexpectedly. But this also means that you can't add another ImmutableList implementation, at least not without modifying Guava.

A problem that isn't solved by this approach is the "scrubbing" of immutability by upcasting. A lot of existing APIs define methods with parameters of type Collection or Iterable. If you were to pass an ImmutableList to such a method, it would lose the type information indicating that the list is immutable. To benefit from this, you'd have to add immutable-flavored overloads everywhere. Or, you could add instanceof checks everywhere. Both are pretty messy.

(Note that the JDK's List.copyOf sidesteps this problem. Even though there are no immutable types, it checks the implementation before making a copy, and avoids making copies unnecessarily. Thus, callers can use List.copyOf to make defensive copies with impunity.)

As an alternative, one might argue that we don't want ImmutableList to be a sub-interface of List, we want it to be a super-interface:

List <: ImmutableList

This way, instead of ImmutableList having to specify that all those mutator methods throw exceptions, they wouldn't be present in the interface at all. This is nice, except that this model is completely wrong. Since ArrayList is a List, that means ArrayList is also an ImmutableList, which is clearly nonsensical. The problem is that "immutable" implies a restriction on subtypes, which can't be done in an inheritance hierarchy. Instead, it would need to be renamed to allow capabilities to be added as one goes down the hierarchy, for example,

List <: ReadableList

which is more accurate. However, ReadableList is altogether a different thing from an ImmutableList.

Finally, there are a bunch of semantic issues that we haven't considered. One concerns immutability vs. unmodifiability. Java has APIs that support unmodifiability, for example:

List<String> alist = new ArrayList<>(...);
??? ulist = Collections.unmodifiableList(alist);

What should the type of ulist be? It's not immutable, since it will change if somebody changes the backing list alist. Now consider:

???<String[]> arlist = List.of(new String[] { ... }, new String[] { ... });

What should the type be? It's certainly not immutable, as it contains arrays, and arrays are always mutable. Thus it's not at all clear that it would be reasonable to say that List.of returns something immutable.

Answer 2

Removing add, remove, etc. from all the Collection types and creating subinterfaces MutableCollection, MutableList, MutableSet would double the number of Collection interfaces, which is a complexity cost to be considered. Furthermore, Collections aren't cleanly separated into Mutable and Immutable: Arrays.asList supports set, but not add.

Ultimately there's a tradeoff to be made about how much to capture in the type system and how much to enforce at runtime. Reasonable people can disagree as to where to draw the line.

Answer 3

I would say that since commonly collections tend to (or at least should) be treated as "immutable by default" (meaning you're rarely modifying collections that you didn't create), it's not very important to specify that "this is immutable". It would be more useful to specify "you can safely modify this collection if you wish".

Secondly, your suggested approach wouldn't work. You can't extend List and hide methods, so the only option would be to make it return an ImmutableList that's not a subtype of List. That would make it useless, as it would require a new ImmutableList interface, and any existing code wouldn't be able to use it.

So is this optimal design? No, not really, but for backwards compatibility that's not going to change.