wrecparser.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 "WRECParser.h"

#if ENABLE(WREC)

#include "CharacterClassConstructor.h"
#include "WRECFunctors.h"

using namespace WTF;

namespace JSC { namespace WREC {

// These error messages match the error messages used by PCRE.
const char* Parser::QuantifierOutOfOrder = "numbers out of order in {} quantifier";
const char* Parser::QuantifierWithoutAtom = "nothing to repeat";
const char* Parser::ParenthesesUnmatched = "unmatched parentheses";
const char* Parser::ParenthesesTypeInvalid = "unrecognized character after (?";
const char* Parser::ParenthesesNotSupported = ""; // Not a user-visible syntax error -- just signals a syntax that WREC doesn't support yet.
const char* Parser::CharacterClassUnmatched = "missing terminating ] for character class";
const char* Parser::CharacterClassOutOfOrder = "range out of order in character class";
const char* Parser::EscapeUnterminated = "\\ at end of pattern";

class PatternCharacterSequence {
typedef Generator::JumpList JumpList;

public:
    PatternCharacterSequence(Generator& generator, JumpList& failures)
        : m_generator(generator)
        , m_failures(failures)
    {
    }
    
    size_t size() { return m_sequence.size(); }
    
    void append(int ch)
    {
        m_sequence.append(ch);
    }
    
    void flush()
    {
        if (!m_sequence.size())
            return;

        m_generator.generatePatternCharacterSequence(m_failures, m_sequence.begin(), m_sequence.size());
        m_sequence.clear();
    }

    void flush(const Quantifier& quantifier)
    {
        if (!m_sequence.size())
            return;

        m_generator.generatePatternCharacterSequence(m_failures, m_sequence.begin(), m_sequence.size() - 1);

        switch (quantifier.type) {
        case Quantifier::None:
        case Quantifier::Error:
            ASSERT_NOT_REACHED();
            break;

        case Quantifier::Greedy: {
            GeneratePatternCharacterFunctor functor(m_sequence.last());
            m_generator.generateGreedyQuantifier(m_failures, functor, quantifier.min, quantifier.max);
            break;
        }
        
        case Quantifier::NonGreedy: {
            GeneratePatternCharacterFunctor functor(m_sequence.last());
            m_generator.generateNonGreedyQuantifier(m_failures, functor, quantifier.min, quantifier.max);
            break;
        }
        }
        
        m_sequence.clear();
    }

private:
    Generator& m_generator;
    JumpList& m_failures;
    Vector<int, 8> m_sequence;
};

ALWAYS_INLINE Quantifier Parser::consumeGreedyQuantifier()
{
    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 '{': {
            SavedState state(*this);
            consume();

            // Accept: {n}, {n,}, {n,m}.
            // Reject: {n,m} where n > m.
            // Ignore: Anything else, such as {n, m}.

            if (!peekIsDigit()) {
                state.restore();
                return Quantifier();
            }

            unsigned min = consumeNumber();
            unsigned max = min;

            if (peek() == ',') {
                consume();
                max = peekIsDigit() ? consumeNumber() : Quantifier::Infinity;
            }

            if (peek() != '}') {
                state.restore();
                return Quantifier();
            }
            consume();
 
            if (min > max) {
                setError(QuantifierOutOfOrder);
                return Quantifier(Quantifier::Error);
            }

            return Quantifier(Quantifier::Greedy, min, max);
         }

         default:
            return Quantifier(); // No quantifier.
    }
}

Quantifier Parser::consumeQuantifier()
{
    Quantifier q = consumeGreedyQuantifier();
    
    if ((q.type == Quantifier::Greedy) && (peek() == '?')) {
        consume();
        q.type = Quantifier::NonGreedy;
    }
    
    return q;
}

bool Parser::parseCharacterClassQuantifier(JumpList& failures, const CharacterClass& charClass, bool invert)
{
    Quantifier q = consumeQuantifier();

    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 Parser::parseBackreferenceQuantifier(JumpList& failures, unsigned subpatternId)
{
    Quantifier q = consumeQuantifier();

    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 Parser::parseParentheses(JumpList& failures)
{
    ParenthesesType type = consumeParenthesesType();

    // FIXME: WREC originally failed to backtrack correctly in cases such as
    // "c".match(/(.*)c/). Now, most parentheses handling is disabled. For
    // unsupported parentheses, we fall back on PCRE.

    switch (type) {
        case Generator::Assertion: {
            m_generator.generateParenthesesAssertion(failures);

            if (consume() != ')') {
                setError(ParenthesesUnmatched);
                return false;
            }

            Quantifier quantifier = consumeQuantifier();
            if (quantifier.type != Quantifier::None && quantifier.min == 0) {
                setError(ParenthesesNotSupported);
                return false;
            }

            return true;
        }
        case Generator::InvertedAssertion: {
            m_generator.generateParenthesesInvertedAssertion(failures);

            if (consume() != ')') {
                setError(ParenthesesUnmatched);
                return false;
            }

            Quantifier quantifier = consumeQuantifier();
            if (quantifier.type != Quantifier::None && quantifier.min == 0) {
                setError(ParenthesesNotSupported);
                return false;
            }

            return true;
        }
        default:
            setError(ParenthesesNotSupported);
            return false;
    }
}

bool Parser::parseCharacterClass(JumpList& failures)
{
    bool invert = false;
    if (peek() == '^') {
        consume();
        invert = true;
    }

    CharacterClassConstructor constructor(m_ignoreCase);

    int ch;
    while ((ch = peek()) != ']') {
        switch (ch) {
        case EndOfPattern:
            setError(CharacterClassUnmatched);
            return false;

        case '\\': {
            consume();
            Escape escape = consumeEscape(true);

            switch (escape.type()) {
                case Escape::PatternCharacter: {
                    int character = PatternCharacterEscape::cast(escape).character();
                    if (character == '-')
                        constructor.flushBeforeEscapedHyphen();
                    constructor.put(character);
                    break;
                }
                case Escape::CharacterClass: {
                    const CharacterClassEscape& characterClassEscape = CharacterClassEscape::cast(escape);
                    ASSERT(!characterClassEscape.invert());
                    constructor.append(characterClassEscape.characterClass());
                    break;
                }
                case Escape::Error:
                    return false;
                case Escape::Backreference:
                case Escape::WordBoundaryAssertion: {
                    ASSERT_NOT_REACHED();
                    break;
                }
            }
            break;
        }

        default:
            consume();
            constructor.put(ch);