wrecgenerator.cpp

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

/*
 * 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)));