Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Maximum call stack size exceeded when using many optional groups #775

Closed
dhuebner opened this issue Nov 23, 2022 · 8 comments · Fixed by #1473
Closed

Maximum call stack size exceeded when using many optional groups #775

dhuebner opened this issue Nov 23, 2022 · 8 comments · Fixed by #1473
Labels
bug Something isn't working grammar Grammar language related issue types Types related issue

Comments

@dhuebner
Copy link
Contributor

Langium version: current master

When using many optional groups collectInferredTypes (inferred-types.ts Line: 184) creates many different types. Currently it seems like 2ⁿ where n is number of optional groups.

With the node v14 and 17 optional groups a "RangeError" error is thrown. Below is a example grammar for testing:

grammar Test

entry Model:
    (title1=INT ';')?
    (title2=INT ';')?
    (title3=INT ';')?
    (title4=INT ';')?
    (title5=INT ';')?
    (title6=INT ';')?
    (title7=INT ';')?
    (title8=INT ';')?
    (title9=INT ';')?
    (title10=INT ';')?
    (title11=INT ';')?
    (title12=INT ';')?
    (title13=INT ';')?
    (title14=INT ';')?
    (title15=INT ';')?
    (title16=INT ';')?
    (title17=INT ';')?
    /* 
    (title18=INT ';')?
    (title19=INT ';')?
    (title20=INT ';')?
    (title21=INT ';')?
    (title22=INT ';')?
    (title23=INT ';')?
    (title24=INT ';')?
    (title25=INT ';')?
    (title26=INT ';')?
    */
;
terminal INT returns number: ('0'..'9')+;
@dhuebner dhuebner added bug Something isn't working grammar Grammar language related issue labels Nov 23, 2022
@pluralia pluralia added the types Types related issue label Nov 23, 2022
@msujew msujew added this to the v1.0.0 milestone Dec 7, 2022
@spoenemann spoenemann removed this from the v1.0.0 milestone Dec 16, 2022
@tavoda
Copy link

tavoda commented Apr 25, 2024

Hello, is somebody working on this? Without this you can't use langium for any serious grammar.

@dhuebner dhuebner added types Types related issue and removed types Types related issue labels Apr 25, 2024
@msujew
Copy link
Contributor

msujew commented Apr 25, 2024

@tavoda I've provided a fix. We'll probably soon release a version 3.0.1 that contains this fix.

Without this you can't use langium for any serious grammar.

Note that I would strongly disagree with this. We're working quite intensively with Langium and designed some pretty "serious grammars", and so far the only time we've encountered this issue was when we migrated a legacy grammar from Xtext to Langium, which we needed to rewrite anyway.

@tavoda
Copy link

tavoda commented Apr 26, 2024

@msujew thanks for fix. How I can rewrite such rules? This is of course old XText project which I would like to port but I don't see other options. Please check e.g. DslAttribute:
https://github.com/sculptor/sculptor/blob/f57ce67563f1ffa0a6a52d1ea81ad14dbe31b8e7/sculptor-eclipse/org.sculptor.dsl/src/org/sculptor/dsl/Sculptordsl.xtext#L336
You don't support reordered optional parameters, I can live without this but how to migrate this grammar?

@msujew
Copy link
Contributor

msujew commented Apr 27, 2024

@tavoda I'd rewrite all these <key> = <value> mappings using a new rule:

DslAttribute :
  (doc=STRING)?
  (visibility=DslVisibility)? (collectionType=DslCollectionType"<")? type=DslType (">")? name=ID
    (properties+=DslAttributeProperty)*
  (";")?;

DslAttributeProperty: NOT ref=[PropertyDefinition:ID] | ref=[PropertyDefinition:ID] ('=' value=Literal)?;
...
PropertyDefinition: name=ID ':' type=Type;

These PropertyDefinition elements are part of a standard library delivered with your language. Everything else is handled via type based validation rules and cross references. That how we design most languages nowadays which contain a lot of structural data.

@tavoda
Copy link

tavoda commented Apr 29, 2024

It's just moving syntactical rules to semantic layer. For me BNF rules are exactly for this purpose to express as much as possible in syntax. We can rewrite nearly whole grammar (and all C like grammars) to:
CLikeGramars: NOT ref=[PropertyDefinition:ID] | ref=[PropertyDefinition:ID] ('=' value=Literal)? | Punct | String;
Punct: /\b[!#$%&()*+,-./:;<=>?@[\]^_{\|}~]\b/
That is not purpose of parser because than you degrade it to tokenizer.
Thanks again for fix, looking forward to test it.

@msujew
Copy link
Contributor

msujew commented Apr 29, 2024

For me BNF rules are exactly for this purpose to express as much as possible in syntax.

IMO there's a big difference in BNF purely for parsing (i.e. something like a compiler) compared to editing (e.g. Xtext or Langium). In our experience (i.e. at TypeFox), the parser for an editor should allow a lot of "invalid" input, which is then validated against a set of known rules. This serves two purposes:

  1. You usually get way better error recovery/messages from the parser when being a bit more flexible with your language.
  2. Error messages can be way better compared to auto-generated syntax errors (both in regards to incorrectly typed property names as well as the value assigned to it).

With that in mind, I think my suggestion serves that grammar better than just embedding all that information into the grammar directly. No offense here, that's exactly what I did when I started out with Xtext. But in my experience, making things more flexible usually leads to a better product/end result.

That is not purpose of parser because then you degrade it to tokenizer.

It's honestly pretty difficult to tell what the purpose of a parser is. To some, it's just validating some string input. Others want a visitor like pattern, that allows them to tell which rule/part of a rule has been called. This is usually the academic perspective. Some even want a full AST. We serve the last requirement together with all the editing and linking services.

@tavoda
Copy link

tavoda commented Apr 29, 2024

Yes, I'm more on AST side ;-).
After you explanation I see. For editor is better to have your approach with validation on semantic layer.

@snarkipus
Copy link
Contributor

snarkipus commented May 5, 2024

IMO there's a big difference in BNF purely for parsing (i.e. something like a compiler) compared to editing (e.g. Xtext or Langium). In our experience (i.e. at TypeFox), the parser for an editor should allow a lot of "invalid" input, which is then validated against a set of known rules. This serves two purposes:

  1. You usually get way better error recovery/messages from the parser when being a bit more flexible with your language.
  2. Error messages can be way better compared to auto-generated syntax errors (both in regards to incorrectly typed property names as well as the value assigned to it).

This is such a great take. While immediately obvious to some, this realization took me a while to grasp, but it fundamentally changed how I think about tooling in general.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working grammar Grammar language related issue types Types related issue
Projects
None yet
Development

Successfully merging a pull request may close this issue.

6 participants