8046201: Avoid repeated flattening of nested ConsStrings
authorhannesw
Mon, 23 Jun 2014 18:32:11 +0200
changeset 25239 7cb49fc90bab
parent 25238 28476bdc25ce
child 25240 f92c14b1ca11
8046201: Avoid repeated flattening of nested ConsStrings Reviewed-by: lagergren, attila
nashorn/src/jdk/nashorn/internal/runtime/ConsString.java
nashorn/test/src/jdk/nashorn/internal/runtime/ConsStringTest.java
--- a/nashorn/src/jdk/nashorn/internal/runtime/ConsString.java	Mon Jun 23 21:23:53 2014 +0530
+++ b/nashorn/src/jdk/nashorn/internal/runtime/ConsString.java	Mon Jun 23 18:32:11 2014 +0200
@@ -36,8 +36,12 @@
 public final class ConsString implements CharSequence {
 
     private CharSequence left, right;
-    final private int length;
-    private boolean flat = false;
+    private final int length;
+    private volatile int state = STATE_NEW;
+
+    private final static int STATE_NEW       =  0;
+    private final static int STATE_THRESHOLD =  2;
+    private final static int STATE_FLATTENED = -1;
 
     /**
      * Constructor
@@ -57,7 +61,7 @@
 
     @Override
     public String toString() {
-        return (String) flattened();
+        return (String) flattened(true);
     }
 
     @Override
@@ -67,22 +71,31 @@
 
     @Override
     public char charAt(final int index) {
-        return flattened().charAt(index);
+        return flattened(true).charAt(index);
     }
 
     @Override
     public CharSequence subSequence(final int start, final int end) {
-        return flattened().subSequence(start, end);
+        return flattened(true).subSequence(start, end);
     }
 
-    private CharSequence flattened() {
-        if (!flat) {
-            flatten();
+    /**
+     * Returns the components of this ConsString as a {@code CharSequence} array with two elements.
+     * The elements will be either {@code Strings} or other {@code ConsStrings}.
+     * @return CharSequence array of length 2
+     */
+    public synchronized CharSequence[] getComponents() {
+        return new CharSequence[] { left, right };
+    }
+
+    private CharSequence flattened(boolean flattenNested) {
+        if (state != STATE_FLATTENED) {
+            flatten(flattenNested);
         }
         return left;
     }
 
-    private void flatten() {
+    private synchronized void flatten(boolean flattenNested) {
         // We use iterative traversal as recursion may exceed the stack size limit.
         final char[] chars = new char[length];
         int pos = length;
@@ -97,8 +110,14 @@
         do {
             if (cs instanceof ConsString) {
                 final ConsString cons = (ConsString) cs;
-                stack.addFirst(cons.left);
-                cs = cons.right;
+                // Count the times a cons-string is traversed as part of other cons-strings being flattened.
+                // If it crosses a threshold we flatten the nested cons-string internally.
+                if (cons.state == STATE_FLATTENED || (flattenNested && ++cons.state >= STATE_THRESHOLD)) {
+                    cs = cons.flattened(false);
+                } else {
+                    stack.addFirst(cons.left);
+                    cs = cons.right;
+                }
             } else {
                 final String str = (String) cs;
                 pos -= str.length();
@@ -109,7 +128,7 @@
 
         left = new String(chars);
         right = "";
-        flat = true;
+        state = STATE_FLATTENED;
     }
 
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/nashorn/test/src/jdk/nashorn/internal/runtime/ConsStringTest.java	Mon Jun 23 18:32:11 2014 +0200
@@ -0,0 +1,135 @@
+/*
+ * Copyright (c) 2010, 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package jdk.nashorn.internal.runtime;
+
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertTrue;
+
+import jdk.nashorn.internal.runtime.JSType;
+import jdk.nashorn.internal.runtime.ScriptRuntime;
+import org.testng.annotations.Test;
+
+/**
+ * Tests for JSType methods.
+ *
+ * @test
+ * @run testng jdk.nashorn.internal.runtime.ConsStringTest
+ */
+public class ConsStringTest {
+
+    /**
+     * Test toString conversion
+     */
+    @Test
+    public void testConsStringToString() {
+        final ConsString cs1 = new ConsString("b", "c");
+        final ConsString cs2 = new ConsString("d", "e");
+        final ConsString cs3 = new ConsString(cs1, cs2);
+        final ConsString cs4 = new ConsString(cs3, "f");
+        final ConsString cs5 = new ConsString("a", cs4);
+        assertEquals(cs5.toString(), "abcdef");
+        assertEquals(cs4.toString(), "bcdef");
+        assertEquals(cs3.toString(), "bcde");
+        assertEquals(cs2.toString(), "de");
+        assertEquals(cs1.toString(), "bc");
+        // ConsStrings should be flattened now
+        assertEquals(cs1.getComponents()[0], "bc");
+        assertEquals(cs1.getComponents()[1], "");
+        assertEquals(cs2.getComponents()[0], "de");
+        assertEquals(cs2.getComponents()[1], "");
+        assertEquals(cs3.getComponents()[0], "bcde");
+        assertEquals(cs3.getComponents()[1], "");
+        assertEquals(cs4.getComponents()[0], "bcdef");
+        assertEquals(cs4.getComponents()[1], "");
+        assertEquals(cs5.getComponents()[0], "abcdef");
+        assertEquals(cs5.getComponents()[1], "");
+    }
+
+    /**
+     * Test charAt
+     */
+    @Test
+    public void testConsStringCharAt() {
+        final ConsString cs1 = new ConsString("b", "c");
+        final ConsString cs2 = new ConsString("d", "e");
+        final ConsString cs3 = new ConsString(cs1, cs2);
+        final ConsString cs4 = new ConsString(cs3, "f");
+        final ConsString cs5 = new ConsString("a", cs4);
+        assertEquals(cs1.charAt(1), 'c');
+        assertEquals(cs2.charAt(0), 'd');
+        assertEquals(cs3.charAt(3), 'e');
+        assertEquals(cs4.charAt(1), 'c');
+        assertEquals(cs5.charAt(2), 'c');
+        // ConsStrings should be flattened now
+        assertEquals(cs1.getComponents()[0], "bc");
+        assertEquals(cs1.getComponents()[1], "");
+        assertEquals(cs2.getComponents()[0], "de");
+        assertEquals(cs2.getComponents()[1], "");
+        assertEquals(cs3.getComponents()[0], "bcde");
+        assertEquals(cs3.getComponents()[1], "");
+        assertEquals(cs4.getComponents()[0], "bcdef");
+        assertEquals(cs4.getComponents()[1], "");
+        assertEquals(cs5.getComponents()[0], "abcdef");
+        assertEquals(cs5.getComponents()[1], "");
+    }
+
+
+    /**
+     * Test flattening of top-level and internal ConsStrings
+     */
+    @Test
+    public void testConsStringFlattening() {
+        final ConsString cs1 = new ConsString("b", "c");
+        final ConsString cs2 = new ConsString("d", "e");
+        final ConsString cs3 = new ConsString(cs1, cs2);
+        final ConsString cs4 = new ConsString(cs3, "f");
+
+        final ConsString cs5 = new ConsString("a", cs4);
+        // top-level ConsString should not yet be flattened
+        assert(cs5.getComponents()[0] == "a");
+        assert(cs5.getComponents()[1] == cs4);
+        assertEquals(cs5.toString(), "abcdef");
+        // top-level ConsString should be flattened
+        assertEquals(cs5.getComponents()[0], "abcdef");
+        assertEquals(cs5.getComponents()[1], "");
+        // internal ConsString should not yet be flattened after first traversal
+        assertEquals(cs4.getComponents()[0], cs3);
+        assertEquals(cs4.getComponents()[1], "f");
+
+        final ConsString cs6 = new ConsString("a", cs4);
+        // top-level ConsString should not yet be flattened
+        assertEquals(cs6.getComponents()[0], "a");
+        assertEquals(cs6.getComponents()[1], cs4);
+        assertEquals(cs6.toString(), "abcdef");
+        // top-level ConsString should be flattened
+        assertEquals(cs6.getComponents()[0], "abcdef");
+        assertEquals(cs6.getComponents()[1], "");
+        // internal ConsString should have been flattened after second traversal
+        assertEquals(cs4.getComponents()[0], "bcdef");
+        assertEquals(cs4.getComponents()[1], "");
+    }
+}