Compiler hangs instead of reporting an error if infinitely recursive function is called

[Labadore64]

GWT version: gwt-2.10.0
Browser (with version): N/A
Operating System: Windows 10

---

Description

If there is an infinitely recursive call, it will cause the compiler to hang on permutation 0. There should be an error reported and exiting the compiler. I tested this in Eclipse, version 2022-06 (4.24.0); not sure if it also happens on the command line or in different editors.

Steps to reproduce

Create a method that calls itself infinitely in a loop, and call this method. Code example:

public void methodTest(){
	methodTest();
}

Then compile the GWT project. It will hang on permutation 0.

[jnehlmeier]

This has already been reported against 2.8.2, see #9647

As a workaround you could try setting -optimize 8 GWT compiler parameter which then optimizes the Java AST at most 8 times. By default it is optimized endlessly (which is -optimize 9) until the AST is stable and does not change anymore. This could result in an infinit loop during compilation. As a last resort you can also set the optimization level to zero, which disables AST optimizations.

[niloc132]

Aside from full correctness, is there a reason that this is needed? Recursive methods don't fail in this one, only ones that only call themselves (with no base case, so not actually "recursive", can only result in a stack overflow). Or is there a case where this can fail in normal applications, beyond this simple example case?

I admit I've made this particular mistake before, but typically my IDE is yelling at me for writing nonsense before I've even tabbed over to a browser to try refreshing. I'm certainly not arguing that it shouldn't be fixed, just trying to understand if it happens in more than the degenerate case.

[niloc132]

It looks like this bug is coming from the JsInliner, and I'm currently leaning towards this being a bug introduced by 023151f, specifically 023151f#diff-89bee58f816ba770a5fdd213869c8e639c329afcd379c2e69426f21093119d93L746-L756 where endVisit(JsInvocation, JsContext) used to bail if the function wasn't included in whitelist. Instead, if I'm reasoning about this right, the patch only looks for methods to inline in whitelisted methods, which was not the intent of the whitelist field, at least according to the comments in JsInliner.execImpl even after that patch:

gwt/dev/core/src/com/google/gwt/dev/js/JsInliner.java

Lines 1597 to 1612 in 023151f

	// We are not covering the whole AST, hence we will try to inline functions with a single call
	// site as well as those produced by native methods and their callers.
	SingleInvocationVisitor s = new SingleInvocationVisitor();
	s.accept(program);
	Set<JsNode> candidates = Sets.newLinkedHashSet(toInline);
	candidates.addAll(s.inliningCandidates());
	RedefinedFunctionCollector d = new RedefinedFunctionCollector();
	d.accept(program);
	RecursionCollector rc = new RecursionCollector();
	for (JsNode fn : candidates) {
	rc.accept(fn);
	}
	InliningVisitor v = new InliningVisitor(program, candidates);

My read is that candidates here should be about what might be inlined, not which functions might permit their invocations to be inlined.

This ends up causing the bug, because an earlier patch (which introduced the whitelist to begin with) 7d3ed84 reduced the possible inlinable methods to those which are inline called from a single invocation. A "recursive" method like the one that causes this bug however has two callsites, itself, and the code that would call into it and blow the stack. Attempting to inline the call into this function seems to succeed, but results in an identical caller. Example:

function a() {
  //do other things
  b();
}
function b() {
  b();
}

Roughly, a is marked as changed since b() was inlined, but the result of inlining b() is "the same". It is an error to replace a node with itself, but not an error to replace a node with another node instance that just happens to have the same contents... I'm going to spend a little more time with those two patches and other "recent" changes to see if I can hopefully distill what was intended, and how we can avoid this case.

Also, TIL about gwt.jsinlinerMaxFnSize, gwt.jsinlinerRatio, and gwt.jsinlinerInliningBias - once upon a time there was a page at code.google.com that documented all/most of the system properties that would let you fine tune GWT, but I don't think these ever made the list.

[cueman]

On the question of "is this needed" - I just fell into this trap. A stupid mistake of a one-line method that called itself instead of an overloaded method. It wasn't called while using super dev mode (the bug doesn't show up with no optimisation), and then failed when transpiling in production mode. It was relatively painful for me to find it because it was quite a few commits in the past, and the compiler gives no clues as to where to look, or what the problem might be.

[niloc132]

@cueman understood, but it still needs someone to spend some hours working on it. The point about "is this needed" hits a few different thoughts:

• your IDE didn't yell at you for writing this, maybe ask why not, is that in a class of bugs it should highlight right away (intellij ultimate can highlight this as broken as soon as you write it)
  

• your java compiler didn't yell at you for writing this (see https://errorprone.info/ for a plugin to javac that will catch this and many more bugs, and prevent compiling at all, and https://errorprone.info/bugpattern/InfiniteRecursion for the specific failure you will get)

• we can work around this if needed, if there is a real reason that it should exist.

As in my comment from June 23, I agree that while a compiler shouldn't break in this way, there is also no reasonable reason to write this code. I would like to see a fix - do you have time to explore the linked code above, or sponsor someone to do so?

My hunch is that JsInliner.InliningVisitor.process(...) or its caller, JsInliner.InliningVisitor.endVisit(JsInvocation,JsContext) should be able to test the old vs new expression for equality - and if equal, reject the replacement. It might not be this simple (likely, since I didn't fix it so quickly the last time I looked at it), and it will certainly require tests to validate this. It also might not be straightforward to compare the expressions themselves, or it could be possible to parameterize the call such that they no longer match after inlining (though I'm struggling to imagine how - but if we think this is worth fixing, it is worth entirely fixing).

[niloc132]

I've been looking more into this, and the code is really unclear to me - there is definitely a bug in JsInliner, and the comments and param naming is inconsistent with what the code actually does.

To start with, JsInliner.exec() takes two params - the JsProgram to optimize, and a Collection<JsNode> named toInline - that name implies to me that these are nodes (mostly functions?) that should be inlined if possible.

Those nodes come from CollectJsFunctionsForInlining (if incremental compilation is disabled), and is only computed once, even if the js optimization loop continues.

gwt/dev/core/src/com/google/gwt/dev/jjs/impl/GenerateJavaScriptAST.java

Lines 2746 to 2750 in 2b6f856

	private class CollectJsFunctionsForInlining extends JVisitor {
	// JavaScript functions that arise from methods that were not inlined in the Java AST
	// NOTE: We use a LinkedHashSet to preserve the order of insertion. So that the following passes
	// that use this result are deterministic.

gwt/dev/core/src/com/google/gwt/dev/jjs/impl/GenerateJavaScriptAST.java

Lines 2781 to 2784 in 2b6f856

	// These are either: 1) callsites to JSNI functions, in which case MethodInliner did not
	// attempt to inline; 2) inserted by normalizations passes AFTER all inlining or 3)
	// calls to methods annotated with @ForceInline that were not inlined by the simple
	// MethodInliner.

So to rephrase, this collects all JS Functions where the function contains a call to a JSNI method (which cannot be inlined by the java inliner pass), calls to functions created after the java inliner pass, calls to un-inlined functions marked with @ForceInline, and any JSNI method where its own body contains a function declaration. However, this means that these nodes themselves will not necessarily be inlined, just that one of their calls might be.

JsInliner's private execImpl function then takes toInline (which would better be named something like toInlineInto), copies it into a new set candidates, and also uses SingleInvocationVisitor to discover any function which is called in exactly one location.

gwt/dev/core/src/com/google/gwt/dev/js/JsInliner.java

Lines 1604 to 1612 in 2b6f856

	private static OptimizerStats execImpl(JsProgram program, Collection<JsNode> toInline) {
	OptimizerStats stats = new OptimizerStats(NAME);
	// We are not covering the whole AST, hence we will try to inline functions with a single call
	// site as well as those produced by native methods and their callers.
	SingleInvocationVisitor s = new SingleInvocationVisitor();
	s.accept(program);
	Set<JsNode> candidates = Sets.newLinkedHashSet(toInline);
	candidates.addAll(s.inliningCandidates());

Methods called exactly once are an excellent candidate to be inline (rather than have methods inlined into them) since if this can be done safely, we remove the overhead of the function(){...} wrapping. The code/comments aren't terrible clear, but inliningCandidates doesnt return the function that was called once, but the one function that called it.

Next, we exclude certain functions from themselves being inlined:

gwt/dev/core/src/com/google/gwt/dev/js/JsInliner.java

Lines 1614 to 1624 in 2b6f856

	RedefinedFunctionCollector d = new RedefinedFunctionCollector();
	d.accept(program);
	RecursionCollector rc = new RecursionCollector();
	for (JsNode fn : candidates) {
	rc.accept(fn);
	}
	InliningVisitor v = new InliningVisitor(program, candidates);
	v.blacklist(d.getRedefined());
	v.blacklist(rc.getRecursive());

Here we exclude from being inlined any function that calls itself, and any function that is defined more than once. In theory, that first check should prevent the bug here - "recursive" functions shouldn't ever be inlined.

But this isn't quite right - the recursion collector is only running on functions that should have other functions inlined into them. The visitor (rightly, I think) doesn't descend into referenced functions and explore from there, so unless the recursive function was declared inside the toInlineInto function, it won't be noticed.

Since it isn't noticed, it isn't added to the "never inline this" collection, so the function is inlined as the pass proceeds. If you inline invocation a() where a is defined as function a() { a() }, you end up with the same output, just a(), so the compiler observes that a small change was made, and tries again, with the same result.

The fix then appears to be to run the RecursionCollector on the entire program, so we can never miss a recursive function. The comments do discuss mutually-recursive functions, but (correctly IMHO) rules them out as being a problem since the first inline attempt will potentially inline one or the other (or both), and the resulting function(s) then will be self-recursive, and the loop will stop.

This seems to fix my contrived example, and doesn't appear to fail related tests.