/*

 * 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 "RegexJIT.h"

#include "ASCIICType.h"

#include "JSGlobalData.h"

#include "LinkBuffer.h"

#include "MacroAssembler.h"

#include "RegexCompiler.h"

#include "pcre.h" // temporary, remove when fallback is removed.

#if ENABLE(YARR_JIT)

using namespace WTF;

namespace JSC { namespace Yarr {

class RegexGenerator : private MacroAssembler {

    friend void jitCompileRegex(JSGlobalData* globalData, RegexCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);

#if CPU(ARM)

    static const RegisterID input = ARMRegisters::r0;

    static const RegisterID index = ARMRegisters::r1;

    static const RegisterID length = ARMRegisters::r2;

    static const RegisterID output = ARMRegisters::r4;

    static const RegisterID regT0 = ARMRegisters::r5;

    static const RegisterID regT1 = ARMRegisters::r6;

    static const RegisterID returnRegister = ARMRegisters::r0;

#elif CPU(MIPS)

    static const RegisterID input = MIPSRegisters::a0;

    static const RegisterID index = MIPSRegisters::a1;

    static const RegisterID length = MIPSRegisters::a2;

    static const RegisterID output = MIPSRegisters::a3;

    static const RegisterID regT0 = MIPSRegisters::t4;

    static const RegisterID regT1 = MIPSRegisters::t5;

    static const RegisterID returnRegister = MIPSRegisters::v0;

#elif CPU(X86)

    static const RegisterID input = X86Registers::eax;

    static const RegisterID index = X86Registers::edx;

    static const RegisterID length = X86Registers::ecx;

    static const RegisterID output = X86Registers::edi;

    static const RegisterID regT0 = X86Registers::ebx;

    static const RegisterID regT1 = X86Registers::esi;

    static const RegisterID returnRegister = X86Registers::eax;

#elif CPU(X86_64)

    static const RegisterID input = X86Registers::edi;

    static const RegisterID index = X86Registers::esi;

    static const RegisterID length = X86Registers::edx;

    static const RegisterID output = X86Registers::ecx;

    static const RegisterID regT0 = X86Registers::eax;

    static const RegisterID regT1 = X86Registers::ebx;

    static const RegisterID returnRegister = X86Registers::eax;

#endif

    void optimizeAlternative(PatternAlternative* alternative)

    {

        if (!alternative->m_terms.size())

            return;

        for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {

            PatternTerm& term = alternative->m_terms[i];

            PatternTerm& nextTerm = alternative->m_terms[i + 1];

            if ((term.type == PatternTerm::TypeCharacterClass)

                && (term.quantityType == QuantifierFixedCount)

                && (nextTerm.type == PatternTerm::TypePatternCharacter)

                && (nextTerm.quantityType == QuantifierFixedCount)) {

                PatternTerm termCopy = term;

                alternative->m_terms[i] = nextTerm;

                alternative->m_terms[i + 1] = termCopy;

            }

        }

    }

    void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)

    {

        do {

            // pick which range we're going to generate

            int which = count >> 1;

            char lo = ranges[which].begin;

            char hi = ranges[which].end;

            // check if there are any ranges or matches below lo.  If not, just jl to failure -

            // if there is anything else to check, check that first, if it falls through jmp to failure.

            if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {

                Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));

                // generate code for all ranges before this one

                if (which)

                    matchCharacterClassRange(character, 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));

                matchCharacterClassRange(character, 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)));

            // fall through to here, the value is above hi.

            // shuffle along & loop around if there are any more matches to handle.

            unsigned next = which + 1;

            ranges += next;

            count -= next;

        } while (count);

    }

    void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)

    {

        if (charClass->m_table) {

            ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table));

            matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry));   

            return;

        }

        Jump unicodeFail;

        if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {

            Jump isAscii = branch32(LessThanOrEqual, character, Imm32(0x7f));

            if (charClass->m_matchesUnicode.size()) {

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

                    UChar ch = charClass->m_matchesUnicode[i];

                    matchDest.append(branch32(Equal, character, Imm32(ch)));

                }

            }

            if (charClass->m_rangesUnicode.size()) {

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

                    UChar lo = charClass->m_rangesUnicode[i].begin;

                    UChar hi = charClass->m_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->m_ranges.size()) {

            unsigned matchIndex = 0;

            JumpList failures; 

            matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());

            while (matchIndex < charClass->m_matches.size())

                matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));

            failures.link(this);

        } else if (charClass->m_matches.size()) {

            // optimization: gather 'a','A' etc back together, can mask & test once.

            Vector<char> matchesAZaz;

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

                char ch = charClass->m_matches[i];

                if (m_pattern.m_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->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())

            unicodeFail.link(this);

    }

    // Jumps if input not available; will have (incorrectly) incremented already!

    Jump jumpIfNoAvailableInput(unsigned countToCheck)

    {

        add32(Imm32(countToCheck), index);

        return branch32(Above, index, length);

    }

    Jump jumpIfAvailableInput(unsigned countToCheck)

    {

        add32(Imm32(countToCheck), index);

        return branch32(BelowOrEqual, index, length);

    }

    Jump checkInput()

    {

        return branch32(BelowOrEqual, index, length);

    }

    Jump atEndOfInput()

    {

        return branch32(Equal, index, length);

    }

    Jump notAtEndOfInput()

    {

        return branch32(NotEqual, index, length);

    }

    Jump jumpIfCharEquals(UChar ch, int inputPosition)

    {

        return branch16(Equal, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));

    }

    Jump jumpIfCharNotEquals(UChar ch, int inputPosition)

    {

        return branch16(NotEqual, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));

    }

    void readCharacter(int inputPosition, RegisterID reg)

    {

        load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);

    }

    void storeToFrame(RegisterID reg, unsigned frameLocation)

    {

        poke(reg, frameLocation);

    }

    void storeToFrame(Imm32 imm, unsigned frameLocation)

    {

        poke(imm, frameLocation);

    }

    DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)

    {

        return storePtrWithPatch(ImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));

    }

    void loadFromFrame(unsigned frameLocation, RegisterID reg)

    {

        peek(reg, frameLocation);

    }

    void loadFromFrameAndJump(unsigned frameLocation)

    {

        jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));

    }

    struct AlternativeBacktrackRecord {

        DataLabelPtr dataLabel;

        Label backtrackLocation;

        AlternativeBacktrackRecord(DataLabelPtr dataLabel, Label backtrackLocation)

            : dataLabel(dataLabel)

            , backtrackLocation(backtrackLocation)

        {

        }

    };

    struct TermGenerationState {

        TermGenerationState(PatternDisjunction* disjunction, unsigned checkedTotal)

            : disjunction(disjunction)

            , checkedTotal(checkedTotal)

        {

        }

        void resetAlternative()

        {

            isBackTrackGenerated = false;

            alt = 0;

        }

        bool alternativeValid()

        {

            return alt < disjunction->m_alternatives.size();

        }

        void nextAlternative()

        {

            ++alt;

        }

        PatternAlternative* alternative()

        {

            return disjunction->m_alternatives[alt];

        }

        void resetTerm()

        {

            ASSERT(alternativeValid());

            t = 0;

        }

        bool termValid()

        {

            ASSERT(alternativeValid());

            return t < alternative()->m_terms.size();

        }

        void nextTerm()

        {

            ASSERT(alternativeValid());

            ++t;

        }

        PatternTerm& term()

        {

            ASSERT(alternativeValid());

            return alternative()->m_terms[t];

        }

        bool isLastTerm()

        {

            ASSERT(alternativeValid());

            return (t + 1) == alternative()->m_terms.size();

        }

        bool isMainDisjunction()

        {

            return !disjunction->m_parent;

        }

        PatternTerm& lookaheadTerm()

        {

            ASSERT(alternativeValid());

            ASSERT((t + 1) < alternative()->m_terms.size());

            return alternative()->m_terms[t + 1];

        }

        bool isSinglePatternCharacterLookaheadTerm()

        {

            ASSERT(alternativeValid());

            return ((t + 1) < alternative()->m_terms.size())

                && (lookaheadTerm().type == PatternTerm::TypePatternCharacter)

                && (lookaheadTerm().quantityType == QuantifierFixedCount)

                && (lookaheadTerm().quantityCount == 1);

        }

        int inputOffset()

        {

            return term().inputPosition - checkedTotal;

        }

        void jumpToBacktrack(Jump jump, MacroAssembler* masm)

        {

            if (isBackTrackGenerated)

                jump.linkTo(backtrackLabel, masm);

            else

                backTrackJumps.append(jump);

        }

        void jumpToBacktrack(JumpList& jumps, MacroAssembler* masm)

        {

            if (isBackTrackGenerated)

                jumps.linkTo(backtrackLabel, masm);

            else

                backTrackJumps.append(jumps);

        }

        bool plantJumpToBacktrackIfExists(MacroAssembler* masm)

        {

            if (isBackTrackGenerated) {

                masm->jump(backtrackLabel);

                return true;

            }

            return false;

        }

        void addBacktrackJump(Jump jump)

        {

            backTrackJumps.append(jump);

        }

        void setBacktrackGenerated(Label label)

        {

            isBackTrackGenerated = true;

            backtrackLabel = label;

        }

        void linkAlternativeBacktracks(MacroAssembler* masm)

        {

            isBackTrackGenerated = false;

            backTrackJumps.link(masm);

        }

        void linkAlternativeBacktracksTo(Label label, MacroAssembler* masm)

        {

            isBackTrackGenerated = false;

            backTrackJumps.linkTo(label, masm);

        }

        void propagateBacktrackingFrom(TermGenerationState& nestedParenthesesState, MacroAssembler* masm)

        {

            jumpToBacktrack(nestedParenthesesState.backTrackJumps, masm);

            if (nestedParenthesesState.isBackTrackGenerated)

                setBacktrackGenerated(nestedParenthesesState.backtrackLabel);

        }

        PatternDisjunction* disjunction;

        int checkedTotal;

    private:

        unsigned alt;

        unsigned t;

        JumpList backTrackJumps;

        Label backtrackLabel;

        bool isBackTrackGenerated;

    };

    void generateAssertionBOL(TermGenerationState& state)

    {

        PatternTerm& term = state.term();

        if (m_pattern.m_multiline) {

            const RegisterID character = regT0;

            JumpList matchDest;

            if (!term.inputPosition)

                matchDest.append(branch32(Equal, index, Imm32(state.checkedTotal)));

            readCharacter(state.inputOffset() - 1, character);

            matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());

            state.jumpToBacktrack(jump(), this);

            matchDest.link(this);

        } else {

            // Erk, really should poison out these alternatives early. :-/

            if (term.inputPosition)

                state.jumpToBacktrack(jump(), this);

            else

                state.jumpToBacktrack(branch32(NotEqual, index, Imm32(state.checkedTotal)), this);

        }

    }

    void generateAssertionEOL(TermGenerationState& state)

    {

        PatternTerm& term = state.term();

        if (m_pattern.m_multiline) {

            const RegisterID character = regT0;

            JumpList matchDest;

            if (term.inputPosition == state.checkedTotal)

                matchDest.append(atEndOfInput());

            readCharacter(state.inputOffset(), character);

            matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());

            state.jumpToBacktrack(jump(), this);

            matchDest.link(this);

        } else {

            if (term.inputPosition == state.checkedTotal)

                state.jumpToBacktrack(notAtEndOfInput(), this);

            // Erk, really should poison out these alternatives early. :-/

            else

                state.jumpToBacktrack(jump(), this);

        }

    }

    // Also falls though on nextIsNotWordChar.

    void matchAssertionWordchar(TermGenerationState& state, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)

    {

        const RegisterID character = regT0;

        PatternTerm& term = state.term();

        if (term.inputPosition == state.checkedTotal)

            nextIsNotWordChar.append(atEndOfInput());

        readCharacter(state.inputOffset(), character);

        matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());

    }

    void generateAssertionWordBoundary(TermGenerationState& state)

    {

        const RegisterID character = regT0;

        PatternTerm& term = state.term();

        Jump atBegin;

        JumpList matchDest;

        if (!term.inputPosition)

            atBegin = branch32(Equal, index, Imm32(state.checkedTotal));

        readCharacter(state.inputOffset() - 1, character);

        matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());

        if (!term.inputPosition)

            atBegin.link(this);

        // We fall through to here if the last character was not a wordchar.

        JumpList nonWordCharThenWordChar;

        JumpList nonWordCharThenNonWordChar;

        if (term.invertOrCapture) {

            matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);

            nonWordCharThenWordChar.append(jump());

        } else {

            matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);

            nonWordCharThenNonWordChar.append(jump());

        }

        state.jumpToBacktrack(nonWordCharThenNonWordChar, this);

        // We jump here if the last character was a wordchar.

        matchDest.link(this);

        JumpList wordCharThenWordChar;

        JumpList wordCharThenNonWordChar;