oniguruma-to-es: Edge case handling of duplicate group names with target ES2025

Note: The following details don’t matter when emulating Oniguruma as experienced via vscode-oniguruma. oniguruma-to-es already correctly emulates the subpattern match values and indices as returned by vscode-oniguruma (which are complex to get right for certain edge cases) since vscode-oniguruma (as of v2.0.1) returns subpattern matches by index only, not including group names.


Context: As part of emulation for duplicate group names, oniguruma-to-es strips duplicate group names from all but the first instance. This is necessary since JavaScript prior to ES2025 didn’t support duplicate group names. When not using option avoidSubclass, oniguruma-to-es also transfers in (via handling in EmulatedRegExp) the matched subpattern values and indices on result arrays from later subroutines that reference the group. All of this matches Oniguruma’s behavior and the behavior visible from Onigmo via rubular.com.

For example:

  • (?<n>.)(?<n>.) matched against ab returns a as the value for group n/1, and b as the value for group 2.
  • (?<n>.)\g<n> matched against ab returns b as the value for group n, and has no second capturing group on match results.

Despite being correct, note that none of this is intuitive. In other regex flavors, the subpattern value/index for a duplicate group name is based on the last participating instance. And PCRE/Perl/Regex+ subroutines revert any capturing groups that are set during a subroutine call to their previous values after exiting the subroutine, so subroutines in these regex flavors don’t replace captured values on match results.

Also note that this doesn’t affect backreferenes within the regex. Once again, Oniguruma does something weird here and makes backreferences to duplicate group names match any of the values captured by participating groups with the duplicate name (“backreference multiplexing”), and uses different/complex handling related to subroutines (of course, since Oniguruma seems determined to make no edge cases intuitive or easy to emulate). oniguruma-to-es already emulates all of this correctly.

So, all of the above is already working correctly, despite being weird and complicated.

However, a potential issue arises with oniguruma-to-es’s special handling for duplicate group names with target: 'ES2025' (or target: 'auto' in environments that support ES2025 regex features). For ES2025, oniguruma-to-es’s behavior changes subtly to keep duplicate group names on the first instance per alternation path (since this special case of duplicate group names is no longer an error in JS as of ES2025). So e.g. (?<n>a)(?<n>b)|(?<n>c)(?<n>d) becomes (?<n>a)(b)|(?<n>c)(d).

This is oniguruma-to-es trying to be smart and use the latest features of JS, but it might be introducing an edge case issue in terms of identically copying Oniguruma behavior.

I’m not yet certain, but it seems like the handling for target: 'ES2025' might not follow Oniguruma accurately. vscode-oniguruma doesn’t include capture names for subpattern matches on results, so it doesn’t matter there and I can’t test there. However, rubular.com (which uses Onigmo, a fork of Oniguruma) shows the following results when matching (?<n>a)(?<n>b)|(?<n>c)(?<n>d) against abcd:

Match 1

n/1. a
2. b
3.
4.

Match 2

n/1.
2.
3. c
4. d

The match 2 results above don’t match the results that you’d get for match 2 from JS RegExp behavior when executing the regex generated by oniguruma-to-es with target: 'ES2025':

1.
2.
n/3. c
4. d

JS’s behavior for the match result of subpattern n is 'c' instead of undefined, since it returns the captured value of the group n instance that actually participated in the match.

If rubular.com is indeed showing the behavior of Oniguruma (rather than something specific to Onigmo or rubular.com), this can be fixed by simply dropping oniguruma-to-es’s fancy handling of duplicate group names with target: 'ES2025', and handling it the same as with earlier target values.

About this issue

  • Original URL
  • State: closed
  • Created 2 years ago
  • Comments: 21 (12 by maintainers)

Commits related to this issue

Most upvoted comments

This problem goes beyond the scope of (?W)

Against “ss”

^(?i)\w$          /* search fail */
^(?i)[\w]$        /* Matched (0-2) */

I was partially aware of this, but I’d been trying to forget about it 😜 since it’s a can of worms. However, I’m glad to now be digging into the details – thank you!

So there are two things here: and the inconsistency inside and outside of character classes, and the fancy behavior we’re seeing inside the character class.

  1. Again, I consider the inconsistency of behavior for things like \w inside and outside of character classes to be a long-term bug, even though it probably won’t be fixed.
  2. As for the fancy behavior for allowing characters, character sets, and character classes to expand to match more than one character (as a result of Unicode case folding), I think it was a mistake for Oniguruma to behave this way. Most other regex flavors (including JavaScript) don’t do this, even when they they support Unicode case folding (rather than the simpler case mapping algorithm). I mean, it is a cool feature, and maybe it was based on the Unicode recommendations for regular expressions in UTS 18 (I’m not sure). However, it causes surprises and problems that are probably best avoided. And if you’re not going to implement it consistently anyway, then there are even more problems and IMO it isn’t worth it.

Me ranting at the wind

This comment from kkos helps to make the point:

Therefore, choices for elements other than the character class are generated after the character class. In fact, it would be correct to do the same for .(dot), but this is not done because of the high cost. Since \S is also implemented internally with [\S], it should be the same, but it was not done. I think I simply forgot to do this. It may be best not to change it now.

If the behavior is too slow and/or complicated to be applied consistently, then IMO it shouldn’t have been added.

Also from the issue:

So [\S] is just one of the things that causes problems.

😔 It should not have been acceptable that freezes/crashes occur randomly (from the user’s perspective) when enabling the ignore-case flag (which is very common). That’s especially true since, in exchange for the complexity and performance issues, it doesn’t solve a problem people actually care about.

However, I know that Oniguruma is unlikely to change these longstanding behaviors.

Behavior details

I ran the following tests to try to better understand the behavior. The first value in each array is the regex pattern, and the second is the target string. I’m using r as an alias for JS’s String.raw so that I don’t have to escape backslashes.

✅ = match ❌ = no match 🤔 = inconsistent or questionable behavior 🤯 = very surprising

[
  // Single `s` doesn't map to small sharp s (German eszett, ß) or its case equivalents
  [r`(?i)^s$`, 'ß'], // ❌
  [r`(?i)^s$`, 'ss'], // ❌
  [r`(?i)^[s]$`, 'ß'], // ❌
  [r`(?i)^[s]$`, 'ss'], // ❌
  [r`(?i)^ß$`, 's'], // ❌
  [r`(?i)^[ß]$`, 's'], // ❌

  // Single `s` does map to its case equivalent small long s
  [r`(?i)^s$`, 'ſ'], // ✅

  // Single `ß` maps to `ss` and its case equivalents
  [r`(?i)^ß$`, 'ß'], // ✅
  [r`(?i)^ß$`, 'ss'], // ✅
  [r`(?i)^ß$`, 'SS'], // ✅
  [r`(?i)^ß$`, 'ſſ'], // ✅
  [r`(?i)^ß$`, 'sS'], // ✅
  [r`(?i)^ß$`, 'sſ'], // ✅
  [r`(?i)^ß$`, 'Ss'], // ✅
  [r`(?i)^ß$`, 'Sſ'], // ✅
  [r`(?i)^ß$`, 'ſs'], // ✅
  [r`(?i)^ß$`, 'ſS'], // ✅
  [r`(?i)^ß$`, 'ẞ'], // ✅ Uppercase `ẞ` in target
  [r`(?i)^ẞ$`, 'ß'], // ✅ Uppercase `ẞ` in pattern

  // The same, within a positive class
  [r`(?i)^[ß]$`, 'ß'], // ✅
  [r`(?i)^[ß]$`, 'ss'], // ✅
  [r`(?i)^[ß]$`, 'SS'], // ✅
  [r`(?i)^[ß]$`, 'ſſ'], // ✅
  [r`(?i)^[ß]$`, 'sS'], // ✅
  [r`(?i)^[ß]$`, 'sſ'], // ✅
  [r`(?i)^[ß]$`, 'Ss'], // ✅
  [r`(?i)^[ß]$`, 'Sſ'], // ✅
  [r`(?i)^[ß]$`, 'ſs'], // ✅
  [r`(?i)^[ß]$`, 'ſS'], // ✅
  [r`(?i)^[ß]$`, 'ẞ'], // ✅ Uppercase `ẞ` in target
  [r`(?i)^[ẞ]$`, 'ß'], // ✅ Uppercase `ẞ` in pattern

  // Negated class basics; nothing surprising here
  [r`(?i)^[^ß]$`, 'ß'], // ❌
  [r`(?i)^[^ß]$`, 'ss'], // ❌
  [r`(?i)^[^s]$`, 'ß'], // ✅
  [r`(?i)^[^s]$`, 'ss'], // ❌
  [r`(?i)^[^ſ]$`, 'ß'], // ✅
  [r`(?i)^[^ſ]$`, 'ss'], // ❌
  [r`(?i)^[^ẞ]$`, 'ß'], // ❌ Uppercase `ẞ` in pattern
  [r`(?i)^[^ẞ]$`, 'ss'], // ❌ Uppercase `ẞ` in pattern

  // Other representations of exactly `ß` are OK
  [r`(?i)^\x{DF}$`, 'ss'], // ✅

  // But not sets that include `ß` 🤔
  [r`(?i)^\w$`, 'ss'], // ❌
  [r`(?i)^\p{Word}$`, 'ss'], // ❌
  [r`(?i)^\D$`, 'ss'], // ❌
  [r`(?i)^.$`, 'ss'], // ❌
  [r`(?i)^\O$`, 'ss'], // ❌
  [r`(?i)^\p{Any}$`, 'ss'], // ❌

  // Within positive classes, other representations of `ß`, and sets/ranges that include `ß`, are OK
  [r`(?i)^[\x{DF}]$`, 'ss'], // ✅
  [r`(?i)^[\x{DE}-\x{E0}]$`, 'ss'], // ✅
  [r`(?i)^[\w]$`, 'ss'], // ✅
  [r`(?i)^[\p{Word}]$`, 'ss'], // ✅
  [r`(?i)^[[:word:]]$`, 'ss'], // ✅
  [r`(?i)^[\D]$`, 'ss'], // ✅
  [r`(?i)^[\P{M}]$`, 'ss'], // ✅
  [r`(?i)^[\p{Any}]$`, 'ss'], // ✅

  // But not within negated classes 🤔
  [r`(?i)^[^[^\x{DF}]]$`, 'ss'], // ❌
  [r`(?i)^[^\0]$`, 'ss'], // ❌
  [r`(?i)^[^\W]$`, 'ss'], // ❌
  [r`(?i)^[^\d]$`, 'ss'], // ❌
  [r`(?i)^[^\p{M}]$`, 'ss'], // ❌

  // The negation rule is about negation of the outermost class, only 🤔
  [r`(?i)^[^[\W]]$`, 'ss'], // ❌
  [r`(?i)^[[^\W]]$`, 'ss'], // ✅ 🤯
  [r`(?i)^[\w&&[^\W]]$`, 'ss'], // ✅ 🤯

  // Flags `W` and `P` exclude `ß` from `\w`
  [r`(?iP)^[\w]$`, 'ss'], // ❌
  [r`(?iW)^[\w]$`, 'ss'], // ❌
  [r`(?iW)^\w$`, 'ss'], // ❌
  [r`(?iW)^[ß]$`, 'ss'], // ✅
  [r`(?iW)^ß$`, 'ss'], // ✅
  [r`(?iW)^\x{DF}$`, 'ss'], // ✅

  // Quantifier basics; nothing surprising here
  [r`(?i)^ß{2}$`, 'ßß'], // ✅
  [r`(?i)^ß{2}$`, 'ss'], // ❌
  [r`(?i)^ß{2}$`, 'ssss'], // ✅
  [r`(?i)^[ß]{2}$`, 'ss'], // ❌
  [r`(?i)^[ß]{2}$`, 'ssss'], // ✅
  [r`(?i)^[^ß]{2}$`, 'ss'], // ✅
  [r`(?i)^[^ß]{2}$`, 'ssss'], // ❌

  // Character classes are affected by backtracking! 🤔
  // Bad news for performance (it probably should have been atomic like `\R` and `\X`)
  [r`(?i)^[\w]{2}$`, 'ss'], // ✅
  [r`(?i)^[\w]{2}$`, 'sss'], // ✅
  [r`(?i)^[\w]{2}$`, 'ssss'], // ✅

  // In the reverse direction
  [r`(?i)^ss$`, 'ss'], // ✅
  [r`(?i)^ss$`, 'ß'], // ✅
  [r`(?i)^ſſ$`, 'ß'], // ✅
  [r`(?i)^ss$`, 'ẞ'], // ✅ // Uppercase `ẞ`

  // In the reverse direction with quantifiers; nothing surprising here
  [r`(?i)^s{2}$`, 'ß'], // ❌
  [r`(?i)^ss{2}$`, 'ßß'], // ❌
  [r`(?i)^(?:ss){2}$`, 'ßß'], // ✅
]

To be frank, this is a mess. It’s unreasonable to expect users to understand this. However, if you do understand the rules, it is consistent and predictable.

New problems with Quantifier(*, +, {n,}, etc…)

The fact that (?i)[\w] matches "ss" creates a new problem. Quantifier can cause a phenomenon similar to ReDos. ex. (?i)[\w]+. Please see the comments below for more details. kkos/oniguruma#290 (comment) This issue is separate from the (?i)\w and (?i)[\w] issue. But you’ll need to be careful.

Thanks for pointing this out, and including the link!

Oniguruma should have made […] atomic, like is already done for \R and \X.

About the behavior of (?i)[\w] matching “ss”

This may be a new problem for oniguruma-to-es. I tried it and it didn’t match in JavaScript. Addressing this issue will result in the Quantifier issues mentioned above.

Thanks for testing! Yes, this behavior is not in oniguruma-to-es. And although I should document this somewhere as a known difference, I don’t plan to implement it, because:

  1. The behavior is inconsistent (in complicated ways, and the inconsistency can be thought of as a bug).
  2. It would create the potential for serious performance problems.
  3. It would significantly increase browser bundle size to include all the relevant Unicode data (I think the rules for this are in Unicode’s SpecialCasing.txt) and to track all the Unicode properties/etc. that should trigger it.
  4. There are close to zero cases where anybody will want or benefit from this behavior.

If someone reports it as a bug based on real-world use, we can consider it again at that time.

By the way, in case it’s helpful for future testing, I have a command line script in this library that allows quickly testing a regex in Oniguruma (via vscode-oniguruma) and comparing the result to the JS regex created by this library. I just made some improvements to it, and mentioned it in the new contributing guide. You can run it via node scripts/onig-match.js 'pattern' 'str'. There are more details in the comment at the top of the script file.

Image

Against “\xc5\xbf”

(?iW)\w          /* search fail */
(?iW)\p{Word}    /* search fail */
(?iW)[\w]        /* Matched (0-2) */
(?iW)[[:word:]]  /* Matched (0-2) */

Oniguruma Owner(K.Kosako)'s comment:

I agree that it is odd that these four results do not match. However, for word type, it is difficult to have exactly the same behavior because of the particular implementation method. Therefore, only word type has a special specification for IGNORECASE. But if you are not using the (?W) option, you probably don’t need to worry about it.

Problems caused by optimization (perhaps)

(?iW)[^\W] will probably be treated as (?iW)\w due to optimization. (?iW)[[^\W]] will probably be treated as (?iW)[\w] due to optimization. So (?iW)[^\W] and (?iW)[[^\W]] behave differently.

This problem goes beyond the scope of (?W)

Against “ss”

^(?i)\w$          /* search fail */
^(?i)[\w]$        /* Matched (0-2) */

New problems with Quantifier(*, +, {n,}, etc…)

The fact that (?i)[\w] matches "ss" creates a new problem. Quantifier can cause a phenomenon similar to ReDos. ex. (?i)[\w]+. Please see the comments below for more details. https://github.com/kkos/oniguruma/issues/290#issuecomment-1825555154 This issue is separate from the (?i)\w and (?i)[\w] issue. But you’ll need to be careful.

About the behavior of (?i)[\w] matching “ss”

This may be a new problem for oniguruma-to-es. I tried it and it didn’t match in JavaScript. Addressing this issue will result in the Quantifier issues mentioned above.

😊 To be clear…

In particular, the {m,n} that @RedCMD pointed out is hard to notice.🙀 https://github.com/slevithan/oniguruma-to-es/issues/25

I think Oniguruma is amazing, and a marvel of engineering!

That’s true! Of course, the same goes for what you’re making.😊

I think all of those results are reasonable. My surprise (“🤯”) was about how the behavior is different for outermost negated classes [^…] and nested negated classes [[^…]].

Even though I argued for removing the behavior of changing match length during case insensitive matching (unless the user opts into it via an option), I think that when the behavior is enabled it should always apply, regardless of the specific features used. So the “🤯” did not mean I thought the result was wrong. It only meant I was surprised by the result.

@slevithan You and K. Kosako(Oniguruma Ower) have worked hard to make Oniguruma better. Many thanks to both of you. I respect K. Kosako’s decision.

About Oniguruma

https://github.com/kkos/oniguruma/issues/351 is solved by https://github.com/kkos/oniguruma/commit/5d0506c66c4d3613912fa81d7d1b99f83dbea8e2 . In other words, The Quantifier issues mentioned above is solved in the fix_351_349 branch . I think this is a great benefit to users. And also, Time-Limit and Unicode property \pC, \pL, \pM, \pN, \pP, \pS, \pZ have been added. It would be a loss for Oniguruma users if these are not released.

That’s why I use fix_351_349 branch. This is Oniguruma v6.9.11 for me. For https://github.com/kkos/oniguruma/issues/349, there is no problem as long as I do not use ignore-case.


About PHP

As @slevithan already knows (Thank you for giving me a ⭐), I have written a way to test Oniguruma 6.9.10 with PHP 8.4.6 . If you are good at PHP, please give it a try.


About Oniguruma-To-ES

I have nothing more to point out. Thank you for your assistance. I learned a lot about Oniguruma from you, thank you.

@RedCMD:

Tweak: Your (xx)\1|(xx)(x)(?>\2|\1) should be (?<n>xx)\1|(xx)(x)(?>\3|\2).

That’s creative thinking, but I’m quite skeptical it could be made to work in a generalized way, once you accounted for all Oniguruma features, plus everything else already going on with capturing groups under the hood (given the needs of JS emulation).

Consider:

  • (?<n>…)(?<n>…)??…\k<n>
  • (?<n>…)(?<n>…)??\k<n>…
  • (?<n>…)(?<n>…)??…\k<n>…
  • (?<n>…)…(?<n>…)??…\k<n>
  • (?<n>…)…(?<n>…)??\k<n>…
  • (?<n>…)…(?<n>…)??…\k<n>…

…For any possible values of ….

As one of the simpler complications that first comes to mind, what about (?<n>a)(?<n>b)??(?<n>c)??\k<n>? Now we have something like (?<n>a)\1|(a)(b)(?>\3|\2)|(a)(b)(c)(?>\6|\5|\4)|(a)(c)(?>\8|\7).

You might see the problems already:

  • It’s not equivalent, since there’s no reason to assume that the testing order should go from (a)(b) → (a)(b)(c) → (a)(c). The appropriate match order would probably have to change dynamically based on backtracking, which isn’t possible.
  • This is an exponential explosion in length and alternation, which could easily become an attack vector similar to ReDoS.

And what about when some of the (?<n>…) captures contain \k<n>, assuming they appear after some earlier instances of (?<n>…) have already participated?

And I shudder to think about how it would complicate subroutine handling, which is already complicated enough in Oniguruma but is wildly complicated in oniguruma-to-es after all the hoops that are jumped through to emulate all of their edge cases using JS’s limited native regex features. You might say that subroutines can’t reference duplicate group names… but they can! Just indirectly (they can reference a group that contains a duplicate group name).

Result:

number of names: 2
match at 0

foo (1): (0-3) 
foo (3): (7-9) *
bar (2): (3-7) *

Note: About ‘*’ https://github.com/kkos/oniguruma/blob/c98766f14e98cf3db83aa63213dbd381ae47a19a/sample/names.c#L20

This is very helpful – thank you. However, the native API for JS RegExp results can only include one value for each group name, due to the shape of the match result object. These values are stored on a result’s groups object. If you use JS flag /d (which adds subpattern indices to the result), the positions by name are stored on indices.groups.

So, my next question is: do any Oniguruma APIs consider there to be one (official) subpattern value for duplicate group names? If yes, I should probably emulate those results. If not, the current oniguruma-to-es behavior for named subpatterns on match results might be good enough, since there isn’t something official to emulate. The current behavior is that, for example, result.groups.name will hold the value from the first capture called name. However, that value might be changed based on later-participating subroutines which reference that group.

Even if there isn’t an official single value from Oniguruma, because of the *s you pointed out on results, it still feels like it might be better to change this behavior so that it changes the subpattern value based on later-participating instances of duplicate group names. However, this wouldn’t necessarily be a bug fix, just an improvement that follows the spirit of Oniguruma.

Case 3. (?<n>xx)(?<n>x)??\k<n> and (xx)(x)??(?>\2|\1)

This case will fail to match the same result in oniguruma-to-es (it will match 'xx' instead of 'xxxx') because it is not possible to determine at compilation time whether a capturing group (in the same alternation path) with a lazy, zero-minimum quantifier will have participated in the match when the backreference is matched (it can change dynamically, based on backtracking). So, the \k<n> will be converted to the equivalent of (?>\2|\1) (instead of just \1 as it would be if this was a case where nonparticipation could be detected), and in JavaScript the \2 will match ''. 😔

Ironically, this particular case would have been fine if we hadn’t switched the order from \1|\2 to \2|\1.

It is technically possible to specifically target this case to make it work. We could determine that the group is nonparticipating since (1) it has a zero-min, lazy quantifier, (2) it is immediately followed by a backreference to it (there’s nothing in between to potentially force backtracking), and (3) there are no tokens after the backreference that could lead to backtracking. But, apart from test cases, people don’t write patterns that would satisfy those conditions, so it wouldn’t be very useful.

This situation is documented in the “Supported features” table in the readme (see the “❌”):

Backreferences | To nonparticipating groups ✔ Error if group to the right[4] ✔ Duplicate names (and subroutines) to the right not included in multiplex ✔ Fail to match (or don’t include in multiplex) ancestor groups and groups in preceding alternation paths ❌ Some rare cases are indeterminable at compile time and use the JS behavior of matching an empty string

I don’t believe it’s possible to solve this in a generalized way using native JavaScript RegExp. And there is no alternative to using native RegExp unless you create your own compatible regex engine in JS (in which case it would be huge, slower than the native solution, and probably have lots of new bugs).

Even though oniguruma-to-es is not able to detect all cases of capturing-group-nonparticipation, the fact that it solves this at all (in fact, for most cases!) makes it unique, since no other JavaScript library does anything like this for any regex flavor. Also note that the missing support for this isn’t triggered by any of the ~55,000 real-world Oniguruma regexes used in TextMate grammars that are provided by Shiki.

It’s a pleasure to meet such a great IT engineer as you.

Same to you, regex brother! 😊

@slevithan Rubular’s “Match groups” seem wrong. https://rubular.com/r/adP02b0KO231c6

(?<n>a)(?<n>b)|(?<r>c)(?<r>d)
Test string: abcd
r b   # I think this is a bug.

oniguruma/doc/RE#L420-L425

When backreferencing with a name that is assigned to more than one groups, the last group with the name is checked first, if not matched then the previous one with the name, and so on, until there is a match.
* Backreference by number is forbidden if any named group is defined and ONIG_OPTION_CAPTURE_GROUP is not set.

The following are tests using v6.9.10. (Same result on the current master branch.)

(?<n>x)(?<n>xx)\k<n> matches “xxxxx”. ( Matched pos 0 to pos 5, not pos 0 to pos 4.) (?<n>x)(?<n>xx)\k<n> matches “xxxx”. (However, Rubular fails.)

(?<n>x)(?<n>xx)\k<n>x does not match “xxxxx”. ( https://github.com/kkos/oniguruma/issues/252 ) Oniguruma owner(K.Kosako)'s comment:

This is inevitable because backreferences to duplicate names are achieved by a different process than the usual alternations(|). Therefore, it is a specification. Consider that once one of these matches is made, the other options are cut.

(?<n>x)(?<n>xx)\k<n>\k<n>x does not match “xxxxxx”. (6 x’s) (?<n>x)(?<n>xx)\k<n>\k<n>x does not match “xxxxxxx”. (7 x’s) (?<n>x)(?<n>xx)\k<n>\k<n>x matches “xxxxxxxx”. (8 x’s)

Is there a test you’d like to try?