/*

 * 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.

 */

#include "config.h"

#include "RegexInterpreter.h"

#include "RegexCompiler.h"

#include "RegexPattern.h"

#ifndef NDEBUG

#include <stdio.h>

#endif

#if ENABLE(YARR)

using namespace WTF;

namespace JSC { namespace Yarr {

class Interpreter {

public:

    struct ParenthesesDisjunctionContext;

    struct BackTrackInfoPatternCharacter {

        uintptr_t matchAmount;

    };

    struct BackTrackInfoCharacterClass {

        uintptr_t matchAmount;

    };

    struct BackTrackInfoBackReference {

        uintptr_t begin; // Not really needed for greedy quantifiers.

        uintptr_t matchAmount; // Not really needed for fixed quantifiers.

    };

    struct BackTrackInfoAlternative {

        uintptr_t offset;

    };

    struct BackTrackInfoParentheticalAssertion {

        uintptr_t begin;

    };

    struct BackTrackInfoParenthesesOnce {

        uintptr_t inParentheses;

    };

    struct BackTrackInfoParentheses {

        uintptr_t matchAmount;

        ParenthesesDisjunctionContext* lastContext;

        uintptr_t prevBegin;

        uintptr_t prevEnd;

    };

    static inline void appendParenthesesDisjunctionContext(BackTrackInfoParentheses* backTrack, ParenthesesDisjunctionContext* context)

    {

        context->next = backTrack->lastContext;

        backTrack->lastContext = context;

        ++backTrack->matchAmount;

    }

    static inline void popParenthesesDisjunctionContext(BackTrackInfoParentheses* backTrack)

    {

        ASSERT(backTrack->matchAmount);

        ASSERT(backTrack->lastContext);

        backTrack->lastContext = backTrack->lastContext->next;

        --backTrack->matchAmount;

    }

    struct DisjunctionContext

    {

        DisjunctionContext()

            : term(0)

        {

        }

        void* operator new(size_t, void* where)

        {

            return where;

        }

        int term;

        unsigned matchBegin;

        unsigned matchEnd;

        uintptr_t frame[1];

    };

    DisjunctionContext* allocDisjunctionContext(ByteDisjunction* disjunction)

    {

        return new(malloc(sizeof(DisjunctionContext) + (disjunction->m_frameSize - 1) * sizeof(uintptr_t))) DisjunctionContext();

    }

    void freeDisjunctionContext(DisjunctionContext* context)

    {

        free(context);

    }

    struct ParenthesesDisjunctionContext

    {

        ParenthesesDisjunctionContext(int* output, ByteTerm& term)

            : next(0)

        {

            unsigned firstSubpatternId = term.atom.subpatternId;

            unsigned numNestedSubpatterns = term.atom.parenthesesDisjunction->m_numSubpatterns;

            for (unsigned i = 0; i < (numNestedSubpatterns << 1); ++i) {

                subpatternBackup[i] = output[(firstSubpatternId << 1) + i];

                output[(firstSubpatternId << 1) + i] = -1;

            }

            new(getDisjunctionContext(term)) DisjunctionContext();

        }

        void* operator new(size_t, void* where)

        {

            return where;

        }

        void restoreOutput(int* output, unsigned firstSubpatternId, unsigned numNestedSubpatterns)

        {

            for (unsigned i = 0; i < (numNestedSubpatterns << 1); ++i)

                output[(firstSubpatternId << 1) + i] = subpatternBackup[i];

        }

        DisjunctionContext* getDisjunctionContext(ByteTerm& term)

        {

            return reinterpret_cast<DisjunctionContext*>(&(subpatternBackup[term.atom.parenthesesDisjunction->m_numSubpatterns << 1]));

        }

        ParenthesesDisjunctionContext* next;

        int subpatternBackup[1];

    };

    ParenthesesDisjunctionContext* allocParenthesesDisjunctionContext(ByteDisjunction* disjunction, int* output, ByteTerm& term)

    {

        return new(malloc(sizeof(ParenthesesDisjunctionContext) + (((term.atom.parenthesesDisjunction->m_numSubpatterns << 1) - 1) * sizeof(int)) + sizeof(DisjunctionContext) + (disjunction->m_frameSize - 1) * sizeof(uintptr_t))) ParenthesesDisjunctionContext(output, term);

    }

    void freeParenthesesDisjunctionContext(ParenthesesDisjunctionContext* context)

    {

        free(context);

    }

    class InputStream {

    public:

        InputStream(const UChar* input, unsigned start, unsigned length)

            : input(input)

            , pos(start)

            , length(length)

        {

        }

        void next()

        {

            ++pos;

        }

        void rewind(unsigned amount)

        {

            ASSERT(pos >= amount);

            pos -= amount;

        }

        int read()

        {

            ASSERT(pos < length);

            if (pos < length)

                return input[pos];

            return -1;

        }

        int readChecked(int position)

        {

            ASSERT(position < 0);

            ASSERT((unsigned)-position <= pos);

            unsigned p = pos + position;

            ASSERT(p < length);

            return input[p];

        }

        int reread(unsigned from)

        {

            ASSERT(from < length);

            return input[from];

        }

        int prev()

        {

            ASSERT(!(pos > length));

            if (pos && length)

                return input[pos - 1];

            return -1;

        }

        unsigned getPos()

        {

            return pos;

        }

        void setPos(unsigned p)

        {

            pos = p;

        }

        bool atStart()

        {

            return pos == 0;

        }

        bool atEnd()

        {

            return pos == length;

        }

        bool checkInput(int count)

        {

            if ((pos + count) <= length) {

                pos += count;

                return true;

            } else

                return false;

        }

        void uncheckInput(int count)

        {

            pos -= count;

        }

        bool atStart(int position)

        {

            return (pos + position) == 0;

        }

        bool atEnd(int position)

        {

            return (pos + position) == length;

        }

    private:

        const UChar* input;

        unsigned pos;

        unsigned length;

    };

    bool testCharacterClass(CharacterClass* characterClass, int ch)

    {

        if (ch & 0xFF80) {

            for (unsigned i = 0; i < characterClass->m_matchesUnicode.size(); ++i)

                if (ch == characterClass->m_matchesUnicode[i])

                    return true;

            for (unsigned i = 0; i < characterClass->m_rangesUnicode.size(); ++i)

                if ((ch >= characterClass->m_rangesUnicode[i].begin) && (ch <= characterClass->m_rangesUnicode[i].end))

                    return true;

        } else {

            for (unsigned i = 0; i < characterClass->m_matches.size(); ++i)

                if (ch == characterClass->m_matches[i])

                    return true;

            for (unsigned i = 0; i < characterClass->m_ranges.size(); ++i)

                if ((ch >= characterClass->m_ranges[i].begin) && (ch <= characterClass->m_ranges[i].end))

                    return true;

        }

        return false;

    }

    bool checkCharacter(int testChar, int inputPosition)

    {

        return testChar == input.readChecked(inputPosition);

    }

    bool checkCasedCharacter(int loChar, int hiChar, int inputPosition)

    {

        int ch = input.readChecked(inputPosition);

        return (loChar == ch) || (hiChar == ch);

    }

    bool checkCharacterClass(CharacterClass* characterClass, bool invert, int inputPosition)

    {

        bool match = testCharacterClass(characterClass, input.readChecked(inputPosition));

        return invert ? !match : match;

    }

    bool tryConsumeBackReference(int matchBegin, int matchEnd, int inputOffset)

    {

        int matchSize = matchEnd - matchBegin;

        if (!input.checkInput(matchSize))

            return false;

        for (int i = 0; i < matchSize; ++i) {

            if (!checkCharacter(input.reread(matchBegin + i), inputOffset - matchSize + i)) {

                input.uncheckInput(matchSize);

                return false;

            }

        }

        return true;

    }

    bool matchAssertionBOL(ByteTerm& term)

    {

        return (input.atStart(term.inputPosition)) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.readChecked(term.inputPosition - 1)));

    }

    bool matchAssertionEOL(ByteTerm& term)

    {

        if (term.inputPosition)

            return (input.atEnd(term.inputPosition)) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.readChecked(term.inputPosition)));

        else

            return (input.atEnd()) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.read()));

    }

    bool matchAssertionWordBoundary(ByteTerm& term)

    {

        bool prevIsWordchar = !input.atStart(term.inputPosition) && testCharacterClass(pattern->wordcharCharacterClass, input.readChecked(term.inputPosition - 1));

        bool readIsWordchar;

        if (term.inputPosition)

            readIsWordchar = !input.atEnd(term.inputPosition) && testCharacterClass(pattern->wordcharCharacterClass, input.readChecked(term.inputPosition));

        else

            readIsWordchar = !input.atEnd() && testCharacterClass(pattern->wordcharCharacterClass, input.read());

        bool wordBoundary = prevIsWordchar != readIsWordchar;

        return term.invert() ? !wordBoundary : wordBoundary;

    }

    bool backtrackPatternCharacter(ByteTerm& term, DisjunctionContext* context)

    {

        BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);

        switch (term.atom.quantityType) {

        case QuantifierFixedCount:

            break;

        case QuantifierGreedy:

            if (backTrack->matchAmount) {

                --backTrack->matchAmount;

                input.uncheckInput(1);

                return true;

            }

            break;

        case QuantifierNonGreedy:

            if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {

                ++backTrack->matchAmount;

                if (checkCharacter(term.atom.patternCharacter, term.inputPosition - 1))

                    return true;

            }

            input.uncheckInput(backTrack->matchAmount);

            break;

        }

        return false;

    }

    bool backtrackPatternCasedCharacter(ByteTerm& term, DisjunctionContext* context)

    {

        BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);

        switch (term.atom.quantityType) {

        case QuantifierFixedCount:

            break;

        case QuantifierGreedy:

            if (backTrack->matchAmount) {

                --backTrack->matchAmount;

                input.uncheckInput(1);

                return true;

            }

            break;

        case QuantifierNonGreedy:

            if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {

                ++backTrack->matchAmount;

                if (checkCasedCharacter(term.atom.casedCharacter.lo, term.atom.casedCharacter.hi, term.inputPosition - 1))

                    return true;

            }

            input.uncheckInput(backTrack->matchAmount);

            break;

        }

        return false;

    }

    bool matchCharacterClass(ByteTerm& term, DisjunctionContext* context)

    {

        ASSERT(term.type == ByteTerm::TypeCharacterClass);

        BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);

        switch (term.atom.quantityType) {

        case QuantifierFixedCount: {

            for (unsigned matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {

                if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition + matchAmount))

                    return false;

            }

            return true;

        }

        case QuantifierGreedy: {

            unsigned matchAmount = 0;

            while ((matchAmount < term.atom.quantityCount) && input.checkInput(1)) {

                if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition - 1)) {

                    input.uncheckInput(1);

                    break;

                }

                ++matchAmount;

            }

            backTrack->matchAmount = matchAmount;

            return true;

        }

        case QuantifierNonGreedy:

            backTrack->matchAmount = 0;

            return true;

        }

        ASSERT_NOT_REACHED();

        return false;

    }

    bool backtrackCharacterClass(ByteTerm& term, DisjunctionContext* context)

    {

        ASSERT(term.type == ByteTerm::TypeCharacterClass);

        BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);

        switch (term.atom.quantityType) {

        case QuantifierFixedCount:

            break;

        case QuantifierGreedy:

            if (backTrack->matchAmount) {

                --backTrack->matchAmount;

                input.uncheckInput(1);

                return true;

            }

            break;

        case QuantifierNonGreedy:

            if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {

                ++backTrack->matchAmount;

                if (checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition - 1))

                    return true;

            }

            input.uncheckInput(backTrack->matchAmount);

            break;

        }

        return false;

    }

    bool matchBackReference(ByteTerm& term, DisjunctionContext* context)

    {

        ASSERT(term.type == ByteTerm::TypeBackReference);

        BackTrackInfoBackReference* backTrack = reinterpret_cast<BackTrackInfoBackReference*>(context->frame + term.frameLocation);

        int matchBegin = output[(term.atom.subpatternId << 1)];

        int matchEnd = output[(term.atom.subpatternId << 1) + 1];

        ASSERT((matchBegin == -1) == (matchEnd == -1));

        ASSERT(matchBegin <= matchEnd);

        if (matchBegin == matchEnd)

            return true;

        switch (term.atom.quantityType) {

        case QuantifierFixedCount: {

            backTrack->begin = input.getPos();

            for (unsigned matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {

                if (!tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {

                    input.setPos(backTrack->begin);

                    return false;

                }

            }

            return true;

        }

        case QuantifierGreedy: {

            unsigned matchAmount = 0;

            while ((matchAmount < term.atom.quantityCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition))

                ++matchAmount;

            backTrack->matchAmount = matchAmount;

            return true;

        }

        case QuantifierNonGreedy:

            backTrack->begin = input.getPos();

            backTrack->matchAmount = 0;

            return true;

        }

        ASSERT_NOT_REACHED();

        return false;

    }

    bool backtrackBackReference(ByteTerm& term, DisjunctionContext* context)

    {

        ASSERT(term.type == ByteTerm::TypeBackReference);

        BackTrackInfoBackReference* backTrack = reinterpret_cast<BackTrackInfoBackReference*>(context->frame + term.frameLocation);

        int matchBegin = output[(term.atom.subpatternId << 1)];

        int matchEnd = output[(term.atom.subpatternId << 1) + 1];

        ASSERT((matchBegin == -1) == (matchEnd == -1));

        ASSERT(matchBegin <= matchEnd);

        if (matchBegin == matchEnd)

            return false;

        switch (term.atom.quantityType) {

        case QuantifierFixedCount:

            // for quantityCount == 1, could rewind.

            input.setPos(backTrack->begin);

            break;