+++ /dev/null
-/*
- * Copyright (C) 2009 Apple Inc. All rights reserved.
- *
- * 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 "RegexInterpreter.h"
-
-#include "RegexCompiler.h"
-#include "RegexPattern.h"
-
-#ifndef NDEBUG
-#include <stdio.h>
-#endif
-
-#if ENABLE(YARR)
-
-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 inParentheses;
- };
- struct BackTrackInfoParentheses {
- uintptr_t matchAmount;
- ParenthesesDisjunctionContext* lastContext;
- uintptr_t prevBegin;
- uintptr_t prevEnd;
- };
-
- 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)
- {
- return new(malloc(sizeof(DisjunctionContext) + (disjunction->m_frameSize - 1) * sizeof(uintptr_t))) DisjunctionContext();
- }
-
- void freeDisjunctionContext(DisjunctionContext* context)
- {
- free(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)
- {
- return new(malloc(sizeof(ParenthesesDisjunctionContext) + (((term.atom.parenthesesDisjunction->m_numSubpatterns << 1) - 1) * sizeof(int)) + sizeof(DisjunctionContext) + (disjunction->m_frameSize - 1) * sizeof(uintptr_t))) ParenthesesDisjunctionContext(output, term);
- }
-
- void freeParenthesesDisjunctionContext(ParenthesesDisjunctionContext* context)
- {
- free(context);
- }
-
- class InputStream {
- public:
- InputStream(const UChar* 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 readChecked(int position)
- {
- ASSERT(position < 0);
- ASSERT((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;
- }
-
- bool checkInput(int count)
- {
- if ((pos + count) <= length) {
- pos += count;
- return true;
- } else
- return false;
- }
-
- void uncheckInput(int count)
- {
- pos -= count;
- }
-
- bool atStart(int position)
- {
- return (pos + position) == 0;
- }
-
- bool atEnd(int position)
- {
- return (pos + position) == length;
- }
-
- private:
- const UChar* 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;
-
- 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)));
- else
- 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];
- ASSERT((matchBegin == -1) == (matchEnd == -1));
- 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];
- ASSERT((matchBegin == -1) == (matchEnd == -1));
- 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;
- } else
- 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);
- }
- void resetAssertionMatches(ByteTerm& term)
- {
- unsigned firstSubpatternId = term.atom.subpatternId;
- unsigned count = term.atom.parenthesesDisjunction->m_numSubpatterns;
- for (unsigned i = 0; i < (count << 1); ++i)
- output[(firstSubpatternId << 1) + i] = -1;
- }
- bool parenthesesDoBacktrack(ByteTerm& term, BackTrackInfoParentheses* backTrack)
- {
- while (backTrack->matchAmount) {
- ParenthesesDisjunctionContext* context = backTrack->lastContext;
-
- if (matchDisjunction(term.atom.parenthesesDisjunction, context->getDisjunctionContext(term), true))
- return true;
-
- resetMatches(term, context);
- popParenthesesDisjunctionContext(backTrack);
- freeParenthesesDisjunctionContext(context);
- }
-
- return false;
- }
-
- 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->inParentheses = 1;
- break;
- }
- case QuantifierNonGreedy: {
- backTrack->inParentheses = 0;
- 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*)
- {
- 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;
- }
- return true;
- }
-
- 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->inParentheses);
- backTrack->inParentheses = 0;
- context->term += term.atom.parenthesesWidth;
- return true;
- case QuantifierNonGreedy:
- ASSERT(backTrack->inParentheses);
- 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->inParentheses) {
- context->term -= term.atom.parenthesesWidth;
- return false;
- }
- case QuantifierNonGreedy:
- if (!backTrack->inParentheses) {
- // now try to match the parens; set this speculatively.
- backTrack->inParentheses = 1;
- if (term.capture()) {
- unsigned subpatternId = term.atom.subpatternId;
- output[(subpatternId << 1) + 1] = input.getPos() + term.inputPosition;
- }
- context->term -= term.atom.parenthesesWidth;
- return true;
- }
- case QuantifierFixedCount:
- break;
- }
-
- 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;
- }
-
- bool matchParentheses(ByteTerm& term, DisjunctionContext* context)
- {
- ASSERT(term.type == ByteTerm::TypeParenthesesSubpattern);
-
- BackTrackInfoParentheses* backTrack = reinterpret_cast<BackTrackInfoParentheses*>(context->frame + term.frameLocation);
-
- unsigned subpatternId = term.atom.subpatternId;
- ByteDisjunction* disjunctionBody = term.atom.parenthesesDisjunction;
-
- backTrack->prevBegin = output[(subpatternId << 1)];
- backTrack->prevEnd = output[(subpatternId << 1) + 1];
-
- 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);
- if (matchDisjunction(disjunctionBody, context->getDisjunctionContext(term)))
- appendParenthesesDisjunctionContext(backTrack, context);
- else {
- // The match failed; try to find an alternate point to carry on from.
- resetMatches(term, context);
- freeParenthesesDisjunctionContext(context);
- if (!parenthesesDoBacktrack(term, backTrack))
- return false;
- }
- }
-
- ASSERT(backTrack->matchAmount == term.atom.quantityCount);
- ParenthesesDisjunctionContext* context = backTrack->lastContext;
- recordParenthesesMatch(term, context);
- return true;
- }
-
- case QuantifierGreedy: {
- while (backTrack->matchAmount < term.atom.quantityCount) {
- ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
- if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term)))
- appendParenthesesDisjunctionContext(backTrack, context);
- else {
- resetMatches(term, context);
- freeParenthesesDisjunctionContext(context);
- break;
- }
- }
-
- if (backTrack->matchAmount) {
- ParenthesesDisjunctionContext* context = backTrack->lastContext;
- recordParenthesesMatch(term, context);
- }
- return true;
- }
-
- case QuantifierNonGreedy:
- return true;
- }
-
- ASSERT_NOT_REACHED();
- return false;
- }
-
- // 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.
- //
- bool backtrackParentheses(ByteTerm& term, DisjunctionContext* context)
- {
- ASSERT(term.type == ByteTerm::TypeParenthesesSubpattern);
-
- BackTrackInfoParentheses* backTrack = reinterpret_cast<BackTrackInfoParentheses*>(context->frame + term.frameLocation);
-
- if (term.capture()) {
- unsigned subpatternId = term.atom.subpatternId;
- output[(subpatternId << 1)] = backTrack->prevBegin;
- output[(subpatternId << 1) + 1] = backTrack->prevEnd;
- }
-
- ByteDisjunction* disjunctionBody = term.atom.parenthesesDisjunction;
-
- switch (term.atom.quantityType) {
- case QuantifierFixedCount: {
- ASSERT(backTrack->matchAmount == term.atom.quantityCount);
-
- ParenthesesDisjunctionContext* context = 0;
-
- if (!parenthesesDoBacktrack(term, backTrack))
- return false;
-
- // 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);
- if (matchDisjunction(disjunctionBody, context->getDisjunctionContext(term)))
- appendParenthesesDisjunctionContext(backTrack, context);
- else {
- // The match failed; try to find an alternate point to carry on from.
- resetMatches(term, context);
- freeParenthesesDisjunctionContext(context);
- if (!parenthesesDoBacktrack(term, backTrack))
- return false;
- }
- }
-
- ASSERT(backTrack->matchAmount == term.atom.quantityCount);
- context = backTrack->lastContext;
- recordParenthesesMatch(term, context);
- return true;
- }
-
- case QuantifierGreedy: {
- if (!backTrack->matchAmount)
- return false;
-
- ParenthesesDisjunctionContext* context = backTrack->lastContext;
- if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term), true)) {
- while (backTrack->matchAmount < term.atom.quantityCount) {
- ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
- if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term)))
- appendParenthesesDisjunctionContext(backTrack, context);
- else {
- resetMatches(term, context);
- freeParenthesesDisjunctionContext(context);
- break;
- }
- }
- } else {
- resetMatches(term, context);
- popParenthesesDisjunctionContext(backTrack);
- freeParenthesesDisjunctionContext(context);
- }
-
- if (backTrack->matchAmount) {
- ParenthesesDisjunctionContext* context = backTrack->lastContext;
- recordParenthesesMatch(term, context);
- }
- return true;
- }
-
- case QuantifierNonGreedy: {
- // If we've not reached the limit, try to add one more match.
- if (backTrack->matchAmount < term.atom.quantityCount) {
- ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
- if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term))) {
- appendParenthesesDisjunctionContext(backTrack, context);
- recordParenthesesMatch(term, context);
- return true;
- } else {
- resetMatches(term, context);
- freeParenthesesDisjunctionContext(context);
- }
- }
-
- // Nope - okay backtrack looking for an alternative.
- while (backTrack->matchAmount) {
- ParenthesesDisjunctionContext* context = backTrack->lastContext;
- if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term), true)) {
- // successful backtrack! we're back in the game!
- if (backTrack->matchAmount) {
- context = backTrack->lastContext;
- recordParenthesesMatch(term, context);
- }
- return true;
- }
-
- // pop a match off the stack
- resetMatches(term, context);
- popParenthesesDisjunctionContext(backTrack);
- freeParenthesesDisjunctionContext(context);
- }
-
- return false;
- }
- }
-
- ASSERT_NOT_REACHED();
- return false;
- }
-
-#define MATCH_NEXT() { ++context->term; goto matchAgain; }
-#define BACKTRACK() { --context->term; goto backtrack; }
-#define currentTerm() (disjunction->terms[context->term])
- bool matchDisjunction(ByteDisjunction* disjunction, DisjunctionContext* context, bool btrack = false)
- {
- if (btrack)
- BACKTRACK();
-
- context->matchBegin = input.getPos();
- context->term = 0;
-
- matchAgain:
- ASSERT(context->term < static_cast<int>(disjunction->terms.size()));
-
- switch (currentTerm().type) {
- case ByteTerm::TypeSubpatternBegin:
- MATCH_NEXT();
- case ByteTerm::TypeSubpatternEnd:
- context->matchEnd = input.getPos();
- return true;
-
- case ByteTerm::TypeBodyAlternativeBegin:
- MATCH_NEXT();
- case ByteTerm::TypeBodyAlternativeDisjunction:
- case ByteTerm::TypeBodyAlternativeEnd:
- context->matchEnd = input.getPos();
- return true;
-
- case ByteTerm::TypeAlternativeBegin:
- MATCH_NEXT();
- case ByteTerm::TypeAlternativeDisjunction:
- case ByteTerm::TypeAlternativeEnd: {
- int offset = currentTerm().alternative.end;
- BackTrackInfoAlternative* backTrack = reinterpret_cast<BackTrackInfoAlternative*>(context->frame + currentTerm().frameLocation);
- backTrack->offset = offset;
- context->term += offset;
- MATCH_NEXT();
- }
-
- case ByteTerm::TypeAssertionBOL:
- if (matchAssertionBOL(currentTerm()))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeAssertionEOL:
- if (matchAssertionEOL(currentTerm()))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeAssertionWordBoundary:
- if (matchAssertionWordBoundary(currentTerm()))
- MATCH_NEXT();
- BACKTRACK();
-
- case ByteTerm::TypePatternCharacterOnce:
- case ByteTerm::TypePatternCharacterFixed: {
- for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityCount; ++matchAmount) {
- if (!checkCharacter(currentTerm().atom.patternCharacter, currentTerm().inputPosition + matchAmount))
- BACKTRACK();
- }
- MATCH_NEXT();
- }
- case ByteTerm::TypePatternCharacterGreedy: {
- BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + currentTerm().frameLocation);
- unsigned matchAmount = 0;
- while ((matchAmount < currentTerm().atom.quantityCount) && input.checkInput(1)) {
- if (!checkCharacter(currentTerm().atom.patternCharacter, currentTerm().inputPosition - 1)) {
- input.uncheckInput(1);
- break;
- }
- ++matchAmount;
- }
- backTrack->matchAmount = matchAmount;
-
- MATCH_NEXT();
- }
- case ByteTerm::TypePatternCharacterNonGreedy: {
- BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + currentTerm().frameLocation);
- backTrack->matchAmount = 0;
- MATCH_NEXT();
- }
-
- case ByteTerm::TypePatternCasedCharacterOnce:
- case ByteTerm::TypePatternCasedCharacterFixed: {
- for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityCount; ++matchAmount) {
- if (!checkCasedCharacter(currentTerm().atom.casedCharacter.lo, currentTerm().atom.casedCharacter.hi, currentTerm().inputPosition + matchAmount))
- BACKTRACK();
- }
- MATCH_NEXT();
- }
- case ByteTerm::TypePatternCasedCharacterGreedy: {
- BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + currentTerm().frameLocation);
- unsigned matchAmount = 0;
- while ((matchAmount < currentTerm().atom.quantityCount) && input.checkInput(1)) {
- if (!checkCasedCharacter(currentTerm().atom.casedCharacter.lo, currentTerm().atom.casedCharacter.hi, currentTerm().inputPosition - 1)) {
- input.uncheckInput(1);
- break;
- }
- ++matchAmount;
- }
- backTrack->matchAmount = matchAmount;
-
- MATCH_NEXT();
- }
- case ByteTerm::TypePatternCasedCharacterNonGreedy: {
- BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + currentTerm().frameLocation);
- backTrack->matchAmount = 0;
- MATCH_NEXT();
- }
-
- case ByteTerm::TypeCharacterClass:
- if (matchCharacterClass(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeBackReference:
- if (matchBackReference(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParenthesesSubpattern:
- if (matchParentheses(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParenthesesSubpatternOnceBegin:
- if (matchParenthesesOnceBegin(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParenthesesSubpatternOnceEnd:
- if (matchParenthesesOnceEnd(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParentheticalAssertionBegin:
- if (matchParentheticalAssertionBegin(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParentheticalAssertionEnd:
- if (matchParentheticalAssertionEnd(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
-
- case ByteTerm::TypeCheckInput:
- if (input.checkInput(currentTerm().checkInputCount))
- MATCH_NEXT();
- BACKTRACK();
- }
-
- // We should never fall-through to here.
- ASSERT_NOT_REACHED();
-
- backtrack:
- ASSERT(context->term < static_cast<int>(disjunction->terms.size()));
-
- switch (currentTerm().type) {
- case ByteTerm::TypeSubpatternBegin:
- return false;
- case ByteTerm::TypeSubpatternEnd:
- ASSERT_NOT_REACHED();
-
- case ByteTerm::TypeBodyAlternativeBegin:
- case ByteTerm::TypeBodyAlternativeDisjunction: {
- int offset = currentTerm().alternative.next;
- context->term += offset;
- if (offset > 0)
- MATCH_NEXT();
-
- if (input.atEnd())
- return false;
-
- input.next();
- context->matchBegin = input.getPos();
- MATCH_NEXT();
- }
- case ByteTerm::TypeBodyAlternativeEnd:
- ASSERT_NOT_REACHED();
-
- case ByteTerm::TypeAlternativeBegin:
- case ByteTerm::TypeAlternativeDisjunction: {
- int offset = currentTerm().alternative.next;
- context->term += offset;
- if (offset > 0)
- MATCH_NEXT();
- BACKTRACK();
- }
- case ByteTerm::TypeAlternativeEnd: {
- // We should never backtrack back into an alternative of the main body of the regex.
- BackTrackInfoAlternative* backTrack = reinterpret_cast<BackTrackInfoAlternative*>(context->frame + currentTerm().frameLocation);
- unsigned offset = backTrack->offset;
- context->term -= offset;
- BACKTRACK();
- }
-
- case ByteTerm::TypeAssertionBOL:
- case ByteTerm::TypeAssertionEOL:
- case ByteTerm::TypeAssertionWordBoundary:
- BACKTRACK();
-
- case ByteTerm::TypePatternCharacterOnce:
- case ByteTerm::TypePatternCharacterFixed:
- case ByteTerm::TypePatternCharacterGreedy:
- case ByteTerm::TypePatternCharacterNonGreedy:
- if (backtrackPatternCharacter(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypePatternCasedCharacterOnce:
- case ByteTerm::TypePatternCasedCharacterFixed:
- case ByteTerm::TypePatternCasedCharacterGreedy:
- case ByteTerm::TypePatternCasedCharacterNonGreedy:
- if (backtrackPatternCasedCharacter(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeCharacterClass:
- if (backtrackCharacterClass(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeBackReference:
- if (backtrackBackReference(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParenthesesSubpattern:
- if (backtrackParentheses(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParenthesesSubpatternOnceBegin:
- if (backtrackParenthesesOnceBegin(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParenthesesSubpatternOnceEnd:
- if (backtrackParenthesesOnceEnd(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParentheticalAssertionBegin:
- if (backtrackParentheticalAssertionBegin(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
- case ByteTerm::TypeParentheticalAssertionEnd:
- if (backtrackParentheticalAssertionEnd(currentTerm(), context))
- MATCH_NEXT();
- BACKTRACK();
-
- case ByteTerm::TypeCheckInput:
- input.uncheckInput(currentTerm().checkInputCount);
- BACKTRACK();
- }
-
- ASSERT_NOT_REACHED();
- return false;
- }
-
- bool matchNonZeroDisjunction(ByteDisjunction* disjunction, DisjunctionContext* context, bool btrack = false)
- {
- if (matchDisjunction(disjunction, context, btrack)) {
- while (context->matchBegin == context->matchEnd) {
- if (!matchDisjunction(disjunction, context, true))
- return false;
- }
- return true;
- }
-
- return false;
- }
-
- int interpret()
- {
- for (unsigned i = 0; i < ((pattern->m_body->m_numSubpatterns + 1) << 1); ++i)
- output[i] = -1;
-
- DisjunctionContext* context = allocDisjunctionContext(pattern->m_body.get());
-
- if (matchDisjunction(pattern->m_body.get(), context)) {
- output[0] = context->matchBegin;
- output[1] = context->matchEnd;
- }
-
- freeDisjunctionContext(context);
-
- return output[0];
- }
-
- Interpreter(BytecodePattern* pattern, int* output, const UChar* inputChar, unsigned start, unsigned length)
- : pattern(pattern)
- , output(output)
- , input(inputChar, start, length)
- {
- }
-
-private:
- BytecodePattern *pattern;
- int* output;
- InputStream input;
-};
-
-
-
-class ByteCompiler {
- struct ParenthesesStackEntry {
- unsigned beginTerm;
- unsigned savedAlternativeIndex;
- ParenthesesStackEntry(unsigned beginTerm, unsigned savedAlternativeIndex/*, unsigned subpatternId, bool capture = false*/)
- : beginTerm(beginTerm)
- , savedAlternativeIndex(savedAlternativeIndex)
- {
- }
- };
-
-public:
- ByteCompiler(RegexPattern& pattern)
- : m_pattern(pattern)
- {
- m_bodyDisjunction = 0;
- m_currentAlternativeIndex = 0;
- }
-
- BytecodePattern* compile()
- {
- regexBegin(m_pattern.m_numSubpatterns, m_pattern.m_body->m_callFrameSize);
- emitDisjunction(m_pattern.m_body);
- regexEnd();
-
- return new BytecodePattern(m_bodyDisjunction, m_allParenthesesInfo, m_pattern);
- }
-
- void checkInput(unsigned count)
- {
- m_bodyDisjunction->terms.append(ByteTerm::CheckInput(count));
- }
-
- void assertionBOL(int inputPosition)
- {
- m_bodyDisjunction->terms.append(ByteTerm::BOL(inputPosition));
- }
-
- void assertionEOL(int inputPosition)
- {
- m_bodyDisjunction->terms.append(ByteTerm::EOL(inputPosition));
- }
-
- void assertionWordBoundary(bool invert, int inputPosition)
- {
- m_bodyDisjunction->terms.append(ByteTerm::WordBoundary(invert, inputPosition));
- }
-
- void atomPatternCharacter(UChar ch, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
- {
- if (m_pattern.m_ignoreCase) {
- UChar lo = Unicode::toLower(ch);
- UChar hi = Unicode::toUpper(ch);
-
- if (lo != hi) {
- m_bodyDisjunction->terms.append(ByteTerm(lo, hi, inputPosition, frameLocation, quantityCount, quantityType));
- return;
- }
- }
-
- m_bodyDisjunction->terms.append(ByteTerm(ch, inputPosition, frameLocation, quantityCount, quantityType));
- }
-
- void atomCharacterClass(CharacterClass* characterClass, bool invert, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
- {
- m_bodyDisjunction->terms.append(ByteTerm(characterClass, invert, inputPosition));
-
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount;
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType;
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
- }
-
- void atomBackReference(unsigned subpatternId, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
- {
- ASSERT(subpatternId);
-
- m_bodyDisjunction->terms.append(ByteTerm::BackReference(subpatternId, inputPosition));
-
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount;
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType;
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
- }
-
- void atomParenthesesSubpatternBegin(unsigned subpatternId, bool capture, int inputPosition, unsigned frameLocation, unsigned alternativeFrameLocation)
- {
- int beginTerm = m_bodyDisjunction->terms.size();
-
- m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, inputPosition));
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
- m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;
-
- m_parenthesesStack.append(ParenthesesStackEntry(beginTerm, m_currentAlternativeIndex));
- m_currentAlternativeIndex = beginTerm + 1;
- }
-
- void atomParentheticalAssertionBegin(unsigned subpatternId, bool invert, unsigned frameLocation, unsigned alternativeFrameLocation)
- {
- int beginTerm = m_bodyDisjunction->terms.size();
-
- m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParentheticalAssertionBegin, subpatternId, invert, 0));
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
- m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());
- m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;
-
- m_parenthesesStack.append(ParenthesesStackEntry(beginTerm, m_currentAlternativeIndex));
- m_currentAlternativeIndex = beginTerm + 1;
- }
-
- unsigned popParenthesesStack()
- {
- ASSERT(m_parenthesesStack.size());
- int stackEnd = m_parenthesesStack.size() - 1;
- unsigned beginTerm = m_parenthesesStack[stackEnd].beginTerm;
- m_currentAlternativeIndex = m_parenthesesStack[stackEnd].savedAlternativeIndex;
- m_parenthesesStack.shrink(stackEnd);
-
- ASSERT(beginTerm < m_bodyDisjunction->terms.size());
- ASSERT(m_currentAlternativeIndex < m_bodyDisjunction->terms.size());
-
- return beginTerm;
- }
-
-#ifndef NDEBUG
- void dumpDisjunction(ByteDisjunction* disjunction)
- {
- printf("ByteDisjunction(%p):\n\t", disjunction);
- for (unsigned i = 0; i < disjunction->terms.size(); ++i)
- printf("{ %d } ", disjunction->terms[i].type);
- printf("\n");
- }
-#endif
-
- void closeAlternative(int beginTerm)
- {
- int origBeginTerm = beginTerm;
- ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeAlternativeBegin);
- int endIndex = m_bodyDisjunction->terms.size();
-
- unsigned frameLocation = m_bodyDisjunction->terms[beginTerm].frameLocation;
-
- if (!m_bodyDisjunction->terms[beginTerm].alternative.next)
- m_bodyDisjunction->terms.remove(beginTerm);
- else {
- while (m_bodyDisjunction->terms[beginTerm].alternative.next) {
- beginTerm += m_bodyDisjunction->terms[beginTerm].alternative.next;
- ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeAlternativeDisjunction);
- m_bodyDisjunction->terms[beginTerm].alternative.end = endIndex - beginTerm;
- m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;
- }
-
- m_bodyDisjunction->terms[beginTerm].alternative.next = origBeginTerm - beginTerm;
-
- m_bodyDisjunction->terms.append(ByteTerm::AlternativeEnd());
- m_bodyDisjunction->terms[endIndex].frameLocation = frameLocation;
- }
- }
-
- void closeBodyAlternative()
- {
- int beginTerm = 0;
- int origBeginTerm = 0;
- ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeBodyAlternativeBegin);
- int endIndex = m_bodyDisjunction->terms.size();
-
- unsigned frameLocation = m_bodyDisjunction->terms[beginTerm].frameLocation;
-
- while (m_bodyDisjunction->terms[beginTerm].alternative.next) {
- beginTerm += m_bodyDisjunction->terms[beginTerm].alternative.next;
- ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeBodyAlternativeDisjunction);
- m_bodyDisjunction->terms[beginTerm].alternative.end = endIndex - beginTerm;
- m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;
- }
-
- m_bodyDisjunction->terms[beginTerm].alternative.next = origBeginTerm - beginTerm;
-
- m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeEnd());
- m_bodyDisjunction->terms[endIndex].frameLocation = frameLocation;
- }
-
- void atomParenthesesEnd(bool doInline, unsigned lastSubpatternId, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType, unsigned callFrameSize = 0)
- {
- unsigned beginTerm = popParenthesesStack();
- closeAlternative(beginTerm + 1);
- unsigned endTerm = m_bodyDisjunction->terms.size();
-
- bool isAssertion = m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeParentheticalAssertionBegin;
- bool invertOrCapture = m_bodyDisjunction->terms[beginTerm].invertOrCapture;
- unsigned subpatternId = m_bodyDisjunction->terms[beginTerm].atom.subpatternId;
-
- m_bodyDisjunction->terms.append(ByteTerm(isAssertion ? ByteTerm::TypeParentheticalAssertionEnd : ByteTerm::TypeParenthesesSubpatternOnceEnd, subpatternId, invertOrCapture, inputPosition));
- m_bodyDisjunction->terms[beginTerm].atom.parenthesesWidth = endTerm - beginTerm;
- m_bodyDisjunction->terms[endTerm].atom.parenthesesWidth = endTerm - beginTerm;
- m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation;
-
- if (doInline) {
- m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount;
- m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
- m_bodyDisjunction->terms[endTerm].atom.quantityCount = quantityCount;
- m_bodyDisjunction->terms[endTerm].atom.quantityType = quantityType;
- } else {
- ByteTerm& parenthesesBegin = m_bodyDisjunction->terms[beginTerm];
- ASSERT(parenthesesBegin.type == ByteTerm::TypeParenthesesSubpatternOnceBegin);
-
- bool invertOrCapture = parenthesesBegin.invertOrCapture;
- unsigned subpatternId = parenthesesBegin.atom.subpatternId;
-
- unsigned numSubpatterns = lastSubpatternId - subpatternId + 1;
- ByteDisjunction* parenthesesDisjunction = new ByteDisjunction(numSubpatterns, callFrameSize);
-
- parenthesesDisjunction->terms.append(ByteTerm::SubpatternBegin());
- for (unsigned termInParentheses = beginTerm + 1; termInParentheses < endTerm; ++termInParentheses)
- parenthesesDisjunction->terms.append(m_bodyDisjunction->terms[termInParentheses]);
- parenthesesDisjunction->terms.append(ByteTerm::SubpatternEnd());
-
- m_bodyDisjunction->terms.shrink(beginTerm);
-
- m_allParenthesesInfo.append(parenthesesDisjunction);
- m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, invertOrCapture, inputPosition));
-
- m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount;
- m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
- m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;
- }
- }
-
- void regexBegin(unsigned numSubpatterns, unsigned callFrameSize)
- {
- m_bodyDisjunction = new ByteDisjunction(numSubpatterns, callFrameSize);
- m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeBegin());
- m_bodyDisjunction->terms[0].frameLocation = 0;
- m_currentAlternativeIndex = 0;
- }
-
- void regexEnd()
- {
- closeBodyAlternative();
- }
-
- void alternativeBodyDisjunction()
- {
- int newAlternativeIndex = m_bodyDisjunction->terms.size();
- m_bodyDisjunction->terms[m_currentAlternativeIndex].alternative.next = newAlternativeIndex - m_currentAlternativeIndex;
- m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeDisjunction());
-
- m_currentAlternativeIndex = newAlternativeIndex;
- }
-
- void alternativeDisjunction()
- {
- int newAlternativeIndex = m_bodyDisjunction->terms.size();
- m_bodyDisjunction->terms[m_currentAlternativeIndex].alternative.next = newAlternativeIndex - m_currentAlternativeIndex;
- m_bodyDisjunction->terms.append(ByteTerm::AlternativeDisjunction());
-
- m_currentAlternativeIndex = newAlternativeIndex;
- }
-
- void emitDisjunction(PatternDisjunction* disjunction, unsigned inputCountAlreadyChecked = 0, unsigned parenthesesInputCountAlreadyChecked = 0)
- {
- for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
- unsigned currentCountAlreadyChecked = inputCountAlreadyChecked;
-
- if (alt) {
- if (disjunction == m_pattern.m_body)
- alternativeBodyDisjunction();
- else
- alternativeDisjunction();
- }
-
- PatternAlternative* alternative = disjunction->m_alternatives[alt];
- unsigned minimumSize = alternative->m_minimumSize;
-
- ASSERT(minimumSize >= parenthesesInputCountAlreadyChecked);
- unsigned countToCheck = minimumSize - parenthesesInputCountAlreadyChecked;
- if (countToCheck)
- checkInput(countToCheck);
- currentCountAlreadyChecked += countToCheck;
-
- for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
- PatternTerm& term = alternative->m_terms[i];
-
- switch (term.type) {
- case PatternTerm::TypeAssertionBOL:
- assertionBOL(term.inputPosition - currentCountAlreadyChecked);
- break;
-
- case PatternTerm::TypeAssertionEOL:
- assertionEOL(term.inputPosition - currentCountAlreadyChecked);
- break;
-
- case PatternTerm::TypeAssertionWordBoundary:
- assertionWordBoundary(term.invertOrCapture, term.inputPosition - currentCountAlreadyChecked);
- break;
-
- case PatternTerm::TypePatternCharacter:
- atomPatternCharacter(term.patternCharacter, term.inputPosition - currentCountAlreadyChecked, term.frameLocation, term.quantityCount, term.quantityType);
- break;
-
- case PatternTerm::TypeCharacterClass:
- atomCharacterClass(term.characterClass, term.invertOrCapture, term.inputPosition - currentCountAlreadyChecked, term.frameLocation, term.quantityCount, term.quantityType);
- break;
-
- case PatternTerm::TypeBackReference:
- atomBackReference(term.subpatternId, term.inputPosition - currentCountAlreadyChecked, term.frameLocation, term.quantityCount, term.quantityType);
- break;
-
- case PatternTerm::TypeForwardReference:
- break;
-
- case PatternTerm::TypeParenthesesSubpattern: {
- unsigned disjunctionAlreadyCheckedCount = 0;
- if ((term.quantityCount == 1) && !term.parentheses.isCopy) {
- if (term.quantityType == QuantifierFixedCount) {
- disjunctionAlreadyCheckedCount = term.parentheses.disjunction->m_minimumSize;
- unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
- atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, term.frameLocation);
- emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, term.parentheses.disjunction->m_minimumSize);
- atomParenthesesEnd(true, term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
- } else {
- unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
- atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, term.frameLocation + RegexStackSpaceForBackTrackInfoParenthesesOnce);
- emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0);
- atomParenthesesEnd(true, term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
- }
- } else {
- unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
- atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, 0);
- emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0);
- atomParenthesesEnd(false, term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
- }
- break;
- }
-
- case PatternTerm::TypeParentheticalAssertion: {
- unsigned alternativeFrameLocation = term.frameLocation + RegexStackSpaceForBackTrackInfoParentheticalAssertion;
-
- atomParentheticalAssertionBegin(term.parentheses.subpatternId, term.invertOrCapture, term.frameLocation, alternativeFrameLocation);
- emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0);
- atomParenthesesEnd(true, term.parentheses.lastSubpatternId, 0, term.frameLocation, term.quantityCount, term.quantityType);
- break;
- }
- }
- }
- }
- }
-
-private:
- RegexPattern& m_pattern;
- ByteDisjunction* m_bodyDisjunction;
- unsigned m_currentAlternativeIndex;
- Vector<ParenthesesStackEntry> m_parenthesesStack;
- Vector<ByteDisjunction*> m_allParenthesesInfo;
-};
-
-
-BytecodePattern* byteCompileRegex(const UString& patternString, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline)
-{
- RegexPattern pattern(ignoreCase, multiline);
-
- if ((error = compileRegex(patternString, pattern)))
- return 0;
-
- numSubpatterns = pattern.m_numSubpatterns;
-
- return ByteCompiler(pattern).compile();
-}
-
-int interpretRegex(BytecodePattern* regex, const UChar* input, unsigned start, unsigned length, int* output)
-{
- return Interpreter(regex, output, input, start, length).interpret();
-}
-
-
-COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoPatternCharacter) == (RegexStackSpaceForBackTrackInfoPatternCharacter * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoPatternCharacter);
-COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoCharacterClass) == (RegexStackSpaceForBackTrackInfoCharacterClass * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoCharacterClass);
-COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoBackReference) == (RegexStackSpaceForBackTrackInfoBackReference * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoBackReference);
-COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoAlternative) == (RegexStackSpaceForBackTrackInfoAlternative * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoAlternative);
-COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoParentheticalAssertion) == (RegexStackSpaceForBackTrackInfoParentheticalAssertion * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoParentheticalAssertion);
-COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoParenthesesOnce) == (RegexStackSpaceForBackTrackInfoParenthesesOnce * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoParenthesesOnce);
-COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoParentheses) == (RegexStackSpaceForBackTrackInfoParentheses * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoParentheses);
-
-
-} }
-
-#endif
projects / apple / javascriptcore.git / blobdiff