/*

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

* Copyright (C) 2010 Peter Varga ([email protected]), University of Szeged

*

* Redistribution and use in source and binary forms, with or without

* modification, are permitted provided that the following conditions

* are met:

* 1. Redistributions of source code must retain the above copyright

* notice, this list of conditions and the following disclaimer.

* 2. Redistributions in binary form must reproduce the above copyright

* notice, this list of conditions and the following disclaimer in the

* documentation and/or other materials provided with the distribution.

*

* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY

* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR

* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*/

#include "config.h"

#include "YarrInterpreter.h"

#include "UString.h"

#include "Yarr.h"

#include <wtf/BumpPointerAllocator.h>

#include <wtf/DataLog.h>

#include <wtf/text/CString.h>

#ifndef NDEBUG

#include <stdio.h>

#endif

using namespace WTF;

namespace JSC { namespace Yarr {

class Interpreter {

public:

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)

{

ASSERT(backTrack->matchAmount);

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);

if (!allocatorPool)

CRASH();

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

}

void freeDisjunctionContext(DisjunctionContext* context)

{

allocatorPool = allocatorPool->dealloc(context);

}

struct ParenthesesDisjunctionContext

{

ParenthesesDisjunctionContext(int* 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] = -1;

}

new (getDisjunctionContext(term)) DisjunctionContext();

}

void* operator new(size_t, void* where)

{

return where;

}

void restoreOutput(int* 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;

int subpatternBackup[1];

};

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

{

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

allocatorPool = allocatorPool->ensureCapacity(size);

if (!allocatorPool)

CRASH();

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

}

void freeParenthesesDisjunctionContext(ParenthesesDisjunctionContext* context)

{

allocatorPool = allocatorPool->dealloc(context);

}

// This class is a placeholder for future character iterator, current

// proposed name StringConstCharacterIterator.

class CharAccess {

public:

CharAccess(const UString& s)

{

if (s.is8Bit()) {

m_charSize = Char8;

m_ptr.ptr8 = s.characters8();

} else {

m_charSize = Char16;

m_ptr.ptr16 = s.characters16();

}

}

CharAccess(const LChar* ptr)

: m_charSize(Char8)

{

m_ptr.ptr8 = ptr;

}

CharAccess(const UChar* ptr)

: m_charSize(Char16)

{

m_ptr.ptr16 = ptr;

}

~CharAccess()

{

}

inline UChar operator[](unsigned index)

{

if (m_charSize == Char8)

return m_ptr.ptr8[index];

return m_ptr.ptr16[index];

}

private:

union {

const LChar* ptr8;

const UChar* ptr16;

} m_ptr;

YarrCharSize m_charSize;

};

class InputStream {

public:

InputStream(const UString& 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(int position)

{

ASSERT(position < 0);

ASSERT(static_cast<unsigned>(-position) <= pos);

unsigned p = pos + position;

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(int count)

{

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

pos += count;

return true;

}

return false;

}

void uncheckInput(int count)

{

pos -= count;

}

bool atStart(int position)

{

return (pos + position) == 0;

}

bool atEnd(int position)

{

return (pos + position) == length;

}

bool isNotAvailableInput(int position)

{

return (pos + position) > length;

}

private:

CharAccess 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, int inputPosition)

{

return testChar == input.readChecked(inputPosition);

}

bool checkCasedCharacter(int loChar, int hiChar, int inputPosition)

{

int ch = input.readChecked(inputPosition);

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

}

bool checkCharacterClass(CharacterClass* characterClass, bool invert, int inputPosition)

{

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

return invert ? !match : match;

}

bool tryConsumeBackReference(int matchBegin, int matchEnd, int inputOffset)

{

int matchSize = matchEnd - matchBegin;

if (!input.checkInput(matchSize))

return false;

if (pattern->m_ignoreCase) {

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

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

int lo = Unicode::toLower(ch);

int hi = Unicode::toUpper(ch);

if ((lo != hi) ? (!checkCasedCharacter(lo, hi, inputOffset - matchSize + i)) : (!checkCharacter(ch, inputOffset - matchSize + i))) {

input.uncheckInput(matchSize);

return false;

}

}

} else {

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

if (!checkCharacter(input.reread(matchBegin + i), inputOffset - 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;

}

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);

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

int 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 == -1)

return true;

if (matchBegin == -1)

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;

}

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);

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

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

if (matchBegin == -1)

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)] = -1;

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

}

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.

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;

}

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)