/*

* Copyright (C) 2009-2021 Apple Inc. All rights reserved.

* Copyright (C) 2019 the V8 project authors. 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 "CCallHelpers.h"

#include "LinkBuffer.h"

#include "Options.h"

#include "VM.h"

#include "Yarr.h"

#include "YarrCanonicalize.h"

#include "YarrDisassembler.h"

#include "YarrJITRegisters.h"

#include "YarrMatchingContextHolder.h"

#include <wtf/ASCIICType.h>

#include <wtf/HexNumber.h>

#include <wtf/ListDump.h>

#include <wtf/Threading.h>

#if ENABLE(YARR_JIT)

namespace JSC { namespace Yarr {

namespace YarrJITInternal {

static constexpr bool verbose = false;

}

#if CPU(ARM64E)

JSC_ANNOTATE_JIT_OPERATION_RETURN(vmEntryToYarrJITAfter);

#endif

void BoyerMooreFastCandidates::dump(PrintStream& out) const

{

if (!isValid()) {

out.print("isValid:(false)");

return;

}

out.print("isValid:(true),characters:(", listDump(m_characters), ")");

}

class BoyerMooreInfo {

WTF_MAKE_NONCOPYABLE(BoyerMooreInfo);

WTF_MAKE_FAST_ALLOCATED(BoyerMooreInfo);

public:

static constexpr unsigned maxLength = 32;

explicit BoyerMooreInfo(CharSize charSize, unsigned length)

: m_characters(length)

, m_charSize(charSize)

{

ASSERT(this->length() <= maxLength);

}

unsigned length() const { return m_characters.size(); }

void shortenLength(unsigned length)

{

ASSERT(length <= this->length());

m_characters.shrink(length);

}

void set(unsigned index, UChar32 character)

{

m_characters[index].add(m_charSize, character);

}

void setAll(unsigned index)

{

m_characters[index].setAll();

}

void addCharacters(unsigned index, const Vector<UChar32>& characters)

{

m_characters[index].addCharacters(m_charSize, characters);

}

void addRanges(unsigned index, const Vector<CharacterRange>& range)

{

m_characters[index].addRanges(m_charSize, range);

}

static UniqueRef<BoyerMooreInfo> create(CharSize charSize, unsigned length)

{

return makeUniqueRef<BoyerMooreInfo>(charSize, length);

}

std::optional<std::tuple<unsigned, unsigned>> findWorthwhileCharacterSequenceForLookahead() const;

std::tuple<BoyerMooreBitmap::Map, BoyerMooreFastCandidates> createCandidateBitmap(unsigned begin, unsigned end) const;

private:

std::tuple<int, unsigned, unsigned> findBestCharacterSequence(unsigned numberOfCandidatesLimit) const;

Vector<BoyerMooreBitmap> m_characters;

CharSize m_charSize;

};

std::tuple<int, unsigned, unsigned> BoyerMooreInfo::findBestCharacterSequence(unsigned numberOfCandidatesLimit) const

{

int biggestPoint = 0;

unsigned beginResult = 0;

unsigned endResult = 0;

for (unsigned index = 0; index < length();) {

while (index < length() && m_characters[index].count() > numberOfCandidatesLimit)

++index;

if (index == length())

break;

unsigned begin = index;

BoyerMooreBitmap::Map map { };

for (; index < length() && m_characters[index].count() <= numberOfCandidatesLimit; ++index)

map.merge(m_characters[index].map());

// If map has many candidates, then point of this sequence is low since it will match too many things.

// And if the sequence is longer, then the point of this sequence is higher since it can skip many characters.

// FIXME: Currently we are handling all characters equally. But we should have weight per character since e.g. 'e' should appear more frequently than '\v'.

// https://bugs.webkit.org/show_bug.cgi?id=228610

int frequency = map.count();

int matchingProbability = BoyerMooreBitmap::mapSize - frequency;

int point = (index - begin) * matchingProbability;

if (point > biggestPoint) {

biggestPoint = point;

beginResult = begin;

endResult = index;

}

}

return std::tuple { biggestPoint, beginResult, endResult };

}

std::optional<std::tuple<unsigned, unsigned>> BoyerMooreInfo::findWorthwhileCharacterSequenceForLookahead() const

{

// If candiates-per-character becomes larger, then sequence is not profitable since this sequence will match against

// too many characters. But if we limit candiates-per-character smaller, it is possible that we only find very short

// character sequence. We start with low limit, then enlarging the limit to find more and more profitable

// character sequence.

int biggestPoint = 0;

unsigned begin = 0;

unsigned end = 0;

constexpr unsigned maxCandidatesPerCharacter = 32;

static_assert(maxCandidatesPerCharacter < BoyerMooreBitmap::mapSize);

for (unsigned limit = 4; limit < maxCandidatesPerCharacter; limit *= 2) {

auto [newPoint, newBegin, newEnd] = findBestCharacterSequence(limit);

if (newPoint > biggestPoint) {

biggestPoint = newPoint;

begin = newBegin;

end = newEnd;

}

}

if (!biggestPoint)

return std::nullopt;

return std::tuple { begin, end };

}

std::tuple<BoyerMooreBitmap::Map, BoyerMooreFastCandidates> BoyerMooreInfo::createCandidateBitmap(unsigned begin, unsigned end) const

{

BoyerMooreBitmap::Map map { };

BoyerMooreFastCandidates charactersFastPath;

for (unsigned index = begin; index < end; ++index) {

auto& bmBitmap = m_characters[index];

map.merge(bmBitmap.map());

charactersFastPath.merge(bmBitmap.charactersFastPath());

}

return std::tuple { WTFMove(map), WTFMove(charactersFastPath) };

}

template<class YarrJITRegs = YarrJITDefaultRegisters>

class YarrGenerator final : public YarrJITInfo {

#if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)

struct ParenContextSizes {

size_t m_numSubpatterns;

size_t m_frameSlots;

ParenContextSizes(size_t numSubpatterns, size_t frameSlots)

: m_numSubpatterns(numSubpatterns)

, m_frameSlots(frameSlots)

{

}

size_t numSubpatterns() { return m_numSubpatterns; }

size_t frameSlots() { return m_frameSlots; }

};

struct ParenContext {

struct ParenContext* next;

struct BeginAndMatchAmount {

uint32_t begin;

uint32_t matchAmount;

} beginAndMatchAmount;

uintptr_t returnAddress;

struct Subpatterns {

unsigned start;

unsigned end;

} subpatterns[0];

uintptr_t frameSlots[0];

static size_t sizeFor(ParenContextSizes& parenContextSizes)

{

return sizeof(ParenContext) + sizeof(Subpatterns) * parenContextSizes.numSubpatterns() + sizeof(uintptr_t) * parenContextSizes.frameSlots();

}

static constexpr ptrdiff_t nextOffset()

{

return offsetof(ParenContext, next);

}

static constexpr ptrdiff_t beginOffset()

{

return offsetof(ParenContext, beginAndMatchAmount) + offsetof(BeginAndMatchAmount, begin);

}

static constexpr ptrdiff_t matchAmountOffset()

{

return offsetof(ParenContext, beginAndMatchAmount) + offsetof(BeginAndMatchAmount, matchAmount);

}

static constexpr ptrdiff_t returnAddressOffset()

{

return offsetof(ParenContext, returnAddress);

}

static constexpr ptrdiff_t subpatternOffset(size_t subpattern)

{

return offsetof(ParenContext, subpatterns) + (subpattern - 1) * sizeof(Subpatterns);

}

static ptrdiff_t savedFrameOffset(ParenContextSizes& parenContextSizes)

{

return offsetof(ParenContext, subpatterns) + (parenContextSizes.numSubpatterns()) * sizeof(Subpatterns);

}

};

void initParenContextFreeList()

{

MacroAssembler::RegisterID parenContextPointer = m_regs.regT0;

MacroAssembler::RegisterID nextParenContextPointer = m_regs.regT2;

m_usesT2 = true;

size_t parenContextSize = ParenContext::sizeFor(m_parenContextSizes);

parenContextSize = WTF::roundUpToMultipleOf<sizeof(uintptr_t)>(parenContextSize);

if (parenContextSize > VM::patternContextBufferSize) {

m_failureReason = JITFailureReason::ParenthesisNestedTooDeep;

return;

}

m_jit.load32(MacroAssembler::Address(m_regs.matchingContext, MatchingContextHolder::offsetOfPatternContextBufferSize()), m_regs.freelistSizeRegister);

// Note that matchingContext and freelistRegister are likely the same register.

m_jit.loadPtr(MacroAssembler::Address(m_regs.matchingContext, MatchingContextHolder::offsetOfPatternContextBuffer()), m_regs.freelistRegister);

MacroAssembler::Jump emptyFreeList = m_jit.branchTestPtr(MacroAssembler::Zero, m_regs.freelistRegister);

m_jit.move(m_regs.freelistRegister, parenContextPointer);

m_jit.addPtr(MacroAssembler::TrustedImm32(parenContextSize), m_regs.freelistRegister, nextParenContextPointer);

m_jit.addPtr(m_regs.freelistRegister, m_regs.freelistSizeRegister);

m_jit.subPtr(MacroAssembler::TrustedImm32(parenContextSize), m_regs.freelistSizeRegister);

MacroAssembler::Label loopTop(&m_jit);

MacroAssembler::Jump initDone = m_jit.branchPtr(MacroAssembler::Above, nextParenContextPointer, m_regs.freelistSizeRegister);

m_jit.storePtr(nextParenContextPointer, MacroAssembler::Address(parenContextPointer, ParenContext::nextOffset()));

m_jit.move(nextParenContextPointer, parenContextPointer);

m_jit.addPtr(MacroAssembler::TrustedImm32(parenContextSize), parenContextPointer, nextParenContextPointer);

m_jit.jump(loopTop);

initDone.link(&m_jit);

m_jit.storePtr(MacroAssembler::TrustedImmPtr(nullptr), MacroAssembler::Address(parenContextPointer, ParenContext::nextOffset()));

emptyFreeList.link(&m_jit);

}

void allocateParenContext(MacroAssembler::RegisterID result)

{

m_abortExecution.append(m_jit.branchTestPtr(MacroAssembler::Zero, m_regs.freelistRegister));

m_jit.sub32(MacroAssembler::TrustedImm32(1), m_regs.remainingMatchCount);

m_hitMatchLimit.append(m_jit.branchTestPtr(MacroAssembler::Zero, m_regs.remainingMatchCount));

m_jit.move(m_regs.freelistRegister, result);

m_jit.loadPtr(MacroAssembler::Address(m_regs.freelistRegister, ParenContext::nextOffset()), m_regs.freelistRegister);

}

void freeParenContext(MacroAssembler::RegisterID headPtrRegister, MacroAssembler::RegisterID newHeadPtrRegister)

{

m_jit.loadPtr(MacroAssembler::Address(headPtrRegister, ParenContext::nextOffset()), newHeadPtrRegister);

m_jit.storePtr(m_regs.freelistRegister, MacroAssembler::Address(headPtrRegister, ParenContext::nextOffset()));

m_jit.move(headPtrRegister, m_regs.freelistRegister);

}

void storeBeginAndMatchAmountToParenContext(MacroAssembler::RegisterID beginGPR, MacroAssembler::RegisterID matchAmountGPR, MacroAssembler::RegisterID parenContextGPR)

{

static_assert(ParenContext::beginOffset() + 4 == ParenContext::matchAmountOffset());

m_jit.storePair32(beginGPR, matchAmountGPR, parenContextGPR, MacroAssembler::TrustedImm32(ParenContext::beginOffset()));

}

void loadBeginAndMatchAmountFromParenContext(MacroAssembler::RegisterID parenContextGPR, MacroAssembler::RegisterID beginGPR, MacroAssembler::RegisterID matchAmountGPR)

{

static_assert(ParenContext::beginOffset() + 4 == ParenContext::matchAmountOffset());

m_jit.loadPair32(parenContextGPR, MacroAssembler::TrustedImm32(ParenContext::beginOffset()), beginGPR, matchAmountGPR);

}

void saveParenContext(MacroAssembler::RegisterID parenContextReg, MacroAssembler::RegisterID tempReg, unsigned firstSubpattern, unsigned lastSubpattern, unsigned subpatternBaseFrameLocation)

{

loadFromFrame(subpatternBaseFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), tempReg);

storeBeginAndMatchAmountToParenContext(m_regs.index, tempReg, parenContextReg);

loadFromFrame(subpatternBaseFrameLocation + BackTrackInfoParentheses::returnAddressIndex(), tempReg);

m_jit.storePtr(tempReg, MacroAssembler::Address(parenContextReg, ParenContext::returnAddressOffset()));

if (m_compileMode == JITCompileMode::IncludeSubpatterns) {

for (unsigned subpattern = firstSubpattern; subpattern <= lastSubpattern; subpattern++) {

static_assert(is64Bit());

m_jit.load64(MacroAssembler::Address(m_regs.output, (subpattern << 1) * sizeof(unsigned)), tempReg);

m_jit.store64(tempReg, MacroAssembler::Address(parenContextReg, ParenContext::subpatternOffset(subpattern)));

clearSubpatternStart(subpattern);

}

}

subpatternBaseFrameLocation += YarrStackSpaceForBackTrackInfoParentheses;

for (unsigned frameLocation = subpatternBaseFrameLocation; frameLocation < m_parenContextSizes.frameSlots(); frameLocation++) {

loadFromFrame(frameLocation, tempReg);

m_jit.storePtr(tempReg, MacroAssembler::Address(parenContextReg, ParenContext::savedFrameOffset(m_parenContextSizes) + frameLocation * sizeof(uintptr_t)));

}

}

void restoreParenContext(MacroAssembler::RegisterID parenContextReg, MacroAssembler::RegisterID tempReg, unsigned firstSubpattern, unsigned lastSubpattern, unsigned subpatternBaseFrameLocation)

{

loadBeginAndMatchAmountFromParenContext(parenContextReg, m_regs.index, tempReg);

storeToFrame(m_regs.index, subpatternBaseFrameLocation + BackTrackInfoParentheses::beginIndex());

storeToFrame(tempReg, subpatternBaseFrameLocation + BackTrackInfoParentheses::matchAmountIndex());

m_jit.loadPtr(MacroAssembler::Address(parenContextReg, ParenContext::returnAddressOffset()), tempReg);

storeToFrame(tempReg, subpatternBaseFrameLocation + BackTrackInfoParentheses::returnAddressIndex());

if (m_compileMode == JITCompileMode::IncludeSubpatterns) {

for (unsigned subpattern = firstSubpattern; subpattern <= lastSubpattern; subpattern++) {

static_assert(is64Bit());

m_jit.load64(MacroAssembler::Address(parenContextReg, ParenContext::subpatternOffset(subpattern)), tempReg);

m_jit.store64(tempReg, MacroAssembler::Address(m_regs.output, (subpattern << 1) * sizeof(unsigned)));

}

}

subpatternBaseFrameLocation += YarrStackSpaceForBackTrackInfoParentheses;

for (unsigned frameLocation = subpatternBaseFrameLocation; frameLocation < m_parenContextSizes.frameSlots(); frameLocation++) {

m_jit.loadPtr(MacroAssembler::Address(parenContextReg, ParenContext::savedFrameOffset(m_parenContextSizes) + frameLocation * sizeof(uintptr_t)), tempReg);

storeToFrame(tempReg, frameLocation);

}

}

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

// We can move BMP only character classes after fixed character terms.

if ((term.type == PatternTerm::Type::CharacterClass)

&& (term.quantityType == QuantifierType::FixedCount)

&& (!m_decodeSurrogatePairs || (term.characterClass->hasOneCharacterSize() && !term.m_invert))

&& (nextTerm.type == PatternTerm::Type::PatternCharacter)

&& (nextTerm.quantityType == QuantifierType::FixedCount)) {

PatternTerm termCopy = term;

alternative->m_terms[i] = nextTerm;

alternative->m_terms[i + 1] = termCopy;

}

}

}

void matchCharacterClassRange(MacroAssembler::RegisterID character, MacroAssembler::JumpList& failures, MacroAssembler::JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar32* 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)) {

MacroAssembler::Jump loOrAbove = m_jit.branch32(MacroAssembler::GreaterThanOrEqual, character, MacroAssembler::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(m_jit.branch32(MacroAssembler::Equal, character, MacroAssembler::Imm32((unsigned short)matches[*matchIndex])));

++*matchIndex;

}

failures.append(m_jit.jump());

loOrAbove.link(&m_jit);

} else if (which) {

MacroAssembler::Jump loOrAbove = m_jit.branch32(MacroAssembler::GreaterThanOrEqual, character, MacroAssembler::Imm32((unsigned short)lo));

matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);

failures.append(m_jit.jump());

loOrAbove.link(&m_jit);

} else

failures.append(m_jit.branch32(MacroAssembler::LessThan, character, MacroAssembler::Imm32((unsigned short)lo)));

while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))

++*matchIndex;

matchDest.append(m_jit.branch32(MacroAssembler::LessThanOrEqual, character, MacroAssembler::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(MacroAssembler::RegisterID character, MacroAssembler::JumpList& matchDest, const CharacterClass* charClass)

{

if (charClass->m_table && !m_decodeSurrogatePairs) {

MacroAssembler::ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table));

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

return;

}

MacroAssembler::JumpList unicodeFail;

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

MacroAssembler::JumpList isAscii;

if (charClass->m_matches.size() || charClass->m_ranges.size())

isAscii.append(m_jit.branch32(MacroAssembler::LessThanOrEqual, character, MacroAssembler::TrustedImm32(0x7f)));

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

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

UChar32 ch = charClass->m_matchesUnicode[i];

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

}

}

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

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

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

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

MacroAssembler::Jump below = m_jit.branch32(MacroAssembler::LessThan, character, MacroAssembler::Imm32(lo));

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

below.link(&m_jit);

}

}

if (charClass->m_matches.size() || charClass->m_ranges.size())

unicodeFail = m_jit.jump();

isAscii.link(&m_jit);

}

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

unsigned matchIndex = 0;

MacroAssembler::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(m_jit.branch32(MacroAssembler::Equal, character, MacroAssembler::Imm32((unsigned short)charClass->m_matches[matchIndex++])));

failures.link(&m_jit);

} 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.ignoreCase()) {

if (isASCIILower(ch)) {

matchesAZaz.append(ch);

continue;

}

if (isASCIIUpper(ch))

continue;

}

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

}

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

m_jit.or32(MacroAssembler::TrustedImm32(32), character);

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

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

}

}

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

unicodeFail.link(&m_jit);

}

#if ENABLE(YARR_JIT_UNICODE_EXPRESSIONS)

void advanceIndexAfterCharacterClassTermMatch(const PatternTerm* term, MacroAssembler::JumpList& failuresAfterIncrementingIndex, const MacroAssembler::RegisterID character)

{

ASSERT(term->type == PatternTerm::Type::CharacterClass);

if (term->isFixedWidthCharacterClass())

m_jit.add32(MacroAssembler::TrustedImm32(term->characterClass->hasNonBMPCharacters() ? 2 : 1), m_regs.index);

else {

m_jit.add32(MacroAssembler::TrustedImm32(1), m_regs.index);

MacroAssembler::Jump isBMPChar = m_jit.branch32(MacroAssembler::LessThan, character, m_regs.supplementaryPlanesBase);

failuresAfterIncrementingIndex.append(atEndOfInput());

m_jit.add32(MacroAssembler::TrustedImm32(1), m_regs.index);

isBMPChar.link(&m_jit);

}

}

#endif

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

MacroAssembler::Jump jumpIfNoAvailableInput(unsigned countToCheck = 0)

{

if (countToCheck)

m_jit.add32(MacroAssembler::Imm32(countToCheck), m_regs.index);

return m_jit.branch32(MacroAssembler::Above, m_regs.index, m_regs.length);

}

MacroAssembler::Jump jumpIfAvailableInput(unsigned countToCheck)

{

m_jit.add32(MacroAssembler::Imm32(countToCheck), m_regs.index);

return m_jit.branch32(MacroAssembler::BelowOrEqual, m_regs.index, m_regs.length);

}

MacroAssembler::Jump checkNotEnoughInput(MacroAssembler::RegisterID additionalAmount)

{

m_jit.add32(m_regs.index, additionalAmount);

return m_jit.branch32(MacroAssembler::Above, additionalAmount, m_regs.length);

}

MacroAssembler::Jump checkInput()

{

return m_jit.branch32(MacroAssembler::BelowOrEqual, m_regs.index, m_regs.length);

}

MacroAssembler::Jump atEndOfInput()

{

return m_jit.branch32(MacroAssembler::Equal, m_regs.index, m_regs.length);

}

MacroAssembler::Jump notAtEndOfInput()

{

return m_jit.branch32(MacroAssembler::NotEqual, m_regs.index, m_regs.length);

}

MacroAssembler::BaseIndex negativeOffsetIndexedAddress(Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID tempReg)

{

return negativeOffsetIndexedAddress(negativeCharacterOffset, tempReg, m_regs.index);

}

MacroAssembler::BaseIndex negativeOffsetIndexedAddress(Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID tempReg, MacroAssembler::RegisterID indexReg)

{

MacroAssembler::RegisterID base = m_regs.input;

// MacroAssembler::BaseIndex() addressing can take a int32_t offset. Given that we can have a regular

// expression that has unsigned character offsets, MacroAssembler::BaseIndex's signed offset is insufficient

// for addressing in extreme cases where we might underflow. Therefore we check to see if

// negativeCharacterOffset will underflow directly or after converting for 16 bit characters.

// If so, we do our own address calculating by adjusting the base, using the result register

// as a temp address register.

unsigned maximumNegativeOffsetForCharacterSize = m_charSize == CharSize::Char8 ? 0x7fffffff : 0x3fffffff;

unsigned offsetAdjustAmount = 0x40000000;

if (negativeCharacterOffset > maximumNegativeOffsetForCharacterSize) {

base = tempReg;

m_jit.move(m_regs.input, base);

while (negativeCharacterOffset > maximumNegativeOffsetForCharacterSize) {

m_jit.subPtr(MacroAssembler::TrustedImm32(offsetAdjustAmount), base);

if (m_charSize != CharSize::Char8)

m_jit.subPtr(MacroAssembler::TrustedImm32(offsetAdjustAmount), base);

negativeCharacterOffset -= offsetAdjustAmount;

}

}

Checked<int32_t> characterOffset(-static_cast<int32_t>(negativeCharacterOffset));

if (m_charSize == CharSize::Char8)

return MacroAssembler::BaseIndex(m_regs.input, indexReg, MacroAssembler::TimesOne, characterOffset * static_cast<int32_t>(sizeof(char)));

return MacroAssembler::BaseIndex(m_regs.input, indexReg, MacroAssembler::TimesTwo, characterOffset * static_cast<int32_t>(sizeof(UChar)));

}

#if ENABLE(YARR_JIT_UNICODE_EXPRESSIONS)

void tryReadUnicodeCharImpl(MacroAssembler::RegisterID resultReg)

{

ASSERT(m_charSize == CharSize::Char16);

MacroAssembler::JumpList notUnicode;

m_jit.load16Unaligned(MacroAssembler::Address(m_regs.regUnicodeInputAndTrail), resultReg);

// Is the character a leading surrogate?

m_jit.and32(m_regs.surrogateTagMask, resultReg, m_regs.unicodeTemp);

notUnicode.append(m_jit.branch32(MacroAssembler::NotEqual, m_regs.unicodeTemp, m_regs.leadingSurrogateTag));

// Is the input long enough to read a trailing surrogate?

m_jit.addPtr(MacroAssembler::TrustedImm32(2), m_regs.regUnicodeInputAndTrail);

notUnicode.append(m_jit.branchPtr(MacroAssembler::AboveOrEqual, m_regs.regUnicodeInputAndTrail, m_regs.endOfStringAddress));

// Is the character a trailing surrogate?

m_jit.load16Unaligned(MacroAssembler::Address(m_regs.regUnicodeInputAndTrail), m_regs.regUnicodeInputAndTrail);

m_jit.and32(m_regs.surrogateTagMask, m_regs.regUnicodeInputAndTrail, m_regs.unicodeTemp);

notUnicode.append(m_jit.branch32(MacroAssembler::NotEqual, m_regs.unicodeTemp, m_regs.trailingSurrogateTag));

// Combine leading and trailing surrogates to produce a code point.

m_jit.lshift32(MacroAssembler::TrustedImm32(10), resultReg);

m_jit.getEffectiveAddress(MacroAssembler::BaseIndex(resultReg, m_regs.regUnicodeInputAndTrail, MacroAssembler::TimesOne, -U16_SURROGATE_OFFSET), resultReg);

notUnicode.link(&m_jit);

}

void tryReadUnicodeChar(MacroAssembler::BaseIndex address, MacroAssembler::RegisterID resultReg)

{

ASSERT(m_charSize == CharSize::Char16);

m_jit.getEffectiveAddress(address, m_regs.regUnicodeInputAndTrail);

if (resultReg == m_regs.regT0)

m_tryReadUnicodeCharacterCalls.append(m_jit.nearCall());

else

tryReadUnicodeCharImpl(resultReg);

}

#endif

void readCharacter(Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID resultReg)

{

readCharacter(negativeCharacterOffset, resultReg, m_regs.index);

}

void readCharacter(Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID resultReg, MacroAssembler::RegisterID indexReg)

{

MacroAssembler::BaseIndex address = negativeOffsetIndexedAddress(negativeCharacterOffset, resultReg, indexReg);

if (m_charSize == CharSize::Char8)

m_jit.load8(address, resultReg);

#if ENABLE(YARR_JIT_UNICODE_EXPRESSIONS)

else if (m_decodeSurrogatePairs)

tryReadUnicodeChar(address, resultReg);

#endif

else

m_jit.load16Unaligned(address, resultReg);

}

MacroAssembler::Jump jumpIfCharNotEquals(UChar32 ch, Checked<unsigned> negativeCharacterOffset, MacroAssembler::RegisterID character)

{

readCharacter(negativeCharacterOffset, character);

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

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

ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode));

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

m_jit.or32(MacroAssembler::TrustedImm32(0x20), character);

ch |= 0x20;

}

return m_jit.branch32(MacroAssembler::NotEqual, character, MacroAssembler::Imm32(ch));

}

void storeToFrame(MacroAssembler::RegisterID reg, unsigned frameLocation)

{

m_jit.poke(reg, frameLocation);

}

void storeToFrame(MacroAssembler::TrustedImm32 imm, unsigned frameLocation)

{

m_jit.poke(imm, frameLocation);

}

#if CPU(ARM64) || CPU(X86_64) || CPU(RISCV64)

void storeToFrame(MacroAssembler::TrustedImmPtr imm, unsigned frameLocation)

{

m_jit.poke(imm, frameLocation);

}

#endif

MacroAssembler::DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)

{

return m_jit.storePtrWithPatch(MacroAssembler::TrustedImmPtr(nullptr), MacroAssembler::Address(MacroAssembler::stackPointerRegister, frameLocation * sizeof(void*)));

}

void loadFromFrame(unsigned frameLocation, MacroAssembler::RegisterID reg)

{

m_jit.peek(reg, frameLocation);

}

void loadFromFrameAndJump(unsigned frameLocation)

{

m_jit.farJump(MacroAssembler::Address(MacroAssembler::stackPointerRegister, frameLocation * sizeof(void*)), YarrBacktrackPtrTag);

}

unsigned alignCallFrameSizeInBytes(unsigned callFrameSize)

{

if (!callFrameSize)

return 0;

callFrameSize *= sizeof(void*);

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

CRASH();

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

return callFrameSize;

}

void removeCallFrame()

{

unsigned callFrameSizeInBytes = alignCallFrameSizeInBytes(m_pattern.m_body->m_callFrameSize);

if (callFrameSizeInBytes)

m_jit.addPtr(MacroAssembler::Imm32(callFrameSizeInBytes), MacroAssembler::stackPointerRegister);

}

void generateFailReturn()

{

m_jit.move(MacroAssembler::TrustedImmPtr((void*)WTF::notFound), m_regs.returnRegister);

m_jit.move(MacroAssembler::TrustedImm32(0), m_regs.returnRegister2);

#if ENABLE(YARR_JIT_REGEXP_TEST_INLINE)

if (m_compileMode == JITCompileMode::InlineTest) {

m_inlinedFailedMatch.append(m_jit.jump());

return;

}

#endif

generateReturn();

}

void generateJITFailReturn()

{

if (m_abortExecution.empty() && m_hitMatchLimit.empty())

return;

MacroAssembler::JumpList finishExiting;

if (!m_abortExecution.empty()) {

m_abortExecution.link(&m_jit);

m_jit.move(MacroAssembler::TrustedImmPtr((void*)static_cast<size_t>(-2)), m_regs.returnRegister);

finishExiting.append(m_jit.jump());

}

if (!m_hitMatchLimit.empty()) {

m_hitMatchLimit.link(&m_jit);

m_jit.move(MacroAssembler::TrustedImmPtr((void*)static_cast<size_t>(-1)), m_regs.returnRegister);

}

finishExiting.link(&m_jit);

removeCallFrame();

m_jit.move(MacroAssembler::TrustedImm32(0), m_regs.returnRegister2);

generateReturn();

}

// Used to record subpatterns, should only be called if m_compileMode is JITCompileMode::IncludeSubpatterns.

void setSubpatternStart(MacroAssembler::RegisterID reg, unsigned subpattern)

{

ASSERT(subpattern);

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

m_jit.store32(reg, MacroAssembler::Address(m_regs.output, (subpattern << 1) * sizeof(int)));

}

void setSubpatternEnd(MacroAssembler::RegisterID reg, unsigned subpattern)

{

ASSERT(subpattern);

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

m_jit.store32(reg, MacroAssembler::Address(m_regs.output, ((subpattern << 1) + 1) * sizeof(int)));

}

void clearSubpatternStart(unsigned subpattern)

{

ASSERT(subpattern);

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

m_jit.store32(MacroAssembler::TrustedImm32(-1), MacroAssembler::Address(m_regs.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 m_compileMode, and in this case

// these methods should never be called.

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

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

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

// in this register.

void setMatchStart(MacroAssembler::RegisterID reg)

{

ASSERT(!m_pattern.m_body->m_hasFixedSize);

if (m_compileMode == JITCompileMode::IncludeSubpatterns)

m_jit.store32(reg, MacroAssembler::Address(m_regs.output));

else

m_jit.move(reg, m_regs.output);

}

void getMatchStart(MacroAssembler::RegisterID reg)

{

ASSERT(!m_pattern.m_body->m_hasFixedSize);

if (m_compileMode == JITCompileMode::IncludeSubpatterns)

m_jit.load32(MacroAssembler::Address(m_regs.output), reg);

else

m_jit.move(m_regs.output, reg);

}

enum class YarrOpCode : uint8_t {

// 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'.

BodyAlternativeBegin,

BodyAlternativeNext,

BodyAlternativeEnd,

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

// or more alternatives.

NestedAlternativeBegin,

NestedAlternativeNext,

NestedAlternativeEnd,

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

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

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

// terminal subpatterns).

SimpleNestedAlternativeBegin,

SimpleNestedAlternativeNext,

SimpleNestedAlternativeEnd,

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

ParenthesesSubpatternOnceBegin,

ParenthesesSubpatternOnceEnd,

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

ParenthesesSubpatternTerminalBegin,

ParenthesesSubpatternTerminalEnd,

// Used to wrap generic captured matches

ParenthesesSubpatternBegin,

ParenthesesSubpatternEnd,

// Used to wrap parenthetical assertions.

ParentheticalAssertionBegin,

ParentheticalAssertionEnd,

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

Term,

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

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

MatchFailed

};

// 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_term(term)

, m_op(YarrOpCode::Term)

{

}

explicit YarrOp(YarrOpCode op)

: m_op(op)

{

}

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

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

// YarrOpCode::BodyAlternativeEnd node at the end of a section of repeating nodes,

// m_nextOp will reference the YarrOpCode::BodyAlternativeBegin node of the first

// repeating alternative.

PatternAlternative* m_alternative;

size_t m_previousOp;

size_t m_nextOp;

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

PatternTerm* m_term;

YarrOpCode m_op;

// 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).

MacroAssembler::Label m_reentry;

MacroAssembler::JumpList m_jumps;

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

// characters but matched.

MacroAssembler::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 { false };

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

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

// recalculating it.

Checked<unsigned> m_checkAdjust;

// Used by YarrOpCode::NestedAlternativeNext/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.

MacroAssembler::DataLabelPtr m_returnAddress;

BoyerMooreInfo* m_bmInfo { nullptr };

};

// 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 {

private:

struct ReturnAddressRecord {

ReturnAddressRecord(MacroAssembler::DataLabelPtr dataLabel, MacroAssembler::Label backtrackLocation)

: m_dataLabel(dataLabel)

, m_backtrackLocation(backtrackLocation)

{

}

MacroAssembler::DataLabelPtr m_dataLabel;

MacroAssembler::Label m_backtrackLocation;

};

public:

typedef Vector<ReturnAddressRecord, 4> BacktrackRecords;

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 MacroAssembler::Jump& jump)

{

m_laterFailures.append(jump);

}

void append(MacroAssembler::JumpList& jumpList)

{

m_laterFailures.append(jumpList);

}

void append(const MacroAssembler::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()) {

MacroAssembler::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(MacroAssembler::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(MacroAssembler::JumpList& jumpList, MacroAssembler* assembler)

{

if (m_pendingReturns.size()) {

MacroAssembler::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;

}