| /* |
| * Copyright (C) 2009 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include "YarrJIT.h" |
| |
| #include "ASCIICType.h" |
| #include "LinkBuffer.h" |
| #include "Yarr.h" |
| |
| #if ENABLE(YARR_JIT) |
| |
| using namespace WTF; |
| |
| namespace JSC { namespace Yarr { |
| |
| class YarrGenerator : private MacroAssembler { |
| friend void jitCompile(JSGlobalData*, YarrCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline); |
| |
| #if CPU(ARM) |
| static const RegisterID input = ARMRegisters::r0; |
| static const RegisterID index = ARMRegisters::r1; |
| static const RegisterID length = ARMRegisters::r2; |
| static const RegisterID output = ARMRegisters::r4; |
| |
| static const RegisterID regT0 = ARMRegisters::r5; |
| static const RegisterID regT1 = ARMRegisters::r6; |
| |
| static const RegisterID returnRegister = ARMRegisters::r0; |
| #elif CPU(MIPS) |
| static const RegisterID input = MIPSRegisters::a0; |
| static const RegisterID index = MIPSRegisters::a1; |
| static const RegisterID length = MIPSRegisters::a2; |
| static const RegisterID output = MIPSRegisters::a3; |
| |
| static const RegisterID regT0 = MIPSRegisters::t4; |
| static const RegisterID regT1 = MIPSRegisters::t5; |
| |
| static const RegisterID returnRegister = MIPSRegisters::v0; |
| #elif CPU(SH4) |
| static const RegisterID input = SH4Registers::r4; |
| static const RegisterID index = SH4Registers::r5; |
| static const RegisterID length = SH4Registers::r6; |
| static const RegisterID output = SH4Registers::r7; |
| |
| static const RegisterID regT0 = SH4Registers::r0; |
| static const RegisterID regT1 = SH4Registers::r1; |
| |
| static const RegisterID returnRegister = SH4Registers::r0; |
| #elif CPU(X86) |
| static const RegisterID input = X86Registers::eax; |
| static const RegisterID index = X86Registers::edx; |
| static const RegisterID length = X86Registers::ecx; |
| static const RegisterID output = X86Registers::edi; |
| |
| static const RegisterID regT0 = X86Registers::ebx; |
| static const RegisterID regT1 = X86Registers::esi; |
| |
| static const RegisterID returnRegister = X86Registers::eax; |
| #elif CPU(X86_64) |
| static const RegisterID input = X86Registers::edi; |
| static const RegisterID index = X86Registers::esi; |
| static const RegisterID length = X86Registers::edx; |
| static const RegisterID output = X86Registers::ecx; |
| |
| static const RegisterID regT0 = X86Registers::eax; |
| static const RegisterID regT1 = X86Registers::ebx; |
| |
| static const RegisterID returnRegister = X86Registers::eax; |
| #endif |
| |
| void optimizeAlternative(PatternAlternative* alternative) |
| { |
| if (!alternative->m_terms.size()) |
| return; |
| |
| for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) { |
| PatternTerm& term = alternative->m_terms[i]; |
| PatternTerm& nextTerm = alternative->m_terms[i + 1]; |
| |
| if ((term.type == PatternTerm::TypeCharacterClass) |
| && (term.quantityType == QuantifierFixedCount) |
| && (nextTerm.type == PatternTerm::TypePatternCharacter) |
| && (nextTerm.quantityType == QuantifierFixedCount)) { |
| PatternTerm termCopy = term; |
| alternative->m_terms[i] = nextTerm; |
| alternative->m_terms[i + 1] = termCopy; |
| } |
| } |
| } |
| |
| void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount) |
| { |
| do { |
| // pick which range we're going to generate |
| int which = count >> 1; |
| char lo = ranges[which].begin; |
| char hi = ranges[which].end; |
| |
| // check if there are any ranges or matches below lo. If not, just jl to failure - |
| // if there is anything else to check, check that first, if it falls through jmp to failure. |
| if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) { |
| Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo)); |
| |
| // generate code for all ranges before this one |
| if (which) |
| matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount); |
| |
| while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) { |
| matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex]))); |
| ++*matchIndex; |
| } |
| failures.append(jump()); |
| |
| loOrAbove.link(this); |
| } else if (which) { |
| Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo)); |
| |
| matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount); |
| failures.append(jump()); |
| |
| loOrAbove.link(this); |
| } else |
| failures.append(branch32(LessThan, character, Imm32((unsigned short)lo))); |
| |
| while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi)) |
| ++*matchIndex; |
| |
| matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi))); |
| // fall through to here, the value is above hi. |
| |
| // shuffle along & loop around if there are any more matches to handle. |
| unsigned next = which + 1; |
| ranges += next; |
| count -= next; |
| } while (count); |
| } |
| |
| void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass) |
| { |
| if (charClass->m_table) { |
| ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table)); |
| matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry)); |
| return; |
| } |
| Jump unicodeFail; |
| if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) { |
| Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f)); |
| |
| if (charClass->m_matchesUnicode.size()) { |
| for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) { |
| UChar ch = charClass->m_matchesUnicode[i]; |
| matchDest.append(branch32(Equal, character, Imm32(ch))); |
| } |
| } |
| |
| if (charClass->m_rangesUnicode.size()) { |
| for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) { |
| UChar lo = charClass->m_rangesUnicode[i].begin; |
| UChar hi = charClass->m_rangesUnicode[i].end; |
| |
| Jump below = branch32(LessThan, character, Imm32(lo)); |
| matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi))); |
| below.link(this); |
| } |
| } |
| |
| unicodeFail = jump(); |
| isAscii.link(this); |
| } |
| |
| if (charClass->m_ranges.size()) { |
| unsigned matchIndex = 0; |
| JumpList failures; |
| matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size()); |
| while (matchIndex < charClass->m_matches.size()) |
| matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++]))); |
| |
| failures.link(this); |
| } else if (charClass->m_matches.size()) { |
| // optimization: gather 'a','A' etc back together, can mask & test once. |
| Vector<char> matchesAZaz; |
| |
| for (unsigned i = 0; i < charClass->m_matches.size(); ++i) { |
| char ch = charClass->m_matches[i]; |
| if (m_pattern.m_ignoreCase) { |
| if (isASCIILower(ch)) { |
| matchesAZaz.append(ch); |
| continue; |
| } |
| if (isASCIIUpper(ch)) |
| continue; |
| } |
| matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch))); |
| } |
| |
| if (unsigned countAZaz = matchesAZaz.size()) { |
| or32(TrustedImm32(32), character); |
| for (unsigned i = 0; i < countAZaz; ++i) |
| matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i]))); |
| } |
| } |
| |
| if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) |
| unicodeFail.link(this); |
| } |
| |
| // Jumps if input not available; will have (incorrectly) incremented already! |
| Jump jumpIfNoAvailableInput(unsigned countToCheck) |
| { |
| add32(Imm32(countToCheck), index); |
| return branch32(Above, index, length); |
| } |
| |
| Jump jumpIfAvailableInput(unsigned countToCheck) |
| { |
| add32(Imm32(countToCheck), index); |
| return branch32(BelowOrEqual, index, length); |
| } |
| |
| Jump checkInput() |
| { |
| return branch32(BelowOrEqual, index, length); |
| } |
| |
| Jump atEndOfInput() |
| { |
| return branch32(Equal, index, length); |
| } |
| |
| Jump notAtEndOfInput() |
| { |
| return branch32(NotEqual, index, length); |
| } |
| |
| Jump jumpIfCharEquals(UChar ch, int inputPosition) |
| { |
| return branch16(Equal, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch)); |
| } |
| |
| Jump jumpIfCharNotEquals(UChar ch, int inputPosition) |
| { |
| return branch16(NotEqual, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch)); |
| } |
| |
| void readCharacter(int inputPosition, RegisterID reg) |
| { |
| load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg); |
| } |
| |
| void storeToFrame(RegisterID reg, unsigned frameLocation) |
| { |
| poke(reg, frameLocation); |
| } |
| |
| void storeToFrame(TrustedImm32 imm, unsigned frameLocation) |
| { |
| poke(imm, frameLocation); |
| } |
| |
| DataLabelPtr storeToFrameWithPatch(unsigned frameLocation) |
| { |
| return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*))); |
| } |
| |
| void loadFromFrame(unsigned frameLocation, RegisterID reg) |
| { |
| peek(reg, frameLocation); |
| } |
| |
| void loadFromFrameAndJump(unsigned frameLocation) |
| { |
| jump(Address(stackPointerRegister, frameLocation * sizeof(void*))); |
| } |
| |
| struct IndirectJumpEntry { |
| IndirectJumpEntry(int32_t stackOffset) |
| : m_stackOffset(stackOffset) |
| { |
| } |
| |
| IndirectJumpEntry(int32_t stackOffset, Jump jump) |
| : m_stackOffset(stackOffset) |
| { |
| addJump(jump); |
| } |
| |
| IndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel) |
| : m_stackOffset(stackOffset) |
| { |
| addDataLabel(dataLabel); |
| } |
| |
| void addJump(Jump jump) |
| { |
| m_relJumps.append(jump); |
| } |
| |
| void addDataLabel(DataLabelPtr dataLabel) |
| { |
| m_dataLabelPtrVector.append(dataLabel); |
| } |
| |
| int32_t m_stackOffset; |
| JumpList m_relJumps; |
| Vector<DataLabelPtr, 16> m_dataLabelPtrVector; |
| }; |
| |
| struct AlternativeBacktrackRecord { |
| DataLabelPtr dataLabel; |
| Label backtrackLocation; |
| |
| AlternativeBacktrackRecord(DataLabelPtr dataLabel, Label backtrackLocation) |
| : dataLabel(dataLabel) |
| , backtrackLocation(backtrackLocation) |
| { |
| } |
| }; |
| |
| struct ParenthesesTail; |
| struct TermGenerationState; |
| |
| struct GenerationState { |
| typedef HashMap<int, IndirectJumpEntry*, WTF::IntHash<uint32_t>, UnsignedWithZeroKeyHashTraits<uint32_t> > IndirectJumpHashMap; |
| |
| GenerationState() |
| : m_parenNestingLevel(0) |
| { |
| } |
| |
| void addIndirectJumpEntry(int32_t stackOffset, Jump jump) |
| { |
| IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset); |
| |
| ASSERT(stackOffset >= 0); |
| |
| uint32_t offset = static_cast<uint32_t>(stackOffset); |
| |
| if (result == m_indirectJumpMap.end()) |
| m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, jump)); |
| else |
| result->second->addJump(jump); |
| } |
| |
| void addIndirectJumpEntry(int32_t stackOffset, JumpList jumps) |
| { |
| JumpList::JumpVector jumpVector = jumps.jumps(); |
| size_t size = jumpVector.size(); |
| for (size_t i = 0; i < size; ++i) |
| addIndirectJumpEntry(stackOffset, jumpVector[i]); |
| |
| jumps.empty(); |
| } |
| |
| void addIndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel) |
| { |
| IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset); |
| |
| ASSERT(stackOffset >= 0); |
| |
| uint32_t offset = static_cast<uint32_t>(stackOffset); |
| |
| if (result == m_indirectJumpMap.end()) |
| m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, dataLabel)); |
| else |
| result->second->addDataLabel(dataLabel); |
| } |
| |
| void emitIndirectJumpTable(MacroAssembler* masm) |
| { |
| for (IndirectJumpHashMap::iterator iter = m_indirectJumpMap.begin(); iter != m_indirectJumpMap.end(); ++iter) { |
| IndirectJumpEntry* indJumpEntry = iter->second; |
| size_t size = indJumpEntry->m_dataLabelPtrVector.size(); |
| if (size) { |
| // Link any associated DataLabelPtr's with indirect jump via label |
| Label hereLabel = masm->label(); |
| for (size_t i = 0; i < size; ++i) |
| m_backtrackRecords.append(AlternativeBacktrackRecord(indJumpEntry->m_dataLabelPtrVector[i], hereLabel)); |
| } |
| indJumpEntry->m_relJumps.link(masm); |
| masm->jump(Address(stackPointerRegister, indJumpEntry->m_stackOffset)); |
| delete indJumpEntry; |
| } |
| } |
| |
| void incrementParenNestingLevel() |
| { |
| ++m_parenNestingLevel; |
| } |
| |
| void decrementParenNestingLevel() |
| { |
| --m_parenNestingLevel; |
| } |
| |
| ParenthesesTail* addParenthesesTail(PatternTerm& term, JumpList* jumpListToPriorParen) |
| { |
| ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, jumpListToPriorParen); |
| m_parenTails.append(parenthesesTail); |
| m_parenTailsForIteration.append(parenthesesTail); |
| |
| return parenthesesTail; |
| } |
| |
| void emitParenthesesTail(YarrGenerator* generator) |
| { |
| unsigned vectorSize = m_parenTails.size(); |
| bool priorBacktrackFallThrough = false; |
| |
| // Emit in reverse order so parentTail N can fall through to N-1 |
| for (unsigned index = vectorSize; index > 0; --index) { |
| JumpList jumpsToNext; |
| priorBacktrackFallThrough = m_parenTails[index-1].get()->generateCode(generator, jumpsToNext, priorBacktrackFallThrough, index > 1); |
| if (index > 1) |
| jumpsToNext.linkTo(generator->label(), generator); |
| else |
| addJumpsToNextInteration(jumpsToNext); |
| } |
| m_parenTails.clear(); |
| } |
| |
| void addJumpToNextInteration(Jump jump) |
| { |
| m_jumpsToNextInteration.append(jump); |
| } |
| |
| void addJumpsToNextInteration(JumpList jumps) |
| { |
| m_jumpsToNextInteration.append(jumps); |
| } |
| |
| void addDataLabelToNextIteration(DataLabelPtr dataLabel) |
| { |
| m_dataPtrsToNextIteration.append(dataLabel); |
| } |
| |
| void linkToNextIteration(Label label) |
| { |
| m_nextIteration = label; |
| |
| for (unsigned i = 0; i < m_dataPtrsToNextIteration.size(); ++i) |
| m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataPtrsToNextIteration[i], m_nextIteration)); |
| |
| m_dataPtrsToNextIteration.clear(); |
| |
| for (unsigned i = 0; i < m_parenTailsForIteration.size(); ++i) |
| m_parenTailsForIteration[i]->setNextIteration(m_nextIteration); |
| |
| m_parenTailsForIteration.clear(); |
| } |
| |
| void linkToNextIteration(YarrGenerator* generator) |
| { |
| m_jumpsToNextInteration.linkTo(m_nextIteration, generator); |
| } |
| |
| int m_parenNestingLevel; |
| Vector<AlternativeBacktrackRecord> m_backtrackRecords; |
| IndirectJumpHashMap m_indirectJumpMap; |
| Label m_nextIteration; |
| Vector<OwnPtr<ParenthesesTail> > m_parenTails; |
| JumpList m_jumpsToNextInteration; |
| Vector<DataLabelPtr> m_dataPtrsToNextIteration; |
| Vector<ParenthesesTail*> m_parenTailsForIteration; |
| }; |
| |
| struct BacktrackDestination { |
| typedef enum { |
| NoBacktrack, |
| BacktrackLabel, |
| BacktrackStackOffset, |
| BacktrackJumpList, |
| BacktrackLinked |
| } BacktrackType; |
| |
| BacktrackDestination() |
| : m_backtrackType(NoBacktrack) |
| , m_backtrackToLabel(0) |
| , m_subDataLabelPtr(0) |
| , m_nextBacktrack(0) |
| , m_backtrackSourceLabel(0) |
| , m_backtrackSourceJumps(0) |
| { |
| } |
| |
| BacktrackDestination(int32_t stackOffset) |
| : m_backtrackType(BacktrackStackOffset) |
| , m_backtrackStackOffset(stackOffset) |
| , m_backtrackToLabel(0) |
| , m_subDataLabelPtr(0) |
| , m_nextBacktrack(0) |
| , m_backtrackSourceLabel(0) |
| , m_backtrackSourceJumps(0) |
| { |
| } |
| |
| BacktrackDestination(Label label) |
| : m_backtrackType(BacktrackLabel) |
| , m_backtrackLabel(label) |
| , m_backtrackToLabel(0) |
| , m_subDataLabelPtr(0) |
| , m_nextBacktrack(0) |
| , m_backtrackSourceLabel(0) |
| , m_backtrackSourceJumps(0) |
| { |
| } |
| |
| void clear(bool doDataLabelClear = true) |
| { |
| m_backtrackType = NoBacktrack; |
| if (doDataLabelClear) |
| clearDataLabel(); |
| m_nextBacktrack = 0; |
| } |
| |
| void clearDataLabel() |
| { |
| m_dataLabelPtr = DataLabelPtr(); |
| } |
| |
| bool hasDestination() |
| { |
| return (m_backtrackType != NoBacktrack); |
| } |
| |
| bool isStackOffset() |
| { |
| return (m_backtrackType == BacktrackStackOffset); |
| } |
| |
| bool isLabel() |
| { |
| return (m_backtrackType == BacktrackLabel); |
| } |
| |
| bool isJumpList() |
| { |
| return (m_backtrackType == BacktrackJumpList); |
| } |
| |
| bool hasDataLabel() |
| { |
| return m_dataLabelPtr.isSet(); |
| } |
| |
| void copyTarget(BacktrackDestination& rhs, bool copyDataLabel = true) |
| { |
| m_backtrackType = rhs.m_backtrackType; |
| if (m_backtrackType == BacktrackStackOffset) |
| m_backtrackStackOffset = rhs.m_backtrackStackOffset; |
| else if (m_backtrackType == BacktrackLabel) |
| m_backtrackLabel = rhs.m_backtrackLabel; |
| if (copyDataLabel) |
| m_dataLabelPtr = rhs.m_dataLabelPtr; |
| m_backtrackSourceJumps = rhs.m_backtrackSourceJumps; |
| m_backtrackSourceLabel = rhs.m_backtrackSourceLabel; |
| } |
| |
| void copyTo(BacktrackDestination& lhs) |
| { |
| lhs.m_backtrackType = m_backtrackType; |
| if (m_backtrackType == BacktrackStackOffset) |
| lhs.m_backtrackStackOffset = m_backtrackStackOffset; |
| else if (m_backtrackType == BacktrackLabel) |
| lhs.m_backtrackLabel = m_backtrackLabel; |
| lhs.m_backtrackSourceJumps = m_backtrackSourceJumps; |
| lhs.m_backtrackSourceLabel = m_backtrackSourceLabel; |
| lhs.m_dataLabelPtr = m_dataLabelPtr; |
| lhs.m_backTrackJumps = m_backTrackJumps; |
| } |
| |
| void addBacktrackJump(Jump jump) |
| { |
| m_backTrackJumps.append(jump); |
| } |
| |
| void setStackOffset(int32_t stackOffset) |
| { |
| m_backtrackType = BacktrackStackOffset; |
| m_backtrackStackOffset = stackOffset; |
| } |
| |
| void setLabel(Label label) |
| { |
| m_backtrackType = BacktrackLabel; |
| m_backtrackLabel = label; |
| } |
| |
| void setNextBacktrackLabel(Label label) |
| { |
| if (m_nextBacktrack) |
| m_nextBacktrack->setLabel(label); |
| } |
| |
| void propagateBacktrackToLabel(const BacktrackDestination& rhs) |
| { |
| if (!m_backtrackToLabel && rhs.m_backtrackToLabel) |
| m_backtrackToLabel = rhs.m_backtrackToLabel; |
| } |
| |
| void setBacktrackToLabel(Label* backtrackToLabel) |
| { |
| if (!m_backtrackToLabel) |
| m_backtrackToLabel = backtrackToLabel; |
| } |
| |
| bool hasBacktrackToLabel() |
| { |
| return m_backtrackToLabel; |
| } |
| |
| void setBacktrackJumpList(JumpList* jumpList) |
| { |
| m_backtrackType = BacktrackJumpList; |
| m_backtrackSourceJumps = jumpList; |
| } |
| |
| void setBacktrackSourceLabel(Label* backtrackSourceLabel) |
| { |
| m_backtrackSourceLabel = backtrackSourceLabel; |
| } |
| |
| void setDataLabel(DataLabelPtr dp) |
| { |
| if (m_subDataLabelPtr) { |
| *m_subDataLabelPtr = dp; |
| m_subDataLabelPtr = 0; |
| } else { |
| ASSERT(!hasDataLabel()); |
| m_dataLabelPtr = dp; |
| } |
| } |
| |
| void clearSubDataLabelPtr() |
| { |
| m_subDataLabelPtr = 0; |
| } |
| |
| void setSubDataLabelPtr(DataLabelPtr* subDataLabelPtr) |
| { |
| m_subDataLabelPtr = subDataLabelPtr; |
| } |
| |
| void linkToNextBacktrack(BacktrackDestination* nextBacktrack) |
| { |
| m_nextBacktrack = nextBacktrack; |
| } |
| |
| int32_t getStackOffset() |
| { |
| ASSERT(m_backtrackType == BacktrackStackOffset); |
| return m_backtrackStackOffset; |
| } |
| |
| Label getLabel() |
| { |
| ASSERT(m_backtrackType == BacktrackLabel); |
| return m_backtrackLabel; |
| } |
| |
| JumpList& getBacktrackJumps() |
| { |
| return m_backTrackJumps; |
| } |
| |
| DataLabelPtr& getDataLabel() |
| { |
| return m_dataLabelPtr; |
| } |
| |
| void jumpToBacktrack(MacroAssembler* masm) |
| { |
| if (isJumpList()) { |
| if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet())) |
| masm->jump().linkTo(*m_backtrackSourceLabel, masm); |
| else |
| m_backtrackSourceJumps->append(masm->jump()); |
| } else if (isStackOffset()) |
| masm->jump(Address(stackPointerRegister, m_backtrackStackOffset)); |
| else if (isLabel()) |
| masm->jump().linkTo(m_backtrackLabel, masm); |
| else |
| m_backTrackJumps.append(masm->jump()); |
| } |
| |
| void jumpToBacktrack(YarrGenerator* generator, Jump jump) |
| { |
| if (isJumpList()) { |
| if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet())) |
| jump.linkTo(*m_backtrackSourceLabel, generator); |
| else |
| m_backtrackSourceJumps->append(jump); |
| } else if (isStackOffset()) |
| generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jump); |
| else if (isLabel()) |
| jump.linkTo(getLabel(), generator); |
| else |
| m_backTrackJumps.append(jump); |
| } |
| |
| void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps) |
| { |
| if (isJumpList()) { |
| if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet())) |
| jumps.linkTo(*m_backtrackSourceLabel, generator); |
| else |
| m_backtrackSourceJumps->append(jumps); |
| } else if (isStackOffset()) |
| generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jumps); |
| else if (isLabel()) |
| jumps.linkTo(getLabel(), generator); |
| else |
| m_backTrackJumps.append(jumps); |
| } |
| |
| bool plantJumpToBacktrackIfExists(YarrGenerator* generator) |
| { |
| if (isJumpList()) { |
| if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet())) |
| generator->jump(*m_backtrackSourceLabel); |
| else |
| m_backtrackSourceJumps->append(generator->jump()); |
| |
| return true; |
| } |
| |
| if (isStackOffset()) { |
| generator->jump(Address(stackPointerRegister, getStackOffset())); |
| return true; |
| } |
| |
| if (isLabel()) { |
| generator->jump(getLabel()); |
| if (hasDataLabel()) { |
| generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), getLabel())); |
| clearDataLabel(); |
| } |
| return true; |
| } |
| |
| return false; |
| } |
| |
| void linkBacktrackToLabel(Label backtrackLabel) |
| { |
| if (m_backtrackToLabel) |
| *m_backtrackToLabel = backtrackLabel; |
| } |
| |
| void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false) |
| { |
| Label hereLabel = generator->label(); |
| |
| if (m_backtrackToLabel) { |
| *m_backtrackToLabel = hereLabel; |
| m_backtrackToLabel = 0; |
| } |
| |
| m_backTrackJumps.link(generator); |
| |
| if (nextIteration) |
| generator->m_expressionState.linkToNextIteration(hereLabel); |
| |
| if (hasDataLabel()) { |
| generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), hereLabel)); |
| // data label cleared as a result of the clear() below |
| } |
| |
| clear(); |
| } |
| |
| void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false) |
| { |
| m_backTrackJumps.linkTo(label, generator); |
| |
| if (nextIteration) |
| generator->m_expressionState.linkToNextIteration(label); |
| |
| if (hasDataLabel()) { |
| generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), label)); |
| clearDataLabel(); |
| } |
| } |
| |
| private: |
| BacktrackType m_backtrackType; |
| int32_t m_backtrackStackOffset; |
| Label m_backtrackLabel; |
| DataLabelPtr m_dataLabelPtr; |
| Label* m_backtrackToLabel; |
| DataLabelPtr* m_subDataLabelPtr; |
| BacktrackDestination* m_nextBacktrack; |
| Label* m_backtrackSourceLabel; |
| JumpList* m_backtrackSourceJumps; |
| JumpList m_backTrackJumps; |
| }; |
| |
| struct TermGenerationState { |
| TermGenerationState(PatternDisjunction* disjunction, unsigned checkedTotal) |
| : disjunction(disjunction) |
| , checkedTotal(checkedTotal) |
| , m_subParenNum(0) |
| , m_linkedBacktrack(0) |
| , m_jumpList(0) |
| { |
| } |
| |
| void resetAlternative() |
| { |
| m_backtrack.clear(); |
| alt = 0; |
| } |
| bool alternativeValid() |
| { |
| return alt < disjunction->m_alternatives.size(); |
| } |
| void nextAlternative() |
| { |
| ++alt; |
| } |
| PatternAlternative* alternative() |
| { |
| return disjunction->m_alternatives[alt]; |
| } |
| bool isLastAlternative() |
| { |
| return (alt + 1) == disjunction->m_alternatives.size(); |
| } |
| |
| void resetTerm() |
| { |
| ASSERT(alternativeValid()); |
| t = 0; |
| m_subParenNum = 0; |
| } |
| bool termValid() |
| { |
| ASSERT(alternativeValid()); |
| return t < alternative()->m_terms.size(); |
| } |
| void nextTerm() |
| { |
| ASSERT(alternativeValid()); |
| ++t; |
| } |
| PatternTerm& term() |
| { |
| ASSERT(alternativeValid()); |
| return alternative()->m_terms[t]; |
| } |
| bool isLastTerm() |
| { |
| ASSERT(alternativeValid()); |
| return (t + 1) == alternative()->m_terms.size(); |
| } |
| unsigned getSubParenNum() |
| { |
| return m_subParenNum++; |
| } |
| bool isMainDisjunction() |
| { |
| return !disjunction->m_parent; |
| } |
| |
| void setJumpListToPriorParen(JumpList* jumpList) |
| { |
| m_jumpList = jumpList; |
| } |
| |
| JumpList* getJumpListToPriorParen() |
| { |
| return m_jumpList; |
| } |
| |
| PatternTerm& lookaheadTerm() |
| { |
| ASSERT(alternativeValid()); |
| ASSERT((t + 1) < alternative()->m_terms.size()); |
| return alternative()->m_terms[t + 1]; |
| } |
| bool isSinglePatternCharacterLookaheadTerm() |
| { |
| ASSERT(alternativeValid()); |
| return ((t + 1) < alternative()->m_terms.size()) |
| && (lookaheadTerm().type == PatternTerm::TypePatternCharacter) |
| && (lookaheadTerm().quantityType == QuantifierFixedCount) |
| && (lookaheadTerm().quantityCount == 1); |
| } |
| |
| int inputOffset() |
| { |
| return term().inputPosition - checkedTotal; |
| } |
| |
| void clearBacktrack() |
| { |
| m_backtrack.clear(false); |
| m_linkedBacktrack = 0; |
| } |
| |
| void jumpToBacktrack(MacroAssembler* masm) |
| { |
| m_backtrack.jumpToBacktrack(masm); |
| } |
| |
| void jumpToBacktrack(YarrGenerator* generator, Jump jump) |
| { |
| m_backtrack.jumpToBacktrack(generator, jump); |
| } |
| |
| void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps) |
| { |
| m_backtrack.jumpToBacktrack(generator, jumps); |
| } |
| |
| bool plantJumpToBacktrackIfExists(YarrGenerator* generator) |
| { |
| return m_backtrack.plantJumpToBacktrackIfExists(generator); |
| } |
| |
| void linkDataLabelToBacktrackIfExists(YarrGenerator* generator, DataLabelPtr dataLabel) |
| { |
| // If we have a stack offset backtrack destination, use it directly |
| if (m_backtrack.isStackOffset()) { |
| generator->m_expressionState.addIndirectJumpEntry(m_backtrack.getStackOffset(), dataLabel); |
| m_backtrack.clearSubDataLabelPtr(); |
| } else { |
| // If we have a backtrack label, connect the datalabel to it directly. |
| if (m_backtrack.isLabel()) |
| generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(dataLabel, m_backtrack.getLabel())); |
| else |
| setBacktrackDataLabel(dataLabel); |
| } |
| } |
| |
| void addBacktrackJump(Jump jump) |
| { |
| m_backtrack.addBacktrackJump(jump); |
| } |
| |
| void setBacktrackDataLabel(DataLabelPtr dp) |
| { |
| m_backtrack.setDataLabel(dp); |
| } |
| |
| void setBackTrackStackOffset(int32_t stackOffset) |
| { |
| m_backtrack.setStackOffset(stackOffset); |
| } |
| |
| void setBacktrackLabel(Label label) |
| { |
| m_backtrack.setLabel(label); |
| } |
| |
| void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false) |
| { |
| m_backtrack.linkAlternativeBacktracks(generator, nextIteration); |
| m_linkedBacktrack = 0; |
| } |
| |
| void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false) |
| { |
| m_backtrack.linkAlternativeBacktracksTo(generator, label, nextIteration); |
| } |
| |
| void setBacktrackLink(BacktrackDestination* linkedBacktrack) |
| { |
| m_linkedBacktrack = linkedBacktrack; |
| } |
| |
| void chainBacktracks(BacktrackDestination* followonBacktrack) |
| { |
| if (m_linkedBacktrack) |
| m_linkedBacktrack->linkToNextBacktrack(followonBacktrack); |
| } |
| |
| BacktrackDestination& getBacktrackDestination() |
| { |
| return m_backtrack; |
| } |
| |
| void propagateBacktrackingFrom(YarrGenerator* generator, BacktrackDestination& backtrack, bool doJump = true) |
| { |
| if (doJump) |
| m_backtrack.jumpToBacktrack(generator, backtrack.getBacktrackJumps()); |
| |
| if (m_backtrack.isLabel() && backtrack.hasBacktrackToLabel()) |
| backtrack.linkBacktrackToLabel(m_backtrack.getLabel()); |
| |
| if (backtrack.hasDestination()) { |
| if (m_backtrack.hasDataLabel()) |
| generator->m_expressionState.addDataLabelToNextIteration(m_backtrack.getDataLabel()); |
| |
| m_backtrack.copyTarget(backtrack, doJump); |
| } |
| } |
| |
| PatternDisjunction* disjunction; |
| int checkedTotal; |
| private: |
| unsigned alt; |
| unsigned t; |
| unsigned m_subParenNum; |
| BacktrackDestination m_backtrack; |
| BacktrackDestination* m_linkedBacktrack; |
| JumpList* m_jumpList; |
| }; |
| |
| struct ParenthesesTail { |
| ParenthesesTail(PatternTerm& term, int nestingLevel, JumpList* jumpListToPriorParen) |
| : m_term(term) |
| , m_nestingLevel(nestingLevel) |
| , m_subParenIndex(0) |
| , m_jumpListToPriorParen(jumpListToPriorParen) |
| { |
| } |
| |
| void processBacktracks(YarrGenerator* generator, TermGenerationState& state, TermGenerationState& parenthesesState, Label nonGreedyTryParentheses, Label fallThrough) |
| { |
| m_nonGreedyTryParentheses = nonGreedyTryParentheses; |
| m_fallThrough = fallThrough; |
| |
| m_subParenIndex = state.getSubParenNum(); |
| parenthesesState.getBacktrackDestination().copyTo(m_parenBacktrack); |
| state.chainBacktracks(&m_backtrack); |
| BacktrackDestination& stateBacktrack = state.getBacktrackDestination(); |
| stateBacktrack.copyTo(m_backtrack); |
| stateBacktrack.setBacktrackToLabel(&m_backtrackToLabel); |
| state.setBacktrackLink(&m_backtrack); |
| stateBacktrack.setSubDataLabelPtr(&m_dataAfterLabelPtr); |
| |
| m_doDirectBacktrack = m_parenBacktrack.hasDestination(); |
| |
| if ((m_term.quantityType == QuantifierGreedy) || (m_term.quantityType == QuantifierNonGreedy)) |
| m_doDirectBacktrack = false; |
| |
| if (m_doDirectBacktrack) |
| state.propagateBacktrackingFrom(generator, m_parenBacktrack, false); |
| else { |
| stateBacktrack.setBacktrackJumpList(&m_afterBacktrackJumps); |
| stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens); |
| } |
| } |
| |
| void setNextIteration(Label nextIteration) |
| { |
| if (!m_nestingLevel && !m_backtrackToLabel.isSet()) |
| m_backtrackToLabel = nextIteration; |
| } |
| |
| void addAfterParenJump(Jump jump) |
| { |
| m_afterBacktrackJumps.append(jump); |
| } |
| |
| bool generateCode(YarrGenerator* generator, JumpList& jumpsToNext, bool priorBackTrackFallThrough, bool nextBacktrackFallThrough) |
| { |
| const RegisterID indexTemporary = regT0; |
| unsigned parenthesesFrameLocation = m_term.frameLocation; |
| Jump fromPriorBacktrack; |
| bool needJumpForPriorParenTail = false; |
| |
| if (priorBackTrackFallThrough |
| && ((m_term.quantityType == QuantifierGreedy) |
| || (m_term.quantityType == QuantifierNonGreedy) |
| || (!m_doDirectBacktrack && m_parenBacktrack.hasDestination()))) { |
| // If the prior paren tail code assumed that it could fall through, |
| // but we need to generate after paren backtrack code, then provide |
| // a jump around that code for the prior paren tail code. |
| // A regular expressing like ((xxx)...)? needs this. |
| fromPriorBacktrack = generator->jump(); |
| needJumpForPriorParenTail = true; |
| } |
| |
| if (!m_backtrack.hasDestination()) { |
| if (m_backtrackToLabel.isSet()) { |
| m_backtrack.setLabel(m_backtrackToLabel); |
| nextBacktrackFallThrough = false; |
| } else if (m_jumpListToPriorParen) { |
| // If we don't have a destination, go back to either the prior paren or the next outer paren. |
| m_backtrack.setBacktrackJumpList(m_jumpListToPriorParen); |
| nextBacktrackFallThrough = false; |
| } else |
| m_backtrack.setBacktrackJumpList(&jumpsToNext); |
| } else |
| nextBacktrackFallThrough = false; |
| |
| // A failure AFTER the parens jumps here - Backtrack to this paren |
| m_backtrackFromAfterParens = generator->label(); |
| |
| if (m_dataAfterLabelPtr.isSet()) |
| generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataAfterLabelPtr, m_backtrackFromAfterParens)); |
| |
| m_afterBacktrackJumps.link(generator); |
| |
| if (m_term.quantityType == QuantifierGreedy) { |
| // If this is -1 we have now tested with both with and without the parens. |
| generator->loadFromFrame(parenthesesFrameLocation, indexTemporary); |
| m_backtrack.jumpToBacktrack(generator, generator->branch32(Equal, indexTemporary, TrustedImm32(-1))); |
| } else if (m_term.quantityType == QuantifierNonGreedy) { |
| // If this is -1 we have now tested with both with and without the parens. |
| generator->loadFromFrame(parenthesesFrameLocation, indexTemporary); |
| generator->branch32(Equal, indexTemporary, TrustedImm32(-1)).linkTo(m_nonGreedyTryParentheses, generator); |
| } |
| |
| if (!m_doDirectBacktrack) |
| m_parenBacktrack.plantJumpToBacktrackIfExists(generator); |
| |
| // A failure WITHIN the parens jumps here |
| if (needJumpForPriorParenTail) |
| fromPriorBacktrack.link(generator); |
| m_parenBacktrack.linkAlternativeBacktracks(generator); |
| m_withinBacktrackJumps.link(generator); |
| |
| if (m_term.capture()) |
| generator->store32(TrustedImm32(-1), Address(output, (m_term.parentheses.subpatternId << 1) * sizeof(int))); |
| |
| if (m_term.quantityType == QuantifierGreedy) { |
| generator->storeToFrame(TrustedImm32(-1), parenthesesFrameLocation); |
| generator->jump().linkTo(m_fallThrough, generator); |
| nextBacktrackFallThrough = false; |
| } else if (!nextBacktrackFallThrough) |
| m_backtrack.jumpToBacktrack(generator); |
| |
| if (!m_doDirectBacktrack) |
| m_backtrack.setNextBacktrackLabel(m_backtrackFromAfterParens); |
| |
| return nextBacktrackFallThrough; |
| } |
| |
| PatternTerm& m_term; |
| int m_nestingLevel; |
| unsigned m_subParenIndex; |
| JumpList* m_jumpListToPriorParen; |
| Label m_nonGreedyTryParentheses; |
| Label m_fallThrough; |
| Label m_backtrackToLabel; |
| Label m_backtrackFromAfterParens; |
| DataLabelPtr m_dataAfterLabelPtr; |
| JumpList m_withinBacktrackJumps; |
| JumpList m_afterBacktrackJumps; |
| BacktrackDestination m_parenBacktrack; |
| BacktrackDestination m_backtrack; |
| bool m_doDirectBacktrack; |
| }; |
| |
| void generateAssertionBOL(TermGenerationState& state) |
| { |
| PatternTerm& term = state.term(); |
| |
| if (m_pattern.m_multiline) { |
| const RegisterID character = regT0; |
| |
| JumpList matchDest; |
| if (!term.inputPosition) |
| matchDest.append(branch32(Equal, index, Imm32(state.checkedTotal))); |
| |
| readCharacter(state.inputOffset() - 1, character); |
| matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass()); |
| state.jumpToBacktrack(this); |
| |
| matchDest.link(this); |
| } else { |
| // Erk, really should poison out these alternatives early. :-/ |
| if (term.inputPosition) |
| state.jumpToBacktrack(this); |
| else |
| state.jumpToBacktrack(this, branch32(NotEqual, index, Imm32(state.checkedTotal))); |
| } |
| } |
| |
| void generateAssertionEOL(TermGenerationState& state) |
| { |
| PatternTerm& term = state.term(); |
| |
| if (m_pattern.m_multiline) { |
| const RegisterID character = regT0; |
| |
| JumpList matchDest; |
| if (term.inputPosition == state.checkedTotal) |
| matchDest.append(atEndOfInput()); |
| |
| readCharacter(state.inputOffset(), character); |
| matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass()); |
| state.jumpToBacktrack(this); |
| |
| matchDest.link(this); |
| } else { |
| if (term.inputPosition == state.checkedTotal) |
| state.jumpToBacktrack(this, notAtEndOfInput()); |
| // Erk, really should poison out these alternatives early. :-/ |
| else |
| state.jumpToBacktrack(this); |
| } |
| } |
| |
| // Also falls though on nextIsNotWordChar. |
| void matchAssertionWordchar(TermGenerationState& state, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar) |
| { |
| const RegisterID character = regT0; |
| PatternTerm& term = state.term(); |
| |
| if (term.inputPosition == state.checkedTotal) |
| nextIsNotWordChar.append(atEndOfInput()); |
| |
| readCharacter(state.inputOffset(), character); |
| matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass()); |
| } |
| |
| void generateAssertionWordBoundary(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| PatternTerm& term = state.term(); |
| |
| Jump atBegin; |
| JumpList matchDest; |
| if (!term.inputPosition) |
| atBegin = branch32(Equal, index, Imm32(state.checkedTotal)); |
| readCharacter(state.inputOffset() - 1, character); |
| matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass()); |
| if (!term.inputPosition) |
| atBegin.link(this); |
| |
| // We fall through to here if the last character was not a wordchar. |
| JumpList nonWordCharThenWordChar; |
| JumpList nonWordCharThenNonWordChar; |
| if (term.invert()) { |
| matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar); |
| nonWordCharThenWordChar.append(jump()); |
| } else { |
| matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar); |
| nonWordCharThenNonWordChar.append(jump()); |
| } |
| state.jumpToBacktrack(this, nonWordCharThenNonWordChar); |
| |
| // We jump here if the last character was a wordchar. |
| matchDest.link(this); |
| JumpList wordCharThenWordChar; |
| JumpList wordCharThenNonWordChar; |
| if (term.invert()) { |
| matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar); |
| wordCharThenWordChar.append(jump()); |
| } else { |
| matchAssertionWordchar(state, wordCharThenWordChar, wordCharThenNonWordChar); |
| // This can fall-though! |
| } |
| |
| state.jumpToBacktrack(this, wordCharThenWordChar); |
| |
| nonWordCharThenWordChar.link(this); |
| wordCharThenNonWordChar.link(this); |
| } |
| |
| void generatePatternCharacterSingle(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| UChar ch = state.term().patternCharacter; |
| |
| if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) { |
| readCharacter(state.inputOffset(), character); |
| or32(TrustedImm32(32), character); |
| state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch)))); |
| } else { |
| ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch))); |
| state.jumpToBacktrack(this, jumpIfCharNotEquals(ch, state.inputOffset())); |
| } |
| } |
| |
| void generatePatternCharacterPair(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| UChar ch1 = state.term().patternCharacter; |
| UChar ch2 = state.lookaheadTerm().patternCharacter; |
| |
| int mask = 0; |
| int chPair = ch1 | (ch2 << 16); |
| |
| if (m_pattern.m_ignoreCase) { |
| if (isASCIIAlpha(ch1)) |
| mask |= 32; |
| if (isASCIIAlpha(ch2)) |
| mask |= 32 << 16; |
| } |
| |
| if (mask) { |
| load32WithUnalignedHalfWords(BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), character); |
| or32(Imm32(mask), character); |
| state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(chPair | mask))); |
| } else |
| state.jumpToBacktrack(this, branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair))); |
| } |
| |
| void generatePatternCharacterFixed(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| const RegisterID countRegister = regT1; |
| PatternTerm& term = state.term(); |
| UChar ch = term.patternCharacter; |
| |
| move(index, countRegister); |
| sub32(Imm32(term.quantityCount), countRegister); |
| |
| Label loop(this); |
| if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) { |
| load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character); |
| or32(TrustedImm32(32), character); |
| state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch)))); |
| } else { |
| ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch))); |
| state.jumpToBacktrack(this, branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch))); |
| } |
| add32(TrustedImm32(1), countRegister); |
| branch32(NotEqual, countRegister, index).linkTo(loop, this); |
| } |
| |
| void generatePatternCharacterGreedy(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| const RegisterID countRegister = regT1; |
| PatternTerm& term = state.term(); |
| UChar ch = term.patternCharacter; |
| |
| move(TrustedImm32(0), countRegister); |
| |
| JumpList failures; |
| Label loop(this); |
| failures.append(atEndOfInput()); |
| if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) { |
| readCharacter(state.inputOffset(), character); |
| or32(TrustedImm32(32), character); |
| failures.append(branch32(NotEqual, character, Imm32(Unicode::toLower(ch)))); |
| } else { |
| ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch))); |
| failures.append(jumpIfCharNotEquals(ch, state.inputOffset())); |
| } |
| |
| add32(TrustedImm32(1), countRegister); |
| add32(TrustedImm32(1), index); |
| if (term.quantityCount != quantifyInfinite) { |
| branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this); |
| failures.append(jump()); |
| } else |
| jump(loop); |
| |
| Label backtrackBegin(this); |
| loadFromFrame(term.frameLocation, countRegister); |
| state.jumpToBacktrack(this, branchTest32(Zero, countRegister)); |
| sub32(TrustedImm32(1), countRegister); |
| sub32(TrustedImm32(1), index); |
| |
| failures.link(this); |
| |
| storeToFrame(countRegister, term.frameLocation); |
| |
| state.setBacktrackLabel(backtrackBegin); |
| } |
| |
| void generatePatternCharacterNonGreedy(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| const RegisterID countRegister = regT1; |
| PatternTerm& term = state.term(); |
| UChar ch = term.patternCharacter; |
| |
| move(TrustedImm32(0), countRegister); |
| |
| Jump firstTimeDoNothing = jump(); |
| |
| Label hardFail(this); |
| sub32(countRegister, index); |
| state.jumpToBacktrack(this); |
| |
| Label backtrackBegin(this); |
| loadFromFrame(term.frameLocation, countRegister); |
| |
| atEndOfInput().linkTo(hardFail, this); |
| if (term.quantityCount != quantifyInfinite) |
| branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail); |
| if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) { |
| readCharacter(state.inputOffset(), character); |
| or32(TrustedImm32(32), character); |
| branch32(NotEqual, character, Imm32(Unicode::toLower(ch))).linkTo(hardFail, this); |
| } else { |
| ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch))); |
| jumpIfCharNotEquals(ch, state.inputOffset()).linkTo(hardFail, this); |
| } |
| |
| add32(TrustedImm32(1), countRegister); |
| add32(TrustedImm32(1), index); |
| |
| firstTimeDoNothing.link(this); |
| storeToFrame(countRegister, term.frameLocation); |
| |
| state.setBacktrackLabel(backtrackBegin); |
| } |
| |
| void generateCharacterClassSingle(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| PatternTerm& term = state.term(); |
| |
| JumpList matchDest; |
| readCharacter(state.inputOffset(), character); |
| matchCharacterClass(character, matchDest, term.characterClass); |
| |
| if (term.invert()) |
| state.jumpToBacktrack(this, matchDest); |
| else { |
| state.jumpToBacktrack(this); |
| matchDest.link(this); |
| } |
| } |
| |
| void generateCharacterClassFixed(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| const RegisterID countRegister = regT1; |
| PatternTerm& term = state.term(); |
| |
| move(index, countRegister); |
| sub32(Imm32(term.quantityCount), countRegister); |
| |
| Label loop(this); |
| JumpList matchDest; |
| load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character); |
| matchCharacterClass(character, matchDest, term.characterClass); |
| |
| if (term.invert()) |
| state.jumpToBacktrack(this, matchDest); |
| else { |
| state.jumpToBacktrack(this); |
| matchDest.link(this); |
| } |
| |
| add32(TrustedImm32(1), countRegister); |
| branch32(NotEqual, countRegister, index).linkTo(loop, this); |
| } |
| |
| void generateCharacterClassGreedy(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| const RegisterID countRegister = regT1; |
| PatternTerm& term = state.term(); |
| |
| move(TrustedImm32(0), countRegister); |
| |
| JumpList failures; |
| Label loop(this); |
| failures.append(atEndOfInput()); |
| |
| if (term.invert()) { |
| readCharacter(state.inputOffset(), character); |
| matchCharacterClass(character, failures, term.characterClass); |
| } else { |
| JumpList matchDest; |
| readCharacter(state.inputOffset(), character); |
| matchCharacterClass(character, matchDest, term.characterClass); |
| failures.append(jump()); |
| matchDest.link(this); |
| } |
| |
| add32(TrustedImm32(1), countRegister); |
| add32(TrustedImm32(1), index); |
| if (term.quantityCount != quantifyInfinite) { |
| branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this); |
| failures.append(jump()); |
| } else |
| jump(loop); |
| |
| Label backtrackBegin(this); |
| loadFromFrame(term.frameLocation, countRegister); |
| state.jumpToBacktrack(this, branchTest32(Zero, countRegister)); |
| sub32(TrustedImm32(1), countRegister); |
| sub32(TrustedImm32(1), index); |
| |
| failures.link(this); |
| |
| storeToFrame(countRegister, term.frameLocation); |
| |
| state.setBacktrackLabel(backtrackBegin); |
| } |
| |
| void generateCharacterClassNonGreedy(TermGenerationState& state) |
| { |
| const RegisterID character = regT0; |
| const RegisterID countRegister = regT1; |
| PatternTerm& term = state.term(); |
| |
| move(TrustedImm32(0), countRegister); |
| |
| Jump firstTimeDoNothing = jump(); |
| |
| Label hardFail(this); |
| sub32(countRegister, index); |
| state.jumpToBacktrack(this); |
| |
| Label backtrackBegin(this); |
| loadFromFrame(term.frameLocation, countRegister); |
| |
| atEndOfInput().linkTo(hardFail, this); |
| branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail); |
| |
| JumpList matchDest; |
| readCharacter(state.inputOffset(), character); |
| matchCharacterClass(character, matchDest, term.characterClass); |
| |
| if (term.invert()) |
| matchDest.linkTo(hardFail, this); |
| else { |
| jump(hardFail); |
| matchDest.link(this); |
| } |
| |
| add32(TrustedImm32(1), countRegister); |
| add32(TrustedImm32(1), index); |
| |
| firstTimeDoNothing.link(this); |
| storeToFrame(countRegister, term.frameLocation); |
| |
| state.setBacktrackLabel(backtrackBegin); |
| } |
| |
| void generateParenthesesDisjunction(PatternTerm& parenthesesTerm, TermGenerationState& state, unsigned alternativeFrameLocation) |
| { |
| ASSERT((parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern) || (parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion)); |
| ASSERT(parenthesesTerm.quantityCount == 1); |
| |
| PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction; |
| unsigned preCheckedCount = ((parenthesesTerm.quantityType == QuantifierFixedCount) && (parenthesesTerm.type != PatternTerm::TypeParentheticalAssertion)) ? disjunction->m_minimumSize : 0; |
| |
| if (disjunction->m_alternatives.size() == 1) { |
| state.resetAlternative(); |
| ASSERT(state.alternativeValid()); |
| PatternAlternative* alternative = state.alternative(); |
| optimizeAlternative(alternative); |
| |
| int countToCheck = alternative->m_minimumSize - preCheckedCount; |
| if (countToCheck) { |
| ASSERT((parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion) || (parenthesesTerm.quantityType != QuantifierFixedCount)); |
| |
| // FIXME: This is quite horrible. The call to 'plantJumpToBacktrackIfExists' |
| // will be forced to always trampoline into here, just to decrement the index. |
| // Ick. |
| Jump skip = jump(); |
| |
| Label backtrackBegin(this); |
| sub32(Imm32(countToCheck), index); |
| state.addBacktrackJump(jump()); |
| |
| skip.link(this); |
| |
| state.setBacktrackLabel(backtrackBegin); |
| |
| state.jumpToBacktrack(this, jumpIfNoAvailableInput(countToCheck)); |
| state.checkedTotal += countToCheck; |
| } |
| |
| for (state.resetTerm(); state.termValid(); state.nextTerm()) |
| generateTerm(state); |
| |
| state.checkedTotal -= countToCheck; |
| } else { |
| JumpList successes; |
| bool propogateBacktrack = false; |
| |
| // Save current state's paren jump list for use with each alternative |
| JumpList* outerJumpList = state.getJumpListToPriorParen(); |
| |
| for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative(), state.setJumpListToPriorParen(outerJumpList)) { |
| PatternAlternative* alternative = state.alternative(); |
| optimizeAlternative(alternative); |
| |
| ASSERT(alternative->m_minimumSize >= preCheckedCount); |
| int countToCheck = alternative->m_minimumSize - preCheckedCount; |
| if (countToCheck) { |
| state.addBacktrackJump(jumpIfNoAvailableInput(countToCheck)); |
| state.checkedTotal += countToCheck; |
| } |
| |
| for (state.resetTerm(); state.termValid(); state.nextTerm()) |
| generateTerm(state); |
| |
| // Matched an alternative. |
| DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation); |
| |
| if (!state.isLastAlternative() || countToCheck) |
| successes.append(jump()); |
| |
| // Alternative did not match. |
| |
| // Do we have a backtrack destination? |
| // if so, link the data label to it. |
| state.linkDataLabelToBacktrackIfExists(this, dataLabel); |
| |
| if (!state.isLastAlternative() || countToCheck) |
| state.linkAlternativeBacktracks(this); |
| |
| if (countToCheck) { |
| sub32(Imm32(countToCheck), index); |
| state.checkedTotal -= countToCheck; |
| } else if (state.isLastAlternative()) |
| propogateBacktrack = true; |
| } |
| // We fall through to here when the last alternative fails. |
| // Add a backtrack out of here for the parenthese handling code to link up. |
| if (!propogateBacktrack) |
| state.addBacktrackJump(jump()); |
| |
| // Save address on stack for the parens code to backtrack to, to retry the |
| // next alternative. |
| state.setBackTrackStackOffset(alternativeFrameLocation * sizeof(void*)); |
| |
| successes.link(this); |
| } |
| } |
| |
| void generateParenthesesSingle(TermGenerationState& state) |
| { |
| const RegisterID indexTemporary = regT0; |
| PatternTerm& term = state.term(); |
| PatternDisjunction* disjunction = term.parentheses.disjunction; |
| ASSERT(term.quantityCount == 1); |
| |
| unsigned preCheckedCount = (term.quantityType == QuantifierFixedCount) ? disjunction->m_minimumSize : 0; |
| |
| unsigned parenthesesFrameLocation = term.frameLocation; |
| unsigned alternativeFrameLocation = parenthesesFrameLocation; |
| if (term.quantityType != QuantifierFixedCount) |
| alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce; |
| |
| // optimized case - no capture & no quantifier can be handled in a light-weight manner. |
| if (!term.capture() && (term.quantityType == QuantifierFixedCount)) { |
| m_expressionState.incrementParenNestingLevel(); |
| |
| TermGenerationState parenthesesState(disjunction, state.checkedTotal); |
| |
| // Use the current state's jump list for the nested parentheses. |
| parenthesesState.setJumpListToPriorParen(state.getJumpListToPriorParen()); |
| |
| generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation); |
| // this expects that any backtracks back out of the parentheses will be in the |
| // parenthesesState's m_backTrackJumps vector, and that if they need backtracking |
| // they will have set an entry point on the parenthesesState's m_backtrackLabel. |
| BacktrackDestination& parenthesesBacktrack = parenthesesState.getBacktrackDestination(); |
| BacktrackDestination& stateBacktrack = state.getBacktrackDestination(); |
| |
| state.propagateBacktrackingFrom(this, parenthesesBacktrack); |
| stateBacktrack.propagateBacktrackToLabel(parenthesesBacktrack); |
| |
| state.setJumpListToPriorParen(parenthesesState.getJumpListToPriorParen()); |
| |
| m_expressionState.decrementParenNestingLevel(); |
| } else { |
| Jump nonGreedySkipParentheses; |
| Label nonGreedyTryParentheses; |
| if (term.quantityType == QuantifierGreedy) |
| storeToFrame(index, parenthesesFrameLocation); |
| else if (term.quantityType == QuantifierNonGreedy) { |
| storeToFrame(TrustedImm32(-1), parenthesesFrameLocation); |
| nonGreedySkipParentheses = jump(); |
| nonGreedyTryParentheses = label(); |
| storeToFrame(index, parenthesesFrameLocation); |
| } |
| |
| // store the match start index |
| if (term.capture()) { |
| int inputOffset = state.inputOffset() - preCheckedCount; |
| if (inputOffset) { |
| move(index, indexTemporary); |
| add32(Imm32(inputOffset), indexTemporary); |
| store32(indexTemporary, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int))); |
| } else |
| store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int))); |
| } |
| |
| ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getJumpListToPriorParen()); |
| |
| m_expressionState.incrementParenNestingLevel(); |
| |
| TermGenerationState parenthesesState(disjunction, state.checkedTotal); |
| |
| // Save the parenthesesTail for backtracking from nested parens to this one. |
| parenthesesState.setJumpListToPriorParen(&parenthesesTail->m_withinBacktrackJumps); |
| |
| // generate the body of the parentheses |
| generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation); |
| |
| // For non-fixed counts, backtrack if we didn't match anything. |
| if (term.quantityType != QuantifierFixedCount) |
| parenthesesTail->addAfterParenJump(branch32(Equal, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*))))); |
| |
| // store the match end index |
| if (term.capture()) { |
| int inputOffset = state.inputOffset(); |
| if (inputOffset) { |
| move(index, indexTemporary); |
| add32(Imm32(state.inputOffset()), indexTemporary); |
| store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int))); |
| } else |
| store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int))); |
| } |
| |
| m_expressionState.decrementParenNestingLevel(); |
| |
| parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label()); |
| |
| state.setJumpListToPriorParen(&parenthesesTail->m_afterBacktrackJumps); |
| |
| parenthesesState.getBacktrackDestination().clear(); |
| |
| if (term.quantityType == QuantifierNonGreedy) |
| nonGreedySkipParentheses.link(this); |
| } |
| } |
| |
| void generateParenthesesGreedyNoBacktrack(TermGenerationState& state) |
| { |
| PatternTerm& parenthesesTerm = state.term(); |
| PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction; |
| ASSERT(parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern); |
| ASSERT(parenthesesTerm.quantityCount != 1); // Handled by generateParenthesesSingle. |
| |
| TermGenerationState parenthesesState(disjunction, state.checkedTotal); |
| |
| Label matchAgain(this); |
| |
| storeToFrame(index, parenthesesTerm.frameLocation); // Save the current index to check for zero len matches later. |
| |
| for (parenthesesState.resetAlternative(); parenthesesState.alternativeValid(); parenthesesState.nextAlternative()) { |
| |
| PatternAlternative* alternative = parenthesesState.alternative(); |
| optimizeAlternative(alternative); |
| |
| int countToCheck = alternative->m_minimumSize; |
| if (countToCheck) { |
| parenthesesState.addBacktrackJump(jumpIfNoAvailableInput(countToCheck)); |
| parenthesesState.checkedTotal += countToCheck; |
| } |
| |
| for (parenthesesState.resetTerm(); parenthesesState.termValid(); parenthesesState.nextTerm()) |
| generateTerm(parenthesesState); |
| |
| // If we get here, we matched! If the index advanced then try to match more since limit isn't supported yet. |
| branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesTerm.frameLocation * sizeof(void*))), matchAgain); |
| |
| // If we get here we matched, but we matched "" - cannot accept this alternative as is, so either backtrack, |
| // or fall through to try the next alternative if no backtrack is available. |
| parenthesesState.plantJumpToBacktrackIfExists(this); |
| |
| parenthesesState.linkAlternativeBacktracks(this); |
| |
| // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop. |
| |
| if (countToCheck) { |
| sub32(Imm32(countToCheck), index); |
| parenthesesState.checkedTotal -= countToCheck; |
| } |
| } |
| |
| // If the last alternative falls through to here, we have a failed match... |
| // Which means that we match whatever we have matched up to this point (even if nothing). |
| } |
| |
| void generateParentheticalAssertion(TermGenerationState& state) |
| { |
| PatternTerm& term = state.term(); |
| PatternDisjunction* disjunction = term.parentheses.disjunction; |
| ASSERT(term.quantityCount == 1); |
| ASSERT(term.quantityType == QuantifierFixedCount); |
| |
| unsigned parenthesesFrameLocation = term.frameLocation; |
| unsigned alternativeFrameLocation = parenthesesFrameLocation + YarrStackSpaceForBackTrackInfoParentheticalAssertion; |
| |
| int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition; |
| |
| if (term.invert()) { |
| // Inverted case |
| storeToFrame(index, parenthesesFrameLocation); |
| |
| state.checkedTotal -= countCheckedAfterAssertion; |
| if (countCheckedAfterAssertion) |
| sub32(Imm32(countCheckedAfterAssertion), index); |
| |
| TermGenerationState parenthesesState(disjunction, state.checkedTotal); |
| generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation); |
| // Success! - which means - Fail! |
| loadFromFrame(parenthesesFrameLocation, index); |
| state.jumpToBacktrack(this); |
| |
| // And fail means success. |
| parenthesesState.linkAlternativeBacktracks(this); |
| |
| loadFromFrame(parenthesesFrameLocation, index); |
| |
| state.checkedTotal += countCheckedAfterAssertion; |
| } else { |
| // Normal case |
| storeToFrame(index, parenthesesFrameLocation); |
| |
| state.checkedTotal -= countCheckedAfterAssertion; |
| if (countCheckedAfterAssertion) |
| sub32(Imm32(countCheckedAfterAssertion), index); |
| |
| TermGenerationState parenthesesState(disjunction, state.checkedTotal); |
| generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation); |
| // Success! - which means - Success! |
| loadFromFrame(parenthesesFrameLocation, index); |
| Jump success = jump(); |
| |
| parenthesesState.linkAlternativeBacktracks(this); |
| |
| loadFromFrame(parenthesesFrameLocation, index); |
| state.jumpToBacktrack(this); |
| |
| success.link(this); |
| |
| state.checkedTotal += countCheckedAfterAssertion; |
| } |
| } |
| |
| void generateTerm(TermGenerationState& state) |
| { |
| PatternTerm& term = state.term(); |
| |
| switch (term.type) { |
| case PatternTerm::TypeAssertionBOL: |
| generateAssertionBOL(state); |
| break; |
| |
| case PatternTerm::TypeAssertionEOL: |
| generateAssertionEOL(state); |
| break; |
| |
| case PatternTerm::TypeAssertionWordBoundary: |
| generateAssertionWordBoundary(state); |
| break; |
| |
| case PatternTerm::TypePatternCharacter: |
| switch (term.quantityType) { |
| case QuantifierFixedCount: |
| if (term.quantityCount == 1) { |
| if (state.isSinglePatternCharacterLookaheadTerm() && (state.lookaheadTerm().inputPosition == (term.inputPosition + 1))) { |
| generatePatternCharacterPair(state); |
| state.nextTerm(); |
| } else |
| generatePatternCharacterSingle(state); |
| } else |
| generatePatternCharacterFixed(state); |
| break; |
| case QuantifierGreedy: |
| generatePatternCharacterGreedy(state); |
| break; |
| case QuantifierNonGreedy: |
| generatePatternCharacterNonGreedy(state); |
| break; |
| } |
| break; |
| |
| case PatternTerm::TypeCharacterClass: |
| switch (term.quantityType) { |
| case QuantifierFixedCount: |
| if (term.quantityCount == 1) |
| generateCharacterClassSingle(state); |
| else |
| generateCharacterClassFixed(state); |
| break; |
| case QuantifierGreedy: |
| generateCharacterClassGreedy(state); |
| break; |
| case QuantifierNonGreedy: |
| generateCharacterClassNonGreedy(state); |
| break; |
| } |
| break; |
| |
| case PatternTerm::TypeBackReference: |
| m_shouldFallBack = true; |
| break; |
| |
| case PatternTerm::TypeForwardReference: |
| break; |
| |
| case PatternTerm::TypeParenthesesSubpattern: |
| if (term.quantityCount == 1 && !term.parentheses.isCopy) |
| generateParenthesesSingle(state); |
| else if (term.parentheses.isTerminal) |
| generateParenthesesGreedyNoBacktrack(state); |
| else |
| m_shouldFallBack = true; |
| break; |
| |
| case PatternTerm::TypeParentheticalAssertion: |
| generateParentheticalAssertion(state); |
| break; |
| } |
| } |
| |
| void generateDisjunction(PatternDisjunction* disjunction) |
| { |
| TermGenerationState state(disjunction, 0); |
| state.resetAlternative(); |
| |
| // check availability for the next alternative |
| int countCheckedForCurrentAlternative = 0; |
| int countToCheckForFirstAlternative = 0; |
| bool hasShorterAlternatives = false; |
| bool setRepeatAlternativeLabels = false; |
| JumpList notEnoughInputForPreviousAlternative; |
| Label firstAlternative; |
| Label firstAlternativeInputChecked; |
| |
| // The label 'firstAlternative' is used to plant a check to see if there is |
| // sufficient input available to run the first repeating alternative. |
| // The label 'firstAlternativeInputChecked' will jump directly to matching |
| // the first repeating alternative having skipped this check. |
| |
| if (state.alternativeValid()) { |
| PatternAlternative* alternative = state.alternative(); |
| if (!alternative->onceThrough()) { |
| firstAlternative = Label(this); |
| setRepeatAlternativeLabels = true; |
| } |
| countToCheckForFirstAlternative = alternative->m_minimumSize; |
| state.checkedTotal += countToCheckForFirstAlternative; |
| if (countToCheckForFirstAlternative) |
| notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative)); |
| countCheckedForCurrentAlternative = countToCheckForFirstAlternative; |
| } |
| |
| if (setRepeatAlternativeLabels) |
| firstAlternativeInputChecked = Label(this); |
| |
| while (state.alternativeValid()) { |
| PatternAlternative* alternative = state.alternative(); |
| optimizeAlternative(alternative); |
| |
| // Track whether any alternatives are shorter than the first one. |
| if (!alternative->onceThrough()) |
| hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative); |
| |
| for (state.resetTerm(); state.termValid(); state.nextTerm()) |
| generateTerm(state); |
| |
| // If we get here, the alternative matched. |
| if (m_pattern.m_body->m_callFrameSize) |
| addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister); |
| |
| ASSERT(index != returnRegister); |
| if (m_pattern.m_body->m_hasFixedSize) { |
| move(index, returnRegister); |
| if (alternative->m_minimumSize) |
| sub32(Imm32(alternative->m_minimumSize), returnRegister); |
| |
| store32(returnRegister, output); |
| } else |
| load32(Address(output), returnRegister); |
| |
| store32(index, Address(output, 4)); |
| |
| generateReturn(); |
| |
| state.nextAlternative(); |
| if (alternative->onceThrough() && state.alternativeValid()) |
| state.clearBacktrack(); |
| |
| // if there are any more alternatives, plant the check for input before looping. |
| if (state.alternativeValid()) { |
| state.setJumpListToPriorParen(0); |
| PatternAlternative* nextAlternative = state.alternative(); |
| if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) { |
| // We have handled non-repeating alternatives, jump to next iteration |
| // and loop over repeating alternatives. |
| state.jumpToBacktrack(this); |
| |
| countToCheckForFirstAlternative = nextAlternative->m_minimumSize; |
| |
| // If we get here, there the last input checked failed. |
| notEnoughInputForPreviousAlternative.link(this); |
| |
| state.linkAlternativeBacktracks(this); |
| |
| // Back up to start the looping alternatives. |
| if (countCheckedForCurrentAlternative) |
| sub32(Imm32(countCheckedForCurrentAlternative), index); |
| |
| firstAlternative = Label(this); |
| |
| state.checkedTotal = countToCheckForFirstAlternative; |
| if (countToCheckForFirstAlternative) |
| notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative)); |
| |
| countCheckedForCurrentAlternative = countToCheckForFirstAlternative; |
| |
| firstAlternativeInputChecked = Label(this); |
| |
| setRepeatAlternativeLabels = true; |
| } else { |
| int countToCheckForNextAlternative = nextAlternative->m_minimumSize; |
| |
| if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one. |
| // If we get here, then the last input checked failed. |
| notEnoughInputForPreviousAlternative.link(this); |
| |
| // Check if sufficent input available to run the next alternative |
| notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative)); |
| // We are now in the correct state to enter the next alternative; this add is only required |
| // to mirror and revert operation of the sub32, just below. |
| add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index); |
| |
| // If we get here, then the last input checked passed. |
| state.linkAlternativeBacktracks(this); |
| |
| // No need to check if we can run the next alternative, since it is shorter - |
| // just update index. |
| sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index); |
| } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one. |
| // If we get here, then the last input checked failed. |
| // If there is insufficient input to run the current alternative, and the next alternative is longer, |
| // then there is definitely not enough input to run it - don't even check. Just adjust index, as if |
| // we had checked. |
| notEnoughInputForPreviousAlternative.link(this); |
| add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index); |
| notEnoughInputForPreviousAlternative.append(jump()); |
| |
| // The next alternative is longer than the current one; check the difference. |
| state.linkAlternativeBacktracks(this); |
| |
| notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative)); |
| } else { // CASE 3: Both alternatives are the same length. |
| ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative); |
| |
| // If the next alterative is the same length as this one, then no need to check the input - |
| // if there was sufficent input to run the current alternative then there is sufficient |
| // input to run the next one; if not, there isn't. |
| state.linkAlternativeBacktracks(this); |
| } |
| state.checkedTotal -= countCheckedForCurrentAlternative; |
| countCheckedForCurrentAlternative = countToCheckForNextAlternative; |
| state.checkedTotal += countCheckedForCurrentAlternative; |
| } |
| } |
| } |
| |
| // If we get here, all Alternatives failed... |
| |
| state.checkedTotal -= countCheckedForCurrentAlternative; |
| |
| if (!setRepeatAlternativeLabels) { |
| // If there are no alternatives that need repeating (all are marked 'onceThrough') then just link |
| // the match failures to this point, and fall through to the return below. |
| state.linkAlternativeBacktracks(this, true); |
| |
| notEnoughInputForPreviousAlternative.link(this); |
| } else { |
| // How much more input need there be to be able to retry from the first alternative? |
| // examples: |
| // /yarr_jit/ or /wrec|pcre/ |
| // In these examples we need check for one more input before looping. |
| // /yarr_jit|pcre/ |
| // In this case we need check for 5 more input to loop (+4 to allow for the first alterative |
| // being four longer than the last alternative checked, and another +1 to effectively move |
| // the start position along by one). |
| // /yarr|rules/ or /wrec|notsomuch/ |
| // In these examples, provided that there was sufficient input to have just been matching for |
| // the second alternative we can loop without checking for available input (since the second |
| // alternative is longer than the first). In the latter example we need to decrement index |
| // (by 4) so the start position is only progressed by 1 from the last iteration. |
| int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1; |
| |
| // First, deal with the cases where there was sufficient input to try the last alternative. |
| if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below. |
| state.linkAlternativeBacktracks(this, true); |
| else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop! |
| state.linkAlternativeBacktracksTo(this, firstAlternativeInputChecked, true); |
| else { // no need to check the input, but we do have some bookkeeping to do first. |
| state.linkAlternativeBacktracks(this, true); |
| |
| // Where necessary update our preserved start position. |
| if (!m_pattern.m_body->m_hasFixedSize) { |
| move(index, regT0); |
| sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0); |
| store32(regT0, Address(output)); |
| } |
| |
| // Update index if necessary, and loop (without checking). |
| if (incrementForNextIter) |
| add32(Imm32(incrementForNextIter), index); |
| jump().linkTo(firstAlternativeInputChecked, this); |
| } |
| |
| notEnoughInputForPreviousAlternative.link(this); |
| // Update our idea of the start position, if we're tracking this. |
| if (!m_pattern.m_body->m_hasFixedSize) { |
| if (countCheckedForCurrentAlternative - 1) { |
| move(index, regT0); |
| sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0); |
| store32(regT0, Address(output)); |
| } else |
| store32(index, Address(output)); |
| } |
| |
| // Check if there is sufficent input to run the first alternative again. |
| jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this); |
| // No - insufficent input to run the first alteranative, are there any other alternatives we |
| // might need to check? If so, the last check will have left the index incremented by |
| // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative |
| // LESS input is available, to have the effect of just progressing the start position by 1 |
| // from the last iteration. If this check passes we can just jump up to the check associated |
| // with the first alternative in the loop. This is a bit sad, since we'll end up trying the |
| // first alternative again, and this check will fail (otherwise the check planted just above |
| // here would have passed). This is a bit sad, however it saves trying to do something more |
| // complex here in compilation, and in the common case we should end up coallescing the checks. |
| // |
| // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least |
| // of the minimum-alternative-lengths. E.g. if I have two alternatives of length 200 and 150, |
| // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there |
| // is sufficient input to run either alternative (constantly failing). If there had been only |
| // one alternative, or if the shorter alternative had come first, we would have terminated |
| // immediately. :-/ |
| if (hasShorterAlternatives) |
| jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this); |
| // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true, |
| // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ... |
| // but since we're about to return a failure this doesn't really matter!) |
| } |
| |
| if (m_pattern.m_body->m_callFrameSize) |
| addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister); |
| |
| move(TrustedImm32(-1), returnRegister); |
| |
| generateReturn(); |
| |
| m_expressionState.emitParenthesesTail(this); |
| m_expressionState.emitIndirectJumpTable(this); |
| m_expressionState.linkToNextIteration(this); |
| } |
| |
| void generateEnter() |
| { |
| #if CPU(X86_64) |
| push(X86Registers::ebp); |
| move(stackPointerRegister, X86Registers::ebp); |
| push(X86Registers::ebx); |
| #elif CPU(X86) |
| push(X86Registers::ebp); |
| move(stackPointerRegister, X86Registers::ebp); |
| // TODO: do we need spill registers to fill the output pointer if there are no sub captures? |
| push(X86Registers::ebx); |
| push(X86Registers::edi); |
| push(X86Registers::esi); |
| // load output into edi (2 = saved ebp + return address). |
| #if COMPILER(MSVC) |
| loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input); |
| loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index); |
| loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length); |
| loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output); |
| #else |
| loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output); |
| #endif |
| #elif CPU(ARM) |
| push(ARMRegisters::r4); |
| push(ARMRegisters::r5); |
| push(ARMRegisters::r6); |
| #if CPU(ARM_TRADITIONAL) |
| push(ARMRegisters::r8); // scratch register |
| #endif |
| move(ARMRegisters::r3, output); |
| #elif CPU(SH4) |
| push(SH4Registers::r11); |
| push(SH4Registers::r13); |
| #elif CPU(MIPS) |
| // Do nothing. |
| #endif |
| } |
| |
| void generateReturn() |
| { |
| #if CPU(X86_64) |
| pop(X86Registers::ebx); |
| pop(X86Registers::ebp); |
| #elif CPU(X86) |
| pop(X86Registers::esi); |
| pop(X86Registers::edi); |
| pop(X86Registers::ebx); |
| pop(X86Registers::ebp); |
| #elif CPU(ARM) |
| #if CPU(ARM_TRADITIONAL) |
| pop(ARMRegisters::r8); // scratch register |
| #endif |
| pop(ARMRegisters::r6); |
| pop(ARMRegisters::r5); |
| pop(ARMRegisters::r4); |
| #elif CPU(SH4) |
| pop(SH4Registers::r13); |
| pop(SH4Registers::r11); |
| #elif CPU(MIPS) |
| // Do nothing |
| #endif |
| ret(); |
| } |
| |
| public: |
| YarrGenerator(YarrPattern& pattern) |
| : m_pattern(pattern) |
| , m_shouldFallBack(false) |
| { |
| } |
| |
| void generate() |
| { |
| generateEnter(); |
| |
| if (!m_pattern.m_body->m_hasFixedSize) |
| store32(index, Address(output)); |
| |
| if (m_pattern.m_body->m_callFrameSize) |
| subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister); |
| |
| generateDisjunction(m_pattern.m_body); |
| } |
| |
| void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject) |
| { |
| generate(); |
| |
| LinkBuffer patchBuffer(this, globalData->regexAllocator.poolForSize(size()), 0); |
| |
| for (unsigned i = 0; i < m_expressionState.m_backtrackRecords.size(); ++i) |
| patchBuffer.patch(m_expressionState.m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_expressionState.m_backtrackRecords[i].backtrackLocation)); |
| |
| jitObject.set(patchBuffer.finalizeCode()); |
| jitObject.setFallBack(m_shouldFallBack); |
| } |
| |
| private: |
| YarrPattern& m_pattern; |
| bool m_shouldFallBack; |
| GenerationState m_expressionState; |
| }; |
| |
| void jitCompile(YarrPattern& pattern, JSGlobalData* globalData, YarrCodeBlock& jitObject) |
| { |
| YarrGenerator(pattern).compile(globalData, jitObject); |
| } |
| |
| int execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output) |
| { |
| return jitObject.execute(input, start, length, output); |
| } |
| |
| }} |
| |
| #endif |
