ConsString.java revision 1196:d0efd099521a
11901Swollman/* 21901Swollman * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved. 31901Swollman * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 41901Swollman * 51901Swollman * This code is free software; you can redistribute it and/or modify it 61901Swollman * under the terms of the GNU General Public License version 2 only, as 71901Swollman * published by the Free Software Foundation. Oracle designates this 88870Srgrimes * particular file as subject to the "Classpath" exception as provided 91901Swollman * by Oracle in the LICENSE file that accompanied this code. 101901Swollman * 111901Swollman * This code is distributed in the hope that it will be useful, but WITHOUT 128870Srgrimes * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 131901Swollman * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 141901Swollman * version 2 for more details (a copy is included in the LICENSE file that 151901Swollman * accompanied this code). 168870Srgrimes * 171901Swollman * You should have received a copy of the GNU General Public License version 181901Swollman * 2 along with this work; if not, write to the Free Software Foundation, 191901Swollman * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 208870Srgrimes * 211901Swollman * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 221901Swollman * or visit www.oracle.com if you need additional information or have any 231901Swollman * questions. 248870Srgrimes */ 251901Swollman 261901Swollmanpackage jdk.nashorn.internal.runtime; 271901Swollman 281901Swollmanimport static jdk.nashorn.internal.runtime.JSType.isString; 291901Swollman 308870Srgrimesimport java.util.ArrayDeque; 311901Swollmanimport java.util.Deque; 321901Swollman 338870Srgrimes/** 341901Swollman * This class represents a string composed of two parts which may themselves be 351901Swollman * instances of <tt>ConsString</tt> or {@link String}. Copying of characters to 361901Swollman * a proper string is delayed until it becomes necessary. 371901Swollman */ 381901Swollmanpublic final class ConsString implements CharSequence { 391901Swollman 401901Swollman private CharSequence left, right; 411901Swollman private final int length; 421901Swollman private volatile int state = STATE_NEW; 431901Swollman 441901Swollman private final static int STATE_NEW = 0; 451901Swollman private final static int STATE_THRESHOLD = 2; 461901Swollman private final static int STATE_FLATTENED = -1; 471901Swollman 481901Swollman /** 491901Swollman * Constructor 501901Swollman * 511901Swollman * Takes two {@link CharSequence} instances that, concatenated, forms this {@code ConsString} 521901Swollman * 531901Swollman * @param left left char sequence 541901Swollman * @param right right char sequence 551901Swollman */ 561901Swollman public ConsString(final CharSequence left, final CharSequence right) { 571901Swollman assert isString(left); 581901Swollman assert isString(right); 591901Swollman this.left = left; 601901Swollman this.right = right; 611901Swollman length = left.length() + right.length(); 621901Swollman if (length < 0) { 631901Swollman throw new IllegalArgumentException("too big concatenated String"); 641901Swollman } 651901Swollman } 661901Swollman 671901Swollman @Override 681901Swollman public String toString() { 691901Swollman return (String) flattened(true); 701901Swollman } 711901Swollman 721901Swollman @Override 731901Swollman public int length() { 741901Swollman return length; 751901Swollman } 761901Swollman 771901Swollman @Override 781901Swollman public char charAt(final int index) { 791901Swollman return flattened(true).charAt(index); 801901Swollman } 811901Swollman 821901Swollman @Override 831901Swollman public CharSequence subSequence(final int start, final int end) { 841901Swollman return flattened(true).subSequence(start, end); 851901Swollman } 861901Swollman 871901Swollman /** 881901Swollman * Returns the components of this ConsString as a {@code CharSequence} array with two elements. 891901Swollman * The elements will be either {@code Strings} or other {@code ConsStrings}. 901901Swollman * @return CharSequence array of length 2 911901Swollman */ 921901Swollman public synchronized CharSequence[] getComponents() { 931901Swollman return new CharSequence[] { left, right }; 941901Swollman } 951901Swollman 961901Swollman private CharSequence flattened(final boolean flattenNested) { 971901Swollman if (state != STATE_FLATTENED) { 981901Swollman flatten(flattenNested); 991901Swollman } 1001901Swollman return left; 1011901Swollman } 1021901Swollman 1031901Swollman private synchronized void flatten(final boolean flattenNested) { 1041901Swollman // We use iterative traversal as recursion may exceed the stack size limit. 1051901Swollman final char[] chars = new char[length]; 1061901Swollman int pos = length; 1071901Swollman // Strings are most often composed by appending to the end, which causes ConsStrings 1088870Srgrimes // to be very unbalanced, with mostly single string elements on the right and a long 1091901Swollman // linear list on the left. Traversing from right to left helps to keep the stack small 1101901Swollman // in this scenario. 1118870Srgrimes final Deque<CharSequence> stack = new ArrayDeque<>(); 1121901Swollman stack.addFirst(left); 1138870Srgrimes CharSequence cs = right; 1141901Swollman 1151901Swollman do { 1161901Swollman if (cs instanceof ConsString) { 1171901Swollman final ConsString cons = (ConsString) cs; 1181901Swollman // Count the times a cons-string is traversed as part of other cons-strings being flattened. 1191901Swollman // If it crosses a threshold we flatten the nested cons-string internally. 1201901Swollman if (cons.state == STATE_FLATTENED || (flattenNested && ++cons.state >= STATE_THRESHOLD)) { 1211901Swollman cs = cons.flattened(false); 1221901Swollman } else { 1231901Swollman stack.addFirst(cons.left); 1241901Swollman cs = cons.right; 1251901Swollman } 1261901Swollman } else { 1271901Swollman final String str = (String) cs; 1281901Swollman pos -= str.length(); 1291901Swollman str.getChars(0, str.length(), chars, pos); 1301901Swollman cs = stack.isEmpty() ? null : stack.pollFirst(); 1311901Swollman } 1321901Swollman } while (cs != null); 1331901Swollman 1341901Swollman left = new String(chars); 1351901Swollman right = ""; 1361901Swollman state = STATE_FLATTENED; 1371901Swollman } 1381901Swollman 1391901Swollman} 1401901Swollman