| /* |
| * Copyright (C) 2008 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 "WREC.h" |
| |
| #if ENABLE(WREC) |
| |
| #include "CharacterClassConstructor.h" |
| #include "Machine.h" |
| #include "pcre_internal.h" |
| |
| using namespace WTF; |
| |
| namespace JSC { |
| |
| class GenerateAtomFunctor { |
| public: |
| virtual ~GenerateAtomFunctor() {} |
| |
| virtual void generateAtom(WRECGenerator*, JmpSrcVector&) = 0; |
| virtual void backtrack(WRECGenerator*) = 0; |
| }; |
| |
| class GeneratePatternCharacterFunctor : public GenerateAtomFunctor { |
| public: |
| GeneratePatternCharacterFunctor(const UChar ch) |
| : m_ch(ch) |
| { |
| } |
| |
| virtual void generateAtom(WRECGenerator*, JmpSrcVector&); |
| virtual void backtrack(WRECGenerator*); |
| |
| private: |
| const UChar m_ch; |
| }; |
| |
| class GenerateCharacterClassFunctor : public GenerateAtomFunctor { |
| public: |
| GenerateCharacterClassFunctor(CharacterClass* charClass, bool invert) |
| : m_charClass(charClass) |
| , m_invert(invert) |
| { |
| } |
| |
| virtual void generateAtom(WRECGenerator*, JmpSrcVector&); |
| virtual void backtrack(WRECGenerator*); |
| |
| private: |
| CharacterClass* m_charClass; |
| bool m_invert; |
| }; |
| |
| class GenerateBackreferenceFunctor : public GenerateAtomFunctor { |
| public: |
| GenerateBackreferenceFunctor(unsigned subpatternId) |
| : m_subpatternId(subpatternId) |
| { |
| } |
| |
| virtual void generateAtom(WRECGenerator*, JmpSrcVector&); |
| virtual void backtrack(WRECGenerator*); |
| |
| private: |
| unsigned m_subpatternId; |
| }; |
| |
| class GenerateParenthesesNonGreedyFunctor : public GenerateAtomFunctor { |
| public: |
| GenerateParenthesesNonGreedyFunctor(WRECGenerator::JmpDst start, WRECGenerator::JmpSrc success, WRECGenerator::JmpSrc fail) |
| : m_start(start) |
| , m_success(success) |
| , m_fail(fail) |
| { |
| } |
| |
| virtual void generateAtom(WRECGenerator*, JmpSrcVector&); |
| virtual void backtrack(WRECGenerator*); |
| |
| private: |
| WRECGenerator::JmpDst m_start; |
| WRECGenerator::JmpSrc m_success; |
| WRECGenerator::JmpSrc m_fail; |
| }; |
| |
| void GeneratePatternCharacterFunctor::generateAtom(WRECGenerator* wrec, JmpSrcVector& failures) |
| { |
| wrec->generatePatternCharacter(failures, m_ch); |
| } |
| void GeneratePatternCharacterFunctor::backtrack(WRECGenerator* wrec) |
| { |
| wrec->generateBacktrack1(); |
| } |
| |
| void GenerateCharacterClassFunctor::generateAtom(WRECGenerator* wrec, JmpSrcVector& failures) |
| { |
| wrec->generateCharacterClass(failures, *m_charClass, m_invert); |
| } |
| void GenerateCharacterClassFunctor::backtrack(WRECGenerator* wrec) |
| { |
| wrec->generateBacktrack1(); |
| } |
| |
| void GenerateBackreferenceFunctor::generateAtom(WRECGenerator* wrec, JmpSrcVector& failures) |
| { |
| wrec->generateBackreference(failures, m_subpatternId); |
| } |
| void GenerateBackreferenceFunctor::backtrack(WRECGenerator* wrec) |
| { |
| wrec->generateBacktrackBackreference(m_subpatternId); |
| } |
| |
| void GenerateParenthesesNonGreedyFunctor::generateAtom(WRECGenerator* wrec, JmpSrcVector& failures) |
| { |
| wrec->generateParenthesesNonGreedy(failures, m_start, m_success, m_fail); |
| } |
| |
| void GenerateParenthesesNonGreedyFunctor::backtrack(WRECGenerator*) |
| { |
| // FIXME: do something about this. |
| CRASH(); |
| } |
| |
| void WRECGenerator::generateBacktrack1() |
| { |
| m_jit.subl_i8r(1, currentPositionRegister); |
| } |
| |
| void WRECGenerator::generateBacktrackBackreference(unsigned subpatternId) |
| { |
| m_jit.subl_mr((2 * subpatternId + 1) * sizeof(int), outputRegister, currentPositionRegister); |
| m_jit.addl_mr((2 * subpatternId) * sizeof(int), outputRegister, currentPositionRegister); |
| } |
| |
| void WRECGenerator::generateBackreferenceQuantifier(JmpSrcVector& failures, Quantifier::Type quantifierType, unsigned subpatternId, unsigned min, unsigned max) |
| { |
| GenerateBackreferenceFunctor functor(subpatternId); |
| |
| m_jit.movl_mr((2 * subpatternId) * sizeof(int), outputRegister, currentValueRegister); |
| m_jit.cmpl_rm(currentValueRegister, ((2 * subpatternId) + 1) * sizeof(int), outputRegister); |
| JmpSrc skipIfEmpty = m_jit.emitUnlinkedJe(); |
| |
| ASSERT(quantifierType == Quantifier::Greedy || quantifierType == Quantifier::NonGreedy); |
| if (quantifierType == Quantifier::Greedy) |
| generateGreedyQuantifier(failures, functor, min, max); |
| else |
| generateNonGreedyQuantifier(failures, functor, min, max); |
| |
| m_jit.link(skipIfEmpty, m_jit.label()); |
| } |
| |
| void WRECGenerator::generateNonGreedyQuantifier(JmpSrcVector& failures, GenerateAtomFunctor& functor, unsigned min, unsigned max) |
| { |
| // comment me better! |
| JmpSrcVector newFailures; |
| |
| // (0) Setup: |
| // init quantifierCountRegister |
| m_jit.pushl_r(quantifierCountRegister); |
| m_jit.xorl_rr(quantifierCountRegister, quantifierCountRegister); |
| JmpSrc gotoStart = m_jit.emitUnlinkedJmp(); |
| |
| // (4) Failure case |
| |
| JmpDst quantifierFailed = m_jit.label(); |
| // (4.1) Restore original value of quantifierCountRegister from the stack |
| m_jit.popl_r(quantifierCountRegister); |
| failures.append(m_jit.emitUnlinkedJmp()); |
| |
| // (3) We just tried an alternative, and it failed - check we can try more. |
| |
| JmpDst alternativeFailed = m_jit.label(); |
| // (3.1) remove the value pushed prior to testing the alternative |
| m_jit.popl_r(currentPositionRegister); |
| // (3.2) if there is a limit, and we have reached it, game over. |
| if (max != Quantifier::noMaxSpecified) { |
| m_jit.cmpl_i32r(max, quantifierCountRegister); |
| m_jit.link(m_jit.emitUnlinkedJe(), quantifierFailed); |
| } |
| |
| // (1) Do a check for the atom |
| |
| // (1.0) This is where we start, if there is a minimum (then we must read at least one of the atom). |
| JmpDst testQuantifiedAtom = m_jit.label(); |
| if (min) |
| m_jit.link(gotoStart, testQuantifiedAtom); |
| // (1.1) Do a check for the atom check. |
| functor.generateAtom(this, newFailures); |
| // (1.2) If we get here, successful match! |
| m_jit.addl_i8r(1, quantifierCountRegister); |
| // (1.3) We needed to read the atom, and we failed - that's terminally bad news. |
| for (unsigned i = 0; i < newFailures.size(); ++i) |
| m_jit.link(newFailures[i], quantifierFailed); |
| newFailures.clear(); |
| // (1.4) If there is a minimum, check we have read enough ... |
| if (min) { |
| // ... except if min was 1 no need to keep checking! |
| if (min != 1) { |
| m_jit.cmpl_i32r(min, quantifierCountRegister); |
| m_jit.link(m_jit.emitUnlinkedJl(), testQuantifiedAtom); |
| } |
| } else |
| m_jit.link(gotoStart, m_jit.label()); |
| // if there was no minimum, this is where we start. |
| |
| // (2) Plant an alternative check for the remainder of the expression |
| |
| // (2.1) recursively call to parseAlternative, if it falls through, success! |
| m_jit.pushl_r(currentPositionRegister); |
| m_parser.parseAlternative(newFailures); |
| m_jit.addl_i8r(4, X86::esp); |
| m_jit.popl_r(quantifierCountRegister); |
| // (2.2) link failure cases to jump back up to alternativeFailed. |
| for (unsigned i = 0; i < newFailures.size(); ++i) |
| m_jit.link(newFailures[i], alternativeFailed); |
| newFailures.clear(); |
| } |
| |
| void WRECGenerator::generateGreedyQuantifier(JmpSrcVector& failures, GenerateAtomFunctor& functor, unsigned min, unsigned max) |
| { |
| if (!max) |
| return; |
| |
| // comment me better! |
| JmpSrcVector newFailures; |
| |
| // (0) Setup: |
| // init quantifierCountRegister |
| m_jit.pushl_r(quantifierCountRegister); |
| m_jit.xorl_rr(quantifierCountRegister, quantifierCountRegister); |
| |
| // (1) Greedily read as many of the atom as possible |
| |
| JmpDst readMore = m_jit.label(); |
| |
| // (1.1) Do a character class check. |
| functor.generateAtom(this, newFailures); |
| // (1.2) If we get here, successful match! |
| m_jit.addl_i8r(1, quantifierCountRegister); |
| // (1.3) loop, unless we've read max limit. |
| if (max != Quantifier::noMaxSpecified) { |
| if (max != 1) { |
| // if there is a limit, only loop while less than limit, otherwise fall throught to... |
| m_jit.cmpl_i32r(max, quantifierCountRegister); |
| m_jit.link(m_jit.emitUnlinkedJne(), readMore); |
| } |
| // ...if there is no min we need jump to the alternative test, if there is we can just fall through to it. |
| if (!min) |
| newFailures.append(m_jit.emitUnlinkedJmp()); |
| } else |
| m_jit.link(m_jit.emitUnlinkedJmp(), readMore); |
| // (1.4) check enough matches to bother trying an alternative... |
| if (min) { |
| // We will fall through to here if (min && max), after the max check. |
| // First, also link a |
| JmpDst minimumTest = m_jit.label(); |
| for (unsigned i = 0; i < newFailures.size(); ++i) |
| m_jit.link(newFailures[i], minimumTest); |
| newFailures.clear(); |
| // |
| m_jit.cmpl_i32r(min, quantifierCountRegister); |
| newFailures.append(m_jit.emitUnlinkedJae()); |
| } |
| |
| // (4) Failure case |
| |
| JmpDst quantifierFailed = m_jit.label(); |
| // (4.1) Restore original value of quantifierCountRegister from the stack |
| m_jit.popl_r(quantifierCountRegister); |
| failures.append(m_jit.emitUnlinkedJmp()); |
| |
| // (3) Backtrack |
| |
| JmpDst backtrack = m_jit.label(); |
| // (3.1) this was preserved prior to executing the alternative |
| m_jit.popl_r(currentPositionRegister); |
| // (3.2) check we can retry with fewer matches - backtracking fails if already at the minimum |
| m_jit.cmpl_i32r(min, quantifierCountRegister); |
| m_jit.link(m_jit.emitUnlinkedJe(), quantifierFailed); |
| // (3.3) roll off one match, and retry. |
| functor.backtrack(this); |
| m_jit.subl_i8r(1, quantifierCountRegister); |
| |
| // (2) Try an alternative. |
| |
| // (2.1) point to retry |
| JmpDst tryAlternative = m_jit.label(); |
| for (unsigned i = 0; i < newFailures.size(); ++i) |
| m_jit.link(newFailures[i], tryAlternative); |
| newFailures.clear(); |
| // (2.2) recursively call to parseAlternative, if it falls through, success! |
| m_jit.pushl_r(currentPositionRegister); |
| m_parser.parseAlternative(newFailures); |
| m_jit.addl_i8r(4, X86::esp); |
| m_jit.popl_r(quantifierCountRegister); |
| // (2.3) link failure cases to here. |
| for (unsigned i = 0; i < newFailures.size(); ++i) |
| m_jit.link(newFailures[i], backtrack); |
| newFailures.clear(); |
| } |
| |
| void WRECGenerator::generatePatternCharacter(JmpSrcVector& failures, int ch) |
| { |
| // check there is more input, read a char. |
| m_jit.cmpl_rr(lengthRegister, currentPositionRegister); |
| failures.append(m_jit.emitUnlinkedJe()); |
| m_jit.movzwl_mr(inputRegister, currentPositionRegister, 2, currentValueRegister); |
| |
| // used for unicode case insensitive |
| bool hasUpper = false; |
| JmpSrc isUpper; |
| |
| // if case insensitive match |
| if (m_parser.m_ignoreCase) { |
| UChar lower, upper; |
| |
| // check for ascii case sensitive characters |
| if (isASCIIAlpha(ch)) { |
| m_jit.orl_i32r(32, currentValueRegister); |
| ch |= 32; |
| } else if ((ch > 0x7f) && ((lower = Unicode::toLower(ch)) != (upper = Unicode::toUpper(ch)))) { |
| // handle unicode case sentitive characters - branch to success on upper |
| m_jit.cmpl_i32r(upper, currentValueRegister); |
| isUpper = m_jit.emitUnlinkedJe(); |
| hasUpper = true; |
| ch = lower; |
| } |
| } |
| |
| // checks for ch, or lower case version of ch, if insensitive |
| m_jit.cmpl_i32r((unsigned short)ch, currentValueRegister); |
| failures.append(m_jit.emitUnlinkedJne()); |
| |
| if (m_parser.m_ignoreCase && hasUpper) { |
| // for unicode case insensitive matches, branch here if upper matches. |
| m_jit.link(isUpper, m_jit.label()); |
| } |
| |
| // on success consume the char |
| m_jit.addl_i8r(1, currentPositionRegister); |
| } |
| |
| void WRECGenerator::generateCharacterClassInvertedRange(JmpSrcVector& failures, JmpSrcVector& matchDest, const CharacterClassRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount) |
| { |
| do { |
| // pick which range we're going to generate |
| int which = count >> 1; |
| char lo = ranges[which].begin; |
| char hi = ranges[which].end; |
| |
| m_jit.cmpl_i32r((unsigned short)lo, currentValueRegister); |
| |
| // check if there are any ranges or matches below lo. If not, just jl to failure - |
| // if there is anything else to check, check that first, if it falls through jmp to failure. |
| if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) { |
| JmpSrc loOrAbove = m_jit.emitUnlinkedJge(); |
| |
| // generate code for all ranges before this one |
| if (which) |
| generateCharacterClassInvertedRange(failures, matchDest, ranges, which, matchIndex, matches, matchCount); |
| |
| do { |
| m_jit.cmpl_i32r((unsigned short)matches[*matchIndex], currentValueRegister); |
| matchDest.append(m_jit.emitUnlinkedJe()); |
| ++*matchIndex; |
| } while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)); |
| failures.append(m_jit.emitUnlinkedJmp()); |
| |
| m_jit.link(loOrAbove, m_jit.label()); |
| } else if (which) { |
| JmpSrc loOrAbove = m_jit.emitUnlinkedJge(); |
| |
| generateCharacterClassInvertedRange(failures, matchDest, ranges, which, matchIndex, matches, matchCount); |
| failures.append(m_jit.emitUnlinkedJmp()); |
| |
| m_jit.link(loOrAbove, m_jit.label()); |
| } else |
| failures.append(m_jit.emitUnlinkedJl()); |
| |
| while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi)) |
| ++*matchIndex; |
| |
| m_jit.cmpl_i32r((unsigned short)hi, currentValueRegister); |
| matchDest.append(m_jit.emitUnlinkedJle()); |
| // fall through to here, the value is above hi. |
| |
| // shuffle along & loop around if there are any more matches to handle. |
| unsigned next = which + 1; |
| ranges += next; |
| count -= next; |
| } while (count); |
| } |
| |
| void WRECGenerator::generateCharacterClassInverted(JmpSrcVector& matchDest, CharacterClass& charClass) |
| { |
| JmpSrc unicodeFail; |
| if (charClass.numMatchesUnicode || charClass.numRangesUnicode) { |
| m_jit.cmpl_i8r(0x7f, currentValueRegister); |
| JmpSrc isAscii = m_jit.emitUnlinkedJle(); |
| |
| if (charClass.numMatchesUnicode) { |
| for (unsigned i = 0; i < charClass.numMatchesUnicode; ++i) { |
| UChar ch = charClass.matchesUnicode[i]; |
| m_jit.cmpl_i32r((unsigned short)ch, currentValueRegister); |
| matchDest.append(m_jit.emitUnlinkedJe()); |
| } |
| } |
| |
| if (charClass.numRangesUnicode) { |
| for (unsigned i = 0; i < charClass.numRangesUnicode; ++i) { |
| UChar lo = charClass.rangesUnicode[i].begin; |
| UChar hi = charClass.rangesUnicode[i].end; |
| |
| m_jit.cmpl_i32r((unsigned short)lo, currentValueRegister); |
| JmpSrc below = m_jit.emitUnlinkedJl(); |
| m_jit.cmpl_i32r((unsigned short)hi, currentValueRegister); |
| matchDest.append(m_jit.emitUnlinkedJle()); |
| m_jit.link(below, m_jit.label()); |
| } |
| } |
| |
| unicodeFail = m_jit.emitUnlinkedJmp(); |
| m_jit.link(isAscii, m_jit.label()); |
| } |
| |
| if (charClass.numRanges) { |
| unsigned matchIndex = 0; |
| JmpSrcVector failures; |
| generateCharacterClassInvertedRange(failures, matchDest, charClass.ranges, charClass.numRanges, &matchIndex, charClass.matches, charClass.numMatches); |
| while (matchIndex < charClass.numMatches) { |
| m_jit.cmpl_i32r((unsigned short)charClass.matches[matchIndex], currentValueRegister); |
| matchDest.append(m_jit.emitUnlinkedJe()); |
| ++matchIndex; |
| } |
| JmpDst noMatch = m_jit.label(); |
| for (unsigned i = 0; i < failures.size(); ++i) |
| m_jit.link(failures[i], noMatch); |
| failures.clear(); |
| } else if (charClass.numMatches) { |
| // optimization: gather 'a','A' etc back together, can mask & test once. |
| Vector<char> matchesAZaz; |
| |
| for (unsigned i = 0; i < charClass.numMatches; ++i) { |
| char ch = charClass.matches[i]; |
| if (m_parser.m_ignoreCase) { |
| if (isASCIILower(ch)) { |
| matchesAZaz.append(ch); |
| continue; |
| } |
| if (isASCIIUpper(ch)) |
| continue; |
| } |
| m_jit.cmpl_i32r((unsigned short)ch, currentValueRegister); |
| matchDest.append(m_jit.emitUnlinkedJe()); |
| } |
| |
| if (unsigned countAZaz = matchesAZaz.size()) { |
| m_jit.orl_i32r(32, currentValueRegister); |
| |
| for (unsigned i = 0; i < countAZaz; ++i) { |
| char ch = matchesAZaz[i]; |
| m_jit.cmpl_i32r((unsigned short)ch, currentValueRegister); |
| matchDest.append(m_jit.emitUnlinkedJe()); |
| } |
| } |
| } |
| |
| if (charClass.numMatchesUnicode || charClass.numRangesUnicode) |
| m_jit.link(unicodeFail, m_jit.label()); |
| } |
| |
| void WRECGenerator::generateCharacterClass(JmpSrcVector& failures, CharacterClass& charClass, bool invert) |
| { |
| m_jit.cmpl_rr(lengthRegister, currentPositionRegister); |
| failures.append(m_jit.emitUnlinkedJe()); |
| m_jit.movzwl_mr(inputRegister, currentPositionRegister, 2, currentValueRegister); |
| |
| if (invert) |
| generateCharacterClassInverted(failures, charClass); |
| else { |
| JmpSrcVector successes; |
| generateCharacterClassInverted(successes, charClass); |
| failures.append(m_jit.emitUnlinkedJmp()); |
| JmpDst here = m_jit.label(); |
| for (unsigned i = 0; i < successes.size(); ++i) |
| m_jit.link(successes[i], here); |
| } |
| |
| m_jit.addl_i8r(1, currentPositionRegister); |
| } |
| |
| WRECGenerator::JmpSrc WRECGenerator::generateParentheses(ParenthesesType type) |
| { |
| unsigned subpatternId = (type == capturing) ? ++m_parser.m_numSubpatterns : m_parser.m_numSubpatterns; |
| |
| // push pos, both to preserve for fail + reloaded in parseDisjunction |
| m_jit.pushl_r(currentPositionRegister); |
| |
| // Plant a disjunction, wrapped to invert behaviour - |
| JmpSrcVector newFailures; |
| m_parser.parseDisjunction(newFailures); |
| |
| if (type == capturing) { |
| m_jit.popl_r(currentValueRegister); |
| m_jit.movl_rm(currentValueRegister, (2 * subpatternId) * sizeof(int), outputRegister); |
| m_jit.movl_rm(currentPositionRegister, (2 * subpatternId + 1) * sizeof(int), outputRegister); |
| } else if (type == non_capturing) |
| m_jit.addl_i8r(4, X86::esp); |
| else |
| m_jit.popl_r(currentPositionRegister); |
| |
| // This is a little lame - jump to jump if there is a nested disjunction. |
| // (suggestion to fix: make parseDisjunction populate a JmpSrcVector of |
| // disjunct successes... this is probably not worth the compile cost in |
| // the common case to fix). |
| JmpSrc successfulMatch = m_jit.emitUnlinkedJmp(); |
| |
| JmpDst originalFailure = m_jit.label(); |
| for (unsigned i = 0; i < newFailures.size(); ++i) |
| m_jit.link(newFailures[i], originalFailure); |
| newFailures.clear(); |
| // fail: restore currentPositionRegister |
| m_jit.popl_r(currentPositionRegister); |
| |
| JmpSrc jumpToFail; |
| // If this was an inverted assert, fail = success! - just let the failure case drop through, |
| // success case goes to failures. Both paths restore curr pos. |
| if (type == inverted_assertion) |
| jumpToFail = successfulMatch; |
| else { |
| // plant a jump so any fail will link off to 'failures', |
| jumpToFail = m_jit.emitUnlinkedJmp(); |
| // link successes to jump here |
| m_jit.link(successfulMatch, m_jit.label()); |
| } |
| return jumpToFail; |
| } |
| |
| void WRECGenerator::generateParenthesesNonGreedy(JmpSrcVector& failures, JmpDst start, JmpSrc success, JmpSrc fail) |
| { |
| m_jit.link(m_jit.emitUnlinkedJmp(), start); |
| m_jit.link(success, m_jit.label()); |
| |
| failures.append(fail); |
| } |
| |
| WRECGenerator::JmpSrc WRECGenerator::generateParenthesesResetTrampoline(JmpSrcVector& newFailures, unsigned subpatternIdBefore, unsigned subpatternIdAfter) |
| { |
| JmpSrc skip = m_jit.emitUnlinkedJmp(); |
| |
| JmpDst subPatternResetTrampoline = m_jit.label(); |
| for (unsigned i = 0; i < newFailures.size(); ++i) |
| m_jit.link(newFailures[i], subPatternResetTrampoline); |
| newFailures.clear(); |
| for (unsigned i = subpatternIdBefore + 1; i <= subpatternIdAfter; ++i) { |
| m_jit.movl_i32m(-1, (2 * i) * sizeof(int), outputRegister); |
| m_jit.movl_i32m(-1, (2 * i + 1) * sizeof(int), outputRegister); |
| } |
| |
| JmpSrc newFailJump = m_jit.emitUnlinkedJmp(); |
| m_jit.link(skip, m_jit.label()); |
| |
| return newFailJump; |
| } |
| |
| void WRECGenerator::generateAssertionBOL(JmpSrcVector& failures) |
| { |
| if (m_parser.m_multiline) { |
| JmpSrcVector previousIsNewline; |
| |
| // begin of input == success |
| m_jit.cmpl_i8r(0, currentPositionRegister); |
| previousIsNewline.append(m_jit.emitUnlinkedJe()); |
| |
| // now check prev char against newline characters. |
| m_jit.movzwl_mr(-2, inputRegister, currentPositionRegister, 2, currentValueRegister); |
| generateCharacterClassInverted(previousIsNewline, getCharacterClassNewline()); |
| |
| failures.append(m_jit.emitUnlinkedJmp()); |
| |
| JmpDst success = m_jit.label(); |
| for (unsigned i = 0; i < previousIsNewline.size(); ++i) |
| m_jit.link(previousIsNewline[i], success); |
| previousIsNewline.clear(); |
| } else { |
| m_jit.cmpl_i8r(0, currentPositionRegister); |
| failures.append(m_jit.emitUnlinkedJne()); |
| } |
| } |
| |
| void WRECGenerator::generateAssertionEOL(JmpSrcVector& failures) |
| { |
| if (m_parser.m_multiline) { |
| JmpSrcVector nextIsNewline; |
| |
| // end of input == success |
| m_jit.cmpl_rr(lengthRegister, currentPositionRegister); |
| nextIsNewline.append(m_jit.emitUnlinkedJe()); |
| |
| // now check next char against newline characters. |
| m_jit.movzwl_mr(inputRegister, currentPositionRegister, 2, currentValueRegister); |
| generateCharacterClassInverted(nextIsNewline, getCharacterClassNewline()); |
| |
| failures.append(m_jit.emitUnlinkedJmp()); |
| |
| JmpDst success = m_jit.label(); |
| for (unsigned i = 0; i < nextIsNewline.size(); ++i) |
| m_jit.link(nextIsNewline[i], success); |
| nextIsNewline.clear(); |
| } else { |
| m_jit.cmpl_rr(lengthRegister, currentPositionRegister); |
| failures.append(m_jit.emitUnlinkedJne()); |
| } |
| } |
| |
| void WRECGenerator::generateAssertionWordBoundary(JmpSrcVector& failures, bool invert) |
| { |
| JmpSrcVector wordBoundary; |
| JmpSrcVector notWordBoundary; |
| |
| // (1) Check if the previous value was a word char |
| |
| // (1.1) check for begin of input |
| m_jit.cmpl_i8r(0, currentPositionRegister); |
| JmpSrc atBegin = m_jit.emitUnlinkedJe(); |
| // (1.2) load the last char, and chck if is word character |
| m_jit.movzwl_mr(-2, inputRegister, currentPositionRegister, 2, currentValueRegister); |
| JmpSrcVector previousIsWord; |
| generateCharacterClassInverted(previousIsWord, getCharacterClassWordchar()); |
| // (1.3) if we get here, previous is not a word char |
| m_jit.link(atBegin, m_jit.label()); |
| |
| // (2) Handle situation where previous was NOT a \w |
| |
| // (2.1) check for end of input |
| m_jit.cmpl_rr(lengthRegister, currentPositionRegister); |
| notWordBoundary.append(m_jit.emitUnlinkedJe()); |
| // (2.2) load the next char, and chck if is word character |
| m_jit.movzwl_mr(inputRegister, currentPositionRegister, 2, currentValueRegister); |
| generateCharacterClassInverted(wordBoundary, getCharacterClassWordchar()); |
| // (2.3) If we get here, neither chars are word chars |
| notWordBoundary.append(m_jit.emitUnlinkedJmp()); |
| |
| // (3) Handle situation where previous was a \w |
| |
| // (3.0) link success in first match to here |
| JmpDst section3 = m_jit.label(); |
| for (unsigned i = 0; i < previousIsWord.size(); ++i) |
| m_jit.link(previousIsWord[i], section3); |
| previousIsWord.clear(); |
| // (3.1) check for end of input |
| m_jit.cmpl_rr(lengthRegister, currentPositionRegister); |
| wordBoundary.append(m_jit.emitUnlinkedJe()); |
| // (3.2) load the next char, and chck if is word character |
| m_jit.movzwl_mr(inputRegister, currentPositionRegister, 2, currentValueRegister); |
| generateCharacterClassInverted(notWordBoundary, getCharacterClassWordchar()); |
| // (3.3) If we get here, this is an end of a word, within the input. |
| |
| // (4) Link everything up |
| |
| if (invert) { |
| // handle the fall through case |
| wordBoundary.append(m_jit.emitUnlinkedJmp()); |
| |
| // looking for non word boundaries, so link boundary fails to here. |
| JmpDst success = m_jit.label(); |
| for (unsigned i = 0; i < notWordBoundary.size(); ++i) |
| m_jit.link(notWordBoundary[i], success); |
| notWordBoundary.clear(); |
| |
| failures.append(wordBoundary.begin(), wordBoundary.size()); |
| } else { |
| // looking for word boundaries, so link successes here. |
| JmpDst success = m_jit.label(); |
| for (unsigned i = 0; i < wordBoundary.size(); ++i) |
| m_jit.link(wordBoundary[i], success); |
| wordBoundary.clear(); |
| |
| failures.append(notWordBoundary.begin(), notWordBoundary.size()); |
| } |
| } |
| |
| void WRECGenerator::generateBackreference(JmpSrcVector& failures, unsigned subpatternId) |
| { |
| m_jit.pushl_r(currentPositionRegister); |
| m_jit.pushl_r(quantifierCountRegister); |
| |
| // get the start pos of the backref into quantifierCountRegister (multipurpose!) |
| m_jit.movl_mr((2 * subpatternId) * sizeof(int), outputRegister, quantifierCountRegister); |
| |
| JmpSrc skipIncrement = m_jit.emitUnlinkedJmp(); |
| JmpDst topOfLoop = m_jit.label(); |
| m_jit.addl_i8r(1, currentPositionRegister); |
| m_jit.addl_i8r(1, quantifierCountRegister); |
| m_jit.link(skipIncrement, m_jit.label()); |
| |
| // check if we're at the end of backref (if we are, success!) |
| m_jit.cmpl_rm(quantifierCountRegister, ((2 * subpatternId) + 1) * sizeof(int), outputRegister); |
| JmpSrc endOfBackRef = m_jit.emitUnlinkedJe(); |
| |
| m_jit.movzwl_mr(inputRegister, quantifierCountRegister, 2, currentValueRegister); |
| |
| // check if we've run out of input (this would be a can o'fail) |
| m_jit.cmpl_rr(lengthRegister, currentPositionRegister); |
| JmpSrc endOfInput = m_jit.emitUnlinkedJe(); |
| |
| m_jit.cmpw_rm(currentValueRegister, inputRegister, currentPositionRegister, 2); |
| m_jit.link(m_jit.emitUnlinkedJe(), topOfLoop); |
| |
| m_jit.link(endOfInput, m_jit.label()); |
| // Failure |
| m_jit.popl_r(quantifierCountRegister); |
| m_jit.popl_r(currentPositionRegister); |
| failures.append(m_jit.emitUnlinkedJmp()); |
| |
| // Success |
| m_jit.link(endOfBackRef, m_jit.label()); |
| m_jit.popl_r(quantifierCountRegister); |
| m_jit.addl_i8r(4, X86::esp); |
| } |
| |
| void WRECGenerator::generateDisjunction(JmpSrcVector& successes, JmpSrcVector& failures) |
| { |
| successes.append(m_jit.emitUnlinkedJmp()); |
| |
| JmpDst here = m_jit.label(); |
| |
| for (unsigned i = 0; i < failures.size(); ++i) |
| m_jit.link(failures[i], here); |
| failures.clear(); |
| |
| m_jit.movl_mr(X86::esp, currentPositionRegister); |
| } |
| |
| void WRECGenerator::terminateDisjunction(JmpSrcVector& successes) |
| { |
| JmpDst here = m_jit.label(); |
| for (unsigned i = 0; i < successes.size(); ++i) |
| m_jit.link(successes[i], here); |
| successes.clear(); |
| } |
| |
| ALWAYS_INLINE Quantifier WRECParser::parseGreedyQuantifier() |
| { |
| switch (peek()) { |
| case '?': |
| consume(); |
| return Quantifier(Quantifier::Greedy, 0, 1); |
| |
| case '*': |
| consume(); |
| return Quantifier(Quantifier::Greedy, 0); |
| |
| case '+': |
| consume(); |
| return Quantifier(Quantifier::Greedy, 1); |
| |
| case '{': { |
| consume(); |
| // a numeric quantifier should always have a lower bound |
| if (!peekIsDigit()) { |
| m_err = Error_malformedQuantifier; |
| return Quantifier(Quantifier::Error); |
| } |
| int min = consumeNumber(); |
| |
| // this should either be a , or a } |
| switch (peek()) { |
| case '}': |
| // {n} - exactly n times. (technically I think a '?' is valid in the bnf - bit meaningless). |
| consume(); |
| return Quantifier(Quantifier::Greedy, min, min); |
| |
| case ',': |
| consume(); |
| switch (peek()) { |
| case '}': |
| // {n,} - n to inf times. |
| consume(); |
| return Quantifier(Quantifier::Greedy, min); |
| |
| case '0': |
| case '1': |
| case '2': |
| case '3': |
| case '4': |
| case '5': |
| case '6': |
| case '7': |
| case '8': |
| case '9': { |
| // {n,m} - n to m times. |
| int max = consumeNumber(); |
| |
| if (peek() != '}') { |
| m_err = Error_malformedQuantifier; |
| return Quantifier(Quantifier::Error); |
| } |
| consume(); |
| |
| return Quantifier(Quantifier::Greedy, min, max); |
| } |
| |
| default: |
| m_err = Error_malformedQuantifier; |
| return Quantifier(Quantifier::Error); |
| } |
| |
| default: |
| m_err = Error_malformedQuantifier; |
| return Quantifier(Quantifier::Error); |
| } |
| } |
| // None of the above - no quantifier |
| default: |
| return Quantifier(); |
| } |
| } |
| |
| Quantifier WRECParser::parseQuantifier() |
| { |
| Quantifier q = parseGreedyQuantifier(); |
| |
| if ((q.type == Quantifier::Greedy) && (peek() == '?')) { |
| consume(); |
| q.type = Quantifier::NonGreedy; |
| } |
| |
| return q; |
| } |
| |
| bool WRECParser::parsePatternCharacterQualifier(JmpSrcVector& failures, int ch) |
| { |
| Quantifier q = parseQuantifier(); |
| |
| switch (q.type) { |
| case Quantifier::None: { |
| m_generator.generatePatternCharacter(failures, ch); |
| break; |
| } |
| |
| case Quantifier::Greedy: { |
| GeneratePatternCharacterFunctor functor(ch); |
| m_generator.generateGreedyQuantifier(failures, functor, q.min, q.max); |
| break; |
| } |
| |
| case Quantifier::NonGreedy: { |
| GeneratePatternCharacterFunctor functor(ch); |
| m_generator.generateNonGreedyQuantifier(failures, functor, q.min, q.max); |
| break; |
| } |
| |
| case Quantifier::Error: |
| return false; |
| } |
| |
| return true; |
| } |
| |
| bool WRECParser::parseCharacterClassQuantifier(JmpSrcVector& failures, CharacterClass& charClass, bool invert) |
| { |
| Quantifier q = parseQuantifier(); |
| |
| switch (q.type) { |
| case Quantifier::None: { |
| m_generator.generateCharacterClass(failures, charClass, invert); |
| break; |
| } |
| |
| case Quantifier::Greedy: { |
| GenerateCharacterClassFunctor functor(&charClass, invert); |
| m_generator.generateGreedyQuantifier(failures, functor, q.min, q.max); |
| break; |
| } |
| |
| case Quantifier::NonGreedy: { |
| GenerateCharacterClassFunctor functor(&charClass, invert); |
| m_generator.generateNonGreedyQuantifier(failures, functor, q.min, q.max); |
| break; |
| } |
| |
| case Quantifier::Error: |
| return false; |
| } |
| |
| return true; |
| } |
| |
| bool WRECParser::parseBackreferenceQuantifier(JmpSrcVector& failures, unsigned subpatternId) |
| { |
| Quantifier q = parseQuantifier(); |
| |
| switch (q.type) { |
| case Quantifier::None: { |
| m_generator.generateBackreference(failures, subpatternId); |
| break; |
| } |
| |
| case Quantifier::Greedy: |
| case Quantifier::NonGreedy: |
| m_generator.generateBackreferenceQuantifier(failures, q.type, subpatternId, q.min, q.max); |
| return true; |
| |
| case Quantifier::Error: |
| return false; |
| } |
| |
| return true; |
| } |
| |
| bool WRECParser::parseParentheses(JmpSrcVector&) |
| { |
| // FIXME: We don't currently backtrack correctly within parentheses in cases such as |
| // "c".match(/(.*)c/) so we fall back to PCRE for any regexp containing parentheses. |
| |
| m_err = TempError_unsupportedParentheses; |
| return false; |
| } |
| |
| bool WRECParser::parseCharacterClass(JmpSrcVector& failures) |
| { |
| bool invert = false; |
| if (peek() == '^') { |
| consume(); |
| invert = true; |
| } |
| |
| CharacterClassConstructor charClassConstructor(m_ignoreCase); |
| |
| UChar ch; |
| while ((ch = peek()) != ']') { |
| switch (ch) { |
| case EndOfPattern: |
| m_err = Error_malformedCharacterClass; |
| return false; |
| |
| case '\\': |
| consume(); |
| switch (ch = peek()) { |
| case EndOfPattern: |
| m_err = Error_malformedEscape; |
| return false; |
| case '0': |
| case '1': |
| case '2': |
| case '3': |
| case '4': |
| case '5': |
| case '6': |
| case '7': |
| charClassConstructor.put(consumeOctal()); |
| break; |
| |
| // ControlEscape |
| case 'b': |
| consume(); |
| charClassConstructor.put('\b'); |
| break; |
| case 'f': |
| consume(); |
| charClassConstructor.put('\f'); |
| break; |
| case 'n': |
| consume(); |
| charClassConstructor.put('\n'); |
| break; |
| case 'r': |
| consume(); |
| charClassConstructor.put('\r'); |
| break; |
| case 't': |
| consume(); |
| charClassConstructor.put('\t'); |
| break; |
| case 'v': |
| consume(); |
| charClassConstructor.put('\v'); |
| break; |
| |
| // ControlLetter |
| case 'c': { |
| consume(); |
| int control = consume(); |
| if (!isASCIIAlpha(control)) { |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| charClassConstructor.put(control&31); |
| break; |
| } |
| |
| // HexEscape |
| case 'x': { |
| consume(); |
| int x = consumeHex(2); |
| if (x == -1) { |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| charClassConstructor.put(x); |
| break; |
| } |
| |
| // UnicodeEscape |
| case 'u': { |
| consume(); |
| int x = consumeHex(4); |
| if (x == -1) { |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| charClassConstructor.put(x); |
| break; |
| } |
| |
| // CharacterClassEscape |
| case 'd': |
| consume(); |
| charClassConstructor.append(getCharacterClassDigits()); |
| break; |
| case 's': |
| consume(); |
| charClassConstructor.append(getCharacterClassSpaces()); |
| break; |
| case 'w': |
| consume(); |
| charClassConstructor.append(getCharacterClassWordchar()); |
| break; |
| case 'D': |
| consume(); |
| charClassConstructor.append(getCharacterClassNondigits()); |
| break; |
| case 'S': |
| consume(); |
| charClassConstructor.append(getCharacterClassNonspaces()); |
| break; |
| case 'W': |
| consume(); |
| charClassConstructor.append(getCharacterClassNonwordchar()); |
| break; |
| |
| case '-': |
| consume(); |
| charClassConstructor.flushBeforeEscapedHyphen(); |
| charClassConstructor.put(ch); |
| break; |
| |
| // IdentityEscape |
| default: { |
| // TODO: check this test for IdentifierPart. |
| int ch = consume(); |
| if (isASCIIAlphanumeric(ch) || (ch == '_')) { |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| charClassConstructor.put(ch); |
| break; |
| } |
| } |
| break; |
| |
| default: |
| consume(); |
| charClassConstructor.put(ch); |
| } |
| } |
| consume(); |
| |
| // lazily catch reversed ranges ([z-a])in character classes |
| if (charClassConstructor.isUpsideDown()) { |
| m_err = Error_malformedCharacterClass; |
| return false; |
| } |
| |
| charClassConstructor.flush(); |
| CharacterClass charClass = charClassConstructor.charClass(); |
| return parseCharacterClassQuantifier(failures, charClass, invert); |
| } |
| |
| bool WRECParser::parseOctalEscape(JmpSrcVector& failures) |
| { |
| return parsePatternCharacterQualifier(failures, consumeOctal()); |
| } |
| |
| bool WRECParser::parseEscape(JmpSrcVector& failures) |
| { |
| switch (peek()) { |
| case EndOfPattern: |
| m_err = Error_malformedEscape; |
| return false; |
| |
| // Assertions |
| case 'b': |
| consume(); |
| m_generator.generateAssertionWordBoundary(failures, false); |
| return true; |
| |
| case 'B': |
| consume(); |
| m_generator.generateAssertionWordBoundary(failures, true); |
| return true; |
| |
| // Octal escape |
| case '0': |
| consume(); |
| return parseOctalEscape(failures); |
| |
| // DecimalEscape |
| case '1': |
| case '2': |
| case '3': |
| case '4': |
| case '5': |
| case '6': |
| case '7': { |
| // FIXME: This does not support forward references. It's not clear whether they |
| // should be valid. |
| unsigned value = peekDigit(); |
| if (value > m_numSubpatterns) |
| return parseOctalEscape(failures); |
| } |
| case '8': |
| case '9': { |
| unsigned value = peekDigit(); |
| if (value > m_numSubpatterns) { |
| consume(); |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| consume(); |
| |
| while (peekIsDigit()) { |
| unsigned newValue = value * 10 + peekDigit(); |
| if (newValue > m_numSubpatterns) |
| break; |
| value = newValue; |
| consume(); |
| } |
| |
| parseBackreferenceQuantifier(failures, value); |
| return true; |
| } |
| |
| // ControlEscape |
| case 'f': |
| consume(); |
| return parsePatternCharacterQualifier(failures, '\f'); |
| case 'n': |
| consume(); |
| return parsePatternCharacterQualifier(failures, '\n'); |
| case 'r': |
| consume(); |
| return parsePatternCharacterQualifier(failures, '\r'); |
| case 't': |
| consume(); |
| return parsePatternCharacterQualifier(failures, '\t'); |
| case 'v': |
| consume(); |
| return parsePatternCharacterQualifier(failures, '\v'); |
| |
| // ControlLetter |
| case 'c': { |
| consume(); |
| int control = consume(); |
| if (!isASCIIAlpha(control)) { |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| return parsePatternCharacterQualifier(failures, control&31); |
| } |
| |
| // HexEscape |
| case 'x': { |
| consume(); |
| int x = consumeHex(2); |
| if (x == -1) { |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| return parsePatternCharacterQualifier(failures, x); |
| } |
| |
| // UnicodeEscape |
| case 'u': { |
| consume(); |
| int x = consumeHex(4); |
| if (x == -1) { |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| return parsePatternCharacterQualifier(failures, x); |
| } |
| |
| // CharacterClassEscape |
| case 'd': |
| consume(); |
| return parseCharacterClassQuantifier(failures, getCharacterClassDigits(), false); |
| case 's': |
| consume(); |
| return parseCharacterClassQuantifier(failures, getCharacterClassSpaces(), false); |
| case 'w': |
| consume(); |
| return parseCharacterClassQuantifier(failures, getCharacterClassWordchar(), false); |
| case 'D': |
| consume(); |
| return parseCharacterClassQuantifier(failures, getCharacterClassDigits(), true); |
| case 'S': |
| consume(); |
| return parseCharacterClassQuantifier(failures, getCharacterClassSpaces(), true); |
| case 'W': |
| consume(); |
| return parseCharacterClassQuantifier(failures, getCharacterClassWordchar(), true); |
| |
| // IdentityEscape |
| default: { |
| // TODO: check this test for IdentifierPart. |
| int ch = consume(); |
| if (isASCIIAlphanumeric(ch) || (ch == '_')) { |
| m_err = Error_malformedEscape; |
| return false; |
| } |
| return parsePatternCharacterQualifier(failures, ch); |
| } |
| } |
| } |
| |
| bool WRECParser::parseTerm(JmpSrcVector& failures) |
| { |
| switch (peek()) { |
| case EndOfPattern: |
| case '*': |
| case '+': |
| case '?': |
| case ')': |
| case ']': |
| case '{': |
| case '}': |
| case '|': |
| // Not allowed in a Term! |
| return false; |
| |
| case '^': |
| consume(); |
| m_generator.generateAssertionBOL(failures); |
| return true; |
| |
| case '$': |
| consume(); |
| m_generator.generateAssertionEOL(failures); |
| return true; |
| |
| case '\\': |
| // b & B are also assertions... |
| consume(); |
| return parseEscape(failures); |
| |
| case '.': |
| consume(); |
| return parseCharacterClassQuantifier(failures, getCharacterClassNewline(), true); |
| |
| case '[': |
| // CharacterClass |
| consume(); |
| return parseCharacterClass(failures); |
| |
| case '(': |
| consume(); |
| return parseParentheses(failures); |
| |
| default: |
| // Anything else is a PatternCharacter |
| return parsePatternCharacterQualifier(failures, consume()); |
| } |
| } |
| |
| /* |
| interface req: CURR_POS is on stack (can be reloaded). |
| */ |
| void WRECParser::parseDisjunction(JmpSrcVector& failures) |
| { |
| parseAlternative(failures); |
| |
| if (peek() == '|') { |
| JmpSrcVector successes; |
| |
| do { |
| consume(); |
| |
| m_generator.generateDisjunction(successes, failures); |
| |
| parseAlternative(failures); |
| } while (peek() == '|'); |
| |
| m_generator.terminateDisjunction(successes); |
| } |
| } |
| |
| } // namespace JSC |
| |
| #endif // ENABLE(WREC) |
