+++ /dev/null
-/*
- * 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 "RegexJIT.h"
-
-#include "ASCIICType.h"
-#include "JSGlobalData.h"
-#include "LinkBuffer.h"
-#include "MacroAssembler.h"
-#include "RegExpCache.h"
-#include "RegexCompiler.h"
-
-#include "pcre.h" // temporary, remove when fallback is removed.
-
-#if ENABLE(YARR_JIT)
-
-using namespace WTF;
-
-namespace JSC { namespace Yarr {
-
-class RegexGenerator : private MacroAssembler {
- friend void jitCompileRegex(JSGlobalData* globalData, RegexCodeBlock& 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(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, Imm32(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(Imm32(32), character);
- for (unsigned i = 0; i < countAZaz; ++i)
- matchDest.append(branch32(Equal, character, Imm32(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(Imm32 imm, unsigned frameLocation)
- {
- poke(imm, frameLocation);
- }
-
- DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
- {
- return storePtrWithPatch(ImmPtr(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 AlternativeBacktrackRecord {
- DataLabelPtr dataLabel;
- Label backtrackLocation;
-
- AlternativeBacktrackRecord(DataLabelPtr dataLabel, Label backtrackLocation)
- : dataLabel(dataLabel)
- , backtrackLocation(backtrackLocation)
- {
- }
- };
-
- struct TermGenerationState {
- TermGenerationState(PatternDisjunction* disjunction, unsigned checkedTotal)
- : disjunction(disjunction)
- , checkedTotal(checkedTotal)
- {
- }
-
- void resetAlternative()
- {
- isBackTrackGenerated = false;
- alt = 0;
- }
- bool alternativeValid()
- {
- return alt < disjunction->m_alternatives.size();
- }
- void nextAlternative()
- {
- ++alt;
- }
- PatternAlternative* alternative()
- {
- return disjunction->m_alternatives[alt];
- }
-
- void resetTerm()
- {
- ASSERT(alternativeValid());
- t = 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];
- }
-
- 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 jumpToBacktrack(Jump jump, MacroAssembler* masm)
- {
- if (isBackTrackGenerated)
- jump.linkTo(backtrackLabel, masm);
- else
- backTrackJumps.append(jump);
- }
- void jumpToBacktrack(JumpList& jumps, MacroAssembler* masm)
- {
- if (isBackTrackGenerated)
- jumps.linkTo(backtrackLabel, masm);
- else
- backTrackJumps.append(jumps);
- }
- bool plantJumpToBacktrackIfExists(MacroAssembler* masm)
- {
- if (isBackTrackGenerated) {
- masm->jump(backtrackLabel);
- return true;
- }
- return false;
- }
- void addBacktrackJump(Jump jump)
- {
- backTrackJumps.append(jump);
- }
- void setBacktrackGenerated(Label label)
- {
- isBackTrackGenerated = true;
- backtrackLabel = label;
- }
- void linkAlternativeBacktracks(MacroAssembler* masm)
- {
- isBackTrackGenerated = false;
- backTrackJumps.link(masm);
- }
- void linkAlternativeBacktracksTo(Label label, MacroAssembler* masm)
- {
- isBackTrackGenerated = false;
- backTrackJumps.linkTo(label, masm);
- }
- void propagateBacktrackingFrom(TermGenerationState& nestedParenthesesState, MacroAssembler* masm)
- {
- jumpToBacktrack(nestedParenthesesState.backTrackJumps, masm);
- if (nestedParenthesesState.isBackTrackGenerated)
- setBacktrackGenerated(nestedParenthesesState.backtrackLabel);
- }
-
- PatternDisjunction* disjunction;
- int checkedTotal;
- private:
- unsigned alt;
- unsigned t;
- JumpList backTrackJumps;
- Label backtrackLabel;
- bool isBackTrackGenerated;
- };
-
- 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(jump(), this);
-
- matchDest.link(this);
- } else {
- // Erk, really should poison out these alternatives early. :-/
- if (term.inputPosition)
- state.jumpToBacktrack(jump(), this);
- else
- state.jumpToBacktrack(branch32(NotEqual, index, Imm32(state.checkedTotal)), this);
- }
- }
-
- 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(jump(), this);
-
- matchDest.link(this);
- } else {
- if (term.inputPosition == state.checkedTotal)
- state.jumpToBacktrack(notAtEndOfInput(), this);
- // Erk, really should poison out these alternatives early. :-/
- else
- state.jumpToBacktrack(jump(), 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.invertOrCapture) {
- matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
- nonWordCharThenWordChar.append(jump());
- } else {
- matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
- nonWordCharThenNonWordChar.append(jump());
- }
- state.jumpToBacktrack(nonWordCharThenNonWordChar, this);
-
- // We jump here if the last character was a wordchar.
- matchDest.link(this);
- JumpList wordCharThenWordChar;
- JumpList wordCharThenNonWordChar;
- if (term.invertOrCapture) {
- matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
- wordCharThenWordChar.append(jump());
- } else {
- matchAssertionWordchar(state, wordCharThenWordChar, wordCharThenNonWordChar);
- // This can fall-though!
- }
-
- state.jumpToBacktrack(wordCharThenWordChar, this);
-
- 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(Imm32(32), character);
- state.jumpToBacktrack(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))), this);
- } else {
- ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
- state.jumpToBacktrack(jumpIfCharNotEquals(ch, state.inputOffset()), this);
- }
- }
-
- 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(branch32(NotEqual, character, Imm32(chPair | mask)), this);
- } else
- state.jumpToBacktrack(branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)), this);
- }
-
- 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(Imm32(32), character);
- state.jumpToBacktrack(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))), this);
- } else {
- ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
- state.jumpToBacktrack(branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)), this);
- }
- add32(Imm32(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(Imm32(0), countRegister);
-
- JumpList failures;
- Label loop(this);
- failures.append(atEndOfInput());
- if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
- readCharacter(state.inputOffset(), character);
- or32(Imm32(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(Imm32(1), countRegister);
- add32(Imm32(1), index);
- if (term.quantityCount != 0xffffffff)
- branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
- else
- jump(loop);
-
- failures.append(jump());
-
- Label backtrackBegin(this);
- loadFromFrame(term.frameLocation, countRegister);
- state.jumpToBacktrack(branchTest32(Zero, countRegister), this);
- sub32(Imm32(1), countRegister);
- sub32(Imm32(1), index);
-
- failures.link(this);
-
- storeToFrame(countRegister, term.frameLocation);
-
- state.setBacktrackGenerated(backtrackBegin);
- }
-
- void generatePatternCharacterNonGreedy(TermGenerationState& state)
- {
- const RegisterID character = regT0;
- const RegisterID countRegister = regT1;
- PatternTerm& term = state.term();
- UChar ch = term.patternCharacter;
-
- move(Imm32(0), countRegister);
-
- Jump firstTimeDoNothing = jump();
-
- Label hardFail(this);
- sub32(countRegister, index);
- state.jumpToBacktrack(jump(), this);
-
- Label backtrackBegin(this);
- loadFromFrame(term.frameLocation, countRegister);
-
- atEndOfInput().linkTo(hardFail, this);
- if (term.quantityCount != 0xffffffff)
- branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
- if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
- readCharacter(state.inputOffset(), character);
- or32(Imm32(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(Imm32(1), countRegister);
- add32(Imm32(1), index);
-
- firstTimeDoNothing.link(this);
- storeToFrame(countRegister, term.frameLocation);
-
- state.setBacktrackGenerated(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.invertOrCapture)
- state.jumpToBacktrack(matchDest, this);
- else {
- state.jumpToBacktrack(jump(), 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.invertOrCapture)
- state.jumpToBacktrack(matchDest, this);
- else {
- state.jumpToBacktrack(jump(), this);
- matchDest.link(this);
- }
-
- add32(Imm32(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(Imm32(0), countRegister);
-
- JumpList failures;
- Label loop(this);
- failures.append(atEndOfInput());
-
- if (term.invertOrCapture) {
- 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(Imm32(1), countRegister);
- add32(Imm32(1), index);
- if (term.quantityCount != 0xffffffff)
- branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
- else
- jump(loop);
-
- failures.append(jump());
-
- Label backtrackBegin(this);
- loadFromFrame(term.frameLocation, countRegister);
- state.jumpToBacktrack(branchTest32(Zero, countRegister), this);
- sub32(Imm32(1), countRegister);
- sub32(Imm32(1), index);
-
- failures.link(this);
-
- storeToFrame(countRegister, term.frameLocation);
-
- state.setBacktrackGenerated(backtrackBegin);
- }
-
- void generateCharacterClassNonGreedy(TermGenerationState& state)
- {
- const RegisterID character = regT0;
- const RegisterID countRegister = regT1;
- PatternTerm& term = state.term();
-
- move(Imm32(0), countRegister);
-
- Jump firstTimeDoNothing = jump();
-
- Label hardFail(this);
- sub32(countRegister, index);
- state.jumpToBacktrack(jump(), 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.invertOrCapture)
- matchDest.linkTo(hardFail, this);
- else {
- jump(hardFail);
- matchDest.link(this);
- }
-
- add32(Imm32(1), countRegister);
- add32(Imm32(1), index);
-
- firstTimeDoNothing.link(this);
- storeToFrame(countRegister, term.frameLocation);
-
- state.setBacktrackGenerated(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.setBacktrackGenerated(backtrackBegin);
-
- state.jumpToBacktrack(jumpIfNoAvailableInput(countToCheck), this);
- state.checkedTotal += countToCheck;
- }
-
- for (state.resetTerm(); state.termValid(); state.nextTerm())
- generateTerm(state);
-
- state.checkedTotal -= countToCheck;
- } else {
- JumpList successes;
-
- for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative()) {
-
- 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);
- successes.append(jump());
-
- // Alternative did not match.
- Label backtrackLocation(this);
-
- // Can we backtrack the alternative? - if so, do so. If not, just fall through to the next one.
- state.plantJumpToBacktrackIfExists(this);
-
- state.linkAlternativeBacktracks(this);
-
- if (countToCheck) {
- sub32(Imm32(countToCheck), index);
- state.checkedTotal -= countToCheck;
- }
-
- m_backtrackRecords.append(AlternativeBacktrackRecord(dataLabel, backtrackLocation));
- }
- // We fall through to here when the last alternative fails.
- // Add a backtrack out of here for the parenthese handling code to link up.
- state.addBacktrackJump(jump());
-
- // Generate a trampoline for the parens code to backtrack to, to retry the
- // next alternative.
- state.setBacktrackGenerated(label());
- loadFromFrameAndJump(alternativeFrameLocation);
-
- // FIXME: both of the above hooks are a little inefficient, in that you
- // may end up trampolining here, just to trampoline back out to the
- // parentheses code, or vice versa. We can probably eliminate a jump
- // by restructuring, but coding this way for now for simplicity during
- // development.
-
- 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.quantityCount == 1) && (term.quantityType == QuantifierFixedCount)) ? disjunction->m_minimumSize : 0;
-
- unsigned parenthesesFrameLocation = term.frameLocation;
- unsigned alternativeFrameLocation = parenthesesFrameLocation;
- if (term.quantityType != QuantifierFixedCount)
- alternativeFrameLocation += RegexStackSpaceForBackTrackInfoParenthesesOnce;
-
- // optimized case - no capture & no quantifier can be handled in a light-weight manner.
- if (!term.invertOrCapture && (term.quantityType == QuantifierFixedCount)) {
- TermGenerationState parenthesesState(disjunction, state.checkedTotal);
- generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
- // this expects that any backtracks back out of the parentheses will be in the
- // parenthesesState's backTrackJumps vector, and that if they need backtracking
- // they will have set an entry point on the parenthesesState's backtrackLabel.
- state.propagateBacktrackingFrom(parenthesesState, this);
- } else {
- Jump nonGreedySkipParentheses;
- Label nonGreedyTryParentheses;
- if (term.quantityType == QuantifierGreedy)
- storeToFrame(Imm32(1), parenthesesFrameLocation);
- else if (term.quantityType == QuantifierNonGreedy) {
- storeToFrame(Imm32(0), parenthesesFrameLocation);
- nonGreedySkipParentheses = jump();
- nonGreedyTryParentheses = label();
- storeToFrame(Imm32(1), parenthesesFrameLocation);
- }
-
- // store the match start index
- if (term.invertOrCapture) {
- 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)));
- }
-
- // generate the body of the parentheses
- TermGenerationState parenthesesState(disjunction, state.checkedTotal);
- generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
-
- // store the match end index
- if (term.invertOrCapture) {
- 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)));
- }
- Jump success = jump();
-
- // A failure AFTER the parens jumps here
- Label backtrackFromAfterParens(this);
-
- if (term.quantityType == QuantifierGreedy) {
- // If this is zero we have now tested with both with and without the parens.
- loadFromFrame(parenthesesFrameLocation, indexTemporary);
- state.jumpToBacktrack(branchTest32(Zero, indexTemporary), this);
- } else if (term.quantityType == QuantifierNonGreedy) {
- // If this is zero we have now tested with both with and without the parens.
- loadFromFrame(parenthesesFrameLocation, indexTemporary);
- branchTest32(Zero, indexTemporary).linkTo(nonGreedyTryParentheses, this);
- }
-
- parenthesesState.plantJumpToBacktrackIfExists(this);
- // A failure WITHIN the parens jumps here
- parenthesesState.linkAlternativeBacktracks(this);
- if (term.invertOrCapture) {
- store32(Imm32(-1), Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
- store32(Imm32(-1), Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
- }
-
- if (term.quantityType == QuantifierGreedy)
- storeToFrame(Imm32(0), parenthesesFrameLocation);
- else
- state.jumpToBacktrack(jump(), this);
-
- state.setBacktrackGenerated(backtrackFromAfterParens);
- if (term.quantityType == QuantifierNonGreedy)
- nonGreedySkipParentheses.link(this);
- success.link(this);
- }
- }
-
- 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 + RegexStackSpaceForBackTrackInfoParentheticalAssertion;
-
- int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;
-
- if (term.invertOrCapture) {
- // 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(jump(), 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(jump(), 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:
- ASSERT_NOT_REACHED();
- break;
-
- case PatternTerm::TypeForwardReference:
- break;
-
- case PatternTerm::TypeParenthesesSubpattern:
- ASSERT((term.quantityCount == 1) && !term.parentheses.isCopy); // must fallback to pcre before this point
- generateParenthesesSingle(state);
- break;
-
- case PatternTerm::TypeParentheticalAssertion:
- generateParentheticalAssertion(state);
- break;
- }
- }
-
- void generateDisjunction(PatternDisjunction* disjunction)
- {
- TermGenerationState state(disjunction, 0);
- state.resetAlternative();
-
- // Plant a check to see if there is sufficient input available to run the first alternative.
- // Jumping back to the label 'firstAlternative' will get to this check, jumping to
- // 'firstAlternativeInputChecked' will jump directly to matching the alternative having
- // skipped this check.
-
- Label firstAlternative(this);
-
- // check availability for the next alternative
- int countCheckedForCurrentAlternative = 0;
- int countToCheckForFirstAlternative = 0;
- bool hasShorterAlternatives = false;
- JumpList notEnoughInputForPreviousAlternative;
-
- if (state.alternativeValid()) {
- PatternAlternative* alternative = state.alternative();
- countToCheckForFirstAlternative = alternative->m_minimumSize;
- state.checkedTotal += countToCheckForFirstAlternative;
- if (countToCheckForFirstAlternative)
- notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
- countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
- }
-
- Label firstAlternativeInputChecked(this);
-
- while (state.alternativeValid()) {
- // Track whether any alternatives are shorter than the first one.
- hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative);
-
- PatternAlternative* alternative = state.alternative();
- optimizeAlternative(alternative);
-
- 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);
- } else
- pop(returnRegister);
- store32(index, Address(output, 4));
- store32(returnRegister, output);
-
- generateReturn();
-
- state.nextAlternative();
-
- // if there are any more alternatives, plant the check for input before looping.
- if (state.alternativeValid()) {
- PatternAlternative* nextAlternative = state.alternative();
- int countToCheckForNextAlternative = nextAlternative->m_minimumSize;
-
- if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one.
- // If we get here, there 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, there 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, there 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;
-
- // 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);
- 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(firstAlternativeInputChecked, this);
- else { // no need to check the input, but we do have some bookkeeping to do first.
- state.linkAlternativeBacktracks(this);
-
- // Where necessary update our preserved start position.
- if (!m_pattern.m_body->m_hasFixedSize) {
- move(index, regT0);
- sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
- poke(regT0, m_pattern.m_body->m_callFrameSize);
- }
-
- // 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);
- poke(regT0, m_pattern.m_body->m_callFrameSize);
- } else
- poke(index, m_pattern.m_body->m_callFrameSize);
- }
- // 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!)
-
- unsigned frameSize = m_pattern.m_body->m_callFrameSize;
- if (!m_pattern.m_body->m_hasFixedSize)
- ++frameSize;
- if (frameSize)
- addPtr(Imm32(frameSize * sizeof(void*)), stackPointerRegister);
-
- move(Imm32(-1), returnRegister);
-
- generateReturn();
- }
-
- 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);
- move(ARMRegisters::r3, output);
-#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)
- pop(ARMRegisters::r6);
- pop(ARMRegisters::r5);
- pop(ARMRegisters::r4);
-#elif CPU(MIPS)
- // Do nothing
-#endif
- ret();
- }
-
-public:
- RegexGenerator(RegexPattern& pattern)
- : m_pattern(pattern)
- {
- }
-
- void generate()
- {
- generateEnter();
-
- // TODO: do I really want this on the stack?
- if (!m_pattern.m_body->m_hasFixedSize)
- push(index);
-
- 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, RegexCodeBlock& jitObject)
- {
- generate();
-
- LinkBuffer patchBuffer(this, globalData->regexAllocator.poolForSize(size()), 0);
-
- for (unsigned i = 0; i < m_backtrackRecords.size(); ++i)
- patchBuffer.patch(m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_backtrackRecords[i].backtrackLocation));
-
- jitObject.set(patchBuffer.finalizeCode());
- }
-
-private:
- RegexPattern& m_pattern;
- Vector<AlternativeBacktrackRecord> m_backtrackRecords;
-};
-
-void jitCompileRegex(JSGlobalData* globalData, RegexCodeBlock& jitObject, const UString& patternString, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline)
-{
- RegexPattern pattern(ignoreCase, multiline);
- if ((error = compileRegex(patternString, pattern)))
- return;
- numSubpatterns = pattern.m_numSubpatterns;
-
- if (!pattern.m_shouldFallBack && globalData->canUseJIT() && RegExpCache::isCacheable(patternString)) {
- RegexGenerator generator(pattern);
- generator.compile(globalData, jitObject);
- return;
- }
-
- JSRegExpIgnoreCaseOption ignoreCaseOption = ignoreCase ? JSRegExpIgnoreCase : JSRegExpDoNotIgnoreCase;
- JSRegExpMultilineOption multilineOption = multiline ? JSRegExpMultiline : JSRegExpSingleLine;
- jitObject.setFallback(jsRegExpCompile(reinterpret_cast<const UChar*>(patternString.data()), patternString.size(), ignoreCaseOption, multilineOption, &numSubpatterns, &error));
-}
-
-}}
-
-#endif
-
-
-
-
-
projects / apple / javascriptcore.git / blobdiff