1 /*
   2  * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.runtime;
  27 
  28 import static jdk.nashorn.internal.runtime.JSType.isString;
  29 
  30 import java.util.ArrayDeque;
  31 import java.util.Deque;
  32 
  33 /**
  34  * This class represents a string composed of two parts which may themselves be
  35  * instances of <code>ConsString</code> or {@link String}. Copying of characters to
  36  * a proper string is delayed until it becomes necessary.
  37  */
  38 public final class ConsString implements CharSequence {
  39 
  40     private CharSequence left, right;
  41     private final int length;
  42     private volatile int state = STATE_NEW;
  43 
  44     private final static int STATE_NEW       =  0;
  45     private final static int STATE_THRESHOLD =  2;
  46     private final static int STATE_FLATTENED = -1;
  47 
  48     /**
  49      * Constructor
  50      *
  51      * Takes two {@link CharSequence} instances that, concatenated, forms this {@code ConsString}
  52      *
  53      * @param left  left char sequence
  54      * @param right right char sequence
  55      */
  56     public ConsString(final CharSequence left, final CharSequence right) {
  57         assert isString(left);
  58         assert isString(right);
  59         this.left = left;
  60         this.right = right;
  61         length = left.length() + right.length();
  62         if (length < 0) {
  63             throw new IllegalArgumentException("too big concatenated String");
  64         }
  65     }
  66 
  67     @Override
  68     public String toString() {
  69         return (String) flattened(true);
  70     }
  71 
  72     @Override
  73     public int length() {
  74         return length;
  75     }
  76 
  77     @Override
  78     public char charAt(final int index) {
  79         return flattened(true).charAt(index);
  80     }
  81 
  82     @Override
  83     public CharSequence subSequence(final int start, final int end) {
  84         return flattened(true).subSequence(start, end);
  85     }
  86 
  87     /**
  88      * Returns the components of this ConsString as a {@code CharSequence} array with two elements.
  89      * The elements will be either {@code Strings} or other {@code ConsStrings}.
  90      * @return CharSequence array of length 2
  91      */
  92     public synchronized CharSequence[] getComponents() {
  93         return new CharSequence[] { left, right };
  94     }
  95 
  96     private CharSequence flattened(final boolean flattenNested) {
  97         if (state != STATE_FLATTENED) {
  98             flatten(flattenNested);
  99         }
 100         return left;
 101     }
 102 
 103     private synchronized void flatten(final boolean flattenNested) {
 104         // We use iterative traversal as recursion may exceed the stack size limit.
 105         final char[] chars = new char[length];
 106         int pos = length;
 107         // Strings are most often composed by appending to the end, which causes ConsStrings
 108         // to be very unbalanced, with mostly single string elements on the right and a long
 109         // linear list on the left. Traversing from right to left helps to keep the stack small
 110         // in this scenario.
 111         final Deque<CharSequence> stack = new ArrayDeque<>();
 112         stack.addFirst(left);
 113         CharSequence cs = right;
 114 
 115         do {
 116             if (cs instanceof ConsString) {
 117                 final ConsString cons = (ConsString) cs;
 118                 // Count the times a cons-string is traversed as part of other cons-strings being flattened.
 119                 // If it crosses a threshold we flatten the nested cons-string internally.
 120                 if (cons.state == STATE_FLATTENED || (flattenNested && ++cons.state >= STATE_THRESHOLD)) {
 121                     cs = cons.flattened(false);
 122                 } else {
 123                     stack.addFirst(cons.left);
 124                     cs = cons.right;
 125                 }
 126             } else {
 127                 final String str = (String) cs;
 128                 pos -= str.length();
 129                 str.getChars(0, str.length(), chars, pos);
 130                 cs = stack.isEmpty() ? null : stack.pollFirst();
 131             }
 132         } while (cs != null);
 133 
 134         left = new String(chars);
 135         right = "";
 136         state = STATE_FLATTENED;
 137     }
 138 
 139 }