CharacterClassConstructor(bool isCaseInsensitive = false)

: m_isCaseInsensitive(isCaseInsensitive)

{

}

void reset()

{

m_matches.clear();

m_ranges.clear();

m_matchesUnicode.clear();

m_rangesUnicode.clear();

}

void append(const CharacterClass* other)

{

for (size_t i = 0; i < other->m_matches.size(); ++i)

addSorted(m_matches, other->m_matches[i]);

for (size_t i = 0; i < other->m_ranges.size(); ++i)

addSortedRange(m_ranges, other->m_ranges[i].begin, other->m_ranges[i].end);

for (size_t i = 0; i < other->m_matchesUnicode.size(); ++i)

addSorted(m_matchesUnicode, other->m_matchesUnicode[i]);

for (size_t i = 0; i < other->m_rangesUnicode.size(); ++i)

addSortedRange(m_rangesUnicode, other->m_rangesUnicode[i].begin, other->m_rangesUnicode[i].end);

}

void putChar(UChar ch)

{

// Handle ascii cases.

if (ch <= 0x7f) {

if (m_isCaseInsensitive && isASCIIAlpha(ch)) {

addSorted(m_matches, toASCIIUpper(ch));

addSorted(m_matches, toASCIILower(ch));

} else

addSorted(m_matches, ch);

return;

}

// Simple case, not a case-insensitive match.

if (!m_isCaseInsensitive) {

addSorted(m_matchesUnicode, ch);

return;

}

// Add multiple matches, if necessary.

const UCS2CanonicalizationRange* info = rangeInfoFor(ch);

if (info->type == CanonicalizeUnique)

addSorted(m_matchesUnicode, ch);

else

putUnicodeIgnoreCase(ch, info);

}

void putUnicodeIgnoreCase(UChar ch, const UCS2CanonicalizationRange* info)

{

ASSERT(m_isCaseInsensitive);

ASSERT(ch > 0x7f);

ASSERT(ch >= info->begin && ch <= info->end);

ASSERT(info->type != CanonicalizeUnique);

if (info->type == CanonicalizeSet) {

for (const uint16_t* set = characterSetInfo[info->value]; (ch = *set); ++set)

addSorted(m_matchesUnicode, ch);

} else {

addSorted(m_matchesUnicode, ch);

addSorted(m_matchesUnicode, getCanonicalPair(info, ch));

}

}

void putRange(UChar lo, UChar hi)

{

if (lo <= 0x7f) {

char asciiLo = lo;

char asciiHi = std::min(hi, (UChar)0x7f);

addSortedRange(m_ranges, lo, asciiHi);

if (m_isCaseInsensitive) {

if ((asciiLo <= 'Z') && (asciiHi >= 'A'))

addSortedRange(m_ranges, std::max(asciiLo, 'A')+('a'-'A'), std::min(asciiHi, 'Z')+('a'-'A'));

if ((asciiLo <= 'z') && (asciiHi >= 'a'))

addSortedRange(m_ranges, std::max(asciiLo, 'a')+('A'-'a'), std::min(asciiHi, 'z')+('A'-'a'));

}

}

if (hi <= 0x7f)

return;

lo = std::max(lo, (UChar)0x80);

addSortedRange(m_rangesUnicode, lo, hi);

if (!m_isCaseInsensitive)

return;

const UCS2CanonicalizationRange* info = rangeInfoFor(lo);

while (true) {

// Handle the range [lo .. end]

UChar end = std::min<UChar>(info->end, hi);

switch (info->type) {

case CanonicalizeUnique:

// Nothing to do - no canonical equivalents.

break;

case CanonicalizeSet: {

UChar ch;

for (const uint16_t* set = characterSetInfo[info->value]; (ch = *set); ++set)

addSorted(m_matchesUnicode, ch);

break;

}

case CanonicalizeRangeLo:

addSortedRange(m_rangesUnicode, lo + info->value, end + info->value);

break;

case CanonicalizeRangeHi:

addSortedRange(m_rangesUnicode, lo - info->value, end - info->value);

break;

case CanonicalizeAlternatingAligned:

// Use addSortedRange since there is likely an abutting range to combine with.

if (lo & 1)

addSortedRange(m_rangesUnicode, lo - 1, lo - 1);

if (!(end & 1))

addSortedRange(m_rangesUnicode, end + 1, end + 1);

break;

case CanonicalizeAlternatingUnaligned:

// Use addSortedRange since there is likely an abutting range to combine with.

if (!(lo & 1))

addSortedRange(m_rangesUnicode, lo - 1, lo - 1);

if (end & 1)

addSortedRange(m_rangesUnicode, end + 1, end + 1);

break;

}

if (hi == end)

return;

++info;

lo = info->begin;

};

}

PassOwnPtr<CharacterClass> charClass()

{

OwnPtr<CharacterClass> characterClass = adoptPtr(new CharacterClass);

characterClass->m_matches.swap(m_matches);

characterClass->m_ranges.swap(m_ranges);

characterClass->m_matchesUnicode.swap(m_matchesUnicode);

characterClass->m_rangesUnicode.swap(m_rangesUnicode);

return characterClass.release();

}

void addSorted(Vector<UChar>& matches, UChar ch)

{

unsigned pos = 0;

unsigned range = matches.size();

// binary chop, find position to insert char.

while (range) {

unsigned index = range >> 1;

int val = matches[pos+index] - ch;

if (!val)

return;

else if (val > 0)

range = index;

else {

pos += (index+1);

range -= (index+1);

}

}

if (pos == matches.size())

matches.append(ch);

else

matches.insert(pos, ch);

}

void addSortedRange(Vector<CharacterRange>& ranges, UChar lo, UChar hi)

{

unsigned end = ranges.size();

// Simple linear scan - I doubt there are that many ranges anyway...

// feel free to fix this with something faster (eg binary chop).

for (unsigned i = 0; i < end; ++i) {

// does the new range fall before the current position in the array

if (hi < ranges[i].begin) {

// optional optimization: concatenate appending ranges? - may not be worthwhile.

if (hi == (ranges[i].begin - 1)) {

ranges[i].begin = lo;

return;

}

ranges.insert(i, CharacterRange(lo, hi));

return;

}

// Okay, since we didn't hit the last case, the end of the new range is definitely at or after the begining

// If the new range start at or before the end of the last range, then the overlap (if it starts one after the

// end of the last range they concatenate, which is just as good.

if (lo <= (ranges[i].end + 1)) {

// found an intersect! we'll replace this entry in the array.

ranges[i].begin = std::min(ranges[i].begin, lo);

ranges[i].end = std::max(ranges[i].end, hi);

// now check if the new range can subsume any subsequent ranges.

unsigned next = i+1;

// each iteration of the loop we will either remove something from the list, or break the loop.

while (next < ranges.size()) {

if (ranges[next].begin <= (ranges[i].end + 1)) {

// the next entry now overlaps / concatenates this one.

ranges[i].end = std::max(ranges[i].end, ranges[next].end);

ranges.remove(next);

} else

break;

}

return;

}

}

// CharacterRange comes after all existing ranges.

ranges.append(CharacterRange(lo, hi));

}

bool m_isCaseInsensitive;

Vector<UChar> m_matches;

Vector<CharacterRange> m_ranges;

Vector<UChar> m_matchesUnicode;

Vector<CharacterRange> m_rangesUnicode;

YarrPatternConstructor(YarrPattern& pattern)

: m_pattern(pattern)

, m_characterClassConstructor(pattern.m_ignoreCase)

, m_invertParentheticalAssertion(false)

{

OwnPtr<PatternDisjunction> body = adoptPtr(new PatternDisjunction);

m_pattern.m_body = body.get();

m_alternative = body->addNewAlternative();

m_pattern.m_disjunctions.append(body.release());

}

~YarrPatternConstructor()

{

}

void reset()

{

m_pattern.reset();

m_characterClassConstructor.reset();

OwnPtr<PatternDisjunction> body = adoptPtr(new PatternDisjunction);

m_pattern.m_body = body.get();

m_alternative = body->addNewAlternative();

m_pattern.m_disjunctions.append(body.release());

}

void assertionBOL()

{

if (!m_alternative->m_terms.size() & !m_invertParentheticalAssertion) {

m_alternative->m_startsWithBOL = true;

m_alternative->m_containsBOL = true;

m_pattern.m_containsBOL = true;

}

m_alternative->m_terms.append(PatternTerm::BOL());

}

void assertionEOL()

{

m_alternative->m_terms.append(PatternTerm::EOL());

}

void assertionWordBoundary(bool invert)

{

m_alternative->m_terms.append(PatternTerm::WordBoundary(invert));

}

void atomPatternCharacter(UChar ch)

{

// We handle case-insensitive checking of unicode characters which do have both

// cases by handling them as if they were defined using a CharacterClass.

if (!m_pattern.m_ignoreCase || isASCII(ch)) {

m_alternative->m_terms.append(PatternTerm(ch));

return;

}

const UCS2CanonicalizationRange* info = rangeInfoFor(ch);

if (info->type == CanonicalizeUnique) {

m_alternative->m_terms.append(PatternTerm(ch));

return;

}

m_characterClassConstructor.putUnicodeIgnoreCase(ch, info);

OwnPtr<CharacterClass> newCharacterClass = m_characterClassConstructor.charClass();

m_alternative->m_terms.append(PatternTerm(newCharacterClass.get(), false));

m_pattern.m_userCharacterClasses.append(newCharacterClass.release());

}

void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)

{

switch (classID) {

case DigitClassID:

m_alternative->m_terms.append(PatternTerm(m_pattern.digitsCharacterClass(), invert));

break;

case SpaceClassID:

m_alternative->m_terms.append(PatternTerm(m_pattern.spacesCharacterClass(), invert));

break;

case WordClassID:

m_alternative->m_terms.append(PatternTerm(m_pattern.wordcharCharacterClass(), invert));

break;

case NewlineClassID:

m_alternative->m_terms.append(PatternTerm(m_pattern.newlineCharacterClass(), invert));

break;

}

}

void atomCharacterClassBegin(bool invert = false)

{

m_invertCharacterClass = invert;

}

void atomCharacterClassAtom(UChar ch)

{

m_characterClassConstructor.putChar(ch);

}

void atomCharacterClassRange(UChar begin, UChar end)

{

m_characterClassConstructor.putRange(begin, end);

}

void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert)

{

ASSERT(classID != NewlineClassID);

switch (classID) {

case DigitClassID:

m_characterClassConstructor.append(invert ? m_pattern.nondigitsCharacterClass() : m_pattern.digitsCharacterClass());

break;

case SpaceClassID:

m_characterClassConstructor.append(invert ? m_pattern.nonspacesCharacterClass() : m_pattern.spacesCharacterClass());

break;

case WordClassID:

m_characterClassConstructor.append(invert ? m_pattern.nonwordcharCharacterClass() : m_pattern.wordcharCharacterClass());

break;

default:

RELEASE_ASSERT_NOT_REACHED();

}

}

void atomCharacterClassEnd()

{

OwnPtr<CharacterClass> newCharacterClass = m_characterClassConstructor.charClass();

m_alternative->m_terms.append(PatternTerm(newCharacterClass.get(), m_invertCharacterClass));

m_pattern.m_userCharacterClasses.append(newCharacterClass.release());

}

void atomParenthesesSubpatternBegin(bool capture = true)

{

unsigned subpatternId = m_pattern.m_numSubpatterns + 1;

if (capture)

m_pattern.m_numSubpatterns++;

OwnPtr<PatternDisjunction> parenthesesDisjunction = adoptPtr(new PatternDisjunction(m_alternative));

m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction.get(), capture, false));

m_alternative = parenthesesDisjunction->addNewAlternative();

m_pattern.m_disjunctions.append(parenthesesDisjunction.release());

}

void atomParentheticalAssertionBegin(bool invert = false)

{

OwnPtr<PatternDisjunction> parenthesesDisjunction = adoptPtr(new PatternDisjunction(m_alternative));

m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction.get(), false, invert));

m_alternative = parenthesesDisjunction->addNewAlternative();

m_invertParentheticalAssertion = invert;

m_pattern.m_disjunctions.append(parenthesesDisjunction.release());

}

void atomParenthesesEnd()

{

ASSERT(m_alternative->m_parent);

ASSERT(m_alternative->m_parent->m_parent);

PatternDisjunction* parenthesesDisjunction = m_alternative->m_parent;

m_alternative = m_alternative->m_parent->m_parent;

PatternTerm& lastTerm = m_alternative->lastTerm();

unsigned numParenAlternatives = parenthesesDisjunction->m_alternatives.size();

unsigned numBOLAnchoredAlts = 0;

for (unsigned i = 0; i < numParenAlternatives; i++) {

// Bubble up BOL flags

if (parenthesesDisjunction->m_alternatives[i]->m_startsWithBOL)

numBOLAnchoredAlts++;

}

if (numBOLAnchoredAlts) {

m_alternative->m_containsBOL = true;

// If all the alternatives in parens start with BOL, then so does this one

if (numBOLAnchoredAlts == numParenAlternatives)

m_alternative->m_startsWithBOL = true;

}

lastTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;

m_invertParentheticalAssertion = false;

}

void atomBackReference(unsigned subpatternId)

{

ASSERT(subpatternId);

m_pattern.m_containsBackreferences = true;

m_pattern.m_maxBackReference = std::max(m_pattern.m_maxBackReference, subpatternId);

if (subpatternId > m_pattern.m_numSubpatterns) {

m_alternative->m_terms.append(PatternTerm::ForwardReference());

return;

}

PatternAlternative* currentAlternative = m_alternative;

ASSERT(currentAlternative);

// Note to self: if we waited until the AST was baked, we could also remove forwards refs

while ((currentAlternative = currentAlternative->m_parent->m_parent)) {

PatternTerm& term = currentAlternative->lastTerm();

ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));

if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.capture() && (subpatternId == term.parentheses.subpatternId)) {

m_alternative->m_terms.append(PatternTerm::ForwardReference());

return;

}

}

m_alternative->m_terms.append(PatternTerm(subpatternId));

}

// deep copy the argument disjunction. If filterStartsWithBOL is true,

// skip alternatives with m_startsWithBOL set true.

PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction, bool filterStartsWithBOL = false)

{

OwnPtr<PatternDisjunction> newDisjunction;

for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {

PatternAlternative* alternative = disjunction->m_alternatives[alt].get();

if (!filterStartsWithBOL || !alternative->m_startsWithBOL) {

if (!newDisjunction) {

newDisjunction = adoptPtr(new PatternDisjunction());

newDisjunction->m_parent = disjunction->m_parent;

}

PatternAlternative* newAlternative = newDisjunction->addNewAlternative();

newAlternative->m_terms.reserveInitialCapacity(alternative->m_terms.size());

for (unsigned i = 0; i < alternative->m_terms.size(); ++i)

newAlternative->m_terms.append(copyTerm(alternative->m_terms[i], filterStartsWithBOL));

}

}

if (!newDisjunction)

return 0;

PatternDisjunction* copiedDisjunction = newDisjunction.get();

m_pattern.m_disjunctions.append(newDisjunction.release());

return copiedDisjunction;

}

PatternTerm copyTerm(PatternTerm& term, bool filterStartsWithBOL = false)

{

if ((term.type != PatternTerm::TypeParenthesesSubpattern) && (term.type != PatternTerm::TypeParentheticalAssertion))

return PatternTerm(term);

PatternTerm termCopy = term;

termCopy.parentheses.disjunction = copyDisjunction(termCopy.parentheses.disjunction, filterStartsWithBOL);

return termCopy;

}

void quantifyAtom(unsigned min, unsigned max, bool greedy)

{

ASSERT(min <= max);

ASSERT(m_alternative->m_terms.size());

if (!max) {

m_alternative->removeLastTerm();

return;

}

PatternTerm& term = m_alternative->lastTerm();

ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);

ASSERT((term.quantityCount == 1) && (term.quantityType == QuantifierFixedCount));

if (term.type == PatternTerm::TypeParentheticalAssertion) {

// If an assertion is quantified with a minimum count of zero, it can simply be removed.

// This arises from the RepeatMatcher behaviour in the spec. Matching an assertion never

// results in any input being consumed, however the continuation passed to the assertion

// (called in steps, 8c and 9 of the RepeatMatcher definition, ES5.1 15.10.2.5) will

// reject all zero length matches (see step 2.1). A match from the continuation of the

// expression will still be accepted regardless (via steps 8a and 11) - the upshot of all

// this is that matches from the assertion are not required, and won't be accepted anyway,

// so no need to ever run it.

if (!min)

m_alternative->removeLastTerm();

// We never need to run an assertion more than once. Subsequent interations will be run

// with the same start index (since assertions are non-capturing) and the same captures

// (per step 4 of RepeatMatcher in ES5.1 15.10.2.5), and as such will always produce the

// same result and captures. If the first match succeeds then the subsequent (min - 1)

// matches will too. Any additional optional matches will fail (on the same basis as the

// minimum zero quantified assertions, above), but this will still result in a match.

return;

}

if (min == 0)

term.quantify(max, greedy ? QuantifierGreedy : QuantifierNonGreedy);

else if (min == max)

term.quantify(min, QuantifierFixedCount);

else {

term.quantify(min, QuantifierFixedCount);

m_alternative->m_terms.append(copyTerm(term));

// NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....

m_alternative->lastTerm().quantify((max == quantifyInfinite) ? max : max - min, greedy ? QuantifierGreedy : QuantifierNonGreedy);

if (m_alternative->lastTerm().type == PatternTerm::TypeParenthesesSubpattern)

m_alternative->lastTerm().parentheses.isCopy = true;

}

}

void disjunction()

{

m_alternative = m_alternative->m_parent->addNewAlternative();

}

unsigned setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition)

{

alternative->m_hasFixedSize = true;

Checked<unsigned> currentInputPosition = initialInputPosition;

for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {

PatternTerm& term = alternative->m_terms[i];

switch (term.type) {

case PatternTerm::TypeAssertionBOL:

case PatternTerm::TypeAssertionEOL:

case PatternTerm::TypeAssertionWordBoundary:

term.inputPosition = currentInputPosition.unsafeGet();

break;

case PatternTerm::TypeBackReference:

term.inputPosition = currentInputPosition.unsafeGet();

term.frameLocation = currentCallFrameSize;

currentCallFrameSize += YarrStackSpaceForBackTrackInfoBackReference;

alternative->m_hasFixedSize = false;

break;

case PatternTerm::TypeForwardReference:

break;

case PatternTerm::TypePatternCharacter:

term.inputPosition = currentInputPosition.unsafeGet();

if (term.quantityType != QuantifierFixedCount) {

term.frameLocation = currentCallFrameSize;

currentCallFrameSize += YarrStackSpaceForBackTrackInfoPatternCharacter;

alternative->m_hasFixedSize = false;

} else

currentInputPosition += term.quantityCount;

break;

case PatternTerm::TypeCharacterClass:

term.inputPosition = currentInputPosition.unsafeGet();

if (term.quantityType != QuantifierFixedCount) {

term.frameLocation = currentCallFrameSize;

currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;

alternative->m_hasFixedSize = false;

} else

currentInputPosition += term.quantityCount;

break;

case PatternTerm::TypeParenthesesSubpattern:

// Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.

term.frameLocation = currentCallFrameSize;

if (term.quantityCount == 1 && !term.parentheses.isCopy) {

if (term.quantityType != QuantifierFixedCount)

currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesOnce;

currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet());

// If quantity is fixed, then pre-check its minimum size.

if (term.quantityType == QuantifierFixedCount)

currentInputPosition += term.parentheses.disjunction->m_minimumSize;

term.inputPosition = currentInputPosition.unsafeGet();

} else if (term.parentheses.isTerminal) {

currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesTerminal;

currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet());

term.inputPosition = currentInputPosition.unsafeGet();

} else {

term.inputPosition = currentInputPosition.unsafeGet();

setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition.unsafeGet());

currentCallFrameSize += YarrStackSpaceForBackTrackInfoParentheses;

}

// Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.

alternative->m_hasFixedSize = false;

break;

case PatternTerm::TypeParentheticalAssertion:

term.inputPosition = currentInputPosition.unsafeGet();

term.frameLocation = currentCallFrameSize;

currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition.unsafeGet());

break;

case PatternTerm::TypeDotStarEnclosure:

alternative->m_hasFixedSize = false;

term.inputPosition = initialInputPosition;

break;

}

}

alternative->m_minimumSize = (currentInputPosition - initialInputPosition).unsafeGet();

return currentCallFrameSize;

}

unsigned setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition)

{

if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))

initialCallFrameSize += YarrStackSpaceForBackTrackInfoAlternative;

unsigned minimumInputSize = UINT_MAX;

unsigned maximumCallFrameSize = 0;

bool hasFixedSize = true;

for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {

PatternAlternative* alternative = disjunction->m_alternatives[alt].get();

unsigned currentAlternativeCallFrameSize = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition);

minimumInputSize = std::min(minimumInputSize, alternative->m_minimumSize);

maximumCallFrameSize = std::max(maximumCallFrameSize, currentAlternativeCallFrameSize);

hasFixedSize &= alternative->m_hasFixedSize;

if (alternative->m_minimumSize > INT_MAX)

m_pattern.m_containsUnsignedLengthPattern = true;

}

ASSERT(minimumInputSize != UINT_MAX);

ASSERT(maximumCallFrameSize >= initialCallFrameSize);

disjunction->m_hasFixedSize = hasFixedSize;

disjunction->m_minimumSize = minimumInputSize;

disjunction->m_callFrameSize = maximumCallFrameSize;

return maximumCallFrameSize;

}

void setupOffsets()

{

setupDisjunctionOffsets(m_pattern.m_body, 0, 0);

}

// This optimization identifies sets of parentheses that we will never need to backtrack.

// In these cases we do not need to store state from prior iterations.

// We can presently avoid backtracking for:

// * where the parens are at the end of the regular expression (last term in any of the

// alternatives of the main body disjunction).

// * where the parens are non-capturing, and quantified unbounded greedy (*).

// * where the parens do not contain any capturing subpatterns.

void checkForTerminalParentheses()

{

// This check is much too crude; should be just checking whether the candidate

// node contains nested capturing subpatterns, not the whole expression!

if (m_pattern.m_numSubpatterns)

return;

Vector<OwnPtr<PatternAlternative>>& alternatives = m_pattern.m_body->m_alternatives;

for (size_t i = 0; i < alternatives.size(); ++i) {

Vector<PatternTerm>& terms = alternatives[i]->m_terms;

if (terms.size()) {

PatternTerm& term = terms.last();

if (term.type == PatternTerm::TypeParenthesesSubpattern

&& term.quantityType == QuantifierGreedy

&& term.quantityCount == quantifyInfinite

&& !term.capture())

term.parentheses.isTerminal = true;

}

}

}

void optimizeBOL()

{

// Look for expressions containing beginning of line (^) anchoring and unroll them.

// e.g. /^a|^b|c/ becomes /^a|^b|c/ which is executed once followed by /c/ which loops

// This code relies on the parsing code tagging alternatives with m_containsBOL and

// m_startsWithBOL and rolling those up to containing alternatives.

// At this point, this is only valid for non-multiline expressions.

PatternDisjunction* disjunction = m_pattern.m_body;

if (!m_pattern.m_containsBOL || m_pattern.m_multiline)

return;

PatternDisjunction* loopDisjunction = copyDisjunction(disjunction, true);

// Set alternatives in disjunction to "onceThrough"

for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt)

disjunction->m_alternatives[alt]->setOnceThrough();

if (loopDisjunction) {

// Move alternatives from loopDisjunction to disjunction

for (unsigned alt = 0; alt < loopDisjunction->m_alternatives.size(); ++alt)

disjunction->m_alternatives.append(loopDisjunction->m_alternatives[alt].release());

loopDisjunction->m_alternatives.clear();

}

}

bool containsCapturingTerms(PatternAlternative* alternative, size_t firstTermIndex, size_t lastTermIndex)

{

Vector<PatternTerm>& terms = alternative->m_terms;

for (size_t termIndex = firstTermIndex; termIndex <= lastTermIndex; ++termIndex) {

PatternTerm& term = terms[termIndex];

if (term.m_capture)

return true;

if (term.type == PatternTerm::TypeParenthesesSubpattern) {

PatternDisjunction* nestedDisjunction = term.parentheses.disjunction;

for (unsigned alt = 0; alt < nestedDisjunction->m_alternatives.size(); ++alt) {

if (containsCapturingTerms(nestedDisjunction->m_alternatives[alt].get(), 0, nestedDisjunction->m_alternatives[alt]->m_terms.size() - 1))

return true;

}

}

}

return false;

}

// This optimization identifies alternatives in the form of

// [^].*[?]<expression>.*[$] for expressions that don't have any

// capturing terms. The alternative is changed to <expression>

// followed by processing of the dot stars to find and adjust the

// beginning and the end of the match.

void optimizeDotStarWrappedExpressions()

{

Vector<OwnPtr<PatternAlternative>>& alternatives = m_pattern.m_body->m_alternatives;

if (alternatives.size() != 1)

return;

PatternAlternative* alternative = alternatives[0].get();

Vector<PatternTerm>& terms = alternative->m_terms;

if (terms.size() >= 3) {

bool startsWithBOL = false;

bool endsWithEOL = false;

size_t termIndex, firstExpressionTerm, lastExpressionTerm;

termIndex = 0;

if (terms[termIndex].type == PatternTerm::TypeAssertionBOL) {

startsWithBOL = true;

++termIndex;

}

PatternTerm& firstNonAnchorTerm = terms[termIndex];

if ((firstNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (firstNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || !((firstNonAnchorTerm.quantityType == QuantifierGreedy) || (firstNonAnchorTerm.quantityType == QuantifierNonGreedy)))

return;

firstExpressionTerm = termIndex + 1;

termIndex = terms.size() - 1;

if (terms[termIndex].type == PatternTerm::TypeAssertionEOL) {

endsWithEOL = true;

--termIndex;

}

PatternTerm& lastNonAnchorTerm = terms[termIndex];

if ((lastNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (lastNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || (lastNonAnchorTerm.quantityType != QuantifierGreedy))

return;

lastExpressionTerm = termIndex - 1;

if (firstExpressionTerm > lastExpressionTerm)

return;

if (!containsCapturingTerms(alternative, firstExpressionTerm, lastExpressionTerm)) {

for (termIndex = terms.size() - 1; termIndex > lastExpressionTerm; --termIndex)

terms.remove(termIndex);

for (termIndex = firstExpressionTerm; termIndex > 0; --termIndex)

terms.remove(termIndex - 1);

terms.append(PatternTerm(startsWithBOL, endsWithEOL));

m_pattern.m_containsBOL = false;

}

}

}

YarrPattern& m_pattern;

PatternAlternative* m_alternative;

CharacterClassConstructor m_characterClassConstructor;

bool m_invertCharacterClass;

bool m_invertParentheticalAssertion;

: m_ignoreCase(ignoreCase)

, m_multiline(multiline)

, m_containsBackreferences(false)

, m_containsBOL(false)

, m_containsUnsignedLengthPattern(false)

, m_numSubpatterns(0)

, m_maxBackReference(0)

, newlineCached(0)

, digitsCached(0)

, spacesCached(0)

, wordcharCached(0)

, nondigitsCached(0)

, nonspacesCached(0)

, nonwordcharCached(0)

{

*error = compile(pattern);