JavaScriptCore/wrec/WRECGenerator.cpp - WebKit - Git at Google

 /*
  * 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 PLATFORM(X86)
     // On x86 edi & esi are callee preserved registers.
     push(X86::edi);
     push(X86::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 PLATFORM(X86)
     pop(X86::esi);
     pop(X86::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 PLATFORM(X86)
     pop(X86::esi);
     pop(X86::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)
	/*
	* 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 PLATFORM(X86)
	// On x86 edi & esi are callee preserved registers.
	push(X86::edi);
	push(X86::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 PLATFORM(X86)
	pop(X86::esi);
	pop(X86::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 PLATFORM(X86)
	pop(X86::esi);
	pop(X86::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)