Skip to content

Commit bbc000a

Browse files
sosukesuzukisosukesuzuki
committed
[YARR] Read raw code units for surrogate-free BMP character classes in unicode mode
https://bugs.webkit.org/show_bug.cgi?id=320903 Reviewed by Yusuke Suzuki. With the /u and /v flags, YARR JIT decodes surrogate pairs for every character read. For a non-inverted character class holding only non-surrogate BMP code points, the decode is unnecessary: a surrogate code unit, a decoded non-BMP code point and errorCodePoint all lie outside of such a class, so testing the raw code unit is equivalent to testing the decoded code point. This patch reads the raw code unit for such character class terms (\w, \d, \s, [a-z], BMP-only property escapes ...) in unicode mode and lets them use the class's 64K m_table, which was disabled whenever surrogate pairs were being decoded. Base Patch regexp-u-flag-class-astral-subject 43.2756+-0.5243 ^ 35.8856+-1.3000 ^ definitely 1.2059x faster regexp-u-flag-character-class-greedy 88.1351+-4.7293 ^ 39.2828+-0.2972 ^ definitely 2.2436x faster Tests: JSTests/microbenchmarks/regexp-u-flag-character-class-greedy.js JSTests/microbenchmarks/regexp-u-flag-class-astral-subject.js JSTests/stress/regexp-unicode-code-unit-read-for-bmp-terms.js * JSTests/microbenchmarks/regexp-u-flag-character-class-greedy.js: Added. (splitmix32): * JSTests/microbenchmarks/regexp-u-flag-class-astral-subject.js: Added. * JSTests/stress/regexp-unicode-code-unit-read-for-bmp-terms.js: Added. (shouldBe): * Source/JavaScriptCore/yarr/YarrJIT.cpp: * Source/JavaScriptCore/yarr/YarrPattern.cpp: (JSC::Yarr::CharacterClass::hasOnlyNonSurrogateBMPCharacters const): * Source/JavaScriptCore/yarr/YarrPattern.h: (JSC::Yarr::CharacterClass::hasOnlyBMPCharacters const): Canonical link: https://commits.webkit.org/318881@main
1 parent b113f83 commit bbc000a

6 files changed

Lines changed: 154 additions & 17 deletions

File tree

‎JSTests/microbenchmarks/regexp-u-flag-character-class-greedy.js‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
// /u greedy character classes (\w, [a-z], \d) that hold no non-BMP or surrogate members, over UTF-16 text.
2+
function splitmix32(seed) {
3+
var a = seed;
4+
return function () {
5+
a |= 0; a = (a + 0x9e3779b9) | 0;
6+
var t = a ^ (a >>> 16); t = Math.imul(t, 0x21f0aaad);
7+
t = t ^ (t >>> 15); t = Math.imul(t, 0x735a2d97);
8+
return ((t = t ^ (t >>> 15)) >>> 0) / 4294967296;
9+
};
10+
}
11+
let rnd = splitmix32(42);
12+
let words = [];
13+
for (let i = 0; i < 60; ++i) {
14+
let n = 300 + (rnd() * 400 | 0);
15+
let w = "";
16+
for (let j = 0; j < n; ++j)
17+
w += String.fromCharCode(0x61 + (rnd() * 26 | 0));
18+
words.push(w + (rnd() * 100000 | 0));
19+
}
20+
let text = words.join(" あ ");
21+
22+
let identifier = /^(?:\w+(?: あ )?)+$/u;
23+
let word = /^(?:[a-z]+\d+(?: あ )?)+$/u;
24+
for (let i = 0; i < 2000; ++i) {
25+
if (!identifier.test(text) || !word.test(text))
26+
throw new Error("bad match");
27+
}

‎JSTests/microbenchmarks/regexp-u-flag-class-astral-subject.js‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
// BMP-only /u character class scanning a subject dense in surrogate pairs.
2+
let unit = "\u{1F600}a\u{1F601}bcd";
3+
let text = "";
4+
for (let i = 0; i < 4000; ++i)
5+
text += unit + (i % 10);
6+
7+
let re = /^(?:[\u{1F600}\u{1F601}]+[a-z0-9]+)+$/u;
8+
for (let i = 0; i < 1500; ++i) {
9+
if (!re.test(text))
10+
throw new Error("bad match");
11+
}

‎JSTests/stress/regexp-unicode-code-unit-read-for-bmp-terms.js‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
function shouldBe(actual, expected) {
2+
if (actual !== expected)
3+
throw new Error(`Bad value: ${actual}, expected ${expected}`);
4+
}
5+
6+
function shouldBeMatch(actual, expected) {
7+
shouldBe(JSON.stringify(actual), JSON.stringify(expected));
8+
}
9+
10+
for (let i = 0; i < 200; ++i) {
11+
// BMP-only classes reading a surrogate pair position must not match either half.
12+
shouldBeMatch(/[a-z]/u.exec("\u{1F600}b"), ["b"]);
13+
shouldBeMatch(/\w+/u.exec("\u{1F600}ab\u{1F601}"), ["ab"]);
14+
shouldBeMatch(/[\d\s]/u.exec("\uD83D 1"), [" "]);
15+
shouldBeMatch(/\w{2}\s/u.exec("ab\uD83Dcd "), ["cd "]);
16+
17+
// Reading in the middle of a surrogate pair (sticky lastIndex on the trail surrogate).
18+
let sticky = /[a-z\u{1F600}]/uy;
19+
sticky.lastIndex = 1;
20+
shouldBeMatch(sticky.exec("\u{1F600}x"), null);
21+
sticky = /\w/uy;
22+
sticky.lastIndex = 1;
23+
shouldBeMatch(sticky.exec("\u{1F600}x"), null);
24+
25+
// Lone surrogates are never members of a surrogate-free class.
26+
shouldBeMatch(/[\s\S]&&[a\uD800]/v.exec("\uD800a"), null);
27+
shouldBeMatch(/[a-z]|q/u.exec("\uDBFFz\uDC00"), ["z"]);
28+
29+
// Word boundary around non-BMP characters and lone surrogates.
30+
shouldBeMatch(/\b\w+\b/u.exec("\u{1F600}abc\u{1F600}"), ["abc"]);
31+
shouldBeMatch(/\B\w/u.exec("\uD83Dab"), ["b"]);
32+
shouldBeMatch(/a\b/u.exec("a\u{1F600}"), ["a"]);
33+
shouldBeMatch(/\bK/iu.exec("K"), ["K"]);
34+
shouldBeMatch(/\b\w\b/iu.exec("\u{1F600} ſ \u{1F600}"), ["ſ"]);
35+
36+
// Multiline anchors next to non-BMP characters.
37+
shouldBeMatch(/^b$/mu.exec("\u{1F600}\nb\n\u{1F601}"), ["b"]);
38+
shouldBeMatch(/^\w+$/mu.exec("a\u{1F600}\nxyz\n"), ["xyz"]);
39+
shouldBeMatch(/x$/mu.exec("x
"), ["x"]);
40+
41+
// A BMP pattern character next to a non-BMP class term keeps decoding for the class.
42+
shouldBeMatch(/a[\u{1F600}-\u{1F64F}]b/u.exec("xa\u{1F60D}b"), ["a\u{1F60D}b"]);
43+
shouldBeMatch(/a?\B|q/u.exec("X\u{1F600}Z"), [""]);
44+
}

‎Source/JavaScriptCore/yarr/YarrJIT.cpp‎

Lines changed: 55 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1166,26 +1166,46 @@ class YarrGenerator final : public YarrJITInfo {
11661166
matchCharacterClassOnlyOneRange(character, scratch, failMatches, ranges[0]);
11671167
}
11681168

1169-
void matchCharacterClassTable(MacroAssembler::RegisterID character, MacroAssembler::JumpList& failMatches, const char* table, bool tableInverted = false)
1169+
// For a class holding only non-surrogate BMP code points, the code unit at the current position is a
1170+
// member exactly when the decoded code point would be: a surrogate code unit, a decoded non-BMP code
1171+
// point and errorCodePoint all lie outside of such a class.
1172+
bool shouldReadRawCodeUnitForCharacterClassTerm(const PatternTerm* term)
11701173
{
1171-
ASSERT(!m_decodeSurrogatePairs);
1172-
MacroAssembler::ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(table));
1173-
failMatches.append(m_jit.branchTest8(tableInverted ? MacroAssembler::NonZero : MacroAssembler::Zero, tableEntry));
1174+
ASSERT(term->type == PatternTerm::Type::CharacterClass);
1175+
return !m_decodeSurrogatePairs || (!term->invert() && term->characterClass->hasOnlyNonSurrogateBMPCharacters());
1176+
}
1177+
1178+
void matchCharacterClassTable(MacroAssembler::RegisterID character, MatchTargets& matchTargets, const CharacterClass* charClass)
1179+
{
1180+
MacroAssembler::ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table));
1181+
if (matchTargets.hasFailedTarget())
1182+
matchTargets.appendFailed(m_jit.branchTest8(charClass->m_tableInverted ? MacroAssembler::NonZero : MacroAssembler::Zero, tableEntry));
1183+
else
1184+
matchTargets.appendSucceeded(m_jit.branchTest8(charClass->m_tableInverted ? MacroAssembler::Zero : MacroAssembler::NonZero, tableEntry));
1185+
}
1186+
1187+
void matchCharacterClass(MacroAssembler::RegisterID character, MacroAssembler::RegisterID scratch, MatchTargets matchTargets, const PatternTerm* characterClassTerm)
1188+
{
1189+
ASSERT(characterClassTerm->type == PatternTerm::Type::CharacterClass);
1190+
const CharacterClass* charClass = characterClassTerm->characterClass;
1191+
if (charClass->m_table && shouldReadRawCodeUnitForCharacterClassTerm(characterClassTerm)) {
1192+
matchCharacterClassTable(character, matchTargets, charClass);
1193+
return;
1194+
}
1195+
matchCharacterClassMatchesAndRanges(character, scratch, matchTargets, charClass);
11741196
}
11751197

11761198
void matchCharacterClass(MacroAssembler::RegisterID character, MacroAssembler::RegisterID scratch, MatchTargets matchTargets, const CharacterClass* charClass)
11771199
{
11781200
if (charClass->m_table && !m_decodeSurrogatePairs) {
1179-
if (matchTargets.hasFailedTarget()) {
1180-
MacroAssembler::ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table));
1181-
matchTargets.appendFailed(m_jit.branchTest8(charClass->m_tableInverted ? MacroAssembler::NonZero : MacroAssembler::Zero, tableEntry));
1182-
return;
1183-
}
1184-
MacroAssembler::ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table));
1185-
matchTargets.appendSucceeded(m_jit.branchTest8(charClass->m_tableInverted ? MacroAssembler::Zero : MacroAssembler::NonZero, tableEntry));
1201+
matchCharacterClassTable(character, matchTargets, charClass);
11861202
return;
11871203
}
1204+
matchCharacterClassMatchesAndRanges(character, scratch, matchTargets, charClass);
1205+
}
11881206

1207+
void matchCharacterClassMatchesAndRanges(MacroAssembler::RegisterID character, MacroAssembler::RegisterID scratch, MatchTargets matchTargets, const CharacterClass* charClass)
1208+
{
11891209
if (charClass->m_latin1Table) {
11901210
bool pureLatin1 = charClass->m_matches32.isEmpty() && charClass->m_ranges32.isEmpty();
11911211
if (m_charSize == CharSize::Char8 || pureLatin1) {
@@ -1271,7 +1291,7 @@ class YarrGenerator final : public YarrJITInfo {
12711291
// If we are matching the "any character" builtin class for non-unicode patterns,
12721292
// we only need to read the character and don't need to match as it will always succeed.
12731293
if (!characterClassToProcess->m_anyCharacter) {
1274-
matchCharacterClass(character, scratch, MatchTargets(matchDest, failures, MatchTargets::PreferredTarget::MatchSuccessFallThrough), characterClassToProcess);
1294+
matchCharacterClass(character, scratch, MatchTargets(matchDest, failures, MatchTargets::PreferredTarget::MatchSuccessFallThrough), term);
12751295
if (!matchDest.empty())
12761296
failures.append(m_jit.jump());
12771297
}
@@ -1557,12 +1577,30 @@ class YarrGenerator final : public YarrJITInfo {
15571577
m_jit.load16Unaligned(address, resultReg);
15581578
}
15591579

1580+
void readCharacterForCharacterClassTerm(Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID resultReg, const PatternTerm* term)
1581+
{
1582+
readCharacterForCharacterClassTerm(negativeCharacterOffset, resultReg, m_regs.index, term);
1583+
}
1584+
1585+
void readCharacterForCharacterClassTerm(Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID resultReg, MacroAssembler::RegisterID indexReg, const PatternTerm* term)
1586+
{
1587+
if (shouldReadRawCodeUnitForCharacterClassTerm(term))
1588+
readCharacterRaw(negativeCharacterOffset, resultReg, indexReg);
1589+
else
1590+
readCharacter(negativeCharacterOffset, resultReg, indexReg);
1591+
}
1592+
15601593
// Read a raw code unit without surrogate pair decoding. This is used for
15611594
// Boyer-Moore lookahead which is a hash-based prefilter where false positives
15621595
// are safe, so exact codepoint decoding is unnecessary.
15631596
void readCharacterRaw(Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID resultReg)
15641597
{
1565-
MacroAssembler::BaseIndex address = negativeOffsetIndexedAddress(negativeCharacterOffset, resultReg, m_regs.index);
1598+
readCharacterRaw(negativeCharacterOffset, resultReg, m_regs.index);
1599+
}
1600+
1601+
void readCharacterRaw(Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID resultReg, MacroAssembler::RegisterID indexReg)
1602+
{
1603+
MacroAssembler::BaseIndex address = negativeOffsetIndexedAddress(negativeCharacterOffset, resultReg, indexReg);
15661604

15671605
if (m_charSize == CharSize::Char8)
15681606
m_jit.load8(address, resultReg);
@@ -3262,7 +3300,7 @@ class YarrGenerator final : public YarrJITInfo {
32623300
}
32633301
}
32643302

3265-
readCharacter(op.m_checkedOffset - term->inputPosition, character);
3303+
readCharacterForCharacterClassTerm(op.m_checkedOffset - term->inputPosition, character, term);
32663304

32673305
matchCharacterClassTermInner(term, op.m_jumps, character, scratch);
32683306

@@ -3335,7 +3373,7 @@ class YarrGenerator final : public YarrJITInfo {
33353373
m_jit.sub32(m_regs.index, MacroAssembler::Imm32(scaledMaxCount), countRegister);
33363374

33373375
MacroAssembler::Label loop(&m_jit);
3338-
readCharacter(op.m_checkedOffset - term->inputPosition - scaledMaxCount, character, countRegister);
3376+
readCharacterForCharacterClassTerm(op.m_checkedOffset - term->inputPosition - scaledMaxCount, character, countRegister, term);
33393377

33403378
MacroAssembler::Label nonBMPLoop(&m_jit);
33413379

@@ -3430,7 +3468,7 @@ class YarrGenerator final : public YarrJITInfo {
34303468
MacroAssembler::Label loop(&m_jit);
34313469
failures.append(atEndOfInput());
34323470

3433-
readCharacter(op.m_checkedOffset - term->inputPosition, character);
3471+
readCharacterForCharacterClassTerm(op.m_checkedOffset - term->inputPosition, character, term);
34343472

34353473
matchCharacterClassTermInner(term, failures, character, scratch);
34363474

@@ -3546,7 +3584,7 @@ class YarrGenerator final : public YarrJITInfo {
35463584
nonGreedyFailures.append(atEndOfInput());
35473585
nonGreedyFailures.append(m_jit.branch32(MacroAssembler::Equal, countRegister, MacroAssembler::Imm32(term->quantityMaxCount)));
35483586

3549-
readCharacter(op.m_checkedOffset - term->inputPosition, character);
3587+
readCharacterForCharacterClassTerm(op.m_checkedOffset - term->inputPosition, character, term);
35503588

35513589
matchCharacterClassTermInner(term, nonGreedyFailures, character, scratch);
35523590

‎Source/JavaScriptCore/yarr/YarrPattern.cpp‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3529,6 +3529,21 @@ std::unique_ptr<CharacterClass> anycharCreate()
35293529
return characterClass;
35303530
}
35313531

3532+
bool CharacterClass::hasOnlyNonSurrogateBMPCharacters() const
3533+
{
3534+
if (hasStrings() || !hasOnlyBMPCharacters())
3535+
return false;
3536+
for (auto character : m_matches32) {
3537+
if (U_IS_SURROGATE(character))
3538+
return false;
3539+
}
3540+
for (auto& range : m_ranges32) {
3541+
if (range.end >= 0xd800 && range.begin <= 0xdfff)
3542+
return false;
3543+
}
3544+
return true;
3545+
}
3546+
35323547
std::optional<char16_t> CharacterClass::hasSharedLeadSurrogate() const
35333548
{
35343549
if (!hasOnlyNonBMPCharacters())

‎Source/JavaScriptCore/yarr/YarrPattern.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -145,11 +145,13 @@ struct CharacterClass {
145145
bool NODELETE hasNonBMPCharacters() const { return m_characterWidths & CharacterClassWidths::HasNonBMPChars; }
146146

147147
bool hasOneCharacterSize() const { return m_characterWidths == CharacterClassWidths::HasBMPChars || m_characterWidths == CharacterClassWidths::HasNonBMPChars; }
148+
bool hasOnlyBMPCharacters() const { return m_characterWidths == CharacterClassWidths::HasBMPChars; }
148149
bool hasOnlyNonBMPCharacters() const { return m_characterWidths == CharacterClassWidths::HasNonBMPChars; }
149150
bool hasStrings() const { return !m_strings.isEmpty(); }
150151
bool hasSingleCharacters() const { return !m_matches8.isEmpty() || !m_ranges8.isEmpty() || !m_matches32.isEmpty() || !m_ranges32.isEmpty(); }
151152

152153
std::optional<char16_t> hasSharedLeadSurrogate() const;
154+
bool hasOnlyNonSurrogateBMPCharacters() const;
153155

154156
Vector<Vector<char32_t>> m_strings;
155157
Vector<char32_t> m_matches8;

0 commit comments

Comments
 (0)