diff options
Diffstat (limited to 'JavaScriptCore/wrec/WREC.cpp')
| -rw-r--r-- | JavaScriptCore/wrec/WREC.cpp | 1324 |
1 files changed, 1324 insertions, 0 deletions
diff --git a/JavaScriptCore/wrec/WREC.cpp b/JavaScriptCore/wrec/WREC.cpp new file mode 100644 index 0000000..6d64a2c --- /dev/null +++ b/JavaScriptCore/wrec/WREC.cpp @@ -0,0 +1,1324 @@ +/* + * 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) |