When does Java type inference produce an infinite type?

Question

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?

Answer 1

A possibility of infinite types could be (for example, an object of Map inside a map inside a map, etc.....

Map<? extends Serializable, Map<? extends Serializable, Map<? extends Serializable, Map<? extends Serializable, Map<? extends Serializable, Map>>>>> objectMap;

(This is done to depth 5 for readability...but you can add maps inside a map infinitely deep.

I don't know if that's what you're looking for....

Answer 2

From what I recall from Types and Programming Languages, recursive types are infinite.

This means that List< List<?> > is already recursive. Indeed, purely from a typing point of view, the following is ok:

    List< List<?> > x = null;
    x.add( x );

At run-time it of course fails with NPE.

I should double-check all that, and whether if that's what is meant by the JLS, but that brings maybe some light on this interesting question.

Answer 3

The following code sends javac to an infinite loop. Presumably, it tries to build an infinite type, but does not manage to represent it as a finite cyclic data structure.

interface I<T> {}
interface A<T> extends I<A<A<T>>>{}
abstract class X {
    abstract <T> T foo(T x, T y);

    void bar(A<Integer> x, A<String> y){
        foo(x, y);
    }
}