Linear regex
Run an operator-supplied pattern in time proportional to the subject, whatever the pattern is.
The backtracking engine every JavaScript runtime ships explores one path at a time and reconsiders when a path fails. For most patterns that is quick and for some it is catastrophic: (a+)+$ against forty as and a ! takes longer than the request that carried it, and the pattern that does it is a few characters long. Where the pattern comes from an operator's configuration and the subject from a request, that is a denial of service with no payload.
Screening the pattern first — b.guardRegex — decides whether a pattern LOOKS dangerous. It is a conservative screen, and conservative screens have two failure modes: they turn away patterns that were fine, and they cannot promise to catch every shape that is not.
This runs the pattern instead. It simulates every path at once, one character of the subject at a time, keeping at most one live position per instruction. A path that dies costs nothing to abandon because it was never the only one being followed, and no input makes the work grow faster than the length of the subject times the size of the pattern. There is nothing to tune, no budget to exhaust and no shape to special-case.
What it will not do is guess. Backreferences and lookaround cannot be simulated this way, so a pattern using them is refused by name at compile time rather than quietly handed to the engine that can be made to hang.
b.regexLinear.compile(source, flags?) #
{
(none — flags are passed as the second argument, as `RegExp` takes them)
}Compile a pattern into a matcher that runs in time proportional to the subject, whatever the pattern is.
source is the pattern without delimiters, as RegExp takes it, or a RegExp whose source and flags are used. Flags i, m, s, u and y are honored. g is not, because the matcher returns one match and the caller decides what to do next.
Two are refused by name rather than ignored, both under regex/unsupported-flag. v brings class set operations — intersection, subtraction, string properties — that this does not implement, and reading it as a u would quietly match a different language; use u, or name the characters in a plain class. d asks for the index of every capture, which this does not record; drop it, or run the pattern with the platform engine once it has been screened.
The returned matcher exposes test(subject) and exec(subject, from?). exec returns null or a result shaped like the platform's: index 0 is the whole match, higher indices are the capture groups, index is where the match began, and groups carries the named ones.
Backreferences and lookaround are refused at compile time, by name, with the code regex/unsupported-backreference or regex/unsupported-lookaround. They cannot be simulated without exploring paths one at a time, which is the thing being avoided — so the choice is made where an operator can see it, rather than by handing the pattern to an engine that can be made to hang.
Four more are refused for narrower reasons, each under its own code and each with a message saying what to write instead: a repetition whose body can match nothing (regex/nullable-repetition — (a*)* means what a* means); a group named outside ASCII, and a name reused across alternatives (regex/bad-group); an inline flag modifier such as (?i:...) (regex/unsupported-group), whose scoped flags this does not yet carry; and a Unicode property escape under u, such as \p{L} ( regex/unsupported-property) — name the characters in a class instead. Without u there is no property escape to refuse: \p{L} is a p, a brace, an L and a brace there, and it compiles. These are patterns the platform accepts, so a pattern using one has to be screened and run with the platform engine, or rewritten.
A source over 64 KiB throws regex/pattern-too-large before parsing. Everything else accepted here returns exactly what RegExp returns, with one exception that belongs to the platform rather than to this matcher: under u, an unanchored pattern ending in a CHARACTER CLASS that can match at most one code point, then $, misses a subject ending in an astral character. new RegExp("[^a]$", "u") finds nothing in a single emoji, while new RegExp("^[^a]$", "u") finds it — and a ^ can only take match positions away, never add one. This returns the match, which is what the language specifies, so on that one shape the two answers differ. A class that may run on ([^a]+$, [^a]*$), a shorthand (\W$), the dot, and the character written out are all unaffected.
A pattern the parser cannot consume to the end, such as an unmatched bracket or parenthesis, throws regex/unbalanced.
The rest of the syntax refusals: a character class whose range runs backwards, or whose endpoint is a shorthand under the u flag, throws regex/bad-class; a trailing backslash, and a lone {, }, ] or other character that u makes a syntax error, throw regex/bad-escape; a {n,m} whose numbers run backwards, and a quantifier with nothing to repeat, throw regex/bad-quantifier. A pattern whose repetition counts multiply out past the program ceiling throws regex/repeat-too-large, which a short pattern can reach when its repetitions nest. A node the compiler has no emitter for throws regex/unsupported.
var m = b.regexLinear.compile("^(\\w+)@([\\w.]+)$");
m.test("ada@example.com"); // → true
m.exec("ada@example.com")[2]; // → "example.com"
// The shape that hangs the platform engine runs in linear time here.
b.regexLinear.compile("(a+)+$").test("a".repeat(40) + "!"); // → false