| Age | Commit message (Collapse) | Author |
|---|
|
Previously we were always choosing the "nothing special" code path, even
if the dollar symbol was at the end of the pattern (and therefore should
have been considered special).
Fix that by actually checking if the pattern end follows, and emitting
the correct instruction if necessary.
|
|
|
|
|
|
|
|
Fixes #10027.
|
|
Otherwise the left and right capture instructions wouldn't point to the
same capture group if there was another nested group there.
|
|
- Make sure that all the Repeat ops are reset (otherwise the operation
would not be correct when going over the Repeat op a second time)
- Make sure that all matches that are allowed to fail are backed by a
fork, otherwise the last failing fork would not have anywhere to
return to.
Fixes #9707.
|
|
Found by OSS-Fuzz: https://oss-fuzz.com/testcase?key=4869334212673536
|
|
For example, consider the following pattern:
new RegExp('\ud834\udf06', 'u')
With this pattern, the regex parser should insert the UTF-8 encoded
bytes 0xf0, 0x9d, 0x8c, and 0x86. However, because these characters are
currently treated as normal char types, they have a negative value since
they are all > 0x7f. Then, due to sign extension, when these characters
are cast to u64, the sign bit is preserved. The result is that these
bytes are inserted as 0xfffffffffffffff0, 0xffffffffffffff9d, etc.
Fortunately, there are only a few places where we insert bytecode with
the raw characters. In these places, be sure to treat the bytes as u8
before they are cast to u64.
|
|
Unfortunately, this requires a slight divergence in the way the capture
group names are stored. Previously, the generated byte code would simply
store a view into the regex pattern string, so no string copying was
required.
Now, the escape sequences are decoded into a new string, and a vector
of all parsed capture group names are stored in a vector in the parser
result structure. The byte code then stores a view into the
corresponding string in that vector.
|
|
|
|
This will allow regex::Lexer users to invoke GenericLexer consumption
methods, such as GenericLexer::consume_escaped_codepoint().
This also allows for de-duplicating common methods between the lexers.
|
|
This is primarily to be able to remove the GenericLexer include out of
Format.h as well. A subsequent commit will add AK::Result to
GenericLexer, which will cause naming conflicts with other structures
named Result. This can be avoided (for now) by preventing nearly every
file in the system from implicitly including GenericLexer.
Other changes in this commit are to add the GenericLexer include to
files where it is missing.
|
|
|
|
Currently, when we need to repeat an instruction N times, we simply add
that instruction N times in a for-loop. This doesn't scale well with
extremely large values of N, and ECMA-262 allows up to N = 2^53 - 1.
Instead, add a new REPEAT bytecode operation to defer this loop from the
parser to the runtime executor. This allows the parser to complete sans
any loops (for this instruction), and allows the executor to bail early
if the repeated bytecode fails.
Note: The templated ByteCode methods are to allow the Posix parsers to
continue using u32 because they are limited to N = 2^20.
|
|
Combining these into one list helps reduce the size of MatchState, and
as a result, reduces the amount of memory consumed during execution of
very large regex matches.
Doing this also allows us to remove a few regex byte code instructions:
ClearNamedCaptureGroup, SaveLeftNamedCaptureGroup, and NamedReference.
Named groups now behave the same as unnamed groups for these operations.
Note that SaveRightNamedCaptureGroup still exists to cache the matched
group name.
This also removes the recursion level from the MatchState, as it can
exist as a local variable in Matcher::execute instead.
|
|
|
|
|
|
The grammar for the ECMA-262 CharacterEscape is:
CharacterEscape[U, N] ::
ControlEscape
c ControlLetter
0 [lookahead ∉ DecimalDigit]
HexEscapeSequence
RegExpUnicodeEscapeSequence[?U]
[~U]LegacyOctalEscapeSequence
IdentityEscape[?U, ?N]
It's important to parse the standalone "\0 [lookahead ∉ DecimalDigit]"
before parsing LegacyOctalEscapeSequence. Otherwise, all standalone "\0"
patterns are parsed as octal, which are disallowed in Unicode mode.
Further, LegacyOctalEscapeSequence should also be parsed while parsing
character classes.
|
|
|
|
|
|
* Only alphabetic (A-Z, a-z) characters may be escaped with \c. The loop
currently parsing \c includes code points between the upper/lower case
groups.
* In Unicode mode, all invalid identity escapes should cause a parser
error, even in browser-extended mode.
* Avoid an infinite loop when parsing the pattern "\c" on its own.
|
|
This was exposed to the user by mistake, and even accumulated a bunch of
users that didn't blow up out of sheer luck.
|
|
Fixes all remaining 'built-ins/RegExp/property-escapes' test262 tests.
|
|
|
|
Note that unlike binary properties and general categories, scripts must
be specified in the non-binary (Script=Value) form.
|
|
These were previously generated as two instructions, Compare [Inverse]
and Compare [Property].
|
|
Before now, only binary properties could be parsed. Non-binary props are
of the form "Type=Value", where "Type" may be General_Category, Script,
or Script_Extension (or their aliases). Of these, LibUnicode currently
supports General_Category, so LibRegex can parse only that type.
|
|
This changes LibRegex to parse the property escape as a Variant of
Unicode Property & General Category values. A byte code instruction is
added to perform matching based on General Category values.
|
|
This supports some binary property matching. It does not support any
properties not yet parsed by LibUnicode, nor does it support value
matching (such as Script_Extensions=Latin).
|
|
Otherwise we'd just loop trying to parse it over and over again, for
instance in `/a{/` or `/a{1,/`.
Unless we're parsing in Annex B mode, which allows `{` as a normal
ExtendedSourceCharacter.
|
|
When the Unicode flag is set, regular expressions may escape code points
by surrounding the hexadecimal code point with curly braces, e.g. \u{41}
is the character "A".
When the Unicode flag is not set, this should be considered a repetition
symbol - \u{41} is the character "u" repeated 41 times. This is left as
a TODO for now.
|
|
When the Unicode option is not set, regular expressions should match
based on code units; when it is set, they should match based on code
points. To do so, the regex parser must combine surrogate pairs when
the Unicode option is set. Further, RegexStringView needs to know if
the flag is set in order to return code point vs. code unit based
string lengths and substrings.
|
|
|
|
ECMA262 requires that the capture groups only contain the values from
the last iteration, e.g. `((c)(a)?(b))` should _not_ contain 'a' in the
second capture group when matching "cabcb".
|
|
|
|
|
|
|
|
|
|
|
|
Otherwise the users won't know how many capture groups are in the
parsed regular expression.
|
|
Commonly, bracket expressions are in fact, enclosed in brackets.
|
|
This implements the internal regex stuff for #8506.
|
|
They were pretty confusing when compared with other non-transforming
functions.
|
|
Fixes 1 test262 test.
|
|
Let's make it a bit more clear when we're appending the elements from
one vector to the end of another vector.
|
|
I have no idea *why*, but this stopped working suddenly:
return { { .code_point = '-', .is_character_class = false } };
Fails with:
error: could not convert ‘{{'-', false}}’ from
‘<brace-enclosed initializer list>’ to
‘AK::Optional<regex::CharClassRangeElement>
Might be related to 66f15c2 somehow, going one past that commit makes
the build work again, however reverting the commit doesn't. Not sure
what's up with that.
Consider this patch a band-aid until we can find the reason and an
actual fix...
Compiler version:
gcc (GCC) 11.1.1 20210531 (Red Hat 11.1.1-3)
|
|
|
|
|
|
|
