/*

 * Copyright (C) 2009 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. 

 */

#ifndef RegexParser_h

#define RegexParser_h

#if ENABLE(YARR)

#include <UString.h>

#include <limits.h>

#include <wtf/ASCIICType.h>

#include <wtf/unicode/Unicode.h>

namespace JSC { namespace Yarr {

enum BuiltInCharacterClassID {

    DigitClassID,

    SpaceClassID,

    WordClassID,

    NewlineClassID,

};

// The Parser class should not be used directly - only via the Yarr::parse() method.

template<class Delegate>

class Parser {

private:

    template<class FriendDelegate>

    friend const char* parse(FriendDelegate& delegate, const UString& pattern, unsigned backReferenceLimit);

    enum ErrorCode {

        NoError,

        PatternTooLarge,

        QuantifierOutOfOrder,

        QuantifierWithoutAtom,

        MissingParentheses,

        ParenthesesUnmatched,

        ParenthesesTypeInvalid,

        CharacterClassUnmatched,

        CharacterClassOutOfOrder,

        EscapeUnterminated,

        NumberOfErrorCodes

    };

    /*

     * CharacterClassParserDelegate:

     *

     * The class CharacterClassParserDelegate is used in the parsing of character

     * classes.  This class handles detection of character ranges.  This class

     * implements enough of the delegate interface such that it can be passed to

     * parseEscape() as an EscapeDelegate.  This allows parseEscape() to be reused

     * to perform the parsing of escape characters in character sets.

     */

    class CharacterClassParserDelegate {

    public:

        CharacterClassParserDelegate(Delegate& delegate, ErrorCode& err)

            : m_delegate(delegate)

            , m_err(err)

            , m_state(empty)

        {

        }

        /*

         * begin():

         *

         * Called at beginning of construction.

         */

        void begin(bool invert)

        {

            m_delegate.atomCharacterClassBegin(invert);

        }

        /*

         * atomPatternCharacterUnescaped():

         *

         * This method is called directly from parseCharacterClass(), to report a new

         * pattern character token.  This method differs from atomPatternCharacter(),

         * which will be called from parseEscape(), since a hypen provided via this

         * method may be indicating a character range, but a hyphen parsed by

         * parseEscape() cannot be interpreted as doing so.

         */

        void atomPatternCharacterUnescaped(UChar ch)

        {

            switch (m_state) {

            case empty:

                m_character = ch;

                m_state = cachedCharacter;

                break;

            case cachedCharacter:

                if (ch == '-')

                    m_state = cachedCharacterHyphen;

                else {

                    m_delegate.atomCharacterClassAtom(m_character);

                    m_character = ch;

                }

                break;

            case cachedCharacterHyphen:

                if (ch >= m_character)

                    m_delegate.atomCharacterClassRange(m_character, ch);

                else

                    m_err = CharacterClassOutOfOrder;

                m_state = empty;

            }

        }

        /*

         * atomPatternCharacter():

         *

         * Adds a pattern character, called by parseEscape(), as such will not

         * interpret a hyphen as indicating a character range.

         */

        void atomPatternCharacter(UChar ch)

        {

            // Flush if a character is already pending to prevent the

            // hyphen from begin interpreted as indicating a range.

            if((ch == '-') && (m_state == cachedCharacter))

                flush();

            atomPatternCharacterUnescaped(ch);

        }

        /*

         * atomBuiltInCharacterClass():

         *

         * Adds a built-in character class, called by parseEscape().

         */

        void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)

        {

            flush();

            m_delegate.atomCharacterClassBuiltIn(classID, invert);

        }

        /*

         * end():

         *

         * Called at end of construction.

         */

        void end()

        {

            flush();

            m_delegate.atomCharacterClassEnd();

        }

        // parseEscape() should never call these delegate methods when

        // invoked with inCharacterClass set.

        void assertionWordBoundary(bool) { ASSERT_NOT_REACHED(); }

        void atomBackReference(unsigned) { ASSERT_NOT_REACHED(); }

    private:

        void flush()

        {

            if (m_state != empty) // either cachedCharacter or cachedCharacterHyphen

                m_delegate.atomCharacterClassAtom(m_character);

            if (m_state == cachedCharacterHyphen)

                m_delegate.atomCharacterClassAtom('-');

            m_state = empty;

        }

        Delegate& m_delegate;

        ErrorCode& m_err;

        enum CharacterClassConstructionState {

            empty,

            cachedCharacter,

            cachedCharacterHyphen,

        } m_state;

        UChar m_character;

    };

    Parser(Delegate& delegate, const UString& pattern, unsigned backReferenceLimit)

        : m_delegate(delegate)

        , m_backReferenceLimit(backReferenceLimit)

        , m_err(NoError)

        , m_data(pattern.data())

        , m_size(pattern.size())

        , m_index(0)

        , m_parenthesesNestingDepth(0)

    {

    }

    /*

     * parseEscape():

     *

     * Helper for parseTokens() AND parseCharacterClass().

     * Unlike the other parser methods, this function does not report tokens

     * directly to the member delegate (m_delegate), instead tokens are

     * emitted to the delegate provided as an argument.  In the case of atom

     * escapes, parseTokens() will call parseEscape() passing m_delegate as

     * an argument, and as such the escape will be reported to the delegate.

     *

     * However this method may also be used by parseCharacterClass(), in which

     * case a CharacterClassParserDelegate will be passed as the delegate that

     * tokens should be added to.  A boolean flag is also provided to indicate

     * whether that an escape in a CharacterClass is being parsed (some parsing

     * rules change in this context).

     *

     * The boolean value returned by this method indicates whether the token

     * parsed was an atom (outside of a characted class \b and \B will be

     * interpreted as assertions).

     */

    template<bool inCharacterClass, class EscapeDelegate>

    bool parseEscape(EscapeDelegate& delegate)

    {

        ASSERT(!m_err);

        ASSERT(peek() == '\\');

        consume();

        if (atEndOfPattern()) {

            m_err = EscapeUnterminated;

            return false;

        }

        switch (peek()) {

        // Assertions

        case 'b':

            consume();

            if (inCharacterClass)

                delegate.atomPatternCharacter('\b');

            else {

                delegate.assertionWordBoundary(false);

                return false;

            }

            break;

        case 'B':

            consume();

            if (inCharacterClass)

                delegate.atomPatternCharacter('B');

            else {

                delegate.assertionWordBoundary(true);

                return false;

            }

            break;

        // CharacterClassEscape

        case 'd':

            consume();

            delegate.atomBuiltInCharacterClass(DigitClassID, false);

            break;

        case 's':

            consume();

            delegate.atomBuiltInCharacterClass(SpaceClassID, false);

            break;

        case 'w':

            consume();

            delegate.atomBuiltInCharacterClass(WordClassID, false);

            break;

        case 'D':

            consume();

            delegate.atomBuiltInCharacterClass(DigitClassID, true);

            break;

        case 'S':

            consume();

            delegate.atomBuiltInCharacterClass(SpaceClassID, true);

            break;

        case 'W':

            consume();

            delegate.atomBuiltInCharacterClass(WordClassID, true);

            break;

        // DecimalEscape

        case '1':

        case '2':

        case '3':

        case '4':

        case '5':

        case '6':

        case '7':

        case '8':

        case '9': {

            // To match Firefox, we parse an invalid backreference in the range [1-7] as an octal escape.

            // First, try to parse this as backreference.

            if (!inCharacterClass) {

                ParseState state = saveState();

                unsigned backReference = consumeNumber();

                if (backReference <= m_backReferenceLimit) {

                    delegate.atomBackReference(backReference);

                    break;

                }

                restoreState(state);

            }

            // Not a backreference, and not octal.

            if (peek() >= '8') {

                delegate.atomPatternCharacter('\\');

                break;

            }

            // Fall-through to handle this as an octal escape.

        }

        // Octal escape

        case '0':

            delegate.atomPatternCharacter(consumeOctal());

            break;

        // ControlEscape

        case 'f':

            consume();

            delegate.atomPatternCharacter('\f');

            break;

        case 'n':

            consume();

            delegate.atomPatternCharacter('\n');

            break;

        case 'r':

            consume();

            delegate.atomPatternCharacter('\r');

            break;

        case 't':

            consume();

            delegate.atomPatternCharacter('\t');

            break;

        case 'v':

            consume();

            delegate.atomPatternCharacter('\v');

            break;

        // ControlLetter

        case 'c': {

            ParseState state = saveState();

            consume();

            if (!atEndOfPattern()) {

                int control = consume();

                // To match Firefox, inside a character class, we also accept numbers and '_' as control characters.

                if (inCharacterClass ? WTF::isASCIIAlphanumeric(control) || (control == '_') : WTF::isASCIIAlpha(control)) {

                    delegate.atomPatternCharacter(control & 0x1f);

                    break;

                }

            }

            restoreState(state);

            delegate.atomPatternCharacter('\\');

            break;

        }

        // HexEscape

        case 'x': {

            consume();

            int x = tryConsumeHex(2);

            if (x == -1)

                delegate.atomPatternCharacter('x');

            else

                delegate.atomPatternCharacter(x);

            break;

        }

        // UnicodeEscape

        case 'u': {

            consume();

            int u = tryConsumeHex(4);

            if (u == -1)

                delegate.atomPatternCharacter('u');

            else

                delegate.atomPatternCharacter(u);

            break;

        }

        // IdentityEscape

        default:

            delegate.atomPatternCharacter(consume());

        }

        return true;

    }

    /*

     * parseAtomEscape(), parseCharacterClassEscape():

     *

     * These methods alias to parseEscape().

     */

    bool parseAtomEscape()

    {

        return parseEscape<false>(m_delegate);

    }

    void parseCharacterClassEscape(CharacterClassParserDelegate& delegate)

    {

        parseEscape<true>(delegate);

    }

    /*

     * parseCharacterClass():

     *

     * Helper for parseTokens(); calls dirctly and indirectly (via parseCharacterClassEscape)

     * to an instance of CharacterClassParserDelegate, to describe the character class to the

     * delegate.

     */

    void parseCharacterClass()

    {

        ASSERT(!m_err);

        ASSERT(peek() == '[');

        consume();

        CharacterClassParserDelegate characterClassConstructor(m_delegate, m_err);

        characterClassConstructor.begin(tryConsume('^'));

        while (!atEndOfPattern()) {

            switch (peek()) {

            case ']':

                consume();

                characterClassConstructor.end();

                return;

            case '\\':

                parseCharacterClassEscape(characterClassConstructor);

                break;

            default:

                characterClassConstructor.atomPatternCharacterUnescaped(consume());

            }

            if (m_err)

                return;

        }

        m_err = CharacterClassUnmatched;

    }

    /*

     * parseParenthesesBegin():

     *

     * Helper for parseTokens(); checks for parentheses types other than regular capturing subpatterns.

     */

    void parseParenthesesBegin()

    {

        ASSERT(!m_err);

        ASSERT(peek() == '(');

        consume();

        if (tryConsume('?')) {

            if (atEndOfPattern()) {

                m_err = ParenthesesTypeInvalid;

                return;

            }

            switch (consume()) {

            case ':':

                m_delegate.atomParenthesesSubpatternBegin(false);

                break;

            case '=':

                m_delegate.atomParentheticalAssertionBegin();

                break;

            case '!':

                m_delegate.atomParentheticalAssertionBegin(true);

                break;

            default:

                m_err = ParenthesesTypeInvalid;

            }

        } else

            m_delegate.atomParenthesesSubpatternBegin();

        ++m_parenthesesNestingDepth;

    }

    /*

     * parseParenthesesEnd():

     *

     * Helper for parseTokens(); checks for parse errors (due to unmatched parentheses).

     */

    void parseParenthesesEnd()

    {

        ASSERT(!m_err);

        ASSERT(peek() == ')');

        consume();

        if (m_parenthesesNestingDepth > 0)

            m_delegate.atomParenthesesEnd();

        else

            m_err = ParenthesesUnmatched;

        --m_parenthesesNestingDepth;

    }

    /*

     * parseQuantifier():

     *

     * Helper for parseTokens(); checks for parse errors and non-greedy quantifiers.

     */

    void parseQuantifier(bool lastTokenWasAnAtom, unsigned min, unsigned max)

    {

        ASSERT(!m_err);

        ASSERT(min <= max);

        if (lastTokenWasAnAtom)

            m_delegate.quantifyAtom(min, max, !tryConsume('?'));

        else

            m_err = QuantifierWithoutAtom;

    }

    /*

     * parseTokens():

     *

     * This method loops over the input pattern reporting tokens to the delegate.

     * The method returns when a parse error is detected, or the end of the pattern

     * is reached.  One piece of state is tracked around the loop, which is whether

     * the last token passed to the delegate was an atom (this is necessary to detect

     * a parse error when a quantifier provided without an atom to quantify).

     */

    void parseTokens()

    {

        bool lastTokenWasAnAtom = false;