Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: a92d79b27748d415391c3d35e3e1df41781e4534
https://github.com/WebKit/WebKit/commit/a92d79b27748d415391c3d35e3e1df41781e4534
Author: Yusuke Suzuki <[email protected]>
Date: 2026-06-04 (Thu, 04 Jun 2026)
Changed paths:
A JSTests/stress/yarr-quantified-parentheses-unified-backtracking.js
M Source/JavaScriptCore/yarr/YarrJIT.cpp
Log Message:
-----------
[YARR] Change FixedCount model from save-at-END to save-at-BEGIN
https://bugs.webkit.org/show_bug.cgi?id=316275
rdar://178684581
Reviewed by Marcus Plutowski.
This patch improves YarrJIT FixedCount model from save-at-END (saving
the ParenContext at the end of parentheses) to save-at-BEGIN (saving the
snapshot of ParenContext at the begin of parentheses). We always save at
begin, and this is a snapshot of the complete previous iteration. If
match-amount is 0, then this means that we have never matched yet.
FixedCount was naturally fit with save-at-END model, but this makes
handling really complicated. Rather, we should always use save-at-BEGIN
model in all quantifiers so we can significantly simplify our handling
of FixedCount.
So let's summarize how it gets handled.
1. ParenthesesSubpatternsBegin.fwd
FixedCount handling is exactly the same to Greedy.
We save ParenContext at BEGIN, which is the snapshot of the previous iteration.
If this parentheses is entirely failed, then we load this snapshot and
do the previous iteration's backtracking.
Then we bump the current stack's matchAmount which indicates the current
iteration number. When it gets saved (at BEGIN), then that snapshot
captures how many iterations it succeeded before.
2. ParenthesesSubpatternsEnd.fwd
FixedCount handling is exactly the same to Greedy. We attempt to run
fixed count iterations, which is the same / similar to Greedy. If the
current iteration amount matches against quantityMaxCount, then we
stop iteration and go to the subsequent pattern. Otherwise, jumping back
to Begin's reentry to start the next iteration.
3. ParenthesesSubpatternsEnd.bt
If the subsequent pattern failed, we come to this. Greedy checks whether
it did any iteration before, and if it was completely skipped before,
then it jumps to the ParenthesesSubpatternsBegin.bt (and going to the
complete failure). On the other hand, FixedCount case means that we are
always running at least one iteration. So just fallthrough, and running
the content backtracking inside the parentheses.
4. ParenthesesSubpatternsBegin.bt
Coming here when the iteration completely failed and we need to roll
back the previous iteration and try to do content backtracking inside it.
FixedCount handling is exactly the same to Greedy again! We reload the
snapshot taken at ParenthesesSubpatternsBegin.fwd to continue backtracking
of the previous iteration. Since matchAmount of the previous iteration
was captured when it gets completed (and it is a bumped number in
ParenthesesSubpatternsBegin.fwd), we do not need to change matchAmount.
If the matchAmount is zero, then it means we exhaust all iterations, so
it is a complete failure. If the loaded matchAmount is enough compared
to min-count, then just go to the next subsequent pattern. Otherwise
jumping to the content backtracking site to continue backtracking in the
previous iteration.
Test: JSTests/stress/yarr-quantified-parentheses-unified-backtracking.js
* JSTests/stress/yarr-quantified-parentheses-unified-backtracking.js: Added.
(shouldBe):
(test):
* Source/JavaScriptCore/yarr/YarrJIT.cpp:
Canonical link: https://commits.webkit.org/314558@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
