Skip to content

Commit 5dcf3d0

Browse files
ConstellationConstellation
committed
[YARR] Use StringList optimization when captures are not used
https://bugs.webkit.org/show_bug.cgi?id=318041 rdar://180826671 Reviewed by Sosuke Suzuki. Currently StringList optimization in YarrJIT is disabled when captures are existing inside it. But if we are using MatchOnly mode & no-capture-related things exist, then we can still use this optimization since captures do not matter. To attach MatchOnly etc. on YarrPattern construction, we move JITCompileMode to ExecutionMode and use it in YarrPattern too, since Yarr::CompileMode already exists. Test: JSTests/stress/regexp-stringlist-match-only-captures.js * JSTests/stress/regexp-stringlist-match-only-captures.js: Added. (shouldBe): (test): * Source/JavaScriptCore/runtime/RegExp.cpp: (JSC::RegExp::compile): (JSC::RegExp::compileMatchOnly): * Source/JavaScriptCore/yarr/Yarr.h: * Source/JavaScriptCore/yarr/YarrJIT.cpp: (JSC::Yarr::jitCompile): (JSC::Yarr::jitCompileInlinedTest): * Source/JavaScriptCore/yarr/YarrJIT.h: * Source/JavaScriptCore/yarr/YarrPattern.cpp: (JSC::Yarr::YarrPatternConstructor::checkForTerminalParentheses): (JSC::Yarr::YarrPattern::YarrPattern): * Source/JavaScriptCore/yarr/YarrPattern.h: Canonical link: https://commits.webkit.org/315987@main
1 parent b897103 commit 5dcf3d0

7 files changed

Lines changed: 346 additions & 50 deletions

File tree

‎JSTests/stress/regexp-stringlist-match-only-captures.js‎

Lines changed: 222 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,222 @@
1+
// Coverage for the match-only StringList optimization (capturing fixed-string
2+
// alternations flattened when captures are not observed) and the
3+
// terminal-parentheses optimization generalized to match-only patterns.
4+
//
5+
// Silent on success; throws on the first discrepancy. Runs the whole battery in
6+
// a loop so every JIT tier (and, via the -interpreter companion, the Yarr
7+
// bytecode interpreter) compiles these patterns. The crux of every case: a
8+
// match-only consumer (test/search) must agree with the spec, AND the very same
9+
// source used with a capture-observing consumer (exec/match/replace) must still
10+
// report the correct captures -- proving the flattening never corrupts the
11+
// capturing compile of the same pattern.
12+
13+
function shouldBe(actual, expected, msg) {
14+
if (actual !== expected)
15+
throw new Error("bad value" + (msg ? " (" + msg + ")" : "") + ": " + actual + " expected " + expected);
16+
}
17+
18+
function shouldBeArray(actual, expected, msg) {
19+
if (actual === null)
20+
throw new Error("bad value" + (msg ? " (" + msg + ")" : "") + ": null expected " + JSON.stringify(expected));
21+
if (actual.length !== expected.length)
22+
throw new Error("bad length" + (msg ? " (" + msg + ")" : "") + ": " + actual.length + " expected " + expected.length);
23+
for (let i = 0; i < expected.length; ++i) {
24+
if (actual[i] !== expected[i])
25+
throw new Error("bad element #" + i + (msg ? " (" + msg + ")" : "") + ": " + actual[i] + " expected " + expected[i]);
26+
}
27+
}
28+
29+
// A 16-bit (non-Latin1) suffix used to force the subject string to be 16-bit so
30+
// the Char16 matcher paths are exercised too. Patterns that match a prefix can
31+
// match an ASCII prefix of a 16-bit string.
32+
const wide = "あ";
33+
34+
function test() {
35+
// --- 1. Register-style: each alternative is a single capturing group around a
36+
// literal; anchored ^(...)$; exercised match-only via test()/search(). ---
37+
{
38+
const re = new RegExp("^((t0)|(t1)|(cfr)|(sp)|(lr)|(pc)|(fr))$");
39+
for (const s of ["t0", "t1", "cfr", "sp", "lr", "pc", "fr"])
40+
shouldBe(re.test(s), true, "reg member " + s);
41+
for (const s of ["", "t", "t2", "zz", "move", "t0x", "xt0", "CFR", "sp ", " sp"])
42+
shouldBe(re.test(s), false, "reg non-member " + s);
43+
// search() is also match-only.
44+
shouldBe(re[Symbol.search]("cfr"), 0, "reg search hit");
45+
shouldBe("cfr".search(re), 0, "reg search hit 2");
46+
shouldBe("zz".search(re), -1, "reg search miss");
47+
48+
// Same source, capture-observing: captures must be exact.
49+
const m = re.exec("cfr");
50+
shouldBeArray(m, ["cfr", "cfr", undefined, undefined, "cfr", undefined, undefined, undefined, undefined], "reg exec cfr");
51+
shouldBe(m.index, 0, "reg exec index");
52+
shouldBeArray("t1".match(new RegExp("^((t0)|(t1)|(cfr)|(sp)|(lr)|(pc)|(fr))$")),
53+
["t1", "t1", undefined, "t1", undefined, undefined, undefined, undefined, undefined], "reg match t1");
54+
shouldBe("fr".replace(re, "$1/$8"), "fr/fr", "reg replace captures");
55+
}
56+
57+
// --- 2. Large generated alternation (like the offlineasm register set). ---
58+
{
59+
const regs = [];
60+
for (let i = 0; i < 6; ++i) regs.push("t" + i, "ft" + i);
61+
for (let i = 0; i < 10; ++i) regs.push("csr" + i);
62+
regs.push("cfr", "sp", "lr", "pc", "fr", "a0", "a1", "a2", "a3");
63+
const re = new RegExp("^((" + regs.join(")|(") + "))$");
64+
for (const s of regs)
65+
shouldBe(re.test(s), true, "big member " + s);
66+
for (const s of ["", "x", "t6", "csr10", "move", "loadi", "storei", "jmp", "bineq"])
67+
shouldBe(re.test(s), false, "big non-member " + s);
68+
// exec on a member still reports group 1 (the outer group) correctly.
69+
const m = re.exec("csr3");
70+
shouldBe(m[0], "csr3", "big exec[0]");
71+
shouldBe(m[1], "csr3", "big exec[1]");
72+
}
73+
74+
// --- 3. Keyword-style alternation used via test() in a boolean expression. ---
75+
{
76+
const kw = new RegExp("^((true)|(false)|(if)|(then)|(else)|(end)|(and)|(or)|(not))$");
77+
for (const s of ["true", "false", "if", "then", "else", "end", "and", "or", "not"])
78+
shouldBe(kw.test(s), true, "kw member " + s);
79+
for (const s of ["tru", "trueX", "Xtrue", "iff", "", "macro"])
80+
shouldBe(kw.test(s), false, "kw non-member " + s);
81+
}
82+
83+
// --- 4. Mixed alternatives: capturing groups, bare strings, non-capturing. ---
84+
{
85+
const mix = /^((foo)|bar|(baz)|(?:qux))$/;
86+
for (const s of ["foo", "bar", "baz", "qux"])
87+
shouldBe(mix.test(s), true, "mix member " + s);
88+
for (const s of ["fo", "barX", "quxx", "", "FOO"])
89+
shouldBe(mix.test(s), false, "mix non-member " + s);
90+
shouldBeArray(mix.exec("baz"), ["baz", "baz", undefined, "baz"], "mix exec baz");
91+
shouldBeArray(mix.exec("bar"), ["bar", "bar", undefined, undefined], "mix exec bar");
92+
shouldBeArray(mix.exec("qux"), ["qux", "qux", undefined, undefined], "mix exec qux");
93+
}
94+
95+
// --- 5. Non-EOL prefix string list (no trailing $). Exercises 16-bit subjects. ---
96+
{
97+
const pre = /^((alpha)|(beta)|(gamma)|(delta)|(epsilon)|(zeta)|(eta)|(theta))/;
98+
shouldBe(pre.test("alphaXYZ"), true, "prefix alpha");
99+
shouldBe(pre.test("thetabeta"), true, "prefix theta");
100+
shouldBe(pre.test("zzz"), false, "prefix miss");
101+
shouldBe(pre.test("alph"), false, "prefix partial");
102+
// 16-bit subject whose ASCII prefix matches.
103+
shouldBe(pre.test("gamma" + wide), true, "prefix 16-bit gamma");
104+
shouldBe(pre.test(wide + "gamma"), false, "prefix 16-bit leading-wide");
105+
shouldBe(pre.exec("delta!")[5], "delta", "prefix exec capture");
106+
}
107+
108+
// --- 6. ignore-case. ---
109+
{
110+
const ci = new RegExp("^((AA)|(BB)|(CC)|(DD)|(EE)|(FF)|(GG)|(HH))$", "i");
111+
shouldBe(ci.test("aa"), true, "ci aa");
112+
shouldBe(ci.test("Cc"), true, "ci Cc");
113+
shouldBe(ci.test("hh"), true, "ci hh");
114+
shouldBe(ci.test("zz"), false, "ci zz");
115+
shouldBeArray(ci.exec("dd"), ["dd", "dd", undefined, undefined, undefined, "dd", undefined, undefined, undefined, undefined], "ci exec dd");
116+
}
117+
118+
// --- 7. multiline: ^/$ match at line boundaries; result must stay correct. ---
119+
{
120+
const ml = new RegExp("^((aa)|(bb)|(cc)|(dd)|(ee)|(ff)|(gg)|(hh))$", "m");
121+
shouldBe(ml.test("xx\ncc\nyy"), true, "ml cc");
122+
shouldBe(ml.test("xxbbyy"), false, "ml no-boundary");
123+
shouldBe(ml.test("zz\nqq"), false, "ml miss");
124+
shouldBe(ml.exec("xx\ndd\nyy").index, 3, "ml exec index");
125+
}
126+
127+
// --- 8. Empty alternative in the list (matches empty -> always succeeds). ---
128+
{
129+
const emptyEOL = /^((aa)|(bb)|()|(cc)|(dd)|(ee)|(ff)|(gg))$/;
130+
shouldBe(emptyEOL.test(""), true, "emptyEOL empty");
131+
shouldBe(emptyEOL.test("aa"), true, "emptyEOL aa");
132+
shouldBe(emptyEOL.test("zz"), false, "emptyEOL zz");
133+
const emptyNonEOL = /^((aa)|(bb)|()|(cc)|(dd)|(ee)|(ff)|(gg))/;
134+
shouldBe(emptyNonEOL.test("anything"), true, "emptyNonEOL always");
135+
shouldBe(emptyNonEOL.test(""), true, "emptyNonEOL empty");
136+
}
137+
138+
// --- 9. Fallback shapes that must NOT be flattened but stay correct. ---
139+
{
140+
// Backreference -> capture is observable even match-only; no flatten.
141+
const br = /^((aa)\2|(bb)|(cc)|(dd)|(ee)|(ff)|(gg)|(hh))$/;
142+
shouldBe(br.test("aaaa"), true, "br aaaa");
143+
shouldBe(br.test("bb"), true, "br bb");
144+
shouldBe(br.test("aa"), false, "br aa-only");
145+
shouldBeArray(br.exec("aaaa"), ["aaaa", "aaaa", "aa", undefined, undefined, undefined, undefined, undefined, undefined, undefined], "br exec");
146+
147+
// Named groups -> no flatten; captures correct.
148+
const named = /^((?<x>aa)|(bb)|(cc)|(dd)|(ee)|(ff)|(gg)|(hh))$/;
149+
shouldBe(named.test("aa"), true, "named aa");
150+
shouldBe(named.test("zz"), false, "named zz");
151+
shouldBe(named.exec("aa").groups.x, "aa", "named group x");
152+
153+
// Quantified inner group -> not a pure fixed string; falls back.
154+
const quant = /^((t0)|(t1)?|(cc)|(dd)|(ee)|(ff)|(gg)|(hh))$/;
155+
shouldBe(quant.test("t0"), true, "quant t0");
156+
shouldBe(quant.test("t1"), true, "quant t1");
157+
shouldBe(quant.test(""), true, "quant empty (t1? empty)");
158+
shouldBe(quant.test("zz"), false, "quant zz");
159+
160+
// Deeper nesting inside an alternative -> not unwrappable; falls back.
161+
const deep = /^(((ab))|(cd)|(ee)|(ff)|(gg)|(hh)|(ii))$/;
162+
shouldBe(deep.test("ab"), true, "deep ab");
163+
shouldBe(deep.test("cd"), true, "deep cd");
164+
shouldBe(deep.test("zz"), false, "deep zz");
165+
shouldBe(deep.exec("ab")[3], "ab", "deep inner capture");
166+
}
167+
168+
// --- 10. Terminal-parentheses optimization in match-only with captures elsewhere. ---
169+
{
170+
// Trailing greedy non-capturing group; capture (\d+) elsewhere.
171+
const t1 = /(\d+)x(?:ab)*/;
172+
shouldBe(t1.test("12xababab"), true, "term t1 a");
173+
shouldBe(t1.test("7x"), true, "term t1 b");
174+
shouldBe(t1.test("nope"), false, "term t1 c");
175+
shouldBeArray(t1.exec("12xabab"), ["12xabab", "12"], "term t1 exec");
176+
177+
// Multi-alternative terminal group.
178+
const t2 = /(\w)(?:ab|cd)*/;
179+
shouldBe(t2.test("zabcdab"), true, "term t2 a");
180+
shouldBe(t2.test("z"), true, "term t2 b");
181+
shouldBe(t2.exec("zabcd")[1], "z", "term t2 exec");
182+
183+
// Terminal candidate that CONTAINS a nested capture: must stay correct
184+
// (guard keeps it off the terminal fast path).
185+
const t3 = /q(?:(a)b)*/;
186+
shouldBe(t3.test("qababab"), true, "term t3 a");
187+
shouldBe(t3.test("q"), true, "term t3 b");
188+
shouldBeArray(t3.exec("qabab"), ["qabab", "a"], "term t3 exec");
189+
190+
// Capturing trailing group must not be terminal-marked; captures correct.
191+
const t4 = /m(\d)*/;
192+
shouldBe(t4.test("m123"), true, "term t4 a");
193+
shouldBe(t4.exec("m123")[1], "3", "term t4 exec last iter");
194+
195+
// No-capture trailing greedy (the originally-supported shape).
196+
const t5 = /foo(?:x)*/;
197+
shouldBe(t5.test("fooxxxx"), true, "term t5 a");
198+
shouldBe(t5.test("bar"), false, "term t5 b");
199+
}
200+
201+
// --- 11. Single-character alternatives (length-1 fixed strings). ---
202+
{
203+
const ch = /^((a)|(b)|(c)|(d)|(e)|(f)|(g)|(h))$/;
204+
for (const s of ["a", "c", "h"])
205+
shouldBe(ch.test(s), true, "ch member " + s);
206+
for (const s of ["", "z", "ab"])
207+
shouldBe(ch.test(s), false, "ch non-member " + s);
208+
shouldBeArray(ch.exec("c"), ["c", "c", undefined, undefined, "c", undefined, undefined, undefined, undefined, undefined], "ch exec c");
209+
}
210+
211+
// --- 12. Varying-length EOL alternatives (length-sort path). ---
212+
{
213+
const vl = /^((a)|(bb)|(ccc)|(dddd)|(ee)|(f)|(gggg)|(hh))$/;
214+
for (const s of ["a", "bb", "ccc", "dddd", "ee", "f", "gggg", "hh"])
215+
shouldBe(vl.test(s), true, "vl member " + s);
216+
for (const s of ["", "aa", "cccc", "ddddd", "z"])
217+
shouldBe(vl.test(s), false, "vl non-member " + s);
218+
}
219+
}
220+
221+
for (let i = 0; i < 200; ++i)
222+
test();

‎Source/JavaScriptCore/runtime/RegExp.cpp‎

Lines changed: 14 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -274,7 +274,7 @@ void RegExp::compile(VM* vm, Yarr::CharSize charSize, std::optional<StringView>
274274
&& !pattern.m_containsLookbehinds
275275
) {
276276
auto& jitCode = ensureRegExpJITCode();
277-
Yarr::jitCompile(pattern, m_patternString, charSize, sampleString, vm, jitCode, Yarr::JITCompileMode::IncludeSubpatterns);
277+
Yarr::jitCompile(pattern, m_patternString, charSize, sampleString, vm, jitCode, Yarr::ExecutionMode::IncludeSubpatterns);
278278
if (!jitCode.failureReason()) {
279279
m_state = JITCode;
280280
return;
@@ -317,8 +317,8 @@ bool RegExp::matchConcurrently(
317317
void RegExp::compileMatchOnly(VM* vm, Yarr::CharSize charSize, std::optional<StringView> sampleString)
318318
{
319319
Locker locker { cellLock() };
320-
321-
Yarr::YarrPattern pattern(m_patternString, m_flags, m_constructionErrorCode);
320+
321+
Yarr::YarrPattern pattern(m_patternString, m_flags, m_constructionErrorCode, Yarr::ExecutionMode::MatchOnly);
322322
if (hasError(m_constructionErrorCode)) {
323323
m_state = ParseError;
324324
return;
@@ -342,7 +342,7 @@ void RegExp::compileMatchOnly(VM* vm, Yarr::CharSize charSize, std::optional<Str
342342
&& !pattern.m_containsLookbehinds
343343
) {
344344
auto& jitCode = ensureRegExpJITCode();
345-
Yarr::jitCompile(pattern, m_patternString, charSize, sampleString, vm, jitCode, Yarr::JITCompileMode::MatchOnly);
345+
Yarr::jitCompile(pattern, m_patternString, charSize, sampleString, vm, jitCode, Yarr::ExecutionMode::MatchOnly);
346346
if (!jitCode.failureReason()) {
347347
m_state = JITCode;
348348
return;
@@ -356,7 +356,16 @@ void RegExp::compileMatchOnly(VM* vm, Yarr::CharSize charSize, std::optional<Str
356356
dataLogLnIf(Options::dumpCompiledRegExpPatterns(), "Can't JIT this regular expression: \"/", m_patternString, "/\"");
357357

358358
m_state = ByteCode;
359-
m_regExpBytecode = byteCodeCompilePattern(vm, pattern, m_constructionErrorCode);
359+
// m_regExpBytecode is shared with capture-observing operations (exec/match) and the Yarr
360+
// interpreter has no StringList fast path, so compile it from a capture-complete pattern rather
361+
// than the match-only one above, whose capturing fixed-string alternations may have been
362+
// flattened (dropping their subpatterns) for the JIT.
363+
Yarr::YarrPattern bytecodePattern(m_patternString, m_flags, m_constructionErrorCode, Yarr::ExecutionMode::IncludeSubpatterns);
364+
if (hasError(m_constructionErrorCode)) {
365+
m_state = ParseError;
366+
return;
367+
}
368+
m_regExpBytecode = byteCodeCompilePattern(vm, bytecodePattern, m_constructionErrorCode);
360369
if (!m_regExpBytecode) {
361370
m_state = ParseError;
362371
return;

‎Source/JavaScriptCore/yarr/Yarr.h‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,12 @@ enum class SpecificPattern : uint8_t {
8585
Newlines,
8686
};
8787

88+
enum class ExecutionMode : uint8_t {
89+
MatchOnly,
90+
IncludeSubpatterns,
91+
InlineTest
92+
};
93+
8894
struct BytecodePattern;
8995

9096
} } // namespace JSC::Yarr

0 commit comments

Comments
 (0)