summaryrefslogtreecommitdiff
path: root/Userland/Libraries/LibRegex/RegexParser.cpp
AgeCommit message (Collapse)Author
2021-08-15LibRegex: Implement and use a REPEAT operation for bytecode repetitionTimothy Flynn
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.
2021-08-15LibRegex+LibJS: Combine named and unnamed capture groups in MatchStateTimothy Flynn
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.
2021-08-15LibRegex: Disallow unescaped quantifiers in Unicode modeTimothy Flynn
2021-08-15LibRegex: Use correct source characters for Unicode identity escapesTimothy Flynn
2021-08-15LibRegex: Implement legacy octal escape parsing closer to the specTimothy Flynn
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.
2021-08-15LibRegex: Ensure escaped hexadecimals are exactly 2 digits in lengthTimothy Flynn
2021-08-15LibRegex: Ensure escaped code points are exactly 4 digits in lengthTimothy Flynn
2021-08-15LibRegex: Fix ECMA-262 parsing of invalid identity escapesTimothy Flynn
* 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.
2021-08-13AK+Everywhere: Delete Variant's default constructorAli Mohammad Pur
This was exposed to the user by mistake, and even accumulated a bunch of users that didn't blow up out of sheer luck.
2021-08-11LibRegex: Disallow invalid interval qualifiers in Unicode modeTimothy Flynn
Fixes all remaining 'built-ins/RegExp/property-escapes' test262 tests.
2021-08-04LibRegex: Support property escapes of Unicode script extensionsTimothy Flynn
2021-08-04LibRegex: Support property escapes of the Unicode script propertyTimothy Flynn
Note that unlike binary properties and general categories, scripts must be specified in the non-binary (Script=Value) form.
2021-08-02LibRegex: Generate negated property escapes as a single instructionTimothy Flynn
These were previously generated as two instructions, Compare [Inverse] and Compare [Property].
2021-08-02LibRegex: Support property escapes of the form \p{Type=Value}Timothy Flynn
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.
2021-08-02LibRegex: Support property escapes of Unicode General CategoriesTimothy Flynn
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.
2021-07-30LibRegex+LibUnicode: Begin implementing Unicode property escapesTimothy Flynn
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).
2021-07-24LibRegex: Make unclosed-at-eof brace quantifiers an errorAli Mohammad Pur
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.
2021-07-23LibRegex: Support ECMA-262 Unicode escapes of the form "\u{code_point}"Timothy Flynn
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.
2021-07-23LibRegex: Support UTF-16 RegexStringView and improve Unicode matchingTimothy Flynn
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.
2021-07-23LibRegex: Switch to east-const styleAli Mohammad Pur
2021-07-23LibRegex: Clear previous capture group contents in ECMA262 modeAli Mohammad Pur
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".
2021-07-13LibRegex: Consider EOF in the middle of a range an errorAli Mohammad Pur
2021-07-13LibRegex: Don't attempt to insert invalid bytecode in {B,E}REAli Mohammad Pur
2021-07-13LibRegex: Implement lookaround in EREAli Mohammad Pur
2021-07-13LibRegex: Allow empty character classes in {B,E}REAli Mohammad Pur
2021-07-13LibRegex: Disallow excessively large repetition counts in {B,E}REAli Mohammad Pur
2021-07-10LibRegex: Use the parser state capture group count in BREAli Mohammad Pur
Otherwise the users won't know how many capture groups are in the parsed regular expression.
2021-07-10LibRegex: Correctly parse BRE bracket expressionsAli Mohammad Pur
Commonly, bracket expressions are in fact, enclosed in brackets.
2021-07-10LibRegex: Add support for the Basic POSIX regular expressionsAli Mohammad Pur
This implements the internal regex stuff for #8506.
2021-07-10LibRegex: Make the bytecode transformation functions staticAli Mohammad Pur
They were pretty confusing when compared with other non-transforming functions.
2021-07-06LibRegex: Allow dollar signs in ECMA262 named capture groupsTimothy Flynn
Fixes 1 test262 test.
2021-06-12AK: Rename Vector::append(Vector) => Vector::extend(Vector)Andreas Kling
Let's make it a bit more clear when we're appending the elements from one vector to the end of another vector.
2021-06-06LibRegex: Fix compilation errors on my host machineLinus Groh
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)
2021-06-02LibRegex: Hide stray dbgln() behind REGEX_DEBUGLinus Groh
2021-06-01Everywhere: codepoint => code pointAndreas Kling
2021-05-31LibRegex: Replace fprintf()/printf() with warnln()/outln()/dbgln()Linus Groh
2021-05-01Everywhere: Turn #if *_DEBUG into dbgln_if/if constexprGunnar Beutner
2021-04-22Everything: Move to SPDX license identifiers in all files.Brian Gianforcaro
SPDX License Identifiers are a more compact / standardized way of representing file license information. See: https://spdx.dev/resources/use/#identifiers This was done with the `ambr` search and replace tool. ambr --no-parent-ignore --key-from-file --rep-from-file key.txt rep.txt *
2021-04-12LibRegex: Generate a 'Compare' op for empty character classesAnotherTest
Otherwise it would match zero-length strings. Fixes #6256.
2021-04-10LibRegex: Remove 'ReadDigitFollowPolicy' as it's no longer neededAnotherTest
Thanks to @GMTA: https://github.com/SerenityOS/serenity/commit/1b071455b1793dbfc7039a9090540ba0aeaf3221#r49343474
2021-04-10LibRegex: Treat brace quantifiers with invalid contents as literalsAnotherTest
Fixes #6208.
2021-04-10LibRegex: Allow a '?' suffix for brace quantifiersAnotherTest
This fixes another compat point in #6042.
2021-04-09LibRegex: Parse `\0` as a zero-byte instead of 0x30 ("0")Jelle Raaijmakers
This was causing some regexes to trip up. Fixes #6202.
2021-04-05LibRegex: Consider named capture groups as normal capture groups tooAnotherTest
2021-04-05LibRegex: Reset capture group indices when resetting parser stateAnotherTest
2021-04-01LibRegex: Allow references to capture groups that aren't parsed yetAnotherTest
This only applies to the ECMA262 parser. This behaviour is an ECMA262-specific quirk, such references always generate zero-length matches (even on subsequent passes). Also adds a test in LibJS's test suite. Fixes #6039.
2021-02-27LibRegex: Allow missing high bound in {x,y} quantifiersAnotherTest
Fixes #5518.
2021-02-27LibRegex: Match the escaped part of escaped syntax charactersAnotherTest
Previously, `\^` would've matched `\`, not `^`.
2021-02-27LibRegex: Implement section B.1.4. of the ECMA262 specAnotherTest
This allows the parser to deal with crazy patterns like the one in #5517.
2021-02-23Everywhere: Rename ASSERT => VERIFYAndreas Kling
(...and ASSERT_NOT_REACHED => VERIFY_NOT_REACHED) Since all of these checks are done in release builds as well, let's rename them to VERIFY to prevent confusion, as everyone is used to assertions being compiled out in release. We can introduce a new ASSERT macro that is specifically for debug checks, but I'm doing this wholesale conversion first since we've accumulated thousands of these already, and it's not immediately obvious which ones are suitable for ASSERT.
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-17 14:49:19 +0000