//-------------------------------------------------------------------------------------------------------

// Copyright (C) Microsoft. All rights reserved.

// Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.

//-------------------------------------------------------------------------------------------------------

#include "ParserPch.h"

namespace UnifiedRegex

{

// ----------------------------------------------------------------------

// Compiler (inlines etc)

// ----------------------------------------------------------------------

uint8* Compiler::Emit(size_t size)

{

Assert(size <= UINT32_MAX);

if (instLen - instNext < size)

{

CharCount newLen = max(instLen, initInstBufSize);

CharCount instLenPlus = (CharCount)(instLen + size - 1);

// check for overflow

if (instLenPlus < instLen || instLenPlus * 2 < instLenPlus)

{

Js::Throw::OutOfMemory();

}

while (newLen <= instLenPlus)

{

newLen *= 2;

}

instBuf = (uint8*)ctAllocator->Realloc(instBuf, instLen, newLen);

instLen = newLen;

}

uint8* inst = instBuf + instNext;

instNext += (CharCount)size;

return inst;

}

template <typename T>

T* Compiler::Emit()

{

return new(Emit(sizeof(T))) T;

}

#define EMIT(compiler, T, ...) (new (compiler.Emit(sizeof(T))) T(__VA_ARGS__))

#define L2I(O, label) LabelToInstPointer<O##Inst>(Inst::O, label)

// Remember: The machine address of an instruction is no longer valid after a subsequent emit,

// so all label fixups must be done using Compiler::GetFixup / Compiler::DoFixup

// ----------------------------------------------------------------------

// Node

// ----------------------------------------------------------------------

void Node::AppendLiteral(CharCount& litbufNext, CharCount litbufLen, __inout_ecount(litbufLen) Char* litbuf) const

{

Assert(false);

}

CharCount Node::EmitScanFirstSet(Compiler& compiler)

{

Assert(prevConsumes.IsExact(0));

if (thisConsumes.CouldMatchEmpty())

// Can't be sure of consuming something in FIRST

return 0;

if (firstSet->Count() > maxSyncToSetSize)

// HEURISTIC: If FIRST is large we'll get too many false positives

return 0;

//

// Compilation scheme:

//

// SyncTo(Char|Char2|Set)And(Consume|Continue)

//

Char entries[CharSet<Char>::MaxCompact];

int count = firstSet->GetCompactEntries(2, entries);

if (SupportsPrefixSkipping(compiler))

{

if (count == 1)

EMIT(compiler, SyncToCharAndConsumeInst, entries[0]);

else if (count == 2)

EMIT(compiler, SyncToChar2SetAndConsumeInst, entries[0], entries[1]);

else

EMIT(compiler, SyncToSetAndConsumeInst<false>)->set.CloneFrom(compiler.rtAllocator, *firstSet);

return 1;

}

else

{

if (count == 1)

EMIT(compiler, SyncToCharAndContinueInst, entries[0]);

else if (count == 2)

EMIT(compiler, SyncToChar2SetAndContinueInst, entries[0], entries[1]);

else

EMIT(compiler, SyncToSetAndContinueInst<false>)->set.CloneFrom(compiler.rtAllocator, *firstSet);

return 0;

}

}

bool Node::IsBetterSyncronizingNode(Compiler& compiler, Node* curr, Node* proposed)

{

int proposedNumLiterals = 0;

CharCount proposedLength = proposed->MinSyncronizingLiteralLength(compiler, proposedNumLiterals);

if (proposedLength == 0 || proposedNumLiterals > maxNumSyncLiterals)

// Not a synchronizable node or too many literals.

return false;

if (curr == nullptr)

// We'll take whatever we can get

return true;

int currNumLiterals = 0;

CharCount currLength = curr->MinSyncronizingLiteralLength(compiler, currNumLiterals);

// Lexicographic ordering based on

// - whether literal length is above a threshold (above is better)

// - number of literals (smaller is better)

// - upper bound on backup (finite is better)

// - minimum literal length (longer is better)

// - actual backup upper bound (shorter is better)

if (proposedLength >= preferredMinSyncToLiteralLength

&& currLength < preferredMinSyncToLiteralLength)

{

return true;

}

if (proposedLength < preferredMinSyncToLiteralLength

&& currLength >= preferredMinSyncToLiteralLength)

{

return false;

}

if (proposedNumLiterals < currNumLiterals)

return true;

if (proposedNumLiterals > currNumLiterals)

return false;

if (!proposed->prevConsumes.IsUnbounded() && curr->prevConsumes.IsUnbounded())

return true;

if (proposed->prevConsumes.IsUnbounded() && !curr->prevConsumes.IsUnbounded())

return false;

if (proposedLength > currLength)

return true;

if (proposedLength < currLength)

return false;

return proposed->prevConsumes.upper < curr->prevConsumes.upper;

}

bool Node::IsSingleChar(Compiler& compiler, Char& outChar) const

{

if (tag != Node::MatchChar)

return false;

const MatchCharNode* node = (const MatchCharNode*)this;

if (node->isEquivClass)

return false;

outChar = node->cs[0];

return true;

}

bool Node::IsBoundedWord(Compiler& compiler) const

{

if (tag != Node::Concat)

return false;

const ConcatNode* concatNode = (const ConcatNode *)this;

if (concatNode->head->tag != Node::WordBoundary ||

concatNode->tail == 0 ||

concatNode->tail->head->tag != Node::Loop ||

concatNode->tail->tail == 0 ||

concatNode->tail->tail->head->tag != Node::WordBoundary ||

concatNode->tail->tail->tail != 0)

return false;

const WordBoundaryNode* enter = (const WordBoundaryNode*)concatNode->head;

const LoopNode* loop = (const LoopNode*)concatNode->tail->head;

const WordBoundaryNode* leave = (const WordBoundaryNode*)concatNode->tail->tail->head;

if (enter->isNegation ||

!loop->isGreedy ||

loop->repeats.lower != 1 ||

loop->repeats.upper != CharCountFlag ||

loop->body->tag != Node::MatchSet ||

leave->isNegation)

return false;

const MatchSetNode* wordSet = (const MatchSetNode*)loop->body;

if (wordSet->isNegation)

return false;

return wordSet->set.IsEqualTo(*compiler.standardChars->GetWordSet());

}

bool Node::IsBOILiteral2(Compiler& compiler) const

{

if (tag != Node::Concat)

return false;

const ConcatNode* concatNode = (const ConcatNode *)this;

if ((compiler.program->flags & (IgnoreCaseRegexFlag | MultilineRegexFlag)) != 0 ||

concatNode->head->tag != Node::BOL ||

concatNode->tail == nullptr ||

concatNode->tail->head->tag != Node::MatchLiteral ||

concatNode->tail->tail != nullptr ||

((MatchLiteralNode *)concatNode->tail->head)->isEquivClass ||

((MatchLiteralNode *)concatNode->tail->head)->length != 2)

{

return false;

}

return true;

}

bool Node::IsLeadingTrailingSpaces(Compiler& compiler, CharCount& leftMinMatch, CharCount& rightMinMatch) const

{

if (tag != Node::Alt)

return false;

if (compiler.program->flags & MultilineRegexFlag)

return false;

const AltNode* altNode = (const AltNode*)this;

if (altNode->head->tag != Node::Concat ||

altNode->tail == 0 ||

altNode->tail->head->tag != Node::Concat ||

altNode->tail->tail != 0)

return false;

const ConcatNode* left = (const ConcatNode*)altNode->head;

const ConcatNode* right = (const ConcatNode*)altNode->tail->head;

if (left->head->tag != Node::BOL ||

left->tail == 0 ||

left->tail->head->tag != Node::Loop ||

left->tail->tail != 0)

return false;

if (right->head->tag != Node::Loop ||

right->tail == 0 ||

right->tail->head->tag != Node::EOL ||

right->tail->tail != 0)

return false;

const LoopNode* leftLoop = (const LoopNode*)left->tail->head;

const LoopNode* rightLoop = (const LoopNode*)right->head;

if (!leftLoop->isGreedy ||

leftLoop->repeats.upper != CharCountFlag ||

leftLoop->body->tag != Node::MatchSet ||

!rightLoop->isGreedy ||

rightLoop->repeats.upper != CharCountFlag ||

rightLoop->body->tag != Node::MatchSet)

return false;

const MatchSetNode* leftSet = (const MatchSetNode*)leftLoop->body;

const MatchSetNode* rightSet = (const MatchSetNode*)rightLoop->body;

if (leftSet->isNegation ||

rightSet->isNegation)

return false;

leftMinMatch = leftLoop->repeats.lower;

rightMinMatch = rightLoop->repeats.lower;

return

leftSet->set.IsEqualTo(*compiler.standardChars->GetWhitespaceSet()) &&

rightSet->set.IsEqualTo(*compiler.standardChars->GetWhitespaceSet());

}

#if ENABLE_REGEX_CONFIG_OPTIONS

void Node::PrintAnnotations(DebugWriter* w) const

{

if (firstSet != 0)

{

w->PrintEOL(L"<");

w->Indent();

w->Print(L"features: {");

bool first = true;

for (uint i = Empty; i <= Assertion; i++)

{

if ((features & (1 << i)) != 0)

{

if (first)

first = false;

else

w->Print(L",");

switch (i)

{

case Empty: w->Print(L"Empty"); break;

case BOL: w->Print(L"BOL"); break;

case EOL: w->Print(L"EOL"); break;

case WordBoundary: w->Print(L"WordBoundary"); break;

case MatchLiteral: w->Print(L"MatchLiteral"); break;

case MatchChar: w->Print(L"MatchChar"); break;

case Concat: w->Print(L"Concat"); break;

case Alt: w->Print(L"Alt"); break;

case DefineGroup: w->Print(L"DefineGroup"); break;

case MatchGroup: w->Print(L"MatchGroup"); break;

case Loop: w->Print(L"Loop"); break;

case MatchSet: w->Print(L"MatchSet"); break;

case Assertion: w->Print(L"Assertion"); break;

}

}

}

w->PrintEOL(L"}");

w->Print(L"firstSet: ");

firstSet->Print(w);

if (isFirstExact)

w->Print(L" (exact)");

w->EOL();

w->Print(L"followSet: ");

followSet->Print(w);

w->EOL();

w->Print(L"prevConsumes: ");

prevConsumes.Print(w);

w->EOL();

w->Print(L"thisConsumes: ");

thisConsumes.Print(w);

w->EOL();

w->Print(L"followConsumes: ");

followConsumes.Print(w);

w->EOL();

w->PrintEOL(L"isThisIrrefutable: %s", isThisIrrefutable ? L"true" : L"false");

w->PrintEOL(L"isFollowIrrefutable: %s", isFollowIrrefutable ? L"true" : L"false");

w->PrintEOL(L"isWord: %s", isWord ? L"true" : L"false");

w->PrintEOL(L"isThisWillNotProgress: %s", isThisWillNotProgress ? L"true" : L"false");

w->PrintEOL(L"isThisWillNotRegress: %s", isThisWillNotRegress ? L"true" : L"false");

w->PrintEOL(L"isPrevWillNotProgress: %s", isPrevWillNotProgress ? L"true" : L"false");

w->PrintEOL(L"isPrevWillNotRegress: %s", isPrevWillNotRegress ? L"true" : L"false");

w->PrintEOL(L"isDeterministic: %s", isDeterministic ? L"true" : L"false");

w->PrintEOL(L"isNotInLoop: %s", isNotInLoop ? L"true" : L"false");

w->PrintEOL(L"isNotNegated: %s", isNotNegated ? L"true" : L"false");

w->PrintEOL(L"isAtLeastOnce: %s", isAtLeastOnce ? L"true" : L"false");

w->PrintEOL(L"hasInitialHardFailBOI: %s", hasInitialHardFailBOI ? L"true" : L"false");

w->Unindent();

w->PrintEOL(L">");

}

}

#endif

// ----------------------------------------------------------------------

// SimpleNode

// ----------------------------------------------------------------------

CharCount SimpleNode::LiteralLength() const

{

return 0;

}

bool SimpleNode::IsCharOrPositiveSet() const

{

return false;

}

CharCount SimpleNode::TransferPass0(Compiler& compiler, const Char* litbuf)

{

return 0;

}

void SimpleNode::TransferPass1(Compiler& compiler, const Char* litbuf)

{

}

bool SimpleNode::IsRefiningAssertion(Compiler& compiler)

{

return tag == EOL && (compiler.program->flags & MultilineRegexFlag) != 0;

}

void SimpleNode::AnnotatePass0(Compiler& compiler)

{

isWord = false;

}

void SimpleNode::AnnotatePass1(Compiler& compiler, bool parentNotInLoop, bool parentAtLeastOnce, bool parentNotSpeculative, bool parentNotNegated)

{

isFirstExact = false;

thisConsumes.Exact(0);

isThisWillNotProgress = true;

isThisWillNotRegress = true;

isNotInLoop = parentNotInLoop;

isAtLeastOnce = parentAtLeastOnce;

isNotSpeculative = parentNotSpeculative;

isNotNegated = parentNotNegated;

switch (tag)

{

case Empty:

features = HasEmpty;

firstSet = compiler.standardChars->GetEmptySet();

isThisIrrefutable = true;

break;

case BOL:

features = HasBOL;

firstSet = compiler.standardChars->GetFullSet();

isThisIrrefutable = false;

break;

case EOL:

features = HasEOL;

if ((compiler.program->flags & MultilineRegexFlag) != 0)

firstSet = compiler.standardChars->GetNewlineSet();

else

firstSet = compiler.standardChars->GetEmptySet();

isThisIrrefutable = false;

break;

default:

Assert(false);

}

}

void SimpleNode::AnnotatePass2(Compiler& compiler, CountDomain accumConsumes, bool accumPrevWillNotProgress, bool accumPrevWillNotRegress)

{

prevConsumes = accumConsumes;

isPrevWillNotProgress = accumPrevWillNotProgress;

isPrevWillNotRegress = accumPrevWillNotRegress;

}

void SimpleNode::AnnotatePass3(Compiler& compiler, CountDomain accumConsumes, CharSet<Char>* accumFollow, bool accumFollowIrrefutable, bool accumFollowEOL)

{

followConsumes = accumConsumes;

followSet = accumFollow;

isFollowIrrefutable = accumFollowIrrefutable;

isFollowEOL = accumFollowEOL;

hasInitialHardFailBOI = ((tag == BOL) &&

prevConsumes.IsExact(0) &&

(compiler.program->flags & MultilineRegexFlag) == 0 &&

isAtLeastOnce &&

isNotNegated &&

isPrevWillNotRegress);

}

void SimpleNode::AnnotatePass4(Compiler& compiler)

{

isDeterministic = true;

}

bool SimpleNode::SupportsPrefixSkipping(Compiler& compiler) const

{

return false;

}

Node* SimpleNode::HeadSyncronizingNode(Compiler& compiler)

{

return 0;

}

CharCount SimpleNode::MinSyncronizingLiteralLength(Compiler& compiler, int& numLiterals) const

{

return 0;

}

void SimpleNode::CollectSyncronizingLiterals(Compiler& compiler, ScannersMixin& scanners) const

{

Assert(false);

}

void SimpleNode::BestSyncronizingNode(Compiler& compiler, Node*& bestNode)

{

}

void SimpleNode::AccumDefineGroups(Js::ScriptContext* scriptContext, int& minGroup, int& maxGroup)

{

}

void SimpleNode::Emit(Compiler& compiler, CharCount& skipped)

{

Assert(skipped == 0);

switch (tag)

{

case Empty:

// Nothing

break;

case BOL:

{

if ((compiler.program->flags & MultilineRegexFlag) != 0)

{

//

// Compilation scheme:

//

// BOLTest

//

EMIT(compiler, BOLTestInst);

}

else

{

if (compiler.CurrentLabel() == 0)

{

// The first instruction is BOI, change the tag and only execute it once

// without looping every start position

compiler.SetBOIInstructionsProgramTag();

}

else

{

//

// Compilation scheme:

//

// BOITest

//

// Obviously starting later in the string won't help, so can hard fail if:

// - this pattern must always be matched

// - not in an negative assertion

// - backtracking could never rewind the input pointer

//

EMIT(compiler, BOITestInst, isAtLeastOnce && isNotNegated && isPrevWillNotRegress);

}

}

break;

}

case EOL:

{

if ((compiler.program->flags & MultilineRegexFlag) != 0)

//

// Compilation scheme:

//

// EOLTest

//

EMIT(compiler, EOLTestInst);

else

//

// Compilation scheme:

//

// EOITest

//

// Can hard fail if

// - this pattern must always be matched

// - not in an negative assertion

// - backtracking could never advance the input pointer

//

EMIT(compiler, EOITestInst, isAtLeastOnce && isNotNegated && isPrevWillNotProgress);

break;

}

default:

Assert(false);

}

}

CharCount SimpleNode::EmitScan(Compiler& compiler, bool isHeadSyncronizingNode)

{

Assert(false);

return 0;

}

bool SimpleNode::IsOctoquad(Compiler& compiler, OctoquadIdentifier* oi)

{

return false;

}

bool SimpleNode::IsCharTrieArm(Compiler& compiler, uint& accNumAlts) const

{

return tag == Empty;

}

bool SimpleNode::BuildCharTrie(Compiler& compiler, CharTrie* trie, Node* cont, bool isAcceptFirst) const

{

PROBE_STACK(compiler.scriptContext, Js::Constants::MinStackRegex);

Assert(tag == Empty);

if (cont == 0)

{

if (trie->Count() > 0)

// This literal is a proper prefix of an earlier literal

return false;

trie->SetAccepting();

return true;

}

return cont->BuildCharTrie(compiler, trie, 0, isAcceptFirst);

}

#if ENABLE_REGEX_CONFIG_OPTIONS

void SimpleNode::Print(DebugWriter* w, const Char* litbuf) const

{

switch (tag)

{

case Empty:

w->Print(L"Empty"); break;

case BOL:

w->Print(L"BOL"); break;

case EOL:

w->Print(L"EOL"); break;

default:

Assert(false);

}

w->PrintEOL(L"()");

PrintAnnotations(w);

}

#endif

// ----------------------------------------------------------------------

// WordBoundaryNode

// ----------------------------------------------------------------------

CharCount WordBoundaryNode::LiteralLength() const

{

return 0;

}

bool WordBoundaryNode::IsCharOrPositiveSet() const

{

return false;

}

CharCount WordBoundaryNode::TransferPass0(Compiler& compiler, const Char* litbuf)

{

return 0;

}

void WordBoundaryNode::TransferPass1(Compiler& compiler, const Char* litbuf)

{

// WordChars and NonWordChars sets are already case invariant

}

bool WordBoundaryNode::IsRefiningAssertion(Compiler& compiler)

{

return mustIncludeEntering != mustIncludeLeaving;

}

void WordBoundaryNode::AnnotatePass0(Compiler& compiler)

{

isWord = false;

}

void WordBoundaryNode::AnnotatePass1(Compiler& compiler, bool parentNotInLoop, bool parentAtLeastOnce, bool parentNotSpeculative, bool parentNotNegated)

{

features = HasWordBoundary;

thisConsumes.Exact(0);

isFirstExact = false;

isThisIrrefutable = false;

isThisWillNotProgress = true;

isThisWillNotRegress = true;

isNotInLoop = parentNotInLoop;

isAtLeastOnce = parentAtLeastOnce;

isNotSpeculative = parentNotSpeculative;

isNotNegated = parentNotNegated;

if (isNegation)

firstSet = compiler.standardChars->GetFullSet();

else

{

if (mustIncludeEntering && !mustIncludeLeaving)

firstSet = compiler.standardChars->GetWordSet();

else if (mustIncludeLeaving && !mustIncludeEntering)

firstSet = compiler.standardChars->GetNonWordSet();

else

firstSet = compiler.standardChars->GetFullSet();

}

}

void WordBoundaryNode::AnnotatePass2(Compiler& compiler, CountDomain accumConsumes, bool accumPrevWillNotProgress, bool accumPrevWillNotRegress)

{

prevConsumes = accumConsumes;

isPrevWillNotProgress = accumPrevWillNotProgress;

isPrevWillNotRegress = accumPrevWillNotRegress;

}

void WordBoundaryNode::AnnotatePass3(Compiler& compiler, CountDomain accumConsumes, CharSet<Char>* accumFollow, bool accumFollowIrrefutable, bool accumFollowEOL)

{

followConsumes = accumConsumes;

followSet = accumFollow;

isFollowIrrefutable = accumFollowIrrefutable;

isFollowEOL = accumFollowEOL;

}

void WordBoundaryNode::AnnotatePass4(Compiler& compiler)

{

isDeterministic = true;

}

bool WordBoundaryNode::SupportsPrefixSkipping(Compiler& compiler) const

{

return false;

}

Node* WordBoundaryNode::HeadSyncronizingNode(Compiler& compiler)

{

return 0;

}

CharCount WordBoundaryNode::MinSyncronizingLiteralLength(Compiler& compiler, int& numLiterals) const

{

return 0;

}

void WordBoundaryNode::CollectSyncronizingLiterals(Compiler& compiler, ScannersMixin& scanners) const

{

Assert(false);

}

void WordBoundaryNode::BestSyncronizingNode(Compiler& compiler, Node*& bestNode)

{

}

void WordBoundaryNode::AccumDefineGroups(Js::ScriptContext* scriptContext, int& minGroup, int& maxGroup)

{

}

void WordBoundaryNode::Emit(Compiler& compiler, CharCount& skipped)

{

Assert(skipped == 0);

//

// Compilation scheme:

//

// WordBoundaryTest

//

EMIT(compiler, WordBoundaryTestInst, isNegation);

}

CharCount WordBoundaryNode::EmitScan(Compiler& compiler, bool isHeadSyncronizingNode)

{

Assert(false);

return 0;

}

bool WordBoundaryNode::IsOctoquad(Compiler& compiler, OctoquadIdentifier* oi)

{

return false;

}

bool WordBoundaryNode::IsCharTrieArm(Compiler& compiler, uint& accNumAlts) const

{

return false;

}

bool WordBoundaryNode::BuildCharTrie(Compiler& compiler, CharTrie* trie, Node* cont, bool isAcceptFirst) const

{

Assert(false);

return false;

}

#if ENABLE_REGEX_CONFIG_OPTIONS

void WordBoundaryNode::Print(DebugWriter* w, const Char* litbuf) const

{

w->PrintEOL(L"WordBoundary(%s, %s, %s)", isNegation ? L"negative" : L"positive", mustIncludeEntering ? L"entering" : L"-", mustIncludeLeaving ? L"leaving" : L"-");

PrintAnnotations(w);

}

#endif

// ----------------------------------------------------------------------

// MatchLiteralNode

// ----------------------------------------------------------------------

CharCount MatchLiteralNode::LiteralLength() const

{

return length;

}

void MatchLiteralNode::AppendLiteral(CharCount& litbufNext, CharCount litbufLen, __inout_ecount(litbufLen) Char* litbuf) const

{

// Called during parsing only, so literal always in original form

Assert(!isEquivClass);

Assert(litbufNext + length <= litbufLen && offset + length <= litbufLen);

#pragma prefast(suppress:26000, "The error said that offset + length >= litbufLen + 1, which is incorrect due to if statement below.")

if (litbufNext + length <= litbufLen && offset + length <= litbufLen) // for prefast

{

js_wmemcpy_s(litbuf + litbufNext, litbufLen - litbufNext, litbuf + offset, length);

}

litbufNext += length;

}

bool MatchLiteralNode::IsCharOrPositiveSet() const

{

return false;

}

CharCount MatchLiteralNode::TransferPass0(Compiler& compiler, const Char* litbuf)

{

Assert(length > 1);

if ((compiler.program->flags & IgnoreCaseRegexFlag) != 0

&& !compiler.standardChars->IsTrivialString(compiler.program->GetCaseMappingSource(), litbuf + offset, length))

{

// We'll need to expand each character of literal into its equivalence class

isEquivClass = true;

return length * CaseInsensitive::EquivClassSize;

}

else

return length;

}

void MatchLiteralNode::TransferPass1(Compiler& compiler, const Char* litbuf)

{

CharCount nextLit = compiler.program->rep.insts.litbufLen;

if (isEquivClass)

{

Assert((compiler.program->flags & IgnoreCaseRegexFlag) != 0);

// Expand literal according to character equivalence classes

for (CharCount i = 0; i < length; i++)

{

compiler.standardChars->ToEquivs(

compiler.program->GetCaseMappingSource(),

litbuf[offset + i],

compiler.program->rep.insts.litbuf + nextLit + i * CaseInsensitive::EquivClassSize);

}

compiler.program->rep.insts.litbufLen += length * CaseInsensitive::EquivClassSize;

}

else

{

for (CharCount i = 0; i < length; i++)

compiler.program->rep.insts.litbuf[nextLit + i] = litbuf[offset + i];

compiler.program->rep.insts.litbufLen += length;

}

offset = nextLit;

}

void MatchLiteralNode::AnnotatePass0(Compiler& compiler)

{

const Char* litbuf = compiler.program->rep.insts.litbuf;

for (CharCount i = offset; i < offset + length; i++)

{

if (!compiler.standardChars->IsWord(litbuf[i]))

{

isWord = false;

return;

}

}

isWord = true;

}

bool MatchLiteralNode::IsRefiningAssertion(Compiler& compiler)

{

return false;

}

void MatchLiteralNode::AnnotatePass1(Compiler& compiler, bool parentNotInLoop, bool parentAtLeastOnce, bool parentNotSpeculative, bool parentNotNegated)

{

features = HasMatchLiteral;

thisConsumes.Exact(length);

firstSet = Anew(compiler.ctAllocator, UnicodeCharSet);

for (int i = 0; i < (isEquivClass ? CaseInsensitive::EquivClassSize : 1); i++)

firstSet->Set(compiler.ctAllocator, compiler.program->rep.insts.litbuf[offset + i]);

isFirstExact = true;

isThisIrrefutable = false;

isThisWillNotProgress = true;

isThisWillNotRegress = true;

isNotInLoop = parentNotInLoop;

isAtLeastOnce = parentAtLeastOnce;

isNotSpeculative = parentNotSpeculative;

isNotNegated = parentNotNegated;

}

void MatchLiteralNode::AnnotatePass2(Compiler& compiler, CountDomain accumConsumes, bool accumPrevWillNotProgress, bool accumPrevWillNotRegress)

{

prevConsumes = accumConsumes;

isPrevWillNotProgress = accumPrevWillNotProgress;

isPrevWillNotRegress = accumPrevWillNotRegress;

}

void MatchLiteralNode::AnnotatePass3(Compiler& compiler, CountDomain accumConsumes, CharSet<Char>* accumFollow, bool accumFollowIrrefutable, bool accumFollowEOL)

{

followConsumes = accumConsumes;

followSet = accumFollow;

isFollowIrrefutable = accumFollowIrrefutable;

isFollowEOL = accumFollowEOL;

}

void MatchLiteralNode::AnnotatePass4(Compiler& compiler)

{

isDeterministic = true;

}

bool MatchLiteralNode::SupportsPrefixSkipping(Compiler& compiler) const

{

return true;

}

Node* MatchLiteralNode::HeadSyncronizingNode(Compiler& compiler)

{

return this;

}

CharCount MatchLiteralNode::MinSyncronizingLiteralLength(Compiler& compiler, int& numLiterals) const

{

numLiterals++;

return length;

}

void MatchLiteralNode::CollectSyncronizingLiterals(Compiler& compiler, ScannersMixin& scanners) const

{

ScannerMixin* scanner =

scanners.Add(compiler.GetScriptContext()->GetRecycler(), compiler.GetProgram(), offset, length, isEquivClass);

scanner->scanner.Setup(compiler.rtAllocator, compiler.program->rep.insts.litbuf + offset, length, isEquivClass ? CaseInsensitive::EquivClassSize : 1);

}

void MatchLiteralNode::BestSyncronizingNode(Compiler& compiler, Node*& bestNode)

{

if (IsBetterSyncronizingNode(compiler, bestNode, this))

bestNode = this;

}

void MatchLiteralNode::AccumDefineGroups(Js::ScriptContext* scriptContext, int& minGroup, int& maxGroup)

{

}

void MatchLiteralNode::Emit(Compiler& compiler, CharCount& skipped)

{

if (skipped >= length)

{

// Asking to skip entire literal

skipped -= length;

return;

}

//

// Compilation scheme:

//

// Match(Char|Char4|Literal|LiteralEquiv)Inst

//

CharCount effectiveOffset = offset + skipped * (isEquivClass ? CaseInsensitive::EquivClassSize : 1);

CharCount effectiveLength = length - skipped;

skipped -= min(skipped, length);

if (effectiveLength == 1)

{

Char* cs = compiler.program->rep.insts.litbuf + effectiveOffset;

MatchCharNode::Emit(compiler, cs, isEquivClass);

}

else

{

if (isEquivClass)

EMIT(compiler, MatchLiteralEquivInst, effectiveOffset, effectiveLength);

else

EMIT(compiler, MatchLiteralInst, effectiveOffset, effectiveLength);

}

}

CompileAssert(CaseInsensitive::EquivClassSize == 4);

CharCount MatchLiteralNode::EmitScan(Compiler& compiler, bool isHeadSyncronizingNode)

{

//

// Compilation scheme:

//

// SyncTo(Literal|LiteralEquiv|LinearLiteral)And(Continue|Consume|Backup)

//

Char * litptr = compiler.program->rep.insts.litbuf + offset;

if (isHeadSyncronizingNode)

{

// For a head literal there's no need to back up after finding the literal, so use a faster instruction

Assert(prevConsumes.IsExact(0)); // there should not be any consumes before this node

if (isEquivClass)

{

const uint lastPatCharIndex = length - 1;

if (litptr[lastPatCharIndex * CaseInsensitive::EquivClassSize] == litptr[lastPatCharIndex * CaseInsensitive::EquivClassSize + 1]

&& litptr[lastPatCharIndex * CaseInsensitive::EquivClassSize] == litptr[lastPatCharIndex * CaseInsensitive::EquivClassSize + 2]

&& litptr[lastPatCharIndex * CaseInsensitive::EquivClassSize] == litptr[lastPatCharIndex * CaseInsensitive::EquivClassSize + 3])

{

EMIT(compiler, SyncToLiteralEquivTrivialLastPatCharAndConsumeInst, offset, length)->scanner.Setup(compiler.rtAllocator, litptr, length, CaseInsensitive::EquivClassSize);

}

else

{

EMIT(compiler, SyncToLiteralEquivAndConsumeInst, offset, length)->scanner.Setup(compiler.rtAllocator, litptr, length, CaseInsensitive::EquivClassSize);

}

}

else if (length == 1)

EMIT(compiler, SyncToCharAndConsumeInst, litptr[0]);

else if (length == 2)

EMIT(compiler, SyncToChar2LiteralAndConsumeInst, litptr[0], litptr[1]);

else

{

TextbookBoyerMooreSetup<wchar_t> setup(litptr, length);

switch (setup.GetScheme())

{

case TextbookBoyerMooreSetup<wchar_t>::LinearScheme:

EMIT(compiler, SyncToLinearLiteralAndConsumeInst, offset, length)->scanner.Setup(compiler.rtAllocator, setup);

break;

case TextbookBoyerMooreSetup<wchar_t>::DefaultScheme:

EMIT(compiler, SyncToLiteralAndConsumeInst, offset, length)->scanner.Setup(compiler.rtAllocator, setup);

break;

};

}

return length;

}

else

{

// We're synchronizing on a non-head literal so we may need to back up. Or if we're syncing to the first literal

// inside a group for instance, then we won't need to back up but we cannot consume the literal.

if (prevConsumes.IsExact(0))

{

if (isEquivClass)

{

const uint lastPatCharIndex = length - 1;

if (litptr[lastPatCharIndex * CaseInsensitive::EquivClassSize] == litptr[lastPatCharIndex * CaseInsensitive::EquivClassSize + 1]