Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Local type inference and contravariance in generic type variables

I came accross the following code:

public static <T> Set<T> distinct(
        Collection<? extends T> list,
        Comparator<? super T> comparator) {

    Set<T> set = new TreeSet<>(comparator);
    set.addAll(list);
    return set;
}

This code just uses an intermediate TreeSet to remove duplicates, where equality among elements is defined as per the provided comparator.

Let's give local type inference an opportunity, I (naively) thought... So I changed the above code to:

public static <T> Set<T> distinct(
        Collection<? extends T> list,
        Comparator<? super T> comparator) {

    var set = new TreeSet<>(comparator);
    set.addAll(list);
    return set;
}

This made sense to me, because the type of set can be inferred from the type of comparator, or so I thought. However, the modified code doesn't compile and generates the following error:

java: incompatible types: java.util.TreeSet<capture#1 of ? super T> cannot be converted to java.util.Set<T>

Now, I understand why the error occurs and I admit that the type of the comparator is actually Comparator<? super T>, so the type inferred by var is TreeSet<? super T>.

However, I wonder why var isn't able to infer the generic type of TreeSet as just T instead of ? super T. After all, according to the docs, a TreeSet<E> has a constructor that accepts an argument of type Comparator<? super E>. So invoking this constructor should create a TreeSet<E>, not a TreeSet<? super E>. (This is what the first snippet shows). I expected var to follow this same logic.

Note 1: One way to make the code compile would be to change the return type to Set<? super T>. However, that would be a hardly usable set...

Note 2: Another way would be to not use contravariance in the comparator, but I don't want this, because I wouldn't be able to use a Comparator that compares ancestors of T.

Note 3: I know that the first snippet works, so it seems obvious that I should stick to not using var and declare the set explicitly as Set<T>. However, my question is not whether I should discard my second snippet or how to fix it. Instead, I'd like to know why var is not inferring TreeSet<T> as the type of the set local variable in my 2nd snippet.


EDIT 1: In this comment, user @nullpointer correctly points out that I should make the following subtle change to make the 2nd snippet compile:

var set = new TreeSet<T>(comparator); // T brings in the magic!

Now the generic type parameter T is explicit for TreeSet, so var correctly infers the type of the set local variable as TreeSet<T>. Still, I'd like to know why I must specify T explicitly.


EDIT 2: In this other comment, user @Holger cleverly mentions that the following is forbidden in the language:

var set = new TreeSet<? super T>(comparator);

The code above fails to compile with the following error:

java: unexpected type
  required: class or interface without bounds
  found:    ? super T

So now the question becomes more evident: if I cannot explicitly specify the bounded generic type ? super T in the instantiation expression new TreeSet<? super T>(comparator), why is the compiler infering TreeSet<? super T> as the type of the set local variable?

like image 398
fps Avatar asked Apr 02 '18 18:04

fps


People also ask

What is local type inference?

Type inference occurs when a local variable is declared without an As clause and initialized. The compiler uses the type of the assigned initial value as the type of the variable. For example, each of the following lines of code declares a variable of type String . VB Copy. ' Using explicit typing.

What is infer generic type arguments?

Type inference represents the Java compiler's ability to look at a method invocation and its corresponding declaration to check and determine the type argument(s). The inference algorithm checks the types of the arguments and, if available, assigned type is returned.

What is type inference in Java?

Type inference is a Java compiler's ability to look at each method invocation and corresponding declaration to determine the type argument (or arguments) that make the invocation applicable.

What is type inference in compiler design?

Type inference is the ability to automatically deduce, either partially or fully, the type of an expression at compile time. The compiler is often able to infer the type of a variable or the type signature of a function, without explicit type annotations having been given.


1 Answers

According to Brian Goetz' answer on my question, he states:

Local variable type inference says: the types I need are probably already present on the right hand side, why repeat them on the left.

Regarding the code in your question, the only type available to infer (by using the Comparator provided) is TreeSet<? super T>. Us humans are smart enough to see that distinct returns set and expects a Set<T>. However, the compiler either may not be smart enough to resolve it (I'm sure it can), but it's more likely the fact that var infers the most specific type using the information provided on the RHS, and the architects didn't want to break that.

Now, as nullpointer stated in their comment, you can explicitly define your TreeSet to be of type T rather than the inferred capture type ? super T with the following:

var set = new TreeSet<T>(comparator);

I'd assume that explicit generic types override inferred types passed to the constructor, which would make sense.

JLS §14.4.1: Local Variable Declarators and Types seems to back up my claim, stating the following:

enter image description here

Note: "upward projection of T", which may just infer to the type (TreeSet instead of Set), but could possibly include generic type as well.

I believe it's the same reason why list in var list = List.<Number>of(1, 2, 3); is a List<Number> rather than a List<Integer>, which works just as well without var.

like image 126
Jacob G. Avatar answered Sep 20 '22 10:09

Jacob G.