When does Java type inference produce an infinite type?

user_141502 0
Viewed 817

The JLS mentions in the type inference algorithm (§15.12.2):

It is possible that the process above yields an infinite type. This is permissible, and Java compilers must recognize such situations and represent them appropriately using cyclic data structures.

However, I'm unable to find an actual example where javac produces an infinite type. I think it ought to produce one in the following case:

<T> T pick(T a, T b) { ... }

pick("string", 3);

Both String and Integer are Comparable<themselve>, so their common supertype should be Comparable<? extends Comparable<? extends Comparable<? ...>>> (infinite).

I can do:

Comparable<? extends Comparable<?>> x = pick("string", 3);

but then I tried:

Comparable<? extends Comparable<? extends Comparable<?>>> x = pick("string", 3);

and this doesn't compile. It seems that the recursion is aborted after 2 steps.

Do you know of any case to make Java actually produce an infinite type?

--

Edit: it seems that the above is a compiler bug. Reading the specification, let's see how the calculation of lub(String, Integer) works out:

ST(String) = { String, Comparable<String>, Serializable, CharSequence, Object }
ST(Integer) = { Integer, Comparable<Integer>, Serializable, Number, Object }
EC = { Comparable, Serializable, Object }
MEC = { Comparable, Serializable }
Inv(Comparable) = { Comparable<String>, Comparable<Integer> }
lcta(String, Integer) = ? extends lub(String, Integer)
lci(Inv(Comparable)) = Comparable<? extends lub(String, Integer)>
lub(String, Integer) = Serializable & Comparable<? extends lub(String, Integer)>

So lub(String, Integer) should be an infinite type. Javac seems to be wrong here. Maybe it doesn't implement infinite types after all?

wildcard type-inference programming-languages java
3 Answers

This question have been answered by R.Grigore(2016) in his paper Java Generics are Turing Complete

Take the following Java code as an example to his suggestion:

//an empty interface
interface Z {}

//4 generic interfaces, one argument each
interface N<X> {}
interface L<X> {}
interface Qlr<X> {}
interface Qrl<X> {}

//one complex generic, inheriting from instantiations of two other
interface E<X> extends
    Qlr<N<? super Qr<? super E<? super E<? super X>>>>>,
    Qrl<N<?super Ql<? super E<? super E<? super X>>>>>
    {}

//main class with a single function
class Main{
    //heavily nested return type
    L<? super N<? super L<? super N<? super L<? super N<? super E<? super E<? super Z>>>>>>>>
    f(Qr<? super E<? super E<? super Z>>> v) {return v;}
}
user_139065150
Related