Bug 122775 - [1.5][compiler] StackOverflow in compiler
Summary: [1.5][compiler] StackOverflow in compiler
Status: VERIFIED FIXED
Alias: None
Product: JDT
Classification: Eclipse Project
Component: Core (show other bugs)
Version: 3.1   Edit
Hardware: PC Linux
: P3 normal (vote)
Target Milestone: 3.2 M6   Edit
Assignee: Philipe Mulet CLA
QA Contact:
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2006-01-05 11:41 EST by Adam Kiezun CLA
Modified: 2006-03-27 11:23 EST (History)
0 users

See Also:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Adam Kiezun CLA 2006-01-05 11:41:19 EST 
Eclipse 3.1

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

org.eclipse.core.internal.utils.AssertionFailedException: Assertion failed: Marker property value is too long: Internal compiler error
java.lang.StackOverflowError
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:323)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isCompatibleWith(ReferenceBinding.java:769)
	at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.isTypeArgumentContainedBy(TypeBinding.java:360)
	at org.eclipse.jdt.internal.compiler.lookup.ParameterizedTypeBinding.isEquivalentTo(ParameterizedTypeBinding.java:594)
	at org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding.isSuperclassOf(ReferenceBinding.java:841)
	at org.eclipse.jdt.internal.compiler.lookup.Ref
	at org.eclipse.core.internal.utils.Assert.isTrue(Assert.java:109)
	at org.eclipse.core.internal.resources.MarkerInfo.checkValidAttribute(MarkerInfo.java:57)
	at org.eclipse.core.internal.resources.MarkerInfo.setAttribute(MarkerInfo.java:120)
	at org.eclipse.core.internal.resources.MarkerInfo.setAttributes(MarkerInfo.java:147)
	at org.eclipse.core.internal.resources.Marker.setAttributes(Marker.java:279)
	at org.eclipse.jdt.internal.core.builder.AbstractImageBuilder.storeProblemsFor(AbstractImageBuilder.java:386)
	at org.eclipse.jdt.internal.core.builder.AbstractImageBuilder.updateProblemsFor(AbstractImageBuilder.java:456)
	at org.eclipse.jdt.internal.core.builder.AbstractImageBuilder.acceptResult(AbstractImageBuilder.java:96)
	at org.eclipse.jdt.internal.compiler.Compiler.handleInternalException(Compiler.java:411)
	at org.eclipse.jdt.internal.compiler.Compiler.compile(Compiler.java:348)
	at org.eclipse.jdt.internal.core.builder.AbstractImageBuilder.compile(AbstractImageBuilder.java:240)
	at org.eclipse.jdt.internal.core.builder.AbstractImageBuilder.compile(AbstractImageBuilder.java:190)
	at org.eclipse.jdt.internal.core.builder.BatchImageBuilder.build(BatchImageBuilder.java:50)
	at org.eclipse.jdt.internal.core.builder.JavaBuilder.buildAll(JavaBuilder.java:213)
	at org.eclipse.jdt.internal.core.builder.JavaBuilder.build(JavaBuilder.java:141)
	at org.eclipse.core.internal.events.BuildManager$2.run(BuildManager.java:593)
	at org.eclipse.core.internal.runtime.InternalPlatform.run(InternalPlatform.java:1044)
	at org.eclipse.core.runtime.Platform.run(Platform.java:783)
	at org.eclipse.core.internal.events.BuildManager.basicBuild(BuildManager.java:168)
	at org.eclipse.core.internal.events.BuildManager.basicBuild(BuildManager.java:202)
	at org.eclipse.core.internal.events.BuildManager$1.run(BuildManager.java:231)
	at org.eclipse.core.internal.runtime.InternalPlatform.run(InternalPlatform.java:1044)
	at org.eclipse.core.runtime.Platform.run(Platform.java:783)
	at org.eclipse.core.internal.events.BuildManager.basicBuild(BuildManager.java:234)
	at org.eclipse.core.internal.events.BuildManager.basicBuildLoop(BuildManager.java:253)
	at org.eclipse.core.internal.events.BuildManager.build(BuildManager.java:282)
	at org.eclipse.core.internal.resources.Workspace.build(Workspace.java:211)
	at org.eclipse.ui.actions.GlobalBuildAction$1.run(GlobalBuildAction.java:182)
	at org.eclipse.core.internal.jobs.Worker.run(Worker.java:76)
Comment 1 Philipe Mulet CLA 2006-01-05 11:56:38 EST 
Are you really writing such code ? <g>
Comment 2 Adam Kiezun CLA 2006-01-05 12:11:38 EST 
nope, and actually I didn't come up with this example myself. 
I saw it in a paper. :)
Comment 3 Philipe Mulet CLA 2006-02-01 05:57:16 EST 
Interestingly, javac has the same flaw:
D:\eclipse\workspaces\dev3.2\plugins\Crap\src>javac X.java -d ..\bin


The system is out of resources.
Consult the following stack trace for details.
java.lang.StackOverflowError
        at com.sun.tools.javac.code.Types$LowerBoundFcn.visitType(Types.java:119)
        at com.sun.tools.javac.code.Type$Visitor.visitClassType(Type.java:970)
        at com.sun.tools.javac.code.Type$ClassType.accept(Type.java:482)
        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)
        at com.sun.tools.javac.code.Type$Visitor.visitTypeVar(Type.java:975)
        at com.sun.tools.javac.code.Type$TypeVar.accept(Type.java:807)
        at com.sun.tools.javac.code.Types$IsSubTypeFcn.isSubType(Types.java:347)
        at com.sun.tools.javac.code.Types.isSubTypeNoCapture(Types.java:331)
        at com.sun.tools.javac.code.Types$ContainsTypeFcn.visitArgumentType(Types.java:881)
        at com.sun.tools.javac.code.Type$ArgumentType.accept(Type.java:367)
Comment 4 Adam Kiezun CLA 2006-02-01 07:53:20 EST 
yes, it's javac bug
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6207386

the problem is that apparently java's type system is undecidable:

see http://www.cis.upenn.edu/~stevez/papers/MZ06.pdf
section 3.2 
shown by reduction from subtyping in full F_<: which is known to be undecidable
Comment 5 Philipe Mulet CLA 2006-02-01 08:37:27 EST 
When checking 'f' local definition, compiler must ensure type of 'x' is compatible with type of 'f', i.e. : X  <:  Foo<? super X>

 which holds iff:
   Foo<Foo<? super X>> <: Foo<? super X>   // using lower bound of X on lhs
 which is true, providing type arguments satisfy:
   Foo<? super X>  <= ? super X
 using 4.5.1.1, it is true iff:
   X <: Foo<? super X>

  back to square one
Comment 6 Philipe Mulet CLA 2006-02-01 15:51:37 EST 
Added GenericTypeTests#test887-891
Comment 7 Philipe Mulet CLA 2006-02-28 06:38:58 EST 
Released Kent's cache for compatibility checks on ReferenceBinding.
Fixed
Comment 8 David Audel CLA 2006-03-27 11:23:15 EST 
Verified for 3.2 M6 using build I20060327-0010