KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > regex > Pattern


1 /*
2  * @(#)Pattern.java 1.113 07/05/07
3  *
4  * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */

7
8 package java.util.regex;
9
10 import java.security.AccessController JavaDoc;
11 import java.security.PrivilegedAction JavaDoc;
12 import java.text.CharacterIterator JavaDoc;
13 import sun.text.Normalizer;
14 import java.util.ArrayList JavaDoc;
15 import java.util.HashMap JavaDoc;
16
17
18 /**
19  * A compiled representation of a regular expression.
20  *
21  * <p> A regular expression, specified as a string, must first be compiled into
22  * an instance of this class. The resulting pattern can then be used to create
23  * a {@link Matcher} object that can match arbitrary {@link
24  * java.lang.CharSequence </code>character sequences<code>} against the regular
25  * expression. All of the state involved in performing a match resides in the
26  * matcher, so many matchers can share the same pattern.
27  *
28  * <p> A typical invocation sequence is thus
29  *
30  * <blockquote><pre>
31  * Pattern p = Pattern.{@link #compile compile}("a*b");
32  * Matcher m = p.{@link #matcher matcher}("aaaaab");
33  * boolean b = m.{@link Matcher#matches matches}();</pre></blockquote>
34  *
35  * <p> A {@link #matches matches} method is defined by this class as a
36  * convenience for when a regular expression is used just once. This method
37  * compiles an expression and matches an input sequence against it in a single
38  * invocation. The statement
39  *
40  * <blockquote><pre>
41  * boolean b = Pattern.matches("a*b", "aaaaab");</pre></blockquote>
42  *
43  * is equivalent to the three statements above, though for repeated matches it
44  * is less efficient since it does not allow the compiled pattern to be reused.
45  *
46  * <p> Instances of this class are immutable and are safe for use by multiple
47  * concurrent threads. Instances of the {@link Matcher} class are not safe for
48  * such use.
49  *
50  *
51  * <a name="sum">
52  * <h4> Summary of regular-expression constructs </h4>
53  *
54  * <table border="0" cellpadding="1" cellspacing="0"
55  * summary="Regular expression constructs, and what they match">
56  *
57  * <tr align="left">
58  * <th bgcolor="#CCCCFF" align="left" id="construct">Construct</th>
59  * <th bgcolor="#CCCCFF" align="left" id="matches">Matches</th>
60  * </tr>
61  *
62  * <tr><th>&nbsp;</th></tr>
63  * <tr align="left"><th colspan="2" id="characters">Characters</th></tr>
64  *
65  * <tr><td valign="top" headers="construct characters"><i>x</i></td>
66  * <td headers="matches">The character <i>x</i></td></tr>
67  * <tr><td valign="top" headers="construct characters"><tt>\\</tt></td>
68  * <td headers="matches">The backslash character</td></tr>
69  * <tr><td valign="top" headers="construct characters"><tt>\0</tt><i>n</i></td>
70  * <td headers="matches">The character with octal value <tt>0</tt><i>n</i>
71  * (0&nbsp;<tt>&lt;=</tt>&nbsp;<i>n</i>&nbsp;<tt>&lt;=</tt>&nbsp;7)</td></tr>
72  * <tr><td valign="top" headers="construct characters"><tt>\0</tt><i>nn</i></td>
73  * <td headers="matches">The character with octal value <tt>0</tt><i>nn</i>
74  * (0&nbsp;<tt>&lt;=</tt>&nbsp;<i>n</i>&nbsp;<tt>&lt;=</tt>&nbsp;7)</td></tr>
75  * <tr><td valign="top" headers="construct characters"><tt>\0</tt><i>mnn</i></td>
76  * <td headers="matches">The character with octal value <tt>0</tt><i>mnn</i>
77  * (0&nbsp;<tt>&lt;=</tt>&nbsp;<i>m</i>&nbsp;<tt>&lt;=</tt>&nbsp;3,
78  * 0&nbsp;<tt>&lt;=</tt>&nbsp;<i>n</i>&nbsp;<tt>&lt;=</tt>&nbsp;7)</td></tr>
79  * <tr><td valign="top" headers="construct characters"><tt>\x</tt><i>hh</i></td>
80  * <td headers="matches">The character with hexadecimal&nbsp;value&nbsp;<tt>0x</tt><i>hh</i></td></tr>
81  * <tr><td valign="top" headers="construct characters"><tt>&#92;u</tt><i>hhhh</i></td>
82  * <td headers="matches">The character with hexadecimal&nbsp;value&nbsp;<tt>0x</tt><i>hhhh</i></td></tr>
83  * <tr><td valign="top" headers="matches"><tt>\t</tt></td>
84  * <td headers="matches">The tab character (<tt>'&#92;u0009'</tt>)</td></tr>
85  * <tr><td valign="top" headers="construct characters"><tt>\n</tt></td>
86  * <td headers="matches">The newline (line feed) character (<tt>'&#92;u000A'</tt>)</td></tr>
87  * <tr><td valign="top" headers="construct characters"><tt>\r</tt></td>
88  * <td headers="matches">The carriage-return character (<tt>'&#92;u000D'</tt>)</td></tr>
89  * <tr><td valign="top" headers="construct characters"><tt>\f</tt></td>
90  * <td headers="matches">The form-feed character (<tt>'&#92;u000C'</tt>)</td></tr>
91  * <tr><td valign="top" headers="construct characters"><tt>\a</tt></td>
92  * <td headers="matches">The alert (bell) character (<tt>'&#92;u0007'</tt>)</td></tr>
93  * <tr><td valign="top" headers="construct characters"><tt>\e</tt></td>
94  * <td headers="matches">The escape character (<tt>'&#92;u001B'</tt>)</td></tr>
95  * <tr><td valign="top" headers="construct characters"><tt>\c</tt><i>x</i></td>
96  * <td headers="matches">The control character corresponding to <i>x</i></td></tr>
97  *
98  * <tr><th>&nbsp;</th></tr>
99  * <tr align="left"><th colspan="2" id="classes">Character classes</th></tr>
100  *
101  * <tr><td valign="top" headers="construct classes"><tt>[abc]</tt></td>
102  * <td headers="matches"><tt>a</tt>, <tt>b</tt>, or <tt>c</tt> (simple class)</td></tr>
103  * <tr><td valign="top" headers="construct classes"><tt>[^abc]</tt></td>
104  * <td headers="matches">Any character except <tt>a</tt>, <tt>b</tt>, or <tt>c</tt> (negation)</td></tr>
105  * <tr><td valign="top" headers="construct classes"><tt>[a-zA-Z]</tt></td>
106  * <td headers="matches"><tt>a</tt> through <tt>z</tt>
107  * or <tt>A</tt> through <tt>Z</tt>, inclusive (range)</td></tr>
108  * <tr><td valign="top" headers="construct classes"><tt>[a-d[m-p]]</tt></td>
109  * <td headers="matches"><tt>a</tt> through <tt>d</tt>,
110  * or <tt>m</tt> through <tt>p</tt>: <tt>[a-dm-p]</tt> (union)</td></tr>
111  * <tr><td valign="top" headers="construct classes"><tt>[a-z&&[def]]</tt></td>
112  * <td headers="matches"><tt>d</tt>, <tt>e</tt>, or <tt>f</tt> (intersection)</tr>
113  * <tr><td valign="top" headers="construct classes"><tt>[a-z&&[^bc]]</tt></td>
114  * <td headers="matches"><tt>a</tt> through <tt>z</tt>,
115  * except for <tt>b</tt> and <tt>c</tt>: <tt>[ad-z]</tt> (subtraction)</td></tr>
116  * <tr><td valign="top" headers="construct classes"><tt>[a-z&&[^m-p]]</tt></td>
117  * <td headers="matches"><tt>a</tt> through <tt>z</tt>,
118  * and not <tt>m</tt> through <tt>p</tt>: <tt>[a-lq-z]</tt>(subtraction)</td></tr>
119  * <tr><th>&nbsp;</th></tr>
120  *
121  * <tr align="left"><th colspan="2" id="predef">Predefined character classes</th></tr>
122  *
123  * <tr><td valign="top" headers="construct predef"><tt>.</tt></td>
124  * <td headers="matches">Any character (may or may not match <a HREF="#lt">line terminators</a>)</td></tr>
125  * <tr><td valign="top" headers="construct predef"><tt>\d</tt></td>
126  * <td headers="matches">A digit: <tt>[0-9]</tt></td></tr>
127  * <tr><td valign="top" headers="construct predef"><tt>\D</tt></td>
128  * <td headers="matches">A non-digit: <tt>[^0-9]</tt></td></tr>
129  * <tr><td valign="top" headers="construct predef"><tt>\s</tt></td>
130  * <td headers="matches">A whitespace character: <tt>[ \t\n\x0B\f\r]</tt></td></tr>
131  * <tr><td valign="top" headers="construct predef"><tt>\S</tt></td>
132  * <td headers="matches">A non-whitespace character: <tt>[^\s]</tt></td></tr>
133  * <tr><td valign="top" headers="construct predef"><tt>\w</tt></td>
134  * <td headers="matches">A word character: <tt>[a-zA-Z_0-9]</tt></td></tr>
135  * <tr><td valign="top" headers="construct predef"><tt>\W</tt></td>
136  * <td headers="matches">A non-word character: <tt>[^\w]</tt></td></tr>
137  *
138  * <tr><th>&nbsp;</th></tr>
139  * <tr align="left"><th colspan="2" id="posix">POSIX character classes</b> (US-ASCII only)<b></th></tr>
140  *
141  * <tr><td valign="top" headers="construct posix"><tt>\p{Lower}</tt></td>
142  * <td headers="matches">A lower-case alphabetic character: <tt>[a-z]</tt></td></tr>
143  * <tr><td valign="top" headers="construct posix"><tt>\p{Upper}</tt></td>
144  * <td headers="matches">An upper-case alphabetic character:<tt>[A-Z]</tt></td></tr>
145  * <tr><td valign="top" headers="construct posix"><tt>\p{ASCII}</tt></td>
146  * <td headers="matches">All ASCII:<tt>[\x00-\x7F]</tt></td></tr>
147  * <tr><td valign="top" headers="construct posix"><tt>\p{Alpha}</tt></td>
148  * <td headers="matches">An alphabetic character:<tt>[\p{Lower}\p{Upper}]</tt></td></tr>
149  * <tr><td valign="top" headers="construct posix"><tt>\p{Digit}</tt></td>
150  * <td headers="matches">A decimal digit: <tt>[0-9]</tt></td></tr>
151  * <tr><td valign="top" headers="construct posix"><tt>\p{Alnum}</tt></td>
152  * <td headers="matches">An alphanumeric character:<tt>[\p{Alpha}\p{Digit}]</tt></td></tr>
153  * <tr><td valign="top" headers="construct posix"><tt>\p{Punct}</tt></td>
154  * <td headers="matches">Punctuation: One of <tt>!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~</tt></td></tr>
155  * <!-- <tt>[\!"#\$%&'\(\)\*\+,\-\./:;\<=\>\?@\[\\\]\^_`\{\|\}~]</tt>
156  * <tt>[\X21-\X2F\X31-\X40\X5B-\X60\X7B-\X7E]</tt> -->
157  * <tr><td valign="top" headers="construct posix"><tt>\p{Graph}</tt></td>
158  * <td headers="matches">A visible character: <tt>[\p{Alnum}\p{Punct}]</tt></td></tr>
159  * <tr><td valign="top" headers="construct posix"><tt>\p{Print}</tt></td>
160  * <td headers="matches">A printable character: <tt>[\p{Graph}\x20]</tt></td></tr>
161  * <tr><td valign="top" headers="construct posix"><tt>\p{Blank}</tt></td>
162  * <td headers="matches">A space or a tab: <tt>[ \t]</tt></td></tr>
163  * <tr><td valign="top" headers="construct posix"><tt>\p{Cntrl}</tt></td>
164  * <td headers="matches">A control character: <tt>[\x00-\x1F\x7F]</td></tr>
165  * <tr><td valign="top" headers="construct posix"><tt>\p{XDigit}</tt></td>
166  * <td headers="matches">A hexadecimal digit: <tt>[0-9a-fA-F]</tt></td></tr>
167  * <tr><td valign="top" headers="construct posix"><tt>\p{Space}</tt></td>
168  * <td headers="matches">A whitespace character: <tt>[ \t\n\x0B\f\r]</tt></td></tr>
169  *
170  * <tr><th>&nbsp;</th></tr>
171  * <tr align="left"><th colspan="2">java.lang.Character classes (simple <a HREF="#jcc">java character type</a>)</th></tr>
172  *
173  * <tr><td valign="top"><tt>\p{javaLowerCase}</tt></td>
174  * <td>Equivalent to java.lang.Character.isLowerCase()</td></tr>
175  * <tr><td valign="top"><tt>\p{javaUpperCase}</tt></td>
176  * <td>Equivalent to java.lang.Character.isUpperCase()</td></tr>
177  * <tr><td valign="top"><tt>\p{javaWhitespace}</tt></td>
178  * <td>Equivalent to java.lang.Character.isWhitespace()</td></tr>
179  * <tr><td valign="top"><tt>\p{javaMirrored}</tt></td>
180  * <td>Equivalent to java.lang.Character.isMirrored()</td></tr>
181  *
182  * <tr><th>&nbsp;</th></tr>
183  * <tr align="left"><th colspan="2" id="unicode">Classes for Unicode blocks and categories</th></tr>
184  *
185  * <tr><td valign="top" headers="construct unicode"><tt>\p{InGreek}</tt></td>
186  * <td headers="matches">A character in the Greek&nbsp;block (simple <a HREF="#ubc">block</a>)</td></tr>
187  * <tr><td valign="top" headers="construct unicode"><tt>\p{Lu}</tt></td>
188  * <td headers="matches">An uppercase letter (simple <a HREF="#ubc">category</a>)</td></tr>
189  * <tr><td valign="top" headers="construct unicode"><tt>\p{Sc}</tt></td>
190  * <td headers="matches">A currency symbol</td></tr>
191  * <tr><td valign="top" headers="construct unicode"><tt>\P{InGreek}</tt></td>
192  * <td headers="matches">Any character except one in the Greek block (negation)</td></tr>
193  * <tr><td valign="top" headers="construct unicode"><tt>[\p{L}&&[^\p{Lu}]]&nbsp;</tt></td>
194  * <td headers="matches">Any letter except an uppercase letter (subtraction)</td></tr>
195  *
196  * <tr><th>&nbsp;</th></tr>
197  * <tr align="left"><th colspan="2" id="bounds">Boundary matchers</th></tr>
198  *
199  * <tr><td valign="top" headers="construct bounds"><tt>^</tt></td>
200  * <td headers="matches">The beginning of a line</td></tr>
201  * <tr><td valign="top" headers="construct bounds"><tt>$</tt></td>
202  * <td headers="matches">The end of a line</td></tr>
203  * <tr><td valign="top" headers="construct bounds"><tt>\b</tt></td>
204  * <td headers="matches">A word boundary</td></tr>
205  * <tr><td valign="top" headers="construct bounds"><tt>\B</tt></td>
206  * <td headers="matches">A non-word boundary</td></tr>
207  * <tr><td valign="top" headers="construct bounds"><tt>\A</tt></td>
208  * <td headers="matches">The beginning of the input</td></tr>
209  * <tr><td valign="top" headers="construct bounds"><tt>\G</tt></td>
210  * <td headers="matches">The end of the previous match</td></tr>
211  * <tr><td valign="top" headers="construct bounds"><tt>\Z</tt></td>
212  * <td headers="matches">The end of the input but for the final
213  * <a HREF="#lt">terminator</a>, if&nbsp;any</td></tr>
214  * <tr><td valign="top" headers="construct bounds"><tt>\z</tt></td>
215  * <td headers="matches">The end of the input</td></tr>
216  *
217  * <tr><th>&nbsp;</th></tr>
218  * <tr align="left"><th colspan="2" id="greedy">Greedy quantifiers</th></tr>
219  *
220  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>?</tt></td>
221  * <td headers="matches"><i>X</i>, once or not at all</td></tr>
222  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>*</tt></td>
223  * <td headers="matches"><i>X</i>, zero or more times</td></tr>
224  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>+</tt></td>
225  * <td headers="matches"><i>X</i>, one or more times</td></tr>
226  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>{</tt><i>n</i><tt>}</tt></td>
227  * <td headers="matches"><i>X</i>, exactly <i>n</i> times</td></tr>
228  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>{</tt><i>n</i><tt>,}</tt></td>
229  * <td headers="matches"><i>X</i>, at least <i>n</i> times</td></tr>
230  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>{</tt><i>n</i><tt>,</tt><i>m</i><tt>}</tt></td>
231  * <td headers="matches"><i>X</i>, at least <i>n</i> but not more than <i>m</i> times</td></tr>
232  *
233  * <tr><th>&nbsp;</th></tr>
234  * <tr align="left"><th colspan="2" id="reluc">Reluctant quantifiers</th></tr>
235  *
236  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>??</tt></td>
237  * <td headers="matches"><i>X</i>, once or not at all</td></tr>
238  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>*?</tt></td>
239  * <td headers="matches"><i>X</i>, zero or more times</td></tr>
240  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>+?</tt></td>
241  * <td headers="matches"><i>X</i>, one or more times</td></tr>
242  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>{</tt><i>n</i><tt>}?</tt></td>
243  * <td headers="matches"><i>X</i>, exactly <i>n</i> times</td></tr>
244  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>{</tt><i>n</i><tt>,}?</tt></td>
245  * <td headers="matches"><i>X</i>, at least <i>n</i> times</td></tr>
246  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>{</tt><i>n</i><tt>,</tt><i>m</i><tt>}?</tt></td>
247  * <td headers="matches"><i>X</i>, at least <i>n</i> but not more than <i>m</i> times</td></tr>
248  *
249  * <tr><th>&nbsp;</th></tr>
250  * <tr align="left"><th colspan="2" id="poss">Possessive quantifiers</th></tr>
251  *
252  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>?+</tt></td>
253  * <td headers="matches"><i>X</i>, once or not at all</td></tr>
254  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>*+</tt></td>
255  * <td headers="matches"><i>X</i>, zero or more times</td></tr>
256  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>++</tt></td>
257  * <td headers="matches"><i>X</i>, one or more times</td></tr>
258  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>{</tt><i>n</i><tt>}+</tt></td>
259  * <td headers="matches"><i>X</i>, exactly <i>n</i> times</td></tr>
260  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>{</tt><i>n</i><tt>,}+</tt></td>
261  * <td headers="matches"><i>X</i>, at least <i>n</i> times</td></tr>
262  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>{</tt><i>n</i><tt>,</tt><i>m</i><tt>}+</tt></td>
263  * <td headers="matches"><i>X</i>, at least <i>n</i> but not more than <i>m</i> times</td></tr>
264  *
265  * <tr><th>&nbsp;</th></tr>
266  * <tr align="left"><th colspan="2" id="logical">Logical operators</th></tr>
267  *
268  * <tr><td valign="top" headers="construct logical"><i>XY</i></td>
269  * <td headers="matches"><i>X</i> followed by <i>Y</i></td></tr>
270  * <tr><td valign="top" headers="construct logical"><i>X</i><tt>|</tt><i>Y</i></td>
271  * <td headers="matches">Either <i>X</i> or <i>Y</i></td></tr>
272  * <tr><td valign="top" headers="construct logical"><tt>(</tt><i>X</i><tt>)</tt></td>
273  * <td headers="matches">X, as a <a HREF="#cg">capturing group</a></td></tr>
274  *
275  * <tr><th>&nbsp;</th></tr>
276  * <tr align="left"><th colspan="2" id="backref">Back references</th></tr>
277  *
278  * <tr><td valign="bottom" headers="construct backref"><tt>\</tt><i>n</i></td>
279  * <td valign="bottom" headers="matches">Whatever the <i>n</i><sup>th</sup>
280  * <a HREF="#cg">capturing group</a> matched</td></tr>
281  *
282  * <tr><th>&nbsp;</th></tr>
283  * <tr align="left"><th colspan="2" id="quot">Quotation</th></tr>
284  *
285  * <tr><td valign="top" headers="construct quot"><tt>\</tt></td>
286  * <td headers="matches">Nothing, but quotes the following character</tt></td></tr>
287  * <tr><td valign="top" headers="construct quot"><tt>\Q</tt></td>
288  * <td headers="matches">Nothing, but quotes all characters until <tt>\E</tt></td></tr>
289  * <tr><td valign="top" headers="construct quot"><tt>\E</tt></td>
290  * <td headers="matches">Nothing, but ends quoting started by <tt>\Q</tt></td></tr>
291  * <!-- Metachars: !$()*+.<>?[\]^{|} -->
292  *
293  * <tr><th>&nbsp;</th></tr>
294  * <tr align="left"><th colspan="2" id="special">Special constructs (non-capturing)</th></tr>
295  *
296  * <tr><td valign="top" headers="construct special"><tt>(?:</tt><i>X</i><tt>)</tt></td>
297  * <td headers="matches"><i>X</i>, as a non-capturing group</td></tr>
298  * <tr><td valign="top" headers="construct special"><tt>(?idmsux-idmsux)&nbsp;</tt></td>
299  * <td headers="matches">Nothing, but turns match flags on - off</td></tr>
300  * <tr><td valign="top" headers="construct special"><tt>(?idmsux-idmsux:</tt><i>X</i><tt>)</tt>&nbsp;&nbsp;</td>
301  * <td headers="matches"><i>X</i>, as a <a HREF="#cg">non-capturing group</a> with the
302  * given flags on - off</td></tr>
303  * <tr><td valign="top" headers="construct special"><tt>(?=</tt><i>X</i><tt>)</tt></td>
304  * <td headers="matches"><i>X</i>, via zero-width positive lookahead</td></tr>
305  * <tr><td valign="top" headers="construct special"><tt>(?!</tt><i>X</i><tt>)</tt></td>
306  * <td headers="matches"><i>X</i>, via zero-width negative lookahead</td></tr>
307  * <tr><td valign="top" headers="construct special"><tt>(?&lt;=</tt><i>X</i><tt>)</tt></td>
308  * <td headers="matches"><i>X</i>, via zero-width positive lookbehind</td></tr>
309  * <tr><td valign="top" headers="construct special"><tt>(?&lt;!</tt><i>X</i><tt>)</tt></td>
310  * <td headers="matches"><i>X</i>, via zero-width negative lookbehind</td></tr>
311  * <tr><td valign="top" headers="construct special"><tt>(?&gt;</tt><i>X</i><tt>)</tt></td>
312  * <td headers="matches"><i>X</i>, as an independent, non-capturing group</td></tr>
313  *
314  * </table>
315  *
316  * <hr>
317  *
318  *
319  * <a name="bs">
320  * <h4> Backslashes, escapes, and quoting </h4>
321  *
322  * <p> The backslash character (<tt>'\'</tt>) serves to introduce escaped
323  * constructs, as defined in the table above, as well as to quote characters
324  * that otherwise would be interpreted as unescaped constructs. Thus the
325  * expression <tt>\\</tt> matches a single backslash and <tt>\{</tt> matches a
326  * left brace.
327  *
328  * <p> It is an error to use a backslash prior to any alphabetic character that
329  * does not denote an escaped construct; these are reserved for future
330  * extensions to the regular-expression language. A backslash may be used
331  * prior to a non-alphabetic character regardless of whether that character is
332  * part of an unescaped construct.
333  *
334  * <p> Backslashes within string literals in Java source code are interpreted
335  * as required by the <a
336  * HREF="http://java.sun.com/docs/books/jls/second_edition/html/">Java Language
337  * Specification</a> as either <a
338  * HREF="http://java.sun.com/docs/books/jls/second_edition/html/lexical.doc.html#100850">Unicode
339  * escapes</a> or other <a
340  * HREF="http://java.sun.com/docs/books/jls/second_edition/html/lexical.doc.html#101089">character
341  * escapes</a>. It is therefore necessary to double backslashes in string
342  * literals that represent regular expressions to protect them from
343  * interpretation by the Java bytecode compiler. The string literal
344  * <tt>"&#92;b"</tt>, for example, matches a single backspace character when
345  * interpreted as a regular expression, while <tt>"&#92;&#92;b"</tt> matches a
346  * word boundary. The string literal <tt>"&#92;(hello&#92;)"</tt> is illegal
347  * and leads to a compile-time error; in order to match the string
348  * <tt>(hello)</tt> the string literal <tt>"&#92;&#92;(hello&#92;&#92;)"</tt>
349  * must be used.
350  *
351  * <a name="cc">
352  * <h4> Character Classes </h4>
353  *
354  * <p> Character classes may appear within other character classes, and
355  * may be composed by the union operator (implicit) and the intersection
356  * operator (<tt>&amp;&amp;</tt>).
357  * The union operator denotes a class that contains every character that is
358  * in at least one of its operand classes. The intersection operator
359  * denotes a class that contains every character that is in both of its
360  * operand classes.
361  *
362  * <p> The precedence of character-class operators is as follows, from
363  * highest to lowest:
364  *
365  * <blockquote><table border="0" cellpadding="1" cellspacing="0"
366  * summary="Precedence of character class operators.">
367  * <tr><th>1&nbsp;&nbsp;&nbsp;&nbsp;</th>
368  * <td>Literal escape&nbsp;&nbsp;&nbsp;&nbsp;</td>
369  * <td><tt>\x</tt></td></tr>
370  * <tr><th>2&nbsp;&nbsp;&nbsp;&nbsp;</th>
371  * <td>Grouping</td>
372  * <td><tt>[...]</tt></td></tr>
373  * <tr><th>3&nbsp;&nbsp;&nbsp;&nbsp;</th>
374  * <td>Range</td>
375  * <td><tt>a-z</tt></td></tr>
376  * <tr><th>4&nbsp;&nbsp;&nbsp;&nbsp;</th>
377  * <td>Union</td>
378  * <td><tt>[a-e][i-u]<tt></td></tr>
379  * <tr><th>5&nbsp;&nbsp;&nbsp;&nbsp;</th>
380  * <td>Intersection</td>
381  * <td><tt>[a-z&&[aeiou]]</tt></td></tr>
382  * </table></blockquote>
383  *
384  * <p> Note that a different set of metacharacters are in effect inside
385  * a character class than outside a character class. For instance, the
386  * regular expression <tt>.</tt> loses its special meaning inside a
387  * character class, while the expression <tt>-</tt> becomes a range
388  * forming metacharacter.
389  *
390  * <a name="lt">
391  * <h4> Line terminators </h4>
392  *
393  * <p> A <i>line terminator</i> is a one- or two-character sequence that marks
394  * the end of a line of the input character sequence. The following are
395  * recognized as line terminators:
396  *
397  * <ul>
398  *
399  * <li> A newline (line feed) character&nbsp;(<tt>'\n'</tt>),
400  *
401  * <li> A carriage-return character followed immediately by a newline
402  * character&nbsp;(<tt>"\r\n"</tt>),
403  *
404  * <li> A standalone carriage-return character&nbsp;(<tt>'\r'</tt>),
405  *
406  * <li> A next-line character&nbsp;(<tt>'&#92;u0085'</tt>),
407  *
408  * <li> A line-separator character&nbsp;(<tt>'&#92;u2028'</tt>), or
409  *
410  * <li> A paragraph-separator character&nbsp;(<tt>'&#92;u2029</tt>).
411  *
412  * </ul>
413  * <p>If {@link #UNIX_LINES} mode is activated, then the only line terminators
414  * recognized are newline characters.
415  *
416  * <p> The regular expression <tt>.</tt> matches any character except a line
417  * terminator unless the {@link #DOTALL} flag is specified.
418  *
419  * <p> By default, the regular expressions <tt>^</tt> and <tt>$</tt> ignore
420  * line terminators and only match at the beginning and the end, respectively,
421  * of the entire input sequence. If {@link #MULTILINE} mode is activated then
422  * <tt>^</tt> matches at the beginning of input and after any line terminator
423  * except at the end of input. When in {@link #MULTILINE} mode <tt>$</tt>
424  * matches just before a line terminator or the end of the input sequence.
425  *
426  * <a name="cg">
427  * <h4> Groups and capturing </h4>
428  *
429  * <p> Capturing groups are numbered by counting their opening parentheses from
430  * left to right. In the expression <tt>((A)(B(C)))</tt>, for example, there
431  * are four such groups: </p>
432  *
433  * <blockquote><table cellpadding=1 cellspacing=0 summary="Capturing group numberings">
434  * <tr><th>1&nbsp;&nbsp;&nbsp;&nbsp;</th>
435  * <td><tt>((A)(B(C)))</tt></td></tr>
436  * <tr><th>2&nbsp;&nbsp;&nbsp;&nbsp;</th>
437  * <td><tt>(A)</tt></td></tr>
438  * <tr><th>3&nbsp;&nbsp;&nbsp;&nbsp;</th>
439  * <td><tt>(B(C))</tt></td></tr>
440  * <tr><th>4&nbsp;&nbsp;&nbsp;&nbsp;</th>
441  * <td><tt>(C)</tt></td></tr>
442  * </table></blockquote>
443  *
444  * <p> Group zero always stands for the entire expression.
445  *
446  * <p> Capturing groups are so named because, during a match, each subsequence
447  * of the input sequence that matches such a group is saved. The captured
448  * subsequence may be used later in the expression, via a back reference, and
449  * may also be retrieved from the matcher once the match operation is complete.
450  *
451  * <p> The captured input associated with a group is always the subsequence
452  * that the group most recently matched. If a group is evaluated a second time
453  * because of quantification then its previously-captured value, if any, will
454  * be retained if the second evaluation fails. Matching the string
455  * <tt>"aba"</tt> against the expression <tt>(a(b)?)+</tt>, for example, leaves
456  * group two set to <tt>"b"</tt>. All captured input is discarded at the
457  * beginning of each match.
458  *
459  * <p> Groups beginning with <tt>(?</tt> are pure, <i>non-capturing</i> groups
460  * that do not capture text and do not count towards the group total.
461  *
462  *
463  * <h4> Unicode support </h4>
464  *
465  * <p> This class is in conformance with Level 1 of <a
466  * HREF="http://www.unicode.org/reports/tr18/"><i>Unicode Technical
467  * Standard #18: Unicode Regular Expression Guidelines</i></a>, plus RL2.1
468  * Canonical Equivalents.
469  *
470  * <p> Unicode escape sequences such as <tt>&#92;u2014</tt> in Java source code
471  * are processed as described in <a
472  * HREF="http://java.sun.com/docs/books/jls/second_edition/html/lexical.doc.html#100850">§3.3</a>
473  * of the Java Language Specification. Such escape sequences are also
474  * implemented directly by the regular-expression parser so that Unicode
475  * escapes can be used in expressions that are read from files or from the
476  * keyboard. Thus the strings <tt>"&#92;u2014"</tt> and <tt>"\\u2014"</tt>,
477  * while not equal, compile into the same pattern, which matches the character
478  * with hexadecimal value <tt>0x2014</tt>.
479  *
480  * <a name="ubc"> <p>Unicode blocks and categories are written with the
481  * <tt>\p</tt> and <tt>\P</tt> constructs as in
482  * Perl. <tt>\p{</tt><i>prop</i><tt>}</tt> matches if the input has the
483  * property <i>prop</i>, while \P{</tt><i>prop</i><tt>}</tt> does not match if
484  * the input has that property. Blocks are specified with the prefix
485  * <tt>In</tt>, as in <tt>InMongolian</tt>. Categories may be specified with
486  * the optional prefix <tt>Is</tt>: Both <tt>\p{L}</tt> and <tt>\p{IsL}</tt>
487  * denote the category of Unicode letters. Blocks and categories can be used
488  * both inside and outside of a character class.
489  *
490  * <p> The supported categories are those of
491  * <a HREF="http://www.unicode.org/unicode/standard/standard.html">
492  * <i>The Unicode Standard</i></a> in the version specified by the
493  * {@link java.lang.Character Character} class. The category names are those
494  * defined in the Standard, both normative and informative.
495  * The block names supported by <code>Pattern</code> are the valid block names
496  * accepted and defined by
497  * {@link java.lang.Character.UnicodeBlock#forName(String) UnicodeBlock.forName}.
498  *
499  * <a name="jcc"> <p>Categories that behave like the java.lang.Character
500  * boolean is<i>methodname</i> methods (except for the deprecated ones) are
501  * available through the same <tt>\p{</tt><i>prop</i><tt>}</tt> syntax where
502  * the specified property has the name <tt>java<i>methodname</i></tt>.
503  *
504  * <h4> Comparison to Perl 5 </h4>
505  *
506  * <p>The <code>Pattern</code> engine performs traditional NFA-based matching
507  * with ordered alternation as occurs in Perl 5.
508  *
509  * <p> Perl constructs not supported by this class: </p>
510  *
511  * <ul>
512  *
513  * <li><p> The conditional constructs <tt>(?{</tt><i>X</i><tt>})</tt> and
514  * <tt>(?(</tt><i>condition</i><tt>)</tt><i>X</i><tt>|</tt><i>Y</i><tt>)</tt>,
515  * </p></li>
516  *
517  * <li><p> The embedded code constructs <tt>(?{</tt><i>code</i><tt>})</tt>
518  * and <tt>(??{</tt><i>code</i><tt>})</tt>,</p></li>
519  *
520  * <li><p> The embedded comment syntax <tt>(?#comment)</tt>, and </p></li>
521  *
522  * <li><p> The preprocessing operations <tt>\l</tt> <tt>&#92;u</tt>,
523  * <tt>\L</tt>, and <tt>\U</tt>. </p></li>
524  *
525  * </ul>
526  *
527  * <p> Constructs supported by this class but not by Perl: </p>
528  *
529  * <ul>
530  *
531  * <li><p> Possessive quantifiers, which greedily match as much as they can
532  * and do not back off, even when doing so would allow the overall match to
533  * succeed. </p></li>
534  *
535  * <li><p> Character-class union and intersection as described
536  * <a HREF="#cc">above</a>.</p></li>
537  *
538  * </ul>
539  *
540  * <p> Notable differences from Perl: </p>
541  *
542  * <ul>
543  *
544  * <li><p> In Perl, <tt>\1</tt> through <tt>\9</tt> are always interpreted
545  * as back references; a backslash-escaped number greater than <tt>9</tt> is
546  * treated as a back reference if at least that many subexpressions exist,
547  * otherwise it is interpreted, if possible, as an octal escape. In this
548  * class octal escapes must always begin with a zero. In this class,
549  * <tt>\1</tt> through <tt>\9</tt> are always interpreted as back
550  * references, and a larger number is accepted as a back reference if at
551  * least that many subexpressions exist at that point in the regular
552  * expression, otherwise the parser will drop digits until the number is
553  * smaller or equal to the existing number of groups or it is one digit.
554  * </p></li>
555  *
556  * <li><p> Perl uses the <tt>g</tt> flag to request a match that resumes
557  * where the last match left off. This functionality is provided implicitly
558  * by the {@link Matcher} class: Repeated invocations of the {@link
559  * Matcher#find find} method will resume where the last match left off,
560  * unless the matcher is reset. </p></li>
561  *
562  * <li><p> In Perl, embedded flags at the top level of an expression affect
563  * the whole expression. In this class, embedded flags always take effect
564  * at the point at which they appear, whether they are at the top level or
565  * within a group; in the latter case, flags are restored at the end of the
566  * group just as in Perl. </p></li>
567  *
568  * <li><p> Perl is forgiving about malformed matching constructs, as in the
569  * expression <tt>*a</tt>, as well as dangling brackets, as in the
570  * expression <tt>abc]</tt>, and treats them as literals. This
571  * class also accepts dangling brackets but is strict about dangling
572  * metacharacters like +, ? and *, and will throw a
573  * {@link PatternSyntaxException} if it encounters them. </p></li>
574  *
575  * </ul>
576  *
577  *
578  * <p> For a more precise description of the behavior of regular expression
579  * constructs, please see <a HREF="http://www.oreilly.com/catalog/regex2/">
580  * <i>Mastering Regular Expressions, 2nd Edition</i>, Jeffrey E. F. Friedl,
581  * O'Reilly and Associates, 2002.</a>
582  * </p>
583  *
584  * @see java.lang.String#split(String, int)
585  * @see java.lang.String#split(String)
586  *
587  * @author Mike McCloskey
588  * @author Mark Reinhold
589  * @author JSR-51 Expert Group
590  * @version 1.113, 07/05/07
591  * @since 1.4
592  * @spec JSR-51
593  */

594
595 public final class Pattern
596     implements java.io.Serializable JavaDoc
597 {
598
599     /**
600      * Regular expression modifier values. Instead of being passed as
601      * arguments, they can also be passed as inline modifiers.
602      * For example, the following statements have the same effect.
603      * <pre>
604      * RegExp r1 = RegExp.compile("abc", Pattern.I|Pattern.M);
605      * RegExp r2 = RegExp.compile("(?im)abc", 0);
606      * </pre>
607      *
608      * The flags are duplicated so that the familiar Perl match flag
609      * names are available.
610      */

611
612     /**
613      * Enables Unix lines mode.
614      *
615      * <p> In this mode, only the <tt>'\n'</tt> line terminator is recognized
616      * in the behavior of <tt>.</tt>, <tt>^</tt>, and <tt>$</tt>.
617      *
618      * <p> Unix lines mode can also be enabled via the embedded flag
619      * expression&nbsp;<tt>(?d)</tt>.
620      */

621     public static final int UNIX_LINES = 0x01;
622
623     /**
624      * Enables case-insensitive matching.
625      *
626      * <p> By default, case-insensitive matching assumes that only characters
627      * in the US-ASCII charset are being matched. Unicode-aware
628      * case-insensitive matching can be enabled by specifying the {@link
629      * #UNICODE_CASE} flag in conjunction with this flag.
630      *
631      * <p> Case-insensitive matching can also be enabled via the embedded flag
632      * expression&nbsp;<tt>(?i)</tt>.
633      *
634      * <p> Specifying this flag may impose a slight performance penalty. </p>
635      */

636     public static final int CASE_INSENSITIVE = 0x02;
637
638     /**
639      * Permits whitespace and comments in pattern.
640      *
641      * <p> In this mode, whitespace is ignored, and embedded comments starting
642      * with <tt>#</tt> are ignored until the end of a line.
643      *
644      * <p> Comments mode can also be enabled via the embedded flag
645      * expression&nbsp;<tt>(?x)</tt>.
646      */

647     public static final int COMMENTS = 0x04;
648
649     /**
650      * Enables multiline mode.
651      *
652      * <p> In multiline mode the expressions <tt>^</tt> and <tt>$</tt> match
653      * just after or just before, respectively, a line terminator or the end of
654      * the input sequence. By default these expressions only match at the
655      * beginning and the end of the entire input sequence.
656      *
657      * <p> Multiline mode can also be enabled via the embedded flag
658      * expression&nbsp;<tt>(?m)</tt>. </p>
659      */

660     public static final int MULTILINE = 0x08;
661
662     /**
663      * Enables literal parsing of the pattern.
664      *
665      * <p> When this flag is specified then the input string that specifies
666      * the pattern is treated as a sequence of literal characters.
667      * Metacharacters or escape sequences in the input sequence will be
668      * given no special meaning.
669      *
670      * <p>The flags CASE_INSENSITIVE and UNICODE_CASE retain their impact on
671      * matching when used in conjunction with this flag. The other flags
672      * become superfluous.
673      *
674      * <p> There is no embedded flag character for enabling literal parsing.
675      */

676     public static final int LITERAL = 0x10;
677
678     /**
679      * Enables dotall mode.
680      *
681      * <p> In dotall mode, the expression <tt>.</tt> matches any character,
682      * including a line terminator. By default this expression does not match
683      * line terminators.
684      *
685      * <p> Dotall mode can also be enabled via the embedded flag
686      * expression&nbsp;<tt>(?s)</tt>. (The <tt>s</tt> is a mnemonic for
687      * "single-line" mode, which is what this is called in Perl.) </p>
688      */

689     public static final int DOTALL = 0x20;
690
691     /**
692      * Enables Unicode-aware case folding.
693      *
694      * <p> When this flag is specified then case-insensitive matching, when
695      * enabled by the {@link #CASE_INSENSITIVE} flag, is done in a manner
696      * consistent with the Unicode Standard. By default, case-insensitive
697      * matching assumes that only characters in the US-ASCII charset are being
698      * matched.
699      *
700      * <p> Unicode-aware case folding can also be enabled via the embedded flag
701      * expression&nbsp;<tt>(?u)</tt>.
702      *
703      * <p> Specifying this flag may impose a performance penalty. </p>
704      */

705     public static final int UNICODE_CASE = 0x40;
706
707     /**
708      * Enables canonical equivalence.
709      *
710      * <p> When this flag is specified then two characters will be considered
711      * to match if, and only if, their full canonical decompositions match.
712      * The expression <tt>"a&#92;u030A"</tt>, for example, will match the
713      * string <tt>"å"</tt> when this flag is specified. By default,
714      * matching does not take canonical equivalence into account.
715      *
716      * <p> There is no embedded flag character for enabling canonical
717      * equivalence.
718      *
719      * <p> Specifying this flag may impose a performance penalty. </p>
720      */

721     public static final int CANON_EQ = 0x80;
722
723     /* Pattern has only two serialized components: The pattern string
724      * and the flags, which are all that is needed to recompile the pattern
725      * when it is deserialized.
726      */

727
728     /** use serialVersionUID from Merlin b59 for interoperability */
729     private static final long serialVersionUID = 5073258162644648461L;
730
731     /**
732      * The original regular-expression pattern string.
733      *
734      * @serial
735      */

736     private String JavaDoc pattern;
737
738     /**
739      * The original pattern flags.
740      *
741      * @serial
742      */

743     private int flags;
744
745     /**
746      * Boolean indicating this Pattern is compiled; this is necessary in order
747      * to lazily compile deserialized Patterns.
748      */

749     private transient volatile boolean compiled = false;
750
751     /**
752      * The normalized pattern string.
753      */

754     private transient String JavaDoc normalizedPattern;
755
756     /**
757      * The starting point of state machine for the find operation. This allows
758      * a match to start anywhere in the input.
759      */

760     transient Node root;
761
762     /**
763      * The root of object tree for a match operation. The pattern is matched
764      * at the beginning. This may include a find that uses BnM or a First
765      * node.
766      */

767     transient Node matchRoot;
768
769     /**
770      * Temporary storage used by parsing pattern slice.
771      */

772     transient int[] buffer;
773
774     /**
775      * Temporary storage used while parsing group references.
776      */

777     transient GroupHead[] groupNodes;
778
779     /**
780      * Temporary null terminating char array used by pattern compiling.
781      */

782     private transient int[] temp;
783
784     /**
785      * The number of capturing groups in this Pattern. Used by matchers to
786      * allocate storage needed to perform a match.
787      */

788     transient int capturingGroupCount;
789
790     /**
791      * The local variable count used by parsing tree. Used by matchers to
792      * allocate storage needed to perform a match.
793      */

794     transient int localCount;
795
796     /**
797      * Index into the pattern string that keeps track of how much has been
798      * parsed.
799      */

800     private transient int cursor;
801
802     /**
803      * Holds the length of the pattern string.
804      */

805     private transient int patternLength;
806
807     /**
808      * Compiles the given regular expression into a pattern. </p>
809      *
810      * @param regex
811      * The expression to be compiled
812      *
813      * @throws PatternSyntaxException
814      * If the expression's syntax is invalid
815      */

816     public static Pattern JavaDoc compile(String JavaDoc regex) {
817         return new Pattern JavaDoc(regex, 0);
818     }
819
820     /**
821      * Compiles the given regular expression into a pattern with the given
822      * flags. </p>
823      *
824      * @param regex
825      * The expression to be compiled
826      *
827      * @param flags
828      * Match flags, a bit mask that may include
829      * {@link #CASE_INSENSITIVE}, {@link #MULTILINE}, {@link #DOTALL},
830      * {@link #UNICODE_CASE}, and {@link #CANON_EQ}
831      *
832      * @throws IllegalArgumentException
833      * If bit values other than those corresponding to the defined
834      * match flags are set in <tt>flags</tt>
835      *
836      * @throws PatternSyntaxException
837      * If the expression's syntax is invalid
838      */

839     public static Pattern JavaDoc compile(String JavaDoc regex, int flags) {
840         return new Pattern JavaDoc(regex, flags);
841     }
842
843     /**
844      * Returns the regular expression from which this pattern was compiled.
845      * </p>
846      *
847      * @return The source of this pattern
848      */

849     public String JavaDoc pattern() {
850         return pattern;
851     }
852
853     /**
854      * <p>Returns the string representation of this pattern. This
855      * is the regular expression from which this pattern was
856      * compiled.</p>
857      *
858      * @return The string representation of this pattern
859      * @since 1.5
860      */

861     public String JavaDoc toString() {
862         return pattern;
863     }
864
865     /**
866      * Creates a matcher that will match the given input against this pattern.
867      * </p>
868      *
869      * @param input
870      * The character sequence to be matched
871      *
872      * @return A new matcher for this pattern
873      */

874     public Matcher JavaDoc matcher(CharSequence JavaDoc input) {
875         synchronized(this) {
876             if (!compiled)
877                 compile();
878         }
879         Matcher JavaDoc m = new Matcher JavaDoc(this, input);
880         return m;
881     }
882
883     /**
884      * Returns this pattern's match flags. </p>
885      *
886      * @return The match flags specified when this pattern was compiled
887      */

888     public int flags() {
889         return flags;
890     }
891
892     /**
893      * Compiles the given regular expression and attempts to match the given
894      * input against it.
895      *
896      * <p> An invocation of this convenience method of the form
897      *
898      * <blockquote><pre>
899      * Pattern.matches(regex, input);</pre></blockquote>
900      *
901      * behaves in exactly the same way as the expression
902      *
903      * <blockquote><pre>
904      * Pattern.compile(regex).matcher(input).matches()</pre></blockquote>
905      *
906      * <p> If a pattern is to be used multiple times, compiling it once and reusing
907      * it will be more efficient than invoking this method each time. </p>
908      *
909      * @param regex
910      * The expression to be compiled
911      *
912      * @param input
913      * The character sequence to be matched
914      *
915      * @throws PatternSyntaxException
916      * If the expression's syntax is invalid
917      */

918     public static boolean matches(String JavaDoc regex, CharSequence JavaDoc input) {
919         Pattern JavaDoc p = Pattern.compile(regex);
920         Matcher JavaDoc m = p.matcher(input);
921         return m.matches();
922     }
923
924     /**
925      * Splits the given input sequence around matches of this pattern.
926      *
927      * <p> The array returned by this method contains each substring of the
928      * input sequence that is terminated by another subsequence that matches
929      * this pattern or is terminated by the end of the input sequence. The
930      * substrings in the array are in the order in which they occur in the
931      * input. If this pattern does not match any subsequence of the input then
932      * the resulting array has just one element, namely the input sequence in
933      * string form.
934      *
935      * <p> The <tt>limit</tt> parameter controls the number of times the
936      * pattern is applied and therefore affects the length of the resulting
937      * array. If the limit <i>n</i> is greater than zero then the pattern
938      * will be applied at most <i>n</i>&nbsp;-&nbsp;1 times, the array's
939      * length will be no greater than <i>n</i>, and the array's last entry
940      * will contain all input beyond the last matched delimiter. If <i>n</i>
941      * is non-positive then the pattern will be applied as many times as
942      * possible and the array can have any length. If <i>n</i> is zero then
943      * the pattern will be applied as many times as possible, the array can
944      * have any length, and trailing empty strings will be discarded.
945      *
946      * <p> The input <tt>"boo:and:foo"</tt>, for example, yields the following
947      * results with these parameters:
948      *
949      * <blockquote><table cellpadding=1 cellspacing=0
950      * summary="Split examples showing regex, limit, and result">
951      * <tr><th><P align="left"><i>Regex&nbsp;&nbsp;&nbsp;&nbsp;</i></th>
952      * <th><P align="left"><i>Limit&nbsp;&nbsp;&nbsp;&nbsp;</i></th>
953      * <th><P align="left"><i>Result&nbsp;&nbsp;&nbsp;&nbsp;</i></th></tr>
954      * <tr><td align=center>:</td>
955      * <td align=center>2</td>
956      * <td><tt>{ "boo", "and:foo" }</tt></td></tr>
957      * <tr><td align=center>:</td>
958      * <td align=center>5</td>
959      * <td><tt>{ "boo", "and", "foo" }</tt></td></tr>
960      * <tr><td align=center>:</td>
961      * <td align=center>-2</td>
962      * <td><tt>{ "boo", "and", "foo" }</tt></td></tr>
963      * <tr><td align=center>o</td>
964      * <td align=center>5</td>
965      * <td><tt>{ "b", "", ":and:f", "", "" }</tt></td></tr>
966      * <tr><td align=center>o</td>
967      * <td align=center>-2</td>
968      * <td><tt>{ "b", "", ":and:f", "", "" }</tt></td></tr>
969      * <tr><td align=center>o</td>
970      * <td align=center>0</td>
971      * <td><tt>{ "b", "", ":and:f" }</tt></td></tr>
972      * </table></blockquote>
973      *
974      *
975      * @param input
976      * The character sequence to be split
977      *
978      * @param limit
979      * The result threshold, as described above
980      *
981      * @return The array of strings computed by splitting the input
982      * around matches of this pattern
983      */

984     public String JavaDoc[] split(CharSequence JavaDoc input, int limit) {
985         int index = 0;
986         boolean matchLimited = limit > 0;
987         ArrayList JavaDoc matchList = new ArrayList JavaDoc();
988         Matcher JavaDoc m = matcher(input);
989
990         // Add segments before each match found
991
while(m.find()) {
992             if (!matchLimited || matchList.size() < limit - 1) {
993                 String JavaDoc match = input.subSequence(index, m.start()).toString();
994                 matchList.add(match);
995                 index = m.end();
996             } else if (matchList.size() == limit - 1) { // last one
997
String JavaDoc match = input.subSequence(index,
998                                                  input.length()).toString();
999                 matchList.add(match);
1000                index = m.end();
1001            }
1002        }
1003
1004        // If no match was found, return this
1005
if (index == 0)
1006            return new String JavaDoc[] {input.toString()};
1007
1008        // Add remaining segment
1009
if (!matchLimited || matchList.size() < limit)
1010            matchList.add(input.subSequence(index, input.length()).toString());
1011
1012        // Construct result
1013
int resultSize = matchList.size();
1014        if (limit == 0)
1015            while (resultSize > 0 && matchList.get(resultSize-1).equals(""))
1016                resultSize--;
1017        String JavaDoc[] result = new String JavaDoc[resultSize];
1018        return (String JavaDoc[])matchList.subList(0, resultSize).toArray(result);
1019    }
1020
1021    /**
1022     * Splits the given input sequence around matches of this pattern.
1023     *
1024     * <p> This method works as if by invoking the two-argument {@link
1025     * #split(java.lang.CharSequence, int) split} method with the given input
1026     * sequence and a limit argument of zero. Trailing empty strings are
1027     * therefore not included in the resulting array. </p>
1028     *
1029     * <p> The input <tt>"boo:and:foo"</tt>, for example, yields the following
1030     * results with these expressions:
1031     *
1032     * <blockquote><table cellpadding=1 cellspacing=0
1033     * summary="Split examples showing regex and result">
1034     * <tr><th><P align="left"><i>Regex&nbsp;&nbsp;&nbsp;&nbsp;</i></th>
1035     * <th><P align="left"><i>Result</i></th></tr>
1036     * <tr><td align=center>:</td>
1037     * <td><tt>{ "boo", "and", "foo" }</tt></td></tr>
1038     * <tr><td align=center>o</td>
1039     * <td><tt>{ "b", "", ":and:f" }</tt></td></tr>
1040     * </table></blockquote>
1041     *
1042     *
1043     * @param input
1044     * The character sequence to be split
1045     *
1046     * @return The array of strings computed by splitting the input
1047     * around matches of this pattern
1048     */

1049    public String JavaDoc[] split(CharSequence JavaDoc input) {
1050        return split(input, 0);
1051    }
1052
1053    /**
1054     * Returns a literal pattern <code>String</code> for the specified
1055     * <code>String</code>.
1056     *
1057     * <p>This method produces a <code>String</code> that can be used to
1058     * create a <code>Pattern</code> that would match the string
1059     * <code>s</code> as if it were a literal pattern.</p> Metacharacters
1060     * or escape sequences in the input sequence will be given no special
1061     * meaning.
1062     *
1063     * @param s The string to be literalized
1064     * @return A literal string replacement
1065     * @since 1.5
1066     */

1067    public static String JavaDoc quote(String JavaDoc s) {
1068        int slashEIndex = s.indexOf("\\E");
1069        if (slashEIndex == -1)
1070            return "\\Q" + s + "\\E";
1071
1072        StringBuilder JavaDoc sb = new StringBuilder JavaDoc(s.length() * 2);
1073        sb.append("\\Q");
1074        slashEIndex = 0;
1075        int current = 0;
1076        while ((slashEIndex = s.indexOf("\\E", current)) != -1) {
1077            sb.append(s.substring(current, slashEIndex));
1078            current = slashEIndex + 2;
1079            sb.append("\\E\\\\E\\Q");
1080        }
1081        sb.append(s.substring(current, s.length()));
1082        sb.append("\\E");
1083        return sb.toString();
1084    }
1085
1086    /**
1087     * Recompile the Pattern instance from a stream. The original pattern
1088     * string is read in and the object tree is recompiled from it.
1089     */

1090    private void readObject(java.io.ObjectInputStream JavaDoc s)
1091        throws java.io.IOException JavaDoc, ClassNotFoundException JavaDoc {
1092
1093        // Read in all fields
1094
s.defaultReadObject();
1095
1096        // Initialize counts
1097
capturingGroupCount = 1;
1098        localCount = 0;
1099
1100        // if length > 0, the Pattern is lazily compiled
1101
compiled = false;
1102        if (pattern.length() == 0) {
1103            root = new Start(lastAccept);
1104            matchRoot = lastAccept;
1105            compiled = true;
1106        }
1107    }
1108
1109    /**
1110     * This private constructor is used to create all Patterns. The pattern
1111     * string and match flags are all that is needed to completely describe
1112     * a Pattern. An empty pattern string results in an object tree with
1113     * only a Start node and a LastNode node.
1114     */

1115    private Pattern(String JavaDoc p, int f) {
1116        pattern = p;
1117        flags = f;
1118
1119        // Reset group index count
1120
capturingGroupCount = 1;
1121        localCount = 0;
1122
1123        if (pattern.length() > 0) {
1124            compile();
1125        } else {
1126            root = new Start(lastAccept);
1127            matchRoot = lastAccept;
1128        }
1129    }
1130
1131    /**
1132     * The pattern is converted to normalizedD form and then a pure group
1133     * is constructed to match canonical equivalences of the characters.
1134     */

1135    private void normalize() {
1136        boolean inCharClass = false;
1137        int lastCodePoint = -1;
1138
1139        // Convert pattern into normalizedD form
1140
normalizedPattern = Normalizer.decompose(pattern, false, 0);
1141        patternLength = normalizedPattern.length();
1142
1143        // Modify pattern to match canonical equivalences
1144
StringBuilder JavaDoc newPattern = new StringBuilder JavaDoc(patternLength);
1145        for(int i=0; i<patternLength; ) {
1146            int c = normalizedPattern.codePointAt(i);
1147            StringBuilder JavaDoc sequenceBuffer;
1148            if ((Character.getType(c) == Character.NON_SPACING_MARK)
1149                && (lastCodePoint != -1)) {
1150                sequenceBuffer = new StringBuilder JavaDoc();
1151                sequenceBuffer.appendCodePoint(lastCodePoint);
1152                sequenceBuffer.appendCodePoint(c);
1153                while(Character.getType(c) == Character.NON_SPACING_MARK) {
1154                    i += Character.charCount(c);
1155                    if (i >= patternLength)
1156                        break;
1157                    c = normalizedPattern.codePointAt(i);
1158                    sequenceBuffer.appendCodePoint(c);
1159                }
1160                String JavaDoc ea = produceEquivalentAlternation(
1161                                               sequenceBuffer.toString());
1162                newPattern.setLength(newPattern.length()-Character.charCount(lastCodePoint));
1163                newPattern.append("(?:").append(ea).append(")");
1164            } else if (c == '[' && lastCodePoint != '\\') {
1165                i = normalizeCharClass(newPattern, i);
1166            } else {
1167                newPattern.appendCodePoint(c);
1168            }
1169            lastCodePoint = c;
1170        i += Character.charCount(c);
1171        }
1172        normalizedPattern = newPattern.toString();
1173    }
1174
1175    /**
1176     * Complete the character class being parsed and add a set
1177     * of alternations to it that will match the canonical equivalences
1178     * of the characters within the class.
1179     */

1180    private int normalizeCharClass(StringBuilder JavaDoc newPattern, int i) {
1181        StringBuilder JavaDoc charClass = new StringBuilder JavaDoc();
1182        StringBuilder JavaDoc eq = null;
1183        int lastCodePoint = -1;
1184        String JavaDoc result;
1185
1186        i++;
1187        charClass.append("[");
1188        while(true) {
1189            int c = normalizedPattern.codePointAt(i);
1190            StringBuilder JavaDoc sequenceBuffer;
1191
1192            if (c == ']' && lastCodePoint != '\\') {
1193                charClass.append((char)c);
1194                break;
1195            } else if (Character.getType(c) == Character.NON_SPACING_MARK) {
1196                sequenceBuffer = new StringBuilder JavaDoc();
1197                sequenceBuffer.appendCodePoint(lastCodePoint);
1198                while(Character.getType(c) == Character.NON_SPACING_MARK) {
1199                    sequenceBuffer.appendCodePoint(c);
1200                    i += Character.charCount(c);
1201                    if (i >= normalizedPattern.length())
1202                        break;
1203                    c = normalizedPattern.codePointAt(i);
1204                }
1205                String JavaDoc ea = produceEquivalentAlternation(
1206                                                  sequenceBuffer.toString());
1207
1208                charClass.setLength(charClass.length()-Character.charCount(lastCodePoint));
1209                if (eq == null)
1210                    eq = new StringBuilder JavaDoc();
1211                eq.append('|');
1212                eq.append(ea);
1213            } else {
1214                charClass.appendCodePoint(c);
1215                i++;
1216            }
1217            if (i == normalizedPattern.length())
1218                error("Unclosed character class");
1219            lastCodePoint = c;
1220        }
1221
1222        if (eq != null) {
1223            result = new String JavaDoc("(?:"+charClass.toString()+
1224                                eq.toString()+")");
1225        } else {
1226            result = charClass.toString();
1227        }
1228
1229        newPattern.append(result);
1230        return i;
1231    }
1232
1233    /**
1234     * Given a specific sequence composed of a regular character and
1235     * combining marks that follow it, produce the alternation that will
1236     * match all canonical equivalences of that sequence.
1237     */

1238    private String JavaDoc produceEquivalentAlternation(String JavaDoc source) {
1239    int len = countChars(source, 0, 1);
1240        if (source.length() == len)
1241        // source has one character.
1242
return new String JavaDoc(source);
1243
1244        String JavaDoc base = source.substring(0,len);
1245        String JavaDoc combiningMarks = source.substring(len);
1246
1247        String JavaDoc[] perms = producePermutations(combiningMarks);
1248        StringBuilder JavaDoc result = new StringBuilder JavaDoc(source);
1249
1250        // Add combined permutations
1251
for(int x=0; x<perms.length; x++) {
1252            String JavaDoc next = base + perms[x];
1253            if (x>0)
1254                result.append("|"+next);
1255            next = composeOneStep(next);
1256            if (next != null)
1257                result.append("|"+produceEquivalentAlternation(next));
1258        }
1259        return result.toString();
1260    }
1261
1262    /**
1263     * Returns an array of strings that have all the possible
1264     * permutations of the characters in the input string.
1265     * This is used to get a list of all possible orderings
1266     * of a set of combining marks. Note that some of the permutations
1267     * are invalid because of combining class collisions, and these
1268     * possibilities must be removed because they are not canonically
1269     * equivalent.
1270     */

1271    private String JavaDoc[] producePermutations(String JavaDoc input) {
1272        if (input.length() == countChars(input, 0, 1))
1273            return new String JavaDoc[] {input};
1274
1275        if (input.length() == countChars(input, 0, 2)) {
1276        int c0 = Character.codePointAt(input, 0);
1277        int c1 = Character.codePointAt(input, Character.charCount(c0));
1278            if (getClass(c1) == getClass(c0)) {
1279                return new String JavaDoc[] {input};
1280            }
1281            String JavaDoc[] result = new String JavaDoc[2];
1282            result[0] = input;
1283            StringBuilder JavaDoc sb = new StringBuilder JavaDoc(2);
1284        sb.appendCodePoint(c1);
1285        sb.appendCodePoint(c0);
1286            result[1] = sb.toString();
1287            return result;
1288        }
1289
1290        int length = 1;
1291    int nCodePoints = countCodePoints(input);
1292        for(int x=1; x<nCodePoints; x++)
1293            length = length * (x+1);
1294
1295        String JavaDoc[] temp = new String JavaDoc[length];
1296
1297        int combClass[] = new int[nCodePoints];
1298        for(int x=0, i=0; x<nCodePoints; x++) {
1299        int c = Character.codePointAt(input, i);
1300            combClass[x] = getClass(c);
1301        i += Character.charCount(c);
1302    }
1303
1304        // For each char, take it out and add the permutations
1305
// of the remaining chars
1306
int index = 0;
1307    int len;
1308    // offset maintains the index in code units.
1309
loop: for(int x=0, offset=0; x<nCodePoints; x++, offset+=len) {
1310        len = countChars(input, offset, 1);
1311            boolean skip = false;
1312            for(int y=x-1; y>=0; y--) {
1313                if (combClass[y] == combClass[x]) {
1314                    continue loop;
1315                }
1316            }
1317            StringBuilder JavaDoc sb = new StringBuilder JavaDoc(input);
1318            String JavaDoc otherChars = sb.delete(offset, offset+len).toString();
1319            String JavaDoc[] subResult = producePermutations(otherChars);
1320
1321            String JavaDoc prefix = input.substring(offset, offset+len);
1322            for(int y=0; y<subResult.length; y++)
1323                temp[index++] = prefix + subResult[y];
1324        }
1325        String JavaDoc[] result = new String JavaDoc[index];
1326        for (int x=0; x<index; x++)
1327            result[x] = temp[x];
1328        return result;
1329    }
1330
1331    private int getClass(int c) {
1332        return Normalizer.getClass(c);
1333    }
1334
1335    /**
1336     * Attempts to compose input by combining the first character
1337     * with the first combining mark following it. Returns a String
1338     * that is the composition of the leading character with its first
1339     * combining mark followed by the remaining combining marks. Returns
1340     * null if the first two characters cannot be further composed.
1341     */

1342    private String JavaDoc composeOneStep(String JavaDoc input) {
1343    int len = countChars(input, 0, 2);
1344        String JavaDoc firstTwoCharacters = input.substring(0, len);
1345        String JavaDoc result = Normalizer.compose(firstTwoCharacters, false, 0);
1346
1347        if (result.equals(firstTwoCharacters))
1348            return null;
1349        else {
1350            String JavaDoc remainder = input.substring(len);
1351            return result + remainder;
1352        }
1353    }
1354
1355    /**
1356     * Copies regular expression to a char array and invokes the parsing
1357     * of the expression which will create the object tree.
1358     */

1359    private void compile() {
1360        // Handle canonical equivalences
1361
if (has(CANON_EQ) && !has(LITERAL)) {
1362            normalize();
1363        } else {
1364            normalizedPattern = pattern;
1365        }
1366
1367        // Copy pattern to char array for convenience
1368
patternLength = normalizedPattern.length();
1369        temp = new int[patternLength + 2];
1370
1371    boolean hasSupplementary = false;
1372        // Use double null characters to terminate pattern
1373
int c, count = 0;
1374    // Convert all chars into code points
1375
for (int x = 0; x < patternLength; x += Character.charCount(c)) {
1376        c = normalizedPattern.codePointAt(x);
1377        if (isSupplementary(c)) {
1378        hasSupplementary = true;
1379        }
1380        temp[count++] = c;
1381    }
1382
1383    patternLength = count; // patternLength now in code points
1384
temp[patternLength] = 0;
1385        temp[patternLength + 1] = 0;
1386
1387        // Allocate all temporary objects here.
1388
buffer = new int[32];
1389        groupNodes = new GroupHead[10];
1390
1391        if (has(LITERAL)) {
1392            // Literal pattern handling
1393
matchRoot = newSlice(temp, patternLength, hasSupplementary);
1394            matchRoot.next = lastAccept;
1395        } else {
1396            // Start recursive decedent parsing
1397
matchRoot = expr(lastAccept);
1398            // Check extra pattern characters
1399
if (patternLength != cursor) {
1400                if (peek() == ')') {
1401                    error("Unmatched closing ')'");
1402                } else {
1403                    error("Unexpected internal error");
1404                }
1405            }
1406        }
1407
1408        // Peephole optimization
1409
if (matchRoot instanceof Slice) {
1410            root = BnM.optimize(matchRoot);
1411            if (root == matchRoot) {
1412                root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);
1413            }
1414        } else if (matchRoot instanceof Begin || matchRoot instanceof First) {
1415            root = matchRoot;
1416        } else {
1417            root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);
1418        }
1419
1420        // Release temporary storage
1421
temp = null;
1422        buffer = null;
1423        groupNodes = null;
1424        patternLength = 0;
1425        compiled = true;
1426    }
1427
1428    /**
1429     * Used to print out a subtree of the Pattern to help with debugging.
1430     */

1431    private static void printObjectTree(Node node) {
1432        while(node != null) {
1433            if (node instanceof Prolog) {
1434                System.out.println(node);
1435                printObjectTree(((Prolog)node).loop);
1436                System.out.println("**** end contents prolog loop");
1437            } else if (node instanceof Loop) {
1438                System.out.println(node);
1439                printObjectTree(((Loop)node).body);
1440                System.out.println("**** end contents Loop body");
1441            } else if (node instanceof Curly) {
1442                System.out.println(node);
1443                printObjectTree(((Curly)node).atom);
1444                System.out.println("**** end contents Curly body");
1445            } else if (node instanceof GroupCurly) {
1446                System.out.println(node);
1447                printObjectTree(((GroupCurly)node).atom);
1448                System.out.println("**** end contents GroupCurly body");
1449            } else if (node instanceof GroupTail) {
1450                System.out.println(node);
1451                System.out.println("Tail next is "+node.next);
1452                return;
1453            } else {
1454                System.out.println(node);
1455            }
1456            node = node.next;
1457            if (node != null)
1458                System.out.println("->next:");
1459            if (node == Pattern.accept) {
1460                System.out.println("Accept Node");
1461                node = null;
1462            }
1463       }
1464    }
1465
1466    /**
1467     * Used to accumulate information about a subtree of the object graph
1468     * so that optimizations can be applied to the subtree.
1469     */

1470    static final class TreeInfo {
1471        int minLength;
1472        int maxLength;
1473        boolean maxValid;
1474        boolean deterministic;
1475
1476        TreeInfo() {
1477            reset();
1478        }
1479        void reset() {
1480            minLength = 0;
1481            maxLength = 0;
1482            maxValid = true;
1483            deterministic = true;
1484        }
1485    }
1486
1487    /**
1488     * The following private methods are mainly used to improve the
1489     * readability of the code. In order to let the Java compiler easily
1490     * inline them, we should not put many assertions or error checks in them.
1491     */

1492
1493    /**
1494     * Indicates whether a particular flag is set or not.
1495     */

1496    private boolean has(int f) {
1497        return (flags & f) > 0;
1498    }
1499
1500    /**
1501     * Match next character, signal error if failed.
1502     */

1503    private void accept(int ch, String JavaDoc s) {
1504        int testChar = temp[cursor++];
1505        if (has(COMMENTS))
1506            testChar = parsePastWhitespace(testChar);
1507        if (ch != testChar) {
1508           error(s);
1509        }
1510    }
1511
1512    /**
1513     * Mark the end of pattern with a specific character.
1514     */

1515    private void mark(int c) {
1516        temp[patternLength] = c;
1517    }
1518
1519    /**
1520     * Peek the next character, and do not advance the cursor.
1521     */

1522    private int peek() {
1523        int ch = temp[cursor];
1524        if (has(COMMENTS))
1525            ch = peekPastWhitespace(ch);
1526        return ch;
1527    }
1528
1529    /**
1530     * Read the next character, and advance the cursor by one.
1531     */

1532    private int read() {
1533        int ch = temp[cursor++];
1534        if (has(COMMENTS))
1535            ch = parsePastWhitespace(ch);
1536        return ch;
1537    }
1538
1539    /**
1540     * Read the next character, and advance the cursor by one,
1541     * ignoring the COMMENTS setting
1542     */

1543    private int readEscaped() {
1544        int ch = temp[cursor++];
1545        return ch;
1546    }
1547
1548    /**
1549     * Advance the cursor by one, and peek the next character.
1550     */

1551    private int next() {
1552        int ch = temp[++cursor];
1553        if (has(COMMENTS))
1554            ch = peekPastWhitespace(ch);
1555        return ch;
1556    }
1557
1558    /**
1559     * Advance the cursor by one, and peek the next character,
1560     * ignoring the COMMENTS setting
1561     */

1562    private int nextEscaped() {
1563        int ch = temp[++cursor];
1564        return ch;
1565    }
1566
1567    /**
1568     * If in xmode peek past whitespace and comments.
1569     */

1570    private int peekPastWhitespace(int ch) {
1571        while (ASCII.isSpace(ch) || ch == '#') {
1572            while (ASCII.isSpace(ch))
1573                ch = temp[++cursor];
1574            if (ch == '#') {
1575                ch = peekPastLine();
1576            }
1577        }
1578        return ch;
1579    }
1580
1581    /**
1582     * If in xmode parse past whitespace and comments.
1583     */

1584    private int parsePastWhitespace(int ch) {
1585        while (ASCII.isSpace(ch) || ch == '#') {
1586            while (ASCII.isSpace(ch))
1587                ch = temp[cursor++];
1588            if (ch == '#')
1589                ch = parsePastLine();
1590        }
1591        return ch;
1592    }
1593
1594    /**
1595     * xmode parse past comment to end of line.
1596     */

1597    private int parsePastLine() {
1598        int ch = temp[cursor++];
1599        while (ch != 0 && !isLineSeparator(ch))
1600            ch = temp[cursor++];
1601        return ch;
1602    }
1603
1604    /**
1605     * xmode peek past comment to end of line.
1606     */

1607    private int peekPastLine() {
1608        int ch = temp[++cursor];
1609        while (ch != 0 && !isLineSeparator(ch))
1610            ch = temp[++cursor];
1611        return ch;
1612    }
1613
1614    /**
1615     * Determines if character is a line separator in the current mode
1616     */

1617    private boolean isLineSeparator(int ch) {
1618        if (has(UNIX_LINES)) {
1619            return ch == '\n';
1620        } else {
1621            return (ch == '\n' ||
1622                    ch == '\r' ||
1623                    (ch|1) == '\u2029' ||
1624                    ch == '\u0085');
1625        }
1626    }
1627
1628    /**
1629     * Read the character after the next one, and advance the cursor by two.
1630     */

1631    private int skip() {
1632        int i = cursor;
1633        int ch = temp[i+1];
1634        cursor = i + 2;
1635        return ch;
1636    }
1637
1638    /**
1639     * Unread one next character, and retreat cursor by one.
1640     */

1641    private void unread() {
1642        cursor--;
1643    }
1644
1645    /**
1646     * Internal method used for handling all syntax errors. The pattern is
1647     * displayed with a pointer to aid in locating the syntax error.
1648     */

1649    private Node error(String JavaDoc s) {
1650    throw new PatternSyntaxException JavaDoc(s, normalizedPattern,
1651                     cursor - 1);
1652    }
1653
1654    /**
1655     * Determines if there is any supplementary character or unpaired
1656     * surrogate in the specified range.
1657     */

1658    private boolean findSupplementary(int start, int end) {
1659    for (int i = start; i < end; i++) {
1660        if (isSupplementary(temp[i]))
1661        return true;
1662    }
1663    return false;
1664    }
1665
1666    /**
1667     * Determines if the specified code point is a supplementary
1668     * character or unpaired surrogate.
1669     */

1670    private static final boolean isSupplementary(int ch) {
1671    return ch >= Character.MIN_SUPPLEMENTARY_CODE_POINT || isSurrogate(ch);
1672    }
1673
1674    /**
1675     * The following methods handle the main parsing. They are sorted
1676     * according to their precedence order, the lowest one first.
1677     */

1678
1679    /**
1680     * The expression is parsed with branch nodes added for alternations.
1681     * This may be called recursively to parse sub expressions that may
1682     * contain alternations.
1683     */

1684    private Node expr(Node end) {
1685        Node prev = null;
1686        for (;;) {
1687            Node node = sequence(end);
1688            if (prev == null) {
1689                prev = node;
1690            } else {
1691                prev = new Branch(prev, node);
1692            }
1693            if (peek() != '|') {
1694                return prev;
1695            }
1696            next();
1697        }
1698    }
1699
1700    /**
1701     * Parsing of sequences between alternations.
1702     */

1703    private Node sequence(Node end) {
1704        Node head = null;
1705        Node tail = null;
1706        Node node = null;
1707        int i, j, ch;
1708    LOOP:
1709        for (;;) {
1710            ch = peek();
1711            switch (ch) {
1712            case '(':
1713                // Because group handles its own closure,
1714
// we need to treat it differently
1715
node = group0();
1716                // Check for comment or flag group
1717
if (node == null)
1718                    continue;
1719                if (head == null)
1720                    head = node;
1721                else
1722                    tail.next = node;
1723                // Double return: Tail was returned in root
1724
tail = root;
1725                continue;
1726            case '[':
1727                node = clazz(true);
1728                break;
1729            case '\\':
1730                ch = nextEscaped();
1731                if (ch == 'p' || ch == 'P') {
1732                    boolean comp = (ch == 'P');
1733                    boolean oneLetter = true;
1734                    ch = next(); // Consume { if present
1735
if (ch != '{') {
1736                        unread();
1737                    } else {
1738                        oneLetter = false;
1739                    }
1740                    node = family(comp, oneLetter);
1741                } else {
1742                    unread();
1743                    node = atom();
1744                }
1745                break;
1746            case '^':
1747                next();
1748                if (has(MULTILINE)) {
1749                    if (has(UNIX_LINES))
1750                        node = new UnixCaret();
1751                    else
1752                        node = new Caret();
1753                } else {
1754                    node = new Begin();
1755                }
1756                break;
1757            case '$':
1758                next();
1759                if (has(UNIX_LINES))
1760                    node = new UnixDollar(has(MULTILINE));
1761                else
1762                    node = new Dollar(has(MULTILINE));
1763                break;
1764            case '.':
1765                next();
1766                if (has(DOTALL)) {
1767                    node = new All();
1768                } else {
1769                    if (has(UNIX_LINES))
1770                        node = new UnixDot();
1771                    else {
1772                        node = new Dot();
1773                    }
1774                }
1775                break;
1776            case '|':
1777            case ')':
1778                break LOOP;
1779            case ']': // Now interpreting dangling ] and } as literals
1780
case '}':
1781                node = atom();
1782                break;
1783            case '?':
1784            case '*':
1785            case '+':
1786                next();
1787                return error("Dangling meta character '" + ((char)ch) + "'");
1788            case 0:
1789                if (cursor >= patternLength) {
1790                    break LOOP;
1791                }
1792                // Fall through
1793
default:
1794                node = atom();
1795                break;
1796            }
1797
1798            node = closure(node);
1799
1800            if (head == null) {
1801                head = tail = node;
1802            } else {
1803                tail.next = node;
1804                tail = node;
1805            }
1806        }
1807        if (head == null) {
1808            return end;
1809        }
1810        tail.next = end;
1811        return head;
1812    }
1813
1814    /**
1815     * Parse and add a new Single or Slice.
1816     */

1817    private Node atom() {
1818        int first = 0;
1819        int prev = -1;
1820    boolean hasSupplementary = false;
1821        int ch = peek();
1822        for (;;) {
1823            switch (ch) {
1824            case '*':
1825            case '+':
1826            case '?':
1827            case '{':
1828                if (first > 1) {
1829                    cursor = prev; // Unwind one character
1830
first--;
1831                }
1832                break;
1833            case '$':
1834            case '.':
1835            case '^':
1836            case '(':
1837            case '[':
1838            case '|':
1839            case ')':
1840                break;
1841            case '\\':
1842                ch = nextEscaped();
1843                if (ch == 'p' || ch == 'P') { // Property
1844
if (first > 0) { // Slice is waiting; handle it first
1845
unread();
1846                        break;
1847                    } else { // No slice; just return the family node
1848
if (ch == 'p' || ch == 'P') {
1849                            boolean comp = (ch == 'P');
1850                            boolean oneLetter = true;
1851                            ch = next(); // Consume { if present
1852
if (ch != '{')
1853                                unread();
1854                            else
1855                                oneLetter = false;
1856                            return family(comp, oneLetter);
1857                        }
1858                    }
1859                    break;
1860                }
1861                unread();
1862                prev = cursor;
1863                ch = escape(false, first == 0);
1864                if (ch >= 0) {
1865                    append(ch, first);
1866                    first++;
1867            if (isSupplementary(ch)) {
1868            hasSupplementary = true;
1869            }
1870                    ch = peek();
1871                    continue;
1872                } else if (first == 0) {
1873                    return root;
1874                }
1875                // Unwind meta escape sequence
1876
cursor = prev;
1877                break;
1878            case 0:
1879                if (cursor >= patternLength) {
1880                    break;
1881                }
1882                // Fall through
1883
default:
1884                prev = cursor;
1885                append(ch, first);
1886                first++;
1887        if (isSupplementary(ch)) {
1888            hasSupplementary = true;
1889        }
1890                ch = next();
1891                continue;
1892            }
1893            break;
1894        }
1895        if (first == 1) {
1896            return newSingle(buffer[0]);
1897        } else {
1898            return newSlice(buffer, first, hasSupplementary);
1899        }
1900    }
1901
1902    private void append(int ch, int len) {
1903        if (len >= buffer.length) {
1904            int[] tmp = new int[len+len];
1905            System.arraycopy(buffer, 0, tmp, 0, len);
1906            buffer = tmp;
1907        }
1908        buffer[len] = ch;
1909    }
1910
1911    /**
1912     * Parses a backref greedily, taking as many numbers as it
1913     * can. The first digit is always treated as a backref, but
1914     * multi digit numbers are only treated as a backref if at
1915     * least that many backrefs exist at this point in the regex.
1916     */

1917    private Node ref(int refNum) {
1918        boolean done = false;
1919        while(!done) {
1920            int ch = peek();
1921            switch(ch) {
1922                case '0':
1923                case '1':
1924                case '2':
1925                case '3':
1926                case '4':
1927                case '5':
1928                case '6':
1929                case '7':
1930                case '8':
1931                case '9':
1932                    int newRefNum = (refNum * 10) + (ch - '0');
1933                    // Add another number if it doesn't make a group
1934
// that doesn't exist
1935
if (capturingGroupCount - 1 < newRefNum) {
1936                        done = true;
1937                        break;
1938                    }
1939                    refNum = newRefNum;
1940                    read();
1941                    break;
1942                default:
1943                    done = true;
1944                    break;
1945            }
1946        }
1947        if (has(CASE_INSENSITIVE) || has(UNICODE_CASE))
1948            return new CIBackRef(refNum);
1949        else
1950            return new BackRef(refNum);
1951    }
1952
1953    /**
1954     * Parses an escape sequence to determine the actual value that needs
1955     * to be matched.
1956     * If -1 is returned and create was true a new object was added to the tree
1957     * to handle the escape sequence.
1958     * If the returned value is greater than zero, it is the value that
1959     * matches the escape sequence.
1960     */

1961    private int escape(boolean inclass, boolean create) {
1962        int ch = skip();
1963        switch (ch) {
1964            case '0':
1965                return o();
1966            case '1':
1967            case '2':
1968            case '3':
1969            case '4':
1970            case '5':
1971            case '6':
1972            case '7':
1973            case '8':
1974            case '9':
1975                if (inclass) break;
1976                if (capturingGroupCount < (ch - '0'))
1977                    error("No such group yet exists at this point in the pattern");
1978                if (create) {
1979                    root = ref((ch - '0'));
1980                }
1981                return -1;
1982            case 'A':
1983                if (inclass) break;
1984                if (create) root = new Begin();
1985                return -1;
1986            case 'B':
1987                if (inclass) break;
1988                if (create) root = new Bound(Bound.NONE);
1989                return -1;
1990            case 'C':
1991                break;
1992            case 'D':
1993                if (create) root = new NotCtype(ASCII.DIGIT);
1994                return -1;
1995            case 'E':
1996            case 'F':
1997                break;
1998            case 'G':
1999                if (inclass) break;
2000                if (create) root = new LastMatch();
2001                return -1;
2002            case 'H':
2003            case 'I':
2004            case 'J':
2005            case 'K':
2006            case 'L':
2007            case 'M':
2008            case 'N':
2009            case 'O':
2010            case 'P':
2011                break;
2012            case 'Q':
2013                if (create) {
2014                    // Disable metacharacters. We will return a slice
2015
// up to the next \E
2016
int i = cursor;
2017                    int c;
2018                    while ((c = readEscaped()) != 0) {
2019                        if (c == '\\') {
2020                            c = readEscaped();
2021                            if (c == 'E' || c == 0)
2022                                break;
2023                            else
2024                               unread();
2025                        }
2026                    }
2027                    int j = cursor-1;
2028                    if (c == 'E')
2029                        j--;
2030                    else
2031                        unread();
2032            boolean hasSupplementary = false;
2033                    for (int x = i; x<j; x++) {
2034            c = temp[x];
2035                        append(c, x-i);
2036            if (isSupplementary(c)) {
2037                hasSupplementary = true;
2038            }
2039            }
2040                    root = newSlice(buffer, j-i, hasSupplementary);
2041                }
2042                return -1;
2043            case 'R':
2044                break;
2045            case 'S':
2046                if (create) root = new NotCtype(ASCII.SPACE);
2047                return -1;
2048            case 'T':
2049            case 'U':
2050            case 'V':
2051                break;
2052            case 'W':
2053                if (create) root = new NotCtype(ASCII.WORD);
2054                return -1;
2055            case 'X':
2056            case 'Y':
2057                break;
2058            case 'Z':
2059                if (inclass) break;
2060                if (create) {
2061                    if (has(UNIX_LINES))
2062                        root = new UnixDollar(false);
2063                    else
2064                        root = new Dollar(false);
2065                }
2066                return -1;
2067            case 'a':
2068                return '\007';
2069            case 'b':
2070                if (inclass) break;
2071                if (create) root = new Bound(Bound.BOTH);
2072                return -1;
2073            case 'c':
2074                return c();
2075            case 'd':
2076                if (create) root = new Ctype(ASCII.DIGIT);
2077                return -1;
2078            case 'e':
2079                return '\033';
2080            case 'f':
2081                return '\f';
2082            case 'g':
2083            case 'h':
2084            case 'i':
2085            case 'j':
2086            case 'k':
2087            case 'l':
2088            case 'm':
2089                break;
2090            case 'n':
2091                return '\n';
2092            case 'o':
2093            case 'p':
2094            case 'q':
2095                break;
2096            case 'r':
2097                return '\r';
2098            case 's':
2099                if (create) root = new Ctype(ASCII.SPACE);
2100                return -1;
2101            case 't':
2102                return '\t';
2103            case 'u':
2104                return u();
2105            case 'v':
2106                return '\013';
2107            case 'w':
2108                if (create) root = new Ctype(ASCII.WORD);
2109                return -1;
2110            case 'x':
2111                return x();
2112            case 'y':
2113                break;
2114            case 'z':
2115                if (inclass) break;
2116                if (create) root = new End();
2117                return -1;
2118            default:
2119                return ch;
2120        }
2121        error("Illegal/unsupported escape squence");
2122        return -2;
2123    }
2124
2125    /**
2126     * Parse a character class, and return the node that matches it.
2127     *
2128     * Consumes a ] on the way out if consume is true. Usually consume
2129     * is true except for the case of [abc&&def] where def is a separate
2130     * right hand node with "understood" brackets.
2131     */

2132    private Node clazz(boolean consume) {
2133        Node prev = null;
2134        Node node = null;
2135        BitClass bits = new BitClass(false);
2136        boolean include = true;
2137        boolean firstInClass = true;
2138        int ch = next();
2139        for (;;) {
2140            switch (ch) {
2141                case '^':
2142                    // Negates if first char in a class, otherwise literal
2143
if (firstInClass) {
2144                        if (temp[cursor-1] != '[')
2145                            break;
2146                        ch = next();
2147                        include = !include;
2148                        continue;
2149                    } else {
2150                        // ^ not first in class, treat as literal
2151
break;
2152                    }
2153                case '[':
2154                    firstInClass = false;
2155                    node = clazz(true);
2156                    if (prev == null)
2157                        prev = node;
2158                    else
2159                        prev = new Add(prev, node);
2160                    ch = peek();
2161                    continue;
2162                case '&':
2163                    firstInClass = false;
2164                    ch = next();
2165                    if (ch == '&') {
2166                        ch = next();
2167                        Node rightNode = null;
2168                        while (ch != ']' && ch != '&') {
2169                            if (ch == '[') {
2170                                if (rightNode == null)
2171                                    rightNode = clazz(true);
2172                                else
2173                                    rightNode = new Add(rightNode, clazz(true));
2174                            } else { // abc&&def
2175
unread();
2176                                rightNode = clazz(false);
2177                            }
2178                            ch = peek();
2179                        }
2180                        if (rightNode != null)
2181                            node = rightNode;
2182                        if (prev == null) {
2183                            if (rightNode == null)
2184                                return error("Bad class syntax");
2185                            else
2186                                prev = rightNode;
2187                        } else {
2188                            prev = new Both(prev, node);
2189                        }
2190                    } else {
2191                        // treat as a literal &
2192
unread();
2193                        break;
2194                    }
2195                    continue;
2196                case 0:
2197                    firstInClass = false;
2198                    if (cursor >= patternLength)
2199                        return error("Unclosed character class");
2200                    break;
2201                case ']':
2202                    firstInClass = false;
2203                    if (prev != null) {
2204                        if (consume)
2205                            next();
2206                        return prev;
2207                    }
2208                    break;
2209                default:
2210                    firstInClass = false;
2211                    break;
2212            }
2213            node = range(bits);
2214            if (include) {
2215                if (prev == null) {
2216                    prev = node;
2217                } else {
2218                    if (prev != node)
2219                        prev = new Add(prev, node);
2220                }
2221            } else {
2222                if (prev == null) {
2223                    prev = node.dup(true); // Complement
2224
} else {
2225                    if (prev != node)
2226                        prev = new Sub(prev, node);
2227                }
2228            }
2229            ch = peek();
2230        }
2231    }
2232
2233    /**
2234     * Parse a single character or a character range in a character class
2235     * and return its representative node.
2236     */

2237    private Node range(BitClass bits) {
2238        int ch = peek();
2239        if (ch == '\\') {
2240            ch = nextEscaped();
2241            if (ch == 'p' || ch == 'P') { // A property
2242
boolean comp = (ch == 'P');
2243                boolean oneLetter = true;
2244                // Consume { if present
2245
ch = next();
2246                if (ch != '{')
2247                    unread();
2248                else
2249                    oneLetter = false;
2250                return family(comp, oneLetter);
2251            } else { // ordinary escape
2252
unread();
2253                ch = escape(true, true);
2254                if (ch == -1)
2255                    return root;
2256            }
2257        } else {
2258            ch = single();
2259        }
2260        if (ch >= 0) {
2261            if (peek() == '-') {
2262                int endRange = temp[cursor+1];
2263                if (endRange == '[') {
2264                    if (ch < 256)
2265                        return bits.add(ch, flags());
2266                    return newSingle(ch);
2267                }
2268                if (endRange != ']') {
2269                    next();
2270                    int m = single();
2271                    if (m < ch)
2272                        return error("Illegal character range");
2273                    if (has(CASE_INSENSITIVE) || has(UNICODE_CASE))
2274                        return new CIRange(ch, m);
2275                    else
2276                        return new Range(ch, m);
2277                }
2278            }
2279            if (ch < 256)
2280                return bits.add(ch, flags());
2281            return newSingle(ch);
2282        }
2283        return error("Unexpected character '"+((char)ch)+"'");
2284    }
2285
2286    private int single() {
2287        int ch = peek();
2288        switch (ch) {
2289        case '\\':
2290            return escape(true, false);
2291        default:
2292            next();
2293            return ch;
2294        }
2295    }
2296
2297    /**
2298     * Parses a Unicode character family and returns its representative node.
2299     * Reference to an unknown character family results in a list of supported
2300     * families in the error.
2301     */

2302    private Node family(boolean not, boolean singleLetter) {
2303        next();
2304        String JavaDoc name;
2305
2306        if (singleLetter) {
2307        int c = temp[cursor];
2308        if (!Character.isSupplementaryCodePoint(c)) {
2309        name = String.valueOf((char)c);
2310        } else {
2311        name = new String JavaDoc(temp, cursor, 1);
2312        }
2313        name = name.intern();
2314            read();
2315        } else {
2316            int i = cursor;
2317            mark('}');
2318            while(read() != '}') {
2319            }
2320            mark('\000');
2321            int j = cursor;
2322            if (j > patternLength)
2323                return error("Unclosed character family");
2324            if (i + 1 >= j)
2325                return error("Empty character family");
2326            name = new String JavaDoc(temp, i, j-i-1).intern();
2327        }
2328
2329        if (name.startsWith("In")) {
2330            name = name.substring(2, name.length()).intern();
2331            return retrieveFamilyNode(name, not);
2332        }
2333        if (name.startsWith("Is"))
2334            name = name.substring(2, name.length()).intern();
2335        return retrieveCategoryNode(name).dup(not);
2336    }
2337
2338    private Node retrieveFamilyNode(String JavaDoc name, boolean not) {
2339        if (name == null) {
2340            return familyError("", "Null character family.");
2341        }
2342        Node n = null;
2343        try {
2344            Character.UnicodeBlock JavaDoc block = Character.UnicodeBlock.forName(name);
2345            n = new UBlock(block, not);
2346        } catch (IllegalArgumentException JavaDoc iae) {
2347            return familyError(name, "Unknown character family {");
2348        }
2349        return n;
2350    }
2351
2352    private Node retrieveCategoryNode(String JavaDoc name) {
2353        Node n = (Node)categoryNames.cMap.get(name);
2354        if (n != null)
2355            return n;
2356
2357        return familyError(name, "Unknown character category {");
2358    }
2359
2360    private Node familyError(String JavaDoc name, String JavaDoc type) {
2361        StringBuilder JavaDoc sb = new StringBuilder JavaDoc();
2362        sb.append(type);
2363        sb.append(name);
2364        sb.append("}");
2365        name = sb.toString();
2366        return error(name);
2367    }
2368
2369    /**
2370     * Parses a group and returns the head node of a set of nodes that process
2371     * the group. Sometimes a double return system is used where the tail is
2372     * returned in root.
2373     */

2374    private Node group0() {
2375        boolean capturingGroup = false;
2376        Node head = null;
2377        Node tail = null;
2378        int save = flags;
2379        root = null;
2380        int ch = next();
2381        if (ch == '?') {
2382            ch = skip();
2383            switch (ch) {
2384            case ':': // (?:xxx) pure group
2385
head = createGroup(true);
2386                tail = root;
2387                head.next = expr(tail);
2388                break;
2389            case '=': // (?=xxx) and (?!xxx) lookahead
2390
case '!':
2391                head = createGroup(true);
2392                tail = root;
2393                head.next = expr(tail);
2394                if (ch == '=') {
2395                    head = tail = new Pos(head);
2396                } else {
2397                    head = tail = new Neg(head);
2398                }
2399                break;
2400            case '>': // (?>xxx) independent group
2401
head = createGroup(true);
2402                tail = root;
2403                head.next = expr(tail);
2404                head = tail = new Ques(head, INDEPENDENT);
2405                break;
2406            case '<': // (?<xxx) look behind
2407
ch = read();
2408        int start = cursor;
2409                head = createGroup(true);
2410                tail = root;
2411                head.next = expr(tail);
2412                TreeInfo info = new TreeInfo();
2413                head.study(info);
2414                if (info.maxValid == false) {
2415                    return error("Look-behind group does not have "
2416                                 + "an obvious maximum length");
2417                }
2418        boolean hasSupplementary = findSupplementary(start, patternLength);
2419                if (ch == '=') {
2420                    head = tail = (hasSupplementary ?
2421                   new BehindS(head, info.maxLength,
2422                           info.minLength) :
2423                   new Behind(head, info.maxLength,
2424                          info.minLength));
2425                } else if (ch == '!') {
2426                    head = tail = (hasSupplementary ?
2427                   new NotBehindS(head, info.maxLength,
2428                          info.minLength) :
2429                   new NotBehind(head, info.maxLength,
2430                         info.minLength));
2431                } else {
2432                    error("Unknown look-behind group");
2433                }
2434                break;
2435            case '$':
2436            case '@':
2437        return error("Unknown group type");
2438            default: // (?xxx:) inlined match flags
2439
unread();
2440                addFlag();
2441                ch = read();
2442                if (ch == ')') {
2443                    return null; // Inline modifier only
2444
}
2445                if (ch != ':') {
2446                    return error("Unknown inline modifier");
2447                }
2448                head = createGroup(true);
2449                tail = root;
2450                head.next = expr(tail);
2451                break;
2452            }
2453        } else { // (xxx) a regular group
2454
capturingGroup = true;
2455            head = createGroup(false);
2456            tail = root;
2457            head.next = expr(tail);
2458        }
2459
2460        accept(')', "Unclosed group");
2461        flags = save;
2462
2463        // Check for quantifiers
2464
Node node = closure(head);
2465        if (node == head) { // No closure
2466
root = tail;
2467            return node; // Dual return
2468
}
2469        if (head == tail) { // Zero length assertion
2470
root = node;
2471            return node; // Dual return
2472
}
2473
2474        if (node instanceof Ques) {
2475            Ques ques = (Ques) node;
2476            if (ques.type == POSSESSIVE) {
2477                root = node;
2478                return node;
2479            }
2480            // Dummy node to connect branch
2481
tail.next = new Dummy();
2482            tail = tail.next;
2483            if (ques.type == GREEDY) {
2484                head = new Branch(head, tail);
2485            } else { // Reluctant quantifier
2486
head = new Branch(tail, head);
2487            }
2488            root = tail;
2489            return head;
2490        } else if (node instanceof Curly) {
2491            Curly curly = (Curly) node;
2492            if (curly.type == POSSESSIVE) {
2493                root = node;
2494                return node;
2495            }
2496            // Discover if the group is deterministic
2497
TreeInfo info = new TreeInfo();
2498            if (head.study(info)) { // Deterministic
2499
GroupTail temp = (GroupTail) tail;
2500                head = root = new GroupCurly(head.next, curly.cmin,
2501                                   curly.cmax, curly.type,
2502                                   ((GroupTail)tail).localIndex,
2503                                   ((GroupTail)tail).groupIndex,
2504                                             capturingGroup);
2505                return head;
2506            } else { // Non-deterministic
2507
int temp = ((GroupHead) head).localIndex;
2508                Loop loop;
2509                if (curly.type == GREEDY)
2510                    loop = new Loop(this.localCount, temp);
2511                else // Reluctant Curly
2512
loop = new LazyLoop(this.localCount, temp);
2513                Prolog prolog = new Prolog(loop);
2514                this.localCount += 1;
2515                loop.cmin = curly.cmin;
2516                loop.cmax = curly.cmax;
2517                loop.body = head;
2518                tail.next = loop;
2519                root = loop;
2520                return prolog; // Dual return
2521
}
2522        } else if (node instanceof First) {
2523            root = node;
2524            return node;
2525        }
2526        return error("Internal logic error");
2527    }
2528
2529    /**
2530     * Create group head and tail nodes using double return. If the group is
2531     * created with anonymous true then it is a pure group and should not
2532     * affect group counting.
2533     */

2534    private Node createGroup(boolean anonymous) {
2535        int localIndex = localCount++;
2536        int groupIndex = 0;
2537        if (!anonymous)
2538            groupIndex = capturingGroupCount++;
2539        GroupHead head = new GroupHead(localIndex);
2540        root = new GroupTail(localIndex, groupIndex);
2541        if (!anonymous && groupIndex < 10)
2542            groupNodes[groupIndex] = head;
2543        return head;
2544    }
2545
2546    /**
2547     * Parses inlined match flags and set them appropriately.
2548     */

2549    private void addFlag() {
2550        int ch = peek();
2551        for (;;) {
2552            switch (ch) {
2553            case 'i':
2554                flags |= CASE_INSENSITIVE;
2555                break;
2556            case 'm':
2557                flags |= MULTILINE;
2558                break;
2559            case 's':
2560                flags |= DOTALL;
2561                break;
2562            case 'd':
2563                flags |= UNIX_LINES;
2564                break;
2565            case 'u':
2566                flags |= UNICODE_CASE;
2567                break;
2568            case 'c':
2569                flags |= CANON_EQ;
2570                break;
2571            case 'x':
2572                flags |= COMMENTS;
2573                break;
2574            case '-': // subFlag then fall through
2575
ch = next();
2576                subFlag();
2577            default:
2578                return;
2579            }
2580            ch = next();
2581        }
2582    }
2583
2584    /**
2585     * Parses the second part of inlined match flags and turns off
2586     * flags appropriately.
2587     */

2588    private void subFlag() {
2589        int ch = peek();
2590        for (;;) {
2591            switch (ch) {
2592            case 'i':
2593                flags &= ~CASE_INSENSITIVE;
2594                break;
2595            case 'm':
2596                flags &= ~MULTILINE;
2597                break;
2598            case 's':
2599                flags &= ~DOTALL;
2600                break;
2601            case 'd':
2602                flags &= ~UNIX_LINES;
2603                break;
2604            case 'u':
2605                flags &= ~UNICODE_CASE;
2606                break;
2607            case 'c':
2608                flags &= ~CANON_EQ;
2609                break;
2610            case 'x':
2611                flags &= ~COMMENTS;
2612                break;
2613            default:
2614                return;
2615            }
2616            ch = next();
2617        }
2618    }
2619
2620    static final int MAX_REPS = 0x7FFFFFFF;
2621
2622    static final int GREEDY = 0;
2623
2624    static final int LAZY = 1;
2625
2626    static final int POSSESSIVE = 2;
2627
2628    static final int INDEPENDENT = 3;
2629
2630    /**
2631     * Processes repetition. If the next character peeked is a quantifier
2632     * then new nodes must be appended to handle the repetition.
2633     * Prev could be a single or a group, so it could be a chain of nodes.
2634     */

2635    private Node closure(Node prev) {
2636        Node atom;
2637        int ch = peek();
2638        switch (ch) {
2639        case '?':
2640            ch = next();
2641            if (ch == '?') {
2642                next();
2643                return new Ques(prev, LAZY);
2644            } else if (ch == '+') {
2645                next();
2646                return new Ques(prev, POSSESSIVE);
2647            }
2648            return new Ques(prev, GREEDY);
2649        case '*':
2650            ch = next();
2651            if (ch == '?') {
2652                next();
2653                return new Curly(prev, 0, MAX_REPS, LAZY);
2654            } else if (ch == '+') {
2655                next();
2656                return new Curly(prev, 0, MAX_REPS, POSSESSIVE);
2657            }
2658            return new Curly(prev, 0, MAX_REPS, GREEDY);
2659        case '+':
2660            ch = next();
2661            if (ch == '?') {
2662                next();
2663                return new Curly(prev, 1, MAX_REPS, LAZY);
2664            } else if (ch == '+') {
2665                next();
2666                return new Curly(prev, 1, MAX_REPS, POSSESSIVE);
2667            }
2668            return new Curly(prev, 1, MAX_REPS, GREEDY);
2669        case '{':
2670            ch = temp[cursor+1];
2671            if (ASCII.isDigit(ch)) {
2672                skip();
2673                int cmin = 0;
2674                do {
2675                    cmin = cmin * 10 + (ch - '0');
2676                } while (ASCII.isDigit(ch = read()));
2677                int cmax = cmin;
2678                if (ch == ',') {
2679                    ch = read();
2680                    cmax = MAX_REPS;
2681                    if (ch != '}') {
2682                        cmax = 0;
2683                        while (ASCII.isDigit(ch)) {
2684                            cmax = cmax * 10 + (ch - '0');
2685                            ch = read();
2686                        }
2687                    }
2688                }
2689                if (ch != '}')
2690                    return error("Unclosed counted closure");
2691                if (((cmin) | (cmax) | (cmax - cmin)) < 0)
2692                    return error("Illegal repetition range");
2693                Curly curly;
2694                ch = peek();
2695                if (ch == '?') {
2696                    next();
2697                    curly = new Curly(prev, cmin, cmax, LAZY);
2698                } else if (ch == '+') {
2699                    next();
2700                    curly = new Curly(prev, cmin, cmax, POSSESSIVE);
2701                } else {
2702                    curly = new Curly(prev, cmin, cmax, GREEDY);
2703                }
2704                return curly;
2705            } else {
2706                error("Illegal repetition");
2707            }
2708            return prev;
2709        default:
2710            return prev;
2711        }
2712    }
2713
2714    /**
2715     * Utility method for parsing control escape sequences.
2716     */

2717    private int c() {
2718        if (cursor < patternLength) {
2719            return read() ^ 64;
2720        }
2721        error("Illegal control escape sequence");
2722        return -1;
2723    }
2724
2725    /**
2726     * Utility method for parsing octal escape sequences.
2727     */

2728    private int o() {
2729        int n = read();
2730        if (((n-'0')|('7'-n)) >= 0) {
2731            int m = read();
2732            if (((m-'0')|('7'-m)) >= 0) {
2733                int o = read();
2734                if ((((o-'0')|('7'-o)) >= 0) && (((n-'0')|('3'-n)) >= 0)) {
2735                    return (n - '0') * 64 + (m - '0') * 8 + (o - '0');
2736                }
2737                unread();
2738                return (n - '0') * 8 + (m - '0');
2739            }
2740            unread();
2741            return (n - '0');
2742        }
2743        error("Illegal octal escape sequence");
2744        return -1;
2745    }
2746
2747    /**
2748     * Utility method for parsing hexadecimal escape sequences.
2749     */

2750    private int x() {
2751        int n = read();
2752        if (ASCII.isHexDigit(n)) {
2753            int m = read();
2754            if (ASCII.isHexDigit(m)) {
2755                return ASCII.toDigit(n) * 16 + ASCII.toDigit(m);
2756            }
2757        }
2758        error("Illegal hexadecimal escape sequence");
2759        return -1;
2760    }
2761
2762    /**
2763     * Utility method for parsing unicode escape sequences.
2764     */

2765    private int u() {
2766        int n = 0;
2767        for (int i = 0; i < 4; i++) {
2768            int ch = read();
2769            if (!ASCII.isHexDigit(ch)) {
2770                error("Illegal Unicode escape sequence");
2771            }
2772            n = n * 16 + ASCII.toDigit(ch);
2773        }
2774        return n;
2775    }
2776
2777    //
2778
// Utility methods for code point support
2779
//
2780

2781    /**
2782     * Tests a surrogate value.
2783     */

2784    private static final boolean isSurrogate(int c) {
2785    return c >= Character.MIN_HIGH_SURROGATE && c <= Character.MAX_LOW_SURROGATE;
2786    }
2787
2788    private static final int countChars(CharSequence JavaDoc seq, int index,
2789                    int lengthInCodePoints) {
2790    // optimization
2791
if (lengthInCodePoints == 1 && !Character.isHighSurrogate(seq.charAt(index))) {
2792        assert (index >= 0 && index < seq.length());
2793        return 1;
2794    }
2795    int length = seq.length();
2796    int x = index;
2797    if (lengthInCodePoints >= 0) {
2798        assert (index >= 0 && index < length);
2799        for (int i = 0; x < length && i < lengthInCodePoints; i++) {
2800        if (Character.isHighSurrogate(seq.charAt(x++))) {
2801            if (x < length && Character.isLowSurrogate(seq.charAt(x))) {
2802            x++;
2803            }
2804        }
2805        }
2806        return x - index;
2807    }
2808
2809    assert (index >= 0 && index <= length);
2810    if (index == 0) {
2811        return 0;
2812    }
2813    int len = -lengthInCodePoints;
2814    for (int i = 0; x > 0 && i < len; i++) {
2815        if (Character.isLowSurrogate(seq.charAt(--x))) {
2816        if (x > 0 && Character.isHighSurrogate(seq.charAt(x-1))) {
2817            x--;
2818        }
2819        }
2820    }
2821    return index - x;
2822    }
2823
2824    private static final int countCodePoints(CharSequence JavaDoc seq) {
2825    int length = seq.length();
2826    int n = 0;
2827    for (int i = 0; i < length; ) {
2828        n++;
2829        if (Character.isHighSurrogate(seq.charAt(i++))) {
2830        if (i < length && Character.isLowSurrogate(seq.charAt(i))) {
2831            i++;
2832        }
2833        }
2834    }
2835    return n;
2836    }
2837
2838    /**
2839     * Creates a bit vector for matching Latin-1 values. A normal BitClass
2840     * never matches values above Latin-1, and a complemented BitClass always
2841     * matches values above Latin-1.
2842     */

2843    static final class BitClass extends Node {
2844        boolean[] bits = new boolean[256];
2845        boolean complementMe = false;
2846        BitClass(boolean not) {
2847            complementMe = not;
2848        }
2849        BitClass(boolean[] newBits, boolean not) {
2850            complementMe = not;
2851            bits = newBits;
2852        }
2853        Node add(int c, int f) {
2854            if ((f & CASE_INSENSITIVE) == 0) {
2855                bits[c] = true;
2856            } else if (ASCII.isAscii(c)) {
2857                bits[ASCII.toUpper(c)] = true;
2858                bits[ASCII.toLower(c)] = true;
2859            } else {
2860                bits[Character.toLowerCase((char)c)] = true;
2861                bits[Character.toUpperCase((char)c)] = true;
2862            }
2863            return this;
2864        }
2865        Node dup(boolean not) {
2866            return new BitClass(bits, not);
2867        }
2868        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
2869            if (i >= matcher.to) {
2870                matcher.hitEnd = true;
2871                return false;
2872            }
2873        int c = Character.codePointAt(seq, i);
2874        boolean charMatches =
2875        (c > 255) ? complementMe : (bits[c] ^ complementMe);
2876            return charMatches && next.match(matcher, i+Character.charCount(c), seq);
2877        }
2878        boolean study(TreeInfo info) {
2879            info.minLength++;
2880            info.maxLength++;
2881            return next.study(info);
2882        }
2883    }
2884
2885    /**
2886     * Utility method for creating a single character matcher.
2887     */

2888    private Node newSingle(int ch) {
2889        int f = flags;
2890        if ((f & (CASE_INSENSITIVE|UNICODE_CASE)) == 0) {
2891            return new Single(ch);
2892        }
2893        if ((f & UNICODE_CASE) == 0) {
2894            return new SingleA(ch);
2895        }
2896        return new SingleU(ch);
2897    }
2898
2899    /**
2900     * Utility method for creating a string slice matcher.
2901     */

2902    private Node newSlice(int[] buf, int count, boolean hasSupplementary) {
2903        int[] tmp = new int[count];
2904        int i = flags;
2905        if ((i & (CASE_INSENSITIVE|UNICODE_CASE)) == 0) {
2906            for (i = 0; i < count; i++) {
2907                tmp[i] = buf[i];
2908            }
2909            return hasSupplementary ? new SliceS(tmp) : new Slice(tmp);
2910        } else if ((i & UNICODE_CASE) == 0) {
2911            for (i = 0; i < count; i++) {
2912                tmp[i] = (char)ASCII.toLower(buf[i]);
2913            }
2914            return new SliceA(tmp);
2915        } else {
2916            for (i = 0; i < count; i++) {
2917                int c = buf[i];
2918                c = Character.toUpperCase(c);
2919                c = Character.toLowerCase(c);
2920                tmp[i] = c;
2921            }
2922            return new SliceU(tmp);
2923        }
2924    }
2925
2926    /**
2927     * The following classes are the building components of the object
2928     * tree that represents a compiled regular expression. The object tree
2929     * is made of individual elements that handle constructs in the Pattern.
2930     * Each type of object knows how to match its equivalent construct with
2931     * the match() method.
2932     */

2933
2934    /**
2935     * Base class for all node classes. Subclasses should override the match()
2936     * method as appropriate. This class is an accepting node, so its match()
2937     * always returns true.
2938     */

2939    static class Node extends Object JavaDoc {
2940        Node next;
2941        Node() {
2942            next = Pattern.accept;
2943        }
2944        Node dup(boolean not) {
2945            if (not) {
2946                return new Not(this);
2947            } else {
2948                throw new RuntimeException JavaDoc("internal error in Node dup()");
2949            }
2950        }
2951        /**
2952         * This method implements the classic accept node.
2953         */

2954        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
2955            matcher.last = i;
2956            matcher.groups[0] = matcher.first;
2957            matcher.groups[1] = matcher.last;
2958            return true;
2959        }
2960        /**
2961         * This method is good for all zero length assertions.
2962         */

2963        boolean study(TreeInfo info) {
2964            if (next != null) {
2965                return next.study(info);
2966            } else {
2967                return info.deterministic;
2968            }
2969        }
2970    }
2971
2972    static class LastNode extends Node {
2973        /**
2974         * This method implements the classic accept node with
2975         * the addition of a check to see if the match occurred
2976         * using all of the input.
2977         */

2978        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
2979            if (matcher.acceptMode == Matcher.ENDANCHOR && i != matcher.to)
2980                return false;
2981            matcher.last = i;
2982            matcher.groups[0] = matcher.first;
2983            matcher.groups[1] = matcher.last;
2984            return true;
2985        }
2986    }
2987
2988    /**
2989     * Dummy node to assist in connecting branches.
2990     */

2991    static class Dummy extends Node {
2992        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
2993            return next.match(matcher, i, seq);
2994        }
2995    }
2996
2997    /**
2998     * Used for REs that can start anywhere within the input string.
2999     * This basically tries to match repeatedly at each spot in the
3000     * input string, moving forward after each try. An anchored search
3001     * or a BnM will bypass this node completely.
3002     */

3003    static class Start extends Node {
3004        int minLength;
3005        Start(Node node) {
3006            this.next = node;
3007            TreeInfo info = new TreeInfo();
3008            next.study(info);
3009            minLength = info.minLength;
3010        }
3011        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3012            if (i > matcher.to - minLength) {
3013                matcher.hitEnd = true;
3014                return false;
3015            }
3016            boolean ret = false;
3017            int guard = matcher.to - minLength;
3018            for (; i <= guard; i++) {
3019                if (ret = next.match(matcher, i, seq))
3020                    break;
3021                if (i == guard)
3022                    matcher.hitEnd = true;
3023            }
3024            if (ret) {
3025                matcher.first = i;
3026                matcher.groups[0] = matcher.first;
3027                matcher.groups[1] = matcher.last;
3028            }
3029            return ret;
3030        }
3031        boolean study(TreeInfo info) {
3032            next.study(info);
3033            info.maxValid = false;
3034            info.deterministic = false;
3035            return false;
3036        }
3037    }
3038
3039    /*
3040     * StartS supports supplementary characters, including unpaired surrogates.
3041     */

3042    static final class StartS extends Start {
3043        StartS(Node node) {
3044        super(node);
3045        }
3046        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3047            if (i > matcher.to - minLength) {
3048                matcher.hitEnd = true;
3049                return false;
3050            }
3051            boolean ret = false;
3052            int guard = matcher.to - minLength;
3053            while (i <= guard) {
3054                if ((ret = next.match(matcher, i, seq)) || i == guard)
3055                    break;
3056        // Optimization to move to the next character. This is
3057
// faster than countChars(seq, i, 1).
3058
if (Character.isHighSurrogate(seq.charAt(i++))) {
3059            if (i < seq.length() && Character.isLowSurrogate(seq.charAt(i))) {
3060            i++;
3061            }
3062        }
3063                if (i == guard)
3064                    matcher.hitEnd = true;
3065            }
3066            if (ret) {
3067                matcher.first = i;
3068                matcher.groups[0] = matcher.first;
3069                matcher.groups[1] = matcher.last;
3070            }
3071            return ret;
3072        }
3073    }
3074
3075    /**
3076     * Node to anchor at the beginning of input. This object implements the
3077     * match for a \A sequence, and the caret anchor will use this if not in
3078     * multiline mode.
3079     */

3080    static final class Begin extends Node {
3081        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3082            int fromIndex = (matcher.anchoringBounds) ?
3083                matcher.from : 0;
3084            if (i == fromIndex && next.match(matcher, i, seq)) {
3085                matcher.first = i;
3086                matcher.groups[0] = i;
3087                matcher.groups[1] = matcher.last;
3088                return true;
3089            } else {
3090                return false;
3091            }
3092        }
3093    }
3094
3095    /**
3096     * Node to anchor at the end of input. This is the absolute end, so this
3097     * should not match at the last newline before the end as $ will.
3098     */

3099    static final class End extends Node {
3100        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3101            int endIndex = (matcher.anchoringBounds) ?
3102                matcher.to : matcher.getTextLength();
3103            if (i == endIndex) {
3104                matcher.hitEnd = true;
3105                return next.match(matcher, i, seq);
3106            }
3107            return false;
3108        }
3109    }
3110
3111    /**
3112     * Node to anchor at the beginning of a line. This is essentially the
3113     * object to match for the multiline ^.
3114     */

3115    static final class Caret extends Node {
3116        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3117            int startIndex = matcher.from;
3118            int endIndex = matcher.to;
3119            if (!matcher.anchoringBounds) {
3120                startIndex = 0;
3121                endIndex = matcher.getTextLength();
3122            }
3123            // Perl does not match ^ at end of input even after newline
3124
if (i == endIndex) {
3125                matcher.hitEnd = true;
3126                return false;
3127            }
3128            if (i > startIndex) {
3129                char ch = seq.charAt(i-1);
3130                if (ch != '\n' && ch != '\r'
3131                    && (ch|1) != '\u2029'
3132                    && ch != '\u0085' ) {
3133                    return false;
3134                }
3135                // Should treat /r/n as one newline
3136
if (ch == '\r' && seq.charAt(i) == '\n')
3137                    return false;
3138            }
3139            return next.match(matcher, i, seq);
3140        }
3141    }
3142
3143    /**
3144     * Node to anchor at the beginning of a line when in unixdot mode.
3145     */

3146    static final class UnixCaret extends Node {
3147        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3148            int startIndex = matcher.from;
3149            int endIndex = matcher.to;
3150            if (!matcher.anchoringBounds) {
3151                startIndex = 0;
3152                endIndex = matcher.getTextLength();
3153            }
3154            // Perl does not match ^ at end of input even after newline
3155
if (i == endIndex) {
3156                matcher.hitEnd = true;
3157                return false;
3158            }
3159            if (i > startIndex) {
3160                char ch = seq.charAt(i-1);
3161                if (ch != '\n') {
3162                    return false;
3163                }
3164            }
3165            return next.match(matcher, i, seq);
3166        }
3167    }
3168
3169    /**
3170     * Node to match the location where the last match ended.
3171     * This is used for the \G construct.
3172     */

3173    static final class LastMatch extends Node {
3174        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3175            if (i != matcher.oldLast)
3176                return false;
3177            return next.match(matcher, i, seq);
3178        }
3179    }
3180
3181    /**
3182     * Node to anchor at the end of a line or the end of input based on the
3183     * multiline mode.
3184     *
3185     * When not in multiline mode, the $ can only match at the very end
3186     * of the input, unless the input ends in a line terminator in which
3187     * it matches right before the last line terminator.
3188     *
3189     * Note that \r\n is considered an atomic line terminator.
3190     *
3191     * Like ^ the $ operator matches at a position, it does not match the
3192     * line terminators themselves.
3193     */

3194    static final class Dollar extends Node {
3195        boolean multiline;
3196        Dollar(boolean mul) {
3197            multiline = mul;
3198        }
3199        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3200            int endIndex = (matcher.anchoringBounds) ?
3201                matcher.to : matcher.getTextLength();
3202            if (!multiline) {
3203                if (i < endIndex - 2)
3204                    return false;
3205                if (i == endIndex - 2) {
3206                    char ch = seq.charAt(i);
3207                    if (ch != '\r')
3208                        return false;
3209                    ch = seq.charAt(i + 1);
3210                    if (ch != '\n')
3211                        return false;
3212                }
3213            }
3214            // Matches before any line terminator; also matches at the
3215
// end of input
3216
// Before line terminator:
3217
// If multiline, we match here no matter what
3218
// If not multiline, fall through so that the end
3219
// is marked as hit; this must be a /r/n or a /n
3220
// at the very end so the end was hit; more input
3221
// could make this not match here
3222
if (i < endIndex) {
3223                char ch = seq.charAt(i);
3224                 if (ch == '\n') {
3225                     // No match between \r\n
3226
if (i > 0 && seq.charAt(i-1) == '\r')
3227                         return false;
3228                     if (multiline)
3229                         return next.match(matcher, i, seq);
3230                 } else if (ch == '\r' || ch == '\u0085' ||
3231                            (ch|1) == '\u2029') {
3232                     if (multiline)
3233                         return next.match(matcher, i, seq);
3234                 } else { // No line terminator, no match
3235
return false;
3236                 }
3237            }
3238            // Matched at current end so hit end
3239
matcher.hitEnd = true;
3240            // If a $ matches because of end of input, then more input
3241
// could cause it to fail!
3242
matcher.requireEnd = true;
3243            return next.match(matcher, i, seq);
3244        }
3245        boolean study(TreeInfo info) {
3246            next.study(info);
3247            return info.deterministic;
3248        }
3249    }
3250
3251    /**
3252     * Node to anchor at the end of a line or the end of input based on the
3253     * multiline mode when in unix lines mode.
3254     */

3255    static final class UnixDollar extends Node {
3256        boolean multiline;
3257        UnixDollar(boolean mul) {
3258            multiline = mul;
3259        }
3260        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3261            int endIndex = (matcher.anchoringBounds) ?
3262                matcher.to : matcher.getTextLength();
3263            if (i < endIndex) {
3264                char ch = seq.charAt(i);
3265                if (ch == '\n') {
3266                    // If not multiline, then only possible to
3267
// match at very end or one before end
3268
if (multiline == false && i != endIndex - 1)
3269                        return false;
3270                    // If multiline return next.match without setting
3271
// matcher.hitEnd
3272
if (multiline)
3273                        return next.match(matcher, i, seq);
3274                } else {
3275                    return false;
3276                }
3277            }
3278            // Matching because at the end or 1 before the end;
3279
// more input could change this so set hitEnd
3280
matcher.hitEnd = true;
3281            // If a $ matches because of end of input, then more input
3282
// could cause it to fail!
3283
matcher.requireEnd = true;
3284            return next.match(matcher, i, seq);
3285        }
3286        boolean study(TreeInfo info) {
3287            next.study(info);
3288            return info.deterministic;
3289        }
3290    }
3291
3292    /**
3293     * Node class for a single character value.
3294     */

3295    static final class Single extends Node {
3296        int ch;
3297    int len;
3298        Single(int n) {
3299            ch = n;
3300        len = Character.charCount(ch);
3301        }
3302        Node dup(boolean not) {
3303            if (not)
3304                return new NotSingle(ch);
3305            else
3306                return new Single(ch);
3307        }
3308        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3309            if (i >= matcher.to) {
3310                matcher.hitEnd = true;
3311        return false;
3312            }
3313        int c = Character.codePointAt(seq, i);
3314            return (c == ch
3315                && next.match(matcher, i+len, seq));
3316        }
3317        boolean study(TreeInfo info) {
3318            info.minLength++;
3319            info.maxLength++;
3320            return next.study(info);
3321        }
3322    }
3323
3324    /**
3325     * Node class to match any character except a single char value.
3326     */

3327    static final class NotSingle extends Node {
3328        int ch;
3329        NotSingle(int n) {
3330            ch = n;
3331        }
3332        Node dup(boolean not) {
3333            if (not)
3334                return new Single(ch);
3335            else
3336                return new NotSingle(ch);
3337        }
3338        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3339            if (i >= matcher.to) {
3340                matcher.hitEnd = true;
3341        return false;
3342            }
3343        int c = Character.codePointAt(seq, i);
3344            return (c != ch
3345                && next.match(matcher, i+Character.charCount(c), seq));
3346        }
3347        boolean study(TreeInfo info) {
3348            info.minLength++;
3349            info.maxLength++;
3350            return next.study(info);
3351        }
3352    }
3353
3354    /**
3355     * Case independent ASCII value.
3356     */

3357    static final class SingleA extends Node {
3358        int ch;
3359        SingleA(int n) {
3360            ch = ASCII.toLower(n);
3361        }
3362        Node dup(boolean not) {
3363            if (not)
3364                return new NotSingleA(ch);
3365            else
3366                return new SingleA(ch);
3367        }
3368        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3369            if (i >= matcher.to) {
3370                matcher.hitEnd = true;
3371            } else {
3372                int c = seq.charAt(i);
3373                if (c == ch || ASCII.toLower(c) == ch) {
3374                    return next.match(matcher, i+1, seq);
3375                }
3376            }
3377            return false;
3378        }
3379
3380        boolean study(TreeInfo info) {
3381            info.minLength++;
3382            info.maxLength++;
3383            return next.study(info);
3384        }
3385    }
3386
3387    static final class NotSingleA extends Node {
3388        int ch;
3389        NotSingleA(int n) {
3390            ch = ASCII.toLower(n);
3391        }
3392        Node dup(boolean not) {
3393            if (not)
3394                return new SingleA(ch);
3395            else
3396                return new NotSingleA(ch);
3397        }
3398        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3399            if (i >= matcher.to) {
3400                matcher.hitEnd = true;
3401            } else {
3402                int c = Character.codePointAt(seq, i);
3403                if (c != ch && ASCII.toLower(c) != ch) {
3404                    return next.match(matcher, i+Character.charCount(c), seq);
3405                }
3406            }
3407            return false;
3408        }
3409
3410        boolean study(TreeInfo info) {
3411            info.minLength++;
3412            info.maxLength++;
3413            return next.study(info);
3414        }
3415    }
3416
3417    /**
3418     * Case independent unicode (including supplementary characters) value.
3419     */

3420    static final class SingleU extends Node {
3421        int ch;
3422    int len;
3423        SingleU(int c) {
3424            ch = Character.toLowerCase(Character.toUpperCase(c));
3425        len = Character.charCount(ch);
3426        }
3427        Node dup(boolean not) {
3428            if (not)
3429                return new NotSingleU(ch);
3430            else
3431                return new SingleU(ch);
3432        }
3433        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3434            if (i >= matcher.to) {
3435                matcher.hitEnd = true;
3436            } else {
3437                int c = Character.codePointAt(seq, i);
3438                if (c == ch)
3439                    return next.match(matcher, i+len, seq);
3440                int cc = Character.toUpperCase(c);
3441                cc = Character.toLowerCase(cc);
3442                if (cc == ch)
3443                    return next.match(matcher, i+Character.charCount(c), seq);
3444            }
3445            return false;
3446        }
3447        boolean study(TreeInfo info) {
3448            info.minLength++;
3449            info.maxLength++;
3450            return next.study(info);
3451        }
3452    }
3453
3454    /**
3455     * Case independent unicode value.
3456     */

3457    static final class NotSingleU extends Node {
3458        int ch;
3459        NotSingleU(int c) {
3460            ch = Character.toLowerCase(Character.toUpperCase((char)c));
3461        }
3462        Node dup(boolean not) {
3463            if (not)
3464                return new SingleU(ch);
3465            else
3466                return new NotSingleU(ch);
3467        }
3468        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3469            if (i >= matcher.to) {
3470                matcher.hitEnd = true;
3471            } else {
3472                int c = Character.codePointAt(seq, i);
3473                if (c == ch)
3474                    return false;
3475                int cc = Character.toUpperCase(c);
3476                cc = Character.toLowerCase(cc);
3477
3478                if (cc != ch)
3479                    return next.match(matcher, i+Character.charCount(c), seq);
3480            }
3481            return false;
3482        }
3483        boolean study(TreeInfo info) {
3484            info.minLength++;
3485            info.maxLength++;
3486            return next.study(info);
3487        }
3488    }
3489
3490    /**
3491     * Node class that matches a Unicode category.
3492     */

3493    static final class Category extends Node {
3494        int atype;
3495        Category(int type) {
3496            atype = type;
3497        }
3498        Node dup(boolean not) {
3499            return new Category(not ? ~atype : atype);
3500        }
3501        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3502            if (i >= matcher.to) {
3503                matcher.hitEnd = true;
3504        return false;
3505            }
3506        int c = Character.codePointAt(seq, i);
3507        return (atype & (1 << Character.getType(c))) != 0
3508                && next.match(matcher, i+Character.charCount(c), seq);
3509        }
3510        boolean study(TreeInfo info) {
3511            info.minLength++;
3512            info.maxLength++;
3513            return next.study(info);
3514        }
3515    }
3516
3517    /**
3518     * Node class that matches a POSIX type.
3519     */

3520    static final class Ctype extends Node {
3521        int ctype;
3522        Ctype(int type) {
3523            ctype = type;
3524        }
3525        Node dup(boolean not) {
3526            if (not) {
3527                return new NotCtype(ctype);
3528            } else {
3529                return new Ctype(ctype);
3530            }
3531        }
3532        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3533            if (i >= matcher.to) {
3534                matcher.hitEnd = true;
3535        return false;
3536            }
3537        int c = Character.codePointAt(seq, i);
3538        return (c < 128 && ASCII.isType(c, ctype)
3539                && next.match(matcher, i+1, seq));
3540        }
3541        boolean study(TreeInfo info) {
3542            info.minLength++;
3543            info.maxLength++;
3544            return next.study(info);
3545        }
3546    }
3547
3548    static final class NotCtype extends Node {
3549        int ctype;
3550        NotCtype(int type) {
3551            ctype = type;
3552        }
3553        Node dup(boolean not) {
3554            if (not) {
3555                return new Ctype(ctype);
3556            } else {
3557                return new NotCtype(ctype);
3558            }
3559        }
3560        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3561            if (i >= matcher.to) {
3562                matcher.hitEnd = true;
3563        return false;
3564            }
3565        int c = Character.codePointAt(seq, i);
3566        return ((c >= 128 || !ASCII.isType(c, ctype))
3567                && next.match(matcher, i+Character.charCount(c), seq));
3568        }
3569        boolean study(TreeInfo info) {
3570            info.minLength++;
3571            info.maxLength++;
3572            return next.study(info);
3573        }
3574    }
3575
3576    static abstract class JavaTypeClass extends Node {
3577        JavaTypeClass() {
3578        }
3579        Node dup(boolean not) {
3580            Node duplicate = null;
3581            try {
3582                duplicate = (Node)this.getClass().newInstance();
3583            } catch (InstantiationException JavaDoc ie) {
3584                throw new Error JavaDoc("Cannot instantiate node");
3585            } catch (IllegalAccessException JavaDoc iae) {
3586                throw new Error JavaDoc("Cannot instantiate node");
3587            }
3588            if (not)
3589                return new Not(duplicate);
3590            else
3591                return duplicate;
3592        }
3593    abstract boolean isProperty(int ch);
3594        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3595            if (i >= matcher.to) {
3596                matcher.hitEnd = true;
3597        return false;
3598            }
3599        int c = Character.codePointAt(seq, i);
3600        return (isProperty(c)
3601                && next.match(matcher, i+Character.charCount(c), seq));
3602        }
3603        boolean study(TreeInfo info) {
3604            info.minLength++;
3605            info.maxLength++;
3606            return next.study(info);
3607        }
3608    }
3609
3610    static final class JavaLowerCase extends JavaTypeClass {
3611        JavaLowerCase() {
3612        }
3613    boolean isProperty(int ch) {
3614        return Character.isLowerCase(ch);
3615    }
3616    }
3617
3618    static final class JavaUpperCase extends JavaTypeClass {
3619        JavaUpperCase() {
3620        }
3621    boolean isProperty(int ch) {
3622        return Character.isUpperCase(ch);
3623        }
3624    }
3625
3626    static final class JavaTitleCase extends JavaTypeClass {
3627        JavaTitleCase() {
3628        }
3629    boolean isProperty(int ch) {
3630        return Character.isTitleCase(ch);
3631    }
3632    }
3633
3634    static final class JavaDigit extends JavaTypeClass {
3635        JavaDigit() {
3636        }
3637    boolean isProperty(int ch) {
3638        return Character.isDigit(ch);
3639        }
3640    }
3641
3642    static final class JavaDefined extends JavaTypeClass {
3643        JavaDefined() {
3644        }
3645    boolean isProperty(int ch) {
3646        return Character.isDefined(ch);
3647        }
3648    }
3649
3650    static final class JavaLetter extends JavaTypeClass {
3651        JavaLetter() {
3652        }
3653    boolean isProperty(int ch) {
3654        return Character.isLetter(ch);
3655        }
3656    }
3657
3658    static final class JavaLetterOrDigit extends JavaTypeClass {
3659        JavaLetterOrDigit() {
3660        }
3661    boolean isProperty(int ch) {
3662        return Character.isLetterOrDigit(ch);
3663        }
3664    }
3665
3666    static final class JavaJavaIdentifierStart extends JavaTypeClass {
3667        JavaJavaIdentifierStart() {
3668        }
3669    boolean isProperty(int ch) {
3670        return Character.isJavaIdentifierStart(ch);
3671        }
3672    }
3673
3674    static final class JavaJavaIdentifierPart extends JavaTypeClass {
3675        JavaJavaIdentifierPart() {
3676        }
3677    boolean isProperty(int ch) {
3678        return Character.isJavaIdentifierPart(ch);
3679        }
3680    }
3681
3682    static final class JavaUnicodeIdentifierStart extends JavaTypeClass {
3683        JavaUnicodeIdentifierStart() {
3684        }
3685    boolean isProperty(int ch) {
3686        return Character.isUnicodeIdentifierStart(ch);
3687        }
3688    }
3689
3690    static final class JavaUnicodeIdentifierPart extends JavaTypeClass {
3691        JavaUnicodeIdentifierPart() {
3692        }
3693    boolean isProperty(int ch) {
3694        return Character.isUnicodeIdentifierPart(ch);
3695        }
3696    }
3697
3698    static final class JavaIdentifierIgnorable extends JavaTypeClass {
3699        JavaIdentifierIgnorable() {
3700        }
3701    boolean isProperty(int ch) {
3702        return Character.isIdentifierIgnorable(ch);
3703        }
3704    }
3705
3706    static final class JavaSpaceChar extends JavaTypeClass {
3707        JavaSpaceChar() {
3708        }
3709    boolean isProperty(int ch) {
3710        return Character.isSpaceChar(ch);
3711        }
3712    }
3713
3714    static final class JavaWhitespace extends JavaTypeClass {
3715        JavaWhitespace() {
3716        }
3717    boolean isProperty(int ch) {
3718        return Character.isWhitespace(ch);
3719        }
3720    }
3721
3722    static final class JavaISOControl extends JavaTypeClass {
3723        JavaISOControl() {
3724        }
3725    boolean isProperty(int ch) {
3726        return Character.isISOControl(ch);
3727        }
3728    }
3729
3730    static final class JavaMirrored extends JavaTypeClass {
3731        JavaMirrored() {
3732        }
3733    boolean isProperty(int ch) {
3734        return Character.isMirrored(ch);
3735        }
3736    }
3737
3738    static final class Specials extends Node {
3739        Specials() {
3740        }
3741        Node dup(boolean not) {
3742            if (not)
3743                return new Not(this);
3744            else
3745                return new Specials();
3746        }
3747        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3748            if (i < matcher.to) {
3749                int ch = seq.charAt(i);
3750                return (((ch-0xFFF0) | (0xFFFD-ch)) >= 0 || ch == 0xFEFF)
3751                    && next.match(matcher, i+1, seq);
3752            }
3753            matcher.hitEnd = true;
3754            return false;
3755        }
3756        boolean study(TreeInfo info) {
3757            info.minLength++;
3758            info.maxLength++;
3759            return next.study(info);
3760        }
3761    }
3762
3763    static final class Not extends Node {
3764        Node atom;
3765        Not(Node atom) {
3766            this.atom = atom;
3767        }
3768        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3769            if (i < matcher.to)
3770                return !atom.match(matcher, i, seq)
3771            && next.match(matcher, i+countChars(seq, i, 1), seq);
3772        matcher.hitEnd = true;
3773        return false;
3774        }
3775        boolean study(TreeInfo info) {
3776            info.minLength++;
3777            info.maxLength++;
3778            return next.study(info);
3779        }
3780    }
3781
3782    /**
3783     * Node class for a case sensitive sequence of literal characters.
3784     */

3785    static class Slice extends Node {
3786        int[] buffer;
3787        Slice(int[] buf) {
3788            buffer = buf;
3789        }
3790        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3791            int[] buf = buffer;
3792            int len = buf.length;
3793
3794            // Unfortunately we must now void this opto
3795
// in order to properly report hitEnd...
3796
//if (i + len > matcher.to) {
3797
// matcher.hitEnd = true;
3798
// return false;
3799
//}
3800

3801            for (int j=0; j<len; j++) {
3802                if ((i+j) >= matcher.to) {
3803                    matcher.hitEnd = true;
3804                    return false;
3805                }
3806                if (buf[j] != seq.charAt(i+j))
3807                    return false;
3808            }
3809
3810            return next.match(matcher, i+len, seq);
3811        }
3812        boolean study(TreeInfo info) {
3813            info.minLength += buffer.length;
3814            info.maxLength += buffer.length;
3815            return next.study(info);
3816        }
3817    }
3818
3819    /**
3820     * Node class for a case insensitive sequence of literal characters.
3821     */

3822    static final class SliceA extends Node {
3823        int[] buffer;
3824        SliceA(int[] buf) {
3825            buffer = buf;
3826        }
3827        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3828            int[] buf = buffer;
3829            int len = buf.length;
3830            for (int j=0; j<len; j++) {
3831                if ((i+j) >= matcher.to) {
3832                    matcher.hitEnd = true;
3833                    return false;
3834                }
3835                int c = ASCII.toLower(seq.charAt(i+j));
3836                if (buf[j] != c)
3837                    return false;
3838            }
3839            return next.match(matcher, i+len, seq);
3840        }
3841        boolean study(TreeInfo info) {
3842            info.minLength += buffer.length;
3843            info.maxLength += buffer.length;
3844            return next.study(info);
3845        }
3846    }
3847
3848    /**
3849     * Node class for a case insensitive sequence of literal characters.
3850     * Uses unicode case folding.
3851     */

3852    static final class SliceU extends Node {
3853        int[] buffer;
3854        SliceU(int[] buf) {
3855            buffer = buf;
3856        }
3857        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3858            int[] buf = buffer;
3859            int x = i;
3860            for (int j = 0; j < buf.length; j++) {
3861                if (x >= matcher.to) {
3862                    matcher.hitEnd = true;
3863                    return false;
3864                }
3865                int c = Character.codePointAt(seq, x);
3866                int cc = Character.toUpperCase(c);
3867                cc = Character.toLowerCase(cc);
3868                if (buf[j] != cc) {
3869                    return false;
3870                }
3871        x += Character.charCount(c);
3872        if (x > matcher.to) {
3873                    matcher.hitEnd = true;
3874            return false;
3875        }
3876            }
3877            return next.match(matcher, x, seq);
3878        }
3879        boolean study(TreeInfo info) {
3880            info.minLength += buffer.length;
3881            info.maxLength += buffer.length;
3882            return next.study(info);
3883        }
3884    }
3885
3886    /**
3887     * Node class for a case sensitive sequence of literal characters
3888     * including supplementary characters.
3889     */

3890    static final class SliceS extends Slice {
3891        SliceS(int[] buf) {
3892            super(buf);
3893        }
3894        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3895        int[] buf = buffer;
3896        int x = i;
3897        for (int j = 0; j < buf.length; j++) {
3898                if (x >= matcher.to) {
3899                    matcher.hitEnd = true;
3900                    return false;
3901                }
3902        int c = Character.codePointAt(seq, x);
3903        if (buf[j] != c)
3904            return false;
3905        x += Character.charCount(c);
3906        if (x > matcher.to) {
3907                    matcher.hitEnd = true;
3908            return false;
3909                }
3910        }
3911
3912            return next.match(matcher, x, seq);
3913        }
3914    }
3915
3916    /**
3917     * Node class for matching characters within an explicit value range.
3918     */

3919    static class Range extends Node {
3920        int lower, upper;
3921        Range() {
3922        }
3923        Range(int n) {
3924            lower = n >>> 16;
3925            upper = n & 0xFFFF;
3926        }
3927    Range(int lower, int upper) {
3928        this.lower = lower;
3929        this.upper = upper;
3930    }
3931        Node dup(boolean not) {
3932            if (not)
3933                return new NotRange(lower, upper);
3934            else
3935                return new Range(lower, upper);
3936        }
3937        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3938            if (i < matcher.to) {
3939                int ch = Character.codePointAt(seq, i);
3940                return ((ch-lower)|(upper-ch)) >= 0
3941                    && next.match(matcher, i+Character.charCount(ch), seq);
3942            }
3943            matcher.hitEnd = true;
3944            return false;
3945        }
3946        boolean study(TreeInfo info) {
3947            info.minLength++;
3948            info.maxLength++;
3949            return next.study(info);
3950        }
3951    }
3952
3953    /**
3954     * Node class for matching characters within an explicit value range
3955     * in a case insensitive manner.
3956     */

3957    static final class CIRange extends Range {
3958        CIRange(int n) {
3959            lower = n >>> 16;
3960            upper = n & 0xFFFF;
3961        }
3962        CIRange(int lower, int upper) {
3963        super(lower, upper);
3964        }
3965        Node dup(boolean not) {
3966            if (not)
3967                return new CINotRange(lower, upper);
3968            else
3969                return new CIRange(lower, upper);
3970        }
3971        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
3972            if (i < matcher.to) {
3973                int ch = Character.codePointAt(seq, i);
3974                boolean m = (((ch-lower)|(upper-ch)) >= 0);
3975                if (!m) {
3976                    int cc = Character.toUpperCase(ch);
3977                    m = (((cc-lower)|(upper-cc)) >= 0);
3978                    if (!m) {
3979                        cc = Character.toLowerCase(cc);
3980                        m = (((cc-lower)|(upper-cc)) >= 0);
3981                    }
3982                }
3983                return (m && next.match(matcher, i+Character.charCount(ch), seq));
3984            }
3985            matcher.hitEnd = true;
3986            return false;
3987        }
3988    }
3989
3990    static class NotRange extends Node {
3991        int lower, upper;
3992        NotRange() {
3993        }
3994        NotRange(int n) {
3995            lower = n >>> 16;
3996            upper = n & 0xFFFF;
3997        }
3998        NotRange(int lower, int upper) {
3999            this.lower = lower;
4000        this.upper = upper;
4001    }
4002        Node dup(boolean not) {
4003            if (not) {
4004                return new Range(lower, upper);
4005            } else {
4006                return new NotRange(lower, upper);
4007            }
4008        }
4009        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4010            if (i < matcher.to) {
4011                int ch = Character.codePointAt(seq, i);
4012                return ((ch-lower)|(upper-ch)) < 0
4013                    && next.match(matcher, i+Character.charCount(ch), seq);
4014            }
4015            matcher.hitEnd = true;
4016            return false;
4017        }
4018        boolean study(TreeInfo info) {
4019            info.minLength++;
4020            info.maxLength++;
4021            return next.study(info);
4022        }
4023    }
4024
4025    static class CINotRange extends NotRange {
4026        int lower, upper;
4027        CINotRange(int n) {
4028            lower = n >>> 16;
4029            upper = n & 0xFFFF;
4030        }
4031        CINotRange(int lower, int upper) {
4032            this.lower = lower;
4033            this.upper = upper;
4034    }
4035        Node dup(boolean not) {
4036            if (not) {
4037                return new CIRange(lower, upper);
4038            } else {
4039                return new CINotRange(lower, upper);
4040            }
4041        }
4042        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4043            if (i < matcher.to) {
4044                int ch = Character.codePointAt(seq, i);
4045                boolean m = (((ch-lower)|(upper-ch)) < 0);
4046                if (m) {
4047                    int cc = Character.toUpperCase(ch);
4048                    m = (((cc-lower)|(upper-cc)) < 0);
4049                    if (m) {
4050                        cc = Character.toLowerCase(cc);
4051                        m = (((cc-lower)|(upper-cc)) < 0);
4052                    }
4053                }
4054
4055                return (m && next.match(matcher, i+Character.charCount(ch), seq));
4056            }
4057            matcher.hitEnd = true;
4058            return false;
4059        }
4060    }
4061
4062    /**
4063     * Implements the Unicode category ALL and the dot metacharacter when
4064     * in dotall mode.
4065     */

4066    static final class All extends Node {
4067        All() {
4068            super();
4069        }
4070        Node dup(boolean not) {
4071            if (not) {
4072                return new Single(-1);
4073            } else {
4074                return new All();
4075            }
4076        }
4077        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4078            if (i < matcher.to) {
4079                return next.match(matcher, i+countChars(seq, i, 1), seq);
4080            }
4081            matcher.hitEnd = true;
4082            return false;
4083        }
4084        boolean study(TreeInfo info) {
4085            info.minLength++;
4086            info.maxLength++;
4087            return next.study(info);
4088        }
4089    }
4090
4091    /**
4092     * Node class for the dot metacharacter when dotall is not enabled.
4093     */

4094    static final class Dot extends Node {
4095        Dot() {
4096            super();
4097        }
4098        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4099            if (i < matcher.to) {
4100                int ch = Character.codePointAt(seq, i);
4101                return (ch != '\n' && ch != '\r'
4102                    && (ch|1) != '\u2029'
4103                    && ch != '\u0085'
4104                    && next.match(matcher, i+Character.charCount(ch), seq));
4105            }
4106            matcher.hitEnd = true;
4107            return false;
4108        }
4109        boolean study(TreeInfo info) {
4110            info.minLength++;
4111            info.maxLength++;
4112            return next.study(info);
4113        }
4114    }
4115
4116    /**
4117     * Node class for the dot metacharacter when dotall is not enabled
4118     * but UNIX_LINES is enabled.
4119     */

4120    static final class UnixDot extends Node {
4121        UnixDot() {
4122            super();
4123        }
4124        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4125            if (i < matcher.to) {
4126                int ch = Character.codePointAt(seq, i);
4127                return (ch != '\n' && next.match(matcher, i+Character.charCount(ch), seq));
4128            }
4129            matcher.hitEnd = true;
4130            return false;
4131        }
4132        boolean study(TreeInfo info) {
4133            info.minLength++;
4134            info.maxLength++;
4135            return next.study(info);
4136        }
4137    }
4138
4139    /**
4140     * The 0 or 1 quantifier. This one class implements all three types.
4141     */

4142    static final class Ques extends Node {
4143        Node atom;
4144        int type;
4145        Ques(Node node, int type) {
4146            this.atom = node;
4147            this.type = type;
4148        }
4149        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4150            switch (type) {
4151            case GREEDY:
4152                return (atom.match(matcher, i, seq) && next.match(matcher, matcher.last, seq))
4153                    || next.match(matcher, i, seq);
4154            case LAZY:
4155                return next.match(matcher, i, seq)
4156                    || (atom.match(matcher, i, seq) && next.match(matcher, matcher.last, seq));
4157            case POSSESSIVE:
4158                if (atom.match(matcher, i, seq)) i = matcher.last;
4159                return next.match(matcher, i, seq);
4160            default:
4161                return atom.match(matcher, i, seq) && next.match(matcher, matcher.last, seq);
4162            }
4163        }
4164        boolean study(TreeInfo info) {
4165            if (type != INDEPENDENT) {
4166                int minL = info.minLength;
4167                atom.study(info);
4168                info.minLength = minL;
4169                info.deterministic = false;
4170                return next.study(info);
4171            } else {
4172                atom.study(info);
4173                return next.study(info);
4174            }
4175        }
4176    }
4177
4178    /**
4179     * Handles the curly-brace style repetition with a specified minimum and
4180     * maximum occurrences. The * quantifier is handled as a special case.
4181     * This class handles the three types.
4182     */

4183    static final class Curly extends Node {
4184        Node atom;
4185        int type;
4186        int cmin;
4187        int cmax;
4188
4189        Curly(Node node, int cmin, int cmax, int type) {
4190            this.atom = node;
4191            this.type = type;
4192            this.cmin = cmin;
4193            this.cmax = cmax;
4194        }
4195        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4196            int j;
4197            for (j = 0; j < cmin; j++) {
4198                if (atom.match(matcher, i, seq)) {
4199                    i = matcher.last;
4200                    continue;
4201                }
4202                return false;
4203            }
4204            if (type == GREEDY)
4205                return match0(matcher, i, j, seq);
4206            else if (type == LAZY)
4207                return match1(matcher, i, j, seq);
4208            else
4209                return match2(matcher, i, j, seq);
4210        }
4211        // Greedy match.
4212
// i is the index to start matching at
4213
// j is the number of atoms that have matched
4214
boolean match0(Matcher JavaDoc matcher, int i, int j, CharSequence JavaDoc seq) {
4215            if (j >= cmax) {
4216                // We have matched the maximum... continue with the rest of
4217
// the regular expression
4218
return next.match(matcher, i, seq);
4219            }
4220            int backLimit = j;
4221            while (atom.match(matcher, i, seq)) {
4222                // k is the length of this match
4223
int k = matcher.last - i;
4224                if (k == 0) // Zero length match
4225
break;
4226                // Move up index and number matched
4227
i = matcher.last;
4228                j++;
4229                // We are greedy so match as many as we can
4230
while (j < cmax) {
4231                    if (!atom.match(matcher, i, seq))
4232                        break;
4233                    if (i + k != matcher.last) {
4234                        if (match0(matcher, matcher.last, j+1, seq))
4235                            return true;
4236                        break;
4237                    }
4238                    i += k;
4239                    j++;
4240                }
4241                // Handle backing off if match fails
4242
while (j >= backLimit) {
4243                   if (next.match(matcher, i, seq))
4244                        return true;
4245                    i -= k;
4246                    j--;
4247                }
4248                return false;
4249            }
4250            return next.match(matcher, i, seq);
4251        }
4252        // Reluctant match. At this point, the minimum has been satisfied.
4253
// i is the index to start matching at
4254
// j is the number of atoms that have matched
4255
boolean match1(Matcher JavaDoc matcher, int i, int j, CharSequence JavaDoc seq) {
4256            for (;;) {
4257                // Try finishing match without consuming any more
4258
if (next.match(matcher, i, seq))
4259                    return true;
4260                // At the maximum, no match found
4261
if (j >= cmax)
4262                    return false;
4263                // Okay, must try one more atom
4264
if (!atom.match(matcher, i, seq))
4265                    return false;
4266                // If we haven't moved forward then must break out
4267
if (i == matcher.last)
4268                    return false;
4269                // Move up index and number matched
4270
i = matcher.last;
4271                j++;
4272            }
4273        }
4274        boolean match2(Matcher JavaDoc matcher, int i, int j, CharSequence JavaDoc seq) {
4275            for (; j < cmax; j++) {
4276                if (!atom.match(matcher, i, seq))
4277                    break;
4278                if (i == matcher.last)
4279                    break;
4280                i = matcher.last;
4281            }
4282            return next.match(matcher, i, seq);
4283        }
4284        boolean study(TreeInfo info) {
4285            // Save original info
4286
int minL = info.minLength;
4287            int maxL = info.maxLength;
4288            boolean maxV = info.maxValid;
4289            boolean detm = info.deterministic;
4290            info.reset();
4291
4292            atom.study(info);
4293
4294            int temp = info.minLength * cmin + minL;
4295            if (temp < minL) {
4296                temp = 0xFFFFFFF; // arbitrary large number
4297
}
4298            info.minLength = temp;
4299
4300            if (maxV & info.maxValid) {
4301                temp = info.maxLength * cmax + maxL;
4302                info.maxLength = temp;
4303                if (temp < maxL) {
4304                    info.maxValid = false;
4305                }
4306            } else {
4307                info.maxValid = false;
4308            }
4309
4310            if (info.deterministic && cmin == cmax)
4311                info.deterministic = detm;
4312            else
4313                info.deterministic = false;
4314
4315            return next.study(info);
4316        }
4317    }
4318
4319    /**
4320     * Handles the curly-brace style repetition with a specified minimum and
4321     * maximum occurrences in deterministic cases. This is an iterative
4322     * optimization over the Prolog and Loop system which would handle this
4323     * in a recursive way. The * quantifier is handled as a special case.
4324     * If capture is true then this class saves group settings and ensures
4325     * that groups are unset when backing off of a group match.
4326     */

4327    static final class GroupCurly extends Node {
4328        Node atom;
4329        int type;
4330        int cmin;
4331        int cmax;
4332        int localIndex;
4333        int groupIndex;
4334        boolean capture;
4335
4336        GroupCurly(Node node, int cmin, int cmax, int type, int local,
4337                   int group, boolean capture) {
4338            this.atom = node;
4339            this.type = type;
4340            this.cmin = cmin;
4341            this.cmax = cmax;
4342            this.localIndex = local;
4343            this.groupIndex = group;
4344            this.capture = capture;
4345        }
4346        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4347            int[] groups = matcher.groups;
4348            int[] locals = matcher.locals;
4349            int save0 = locals[localIndex];
4350            int save1 = 0;
4351            int save2 = 0;
4352
4353            if (capture) {
4354                save1 = groups[groupIndex];
4355                save2 = groups[groupIndex+1];
4356            }
4357
4358            // Notify GroupTail there is no need to setup group info
4359
// because it will be set here
4360
locals[localIndex] = -1;
4361
4362            boolean ret = true;
4363            for (int j = 0; j < cmin; j++) {
4364                if (atom.match(matcher, i, seq)) {
4365                    if (capture) {
4366                        groups[groupIndex] = i;
4367                        groups[groupIndex+1] = matcher.last;
4368                    }
4369                    i = matcher.last;
4370                } else {
4371                    ret = false;
4372                    break;
4373                }
4374            }
4375            if (!ret) {
4376                locals[localIndex] = save0;
4377                if (capture) {
4378                    groups[groupIndex] = save1;
4379                    groups[groupIndex+1] = save2;
4380                }
4381            } else if (type == GREEDY) {
4382                ret = match0(matcher, i, cmin, seq);
4383            } else if (type == LAZY) {
4384                ret = match1(matcher, i, cmin, seq);
4385            } else {
4386                ret = match2(matcher, i, cmin, seq);
4387            }
4388            return ret;
4389        }
4390        // Aggressive group match
4391
boolean match0(Matcher JavaDoc matcher, int i, int j, CharSequence JavaDoc seq) {
4392            int[] groups = matcher.groups;
4393            int save0 = 0;
4394            int save1 = 0;
4395            if (capture) {
4396                save0 = groups[groupIndex];
4397                save1 = groups[groupIndex+1];
4398            }
4399            for (;;) {
4400                if (j >= cmax)
4401                    break;
4402                if (!atom.match(matcher, i, seq))
4403                    break;
4404                int k = matcher.last - i;
4405                if (k <= 0) {
4406                    if (capture) {
4407                        groups[groupIndex] = i;
4408                        groups[groupIndex+1] = i + k;
4409                    }
4410                    i = i + k;
4411                    break;
4412                }
4413                for (;;) {
4414                    if (capture) {
4415                        groups[groupIndex] = i;
4416                        groups[groupIndex+1] = i + k;
4417                    }
4418                    i = i + k;
4419                    if (++j >= cmax)
4420                        break;
4421                    if (!atom.match(matcher, i, seq))
4422                        break;
4423                    if (i + k != matcher.last) {
4424                        if (match0(matcher, i, j, seq))
4425                            return true;
4426                        break;
4427                    }
4428                }
4429                while (j > cmin) {
4430                    if (next.match(matcher, i, seq)) {
4431                        if (capture) {
4432                            groups[groupIndex+1] = i;
4433                            groups[groupIndex] = i - k;
4434                        }
4435                        i = i - k;
4436                        return true;
4437                    }
4438                    // backing off
4439
if (capture) {
4440                        groups[groupIndex+1] = i;
4441                        groups[groupIndex] = i - k;
4442                    }
4443                    i = i - k;
4444                    j--;
4445                }
4446                break;
4447            }
4448            if (capture) {
4449                groups[groupIndex] = save0;
4450                groups[groupIndex+1] = save1;
4451            }
4452            return next.match(matcher, i, seq);
4453        }
4454        // Reluctant matching
4455
boolean match1(Matcher JavaDoc matcher, int i, int j, CharSequence JavaDoc seq) {
4456            for (;;) {
4457                if (next.match(matcher, i, seq))
4458                    return true;
4459                if (j >= cmax)
4460                    return false;
4461                if (!atom.match(matcher, i, seq))
4462                    return false;
4463                if (i == matcher.last)
4464                    return false;
4465                if (capture) {
4466                    matcher.groups[groupIndex] = i;
4467                    matcher.groups[groupIndex+1] = matcher.last;
4468                }
4469                i = matcher.last;
4470                j++;
4471            }
4472        }
4473        // Possessive matching
4474
boolean match2(Matcher JavaDoc matcher, int i, int j, CharSequence JavaDoc seq) {
4475            for (; j < cmax; j++) {
4476                if (!atom.match(matcher, i, seq)) {
4477                    break;
4478                }
4479                if (capture) {
4480                    matcher.groups[groupIndex] = i;
4481                    matcher.groups[groupIndex+1] = matcher.last;
4482                }
4483                if (i == matcher.last) {
4484                    break;
4485                }
4486                i = matcher.last;
4487            }
4488            return next.match(matcher, i, seq);
4489        }
4490        boolean study(TreeInfo info) {
4491            // Save original info
4492
int minL = info.minLength;
4493            int maxL = info.maxLength;
4494            boolean maxV = info.maxValid;
4495            boolean detm = info.deterministic;
4496            info.reset();
4497
4498            atom.study(info);
4499
4500            int temp = info.minLength * cmin + minL;
4501            if (temp < minL) {
4502                temp = 0xFFFFFFF; // Arbitrary large number
4503
}
4504            info.minLength = temp;
4505
4506            if (maxV & info.maxValid) {
4507                temp = info.maxLength * cmax + maxL;
4508                info.maxLength = temp;
4509                if (temp < maxL) {
4510                    info.maxValid = false;
4511                }
4512            } else {
4513                info.maxValid = false;
4514            }
4515
4516            if (info.deterministic && cmin == cmax) {
4517                info.deterministic = detm;
4518            } else {
4519                info.deterministic = false;
4520            }
4521
4522            return next.study(info);
4523        }
4524    }
4525
4526    /**
4527     * Handles the branching of alternations. Note this is also used for
4528     * the ? quantifier to branch between the case where it matches once
4529     * and where it does not occur.
4530     */

4531    static final class Branch extends Node {
4532        Node prev;
4533        Branch(Node lhs, Node rhs) {
4534            this.prev = lhs;
4535            this.next = rhs;
4536        }
4537        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4538            return (prev.match(matcher, i, seq) || next.match(matcher, i, seq));
4539        }
4540        boolean study(TreeInfo info) {
4541            int minL = info.minLength;
4542            int maxL = info.maxLength;
4543            boolean maxV = info.maxValid;
4544            info.reset();
4545            prev.study(info);
4546
4547            int minL2 = info.minLength;
4548            int maxL2 = info.maxLength;
4549            boolean maxV2 = info.maxValid;
4550            info.reset();
4551            next.study(info);
4552
4553            info.minLength = minL + Math.min(minL2, info.minLength);
4554            info.maxLength = maxL + Math.max(maxL2, info.maxLength);
4555            info.maxValid = (maxV & maxV2 & info.maxValid);
4556            info.deterministic = false;
4557            return false;
4558        }
4559    }
4560
4561    /**
4562     * The GroupHead saves the location where the group begins in the locals
4563     * and restores them when the match is done.
4564     *
4565     * The matchRef is used when a reference to this group is accessed later
4566     * in the expression. The locals will have a negative value in them to
4567     * indicate that we do not want to unset the group if the reference
4568     * doesn't match.
4569     */

4570    static final class GroupHead extends Node {
4571        int localIndex;
4572        GroupHead(int localCount) {
4573            localIndex = localCount;
4574        }
4575        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4576            int save = matcher.locals[localIndex];
4577            matcher.locals[localIndex] = i;
4578            boolean ret = next.match(matcher, i, seq);
4579            matcher.locals[localIndex] = save;
4580            return ret;
4581        }
4582        boolean matchRef(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4583            int save = matcher.locals[localIndex];
4584            matcher.locals[localIndex] = ~i; // HACK
4585
boolean ret = next.match(matcher, i, seq);
4586            matcher.locals[localIndex] = save;
4587            return ret;
4588        }
4589    }
4590
4591    /**
4592     * Recursive reference to a group in the regular expression. It calls
4593     * matchRef because if the reference fails to match we would not unset
4594     * the group.
4595     */

4596    static final class GroupRef extends Node {
4597        GroupHead head;
4598        GroupRef(GroupHead head) {
4599            this.head = head;
4600        }
4601        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4602            return head.matchRef(matcher, i, seq)
4603                && next.match(matcher, matcher.last, seq);
4604        }
4605        boolean study(TreeInfo info) {
4606            info.maxValid = false;
4607            info.deterministic = false;
4608            return next.study(info);
4609        }
4610    }
4611
4612    /**
4613     * The GroupTail handles the setting of group beginning and ending
4614     * locations when groups are successfully matched. It must also be able to
4615     * unset groups that have to be backed off of.
4616     *
4617     * The GroupTail node is also used when a previous group is referenced,
4618     * and in that case no group information needs to be set.
4619     */

4620    static final class GroupTail extends Node {
4621        int localIndex;
4622        int groupIndex;
4623        GroupTail(int localCount, int groupCount) {
4624            localIndex = localCount;
4625            groupIndex = groupCount + groupCount;
4626        }
4627        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4628            int tmp = matcher.locals[localIndex];
4629            if (tmp >= 0) { // This is the normal group case.
4630
// Save the group so we can unset it if it
4631
// backs off of a match.
4632
int groupStart = matcher.groups[groupIndex];
4633                int groupEnd = matcher.groups[groupIndex+1];
4634
4635                matcher.groups[groupIndex] = tmp;
4636                matcher.groups[groupIndex+1] = i;
4637                if (next.match(matcher, i, seq)) {
4638                    return true;
4639                }
4640                matcher.groups[groupIndex] = groupStart;
4641                matcher.groups[groupIndex+1] = groupEnd;
4642                return false;
4643            } else {
4644                // This is a group reference case. We don't need to save any
4645
// group info because it isn't really a group.
4646
matcher.last = i;
4647                return true;
4648            }
4649        }
4650    }
4651
4652    /**
4653     * This sets up a loop to handle a recursive quantifier structure.
4654     */

4655    static final class Prolog extends Node {
4656        Loop loop;
4657        Prolog(Loop loop) {
4658            this.loop = loop;
4659        }
4660        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4661            return loop.matchInit(matcher, i, seq);
4662        }
4663        boolean study(TreeInfo info) {
4664            return loop.study(info);
4665        }
4666    }
4667
4668    /**
4669     * Handles the repetition count for a greedy Curly. The matchInit
4670     * is called from the Prolog to save the index of where the group
4671     * beginning is stored. A zero length group check occurs in the
4672     * normal match but is skipped in the matchInit.
4673     */

4674    static class Loop extends Node {
4675        Node body;
4676        int countIndex; // local count index in matcher locals
4677
int beginIndex; // group beginning index
4678
int cmin, cmax;
4679        Loop(int countIndex, int beginIndex) {
4680            this.countIndex = countIndex;
4681            this.beginIndex = beginIndex;
4682        }
4683        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4684            // Avoid infinite loop in zero-length case.
4685
if (i > matcher.locals[beginIndex]) {
4686                int count = matcher.locals[countIndex];
4687
4688                // This block is for before we reach the minimum
4689
// iterations required for the loop to match
4690
if (count < cmin) {
4691                    matcher.locals[countIndex] = count + 1;
4692                    boolean b = body.match(matcher, i, seq);
4693                    // If match failed we must backtrack, so
4694
// the loop count should NOT be incremented
4695
if (!b)
4696                        matcher.locals[countIndex] = count;
4697                    // Return success or failure since we are under
4698
// minimum
4699
return b;
4700                }
4701                // This block is for after we have the minimum
4702
// iterations required for the loop to match
4703
if (count < cmax) {
4704                    matcher.locals[countIndex] = count + 1;
4705                    boolean b = body.match(matcher, i, seq);
4706                    // If match failed we must backtrack, so
4707
// the loop count should NOT be incremented
4708
if (!b)
4709                        matcher.locals[countIndex] = count;
4710                    else
4711                        return true;
4712                }
4713            }
4714            return next.match(matcher, i, seq);
4715        }
4716        boolean matchInit(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4717            int save = matcher.locals[countIndex];
4718            boolean ret = false;
4719            if (0 < cmin) {
4720                matcher.locals[countIndex] = 1;
4721                ret = body.match(matcher, i, seq);
4722            } else if (0 < cmax) {
4723                matcher.locals[countIndex] = 1;
4724                ret = body.match(matcher, i, seq);
4725                if (ret == false)
4726                    ret = next.match(matcher, i, seq);
4727            } else {
4728                ret = next.match(matcher, i, seq);
4729            }
4730            matcher.locals[countIndex] = save;
4731            return ret;
4732        }
4733        boolean study(TreeInfo info) {
4734            info.maxValid = false;
4735            info.deterministic = false;
4736            return false;
4737        }
4738    }
4739
4740    /**
4741     * Handles the repetition count for a reluctant Curly. The matchInit
4742     * is called from the Prolog to save the index of where the group
4743     * beginning is stored. A zero length group check occurs in the
4744     * normal match but is skipped in the matchInit.
4745     */

4746    static final class LazyLoop extends Loop {
4747        LazyLoop(int countIndex, int beginIndex) {
4748            super(countIndex, beginIndex);
4749        }
4750        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4751            // Check for zero length group
4752
if (i > matcher.locals[beginIndex]) {
4753                int count = matcher.locals[countIndex];
4754                if (count < cmin) {
4755                    matcher.locals[countIndex] = count + 1;
4756                    boolean result = body.match(matcher, i, seq);
4757                    // If match failed we must backtrack, so
4758
// the loop count should NOT be incremented
4759
if (!result)
4760                        matcher.locals[countIndex] = count;
4761                    return result;
4762                }
4763                if (next.match(matcher, i, seq))
4764                    return true;
4765                if (count < cmax) {
4766                    matcher.locals[countIndex] = count + 1;
4767                    boolean result = body.match(matcher, i, seq);
4768                    // If match failed we must backtrack, so
4769
// the loop count should NOT be incremented
4770
if (!result)
4771                        matcher.locals[countIndex] = count;
4772                    return result;
4773                }
4774                return false;
4775            }
4776            return next.match(matcher, i, seq);
4777        }
4778        boolean matchInit(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4779            int save = matcher.locals[countIndex];
4780            boolean ret = false;
4781            if (0 < cmin) {
4782                matcher.locals[countIndex] = 1;
4783                ret = body.match(matcher, i, seq);
4784            } else if (next.match(matcher, i, seq)) {
4785                ret = true;
4786            } else if (0 < cmax) {
4787                matcher.locals[countIndex] = 1;
4788                ret = body.match(matcher, i, seq);
4789            }
4790            matcher.locals[countIndex] = save;
4791            return ret;
4792        }
4793        boolean study(TreeInfo info) {
4794            info.maxValid = false;
4795            info.deterministic = false;
4796            return false;
4797        }
4798    }
4799
4800    /**
4801     * Refers to a group in the regular expression. Attempts to match
4802     * whatever the group referred to last matched.
4803     */

4804    static class BackRef extends Node {
4805        int groupIndex;
4806        BackRef(int groupCount) {
4807            super();
4808            groupIndex = groupCount + groupCount;
4809        }
4810        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4811            int j = matcher.groups[groupIndex];
4812            int k = matcher.groups[groupIndex+1];
4813
4814            int groupSize = k - j;
4815
4816            // If the referenced group didn't match, neither can this
4817
if (j < 0)
4818                return false;
4819
4820            // If there isn't enough input left no match
4821
if (i + groupSize > matcher.to) {
4822                matcher.hitEnd = true;
4823                return false;
4824            }
4825
4826            // Check each new char to make sure it matches what the group
4827
// referenced matched last time around
4828
for (int index=0; index<groupSize; index++)
4829                if (seq.charAt(i+index) != seq.charAt(j+index))
4830                    return false;
4831
4832            return next.match(matcher, i+groupSize, seq);
4833        }
4834        boolean study(TreeInfo info) {
4835            info.maxValid = false;
4836            return next.study(info);
4837        }
4838    }
4839
4840    static class CIBackRef extends Node {
4841        int groupIndex;
4842        CIBackRef(int groupCount) {
4843            super();
4844            groupIndex = groupCount + groupCount;
4845        }
4846        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4847            int j = matcher.groups[groupIndex];
4848            int k = matcher.groups[groupIndex+1];
4849
4850            int groupSize = k - j;
4851
4852            // If the referenced group didn't match, neither can this
4853
if (j < 0)
4854                return false;
4855
4856            // If there isn't enough input left no match
4857
if (i + groupSize > matcher.to) {
4858                matcher.hitEnd = true;
4859                return false;
4860            }
4861
4862            // Check each new char to make sure it matches what the group
4863
// referenced matched last time around
4864
int x = i;
4865            for (int index=0; index<groupSize; index++) {
4866                int c1 = Character.codePointAt(seq, x);
4867                int c2 = Character.codePointAt(seq, j);
4868                if (c1 != c2) {
4869                    int cc1 = Character.toUpperCase(c1);
4870                    int cc2 = Character.toUpperCase(c2);
4871                    if (cc1 != cc2) {
4872                        cc1 = Character.toLowerCase(cc1);
4873                        cc2 = Character.toLowerCase(cc2);
4874                        if (cc1 != cc2)
4875                            return false;
4876                    }
4877                }
4878        x += Character.charCount(c1);
4879        j += Character.charCount(c2);
4880            }
4881
4882            return next.match(matcher, i+groupSize, seq);
4883        }
4884        boolean study(TreeInfo info) {
4885            info.maxValid = false;
4886            return next.study(info);
4887        }
4888    }
4889
4890    /**
4891     * Searches until the next instance of its atom. This is useful for
4892     * finding the atom efficiently without passing an instance of it
4893     * (greedy problem) and without a lot of wasted search time (reluctant
4894     * problem).
4895     */

4896    static final class First extends Node {
4897        Node atom;
4898        First(Node node) {
4899            this.atom = BnM.optimize(node);
4900        }
4901        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4902            if (atom instanceof BnM) {
4903                return atom.match(matcher, i, seq)
4904                    && next.match(matcher, matcher.last, seq);
4905            }
4906            for (;;) {
4907                if (i > matcher.to) {
4908                    matcher.hitEnd = true;
4909                    return false;
4910                }
4911                if (atom.match(matcher, i, seq)) {
4912                    return next.match(matcher, matcher.last, seq);
4913                }
4914                i += countChars(seq, i, 1);
4915                matcher.first++;
4916            }
4917        }
4918        boolean study(TreeInfo info) {
4919            atom.study(info);
4920            info.maxValid = false;
4921            info.deterministic = false;
4922            return next.study(info);
4923        }
4924    }
4925
4926    static final class Conditional extends Node {
4927        Node cond, yes, not;
4928        Conditional(Node cond, Node yes, Node not) {
4929            this.cond = cond;
4930            this.yes = yes;
4931            this.not = not;
4932        }
4933        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4934            if (cond.match(matcher, i, seq)) {
4935                return yes.match(matcher, i, seq);
4936            } else {
4937                return not.match(matcher, i, seq);
4938            }
4939        }
4940        boolean study(TreeInfo info) {
4941            int minL = info.minLength;
4942            int maxL = info.maxLength;
4943            boolean maxV = info.maxValid;
4944            info.reset();
4945            yes.study(info);
4946
4947            int minL2 = info.minLength;
4948            int maxL2 = info.maxLength;
4949            boolean maxV2 = info.maxValid;
4950            info.reset();
4951            not.study(info);
4952
4953            info.minLength = minL + Math.min(minL2, info.minLength);
4954            info.maxLength = maxL + Math.max(maxL2, info.maxLength);
4955            info.maxValid = (maxV & maxV2 & info.maxValid);
4956            info.deterministic = false;
4957            return next.study(info);
4958        }
4959    }
4960
4961    /**
4962     * Zero width positive lookahead.
4963     */

4964    static final class Pos extends Node {
4965        Node cond;
4966        Pos(Node cond) {
4967            this.cond = cond;
4968        }
4969        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4970            int savedTo = matcher.to;
4971            boolean conditionMatched = false;
4972
4973            // Relax transparent region boundaries for lookahead
4974
if (matcher.transparentBounds)
4975                matcher.to = matcher.getTextLength();
4976            try {
4977                conditionMatched = cond.match(matcher, i, seq);
4978            } finally {
4979                // Reinstate region boundaries
4980
matcher.to = savedTo;
4981            }
4982            return conditionMatched && next.match(matcher, i, seq);
4983        }
4984    }
4985
4986    /**
4987     * Zero width negative lookahead.
4988     */

4989    static final class Neg extends Node {
4990        Node cond;
4991        Neg(Node cond) {
4992            this.cond = cond;
4993        }
4994        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
4995            int savedTo = matcher.to;
4996            boolean conditionMatched = false;
4997            
4998            // Relax transparent region boundaries for lookahead
4999
if (matcher.transparentBounds)
5000                matcher.to = matcher.getTextLength();
5001            try {
5002                if (i < matcher.to) {
5003                    conditionMatched = !cond.match(matcher, i, seq);
5004                } else {
5005                    // If a negative lookahead succeeds then more input
5006
// could cause it to fail!
5007
matcher.requireEnd = true;
5008                    conditionMatched = !cond.match(matcher, i, seq);
5009                }
5010            } finally {
5011                // Reinstate region boundaries
5012
matcher.to = savedTo;
5013            }
5014            return conditionMatched && next.match(matcher, i, seq);
5015        }
5016    }
5017
5018    /**
5019     * Zero width positive lookbehind.
5020     */

5021    static class Behind extends Node {
5022        Node cond;
5023        int rmax, rmin;
5024        Behind(Node cond, int rmax, int rmin) {
5025            this.cond = cond;
5026            this.rmax = rmax;
5027            this.rmin = rmin;
5028        }
5029        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5030            int savedFrom = matcher.from;
5031            boolean conditionMatched = false;
5032            int startIndex = (!matcher.transparentBounds) ?
5033                             matcher.from : 0;
5034            int from = Math.max(i - rmax, startIndex);
5035            for (int j = i - rmin; j >= from; j--) {
5036
5037                // Relax transparent region boundaries for lookbehind
5038
if (matcher.transparentBounds)
5039                    matcher.from = 0;
5040                try {
5041                    conditionMatched =
5042                        (cond.match(matcher, j, seq) && matcher.last == i);
5043                } finally { // Reinstate region boundaries
5044
matcher.from = savedFrom;
5045                }
5046                
5047                if (conditionMatched)
5048                    return next.match(matcher, i, seq);
5049            }
5050            return false;
5051        }
5052    }
5053
5054    /**
5055     * Zero width positive lookbehind, including supplementary
5056     * characters or unpaired surrogates.
5057     */

5058    static final class BehindS extends Behind {
5059        BehindS(Node cond, int rmax, int rmin) {
5060            super(cond, rmax, rmin);
5061        }
5062        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5063        int rmaxChars = countChars(seq, i, -rmax);
5064        int rminChars = countChars(seq, i, -rmin);
5065            int savedFrom = matcher.from;
5066            int startIndex = (!matcher.transparentBounds) ?
5067                             matcher.from : 0;
5068            boolean conditionMatched = false;
5069            int from = Math.max(i - rmaxChars, startIndex);
5070            for (int j = i - rminChars;
5071                 j >= from;
5072                 j -= j>from ? countChars(seq, j, -1) : 1) {
5073                // Relax transparent region boundaries for lookbehind
5074
if (matcher.transparentBounds)
5075                    matcher.from = 0;
5076                try {
5077                    conditionMatched =
5078                        (cond.match(matcher, j, seq) && matcher.last == i);
5079                } finally { // Reinstate region boundaries
5080
matcher.from = savedFrom;
5081                }
5082                if (conditionMatched)
5083                    return next.match(matcher, i, seq);
5084            }
5085            return false;
5086        }
5087    }
5088
5089    /**
5090     * Zero width negative lookbehind.
5091     */

5092    static class NotBehind extends Node {
5093        Node cond;
5094        int rmax, rmin;
5095        NotBehind(Node cond, int rmax, int rmin) {
5096            this.cond = cond;
5097            this.rmax = rmax;
5098            this.rmin = rmin;
5099        }
5100        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5101            int savedFrom = matcher.from;
5102            boolean conditionMatched = false;
5103            int startIndex = (!matcher.transparentBounds) ?
5104                             matcher.from : 0;
5105            int from = Math.max(i - rmax, startIndex);
5106            for (int j = i - rmin; j >= from; j--) {
5107
5108                // Relax transparent region boundaries for lookbehind
5109
if (matcher.transparentBounds)
5110                    matcher.from = 0;
5111                try {
5112                    conditionMatched =
5113                        (cond.match(matcher, j, seq) && matcher.last == i);
5114                } finally { // Reinstate region boundaries
5115
matcher.from = savedFrom;
5116                }
5117                if (conditionMatched)
5118                    return false;
5119            }
5120            return next.match(matcher, i, seq);
5121        }
5122    }
5123
5124    /**
5125     * Zero width negative lookbehind, including supplementary
5126     * characters or unpaired surrogates.
5127     */

5128    static final class NotBehindS extends NotBehind {
5129        NotBehindS(Node cond, int rmax, int rmin) {
5130            super(cond, rmax, rmin);
5131        }
5132        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5133        int rmaxChars = countChars(seq, i, -rmax);
5134        int rminChars = countChars(seq, i, -rmin);
5135            int savedFrom = matcher.from;
5136            boolean conditionMatched = false;
5137            int startIndex = (!matcher.transparentBounds) ?
5138                             matcher.from : 0;
5139            int from = Math.max(i - rmaxChars, startIndex);
5140            for (int j = i - rminChars;
5141                 j >= from;
5142                 j -= j>from ? countChars(seq, j, -1) : 1) {
5143                // Relax transparent region boundaries for lookbehind
5144
if (matcher.transparentBounds)
5145                    matcher.from = 0;
5146                try {
5147                    conditionMatched =
5148                        (cond.match(matcher, j, seq) && matcher.last == i);
5149                } finally { // Reinstate region boundaries
5150
matcher.from = savedFrom;
5151                }
5152                if (conditionMatched)
5153                    return false;
5154            }
5155            return next.match(matcher, i, seq);
5156        }
5157    }
5158
5159    /**
5160     * An object added to the tree when a character class has an additional
5161     * range added to it.
5162     */

5163    static class Add extends Node {
5164        Node lhs, rhs;
5165        Add(Node lhs, Node rhs) {
5166            this.lhs = lhs;
5167            this.rhs = rhs;
5168        }
5169        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5170            if (i < matcher.to) {
5171                return ((lhs.match(matcher, i, seq) ||
5172                         rhs.match(matcher, i, seq)) &&
5173                        next.match(matcher, matcher.last, seq));
5174            }
5175            matcher.hitEnd = true;
5176            return false;
5177        }
5178        boolean study(TreeInfo info) {
5179            boolean maxV = info.maxValid;
5180            boolean detm = info.deterministic;
5181
5182            int minL = info.minLength;
5183            int maxL = info.maxLength;
5184            lhs.study(info);
5185
5186            int minL2 = info.minLength;
5187            int maxL2 = info.maxLength;
5188
5189            info.minLength = minL;
5190            info.maxLength = maxL;
5191            rhs.study(info);
5192
5193            info.minLength = Math.min(minL2, info.minLength);
5194            info.maxLength = Math.max(maxL2, info.maxLength);
5195            info.maxValid = maxV;
5196            info.deterministic = detm;
5197
5198            return next.study(info);
5199        }
5200    }
5201
5202    /**
5203     * An object added to the tree when a character class has another
5204     * nested class in it.
5205     */

5206    static class Both extends Node {
5207        Node lhs, rhs;
5208        Both(Node lhs, Node rhs) {
5209            this.lhs = lhs;
5210            this.rhs = rhs;
5211        }
5212        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5213            if (i < matcher.to) {
5214                return ((lhs.match(matcher, i, seq) &&
5215                         rhs.match(matcher, i, seq)) &&
5216                        next.match(matcher, matcher.last, seq));
5217            }
5218            matcher.hitEnd = true;
5219            return false;
5220        }
5221        boolean study(TreeInfo info) {
5222            boolean maxV = info.maxValid;
5223            boolean detm = info.deterministic;
5224
5225            int minL = info.minLength;
5226            int maxL = info.maxLength;
5227            lhs.study(info);
5228
5229            int minL2 = info.minLength;
5230            int maxL2 = info.maxLength;
5231
5232            info.minLength = minL;
5233            info.maxLength = maxL;
5234            rhs.study(info);
5235
5236            info.minLength = Math.min(minL2, info.minLength);
5237            info.maxLength = Math.max(maxL2, info.maxLength);
5238            info.maxValid = maxV;
5239            info.deterministic = detm;
5240
5241            return next.study(info);
5242        }
5243    }
5244
5245    /**
5246     * An object added to the tree when a character class has a range
5247     * or single subtracted from it.
5248     */

5249    static final class Sub extends Add {
5250        Sub(Node lhs, Node rhs) {
5251            super(lhs, rhs);
5252        }
5253        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5254            if (i < matcher.to) {
5255                return !rhs.match(matcher, i, seq)
5256                    && lhs.match(matcher, i, seq)
5257                    && next.match(matcher, matcher.last, seq);
5258            }
5259            matcher.hitEnd = true;
5260            return false;
5261        }
5262        boolean study(TreeInfo info) {
5263            lhs.study(info);
5264            return next.study(info);
5265        }
5266    }
5267
5268    /**
5269     * Handles word boundaries. Includes a field to allow this one class to
5270     * deal with the different types of word boundaries we can match. The word
5271     * characters include underscores, letters, and digits. Non spacing marks
5272     * can are also part of a word if they have a base character, otherwise
5273     * they are ignored for purposes of finding word boundaries.
5274     */

5275    static final class Bound extends Node {
5276        static int LEFT = 0x1;
5277        static int RIGHT= 0x2;
5278        static int BOTH = 0x3;
5279        static int NONE = 0x4;
5280        int type;
5281        Bound(int n) {
5282            type = n;
5283        }
5284        int check(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5285            int ch;
5286            boolean left = false;
5287            int startIndex = matcher.from;
5288            int endIndex = matcher.to;
5289            if (matcher.transparentBounds) {
5290                startIndex = 0;
5291                endIndex = matcher.getTextLength();
5292            }
5293            if (i > startIndex) {
5294                ch = Character.codePointBefore(seq, i);
5295                left = (ch == '_' || Character.isLetterOrDigit(ch) ||
5296                    ((Character.getType(ch) == Character.NON_SPACING_MARK)
5297                     && hasBaseCharacter(matcher, i-1, seq)));
5298            }
5299            boolean right = false;
5300            if (i < endIndex) {
5301                ch = Character.codePointAt(seq, i);
5302                right = (ch == '_' || Character.isLetterOrDigit(ch) ||
5303                    ((Character.getType(ch) == Character.NON_SPACING_MARK)
5304                     && hasBaseCharacter(matcher, i, seq)));
5305            } else {
5306                // Tried to access char past the end
5307
matcher.hitEnd = true;
5308                // The addition of another char could wreck a boundary
5309
matcher.requireEnd = true;
5310            }
5311            return ((left ^ right) ? (right ? LEFT : RIGHT) : NONE);
5312        }
5313        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5314            return (check(matcher, i, seq) & type) > 0
5315                && next.match(matcher, i, seq);
5316        }
5317    }
5318
5319    /**
5320     * Non spacing marks only count as word characters in bounds calculations
5321     * if they have a base character.
5322     */

5323    private static boolean hasBaseCharacter(Matcher JavaDoc matcher, int i,
5324                                            CharSequence JavaDoc seq)
5325    {
5326        int start = (!matcher.transparentBounds) ?
5327            matcher.from : 0;
5328        for (int x=i; x >= start; x--) {
5329            int ch = Character.codePointAt(seq, x);
5330            if (Character.isLetterOrDigit(ch))
5331                return true;
5332            if (Character.getType(ch) == Character.NON_SPACING_MARK)
5333                continue;
5334            return false;
5335        }
5336        return false;
5337    }
5338
5339    /**
5340     * Attempts to match a slice in the input using the Boyer-Moore string
5341     * matching algorithm. The algorithm is based on the idea that the
5342     * pattern can be shifted farther ahead in the search text if it is
5343     * matched right to left.
5344     * <p>
5345     * The pattern is compared to the input one character at a time, from
5346     * the rightmost character in the pattern to the left. If the characters
5347     * all match the pattern has been found. If a character does not match,
5348     * the pattern is shifted right a distance that is the maximum of two
5349     * functions, the bad character shift and the good suffix shift. This
5350     * shift moves the attempted match position through the input more
5351     * quickly than a naive one position at a time check.
5352     * <p>
5353     * The bad character shift is based on the character from the text that
5354     * did not match. If the character does not appear in the pattern, the
5355     * pattern can be shifted completely beyond the bad character. If the
5356     * character does occur in the pattern, the pattern can be shifted to
5357     * line the pattern up with the next occurrence of that character.
5358     * <p>
5359     * The good suffix shift is based on the idea that some subset on the right
5360     * side of the pattern has matched. When a bad character is found, the
5361     * pattern can be shifted right by the pattern length if the subset does
5362     * not occur again in pattern, or by the amount of distance to the
5363     * next occurrence of the subset in the pattern.
5364     *
5365     * Boyer-Moore search methods adapted from code by Amy Yu.
5366     */

5367    static class BnM extends Node {
5368        int[] buffer;
5369        int[] lastOcc;
5370        int[] optoSft;
5371
5372        /**
5373         * Pre calculates arrays needed to generate the bad character
5374         * shift and the good suffix shift. Only the last seven bits
5375         * are used to see if chars match; This keeps the tables small
5376         * and covers the heavily used ASCII range, but occasionally
5377         * results in an aliased match for the bad character shift.
5378         */

5379        static Node optimize(Node node) {
5380            if (!(node instanceof Slice)) {
5381                return node;
5382            }
5383
5384            int[] src = ((Slice) node).buffer;
5385            int patternLength = src.length;
5386            // The BM algorithm requires a bit of overhead;
5387
// If the pattern is short don't use it, since
5388
// a shift larger than the pattern length cannot
5389
// be used anyway.
5390
if (patternLength < 4) {
5391                return node;
5392            }
5393            int i, j, k;
5394            int[] lastOcc = new int[128];
5395            int[] optoSft = new int[patternLength];
5396            // Precalculate part of the bad character shift
5397
// It is a table for where in the pattern each
5398
// lower 7-bit value occurs
5399
for (i = 0; i < patternLength; i++) {
5400                lastOcc[src[i]&0x7F] = i + 1;
5401            }
5402            // Precalculate the good suffix shift
5403
// i is the shift amount being considered
5404
NEXT: for (i = patternLength; i > 0; i--) {
5405                // j is the beginning index of suffix being considered
5406
for (j = patternLength - 1; j >= i; j--) {
5407                    // Testing for good suffix
5408
if (src[j] == src[j-i]) {
5409                        // src[j..len] is a good suffix
5410
optoSft[j-1] = i;
5411                    } else {
5412                        // No match. The array has already been
5413
// filled up with correct values before.
5414
continue NEXT;
5415                    }
5416                }
5417                // This fills up the remaining of optoSft
5418
// any suffix can not have larger shift amount
5419
// then its sub-suffix. Why???
5420
while (j > 0) {
5421                    optoSft[--j] = i;
5422                }
5423            }
5424            // Set the guard value because of unicode compression
5425
optoSft[patternLength-1] = 1;
5426        if (node instanceof SliceS)
5427        return new BnMS(src, lastOcc, optoSft, node.next);
5428            return new BnM(src, lastOcc, optoSft, node.next);
5429        }
5430        BnM(int[] src, int[] lastOcc, int[] optoSft, Node next) {
5431            this.buffer = src;
5432            this.lastOcc = lastOcc;
5433            this.optoSft = optoSft;
5434            this.next = next;
5435        }
5436        boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5437            int[] src = buffer;
5438            int patternLength = src.length;
5439            int last = matcher.to - patternLength;
5440
5441            // Loop over all possible match positions in text
5442
NEXT: while (i <= last) {
5443                // Loop over pattern from right to left
5444
for (int j = patternLength - 1; j >= 0; j--) {
5445                    int ch = seq.charAt(i+j);
5446                    if (ch != src[j]) {
5447                        // Shift search to the right by the maximum of the
5448
// bad character shift and the good suffix shift
5449
i += Math.max(j + 1 - lastOcc[ch&0x7F], optoSft[j]);
5450                        continue NEXT;
5451                    }
5452                }
5453                // Entire pattern matched starting at i
5454
matcher.first = i;
5455                boolean ret = next.match(matcher, i + patternLength, seq);
5456                if (ret) {
5457                    matcher.first = i;
5458                    matcher.groups[0] = matcher.first;
5459                    matcher.groups[1] = matcher.last;
5460                    return true;
5461                }
5462                i++;
5463            }
5464            // BnM is only used as the leading node in the unanchored case,
5465
// and it replaced its Start() which always searches to the end
5466
// if it doesn't find what it's looking for, so hitEnd is true.
5467
matcher.hitEnd = true;
5468            return false;
5469        }
5470        boolean study(TreeInfo info) {
5471            info.minLength += buffer.length;
5472            info.maxValid = false;
5473            return next.study(info);
5474        }
5475    }
5476
5477    /**
5478     * Supplementary support version of BnM(). Unpaired surrogates are
5479     * also handled by this class.
5480     */

5481    static final class BnMS extends BnM {
5482    int lengthInChars;
5483
5484    BnMS(int[] src, int[] lastOcc, int[] optoSft, Node next) {
5485        super(src, lastOcc, optoSft, next);
5486        for (int x = 0; x < buffer.length; x++) {
5487        lengthInChars += Character.charCount(buffer[x]);
5488        }
5489    }
5490    boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5491            int[] src = buffer;
5492            int patternLength = src.length;
5493        int last = matcher.to - lengthInChars;
5494
5495            // Loop over all possible match positions in text
5496
NEXT: while (i <= last) {
5497                // Loop over pattern from right to left
5498
int ch;
5499                for (int j = countChars(seq, i, patternLength), x = patternLength - 1;
5500             j > 0; j -= Character.charCount(ch), x--) {
5501            ch = Character.codePointBefore(seq, i+j);
5502                    if (ch != src[x]) {
5503                        // Shift search to the right by the maximum of the
5504
// bad character shift and the good suffix shift
5505
int n = Math.max(x + 1 - lastOcc[ch&0x7F], optoSft[x]);
5506            i += countChars(seq, i, n);
5507                        continue NEXT;
5508                    }
5509                }
5510                // Entire pattern matched starting at i
5511
matcher.first = i;
5512                boolean ret = next.match(matcher, i + lengthInChars, seq);
5513                if (ret) {
5514                    matcher.first = i;
5515                    matcher.groups[0] = matcher.first;
5516                    matcher.groups[1] = matcher.last;
5517                    return true;
5518                }
5519        i += countChars(seq, i, 1);
5520            }
5521            matcher.hitEnd = true;
5522            return false;
5523        }
5524    }
5525
5526     /**
5527      * Node class for matching characters in a Unicode block
5528      */

5529     static final class UBlock extends Node {
5530         Character.UnicodeBlock JavaDoc block;
5531         boolean complementMe = false;
5532
5533         UBlock() {
5534         }
5535
5536         UBlock(Character.UnicodeBlock JavaDoc block, boolean not) {
5537             this.block = block;
5538             this.complementMe = not;
5539         }
5540
5541         Node dup(boolean not) {
5542             if (not)
5543                 return new UBlock(block, !complementMe);
5544             else
5545                 return new UBlock(block, complementMe);
5546         }
5547
5548         boolean match(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5549             if (complementMe)
5550                 return notMatch(matcher, i, seq);
5551             if (i < matcher.to) {
5552                 int ch = Character.codePointAt(seq, i);
5553                 return (block == Character.UnicodeBlock.of(ch) &&
5554                         (next.match(matcher, i+Character.charCount(ch), seq)));
5555             }
5556             matcher.hitEnd = true;
5557             return false;
5558         }
5559
5560         boolean notMatch(Matcher JavaDoc matcher, int i, CharSequence JavaDoc seq) {
5561             if (i < matcher.to) {
5562                 int ch = Character.codePointAt(seq, i);
5563                 return (block != Character.UnicodeBlock.of(ch) &&
5564                         (next.match(matcher, i+Character.charCount(ch), seq)));
5565             }
5566             matcher.hitEnd = true;
5567             return false;
5568         }
5569
5570         boolean study(TreeInfo info) {
5571             info.minLength++;
5572             info.maxLength++;
5573             return next.study(info);
5574         }
5575
5576     }
5577 
5578 
5579
5580///////////////////////////////////////////////////////////////////////////////
5581
///////////////////////////////////////////////////////////////////////////////
5582

5583    /**
5584     * This must be the very first initializer.
5585     */

5586    static Node accept = new Node();
5587
5588    static Node lastAccept = new LastNode();
5589
5590    static class categoryNames {
5591
5592        static HashMap JavaDoc cMap = new HashMap JavaDoc();
5593
5594        static {
5595            cMap.put("Cn", new Category(1<<0)); // UNASSIGNED
5596
cMap.put("Lu", new Category(1<<1)); // UPPERCASE_LETTER
5597
cMap.put("Ll", new Category(1<<2)); // LOWERCASE_LETTER
5598
cMap.put("Lt", new Category(1<<3)); // TITLECASE_LETTER
5599
cMap.put("Lm", new Category(1<<4)); // MODIFIER_LETTER
5600
cMap.put("Lo", new Category(1<<5)); // OTHER_LETTER
5601
cMap.put("Mn", new Category(1<<6)); // NON_SPACING_MARK
5602
cMap.put("Me", new Category(1<<7)); // ENCLOSING_MARK
5603
cMap.put("Mc", new Category(1<<8)); // COMBINING_SPACING_MARK
5604
cMap.put("Nd", new Category(1<<9)); // DECIMAL_DIGIT_NUMBER
5605
cMap.put("Nl", new Category(1<<10)); // LETTER_NUMBER
5606
cMap.put("No", new Category(1<<11)); // OTHER_NUMBER
5607
cMap.put("Zs", new Category(1<<12)); // SPACE_SEPARATOR
5608
cMap.put("Zl", new Category(1<<13)); // LINE_SEPARATOR
5609
cMap.put("Zp", new Category(1<<14)); // PARAGRAPH_SEPARATOR
5610
cMap.put("Cc", new Category(1<<15)); // CNTRL
5611
cMap.put("Cf", new Category(1<<16)); // FORMAT
5612
cMap.put("Co", new Category(1<<18)); // PRIVATE USE
5613
cMap.put("Cs", new Category(1<<19)); // SURROGATE
5614
cMap.put("Pd", new Category(1<<20)); // DASH_PUNCTUATION
5615
cMap.put("Ps", new Category(1<<21)); // START_PUNCTUATION
5616
cMap.put("Pe", new Category(1<<22)); // END_PUNCTUATION
5617
cMap.put("Pc", new Category(1<<23)); // CONNECTOR_PUNCTUATION
5618
cMap.put("Po", new Category(1<<24)); // OTHER_PUNCTUATION
5619
cMap.put("Sm", new Category(1<<25)); // MATH_SYMBOL
5620
cMap.put("Sc", new Category(1<<26)); // CURRENCY_SYMBOL
5621
cMap.put("Sk", new Category(1<<27)); // MODIFIER_SYMBOL
5622
cMap.put("So", new Category(1<<28)); // OTHER_SYMBOL
5623
cMap.put("L", new Category(0x0000003E)); // LETTER
5624
cMap.put("M", new Category(0x000001C0)); // MARK
5625
cMap.put("N", new Category(0x00000E00)); // NUMBER
5626
cMap.put("Z", new Category(0x00007000)); // SEPARATOR
5627
cMap.put("C", new Category(0x000D8000)); // CONTROL
5628
cMap.put("P", new Category(0x01F00000)); // PUNCTUATION
5629
cMap.put("S", new Category(0x1E000000)); // SYMBOL
5630
cMap.put("LD", new Category(0x0000023E)); // LETTER_OR_DIGIT
5631
cMap.put("L1", new Range(0x000000FF)); // Latin-1
5632
cMap.put("all", new All()); // ALL
5633
cMap.put("ASCII", new Range(0x0000007F)); // ASCII
5634
cMap.put("Alnum", new Ctype(ASCII.ALNUM)); // Alphanumeric characters
5635
cMap.put("Alpha", new Ctype(ASCII.ALPHA)); // Alphabetic characters
5636
cMap.put("Blank", new Ctype(ASCII.BLANK)); // Space and tab characters
5637
cMap.put("Cntrl", new Ctype(ASCII.CNTRL)); // Control characters
5638
cMap.put("Digit", new Range(('0'<<16)|'9')); // Numeric characters
5639
cMap.put("Graph", new Ctype(ASCII.GRAPH)); // printable and visible
5640
cMap.put("Lower", new Range(('a'<<16)|'z')); // Lower-case alphabetic
5641
cMap.put("Print", new Range(0x0020007E)); // Printable characters
5642
cMap.put("Punct", new Ctype(ASCII.PUNCT)); // Punctuation characters
5643
cMap.put("Space", new Ctype(ASCII.SPACE)); // Space characters
5644
cMap.put("Upper", new Range(('A'<<16)|'Z')); // Upper-case alphabetic
5645
cMap.put("XDigit", new Ctype(ASCII.XDIGIT)); // hexadecimal digits
5646
cMap.put("javaLowerCase", new JavaLowerCase());
5647            cMap.put("javaUpperCase", new JavaUpperCase());
5648            cMap.put("javaTitleCase", new JavaTitleCase());
5649            cMap.put("javaDigit", new JavaDigit());
5650            cMap.put("javaDefined", new JavaDefined());
5651            cMap.put("javaLetter", new JavaLetter());
5652            cMap.put("javaLetterOrDigit", new JavaLetterOrDigit());
5653            cMap.put("javaJavaIdentifierStart", new JavaJavaIdentifierStart());
5654            cMap.put("javaJavaIdentifierPart", new JavaJavaIdentifierPart());
5655            cMap.put("javaUnicodeIdentifierStart", new JavaUnicodeIdentifierStart());
5656            cMap.put("javaUnicodeIdentifierPart", new JavaUnicodeIdentifierPart());
5657            cMap.put("javaIdentifierIgnorable", new JavaIdentifierIgnorable());
5658            cMap.put("javaSpaceChar", new JavaSpaceChar());
5659            cMap.put("javaWhitespace", new JavaWhitespace());
5660            cMap.put("javaISOControl", new JavaISOControl());
5661            cMap.put("javaMirrored", new JavaMirrored());
5662        }
5663    }
5664}
5665
Popular Tags