CODEWITHSUNDEEP
javagenericsbounded-wildcardsubtyping
Geoffrey Irving
Geoffrey Irving

Reputation: 6613

Where does the Java spec say List<T> assigns to List<? super T>?

Assume class B inherits from class A. The following is legal Java:

List<A> x;
List<? super B> y = x;

In terms of the specification, this means that List<A> assignsTo List<? super B>. However, I am having trouble finding the part of the spec that says this is legal. In particular, I believe we should have the subtype relation

List<A>  <:  List<? super B>

but section 4.10 of the Java 8 spec defines the subtype relation as the transitive closure of a direct supertype relation S >1 T, and it defines the direct supertype relation in terms of a finite function which computes a set of supertypes of T. There is no bounded function which on input List<A> can produce List<? super B> since there might be an arbitrary number of Bs that inherit from A, so the spec's subtype definition seems to break down for super wildcards. Section 4.10.2 on "Subtyping among class and interface types" does mention wildcards, but it handles only the other direction where the wildcard appears in the potential subtype (this direction fits into the computed direct supertype mechanism).

Question: What part of the spec says that the above code is legal?

The motivation is for compiler code, so it's not enough to understand why it is legal intuitively or come up with an algorithm that handles it. Since the general subtyping problem in Java is undecidable, I would like to handle exactly the same cases as the spec, and therefore want the part of the spec that handles this case.

Upvotes: 16

Views: 323

Answers (2)

John Kugelman
John Kugelman

Reputation: 362007

List<? super B> is defined to be a supertype of List<A> by §4.10.2. Subtyping among Class and Interface Types:

The direct supertypes of the parameterized type C<T1,...,Tn>, where Ti (1 ≤ i ≤ n) is a type, are all of the following:

  • D<U1 θ,...,Uk θ>, where D<U1,...,Uk> is a direct supertype of C<T1,...,Tn> and θ is the substitution [F1:=T1,...,Fn:=Tn].

  • C<S1,...,Sn>, where Si contains Ti (1 ≤ i ≤ n) (§4.5.1).

Let C<T1,...,Tn> = List<A> and C<S1,...,Sn> = List<? super B>. According to the second bullet, List<? super B> is a supertype of List<A> if ? super B contains A.

The contains relation is defined in §4.5.1. Type Arguments and Wildcards:

A type argument T1 is said to contain another type argument T2, written T2 <= T1, if the set of types denoted by T2 is provably a subset of the set of types denoted by T1 under the reflexive and transitive closure of the following rules (where <: denotes subtyping (§4.10)):

  • ? extends T <= ? extends S if T <: S

  • ? super T <= ? super S if S <: T

  • T <= T

  • T <= ? extends T

  • T <= ? super T

By the second bullet, we can see that ? super B contains ? super A. By the last bullet, we see that ? super A contains A. Transitively, we therefore know that ? super B contains A.

Upvotes: 11

durron597
durron597

Reputation: 32343

What does assigning the list to <? super B> actually mean?

Consider the following program:

public class Generics {
    static class Quux { }
    static class Foo extends Quux { }
    static class Bar extends Foo { }

    public static void main(String... args) {
        List<Foo> fooList = new ArrayList<>();
        // This is legal Java
        List<? super Bar> superBarList = fooList;
        // So is this
        List<? super Foo> superFooList = fooList;

        // However, this is *not* legal Java
        superBarList.add(new Quux());

        // Neither is this
        superFooList.add(new Quux());

        // Or this:
        superFooList.add(new Object());

        // But this is fine
        superFooList.add(new Foo());
    }
}

Why would this be? First of all, let's talk about what the JLS says

From the JLS, §4.5.1:

A type argument T1 is said to contain another type argument T2, written T2 <= T1, if the set of types denoted by T2 is provably a subset of the set of types denoted by T1 under the reflexive and transitive closure of the following rules (where <: denotes subtyping (§4.10)):

  • ? super T <= ? super S if S <: T
  • T <= ? super T

Therefore, T <= ? super S if S <: T.

... but what does THAT mean?

If I can't add a new Quux(), or a new Object()? List<? super Foo> means that this list contains only elements which are strict supertypes to Foo, but I don't know which type that happens to be. In other words, I can declare the list to be such a type, but I cannot add elements to it that I am not 100% certain are of type ? super Foo. Quux could be that type, but it might also not be that type.

For this reason, assigning a List<Foo> to to be List<? super Bar> doesn't allow heap pollution, and ultimately isn't a problem.

Further reading: Relevant section of AngelikaLanger's generic explanation

Upvotes: 4

Related Questions