/*

 * Copyright (c) 1999, 2010, 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.

 */

/*

 *

 * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved

 * (C) Copyright IBM Corp. 1996 - 2002 - All Rights Reserved

 *

 * The original version of this source code and documentation

 * is copyrighted and owned by Taligent, Inc., a wholly-owned

 * subsidiary of IBM. These materials are provided under terms

 * of a License Agreement between Taligent and Sun. This technology

 * is protected by multiple US and International patents.

 *

 * This notice and attribution to Taligent may not be removed.

 * Taligent is a registered trademark of Taligent, Inc.

 */

package java.text;

import java.io.BufferedInputStream;

import java.io.IOException;

import java.security.AccessController;

import java.security.PrivilegedActionException;

import java.security.PrivilegedExceptionAction;

import java.util.Vector;

import java.util.Stack;

import java.util.Hashtable;

import java.util.Enumeration;

import java.util.MissingResourceException;

import java.text.CharacterIterator;

import java.text.StringCharacterIterator;

import sun.text.CompactByteArray;

import sun.text.SupplementaryCharacterData;

/**

 * <p>A subclass of BreakIterator whose behavior is specified using a list of rules.</p>

 *

 * <p>There are two kinds of rules, which are separated by semicolons: <i>substitutions</i>

 * and <i>regular expressions.</i></p>

 *

 * <p>A substitution rule defines a name that can be used in place of an expression. It

 * consists of a name, which is a string of characters contained in angle brackets, an equals

 * sign, and an expression. (There can be no whitespace on either side of the equals sign.)

 * To keep its syntactic meaning intact, the expression must be enclosed in parentheses or

 * square brackets. A substitution is visible after its definition, and is filled in using

 * simple textual substitution. Substitution definitions can contain other substitutions, as

 * long as those substitutions have been defined first. Substitutions are generally used to

 * make the regular expressions (which can get quite complex) shorted and easier to read.

 * They typically define either character categories or commonly-used subexpressions.</p>

 *

 * <p>There is one special substitution.&nbsp; If the description defines a substitution

 * called "<ignore>", the expression must be a [] expression, and the

 * expression defines a set of characters (the &quot;<em>ignore characters</em>&quot;) that

 * will be transparent to the BreakIterator.  A sequence of characters will break the

 * same way it would if any ignore characters it contains are taken out.  Break

 * positions never occur befoer ignore characters.</p>

 *

 * <p>A regular expression uses a subset of the normal Unix regular-expression syntax, and

 * defines a sequence of characters to be kept together. With one significant exception, the

 * iterator uses a longest-possible-match algorithm when matching text to regular

 * expressions. The iterator also treats descriptions containing multiple regular expressions

 * as if they were ORed together (i.e., as if they were separated by |).</p>

 *

 * <p>The special characters recognized by the regular-expression parser are as follows:</p>

 *

 * <blockquote>

 *   <table border="1" width="100%">

 *     <tr>

 *       <td width="6%">*</td>

 *       <td width="94%">Specifies that the expression preceding the asterisk may occur any number

 *       of times (including not at all).</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">{}</td>

 *       <td width="94%">Encloses a sequence of characters that is optional.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">()</td>

 *       <td width="94%">Encloses a sequence of characters.&nbsp; If followed by *, the sequence

 *       repeats.  Otherwise, the parentheses are just a grouping device and a way to delimit

 *       the ends of expressions containing |.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">|</td>

 *       <td width="94%">Separates two alternative sequences of characters.&nbsp; Either one

 *       sequence or the other, but not both, matches this expression.  The | character can

 *       only occur inside ().</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">.</td>

 *       <td width="94%">Matches any character.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">*?</td>

 *       <td width="94%">Specifies a non-greedy asterisk.&nbsp; *? works the same way as *, except

 *       when there is overlap between the last group of characters in the expression preceding the

 *       * and the first group of characters following the *.  When there is this kind of

 *       overlap, * will match the longest sequence of characters that match the expression before

 *       the *, and *? will match the shortest sequence of characters matching the expression

 *       before the *?.  For example, if you have "xxyxyyyxyxyxxyxyxyy" in the text,

 *       &quot;x[xy]*x&quot; will match through to the last x (i.e., &quot;<strong>xxyxyyyxyxyxxyxyx</strong>yy&quot;,

 *       but &quot;x[xy]*?x&quot; will only match the first two xes (&quot;<strong>xx</strong>yxyyyxyxyxxyxyxyy&quot;).</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">[]</td>

 *       <td width="94%">Specifies a group of alternative characters.&nbsp; A [] expression will

 *       match any single character that is specified in the [] expression.  For more on the

 *       syntax of [] expressions, see below.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">/</td>

 *       <td width="94%">Specifies where the break position should go if text matches this

 *       expression.  (e.g., "[a-z]*/[:Zs:]*[1-0]" will match if the iterator sees a run

 *       of letters, followed by a run of whitespace, followed by a digit, but the break position

 *       will actually go before the whitespace).  Expressions that don't contain / put the

 *       break position at the end of the matching text.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">\</td>

 *       <td width="94%">Escape character.&nbsp; The \ itself is ignored, but causes the next

 *       character to be treated as literal character.  This has no effect for many

 *       characters, but for the characters listed above, this deprives them of their special

 *       meaning.  (There are no special escape sequences for Unicode characters, or tabs and

 *       newlines; these are all handled by a higher-level protocol.  In a Java string,

 *       "\n" will be converted to a literal newline character by the time the

 *       regular-expression parser sees it.  Of course, this means that \ sequences that are

 *       visible to the regexp parser must be written as \\ when inside a Java string.)  All

 *       characters in the ASCII range except for letters, digits, and control characters are

 *       reserved characters to the parser and must be preceded by \ even if they currently don't

 *       mean anything.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">!</td>

 *       <td width="94%">If ! appears at the beginning of a regular expression, it tells the regexp

 *       parser that this expression specifies the backwards-iteration behavior of the iterator,

 *       and not its normal iteration behavior.  This is generally only used in situations

 *       where the automatically-generated backwards-iteration brhavior doesn't produce

 *       satisfactory results and must be supplemented with extra client-specified rules.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%"><em>(all others)</em></td>

 *       <td width="94%">All other characters are treated as literal characters, which must match

 *       the corresponding character(s) in the text exactly.</td>

 *     </tr>

 *   </table>

 * </blockquote>

 *

 * <p>Within a [] expression, a number of other special characters can be used to specify

 * groups of characters:</p>

 *

 * <blockquote>

 *   <table border="1" width="100%">

 *     <tr>

 *       <td width="6%">-</td>

 *       <td width="94%">Specifies a range of matching characters.&nbsp; For example

 *       "[a-p]" matches all lowercase Latin letters from a to p (inclusive).  The -

 *       sign specifies ranges of continuous Unicode numeric values, not ranges of characters in a

 *       language's alphabetical order: "[a-z]" doesn't include capital letters, nor does

 *       it include accented letters such as a-umlaut.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">::</td>

 *       <td width="94%">A pair of colons containing a one- or two-letter code matches all

 *       characters in the corresponding Unicode category.  The two-letter codes are the same

 *       as the two-letter codes in the Unicode database (for example, "[:Sc::Sm:]"

 *       matches all currency symbols and all math symbols).  Specifying a one-letter code is

 *       the same as specifying all two-letter codes that begin with that letter (for example,

 *       "[:L:]" matches all letters, and is equivalent to

 *       "[:Lu::Ll::Lo::Lm::Lt:]").  Anything other than a valid two-letter Unicode

 *       category code or a single letter that begins a Unicode category code is illegal within

 *       colons.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">[]</td>

 *       <td width="94%">[] expressions can nest.&nbsp; This has no effect, except when used in

 *       conjunction with the ^ token.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%">^</td>

 *       <td width="94%">Excludes the character (or the characters in the [] expression) following

 *       it from the group of characters.  For example, "[a-z^p]" matches all Latin

 *       lowercase letters except p.  "[:L:^[\u4e00-\u9fff]]" matches all letters

 *       except the Han ideographs.</td>

 *     </tr>

 *     <tr>

 *       <td width="6%"><em>(all others)</em></td>

 *       <td width="94%">All other characters are treated as literal characters.&nbsp; (For

 *       example, &quot;[aeiou]&quot; specifies just the letters a, e, i, o, and u.)</td>

 *     </tr>

 *   </table>

 * </blockquote>

 *

 * <p>For a more complete explanation, see <a

 * href="http://www.ibm.com/java/education/boundaries/boundaries.html">http://www.ibm.com/java/education/boundaries/boundaries.html</a>.

 * &nbsp; For examples, see the resource data (which is annotated).</p>

 *

 * @author Richard Gillam

 */

class RuleBasedBreakIterator extends BreakIterator {

    /**

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

     */

    protected static final byte IGNORE = -1;

    /**

     * The state number of the starting state

     */

    private static final short START_STATE = 1;

    /**

     * The state-transition value indicating "stop"

     */

    private static final short STOP_STATE = 0;

    /**

     * Magic number for the BreakIterator data file format.

     */

    static final byte[] LABEL = {

        (byte)'B', (byte)'I', (byte)'d', (byte)'a', (byte)'t', (byte)'a',

        (byte)'\0'

    };

    static final int    LABEL_LENGTH = LABEL.length;

    /**

     * Version number of the dictionary that was read in.

     */

    static final byte supportedVersion = 1;

    /**

     * Header size in byte count

     */

    private static final int HEADER_LENGTH = 36;

    /**

     * An array length of indices for BMP characters

     */

    private static final int BMP_INDICES_LENGTH = 512;

    /**

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

    /**

     * The character iterator through which this BreakIterator accesses the text

     */

    private CharacterIterator text = null;

    /**

     * A CRC32 value of all data in datafile

     */

    private long checksum;

    //=======================================================================

    // constructors

    //=======================================================================

    /**

     * Constructs a RuleBasedBreakIterator according to the datafile

     * provided.

     */

    public RuleBasedBreakIterator(String datafile)

        throws IOException, MissingResourceException {

        readTables(datafile);

    }

    /**

     * Read datafile. The datafile's format is as follows:

     * <pre>

     *   BreakIteratorData {

     *       u1           magic[7];

     *       u1           version;

     *       u4           totalDataSize;

     *       header_info  header;

     *       body         value;

     *   }

     * </pre>

     * <code>totalDataSize</code> is the summation of the size of

     * <code>header_info</code> and <code>body</code> in byte count.

     * <p>

     * In <code>header</code>, each field except for checksum implies the

     * length of each field. Since <code>BMPdataLength</code> is a fixed-length

     *  data(512 entries), its length isn't included in <code>header</code>.

     * <code>checksum</code> is a CRC32 value of all in <code>body</code>.

     * <pre>

     *   header_info {

     *       u4           stateTableLength;

     *       u4           backwardsStateTableLength;

     *       u4           endStatesLength;

     *       u4           lookaheadStatesLength;

     *       u4           BMPdataLength;

     *       u4           nonBMPdataLength;

     *       u4           additionalDataLength;

     *       u8           checksum;

     *   }

     * </pre>

     * <p>

     *

     * Finally, <code>BMPindices</code> and <code>BMPdata</code> are set to

     * <code>charCategoryTable</code>. <code>nonBMPdata</code> is set to

     * <code>supplementaryCharCategoryTable</code>.

     * <pre>

     *   body {

     *       u2           stateTable[stateTableLength];

     *       u2           backwardsStateTable[backwardsStateTableLength];

     *       u1           endStates[endStatesLength];

     *       u1           lookaheadStates[lookaheadStatesLength];

     *       u2           BMPindices[512];

     *       u1           BMPdata[BMPdataLength];

     *       u4           nonBMPdata[numNonBMPdataLength];

     *       u1           additionalData[additionalDataLength];

     *   }

     * </pre>

     */

    protected void readTables(String datafile)

        throws IOException, MissingResourceException {

        byte[] buffer = readFile(datafile);

        /* Read header_info. */

        int stateTableLength = BreakIterator.getInt(buffer, 0);

        int backwardsStateTableLength = BreakIterator.getInt(buffer, 4);

        int endStatesLength = BreakIterator.getInt(buffer, 8);

        int lookaheadStatesLength = BreakIterator.getInt(buffer, 12);

        int BMPdataLength = BreakIterator.getInt(buffer, 16);

        int nonBMPdataLength = BreakIterator.getInt(buffer, 20);

        int additionalDataLength = BreakIterator.getInt(buffer, 24);

        checksum = BreakIterator.getLong(buffer, 28);

        /* Read stateTable[numCategories * numRows] */

        stateTable = new short[stateTableLength];

        int offset = HEADER_LENGTH;

        for (int i = 0; i < stateTableLength; i++, offset+=2) {

           stateTable[i] = BreakIterator.getShort(buffer, offset);

        }

        /* Read backwardsStateTable[numCategories * numRows] */

        backwardsStateTable = new short[backwardsStateTableLength];

        for (int i = 0; i < backwardsStateTableLength; i++, offset+=2) {

           backwardsStateTable[i] = BreakIterator.getShort(buffer, offset);

        }

        /* Read endStates[numRows] */

        endStates = new boolean[endStatesLength];

        for (int i = 0; i < endStatesLength; i++, offset++) {

           endStates[i] = buffer[offset] == 1;

        }

        /* Read lookaheadStates[numRows] */

        lookaheadStates = new boolean[lookaheadStatesLength];

        for (int i = 0; i < lookaheadStatesLength; i++, offset++) {

           lookaheadStates[i] = buffer[offset] == 1;

        }

        /* Read a category table and indices for BMP characters. */

        short[] temp1 = new short[BMP_INDICES_LENGTH];  // BMPindices

        for (int i = 0; i < BMP_INDICES_LENGTH; i++, offset+=2) {

            temp1[i] = BreakIterator.getShort(buffer, offset);

        }

        byte[] temp2 = new byte[BMPdataLength];  // BMPdata

        System.arraycopy(buffer, offset, temp2, 0, BMPdataLength);

        offset += BMPdataLength;

        charCategoryTable = new CompactByteArray(temp1, temp2);

        /* Read a category table for non-BMP characters. */

        int[] temp3 = new int[nonBMPdataLength];

        for (int i = 0; i < nonBMPdataLength; i++, offset+=4) {

            temp3[i] = BreakIterator.getInt(buffer, offset);

        }

        supplementaryCharCategoryTable = new SupplementaryCharacterData(temp3);

        /* Read additional data */

        if (additionalDataLength > 0) {

            additionalData = new byte[additionalDataLength];

            System.arraycopy(buffer, offset, additionalData, 0, additionalDataLength);

        }

        /* Set numCategories */

        numCategories = stateTable.length / endStates.length;

    }

    protected byte[] readFile(final String datafile)

        throws IOException, MissingResourceException {

        BufferedInputStream is;

        try {

            is = (BufferedInputStream)AccessController.doPrivileged(

                new PrivilegedExceptionAction() {

                    public Object run() throws Exception {

                        return new BufferedInputStream(getClass().getResourceAsStream("/sun/text/resources/" + datafile));

                    }

                }

            );

        }

        catch (PrivilegedActionException e) {

            throw new InternalError(e.toString());

        }

        int offset = 0;

        /* First, read magic, version, and header_info. */

        int len = LABEL_LENGTH + 5;

        byte[] buf = new byte[len];

        if (is.read(buf) != len) {

            throw new MissingResourceException("Wrong header length",

                                               datafile, "");

        }

        /* Validate the magic number. */

        for (int i = 0; i < LABEL_LENGTH; i++, offset++) {

            if (buf[offset] != LABEL[offset]) {

                throw new MissingResourceException("Wrong magic number",

                                                   datafile, "");

            }

        }

        /* Validate the version number. */

        if (buf[offset] != supportedVersion) {

            throw new MissingResourceException("Unsupported version(" + buf[offset] + ")",

                                               datafile, "");

        }

        /* Read data: totalDataSize + 8(for checksum) */

        len = BreakIterator.getInt(buf, ++offset);

        buf = new byte[len];

        if (is.read(buf) != len) {

            throw new MissingResourceException("Wrong data length",

                                               datafile, "");

        }

        is.close();

        return buf;

    }

    byte[] getAdditionalData() {

        return additionalData;

    }

    void setAdditionalData(byte[] b) {

        additionalData = b;

    }

    //=======================================================================

    // boilerplate

    //=======================================================================

    /**

     * Clones this iterator.

     * @return A newly-constructed RuleBasedBreakIterator with the same

     * behavior as this one.

     */

    public Object clone() {

        RuleBasedBreakIterator result = (RuleBasedBreakIterator) super.clone();

        if (text != null) {

            result.text = (CharacterIterator) text.clone();

        }

        return result;

    }

    /**

     * Returns true if both BreakIterators are of the same class, have the same

     * rules, and iterate over the same text.

     */

    public boolean equals(Object that) {

        try {

            if (that == null) {

                return false;

            }