Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8078016

4.10.2: Cope with subtyping loops involving new capture variables



      The use of capture in the wildcard-parameterized class subtyping rule (JLS 4.10.2) allows new type variables to appear in a recursive subtyping invocation:

      "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> (§5.1.10)."

      The implication is that the set of types "reachable" from C<A1,...,An> (that is, types that might appear in a subsequent recursive subtyping test) include the fresh type variables named by capture(C<A1,...,An>); and since new type variables are produced every time capture is invoked, the reachable set of types is infinite. This implies that subtyping may be undecidable, or at least difficult to implement properly.

      Tate, Leung, & Lerner [1] provide the following example (slightly modified here):

      class C<P, Q extends Supplier<P>> implements List<List<? super C<Q,?>>> {}

      C<String,?> <: List<? super C<Integer,?>>
      C<String,CAP1> <: List<? super C<Integer,?>>
      List<List<? super<CAP1,?>>> <: List<? super C<Integer,?>>

      C<Integer,?> <: List<? super<CAP1,?>>
      C<Integer,CAP2> <: List<? super C<CAP1,?>>
      List<List<? super<CAP2,?>>> <: List<? super C<CAP1,?>>

      C<CAP1,?> <: List<? super<CAP2,?>>
      C<CAP1,CAP3> <: List<? super C<CAP2,?>>
      List<List<? super<CAP3,?>>> <: List<? super C<CAP2,?>>

      C<CAP2,?> <: List<? super<CAP3,?>>
      C<CAP2,CAP4> <: List<? super C<CAP3,?>>
      List<List<? super<CAP4,?>>> <: List<? super C<CAP3,?>>


      Note that no subtype test is repeated in this sequence: the types are similar, but at each cycle a different set of capture variables is used. Also note that, while each capture variable comes from the capture of a parameterization of C, each parameterization is different, resulting in a slightly different bound. So CAP1 <: Supplier<String>, CAP2 <: Supplier<Integer>, CAP3 <: Supplier<CAP1>, CAP4 <: Supplier<CAP2>, etc.

      It's unclear how best to address this. Intuitively, continuing to produce capture variables isn't going to get us any closer to an answer, and perhaps a loop detection test could somehow detect this—although note that the relationship between, say, CAP2 and CAP4 is nontrivial. There may also be syntactic restrictions that could be applied to the use of wildcards in extends clauses—though wildcards appear quite naturally in many contexts, perhaps so much so that there can be no reasonable restriction.

      [1] http://www.cs.cornell.edu/~ross/publications/tamewild/


          Issue Links



              • Assignee:
                dlsmith Dan Smith
                dlsmith Dan Smith
              • Votes:
                0 Vote for this issue
                2 Start watching this issue


                • Created: