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