/*

 * Copyright (c) 1999, 2009, 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;

/**

 * An engine that performs match operations on a {@link java.lang.CharSequence

 * </code>character sequence<code>} by interpreting a {@link Pattern}.

 *

 * <p> A matcher is created from a pattern by invoking the pattern's {@link

 * Pattern#matcher matcher} method.  Once created, a matcher can be used to

 * perform three different kinds of match operations:

 *

 * <ul>

 *

 *   <li><p> The {@link #matches matches} method attempts to match the entire

 *   input sequence against the pattern.  </p></li>

 *

 *   <li><p> The {@link #lookingAt lookingAt} method attempts to match the

 *   input sequence, starting at the beginning, against the pattern.  </p></li>

 *

 *   <li><p> The {@link #find find} method scans the input sequence looking for

 *   the next subsequence that matches the pattern.  </p></li>

 *

 * </ul>

 *

 * <p> Each of these methods returns a boolean indicating success or failure.

 * More information about a successful match can be obtained by querying the

 * state of the matcher.

 *

 * <p> A matcher finds matches in a subset of its input called the

 * <i>region</i>. By default, the region contains all of the matcher's input.

 * The region can be modified via the{@link #region region} method and queried

 * via the {@link #regionStart regionStart} and {@link #regionEnd regionEnd}

 * methods. The way that the region boundaries interact with some pattern

 * constructs can be changed. See {@link #useAnchoringBounds

 * useAnchoringBounds} and {@link #useTransparentBounds useTransparentBounds}

 * for more details.

 *

 * <p> This class also defines methods for replacing matched subsequences with

 * new strings whose contents can, if desired, be computed from the match

 * result.  The {@link #appendReplacement appendReplacement} and {@link

 * #appendTail appendTail} methods can be used in tandem in order to collect

 * the result into an existing string buffer, or the more convenient {@link

 * #replaceAll replaceAll} method can be used to create a string in which every

 * matching subsequence in the input sequence is replaced.

 *

 * <p> The explicit state of a matcher includes the start and end indices of

 * the most recent successful match.  It also includes the start and end

 * indices of the input subsequence captured by each <a

 * href="Pattern.html#cg">capturing group</a> in the pattern as well as a total

 * count of such subsequences.  As a convenience, methods are also provided for

 * returning these captured subsequences in string form.

 *

 * <p> The explicit state of a matcher is initially undefined; attempting to

 * query any part of it before a successful match will cause an {@link

 * IllegalStateException} to be thrown.  The explicit state of a matcher is

 * recomputed by every match operation.

 *

 * <p> The implicit state of a matcher includes the input character sequence as

 * well as the <i>append position</i>, which is initially zero and is updated

 * by the {@link #appendReplacement appendReplacement} method.

 *

 * <p> A matcher may be reset explicitly by invoking its {@link #reset()}

 * method or, if a new input sequence is desired, its {@link

 * #reset(java.lang.CharSequence) reset(CharSequence)} method.  Resetting a

 * matcher discards its explicit state information and sets the append position

 * to zero.

 *

 * <p> Instances of this class are not safe for use by multiple concurrent

 * threads. </p>

 *

 *

 * @author      Mike McCloskey

 * @author      Mark Reinhold

 * @author      JSR-51 Expert Group

 * @since       1.4

 * @spec        JSR-51

 */

public final class Matcher implements MatchResult {

    /**

     * The Pattern object that created this Matcher.

     */

    Pattern parentPattern;

    /**

     * The storage used by groups. They may contain invalid values if

     * a group was skipped during the matching.

     */

    int[] groups;

    /**

     * The range within the sequence that is to be matched. Anchors

     * will match at these "hard" boundaries. Changing the region

     * changes these values.

     */

    int from, to;

    /**

     * Lookbehind uses this value to ensure that the subexpression

     * match ends at the point where the lookbehind was encountered.

     */

    int lookbehindTo;

    /**

     * The original string being matched.

     */

    CharSequence text;

    /**

     * Matcher state used by the last node. NOANCHOR is used when a

     * match does not have to consume all of the input. ENDANCHOR is

     * the mode used for matching all the input.

     */

    static final int ENDANCHOR = 1;

    static final int NOANCHOR = 0;

    int acceptMode = NOANCHOR;

    /**

     * The range of string that last matched the pattern. If the last

     * match failed then first is -1; last initially holds 0 then it

     * holds the index of the end of the last match (which is where the

     * next search starts).

     */

    int first = -1, last = 0;

    /**

     * The end index of what matched in the last match operation.

     */

    int oldLast = -1;

    /**

     * The index of the last position appended in a substitution.

     */

    int lastAppendPosition = 0;

    /**

     * Storage used by nodes to tell what repetition they are on in

     * a pattern, and where groups begin. The nodes themselves are stateless,

     * so they rely on this field to hold state during a match.

     */

    int[] locals;

    /**

     * Boolean indicating whether or not more input could change

     * the results of the last match.

     *

     * If hitEnd is true, and a match was found, then more input

     * might cause a different match to be found.

     * If hitEnd is true and a match was not found, then more

     * input could cause a match to be found.

     * If hitEnd is false and a match was found, then more input

     * will not change the match.

     * If hitEnd is false and a match was not found, then more

     * input will not cause a match to be found.

     */

    boolean hitEnd;

    /**

     * Boolean indicating whether or not more input could change

     * a positive match into a negative one.

     *

     * If requireEnd is true, and a match was found, then more

     * input could cause the match to be lost.

     * If requireEnd is false and a match was found, then more

     * input might change the match but the match won't be lost.

     * If a match was not found, then requireEnd has no meaning.

     */

    boolean requireEnd;

    /**

     * If transparentBounds is true then the boundaries of this

     * matcher's region are transparent to lookahead, lookbehind,

     * and boundary matching constructs that try to see beyond them.

     */

    boolean transparentBounds = false;

    /**

     * If anchoringBounds is true then the boundaries of this

     * matcher's region match anchors such as ^ and $.

     */

    boolean anchoringBounds = true;

    /**

     * No default constructor.

     */

    Matcher() {

    }

    /**

     * All matchers have the state used by Pattern during a match.

     */

    Matcher(Pattern parent, CharSequence text) {

        this.parentPattern = parent;

        this.text = text;

        // Allocate state storage

        int parentGroupCount = Math.max(parent.capturingGroupCount, 10);

        groups = new int[parentGroupCount * 2];

        locals = new int[parent.localCount];

        // Put fields into initial states

        reset();

    }

    /**

     * Returns the pattern that is interpreted by this matcher.

     *

     * @return  The pattern for which this matcher was created

     */

    public Pattern pattern() {

        return parentPattern;

    }

    /**

     * Returns the match state of this matcher as a {@link MatchResult}.

     * The result is unaffected by subsequent operations performed upon this

     * matcher.

     *

     * @return  a <code>MatchResult</code> with the state of this matcher

     * @since 1.5

     */

    public MatchResult toMatchResult() {

        Matcher result = new Matcher(this.parentPattern, text.toString());

        result.first = this.first;

        result.last = this.last;

        result.groups = this.groups.clone();

        return result;

    }

    /**

      * Changes the <tt>Pattern</tt> that this <tt>Matcher</tt> uses to

      * find matches with.

      *

      * <p> This method causes this matcher to lose information

      * about the groups of the last match that occurred. The

      * matcher's position in the input is maintained and its

      * last append position is unaffected.</p>

      *

      * @param  newPattern

      *         The new pattern used by this matcher

      * @return  This matcher

      * @throws  IllegalArgumentException

      *          If newPattern is <tt>null</tt>

      * @since 1.5

      */

    public Matcher usePattern(Pattern newPattern) {

        if (newPattern == null)

            throw new IllegalArgumentException("Pattern cannot be null");

        parentPattern = newPattern;

        // Reallocate state storage

        int parentGroupCount = Math.max(newPattern.capturingGroupCount, 10);

        groups = new int[parentGroupCount * 2];

        locals = new int[newPattern.localCount];

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

            groups[i] = -1;

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

            locals[i] = -1;

        return this;

    }

    /**

     * Resets this matcher.

     *

     * <p> Resetting a matcher discards all of its explicit state information

     * and sets its append position to zero. The matcher's region is set to the

     * default region, which is its entire character sequence. The anchoring

     * and transparency of this matcher's region boundaries are unaffected.

     *

     * @return  This matcher

     */

    public Matcher reset() {

        first = -1;

        last = 0;

        oldLast = -1;

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

            groups[i] = -1;

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

            locals[i] = -1;

        lastAppendPosition = 0;

        from = 0;

        to = getTextLength();

        return this;

    }

    /**

     * Resets this matcher with a new input sequence.

     *

     * <p> Resetting a matcher discards all of its explicit state information

     * and sets its append position to zero.  The matcher's region is set to

     * the default region, which is its entire character sequence.  The

     * anchoring and transparency of this matcher's region boundaries are

     * unaffected.

     *

     * @param  input

     *         The new input character sequence

     *

     * @return  This matcher

     */

    public Matcher reset(CharSequence input) {

        text = input;

        return reset();

    }

    /**

     * Returns the start index of the previous match.  </p>

     *

     * @return  The index of the first character matched

     *

     * @throws  IllegalStateException

     *          If no match has yet been attempted,

     *          or if the previous match operation failed

     */

    public int start() {

        if (first < 0)

            throw new IllegalStateException("No match available");

        return first;

    }

    /**

     * Returns the start index of the subsequence captured by the given group

     * during the previous match operation.

     *

     * <p> <a href="Pattern.html#cg">Capturing groups</a> are indexed from left

     * to right, starting at one.  Group zero denotes the entire pattern, so

     * the expression <i>m.</i><tt>start(0)</tt> is equivalent to

     * <i>m.</i><tt>start()</tt>.  </p>

     *

     * @param  group

     *         The index of a capturing group in this matcher's pattern

     *

     * @return  The index of the first character captured by the group,

     *          or <tt>-1</tt> if the match was successful but the group

     *          itself did not match anything

     *

     * @throws  IllegalStateException

     *          If no match has yet been attempted,

     *          or if the previous match operation failed

     *

     * @throws  IndexOutOfBoundsException

     *          If there is no capturing group in the pattern

     *          with the given index

     */

    public int start(int group) {

        if (first < 0)

            throw new IllegalStateException("No match available");

        if (group > groupCount())

            throw new IndexOutOfBoundsException("No group " + group);

        return groups[group * 2];

    }

    /**

     * Returns the offset after the last character matched.  </p>

     *

     * @return  The offset after the last character matched

     *

     * @throws  IllegalStateException

     *          If no match has yet been attempted,

     *          or if the previous match operation failed

     */

    public int end() {

        if (first < 0)

            throw new IllegalStateException("No match available");

        return last;

    }

    /**

     * Returns the offset after the last character of the subsequence

     * captured by the given group during the previous match operation.

     *

     * <p> <a href="Pattern.html#cg">Capturing groups</a> are indexed from left

     * to right, starting at one.  Group zero denotes the entire pattern, so

     * the expression <i>m.</i><tt>end(0)</tt> is equivalent to

     * <i>m.</i><tt>end()</tt>.  </p>

     *

     * @param  group

     *         The index of a capturing group in this matcher's pattern

     *

     * @return  The offset after the last character captured by the group,

     *          or <tt>-1</tt> if the match was successful

     *          but the group itself did not match anything

     *

     * @throws  IllegalStateException

     *          If no match has yet been attempted,

     *          or if the previous match operation failed

     *

     * @throws  IndexOutOfBoundsException

     *          If there is no capturing group in the pattern

     *          with the given index

     */

    public int end(int group) {

        if (first < 0)

            throw new IllegalStateException("No match available");

        if (group > groupCount())

            throw new IndexOutOfBoundsException("No group " + group);

        return groups[group * 2 + 1];

    }

    /**

     * Returns the input subsequence matched by the previous match.

     *

     * <p> For a matcher <i>m</i> with input sequence <i>s</i>,

     * the expressions <i>m.</i><tt>group()</tt> and

     * <i>s.</i><tt>substring(</tt><i>m.</i><tt>start(),</tt>&nbsp;<i>m.</i><tt>end())</tt>

     * are equivalent.  </p>

     *

     * <p> Note that some patterns, for example <tt>a*</tt>, match the empty

     * string.  This method will return the empty string when the pattern

     * successfully matches the empty string in the input.  </p>

     *

     * @return The (possibly empty) subsequence matched by the previous match,

     *         in string form

     *

     * @throws  IllegalStateException

     *          If no match has yet been attempted,

     *          or if the previous match operation failed

     */

    public String group() {

        return group(0);

    }

    /**

     * Returns the input subsequence captured by the given group during the

     * previous match operation.

     *

     * <p> For a matcher <i>m</i>, input sequence <i>s</i>, and group index

     * <i>g</i>, the expressions <i>m.</i><tt>group(</tt><i>g</i><tt>)</tt> and

     * <i>s.</i><tt>substring(</tt><i>m.</i><tt>start(</tt><i>g</i><tt>),</tt>&nbsp;<i>m.</i><tt>end(</tt><i>g</i><tt>))</tt>

     * are equivalent.  </p>

     *

     * <p> <a href="Pattern.html#cg">Capturing groups</a> are indexed from left

     * to right, starting at one.  Group zero denotes the entire pattern, so

     * the expression <tt>m.group(0)</tt> is equivalent to <tt>m.group()</tt>.

     * </p>

     *

     * <p> If the match was successful but the group specified failed to match

     * any part of the input sequence, then <tt>null</tt> is returned. Note

     * that some groups, for example <tt>(a*)</tt>, match the empty string.

     * This method will return the empty string when such a group successfully

     * matches the empty string in the input.  </p>

     *

     * @param  group

     *         The index of a capturing group in this matcher's pattern

     *

     * @return  The (possibly empty) subsequence captured by the group

     *          during the previous match, or <tt>null</tt> if the group

     *          failed to match part of the input

     *

     * @throws  IllegalStateException

     *          If no match has yet been attempted,

     *          or if the previous match operation failed

     *

     * @throws  IndexOutOfBoundsException

     *          If there is no capturing group in the pattern

     *          with the given index

     */

    public String group(int group) {

        if (first < 0)

            throw new IllegalStateException("No match found");

        if (group < 0 || group > groupCount())

            throw new IndexOutOfBoundsException("No group " + group);

        if ((groups[group*2] == -1) || (groups[group*2+1] == -1))

            return null;

        return getSubSequence(groups[group * 2], groups[group * 2 + 1]).toString();

    }

    /**

     * Returns the input subsequence captured by the given

     * <a href="Pattern.html#groupname">named-capturing group</a> during the previous

     * match operation.

     *

     * <p> If the match was successful but the group specified failed to match

     * any part of the input sequence, then <tt>null</tt> is returned. Note

     * that some groups, for example <tt>(a*)</tt>, match the empty string.

     * This method will return the empty string when such a group successfully

     * matches the empty string in the input.  </p>

     *

     * @param  name

     *         The name of a named-capturing group in this matcher's pattern

     *

     * @return  The (possibly empty) subsequence captured by the named group

     *          during the previous match, or <tt>null</tt> if the group

     *          failed to match part of the input

     *

     * @throws  IllegalStateException

     *          If no match has yet been attempted,

     *          or if the previous match operation failed

     *

     * @throws  IllegalArgumentException

     *          If there is no capturing group in the pattern

     *          with the given name

     */

    public String group(String name) {

        if (name == null)

            throw new NullPointerException("Null group name");

        if (first < 0)

            throw new IllegalStateException("No match found");

        if (!parentPattern.namedGroups().containsKey(name))

            throw new IllegalArgumentException("No group with name <" + name + ">");

        int group = parentPattern.namedGroups().get(name);

        if ((groups[group*2] == -1) || (groups[group*2+1] == -1))

            return null;

        return getSubSequence(groups[group * 2], groups[group * 2 + 1]).toString();

    }

    /**

     * Returns the number of capturing groups in this matcher's pattern.

     *

     * <p> Group zero denotes the entire pattern by convention. It is not

     * included in this count.

     *

     * <p> Any non-negative integer smaller than or equal to the value

     * returned by this method is guaranteed to be a valid group index for

     * this matcher.  </p>

     *

     * @return The number of capturing groups in this matcher's pattern

     */

    public int groupCount() {

        return parentPattern.capturingGroupCount - 1;

    }

    /**

     * Attempts to match the entire region against the pattern.

     *

     * <p> If the match succeeds then more information can be obtained via the

     * <tt>start</tt>, <tt>end</tt>, and <tt>group</tt> methods.  </p>

     *

     * @return  <tt>true</tt> if, and only if, the entire region sequence

     *          matches this matcher's pattern

     */

    public boolean matches() {

        return match(from, ENDANCHOR);

    }

    /**

     * Attempts to find the next subsequence of the input sequence that matches

     * the pattern.

     *

     * <p> This method starts at the beginning of this matcher's region, or, if

     * a previous invocation of the method was successful and the matcher has

     * not since been reset, at the first character not matched by the previous

     * match.

     *

     * <p> If the match succeeds then more information can be obtained via the

     * <tt>start</tt>, <tt>end</tt>, and <tt>group</tt> methods.  </p>

     *

     * @return  <tt>true</tt> if, and only if, a subsequence of the input

     *          sequence matches this matcher's pattern

     */

    public boolean find() {

        int nextSearchIndex = last;

        if (nextSearchIndex == first)

            nextSearchIndex++;

        // If next search starts before region, start it at region

        if (nextSearchIndex < from)

            nextSearchIndex = from;

        // If next search starts beyond region then it fails

        if (nextSearchIndex > to) {

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

                groups[i] = -1;

            return false;

        }

        return search(nextSearchIndex);

    }

    /**

     * Resets this matcher and then attempts to find the next subsequence of

     * the input sequence that matches the pattern, starting at the specified

     * index.

     *

     * <p> If the match succeeds then more information can be obtained via the

     * <tt>start</tt>, <tt>end</tt>, and <tt>group</tt> methods, and subsequent

     * invocations of the {@link #find()} method will start at the first

     * character not matched by this match.  </p>

     *

     * @throws  IndexOutOfBoundsException

     *          If start is less than zero or if start is greater than the

     *          length of the input sequence.

     *

     * @return  <tt>true</tt> if, and only if, a subsequence of the input

     *          sequence starting at the given index matches this matcher's

     *          pattern

     */

    public boolean find(int start) {

        int limit = getTextLength();

        if ((start < 0) || (start > limit))

            throw new IndexOutOfBoundsException("Illegal start index");

        reset();

        return search(start);

    }

    /**

     * Attempts to match the input sequence, starting at the beginning of the

     * region, against the pattern.

     *

     * <p> Like the {@link #matches matches} method, this method always starts

     * at the beginning of the region; unlike that method, it does not

     * require that the entire region be matched.

     *

     * <p> If the match succeeds then more information can be obtained via the

     * <tt>start</tt>, <tt>end</tt>, and <tt>group</tt> methods.  </p>

     *

     * @return  <tt>true</tt> if, and only if, a prefix of the input

     *          sequence matches this matcher's pattern

     */

    public boolean lookingAt() {

        return match(from, NOANCHOR);

    }

    /**

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

     * <code>String</code>.

     *

     * This method produces a <code>String</code> that will work

     * as a literal replacement <code>s</code> in the

     * <code>appendReplacement</code> method of the {@link Matcher} class.

     * The <code>String</code> produced will match the sequence of characters

     * in <code>s</code> treated as a literal sequence. Slashes ('\') and

     * dollar signs ('$') will be given no special meaning.

     *

     * @param  s The string to be literalized

     * @return  A literal string replacement

     * @since 1.5

     */

    public static String quoteReplacement(String s) {

        if ((s.indexOf('\\') == -1) && (s.indexOf('$') == -1))

            return s;

        StringBuilder sb = new StringBuilder();

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

            char c = s.charAt(i);

            if (c == '\\' || c == '$') {

                sb.append('\\');

            }

            sb.append(c);

        }

        return sb.toString();

    }

    /**

     * Implements a non-terminal append-and-replace step.

     *

     * <p> This method performs the following actions: </p>

     *

     * <ol>

     *

     *   <li><p> It reads characters from the input sequence, starting at the

     *   append position, and appends them to the given string buffer.  It

     *   stops after reading the last character preceding the previous match,

     *   that is, the character at index {@link

     *   #start()}&nbsp;<tt>-</tt>&nbsp;<tt>1</tt>.  </p></li>

     *

     *   <li><p> It appends the given replacement string to the string buffer.

     *   </p></li>

     *

     *   <li><p> It sets the append position of this matcher to the index of

     *   the last character matched, plus one, that is, to {@link #end()}.

     *   </p></li>

     *

     * </ol>

     *

     * <p> The replacement string may contain references to subsequences

     * captured during the previous match: Each occurrence of

     * <tt>${</tt><i>name</i><tt>}</tt> or <tt>$</tt><i>g</i>

     * will be replaced by the result of evaluating the corresponding

     * {@link #group(String) group(name)} or {@link #group(int) group(g)</tt>}

     * respectively. For  <tt>$</tt><i>g</i><tt></tt>,

     * the first number after the <tt>$</tt> is always treated as part of

     * the group reference. Subsequent numbers are incorporated into g if

     * they would form a legal group reference. Only the numerals '0'

     * through '9' are considered as potential components of the group

     * reference. If the second group matched the string <tt>"foo"</tt>, for

     * example, then passing the replacement string <tt>"$2bar"</tt> would

     * cause <tt>"foobar"</tt> to be appended to the string buffer. A dollar

     * sign (<tt>$</tt>) may be included as a literal in the replacement

     * string by preceding it with a backslash (<tt>\$</tt>).

     *

     * <p> Note that backslashes (<tt>\</tt>) and dollar signs (<tt>$</tt>) in

     * the replacement string may cause the results to be different than if it

     * were being treated as a literal replacement string. Dollar signs may be

     * treated as references to captured subsequences as described above, and

     * backslashes are used to escape literal characters in the replacement

     * string.

     *

     * <p> This method is intended to be used in a loop together with the

     * {@link #appendTail appendTail} and {@link #find find} methods.  The

     * following code, for example, writes <tt>one dog two dogs in the

     * yard</tt> to the standard-output stream: </p>

     *

     * <blockquote><pre>

     * Pattern p = Pattern.compile("cat");

     * Matcher m = p.matcher("one cat two cats in the yard");

     * StringBuffer sb = new StringBuffer();

     * while (m.find()) {

     *     m.appendReplacement(sb, "dog");

     * }

     * m.appendTail(sb);

     * System.out.println(sb.toString());</pre></blockquote>

     *

     * @param  sb

     *         The target string buffer

     *

     * @param  replacement

     *         The replacement string

     *

     * @return  This matcher

     *

     * @throws  IllegalStateException

     *          If no match has yet been attempted,

     *          or if the previous match operation failed

     *

     * @throws  IllegalArgumentException

     *          If the replacement string refers to a named-capturing

     *          group that does not exist in the pattern

     *

     * @throws  IndexOutOfBoundsException

     *          If the replacement string refers to a capturing group

     *          that does not exist in the pattern

     */

    public Matcher appendReplacement(StringBuffer sb, String replacement) {

        // If no match, return error

        if (first < 0)

            throw new IllegalStateException("No match available");

        // Process substitution string to replace group references with groups

        int cursor = 0;

        StringBuilder result = new StringBuilder();

        while (cursor < replacement.length()) {

            char nextChar = replacement.charAt(cursor);

            if (nextChar == '\\') {

                cursor++;

                nextChar = replacement.charAt(cursor);

                result.append(nextChar);

                cursor++;

            } else if (nextChar == '$') {

                // Skip past $

                cursor++;

                // A StringIndexOutOfBoundsException is thrown if

                // this "$" is the last character in replacement

                // string in current implementation, a IAE might be

                // more appropriate.

                nextChar = replacement.charAt(cursor);

                int refNum = -1;

                if (nextChar == '{') {

                    cursor++;

                    StringBuilder gsb = new StringBuilder();

                    while (cursor < replacement.length()) {

                        nextChar = replacement.charAt(cursor);

                        if (ASCII.isLower(nextChar) ||

                            ASCII.isUpper(nextChar) ||

                            ASCII.isDigit(nextChar)) {

                            gsb.append(nextChar);

                            cursor++;

                        } else {

                            break;

                        }

                    }

                    if (gsb.length() == 0)

                        throw new IllegalArgumentException(

                            "named capturing group has 0 length name");

                    if (nextChar != '}')

                        throw new IllegalArgumentException(

                            "named capturing group is missing trailing '}'");

                    String gname = gsb.toString();

                    if (ASCII.isDigit(gname.charAt(0)))

                        throw new IllegalArgumentException(

                            "capturing group name {" + gname +

                            "} starts with digit character");

                    if (!parentPattern.namedGroups().containsKey(gname))

                        throw new IllegalArgumentException(

                            "No group with name {" + gname + "}");

                    refNum = parentPattern.namedGroups().get(gname);

                    cursor++;

                } else {

                    // The first number is always a group

                    refNum = (int)nextChar - '0';

                    if ((refNum < 0)||(refNum > 9))

                        throw new IllegalArgumentException(

                            "Illegal group reference");

                    cursor++;

                    // Capture the largest legal group string

                    boolean done = false;

                    while (!done) {

                        if (cursor >= replacement.length()) {

                            break;

                        }

                        int nextDigit = replacement.charAt(cursor) - '0';

                        if ((nextDigit < 0)||(nextDigit > 9)) { // not a number

                            break;

                        }

                        int newRefNum = (refNum * 10) + nextDigit;

                        if (groupCount() < newRefNum) {

                            done = true;

                        } else {

                            refNum = newRefNum;

                            cursor++;

                        }

                    }

                }

                // Append group

                if (start(refNum) != -1 && end(refNum) != -1)

                    result.append(text, start(refNum), end(refNum));

            } else {

                result.append(nextChar);

                cursor++;

            }

        }

        // Append the intervening text

        sb.append(text, lastAppendPosition, first);

        // Append the match substitution

        sb.append(result);

        lastAppendPosition = last;

        return this;

    }

    /**

     * Implements a terminal append-and-replace step.

     *

     * <p> This method reads characters from the input sequence, starting at

     * the append position, and appends them to the given string buffer.  It is

     * intended to be invoked after one or more invocations of the {@link

     * #appendReplacement appendReplacement} method in order to copy the

     * remainder of the input sequence.  </p>

     *

     * @param  sb

     *         The target string buffer

     *

     * @return  The target string buffer

     */

    public StringBuffer appendTail(StringBuffer sb) {

        sb.append(text, lastAppendPosition, getTextLength());

        return sb;

    }

    /**

     * Replaces every subsequence of the input sequence that matches the

     * pattern with the given replacement string.

     *

     * <p> This method first resets this matcher.  It then scans the input

     * sequence looking for matches of the pattern.  Characters that are not

     * part of any match are appended directly to the result string; each match

     * is replaced in the result by the replacement string.  The replacement

     * string may contain references to captured subsequences as in the {@link

     * #appendReplacement appendReplacement} method.

     *

     * <p> Note that backslashes (<tt>\</tt>) and dollar signs (<tt>$</tt>) in

     * the replacement string may cause the results to be different than if it

     * were being treated as a literal replacement string. Dollar signs may be

     * treated as references to captured subsequences as described above, and

     * backslashes are used to escape literal characters in the replacement

     * string.

     *

     * <p> Given the regular expression <tt>a*b</tt>, the input

     * <tt>"aabfooaabfooabfoob"</tt>, and the replacement string

     * <tt>"-"</tt>, an invocation of this method on a matcher for that

     * expression would yield the string <tt>"-foo-foo-foo-"</tt>.

     *

     * <p> Invoking this method changes this matcher's state.  If the matcher

     * is to be used in further matching operations then it should first be

     * reset.  </p>

     *

     * @param  replacement

     *         The replacement string

     *

     * @return  The string constructed by replacing each matching subsequence

     *          by the replacement string, substituting captured subsequences

     *          as needed

     */

    public String replaceAll(String replacement) {

        reset();

        boolean result = find();

        if (result) {

            StringBuffer sb = new StringBuffer();

            do {

                appendReplacement(sb, replacement);

                result = find();

            } while (result);

            appendTail(sb);

            return sb.toString();

        }

        return text.toString();

    }

    /**

     * Replaces the first subsequence of the input sequence that matches the

     * pattern with the given replacement string.

     *

     * <p> This method first resets this matcher.  It then scans the input

     * sequence looking for a match of the pattern.  Characters that are not

     * part of the match are appended directly to the result string; the match

     * is replaced in the result by the replacement string.  The replacement

     * string may contain references to captured subsequences as in the {@link

     * #appendReplacement appendReplacement} method.

     *

     * <p>Note that backslashes (<tt>\</tt>) and dollar signs (<tt>$</tt>) in

     * the replacement string may cause the results to be different than if it

     * were being treated as a literal replacement string. Dollar signs may be

     * treated as references to captured subsequences as described above, and

     * backslashes are used to escape literal characters in the replacement

     * string.

     *

     * <p> Given the regular expression <tt>dog</tt>, the input

     * <tt>"zzzdogzzzdogzzz"</tt>, and the replacement string

     * <tt>"cat"</tt>, an invocation of this method on a matcher for that

     * expression would yield the string <tt>"zzzcatzzzdogzzz"</tt>.  </p>

     *

     * <p> Invoking this method changes this matcher's state.  If the matcher

     * is to be used in further matching operations then it should first be

     * reset.  </p>

     *

     * @param  replacement

     *         The replacement string

     * @return  The string constructed by replacing the first matching

     *          subsequence by the replacement string, substituting captured

     *          subsequences as needed

     */

    public String replaceFirst(String replacement) {

        if (replacement == null)

            throw new NullPointerException("replacement");

        reset();

        if (!find())

            return text.toString();

        StringBuffer sb = new StringBuffer();

        appendReplacement(sb, replacement);

        appendTail(sb);

        return sb.toString();

    }

    /**

     * Sets the limits of this matcher's region. The region is the part of the

     * input sequence that will be searched to find a match. Invoking this

     * method resets the matcher, and then sets the region to start at the

     * index specified by the <code>start</code> parameter and end at the

     * index specified by the <code>end</code> parameter.

     *

     * <p>Depending on the transparency and anchoring being used (see

     * {@link #useTransparentBounds useTransparentBounds} and

     * {@link #useAnchoringBounds useAnchoringBounds}), certain constructs such

     * as anchors may behave differently at or around the boundaries of the

     * region.

     *

     * @param  start

     *         The index to start searching at (inclusive)

     * @param  end

     *         The index to end searching at (exclusive)

     * @throws  IndexOutOfBoundsException

     *          If start or end is less than zero, if

     *          start is greater than the length of the input sequence, if

     *          end is greater than the length of the input sequence, or if

     *          start is greater than end.

     * @return  this matcher

     * @since 1.5

     */

    public Matcher region(int start, int end) {

        if ((start < 0) || (start > getTextLength()))

            throw new IndexOutOfBoundsException("start");

        if ((end < 0) || (end > getTextLength()))

            throw new IndexOutOfBoundsException("end");

        if (start > end)

            throw new IndexOutOfBoundsException("start > end");

        reset();

        from = start;

        to = end;

        return this;