xref: /external/webkit/Source/JavaScriptCore/yarr/YarrJIT.cpp

/*
 * Copyright (C) 2009 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "YarrJIT.h"

#include "ASCIICType.h"
#include "LinkBuffer.h"
#include "Yarr.h"

#if ENABLE(YARR_JIT)

using namespace WTF;

namespace JSC { namespace Yarr {

class YarrGenerator : private MacroAssembler {
    friend void jitCompile(JSGlobalData*, YarrCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);

#if CPU(ARM)
    static const RegisterID input = ARMRegisters::r0;
    static const RegisterID index = ARMRegisters::r1;
    static const RegisterID length = ARMRegisters::r2;
    static const RegisterID output = ARMRegisters::r4;

    static const RegisterID regT0 = ARMRegisters::r5;
    static const RegisterID regT1 = ARMRegisters::r6;

    static const RegisterID returnRegister = ARMRegisters::r0;
#elif CPU(MIPS)
    static const RegisterID input = MIPSRegisters::a0;
    static const RegisterID index = MIPSRegisters::a1;
    static const RegisterID length = MIPSRegisters::a2;
    static const RegisterID output = MIPSRegisters::a3;

    static const RegisterID regT0 = MIPSRegisters::t4;
    static const RegisterID regT1 = MIPSRegisters::t5;

    static const RegisterID returnRegister = MIPSRegisters::v0;
#elif CPU(SH4)
    static const RegisterID input = SH4Registers::r4;
    static const RegisterID index = SH4Registers::r5;
    static const RegisterID length = SH4Registers::r6;
    static const RegisterID output = SH4Registers::r7;

    static const RegisterID regT0 = SH4Registers::r0;
    static const RegisterID regT1 = SH4Registers::r1;

    static const RegisterID returnRegister = SH4Registers::r0;
#elif CPU(X86)
    static const RegisterID input = X86Registers::eax;
    static const RegisterID index = X86Registers::edx;
    static const RegisterID length = X86Registers::ecx;
    static const RegisterID output = X86Registers::edi;

    static const RegisterID regT0 = X86Registers::ebx;
    static const RegisterID regT1 = X86Registers::esi;

    static const RegisterID returnRegister = X86Registers::eax;
#elif CPU(X86_64)
    static const RegisterID input = X86Registers::edi;
    static const RegisterID index = X86Registers::esi;
    static const RegisterID length = X86Registers::edx;
    static const RegisterID output = X86Registers::ecx;

    static const RegisterID regT0 = X86Registers::eax;
    static const RegisterID regT1 = X86Registers::ebx;

    static const RegisterID returnRegister = X86Registers::eax;
#endif

    void optimizeAlternative(PatternAlternative* alternative)
    {
        if (!alternative->m_terms.size())
            return;

        for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {
            PatternTerm& term = alternative->m_terms[i];
            PatternTerm& nextTerm = alternative->m_terms[i + 1];

            if ((term.type == PatternTerm::TypeCharacterClass)
                && (term.quantityType == QuantifierFixedCount)
                && (nextTerm.type == PatternTerm::TypePatternCharacter)
                && (nextTerm.quantityType == QuantifierFixedCount)) {
                PatternTerm termCopy = term;
                alternative->m_terms[i] = nextTerm;
                alternative->m_terms[i + 1] = termCopy;
            }
        }
    }

    void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
    {
        do {
            // pick which range we're going to generate
            int which = count >> 1;
            char lo = ranges[which].begin;
            char hi = ranges[which].end;

            // check if there are any ranges or matches below lo.  If not, just jl to failure -
            // if there is anything else to check, check that first, if it falls through jmp to failure.
            if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
                Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));

                // generate code for all ranges before this one
                if (which)
                    matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);

                while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
                    matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
                    ++*matchIndex;
                }
                failures.append(jump());

                loOrAbove.link(this);
            } else if (which) {
                Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));

                matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
                failures.append(jump());

                loOrAbove.link(this);
            } else
                failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));

            while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
                ++*matchIndex;

            matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
            // fall through to here, the value is above hi.

            // shuffle along & loop around if there are any more matches to handle.
            unsigned next = which + 1;
            ranges += next;
            count -= next;
        } while (count);
    }

    void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
    {
        if (charClass->m_table) {
            ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table));
            matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry));
            return;
        }
        Jump unicodeFail;
        if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
            Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f));

            if (charClass->m_matchesUnicode.size()) {
                for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {
                    UChar ch = charClass->m_matchesUnicode[i];
                    matchDest.append(branch32(Equal, character, Imm32(ch)));
                }
            }

            if (charClass->m_rangesUnicode.size()) {
                for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {
                    UChar lo = charClass->m_rangesUnicode[i].begin;
                    UChar hi = charClass->m_rangesUnicode[i].end;

                    Jump below = branch32(LessThan, character, Imm32(lo));
                    matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
                    below.link(this);
                }
            }

            unicodeFail = jump();
            isAscii.link(this);
        }

        if (charClass->m_ranges.size()) {
            unsigned matchIndex = 0;
            JumpList failures;
            matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
            while (matchIndex < charClass->m_matches.size())
                matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));

            failures.link(this);
        } else if (charClass->m_matches.size()) {
            // optimization: gather 'a','A' etc back together, can mask & test once.
            Vector<char> matchesAZaz;

            for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {
                char ch = charClass->m_matches[i];
                if (m_pattern.m_ignoreCase) {
                    if (isASCIILower(ch)) {
                        matchesAZaz.append(ch);
                        continue;
                    }
                    if (isASCIIUpper(ch))
                        continue;
                }
                matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
            }

            if (unsigned countAZaz = matchesAZaz.size()) {
                or32(TrustedImm32(32), character);
                for (unsigned i = 0; i < countAZaz; ++i)
                    matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));
            }
        }

        if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())
            unicodeFail.link(this);
    }

    // Jumps if input not available; will have (incorrectly) incremented already!
    Jump jumpIfNoAvailableInput(unsigned countToCheck)
    {
        add32(Imm32(countToCheck), index);
        return branch32(Above, index, length);
    }

    Jump jumpIfAvailableInput(unsigned countToCheck)
    {
        add32(Imm32(countToCheck), index);
        return branch32(BelowOrEqual, index, length);
    }

    Jump checkInput()
    {
        return branch32(BelowOrEqual, index, length);
    }

    Jump atEndOfInput()
    {
        return branch32(Equal, index, length);
    }

    Jump notAtEndOfInput()
    {
        return branch32(NotEqual, index, length);
    }

    Jump jumpIfCharEquals(UChar ch, int inputPosition)
    {
        return branch16(Equal, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
    }

    Jump jumpIfCharNotEquals(UChar ch, int inputPosition)
    {
        return branch16(NotEqual, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
    }

    void readCharacter(int inputPosition, RegisterID reg)
    {
        load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
    }

    void storeToFrame(RegisterID reg, unsigned frameLocation)
    {
        poke(reg, frameLocation);
    }

    void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
    {
        poke(imm, frameLocation);
    }

    DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
    {
        return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
    }

    void loadFromFrame(unsigned frameLocation, RegisterID reg)
    {
        peek(reg, frameLocation);
    }

    void loadFromFrameAndJump(unsigned frameLocation)
    {
        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);
        }

        IndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
        : m_stackOffset(stackOffset)
        {
            addDataLabel(dataLabel);
        }

        void addJump(Jump jump)
        {
            m_relJumps.append(jump);
        }

        void addDataLabel(DataLabelPtr dataLabel)
        {
            m_dataLabelPtrVector.append(dataLabel);
        }

        int32_t m_stackOffset;
        JumpList m_relJumps;
        Vector<DataLabelPtr, 16> m_dataLabelPtrVector;
    };

    struct AlternativeBacktrackRecord {
        DataLabelPtr dataLabel;
        Label backtrackLocation;

        AlternativeBacktrackRecord(DataLabelPtr dataLabel, Label backtrackLocation)
            : dataLabel(dataLabel)
            , backtrackLocation(backtrackLocation)
        {
        }
    };

    struct ParenthesesTail;
    struct TermGenerationState;

    struct GenerationState {
        typedef HashMap<int, IndirectJumpEntry*, WTF::IntHash<uint32_t>, UnsignedWithZeroKeyHashTraits<uint32_t> > IndirectJumpHashMap;

        GenerationState()
            : m_parenNestingLevel(0)
        {
        }

        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 addIndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
        {
            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, dataLabel));
            else
                result->second->addDataLabel(dataLabel);
        }

        void emitIndirectJumpTable(MacroAssembler* masm)
        {
            for (IndirectJumpHashMap::iterator iter = m_indirectJumpMap.begin(); iter != m_indirectJumpMap.end(); ++iter) {
                IndirectJumpEntry* indJumpEntry = iter->second;
                size_t size = indJumpEntry->m_dataLabelPtrVector.size();
                if (size) {
                    // Link any associated DataLabelPtr's with indirect jump via label
                    Label hereLabel = masm->label();
                    for (size_t i = 0; i < size; ++i)
                        m_backtrackRecords.append(AlternativeBacktrackRecord(indJumpEntry->m_dataLabelPtrVector[i], hereLabel));
                }
                indJumpEntry->m_relJumps.link(masm);
                masm->jump(Address(stackPointerRegister, indJumpEntry->m_stackOffset));
                delete indJumpEntry;
            }
        }

        void incrementParenNestingLevel()
        {
            ++m_parenNestingLevel;
        }

        void decrementParenNestingLevel()
        {
            --m_parenNestingLevel;
        }

        ParenthesesTail* addParenthesesTail(PatternTerm& term, JumpList* jumpListToPriorParen)
        {
            ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, jumpListToPriorParen);
            m_parenTails.append(parenthesesTail);
            m_parenTailsForIteration.append(parenthesesTail);

            return parenthesesTail;
        }

        void emitParenthesesTail(YarrGenerator* generator)
        {
            unsigned vectorSize = m_parenTails.size();
            bool priorBacktrackFallThrough = false;

            // Emit in reverse order so parentTail N can fall through to N-1
            for (unsigned index = vectorSize; index > 0; --index) {
                JumpList jumpsToNext;
                priorBacktrackFallThrough = m_parenTails[index-1].get()->generateCode(generator, jumpsToNext, priorBacktrackFallThrough, 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(YarrGenerator* generator)
        {
            m_jumpsToNextInteration.linkTo(m_nextIteration, generator);
        }

        int m_parenNestingLevel;
        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(bool doDataLabelClear = true)
        {
            m_backtrackType = NoBacktrack;
            if (doDataLabelClear)
                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 propagateBacktrackToLabel(const BacktrackDestination& rhs)
        {
            if (!m_backtrackToLabel && rhs.m_backtrackToLabel)
                m_backtrackToLabel = rhs.m_backtrackToLabel;
        }

        void setBacktrackToLabel(Label* backtrackToLabel)
        {
            if (!m_backtrackToLabel)
                m_backtrackToLabel = backtrackToLabel;
        }

        bool hasBacktrackToLabel()
        {
            return m_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 {
                ASSERT(!hasDataLabel());
                m_dataLabelPtr = dp;
            }
        }

        void clearSubDataLabelPtr()
        {
            m_subDataLabelPtr = 0;
        }

        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(YarrGenerator* 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(YarrGenerator* 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 plantJumpToBacktrackIfExists(YarrGenerator* 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 linkBacktrackToLabel(Label backtrackLabel)
        {
            if (m_backtrackToLabel)
                *m_backtrackToLabel = backtrackLabel;
        }

        void linkAlternativeBacktracks(YarrGenerator* 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(YarrGenerator* 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_subParenNum(0)
            , m_linkedBacktrack(0)
            , m_jumpList(0)
        {
        }

        void resetAlternative()
        {
            m_backtrack.clear();
            alt = 0;
        }
        bool alternativeValid()
        {
            return alt < disjunction->m_alternatives.size();
        }
        void nextAlternative()
        {
            ++alt;
        }
        PatternAlternative* alternative()
        {
            return disjunction->m_alternatives[alt];
        }
        bool isLastAlternative()
        {
            return (alt + 1) == disjunction->m_alternatives.size();
        }

        void resetTerm()
        {
            ASSERT(alternativeValid());
            t = 0;
            m_subParenNum = 0;
        }
        bool termValid()
        {
            ASSERT(alternativeValid());
            return t < alternative()->m_terms.size();
        }
        void nextTerm()
        {
            ASSERT(alternativeValid());
            ++t;
        }
        PatternTerm& term()
        {
            ASSERT(alternativeValid());
            return alternative()->m_terms[t];
        }
        bool isLastTerm()
        {
            ASSERT(alternativeValid());
            return (t + 1) == alternative()->m_terms.size();
        }
        unsigned getSubParenNum()
        {
            return m_subParenNum++;
        }
        bool isMainDisjunction()
        {
            return !disjunction->m_parent;
        }

        void setJumpListToPriorParen(JumpList* jumpList)
        {
            m_jumpList = jumpList;
        }

        JumpList* getJumpListToPriorParen()
        {
            return m_jumpList;
        }

        PatternTerm& lookaheadTerm()
        {
            ASSERT(alternativeValid());
            ASSERT((t + 1) < alternative()->m_terms.size());
            return alternative()->m_terms[t + 1];
        }
        bool isSinglePatternCharacterLookaheadTerm()
        {
            ASSERT(alternativeValid());
            return ((t + 1) < alternative()->m_terms.size())
                && (lookaheadTerm().type == PatternTerm::TypePatternCharacter)
                && (lookaheadTerm().quantityType == QuantifierFixedCount)
                && (lookaheadTerm().quantityCount == 1);
        }

        int inputOffset()
        {
            return term().inputPosition - checkedTotal;
        }

        void clearBacktrack()
        {
            m_backtrack.clear(false);
            m_linkedBacktrack = 0;
        }

        void jumpToBacktrack(MacroAssembler* masm)
        {
            m_backtrack.jumpToBacktrack(masm);
        }

        void jumpToBacktrack(YarrGenerator* generator, Jump jump)
        {
            m_backtrack.jumpToBacktrack(generator, jump);
        }

        void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps)
        {
            m_backtrack.jumpToBacktrack(generator, jumps);
        }

        bool plantJumpToBacktrackIfExists(YarrGenerator* generator)
        {
            return m_backtrack.plantJumpToBacktrackIfExists(generator);
        }

        void linkDataLabelToBacktrackIfExists(YarrGenerator* generator, DataLabelPtr dataLabel)
        {
            // If we have a stack offset backtrack destination, use it directly
            if (m_backtrack.isStackOffset()) {
                generator->m_expressionState.addIndirectJumpEntry(m_backtrack.getStackOffset(), dataLabel);
                m_backtrack.clearSubDataLabelPtr();
            } else {
                // If we have a backtrack label, connect the datalabel to it directly.
                if (m_backtrack.isLabel())
                    generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(dataLabel, m_backtrack.getLabel()));
                else
                    setBacktrackDataLabel(dataLabel);
            }
        }

        void addBacktrackJump(Jump 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(YarrGenerator* generator, bool nextIteration = false)
        {
            m_backtrack.linkAlternativeBacktracks(generator, nextIteration);
            m_linkedBacktrack = 0;
        }

        void linkAlternativeBacktracksTo(YarrGenerator* 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);
        }

        BacktrackDestination& getBacktrackDestination()
        {
            return m_backtrack;
        }

        void propagateBacktrackingFrom(YarrGenerator* generator, BacktrackDestination& backtrack, bool doJump = true)
        {
            if (doJump)
                m_backtrack.jumpToBacktrack(generator, backtrack.getBacktrackJumps());

            if (m_backtrack.isLabel() && backtrack.hasBacktrackToLabel())
                backtrack.linkBacktrackToLabel(m_backtrack.getLabel());

            if (backtrack.hasDestination()) {
                if (m_backtrack.hasDataLabel())
                    generator->m_expressionState.addDataLabelToNextIteration(m_backtrack.getDataLabel());

                m_backtrack.copyTarget(backtrack, doJump);
            }
        }

        PatternDisjunction* disjunction;
        int checkedTotal;
    private:
        unsigned alt;
        unsigned t;
        unsigned m_subParenNum;
        BacktrackDestination m_backtrack;
        BacktrackDestination* m_linkedBacktrack;
        JumpList* m_jumpList;
    };

    struct ParenthesesTail {
        ParenthesesTail(PatternTerm& term, int nestingLevel, JumpList* jumpListToPriorParen)
            : m_term(term)
            , m_nestingLevel(nestingLevel)
            , m_subParenIndex(0)
            , m_jumpListToPriorParen(jumpListToPriorParen)
        {
        }

        void processBacktracks(YarrGenerator* generator, TermGenerationState& state, TermGenerationState& parenthesesState, Label nonGreedyTryParentheses, Label fallThrough)
        {
            m_nonGreedyTryParentheses = nonGreedyTryParentheses;
            m_fallThrough = fallThrough;

            m_subParenIndex = state.getSubParenNum();
            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_afterBacktrackJumps);
                stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens);
            }
        }

        void setNextIteration(Label nextIteration)
        {
            if (!m_nestingLevel && !m_backtrackToLabel.isSet())
                m_backtrackToLabel = nextIteration;
        }

        void addAfterParenJump(Jump jump)
        {
            m_afterBacktrackJumps.append(jump);
        }

        bool generateCode(YarrGenerator* generator, JumpList& jumpsToNext, bool priorBackTrackFallThrough, bool nextBacktrackFallThrough)
        {
            const RegisterID indexTemporary = regT0;
            unsigned parenthesesFrameLocation = m_term.frameLocation;
            Jump fromPriorBacktrack;
            bool needJumpForPriorParenTail = false;

            if (priorBackTrackFallThrough
                && ((m_term.quantityType == QuantifierGreedy)
                 || (m_term.quantityType == QuantifierNonGreedy)
                 || (!m_doDirectBacktrack && m_parenBacktrack.hasDestination()))) {
                // If the prior paren tail code assumed that it could fall through,
                // but we need to generate after paren backtrack code, then provide
                // a jump around that code for the prior paren tail code.
                // A regular expressing like ((xxx)...)? needs this.
                fromPriorBacktrack = generator->jump();
                needJumpForPriorParenTail = true;
            }

            if (!m_backtrack.hasDestination()) {
                if (m_backtrackToLabel.isSet()) {
                    m_backtrack.setLabel(m_backtrackToLabel);
                    nextBacktrackFallThrough = false;
                } else if (m_jumpListToPriorParen) {
                    // If we don't have a destination, go back to either the prior paren or the next outer paren.
                    m_backtrack.setBacktrackJumpList(m_jumpListToPriorParen);
                    nextBacktrackFallThrough = false;
                } else
                    m_backtrack.setBacktrackJumpList(&jumpsToNext);
            } 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_afterBacktrackJumps.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, TrustedImm32(-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, TrustedImm32(-1)).linkTo(m_nonGreedyTryParentheses, generator);
            }

            if (!m_doDirectBacktrack)
                m_parenBacktrack.plantJumpToBacktrackIfExists(generator);

            // A failure WITHIN the parens jumps here
            if (needJumpForPriorParenTail)
                fromPriorBacktrack.link(generator);
            m_parenBacktrack.linkAlternativeBacktracks(generator);
            m_withinBacktrackJumps.link(generator);

            if (m_term.capture())
                generator->store32(TrustedImm32(-1), Address(output, (m_term.parentheses.subpatternId << 1) * sizeof(int)));

            if (m_term.quantityType == QuantifierGreedy) {
                generator->storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
                generator->jump().linkTo(m_fallThrough, generator);
                nextBacktrackFallThrough = false;
            } else if (!nextBacktrackFallThrough)
                m_backtrack.jumpToBacktrack(generator);

            if (!m_doDirectBacktrack)
                m_backtrack.setNextBacktrackLabel(m_backtrackFromAfterParens);

            return nextBacktrackFallThrough;
        }

        PatternTerm& m_term;
        int m_nestingLevel;
        unsigned m_subParenIndex;
        JumpList* m_jumpListToPriorParen;
        Label m_nonGreedyTryParentheses;
        Label m_fallThrough;
        Label m_backtrackToLabel;
        Label m_backtrackFromAfterParens;
        DataLabelPtr m_dataAfterLabelPtr;
        JumpList m_withinBacktrackJumps;
        JumpList m_afterBacktrackJumps;
        BacktrackDestination m_parenBacktrack;
        BacktrackDestination m_backtrack;
        bool m_doDirectBacktrack;
    };

    void generateAssertionBOL(TermGenerationState& state)
    {
        PatternTerm& term = state.term();

        if (m_pattern.m_multiline) {
            const RegisterID character = regT0;

            JumpList matchDest;
            if (!term.inputPosition)
                matchDest.append(branch32(Equal, index, Imm32(state.checkedTotal)));

            readCharacter(state.inputOffset() - 1, character);
            matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
            state.jumpToBacktrack(this);

            matchDest.link(this);
        } else {
            // Erk, really should poison out these alternatives early. :-/
            if (term.inputPosition)
                state.jumpToBacktrack(this);
            else
                state.jumpToBacktrack(this, branch32(NotEqual, index, Imm32(state.checkedTotal)));
        }
    }

    void generateAssertionEOL(TermGenerationState& state)
    {
        PatternTerm& term = state.term();

        if (m_pattern.m_multiline) {
            const RegisterID character = regT0;

            JumpList matchDest;
            if (term.inputPosition == state.checkedTotal)
                matchDest.append(atEndOfInput());

            readCharacter(state.inputOffset(), character);
            matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
            state.jumpToBacktrack(this);

            matchDest.link(this);
        } else {
            if (term.inputPosition == state.checkedTotal)
                state.jumpToBacktrack(this, notAtEndOfInput());
            // Erk, really should poison out these alternatives early. :-/
            else
                state.jumpToBacktrack(this);
        }
    }

    // Also falls though on nextIsNotWordChar.
    void matchAssertionWordchar(TermGenerationState& state, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
    {
        const RegisterID character = regT0;
        PatternTerm& term = state.term();

        if (term.inputPosition == state.checkedTotal)
            nextIsNotWordChar.append(atEndOfInput());

        readCharacter(state.inputOffset(), character);
        matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
    }

    void generateAssertionWordBoundary(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        PatternTerm& term = state.term();

        Jump atBegin;
        JumpList matchDest;
        if (!term.inputPosition)
            atBegin = branch32(Equal, index, Imm32(state.checkedTotal));
        readCharacter(state.inputOffset() - 1, character);
        matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
        if (!term.inputPosition)
            atBegin.link(this);

        // We fall through to here if the last character was not a wordchar.
        JumpList nonWordCharThenWordChar;
        JumpList nonWordCharThenNonWordChar;
        if (term.invert()) {
            matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
            nonWordCharThenWordChar.append(jump());
        } else {
            matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
            nonWordCharThenNonWordChar.append(jump());
        }
        state.jumpToBacktrack(this, nonWordCharThenNonWordChar);

        // We jump here if the last character was a wordchar.
        matchDest.link(this);
        JumpList wordCharThenWordChar;
        JumpList wordCharThenNonWordChar;
        if (term.invert()) {
            matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
            wordCharThenWordChar.append(jump());
        } else {
            matchAssertionWordchar(state, wordCharThenWordChar, wordCharThenNonWordChar);
            // This can fall-though!
        }

        state.jumpToBacktrack(this, wordCharThenWordChar);

        nonWordCharThenWordChar.link(this);
        wordCharThenNonWordChar.link(this);
    }

    void generatePatternCharacterSingle(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        UChar ch = state.term().patternCharacter;

        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
            readCharacter(state.inputOffset(), character);
            or32(TrustedImm32(32), character);
            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
        } else {
            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
            state.jumpToBacktrack(this, jumpIfCharNotEquals(ch, state.inputOffset()));
        }
    }

    void generatePatternCharacterPair(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        UChar ch1 = state.term().patternCharacter;
        UChar ch2 = state.lookaheadTerm().patternCharacter;

        int mask = 0;
        int chPair = ch1 | (ch2 << 16);

        if (m_pattern.m_ignoreCase) {
            if (isASCIIAlpha(ch1))
                mask |= 32;
            if (isASCIIAlpha(ch2))
                mask |= 32 << 16;
        }

        if (mask) {
            load32WithUnalignedHalfWords(BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), character);
            or32(Imm32(mask), character);
            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(chPair | mask)));
        } else
            state.jumpToBacktrack(this, branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)));
    }

    void generatePatternCharacterFixed(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        const RegisterID countRegister = regT1;
        PatternTerm& term = state.term();
        UChar ch = term.patternCharacter;

        move(index, countRegister);
        sub32(Imm32(term.quantityCount), countRegister);

        Label loop(this);
        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
            load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
            or32(TrustedImm32(32), character);
            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
        } else {
            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
            state.jumpToBacktrack(this, branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)));
        }
        add32(TrustedImm32(1), countRegister);
        branch32(NotEqual, countRegister, index).linkTo(loop, this);
    }

    void generatePatternCharacterGreedy(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        const RegisterID countRegister = regT1;
        PatternTerm& term = state.term();
        UChar ch = term.patternCharacter;

        move(TrustedImm32(0), countRegister);

        JumpList failures;
        Label loop(this);
        failures.append(atEndOfInput());
        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
            readCharacter(state.inputOffset(), character);
            or32(TrustedImm32(32), character);
            failures.append(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
        } else {
            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
            failures.append(jumpIfCharNotEquals(ch, state.inputOffset()));
        }

        add32(TrustedImm32(1), countRegister);
        add32(TrustedImm32(1), index);
        if (term.quantityCount != quantifyInfinite) {
            branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
            failures.append(jump());
        } else
            jump(loop);

        Label backtrackBegin(this);
        loadFromFrame(term.frameLocation, countRegister);
        state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
        sub32(TrustedImm32(1), countRegister);
        sub32(TrustedImm32(1), index);

        failures.link(this);

        storeToFrame(countRegister, term.frameLocation);

        state.setBacktrackLabel(backtrackBegin);
    }

    void generatePatternCharacterNonGreedy(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        const RegisterID countRegister = regT1;
        PatternTerm& term = state.term();
        UChar ch = term.patternCharacter;

        move(TrustedImm32(0), countRegister);

        Jump firstTimeDoNothing = jump();

        Label hardFail(this);
        sub32(countRegister, index);
        state.jumpToBacktrack(this);

        Label backtrackBegin(this);
        loadFromFrame(term.frameLocation, countRegister);

        atEndOfInput().linkTo(hardFail, this);
        if (term.quantityCount != quantifyInfinite)
            branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
            readCharacter(state.inputOffset(), character);
            or32(TrustedImm32(32), character);
            branch32(NotEqual, character, Imm32(Unicode::toLower(ch))).linkTo(hardFail, this);
        } else {
            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
            jumpIfCharNotEquals(ch, state.inputOffset()).linkTo(hardFail, this);
        }

        add32(TrustedImm32(1), countRegister);
        add32(TrustedImm32(1), index);

        firstTimeDoNothing.link(this);
        storeToFrame(countRegister, term.frameLocation);

        state.setBacktrackLabel(backtrackBegin);
    }

    void generateCharacterClassSingle(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        PatternTerm& term = state.term();

        JumpList matchDest;
        readCharacter(state.inputOffset(), character);
        matchCharacterClass(character, matchDest, term.characterClass);

        if (term.invert())
            state.jumpToBacktrack(this, matchDest);
        else {
            state.jumpToBacktrack(this);
            matchDest.link(this);
        }
    }

    void generateCharacterClassFixed(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        const RegisterID countRegister = regT1;
        PatternTerm& term = state.term();

        move(index, countRegister);
        sub32(Imm32(term.quantityCount), countRegister);

        Label loop(this);
        JumpList matchDest;
        load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
        matchCharacterClass(character, matchDest, term.characterClass);

        if (term.invert())
            state.jumpToBacktrack(this, matchDest);
        else {
            state.jumpToBacktrack(this);
            matchDest.link(this);
        }

        add32(TrustedImm32(1), countRegister);
        branch32(NotEqual, countRegister, index).linkTo(loop, this);
    }

    void generateCharacterClassGreedy(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        const RegisterID countRegister = regT1;
        PatternTerm& term = state.term();

        move(TrustedImm32(0), countRegister);

        JumpList failures;
        Label loop(this);
        failures.append(atEndOfInput());

        if (term.invert()) {
            readCharacter(state.inputOffset(), character);
            matchCharacterClass(character, failures, term.characterClass);
        } else {
            JumpList matchDest;
            readCharacter(state.inputOffset(), character);
            matchCharacterClass(character, matchDest, term.characterClass);
            failures.append(jump());
            matchDest.link(this);
        }

        add32(TrustedImm32(1), countRegister);
        add32(TrustedImm32(1), index);
        if (term.quantityCount != quantifyInfinite) {
            branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
            failures.append(jump());
        } else
            jump(loop);

        Label backtrackBegin(this);
        loadFromFrame(term.frameLocation, countRegister);
        state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
        sub32(TrustedImm32(1), countRegister);
        sub32(TrustedImm32(1), index);

        failures.link(this);

        storeToFrame(countRegister, term.frameLocation);

        state.setBacktrackLabel(backtrackBegin);
    }

    void generateCharacterClassNonGreedy(TermGenerationState& state)
    {
        const RegisterID character = regT0;
        const RegisterID countRegister = regT1;
        PatternTerm& term = state.term();

        move(TrustedImm32(0), countRegister);

        Jump firstTimeDoNothing = jump();

        Label hardFail(this);
        sub32(countRegister, index);
        state.jumpToBacktrack(this);

        Label backtrackBegin(this);
        loadFromFrame(term.frameLocation, countRegister);

        atEndOfInput().linkTo(hardFail, this);
        branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);

        JumpList matchDest;
        readCharacter(state.inputOffset(), character);
        matchCharacterClass(character, matchDest, term.characterClass);

        if (term.invert())
            matchDest.linkTo(hardFail, this);
        else {
            jump(hardFail);
            matchDest.link(this);
        }

        add32(TrustedImm32(1), countRegister);
        add32(TrustedImm32(1), index);

        firstTimeDoNothing.link(this);
        storeToFrame(countRegister, term.frameLocation);

        state.setBacktrackLabel(backtrackBegin);
    }

    void generateParenthesesDisjunction(PatternTerm& parenthesesTerm, TermGenerationState& state, unsigned alternativeFrameLocation)
    {
        ASSERT((parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern) || (parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion));
        ASSERT(parenthesesTerm.quantityCount == 1);

        PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
        unsigned preCheckedCount = ((parenthesesTerm.quantityType == QuantifierFixedCount) && (parenthesesTerm.type != PatternTerm::TypeParentheticalAssertion)) ? disjunction->m_minimumSize : 0;

        if (disjunction->m_alternatives.size() == 1) {
            state.resetAlternative();
            ASSERT(state.alternativeValid());
            PatternAlternative* alternative = state.alternative();
            optimizeAlternative(alternative);

            int countToCheck = alternative->m_minimumSize - preCheckedCount;
            if (countToCheck) {
                ASSERT((parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion) || (parenthesesTerm.quantityType != QuantifierFixedCount));

                // FIXME: This is quite horrible.  The call to 'plantJumpToBacktrackIfExists'
                // will be forced to always trampoline into here, just to decrement the index.
                // Ick.
                Jump skip = jump();

                Label backtrackBegin(this);
                sub32(Imm32(countToCheck), index);
                state.addBacktrackJump(jump());

                skip.link(this);

                state.setBacktrackLabel(backtrackBegin);

                state.jumpToBacktrack(this, jumpIfNoAvailableInput(countToCheck));
                state.checkedTotal += countToCheck;
            }

            for (state.resetTerm(); state.termValid(); state.nextTerm())
                generateTerm(state);

            state.checkedTotal -= countToCheck;
        } else {
            JumpList successes;
            bool propogateBacktrack = false;

            // Save current state's paren jump list for use with each alternative
            JumpList* outerJumpList = state.getJumpListToPriorParen();

            for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative(), state.setJumpListToPriorParen(outerJumpList)) {
                PatternAlternative* alternative = state.alternative();
                optimizeAlternative(alternative);

                ASSERT(alternative->m_minimumSize >= preCheckedCount);
                int countToCheck = alternative->m_minimumSize - preCheckedCount;
                if (countToCheck) {
                    state.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
                    state.checkedTotal += countToCheck;
                }

                for (state.resetTerm(); state.termValid(); state.nextTerm())
                    generateTerm(state);

                // Matched an alternative.
                DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation);

                if (!state.isLastAlternative() || countToCheck)
                    successes.append(jump());

                // Alternative did not match.

                // Do we have a backtrack destination?
                //    if so, link the data label to it.
                state.linkDataLabelToBacktrackIfExists(this, dataLabel);

                if (!state.isLastAlternative() || countToCheck)
                    state.linkAlternativeBacktracks(this);

                if (countToCheck) {
                    sub32(Imm32(countToCheck), index);
                    state.checkedTotal -= countToCheck;
                } 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.
            if (!propogateBacktrack)
                state.addBacktrackJump(jump());

            // Save address on stack for the parens code to backtrack to, to retry the
            // next alternative.
            state.setBackTrackStackOffset(alternativeFrameLocation * sizeof(void*));

            successes.link(this);
        }
    }

    void generateParenthesesSingle(TermGenerationState& state)
    {
        const RegisterID indexTemporary = regT0;
        PatternTerm& term = state.term();
        PatternDisjunction* disjunction = term.parentheses.disjunction;
        ASSERT(term.quantityCount == 1);

        unsigned preCheckedCount = (term.quantityType == QuantifierFixedCount) ? disjunction->m_minimumSize : 0;

        unsigned parenthesesFrameLocation = term.frameLocation;
        unsigned alternativeFrameLocation = parenthesesFrameLocation;
        if (term.quantityType != QuantifierFixedCount)
            alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;

        // optimized case - no capture & no quantifier can be handled in a light-weight manner.
        if (!term.capture() && (term.quantityType == QuantifierFixedCount)) {
            m_expressionState.incrementParenNestingLevel();

            TermGenerationState parenthesesState(disjunction, state.checkedTotal);

            // Use the current state's jump list for the nested parentheses.
            parenthesesState.setJumpListToPriorParen(state.getJumpListToPriorParen());

            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
            // this expects that any backtracks back out of the parentheses will be in the
            // parenthesesState's m_backTrackJumps vector, and that if they need backtracking
            // they will have set an entry point on the parenthesesState's m_backtrackLabel.
            BacktrackDestination& parenthesesBacktrack = parenthesesState.getBacktrackDestination();
            BacktrackDestination& stateBacktrack = state.getBacktrackDestination();

            state.propagateBacktrackingFrom(this, parenthesesBacktrack);
            stateBacktrack.propagateBacktrackToLabel(parenthesesBacktrack);

            state.setJumpListToPriorParen(parenthesesState.getJumpListToPriorParen());

            m_expressionState.decrementParenNestingLevel();
        } else {
            Jump nonGreedySkipParentheses;
            Label nonGreedyTryParentheses;
            if (term.quantityType == QuantifierGreedy)
                storeToFrame(index, parenthesesFrameLocation);
            else if (term.quantityType == QuantifierNonGreedy) {
                storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
                nonGreedySkipParentheses = jump();
                nonGreedyTryParentheses = label();
                storeToFrame(index, parenthesesFrameLocation);
            }

            // store the match start index
            if (term.capture()) {
                int inputOffset = state.inputOffset() - preCheckedCount;
                if (inputOffset) {
                    move(index, indexTemporary);
                    add32(Imm32(inputOffset), indexTemporary);
                    store32(indexTemporary, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
                } else
                    store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
            }

            ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getJumpListToPriorParen());

            m_expressionState.incrementParenNestingLevel();

            TermGenerationState parenthesesState(disjunction, state.checkedTotal);

            // Save the parenthesesTail for backtracking from nested parens to this one.
            parenthesesState.setJumpListToPriorParen(&parenthesesTail->m_withinBacktrackJumps);

            // generate the body of the parentheses
            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);

            // 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.capture()) {
                int inputOffset = state.inputOffset();
                if (inputOffset) {
                    move(index, indexTemporary);
                    add32(Imm32(state.inputOffset()), indexTemporary);
                    store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
                } else
                    store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
            }

            m_expressionState.decrementParenNestingLevel();

            parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label());

            state.setJumpListToPriorParen(&parenthesesTail->m_afterBacktrackJumps);

            parenthesesState.getBacktrackDestination().clear();

            if (term.quantityType == QuantifierNonGreedy)
                nonGreedySkipParentheses.link(this);
        }
    }

    void generateParenthesesGreedyNoBacktrack(TermGenerationState& state)
    {
        PatternTerm& parenthesesTerm = state.term();
        PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
        ASSERT(parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern);
        ASSERT(parenthesesTerm.quantityCount != 1); // Handled by generateParenthesesSingle.

        TermGenerationState parenthesesState(disjunction, state.checkedTotal);

        Label matchAgain(this);

        storeToFrame(index, parenthesesTerm.frameLocation); // Save the current index to check for zero len matches later.

        for (parenthesesState.resetAlternative(); parenthesesState.alternativeValid(); parenthesesState.nextAlternative()) {

            PatternAlternative* alternative = parenthesesState.alternative();
            optimizeAlternative(alternative);

            int countToCheck = alternative->m_minimumSize;
            if (countToCheck) {
                parenthesesState.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
                parenthesesState.checkedTotal += countToCheck;
            }

            for (parenthesesState.resetTerm(); parenthesesState.termValid(); parenthesesState.nextTerm())
                generateTerm(parenthesesState);

            // If we get here, we matched! If the index advanced then try to match more since limit isn't supported yet.
            branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesTerm.frameLocation * sizeof(void*))), matchAgain);

            // If we get here we matched, but we matched "" - cannot accept this alternative as is, so either backtrack,
            // or fall through to try the next alternative if no backtrack is available.
            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) {
                sub32(Imm32(countToCheck), index);
                parenthesesState.checkedTotal -= countToCheck;
            }
        }

        // If the last alternative falls through to here, we have a failed match...
        // Which means that we match whatever we have matched up to this point (even if nothing).
    }

    void generateParentheticalAssertion(TermGenerationState& state)
    {
        PatternTerm& term = state.term();
        PatternDisjunction* disjunction = term.parentheses.disjunction;
        ASSERT(term.quantityCount == 1);
        ASSERT(term.quantityType == QuantifierFixedCount);

        unsigned parenthesesFrameLocation = term.frameLocation;
        unsigned alternativeFrameLocation = parenthesesFrameLocation + YarrStackSpaceForBackTrackInfoParentheticalAssertion;

        int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;

        if (term.invert()) {
            // Inverted case
            storeToFrame(index, parenthesesFrameLocation);

            state.checkedTotal -= countCheckedAfterAssertion;
            if (countCheckedAfterAssertion)
                sub32(Imm32(countCheckedAfterAssertion), index);

            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
            // Success! - which means - Fail!
            loadFromFrame(parenthesesFrameLocation, index);
            state.jumpToBacktrack(this);

            // And fail means success.
            parenthesesState.linkAlternativeBacktracks(this);

            loadFromFrame(parenthesesFrameLocation, index);

            state.checkedTotal += countCheckedAfterAssertion;
        } else {
            // Normal case
            storeToFrame(index, parenthesesFrameLocation);

            state.checkedTotal -= countCheckedAfterAssertion;
            if (countCheckedAfterAssertion)
                sub32(Imm32(countCheckedAfterAssertion), index);

            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
            // Success! - which means - Success!
            loadFromFrame(parenthesesFrameLocation, index);
            Jump success = jump();

            parenthesesState.linkAlternativeBacktracks(this);

            loadFromFrame(parenthesesFrameLocation, index);
            state.jumpToBacktrack(this);

            success.link(this);

            state.checkedTotal += countCheckedAfterAssertion;
        }
    }

    void generateTerm(TermGenerationState& state)
    {
        PatternTerm& term = state.term();

        switch (term.type) {
        case PatternTerm::TypeAssertionBOL:
            generateAssertionBOL(state);
            break;

        case PatternTerm::TypeAssertionEOL:
            generateAssertionEOL(state);
            break;

        case PatternTerm::TypeAssertionWordBoundary:
            generateAssertionWordBoundary(state);
            break;

        case PatternTerm::TypePatternCharacter:
            switch (term.quantityType) {
            case QuantifierFixedCount:
                if (term.quantityCount == 1) {
                    if (state.isSinglePatternCharacterLookaheadTerm() && (state.lookaheadTerm().inputPosition == (term.inputPosition + 1))) {
                        generatePatternCharacterPair(state);
                        state.nextTerm();
                    } else
                        generatePatternCharacterSingle(state);
                } else
                    generatePatternCharacterFixed(state);
                break;
            case QuantifierGreedy:
                generatePatternCharacterGreedy(state);
                break;
            case QuantifierNonGreedy:
                generatePatternCharacterNonGreedy(state);
                break;
            }
            break;

        case PatternTerm::TypeCharacterClass:
            switch (term.quantityType) {
            case QuantifierFixedCount:
                if (term.quantityCount == 1)
                    generateCharacterClassSingle(state);
                else
                    generateCharacterClassFixed(state);
                break;
            case QuantifierGreedy:
                generateCharacterClassGreedy(state);
                break;
            case QuantifierNonGreedy:
                generateCharacterClassNonGreedy(state);
                break;
            }
            break;

        case PatternTerm::TypeBackReference:
            m_shouldFallBack = true;
            break;

        case PatternTerm::TypeForwardReference:
            break;

        case PatternTerm::TypeParenthesesSubpattern:
            if (term.quantityCount == 1 && !term.parentheses.isCopy)
                generateParenthesesSingle(state);
            else if (term.parentheses.isTerminal)
                generateParenthesesGreedyNoBacktrack(state);
            else
                m_shouldFallBack = true;
            break;

        case PatternTerm::TypeParentheticalAssertion:
            generateParentheticalAssertion(state);
            break;
        }
    }

    void generateDisjunction(PatternDisjunction* disjunction)
    {
        TermGenerationState state(disjunction, 0);
        state.resetAlternative();

        // check availability for the next alternative
        int countCheckedForCurrentAlternative = 0;
        int countToCheckForFirstAlternative = 0;
        bool hasShorterAlternatives = false;
        bool setRepeatAlternativeLabels = false;
        JumpList notEnoughInputForPreviousAlternative;
        Label firstAlternative;
        Label firstAlternativeInputChecked;

        // The label 'firstAlternative' is used to plant a check to see if there is
        // sufficient input available to run the first repeating alternative.
        // The label 'firstAlternativeInputChecked' will jump directly to matching
        // the first repeating alternative having skipped this check.

        if (state.alternativeValid()) {
            PatternAlternative* alternative = state.alternative();
            if (!alternative->onceThrough()) {
                firstAlternative = Label(this);
                setRepeatAlternativeLabels = true;
            }
            countToCheckForFirstAlternative = alternative->m_minimumSize;
            state.checkedTotal += countToCheckForFirstAlternative;
            if (countToCheckForFirstAlternative)
                notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
            countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
        }

        if (setRepeatAlternativeLabels)
            firstAlternativeInputChecked = Label(this);

        while (state.alternativeValid()) {
            PatternAlternative* alternative = state.alternative();
            optimizeAlternative(alternative);

            // Track whether any alternatives are shorter than the first one.
            if (!alternative->onceThrough())
                hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative);

            for (state.resetTerm(); state.termValid(); state.nextTerm())
                generateTerm(state);

            // If we get here, the alternative matched.
            if (m_pattern.m_body->m_callFrameSize)
                addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);

            ASSERT(index != returnRegister);
            if (m_pattern.m_body->m_hasFixedSize) {
                move(index, returnRegister);
                if (alternative->m_minimumSize)
                    sub32(Imm32(alternative->m_minimumSize), returnRegister);

                store32(returnRegister, output);
            } else
                load32(Address(output), returnRegister);

            store32(index, Address(output, 4));

            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()) {
                state.setJumpListToPriorParen(0);
                PatternAlternative* nextAlternative = state.alternative();
                if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
                    // We have handled non-repeating alternatives, jump to next iteration
                    // and loop over repeating alternatives.
                    state.jumpToBacktrack(this);

                    countToCheckForFirstAlternative = nextAlternative->m_minimumSize;

                    // If we get here, there the last input checked failed.
                    notEnoughInputForPreviousAlternative.link(this);

                    state.linkAlternativeBacktracks(this);

                    // Back up to start the looping alternatives.
                    if (countCheckedForCurrentAlternative)
                        sub32(Imm32(countCheckedForCurrentAlternative), index);

                    firstAlternative = Label(this);

                    state.checkedTotal = countToCheckForFirstAlternative;
                    if (countToCheckForFirstAlternative)
                        notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));

                    countCheckedForCurrentAlternative = countToCheckForFirstAlternative;

                    firstAlternativeInputChecked = Label(this);

                    setRepeatAlternativeLabels = true;
                } else {
                    int countToCheckForNextAlternative = nextAlternative->m_minimumSize;

                    if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one.
                        // If we get here, then the last input checked failed.
                        notEnoughInputForPreviousAlternative.link(this);

                        // Check if sufficent input available to run the next alternative
                        notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
                        // We are now in the correct state to enter the next alternative; this add is only required
                        // to mirror and revert operation of the sub32, just below.
                        add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);

                        // 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);
                    } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one.
                        // If we get here, then the last input checked failed.
                        // If there is insufficient input to run the current alternative, and the next alternative is longer,
                        // then there is definitely not enough input to run it - don't even check. Just adjust index, as if
                        // we had checked.
                        notEnoughInputForPreviousAlternative.link(this);
                        add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index);
                        notEnoughInputForPreviousAlternative.append(jump());

                        // 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);

                        // If the next alterative is the same length as this one, then no need to check the input -
                        // if there was sufficent input to run the current alternative then there is sufficient
                        // input to run the next one; if not, there isn't.
                        state.linkAlternativeBacktracks(this);
                    }
                    state.checkedTotal -= countCheckedForCurrentAlternative;
                    countCheckedForCurrentAlternative = countToCheckForNextAlternative;
                    state.checkedTotal += countCheckedForCurrentAlternative;
                }
            }
        }

        // If we get here, all Alternatives failed...

        state.checkedTotal -= countCheckedForCurrentAlternative;

        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, true);

            notEnoughInputForPreviousAlternative.link(this);
        } else {
            // How much more input need there be to be able to retry from the first alternative?
            // examples:
            //   /yarr_jit/ or /wrec|pcre/
            //     In these examples we need check for one more input before looping.
            //   /yarr_jit|pcre/
            //     In this case we need check for 5 more input to loop (+4 to allow for the first alterative
            //     being four longer than the last alternative checked, and another +1 to effectively move
            //     the start position along by one).
            //   /yarr|rules/ or /wrec|notsomuch/
            //     In these examples, provided that there was sufficient input to have just been matching for
            //     the second alternative we can loop without checking for available input (since the second
            //     alternative is longer than the first).  In the latter example we need to decrement index
            //     (by 4) so the start position is only progressed by 1 from the last iteration.
            int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1;

            // 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, 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(this, firstAlternativeInputChecked, true);
            else { // no need to check the input, but we do have some bookkeeping to do first.
                state.linkAlternativeBacktracks(this, true);

                // Where necessary update our preserved start position.
                if (!m_pattern.m_body->m_hasFixedSize) {
                    move(index, regT0);
                    sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
                    store32(regT0, Address(output));
                }

                // Update index if necessary, and loop (without checking).
                if (incrementForNextIter)
                    add32(Imm32(incrementForNextIter), index);
                jump().linkTo(firstAlternativeInputChecked, this);
            }

            notEnoughInputForPreviousAlternative.link(this);
            // Update our idea of the start position, if we're tracking this.
            if (!m_pattern.m_body->m_hasFixedSize) {
                if (countCheckedForCurrentAlternative - 1) {
                    move(index, regT0);
                    sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
                    store32(regT0, Address(output));
                } else
                    store32(index, Address(output));
            }

            // Check if there is sufficent input to run the first alternative again.
            jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this);
            // No - insufficent input to run the first alteranative, are there any other alternatives we
            // might need to check?  If so, the last check will have left the index incremented by
            // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative
            // LESS input is available, to have the effect of just progressing the start position by 1
            // from the last iteration.  If this check passes we can just jump up to the check associated
            // with the first alternative in the loop.  This is a bit sad, since we'll end up trying the
            // first alternative again, and this check will fail (otherwise the check planted just above
            // here would have passed).  This is a bit sad, however it saves trying to do something more
            // complex here in compilation, and in the common case we should end up coallescing the checks.
            //
            // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least
            // of the minimum-alternative-lengths.  E.g. if I have two alternatives of length 200 and 150,
            // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there
            // is sufficient input to run either alternative (constantly failing).  If there had been only
            // one alternative, or if the shorter alternative had come first, we would have terminated
            // immediately. :-/
            if (hasShorterAlternatives)
                jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this);
            // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true,
            // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ...
            // but since we're about to return a failure this doesn't really matter!)
        }

        if (m_pattern.m_body->m_callFrameSize)
            addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);

        move(TrustedImm32(-1), returnRegister);

        generateReturn();

        m_expressionState.emitParenthesesTail(this);
        m_expressionState.emitIndirectJumpTable(this);
        m_expressionState.linkToNextIteration(this);
    }

    void generateEnter()
    {
#if CPU(X86_64)
        push(X86Registers::ebp);
        move(stackPointerRegister, X86Registers::ebp);
        push(X86Registers::ebx);
#elif CPU(X86)
        push(X86Registers::ebp);
        move(stackPointerRegister, X86Registers::ebp);
        // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
        push(X86Registers::ebx);
        push(X86Registers::edi);
        push(X86Registers::esi);
        // load output into edi (2 = saved ebp + return address).
    #if COMPILER(MSVC)
        loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
        loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
        loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
        loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
    #else
        loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
    #endif
#elif CPU(ARM)
        push(ARMRegisters::r4);
        push(ARMRegisters::r5);
        push(ARMRegisters::r6);
#if CPU(ARM_TRADITIONAL)
        push(ARMRegisters::r8); // scratch register
#endif
        move(ARMRegisters::r3, output);
#elif CPU(SH4)
        push(SH4Registers::r11);
        push(SH4Registers::r13);
#elif CPU(MIPS)
        // Do nothing.
#endif
    }

    void generateReturn()
    {
#if CPU(X86_64)
        pop(X86Registers::ebx);
        pop(X86Registers::ebp);
#elif CPU(X86)
        pop(X86Registers::esi);
        pop(X86Registers::edi);
        pop(X86Registers::ebx);
        pop(X86Registers::ebp);
#elif CPU(ARM)
#if CPU(ARM_TRADITIONAL)
        pop(ARMRegisters::r8); // scratch register
#endif
        pop(ARMRegisters::r6);
        pop(ARMRegisters::r5);
        pop(ARMRegisters::r4);
#elif CPU(SH4)
        pop(SH4Registers::r13);
        pop(SH4Registers::r11);
#elif CPU(MIPS)
        // Do nothing
#endif
        ret();
    }

public:
    YarrGenerator(YarrPattern& pattern)
        : m_pattern(pattern)
        , m_shouldFallBack(false)
    {
    }

    void generate()
    {
        generateEnter();

        if (!m_pattern.m_body->m_hasFixedSize)
            store32(index, Address(output));

        if (m_pattern.m_body->m_callFrameSize)
            subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);

        generateDisjunction(m_pattern.m_body);
    }

    void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject)
    {
        generate();

        LinkBuffer patchBuffer(this, globalData->regexAllocator.poolForSize(size()), 0);

        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);
    }

private:
    YarrPattern& m_pattern;
    bool m_shouldFallBack;
    GenerationState m_expressionState;
};

void jitCompile(YarrPattern& pattern, JSGlobalData* globalData, YarrCodeBlock& jitObject)
{
    YarrGenerator(pattern).compile(globalData, jitObject);
}

int execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output)
{
    return jitObject.execute(input, start, length, output);
}

}}

#endif