| /* |
| * 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.inputPosition + 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 |
