Second order generics seem to behave differently than first order generics

Question

I thought I have a reasonable grasp of generics. For example, I understand why

private void addString(List<? extends String> list, String s) {
    list.add(s); // does not compile
    list.add(list.get(0)); // doesn't compile either
}

Does not compile. I even earned some internet karma with the knowledge.

But I'd think by the same argument this shouldn't compile:

private void addClassWildcard(List<Class<? extends String>> list, Class<? extends String> c) {
    list.add(c);
    list.add(list.get(0));
}

Nor should this:

private void addClass(List<Class<? extends String>> list, Class<String> c) {
    list.add(c);
    list.add(list.get(0));
}

But both compile. Why? What is the difference to the example from the top?

I'd appreciate an explanation in common English as well as a pointer to the relevant parts of the Java Specification or similar.

Answer 1

The second case is safe because all instances of Class<String> are instances of Class<? extends String>.

There is nothing unsafe about adding an instance of Class<? extends String> to a List<Class<? extends String> - you will get back an instance of Class<? extends String> using get(int), iterator() etc - so it's allowed.

---

In a sense the wildcard inside Class gets only considered when an instance of that is actually encountered. Consider the following examples (switching from String to Number since String is final).

private void addClass(List<Class<? extends Number>> list, Class<Number> c) {
    list.add(c);
    list.add(list.get(0));
}

private void tryItSubclass() {
    List<Class<Integer>> ints = new ArrayList<>();

    addClass(ints, Number.class); // does not compile 
}

Here ints can only ever contain instances of Class<Integer> but Number.class is also a Class<? extends Number> with ? captured as Number so the two types are not compatible.

private void tryItBound() {
    List<Class<Number>> ints = new ArrayList<>();

    addClass(ints, Number.class); // does not compile
}

Here ints can only ever contain instances of Class<Number> but Integer.class is also a Class<? extends Number> with ? captured as Integer so the two types are not compatible.

private void tryItWildcard() {
    List<Class<? extends Number>> ints = new ArrayList<>();

    addClass(ints, Number.class); // does compile

    Class<? extends Number> aClass = ints.get(0);
}

---

The first case is unsafe because - were there a hypothetical class which extended String (which there isn't, because String is final; however, generics ignore final), a List<? extends String> might be a List<HypotheticalClass>. As such, you can't add a String to a List<? extends String>, because you expect everything in that list to be an instance of HypotheticalClass:

List<HypotheticalClass> list = new ArrayList<>();
List<? extends String> list2 = list;
list2.add("");  // Not allowed, but pretend it is.
HypotheticalClass h = list.get(0);  // ClassCastException.

Answer 2

This has to do with capture conversion. Andy's answer is great but it doesn't explain how the specification works. My answer here is long because, well, this is a pretty dense part of the JLS, but I don't see it explained much and it's not that difficult if you walk through it step-by-step.

Capture conversion is a process whereby the compiler takes a type with wildcards and replaces (some of) the wildcards with types which are not wildcards.

The supertypes of a parameterized type with wildcards are the supertypes of that type after capture conversion:

4.10.2. Subtyping among Class and Interface Types

Given a generic type declaration C<F1,...,Fn> (n > 0), the direct supertypes of the parameterized type C<R1,...,Rn> where at least one of the Ri (1 ≤ i ≤ n) is a wildcard type argument, are the direct supertypes of the parameterized type C<X1,...,Xn> which is the result of applying capture conversion to C<R1,...,Rn>.

The types of the members (including methods) of a parameterized type with wildcards are the types of the members of that type after capture conversion:

4.5.2. Members and Constructors of Parameterized Types

Let C be a generic class or interface declaration with type parameters A1,...,An, and let C<T1,...,Tn> be a parameterization of C where, for 1 ≤ i ≤ n, Ti is a type (rather than a wildcard). Then:

• [skipped for irrelevance]

If any of the type arguments in the parameterization of C are wildcards, then:

• The types of the fields, methods, and constructors in C<T1,...,Tn> are the types of the fields, methods, and constructors in the capture conversion of C<T1,...,Tn>.

So how does capture conversion work?

Suppose we are given the following class declaration (chosen to illustrate some parts of the process more completely):

class C<V, W extends List<V>> {

    void m(V v, W w) {
    }
}

And the following use of this type:

C<Number, ?> c = new C<>();

Double       tArg = 1.0;
List<Number> uArg = new ArrayList<>();
c.m(tArg, uArg);

How do we determine the type of c.m for the purpose of determining if the argument types may be assigned to the parameter types?

Well, to start with, as stated above, the parameter types of c.m are the parameter types of m in the capture conversion of C<Number, ?>:

5.1.10. Capture Conversion

Let G name a generic type declaration with n type parameters A1,...,An with corresponding bounds U1,...,Un.

For this example:

• G is C.
• A1 is V with bound U1 which is Object.
• A2 is W with bound U2 which is List<V>.

There exists a capture conversion from a parameterized type G<T1,...,Tn> to a parameterized type G<S1,...,Sn>...

For this example, G<T1,...,Tn> is C<Number, ?>:

• T1 is Number.
• T2 is ?.

..., where, for 1 ≤ i ≤ n:

• If Ti is a wildcard type argument of the form ?, then Si is a fresh type variable whose upper bound is Ui[A1:=S1,...,An:=Sn] and whose lower bound is the null type.

• If Ti is a wildcard type argument of the form ? extends Bi, then Si is a fresh type variable whose upper bound is glb(Bi, Ui[A1:=S1,...,An:=Sn]) and whose lower bound is the null type.

  glb(V1,...,Vm) is defined as V1 & ... & Vm.

Ui[A1:=S1,...,An:=Sn] is the bound of Ai (the type parameter) with the substitution of each type argument for each corresponding type parameter. (This is why I declared C with a type parameter whose bound references another type parameter: because it illustrates what this part does.)

In our example, for T2 (which is ?), S2 is a fresh type variable whose upper bound is U2 (which is List<V>) with the substitution of Number for V.

S2 is therefore a fresh type variable whose upper bound is List<Number>.

For simplicity, I'm going to ignore the case where we have a bounded wildcard, but a bounded wildcard is essentially just capture converted to a fresh type variable whose bound is BoundOfWildcard & BoundOfTypeParameter. Also, if a wildcard has a lower bound (super), then the fresh type variable has the lower bound too.

If Ti is not a wildcard, then:

• Otherwise, Si = Ti.

So in our example, S1 is just T1 which is Number.

And that:

Capture conversion is not applied recursively.

which we'll get to later.

We now know that:

• S1 is Number.
• S2 is some type variable FRESH extends List<Number> which the compiler's just created.

Therefore, the capture conversion of C<Number, ?> is C<Number, FRESH>.

Now we can actually answer the question: are Double and List<Number> assignable to Number and FRESH extends List<Number>, respectively? In the former case, yes. In the latter case, no.

This is for the same reasons that the expression wouldn't compile if we declared a type variable in this way ourselves:

static <FRESH extends List<Number>> void n() {
    C<Number, FRESH> c = new C<>();

    Double       tArg = 1.0;
    List<Number> uArg = new ArrayList<>();
    c.m(tArg, uArg);
}

The supertypes of a type variable are:

• The direct supertypes of a type variable are the types listed in its bound.

Therefore, List<Number> may not be assigned to FRESH because List<Number> is a a supertype of FRESH.

By analogy, we could also declare a class this way:

class Fresh extends List<Number> {}
C<Number, Fresh> c = new C<>();

Double       tArg = 1.0;
List<Number> uArg = new ArrayList<>();
c.m(tArg, uArg);

That might be more familiar, and isn't really all that different with respect to how the relationship between types works in this case.

In other words, in our original example:

C<Number, ?> c = new C<>();

Double       tArg = 1.0;
List<Number> uArg = new ArrayList<>();
c.m(tArg, uArg);
//        ^^^^ this

is just a more complicated version of this:

Object o = ...;
String s = o; // Error: attempting to assign a supertype to its subtype.

and (at the end of the day) doesn't compile for roughly the same reason.

In Summary

Capture conversion takes wildcards and turns them in to type variables (temporarily). After that, it's just the regular rules of subtyping that cause these errors.

So for example, given the code in the question:

private void addString(List<? extends String> list, String s) {
    list.add(s); // does not compile
    list.add(list.get(0)); // doesn't compile either
}

While viewing the expression list.add(s), the compiler sees something like this:

private <CAP#1 extends String>
void addString(List<? extends String> list, String s) {
    ((List<CAP#1>) list).add( s );
    list.add(list.get(0));
}

The error produced is as follows:

error: no suitable method found for add(String)
        list.add(s); // does not compile
            ^
    method Collection.add(CAP#1) is not applicable
      (argument mismatch; String cannot be converted to CAP#1)
    method List.add(CAP#1) is not applicable
      (argument mismatch; String cannot be converted to CAP#1)
  where CAP#1 is a fresh type-variable:
    CAP#1 extends String from capture of ? extends String

In other words, the compiler found methods add(CAP#1) and String is inconvertible to the type variable CAP#1.

While viewing the expression list.add(list.get(0)), the compiler sees something like this:

private <CAP#1 extends String, CAP#2 extends String>
void addString(List<? extends String> list, String s) {
    list.add(s);
    ((List<CAP#2>) list).add( ((List<CAP#1>) list).get(0) );
}

The error produced is as follows:

error: no suitable method found for add(CAP#1)
        list.add(list.get(0)); // doesn't compile either
            ^
    method Collection.add(CAP#2) is not applicable
      (argument mismatch; String cannot be converted to CAP#2)
    method List.add(CAP#2) is not applicable
      (argument mismatch; String cannot be converted to CAP#2)
  where CAP#1,CAP#2 are fresh type-variables:
    CAP#1 extends String from capture of ? extends String
    CAP#2 extends String from capture of ? extends String

In other words, the compiler found that list.get(0) returns CAP#1 and found methods add(CAP#2) but CAP#1 is inconvertible to CAP#2.

(Source for errors.)

So why do List<Class<?>> and other similar types work?

Recall that:

• Otherwise, [if Ti is not a wildcard type], Si = Ti.

And that:

Capture conversion is not applied recursively.

So if Ti is a parameterized type like Class<?>, then Si is just Class<?>. Also, since capture conversion is not applied recursively, the algorithm just stops after converting T1,...,Tn to S1,...,Sn. The new type is not capture-converted and the bounds of the fresh type variables are not capture-converted.

We can also verify that this is indeed what the compiler does by causing some interesting errors:

Map<?, List<?>> m = new HashMap<>();

List<?> list = new ArrayList<>();
list.add(m);

This produces the following error:

error: no suitable method found for add(Map<CAP#1,List<?>>)
        list.add(m);
            ^
    […]

(Source.)

Note that the type argument List<?> in the Map type capture converts to itself.

And another:

Map<?, ? extends List<?>> m = new HashMap<>();

List<?> list = new ArrayList<>();
list.add(m);

This produces the following error:

error: no suitable method found for add(Map<CAP#1,CAP#2>)
        list.add(m);
            ^
    […]
  where CAP#1,CAP#2,CAP#3 are fresh type-variables:
    CAP#1 extends Object from capture of ?
    CAP#2 extends List<?> from capture of ? extends List<?>
    CAP#3 extends Object from capture of ?

(Source.)

Note that this time, while ? extends List<?> is capture-converted, the bound List<?> is not.

Finally

The answer to the question as-stated is that the wildcard in List<? extends String> is capture-converted to a fresh type variable but the wildcard in List<Class<? extends String>> is not.