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

Question

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.

Fistic

Define "subtype relation"? Generics are not reifiable so I fail to see your point – Leotie

Unfortunately, the best I can do is say that the subtyping relation is defined in Section 4.10 of the spec. :) A first principles definition doesn't help here, since it doesn't localize which part of the spec says my particular wildcard assignsTo is valid. I can't see that the spec's subtype relation handles it, but I also can't see how the spec's assignsTo relation handles it, so I'm lost. – Fistic

To clarify, the reason I'm talking about subtyping at all is that assignsTo is defined in terms of widening reference conversions which is defined in terms of subtyping. However, assignsTo is defined in terms of a pile of other relations as well, so the relevant bit could be unrelated to subtyping. – Fistic

I'm in the same spot you were many years ago. Everything is defined, or at least wants to be defined, in terms of direct supertypes. As @John Kugelman points out below, it's in the language of the "contains" clause in 4.5.1. Where that gets weird is in conjunction with 4.10.2 it appears to be the only place in the JLS where something is defined to be its own direct supertype. More: #69520038 – Daryl

Answer 1

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.

Idaho

I made this community wiki because I'm not sure I got all of the details right. Language lawyers, please correct anything I got wrong. – Idaho

"I'm not sure I got all of the details right." You did. – Shipway

As I mentioned in the question, 4.10.2 says to apply capture conversion to the thing that is the subtype to find its direct supertypes. However, in this case the subtype is List<A>, so there's no capture conversion to apply. Thus, I don't yet understand how that section works in my case. – Fistic

Ah, got it. I had missed the critical C<S1,...,Sn>, where Si contains Ti (1 ≤ i ≤ n) (§4.5.1). bit. Thanks! – Fistic

@GeoffreyIrving Actually I suppose you are right that ? super A does not get captured in the assignment context, but it doesn't matter. The excerpts from 4.10.2 and 4.5.1 show that List<? super A> is a direct supertype of List<A>. – Shipway

Perfect, that last edit removes the bit that was leading me astray. All good! – Fistic

Answer 2

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

Epanodos

This is a good explanation, and I wish my question was about either intuitive understanding or semantic proofs of safety. Either would be so much easier! :) Unfortunately, I am mired in compiler internals, and specifically need where in the spec assignsTo or subtype is defined for this case. You're absolutely right that it should be related to the contains relation on type arguments, but unfortunately I can't figure out how. – Fistic