[java] Huge max-k in d=39 classBodyDeclaration while parsing ManyStringsConcat.java

[kaby76]

The ManyStringsConcat.java example brings to light a large max-k when parsing a classBodyDeclaration for the input starting at @ApiModelProperty(value.... The decision that AdaptivePredict() is trying to find is d=39.

The definition of classBodyDeclaration, which is loosely derived from the JLS 24, is the following.

grammars-v4/java/java/JavaParser.g4

Lines 142 to 146 in a5754dd

	classBodyDeclaration
	: ';'
	| STATIC? block
	| modifier* memberDeclaration
	;

The parser requires 3611 tokens to resolve the decision, and accounts for the majority of the time to parse the file.

Reading the source code of the javac parser, we see that this is not the grammar that the parser implements.

https://github.com/openjdk/jdk/blob/166ef5e7b1c6d6a9f0f1f29fedb7f65b94f53119/src/jdk.compiler/share/classes/com/sun/tools/javac/parser/JavacParser.java#L4721-L4782

[kaby76]

The problem becomes apparent if you remove modifier* from the alt | modifier* memberDeclaration and then parse this:

class Test
{
    @ApiModelProperty(value = "x")
    @XmlElement
    AdditionalParams additionalParams;
}

We see that it parses. That means there is some common parsing element between modifier and memberDeclaration. In fact, it's annotation, which you can see from the parse tree.

compilationUnit
├── typeDeclaration
│   └── classDeclaration
│       ├── CLASS
│       │   └── "class"
│       ├── identifier
│       │   ├── Attribute WS Value ' ' chnl:HIDDEN
│       │   └── IDENTIFIER
│       │       └── "Test"
│       └── classBody
│           ├── Attribute WS Value '\r\n' chnl:HIDDEN
│           ├── LBRACE
│           │   └── "{"
│           ├── classBodyDeclaration
│           │   └── memberDeclaration
│           │       └── fieldDeclaration
│           │           ├── typeType
│           │           │   ├── annotation
│           │           │   │   ├── Attribute WS Value '\r\n    ' chnl:HIDDEN
│           │           │   │   ├── AT
│           │           │   │   │   └── "@"
│           │           │   │   ├── qualifiedName
│           │           │   │   │   └── identifier
│           │           │   │   │       └── IDENTIFIER
│           │           │   │   │           └── "ApiModelProperty"
│           │           │   │   └── annotationFieldValues
│           │           │   │       ├── LPAREN
│           │           │   │       │   └── "("
│           │           │   │       ├── annotationFieldValue
│           │           │   │       │   ├── identifier
│           │           │   │       │   │   └── IDENTIFIER
│           │           │   │       │   │       └── "value"
│           │           │   │       │   ├── Attribute WS Value ' ' chnl:HIDDEN
│           │           │   │       │   ├── ASSIGN
│           │           │   │       │   │   └── "="
│           │           │   │       │   └── annotationValue
│           │           │   │       │       └── expression
│           │           │   │       │           └── primary
│           │           │   │       │               └── literal
│           │           │   │       │                   ├── Attribute WS Value ' ' chnl:HIDDEN
│           │           │   │       │                   └── STRING_LITERAL
│           │           │   │       │                       └── "\"x\""
│           │           │   │       └── RPAREN
│           │           │   │           └── ")"
│           │           │   ├── annotation
│           │           │   │   ├── Attribute WS Value '\r\n    ' chnl:HIDDEN
│           │           │   │   ├── AT
│           │           │   │   │   └── "@"
│           │           │   │   └── qualifiedName
│           │           │   │       └── identifier
│           │           │   │           └── IDENTIFIER
│           │           │   │               └── "XmlElement"
│           │           │   └── classOrInterfaceType
│           │           │       └── classType
│           │           │           └── typeIdentifier
│           │           │               ├── Attribute WS Value '\r\n    ' chnl:HIDDEN
│           │           │               └── IDENTIFIER
│           │           │                   └── "AdditionalParams"
│           │           ├── variableDeclarators
│           │           │   └── variableDeclarator
│           │           │       └── variableDeclaratorId
│           │           │           └── identifier
│           │           │               ├── Attribute WS Value ' ' chnl:HIDDEN
│           │           │               └── IDENTIFIER
│           │           │                   └── "additionalParams"
│           │           └── SEMI
│           │               └── ";"
│           ├── Attribute WS Value '\r\n' chnl:HIDDEN
│           └── RBRACE
│               └── "}"
└── EOF
    └── ""

If you put modifier* back in, the parse tree is:

compilationUnit
├── typeDeclaration
│   └── classDeclaration
│       ├── CLASS
│       │   └── "class"
│       ├── identifier
│       │   ├── Attribute WS Value ' ' chnl:HIDDEN
│       │   └── IDENTIFIER
│       │       └── "Test"
│       └── classBody
│           ├── Attribute WS Value '\n' chnl:HIDDEN
│           ├── LBRACE
│           │   └── "{"
│           ├── classBodyDeclaration
│           │   ├── modifier
│           │   │   └── classOrInterfaceModifier
│           │   │       └── annotation
│           │   │           ├── Attribute WS Value '\n    ' chnl:HIDDEN
│           │   │           ├── AT
│           │   │           │   └── "@"
│           │   │           ├── qualifiedName
│           │   │           │   └── identifier
│           │   │           │       └── IDENTIFIER
│           │   │           │           └── "ApiModelProperty"
│           │   │           └── annotationFieldValues
│           │   │               ├── LPAREN
│           │   │               │   └── "("
│           │   │               ├── annotationFieldValue
│           │   │               │   ├── identifier
│           │   │               │   │   └── IDENTIFIER
│           │   │               │   │       └── "value"
│           │   │               │   ├── Attribute WS Value ' ' chnl:HIDDEN
│           │   │               │   ├── ASSIGN
│           │   │               │   │   └── "="
│           │   │               │   └── annotationValue
│           │   │               │       └── expression
│           │   │               │           └── primary
│           │   │               │               └── literal
│           │   │               │                   ├── Attribute WS Value ' ' chnl:HIDDEN
│           │   │               │                   └── STRING_LITERAL
│           │   │               │                       └── "\"x\""
│           │   │               └── RPAREN
│           │   │                   └── ")"
│           │   ├── modifier
│           │   │   └── classOrInterfaceModifier
│           │   │       └── annotation
│           │   │           ├── Attribute WS Value '\n    ' chnl:HIDDEN
│           │   │           ├── AT
│           │   │           │   └── "@"
│           │   │           └── qualifiedName
│           │   │               └── identifier
│           │   │                   └── IDENTIFIER
│           │   │                       └── "XmlElement"
│           │   ├── modifier
│           │   │   └── classOrInterfaceModifier
│           │   │       ├── Attribute WS Value '\n    ' chnl:HIDDEN
│           │   │       └── PROTECTED
│           │   │           └── "protected"
│           │   └── memberDeclaration
│           │       └── fieldDeclaration
│           │           ├── typeType
│           │           │   └── classOrInterfaceType
│           │           │       └── classType
│           │           │           └── typeIdentifier
│           │           │               ├── Attribute WS Value ' ' chnl:HIDDEN
│           │           │               └── IDENTIFIER
│           │           │                   └── "AdditionalParams"
│           │           ├── variableDeclarators
│           │           │   └── variableDeclarator
│           │           │       └── variableDeclaratorId
│           │           │           └── identifier
│           │           │               ├── Attribute WS Value ' ' chnl:HIDDEN
│           │           │               └── IDENTIFIER
│           │           │                   └── "additionalParams"
│           │           └── SEMI
│           │               └── ";"
│           ├── Attribute WS Value '\n' chnl:HIDDEN
│           └── RBRACE
│               └── "}"
└── EOF
    └── ""

And, you get multiple parse trees due to ambiguity.

zzz.d=39.a=1: (compilationUnit (typeDeclaration (classDeclaration (CLASS "class") (identifier (IDENTIFIER "Test")) (classBody (LBRACE "{") (classBodyDeclaration (modifier (classOrInterfaceModifier (annotation (AT "@") (qualifiedName (identifier (IDENTIFIER "ApiModelProperty"))) (annotationFieldValues (LPAREN "(") (annotationFieldValue (annotationValue (expression (expression (primary (identifier (IDENTIFIER "value")))) (ASSIGN "=") (expression (primary (literal (STRING_LITERAL "\"x\""))))))) (RPAREN ")"))))) (modifier (classOrInterfaceModifier (annotation (AT "@") (qualifiedName (identifier (IDENTIFIER "XmlElement")))))) (memberDeclaration (fieldDeclaration (typeType (classOrInterfaceType (classType (typeIdentifier (IDENTIFIER "AdditionalParams"))))) (variableDeclarators (variableDeclarator (variableDeclaratorId (identifier (IDENTIFIER "additionalParams"))))) (SEMI ";")))) (RBRACE "}")))) (EOF ""))
zzz.d=39.a=2: (compilationUnit (typeDeclaration (classDeclaration (CLASS "class") (identifier (IDENTIFIER "Test")) (classBody (LBRACE "{") (classBodyDeclaration (memberDeclaration (fieldDeclaration (typeType (annotation (AT "@") (qualifiedName (identifier (IDENTIFIER "ApiModelProperty"))) (annotationFieldValues (LPAREN "(") (annotationFieldValue (annotationValue (expression (expression (primary (identifier (IDENTIFIER "value")))) (ASSIGN "=") (expression (primary (literal (STRING_LITERAL "\"x\""))))))) (RPAREN ")"))) (annotation (AT "@") (qualifiedName (identifier (IDENTIFIER "XmlElement")))) (classOrInterfaceType (classType (typeIdentifier (IDENTIFIER "AdditionalParams"))))) (variableDeclarators (variableDeclarator (variableDeclaratorId (identifier (IDENTIFIER "additionalParams"))))) (SEMI ";")))) (RBRACE "}")))) (EOF ""))
zzz.d=39.a=1: (compilationUnit (typeDeclaration (classDeclaration (CLASS "class") (identifier (IDENTIFIER "Test")) (classBody (LBRACE "{") (classBodyDeclaration (modifier (classOrInterfaceModifier (annotation (AT "@") (qualifiedName (identifier (IDENTIFIER "ApiModelProperty"))) (annotationFieldValues (LPAREN "(") (annotationFieldValue (annotationValue (expression (expression (primary (identifier (IDENTIFIER "value")))) (ASSIGN "=") (expression (primary (literal (STRING_LITERAL "\"x\""))))))) (RPAREN ")"))))) (modifier (classOrInterfaceModifier (annotation (AT "@") (qualifiedName (identifier (IDENTIFIER "XmlElement")))))) (memberDeclaration (fieldDeclaration (typeType (classOrInterfaceType (classType (typeIdentifier (IDENTIFIER "AdditionalParams"))))) (variableDeclarators (variableDeclarator (variableDeclaratorId (identifier (IDENTIFIER "additionalParams"))))) (SEMI ";")))) (RBRACE "}")))) (EOF ""))
zzz.d=39.a=2: (compilationUnit (typeDeclaration (classDeclaration (CLASS "class") (identifier (IDENTIFIER "Test")) (classBody (LBRACE "{") (classBodyDeclaration (modifier (classOrInterfaceModifier (annotation (AT "@") (qualifiedName (identifier (IDENTIFIER "ApiModelProperty"))) (annotationFieldValues (LPAREN "(") (annotationFieldValue (annotationValue (expression (expression (primary (identifier (IDENTIFIER "value")))) (ASSIGN "=") (expression (primary (literal (STRING_LITERAL "\"x\""))))))) (RPAREN ")"))))) (memberDeclaration (fieldDeclaration (typeType (annotation (AT "@") (qualifiedName (identifier (IDENTIFIER "XmlElement")))) (classOrInterfaceType (classType (typeIdentifier (IDENTIFIER "AdditionalParams"))))) (variableDeclarators (variableDeclarator (variableDeclaratorId (identifier (IDENTIFIER "additionalParams"))))) (SEMI ";")))) (RBRACE "}")))) (EOF ""))

How does this compare with java20? The parse tree for this example is:

start_
├── compilationUnit
│   └── ordinaryCompilationUnit
│       └── topLevelClassOrInterfaceDeclaration
│           └── classDeclaration
│               └── normalClassDeclaration
│                   ├── CLASS
│                   │   └── "class"
│                   ├── typeIdentifier
│                   │   ├── Attribute Skip Value ' '
│                   │   └── Identifier
│                   │       └── "Test"
│                   └── classBody
│                       ├── Attribute Skip Value '\n'
│                       ├── LBRACE
│                       │   └── "{"
│                       ├── classBodyDeclaration
│                       │   └── classMemberDeclaration
│                       │       └── fieldDeclaration
│                       │           ├── fieldModifier
│                       │           │   └── annotation
│                       │           │       └── normalAnnotation
│                       │           │           ├── Attribute Skip Value '\n    '
│                       │           │           ├── AT
│                       │           │           │   └── "@"
│                       │           │           ├── typeName
│                       │           │           │   └── packageName
│                       │           │           │       └── identifier
│                       │           │           │           └── Identifier
│                       │           │           │               └── "ApiModelProperty"
│                       │           │           ├── LPAREN
│                       │           │           │   └── "("
│                       │           │           ├── elementValuePairList
│                       │           │           │   └── elementValuePair
│                       │           │           │       ├── identifier
│                       │           │           │       │   └── Identifier
│                       │           │           │       │       └── "value"
│                       │           │           │       ├── Attribute Skip Value ' '
│                       │           │           │       ├── ASSIGN
│                       │           │           │       │   └── "="
│                       │           │           │       └── elementValue
│                       │           │           │           └── conditionalExpression
│                       │           │           │               └── conditionalOrExpression
│                       │           │           │                   └── conditionalAndExpression
│                       │           │           │                       └── inclusiveOrExpression
│                       │           │           │                           └── exclusiveOrExpression
│                       │           │           │                               └── andExpression
│                       │           │           │                                   └── equalityExpression
│                       │           │           │                                       └── relationalExpression
│                       │           │           │                                           └── shiftExpression
│                       │           │           │                                               └── additiveExpression
│                       │           │           │                                                   └── multiplicativeExpression
│                       │           │           │                                                       └── unaryExpression
│                       │           │           │                                                           └── unaryExpressionNotPlusMinus
│                       │           │           │                                                               └── postfixExpression
│                       │           │           │                                                                   └── primary
│                       │           │           │                                                                       └── primaryNoNewArray
│                       │           │           │                                                                           └── literal
│                       │           │           │                                                                               ├── Attribute Skip Value ' '
│                       │           │           │                                                                               └── StringLiteral
│                       │           │           │                                                                                   └── "\"x\""
│                       │           │           └── RPAREN
│                       │           │               └── ")"
│                       │           ├── fieldModifier
│                       │           │   └── annotation
│                       │           │       └── markerAnnotation
│                       │           │           ├── Attribute Skip Value '\n    '
│                       │           │           ├── AT
│                       │           │           │   └── "@"
│                       │           │           └── typeName
│                       │           │               └── packageName
│                       │           │                   └── identifier
│                       │           │                       └── Identifier
│                       │           │                           └── "XmlElement"
│                       │           ├── fieldModifier
│                       │           │   ├── Attribute Skip Value '\n    '
│                       │           │   └── PROTECTED
│                       │           │       └── "protected"
│                       │           ├── unannType
│                       │           │   └── unannReferenceType
│                       │           │       └── unannClassOrInterfaceType
│                       │           │           └── typeIdentifier
│                       │           │               ├── Attribute Skip Value ' '
│                       │           │               └── Identifier
│                       │           │                   └── "AdditionalParams"
│                       │           ├── variableDeclaratorList
│                       │           │   └── variableDeclarator
│                       │           │       └── variableDeclaratorId
│                       │           │           └── identifier
│                       │           │               ├── Attribute Skip Value ' '
│                       │           │               └── Identifier
│                       │           │                   └── "additionalParams"
│                       │           └── SEMI
│                       │               └── ";"
│                       ├── Attribute Skip Value '\n'
│                       └── RBRACE
│                           └── "}"
└── EOF
    └── ""

Unfortunately, we see the same max-k problem over there.