Merge WebKit at r78450: Initial merge by git.

Change-Id: I6d3e5f1f868ec266a0aafdef66182ddc3f265dc1

9 files changed, 91 insertions, 52 deletions

diff --git a/Source/JavaScriptCore/yarr/Yarr.h b/Source/JavaScriptCore/yarr/Yarr.h
index 57176bc..de64fdd 100644
--- a/Source/JavaScriptCore/yarr/Yarr.h
+++ b/Source/JavaScriptCore/yarr/Yarr.h
@@ -29,7 +29,6 @@
 #define Yarr_h
 
 #include "YarrInterpreter.h"
-#include "YarrJIT.h"
 #include "YarrPattern.h"
 
 namespace JSC { namespace Yarr {
@@ -61,11 +60,6 @@ enum JSRegExpResult {
 PassOwnPtr<BytecodePattern> byteCompile(YarrPattern&, BumpPointerAllocator*);
 int interpret(BytecodePattern*, const UChar* input, unsigned start, unsigned length, int* output);
 
-#if ENABLE(YARR_JIT)
-void jitCompile(YarrPattern&, JSGlobalData*, YarrCodeBlock& jitObject);
-int execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output);
-#endif
-
 } } // namespace JSC::Yarr
 
 #endif // Yarr_h
diff --git a/Source/JavaScriptCore/yarr/YarrInterpreter.cpp b/Source/JavaScriptCore/yarr/YarrInterpreter.cpp
index d2dbf23..37d44f7 100644
--- a/Source/JavaScriptCore/yarr/YarrInterpreter.cpp
+++ b/Source/JavaScriptCore/yarr/YarrInterpreter.cpp
@@ -203,7 +203,7 @@ public:
         int readChecked(int position)
         {
             ASSERT(position < 0);
-            ASSERT((unsigned)-position <= pos);
+            ASSERT(static_cast<unsigned>(-position) <= pos);
             unsigned p = pos + position;
             ASSERT(p < length);
             return input[p];
@@ -248,8 +248,8 @@ public:
             if ((pos + count) <= length) {
                 pos += count;
                 return true;
-            } else
-                return false;
+            }
+            return false;
         }
 
         void uncheckInput(int count)
@@ -356,8 +356,8 @@ public:
     {
         if (term.inputPosition)
             return (input.atEnd(term.inputPosition)) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.readChecked(term.inputPosition)));
-        else
-            return (input.atEnd()) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.read()));
+
+        return (input.atEnd()) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.read()));
     }
 
     bool matchAssertionWordBoundary(ByteTerm& term)
@@ -577,8 +577,8 @@ public:
             if ((backTrack->matchAmount < term.atom.quantityCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {
                 ++backTrack->matchAmount;
                 return true;
-            } else
-                input.setPos(backTrack->begin);
+            }
+            input.setPos(backTrack->begin);
             break;
         }
 
@@ -1412,7 +1412,7 @@ public:
     }
 
 private:
-    BytecodePattern *pattern;
+    BytecodePattern* pattern;
     int* output;
     InputStream input;
     BumpPointerPool* allocatorPool;
@@ -1847,7 +1847,7 @@ public:
                 case PatternTerm::TypeParentheticalAssertion: {
                     unsigned alternativeFrameLocation = term.frameLocation + YarrStackSpaceForBackTrackInfoParentheticalAssertion;
 
-                    ASSERT(currentCountAlreadyChecked >= (unsigned)term.inputPosition);
+                    ASSERT(currentCountAlreadyChecked >= static_cast<unsigned>(term.inputPosition));
                     int positiveInputOffset = currentCountAlreadyChecked - term.inputPosition;
 
                     atomParentheticalAssertionBegin(term.parentheses.subpatternId, term.invert(), term.frameLocation, alternativeFrameLocation);
diff --git a/Source/JavaScriptCore/yarr/YarrJIT.cpp b/Source/JavaScriptCore/yarr/YarrJIT.cpp
index 9d13d45..e34e6f4 100644
--- a/Source/JavaScriptCore/yarr/YarrJIT.cpp
+++ b/Source/JavaScriptCore/yarr/YarrJIT.cpp
@@ -27,9 +27,7 @@
 #include "YarrJIT.h"
 
 #include "ASCIICType.h"
-#include "JSGlobalData.h"
 #include "LinkBuffer.h"
-#include "MacroAssembler.h"
 #include "Yarr.h"
 
 #if ENABLE(YARR_JIT)
@@ -407,9 +405,9 @@ class YarrGenerator : private MacroAssembler {
             --m_parenNestingLevel;
         }
 
-        ParenthesesTail* addParenthesesTail(PatternTerm& term, ParenthesesTail* nextOuterParenTail)
+        ParenthesesTail* addParenthesesTail(PatternTerm& term, JumpList* jumpListToPriorParen)
         {
-            ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, nextOuterParenTail);
+            ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, jumpListToPriorParen);
             m_parenTails.append(parenthesesTail);
             m_parenTailsForIteration.append(parenthesesTail);
 
@@ -815,7 +813,7 @@ class YarrGenerator : private MacroAssembler {
             , checkedTotal(checkedTotal)
             , m_subParenNum(0)
             , m_linkedBacktrack(0)
-            , m_parenthesesTail(0)
+            , m_jumpList(0)
         {
         }
 
@@ -876,14 +874,14 @@ class YarrGenerator : private MacroAssembler {
             return !disjunction->m_parent;
         }
 
-        void setParenthesesTail(ParenthesesTail* parenthesesTail)
+        void setJumpListToPriorParen(JumpList* jumpList)
         {
-            m_parenthesesTail = parenthesesTail;
+            m_jumpList = jumpList;
         }
 
-        ParenthesesTail* getParenthesesTail()
+        JumpList* getJumpListToPriorParen()
         {
-            return m_parenthesesTail;
+            return m_jumpList;
         }
 
         PatternTerm& lookaheadTerm()
@@ -1018,15 +1016,15 @@ class YarrGenerator : private MacroAssembler {
         unsigned m_subParenNum;
         BacktrackDestination m_backtrack;
         BacktrackDestination* m_linkedBacktrack;
-        ParenthesesTail* m_parenthesesTail;
+        JumpList* m_jumpList;
     };
 
     struct ParenthesesTail {
-        ParenthesesTail(PatternTerm& term, int nestingLevel, ParenthesesTail* nextOuterParenTail)
+        ParenthesesTail(PatternTerm& term, int nestingLevel, JumpList* jumpListToPriorParen)
             : m_term(term)
             , m_nestingLevel(nestingLevel)
             , m_subParenIndex(0)
-            , m_nextOuterParenTail(nextOuterParenTail)
+            , m_jumpListToPriorParen(jumpListToPriorParen)
         {
         }
 
@@ -1052,7 +1050,7 @@ class YarrGenerator : private MacroAssembler {
             if (m_doDirectBacktrack)
                 state.propagateBacktrackingFrom(generator, m_parenBacktrack, false);
             else {
-                stateBacktrack.setBacktrackJumpList(&m_pattBacktrackJumps);
+                stateBacktrack.setBacktrackJumpList(&m_afterBacktrackJumps);
                 stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens);
             }
         }
@@ -1065,7 +1063,7 @@ class YarrGenerator : private MacroAssembler {
 
         void addAfterParenJump(Jump jump)
         {
-            m_pattBacktrackJumps.append(jump);
+            m_afterBacktrackJumps.append(jump);
         }
 
         bool generateCode(YarrGenerator* generator, JumpList& jumpsToNext, bool priorBackTrackFallThrough, bool nextBacktrackFallThrough)
@@ -1091,12 +1089,9 @@ class YarrGenerator : private MacroAssembler {
                 if (m_backtrackToLabel.isSet()) {
                     m_backtrack.setLabel(m_backtrackToLabel);
                     nextBacktrackFallThrough = false;
-                } else if (!m_subParenIndex && m_nextOuterParenTail) {
-                    // If we don't have a destination and we are the first term of a nested paren, go
-                    // back to the outer paren.
-                    // There is an optimization if the next outer paren is the next paren to be emitted.
-                    // In that case we really want the else clause.
-                    m_backtrack.setBacktrackJumpList(&m_nextOuterParenTail->m_withinBacktrackJumps);
+                } else if (m_jumpListToPriorParen) {
+                    // If we don't have a destination, go back to either the prior paren or the next outer paren.
+                    m_backtrack.setBacktrackJumpList(m_jumpListToPriorParen);
                     nextBacktrackFallThrough = false;
                 } else
                     m_backtrack.setBacktrackJumpList(&jumpsToNext);
@@ -1109,7 +1104,7 @@ class YarrGenerator : private MacroAssembler {
             if (m_dataAfterLabelPtr.isSet())
                 generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataAfterLabelPtr, m_backtrackFromAfterParens));
 
-            m_pattBacktrackJumps.link(generator);
+            m_afterBacktrackJumps.link(generator);
 
             if (m_term.quantityType == QuantifierGreedy) {
                 // If this is -1 we have now tested with both with and without the parens.
@@ -1149,14 +1144,14 @@ class YarrGenerator : private MacroAssembler {
         PatternTerm& m_term;
         int m_nestingLevel;
         unsigned m_subParenIndex;
-        ParenthesesTail* m_nextOuterParenTail;
+        JumpList* m_jumpListToPriorParen;
         Label m_nonGreedyTryParentheses;
         Label m_fallThrough;
         Label m_backtrackToLabel;
         Label m_backtrackFromAfterParens;
         DataLabelPtr m_dataAfterLabelPtr;
-        JumpList m_pattBacktrackJumps;
         JumpList m_withinBacktrackJumps;
+        JumpList m_afterBacktrackJumps;
         BacktrackDestination m_parenBacktrack;
         BacktrackDestination m_backtrack;
         bool m_doDirectBacktrack;
@@ -1581,8 +1576,10 @@ class YarrGenerator : private MacroAssembler {
             JumpList successes;
             bool propogateBacktrack = false;
 
-            for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative()) {
+            // Save current state's paren jump list for use with each alternative 
+            JumpList* outerJumpList = state.getJumpListToPriorParen();
 
+            for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative(), state.setJumpListToPriorParen(outerJumpList)) {
                 PatternAlternative* alternative = state.alternative();
                 optimizeAlternative(alternative);
 
@@ -1649,9 +1646,9 @@ class YarrGenerator : private MacroAssembler {
             m_expressionState.incrementParenNestingLevel();
 
             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
-            
-            // Use the current paren Tail to connect the nested parentheses.
-            parenthesesState.setParenthesesTail(state.getParenthesesTail());
+
+            // Use the current state's jump list for the nested parentheses.
+            parenthesesState.setJumpListToPriorParen(state.getJumpListToPriorParen());
 
             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
             // this expects that any backtracks back out of the parentheses will be in the
@@ -1663,6 +1660,8 @@ class YarrGenerator : private MacroAssembler {
             state.propagateBacktrackingFrom(this, parenthesesBacktrack);
             stateBacktrack.propagateBacktrackToLabel(parenthesesBacktrack);
 
+            state.setJumpListToPriorParen(parenthesesState.getJumpListToPriorParen());
+
             m_expressionState.decrementParenNestingLevel();
         } else {
             Jump nonGreedySkipParentheses;
@@ -1687,14 +1686,14 @@ class YarrGenerator : private MacroAssembler {
                     store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
             }
 
-            ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getParenthesesTail());
+            ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getJumpListToPriorParen());
 
             m_expressionState.incrementParenNestingLevel();
 
             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
 
             // Save the parenthesesTail for backtracking from nested parens to this one.
-            parenthesesState.setParenthesesTail(parenthesesTail);
+            parenthesesState.setJumpListToPriorParen(&parenthesesTail->m_withinBacktrackJumps);
 
             // generate the body of the parentheses
             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
@@ -1718,6 +1717,8 @@ class YarrGenerator : private MacroAssembler {
 
             parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label());
 
+            state.setJumpListToPriorParen(&parenthesesTail->m_afterBacktrackJumps);
+            
             parenthesesState.getBacktrackDestination().clear();
 
             if (term.quantityType == QuantifierNonGreedy)
@@ -1977,6 +1978,7 @@ class YarrGenerator : private MacroAssembler {
 
             // if there are any more alternatives, plant the check for input before looping.
             if (state.alternativeValid()) {
+                state.setJumpListToPriorParen(0);
                 PatternAlternative* nextAlternative = state.alternative();
                 if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
                     // We have handled non-repeating alternatives, jump to next iteration 
diff --git a/Source/JavaScriptCore/yarr/YarrJIT.h b/Source/JavaScriptCore/yarr/YarrJIT.h
index 414b575..91c5b85 100644
--- a/Source/JavaScriptCore/yarr/YarrJIT.h
+++ b/Source/JavaScriptCore/yarr/YarrJIT.h
@@ -28,8 +28,10 @@
 
 #if ENABLE(YARR_JIT)
 
+#include "JSGlobalData.h"
 #include "MacroAssembler.h"
 #include "UString.h"
+#include "YarrPattern.h"
 
 #if CPU(X86) && !COMPILER(MSVC)
 #define YARR_CALL __attribute__ ((regparm (3)))
@@ -75,6 +77,9 @@ private:
     bool m_needFallBack;
 };
 
+void jitCompile(YarrPattern&, JSGlobalData*, YarrCodeBlock& jitObject);
+int execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output);
+
 } } // namespace JSC::Yarr
 
 #endif
diff --git a/Source/JavaScriptCore/yarr/YarrParser.h b/Source/JavaScriptCore/yarr/YarrParser.h
index 8c5741a..c59310a 100644
--- a/Source/JavaScriptCore/yarr/YarrParser.h
+++ b/Source/JavaScriptCore/yarr/YarrParser.h
@@ -26,7 +26,7 @@
 #ifndef YarrParser_h
 #define YarrParser_h
 
-#include "UString.h"
+#include <runtime/UString.h>
 #include "Yarr.h"
 #include <wtf/ASCIICType.h>
 #include <wtf/unicode/Unicode.h>
diff --git a/Source/JavaScriptCore/yarr/YarrPattern.cpp b/Source/JavaScriptCore/yarr/YarrPattern.cpp
index 112b65d..3d6dbd3 100644
--- a/Source/JavaScriptCore/yarr/YarrPattern.cpp
+++ b/Source/JavaScriptCore/yarr/YarrPattern.cpp
@@ -488,24 +488,56 @@ public:
         m_alternative = m_alternative->m_parent->m_parent;
 
         PatternTerm& lastTerm = m_alternative->lastTerm();
-        
+
         unsigned numParenAlternatives = parenthesesDisjunction->m_alternatives.size();
         unsigned numBOLAnchoredAlts = 0;
-        // Bubble up BOL flags
+        bool containsEmptyAlternative = false;
+
         for (unsigned i = 0; i < numParenAlternatives; i++) {
+            if (!parenthesesDisjunction->m_alternatives[i]->m_terms.size() && numParenAlternatives > 1) {
+                parenthesesDisjunction->m_alternatives.remove(i);
+                --numParenAlternatives;
+
+                containsEmptyAlternative = true;
+                continue;
+            }
+
+            // Bubble up BOL flags
             if (parenthesesDisjunction->m_alternatives[i]->m_startsWithBOL)
                 numBOLAnchoredAlts++;
         }
-        
+
         if (numBOLAnchoredAlts) {
             m_alternative->m_containsBOL = true;
             // If all the alternatives in parens start with BOL, then so does this one
             if (numBOLAnchoredAlts == numParenAlternatives)
                 m_alternative->m_startsWithBOL = true;
         }
-        
+
         lastTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
         m_invertParentheticalAssertion = false;
+
+        if (containsEmptyAlternative) {
+            // Backup and remove the current disjunction's alternatives.
+            Vector<PatternAlternative*> alternatives;
+            alternatives.append(parenthesesDisjunction->m_alternatives);
+            parenthesesDisjunction->m_alternatives.clear();
+            PatternAlternative* alternative = parenthesesDisjunction->addNewAlternative();
+
+            // Insert a new non-capturing parentheses.
+            unsigned subpatternId = m_pattern.m_numSubpatterns + 1;
+            PatternDisjunction* newDisjunction = new PatternDisjunction(alternative);
+            m_pattern.m_disjunctions.append(newDisjunction);
+            alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, newDisjunction, false, false));
+            newDisjunction->m_alternatives.append(alternatives);
+
+            // Set the quantifier of the new parentheses to '?' and set the inherited properties.
+            PatternTerm& disjunctionTerm = alternative->lastTerm();
+            disjunctionTerm.quantify(1, QuantifierGreedy);
+            disjunctionTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
+            alternative->m_containsBOL = m_alternative->m_containsBOL;
+            alternative->m_startsWithBOL = m_alternative->m_startsWithBOL;
+        }
     }
 
     void atomBackReference(unsigned subpatternId)
diff --git a/Source/JavaScriptCore/yarr/YarrPattern.h b/Source/JavaScriptCore/yarr/YarrPattern.h
index d80f692..cfe804f 100644
--- a/Source/JavaScriptCore/yarr/YarrPattern.h
+++ b/Source/JavaScriptCore/yarr/YarrPattern.h
@@ -27,11 +27,10 @@
 #ifndef YarrPattern_h
 #define YarrPattern_h
 
+#include <runtime/UString.h>
 #include <wtf/Vector.h>
 #include <wtf/unicode/Unicode.h>
 
-#include <UString.h>
-
 namespace JSC { namespace Yarr {
 
 struct PatternDisjunction;
diff --git a/Source/JavaScriptCore/yarr/YarrSyntaxChecker.h b/Source/JavaScriptCore/yarr/YarrSyntaxChecker.h
index e48cb9e..2013671 100644
--- a/Source/JavaScriptCore/yarr/YarrSyntaxChecker.h
+++ b/Source/JavaScriptCore/yarr/YarrSyntaxChecker.h
@@ -26,7 +26,7 @@
 #ifndef YarrSyntaxChecker_h
 #define YarrSyntaxChecker_h
 
-#include <UString.h>
+#include <runtime/UString.h>
 
 namespace JSC { namespace Yarr {
 
diff --git a/Source/JavaScriptCore/yarr/yarr.pri b/Source/JavaScriptCore/yarr/yarr.pri
new file mode 100644
index 0000000..a7b1242
--- /dev/null
+++ b/Source/JavaScriptCore/yarr/yarr.pri
@@ -0,0 +1,7 @@
+# Yet Another Regex Runtime - Qt4 build info
+
+SOURCES += \
+    yarr/YarrInterpreter.cpp \
+    yarr/YarrPattern.cpp \
+    yarr/YarrSyntaxChecker.cpp
+