Java Generics Tutorial - Part II - Subtyping

Part I - The Basics
Part II - Subtyping
Part III - Wildcards
Part IV - Bounded Type Variables

In Part I we quickly explored the basics of Java generics. In this blog post we will explore how generic types behave in the Java type system.

Subtypes

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 of Generic Types

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.

This means that the following code snippet is invalid:

List<Apple> apples = ...;

List<Fruit> fruits = apples;

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.

Is It Really a Problem?

It should not be. The strongest reason for a Java developer to be surprised is the inconsistency between the behavior of arrays and generic types. While the subtyping relations of the latter is invariant, the subtyping relation of the former is covariant: if a type A is a subtype of type B, then A[] is a subtype of B[]:

Apple[] apples = ...;
Fruit[] fruits = apples;

But wait! If we repeat the argument exposed in the previous section, we might end up adding strawberries to an array of apples:

Apple[] apples = new Apple[1];
Fruit[] fruits = apples;
fruits[0] = new Strawberry();

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.

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.

Next Steps

In the next post we will see how generic wildcards introduce both covariant and contravariant subtyping relations with generics.

Part I - The Basics
Part II - Subtyping
Part III - Wildcards
Part IV - Bounded Type Variables