ECJ hangs when pattern matching code is used in a nested conditional expression.

[ValeryKomarov]

Hello.

I'm from PVS-Studio LLC. We develop a static analyzer for Java code that uses the Spoon library (we use the 10.3.0 version). Spoon uses your org.eclipse.jdt.core 3.32.0 library.

Reproduction of hang

When such code is evaluated via Spoon (a compliance level equal to 17 is used):

public class Main {
    static class PvsVariable {
    }

    static class PvsVariableNext_1 extends PvsVariable {
    }

    static class PvsVariableNext_2 extends PvsVariableNext_1 {
    }

    static class PvsVariableNext_3 extends PvsVariableNext_2 {
    }

    static class PvsVariableNext_4 extends PvsVariableNext_3 {
    }

    public static void main(String[] args) {
        final var pvsVariable = new PvsVariable();
        final Object origVar =
                pvsVariable instanceof PvsVariableNext_1 var_first
                    ? null
                    : (pvsVariable instanceof PvsVariableNext_2 var_second && 
                       pvsVariable instanceof PvsVariableNext_3 var_three && 
                       true) ? null
                                : null;
    }
}

the org.eclipse.jdt.internal.compiler.ast.Statement class hangs on a method:

The method on which the hang occurs

private LocalVariableBinding[] addPatternVariables(LocalVariableBinding[] current, LocalVariableBinding add) {
	int oldSize = current.length;
	// it's odd that we only look at the last element, but in most cases
	// we will only have one in the array. In the unlikely case of having two
	// distinct pattern variables, the cost is nothing but setting the same
	// bit twice on the same object.
	if (oldSize > 0 && current[oldSize - 1] == add) {
		return current;
	}
	int newLength = current.length + 1;
	System.arraycopy(current, 0, (current = new LocalVariableBinding[newLength]), 0, oldSize);
	current[oldSize] = add;
	return current;
}

The code in the latest version of the org.eclispe.jdt.core library is the same as here.

StackTrace hangs

Here is a StackTrace of the hang:

at org.eclipse.jdt.internal.compiler.ast.Statement.addPatternVariables(Statement.java:522)
        at org.eclipse.jdt.internal.compiler.ast.Statement.addPatternVariables(Statement.java:507)
        at org.eclipse.jdt.internal.compiler.ast.Statement.addPatternVariablesWhenTrue(Statement.java:495)
        at org.eclipse.jdt.internal.compiler.ast.AND_AND_Expression.collectPatternVariablesToScope(AND_AND_Expression.java:284)
        at org.eclipse.jdt.internal.compiler.ast.AND_AND_Expression.collectPatternVariablesToScope(AND_AND_Expression.java:281)
        at org.eclipse.jdt.internal.compiler.ast.ConditionalExpression.collectPatternVariablesToScope(ConditionalExpression.java:460)
        at org.eclipse.jdt.internal.compiler.ast.ConditionalExpression.resolveType(ConditionalExpression.java:535)
        at org.eclipse.jdt.internal.compiler.ast.ConditionalExpression.resolveType(ConditionalExpression.java:546)
        at org.eclipse.jdt.internal.compiler.ast.LocalDeclaration.resolve(LocalDeclaration.java:390)
        at org.eclipse.jdt.internal.compiler.ast.LocalDeclaration.resolve(LocalDeclaration.java:259)
        at org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements(AbstractMethodDeclaration.java:662)
        at org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements(MethodDeclaration.java:388)
        at org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(AbstractMethodDeclaration.java:571)
        at org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(TypeDeclaration.java:1503)
        at org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(TypeDeclaration.java:1628)
        at org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve(CompilationUnitDeclaration.java:667)
        at spoon.support.compiler.jdt.TreeBuilderCompiler.buildUnits(TreeBuilderCompiler.java:105)
        at spoon.support.compiler.jdt.JDTBatchCompiler.getUnits(JDTBatchCompiler.java:282)
        at spoon.support.compiler.jdt.JDTBasedSpoonCompiler.buildUnits(JDTBasedSpoonCompiler.java:418)
        at spoon.support.compiler.jdt.JDTBasedSpoonCompiler.buildUnitsAndModel(JDTBasedSpoonCompiler.java:370)
        at spoon.support.compiler.jdt.JDTBasedSpoonCompiler.buildSources(JDTBasedSpoonCompiler.java:336)
        at spoon.support.compiler.jdt.JDTBasedSpoonCompiler.build(JDTBasedSpoonCompiler.java:117)
        at spoon.support.compiler.jdt.JDTBasedSpoonCompiler.build(JDTBasedSpoonCompiler.java:100)
        at spoon.Launcher.buildModel(Launcher.java:782)
        at com.pvsstudio.projects.Module.build(Module.java:428)
        at com.pvsstudio.runner.ModuleModelBuilder.createModuleWorkerWithBuiltModelAndAnalyzeTasksForModule(ModuleModelBuilder.java:136)
        at com.pvsstudio.runner.AnalyzerRunner.run(AnalyzerRunner.java:93)
        at com.pvsstudio.Main.main(Main.java:575)

Possible edit

I think you could edit the code of the method that is up the call stack in such a way. It would help avoid the hang on the code above:

private LocalVariableBinding[] addPatternVariables(LocalVariableBinding[] current, LocalVariableBinding[] add) {
    if (add == null || add.length == 0)
       return current;
    if (current == null || Arrays.equals(current, add)) {        // the edit: || Arrays.equals
       current = add;
    } else {
       for (LocalVariableBinding local : add) {
          current = addPatternVariables(current, local);
       }
    }
    return current;
}

The hang occurs due to the fact that the current parameter and the add parameter contain a reference to the same array when the last statement is called in the org.eclipse.jdt.internal.compiler.ast.AND_AND_Expression.collectPatternVariablesToScope method.

Additional questions

I would also like to know: how do I build org.eclipse.jdt.core 3.32.0? I would like to edit the org.eclipse.jdt.core source code for the 3.32.0 version and build the library, so we can use it in our Spoon branch on Github .

I checked out to the fe90c2cce150ba4fcadeee10f32bcab0a7f29969 commit (the 4.26 release version is specified in its message). However, when trying to build the library, the plugins from the org.eclipse.tycho group version 4.0.0-SNAPSHOT are not in the repository - https://repo.eclipse.org/content/repositories/eclipse/

I need this specific version because we use Spoon 10.3.0, and this version of Spoon uses org.eclipse.jdt.core 3.32.0.

[ValeryKomarov]

Here is an edit to the org.eclipse.jdt.internal.compiler.ast.Statement.addPatternVariables(LocalVariableBinding[] current, LocalVariableBinding[] add) method, which finally helped to deal with the hang in org.eclipse.jdt.core 3.32.0 lib when analyzing the IntelliJ IDEA source code using PVS-Studio (edits are only in beta for now):

private LocalVariableBinding[] addPatternVariables(LocalVariableBinding[] current, LocalVariableBinding[] add) {
    if (add == null || add.length == 0)
        return current;
    if (current == null || Arrays.equals(current, add)) {            // the edit: || Arrays.equals
        current = add;
    } else {
        final Set<LocalVariableBinding> localSet = new HashSet<LocalVariableBinding>(List.of(current));          // the edit
        for (LocalVariableBinding local : add) {
            if (!localSet.contains(local)) {          // the edit
                current = addPatternVariables(current, local);
            }
        }
    }
    return current;
}

[srikanth-sankaran]

I'll propose an alternate fix. The core issue is that we should be maintaining pattern variables in a Set as opposed to an array. While debugging the test case above, I encounter situations like this below for the return value current of the method org.eclipse.jdt.internal.compiler.ast.Statement.addPatternVariables(LocalVariableBinding[], LocalVariableBinding[])

[sealed X.PvsVariableNext_2 var_second[pos: 0][id:4], sealed X.PvsVariableNext_3 var_three[pos: 0][id:5], sealed X.PvsVariableNext_2 var_second[pos: 0][id:4], sealed X.PvsVariableNext_3 var_three[pos: 0][id:5], sealed X.PvsVariableNext_2 var_second[pos: 0][id:4], sealed X.PvsVariableNext_3 var_three[pos: 0][id:5], sealed X.PvsVariableNext_2 var_second[pos: 0][id:4], sealed X.PvsVariableNext_3 var_three[pos: 0][id:5], sealed X.PvsVariableNext_2 var_second[pos: 0][id:4], sealed X.PvsVariableNext_3 var_three[pos: 0][id:5], sealed X.PvsVariableNext_2 var_second[pos: 0][id:4], sealed X.PvsVariableNext_3 var_three[pos: 0][id:5]]
sealed X.PvsVariableNext_2 var_second[pos: 0][id:4]
sealed X.PvsVariableNext_3 var_three[pos: 0][id:5]
sealed X.PvsVariableNext_2 var_second[pos: 0][id:4]
sealed X.PvsVariableNext_3 var_three[pos: 0][id:5]
sealed X.PvsVariableNext_2 var_second[pos: 0][id:4]
sealed X.PvsVariableNext_3 var_three[pos: 0][id:5]
sealed X.PvsVariableNext_2 var_second[pos: 0][id:4]
sealed X.PvsVariableNext_3 var_three[pos: 0][id:5]
sealed X.PvsVariableNext_2 var_second[pos: 0][id:4]
sealed X.PvsVariableNext_3 var_three[pos: 0][id:5]
sealed X.PvsVariableNext_2 var_second[pos: 0][id:4]
sealed X.PvsVariableNext_3 var_three[pos: 0][id:5]

That the debug print routine prints sealed is problematic but only a minor annoyance. More importantly see the duplication (multiplication) of the pattern variables.

Changing this is a sizeable refactoring. I will explore maintaining setness while using array instead.

[srikanth-sankaran]

The comment in org.eclipse.jdt.internal.compiler.ast.Statement.addPatternVariables(LocalVariableBinding[], LocalVariableBinding) reads:

int oldSize = current.length;
	// it's odd that we only look at the last element, but in most cases
	// we will only have one in the array. In the unlikely case of having two
	// distinct pattern variables, the cost is nothing but setting the same
	// bit twice on the same object.
	if (oldSize > 0 && current[oldSize - 1] == add) {
		return current;
	}

but that is not quite so. We don't set the same bit twice - we end up duplicating the pattern binding. The array current's length keep increasing monotonically and we hang.

The reason I don't like the Arrays.equals() approach is because the order of elements may differ while as a set they may be equal - if that were possible the problem would resurface.

[ValeryKomarov]

As I understand, the comment you referred to was added before Pattern Matching was extended in Java, so this limitation is most likely no longer relevant.

I used Arrays.equals to cut out the simplest cases (in my simple examples, Arrays.equals was enough in most cases). In order not to create a HashSet for each case, wasting memory.

In more complex situations (for example, in the case of different orders of array elements), I just used HashSet in the else branch. This is exactly what happened when analyzing the code of the private void invoke(@NotNull PsiExpression initializer) method from the RemoveInitializerFix class of the project intellij-community with the PVS-Studio analyzer. We wrote a short article about the analysis of intellij-community project and made a Pull Request for it.

[srikanth-sankaran]

As I understand, the comment you referred to was added before Pattern Matching was extended in Java, so this limitation is most likely no longer relevant.

FWIW, According to git blame, the comment it's odd that we only look at the last element ... was added for https://bugs.eclipse.org/bugs/show_bug.cgi?id=562824 - [14] Pattern variable with same name as outer local or field is rejected

I used Arrays.equals to cut out the simplest cases (in my simple examples, Arrays.equals was enough in most cases). In order not to create a HashSet for each case, wasting memory.

In more complex situations (for example, in the case of different orders of array elements), I just used HashSet in the else branch.

Do I understand that you maintain a fork where you made such a change ??

This is exactly what happened when analyzing the code of the private void invoke(@NotNull PsiExpression initializer) method from the RemoveInitializerFix class of the project intellij-community with the PVS-Studio analyzer. We wrote a short article about the analysis of intellij-community project and made a Pull Request for it.

Interesting, thanks.

[srikanth-sankaran]

As I understand, the comment you referred to was added before Pattern Matching was extended in Java, so this limitation is most likely no longer relevant.

FWIW, According to git blame, the comment it's odd that we only look at the last element ... was added for https://bugs.eclipse.org/bugs/show_bug.cgi?id=562824 - [14] Pattern variable with same name as outer local or field is rejected

I used Arrays.equals to cut out the simplest cases (in my simple examples, Arrays.equals was enough in most cases). In order not to create a HashSet for each case, wasting memory.
In more complex situations (for example, in the case of different orders of array elements), I just used HashSet in the else branch.

Do I understand that you maintain a fork where you made such a change ??

This is exactly what happened when analyzing the code of the private void invoke(@NotNull PsiExpression initializer) >method from the RemoveInitializerFix class of the project intellij-community with the PVS-Studio analyzer. We wrote a short article about the analysis of intellij-community project and made a Pull Request for it.

Interesting, thanks.

[srikanth-sankaran]

Additional questions

I would also like to know: how do I build org.eclipse.jdt.core 3.32.0? I would like to edit the org.eclipse.jdt.core source code for the 3.32.0 version and build the library, so we can use it in our Spoon branch on Github .

Sorry, this didn't get answered in time. Do you still have the question open ? If so I can request @jarthana or @mpalat to help clarify how to do what you want to do. Thanks.

I checked out to the fe90c2cce150ba4fcadeee10f32bcab0a7f29969 commit (the 4.26 release version is specified in its message). However, when trying to build the library, the plugins from the org.eclipse.tycho group version 4.0.0-SNAPSHOT are not in the repository - https://repo.eclipse.org/content/repositories/eclipse/

I need this specific version because we use Spoon 10.3.0, and this version of Spoon uses org.eclipse.jdt.core 3.32.0.

[ValeryKomarov]

No thanks. We managed to assemble the necessary version (3.32.0) with our modification from our branch.