Subtyping in Generics

Before starting on subtyping in Generics, let's first understand what is covariance.
See - What is covariance, contravariance and invariance?

In Java, as in other object-oriented typed languages, hierarchies of types can be built:

 

In Java, a subtype of a type T is either a type that extends T or a type that implements T (if T is an interface) directly or indirectly. Since "being subtype of" is a transitive relation, if a type A is a subtype of B and B is a subtype of C, then A will be a subtype of C too. In the figure above:

• FujiApple is a subtype of Apple.
• Apple is a subtype of Fruit.
• FujiApple is a subtype of Fruit.

Every Java type will also be subtype of Object.

Every subtype A of a type B may be assigned to a reference of type B:

Apple a = ...;

Fruit f = a;

Subtyping a generic types -  Invariance of Generic types

Parametrized types and Arrays

Subtyping of Generic Types - Parametrized Type Invariance

If a reference of an Apple instance can be assigned to a reference of a Fruit, as seen above, then what's the relation between, let's say, a List<Apple> and a List<Fruit>? Which one is a subtype of which? More generally, if a type A is a subtype of a type B, how does C<A> and C<B> relate themselves?

Surprisingly, the answer is: in no way. In more formal words, the subtyping relation between generic types is invariant.

Eg.

List<Apple> apples = new ArrayList<>();

List<Apple> foulApples = apples; //fine 

Collection<Apple> greenApples = apples; //fine again

However this is not fine:

List<Apple> apples = new ArrayList<>();

List<Fruit> fruits = apples;//Error

and so does the following:

List<Apple> apples;

List<Fruit> fruits = ...;

apples = fruits;

But why? Is an apple is a fruit, a box of apples (a list) is also a box of fruits.

In some sense, it is, but types (classes) encapsulate state and operations. What would happen if a box of apples was a box of fruits?

List<Apple> apples = ...;

List<Fruit> fruits = apples;

fruits.add(new Strawberry());

If it was, we could add other different subtypes of Fruit into the list and this must be forbidden.

The other way round is more intuitive: a box of fruits is not a box of apples, since it may be a box (List) of other kinds (subtypes) of fruits (Fruit), such as Strawberry.


So what if they were covariant?

Please go through the comments to see what is the problem:

List<Integer> li = new ArrayList<Integer>();
li.add(new Integer(122));
List<Object> lo = li; // Problem starts here
Object num = lo.get(0); // Nothing wrong with this
lo.add("Bang!"); // This would be OK through
// lo but what about li

Integer i = li.get(1); // ClassCastException

Parametrized types and Arrays : Covariance of Arrays

Array types are covariant,  if a type A is a subtype of type B, then A[] is a subtype of B[].

However we have just seen that the parameterised types are not covariant. This leads to an anomaly that cannot be resolved, so Java has the rule that arrays of parameterised types are not allowed. Otherwise we could write code that would potentially cause a ClassCastException, and the whole idea behind the generic types is to remove this possibility so long as no compiler warnings are issued.

Places where covariance of arrays may be harmful:
Case 1 : ArrayStoreException
Apple[] apples = new Apple[1];
Fruit[] fruits = apples;
fruits[0] = new Strawberry();//generates ArrayStoreException

The code indeed compiles, but the error will be raised at runtime as an ArrayStoreException. Because of this behavior of arrays, during a store operation, the Java runtime needs to check that the types are compatible. The check, obviously, also adds a performance penalty that you should be aware of.


Case 2: ClassCastException

List<String>[] wordlists = new ArrayList<String>[10];
ArrayList<Integer> ali = new ArrayList<Integer>();
ali.add( new Integer(123) );
Object[] objs = wordlists;
objs[0] = ali; // No ArrayStoreException
String s = wordlists[0].get(0); // ClassCastException

Once more, generics are safer to use and "correct" this type safety weakness of Java arrays.

In the case you're now wondering why the subtyping relation for arrays is covariant, I'll give you the answer that Java Generics and Collections give: if it was invariant, there would be no way of passing a reference to an array of objects of an unknown type (without copying every time to an Object[]) to a method such as:

void sort(Object[] o);

With the advent of generics, this characteristics of arrays is no longer necessary (as we'll see in the next part of this post) and should indeed by avoided.