Arrays in Java Generics
What are the issues regarding arrays in Java Generics?

Angelika Langer & Klaus Kreft

Arrays in Java Generics

Arrays of parameterized types and arrays of type variables exhibit counter-intuitive behavior. Below is an explanation of the issue, which illustrates why it might make sense to ban both arrays of parameterized types and arrays of type variables from Java Generics.

Arrays of Parameterized Types

Covariance

Java arrays have the property that there types are covariant , which means that an array of supertype references is a supertype of an array of subtype references.That is, Object[] is a supertype of String[] for example. As a result of covariance all the type rules apply that are customary for sub- and supertypes: a subtype array can be assigned to a supertype array variable, subtype arrays can be passed as arguments to methods that expect supertype arrays, and so on and so forth.Here is an example:

Object[] objArr = new String[10];// fine

In contrast, generic collections are not covariant. An instantiation of a parameterized type for a supertype is not considered a supertype of an instantiation of the same parameterized type for a subtype.That is, a LinkedList<Object> is not a supertype of LinkedList<String> and consequently a LinkedList<String> cannot be used where a LinkedList<Object> is expected; there is no assignment compatibility between those two instantiations of the same parameterized type, etc.Here is an example that illustrates the difference:

LinkedList<Object> objLst = new LinkedList<String>(); // compile-time error

Runtime Type Information

Java arrays carry runtime type information that identifies the type of the elements contained. Generic collections have no runtime type information about their element type. Here are some examples showing the static type of the reference variables referring to an array or collection and the dynamic type of referenced array or collection:

	static type	dynamic type
`String[] strArr = new String[10];`	`String[]`	`String[]`
`Object[] objArr = new String[10];`	`Object[]`	`String[]`
`LinkedList<String> strLst = new LinkedList<String>();`	`LinkedList<String>`	`LinkedList`

The runtime type information about the element type of array elements is used when elements are stored in an array. Consider the following example:

1 Object[] objArr = new String[10];

2 objArr[0] = new Object(); // compiles; fails at runtime with ArrayStoreException

The reference variable of type Object[] refers to a String[] and for this reason only strings should be stored in the referred to array. Indeed, at runtime a so-called array store check is performed. It uses the information about the array element type to perform a type check. In our example the array store check fails because an Object reference must not be stored in a String[]. The JVM raises a ArrayStoreException to indicate the type mismatch.

An equivalent store check is not needed for generic collections, because a reference to a supertype collection cannot refer to a subtype collection:

1 LinkedList<Object> objLst = new LinkedList<String>(); // compile-time error

2 objLst.add(new Object());

We can never get to line 2 because line 1 does not compile.

Parameterized Types As Array Elements

Problems arise when an array holds elements of a parameterized type. The array store uses the dynamic type of the array element type for the array store check. As a result of type erasure, elements of a parameterized type do not have exact runtime type information. What are the consequences?

Consider the example below. It uses a parameterized Pair type that is shown in Listing 1.

Listing 1: Sketch of a Pair type

public final class Pair<X,Y> {

private X fst;

private Y snd;

public Pair(X fst, Y snd) {this.fst=fst; this.snd=snd;}

public X getFirst() { return fst; }

public Y getSecond() { return snd; }

}

1 Pair<Integer,Integer>[] intPairArr = new Pair<Integer,Integer>[10];

2 Object[] objArr = intPairArr;

3 objArr[0] = new Pair<String,String>("",""); // should fail, but succeeds

The array assignment in line 2 compiles as before, because arrays are covariant and an Object[] is considered a supertype of Pair<Integer,Integer>[]. At runtime an array store check must be performed in line 3 when an array element is assigned. We would expect that the check fails because we are not supposed to store a Pair<String,String> in a Pair<Integer,Integer>[]. However, the JVM cannot detect any type mismatch here: at runtime, after type erasure, objArr has the dynamic type Pair[] and the element to be stored has the matching dynamic type Pair. Hence the store check succeeds.

We end up in a counter-intuitive situation. The array, that the reference variables objArr and intPairArr refer to, contains different types of pairs instead of pairs of the same type. This is in contradiction to the expectation that arrays hold elements of the same type or subtypes thereof. This counter-intuitive situation is likely to lead to program failure later, like for instance when any methods are invoked on the array elements. For instance the following code will fail:

Integer i = intPairArr[0].getFirst(); // fails at runtime with ClassCastException

The method getFirst() is applied to the first element of the array and it returns a String instead of an Integer because the first element in the array intPairArr is – unexpectedly – a pair of strings.

In order to eliminate this unfortunate deficiency of Java Generics, which is a side effect of its translation by type erasure, it might make sense to disallow arrays of parameterized types in the first place.

Arrays of Type Variables

Generic Object Creation

The lack of exact type information and the erasure of type variables has a number of consequences. The severest is probably that no objects of the type represented by the type variable can be created. The following for instance is not permitted in Java Generics:

<T> void g() {

T ref = new T(); // error: T is not a class

}

The compiler rejects all attempts to use type variables in new expressions. However, creation of objects is often desired, like in the example below:

public final class Pair<A, B> {

public final A fst;

public final B snd;

public Pair() {

this.fst = new A(); // error

this.snd = new B(); // error

}

public Pair(A fst, B snd) {

this.fst = fst;

this.snd = snd;

}

In the default constructor we want to initialize the two fields with default constructed objects of their respective types, but this is not allowed. I order to understand why, imagine what this generic Pair class would be translated to, provided the compiler were willing to translate it:

public final class Pair<Object, Object> {

public final Object fst;

public final Object snd;

public Pair() {

this.fst = new Object(); // nonsense

this.snd = new Object(); // nonsense

}

public Pair(Object fst, Object snd) {

this.fst = fst;

this.snd = snd;

}

At runtime we could allocate default created objects of type Object, but that’s not what we want anyway, and for this reason the compiler radically forbids the occurrence of type variables in new expressions. This rule makes even more sense when the type variables have bounds, like in this case:

public final class Pair<A extends Cloneable, B extends Cloneable> {

…

}

The erasure would then look like:

public final class Pair {

public final Cloneable fst;

public final Cloneable snd;

public Pair() {

this.fst = new Cloneable(); // nonsense

this.snd = new Cloneable(); // nonsense

}

…

}

Clearly, interfaces cannot appear in new expressions so that this case can never work.

Generic Array Creation

Creation of arrays of unknown type has a problem similar to the one of creation of objects of an unknown type: the translation process maps the array to an array of the type variable’s erasure, which is its leftmost bound or Object, if no bound is specified. Here is an example:

<T> T[] makeArray() {

T[] ret = new T[0]; // warning: unchecked generic array creation

return ret;

}

The usual translation by type erasure would translate an array new expression to:

void Object[] makeArray() {

Object[] ret = new Object[0];

return ret;

}

An innocent assignment such as the following will compile, but fail at runtime:

String[] arr = makeArray();

Inside makeArray() an Object array is created, which is not assignable to a String array, and as a result a ClassCastException is raised at runtime.

Since this is an inevitable side effect of the translation by erasure, it might make sense to ban arrays of type variables from Java Generics.