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

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

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

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

/*

--------------------------------------------------------------------------------------------------------------------------------

Original

--------------------------------------------------------------------------------------------------------------------------------

Pattern ::= Disjunction

Disjunction ::= Alternative | Alternative '|' Disjunction

Alternative ::= [empty] | Alternative Term

Term ::= Assertion | Atom | Atom Quantifier

Assertion ::= '^' | '$' | '\' 'b' | '\' 'B' | '(' '?' '=' Disjunction ')' | '(' '?' '!' Disjunction ')'

Quantifier ::= QuantifierPrefix | QuantifierPrefix '?'

QuantifierPrefix ::= '*' | '+' | '?' | '{' DecimalDigits '}' | '{' DecimalDigits ',' '}' | '{' DecimalDigits ',' DecimalDigits '}'

Atom ::= PatternCharacter | '.' | '\' AtomEscape | CharacterClass | '(' Disjunction ')' | '(' '?' ':' Disjunction ')'

PatternCharacter ::= SourceCharacter but not any of { '^', '$', '\', '.', '*', '+', '?', '(', ')', '[', ']', '{', '}', '|' }

AtomEscape ::= DecimalEscape | CharacterEscape | CharacterClassEscape

CharacterEscape ::= ControlEscape | 'c' ControlLetter | HexEscapeSequence | UnicodeEscapeSequence | IdentityEscape

ControlEscape ::= one of { 'f', 'n', 'r', 't', 'v' }

ControlLetter ::= one of { 'a'..'z', 'A'..'Z' }

IdentityEscape ::= (SourceCharacter but not IdentifierPart) | <ZWJ> | <ZWNJ>

DecimalEscape ::= DecimalIntegerLiteral [lookahead not in DecimalDigit]

CharacterClassEscape :: one of { 'd', 'D', 's', 'S', 'w', 'W' }

CharacterClass ::= '[' [lookahead not in {'^'}] ClassRanges ']' | '[' '^' ClassRanges ']'

ClassRanges ::= [empty] | NonemptyClassRanges

NonemptyClassRanges ::= ClassAtom | ClassAtom NonemptyClassRangesNoDash | ClassAtom '-' ClassAtom ClassRanges

NonemptyClassRangesNoDash ::= ClassAtom | ClassAtomNoDash NonemptyClassRangesNoDash | ClassAtomNoDash '-' ClassAtom ClassRanges

ClassAtom ::= '-' | ClassAtomNoDash

ClassAtomNoDash ::= SourceCharacter but not one of { '\', ']', '-' } | '\' ClassEscape

ClassEscape ::= DecimalEscape | 'b' | CharacterEscape | CharacterClassEscape

SourceCharacter ::= <unicode character>

HexEscapeSequence ::= 'x' HexDigit HexDigit

UnicodeEscapeSequence ::= 'u' HexDigit HexDigit HexDigit HexDigit | 'u' '{' HexDigits '}'

HexDigit ::= one of { '0'..'9', 'a'..'f', 'A'..'F' }

IdentifierStart ::= UnicodeLetter | '$' | '_' | '\' UnicodeEscapeSequence

IdentifierPart ::= IdentifierStart | UnicodeCombiningMark | UnicodeDigit | UnicodeConnectorPunctuation | <ZWNJ> | <ZWJ>

UnicodeLetter ::= <unicode Uppercase letter> | <unicode Lowercase letter> | <unicode Titlecase letter> | <unicode Modifier letter> | <unicode Other letter> | <unicode Letter number>

UnicodeCombiningMark = <unicode Non-spacing mark> | <unicode combining spacing mark>

UnicodeDigit ::= <unicode Decimal number>

UnicodeConnectorPunctuation ::= <unicode Connector punctuation>

DecimalIntegerLiteral ::= '0' | NonZeroDigit DecimalDigits?

DecimalDigits ::= DecimalDigit | DecimalDigits DecimalDigit

DecimalDigit ::= one of { '0'..'9' }

NonZeroDigit ::= one of { '1'..'9' }

------------------

Annex B Deviations

------------------

1. The assertions (?= ) and (?! ) are treated as though they have a surrounding non-capture group, and hence can be quantified.

Other assertions are not quantifiable.

QuantifiableAssertion [added] ::= '(' '?' '=' Disjunction ')' | '(' '?' '!' Disjunction ')'

Assertion [replaced] ::= '^' | '$' | '\' 'b' | '\' 'B' | QuantifiableAssertion

Term ::= ... | QuantifiableAssertion Quantifier [added]

--------------------------------------------------------------------------------------------------------------------------------

Left factored

--------------------------------------------------------------------------------------------------------------------------------

Pattern ::= Disjunction

Disjunction ::= Alternative ('|' Alternative)*

FOLLOW(Disjunction) = { <eof>, ')' }

Alternative ::= Term*

FOLLOW(Alternative) = { <eof>, ')', '|' }

Term ::= ( '^' | '$' | '\' 'b' | '\' 'B' | '(' '?' '=' Disjunction ')' | '(' '?' '!' Disjunction ')' | Atom Quantifier? )

| ( PatternCharacter | '.' | '\' AtomEscape | CharacterClass | '(' Disjunction ')' | '(' '?' ':' Disjunction ')' )

( '*' | '+' | '?' | '{' DecimalDigits (',' DecimalDigits?)? '}' ) '?'?

PatternCharacter ::= <unicode character> but not any of { '^', '$', '\', '.', '*', '+', '?', '(', ')', '[', ']', '{', '}', '|' }

AtomEscape ::= DecimalEscape | CharacterEscape | CharacterClassEscape

CharacterEscape ::= ControlEscape | 'c' ControlLetter | HexEscapeSequence | UnicodeEscapeSequence | IdentityEscape

ControlEscape ::= one of { 'f', 'n', 'r', 't', 'v' }

ControlLetter ::= one of { 'a'..'z', 'A'..'Z' }

IdentityEscape ::= <unicode character> but not <unicode Uppercase letter>, <unicode Lowercase letter>, <unicode Titlecase letter>, <unicode Modifier letter>, <unicode Other letter>, <unicode Letter number>, '$', '_', <unicode Non-spacing mark>, <unicode combining spacing mark>, <unicode Decimal number>, <unicode Connector punctuation>

DecimalEscape ::= DecimalIntegerLiteral [lookahead not in DecimalDigit]

CharacterClassEscape :: one of { 'd', 'D', 's', 'S', 'w', 'W' }

CharacterClass ::= '[' [lookahead not in {'^'}] ClassRanges ']' | '[' '^' ClassRanges ']'

ClassRanges ::= [empty] | NonemptyClassRanges

NonemptyClassRanges ::= ClassAtom | ClassAtom NonemptyClassRangesNoDash | ClassAtom '-' ClassAtom ClassRanges

NonemptyClassRangesNoDash ::= ClassAtom | ClassAtomNoDash NonemptyClassRangesNoDash | ClassAtomNoDash '-' ClassAtom ClassRanges

ClassAtom ::= '-' | ClassAtomNoDash

ClassAtomNoDash ::= SourceCharacter but not one of { '\', ']', '-' } | '\' ClassEscape

ClassEscape ::= DecimalEscape | 'b' | CharacterEscape | CharacterClassEscape

HexEscapeSequence ::= 'x' HexDigit{2}

UnicodeEscapeSequence ::= 'u' HexDigit{4} | 'u' '{' HexDigits{4-6} '}'

HexDigit ::= one of { '0'..'9', 'a'..'f', 'A'..'F' }

DecimalIntegerLiteral ::= '0' | NonZeroDigit DecimalDigits?

DecimalDigits ::= DecimalDigit+

DecimalDigit ::= one of { '0'..'9' }

NonZeroDigit ::= one of { '1'..'9' }

------------------

Annex B Deviations

------------------

QuantifiableAssertion [added] ::= '(' '?' '=' Disjunction ')' | '(' '?' '!' Disjunction ')'

Term ::= ... | '(' '?' '=' Disjunction ')' [removed] | '(' '?' '!' Disjunction ')' [removed] | QuantifiableAssertion Quantifier? [added]

*/

#include "ParserPch.h"

namespace UnifiedRegex

{

template <typename P, const bool IsLiteral>

const CharCount Parser<P, IsLiteral>::initLitbufSize;

ParseError::ParseError(bool isBody, CharCount pos, CharCount encodedPos, HRESULT error)

: isBody(isBody), pos(pos), encodedPos(encodedPos), error(error)

{

}

template <typename P, const bool IsLiteral>

Parser<P, IsLiteral>::Parser

( Js::ScriptContext* scriptContext

, ArenaAllocator* ctAllocator

, StandardChars<EncodedChar>* standardEncodedChars

, StandardChars<Char>* standardChars

, bool isFromExternalSource

#if ENABLE_REGEX_CONFIG_OPTIONS

, DebugWriter* w

#endif

)

: scriptContext(scriptContext)

, ctAllocator(ctAllocator)

, standardEncodedChars(standardEncodedChars)

, standardChars(standardChars)

#if ENABLE_REGEX_CONFIG_OPTIONS

, w(w)

#endif

, input(0)

, inputLim(0)

, next(0)

, inBody(false)

, numGroups(1)

, nextGroupId(1) // implicit overall group always takes index 0

, litbuf(0)

, litbufLen(0)

, litbufNext(0)

, surrogatePairList(nullptr)

, currentSurrogatePairNode(nullptr)

, tempLocationOfSurrogatePair(nullptr)

, tempLocationOfRange(nullptr)

, codePointAtTempLocation(0)

, unicodeFlagPresent(false)

, caseInsensitiveFlagPresent(false)

, positionAfterLastSurrogate(nullptr)

, valueOfLastSurrogate(INVALID_CODEPOINT)

, deferredIfNotUnicodeError(nullptr)

, deferredIfUnicodeError(nullptr)

{

if (isFromExternalSource)

this->FromExternalSource();

}

//

// Input buffer management

//

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::SetPosition(const EncodedChar* input, const EncodedChar* inputLim, bool inBody)

{

this->input = input;

this->inputLim = inputLim;

next = input;

this->inBody = inBody;

this->RestoreMultiUnits(0);

}

template <typename P, const bool IsLiteral>

inline CharCount Parser<P, IsLiteral>::Pos()

{

CharCount nextOffset = Chars<EncodedChar>::OSB(next, input);

Assert(nextOffset >= this->m_cMultiUnits);

return nextOffset - (CharCount) this->m_cMultiUnits;

}

template <typename P, const bool IsLiteral>

inline bool Parser<P, IsLiteral>::IsEOF()

{

return next >= inputLim;

}

template <typename P, const bool IsLiteral>

inline bool Parser<P, IsLiteral>::ECCanConsume(CharCount n /*= 1*/)

{

return next + n <= inputLim;

}

template <typename P, const bool IsLiteral>

inline typename P::EncodedChar Parser<P, IsLiteral>::ECLookahead(CharCount n /*= 0*/)

{

// Ok to look ahead to terminating 0

Assert(next + n <= inputLim);

return next[n];

}

template <typename P, const bool IsLiteral>

inline typename P::EncodedChar Parser<P, IsLiteral>::ECLookback(CharCount n /*= 0*/)

{

// Ok to look ahead to terminating 0

Assert(n + input <= next);

return *(next - n);

}

template <typename P, const bool IsLiteral>

inline void Parser<P, IsLiteral>::ECConsume(CharCount n /*= 1*/)

{

Assert(next + n <= inputLim);

#if DBG

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

Assert(!this->IsMultiUnitChar(next[i]));

#endif

next += n;

}

template <typename P, const bool IsLiteral>

inline void Parser<P, IsLiteral>::ECConsumeMultiUnit(CharCount n /*= 1*/)

{

Assert(next + n <= inputLim);

next += n;

}

template <typename P, const bool IsLiteral>

inline void Parser<P, IsLiteral>::ECRevert(CharCount n /*= 1*/)

{

Assert(n + input <= next);

next -= n;

}

//

// Helpers

//

template <typename P, const bool IsLiteral>

int Parser<P, IsLiteral>::TryParseExtendedUnicodeEscape(Char& c, bool& previousSurrogatePart, bool trackSurrogatePair = false)

{

if (!scriptContext->GetConfig()->IsES6UnicodeExtensionsEnabled())

{

return 0;

}

if (!ECCanConsume(2) || ECLookahead(0) !='{' || !standardEncodedChars->IsHex(ECLookahead(1)))

{

return 0;

}

// The first character is mandatory to consume escape sequence, so we check for it above, at this stage we can set it as we already checked.

codepoint_t codePoint = standardEncodedChars->DigitValue(ECLookahead(1));

int i = 2;

while(ECCanConsume(i + 1) && standardEncodedChars->IsHex(ECLookahead(i)))

{

codePoint <<= 4;

codePoint += standardEncodedChars->DigitValue(ECLookahead(i));

if (codePoint > 0x10FFFF)

{

return 0;

}

i++;

}

if(!ECCanConsume(i + 1) || ECLookahead(i) != '}')

{

return 0;

}

uint consumptionNumber = i + 1;

Assert(consumptionNumber >= 3);

if (!previousSurrogatePart && trackSurrogatePair && this->scriptContext->GetConfig()->IsES6UnicodeExtensionsEnabled())

{

// Current location

TrackIfSurrogatePair(codePoint, (next - 1), consumptionNumber + 1);

}

char16 other;

// Generally if this code point is a single character, then we take it and return.

// If the character is made up of two characters then we emit the first and backtrack to the start of th escape sequence;

// Following that we check if we have already seen the first character, and if so emit the second and consume the entire escape sequence.

if (codePoint < 0x10000)

{

c = UTC(codePoint);

ECConsumeMultiUnit(consumptionNumber);

}

else if (previousSurrogatePart)

{

previousSurrogatePart = false;

Js::NumberUtilities::CodePointAsSurrogatePair(codePoint, &other, &c);

ECConsumeMultiUnit(consumptionNumber);

}

else

{

previousSurrogatePart = true;

Js::NumberUtilities::CodePointAsSurrogatePair(codePoint, &c, &other);

Assert(ECLookback(1) == 'u' && ECLookback(2) == '\\');

ECRevert(2);

}

return consumptionNumber;

}

// This function has the following 'knowledge':

// - A codepoint that might be part of a surrogate pair or part of one

// - A location where that codepoint is located

// - Previously tracked part of surrogate pair (tempLocationOfSurrogatePair, and codePointAtTempLocation), which is always a surrogate lower part.

// - A pointer to the current location of the linked list

// - If a previous location is tracked, then it is of a parsed character (not given character) before current, and not same to current

// This can't be asserted directly, and has to be followed by callers. Term pass can reset with each iteration, as well as this method in cases it needs.

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>:: TrackIfSurrogatePair(codepoint_t codePoint, const EncodedChar* location, uint32 consumptionLength)

{

Assert(codePoint < 0x110000);

Assert(location != nullptr);

Assert(location != this->tempLocationOfSurrogatePair);

if (Js::NumberUtilities::IsSurrogateLowerPart(codePoint))

{

this->tempLocationOfSurrogatePair = location;

this->codePointAtTempLocation = codePoint;

}

else

{

if(Js::NumberUtilities::IsSurrogateUpperPart(codePoint) && this->tempLocationOfSurrogatePair != nullptr)

{

Assert(Js::NumberUtilities::IsSurrogateLowerPart(codePointAtTempLocation));

consumptionLength = (uint32)(location - this->tempLocationOfSurrogatePair) + consumptionLength;

codePoint = Js::NumberUtilities::SurrogatePairAsCodePoint(codePointAtTempLocation, codePoint);

location = this->tempLocationOfSurrogatePair;

}

// At this point we can clear previous location, and then if codePoint is bigger than 0xFFFF store it, as we either received it or combined it above

this->tempLocationOfSurrogatePair = nullptr;

this->codePointAtTempLocation = 0;

}

if (codePoint > 0xFFFF)

{

this->positionAfterLastSurrogate = location + consumptionLength;

this->valueOfLastSurrogate = codePoint;

// When parsing without AST we aren't given an allocator. In addition, only the 2 lines above are used during Pass 0;

// while the bottom is used during Pass 1 (which isn't done when ParseNoAST)

if(this->ctAllocator != nullptr)

{

SurrogatePairTracker* node = Anew(this->ctAllocator, SurrogatePairTracker, location, this->tempLocationOfRange, codePoint, consumptionLength, this->m_cMultiUnits);

if (surrogatePairList == nullptr)

{

Assert(currentSurrogatePairNode == nullptr);

surrogatePairList = node;

currentSurrogatePairNode = node;

}

else

{

Assert(currentSurrogatePairNode != nullptr);

currentSurrogatePairNode->next = node;

currentSurrogatePairNode = node;

}

}

}

}

template <typename P, const bool IsLiteral>

Node* Parser<P, IsLiteral>::CreateSurrogatePairAtom(char16 lower, char16 upper)

{

MatchLiteralNode * literalNode = Anew(this->ctAllocator, MatchLiteralNode, 0, 0);

MatchCharNode lowerNode(lower);

MatchCharNode upperNode(upper);

AccumLiteral(literalNode, &lowerNode);

AccumLiteral(literalNode, &upperNode);

return literalNode;

}

// This function will create appropriate pairs of ranges and add them to the disjunction node.

// Terms used in comments:

// - A minor codePoint is smaller than major codePoint, and both define a range of codePoints above 0x10000; to avoid confusion between lower/upper denoting codeUnits composing the surrogate pair.

// - A boundary is a mod 0x400 alignment marker due to the nature of surrogate pairs representation. So the codepoint 0x10300 lies between boundaries 0x10000 and 0x10400.

// - A prefix is the range set used to represent the values from minorCodePoint to the first boundary above minorCodePoint if applicable.

// - A suffix is the range set used to represent the values from first boundary below majorCodePoint to the majorCodePoint if applicable.

// - A full range is the range set used to represent the values from first boundary above minorCodePoint to first boundary below majorCodePoint if applicable.

// The algorithm works as follows:

// 1. Determine minorBoundary (minorCodePoint - mod 0x400 +0x400) and majorBoundary (majorCodePoint - mod 0x400). minorBoundary > minorCodePoint and majorBoundary < majorCodePoint

// 2. Based on the codePoints and the boundaries, prefix, suffix, and full range is determined. Here are the rules:

// 2-a. If minorBoundary > majorBoundary, we have an inner boundary range, output just that.

// 2-b. If minorBoundary - 0x400u != minorCodepoint (i.e. codePoint doesn't lie right on a boundary to be part of a full range) we have a prefix.

// 2-c. If majorBoundary + 0x3FFu != majorCodepoint (i.e. codePoint doesn't lie right before a boundary to be part of a full range) we have a suffix.

// 2-d. We have a full range, if the two boundaries don't equal, OR the codePoints lie on the range boundaries opposite to what constitutes a prefix/suffix.

// Visual representation for sample range 0x10300 - 0x10900

// | [ _ | ^ ] |

// 0x10000 0x10800 0x11000

// [ ] - denote the actual range

// _ - minorBoundary

// ^ - majorBoundary

// | - other boundaries

// prefix is between [ and _

// suffix is between ^ and ]

// full range is between _ and ^

template <typename P, const bool IsLiteral>

AltNode* Parser<P, IsLiteral>::AppendSurrogateRangeToDisjunction(codepoint_t minorCodePoint, codepoint_t majorCodePoint, AltNode *lastAltNode)

{

Assert(minorCodePoint < majorCodePoint);

Assert(minorCodePoint >= 0x10000u);

Assert(majorCodePoint >= 0x10000u);

Assert(scriptContext->GetConfig()->IsES6UnicodeExtensionsEnabled() && unicodeFlagPresent);

char16 lowerMinorCodeUnit, upperMinorCodeUnit, lowerMajorCodeUnit, upperMajorCodeUnit;

Js::NumberUtilities::CodePointAsSurrogatePair(minorCodePoint, &lowerMinorCodeUnit, &upperMinorCodeUnit);

Js::NumberUtilities::CodePointAsSurrogatePair(majorCodePoint, &lowerMajorCodeUnit, &upperMajorCodeUnit);

// These boundaries represent whole range boundaries, as in 0x10000, 0x10400, 0x10800 etc

// minor boundary is the first boundary strictly above minorCodePoint

// major boundary is the first boundary below or equal to majorCodePoint

codepoint_t minorBoundary = minorCodePoint - (minorCodePoint % 0x400u) + 0x400u;

codepoint_t majorBoundary = majorCodePoint - (majorCodePoint % 0x400u);

Assert(minorBoundary >= 0x10000);

Assert(majorBoundary >= 0x10000);

AltNode* tailToAdd = nullptr;

// If the minor boundary is higher than major boundary, that means we have a range within the boundary and is less than 0x400

// Ex: 0x10430 - 0x10700 will have minor boundary of 0x10800 and major of 0x10400

// This pair will be represented in single range set.

const bool singleRange = minorBoundary > majorBoundary;

if (singleRange)

{

Assert(majorCodePoint - minorCodePoint < 0x400u);

Assert(lowerMinorCodeUnit == lowerMajorCodeUnit);

MatchCharNode* lowerCharNode = Anew(ctAllocator, MatchCharNode, lowerMinorCodeUnit);

MatchSetNode* setNode = Anew(ctAllocator, MatchSetNode, false, false);

setNode->set.SetRange(ctAllocator, (Char)upperMinorCodeUnit, (Char)upperMajorCodeUnit);

ConcatNode* concatNode = Anew(ctAllocator, ConcatNode, lowerCharNode, Anew(ctAllocator, ConcatNode, setNode, nullptr));

tailToAdd = Anew(ctAllocator, AltNode, concatNode, nullptr);

}

else

{

Node* prefixNode = nullptr, *suffixNode = nullptr;

const bool twoConsecutiveRanges = minorBoundary == majorBoundary;

// For minorBoundary,

if (minorBoundary - minorCodePoint == 1) // Single character in minor range

{

// The prefix is only a surrogate pair atom

prefixNode = CreateSurrogatePairAtom(lowerMinorCodeUnit, upperMinorCodeUnit);

}

else if (minorCodePoint != minorBoundary - 0x400u) // Minor range isn't full

{

Assert(minorBoundary - minorCodePoint < 0x400u);

MatchCharNode* lowerCharNode = Anew(ctAllocator, MatchCharNode, (Char)lowerMinorCodeUnit);

MatchSetNode* upperSetNode = Anew(ctAllocator, MatchSetNode, false);

upperSetNode->set.SetRange(ctAllocator, (Char)upperMinorCodeUnit, (Char)0xDFFFu);

prefixNode = Anew(ctAllocator, ConcatNode, lowerCharNode, Anew(ctAllocator, ConcatNode, upperSetNode, nullptr));

}

else // Full minor range

{

minorBoundary -= 0x400u;

}

if (majorBoundary == majorCodePoint) // Single character in major range

{

// The suffix is only a surrogate pair atom

suffixNode = CreateSurrogatePairAtom(lowerMajorCodeUnit, upperMajorCodeUnit);

majorBoundary -= 0x400u;

}

else if (majorBoundary + 0x3FFu != majorCodePoint) // Major range isn't full

{

Assert(majorCodePoint - majorBoundary < 0x3FFu);

MatchCharNode* lowerCharNode = Anew(ctAllocator, MatchCharNode, (Char)lowerMajorCodeUnit);

MatchSetNode* upperSetNode = Anew(ctAllocator, MatchSetNode, false, false);

upperSetNode->set.SetRange(ctAllocator, (Char)0xDC00u, (Char)upperMajorCodeUnit);

suffixNode = Anew(ctAllocator, ConcatNode, lowerCharNode, Anew(ctAllocator, ConcatNode, upperSetNode, nullptr));

majorBoundary -= 0x400u;

}

const bool nonFullConsecutiveRanges = twoConsecutiveRanges && prefixNode != nullptr && suffixNode != nullptr;

if (nonFullConsecutiveRanges)

{

Assert(suffixNode != nullptr);

Assert(minorCodePoint != minorBoundary - 0x400u);

Assert(majorBoundary + 0x3FFu != majorCodePoint);

// If the minor boundary is equal to major boundary, that means we have a cross boundary range that only needs 2 nodes for prefix/suffix.

// We can only cross one boundary.

Assert(majorCodePoint - minorCodePoint < 0x800u);

tailToAdd = Anew(ctAllocator, AltNode, prefixNode, Anew(ctAllocator, AltNode, suffixNode, nullptr));

}

else

{

// We have 3 sets of ranges, comprising of prefix, full and suffix.

Assert(majorCodePoint - minorCodePoint >= 0x400u);

Assert((prefixNode != nullptr && suffixNode != nullptr) // Spanning more than two ranges

|| (prefixNode == nullptr && minorBoundary == minorCodePoint) // Two consecutive ranges and the minor is full

|| (suffixNode == nullptr && majorBoundary + 0x3FFu == majorCodePoint)); // Two consecutive ranges and the major is full

Node* lowerOfFullRange;

char16 lowerMinorBoundary, lowerMajorBoundary, ignore;

Js::NumberUtilities::CodePointAsSurrogatePair(minorBoundary, &lowerMinorBoundary, &ignore);

bool singleFullRange = majorBoundary == minorBoundary;

if (singleFullRange)

{

// The lower part of the full range is simple a surrogate lower char

lowerOfFullRange = Anew(ctAllocator, MatchCharNode, (Char)lowerMinorBoundary);

}

else

{

Js::NumberUtilities::CodePointAsSurrogatePair(majorBoundary, &lowerMajorBoundary, &ignore);

MatchSetNode* setNode = Anew(ctAllocator, MatchSetNode, false, false);

setNode->set.SetRange(ctAllocator, (Char)lowerMinorBoundary, (Char)lowerMajorBoundary);

lowerOfFullRange = setNode;

}

MatchSetNode* fullUpperRange = Anew(ctAllocator, MatchSetNode, false, false);

fullUpperRange->set.SetRange(ctAllocator, (Char)0xDC00u, (Char)0xDFFFu);

// These are added in the following order [full] [prefix][suffix]

// This is doing by prepending, so in reverse.

if (suffixNode != nullptr)

{

tailToAdd = Anew(ctAllocator, AltNode, suffixNode, tailToAdd);

}

if (prefixNode != nullptr)

{

tailToAdd = Anew(ctAllocator, AltNode, prefixNode, tailToAdd);

}

tailToAdd = Anew(ctAllocator, AltNode, Anew(ctAllocator, ConcatNode, lowerOfFullRange, Anew(ctAllocator, ConcatNode, fullUpperRange, nullptr)), tailToAdd);

}

}

if (lastAltNode != nullptr)

{

Assert(lastAltNode->tail == nullptr);

lastAltNode->tail = tailToAdd;

}

return tailToAdd;

}

template <typename P, const bool IsLiteral>

AltNode* Parser<P, IsLiteral>::AppendSurrogatePairToDisjunction(codepoint_t codePoint, AltNode *lastAltNode)

{

char16 lower, upper;

Js::NumberUtilities::CodePointAsSurrogatePair(codePoint, &lower, &upper);

AltNode* tailNode = Anew(ctAllocator, AltNode, CreateSurrogatePairAtom(lower, upper), nullptr);

if (lastAltNode != nullptr)

{

lastAltNode->tail = tailNode;

}

return tailNode;

}

//

// Errors

//

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::Fail(HRESULT error)

{

throw ParseError(inBody, Pos(), Chars<EncodedChar>::OSB(next, input), error);

}

// This doesn't throw, but stores first error code for throwing later

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::DeferredFailIfUnicode(HRESULT error)

{

Assert(this->scriptContext->GetConfig()->IsES6UnicodeExtensionsEnabled());

if (this->deferredIfUnicodeError == nullptr)

{

this->deferredIfUnicodeError = Anew(ctAllocator, ParseError, inBody, Pos(), Chars<EncodedChar>::OSB(next, input), error);

}

}

// This doesn't throw, but stores first error code for throwing later

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::DeferredFailIfNotUnicode(HRESULT error)

{

Assert(this->scriptContext->GetConfig()->IsES6UnicodeExtensionsEnabled());

if (this->deferredIfNotUnicodeError == nullptr)

{

this->deferredIfNotUnicodeError = Anew(ctAllocator, ParseError, inBody, Pos(), Chars<EncodedChar>::OSB(next, input), error);

}

}

template <typename P, const bool IsLiteral>

inline void Parser<P, IsLiteral>::ECMust(EncodedChar ec, HRESULT error)

{

// We never look for 0

Assert(ec != 0);

if (ECLookahead() != ec)

Fail(error);

ECConsume();

}

template <typename P, const bool IsLiteral>

inline char16 Parser<P, IsLiteral>::NextChar()

{

Assert(!IsEOF());

// Could be an embedded 0

Char c = this->template ReadFull<true>(next, inputLim);

// No embedded newlines in literals

if (IsLiteral && standardChars->IsNewline(c))

Fail(ERRnoSlash);

return c;

}

//

// Patterns/Disjunctions/Alternatives

//

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::PatternPass0()

{

this->positionAfterLastSurrogate = nullptr;

this->deferredIfNotUnicodeError = nullptr;

this->deferredIfUnicodeError = nullptr;

DisjunctionPass0(0);

}

template <typename P, const bool IsLiteral>

Node* Parser<P, IsLiteral>::PatternPass1()

{

return DisjunctionPass1();

}

template <typename P, const bool IsLiteral>

Node* Parser<P, IsLiteral>::UnionNodes(Node* prev, Node* curr)

{

if (prev->tag == Node::MatchChar)

{

MatchCharNode* prevChar = (MatchCharNode*)prev;

if (curr->tag == Node::MatchChar)

{

MatchCharNode* currChar = (MatchCharNode*)curr;

if (prevChar->cs[0] == currChar->cs[0])

// Just ignore current node

return prevChar;

else

{

// Union chars into new set

MatchSetNode* setNode = Anew(ctAllocator, MatchSetNode, false);

setNode->set.Set(ctAllocator, prevChar->cs[0]);

setNode->set.Set(ctAllocator, currChar->cs[0]);

return setNode;

}

}

else if (curr->tag == Node::MatchSet)

{

MatchSetNode* currSet = (MatchSetNode*)curr;

if (currSet->isNegation)

// Can't merge

return 0;

else

{

// Union chars into new set

MatchSetNode* setNode = Anew(ctAllocator, MatchSetNode, false);

setNode->set.Set(ctAllocator, prevChar->cs[0]) ;

setNode->set.UnionInPlace(ctAllocator, currSet->set);

return setNode;

}

}

else

// Can't merge

return 0;

}

else if (prev->tag == Node::MatchSet)

{

MatchSetNode* prevSet = (MatchSetNode*)prev;

if (prevSet->isNegation)

// Can't merge

return 0;

else if (curr->tag == Node::MatchChar)

{

MatchCharNode* currChar = (MatchCharNode*)curr;

// Include char in prev set

prevSet->set.Set(ctAllocator, currChar->cs[0]);

return prevSet;

}

else if (curr->tag == Node::MatchSet)

{

MatchSetNode* currSet = (MatchSetNode*)curr;

if (currSet->isNegation)

// Can't merge

return 0;

else

{

// Include chars in prev set

prevSet->set.UnionInPlace(ctAllocator, currSet->set);

return prevSet;

}

}

else

// Can't merge

return 0;

}

else

// Can't merge

return 0;

}

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::DisjunctionPass0(int depth)

{

AlternativePass0(depth);

while (true)

{

// Could be terminating 0

if (ECLookahead() != '|')

return;

ECConsume();

AlternativePass0(depth);

}

}

template <typename P, const bool IsLiteral>

Node* Parser<P, IsLiteral>::DisjunctionPass1()

{

// Maintain the invariants:

// - alt lists have two or more items

// - alt list items are never alt lists (so we must inline them)

// - an alt list never contains two consecutive match-character/match-set nodes

// (so we must union consecutive items into a single set)

Node* node = AlternativePass1();

AltNode* last = 0;

// First node may be an alternative

if (node->tag == Node::Alt)

{

last = (AltNode*)node;

while (last->tail != 0)

last = last->tail;

}

while (true)

{

// Could be terminating 0

if (ECLookahead() != '|')

return node;

ECConsume(); // '|'

Node* next = AlternativePass1();

AnalysisAssert(next != nullptr);

Node* revisedPrev = UnionNodes(last == 0 ? node : last->head, next);

if (revisedPrev != 0)

{

// Can merge next into previously seen alternative

if (last == 0)

node = revisedPrev;

else

last->head = revisedPrev;

}

else if (next->tag == Node::Alt)

{

AltNode* nextList = (AltNode*)next;

// Append inner list to current list

revisedPrev = UnionNodes(last == 0 ? node : last->head, nextList->head);

if (revisedPrev != 0)

{

// Can merge head of list into previously seen alternative

if (last ==0)

node = revisedPrev;

else

last->head = revisedPrev;

nextList = nextList->tail;

}

AnalysisAssert(nextList != nullptr);

if (last == 0)

node = Anew(ctAllocator, AltNode, node, nextList);

else

last->tail = nextList;

while (nextList->tail != 0)

nextList = nextList->tail;

last = nextList;

}

else

{

// Append node

AltNode* cons = Anew(ctAllocator, AltNode, next, 0);

if (last == 0)

node = Anew(ctAllocator, AltNode, node, cons);

else

last->tail = cons;

last = cons;

}

}

}

template <typename P, const bool IsLiteral>

inline bool Parser<P, IsLiteral>::IsEndOfAlternative()

{

EncodedChar ec = ECLookahead();

// Could be terminating 0, but embedded 0 is part of alternative

return (ec == 0 && IsEOF()) || ec == ')' || ec == '|' || (IsLiteral && ec == '/');

}

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::EnsureLitbuf(CharCount size)

{

if (litbufLen - litbufNext < size)

{

CharCount newLen = max(litbufLen, initLitbufSize);

while (newLen < litbufNext + size)

newLen *= 2;

litbuf = (Char*)ctAllocator->Realloc(litbuf, litbufLen * sizeof(Char), newLen * sizeof(Char));

litbufLen = newLen;

}

}

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::AccumLiteral(MatchLiteralNode* deferredLiteralNode, Node* charOrLiteralNode)

{

Assert(charOrLiteralNode->tag == Node::MatchChar || charOrLiteralNode->tag == Node::MatchLiteral);

CharCount addLen = charOrLiteralNode->LiteralLength();

Assert(addLen > 0);

if (deferredLiteralNode->length == 0)

{

// Start a new literal

EnsureLitbuf(addLen);

deferredLiteralNode->offset = litbufNext;

deferredLiteralNode->length = addLen;

charOrLiteralNode->AppendLiteral(litbufNext, litbufLen, litbuf);

}

else if (deferredLiteralNode->offset + deferredLiteralNode->length == litbufNext)

{

// Keep growing the current literal

EnsureLitbuf(addLen);

charOrLiteralNode->AppendLiteral(litbufNext, litbufLen, litbuf);

deferredLiteralNode->length += addLen;

}

else if (charOrLiteralNode->tag == Node::MatchLiteral && deferredLiteralNode->offset + deferredLiteralNode->length == ((MatchLiteralNode*)charOrLiteralNode)->offset)

{

// Absorb next literal into current literal since they are adjacent

deferredLiteralNode->length += addLen;

}

else

{

// Abandon current literal and start a fresh one (leaves gap)

EnsureLitbuf(deferredLiteralNode->length + addLen);

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

deferredLiteralNode->offset = litbufNext;

litbufNext += deferredLiteralNode->length;

charOrLiteralNode->AppendLiteral(litbufNext, litbufLen, litbuf);

deferredLiteralNode->length += addLen;

}

}

template <typename P, const bool IsLiteral>

Node* Parser<P, IsLiteral>::FinalTerm(Node* node, MatchLiteralNode* deferredLiteralNode)

{

if (node == deferredLiteralNode)

{

#if DBG

if (deferredLiteralNode->length == 0)

Assert(false);

#endif

Assert(deferredLiteralNode->offset < litbufNext);

Assert(deferredLiteralNode->offset + deferredLiteralNode->length <= litbufNext);

if (deferredLiteralNode->length == 1)

{

node = Anew(ctAllocator, MatchCharNode, litbuf[deferredLiteralNode->offset]);

if (deferredLiteralNode->offset + deferredLiteralNode->length == litbufNext)

// Reclaim last added character

litbufNext--;

// else: leave a gap in the literal buffer

}

else

node = Anew(ctAllocator, MatchLiteralNode, *deferredLiteralNode);

deferredLiteralNode->offset = 0;

deferredLiteralNode->length = 0;

}

return node;

}

template <typename P, const bool IsLiteral>

void Parser<P, IsLiteral>::AlternativePass0(int depth)

{

while (!IsEndOfAlternative())

TermPass0(depth);

}

template <typename P, const bool IsLiteral>

Node* Parser<P, IsLiteral>::AlternativePass1()

{

if (IsEndOfAlternative())

return Anew(ctAllocator, SimpleNode, Node::Empty);

MatchCharNode deferredCharNode(0);

MatchLiteralNode deferredLiteralNode(0, 0);

// Maintain the invariants:

// - concat lists have two or more items

// - concat list items are never concat lists

// - a concat list never contains two consecutive match-character/match-literal nodes

bool previousSurrogatePart = false;

Node* node = TermPass1(&deferredCharNode, previousSurrogatePart);

AnalysisAssert(node != nullptr);

ConcatNode* last = 0;

// First node may be a concat

if (node->tag == Node::Concat)

{

last = (ConcatNode*)node;

while (last->tail != 0)

last = last->tail;

}

if (last == 0)

{

if (node->LiteralLength() > 0)

{

// Begin a new literal

AccumLiteral(&deferredLiteralNode, node);

node = &deferredLiteralNode;

}

}

else

{

if (last->head->LiteralLength() > 0)

{

// Begin a new literal

AccumLiteral(&deferredLiteralNode, last->head);

last->head = &deferredLiteralNode;

}

}

while (!IsEndOfAlternative())

{

Node* next = TermPass1(&deferredCharNode, previousSurrogatePart);

AnalysisAssert(next != nullptr);

if (next->LiteralLength() > 0)

{

// Begin a new literal or grow the existing literal

AccumLiteral(&deferredLiteralNode, next);

if (last == 0)

{

if (node != &deferredLiteralNode)

{

// So far we have first item and the current literal

ConcatNode* cons = Anew(ctAllocator, ConcatNode, &deferredLiteralNode, 0);

node = Anew(ctAllocator, ConcatNode, node, cons);

last = cons;

}

// else: keep growing first literal

}

else

{

if (last->head != &deferredLiteralNode)

{

// Append a new literal node

ConcatNode* cons = Anew(ctAllocator, ConcatNode, &deferredLiteralNode, 0);

last->tail = cons;

last = cons;

}

// else: keep growing current literal

}

}

else if (next->tag == Node::Concat)

{

// Append this list to accumulated list

ConcatNode* nextList = (ConcatNode*)next;

if (nextList->head->LiteralLength() > 0 &&

((last == 0 && node == &deferredLiteralNode) ||

(last != 0 && last->head == &deferredLiteralNode)))

{

// Absorb the next character or literal into the current literal

// (may leave a gab in litbuf)

AccumLiteral(&deferredLiteralNode, nextList->head);

nextList = nextList->tail;

// List has at least two items

AnalysisAssert(nextList != 0);

// List should be in canonical form, so no consecutive chars/literals

Assert(nextList->head->LiteralLength() == 0);

}

if (last == 0)

node = Anew(ctAllocator, ConcatNode, FinalTerm(node, &deferredLiteralNode), nextList);

else

{

last->head = FinalTerm(last->head, &deferredLiteralNode);

last->tail = nextList;

}

while (nextList->tail != 0)

nextList = nextList->tail;

last = nextList;

// No outstanding literals

Assert(deferredLiteralNode.length == 0);

if (last->head->LiteralLength() > 0)

{

// If the list ends with a literal, transfer it into deferredLiteralNode

// so we can continue accumulating (won't leave a gab in litbuf)

AccumLiteral(&deferredLiteralNode, last->head);

// Can discard MatchLiteralNode since it lives in compile-time allocator

last->head = &deferredLiteralNode;

}

}

else

{