Skip to content

Commit 6279ebe

Browse files
sosukesuzukisosukesuzuki
committed
[YARR] Share built-in character classes between all YarrPatterns
https://bugs.webkit.org/show_bug.cgi?id=323731 Reviewed by Yusuke Suzuki. Regular expressions that contain a built-in character class such as \d or \w allocate a new CharacterClass instance on the heap for every YarrPattern. The contents of these instances are always identical and never change once the YarrPattern has been built. So construct each of these built-in classes only once per process and cache it. Also, to keep the cached CharacterClasses from being modified in the future, hand them out as const CharacterClass*. * Source/JavaScriptCore/yarr/YarrInterpreter.cpp: (JSC::Yarr::Interpreter::testCharacterClass): (JSC::Yarr::Interpreter::checkCharacterClassDontAdvanceInputForNonBMP): (JSC::Yarr::ByteCompiler::atomCharacterClass): * Source/JavaScriptCore/yarr/YarrInterpreter.h: (JSC::Yarr::ByteTerm::ByteTerm): * Source/JavaScriptCore/yarr/YarrJIT.cpp: * Source/JavaScriptCore/yarr/YarrPattern.cpp: (JSC::Yarr::YarrPattern::unicodeCharacterClassFor): (JSC::Yarr::YarrPatternConstructor::atomBuiltInCharacterClass): (JSC::Yarr::YarrPatternConstructor::atomCharacterClassBuiltIn): (JSC::Yarr::YarrPatternConstructor::optimizeDotStarWrappedExpressions): (JSC::Yarr::dumpCharacterClass): * Source/JavaScriptCore/yarr/YarrPattern.h: (JSC::Yarr::PatternTerm::PatternTerm): (JSC::Yarr::YarrPattern::resetForReparsing): (JSC::Yarr::YarrPattern::create const): (JSC::Yarr::YarrPattern::anyCharacterClass): (JSC::Yarr::YarrPattern::newlineCharacterClass): (JSC::Yarr::YarrPattern::digitsCharacterClass): (JSC::Yarr::YarrPattern::spacesCharacterClass): (JSC::Yarr::YarrPattern::wordcharCharacterClass): (JSC::Yarr::YarrPattern::wordUnicodeIgnoreCaseCharCharacterClass): (JSC::Yarr::YarrPattern::nondigitsCharacterClass): (JSC::Yarr::YarrPattern::nonspacesCharacterClass): (JSC::Yarr::YarrPattern::nonwordcharCharacterClass): (JSC::Yarr::YarrPattern::nonwordUnicodeIgnoreCaseCharCharacterClass): Canonical link: https://commits.webkit.org/320792@main
1 parent f547fd7 commit 6279ebe

5 files changed

Lines changed: 60 additions & 121 deletions

File tree

‎Source/JavaScriptCore/yarr/YarrInterpreter.cpp‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -446,7 +446,7 @@ class Interpreter {
446446
bool decodeSurrogatePairs;
447447
};
448448

449-
bool testCharacterClass(CharacterClass* characterClass, char32_t ch)
449+
bool testCharacterClass(const CharacterClass* characterClass, char32_t ch)
450450
{
451451
auto linearSearchMatches = [ch](const Vector<char32_t>& matches) {
452452
for (unsigned i = 0; i < matches.size(); ++i) {
@@ -593,7 +593,7 @@ class Interpreter {
593593
bool checkCharacterClassDontAdvanceInputForNonBMP(ByteTerm& term, unsigned negativeInputOffset)
594594
{
595595
ASSERT(term.isCharacterClass());
596-
CharacterClass* characterClass = term.atom.characterClass;
596+
const CharacterClass* characterClass = term.atom.characterClass;
597597

598598
auto readCharacter = characterClass->hasOnlyNonBMPCharacters() ? input.readSurrogatePairChecked(direction, negativeInputOffset) : input.readChecked(direction, negativeInputOffset);
599599

@@ -2233,7 +2233,7 @@ class ByteCompiler {
22332233
m_bodyDisjunction->terms.append(ByteTerm(ch, matchDirection, inputPosition, frameLocation, quantityMaxCount, quantityType, flags));
22342234
}
22352235

2236-
void atomCharacterClass(CharacterClass* characterClass, bool invert, MatchDirection matchDirection, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMaxCount, QuantifierType quantityType, OptionSet<Flags> flags)
2236+
void atomCharacterClass(const CharacterClass* characterClass, bool invert, MatchDirection matchDirection, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMaxCount, QuantifierType quantityType, OptionSet<Flags> flags)
22372237
{
22382238
m_bodyDisjunction->terms.append(ByteTerm(characterClass, invert, matchDirection, inputPosition, flags));
22392239

‎Source/JavaScriptCore/yarr/YarrInterpreter.h‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ struct ByteTerm {
4949
char32_t lo;
5050
char32_t hi;
5151
} casedCharacter;
52-
CharacterClass* characterClass;
52+
const CharacterClass* characterClass;
5353
struct {
5454
unsigned subpatternId;
5555
unsigned duplicateNamedGroupId;
@@ -204,7 +204,7 @@ struct ByteTerm {
204204
atom.quantityMaxCount = quantityCount;
205205
}
206206

207-
ByteTerm(CharacterClass* characterClass, bool invert, MatchDirection matchDirection, unsigned inputPos, OptionSet<Flags> flags)
207+
ByteTerm(const CharacterClass* characterClass, bool invert, MatchDirection matchDirection, unsigned inputPos, OptionSet<Flags> flags)
208208
: type(directed(Type::CharacterClass, Type::CharacterClassBackward, matchDirection))
209209
, m_flags(flags)
210210
, m_capture(false)
@@ -590,9 +590,9 @@ struct BytecodePattern {
590590
unsigned m_offsetsSize;
591591
Vector<unsigned> m_duplicateNamedGroupForSubpatternId;
592592

593-
CharacterClass* newlineCharacterClass;
594-
CharacterClass* wordcharCharacterClass;
595-
CharacterClass* ignoreCaseWordcharCharacterClass;
593+
const CharacterClass* newlineCharacterClass;
594+
const CharacterClass* wordcharCharacterClass;
595+
const CharacterClass* ignoreCaseWordcharCharacterClass;
596596

597597
private:
598598
Vector<std::unique_ptr<ByteDisjunction>> m_allParenthesesInfo;

‎Source/JavaScriptCore/yarr/YarrJIT.cpp‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1275,7 +1275,7 @@ class YarrGenerator final : public YarrJITInfo {
12751275
{
12761276
ASSERT(term->type == PatternTerm::Type::CharacterClass);
12771277

1278-
auto processCharacterClass = [&] (CharacterClass* characterClassToProcess) {
1278+
auto processCharacterClass = [&] (const CharacterClass* characterClassToProcess) {
12791279
if (m_decodeSurrogatePairs && (term->invert() || characterClassToProcess->m_anyCharacter))
12801280
failures.append(m_jit.branch32(MacroAssembler::Equal, character, MacroAssembler::TrustedImm32(errorCodePoint)));
12811281
if (term->invert())
@@ -2441,7 +2441,7 @@ class YarrGenerator final : public YarrJITInfo {
24412441

24422442
readCharacter(offsetOfCharacterAfter(op), character);
24432443

2444-
CharacterClass* wordcharCharacterClass;
2444+
const CharacterClass* wordcharCharacterClass;
24452445

24462446
if (m_pattern.eitherUnicode() && term->ignoreCase())
24472447
wordcharCharacterClass = m_pattern.wordUnicodeIgnoreCaseCharCharacterClass();
@@ -2465,7 +2465,7 @@ class YarrGenerator final : public YarrJITInfo {
24652465
atBegin = branchIfAtStartOfInput(op);
24662466
readCharacter(offsetOfCharacterBefore(op), character);
24672467

2468-
CharacterClass* wordcharCharacterClass;
2468+
const CharacterClass* wordcharCharacterClass;
24692469

24702470
if (m_pattern.eitherUnicode() && term->ignoreCase())
24712471
wordcharCharacterClass = m_pattern.wordUnicodeIgnoreCaseCharCharacterClass();

‎Source/JavaScriptCore/yarr/YarrPattern.cpp‎

Lines changed: 29 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -33,8 +33,10 @@
3333
#include "YarrCanonicalize.h"
3434
#include "YarrParser.h"
3535
#include <limits>
36+
#include <mutex>
3637
#include <wtf/BitSet.h>
3738
#include <wtf/DataLog.h>
39+
#include <wtf/NeverDestroyed.h>
3840
#include <wtf/StackCheck.h>
3941
#include <wtf/TriState.h>
4042
#include <wtf/Vector.h>
@@ -1185,7 +1187,29 @@ static std::unique_ptr<CharacterClass> invertedCharacterClass(const CharacterCla
11851187
return constructor.charClass();
11861188
}
11871189

1188-
CharacterClass* YarrPattern::unicodeCharacterClassFor(BuiltInCharacterClassID unicodeClassID, bool ignoreCase, bool invert)
1190+
template<std::unique_ptr<CharacterClass> (*create)()>
1191+
const CharacterClass* YarrPattern::sharedCharacterClass()
1192+
{
1193+
static LazyNeverDestroyed<std::unique_ptr<CharacterClass>> characterClass;
1194+
static std::once_flag onceFlag;
1195+
std::call_once(onceFlag, [] {
1196+
characterClass.construct(create());
1197+
});
1198+
return characterClass->get();
1199+
}
1200+
1201+
const CharacterClass* YarrPattern::anyCharacterClass() { return sharedCharacterClass<anycharCreate>(); }
1202+
const CharacterClass* YarrPattern::newlineCharacterClass() { return sharedCharacterClass<newlineCreate>(); }
1203+
const CharacterClass* YarrPattern::digitsCharacterClass() { return sharedCharacterClass<digitsCreate>(); }
1204+
const CharacterClass* YarrPattern::spacesCharacterClass() { return sharedCharacterClass<spacesCreate>(); }
1205+
const CharacterClass* YarrPattern::wordcharCharacterClass() { return sharedCharacterClass<wordcharCreate>(); }
1206+
const CharacterClass* YarrPattern::wordUnicodeIgnoreCaseCharCharacterClass() { return sharedCharacterClass<wordUnicodeIgnoreCaseCharCreate>(); }
1207+
const CharacterClass* YarrPattern::nondigitsCharacterClass() { return sharedCharacterClass<nondigitsCreate>(); }
1208+
const CharacterClass* YarrPattern::nonspacesCharacterClass() { return sharedCharacterClass<nonspacesCreate>(); }
1209+
const CharacterClass* YarrPattern::nonwordcharCharacterClass() { return sharedCharacterClass<nonwordcharCreate>(); }
1210+
const CharacterClass* YarrPattern::nonwordUnicodeIgnoreCaseCharCharacterClass() { return sharedCharacterClass<nonwordUnicodeIgnoreCaseCharCreate>(); }
1211+
1212+
const CharacterClass* YarrPattern::unicodeCharacterClassFor(BuiltInCharacterClassID unicodeClassID, bool ignoreCase, bool invert)
11891213
{
11901214
ASSERT(unicodeClassID >= BuiltInCharacterClassID::BaseUnicodePropertyID);
11911215

@@ -1414,7 +1438,7 @@ class YarrPatternConstructor {
14141438
m_alternative->m_terms.append(PatternTerm(m_pattern.newlineCharacterClass(), true, m_flags, parenthesisMatchDirection()));
14151439
break;
14161440
default: {
1417-
CharacterClass* characterClass = m_pattern.unicodeCharacterClassFor(classID, ignoreCase(), invert);
1441+
const CharacterClass* characterClass = m_pattern.unicodeCharacterClassFor(classID, ignoreCase(), invert);
14181442
if (characterClass->hasStrings()) {
14191443
atomParenthesesSubpatternBegin(false);
14201444
unsigned alternativeCount = 0;
@@ -1486,7 +1510,7 @@ class YarrPatternConstructor {
14861510
break;
14871511

14881512
default: {
1489-
CharacterClass* characterClass = m_pattern.unicodeCharacterClassFor(classID, ignoreCase(), invert);
1513+
const CharacterClass* characterClass = m_pattern.unicodeCharacterClassFor(classID, ignoreCase(), invert);
14901514
if (!invert)
14911515
m_currentCharacterClassConstructor->append(characterClass);
14921516
else
@@ -2606,7 +2630,7 @@ class YarrPatternConstructor {
26062630
if (m_pattern.sticky())
26072631
return;
26082632

2609-
CharacterClass* dotCharacterClass = dotAll() ? m_pattern.anyCharacterClass() : m_pattern.newlineCharacterClass();
2633+
const CharacterClass* dotCharacterClass = dotAll() ? m_pattern.anyCharacterClass() : m_pattern.newlineCharacterClass();
26102634
PatternAlternative* alternative = alternatives[0].get();
26112635
Vector<PatternTerm>& terms = alternative->m_terms;
26122636
if (terms.size() >= 3) {
@@ -3240,7 +3264,7 @@ void dumpChar32(PrintStream& out, char32_t c)
32403264
out.printf("0x%04x", c);
32413265
}
32423266

3243-
void dumpCharacterClass(PrintStream& out, YarrPattern* pattern, CharacterClass* characterClass)
3267+
void dumpCharacterClass(PrintStream& out, YarrPattern* pattern, const CharacterClass* characterClass)
32443268
{
32453269
if (pattern) {
32463270
if (characterClass == pattern->anyCharacterClass()) {

‎Source/JavaScriptCore/yarr/YarrPattern.h‎

Lines changed: 20 additions & 105 deletions
Original file line numberDiff line numberDiff line change
@@ -252,7 +252,7 @@ struct PatternTerm {
252252
Checked<unsigned> quantityMaxCount;
253253
union {
254254
char32_t patternCharacter;
255-
CharacterClass* characterClass;
255+
const CharacterClass* characterClass;
256256
unsigned backReferenceSubpatternId;
257257
struct {
258258
PatternDisjunction* disjunction;
@@ -290,7 +290,7 @@ struct PatternTerm {
290290
quantityMinCount = quantityMaxCount = 1;
291291
}
292292

293-
PatternTerm(CharacterClass* charClass, bool invert, OptionSet<Flags> currFlags, MatchDirection matchDirection = Forward)
293+
PatternTerm(const CharacterClass* charClass, bool invert, OptionSet<Flags> currFlags, MatchDirection matchDirection = Forward)
294294
: type(PatternTerm::Type::CharacterClass)
295295
, m_currentFlags(currFlags)
296296
, m_capture(false)
@@ -643,16 +643,6 @@ struct YarrPattern {
643643
m_hasNamedCaptureGroups = false;
644644
m_saveInitialStartValue = false;
645645

646-
anycharCached = nullptr;
647-
newlineCached = nullptr;
648-
digitsCached = nullptr;
649-
spacesCached = nullptr;
650-
wordcharCached = nullptr;
651-
wordUnicodeIgnoreCaseCharCached = nullptr;
652-
nondigitsCached = nullptr;
653-
nonspacesCached = nullptr;
654-
nonwordcharCached = nullptr;
655-
nonwordUnicodeIgnoreCasecharCached = nullptr;
656646
unicodePropertiesCached.clear();
657647

658648
m_disjunctions.clear();
@@ -667,87 +657,22 @@ struct YarrPattern {
667657
return m_containsUnsignedLengthPattern;
668658
}
669659

670-
CharacterClass* anyCharacterClass()
671-
{
672-
if (!anycharCached) {
673-
m_userCharacterClasses.append(anycharCreate());
674-
anycharCached = m_userCharacterClasses.last().get();
675-
}
676-
return anycharCached;
677-
}
678-
CharacterClass* newlineCharacterClass()
679-
{
680-
if (!newlineCached) {
681-
m_userCharacterClasses.append(newlineCreate());
682-
newlineCached = m_userCharacterClasses.last().get();
683-
}
684-
return newlineCached;
685-
}
686-
CharacterClass* digitsCharacterClass()
687-
{
688-
if (!digitsCached) {
689-
m_userCharacterClasses.append(digitsCreate());
690-
digitsCached = m_userCharacterClasses.last().get();
691-
}
692-
return digitsCached;
693-
}
694-
CharacterClass* spacesCharacterClass()
695-
{
696-
if (!spacesCached) {
697-
m_userCharacterClasses.append(spacesCreate());
698-
spacesCached = m_userCharacterClasses.last().get();
699-
}
700-
return spacesCached;
701-
}
702-
CharacterClass* wordcharCharacterClass()
703-
{
704-
if (!wordcharCached) {
705-
m_userCharacterClasses.append(wordcharCreate());
706-
wordcharCached = m_userCharacterClasses.last().get();
707-
}
708-
return wordcharCached;
709-
}
710-
CharacterClass* wordUnicodeIgnoreCaseCharCharacterClass()
711-
{
712-
if (!wordUnicodeIgnoreCaseCharCached) {
713-
m_userCharacterClasses.append(wordUnicodeIgnoreCaseCharCreate());
714-
wordUnicodeIgnoreCaseCharCached = m_userCharacterClasses.last().get();
715-
}
716-
return wordUnicodeIgnoreCaseCharCached;
717-
}
718-
CharacterClass* nondigitsCharacterClass()
719-
{
720-
if (!nondigitsCached) {
721-
m_userCharacterClasses.append(nondigitsCreate());
722-
nondigitsCached = m_userCharacterClasses.last().get();
723-
}
724-
return nondigitsCached;
725-
}
726-
CharacterClass* nonspacesCharacterClass()
727-
{
728-
if (!nonspacesCached) {
729-
m_userCharacterClasses.append(nonspacesCreate());
730-
nonspacesCached = m_userCharacterClasses.last().get();
731-
}
732-
return nonspacesCached;
733-
}
734-
CharacterClass* nonwordcharCharacterClass()
735-
{
736-
if (!nonwordcharCached) {
737-
m_userCharacterClasses.append(nonwordcharCreate());
738-
nonwordcharCached = m_userCharacterClasses.last().get();
739-
}
740-
return nonwordcharCached;
741-
}
742-
CharacterClass* nonwordUnicodeIgnoreCaseCharCharacterClass()
743-
{
744-
if (!nonwordUnicodeIgnoreCasecharCached) {
745-
m_userCharacterClasses.append(nonwordUnicodeIgnoreCaseCharCreate());
746-
nonwordUnicodeIgnoreCasecharCached = m_userCharacterClasses.last().get();
747-
}
748-
return nonwordUnicodeIgnoreCasecharCached;
749-
}
750-
CharacterClass* unicodeCharacterClassFor(BuiltInCharacterClassID, bool ignoreCase, bool invert);
660+
private:
661+
template<std::unique_ptr<CharacterClass> (*create)()>
662+
static const CharacterClass* sharedCharacterClass();
663+
664+
public:
665+
static const CharacterClass* anyCharacterClass();
666+
static const CharacterClass* newlineCharacterClass();
667+
static const CharacterClass* digitsCharacterClass();
668+
static const CharacterClass* spacesCharacterClass();
669+
static const CharacterClass* wordcharCharacterClass();
670+
static const CharacterClass* wordUnicodeIgnoreCaseCharCharacterClass();
671+
static const CharacterClass* nondigitsCharacterClass();
672+
static const CharacterClass* nonspacesCharacterClass();
673+
static const CharacterClass* nonwordcharCharacterClass();
674+
static const CharacterClass* nonwordUnicodeIgnoreCaseCharCharacterClass();
675+
const CharacterClass* unicodeCharacterClassFor(BuiltInCharacterClassID, bool ignoreCase, bool invert);
751676

752677
unsigned offsetVectorBaseForNamedCaptures() const
753678
{
@@ -829,22 +754,12 @@ struct YarrPattern {
829754
private:
830755
ErrorCode compile(StringView patternString);
831756

832-
CharacterClass* anycharCached { nullptr };
833-
CharacterClass* newlineCached { nullptr };
834-
CharacterClass* digitsCached { nullptr };
835-
CharacterClass* spacesCached { nullptr };
836-
CharacterClass* wordcharCached { nullptr };
837-
CharacterClass* wordUnicodeIgnoreCaseCharCached { nullptr };
838-
CharacterClass* nondigitsCached { nullptr };
839-
CharacterClass* nonspacesCached { nullptr };
840-
CharacterClass* nonwordcharCached { nullptr };
841-
CharacterClass* nonwordUnicodeIgnoreCasecharCached { nullptr };
842-
UncheckedKeyHashMap<unsigned, CharacterClass*> unicodePropertiesCached;
757+
UncheckedKeyHashMap<unsigned, const CharacterClass*> unicodePropertiesCached;
843758
};
844759

845760
void indentForNestingLevel(PrintStream&, unsigned);
846761
void dumpChar32(PrintStream&, char32_t);
847-
void dumpCharacterClass(PrintStream&, YarrPattern*, CharacterClass*);
762+
void dumpCharacterClass(PrintStream&, YarrPattern*, const CharacterClass*);
848763

849764
struct BackTrackInfoPatternCharacter {
850765
uintptr_t begin; // Only needed for unicode patterns

0 commit comments

Comments
 (0)