Changeset 72186 in webkit for trunk/JavaScriptCore/yarr/RegexInterpreter.cpp

Timestamp:

Nov 17, 2010, 3:03:40 AM (15 years ago)

Author:

Csaba Osztrogonác

Message:

Extend YARR Interpreter with beginning character look-up optimization
​https://bugs.webkit.org/show_bug.cgi?id=45751

Patch by Peter Varga <​[email protected]> on 2010-11-17
Reviewed by Gavin Barraclough.

Add beginning character look-up optimization which sets the start
index to the first possible successful pattern match.
Extend YARR Interpreter with lookupForBeginChars function which
implements the beginning character look-up optimization.

• yarr/RegexInterpreter.cpp:

(JSC::Yarr::Interpreter::InputStream::readPair):
(JSC::Yarr::Interpreter::InputStream::isNotAvailableInput):
(JSC::Yarr::Interpreter::lookupForBeginChars):
(JSC::Yarr::Interpreter::matchDisjunction):
(JSC::Yarr::Interpreter::interpret):

• yarr/RegexInterpreter.h:

(JSC::Yarr::BytecodePattern::BytecodePattern):

File:

• trunk/JavaScriptCore/yarr/RegexInterpreter.cpp (modified) (6 diffs)

trunk/JavaScriptCore/yarr/RegexInterpreter.cpp

@@ -197 +197 @@
         }
 
+        int readPair()
+        {
+            ASSERT(pos + 1 < length);
+            return input[pos] | input[pos + 1] << 16;
+        }
+
         int readChecked(int position)
         {
@@ -262 +268 @@
         {
             return (pos + position) == length;
+        }
+
+        bool isNotAvailableInput(int position)
+        {
+            return (pos + position) > length;
         }
 
@@ -994 +1005 @@
     }
 
+    void lookupForBeginChars()
+    {
+        int character;
+        bool firstSingleCharFound;
+
+        while (true) {
+            if (input.isNotAvailableInput(2))
+                return;
+
+            firstSingleCharFound = false;
+
+            character = input.readPair();
+
+            for (unsigned i = 0; i < pattern->m_beginChars.size(); ++i) {
+                BeginChar bc = pattern->m_beginChars[i];
+
+                if (!firstSingleCharFound && bc.value <= 0xFFFF) {
+                    firstSingleCharFound = true;
+                    character &= 0xFFFF;
+                }
+
+                if ((character | bc.mask) == bc.value)
+                    return;
+            }
+
+            input.next();
+        }
+    }
+
 #define MATCH_NEXT() { ++context->term; goto matchAgain; }
 #define BACKTRACK() { --context->term; goto backtrack; }
 #define currentTerm() (disjunction->terms[context->term])
-    JSRegExpResult matchDisjunction(ByteDisjunction* disjunction, DisjunctionContext* context, bool btrack = false)
+    JSRegExpResult matchDisjunction(ByteDisjunction* disjunction, DisjunctionContext* context, bool btrack = false, bool isBody = false)
     {
         if (!--remainingMatchCount)
@@ -1004 +1044 @@
         if (btrack)
             BACKTRACK();
+
+        if (pattern->m_containsBeginChars && isBody)
+            lookupForBeginChars();
 
         context->matchBegin = input.getPos();
@@ -1169 +1212 @@
 
             input.next();
+
+            if (pattern->m_containsBeginChars && isBody)
+                lookupForBeginChars();
+
             context->matchBegin = input.getPos();
 
@@ -1285 +1332 @@
         DisjunctionContext* context = allocDisjunctionContext(pattern->m_body.get());
 
-        JSRegExpResult result = matchDisjunction(pattern->m_body.get(), context);
+        JSRegExpResult result = matchDisjunction(pattern->m_body.get(), context, false, true);
         if (result == JSRegExpMatch) {
             output[0] = context->matchBegin;