Generic arrays

[akishore]

Hi,

I was coding when I wrote a line which would not compile:

elements = new T[rows][cols];

where T is a generic type, elements is of type T[][] and rows/cols are ints. The error was:

Cannot create a generic array of type T.

This made no sense to me, so I googled around and found a few interesting threads, etc.

http://forum.java.sun.com/thread.jspa?forumID=316&threadID=530823
http://forum.java.sun.com/thread.jspa?forumID=316&threadID=564355
http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf (section 7.3)

But even after reading all these, I am thoroughly confused and unconvinced that allowing generic arrays would remove type-safety (many examples don't seem to be completely valid, since it seems that this removal of type-safety would be the case even if you replaced all arrays with Lists, for example).

So I have two questions.

1. Can anyone help explain why generic arrays aren't allowed?

2. The solution proposed by many is to create an array of Objects and cast it to an array of type T. In fact, the constructor for ArrayList<T> actually does exactly that--one of the links above shows this, e.g.

T[] array = (T[]) (new Object[10]);

Casting is bad style in most cases, but is this one acceptable if we really would prefer/need to use generic arrays?

Thanks!

Aseem



EDIT:

When I try to use the casting workaround, e.g.

T[] array = (T[]) (new Object[10]);

I get the notorious "erased type" warning:

The cast from Object[] to T[] is actually checking against the erased type Object[].

Now, I understand this warning if I am casting from a Collection<A> to a List<A>, for example, because the generic information is lost ("erased") at run-time, so the compiler can only check that the Collection is a List, not that the Collection is a List of type A. But, I don't understand why this warning is occuring with arrays??

Isn't the compiler definitely able to check at runtime whether or not the array is of type Object or of type T??

Thanks,
Aseem

[Dave Glasser (LA)]

To answer your question 1: type variables like T "don't exist" at runtime, so you won't really be able to create a new T[], because there's no way to determine what the actual type of that array will be.

So why are you allowed to make a List<T>? Because the "generic argument" to List *also* doesn't exist at runtime -- the runtime class here will always just be List.

[Vincent Yeung (TA)]

Good question.  Regarding your added question about why casting as (T[]) gives a warning--the JVM can indeed check if an array is, say, of type String[] in runtime, but it can't check if it's of type T[] because it doesn't know what T is.

To elaborate on Dave's response to your original question:

I find the first response here to be rather concise and well-written (I believe it to be by Neal Gafter, one of the Java gurus at Sun until recently):
http://forum.java.sun.com/thread.jspa?forumID=316&threadID=457033

(note: 'statically' means during compile-time, and 'dynamically' means during run-time)

Notice the reason he writes "BOOM!" on the last line of code. 
1. If generic arrays were allowed, everything until that line would work--even oa[0] = new Box<Integer>(3);!.  That's because Java checks if this assignment is valid dynamically, and at runtime, oa points to a Box[] (remember generic type information is lost), and you're assigning a Box to it, so all's good. 
2. If the JVM were able to determine that the assignment was invalid (e.g. if you try to put an Integer in an array of runtime type String[]), it would perform the well-specified behavior of throwing an ArrayStoreException, but here this error would be missed, and you'd have a vicious problem on the final line.

Notice another difference between arrays and classes is that the generic List equivalent of
Object[] oa = bsa; gives a compile error (i.e. you can't assign a List<Box<String>> to a List<Object>).  That allows the compiler to statically check the type safety of generic class operations.

The post mentions a proposal to introduce variance on arrays in Java; here's a draft of such a proposal http://www.daimi.au.dk/~plesner/variance/docs/variance-whitepaper.pdf.  See section 3.

Casting is not necessarily bad, but you might want to reconsider if it is really best to use an array for whatever you are doing.  Speak with your TA about your particular case.

[akishore]

Vincent,

That was a really helpful post. Thanks so much! 

After reading Neal Gafter's post, it makes sense. I also read most of the paper and it was nice because I had done some reading on variance earlier today, because a few posts on this generic array issue alluded to it (on that note, Wikipedia's entry for contravariance/covariance is really great)... but had no idea just how it applied, because I didn't realize the difference between classes and arrays in terms of dynamic vs. static checking.

After the reading, I feel quite a bit in favor of variance (though I did not like the syntax used in this paper at all... I much prefer something like List<? contravar Integer> or List<? covar Integer>, etc.... one could very easily mix up + and - and which means which). I notice that Neil Gafter says that the idea was rejected for Tiger (which according to Wikipedia is the codename for J2SE 5.0)... do you know why?

Thanks again for your help and suggestion.

Aseem

[C. Scott Ananian (TA)]

I was involved in the spec process for generics in Java 1.5.  Variance actually *did* make it to 1.5 -- in the form of the "super" and "extends" keywords, which were deemed to fix the confusing nature of "+" and "-".  Variance on arrays as well was supported in all of the betas of 1.5, but was removed for release-engineering reasons only: the new issues it introduced were understood but a solution hadn't been prototyped yet and it was thought too risky to make Sun's flagship production compiler the first prototype of array variance.  I had to rewrite a lot of my code when this happened, sigh.

Please avoid the Object[] -> T[] cast at all costs in your code.  The reason why array variance was dropped is that you can do the same thing with (Array)List<T>, with almost identical performance.  Arrays of generics don't offer such a compelling benefit over List of generics that they merited the risk to the release.  If you remember, I asked Gilad when he was here if he thought T[] would ever be supported, and he said no -- it just doesn't fundamentally do anything you couldn't otherwise do.

If you're curious, you can look at the implementation of ArrayList<T> in Sun's library, where you'll indeed find an Object[] -> T[] cast at the heart of it.  You can think of using ArrayList<T> as a means to wrap this fundamental ugliness with an interface that has been proven type-safe, so that you don't have to do the ugly thing in your own code.

[akishore]

Actually, Scott, I did read a few of your posts on the forum. I believe you are "fredastaire"? Good stuff. 

Thanks for the helpful comments. I did think of the possibility of using ArrayLists; I just thought arrays would be easier in this specific case where I'm actually representing a 2D array (matrix), so it's easier to write T[][] than ArrayList<ArrayList<T>> or List<List<T>>, but no big deal.

Thanks again,
Aseem

[C. Scott Ananian (TA)]

There's also some historical stuff at http://cscott.net/Projects/GJ/ .

Yes, List<List<T>> is slightly uglier than T[][], but you can always do:

private class L<T> extends ArrayList<T> { public L() { super(16/*size of yr arrays*/); } }

and then it's just L<L<T>>, which is only two characters longer (but admittedly very ugly!).

Better would be:

private class Matrix extends ArrayList<List<MyType>> { ... }

and then you can have human-meaningful type declarations w/o having to type all those angle brackets repeatedly.