Skip to content

Commit e6d0f57

Browse files
sosukesuzukisosukesuzuki
committed
[YARR] String list fast path drops a non-final empty alternative
https://bugs.webkit.org/show_bug.cgi?id=316288 Reviewed by Yusuke Suzuki. A regex like /^(?:c||b)/ matched against "bccc" returned "b" under the RegExp JIT instead of the empty string. The JIT "string list" fast path plants each alternative's success jump off its character comparisons, so an empty alternative emits no jump and execution falls through into the next alternative as if the empty one had failed. The interpreter and the spec match the empty alternative and return a zero-length match. Without a trailing end-of-line anchor a string list is terminal: the first empty alternative always matches and ends the overall match, so any alternatives after it are unreachable. Drop them while building the pattern, which leaves the empty alternative last so the JIT matches it via its existing fall-through success path. Alternatives after an empty one are kept when the list is end-of-line anchored, since there the empty alternative does not guarantee an overall match. * JSTests/stress/regexp-string-list-empty-alternative.js: Added. * Source/JavaScriptCore/yarr/YarrPattern.cpp: (JSC::Yarr::YarrPatternConstructor::checkForTerminalParentheses): Canonical link: https://commits.webkit.org/314686@main
1 parent d376be4 commit e6d0f57

2 files changed

Lines changed: 98 additions & 2 deletions

File tree

‎JSTests/stress/regexp-string-list-empty-alternative.js‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
// Test that the Yarr string list fast path correctly matches an empty
2+
// alternative that is not the last alternative, e.g. /^(?:c||b)/.
3+
4+
function shouldBe(actual, expected, message) {
5+
if (actual !== expected)
6+
throw new Error((message ? message + ": " : "") + "expected " + JSON.stringify(expected) + " but got " + JSON.stringify(actual));
7+
}
8+
9+
function shouldBeMatch(result, expectedStrings, expectedIndex, message) {
10+
if (expectedStrings === null) {
11+
shouldBe(result, null, message);
12+
return;
13+
}
14+
if (result === null)
15+
throw new Error((message ? message + ": " : "") + "expected a match but got null");
16+
shouldBe(result.length, expectedStrings.length, message + " (length)");
17+
for (var i = 0; i < expectedStrings.length; ++i)
18+
shouldBe(result[i], expectedStrings[i], message + " [" + i + "]");
19+
shouldBe(result.index, expectedIndex, message + " (index)");
20+
}
21+
22+
// Empty alternative in the middle.
23+
shouldBeMatch(/^(?:c||b)/.exec("bccc"), [""], 0, "/^(?:c||b)/ vs \"bccc\"");
24+
shouldBeMatch(/^(?:c||b)/.exec("cccc"), ["c"], 0, "/^(?:c||b)/ vs \"cccc\"");
25+
shouldBeMatch(/^(?:c||b)/.exec("zzzz"), [""], 0, "/^(?:c||b)/ vs \"zzzz\"");
26+
shouldBeMatch(/^(?:c||b)/.exec(""), [""], 0, "/^(?:c||b)/ vs \"\"");
27+
28+
// Empty alternative first.
29+
shouldBeMatch(/^(?:|c)/.exec("c"), [""], 0, "/^(?:|c)/ vs \"c\"");
30+
shouldBeMatch(/^(?:|foo|bar)/.exec("bar"), [""], 0, "/^(?:|foo|bar)/ vs \"bar\"");
31+
32+
// Multiple empty alternatives.
33+
shouldBeMatch(/^(?:||b)/.exec("b"), [""], 0, "/^(?:||b)/ vs \"b\"");
34+
35+
// Empty alternative last already worked; check for regressions.
36+
shouldBeMatch(/^(?:c|b|)/.exec("bccc"), ["b"], 0, "/^(?:c|b|)/ vs \"bccc\"");
37+
shouldBeMatch(/^(?:c|b|)/.exec("zzzz"), [""], 0, "/^(?:c|b|)/ vs \"zzzz\"");
38+
39+
// Multi-character alternatives.
40+
shouldBeMatch(/^(?:foo||bar)/.exec("bar"), [""], 0, "/^(?:foo||bar)/ vs \"bar\"");
41+
shouldBeMatch(/^(?:foo||bar)/.exec("foofoo"), ["foo"], 0, "/^(?:foo||bar)/ vs \"foofoo\"");
42+
43+
// EOL anchored string lists: alternatives after an empty one stay reachable.
44+
shouldBeMatch(/^(?:c||b)$/.exec("c"), ["c"], 0, "/^(?:c||b)$/ vs \"c\"");
45+
shouldBeMatch(/^(?:c||b)$/.exec("b"), ["b"], 0, "/^(?:c||b)$/ vs \"b\"");
46+
shouldBeMatch(/^(?:c||b)$/.exec(""), [""], 0, "/^(?:c||b)$/ vs \"\"");
47+
shouldBeMatch(/^(?:c||b)$/.exec("bc"), null, 0, "/^(?:c||b)$/ vs \"bc\"");
48+
49+
// Not a string list: no BOL anchor.
50+
shouldBeMatch(/(?:c||b)/.exec("bccc"), [""], 0, "/(?:c||b)/ vs \"bccc\"");
51+
52+
// Not a string list: capturing group.
53+
shouldBeMatch(/^(c||b)/.exec("bccc"), ["", ""], 0, "/^(c||b)/ vs \"bccc\"");
54+
55+
// Not a string list: quantified group. A zero-length iteration is rejected
56+
// by RepeatMatcher, so the "b" alternative matches.
57+
shouldBeMatch(/^(?:c||b)?/.exec("bccc"), ["b"], 0, "/^(?:c||b)?/ vs \"bccc\"");
58+
59+
// String list without empty alternatives: fast path regression check.
60+
shouldBeMatch(/^(?:foo|bar|baz)/.exec("barxx"), ["bar"], 0, "/^(?:foo|bar|baz)/ vs \"barxx\"");
61+
shouldBeMatch(/^(?:foo|bar|baz)/.exec("qux"), null, 0, "/^(?:foo|bar|baz)/ vs \"qux\"");
62+
63+
// Flags.
64+
shouldBeMatch(/^(?:c||b)/i.exec("Bccc"), [""], 0, "/^(?:c||b)/i vs \"Bccc\"");
65+
shouldBeMatch(/^(?:c||b)/m.exec("x\nbc"), [""], 0, "/^(?:c||b)/m vs \"x\\nbc\"");
66+
67+
var stickyRe = /^(?:c||b)/y;
68+
stickyRe.lastIndex = 0;
69+
shouldBeMatch(stickyRe.exec("bccc"), [""], 0, "/^(?:c||b)/y vs \"bccc\"");
70+
shouldBe(stickyRe.lastIndex, 0, "sticky lastIndex after zero-length match");
71+
72+
var globalRe = /^(?:c||b)/g;
73+
globalRe.lastIndex = 0;
74+
shouldBeMatch(globalRe.exec("bccc"), [""], 0, "/^(?:c||b)/g vs \"bccc\"");
75+
shouldBe(globalRe.lastIndex, 0, "global lastIndex after zero-length match");
76+
77+
// 16-bit strings.
78+
shouldBeMatch(/^(?:あ||い)/.exec("いい"), [""], 0, "/^(?:\\u3042||\\u3044)/ vs \"\\u3044\\u3044\"");
79+
shouldBeMatch(/^(?:あ||い)/.exec("ああ"), ["あ"], 0, "/^(?:\\u3042||\\u3044)/ vs \"\\u3042\\u3042\"");
80+
81+
// test() and replace() use the same match.
82+
shouldBe(/^(?:c||b)/.test("zzz"), true, "/^(?:c||b)/.test(\"zzz\")");
83+
shouldBe("bccc".replace(/^(?:c||b)/, "X"), "Xbccc", "replace with /^(?:c||b)/");

‎Source/JavaScriptCore/yarr/YarrPattern.cpp‎

Lines changed: 15 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2013,7 +2013,7 @@ class YarrPatternConstructor {
20132013
// matched string alternative, without jumping to backtracking doe to fixup offests.
20142014
// Instead we fixup the offsets, if needed, at the top of the next alternative's
20152015
// matching JIT code.
2016-
void NODELETE checkForTerminalParentheses()
2016+
void checkForTerminalParentheses()
20172017
{
20182018
// This check is much too crude; should be just checking whether the candidate
20192019
// node contains nested capturing subpatterns, not the whole expression!
@@ -2041,9 +2041,14 @@ class YarrPatternConstructor {
20412041
PatternTerm& term = terms[1];
20422042

20432043
PatternDisjunction* nestedDisjunction = term.parentheses.disjunction;
2044+
constexpr unsigned emptyAlternativeNotFound = std::numeric_limits<unsigned>::max();
2045+
unsigned firstEmptyAlternative = emptyAlternativeNotFound;
20442046
for (unsigned alt = 0; isStringList && alt < nestedDisjunction->m_alternatives.size(); ++alt) {
20452047
Vector<PatternTerm>& innerTerms = nestedDisjunction->m_alternatives[alt]->m_terms;
20462048

2049+
if (innerTerms.isEmpty() && firstEmptyAlternative == emptyAlternativeNotFound)
2050+
firstEmptyAlternative = alt;
2051+
20472052
for (size_t termIndex = 0; termIndex < innerTerms.size(); ++termIndex) {
20482053
PatternTerm& innerTerm = innerTerms[termIndex];
20492054
if (innerTerm.type != PatternTerm::Type::PatternCharacter
@@ -2055,8 +2060,16 @@ class YarrPatternConstructor {
20552060
}
20562061
}
20572062

2063+
bool isEOLStringList = terms.size() == 3 && terms[2].type == PatternTerm::Type::AssertionEOL;
20582064
term.parentheses.isStringList = isStringList;
2059-
term.parentheses.isEOLStringList = (terms.size() == 3 && terms[2].type == PatternTerm::Type::AssertionEOL);
2065+
term.parentheses.isEOLStringList = isEOLStringList;
2066+
2067+
// In a non-EOL string list the first empty alternative always matches and ends the match, so later
2068+
// alternatives are unreachable. Drop them so the empty alternative is last and the JIT can fall through to success.
2069+
if (isStringList && !isEOLStringList && firstEmptyAlternative != emptyAlternativeNotFound && firstEmptyAlternative + 1 < nestedDisjunction->m_alternatives.size()) {
2070+
nestedDisjunction->m_alternatives.shrink(firstEmptyAlternative + 1);
2071+
nestedDisjunction->m_alternatives.last()->m_isLastAlternative = true;
2072+
}
20602073
}
20612074

20622075
if (isStringList)

0 commit comments

Comments
 (0)