Skip to content

Commit 2a8223d

Browse files
ConstellationConstellation
committed
[YARR] Add auto-possession optimization
https://bugs.webkit.org/show_bug.cgi?id=316491 rdar://178912776 Reviewed by Yijia Huang. This is an initial patch adding auto-possession optimization to YarrJIT. This optimization adds possessive flag to Terms. This is completely optional and implementation can leverage this additional information just if they want, but it is totally fine to ignore this flag too. When you have a code like, /a*b/, and `a` and `b` are exclusive each other, then you can find that backtracking `a` part is meaningless since once-`a`-matched character never matches against `b`. We detect this pattern and annotate Term with possessive flag. Then YarrJIT can skip backtracking when this flag is set. Test: JSTests/stress/yarr-auto-possessification.js * JSTests/stress/yarr-auto-possessification.js: Added. (shouldBe): (test): * Source/JavaScriptCore/yarr/YarrJIT.cpp: * Source/JavaScriptCore/yarr/YarrPattern.cpp: (JSC::Yarr::YarrPatternConstructor::optimizePossessiveQuantifiers): (JSC::Yarr::YarrPattern::compile): (JSC::Yarr::PatternTerm::dumpQuantifier): * Source/JavaScriptCore/yarr/YarrPattern.h: (JSC::Yarr::PatternTerm::capture const): (JSC::Yarr::PatternTerm::possessive const): (JSC::Yarr::PatternTerm::ignoreCase const): (JSC::Yarr::PatternTerm::multiline const): (JSC::Yarr::PatternTerm::dotAll const): (JSC::Yarr::PatternTerm::containsAnyCaptures const): (JSC::Yarr::PatternTerm::capture): Deleted. (JSC::Yarr::PatternTerm::ignoreCase): Deleted. (JSC::Yarr::PatternTerm::multiline): Deleted. (JSC::Yarr::PatternTerm::dotAll): Deleted. (JSC::Yarr::PatternTerm::containsAnyCaptures): Deleted. Canonical link: https://commits.webkit.org/314736@main
1 parent 30bf5b4 commit 2a8223d

4 files changed

Lines changed: 271 additions & 5 deletions

File tree

‎JSTests/stress/yarr-auto-possessification.js‎

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
// Regression coverage for YarrJIT auto-possessification: a Greedy single-character term
2+
// (PatternCharacter / CharacterClass) immediately followed by a mandatory term whose first
3+
// character is disjoint from the greedy term's set is matched possessively (the JIT skips the
4+
// futile give-back/retry backtracking). Results must be identical to a fully-backtracking
5+
// engine, so every case below is also validated against the Yarr interpreter and V8.
6+
// Throws on mismatch; no output on success.
7+
8+
function shouldBe(actual, expected) {
9+
if (actual !== expected)
10+
throw new Error(`bad value: got ${actual}, expected ${expected}`);
11+
}
12+
13+
function match(re, str) {
14+
let m = re.exec(str);
15+
return m === null ? "null" : JSON.stringify(Array.from(m).map(x => x === undefined ? null : x)) + "@" + m.index;
16+
}
17+
18+
function test(reSource, flags, str, expected) {
19+
// Compile once and run hot so the JIT tiers up and the possessive backtrack path runs.
20+
let re = new RegExp(reSource, flags);
21+
for (let i = 0; i < 200; ++i)
22+
shouldBe(match(re, str), expected);
23+
}
24+
25+
// --- Greedy followed by a disjoint mandatory single character (the possessified case) ---
26+
// Successful matches must still produce the correct longest match.
27+
test("[0-9a-f]{1,4}:", "", "abcd:", '["abcd:"]@0');
28+
test("[0-9a-f]{1,4}:", "", "a:", '["a:"]@0');
29+
test("^([0-9a-f]{1,4}:)+x$", "", "abcd:1:ef01:x", '["abcd:1:ef01:x","ef01:"]@0');
30+
test("^[0-9]+\\.[0-9]+$", "", "123.456", '["123.456"]@0');
31+
test("^[a-z]+-end$", "", "hello-end", '["hello-end"]@0');
32+
test("a+b", "", "aaab", '["aaab"]@0');
33+
34+
// --- Failing inputs: possessification must not change the (non-)match ---
35+
test("^([0-9a-f]{1,8}-)+x$", "", "abcdef12-abcdef12-y", "null");
36+
test("[0-9a-f]{1,4}:", "", "abcd", "null");
37+
test("^[0-9]+\\.[0-9]+$", "", "123.", "null");
38+
test("a+b", "", "aaac", "null");
39+
test("^([0-9a-f]{1,4}:){7}(?:[0-9a-f]{1,4}|:)$", "", "2001:db8:0:1:1:1:1::1", "null");
40+
41+
// --- Overlapping follower: MUST NOT be possessified (give-back is required) ---
42+
test("a+a$", "", "aaaa", '["aaaa"]@0'); // 'a+' followed by 'a' (same char): must give back one.
43+
test("a+ab", "", "aaab", '["aaab"]@0'); // 'a+' must yield the 'a' that 'ab' needs.
44+
test("[0-9]+[0-9a-f]+g$", "", "12ffg", '["12ffg"]@0'); // overlapping classes.
45+
test("[0-9]+[5-9]z$", "", "1239z", '["1239z"]@0'); // overlapping ranges: give-back needed.
46+
47+
// --- ignoreCase: class folds in case; follower case-insensitive ---
48+
test("[a-z]+;", "i", "ABCdef;", '["ABCdef;"]@0');
49+
test("[a-z]+X", "i", "abcx", '["abcx"]@0'); // follower 'X' under /i matches 'x' which IS in [a-z]: must not possessify.
50+
51+
// --- Disjoint follower under /i where follower has no case (digit/punct) ---
52+
test("[a-z]+9", "i", "ABc9", '["ABc9"]@0');
53+
54+
// --- Greedy CharacterClass followed by disjoint class-shaped literal, with captures intact ---
55+
test("^(\\d{1,3})\\.(\\d{1,3})$", "", "12.250", '["12.250","12","250"]@0');
56+
57+
// --- Quantified parentheses wrapping a possessive inner term (IPv6-like) ---
58+
test("^(?:[0-9a-f]{1,4}:){2}[0-9a-f]{1,4}$", "", "ab:cd:ef", '["ab:cd:ef"]@0');
59+
test("^(?:[0-9a-f]{1,4}:){2}[0-9a-f]{1,4}$", "", "ab:cd:", "null");
60+
61+
// === Unicode (/u) and unicodeSets (/v): surrogate-pair decode and case-fold soundness ===
62+
// All expected values below were cross-checked against V8 (a fully-backtracking engine).
63+
64+
// --- Non-BMP greedy PatternCharacter + disjoint BMP follower: give-back must be doubled
65+
// (2 code units per matched code point). ---
66+
test("\\u{1F600}+x", "u", "\u{1F600}\u{1F600}\u{1F600}x", '["\u{1F600}\u{1F600}\u{1F600}x"]@0');
67+
test("\\u{1F600}+x", "u", "\u{1F600}\u{1F600}\u{1F600}y", "null"); // possessive give-back is futile.
68+
69+
// --- Non-BMP, fixed-width CharacterClass greedy + disjoint follower (count << 1 give-back). ---
70+
test("[\\u{1F600}-\\u{1F610}]+!", "u", "\u{1F600}\u{1F601}\u{1F602}!", '["\u{1F600}\u{1F601}\u{1F602}!"]@0');
71+
test("[\\u{1F600}-\\u{1F610}]+!", "u", "\u{1F600}\u{1F601}\u{1F602}?", "null");
72+
// Bounded greedy: possessive at index 0 fails, engine still finds the later non-anchored match.
73+
test("[\\u{1F600}-\\u{1F610}]{1,3}!", "u", "\u{1F600}\u{1F601}\u{1F602}\u{1F603}!", '["\u{1F601}\u{1F602}\u{1F603}!"]@2');
74+
75+
// --- Variable-width class (mixes BMP + non-BMP): NOT fixed width, so the JIT must fall back to
76+
// the normal per-step backtrack under surrogate decoding. Result must still be correct. ---
77+
test("[a\\u{1F600}]+!", "u", "a\u{1F600}a!", '["a\u{1F600}a!"]@0');
78+
test("[a\\u{1F600}]+!", "u", "a\u{1F600}a?", "null");
79+
80+
// --- Inverted class under /u is variable width too (JIT falls back); must stay correct. ---
81+
test("[^0-9]+5", "u", "abc5", '["abc5"]@0');
82+
test("[^0-9]+5", "u", "ab\u{1F600}c5", '["ab\u{1F600}c5"]@0');
83+
test("[^0-9]+5", "u", "abc6", "null");
84+
85+
// --- Case-fold soundness under /iu: a disjoint follower whose Unicode fold reaches a non-ASCII
86+
// char (Kelvin U+212A folds to 'k', long-s U+017F folds to 's'). The greedy [0-9]/[a-z] class
87+
// genuinely rejects those, so possessification is valid and the follower still matches them. ---
88+
test("[0-9]+k", "iu", "123K", '["123K"]@0'); // follower /k/iu matches Kelvin.
89+
test("[0-9]+s", "iu", "12ſ", '["12ſ"]@0'); // follower /s/iu matches long-s.
90+
test("[0-9]+k", "iu", "123k", '["123k"]@0');
91+
92+
// --- The dangerous case that must NOT be possessified: under /iu, [K] folds to {k,K,Kelvin},
93+
// so it DOES overlap the ASCII follower 'k' and give-back is required. (A naive analysis that
94+
// only saw the literal Kelvin code point would wrongly possessify and return null.) ---
95+
test("[\\u212A]+k", "iu", "KKKk", '["KKKk"]@0');
96+
test("[\\u212A]+k", "iu", "KKk", '["KKk"]@0');
97+
98+
// --- /v string-disjunction class: [\q{..}] is decomposed into a group, so the inner single-char
99+
// class is FixedCount (never the greedy term) and the strings are never possessified away. ---
100+
test("[\\q{ab}c]+d", "v", "ababccd", '["ababccd"]@0');
101+
test("[\\q{xy}a]+b", "v", "xyaab", '["xyaab"]@0');
102+
test("[\\q{ab}]+a", "v", "ababa", '["ababa"]@0');
103+
104+
// --- Dot (non-dotAll) is the newline class inverted: '.' rejects '\n', so '.+\n' is possessifiable.
105+
// This is the BMP path (one code unit per match). ---
106+
test(".+\\n", "", "abc\ndef", '["abc\\n"]@0');
107+
test(".+\\n", "", "abcdef", "null");
108+
test("[^0-9]+5", "", "abc5", '["abc5"]@0');
109+
test("[^0-9]+5", "", "abc6", "null");

‎Source/JavaScriptCore/yarr/YarrJIT.cpp‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2952,6 +2952,17 @@ class YarrGenerator final : public YarrJITInfo {
29522952

29532953
m_backtrackingState.link(*this, op);
29542954

2955+
if (term->possessive()) {
2956+
// When term is possessive, we do not need to do backtracking.
2957+
// Just rewind index completely and falling through to the next backtracking.
2958+
loadFromFrame(term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex(), countRegister);
2959+
if (m_decodeSurrogatePairs && !U_IS_BMP(term->patternCharacter))
2960+
m_jit.lshift32(MacroAssembler::TrustedImm32(1), countRegister);
2961+
m_jit.sub32(countRegister, m_regs.index);
2962+
m_backtrackingState.fallthrough();
2963+
return;
2964+
}
2965+
29552966
loadFromFrame(term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex(), countRegister);
29562967
m_backtrackingState.append(m_jit.branchTest32(MacroAssembler::Zero, countRegister));
29572968
m_jit.sub32(MacroAssembler::TrustedImm32(1), countRegister);
@@ -3266,6 +3277,18 @@ class YarrGenerator final : public YarrJITInfo {
32663277

32673278
m_backtrackingState.link(*this, op);
32683279

3280+
// Leveraging possessive flag to optimize this backtracking by rewinding entire matching so far.
3281+
// Important thing is possessive in YarrJIT is optional optimization flag: we can leverage this only when we can use it easily.
3282+
// We can completely ignore this flag and still this is OK.
3283+
if (term->possessive() && (!m_decodeSurrogatePairs || term->isFixedWidthCharacterClass())) {
3284+
loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), countRegister);
3285+
if (m_decodeSurrogatePairs && term->characterClass->hasNonBMPCharacters())
3286+
m_jit.lshift32(MacroAssembler::TrustedImm32(1), countRegister); // 2 code units per match.
3287+
m_jit.sub32(countRegister, m_regs.index);
3288+
m_backtrackingState.fallthrough();
3289+
return;
3290+
}
3291+
32693292
loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), countRegister);
32703293
m_backtrackingState.append(m_jit.branchTest32(MacroAssembler::Zero, countRegister));
32713294
m_jit.sub32(MacroAssembler::TrustedImm32(1), countRegister);

‎Source/JavaScriptCore/yarr/YarrPattern.cpp‎

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,7 @@
3636
#include <wtf/BitSet.h>
3737
#include <wtf/DataLog.h>
3838
#include <wtf/StackCheck.h>
39+
#include <wtf/TriState.h>
3940
#include <wtf/Vector.h>
4041

4142
WTF_ALLOW_UNSAFE_BUFFER_USAGE_BEGIN
@@ -2090,6 +2091,125 @@ class YarrPatternConstructor {
20902091
}
20912092
}
20922093

2094+
// Auto-possessification optimization
2095+
//
2096+
// "Possessive Quantifier" is yet another quantifier type supported in non-JS RegExp engines (e.g. PCRE2).
2097+
// https://www.pcre.org/current/doc/html/pcre2syntax.html
2098+
// It is like /a++/, /a*+/. This is different from Greedy quantifier (/a+/, /a*/) in particular it never does backtracking.
2099+
// Once it greedily matches, even if the subsequent pattern fails, we do not do backtracking. For example,
2100+
//
2101+
// /.*+b/ and "textb". In /.*b/ case, .* will do backtrack to spare "b" for the subsequent pattern. But possessive quantifier
2102+
// drains all text input in this case and never doing backtracking, thus match fails.
2103+
//
2104+
// The benefit of possessive quantifier is it can eliminate the cost of backtracking, so failure becomes quick due to removal
2105+
// of backtracking.
2106+
//
2107+
// While JS RegExp does not support possessive quantifiers, we can internally support and convert patterns to possessive quantifier
2108+
// if we can find this term's backtracking never produces the potentially matching cases for the subsequent patterns.
2109+
//
2110+
// Let's show an example. A greedy single-character term `T` immediately followed by a mandatory term `U` whose first character
2111+
// can never be a character that `T` matches is effectively possessive. Once `T` has matched greedily, giving characters back
2112+
// can never let `U` match (a given-back position still holds a `T` character, which `U` rejects), so all of the backtracking the
2113+
// engine would do into `T` is futile. We mark such a `T` so the JIT can skip generating (and running) that dead backtracking.
2114+
2115+
void optimizePossessiveQuantifiers()
2116+
{
2117+
auto rawClassContains = [](const CharacterClass* characterClass, char32_t ch) -> TriState {
2118+
if (characterClass->m_anyCharacter)
2119+
return TriState::True;
2120+
2121+
if (!characterClass->hasSingleCharacters())
2122+
return characterClass->m_table ? TriState::Indeterminate : TriState::False;
2123+
2124+
bool isLatin1Char = isLatin1(ch);
2125+
const auto& matches = isLatin1Char ? characterClass->m_matches8 : characterClass->m_matches32;
2126+
for (auto match : matches) {
2127+
if (match == ch)
2128+
return TriState::True;
2129+
}
2130+
const auto& ranges = isLatin1Char ? characterClass->m_ranges8 : characterClass->m_ranges32;
2131+
for (auto range : ranges) {
2132+
if (ch >= range.begin && ch <= range.end)
2133+
return TriState::True;
2134+
}
2135+
return TriState::False;
2136+
};
2137+
2138+
auto termMatchesCharacter = [&](const PatternTerm& term, char32_t ch) -> TriState {
2139+
if (term.type == PatternTerm::Type::PatternCharacter) {
2140+
char32_t pc = term.patternCharacter;
2141+
if (pc == ch)
2142+
return TriState::True;
2143+
if (term.ignoreCase()) {
2144+
if (!isASCII(pc) || !isASCII(ch))
2145+
return TriState::Indeterminate;
2146+
if (toASCIIUpper(pc) == toASCIIUpper(ch))
2147+
return TriState::True;
2148+
}
2149+
return TriState::False;
2150+
}
2151+
2152+
ASSERT(term.type == PatternTerm::Type::CharacterClass);
2153+
TriState raw = rawClassContains(term.characterClass, ch);
2154+
if (raw == TriState::Indeterminate)
2155+
return TriState::Indeterminate;
2156+
if (term.invert())
2157+
return raw == TriState::True ? TriState::False : TriState::True;
2158+
return raw;
2159+
};
2160+
2161+
// Returns true if and only if `next` (the term right after the greedy term) is mandatory and its
2162+
// first character is provably disjoint from `greedy`'s set.
2163+
auto followerForcesPossessive = [&](const PatternTerm& greedy, const PatternTerm& next) -> bool {
2164+
if (next.type != PatternTerm::Type::PatternCharacter)
2165+
return false;
2166+
2167+
if (next.quantityType != QuantifierType::FixedCount || next.quantityMinCount < 1)
2168+
return false;
2169+
2170+
// Every character `next` would accept must be rejected by `greedy`.
2171+
char32_t fc = next.patternCharacter;
2172+
if (termMatchesCharacter(greedy, fc) != TriState::False)
2173+
return false;
2174+
2175+
if (next.ignoreCase()) {
2176+
if (!isASCII(fc))
2177+
return false; // Don't reason about non-ASCII case folds.
2178+
2179+
if (termMatchesCharacter(greedy, toASCIIUpper(fc)) != TriState::False)
2180+
return false;
2181+
2182+
if (termMatchesCharacter(greedy, toASCIILower(fc)) != TriState::False)
2183+
return false;
2184+
}
2185+
return true;
2186+
};
2187+
2188+
auto isPossessifiableGreedyTerm = [](const PatternTerm& term) -> bool {
2189+
return term.quantityType == QuantifierType::Greedy && (term.type == PatternTerm::Type::PatternCharacter || term.type == PatternTerm::Type::CharacterClass);
2190+
};
2191+
2192+
for (auto& disjunction : m_pattern.m_disjunctions) {
2193+
for (auto& alternative : disjunction->m_alternatives) {
2194+
if (alternative->matchDirection() != Forward)
2195+
continue;
2196+
2197+
auto& terms = alternative->m_terms;
2198+
for (unsigned i = 1; i < terms.size(); ++i) {
2199+
PatternTerm& current = terms[i - 1];
2200+
PatternTerm& next = terms[i];
2201+
if (!isPossessifiableGreedyTerm(current))
2202+
continue;
2203+
2204+
if (!followerForcesPossessive(current, next))
2205+
continue;
2206+
2207+
current.m_possessive = true;
2208+
}
2209+
}
2210+
}
2211+
}
2212+
20932213
void optimizeBOL()
20942214
{
20952215
// Look for expressions containing beginning of line (^) anchoring and unroll them.
@@ -2706,6 +2826,7 @@ ErrorCode YarrPattern::compile(StringView patternString)
27062826
constructor.checkForTerminalParentheses();
27072827
constructor.optimizeDotStarWrappedExpressions();
27082828
constructor.optimizeBOL();
2829+
constructor.optimizePossessiveQuantifiers();
27092830

27102831
if (hasError(constructor.error()))
27112832
return constructor.error();
@@ -2885,6 +3006,8 @@ void PatternTerm::dumpQuantifier(PrintStream& out)
28853006
out.print(" greedy");
28863007
else if (quantityType == QuantifierType::NonGreedy)
28873008
out.print(" non-greedy");
3009+
if (m_possessive)
3010+
out.print(" possessive");
28883011
}
28893012

28903013
void PatternTerm::dump(PrintStream& out, YarrPattern* thisPattern, unsigned nestingDepth)

‎Source/JavaScriptCore/yarr/YarrPattern.h‎

Lines changed: 16 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -248,6 +248,12 @@ struct PatternTerm {
248248
unsigned inputPosition;
249249
unsigned frameLocation;
250250

251+
// Set by YarrPattern's auto-possessification pass for a Greedy single-character
252+
// (PatternCharacter / CharacterClass) term whose following mandatory term can never
253+
// match a character this term matches. Backtracking into such a term is always futile,
254+
// so the JIT generates a possessive (no-give-back) backtrack instead of the retry loop.
255+
bool m_possessive { false };
256+
251257
PatternTerm(char32_t ch, OptionSet<Flags> currFlags, MatchDirection matchDirection = Forward)
252258
: type(PatternTerm::Type::PatternCharacter)
253259
, m_currentFlags(currFlags)
@@ -389,22 +395,27 @@ struct PatternTerm {
389395
return m_matchDirection;
390396
}
391397

392-
bool capture()
398+
bool capture() const
393399
{
394400
return m_capture;
395401
}
396402

397-
bool NODELETE ignoreCase()
403+
bool possessive() const
404+
{
405+
return m_possessive;
406+
}
407+
408+
bool NODELETE ignoreCase() const
398409
{
399410
return m_currentFlags.contains(Flags::IgnoreCase);
400411
}
401412

402-
bool NODELETE multiline()
413+
bool NODELETE multiline() const
403414
{
404415
return m_currentFlags.contains(Flags::Multiline);
405416
}
406417

407-
bool NODELETE dotAll()
418+
bool NODELETE dotAll() const
408419
{
409420
return m_currentFlags.contains(Flags::DotAll);
410421
}
@@ -414,7 +425,7 @@ struct PatternTerm {
414425
return type == Type::CharacterClass && characterClass->hasOneCharacterSize() && !invert();
415426
}
416427

417-
bool containsAnyCaptures()
428+
bool containsAnyCaptures() const
418429
{
419430
ASSERT(this->type == Type::ParenthesesSubpattern
420431
|| this->type == Type::ParentheticalAssertion);

0 commit comments

Comments
 (0)