KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > org > apache > xerces > internal > impl > xpath > regex > RegularExpression


1 /*
2  * The Apache Software License, Version 1.1
3  *
4  *
5  * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
6  * reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Apache Software Foundation (http://www.apache.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Xerces" and "Apache Software Foundation" must
28  * not be used to endorse or promote products derived from this
29  * software without prior written permission. For written
30  * permission, please contact apache@apache.org.
31  *
32  * 5. Products derived from this software may not be called "Apache",
33  * nor may "Apache" appear in their name, without prior written
34  * permission of the Apache Software Foundation.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47  * SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This software consists of voluntary contributions made by many
51  * individuals on behalf of the Apache Software Foundation and was
52  * originally based on software copyright (c) 1999, International
53  * Business Machines, Inc., http://www.apache.org. For more
54  * information on the Apache Software Foundation, please see
55  * <http://www.apache.org/>.
56  */

57
58 package com.sun.org.apache.xerces.internal.impl.xpath.regex;
59
60 import java.text.CharacterIterator JavaDoc;
61
62 /**
63  * A regular expression matching engine using Non-deterministic Finite Automaton (NFA).
64  * This engine does not conform to the POSIX regular expression.
65  *
66  * <hr width="50%">
67  * <h3>How to use</h3>
68  *
69  * <dl>
70  * <dt>A. Standard way
71  * <dd>
72  * <pre>
73  * RegularExpression re = new RegularExpression(<var>regex</var>);
74  * if (re.matches(text)) { ... }
75  * </pre>
76  *
77  * <dt>B. Capturing groups
78  * <dd>
79  * <pre>
80  * RegularExpression re = new RegularExpression(<var>regex</var>);
81  * Match match = new Match();
82  * if (re.matches(text, match)) {
83  * ... // You can refer captured texts with methods of the <code>Match</code> class.
84  * }
85  * </pre>
86  *
87  * </dl>
88  *
89  * <h4>Case-insensitive matching</h4>
90  * <pre>
91  * RegularExpression re = new RegularExpression(<var>regex</var>, "i");
92  * if (re.matches(text) >= 0) { ...}
93  * </pre>
94  *
95  * <h4>Options</h4>
96  * <p>You can specify options to <a HREF="#RegularExpression(java.lang.String, java.lang.String)"><code>RegularExpression(</code><var>regex</var><code>, </code><var>options</var><code>)</code></a>
97  * or <a HREF="#setPattern(java.lang.String, java.lang.String)"><code>setPattern(</code><var>regex</var><code>, </code><var>options</var><code>)</code></a>.
98  * This <var>options</var> parameter consists of the following characters.
99  * </p>
100  * <dl>
101  * <dt><a name="I_OPTION"><code>"i"</code></a>
102  * <dd>This option indicates case-insensitive matching.
103  * <dt><a name="M_OPTION"><code>"m"</code></a>
104  * <dd class="REGEX"><kbd>^</kbd> and <kbd>$</kbd> consider the EOL characters within the text.
105  * <dt><a name="S_OPTION"><code>"s"</code></a>
106  * <dd class="REGEX"><kbd>.</kbd> matches any one character.
107  * <dt><a name="U_OPTION"><code>"u"</code></a>
108  * <dd class="REGEX">Redefines <Kbd>\d \D \w \W \s \S \b \B \&lt; \></kbd> as becoming to Unicode.
109  * <dt><a name="W_OPTION"><code>"w"</code></a>
110  * <dd class="REGEX">By this option, <kbd>\b \B \&lt; \></kbd> are processed with the method of
111  * 'Unicode Regular Expression Guidelines' Revision 4.
112  * When "w" and "u" are specified at the same time,
113  * <kbd>\b \B \&lt; \></kbd> are processed for the "w" option.
114  * <dt><a name="COMMA_OPTION"><code>","</code></a>
115  * <dd>The parser treats a comma in a character class as a range separator.
116  * <kbd class="REGEX">[a,b]</kbd> matches <kbd>a</kbd> or <kbd>,</kbd> or <kbd>b</kbd> without this option.
117  * <kbd class="REGEX">[a,b]</kbd> matches <kbd>a</kbd> or <kbd>b</kbd> with this option.
118  *
119  * <dt><a name="X_OPTION"><code>"X"</code></a>
120  * <dd class="REGEX">
121  * By this option, the engine confoms to <a HREF="http://www.w3.org/TR/2000/WD-xmlschema-2-20000407/#regexs">XML Schema: Regular Expression</a>.
122  * The <code>match()</code> method does not do subsring matching
123  * but entire string matching.
124  *
125  * </dl>
126  *
127  * <hr width="50%">
128  * <h3>Syntax</h3>
129  * <table border="1" bgcolor="#ddeeff">
130  * <tr>
131  * <td>
132  * <h4>Differences from the Perl 5 regular expression</h4>
133  * <ul>
134  * <li>There is 6-digit hexadecimal character representation (<kbd>\v</kbd><var>HHHHHH</var>.)
135  * <li>Supports subtraction, union, and intersection operations for character classes.
136  * <li>Not supported: <kbd>\</kbd><var>ooo</var> (Octal character representations),
137  * <Kbd>\G</kbd>, <kbd>\C</kbd>, <kbd>\l</kbd><var>c</var>,
138  * <kbd>\ u</kbd><var>c</var>, <kbd>\L</kbd>, <kbd>\U</kbd>,
139  * <kbd>\E</kbd>, <kbd>\Q</kbd>, <kbd>\N{</kbd><var>name</var><kbd>}</kbd>,
140  * <Kbd>(?{<kbd><var>code</var><kbd>})</kbd>, <Kbd>(??{<kbd><var>code</var><kbd>})</kbd>
141  * </ul>
142  * </td>
143  * </tr>
144  * </table>
145  *
146  * <P>Meta characters are `<KBD>. * + ? { [ ( ) | \ ^ $</KBD>'.</P>
147  * <ul>
148  * <li>Character
149  * <dl>
150  * <dt class="REGEX"><kbd>.</kbd> (A period)
151  * <dd>Matches any one character except the following characters.
152  * <dd>LINE FEED (U+000A), CARRIAGE RETURN (U+000D),
153  * PARAGRAPH SEPARATOR (U+2029), LINE SEPARATOR (U+2028)
154  * <dd>This expression matches one code point in Unicode. It can match a pair of surrogates.
155  * <dd>When <a HREF="#S_OPTION">the "s" option</a> is specified,
156  * it matches any character including the above four characters.
157  *
158  * <dt class="REGEX"><Kbd>\e \f \n \r \t</kbd>
159  * <dd>Matches ESCAPE (U+001B), FORM FEED (U+000C), LINE FEED (U+000A),
160  * CARRIAGE RETURN (U+000D), HORIZONTAL TABULATION (U+0009)
161  *
162  * <dt class="REGEX"><kbd>\c</kbd><var>C</var>
163  * <dd>Matches a control character.
164  * The <var>C</var> must be one of '<kbd>@</kbd>', '<kbd>A</kbd>'-'<kbd>Z</kbd>',
165  * '<kbd>[</kbd>', '<kbd>\</kbd>', '<kbd>]</kbd>', '<kbd>^</kbd>', '<kbd>_</kbd>'.
166  * It matches a control character of which the character code is less than
167  * the character code of the <var>C</var> by 0x0040.
168  * <dd class="REGEX">For example, a <kbd>\cJ</kbd> matches a LINE FEED (U+000A),
169  * and a <kbd>\c[</kbd> matches an ESCAPE (U+001B).
170  *
171  * <dt class="REGEX">a non-meta character
172  * <dd>Matches the character.
173  *
174  * <dt class="REGEX"><KBD>\</KBD> + a meta character
175  * <dd>Matches the meta character.
176  *
177  * <dt class="REGEX"><kbd>\x</kbd><var>HH</var> <kbd>\x{</kbd><var>HHHH</var><kbd>}</kbd>
178  * <dd>Matches a character of which code point is <var>HH</var> (Hexadecimal) in Unicode.
179  * You can write just 2 digits for <kbd>\x</kbd><var>HH</var>, and
180  * variable length digits for <kbd>\x{</kbd><var>HHHH</var><kbd>}</kbd>.
181  *
182  * <!--
183  * <dt class="REGEX"><kbd>\ u</kbd><var>HHHH</var>
184  * <dd>Matches a character of which code point is <var>HHHH</var> (Hexadecimal) in Unicode.
185  * -->
186  *
187  * <dt class="REGEX"><kbd>\v</kbd><var>HHHHHH</var>
188  * <dd>Matches a character of which code point is <var>HHHHHH</var> (Hexadecimal) in Unicode.
189  *
190  * <dt class="REGEX"><kbd>\g</kbd>
191  * <dd>Matches a grapheme.
192  * <dd class="REGEX">It is equivalent to <kbd>(?[\p{ASSIGNED}]-[\p{M}\p{C}])?(?:\p{M}|[\x{094D}\x{09CD}\x{0A4D}\x{0ACD}\x{0B3D}\x{0BCD}\x{0C4D}\x{0CCD}\x{0D4D}\x{0E3A}\x{0F84}]\p{L}|[\x{1160}-\x{11A7}]|[\x{11A8}-\x{11FF}]|[\x{FF9E}\x{FF9F}])*</kbd>
193  *
194  * <dt class="REGEX"><kbd>\X</kbd>
195  * <dd class="REGEX">Matches a combining character sequence.
196  * It is equivalent to <kbd>(?:\PM\pM*)</kbd>
197  * </dl>
198  * </li>
199  *
200  * <li>Character class
201  * <dl>
202 + * <dt class="REGEX"><kbd>[</kbd><var>R<sub>1</sub></var><var>R<sub>2</sub></var><var>...</var><var>R<sub>n</sub></var><kbd>]</kbd> (without <a HREF="#COMMA_OPTION">"," option</a>)
203 + * <dt class="REGEX"><kbd>[</kbd><var>R<sub>1</sub></var><kbd>,</kbd><var>R<sub>2</sub></var><kbd>,</kbd><var>...</var><kbd>,</kbd><var>R<sub>n</sub></var><kbd>]</kbd> (with <a HREF="#COMMA_OPTION">"," option</a>)
204  * <dd>Positive character class. It matches a character in ranges.
205  * <dd><var>R<sub>n</sub></var>:
206  * <ul>
207  * <li class="REGEX">A character (including <Kbd>\e \f \n \r \t</kbd> <kbd>\x</kbd><var>HH</var> <kbd>\x{</kbd><var>HHHH</var><kbd>}</kbd> <!--kbd>\ u</kbd><var>HHHH</var--> <kbd>\v</kbd><var>HHHHHH</var>)
208  * <p>This range matches the character.
209  * <li class="REGEX"><var>C<sub>1</sub></var><kbd>-</kbd><var>C<sub>2</sub></var>
210  * <p>This range matches a character which has a code point that is >= <var>C<sub>1</sub></var>'s code point and &lt;= <var>C<sub>2</sub></var>'s code point.
211 + * <li class="REGEX">A POSIX character class: <Kbd>[:alpha:] [:alnum:] [:ascii:] [:cntrl:] [:digit:] [:graph:] [:lower:] [:print:] [:punct:] [:space:] [:upper:] [:xdigit:]</kbd>,
212 + * and negative POSIX character classes in Perl like <kbd>[:^alpha:]</kbd>
213  * <p>...
214  * <li class="REGEX"><kbd>\d \D \s \S \w \W \p{</kbd><var>name</var><kbd>} \P{</kbd><var>name</var><kbd>}</kbd>
215  * <p>These expressions specifies the same ranges as the following expressions.
216  * </ul>
217  * <p class="REGEX">Enumerated ranges are merged (union operation).
218  * <kbd>[a-ec-z]</kbd> is equivalent to <kbd>[a-z]</kbd>
219  *
220  * <dt class="REGEX"><kbd>[^</kbd><var>R<sub>1</sub></var><var>R<sub>2</sub></var><var>...</var><var>R<sub>n</sub></var><kbd>]</kbd> (without a <a HREF="#COMMA_OPTION">"," option</a>)
221  * <dt class="REGEX"><kbd>[^</kbd><var>R<sub>1</sub></var><kbd>,</kbd><var>R<sub>2</sub></var><kbd>,</kbd><var>...</var><kbd>,</kbd><var>R<sub>n</sub></var><kbd>]</kbd> (with a <a HREF="#COMMA_OPTION">"," option</a>)
222  * <dd>Negative character class. It matches a character not in ranges.
223  *
224  * <dt class="REGEX"><kbd>(?[</kbd><var>ranges</var><kbd>]</kbd><var>op</var><kbd>[</kbd><var>ranges</var><kbd>]</kbd><var>op</var><kbd>[</kbd><var>ranges</var><kbd>]</kbd> ... <Kbd>)</kbd>
225  * (<var>op</var> is <kbd>-</kbd> or <kbd>+</kbd> or <kbd>&</kbd>.)
226  * <dd>Subtraction or union or intersection for character classes.
227  * <dd class="REGEX">For exmaple, <kbd>(?[A-Z]-[CF])</kbd> is equivalent to <kbd>[A-BD-EG-Z]</kbd>, and <kbd>(?[0x00-0x7f]-[K]&[\p{Lu}])</kbd> is equivalent to <kbd>[A-JL-Z]</kbd>.
228  * <dd>The result of this operations is a <u>positive character class</u>
229  * even if an expression includes any negative character classes.
230  * You have to take care on this in case-insensitive matching.
231  * For instance, <kbd>(?[^b])</kbd> is equivalent to <kbd>[\x00-ac-\x{10ffff}]</kbd>,
232  * which is equivalent to <kbd>[^b]</kbd> in case-sensitive matching.
233  * But, in case-insensitive matching, <kbd>(?[^b])</kbd> matches any character because
234  * it includes '<kbd>B</kbd>' and '<kbd>B</kbd>' matches '<kbd>b</kbd>'
235  * though <kbd>[^b]</kbd> is processed as <kbd>[^Bb]</kbd>.
236  *
237  * <dt class="REGEX"><kbd>[</kbd><var>R<sub>1</sub>R<sub>2</sub>...</var><kbd>-[</kbd><var>R<sub>n</sub>R<sub>n+1</sub>...</var><kbd>]]</kbd> (with an <a HREF="#X_OPTION">"X" option</a>)</dt>
238  * <dd>Character class subtraction for the XML Schema.
239  * You can use this syntax when you specify an <a HREF="#X_OPTION">"X" option</a>.
240  *
241  * <dt class="REGEX"><kbd>\d</kbd>
242  * <dd class="REGEX">Equivalent to <kbd>[0-9]</kbd>.
243  * <dd>When <a HREF="#U_OPTION">a "u" option</a> is set, it is equivalent to
244  * <span class="REGEX"><kbd>\p{Nd}</kbd></span>.
245  *
246  * <dt class="REGEX"><kbd>\D</kbd>
247  * <dd class="REGEX">Equivalent to <kbd>[^0-9]</kbd>
248  * <dd>When <a HREF="#U_OPTION">a "u" option</a> is set, it is equivalent to
249  * <span class="REGEX"><kbd>\P{Nd}</kbd></span>.
250  *
251  * <dt class="REGEX"><kbd>\s</kbd>
252  * <dd class="REGEX">Equivalent to <kbd>[ \f\n\r\t]</kbd>
253  * <dd>When <a HREF="#U_OPTION">a "u" option</a> is set, it is equivalent to
254  * <span class="REGEX"><kbd>[ \f\n\r\t\p{Z}]</kbd></span>.
255  *
256  * <dt class="REGEX"><kbd>\S</kbd>
257  * <dd class="REGEX">Equivalent to <kbd>[^ \f\n\r\t]</kbd>
258  * <dd>When <a HREF="#U_OPTION">a "u" option</a> is set, it is equivalent to
259  * <span class="REGEX"><kbd>[^ \f\n\r\t\p{Z}]</kbd></span>.
260  *
261  * <dt class="REGEX"><kbd>\w</kbd>
262  * <dd class="REGEX">Equivalent to <kbd>[a-zA-Z0-9_]</kbd>
263  * <dd>When <a HREF="#U_OPTION">a "u" option</a> is set, it is equivalent to
264  * <span class="REGEX"><kbd>[\p{Lu}\p{Ll}\p{Lo}\p{Nd}_]</kbd></span>.
265  *
266  * <dt class="REGEX"><kbd>\W</kbd>
267  * <dd class="REGEX">Equivalent to <kbd>[^a-zA-Z0-9_]</kbd>
268  * <dd>When <a HREF="#U_OPTION">a "u" option</a> is set, it is equivalent to
269  * <span class="REGEX"><kbd>[^\p{Lu}\p{Ll}\p{Lo}\p{Nd}_]</kbd></span>.
270  *
271  * <dt class="REGEX"><kbd>\p{</kbd><var>name</var><kbd>}</kbd>
272  * <dd>Matches one character in the specified General Category (the second field in <a HREF="ftp://ftp.unicode.org/Public/UNIDATA/UnicodeData.txt"><kbd>UnicodeData.txt</kbd></a>) or the specified <a HREF="ftp://ftp.unicode.org/Public/UNIDATA/Blocks.txt">Block</a>.
273  * The following names are available:
274  * <dl>
275  * <dt>Unicode General Categories:
276  * <dd><kbd>
277  * L, M, N, Z, C, P, S, Lu, Ll, Lt, Lm, Lo, Mn, Me, Mc, Nd, Nl, No, Zs, Zl, Zp,
278  * Cc, Cf, Cn, Co, Cs, Pd, Ps, Pe, Pc, Po, Sm, Sc, Sk, So,
279  * </kbd>
280  * <dd>(Currently the Cn category includes U+10000-U+10FFFF characters)
281  * <dt>Unicode Blocks:
282  * <dd><kbd>
283  * Basic Latin, Latin-1 Supplement, Latin Extended-A, Latin Extended-B,
284  * IPA Extensions, Spacing Modifier Letters, Combining Diacritical Marks, Greek,
285  * Cyrillic, Armenian, Hebrew, Arabic, Devanagari, Bengali, Gurmukhi, Gujarati,
286  * Oriya, Tamil, Telugu, Kannada, Malayalam, Thai, Lao, Tibetan, Georgian,
287  * Hangul Jamo, Latin Extended Additional, Greek Extended, General Punctuation,
288  * Superscripts and Subscripts, Currency Symbols, Combining Marks for Symbols,
289  * Letterlike Symbols, Number Forms, Arrows, Mathematical Operators,
290  * Miscellaneous Technical, Control Pictures, Optical Character Recognition,
291  * Enclosed Alphanumerics, Box Drawing, Block Elements, Geometric Shapes,
292  * Miscellaneous Symbols, Dingbats, CJK Symbols and Punctuation, Hiragana,
293  * Katakana, Bopomofo, Hangul Compatibility Jamo, Kanbun,
294  * Enclosed CJK Letters and Months, CJK Compatibility, CJK Unified Ideographs,
295  * Hangul Syllables, High Surrogates, High Private Use Surrogates, Low Surrogates,
296  * Private Use, CJK Compatibility Ideographs, Alphabetic Presentation Forms,
297  * Arabic Presentation Forms-A, Combining Half Marks, CJK Compatibility Forms,
298  * Small Form Variants, Arabic Presentation Forms-B, Specials,
299  * Halfwidth and Fullwidth Forms
300  * </kbd>
301  * <dt>Others:
302  * <dd><kbd>ALL</kbd> (Equivalent to <kbd>[\u0000-\v10FFFF]</kbd>)
303  * <dd><kbd>ASSGINED</kbd> (<kbd>\p{ASSIGNED}</kbd> is equivalent to <kbd>\P{Cn}</kbd>)
304  * <dd><kbd>UNASSGINED</kbd>
305  * (<kbd>\p{UNASSIGNED}</kbd> is equivalent to <kbd>\p{Cn}</kbd>)
306  * </dl>
307  *
308  * <dt class="REGEX"><kbd>\P{</kbd><var>name</var><kbd>}</kbd>
309  * <dd>Matches one character not in the specified General Category or the specified Block.
310  * </dl>
311  * </li>
312  *
313  * <li>Selection and Quantifier
314  * <dl>
315  * <dt class="REGEX"><VAR>X</VAR><kbd>|</kbd><VAR>Y</VAR>
316  * <dd>...
317  *
318  * <dt class="REGEX"><VAR>X</VAR><kbd>*</KBD>
319  * <dd>Matches 0 or more <var>X</var>.
320  *
321  * <dt class="REGEX"><VAR>X</VAR><kbd>+</KBD>
322  * <dd>Matches 1 or more <var>X</var>.
323  *
324  * <dt class="REGEX"><VAR>X</VAR><kbd>?</KBD>
325  * <dd>Matches 0 or 1 <var>X</var>.
326  *
327  * <dt class="REGEX"><var>X</var><kbd>{</kbd><var>number</var><kbd>}</kbd>
328  * <dd>Matches <var>number</var> times.
329  *
330  * <dt class="REGEX"><var>X</var><kbd>{</kbd><var>min</var><kbd>,}</kbd>
331  * <dd>...
332  *
333  * <dt class="REGEX"><var>X</var><kbd>{</kbd><var>min</var><kbd>,</kbd><var>max</var><kbd>}</kbd>
334  * <dd>...
335  *
336  * <dt class="REGEX"><VAR>X</VAR><kbd>*?</kbd>
337  * <dt class="REGEX"><VAR>X</VAR><kbd>+?</kbd>
338  * <dt class="REGEX"><VAR>X</VAR><kbd>??</kbd>
339  * <dt class="REGEX"><var>X</var><kbd>{</kbd><var>min</var><kbd>,}?</kbd>
340  * <dt class="REGEX"><var>X</var><kbd>{</kbd><var>min</var><kbd>,</kbd><var>max</var><kbd>}?</kbd>
341  * <dd>Non-greedy matching.
342  * </dl>
343  * </li>
344  *
345  * <li>Grouping, Capturing, and Back-reference
346  * <dl>
347  * <dt class="REGEX"><KBD>(?:</kbd><VAR>X</VAR><kbd>)</KBD>
348  * <dd>Grouping. "<KBD>foo+</KBD>" matches "<KBD>foo</KBD>" or "<KBD>foooo</KBD>".
349  * If you want it matches "<KBD>foofoo</KBD>" or "<KBD>foofoofoo</KBD>",
350  * you have to write "<KBD>(?:foo)+</KBD>".
351  *
352  * <dt class="REGEX"><KBD>(</kbd><VAR>X</VAR><kbd>)</KBD>
353  * <dd>Grouping with capturing.
354  * It make a group and applications can know
355  * where in target text a group matched with methods of a <code>Match</code> instance
356  * after <code><a HREF="#matches(java.lang.String, com.sun.org.apache.xerces.internal.utils.regex.Match)">matches(String,Match)</a></code>.
357  * The 0th group means whole of this regular expression.
358  * The <VAR>N</VAR>th gorup is the inside of the <VAR>N</VAR>th left parenthesis.
359  *
360  * <p>For instance, a regular expression is
361  * "<FONT color=blue><KBD> *([^&lt;:]*) +&lt;([^&gt;]*)&gt; *</KBD></FONT>"
362  * and target text is
363  * "<FONT color=red><KBD>From: TAMURA Kent &lt;kent@trl.ibm.co.jp&gt;</KBD></FONT>":
364  * <ul>
365  * <li><code>Match.getCapturedText(0)</code>:
366  * "<FONT color=red><KBD> TAMURA Kent &lt;kent@trl.ibm.co.jp&gt;</KBD></FONT>"
367  * <li><code>Match.getCapturedText(1)</code>: "<FONT color=red><KBD>TAMURA Kent</KBD></FONT>"
368  * <li><code>Match.getCapturedText(2)</code>: "<FONT color=red><KBD>kent@trl.ibm.co.jp</KBD></FONT>"
369  * </ul>
370  *
371  * <dt class="REGEX"><kbd>\1 \2 \3 \4 \5 \6 \7 \8 \9</kbd>
372  * <dd>
373  *
374  * <dt class="REGEX"><kbd>(?></kbd><var>X</var><kbd>)</kbd>
375  * <dd>Independent expression group. ................
376  *
377  * <dt class="REGEX"><kbd>(?</kbd><var>options</var><kbd>:</kbd><var>X</var><kbd>)</kbd>
378  * <dt class="REGEX"><kbd>(?</kbd><var>options</var><kbd>-</kbd><var>options2</var><kbd>:</kbd><var>X</var><kbd>)</kbd>
379  * <dd>............................
380  * <dd>The <var>options</var> or the <var>options2</var> consists of 'i' 'm' 's' 'w'.
381  * Note that it can not contain 'u'.
382  *
383  * <dt class="REGEX"><kbd>(?</kbd><var>options</var><kbd>)</kbd>
384  * <dt class="REGEX"><kbd>(?</kbd><var>options</var><kbd>-</kbd><var>options2</var><kbd>)</kbd>
385  * <dd>......
386  * <dd>These expressions must be at the beginning of a group.
387  * </dl>
388  * </li>
389  *
390  * <li>Anchor
391  * <dl>
392  * <dt class="REGEX"><kbd>\A</kbd>
393  * <dd>Matches the beginnig of the text.
394  *
395  * <dt class="REGEX"><kbd>\Z</kbd>
396  * <dd>Matches the end of the text, or before an EOL character at the end of the text,
397  * or CARRIAGE RETURN + LINE FEED at the end of the text.
398  *
399  * <dt class="REGEX"><kbd>\z</kbd>
400  * <dd>Matches the end of the text.
401  *
402  * <dt class="REGEX"><kbd>^</kbd>
403  * <dd>Matches the beginning of the text. It is equivalent to <span class="REGEX"><Kbd>\A</kbd></span>.
404  * <dd>When <a HREF="#M_OPTION">a "m" option</a> is set,
405  * it matches the beginning of the text, or after one of EOL characters (
406  * LINE FEED (U+000A), CARRIAGE RETURN (U+000D), LINE SEPARATOR (U+2028),
407  * PARAGRAPH SEPARATOR (U+2029).)
408  *
409  * <dt class="REGEX"><kbd>$</kbd>
410  * <dd>Matches the end of the text, or before an EOL character at the end of the text,
411  * or CARRIAGE RETURN + LINE FEED at the end of the text.
412  * <dd>When <a HREF="#M_OPTION">a "m" option</a> is set,
413  * it matches the end of the text, or before an EOL character.
414  *
415  * <dt class="REGEX"><kbd>\b</kbd>
416  * <dd>Matches word boundary.
417  * (See <a HREF="#W_OPTION">a "w" option</a>)
418  *
419  * <dt class="REGEX"><kbd>\B</kbd>
420  * <dd>Matches non word boundary.
421  * (See <a HREF="#W_OPTION">a "w" option</a>)
422  *
423  * <dt class="REGEX"><kbd>\&lt;</kbd>
424  * <dd>Matches the beginning of a word.
425  * (See <a HREF="#W_OPTION">a "w" option</a>)
426  *
427  * <dt class="REGEX"><kbd>\&gt;</kbd>
428  * <dd>Matches the end of a word.
429  * (See <a HREF="#W_OPTION">a "w" option</a>)
430  * </dl>
431  * </li>
432  * <li>Lookahead and lookbehind
433  * <dl>
434  * <dt class="REGEX"><kbd>(?=</kbd><var>X</var><kbd>)</kbd>
435  * <dd>Lookahead.
436  *
437  * <dt class="REGEX"><kbd>(?!</kbd><var>X</var><kbd>)</kbd>
438  * <dd>Negative lookahead.
439  *
440  * <dt class="REGEX"><kbd>(?&lt;=</kbd><var>X</var><kbd>)</kbd>
441  * <dd>Lookbehind.
442  * <dd>(Note for text capturing......)
443  *
444  * <dt class="REGEX"><kbd>(?&lt;!</kbd><var>X</var><kbd>)</kbd>
445  * <dd>Negative lookbehind.
446  * </dl>
447  * </li>
448  *
449  * <li>Misc.
450  * <dl>
451  * <dt class="REGEX"><kbd>(?(</Kbd><var>condition</var><Kbd>)</kbd><var>yes-pattern</var><kbd>|</kbd><var>no-pattern</var><kbd>)</kbd>,
452  * <dt class="REGEX"><kbd>(?(</kbd><var>condition</var><kbd>)</kbd><var>yes-pattern</var><kbd>)</kbd>
453  * <dd>......
454  * <dt class="REGEX"><kbd>(?#</kbd><var>comment</var><kbd>)</kbd>
455  * <dd>Comment. A comment string consists of characters except '<kbd>)</kbd>'.
456  * You can not write comments in character classes and before quantifiers.
457  * </dl>
458  * </li>
459  * </ul>
460  *
461  *
462  * <hr width="50%">
463  * <h3>BNF for the regular expression</h3>
464  * <pre>
465  * regex ::= ('(?' options ')')? term ('|' term)*
466  * term ::= factor+
467  * factor ::= anchors | atom (('*' | '+' | '?' | minmax ) '?'? )?
468  * | '(?#' [^)]* ')'
469  * minmax ::= '{' ([0-9]+ | [0-9]+ ',' | ',' [0-9]+ | [0-9]+ ',' [0-9]+) '}'
470  * atom ::= char | '.' | char-class | '(' regex ')' | '(?:' regex ')' | '\' [0-9]
471  * | '\w' | '\W' | '\d' | '\D' | '\s' | '\S' | category-block | '\X'
472  * | '(?>' regex ')' | '(?' options ':' regex ')'
473  * | '(?' ('(' [0-9] ')' | '(' anchors ')' | looks) term ('|' term)? ')'
474  * options ::= [imsw]* ('-' [imsw]+)?
475  * anchors ::= '^' | '$' | '\A' | '\Z' | '\z' | '\b' | '\B' | '\&lt;' | '\>'
476  * looks ::= '(?=' regex ')' | '(?!' regex ')'
477  * | '(?&lt;=' regex ')' | '(?&lt;!' regex ')'
478  * char ::= '\\' | '\' [efnrtv] | '\c' [@-_] | code-point | character-1
479  * category-block ::= '\' [pP] category-symbol-1
480  * | ('\p{' | '\P{') (category-symbol | block-name
481  * | other-properties) '}'
482  * category-symbol-1 ::= 'L' | 'M' | 'N' | 'Z' | 'C' | 'P' | 'S'
483  * category-symbol ::= category-symbol-1 | 'Lu' | 'Ll' | 'Lt' | 'Lm' | Lo'
484  * | 'Mn' | 'Me' | 'Mc' | 'Nd' | 'Nl' | 'No'
485  * | 'Zs' | 'Zl' | 'Zp' | 'Cc' | 'Cf' | 'Cn' | 'Co' | 'Cs'
486  * | 'Pd' | 'Ps' | 'Pe' | 'Pc' | 'Po'
487  * | 'Sm' | 'Sc' | 'Sk' | 'So'
488  * block-name ::= (See above)
489  * other-properties ::= 'ALL' | 'ASSIGNED' | 'UNASSIGNED'
490  * character-1 ::= (any character except meta-characters)
491  *
492  * char-class ::= '[' ranges ']'
493  * | '(?[' ranges ']' ([-+&] '[' ranges ']')? ')'
494  * ranges ::= '^'? (range <a HREF="#COMMA_OPTION">','?</a>)+
495  * range ::= '\d' | '\w' | '\s' | '\D' | '\W' | '\S' | category-block
496  * | range-char | range-char '-' range-char
497  * range-char ::= '\[' | '\]' | '\\' | '\' [,-efnrtv] | code-point | character-2
498  * code-point ::= '\x' hex-char hex-char
499  * | '\x{' hex-char+ '}'
500  * <!-- | '\ u' hex-char hex-char hex-char hex-char
501  * --> | '\v' hex-char hex-char hex-char hex-char hex-char hex-char
502  * hex-char ::= [0-9a-fA-F]
503  * character-2 ::= (any character except \[]-,)
504  * </pre>
505  *
506  * <hr width="50%">
507  * <h3>TODO</h3>
508  * <ul>
509  * <li><a HREF="http://www.unicode.org/unicode/reports/tr18/">Unicode Regular Expression Guidelines</a>
510  * <ul>
511  * <li>2.4 Canonical Equivalents
512  * <li>Level 3
513  * </ul>
514  * <li>Parsing performance
515  * </ul>
516  *
517  * <hr width="50%">
518  *
519  * @author TAMURA Kent &lt;kent@trl.ibm.co.jp&gt;
520  * @version $Id: RegularExpression.java,v 1.7 2003/07/15 12:28:25 neeraj Exp $
521  */

522 public class RegularExpression implements java.io.Serializable JavaDoc {
523     static final boolean DEBUG = false;
524
525     /**
526      * Compiles a token tree into an operation flow.
527      */

528     private synchronized void compile(Token tok) {
529         if (this.operations != null)
530             return;
531         this.numberOfClosures = 0;
532         this.operations = this.compile(tok, null, false);
533     }
534
535     /**
536      * Converts a token to an operation.
537      */

538     private Op compile(Token tok, Op next, boolean reverse) {
539         Op ret;
540         switch (tok.type) {
541         case Token.DOT:
542             ret = Op.createDot();
543             ret.next = next;
544             break;
545
546         case Token.CHAR:
547             ret = Op.createChar(tok.getChar());
548             ret.next = next;
549             break;
550
551         case Token.ANCHOR:
552             ret = Op.createAnchor(tok.getChar());
553             ret.next = next;
554             break;
555
556         case Token.RANGE:
557         case Token.NRANGE:
558             ret = Op.createRange(tok);
559             ret.next = next;
560             break;
561
562         case Token.CONCAT:
563             ret = next;
564             if (!reverse) {
565                 for (int i = tok.size()-1; i >= 0; i --) {
566                     ret = compile(tok.getChild(i), ret, false);
567                 }
568             } else {
569                 for (int i = 0; i < tok.size(); i ++) {
570                     ret = compile(tok.getChild(i), ret, true);
571                 }
572             }
573             break;
574
575         case Token.UNION:
576             Op.UnionOp uni = Op.createUnion(tok.size());
577             for (int i = 0; i < tok.size(); i ++) {
578                 uni.addElement(compile(tok.getChild(i), next, reverse));
579             }
580             ret = uni; // ret.next is null.
581
break;
582
583         case Token.CLOSURE:
584         case Token.NONGREEDYCLOSURE:
585             Token child = tok.getChild(0);
586             int min = tok.getMin();
587             int max = tok.getMax();
588             if (min >= 0 && min == max) { // {n}
589
ret = next;
590                 for (int i = 0; i < min; i ++) {
591                     ret = compile(child, ret, reverse);
592                 }
593                 break;
594             }
595             if (min > 0 && max > 0)
596                 max -= min;
597             if (max > 0) {
598                 // X{2,6} -> XX(X(X(XX?)?)?)?
599
ret = next;
600                 for (int i = 0; i < max; i ++) {
601                     Op.ChildOp q = Op.createQuestion(tok.type == Token.NONGREEDYCLOSURE);
602                     q.next = next;
603                     q.setChild(compile(child, ret, reverse));
604                     ret = q;
605                 }
606             } else {
607                 Op.ChildOp op;
608                 if (tok.type == Token.NONGREEDYCLOSURE) {
609                     op = Op.createNonGreedyClosure();
610                 } else { // Token.CLOSURE
611
if (child.getMinLength() == 0)
612                         op = Op.createClosure(this.numberOfClosures++);
613                     else
614                         op = Op.createClosure(-1);
615                 }
616                 op.next = next;
617                 op.setChild(compile(child, op, reverse));
618                 ret = op;
619             }
620             if (min > 0) {
621                 for (int i = 0; i < min; i ++) {
622                     ret = compile(child, ret, reverse);
623                 }
624             }
625             break;
626
627         case Token.EMPTY:
628             ret = next;
629             break;
630
631         case Token.STRING:
632             ret = Op.createString(tok.getString());
633             ret.next = next;
634             break;
635
636         case Token.BACKREFERENCE:
637             ret = Op.createBackReference(tok.getReferenceNumber());
638             ret.next = next;
639             break;
640
641         case Token.PAREN:
642             if (tok.getParenNumber() == 0) {
643                 ret = compile(tok.getChild(0), next, reverse);
644             } else if (reverse) {
645                 next = Op.createCapture(tok.getParenNumber(), next);
646                 next = compile(tok.getChild(0), next, reverse);
647                 ret = Op.createCapture(-tok.getParenNumber(), next);
648             } else {
649                 next = Op.createCapture(-tok.getParenNumber(), next);
650                 next = compile(tok.getChild(0), next, reverse);
651                 ret = Op.createCapture(tok.getParenNumber(), next);
652             }
653             break;
654
655         case Token.LOOKAHEAD:
656             ret = Op.createLook(Op.LOOKAHEAD, next, compile(tok.getChild(0), null, false));
657             break;
658         case Token.NEGATIVELOOKAHEAD:
659             ret = Op.createLook(Op.NEGATIVELOOKAHEAD, next, compile(tok.getChild(0), null, false));
660             break;
661         case Token.LOOKBEHIND:
662             ret = Op.createLook(Op.LOOKBEHIND, next, compile(tok.getChild(0), null, true));
663             break;
664         case Token.NEGATIVELOOKBEHIND:
665             ret = Op.createLook(Op.NEGATIVELOOKBEHIND, next, compile(tok.getChild(0), null, true));
666             break;
667
668         case Token.INDEPENDENT:
669             ret = Op.createIndependent(next, compile(tok.getChild(0), null, reverse));
670             break;
671
672         case Token.MODIFIERGROUP:
673             ret = Op.createModifier(next, compile(tok.getChild(0), null, reverse),
674                                     ((Token.ModifierToken)tok).getOptions(),
675                                     ((Token.ModifierToken)tok).getOptionsMask());
676             break;
677
678         case Token.CONDITION:
679             Token.ConditionToken ctok = (Token.ConditionToken)tok;
680             int ref = ctok.refNumber;
681             Op condition = ctok.condition == null ? null : compile(ctok.condition, null, reverse);
682             Op yes = compile(ctok.yes, next, reverse);
683             Op no = ctok.no == null ? null : compile(ctok.no, next, reverse);
684             ret = Op.createCondition(next, ref, condition, yes, no);
685             break;
686
687         default:
688             throw new RuntimeException JavaDoc("Unknown token type: "+tok.type);
689         } // switch (tok.type)
690
return ret;
691     }
692
693
694 //Public
695

696     /**
697      * Checks whether the <var>target</var> text <strong>contains</strong> this pattern or not.
698      *
699      * @return true if the target is matched to this regular expression.
700      */

701     public boolean matches(char[] target) {
702         return this.matches(target, 0, target .length , (Match)null);
703     }
704
705     /**
706      * Checks whether the <var>target</var> text <strong>contains</strong> this pattern
707      * in specified range or not.
708      *
709      * @param start Start offset of the range.
710      * @param end End offset +1 of the range.
711      * @return true if the target is matched to this regular expression.
712      */

713     public boolean matches(char[] target, int start, int end) {
714         return this.matches(target, start, end, (Match)null);
715     }
716
717     /**
718      * Checks whether the <var>target</var> text <strong>contains</strong> this pattern or not.
719      *
720      * @param match A Match instance for storing matching result.
721      * @return Offset of the start position in <VAR>target</VAR>; or -1 if not match.
722      */

723     public boolean matches(char[] target, Match match) {
724         return this.matches(target, 0, target .length , match);
725     }
726
727
728     /**
729      * Checks whether the <var>target</var> text <strong>contains</strong> this pattern
730      * in specified range or not.
731      *
732      * @param start Start offset of the range.
733      * @param end End offset +1 of the range.
734      * @param match A Match instance for storing matching result.
735      * @return Offset of the start position in <VAR>target</VAR>; or -1 if not match.
736      */

737     public boolean matches(char[] target, int start, int end, Match match) {
738
739         synchronized (this) {
740             if (this.operations == null)
741                 this.prepare();
742             if (this.context == null)
743                 this.context = new Context();
744         }
745         Context con = null;
746         synchronized (this.context) {
747             con = this.context.inuse ? new Context() : this.context;
748             con.reset(target, start, end, this.numberOfClosures);
749         }
750         if (match != null) {
751             match.setNumberOfGroups(this.nofparen);
752             match.setSource(target);
753         } else if (this.hasBackReferences) {
754             match = new Match();
755             match.setNumberOfGroups(this.nofparen);
756             // Need not to call setSource() because
757
// a caller can not access this match instance.
758
}
759         con.match = match;
760
761         if (RegularExpression.isSet(this.options, XMLSCHEMA_MODE)) {
762             int matchEnd = this. matchCharArray (con, this.operations, con.start, 1, this.options);
763             //System.err.println("DEBUG: matchEnd="+matchEnd);
764
if (matchEnd == con.limit) {
765                 if (con.match != null) {
766                     con.match.setBeginning(0, con.start);
767                     con.match.setEnd(0, matchEnd);
768                 }
769                 con.inuse = false;
770                 return true;
771             }
772             return false;
773         }
774
775         /*
776          * The pattern has only fixed string.
777          * The engine uses Boyer-Moore.
778          */

779         if (this.fixedStringOnly) {
780             //System.err.println("DEBUG: fixed-only: "+this.fixedString);
781
int o = this.fixedStringTable.matches(target, con.start, con.limit);
782             if (o >= 0) {
783                 if (con.match != null) {
784                     con.match.setBeginning(0, o);
785                     con.match.setEnd(0, o+this.fixedString.length());
786                 }
787                 con.inuse = false;
788                 return true;
789             }
790             con.inuse = false;
791             return false;
792         }
793
794         /*
795          * The pattern contains a fixed string.
796          * The engine checks with Boyer-Moore whether the text contains the fixed string or not.
797          * If not, it return with false.
798          */

799         if (this.fixedString != null) {
800             int o = this.fixedStringTable.matches(target, con.start, con.limit);
801             if (o < 0) {
802                 //System.err.println("Non-match in fixed-string search.");
803
con.inuse = false;
804                 return false;
805             }
806         }
807
808         int limit = con.limit-this.minlength;
809         int matchStart;
810         int matchEnd = -1;
811
812         /*
813          * Checks whether the expression starts with ".*".
814          */

815         if (this.operations != null
816             && this.operations.type == Op.CLOSURE && this.operations.getChild().type == Op.DOT) {
817             if (isSet(this.options, SINGLE_LINE)) {
818                 matchStart = con.start;
819                 matchEnd = this. matchCharArray (con, this.operations, con.start, 1, this.options);
820             } else {
821                 boolean previousIsEOL = true;
822                 for (matchStart = con.start; matchStart <= limit; matchStart ++) {
823                     int ch = target [ matchStart ] ;
824                     if (isEOLChar(ch)) {
825                         previousIsEOL = true;
826                     } else {
827                         if (previousIsEOL) {
828                             if (0 <= (matchEnd = this. matchCharArray (con, this.operations,
829                                                                        matchStart, 1, this.options)))
830                                 break;
831                         }
832                         previousIsEOL = false;
833                     }
834                 }
835             }
836         }
837
838         /*
839          * Optimization against the first character.
840          */

841         else if (this.firstChar != null) {
842             //System.err.println("DEBUG: with firstchar-matching: "+this.firstChar);
843
RangeToken range = this.firstChar;
844             if (RegularExpression.isSet(this.options, IGNORE_CASE)) {
845                 range = this.firstChar.getCaseInsensitiveToken();
846                 for (matchStart = con.start; matchStart <= limit; matchStart ++) {
847                     int ch = target [ matchStart ] ;
848                     if (REUtil.isHighSurrogate(ch) && matchStart+1 < con.limit) {
849                         ch = REUtil.composeFromSurrogates(ch, target [ matchStart+1 ] );
850                         if (!range.match(ch)) continue;
851                     } else {
852                         if (!range.match(ch)) {
853                             char ch1 = Character.toUpperCase((char)ch);
854                             if (!range.match(ch1))
855                                 if (!range.match(Character.toLowerCase(ch1)))
856                                     continue;
857                         }
858                     }
859                     if (0 <= (matchEnd = this. matchCharArray (con, this.operations,
860                                                                matchStart, 1, this.options)))
861                         break;
862                 }
863             } else {
864                 for (matchStart = con.start; matchStart <= limit; matchStart ++) {
865                     int ch = target [ matchStart ] ;
866                     if (REUtil.isHighSurrogate(ch) && matchStart+1 < con.limit)
867                         ch = REUtil.composeFromSurrogates(ch, target [ matchStart+1 ] );
868                     if (!range.match(ch)) continue;
869                     if (0 <= (matchEnd = this. matchCharArray (con, this.operations,
870                                                                matchStart, 1, this.options)))
871                         break;
872                 }
873             }
874         }
875
876         /*
877          * Straightforward matching.
878          */

879         else {
880             for (matchStart = con.start; matchStart <= limit; matchStart ++) {
881                 if (0 <= (matchEnd = this. matchCharArray (con, this.operations, matchStart, 1, this.options)))
882                     break;
883             }
884         }
885
886         if (matchEnd >= 0) {
887             if (con.match != null) {
888                 con.match.setBeginning(0, matchStart);
889                 con.match.setEnd(0, matchEnd);
890             }
891             con.inuse = false;
892             return true;
893         } else {
894             con.inuse = false;
895             return false;
896         }
897     }
898
899 /**
900  * @return -1 when not match; offset of the end of matched string when match.
901  */

902     private int matchCharArray (Context con, Op op, int offset, int dx, int opts) {
903
904         char[] target = con.charTarget;
905
906
907         while (true) {
908             if (op == null)
909                 return isSet(opts, XMLSCHEMA_MODE) && offset != con.limit ? -1 : offset;
910             if (offset > con.limit || offset < con.start)
911                 return -1;
912             switch (op.type) {
913             case Op.CHAR:
914                 if (isSet(opts, IGNORE_CASE)) {
915                     int ch = op.getData();
916                     if (dx > 0) {
917                         if (offset >= con.limit || !matchIgnoreCase(ch, target [ offset ] ))
918                             return -1;
919                         offset ++;
920                     } else {
921                         int o1 = offset-1;
922                         if (o1 >= con.limit || o1 < 0 || !matchIgnoreCase(ch, target [ o1 ] ))
923                             return -1;
924                         offset = o1;
925                     }
926                 } else {
927                     int ch = op.getData();
928                     if (dx > 0) {
929                         if (offset >= con.limit || ch != target [ offset ] )
930                             return -1;
931                         offset ++;
932                     } else {
933                         int o1 = offset-1;
934                         if (o1 >= con.limit || o1 < 0 || ch != target [ o1 ] )
935                             return -1;
936                         offset = o1;
937                     }
938                 }
939                 op = op.next;
940                 break;
941
942             case Op.DOT:
943                 if (dx > 0) {
944                     if (offset >= con.limit)
945                         return -1;
946                     int ch = target [ offset ] ;
947                     if (isSet(opts, SINGLE_LINE)) {
948                         if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
949                             offset ++;
950                     } else {
951                         if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
952                             ch = REUtil.composeFromSurrogates(ch, target [ ++offset ] );
953                         if (isEOLChar(ch))
954                             return -1;
955                     }
956                     offset ++;
957                 } else {
958                     int o1 = offset-1;
959                     if (o1 >= con.limit || o1 < 0)
960                         return -1;
961                     int ch = target [ o1 ] ;
962                     if (isSet(opts, SINGLE_LINE)) {
963                         if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
964                             o1 --;
965                     } else {
966                         if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
967                             ch = REUtil.composeFromSurrogates( target [ --o1 ] , ch);
968                         if (!isEOLChar(ch))
969                             return -1;
970                     }
971                     offset = o1;
972                 }
973                 op = op.next;
974                 break;
975
976             case Op.RANGE:
977             case Op.NRANGE:
978                 if (dx > 0) {
979                     if (offset >= con.limit)
980                         return -1;
981                     int ch = target [ offset ] ;
982                     if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
983                         ch = REUtil.composeFromSurrogates(ch, target [ ++offset ] );
984                     RangeToken tok = op.getToken();
985                     if (isSet(opts, IGNORE_CASE)) {
986                         tok = tok.getCaseInsensitiveToken();
987                         if (!tok.match(ch)) {
988                             if (ch >= 0x10000) return -1;
989                             char uch;
990                             if (!tok.match(uch = Character.toUpperCase((char)ch))
991                                 && !tok.match(Character.toLowerCase(uch)))
992                                 return -1;
993                         }
994                     } else {
995                         if (!tok.match(ch)) return -1;
996                     }
997                     offset ++;
998                 } else {
999                     int o1 = offset-1;
1000                    if (o1 >= con.limit || o1 < 0)
1001                        return -1;
1002                    int ch = target [ o1 ] ;
1003                    if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
1004                        ch = REUtil.composeFromSurrogates( target [ --o1 ] , ch);
1005                    RangeToken tok = op.getToken();
1006                    if (isSet(opts, IGNORE_CASE)) {
1007                        tok = tok.getCaseInsensitiveToken();
1008                        if (!tok.match(ch)) {
1009                            if (ch >= 0x10000) return -1;
1010                            char uch;
1011                            if (!tok.match(uch = Character.toUpperCase((char)ch))
1012                                && !tok.match(Character.toLowerCase(uch)))
1013                                return -1;
1014                        }
1015                    } else {
1016                        if (!tok.match(ch)) return -1;
1017                    }
1018                    offset = o1;
1019                }
1020                op = op.next;
1021                break;
1022
1023            case Op.ANCHOR:
1024                boolean go = false;
1025                switch (op.getData()) {
1026                case '^':
1027                    if (isSet(opts, MULTIPLE_LINES)) {
1028                        if (!(offset == con.start
1029                              || offset > con.start && isEOLChar( target [ offset-1 ] )))
1030                            return -1;
1031                    } else {
1032                        if (offset != con.start)
1033                            return -1;
1034                    }
1035                    break;
1036
1037                case '@': // Internal use only.
1038
// The @ always matches line beginnings.
1039
if (!(offset == con.start
1040                          || offset > con.start && isEOLChar( target [ offset-1 ] )))
1041                        return -1;
1042                    break;
1043
1044                case '$':
1045                    if (isSet(opts, MULTIPLE_LINES)) {
1046                        if (!(offset == con.limit
1047                              || offset < con.limit && isEOLChar( target [ offset ] )))
1048                            return -1;
1049                    } else {
1050                        if (!(offset == con.limit
1051                              || offset+1 == con.limit && isEOLChar( target [ offset ] )
1052                              || offset+2 == con.limit && target [ offset ] == CARRIAGE_RETURN
1053                              && target [ offset+1 ] == LINE_FEED))
1054                            return -1;
1055                    }
1056                    break;
1057
1058                case 'A':
1059                    if (offset != con.start) return -1;
1060                    break;
1061
1062                case 'Z':
1063                    if (!(offset == con.limit
1064                          || offset+1 == con.limit && isEOLChar( target [ offset ] )
1065                          || offset+2 == con.limit && target [ offset ] == CARRIAGE_RETURN
1066                          && target [ offset+1 ] == LINE_FEED))
1067                        return -1;
1068                    break;
1069
1070                case 'z':
1071                    if (offset != con.limit) return -1;
1072                    break;
1073
1074                case 'b':
1075                    if (con.length == 0) return -1;
1076                    {
1077                        int after = getWordType(target, con.start, con.limit, offset, opts);
1078                        if (after == WT_IGNORE) return -1;
1079                        int before = getPreviousWordType(target, con.start, con.limit, offset, opts);
1080                        if (after == before) return -1;
1081                    }
1082                    break;
1083
1084                case 'B':
1085                    if (con.length == 0)
1086                        go = true;
1087                    else {
1088                        int after = getWordType(target, con.start, con.limit, offset, opts);
1089                        go = after == WT_IGNORE
1090                             || after == getPreviousWordType(target, con.start, con.limit, offset, opts);
1091                    }
1092                    if (!go) return -1;
1093                    break;
1094
1095                case '<':
1096                    if (con.length == 0 || offset == con.limit) return -1;
1097                    if (getWordType(target, con.start, con.limit, offset, opts) != WT_LETTER
1098                        || getPreviousWordType(target, con.start, con.limit, offset, opts) != WT_OTHER)
1099                        return -1;
1100                    break;
1101
1102                case '>':
1103                    if (con.length == 0 || offset == con.start) return -1;
1104                    if (getWordType(target, con.start, con.limit, offset, opts) != WT_OTHER
1105                        || getPreviousWordType(target, con.start, con.limit, offset, opts) != WT_LETTER)
1106                        return -1;
1107                    break;
1108                } // switch anchor type
1109
op = op.next;
1110                break;
1111
1112            case Op.BACKREFERENCE:
1113                {
1114                    int refno = op.getData();
1115                    if (refno <= 0 || refno >= this.nofparen)
1116                        throw new RuntimeException JavaDoc("Internal Error: Reference number must be more than zero: "+refno);
1117                    if (con.match.getBeginning(refno) < 0
1118                        || con.match.getEnd(refno) < 0)
1119                        return -1; // ********
1120
int o2 = con.match.getBeginning(refno);
1121                    int literallen = con.match.getEnd(refno)-o2;
1122                    if (!isSet(opts, IGNORE_CASE)) {
1123                        if (dx > 0) {
1124                            if (!regionMatches(target, offset, con.limit, o2, literallen))
1125                                return -1;
1126                            offset += literallen;
1127                        } else {
1128                            if (!regionMatches(target, offset-literallen, con.limit, o2, literallen))
1129                                return -1;
1130                            offset -= literallen;
1131                        }
1132                    } else {
1133                        if (dx > 0) {
1134                            if (!regionMatchesIgnoreCase(target, offset, con.limit, o2, literallen))
1135                                return -1;
1136                            offset += literallen;
1137                        } else {
1138                            if (!regionMatchesIgnoreCase(target, offset-literallen, con.limit,
1139                                                         o2, literallen))
1140                                return -1;
1141                            offset -= literallen;
1142                        }
1143                    }
1144                }
1145                op = op.next;
1146                break;
1147            case Op.STRING:
1148                {
1149                    String JavaDoc literal = op.getString();
1150                    int literallen = literal.length();
1151                    if (!isSet(opts, IGNORE_CASE)) {
1152                        if (dx > 0) {
1153                            if (!regionMatches(target, offset, con.limit, literal, literallen))
1154                                return -1;
1155                            offset += literallen;
1156                        } else {
1157                            if (!regionMatches(target, offset-literallen, con.limit, literal, literallen))
1158                                return -1;
1159                            offset -= literallen;
1160                        }
1161                    } else {
1162                        if (dx > 0) {
1163                            if (!regionMatchesIgnoreCase(target, offset, con.limit, literal, literallen))
1164                                return -1;
1165                            offset += literallen;
1166                        } else {
1167                            if (!regionMatchesIgnoreCase(target, offset-literallen, con.limit,
1168                                                         literal, literallen))
1169                                return -1;
1170                            offset -= literallen;
1171                        }
1172                    }
1173                }
1174                op = op.next;
1175                break;
1176
1177            case Op.CLOSURE:
1178                {
1179                    /*
1180                     * Saves current position to avoid
1181                     * zero-width repeats.
1182                     */

1183                    int id = op.getData();
1184                    if (id >= 0) {
1185                        int previousOffset = con.offsets[id];
1186                        if (previousOffset < 0 || previousOffset != offset) {
1187                            con.offsets[id] = offset;
1188                        } else {
1189                            con.offsets[id] = -1;
1190                            op = op.next;
1191                            break;
1192                        }
1193                    }
1194
1195                    int ret = this. matchCharArray (con, op.getChild(), offset, dx, opts);
1196                    if (id >= 0) con.offsets[id] = -1;
1197                    if (ret >= 0) return ret;
1198                    op = op.next;
1199                }
1200                break;
1201
1202            case Op.QUESTION:
1203                {
1204                    int ret = this. matchCharArray (con, op.getChild(), offset, dx, opts);
1205                    if (ret >= 0) return ret;
1206                    op = op.next;
1207                }
1208                break;
1209
1210            case Op.NONGREEDYCLOSURE:
1211            case Op.NONGREEDYQUESTION:
1212                {
1213                    int ret = this. matchCharArray (con, op.next, offset, dx, opts);
1214                    if (ret >= 0) return ret;
1215                    op = op.getChild();
1216                }
1217                break;
1218
1219            case Op.UNION:
1220                for (int i = 0; i < op.size(); i ++) {
1221                    int ret = this. matchCharArray (con, op.elementAt(i), offset, dx, opts);
1222                    if (DEBUG) {
1223                        System.err.println("UNION: "+i+", ret="+ret);
1224                    }
1225                    if (ret >= 0) return ret;
1226                }
1227                return -1;
1228
1229            case Op.CAPTURE:
1230                int refno = op.getData();
1231                if (con.match != null && refno > 0) {
1232                    int save = con.match.getBeginning(refno);
1233                    con.match.setBeginning(refno, offset);
1234                    int ret = this. matchCharArray (con, op.next, offset, dx, opts);
1235                    if (ret < 0) con.match.setBeginning(refno, save);
1236                    return ret;
1237                } else if (con.match != null && refno < 0) {
1238                    int index = -refno;
1239                    int save = con.match.getEnd(index);
1240                    con.match.setEnd(index, offset);
1241                    int ret = this. matchCharArray (con, op.next, offset, dx, opts);
1242                    if (ret < 0) con.match.setEnd(index, save);
1243                    return ret;
1244                }
1245                op = op.next;
1246                break;
1247
1248            case Op.LOOKAHEAD:
1249                if (0 > this. matchCharArray (con, op.getChild(), offset, 1, opts)) return -1;
1250                op = op.next;
1251                break;
1252            case Op.NEGATIVELOOKAHEAD:
1253                if (0 <= this. matchCharArray (con, op.getChild(), offset, 1, opts)) return -1;
1254                op = op.next;
1255                break;
1256            case Op.LOOKBEHIND:
1257                if (0 > this. matchCharArray (con, op.getChild(), offset, -1, opts)) return -1;
1258                op = op.next;
1259                break;
1260            case Op.NEGATIVELOOKBEHIND:
1261                if (0 <= this. matchCharArray (con, op.getChild(), offset, -1, opts)) return -1;
1262                op = op.next;
1263                break;
1264
1265            case Op.INDEPENDENT:
1266                {
1267                    int ret = this. matchCharArray (con, op.getChild(), offset, dx, opts);
1268                    if (ret < 0) return ret;
1269                    offset = ret;
1270                    op = op.next;
1271                }
1272                break;
1273
1274            case Op.MODIFIER:
1275                {
1276                    int localopts = opts;
1277                    localopts |= op.getData();
1278                    localopts &= ~op.getData2();
1279                    //System.err.println("MODIFIER: "+Integer.toString(opts, 16)+" -> "+Integer.toString(localopts, 16));
1280
int ret = this. matchCharArray (con, op.getChild(), offset, dx, localopts);
1281                    if (ret < 0) return ret;
1282                    offset = ret;
1283                    op = op.next;
1284                }
1285                break;
1286
1287            case Op.CONDITION:
1288                {
1289                    Op.ConditionOp cop = (Op.ConditionOp)op;
1290                    boolean matchp = false;
1291                    if (cop.refNumber > 0) {
1292                        if (cop.refNumber >= this.nofparen)
1293                            throw new RuntimeException JavaDoc("Internal Error: Reference number must be more than zero: "+cop.refNumber);
1294                        matchp = con.match.getBeginning(cop.refNumber) >= 0
1295                                 && con.match.getEnd(cop.refNumber) >= 0;
1296                    } else {
1297                        matchp = 0 <= this. matchCharArray (con, cop.condition, offset, dx, opts);
1298                    }
1299
1300                    if (matchp) {
1301                        op = cop.yes;
1302                    } else if (cop.no != null) {
1303                        op = cop.no;
1304                    } else {
1305                        op = cop.next;
1306                    }
1307                }
1308                break;
1309
1310            default:
1311                throw new RuntimeException JavaDoc("Unknown operation type: "+op.type);
1312            } // switch (op.type)
1313
} // while
1314
}
1315
1316    private static final int getPreviousWordType(char[] target, int begin, int end,
1317                                                 int offset, int opts) {
1318        int ret = getWordType(target, begin, end, --offset, opts);
1319        while (ret == WT_IGNORE)
1320            ret = getWordType(target, begin, end, --offset, opts);
1321        return ret;
1322    }
1323
1324    private static final int getWordType(char[] target, int begin, int end,
1325                                         int offset, int opts) {
1326        if (offset < begin || offset >= end) return WT_OTHER;
1327        return getWordType0( target [ offset ] , opts);
1328    }
1329
1330
1331
1332    private static final boolean regionMatches(char[] target, int offset, int limit,
1333                                               String JavaDoc part, int partlen) {
1334        if (offset < 0) return false;
1335        if (limit-offset < partlen)
1336            return false;
1337        int i = 0;
1338        while (partlen-- > 0) {
1339            if ( target [ offset++ ] != part.charAt(i++))
1340                return false;
1341        }
1342        return true;
1343    }
1344
1345    private static final boolean regionMatches(char[] target, int offset, int limit,
1346                                               int offset2, int partlen) {
1347        if (offset < 0) return false;
1348        if (limit-offset < partlen)
1349            return false;
1350        int i = offset2;
1351        while (partlen-- > 0) {
1352            if ( target [ offset++ ] != target [ i++ ] )
1353                return false;
1354        }
1355        return true;
1356    }
1357
1358/**
1359 * @see java.lang.String#regionMatches
1360 */

1361    private static final boolean regionMatchesIgnoreCase(char[] target, int offset, int limit,
1362                                                         String JavaDoc part, int partlen) {
1363        if (offset < 0) return false;
1364        if (limit-offset < partlen)
1365            return false;
1366        int i = 0;
1367        while (partlen-- > 0) {
1368            char ch1 = target [ offset++ ] ;
1369            char ch2 = part.charAt(i++);
1370            if (ch1 == ch2)
1371                continue;
1372            char uch1 = Character.toUpperCase(ch1);
1373            char uch2 = Character.toUpperCase(ch2);
1374            if (uch1 == uch2)
1375                continue;
1376            if (Character.toLowerCase(uch1) != Character.toLowerCase(uch2))
1377                return false;
1378        }
1379        return true;
1380    }
1381
1382    private static final boolean regionMatchesIgnoreCase(char[] target, int offset, int limit,
1383                                                         int offset2, int partlen) {
1384        if (offset < 0) return false;
1385        if (limit-offset < partlen)
1386            return false;
1387        int i = offset2;
1388        while (partlen-- > 0) {
1389            char ch1 = target [ offset++ ] ;
1390            char ch2 = target [ i++ ] ;
1391            if (ch1 == ch2)
1392                continue;
1393            char uch1 = Character.toUpperCase(ch1);
1394            char uch2 = Character.toUpperCase(ch2);
1395            if (uch1 == uch2)
1396                continue;
1397            if (Character.toLowerCase(uch1) != Character.toLowerCase(uch2))
1398                return false;
1399        }
1400        return true;
1401    }
1402
1403
1404
1405
1406    /**
1407     * Checks whether the <var>target</var> text <strong>contains</strong> this pattern or not.
1408     *
1409     * @return true if the target is matched to this regular expression.
1410     */

1411    public boolean matches(String JavaDoc target) {
1412        return this.matches(target, 0, target .length() , (Match)null);
1413    }
1414
1415    /**
1416     * Checks whether the <var>target</var> text <strong>contains</strong> this pattern
1417     * in specified range or not.
1418     *
1419     * @param start Start offset of the range.
1420     * @param end End offset +1 of the range.
1421     * @return true if the target is matched to this regular expression.
1422     */

1423    public boolean matches(String JavaDoc target, int start, int end) {
1424        return this.matches(target, start, end, (Match)null);
1425    }
1426
1427    /**
1428     * Checks whether the <var>target</var> text <strong>contains</strong> this pattern or not.
1429     *
1430     * @param match A Match instance for storing matching result.
1431     * @return Offset of the start position in <VAR>target</VAR>; or -1 if not match.
1432     */

1433    public boolean matches(String JavaDoc target, Match match) {
1434        return this.matches(target, 0, target .length() , match);
1435    }
1436
1437    /**
1438     * Checks whether the <var>target</var> text <strong>contains</strong> this pattern
1439     * in specified range or not.
1440     *
1441     * @param start Start offset of the range.
1442     * @param end End offset +1 of the range.
1443     * @param match A Match instance for storing matching result.
1444     * @return Offset of the start position in <VAR>target</VAR>; or -1 if not match.
1445     */

1446    public boolean matches(String JavaDoc target, int start, int end, Match match) {
1447
1448        synchronized (this) {
1449            if (this.operations == null)
1450                this.prepare();
1451            if (this.context == null)
1452                this.context = new Context();
1453        }
1454        Context con = null;
1455        synchronized (this.context) {
1456            con = this.context.inuse ? new Context() : this.context;
1457            con.reset(target, start, end, this.numberOfClosures);
1458        }
1459        if (match != null) {
1460            match.setNumberOfGroups(this.nofparen);
1461            match.setSource(target);
1462        } else if (this.hasBackReferences) {
1463            match = new Match();
1464            match.setNumberOfGroups(this.nofparen);
1465            // Need not to call setSource() because
1466
// a caller can not access this match instance.
1467
}
1468        con.match = match;
1469
1470        if (RegularExpression.isSet(this.options, XMLSCHEMA_MODE)) {
1471            if (DEBUG) {
1472                System.err.println("target string="+target);
1473            }
1474            int matchEnd = this. matchString (con, this.operations, con.start, 1, this.options);
1475            if (DEBUG) {
1476                System.err.println("matchEnd="+matchEnd);
1477                System.err.println("con.limit="+con.limit);
1478            }
1479            if (matchEnd == con.limit) {
1480                if (con.match != null) {
1481                    con.match.setBeginning(0, con.start);
1482                    con.match.setEnd(0, matchEnd);
1483                }
1484                con.inuse = false;
1485                return true;
1486            }
1487            return false;
1488        }
1489
1490        /*
1491         * The pattern has only fixed string.
1492         * The engine uses Boyer-Moore.
1493         */

1494        if (this.fixedStringOnly) {
1495            //System.err.println("DEBUG: fixed-only: "+this.fixedString);
1496
int o = this.fixedStringTable.matches(target, con.start, con.limit);
1497            if (o >= 0) {
1498                if (con.match != null) {
1499                    con.match.setBeginning(0, o);
1500                    con.match.setEnd(0, o+this.fixedString.length());
1501                }
1502                con.inuse = false;
1503                return true;
1504            }
1505            con.inuse = false;
1506            return false;
1507        }
1508
1509        /*
1510         * The pattern contains a fixed string.
1511         * The engine checks with Boyer-Moore whether the text contains the fixed string or not.
1512         * If not, it return with false.
1513         */

1514        if (this.fixedString != null) {
1515            int o = this.fixedStringTable.matches(target, con.start, con.limit);
1516            if (o < 0) {
1517                //System.err.println("Non-match in fixed-string search.");
1518
con.inuse = false;
1519                return false;
1520            }
1521        }
1522
1523        int limit = con.limit-this.minlength;
1524        int matchStart;
1525        int matchEnd = -1;
1526
1527        /*
1528         * Checks whether the expression starts with ".*".
1529         */

1530        if (this.operations != null
1531            && this.operations.type == Op.CLOSURE && this.operations.getChild().type == Op.DOT) {
1532            if (isSet(this.options, SINGLE_LINE)) {
1533                matchStart = con.start;
1534                matchEnd = this. matchString (con, this.operations, con.start, 1, this.options);
1535            } else {
1536                boolean previousIsEOL = true;
1537                for (matchStart = con.start; matchStart <= limit; matchStart ++) {
1538                    int ch = target .charAt( matchStart ) ;
1539                    if (isEOLChar(ch)) {
1540                        previousIsEOL = true;
1541                    } else {
1542                        if (previousIsEOL) {
1543                            if (0 <= (matchEnd = this. matchString (con, this.operations,
1544                                                                    matchStart, 1, this.options)))
1545                                break;
1546                        }
1547                        previousIsEOL = false;
1548                    }
1549                }
1550            }
1551        }
1552
1553        /*
1554         * Optimization against the first character.
1555         */

1556        else if (this.firstChar != null) {
1557            //System.err.println("DEBUG: with firstchar-matching: "+this.firstChar);
1558
RangeToken range = this.firstChar;
1559            if (RegularExpression.isSet(this.options, IGNORE_CASE)) {
1560                range = this.firstChar.getCaseInsensitiveToken();
1561                for (matchStart = con.start; matchStart <= limit; matchStart ++) {
1562                    int ch = target .charAt( matchStart ) ;
1563                    if (REUtil.isHighSurrogate(ch) && matchStart+1 < con.limit) {
1564                        ch = REUtil.composeFromSurrogates(ch, target .charAt( matchStart+1 ) );
1565                        if (!range.match(ch)) continue;
1566                    } else {
1567                        if (!range.match(ch)) {
1568                            char ch1 = Character.toUpperCase((char)ch);
1569                            if (!range.match(ch1))
1570                                if (!range.match(Character.toLowerCase(ch1)))
1571                                    continue;
1572                        }
1573                    }
1574                    if (0 <= (matchEnd = this. matchString (con, this.operations,
1575                                                            matchStart, 1, this.options)))
1576                        break;
1577                }
1578            } else {
1579                for (matchStart = con.start; matchStart <= limit; matchStart ++) {
1580                    int ch = target .charAt( matchStart ) ;
1581                    if (REUtil.isHighSurrogate(ch) && matchStart+1 < con.limit)
1582                        ch = REUtil.composeFromSurrogates(ch, target .charAt( matchStart+1 ) );
1583                    if (!range.match(ch)) continue;
1584                    if (0 <= (matchEnd = this. matchString (con, this.operations,
1585                                                            matchStart, 1, this.options)))
1586                        break;
1587                }
1588            }
1589        }
1590
1591        /*
1592         * Straightforward matching.
1593         */

1594        else {
1595            for (matchStart = con.start; matchStart <= limit; matchStart ++) {
1596                if (0 <= (matchEnd = this. matchString (con, this.operations, matchStart, 1, this.options)))
1597                    break;
1598            }
1599        }
1600
1601        if (matchEnd >= 0) {
1602            if (con.match != null) {
1603                con.match.setBeginning(0, matchStart);
1604                con.match.setEnd(0, matchEnd);
1605            }
1606            con.inuse = false;
1607            return true;
1608        } else {
1609            con.inuse = false;
1610            return false;
1611        }
1612    }
1613
1614    /**
1615     * @return -1 when not match; offset of the end of matched string when match.
1616     */

1617    private int matchString (Context con, Op op, int offset, int dx, int opts) {
1618
1619
1620
1621
1622        String JavaDoc target = con.strTarget;
1623
1624
1625
1626
1627        while (true) {
1628            if (op == null)
1629                return isSet(opts, XMLSCHEMA_MODE) && offset != con.limit ? -1 : offset;
1630            if (offset > con.limit || offset < con.start)
1631                return -1;
1632            switch (op.type) {
1633            case Op.CHAR:
1634                if (isSet(opts, IGNORE_CASE)) {
1635                    int ch = op.getData();
1636                    if (dx > 0) {
1637                        if (offset >= con.limit || !matchIgnoreCase(ch, target .charAt( offset ) ))
1638                            return -1;
1639                        offset ++;
1640                    } else {
1641                        int o1 = offset-1;
1642                        if (o1 >= con.limit || o1 < 0 || !matchIgnoreCase(ch, target .charAt( o1 ) ))
1643                            return -1;
1644                        offset = o1;
1645                    }
1646                } else {
1647                    int ch = op.getData();
1648                    if (dx > 0) {
1649                        if (offset >= con.limit || ch != target .charAt( offset ) )
1650                            return -1;
1651                        offset ++;
1652                    } else {
1653                        int o1 = offset-1;
1654                        if (o1 >= con.limit || o1 < 0 || ch != target .charAt( o1 ) )
1655                            return -1;
1656                        offset = o1;
1657                    }
1658                }
1659                op = op.next;
1660                break;
1661
1662            case Op.DOT:
1663                if (dx > 0) {
1664                    if (offset >= con.limit)
1665                        return -1;
1666                    int ch = target .charAt( offset ) ;
1667                    if (isSet(opts, SINGLE_LINE)) {
1668                        if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
1669                            offset ++;
1670                    } else {
1671                        if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
1672                            ch = REUtil.composeFromSurrogates(ch, target .charAt( ++offset ) );
1673                        if (isEOLChar(ch))
1674                            return -1;
1675                    }
1676                    offset ++;
1677                } else {
1678                    int o1 = offset-1;
1679                    if (o1 >= con.limit || o1 < 0)
1680                        return -1;
1681                    int ch = target .charAt( o1 ) ;
1682                    if (isSet(opts, SINGLE_LINE)) {
1683                        if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
1684                            o1 --;
1685                    } else {
1686                        if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
1687                            ch = REUtil.composeFromSurrogates( target .charAt( --o1 ) , ch);
1688                        if (!isEOLChar(ch))
1689                            return -1;
1690                    }
1691                    offset = o1;
1692                }
1693                op = op.next;
1694                break;
1695
1696            case Op.RANGE:
1697            case Op.NRANGE:
1698                if (dx > 0) {
1699                    if (offset >= con.limit)
1700                        return -1;
1701                    int ch = target .charAt( offset ) ;
1702                    if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
1703                        ch = REUtil.composeFromSurrogates(ch, target .charAt( ++offset ) );
1704                    RangeToken tok = op.getToken();
1705                    if (isSet(opts, IGNORE_CASE)) {
1706                        tok = tok.getCaseInsensitiveToken();
1707                        if (!tok.match(ch)) {
1708                            if (ch >= 0x10000) return -1;
1709                            char uch;
1710                            if (!tok.match(uch = Character.toUpperCase((char)ch))
1711                                && !tok.match(Character.toLowerCase(uch)))
1712                                return -1;
1713                        }
1714                    } else {
1715                        if (!tok.match(ch)) return -1;
1716                    }
1717                    offset ++;
1718                } else {
1719                    int o1 = offset-1;
1720                    if (o1 >= con.limit || o1 < 0)
1721                        return -1;
1722                    int ch = target .charAt( o1 ) ;
1723                    if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
1724                        ch = REUtil.composeFromSurrogates( target .charAt( --o1 ) , ch);
1725                    RangeToken tok = op.getToken();
1726                    if (isSet(opts, IGNORE_CASE)) {
1727                        tok = tok.getCaseInsensitiveToken();
1728                        if (!tok.match(ch)) {
1729                            if (ch >= 0x10000) return -1;
1730                            char uch;
1731                            if (!tok.match(uch = Character.toUpperCase((char)ch))
1732                                && !tok.match(Character.toLowerCase(uch)))
1733                                return -1;
1734                        }
1735                    } else {
1736                        if (!tok.match(ch)) return -1;
1737                    }
1738                    offset = o1;
1739                }
1740                op = op.next;
1741                break;
1742
1743            case Op.ANCHOR:
1744                boolean go = false;
1745                switch (op.getData()) {
1746                case '^':
1747                    if (isSet(opts, MULTIPLE_LINES)) {
1748                        if (!(offset == con.start
1749                              || offset > con.start && isEOLChar( target .charAt( offset-1 ) )))
1750                            return -1;
1751                    } else {
1752                        if (offset != con.start)
1753                            return -1;
1754                    }
1755                    break;
1756
1757                case '@': // Internal use only.
1758
// The @ always matches line beginnings.
1759
if (!(offset == con.start
1760                          || offset > con.start && isEOLChar( target .charAt( offset-1 ) )))
1761                        return -1;
1762                    break;
1763
1764                case '$':
1765                    if (isSet(opts, MULTIPLE_LINES)) {
1766                        if (!(offset == con.limit
1767                              || offset < con.limit && isEOLChar( target .charAt( offset ) )))
1768                            return -1;
1769                    } else {
1770                        if (!(offset == con.limit
1771                              || offset+1 == con.limit && isEOLChar( target .charAt( offset ) )
1772                              || offset+2 == con.limit && target .charAt( offset ) == CARRIAGE_RETURN
1773                              && target .charAt( offset+1 ) == LINE_FEED))
1774                            return -1;
1775                    }
1776                    break;
1777
1778                case 'A':
1779                    if (offset != con.start) return -1;
1780                    break;
1781
1782                case 'Z':
1783                    if (!(offset == con.limit
1784                          || offset+1 == con.limit && isEOLChar( target .charAt( offset ) )
1785                          || offset+2 == con.limit && target .charAt( offset ) == CARRIAGE_RETURN
1786                          && target .charAt( offset+1 ) == LINE_FEED))
1787                        return -1;
1788                    break;
1789
1790                case 'z':
1791                    if (offset != con.limit) return -1;
1792                    break;
1793
1794                case 'b':
1795                    if (con.length == 0) return -1;
1796                    {
1797                        int after = getWordType(target, con.start, con.limit, offset, opts);
1798                        if (after == WT_IGNORE) return -1;
1799                        int before = getPreviousWordType(target, con.start, con.limit, offset, opts);
1800                        if (after == before) return -1;
1801                    }
1802                    break;
1803
1804                case 'B':
1805                    if (con.length == 0)
1806                        go = true;
1807                    else {
1808                        int after = getWordType(target, con.start, con.limit, offset, opts);
1809                        go = after == WT_IGNORE
1810                             || after == getPreviousWordType(target, con.start, con.limit, offset, opts);
1811                    }
1812                    if (!go) return -1;
1813                    break;
1814
1815                case '<':
1816                    if (con.length == 0 || offset == con.limit) return -1;
1817                    if (getWordType(target, con.start, con.limit, offset, opts) != WT_LETTER
1818                        || getPreviousWordType(target, con.start, con.limit, offset, opts) != WT_OTHER)
1819                        return -1;
1820                    break;
1821
1822                case '>':
1823                    if (con.length == 0 || offset == con.start) return -1;
1824                    if (getWordType(target, con.start, con.limit, offset, opts) != WT_OTHER
1825                        || getPreviousWordType(target, con.start, con.limit, offset, opts) != WT_LETTER)
1826                        return -1;
1827                    break;
1828                } // switch anchor type
1829
op = op.next;
1830                break;
1831
1832            case Op.BACKREFERENCE:
1833                {
1834                    int refno = op.getData();
1835                    if (refno <= 0 || refno >= this.nofparen)
1836                        throw new RuntimeException JavaDoc("Internal Error: Reference number must be more than zero: "+refno);
1837                    if (con.match.getBeginning(refno) < 0
1838                        || con.match.getEnd(refno) < 0)
1839                        return -1; // ********
1840
int o2 = con.match.getBeginning(refno);
1841                    int literallen = con.match.getEnd(refno)-o2;
1842                    if (!isSet(opts, IGNORE_CASE)) {
1843                        if (dx > 0) {
1844                            if (!regionMatches(target, offset, con.limit, o2, literallen))
1845                                return -1;
1846                            offset += literallen;
1847                        } else {
1848                            if (!regionMatches(target, offset-literallen, con.limit, o2, literallen))
1849                                return -1;
1850                            offset -= literallen;
1851                        }
1852                    } else {
1853                        if (dx > 0) {
1854                            if (!regionMatchesIgnoreCase(target, offset, con.limit, o2, literallen))
1855                                return -1;
1856                            offset += literallen;
1857                        } else {
1858                            if (!regionMatchesIgnoreCase(target, offset-literallen, con.limit,
1859                                                         o2, literallen))
1860                                return -1;
1861                            offset -= literallen;
1862                        }
1863                    }
1864                }
1865                op = op.next;
1866                break;
1867            case Op.STRING:
1868                {
1869                    String JavaDoc literal = op.getString();
1870                    int literallen = literal.length();
1871                    if (!isSet(opts, IGNORE_CASE)) {
1872                        if (dx > 0) {
1873                            if (!regionMatches(target, offset, con.limit, literal, literallen))
1874                                return -1;
1875                            offset += literallen;
1876                        } else {
1877                            if (!regionMatches(target, offset-literallen, con.limit, literal, literallen))
1878                                return -1;
1879                            offset -= literallen;
1880                        }
1881                    } else {
1882                        if (dx > 0) {
1883                            if (!regionMatchesIgnoreCase(target, offset, con.limit, literal, literallen))
1884                                return -1;
1885                            offset += literallen;
1886                        } else {
1887                            if (!regionMatchesIgnoreCase(target, offset-literallen, con.limit,
1888                                                         literal, literallen))
1889                                return -1;
1890                            offset -= literallen;
1891                        }
1892                    }
1893                }
1894                op = op.next;
1895                break;
1896
1897            case Op.CLOSURE:
1898                {
1899                    /*
1900                     * Saves current position to avoid
1901                     * zero-width repeats.
1902                     */

1903                    int id = op.getData();
1904                    if (id >= 0) {
1905                        int previousOffset = con.offsets[id];
1906                        if (previousOffset < 0 || previousOffset != offset) {
1907                            con.offsets[id] = offset;
1908                        } else {
1909                            con.offsets[id] = -1;
1910                            op = op.next;
1911                            break;
1912                        }
1913                    }
1914                    int ret = this. matchString (con, op.getChild(), offset, dx, opts);
1915                    if (id >= 0) con.offsets[id] = -1;
1916                    if (ret >= 0) return ret;
1917                    op = op.next;
1918                }
1919                break;
1920
1921            case Op.QUESTION:
1922                {
1923                    int ret = this. matchString (con, op.getChild(), offset, dx, opts);
1924                    if (ret >= 0) return ret;
1925                    op = op.next;
1926                }
1927                break;
1928
1929            case Op.NONGREEDYCLOSURE:
1930            case Op.NONGREEDYQUESTION:
1931                {
1932                    int ret = this. matchString (con, op.next, offset, dx, opts);
1933                    if (ret >= 0) return ret;
1934                    op = op.getChild();
1935                }
1936                break;
1937
1938            case Op.UNION:
1939                for (int i = 0; i < op.size(); i ++) {
1940                    int ret = this. matchString (con, op.elementAt(i), offset, dx, opts);
1941                    if (DEBUG) {
1942                        System.err.println("UNION: "+i+", ret="+ret);
1943                    }
1944                    if (ret >= 0) return ret;
1945                }
1946                return -1;
1947
1948            case Op.CAPTURE:
1949                int refno = op.getData();
1950                if (con.match != null && refno > 0) {
1951                    int save = con.match.getBeginning(refno);
1952                    con.match.setBeginning(refno, offset);
1953                    int ret = this. matchString (con, op.next, offset, dx, opts);
1954                    if (ret < 0) con.match.setBeginning(refno, save);
1955                    return ret;
1956                } else if (con.match != null && refno < 0) {
1957                    int index = -refno;
1958                    int save = con.match.getEnd(index);
1959                    con.match.setEnd(index, offset);
1960                    int ret = this. matchString (con, op.next, offset, dx, opts);
1961                    if (ret < 0) con.match.setEnd(index, save);
1962                    return ret;
1963                }
1964                op = op.next;
1965                break;
1966
1967            case Op.LOOKAHEAD:
1968                if (0 > this. matchString (con, op.getChild(), offset, 1, opts)) return -1;
1969                op = op.next;
1970                break;
1971            case Op.NEGATIVELOOKAHEAD:
1972                if (0 <= this. matchString (con, op.getChild(), offset, 1, opts)) return -1;
1973                op = op.next;
1974                break;
1975            case Op.LOOKBEHIND:
1976                if (0 > this. matchString (con, op.getChild(), offset, -1, opts)) return -1;
1977                op = op.next;
1978                break;
1979            case Op.NEGATIVELOOKBEHIND:
1980                if (0 <= this. matchString (con, op.getChild(), offset, -1, opts)) return -1;
1981                op = op.next;
1982                break;
1983
1984            case Op.INDEPENDENT:
1985                {
1986                    int ret = this. matchString (con, op.getChild(), offset, dx, opts);
1987                    if (ret < 0) return ret;
1988                    offset = ret;
1989                    op = op.next;
1990                }
1991                break;
1992
1993            case Op.MODIFIER:
1994                {
1995                    int localopts = opts;
1996                    localopts |= op.getData();
1997                    localopts &= ~op.getData2();
1998                    //System.err.println("MODIFIER: "+Integer.toString(opts, 16)+" -> "+Integer.toString(localopts, 16));
1999
int ret = this. matchString (con, op.getChild(), offset, dx, localopts);
2000                    if (ret < 0) return ret;
2001                    offset = ret;
2002                    op = op.next;
2003                }
2004                break;
2005
2006            case Op.CONDITION:
2007                {
2008                    Op.ConditionOp cop = (Op.ConditionOp)op;
2009                    boolean matchp = false;
2010                    if (cop.refNumber > 0) {
2011                        if (cop.refNumber >= this.nofparen)
2012                            throw new RuntimeException JavaDoc("Internal Error: Reference number must be more than zero: "+cop.refNumber);
2013                        matchp = con.match.getBeginning(cop.refNumber) >= 0
2014                                 && con.match.getEnd(cop.refNumber) >= 0;
2015                    } else {
2016                        matchp = 0 <= this. matchString (con, cop.condition, offset, dx, opts);
2017                    }
2018
2019                    if (matchp) {
2020                        op = cop.yes;
2021                    } else if (cop.no != null) {
2022                        op = cop.no;
2023                    } else {
2024                        op = cop.next;
2025                    }
2026                }
2027                break;
2028
2029            default:
2030                throw new RuntimeException JavaDoc("Unknown operation type: "+op.type);
2031            } // switch (op.type)
2032
} // while
2033
}
2034
2035    private static final int getPreviousWordType(String JavaDoc target, int begin, int end,
2036                                                 int offset, int opts) {
2037        int ret = getWordType(target, begin, end, --offset, opts);
2038        while (ret == WT_IGNORE)
2039            ret = getWordType(target, begin, end, --offset, opts);
2040        return ret;
2041    }
2042
2043    private static final int getWordType(String JavaDoc target, int begin, int end,
2044                                         int offset, int opts) {
2045        if (offset < begin || offset >= end) return WT_OTHER;
2046        return getWordType0( target .charAt( offset ) , opts);
2047    }
2048
2049
2050    private static final boolean regionMatches(String JavaDoc text, int offset, int limit,
2051                                               String JavaDoc part, int partlen) {
2052        if (limit-offset < partlen) return false;
2053        return text.regionMatches(offset, part, 0, partlen);
2054    }
2055
2056    private static final boolean regionMatches(String JavaDoc text, int offset, int limit,
2057                                               int offset2, int partlen) {
2058        if (limit-offset < partlen) return false;
2059        return text.regionMatches(offset, text, offset2, partlen);
2060    }
2061
2062    private static final boolean regionMatchesIgnoreCase(String JavaDoc text, int offset, int limit,
2063                                                         String JavaDoc part, int partlen) {
2064        return text.regionMatches(true, offset, part, 0, partlen);
2065    }
2066
2067    private static final boolean regionMatchesIgnoreCase(String JavaDoc text, int offset, int limit,
2068                                                         int offset2, int partlen) {
2069        if (limit-offset < partlen) return false;
2070        return text.regionMatches(true, offset, text, offset2, partlen);
2071    }
2072
2073
2074
2075
2076
2077
2078
2079    /**
2080     * Checks whether the <var>target</var> text <strong>contains</strong> this pattern or not.
2081     *
2082     * @return true if the target is matched to this regular expression.
2083     */

2084    public boolean matches(CharacterIterator JavaDoc target) {
2085        return this.matches(target, (Match)null);
2086    }
2087
2088
2089    /**
2090     * Checks whether the <var>target</var> text <strong>contains</strong> this pattern or not.
2091     *
2092     * @param match A Match instance for storing matching result.
2093     * @return Offset of the start position in <VAR>target</VAR>; or -1 if not match.
2094     */

2095    public boolean matches(CharacterIterator JavaDoc target, Match match) {
2096        int start = target.getBeginIndex();
2097        int end = target.getEndIndex();
2098
2099
2100
2101        synchronized (this) {
2102            if (this.operations == null)
2103                this.prepare();
2104            if (this.context == null)
2105                this.context = new Context();
2106        }
2107        Context con = null;
2108        synchronized (this.context) {
2109            con = this.context.inuse ? new Context() : this.context;
2110            con.reset(target, start, end, this.numberOfClosures);
2111        }
2112        if (match != null) {
2113            match.setNumberOfGroups(this.nofparen);
2114            match.setSource(target);
2115        } else if (this.hasBackReferences) {
2116            match = new Match();
2117            match.setNumberOfGroups(this.nofparen);
2118            // Need not to call setSource() because
2119
// a caller can not access this match instance.
2120
}
2121        con.match = match;
2122
2123        if (RegularExpression.isSet(this.options, XMLSCHEMA_MODE)) {
2124            int matchEnd = this. matchCharacterIterator (con, this.operations, con.start, 1, this.options);
2125            //System.err.println("DEBUG: matchEnd="+matchEnd);
2126
if (matchEnd == con.limit) {
2127                if (con.match != null) {
2128                    con.match.setBeginning(0, con.start);
2129                    con.match.setEnd(0, matchEnd);
2130                }
2131                con.inuse = false;
2132                return true;
2133            }
2134            return false;
2135        }
2136
2137        /*
2138         * The pattern has only fixed string.
2139         * The engine uses Boyer-Moore.
2140         */

2141        if (this.fixedStringOnly) {
2142            //System.err.println("DEBUG: fixed-only: "+this.fixedString);
2143
int o = this.fixedStringTable.matches(target, con.start, con.limit);
2144            if (o >= 0) {
2145                if (con.match != null) {
2146                    con.match.setBeginning(0, o);
2147                    con.match.setEnd(0, o+this.fixedString.length());
2148                }
2149                con.inuse = false;
2150                return true;
2151            }
2152            con.inuse = false;
2153            return false;
2154        }
2155
2156        /*
2157         * The pattern contains a fixed string.
2158         * The engine checks with Boyer-Moore whether the text contains the fixed string or not.
2159         * If not, it return with false.
2160         */

2161        if (this.fixedString != null) {
2162            int o = this.fixedStringTable.matches(target, con.start, con.limit);
2163            if (o < 0) {
2164                //System.err.println("Non-match in fixed-string search.");
2165
con.inuse = false;
2166                return false;
2167            }
2168        }
2169
2170        int limit = con.limit-this.minlength;
2171        int matchStart;
2172        int matchEnd = -1;
2173
2174        /*
2175         * Checks whether the expression starts with ".*".
2176         */

2177        if (this.operations != null
2178            && this.operations.type == Op.CLOSURE && this.operations.getChild().type == Op.DOT) {
2179            if (isSet(this.options, SINGLE_LINE)) {
2180                matchStart = con.start;
2181                matchEnd = this. matchCharacterIterator (con, this.operations, con.start, 1, this.options);
2182            } else {
2183                boolean previousIsEOL = true;
2184                for (matchStart = con.start; matchStart <= limit; matchStart ++) {
2185                    int ch = target .setIndex( matchStart ) ;
2186                    if (isEOLChar(ch)) {
2187                        previousIsEOL = true;
2188                    } else {
2189                        if (previousIsEOL) {
2190                            if (0 <= (matchEnd = this. matchCharacterIterator (con, this.operations,
2191                                                                               matchStart, 1, this.options)))
2192                                break;
2193                        }
2194                        previousIsEOL = false;
2195                    }
2196                }
2197            }
2198        }
2199
2200        /*
2201         * Optimization against the first character.
2202         */

2203        else if (this.firstChar != null) {
2204            //System.err.println("DEBUG: with firstchar-matching: "+this.firstChar);
2205
RangeToken range = this.firstChar;
2206            if (RegularExpression.isSet(this.options, IGNORE_CASE)) {
2207                range = this.firstChar.getCaseInsensitiveToken();
2208                for (matchStart = con.start; matchStart <= limit; matchStart ++) {
2209                    int ch = target .setIndex( matchStart ) ;
2210                    if (REUtil.isHighSurrogate(ch) && matchStart+1 < con.limit) {
2211                        ch = REUtil.composeFromSurrogates(ch, target .setIndex( matchStart+1 ) );
2212                        if (!range.match(ch)) continue;
2213                    } else {
2214                        if (!range.match(ch)) {
2215                            char ch1 = Character.toUpperCase((char)ch);
2216                            if (!range.match(ch1))
2217                                if (!range.match(Character.toLowerCase(ch1)))
2218                                    continue;
2219                        }
2220                    }
2221                    if (0 <= (matchEnd = this. matchCharacterIterator (con, this.operations,
2222                                                                       matchStart, 1, this.options)))
2223                        break;
2224                }
2225            } else {
2226                for (matchStart = con.start; matchStart <= limit; matchStart ++) {
2227                    int ch = target .setIndex( matchStart ) ;
2228                    if (REUtil.isHighSurrogate(ch) && matchStart+1 < con.limit)
2229                        ch = REUtil.composeFromSurrogates(ch, target .setIndex( matchStart+1 ) );
2230                    if (!range.match(ch)) continue;
2231                    if (0 <= (matchEnd = this. matchCharacterIterator (con, this.operations,
2232                                                                       matchStart, 1, this.options)))
2233                        break;
2234                }
2235            }
2236        }
2237
2238        /*
2239         * Straightforward matching.
2240         */

2241        else {
2242            for (matchStart = con.start; matchStart <= limit; matchStart ++) {
2243                if (0 <= (matchEnd = this. matchCharacterIterator (con, this.operations, matchStart, 1, this.options)))
2244                    break;
2245            }
2246        }
2247
2248        if (matchEnd >= 0) {
2249            if (con.match != null) {
2250                con.match.setBeginning(0, matchStart);
2251                con.match.setEnd(0, matchEnd);
2252            }
2253            con.inuse = false;
2254            return true;
2255        } else {
2256            con.inuse = false;
2257            return false;
2258        }
2259    }
2260
2261    /**
2262     * @return -1 when not match; offset of the end of matched string when match.
2263     */

2264    private int matchCharacterIterator (Context con, Op op, int offset, int dx, int opts) {
2265
2266
2267        CharacterIterator JavaDoc target = con.ciTarget;
2268
2269
2270
2271
2272
2273
2274        while (true) {
2275            if (op == null)
2276                return isSet(opts, XMLSCHEMA_MODE) && offset != con.limit ? -1 : offset;
2277            if (offset > con.limit || offset < con.start)
2278                return -1;
2279            switch (op.type) {
2280            case Op.CHAR:
2281                if (isSet(opts, IGNORE_CASE)) {
2282                    int ch = op.getData();
2283                    if (dx > 0) {
2284                        if (offset >= con.limit || !matchIgnoreCase(ch, target .setIndex( offset ) ))
2285                            return -1;
2286                        offset ++;
2287                    } else {
2288                        int o1 = offset-1;
2289                        if (o1 >= con.limit || o1 < 0 || !matchIgnoreCase(ch, target .setIndex( o1 ) ))
2290                            return -1;
2291                        offset = o1;
2292                    }
2293                } else {
2294                    int ch = op.getData();
2295                    if (dx > 0) {
2296                        if (offset >= con.limit || ch != target .setIndex( offset ) )
2297                            return -1;
2298                        offset ++;
2299                    } else {
2300                        int o1 = offset-1;
2301                        if (o1 >= con.limit || o1 < 0 || ch != target .setIndex( o1 ) )
2302                            return -1;
2303                        offset = o1;
2304                    }
2305                }
2306                op = op.next;
2307                break;
2308
2309            case Op.DOT:
2310                if (dx > 0) {
2311                    if (offset >= con.limit)
2312                        return -1;
2313                    int ch = target .setIndex( offset ) ;
2314                    if (isSet(opts, SINGLE_LINE)) {
2315                        if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
2316                            offset ++;
2317                    } else {
2318                        if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
2319                            ch = REUtil.composeFromSurrogates(ch, target .setIndex( ++offset ) );
2320                        if (isEOLChar(ch))
2321                            return -1;
2322                    }
2323                    offset ++;
2324                } else {
2325                    int o1 = offset-1;
2326                    if (o1 >= con.limit || o1 < 0)
2327                        return -1;
2328                    int ch = target .setIndex( o1 ) ;
2329                    if (isSet(opts, SINGLE_LINE)) {
2330                        if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
2331                            o1 --;
2332                    } else {
2333                        if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
2334                            ch = REUtil.composeFromSurrogates( target .setIndex( --o1 ) , ch);
2335                        if (!isEOLChar(ch))
2336                            return -1;
2337                    }
2338                    offset = o1;
2339                }
2340                op = op.next;
2341                break;
2342
2343            case Op.RANGE:
2344            case Op.NRANGE:
2345                if (dx > 0) {
2346                    if (offset >= con.limit)
2347                        return -1;
2348                    int ch = target .setIndex( offset ) ;
2349                    if (REUtil.isHighSurrogate(ch) && offset+1 < con.limit)
2350                        ch = REUtil.composeFromSurrogates(ch, target .setIndex( ++offset ) );
2351                    RangeToken tok = op.getToken();
2352                    if (isSet(opts, IGNORE_CASE)) {
2353                        tok = tok.getCaseInsensitiveToken();
2354                        if (!tok.match(ch)) {
2355                            if (ch >= 0x10000) return -1;
2356                            char uch;
2357                            if (!tok.match(uch = Character.toUpperCase((char)ch))
2358                                && !tok.match(Character.toLowerCase(uch)))
2359                                return -1;
2360                        }
2361                    } else {
2362                        if (!tok.match(ch)) return -1;
2363                    }
2364                    offset ++;
2365                } else {
2366                    int o1 = offset-1;
2367                    if (o1 >= con.limit || o1 < 0)
2368                        return -1;
2369                    int ch = target .setIndex( o1 ) ;
2370                    if (REUtil.isLowSurrogate(ch) && o1-1 >= 0)
2371                        ch = REUtil.composeFromSurrogates( target .setIndex( --o1 ) , ch);
2372                    RangeToken tok = op.getToken();
2373                    if (isSet(opts, IGNORE_CASE)) {
2374                        tok = tok.getCaseInsensitiveToken();
2375                        if (!tok.match(ch)) {
2376                            if (ch >= 0x10000) return -1;
2377                            char uch;
2378                            if (!tok.match(uch = Character.toUpperCase((char)ch))
2379                                && !tok.match(Character.toLowerCase(uch)))
2380                                return -1;
2381                        }
2382                    } else {
2383                        if (!tok.match(ch)) return -1;
2384                    }
2385                    offset = o1;
2386                }
2387                op = op.next;
2388                break;
2389
2390            case Op.ANCHOR:
2391                boolean go = false;
2392                switch (op.getData()) {
2393                case '^':
2394                    if (isSet(opts, MULTIPLE_LINES)) {
2395                        if (!(offset == con.start
2396                              || offset > con.start && isEOLChar( target .setIndex( offset-1 ) )))
2397                            return -1;
2398                    } else {
2399                        if (offset != con.start)
2400                            return -1;
2401                    }
2402                    break;
2403
2404                case '@': // Internal use only.
2405
// The @ always matches line beginnings.
2406
if (!(offset == con.start
2407                          || offset > con.start && isEOLChar( target .setIndex( offset-1 ) )))
2408                        return -1;
2409                    break;
2410
2411                case '$':
2412                    if (isSet(opts, MULTIPLE_LINES)) {
2413                        if (!(offset == con.limit
2414                              || offset < con.limit && isEOLChar( target .setIndex( offset ) )))
2415                            return -1;
2416                    } else {
2417                        if (!(offset == con.limit
2418                              || offset+1 == con.limit && isEOLChar( target .setIndex( offset ) )
2419                              || offset+2 == con.limit && target .setIndex( offset ) == CARRIAGE_RETURN
2420                              && target .setIndex( offset+1 ) == LINE_FEED))
2421                            return -1;
2422                    }
2423                    break;
2424
2425                case 'A':
2426                    if (offset != con.start) return -1;
2427                    break;
2428
2429                case 'Z':
2430                    if (!(offset == con.limit
2431                          || offset+1 == con.limit && isEOLChar( target .setIndex( offset ) )
2432                          || offset+2 == con.limit && target .setIndex( offset ) == CARRIAGE_RETURN
2433                          && target .setIndex( offset+1 ) == LINE_FEED))
2434                        return -1;
2435                    break;
2436
2437                case 'z':
2438                    if (offset != con.limit) return -1;
2439                    break;
2440
2441                case 'b':
2442                    if (con.length == 0) return -1;
2443                    {
2444                        int after = getWordType(target, con.start, con.limit, offset, opts);
2445                        if (after == WT_IGNORE) return -1;
2446                        int before = getPreviousWordType(target, con.start, con.limit, offset, opts);
2447                        if (after == before) return -1;
2448                    }
2449                    break;
2450
2451                case 'B':
2452                    if (con.length == 0)
2453                        go = true;
2454                    else {
2455                        int after = getWordType(target, con.start, con.limit, offset, opts);
2456                        go = after == WT_IGNORE
2457                             || after == getPreviousWordType(target, con.start, con.limit, offset, opts);
2458                    }
2459                    if (!go) return -1;
2460                    break;
2461
2462                case '<':
2463                    if (con.length == 0 || offset == con.limit) return -1;
2464                    if (getWordType(target, con.start, con.limit, offset, opts) != WT_LETTER
2465                        || getPreviousWordType(target, con.start, con.limit, offset, opts) != WT_OTHER)
2466                        return -1;
2467                    break;
2468
2469                case '>':
2470                    if (con.length == 0 || offset == con.start) return -1;
2471                    if (getWordType(target, con.start, con.limit, offset, opts) != WT_OTHER
2472                        || getPreviousWordType(target, con.start, con.limit, offset, opts) != WT_LETTER)
2473                        return -1;
2474                    break;
2475                } // switch anchor type
2476
op = op.next;
2477                break;
2478
2479            case Op.BACKREFERENCE:
2480                {
2481                    int refno = op.getData();
2482                    if (refno <= 0 || refno >= this.nofparen)
2483                        throw new RuntimeException JavaDoc("Internal Error: Reference number must be more than zero: "+refno);
2484                    if (con.match.getBeginning(refno) < 0
2485                        || con.match.getEnd(refno) < 0)
2486                        return -1; // ********
2487
int o2 = con.match.getBeginning(refno);
2488                    int literallen = con.match.getEnd(refno)-o2;
2489                    if (!isSet(opts, IGNORE_CASE)) {
2490                        if (dx > 0) {
2491                            if (!regionMatches(target, offset, con.limit, o2, literallen))
2492                                return -1;
2493                            offset += literallen;
2494                        } else {
2495                            if (!regionMatches(target, offset-literallen, con.limit, o2, literallen))
2496                                return -1;
2497                            offset -= literallen;
2498                        }
2499                    } else {
2500                        if (dx > 0) {
2501                            if (!regionMatchesIgnoreCase(target, offset, con.limit, o2, literallen))
2502                                return -1;
2503                            offset += literallen;
2504                        } else {
2505                            if (!regionMatchesIgnoreCase(target, offset-literallen, con.limit,
2506                                                         o2, literallen))
2507                                return -1;
2508                            offset -= literallen;
2509                        }
2510                    }
2511                }
2512                op = op.next;
2513                break;
2514            case Op.STRING:
2515                {
2516                    String JavaDoc literal = op.getString();
2517                    int literallen = literal.length();
2518                    if (!isSet(opts, IGNORE_CASE)) {
2519                        if (dx > 0) {
2520                            if (!regionMatches(target, offset, con.limit, literal, literallen))
2521                                return -1;
2522                            offset += literallen;
2523                        } else {
2524                            if (!regionMatches(target, offset-literallen, con.limit, literal, literallen))
2525                                return -1;
2526                            offset -= literallen;
2527                        }
2528                    } else {
2529                        if (dx > 0) {
2530                            if (!regionMatchesIgnoreCase(target, offset, con.limit, literal, literallen))
2531                                return -1;
2532                            offset += literallen;
2533                        } else {
2534                            if (!regionMatchesIgnoreCase(target, offset-literallen, con.limit,
2535                                                         literal, literallen))
2536                                return -1;
2537                            offset -= literallen;
2538                        }
2539                    }
2540                }
2541                op = op.next;
2542                break;
2543
2544            case Op.CLOSURE:
2545                {
2546                    /*
2547                     * Saves current position to avoid
2548                     * zero-width repeats.
2549                     */

2550                    int id = op.getData();
2551                    if (id >= 0) {
2552                        int previousOffset = con.offsets[id];
2553                        if (previousOffset < 0 || previousOffset != offset) {
2554                            con.offsets[id] = offset;
2555                        } else {
2556                            con.offsets[id] = -1;
2557                            op = op.next;
2558                            break;
2559                        }
2560                    }
2561                    
2562                    int ret = this. matchCharacterIterator (con, op.getChild(), offset, dx, opts);
2563                    if (id >= 0) con.offsets[id] = -1;
2564                    if (ret >= 0) return ret;
2565                    op = op.next;
2566                }
2567                break;
2568
2569            case Op.QUESTION:
2570                {
2571                    int ret = this. matchCharacterIterator (con, op.getChild(), offset, dx, opts);
2572                    if (ret >= 0) return ret;
2573                    op = op.next;
2574                }
2575                break;
2576
2577            case Op.NONGREEDYCLOSURE:
2578            case Op.NONGREEDYQUESTION:
2579                {
2580                    int ret = this. matchCharacterIterator (con, op.next, offset, dx, opts);
2581                    if (ret >= 0) return ret;
2582                    op = op.getChild();
2583                }
2584                break;
2585
2586            case Op.UNION:
2587                for (int i = 0; i < op.size(); i ++) {
2588                    int ret = this. matchCharacterIterator (con, op.elementAt(i), offset, dx, opts);
2589                    if (DEBUG) {
2590                        System.err.println("UNION: "+i+", ret="+ret);
2591                    }
2592                    if (ret >= 0) return ret;
2593                }
2594                return -1;
2595
2596            case Op.CAPTURE:
2597                int refno = op.getData();
2598                if (con.match != null && refno > 0) {
2599                    int save = con.match.getBeginning(refno);
2600                    con.match.setBeginning(refno, offset);
2601                    int ret = this. matchCharacterIterator (con, op.next, offset, dx, opts);
2602                    if (ret < 0) con.match.setBeginning(refno, save);
2603                    return ret;
2604                } else if (con.match != null && refno < 0) {
2605                    int index = -refno;
2606                    int save = con.match.getEnd(index);
2607                    con.match.setEnd(index, offset);
2608                    int ret = this. matchCharacterIterator (con, op.next, offset, dx, opts);
2609                    if (ret < 0) con.match.setEnd(index, save);
2610                    return ret;
2611                }
2612                op = op.next;
2613                break;
2614
2615            case Op.LOOKAHEAD:
2616                if (0 > this. matchCharacterIterator (con, op.getChild(), offset, 1, opts)) return -1;
2617                op = op.next;
2618                break;
2619            case Op.NEGATIVELOOKAHEAD:
2620                if (0 <= this. matchCharacterIterator (con, op.getChild(), offset, 1, opts)) return -1;
2621                op = op.next;
2622                break;
2623            case Op.LOOKBEHIND:
2624                if (0 > this. matchCharacterIterator (con, op.getChild(), offset, -1, opts)) return -1;
2625                op = op.next;
2626                break;
2627            case Op.NEGATIVELOOKBEHIND:
2628                if (0 <= this. matchCharacterIterator (con, op.getChild(), offset, -1, opts)) return -1;
2629                op = op.next;
2630                break;
2631
2632            case Op.INDEPENDENT:
2633                {
2634                    int ret = this. matchCharacterIterator (con, op.getChild(), offset, dx, opts);
2635                    if (ret < 0) return ret;
2636                    offset = ret;
2637                    op = op.next;
2638                }
2639                break;
2640
2641            case Op.MODIFIER:
2642                {
2643                    int localopts = opts;
2644                    localopts |= op.getData();
2645                    localopts &= ~op.getData2();
2646                    //System.err.println("MODIFIER: "+Integer.toString(opts, 16)+" -> "+Integer.toString(localopts, 16));
2647
int ret = this. matchCharacterIterator (con, op.getChild(), offset, dx, localopts);
2648                    if (ret < 0) return ret;
2649                    offset = ret;
2650                    op = op.next;
2651                }
2652                break;
2653
2654            case Op.CONDITION:
2655                {
2656                    Op.ConditionOp cop = (Op.ConditionOp)op;
2657                    boolean matchp = false;
2658                    if (cop.refNumber > 0) {
2659                        if (cop.refNumber >= this.nofparen)
2660                            throw new RuntimeException JavaDoc("Internal Error: Reference number must be more than zero: "+cop.refNumber);
2661                        matchp = con.match.getBeginning(cop.refNumber) >= 0
2662                                 && con.match.getEnd(cop.refNumber) >= 0;
2663                    } else {
2664                        matchp = 0 <= this. matchCharacterIterator (con, cop.condition, offset, dx, opts);
2665                    }
2666
2667                    if (matchp) {
2668                        op = cop.yes;
2669                    } else if (cop.no != null) {
2670                        op = cop.no;
2671                    } else {
2672                        op = cop.next;
2673                    }
2674                }
2675                break;
2676
2677            default:
2678                throw new RuntimeException JavaDoc("Unknown operation type: "+op.type);
2679            } // switch (op.type)
2680
} // while
2681
}
2682
2683    private static final int getPreviousWordType(CharacterIterator JavaDoc target, int begin, int end,
2684                                                 int offset, int opts) {
2685        int ret = getWordType(target, begin, end, --offset, opts);
2686        while (ret == WT_IGNORE)
2687            ret = getWordType(target, begin, end, --offset, opts);
2688        return ret;
2689    }
2690
2691    private static final int getWordType(CharacterIterator JavaDoc target, int begin, int end,
2692                                         int offset, int opts) {
2693        if (offset < begin || offset >= end) return WT_OTHER;
2694        return getWordType0( target .setIndex( offset ) , opts);
2695    }
2696
2697
2698
2699    private static final boolean regionMatches(CharacterIterator JavaDoc target, int offset, int limit,
2700                                               String JavaDoc part, int partlen) {
2701        if (offset < 0) return false;
2702        if (limit-offset < partlen)
2703            return false;
2704        int i = 0;
2705        while (partlen-- > 0) {
2706            if ( target .setIndex( offset++ ) != part.charAt(i++))
2707                return false;
2708        }
2709        return true;
2710    }
2711
2712    private static final boolean regionMatches(CharacterIterator JavaDoc target, int offset, int limit,
2713                                               int offset2, int partlen) {
2714        if (offset < 0) return false;
2715        if (limit-offset < partlen)
2716            return false;
2717        int i = offset2;
2718        while (partlen-- > 0) {
2719            if ( target .setIndex( offset++ ) != target .setIndex( i++ ) )
2720                return false;
2721        }
2722        return true;
2723    }
2724
2725    /**
2726     * @see java.lang.String#regionMatches
2727     */

2728    private static final boolean regionMatchesIgnoreCase(CharacterIterator JavaDoc target, int offset, int limit,
2729                                                         String JavaDoc part, int partlen) {
2730        if (offset < 0) return false;
2731        if (limit-offset < partlen)
2732            return false;
2733        int i = 0;
2734        while (partlen-- > 0) {
2735            char ch1 = target .setIndex( offset++ ) ;
2736            char ch2 = part.charAt(i++);
2737            if (ch1 == ch2)
2738                continue;
2739            char uch1 = Character.toUpperCase(ch1);
2740            char uch2 = Character.toUpperCase(ch2);
2741            if (uch1 == uch2)
2742                continue;
2743            if (Character.toLowerCase(uch1) != Character.toLowerCase(uch2))
2744                return false;
2745        }
2746        return true;
2747    }
2748
2749    private static final boolean regionMatchesIgnoreCase(CharacterIterator JavaDoc target, int offset, int limit,
2750                                                         int offset2, int partlen) {
2751        if (offset < 0) return false;
2752        if (limit-offset < partlen)
2753            return false;
2754        int i = offset2;
2755        while (partlen-- > 0) {
2756            char ch1 = target .setIndex( offset++ ) ;
2757            char ch2 = target .setIndex( i++ ) ;
2758            if (ch1 == ch2)
2759                continue;
2760            char uch1 = Character.toUpperCase(ch1);
2761            char uch2 = Character.toUpperCase(ch2);
2762            if (uch1 == uch2)
2763                continue;
2764            if (Character.toLowerCase(uch1) != Character.toLowerCase(uch2))
2765                return false;
2766        }
2767        return true;
2768    }
2769
2770
2771
2772
2773    // ================================================================
2774

2775    /**
2776     * A regular expression.
2777     * @serial
2778     */

2779    String JavaDoc regex;
2780    /**
2781     * @serial
2782     */

2783    int options;
2784
2785    /**
2786     * The number of parenthesis in the regular expression.
2787     * @serial
2788     */

2789    int nofparen;
2790    /**
2791     * Internal representation of the regular expression.
2792     * @serial
2793     */

2794    Token tokentree;
2795
2796    boolean hasBackReferences = false;
2797
2798    transient int minlength;
2799    transient Op operations = null;
2800    transient int numberOfClosures;
2801    transient Context context = null;
2802    transient RangeToken firstChar = null;
2803
2804    transient String JavaDoc fixedString = null;
2805    transient int fixedStringOptions;
2806    transient BMPattern fixedStringTable = null;
2807    transient boolean fixedStringOnly = false;
2808
2809
2810    static final class Context {
2811        CharacterIterator JavaDoc ciTarget;
2812        String JavaDoc strTarget;
2813        char[] charTarget;
2814        int start;
2815        int limit;
2816        int length;
2817        Match match;
2818        boolean inuse = false;
2819        int[] offsets;
2820
2821        Context() {
2822        }
2823
2824        private void resetCommon(int nofclosures) {
2825            this.length = this.limit-this.start;
2826            this.inuse = true;
2827            this.match = null;
2828            if (this.offsets == null || this.offsets.length != nofclosures)
2829                this.offsets = new int[nofclosures];
2830            for (int i = 0; i < nofclosures; i ++) this.offsets[i] = -1;
2831        }
2832        void reset(CharacterIterator JavaDoc target, int start, int limit, int nofclosures) {
2833            this.ciTarget = target;
2834            this.start = start;
2835            this.limit = limit;
2836            this.resetCommon(nofclosures);
2837        }
2838        void reset(String JavaDoc target, int start, int limit, int nofclosures) {
2839            this.strTarget = target;
2840            this.start = start;
2841            this.limit = limit;
2842            this.resetCommon(nofclosures);
2843        }
2844        void reset(char[] target, int start, int limit, int nofclosures) {
2845            this.charTarget = target;
2846            this.start = start;
2847            this.limit = limit;
2848            this.resetCommon(nofclosures);
2849        }
2850    }
2851
2852    /**
2853     * Prepares for matching. This method is called just before starting matching.
2854     */

2855    void prepare() {
2856        if (Op.COUNT) Op.nofinstances = 0;
2857        this.compile(this.tokentree);
2858        /*
2859        if (this.operations.type == Op.CLOSURE && this.operations.getChild().type == Op.DOT) { // .*
2860            Op anchor = Op.createAnchor(isSet(this.options, SINGLE_LINE) ? 'A' : '@');
2861            anchor.next = this.operations;
2862            this.operations = anchor;
2863        }
2864        */

2865        if (Op.COUNT) System.err.println("DEBUG: The number of operations: "+Op.nofinstances);
2866
2867        this.minlength = this.tokentree.getMinLength();
2868
2869        this.firstChar = null;
2870        if (!isSet(this.options, PROHIBIT_HEAD_CHARACTER_OPTIMIZATION)
2871            && !isSet(this.options, XMLSCHEMA_MODE)) {
2872            RangeToken firstChar = Token.createRange();
2873            int fresult = this.tokentree.analyzeFirstCharacter(firstChar, this.options);
2874            if (fresult == Token.FC_TERMINAL) {
2875                firstChar.compactRanges();
2876                this.firstChar = firstChar;
2877                if (DEBUG)
2878                    System.err.println("DEBUG: Use the first character optimization: "+firstChar);
2879            }
2880        }
2881
2882        if (this.operations != null
2883            && (this.operations.type == Op.STRING || this.operations.type == Op.CHAR)
2884            && this.operations.next == null) {
2885            if (DEBUG)
2886                System.err.print(" *** Only fixed string! *** ");
2887            this.fixedStringOnly = true;
2888            if (this.operations.type == Op.STRING)
2889                this.fixedString = this.operations.getString();
2890            else if (this.operations.getData() >= 0x10000) { // Op.CHAR
2891
this.fixedString = REUtil.decomposeToSurrogates(this.operations.getData());
2892            } else {
2893                char[] ac = new char[1];
2894                ac[0] = (char)this.operations.getData();
2895                this.fixedString = new String JavaDoc(ac);
2896            }
2897            this.fixedStringOptions = this.options;
2898            this.fixedStringTable = new BMPattern(this.fixedString, 256,
2899                                                  isSet(this.fixedStringOptions, IGNORE_CASE));
2900        } else if (!isSet(this.options, PROHIBIT_FIXED_STRING_OPTIMIZATION)
2901                   && !isSet(this.options, XMLSCHEMA_MODE)) {
2902            Token.FixedStringContainer container = new Token.FixedStringContainer();
2903            this.tokentree.findFixedString(container, this.options);
2904            this.fixedString = container.token == null ? null : container.token.getString();
2905            this.fixedStringOptions = container.options;
2906            if (this.fixedString != null && this.fixedString.length() < 2)
2907                this.fixedString = null;
2908            // This pattern has a fixed string of which length is more than one.
2909
if (this.fixedString != null) {
2910                this.fixedStringTable = new BMPattern(this.fixedString, 256,
2911                                                      isSet(this.fixedStringOptions, IGNORE_CASE));
2912                if (DEBUG) {
2913                    System.err.println("DEBUG: The longest fixed string: "+this.fixedString.length()
2914                                       +"/" //+this.fixedString
2915
+"/"+REUtil.createOptionString(this.fixedStringOptions));
2916                    System.err.print("String: ");
2917                    REUtil.dumpString(this.fixedString);
2918                }
2919            }
2920        }
2921    }
2922
2923    /**
2924     * An option.
2925     * If you specify this option, <span class="REGEX"><kbd>(</kbd><var>X</var><kbd>)</kbd></span>
2926     * captures matched text, and <span class="REGEX"><kbd>(:?</kbd><var>X</var><kbd>)</kbd></span>
2927     * does not capture.
2928     *
2929     * @see #RegularExpression(java.lang.String,int)
2930     * @see #setPattern(java.lang.String,int)
2931    static final int MARK_PARENS = 1<<0;
2932     */

2933
2934    /**
2935     * "i"
2936     */

2937    static final int IGNORE_CASE = 1<<1;
2938
2939    /**
2940     * "s"
2941     */

2942    static final int SINGLE_LINE = 1<<2;
2943
2944    /**
2945     * "m"
2946     */

2947    static final int MULTIPLE_LINES = 1<<3;
2948
2949    /**
2950     * "x"
2951     */

2952    static final int EXTENDED_COMMENT = 1<<4;
2953
2954    /**
2955     * This option redefines <span class="REGEX"><kbd>\d \D \w \W \s \S</kbd></span>.
2956     *
2957     * @see #RegularExpression(java.lang.String,int)
2958     * @see #setPattern(java.lang.String,int)
2959     * @see #UNICODE_WORD_BOUNDARY
2960     */

2961    static final int USE_UNICODE_CATEGORY = 1<<5; // "u"
2962

2963    /**
2964     * An option.
2965     * This enables to process locale-independent word boundary for <span class="REGEX"><kbd>\b \B \&lt; \></kbd></span>.
2966     * <p>By default, the engine considers a position between a word character
2967     * (<span class="REGEX"><Kbd>\w</kbd></span>) and a non word character
2968     * is a word boundary.
2969     * <p>By this option, the engine checks word boundaries with the method of
2970     * 'Unicode Regular Expression Guidelines' Revision 4.
2971     *
2972     * @see #RegularExpression(java.lang.String,int)
2973     * @see #setPattern(java.lang.String,int)
2974     */

2975    static final int UNICODE_WORD_BOUNDARY = 1<<6; // "w"
2976

2977    /**
2978     * "H"
2979     */

2980    static final int PROHIBIT_HEAD_CHARACTER_OPTIMIZATION = 1<<7;
2981    /**
2982     * "F"
2983     */

2984    static final int PROHIBIT_FIXED_STRING_OPTIMIZATION = 1<<8;
2985    /**
2986     * "X". XML Schema mode.
2987     */

2988    static final int XMLSCHEMA_MODE = 1<<9;
2989    /**
2990     * ",".
2991     */

2992    static final int SPECIAL_COMMA = 1<<10;
2993
2994
2995    private static final boolean isSet(int options, int flag) {
2996        return (options & flag) == flag;
2997    }
2998
2999    /**
3000     * Creates a new RegularExpression instance.
3001     *
3002     * @param regex A regular expression
3003     * @exception com.sun.org.apache.xerces.internal.utils.regex.ParseException <VAR>regex</VAR> is not conforming to the syntax.
3004     */

3005    public RegularExpression(String JavaDoc regex) throws ParseException {
3006        this.setPattern(regex, null);
3007    }
3008
3009    /**
3010     * Creates a new RegularExpression instance with options.
3011     *
3012     * @param regex A regular expression
3013     * @param options A String consisted of "i" "m" "s" "u" "w" "," "X"
3014     * @exception com.sun.org.apache.xerces.internal.utils.regex.ParseException <VAR>regex</VAR> is not conforming to the syntax.
3015     */

3016    public RegularExpression(String JavaDoc regex, String JavaDoc options) throws ParseException {
3017        this.setPattern(regex, options);
3018    }
3019
3020    RegularExpression(String JavaDoc regex, Token tok, int parens, boolean hasBackReferences, int options) {
3021        this.regex = regex;
3022        this.tokentree = tok;
3023        this.nofparen = parens;
3024        this.options = options;
3025        this.hasBackReferences = hasBackReferences;
3026    }
3027
3028    /**
3029     *
3030     */

3031    public void setPattern(String JavaDoc newPattern) throws ParseException {
3032        this.setPattern(newPattern, this.options);
3033    }
3034
3035    private void setPattern(String JavaDoc newPattern, int options) throws ParseException {
3036        this.regex = newPattern;
3037        this.options = options;
3038        RegexParser rp = RegularExpression.isSet(this.options, RegularExpression.XMLSCHEMA_MODE)
3039                         ? new ParserForXMLSchema() : new RegexParser();
3040        this.tokentree = rp.parse(this.regex, this.options);
3041        this.nofparen = rp.parennumber;
3042        this.hasBackReferences = rp.hasBackReferences;
3043
3044        this.operations = null;
3045        this.context = null;
3046    }
3047    /**
3048     *
3049     */

3050    public void setPattern(String JavaDoc newPattern, String JavaDoc options) throws ParseException {
3051        this.setPattern(newPattern, REUtil.parseOptions(options));
3052    }
3053
3054    /**
3055     *
3056     */

3057    public String JavaDoc getPattern() {
3058        return this.regex;
3059    }
3060
3061    /**
3062     * Represents this instence in String.
3063     */

3064    public String JavaDoc toString() {
3065        return this.tokentree.toString(this.options);
3066    }
3067
3068    /**
3069     * Returns a option string.
3070     * The order of letters in it may be different from a string specified
3071     * in a constructor or <code>setPattern()</code>.
3072     *
3073     * @see #RegularExpression(java.lang.String,java.lang.String)
3074     * @see #setPattern(java.lang.String,java.lang.String)
3075     */

3076    public String JavaDoc getOptions() {
3077        return REUtil.createOptionString(this.options);
3078    }
3079
3080    /**
3081     * Return true if patterns are the same and the options are equivalent.
3082     */

3083    public boolean equals(Object JavaDoc obj) {
3084        if (obj == null) return false;
3085        if (!(obj instanceof RegularExpression))
3086            return false;
3087        RegularExpression r = (RegularExpression)obj;
3088        return this.regex.equals(r.regex) && this.options == r.options;
3089    }
3090
3091    boolean equals(String JavaDoc pattern, int options) {
3092        return this.regex.equals(pattern) && this.options == options;
3093    }
3094
3095    /**
3096     *
3097     */

3098    public int hashCode() {
3099        return (this.regex+"/"+this.getOptions()).hashCode();
3100    }
3101
3102    /**
3103     * Return the number of regular expression groups.
3104     * This method returns 1 when the regular expression has no capturing-parenthesis.
3105     *
3106     */

3107    public int getNumberOfGroups() {
3108        return this.nofparen;
3109    }
3110
3111    // ================================================================
3112

3113    private static final int WT_IGNORE = 0;
3114    private static final int WT_LETTER = 1;
3115    private static final int WT_OTHER = 2;
3116    private static final int getWordType0(char ch, int opts) {
3117        if (!isSet(opts, UNICODE_WORD_BOUNDARY)) {
3118            if (isSet(opts, USE_UNICODE_CATEGORY)) {
3119                return (Token.getRange("IsWord", true).match(ch)) ? WT_LETTER : WT_OTHER;
3120            }
3121            return isWordChar(ch) ? WT_LETTER : WT_OTHER;
3122        }
3123
3124        switch (Character.getType(ch)) {
3125        case Character.UPPERCASE_LETTER: // L
3126
case Character.LOWERCASE_LETTER: // L
3127
case Character.TITLECASE_LETTER: // L
3128
case Character.MODIFIER_LETTER: // L
3129
case Character.OTHER_LETTER: // L
3130
case Character.LETTER_NUMBER: // N
3131
case Character.DECIMAL_DIGIT_NUMBER: // N
3132
case Character.OTHER_NUMBER: // N
3133
case Character.COMBINING_SPACING_MARK: // Mc
3134
return WT_LETTER;
3135
3136        case Character.FORMAT: // Cf
3137
case Character.NON_SPACING_MARK: // Mn
3138
case Character.ENCLOSING_MARK: // Mc
3139
return WT_IGNORE;
3140
3141        case Character.CONTROL: // Cc
3142
switch (ch) {
3143            case '\t':
3144            case '\n':
3145            case '\u000B':
3146            case '\f':
3147            case '\r':
3148                return WT_OTHER;
3149            default:
3150                return WT_IGNORE;
3151            }
3152
3153        default:
3154            return WT_OTHER;
3155        }
3156    }
3157
3158    // ================================================================
3159

3160    static final int LINE_FEED = 0x000A;
3161    static final int CARRIAGE_RETURN = 0x000D;
3162    static final int LINE_SEPARATOR = 0x2028;
3163    static final int PARAGRAPH_SEPARATOR = 0x2029;
3164
3165    private static final boolean isEOLChar(int ch) {
3166        return ch == LINE_FEED || ch == CARRIAGE_RETURN || ch == LINE_SEPARATOR
3167        || ch == PARAGRAPH_SEPARATOR;
3168    }
3169
3170    private static final boolean isWordChar(int ch) { // Legacy word characters
3171
if (ch == '_') return true;
3172        if (ch < '0') return false;
3173        if (ch > 'z') return false;
3174        if (ch <= '9') return true;
3175        if (ch < 'A') return false;
3176        if (ch <= 'Z') return true;
3177        if (ch < 'a') return false;
3178        return true;
3179    }
3180
3181    private static final boolean matchIgnoreCase(int chardata, int ch) {
3182        if (chardata == ch) return true;
3183        if (chardata > 0xffff || ch > 0xffff) return false;
3184        char uch1 = Character.toUpperCase((char)chardata);
3185        char uch2 = Character.toUpperCase((char)ch);
3186        if (uch1 == uch2) return true;
3187        return Character.toLowerCase(uch1) == Character.toLowerCase(uch2);
3188    }
3189}
3190
Popular Tags