struct ParenthesesDisjunctionContext;

struct BackTrackInfoPatternCharacter {

uintptr_t matchAmount;

};

struct BackTrackInfoCharacterClass {

uintptr_t matchAmount;

};

struct BackTrackInfoBackReference {

uintptr_t begin; // Not really needed for greedy quantifiers.

uintptr_t matchAmount; // Not really needed for fixed quantifiers.

};

struct BackTrackInfoAlternative {

uintptr_t offset;

};

struct BackTrackInfoParentheticalAssertion {

uintptr_t begin;

};

struct BackTrackInfoParenthesesOnce {

uintptr_t begin;

};

struct BackTrackInfoParenthesesTerminal {

uintptr_t begin;

};

struct BackTrackInfoParentheses {

uintptr_t matchAmount;

ParenthesesDisjunctionContext* lastContext;

};

static inline void appendParenthesesDisjunctionContext(BackTrackInfoParentheses* backTrack, ParenthesesDisjunctionContext* context)

{

context->next = backTrack->lastContext;

backTrack->lastContext = context;

++backTrack->matchAmount;

}

static inline void popParenthesesDisjunctionContext(BackTrackInfoParentheses* backTrack)

{

RELEASE_ASSERT(backTrack->matchAmount);

RELEASE_ASSERT(backTrack->lastContext);

backTrack->lastContext = backTrack->lastContext->next;

--backTrack->matchAmount;

}

struct DisjunctionContext

{

DisjunctionContext()

: term(0)

{

}

void* operator new(size_t, void* where)

{

return where;

}

int term;

unsigned matchBegin;

unsigned matchEnd;

uintptr_t frame[1];

};

DisjunctionContext* allocDisjunctionContext(ByteDisjunction* disjunction)

{

size_t size = sizeof(DisjunctionContext) - sizeof(uintptr_t) + disjunction->m_frameSize * sizeof(uintptr_t);

allocatorPool = allocatorPool->ensureCapacity(size);

RELEASE_ASSERT(allocatorPool);

return new (allocatorPool->alloc(size)) DisjunctionContext();

}

void freeDisjunctionContext(DisjunctionContext* context)

{

allocatorPool = allocatorPool->dealloc(context);

}

struct ParenthesesDisjunctionContext

{

ParenthesesDisjunctionContext(unsigned* output, ByteTerm& term)

: next(0)

{

unsigned firstSubpatternId = term.atom.subpatternId;

unsigned numNestedSubpatterns = term.atom.parenthesesDisjunction->m_numSubpatterns;

for (unsigned i = 0; i < (numNestedSubpatterns << 1); ++i) {

subpatternBackup[i] = output[(firstSubpatternId << 1) + i];

output[(firstSubpatternId << 1) + i] = offsetNoMatch;

}

new (getDisjunctionContext(term)) DisjunctionContext();

}

void* operator new(size_t, void* where)

{

return where;

}

void restoreOutput(unsigned* output, unsigned firstSubpatternId, unsigned numNestedSubpatterns)

{

for (unsigned i = 0; i < (numNestedSubpatterns << 1); ++i)

output[(firstSubpatternId << 1) + i] = subpatternBackup[i];

}

DisjunctionContext* getDisjunctionContext(ByteTerm& term)

{

return reinterpret_cast<DisjunctionContext*>(&(subpatternBackup[term.atom.parenthesesDisjunction->m_numSubpatterns << 1]));

}

ParenthesesDisjunctionContext* next;

unsigned subpatternBackup[1];

};

ParenthesesDisjunctionContext* allocParenthesesDisjunctionContext(ByteDisjunction* disjunction, unsigned* output, ByteTerm& term)

{

size_t size = sizeof(ParenthesesDisjunctionContext) - sizeof(unsigned) + (term.atom.parenthesesDisjunction->m_numSubpatterns << 1) * sizeof(unsigned) + sizeof(DisjunctionContext) - sizeof(uintptr_t) + disjunction->m_frameSize * sizeof(uintptr_t);

allocatorPool = allocatorPool->ensureCapacity(size);

RELEASE_ASSERT(allocatorPool);

return new (allocatorPool->alloc(size)) ParenthesesDisjunctionContext(output, term);

}

void freeParenthesesDisjunctionContext(ParenthesesDisjunctionContext* context)

{

allocatorPool = allocatorPool->dealloc(context);

}

class InputStream {

public:

InputStream(const CharType* input, unsigned start, unsigned length)

: input(input)

, pos(start)

, length(length)

{

}

void next()

{

++pos;

}

void rewind(unsigned amount)

{

ASSERT(pos >= amount);

pos -= amount;

}

int read()

{

ASSERT(pos < length);

if (pos < length)

return input[pos];

return -1;

}

int readPair()

{

ASSERT(pos + 1 < length);

return input[pos] | input[pos + 1] << 16;

}

int readChecked(unsigned negativePositionOffest)

{

RELEASE_ASSERT(pos >= negativePositionOffest);

unsigned p = pos - negativePositionOffest;

ASSERT(p < length);

return input[p];

}

int reread(unsigned from)

{

ASSERT(from < length);

return input[from];

}

int prev()

{

ASSERT(!(pos > length));

if (pos && length)

return input[pos - 1];

return -1;

}

unsigned getPos()

{

return pos;

}

void setPos(unsigned p)

{

pos = p;

}

bool atStart()

{

return pos == 0;

}

bool atEnd()

{

return pos == length;

}

unsigned end()

{

return length;

}

bool checkInput(unsigned count)

{

if (((pos + count) <= length) && ((pos + count) >= pos)) {

pos += count;

return true;

}

return false;

}

void uncheckInput(unsigned count)

{

RELEASE_ASSERT(pos >= count);

pos -= count;

}

bool atStart(unsigned negativePositionOffest)

{

return pos == negativePositionOffest;

}

bool atEnd(unsigned negativePositionOffest)

{

RELEASE_ASSERT(pos >= negativePositionOffest);

return (pos - negativePositionOffest) == length;

}

bool isAvailableInput(unsigned offset)

{

return (((pos + offset) <= length) && ((pos + offset) >= pos));

}

private:

const CharType* input;

unsigned pos;

unsigned length;

};

bool testCharacterClass(CharacterClass* characterClass, int ch)

{

if (ch & 0xFF80) {

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

if (ch == characterClass->m_matchesUnicode[i])

return true;

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

if ((ch >= characterClass->m_rangesUnicode[i].begin) && (ch <= characterClass->m_rangesUnicode[i].end))

return true;

} else {

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

if (ch == characterClass->m_matches[i])

return true;

for (unsigned i = 0; i < characterClass->m_ranges.size(); ++i)

if ((ch >= characterClass->m_ranges[i].begin) && (ch <= characterClass->m_ranges[i].end))

return true;

}

return false;

}

bool checkCharacter(int testChar, unsigned negativeInputOffset)

{

return testChar == input.readChecked(negativeInputOffset);

}

bool checkCasedCharacter(int loChar, int hiChar, unsigned negativeInputOffset)

{

int ch = input.readChecked(negativeInputOffset);

return (loChar == ch) || (hiChar == ch);

}

bool checkCharacterClass(CharacterClass* characterClass, bool invert, unsigned negativeInputOffset)

{

bool match = testCharacterClass(characterClass, input.readChecked(negativeInputOffset));

return invert ? !match : match;

}

bool tryConsumeBackReference(int matchBegin, int matchEnd, unsigned negativeInputOffset)

{

unsigned matchSize = (unsigned)(matchEnd - matchBegin);

if (!input.checkInput(matchSize))

return false;

if (pattern->m_ignoreCase) {

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

int oldCh = input.reread(matchBegin + i);

int ch = input.readChecked(negativeInputOffset + matchSize - i);

if (oldCh == ch)

continue;

// The definition for canonicalize (see ES 5.1, 15.10.2.8) means that

// unicode values are never allowed to match against ascii ones.

if (isASCII(oldCh) || isASCII(ch)) {

if (toASCIIUpper(oldCh) == toASCIIUpper(ch))

continue;

} else if (areCanonicallyEquivalent(oldCh, ch))

continue;

input.uncheckInput(matchSize);

return false;

}

} else {

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

if (!checkCharacter(input.reread(matchBegin + i), negativeInputOffset + matchSize - i)) {

input.uncheckInput(matchSize);

return false;

}

}

}

return true;

}

bool matchAssertionBOL(ByteTerm& term)

{

return (input.atStart(term.inputPosition)) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.readChecked(term.inputPosition + 1)));

}

bool matchAssertionEOL(ByteTerm& term)

{

if (term.inputPosition)

return (input.atEnd(term.inputPosition)) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.readChecked(term.inputPosition)));

return (input.atEnd()) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.read()));

}

bool matchAssertionWordBoundary(ByteTerm& term)

{

bool prevIsWordchar = !input.atStart(term.inputPosition) && testCharacterClass(pattern->wordcharCharacterClass, input.readChecked(term.inputPosition + 1));

bool readIsWordchar;

if (term.inputPosition)

readIsWordchar = !input.atEnd(term.inputPosition) && testCharacterClass(pattern->wordcharCharacterClass, input.readChecked(term.inputPosition));

else

readIsWordchar = !input.atEnd() && testCharacterClass(pattern->wordcharCharacterClass, input.read());

bool wordBoundary = prevIsWordchar != readIsWordchar;

return term.invert() ? !wordBoundary : wordBoundary;

}

bool backtrackPatternCharacter(ByteTerm& term, DisjunctionContext* context)

{

BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);

switch (term.atom.quantityType) {

case QuantifierFixedCount:

break;

case QuantifierGreedy:

if (backTrack->matchAmount) {

--backTrack->matchAmount;

input.uncheckInput(1);

return true;

}

break;

case QuantifierNonGreedy:

if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {

++backTrack->matchAmount;

if (checkCharacter(term.atom.patternCharacter, term.inputPosition + 1))

return true;

}

input.uncheckInput(backTrack->matchAmount);

break;

}

return false;

}

bool backtrackPatternCasedCharacter(ByteTerm& term, DisjunctionContext* context)

{

BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);

switch (term.atom.quantityType) {

case QuantifierFixedCount:

break;

case QuantifierGreedy:

if (backTrack->matchAmount) {

--backTrack->matchAmount;

input.uncheckInput(1);

return true;

}

break;

case QuantifierNonGreedy:

if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {

++backTrack->matchAmount;

if (checkCasedCharacter(term.atom.casedCharacter.lo, term.atom.casedCharacter.hi, term.inputPosition + 1))

return true;

}

input.uncheckInput(backTrack->matchAmount);

break;

}

return false;

}

bool matchCharacterClass(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeCharacterClass);

BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);

switch (term.atom.quantityType) {

case QuantifierFixedCount: {

for (unsigned matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {

if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition - matchAmount))

return false;

}

return true;

}

case QuantifierGreedy: {

unsigned matchAmount = 0;

while ((matchAmount < term.atom.quantityCount) && input.checkInput(1)) {

if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition + 1)) {

input.uncheckInput(1);

break;

}

++matchAmount;

}

backTrack->matchAmount = matchAmount;

return true;

}

case QuantifierNonGreedy:

backTrack->matchAmount = 0;

return true;

}

RELEASE_ASSERT_NOT_REACHED();

return false;

}

bool backtrackCharacterClass(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeCharacterClass);

BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);

switch (term.atom.quantityType) {

case QuantifierFixedCount:

break;

case QuantifierGreedy:

if (backTrack->matchAmount) {

--backTrack->matchAmount;

input.uncheckInput(1);

return true;

}

break;

case QuantifierNonGreedy:

if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {

++backTrack->matchAmount;

if (checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition + 1))

return true;

}

input.uncheckInput(backTrack->matchAmount);

break;

}

return false;

}

bool matchBackReference(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeBackReference);

BackTrackInfoBackReference* backTrack = reinterpret_cast<BackTrackInfoBackReference*>(context->frame + term.frameLocation);

unsigned matchBegin = output[(term.atom.subpatternId << 1)];

unsigned matchEnd = output[(term.atom.subpatternId << 1) + 1];

// If the end position of the referenced match hasn't set yet then the backreference in the same parentheses where it references to that.

// In this case the result of match is empty string like when it references to a parentheses with zero-width match.

// Eg.: /(a\1)/

if (matchEnd == offsetNoMatch)

return true;

if (matchBegin == offsetNoMatch)

return true;

ASSERT(matchBegin <= matchEnd);

if (matchBegin == matchEnd)

return true;

switch (term.atom.quantityType) {

case QuantifierFixedCount: {

backTrack->begin = input.getPos();

for (unsigned matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {

if (!tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {

input.setPos(backTrack->begin);

return false;

}

}

return true;

}

case QuantifierGreedy: {

unsigned matchAmount = 0;

while ((matchAmount < term.atom.quantityCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition))

++matchAmount;

backTrack->matchAmount = matchAmount;

return true;

}

case QuantifierNonGreedy:

backTrack->begin = input.getPos();

backTrack->matchAmount = 0;

return true;

}

RELEASE_ASSERT_NOT_REACHED();

return false;

}

bool backtrackBackReference(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeBackReference);

BackTrackInfoBackReference* backTrack = reinterpret_cast<BackTrackInfoBackReference*>(context->frame + term.frameLocation);

unsigned matchBegin = output[(term.atom.subpatternId << 1)];

unsigned matchEnd = output[(term.atom.subpatternId << 1) + 1];

if (matchBegin == offsetNoMatch)

return false;

ASSERT(matchBegin <= matchEnd);

if (matchBegin == matchEnd)

return false;

switch (term.atom.quantityType) {

case QuantifierFixedCount:

// for quantityCount == 1, could rewind.

input.setPos(backTrack->begin);

break;

case QuantifierGreedy:

if (backTrack->matchAmount) {

--backTrack->matchAmount;

input.rewind(matchEnd - matchBegin);

return true;

}

break;

case QuantifierNonGreedy:

if ((backTrack->matchAmount < term.atom.quantityCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {

++backTrack->matchAmount;

return true;

}

input.setPos(backTrack->begin);

break;

}

return false;

}

void recordParenthesesMatch(ByteTerm& term, ParenthesesDisjunctionContext* context)

{

if (term.capture()) {

unsigned subpatternId = term.atom.subpatternId;

output[(subpatternId << 1)] = context->getDisjunctionContext(term)->matchBegin + term.inputPosition;

output[(subpatternId << 1) + 1] = context->getDisjunctionContext(term)->matchEnd + term.inputPosition;

}

}

void resetMatches(ByteTerm& term, ParenthesesDisjunctionContext* context)

{

unsigned firstSubpatternId = term.atom.subpatternId;

unsigned count = term.atom.parenthesesDisjunction->m_numSubpatterns;

context->restoreOutput(output, firstSubpatternId, count);

}

JSRegExpResult parenthesesDoBacktrack(ByteTerm& term, BackTrackInfoParentheses* backTrack)

{

while (backTrack->matchAmount) {

ParenthesesDisjunctionContext* context = backTrack->lastContext;

JSRegExpResult result = matchDisjunction(term.atom.parenthesesDisjunction, context->getDisjunctionContext(term), true);

if (result == JSRegExpMatch)

return JSRegExpMatch;

resetMatches(term, context);

popParenthesesDisjunctionContext(backTrack);

freeParenthesesDisjunctionContext(context);

if (result != JSRegExpNoMatch)

return result;

}

return JSRegExpNoMatch;

}

bool matchParenthesesOnceBegin(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceBegin);

ASSERT(term.atom.quantityCount == 1);

BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);

switch (term.atom.quantityType) {

case QuantifierGreedy: {

// set this speculatively; if we get to the parens end this will be true.

backTrack->begin = input.getPos();

break;

}

case QuantifierNonGreedy: {

backTrack->begin = notFound;

context->term += term.atom.parenthesesWidth;

return true;

}

case QuantifierFixedCount:

break;

}

if (term.capture()) {

unsigned subpatternId = term.atom.subpatternId;

output[(subpatternId << 1)] = input.getPos() - term.inputPosition;

}

return true;

}

bool matchParenthesesOnceEnd(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceEnd);

ASSERT(term.atom.quantityCount == 1);

if (term.capture()) {

unsigned subpatternId = term.atom.subpatternId;

output[(subpatternId << 1) + 1] = input.getPos() + term.inputPosition;

}

if (term.atom.quantityType == QuantifierFixedCount)

return true;

BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);

return backTrack->begin != input.getPos();

}

bool backtrackParenthesesOnceBegin(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceBegin);

ASSERT(term.atom.quantityCount == 1);

BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);

if (term.capture()) {

unsigned subpatternId = term.atom.subpatternId;

output[(subpatternId << 1)] = offsetNoMatch;

output[(subpatternId << 1) + 1] = offsetNoMatch;

}

switch (term.atom.quantityType) {

case QuantifierGreedy:

// if we backtrack to this point, there is another chance - try matching nothing.

ASSERT(backTrack->begin != notFound);

backTrack->begin = notFound;

context->term += term.atom.parenthesesWidth;

return true;

case QuantifierNonGreedy:

ASSERT(backTrack->begin != notFound);

case QuantifierFixedCount:

break;

}

return false;

}

bool backtrackParenthesesOnceEnd(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceEnd);

ASSERT(term.atom.quantityCount == 1);

BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);

switch (term.atom.quantityType) {

case QuantifierGreedy:

if (backTrack->begin == notFound) {

context->term -= term.atom.parenthesesWidth;

return false;

}

case QuantifierNonGreedy:

if (backTrack->begin == notFound) {

backTrack->begin = input.getPos();

if (term.capture()) {

// Technically this access to inputPosition should be accessing the begin term's

// inputPosition, but for repeats other than fixed these values should be

// the same anyway! (We don't pre-check for greedy or non-greedy matches.)

ASSERT((&term - term.atom.parenthesesWidth)->type == ByteTerm::TypeParenthesesSubpatternOnceBegin);

ASSERT((&term - term.atom.parenthesesWidth)->inputPosition == term.inputPosition);

unsigned subpatternId = term.atom.subpatternId;

output[subpatternId << 1] = input.getPos() + term.inputPosition;

}

context->term -= term.atom.parenthesesWidth;

return true;

}

case QuantifierFixedCount:

break;

}

return false;

}

bool matchParenthesesTerminalBegin(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternTerminalBegin);

ASSERT(term.atom.quantityType == QuantifierGreedy);

ASSERT(term.atom.quantityCount == quantifyInfinite);

ASSERT(!term.capture());

BackTrackInfoParenthesesTerminal* backTrack = reinterpret_cast<BackTrackInfoParenthesesTerminal*>(context->frame + term.frameLocation);

backTrack->begin = input.getPos();

return true;

}

bool matchParenthesesTerminalEnd(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternTerminalEnd);

BackTrackInfoParenthesesTerminal* backTrack = reinterpret_cast<BackTrackInfoParenthesesTerminal*>(context->frame + term.frameLocation);

// Empty match is a failed match.

if (backTrack->begin == input.getPos())

return false;

// Successful match! Okay, what's next? - loop around and try to match moar!

context->term -= (term.atom.parenthesesWidth + 1);

return true;

}

bool backtrackParenthesesTerminalBegin(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternTerminalBegin);

ASSERT(term.atom.quantityType == QuantifierGreedy);

ASSERT(term.atom.quantityCount == quantifyInfinite);

ASSERT(!term.capture());

// If we backtrack to this point, we have failed to match this iteration of the parens.

// Since this is greedy / zero minimum a failed is also accepted as a match!

context->term += term.atom.parenthesesWidth;

return true;

}

bool backtrackParenthesesTerminalEnd(ByteTerm&, DisjunctionContext*)

{

// 'Terminal' parentheses are at the end of the regex, and as such a match past end

// should always be returned as a successful match - we should never backtrack to here.

RELEASE_ASSERT_NOT_REACHED();

return false;

}

bool matchParentheticalAssertionBegin(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParentheticalAssertionBegin);

ASSERT(term.atom.quantityCount == 1);

BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);

backTrack->begin = input.getPos();

return true;

}

bool matchParentheticalAssertionEnd(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParentheticalAssertionEnd);

ASSERT(term.atom.quantityCount == 1);

BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);

input.setPos(backTrack->begin);

// We've reached the end of the parens; if they are inverted, this is failure.

if (term.invert()) {

context->term -= term.atom.parenthesesWidth;

return false;

}

return true;

}

bool backtrackParentheticalAssertionBegin(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParentheticalAssertionBegin);

ASSERT(term.atom.quantityCount == 1);

// We've failed to match parens; if they are inverted, this is win!

if (term.invert()) {

context->term += term.atom.parenthesesWidth;

return true;

}

return false;

}

bool backtrackParentheticalAssertionEnd(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParentheticalAssertionEnd);

ASSERT(term.atom.quantityCount == 1);

BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);

input.setPos(backTrack->begin);

context->term -= term.atom.parenthesesWidth;

return false;

}

JSRegExpResult matchParentheses(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpattern);

BackTrackInfoParentheses* backTrack = reinterpret_cast<BackTrackInfoParentheses*>(context->frame + term.frameLocation);

ByteDisjunction* disjunctionBody = term.atom.parenthesesDisjunction;

backTrack->matchAmount = 0;

backTrack->lastContext = 0;

switch (term.atom.quantityType) {

case QuantifierFixedCount: {

// While we haven't yet reached our fixed limit,

while (backTrack->matchAmount < term.atom.quantityCount) {

// Try to do a match, and it it succeeds, add it to the list.

ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);

JSRegExpResult result = matchDisjunction(disjunctionBody, context->getDisjunctionContext(term));

if (result == JSRegExpMatch)

appendParenthesesDisjunctionContext(backTrack, context);

else {

// The match failed; try to find an alternate point to carry on from.

resetMatches(term, context);

freeParenthesesDisjunctionContext(context);

if (result != JSRegExpNoMatch)

return result;

JSRegExpResult backtrackResult = parenthesesDoBacktrack(term, backTrack);

if (backtrackResult != JSRegExpMatch)

return backtrackResult;

}

}

ASSERT(backTrack->matchAmount == term.atom.quantityCount);

ParenthesesDisjunctionContext* context = backTrack->lastContext;

recordParenthesesMatch(term, context);

return JSRegExpMatch;

}

case QuantifierGreedy: {

while (backTrack->matchAmount < term.atom.quantityCount) {

ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);

JSRegExpResult result = matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term));

if (result == JSRegExpMatch)

appendParenthesesDisjunctionContext(backTrack, context);

else {

resetMatches(term, context);

freeParenthesesDisjunctionContext(context);

if (result != JSRegExpNoMatch)

return result;

break;

}

}

if (backTrack->matchAmount) {

ParenthesesDisjunctionContext* context = backTrack->lastContext;

recordParenthesesMatch(term, context);

}

return JSRegExpMatch;

}

case QuantifierNonGreedy:

return JSRegExpMatch;

}

RELEASE_ASSERT_NOT_REACHED();

return JSRegExpErrorNoMatch;

}

// Rules for backtracking differ depending on whether this is greedy or non-greedy.

//

// Greedy matches never should try just adding more - you should already have done

// the 'more' cases. Always backtrack, at least a leetle bit. However cases where

// you backtrack an item off the list needs checking, since we'll never have matched

// the one less case. Tracking forwards, still add as much as possible.

//

// Non-greedy, we've already done the one less case, so don't match on popping.

// We haven't done the one more case, so always try to add that.

//

JSRegExpResult backtrackParentheses(ByteTerm& term, DisjunctionContext* context)

{

ASSERT(term.type == ByteTerm::TypeParenthesesSubpattern);

BackTrackInfoParentheses* backTrack = reinterpret_cast<BackTrackInfoParentheses*>(context->frame + term.frameLocation);

ByteDisjunction* disjunctionBody = term.atom.parenthesesDisjunction;

switch (term.atom.quantityType) {

case QuantifierFixedCount: {

ASSERT(backTrack->matchAmount == term.atom.quantityCount);

ParenthesesDisjunctionContext* context = 0;

JSRegExpResult result = parenthesesDoBacktrack(term, backTrack);

if (result != JSRegExpMatch)

return result;

// While we haven't yet reached our fixed limit,

while (backTrack->matchAmount < term.atom.quantityCount) {

// Try to do a match, and it it succeeds, add it to the list.

context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);

result = matchDisjunction(disjunctionBody, context->getDisjunctionContext(term));

if (result == JSRegExpMatch)

appendParenthesesDisjunctionContext(backTrack, context);

else {

// The match failed; try to find an alternate point to carry on from.

resetMatches(term, context);

freeParenthesesDisjunctionContext(context);

if (result != JSRegExpNoMatch)

return result;

JSRegExpResult backtrackResult = parenthesesDoBacktrack(term, backTrack);

if (backtrackResult != JSRegExpMatch)

return backtrackResult;

}

}

ASSERT(backTrack->matchAmount == term.atom.quantityCount);

context = backTrack->lastContext;

recordParenthesesMatch(term, context);

return JSRegExpMatch;

}

case QuantifierGreedy: {

if (!backTrack->matchAmount)

return JSRegExpNoMatch;

ParenthesesDisjunctionContext* context = backTrack->lastContext;

JSRegExpResult result = matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term), true);

if (result == JSRegExpMatch) {

while (backTrack->matchAmount < term.atom.quantityCount) {

ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);

JSRegExpResult parenthesesResult = matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term));

if (parenthesesResult == JSRegExpMatch)

appendParenthesesDisjunctionContext(backTrack, context);

else {

resetMatches(term, context);

freeParenthesesDisjunctionContext(context);

if (parenthesesResult != JSRegExpNoMatch)

return parenthesesResult;

break;

}

}