Previously, a character class containing any builtin (\d, \w, \s)
forced the compiler down the slow "complex class" path, which emits
a disjunction of alternatives and backtracks at runtime.
For non-unicode, non-unicode-sets, non-negated classes, \w and \d
can be inlined as their raw ASCII code-point ranges. The resulting
class stays on the fast path and compiles into a single sorted
CharClass instruction.
The unicode/unicode_sets and negation guards are required for
correctness: with the /u + /i flags, \w gains non-ASCII members
via case folding (e.g. U+017F, U+212A), and negated classes have
a separate, smarter compilation path.
Analyze parsed patterns for literal substrings that every match
must contain and feed the longest one into the existing
required-literal hint. This lets the VM reject obvious misses
for optional-prefix extractors, literal-prefix parsers, and
common-substring alternations without adding more shape-specific
fast paths.
Use ASCII case-insensitive probes when the required literal comes
from a legacy `/i` pattern, and skip modifier groups that change
ignore-case so the hint does not over-constrain scoped flag
behavior. Keep the analysis within the same 64-code-unit budget
that the VM hint already uses so large fixed quantifiers and long
literal alternations do not blow up compile time.
Add TestRegex coverage for assignment extractors, ASCII ignore-
case prefilters, common-substring alternations, and the compile-
time regression shapes. TestRegex passes, the long-pattern js
probes behave correctly, and regex benchmark spot checks stay
fast.
Extract whole-pattern `\bliteral\b` cases outside Unicode
modes and handle them with literal search plus ASCII word-
boundary checks. This keeps the optimization narrow while
still covering the token-style patterns that show up often in
our regex workloads.
Keep Unicode word-boundary patterns on the VM path, since
`\b` semantics change there. Add tests for plain matching,
ASCII ignore-case matching, and the Unicode fallback case.
Extend the literal alternation fast path to cover ASCII-only
`/i` patterns outside Unicode modes. Search candidate start
positions with a folded first-code-unit set, then verify the
alternatives in source order to preserve ECMAScript semantics.
Keep Unicode ignore-case alternations on the VM path, since they
can match non-ASCII code points through canonicalization. Add
tests for mixed-prefix alternatives, source-order selection,
and the Unicode fallback behavior.
Whole-pattern ignore-case literals already bypass the VM, but the
search path still checked every start position linearly with full
case-fold comparisons. For ASCII literals we can cheaply scan for the
first code unit and only verify the rest at candidate positions.
This keeps the existing non-ASCII fallback intact while speeding up
common benchmark shapes such as `/puebzr/i`, `/zfvr/gi`, and
`/##yv22##/gi`. Add tests covering both alphabetic and punctuation-led
ASCII literals under ignore-case matching.
TestRegex passes. In Build/release js microbenchmarks, representative
cases dropped from about 47ms to 38ms, 95ms to 63ms, and 121ms to
79ms.
Patterns like `(?:^|;)\s*foo=...` can only start matching at input
start or at occurrences of the separator, but the generic
start-position loop still entered the VM at each byte and paid the
leading split/backtrack cost on every miss.
Teach the start-position analysis to recognize this `(^|literal)`
shape and jump straight to those candidate positions. Keep the
optimization narrow: wider literal sets would need a single-pass
scanner, and rescanning once per literal would make miss-heavy
alternations quadratic.
Add a LibRegex test for the cookie-style prefix. TestRegex still
passes, and a release js benchmark exercising this shape remains
fast.
Port a broad slice of the old TestRegex.cpp coverage to the new
ECMAScriptRegex API so we keep exercising the Rust engine with the
same kinds of parser and matcher edge cases that used to live in the
legacy C++ suite.
Restore checks for parser acceptance and rejection, lookbehind
captures, quantified alternations, zero-width backreferences,
undefined backreferences, optional groups with empty matches,
modifier groups, Unicode properties and Unicode sets, empty-match
loops, and long fork chains.
Leave out the old Posix tests and bytecode-dump assertions that were
specific to the removed engine internals. One old boolean expectation
for duplicate named groups also did not translate cleanly to the new
search-style API, so keep the surrounding duplicate-name coverage in
capture-focused tests instead.
Verify the port with ./Build/sanitizers/bin/TestRegex.
Teach the Rust matcher to execute directly on ASCII-backed input.
Make the VM and literal fast paths generic over an input trait so we
can monomorphize separate ASCII and WTF-16 execution paths without
duplicating the regex semantics. Add ASCII-specific FFI entry points
and have the C++ bridge dispatch to them whenever Utf16View carries
ASCII storage.
This removes the per-match widening step from the hot path for exec(),
test(), and find_all(), which is exactly where LibJS often hands us
pure ASCII strings in 8-bit form. Keep the compiled representation
and reported capture offsets in UTF-16 code units so the observable
JavaScript behavior stays unchanged.
Delete the old C++ ECMA-262 parser, optimizer, and matcher now that all
in-tree users compile and execute through `ECMAScriptRegex`.
Stop building the legacy engine, remove its source files and the
POSIX-only fuzzers that depended on it, and update the remaining
LibRegex tests to target the Rust-backed facade instead of the deleted
implementation. Clean up the last includes, comments, and helper paths
that only existed to support the old backend.
After this commit LibRegex has a single ECMAScript engine in-tree,
eliminating duplicated maintenance and unifying future regex work.
Backreferences can match the empty string when the referenced group
didn't participate in the match, so we shouldn't add their length to the
match_length_minimum, as it makes us skip valid matches.
Optimizer wasn't considering case-insensitive mode when checking for
overlap between the repeated element and what follows. So patterns like
`/a*A\d/i` failed to match because 'a' and 'A' weren't seen as
overlapping. We compare them in a case-insensitive way now, when i flag
is set.
`range_contains()` checked if an lhs_range was contained within the
query range, rather than checking for overlap. This caused patterns
like `/A*[A-Z]/` to fail matching "A" because the optimizer didn't
detect that 'A' overlaps with [A-Z]. And `char_class_contains()` only
checked if two character classes were identical, not if they overlapped.
So patterns like `/\d*\w/` failed to match "1" because \d and \w were
not recognized as overlapping, even though all digits are word
characters.
This commit implements the regexp-modifiers proposal. It allows us to
use modification of i,m,s flags within groups using
`(?flags:subpattern)` and `(?flags-flags:subpattern)` syntax.
Step 2.b of the RepeatMatcher states that once minimum repetitions
are satisfied, empty matches should not be considered for further
repetitions. This was not being enforced for optional quantifiers
like `?`, so we had extra capture group matches.
This introduces a new mechanism for evaluating lookbehind assertions by
adding four new bytecode opcodes: SetStepBack, IncStepBack,
CheckStepBack, and CheckSavedPosition.
These opcodes replace the previous GoBack-based approach and enables
correct handling of variable-length lookbehind patterns,
where the match length cannot be known statically.
Track lookbehind greediness in the parser and propagate it to bytecode
generation. Allow controlled backtracking in lookbehind bodies while
avoiding incorrect captures during step-back execution.
Partially fix issue: #3459
Previously, we used restoration based on character position in parser.
This caused the lexer to re-tokenize from the middle of multi-character
tokens like escape sequences, and led to incorrect parse failures for
patterns like `[\[\]]`. We would backtrack to before the first `\[`
token, then re-lex the `[` as a separate token instead of part of the
`\[` escape.
Now we save and restore the actual token object along with the lexer
index, so we keep correct token state when backtracking.
We were incorrectly checking for negated character class when string
properties appeared in nested classes. Now we track negation state in
the parser and correctly reject invalid string properties in negated
classes.
Patterns like /[^\S]/ should match whitespace characters, but previously
would fail to match. The position would advance twice: once during the
character class comparison, and again at the end when temporary_inverse
was reset. This caused matches to be skipped incorrectly.
Now we advance at the end only if position hasn't already changed during
the loop.
Fixes parsing of regex quantifiers with extremely large numeric values.
Previously, very large quantifiers would fail to parse, but Chrome and
Firefox both clamp such large values to 2^31-1 instead of rejecting
them. So now we do the same.
Fixes handling of backreferences when the referenced capture group is
undefined or hasn't participated in the match.
CharacterCompareType::NamedReference is added to distinguish numbered
(\1) from named (\k<name>) backreferences. Numbered backreferences use
exact group lookup. Named backreferences search for participating
groups among duplicates.
Not accounting for opcode size when calculating incoming jump edges
meant that we were merging nodes where we otherwise shouldn't have been,
for example /.*a|.*b/.
Finishes what 7f6b70fafb started.
Having one part use length and another code unit length lead to crashes,
the added test ensures we don't mess that up again.
This prevents empty matches from overwriting non-empty captures in
quantified alternations. Fixes patterns like (a|a?)+ where the optional
branch would incorrectly overwrite meaningful captures with empty
strings.
We had typo'd using ClassSetReservedDoublePunctuator which was
resulting in a parse error for the regex:
([^\\:]+?)
With the 'v' flag set.
Co-Authored-By: Ali Mohammad Pur <mpfard@serenityos.org>
As LibRegex was not specified in TEST_DIRECTORIES, the existing
Tests/LibRegex subdirectory was not actually included during
configuration. Also the RegexLibC test has not been needed
since migration away from Serenitys LibC was done, so
that test has been fully removed. I also renamed the
Regex.cpp test to TestRegex.cpp to match the naming
convention of most test targets.
Fixes a bunch of websites breaking because we now verify jump offsets by
trying to remove 0-offset jumps.
This has been broken for a good while, it was just rare to see Repeat
inside alternatives that lended themselves well to tree alts.
This removes another Match member that required destruction. The "API"
for accessing the strings is definitely a bit awkward. We'll think of
something nicer eventually.
This mode made a lot of incorrect assumptions about string lifetimes,
and instead of fixing it, let's just remove it and tweak the few unit
tests that used it.
