Bugzilla – Full Text Bug Listing
| Summary: | Eclipse compiler gets stuck in infinite loop | ||
|---|---|---|---|
| Product: | [Eclipse Project] JDT | Reporter: | Stefan Xenos <sxenos> |
| Component: | Core | Assignee: | Till Brychcy <register.eclipse> |
| Status: | VERIFIED FIXED | QA Contact: | Stephan Herrmann <stephan.herrmann> |
| Severity: | normal | ||
| Priority: | P3 | CC: | daniel_megert, dominik.stadler, jarthana, manoj.palat, register.eclipse, stephan.herrmann |
| Version: | 4.6 | Flags: | daniel_megert:
pmc_approved+
stephan.herrmann: review+ |
| Target Milestone: | 4.6.2 | ||
| Hardware: | PC | ||
| OS: | Linux | ||
| See Also: |
https://git.eclipse.org/r/82139 https://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/?id=372105883c90f57f2c7a8992de070fba3f4f7974 https://git.eclipse.org/r/85227 https://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/?id=0cdebe3b9ca49ce7d54cc31b9fee2a075a55b264 https://bugs.eclipse.org/bugs/show_bug.cgi?id=527742 |
||
| Whiteboard: | |||
Here is a stack trace from the livelocked indexer thread: at org.eclipse.jdt.internal.compiler.lookup.TypeBinding.findSuperTypeOriginatingFrom(TypeBinding.java:422) at org.eclipse.jdt.internal.compiler.lookup.CaptureBinding18.findSuperTypeOriginatingFrom(CaptureBinding18.java:188) at org.eclipse.jdt.internal.compiler.lookup.CaptureBinding18.findSuperTypeOriginatingFrom(CaptureBinding18.java:181) at org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.addConstraintsFromTypeParameters(ConstraintTypeFormula.java:368) at org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduceSubType(ConstraintTypeFormula.java:250) at org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduce(ConstraintTypeFormula.java:95) at org.eclipse.jdt.internal.compiler.lookup.BoundSet.reduceOneConstraint(BoundSet.java:949) at org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(BoundSet.java:669) at org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(BoundSet.java:570) at org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.resolve(InferenceContext18.java:1076) at org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.solve(InferenceContext18.java:843) at org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod18(ParameterizedGenericMethodBinding.java:238) at org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod(ParameterizedGenericMethodBinding.java:84) at org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(Scope.java:743) at org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(Scope.java:700) at org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(Scope.java:1656) at org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(Scope.java:1557) at org.eclipse.jdt.internal.compiler.lookup.Scope.getMethod(Scope.java:2840) at org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(MessageSend.java:915) at org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(MessageSend.java:729) at org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(MessageSend.java:684) at org.eclipse.jdt.internal.compiler.ast.FieldDeclaration.resolve(FieldDeclaration.java:266) at org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(TypeDeclaration.java:1131) at org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(TypeDeclaration.java:1308) at org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve(CompilationUnitDeclaration.java:593) at org.eclipse.jdt.internal.core.search.indexing.SourceIndexer.resolveDocument(SourceIndexer.java:165) at org.eclipse.jdt.internal.core.search.JavaSearchParticipant.resolveDocument(JavaSearchParticipant.java:102) at org.eclipse.jdt.internal.core.search.indexing.IndexManager.indexResolvedDocument(IndexManager.java:510) at org.eclipse.jdt.internal.core.search.indexing.IndexManager$1.execute(IndexManager.java:989) at org.eclipse.jdt.internal.core.search.processing.JobManager.run(JobManager.java:394) at java.lang.Thread.run(Thread.java:745) The loop is entirely within findSuperTypeOriginatingFrom. It is traversing the supertype hierarchy, and gets stuck in a cycle due to the following bindings which each point to one another as their parent binding: <Z#1-T#2 extends Z#0-T#0> <Z#0-T#0 extends Z#1-T#2 & Comparable<? super Z#1-T#2>> (In reply to Stefan Xenos from comment #2) > The loop is entirely within findSuperTypeOriginatingFrom. It is traversing > the supertype hierarchy, and gets stuck in a cycle due to the following > bindings which each point to one another as their parent binding: > > <Z#1-T#2 extends Z#0-T#0> > <Z#0-T#0 extends Z#1-T#2 & Comparable<? super Z#1-T#2>> Thanks for the analysis. Wow! I'm not even sure such cyclic type variables are forbidden ... As you assigned this to yourself, do you have a strategy for fixing this? > do you have a strategy for fixing this?
No. I just have a need to have it fixed. :-)
I've been reading Section 18 JLS all morning trying to understand the intended behavior better, and was hoping to figure things out from there.
You probably understand Java's type inferencing better than I do, so please feel free to reassign to yourself if you have time to look into this.
To make debugging easier, I've made the example self-contained (no jdk types), renamed all type parameters so they have distinct names and reduced it further:
package makeCompilerFreeze;
interface Comparable<E> {}
interface Function<Q, R> {}
interface Comparator<A> {
public static <B extends Comparable<? super B>> Comparator<B> naturalOrder() {
return null;
}
public static <C, D> Comparator<C> comparing(Function<? super C, ? extends D> f1, Comparator<? super D> f2) {
return null;
}
}
class Stuff {
public static <T, S extends T> Comparator<Iterable<S>> func(Comparator<T> comparator) {
return null;
}
}
public class EclipseJava8Bug {
static final Comparator<Object> BORKED =
Comparator.comparing(null, Stuff.func(Comparator.naturalOrder()));
}
With these names the cycle is:
<Z#1-T#0 extends Z#0-B#2>
<Z#0-B#2 extends Z#1-T#0 & Comparable<? super Z#0-B#2>>
Further reduced:
package makeCompilerFreeze;
interface Comparable<E> {}
interface Comparator<A> {
public static <B extends Comparable<? super B>> Comparator<B> naturalOrder() {
return null;
}
}
class Stuff {
public static <T, S extends T> Comparator<Iterable<S>> func(Comparator<T> comparator) {
return null;
}
}
public class EclipseJava8Bug {
static final Object BORKED =
Stuff.func(Comparator.naturalOrder());
}
bwt, javac says:
makeCompilerFreeze/EclipseJava8Bug.java:20: error: method func in class Stuff cannot be applied to given types;
Stuff.func(Comparator.naturalOrder());
^
required: Comparator<T>
found: Comparator<B>
reason: inferred type does not conform to upper bound(s)
inferred: Object
upper bound(s): Comparable<? super Object>,Object
where T,S,B are type-variables:
T extends Object declared in method <T,S>func(Comparator<T>)
S extends T declared in method <T,S>func(Comparator<T>)
B extends Comparable<? super B>
1 error
I think this is the minimal example. S is not used at all, but if you remove it, the endless loop doesn't happen:
package makeCompilerFreeze;
interface Comparable<E> {}
interface Comparator<A> {
public static <B extends Comparable<? super B>> Comparator<B> naturalOrder() {
return null;
}
}
class Stuff {
public static <T, S extends T> Object func(Comparator<T> comparator) {
return null;
}
}
public class EclipseJava8Bug {
static final Object BORKED =
Stuff.func(Comparator.naturalOrder());
}
New Gerrit change created: https://git.eclipse.org/r/82127 I've attached a patch that seems to fix this specific example. It uses Brent's algorithm to detect cycles in the superclass list and breaks out of the iteration before visiting any class twice. However, after searching for all callers of the superclass() method, it looks like none of the others can handle cycles in the superclass list either. Should this pattern be applied more widely? Or should the cycle not have been there in the first place? FYI, this patch was written with a very limited understanding of the type inferencing algorithm. It looked to me like the findSuperTypeOriginatingFrom method only needed to visit each superclass once and could otherwise tolerate cycles... but I'd really like someone with a deeper understanding of type inferencing to offer their opinion on whether or not tolerating the cycle is appropriate in this case. New Gerrit change created: https://git.eclipse.org/r/82139 (In reply to Eclipse Genie from comment #11) > New Gerrit change created: https://git.eclipse.org/r/82139 Cool! Someone understood that code deep inside the inference engine. And found the tiny mistake hidden inside. Well spotted! I'll quickly amend the patch with a tiny refactoring that should demonstrate why the proposed correction is - correct. Bookkeeping: Since we could choose between a broken and a working proposal, I simply removed the review requests, abandoned the failed attempt in gerrit, resubmitted the winning gerrit with my tiny refactoring and assigned to Till. Thanks. > I simply removed the review requests, abandoned the failed attempt in gerrit,
No worries. Thanks for looking at this, Till.
(In reply to Stephan Herrmann from comment #12) > (In reply to Eclipse Genie from comment #11) > > New Gerrit change created: https://git.eclipse.org/r/82139 > > Cool! Someone understood that code deep inside the inference engine. > And found the tiny mistake hidden inside. > Well spotted! > Thanks for the nice words. The inference engine is really impressive. In case you wondered why the commit is dated March, 21, 2016: I came across that code when I looked if I can find a solution for what is now bug 493151. I suspected it was wrong and made an experimental fix in a branch, but could not construct an example that led to an observable bug, and was busy with other bugs, so I forgot about it. When I stepped throught the code for this bug, it felt familiar and I found my experimental fix. Next time I'll file a bug immediately if I see something like that :-) > I'll quickly amend the patch with a tiny refactoring that should demonstrate > why the proposed correction is - correct. Good! Gerrit change https://git.eclipse.org/r/82139 was merged to [master]. Commit: http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/?id=372105883c90f57f2c7a8992de070fba3f4f7974 (In reply to Eclipse Genie from comment #16) > Gerrit change https://git.eclipse.org/r/82139 was merged to [master]. > Commit: > http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/ > ?id=372105883c90f57f2c7a8992de070fba3f4f7974 Released for 4.7M3 Verified for 4.7 M3 with build I20161024-2000 I am hit by this also, compilation reproducibly locks up for a large project in one specific package. The same code is compiled fine in CI by JDK and locally by IntelliJ, so I cannot use Eclipse any longer for that project. Is there any way to get this fix earlier than with 4.7 which is due only in July 2017? Proposing for 4.6.3, the mistake is obvious, the effect is really bad and the fix is straight forward. If people insist, we _could_ even ship this with 4.6.2 RC3. New Gerrit change created: https://git.eclipse.org/r/85227 (In reply to Eclipse Genie from comment #21) > New Gerrit change created: https://git.eclipse.org/r/85227 Gerrit for a possible backport (now or later) (In reply to Stephan Herrmann from comment #20) > Proposing for 4.6.3, the mistake is obvious, the effect is really bad and > the fix is straight forward. +1 > > If people insist, we _could_ even ship this with 4.6.2 RC3. (In reply to Dominik Stadler from comment #19) > I am hit by this also, compilation reproducibly locks up for a large project > in one specific package. The same code is compiled fine in CI by JDK and > locally by IntelliJ, so I cannot use Eclipse any longer for that project. > > Is there any way to get this fix earlier than with 4.7 which is due only in > July 2017? If we backport this: Neon.3 (4.6.3) will be out in March 23, 2017. Maybe you could use 4.7 M3? (In reply to Stephan Herrmann from comment #20) > Proposing for 4.6.3, the mistake is obvious, the effect is really bad and > the fix is straight forward. > > If people insist, we _could_ even ship this with 4.6.2 RC3. Agree, it will be good to have this in 4.6.2 itself. Requesting PMC to approve this change for RC3. (In reply to Jay Arthanareeswaran from comment #24) > (In reply to Stephan Herrmann from comment #20) > Requesting PMC to approve this change for RC3. +1 reopened for back port to 4.6.2 Gerrit change https://git.eclipse.org/r/85227 was merged to [R4_6_maintenance]. Commit: http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/?id=0cdebe3b9ca49ce7d54cc31b9fee2a075a55b264 (In reply to Eclipse Genie from comment #27) > Gerrit change https://git.eclipse.org/r/85227 was merged to > [R4_6_maintenance]. > Commit: > http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/ > ?id=0cdebe3b9ca49ce7d54cc31b9fee2a075a55b264 Released for 4.6.2 Verified for 4.6.2 with build M20161122-0800 |
Create the following class, turn on autobuild, and observe that the compiler and indexer get stuck in an infinite loop: package makeCompilerFreeze; import java.util.Collection; import java.util.Comparator; class Stuff { public static <T, S extends T> Comparator<Iterable<S>> func(Comparator<T> comparator) { return null; } } public class EclipseJava8Bug { class Thing { Collection<Object> getStuff() { return null; } } static final Comparator<Thing> BORKED = Comparator.comparing(Thing::getStuff, Stuff.func(Comparator.naturalOrder())); }