JDK-6558545 : Undecidable type system leads to stack overflow
  • Type: Bug
  • Component: tools
  • Sub-Component: javac
  • Affected Version: 5.0,6u27,7,8,9
  • Priority: P4
  • Status: Closed
  • Resolution: Won't Fix
  • OS: generic,windows_xp
  • CPU: generic,x86
  • Submitted: 2007-05-17
  • Updated: 2025-10-07
  • Resolved: 2025-10-07
Related Reports
Blocks :  
JDK-8016206 - Develop a strategy for coping with expansive inheritance
Duplicate :  
JDK-7078829 - compiler stackoverflows
Duplicate :  
JDK-7116195 - javac gets a stack overflow on generics code
Duplicate :  
JDK-8027982 - Compiler infinite recursion when using transitive, recursive generics
Duplicate :  
JDK-2213366 - compiler stackoverflows
Duplicate :  
JDK-8062888 - Compiler crashes with StackOverflowError when type comparison is undecidable
Relates :  
JDK-8027982 - Compiler infinite recursion when using transitive, recursive generics
Relates :  
JDK-8043725 - javac fails with StackOverflowException
Description
This crashes the compiler:

class T { }
class N<Z> { }
class C<X> extends N<N<? super C<C<X>>>> {
  N<? super C<T>> cast(C<T> c) { return c; }
}

from http://research.microsoft.com/~akenn/generics/FOOL2007.pdf
Comments
There are several papers which propose "reasonable" restrictions to the type system, at least one of which does seem to be truly reasonable, that restore the decidability of the type system. However, adopting these would require a widespread study of the effects on existing Java code. The alternative is to implement a type checker that is guaranteed to be complete for all well-typed programs, but may diverge on ill-typed ones, which would involve significant changes to the type checker. Both of these are at least JEP-level efforts, and it's questionable whether they could even be done for 9. They obviously cannot be done for 8. A final note: this issue needs to be addressed as part of any effort to reify generics.
23-08-2013