Log Message
[JSC] Yarr BoyerMoore search should support character-class https://bugs.webkit.org/show_bug.cgi?id=228613
Reviewed by Saam Barati.
JSTests:
* stress/regexp-bm-search-character-non-fixed-size.js: Added.
(shouldBe):
* stress/regexp-bm-search-many-candidate-zero-length.js: Added.
(shouldBe):
(regexp.a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p.q.r.s.t.u.v.w.x.y.z.0.1.2.3.4.5.6.7.8.9.t.v.n.r):
* stress/regexp-bm-search-non-fixed-size.js: Added.
(shouldBe):
Source/_javascript_Core:
This patch adds character-class support for BoyerMoore lookahead search in Yarr.
Currently, we only support fixed-sized character-class. We can extend it for repeat cases in the future.
To apply this character-class thing to jQuery's RegExp, we also allow non-fixed-sized disjunction.
For example, /aaaa.*|bbbb/'s disjunction is not fixed-sized. But still we can use (aaaa|bbbb) prefix since
this part is fixed-sized and we know minimum-size of this disjunction is 4.
Plus, instead of giving up BoyerMoore search when we found non-supported terms, we shorten BoyerMoore search
length not to include this term so that we can still have a chance to leverage BoyerMoore search. In the case
of /aaaa|bbbb|ccc(d|e|f)/, we previously gave up since it finds `(d|e|f)`. But now, instead we shorten the length
from 4 to 3, and construct search pattern with `aaa|bbb|ccc`.
This patch improves jquery-todomvc-regexp by 20%.
ToT Patched
jquery-todomvc-regexp 545.3561+-0.6968 ^ 451.6117+-0.4613 ^ definitely 1.2076x faster
This improves Speedometer2/jQuery-TodoMVC by 2%.
----------------------------------------------------------------------------------------------------------------------------------
| subtest | ms | ms | b / a | pValue (significance using False Discovery Rate) |
----------------------------------------------------------------------------------------------------------------------------------
| Elm-TodoMVC |123.470833 |123.550000 |1.000641 | 0.841600 |
| VueJS-TodoMVC |26.883333 |26.950000 |1.002480 | 0.846732 |
| EmberJS-TodoMVC |127.708333 |127.754167 |1.000359 | 0.934206 |
| BackboneJS-TodoMVC |50.545833 |50.445833 |0.998022 | 0.679610 |
| Preact-TodoMVC |20.879167 |20.791667 |0.995809 | 0.796541 |
| AngularJS-TodoMVC |137.479167 |137.275000 |0.998515 | 0.729817 |
| Vanilla-ES2015-TodoMVC |69.079167 |68.912500 |0.997587 | 0.524325 |
| Inferno-TodoMVC |65.604167 |66.120833 |1.007876 | 0.145549 |
| Flight-TodoMVC |77.029167 |76.708333 |0.995835 | 0.518562 |
| Angular2-TypeScript-TodoMVC |40.516667 |40.812500 |1.007302 | 0.513386 |
| VanillaJS-TodoMVC |54.762500 |54.895833 |1.002435 | 0.647381 |
| jQuery-TodoMVC |255.950000 |250.425000 |0.978414 | 0.000000 (significant) |
| EmberJS-Debug-TodoMVC |341.745833 |342.804167 |1.003097 | 0.219937 |
| React-TodoMVC |88.854167 |88.700000 |0.998265 | 0.568405 |
| React-Redux-TodoMVC |151.266667 |150.804167 |0.996942 | 0.256403 |
| Vanilla-ES2015-Babel-Webpack-TodoMVC |65.783333 |65.645833 |0.997910 | 0.437464 |
----------------------------------------------------------------------------------------------------------------------------------
a mean = 246.52898
b mean = 246.85128
pValue = 0.3927330278
(Bigger means are better.)
1.001 times better
Results ARE NOT significant
* yarr/YarrJIT.cpp:
(JSC::Yarr::BoyerMooreInfo::shortenLength):
(JSC::Yarr::BoyerMooreInfo::setAll):
(JSC::Yarr::BoyerMooreInfo::addCharacters):
(JSC::Yarr::BoyerMooreInfo::addRanges):
* yarr/YarrJIT.h:
(JSC::Yarr::BoyerMooreBitmap::add):
(JSC::Yarr::BoyerMooreBitmap::addCharacters):
(JSC::Yarr::BoyerMooreBitmap::addRanges):
(JSC::Yarr::BoyerMooreBitmap::setAll):
(JSC::Yarr::BoyerMooreBitmap::isAllSet const):
Modified Paths
- trunk/JSTests/ChangeLog
- trunk/Source/_javascript_Core/ChangeLog
- trunk/Source/_javascript_Core/yarr/YarrJIT.cpp
- trunk/Source/_javascript_Core/yarr/YarrJIT.h
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (280569 => 280570)
--- trunk/JSTests/ChangeLog 2021-08-02 23:39:10 UTC (rev 280569)
+++ trunk/JSTests/ChangeLog 2021-08-02 23:43:16 UTC (rev 280570)
@@ -1,5 +1,20 @@
2021-08-02 Yusuke Suzuki <[email protected]>
+ [JSC] Yarr BoyerMoore search should support character-class
+ https://bugs.webkit.org/show_bug.cgi?id=228613
+
+ Reviewed by Saam Barati.
+
+ * stress/regexp-bm-search-character-non-fixed-size.js: Added.
+ (shouldBe):
+ * stress/regexp-bm-search-many-candidate-zero-length.js: Added.
+ (shouldBe):
+ (regexp.a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p.q.r.s.t.u.v.w.x.y.z.0.1.2.3.4.5.6.7.8.9.t.v.n.r):
+ * stress/regexp-bm-search-non-fixed-size.js: Added.
+ (shouldBe):
+
+2021-08-02 Yusuke Suzuki <[email protected]>
+
[JSC] Update test262
https://bugs.webkit.org/show_bug.cgi?id=228709
Added: trunk/JSTests/stress/regexp-bm-search-character-non-fixed-size.js (0 => 280570)
--- trunk/JSTests/stress/regexp-bm-search-character-non-fixed-size.js (rev 0)
+++ trunk/JSTests/stress/regexp-bm-search-character-non-fixed-size.js 2021-08-02 23:43:16 UTC (rev 280570)
@@ -0,0 +1,14 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+let regexp = /ssssss.*ss/;
+let regexpFail = /oooooo.*oo/;
+
+for (var i = 0; i < 1e2; ++i) {
+ let matched = `aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbcccccccpppppppppppptttttttttttt<<<<<<<<<<<<<<ddddddddddddddddddddddddddddddddddddddddjjjjjjjjjjssssss src="" ssHey`.match(regexp);
+ shouldBe(matched[0], `ssssss src="" ss`);
+ let notMatched = `aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbcccccccpppppppppppptttttttttttt<<<<<<<<<<<<<<ddddddddddddddddddddddddddddddddddddddddjjjjjjjjjjssssss src="" ssHey`.match(regexpFail);
+ shouldBe(notMatched, null);
+}
Added: trunk/JSTests/stress/regexp-bm-search-many-candidate-zero-length.js (0 => 280570)
--- trunk/JSTests/stress/regexp-bm-search-many-candidate-zero-length.js (rev 0)
+++ trunk/JSTests/stress/regexp-bm-search-many-candidate-zero-length.js 2021-08-02 23:43:16 UTC (rev 280570)
@@ -0,0 +1,14 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+var regexp = /a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|0|1|2|3|4|5|6|7|8|9| |\t|\v|\n|\r|\$|\^|\&|\*|\(|\)/
+
+for (var i = 0; i < 1e2; ++i) {
+ shouldBe(regexp.test(`%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%`), false);
+ shouldBe(regexp.test(`ใในใ`), false);
+ shouldBe(regexp.test(`testing`), true);
+ shouldBe(RegExp.leftContext, ``);
+ shouldBe(RegExp.rightContext, `esting`);
+}
Added: trunk/JSTests/stress/regexp-bm-search-non-fixed-size.js (0 => 280570)
--- trunk/JSTests/stress/regexp-bm-search-non-fixed-size.js (rev 0)
+++ trunk/JSTests/stress/regexp-bm-search-non-fixed-size.js 2021-08-02 23:43:16 UTC (rev 280570)
@@ -0,0 +1,14 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+let regexp = /<script.*\/>/i;
+let regexpFail = /<scripp.*\/>/i;
+
+for (var i = 0; i < 1e2; ++i) {
+ let matched = `aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbcccccccpppppppppppptttttttttttt<<<<<<<<<<<<<<ddddddddddddddddddddddddddddddddddddddddjjjjjjjjjj<script src="" />Hey`.match(regexp);
+ shouldBe(matched[0], `<script src="" />`);
+ let notMatched = `aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbcccccccpppppppppppptttttttttttt<<<<<<<<<<<<<<ddddddddddddddddddddddddddddddddddddddddjjjjjjjjjj<script src="" />Hey`.match(regexpFail);
+ shouldBe(notMatched, null);
+}
Modified: trunk/Source/_javascript_Core/ChangeLog (280569 => 280570)
--- trunk/Source/_javascript_Core/ChangeLog 2021-08-02 23:39:10 UTC (rev 280569)
+++ trunk/Source/_javascript_Core/ChangeLog 2021-08-02 23:43:16 UTC (rev 280570)
@@ -1,3 +1,69 @@
+2021-08-02 Yusuke Suzuki <[email protected]>
+
+ [JSC] Yarr BoyerMoore search should support character-class
+ https://bugs.webkit.org/show_bug.cgi?id=228613
+
+ Reviewed by Saam Barati.
+
+ This patch adds character-class support for BoyerMoore lookahead search in Yarr.
+ Currently, we only support fixed-sized character-class. We can extend it for repeat cases in the future.
+
+ To apply this character-class thing to jQuery's RegExp, we also allow non-fixed-sized disjunction.
+ For example, /aaaa.*|bbbb/'s disjunction is not fixed-sized. But still we can use (aaaa|bbbb) prefix since
+ this part is fixed-sized and we know minimum-size of this disjunction is 4.
+
+ Plus, instead of giving up BoyerMoore search when we found non-supported terms, we shorten BoyerMoore search
+ length not to include this term so that we can still have a chance to leverage BoyerMoore search. In the case
+ of /aaaa|bbbb|ccc(d|e|f)/, we previously gave up since it finds `(d|e|f)`. But now, instead we shorten the length
+ from 4 to 3, and construct search pattern with `aaa|bbb|ccc`.
+
+ This patch improves jquery-todomvc-regexp by 20%.
+
+ ToT Patched
+
+ jquery-todomvc-regexp 545.3561+-0.6968 ^ 451.6117+-0.4613 ^ definitely 1.2076x faster
+
+ This improves Speedometer2/jQuery-TodoMVC by 2%.
+
+ ----------------------------------------------------------------------------------------------------------------------------------
+ | subtest | ms | ms | b / a | pValue (significance using False Discovery Rate) |
+ ----------------------------------------------------------------------------------------------------------------------------------
+ | Elm-TodoMVC |123.470833 |123.550000 |1.000641 | 0.841600 |
+ | VueJS-TodoMVC |26.883333 |26.950000 |1.002480 | 0.846732 |
+ | EmberJS-TodoMVC |127.708333 |127.754167 |1.000359 | 0.934206 |
+ | BackboneJS-TodoMVC |50.545833 |50.445833 |0.998022 | 0.679610 |
+ | Preact-TodoMVC |20.879167 |20.791667 |0.995809 | 0.796541 |
+ | AngularJS-TodoMVC |137.479167 |137.275000 |0.998515 | 0.729817 |
+ | Vanilla-ES2015-TodoMVC |69.079167 |68.912500 |0.997587 | 0.524325 |
+ | Inferno-TodoMVC |65.604167 |66.120833 |1.007876 | 0.145549 |
+ | Flight-TodoMVC |77.029167 |76.708333 |0.995835 | 0.518562 |
+ | Angular2-TypeScript-TodoMVC |40.516667 |40.812500 |1.007302 | 0.513386 |
+ | VanillaJS-TodoMVC |54.762500 |54.895833 |1.002435 | 0.647381 |
+ | jQuery-TodoMVC |255.950000 |250.425000 |0.978414 | 0.000000 (significant) |
+ | EmberJS-Debug-TodoMVC |341.745833 |342.804167 |1.003097 | 0.219937 |
+ | React-TodoMVC |88.854167 |88.700000 |0.998265 | 0.568405 |
+ | React-Redux-TodoMVC |151.266667 |150.804167 |0.996942 | 0.256403 |
+ | Vanilla-ES2015-Babel-Webpack-TodoMVC |65.783333 |65.645833 |0.997910 | 0.437464 |
+ ----------------------------------------------------------------------------------------------------------------------------------
+ a mean = 246.52898
+ b mean = 246.85128
+ pValue = 0.3927330278
+ (Bigger means are better.)
+ 1.001 times better
+ Results ARE NOT significant
+
+ * yarr/YarrJIT.cpp:
+ (JSC::Yarr::BoyerMooreInfo::shortenLength):
+ (JSC::Yarr::BoyerMooreInfo::setAll):
+ (JSC::Yarr::BoyerMooreInfo::addCharacters):
+ (JSC::Yarr::BoyerMooreInfo::addRanges):
+ * yarr/YarrJIT.h:
+ (JSC::Yarr::BoyerMooreBitmap::add):
+ (JSC::Yarr::BoyerMooreBitmap::addCharacters):
+ (JSC::Yarr::BoyerMooreBitmap::addRanges):
+ (JSC::Yarr::BoyerMooreBitmap::setAll):
+ (JSC::Yarr::BoyerMooreBitmap::isAllSet const):
+
2021-08-02 Stephan Szabo <[email protected]>
[PlayStation] Make C files in testapi compile with a C standard rather than C++ one
Modified: trunk/Source/_javascript_Core/yarr/YarrJIT.cpp (280569 => 280570)
--- trunk/Source/_javascript_Core/yarr/YarrJIT.cpp 2021-08-02 23:39:10 UTC (rev 280569)
+++ trunk/Source/_javascript_Core/yarr/YarrJIT.cpp 2021-08-02 23:43:16 UTC (rev 280570)
@@ -63,6 +63,11 @@
}
unsigned length() const { return m_characters.size(); }
+ void shortenLength(unsigned length)
+ {
+ ASSERT(length <= this->length());
+ m_characters.shrink(length);
+ }
void set(unsigned index, UChar32 character)
{
@@ -69,6 +74,21 @@
m_characters[index].add(character);
}
+ void setAll(unsigned index)
+ {
+ m_characters[index].setAll();
+ }
+
+ void addCharacters(unsigned index, const Vector<UChar32>& characters)
+ {
+ m_characters[index].addCharacters(characters);
+ }
+
+ void addRanges(unsigned index, const Vector<CharacterRange>& range)
+ {
+ m_characters[index].addRanges(range);
+ }
+
static UniqueRef<BoyerMooreInfo> create(unsigned length)
{
return makeUniqueRef<BoyerMooreInfo>(length);
@@ -124,6 +144,7 @@
unsigned begin = 0;
unsigned end = 0;
constexpr unsigned maxCandidatesPerCharacter = 32;
+ static_assert(maxCandidatesPerCharacter < BoyerMooreBitmap::mapSize);
for (unsigned limit = 4; limit < maxCandidatesPerCharacter; limit *= 2) {
auto [newPoint, newBegin, newEnd] = findBestCharacterSequence(limit);
if (newPoint > biggestPoint) {
@@ -2381,6 +2402,12 @@
auto [map, isMaskEffective] = op.m_bmInfo->createCandidateBitmap(beginIndex, endIndex);
unsigned mapCount = map.count();
// If candiate characters are <= 2, checking each is better than using vector.
+ JumpList outOfLengthFailure;
+ JumpList matched;
+ dataLogLnIf(YarrJITInternal::verbose, "BM Bitmap is ", map);
+ // Patterns like /[]/ have zero candidates. Since it is rare, we do not do nothing for now.
+ if (!mapCount)
+ break;
if (mapCount <= 2) {
UChar32 character1 = map.findBit(0, true);
ASSERT(character1 != BoyerMooreBitmap::Map::size());
@@ -2391,7 +2418,6 @@
}
dataLogLnIf(Options::verboseRegExpCompilation(), "Found 1-or-2 characters lookahead character:(0x", hex(character1), "),character2:(", hex(character2), "),isMaskEffective:(", isMaskEffective,"),range:[", beginIndex, ", ", endIndex, ")");
- JumpList matched;
auto loopHead = label();
readCharacter(m_checkedOffset - endIndex + 1, regT0);
if (isMaskEffective)
@@ -2399,9 +2425,8 @@
matched.append(branch32(Equal, regT0, TrustedImm32(character1)));
if (mapCount == 2)
matched.append(branch32(Equal, regT0, TrustedImm32(character2)));
- op.m_jumps.append(jumpIfNoAvailableInput(endIndex - beginIndex));
+ outOfLengthFailure.append(jumpIfNoAvailableInput(endIndex - beginIndex));
jump().linkTo(loopHead, this);
- matched.link(this);
} else {
const auto* pointer = getBoyerMooreBitmap(map);
dataLogLnIf(Options::verboseRegExpCompilation(), "Found bitmap lookahead count:(", mapCount, "),range:[", beginIndex, ", ", endIndex, ")");
@@ -2416,7 +2441,7 @@
extractUnsignedBitfield32(regT0, TrustedImm32(6), TrustedImm32(1), regT2); // Extract 1 bit for index.
load64(BaseIndex(regT1, regT2, TimesEight), regT2);
urshift64(regT0, regT2); // We can ignore upper bits and only lower 6bits are effective.
- auto matched = branchTest64(NonZero, regT2, TrustedImm32(1));
+ matched.append(branchTest64(NonZero, regT2, TrustedImm32(1)));
#elif CPU(X86_64)
static_assert(sizeof(BoyerMooreBitmap::Map::WordType) == sizeof(uint64_t));
static_assert(1 << 6 == 64);
@@ -2425,7 +2450,7 @@
urshift32(TrustedImm32(6), regT2);
and32(TrustedImm32(1), regT2);
load64(BaseIndex(regT1, regT2, TimesEight), regT2);
- auto matched = branchTestBit64(NonZero, regT2, regT0); // We can ignore upper bits since modulo-64 is performed.
+ matched.append(branchTestBit64(NonZero, regT2, regT0)); // We can ignore upper bits since modulo-64 is performed.
#else
static_assert(sizeof(BoyerMooreBitmap::Map::WordType) == sizeof(uint32_t));
static_assert(1 << 5 == 32);
@@ -2435,15 +2460,16 @@
and32(TrustedImm32(0b11), regT2);
load32(BaseIndex(regT1, regT2, TimesFour), regT2);
urshift32(regT0, regT2); // We can ignore upper bits and only lower 5bits are effective.
- auto matched = branchTest32(NonZero, regT2, TrustedImm32(1));
+ matched.append(branchTest32(NonZero, regT2, TrustedImm32(1)));
#endif
- op.m_jumps.append(jumpIfNoAvailableInput(endIndex - beginIndex));
+ outOfLengthFailure.append(jumpIfNoAvailableInput(endIndex - beginIndex));
jump().linkTo(loopHead, this);
- matched.link(this);
}
// If the pattern size is not fixed, then store the start index for use if we match.
+ // This is used for adjusting match-start when we failed to find the start with BoyerMoore search.
if (!m_pattern.m_body->m_hasFixedSize) {
+ outOfLengthFailure.link(this);
if (alternative->m_minimumSize) {
move(index, regT0);
sub32(Imm32(alternative->m_minimumSize), regT0);
@@ -2450,6 +2476,21 @@
setMatchStart(regT0);
} else
setMatchStart(index);
+ op.m_jumps.append(jump());
+ } else
+ op.m_jumps.append(outOfLengthFailure);
+
+ matched.link(this);
+ // If the pattern size is not fixed, then store the start index for use if we match.
+ // This is used for adjusting match-start when we start pattern matching with the updated index
+ // by BoyerMoore search.
+ if (!m_pattern.m_body->m_hasFixedSize) {
+ if (alternative->m_minimumSize) {
+ move(index, regT0);
+ sub32(Imm32(alternative->m_minimumSize), regT0);
+ setMatchStart(regT0);
+ } else
+ setMatchStart(index);
}
}
}
@@ -3842,7 +3883,7 @@
// it fails when the body alternatives fail to match with the current offset.
// FIXME: Support unicode flag.
// https://bugs.webkit.org/show_bug.cgi?id=228611
- if (disjunction->m_minimumSize && disjunction->m_hasFixedSize && !m_pattern.sticky() && !m_pattern.unicode()) {
+ if (disjunction->m_minimumSize && !m_pattern.sticky() && !m_pattern.unicode()) {
auto bmInfo = BoyerMooreInfo::create(std::min<unsigned>(disjunction->m_minimumSize, BoyerMooreInfo::maxLength));
if (collectBoyerMooreInfo(disjunction, currentAlternativeIndex, bmInfo.get())) {
m_ops.last().m_bmInfo = bmInfo.ptr();
@@ -3890,13 +3931,10 @@
// We first collect possible characters for each character position. Then, apply heuristics to extract good character sequence from
// that and construct fast searching with long stride.
- ASSERT(disjunction->m_hasFixedSize); // We only support fixed-sized lookahead for BoyerMoore search.
ASSERT(disjunction->m_minimumSize);
// FIXME: Support nested disjunctions (e.g. /(?:abc|def|g(?:hi|jk))/).
// https://bugs.webkit.org/show_bug.cgi?id=228614
- // FIXME: Support character-class (e.g. /[\d]test/).
- // https://bugs.webkit.org/show_bug.cgi?id=228613
// FIXME: Support non-fixed-sized lookahead (e.g. /.*abc/ and extract "abc" sequence).
// https://bugs.webkit.org/show_bug.cgi?id=228612
auto& alternatives = disjunction->m_alternatives;
@@ -3909,20 +3947,46 @@
case PatternTerm::Type::AssertionBOL:
case PatternTerm::Type::AssertionEOL:
case PatternTerm::Type::AssertionWordBoundary:
- case PatternTerm::Type::CharacterClass:
case PatternTerm::Type::BackReference:
case PatternTerm::Type::ForwardReference:
case PatternTerm::Type::ParenthesesSubpattern:
case PatternTerm::Type::ParentheticalAssertion:
case PatternTerm::Type::DotStarEnclosure:
- return false;
+ break;
+ case PatternTerm::Type::CharacterClass: {
+ if (term.quantityType != QuantifierType::FixedCount || term.quantityMaxCount != 1)
+ break;
+ if (term.inputPosition != index)
+ break;
+ auto& characterClass = *term.characterClass;
+ if (term.invert() || characterClass.m_anyCharacter) {
+ bmInfo.setAll(cursor);
+ ++cursor;
+ continue;
+ }
+ if (characterClass.m_table) {
+ bmInfo.setAll(cursor);
+ ++cursor;
+ continue;
+ }
+ if (!characterClass.m_rangesUnicode.isEmpty())
+ bmInfo.addRanges(cursor, characterClass.m_rangesUnicode);
+ if (!characterClass.m_matchesUnicode.isEmpty())
+ bmInfo.addCharacters(cursor, characterClass.m_matchesUnicode);
+ if (!characterClass.m_ranges.isEmpty())
+ bmInfo.addRanges(cursor, characterClass.m_ranges);
+ if (!characterClass.m_matches.isEmpty())
+ bmInfo.addCharacters(cursor, characterClass.m_matches);
+ ++cursor;
+ continue;
+ }
case PatternTerm::Type::PatternCharacter: {
if (term.quantityType != QuantifierType::FixedCount || term.quantityMaxCount != 1)
- return false;
+ break;
if (term.inputPosition != index)
- return false;
+ break;
if (U16_LENGTH(term.patternCharacter) != 1 && m_decodeSurrogatePairs)
- return false;
+ break;
// For case-insesitive compares, non-ascii characters that have different
// upper & lower case representations are already converted to a character class.
ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(term.patternCharacter) || isCanonicallyUnique(term.patternCharacter, m_canonicalMode));
@@ -3932,13 +3996,15 @@
} else
bmInfo.set(cursor, term.patternCharacter);
++cursor;
- break;
+ continue;
}
}
+ dataLogLnIf(YarrJITInternal::verbose, "Shortening to ", cursor);
+ bmInfo.shortenLength(cursor);
+ break;
}
}
- dataLogLnIf(YarrJITInternal::verbose, "Characters collected");
- return true;
+ return bmInfo.length();
}
const BoyerMooreBitmap::Map::WordType* getBoyerMooreBitmap(const BoyerMooreBitmap::Map& map)
Modified: trunk/Source/_javascript_Core/yarr/YarrJIT.h (280569 => 280570)
--- trunk/Source/_javascript_Core/yarr/YarrJIT.h 2021-08-02 23:39:10 UTC (rev 280569)
+++ trunk/Source/_javascript_Core/yarr/YarrJIT.h 2021-08-02 23:43:16 UTC (rev 280570)
@@ -61,6 +61,7 @@
};
class BoyerMooreBitmap {
+ WTF_MAKE_NONCOPYABLE(BoyerMooreBitmap);
WTF_MAKE_FAST_ALLOCATED(BoyerMooreBitmap);
public:
static constexpr unsigned mapSize = 128;
@@ -75,6 +76,8 @@
void add(UChar32 character)
{
+ if (isAllSet())
+ return;
unsigned position = character & mapMask;
if (position != static_cast<unsigned>(character))
m_isMaskEffective = true;
@@ -84,6 +87,43 @@
}
}
+ void addCharacters(const Vector<UChar32>& characters)
+ {
+ if (isAllSet())
+ return;
+ if (characters.size() >= mapSize) {
+ setAll();
+ return;
+ }
+ for (UChar character : characters)
+ add(character);
+ }
+
+ void addRanges(const Vector<CharacterRange>& ranges)
+ {
+ if (ranges.size() >= mapSize) {
+ setAll();
+ return;
+ }
+ for (CharacterRange range : ranges) {
+ if (isAllSet())
+ return;
+ if (static_cast<unsigned>(range.end - range.begin + 1) >= mapSize) {
+ setAll();
+ return;
+ }
+ for (UChar32 character = range.begin; character <= range.end; ++character)
+ add(character);
+ }
+ }
+
+ void setAll()
+ {
+ m_count = mapSize;
+ }
+
+ bool isAllSet() const { return m_count == mapSize; }
+
private:
Map m_map { };
unsigned m_count { 0 };
_______________________________________________ webkit-changes mailing list [email protected] https://lists.webkit.org/mailman/listinfo/webkit-changes
