Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 7c5dbbcba11029727e3494d5a12ae482a542774d
https://github.com/WebKit/WebKit/commit/7c5dbbcba11029727e3494d5a12ae482a542774d
Author: Yusuke Suzuki <[email protected]>
Date: 2026-07-29 (Wed, 29 Jul 2026)
Changed paths:
A JSTests/stress/yarr-terminal-parentheses-captures.js
A JSTests/stress/yarr-terminal-parentheses-frame-layout.js
A JSTests/stress/yarr-terminal-parentheses-min-count.js
M Source/JavaScriptCore/yarr/Yarr.h
M Source/JavaScriptCore/yarr/YarrInterpreter.cpp
M Source/JavaScriptCore/yarr/YarrJIT.cpp
M Source/JavaScriptCore/yarr/YarrPattern.cpp
M Source/JavaScriptCore/yarr/YarrPattern.h
Log Message:
-----------
[YARR] Extend ParenthesesSubpatternTerminal
https://bugs.webkit.org/show_bug.cgi?id=320533
rdar://183490993
Reviewed by Yijia Huang.
Greedy * or + non-capturing parens in the tail position does not need
inter-iteration backtracking state.
1. For * case (term.quantityMinCount == 0)
Pattern like /(?:AA|A)*/ can never fail, because * succeeds even with zero
iterations.
And because it is in the tail position, all backtracking are coming from the
greedy matching attempt of (?:AA|A). This means that we will never restore
the
previous iteration's state to explore a different matching. When we failed
in the current
iteration, we can just say "the matching is complete" because we are at the
terminal position.
2. For + case (term.quantityMinCount == 1)
Pattern like /(?:AA|A)+/ will need to match at least once. If we failed in
this 1st iteration,
since this is the initial iteration, we have no context to restore, and we
can simply fail.
If we matched once and in the second iteration, if we failed to match, then
we also do not need
to restore to the 1st iteration since we already succeeded the 1st
iteration (and + suffices),
and since it is a terminal position, we can just say "the matching is
complete"
As a result, term.quantityMinCount <= 1 cases never require per-iteration
ParenContext when
we have these greedy patterns at the terminal position. Thus we can mark them
`isTerminal` to
skip ParenContext generation as an optimization.
On the other hand, term.quantityMinCount >= 2 cannot work in this way. Let's
have a RegExp matching
`/(?:AA|A){2,}/.exec("AA")`. The right answer is "AA" since "A" and "A" matches
with 2 iterations.
But this is achieved by restoring the 1st iteration and taking a different
alternative "A" instead of "AA".
Thus, inter-iteration backtracking state is necessary for this case.
Tests: JSTests/stress/yarr-terminal-parentheses-captures.js
JSTests/stress/yarr-terminal-parentheses-frame-layout.js
JSTests/stress/yarr-terminal-parentheses-min-count.js
* JSTests/stress/yarr-terminal-parentheses-captures.js: Added.
(shouldBe):
(testExec):
* JSTests/stress/yarr-terminal-parentheses-frame-layout.js: Added.
(shouldBe):
(test):
* JSTests/stress/yarr-terminal-parentheses-min-count.js: Added.
(shouldBe):
(test):
* Source/JavaScriptCore/yarr/Yarr.h:
* Source/JavaScriptCore/yarr/YarrInterpreter.cpp:
(JSC::Yarr::Interpreter::matchParenthesesTerminalBegin):
(JSC::Yarr::Interpreter::matchParenthesesTerminalEnd):
(JSC::Yarr::Interpreter::backtrackParenthesesTerminalBegin):
* Source/JavaScriptCore/yarr/YarrJIT.cpp:
* Source/JavaScriptCore/yarr/YarrPattern.cpp:
(JSC::Yarr::YarrPatternConstructor::checkForTerminalParentheses):
* Source/JavaScriptCore/yarr/YarrPattern.h:
(JSC::Yarr::BackTrackInfoParenthesesTerminal::entryPositionIndex):
Canonical link: https://commits.webkit.org/318163@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
