Java Generics: Cannot cast List<SubClass> to List<SuperClass>?

Just come across with this problem:

List<DataNode> a1 = new ArrayList<DataNode>();
List<Tree> b1 = a1;  // compile error: incompatible type

Where the type DataNode is a subtype of Tree.

public class DataNode implements Tree

To my surprise, this works for array:

DataNode[] a2 = new DataNode[0];
Tree[] b2 = a2;   // this is okay

This likes a bit strange. Can anyone give an explanation on this?

What you're seeing in the second case is array covariance. It's a bad thing IMO, which makes assignments within the array unsafe - they can fail at execution time, despite being fine at compile time.

In the first case, imagine that the code did compile, and was followed by:

b1.add(new SomeOtherTree());
DataNode node = a1.get(0);

What would you expect to happen?

You can do this:

List<DataNode> a1 = new ArrayList<DataNode>();
List<? extends Tree> b1 = a1;

... because then you can only fetch things from b1, and they're guaranteed to be compatible with Tree. You can't call b1.add(...) precisely because the compiler won't know whether it's safe or not.

Have a look at this section of Angelika Langer's Java Generics FAQ for more information.

If you do have to cast from List<DataNode> to List<Tree>, and you know it is safe to do so, then an ugly way to achieve this is to do a double-cast:

List<DataNode> a1 = new ArrayList<DataNode>();

List<Tree> b1 = (List<Tree>) (List<? extends Tree>) a1;

The short explanation: it was a mistake to allow it originally for Arrays.

The longer explanation:

Suppose this were allowed:

List<DataNode> a1 = new ArrayList<DataNode>();
List<Tree> b1 = a1;  // pretend this is allowed

Then couldn't I proceed to:

b1.add(new TreeThatIsntADataNode()); // Hey, b1 is a List<Tree>, so this is fine

for (DataNode dn : a1) {
  // Uh-oh!  There's stuff in a1 that isn't a DataNode!!
}

Now an ideal solution would allow the kind of cast you want when using a variant of List that was read-only, but would disallow it when using an interface (like List) that's read-write. Java doesn't allow that kind of variance notation on generics parameters, (*) but even if it did you wouldn't be able to cast a List<A> to a List<B> unless A and B were identical.

(*) That is, doesn't allow it when writing classes. You can declare your variable to have the type List<? extends Tree>, and that's fine.

List<DataNode> does not extend List<Tree> even though DataNode extends Tree. That's because after your code you could do b1.add(SomeTreeThatsNotADataNode), and that would be a problem since then a1 would have an element that is not a DataNode in it as well.

You need to use wildcard to achieve something like this

List<DataNode> a1 = new ArrayList<DataNode>();
List<? extends Tree> b1 = a1;
b1.add(new Tree()); // compiler error, instead of runtime error

On the other hand DataNode[] DOES extend Tree[]. At the time it seemed like the logical thing to do, but you can do something like:

DataNode[] a2 = new DataNode[1];
Tree[] b2 = a2; // this is okay
b2[0] = new Tree(); // this will cause ArrayStoreException since b2 is actually a DataNode[] and can't store a Tree

This is why when they added generics to Collections they chose to do it a little differently to prevent runtime errors.

When arrays were designed (i.e. pretty much when java was designed) the developers decided that variance would be useful, so they allowed it. However this decision was often criticized because it allows you to do this (assume that NotADataNode is another subclass of Tree):

DataNode[] a2 = new DataNode[1];
Tree[] b2 = a2;   // this is okay
b2[0] = new NotADataNode(); //compiles fine, causes runtime error

So when generics were designed it was decided, that generic data structures should only allow explicit variance. I.e. you can't do List<Tree> b1 = a1;, but you can do List<? extends Tree> b1 = a1;.

However if you do the latter, trying to use the add or set method (or any other method which takes a T as an argument) will cause a compile error. This way it is not possible to make the equivalent of the above array problem compile (without unsafe casts).

Short answer: List a1 is not the same type as List b2; In a1 you can put any objecttype wichs extens DataNode. So it may contain other types than Tree.

DataNode might be a subtype of Tree, but List DataNode is not a subtype of List Tree.

https://docs.oracle.com/javase/tutorial/extra/generics/subtype.html

It is the answer from C#, but I think it doesn't actually matter here, as the reason is the same.

"In particular, unlike array types, constructed reference types do not exhibit “covariant” conversions. This means that a type List<B> has no conversion (either implicit or explicit) to List<A> even if B is derived from A. Likewise, no conversion exists from List<B> to List<object>.

The rationale for this is simple: if a conversion to List<A> is permitted, then apparently one can store values of type A into the list. But this would break the invariant that every object in a list of type List<B> is always a value of type B, or else unexpected failures may occur when assigning into collection classes."

http://social.msdn.microsoft.com/forums/en-US/clr/thread/22e262ed-c3f8-40ed-baf3-2cbcc54a216e

This is a classic problem with generics implemented with type erasure.

Suppose that your first example really did work. You would then be able to do the following:

List<DataNode> a1 = new ArrayList<DataNode>();
List<Tree> b1 = a1;  // suppose this works
b1.add(new Tree());

But since b1 and a1 refer to the same object, it means that a1 now refers to a List that holds both DataNodes and Trees. If you try to get that last element, you will get an exception (can't remember which one).

Well, I'll be honest here: lazy genericity implementation.

There's no semantic reason not to allow your first affectation.

Incidentally, though I adored templating in C++, generics, together with the kind of silly limitation we have here, are the main reason why I gave up on Java.