/*

 * reserved comment block

 * DO NOT REMOVE OR ALTER!

 */

/*

 * Copyright 1999-2004 The Apache Software Foundation.

 *

 * Licensed under the Apache License, Version 2.0 (the "License");

 * you may not use this file except in compliance with the License.

 * You may obtain a copy of the License at

 *

 *     http://www.apache.org/licenses/LICENSE-2.0

 *

 * Unless required by applicable law or agreed to in writing, software

 * distributed under the License is distributed on an "AS IS" BASIS,

 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 * See the License for the specific language governing permissions and

 * limitations under the License.

 */

package com.sun.org.apache.regexp.internal;

import java.io.Serializable;

import java.util.Vector;

/**

 * RE is an efficient, lightweight regular expression evaluator/matcher

 * class. Regular expressions are pattern descriptions which enable

 * sophisticated matching of strings.  In addition to being able to

 * match a string against a pattern, you can also extract parts of the

 * match.  This is especially useful in text parsing! Details on the

 * syntax of regular expression patterns are given below.

 *

 * <p>

 * To compile a regular expression (RE), you can simply construct an RE

 * matcher object from the string specification of the pattern, like this:

 *

 * <pre>

 *  RE r = new RE("a*b");

 * </pre>

 *

 * <p>

 * Once you have done this, you can call either of the RE.match methods to

 * perform matching on a String.  For example:

 *

 * <pre>

 *  boolean matched = r.match("aaaab");

 * </pre>

 *

 * will cause the boolean matched to be set to true because the

 * pattern "a*b" matches the string "aaaab".

 *

 * <p>

 * If you were interested in the <i>number</i> of a's which matched the

 * first part of our example expression, you could change the expression to

 * "(a*)b".  Then when you compiled the expression and matched it against

 * something like "xaaaab", you would get results like this:

 *

 * <pre>

 *  RE r = new RE("(a*)b");                  // Compile expression

 *  boolean matched = r.match("xaaaab");     // Match against "xaaaab"

 *

 *  String wholeExpr = r.getParen(0);        // wholeExpr will be 'aaaab'

 *  String insideParens = r.getParen(1);     // insideParens will be 'aaaa'

 *

 *  int startWholeExpr = r.getParenStart(0); // startWholeExpr will be index 1

 *  int endWholeExpr = r.getParenEnd(0);     // endWholeExpr will be index 6

 *  int lenWholeExpr = r.getParenLength(0);  // lenWholeExpr will be 5

 *

 *  int startInside = r.getParenStart(1);    // startInside will be index 1

 *  int endInside = r.getParenEnd(1);        // endInside will be index 5

 *  int lenInside = r.getParenLength(1);     // lenInside will be 4

 * </pre>

 *

 * You can also refer to the contents of a parenthesized expression

 * within a regular expression itself.  This is called a

 * 'backreference'.  The first backreference in a regular expression is

 * denoted by \1, the second by \2 and so on.  So the expression:

 *

 * <pre>

 *  ([0-9]+)=\1

 * </pre>

 *

 * will match any string of the form n=n (like 0=0 or 2=2).

 *

 * <p>

 * The full regular expression syntax accepted by RE is described here:

 *

 * <pre>

 *

 *  <b><font face=times roman>Characters</font></b>

 *

 *    <i>unicodeChar</i>   Matches any identical unicode character

 *    \                    Used to quote a meta-character (like '*')

 *    \\                   Matches a single '\' character

 *    \0nnn                Matches a given octal character

 *    \xhh                 Matches a given 8-bit hexadecimal character

 *    \\uhhhh              Matches a given 16-bit hexadecimal character

 *    \t                   Matches an ASCII tab character

 *    \n                   Matches an ASCII newline character

 *    \r                   Matches an ASCII return character

 *    \f                   Matches an ASCII form feed character

 *

 *

 *  <b><font face=times roman>Character Classes</font></b>

 *

 *    [abc]                Simple character class

 *    [a-zA-Z]             Character class with ranges

 *    [^abc]               Negated character class

 * </pre>

 *

 * <b>NOTE:</b> Incomplete ranges will be interpreted as &quot;starts

 * from zero" or "ends with last character".

 * <br>

 * I.e. [-a] is the same as [\\u0000-a], and [a-] is the same as [a-\\uFFFF],

 * [-] means "all characters".

 *

 * <pre>

 *

 *  <b><font face=times roman>Standard POSIX Character Classes</font></b>

 *

 *    [:alnum:]            Alphanumeric characters.

 *    [:alpha:]            Alphabetic characters.

 *    [:blank:]            Space and tab characters.

 *    [:cntrl:]            Control characters.

 *    [:digit:]            Numeric characters.

 *    [:graph:]            Characters that are printable and are also visible.

 *                         (A space is printable, but not visible, while an

 *                         `a' is both.)

 *    [:lower:]            Lower-case alphabetic characters.

 *    [:print:]            Printable characters (characters that are not

 *                         control characters.)

 *    [:punct:]            Punctuation characters (characters that are not letter,

 *                         digits, control characters, or space characters).

 *    [:space:]            Space characters (such as space, tab, and formfeed,

 *                         to name a few).

 *    [:upper:]            Upper-case alphabetic characters.

 *    [:xdigit:]           Characters that are hexadecimal digits.

 *

 *

 *  <b><font face=times roman>Non-standard POSIX-style Character Classes</font></b>

 *

 *    [:javastart:]        Start of a Java identifier

 *    [:javapart:]         Part of a Java identifier

 *

 *

 *  <b><font face=times roman>Predefined Classes</font></b>

 *

 *    .         Matches any character other than newline

 *    \w        Matches a "word" character (alphanumeric plus "_")

 *    \W        Matches a non-word character

 *    \s        Matches a whitespace character

 *    \S        Matches a non-whitespace character

 *    \d        Matches a digit character

 *    \D        Matches a non-digit character

 *

 *

 *  <b><font face=times roman>Boundary Matchers</font></b>

 *

 *    ^         Matches only at the beginning of a line

 *    $         Matches only at the end of a line

 *    \b        Matches only at a word boundary

 *    \B        Matches only at a non-word boundary

 *

 *

 *  <b><font face=times roman>Greedy Closures</font></b>

 *

 *    A*        Matches A 0 or more times (greedy)

 *    A+        Matches A 1 or more times (greedy)

 *    A?        Matches A 1 or 0 times (greedy)

 *    A{n}      Matches A exactly n times (greedy)

 *    A{n,}     Matches A at least n times (greedy)

 *    A{n,m}    Matches A at least n but not more than m times (greedy)

 *

 *

 *  <b><font face=times roman>Reluctant Closures</font></b>

 *

 *    A*?       Matches A 0 or more times (reluctant)

 *    A+?       Matches A 1 or more times (reluctant)

 *    A??       Matches A 0 or 1 times (reluctant)

 *

 *

 *  <b><font face=times roman>Logical Operators</font></b>

 *

 *    AB        Matches A followed by B

 *    A|B       Matches either A or B

 *    (A)       Used for subexpression grouping

 *   (?:A)      Used for subexpression clustering (just like grouping but

 *              no backrefs)

 *

 *

 *  <b><font face=times roman>Backreferences</font></b>

 *

 *    \1    Backreference to 1st parenthesized subexpression

 *    \2    Backreference to 2nd parenthesized subexpression

 *    \3    Backreference to 3rd parenthesized subexpression

 *    \4    Backreference to 4th parenthesized subexpression

 *    \5    Backreference to 5th parenthesized subexpression

 *    \6    Backreference to 6th parenthesized subexpression

 *    \7    Backreference to 7th parenthesized subexpression

 *    \8    Backreference to 8th parenthesized subexpression

 *    \9    Backreference to 9th parenthesized subexpression

 * </pre>

 *

 * <p>

 * All closure operators (+, *, ?, {m,n}) are greedy by default, meaning

 * that they match as many elements of the string as possible without

 * causing the overall match to fail.  If you want a closure to be

 * reluctant (non-greedy), you can simply follow it with a '?'.  A

 * reluctant closure will match as few elements of the string as

 * possible when finding matches.  {m,n} closures don't currently

 * support reluctancy.

 *

 * <p>

 * <b><font face="times roman">Line terminators</font></b>

 * <br>

 * A line terminator is a one- or two-character sequence that marks

 * the end of a line of the input character sequence. The following

 * are recognized as line terminators:

 * <ul>

 * <li>A newline (line feed) character ('\n'),</li>

 * <li>A carriage-return character followed immediately by a newline character ("\r\n"),</li>

 * <li>A standalone carriage-return character ('\r'),</li>

 * <li>A next-line character ('\u0085'),</li>

 * <li>A line-separator character ('\u2028'), or</li>

 * <li>A paragraph-separator character ('\u2029).</li>

 * </ul>

 *

 * <p>

 * RE runs programs compiled by the RECompiler class.  But the RE

 * matcher class does not include the actual regular expression compiler

 * for reasons of efficiency.  In fact, if you want to pre-compile one

 * or more regular expressions, the 'recompile' class can be invoked

 * from the command line to produce compiled output like this:

 *

 * <pre>

 *    // Pre-compiled regular expression "a*b"

 *    char[] re1Instructions =

 *    {

 *        0x007c, 0x0000, 0x001a, 0x007c, 0x0000, 0x000d, 0x0041,

 *        0x0001, 0x0004, 0x0061, 0x007c, 0x0000, 0x0003, 0x0047,

 *        0x0000, 0xfff6, 0x007c, 0x0000, 0x0003, 0x004e, 0x0000,

 *        0x0003, 0x0041, 0x0001, 0x0004, 0x0062, 0x0045, 0x0000,

 *        0x0000,

 *    };

 *

 *

 *    REProgram re1 = new REProgram(re1Instructions);

 * </pre>

 *

 * You can then construct a regular expression matcher (RE) object from

 * the pre-compiled expression re1 and thus avoid the overhead of

 * compiling the expression at runtime. If you require more dynamic

 * regular expressions, you can construct a single RECompiler object and

 * re-use it to compile each expression. Similarly, you can change the

 * program run by a given matcher object at any time. However, RE and

 * RECompiler are not threadsafe (for efficiency reasons, and because

 * requiring thread safety in this class is deemed to be a rare

 * requirement), so you will need to construct a separate compiler or

 * matcher object for each thread (unless you do thread synchronization

 * yourself). Once expression compiled into the REProgram object, REProgram

 * can be safely shared across multiple threads and RE objects.

 *

 * <br><p><br>

 *

 * <font color="red">

 * <i>ISSUES:</i>

 *

 * <ul>

 *  <li>com.weusours.util.re is not currently compatible with all

 *      standard POSIX regcomp flags</li>

 *  <li>com.weusours.util.re does not support POSIX equivalence classes

 *      ([=foo=] syntax) (I18N/locale issue)</li>

 *  <li>com.weusours.util.re does not support nested POSIX character

 *      classes (definitely should, but not completely trivial)</li>

 *  <li>com.weusours.util.re Does not support POSIX character collation

 *      concepts ([.foo.] syntax) (I18N/locale issue)</li>

 *  <li>Should there be different matching styles (simple, POSIX, Perl etc?)</li>

 *  <li>Should RE support character iterators (for backwards RE matching!)?</li>

 *  <li>Should RE support reluctant {m,n} closures (does anyone care)?</li>

 *  <li>Not *all* possibilities are considered for greediness when backreferences

 *      are involved (as POSIX suggests should be the case).  The POSIX RE

 *      "(ac*)c*d[ac]*\1", when matched against "acdacaa" should yield a match

 *      of acdacaa where \1 is "a".  This is not the case in this RE package,

 *      and actually Perl doesn't go to this extent either!  Until someone

 *      actually complains about this, I'm not sure it's worth "fixing".

 *      If it ever is fixed, test #137 in RETest.txt should be updated.</li>

 * </ul>

 *

 * </font>

 *

 * @see recompile

 * @see RECompiler

 *

 * @author <a href="mailto:jonl@muppetlabs.com">Jonathan Locke</a>

 * @author <a href="mailto:ts@sch-fer.de">Tobias Sch&auml;fer</a>

 */

public class RE implements Serializable

{

    /**

     * Specifies normal, case-sensitive matching behaviour.

     */

    public static final int MATCH_NORMAL          = 0x0000;

    /**

     * Flag to indicate that matching should be case-independent (folded)

     */

    public static final int MATCH_CASEINDEPENDENT = 0x0001;

    /**

     * Newlines should match as BOL/EOL (^ and $)

     */

    public static final int MATCH_MULTILINE       = 0x0002;

    /**

     * Consider all input a single body of text - newlines are matched by .

     */

    public static final int MATCH_SINGLELINE      = 0x0004;

    /************************************************

     *                                              *

     * The format of a node in a program is:        *

     *                                              *

     * [ OPCODE ] [ OPDATA ] [ OPNEXT ] [ OPERAND ] *

     *                                              *

     * char OPCODE - instruction                    *

     * char OPDATA - modifying data                 *

     * char OPNEXT - next node (relative offset)    *

     *                                              *

     ************************************************/

                 //   Opcode              Char       Opdata/Operand  Meaning

                 //   ----------          ---------- --------------- --------------------------------------------------

    static final char OP_END              = 'E';  //                 end of program

    static final char OP_BOL              = '^';  //                 match only if at beginning of line

    static final char OP_EOL              = '$';  //                 match only if at end of line

    static final char OP_ANY              = '.';  //                 match any single character except newline

    static final char OP_ANYOF            = '[';  // count/ranges    match any char in the list of ranges

    static final char OP_BRANCH           = '|';  // node            match this alternative or the next one

    static final char OP_ATOM             = 'A';  // length/string   length of string followed by string itself

    static final char OP_STAR             = '*';  // node            kleene closure

    static final char OP_PLUS             = '+';  // node            positive closure

    static final char OP_MAYBE            = '?';  // node            optional closure

    static final char OP_ESCAPE           = '\\'; // escape          special escape code char class (escape is E_* code)

    static final char OP_OPEN             = '(';  // number          nth opening paren

    static final char OP_OPEN_CLUSTER     = '<';  //                 opening cluster

    static final char OP_CLOSE            = ')';  // number          nth closing paren

    static final char OP_CLOSE_CLUSTER    = '>';  //                 closing cluster

    static final char OP_BACKREF          = '#';  // number          reference nth already matched parenthesized string

    static final char OP_GOTO             = 'G';  //                 nothing but a (back-)pointer

    static final char OP_NOTHING          = 'N';  //                 match null string such as in '(a|)'

    static final char OP_RELUCTANTSTAR    = '8';  // none/expr       reluctant '*' (mnemonic for char is unshifted '*')

    static final char OP_RELUCTANTPLUS    = '=';  // none/expr       reluctant '+' (mnemonic for char is unshifted '+')

    static final char OP_RELUCTANTMAYBE   = '/';  // none/expr       reluctant '?' (mnemonic for char is unshifted '?')

    static final char OP_POSIXCLASS       = 'P';  // classid         one of the posix character classes

    // Escape codes

    static final char E_ALNUM             = 'w';  // Alphanumeric

    static final char E_NALNUM            = 'W';  // Non-alphanumeric

    static final char E_BOUND             = 'b';  // Word boundary

    static final char E_NBOUND            = 'B';  // Non-word boundary

    static final char E_SPACE             = 's';  // Whitespace

    static final char E_NSPACE            = 'S';  // Non-whitespace

    static final char E_DIGIT             = 'd';  // Digit

    static final char E_NDIGIT            = 'D';  // Non-digit

    // Posix character classes

    static final char POSIX_CLASS_ALNUM   = 'w';  // Alphanumerics

    static final char POSIX_CLASS_ALPHA   = 'a';  // Alphabetics

    static final char POSIX_CLASS_BLANK   = 'b';  // Blanks

    static final char POSIX_CLASS_CNTRL   = 'c';  // Control characters

    static final char POSIX_CLASS_DIGIT   = 'd';  // Digits

    static final char POSIX_CLASS_GRAPH   = 'g';  // Graphic characters

    static final char POSIX_CLASS_LOWER   = 'l';  // Lowercase characters

    static final char POSIX_CLASS_PRINT   = 'p';  // Printable characters

    static final char POSIX_CLASS_PUNCT   = '!';  // Punctuation

    static final char POSIX_CLASS_SPACE   = 's';  // Spaces

    static final char POSIX_CLASS_UPPER   = 'u';  // Uppercase characters

    static final char POSIX_CLASS_XDIGIT  = 'x';  // Hexadecimal digits

    static final char POSIX_CLASS_JSTART  = 'j';  // Java identifier start

    static final char POSIX_CLASS_JPART   = 'k';  // Java identifier part

    // Limits

    static final int maxNode  = 65536;            // Maximum number of nodes in a program

    static final int MAX_PAREN = 16;              // Number of paren pairs (only 9 can be backrefs)

    // Node layout constants

    static final int offsetOpcode = 0;            // Opcode offset (first character)

    static final int offsetOpdata = 1;            // Opdata offset (second char)

    static final int offsetNext   = 2;            // Next index offset (third char)

    static final int nodeSize     = 3;            // Node size (in chars)

    // State of current program

    REProgram program;                            // Compiled regular expression 'program'

    transient CharacterIterator search;           // The string being matched against

    int matchFlags;                               // Match behaviour flags

    int maxParen = MAX_PAREN;

    // Parenthesized subexpressions

    transient int parenCount;                     // Number of subexpressions matched (num open parens + 1)

    transient int start0;                         // Cache of start[0]

    transient int end0;                           // Cache of start[0]

    transient int start1;                         // Cache of start[1]

    transient int end1;                           // Cache of start[1]

    transient int start2;                         // Cache of start[2]

    transient int end2;                           // Cache of start[2]

    transient int[] startn;                       // Lazy-alloced array of sub-expression starts

    transient int[] endn;                         // Lazy-alloced array of sub-expression ends

    // Backreferences

    transient int[] startBackref;                 // Lazy-alloced array of backref starts

    transient int[] endBackref;                   // Lazy-alloced array of backref ends

    /**

     * Constructs a regular expression matcher from a String by compiling it

     * using a new instance of RECompiler.  If you will be compiling many

     * expressions, you may prefer to use a single RECompiler object instead.

     *

     * @param pattern The regular expression pattern to compile.

     * @exception RESyntaxException Thrown if the regular expression has invalid syntax.

     * @see RECompiler

     * @see recompile

     */

    public RE(String pattern) throws RESyntaxException

    {

        this(pattern, MATCH_NORMAL);

    }

    /**

     * Constructs a regular expression matcher from a String by compiling it

     * using a new instance of RECompiler.  If you will be compiling many

     * expressions, you may prefer to use a single RECompiler object instead.

     *

     * @param pattern The regular expression pattern to compile.

     * @param matchFlags The matching style

     * @exception RESyntaxException Thrown if the regular expression has invalid syntax.

     * @see RECompiler

     * @see recompile

     */

    public RE(String pattern, int matchFlags) throws RESyntaxException

    {

        this(new RECompiler().compile(pattern));

        setMatchFlags(matchFlags);

    }

    /**

     * Construct a matcher for a pre-compiled regular expression from program

     * (bytecode) data.  Permits special flags to be passed in to modify matching

     * behaviour.

     *

     * @param program Compiled regular expression program (see RECompiler and/or recompile)

     * @param matchFlags One or more of the RE match behaviour flags (RE.MATCH_*):

     *

     * <pre>

     *   MATCH_NORMAL              // Normal (case-sensitive) matching

     *   MATCH_CASEINDEPENDENT     // Case folded comparisons

     *   MATCH_MULTILINE           // Newline matches as BOL/EOL

     * </pre>

     *

     * @see RECompiler

     * @see REProgram

     * @see recompile

     */

    public RE(REProgram program, int matchFlags)

    {

        setProgram(program);

        setMatchFlags(matchFlags);

    }

    /**

     * Construct a matcher for a pre-compiled regular expression from program

     * (bytecode) data.

     *

     * @param program Compiled regular expression program

     * @see RECompiler

     * @see recompile

     */

    public RE(REProgram program)

    {

        this(program, MATCH_NORMAL);

    }

    /**

     * Constructs a regular expression matcher with no initial program.

     * This is likely to be an uncommon practice, but is still supported.

     */

    public RE()

    {

        this((REProgram)null, MATCH_NORMAL);

    }

    /**

     * Converts a 'simplified' regular expression to a full regular expression

     *

     * @param pattern The pattern to convert

     * @return The full regular expression

     */

    public static String simplePatternToFullRegularExpression(String pattern)

    {

        StringBuffer buf = new StringBuffer();

        for (int i = 0; i < pattern.length(); i++)

        {

            char c = pattern.charAt(i);

            switch (c)

            {

                case '*':

                    buf.append(".*");

                    break;

                case '.':

                case '[':

                case ']':

                case '\\':

                case '+':

                case '?':

                case '{':

                case '}':

                case '$':

                case '^':

                case '|':

                case '(':

                case ')':

                    buf.append('\\');

                default:

                    buf.append(c);

                    break;

            }

        }

        return buf.toString();