microsoft / vscode-textmate

A library that helps tokenize text using Text Mate grammars.
MIT License
580 stars 114 forks source link

Scopes on Recursive Regex Cause Problems #208

Open jeff-hykin opened 1 year ago

jeff-hykin commented 1 year ago

Non-issue example:

Adding scopes to the this capture group (a)+ will only apply the scopes to the last match. While annoying, that behavior is the expected behavior and it's easy enough to work around.

A similar behavior happens with recursion (a)b\g<1>? this can match ababab but only tags the last a with a scope.

The issue

Let's say (a)\g<1>? is trivial recursion (just repetion)
And (basecase|(\[)\g<1>(\])) is basic recursion (balanced square brackets around the word "basecase")

Anything more complex than those, such as adding alternation, dual-recusion, branching recursion, becomes impossible to reliably highlight.

For illustration, applying a balanced parentheses pattern to [[basecase]] would only add scopes to "basecase". And while there might be a hacky way to color the outside brackets, that hack will fall apart as soon as there's a more complex matcher applied to something like [basecase lambda {basecase[basecase][basecase]}]. Only the last basecase will have scopes. It might only be possible to find "lambda" using a recursive pattern, but by using a recursive pattern we are unable to tag the "lambda", because it only adds scopes to the inner most basecase.

TLDR; this is fundamentally limiting, not just an inconvenience that can be worked around.

Not only is the behavior incredibly unintuitve, but add multiple-recusion (e.g. \g<1>|\g<2>) on top of it and it's debatably undefined behavior.

Rare? Well...

Even hello-world tutorials for defining languages (like a BNF grammar) use recursion like this. When defining a syntax it's easy to define it with this kind of recusion, so it's necessary that this work if those languages are ever going to be correctly parsed by textmate.

Requested solution

There are only a handful of textmate grammars that use complex recusion, and the ones that do almost certainly don't expect this behavior. So changing the scoping behavior shouldn't affect anyone negatively regardless of whether or matches the original textmate implementation.

With that in mind, having the FIRST recursive case be given scopes rather than the last basecase should avoid this problem.