/*

 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package jdk.nashorn.internal.runtime.regexp;

import java.util.HashMap;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.regex.PatternSyntaxException;

import jdk.nashorn.internal.parser.Lexer;

import jdk.nashorn.internal.parser.Scanner;

import jdk.nashorn.internal.runtime.BitVector;

/**

 * Scan a JavaScript regexp, converting to Java regex if necessary.

 *

 */

final class RegExpScanner extends Scanner {

    /**

     * String builder used to rewrite the pattern for the currently used regexp factory.

     */

    private final StringBuilder sb;

    /** Expected token table */

    private final Map<Character, Integer> expected = new HashMap<>();

    /** Capturing parenthesis that have been found so far. */

    private final List<Capture> caps = new LinkedList<>();

    /** Forward references to capturing parenthesis to be resolved later.*/

    private final LinkedList<Integer> forwardReferences = new LinkedList<>();

    /** Current level of zero-width negative lookahead assertions. */

    private int negativeLookaheadLevel;

    /** Are we currently inside a character class? */

    private boolean inCharClass = false;

    /** Are we currently inside a negated character class? */

    private boolean inNegativeClass = false;

    private static final String NON_IDENT_ESCAPES = "$^*+(){}[]|\\.?";

    private static class Capture {

        /**

         * Zero-width negative lookaheads enclosing the capture.

         */

        private final int negativeLookaheadLevel;

        Capture(final int negativeLookaheadLevel) {

            this.negativeLookaheadLevel = negativeLookaheadLevel;

        }

        public int getNegativeLookaheadLevel() {

            return negativeLookaheadLevel;

        }

    }

    /**

     * Constructor

     * @param string the JavaScript regexp to parse

     */

    private RegExpScanner(final String string) {

        super(string);

        sb = new StringBuilder(limit);

        reset(0);

        expected.put(']', 0);

        expected.put('}', 0);

    }

    private void processForwardReferences() {

        Iterator<Integer> iterator = forwardReferences.descendingIterator();

        while (iterator.hasNext()) {

            final int pos = iterator.next();

            final int num = iterator.next();

            if (num > caps.size()) {

                // Non-existing backreference. If the number begins with a valid octal convert it to

                // Unicode escape and append the rest to a literal character sequence.

                final StringBuilder buffer = new StringBuilder();

                octalOrLiteral(Integer.toString(num), buffer);

                sb.insert(pos, buffer);

            }

        }

        forwardReferences.clear();

    }

    /**

     * Scan a JavaScript regexp string returning a Java safe regex string.

     *

     * @param string

     *            JavaScript regexp string.

     * @return Java safe regex string.

     */

    public static RegExpScanner scan(final String string) {

        final RegExpScanner scanner = new RegExpScanner(string);

        try {

            scanner.disjunction();

        } catch (final Exception e) {

            throw new PatternSyntaxException(e.getMessage(), string, scanner.position);

        }

        scanner.processForwardReferences();

        // Throw syntax error unless we parsed the entire JavaScript regexp without syntax errors

        if (scanner.position != string.length()) {

            final String p = scanner.getStringBuilder().toString();

            throw new PatternSyntaxException(string, p, p.length() + 1);

        }

        return scanner;

    }

    final StringBuilder getStringBuilder() {

        return sb;

    }

    String getJavaPattern() {

        return sb.toString();

    }

    BitVector getGroupsInNegativeLookahead() {

        BitVector vec = null;

        for (int i = 0; i < caps.size(); i++) {

            final Capture cap = caps.get(i);

            if (cap.getNegativeLookaheadLevel() > 0) {

                if (vec == null) {

                    vec = new BitVector(caps.size() + 1);

                }

                vec.set(i + 1);

            }

        }

        return vec;

    }

    /**

     * Commit n characters to the builder and to a given token

     * @param n     Number of characters.

     * @return Committed token

     */

    private boolean commit(final int n) {

        switch (n) {

        case 1:

            sb.append(ch0);

            skip(1);

            break;

        case 2:

            sb.append(ch0);

            sb.append(ch1);

            skip(2);

            break;

        case 3:

            sb.append(ch0);

            sb.append(ch1);

            sb.append(ch2);

            skip(3);

            break;

        default:

            assert false : "Should not reach here";

        }

        return true;

    }

    /**

     * Restart the buffers back at an earlier position.

     *

     * @param startIn

     *            Position in the input stream.

     * @param startOut

     *            Position in the output stream.

     */

    private void restart(final int startIn, final int startOut) {

        reset(startIn);

        sb.setLength(startOut);

    }

    private void push(final char ch) {

        expected.put(ch, expected.get(ch) + 1);

    }

    private void pop(final char ch) {

        expected.put(ch, Math.min(0, expected.get(ch) - 1));

    }

    /*

     * Recursive descent tokenizer starts below.

     */

    /*

     * Disjunction ::

     *      Alternative

     *      Alternative | Disjunction

     */

    private void disjunction() {

        while (true) {

            alternative();

            if (ch0 == '|') {

                commit(1);

            } else {

                break;

            }

        }

    }

    /*

     * Alternative ::

     *      [empty]

     *      Alternative Term

     */

    private void alternative() {

        while (term()) {

            // do nothing

        }

    }

    /*

     * Term ::

     *      Assertion

     *      Atom

     *      Atom Quantifier

     */

    private boolean term() {

        final int startIn  = position;

        final int startOut = sb.length();

        if (assertion()) {

            return true;

        }

        if (atom()) {

            if (sb.toString().endsWith("[]")) {

            } else if (sb.toString().endsWith("[^]")) {

                sb.setLength(sb.length() - 2);

                sb.append("\\s\\S]");

            }

            return true;

        }

        restart(startIn, startOut);

        return false;

    }

    /*

     * Assertion ::

     *      ^

     *      $

     *      \b

     *      \B

     *      ( ? = Disjunction )

     *      ( ? ! Disjunction )

     */

    private boolean assertion() {

        final int startIn  = position;

        final int startOut = sb.length();

        switch (ch0) {

        case '^':

        case '$':

            return commit(1);

        case '\\':

            if (ch1 == 'b' || ch1 == 'B') {

                return commit(2);

            }

            break;

        case '(':

            if (ch1 != '?') {

                break;

            }

            if (ch2 != '=' && ch2 != '!') {

                break;

            }

            final boolean isNegativeLookahead = (ch2 == '!');

            commit(3);

            if (isNegativeLookahead) {

                negativeLookaheadLevel++;

            }

            disjunction();

            if (isNegativeLookahead) {

                negativeLookaheadLevel--;

            }

            if (ch0 == ')') {

                return commit(1);

            }

            break;

        default:

            break;

        }

        restart(startIn, startOut);

        return false;

    }

    /*

     * Quantifier ::

     *      QuantifierPrefix

     *      QuantifierPrefix ?

     */

    private boolean quantifier() {

        if (quantifierPrefix()) {

            if (ch0 == '?') {

                commit(1);

            }

            return true;

        }

        return false;

    }

    /*

     * QuantifierPrefix ::

     *      *

     *      +

     *      ?

     *      { DecimalDigits }

     *      { DecimalDigits , }

     *      { DecimalDigits , DecimalDigits }

     */

    private boolean quantifierPrefix() {

        final int startIn  = position;

        final int startOut = sb.length();

        switch (ch0) {

        case '*':

        case '+':

        case '?':

            return commit(1);

        case '{':

            commit(1);

            if (!decimalDigits()) {

                break; // not a quantifier - back out

            }

            push('}');

            if (ch0 == ',') {

                commit(1);

                decimalDigits();

            }

            if (ch0 == '}') {

                pop('}');

                commit(1);

            } else {

                // Bad quantifier should be rejected but is accepted by all major engines

                restart(startIn, startOut);

                return false;

            }

            return true;

        default:

            break;

        }

        restart(startIn, startOut);

        return false;

    }

    /*

     * Atom ::

     *      PatternCharacter

     *      .

     *      \ AtomEscape

     *      CharacterClass

     *      ( Disjunction )

     *      ( ? : Disjunction )

     *

     */

    private boolean atom() {

        final int startIn  = position;

        final int startOut = sb.length();

        if (patternCharacter()) {

            return true;

        }

        if (ch0 == '.') {

            return commit(1);

        }

        if (ch0 == '\\') {

            commit(1);

            if (atomEscape()) {

                return true;

            }

        }

        if (characterClass()) {

            return true;

        }

        if (ch0 == '(') {

            boolean capturingParens = true;

            commit(1);

            if (ch0 == '?' && ch1 == ':') {

                capturingParens = false;

                commit(2);

            }

            disjunction();

            if (ch0 == ')') {

                commit(1);

                if (capturingParens) {

                    caps.add(new Capture(negativeLookaheadLevel));

                }

                return true;

            }

        }

        restart(startIn, startOut);

        return false;

    }

    /*

     * PatternCharacter ::

     *      SourceCharacter but not any of: ^$\.*+?()[]{}|

     */

    @SuppressWarnings("fallthrough")

    private boolean patternCharacter() {

        if (atEOF()) {

            return false;

        }

        switch (ch0) {

        case '^':

        case '$':

        case '\\':

        case '.':

        case '*':

        case '+':

        case '?':

        case '(':

        case ')':

        case '[':

        case '|':

            return false;

        case '}':

        case ']':

            final int n = expected.get(ch0);

            if (n != 0) {

                return false;

            }

       case '{':

           // if not a valid quantifier escape curly brace to match itself

           // this ensures compatibility with other JS implementations

           if (!quantifierPrefix()) {

               sb.append('\\');

               return commit(1);

           }

           return false;

        default:

            return commit(1); // SOURCECHARACTER

        }

    }

    /*

     * AtomEscape ::

     *      DecimalEscape

     *      CharacterEscape

     *      CharacterClassEscape

     */

    private boolean atomEscape() {

        // Note that contrary to ES 5.1 spec we put identityEscape() last because it acts as a catch-all

        return decimalEscape() || characterClassEscape() || characterEscape() || identityEscape();

    }