Saturday 7 July 2012

Item 25: Prefer lists to arrays


Arrays differ from generic types in two important ways. First, arrays are covariant. This scary-sounding word means simply that if Sub is a subtype of Super, then the array type Sub[] is a subtype of Super[]. Generics, by contrast, are invariant: for any two distinct types Type1 and Type2, List<Type1> is neither a subtype nor a supertype of List<Type2>.

This code fragment is legal:

// Fails at runtime!
Object[] objectArray = new Long[1];
objectArray[0] = "I don't fit in"; // Throws ArrayStoreException

but this one is not:

// Won't compile!
List<Object> ol = new ArrayList<Long>(); // Incompatible types
ol.add("I don't fit in");

The second major difference between arrays and generics is that arrays are reified [JLS, 4.7]. This means that arrays know and enforce their element types at runtime. As noted above, if you try to store a String into an array of Long, you’ll get an ArrayStoreException. Generics, by contrast, are implemented by erasure [JLS, 4.6]. This means that they enforce their type constraints only at compile time and discard (or erase) their element type information at runtime.

Because of these fundamental differences, arrays and generics do not mix well. For example, it is illegal to create an array of a generic type, a parameterized type, or a type parameter. None of these array creation expressions are legal: new List<E>[], new List<String>[], new E[]. All will result in generic array creation errors at compile time. Because it isn’t typesafe.

To make this more concrete, consider the following code fragment:

// Why generic array creation is illegal - won't compile!
List<String>[] stringLists = new List<String>[1]; // (1)
List<Integer> intList = Arrays.asList(42); // (2)
Object[] objects = stringLists; // (3)
objects[0] = intList; // (4)
String s = stringLists[0].get(0); // (5)

Let’s pretend that line 1, which creates a generic array, is legal. Line 2 creates and initializes a List<Integer> containing a single element. Line 3 stores the List<String> array into an Object array variable, which is legal because arrays are covariant. Line 4 stores the List<Integer> into the sole element of the Object array, which succeeds because generics are implemented by erasure: the
runtime type of a List<Integer> instance is simply List, and the runtime type of a List<String>[] instance is List[], so this assignment doesn’t generate an ArrayStoreException. Now we’re in trouble. We’ve stored a List<Integer> instance into an array that is declared to hold only List<String> instances. In line 5, we retrieve the sole element from the sole list in this array. The compiler
automatically casts the retrieved element to String, but it’s an Integer, so we get a ClassCastException at runtime. In order to prevent this from happening, line 1 (which creates a generic array) generates a compile-time error.

When you get a generic array creation error, the best solution is often to use the collection type List<E> in preference to the array type E[]. You might sacrifice some performance or conciseness, but in exchange you get better type safety and interoperability.

For example, suppose you have a synchronized list (of the sort returned by Collections.synchronizedList) and a function that takes two values of the type held by the list and returns a third. Now suppose you want to write a method to “reduce” the list by applying the function across it.

Here’s how the code might have looked without generics:

// Reduction without generics, and with concurrency flaw!
static Object reduce(List list, Function f, Object initVal) {
synchronized(list) {
Object result = initVal;
for (Object o : list)
result = f.apply(result, o);
return result;
}
}
interface Function {
Object apply(Object arg1, Object arg2);
}

So, you modify the reduce method to copy the contents of the list while holding the lock, which allows you to perform the reduction on the copy. Prior to release 1.5, the natural way to do this would have been using List’s toArray method (which locks the list internally):

// Reduction without generics or concurrency flaw
static Object reduce(List list, Function f, Object initVal) {
Object[] snapshot = list.toArray(); // Locks list internally
Object result = initVal;
for (Object o : list)
result = f.apply(result, o);
return result;
}

If you try to do this with generics you’ll get into trouble of the sort that we discussed above. Here’s a generic version of the Function interface:

interface Function<T> {
T apply(T arg1, T arg2);
}

And here’s a naive attempt to apply generics to the revised version of the reduce method. This is a generic method (Item 27). Don’t worry if you don’t understand the declaration. For the purposes of this item, you should concentrate on the method body:

// Naive generic version of reduction - won't compile!
static <E> E reduce(List<E> list, Function<E> f, E initVal) {
E[] snapshot = list.toArray(); // Locks list
E result = initVal;
for (E e : snapshot)
result = f.apply(result, e);
return result;
}

If you try to compile this method, you’ll get the following error:

Reduce.java:12: incompatible types
found : Object[], required: E[]
E[] snapshot = list.toArray(); // Locks list
^

No big deal, you say, I’ll cast the Object array to an E array:

E[] snapshot = (E[]) list.toArray();

That gets rid of the error, but now you get a warning:

Reduce.java:12: warning: [unchecked] unchecked cast
found : Object[], required: E[]
E[] snapshot = (E[]) list.toArray(); // Locks list
^

The compiler is telling you that it can’t check the safety of the cast at runtime because it doesn’t know what E is at runtime—remember, element type information is erased from generics at runtime. Will this program work? Yes, it turns out that it will, but it isn’t safe. With minor modifications, you could get it to throw a ClassCastException on a line that doesn’t contain an explicit cast. The compiletime type of snapshot is E[] which could be String[], Integer[], or any other
kind of array. The runtime type is Object[], and that’s dangerous. Casts to arrays of non-reifiable types should be used only under special circumstances (Item 26). So what should you do? Use a list instead of an array. Here is a version of the reduce method that compiles without error or warning:

// List-based generic reduction
static <E> E reduce(List<E> list, Function<E> f, E initVal) {
List<E> snapshot;
synchronized(list) {
snapshot = new ArrayList<E>(list);
}
E result = initVal;
for (E e : snapshot)
result = f.apply(result, e);
return result;
}

This version is a tad more verbose than the array version, but it’s worth it for the peace of mind that comes from knowing you won’t get a ClassCastException at runtime.

In summary, arrays and generics have very different type rules. Arrays are covariant and reified; generics are invariant and erased. As a consequence, arrays provide runtime type safety but not compile-time type safety and vice versa for generics. Generally speaking, arrays and generics don’t mix well. If you find yourself mixing them and getting compile-time errors or warnings, your first impulse should be to replace the arrays with lists.


Reference: Effective Java 2nd Edition by Joshua Bloch