Rework regular expression parsing/compiling to be more lenient

[svaarala]

Duktape's regular expression parser/compiler conforms strictly to the E5/E5.1 regular expression syntax, and rejects many regular expressions that are leniently allowed by other engines. It's confusing to users that other engines parse several regexp forms that Duktape (technically correctly) rejects as a SyntaxError.

Examples of technically invalid regexps that work with most engines:

• /^\_/: underscore escape is not allowed, underscore is an IdentifierPart and identity escapes are not allowed for identifier part characters.
• /\$/: regexp escape is not allowed, dollar sign is an IdentifierPart. Duktape already has a fix to allow a dollar escape because it's so common.
• /\\{/: unescaped brace is not allowed (unless it is part of a quantifier like /x{5}/).
• /[\2]/: non-zero decimal escape is not allowed (E5 Section 15.10.2.19) but accepted by other engines.

Because these regexps are quite widely used, Duktape should probably parse regexps a bit more leniently. This change is non-trivial because lenient regexp parsing needs backtracking which doesn't fit easily into the current regexp parser/compiler code. For instance, when parsing /{foo}/, Duktape will see the left curly brace and think it's parsing a quantifier. When it fails to parse, it currently throws a SyntaxError. Instead, it should rewind and assume { is meant literally, i.e. parse the regexp as /\{foo\}/.

Related issues with notes on various failing regexps:

• Regexp parse error - dollar escape /\$/ #19
• Invalid decimal escape regex parse error #39
• Regular expression parse error - /^\_/ and /\\{/g #69
• Regexp parse error - [^[]] #86
• Duktape chokes on literal braces in RegExp #142
• Duktape fails to parse a regexp accepted by chrome #425
• Escaped unicode identifier parts in duktape regexp #643

Tasks:

• Figure out what leniency is necessary for "real world" compatibility with other engines. The main goal is to avoid unnecessarily surprising users.
• Make the necessary changes to Duktape for more lenient parsing. The changes should be made with code footprint in mind (not growing the footprint if possible). There should be an option to restore compliance, if possible. There's probably no need to have an option to enable/disable individual leniency cases, just a lenient/compliant option.
• Update testcases.
• Update internal documentation (doc/regexp.rst) to reflect the changes in the regexp algorithm.
• Update external documentation. Document the non-compliant regexp forms allowed.

[mitchblank]

Not directly related, but just wanted to plant an idea in your head.

In my codebase I already have a regex engine available -- namely PCRE with some optimizations layered on top. Modern PCRE even support things like JIT compilation.

I know that pcre and ecmascript regexes aren't identical but pcre is pretty close to being a superset, so if it were possible to bring my own regex engine I probably would.

When I was doing some investigations of mruby, that was one thing I really liked. The language's parser would find the regex, but it would then just hand off the string to a constructor for the ruby Regex class. By putting your own implementation of that class in the global scope it was very easy to seamlessly wire in your own engine.

I don't consider this a high-priority item at all, but if there was an API for me to pass in a few function pointers and slide in my own versions of duk__regexp_match_helper() and duk_regexp_create_instance() (and make the bytecode just emit the raw regex into the bytecode) I would probably do so. Maybe others would find that useful as well, not sure.

[svaarala]

I agree that replacing the regexp engine would be very nice. The built-in engine in Duktape is optimized for compactness which leads to necessary compromises on other features (including performance). I think there's already a Ditz issue for this but it's been low priority.

But now that you mention it, it might make sense to keep Duktape's built-in engine strictly compliant, but make it easy to plug in external regexp engines. These can then be lenient and provide a superset of features when that makes sense.

As for the required hooks, another very straightforward approach is simply to replace the RegExp constructor entirely. RegExp literals need special handling because they're compiled during Ecmascript code compilation and only instantiated during execution. A few hooks would be needed for this.

[mitchblank]

Of course the compiler would still need to lex the regex enough to find its terminating '/' character so it would have to interpret the regex enough to see the backslash escapes etc. It just would skip doing the bytecode generation part.

[svaarala]

Yes, that's what I mean: the compiler would parse the regexp literals (and their flags) but would consult a hook to compile it.

[svaarala]

By the way, ES6 has optional support for literal braces in Section B.1.4:

• http://www.ecma-international.org/ecma-262/6.0/#sec-regular-expressions-patterns

This doesn't extend to unquoted square brackets etc though.

[fatcerberus]

Nice, so we can say the curly brace support is part of "some features borrowed from Ecmascript E6" ;)

[svaarala]

Yes, and as a technical detail the config option shouldn't say "DUK_USE_NONSTD_..." but "DUK_USE_ES6_...".

[mathiasbynens]

Another example: /]/ — see slevithan/xregexp#141. (Since portability is one of Duktape’s goals you’ll want to support this.)