2010-12-03 Michael Saboff <msaboff@apple.com>
authormsaboff@apple.com <msaboff@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 3 Dec 2010 22:48:19 +0000 (22:48 +0000)
committermsaboff@apple.com <msaboff@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 3 Dec 2010 22:48:19 +0000 (22:48 +0000)
        Reviewed by Gavin Barraclough

        Changes to significantly reduce branches to branches in JIT'ed
        parentheses backtrack processing.  The changes include the following:
        - Taking the backtracking processing out of line and adding it as
          code at the end of the JIT'ed routine.
        - Allow backtracks to be direct via an indirect branch for an address
          pushed onto the stack.  If the use of an indirect branch is from a
          conditional jump, then we emit a trampoline at the end of the
          routine.
        - Propogate backtracks instead of adding trampolines.  Backtracks are
          propogated to where they are used.  This change also eliminated
          trampoline branch code that aren't used.
        - Added global expression state to keep track of parentheses tail
          code and indirect branches.
        Other changes made to support these changes.
        - Split invertOrCapture flag on Patterns to two separate flags.  Added
          getters for these flags.  Rippled these changes to both the JIT
          and interpreter code.
        - Split BacktrackDestination out off TermGenerationState struct.
          This is done to hold references to a backtrack for later code
          generation.
        https://bugs.webkit.org/show_bug.cgi?id=50295

        * assembler/ARMAssembler.h:
        (JSC::ARMAssembler::JmpDst::isSet):
        * assembler/ARMv7Assembler.h:
        (JSC::ARMv7Assembler::JmpDst::isSet):
        * assembler/AbstractMacroAssembler.h:
        (JSC::AbstractMacroAssembler::Label::isSet):
        (JSC::AbstractMacroAssembler::DataLabelPtr::isUsed):
        (JSC::AbstractMacroAssembler::DataLabelPtr::used):
        (JSC::AbstractMacroAssembler::JumpList::clear):
        * assembler/MIPSAssembler.h:
        (JSC::MIPSAssembler::JmpDst::isSet):
        * assembler/X86Assembler.h:
        (JSC::X86Assembler::JmpDst::isSet):
        * yarr/RegexCompiler.cpp:
        (JSC::Yarr::RegexPatternConstructor::atomParenthesesSubpatternBegin):
        (JSC::Yarr::RegexPatternConstructor::atomParentheticalAssertionBegin):
        (JSC::Yarr::RegexPatternConstructor::atomBackReference):
        (JSC::Yarr::RegexPatternConstructor::setupAlternativeBeginTerms):
        * yarr/RegexInterpreter.cpp:
        (JSC::Yarr::ByteCompiler::atomParenthesesOnceBegin):
        (JSC::Yarr::ByteCompiler::atomParenthesesTerminalBegin):
        (JSC::Yarr::ByteCompiler::atomParenthesesSubpatternBegin):
        (JSC::Yarr::ByteCompiler::atomParentheticalAssertionBegin):
        (JSC::Yarr::ByteCompiler::atomParentheticalAssertionEnd):
        (JSC::Yarr::ByteCompiler::atomParenthesesSubpatternEnd):
        (JSC::Yarr::ByteCompiler::atomParenthesesOnceEnd):
        (JSC::Yarr::ByteCompiler::atomParenthesesTerminalEnd):
        (JSC::Yarr::ByteCompiler::emitDisjunction):
        * yarr/RegexInterpreter.h:
        (JSC::Yarr::ByteTerm::ByteTerm):
        (JSC::Yarr::ByteTerm::BackReference):
        (JSC::Yarr::ByteTerm::invert):
        (JSC::Yarr::ByteTerm::capture):
        * yarr/RegexJIT.cpp:
        (JSC::Yarr::RegexGenerator::IndirectJumpEntry::IndirectJumpEntry):
        (JSC::Yarr::RegexGenerator::IndirectJumpEntry::addJump):
        (JSC::Yarr::RegexGenerator::GenerationState::GenerationState):
        (JSC::Yarr::RegexGenerator::GenerationState::addIndirectJumpEntry):
        (JSC::Yarr::RegexGenerator::GenerationState::emitIndirectJumpTable):
        (JSC::Yarr::RegexGenerator::GenerationState::addParenthesesTail):
        (JSC::Yarr::RegexGenerator::GenerationState::emitParenthesesTail):
        (JSC::Yarr::RegexGenerator::GenerationState::addJumpToNextInteration):
        (JSC::Yarr::RegexGenerator::GenerationState::addJumpsToNextInteration):
        (JSC::Yarr::RegexGenerator::GenerationState::addDataLabelToNextIteration):
        (JSC::Yarr::RegexGenerator::GenerationState::linkToNextIteration):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::BacktrackDestination):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::clear):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::clearDataLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::haveDestination):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::isStackOffset):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::isLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::isJumpList):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::haveDataLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::copyTarget):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::copyTo):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::addBacktrackJump):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::setStackOffset):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::setLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::setNextBacktrackLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackToLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackJumpList):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackSourceLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::setDataLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::setSubDataLabelPtr):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::linkToNextBacktrack):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::getStackOffset):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::getLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::getBacktrackJumps):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::getDataLabel):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::jumpToBacktrack):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::linkDataLabelToHereIfExists):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::plantJumpToBacktrackIfExists):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::linkAlternativeBacktracks):
        (JSC::Yarr::RegexGenerator::BacktrackDestination::linkAlternativeBacktracksTo):
        (JSC::Yarr::RegexGenerator::TermGenerationState::TermGenerationState):
        (JSC::Yarr::RegexGenerator::TermGenerationState::resetAlternative):
        (JSC::Yarr::RegexGenerator::TermGenerationState::isLastAlternative):
        (JSC::Yarr::RegexGenerator::TermGenerationState::clearBacktrack):
        (JSC::Yarr::RegexGenerator::TermGenerationState::jumpToBacktrack):
        (JSC::Yarr::RegexGenerator::TermGenerationState::plantJumpToBacktrackIfExists):
        (JSC::Yarr::RegexGenerator::TermGenerationState::linkDataLabelToBacktrackIfExists):
        (JSC::Yarr::RegexGenerator::TermGenerationState::addBacktrackJump):
        (JSC::Yarr::RegexGenerator::TermGenerationState::setDataLabelPtr):
        (JSC::Yarr::RegexGenerator::TermGenerationState::setBackTrackStackOffset):
        (JSC::Yarr::RegexGenerator::TermGenerationState::setBacktrackLabel):
        (JSC::Yarr::RegexGenerator::TermGenerationState::linkAlternativeBacktracks):
        (JSC::Yarr::RegexGenerator::TermGenerationState::linkAlternativeBacktracksTo):
        (JSC::Yarr::RegexGenerator::TermGenerationState::setBacktrackLink):
        (JSC::Yarr::RegexGenerator::TermGenerationState::chainBacktracks):
        (JSC::Yarr::RegexGenerator::TermGenerationState::chainBacktrackJumps):
        (JSC::Yarr::RegexGenerator::TermGenerationState::getBacktrackDestination):
        (JSC::Yarr::RegexGenerator::TermGenerationState::propagateBacktrackingFrom):
        (JSC::Yarr::RegexGenerator::ParenthesesTail::ParenthesesTail):
        (JSC::Yarr::RegexGenerator::ParenthesesTail::processBacktracks):
        (JSC::Yarr::RegexGenerator::ParenthesesTail::setNextIteration):
        (JSC::Yarr::RegexGenerator::ParenthesesTail::generateCode):
        (JSC::Yarr::RegexGenerator::generateAssertionBOL):
        (JSC::Yarr::RegexGenerator::generateAssertionEOL):
        (JSC::Yarr::RegexGenerator::generateAssertionWordBoundary):
        (JSC::Yarr::RegexGenerator::generatePatternCharacterSingle):
        (JSC::Yarr::RegexGenerator::generatePatternCharacterPair):
        (JSC::Yarr::RegexGenerator::generatePatternCharacterFixed):
        (JSC::Yarr::RegexGenerator::generatePatternCharacterGreedy):
        (JSC::Yarr::RegexGenerator::generatePatternCharacterNonGreedy):
        (JSC::Yarr::RegexGenerator::generateCharacterClassSingle):
        (JSC::Yarr::RegexGenerator::generateCharacterClassFixed):
        (JSC::Yarr::RegexGenerator::generateCharacterClassGreedy):
        (JSC::Yarr::RegexGenerator::generateCharacterClassNonGreedy):
        (JSC::Yarr::RegexGenerator::generateParenthesesDisjunction):
        (JSC::Yarr::RegexGenerator::generateParenthesesSingle):
        (JSC::Yarr::RegexGenerator::generateParenthesesGreedyNoBacktrack):
        (JSC::Yarr::RegexGenerator::generateParentheticalAssertion):
        (JSC::Yarr::RegexGenerator::generateDisjunction):
        (JSC::Yarr::RegexGenerator::compile):
        * yarr/RegexPattern.h:
        (JSC::Yarr::PatternTerm::PatternTerm):
        (JSC::Yarr::PatternTerm::invert):
        (JSC::Yarr::PatternTerm::capture):
2010-12-03  Michael Saboff  <msaboff@apple.com>

        Reviewed by Gavin Barraclough

        Added new tests to support changes to Regexp JIT code handling
        of parentheses.  Tests focused on backtracking and nested
        subexpressions.
        https://bugs.webkit.org/show_bug.cgi?id=50295

        * fast/regex/parentheses-expected.txt: Added.
        * fast/regex/parentheses.html: Added.
        * fast/regex/script-tests/parentheses.js: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@73307 268f45cc-cd09-0410-ab3c-d52691b4dbfc

15 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/assembler/ARMAssembler.h
JavaScriptCore/assembler/ARMv7Assembler.h
JavaScriptCore/assembler/AbstractMacroAssembler.h
JavaScriptCore/assembler/MIPSAssembler.h
JavaScriptCore/assembler/X86Assembler.h
JavaScriptCore/yarr/RegexCompiler.cpp
JavaScriptCore/yarr/RegexInterpreter.cpp
JavaScriptCore/yarr/RegexInterpreter.h
JavaScriptCore/yarr/RegexJIT.cpp
JavaScriptCore/yarr/RegexPattern.h
LayoutTests/ChangeLog
LayoutTests/fast/regex/parentheses-expected.txt [new file with mode: 0644]
LayoutTests/fast/regex/parentheses.html [new file with mode: 0644]
LayoutTests/fast/regex/script-tests/parentheses.js [new file with mode: 0644]

index dc129b1..9b804bd 100644 (file)
@@ -1,3 +1,148 @@
+2010-12-03  Michael Saboff  <msaboff@apple.com>
+
+        Reviewed by Gavin Barraclough
+
+        Changes to significantly reduce branches to branches in JIT'ed
+        parentheses backtrack processing.  The changes include the following:
+        - Taking the backtracking processing out of line and adding it as
+          code at the end of the JIT'ed routine.
+        - Allow backtracks to be direct via an indirect branch for an address
+          pushed onto the stack.  If the use of an indirect branch is from a
+          conditional jump, then we emit a trampoline at the end of the 
+          routine.
+        - Propogate backtracks instead of adding trampolines.  Backtracks are
+          propogated to where they are used.  This change also eliminated 
+          trampoline branch code that aren't used.
+        - Added global expression state to keep track of parentheses tail
+          code and indirect branches.
+        Other changes made to support these changes.
+        - Split invertOrCapture flag on Patterns to two separate flags.  Added
+          getters for these flags.  Rippled these changes to both the JIT 
+          and interpreter code.
+        - Split BacktrackDestination out off TermGenerationState struct.
+          This is done to hold references to a backtrack for later code
+          generation.
+        https://bugs.webkit.org/show_bug.cgi?id=50295
+
+        * assembler/ARMAssembler.h:
+        (JSC::ARMAssembler::JmpDst::isSet):
+        * assembler/ARMv7Assembler.h:
+        (JSC::ARMv7Assembler::JmpDst::isSet):
+        * assembler/AbstractMacroAssembler.h:
+        (JSC::AbstractMacroAssembler::Label::isSet):
+        (JSC::AbstractMacroAssembler::DataLabelPtr::isUsed):
+        (JSC::AbstractMacroAssembler::DataLabelPtr::used):
+        (JSC::AbstractMacroAssembler::JumpList::clear):
+        * assembler/MIPSAssembler.h:
+        (JSC::MIPSAssembler::JmpDst::isSet):
+        * assembler/X86Assembler.h:
+        (JSC::X86Assembler::JmpDst::isSet):
+        * yarr/RegexCompiler.cpp:
+        (JSC::Yarr::RegexPatternConstructor::atomParenthesesSubpatternBegin):
+        (JSC::Yarr::RegexPatternConstructor::atomParentheticalAssertionBegin):
+        (JSC::Yarr::RegexPatternConstructor::atomBackReference):
+        (JSC::Yarr::RegexPatternConstructor::setupAlternativeBeginTerms):
+        * yarr/RegexInterpreter.cpp:
+        (JSC::Yarr::ByteCompiler::atomParenthesesOnceBegin):
+        (JSC::Yarr::ByteCompiler::atomParenthesesTerminalBegin):
+        (JSC::Yarr::ByteCompiler::atomParenthesesSubpatternBegin):
+        (JSC::Yarr::ByteCompiler::atomParentheticalAssertionBegin):
+        (JSC::Yarr::ByteCompiler::atomParentheticalAssertionEnd):
+        (JSC::Yarr::ByteCompiler::atomParenthesesSubpatternEnd):
+        (JSC::Yarr::ByteCompiler::atomParenthesesOnceEnd):
+        (JSC::Yarr::ByteCompiler::atomParenthesesTerminalEnd):
+        (JSC::Yarr::ByteCompiler::emitDisjunction):
+        * yarr/RegexInterpreter.h:
+        (JSC::Yarr::ByteTerm::ByteTerm):
+        (JSC::Yarr::ByteTerm::BackReference):
+        (JSC::Yarr::ByteTerm::invert):
+        (JSC::Yarr::ByteTerm::capture):
+        * yarr/RegexJIT.cpp:
+        (JSC::Yarr::RegexGenerator::IndirectJumpEntry::IndirectJumpEntry):
+        (JSC::Yarr::RegexGenerator::IndirectJumpEntry::addJump):
+        (JSC::Yarr::RegexGenerator::GenerationState::GenerationState):
+        (JSC::Yarr::RegexGenerator::GenerationState::addIndirectJumpEntry):
+        (JSC::Yarr::RegexGenerator::GenerationState::emitIndirectJumpTable):
+        (JSC::Yarr::RegexGenerator::GenerationState::addParenthesesTail):
+        (JSC::Yarr::RegexGenerator::GenerationState::emitParenthesesTail):
+        (JSC::Yarr::RegexGenerator::GenerationState::addJumpToNextInteration):
+        (JSC::Yarr::RegexGenerator::GenerationState::addJumpsToNextInteration):
+        (JSC::Yarr::RegexGenerator::GenerationState::addDataLabelToNextIteration):
+        (JSC::Yarr::RegexGenerator::GenerationState::linkToNextIteration):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::BacktrackDestination):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::clear):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::clearDataLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::haveDestination):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::isStackOffset):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::isLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::isJumpList):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::haveDataLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::copyTarget):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::copyTo):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::addBacktrackJump):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::setStackOffset):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::setLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::setNextBacktrackLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackToLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackJumpList):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackSourceLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::setDataLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::setSubDataLabelPtr):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::linkToNextBacktrack):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::getStackOffset):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::getLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::getBacktrackJumps):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::getDataLabel):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::jumpToBacktrack):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::linkDataLabelToHereIfExists):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::plantJumpToBacktrackIfExists):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::linkAlternativeBacktracks):
+        (JSC::Yarr::RegexGenerator::BacktrackDestination::linkAlternativeBacktracksTo):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::TermGenerationState):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::resetAlternative):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::isLastAlternative):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::clearBacktrack):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::jumpToBacktrack):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::plantJumpToBacktrackIfExists):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::linkDataLabelToBacktrackIfExists):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::addBacktrackJump):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::setDataLabelPtr):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::setBackTrackStackOffset):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::setBacktrackLabel):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::linkAlternativeBacktracks):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::linkAlternativeBacktracksTo):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::setBacktrackLink):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::chainBacktracks):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::chainBacktrackJumps):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::getBacktrackDestination):
+        (JSC::Yarr::RegexGenerator::TermGenerationState::propagateBacktrackingFrom):
+        (JSC::Yarr::RegexGenerator::ParenthesesTail::ParenthesesTail):
+        (JSC::Yarr::RegexGenerator::ParenthesesTail::processBacktracks):
+        (JSC::Yarr::RegexGenerator::ParenthesesTail::setNextIteration):
+        (JSC::Yarr::RegexGenerator::ParenthesesTail::generateCode):
+        (JSC::Yarr::RegexGenerator::generateAssertionBOL):
+        (JSC::Yarr::RegexGenerator::generateAssertionEOL):
+        (JSC::Yarr::RegexGenerator::generateAssertionWordBoundary):
+        (JSC::Yarr::RegexGenerator::generatePatternCharacterSingle):
+        (JSC::Yarr::RegexGenerator::generatePatternCharacterPair):
+        (JSC::Yarr::RegexGenerator::generatePatternCharacterFixed):
+        (JSC::Yarr::RegexGenerator::generatePatternCharacterGreedy):
+        (JSC::Yarr::RegexGenerator::generatePatternCharacterNonGreedy):
+        (JSC::Yarr::RegexGenerator::generateCharacterClassSingle):
+        (JSC::Yarr::RegexGenerator::generateCharacterClassFixed):
+        (JSC::Yarr::RegexGenerator::generateCharacterClassGreedy):
+        (JSC::Yarr::RegexGenerator::generateCharacterClassNonGreedy):
+        (JSC::Yarr::RegexGenerator::generateParenthesesDisjunction):
+        (JSC::Yarr::RegexGenerator::generateParenthesesSingle):
+        (JSC::Yarr::RegexGenerator::generateParenthesesGreedyNoBacktrack):
+        (JSC::Yarr::RegexGenerator::generateParentheticalAssertion):
+        (JSC::Yarr::RegexGenerator::generateDisjunction):
+        (JSC::Yarr::RegexGenerator::compile):
+        * yarr/RegexPattern.h:
+        (JSC::Yarr::PatternTerm::PatternTerm):
+        (JSC::Yarr::PatternTerm::invert):
+        (JSC::Yarr::PatternTerm::capture):
+
 2010-12-03  Chris Rogers  <crogers@google.com>
 
         Reviewed by Kenneth Russell.
index 1d24dd3..77ec60f 100644 (file)
@@ -240,6 +240,7 @@ namespace JSC {
             }
 
             bool isUsed() const { return m_used; }
+            bool isSet() const { return (m_offset != -1); }
             void used() { m_used = true; }
         private:
             JmpDst(int offset)
index a40208a..b962b45 100644 (file)
@@ -553,6 +553,7 @@ public:
         }
 
         bool isUsed() const { return m_used; }
+        bool isSet() const { return (m_offset != -1); }
         void used() { m_used = true; }
     private:
         JmpDst(int offset)
index 1fa5ec7..07bd702 100644 (file)
@@ -241,6 +241,7 @@ public:
         }
         
         bool isUsed() const { return m_label.isUsed(); }
+        bool isSet() const { return m_label.isSet(); }
         void used() { m_label.used(); }
     private:
         JmpDst m_label;
@@ -264,6 +265,8 @@ public:
         {
         }
         
+        bool isSet() const { return m_label.isSet(); }
+        
     private:
         JmpDst m_label;
     };
@@ -410,6 +413,11 @@ public:
             return !m_jumps.size();
         }
         
+        void clear()
+        {
+            m_jumps.clear();
+        }
+        
         const JumpVector& jumps() { return m_jumps; }
 
     private:
index f9e40c4..f7bea6c 100644 (file)
@@ -193,6 +193,7 @@ public:
         }
 
         bool isUsed() const { return m_used; }
+        bool isSet() const { return (m_offset != -1); }
         void used() { m_used = true; }
     private:
         JmpDst(int offset)
index 20d72f5..b352ad4 100644 (file)
@@ -248,6 +248,7 @@ public:
         }
 
         bool isUsed() const { return m_used; }
+        bool isSet() const { return (m_offset != -1); }
         void used() { m_used = true; }
     private:
         JmpDst(int offset)
index e40c791..3a76083 100644 (file)
@@ -459,7 +459,7 @@ public:
 
         PatternDisjunction* parenthesesDisjunction = new PatternDisjunction(m_alternative);
         m_pattern.m_disjunctions.append(parenthesesDisjunction);
-        m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, capture));
+        m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, capture, false));
         m_alternative = parenthesesDisjunction->addNewAlternative();
     }
 
@@ -467,7 +467,7 @@ public:
     {
         PatternDisjunction* parenthesesDisjunction = new PatternDisjunction(m_alternative);
         m_pattern.m_disjunctions.append(parenthesesDisjunction);
-        m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction, invert));
+        m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction, false, invert));
         m_alternative = parenthesesDisjunction->addNewAlternative();
         m_invertParentheticalAssertion = invert;
     }
@@ -520,7 +520,7 @@ public:
             PatternTerm& term = currentAlternative->lastTerm();
             ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));
 
-            if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.invertOrCapture && (subpatternId == term.parentheses.subpatternId)) {
+            if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.capture() && (subpatternId == term.parentheses.subpatternId)) {
                 m_alternative->m_terms.append(PatternTerm::ForwardReference());
                 return;
             }
@@ -845,7 +845,7 @@ public:
                 return false;
 
             case PatternTerm::TypeParentheticalAssertion:
-                if (term.invertOrCapture)
+                if (term.invert())
                     return false;
 
             case PatternTerm::TypeParenthesesSubpattern:
index d0fe41d..0cb0d9c 100644 (file)
@@ -1522,7 +1522,7 @@ public:
     {
         int beginTerm = m_bodyDisjunction->terms.size();
 
-        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, inputPosition));
+        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, false, inputPosition));
         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
         m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());
         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;
@@ -1535,7 +1535,7 @@ public:
     {
         int beginTerm = m_bodyDisjunction->terms.size();
 
-        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternTerminalBegin, subpatternId, capture, inputPosition));
+        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternTerminalBegin, subpatternId, capture, false, inputPosition));
         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
         m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());
         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;
@@ -1552,7 +1552,7 @@ public:
 
         int beginTerm = m_bodyDisjunction->terms.size();
 
-        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, inputPosition));
+        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, false, inputPosition));
         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
         m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());
         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;
@@ -1565,7 +1565,7 @@ public:
     {
         int beginTerm = m_bodyDisjunction->terms.size();
 
-        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParentheticalAssertionBegin, subpatternId, invert, 0));
+        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParentheticalAssertionBegin, subpatternId, false, invert, 0));
         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
         m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());
         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;
@@ -1582,10 +1582,10 @@ public:
 
         ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeParentheticalAssertionBegin);
 
-        bool invertOrCapture = m_bodyDisjunction->terms[beginTerm].invertOrCapture;
+        bool invert = m_bodyDisjunction->terms[beginTerm].invert();
         unsigned subpatternId = m_bodyDisjunction->terms[beginTerm].atom.subpatternId;
 
-        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParentheticalAssertionEnd, subpatternId, invertOrCapture, inputPosition));
+        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParentheticalAssertionEnd, subpatternId, false, invert, inputPosition));
         m_bodyDisjunction->terms[beginTerm].atom.parenthesesWidth = endTerm - beginTerm;
         m_bodyDisjunction->terms[endTerm].atom.parenthesesWidth = endTerm - beginTerm;
         m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation;
@@ -1677,7 +1677,7 @@ public:
 
         ByteTerm& parenthesesBegin = m_bodyDisjunction->terms[beginTerm];
 
-        bool invertOrCapture = parenthesesBegin.invertOrCapture;
+        bool capture = parenthesesBegin.capture();
         unsigned subpatternId = parenthesesBegin.atom.subpatternId;
 
         unsigned numSubpatterns = lastSubpatternId - subpatternId + 1;
@@ -1691,7 +1691,7 @@ public:
         m_bodyDisjunction->terms.shrink(beginTerm);
 
         m_allParenthesesInfo.append(parenthesesDisjunction);
-        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, invertOrCapture, inputPosition));
+        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, capture, inputPosition));
 
         m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount;
         m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
@@ -1706,10 +1706,10 @@ public:
 
         ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeParenthesesSubpatternOnceBegin);
 
-        bool invertOrCapture = m_bodyDisjunction->terms[beginTerm].invertOrCapture;
+        bool capture = m_bodyDisjunction->terms[beginTerm].capture();
         unsigned subpatternId = m_bodyDisjunction->terms[beginTerm].atom.subpatternId;
 
-        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceEnd, subpatternId, invertOrCapture, inputPosition));
+        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceEnd, subpatternId, capture, false, inputPosition));
         m_bodyDisjunction->terms[beginTerm].atom.parenthesesWidth = endTerm - beginTerm;
         m_bodyDisjunction->terms[endTerm].atom.parenthesesWidth = endTerm - beginTerm;
         m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation;
@@ -1728,10 +1728,10 @@ public:
 
         ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeParenthesesSubpatternTerminalBegin);
 
-        bool invertOrCapture = m_bodyDisjunction->terms[beginTerm].invertOrCapture;
+        bool capture = m_bodyDisjunction->terms[beginTerm].capture();
         unsigned subpatternId = m_bodyDisjunction->terms[beginTerm].atom.subpatternId;
 
-        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternTerminalEnd, subpatternId, invertOrCapture, inputPosition));
+        m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternTerminalEnd, subpatternId, capture, false, inputPosition));
         m_bodyDisjunction->terms[beginTerm].atom.parenthesesWidth = endTerm - beginTerm;
         m_bodyDisjunction->terms[endTerm].atom.parenthesesWidth = endTerm - beginTerm;
         m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation;
@@ -1814,7 +1814,7 @@ public:
                     break;
 
                 case PatternTerm::TypeAssertionWordBoundary:
-                    assertionWordBoundary(term.invertOrCapture, term.inputPosition - currentCountAlreadyChecked);
+                    assertionWordBoundary(term.invert(), term.inputPosition - currentCountAlreadyChecked);
                     break;
 
                 case PatternTerm::TypePatternCharacter:
@@ -1822,7 +1822,7 @@ public:
                     break;
 
                 case PatternTerm::TypeCharacterClass:
-                    atomCharacterClass(term.characterClass, term.invertOrCapture, term.inputPosition - currentCountAlreadyChecked, term.frameLocation, term.quantityCount, term.quantityType);
+                    atomCharacterClass(term.characterClass, term.invert(), term.inputPosition - currentCountAlreadyChecked, term.frameLocation, term.quantityCount, term.quantityType);
                     break;
 
                 case PatternTerm::TypeBackReference:
@@ -1842,17 +1842,17 @@ public:
                         else
                             alternativeFrameLocation += RegexStackSpaceForBackTrackInfoParenthesesOnce;
                         unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
-                        atomParenthesesOnceBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, alternativeFrameLocation);
+                        atomParenthesesOnceBegin(term.parentheses.subpatternId, term.capture(), delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, alternativeFrameLocation);
                         emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, disjunctionAlreadyCheckedCount);
                         atomParenthesesOnceEnd(delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType);
                     } else if (term.parentheses.isTerminal) {
                         unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
-                        atomParenthesesTerminalBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, term.frameLocation + RegexStackSpaceForBackTrackInfoParenthesesOnce);
+                        atomParenthesesTerminalBegin(term.parentheses.subpatternId, term.capture(), delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, term.frameLocation + RegexStackSpaceForBackTrackInfoParenthesesOnce);
                         emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, disjunctionAlreadyCheckedCount);
                         atomParenthesesTerminalEnd(delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType);
                     } else {
                         unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
-                        atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, 0);
+                        atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.capture(), delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, 0);
                         emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0);
                         atomParenthesesSubpatternEnd(term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
                     }
@@ -1865,7 +1865,7 @@ public:
                     ASSERT(currentCountAlreadyChecked >= (unsigned)term.inputPosition);
                     int positiveInputOffset = currentCountAlreadyChecked - term.inputPosition;
 
-                    atomParentheticalAssertionBegin(term.parentheses.subpatternId, term.invertOrCapture, term.frameLocation, alternativeFrameLocation);
+                    atomParentheticalAssertionBegin(term.parentheses.subpatternId, term.invert(), term.frameLocation, alternativeFrameLocation);
                     emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, positiveInputOffset, true);
                     atomParentheticalAssertionEnd(0, term.frameLocation, term.quantityCount, term.quantityType);
                     break;
index 3980ab9..0fd8a57 100644 (file)
@@ -87,7 +87,6 @@ struct ByteTerm {
         TypeParentheticalAssertionEnd,
         TypeCheckInput,
     } type;
-    bool invertOrCapture;
     union {
         struct {
             union {
@@ -114,10 +113,14 @@ struct ByteTerm {
         unsigned checkInputCount;
     };
     unsigned frameLocation;
+    bool m_capture : 1;
+    bool m_invert : 1;
     int inputPosition;
 
     ByteTerm(UChar ch, int inputPos, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
         : frameLocation(frameLocation)
+        , m_capture(false)
+        , m_invert(false)
     {
         switch (quantityType) {
         case QuantifierFixedCount:
@@ -139,6 +142,8 @@ struct ByteTerm {
 
     ByteTerm(UChar lo, UChar hi, int inputPos, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
         : frameLocation(frameLocation)
+        , m_capture(false)
+        , m_invert(false)
     {
         switch (quantityType) {
         case QuantifierFixedCount:
@@ -161,7 +166,8 @@ struct ByteTerm {
 
     ByteTerm(CharacterClass* characterClass, bool invert, int inputPos)
         : type(ByteTerm::TypeCharacterClass)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         atom.characterClass = characterClass;
         atom.quantityType = QuantifierFixedCount;
@@ -169,9 +175,10 @@ struct ByteTerm {
         inputPosition = inputPos;
     }
 
-    ByteTerm(Type type, unsigned subpatternId, ByteDisjunction* parenthesesInfo, bool invertOrCapture, int inputPos)
+    ByteTerm(Type type, unsigned subpatternId, ByteDisjunction* parenthesesInfo, bool capture, int inputPos)
         : type(type)
-        , invertOrCapture(invertOrCapture)
+        , m_capture(capture)
+        , m_invert(false)
     {
         atom.subpatternId = subpatternId;
         atom.parenthesesDisjunction = parenthesesInfo;
@@ -182,15 +189,17 @@ struct ByteTerm {
     
     ByteTerm(Type type, bool invert = false)
         : type(type)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         atom.quantityType = QuantifierFixedCount;
         atom.quantityCount = 1;
     }
 
-    ByteTerm(Type type, unsigned subpatternId, bool invertOrCapture, int inputPos)
+    ByteTerm(Type type, unsigned subpatternId, bool capture, bool invert, int inputPos)
         : type(type)
-        , invertOrCapture(invertOrCapture)
+        , m_capture(capture)
+        , m_invert(invert)
     {
         atom.subpatternId = subpatternId;
         atom.quantityType = QuantifierFixedCount;
@@ -228,7 +237,7 @@ struct ByteTerm {
     
     static ByteTerm BackReference(unsigned subpatternId, int inputPos)
     {
-        return ByteTerm(TypeBackReference, subpatternId, false, inputPos);
+        return ByteTerm(TypeBackReference, subpatternId, false, false, inputPos);
     }
 
     static ByteTerm BodyAlternativeBegin(bool onceThrough)
@@ -297,12 +306,12 @@ struct ByteTerm {
 
     bool invert()
     {
-        return invertOrCapture;
+        return m_invert;
     }
 
     bool capture()
     {
-        return invertOrCapture;
+        return m_capture;
     }
 };
 
index 04fa69e..7f1856a 100644 (file)
@@ -287,6 +287,27 @@ class RegexGenerator : private MacroAssembler {
         jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
     }
 
+    struct IndirectJumpEntry {
+        IndirectJumpEntry(int32_t stackOffset)
+            : m_stackOffset(stackOffset)
+        {
+        }
+
+        IndirectJumpEntry(int32_t stackOffset, Jump jump)
+            : m_stackOffset(stackOffset)
+        {
+            addJump(jump);
+        }
+        
+        void addJump(Jump jump)
+        {
+            m_relJumps.append(jump);
+        }
+        
+        int32_t m_stackOffset;
+        JumpList m_relJumps;
+    };
+        
     struct AlternativeBacktrackRecord {
         DataLabelPtr dataLabel;
         Label backtrackLocation;
@@ -298,16 +319,446 @@ class RegexGenerator : private MacroAssembler {
         }
     };
 
+    struct ParenthesesTail;
+    struct TermGenerationState;
+    
+    struct GenerationState {
+        typedef HashMap<int, IndirectJumpEntry*, WTF::IntHash<uint32_t>, UnsignedWithZeroKeyHashTraits<uint32_t> > IndirectJumpHashMap;
+        
+        GenerationState()
+        {
+        }
+        
+        void addIndirectJumpEntry(int32_t stackOffset, Jump jump)
+        {
+            IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset);
+            
+            ASSERT(stackOffset >= 0);
+            
+            uint32_t offset = static_cast<uint32_t>(stackOffset);
+            
+            if (result == m_indirectJumpMap.end())
+                m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, jump));
+            else
+                result->second->addJump(jump);
+        }
+        
+        void addIndirectJumpEntry(int32_t stackOffset, JumpList jumps)
+        {
+            JumpList::JumpVector jumpVector = jumps.jumps();
+            size_t size = jumpVector.size();
+            for (size_t i = 0; i < size; ++i)
+                addIndirectJumpEntry(stackOffset, jumpVector[i]);
+            
+            jumps.empty();
+        }
+        
+        void emitIndirectJumpTable(MacroAssembler* masm)
+        {
+            for (IndirectJumpHashMap::iterator iter = m_indirectJumpMap.begin(); iter != m_indirectJumpMap.end(); ++iter) {
+                IndirectJumpEntry* indJumpEntry = iter->second;
+                indJumpEntry->m_relJumps.link(masm);
+                masm->jump(Address(stackPointerRegister, indJumpEntry->m_stackOffset));
+                delete indJumpEntry;
+            }
+        }
+        
+        ParenthesesTail* addParenthesesTail(PatternTerm& term)
+        {
+            ParenthesesTail* parenthesesTail = new ParenthesesTail(term);
+            m_parenTails.append(parenthesesTail);
+            m_parenTailsForIteration.append(parenthesesTail);
+            
+            return parenthesesTail;
+        }
+        
+        void emitParenthesesTail(RegexGenerator* generator)
+        {
+            unsigned vectorSize = m_parenTails.size();
+            
+            // Emit in reverse order so parentTail N can fall through to N-1
+            for (unsigned index = vectorSize; index > 0; --index) {
+                JumpList jumpsToNext;
+                m_parenTails[index-1].get()->generateCode(generator, jumpsToNext, index > 1);
+                if (index > 1)
+                    jumpsToNext.linkTo(generator->label(), generator);
+                else
+                    addJumpsToNextInteration(jumpsToNext);
+            }
+            m_parenTails.clear();
+        }        
+        
+        void addJumpToNextInteration(Jump jump)
+        {
+            m_jumpsToNextInteration.append(jump);
+        }
+        
+        void addJumpsToNextInteration(JumpList jumps)
+        {
+            m_jumpsToNextInteration.append(jumps);
+        }
+        
+        void addDataLabelToNextIteration(DataLabelPtr dataLabel)
+        {
+            m_dataPtrsToNextIteration.append(dataLabel);
+        }
+        
+        void linkToNextIteration(Label label)
+        {
+            m_nextIteration = label;
+            
+            for (unsigned i = 0; i < m_dataPtrsToNextIteration.size(); ++i)
+                m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataPtrsToNextIteration[i], m_nextIteration));
+            
+            m_dataPtrsToNextIteration.clear();
+
+            for (unsigned i = 0; i < m_parenTailsForIteration.size(); ++i)
+                m_parenTailsForIteration[i]->setNextIteration(m_nextIteration);
+            
+            m_parenTailsForIteration.clear();            
+        }
+
+        void linkToNextIteration(RegexGenerator* generator)
+        {
+            m_jumpsToNextInteration.linkTo(m_nextIteration, generator);
+        }        
+        
+        Vector<AlternativeBacktrackRecord> m_backtrackRecords;
+        IndirectJumpHashMap m_indirectJumpMap;
+        Label m_nextIteration;
+        Vector<OwnPtr<ParenthesesTail> > m_parenTails;
+        JumpList m_jumpsToNextInteration;
+        Vector<DataLabelPtr> m_dataPtrsToNextIteration;
+        Vector<ParenthesesTail*> m_parenTailsForIteration;
+    };
+
+    struct BacktrackDestination {
+        typedef enum {
+            NoBacktrack,
+            BacktrackLabel,
+            BacktrackStackOffset,
+            BacktrackJumpList,
+            BacktrackLinked
+        } BacktrackType;
+        
+        BacktrackDestination()
+            : m_backtrackType(NoBacktrack)
+            , m_backtrackToLabel(0)
+            , m_subDataLabelPtr(0)
+            , m_nextBacktrack(0)
+            , m_backtrackSourceLabel(0)
+            , m_backtrackSourceJumps(0)
+        {
+        }
+        
+        BacktrackDestination(int32_t stackOffset) 
+            : m_backtrackType(BacktrackStackOffset)
+            , m_backtrackStackOffset(stackOffset)
+            , m_backtrackToLabel(0)
+            , m_subDataLabelPtr(0)
+            , m_nextBacktrack(0)
+            , m_backtrackSourceLabel(0)
+            , m_backtrackSourceJumps(0)
+        {
+        }
+        
+        BacktrackDestination(Label label) 
+            : m_backtrackType(BacktrackLabel)
+            , m_backtrackLabel(label)
+            , m_backtrackToLabel(0)
+            , m_subDataLabelPtr(0)
+            , m_nextBacktrack(0)
+            , m_backtrackSourceLabel(0)
+            , m_backtrackSourceJumps(0)
+        {
+        }
+        
+        void clear()
+        {
+            m_backtrackType = NoBacktrack;
+            clearDataLabel();
+            m_nextBacktrack = 0;
+        }
+        
+        void clearDataLabel()
+        {
+            m_dataLabelPtr = DataLabelPtr();
+        }
+        
+        bool hasDestination()
+        {
+            return (m_backtrackType != NoBacktrack);
+        }
+        
+        bool isStackOffset()
+        {
+            return (m_backtrackType == BacktrackStackOffset);
+        }
+        
+        bool isLabel()
+        {
+            return (m_backtrackType == BacktrackLabel);
+        }
+        
+        bool isJumpList()
+        {
+            return (m_backtrackType == BacktrackJumpList);
+        }
+        
+        bool hasDataLabel()
+        {
+            return m_dataLabelPtr.isSet();
+        }
+        
+        void copyTarget(BacktrackDestination& rhs, bool copyDataLabel = true)
+        {
+            m_backtrackType = rhs.m_backtrackType;
+            if (m_backtrackType == BacktrackStackOffset)
+                m_backtrackStackOffset = rhs.m_backtrackStackOffset;
+            else if (m_backtrackType == BacktrackLabel)
+                m_backtrackLabel = rhs.m_backtrackLabel;
+            if (copyDataLabel)
+                m_dataLabelPtr = rhs.m_dataLabelPtr;
+            m_backtrackSourceJumps = rhs.m_backtrackSourceJumps;
+            m_backtrackSourceLabel = rhs.m_backtrackSourceLabel;
+        }
+        
+        void copyTo(BacktrackDestination& lhs)
+        {
+            lhs.m_backtrackType = m_backtrackType;
+            if (m_backtrackType == BacktrackStackOffset)
+                lhs.m_backtrackStackOffset = m_backtrackStackOffset;
+            else if (m_backtrackType == BacktrackLabel)
+                lhs.m_backtrackLabel = m_backtrackLabel;
+            lhs.m_backtrackSourceJumps = m_backtrackSourceJumps;
+            lhs.m_backtrackSourceLabel = m_backtrackSourceLabel;
+            lhs.m_dataLabelPtr = m_dataLabelPtr;
+            lhs.m_backTrackJumps = m_backTrackJumps;
+        }
+        
+        void addBacktrackJump(Jump jump)
+        {
+            m_backTrackJumps.append(jump);
+        }
+
+        void setStackOffset(int32_t stackOffset)
+        {
+            m_backtrackType = BacktrackStackOffset;
+            m_backtrackStackOffset = stackOffset;
+        }
+        
+        void setLabel(Label label)
+        {
+            m_backtrackType = BacktrackLabel;
+            m_backtrackLabel = label;
+        }
+        
+        void setNextBacktrackLabel(Label label)
+        {
+            if (m_nextBacktrack)
+                m_nextBacktrack->setLabel(label);
+        }
+        
+        void setBacktrackToLabel(Label* backtrackToLabel)
+        {
+            m_backtrackToLabel = backtrackToLabel;
+        }
+        
+        void setBacktrackJumpList(JumpList* jumpList)
+        {
+            m_backtrackType = BacktrackJumpList;
+            m_backtrackSourceJumps = jumpList;
+        }
+        
+        void setBacktrackSourceLabel(Label* backtrackSourceLabel)
+        {
+            m_backtrackSourceLabel = backtrackSourceLabel;
+        }
+        
+        void setDataLabel(DataLabelPtr dp)
+        {
+            if (m_subDataLabelPtr) {
+                *m_subDataLabelPtr = dp;
+                m_subDataLabelPtr = 0;
+            } else
+                m_dataLabelPtr = dp;
+        }
+        
+        void setSubDataLabelPtr(DataLabelPtr* subDataLabelPtr)
+        {
+            m_subDataLabelPtr = subDataLabelPtr;
+        }
+
+        void linkToNextBacktrack(BacktrackDestination* nextBacktrack)
+        {
+            m_nextBacktrack = nextBacktrack;
+        }
+                                 
+        int32_t getStackOffset()
+        {
+            ASSERT(m_backtrackType == BacktrackStackOffset);
+            return m_backtrackStackOffset;
+        }
+        
+        Label getLabel()
+        {
+            ASSERT(m_backtrackType == BacktrackLabel);
+            return m_backtrackLabel;
+        }
+        
+        JumpList& getBacktrackJumps()
+        {
+            return m_backTrackJumps;
+        }
+        
+        DataLabelPtr& getDataLabel()
+        {
+            return m_dataLabelPtr;
+        }
+        
+        void jumpToBacktrack(MacroAssembler* masm)
+        {
+            if (isJumpList()) {
+                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
+                    masm->jump().linkTo(*m_backtrackSourceLabel, masm);
+                else
+                    m_backtrackSourceJumps->append(masm->jump());
+            } else if (isStackOffset())
+                masm->jump(Address(stackPointerRegister, m_backtrackStackOffset));
+            else if (isLabel())
+                masm->jump().linkTo(m_backtrackLabel, masm);
+            else
+                m_backTrackJumps.append(masm->jump());
+        }
+        
+        void jumpToBacktrack(RegexGenerator* generator, Jump jump)
+        {
+            if (isJumpList()) {
+                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
+                    jump.linkTo(*m_backtrackSourceLabel, generator);
+                else
+                    m_backtrackSourceJumps->append(jump);
+            } else if (isStackOffset())
+                generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jump);
+            else if (isLabel())
+                jump.linkTo(getLabel(), generator);
+            else
+                m_backTrackJumps.append(jump);
+        }
+        
+        void jumpToBacktrack(RegexGenerator* generator, JumpList& jumps)
+        {
+            if (isJumpList()) {
+                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
+                    jumps.linkTo(*m_backtrackSourceLabel, generator);
+                else
+                    m_backtrackSourceJumps->append(jumps);
+            } else if (isStackOffset())
+                generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jumps);
+            else if (isLabel())
+                jumps.linkTo(getLabel(), generator);
+            else
+                m_backTrackJumps.append(jumps);
+        }
+
+        bool linkDataLabelToHereIfExists(RegexGenerator* generator)
+        {
+            if (hasDataLabel()) {
+                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), generator->label()));
+                clearDataLabel();
+                return true;
+            }
+            
+            return false;
+        }        
+                
+        bool plantJumpToBacktrackIfExists(RegexGenerator* generator)
+        {
+            if (isJumpList()) {
+                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
+                    generator->jump(*m_backtrackSourceLabel);
+                else
+                    m_backtrackSourceJumps->append(generator->jump());
+
+                return true;
+            }
+
+            if (isStackOffset()) {
+                generator->jump(Address(stackPointerRegister, getStackOffset()));
+                return true;
+            }
+            
+            if (isLabel()) {
+                generator->jump(getLabel());
+                if (hasDataLabel()) {
+                    generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), getLabel()));
+                    clearDataLabel();
+                }                
+                return true;
+            }
+            
+            return false;
+        }
+
+        void linkAlternativeBacktracks(RegexGenerator* generator, bool nextIteration = false)
+        {
+            Label hereLabel = generator->label();
+            
+            if (m_backtrackToLabel) {
+                *m_backtrackToLabel = hereLabel;
+                m_backtrackToLabel = 0;
+            }
+            
+            m_backTrackJumps.link(generator);
+            
+            if (nextIteration)
+                generator->m_expressionState.linkToNextIteration(hereLabel);
+            
+            if (hasDataLabel()) {
+                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), hereLabel));
+                // data label cleared as a result of the clear() below
+            }
+            
+            clear();
+        }
+        
+        void linkAlternativeBacktracksTo(RegexGenerator* generator, Label label, bool nextIteration = false)
+        {
+            m_backTrackJumps.linkTo(label, generator);
+            
+            if (nextIteration)
+                generator->m_expressionState.linkToNextIteration(label);
+            
+            if (hasDataLabel()) {
+                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), label));
+                clearDataLabel();
+            }
+        }
+        
+    private:
+        BacktrackType m_backtrackType;
+        int32_t m_backtrackStackOffset;
+        Label m_backtrackLabel;
+        DataLabelPtr m_dataLabelPtr;
+        Label* m_backtrackToLabel;
+        DataLabelPtr* m_subDataLabelPtr;
+        BacktrackDestination* m_nextBacktrack;
+        Label* m_backtrackSourceLabel;
+        JumpList* m_backtrackSourceJumps;
+        JumpList m_backTrackJumps;
+    };
+        
     struct TermGenerationState {
         TermGenerationState(PatternDisjunction* disjunction, unsigned checkedTotal)
             : disjunction(disjunction)
             , checkedTotal(checkedTotal)
+            , m_linkedBacktrack(0)
         {
         }
 
         void resetAlternative()
         {
-            isBackTrackGenerated = false;
+            m_backtrack.clear();
             alt = 0;
         }
         bool alternativeValid()
@@ -322,7 +773,11 @@ class RegexGenerator : private MacroAssembler {
         {
             return disjunction->m_alternatives[alt];
         }
-
+        bool isLastAlternative()
+        {
+            return (alt + 1) == disjunction->m_alternatives.size();
+        }
+        
         void resetTerm()
         {
             ASSERT(alternativeValid());
@@ -373,52 +828,106 @@ class RegexGenerator : private MacroAssembler {
             return term().inputPosition - checkedTotal;
         }
 
-        void jumpToBacktrack(Jump jump, MacroAssembler* masm)
+        void clearBacktrack()
         {
-            if (isBackTrackGenerated)
-                jump.linkTo(backtrackLabel, masm);
-            else
-                backTrackJumps.append(jump);
+            m_backtrack.clear();
+            m_linkedBacktrack = 0;
         }
-        void jumpToBacktrack(JumpList& jumps, MacroAssembler* masm)
+        
+        void jumpToBacktrack(MacroAssembler* masm)
         {
-            if (isBackTrackGenerated)
-                jumps.linkTo(backtrackLabel, masm);
-            else
-                backTrackJumps.append(jumps);
+            m_backtrack.jumpToBacktrack(masm);
         }
-        bool plantJumpToBacktrackIfExists(MacroAssembler* masm)
+        
+        void jumpToBacktrack(RegexGenerator* generator, Jump jump)
+        {
+            m_backtrack.jumpToBacktrack(generator, jump);
+        }
+
+        void jumpToBacktrack(RegexGenerator* generator, JumpList& jumps)
+        {
+            m_backtrack.jumpToBacktrack(generator, jumps);
+        }
+        
+        bool plantJumpToBacktrackIfExists(RegexGenerator* generator)
+        {
+            return m_backtrack.plantJumpToBacktrackIfExists(generator);
+        }
+        
+        bool linkDataLabelToBacktrackIfExists(RegexGenerator* generator)
         {
-            if (isBackTrackGenerated) {
-                masm->jump(backtrackLabel);
+            if ((m_backtrack.isLabel()) && (m_backtrack.hasDataLabel())) {
+                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_backtrack.getDataLabel(), m_backtrack.getLabel()));
+                m_backtrack.clearDataLabel();
                 return true;
             }
+            
             return false;
-        }
+        }        
+
         void addBacktrackJump(Jump jump)
         {
-            backTrackJumps.append(jump);
+            m_backtrack.addBacktrackJump(jump);
+        }
+
+        void setBacktrackDataLabel(DataLabelPtr dp)
+        {
+            m_backtrack.setDataLabel(dp);
+        }
+
+        void setBackTrackStackOffset(int32_t stackOffset)
+        {
+            m_backtrack.setStackOffset(stackOffset);
+        }
+        
+        void setBacktrackLabel(Label label)
+        {
+            m_backtrack.setLabel(label);
+        }
+
+        void linkAlternativeBacktracks(RegexGenerator* generator, bool nextIteration = false)
+        {
+            m_backtrack.linkAlternativeBacktracks(generator, nextIteration);
+            m_linkedBacktrack = 0;
+        }
+
+        void linkAlternativeBacktracksTo(RegexGenerator* generator, Label label, bool nextIteration = false)
+        {
+            m_backtrack.linkAlternativeBacktracksTo(generator, label, nextIteration);
+        }
+
+        void setBacktrackLink(BacktrackDestination* linkedBacktrack)
+        {
+            m_linkedBacktrack = linkedBacktrack;
         }
-        void setBacktrackGenerated(Label label)
+        
+        void chainBacktracks(BacktrackDestination* followonBacktrack)
         {
-            isBackTrackGenerated = true;
-            backtrackLabel = label;
+            if (m_linkedBacktrack)
+                m_linkedBacktrack->linkToNextBacktrack(followonBacktrack);
         }
-        void linkAlternativeBacktracks(MacroAssembler* masm)
+        
+        void chainBacktrackJumps(JumpList* jumpList)
         {
-            isBackTrackGenerated = false;
-            backTrackJumps.link(masm);
+            if (m_linkedBacktrack && !(m_linkedBacktrack->hasDestination()))
+                m_linkedBacktrack->setBacktrackJumpList(jumpList);
         }
-        void linkAlternativeBacktracksTo(Label label, MacroAssembler* masm)
+        
+        BacktrackDestination& getBacktrackDestination()
         {
-            isBackTrackGenerated = false;
-            backTrackJumps.linkTo(label, masm);
+            return m_backtrack;
         }
-        void propagateBacktrackingFrom(TermGenerationState& nestedParenthesesState, MacroAssembler* masm)
+
+        void propagateBacktrackingFrom(RegexGenerator* generator, BacktrackDestination& backtrack, bool doJump = true)
         {
-            jumpToBacktrack(nestedParenthesesState.backTrackJumps, masm);
-            if (nestedParenthesesState.isBackTrackGenerated)
-                setBacktrackGenerated(nestedParenthesesState.backtrackLabel);
+            if (doJump)
+                m_backtrack.jumpToBacktrack(generator, backtrack.getBacktrackJumps());
+            if (backtrack.hasDestination()) {
+                if (m_backtrack.hasDataLabel())
+                    generator->m_expressionState.addDataLabelToNextIteration(m_backtrack.getDataLabel());
+                
+                m_backtrack.copyTarget(backtrack, doJump);
+            }
         }
 
         PatternDisjunction* disjunction;
@@ -426,11 +935,120 @@ class RegexGenerator : private MacroAssembler {
     private:
         unsigned alt;
         unsigned t;
-        JumpList backTrackJumps;
-        Label backtrackLabel;
-        bool isBackTrackGenerated;
+        BacktrackDestination m_backtrack;
+        BacktrackDestination* m_linkedBacktrack;
+        
     };
 
+    struct ParenthesesTail {
+        ParenthesesTail(PatternTerm& term)
+            : m_term(term)
+        {
+        }
+        
+        void processBacktracks(RegexGenerator* generator, TermGenerationState& state, TermGenerationState& parenthesesState, Label nonGreedyTryParentheses, Label fallThrough)
+        {
+            m_nonGreedyTryParentheses = nonGreedyTryParentheses;
+            m_fallThrough = fallThrough;
+
+            parenthesesState.getBacktrackDestination().copyTo(m_parenBacktrack);
+            state.chainBacktracks(&m_backtrack);
+            BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
+            stateBacktrack.copyTo(m_backtrack);
+            stateBacktrack.setBacktrackToLabel(&m_backtrackToLabel);
+            state.setBacktrackLink(&m_backtrack);
+            stateBacktrack.setSubDataLabelPtr(&m_dataAfterLabelPtr);
+            
+            m_doDirectBacktrack = m_parenBacktrack.hasDestination();
+            
+            if ((m_term.quantityType == QuantifierGreedy) || (m_term.quantityType == QuantifierNonGreedy))
+                m_doDirectBacktrack = false;
+
+            if (m_doDirectBacktrack)
+                state.propagateBacktrackingFrom(generator, m_parenBacktrack, false);
+            else {
+                stateBacktrack.setBacktrackJumpList(&m_pattBacktrackJumps);
+                stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens);
+            }
+            
+            parenthesesState.chainBacktrackJumps(&m_pattBacktrackJumps);
+        }
+
+        void setNextIteration(Label nextIteration)
+        {
+            if (!m_backtrackToLabel.isSet())
+                m_backtrackToLabel = nextIteration;
+        }
+
+        void addAfterParenJump(Jump jump)
+        {
+            m_pattBacktrackJumps.append(jump);
+        }
+        
+        void generateCode(RegexGenerator* generator, JumpList& jumpsToNext, bool nextBacktrackFallThrough)
+        {
+            const RegisterID indexTemporary = regT0;
+            unsigned parenthesesFrameLocation = m_term.frameLocation;
+            
+            if (!m_backtrack.hasDestination()) {
+                if (m_backtrackToLabel.isSet()) {
+                    m_backtrack.setLabel(m_backtrackToLabel);
+                    nextBacktrackFallThrough = false;
+                } else
+                    m_backtrack.setBacktrackJumpList(&jumpsToNext);
+            } else
+                nextBacktrackFallThrough = false;
+            
+            // A failure AFTER the parens jumps here - Backtrack to this paren
+            m_backtrackFromAfterParens = generator->label();
+            
+            if (m_dataAfterLabelPtr.isSet())
+                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataAfterLabelPtr, m_backtrackFromAfterParens));
+
+            m_pattBacktrackJumps.link(generator);
+            
+            if (m_term.quantityType == QuantifierGreedy) {
+                // If this is -1 we have now tested with both with and without the parens.
+                generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
+                m_backtrack.jumpToBacktrack(generator, generator->branch32(Equal, indexTemporary, Imm32(-1)));
+            } else if (m_term.quantityType == QuantifierNonGreedy) {
+                // If this is -1 we have now tested with both with and without the parens.
+                generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
+                generator->branch32(Equal, indexTemporary, Imm32(-1)).linkTo(m_nonGreedyTryParentheses, generator);
+            }
+            
+            if (!m_doDirectBacktrack)
+                m_parenBacktrack.plantJumpToBacktrackIfExists(generator);
+            
+            // A failure WITHIN the parens jumps here
+            m_parenBacktrack.linkAlternativeBacktracks(generator);
+            
+            if (m_term.capture())
+                generator->store32(Imm32(-1), Address(output, (m_term.parentheses.subpatternId << 1) * sizeof(int)));
+            
+            if (m_term.quantityType == QuantifierGreedy) {
+                generator->storeToFrame(Imm32(-1), parenthesesFrameLocation);
+                generator->jump().linkTo(m_fallThrough, generator);
+            } else if (!nextBacktrackFallThrough)
+                m_backtrack.jumpToBacktrack(generator);
+
+            if (!m_doDirectBacktrack)
+                m_backtrack.setNextBacktrackLabel(m_backtrackFromAfterParens);
+        }
+        
+        PatternTerm& m_term;
+        Label m_nonGreedyTryParentheses;
+        Label m_fallThrough;
+        Label m_backtrackToLabel;
+        Label m_backtrackFromAfterParens;
+        DataLabelPtr m_dataAfterLabelPtr;
+        JumpList m_pattBacktrackJumps;
+        BacktrackDestination m_parenBacktrack;
+        BacktrackDestination m_backtrack;
+        bool m_doDirectBacktrack;
+    };
+    
+    
     void generateAssertionBOL(TermGenerationState& state)
     {
         PatternTerm& term = state.term();
@@ -444,15 +1062,15 @@ class RegexGenerator : private MacroAssembler {
 
             readCharacter(state.inputOffset() - 1, character);
             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
 
             matchDest.link(this);
         } else {
             // Erk, really should poison out these alternatives early. :-/
             if (term.inputPosition)
-                state.jumpToBacktrack(jump(), this);
+                state.jumpToBacktrack(this);
             else
-                state.jumpToBacktrack(branch32(NotEqual, index, Imm32(state.checkedTotal)), this);
+                state.jumpToBacktrack(this, branch32(NotEqual, index, Imm32(state.checkedTotal)));
         }
     }
 
@@ -469,15 +1087,15 @@ class RegexGenerator : private MacroAssembler {
 
             readCharacter(state.inputOffset(), character);
             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
 
             matchDest.link(this);
         } else {
             if (term.inputPosition == state.checkedTotal)
-                state.jumpToBacktrack(notAtEndOfInput(), this);
+                state.jumpToBacktrack(this, notAtEndOfInput());
             // Erk, really should poison out these alternatives early. :-/
             else
-                state.jumpToBacktrack(jump(), this);
+                state.jumpToBacktrack(this);
         }
     }
 
@@ -511,20 +1129,20 @@ class RegexGenerator : private MacroAssembler {
         // We fall through to here if the last character was not a wordchar.
         JumpList nonWordCharThenWordChar;
         JumpList nonWordCharThenNonWordChar;
-        if (term.invertOrCapture) {
+        if (term.invert()) {
             matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
             nonWordCharThenWordChar.append(jump());
         } else {
             matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
             nonWordCharThenNonWordChar.append(jump());
         }
-        state.jumpToBacktrack(nonWordCharThenNonWordChar, this);
+        state.jumpToBacktrack(this, nonWordCharThenNonWordChar);
 
         // We jump here if the last character was a wordchar.
         matchDest.link(this);
         JumpList wordCharThenWordChar;
         JumpList wordCharThenNonWordChar;
-        if (term.invertOrCapture) {
+        if (term.invert()) {
             matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
             wordCharThenWordChar.append(jump());
         } else {
@@ -532,7 +1150,7 @@ class RegexGenerator : private MacroAssembler {
             // This can fall-though!
         }
 
-        state.jumpToBacktrack(wordCharThenWordChar, this);
+        state.jumpToBacktrack(this, wordCharThenWordChar);
         
         nonWordCharThenWordChar.link(this);
         wordCharThenNonWordChar.link(this);
@@ -546,10 +1164,10 @@ class RegexGenerator : private MacroAssembler {
         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
             readCharacter(state.inputOffset(), character);
             or32(Imm32(32), character);
-            state.jumpToBacktrack(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))), this);
+            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
         } else {
             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
-            state.jumpToBacktrack(jumpIfCharNotEquals(ch, state.inputOffset()), this);
+            state.jumpToBacktrack(this, jumpIfCharNotEquals(ch, state.inputOffset()));
         }
     }
 
@@ -572,9 +1190,9 @@ class RegexGenerator : private MacroAssembler {
         if (mask) {
             load32WithUnalignedHalfWords(BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), character);
             or32(Imm32(mask), character);
-            state.jumpToBacktrack(branch32(NotEqual, character, Imm32(chPair | mask)), this);
+            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(chPair | mask)));
         } else
-            state.jumpToBacktrack(branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)), this);
+            state.jumpToBacktrack(this, branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)));
     }
 
     void generatePatternCharacterFixed(TermGenerationState& state)
@@ -591,10 +1209,10 @@ class RegexGenerator : private MacroAssembler {
         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
             load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
             or32(Imm32(32), character);
-            state.jumpToBacktrack(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))), this);
+            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
         } else {
             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
-            state.jumpToBacktrack(branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)), this);
+            state.jumpToBacktrack(this, branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)));
         }
         add32(Imm32(1), countRegister);
         branch32(NotEqual, countRegister, index).linkTo(loop, this);
@@ -631,7 +1249,7 @@ class RegexGenerator : private MacroAssembler {
 
         Label backtrackBegin(this);
         loadFromFrame(term.frameLocation, countRegister);
-        state.jumpToBacktrack(branchTest32(Zero, countRegister), this);
+        state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
         sub32(Imm32(1), countRegister);
         sub32(Imm32(1), index);
 
@@ -639,7 +1257,7 @@ class RegexGenerator : private MacroAssembler {
 
         storeToFrame(countRegister, term.frameLocation);
 
-        state.setBacktrackGenerated(backtrackBegin);
+        state.setBacktrackLabel(backtrackBegin);
     }
 
     void generatePatternCharacterNonGreedy(TermGenerationState& state)
@@ -655,7 +1273,7 @@ class RegexGenerator : private MacroAssembler {
 
         Label hardFail(this);
         sub32(countRegister, index);
-        state.jumpToBacktrack(jump(), this);
+        state.jumpToBacktrack(this);
 
         Label backtrackBegin(this);
         loadFromFrame(term.frameLocation, countRegister);
@@ -678,7 +1296,7 @@ class RegexGenerator : private MacroAssembler {
         firstTimeDoNothing.link(this);
         storeToFrame(countRegister, term.frameLocation);
 
-        state.setBacktrackGenerated(backtrackBegin);
+        state.setBacktrackLabel(backtrackBegin);
     }
 
     void generateCharacterClassSingle(TermGenerationState& state)
@@ -690,10 +1308,10 @@ class RegexGenerator : private MacroAssembler {
         readCharacter(state.inputOffset(), character);
         matchCharacterClass(character, matchDest, term.characterClass);
 
-        if (term.invertOrCapture)
-            state.jumpToBacktrack(matchDest, this);
+        if (term.invert())
+            state.jumpToBacktrack(this, matchDest);
         else {
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
             matchDest.link(this);
         }
     }
@@ -712,10 +1330,10 @@ class RegexGenerator : private MacroAssembler {
         load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
         matchCharacterClass(character, matchDest, term.characterClass);
 
-        if (term.invertOrCapture)
-            state.jumpToBacktrack(matchDest, this);
+        if (term.invert())
+            state.jumpToBacktrack(this, matchDest);
         else {
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
             matchDest.link(this);
         }
 
@@ -735,7 +1353,7 @@ class RegexGenerator : private MacroAssembler {
         Label loop(this);
         failures.append(atEndOfInput());
 
-        if (term.invertOrCapture) {
+        if (term.invert()) {
             readCharacter(state.inputOffset(), character);
             matchCharacterClass(character, failures, term.characterClass);
         } else {
@@ -756,7 +1374,7 @@ class RegexGenerator : private MacroAssembler {
 
         Label backtrackBegin(this);
         loadFromFrame(term.frameLocation, countRegister);
-        state.jumpToBacktrack(branchTest32(Zero, countRegister), this);
+        state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
         sub32(Imm32(1), countRegister);
         sub32(Imm32(1), index);
 
@@ -764,7 +1382,7 @@ class RegexGenerator : private MacroAssembler {
 
         storeToFrame(countRegister, term.frameLocation);
 
-        state.setBacktrackGenerated(backtrackBegin);
+        state.setBacktrackLabel(backtrackBegin);
     }
 
     void generateCharacterClassNonGreedy(TermGenerationState& state)
@@ -779,7 +1397,7 @@ class RegexGenerator : private MacroAssembler {
 
         Label hardFail(this);
         sub32(countRegister, index);
-        state.jumpToBacktrack(jump(), this);
+        state.jumpToBacktrack(this);
 
         Label backtrackBegin(this);
         loadFromFrame(term.frameLocation, countRegister);
@@ -791,7 +1409,7 @@ class RegexGenerator : private MacroAssembler {
         readCharacter(state.inputOffset(), character);
         matchCharacterClass(character, matchDest, term.characterClass);
 
-        if (term.invertOrCapture)
+        if (term.invert())
             matchDest.linkTo(hardFail, this);
         else {
             jump(hardFail);
@@ -804,7 +1422,7 @@ class RegexGenerator : private MacroAssembler {
         firstTimeDoNothing.link(this);
         storeToFrame(countRegister, term.frameLocation);
 
-        state.setBacktrackGenerated(backtrackBegin);
+        state.setBacktrackLabel(backtrackBegin);
     }
 
     void generateParenthesesDisjunction(PatternTerm& parenthesesTerm, TermGenerationState& state, unsigned alternativeFrameLocation)
@@ -836,9 +1454,9 @@ class RegexGenerator : private MacroAssembler {
                 
                 skip.link(this);
 
-                state.setBacktrackGenerated(backtrackBegin);
+                state.setBacktrackLabel(backtrackBegin);
 
-                state.jumpToBacktrack(jumpIfNoAvailableInput(countToCheck), this);
+                state.jumpToBacktrack(this, jumpIfNoAvailableInput(countToCheck));
                 state.checkedTotal += countToCheck;
             }
 
@@ -848,6 +1466,7 @@ class RegexGenerator : private MacroAssembler {
             state.checkedTotal -= countToCheck;
         } else {
             JumpList successes;
+            bool propogateBacktrack = false;
 
             for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative()) {
 
@@ -866,37 +1485,35 @@ class RegexGenerator : private MacroAssembler {
 
                 // Matched an alternative.
                 DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation);
-                successes.append(jump());
+                
+                if (!state.isLastAlternative() || countToCheck)
+                    successes.append(jump());
 
                 // Alternative did not match.
-                Label backtrackLocation(this);
-                
-                // Can we backtrack the alternative? - if so, do so.  If not, just fall through to the next one.
-                state.plantJumpToBacktrackIfExists(this);
+
+                state.setBacktrackDataLabel(dataLabel);
                 
-                state.linkAlternativeBacktracks(this);
+                // Do we have a backtrack destination? 
+                //    if so, link the data label to it.
+                state.linkDataLabelToBacktrackIfExists(this);
+
+                if (!state.isLastAlternative() || countToCheck)
+                    state.linkAlternativeBacktracks(this);
 
                 if (countToCheck) {
                     sub32(Imm32(countToCheck), index);
                     state.checkedTotal -= countToCheck;
-                }
-
-                m_backtrackRecords.append(AlternativeBacktrackRecord(dataLabel, backtrackLocation));
+                } else if (state.isLastAlternative())
+                    propogateBacktrack = true;
             }
             // We fall through to here when the last alternative fails.
             // Add a backtrack out of here for the parenthese handling code to link up.
-            state.addBacktrackJump(jump());
+            if (!propogateBacktrack)
+                state.addBacktrackJump(jump());
 
-            // Generate a trampoline for the parens code to backtrack to, to retry the
+            // Save address on stack for the parens code to backtrack to, to retry the
             // next alternative.
-            state.setBacktrackGenerated(label());
-            loadFromFrameAndJump(alternativeFrameLocation);
-
-            // FIXME: both of the above hooks are a little inefficient, in that you
-            // may end up trampolining here, just to trampoline back out to the
-            // parentheses code, or vice versa.  We can probably eliminate a jump
-            // by restructuring, but coding this way for now for simplicity during
-            // development.
+            state.setBackTrackStackOffset(alternativeFrameLocation * sizeof(void*));
 
             successes.link(this);
         }
@@ -917,13 +1534,13 @@ class RegexGenerator : private MacroAssembler {
             alternativeFrameLocation += RegexStackSpaceForBackTrackInfoParenthesesOnce;
 
         // optimized case - no capture & no quantifier can be handled in a light-weight manner.
-        if (!term.invertOrCapture && (term.quantityType == QuantifierFixedCount)) {
+        if (!term.capture() && (term.quantityType == QuantifierFixedCount)) {
             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
             // this expects that any backtracks back out of the parentheses will be in the
-            // parenthesesState's backTrackJumps vector, and that if they need backtracking
-            // they will have set an entry point on the parenthesesState's backtrackLabel.
-            state.propagateBacktrackingFrom(parenthesesState, this);
+            // parenthesesState's m_backTrackJumps vector, and that if they need backtracking
+            // they will have set an entry point on the parenthesesState's m_backtrackLabel.
+            state.propagateBacktrackingFrom(this, parenthesesState.getBacktrackDestination());
         } else {
             Jump nonGreedySkipParentheses;
             Label nonGreedyTryParentheses;
@@ -937,7 +1554,7 @@ class RegexGenerator : private MacroAssembler {
             }
 
             // store the match start index
-            if (term.invertOrCapture) {
+            if (term.capture()) {
                 int inputOffset = state.inputOffset() - preCheckedCount;
                 if (inputOffset) {
                     move(index, indexTemporary);
@@ -947,45 +1564,18 @@ class RegexGenerator : private MacroAssembler {
                     store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
             }
 
+            ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term);
+            
             // generate the body of the parentheses
             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
 
-            Jump success = (term.quantityType == QuantifierFixedCount) ?
-                jump() :
-                branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*))));
-
-            // A failure AFTER the parens jumps here
-            Label backtrackFromAfterParens(this);
-
-            if (term.quantityType == QuantifierGreedy) {
-                // If this is -1 we have now tested with both with and without the parens.
-                loadFromFrame(parenthesesFrameLocation, indexTemporary);
-                state.jumpToBacktrack(branch32(Equal, indexTemporary, Imm32(-1)), this);
-            } else if (term.quantityType == QuantifierNonGreedy) {
-                // If this is -1 we have now tested without the parens, now test with.
-                loadFromFrame(parenthesesFrameLocation, indexTemporary);
-                branch32(Equal, indexTemporary, Imm32(-1)).linkTo(nonGreedyTryParentheses, this);
-            }
-
-            parenthesesState.plantJumpToBacktrackIfExists(this);
-            // A failure WITHIN the parens jumps here
-            parenthesesState.linkAlternativeBacktracks(this);
-            if (term.invertOrCapture)
-                store32(Imm32(-1), Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
-
-            if (term.quantityType == QuantifierGreedy)
-                storeToFrame(Imm32(-1), parenthesesFrameLocation);
-            else
-                state.jumpToBacktrack(jump(), this);
-
-            state.setBacktrackGenerated(backtrackFromAfterParens);
-            if (term.quantityType == QuantifierNonGreedy)
-                nonGreedySkipParentheses.link(this);
-            success.link(this);
-
+            // For non-fixed counts, backtrack if we didn't match anything.
+            if (term.quantityType != QuantifierFixedCount)
+                parenthesesTail->addAfterParenJump(branch32(Equal, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*)))));
+            
             // store the match end index
-            if (term.invertOrCapture) {
+            if (term.capture()) {
                 int inputOffset = state.inputOffset();
                 if (inputOffset) {
                     move(index, indexTemporary);
@@ -994,6 +1584,13 @@ class RegexGenerator : private MacroAssembler {
                 } else
                     store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
             }
+            
+            parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label());
+
+            parenthesesState.getBacktrackDestination().clear();
+            
+            if (term.quantityType == QuantifierNonGreedy)
+                nonGreedySkipParentheses.link(this);
         }
     }
 
@@ -1032,6 +1629,7 @@ class RegexGenerator : private MacroAssembler {
             parenthesesState.plantJumpToBacktrackIfExists(this);
 
             parenthesesState.linkAlternativeBacktracks(this);
+
             // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop.
 
             if (countToCheck) {
@@ -1056,7 +1654,7 @@ class RegexGenerator : private MacroAssembler {
 
         int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;
 
-        if (term.invertOrCapture) {
+        if (term.invert()) {
             // Inverted case
             storeToFrame(index, parenthesesFrameLocation);
 
@@ -1068,10 +1666,11 @@ class RegexGenerator : private MacroAssembler {
             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
             // Success! - which means - Fail!
             loadFromFrame(parenthesesFrameLocation, index);
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
 
             // And fail means success.
             parenthesesState.linkAlternativeBacktracks(this);
+
             loadFromFrame(parenthesesFrameLocation, index);
 
             state.checkedTotal += countCheckedAfterAssertion;
@@ -1090,8 +1689,9 @@ class RegexGenerator : private MacroAssembler {
             Jump success = jump();
 
             parenthesesState.linkAlternativeBacktracks(this);
+
             loadFromFrame(parenthesesFrameLocation, index);
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
 
             success.link(this);
 
@@ -1241,6 +1841,8 @@ class RegexGenerator : private MacroAssembler {
             generateReturn();
 
             state.nextAlternative();
+            if (alternative->onceThrough() && state.alternativeValid())
+                state.clearBacktrack();
 
             // if there are any more alternatives, plant the check for input before looping.
             if (state.alternativeValid()) {
@@ -1248,7 +1850,7 @@ class RegexGenerator : private MacroAssembler {
                 if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
                     // We have handled non-repeating alternatives, jump to next iteration 
                     // and loop over repeating alternatives.
-                    state.jumpToBacktrack(jump(), this);
+                    state.jumpToBacktrack(this);
                     
                     countToCheckForFirstAlternative = nextAlternative->m_minimumSize;
                     
@@ -1287,6 +1889,7 @@ class RegexGenerator : private MacroAssembler {
                         
                         // If we get here, then the last input checked passed.
                         state.linkAlternativeBacktracks(this);
+
                         // No need to check if we can run the next alternative, since it is shorter -
                         // just update index.
                         sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
@@ -1301,6 +1904,7 @@ class RegexGenerator : private MacroAssembler {
                         
                         // The next alternative is longer than the current one; check the difference.
                         state.linkAlternativeBacktracks(this);
+
                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
                     } else { // CASE 3: Both alternatives are the same length.
                         ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative);
@@ -1324,7 +1928,8 @@ class RegexGenerator : private MacroAssembler {
         if (!setRepeatAlternativeLabels) {
             // If there are no alternatives that need repeating (all are marked 'onceThrough') then just link
             // the match failures to this point, and fall through to the return below.
-            state.linkAlternativeBacktracks(this);
+            state.linkAlternativeBacktracks(this, true);
+
             notEnoughInputForPreviousAlternative.link(this);
         } else {
             // How much more input need there be to be able to retry from the first alternative?
@@ -1344,11 +1949,11 @@ class RegexGenerator : private MacroAssembler {
 
             // First, deal with the cases where there was sufficient input to try the last alternative.
             if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below.
-                state.linkAlternativeBacktracks(this);
+                state.linkAlternativeBacktracks(this, true);
             else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop!
-                state.linkAlternativeBacktracksTo(firstAlternativeInputChecked, this);
+                state.linkAlternativeBacktracksTo(this, firstAlternativeInputChecked, true);
             else { // no need to check the input, but we do have some bookkeeping to do first.
-                state.linkAlternativeBacktracks(this);
+                state.linkAlternativeBacktracks(this, true);
 
                 // Where necessary update our preserved start position.
                 if (!m_pattern.m_body->m_hasFixedSize) {
@@ -1405,6 +2010,10 @@ class RegexGenerator : private MacroAssembler {
         move(Imm32(-1), returnRegister);
 
         generateReturn();
+
+        m_expressionState.emitParenthesesTail(this);
+        m_expressionState.emitIndirectJumpTable(this);
+        m_expressionState.linkToNextIteration(this);
     }
 
     void generateEnter()
@@ -1491,8 +2100,8 @@ public:
 
         LinkBuffer patchBuffer(this, globalData->executableAllocator.poolForSize(size()), 0);
 
-        for (unsigned i = 0; i < m_backtrackRecords.size(); ++i)
-            patchBuffer.patch(m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_backtrackRecords[i].backtrackLocation));
+        for (unsigned i = 0; i < m_expressionState.m_backtrackRecords.size(); ++i)
+            patchBuffer.patch(m_expressionState.m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_expressionState.m_backtrackRecords[i].backtrackLocation));
 
         jitObject.set(patchBuffer.finalizeCode());
         jitObject.setFallBack(m_shouldFallBack);
@@ -1501,7 +2110,7 @@ public:
 private:
     RegexPattern& m_pattern;
     bool m_shouldFallBack;
-    Vector<AlternativeBacktrackRecord> m_backtrackRecords;
+    GenerationState m_expressionState;
 };
 
 void jitCompileRegex(RegexPattern& pattern, JSGlobalData* globalData, RegexCodeBlock& jitObject)
@@ -1514,8 +2123,3 @@ void jitCompileRegex(RegexPattern& pattern, JSGlobalData* globalData, RegexCodeB
 }}
 
 #endif
-
-
-
-
-
index 8a7d35b..44560a4 100644 (file)
@@ -103,7 +103,8 @@ struct PatternTerm {
         TypeParenthesesSubpattern,
         TypeParentheticalAssertion,
     } type;
-    bool invertOrCapture;
+    bool m_capture :1;
+    bool m_invert :1;
     union {
         UChar patternCharacter;
         CharacterClass* characterClass;
@@ -123,6 +124,8 @@ struct PatternTerm {
 
     PatternTerm(UChar ch)
         : type(PatternTerm::TypePatternCharacter)
+        , m_capture(false)
+        , m_invert(false)
     {
         patternCharacter = ch;
         quantityType = QuantifierFixedCount;
@@ -131,16 +134,18 @@ struct PatternTerm {
 
     PatternTerm(CharacterClass* charClass, bool invert)
         : type(PatternTerm::TypeCharacterClass)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         characterClass = charClass;
         quantityType = QuantifierFixedCount;
         quantityCount = 1;
     }
 
-    PatternTerm(Type type, unsigned subpatternId, PatternDisjunction* disjunction, bool invertOrCapture)
+    PatternTerm(Type type, unsigned subpatternId, PatternDisjunction* disjunction, bool capture = false, bool invert = false)
         : type(type)
-        , invertOrCapture(invertOrCapture)
+        , m_capture(capture)
+        , m_invert(invert)
     {
         parentheses.disjunction = disjunction;
         parentheses.subpatternId = subpatternId;
@@ -152,7 +157,8 @@ struct PatternTerm {
     
     PatternTerm(Type type, bool invert = false)
         : type(type)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         quantityType = QuantifierFixedCount;
         quantityCount = 1;
@@ -160,7 +166,8 @@ struct PatternTerm {
 
     PatternTerm(unsigned spatternId)
         : type(TypeBackReference)
-        , invertOrCapture(false)
+        , m_capture(false)
+        , m_invert(false)
     {
         backReferenceSubpatternId = spatternId;
         quantityType = QuantifierFixedCount;
@@ -189,12 +196,12 @@ struct PatternTerm {
     
     bool invert()
     {
-        return invertOrCapture;
+        return m_invert;
     }
 
     bool capture()
     {
-        return invertOrCapture;
+        return m_capture;
     }
     
     void quantify(unsigned count, QuantifierType type)
index 2feb36a..bce3752 100644 (file)
@@ -1,3 +1,16 @@
+2010-12-03  Michael Saboff  <msaboff@apple.com>
+
+        Reviewed by Gavin Barraclough
+
+        Added new tests to support changes to Regexp JIT code handling
+        of parentheses.  Tests focused on backtracking and nested 
+        subexpressions.
+        https://bugs.webkit.org/show_bug.cgi?id=50295
+
+        * fast/regex/parentheses-expected.txt: Added.
+        * fast/regex/parentheses.html: Added.
+        * fast/regex/script-tests/parentheses.js: Added.
+
 2010-12-03  Chris Guillory  <chris.guillory@google.com>
 
         Reviewed by Chris Fleizach.
diff --git a/LayoutTests/fast/regex/parentheses-expected.txt b/LayoutTests/fast/regex/parentheses-expected.txt
new file mode 100644 (file)
index 0000000..8bd7eda
--- /dev/null
@@ -0,0 +1,37 @@
+This page tests handling of parentheses subexpressions.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS regexp1.exec('abc') is ['ab','a','b']
+PASS regexp2.exec('abacadabe') is ['abe','ab','b','b']
+PASS regexp3.exec('abacadabe') is ['abe','ab','b',undefined]
+PASS regexp4.exec('abacadabe') is ['abe','ab','b',undefined]
+PASS regexp5.exec('abacadabe') is ['abe','ab','b','b',undefined,undefined]
+PASS regexp6.exec('abcde') is ['ab','ab','b','b',undefined,undefined]
+PASS regexp7.exec('abc') is ['abc','ab','b']
+PASS regexp8.exec('bcaddxqy') is ['qy','q','q','y']
+PASS regexp9.exec('asdfjejgsdflaksdfjkeljghkjea') is ['a','a',undefined]
+PASS regexp10.exec('asdfjejgsdflaksdfjkeljghat') is ['at']
+PASS regexp11.exec('Developing with JavaScript is dangerous, do not try it without assistance') is null
+PASS regexp12.exec('Seattle, WA to Buckley, WA') is ['Seattle, WA to Buckley, WA', undefined, 'Seattle', 'WA', undefined, 'Buckley', 'WA']
+PASS regexp13.exec('zxcasd;fl ^AaaAAaaaf;lrlrzs') is ['AaaAAaaaf;lrlrzs',undefined,'AaaAAaaaf;lrlrzs']
+PASS regexp14.exec('b') is ['b',undefined,'b']
+PASS regexp15.exec('abdf') is ['abdf',undefined,'abd','f']
+PASS regexp16.exec('abc') is ['ab','a','b']
+PASS regexp17.exec('bcaDxqy') is ['Dx','D']
+PASS regexp18.exec('Hello: World') is ['Hello:',':']
+PASS regexp19.exec('barrel') is ['bar','']
+PASS regexp20.exec('barrel') is ['barrel','rel']
+PASS regexp20.exec('2barrel') is ['2barrel','rel']
+PASS regexp21.exec('abc') is ['ab','ab','b']
+PASS regexp22.exec('abcdlskfgjdslkfg') is null
+PASS regexp23.exec('<html xmlns="http://www.w3.org/1999/xhtml"') is ['"http://www.w3.org/1999/xhtml"']
+PASS regexp24.exec('123') is null
+PASS regexp25.exec('this is a test') is ['this','this',undefined]
+PASS regexp25.exec('!this is a test') is null
+PASS 'Hi Bob'.match(/(Rob)|(Bob)|(Robert)|(Bobby)/) is ['Bob',undefined,'Bob',undefined,undefined]
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/regex/parentheses.html b/LayoutTests/fast/regex/parentheses.html
new file mode 100644 (file)
index 0000000..06da76a
--- /dev/null
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="../js/resources/js-test-style.css">
+<script src="../js/resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="script-tests/parentheses.js"></script>
+<script src="../js/resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/regex/script-tests/parentheses.js b/LayoutTests/fast/regex/script-tests/parentheses.js
new file mode 100644 (file)
index 0000000..715b4d1
--- /dev/null
@@ -0,0 +1,83 @@
+description("This page tests handling of parentheses subexpressions.");
+
+var regexp1 = /(a|A)(b|B)/;
+shouldBe("regexp1.exec('abc')", "['ab','a','b']");
+
+var regexp2 = /(a((b)|c|d))e/;
+shouldBe("regexp2.exec('abacadabe')", "['abe','ab','b','b']");
+
+var regexp3 = /(a(b|(c)|d))e/;
+shouldBe("regexp3.exec('abacadabe')", "['abe','ab','b',undefined]");
+
+var regexp4 = /(a(b|c|(d)))e/;
+shouldBe("regexp4.exec('abacadabe')", "['abe','ab','b',undefined]");
+
+var regexp5 = /(a((b)|(c)|(d)))e/;
+shouldBe("regexp5.exec('abacadabe')", "['abe','ab','b','b',undefined,undefined]");
+
+var regexp6 = /(a((b)|(c)|(d)))/;
+shouldBe("regexp6.exec('abcde')", "['ab','ab','b','b',undefined,undefined]");
+
+var regexp7 = /(a(b)??)??c/;
+shouldBe("regexp7.exec('abc')", "['abc','ab','b']");
+
+var regexp8 = /(a|(e|q))(x|y)/;
+shouldBe("regexp8.exec('bcaddxqy')" , "['qy','q','q','y']");
+
+var regexp9 = /((t|b)?|a)$/;
+shouldBe("regexp9.exec('asdfjejgsdflaksdfjkeljghkjea')", "['a','a',undefined]");
+
+var regexp10 = /(?:h|e?(?:t|b)?|a?(?:t|b)?)(?:$)/;
+shouldBe("regexp10.exec('asdfjejgsdflaksdfjkeljghat')", "['at']");
+
+var regexp11 = /([Jj]ava([Ss]cript)?)\sis\s(fun\w*)/;
+shouldBeNull("regexp11.exec('Developing with JavaScript is dangerous, do not try it without assistance')");
+
+var regexp12 = /(?:(.+), )?(.+), (..) to (?:(.+), )?(.+), (..)/;
+shouldBe("regexp12.exec('Seattle, WA to Buckley, WA')", "['Seattle, WA to Buckley, WA', undefined, 'Seattle', 'WA', undefined, 'Buckley', 'WA']");
+
+var regexp13 = /(A)?(A.*)/;
+shouldBe("regexp13.exec('zxcasd;fl\ ^AaaAAaaaf;lrlrzs')", "['AaaAAaaaf;lrlrzs',undefined,'AaaAAaaaf;lrlrzs']");
+
+var regexp14 = /(a)|(b)/;
+shouldBe("regexp14.exec('b')", "['b',undefined,'b']");
+
+var regexp15 = /^(?!(ab)de|x)(abd)(f)/;
+shouldBe("regexp15.exec('abdf')", "['abdf',undefined,'abd','f']");
+
+var regexp16 = /(a|A)(b|B)/;
+shouldBe("regexp16.exec('abc')", "['ab','a','b']");
+
+var regexp17 = /(a|d|q|)x/i;
+shouldBe("regexp17.exec('bcaDxqy')", "['Dx','D']");
+
+var regexp18 = /^.*?(:|$)/;
+shouldBe("regexp18.exec('Hello: World')", "['Hello:',':']");
+
+var regexp19 = /(ab|^.{0,2})bar/;
+shouldBe("regexp19.exec('barrel')", "['bar','']");
+
+var regexp20 = /(?:(?!foo)...|^.{0,2})bar(.*)/;
+shouldBe("regexp20.exec('barrel')", "['barrel','rel']");
+shouldBe("regexp20.exec('2barrel')", "['2barrel','rel']");
+
+var regexp21 = /([a-g](b|B)|xyz)/;
+shouldBe("regexp21.exec('abc')", "['ab','ab','b']");
+
+var regexp22 = /(?:^|;)\s*abc=([^;]*)/;
+shouldBeNull("regexp22.exec('abcdlskfgjdslkfg')");
+
+var regexp23 = /"[^<"]*"|'[^<']*'/;
+shouldBe("regexp23.exec('<html xmlns=\"http://www.w3.org/1999/xhtml\"')", "['\"http://www.w3.org/1999/xhtml\"']");
+
+var regexp24 = /^(?:(?=abc)\w{3}:|\d\d)$/;
+shouldBeNull("regexp24.exec('123')");
+
+var regexp25 = /^\s*(\*|[\w\-]+)(\b|$)?/;
+shouldBe("regexp25.exec('this is a test')", "['this','this',undefined]");
+shouldBeNull("regexp25.exec('!this is a test')");
+
+shouldBe("'Hi Bob'.match(/(Rob)|(Bob)|(Robert)|(Bobby)/)", "['Bob',undefined,'Bob',undefined,undefined]");
+
+var successfullyParsed = true;
+