/* * 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(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 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 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, UnsignedWithZeroKeyHashTraits > 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(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(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 m_backtrackRecords; IndirectJumpHashMap m_indirectJumpMap; Label m_nextIteration; Vector > m_parenTails; JumpList m_jumpsToNextInteration; Vector m_dataPtrsToNextIteration; Vector 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