/*

 * Copyright (c) 2003, 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 build.tools.generatebreakiteratordata;

import java.io.*;

import java.util.Enumeration;

import java.util.Hashtable;

import java.util.Stack;

import java.util.Vector;

import java.util.zip.CRC32;

import sun.text.CompactByteArray;

/**

 * This class has the job of constructing a RuleBasedBreakIterator from a

 * textual description. A Builder is constructed by GenerateBreakIteratorData,

 * which uses it to construct the iterator itself and then throws it away.

 * <p>The construction logic is separated out into its own class for two primary

 * reasons:

 * <ul>

 * <li>The construction logic is quite sophisticated and large. Separating

 * it out into its own class means the code must only be loaded into memory

 * while a RuleBasedBreakIterator is being constructed, and can be purged after

 * that.

 * <li>There is a fair amount of state that must be maintained throughout the

 * construction process that is not needed by the iterator after construction.

 * Separating this state out into another class prevents all of the functions

 * that construct the iterator from having to have really long parameter lists,

 * (hopefully) contributing to readability and maintainability.

 * </ul>

 * <p>

 * It'd be really nice if this could be an independent class rather than an

 * inner class, because that would shorten the source file considerably, but

 * making Builder an inner class of RuleBasedBreakIterator allows it direct

 * access to RuleBasedBreakIterator's private members, which saves us from

 * having to provide some kind of "back door" to the Builder class that could

 * then also be used by other classes.

 */

class RuleBasedBreakIteratorBuilder {

    /**

     * A token used as a character-category value to identify ignore characters

     */

    protected static final byte IGNORE = -1;

    /**

     * Tables that indexes from character values to character category numbers

     */

    private CompactByteArray charCategoryTable = null;

    private SupplementaryCharacterData supplementaryCharCategoryTable = null;

    /**

     * The table of state transitions used for forward iteration

     */

    private short[] stateTable = null;

    /**

     * The table of state transitions used to sync up the iterator with the

     * text in backwards and random-access iteration

     */

    private short[] backwardsStateTable = null;

    /**

     * A list of flags indicating which states in the state table are accepting

     * ("end") states

     */

    private boolean[] endStates = null;

    /**

     * A list of flags indicating which states in the state table are

     * lookahead states (states which turn lookahead on and off)

     */

    private boolean[] lookaheadStates = null;

    /**

     * A table for additional data. May be used by a subclass of

     * RuleBasedBreakIterator.

     */

    private byte[] additionalData = null;

    /**

     * The number of character categories (and, thus, the number of columns in

     * the state tables)

     */

    private int numCategories;

    /**

     * A temporary holding place used for calculating the character categories.

     * This object contains CharSet objects.

     */

    protected Vector<CharSet> categories = null;

    /**

     * A table used to map parts of regexp text to lists of character

     * categories, rather than having to figure them out from scratch each time

     */

    protected Hashtable<String, Object> expressions = null;

    /**

     * A temporary holding place for the list of ignore characters

     */

    protected CharSet ignoreChars = null;

    /**

     * A temporary holding place where the forward state table is built

     */

    protected Vector<short[]> tempStateTable = null;

    /**

     * A list of all the states that have to be filled in with transitions to

     * the next state that is created.  Used when building the state table from

     * the regular expressions.

     */

    protected Vector<Integer> decisionPointList = null;

    /**

     * A stack for holding decision point lists.  This is used to handle nested

     * parentheses and braces in regexps.

     */

    protected Stack<Vector<Integer>> decisionPointStack = null;

    /**

     * A list of states that loop back on themselves.  Used to handle .*?

     */

    protected Vector<Integer> loopingStates = null;

    /**

     * Looping states actually have to be backfilled later in the process

     * than everything else.  This is where a the list of states to backfill

     * is accumulated.  This is also used to handle .*?

     */

    protected Vector<Integer> statesToBackfill = null;

    /**

     * A list mapping pairs of state numbers for states that are to be combined

     * to the state number of the state representing their combination.  Used

     * in the process of making the state table deterministic to prevent

     * infinite recursion.

     */

    protected Vector<int[]> mergeList = null;

    /**

     * A flag that is used to indicate when the list of looping states can

     * be reset.

     */

    protected boolean clearLoopingStates = false;

    /**

     * A bit mask used to indicate a bit in the table's flags column that marks

     * a state as an accepting state.

     */

    protected static final int END_STATE_FLAG = 0x8000;

    /**

     * A bit mask used to indicate a bit in the table's flags column that marks

     * a state as one the builder shouldn't loop to any looping states

     */

    protected static final int DONT_LOOP_FLAG = 0x4000;

    /**

     * A bit mask used to indicate a bit in the table's flags column that marks

     * a state as a lookahead state.

     */

    protected static final int LOOKAHEAD_STATE_FLAG = 0x2000;

    /**

     * A bit mask representing the union of the mask values listed above.

     * Used for clearing or masking off the flag bits.

     */

    protected static final int ALL_FLAGS = END_STATE_FLAG

                                         | LOOKAHEAD_STATE_FLAG

                                         | DONT_LOOP_FLAG;

    /**

     * This is the main function for setting up the BreakIterator's tables. It

     * just vectors different parts of the job off to other functions.

     */

    public RuleBasedBreakIteratorBuilder(String description) {

        Vector<String> tempRuleList = buildRuleList(description);

        buildCharCategories(tempRuleList);

        buildStateTable(tempRuleList);

        buildBackwardsStateTable(tempRuleList);

    }

    /**

     * Thus function has three main purposes:

     * <ul><li>Perform general syntax checking on the description, so the rest

     * of the build code can assume that it's parsing a legal description.

     * <li>Split the description into separate rules

     * <li>Perform variable-name substitutions (so that no one else sees

     * variable names)

     * </ul>

     */

    private Vector<String> buildRuleList(String description) {

        // invariants:

        // - parentheses must be balanced: ()[]{}<>

        // - nothing can be nested inside <>

        // - nothing can be nested inside [] except more []s

        // - pairs of ()[]{}<> must not be empty

        // - ; can only occur at the outer level

        // - | can only appear inside ()

        // - only one = or / can occur in a single rule

        // - = and / cannot both occur in the same rule

        // - <> can only occur on the left side of a = expression

        //   (because we'll perform substitutions to eliminate them other places)

        // - the left-hand side of a = expression can only be a single character

        //   (possibly with \) or text inside <>

        // - the right-hand side of a = expression must be enclosed in [] or ()

        // - * may not occur at the beginning of a rule, nor may it follow

        //   =, /, (, (, |, }, ;, or *

        // - ? may only follow *

        // - the rule list must contain at least one / rule

        // - no rule may be empty

        // - all printing characters in the ASCII range except letters and digits

        //   are reserved and must be preceded by \

        // - ! may only occur at the beginning of a rule

        // set up a vector to contain the broken-up description (each entry in the

        // vector is a separate rule) and a stack for keeping track of opening

        // punctuation

        Vector<String> tempRuleList = new Vector<>();

        Stack<Character> parenStack = new Stack<>();

        int p = 0;

        int ruleStart = 0;

        int c = '\u0000';

        int lastC = '\u0000';

        int lastOpen = '\u0000';

        boolean haveEquals = false;

        boolean havePipe = false;

        boolean sawVarName = false;

        final String charsThatCantPrecedeAsterisk = "=/{(|}*;\u0000";

        // if the description doesn't end with a semicolon, tack a semicolon onto the end

        if (description.length() != 0 &&

            description.codePointAt(description.length() - 1) != ';') {

            description = description + ";";

        }

        // for each character, do...

        while (p < description.length()) {

            c = description.codePointAt(p);

            switch (c) {

                // if the character is a backslash, skip the character that follows it

                // (it'll get treated as a literal character)

                case '\\':

                    ++p;

                    break;

                // if the character is opening punctuation, verify that no nesting

                // rules are broken, and push the character onto the stack

                case '{':

                case '<':

                case '[':

                case '(':

                    if (lastOpen == '<') {

                        error("Can't nest brackets inside <>", p, description);

                    }

                    if (lastOpen == '[' && c != '[') {

                        error("Can't nest anything in [] but []", p, description);

                    }

                    // if we see < anywhere except on the left-hand side of =,

                    // we must be seeing a variable name that was never defined

                    if (c == '<' && (haveEquals || havePipe)) {

                        error("Unknown variable name", p, description);

                    }

                    lastOpen = c;

                    parenStack.push(new Character((char)c));

                    if (c == '<') {

                        sawVarName = true;

                    }

                    break;

                // if the character is closing punctuation, verify that it matches the

                // last opening punctuation we saw, and that the brackets contain

                // something, then pop the stack

                case '}':

                case '>':

                case ']':

                case ')':

                    char expectedClose = '\u0000';

                    switch (lastOpen) {

                        case '{':

                            expectedClose = '}';

                            break;

                        case '[':

                            expectedClose = ']';

                            break;

                        case '(':

                            expectedClose = ')';

                            break;

                        case '<':

                            expectedClose = '>';

                            break;

                    }

                    if (c != expectedClose) {

                        error("Unbalanced parentheses", p, description);

                    }

                    if (lastC == lastOpen) {

                        error("Parens don't contain anything", p, description);

                    }

                    parenStack.pop();

                    if (!parenStack.empty()) {

                        lastOpen = parenStack.peek().charValue();

                    }

                    else {

                        lastOpen = '\u0000';

                    }

                    break;

                // if the character is an asterisk, make sure it occurs in a place

                // where an asterisk can legally go

                case '*':

                    if (charsThatCantPrecedeAsterisk.indexOf(lastC) != -1) {

                        error("Misplaced asterisk", p, description);

                    }

                    break;

                // if the character is a question mark, make sure it follows an asterisk

                case '?':

                    if (lastC != '*') {

                        error("Misplaced ?", p, description);

                    }

                    break;

                // if the character is an equals sign, make sure we haven't seen another

                // equals sign or a slash yet

                case '=':

                    if (haveEquals || havePipe) {

                        error("More than one = or / in rule", p, description);

                    }

                    haveEquals = true;

                    break;

                // if the character is a slash, make sure we haven't seen another slash

                // or an equals sign yet

                case '/':

                    if (haveEquals || havePipe) {

                        error("More than one = or / in rule", p, description);

                    }

                    if (sawVarName) {

                        error("Unknown variable name", p, description);

                    }

                    havePipe = true;

                    break;

                // if the character is an exclamation point, make sure it occurs only

                // at the beginning of a rule

                case '!':

                    if (lastC != ';' && lastC != '\u0000') {

                        error("! can only occur at the beginning of a rule", p, description);

                    }

                    break;

                // we don't have to do anything special on a period

                case '.':

                    break;

                // if the character is a syntax character that can only occur

                // inside [], make sure that it does in fact only occur inside [].

                case '^':

                case '-':

                case ':':

                    if (lastOpen != '[' && lastOpen != '<') {

                        error("Illegal character", p, description);

                    }

                    break;

                // if the character is a semicolon, do the following...

                case ';':

                    // make sure the rule contains something and that there are no

                    // unbalanced parentheses or brackets

                    if (lastC == ';' || lastC == '\u0000') {

                        error("Empty rule", p, description);

                    }

                    if (!parenStack.empty()) {

                        error("Unbalanced parenheses", p, description);

                    }

                    if (parenStack.empty()) {

                        // if the rule contained an = sign, call processSubstitution()

                        // to replace the substitution name with the substitution text

                        // wherever it appears in the description

                        if (haveEquals) {

                            description = processSubstitution(description.substring(ruleStart,

                                            p), description, p + 1);

                        }

                        else {

                            // otherwise, check to make sure the rule doesn't reference

                            // any undefined substitutions

                            if (sawVarName) {

                                error("Unknown variable name", p, description);

                            }

                            // then add it to tempRuleList

                            tempRuleList.addElement(description.substring(ruleStart, p));

                        }

                        // and reset everything to process the next rule

                        ruleStart = p + 1;

                        haveEquals = havePipe = sawVarName = false;

                    }

                    break;

                // if the character is a vertical bar, check to make sure that it

                // occurs inside a () expression and that the character that precedes

                // it isn't also a vertical bar

                case '|':

                    if (lastC == '|') {

                        error("Empty alternative", p, description);

                    }

                    if (parenStack.empty() || lastOpen != '(') {

                        error("Misplaced |", p, description);

                    }

                    break;

                // if the character is anything else (escaped characters are

                // skipped and don't make it here), it's an error

                default:

                    if (c >= ' ' && c < '\u007f' && !Character.isLetter((char)c)

                        && !Character.isDigit((char)c)) {

                        error("Illegal character", p, description);

                    }

                    if (c >= Character.MIN_SUPPLEMENTARY_CODE_POINT) {

                        ++p;

                    }

                    break;

            }

            lastC = c;

            ++p;

        }

        if (tempRuleList.size() == 0) {

            error("No valid rules in description", p, description);

        }

        return tempRuleList;

    }

    /**

     * This function performs variable-name substitutions.  First it does syntax

     * checking on the variable-name definition.  If it's syntactically valid, it

     * then goes through the remainder of the description and does a simple

     * find-and-replace of the variable name with its text.  (The variable text

     * must be enclosed in either [] or () for this to work.)

     */

    protected String processSubstitution(String substitutionRule, String description,

                    int startPos) {

        // isolate out the text on either side of the equals sign

        String replace;

        String replaceWith;

        int equalPos = substitutionRule.indexOf('=');

        replace = substitutionRule.substring(0, equalPos);

        replaceWith = substitutionRule.substring(equalPos + 1);

        // check to see whether the substitution name is something we've declared

        // to be "special".  For RuleBasedBreakIterator itself, this is "<ignore>".

        // This function takes care of any extra processing that has to be done

        // with "special" substitution names.

        handleSpecialSubstitution(replace, replaceWith, startPos, description);

        // perform various other syntax checks on the rule

        if (replaceWith.length() == 0) {

            error("Nothing on right-hand side of =", startPos, description);

        }

        if (replace.length() == 0) {

            error("Nothing on left-hand side of =", startPos, description);

        }

        if (replace.length() == 2 && replace.charAt(0) != '\\') {

            error("Illegal left-hand side for =", startPos, description);

        }

        if (replace.length() >= 3 && replace.charAt(0) != '<' &&

            replace.codePointBefore(equalPos) != '>') {

            error("Illegal left-hand side for =", startPos, description);

        }

        if (!(replaceWith.charAt(0) == '[' &&

              replaceWith.charAt(replaceWith.length() - 1) == ']') &&

            !(replaceWith.charAt(0) == '(' &&

              replaceWith.charAt(replaceWith.length() - 1) == ')')) {

            error("Illegal right-hand side for =", startPos, description);

        }

        // now go through the rest of the description (which hasn't been broken up

        // into separate rules yet) and replace every occurrence of the

        // substitution name with the substitution body

        StringBuffer result = new StringBuffer();

        result.append(description.substring(0, startPos));

        int lastPos = startPos;

        int pos = description.indexOf(replace, startPos);

        while (pos != -1) {

            result.append(description.substring(lastPos, pos));

            result.append(replaceWith);

            lastPos = pos + replace.length();

            pos = description.indexOf(replace, lastPos);

        }

        result.append(description.substring(lastPos));

        return result.toString();

    }

    /**

     * This function defines a protocol for handling substitution names that