issues with a big DSL grammar

[movalz]

I investigate if a change from Xtext to Langium is an option for us. I have used xtext2langium to transform a big Xtext DSL grammar of our company to Langium. The *.xtext grammar file has around 2000 lines of code with many references.

Then I have implemented the ScopeProvider and a small generator and tested it with 111 model files with a total size of around 2.3 MB. The tests are:

• starting a VSCode with the DSL plugin installed and editing model files (esp. code completion and "jump to definition")
• running the generator with one of the model files.

I run into some Langium issues:

1. In Xtext we have used "Optional elements in unordered groups" ((...)? &(...)?). I got the error message "Optional elements in Unordered groups are currently not supported". This is an important feature for us. Are there plans when this feature will be implemented?
2. When the grammar rules are too complex/deep the parser and/or ScopeProvider/linker gets trouble. Example:

entry Model infers Model:
    (imports+=Import)*
    xxToplevel=XxToplevelElement

functions, but when I change it to

entry Model infers Model:
    (imports+=Import)*
    (xxToplevel=XxToplevelElement | (packageElements+=PackageElement)* | dEntity=DEntity)?

(where XxToplevelElement and DEntity are deeply nested rules) I get many, many linker errors. Reducing it to

entry Model infers Model:
    (imports+=Import)*
    (xxToplevel=XxToplevelElement | dEntity=DEntity)?

works better (linkings are successful), but I get a strange parse error: "Expecting token of type ';' but found []." for ... SomeType[];, these errors don't appear in the first (short) version of the entry Model rule.
3. Performance: when the inner VSCode instance opens, it takes about 15 seconds until all model files are loaded and the linkings are done. This isn't very fast but ok. But when editing inside a model file each pressing of CTRL+SPACE for code completion takes 5 to 7 seconds, this makes code completion almost useless. Perhaps caching for all model files which hasn't changed would help?
4. Stack overflow error: when pressing CTRL+SPACE at a certain reference position following error occurrs:

[Error - 15:23:19] Request textDocument/completion failed.
  Message: Request textDocument/completion failed with message: Maximum call stack size exceeded
  Code: -32603

This happens when LangiumCompletionParser.parse(input) calls this.mainRule.call(this.wrapper, {}). I don't know if it's an endless loop or if setting call stack size to a higher value (don't know how to do it) would help.
5. When running the generator the linking isn't done successfully. I get many errors "Could not resolve reference to ...".

We would be very grateful for help in solving these issues.

[msujew]

Hey @movalz,

I got the error message "Optional elements in Unordered groups are currently not supported". This is an important feature for us. Are there plans when this feature will be implemented?

Our unordered groups work a bit differently compared to Xtext's. Using optionality shouldn't be necessary at all, since all unordered groups are optional in Langium. Internally, all Langium does is transform (A & B) into (A | B)*.

When the grammar rules are too complex/deep the parser and/or ScopeProvider/linker gets trouble.

Do you have a reproducible example? It's pretty difficult to tell what goes wrong and where. Generally, the default behavior of the scope provider/linker implementation works differently in Langium compared to Xtext. You might need to perform some adjustments in a specialized ScopeProvider for your language to make it work as expected.

Performance: when the inner VSCode instance opens, it takes about 15 seconds until all model files are loaded and the linkings are done.

15 seconds for 2.3mb sounds indeed rather slow. However, we usually deal with small-ish grammars (less than 500 lines) and parser performance can tank pretty heavily once the amount of alternatives increases. Note that Langium already uses the fastest parser generator available for JavaScript - but at some point we are limited by the runtime.

Have you done any benchmarking yet? At least with most grammars, we usually match Xtext in performance.

But when editing inside a model file each pressing of CTRL+SPACE for code completion takes 5 to 7 seconds, this makes code completion almost useless. Perhaps caching for all model files which hasn't changed would help?

Langium already caches stuff pretty agressively. However, it needs to reparse the file up until the point where the completion is requested. How large are the files in question?

I don't know if it's an endless loop or if setting call stack size to a higher value (don't know how to do it) would help.

The parser is pretty well battle-tested. I assume at some part your grammar is so deeply nested that the runtime just cannot keep up. In theory you can increase this by increasing the stack size when starting the language server by passing the appropriate arguments into the language client.

When running the generator the linking isn't done successfully. I get many errors "Could not resolve reference to ...".

What generator?

[msujew]

When I use (A | B)* instead (A & B) the "unordered" point is solved, but it's possible to specify A or B multiple times, which isn't intended. Furthermore I can't say (A? & B), i.e. "A is optional, B is mandatory, the order doesn't matter"

We usually replace unordered groups with (A | B)* and a validation that exactly tells the user what is missing/invalid. We found that the auto generated syntax error messages that are by created by Antlr/Xtext for unordered groups are pretty nondescript and rarely help identifying and fix the issue.

[movalz]

Concerning the parser issue described in 2.: I have build a small grammar which has the same issue: ScopeProvider isn't called when pressing Ctrl+Space and strange error message "Expecting token of type 'EOF' but found singleTopLevel." is shown at the first token of the model file when there is any mistake inside the model.

grammar ParserIssueBottomUp

entry Model:
    (singleToplevel=SingleToplevelElement | (multiTopLevelElements+=MultiTopLevelElement)*)? ;

SingleToplevelElement:
    'singleTopLevel' '{'
        (children+=SingleTopLevelChild)*
    '}'
;

SingleTopLevelChild:
    'child' name=ID ('friend' friend=[SingleTopLevelChild:ID])?
;

MultiTopLevelElement:
    'multiElement' name=ID;

hidden terminal WS: /\s+/;
terminal ID: /[_a-zA-Z][\w_]*/;

A workaround is to replace (multiTopLevelElements+=MultiTopLevelElement)* by (multiTopLevelElements+=MultiTopLevelElement)+ which is ok because an empty model file doesn't make much sense.

[msujew]

Our parser library chevrotain has trouble with potentially empty alternatives, i.e. the (multiTopLevelElements+=MultiTopLevelElement)* part. I would recommend to refactor this into (A | B)* or using the + like you did. Just to give some context on why the issue appears.

[movalz]

Concerning the performance: I have tried Asynchronous Parsing (like described in .../packages/langium/CHANGELOG.md). This did not reduce the time required to read the files (the thread overhead seems to be higher than the benefit of reading asynchronously). I have done some performance profiling. This shows that the reading/parsing of the 156 model files (with a total size of 3MB) takes around 6% of the total time, the linking of the references (via the ScopeProvider) takes 82% of the total time. So I have implemented caching inside my ScopeProvider (using class WorkspaceCache of packages/langium/src/utils/caching.ts), which reduces the total time extremely: without caching in ScopeProvider the time for reading/linking the 156 model files was 47s, with caching it was 6s. Additionally the caching enhances the performance when editing model files in the inner VSCode: pressing Ctrl+Space for code completion answers in less than 1 second, which is ok.

[msujew]

Yeah, I'm also unhappy with the async parsing - the overhead is pretty big and we might refactor this soon to improve on it.

Glad to hear that you're getting performance improvements out of caching - unoptimized scoping can be quite the performance killer. Its why I recommended doing some profiling in the first place.