United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-7024568 Very long method resolution causing OOM error
JDK-7024568 : Very long method resolution causing OOM error

Details
Type:
Bug
Submit Date:
2011-03-04
Status:
Closed
Updated Date:
2011-09-14
Project Name:
JDK
Resolved Date:
2011-04-20
Component:
tools
OS:
generic
Sub-Component:
javac
CPU:
unknown
Priority:
P2
Resolution:
Fixed
Affected Versions:
6
Fixed Versions:

Related Reports
Backport:
Relates:

Sub Tasks

Description
Javac hangs while compiling the following program:


package pkg196134;

public class Main {

    public static void main(String[] args) {
        Obj o = null;
        o.test(0, 0, 0, 0, 0, 0, 0, 0, undefined);
    }
}

interface Test {
    public void test(int i1, int i2, int i3, int i4, int i5, int i6, int i7, int i8, String str);
    public void test(int i1, int i2, int i3, int i4, int i5, int i6, int i7, int i8, long l);
}

interface Obj extends Test, A, B, C, D, E {}
interface A extends Test {}
interface B extends A, Test {}
interface C extends A, B, Test {}
interface D extends A, B, C, Test {}
interface E extends A, B, C, D, Test {}


Compilation eventually fails with the following stack trace:

The system is out of resources.
Consult the following stack trace for details.
java.lang.OutOfMemoryError: Java heap space
	at java.util.Arrays.copyOfRange(Arrays.java:2694)
	at java.lang.String.<init>(String.java:234)
	at java.lang.StringBuilder.toString(StringBuilder.java:405)
	at com.sun.tools.javac.util.JCDiagnostic$Factory.qualify(JCDiagnostic.java:234)
	at com.sun.tools.javac.util.JCDiagnostic$Factory.create(JCDiagnostic.java:230)
	at com.sun.tools.javac.util.JCDiagnostic$Factory.fragment(JCDiagnostic.java:200)
	at com.sun.tools.javac.comp.Resolve$InapplicableMethodException.setMessage(Resolve.java:496)
	at com.sun.tools.javac.comp.Resolve.checkRawArgumentsAcceptable(Resolve.java:444)
	at com.sun.tools.javac.comp.Resolve.rawInstantiate(Resolve.java:389)
	at com.sun.tools.javac.comp.Resolve.instantiate(Resolve.java:405)
	at com.sun.tools.javac.comp.Resolve.signatureMoreSpecific(Resolve.java:820)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:727)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:803)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:803)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:803)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:803)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:803)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:803)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:803)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)
	at com.sun.tools.javac.comp.Resolve.mostSpecific(Resolve.java:802)

                                    

Comments
EVALUATION

Method resolution scans all supertypes of a given 'site' looking for a potentially applicable method. The problem is that the inheritance graph in this example:

interface Obj extends Test, A, B, C, D, E {}
interface A extends Test {}
interface B extends A, Test {}
interface C extends B, A, Test {}
...

Note that each new interface extends all existing interfaces. Since the 'site' we are starting with has type 'Obj', we need to scan all supertypes of Obj:

Obj -> { Test, A, B, C, D, E }

then for each type in the above list we should scan all supertypes:

Test -> {}
A -> { Test }
B -> {Test, A }
C -> { Test, A, B }
...

then, for each type in the above lists we should again determine all supertypes and look for potential candidates... this lead to a combinatorial explosion of checks - which is made worse by the fact that each time javac comes up with a pair of candidates, they are ambiguous (because the last argument in the method call is erroneous, so both methods are applicable but neither is most specific).

This means that javac ends up constructing bigger and bigger tree of AmbiguityErrors (because both methods in Test are seen more than once). The solution is to truncate recursion when we are scanning a supertype that has already been scanned. For example:

Step 1:

Obj -> { Test, A, B, C, D, E }

Step 2:

Test -> {}
A -> { Test } -> {} //Test already scanned
B -> {Test, A } -> {} //Test, A already scanned
C -> { Test, A, B } -> {} //Test, A,B already scanned
...

That is, during the second (recursive) step we are already able to determine that all candidates have already been retrieved.
                                     
2011-03-04
SUGGESTED FIX

A webrev of this fix is available at the following URL:
http://hg.openjdk.java.net/jdk7/tl/langtools/rev/74f0c05c51eb
                                     
2011-03-07



Hardware and Software, Engineered to Work Together