tags:

views:

171

answers:

9

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?

A: 

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.

Julian Aubourg
And I should have foreseen the negative votes.
Julian Aubourg
Your explanation is incorrect, that's why you're being downvoted (not by me, I didn't bother). Now we're left to speculate whether you don't understand Java generics because you gave up on Java prematurely, or you gave up on Java because you don't understand generics.
Carl Smotricz
Down-vote are to be expected when you don't give an answer and you just state your opinion about the situation. It's not helpful in any way.
HoLyVieR
The down votes are for the statement "There's no semantic reason not to allow your first affectation". There clearly is; see other answers. The downvotes aren't for slamming Java, but for being incorrect on a technical matter.
Daniel Martin
@Julian, maybe yes - Jon clearly explained why this limitation is not silly at all.
Andreas_D
I just don't accept an implementation of genericity where a list of apples is not a "sub-case" of a list of fruits. Oh sure, it makes the compiler dev's life a nightmare because you cannot add anything else but an apple to the original list... and that's a problem why? Because, IN JAVA, there's no way to make an object truly Immutable (yes, go and link away, I can debunk any immutability implementation and so can you). I could go on and on about java and how its design is flawed and how each decision impacts one another. Problem is, most people in here know about generics, not genericity.
Julian Aubourg
So, in short, I stand by my statement: there is no SEMANTIC reason not to allow the first affectation. It's forbidden because of limitations in the DESIGN of the language. Now, say it's subjective all you want, if you think for a minute you'll realize it's not.
Julian Aubourg
@Julian: Nope, I've thought about it and I still think the restriction makes sense *given that `List<T>` represents a mutable type which you can add elements to*. You can call that a bad design decision if you want, but once that decision has been made it makes perfect sense to keep type safety by preventing the wrong kind of element from being added to it.
Jon Skeet
@Julian: What if you want to keep the collection object mutable (not that you have a choice) yet also want to be sure it actually only contains one specific type of object?
BobTurbo
@JonSkeet, @BobTurbo: the whole problem is about the mutability of the object, hence why I talked about it in my own comments: should it have that heavy an impact on how generics are implemented? Most of the time, you'd need this kind of cast to give to a third-party which would read through the list. Sad truth is, the answer to the problem are immutable objects, not mutable and unreadable <? extends Fruit> because we all know how ugly code can get with this kind of generics filters. Not to dismiss you answer, Jon, but, to me, it is missing the real issue: lack of immutability in the language.
Julian Aubourg
@Julian: You don't need things to be immutable for this to become safe. (I'm not saying immutability wouldn't be a nice thing, but it's not necessary here.) Look at C# 4's variance, which is only allowed where it's safe - you can convert from an `IEnumerable<String>` to an `IEnumerable<Object>`, but not from an `IList<String>` to an `IList<Object>`. If a caller only wants to read through the list, it would therefore declare a parameter of type `IEnumerable<BaseType>`. The .NET collections aren't as neatly split into reading/writing as I'd like, but it's a valid alternative approach IMO.
Jon Skeet
@Julian: Furthermore, I think all of this *still* goes against your claim that there's "no semantic reason not to allow your first affectation" - the semantic reason *is* that `List<T>` is mutable, and that it therefore becomes unsafe.
Jon Skeet
@Jon: you actually proved my point: how is it a semantic issue when another language has ways around it? You can implement around the issue without immutability btw: be very heavy-handed and clone the collection or be more subtle and raise a runtime exception whenever one tries to add anything else but an instance of the original type parameter. Again, due to design limitations in Java, implicit cloning-on-affectation is a no-go and so is runtime type parameter control (because the information is just lost after compilation -- unless it changed since last time I checked)...
Julian Aubourg
Julian Aubourg
@Julian: Other languages have other ways round it *for other APIs*. You can't do this with the equivalent API in C# (`IList<T>`) for exactly the same reason. I think designing generics to start cloning lists all over the place would have been a *terrible* decision. Even if execution time checks had been available, they would have defeated a large point of using generics - *compile-time* type safty. I stand by *my* argument that within the rest of Java's design approach, the decisions around making this conversion fail in generics makes perfect sense and has nothing to do with laziness.
Jon Skeet
I think it would also be helpful if you'd define "semantic reason" here. You use the term an awful lot in a way which sounds like it's very important to you - so it would be useful if we made sure we all understood it in the same way.
Jon Skeet
@Jon: I'm glad you like how Java is designed, I don't. Semantic: Of or relating to meaning, especially meaning in language. See: a basket of apples IS a basket of fruits, hence you should be able to write: Basket<Apple> a; Basket<Fruit> f = a; and not HAVE TO write Basket<? extends Fruit> f = a; . What is the MEANING of declaring a basket of "things that are fruits" rather than a basket of fruits? None, it's a workaround due to poor design decision and implementation. When I realized I had to put List<? extends T> everywhere in place of List<T> is when I gave up on Java.
Julian Aubourg
@Jon, now this conversation is quickly turning into a "who'll get the last word" contest which I find quite frustrating and counter-productive. I'll try and explain to you why Java's implementation and design of generics is stupidly limited, you'll state that Java is like this and that is makes sense in that context. To get back to my first comment, I have been down-voted by people assuming I knew nothing about the subject and I was just ranting for the sake of ranting. If they can't see they're wrong by now, well, they never will.
Julian Aubourg
So you're just going to assume that anyone who disagrees with you is obviously wrong? While I didn't downvote you, I see no reason to think that those who did are expressing any opinion of *you* - they're disagreeing with the statements you made in your answer. I disagree with those statements too. I quite agree that Java's generics are limited in various ways; I'd love reified generics, the ability to use them for primitive types etc... but I simply *don't* agree with what you've posted for this case. I'm happy to agree to disagree, but please don't patronise those who *do* disagree with you.
Jon Skeet
You misunderstood me, Jon. Please, read the last couple of sentences from my previous post. The meaning is clear: if they can't see they're wrong assuming I knew nothing about generics, they never will (see the second comment which has been up-voted 3 times incidentally). This misunderstanding and you asking me for the definition of semantic (copied/pasted from an online dictionary, fyi) doesn't smell that good, but I have hard time imagining someone with a 200k SO reputation trolling away. Or should I? Nice dodge of the questions raised in the previous post, though. Like I said: frustrating.
Julian Aubourg
+11  A: 

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.

Jon Skeet
ah..! This works: List<? extends Tree>
SiLent SoNG
Thanks for explaining. Can you give an example of "within the array unsafe - they can fail at execution time, despite being fine at compile time."? -- Ignore it. I got the example.
SiLent SoNG
@SiLent SoNG: Yes, basically do exactly the same as my "broken" example but setting a value in an array instead :)
Jon Skeet
A: 

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

http://download.oracle.com/docs/cd/E17409_01/javase/tutorial/extra/generics/subtype.html

BobTurbo
+1  A: 

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.

Andrei Fierbinteanu
+1  A: 

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

Draco Ater
The reason is *somewhat* the same - but Java allows variance in different forms.
Jon Skeet
+2  A: 

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).

sepp2k
This explains the design difference between Array and Generics. This is exactly what I wanted to ask after seeing Jon Skeet's explanation! Thanks for answering.
SiLent SoNG
+2  A: 

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.

Daniel Martin
+1  A: 

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.

tjin
A: 

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).

lindelof
It's not really to do with type erasure. .NET generics don't have type erasure, but they have the same basic issue. I suppose without type erasure you *could* have an execution time exception when adding - but as the point of generics is to put type safety at *compile* time, it doesn't really make much difference here.
Jon Skeet