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;

public final class Pattern

implements java.io.Serializable

{

/**

/**

public static final int UNIX_LINES = 0x01;

/**

public static final int CASE_INSENSITIVE = 0x02;

/**

public static final int COMMENTS = 0x04;

/**

public static final int MULTILINE = 0x08;

/**

public static final int LITERAL = 0x10;

/**

public static final int DOTALL = 0x20;

/**

public static final int UNICODE_CASE = 0x40;

/**

public static final int CANON_EQ = 0x80;

/**

public static final int UNICODE_CHARACTER_CLASS = 0x100;

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

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

private static final long serialVersionUID = 5073258162644648461L;

/**

private String pattern;

/**

private int flags;

/**

private transient volatile boolean compiled = false;

/**

private transient String normalizedPattern;

/**

transient Node root;

/**

transient Node matchRoot;

/**

transient int[] buffer;

/**

transient volatile Map<String, Integer> namedGroups;

/**

transient GroupHead[] groupNodes;

/**

private transient int[] temp;

/**

transient int capturingGroupCount;

/**

transient int localCount;

/**

private transient int cursor;

/**

private transient int patternLength;

/**

private transient boolean hasSupplementary;

/**

public static Pattern compile(String regex) {

return new Pattern(regex, 0);

}

/**

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

return new Pattern(regex, flags);

}

/**

public String pattern() {

return pattern;

}

/**

public String toString() {

return pattern;

}

/**

public Matcher matcher(CharSequence input) {

if (!compiled) {

synchronized(this) {

if (!compiled)

compile();

}

}

Matcher m = new Matcher(this, input);

return m;

}

/**

public int flags() {

return flags;

}

/**

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

Pattern p = Pattern.compile(regex);

Matcher m = p.matcher(input);

return m.matches();

}

/**

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);

}

/**

public String[] split(CharSequence input) {

return split(input, 0);

}

/**

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();

}

/**

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;

}

}

/**

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;

}

}

/**

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();

}

/**

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;

}

/**

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();

}

/**

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);

}

/**

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;

}

}

/**

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

}

/**

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;

}

/**

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;

}

}

}

/**

static final class TreeInfo {

int minLength;

int maxLength;

boolean maxValid;

boolean deterministic;

TreeInfo() {

reset();

}

void reset() {

minLength = 0;

maxLength = 0;

maxValid = true;

deterministic = true;

}

}

/*

/**

private boolean has(int f) {

return (flags & f) != 0;

}

/**

private void accept(int ch, String s) {

int testChar = temp[cursor++];

if (has(COMMENTS))

testChar = parsePastWhitespace(testChar);

if (ch != testChar) {

throw error(s);

}

}

/**

private void mark(int c) {

temp[patternLength] = c;

}

/**

private int peek() {

int ch = temp[cursor];

if (has(COMMENTS))

ch = peekPastWhitespace(ch);

return ch;

}

/**

private int read() {

int ch = temp[cursor++];

if (has(COMMENTS))

ch = parsePastWhitespace(ch);

return ch;

}

/**

private int readEscaped() {

int ch = temp[cursor++];

return ch;

}

/**

private int next() {

int ch = temp[++cursor];

if (has(COMMENTS))

ch = peekPastWhitespace(ch);

return ch;

}

/**

private int nextEscaped() {

int ch = temp[++cursor];

return ch;

}

/**

private int peekPastWhitespace(int ch) {

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

while (ASCII.isSpace(ch))

ch = temp[++cursor];

if (ch == '#') {

ch = peekPastLine();

}

}

return ch;

}

/**

private int parsePastWhitespace(int ch) {

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

while (ASCII.isSpace(ch))

ch = temp[cursor++];

if (ch == '#')

ch = parsePastLine();

}

return ch;

}

/**

private int parsePastLine() {

int ch = temp[cursor++];

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

ch = temp[cursor++];

return ch;

}

/**

private int peekPastLine() {

int ch = temp[++cursor];

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

ch = temp[++cursor];

return ch;

}

/**

private boolean isLineSeparator(int ch) {

if (has(UNIX_LINES)) {

return ch == '\n';

} else {

return (ch == '\n' ||

ch == '\r' ||

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

ch == '\u0085');

}

}

/**

private int skip() {

int i = cursor;

int ch = temp[i+1];

cursor = i + 2;

return ch;

}

/**

private void unread() {

cursor--;

}

/**

private PatternSyntaxException error(String s) {

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

}

/**

private boolean findSupplementary(int start, int end) {

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

if (isSupplementary(temp[i]))

return true;

}

return false;

}

/**

private static final boolean isSupplementary(int ch) {

return ch >= Character.MIN_SUPPLEMENTARY_CODE_POINT ||

Character.isSurrogate((char)ch);

}

/**

/**

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();

}

}

/**

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;

}

/**

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;

}

/**

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);

}

/**

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");

}

/**

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.

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);

}

/**

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;

}

}

/**

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}

String value = name.substring(i + 1);

name = name.substring(0, i).toLowerCase(Locale.ENGLISH);

if ("sc".equals(name) || "script".equals(name)) {

node = unicodeScriptPropertyFor(value);

} else if ("blk".equals(name) || "block".equals(name)) {

node = unicodeBlockPropertyFor(value);

} else if ("gc".equals(name) || "general_category".equals(name)) {

node = charPropertyNodeFor(value);

} else {

throw error("Unknown Unicode property {name=<" + name + ">, "

+ "value=<" + value + ">}");

}

} else {

if (name.startsWith("In")) {

// \p{inBlockName}

node = unicodeBlockPropertyFor(name.substring(2));

} else if (name.startsWith("Is")) {

// \p{isGeneralCategory} and \p{isScriptName}

name = name.substring(2);

UnicodeProp uprop = UnicodeProp.forName(name);

if (uprop != null)

node = new Utype(uprop);

if (node == null)

node = CharPropertyNames.charPropertyFor(name);

if (node == null)

node = unicodeScriptPropertyFor(name);

} else {

if (has(UNICODE_CHARACTER_CLASS)) {

UnicodeProp uprop = UnicodeProp.forPOSIXName(name);

if (uprop != null)

node = new Utype(uprop);

}

if (node == null)

node = charPropertyNodeFor(name);

}

}

if (maybeComplement) {

if (node instanceof Category || node instanceof Block)

hasSupplementary = true;

node = node.complement();

}

return node;

}

/**

private CharProperty unicodeScriptPropertyFor(String name) {

final Character.UnicodeScript script;

try {

script = Character.UnicodeScript.forName(name);

} catch (IllegalArgumentException iae) {

throw error("Unknown character script name {" + name + "}");

}

return new Script(script);

}

/**

private CharProperty unicodeBlockPropertyFor(String name) {

final Character.UnicodeBlock block;

try {

block = Character.UnicodeBlock.forName(name);

} catch (IllegalArgumentException iae) {

throw error("Unknown character block name {" + name + "}");

}

return new Block(block);

}

/**

private CharProperty charPropertyNodeFor(String name) {

CharProperty p = CharPropertyNames.charPropertyFor(name);

if (p == null)

throw error("Unknown character property name {" + name + "}");

return p;

}

/**

private String groupname(int ch) {

StringBuilder sb = new StringBuilder();

sb.append(Character.toChars(ch));

while (ASCII.isLower(ch=read()) || ASCII.isUpper(ch) ||

ASCII.isDigit(ch)) {

sb.append(Character.toChars(ch));

}

if (sb.length() == 0)

throw error("named capturing group has 0 length name");

if (ch != '>')

throw error("named capturing group is missing trailing '>'");

return sb.toString();

}

/**

private Node group0() {

boolean capturingGroup = false;

Node head = null;

Node tail = null;

int save = flags;

root = null;

int ch = next();

if (ch == '?') {

ch = skip();

switch (ch) {

case ':': // (?:xxx) pure group

head = createGroup(true);

tail = root;

head.next = expr(tail);

break;

case '=': // (?=xxx) and (?!xxx) lookahead

case '!':

head = createGroup(true);

tail = root;

head.next = expr(tail);

if (ch == '=') {

head = tail = new Pos(head);

} else {

head = tail = new Neg(head);

}

break;

case '>': // (?>xxx) independent group

head = createGroup(true);

tail = root;

head.next = expr(tail);

head = tail = new Ques(head, INDEPENDENT);

break;

case '<': // (?<xxx) look behind

ch = read();

if (ASCII.isLower(ch) || ASCII.isUpper(ch)) {

// named captured group

String name = groupname(ch);

if (namedGroups().containsKey(name))

throw error("Named capturing group <" + name

+ "> is already defined");

capturingGroup = true;

head = createGroup(false);

tail = root;

namedGroups().put(name, capturingGroupCount-1);

head.next = expr(tail);

break;

}

int start = cursor;

head = createGroup(true);

tail = root;

head.next = expr(tail);

tail.next = lookbehindEnd;

TreeInfo info = new TreeInfo();

head.study(info);

if (info.maxValid == false) {

throw error("Look-behind group does not have "

+ "an obvious maximum length");

}

boolean hasSupplementary = findSupplementary(start, patternLength);

if (ch == '=') {

head = tail = (hasSupplementary ?

new BehindS(head, info.maxLength,

info.minLength) :

new Behind(head, info.maxLength,

info.minLength));

} else if (ch == '!') {

head = tail = (hasSupplementary ?

new NotBehindS(head, info.maxLength,

info.minLength) :

new NotBehind(head, info.maxLength,

info.minLength));

} else {

throw error("Unknown look-behind group");

}

break;

case '$':

case '@':

throw error("Unknown group type");

default: // (?xxx:) inlined match flags

unread();

addFlag();

ch = read();

if (ch == ')') {

return null; // Inline modifier only

}

if (ch != ':') {

throw error("Unknown inline modifier");

}

head = createGroup(true);

tail = root;