Type dependency in Java, Part 2

Using covariance and contravariance in your Java programs

Type dependency in Java Part 2
Credit: chrstphré cæmpbëll

Understanding type compatibility is fundamental to writing good Java programs, but the interplay of variances between Java language elements can seem highly academic to the uninitiated. This two-part article is for software developers ready to tackle the challenge! Part 1 revealed the covariant and contravariant relationships between simpler elements such as array types and generic types, as well as the special Java language element, the wildcard. Part 2 explores type dependency in the Java Collections API, in generics, and in lambda expressions.

We'll jump right in, so if you haven't already read Part 1, I recommend starting there.

API examples for contravariance

For our first example, consider the Comparator version of java.util.Collections.sort(), from the Java Collections API. This method's signature is:

<T> void sort(List<T> list, Comparator<? super T> c)

The sort() method sorts any List. Usually it's easier to use the overloaded version, with the signature:

sort(List<T extends Comparable<? super T>>)

In this case, extends Comparable expresses that the sort() may be called only if the necessary method-comparing elements (namely compareTo) have been defined in the element type (or in its supertype, thanks to ? super T):

sort(integerList); // Integer implements Comparable 
sort(customerList); // works only if Customer implements Comparable

Using generics for comparison

Obviously, a list is sortable only if its elements can be compared among each other. Comparison is done by the single method compareTo, which belongs to the interface Comparable. You must implement compareTo in the element class.

This type of element can be sorted just one way, however. For example, you may sort a Customer by their ID, but not by birthday or postal code. Using the Comparator version of sort() is more flexible:

publicstatic <T> void sort(List<T> list, Comparator<? super T> c)

Now we compare elements not in the element's class, but in an additional Comparator object. This generic interface has one object method:

int compare(T o1, T o2);

Contravariant parameters

Instantiating an object more than once enables you to sort objects using different criteria. But do we really need such a complicated Comparator<? super T> type parameter? In most cases, Comparator<T> would be enough. We could use its compare() method to compare any two elements in the List<T> object, as follows:

class DateComparator implements Comparator<java.util.Date> {
	public int compare(Date d1, Date d2) { return ... }
		// compares the two Date objects
List<java.util.Date> dateList = ... ; // List of Date objects
sort(dateList, new DateComparator()); // sorts dateList

Using the more complicated version of the method Collection.sort() set us up for additional use cases, however. The contravariant type parameter of Comparable makes it possible to sort a list of type List<java.sql.Date>, because java.util.Date is a supertype of java.sql.Date:

List<java.sql.Date> sqlList = ... ;
sort(sqlList, new DateComparator());

If we omit contravariance in the sort() signature (using only <T> or the unspecified, unsafe <?>), then the compiler rejects the last line as type error.

In order to call

sort(sqlList, new SqlDateComparator());

you would have to write an extra featureless class:

class SqlDateComparator extends DateComparator {}

Additional methods

Collections.sort() isn't the only Java Collections API method equipped with a contravariant parameter. Methods like addAll(), binarySearch(), copy(), fill(), and so on, can be used with similar flexibility.

Collections methods like max() and min() offer contravariant result types:

public static <T extends Object & Comparable<? super T>> T max(
	Collection<? extends T> collection) { ... }

As you see here, a type parameter can be requested to satisfy more than one condition, just by using &. The extends Object might appear superfluous, but it stipulates that max() returns a result of type Object and not of row Comparable in the bytecode. (There are no type parameters in bytecode.)

The overloaded version of max() with Comparator is even funnier:

public static <T> T max(Collection<? extends T> collection,
	Comparator<? super T> comp)

This max() has both contravariant and covariant type parameters. While the elements of the Collection must be of (possibly different) subtypes of a certain (not explicitly given) type, Comparator must be instantiated for a supertype of the same type. Much is required of the compiler's inference algorithm, in order to differentiate this in-between type from a call like this one:

Collection<AType> collection = ... ; 
Comparator<AnOtherType> comparator = ... ; 
max(collection, comparator);

Boxed binding of type parameters

As our last example of type dependency and variance in the Java Collections API, let's reconsider the signature of the sort() with Comparable. Note that it uses both extends and super, which are boxed:

static <T extends Comparable<? super T>> void sort(List<T> list) { ... }

In this case, we're not as interested in the compatibility of references as we are in binding the instantiation. This instance of the sort() method sorts a list object with elements of a class implementing Comparable. In most cases, sorting would work without <? super T> in the method's signature:

sort(dateList); // java.util.Date implements Comparable<java.util.Date> 
sort(sqlList); // java.sql.Date implements Comparable<java.sql.Date> 

The lower bound of the type parameter allows additional flexibility, however. Comparable doesn't necessarily need to be implemented in the element class; it's enough to have implemented it in the superclass. For example:

class SuperClass implements Comparable<SuperClass> {
		public int compareTo(SuperClass s) { ... } }
	class SubClass extends SuperClass {} // without overloading of compareTo()
	List<SuperClass> superList = ...;
	List<SubClass> subList = ...;

The compiler accepts the last line with

static <T extends Comparable<? super T>> void sort(List<T> list) { ... }

and rejects it with

static <T extends Comparable<T>> void sort(List<T> list) { ... }

The reason for this rejection is that the type SubClass (which the compiler would determine from the type List<SubClass> in the parameter subList) is not suitable as a type parameter for T extends Comparable<T>. The type SubClass doesn't implement Comparable<SubClass>; it only implements Comparable<SuperClass>. The two elements are not compatible due to the lack of implicit covariance, although SubClass is compatible to SuperClass.

On the other hand, if we use <? super T>, the compiler doesn't expect SubClass to implement Comparable; it's enough if SuperClass does it. It's enough because the method compareTo() is inherited from SuperClass and can be called for SubClass objects: <? super T> expresses this, effecting contravariance.

Contravariant accessing variables of a type parameter

The upper or the lower bound applies only to type parameter of instantiations referred by a covariant or contravariant reference. In the case of Generic<? extends SuperType> covariantReference; and Generic<? super SubType> contravariantReference;, we can create and refer objects of different Generic instantiations.

Different rules are valid for the parameter and result type of a method (such as for input and output parameter types of a generic type). An arbitrary object compatible to SubType can be passed as parameter of the method write(), as defined above.

contravariantReference.write(new SubType()); // OK
contravariantReference.write(new SubSubType()); // OK too
contravariantReference.write(new SuperType()); // type error
((Generic<? super SuperType>)contravariantReference).write(
	new SuperType()); // OK

Because of contravariance, it's possible to pass a parameter to write(). This is in contrast to the covariant (also unbounded) wildcard type.

The situation doesn't change for the result type by binding: read() still delivers a result of type ?, compatible only to Object:

Object o = contravariantReference.read();
SubType st = contravariantReference.read(); // type error

The last line produces an error, even though we've declared a contravariantReference of type Generic<? super SubType>.

The result type is compatible to another type only after the reference type has been explicitly converted:

SuperSuperType sst = ((Generic<SuperSuperType>)contravariantReference).read();
sst = (SuperSuperType)contravariantReference.read(); // unsafer alternative

Examples in the previous listings show that reading or writing access to a variable of type parameter behaves the same way, regardless of whether it happens over a method (read and write) or directly (data in the examples).

Reading and writing to variables of type parameter

Table 1 shows that reading into an Object variable is always possible, because every class and the wildcard are compatible to Object. Writing an Object is possible only over a contravariant reference after appropriate casting, because Object is not compatible to the wildcard. Reading without casting into an unfitting variable is possible with a covariant reference. Writing is possible with a contravariant reference.

Table1. Reading and writing access to variables of type parameter

reading (input) readObject writeObject read supertype write supertype read subtype write subtype
Wildcard? OK Error Cast Cast Cast Cast
Covariant?extends OK error OK Cast Cast Cast
Contravariant?super OK Cast Cast Cast Cast OK

The rows in Table 1 refer to the sort of reference, and the columns to the type of data to be accessed. The headings of "supertype" and "subtype" indicate the wildcard bounds. The entry "cast" means the reference must be casted. An instance of "OK" in the last four columns refers to the typical cases for covariance and contravariance.

See the end of this article for a systematic test program for the table, with detailed explanations.

Creating objects

On the one hand, you cannot create objects of the wildcard type, because they are abstract. On the other hand, you can create array objects only of an unbounded wildcard type. You cannot create objects of other generic instantiations, however.

Generic<Object>[] genericArray = new Generic<Object>[20]; // type error
Generic<?>[] wildcardArray = new Generic<?>[20]; // OK
genericArray = (Generic<Object>[])wildcardArray; // unchecked conversion
genericArray[0] = new Generic<Object>();
genericArray[0] = new Generic<String>(); // type error
wildcardArray[0] = new Generic<String>(); // OK

Because of the covariance of arrays, the wildcard array type Generic<?>[] is the supertype of the array type of all instantiations; therefore the assignment in the last line of the above code is possible.

Within a generic class, we cannot create objects of the type parameter. For example, in the constructor of an ArrayList implementation, the array object must be of type Object[] upon creation. We can then convert it to the array type of the type parameter:

class MyArrayList<E> implements List<E> {
	private final E[] content;
	MyArrayList(int size) {
		content = new E[size]; // type error
		content = (E[])new Object[size]; // workaround

For a safer workaround, pass the Class value of the actual type parameter to the constructor:

content = (E[])java.lang.reflect.Array.newInstance(myClass, size);

Multiple type parameters

A generic type can have more than one type parameter. Type parameters don't change the behavior of covariance and contravariance, and multiple type parameters can occur together, as shown below:

class G<T1, T2> {}
G<? extends SuperType, ? super SubType> reference;
reference = new G<SuperType, SubType>(); // without variance
reference = new G<SubType, SuperType>(); // with co- and contravariance

The generic interface java.util.Map<K, V> is frequently used as an example for multiple type parameters. The interface has two type parameters, one for key and one for value. It's useful to associate objects with keys, for example so that we can more easily find them. A telephone book is an example of a Map object using multiple type parameters: the subscriber's name is the key, the phone number is the value.

The interface's implementation java.util.HashMap has a constructor for converting an arbitrary Map object into an association table:

public HashMap(Map<? extends K,? extends V> m) ...

Because of covariance, the type parameter of the parameter object in this case does not have to correspond with the exact type parameter classes K and V. Instead, it can be adapted through covariance:

Map<CustomerNumber, Customer> customers;
contacts = new HashMap<Id, Person>(customers); // covariant

Here, Id is a supertype of CustomerNumber, and Person is supertype of Customer.

Variance of methods

We've talked about variance of types; now let's turn to a somewhat easier topic.

1 2 3 Page 1