Type dependency in Java, Part 1

Covariance and contravariance for array types, generic types, and the wildcard element

Page 2 of 2

Although generic types in Java are implicitly invariant, some variables can be used covariantly. These must be defined with a wildcard (?), which can be used as an actual type parameter. Generic<?> is the abstract supertype of all instantiations of the generic type, so all the instantiations of Generic are compatible to Generic<?>, as shown here:

Generic<?> wildcardReference; 
wildcardReference = new Generic<String>(); // implicitly compatible 
wildcardReference = new Generic<Integer>(); // implicitly compatible 

Because the wildcard type is abstract, it can be used only for references, and not for objects: new Generic<?>() would be rejected by the compiler.

An example for the usage of the wildcard is the parameter of a method manipulating a collection or an array, independently of its element type. Covariance makes it easy to write such a method for arrays:

static void swap(Object[] array, int i, int j) {
	... // swaps the elements with index i and j

The method can be called for an arbitrary array because every type is compatible to Object, and due to the covariance of array types:

Integer[] integerArray = {1, 2, 3};
swap(integerArray, 0, 2); // Integer[] is compatible to Object[]

The generic version of this method is more type safe because its calling does not use compatibility but generic instantiation, which can be checked by the compiler:

static <T> void swap(T[] array, int i, int j) { ... } 

Note that the two swap definitions may not occur together in the same class because they don't have a distinguishable signature.

Such a solution for ArrayList wouldn't work because of the rule of invariance for generic types. Because wildcard affects covariance, it can be used as a workaround:

static void swap(List<?> list, int i, int j) { ... } // similarly 

Calling the wildcard version is possible with an arbitrary element type:

List<Integer> list = ...;
swap(list, 0, 2); // List<Integer> is compatible to List<?>

We call such compatibility unspecified covariance, because we have not specified which type or supertype makes the covariance possible. It's possible for compatibility based on unspecified covariance to occur on two levels at once: the level of the generic types (ArrayList to List) and the level of the elements (Integer to ?):

ArrayList<Integer> arrayList = ... ; // ArrayList<T> implements List<T> 
swap(list, 0, 2); // ArrayList<Integer> is compatible to List<?> 

Explicit covariance for generic types

The light covariance shown in the previous section can be generalized. If Generic<SubType> were compatible to Generic<SuperType>, the types would be implicitly covariant. Binding the wildcard with extends would make the types explicitly covariant: Generic<SubType> is compatible to Generic<? extends SuperType>. We could declare a reference of this bounded wildcard type (but not of objects because all wildcard types are abstract):

Generic<? extends SuperType> covariantReference; 

This reference may refer any instance of Generic with an actual type parameter of a subtype of SuperType:

covariantReference = new Generic<SuperType>(); // normal 
covariantReference = new Generic<SubType>(); // covariant 
covariantReference = new Generic<Object>(); // type error: only subtypes work 

This means that the type Generic<? extends SuperType> is the abstract supertype of all instantiations of Generic with a subtype of SuperType (just like Generic<?> is the abstract supertype of all instantiations of Generic with any type, as explained above).

Using wildcards for binding is necessary in cases where certain properties are expected of the type parameter--for example if the elements of the parameter collection are to be manipulated:

static void increment(Number[] array) { ... } // for every element + 1
static void increment(Collection<? extends Number> collection) { ... }
	// similarly

The first method may be called with any Number[] parameter as a consequence of covariance between arrays:

increment(integerArray); // Integer[]  is compatible to Number[]

The second method may be called with any ArrayList parameter with a Number instantiation as a consequence of covariance with the wildcard:

increment(integerArrayList); // ArrayList<Integer> is compatible to Collection<? extends Number>

Note that in the above code snip, we're using compatibility on two levels again: the parametrized ArrayList<T> is a subtype of Collection<T> and Integer is a subtype of Number.

Covariant accessing variables of a type parameter

You've seen in the previous few examples how the bounded wildcard can be used for explicit covariance among generic types. While this covariance works on variables of the type parameter, it doesn't always work on method parameters in a generic class.

Assume that in the class Generic we use the type parameter T as the type of the (input and output) parameters of methods:

class Generic<T> {
	T data;
	void write(T data) { this.data = data; } // T is input parameter type
	T read() { return data; } } // T is output parameter type

In this case, the method write() cannot be called directly for a wildcardReference (it can be called only after type casting):

wildcardReference.write(new Object()); // type error
((Generic<Object>)wildcardReference).write(new Object()); // OK
	// however, warning by the compiler: unchecked cast

Because the wildcard is not a type, no type is compatible to it, not even Object. But the wildcard itself is compatible to Object (and to no other type); so the type parameter result of a function can be referred by an Object reference:

Object object = wildcardReference.read(); 

These rules apply for bounded wildcard types--note that input parameters cannot be passed directly; they can be passed only after casting. The output parameters can be assigned to a variable of the type (or a supertype) of the bound:

covariantReference.write(new SuperType()); // type error
covariantReference.write(new SubType()); // type error
((Generic<SuperType>)covariantReference).write(new SuperType()); // OK
((Generic<SuperType>)covariantReference).write(new SubType()); // OK
((Generic<SubType>)covariantReference).write(new SubType()); //OK
object = covariantReference.read(); // OK
SuperType superReference = covariantReference.read(); // OK
SubType subReference1 = covariantReference.read(); // type error
SubType subReference2 = ((Generic<SubType>)covariantReference).read(); // OK
SubType subReference3 = (SubType)covariantReference.read(); // unsafe

The type conversions in the last two program lines can throw a ClassCastException (as always), hence they are unsafe. Whether it happens or not depends on the type of the object in the last write(): if it is new SubType() (as in the sequence above), no exception will be thrown. The difference between the last two lines is that in the first one the reference is being converted (from Generic<? extends SuperType> to Generic<SubType>) and then read() is called, while in the second one the result of read() will be converted (from ? to SubType), so the first one is (somewhat) safer.

We can interpret this to mean that an unbounded wildcard is bounded by Object: Generic<?> has (almost) the same effect as Generic<? extends Object>. Thus, we can say that the unspecified covariance is an explicit covariance through the compatibility to Object.

These rules are valid not only for parameters but for every reading or writing access to variables of the type of the type parameter (assuming they are public or otherwise accessible). No type is compatible to ? but ? is compatible to the upper bound (as the case may be, to Object--but then to no other type):

wildcardReference.data = new Object(); // writing access -> type error
object = wildcardReference.data; // reading access is OK
wildcardReference.write(new Object()); // writing access -> type error
object = wildcardReference.read(); // reading access is OK
String string = wildcardReference.data; // error: ? is compatible only to Object
Generic<? extends String> covariant = new Generic<String>();
String s = covariant.data; // reading is possible with upper bound

Contravariance for parametrized types

Recall that contravariance means downwards compatibility. Arrays are explicitly contravariant; syntactically this can be expressed through type conversion (via casting, see above):

subArray = (SubType[])superArray; // explicit compatible (contravariant) 

Among different instantiations of a generic type, the compiler rejects type conversion. But generic types are explicitly contravariant, too. Syntactically this can be expressed through a lower bound of the wildcard with super:

Generic<? super SubType> contravariantReference; 

This variable can refer any instantiation of Generic with any supertype (e.g., an Object) of SubType:

contravariantReference = new Generic<SubType>(); // normal 
contravariantReference = new Generic<SuperType>(); // contravariant 
contravariantReference = new Generic<Object>(); // always possible 

Here, the assignment of the SuperType instantiation takes place downwards, namely to the SubType instantiation contravariantReference--this means contravariance.

The upper bound changes the behavior for reading and writing (as discussed in the previous section), so the contravariance with Object makes both possible:

Generic<? super Object> contravariantO = new Generic<Object>(); // like above
contravariantO.data = new Object(); // now is OK: writing is possible
object = contravariantO.data; // also reading
contravariantO.write(new Object()); // now is OK
object = contravariantO.read(); // ? is compatible to Object

The contravariance (? super) with other types (like String) reverses the direction for reading and writing compared with covariance (? extends):

Generic<? super String> contravariantS = new Generic<String>();
contravariantS.data = new String(); // OK
string = contravariantS.data; // type error: contrary to covariant case
contravariantS.write(new String()); // OK
string = contravariantS.read(); // type error

The reason is that the lower bound (here String) is compatible to the wildcard but not vice versa. This is the difference between contravariantO.read() (OK) and contravariantS.read() (error): ? is compatible to Object but not to String.

Conclusion to Part 1

Java types may be implicitly or explicitly compatible to each other. Implicit compatibility is asserted by the compiler, whereas explicit compatibility must be asserted by the programmer, in order to avoid exceptions at runtime. Dependent (array and generic) types may also be compatible: upward compatibility (called covariance) is mostly implicit, while downward compatibility (contravariance) is explicit for array types.

Java doesn't allow implicit variance for generic types, because doing so would threaten type safety. The wildcard is a compromise, allowing (implicit) unspecified covariance. Covariance and contravariance for generic types can only be explicit: the developer must define the upper and lower limits, as shown in Table 1.

If you've ever wondered about the many question marks (wildcards) and boxed genericity found in more recent versions of the Java standard libraries, Part 2 of this article should help. We'll look at contravariance in several API examples, and I'll also explain why the compiler sometimes rejects accessing variables of a generic type. You'll learn how to create objects of a generic type, as well as how the idea of variance can be transferred to method declarations, definitions, and calls. We'll conclude with a quick look into compatibility and variance in lambdas--including generic lambda expressions, which could be of interest to programming language enthusiasts.

| 1 2 Page 2