United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6369605 Unconstrained type variables fails to include bounds
JDK-6369605 : Unconstrained type variables fails to include bounds

Details
Type:
Bug
Submit Date:
2006-01-06
Status:
Closed
Updated Date:
2012-03-23
Project Name:
JDK
Resolved Date:
2011-03-07
Component:
tools
OS:
generic,windows_xp
Sub-Component:
javac
CPU:
x86,generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
5.0,6u25
Fixed Versions:

Related Reports
Duplicate:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:

Sub Tasks

Description
See https://bugs.eclipse.org/bugs/show_bug.cgi?id=121369

Javac fails to infer the correct type for this method call

    Foo.foo();

given this definition of Foo:

class Foo {
  static <T, U extends java.util.List<T>> void foo() {
    return;
  }
}

                                    

Comments
EVALUATION

This is a bug in how unconstrained type variables get values inferred.

Furthermore, there appears to be a specification bug, see 6369608.
                                     
2006-01-06
EVALUATION

This problem entails both the compiler implementation and the JLS. The compiler side of the problem is that currently the compiler fails to include recursive bounds when resolving unconstrained type variables according to 15.12.2.8.

This means that given a set of unconstrained type variables X1 <: B1, X2 <: B2 ... Xn <: Bn, only those Bi that does not further depends on X1, X2 ... Xn are considered.

In the example, we have that U is inferred to be Object and, since the constraint T <: List<U> is not considered (as it contains a type-variable), T is inferred to be Object as well - which is wrong.

So far so good, now let's consider the following variation of the original source, in which U has been declared before T:

class Foo {
  static <U extends java.util.List<T>, T> U foo() {
    return;
  }
  String s = (String)foo();
}

This time the inference outcome is different: T is inferred to be Object, while U is inferred to be List<Object> - which appears to be correct. Where does this result come from and, more importantly, why type-inference produce different results depending on the order in which method type variables are declared?

The answer is relatively easy - there's a bug in the routine that checks whether a type does contain an instance of a set of types (Type.containsSome). The routine only check a given type against the first element of the list - this means that when the compiler ensures that the declared bound List<T> does not contain neither U nor T (the order is important!), the compiler only checks that it doesn't contain U, which is true (it only contains T!). As a result the bound is 'erroneously' included in the constraint list so that U is inferred to be List<T> accordingly to JLS 15.12.2.8.

IN the end it seems that this bug could be solved quite easily by fixing Type.containsSome, and by changing the code in Infer.instantiateExpr so that fbounds are taken into account. Unfortunately it's not that easy; consider the following code:

class Foo {
  static <T extends java.util.List<T>> T foo() {
    return;
  }
  String s = (String)foo();
}

This time T's declared bound is recursive; what we should infer in such case? If we look at JLS 15.12.2.8, it looks like T should be inferred to be List<T>, since T <: List<T> is the only available constraint here (given that the method call does not appear in an assignment context). Which means T = glb(List<T>) = List<T>.

This kind of inference has two problems: (i) it allows a type-variable to escape the method declaration's scope and (ii) the inferred result does not satisfy the declared bound. The latter problem is actually the worse: after inference we should check that List<T> <: [T:=List<T>]List<T> = List<list<T>>, which does not hold. This means that even with no other constraints than the declared bound, the inference process is not able to yield a useful answer for T.

What is the correct type for T ? At first it seems that by exploiting some combination of wildcards we should be able to get inference right: e.g. T = List<? extends List<?>>. However that's not true - even if the inferred type does not expose the type-variable anymore, it still suffers from not being able to satisfy the declared bound of T (List<? extends List<?>> is not a subtype of List<List<? extends List<?>>>).

The only possible answer is to infer T as a captured type variable #1, where the upper bound of #1 is set to List<#1>. This way we have a type that (i) does not contain the original type-variable and (ii) satisfies the bound check:

#1 <: [T:=#1]List<T> - List<#1>
ub(#1) = List<#1> <: List<#1> ok!
                                     
2007-12-18
SUGGESTED FIX

A webrev of this fix is available at the following URL:
http://hg.openjdk.java.net/jdk7/tl/langtools/rev/dc550520ed6f
                                     
2007-12-18
SUGGESTED FIX

--- old/src/share/classes/com/sun/tools/javac/code/Type.java	Tue Dec 18 16:30:50 2007
+++ new/src/share/classes/com/sun/tools/javac/code/Type.java	Tue Dec 18 16:30:50 2007
@@ -354,7 +354,8 @@
      */
     public boolean containsSome(List<Type> ts) {
         for (List<Type> l = ts; l.nonEmpty(); l = l.tail)
-            if (this.contains(ts.head)) return true;
+            if (this.contains(l.head)) return true;
         return false;
     }
                                     
2007-12-21
SUGGESTED FIX

--- old/src/share/classes/com/sun/tools/javac/code/Types.java	Fri Dec 21 13:52:01 2007
+++ new/src/share/classes/com/sun/tools/javac/code/Types.java	Fri Dec 21 13:52:01 2007
@@ -662,6 +662,7 @@
                     return visit(t.inst, s);
 
                 t.inst = fromUnknownFun.apply(s);
+                t.hibounds = subst(t.hibounds, List.of(t.qtype), List.of(t.inst));
                 for (List<Type> l = t.lobounds; l.nonEmpty(); l = l.tail) {
                     if (!isSubtype(l.head, t.inst))
                         return false;
                                     
2007-12-21



Hardware and Software, Engineered to Work Together