Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Large if-then-else results in stack overflow in ANTLR parser
Large if-then-else results in stack overflow in ANTLR parser [message #1861427] Thu, 12 October 2023 10:00 Go to next message
Eclipse UserFriend
I have a grammar containing the following rule:

ConditionalExpression returns Expression:
	 {ConditionalExpression} 'if' if=Expression 'then' ifthen=Expression (=>'else' elsethen=Expression)?
;


I have found that a long expression of the form
if True then 42
else if True then 42
else if True then 42
else if True then 42
// repeat ~50 times

sometimes result in a stack overflow exception in the parser, i.e.,
java.lang.StackOverflowError
	at java.base/java.lang.Character.digit(Character.java:9982)
	at java.base/java.lang.Character.digit(Character.java:9930)
	at java.base/java.lang.Integer.parseInt(Integer.java:650)
	at java.base/java.lang.Integer.valueOf(Integer.java:983)
	at org.eclipse.emf.ecore.impl.EcoreFactoryImpl.createEIntFromString(EcoreFactoryImpl.java:656)
	at org.eclipse.emf.ecore.impl.EcoreFactoryImpl.createFromString(EcoreFactoryImpl.java:142)
	at org.eclipse.xtext.conversion.impl.EFactoryValueConverter.toValue(EFactoryValueConverter.java:38)
	at org.eclipse.xtext.conversion.impl.AbstractDeclarativeValueConverterService.toValue(AbstractDeclarativeValueConverterService.java:80)
	at org.eclipse.xtext.parser.DefaultEcoreElementFactory.getTokenValue(DefaultEcoreElementFactory.java:91)
	at org.eclipse.xtext.parser.DefaultEcoreElementFactory.set(DefaultEcoreElementFactory.java:70)
	at org.eclipse.xtext.parser.antlr.AbstractInternalAntlrParser.set(AbstractInternalAntlrParser.java:340)
	at org.eclipse.xtext.parser.antlr.AbstractInternalAntlrParser.set(AbstractInternalAntlrParser.java:348)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleIntLiteral(InternalRosettaParser.java:18946)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleLiteral(InternalRosettaParser.java:18457)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.rulePrimary(InternalRosettaParser.java:31591)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleListOperation(InternalRosettaParser.java:25807)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleBinary(InternalRosettaParser.java:24585)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleMultiplicative(InternalRosettaParser.java:23938)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleAdditive(InternalRosettaParser.java:23632)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleComparison(InternalRosettaParser.java:22639)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleEquality(InternalRosettaParser.java:21796)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleAnd(InternalRosettaParser.java:21280)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleOr(InternalRosettaParser.java:20816)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleConditionalExpression(InternalRosettaParser.java:32398)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.rulePrimary(InternalRosettaParser.java:31525)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleListOperation(InternalRosettaParser.java:25807)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleBinary(InternalRosettaParser.java:24585)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleMultiplicative(InternalRosettaParser.java:23938)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleAdditive(InternalRosettaParser.java:23632)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleComparison(InternalRosettaParser.java:22639)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleEquality(InternalRosettaParser.java:21796)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleAnd(InternalRosettaParser.java:21280)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleOr(InternalRosettaParser.java:20816)
	at com.regnosys.rosetta.parser.antlr.internal.InternalRosettaParser.ruleConditionalExpression(InternalRosettaParser.java:32474)
...


Are there ways to solve this?

A bit more context

Our clients were experiencing crashing language servers when their code contained long if-then-else statements. Upon investigating, I found out that the language server is actually silently swallowing this StackOverflowException, after which it ends up with a Resource with `parseResult` set to `null`. This again results in NullPointerException later whenever a request comes in. I wonder whether the language server should at least log the root cause, rather than silently swallowing it.

A second thing I noticed is that this behaviour is somewhat indeterminate. Running the same repro unit test twice sometimes results in a correct non-null `ParseResult`. I'm not sure why that is.

[Updated on: Thu, 12 October 2023 10:07] by Moderator

Report message to a moderator

Re: Large if-then-else results in stack overflow in ANTLR parser [message #1861428 is a reply to message #1861427] Thu, 12 October 2023 10:05 Go to previous messageGo to next message
Eclipse UserFriend
I have no idea. Maybe you can simply increase Xss as workaround
Re: Large if-then-else results in stack overflow in ANTLR parser [message #1861435 is a reply to message #1861428] Thu, 12 October 2023 12:28 Go to previous messageGo to next message
Eclipse UserFriend
Hmm, I'll try that as a temporary measure, but I am hoping to find a more sustainable solution. I've also added some logging to the language server to make the root cause more obvious.

In the meantime I've noticed another (perhaps worse) problem: when the parsing of such an expression does succeed, the language server will hang on a content assist request.

More precisely, the `ContentAssistContextFactory` will hang seemingly indefinitely on a call to `parser.getFollowElements` (which seems to be called three times as well). Any suggestions to resolve that situation? For now I'll put a timeout in place.

[Updated on: Thu, 12 October 2023 12:30] by Moderator

Report message to a moderator

Re: Large if-then-else results in stack overflow in ANTLR parser [message #1861438 is a reply to message #1861435] Thu, 12 October 2023 13:08 Go to previous messageGo to next message
Eclipse UserFriend
other question: maybe you want to change the grammar to support a swtich statement or something like that
Re: Large if-then-else results in stack overflow in ANTLR parser [message #1861451 is a reply to message #1861438] Fri, 13 October 2023 09:27 Go to previous messageGo to next message
Eclipse UserFriend
Yes, I have been thinking the same. That's probably a longer term solution.
Re: Large if-then-else results in stack overflow in ANTLR parser [message #1861454 is a reply to message #1861451] Fri, 13 October 2023 12:22 Go to previous message
Eclipse UserFriend
I do wonder how other languages such as Haskell handle parsing of large if-then-else expressions. Probably by not using recursive descent in the parser, but rather having a loop? Maybe there is some way of converting the grammer in such as way that the `else` branches are parsed in a loop rather than recursively...

[Updated on: Fri, 13 October 2023 12:23] by Moderator

Report message to a moderator

Previous Topic:compile error: InternalModelingDslParser: too much static variables
Next Topic:How can i disable backtracking ?
Goto Forum:
  


Current Time: Wed Feb 12 17:57:53 GMT 2025

Powered by FUDForum. Page generated in 0.04262 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top