Changeset 73307 in webkit

Timestamp:

Dec 3, 2010 2:48:19 PM (13 years ago)

Author:

msaboff@apple.com

Message:

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 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.

Location:

trunk

Files:

• JavaScriptCore/ChangeLog (modified) (1 diff)
• JavaScriptCore/assembler/ARMAssembler.h (modified) (1 diff)
• JavaScriptCore/assembler/ARMv7Assembler.h (modified) (1 diff)
• JavaScriptCore/assembler/AbstractMacroAssembler.h (modified) (3 diffs)
• JavaScriptCore/assembler/MIPSAssembler.h (modified) (1 diff)
• JavaScriptCore/assembler/X86Assembler.h (modified) (1 diff)
• JavaScriptCore/yarr/RegexCompiler.cpp (modified) (4 diffs)
• JavaScriptCore/yarr/RegexInterpreter.cpp (modified) (13 diffs)
• JavaScriptCore/yarr/RegexInterpreter.h (modified) (9 diffs)
• JavaScriptCore/yarr/RegexJIT.cpp (modified) (49 diffs)
• JavaScriptCore/yarr/RegexPattern.h (modified) (7 diffs)
• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/regex/parentheses-expected.txt (added)
• LayoutTests/fast/regex/parentheses.html (added)
• LayoutTests/fast/regex/script-tests/parentheses.js (added)

trunk/JavaScriptCore/ChangeLog

@@ +1 @@
+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>
 

trunk/JavaScriptCore/assembler/ARMAssembler.h

@@ -241 +241 @@
 
             bool isUsed() const { return m_used; }
+            bool isSet() const { return (m_offset != -1); }
             void used() { m_used = true; }
         private:

trunk/JavaScriptCore/assembler/ARMv7Assembler.h

@@ -554 +554 @@
 
         bool isUsed() const { return m_used; }
+        bool isSet() const { return (m_offset != -1); }
         void used() { m_used = true; }
     private:

trunk/JavaScriptCore/assembler/AbstractMacroAssembler.h

@@ -242 +242 @@
         
         bool isUsed() const { return m_label.isUsed(); }
+        bool isSet() const { return m_label.isSet(); }
         void used() { m_label.used(); }
     private:
@@ -264 +265 @@
         {
         }
+        
+        bool isSet() const { return m_label.isSet(); }
         
     private:
@@ -411 +414 @@
         }
         
+        void clear()
+        {
+            m_jumps.clear();
+        }
+        
         const JumpVector& jumps() { return m_jumps; }
 

trunk/JavaScriptCore/assembler/MIPSAssembler.h

@@ -194 +194 @@
 
         bool isUsed() const { return m_used; }
+        bool isSet() const { return (m_offset != -1); }
         void used() { m_used = true; }
     private:

trunk/JavaScriptCore/assembler/X86Assembler.h

@@ -249 +249 @@
 
         bool isUsed() const { return m_used; }
+        bool isSet() const { return (m_offset != -1); }
         void used() { m_used = true; }
     private:

trunk/JavaScriptCore/yarr/RegexCompiler.cpp

@@ -460 +460 @@
         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();
     }
@@ -468 +468 @@
         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;
@@ -521 +521 @@
             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;
@@ -846 +846 @@
 
             case PatternTerm::TypeParentheticalAssertion:
-                if (term.invertOrCapture)
+                if (term.invert())
                     return false;
 

trunk/JavaScriptCore/yarr/RegexInterpreter.cpp

@@ -1523 +1523 @@
         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());
@@ -1536 +1536 @@
         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());
@@ -1553 +1553 @@
         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());
@@ -1566 +1566 @@
         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());
@@ -1583 +1583 @@
         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;
@@ -1678 +1678 @@
         ByteTerm& parenthesesBegin = m_bodyDisjunction->terms[beginTerm];
 
-        bool invertOrCapture = parenthesesBegin.invertOrCapture;
+        bool capture = parenthesesBegin.capture();
         unsigned subpatternId = parenthesesBegin.atom.subpatternId;
 
@@ -1692 +1692 @@
 
         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;
@@ -1707 +1707 @@
         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;
@@ -1729 +1729 @@
         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;
@@ -1815 +1815 @@
 
                 case PatternTerm::TypeAssertionWordBoundary:
-                    assertionWordBoundary(term.invertOrCapture, term.inputPosition - currentCountAlreadyChecked);
+                    assertionWordBoundary(term.invert(), term.inputPosition - currentCountAlreadyChecked);
                     break;
 
@@ -1823 +1823 @@
 
                 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;
 
@@ -1843 +1843 @@
                             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);
@@ -1866 +1866 @@
                     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);

trunk/JavaScriptCore/yarr/RegexInterpreter.h

@@ -88 +88 @@
         TypeCheckInput,
     } type;
-    bool invertOrCapture;
     union {
         struct {
@@ -115 +114 @@
     };
     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) {
@@ -140 +143 @@
     ByteTerm(UChar lo, UChar hi, int inputPos, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
         : frameLocation(frameLocation)
+        , m_capture(false)
+        , m_invert(false)
     {
         switch (quantityType) {
@@ -162 +167 @@
     ByteTerm(CharacterClass* characterClass, bool invert, int inputPos)
         : type(ByteTerm::TypeCharacterClass)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         atom.characterClass = characterClass;
@@ -170 +176 @@
     }
 
-    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;
@@ -183 +190 @@
     ByteTerm(Type type, bool invert = false)
         : type(type)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         atom.quantityType = QuantifierFixedCount;
@@ -189 +197 @@
     }
 
-    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;
@@ -229 +238 @@
     static ByteTerm BackReference(unsigned subpatternId, int inputPos)
     {
-        return ByteTerm(TypeBackReference, subpatternId, false, inputPos);
+        return ByteTerm(TypeBackReference, subpatternId, false, false, inputPos);
     }
 
@@ -298 +307 @@
     bool invert()
     {
-        return invertOrCapture;
+        return m_invert;
     }
 
     bool capture()
     {
-        return invertOrCapture;
+        return m_capture;
     }
 };

trunk/JavaScriptCore/yarr/RegexJIT.cpp

@@ -288 +288 @@
     }
 
+    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;
@@ -299 +320 @@
     };
 
+    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)
         {
         }
@@ -308 +759 @@
         void resetAlternative()
         {
-            isBackTrackGenerated = false;
+            m_backtrack.clear();
             alt = 0;
         }
@@ -323 +774 @@
             return disjunction->m_alternatives[alt];
         }
-
+        bool isLastAlternative()
+        {
+            return (alt + 1) == disjunction->m_alternatives.size();
+        }
+        
         void resetTerm()
         {
@@ -374 +829 @@
         }
 
-        void jumpToBacktrack(Jump jump, MacroAssembler* masm)
-        {
-            if (isBackTrackGenerated)
-                jump.linkTo(backtrackLabel, masm);
-            else
-                backTrackJumps.append(jump);
-        }
-        void jumpToBacktrack(JumpList& jumps, MacroAssembler* masm)
-        {
-            if (isBackTrackGenerated)
-                jumps.linkTo(backtrackLabel, masm);
-            else
-                backTrackJumps.append(jumps);
-        }
-        bool plantJumpToBacktrackIfExists(MacroAssembler* masm)
-        {
-            if (isBackTrackGenerated) {
-                masm->jump(backtrackLabel);
+        void clearBacktrack()
+        {
+            m_backtrack.clear();
+            m_linkedBacktrack = 0;
+        }
+        
+        void jumpToBacktrack(MacroAssembler* masm)
+        {
+            m_backtrack.jumpToBacktrack(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 ((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);
-        }
-        void setBacktrackGenerated(Label label)
-        {
-            isBackTrackGenerated = true;
-            backtrackLabel = label;
-        }
-        void linkAlternativeBacktracks(MacroAssembler* masm)
-        {
-            isBackTrackGenerated = false;
-            backTrackJumps.link(masm);
-        }
-        void linkAlternativeBacktracksTo(Label label, MacroAssembler* masm)
-        {
-            isBackTrackGenerated = false;
-            backTrackJumps.linkTo(label, masm);
-        }
-        void propagateBacktrackingFrom(TermGenerationState& nestedParenthesesState, MacroAssembler* masm)
-        {
-            jumpToBacktrack(nestedParenthesesState.backTrackJumps, masm);
-            if (nestedParenthesesState.isBackTrackGenerated)
-                setBacktrackGenerated(nestedParenthesesState.backtrackLabel);
+            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 chainBacktracks(BacktrackDestination* followonBacktrack)
+        {
+            if (m_linkedBacktrack)
+                m_linkedBacktrack->linkToNextBacktrack(followonBacktrack);
+        }
+        
+        void chainBacktrackJumps(JumpList* jumpList)
+        {
+            if (m_linkedBacktrack && !(m_linkedBacktrack->hasDestination()))
+                m_linkedBacktrack->setBacktrackJumpList(jumpList);
+        }
+        
+        BacktrackDestination& getBacktrackDestination()
+        {
+            return m_backtrack;
+        }
+
+        void propagateBacktrackingFrom(RegexGenerator* generator, BacktrackDestination& backtrack, bool doJump = true)
+        {
+            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);
+            }
         }
 
@@ -427 +936 @@
         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)
     {
@@ -445 +1063 @@
             readCharacter(state.inputOffset() - 1, character);
             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
 
             matchDest.link(this);
@@ -451 +1069 @@
             // 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)));
         }
     }
@@ -470 +1088 @@
             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);
         }
     }
@@ -512 +1130 @@
         JumpList nonWordCharThenWordChar;
         JumpList nonWordCharThenNonWordChar;
-        if (term.invertOrCapture) {
+        if (term.invert()) {
             matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
             nonWordCharThenWordChar.append(jump());
@@ -519 +1137 @@
             nonWordCharThenNonWordChar.append(jump());
         }
-        state.jumpToBacktrack(nonWordCharThenNonWordChar, this);
+        state.jumpToBacktrack(this, nonWordCharThenNonWordChar);
 
         // We jump here if the last character was a wordchar.
@@ -525 +1143 @@
         JumpList wordCharThenWordChar;
         JumpList wordCharThenNonWordChar;
-        if (term.invertOrCapture) {
+        if (term.invert()) {
             matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
             wordCharThenWordChar.append(jump());
@@ -533 +1151 @@
         }
 
-        state.jumpToBacktrack(wordCharThenWordChar, this);
+        state.jumpToBacktrack(this, wordCharThenWordChar);
         
         nonWordCharThenWordChar.link(this);
@@ -547 +1165 @@
             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()));
         }
     }
@@ -573 +1191 @@
             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)));
     }
 
@@ -592 +1210 @@
             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);
@@ -632 +1250 @@
         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);
@@ -640 +1258 @@
         storeToFrame(countRegister, term.frameLocation);
 
-        state.setBacktrackGenerated(backtrackBegin);
+        state.setBacktrackLabel(backtrackBegin);
     }
 
@@ -656 +1274 @@
         Label hardFail(this);
         sub32(countRegister, index);
-        state.jumpToBacktrack(jump(), this);
+        state.jumpToBacktrack(this);
 
         Label backtrackBegin(this);
@@ -679 +1297 @@
         storeToFrame(countRegister, term.frameLocation);
 
-        state.setBacktrackGenerated(backtrackBegin);
+        state.setBacktrackLabel(backtrackBegin);
     }
 
@@ -691 +1309 @@
         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);
         }
@@ -713 +1331 @@
         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);
         }
@@ -736 +1354 @@
         failures.append(atEndOfInput());
 
-        if (term.invertOrCapture) {
+        if (term.invert()) {
             readCharacter(state.inputOffset(), character);
             matchCharacterClass(character, failures, term.characterClass);
@@ -757 +1375 @@
         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);
@@ -765 +1383 @@
         storeToFrame(countRegister, term.frameLocation);
 
-        state.setBacktrackGenerated(backtrackBegin);
+        state.setBacktrackLabel(backtrackBegin);
     }
 
@@ -780 +1398 @@
         Label hardFail(this);
         sub32(countRegister, index);
-        state.jumpToBacktrack(jump(), this);
+        state.jumpToBacktrack(this);
 
         Label backtrackBegin(this);
@@ -792 +1410 @@
         matchCharacterClass(character, matchDest, term.characterClass);
 
-        if (term.invertOrCapture)
+        if (term.invert())
             matchDest.linkTo(hardFail, this);
         else {
@@ -805 +1423 @@
         storeToFrame(countRegister, term.frameLocation);
 
-        state.setBacktrackGenerated(backtrackBegin);
+        state.setBacktrackLabel(backtrackBegin);
     }
 
@@ -837 +1455 @@
                 skip.link(this);
 
-                state.setBacktrackGenerated(backtrackBegin);
-
-                state.jumpToBacktrack(jumpIfNoAvailableInput(countToCheck), this);
+                state.setBacktrackLabel(backtrackBegin);
+
+                state.jumpToBacktrack(this, jumpIfNoAvailableInput(countToCheck));
                 state.checkedTotal += countToCheck;
             }
@@ -849 +1467 @@
         } else {
             JumpList successes;
+            bool propogateBacktrack = false;
 
             for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative()) {
@@ -867 +1486 @@
                 // Matched an alternative.
                 DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation);
-                successes.append(jump());
+                
+                if (!state.isLastAlternative() || countToCheck)
+                    successes.append(jump());
 
                 // Alternative did not match.
-                Label backtrackLocation(this);
+
+                state.setBacktrackDataLabel(dataLabel);
                 
-                // Can we backtrack the alternative? - if so, do so.  If not, just fall through to the next one.
-                state.plantJumpToBacktrackIfExists(this);
-                
-                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());
-
-            // Generate a trampoline for the parens code to backtrack to, to retry the
+            if (!propogateBacktrack)
+                state.addBacktrackJump(jump());
+
+            // 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);
@@ -918 +1535 @@
 
         // 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;
@@ -938 +1555 @@
 
             // store the match start index
-            if (term.invertOrCapture) {
+            if (term.capture()) {
                 int inputOffset = state.inputOffset() - preCheckedCount;
                 if (inputOffset) {
@@ -948 +1565 @@
             }
 
+            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) {
@@ -995 +1585 @@
                     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);
         }
     }
@@ -1033 +1630 @@
 
             parenthesesState.linkAlternativeBacktracks(this);
+
             // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop.
 
@@ -1057 +1655 @@
         int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;
 
-        if (term.invertOrCapture) {
+        if (term.invert()) {
             // Inverted case
             storeToFrame(index, parenthesesFrameLocation);
@@ -1069 +1667 @@
             // Success! - which means - Fail!
             loadFromFrame(parenthesesFrameLocation, index);
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
 
             // And fail means success.
             parenthesesState.linkAlternativeBacktracks(this);
+
             loadFromFrame(parenthesesFrameLocation, index);
 
@@ -1091 +1690 @@
 
             parenthesesState.linkAlternativeBacktracks(this);
+
             loadFromFrame(parenthesesFrameLocation, index);
-            state.jumpToBacktrack(jump(), this);
+            state.jumpToBacktrack(this);
 
             success.link(this);
@@ -1242 +1842 @@
 
             state.nextAlternative();
+            if (alternative->onceThrough() && state.alternativeValid())
+                state.clearBacktrack();
 
             // if there are any more alternatives, plant the check for input before looping.
@@ -1249 +1851 @@
                     // 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;
@@ -1288 +1890 @@
                         // 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.
@@ -1302 +1905 @@
                         // 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.
@@ -1325 +1929 @@
             // 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 {
@@ -1345 +1950 @@
             // 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.
@@ -1406 +2011 @@
 
         generateReturn();
+
+        m_expressionState.emitParenthesesTail(this);
+        m_expressionState.emitIndirectJumpTable(this);
+        m_expressionState.linkToNextIteration(this);
     }
 
@@ -1492 +2101 @@
         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());
@@ -1502 +2111 @@
     RegexPattern& m_pattern;
     bool m_shouldFallBack;
-    Vector<AlternativeBacktrackRecord> m_backtrackRecords;
+    GenerationState m_expressionState;
 };
 
@@ -1515 +2124 @@
 
 #endif
-
-
-
-
-

trunk/JavaScriptCore/yarr/RegexPattern.h

@@ -104 +104 @@
         TypeParentheticalAssertion,
     } type;
-    bool invertOrCapture;
+    bool m_capture :1;
+    bool m_invert :1;
     union {
         UChar patternCharacter;
@@ -124 +125 @@
     PatternTerm(UChar ch)
         : type(PatternTerm::TypePatternCharacter)
+        , m_capture(false)
+        , m_invert(false)
     {
         patternCharacter = ch;
@@ -132 +135 @@
     PatternTerm(CharacterClass* charClass, bool invert)
         : type(PatternTerm::TypeCharacterClass)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         characterClass = charClass;
@@ -139 +143 @@
     }
 
-    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;
@@ -153 +158 @@
     PatternTerm(Type type, bool invert = false)
         : type(type)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         quantityType = QuantifierFixedCount;
@@ -161 +167 @@
     PatternTerm(unsigned spatternId)
         : type(TypeBackReference)
-        , invertOrCapture(false)
+        , m_capture(false)
+        , m_invert(false)
     {
         backReferenceSubpatternId = spatternId;
@@ -190 +197 @@
     bool invert()
     {
-        return invertOrCapture;
+        return m_invert;
     }
 
     bool capture()
     {
-        return invertOrCapture;
+        return m_capture;
     }
     

trunk/LayoutTests/ChangeLog

@@ +1 @@
+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>