/*

  * Copyright (c) 1999, 2011, Oracle and/or its affiliates. All rights reserved.

  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

  *

  * This code is free software; you can redistribute it and/or modify it

  * under the terms of the GNU General Public License version 2 only, as

  * published by the Free Software Foundation.  Oracle designates this

  * particular file as subject to the "Classpath" exception as provided

  * by Oracle in the LICENSE file that accompanied this code.

  *

  * This code is distributed in the hope that it will be useful, but WITHOUT

  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

  * version 2 for more details (a copy is included in the LICENSE file that

  * accompanied this code).

  *

  * You should have received a copy of the GNU General Public License version

  * 2 along with this work; if not, write to the Free Software Foundation,

  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

  *

  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

  * or visit www.oracle.com if you need additional information or have any

  * questions.

  */

 package java.util.regex;

 import java.security.AccessController;

 import java.security.PrivilegedAction;

 import java.text.CharacterIterator;

 import java.text.Normalizer;

 import java.util.Locale;

 import java.util.Map;

 import java.util.ArrayList;

 import java.util.HashMap;

 import java.util.Arrays;

 /**

  * A compiled representation of a regular expression.

  *

  * <p> A regular expression, specified as a string, must first be compiled into

  * an instance of this class.  The resulting pattern can then be used to create

  * a {@link Matcher} object that can match arbitrary {@link

  * java.lang.CharSequence </code>character sequences<code>} against the regular

  * expression.  All of the state involved in performing a match resides in the

  * matcher, so many matchers can share the same pattern.

  *

  * <p> A typical invocation sequence is thus

  *

  * <blockquote><pre>

  * Pattern p = Pattern.{@link #compile compile}("a*b");

  * Matcher m = p.{@link #matcher matcher}("aaaaab");

  * boolean b = m.{@link Matcher#matches matches}();</pre></blockquote>

  *

  * <p> A {@link #matches matches} method is defined by this class as a

  * convenience for when a regular expression is used just once.  This method

  * compiles an expression and matches an input sequence against it in a single

  * invocation.  The statement

  *

  * <blockquote><pre>

  * boolean b = Pattern.matches("a*b", "aaaaab");</pre></blockquote>

  *

  * is equivalent to the three statements above, though for repeated matches it

  * is less efficient since it does not allow the compiled pattern to be reused.

  *

  * <p> Instances of this class are immutable and are safe for use by multiple

  * concurrent threads.  Instances of the {@link Matcher} class are not safe for

  * such use.

  *

  *

  * <a name="sum">

  * <h4> Summary of regular-expression constructs </h4>

  *

  * <table border="0" cellpadding="1" cellspacing="0"

  *  summary="Regular expression constructs, and what they match">

  *

  * <tr align="left">

  * <th bgcolor="#CCCCFF" align="left" id="construct">Construct</th>

  * <th bgcolor="#CCCCFF" align="left" id="matches">Matches</th>

  * </tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="characters">Characters</th></tr>

  *

  * <tr><td valign="top" headers="construct characters"><i>x</i></td>

  *     <td headers="matches">The character <i>x</i></td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\\</tt></td>

  *     <td headers="matches">The backslash character</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\0</tt><i>n</i></td>

  *     <td headers="matches">The character with octal value <tt>0</tt><i>n</i>

  *         (0&nbsp;<tt>&lt;=</tt>&nbsp;<i>n</i>&nbsp;<tt>&lt;=</tt>&nbsp;7)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\0</tt><i>nn</i></td>

  *     <td headers="matches">The character with octal value <tt>0</tt><i>nn</i>

  *         (0&nbsp;<tt>&lt;=</tt>&nbsp;<i>n</i>&nbsp;<tt>&lt;=</tt>&nbsp;7)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\0</tt><i>mnn</i></td>

  *     <td headers="matches">The character with octal value <tt>0</tt><i>mnn</i>

  *         (0&nbsp;<tt>&lt;=</tt>&nbsp;<i>m</i>&nbsp;<tt>&lt;=</tt>&nbsp;3,

  *         0&nbsp;<tt>&lt;=</tt>&nbsp;<i>n</i>&nbsp;<tt>&lt;=</tt>&nbsp;7)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\x</tt><i>hh</i></td>

  *     <td headers="matches">The character with hexadecimal&nbsp;value&nbsp;<tt>0x</tt><i>hh</i></td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>&#92;u</tt><i>hhhh</i></td>

  *     <td headers="matches">The character with hexadecimal&nbsp;value&nbsp;<tt>0x</tt><i>hhhh</i></td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>&#92;x</tt><i>{h...h}</i></td>

  *     <td headers="matches">The character with hexadecimal&nbsp;value&nbsp;<tt>0x</tt><i>h...h</i>

  *         ({@link java.lang.Character#MIN_CODE_POINT Character.MIN_CODE_POINT}

  *         &nbsp;&lt;=&nbsp;<tt>0x</tt><i>h...h</i>&nbsp;&lt;=&nbsp

  *          {@link java.lang.Character#MAX_CODE_POINT Character.MAX_CODE_POINT})</td></tr>

  * <tr><td valign="top" headers="matches"><tt>\t</tt></td>

  *     <td headers="matches">The tab character (<tt>'&#92;u0009'</tt>)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\n</tt></td>

  *     <td headers="matches">The newline (line feed) character (<tt>'&#92;u000A'</tt>)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\r</tt></td>

  *     <td headers="matches">The carriage-return character (<tt>'&#92;u000D'</tt>)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\f</tt></td>

  *     <td headers="matches">The form-feed character (<tt>'&#92;u000C'</tt>)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\a</tt></td>

  *     <td headers="matches">The alert (bell) character (<tt>'&#92;u0007'</tt>)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\e</tt></td>

  *     <td headers="matches">The escape character (<tt>'&#92;u001B'</tt>)</td></tr>

  * <tr><td valign="top" headers="construct characters"><tt>\c</tt><i>x</i></td>

  *     <td headers="matches">The control character corresponding to <i>x</i></td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="classes">Character classes</th></tr>

  *

  * <tr><td valign="top" headers="construct classes"><tt>[abc]</tt></td>

  *     <td headers="matches"><tt>a</tt>, <tt>b</tt>, or <tt>c</tt> (simple class)</td></tr>

  * <tr><td valign="top" headers="construct classes"><tt>[^abc]</tt></td>

  *     <td headers="matches">Any character except <tt>a</tt>, <tt>b</tt>, or <tt>c</tt> (negation)</td></tr>

  * <tr><td valign="top" headers="construct classes"><tt>[a-zA-Z]</tt></td>

  *     <td headers="matches"><tt>a</tt> through <tt>z</tt>

  *         or <tt>A</tt> through <tt>Z</tt>, inclusive (range)</td></tr>

  * <tr><td valign="top" headers="construct classes"><tt>[a-d[m-p]]</tt></td>

  *     <td headers="matches"><tt>a</tt> through <tt>d</tt>,

  *      or <tt>m</tt> through <tt>p</tt>: <tt>[a-dm-p]</tt> (union)</td></tr>

  * <tr><td valign="top" headers="construct classes"><tt>[a-z&&[def]]</tt></td>

  *     <td headers="matches"><tt>d</tt>, <tt>e</tt>, or <tt>f</tt> (intersection)</tr>

  * <tr><td valign="top" headers="construct classes"><tt>[a-z&&[^bc]]</tt></td>

  *     <td headers="matches"><tt>a</tt> through <tt>z</tt>,

  *         except for <tt>b</tt> and <tt>c</tt>: <tt>[ad-z]</tt> (subtraction)</td></tr>

  * <tr><td valign="top" headers="construct classes"><tt>[a-z&&[^m-p]]</tt></td>

  *     <td headers="matches"><tt>a</tt> through <tt>z</tt>,

  *          and not <tt>m</tt> through <tt>p</tt>: <tt>[a-lq-z]</tt>(subtraction)</td></tr>

  * <tr><th>&nbsp;</th></tr>

  *

  * <tr align="left"><th colspan="2" id="predef">Predefined character classes</th></tr>

  *

  * <tr><td valign="top" headers="construct predef"><tt>.</tt></td>

  *     <td headers="matches">Any character (may or may not match <a href="#lt">line terminators</a>)</td></tr>

  * <tr><td valign="top" headers="construct predef"><tt>\d</tt></td>

  *     <td headers="matches">A digit: <tt>[0-9]</tt></td></tr>

  * <tr><td valign="top" headers="construct predef"><tt>\D</tt></td>

  *     <td headers="matches">A non-digit: <tt>[^0-9]</tt></td></tr>

  * <tr><td valign="top" headers="construct predef"><tt>\s</tt></td>

  *     <td headers="matches">A whitespace character: <tt>[ \t\n\x0B\f\r]</tt></td></tr>

  * <tr><td valign="top" headers="construct predef"><tt>\S</tt></td>

  *     <td headers="matches">A non-whitespace character: <tt>[^\s]</tt></td></tr>

  * <tr><td valign="top" headers="construct predef"><tt>\w</tt></td>

  *     <td headers="matches">A word character: <tt>[a-zA-Z_0-9]</tt></td></tr>

  * <tr><td valign="top" headers="construct predef"><tt>\W</tt></td>

  *     <td headers="matches">A non-word character: <tt>[^\w]</tt></td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="posix">POSIX character classes</b> (US-ASCII only)<b></th></tr>

  *

  * <tr><td valign="top" headers="construct posix"><tt>\p{Lower}</tt></td>

  *     <td headers="matches">A lower-case alphabetic character: <tt>[a-z]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Upper}</tt></td>

  *     <td headers="matches">An upper-case alphabetic character:<tt>[A-Z]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{ASCII}</tt></td>

  *     <td headers="matches">All ASCII:<tt>[\x00-\x7F]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Alpha}</tt></td>

  *     <td headers="matches">An alphabetic character:<tt>[\p{Lower}\p{Upper}]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Digit}</tt></td>

  *     <td headers="matches">A decimal digit: <tt>[0-9]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Alnum}</tt></td>

  *     <td headers="matches">An alphanumeric character:<tt>[\p{Alpha}\p{Digit}]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Punct}</tt></td>

  *     <td headers="matches">Punctuation: One of <tt>!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~</tt></td></tr>

  *     <!-- <tt>[\!"#\$%&'\(\)\*\+,\-\./:;\<=\>\?@\[\\\]\^_`\{\|\}~]</tt>

  *          <tt>[\X21-\X2F\X31-\X40\X5B-\X60\X7B-\X7E]</tt> -->

  * <tr><td valign="top" headers="construct posix"><tt>\p{Graph}</tt></td>

  *     <td headers="matches">A visible character: <tt>[\p{Alnum}\p{Punct}]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Print}</tt></td>

  *     <td headers="matches">A printable character: <tt>[\p{Graph}\x20]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Blank}</tt></td>

  *     <td headers="matches">A space or a tab: <tt>[ \t]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Cntrl}</tt></td>

  *     <td headers="matches">A control character: <tt>[\x00-\x1F\x7F]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{XDigit}</tt></td>

  *     <td headers="matches">A hexadecimal digit: <tt>[0-9a-fA-F]</tt></td></tr>

  * <tr><td valign="top" headers="construct posix"><tt>\p{Space}</tt></td>

  *     <td headers="matches">A whitespace character: <tt>[ \t\n\x0B\f\r]</tt></td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2">java.lang.Character classes (simple <a href="#jcc">java character type</a>)</th></tr>

  *

  * <tr><td valign="top"><tt>\p{javaLowerCase}</tt></td>

  *     <td>Equivalent to java.lang.Character.isLowerCase()</td></tr>

  * <tr><td valign="top"><tt>\p{javaUpperCase}</tt></td>

  *     <td>Equivalent to java.lang.Character.isUpperCase()</td></tr>

  * <tr><td valign="top"><tt>\p{javaWhitespace}</tt></td>

  *     <td>Equivalent to java.lang.Character.isWhitespace()</td></tr>

  * <tr><td valign="top"><tt>\p{javaMirrored}</tt></td>

  *     <td>Equivalent to java.lang.Character.isMirrored()</td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="unicode">Classes for Unicode scripts, blocks, categories and binary properties</th></tr>

  * * <tr><td valign="top" headers="construct unicode"><tt>\p{IsLatin}</tt></td>

  *     <td headers="matches">A Latin&nbsp;script character (<a href="#usc">script</a>)</td></tr>

  * <tr><td valign="top" headers="construct unicode"><tt>\p{InGreek}</tt></td>

  *     <td headers="matches">A character in the Greek&nbsp;block (<a href="#ubc">block</a>)</td></tr>

  * <tr><td valign="top" headers="construct unicode"><tt>\p{Lu}</tt></td>

  *     <td headers="matches">An uppercase letter (<a href="#ucc">category</a>)</td></tr>

  * <tr><td valign="top" headers="construct unicode"><tt>\p{IsAlphabetic}</tt></td>

  *     <td headers="matches">An alphabetic character (<a href="#ubpc">binary property</a>)</td></tr>

  * <tr><td valign="top" headers="construct unicode"><tt>\p{Sc}</tt></td>

  *     <td headers="matches">A currency symbol</td></tr>

  * <tr><td valign="top" headers="construct unicode"><tt>\P{InGreek}</tt></td>

  *     <td headers="matches">Any character except one in the Greek block (negation)</td></tr>

  * <tr><td valign="top" headers="construct unicode"><tt>[\p{L}&&[^\p{Lu}]]&nbsp;</tt></td>

  *     <td headers="matches">Any letter except an uppercase letter (subtraction)</td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="bounds">Boundary matchers</th></tr>

  *

  * <tr><td valign="top" headers="construct bounds"><tt>^</tt></td>

  *     <td headers="matches">The beginning of a line</td></tr>

  * <tr><td valign="top" headers="construct bounds"><tt>$</tt></td>

  *     <td headers="matches">The end of a line</td></tr>

  * <tr><td valign="top" headers="construct bounds"><tt>\b</tt></td>

  *     <td headers="matches">A word boundary</td></tr>

  * <tr><td valign="top" headers="construct bounds"><tt>\B</tt></td>

  *     <td headers="matches">A non-word boundary</td></tr>

  * <tr><td valign="top" headers="construct bounds"><tt>\A</tt></td>

  *     <td headers="matches">The beginning of the input</td></tr>

  * <tr><td valign="top" headers="construct bounds"><tt>\G</tt></td>

  *     <td headers="matches">The end of the previous match</td></tr>

  * <tr><td valign="top" headers="construct bounds"><tt>\Z</tt></td>

  *     <td headers="matches">The end of the input but for the final

  *         <a href="#lt">terminator</a>, if&nbsp;any</td></tr>

  * <tr><td valign="top" headers="construct bounds"><tt>\z</tt></td>

  *     <td headers="matches">The end of the input</td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="greedy">Greedy quantifiers</th></tr>

  *

  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>?</tt></td>

  *     <td headers="matches"><i>X</i>, once or not at all</td></tr>

  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>*</tt></td>

  *     <td headers="matches"><i>X</i>, zero or more times</td></tr>

  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>+</tt></td>

  *     <td headers="matches"><i>X</i>, one or more times</td></tr>

  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>{</tt><i>n</i><tt>}</tt></td>

  *     <td headers="matches"><i>X</i>, exactly <i>n</i> times</td></tr>

  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>{</tt><i>n</i><tt>,}</tt></td>

  *     <td headers="matches"><i>X</i>, at least <i>n</i> times</td></tr>

  * <tr><td valign="top" headers="construct greedy"><i>X</i><tt>{</tt><i>n</i><tt>,</tt><i>m</i><tt>}</tt></td>

  *     <td headers="matches"><i>X</i>, at least <i>n</i> but not more than <i>m</i> times</td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="reluc">Reluctant quantifiers</th></tr>

  *

  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>??</tt></td>

  *     <td headers="matches"><i>X</i>, once or not at all</td></tr>

  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>*?</tt></td>

  *     <td headers="matches"><i>X</i>, zero or more times</td></tr>

  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>+?</tt></td>

  *     <td headers="matches"><i>X</i>, one or more times</td></tr>

  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>{</tt><i>n</i><tt>}?</tt></td>

  *     <td headers="matches"><i>X</i>, exactly <i>n</i> times</td></tr>

  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>{</tt><i>n</i><tt>,}?</tt></td>

  *     <td headers="matches"><i>X</i>, at least <i>n</i> times</td></tr>

  * <tr><td valign="top" headers="construct reluc"><i>X</i><tt>{</tt><i>n</i><tt>,</tt><i>m</i><tt>}?</tt></td>

  *     <td headers="matches"><i>X</i>, at least <i>n</i> but not more than <i>m</i> times</td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="poss">Possessive quantifiers</th></tr>

  *

  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>?+</tt></td>

  *     <td headers="matches"><i>X</i>, once or not at all</td></tr>

  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>*+</tt></td>

  *     <td headers="matches"><i>X</i>, zero or more times</td></tr>

  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>++</tt></td>

  *     <td headers="matches"><i>X</i>, one or more times</td></tr>

  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>{</tt><i>n</i><tt>}+</tt></td>

  *     <td headers="matches"><i>X</i>, exactly <i>n</i> times</td></tr>

  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>{</tt><i>n</i><tt>,}+</tt></td>

  *     <td headers="matches"><i>X</i>, at least <i>n</i> times</td></tr>

  * <tr><td valign="top" headers="construct poss"><i>X</i><tt>{</tt><i>n</i><tt>,</tt><i>m</i><tt>}+</tt></td>

  *     <td headers="matches"><i>X</i>, at least <i>n</i> but not more than <i>m</i> times</td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="logical">Logical operators</th></tr>

  *

  * <tr><td valign="top" headers="construct logical"><i>XY</i></td>

  *     <td headers="matches"><i>X</i> followed by <i>Y</i></td></tr>

  * <tr><td valign="top" headers="construct logical"><i>X</i><tt>|</tt><i>Y</i></td>

  *     <td headers="matches">Either <i>X</i> or <i>Y</i></td></tr>

  * <tr><td valign="top" headers="construct logical"><tt>(</tt><i>X</i><tt>)</tt></td>

  *     <td headers="matches">X, as a <a href="#cg">capturing group</a></td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="backref">Back references</th></tr>

  *

  * <tr><td valign="bottom" headers="construct backref"><tt>\</tt><i>n</i></td>

  *     <td valign="bottom" headers="matches">Whatever the <i>n</i><sup>th</sup>

  *     <a href="#cg">capturing group</a> matched</td></tr>

  *

  * <tr><td valign="bottom" headers="construct backref"><tt>\</tt><i>k</i>&lt;<i>name</i>&gt;</td>

  *     <td valign="bottom" headers="matches">Whatever the

  *     <a href="#groupname">named-capturing group</a> "name" matched</td></tr>

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="quot">Quotation</th></tr>

  *

  * <tr><td valign="top" headers="construct quot"><tt>\</tt></td>

  *     <td headers="matches">Nothing, but quotes the following character</td></tr>

  * <tr><td valign="top" headers="construct quot"><tt>\Q</tt></td>

  *     <td headers="matches">Nothing, but quotes all characters until <tt>\E</tt></td></tr>

  * <tr><td valign="top" headers="construct quot"><tt>\E</tt></td>

  *     <td headers="matches">Nothing, but ends quoting started by <tt>\Q</tt></td></tr>

  *     <!-- Metachars: !$()*+.<>?[\]^{|} -->

  *

  * <tr><th>&nbsp;</th></tr>

  * <tr align="left"><th colspan="2" id="special">Special constructs (named-capturing and non-capturing)</th></tr>

  *

  * <tr><td valign="top" headers="construct special"><tt>(?&lt;<a href="#groupname">name</a>&gt;</tt><i>X</i><tt>)</tt></td>

  *     <td headers="matches"><i>X</i>, as a named-capturing group</td></tr>

  * <tr><td valign="top" headers="construct special"><tt>(?:</tt><i>X</i><tt>)</tt></td>

  *     <td headers="matches"><i>X</i>, as a non-capturing group</td></tr>

  * <tr><td valign="top" headers="construct special"><tt>(?idmsuxU-idmsuxU)&nbsp;</tt></td>

  *     <td headers="matches">Nothing, but turns match flags <a href="#CASE_INSENSITIVE">i</a>

  * <a href="#UNIX_LINES">d</a> <a href="#MULTILINE">m</a> <a href="#DOTALL">s</a>

  * <a href="#UNICODE_CASE">u</a> <a href="#COMMENTS">x</a> <a href="#UNICODE_CHARACTER_CLASS">U</a>

  * on - off</td></tr>

  * <tr><td valign="top" headers="construct special"><tt>(?idmsux-idmsux:</tt><i>X</i><tt>)</tt>&nbsp;&nbsp;</td>

  *     <td headers="matches"><i>X</i>, as a <a href="#cg">non-capturing group</a> with the

  *         given flags <a href="#CASE_INSENSITIVE">i</a> <a href="#UNIX_LINES">d</a>

  * <a href="#MULTILINE">m</a> <a href="#DOTALL">s</a> <a href="#UNICODE_CASE">u</a >

  * <a href="#COMMENTS">x</a> on - off</td></tr>

  * <tr><td valign="top" headers="construct special"><tt>(?=</tt><i>X</i><tt>)</tt></td>

  *     <td headers="matches"><i>X</i>, via zero-width positive lookahead</td></tr>

  * <tr><td valign="top" headers="construct special"><tt>(?!</tt><i>X</i><tt>)</tt></td>

  *     <td headers="matches"><i>X</i>, via zero-width negative lookahead</td></tr>

  * <tr><td valign="top" headers="construct special"><tt>(?&lt;=</tt><i>X</i><tt>)</tt></td>

  *     <td headers="matches"><i>X</i>, via zero-width positive lookbehind</td></tr>

  * <tr><td valign="top" headers="construct special"><tt>(?&lt;!</tt><i>X</i><tt>)</tt></td>

  *     <td headers="matches"><i>X</i>, via zero-width negative lookbehind</td></tr>

  * <tr><td valign="top" headers="construct special"><tt>(?&gt;</tt><i>X</i><tt>)</tt></td>

  *     <td headers="matches"><i>X</i>, as an independent, non-capturing group</td></tr>

  *

  * </table>

  *

  * <hr>

  *

  *

  * <a name="bs">

  * <h4> Backslashes, escapes, and quoting </h4>

  *

  * <p> The backslash character (<tt>'\'</tt>) serves to introduce escaped

  * constructs, as defined in the table above, as well as to quote characters

  * that otherwise would be interpreted as unescaped constructs.  Thus the

  * expression <tt>\\</tt> matches a single backslash and <tt>\{</tt> matches a

  * left brace.

  *

  * <p> It is an error to use a backslash prior to any alphabetic character that

  * does not denote an escaped construct; these are reserved for future

  * extensions to the regular-expression language.  A backslash may be used

  * prior to a non-alphabetic character regardless of whether that character is

  * part of an unescaped construct.

  *

  * <p> Backslashes within string literals in Java source code are interpreted

  * as required by

  * <cite>The Java&trade; Language Specification</cite>

  * as either Unicode escapes (section 3.3) or other character escapes (section 3.10.6)

  * It is therefore necessary to double backslashes in string

  * literals that represent regular expressions to protect them from

  * interpretation by the Java bytecode compiler.  The string literal

  * <tt>"&#92;b"</tt>, for example, matches a single backspace character when

  * interpreted as a regular expression, while <tt>"&#92;&#92;b"</tt> matches a

  * word boundary.  The string literal <tt>"&#92;(hello&#92;)"</tt> is illegal

  * and leads to a compile-time error; in order to match the string

  * <tt>(hello)</tt> the string literal <tt>"&#92;&#92;(hello&#92;&#92;)"</tt>

  * must be used.

  *

  * <a name="cc">

  * <h4> Character Classes </h4>

  *

  *    <p> Character classes may appear within other character classes, and

  *    may be composed by the union operator (implicit) and the intersection

  *    operator (<tt>&amp;&amp;</tt>).

  *    The union operator denotes a class that contains every character that is

  *    in at least one of its operand classes.  The intersection operator

  *    denotes a class that contains every character that is in both of its

  *    operand classes.

  *

  *    <p> The precedence of character-class operators is as follows, from

  *    highest to lowest:

  *

  *    <blockquote><table border="0" cellpadding="1" cellspacing="0"

  *                 summary="Precedence of character class operators.">

  *      <tr><th>1&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *        <td>Literal escape&nbsp;&nbsp;&nbsp;&nbsp;</td>

  *        <td><tt>\x</tt></td></tr>

  *     <tr><th>2&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *        <td>Grouping</td>

  *        <td><tt>[...]</tt></td></tr>

  *     <tr><th>3&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *        <td>Range</td>

  *        <td><tt>a-z</tt></td></tr>

  *      <tr><th>4&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *        <td>Union</td>

  *        <td><tt>[a-e][i-u]</tt></td></tr>

  *      <tr><th>5&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *        <td>Intersection</td>

  *        <td><tt>[a-z&&[aeiou]]</tt></td></tr>

  *    </table></blockquote>

  *

  *    <p> Note that a different set of metacharacters are in effect inside

  *    a character class than outside a character class. For instance, the

  *    regular expression <tt>.</tt> loses its special meaning inside a

  *    character class, while the expression <tt>-</tt> becomes a range

  *    forming metacharacter.

  *

  * <a name="lt">

  * <h4> Line terminators </h4>

  *

  * <p> A <i>line terminator</i> is a one- or two-character sequence that marks

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

  * recognized as line terminators:

  *

  * <ul>

  *

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

  *

  *   <li> A carriage-return character followed immediately by a newline

  *   character&nbsp;(<tt>"\r\n"</tt>),

  *

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

  *

  *   <li> A next-line character&nbsp;(<tt>'&#92;u0085'</tt>),

  *

  *   <li> A line-separator character&nbsp;(<tt>'&#92;u2028'</tt>), or

  *

  *   <li> A paragraph-separator character&nbsp;(<tt>'&#92;u2029</tt>).

  *

  * </ul>

  * <p>If {@link #UNIX_LINES} mode is activated, then the only line terminators

  * recognized are newline characters.

  *

  * <p> The regular expression <tt>.</tt> matches any character except a line

  * terminator unless the {@link #DOTALL} flag is specified.

  *

  * <p> By default, the regular expressions <tt>^</tt> and <tt>$</tt> ignore

  * line terminators and only match at the beginning and the end, respectively,

  * of the entire input sequence. If {@link #MULTILINE} mode is activated then

  * <tt>^</tt> matches at the beginning of input and after any line terminator

  * except at the end of input. When in {@link #MULTILINE} mode <tt>$</tt>

  * matches just before a line terminator or the end of the input sequence.

  *

  * <a name="cg">

  * <h4> Groups and capturing </h4>

  *

  * <a name="gnumber">

  * <h5> Group number </h5>

  * <p> Capturing groups are numbered by counting their opening parentheses from

  * left to right.  In the expression <tt>((A)(B(C)))</tt>, for example, there

  * are four such groups: </p>

  *

  * <blockquote><table cellpadding=1 cellspacing=0 summary="Capturing group numberings">

  * <tr><th>1&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *     <td><tt>((A)(B(C)))</tt></td></tr>

  * <tr><th>2&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *     <td><tt>(A)</tt></td></tr>

  * <tr><th>3&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *     <td><tt>(B(C))</tt></td></tr>

  * <tr><th>4&nbsp;&nbsp;&nbsp;&nbsp;</th>

  *     <td><tt>(C)</tt></td></tr>

  * </table></blockquote>

  *

  * <p> Group zero always stands for the entire expression.

  *

  * <p> Capturing groups are so named because, during a match, each subsequence

  * of the input sequence that matches such a group is saved.  The captured

  * subsequence may be used later in the expression, via a back reference, and

  * may also be retrieved from the matcher once the match operation is complete.

  *

  * <a name="groupname">

  * <h5> Group name </h5>

  * <p>A capturing group can also be assigned a "name", a <tt>named-capturing group</tt>,

  * and then be back-referenced later by the "name". Group names are composed of

  * the following characters. The first character must be a <tt>letter</tt>.

  *

  * <ul>

  *   <li> The uppercase letters <tt>'A'</tt> through <tt>'Z'</tt>

  *        (<tt>'&#92;u0041'</tt>&nbsp;through&nbsp;<tt>'&#92;u005a'</tt>),

  *   <li> The lowercase letters <tt>'a'</tt> through <tt>'z'</tt>

  *        (<tt>'&#92;u0061'</tt>&nbsp;through&nbsp;<tt>'&#92;u007a'</tt>),

  *   <li> The digits <tt>'0'</tt> through <tt>'9'</tt>

  *        (<tt>'&#92;u0030'</tt>&nbsp;through&nbsp;<tt>'&#92;u0039'</tt>),

  * </ul>

  *

  * <p> A <tt>named-capturing group</tt> is still numbered as described in

  * <a href="#gnumber">Group number</a>.

  *

  * <p> The captured input associated with a group is always the subsequence

  * that the group most recently matched.  If a group is evaluated a second time

  * because of quantification then its previously-captured value, if any, will

  * be retained if the second evaluation fails.  Matching the string

  * <tt>"aba"</tt> against the expression <tt>(a(b)?)+</tt>, for example, leaves

  * group two set to <tt>"b"</tt>.  All captured input is discarded at the

  * beginning of each match.

  *

  * <p> Groups beginning with <tt>(?</tt> are either pure, <i>non-capturing</i> groups

  * that do not capture text and do not count towards the group total, or

  * <i>named-capturing</i> group.

  *

  * <h4> Unicode support </h4>

  *

  * <p> This class is in conformance with Level 1 of <a

  * href="http://www.unicode.org/reports/tr18/"><i>Unicode Technical

  * Standard #18: Unicode Regular Expression</i></a>, plus RL2.1

  * Canonical Equivalents.

  * <p>

  * <b>Unicode escape sequences</b> such as <tt>&#92;u2014</tt> in Java source code

  * are processed as described in section 3.3 of

  * <cite>The Java&trade; Language Specification</cite>.

  * Such escape sequences are also implemented directly by the regular-expression

  * parser so that Unicode escapes can be used in expressions that are read from

  * files or from the keyboard.  Thus the strings <tt>"&#92;u2014"</tt> and

  * <tt>"\\u2014"</tt>, while not equal, compile into the same pattern, which

  * matches the character with hexadecimal value <tt>0x2014</tt>.

  * <p>

  * A Unicode character can also be represented in a regular-expression by

  * using its <b>Hex notation</b>(hexadecimal code point value) directly as described in construct

  * <tt>&#92;x{...}</tt>, for example a supplementary character U+2011F

  * can be specified as <tt>&#92;x{2011F}</tt>, instead of two consecutive

  * Unicode escape sequences of the surrogate pair

  * <tt>&#92;uD840</tt><tt>&#92;uDD1F</tt>.

  * <p>

  * Unicode scripts, blocks, categories and binary properties are written with

  * the <tt>\p</tt> and <tt>\P</tt> constructs as in Perl.

  * <tt>\p{</tt><i>prop</i><tt>}</tt> matches if

  * the input has the property <i>prop</i>, while <tt>\P{</tt><i>prop</i><tt>}</tt>

  * does not match if the input has that property.

  * <p>

  * Scripts, blocks, categories and binary properties can be used both inside

  * and outside of a character class.

  * <a name="usc">

  * <p>

  * <b>Scripts</b> are specified either with the prefix {@code Is}, as in

  * {@code IsHiragana}, or by using  the {@code script} keyword (or its short

  * form {@code sc})as in {@code script=Hiragana} or {@code sc=Hiragana}.

  * <p>

  * The script names supported by <code>Pattern</code> are the valid script names

  * accepted and defined by

  * {@link java.lang.Character.UnicodeScript#forName(String) UnicodeScript.forName}.

  * <a name="ubc">

  * <p>

  * <b>Blocks</b> are specified with the prefix {@code In}, as in

  * {@code InMongolian}, or by using the keyword {@code block} (or its short

  * form {@code blk}) as in {@code block=Mongolian} or {@code blk=Mongolian}.

  * <p>

  * The block names supported by <code>Pattern</code> are the valid block names

  * accepted and defined by

  * {@link java.lang.Character.UnicodeBlock#forName(String) UnicodeBlock.forName}.

  * <p>

  * <a name="ucc">

  * <b>Categories</b> may be specified with the optional prefix {@code Is}:

  * Both {@code \p{L}} and {@code \p{IsL}} denote the category of Unicode

  * letters. Same as scripts and blocks, categories can also be specified

  * by using the keyword {@code general_category} (or its short form

  * {@code gc}) as in {@code general_category=Lu} or {@code gc=Lu}.

  * <p>

  * The supported categories are those of

  * <a href="http://www.unicode.org/unicode/standard/standard.html">

  * <i>The Unicode Standard</i></a> in the version specified by the

  * {@link java.lang.Character Character} class. The category names are those

  * defined in the Standard, both normative and informative.

  * <p>

  * <a name="ubpc">

  * <b>Binary properties</b> are specified with the prefix {@code Is}, as in

  * {@code IsAlphabetic}. The supported binary properties by <code>Pattern</code>

  * are

  * <ul>

  *   <li> Alphabetic

  *   <li> Ideographic

  *   <li> Letter

  *   <li> Lowercase

  *   <li> Uppercase

  *   <li> Titlecase

  *   <li> Punctuation

  *   <Li> Control

  *   <li> White_Space

  *   <li> Digit

  *   <li> Hex_Digit

  *   <li> Noncharacter_Code_Point

  *   <li> Assigned

  * </ul>

  * <p>

  * <b>Predefined Character classes</b> and <b>POSIX character classes</b> are in

  * conformance with the recommendation of <i>Annex C: Compatibility Properties</i>

  * of <a href="http://www.unicode.org/reports/tr18/"><i>Unicode Regular Expression

  * </i></a>, when {@link #UNICODE_CHARACTER_CLASS} flag is specified.

  * <p>

  * <table border="0" cellpadding="1" cellspacing="0"

  *  summary="predefined and posix character classes in Unicode mode">

  * <tr align="left">

  * <th bgcolor="#CCCCFF" align="left" id="classes">Classes</th>

  * <th bgcolor="#CCCCFF" align="left" id="matches">Matches</th>

  *</tr>

  * <tr><td><tt>\p{Lower}</tt></td>

  *     <td>A lowercase character:<tt>\p{IsLowercase}</tt></td></tr>

  * <tr><td><tt>\p{Upper}</tt></td>

  *     <td>An uppercase character:<tt>\p{IsUppercase}</tt></td></tr>

  * <tr><td><tt>\p{ASCII}</tt></td>

  *     <td>All ASCII:<tt>[\x00-\x7F]</tt></td></tr>

  * <tr><td><tt>\p{Alpha}</tt></td>

  *     <td>An alphabetic character:<tt>\p{IsAlphabetic}</tt></td></tr>

  * <tr><td><tt>\p{Digit}</tt></td>

  *     <td>A decimal digit character:<tt>p{IsDigit}</tt></td></tr>

  * <tr><td><tt>\p{Alnum}</tt></td>

  *     <td>An alphanumeric character:<tt>[\p{IsAlphabetic}\p{IsDigit}]</tt></td></tr>

  * <tr><td><tt>\p{Punct}</tt></td>

  *     <td>A punctuation character:<tt>p{IsPunctuation}</tt></td></tr>

  * <tr><td><tt>\p{Graph}</tt></td>

  *     <td>A visible character: <tt>[^\p{IsWhite_Space}\p{gc=Cc}\p{gc=Cs}\p{gc=Cn}]</tt></td></tr>

  * <tr><td><tt>\p{Print}</tt></td>

  *     <td>A printable character: <tt>[\p{Graph}\p{Blank}&&[^\p{Cntrl}]]</tt></td></tr>

  * <tr><td><tt>\p{Blank}</tt></td>

  *     <td>A space or a tab: <tt>[\p{IsWhite_Space}&&[^\p{gc=Zl}\p{gc=Zp}\x0a\x0b\x0c\x0d\x85]]</tt></td></tr>

  * <tr><td><tt>\p{Cntrl}</tt></td>

  *     <td>A control character: <tt>\p{gc=Cc}</tt></td></tr>

  * <tr><td><tt>\p{XDigit}</tt></td>

  *     <td>A hexadecimal digit: <tt>[\p{gc=Nd}\p{IsHex_Digit}]</tt></td></tr>

  * <tr><td><tt>\p{Space}</tt></td>

  *     <td>A whitespace character:<tt>\p{IsWhite_Space}</tt></td></tr>

  * <tr><td><tt>\d</tt></td>

  *     <td>A digit: <tt>\p{IsDigit}</tt></td></tr>

  * <tr><td><tt>\D</tt></td>

  *     <td>A non-digit: <tt>[^\d]</tt></td></tr>

  * <tr><td><tt>\s</tt></td>

  *     <td>A whitespace character: <tt>\p{IsWhite_Space}</tt></td></tr>

  * <tr><td><tt>\S</tt></td>

  *     <td>A non-whitespace character: <tt>[^\s]</tt></td></tr>

  * <tr><td><tt>\w</tt></td>

  *     <td>A word character: <tt>[\p{Alpha}\p{gc=Mn}\p{gc=Me}\p{gc=Mc}\p{Digit}\p{gc=Pc}]</tt></td></tr>

  * <tr><td><tt>\W</tt></td>

  *     <td>A non-word character: <tt>[^\w]</tt></td></tr>

  * </table>

  * <p>

  * <a name="jcc">

  * Categories that behave like the java.lang.Character

  * boolean is<i>methodname</i> methods (except for the deprecated ones) are

  * available through the same <tt>\p{</tt><i>prop</i><tt>}</tt> syntax where

  * the specified property has the name <tt>java<i>methodname</i></tt>.

  *

  * <h4> Comparison to Perl 5 </h4>

  *

  * <p>The <code>Pattern</code> engine performs traditional NFA-based matching

  * with ordered alternation as occurs in Perl 5.

  *

  * <p> Perl constructs not supported by this class: </p>

  *

  * <ul>

  *    <li><p> Predefined character classes (Unicode character)

  *    <p><tt>\h&nbsp;&nbsp;&nbsp;&nbsp;</tt>A horizontal whitespace

  *    <p><tt>\H&nbsp;&nbsp;&nbsp;&nbsp;</tt>A non horizontal whitespace

  *    <p><tt>\v&nbsp;&nbsp;&nbsp;&nbsp;</tt>A vertical whitespace

  *    <p><tt>\V&nbsp;&nbsp;&nbsp;&nbsp;</tt>A non vertical whitespace

  *    <p><tt>\R&nbsp;&nbsp;&nbsp;&nbsp;</tt>Any Unicode linebreak sequence

  *    <tt>\u005cu000D\u005cu000A|[\u005cu000A\u005cu000B\u005cu000C\u005cu000D\u005cu0085\u005cu2028\u005cu2029]</tt>

  *    <p><tt>\X&nbsp;&nbsp;&nbsp;&nbsp;</tt>Match Unicode

  *    <a href="http://www.unicode.org/reports/tr18/#Default_Grapheme_Clusters">

  *    <i>extended grapheme cluster</i></a>

  *    </p></li>

  *

  *    <li><p> The backreference constructs, <tt>\g{</tt><i>n</i><tt>}</tt> for

  *    the <i>n</i><sup>th</sup><a href="#cg">capturing group</a> and

  *    <tt>\g{</tt><i>name</i><tt>}</tt> for

  *    <a href="#groupname">named-capturing group</a>.

  *    </p></li>

  *

  *    <li><p> The named character construct, <tt>\N{</tt><i>name</i><tt>}</tt>

  *    for a Unicode character by its name.

  *    </p></li>

  *

  *    <li><p> The conditional constructs

  *    <tt>(?(</tt><i>condition</i><tt>)</tt><i>X</i><tt>)</tt> and

  *    <tt>(?(</tt><i>condition</i><tt>)</tt><i>X</i><tt>|</tt><i>Y</i><tt>)</tt>,

  *    </p></li>

  *

  *    <li><p> The embedded code constructs <tt>(?{</tt><i>code</i><tt>})</tt>

  *    and <tt>(??{</tt><i>code</i><tt>})</tt>,</p></li>

  *

  *    <li><p> The embedded comment syntax <tt>(?#comment)</tt>, and </p></li>

  *

  *    <li><p> The preprocessing operations <tt>\l</tt> <tt>&#92;u</tt>,

  *    <tt>\L</tt>, and <tt>\U</tt>.  </p></li>

  *

  * </ul>

  *

  * <p> Constructs supported by this class but not by Perl: </p>

  *

  * <ul>

  *

  *    <li><p> Character-class union and intersection as described

  *    <a href="#cc">above</a>.</p></li>

  *

  * </ul>

  *

  * <p> Notable differences from Perl: </p>

  *

  * <ul>

  *

  *    <li><p> In Perl, <tt>\1</tt> through <tt>\9</tt> are always interpreted

  *    as back references; a backslash-escaped number greater than <tt>9</tt> is

  *    treated as a back reference if at least that many subexpressions exist,

  *    otherwise it is interpreted, if possible, as an octal escape.  In this

  *    class octal escapes must always begin with a zero. In this class,

  *    <tt>\1</tt> through <tt>\9</tt> are always interpreted as back

  *    references, and a larger number is accepted as a back reference if at

  *    least that many subexpressions exist at that point in the regular

  *    expression, otherwise the parser will drop digits until the number is

  *    smaller or equal to the existing number of groups or it is one digit.

  *    </p></li>

  *

  *    <li><p> Perl uses the <tt>g</tt> flag to request a match that resumes

  *    where the last match left off.  This functionality is provided implicitly

  *    by the {@link Matcher} class: Repeated invocations of the {@link

  *    Matcher#find find} method will resume where the last match left off,

  *    unless the matcher is reset.  </p></li>

  *

  *    <li><p> In Perl, embedded flags at the top level of an expression affect

  *    the whole expression.  In this class, embedded flags always take effect

  *    at the point at which they appear, whether they are at the top level or

  *    within a group; in the latter case, flags are restored at the end of the

  *    group just as in Perl.  </p></li>

  *

  * </ul>

  *

  *

  * <p> For a more precise description of the behavior of regular expression

  * constructs, please see <a href="http://www.oreilly.com/catalog/regex3/">

  * <i>Mastering Regular Expressions, 3nd Edition</i>, Jeffrey E. F. Friedl,

  * O'Reilly and Associates, 2006.</a>

  * </p>

  *

  * @see java.lang.String#split(String, int)

  * @see java.lang.String#split(String)

  *

  * @author      Mike McCloskey

  * @author      Mark Reinhold

  * @author      JSR-51 Expert Group

  * @since       1.4

  * @spec        JSR-51

  */

 public final class Pattern

     implements java.io.Serializable

 {

     /**

      * Regular expression modifier values.  Instead of being passed as

      * arguments, they can also be passed as inline modifiers.

      * For example, the following statements have the same effect.

      * <pre>

      * RegExp r1 = RegExp.compile("abc", Pattern.I|Pattern.M);

      * RegExp r2 = RegExp.compile("(?im)abc", 0);

      * </pre>

      *

      * The flags are duplicated so that the familiar Perl match flag

      * names are available.

      */

     /**

      * Enables Unix lines mode.

      *

      * <p> In this mode, only the <tt>'\n'</tt> line terminator is recognized

      * in the behavior of <tt>.</tt>, <tt>^</tt>, and <tt>$</tt>.

      *

      * <p> Unix lines mode can also be enabled via the embedded flag

      * expression&nbsp;<tt>(?d)</tt>.

      */

     public static final int UNIX_LINES = 0x01;

     /**

      * Enables case-insensitive matching.

      *

      * <p> By default, case-insensitive matching assumes that only characters

      * in the US-ASCII charset are being matched.  Unicode-aware

      * case-insensitive matching can be enabled by specifying the {@link

      * #UNICODE_CASE} flag in conjunction with this flag.

      *

      * <p> Case-insensitive matching can also be enabled via the embedded flag

      * expression&nbsp;<tt>(?i)</tt>.

      *

      * <p> Specifying this flag may impose a slight performance penalty.  </p>

      */

     public static final int CASE_INSENSITIVE = 0x02;

     /**

      * Permits whitespace and comments in pattern.

      *

      * <p> In this mode, whitespace is ignored, and embedded comments starting

      * with <tt>#</tt> are ignored until the end of a line.

      *

      * <p> Comments mode can also be enabled via the embedded flag

      * expression&nbsp;<tt>(?x)</tt>.

      */

     public static final int COMMENTS = 0x04;

     /**

      * Enables multiline mode.

      *

      * <p> In multiline mode the expressions <tt>^</tt> and <tt>$</tt> match

      * just after or just before, respectively, a line terminator or the end of

      * the input sequence.  By default these expressions only match at the

      * beginning and the end of the entire input sequence.

      *

      * <p> Multiline mode can also be enabled via the embedded flag

      * expression&nbsp;<tt>(?m)</tt>.  </p>

      */

     public static final int MULTILINE = 0x08;

     /**

      * Enables literal parsing of the pattern.

      *

      * <p> When this flag is specified then the input string that specifies

      * the pattern is treated as a sequence of literal characters.

      * Metacharacters or escape sequences in the input sequence will be

      * given no special meaning.

      *

      * <p>The flags CASE_INSENSITIVE and UNICODE_CASE retain their impact on

      * matching when used in conjunction with this flag. The other flags

      * become superfluous.

      *

      * <p> There is no embedded flag character for enabling literal parsing.

      * @since 1.5

      */

     public static final int LITERAL = 0x10;

     /**

      * Enables dotall mode.

      *

      * <p> In dotall mode, the expression <tt>.</tt> matches any character,

      * including a line terminator.  By default this expression does not match

      * line terminators.

      *

      * <p> Dotall mode can also be enabled via the embedded flag

      * expression&nbsp;<tt>(?s)</tt>.  (The <tt>s</tt> is a mnemonic for

      * "single-line" mode, which is what this is called in Perl.)  </p>

      */

     public static final int DOTALL = 0x20;

     /**

      * Enables Unicode-aware case folding.

      *

      * <p> When this flag is specified then case-insensitive matching, when

      * enabled by the {@link #CASE_INSENSITIVE} flag, is done in a manner

      * consistent with the Unicode Standard.  By default, case-insensitive

      * matching assumes that only characters in the US-ASCII charset are being

      * matched.

      *

      * <p> Unicode-aware case folding can also be enabled via the embedded flag

      * expression&nbsp;<tt>(?u)</tt>.

      *

      * <p> Specifying this flag may impose a performance penalty.  </p>

      */

     public static final int UNICODE_CASE = 0x40;

     /**

      * Enables canonical equivalence.

      *

      * <p> When this flag is specified then two characters will be considered

      * to match if, and only if, their full canonical decompositions match.

      * The expression <tt>"a&#92;u030A"</tt>, for example, will match the

      * string <tt>"&#92;u00E5"</tt> when this flag is specified.  By default,

      * matching does not take canonical equivalence into account.

      *

      * <p> There is no embedded flag character for enabling canonical

      * equivalence.

      *

      * <p> Specifying this flag may impose a performance penalty.  </p>

      */

     public static final int CANON_EQ = 0x80;

     /**

      * Enables the Unicode version of <i>Predefined character classes</i> and

      * <i>POSIX character classes</i>.

      *

      * <p> When this flag is specified then the (US-ASCII only)

      * <i>Predefined character classes</i> and <i>POSIX character classes</i>

      * are in conformance with

      * <a href="http://www.unicode.org/reports/tr18/"><i>Unicode Technical

      * Standard #18: Unicode Regular Expression</i></a>

      * <i>Annex C: Compatibility Properties</i>.

      * <p>

      * The UNICODE_CHARACTER_CLASS mode can also be enabled via the embedded

      * flag expression&nbsp;<tt>(?U)</tt>.

      * <p>

      * The flag implies UNICODE_CASE, that is, it enables Unicode-aware case

      * folding.

      * <p>

      * Specifying this flag may impose a performance penalty.  </p>

      * @since 1.7

      */

     public static final int UNICODE_CHARACTER_CLASS = 0x100;

     /* Pattern has only two serialized components: The pattern string

      * and the flags, which are all that is needed to recompile the pattern

      * when it is deserialized.

      */

     /** use serialVersionUID from Merlin b59 for interoperability */

     private static final long serialVersionUID = 5073258162644648461L;

     /**

      * The original regular-expression pattern string.

      *

      * @serial

      */

     private String pattern;

     /**

      * The original pattern flags.

      *

      * @serial

      */

     private int flags;

     /**

      * Boolean indicating this Pattern is compiled; this is necessary in order

      * to lazily compile deserialized Patterns.

      */

     private transient volatile boolean compiled = false;

     /**

      * The normalized pattern string.

      */

     private transient String normalizedPattern;

     /**

      * The starting point of state machine for the find operation.  This allows

      * a match to start anywhere in the input.

      */

     transient Node root;

     /**

      * The root of object tree for a match operation.  The pattern is matched

      * at the beginning.  This may include a find that uses BnM or a First

      * node.

      */

     transient Node matchRoot;

     /**

      * Temporary storage used by parsing pattern slice.

      */

     transient int[] buffer;

     /**

      * Map the "name" of the "named capturing group" to its group id

      * node.

      */

     transient volatile Map<String, Integer> namedGroups;

     /**

      * Temporary storage used while parsing group references.

      */

     transient GroupHead[] groupNodes;

     /**

      * Temporary null terminated code point array used by pattern compiling.

      */

     private transient int[] temp;

     /**

      * The number of capturing groups in this Pattern. Used by matchers to

      * allocate storage needed to perform a match.

      */

     transient int capturingGroupCount;

     /**

      * The local variable count used by parsing tree. Used by matchers to

      * allocate storage needed to perform a match.

      */

     transient int localCount;

     /**

      * Index into the pattern string that keeps track of how much has been

      * parsed.

      */

     private transient int cursor;

     /**

      * Holds the length of the pattern string.

      */

     private transient int patternLength;

     /**

      * If the Start node might possibly match supplementary characters.

      * It is set to true during compiling if

      * (1) There is supplementary char in pattern, or

      * (2) There is complement node of Category or Block

      */

     private transient boolean hasSupplementary;

     /**

      * Compiles the given regular expression into a pattern.  </p>

      *

      * @param  regex

      *         The expression to be compiled

      *

      * @throws  PatternSyntaxException

      *          If the expression's syntax is invalid

      */

     public static Pattern compile(String regex) {

         return new Pattern(regex, 0);

     }

     /**

      * Compiles the given regular expression into a pattern with the given

      * flags.  </p>

      *

      * @param  regex

      *         The expression to be compiled

      *

      * @param  flags

      *         Match flags, a bit mask that may include

      *         {@link #CASE_INSENSITIVE}, {@link #MULTILINE}, {@link #DOTALL},

      *         {@link #UNICODE_CASE}, {@link #CANON_EQ}, {@link #UNIX_LINES},

      *         {@link #LITERAL}, {@link #UNICODE_CHARACTER_CLASS}

      *         and {@link #COMMENTS}

      *

      * @throws  IllegalArgumentException

      *          If bit values other than those corresponding to the defined

      *          match flags are set in <tt>flags</tt>

      *

      * @throws  PatternSyntaxException

      *          If the expression's syntax is invalid

      */

     public static Pattern compile(String regex, int flags) {

         return new Pattern(regex, flags);

     }

     /**

      * Returns the regular expression from which this pattern was compiled.

      * </p>

      *

      * @return  The source of this pattern

      */

     public String pattern() {

         return pattern;

     }

     /**

      * <p>Returns the string representation of this pattern. This

      * is the regular expression from which this pattern was

      * compiled.</p>

      *

      * @return  The string representation of this pattern

      * @since 1.5

      */

     public String toString() {

         return pattern;

     }

     /**

      * Creates a matcher that will match the given input against this pattern.

      * </p>

      *

      * @param  input

      *         The character sequence to be matched

      *

      * @return  A new matcher for this pattern

      */

     public Matcher matcher(CharSequence input) {

         if (!compiled) {

             synchronized(this) {

                 if (!compiled)

                     compile();

             }

         }

         Matcher m = new Matcher(this, input);

         return m;

     }

     /**

      * Returns this pattern's match flags.  </p>

      *

      * @return  The match flags specified when this pattern was compiled

      */

     public int flags() {

         return flags;

     }

     /**

      * Compiles the given regular expression and attempts to match the given

      * input against it.

      *

      * <p> An invocation of this convenience method of the form

      *

      * <blockquote><pre>

      * Pattern.matches(regex, input);</pre></blockquote>

      *

      * behaves in exactly the same way as the expression

      *

      * <blockquote><pre>

      * Pattern.compile(regex).matcher(input).matches()</pre></blockquote>

      *

      * <p> If a pattern is to be used multiple times, compiling it once and reusing

      * it will be more efficient than invoking this method each time.  </p>

      *

      * @param  regex

      *         The expression to be compiled

      *

      * @param  input

      *         The character sequence to be matched

      *

      * @throws  PatternSyntaxException

      *          If the expression's syntax is invalid

      */

     public static boolean matches(String regex, CharSequence input) {

         Pattern p = Pattern.compile(regex);

         Matcher m = p.matcher(input);

         return m.matches();

     }

     /**

      * Splits the given input sequence around matches of this pattern.

      *

      * <p> The array returned by this method contains each substring of the

      * input sequence that is terminated by another subsequence that matches

      * this pattern or is terminated by the end of the input sequence.  The

      * substrings in the array are in the order in which they occur in the

      * input.  If this pattern does not match any subsequence of the input then

      * the resulting array has just one element, namely the input sequence in

      * string form.

      *

      * <p> The <tt>limit</tt> parameter controls the number of times the

      * pattern is applied and therefore affects the length of the resulting

      * array.  If the limit <i>n</i> is greater than zero then the pattern

      * will be applied at most <i>n</i>&nbsp;-&nbsp;1 times, the array's

      * length will be no greater than <i>n</i>, and the array's last entry

      * will contain all input beyond the last matched delimiter.  If <i>n</i>

      * is non-positive then the pattern will be applied as many times as

      * possible and the array can have any length.  If <i>n</i> is zero then

      * the pattern will be applied as many times as possible, the array can

      * have any length, and trailing empty strings will be discarded.

      *

      * <p> The input <tt>"boo:and:foo"</tt>, for example, yields the following

      * results with these parameters:

      *

      * <blockquote><table cellpadding=1 cellspacing=0

      *              summary="Split examples showing regex, limit, and result">

      * <tr><th><P align="left"><i>Regex&nbsp;&nbsp;&nbsp;&nbsp;</i></th>

      *     <th><P align="left"><i>Limit&nbsp;&nbsp;&nbsp;&nbsp;</i></th>

      *     <th><P align="left"><i>Result&nbsp;&nbsp;&nbsp;&nbsp;</i></th></tr>

      * <tr><td align=center>:</td>

      *     <td align=center>2</td>

      *     <td><tt>{ "boo", "and:foo" }</tt></td></tr>

      * <tr><td align=center>:</td>

      *     <td align=center>5</td>

      *     <td><tt>{ "boo", "and", "foo" }</tt></td></tr>

      * <tr><td align=center>:</td>

      *     <td align=center>-2</td>

      *     <td><tt>{ "boo", "and", "foo" }</tt></td></tr>

      * <tr><td align=center>o</td>

      *     <td align=center>5</td>

      *     <td><tt>{ "b", "", ":and:f", "", "" }</tt></td></tr>

      * <tr><td align=center>o</td>

      *     <td align=center>-2</td>

      *     <td><tt>{ "b", "", ":and:f", "", "" }</tt></td></tr>

      * <tr><td align=center>o</td>

      *     <td align=center>0</td>

      *     <td><tt>{ "b", "", ":and:f" }</tt></td></tr>

      * </table></blockquote>

      *

      *

      * @param  input

      *         The character sequence to be split

      *

      * @param  limit

      *         The result threshold, as described above

      *

      * @return  The array of strings computed by splitting the input

      *          around matches of this pattern

      */

     public String[] split(CharSequence input, int limit) {

         int index = 0;

         boolean matchLimited = limit > 0;

         ArrayList<String> matchList = new ArrayList<>();

         Matcher m = matcher(input);

         // Add segments before each match found

         while(m.find()) {

             if (!matchLimited || matchList.size() < limit - 1) {

                 String match = input.subSequence(index, m.start()).toString();

                 matchList.add(match);

                 index = m.end();

             } else if (matchList.size() == limit - 1) { // last one

                 String match = input.subSequence(index,

                                                  input.length()).toString();

                 matchList.add(match);

                 index = m.end();

             }

         }

         // If no match was found, return this

         if (index == 0)

             return new String[] {input.toString()};

         // Add remaining segment

         if (!matchLimited || matchList.size() < limit)

             matchList.add(input.subSequence(index, input.length()).toString());

         // Construct result

         int resultSize = matchList.size();

         if (limit == 0)

             while (resultSize > 0 && matchList.get(resultSize-1).equals(""))

                 resultSize--;

         String[] result = new String[resultSize];

         return matchList.subList(0, resultSize).toArray(result);

     }

     /**

      * Splits the given input sequence around matches of this pattern.

      *

      * <p> This method works as if by invoking the two-argument {@link

      * #split(java.lang.CharSequence, int) split} method with the given input

      * sequence and a limit argument of zero.  Trailing empty strings are

      * therefore not included in the resulting array. </p>

      *

      * <p> The input <tt>"boo:and:foo"</tt>, for example, yields the following

      * results with these expressions:

      *

      * <blockquote><table cellpadding=1 cellspacing=0

      *              summary="Split examples showing regex and result">

      * <tr><th><P align="left"><i>Regex&nbsp;&nbsp;&nbsp;&nbsp;</i></th>

      *     <th><P align="left"><i>Result</i></th></tr>

      * <tr><td align=center>:</td>

      *     <td><tt>{ "boo", "and", "foo" }</tt></td></tr>

      * <tr><td align=center>o</td>

      *     <td><tt>{ "b", "", ":and:f" }</tt></td></tr>

      * </table></blockquote>

      *

      *

      * @param  input

      *         The character sequence to be split

      *

      * @return  The array of strings computed by splitting the input

      *          around matches of this pattern

      */

     public String[] split(CharSequence input) {

         return split(input, 0);

     }

     /**

      * Returns a literal pattern <code>String</code> for the specified

      * <code>String</code>.

      *

      * <p>This method produces a <code>String</code> that can be used to

      * create a <code>Pattern</code> that would match the string

      * <code>s</code> as if it were a literal pattern.</p> Metacharacters

      * or escape sequences in the input sequence will be given no special

      * meaning.

      *

      * @param  s The string to be literalized

      * @return  A literal string replacement

      * @since 1.5

      */

     public static String quote(String s) {

         int slashEIndex = s.indexOf("\\E");

         if (slashEIndex == -1)

             return "\\Q" + s + "\\E";

         StringBuilder sb = new StringBuilder(s.length() * 2);

         sb.append("\\Q");

         slashEIndex = 0;

         int current = 0;

         while ((slashEIndex = s.indexOf("\\E", current)) != -1) {

             sb.append(s.substring(current, slashEIndex));

             current = slashEIndex + 2;

             sb.append("\\E\\\\E\\Q");

         }

         sb.append(s.substring(current, s.length()));

         sb.append("\\E");

         return sb.toString();

     }

     /**

      * Recompile the Pattern instance from a stream.  The original pattern

      * string is read in and the object tree is recompiled from it.

      */

     private void readObject(java.io.ObjectInputStream s)

         throws java.io.IOException, ClassNotFoundException {

         // Read in all fields

         s.defaultReadObject();

         // Initialize counts

         capturingGroupCount = 1;

         localCount = 0;

         // if length > 0, the Pattern is lazily compiled

         compiled = false;

         if (pattern.length() == 0) {

             root = new Start(lastAccept);

             matchRoot = lastAccept;

             compiled = true;

         }

     }

     /**

      * This private constructor is used to create all Patterns. The pattern

      * string and match flags are all that is needed to completely describe

      * a Pattern. An empty pattern string results in an object tree with

      * only a Start node and a LastNode node.

      */

     private Pattern(String p, int f) {

         pattern = p;

         flags = f;

         // to use UNICODE_CASE if UNICODE_CHARACTER_CLASS present

         if ((flags & UNICODE_CHARACTER_CLASS) != 0)

             flags |= UNICODE_CASE;

         // Reset group index count

         capturingGroupCount = 1;

         localCount = 0;

         if (pattern.length() > 0) {

             compile();

         } else {

             root = new Start(lastAccept);

             matchRoot = lastAccept;

         }

     }

     /**

      * The pattern is converted to normalizedD form and then a pure group

      * is constructed to match canonical equivalences of the characters.

      */

     private void normalize() {

         boolean inCharClass = false;

         int lastCodePoint = -1;

         // Convert pattern into normalizedD form

         normalizedPattern = Normalizer.normalize(pattern, Normalizer.Form.NFD);

         patternLength = normalizedPattern.length();

         // Modify pattern to match canonical equivalences

         StringBuilder newPattern = new StringBuilder(patternLength);

         for(int i=0; i<patternLength; ) {

             int c = normalizedPattern.codePointAt(i);

             StringBuilder sequenceBuffer;

             if ((Character.getType(c) == Character.NON_SPACING_MARK)

                 && (lastCodePoint != -1)) {

                 sequenceBuffer = new StringBuilder();

                 sequenceBuffer.appendCodePoint(lastCodePoint);

                 sequenceBuffer.appendCodePoint(c);

                 while(Character.getType(c) == Character.NON_SPACING_MARK) {

                     i += Character.charCount(c);

                     if (i >= patternLength)

                         break;

                     c = normalizedPattern.codePointAt(i);

                     sequenceBuffer.appendCodePoint(c);

                 }

                 String ea = produceEquivalentAlternation(

                                                sequenceBuffer.toString());

                 newPattern.setLength(newPattern.length()-Character.charCount(lastCodePoint));

                 newPattern.append("(?:").append(ea).append(")");

             } else if (c == '[' && lastCodePoint != '\\') {

                 i = normalizeCharClass(newPattern, i);

             } else {

                 newPattern.appendCodePoint(c);

             }

             lastCodePoint = c;

             i += Character.charCount(c);

         }

         normalizedPattern = newPattern.toString();

     }

     /**

      * Complete the character class being parsed and add a set

      * of alternations to it that will match the canonical equivalences

      * of the characters within the class.

      */

     private int normalizeCharClass(StringBuilder newPattern, int i) {

         StringBuilder charClass = new StringBuilder();

         StringBuilder eq = null;

         int lastCodePoint = -1;

         String result;

         i++;

         charClass.append("[");

         while(true) {

             int c = normalizedPattern.codePointAt(i);

             StringBuilder sequenceBuffer;

             if (c == ']' && lastCodePoint != '\\') {

                 charClass.append((char)c);

                 break;

             } else if (Character.getType(c) == Character.NON_SPACING_MARK) {

                 sequenceBuffer = new StringBuilder();

                 sequenceBuffer.appendCodePoint(lastCodePoint);

                 while(Character.getType(c) == Character.NON_SPACING_MARK) {

                     sequenceBuffer.appendCodePoint(c);

                     i += Character.charCount(c);

                     if (i >= normalizedPattern.length())

                         break;

                     c = normalizedPattern.codePointAt(i);

                 }

                 String ea = produceEquivalentAlternation(

                                                   sequenceBuffer.toString());

                 charClass.setLength(charClass.length()-Character.charCount(lastCodePoint));

                 if (eq == null)

                     eq = new StringBuilder();

                 eq.append('|');

                 eq.append(ea);

             } else {

                 charClass.appendCodePoint(c);

                 i++;

             }

             if (i == normalizedPattern.length())

                 throw error("Unclosed character class");

             lastCodePoint = c;

         }

         if (eq != null) {

             result = "(?:"+charClass.toString()+eq.toString()+")";

         } else {

             result = charClass.toString();

         }

         newPattern.append(result);

         return i;

     }

     /**

      * Given a specific sequence composed of a regular character and

      * combining marks that follow it, produce the alternation that will

      * match all canonical equivalences of that sequence.

      */

     private String produceEquivalentAlternation(String source) {

         int len = countChars(source, 0, 1);

         if (source.length() == len)

             // source has one character.

             return source;

         String base = source.substring(0,len);

         String combiningMarks = source.substring(len);

         String[] perms = producePermutations(combiningMarks);

         StringBuilder result = new StringBuilder(source);

         // Add combined permutations

         for(int x=0; x<perms.length; x++) {

             String next = base + perms[x];

             if (x>0)

                 result.append("|"+next);

             next = composeOneStep(next);

             if (next != null)

                 result.append("|"+produceEquivalentAlternation(next));

         }

         return result.toString();

     }

     /**

      * Returns an array of strings that have all the possible

      * permutations of the characters in the input string.

      * This is used to get a list of all possible orderings

      * of a set of combining marks. Note that some of the permutations

      * are invalid because of combining class collisions, and these

      * possibilities must be removed because they are not canonically

      * equivalent.

      */

     private String[] producePermutations(String input) {

         if (input.length() == countChars(input, 0, 1))

             return new String[] {input};

         if (input.length() == countChars(input, 0, 2)) {

             int c0 = Character.codePointAt(input, 0);

             int c1 = Character.codePointAt(input, Character.charCount(c0));

             if (getClass(c1) == getClass(c0)) {

                 return new String[] {input};

             }

             String[] result = new String[2];

             result[0] = input;

             StringBuilder sb = new StringBuilder(2);

             sb.appendCodePoint(c1);

             sb.appendCodePoint(c0);

             result[1] = sb.toString();

             return result;

         }

         int length = 1;

         int nCodePoints = countCodePoints(input);

         for(int x=1; x<nCodePoints; x++)

             length = length * (x+1);

         String[] temp = new String[length];

         int combClass[] = new int[nCodePoints];

         for(int x=0, i=0; x<nCodePoints; x++) {

             int c = Character.codePointAt(input, i);

             combClass[x] = getClass(c);

             i +=  Character.charCount(c);

         }

         // For each char, take it out and add the permutations

         // of the remaining chars

         int index = 0;

         int len;

         // offset maintains the index in code units.

 loop:   for(int x=0, offset=0; x<nCodePoints; x++, offset+=len) {

             len = countChars(input, offset, 1);

             boolean skip = false;

             for(int y=x-1; y>=0; y--) {

                 if (combClass[y] == combClass[x]) {

                     continue loop;

                 }

             }

             StringBuilder sb = new StringBuilder(input);

             String otherChars = sb.delete(offset, offset+len).toString();

             String[] subResult = producePermutations(otherChars);

             String prefix = input.substring(offset, offset+len);

             for(int y=0; y<subResult.length; y++)

                 temp[index++] =  prefix + subResult[y];

         }

         String[] result = new String[index];

         for (int x=0; x<index; x++)

             result[x] = temp[x];

         return result;

     }

     private int getClass(int c) {

         return sun.text.Normalizer.getCombiningClass(c);

     }

     /**

      * Attempts to compose input by combining the first character

      * with the first combining mark following it. Returns a String

      * that is the composition of the leading character with its first

      * combining mark followed by the remaining combining marks. Returns

      * null if the first two characters cannot be further composed.

      */

     private String composeOneStep(String input) {

         int len = countChars(input, 0, 2);

         String firstTwoCharacters = input.substring(0, len);

         String result = Normalizer.normalize(firstTwoCharacters, Normalizer.Form.NFC);

         if (result.equals(firstTwoCharacters))

             return null;

         else {

             String remainder = input.substring(len);

             return result + remainder;

         }

     }

     /**

      * Preprocess any \Q...\E sequences in `temp', meta-quoting them.

      * See the description of `quotemeta' in perlfunc(1).

      */

     private void RemoveQEQuoting() {

         final int pLen = patternLength;

         int i = 0;

         while (i < pLen-1) {

             if (temp[i] != '\\')

                 i += 1;

             else if (temp[i + 1] != 'Q')

                 i += 2;

             else

                 break;

         }

         if (i >= pLen - 1)    // No \Q sequence found

             return;

         int j = i;

         i += 2;

         int[] newtemp = new int[j + 2*(pLen-i) + 2];

         System.arraycopy(temp, 0, newtemp, 0, j);

         boolean inQuote = true;

         while (i < pLen) {

             int c = temp[i++];

             if (! ASCII.isAscii(c) || ASCII.isAlnum(c)) {

                 newtemp[j++] = c;

             } else if (c != '\\') {

                 if (inQuote) newtemp[j++] = '\\';

                 newtemp[j++] = c;

             } else if (inQuote) {

                 if (temp[i] == 'E') {

                     i++;

                     inQuote = false;

                 } else {

                     newtemp[j++] = '\\';

                     newtemp[j++] = '\\';

                 }

             } else {

                 if (temp[i] == 'Q') {

                     i++;

                     inQuote = true;

                 } else {

                     newtemp[j++] = c;

                     if (i != pLen)

                         newtemp[j++] = temp[i++];

                 }

             }

         }

         patternLength = j;

         temp = Arrays.copyOf(newtemp, j + 2); // double zero termination

     }

     /**

      * Copies regular expression to an int array and invokes the parsing

      * of the expression which will create the object tree.

      */

     private void compile() {

         // Handle canonical equivalences

         if (has(CANON_EQ) && !has(LITERAL)) {

             normalize();

         } else {

             normalizedPattern = pattern;

         }

         patternLength = normalizedPattern.length();

         // Copy pattern to int array for convenience

         // Use double zero to terminate pattern

         temp = new int[patternLength + 2];

         hasSupplementary = false;

         int c, count = 0;

         // Convert all chars into code points

         for (int x = 0; x < patternLength; x += Character.charCount(c)) {

             c = normalizedPattern.codePointAt(x);

             if (isSupplementary(c)) {

                 hasSupplementary = true;

             }

             temp[count++] = c;

         }

         patternLength = count;   // patternLength now in code points

         if (! has(LITERAL))

             RemoveQEQuoting();

         // Allocate all temporary objects here.

         buffer = new int[32];

         groupNodes = new GroupHead[10];

         namedGroups = null;

         if (has(LITERAL)) {

             // Literal pattern handling

             matchRoot = newSlice(temp, patternLength, hasSupplementary);

             matchRoot.next = lastAccept;

         } else {

             // Start recursive descent parsing

             matchRoot = expr(lastAccept);

             // Check extra pattern characters

             if (patternLength != cursor) {

                 if (peek() == ')') {

                     throw error("Unmatched closing ')'");

                 } else {

                     throw error("Unexpected internal error");

                 }

             }

         }

         // Peephole optimization

         if (matchRoot instanceof Slice) {

             root = BnM.optimize(matchRoot);

             if (root == matchRoot) {

                 root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);

             }

         } else if (matchRoot instanceof Begin || matchRoot instanceof First) {

             root = matchRoot;

         } else {

             root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);

         }

         // Release temporary storage

         temp = null;

         buffer = null;

         groupNodes = null;

         patternLength = 0;

         compiled = true;

     }

     Map<String, Integer> namedGroups() {

         if (namedGroups == null)

             namedGroups = new HashMap<>(2);

         return namedGroups;

     }

     /**

      * Used to print out a subtree of the Pattern to help with debugging.

      */

     private static void printObjectTree(Node node) {

         while(node != null) {

             if (node instanceof Prolog) {

                 System.out.println(node);

                 printObjectTree(((Prolog)node).loop);

                 System.out.println("**** end contents prolog loop");

             } else if (node instanceof Loop) {

                 System.out.println(node);

                 printObjectTree(((Loop)node).body);

                 System.out.println("**** end contents Loop body");

             } else if (node instanceof Curly) {

                 System.out.println(node);

                 printObjectTree(((Curly)node).atom);

                 System.out.println("**** end contents Curly body");

             } else if (node instanceof GroupCurly) {

                 System.out.println(node);

                 printObjectTree(((GroupCurly)node).atom);

                 System.out.println("**** end contents GroupCurly body");

             } else if (node instanceof GroupTail) {

                 System.out.println(node);

                 System.out.println("Tail next is "+node.next);

                 return;

             } else {

                 System.out.println(node);

             }

             node = node.next;

             if (node != null)

                 System.out.println("->next:");

             if (node == Pattern.accept) {

                 System.out.println("Accept Node");

                 node = null;

             }

        }

     }

     /**

      * Used to accumulate information about a subtree of the object graph

      * so that optimizations can be applied to the subtree.

      */

     static final class TreeInfo {

         int minLength;

         int maxLength;

         boolean maxValid;

         boolean deterministic;

         TreeInfo() {

             reset();

         }

         void reset() {

             minLength = 0;

             maxLength = 0;

             maxValid = true;

             deterministic = true;

         }

     }

     /*

      * The following private methods are mainly used to improve the

      * readability of the code. In order to let the Java compiler easily

      * inline them, we should not put many assertions or error checks in them.

      */

     /**

      * Indicates whether a particular flag is set or not.

      */

     private boolean has(int f) {

         return (flags & f) != 0;

     }

     /**

      * Match next character, signal error if failed.

      */

     private void accept(int ch, String s) {

         int testChar = temp[cursor++];

         if (has(COMMENTS))

             testChar = parsePastWhitespace(testChar);

         if (ch != testChar) {

             throw error(s);

         }

     }

     /**

      * Mark the end of pattern with a specific character.

      */

     private void mark(int c) {

         temp[patternLength] = c;

     }

     /**

      * Peek the next character, and do not advance the cursor.

      */

     private int peek() {

         int ch = temp[cursor];

         if (has(COMMENTS))

             ch = peekPastWhitespace(ch);

         return ch;

     }

     /**

      * Read the next character, and advance the cursor by one.

      */

     private int read() {

         int ch = temp[cursor++];

         if (has(COMMENTS))

             ch = parsePastWhitespace(ch);

         return ch;

     }

     /**

      * Read the next character, and advance the cursor by one,

      * ignoring the COMMENTS setting

      */

     private int readEscaped() {

         int ch = temp[cursor++];

         return ch;

     }

     /**

      * Advance the cursor by one, and peek the next character.

      */

     private int next() {

         int ch = temp[++cursor];

         if (has(COMMENTS))

             ch = peekPastWhitespace(ch);

         return ch;

     }

     /**

      * Advance the cursor by one, and peek the next character,

      * ignoring the COMMENTS setting

      */

     private int nextEscaped() {

         int ch = temp[++cursor];

         return ch;

     }

     /**

      * If in xmode peek past whitespace and comments.

      */

     private int peekPastWhitespace(int ch) {

         while (ASCII.isSpace(ch) || ch == '#') {

             while (ASCII.isSpace(ch))

                 ch = temp[++cursor];

             if (ch == '#') {

                 ch = peekPastLine();

             }

         }

         return ch;

     }

     /**

      * If in xmode parse past whitespace and comments.

      */

     private int parsePastWhitespace(int ch) {

         while (ASCII.isSpace(ch) || ch == '#') {

             while (ASCII.isSpace(ch))

                 ch = temp[cursor++];

             if (ch == '#')

                 ch = parsePastLine();

         }

         return ch;

     }

     /**

      * xmode parse past comment to end of line.

      */

     private int parsePastLine() {

         int ch = temp[cursor++];

         while (ch != 0 && !isLineSeparator(ch))

             ch = temp[cursor++];

         return ch;

     }

     /**

      * xmode peek past comment to end of line.

      */

     private int peekPastLine() {

         int ch = temp[++cursor];

         while (ch != 0 && !isLineSeparator(ch))

             ch = temp[++cursor];

         return ch;

     }

     /**

      * Determines if character is a line separator in the current mode

      */

     private boolean isLineSeparator(int ch) {

         if (has(UNIX_LINES)) {

             return ch == '\n';

         } else {

             return (ch == '\n' ||

                     ch == '\r' ||

                     (ch|1) == '\u2029' ||

                     ch == '\u0085');

         }

     }

     /**

      * Read the character after the next one, and advance the cursor by two.

      */

     private int skip() {

         int i = cursor;

         int ch = temp[i+1];

         cursor = i + 2;

         return ch;

     }

     /**

      * Unread one next character, and retreat cursor by one.

      */

     private void unread() {

         cursor--;

     }

     /**

      * Internal method used for handling all syntax errors. The pattern is

      * displayed with a pointer to aid in locating the syntax error.

      */

     private PatternSyntaxException error(String s) {

         return new PatternSyntaxException(s, normalizedPattern,  cursor - 1);

     }

     /**

      * Determines if there is any supplementary character or unpaired

      * surrogate in the specified range.

      */

     private boolean findSupplementary(int start, int end) {

         for (int i = start; i < end; i++) {

             if (isSupplementary(temp[i]))

                 return true;

         }

         return false;

     }

     /**

      * Determines if the specified code point is a supplementary

      * character or unpaired surrogate.

      */

     private static final boolean isSupplementary(int ch) {

         return ch >= Character.MIN_SUPPLEMENTARY_CODE_POINT ||

                Character.isSurrogate((char)ch);

     }

     /**

      *  The following methods handle the main parsing. They are sorted

      *  according to their precedence order, the lowest one first.

      */

     /**

      * The expression is parsed with branch nodes added for alternations.

      * This may be called recursively to parse sub expressions that may

      * contain alternations.

      */

     private Node expr(Node end) {

         Node prev = null;

         Node firstTail = null;

         Node branchConn = null;

         for (;;) {

             Node node = sequence(end);

             Node nodeTail = root;      //double return

             if (prev == null) {

                 prev = node;

                 firstTail = nodeTail;

             } else {

                 // Branch

                 if (branchConn == null) {

                     branchConn = new BranchConn();

                     branchConn.next = end;

                 }

                 if (node == end) {

                     // if the node returned from sequence() is "end"

                     // we have an empty expr, set a null atom into

                     // the branch to indicate to go "next" directly.

                     node = null;

                 } else {

                     // the "tail.next" of each atom goes to branchConn

                     nodeTail.next = branchConn;

                 }

                 if (prev instanceof Branch) {

                     ((Branch)prev).add(node);

                 } else {

                     if (prev == end) {

                         prev = null;

                     } else {

                         // replace the "end" with "branchConn" at its tail.next

                         // when put the "prev" into the branch as the first atom.

                         firstTail.next = branchConn;

                     }

                     prev = new Branch(prev, node, branchConn);

                 }

             }

             if (peek() != '|') {

                 return prev;

             }

             next();

         }

     }

     /**

      * Parsing of sequences between alternations.

      */

     private Node sequence(Node end) {

         Node head = null;

         Node tail = null;

         Node node = null;

     LOOP:

         for (;;) {

             int ch = peek();

             switch (ch) {

             case '(':

                 // Because group handles its own closure,

                 // we need to treat it differently

                 node = group0();

                 // Check for comment or flag group

                 if (node == null)

                     continue;

                 if (head == null)

                     head = node;

                 else

                     tail.next = node;

                 // Double return: Tail was returned in root

                 tail = root;

                 continue;

             case '[':

                 node = clazz(true);

                 break;

             case '\\':

                 ch = nextEscaped();

                 if (ch == 'p' || ch == 'P') {

                     boolean oneLetter = true;

                     boolean comp = (ch == 'P');

                     ch = next(); // Consume { if present

                     if (ch != '{') {

                         unread();

                     } else {

                         oneLetter = false;

                     }

                     node = family(oneLetter, comp);

                 } else {

                     unread();

                     node = atom();

                 }

                 break;

             case '^':

                 next();

                 if (has(MULTILINE)) {

                     if (has(UNIX_LINES))

                         node = new UnixCaret();

                     else

                         node = new Caret();

                 } else {

                     node = new Begin();

                 }

                 break;

             case '$':

                 next();

                 if (has(UNIX_LINES))

                     node = new UnixDollar(has(MULTILINE));

                 else

                     node = new Dollar(has(MULTILINE));

                 break;

             case '.':

                 next();

                 if (has(DOTALL)) {

                     node = new All();

                 } else {

                     if (has(UNIX_LINES))

                         node = new UnixDot();

                     else {

                         node = new Dot();

                     }

                 }

                 break;

             case '|':

             case ')':

                 break LOOP;

             case ']': // Now interpreting dangling ] and } as literals

             case '}':

                 node = atom();

                 break;

             case '?':

             case '*':

             case '+':

                 next();

                 throw error("Dangling meta character '" + ((char)ch) + "'");

             case 0:

                 if (cursor >= patternLength) {

                     break LOOP;

                 }

                 // Fall through

             default:

                 node = atom();

                 break;

             }

             node = closure(node);

             if (head == null) {

                 head = tail = node;

             } else {

                 tail.next = node;

                 tail = node;

             }

         }

         if (head == null) {

             return end;

         }

         tail.next = end;

         root = tail;      //double return

         return head;

     }

     /**

      * Parse and add a new Single or Slice.

      */

     private Node atom() {

         int first = 0;

         int prev = -1;

         boolean hasSupplementary = false;

         int ch = peek();

         for (;;) {

             switch (ch) {

             case '*':

             case '+':

             case '?':

             case '{':

                 if (first > 1) {

                     cursor = prev;    // Unwind one character

                     first--;

                 }

                 break;

             case '$':

             case '.':

             case '^':

             case '(':

             case '[':

             case '|':

             case ')':

                 break;

             case '\\':

                 ch = nextEscaped();

                 if (ch == 'p' || ch == 'P') { // Property

                     if (first > 0) { // Slice is waiting; handle it first

                         unread();

                         break;

                     } else { // No slice; just return the family node

                         boolean comp = (ch == 'P');

                         boolean oneLetter = true;

                         ch = next(); // Consume { if present

                         if (ch != '{')

                             unread();

                         else

                             oneLetter = false;

                         return family(oneLetter, comp);

                     }

                 }

                 unread();

                 prev = cursor;

                 ch = escape(false, first == 0);

                 if (ch >= 0) {

                     append(ch, first);

                     first++;

                     if (isSupplementary(ch)) {

                         hasSupplementary = true;

                     }

                     ch = peek();

                     continue;

                 } else if (first == 0) {

                     return root;

                 }

                 // Unwind meta escape sequence

                 cursor = prev;

                 break;

             case 0:

                 if (cursor >= patternLength) {

                     break;

                 }

                 // Fall through

             default:

                 prev = cursor;

                 append(ch, first);

                 first++;

                 if (isSupplementary(ch)) {

                     hasSupplementary = true;

                 }

                 ch = next();

                 continue;

             }

             break;

         }

         if (first == 1) {

             return newSingle(buffer[0]);

         } else {

             return newSlice(buffer, first, hasSupplementary);

         }

     }

     private void append(int ch, int len) {

         if (len >= buffer.length) {

             int[] tmp = new int[len+len];

             System.arraycopy(buffer, 0, tmp, 0, len);

             buffer = tmp;

         }

         buffer[len] = ch;

     }

     /**

      * Parses a backref greedily, taking as many numbers as it

      * can. The first digit is always treated as a backref, but

      * multi digit numbers are only treated as a backref if at

      * least that many backrefs exist at this point in the regex.

      */

     private Node ref(int refNum) {

         boolean done = false;

         while(!done) {

             int ch = peek();

             switch(ch) {

             case '0':

             case '1':

             case '2':

             case '3':

             case '4':

             case '5':

             case '6':

             case '7':

             case '8':

             case '9':

                 int newRefNum = (refNum * 10) + (ch - '0');

                 // Add another number if it doesn't make a group

                 // that doesn't exist

                 if (capturingGroupCount - 1 < newRefNum) {

                     done = true;

                     break;

                 }

                 refNum = newRefNum;

                 read();

                 break;

             default:

                 done = true;

                 break;

             }

         }

         if (has(CASE_INSENSITIVE))

             return new CIBackRef(refNum, has(UNICODE_CASE));

         else

             return new BackRef(refNum);

     }

     /**

      * Parses an escape sequence to determine the actual value that needs

      * to be matched.

      * If -1 is returned and create was true a new object was added to the tree

      * to handle the escape sequence.

      * If the returned value is greater than zero, it is the value that

      * matches the escape sequence.

      */

     private int escape(boolean inclass, boolean create) {

         int ch = skip();

         switch (ch) {

         case '0':

             return o();

         case '1':

         case '2':

         case '3':

         case '4':

         case '5':

         case '6':

         case '7':

         case '8':

         case '9':

             if (inclass) break;

             if (create) {

                 root = ref((ch - '0'));

             }

             return -1;

         case 'A':

             if (inclass) break;

             if (create) root = new Begin();

             return -1;

         case 'B':

             if (inclass) break;

             if (create) root = new Bound(Bound.NONE, has(UNICODE_CHARACTER_CLASS));

             return -1;

         case 'C':

             break;

         case 'D':

             if (create) root = has(UNICODE_CHARACTER_CLASS)

                                ? new Utype(UnicodeProp.DIGIT).complement()

                                : new Ctype(ASCII.DIGIT).complement();

             return -1;

         case 'E':

         case 'F':

             break;

         case 'G':

             if (inclass) break;

             if (create) root = new LastMatch();

             return -1;

         case 'H':

         case 'I':

         case 'J':

         case 'K':

         case 'L':

         case 'M':

         case 'N':

         case 'O':

         case 'P':

         case 'Q':

         case 'R':

             break;

         case 'S':

             if (create) root = has(UNICODE_CHARACTER_CLASS)

                                ? new Utype(UnicodeProp.WHITE_SPACE).complement()

                                : new Ctype(ASCII.SPACE).complement();

             return -1;

         case 'T':

         case 'U':

         case 'V':

             break;

         case 'W':

             if (create) root = has(UNICODE_CHARACTER_CLASS)

                                ? new Utype(UnicodeProp.WORD).complement()

                                : new Ctype(ASCII.WORD).complement();

             return -1;

         case 'X':

         case 'Y':

             break;

         case 'Z':

             if (inclass) break;

             if (create) {

                 if (has(UNIX_LINES))

                     root = new UnixDollar(false);

                 else

                     root = new Dollar(false);

             }

             return -1;

         case 'a':

             return '\007';

         case 'b':

             if (inclass) break;

             if (create) root = new Bound(Bound.BOTH, has(UNICODE_CHARACTER_CLASS));

             return -1;

         case 'c':

             return c();

         case 'd':

             if (create) root = has(UNICODE_CHARACTER_CLASS)

                                ? new Utype(UnicodeProp.DIGIT)

                                : new Ctype(ASCII.DIGIT);

             return -1;

         case 'e':

             return '\033';

         case 'f':

             return '\f';

         case 'g':

         case 'h':

         case 'i':

         case 'j':

             break;

         case 'k':

             if (inclass)

                 break;

             if (read() != '<')

                 throw error("\\k is not followed by '<' for named capturing group");

             String name = groupname(read());

             if (!namedGroups().containsKey(name))

                 throw error("(named capturing group <"+ name+"> does not exit");

             if (create) {

                 if (has(CASE_INSENSITIVE))

                     root = new CIBackRef(namedGroups().get(name), has(UNICODE_CASE));

                 else

                     root = new BackRef(namedGroups().get(name));

             }

             return -1;

         case 'l':

         case 'm':

             break;

         case 'n':

             return '\n';

         case 'o':

         case 'p':

         case 'q':

             break;

         case 'r':

             return '\r';

         case 's':

             if (create) root = has(UNICODE_CHARACTER_CLASS)

                                ? new Utype(UnicodeProp.WHITE_SPACE)

                                : new Ctype(ASCII.SPACE);

             return -1;

         case 't':

             return '\t';

         case 'u':

             return u();

         case 'v':

             return '\013';

         case 'w':

             if (create) root = has(UNICODE_CHARACTER_CLASS)

                                ? new Utype(UnicodeProp.WORD)

                                : new Ctype(ASCII.WORD);

             return -1;

         case 'x':

             return x();

         case 'y':

             break;

         case 'z':

             if (inclass) break;

             if (create) root = new End();

             return -1;

         default:

             return ch;

         }

         throw error("Illegal/unsupported escape sequence");

     }

     /**

      * Parse a character class, and return the node that matches it.

      *

      * Consumes a ] on the way out if consume is true. Usually consume

      * is true except for the case of [abc&&def] where def is a separate

      * right hand node with "understood" brackets.

      */

     private CharProperty clazz(boolean consume) {

         CharProperty prev = null;

         CharProperty node = null;

         BitClass bits = new BitClass();

         boolean include = true;

         boolean firstInClass = true;

         int ch = next();

         for (;;) {

             switch (ch) {

                 case '^':

                     // Negates if first char in a class, otherwise literal

                     if (firstInClass) {

                         if (temp[cursor-1] != '[')

                             break;

                         ch = next();

                         include = !include;

                         continue;

                     } else {

                         // ^ not first in class, treat as literal

                         break;

                     }

                 case '[':

                     firstInClass = false;

                     node = clazz(true);

                     if (prev == null)

                         prev = node;

                     else

                         prev = union(prev, node);

                     ch = peek();

                     continue;

                 case '&':

                     firstInClass = false;

                     ch = next();

                     if (ch == '&') {

                         ch = next();

                         CharProperty rightNode = null;

                         while (ch != ']' && ch != '&') {

                             if (ch == '[') {

                                 if (rightNode == null)

                                     rightNode = clazz(true);

                                 else

                                     rightNode = union(rightNode, clazz(true));

                             } else { // abc&&def

                                 unread();

                                 rightNode = clazz(false);

                             }

                             ch = peek();

                         }

                         if (rightNode != null)

                             node = rightNode;

                         if (prev == null) {

                             if (rightNode == null)

                                 throw error("Bad class syntax");

                             else

                                 prev = rightNode;

                         } else {

                             prev = intersection(prev, node);

                         }

                     } else {

                         // treat as a literal &

                         unread();

                         break;

                     }

                     continue;

                 case 0:

                     firstInClass = false;

                     if (cursor >= patternLength)

                         throw error("Unclosed character class");

                     break;

                 case ']':

                     firstInClass = false;

                     if (prev != null) {

                         if (consume)

                             next();

                         return prev;

                     }

                     break;

                 default:

                     firstInClass = false;

                     break;

             }

             node = range(bits);

             if (include) {

                 if (prev == null) {

                     prev = node;

                 } else {

                     if (prev != node)

                         prev = union(prev, node);

                 }

             } else {

                 if (prev == null) {

                     prev = node.complement();

                 } else {

                     if (prev != node)

                         prev = setDifference(prev, node);

                 }

             }

             ch = peek();

         }

     }

     private CharProperty bitsOrSingle(BitClass bits, int ch) {

         /* Bits can only handle codepoints in [u+0000-u+00ff] range.

            Use "single" node instead of bits when dealing with unicode

            case folding for codepoints listed below.

            (1)Uppercase out of range: u+00ff, u+00b5

               toUpperCase(u+00ff) -> u+0178

               toUpperCase(u+00b5) -> u+039c

            (2)LatinSmallLetterLongS u+17f

               toUpperCase(u+017f) -> u+0053

            (3)LatinSmallLetterDotlessI u+131

               toUpperCase(u+0131) -> u+0049

            (4)LatinCapitalLetterIWithDotAbove u+0130

               toLowerCase(u+0130) -> u+0069

            (5)KelvinSign u+212a

               toLowerCase(u+212a) ==> u+006B

            (6)AngstromSign u+212b

               toLowerCase(u+212b) ==> u+00e5

         */

         int d;

         if (ch < 256 &&

             !(has(CASE_INSENSITIVE) && has(UNICODE_CASE) &&

               (ch == 0xff || ch == 0xb5 ||

                ch == 0x49 || ch == 0x69 ||  //I and i

                ch == 0x53 || ch == 0x73 ||  //S and s

                ch == 0x4b || ch == 0x6b ||  //K and k

                ch == 0xc5 || ch == 0xe5)))  //A+ring

             return bits.add(ch, flags());

         return newSingle(ch);

     }

     /**

      * Parse a single character or a character range in a character class

      * and return its representative node.

      */

     private CharProperty range(BitClass bits) {

         int ch = peek();

         if (ch == '\\') {

             ch = nextEscaped();

             if (ch == 'p' || ch == 'P') { // A property

                 boolean comp = (ch == 'P');

                 boolean oneLetter = true;

                 // Consume { if present

                 ch = next();

                 if (ch != '{')

                     unread();

                 else

                     oneLetter = false;

                 return family(oneLetter, comp);

             } else { // ordinary escape

                 unread();

                 ch = escape(true, true);

                 if (ch == -1)

                     return (CharProperty) root;

             }

         } else {

             ch = single();

         }

         if (ch >= 0) {

             if (peek() == '-') {

                 int endRange = temp[cursor+1];

                 if (endRange == '[') {

                     return bitsOrSingle(bits, ch);

                 }

                 if (endRange != ']') {

                     next();

                     int m = single();

                     if (m < ch)

                         throw error("Illegal character range");

                     if (has(CASE_INSENSITIVE))

                         return caseInsensitiveRangeFor(ch, m);

                     else

                         return rangeFor(ch, m);

                 }

             }

             return bitsOrSingle(bits, ch);

         }

         throw error("Unexpected character '"+((char)ch)+"'");

     }

     private int single() {

         int ch = peek();

         switch (ch) {

         case '\\':

             return escape(true, false);

         default:

             next();

             return ch;

         }

     }

     /**

      * Parses a Unicode character family and returns its representative node.

      */

     private CharProperty family(boolean singleLetter,

                                 boolean maybeComplement)

     {

         next();

         String name;

         CharProperty node = null;

         if (singleLetter) {

             int c = temp[cursor];

             if (!Character.isSupplementaryCodePoint(c)) {

                 name = String.valueOf((char)c);

             } else {

                 name = new String(temp, cursor, 1);

             }

             read();

         } else {

             int i = cursor;

             mark('}');

             while(read() != '}') {

             }

             mark('\000');

             int j = cursor;

             if (j > patternLength)

                 throw error("Unclosed character family");

             if (i + 1 >= j)

                 throw error("Empty character family");

             name = new String(temp, i, j-i-1);

         }

         int i = name.indexOf('=');

         if (i != -1) {

             // property construct \p{name=value}