United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6638712 Inference with wildcard types causes selection of inapplicable method
JDK-6638712 : Inference with wildcard types causes selection of inapplicable method

Details
Type:
Bug
Submit Date:
2007-12-06
Status:
Closed
Updated Date:
2012-01-13
Project Name:
JDK
Resolved Date:
2012-01-13
Component:
tools
OS:
generic,windows_xp
Sub-Component:
javac
CPU:
x86,generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
6u10,6u23,7
Fixed Versions:

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

Sub Tasks

Description
From Neal Gafter:

The following demonstrates a bug in javac's handling of wildcard types that results in a hole in the type system. javac accepts this program without even a warning but it blows up with a class cast error at runtime.  The Java compiler for Eclipse rejects this code.

import java.util.*;

class Comp {
  static <T> Comparator<T> compound(final Iterable<? extends Comparator<? super T>> it) {
    return new Comparator<T>() {
      public int compare(T t1, T t2) {
        for (Comparator<? super T> c : it) {
          int r = c.compare(t1, t2);
          if (r != 0) return r;
        }
        return 0;
      }
    };
  }
  public static void main(String[] args) {
    List<Comparator<?>> x = new ArrayList<Comparator<?>>();
    Comparator<Integer> c1 = new Comparator<Integer>() {
      public int compare(Integer i1, Integer i2) {
        return i1.compareTo(i2);
      }
    };
    x.add(c1);
    x.add(String.CASE_INSENSITIVE_ORDER);
    Comparator<String> c3 = compound(x);
    c3.compare("foo", "bar");
  }
}

                                    

Comments
EVALUATION

The problem line is:
  Comparator<String> c3 = compound(x);
To infer T for compound(x), the initial constraint is:
  List<Comparator<?>> << Iterable<? extends Comparator<? super T>>
List<Comparator<?>> has a supertype Iterable<Comparator<?>> so we get a new constraint:
  Comparator<?> << ? extends Comparator<? super T>
which causes the JLS to give up on inferring T from actual parameters.

(Sidebar: One could imagine rewriting the constraint to:
  Comparator<? extends Object> << Comparator<? super T>
and inferring T as the null type. The assignment in main of a Comparator<null> to a Comparator<String> would then fail nicely.)

T is then inferred as String from the assignment conversion context, i.e.
  Comparator<String> >> Comparator<T>
We continue with overload resolution, but no method is applicable because the List<Comparator<?>> actual parameter neither subtypes nor converts to Iterable<? extends Comparator<? super String>>. javac should give an error for this reason.
                                     
2007-12-07
EVALUATION

This bug seems to be related to javac failing to propagate <<-like constraints (already discussed in 6640435) that have been generated during inference based on actual argument types over uninferred type variables so that those constraints can actively be exploited in the second part of the inference process (the one taking into account method return type).
                                     
2007-12-18
EVALUATION

After a more accurate evaluation, this bug is definitely due to javac not behaving as described in section 15.12.2.2. A method is defined to be "applicable by subtyping" if the following conditions hold:

1a) each actual argument type is a subtype of the corresponding formal in the method declaration (formal parameter types have to be consider after type inference)

1b) each (either inferred or explicitely given) type parameter must conform to its declared bound.

What is described in section 15.12.2.2 is a sanity check, since we are ensuring that inferred type arguments does not conflict with method applicability. Note that such a check would prevent erroneous situations like the ones described in this CR (in both 'description' and 'comments' sections). Unfortunately javac doesn not apply this kind of "global" check; rather, it applies a smaller check after each of the two steps of type inference has occurred. More precisely it applies it checks for the condition 1a) after 15.12.2.7, while 1b) is only checked after 15.12.2.8. For example, given a type variable T inferred during 15.12.2.7, T is only checked against its bounds (and against the bounds of other type variables that have been inferred in this step, if any); if there is another uninferred Z type variable whose bound happen to involve T, the inferred type of T is not checked against Z's bound, thus possibly opening a hole in the type-system safety.

Another problem is the one described in this CR, where 15.12.2.8 causes the type variable T to be inferred to a type (String) that makes the method unapplicable, since after type substitution [T/String] formals are not supertypes of their corresponding actuals. Again, this is condition 1a) and javac only check for it during 15.12.2.7.

The obvious solution is to strictly follow what described in section 15.12.2.2, so that method applicability is fully checked AFTER type inference has completed. However figuring a way for doing this is not that simple since the compiler does not retain information about the method being called when performing inference as described in 15.12.2.8, making it difficult to detect this kind of conflicts between method applicability and type inference.
                                     
2008-02-11
EVALUATION

It's quite easy however to extend the compiler so that constraints that have been found during the first step of type inference are propagated onto the second step. 

***** Example 1) 

We have that a constraint of the type <nulltype> >> T is generated when checking for method applicability of Comp.compound() we have that the actual argument x should be a subtype of the only formal of the method:

List<Comparator<?>> <: Iterable<? extends Comparable<? super T>>
Iterable<Comparator<?>> <: Iterable<? extends Comparable<? super T>>
Comparator<?> <: ? extends Comparable<? super T>
Comparator<?> <: Comparable<? super T>
? <= ? super T

as we can see, there is no type we can infer for T such that the above type containment relation will hold. The only type that satisfies the relation is <nulltype>.
If we carry this information later on when performing the second step of type-inference, we can indeed realize that the following set of constraints is unsolvable: 

Comparator<String> >> Comparator<T>
<nulltype> >> T (from the step above) 

The first reduces to T == String, but String cannot be inferred for T since this violates the second constraint (T should be a subtype of nulltype). Thus, the method is not applicable for any T.

***** Example 2)

In this example we have that a constraint I >> Foo<Integer> is initially generated, thus I = lub(Foo<Integer>) = Foo<Integer>, not surprisingly, since there is only one parameter here. However, when we check that the inferred type for I is indeed a subtype of I's bound, we could generate another constraint

T == Integer (since I == Foo<Integer> and Foo<T> is the declared bound of I)

Unfortunately this guess is discarded by the compiler that looks forward to infer T during the second step of type-inference. The only constraints generated into this latter phase are String >> T and Object >> T, leading to T = glb(String,Object) = String. If we only had the formerly generated constraint of the form T == Integer, the set would have been unsolvable, making the selected method unapplicable.
                                     
2008-03-07
SUGGESTED FIX

A webrev of this fix is available at the following URL:
http://hg.openjdk.java.net/jdk7/tl/langtools/rev/22872b24d38c
                                     
2008-03-07



Hardware and Software, Engineered to Work Together