/*

* Copyright (C) 2009, 2013 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 <wtf/ASCIICType.h>

#include "LinkBuffer.h"

#include "Options.h"

#include "Yarr.h"

#include "YarrCanonicalizeUCS2.h"

#if ENABLE(YARR_JIT)

using namespace WTF;

namespace JSC { namespace Yarr {

template<YarrJITCompileMode compileMode>

class YarrGenerator : private MacroAssembler {

friend void jitCompile(VM*, YarrCodeBlock& jitObject, const String& 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::r3;

static const RegisterID regT0 = ARMRegisters::r4;

static const RegisterID regT1 = ARMRegisters::r5;

static const RegisterID returnRegister = ARMRegisters::r0;

static const RegisterID returnRegister2 = ARMRegisters::r1;

#elif CPU(ARM64)

static const RegisterID input = ARM64Registers::x0;

static const RegisterID index = ARM64Registers::x1;

static const RegisterID length = ARM64Registers::x2;

static const RegisterID output = ARM64Registers::x3;

static const RegisterID regT0 = ARM64Registers::x4;

static const RegisterID regT1 = ARM64Registers::x5;

static const RegisterID returnRegister = ARM64Registers::x0;

static const RegisterID returnRegister2 = ARM64Registers::x1;

#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;

static const RegisterID returnRegister2 = MIPSRegisters::v1;

#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;

static const RegisterID returnRegister2 = SH4Registers::r1;

#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;

static const RegisterID returnRegister2 = X86Registers::edx;

#elif CPU(X86_64)

#if !OS(WINDOWS)

static const RegisterID input = X86Registers::edi;

static const RegisterID index = X86Registers::esi;

static const RegisterID length = X86Registers::edx;

static const RegisterID output = X86Registers::ecx;

#else

// If the return value doesn't fit in 64bits, its destination is pointed by rcx and the parameters are shifted.

// http://msdn.microsoft.com/en-us/library/7572ztz4.aspx

COMPILE_ASSERT(sizeof(MatchResult) > sizeof(void*), MatchResult_does_not_fit_in_64bits);

static const RegisterID input = X86Registers::edx;

static const RegisterID index = X86Registers::r8;

static const RegisterID length = X86Registers::r9;

static const RegisterID output = X86Registers::r10;

#endif

static const RegisterID regT0 = X86Registers::eax;

static const RegisterID regT1 = X86Registers::ebx;

static const RegisterID returnRegister = X86Registers::eax;

static const RegisterID returnRegister2 = X86Registers::edx;

#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));

matchDest.append(branchTest8(charClass->m_tableInverted ? Zero : NonZero, tableEntry));

return;

}

Jump unicodeFail;

if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {

Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f));

if (charClass->m_matchesUnicode.size()) {

for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {

UChar ch = charClass->m_matchesUnicode[i];

matchDest.append(branch32(Equal, character, Imm32(ch)));

}

}

if (charClass->m_rangesUnicode.size()) {

for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {

UChar lo = charClass->m_rangesUnicode[i].begin;

UChar hi = charClass->m_rangesUnicode[i].end;

Jump below = branch32(LessThan, character, Imm32(lo));

matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));

below.link(this);

}

}

unicodeFail = jump();

isAscii.link(this);

}

if (charClass->m_ranges.size()) {

unsigned matchIndex = 0;

JumpList failures;

matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());

while (matchIndex < charClass->m_matches.size())

matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));

failures.link(this);

} else if (charClass->m_matches.size()) {

// optimization: gather 'a','A' etc back together, can mask & test once.

Vector<char> matchesAZaz;

for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {

char ch = charClass->m_matches[i];

if (m_pattern.m_ignoreCase) {

if (isASCIILower(ch)) {

matchesAZaz.append(ch);

continue;

}

if (isASCIIUpper(ch))

continue;

}

matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));

}

if (unsigned countAZaz = matchesAZaz.size()) {

or32(TrustedImm32(32), character);

for (unsigned i = 0; i < countAZaz; ++i)

matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));

}

}

if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())

unicodeFail.link(this);

}

// Jumps if input not available; will have (incorrectly) incremented already!

Jump jumpIfNoAvailableInput(unsigned countToCheck = 0)

{

if (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 jumpIfCharNotEquals(UChar ch, int inputPosition, RegisterID character)

{

readCharacter(inputPosition, character);

// For case-insesitive compares, non-ascii characters that have different

// upper & lower case representations are converted to a character class.

ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));

if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {

or32(TrustedImm32(0x20), character);

ch |= 0x20;

}

return branch32(NotEqual, character, Imm32(ch));

}

void readCharacter(int inputPosition, RegisterID reg)

{

if (m_charSize == Char8)

load8(BaseIndex(input, index, TimesOne, inputPosition * sizeof(char)), reg);

else

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*)));

}

unsigned alignCallFrameSizeInBytes(unsigned callFrameSize)

{

callFrameSize *= sizeof(void*);

if (callFrameSize / sizeof(void*) != m_pattern.m_body->m_callFrameSize)

CRASH();

callFrameSize = (callFrameSize + 0x3f) & ~0x3f;

if (!callFrameSize)

CRASH();

return callFrameSize;

}

void initCallFrame()

{

unsigned callFrameSize = m_pattern.m_body->m_callFrameSize;

if (callFrameSize)

subPtr(Imm32(alignCallFrameSizeInBytes(callFrameSize)), stackPointerRegister);

}

void removeCallFrame()

{

unsigned callFrameSize = m_pattern.m_body->m_callFrameSize;

if (callFrameSize)

addPtr(Imm32(alignCallFrameSizeInBytes(callFrameSize)), stackPointerRegister);

}

// Used to record subpatters, should only be called if compileMode is IncludeSubpatterns.

void setSubpatternStart(RegisterID reg, unsigned subpattern)

{

ASSERT(subpattern);

// FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(

store32(reg, Address(output, (subpattern << 1) * sizeof(int)));

}

void setSubpatternEnd(RegisterID reg, unsigned subpattern)

{

ASSERT(subpattern);

// FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(

store32(reg, Address(output, ((subpattern << 1) + 1) * sizeof(int)));

}

void clearSubpatternStart(unsigned subpattern)

{

ASSERT(subpattern);

// FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(

store32(TrustedImm32(-1), Address(output, (subpattern << 1) * sizeof(int)));

}

// We use one of three different strategies to track the start of the current match,

// while matching.

// 1) If the pattern has a fixed size, do nothing! - we calculate the value lazily

// at the end of matching. This is irrespective of compileMode, and in this case

// these methods should never be called.

// 2) If we're compiling IncludeSubpatterns, 'output' contains a pointer to an output

// vector, store the match start in the output vector.

// 3) If we're compiling MatchOnly, 'output' is unused, store the match start directly

// in this register.

void setMatchStart(RegisterID reg)

{

ASSERT(!m_pattern.m_body->m_hasFixedSize);

if (compileMode == IncludeSubpatterns)

store32(reg, output);

else

move(reg, output);

}

void getMatchStart(RegisterID reg)

{

ASSERT(!m_pattern.m_body->m_hasFixedSize);

if (compileMode == IncludeSubpatterns)

load32(output, reg);

else

move(output, reg);

}

enum YarrOpCode {

// These nodes wrap body alternatives - those in the main disjunction,

// rather than subpatterns or assertions. These are chained together in

// a doubly linked list, with a 'begin' node for the first alternative,

// a 'next' node for each subsequent alternative, and an 'end' node at

// the end. In the case of repeating alternatives, the 'end' node also

// has a reference back to 'begin'.

OpBodyAlternativeBegin,

OpBodyAlternativeNext,

OpBodyAlternativeEnd,

// Similar to the body alternatives, but used for subpatterns with two

// or more alternatives.

OpNestedAlternativeBegin,

OpNestedAlternativeNext,

OpNestedAlternativeEnd,

// Used for alternatives in subpatterns where there is only a single

// alternative (backtrackingis easier in these cases), or for alternatives

// which never need to be backtracked (those in parenthetical assertions,

// terminal subpatterns).

OpSimpleNestedAlternativeBegin,

OpSimpleNestedAlternativeNext,

OpSimpleNestedAlternativeEnd,

// Used to wrap 'Once' subpattern matches (quantityCount == 1).

OpParenthesesSubpatternOnceBegin,

OpParenthesesSubpatternOnceEnd,

// Used to wrap 'Terminal' subpattern matches (at the end of the regexp).

OpParenthesesSubpatternTerminalBegin,

OpParenthesesSubpatternTerminalEnd,

// Used to wrap parenthetical assertions.

OpParentheticalAssertionBegin,

OpParentheticalAssertionEnd,

// Wraps all simple terms (pattern characters, character classes).

OpTerm,

// Where an expression contains only 'once through' body alternatives

// and no repeating ones, this op is used to return match failure.

OpMatchFailed

};

// This structure is used to hold the compiled opcode information,

// including reference back to the original PatternTerm/PatternAlternatives,

// and JIT compilation data structures.

struct YarrOp {

explicit YarrOp(PatternTerm* term)

: m_op(OpTerm)

, m_term(term)

, m_isDeadCode(false)

{

}

explicit YarrOp(YarrOpCode op)

: m_op(op)

, m_isDeadCode(false)

{

}

// The operation, as a YarrOpCode, and also a reference to the PatternTerm.

YarrOpCode m_op;

PatternTerm* m_term;

// For alternatives, this holds the PatternAlternative and doubly linked

// references to this alternative's siblings. In the case of the

// OpBodyAlternativeEnd node at the end of a section of repeating nodes,

// m_nextOp will reference the OpBodyAlternativeBegin node of the first

// repeating alternative.

PatternAlternative* m_alternative;

size_t m_previousOp;

size_t m_nextOp;

// Used to record a set of Jumps out of the generated code, typically

// used for jumps out to backtracking code, and a single reentry back

// into the code for a node (likely where a backtrack will trigger

// rematching).

Label m_reentry;

JumpList m_jumps;

// Used for backtracking when the prior alternative did not consume any

// characters but matched.

Jump m_zeroLengthMatch;

// This flag is used to null out the second pattern character, when

// two are fused to match a pair together.

bool m_isDeadCode;

// Currently used in the case of some of the more complex management of

// 'm_checked', to cache the offset used in this alternative, to avoid

// recalculating it.

int m_checkAdjust;

// Used by OpNestedAlternativeNext/End to hold the pointer to the

// value that will be pushed into the pattern's frame to return to,

// upon backtracking back into the disjunction.

DataLabelPtr m_returnAddress;

};

// BacktrackingState

// This class encapsulates information about the state of code generation

// whilst generating the code for backtracking, when a term fails to match.

// Upon entry to code generation of the backtracking code for a given node,

// the Backtracking state will hold references to all control flow sources

// that are outputs in need of further backtracking from the prior node

// generated (which is the subsequent operation in the regular expression,

// and in the m_ops Vector, since we generated backtracking backwards).

// These references to control flow take the form of:

// - A jump list of jumps, to be linked to code that will backtrack them

// further.

// - A set of DataLabelPtr values, to be populated with values to be

// treated effectively as return addresses backtracking into complex

// subpatterns.

// - A flag indicating that the current sequence of generated code up to

// this point requires backtracking.

class BacktrackingState {

public:

BacktrackingState()

: m_pendingFallthrough(false)

{

}

// Add a jump or jumps, a return address, or set the flag indicating

// that the current 'fallthrough' control flow requires backtracking.

void append(const Jump& jump)

{

m_laterFailures.append(jump);

}

void append(JumpList& jumpList)

{

m_laterFailures.append(jumpList);

}

void append(const DataLabelPtr& returnAddress)

{

m_pendingReturns.append(returnAddress);

}

void fallthrough()

{

ASSERT(!m_pendingFallthrough);

m_pendingFallthrough = true;

}

// These methods clear the backtracking state, either linking to the

// current location, a provided label, or copying the backtracking out

// to a JumpList. All actions may require code generation to take place,

// and as such are passed a pointer to the assembler.

void link(MacroAssembler* assembler)

{

if (m_pendingReturns.size()) {

Label here(assembler);

for (unsigned i = 0; i < m_pendingReturns.size(); ++i)

m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));

m_pendingReturns.clear();

}

m_laterFailures.link(assembler);

m_laterFailures.clear();

m_pendingFallthrough = false;

}

void linkTo(Label label, MacroAssembler* assembler)

{

if (m_pendingReturns.size()) {

for (unsigned i = 0; i < m_pendingReturns.size(); ++i)

m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], label));

m_pendingReturns.clear();

}

if (m_pendingFallthrough)

assembler->jump(label);

m_laterFailures.linkTo(label, assembler);

m_laterFailures.clear();

m_pendingFallthrough = false;

}

void takeBacktracksToJumpList(JumpList& jumpList, MacroAssembler* assembler)

{

if (m_pendingReturns.size()) {

Label here(assembler);

for (unsigned i = 0; i < m_pendingReturns.size(); ++i)

m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));

m_pendingReturns.clear();

m_pendingFallthrough = true;

}

if (m_pendingFallthrough)

jumpList.append(assembler->jump());

jumpList.append(m_laterFailures);

m_laterFailures.clear();

m_pendingFallthrough = false;

}

bool isEmpty()

{

return m_laterFailures.empty() && m_pendingReturns.isEmpty() && !m_pendingFallthrough;

}

// Called at the end of code generation to link all return addresses.

void linkDataLabels(LinkBuffer& linkBuffer)

{

ASSERT(isEmpty());

for (unsigned i = 0; i < m_backtrackRecords.size(); ++i)

linkBuffer.patch(m_backtrackRecords[i].m_dataLabel, linkBuffer.locationOf(m_backtrackRecords[i].m_backtrackLocation));

}

private:

struct ReturnAddressRecord {

ReturnAddressRecord(DataLabelPtr dataLabel, Label backtrackLocation)

: m_dataLabel(dataLabel)

, m_backtrackLocation(backtrackLocation)

{

}

DataLabelPtr m_dataLabel;

Label m_backtrackLocation;

};

JumpList m_laterFailures;

bool m_pendingFallthrough;

Vector<DataLabelPtr, 4> m_pendingReturns;

Vector<ReturnAddressRecord, 4> m_backtrackRecords;

};

// Generation methods:

// ===================

// This method provides a default implementation of backtracking common

// to many terms; terms commonly jump out of the forwards matching path

// on any failed conditions, and add these jumps to the m_jumps list. If

// no special handling is required we can often just backtrack to m_jumps.

void backtrackTermDefault(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

m_backtrackingState.append(op.m_jumps);

}

void generateAssertionBOL(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

if (m_pattern.m_multiline) {

const RegisterID character = regT0;

JumpList matchDest;

if (!term->inputPosition)

matchDest.append(branch32(Equal, index, Imm32(m_checked)));

readCharacter((term->inputPosition - m_checked) - 1, character);

matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());

op.m_jumps.append(jump());

matchDest.link(this);

} else {

// Erk, really should poison out these alternatives early. :-/

if (term->inputPosition)

op.m_jumps.append(jump());

else

op.m_jumps.append(branch32(NotEqual, index, Imm32(m_checked)));

}

}

void backtrackAssertionBOL(size_t opIndex)

{

backtrackTermDefault(opIndex);

}

void generateAssertionEOL(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

if (m_pattern.m_multiline) {

const RegisterID character = regT0;

JumpList matchDest;

if (term->inputPosition == m_checked)

matchDest.append(atEndOfInput());

readCharacter(term->inputPosition - m_checked, character);

matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());

op.m_jumps.append(jump());

matchDest.link(this);

} else {

if (term->inputPosition == m_checked)

op.m_jumps.append(notAtEndOfInput());

// Erk, really should poison out these alternatives early. :-/

else

op.m_jumps.append(jump());

}

}

void backtrackAssertionEOL(size_t opIndex)

{

backtrackTermDefault(opIndex);

}

// Also falls though on nextIsNotWordChar.

void matchAssertionWordchar(size_t opIndex, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

const RegisterID character = regT0;

if (term->inputPosition == m_checked)

nextIsNotWordChar.append(atEndOfInput());

readCharacter((term->inputPosition - m_checked), character);

matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());

}

void generateAssertionWordBoundary(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

const RegisterID character = regT0;

Jump atBegin;

JumpList matchDest;

if (!term->inputPosition)

atBegin = branch32(Equal, index, Imm32(m_checked));

readCharacter((term->inputPosition - m_checked) - 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(opIndex, nonWordCharThenNonWordChar, nonWordCharThenWordChar);

nonWordCharThenWordChar.append(jump());

} else {

matchAssertionWordchar(opIndex, nonWordCharThenWordChar, nonWordCharThenNonWordChar);

nonWordCharThenNonWordChar.append(jump());

}

op.m_jumps.append(nonWordCharThenNonWordChar);

// We jump here if the last character was a wordchar.

matchDest.link(this);

JumpList wordCharThenWordChar;

JumpList wordCharThenNonWordChar;

if (term->invert()) {

matchAssertionWordchar(opIndex, wordCharThenNonWordChar, wordCharThenWordChar);

wordCharThenWordChar.append(jump());

} else {

matchAssertionWordchar(opIndex, wordCharThenWordChar, wordCharThenNonWordChar);

// This can fall-though!

}

op.m_jumps.append(wordCharThenWordChar);

nonWordCharThenWordChar.link(this);

wordCharThenNonWordChar.link(this);

}

void backtrackAssertionWordBoundary(size_t opIndex)

{

backtrackTermDefault(opIndex);

}

void generatePatternCharacterOnce(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

if (op.m_isDeadCode)

return;

// m_ops always ends with a OpBodyAlternativeEnd or OpMatchFailed

// node, so there must always be at least one more node.

ASSERT(opIndex + 1 < m_ops.size());

YarrOp* nextOp = &m_ops[opIndex + 1];

PatternTerm* term = op.m_term;

UChar ch = term->patternCharacter;

if ((ch > 0xff) && (m_charSize == Char8)) {

// Have a 16 bit pattern character and an 8 bit string - short circuit

op.m_jumps.append(jump());

return;

}

const RegisterID character = regT0;

int maxCharactersAtOnce = m_charSize == Char8 ? 4 : 2;

unsigned ignoreCaseMask = 0;

#if CPU(BIG_ENDIAN)

int allCharacters = ch << (m_charSize == Char8 ? 24 : 16);

#else

int allCharacters = ch;

#endif

int numberCharacters;

int startTermPosition = term->inputPosition;

// For case-insesitive compares, non-ascii characters that have different

// upper & lower case representations are converted to a character class.

ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));

if (m_pattern.m_ignoreCase && isASCIIAlpha(ch))

#if CPU(BIG_ENDIAN)

ignoreCaseMask |= 32 << (m_charSize == Char8 ? 24 : 16);

#else

ignoreCaseMask |= 32;

#endif

for (numberCharacters = 1; numberCharacters < maxCharactersAtOnce && nextOp->m_op == OpTerm; ++numberCharacters, nextOp = &m_ops[opIndex + numberCharacters]) {

PatternTerm* nextTerm = nextOp->m_term;

if (nextTerm->type != PatternTerm::TypePatternCharacter

|| nextTerm->quantityType != QuantifierFixedCount

|| nextTerm->quantityCount != 1

|| nextTerm->inputPosition != (startTermPosition + numberCharacters))

break;

nextOp->m_isDeadCode = true;

#if CPU(BIG_ENDIAN)

int shiftAmount = (m_charSize == Char8 ? 24 : 16) - ((m_charSize == Char8 ? 8 : 16) * numberCharacters);

#else

int shiftAmount = (m_charSize == Char8 ? 8 : 16) * numberCharacters;

#endif

UChar currentCharacter = nextTerm->patternCharacter;

if ((currentCharacter > 0xff) && (m_charSize == Char8)) {

// Have a 16 bit pattern character and an 8 bit string - short circuit

op.m_jumps.append(jump());

return;

}

// For case-insesitive compares, non-ascii characters that have different

// upper & lower case representations are converted to a character class.

ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(currentCharacter) || isCanonicallyUnique(currentCharacter));

allCharacters |= (currentCharacter << shiftAmount);

if ((m_pattern.m_ignoreCase) && (isASCIIAlpha(currentCharacter)))

ignoreCaseMask |= 32 << shiftAmount;

}

if (m_charSize == Char8) {

switch (numberCharacters) {

case 1:

op.m_jumps.append(jumpIfCharNotEquals(ch, startTermPosition - m_checked, character));

return;

case 2: {

BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));

load16Unaligned(address, character);

break;

}

case 3: {

BaseIndex highAddress(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));

load16Unaligned(highAddress, character);

if (ignoreCaseMask)

or32(Imm32(ignoreCaseMask), character);

op.m_jumps.append(branch32(NotEqual, character, Imm32((allCharacters & 0xffff) | ignoreCaseMask)));

op.m_jumps.append(jumpIfCharNotEquals(allCharacters >> 16, startTermPosition + 2 - m_checked, character));

return;

}

case 4: {

BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));

load32WithUnalignedHalfWords(address, character);

break;

}

}

} else {

switch (numberCharacters) {

case 1:

op.m_jumps.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));

return;

case 2:

BaseIndex address(input, index, TimesTwo, (term->inputPosition - m_checked) * sizeof(UChar));

load32WithUnalignedHalfWords(address, character);

break;

}

}

if (ignoreCaseMask)

or32(Imm32(ignoreCaseMask), character);

op.m_jumps.append(branch32(NotEqual, character, Imm32(allCharacters | ignoreCaseMask)));

return;

}

void backtrackPatternCharacterOnce(size_t opIndex)

{

backtrackTermDefault(opIndex);

}

void generatePatternCharacterFixed(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

UChar ch = term->patternCharacter;

const RegisterID character = regT0;

const RegisterID countRegister = regT1;

move(index, countRegister);

sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);

Label loop(this);

BaseIndex address(input, countRegister, m_charScale, (Checked<int>(term->inputPosition - m_checked + Checked<int64_t>(term->quantityCount)) * static_cast<int>(m_charSize == Char8 ? sizeof(char) : sizeof(UChar))).unsafeGet());

if (m_charSize == Char8)

load8(address, character);

else

load16(address, character);

// For case-insesitive compares, non-ascii characters that have different

// upper & lower case representations are converted to a character class.

ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));

if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {

or32(TrustedImm32(0x20), character);

ch |= 0x20;

}

op.m_jumps.append(branch32(NotEqual, character, Imm32(ch)));

add32(TrustedImm32(1), countRegister);

branch32(NotEqual, countRegister, index).linkTo(loop, this);

}

void backtrackPatternCharacterFixed(size_t opIndex)

{

backtrackTermDefault(opIndex);

}

void generatePatternCharacterGreedy(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

UChar ch = term->patternCharacter;

const RegisterID character = regT0;

const RegisterID countRegister = regT1;

move(TrustedImm32(0), countRegister);

// Unless have a 16 bit pattern character and an 8 bit string - short circuit

if (!((ch > 0xff) && (m_charSize == Char8))) {

JumpList failures;

Label loop(this);

failures.append(atEndOfInput());

failures.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));

add32(TrustedImm32(1), countRegister);

add32(TrustedImm32(1), index);

if (term->quantityCount == quantifyInfinite)

jump(loop);

else

branch32(NotEqual, countRegister, Imm32(term->quantityCount.unsafeGet())).linkTo(loop, this);

failures.link(this);

}

op.m_reentry = label();

storeToFrame(countRegister, term->frameLocation);

}

void backtrackPatternCharacterGreedy(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

const RegisterID countRegister = regT1;

m_backtrackingState.link(this);

loadFromFrame(term->frameLocation, countRegister);

m_backtrackingState.append(branchTest32(Zero, countRegister));

sub32(TrustedImm32(1), countRegister);

sub32(TrustedImm32(1), index);

jump(op.m_reentry);

}

void generatePatternCharacterNonGreedy(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

const RegisterID countRegister = regT1;

move(TrustedImm32(0), countRegister);

op.m_reentry = label();

storeToFrame(countRegister, term->frameLocation);

}

void backtrackPatternCharacterNonGreedy(size_t opIndex)

{

YarrOp& op = m_ops[opIndex];

PatternTerm* term = op.m_term;

UChar ch = term->patternCharacter;

const RegisterID character = regT0;

const RegisterID countRegister = regT1;

m_backtrackingState.link(this);

loadFromFrame(term->frameLocation, countRegister);

// Unless have a 16 bit pattern character and an 8 bit string - short circuit

if (!((ch > 0xff) && (m_charSize == Char8))) {

JumpList nonGreedyFailures;

nonGreedyFailures.append(atEndOfInput());

if (term->quantityCount != quantifyInfinite)

nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));

nonGreedyFailures.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));

add32(TrustedImm32(1), countRegister);

add32(TrustedImm32(1), index);

jump(op.m_reentry);