RegExp backreferences

[ChALkeR]

Currently, attempting to use a RegExp with backreferences throws an error: error: backreferences are not supported

They might seem niche and not-very-often used, but that unfortunately breaks much more stuff than one could expect

They are used in https://www.npmjs.com/package/get-intrinsic, which in turn is chain-required by things like:

• https://www.npmjs.com/package/set-function-length
• https://www.npmjs.com/package/call-bind
• https://www.npmjs.com/package/is-arguments
• https://www.npmjs.com/package/util
• https://www.npmjs.com/package/which-typed-array
• https://www.npmjs.com/package/is-typed-array
• https://www.npmjs.com/package/is-array-buffer
• https://www.npmjs.com/package/assert
• ... etc

In Node.js, it is supported back to at least 0.8

[eliassjogreen]

Oh god, those are some horrifyingly long chain requires. I guess that's the state of much of the JavaScript ecosystem still. There's some further context about regexp in nova in the PR #789 but the gist of it is that we are still just using the Rust regex crate which is why this, and many other ecmascript regex features still fail.

[ChALkeR]

The same regex also seems to throw on error: unclosed character class when backreferences are removed, for [^%.[\]]
And then on error: look-around, including look-ahead and look-behind, is not supported.

The original RegExp:
/[^%.[\]]+|\[(?:(-?\d+(?:\.\d+)?)|(["'])((?:(?!\2)[^\\]|\\.)*?)\2)\]|(?=(?:\.|\[\])(?:\.|\[\]|%$))/g

Ref: https://github.com/ljharb/get-intrinsic/blob/v1.3.1/index.js#L246-L248
Ref: https://github.com/lodash/lodash/blob/4.17.15/dist/lodash.js#L146

[ChALkeR]

fancy-regex can parse it with a single [ -> \[ replacement.
Which should be relatively easy to fix

[aapoalas]

Wrote in Discord as well, but including for posteriority here: Nova uses WTF-8 for its string encoding, which means that generally picking up an existing crate is not going to be an easy fix.

The real fix would be to fork regex or fancy-regex or another crate (see f.ex. the crate that Boa uses) and modify it to use WTF-8 as its internal representation and to confirm to the ECMAScript RegExp specification. Regex is a good candidate for this as it already supports arbitrary byte sequences as haystacks meaning that supporting WTF-8 is mostly not about extending but about contracting the API. Supporting WTF-8 for the needles (search patterns) is a much harder ask.

[ChALkeR]

Boa seems to use https://github.com/ridiculousfish/regress
Strings can be recoded

[aapoalas]

Boa seems to use https://github.com/ridiculousfish/regress Strings can be recoded

Recoding would be prohibitively expensive/slow.

Regress would be a nice crate to fork though, since it is expressly ECMAScript flavoured.

[ChALkeR]

Recoding would be prohibitively expensive/slow.

It's only needed on non-well-formed strings which are rare and could be guarded with a check
Could be DoS-like though if that's in scope, but re-encoding is likely not that slow to be considered a DoS

i.e.:

1. isWellFormed check
2. if yes, use unsuffixed form (aka utf-8)
3. if no (unlikely), re-encode to ucs2 surrogates, and use _ucs2 form

[aapoalas]

There are a couple of issues with that approach:

• A (conformant) RegExp made up from a well-formed pattern matching on a well-formed string can still produce non-well-formed strings.
• To be conformant, a RegExp implementation must either operate on (potentially invalid) UTF-16, or on WTF-8. A RegExp engine operating on UTF-8 is not sufficient.

Hence, a wf-check is only sufficient to lead us into running a RegExp on a non-conformant UTF-8 based engine versus running it on a conformant UTF-16 based engine. Effectively, the choice then starts to list towards just running everything on UTF-16 which then requires recoding every string.

[aapoalas]

Now that I'm on a computer to better write this out, basically the options for RegExp is:

1. Run RegExp only on UTF-8 and only with UTF-8 patterns, enabling the engine's RegExp to support backreferences, lookaheads, and lookbehinds by using some other RegExp engine: this would most likely be regress. This would not, however, be a fully compliant engine as it would not support splitting surrogate pairs.
2. Run RegExp on WTF-8 with WTF-8 patterns: this would make us fully compliant, except that no engine exists that we can use. There are two possible paths to get us this engine:
   1. Fork (and possibly upstream changes to) regress, building a WTF-8 based version of it. They already have both UTF-8 and UTF-16 variants. This is probably not a massive effort, though absolutely not trivial either.
   2. Fork regex, building a WTF-8 based version of it. This would not give us backreferences, lookaheads, or lookbehinds. There is an existing branch to support lookbehinds in the engine, and a way to add in lookaheads as well. Backreferences would need something ... more, different. But the nice thing with the regex crate is that it is guaranteed to be linear-time in its matching.
3. Run RegExp on UTF-16: this would enable us to use a fully-compliant engine (again likely regress) but would require converting between WTF-8 and UTF-16 at each interface.
4. Perform WF-checks and use two different RegExp engines; one for UTF-8 strings searched by patterns that we guarantee cannot produce non-well-formed results (this isn't as common as you'd think: /./ can technically produce invalid results).

I'm personally quite partial to option 2.2. but it is a long-term goal and it's unclear what the way to supporting backreferences would be there: backreferences are (in the general case) mathematically proven to not be linear-time matchable, so regex's linear-time guarantees cannot be upheld. Option 2.1. is the best and most realistic option for a fully-compliant RegExp engine, but it sadly does cost us the linear-time guarantees as it is my understanding that regress isn't very linear-time.