Changeset 90962 in webkit for trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp

Timestamp:

Jul 13, 2011, 4:05:40 PM (14 years ago)

Author:

[email protected]

Message:

​https://bugs.webkit.org/show_bug.cgi?id=64202
Enh: Improve handling of RegExp in the form of /.*blah.*/

Reviewed by Gavin Barraclough.

../../../../Volumes/Data/src/webkit/LayoutTests:

New tests to support /.*<expression>.*/ enhancement.

• fast/regex/dotstar-expected.txt: Added.
• fast/regex/dotstar.html: Added.
• fast/regex/script-tests/dotstar.js: Added.

../../../../Volumes/Data/src/webkit/Source/JavaScriptCore:

Added code to both the Yarr interpreter and JIT to handle
these expressions a little differently. First off, the terms
in between the leading and trailing .*'s cannot capture and
also this enhancement is limited to single alternative expressions.
If an expression is of the right form with the aforementioned
restrictions, we process the inner terms and then look for the
beginning of the string and end of the string. There is handling
for multiline expressions to allow the beginning and end to be
right after and right before newlines.

This enhancement speeds up expressions of this type 12x on
a MacBookPro.

Cleaned up 'case' statement indentation.

A new set of tests was added as LayoutTests/fast/regex/dotstar.html

• yarr/YarrInterpreter.cpp:

(JSC::Yarr::Interpreter::InputStream::end):
(JSC::Yarr::Interpreter::matchDotStarEnclosure):
(JSC::Yarr::Interpreter::matchDisjunction):
(JSC::Yarr::ByteCompiler::assertionDotStarEnclosure):
(JSC::Yarr::ByteCompiler::emitDisjunction):

• yarr/YarrInterpreter.h:

(JSC::Yarr::ByteTerm::DotStarEnclosure):

• yarr/YarrJIT.cpp:

(JSC::Yarr::YarrGenerator::generateDotStarEnclosure):
(JSC::Yarr::YarrGenerator::backtrackDotStarEnclosure):
(JSC::Yarr::YarrGenerator::generateTerm):
(JSC::Yarr::YarrGenerator::backtrackTerm):

• yarr/YarrPattern.cpp:

(JSC::Yarr::YarrPatternConstructor::setupAlternativeOffsets):
(JSC::Yarr::YarrPatternConstructor::containsCapturingTerms):
(JSC::Yarr::YarrPatternConstructor::optimizeDotStarWrappedExpressions):
(JSC::Yarr::YarrPattern::compile):

• yarr/YarrPattern.h:

(JSC::Yarr::PatternTerm::PatternTerm):

File:

• trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp (modified) (3 diffs)

trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp

@@ -583 +583 @@
                 currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition);
                 break;
+
+            case PatternTerm::TypeDotStarEnclosure:
+                alternative->m_hasFixedSize = false;
+                term.inputPosition = initialInputPosition;
+                break;
             }
         }
@@ -676 +681 @@
     }
 
+    bool containsCapturingTerms(PatternAlternative* alternative, size_t firstTermIndex, size_t lastTermIndex)
+    {
+        Vector<PatternTerm>& terms = alternative->m_terms;
+
+        for (size_t termIndex = firstTermIndex; termIndex <= lastTermIndex; ++termIndex) {
+            PatternTerm& term = terms[termIndex];
+
+            if (term.m_capture)
+                return true;
+
+            if (term.type == PatternTerm::TypeParenthesesSubpattern) {
+                PatternDisjunction* nestedDisjunction = term.parentheses.disjunction;
+                for (unsigned alt = 0; alt < nestedDisjunction->m_alternatives.size(); ++alt) {
+                    if (containsCapturingTerms(nestedDisjunction->m_alternatives[alt], 0, nestedDisjunction->m_alternatives[alt]->m_terms.size() - 1))
+                        return true;
+                }
+            }
+        }
+
+        return false;
+    }
+
+    // This optimization identifies alternatives in the form of 
+    // [^].*[?]<expression>.*[$] for expressions that don't have any 
+    // capturing terms. The alternative is changed to <expression> 
+    // followed by processing of the dot stars to find and adjust the 
+    // beginning and the end of the match.
+    void optimizeDotStarWrappedExpressions()
+    {
+        Vector<PatternAlternative*>& alternatives = m_pattern.m_body->m_alternatives;
+        if (alternatives.size() != 1)
+            return;
+
+        PatternAlternative* alternative = alternatives[0];
+        Vector<PatternTerm>& terms = alternative->m_terms;
+        if (terms.size() >= 3) {
+            bool startsWithBOL = false;
+            bool endsWithEOL = false;
+            size_t termIndex, firstExpressionTerm, lastExpressionTerm;
+
+            termIndex = 0;
+            if (terms[termIndex].type == PatternTerm::TypeAssertionBOL) {
+                startsWithBOL = true;
+                ++termIndex;
+            }
+            
+            PatternTerm& firstNonAnchorTerm = terms[termIndex];
+            if ((firstNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (firstNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || !((firstNonAnchorTerm.quantityType == QuantifierGreedy) || (firstNonAnchorTerm.quantityType == QuantifierNonGreedy)))
+                return;
+            
+            firstExpressionTerm = termIndex + 1;
+            
+            termIndex = terms.size() - 1;
+            if (terms[termIndex].type == PatternTerm::TypeAssertionEOL) {
+                endsWithEOL = true;
+                --termIndex;
+            }
+            
+            PatternTerm& lastNonAnchorTerm = terms[termIndex];
+            if ((lastNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (lastNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || (lastNonAnchorTerm.quantityType != QuantifierGreedy))
+                return;
+            
+            lastExpressionTerm = termIndex - 1;
+
+            if (firstExpressionTerm > lastExpressionTerm)
+                return;
+
+            if (!containsCapturingTerms(alternative, firstExpressionTerm, lastExpressionTerm)) {
+                for (termIndex = terms.size() - 1; termIndex > lastExpressionTerm; --termIndex)
+                    terms.remove(termIndex);
+
+                for (termIndex = firstExpressionTerm; termIndex > 0; --termIndex)
+                    terms.remove(termIndex - 1);
+
+                terms.append(PatternTerm(startsWithBOL, endsWithEOL));
+                
+                m_pattern.m_containsBOL = false;
+            }
+        }
+    }
+
 private:
     YarrPattern& m_pattern;
@@ -709 +795 @@
 
     constructor.checkForTerminalParentheses();
+    constructor.optimizeDotStarWrappedExpressions();
     constructor.optimizeBOL();