How to implement C++ style templates using Langium

[luan-xiaokun]

Hi guys, I've spent some time lately on parsing C++ style function template, and I'm interested in how to implement this complex feature in Langium, since the language that I'm working on also has this feature.

To be more specific, the C++ style template is complex because:

1. Template function call such as A<B>(C) is ambiguous, as it can also be parsed as a nested comparison (A<B)>(C).
2. Both type and expressions can be passed as a template argument, i.e. the null in foo<null>() can be a constant literal, or can be the null type.

The first type of ambiguity is related to the notation of the template, we can avoid it by changing its notation, such as foo<<<bar>>>. (However, most popular programming languages seem to follow the C++ style generic type notation) The second type of ambiguity is not related to the notation, as long as we can pass both type and expression as a template argument, we have to deal with it.

Here are some ways that I've learned to solve the problem:

1. The ambiguity between template function call and nested comparison is an inherent ambiguity. It's not possible for deterministic parsers like LL/LALR to resolve such ambiguity at the parsing time without relying on context. For example, after knowing the type of A, we may make the decision to solve such ambiguity. As for more powerful (but also less efficient) parsers like GLR/Earley, it's possible to consider all ambiguities at parsing time, and resolve them later.
2. There are several ways to tackle the second issue, as we've already discussed in Distinguishing between type aliases and variable names in templates #741 .
3. PS: Even modern compilers like clang, cannot always get the parse tree the user wants, see this discussion.

I've tried to solve the second issue before by introducing a TypeOrExpression syntax rule that captures anything that looks like a type or an expression and resolving the ambiguity when doing type inference. But I cannot see proper ways to deal with the first issue using Langium.

I know that the syntaxes of TypeScript and C++ are quite different, but as far as I can see, they share the same ambiguities in terms of template function. So when I see @msujew mentioned in #895 that it's possible to implement some complex features of TypeScript in Langium, such as template strings `label: ${value}`, I became really interested in this topic. (I assumed that the template function feature was implemented for TypeScript) Any hints or ideas for using Langium to implement this feature are welcome.

[msujew]

Hey @luan-xiaokun,

thanks for the question! I think this can be solved in theory using multiple different approaches, but I believe the simplest way of achieving this is by manipulating the lexing using positive lookahead in terminal rules. You can take a look at a working example of this in this playground link. The magic mostly lies in the GENERICS_OPEN terminal rule with its positive lookahead. The LESS_THAN is there so that we manually change the ordering of terminal in the lexer. The GENERICS_OPEN needs to have the opportunity to be lexed first, with LESS_THAN being a sort of fallback for the < character.

The pure regex solution isn't as maintainable as I'd hoped it'd be, so I created this PR in hopes of improving that. It would allow to re-use terminals in positive/negative lookahead terminal context.

Also, regarding template strings: You will need a multi-mode lexer for this. I've been meaning to write some documentation on that for some time already, so I should get to it soonish.

[luan-xiaokun]

Thanks for your reply. This solution sounds reasonable, and I'm impressed by the powerful lexer.

If I understand it correctly, this solution will always parse A<X>(Y) as a template function call, instead of a nested comparison (Although it should be rare for someone to write this), right? So I think this approach is not the perfect answer, but it should handle most common cases quite well. That said, if we really want to have a perfect solution, then maybe we'll just end up writing it by hand, which defeats the point of using a parser generator.

[msujew]

Thanks for your reply. This solution sounds reasonable, and I'm impressed by the powerful lexer.

You're welcome :) I'm also quite happy with how the Chevrotain lexer performs. It's both flexible and fast.

That said, if we really want to have a perfect solution, then maybe we'll just end up writing it by hand, which defeats the point of using a parser generator.

Actually, it is almost impossible to get this correct, since it requires way to much semantic information to be available during the parsing phase. Even the handwritten TypeScript parser isn't able to deal with this correctly. See this playground example.

[luan-xiaokun]

Even the handwritten TypeScript parser isn't able to deal with this correctly. See this playground example.

I'm surprised by this. It also makes me think even more that C++ style template is not a good syntax design, and allows me to feel more comfortable not fully supporting this feature in my DSL implementation.

[agacek]

Also, regarding template strings: You will need a multi-mode lexer for this. I've been meaning to write some documentation on that for some time already, so I should get to it soonish.

I would love any documentation or links you have on this. We want to add template strings to our Langium project and I'm muddling through how to wire everything up so it works naturally.

[msujew]

There is a WIP PR for multi mode lexing available over at eclipse-langium/langium-website#132.