A compiled representation of a regular expression.
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 Matcherjava.lang.CharSequence
A typical invocation sequence is thus
Pattern p = Pattern.compile("a*b");
Matcher m = p.matcher("aaaaab");
boolean b = m.matches();
A 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
boolean b = Pattern.matches("a*b", "aaaaab");
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.
Instances of this class are immutable and are safe for use by multiple
concurrent threads. Instances of the Matcher Summary of regular-expression constructs
| Construct | Matches |
|---|
| |
|---|
| Characters |
|---|
| x | The character x |
| \\ | The backslash character |
| \0n | The character with octal value 0n
(0 <= n <= 7) |
| \0nn | The character with octal value 0nn
(0 <= n <= 7) |
| \0mnn | The character with octal value 0mnn
(0 <= m <= 3,
0 <= n <= 7) |
| \xhh | The character with hexadecimal value 0xhh |
| \uhhhh | The character with hexadecimal value 0xhhhh |
| \t | The tab character ('\u0009') |
| \n | The newline (line feed) character ('\u000A') |
| \r | The carriage-return character ('\u000D') |
| \f | The form-feed character ('\u000C') |
| \a | The alert (bell) character ('\u0007') |
| \e | The escape character ('\u001B') |
| \cx | The control character corresponding to x |
| |
|---|
| Character classes |
|---|
| [abc] | a, b, or c (simple class) |
| [^abc] | Any character except a, b, or c (negation) |
| [a-zA-Z] | a through z
or A through Z, inclusive (range) |
| [a-d[m-p]] | a through d,
or m through p: [a-dm-p] (union) |
| [a-z&&[def]] | d, e, or f (intersection) |
| [a-z&&[^bc]] | a through z,
except for b and c: [ad-z] (subtraction) |
| [a-z&&[^m-p]] | a through z,
and not m through p: [a-lq-z](subtraction) |
| |
|---|
| Predefined character classes |
|---|
| . | Any character (may or may not match line terminators) |
| \d | A digit: [0-9] |
| \D | A non-digit: [^0-9] |
| \s | A whitespace character: [ \t\n\x0B\f\r] |
| \S | A non-whitespace character: [^\s] |
| \w | A word character: [a-zA-Z_0-9] |
| \W | A non-word character: [^\w] |
| |
|---|
| POSIX character classes (US-ASCII only) |
|---|
| \p{Lower} | A lower-case alphabetic character: [a-z] |
| \p{Upper} | An upper-case alphabetic character:[A-Z] |
| \p{ASCII} | All ASCII:[\x00-\x7F] |
| \p{Alpha} | An alphabetic character:[\p{Lower}\p{Upper}] |
| \p{Digit} | A decimal digit: [0-9] |
| \p{Alnum} | An alphanumeric character:[\p{Alpha}\p{Digit}] |
| \p{Punct} | Punctuation: One of !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ |
| \p{Graph} | A visible character: [\p{Alnum}\p{Punct}] |
| \p{Print} | A printable character: [\p{Graph}\x20] |
| \p{Blank} | A space or a tab: [ \t] |
| \p{Cntrl} | A control character: [\x00-\x1F\x7F] |
| \p{XDigit} | A hexadecimal digit: [0-9a-fA-F] |
| \p{Space} | A whitespace character: [ \t\n\x0B\f\r] |
| |
|---|
| java.lang.Character classes (simple java character type) |
|---|
| \p{javaLowerCase} | Equivalent to java.lang.Character.isLowerCase() |
| \p{javaUpperCase} | Equivalent to java.lang.Character.isUpperCase() |
| \p{javaWhitespace} | Equivalent to java.lang.Character.isWhitespace() |
| \p{javaMirrored} | Equivalent to java.lang.Character.isMirrored() |
| |
|---|
| Classes for Unicode blocks and categories |
|---|
| \p{InGreek} | A character in the Greek block (simple block) |
| \p{Lu} | An uppercase letter (simple category) |
| \p{Sc} | A currency symbol |
| \P{InGreek} | Any character except one in the Greek block (negation) |
| [\p{L}&&[^\p{Lu}]] | Any letter except an uppercase letter (subtraction) |
| |
|---|
| Boundary matchers |
|---|
| ^ | The beginning of a line |
| $ | The end of a line |
| \b | A word boundary |
| \B | A non-word boundary |
| \A | The beginning of the input |
| \G | The end of the previous match |
| \Z | The end of the input but for the final
terminator, if any |
| \z | The end of the input |
| |
|---|
| Greedy quantifiers |
|---|
| X? | X, once or not at all |
| X* | X, zero or more times |
| X+ | X, one or more times |
| X{n} | X, exactly n times |
| X{n,} | X, at least n times |
| X{n,m} | X, at least n but not more than m times |
| |
|---|
| Reluctant quantifiers |
|---|
| X?? | X, once or not at all |
| X*? | X, zero or more times |
| X+? | X, one or more times |
| X{n}? | X, exactly n times |
| X{n,}? | X, at least n times |
| X{n,m}? | X, at least n but not more than m times |
| |
|---|
| Possessive quantifiers |
|---|
| X?+ | X, once or not at all |
| X*+ | X, zero or more times |
| X++ | X, one or more times |
| X{n}+ | X, exactly n times |
| X{n,}+ | X, at least n times |
| X{n,m}+ | X, at least n but not more than m times |
| |
|---|
| Logical operators |
|---|
| XY | X followed by Y |
| X|Y | Either X or Y |
| (X) | X, as a capturing group |
| |
|---|
| Back references |
|---|
| \n | Whatever the nth
capturing group matched |
| |
|---|
| Quotation |
|---|
| \ | Nothing, but quotes the following character |
| \Q | Nothing, but quotes all characters until \E |
| \E | Nothing, but ends quoting started by \Q |
| |
|---|
| Special constructs (non-capturing) |
|---|
| (?:X) | X, as a non-capturing group |
| (?idmsux-idmsux) | Nothing, but turns match flags i
d m s
u x on - off |
| (?idmsux-idmsux:X) | X, as a non-capturing group with the
given flags i d
m s u
x on - off |
| (?=X) | X, via zero-width positive lookahead |
| (?!X) | X, via zero-width negative lookahead |
| (?<=X) | X, via zero-width positive lookbehind |
| (?<!X) | X, via zero-width negative lookbehind |
| (?>X) | X, as an independent, non-capturing group |
Backslashes, escapes, and quoting
The backslash character ('\') 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 \\ matches a single backslash and \{ matches a
left brace.
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.
Backslashes within string literals in Java source code are interpreted
as required by the Java Language
Specification as either Unicode
escapes or other character
escapes. 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
"\b", for example, matches a single backspace character when
interpreted as a regular expression, while "\\b" matches a
word boundary. The string literal "\(hello\)" is illegal
and leads to a compile-time error; in order to match the string
(hello) the string literal "\\(hello\\)"
must be used.
Character Classes
Character classes may appear within other character classes, and
may be composed by the union operator (implicit) and the intersection
operator (&&).
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.
The precedence of character-class operators is as follows, from
highest to lowest:
| 1 | Literal escape | \x |
|---|
| 2 | Grouping | [...] |
|---|
| 3 | Range | a-z |
|---|
| 4 | Union | [a-e][i-u] |
|---|
| 5 | Intersection | [a-z&&[aeiou]] |
|---|
Note that a different set of metacharacters are in effect inside
a character class than outside a character class. For instance, the
regular expression . loses its special meaning inside a
character class, while the expression - becomes a range
forming metacharacter.
Line terminators
A line terminator 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:
- A newline (line feed) character ('\n'),
- A carriage-return character followed immediately by a newline
character ("\r\n"),
- A standalone carriage-return character ('\r'),
- A next-line character ('\u0085'),
- A line-separator character ('\u2028'), or
- A paragraph-separator character ('\u2029).
If UNIX_LINES
The regular expression . matches any character except a line
terminator unless the DOTALL
By default, the regular expressions ^ and $ ignore
line terminators and only match at the beginning and the end, respectively,
of the entire input sequence. If MULTILINEMULTILINE Groups and capturing
Capturing groups are numbered by counting their opening parentheses from
left to right. In the expression ((A)(B(C))), for example, there
are four such groups:
| 1 | ((A)(B(C))) |
|---|
| 2 | (A) |
|---|
| 3 | (B(C)) |
|---|
| 4 | (C) |
|---|
Group zero always stands for the entire expression.
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.
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
"aba" against the expression (a(b)?)+, for example, leaves
group two set to "b". All captured input is discarded at the
beginning of each match.
Groups beginning with (? are pure, non-capturing groups
that do not capture text and do not count towards the group total.
Unicode support
This class is in conformance with Level 1 of Unicode Technical
Standard #18: Unicode Regular Expression Guidelines, plus RL2.1
Canonical Equivalents.
Unicode escape sequences such as \u2014 in Java source code
are processed as described in \u00A73.3
of the Java Language Specification. 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 "\u2014" and "\\u2014",
while not equal, compile into the same pattern, which matches the character
with hexadecimal value 0x2014.
Unicode blocks and categories are written with the
\p and \P constructs as in
Perl. \p{prop} matches if the input has the
property prop, while \P{prop} does not match if
the input has that property. Blocks are specified with the prefix
In, as in InMongolian. Categories may be specified with
the optional prefix Is: Both \p{L} and \p{IsL}
denote the category of Unicode letters. Blocks and categories can be used
both inside and outside of a character class.
The supported categories are those of
The Unicode Standard in the version specified by the
Character class. The category names are those
defined in the Standard, both normative and informative.
The block names supported by Pattern are the valid block names
accepted and defined by
UnicodeBlock.forName.
Categories that behave like the java.lang.Character
boolean ismethodname methods (except for the deprecated ones) are
available through the same \p{prop} syntax where
the specified property has the name javamethodname.
Comparison to Perl 5
The Pattern engine performs traditional NFA-based matching
with ordered alternation as occurs in Perl 5.
Perl constructs not supported by this class:
The conditional constructs (?{X}) and
(?(condition)X|Y),
The embedded code constructs (?{code})
and (??{code}),
The embedded comment syntax (?#comment), and
The preprocessing operations \l \u,
\L, and \U.
Constructs supported by this class but not by Perl:
Possessive quantifiers, which greedily match as much as they can
and do not back off, even when doing so would allow the overall match to
succeed.
Character-class union and intersection as described
above.
Notable differences from Perl:
In Perl, \1 through \9 are always interpreted
as back references; a backslash-escaped number greater than 9 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,
\1 through \9 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.
Perl uses the g flag to request a match that resumes
where the last match left off. This functionality is provided implicitly
by the MatcherMatcher.find()
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.
Perl is forgiving about malformed matching constructs, as in the
expression *a, as well as dangling brackets, as in the
expression abc], and treats them as literals. This
class also accepts dangling brackets but is strict about dangling
metacharacters like +, ? and *, and will throw a
PatternSyntaxException
For a more precise description of the behavior of regular expression
constructs, please see
Mastering Regular Expressions, 3nd Edition, Jeffrey E. F. Friedl,
O'Reilly and Associates, 2006.
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.
RegExp r1 = RegExp.compile("abc", Pattern.I|Pattern.M);
RegExp r2 = RegExp.compile("(?im)abc", 0);
The flags are duplicated so that the familiar Perl match flag
names are available.
Enables Unix lines mode.
In this mode, only the '\n' line terminator is recognized
in the behavior of ., ^, and $.
Unix lines mode can also be enabled via the embedded flag
expression (?d).
Enables case-insensitive matching.
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 UNICODE_CASE
Case-insensitive matching can also be enabled via the embedded flag
expression (?i).
Specifying this flag may impose a slight performance penalty.
Permits whitespace and comments in pattern.
In this mode, whitespace is ignored, and embedded comments starting
with # are ignored until the end of a line.
Comments mode can also be enabled via the embedded flag
expression (?x).
public static final int COMMENTS = 0x04;
Enables multiline mode.
In multiline mode the expressions ^ and $ 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.
Multiline mode can also be enabled via the embedded flag
expression (?m).
Enables literal parsing of the pattern.
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.
The flags CASE_INSENSITIVE and UNICODE_CASE retain their impact on
matching when used in conjunction with this flag. The other flags
become superfluous.
There is no embedded flag character for enabling literal parsing.
public static final int LITERAL = 0x10;
Enables dotall mode.
In dotall mode, the expression . matches any character,
including a line terminator. By default this expression does not match
line terminators.
Dotall mode can also be enabled via the embedded flag
expression (?s). (The s is a mnemonic for
"single-line" mode, which is what this is called in Perl.)
public static final int DOTALL = 0x20;
Enables Unicode-aware case folding.
When this flag is specified then case-insensitive matching, when
enabled by the CASE_INSENSITIVE
Unicode-aware case folding can also be enabled via the embedded flag
expression (?u).
Specifying this flag may impose a performance penalty.
Enables canonical equivalence.
When this flag is specified then two characters will be considered
to match if, and only if, their full canonical decompositions match.
The expression "a\u030A", for example, will match the
string "\u00E5" when this flag is specified. By default,
matching does not take canonical equivalence into account.
There is no embedded flag character for enabling canonical
equivalence.
Specifying this flag may impose a performance penalty.
public static final int CANON_EQ = 0x80;
use serialVersionUID from Merlin b59 for interoperability
The original regular-expression pattern string.
The original pattern 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.
The starting point of state machine for the find operation. This allows
a match to start anywhere in the input.
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.
Temporary storage used by parsing pattern slice.
Temporary storage used while parsing group references.
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.
The local variable count used by parsing tree. Used by matchers to
allocate storage needed to perform a match.
Index into the pattern string that keeps track of how much has been
parsed.
Holds the length of the pattern string.
Compiles the given regular expression into a pattern.
- Parameters:
regex
The expression to be compiled- Throws:
PatternSyntaxException
If the expression's syntax is invalid
Compiles the given regular expression into a pattern with the given
flags.
Returns the regular expression from which this pattern was compiled.
- Returns:
- The source of this pattern
Returns the string representation of this pattern. This
is the regular expression from which this pattern was
compiled.
- Returns:
- The string representation of this pattern
- Since:
- 1.5
Creates a matcher that will match the given input against this pattern.
- Parameters:
input
The character sequence to be matched- Returns:
- A new matcher for this pattern
Returns this pattern's match flags.
- Returns:
- The match flags specified when this pattern was compiled
Compiles the given regular expression and attempts to match the given
input against it.
An invocation of this convenience method of the form
Pattern.matches(regex, input);
behaves in exactly the same way as the expression
Pattern.compile(regex).matcher(input).matches()
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.
- Parameters:
regex
The expression to be compiledinput
The character sequence to be matched- Throws:
PatternSyntaxException
If the expression's syntax is invalid
Splits the given input sequence around matches of this pattern.
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.
The limit parameter controls the number of times the
pattern is applied and therefore affects the length of the resulting
array. If the limit n is greater than zero then the pattern
will be applied at most n - 1 times, the array's
length will be no greater than n, and the array's last entry
will contain all input beyond the last matched delimiter. If n
is non-positive then the pattern will be applied as many times as
possible and the array can have any length. If n 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.
The input "boo:and:foo", for example, yields the following
results with these parameters:
Regex | Limit | Result |
|---|
| : | 2 | { "boo", "and:foo" } |
| : | 5 | { "boo", "and", "foo" } |
| : | -2 | { "boo", "and", "foo" } |
| o | 5 | { "b", "", ":and:f", "", "" } |
| o | -2 | { "b", "", ":and:f", "", "" } |
| o | 0 | { "b", "", ":and:f" } |
- Parameters:
input
The character sequence to be splitlimit
The result threshold, as described above- Returns:
- The array of strings computed by splitting the input
around matches of this pattern
boolean matchLimited = limit > 0;
if (!matchLimited || matchList.size() < limit - 1) { } else if (matchList.size() == limit - 1) { if (!matchLimited || matchList.size() < limit)
int resultSize = matchList.size();
while (resultSize > 0 && matchList.get(resultSize-1).equals("")) Splits the given input sequence around matches of this pattern.
This method works as if by invoking the two-argument split(java.lang.CharSequence,int)
The input "boo:and:foo", for example, yields the following
results with these expressions:
Regex | Result |
|---|
| : | { "boo", "and", "foo" } |
| o | { "b", "", ":and:f" } |
- Parameters:
input
The character sequence to be split- Returns:
- The array of strings computed by splitting the input
around matches of this pattern
Returns a literal pattern
String for the specified
String.
This method produces a String that can be used to
create a Pattern that would match the string
s as if it were a literal pattern.
Metacharacters
or escape sequences in the input sequence will be given no special
meaning.
- Parameters:
s The string to be literalized- Returns:
- A literal string replacement
- Since:
- 1.5
int slashEIndex = s.indexOf("\\E"); return "\\Q" + s + "\\E";
while ((slashEIndex = s.indexOf("\\E", current)) != -1) { current = slashEIndex + 2;
Recompile the Pattern instance from a stream. The original pattern
string is read in and the object tree is recompiled from it.
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.
The pattern is converted to normalizedD form and then a pure group
is constructed to match canonical equivalences of the characters.
boolean inCharClass = false;
&& (lastCodePoint != -1)) { } else if (c == '[' && lastCodePoint != '\\') { 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.
if (c == ']' && lastCodePoint != '\\') { throw error("Unclosed character class"); 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.
for(int x=0; x<perms.length; x++) { String next = base + perms[x];
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.
for(int x=1; x<nCodePoints; x++)
int combClass[] = new int[nCodePoints];
for(int x=0, i=0; x<nCodePoints; x++) {loop: for(int x=0, offset=0; x<nCodePoints; x++, offset+=len) { for(int y=x-1; y>=0; y--) { if (combClass[y] == combClass[x]) { for(int y=0; y<subResult.length; y++)
temp[index++] = prefix + subResult[y];
for (int x=0; x<index; x++)
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.
if (result.equals(firstTwoCharacters))
return result + remainder;
Preprocess any \Q...\E sequences in `temp', meta-quoting them.
See the description of `quotemeta' in perlfunc(1).
else if (temp[i + 1] != 'Q')
int[] newtemp = new int[j + 2*(pLen-i) + 2];
if (inQuote) newtemp[j++] = '\\';
newtemp[j++] = temp[i++];
Copies regular expression to an int array and invokes the parsing
of the expression which will create the object tree.
boolean hasSupplementary = false;
throw error("Unmatched closing ')'"); throw error("Unexpected internal error"); Used to print out a subtree of the Pattern to help with debugging.
} else if (node instanceof Loop) { } else if (node instanceof Curly) { Used to accumulate information about a subtree of the object graph
so that optimizations can be applied to the subtree.
Indicates whether a particular flag is set or not.
private boolean has(int f) { Match next character, signal error if failed.
Mark the end of pattern with a specific character.
private void mark(int c) { Peek the next character, and do not advance the cursor.
Read the next character, and advance the cursor by one.
Read the next character, and advance the cursor by one,
ignoring the COMMENTS setting
Advance the cursor by one, and peek the next character.
Advance the cursor by one, and peek the next character,
ignoring the COMMENTS setting
If in xmode peek past whitespace and comments.
while (ASCII.isSpace(ch) || ch == '#') { If in xmode parse past whitespace and comments.
while (ASCII.isSpace(ch) || ch == '#') { xmode parse past comment to end of line.
xmode peek past comment to end of line.
Determines if character is a line separator in the current mode
Read the character after the next one, and advance the cursor by two.
Unread one next character, and retreat cursor by one.
Internal method used for handling all syntax errors. The pattern is
displayed with a pointer to aid in locating the syntax error.
Determines if there is any supplementary character or unpaired
surrogate in the specified range.
for (int i = start; i < end; i++) { Determines if the specified code point is a supplementary
character or unpaired surrogate.
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.
if (branchConn == null) { nodeTail.next = branchConn;
firstTail.next = branchConn;
prev = new Branch(prev, node, branchConn);
Parsing of sequences between alternations.
if (ch == 'p' || ch == 'P') { boolean oneLetter = true;
boolean comp = (ch == 'P');
throw error("Dangling meta character '" + ((char)ch) + "'"); Parse and add a new Single or Slice.
boolean hasSupplementary = false;
if (ch == 'p' || ch == 'P') { boolean comp = (ch == 'P');
boolean oneLetter = true;
ch = escape(false, first == 0);
private void append(int ch, int len) { int[] tmp = new int[len+len];
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.
int newRefNum = (refNum * 10) + (ch - '0');
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) { 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.
boolean firstInClass = true;
prev = union(prev, node);
while (ch != ']' && ch != '&') { rightNode = clazz(false);
throw error("Bad class syntax"); throw error("Unclosed character class"); prev = union(prev, node);
(ch == 0xff || ch == 0xb5 ||
ch == 0x49 || ch == 0x69 ||
ch == 0x53 || ch == 0x73 ||
ch == 0x4b || ch == 0x6b ||
ch == 0xc5 || ch == 0xe5)))
Parse a single character or a character range in a character class
and return its representative node.
if (ch == 'p' || ch == 'P') { boolean comp = (ch == 'P');
boolean oneLetter = true;
throw error("Illegal character range"); throw error("Unexpected character '"+((char)ch)+"'"); Parses a Unicode character family and returns its representative node.
throw error("Unclosed character family"); throw error("Empty character family"); Returns a CharProperty matching all characters in a UnicodeBlock.
block = Character.UnicodeBlock.forName(name);
throw error("Unknown character block name {" + name + "}"); return block == Character.UnicodeBlock.of(ch);}};
Returns a CharProperty matching all characters in a named property.
throw error("Unknown character property name {" + name + "}"); Parses a group and returns the head node of a set of nodes that process
the group. Sometimes a double return system is used where the tail is
returned in root.
boolean capturingGroup = false;
head = tail = new Pos(head);
head = tail = new Neg(head);
if (info.maxValid == false) { throw error("Look-behind group does not have " + "an obvious maximum length");
head = tail = (hasSupplementary ?
new Behind(head, info.maxLength,
head = tail = (hasSupplementary ?
throw error("Unknown look-behind group"); throw error("Unknown group type"); throw error("Unknown inline modifier"); accept(')', "Unclosed group"); if (node instanceof Ques) { head = new Branch(head, null, tail);
head = new Branch(null, head, tail);
} else if (node instanceof Curly) { throw error("Internal logic error"); Create group head and tail nodes using double return. If the group is
created with anonymous true then it is a pure group and should not
affect group counting.
if (!anonymous && groupIndex < 10)
Parses inlined match flags and set them appropriately.
Parses the second part of inlined match flags and turns off
flags appropriately.
static final int LAZY = 1;
Processes repetition. If the next character peeked is a quantifier
then new nodes must be appended to handle the repetition.
Prev could be a single or a group, so it could be a chain of nodes.
cmin = cmin * 10 + (ch - '0');
cmax = cmax * 10 + (ch - '0');
throw error("Unclosed counted closure"); if (((cmin) | (cmax) | (cmax - cmin)) < 0)
throw error("Illegal repetition range"); throw error("Illegal repetition"); Utility method for parsing control escape sequences.
throw error("Illegal control escape sequence"); Utility method for parsing octal escape sequences.
if (((n-'0')|('7'-n)) >= 0) { if (((m-'0')|('7'-m)) >= 0) { if ((((o-'0')|('7'-o)) >= 0) && (((n-'0')|('3'-n)) >= 0)) { return (n - '0') * 64 + (m - '0') * 8 + (o - '0');
return (n - '0') * 8 + (m - '0');
throw error("Illegal octal escape sequence"); Utility method for parsing hexadecimal escape sequences.
throw error("Illegal hexadecimal escape sequence"); Utility method for parsing unicode escape sequences.
for (int i = 0; i < 4; i++) { throw error("Illegal Unicode escape sequence"); int lengthInCodePoints) { assert (index >= 0 && index < seq.length());
if (lengthInCodePoints >= 0) { assert (index >= 0 && index < length);
for (int i = 0; x < length && i < lengthInCodePoints; i++) { assert (index >= 0 && index <= length);
int len = -lengthInCodePoints;
for (int i = 0; x > 0 && i < len; i++) { for (int i = 0; i < length; ) { Creates a bit vector for matching Latin-1 values. A normal BitClass
never matches values above Latin-1, and a complemented BitClass always
matches values above Latin-1.
assert c >= 0 && c <= 255;
return ch < 256 && bits[ch];
Returns a suitably optimized, single character matcher.
Utility method for creating a string slice matcher.
private Node newSlice(int[] buf, int count, boolean hasSupplementary) { int[] tmp = new int[count];
for (int i = 0; i < count; i++) { for (int i = 0; i < count; i++) { for (int i = 0; i < count; i++) { return hasSupplementary ? new SliceS(tmp) : new Slice(tmp);
The following classes are the building components of the object
tree that represents a compiled regular expression. The object tree
is made of individual elements that handle constructs in the Pattern.
Each type of object knows how to match its equivalent construct with
the match() method.
Base class for all node classes. Subclasses should override the match()
method as appropriate. This class is an accepting node, so its match()
always returns true.
This method implements the classic accept node.
matcher.groups[0] = matcher.first;
matcher.groups[1] = matcher.last;
This method is good for all zero length assertions.
return info.deterministic;
This method implements the classic accept node with
the addition of a check to see if the match occurred
using all of the input.
matcher.groups[0] = matcher.first;
matcher.groups[1] = matcher.last;
Used for REs that can start anywhere within the input string.
This basically tries to match repeatedly at each spot in the
input string, moving forward after each try. An anchored search
or a BnM will bypass this node completely.
for (; i <= guard; i++) { matcher.groups[0] = matcher.first;
matcher.groups[1] = matcher.last;
info.deterministic = false;
if ((ret = next.match(matcher, i, seq)) || i == guard)
matcher.groups[0] = matcher.first;
matcher.groups[1] = matcher.last;
Node to anchor at the beginning of input. This object implements the
match for a \A sequence, and the caret anchor will use this if not in
multiline mode.
int fromIndex = (matcher.anchoringBounds) ?
if (i == fromIndex && next.match(matcher, i, seq)) { matcher.groups[1] = matcher.last;
Node to anchor at the end of input. This is the absolute end, so this
should not match at the last newline before the end as $ will.
static final class End extends Node { int endIndex = (matcher.anchoringBounds) ?
Node to anchor at the beginning of a line. This is essentially the
object to match for the multiline ^.
int startIndex = matcher.from;
int endIndex = matcher.to;
if (!matcher.anchoringBounds) { if (ch != '\n' && ch != '\r'
if (ch == '\r' && seq.charAt(i) == '\n')
Node to anchor at the beginning of a line when in unixdot mode.
int startIndex = matcher.from;
int endIndex = matcher.to;
if (!matcher.anchoringBounds) { Node to match the location where the last match ended.
This is used for the \G construct.
if (i != matcher.oldLast)
Node to anchor at the end of a line or the end of input based on the
multiline mode.
When not in multiline mode, the $ can only match at the very end
of the input, unless the input ends in a line terminator in which
it matches right before the last line terminator.
Note that \r\n is considered an atomic line terminator.
Like ^ the $ operator matches at a position, it does not match the
line terminators themselves.
int endIndex = (matcher.anchoringBounds) ?
if (i > 0 && seq.charAt(i-1) == '\r')
} else if (ch == '\r' || ch == '\u0085' ||
matcher.requireEnd = true;
return info.deterministic;
Node to anchor at the end of a line or the end of input based on the
multiline mode when in unix lines mode.
int endIndex = (matcher.anchoringBounds) ?
matcher.requireEnd = true;
return info.deterministic;
Abstract node class to match one character satisfying some
boolean property.
Optimized version of CharProperty that works only for
properties never satisfied by Supplementary characters.
Node class that matches a Supplementary Unicode character
Optimization -- matches a given BMP character
Case insensitive matches a given BMP character
Unicode case insensitive matches a given Unicode character
Node class that matches a Unicode category.
Node class that matches a POSIX type.
Base class for all Slice nodes
Node class for a case sensitive/BMP-only sequence of literal
characters.
for (int j=0; j<len; j++) { if ((i+j) >= matcher.to) { if (buf[j] != seq.charAt(i+j))
Node class for a case_insensitive/BMP-only sequence of literal
characters.
for (int j=0; j<len; j++) { if ((i+j) >= matcher.to) { Node class for a unicode_case_insensitive/BMP-only sequence of
literal characters. Uses unicode case folding.
for (int j=0; j<len; j++) { if ((i+j) >= matcher.to) { Node class for a case sensitive sequence of literal characters
including supplementary characters.
for (int j = 0; j < buf.length; j++) { Node class for a case insensitive sequence of literal characters
including supplementary characters.
for (int j = 0; j < buf.length; j++) { if (buf[j] != c && buf[j] != toLower(c))
Node class for a case insensitive sequence of literal characters.
Uses unicode case folding.
private static boolean inRange(int lower, int ch, int upper) { return lower <= ch && ch <= upper;
Returns node for matching characters within an explicit value range.
return inRange(lower, ch, upper);}};
Returns node for matching characters within an explicit value
range in a case insensitive manner.
return inRange(lower, up, upper) ||
return inRange(lower, ch, upper) ||
Implements the Unicode category ALL and the dot metacharacter when
in dotall mode.
Node class for the dot metacharacter when dotall is not enabled.
return (ch != '\n' && ch != '\r'
Node class for the dot metacharacter when dotall is not enabled
but UNIX_LINES is enabled.
The 0 or 1 quantifier. This one class implements all three types.
if (atom.match(matcher, i, seq)) i = matcher.last;
int minL = info.minLength;
info.deterministic = false;
Handles the curly-brace style repetition with a specified minimum and
maximum occurrences. The * quantifier is handled as a special case.
This class handles the three types.
Curly(Node node, int cmin, int cmax, int type) { for (j = 0; j < cmin; j++) { return match0(matcher, i, j, seq);
return match1(matcher, i, j, seq);
return match2(matcher, i, j, seq);
int k = matcher.last - i;
if (i + k != matcher.last) { if (match0(matcher, matcher.last, j+1, seq))
int minL = info.minLength;
int maxL = info.maxLength;
boolean maxV = info.maxValid;
boolean detm = info.deterministic;
int temp = info.minLength * cmin + minL;
if (maxV & info.maxValid) { temp = info.maxLength * cmax + maxL;
info.deterministic = detm;
info.deterministic = false;
Handles the curly-brace style repetition with a specified minimum and
maximum occurrences in deterministic cases. This is an iterative
optimization over the Prolog and Loop system which would handle this
in a recursive way. The * quantifier is handled as a special case.
If capture is true then this class saves group settings and ensures
that groups are unset when backing off of a group match.
int group, boolean capture) { int[] groups = matcher.groups;
int[] locals = matcher.locals;
for (int j = 0; j < cmin; j++) { int[] groups = matcher.groups;
int k = matcher.last - i;
if (i + k != matcher.last) { if (match0(matcher, i, j, seq))
int minL = info.minLength;
int maxL = info.maxLength;
boolean maxV = info.maxValid;
boolean detm = info.deterministic;
int temp = info.minLength * cmin + minL;
if (maxV & info.maxValid) { temp = info.maxLength * cmax + maxL;
if (info.deterministic && cmin == cmax) { info.deterministic = detm;
info.deterministic = false;
A Guard node at the end of each atom node in a Branch. It
serves the purpose of chaining the "match" operation to
"next" but not the "study", so we can collect the TreeInfo
of each atom node without including the TreeInfo of the
"next".
return info.deterministic;
Handles the branching of alternations. Note this is also used for
the ? quantifier to branch between the case where it matches once
and where it does not occur.
for (int n = 0; n < size; n++) { int minL = info.minLength;
int maxL = info.maxLength;
boolean maxV = info.maxValid;
for (int n = 0; n < size; n++) { minL2 = Math.min(minL2, info.minLength);
maxL2 = Math.max(maxL2, info.maxLength);
maxV = (maxV & info.maxValid);
info.deterministic = false;
The GroupHead saves the location where the group begins in the locals
and restores them when the match is done.
The matchRef is used when a reference to this group is accessed later
in the expression. The locals will have a negative value in them to
indicate that we do not want to unset the group if the reference
doesn't match.
Recursive reference to a group in the regular expression. It calls
matchRef because if the reference fails to match we would not unset
the group.
info.deterministic = false;
The GroupTail handles the setting of group beginning and ending
locations when groups are successfully matched. It must also be able to
unset groups that have to be backed off of.
The GroupTail node is also used when a previous group is referenced,
and in that case no group information needs to be set.
This sets up a loop to handle a recursive quantifier structure.
Handles the repetition count for a greedy Curly. The matchInit
is called from the Prolog to save the index of where the group
beginning is stored. A zero length group check occurs in the
normal match but is skipped in the matchInit.
Loop(int countIndex, int beginIndex) { info.deterministic = false;
Handles the repetition count for a reluctant Curly. The matchInit
is called from the Prolog to save the index of where the group
beginning is stored. A zero length group check occurs in the
normal match but is skipped in the matchInit.
LazyLoop(int countIndex, int beginIndex) { super(countIndex, beginIndex);
boolean result = body.match(matcher, i, seq);
boolean result = body.match(matcher, i, seq);
info.deterministic = false;
Refers to a group in the regular expression. Attempts to match
whatever the group referred to last matched.
if (i + groupSize > matcher.to) { for (int index=0; index<groupSize; index++)
return next.match(matcher, i+groupSize, seq);
CIBackRef(int groupCount, boolean doUnicodeCase) { if (i + groupSize > matcher.to) { for (int index=0; index<groupSize; index++) { return next.match(matcher, i+groupSize, seq);
Searches until the next instance of its atom. This is useful for
finding the atom efficiently without passing an instance of it
(greedy problem) and without a lot of wasted search time (reluctant
problem).
return next.match(matcher, matcher.last, seq);
info.deterministic = false;
int minL = info.minLength;
int maxL = info.maxLength;
boolean maxV = info.maxValid;
int minL2 = info.minLength;
int maxL2 = info.maxLength;
boolean maxV2 = info.maxValid;
info.minLength = minL + Math.min(minL2, info.minLength);
info.maxLength = maxL + Math.max(maxL2, info.maxLength);
info.maxValid = (maxV & maxV2 & info.maxValid);
info.deterministic = false;
Zero width positive lookahead.
static final class Pos extends Node { int savedTo = matcher.to;
boolean conditionMatched = false;
if (matcher.transparentBounds)
conditionMatched = cond.match(matcher, i, seq);
return conditionMatched && next.match(matcher, i, seq);
Zero width negative lookahead.
static final class Neg extends Node { int savedTo = matcher.to;
boolean conditionMatched = false;
if (matcher.transparentBounds)
conditionMatched = !cond.match(matcher, i, seq);
matcher.requireEnd = true;
conditionMatched = !cond.match(matcher, i, seq);
return conditionMatched && next.match(matcher, i, seq);
For use with lookbehinds; matches the position where the lookbehind
was encountered.
return i == matcher.lookbehindTo;
Zero width positive lookbehind.
int savedFrom = matcher.from;
boolean conditionMatched = false;
int startIndex = (!matcher.transparentBounds) ?
int from = Math.max(i - rmax, startIndex);
int savedLBT = matcher.lookbehindTo;
matcher.lookbehindTo = i;
if (matcher.transparentBounds)
for (int j = i - rmin; !conditionMatched && j >= from; j--) { conditionMatched = cond.match(matcher, j, seq);
matcher.from = savedFrom;
matcher.lookbehindTo = savedLBT;
return conditionMatched && next.match(matcher, i, seq);
Zero width positive lookbehind, including supplementary
characters or unpaired surrogates.
int savedFrom = matcher.from;
int startIndex = (!matcher.transparentBounds) ?
boolean conditionMatched = false;
int from = Math.max(i - rmaxChars, startIndex);
int savedLBT = matcher.lookbehindTo;
matcher.lookbehindTo = i;
if (matcher.transparentBounds)
for (int j = i - rminChars;
!conditionMatched && j >= from;
conditionMatched = cond.match(matcher, j, seq);
matcher.from = savedFrom;
matcher.lookbehindTo = savedLBT;
return conditionMatched && next.match(matcher, i, seq);
Zero width negative lookbehind.
int savedLBT = matcher.lookbehindTo;
int savedFrom = matcher.from;
boolean conditionMatched = false;
int startIndex = (!matcher.transparentBounds) ?
int from = Math.max(i - rmax, startIndex);
matcher.lookbehindTo = i;
if (matcher.transparentBounds)
for (int j = i - rmin; !conditionMatched && j >= from; j--) { conditionMatched = cond.match(matcher, j, seq);
matcher.from = savedFrom;
matcher.lookbehindTo = savedLBT;
return !conditionMatched && next.match(matcher, i, seq);
Zero width negative lookbehind, including supplementary
characters or unpaired surrogates.
int savedFrom = matcher.from;
int savedLBT = matcher.lookbehindTo;
boolean conditionMatched = false;
int startIndex = (!matcher.transparentBounds) ?
int from = Math.max(i - rmaxChars, startIndex);
matcher.lookbehindTo = i;
if (matcher.transparentBounds)
for (int j = i - rminChars;
!conditionMatched && j >= from;
conditionMatched = cond.match(matcher, j, seq);
matcher.from = savedFrom;
matcher.lookbehindTo = savedLBT;
return !conditionMatched && next.match(matcher, i, seq);
Returns the set union of two CharProperty nodes.
Returns the set intersection of two CharProperty nodes.
Returns the set difference of two CharProperty nodes.
Handles word boundaries. Includes a field to allow this one class to
deal with the different types of word boundaries we can match. The word
characters include underscores, letters, and digits. Non spacing marks
can are also part of a word if they have a base character, otherwise
they are ignored for purposes of finding word boundaries.
int startIndex = matcher.from;
int endIndex = matcher.to;
if (matcher.transparentBounds) { matcher.requireEnd = true;
Non spacing marks only count as word characters in bounds calculations
if they have a base character.
int start = (!matcher.transparentBounds) ?
for (int x=i; x >= start; x--) { Attempts to match a slice in the input using the Boyer-Moore string
matching algorithm. The algorithm is based on the idea that the
pattern can be shifted farther ahead in the search text if it is
matched right to left.
The pattern is compared to the input one character at a time, from
the rightmost character in the pattern to the left. If the characters
all match the pattern has been found. If a character does not match,
the pattern is shifted right a distance that is the maximum of two
functions, the bad character shift and the good suffix shift. This
shift moves the attempted match position through the input more
quickly than a naive one position at a time check.
The bad character shift is based on the character from the text that
did not match. If the character does not appear in the pattern, the
pattern can be shifted completely beyond the bad character. If the
character does occur in the pattern, the pattern can be shifted to
line the pattern up with the next occurrence of that character.
The good suffix shift is based on the idea that some subset on the right
side of the pattern has matched. When a bad character is found, the
pattern can be shifted right by the pattern length if the subset does
not occur again in pattern, or by the amount of distance to the
next occurrence of the subset in the pattern.
Boyer-Moore search methods adapted from code by Amy Yu.
Pre calculates arrays needed to generate the bad character
shift and the good suffix shift. Only the last seven bits
are used to see if chars match; This keeps the tables small
and covers the heavily used ASCII range, but occasionally
results in an aliased match for the bad character shift.
if (!(node instanceof Slice)) { int patternLength = src.length;
int[] lastOcc = new int[128];
int[] optoSft = new int[patternLength];
for (i = 0; i < patternLength; i++) { lastOcc[src[i]&0x7F] = i + 1;
NEXT: for (i = patternLength; i > 0; i--) { for (j = patternLength - 1; j >= i; j--) { if (src[j] == src[j-i]) { optoSft[patternLength-1] = 1;
return new BnMS(src, lastOcc, optoSft, node.next);
return new BnM(src, lastOcc, optoSft, node.next);
BnM(int[] src, int[] lastOcc, int[] optoSft, Node next) { int patternLength = src.length;
int last = matcher.to - patternLength;
NEXT: while (i <= last) { for (int j = patternLength - 1; j >= 0; j--) { boolean ret = next.match(matcher, i + patternLength, seq);
matcher.groups[0] = matcher.first;
matcher.groups[1] = matcher.last;
Supplementary support version of BnM(). Unpaired surrogates are
also handled by this class.
static final class BnMS extends BnM { BnMS(int[] src, int[] lastOcc, int[] optoSft, Node next) { super(src, lastOcc, optoSft, next);
int patternLength = src.length;
NEXT: while (i <= last) { for (int j = countChars(seq, i, patternLength), x = patternLength - 1;
matcher.groups[0] = matcher.first;
matcher.groups[1] = matcher.last;
This must be the very first initializer.
return m == null ? null : m.make();
final int lower, final int upper) {
