#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)
push(X86::edi);
push(X86::esi);
#if COMPILER(MSVC)
peek(input, 3);
peek(index, 4);
peek(length, 5);
peek(output, 6);
#else
peek(output, 3);
#endif
#endif
}
void Generator::generateReturnSuccess()
{
ASSERT(returnRegister != index);
ASSERT(returnRegister != output);
pop(returnRegister); store32(returnRegister, output);
store32(index, Address(output, 4));
#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);
}
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;
push(repeatCount);
move(Imm32(0), repeatCount);
Jump start = jump();
Label quantifierFailed(this);
pop(repeatCount);
failures.append(jump());
Label alternativeFailed(this);
pop(index);
if (max != Quantifier::Infinity)
branch32(Equal, repeatCount, Imm32(max), quantifierFailed);
if (min)
start.link(this);
Label readAtom(this);
functor.generateAtom(this, atomFailedList);
atomFailedList.linkTo(quantifierFailed, this);
add32(Imm32(1), repeatCount);
if (min > 1)
branch32(LessThan, repeatCount, Imm32(min), readAtom);
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;
push(repeatCount);
move(Imm32(0), repeatCount);
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());
}
Label quantifierFailed(this);
pop(repeatCount);
failures.append(jump());
Label alternativeFailed(this);
pop(index);
functor.backtrack(this);
sub32(Imm32(1), repeatCount);
doneReadingAtomsList.link(this);
branch32(LessThan, repeatCount, Imm32(min), quantifierFailed);
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()) {
if (!isASCII(ch1) && Unicode::toLower(ch1) != Unicode::toUpper(ch1))
return false;
if (!isASCII(ch2) && Unicode::toLower(ch2) != Unicode::toUpper(ch2))
return false;
}
add32(Imm32(2), index);
failures.append(branch32(GreaterThan, index, length));
load32(BaseIndex(input, index, TimesTwo, -2 * 2), character);
if (m_parser.ignoreCase()) {
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);
bool hasUpper = false;
Jump isUpper;
if (m_parser.ignoreCase()) {
UChar lower, upper;
if (isASCIIAlpha(ch)) {
or32(Imm32(32), character);
ch |= 32;
} else if (!isASCII(ch) && ((lower = Unicode::toLower(ch)) != (upper = Unicode::toUpper(ch)))) {
isUpper = branch32(Equal, character, Imm32(upper));
hasUpper = true;
ch = lower;
}
}
failures.append(branch32(NotEqual, character, Imm32((unsigned short)ch)));
if (m_parser.ignoreCase() && hasUpper) {
isUpper.link(this);
}
add32(Imm32(1), index);
}
void Generator::generateCharacterClassInvertedRange(JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
{
do {
int which = count >> 1;
char lo = ranges[which].begin;
char hi = ranges[which].end;
if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
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)));
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) {
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);
pop(index);
failures.append(jump());
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;
previousIsNewline.append(branch32(Equal, index, Imm32(0)));
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); 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;
Jump atBegin = branch32(Equal, index, Imm32(0));
load16(BaseIndex(input, index, TimesTwo, -2), character);
JumpList previousIsWord;
generateCharacterClassInverted(previousIsWord, CharacterClass::wordchar());
atBegin.link(this);
generateLoadCharacter(notWordBoundary);
generateCharacterClassInverted(wordBoundary, CharacterClass::wordchar());
notWordBoundary.append(jump());
previousIsWord.link(this);
generateLoadCharacter(wordBoundary);
generateCharacterClassInverted(notWordBoundary, CharacterClass::wordchar());
if (invert) {
wordBoundary.append(jump());
notWordBoundary.link(this);
failures.append(wordBoundary);
} else {
wordBoundary.link(this);
failures.append(notWordBoundary);
}
}
void Generator::generateBackreference(JumpList& failures, unsigned subpatternId)
{
push(index);
push(repeatCount);
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);
Jump endOfBackRef = branch32(Equal, Address(output, ((2 * subpatternId) + 1) * sizeof(int)), repeatCount);
load16(BaseIndex(input, repeatCount, MacroAssembler::TimesTwo), character);
Jump endOfInput = branch32(Equal, length, index);
branch16(Equal, BaseIndex(input, index, TimesTwo), character, topOfLoop);
endOfInput.link(this);
pop(repeatCount);
pop(index);
failures.append(jump());
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);
}
} }
#endif // ENABLE(WREC)