JDK-6207386 : Undecidable type system leads to crash
  • Type: Bug
  • Component: tools
  • Sub-Component: javac
  • Affected Version: 6
  • Priority: P2
  • Status: Closed
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2004-12-11
  • Updated: 2010-04-02
  • Resolved: 2006-02-04
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 6
6 b71Fixed
Related Reports
Relates :  
JDK-6586091 - javac crashes with StackOverflowError
Description
Javac crashes on this program:

class F<T> {}
class C<X extends F<F<? super X>>> {
    C(X x) {
        F<? super X> f = x;
    }
}

The specification needs to be changed to resolve this issue, see 6207379.
Once the specification is clarified, the compiler should be fixed.

###@###.### 2004-12-11 00:17:12 GMT
Stack trace on 5.0u6:

The system is out of resources.
Consult the following stack trace for details.
java.lang.StackOverflowError
        at com.sun.tools.javac.code.Types.lowerBound(Types.java:112)
        at com.sun.tools.javac.code.Types$IsSubTypeFcn.visitClassType(Types.java:410)
        at com.sun.tools.javac.code.Type$ClassType.accept(Type.java:482)
        at com.sun.tools.javac.code.Types$IsSubTypeFcn.isSubType(Types.java:347)
        at com.sun.tools.javac.code.Types$IsSubTypeFcn.visitType(Types.java:387)
Comments
EVALUATION See also http://www.cis.upenn.edu/~stevez/papers/MZ06.pdf for an analysis of the problem. Currently, javac uses a cache to detect the stack overflow. If the problem is detected, the compiler falls back to a more conservative approximation without super-bounded wildcards.
28-02-2006
SUGGESTED FIX See http://sa.sfbay.sun.com/projects/langtools_data/mustang/6207386
28-12-2005
EVALUATION The subtype relation should be tweaked slightly.
13-12-2005
SUGGESTED FIX From: Peter von der Ah�� <###@###.###> To: Martin Odersky <###@###.###> Cc: Neal M Gafter <###@###.###>, Gilad Bracha <###@###.###>, Mads Torgersen <###@###.###>, Erik Ernst <###@###.###>, Jonathan Gibbons <###@###.###>, Christian Plesner Hansen <###@###.###>, Mirko Viroli <###@###.###> Subject: Re: Is Java 1.5 subtyping decidable? Date: Wed, 19 Jan 2005 00:39:54 -0800 Neal pointed out that the answer should be no. So that made me think. This is probably better: u'(F<F<? super X>>) <: l'(F<? super X>) where u'(F<F<? super X>>) = F<? extends F<?>> and l'(F<? super X>) = F<? super X> Now T <: u'(T), and similarly, l'(T) <: T. This leads to this question: F<? extends F<?>> <: F<? super X> which leads to: L(? super X) <: L(? extends F<?>) && U(? extends F<?>) <: U(? super X) which is X <: BOTTOM && F<?> <: Object The answer is then no. Again, I apologize for thinking aloud. Cheers, Peter On Tue, 2005-01-18 at 22:15, Peter von der Ah�� wrote: On Tue, 2005-01-18 at 11:50, Martin Odersky wrote: > > Hold on there! Don't break my libraries just because Peter is confused ;-) > > > > > > interface NaturalOrderedSet<E extends Comparable<? super E>> extends > > > OrderedSet<E> {} > > > > > > do we really want to disallow this perfectly natural type? > > > > > > > Good example! So what other solutions are there? Can we change the > > algorothms and prove that it terminates? Or is there another, more > > reasonable restriction (I don't see any at the moment)? > > > Forgive me for thinking out loud here. Repeating your example: > > class F<T> {} > class C<X extends F<F<? super X>>> { > C(X x) { > F<? super X> f = x; > } > } > To verify that > X <: F<? super X> > I need to unfold X to its upper bound, yielding: > F<F<? super X>> <: F<? super X> > > How about this test: > > u'(F<F<? super X>>) <: l'(F<? super X>) > where u'(F<F<? super X>>) = F<F<?>> > and l'(F<? super X>) = F<? super X> > This means this question: > > F<F<?>> <: F<? super X> > Which leads to: > > X <: F<?> > Which leads to: > > u'(F<F<? super X>>) <: l'(F<?>) > where u'(F<F<? super X>>) = F<F<?>> > l'(F<?>) = F<? super BOTTOM> > So: > > F<F<?>> <: F<? super BOTTOM> > Which leads to: > > BOTTOM <: F<?> > The answer is then yes. The formal definitions of u' and l' are left to the reader, but they are conservative estimates of upper and lower bounds respectively. Also some heuristic for when to apply u' and l' is needed. It seems to be necessary only when the type variable appears as as super bound on the left hand side. > > I have made a quick hack implementing this and it appears to work, here is debug output from the compiler: > > F<F<? super X>> <: F<? super X> > u'(F<F<? super X>>) = F<F<? extends java.lang.Object>> > l'(F<? super X>) = F<? super X> > F<F<? extends java.lang.Object>> <: F<? super X> > F<F<? super X>> <: F<? extends java.lang.Object> > u'(F<F<? super X>>) = F<F<? extends java.lang.Object>> > l'(F<? extends java.lang.Object>) = F<? super <nulltype>> > F<F<? extends java.lang.Object>> <: F<? super <nulltype>> > And my example: > > interface F<T> {} > interface G<Y> extends F<F<Y>> {} > class C<X extends G<? super X>> { > C(X x) { > F<? super X> f = x; > } > } > Debug output: > > G<? super X> <: F<? super X> > u'(G<? super X>) = G<? extends java.lang.Object> > l'(F<? super X>) = F<? super X> > G<? extends java.lang.Object> <: F<? super X> > G<? super X> <: F<? extends java.lang.Object> > u'(G<? super X>) = G<? extends java.lang.Object> > l'(F<? extends java.lang.Object>) = F<? super <nulltype>> > G<? extends java.lang.Object> <: F<? super <nulltype>> > Cheers, > Peter >
05-12-2005