Java generics: variance with wildcard type arguments

Marcio Endo

July 25, 2022

I have recently answered a question posted in the Twitter Java community. It asked why the following code does not compile:

ArrayList<Integer> list1 = new ArrayList<>();
List<Integer> list2 = list1;

ArrayList<ArrayList<Integer>> temp1 = new ArrayList<>();
List<List<Integer>> temp2 = temp1; // does not compile

In this blog post I will try to give a more detailed answer. I will also expand on it by iterating on the original code.

In doing so we will touch on a few Java type-related topics. In particular we will see how to obtain type variance using wildcards.

So let's begin.

In Java, type parameters are invariant

At first, it makes sense to wonder why the example does not compile. After all, if the following is valid:

List<Integer> list = new ArrayList<Integer>();

Why the following is not?

// does not compile!
List<List<Integer>> list = new ArrayList<ArrayList<Integer>>();

In the original example, let's imagine the temp2 variable declaration did not raise an error. It would allow us to write the following code:

ArrayList<ArrayList<Integer>> temp1 = new ArrayList<>();
List<List<Integer>> temp2 = temp1; // assume no error
temp2.add(new LinkedList<>());
ArrayList<Integer>> firstItem = temp1.get(0);

The last line would cause a ClassCastException at runtime. The first (and only) item in the list is not an ArrayList; it is a LinkedList.

We can actually produce an example that can be compiled and experience the exception at runtime. It uses raw types:

public class Listing01 {
  @SuppressWarnings({"unchecked", "rawtypes"})
  public static void main(String[] args) {
    var temp1 = new ArrayList<ArrayList<Integer>>();
    temp1.add(new ArrayList<>());

    List temp2 = temp1;

    temp2.add(new LinkedList<>());

    var arrayList0 = temp1.get(0);
    System.out.println(arrayList0);

    var arrayList1 = temp1.get(1);
    System.out.println(arrayList1);
  }
}

Running this program produces the following output:

[1, 2, 3]
Exception in thread "main" java.lang.ClassCastException: class java.util.LinkedList cannot be cast to class java.util.ArrayList (java.util.LinkedList and java.util.ArrayList are in module java.base of loader 'bootstrap')
        at post.Listing01.main(Listing01.java:34)

So this is the reason the compiler refuses to compile the original example.

More formally, Java type parameters are invariant. In other words, a List<Integer> is not a valid substitute for List<Number>. More specifically, List<Integer> is not a subtype of List<Number>.

But the language provides type variance through wildcard type arguments.

So let's expand on the original example.

An example that can be compiled

As a first step, let's make the original example compile. The easiest way is just to declare the type of second variable as the same of the first one:

public class Listing02 {
  @SuppressWarnings("unused")
  public static void main(String[] args) {
    ArrayList<ArrayList<Integer>> temp1 = new ArrayList<>();
    ArrayList<ArrayList<Integer>> temp2 = temp1;
  }
}

OK, the example now compiles.

A more idiomatic example

Our example, as it is, does not use common Java idioms. In other words, we wouldn't declare the temp2 variable. We would use the temp1 variable directly instead.

Let's make it more idiomatic by extracting the second statement into a method:

public class Listing03 {
  public static void main(String[] args) {
    ArrayList<ArrayList<Integer>> temp1 = new ArrayList<>();

    consume(temp1);
  }

  private static void consume(ArrayList<ArrayList<Integer>> temp2) {

  }
}

I believe this make the example more idiomatic.

Actually using our list

Apart from creating an array list, our program is not doing anything. Let's fix that:

public class Listing04 {
  public static void main(String[] args) {
    var temp1 = new ArrayList<ArrayList<Integer>>();

    // 1
    temp1.add(New.arrayList(1, 2, 3));
    temp1.add(New.arrayList(4, 5, 6));
    temp1.add(New.arrayList(7, 8, 9));

    consume(temp1);
  }

  // 2
  private static void consume(ArrayList<ArrayList<Integer>> temp2) {
    for (var value : temp2) {
      printOne(value);
    }

    System.out.println();
  }

  // 3
  private static void printOne(ArrayList<Integer> list) {
    for (var value : list) {
      int intValue = value.intValue();

      printOneInt(intValue);
    }
  }

  // 4
  private static void printOneInt(int value) {
    System.out.print(value);
    System.out.print(" ");
  }
}

Yes, I know, the line count exploded. But please bear with me.

The example now adds three new array lists to our temp1. Each list contains three distinct integer values. Next, it iterates through the lists and prints the each of the values individually.

Running this example produces the following output:

1 2 3 4 5 6 7 8 9

But this version only works with array lists of integers. Can we make our example more generic? In other words, can we make it work with other types of lists and/or numbers?

`consume` method: accepting more types

Our consume method currently accepts only ArrayList of ArrayList:

void consume(ArrayList<ArrayList<Integer>> temp2)

Can we make it more generic? For example, can we make it to accept List of List instead:

void consume(List<List<Integer>> temp2)

If you recall, that was the original question in the tweet. So let's try this initial refactoring:

private static void consume(List<List<Integer>> temp2) {
  for (var value : temp2) {
    printOne(value);
  }

  System.out.println();
}

Just like the original question, it does not compile:

$ javac src/main/java/post/Listing05.java src/main/java/post/New.java
src/main/java/post/Listing05.java:29: error: incompatible types: ArrayList<ArrayList<Integer>> cannot be converted to List<List<Integer>>
    consume(temp1);
            ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

So how can we fix this?

Enter upper bounded wildcards. Let's try the following:

private static void consume(List<? extends List<Integer>> temp2) {
  for (var value : temp2) {
    printOne(value);
  }

  System.out.println();
}

It compiles! But why? And what exactly is a wildcard type?

These are all valid questions but, for now, let's just keep investigating.

`consume` method: accepting even more types

Could our previous refactoring work with type argument of the innermost list? In other words, could we change our method signature from:

void consume(List<? extends List<Integer>> temp2)

To something like:

private static void consume(List<? extends List<? extends Number>> temp2) {
  for (var value : temp2) {
    printOne(value);
  }

  System.out.println();
}

// 1
private static void printOne(List<? extends Number> one) {
  for (var value : one) {
    int intValue = value.intValue();

    printOneInt(intValue);
  }
}

Notice the "type-widening" tweak in the printOne method:

the type of the one parameter changed from List<Integer> to List<? extends Number>

It compiles. Great!

`consume` method: accepting even more types (again)

In the consume method, the only thing we do with the List instance is to iterate over it using an enhanced for loop. In other words, we are not using any method that is specific to the List interface. Our temp2 parameter can be a simple Iterable.

Let's change our consume method:

private static void consume(
    Iterable<? extends Iterable<? extends Number>> temp2) {
  for (var value : temp2) {
    printOne(value);
  }

  System.out.println();
}

private static void printOne(Iterable<? extends Number> one) {
  for (var value : one) {
    int intValue = value.intValue();

    printOneInt(intValue);
  }
}

We have also changed the printOne method signature accordingly.

Good. Let's now try to remove the New class.

Removing the `New` class

So far we have been relying on a utility class called New. It creates a new ArrayList instance filled with the supplied integer values in order.

We could, instead, create an add method like the following:

private static void add(
    ArrayList<ArrayList<Integer>> temp1,
    Supplier<ArrayList<Integer>> factory,
    Integer... values) {
  var list = factory.get();

  for (var value : values) {
    list.add(value);
  }

  temp1.add(list);
}

And we invoke it in our main method like so:

public static void main(String[] args) {
  var temp1 = new ArrayList<ArrayList<Integer>>();

  add(temp1, ArrayList::new, 1, 2, 3);
  add(temp1, ArrayList::new, 4, 5, 6);
  add(temp1, ArrayList::new, 7, 8, 9);

  consume(temp1);
}

That's great. Let's now try and make the add method generic.

`add` method: accept more types

From our experience with the consume method, we could first try to change the add signature from:

void add(ArrayList<ArrayList<Integer>> temp1,
         Supplier<ArrayList<Integer>> factory,
         Integer... values)

To:

private static void add(
    List<? extends List<Integer>> temp1,
    Supplier<? extends List<Integer>> factory,
    Integer... values) {
  var list = factory.get();

  for (var value : values) {
    list.add(value);
  }

  temp1.add(list);
}

Notice the change in the declared types of both the temp1 and the factory parameters.

But this version of the `add' method does not compile. There is a compilation error at the last statement:

$ javac src/main/java/post/Listing08.java
src/main/java/post/Listing08.java:45: error: incompatible types: List<Integer> cannot be converted to CAP#1
    temp1.add(list);
              ^
  where CAP#1 is a fresh type-variable:
    CAP#1 extends List<Integer> from capture of ? extends List<Integer>
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

AWhat if we reversed the wildcard of the temp1 variable. In other words, what if used a lower bounded wildcard instead?

Let's change add method signature to the following:

void add(List<? super List<Integer>> temp1,
         Supplier<? extends List<Integer>> factory,
         Integer... values)

The add method now compiles. But the main method does not:

$ javac src/main/java/post/Listing08.java
src/main/java/post/Listing08.java:26: error: incompatible types: ArrayList<ArrayList<Integer>> cannot be converted to List<? super List<Integer>>
    add(temp1, ArrayList::new, 1, 2, 3);
        ^
src/main/java/post/Listing08.java:27: error: incompatible types: ArrayList<ArrayList<Integer>> cannot be converted to List<? super List<Integer>>
    add(temp1, ArrayList::new, 4, 5, 6);
        ^
src/main/java/post/Listing08.java:28: error: incompatible types: ArrayList<ArrayList<Integer>> cannot be converted to List<? super List<Integer>>
    add(temp1, ArrayList::new, 4, 5, 6);
        ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
3 errors

A solution is to parameterize the add method itself. Like so:

private static <LIST extends List<Integer>> void add(
    List<? super LIST> temp1, Supplier<LIST> factory, Integer... values) {
  var list = factory.get();

  for (var value : values) {
    list.add(value);
  }

  temp1.add(list);
}

This version compiles and runs without an issue.

OK, let's now make the add method a little more generic.

`add` method: accepting even more types

Like we did with the consume method, let's allow other number types, not only integers. To do it we need to add an additional type parameter to our add method:

@SafeVarargs
private static <LIST extends List<E>, E extends Number> void add(
    List<? super LIST> temp1, Supplier<LIST> factory, E... values) {
  var list = factory.get();

  for (var value : values) {
    list.add(value);
  }

  temp1.add(list);
}

We also had to add the @SafeVarargs annotation to make the compiler happy. What it means is beyond the scope of this post. It is enough to say that, since all we do with the values array is to iterate over its components, we can annotate the method with @SafeVarargs.

This version also compiles and runs.

`add` method: accepting even more types (again)

In our add method the only thing we do with the LIST type is to invoke its add method. The add method is defined by the Collection interface. Therefore the LIST type parameter could refer to a Collection instead.

Let's modify our add method:

@SafeVarargs
static <COLL extends Collection<E>, E extends Number> void add(
    Collection<? super COLL> temp1, Supplier<COLL> factory, E... values) {
  COLL coll = factory.get();

  for (var value : values) {
    coll.add(value);
  }

  temp1.add(coll);
}

Notice the changes:

the LIST type parameter was renamed to COLL;
the upper bound of the former was changed from List<E> to Collection<E>;
the type of the temp1 method parameter was changed from List to Collection.

This version compiles and runs. It produces the same output as before.

All right.

Putting it all together

So now we can change our main method so we can properly test our "generified" example as a whole:

public static void main(String[] args) {
  var temp1 = new LinkedHashSet<Iterable<Number>>();

  add(temp1, ArrayList::new, 1, 2D, 3L);
  add(temp1, LinkedList::new, (byte) 4, (short) 5, 6D);
  add(temp1, LinkedHashSet::new, 7D, 8F, 7D, 9F, 9F);

  consume(temp1);
}

Notice that:

the type of temp1 variable was changed from ArrayList<ArrayList<Integer>> to LinkedHashSet<Iterable<Number>>;
the factories supplied to add method are of three different Collection implementations;
the number values supplied are of different types.

This version compiles and runs. It produces the same output:

1 2 3 4 5 6 7 8 9

That's great! Let's see what is happening.

Covariance: our `consume` method

Let's take a closer look at our consume method. Remember its signature:

void consume(Iterable<? extends Iterable<? extends Number>> temp2)

All of the following invocations are valid:

consume(new ArrayList<ArrayList<Integer>>());
consume(new ArrayList<List<Integer>>());
consume(new HashSet<Collection<Double>>());
consume(new LinkedHashSet<Iterable<Number>>());
consume(new HashSet<Set<Number>>());

In other words, all of the following variable assignments valid:

Iterable<? extends Iterable<? extends Number>> a
    = new ArrayList<ArrayList<Integer>>();

Iterable<? extends Iterable<? extends Number>> b
    = new ArrayList<List<Integer>>();

Iterable<? extends Iterable<? extends Number>> c
    = new HashSet<Collection<Double>>();

Iterable<? extends Iterable<? extends Number>> d
    = new LinkedHashSet<Iterable<Number>>();

Iterable<? extends Iterable<? extends Number>> e
    = new HashSet<Set<Number>>();

If the previous assignments are all valid then the following are also valid:

a = b = c = d = e;
e = d = c = b = a;

What I am trying to say is that the type:

Iterable<? extends Iterable<? extends Number>>

Is a common "supertype" for all of the following types;

ArrayList<ArrayList<Integer>>
ArrayList<List<Integer>>
HashSet<Collection<Double>>
LinkedHashSet<Iterable<Number>>
HashSet<Set<Number>>

But there's a caveat...

The covariance caveat

The caveat is that on a reference parameterized with a upper bounded wildcard you can only invoke methods that, at most, returns the wildcard. More specifically, it cannot invoke any method that takes a parameterized argument.

Suppose our consume method was defined like:

void consume(List<? extends Number> temp2);

Then the following example would be valid and compile:

void consume(List<? extends Number> temp2) {
  // only 'read' the type variable: OK
  Number number = temp2.get(0);
  Iterator<? extends Number> iterator = temp2.iterator();
  Number next = iterator.next();

  // takes an non-parameterized argument: OK
  Number removed = temp2.remove(0);

  // non-parameterized method: also OK
  int size = temp2.size();
}

However, the following is not valid and fails to compile:

static void invalid(List<? extends Number> temp2) {
  // tries to 'write' to the type variable: not OK
  temp2.add(1D);
  temp2.set(0, 123L);
  temp2.addAll(List.of(1, 2, 3));
}

So while the upper bounded wildcard allows for our method to accept references of more distinct types, it comes with the cost of disallowing "write" operations on it.

Contravariance: our `add` method

Let's analyze our add method signature:

<COLL extends Collection<E>, E extends Number> void add(
    Collection<? super COLL> temp1, Supplier<COLL> factory, E... values)

All of the following variations are valid:

var temp1 = new ArrayList<ArrayList<Integer>>();
add(temp1, ArrayList::new, 1, 2, 3);

var temp1 = new ArrayList<List<Integer>>();
add(temp1, ArrayList::new, 1, 2, 3);

var temp1 = new HashSet<Set<Number>>();
add(temp1, HashSet::new, 1, 2, 2, 3, 3);

var temp1 = new HashSet<Collection<Double>>();
add(temp1, HashSet::new, 1D, 2D, 2D, 3D, 3D);

Notice that the COLL type is inferred from the factory argument. In other words, the factory type defines the allowed types for the temp1 argument.

Perhaps more interestingly the following is also valid:

var temp1 = new LinkedHashSet<Iterable<Number>>();
add(temp1, ArrayList::new, 1, 2D, 3L);

In this example, COLL is inferred to be ArrayList<Number>. Therefore, in this particular invocation, the signature could be viewed as:

void add(Collection<? super ArrayList<Number>> temp1,
         Supplier<ArrayList<Number>> factory,
         Number... values)

In other words, the following assignment is valid:

Collection<? super ArrayList<Number>> temp1
    = new LinkedHashSet<Iterable<Number>>();

The interesting thing about it is that:

LinkedHashSet is a subtype of Collection

But:

Iterable is a supertype of ArrayList

So the relation between the type arguments is in the reverse order relative to the types themselves.

But why is this necessary?

Remember the caveat from the previous section? It does not allow "writing" elements to the collection.

Lower bounded wildcards, on the other hand, allow for "writing" to the collection. In our add method we can, indeed, add elements to it.

But there's a different caveat.

The contravariance caveat

The caveat is that invoking any method returning the wildcard will simply return Object.

To make it clearer, suppose our add method was defined like:

void add(List<? extends Number> temp1);

Then invoking methods that accepts a type variable argument are OK:

static void add(List<? super Number> temp1) {
  // 'writing' to the type variable: OK
  temp1.add(1D);
  temp1.set(0, 123L);
  temp1.addAll(List.of(1, 2, 3));
}

On the other hand, while methods that return the wildcard compiles, they all return Object:

static void read(List<? super Number> temp1) {
  // 'reading' the type variable: java.lang.Object
  Object value = temp1.get(0);
  Iterator<? super Number> iterator = temp1.iterator();
  Object next = iterator.next();
}

java.lang.Object is the highest supertype of Number (or of any reference type for the matter).

JEP 300

As final note I'd like to mention JEP 300.

At time of writing it is just in the candidate status. In other words, it is just an idea worth pursuing; it does not mean it will be targeted for any JDK release.

It proposes introducing declaration-site variance. So, instead of "annotating" methods with wildcards, you would annotate the type parameter at the type declaration instead.

Conclusion

In this blog post we discussed a few topics on Java generics.

We saw that Java type parameters are invariant.

Next, we saw how the language provides type variance through wildcard type arguments:

upper bounded wildcards
lower bounded wildcards

By discussing those, we also touched on the topics of:

covariance
contravariance

In particular, we saw the caveats of each.

Finally, we quickly mentioned JEP 300.

The source code for the examples in this post can be found in this GitHub repository.

In Java, type parameters are invariant

An example that can be compiled

A more idiomatic example

Actually using our list

consume method: accepting more types

consume method: accepting even more types

consume method: accepting even more types (again)

Removing the New class

add method: accept more types

add method: accepting even more types

add method: accepting even more types (again)