1 /*

     2  * reserved comment block

     3  * DO NOT REMOVE OR ALTER!

     4  */

     5 /*

     6  * Copyright 1999-2004 The Apache Software Foundation.

     7  *

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

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

    10  * You may obtain a copy of the License at

    11  *

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

    13  *

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

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

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

    17  * See the License for the specific language governing permissions and

    18  * limitations under the License.

    19  */

    20 

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

    22 

    23 import java.io.Serializable;

    24 import java.util.Vector;

    25 

    26 /**

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

    28  * class. Regular expressions are pattern descriptions which enable

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

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

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

    32  * syntax of regular expression patterns are given below.

    33  *

    34  * <p>

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

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

    37  *

    38  * <pre>

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

    40  * </pre>

    41  *

    42  * <p>

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

    44  * perform matching on a String.  For example:

    45  *

    46  * <pre>

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

    48  * </pre>

    49  *

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

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

    52  *

    53  * <p>

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

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

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

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

    58  *

    59  * <pre>

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

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

    62  *

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

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

    65  *

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

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

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

    69  *

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

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

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

    73  * </pre>

    74  *

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

    76  * within a regular expression itself.  This is called a

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

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

    79  *

    80  * <pre>

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

    82  * </pre>

    83  *

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

    85  *

    86  * <p>

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

    88  *

    89  * <pre>

    90  *

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

    92  *

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

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

    95  *    \\                   Matches a single '\' character

    96  *    \0nnn                Matches a given octal character

    97  *    \xhh                 Matches a given 8-bit hexadecimal character

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

    99  *    \t                   Matches an ASCII tab character

   100  *    \n                   Matches an ASCII newline character

   101  *    \r                   Matches an ASCII return character

   102  *    \f                   Matches an ASCII form feed character

   103  *

   104  *

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

   106  *

   107  *    [abc]                Simple character class

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

   109  *    [^abc]               Negated character class

   110  * </pre>

   111  *

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

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

   114  * <br>

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

   116  * [-] means "all characters".

   117  *

   118  * <pre>

   119  *

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

   121  *

   122  *    [:alnum:]            Alphanumeric characters.

   123  *    [:alpha:]            Alphabetic characters.

   124  *    [:blank:]            Space and tab characters.

   125  *    [:cntrl:]            Control characters.

   126  *    [:digit:]            Numeric characters.

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

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

   129  *                         `a' is both.)

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

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

   132  *                         control characters.)

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

   134  *                         digits, control characters, or space characters).

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

   136  *                         to name a few).

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

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

   139  *

   140  *

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

   142  *

   143  *    [:javastart:]        Start of a Java identifier

   144  *    [:javapart:]         Part of a Java identifier

   145  *

   146  *

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

   148  *

   149  *    .         Matches any character other than newline

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

   151  *    \W        Matches a non-word character

   152  *    \s        Matches a whitespace character

   153  *    \S        Matches a non-whitespace character

   154  *    \d        Matches a digit character

   155  *    \D        Matches a non-digit character

   156  *

   157  *

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

   159  *

   160  *    ^         Matches only at the beginning of a line

   161  *    $         Matches only at the end of a line

   162  *    \b        Matches only at a word boundary

   163  *    \B        Matches only at a non-word boundary

   164  *

   165  *

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

   167  *

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

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

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

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

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

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

   174  *

   175  *

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

   177  *

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

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

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

   181  *

   182  *

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

   184  *

   185  *    AB        Matches A followed by B

   186  *    A|B       Matches either A or B

   187  *    (A)       Used for subexpression grouping

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

   189  *              no backrefs)

   190  *

   191  *

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

   193  *

   194  *    \1    Backreference to 1st parenthesized subexpression

   195  *    \2    Backreference to 2nd parenthesized subexpression

   196  *    \3    Backreference to 3rd parenthesized subexpression

   197  *    \4    Backreference to 4th parenthesized subexpression

   198  *    \5    Backreference to 5th parenthesized subexpression

   199  *    \6    Backreference to 6th parenthesized subexpression

   200  *    \7    Backreference to 7th parenthesized subexpression

   201  *    \8    Backreference to 8th parenthesized subexpression

   202  *    \9    Backreference to 9th parenthesized subexpression

   203  * </pre>

   204  *

   205  * <p>

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

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

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

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

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

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

   212  * support reluctancy.

   213  *

   214  * <p>

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

   216  * <br>

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

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

   219  * are recognized as line terminators:

   220  * <ul>

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

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

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

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

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

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

   227  * </ul>

   228  *

   229  * <p>

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

   231  * matcher class does not include the actual regular expression compiler

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

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

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

   235  *

   236  * <pre>

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

   238  *    char[] re1Instructions =

   239  *    {

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

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

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

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

   244  *        0x0000,

   245  *    };

   246  *

   247  *

   248  *    REProgram re1 = new REProgram(re1Instructions);

   249  * </pre>

   250  *

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

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

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

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

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

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

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

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

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

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

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

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

   263  *

   264  * <br><p><br>

   265  *

   266  * <font color="red">

   267  * <i>ISSUES:</i>

   268  *

   269  * <ul>

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

   271  *      standard POSIX regcomp flags</li>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   288  * </ul>

   289  *

   290  * </font>

   291  *

   292  * @see recompile

   293  * @see RECompiler

   294  *

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

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

   297  */

   298 public class RE implements Serializable

   299 {

   300     /**

   301      * Specifies normal, case-sensitive matching behaviour.

   302      */

   303     public static final int MATCH_NORMAL          = 0x0000;

   304 

   305     /**

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

   307      */

   308     public static final int MATCH_CASEINDEPENDENT = 0x0001;

   309 

   310     /**

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

   312      */

   313     public static final int MATCH_MULTILINE       = 0x0002;

   314 

   315     /**

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

   317      */

   318     public static final int MATCH_SINGLELINE      = 0x0004;

   319 

   320     /************************************************

   321      *                                              *

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

   323      *                                              *

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

   325      *                                              *

   326      * char OPCODE - instruction                    *

   327      * char OPDATA - modifying data                 *

   328      * char OPNEXT - next node (relative offset)    *

   329      *                                              *

   330      ************************************************/

   331 

   332                  //   Opcode              Char       Opdata/Operand  Meaning

   333                  //   ----------          ---------- --------------- --------------------------------------------------

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   356 

   357     // Escape codes

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

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

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

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

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

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

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

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

   366 

   367     // Posix character classes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   382 

   383     // Limits

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

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

   386 

   387     // Node layout constants

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

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

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

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

   392 

   393     // State of current program

   394     REProgram program;                            // Compiled regular expression 'program'

   395     transient CharacterIterator search;           // The string being matched against

   396     int matchFlags;                               // Match behaviour flags

   397     int maxParen = MAX_PAREN;

   398 

   399     // Parenthesized subexpressions

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

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

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

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

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

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

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

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

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

   409 

   410     // Backreferences

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

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

   413 

   414     /**

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

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

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

   418      *

   419      * @param pattern The regular expression pattern to compile.

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

   421      * @see RECompiler

   422      * @see recompile

   423      */

   424     public RE(String pattern) throws RESyntaxException

   425     {

   426         this(pattern, MATCH_NORMAL);

   427     }

   428 

   429     /**

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

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

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

   433      *

   434      * @param pattern The regular expression pattern to compile.

   435      * @param matchFlags The matching style

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

   437      * @see RECompiler

   438      * @see recompile

   439      */

   440     public RE(String pattern, int matchFlags) throws RESyntaxException

   441     {

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

   443         setMatchFlags(matchFlags);

   444     }

   445 

   446     /**

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

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

   449      * behaviour.

   450      *

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

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

   453      *

   454      * <pre>

   455      *   MATCH_NORMAL              // Normal (case-sensitive) matching

   456      *   MATCH_CASEINDEPENDENT     // Case folded comparisons

   457      *   MATCH_MULTILINE           // Newline matches as BOL/EOL

   458      * </pre>

   459      *

   460      * @see RECompiler

   461      * @see REProgram

   462      * @see recompile

   463      */

   464     public RE(REProgram program, int matchFlags)

   465     {

   466         setProgram(program);

   467         setMatchFlags(matchFlags);

   468     }

   469 

   470     /**

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

   472      * (bytecode) data.

   473      *

   474      * @param program Compiled regular expression program

   475      * @see RECompiler

   476      * @see recompile

   477      */

   478     public RE(REProgram program)

   479     {

   480         this(program, MATCH_NORMAL);

   481     }

   482 

   483     /**

   484      * Constructs a regular expression matcher with no initial program.

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

   486      */

   487     public RE()

   488     {

   489         this((REProgram)null, MATCH_NORMAL);

   490     }

   491 

   492     /**

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

   494      *

   495      * @param pattern The pattern to convert

   496      * @return The full regular expression

   497      */

   498     public static String simplePatternToFullRegularExpression(String pattern)

   499     {

   500         StringBuffer buf = new StringBuffer();

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

   502         {

   503             char c = pattern.charAt(i);

   504             switch (c)

   505             {

   506                 case '*':

   507                     buf.append(".*");

   508                     break;

   509 

   510                 case '.':

   511                 case '[':

   512                 case ']':

   513                 case '\\':

   514                 case '+':

   515                 case '?':

   516                 case '{':

   517                 case '}':

   518                 case '$':

   519                 case '^':

   520                 case '|':

   521                 case '(':

   522                 case ')':

   523                     buf.append('\\');

   524                 default:

   525                     buf.append(c);

   526                     break;

   527             }

   528         }

   529         return buf.toString();

   530     }

   531 

   532     /**

   533      * Sets match behaviour flags which alter the way RE does matching.

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

   535      *

   536      * <pre>

   537      *   MATCH_NORMAL              // Normal (case-sensitive) matching

   538      *   MATCH_CASEINDEPENDENT     // Case folded comparisons

   539      *   MATCH_MULTILINE           // Newline matches as BOL/EOL

   540      * </pre>

   541      */

   542     public void setMatchFlags(int matchFlags)

   543     {

   544         this.matchFlags = matchFlags;

   545     }

   546 

   547     /**

   548      * Returns the current match behaviour flags.

   549      * @return Current match behaviour flags (RE.MATCH_*).

   550      *

   551      * <pre>

   552      *   MATCH_NORMAL              // Normal (case-sensitive) matching

   553      *   MATCH_CASEINDEPENDENT     // Case folded comparisons

   554      *   MATCH_MULTILINE           // Newline matches as BOL/EOL

   555      * </pre>

   556      *

   557      * @see #setMatchFlags

   558      */

   559     public int getMatchFlags()

   560     {

   561         return matchFlags;

   562     }

   563 

   564     /**

   565      * Sets the current regular expression program used by this matcher object.

   566      *

   567      * @param program Regular expression program compiled by RECompiler.

   568      * @see RECompiler

   569      * @see REProgram

   570      * @see recompile

   571      */

   572     public void setProgram(REProgram program)

   573     {

   574         this.program = program;

   575         if (program != null && program.maxParens != -1) {

   576             this.maxParen = program.maxParens;

   577         } else {

   578             this.maxParen = MAX_PAREN;

   579         }

   580     }

   581 

   582     /**

   583      * Returns the current regular expression program in use by this matcher object.

   584      *

   585      * @return Regular expression program

   586      * @see #setProgram

   587      */

   588     public REProgram getProgram()

   589     {

   590         return program;

   591     }

   592 

   593     /**

   594      * Returns the number of parenthesized subexpressions available after a successful match.

   595      *

   596      * @return Number of available parenthesized subexpressions

   597      */

   598     public int getParenCount()

   599     {

   600         return parenCount;

   601     }

   602 

   603     /**

   604      * Gets the contents of a parenthesized subexpression after a successful match.

   605      *

   606      * @param which Nesting level of subexpression

   607      * @return String

   608      */

   609     public String getParen(int which)

   610     {

   611         int start;

   612         if (which < parenCount && (start = getParenStart(which)) >= 0)

   613         {

   614             return search.substring(start, getParenEnd(which));

   615         }

   616         return null;

   617     }

   618 

   619     /**

   620      * Returns the start index of a given paren level.

   621      *

   622      * @param which Nesting level of subexpression

   623      * @return String index

   624      */

   625     public final int getParenStart(int which)

   626     {

   627         if (which < parenCount)

   628         {

   629             switch (which)

   630             {

   631                 case 0:

   632                     return start0;

   633 

   634                 case 1:

   635                     return start1;

   636 

   637                 case 2:

   638                     return start2;

   639 

   640                 default:

   641                     if (startn == null)

   642                     {

   643                         allocParens();

   644                     }

   645                     return startn[which];

   646             }

   647         }

   648         return -1;

   649     }

   650 

   651     /**

   652      * Returns the end index of a given paren level.

   653      *

   654      * @param which Nesting level of subexpression

   655      * @return String index

   656      */

   657     public final int getParenEnd(int which)

   658     {

   659         if (which < parenCount)

   660         {

   661             switch (which)

   662             {

   663                 case 0:

   664                     return end0;

   665 

   666                 case 1:

   667                     return end1;

   668 

   669                 case 2:

   670                     return end2;

   671 

   672                 default:

   673                     if (endn == null)

   674                     {

   675                         allocParens();

   676                     }

   677                     return endn[which];

   678             }

   679         }

   680         return -1;

   681     }

   682 

   683     /**

   684      * Returns the length of a given paren level.

   685      *

   686      * @param which Nesting level of subexpression

   687      * @return Number of characters in the parenthesized subexpression

   688      */

   689     public final int getParenLength(int which)

   690     {

   691         if (which < parenCount)

   692         {

   693             return getParenEnd(which) - getParenStart(which);

   694         }

   695         return -1;

   696     }

   697 

   698     /**

   699      * Sets the start of a paren level

   700      *

   701      * @param which Which paren level

   702      * @param i Index in input array

   703      */

   704     protected final void setParenStart(int which, int i)

   705     {

   706         if (which < parenCount)

   707         {

   708             switch (which)

   709             {

   710                 case 0:

   711                     start0 = i;

   712                     break;

   713 

   714                 case 1:

   715                     start1 = i;

   716                     break;

   717 

   718                 case 2:

   719                     start2 = i;

   720                     break;

   721 

   722                 default:

   723                     if (startn == null)

   724                     {

   725                         allocParens();

   726                     }

   727                     startn[which] = i;

   728                     break;

   729             }

   730         }

   731     }

   732 

   733     /**

   734      * Sets the end of a paren level

   735      *

   736      * @param which Which paren level

   737      * @param i Index in input array

   738      */

   739     protected final void setParenEnd(int which, int i)

   740     {

   741         if (which < parenCount)

   742         {

   743             switch (which)

   744             {

   745                 case 0:

   746                     end0 = i;

   747                     break;

   748 

   749                 case 1:

   750                     end1 = i;

   751                     break;

   752 

   753                 case 2:

   754                     end2 = i;

   755                     break;

   756 

   757                 default:

   758                     if (endn == null)

   759                     {

   760                         allocParens();

   761                     }

   762                     endn[which] = i;

   763                     break;

   764             }

   765         }

   766     }

   767 

   768     /**

   769      * Throws an Error representing an internal error condition probably resulting

   770      * from a bug in the regular expression compiler (or possibly data corruption).

   771      * In practice, this should be very rare.

   772      *

   773      * @param s Error description

   774      */

   775     protected void internalError(String s) throws Error

   776     {

   777         throw new Error("RE internal error: " + s);

   778     }

   779 

   780     /**

   781      * Performs lazy allocation of subexpression arrays

   782      */

   783     private final void allocParens()

   784     {

   785         // Allocate arrays for subexpressions

   786         startn = new int[maxParen];

   787         endn = new int[maxParen];

   788 

   789         // Set sub-expression pointers to invalid values

   790         for (int i = 0; i < maxParen; i++)

   791         {

   792             startn[i] = -1;

   793             endn[i] = -1;

   794         }

   795     }

   796 

   797     /**

   798      * Try to match a string against a subset of nodes in the program

   799      *

   800      * @param firstNode Node to start at in program

   801      * @param lastNode  Last valid node (used for matching a subexpression without

   802      *                  matching the rest of the program as well).

   803      * @param idxStart  Starting position in character array

   804      * @return Final input array index if match succeeded.  -1 if not.

   805      */

   806     protected int matchNodes(int firstNode, int lastNode, int idxStart)

   807     {

   808         // Our current place in the string

   809         int idx = idxStart;

   810 

   811         // Loop while node is valid

   812         int next, opcode, opdata;

   813         int idxNew;

   814         char[] instruction = program.instruction;

   815         for (int node = firstNode; node < lastNode; )

   816         {

   817             opcode = instruction[node + offsetOpcode];

   818             next   = node + (short)instruction[node + offsetNext];

   819             opdata = instruction[node + offsetOpdata];

   820 

   821             switch (opcode)

   822             {

   823                 case OP_RELUCTANTMAYBE:

   824                     {

   825                         int once = 0;

   826                         do

   827                         {

   828                             // Try to match the rest without using the reluctant subexpr

   829                             if ((idxNew = matchNodes(next, maxNode, idx)) != -1)

   830                             {

   831                                 return idxNew;

   832                             }

   833                         }

   834                         while ((once++ == 0) && (idx = matchNodes(node + nodeSize, next, idx)) != -1);

   835                         return -1;

   836                     }

   837 

   838                 case OP_RELUCTANTPLUS:

   839                     while ((idx = matchNodes(node + nodeSize, next, idx)) != -1)

   840                     {

   841                         // Try to match the rest without using the reluctant subexpr

   842                         if ((idxNew = matchNodes(next, maxNode, idx)) != -1)

   843                         {

   844                             return idxNew;

   845                         }

   846                     }

   847                     return -1;

   848 

   849                 case OP_RELUCTANTSTAR:

   850                     do

   851                     {

   852                         // Try to match the rest without using the reluctant subexpr

   853                         if ((idxNew = matchNodes(next, maxNode, idx)) != -1)

   854                         {

   855                             return idxNew;

   856                         }

   857                     }

   858                     while ((idx = matchNodes(node + nodeSize, next, idx)) != -1);

   859                     return -1;

   860 

   861                 case OP_OPEN:

   862 

   863                     // Match subexpression

   864                     if ((program.flags & REProgram.OPT_HASBACKREFS) != 0)

   865                     {

   866                         startBackref[opdata] = idx;

   867                     }

   868                     if ((idxNew = matchNodes(next, maxNode, idx)) != -1)

   869                     {

   870                         // Increase valid paren count

   871                         if ((opdata + 1) > parenCount)

   872                         {

   873                             parenCount = opdata + 1;

   874                         }

   875 

   876                         // Don't set paren if already set later on

   877                         if (getParenStart(opdata) == -1)

   878                         {

   879                             setParenStart(opdata, idx);

   880                         }

   881                     }

   882                     return idxNew;

   883 

   884                 case OP_CLOSE:

   885 

   886                     // Done matching subexpression

   887                     if ((program.flags & REProgram.OPT_HASBACKREFS) != 0)

   888                     {

   889                         endBackref[opdata] = idx;

   890                     }

   891                     if ((idxNew = matchNodes(next, maxNode, idx)) != -1)

   892                     {

   893                         // Increase valid paren count

   894                         if ((opdata + 1) > parenCount)

   895                         {

   896                             parenCount = opdata + 1;

   897                         }

   898 

   899                         // Don't set paren if already set later on

   900                         if (getParenEnd(opdata) == -1)

   901                         {

   902                             setParenEnd(opdata, idx);

   903                         }

   904                     }

   905                     return idxNew;

   906 

   907                 case OP_OPEN_CLUSTER:

   908                 case OP_CLOSE_CLUSTER:

   909                     // starting or ending the matching of a subexpression which has no backref.

   910                     return matchNodes( next, maxNode, idx );

   911 

   912                 case OP_BACKREF:

   913                     {

   914                         // Get the start and end of the backref

   915                         int s = startBackref[opdata];

   916                         int e = endBackref[opdata];

   917 

   918                         // We don't know the backref yet

   919                         if (s == -1 || e == -1)

   920                         {

   921                             return -1;

   922                         }

   923 

   924                         // The backref is empty size

   925                         if (s == e)

   926                         {

   927                             break;

   928                         }

   929 

   930                         // Get the length of the backref

   931                         int l = e - s;

   932 

   933                         // If there's not enough input left, give up.

   934                         if (search.isEnd(idx + l - 1))

   935                         {

   936                             return -1;

   937                         }

   938 

   939                         // Case fold the backref?

   940                         final boolean caseFold =

   941                             ((matchFlags & MATCH_CASEINDEPENDENT) != 0);

   942                         // Compare backref to input

   943                         for (int i = 0; i < l; i++)

   944                         {

   945                             if (compareChars(search.charAt(idx++), search.charAt(s + i), caseFold) != 0)

   946                             {

   947                                 return -1;

   948                             }

   949                         }

   950                     }

   951                     break;

   952 

   953                 case OP_BOL:

   954 

   955                     // Fail if we're not at the start of the string

   956                     if (idx != 0)

   957                     {

   958                         // If we're multiline matching, we could still be at the start of a line

   959                         if ((matchFlags & MATCH_MULTILINE) == MATCH_MULTILINE)

   960                         {

   961                             // If not at start of line, give up

   962                             if (idx <= 0 || !isNewline(idx - 1)) {

   963                                 return -1;

   964                             } else {

   965                                 break;

   966                             }

   967                         }

   968                         return -1;

   969                     }

   970                     break;

   971 

   972                 case OP_EOL:

   973 

   974                     // If we're not at the end of string

   975                     if (!search.isEnd(0) && !search.isEnd(idx))

   976                     {

   977                         // If we're multi-line matching

   978                         if ((matchFlags & MATCH_MULTILINE) == MATCH_MULTILINE)

   979                         {

   980                             // Give up if we're not at the end of a line

   981                             if (!isNewline(idx)) {

   982                                 return -1;

   983                             } else {

   984                                 break;

   985                             }

   986                         }

   987                         return -1;

   988                     }

   989                     break;

   990 

   991                 case OP_ESCAPE:

   992 

   993                     // Which escape?

   994                     switch (opdata)

   995                     {

   996                         // Word boundary match

   997                         case E_NBOUND:

   998                         case E_BOUND:

   999                             {

  1000                                 char cLast = ((idx == 0) ? '\n' : search.charAt(idx - 1));

  1001                                 char cNext = ((search.isEnd(idx)) ? '\n' : search.charAt(idx));

  1002                                 if ((Character.isLetterOrDigit(cLast) == Character.isLetterOrDigit(cNext)) == (opdata == E_BOUND))

  1003                                 {

  1004                                     return -1;

  1005                                 }

  1006                             }

  1007                             break;

  1008 

  1009                         // Alpha-numeric, digit, space, javaLetter, javaLetterOrDigit

  1010                         case E_ALNUM:

  1011                         case E_NALNUM:

  1012                         case E_DIGIT:

  1013                         case E_NDIGIT:

  1014                         case E_SPACE:

  1015                         case E_NSPACE:

  1016 

  1017                             // Give up if out of input

  1018                             if (search.isEnd(idx))

  1019                             {

  1020                                 return -1;

  1021                             }

  1022 

  1023                             char c = search.charAt(idx);

  1024 

  1025                             // Switch on escape

  1026                             switch (opdata)

  1027                             {

  1028                                 case E_ALNUM:

  1029                                 case E_NALNUM:

  1030                                     if (!((Character.isLetterOrDigit(c) || c == '_') == (opdata == E_ALNUM)))

  1031                                     {

  1032                                         return -1;

  1033                                     }

  1034                                     break;

  1035 

  1036                                 case E_DIGIT:

  1037                                 case E_NDIGIT:

  1038                                     if (!(Character.isDigit(c) == (opdata == E_DIGIT)))

  1039                                     {

  1040                                         return -1;

  1041                                     }

  1042                                     break;

  1043 

  1044                                 case E_SPACE:

  1045                                 case E_NSPACE:

  1046                                     if (!(Character.isWhitespace(c) == (opdata == E_SPACE)))

  1047                                     {

  1048                                         return -1;

  1049                                     }

  1050                                     break;

  1051                             }

  1052                             idx++;

  1053                             break;

  1054 

  1055                         default:

  1056                             internalError("Unrecognized escape '" + opdata + "'");

  1057                     }

  1058                     break;

  1059 

  1060                 case OP_ANY:

  1061 

  1062                     if ((matchFlags & MATCH_SINGLELINE) == MATCH_SINGLELINE) {

  1063                         // Match anything

  1064                         if (search.isEnd(idx))

  1065                         {

  1066                             return -1;

  1067                         }

  1068                     }

  1069                     else

  1070                     {

  1071                         // Match anything but a newline

  1072                         if (search.isEnd(idx) || isNewline(idx))

  1073                         {

  1074                             return -1;

  1075                         }

  1076                     }

  1077                     idx++;

  1078                     break;

  1079 

  1080                 case OP_ATOM:

  1081                     {

  1082                         // Match an atom value

  1083                         if (search.isEnd(idx))

  1084                         {

  1085                             return -1;

  1086                         }

  1087 

  1088                         // Get length of atom and starting index

  1089                         int lenAtom = opdata;

  1090                         int startAtom = node + nodeSize;

  1091 

  1092                         // Give up if not enough input remains to have a match

  1093                         if (search.isEnd(lenAtom + idx - 1))

  1094                         {

  1095                             return -1;

  1096                         }

  1097 

  1098                         // Match atom differently depending on casefolding flag

  1099                         final boolean caseFold =

  1100                             ((matchFlags & MATCH_CASEINDEPENDENT) != 0);

  1101 

  1102                         for (int i = 0; i < lenAtom; i++)

  1103                         {

  1104                             if (compareChars(search.charAt(idx++), instruction[startAtom + i], caseFold) != 0)

  1105                             {

  1106                                 return -1;

  1107                             }

  1108                         }

  1109                     }

  1110                     break;

  1111 

  1112                 case OP_POSIXCLASS:

  1113                     {

  1114                         // Out of input?

  1115                         if (search.isEnd(idx))

  1116                         {

  1117                             return -1;

  1118                         }

  1119 

  1120                         switch (opdata)

  1121                         {

  1122                             case POSIX_CLASS_ALNUM:

  1123                                 if (!Character.isLetterOrDigit(search.charAt(idx)))

  1124                                 {

  1125                                     return -1;

  1126                                 }

  1127                                 break;

  1128 

  1129                             case POSIX_CLASS_ALPHA:

  1130                                 if (!Character.isLetter(search.charAt(idx)))

  1131                                 {

  1132                                     return -1;

  1133                                 }

  1134                                 break;