Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: d886174dfa9e1a4608f81260947531009eb1c31e
https://github.com/WebKit/WebKit/commit/d886174dfa9e1a4608f81260947531009eb1c31e
Author: Sosuke Suzuki <[email protected]>
Date: 2026-07-17 (Fri, 17 Jul 2026)
Changed paths:
A JSTests/stress/regexp-unicode-greedy-charclass-backtrack-exhaustive.js
A JSTests/stress/regexp-unicode-greedy-charclass-backtrack-linear.js
M Source/JavaScriptCore/yarr/YarrJIT.cpp
Log Message:
-----------
[YARR] JIT backtracking of greedy variable-width character classes in unicode
mode is `O(count)` per step
https://bugs.webkit.org/show_bug.cgi?id=319370
Reviewed by Yusuke Suzuki.
When backtracking a greedy character class that can match both BMP and
non-BMP characters under the unicode flag, backtrackCharacterClassGreedy
rewinds to the start of the term and rematches count - 1 characters
forward to recompute the index, because the width of the last matched
character is not fixed. This makes matching O(n^3) overall, while the
interpreter handles the same case in O(n^2):
/[^"]*X/u.test("\u2014" + "a".repeat(4000)) // JIT: ~9.5s, interpreter:
56ms
typescript-eslint's JSX detection regexp hits this path and makes
prettier hang for ~10 seconds on real-world input.
We can step back in O(1) instead: since all term positions in unicode
mode lie on code point boundaries, the last matched character occupied
two code units iff the two code units preceding the current position
form a surrogate pair. When the new match count is zero, we reload the
begin position from the frame instead. Also drop the storeToFrame of
the match count, which only existed so the rematch loop could reload it.
The example above now completes in 16ms (~600x), scaling as O(n^2).
Tests: JSTests/stress/regexp-unicode-greedy-charclass-backtrack-exhaustive.js
JSTests/stress/regexp-unicode-greedy-charclass-backtrack-linear.js
* JSTests/stress/regexp-unicode-greedy-charclass-backtrack-exhaustive.js: Added.
(shouldBe):
(checkSubject):
(enumerate):
* JSTests/stress/regexp-unicode-greedy-charclass-backtrack-linear.js: Added.
(shouldBe):
* Source/JavaScriptCore/yarr/YarrJIT.cpp:
Canonical link: https://commits.webkit.org/317381@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
