Changeset 225683 in webkit

Timestamp:

Dec 8, 2017 10:27:18 AM (6 years ago)

Author:

msaboff@apple.com

Message:

YARR: Coalesce constructed character classes
​https://bugs.webkit.org/show_bug.cgi?id=180537

Reviewed by JF Bastien.

When adding characters or character ranges to a character class being constructed,
we now coalesce adjacent characters and character ranges. When we create a
character class after construction is complete, we do a final coalescing pass
across the character list and ranges to catch any remaining coalescing
opportunities.

Added an optimization for character classes that will match any character.
This is somewhat common in code created before the /s (dotAll) flag was added
to the engine.

• yarr/YarrInterpreter.cpp:

(JSC::Yarr::Interpreter::checkCharacterClass):

• yarr/YarrJIT.cpp:

(JSC::Yarr::YarrGenerator::generateCharacterClassOnce):
(JSC::Yarr::YarrGenerator::generateCharacterClassFixed):
(JSC::Yarr::YarrGenerator::generateCharacterClassGreedy):
(JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy):

• yarr/YarrPattern.cpp:

(JSC::Yarr::CharacterClassConstructor::CharacterClassConstructor):
(JSC::Yarr::CharacterClassConstructor::reset):
(JSC::Yarr::CharacterClassConstructor::charClass):
(JSC::Yarr::CharacterClassConstructor::addSorted):
(JSC::Yarr::CharacterClassConstructor::addSortedRange):
(JSC::Yarr::CharacterClassConstructor::mergeRangesFrom):
(JSC::Yarr::CharacterClassConstructor::coalesceTables):
(JSC::Yarr::CharacterClassConstructor::anyCharacter):
(JSC::Yarr::YarrPatternConstructor::atomCharacterClassEnd):
(JSC::Yarr::PatternTerm::dump):
(JSC::Yarr::anycharCreate):

• yarr/YarrPattern.h:

(JSC::Yarr::CharacterClass::CharacterClass):

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• yarr/YarrInterpreter.cpp (modified) (1 diff)
• yarr/YarrJIT.cpp (modified) (4 diffs)
• yarr/YarrPattern.cpp (modified) (13 diffs)
• yarr/YarrPattern.h (modified) (4 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2017-12-08  Michael Saboff  <msaboff@apple.com>
+
+        YARR: Coalesce constructed character classes
+        https://bugs.webkit.org/show_bug.cgi?id=180537
+
+        Reviewed by JF Bastien.
+
+        When adding characters or character ranges to a character class being constructed,
+        we now coalesce adjacent characters and character ranges.  When we create a
+        character class after construction is complete, we do a final coalescing pass
+        across the character list and ranges to catch any remaining coalescing
+        opportunities.
+
+        Added an optimization for character classes that will match any character.
+        This is somewhat common in code created before the /s (dotAll) flag was added
+        to the engine.
+
+        * yarr/YarrInterpreter.cpp:
+        (JSC::Yarr::Interpreter::checkCharacterClass):
+        * yarr/YarrJIT.cpp:
+        (JSC::Yarr::YarrGenerator::generateCharacterClassOnce):
+        (JSC::Yarr::YarrGenerator::generateCharacterClassFixed):
+        (JSC::Yarr::YarrGenerator::generateCharacterClassGreedy):
+        (JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy):
+        * yarr/YarrPattern.cpp:
+        (JSC::Yarr::CharacterClassConstructor::CharacterClassConstructor):
+        (JSC::Yarr::CharacterClassConstructor::reset):
+        (JSC::Yarr::CharacterClassConstructor::charClass):
+        (JSC::Yarr::CharacterClassConstructor::addSorted):
+        (JSC::Yarr::CharacterClassConstructor::addSortedRange):
+        (JSC::Yarr::CharacterClassConstructor::mergeRangesFrom):
+        (JSC::Yarr::CharacterClassConstructor::coalesceTables):
+        (JSC::Yarr::CharacterClassConstructor::anyCharacter):
+        (JSC::Yarr::YarrPatternConstructor::atomCharacterClassEnd):
+        (JSC::Yarr::PatternTerm::dump):
+        (JSC::Yarr::anycharCreate):
+        * yarr/YarrPattern.h:
+        (JSC::Yarr::CharacterClass::CharacterClass):
+
 2017-12-07  Saam Barati  <sbarati@apple.com>
 

trunk/Source/JavaScriptCore/yarr/YarrInterpreter.cpp

@@ -409 +409 @@
     bool checkCharacterClass(CharacterClass* characterClass, bool invert, unsigned negativeInputOffset)
     {
+        if (characterClass->m_anyCharacter)
+            return !invert;
+
         bool match = testCharacterClass(characterClass, input.readChecked(negativeInputOffset));
         return invert ? !match : match;

trunk/Source/JavaScriptCore/yarr/YarrJIT.cpp

@@ -1172 +1172 @@
         // If we are matching the "any character" builtin class we only need to read the
         // character and don't need to match as it will always succeed.
-        if (term->invert() || term->characterClass != m_pattern.anyCharacterClass()) {
+        if (term->invert() || !term->characterClass->m_anyCharacter) {
             matchCharacterClass(character, matchDest, term->characterClass);
 
@@ -1221 +1221 @@
         // If we are matching the "any character" builtin class we only need to read the
         // character and don't need to match as it will always succeed.
-        if (term->invert() || term->characterClass != m_pattern.anyCharacterClass()) {
+        if (term->invert() || !term->characterClass->m_anyCharacter) {
             matchCharacterClass(character, matchDest, term->characterClass);
 
@@ -1273 +1273 @@
             // If we are matching the "any character" builtin class we only need to read the
             // character and don't need to match as it will always succeed.
-            if (term->characterClass != m_pattern.anyCharacterClass()) {
+            if (!term->characterClass->m_anyCharacter) {
                 matchCharacterClass(character, matchDest, term->characterClass);
                 failures.append(jump());
@@ -1379 +1379 @@
         // If we are matching the "any character" builtin class we only need to read the
         // character and don't need to match as it will always succeed.
-        if (term->invert() || term->characterClass != m_pattern.anyCharacterClass()) {
+        if (term->invert() || !term->characterClass->m_anyCharacter) {
             matchCharacterClass(character, matchDest, term->characterClass);
 

trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp

@@ -49 +49 @@
         : m_isCaseInsensitive(isCaseInsensitive)
         , m_hasNonBMPCharacters(false)
+        , m_anyCharacter(false)
         , m_canonicalMode(canonicalMode)
     {
@@ -60 +61 @@
         m_rangesUnicode.clear();
         m_hasNonBMPCharacters = false;
+        m_anyCharacter = false;
     }
 
@@ -239 +241 @@
     std::unique_ptr<CharacterClass> charClass()
     {
+        coalesceTables();
+
         auto characterClass = std::make_unique<CharacterClass>();
 
@@ -246 +250 @@
         characterClass->m_rangesUnicode.swap(m_rangesUnicode);
         characterClass->m_hasNonBMPCharacters = hasNonBMPCharacters();
+        characterClass->m_anyCharacter = anyCharacter();
+
+        m_hasNonBMPCharacters = false;
+        m_anyCharacter = false;
 
         return characterClass;
@@ -271 +279 @@
             if (!val)
                 return;
-            else if (val > 0)
+            else if (val > 0) {
+                if (val == 1) {
+                    UChar32 lo = ch;
+                    UChar32 hi = ch + 1;
+                    matches.remove(pos + index);
+                    if (pos + index > 0 && matches[pos + index - 1] == ch - 1) {
+                        lo = ch - 1;
+                        matches.remove(pos + index - 1);
+                    }
+                    addSortedRange(isASCII(ch) ? m_ranges : m_rangesUnicode, lo, hi);
+                    return;
+                }
                 range = index;
-            else {
+            } else {
+                if (val == -1) {
+                    UChar32 lo = ch - 1;
+                    UChar32 hi = ch;
+                    matches.remove(pos + index);
+                    if (pos + index + 1 < matches.size() && matches[pos + index + 1] == ch + 1) {
+                        hi = ch + 1;
+                        matches.remove(pos + index + 1);
+                    }
+                    addSortedRange(isASCII(ch) ? m_ranges : m_rangesUnicode, lo, hi);
+                    return;
+                }
                 pos += (index+1);
                 range -= (index+1);
@@ -287 +317 @@
     void addSortedRange(Vector<CharacterRange>& ranges, UChar32 lo, UChar32 hi)
     {
-        unsigned end = ranges.size();
+        size_t end = ranges.size();
 
         if (!U_IS_BMP(hi))
@@ -294 +324 @@
         // Simple linear scan - I doubt there are that many ranges anyway...
         // feel free to fix this with something faster (eg binary chop).
-        for (unsigned i = 0; i < end; ++i) {
+        for (size_t i = 0; i < end; ++i) {
             // does the new range fall before the current position in the array
             if (hi < ranges[i].begin) {
-                // optional optimization: concatenate appending ranges? - may not be worthwhile.
+                // Concatenate appending ranges.
                 if (hi == (ranges[i].begin - 1)) {
                     ranges[i].begin = lo;
@@ -313 +343 @@
                 ranges[i].end = std::max(ranges[i].end, hi);
 
-                // now check if the new range can subsume any subsequent ranges.
-                unsigned next = i+1;
-                // each iteration of the loop we will either remove something from the list, or break the loop.
-                while (next < ranges.size()) {
-                    if (ranges[next].begin <= (ranges[i].end + 1)) {
-                        // the next entry now overlaps / concatenates this one.
-                        ranges[i].end = std::max(ranges[i].end, ranges[next].end);
-                        ranges.remove(next);
-                    } else
-                        break;
-                }
-                
+                mergeRangesFrom(ranges, i);
                 return;
             }
@@ -333 +352 @@
     }
 
+    void mergeRangesFrom(Vector<CharacterRange>& ranges, size_t index)
+    {
+        unsigned next = index + 1;
+
+        // each iteration of the loop we will either remove something from the list, or break out of the loop.
+        while (next < ranges.size()) {
+            if (ranges[next].begin <= (ranges[index].end + 1)) {
+                // the next entry now overlaps / concatenates with this one.
+                ranges[index].end = std::max(ranges[index].end, ranges[next].end);
+                ranges.remove(next);
+            } else
+                break;
+        }
+
+    }
+
+    void coalesceTables()
+    {
+        auto coalesceMatchesAndRanges = [&](Vector<UChar32>& matches, Vector<CharacterRange>& ranges) {
+
+            size_t matchesIndex = 0;
+            size_t rangesIndex = 0;
+
+            while (matchesIndex < matches.size() && rangesIndex < ranges.size()) {
+                while (matchesIndex < matches.size() && matches[matchesIndex] < ranges[rangesIndex].begin - 1)
+                    matchesIndex++;
+
+                if (matchesIndex < matches.size() && matches[matchesIndex] == ranges[rangesIndex].begin - 1) {
+                    ranges[rangesIndex].begin = matches[matchesIndex];
+                    matches.remove(matchesIndex);
+                }
+
+                while (matchesIndex < matches.size() && matches[matchesIndex] < ranges[rangesIndex].end + 1)
+                    matchesIndex++;
+
+                if (matchesIndex < matches.size()) {
+                    if (matches[matchesIndex] == ranges[rangesIndex].end + 1) {
+                        ranges[rangesIndex].end = matches[matchesIndex];
+                        matches.remove(matchesIndex);
+
+                        mergeRangesFrom(ranges, rangesIndex);
+                    } else
+                        matchesIndex++;
+                }
+            }
+        };
+
+        coalesceMatchesAndRanges(m_matches, m_ranges);
+        coalesceMatchesAndRanges(m_matchesUnicode, m_rangesUnicode);
+
+        if (!m_matches.size() && !m_matchesUnicode.size()
+            && m_ranges.size() == 1 && m_rangesUnicode.size() == 1
+            && m_ranges[0].begin == 0 && m_ranges[0].end == 0x7f
+            && m_rangesUnicode[0].begin == 0x80 && m_rangesUnicode[0].end == 0x10ffff)
+            m_anyCharacter = true;
+    }
+
     bool hasNonBMPCharacters()
     {
@@ -338 +414 @@
     }
 
-    bool m_isCaseInsensitive;
-    bool m_hasNonBMPCharacters;
+    bool anyCharacter()
+    {
+        return m_anyCharacter;
+    }
+
+    bool m_isCaseInsensitive : 1;
+    bool m_hasNonBMPCharacters : 1;
+    bool m_anyCharacter : 1;
     CanonicalMode m_canonicalMode;
 
@@ -490 +572 @@
     {
         auto newCharacterClass = m_characterClassConstructor.charClass();
+
+        if (!m_invertCharacterClass && newCharacterClass.get()->m_anyCharacter) {
+            m_alternative->m_terms.append(PatternTerm(m_pattern.anyCharacterClass(), false));
+            return;
+        }
         m_alternative->m_terms.append(PatternTerm(newCharacterClass.get(), m_invertCharacterClass));
         m_pattern.m_userCharacterClasses.append(WTFMove(newCharacterClass));
@@ -1181 +1268 @@
     case TypeCharacterClass:
         out.print("character class ");
-        if (characterClass == thisPattern->anyCharacterClass())
+        if (characterClass->m_anyCharacter)
             out.print("<any character>");
         else if (characterClass == thisPattern->newlineCharacterClass())
@@ -1384 +1471 @@
     characterClass->m_rangesUnicode.append(CharacterRange(0x0080, 0x10ffff));
     characterClass->m_hasNonBMPCharacters = true;
+    characterClass->m_anyCharacter = true;
     return characterClass;
 }

trunk/Source/JavaScriptCore/yarr/YarrPattern.h

@@ -60 +60 @@
         : m_table(0)
         , m_hasNonBMPCharacters(false)
+        , m_anyCharacter(false)
     {
     }
@@ -66 +67 @@
         , m_tableInverted(inverted)
         , m_hasNonBMPCharacters(false)
+        , m_anyCharacter(false)
     {
     }
@@ -76 +78 @@
         , m_tableInverted(false)
         , m_hasNonBMPCharacters(false)
+        , m_anyCharacter(false)
     {
     }
@@ -85 +88 @@
 
     const char* m_table;
-    bool m_tableInverted;
-    bool m_hasNonBMPCharacters;
+    bool m_tableInverted : 1;
+    bool m_hasNonBMPCharacters : 1;
+    bool m_anyCharacter : 1;
 };