summaryrefslogtreecommitdiff
path: root/Tests/LibRegex
AgeCommit message (Collapse)Author
2022-11-09LibRegex: Don't treat ForkReplace* as new forksAli Mohammad Pur
2022-10-10Tests: Remove LibRegex benchmark test file that has become staleAndrew Kaster
This test file had #ifdef macros at the top that caused none of the content to be compiled unless a developer manually wanted to run the specific benchmarks within. As such, it has become stale. Remove it for now, if someone wants to restore it in an always-runnable state, we can restore the specific tests it's trying to benchmark.
2022-09-12LibRegex: Account for eof after \<x> when 'x' leads to legacy behaviourAli Mohammad Pur
2022-09-05LibUnicode+Userland: Migrate generated CLDR data to LibLocaleDataTimothy Flynn
Currently, LibUnicodeData contains the generated UCD and CLDR data. Move the UCD data to the main LibUnicode library, and rename LibUnicodeData to LibLocaleData. This is another prepatory change to migrate to LibLocale.
2022-08-29LibRegex: Explicitly check if a character falls into a table-based rangeTimothy Flynn
Previously, for a regex such as /[a-sy-z]/i, we would incorrectly think the character "u" fell into the range "a-s" because neither of the conditions "u > s && U > s" or "u < a && U < a" would be true, resulting in the lookup falling back to assuming the character is in the range. Instead, first explicitly check if the character falls into the range, rather than checking if it falls outside the range. If the explicit checks fail, then we know the character is outside the range.
2022-07-20LibRegex: Partially implement the ECMAScript unicodeSets proposalAli Mohammad Pur
This skips the new string unicode properties additions, along with \q{}.
2022-07-12Everywhere: Replace single-char StringView op. arguments with charssin-ack
This prevents us from needing a sv suffix, and potentially reduces the need to run generic code for a single character (as contains, starts_with, ends_with etc. for a char will be just a length and equality check). No functional changes.
2022-07-12Everywhere: Add sv suffix to strings relying on StringView(char const*)sin-ack
Each of these strings would previously rely on StringView's char const* constructor overload, which would call __builtin_strlen on the string. Since we now have operator ""sv, we can replace these with much simpler versions. This opens the door to being able to remove StringView(char const*). No functional changes.
2022-07-10LibRegex: Treat inverted Compare entries as disjunctionsAli Mohammad Pur
[^XYZ] is not(X | Y | Z), we used to translate this to not(X) | not(Y) | not(Z), this commit makes LibRegex interpret this pattern as not(X) & not(Y) & not(Z).
2022-07-09LibRegex: Fix lookup table-based range checks in CompareAli Mohammad Pur
The lowercase version of a range is not required to be a valid range, instead of casefolding the range and making it invalid, check twice with both cases of the input character (which are the same as the input if not insensitive). This time includes an actual test :^)
2022-07-05LibRegex: Use proper CharRange constructor instead of bit_castingAli Mohammad Pur
Otherwise the range order would be inverted.
2022-07-04LibRegex: Fully interpret the Compare Op when looking for overlapsAli Mohammad Pur
We had a really naive and simplistic implementation, which lead to various issues where the optimiser incorrectly rewrote the regex to use atomic groups; this commit fixes that.
2022-04-22LibRegex: Check inverse_matched after every op, not just at the endAli Mohammad Pur
Fixes #13755. Co-Authored-By: Damien Firmenich <fir.damien@gmail.com>
2022-04-01Everywhere: Run clang-formatIdan Horowitz
2022-02-20LibRegex: Make codegen+optimisation for alternatives much fasterAli Mohammad Pur
Just a little thinking outside the box, and we can now parse and optimise a million copies of "a|" chained together in just a second :^)
2022-02-20LibRegex: Make parse_disjunction() consume all disjunctions in one frameAli Mohammad Pur
This helps us not blow up when too many disjunctions are chained togther in the regex we're parsing. Fixes #12615.
2022-02-20LibRegex: Allow quantifiers after quantifiable assertionsAli Mohammad Pur
While quantifying assertions is very much meaningless, the specification allows them with annex B's extended grammar for browsers, so read and apply the quantifiers. Fixes #12373.
2022-02-14LibRegex: Correct the alternative matching order when one is emptyAli Mohammad Pur
Previously we were compiling `/a|/` into what effectively would be `/|a`, which is clearly incorrect.
2022-02-09LibRegex: Only skip full instructions when optimizing alternationsAli Mohammad Pur
It makes no sense to skip half of an instruction, so make sure to skip only full instructions!
2022-02-05LibRegex: Support non-ASCII whitespace characters when matching \s or \STimothy Flynn
ECMA-262 defines \s as: Return the CharSet containing all characters corresponding to a code point on the right-hand side of the WhiteSpace or LineTerminator productions. The LineTerminator production is simply: U+000A, U+000D, U+2028, or U+2029. Unfortunately there isn't a Unicode property that covers just those code points. The WhiteSpace production is: U+0009, U+000B, U+000C, U+FEFF, or any code point with the Space_Separator general category. If the Unicode generators are disabled, this will fall back to ASCII space code points.
2022-02-05LibJS+LibRegex: Don't repeat regex match in regexp_exec()Ali Mohammad Pur
LibRegex already implements this loop in a more performant way, so all LibJS has to do here is to return things in the right shape, and not loop over the input string. Previously this was a quadratic operation on string length, which lead to crazy execution times on failing regexps - now it's nice and fast :^) Note that a Regex test has to be updated to remove the stateful flag as it repeats matching on multiple strings.
2022-02-05LibRegex+LibJS: Avoid searching for more than one match in JS RegExpsAli Mohammad Pur
All of JS's regular expression APIs only want a single match, so avoid trying to produce more (which will be discarded anyway).
2022-01-26LibRegex: Implement ECMA262 multiline matching without splitting linesAli Mohammad Pur
As ECMA262 regex allows `[^]` and literal newlines to match newlines in the input string, we shouldn't split the input string into lines, rather simply make boundaries and catchall patterns capable of checking for these conditions specifically.
2022-01-22LibRegex: Allow ClearCaptureGroup to create new groupsAli Mohammad Pur
Instead of leaking all capture groups and selectively clearing some, simply avoid leaking things and only "define" the ones that need to exist. This *actually* implements the capture groups ECMA262 quirk. Also adds the test removed in the previous commit (to avoid messing up test runs across bisects).
2022-01-22Revert "LibRegex: Implement an ECMA262 Regex quirk with negative loo..."Ali Mohammad Pur
This partially reverts commit c11be92e23d899e28d45f67be24e47b2e5114d3a. That commit fixes one thing and breaks many more, a next commit will implement this quirk in a more sane way.
2022-01-21LibRegex: Allow the pattern to match the zero-length end of the stringAli Mohammad Pur
...only if Multiline is not enabled. Fixes #11940.
2022-01-21LibRegex: Implement an ECMA262 Regex quirk with negative lookaroundsAli Mohammad Pur
This implements the quirk defined by "Note 3" in section "Canonicalize" (https://tc39.es/ecma262/#sec-runtime-semantics-canonicalize-ch). Crosses off another quirk from #6042.
2022-01-21LibRegex: Correct jump offset to the start of the loop blockAli Mohammad Pur
Previously we were jumping to the new end of the previous block (created by the newly inserted ForkStay), correct the offset to jump to the correct block as shown in the comments. Fixes #12033.
2022-01-07Everywhere: Fix many spelling errorsmjz19910
2022-01-04Tests: Link some tests directly against LibUnicodeDataTimothy Flynn
These were missed in 565a880ce5a14bac817c73916e91ebfa04c8b99b. This wasn't an issue because these tests don't pledge/unveil anything, so they could happily dlopen() the library at runtime. But this is now needed in order to migrate LibUnicode towards weak symbols instead.
2021-12-25LibRegex: Make FailForks fail all forks up to the last save pointAli Mohammad Pur
This makes negative lookarounds with more than one fork behave correctly. Fixes #11350.
2021-12-21LibRegex: Parse capture group names according to the ECMA262 specdavidot
2021-12-21LibRegex: Disallow duplicate named capture groups in ECMA262 parserdavidot
2021-12-15LibRegex: Merge alternations based on blocks and not instructionsAli Mohammad Pur
The instructions can have dependencies (e.g. Repeat), so only unify equal blocks instead of consecutive instructions. Fixes #11247. Also adds the minimal test case(s) from that issue.
2021-11-18LibRegex: Avoid rewriting `a+` as `a*` as part of atomic rewritingAli Mohammad Pur
The initial `ForkStay` is only needed if the looping block has a following block, if there's no following block or the following block does not attempt to match anything, we should not insert the ForkStay, otherwise we would be rewriting `a+` as `a*` by allowing the 'end' to be executed. Fixes #10952.
2021-11-13Tests/LibRegex: Add tests for line end anchors in PosixBasicTim Schumacher
2021-11-10AK+Everywhere: Stop including Vector.h from StringView.hAndreas Kling
Preparation for using Error.h from Vector.h. This required moving some things out of line.
2021-11-08LibRegex: Don't push LibRegex's "Error" into the global namespaceAndreas Kling
2021-10-29LibRegex: Don't ignore empty alternatives in append_alternation()Ali Mohammad Pur
Doing so would cause patterns like `(a|)` to not match the empty string.
2021-10-03LibRegex: Use a match table for character classesAli Mohammad Pur
Generate a sorted, compressed series of ranges in a match table for character classes, and use a binary search to find the matches. This is about a 3-4x speedup for character class match performance. :^)
2021-09-18AK: Make Utf8View constructors inline and remove C string constructorAndreas Kling
Using StringView instead of C strings is basically always preferable. The only reason to use a C string is because you are calling a C API.
2021-09-15LibRegex: Make the optimizer understand references and capture groupsAli Mohammad Pur
Otherwise the fork in patterns like `(1+)\1` would be (incorrectly) optimized away.
2021-09-13LibRegex: Add a basic optimization passAli Mohammad Pur
This currently tries to convert forking loops to atomic groups, and unify the left side of alternations.
2021-09-07LibRegex: Use the correct capture group index in ERE bytecode generationAli Mohammad Pur
Otherwise the left and right capture instructions wouldn't point to the same capture group if there was another nested group there.
2021-09-06Tests/LibRegex: Decrease the size of the fork chain testAli Mohammad Pur
2021-09-06LibRegex: Make infinite repetitions short-circuit on empty matchesAli Mohammad Pur
This makes (addmittedly weird) patterns like `(a*)*` work correctly without going into an infinite fork loop.
2021-09-02Tests: Remove all file(GLOB) from CMakeLists in TestsAndrew Kaster
Using a file(GLOB) to find all the test files in a directory is an easy hack to get things started, but has some drawbacks. Namely, if you add a test, it won't be found again without re-running CMake. `ninja` seems to do this automatically, but it would be nice to one day stop seeing it rechecking our globbed directories.
2021-08-30LibRegex: Allow null bytes in patternAli Mohammad Pur
That check was rather pointless as the input is a StringView which knows its own bounds. Fixes #9686.
2021-08-20LibRegex: Treat pattern string characters as unsignedTimothy Flynn
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.
2021-08-19LibRegex: Allow Unicode escape sequences in capture group namesTimothy Flynn
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.
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-11 14:20:13 +0000