15f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian/*
25f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * Copyright (C) 2009 Apple Inc. All rights reserved.
35f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian *
45f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * Redistribution and use in source and binary forms, with or without
55f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * modification, are permitted provided that the following conditions
65f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * are met:
75f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * 1. Redistributions of source code must retain the above copyright
85f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian *    notice, this list of conditions and the following disclaimer.
95f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * 2. Redistributions in binary form must reproduce the above copyright
105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian *    notice, this list of conditions and the following disclaimer in the
115f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian *    documentation and/or other materials provided with the distribution.
125f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian *
135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
175f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian */
255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian#include "config.h"
2765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "YarrJIT.h"
285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
295f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian#include "ASCIICType.h"
300bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch#include "LinkBuffer.h"
3165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "Yarr.h"
325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian#if ENABLE(YARR_JIT)
345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qianusing namespace WTF;
365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qiannamespace JSC { namespace Yarr {
385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
3965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochclass YarrGenerator : private MacroAssembler {
4065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch    friend void jitCompile(JSGlobalData*, YarrCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);
415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
42d0825bca7fe65beaee391d30da42e937db621564Steve Block#if CPU(ARM)
43231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID input = ARMRegisters::r0;
44231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID index = ARMRegisters::r1;
45231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID length = ARMRegisters::r2;
46231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID output = ARMRegisters::r4;
470bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch
48231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID regT0 = ARMRegisters::r5;
49231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID regT1 = ARMRegisters::r6;
505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
51231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID returnRegister = ARMRegisters::r0;
52dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block#elif CPU(MIPS)
53dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block    static const RegisterID input = MIPSRegisters::a0;
54dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block    static const RegisterID index = MIPSRegisters::a1;
55dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block    static const RegisterID length = MIPSRegisters::a2;
56dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block    static const RegisterID output = MIPSRegisters::a3;
57dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block
58dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block    static const RegisterID regT0 = MIPSRegisters::t4;
59dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block    static const RegisterID regT1 = MIPSRegisters::t5;
60dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block
61dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block    static const RegisterID returnRegister = MIPSRegisters::v0;
622daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch#elif CPU(SH4)
632daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch    static const RegisterID input = SH4Registers::r4;
642daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch    static const RegisterID index = SH4Registers::r5;
652daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch    static const RegisterID length = SH4Registers::r6;
662daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch    static const RegisterID output = SH4Registers::r7;
672daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch
682daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch    static const RegisterID regT0 = SH4Registers::r0;
692daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch    static const RegisterID regT1 = SH4Registers::r1;
702daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch
712daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch    static const RegisterID returnRegister = SH4Registers::r0;
72d0825bca7fe65beaee391d30da42e937db621564Steve Block#elif CPU(X86)
73231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID input = X86Registers::eax;
74231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID index = X86Registers::edx;
75231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID length = X86Registers::ecx;
76231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID output = X86Registers::edi;
775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
78231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID regT0 = X86Registers::ebx;
79231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID regT1 = X86Registers::esi;
805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
81231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID returnRegister = X86Registers::eax;
82d0825bca7fe65beaee391d30da42e937db621564Steve Block#elif CPU(X86_64)
83231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID input = X86Registers::edi;
84231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID index = X86Registers::esi;
85231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID length = X86Registers::edx;
86231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID output = X86Registers::ecx;
875f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
88231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID regT0 = X86Registers::eax;
89231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID regT1 = X86Registers::ebx;
905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
91231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block    static const RegisterID returnRegister = X86Registers::eax;
925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian#endif
935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void optimizeAlternative(PatternAlternative* alternative)
955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (!alternative->m_terms.size())
975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            return;
985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {
1005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            PatternTerm& term = alternative->m_terms[i];
1015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            PatternTerm& nextTerm = alternative->m_terms[i + 1];
1025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if ((term.type == PatternTerm::TypeCharacterClass)
1045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                && (term.quantityType == QuantifierFixedCount)
1055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                && (nextTerm.type == PatternTerm::TypePatternCharacter)
1065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                && (nextTerm.quantityType == QuantifierFixedCount)) {
1075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                PatternTerm termCopy = term;
1085f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                alternative->m_terms[i] = nextTerm;
1095f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                alternative->m_terms[i + 1] = termCopy;
1105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
1115f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
1125f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
1135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
1155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
1165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        do {
1175f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // pick which range we're going to generate
1185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            int which = count >> 1;
1195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            char lo = ranges[which].begin;
1205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            char hi = ranges[which].end;
121f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // check if there are any ranges or matches below lo.  If not, just jl to failure -
1235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // if there is anything else to check, check that first, if it falls through jmp to failure.
1245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
1255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
126f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                // generate code for all ranges before this one
1285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                if (which)
1295f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
130f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
1325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
1335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    ++*matchIndex;
1345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                }
1355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                failures.append(jump());
1365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                loOrAbove.link(this);
1385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            } else if (which) {
1395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
1405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
1425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                failures.append(jump());
1435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                loOrAbove.link(this);
1455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            } else
1465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));
1475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
1495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                ++*matchIndex;
1505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
1525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // fall through to here, the value is above hi.
1535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // shuffle along & loop around if there are any more matches to handle.
1555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            unsigned next = which + 1;
1565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ranges += next;
1575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            count -= next;
1585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } while (count);
1595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
1605f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
1625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
163dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block        if (charClass->m_table) {
164dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block            ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table));
165f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry));
166dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block            return;
167dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block        }
1685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Jump unicodeFail;
1695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
1702bde8e466a4451c7319e3a072d118917957d6554Steve Block            Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f));
171f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1725f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (charClass->m_matchesUnicode.size()) {
1735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {
1745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    UChar ch = charClass->m_matchesUnicode[i];
1755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    matchDest.append(branch32(Equal, character, Imm32(ch)));
1765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                }
1775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
178f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (charClass->m_rangesUnicode.size()) {
1805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {
1815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    UChar lo = charClass->m_rangesUnicode[i].begin;
1825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    UChar hi = charClass->m_rangesUnicode[i].end;
183f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    Jump below = branch32(LessThan, character, Imm32(lo));
1855f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
1865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    below.link(this);
1875f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                }
1885f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
1895f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            unicodeFail = jump();
1915f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            isAscii.link(this);
1925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
1935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (charClass->m_ranges.size()) {
1955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            unsigned matchIndex = 0;
196f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            JumpList failures;
1975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
1985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            while (matchIndex < charClass->m_matches.size())
1995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
2005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            failures.link(this);
2025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else if (charClass->m_matches.size()) {
2035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // optimization: gather 'a','A' etc back together, can mask & test once.
2045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            Vector<char> matchesAZaz;
2055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {
2075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                char ch = charClass->m_matches[i];
2085f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                if (m_pattern.m_ignoreCase) {
2095f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    if (isASCIILower(ch)) {
2105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                        matchesAZaz.append(ch);
2115f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                        continue;
2125f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    }
2135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    if (isASCIIUpper(ch))
2145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                        continue;
2155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                }
2165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
2175f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
2185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (unsigned countAZaz = matchesAZaz.size()) {
2202bde8e466a4451c7319e3a072d118917957d6554Steve Block                or32(TrustedImm32(32), character);
2215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                for (unsigned i = 0; i < countAZaz; ++i)
2222bde8e466a4451c7319e3a072d118917957d6554Steve Block                    matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));
2235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
2245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
2255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())
2275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            unicodeFail.link(this);
2285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2295f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2305f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    // Jumps if input not available; will have (incorrectly) incremented already!
2315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    Jump jumpIfNoAvailableInput(unsigned countToCheck)
2325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        add32(Imm32(countToCheck), index);
2345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        return branch32(Above, index, length);
2355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    Jump jumpIfAvailableInput(unsigned countToCheck)
2385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        add32(Imm32(countToCheck), index);
2405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        return branch32(BelowOrEqual, index, length);
2415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    Jump checkInput()
2445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        return branch32(BelowOrEqual, index, length);
2465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    Jump atEndOfInput()
2495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        return branch32(Equal, index, length);
2515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    Jump notAtEndOfInput()
2545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        return branch32(NotEqual, index, length);
2565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    Jump jumpIfCharEquals(UChar ch, int inputPosition)
2595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2605f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        return branch16(Equal, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
2615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    Jump jumpIfCharNotEquals(UChar ch, int inputPosition)
2645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        return branch16(NotEqual, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
2665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2675f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void readCharacter(int inputPosition, RegisterID reg)
2695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
2715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2725f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void storeToFrame(RegisterID reg, unsigned frameLocation)
2745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        poke(reg, frameLocation);
2765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2782bde8e466a4451c7319e3a072d118917957d6554Steve Block    void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
2795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        poke(imm, frameLocation);
2815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
2845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2852bde8e466a4451c7319e3a072d118917957d6554Steve Block        return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
2865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2875f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2885f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void loadFromFrame(unsigned frameLocation, RegisterID reg)
2895f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        peek(reg, frameLocation);
2915f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void loadFromFrameAndJump(unsigned frameLocation)
2945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
2965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
2975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
298f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    struct IndirectJumpEntry {
299f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        IndirectJumpEntry(int32_t stackOffset)
300f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            : m_stackOffset(stackOffset)
301f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
302f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
303f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
304f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        IndirectJumpEntry(int32_t stackOffset, Jump jump)
305f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            : m_stackOffset(stackOffset)
306f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
307f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            addJump(jump);
308f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
309f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
31065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        IndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
31165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        : m_stackOffset(stackOffset)
31265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        {
31365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            addDataLabel(dataLabel);
31465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        }
31565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch
316f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void addJump(Jump jump)
317f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
318f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_relJumps.append(jump);
319f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
32065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch
32165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void addDataLabel(DataLabelPtr dataLabel)
32265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        {
32365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            m_dataLabelPtrVector.append(dataLabel);
32465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        }
325f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
326f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        int32_t m_stackOffset;
327f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        JumpList m_relJumps;
32865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        Vector<DataLabelPtr, 16> m_dataLabelPtrVector;
329f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    };
330f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
3315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    struct AlternativeBacktrackRecord {
3325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        DataLabelPtr dataLabel;
3335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label backtrackLocation;
3345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
3355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        AlternativeBacktrackRecord(DataLabelPtr dataLabel, Label backtrackLocation)
3365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            : dataLabel(dataLabel)
3375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            , backtrackLocation(backtrackLocation)
3385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
3395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
3405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    };
3415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
342f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    struct ParenthesesTail;
343f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    struct TermGenerationState;
344f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
345f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    struct GenerationState {
346f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        typedef HashMap<int, IndirectJumpEntry*, WTF::IntHash<uint32_t>, UnsignedWithZeroKeyHashTraits<uint32_t> > IndirectJumpHashMap;
347f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
348f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        GenerationState()
349f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            : m_parenNestingLevel(0)
350f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
351f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
352f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
353f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void addIndirectJumpEntry(int32_t stackOffset, Jump jump)
354f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
355f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset);
356f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
357f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            ASSERT(stackOffset >= 0);
358f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
359f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            uint32_t offset = static_cast<uint32_t>(stackOffset);
360f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
361f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (result == m_indirectJumpMap.end())
362f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, jump));
363f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else
364f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                result->second->addJump(jump);
365f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
366f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
367f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void addIndirectJumpEntry(int32_t stackOffset, JumpList jumps)
368f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
369f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            JumpList::JumpVector jumpVector = jumps.jumps();
370f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            size_t size = jumpVector.size();
371f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            for (size_t i = 0; i < size; ++i)
372f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                addIndirectJumpEntry(stackOffset, jumpVector[i]);
373f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
374f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            jumps.empty();
375f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
376f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
37765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void addIndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
37865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        {
37965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset);
38065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch
38165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            ASSERT(stackOffset >= 0);
38265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch
38365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            uint32_t offset = static_cast<uint32_t>(stackOffset);
38465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch
38565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            if (result == m_indirectJumpMap.end())
38665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, dataLabel));
38765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            else
38865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                result->second->addDataLabel(dataLabel);
38965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        }
39065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch
391f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void emitIndirectJumpTable(MacroAssembler* masm)
392f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
393f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            for (IndirectJumpHashMap::iterator iter = m_indirectJumpMap.begin(); iter != m_indirectJumpMap.end(); ++iter) {
394f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                IndirectJumpEntry* indJumpEntry = iter->second;
39565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                size_t size = indJumpEntry->m_dataLabelPtrVector.size();
39665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                if (size) {
39765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                    // Link any associated DataLabelPtr's with indirect jump via label
39865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                    Label hereLabel = masm->label();
39965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                    for (size_t i = 0; i < size; ++i)
40065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                        m_backtrackRecords.append(AlternativeBacktrackRecord(indJumpEntry->m_dataLabelPtrVector[i], hereLabel));
40165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                }
402f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                indJumpEntry->m_relJumps.link(masm);
403f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                masm->jump(Address(stackPointerRegister, indJumpEntry->m_stackOffset));
404f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                delete indJumpEntry;
405f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
406f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
407f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
408f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void incrementParenNestingLevel()
409f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
410f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            ++m_parenNestingLevel;
411f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
412f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
413f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void decrementParenNestingLevel()
414f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
415f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            --m_parenNestingLevel;
416f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
417f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
4182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block        ParenthesesTail* addParenthesesTail(PatternTerm& term, JumpList* jumpListToPriorParen)
419f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
4202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, jumpListToPriorParen);
421f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_parenTails.append(parenthesesTail);
422f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_parenTailsForIteration.append(parenthesesTail);
423f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
424f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return parenthesesTail;
425f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
426f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
42765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void emitParenthesesTail(YarrGenerator* generator)
428f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
429f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            unsigned vectorSize = m_parenTails.size();
430f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            bool priorBacktrackFallThrough = false;
431f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
432f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // Emit in reverse order so parentTail N can fall through to N-1
433f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            for (unsigned index = vectorSize; index > 0; --index) {
434f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                JumpList jumpsToNext;
435f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                priorBacktrackFallThrough = m_parenTails[index-1].get()->generateCode(generator, jumpsToNext, priorBacktrackFallThrough, index > 1);
436f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (index > 1)
437f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    jumpsToNext.linkTo(generator->label(), generator);
438f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                else
439f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    addJumpsToNextInteration(jumpsToNext);
440f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
441f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_parenTails.clear();
442f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
443f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
444f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void addJumpToNextInteration(Jump jump)
445f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
446f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_jumpsToNextInteration.append(jump);
447f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
448f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
449f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void addJumpsToNextInteration(JumpList jumps)
450f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
451f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_jumpsToNextInteration.append(jumps);
452f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
453f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
454f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void addDataLabelToNextIteration(DataLabelPtr dataLabel)
455f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
456f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_dataPtrsToNextIteration.append(dataLabel);
457f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
458f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
459f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void linkToNextIteration(Label label)
460f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
461f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_nextIteration = label;
462f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
463f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            for (unsigned i = 0; i < m_dataPtrsToNextIteration.size(); ++i)
464f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataPtrsToNextIteration[i], m_nextIteration));
465f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
466f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_dataPtrsToNextIteration.clear();
467f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
468f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            for (unsigned i = 0; i < m_parenTailsForIteration.size(); ++i)
469f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_parenTailsForIteration[i]->setNextIteration(m_nextIteration);
470f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
471f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_parenTailsForIteration.clear();
472f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
473f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
47465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void linkToNextIteration(YarrGenerator* generator)
475f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
476f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_jumpsToNextInteration.linkTo(m_nextIteration, generator);
477f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
478f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
479f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        int m_parenNestingLevel;
480f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Vector<AlternativeBacktrackRecord> m_backtrackRecords;
481f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        IndirectJumpHashMap m_indirectJumpMap;
482f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label m_nextIteration;
483f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Vector<OwnPtr<ParenthesesTail> > m_parenTails;
484f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        JumpList m_jumpsToNextInteration;
485f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Vector<DataLabelPtr> m_dataPtrsToNextIteration;
486f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Vector<ParenthesesTail*> m_parenTailsForIteration;
487f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    };
488f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
489f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    struct BacktrackDestination {
490f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        typedef enum {
491f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            NoBacktrack,
492f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            BacktrackLabel,
493f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            BacktrackStackOffset,
494f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            BacktrackJumpList,
495f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            BacktrackLinked
496f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        } BacktrackType;
497f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
498f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination()
499f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            : m_backtrackType(NoBacktrack)
500f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackToLabel(0)
501f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_subDataLabelPtr(0)
502f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_nextBacktrack(0)
503f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackSourceLabel(0)
504f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackSourceJumps(0)
505f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
506f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
507f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
508f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination(int32_t stackOffset)
509f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            : m_backtrackType(BacktrackStackOffset)
510f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackStackOffset(stackOffset)
511f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackToLabel(0)
512f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_subDataLabelPtr(0)
513f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_nextBacktrack(0)
514f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackSourceLabel(0)
515f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackSourceJumps(0)
516f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
517f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
518f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
519f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination(Label label)
520f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            : m_backtrackType(BacktrackLabel)
521f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackLabel(label)
522f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackToLabel(0)
523f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_subDataLabelPtr(0)
524f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_nextBacktrack(0)
525f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackSourceLabel(0)
526f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_backtrackSourceJumps(0)
527f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
528f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
529f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
530f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void clear(bool doDataLabelClear = true)
531f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
532f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackType = NoBacktrack;
533f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (doDataLabelClear)
534f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                clearDataLabel();
535f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_nextBacktrack = 0;
536f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
537f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
538f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void clearDataLabel()
539f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
540f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_dataLabelPtr = DataLabelPtr();
541f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
542f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
543f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        bool hasDestination()
544f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
545f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return (m_backtrackType != NoBacktrack);
546f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
547f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
548f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        bool isStackOffset()
549f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
550f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return (m_backtrackType == BacktrackStackOffset);
551f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
552f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
553f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        bool isLabel()
554f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
555f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return (m_backtrackType == BacktrackLabel);
556f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
557f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
558f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        bool isJumpList()
559f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
560f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return (m_backtrackType == BacktrackJumpList);
561f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
562f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
563f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        bool hasDataLabel()
564f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
565f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return m_dataLabelPtr.isSet();
566f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
567f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
568f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void copyTarget(BacktrackDestination& rhs, bool copyDataLabel = true)
569f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
570f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackType = rhs.m_backtrackType;
571f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_backtrackType == BacktrackStackOffset)
572f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrackStackOffset = rhs.m_backtrackStackOffset;
573f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else if (m_backtrackType == BacktrackLabel)
574f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrackLabel = rhs.m_backtrackLabel;
575f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (copyDataLabel)
576f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_dataLabelPtr = rhs.m_dataLabelPtr;
577f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackSourceJumps = rhs.m_backtrackSourceJumps;
578f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackSourceLabel = rhs.m_backtrackSourceLabel;
579f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
580f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
581f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void copyTo(BacktrackDestination& lhs)
582f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
583f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            lhs.m_backtrackType = m_backtrackType;
584f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_backtrackType == BacktrackStackOffset)
585f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                lhs.m_backtrackStackOffset = m_backtrackStackOffset;
586f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else if (m_backtrackType == BacktrackLabel)
587f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                lhs.m_backtrackLabel = m_backtrackLabel;
588f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            lhs.m_backtrackSourceJumps = m_backtrackSourceJumps;
589f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            lhs.m_backtrackSourceLabel = m_backtrackSourceLabel;
590f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            lhs.m_dataLabelPtr = m_dataLabelPtr;
591f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            lhs.m_backTrackJumps = m_backTrackJumps;
592f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
593f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
594f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void addBacktrackJump(Jump jump)
595f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
596f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backTrackJumps.append(jump);
597f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
598f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
599f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setStackOffset(int32_t stackOffset)
600f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
601f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackType = BacktrackStackOffset;
602f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackStackOffset = stackOffset;
603f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
604f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
605f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setLabel(Label label)
606f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
607f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackType = BacktrackLabel;
608f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackLabel = label;
609f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
610f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
611f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setNextBacktrackLabel(Label label)
612f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
613f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_nextBacktrack)
614f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_nextBacktrack->setLabel(label);
615f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
616f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
617ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch        void propagateBacktrackToLabel(const BacktrackDestination& rhs)
618f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
619ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch            if (!m_backtrackToLabel && rhs.m_backtrackToLabel)
620f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrackToLabel = rhs.m_backtrackToLabel;
621f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
622f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
623f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setBacktrackToLabel(Label* backtrackToLabel)
624f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
625f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (!m_backtrackToLabel)
626f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrackToLabel = backtrackToLabel;
627f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
628f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
629ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch        bool hasBacktrackToLabel()
630ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch        {
631ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch            return m_backtrackToLabel;
632ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch        }
633ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch
634f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setBacktrackJumpList(JumpList* jumpList)
635f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
636f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackType = BacktrackJumpList;
637f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackSourceJumps = jumpList;
638f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
639f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
640f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setBacktrackSourceLabel(Label* backtrackSourceLabel)
641f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
642f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackSourceLabel = backtrackSourceLabel;
643f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
644f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
645f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setDataLabel(DataLabelPtr dp)
646f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
647f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_subDataLabelPtr) {
648f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                *m_subDataLabelPtr = dp;
649f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_subDataLabelPtr = 0;
650ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch            } else {
651ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch                ASSERT(!hasDataLabel());
652f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_dataLabelPtr = dp;
653ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch            }
654f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
655f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
65665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void clearSubDataLabelPtr()
65765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        {
65865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            m_subDataLabelPtr = 0;
65965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        }
66065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch
661f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setSubDataLabelPtr(DataLabelPtr* subDataLabelPtr)
662f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
663f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_subDataLabelPtr = subDataLabelPtr;
664f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
665f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
666f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void linkToNextBacktrack(BacktrackDestination* nextBacktrack)
667f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
668f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_nextBacktrack = nextBacktrack;
669f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
670f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
671f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        int32_t getStackOffset()
672f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
673f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            ASSERT(m_backtrackType == BacktrackStackOffset);
674f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return m_backtrackStackOffset;
675f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
676f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
677f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label getLabel()
678f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
679f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            ASSERT(m_backtrackType == BacktrackLabel);
680f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return m_backtrackLabel;
681f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
682f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
683f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        JumpList& getBacktrackJumps()
684f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
685f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return m_backTrackJumps;
686f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
687f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
688f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        DataLabelPtr& getDataLabel()
689f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
690f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return m_dataLabelPtr;
691f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
692f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
693f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void jumpToBacktrack(MacroAssembler* masm)
694f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
695f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (isJumpList()) {
696f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
697f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    masm->jump().linkTo(*m_backtrackSourceLabel, masm);
698f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                else
699f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    m_backtrackSourceJumps->append(masm->jump());
700f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            } else if (isStackOffset())
701f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                masm->jump(Address(stackPointerRegister, m_backtrackStackOffset));
702f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else if (isLabel())
703f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                masm->jump().linkTo(m_backtrackLabel, masm);
704f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else
705f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backTrackJumps.append(masm->jump());
706f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
707f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
70865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void jumpToBacktrack(YarrGenerator* generator, Jump jump)
709f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
710f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (isJumpList()) {
711f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
712f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    jump.linkTo(*m_backtrackSourceLabel, generator);
713f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                else
714f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    m_backtrackSourceJumps->append(jump);
715f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            } else if (isStackOffset())
716f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jump);
717f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else if (isLabel())
718f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                jump.linkTo(getLabel(), generator);
719f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else
720f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backTrackJumps.append(jump);
721f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
722f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
72365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps)
724f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
725f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (isJumpList()) {
726f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
727f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    jumps.linkTo(*m_backtrackSourceLabel, generator);
728f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                else
729f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    m_backtrackSourceJumps->append(jumps);
730f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            } else if (isStackOffset())
731f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jumps);
732f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else if (isLabel())
733f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                jumps.linkTo(getLabel(), generator);
734f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else
735f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backTrackJumps.append(jumps);
736f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
737f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
73865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        bool plantJumpToBacktrackIfExists(YarrGenerator* generator)
739f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
740f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (isJumpList()) {
741f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
742f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    generator->jump(*m_backtrackSourceLabel);
743f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                else
744f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    m_backtrackSourceJumps->append(generator->jump());
745f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
746f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                return true;
747f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
748f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
749f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (isStackOffset()) {
750f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->jump(Address(stackPointerRegister, getStackOffset()));
751f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                return true;
752f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
753f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
754f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (isLabel()) {
755f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->jump(getLabel());
756f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (hasDataLabel()) {
757f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), getLabel()));
758f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    clearDataLabel();
759f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                }
760f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                return true;
761f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
762f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
763f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return false;
764f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
765f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
766ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch        void linkBacktrackToLabel(Label backtrackLabel)
767ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch        {
768ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch            if (m_backtrackToLabel)
769ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch                *m_backtrackToLabel = backtrackLabel;
770ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch        }
771ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch
77265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false)
773f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
774f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            Label hereLabel = generator->label();
775f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
776f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_backtrackToLabel) {
777f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                *m_backtrackToLabel = hereLabel;
778f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrackToLabel = 0;
779f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
780f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
781f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backTrackJumps.link(generator);
782f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
783f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (nextIteration)
784f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->m_expressionState.linkToNextIteration(hereLabel);
785f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
786f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (hasDataLabel()) {
787f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), hereLabel));
788f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                // data label cleared as a result of the clear() below
789f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
790f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
791f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            clear();
792f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
793f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
79465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false)
795f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
796f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backTrackJumps.linkTo(label, generator);
797f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
798f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (nextIteration)
799f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->m_expressionState.linkToNextIteration(label);
800f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
801f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (hasDataLabel()) {
802f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), label));
803f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                clearDataLabel();
804f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
805f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
806f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
807f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    private:
808f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackType m_backtrackType;
809f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        int32_t m_backtrackStackOffset;
810f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label m_backtrackLabel;
811f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        DataLabelPtr m_dataLabelPtr;
812f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label* m_backtrackToLabel;
813f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        DataLabelPtr* m_subDataLabelPtr;
814f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination* m_nextBacktrack;
815f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label* m_backtrackSourceLabel;
816f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        JumpList* m_backtrackSourceJumps;
817f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        JumpList m_backTrackJumps;
818f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    };
819f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
8205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    struct TermGenerationState {
8215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        TermGenerationState(PatternDisjunction* disjunction, unsigned checkedTotal)
8225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            : disjunction(disjunction)
8235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            , checkedTotal(checkedTotal)
824f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_subParenNum(0)
825f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_linkedBacktrack(0)
8262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            , m_jumpList(0)
8275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
8295f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
8305f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        void resetAlternative()
8315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
832f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.clear();
8335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            alt = 0;
8345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
8355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        bool alternativeValid()
8365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            return alt < disjunction->m_alternatives.size();
8385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
8395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        void nextAlternative()
8405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ++alt;
8425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
8435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternAlternative* alternative()
8445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            return disjunction->m_alternatives[alt];
8465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
847f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        bool isLastAlternative()
848f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
849f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return (alt + 1) == disjunction->m_alternatives.size();
850f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
8515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
8525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        void resetTerm()
8535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(alternativeValid());
8555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            t = 0;
856f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_subParenNum = 0;
8575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
8585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        bool termValid()
8595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8605f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(alternativeValid());
8615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            return t < alternative()->m_terms.size();
8625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
8635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        void nextTerm()
8645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(alternativeValid());
8665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ++t;
8675f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
8685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term()
8695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(alternativeValid());
8715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            return alternative()->m_terms[t];
8725f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
8735af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        bool isLastTerm()
8745af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        {
8755af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            ASSERT(alternativeValid());
8765af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            return (t + 1) == alternative()->m_terms.size();
8775af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        }
878f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        unsigned getSubParenNum()
879f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
880f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return m_subParenNum++;
881f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
8825af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        bool isMainDisjunction()
8835af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        {
8845af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            return !disjunction->m_parent;
8855af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        }
8865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
8872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block        void setJumpListToPriorParen(JumpList* jumpList)
888f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
8892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            m_jumpList = jumpList;
890f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
891f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
8922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block        JumpList* getJumpListToPriorParen()
893f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
8942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            return m_jumpList;
895f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
896f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
8975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& lookaheadTerm()
8985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
8995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(alternativeValid());
9005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT((t + 1) < alternative()->m_terms.size());
9015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            return alternative()->m_terms[t + 1];
9025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
9035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        bool isSinglePatternCharacterLookaheadTerm()
9045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
9055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(alternativeValid());
9065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            return ((t + 1) < alternative()->m_terms.size())
9075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                && (lookaheadTerm().type == PatternTerm::TypePatternCharacter)
9085f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                && (lookaheadTerm().quantityType == QuantifierFixedCount)
9095f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                && (lookaheadTerm().quantityCount == 1);
9105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
9115f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
9125f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        int inputOffset()
9135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
9145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            return term().inputPosition - checkedTotal;
9155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
9165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
917f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void clearBacktrack()
9185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
919f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.clear(false);
920f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_linkedBacktrack = 0;
9215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
922f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
923f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void jumpToBacktrack(MacroAssembler* masm)
9245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
925f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.jumpToBacktrack(masm);
926f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
927f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
92865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void jumpToBacktrack(YarrGenerator* generator, Jump jump)
929f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
930f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.jumpToBacktrack(generator, jump);
931f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
932f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
93365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps)
934f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
935f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.jumpToBacktrack(generator, jumps);
936f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
937f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
93865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        bool plantJumpToBacktrackIfExists(YarrGenerator* generator)
939f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
940f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return m_backtrack.plantJumpToBacktrackIfExists(generator);
9415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
942f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
943ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch        void linkDataLabelToBacktrackIfExists(YarrGenerator* generator, DataLabelPtr dataLabel)
9445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
94565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            // If we have a stack offset backtrack destination, use it directly
94665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            if (m_backtrack.isStackOffset()) {
94765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                generator->m_expressionState.addIndirectJumpEntry(m_backtrack.getStackOffset(), dataLabel);
94865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                m_backtrack.clearSubDataLabelPtr();
94965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            } else {
950ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch                // If we have a backtrack label, connect the datalabel to it directly.
951ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch                if (m_backtrack.isLabel())
952ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch                    generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(dataLabel, m_backtrack.getLabel()));
953ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch                else
954ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch                    setBacktrackDataLabel(dataLabel);
9555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
9565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
957f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
9585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        void addBacktrackJump(Jump jump)
9595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
960f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.addBacktrackJump(jump);
9615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
962f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
963f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setBacktrackDataLabel(DataLabelPtr dp)
9645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
965f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.setDataLabel(dp);
9665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
967f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
968f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setBackTrackStackOffset(int32_t stackOffset)
969f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
970f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.setStackOffset(stackOffset);
971f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
972f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
973f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setBacktrackLabel(Label label)
974f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
975f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.setLabel(label);
976f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
977f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
97865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false)
979f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
980f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.linkAlternativeBacktracks(generator, nextIteration);
981f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_linkedBacktrack = 0;
982f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
983f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
98465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false)
985f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
986f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrack.linkAlternativeBacktracksTo(generator, label, nextIteration);
987f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
988f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
989f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setBacktrackLink(BacktrackDestination* linkedBacktrack)
990f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
991f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_linkedBacktrack = linkedBacktrack;
992f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
993f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
994f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void chainBacktracks(BacktrackDestination* followonBacktrack)
995f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
996f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_linkedBacktrack)
997f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_linkedBacktrack->linkToNextBacktrack(followonBacktrack);
998f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
999f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1000f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination& getBacktrackDestination()
10015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
1002f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return m_backtrack;
10035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
1004f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
100565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void propagateBacktrackingFrom(YarrGenerator* generator, BacktrackDestination& backtrack, bool doJump = true)
10065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        {
1007f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (doJump)
1008f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrack.jumpToBacktrack(generator, backtrack.getBacktrackJumps());
1009ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch
1010ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch            if (m_backtrack.isLabel() && backtrack.hasBacktrackToLabel())
1011ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch                backtrack.linkBacktrackToLabel(m_backtrack.getLabel());
1012ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch
1013f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (backtrack.hasDestination()) {
1014f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (m_backtrack.hasDataLabel())
1015f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    generator->m_expressionState.addDataLabelToNextIteration(m_backtrack.getDataLabel());
1016f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1017f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrack.copyTarget(backtrack, doJump);
1018f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
10195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
10205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
10215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternDisjunction* disjunction;
10225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        int checkedTotal;
10235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    private:
10245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        unsigned alt;
10255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        unsigned t;
1026f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        unsigned m_subParenNum;
1027f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination m_backtrack;
1028f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination* m_linkedBacktrack;
10292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block        JumpList* m_jumpList;
1030f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    };
1031f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1032f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    struct ParenthesesTail {
10332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block        ParenthesesTail(PatternTerm& term, int nestingLevel, JumpList* jumpListToPriorParen)
1034f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            : m_term(term)
1035f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_nestingLevel(nestingLevel)
1036f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            , m_subParenIndex(0)
10372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            , m_jumpListToPriorParen(jumpListToPriorParen)
1038f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
1039f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
1040f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
104165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        void processBacktracks(YarrGenerator* generator, TermGenerationState& state, TermGenerationState& parenthesesState, Label nonGreedyTryParentheses, Label fallThrough)
1042f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
1043f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_nonGreedyTryParentheses = nonGreedyTryParentheses;
1044f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_fallThrough = fallThrough;
1045f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1046f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_subParenIndex = state.getSubParenNum();
1047f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            parenthesesState.getBacktrackDestination().copyTo(m_parenBacktrack);
1048f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.chainBacktracks(&m_backtrack);
1049f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
1050f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            stateBacktrack.copyTo(m_backtrack);
1051f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            stateBacktrack.setBacktrackToLabel(&m_backtrackToLabel);
1052f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.setBacktrackLink(&m_backtrack);
1053f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            stateBacktrack.setSubDataLabelPtr(&m_dataAfterLabelPtr);
1054f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1055f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_doDirectBacktrack = m_parenBacktrack.hasDestination();
1056f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1057f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if ((m_term.quantityType == QuantifierGreedy) || (m_term.quantityType == QuantifierNonGreedy))
1058f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_doDirectBacktrack = false;
1059f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1060f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_doDirectBacktrack)
1061f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.propagateBacktrackingFrom(generator, m_parenBacktrack, false);
1062f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            else {
10632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block                stateBacktrack.setBacktrackJumpList(&m_afterBacktrackJumps);
1064f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens);
1065f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
1066f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
1067f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1068f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void setNextIteration(Label nextIteration)
1069f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
1070f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (!m_nestingLevel && !m_backtrackToLabel.isSet())
1071f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrackToLabel = nextIteration;
1072f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
1073f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1074f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        void addAfterParenJump(Jump jump)
1075f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
10762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            m_afterBacktrackJumps.append(jump);
1077f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
1078f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
107965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        bool generateCode(YarrGenerator* generator, JumpList& jumpsToNext, bool priorBackTrackFallThrough, bool nextBacktrackFallThrough)
1080f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        {
1081f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            const RegisterID indexTemporary = regT0;
1082f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            unsigned parenthesesFrameLocation = m_term.frameLocation;
1083f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            Jump fromPriorBacktrack;
1084f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            bool needJumpForPriorParenTail = false;
1085f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1086f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (priorBackTrackFallThrough
1087f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                && ((m_term.quantityType == QuantifierGreedy)
1088f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                 || (m_term.quantityType == QuantifierNonGreedy)
1089f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                 || (!m_doDirectBacktrack && m_parenBacktrack.hasDestination()))) {
1090f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                // If the prior paren tail code assumed that it could fall through,
1091f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                // but we need to generate after paren backtrack code, then provide
1092f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                // a jump around that code for the prior paren tail code.
1093f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                // A regular expressing like ((xxx)...)? needs this.
1094f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                fromPriorBacktrack = generator->jump();
1095f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                needJumpForPriorParenTail = true;
1096f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
1097f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1098f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (!m_backtrack.hasDestination()) {
1099f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (m_backtrackToLabel.isSet()) {
1100f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    m_backtrack.setLabel(m_backtrackToLabel);
1101f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    nextBacktrackFallThrough = false;
11022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block                } else if (m_jumpListToPriorParen) {
11032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block                    // If we don't have a destination, go back to either the prior paren or the next outer paren.
11042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block                    m_backtrack.setBacktrackJumpList(m_jumpListToPriorParen);
1105f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    nextBacktrackFallThrough = false;
1106f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                } else
1107f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    m_backtrack.setBacktrackJumpList(&jumpsToNext);
1108f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            } else
1109f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                nextBacktrackFallThrough = false;
1110f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1111f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // A failure AFTER the parens jumps here - Backtrack to this paren
1112f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_backtrackFromAfterParens = generator->label();
1113f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1114f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_dataAfterLabelPtr.isSet())
1115f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataAfterLabelPtr, m_backtrackFromAfterParens));
1116f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
11172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            m_afterBacktrackJumps.link(generator);
1118f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1119f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_term.quantityType == QuantifierGreedy) {
1120f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                // If this is -1 we have now tested with both with and without the parens.
1121f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
11222bde8e466a4451c7319e3a072d118917957d6554Steve Block                m_backtrack.jumpToBacktrack(generator, generator->branch32(Equal, indexTemporary, TrustedImm32(-1)));
1123f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            } else if (m_term.quantityType == QuantifierNonGreedy) {
1124f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                // If this is -1 we have now tested with both with and without the parens.
1125f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
11262bde8e466a4451c7319e3a072d118917957d6554Steve Block                generator->branch32(Equal, indexTemporary, TrustedImm32(-1)).linkTo(m_nonGreedyTryParentheses, generator);
1127f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            }
1128f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1129f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (!m_doDirectBacktrack)
1130f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_parenBacktrack.plantJumpToBacktrackIfExists(generator);
1131f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1132f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // A failure WITHIN the parens jumps here
1133f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (needJumpForPriorParenTail)
1134f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                fromPriorBacktrack.link(generator);
1135f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_parenBacktrack.linkAlternativeBacktracks(generator);
1136f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_withinBacktrackJumps.link(generator);
1137f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1138f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_term.capture())
11392bde8e466a4451c7319e3a072d118917957d6554Steve Block                generator->store32(TrustedImm32(-1), Address(output, (m_term.parentheses.subpatternId << 1) * sizeof(int)));
1140f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1141f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (m_term.quantityType == QuantifierGreedy) {
11422bde8e466a4451c7319e3a072d118917957d6554Steve Block                generator->storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1143f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                generator->jump().linkTo(m_fallThrough, generator);
1144f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                nextBacktrackFallThrough = false;
1145f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            } else if (!nextBacktrackFallThrough)
1146f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrack.jumpToBacktrack(generator);
1147f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1148f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (!m_doDirectBacktrack)
1149f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                m_backtrack.setNextBacktrackLabel(m_backtrackFromAfterParens);
1150f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1151f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            return nextBacktrackFallThrough;
1152f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        }
1153f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1154f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        PatternTerm& m_term;
1155f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        int m_nestingLevel;
1156f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        unsigned m_subParenIndex;
11572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block        JumpList* m_jumpListToPriorParen;
1158f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label m_nonGreedyTryParentheses;
1159f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label m_fallThrough;
1160f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label m_backtrackToLabel;
1161f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        Label m_backtrackFromAfterParens;
1162f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        DataLabelPtr m_dataAfterLabelPtr;
1163f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        JumpList m_withinBacktrackJumps;
11642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block        JumpList m_afterBacktrackJumps;
1165f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination m_parenBacktrack;
1166f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        BacktrackDestination m_backtrack;
1167f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        bool m_doDirectBacktrack;
11685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    };
11695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
11705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateAssertionBOL(TermGenerationState& state)
11715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
11725f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
11735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
11745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (m_pattern.m_multiline) {
11755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            const RegisterID character = regT0;
11765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
11775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            JumpList matchDest;
11785f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (!term.inputPosition)
11795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                matchDest.append(branch32(Equal, index, Imm32(state.checkedTotal)));
11805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
11815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            readCharacter(state.inputOffset() - 1, character);
11825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1183f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this);
11845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
11855f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchDest.link(this);
11865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
11875f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // Erk, really should poison out these alternatives early. :-/
11885f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (term.inputPosition)
1189f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.jumpToBacktrack(this);
11905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            else
1191f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.jumpToBacktrack(this, branch32(NotEqual, index, Imm32(state.checkedTotal)));
11925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
11935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
11945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
11955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateAssertionEOL(TermGenerationState& state)
11965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
11975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
11985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
11995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (m_pattern.m_multiline) {
12005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            const RegisterID character = regT0;
12015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            JumpList matchDest;
12035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (term.inputPosition == state.checkedTotal)
12045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                matchDest.append(atEndOfInput());
12055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            readCharacter(state.inputOffset(), character);
12075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1208f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this);
12095f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchDest.link(this);
12115f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
12125f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (term.inputPosition == state.checkedTotal)
1213f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.jumpToBacktrack(this, notAtEndOfInput());
12145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // Erk, really should poison out these alternatives early. :-/
12155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            else
1216f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.jumpToBacktrack(this);
12175f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
12185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
12195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    // Also falls though on nextIsNotWordChar.
12215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void matchAssertionWordchar(TermGenerationState& state, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
12225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
12235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
12245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
12255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (term.inputPosition == state.checkedTotal)
12275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            nextIsNotWordChar.append(atEndOfInput());
12285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12295f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        readCharacter(state.inputOffset(), character);
12305f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
12315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
12325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateAssertionWordBoundary(TermGenerationState& state)
12345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
12355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
12365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
12375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Jump atBegin;
12395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList matchDest;
12405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (!term.inputPosition)
12415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            atBegin = branch32(Equal, index, Imm32(state.checkedTotal));
12425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        readCharacter(state.inputOffset() - 1, character);
12435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
12445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (!term.inputPosition)
12455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            atBegin.link(this);
12465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        // We fall through to here if the last character was not a wordchar.
12485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList nonWordCharThenWordChar;
12495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList nonWordCharThenNonWordChar;
1250f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.invert()) {
12515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
12525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            nonWordCharThenWordChar.append(jump());
12535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
12545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
12555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            nonWordCharThenNonWordChar.append(jump());
12565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
1257f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.jumpToBacktrack(this, nonWordCharThenNonWordChar);
12585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        // We jump here if the last character was a wordchar.
12605f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        matchDest.link(this);
12615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList wordCharThenWordChar;
12625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList wordCharThenNonWordChar;
1263f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.invert()) {
12645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
12655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            wordCharThenWordChar.append(jump());
12665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
12675f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchAssertionWordchar(state, wordCharThenWordChar, wordCharThenNonWordChar);
12685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // This can fall-though!
12695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
12705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1271f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.jumpToBacktrack(this, wordCharThenWordChar);
1272f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
12735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        nonWordCharThenWordChar.link(this);
12745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        wordCharThenNonWordChar.link(this);
12755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
12765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generatePatternCharacterSingle(TermGenerationState& state)
12785f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
12795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
12805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        UChar ch = state.term().patternCharacter;
12815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
12835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            readCharacter(state.inputOffset(), character);
12842bde8e466a4451c7319e3a072d118917957d6554Steve Block            or32(TrustedImm32(32), character);
1285f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
12865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
12875f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1288f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this, jumpIfCharNotEquals(ch, state.inputOffset()));
12895f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
12905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
12915f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generatePatternCharacterPair(TermGenerationState& state)
12935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
12945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
12955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        UChar ch1 = state.term().patternCharacter;
12965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        UChar ch2 = state.lookaheadTerm().patternCharacter;
12975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
12985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        int mask = 0;
12995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        int chPair = ch1 | (ch2 << 16);
1300f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
13015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (m_pattern.m_ignoreCase) {
13025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (isASCIIAlpha(ch1))
13035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                mask |= 32;
13045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (isASCIIAlpha(ch2))
13055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                mask |= 32 << 16;
13065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
13075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13085f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (mask) {
1309231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block            load32WithUnalignedHalfWords(BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), character);
13105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            or32(Imm32(mask), character);
1311f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(chPair | mask)));
13125f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else
1313f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this, branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)));
13145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
13155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generatePatternCharacterFixed(TermGenerationState& state)
13175f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
13185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
13195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID countRegister = regT1;
13205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
13215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        UChar ch = term.patternCharacter;
13225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        move(index, countRegister);
13245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        sub32(Imm32(term.quantityCount), countRegister);
13255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label loop(this);
13275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
13285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
13292bde8e466a4451c7319e3a072d118917957d6554Steve Block            or32(TrustedImm32(32), character);
1330f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
13315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
13325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1333f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this, branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)));
13345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
13352bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), countRegister);
13365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        branch32(NotEqual, countRegister, index).linkTo(loop, this);
13375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
13385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generatePatternCharacterGreedy(TermGenerationState& state)
13405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
13415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
13425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID countRegister = regT1;
13435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
13445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        UChar ch = term.patternCharacter;
1345f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
13462bde8e466a4451c7319e3a072d118917957d6554Steve Block        move(TrustedImm32(0), countRegister);
13475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList failures;
13495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label loop(this);
13505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        failures.append(atEndOfInput());
13515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
13525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            readCharacter(state.inputOffset(), character);
13532bde8e466a4451c7319e3a072d118917957d6554Steve Block            or32(TrustedImm32(32), character);
13545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            failures.append(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
13555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
13565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
13575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            failures.append(jumpIfCharNotEquals(ch, state.inputOffset()));
13585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
1359dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block
13602bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), countRegister);
13612bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), index);
1362f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.quantityCount != quantifyInfinite) {
1363dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block            branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
13646c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen            failures.append(jump());
13656c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen        } else
1366dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block            jump(loop);
1367dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block
13685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label backtrackBegin(this);
13695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        loadFromFrame(term.frameLocation, countRegister);
1370f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
13712bde8e466a4451c7319e3a072d118917957d6554Steve Block        sub32(TrustedImm32(1), countRegister);
13722bde8e466a4451c7319e3a072d118917957d6554Steve Block        sub32(TrustedImm32(1), index);
13735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        failures.link(this);
13755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        storeToFrame(countRegister, term.frameLocation);
13775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1378f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.setBacktrackLabel(backtrackBegin);
13795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
13805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generatePatternCharacterNonGreedy(TermGenerationState& state)
13825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
13835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
13845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID countRegister = regT1;
13855f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
13865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        UChar ch = term.patternCharacter;
1387f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
13882bde8e466a4451c7319e3a072d118917957d6554Steve Block        move(TrustedImm32(0), countRegister);
13895f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Jump firstTimeDoNothing = jump();
13915f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label hardFail(this);
13935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        sub32(countRegister, index);
1394f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.jumpToBacktrack(this);
13955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label backtrackBegin(this);
13975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        loadFromFrame(term.frameLocation, countRegister);
13985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
13995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        atEndOfInput().linkTo(hardFail, this);
1400f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.quantityCount != quantifyInfinite)
1401dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block            branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
14025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
14035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            readCharacter(state.inputOffset(), character);
14042bde8e466a4451c7319e3a072d118917957d6554Steve Block            or32(TrustedImm32(32), character);
14055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            branch32(NotEqual, character, Imm32(Unicode::toLower(ch))).linkTo(hardFail, this);
14065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
14075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
14085f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            jumpIfCharNotEquals(ch, state.inputOffset()).linkTo(hardFail, this);
14095f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
14105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14112bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), countRegister);
14122bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), index);
14135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        firstTimeDoNothing.link(this);
14155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        storeToFrame(countRegister, term.frameLocation);
14165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1417f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.setBacktrackLabel(backtrackBegin);
14185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
14195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateCharacterClassSingle(TermGenerationState& state)
14215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
14225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
14235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
14245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList matchDest;
14265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        readCharacter(state.inputOffset(), character);
14275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        matchCharacterClass(character, matchDest, term.characterClass);
14285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1429f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.invert())
1430f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this, matchDest);
14315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        else {
1432f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this);
14335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchDest.link(this);
14345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
14355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
14365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateCharacterClassFixed(TermGenerationState& state)
14385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
14395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
14405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID countRegister = regT1;
14415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
14425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        move(index, countRegister);
14445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        sub32(Imm32(term.quantityCount), countRegister);
14455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label loop(this);
14475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList matchDest;
14485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
14495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        matchCharacterClass(character, matchDest, term.characterClass);
14505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1451f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.invert())
1452f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this, matchDest);
14535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        else {
1454f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this);
14555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchDest.link(this);
14565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
14575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14582bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), countRegister);
14595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        branch32(NotEqual, countRegister, index).linkTo(loop, this);
14605f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
14615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateCharacterClassGreedy(TermGenerationState& state)
14635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
14645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
14655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID countRegister = regT1;
14665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
1467f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
14682bde8e466a4451c7319e3a072d118917957d6554Steve Block        move(TrustedImm32(0), countRegister);
14695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList failures;
14715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label loop(this);
14725f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        failures.append(atEndOfInput());
14735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1474f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.invert()) {
14755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            readCharacter(state.inputOffset(), character);
14765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchCharacterClass(character, failures, term.characterClass);
14775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
14785f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            JumpList matchDest;
14795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            readCharacter(state.inputOffset(), character);
14805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchCharacterClass(character, matchDest, term.characterClass);
14815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            failures.append(jump());
14825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchDest.link(this);
14835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
14845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14852bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), countRegister);
14862bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), index);
1487f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.quantityCount != quantifyInfinite) {
1488dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block            branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
14896c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen            failures.append(jump());
14906c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen        } else
1491dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block            jump(loop);
1492dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block
14935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label backtrackBegin(this);
14945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        loadFromFrame(term.frameLocation, countRegister);
1495f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
14962bde8e466a4451c7319e3a072d118917957d6554Steve Block        sub32(TrustedImm32(1), countRegister);
14972bde8e466a4451c7319e3a072d118917957d6554Steve Block        sub32(TrustedImm32(1), index);
14985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
14995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        failures.link(this);
15005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        storeToFrame(countRegister, term.frameLocation);
15025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1503f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.setBacktrackLabel(backtrackBegin);
15045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
15055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateCharacterClassNonGreedy(TermGenerationState& state)
15075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
15085f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID character = regT0;
15095f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID countRegister = regT1;
15105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
1511f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
15122bde8e466a4451c7319e3a072d118917957d6554Steve Block        move(TrustedImm32(0), countRegister);
15135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Jump firstTimeDoNothing = jump();
15155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label hardFail(this);
15175f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        sub32(countRegister, index);
1518f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.jumpToBacktrack(this);
15195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        Label backtrackBegin(this);
15215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        loadFromFrame(term.frameLocation, countRegister);
15225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        atEndOfInput().linkTo(hardFail, this);
15245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
15255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList matchDest;
15275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        readCharacter(state.inputOffset(), character);
15285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        matchCharacterClass(character, matchDest, term.characterClass);
15295f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1530f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.invert())
15315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchDest.linkTo(hardFail, this);
15325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        else {
15335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            jump(hardFail);
15345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            matchDest.link(this);
15355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
15365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15372bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), countRegister);
15382bde8e466a4451c7319e3a072d118917957d6554Steve Block        add32(TrustedImm32(1), index);
15395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        firstTimeDoNothing.link(this);
15415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        storeToFrame(countRegister, term.frameLocation);
15425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1543f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        state.setBacktrackLabel(backtrackBegin);
15445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
15455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateParenthesesDisjunction(PatternTerm& parenthesesTerm, TermGenerationState& state, unsigned alternativeFrameLocation)
15475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
15485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        ASSERT((parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern) || (parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion));
15495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        ASSERT(parenthesesTerm.quantityCount == 1);
1550f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
15515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
15525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        unsigned preCheckedCount = ((parenthesesTerm.quantityType == QuantifierFixedCount) && (parenthesesTerm.type != PatternTerm::TypeParentheticalAssertion)) ? disjunction->m_minimumSize : 0;
15535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (disjunction->m_alternatives.size() == 1) {
15555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            state.resetAlternative();
15565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(state.alternativeValid());
15575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            PatternAlternative* alternative = state.alternative();
15585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            optimizeAlternative(alternative);
15595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15605f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            int countToCheck = alternative->m_minimumSize - preCheckedCount;
15615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (countToCheck) {
15625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                ASSERT((parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion) || (parenthesesTerm.quantityType != QuantifierFixedCount));
15635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                // FIXME: This is quite horrible.  The call to 'plantJumpToBacktrackIfExists'
15655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                // will be forced to always trampoline into here, just to decrement the index.
15665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                // Ick.
15675f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                Jump skip = jump();
15685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                Label backtrackBegin(this);
15705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                sub32(Imm32(countToCheck), index);
15715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                state.addBacktrackJump(jump());
1572f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
15735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                skip.link(this);
15745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1575f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.setBacktrackLabel(backtrackBegin);
15765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1577f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.jumpToBacktrack(this, jumpIfNoAvailableInput(countToCheck));
15785f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                state.checkedTotal += countToCheck;
15795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
15805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            for (state.resetTerm(); state.termValid(); state.nextTerm())
15825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                generateTerm(state);
15835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            state.checkedTotal -= countToCheck;
15855f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
15865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            JumpList successes;
1587f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            bool propogateBacktrack = false;
15885f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            // Save current state's paren jump list for use with each alternative
15902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            JumpList* outerJumpList = state.getJumpListToPriorParen();
15915f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative(), state.setJumpListToPriorParen(outerJumpList)) {
15935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                PatternAlternative* alternative = state.alternative();
15945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                optimizeAlternative(alternative);
15955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
15965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                ASSERT(alternative->m_minimumSize >= preCheckedCount);
15975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                int countToCheck = alternative->m_minimumSize - preCheckedCount;
15985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                if (countToCheck) {
15995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    state.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
16005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    state.checkedTotal += countToCheck;
16015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                }
16025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                for (state.resetTerm(); state.termValid(); state.nextTerm())
16045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    generateTerm(state);
16055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                // Matched an alternative.
16075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation);
1608f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1609f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (!state.isLastAlternative() || countToCheck)
1610f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    successes.append(jump());
16115f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16125f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                // Alternative did not match.
1613f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1614f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                // Do we have a backtrack destination?
1615f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                //    if so, link the data label to it.
161665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch                state.linkDataLabelToBacktrackIfExists(this, dataLabel);
1617f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1618f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                if (!state.isLastAlternative() || countToCheck)
1619f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    state.linkAlternativeBacktracks(this);
16205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                if (countToCheck) {
16225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    sub32(Imm32(countToCheck), index);
16235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    state.checkedTotal -= countToCheck;
1624f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                } else if (state.isLastAlternative())
1625f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    propogateBacktrack = true;
16265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
16275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // We fall through to here when the last alternative fails.
16285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // Add a backtrack out of here for the parenthese handling code to link up.
1629f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (!propogateBacktrack)
1630f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.addBacktrackJump(jump());
16315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1632f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // Save address on stack for the parens code to backtrack to, to retry the
16335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // next alternative.
1634f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.setBackTrackStackOffset(alternativeFrameLocation * sizeof(void*));
16355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            successes.link(this);
16375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
16385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
16395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateParenthesesSingle(TermGenerationState& state)
16415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
16425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        const RegisterID indexTemporary = regT0;
16435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
16445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternDisjunction* disjunction = term.parentheses.disjunction;
16455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        ASSERT(term.quantityCount == 1);
16465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16474576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang        unsigned preCheckedCount = (term.quantityType == QuantifierFixedCount) ? disjunction->m_minimumSize : 0;
16485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        unsigned parenthesesFrameLocation = term.frameLocation;
16505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        unsigned alternativeFrameLocation = parenthesesFrameLocation;
16515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (term.quantityType != QuantifierFixedCount)
165265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch            alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
16535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        // optimized case - no capture & no quantifier can be handled in a light-weight manner.
1655f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (!term.capture() && (term.quantityType == QuantifierFixedCount)) {
1656f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_expressionState.incrementParenNestingLevel();
1657f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
16585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
16592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block
16602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            // Use the current state's jump list for the nested parentheses.
16612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            parenthesesState.setJumpListToPriorParen(state.getJumpListToPriorParen());
1662ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch
16635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
16645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // this expects that any backtracks back out of the parentheses will be in the
1665f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // parenthesesState's m_backTrackJumps vector, and that if they need backtracking
1666f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // they will have set an entry point on the parenthesesState's m_backtrackLabel.
1667f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            BacktrackDestination& parenthesesBacktrack = parenthesesState.getBacktrackDestination();
1668ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch            BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
1669ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch
1670f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.propagateBacktrackingFrom(this, parenthesesBacktrack);
1671ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch            stateBacktrack.propagateBacktrackToLabel(parenthesesBacktrack);
1672f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
16732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            state.setJumpListToPriorParen(parenthesesState.getJumpListToPriorParen());
16742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block
1675f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_expressionState.decrementParenNestingLevel();
16765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
16775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            Jump nonGreedySkipParentheses;
16785f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            Label nonGreedyTryParentheses;
16795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (term.quantityType == QuantifierGreedy)
16804576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                storeToFrame(index, parenthesesFrameLocation);
16815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            else if (term.quantityType == QuantifierNonGreedy) {
16822bde8e466a4451c7319e3a072d118917957d6554Steve Block                storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
16835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                nonGreedySkipParentheses = jump();
16845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                nonGreedyTryParentheses = label();
16854576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                storeToFrame(index, parenthesesFrameLocation);
16865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
16875f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16885f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // store the match start index
1689f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (term.capture()) {
16905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                int inputOffset = state.inputOffset() - preCheckedCount;
16915f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                if (inputOffset) {
16925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    move(index, indexTemporary);
16935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    add32(Imm32(inputOffset), indexTemporary);
16945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    store32(indexTemporary, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
16955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                } else
16965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
16975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
16985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
16992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getJumpListToPriorParen());
17005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1701f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_expressionState.incrementParenNestingLevel();
17025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1703f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
17045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1705f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // Save the parenthesesTail for backtracking from nested parens to this one.
17062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            parenthesesState.setJumpListToPriorParen(&parenthesesTail->m_withinBacktrackJumps);
17075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1708f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // generate the body of the parentheses
1709f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
17105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1711f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            // For non-fixed counts, backtrack if we didn't match anything.
1712f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (term.quantityType != QuantifierFixedCount)
1713f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                parenthesesTail->addAfterParenJump(branch32(Equal, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*)))));
17144576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang
17154576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            // store the match end index
1716f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (term.capture()) {
17174576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                int inputOffset = state.inputOffset();
17184576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                if (inputOffset) {
17194576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                    move(index, indexTemporary);
17204576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                    add32(Imm32(state.inputOffset()), indexTemporary);
17214576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                    store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
17224576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                } else
17234576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                    store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
17244576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            }
1725f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1726f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            m_expressionState.decrementParenNestingLevel();
1727f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1728f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label());
1729f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
17302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block            state.setJumpListToPriorParen(&parenthesesTail->m_afterBacktrackJumps);
17312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block
1732f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            parenthesesState.getBacktrackDestination().clear();
1733f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1734f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (term.quantityType == QuantifierNonGreedy)
1735f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                nonGreedySkipParentheses.link(this);
17365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
17375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
17385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
17395af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke    void generateParenthesesGreedyNoBacktrack(TermGenerationState& state)
17405af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke    {
17415af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        PatternTerm& parenthesesTerm = state.term();
17425af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
17435af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        ASSERT(parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern);
17445af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        ASSERT(parenthesesTerm.quantityCount != 1); // Handled by generateParenthesesSingle.
17455af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
17465af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        TermGenerationState parenthesesState(disjunction, state.checkedTotal);
17475af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
17485af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        Label matchAgain(this);
1749db14019a23d96bc8a444b6576a5da8bd1cfbc8b0Steve Block
1750db14019a23d96bc8a444b6576a5da8bd1cfbc8b0Steve Block        storeToFrame(index, parenthesesTerm.frameLocation); // Save the current index to check for zero len matches later.
1751db14019a23d96bc8a444b6576a5da8bd1cfbc8b0Steve Block
17525af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        for (parenthesesState.resetAlternative(); parenthesesState.alternativeValid(); parenthesesState.nextAlternative()) {
17535af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
17545af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            PatternAlternative* alternative = parenthesesState.alternative();
17555af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            optimizeAlternative(alternative);
17565af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
17575af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            int countToCheck = alternative->m_minimumSize;
17585af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            if (countToCheck) {
17595af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke                parenthesesState.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
17605af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke                parenthesesState.checkedTotal += countToCheck;
17615af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            }
17625af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
17635af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            for (parenthesesState.resetTerm(); parenthesesState.termValid(); parenthesesState.nextTerm())
17645af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke                generateTerm(parenthesesState);
17655af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
1766db14019a23d96bc8a444b6576a5da8bd1cfbc8b0Steve Block            // If we get here, we matched! If the index advanced then try to match more since limit isn't supported yet.
17674576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesTerm.frameLocation * sizeof(void*))), matchAgain);
17684576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang
17694576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            // If we get here we matched, but we matched "" - cannot accept this alternative as is, so either backtrack,
17704576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            // or fall through to try the next alternative if no backtrack is available.
17714576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            parenthesesState.plantJumpToBacktrackIfExists(this);
1772db14019a23d96bc8a444b6576a5da8bd1cfbc8b0Steve Block
17735af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            parenthesesState.linkAlternativeBacktracks(this);
1774f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
17755af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop.
17765af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
17775af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            if (countToCheck) {
17785af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke                sub32(Imm32(countToCheck), index);
17795af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke                parenthesesState.checkedTotal -= countToCheck;
17805af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            }
17815af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        }
17825af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
17835af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        // If the last alternative falls through to here, we have a failed match...
17845af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        // Which means that we match whatever we have matched up to this point (even if nothing).
17855af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke    }
17865af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
17875f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateParentheticalAssertion(TermGenerationState& state)
17885f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
17895f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
17905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternDisjunction* disjunction = term.parentheses.disjunction;
17915f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        ASSERT(term.quantityCount == 1);
17925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        ASSERT(term.quantityType == QuantifierFixedCount);
17935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
17945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        unsigned parenthesesFrameLocation = term.frameLocation;
179565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch        unsigned alternativeFrameLocation = parenthesesFrameLocation + YarrStackSpaceForBackTrackInfoParentheticalAssertion;
17965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
17975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;
17985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
1799f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        if (term.invert()) {
18005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // Inverted case
18015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            storeToFrame(index, parenthesesFrameLocation);
18025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            state.checkedTotal -= countCheckedAfterAssertion;
18045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (countCheckedAfterAssertion)
18055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                sub32(Imm32(countCheckedAfterAssertion), index);
18065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
18085f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
18095f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // Success! - which means - Fail!
18105f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            loadFromFrame(parenthesesFrameLocation, index);
1811f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this);
18125f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // And fail means success.
18145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            parenthesesState.linkAlternativeBacktracks(this);
1815f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
18165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            loadFromFrame(parenthesesFrameLocation, index);
18175f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            state.checkedTotal += countCheckedAfterAssertion;
18195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        } else {
18205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // Normal case
18215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            storeToFrame(index, parenthesesFrameLocation);
18225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            state.checkedTotal -= countCheckedAfterAssertion;
18245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (countCheckedAfterAssertion)
18255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                sub32(Imm32(countCheckedAfterAssertion), index);
18265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
18285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
18295f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // Success! - which means - Success!
18305f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            loadFromFrame(parenthesesFrameLocation, index);
18315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            Jump success = jump();
18325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            parenthesesState.linkAlternativeBacktracks(this);
1834f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
18355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            loadFromFrame(parenthesesFrameLocation, index);
1836f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.jumpToBacktrack(this);
18375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18385f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            success.link(this);
18395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            state.checkedTotal += countCheckedAfterAssertion;
18415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
18425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
18435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateTerm(TermGenerationState& state)
18455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
18465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        PatternTerm& term = state.term();
18475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        switch (term.type) {
18495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypeAssertionBOL:
18505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            generateAssertionBOL(state);
18515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
1852f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
18535f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypeAssertionEOL:
18545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            generateAssertionEOL(state);
18555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
1856f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
18575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypeAssertionWordBoundary:
18585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            generateAssertionWordBoundary(state);
18595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
1860f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
18615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypePatternCharacter:
18625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            switch (term.quantityType) {
18635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            case QuantifierFixedCount:
18645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                if (term.quantityCount == 1) {
18655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    if (state.isSinglePatternCharacterLookaheadTerm() && (state.lookaheadTerm().inputPosition == (term.inputPosition + 1))) {
18665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                        generatePatternCharacterPair(state);
18675f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                        state.nextTerm();
18685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    } else
18695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                        generatePatternCharacterSingle(state);
18705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                } else
18715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    generatePatternCharacterFixed(state);
18725f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                break;
18735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            case QuantifierGreedy:
18745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                generatePatternCharacterGreedy(state);
18755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                break;
18765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            case QuantifierNonGreedy:
18775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                generatePatternCharacterNonGreedy(state);
18785f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                break;
18795f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
18805f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
18815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypeCharacterClass:
18835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            switch (term.quantityType) {
18845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            case QuantifierFixedCount:
18855f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                if (term.quantityCount == 1)
18865f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    generateCharacterClassSingle(state);
18875f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                else
18885f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    generateCharacterClassFixed(state);
18895f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                break;
18905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            case QuantifierGreedy:
18915f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                generateCharacterClassGreedy(state);
18925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                break;
18935f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            case QuantifierNonGreedy:
18945f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                generateCharacterClassNonGreedy(state);
18955f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                break;
18965f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
18975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
18985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
18995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypeBackReference:
19005af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke            m_shouldFallBack = true;
19015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
19025f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypeForwardReference:
19045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
19055f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19065f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypeParenthesesSubpattern:
19074576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            if (term.quantityCount == 1 && !term.parentheses.isCopy)
19085af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke                generateParenthesesSingle(state);
19094576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            else if (term.parentheses.isTerminal)
19104576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                generateParenthesesGreedyNoBacktrack(state);
19114576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang            else
19124576aa36e9a9671459299c7963ac95aa94beaea9Shimeng (Simon) Wang                m_shouldFallBack = true;
19135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
19145f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19155f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        case PatternTerm::TypeParentheticalAssertion:
19165f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            generateParentheticalAssertion(state);
19175f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            break;
19185f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
19195f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
19205f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19215f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateDisjunction(PatternDisjunction* disjunction)
19225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
19235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        TermGenerationState state(disjunction, 0);
19245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        state.resetAlternative();
19255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        // check availability for the next alternative
19275f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        int countCheckedForCurrentAlternative = 0;
19285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        int countToCheckForFirstAlternative = 0;
19295f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        bool hasShorterAlternatives = false;
193068513a70bcd92384395513322f1b801e7bf9c729Steve Block        bool setRepeatAlternativeLabels = false;
19315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        JumpList notEnoughInputForPreviousAlternative;
193268513a70bcd92384395513322f1b801e7bf9c729Steve Block        Label firstAlternative;
193368513a70bcd92384395513322f1b801e7bf9c729Steve Block        Label firstAlternativeInputChecked;
19345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
193568513a70bcd92384395513322f1b801e7bf9c729Steve Block        // The label 'firstAlternative' is used to plant a check to see if there is
193668513a70bcd92384395513322f1b801e7bf9c729Steve Block        // sufficient input available to run the first repeating alternative.
193768513a70bcd92384395513322f1b801e7bf9c729Steve Block        // The label 'firstAlternativeInputChecked' will jump directly to matching
193868513a70bcd92384395513322f1b801e7bf9c729Steve Block        // the first repeating alternative having skipped this check.
1939f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
19405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (state.alternativeValid()) {
19415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            PatternAlternative* alternative = state.alternative();
194268513a70bcd92384395513322f1b801e7bf9c729Steve Block            if (!alternative->onceThrough()) {
194368513a70bcd92384395513322f1b801e7bf9c729Steve Block                firstAlternative = Label(this);
194468513a70bcd92384395513322f1b801e7bf9c729Steve Block                setRepeatAlternativeLabels = true;
194568513a70bcd92384395513322f1b801e7bf9c729Steve Block            }
19465f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            countToCheckForFirstAlternative = alternative->m_minimumSize;
19475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            state.checkedTotal += countToCheckForFirstAlternative;
19485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (countToCheckForFirstAlternative)
19495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
19505f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
19515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
19525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
195368513a70bcd92384395513322f1b801e7bf9c729Steve Block        if (setRepeatAlternativeLabels)
195468513a70bcd92384395513322f1b801e7bf9c729Steve Block            firstAlternativeInputChecked = Label(this);
19555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19565f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        while (state.alternativeValid()) {
19575f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            PatternAlternative* alternative = state.alternative();
19585f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            optimizeAlternative(alternative);
19595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
196068513a70bcd92384395513322f1b801e7bf9c729Steve Block            // Track whether any alternatives are shorter than the first one.
196168513a70bcd92384395513322f1b801e7bf9c729Steve Block            if (!alternative->onceThrough())
196268513a70bcd92384395513322f1b801e7bf9c729Steve Block                hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative);
1963f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
19645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            for (state.resetTerm(); state.termValid(); state.nextTerm())
19655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                generateTerm(state);
19665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19675f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // If we get here, the alternative matched.
19685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (m_pattern.m_body->m_callFrameSize)
19695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
197006ea8e899e48f1f2f396b70e63fae369f2f23232Kristian Monsen
19715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            ASSERT(index != returnRegister);
19725f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (m_pattern.m_body->m_hasFixedSize) {
19735f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                move(index, returnRegister);
19745f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                if (alternative->m_minimumSize)
19755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    sub32(Imm32(alternative->m_minimumSize), returnRegister);
197606ea8e899e48f1f2f396b70e63fae369f2f23232Kristian Monsen
197706ea8e899e48f1f2f396b70e63fae369f2f23232Kristian Monsen                store32(returnRegister, output);
19785f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            } else
197906ea8e899e48f1f2f396b70e63fae369f2f23232Kristian Monsen                load32(Address(output), returnRegister);
198006ea8e899e48f1f2f396b70e63fae369f2f23232Kristian Monsen
19815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            store32(index, Address(output, 4));
19825f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            generateReturn();
19845f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19855f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            state.nextAlternative();
1986f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            if (alternative->onceThrough() && state.alternativeValid())
1987f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.clearBacktrack();
19885f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
19895f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            // if there are any more alternatives, plant the check for input before looping.
19905f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            if (state.alternativeValid()) {
19912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block                state.setJumpListToPriorParen(0);
19925f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                PatternAlternative* nextAlternative = state.alternative();
199368513a70bcd92384395513322f1b801e7bf9c729Steve Block                if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
199468513a70bcd92384395513322f1b801e7bf9c729Steve Block                    // We have handled non-repeating alternatives, jump to next iteration
199568513a70bcd92384395513322f1b801e7bf9c729Steve Block                    // and loop over repeating alternatives.
1996f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                    state.jumpToBacktrack(this);
1997f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
1998bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    countToCheckForFirstAlternative = nextAlternative->m_minimumSize;
1999f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
20005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    // If we get here, there the last input checked failed.
20015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    notEnoughInputForPreviousAlternative.link(this);
2002f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
20035f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian                    state.linkAlternativeBacktracks(this);
20045f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2005bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    // Back up to start the looping alternatives.
2006bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    if (countCheckedForCurrentAlternative)
2007bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        sub32(Imm32(countCheckedForCurrentAlternative), index);
2008f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2009bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    firstAlternative = Label(this);
2010f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2011bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    state.checkedTotal = countToCheckForFirstAlternative;
2012bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    if (countToCheckForFirstAlternative)
2013bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
2014f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2015bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
2016f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
201768513a70bcd92384395513322f1b801e7bf9c729Steve Block                    firstAlternativeInputChecked = Label(this);
2018bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen
2019bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    setRepeatAlternativeLabels = true;
2020bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                } else {
2021bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    int countToCheckForNextAlternative = nextAlternative->m_minimumSize;
2022f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2023bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one.
2024bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // If we get here, then the last input checked failed.
2025bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        notEnoughInputForPreviousAlternative.link(this);
2026f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2027bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // Check if sufficent input available to run the next alternative
2028bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
2029bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // We are now in the correct state to enter the next alternative; this add is only required
2030bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // to mirror and revert operation of the sub32, just below.
2031bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
2032f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2033bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // If we get here, then the last input checked passed.
2034bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        state.linkAlternativeBacktracks(this);
2035f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2036bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // No need to check if we can run the next alternative, since it is shorter -
2037bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // just update index.
2038bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
2039bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one.
2040bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // If we get here, then the last input checked failed.
2041bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // If there is insufficient input to run the current alternative, and the next alternative is longer,
2042bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // then there is definitely not enough input to run it - don't even check. Just adjust index, as if
2043bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // we had checked.
2044bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        notEnoughInputForPreviousAlternative.link(this);
2045bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index);
2046bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        notEnoughInputForPreviousAlternative.append(jump());
2047f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2048bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // The next alternative is longer than the current one; check the difference.
2049bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        state.linkAlternativeBacktracks(this);
2050f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2051bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
2052bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    } else { // CASE 3: Both alternatives are the same length.
2053bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative);
2054f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2055bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // If the next alterative is the same length as this one, then no need to check the input -
2056bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // if there was sufficent input to run the current alternative then there is sufficient
2057bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        // input to run the next one; if not, there isn't.
2058bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                        state.linkAlternativeBacktracks(this);
2059bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    }
2060bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    state.checkedTotal -= countCheckedForCurrentAlternative;
2061bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    countCheckedForCurrentAlternative = countToCheckForNextAlternative;
2062bec39347bb3bb5bf1187ccaf471d26247f28b585Kristian Monsen                    state.checkedTotal += countCheckedForCurrentAlternative;
206368513a70bcd92384395513322f1b801e7bf9c729Steve Block                }
20645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            }
20655f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
2066f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
20675f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        // If we get here, all Alternatives failed...
20685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
20695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        state.checkedTotal -= countCheckedForCurrentAlternative;
20705f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
207168513a70bcd92384395513322f1b801e7bf9c729Steve Block        if (!setRepeatAlternativeLabels) {
207268513a70bcd92384395513322f1b801e7bf9c729Steve Block            // If there are no alternatives that need repeating (all are marked 'onceThrough') then just link
207368513a70bcd92384395513322f1b801e7bf9c729Steve Block            // the match failures to this point, and fall through to the return below.
2074f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            state.linkAlternativeBacktracks(this, true);
2075f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
207668513a70bcd92384395513322f1b801e7bf9c729Steve Block            notEnoughInputForPreviousAlternative.link(this);
207768513a70bcd92384395513322f1b801e7bf9c729Steve Block        } else {
207868513a70bcd92384395513322f1b801e7bf9c729Steve Block            // How much more input need there be to be able to retry from the first alternative?
207968513a70bcd92384395513322f1b801e7bf9c729Steve Block            // examples:
208068513a70bcd92384395513322f1b801e7bf9c729Steve Block            //   /yarr_jit/ or /wrec|pcre/
208168513a70bcd92384395513322f1b801e7bf9c729Steve Block            //     In these examples we need check for one more input before looping.
208268513a70bcd92384395513322f1b801e7bf9c729Steve Block            //   /yarr_jit|pcre/
208368513a70bcd92384395513322f1b801e7bf9c729Steve Block            //     In this case we need check for 5 more input to loop (+4 to allow for the first alterative
208468513a70bcd92384395513322f1b801e7bf9c729Steve Block            //     being four longer than the last alternative checked, and another +1 to effectively move
208568513a70bcd92384395513322f1b801e7bf9c729Steve Block            //     the start position along by one).
208668513a70bcd92384395513322f1b801e7bf9c729Steve Block            //   /yarr|rules/ or /wrec|notsomuch/
208768513a70bcd92384395513322f1b801e7bf9c729Steve Block            //     In these examples, provided that there was sufficient input to have just been matching for
208868513a70bcd92384395513322f1b801e7bf9c729Steve Block            //     the second alternative we can loop without checking for available input (since the second
208968513a70bcd92384395513322f1b801e7bf9c729Steve Block            //     alternative is longer than the first).  In the latter example we need to decrement index
209068513a70bcd92384395513322f1b801e7bf9c729Steve Block            //     (by 4) so the start position is only progressed by 1 from the last iteration.
209168513a70bcd92384395513322f1b801e7bf9c729Steve Block            int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1;
209268513a70bcd92384395513322f1b801e7bf9c729Steve Block
209368513a70bcd92384395513322f1b801e7bf9c729Steve Block            // First, deal with the cases where there was sufficient input to try the last alternative.
209468513a70bcd92384395513322f1b801e7bf9c729Steve Block            if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below.
2095f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.linkAlternativeBacktracks(this, true);
209668513a70bcd92384395513322f1b801e7bf9c729Steve Block            else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop!
2097f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.linkAlternativeBacktracksTo(this, firstAlternativeInputChecked, true);
209868513a70bcd92384395513322f1b801e7bf9c729Steve Block            else { // no need to check the input, but we do have some bookkeeping to do first.
2099f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch                state.linkAlternativeBacktracks(this, true);
21005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
210168513a70bcd92384395513322f1b801e7bf9c729Steve Block                // Where necessary update our preserved start position.
210268513a70bcd92384395513322f1b801e7bf9c729Steve Block                if (!m_pattern.m_body->m_hasFixedSize) {
210368513a70bcd92384395513322f1b801e7bf9c729Steve Block                    move(index, regT0);
210468513a70bcd92384395513322f1b801e7bf9c729Steve Block                    sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
210568513a70bcd92384395513322f1b801e7bf9c729Steve Block                    store32(regT0, Address(output));
210668513a70bcd92384395513322f1b801e7bf9c729Steve Block                }
21075f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
210868513a70bcd92384395513322f1b801e7bf9c729Steve Block                // Update index if necessary, and loop (without checking).
210968513a70bcd92384395513322f1b801e7bf9c729Steve Block                if (incrementForNextIter)
211068513a70bcd92384395513322f1b801e7bf9c729Steve Block                    add32(Imm32(incrementForNextIter), index);
211168513a70bcd92384395513322f1b801e7bf9c729Steve Block                jump().linkTo(firstAlternativeInputChecked, this);
211268513a70bcd92384395513322f1b801e7bf9c729Steve Block            }
21135f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
211468513a70bcd92384395513322f1b801e7bf9c729Steve Block            notEnoughInputForPreviousAlternative.link(this);
211568513a70bcd92384395513322f1b801e7bf9c729Steve Block            // Update our idea of the start position, if we're tracking this.
211668513a70bcd92384395513322f1b801e7bf9c729Steve Block            if (!m_pattern.m_body->m_hasFixedSize) {
211768513a70bcd92384395513322f1b801e7bf9c729Steve Block                if (countCheckedForCurrentAlternative - 1) {
211868513a70bcd92384395513322f1b801e7bf9c729Steve Block                    move(index, regT0);
211968513a70bcd92384395513322f1b801e7bf9c729Steve Block                    sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
212068513a70bcd92384395513322f1b801e7bf9c729Steve Block                    store32(regT0, Address(output));
212168513a70bcd92384395513322f1b801e7bf9c729Steve Block                } else
212268513a70bcd92384395513322f1b801e7bf9c729Steve Block                    store32(index, Address(output));
212368513a70bcd92384395513322f1b801e7bf9c729Steve Block            }
2124f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
212568513a70bcd92384395513322f1b801e7bf9c729Steve Block            // Check if there is sufficent input to run the first alternative again.
212668513a70bcd92384395513322f1b801e7bf9c729Steve Block            jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this);
212768513a70bcd92384395513322f1b801e7bf9c729Steve Block            // No - insufficent input to run the first alteranative, are there any other alternatives we
212868513a70bcd92384395513322f1b801e7bf9c729Steve Block            // might need to check?  If so, the last check will have left the index incremented by
212968513a70bcd92384395513322f1b801e7bf9c729Steve Block            // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative
213068513a70bcd92384395513322f1b801e7bf9c729Steve Block            // LESS input is available, to have the effect of just progressing the start position by 1
213168513a70bcd92384395513322f1b801e7bf9c729Steve Block            // from the last iteration.  If this check passes we can just jump up to the check associated
213268513a70bcd92384395513322f1b801e7bf9c729Steve Block            // with the first alternative in the loop.  This is a bit sad, since we'll end up trying the
213368513a70bcd92384395513322f1b801e7bf9c729Steve Block            // first alternative again, and this check will fail (otherwise the check planted just above
213468513a70bcd92384395513322f1b801e7bf9c729Steve Block            // here would have passed).  This is a bit sad, however it saves trying to do something more
213568513a70bcd92384395513322f1b801e7bf9c729Steve Block            // complex here in compilation, and in the common case we should end up coallescing the checks.
213668513a70bcd92384395513322f1b801e7bf9c729Steve Block            //
213768513a70bcd92384395513322f1b801e7bf9c729Steve Block            // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least
213868513a70bcd92384395513322f1b801e7bf9c729Steve Block            // of the minimum-alternative-lengths.  E.g. if I have two alternatives of length 200 and 150,
213968513a70bcd92384395513322f1b801e7bf9c729Steve Block            // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there
214068513a70bcd92384395513322f1b801e7bf9c729Steve Block            // is sufficient input to run either alternative (constantly failing).  If there had been only
214168513a70bcd92384395513322f1b801e7bf9c729Steve Block            // one alternative, or if the shorter alternative had come first, we would have terminated
214268513a70bcd92384395513322f1b801e7bf9c729Steve Block            // immediately. :-/
214368513a70bcd92384395513322f1b801e7bf9c729Steve Block            if (hasShorterAlternatives)
214468513a70bcd92384395513322f1b801e7bf9c729Steve Block                jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this);
214568513a70bcd92384395513322f1b801e7bf9c729Steve Block            // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true,
214668513a70bcd92384395513322f1b801e7bf9c729Steve Block            // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ...
214768513a70bcd92384395513322f1b801e7bf9c729Steve Block            // but since we're about to return a failure this doesn't really matter!)
21485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        }
21495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
215006ea8e899e48f1f2f396b70e63fae369f2f23232Kristian Monsen        if (m_pattern.m_body->m_callFrameSize)
215106ea8e899e48f1f2f396b70e63fae369f2f23232Kristian Monsen            addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
21525f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
21532bde8e466a4451c7319e3a072d118917957d6554Steve Block        move(TrustedImm32(-1), returnRegister);
21545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
21555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        generateReturn();
2156f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
2157f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        m_expressionState.emitParenthesesTail(this);
2158f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        m_expressionState.emitIndirectJumpTable(this);
2159f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        m_expressionState.linkToNextIteration(this);
21605f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
21615f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
21625f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateEnter()
21635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2164d0825bca7fe65beaee391d30da42e937db621564Steve Block#if CPU(X86_64)
2165231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(X86Registers::ebp);
2166231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        move(stackPointerRegister, X86Registers::ebp);
2167231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(X86Registers::ebx);
2168d0825bca7fe65beaee391d30da42e937db621564Steve Block#elif CPU(X86)
2169231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(X86Registers::ebp);
2170231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        move(stackPointerRegister, X86Registers::ebp);
21715f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
2172231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(X86Registers::ebx);
2173231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(X86Registers::edi);
2174231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(X86Registers::esi);
21755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        // load output into edi (2 = saved ebp + return address).
21765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    #if COMPILER(MSVC)
2177231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
2178231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
2179231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
2180231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
21815f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    #else
2182231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
21835f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    #endif
2184d0825bca7fe65beaee391d30da42e937db621564Steve Block#elif CPU(ARM)
2185231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(ARMRegisters::r4);
2186231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(ARMRegisters::r5);
2187231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        push(ARMRegisters::r6);
2188f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick#if CPU(ARM_TRADITIONAL)
2189f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick        push(ARMRegisters::r8); // scratch register
2190f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick#endif
2191231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        move(ARMRegisters::r3, output);
21922daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch#elif CPU(SH4)
21932daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch        push(SH4Registers::r11);
21942daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch        push(SH4Registers::r13);
2195dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block#elif CPU(MIPS)
2196dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block        // Do nothing.
21975f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian#endif
21985f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
21995f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
22005f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generateReturn()
22015f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
2202d0825bca7fe65beaee391d30da42e937db621564Steve Block#if CPU(X86_64)
2203231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(X86Registers::ebx);
2204231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(X86Registers::ebp);
2205d0825bca7fe65beaee391d30da42e937db621564Steve Block#elif CPU(X86)
2206231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(X86Registers::esi);
2207231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(X86Registers::edi);
2208231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(X86Registers::ebx);
2209231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(X86Registers::ebp);
2210d0825bca7fe65beaee391d30da42e937db621564Steve Block#elif CPU(ARM)
2211f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick#if CPU(ARM_TRADITIONAL)
2212f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick        pop(ARMRegisters::r8); // scratch register
2213f486d19d62f1bc33246748b14b14a9dfa617b57fIain Merrick#endif
2214231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(ARMRegisters::r6);
2215231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(ARMRegisters::r5);
2216231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block        pop(ARMRegisters::r4);
22172daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch#elif CPU(SH4)
22182daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch        pop(SH4Registers::r13);
22192daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch        pop(SH4Registers::r11);
2220dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block#elif CPU(MIPS)
2221dcc8cf2e65d1aa555cce12431a16547e66b469eeSteve Block        // Do nothing
22225f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian#endif
22235f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        ret();
22245f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
22255f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
22265f1ab04193ad0130ca8204aadaceae083aca9881Feng Qianpublic:
222765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch    YarrGenerator(YarrPattern& pattern)
22285f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        : m_pattern(pattern)
22295af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke        , m_shouldFallBack(false)
22305f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
22315f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
22325f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
22335f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    void generate()
22345f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
22355f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        generateEnter();
22365f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
22375f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (!m_pattern.m_body->m_hasFixedSize)
223806ea8e899e48f1f2f396b70e63fae369f2f23232Kristian Monsen            store32(index, Address(output));
22395f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
22405f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        if (m_pattern.m_body->m_callFrameSize)
22415f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian            subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
22425f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
22435f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        generateDisjunction(m_pattern.m_body);
22445f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    }
22455f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
224665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch    void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject)
22475f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian    {
22485f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        generate();
22495f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2250f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        LinkBuffer patchBuffer(this, globalData->regexAllocator.poolForSize(size()), 0);
22515f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
2252f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        for (unsigned i = 0; i < m_expressionState.m_backtrackRecords.size(); ++i)
2253f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch            patchBuffer.patch(m_expressionState.m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_expressionState.m_backtrackRecords[i].backtrackLocation));
22545f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
22555f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian        jitObject.set(patchBuffer.finalizeCode());
2256f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch        jitObject.setFallBack(m_shouldFallBack);
22575af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke    }
22585af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke
22595f1ab04193ad0130ca8204aadaceae083aca9881Feng Qianprivate:
226065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch    YarrPattern& m_pattern;
22615af96e2c7b73ebc627c6894727826a7576d31758Leon Clarke    bool m_shouldFallBack;
2262f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch    GenerationState m_expressionState;
22635f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian};
22645f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
226565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochvoid jitCompile(YarrPattern& pattern, JSGlobalData* globalData, YarrCodeBlock& jitObject)
22665f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian{
226765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch    YarrGenerator(pattern).compile(globalData, jitObject);
22685f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian}
22695f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
227065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochint execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output)
227165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{
227265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch    return jitObject.execute(input, start, length, output);
227365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch}
2274f05b935882198ccf7d81675736e3aeb089c5113aBen Murdoch
22755f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian}}
22765f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian
22775f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian#endif
2278