ConsString.java revision 1196:d0efd099521a 
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
26package jdk.nashorn.internal.runtime;
27
28import static jdk.nashorn.internal.runtime.JSType.isString;
29
30import java.util.ArrayDeque;
31import java.util.Deque;
32
33/**
34 * This class represents a string composed of two parts which may themselves be
35 * instances of <tt>ConsString</tt> or {@link String}. Copying of characters to
36 * a proper string is delayed until it becomes necessary.
37 */
38public 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}
140