diff options
Diffstat (limited to 'src/3rdparty/javascriptcore/JavaScriptCore/wrec/WRECGenerator.cpp')
| -rw-r--r-- | src/3rdparty/javascriptcore/JavaScriptCore/wrec/WRECGenerator.cpp | 653 |
1 files changed, 0 insertions, 653 deletions
diff --git a/src/3rdparty/javascriptcore/JavaScriptCore/wrec/WRECGenerator.cpp b/src/3rdparty/javascriptcore/JavaScriptCore/wrec/WRECGenerator.cpp deleted file mode 100644 index 7105984..0000000 --- a/src/3rdparty/javascriptcore/JavaScriptCore/wrec/WRECGenerator.cpp +++ /dev/null @@ -1,653 +0,0 @@ -/* - * 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 "Interpreter.h" -#include "WRECFunctors.h" -#include "WRECParser.h" -#include "pcre_internal.h" - -using namespace WTF; - -namespace JSC { namespace WREC { - -void Generator::generateEnter() -{ -#if CPU(X86) - // On x86 edi & esi are callee preserved registers. - push(X86Registers::edi); - push(X86Registers::esi); - -#if COMPILER(MSVC) - // Move the arguments into registers. - peek(input, 3); - peek(index, 4); - peek(length, 5); - peek(output, 6); -#else - // On gcc the function is regparm(3), so the input, index, and length registers - // (eax, edx, and ecx respectively) already contain the appropriate values. - // Just load the fourth argument (output) into edi - peek(output, 3); -#endif -#endif -} - -void Generator::generateReturnSuccess() -{ - ASSERT(returnRegister != index); - ASSERT(returnRegister != output); - - // Set return value. - pop(returnRegister); // match begin - store32(returnRegister, output); - store32(index, Address(output, 4)); // match end - - // Restore callee save registers. -#if CPU(X86) - pop(X86Registers::esi); - pop(X86Registers::edi); -#endif - ret(); -} - -void Generator::generateSaveIndex() -{ - push(index); -} - -void Generator::generateIncrementIndex(Jump* failure) -{ - peek(index); - if (failure) - *failure = branch32(Equal, length, index); - add32(Imm32(1), index); - poke(index); -} - -void Generator::generateLoadCharacter(JumpList& failures) -{ - failures.append(branch32(Equal, length, index)); - load16(BaseIndex(input, index, TimesTwo), character); -} - -// For the sake of end-of-line assertions, we treat one-past-the-end as if it -// were part of the input string. -void Generator::generateJumpIfNotEndOfInput(Label target) -{ - branch32(LessThanOrEqual, index, length, target); -} - -void Generator::generateReturnFailure() -{ - pop(); - move(Imm32(-1), returnRegister); - -#if CPU(X86) - pop(X86Registers::esi); - pop(X86Registers::edi); -#endif - ret(); -} - -void Generator::generateBacktrack1() -{ - sub32(Imm32(1), index); -} - -void Generator::generateBacktrackBackreference(unsigned subpatternId) -{ - sub32(Address(output, (2 * subpatternId + 1) * sizeof(int)), index); - add32(Address(output, (2 * subpatternId) * sizeof(int)), index); -} - -void Generator::generateBackreferenceQuantifier(JumpList& failures, Quantifier::Type quantifierType, unsigned subpatternId, unsigned min, unsigned max) -{ - GenerateBackreferenceFunctor functor(subpatternId); - - load32(Address(output, (2 * subpatternId) * sizeof(int)), character); - Jump skipIfEmpty = branch32(Equal, Address(output, ((2 * subpatternId) + 1) * sizeof(int)), character); - - ASSERT(quantifierType == Quantifier::Greedy || quantifierType == Quantifier::NonGreedy); - if (quantifierType == Quantifier::Greedy) - generateGreedyQuantifier(failures, functor, min, max); - else - generateNonGreedyQuantifier(failures, functor, min, max); - - skipIfEmpty.link(this); -} - -void Generator::generateNonGreedyQuantifier(JumpList& failures, GenerateAtomFunctor& functor, unsigned min, unsigned max) -{ - JumpList atomFailedList; - JumpList alternativeFailedList; - - // (0) Setup: Save, then init repeatCount. - push(repeatCount); - move(Imm32(0), repeatCount); - Jump start = jump(); - - // (4) Quantifier failed: No more atom reading possible. - Label quantifierFailed(this); - pop(repeatCount); - failures.append(jump()); - - // (3) Alternative failed: If we can, read another atom, then fall through to (2) to try again. - Label alternativeFailed(this); - pop(index); - if (max != Quantifier::Infinity) - branch32(Equal, repeatCount, Imm32(max), quantifierFailed); - - // (1) Read an atom. - if (min) - start.link(this); - Label readAtom(this); - functor.generateAtom(this, atomFailedList); - atomFailedList.linkTo(quantifierFailed, this); - add32(Imm32(1), repeatCount); - - // (2) Keep reading if we're under the minimum. - if (min > 1) - branch32(LessThan, repeatCount, Imm32(min), readAtom); - - // (3) Test the rest of the alternative. - if (!min) - start.link(this); - push(index); - m_parser.parseAlternative(alternativeFailedList); - alternativeFailedList.linkTo(alternativeFailed, this); - - pop(); - pop(repeatCount); -} - -void Generator::generateGreedyQuantifier(JumpList& failures, GenerateAtomFunctor& functor, unsigned min, unsigned max) -{ - if (!max) - return; - - JumpList doneReadingAtomsList; - JumpList alternativeFailedList; - - // (0) Setup: Save, then init repeatCount. - push(repeatCount); - move(Imm32(0), repeatCount); - - // (1) Greedily read as many copies of the atom as possible, then jump to (2). - Label readAtom(this); - functor.generateAtom(this, doneReadingAtomsList); - add32(Imm32(1), repeatCount); - if (max == Quantifier::Infinity) - jump(readAtom); - else if (max == 1) - doneReadingAtomsList.append(jump()); - else { - branch32(NotEqual, repeatCount, Imm32(max), readAtom); - doneReadingAtomsList.append(jump()); - } - - // (5) Quantifier failed: No more backtracking possible. - Label quantifierFailed(this); - pop(repeatCount); - failures.append(jump()); - - // (4) Alternative failed: Backtrack, then fall through to (2) to try again. - Label alternativeFailed(this); - pop(index); - functor.backtrack(this); - sub32(Imm32(1), repeatCount); - - // (2) Verify that we have enough atoms. - doneReadingAtomsList.link(this); - branch32(LessThan, repeatCount, Imm32(min), quantifierFailed); - - // (3) Test the rest of the alternative. - push(index); - m_parser.parseAlternative(alternativeFailedList); - alternativeFailedList.linkTo(alternativeFailed, this); - - pop(); - pop(repeatCount); -} - -void Generator::generatePatternCharacterSequence(JumpList& failures, int* sequence, size_t count) -{ - for (size_t i = 0; i < count;) { - if (i < count - 1) { - if (generatePatternCharacterPair(failures, sequence[i], sequence[i + 1])) { - i += 2; - continue; - } - } - - generatePatternCharacter(failures, sequence[i]); - ++i; - } -} - -bool Generator::generatePatternCharacterPair(JumpList& failures, int ch1, int ch2) -{ - if (m_parser.ignoreCase()) { - // Non-trivial case folding requires more than one test, so we can't - // test as a pair with an adjacent character. - if (!isASCII(ch1) && Unicode::toLower(ch1) != Unicode::toUpper(ch1)) - return false; - if (!isASCII(ch2) && Unicode::toLower(ch2) != Unicode::toUpper(ch2)) - return false; - } - - // Optimistically consume 2 characters. - add32(Imm32(2), index); - failures.append(branch32(GreaterThan, index, length)); - - // Load the characters we just consumed, offset -2 characters from index. - load32(BaseIndex(input, index, TimesTwo, -2 * 2), character); - - if (m_parser.ignoreCase()) { - // Convert ASCII alphabet characters to upper case before testing for - // equality. (ASCII non-alphabet characters don't require upper-casing - // because they have no uppercase equivalents. Unicode characters don't - // require upper-casing because we only handle Unicode characters whose - // upper and lower cases are equal.) - int ch1Mask = 0; - if (isASCIIAlpha(ch1)) { - ch1 |= 32; - ch1Mask = 32; - } - - int ch2Mask = 0; - if (isASCIIAlpha(ch2)) { - ch2 |= 32; - ch2Mask = 32; - } - - int mask = ch1Mask | (ch2Mask << 16); - if (mask) - or32(Imm32(mask), character); - } - int pair = ch1 | (ch2 << 16); - - failures.append(branch32(NotEqual, character, Imm32(pair))); - return true; -} - -void Generator::generatePatternCharacter(JumpList& failures, int ch) -{ - generateLoadCharacter(failures); - - // used for unicode case insensitive - bool hasUpper = false; - Jump isUpper; - - // if case insensitive match - if (m_parser.ignoreCase()) { - UChar lower, upper; - - // check for ascii case sensitive characters - if (isASCIIAlpha(ch)) { - or32(Imm32(32), character); - ch |= 32; - } else if (!isASCII(ch) && ((lower = Unicode::toLower(ch)) != (upper = Unicode::toUpper(ch)))) { - // handle unicode case sentitive characters - branch to success on upper - isUpper = branch32(Equal, character, Imm32(upper)); - hasUpper = true; - ch = lower; - } - } - - // checks for ch, or lower case version of ch, if insensitive - failures.append(branch32(NotEqual, character, Imm32((unsigned short)ch))); - - if (m_parser.ignoreCase() && hasUpper) { - // for unicode case insensitive matches, branch here if upper matches. - isUpper.link(this); - } - - // on success consume the char - add32(Imm32(1), index); -} - -void Generator::generateCharacterClassInvertedRange(JumpList& failures, JumpList& matchDest, const CharacterRange* 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; - - // 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)) { - Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo)); - - // generate code for all ranges before this one - if (which) - generateCharacterClassInvertedRange(failures, matchDest, ranges, which, matchIndex, matches, matchCount); - - while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) { - matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex]))); - ++*matchIndex; - } - failures.append(jump()); - - loOrAbove.link(this); - } else if (which) { - Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo)); - - generateCharacterClassInvertedRange(failures, matchDest, ranges, which, matchIndex, matches, matchCount); - failures.append(jump()); - - loOrAbove.link(this); - } else - failures.append(branch32(LessThan, character, Imm32((unsigned short)lo))); - - while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi)) - ++*matchIndex; - - matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi))); - // 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 Generator::generateCharacterClassInverted(JumpList& matchDest, const CharacterClass& charClass) -{ - Jump unicodeFail; - if (charClass.numMatchesUnicode || charClass.numRangesUnicode) { - Jump isAscii = branch32(LessThanOrEqual, character, Imm32(0x7f)); - - if (charClass.numMatchesUnicode) { - for (unsigned i = 0; i < charClass.numMatchesUnicode; ++i) { - UChar ch = charClass.matchesUnicode[i]; - matchDest.append(branch32(Equal, character, Imm32(ch))); - } - } - - if (charClass.numRangesUnicode) { - for (unsigned i = 0; i < charClass.numRangesUnicode; ++i) { - UChar lo = charClass.rangesUnicode[i].begin; - UChar hi = charClass.rangesUnicode[i].end; - - Jump below = branch32(LessThan, character, Imm32(lo)); - matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi))); - below.link(this); - } - } - - unicodeFail = jump(); - isAscii.link(this); - } - - if (charClass.numRanges) { - unsigned matchIndex = 0; - JumpList failures; - generateCharacterClassInvertedRange(failures, matchDest, charClass.ranges, charClass.numRanges, &matchIndex, charClass.matches, charClass.numMatches); - while (matchIndex < charClass.numMatches) - matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass.matches[matchIndex++]))); - - failures.link(this); - } 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.ignoreCase()) { - if (isASCIILower(ch)) { - matchesAZaz.append(ch); - continue; - } - if (isASCIIUpper(ch)) - continue; - } - matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch))); - } - - if (unsigned countAZaz = matchesAZaz.size()) { - or32(Imm32(32), character); - for (unsigned i = 0; i < countAZaz; ++i) - matchDest.append(branch32(Equal, character, Imm32(matchesAZaz[i]))); - } - } - - if (charClass.numMatchesUnicode || charClass.numRangesUnicode) - unicodeFail.link(this); -} - -void Generator::generateCharacterClass(JumpList& failures, const CharacterClass& charClass, bool invert) -{ - generateLoadCharacter(failures); - - if (invert) - generateCharacterClassInverted(failures, charClass); - else { - JumpList successes; - generateCharacterClassInverted(successes, charClass); - failures.append(jump()); - successes.link(this); - } - - add32(Imm32(1), index); -} - -void Generator::generateParenthesesAssertion(JumpList& failures) -{ - JumpList disjunctionFailed; - - push(index); - m_parser.parseDisjunction(disjunctionFailed); - Jump success = jump(); - - disjunctionFailed.link(this); - pop(index); - failures.append(jump()); - - success.link(this); - pop(index); -} - -void Generator::generateParenthesesInvertedAssertion(JumpList& failures) -{ - JumpList disjunctionFailed; - - push(index); - m_parser.parseDisjunction(disjunctionFailed); - - // If the disjunction succeeded, the inverted assertion failed. - pop(index); - failures.append(jump()); - - // If the disjunction failed, the inverted assertion succeeded. - disjunctionFailed.link(this); - pop(index); -} - -void Generator::generateParenthesesNonGreedy(JumpList& failures, Label start, Jump success, Jump fail) -{ - jump(start); - success.link(this); - failures.append(fail); -} - -Generator::Jump Generator::generateParenthesesResetTrampoline(JumpList& newFailures, unsigned subpatternIdBefore, unsigned subpatternIdAfter) -{ - Jump skip = jump(); - newFailures.link(this); - for (unsigned i = subpatternIdBefore + 1; i <= subpatternIdAfter; ++i) { - store32(Imm32(-1), Address(output, (2 * i) * sizeof(int))); - store32(Imm32(-1), Address(output, (2 * i + 1) * sizeof(int))); - } - - Jump newFailJump = jump(); - skip.link(this); - - return newFailJump; -} - -void Generator::generateAssertionBOL(JumpList& failures) -{ - if (m_parser.multiline()) { - JumpList previousIsNewline; - - // begin of input == success - previousIsNewline.append(branch32(Equal, index, Imm32(0))); - - // now check prev char against newline characters. - load16(BaseIndex(input, index, TimesTwo, -2), character); - generateCharacterClassInverted(previousIsNewline, CharacterClass::newline()); - - failures.append(jump()); - - previousIsNewline.link(this); - } else - failures.append(branch32(NotEqual, index, Imm32(0))); -} - -void Generator::generateAssertionEOL(JumpList& failures) -{ - if (m_parser.multiline()) { - JumpList nextIsNewline; - - generateLoadCharacter(nextIsNewline); // end of input == success - generateCharacterClassInverted(nextIsNewline, CharacterClass::newline()); - failures.append(jump()); - nextIsNewline.link(this); - } else { - failures.append(branch32(NotEqual, length, index)); - } -} - -void Generator::generateAssertionWordBoundary(JumpList& failures, bool invert) -{ - JumpList wordBoundary; - JumpList notWordBoundary; - - // (1) Check if the previous value was a word char - - // (1.1) check for begin of input - Jump atBegin = branch32(Equal, index, Imm32(0)); - // (1.2) load the last char, and chck if is word character - load16(BaseIndex(input, index, TimesTwo, -2), character); - JumpList previousIsWord; - generateCharacterClassInverted(previousIsWord, CharacterClass::wordchar()); - // (1.3) if we get here, previous is not a word char - atBegin.link(this); - - // (2) Handle situation where previous was NOT a \w - - generateLoadCharacter(notWordBoundary); - generateCharacterClassInverted(wordBoundary, CharacterClass::wordchar()); - // (2.1) If we get here, neither chars are word chars - notWordBoundary.append(jump()); - - // (3) Handle situation where previous was a \w - - // (3.0) link success in first match to here - previousIsWord.link(this); - generateLoadCharacter(wordBoundary); - generateCharacterClassInverted(notWordBoundary, CharacterClass::wordchar()); - // (3.1) 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(jump()); - - // looking for non word boundaries, so link boundary fails to here. - notWordBoundary.link(this); - - failures.append(wordBoundary); - } else { - // looking for word boundaries, so link successes here. - wordBoundary.link(this); - - failures.append(notWordBoundary); - } -} - -void Generator::generateBackreference(JumpList& failures, unsigned subpatternId) -{ - push(index); - push(repeatCount); - - // get the start pos of the backref into repeatCount (multipurpose!) - load32(Address(output, (2 * subpatternId) * sizeof(int)), repeatCount); - - Jump skipIncrement = jump(); - Label topOfLoop(this); - - add32(Imm32(1), index); - add32(Imm32(1), repeatCount); - skipIncrement.link(this); - - // check if we're at the end of backref (if we are, success!) - Jump endOfBackRef = branch32(Equal, Address(output, ((2 * subpatternId) + 1) * sizeof(int)), repeatCount); - - load16(BaseIndex(input, repeatCount, MacroAssembler::TimesTwo), character); - - // check if we've run out of input (this would be a can o'fail) - Jump endOfInput = branch32(Equal, length, index); - - branch16(Equal, BaseIndex(input, index, TimesTwo), character, topOfLoop); - - endOfInput.link(this); - - // Failure - pop(repeatCount); - pop(index); - failures.append(jump()); - - // Success - endOfBackRef.link(this); - pop(repeatCount); - pop(); -} - -void Generator::terminateAlternative(JumpList& successes, JumpList& failures) -{ - successes.append(jump()); - - failures.link(this); - peek(index); -} - -void Generator::terminateDisjunction(JumpList& successes) -{ - successes.link(this); -} - -} } // namespace JSC::WREC - -#endif // ENABLE(WREC) |