summaryrefslogtreecommitdiff
path: root/Userland/Libraries/LibRegex
AgeCommit message (Collapse)Author
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-05LibRegex: Do not return an Optional from Regex::Matcher::executeTimothy Flynn
The code path that could return an optional no longer exists as of commit: a962ee020a6310b2d7c7479aa058c15484127418
2022-02-05LibRegex: Do not continue searching input when the sticky bit is setTimothy Flynn
This partially reverts commit a962ee020a6310b2d7c7479aa058c15484127418. When the sticky bit is set, the global bit should basically be ignored except by external callers who want their own special behavior. For example, RegExp.prototype [ @@match ] will use the global flag to accumulate consecutive matches. But on the first failure, the regex loop should break.
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-26LibRegex: Don't return empty vectors from RegexStringView::lines()Ali Mohammad Pur
Instead, return a vector of one empty string.
2022-01-22LibRegex: Preserve capture groups and matches across ForkReplaceAli Mohammad Pur
This makes the (flawed) ForkStay inserted as a loop header unnecessary, and finally fixes LibRegex rewriting weird loops in weird ways.
2022-01-22LibRegex: Add some more information to Compare::Reference debug outputAli Mohammad Pur
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-14AK+Everywhere: Make Variant::visit() respect the Variant's constnessAli Mohammad Pur
...and fix all the instances of visit() taking non-const arguments.
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: Remove duplicate declaration of execution_result_name(...)Hendiadyoin1
2021-12-21LibRegex: Use AK::any_of in Parser::lookahead_anyHendiadyoin1
Equivalent to std::ranges::any_of, which clang-tidy suggests.
2021-12-21LibRegex: Capture `this` explicitly in RegexStringView::equals lambdaHendiadyoin1
This stops clang-tidy from suggesting that this function can be made static, although accessing `this->operator==` in the lambda function.
2021-12-21LibRegex: Remove some meaningless/useless const-qualifiersHendiadyoin1
Also replace String creation from `""` with `String::empty()`
2021-12-21LibRegex: Collapse some `if(...) return true; else return false;` blocksHendiadyoin1
2021-12-21LibRegex: Remove some else-after-returnsHendiadyoin1
2021-12-21LibRegex: Add some implied auto qualifiersHendiadyoin1
2021-12-21LibRegex: Make append_alternation() significantly fasterAli Mohammad Pur
...by flattening the underlying bytecode chunks first. Also avoid calling DisjointChunks::size() inside a loop. This is a very significant improvement in performance, making the compilation of a large regex with lots of alternatives take only ~100ms instead of many minutes (I ran out of patience waiting for it) :^)
2021-12-21LibRegex: Avoid calling DisjointChunks::size() in get_opcode()Ali Mohammad Pur
That method is O(n), and should generally be avoided.
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-17AK: Convert AK::Format formatting helpers to returning ErrorOr<void>Andreas Kling
This isn't a complete conversion to ErrorOr<void>, but a good chunk. The end goal here is to propagate buffer allocation failures to the caller, and allow the use of TRY() with formatting functions.
2021-11-13LibRegex: Correctly translate BRE pattern end anchorsTim Schumacher
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.
2021-11-11Everywhere: Pass AK::StringView by valueAndreas Kling
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-23AK: Prevent accidental misuse of BumpAllocatorBen Wiederhake
In particular, we implicitly required that the caller initializes the returned instances themselves (solved by making UniformBumpAllocator::allocate call the constructor), and BumpAllocator itself cannot handle classes that are not trivially deconstructible (solved by deleting the method). Co-authored-by: Ali Mohammad Pur <ali.mpfard@gmail.com>
2021-10-09LibRegex: Transform 0,1 min/unbounded max repetitions to * or +Ali Mohammad Pur
The implementation of transform_bytecode_repetition_min_max expects at least min=1, so let's also optimise on our way out of a bug where 'x{0,}' would cause a crash.
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-10-03LibRegex: Avoid creating a new temporary RegexStringView in Char compareAli Mohammad Pur
Instead of making a new string to compare against, simply grab the first code unit of the input and compare against that.
2021-10-02LibJS+AK: Use Vector<u16, 1> for UTF-16 string storageAndreas Kling
It's very common to encounter single-character strings in JavaScript on the web. We can make such strings significantly lighter by having a 1-character inline capacity on the Vectors.
2021-10-02LibRegex: Don't emit signpost events for every regular expressionAndreas Kling
The time we were spending on these signposts was adding up to way too much, so let's not do it automatically.
2021-10-01Libraries: Fix typosNico Weber
2021-09-29LibRegex: Flatten bytecode before performing optimizationsAndreas Kling
This avoids doing DisjointChunks traversal for every bytecode access, significantly reducing startup time for large regular expressions.
2021-09-21Libraries: Use AK::Variant default initialization where appropriateBen Wiederhake
2021-09-16LibRegex: Pass RegexStringView and Vector<RegexStringView> by referenceBrian Gianforcaro
Flagged by pvs-studio, it looks like these were intended to be passed by reference originally, but it was missed. This avoids excessive argument copy when searching / matching in the regex API. Before: Command: /usr/Tests/LibRegex/Regex --bench Average time: 5998.29 ms (median: 5991, stddev: 102.18) After: Command: /usr/Tests/LibRegex/Regex --bench Average time: 5623.2 ms (median: 5623, stddev: 86.25)
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-14LibRegex: Avoid using GenericLexer::consume() when at eofAli Mohammad Pur
Fixes #10027.
2021-09-14LibRegex: Avoid excessive Vector copy when compiling regexpsAli Mohammad Pur
Previously we would've copied the bytecode instead of moving the chunks around, use the fancy new DisjointChunks<T> abstraction to make that happen automagically. This decreases vector copies and uses of memmove() by nearly 10x :^)
2021-09-13LibRegex: Set a signpost on every executed regular expressionAli Mohammad Pur
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.
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-21 13:43:43 +0000