Back to index...

	/*
	* Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
	*/
	/*
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You under the Apache License, Version 2.0
	* (the "License"); you may not use this file except in compliance with
	* the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.sun.org.apache.xerces.internal.impl.xpath.regex;

	/**
	* This class represents a character class such as [a-z] or a period.
	*
	* @xerces.internal
	*
	*/
	final class RangeToken extends Token implements java.io.Serializable {

	private static final long serialVersionUID = 3257568399592010545L;

	int[] ranges;
	boolean sorted;
	boolean compacted;
	RangeToken icaseCache = null;
	int[] map = null;
	int nonMapIndex;

	RangeToken(int type) {
	super(type);
	this.setSorted(false);
	}

	// for RANGE or NRANGE
	protected void addRange(int start, int end) {
	this.icaseCache = null;
	//System.err.println("Token#addRange(): "+start+" "+end);
	int r1, r2;
	if (start <= end) {
	r1 = start;
	r2 = end;
	} else {
	r1 = end;
	r2 = start;
	}

	int pos = 0;
	if (this.ranges == null) {
	this.ranges = new int[2];
	this.ranges[0] = r1;
	this.ranges[1] = r2;
	this.setSorted(true);
	} else {
	pos = this.ranges.length;
	if (this.ranges[pos-1]+1 == r1) {
	this.ranges[pos-1] = r2;
	return;
	}
	int[] temp = new int[pos+2];
	System.arraycopy(this.ranges, 0, temp, 0, pos);
	this.ranges = temp;
	if (this.ranges[pos-1] >= r1)
	this.setSorted(false);
	this.ranges[pos++] = r1;
	this.ranges[pos] = r2;
	if (!this.sorted)
	this.sortRanges();
	}
	}

	private final boolean isSorted() {
	return this.sorted;
	}
	private final void setSorted(boolean sort) {
	this.sorted = sort;
	if (!sort) this.compacted = false;
	}
	private final boolean isCompacted() {
	return this.compacted;
	}
	private final void setCompacted() {
	this.compacted = true;
	}

	protected void sortRanges() {
	if (this.isSorted())
	return;
	if (this.ranges == null)
	return;
	//System.err.println("Do sorting: "+this.ranges.length);

	// Bubble sort
	// Why? -- In many cases,
	// this.ranges has few elements.
	for (int i = this.ranges.length-4; i >= 0; i -= 2) {
	for (int j = 0; j <= i; j += 2) {
	if (this.ranges[j] > this.ranges[j+2]
	\|\| this.ranges[j] == this.ranges[j+2] && this.ranges[j+1] > this.ranges[j+3]) {
	int tmp;
	tmp = this.ranges[j+2];
	this.ranges[j+2] = this.ranges[j];
	this.ranges[j] = tmp;
	tmp = this.ranges[j+3];
	this.ranges[j+3] = this.ranges[j+1];
	this.ranges[j+1] = tmp;
	}
	}
	}
	this.setSorted(true);
	}

	/**
	* this.ranges is sorted.
	*/
	protected void compactRanges() {
	boolean DEBUG = false;
	if (this.ranges == null \|\| this.ranges.length <= 2)
	return;
	if (this.isCompacted())
	return;
	int base = 0; // Index of writing point
	int target = 0; // Index of processing point

	while (target < this.ranges.length) {
	if (base != target) {
	this.ranges[base] = this.ranges[target++];
	this.ranges[base+1] = this.ranges[target++];
	} else
	target += 2;
	int baseend = this.ranges[base+1];
	while (target < this.ranges.length) {
	if (baseend+1 < this.ranges[target])
	break;
	if (baseend+1 == this.ranges[target]) {
	if (DEBUG)
	System.err.println("Token#compactRanges(): Compaction: ["+this.ranges[base]
	+", "+this.ranges[base+1]
	+"], ["+this.ranges[target]
	+", "+this.ranges[target+1]
	+"] -> ["+this.ranges[base]
	+", "+this.ranges[target+1]
	+"]");
	this.ranges[base+1] = this.ranges[target+1];
	baseend = this.ranges[base+1];
	target += 2;
	} else if (baseend >= this.ranges[target+1]) {
	if (DEBUG)
	System.err.println("Token#compactRanges(): Compaction: ["+this.ranges[base]
	+", "+this.ranges[base+1]
	+"], ["+this.ranges[target]
	+", "+this.ranges[target+1]
	+"] -> ["+this.ranges[base]
	+", "+this.ranges[base+1]
	+"]");
	target += 2;
	} else if (baseend < this.ranges[target+1]) {
	if (DEBUG)
	System.err.println("Token#compactRanges(): Compaction: ["+this.ranges[base]
	+", "+this.ranges[base+1]
	+"], ["+this.ranges[target]
	+", "+this.ranges[target+1]
	+"] -> ["+this.ranges[base]
	+", "+this.ranges[target+1]
	+"]");
	this.ranges[base+1] = this.ranges[target+1];
	baseend = this.ranges[base+1];
	target += 2;
	} else {
	throw new RuntimeException("Token#compactRanges(): Internel Error: ["
	+this.ranges[base]
	+","+this.ranges[base+1]
	+"] ["+this.ranges[target]
	+","+this.ranges[target+1]+"]");
	}
	} // while
	base += 2;
	}

	if (base != this.ranges.length) {
	int[] result = new int[base];
	System.arraycopy(this.ranges, 0, result, 0, base);
	this.ranges = result;
	}
	this.setCompacted();
	}

	protected void mergeRanges(Token token) {
	RangeToken tok = (RangeToken)token;
	this.sortRanges();
	tok.sortRanges();
	if (tok.ranges == null)
	return;
	this.icaseCache = null;
	this.setSorted(true);
	if (this.ranges == null) {
	this.ranges = new int[tok.ranges.length];
	System.arraycopy(tok.ranges, 0, this.ranges, 0, tok.ranges.length);
	return;
	}
	int[] result = new int[this.ranges.length+tok.ranges.length];
	for (int i = 0, j = 0, k = 0; i < this.ranges.length \|\| j < tok.ranges.length;) {
	if (i >= this.ranges.length) {
	result[k++] = tok.ranges[j++];
	result[k++] = tok.ranges[j++];
	} else if (j >= tok.ranges.length) {
	result[k++] = this.ranges[i++];
	result[k++] = this.ranges[i++];
	} else if (tok.ranges[j] < this.ranges[i]
	\|\| tok.ranges[j] == this.ranges[i] && tok.ranges[j+1] < this.ranges[i+1]) {
	result[k++] = tok.ranges[j++];
	result[k++] = tok.ranges[j++];
	} else {
	result[k++] = this.ranges[i++];
	result[k++] = this.ranges[i++];
	}
	}
	this.ranges = result;
	}

	protected void subtractRanges(Token token) {
	if (token.type == NRANGE) {
	this.intersectRanges(token);
	return;
	}
	RangeToken tok = (RangeToken)token;
	if (tok.ranges == null \|\| this.ranges == null)
	return;
	this.icaseCache = null;
	this.sortRanges();
	this.compactRanges();
	tok.sortRanges();
	tok.compactRanges();

	//System.err.println("Token#substractRanges(): Entry: "+this.ranges.length+", "+tok.ranges.length);

	int[] result = new int[this.ranges.length+tok.ranges.length];
	int wp = 0, src = 0, sub = 0;
	while (src < this.ranges.length && sub < tok.ranges.length) {
	int srcbegin = this.ranges[src];
	int srcend = this.ranges[src+1];
	int subbegin = tok.ranges[sub];
	int subend = tok.ranges[sub+1];
	if (srcend < subbegin) { // Not overlapped
	// src: o-----o
	// sub: o-----o
	// res: o-----o
	// Reuse sub
	result[wp++] = this.ranges[src++];
	result[wp++] = this.ranges[src++];
	} else if (srcend >= subbegin
	&& srcbegin <= subend) { // Overlapped
	// src: o--------o
	// sub: o----o
	// sub: o----o
	// sub: o----o
	// sub: o------------o
	if (subbegin <= srcbegin && srcend <= subend) {
	// src: o--------o
	// sub: o------------o
	// res: empty
	// Reuse sub
	src += 2;
	} else if (subbegin <= srcbegin) {
	// src: o--------o
	// sub: o----o
	// res: o-----o
	// Reuse src(=res)
	this.ranges[src] = subend+1;
	sub += 2;
	} else if (srcend <= subend) {
	// src: o--------o
	// sub: o----o
	// res: o-----o
	// Reuse sub
	result[wp++] = srcbegin;
	result[wp++] = subbegin-1;
	src += 2;
	} else {
	// src: o--------o
	// sub: o----o
	// res: o-o o-o
	// Reuse src(=right res)
	result[wp++] = srcbegin;
	result[wp++] = subbegin-1;
	this.ranges[src] = subend+1;
	sub += 2;
	}
	} else if (subend < srcbegin) {
	// Not overlapped
	// src: o-----o
	// sub: o----o
	sub += 2;
	} else {
	throw new RuntimeException("Token#subtractRanges(): Internal Error: ["+this.ranges[src]
	+","+this.ranges[src+1]
	+"] - ["+tok.ranges[sub]
	+","+tok.ranges[sub+1]
	+"]");
	}
	}
	while (src < this.ranges.length) {
	result[wp++] = this.ranges[src++];
	result[wp++] = this.ranges[src++];
	}
	this.ranges = new int[wp];
	System.arraycopy(result, 0, this.ranges, 0, wp);
	// this.ranges is sorted and compacted.
	}

	/**
	* @param tok Ignore whether it is NRANGE or not.
	*/
	protected void intersectRanges(Token token) {
	RangeToken tok = (RangeToken)token;
	if (tok.ranges == null \|\| this.ranges == null)
	return;
	this.icaseCache = null;
	this.sortRanges();
	this.compactRanges();
	tok.sortRanges();
	tok.compactRanges();

	int[] result = new int[this.ranges.length+tok.ranges.length];
	int wp = 0, src1 = 0, src2 = 0;
	while (src1 < this.ranges.length && src2 < tok.ranges.length) {
	int src1begin = this.ranges[src1];
	int src1end = this.ranges[src1+1];
	int src2begin = tok.ranges[src2];
	int src2end = tok.ranges[src2+1];
	if (src1end < src2begin) { // Not overlapped
	// src1: o-----o
	// src2: o-----o
	// res: empty
	// Reuse src2
	src1 += 2;
	} else if (src1end >= src2begin
	&& src1begin <= src2end) { // Overlapped
	// src1: o--------o
	// src2: o----o
	// src2: o----o
	// src2: o----o
	// src2: o------------o
	if (src2begin <= src1begin && src1end <= src2end) {
	// src1: o--------o
	// src2: o------------o
	// res: o--------o
	// Reuse src2
	result[wp++] = src1begin;
	result[wp++] = src1end;
	src1 += 2;
	} else if (src2begin <= src1begin) {
	// src1: o--------o
	// src2: o----o
	// res: o--o
	// Reuse the rest of src1
	result[wp++] = src1begin;
	result[wp++] = src2end;
	this.ranges[src1] = src2end+1;
	src2 += 2;
	} else if (src1end <= src2end) {
	// src1: o--------o
	// src2: o----o
	// res: o--o
	// Reuse src2
	result[wp++] = src2begin;
	result[wp++] = src1end;
	src1 += 2;
	} else {
	// src1: o--------o
	// src2: o----o
	// res: o----o
	// Reuse the rest of src1
	result[wp++] = src2begin;
	result[wp++] = src2end;
	this.ranges[src1] = src2end+1;
	src2 += 2;
	}
	} else if (src2end < src1begin) {
	// Not overlapped
	// src1: o-----o
	// src2: o----o
	src2 += 2;
	} else {
	throw new RuntimeException("Token#intersectRanges(): Internal Error: ["
	+this.ranges[src1]
	+","+this.ranges[src1+1]
	+"] & ["+tok.ranges[src2]
	+","+tok.ranges[src2+1]
	+"]");
	}
	}
	this.ranges = new int[wp];
	System.arraycopy(result, 0, this.ranges, 0, wp);
	// this.ranges is sorted and compacted.
	}

	/**
	* for RANGE: Creates complement.
	* for NRANGE: Creates the same meaning RANGE.
	*/
	static Token complementRanges(Token token) {
	if (token.type != RANGE && token.type != NRANGE)
	throw new IllegalArgumentException("Token#complementRanges(): must be RANGE: "+token.type);
	RangeToken tok = (RangeToken)token;
	tok.sortRanges();
	tok.compactRanges();
	int len = tok.ranges.length+2;
	if (tok.ranges[0] == 0)
	len -= 2;
	int last = tok.ranges[tok.ranges.length-1];
	if (last == UTF16_MAX)
	len -= 2;
	RangeToken ret = Token.createRange();
	ret.ranges = new int[len];
	int wp = 0;
	if (tok.ranges[0] > 0) {
	ret.ranges[wp++] = 0;
	ret.ranges[wp++] = tok.ranges[0]-1;
	}
	for (int i = 1; i < tok.ranges.length-2; i += 2) {
	ret.ranges[wp++] = tok.ranges[i]+1;
	ret.ranges[wp++] = tok.ranges[i+1]-1;
	}
	if (last != UTF16_MAX) {
	ret.ranges[wp++] = last+1;
	ret.ranges[wp] = UTF16_MAX;
	}
	ret.setCompacted();
	return ret;
	}

	synchronized RangeToken getCaseInsensitiveToken() {
	if (this.icaseCache != null)
	return this.icaseCache;

	RangeToken uppers = this.type == Token.RANGE ? Token.createRange() : Token.createNRange();
	for (int i = 0; i < this.ranges.length; i += 2) {
	for (int ch = this.ranges[i]; ch <= this.ranges[i+1]; ch ++) {
	if (ch > 0xffff)
	uppers.addRange(ch, ch);
	else {
	char uch = Character.toUpperCase((char)ch);
	uppers.addRange(uch, uch);
	}
	}
	}
	RangeToken lowers = this.type == Token.RANGE ? Token.createRange() : Token.createNRange();
	for (int i = 0; i < uppers.ranges.length; i += 2) {
	for (int ch = uppers.ranges[i]; ch <= uppers.ranges[i+1]; ch ++) {
	if (ch > 0xffff)
	lowers.addRange(ch, ch);
	else {
	char lch = Character.toLowerCase((char)ch);
	lowers.addRange(lch, lch);
	}
	}
	}
	lowers.mergeRanges(uppers);
	lowers.mergeRanges(this);
	lowers.compactRanges();

	this.icaseCache = lowers;
	return lowers;
	}

	void dumpRanges() {
	System.err.print("RANGE: ");
	if (this.ranges == null) {
	System.err.println(" NULL");
	return;
	}
	for (int i = 0; i < this.ranges.length; i += 2) {
	System.err.print("["+this.ranges[i]+","+this.ranges[i+1]+"] ");
	}
	System.err.println("");
	}

	boolean match(int ch) {
	if (this.map == null) this.createMap();
	boolean ret;
	if (this.type == RANGE) {
	if (ch < MAPSIZE)
	return (this.map[ch/32] & (1<<(ch&0x1f))) != 0;
	ret = false;
	for (int i = this.nonMapIndex; i < this.ranges.length; i += 2) {
	if (this.ranges[i] <= ch && ch <= this.ranges[i+1])
	return true;
	}
	} else {
	if (ch < MAPSIZE)
	return (this.map[ch/32] & (1<<(ch&0x1f))) == 0;
	ret = true;
	for (int i = this.nonMapIndex; i < this.ranges.length; i += 2) {
	if (this.ranges[i] <= ch && ch <= this.ranges[i+1])
	return false;
	}
	}
	return ret;
	}

	private static final int MAPSIZE = 256;
	private void createMap() {
	int asize = MAPSIZE/32; // 32 is the number of bits in `int'.
	int [] map = new int[asize];
	int nonMapIndex = this.ranges.length;
	for (int i = 0; i < asize; ++i) {
	map[i] = 0;
	}
	for (int i = 0; i < this.ranges.length; i += 2) {
	int s = this.ranges[i];
	int e = this.ranges[i+1];
	if (s < MAPSIZE) {
	for (int j = s; j <= e && j < MAPSIZE; j++) {
	map[j/32] \|= 1<<(j&0x1f); // s&0x1f : 0-31
	}
	}
	else {
	nonMapIndex = i;
	break;
	}
	if (e >= MAPSIZE) {
	nonMapIndex = i;
	break;
	}
	}
	this.map = map;
	this.nonMapIndex = nonMapIndex;
	//for (int i = 0; i < asize; i ++) System.err.println("Map: "+Integer.toString(this.map[i], 16));
	}

	public String toString(int options) {
	String ret;
	if (this.type == RANGE) {
	if (this == Token.token_dot)
	ret = ".";
	else if (this == Token.token_0to9)
	ret = "\\d";
	else if (this == Token.token_wordchars)
	ret = "\\w";
	else if (this == Token.token_spaces)
	ret = "\\s";
	else {
	StringBuilder sb = new StringBuilder();
	sb.append('[');
	for (int i = 0; i < this.ranges.length; i += 2) {
	if ((options & RegularExpression.SPECIAL_COMMA) != 0 && i > 0) sb.append(',');
	if (this.ranges[i] == this.ranges[i+1]) {
	sb.append(escapeCharInCharClass(this.ranges[i]));
	} else {
	sb.append(escapeCharInCharClass(this.ranges[i]));
	sb.append('-');
	sb.append(escapeCharInCharClass(this.ranges[i+1]));
	}
	}
	sb.append(']');
	ret = sb.toString();
	}
	} else {
	if (this == Token.token_not_0to9)
	ret = "\\D";
	else if (this == Token.token_not_wordchars)
	ret = "\\W";
	else if (this == Token.token_not_spaces)
	ret = "\\S";
	else {
	StringBuffer sb = new StringBuffer();
	sb.append("[^");
	for (int i = 0; i < this.ranges.length; i += 2) {
	if ((options & RegularExpression.SPECIAL_COMMA) != 0 && i > 0) sb.append(',');
	if (this.ranges[i] == this.ranges[i+1]) {
	sb.append(escapeCharInCharClass(this.ranges[i]));
	} else {
	sb.append(escapeCharInCharClass(this.ranges[i]));
	sb.append('-');
	sb.append(escapeCharInCharClass(this.ranges[i+1]));
	}
	}
	sb.append(']');
	ret = sb.toString();
	}
	}
	return ret;
	}

	private static String escapeCharInCharClass(int ch) {
	String ret;
	switch (ch) {
	case '[': case ']': case '-': case '^':
	case ',': case '\\':
	ret = "\\"+(char)ch;
	break;
	case '\f': ret = "\\f"; break;
	case '\n': ret = "\\n"; break;
	case '\r': ret = "\\r"; break;
	case '\t': ret = "\\t"; break;
	case 0x1b: ret = "\\e"; break;
	//case 0x0b: ret = "\\v"; break;
	default:
	if (ch < 0x20) {
	String pre = "0"+Integer.toHexString(ch);
	ret = "\\x"+pre.substring(pre.length()-2, pre.length());
	} else if (ch >= 0x10000) {
	String pre = "0"+Integer.toHexString(ch);
	ret = "\\v"+pre.substring(pre.length()-6, pre.length());
	} else
	ret = ""+(char)ch;
	}
	return ret;
	}

	}

Back to index...