Bug 851064: Allow one-level deep ropes when flattening for substr, r=evilpies
authorHannes Verschore <hv1989@gmail.com>
Mon, 03 Jun 2013 11:27:07 +0200
changeset 133823 ce3ac61c379c81e42797a3d302a5826954975ef7
parent 133813 d2eabe8e27b56ca4e764d1e5f454fecceff11330
child 133824 1797dc46e8622a12ce5e3a1c2f12ea335650e415
push id24773
push userryanvm@gmail.com
push dateTue, 04 Jun 2013 00:43:28 +0000
treeherdermozilla-central@7e3a4ebcf067 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersevilpies
bugs851064
milestone24.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 851064: Allow one-level deep ropes when flattening for substr, r=evilpies
js/src/ion/VMFunctions.cpp
js/src/jit-test/tests/ion/bug851064.js
js/src/jsstr.cpp
js/src/vm/String-inl.h
js/src/vm/String.cpp
js/src/vm/String.h
--- a/js/src/ion/VMFunctions.cpp
+++ b/js/src/ion/VMFunctions.cpp
@@ -362,24 +362,20 @@ ArrayConcatDense(JSContext *cx, HandleOb
     if (!js::array_concat(cx, 1, argv))
         return NULL;
     return &argv[0].toObject();
 }
 
 bool
 CharCodeAt(JSContext *cx, HandleString str, int32_t index, uint32_t *code)
 {
-    JS_ASSERT(index >= 0 &&
-              static_cast<uint32_t>(index) < str->length());
-
-    const jschar *chars = str->getChars(cx);
-    if (!chars)
+    jschar c;
+    if (!str->getChar(cx, index, &c))
         return false;
-
-    *code = chars[index];
+    *code = c;
     return true;
 }
 
 JSFlatString *
 StringFromCharCode(JSContext *cx, int32_t code)
 {
     jschar c = jschar(code);
 
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/bug851064.js
@@ -0,0 +1,13 @@
+var base = "azertyuiopqsdfghjklmwxcvbn";
+function createRopedString() {
+  var test = "";
+  for (var i=0; i<2; i++) {
+    test += base;
+  }
+  return test;
+}
+
+assertEq(createRopedString().substr(0,10), base.substr(0,10));
+assertEq(createRopedString().substr(0,26), base.substr(0,26));
+assertEq(createRopedString().substr(26,10), base.substr(0,10));
+assertEq(createRopedString().substr(24,10), base.substr(24,2) + base.substr(0,8));
--- a/js/src/jsstr.cpp
+++ b/js/src/jsstr.cpp
@@ -565,16 +565,69 @@ ValueToIntegerRange(JSContext *cx, const
             *out = INT32_MIN;
         else
             *out = int32_t(d);
     }
 
     return true;
 }
 
+static JSString *
+DoSubstr(JSContext *cx, JSString *str, size_t begin, size_t len)
+{
+    /*
+     * Optimization for one level deep ropes.
+     * This is common for the following pattern:
+     *
+     * while() {
+     *   text = text.substr(0, x) + "bla" + text.substr(x)
+     *   test.charCodeAt(x + 1)
+     * }
+     */
+    if (str->isRope()) {
+        JSRope *rope = &str->asRope();
+
+        /* Substring is totally in leftChild of rope. */
+        if (begin + len <= rope->leftChild()->length()) {
+            str = rope->leftChild();
+            return js_NewDependentString(cx, str, begin, len);
+        }
+
+        /* Substring is totally in rightChild of rope. */
+        if (begin >= rope->leftChild()->length()) {
+            str = rope->rightChild();
+            begin -= rope->leftChild()->length();
+            return js_NewDependentString(cx, str, begin, len);
+        }
+
+        /*
+         * Requested substring is partly in the left and partly in right child.
+         * Create a rope of substrings for both childs.
+         */
+        JS_ASSERT (begin < rope->leftChild()->length() &&
+                   begin + len > rope->leftChild()->length());
+
+        size_t lhsLength = rope->leftChild()->length() - begin;
+        size_t rhsLength = begin + len - rope->leftChild()->length();
+
+        RootedString lhs(cx, js_NewDependentString(cx, rope->leftChild(),
+                                                   begin, lhsLength));
+        if (!lhs)
+            return NULL;
+
+        RootedString rhs(cx, js_NewDependentString(cx, rope->rightChild(), 0, rhsLength));
+        if (!rhs)
+            return NULL;
+
+        return JSRope::new_<CanGC>(cx, lhs, rhs, len);
+    }
+
+    return js_NewDependentString(cx, str, begin, len);
+}
+
 static JSBool
 str_substring(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
 
     JSString *str = ThisToStringForStringProto(cx, args);
     if (!str)
         return false;
@@ -615,17 +668,17 @@ str_substring(JSContext *cx, unsigned ar
                 if (end < begin) {
                     int32_t tmp = begin;
                     begin = end;
                     end = tmp;
                 }
             }
         }
 
-        str = js_NewDependentString(cx, str, size_t(begin), size_t(end - begin));
+        str = DoSubstr(cx, str, size_t(begin), size_t(end - begin));
         if (!str)
             return false;
     }
 
     args.rval().setString(str);
     return true;
 }
 
@@ -854,22 +907,20 @@ js_str_charCodeAt(JSContext *cx, unsigne
         if (args.length() > 0 && !ToInteger(cx, args[0], &d))
             return false;
 
         if (d < 0 || str->length() <= d)
             goto out_of_range;
         i = size_t(d);
     }
 
-    const jschar *chars;
-    chars = str->getChars(cx);
-    if (!chars)
+    jschar c;
+    if (!str->getChar(cx, i, &c))
         return false;
-
-    args.rval().setInt32(chars[i]);
+    args.rval().setInt32(c);
     return true;
 
 out_of_range:
     args.rval().setDouble(js_NaN);
     return true;
 }
 
 /*
@@ -3104,17 +3155,17 @@ str_substr(JSContext *cx, unsigned argc,
             }
 
             if (uint32_t(length) < uint32_t(begin + len))
                 len = length - begin;
         } else {
             len = length - begin;
         }
 
-        str = js_NewDependentString(cx, str, size_t(begin), size_t(len));
+        str = DoSubstr(cx, str, size_t(begin), size_t(len));
         if (!str)
             return false;
     }
 
     args.rval().setString(str);
     return true;
 }
 
--- a/js/src/vm/String-inl.h
+++ b/js/src/vm/String-inl.h
@@ -399,20 +399,20 @@ js::StaticStrings::getInt(int32_t i)
     JS_ASSERT(hasInt(i));
     return getUint(uint32_t(i));
 }
 
 inline JSLinearString *
 js::StaticStrings::getUnitStringForElement(JSContext *cx, JSString *str, size_t index)
 {
     JS_ASSERT(index < str->length());
-    const jschar *chars = str->getChars(cx);
-    if (!chars)
+
+    jschar c;
+    if (!str->getChar(cx, index, &c))
         return NULL;
-    jschar c = chars[index];
     if (c < UNIT_STATIC_LIMIT)
         return getUnit(c);
     return js_NewDependentString(cx, str, index, 1);
 }
 
 inline JSAtom *
 js::StaticStrings::getLength2(jschar c1, jschar c2)
 {
--- a/js/src/vm/String.cpp
+++ b/js/src/vm/String.cpp
@@ -199,25 +199,46 @@ JSRope::flattenInternal(JSContext *maybe
      */
     const size_t wholeLength = length();
     size_t wholeCapacity;
     jschar *wholeChars;
     JSString *str = this;
     jschar *pos;
     JSRuntime *rt = runtime();
 
-    if (this->leftChild()->isExtensible()) {
-        JSExtensibleString &left = this->leftChild()->asExtensible();
+    /* Find the left most string, containing the first string. */
+    JSRope *leftMostRope = this;
+    while (leftMostRope->leftChild()->isRope())
+        leftMostRope = &leftMostRope->leftChild()->asRope();
+
+    if (leftMostRope->leftChild()->isExtensible()) {
+        JSExtensibleString &left = leftMostRope->leftChild()->asExtensible();
         size_t capacity = left.capacity();
         if (capacity >= wholeLength) {
+            /*
+             * Simulate a left-most traversal from the root to leftMost->leftChild()
+             * via first_visit_node
+             */
+            while (str != leftMostRope) {
+                JS_ASSERT(str->isRope());
+                if (b == WithIncrementalBarrier) {
+                    JSString::writeBarrierPre(str->d.u1.left);
+                    JSString::writeBarrierPre(str->d.s.u2.right);
+                }
+                JSString *child = str->d.u1.left;
+                str->d.u1.chars = left.chars();
+                child->d.s.u3.parent = str;
+                child->d.lengthAndFlags = 0x200;
+                str = child;
+            }
             if (b == WithIncrementalBarrier) {
-                JSString::writeBarrierPre(d.u1.left);
-                JSString::writeBarrierPre(d.s.u2.right);
+                JSString::writeBarrierPre(str->d.u1.left);
+                JSString::writeBarrierPre(str->d.s.u2.right);
             }
-
+            str->d.u1.chars = left.chars();
             wholeCapacity = capacity;
             wholeChars = const_cast<jschar *>(left.chars());
             size_t bits = left.d.lengthAndFlags;
             pos = wholeChars + (bits >> LENGTH_SHIFT);
             JS_STATIC_ASSERT(!(EXTENSIBLE_FLAGS & DEPENDENT_FLAGS));
             left.d.lengthAndFlags = bits ^ (EXTENSIBLE_FLAGS | DEPENDENT_FLAGS);
             left.d.s.u2.base = (JSLinearString *)this;  /* will be true on exit */
             StringWriteBarrierPostRemove(rt, &left.d.u1.left);
--- a/js/src/vm/String.h
+++ b/js/src/vm/String.h
@@ -264,16 +264,17 @@ class JSString : public js::gc::Cell
 
     /*
      * All strings have a fallible operation to get an array of chars.
      * getCharsZ additionally ensures the array is null terminated.
      */
 
     inline const jschar *getChars(JSContext *cx);
     inline const jschar *getCharsZ(JSContext *cx);
+    inline bool getChar(JSContext *cx, size_t index, jschar *code);
 
     /* Fallible conversions to more-derived string types. */
 
     inline JSLinearString *ensureLinear(JSContext *cx);
     inline JSFlatString *ensureFlat(JSContext *cx);
     inline JSStableString *ensureStable(JSContext *cx);
 
     static bool ensureLinear(JSContext *cx, JSString *str) {
@@ -886,16 +887,50 @@ class AutoNameVector : public AutoVector
 JS_ALWAYS_INLINE const jschar *
 JSString::getChars(JSContext *cx)
 {
     if (JSLinearString *str = ensureLinear(cx))
         return str->chars();
     return NULL;
 }
 
+JS_ALWAYS_INLINE bool
+JSString::getChar(JSContext *cx, size_t index, jschar *code)
+{
+    JS_ASSERT(index < length());
+
+    /*
+     * Optimization for one level deep ropes.
+     * This is common for the following pattern:
+     *
+     * while() {
+     *   text = text.substr(0, x) + "bla" + text.substr(x)
+     *   test.charCodeAt(x + 1)
+     * }
+     */
+    const jschar *chars;
+    if (isRope()) {
+        JSRope *rope = &asRope();
+        if (uint32_t(index) < rope->leftChild()->length()) {
+            chars = rope->leftChild()->getChars(cx);
+        } else {
+            chars = rope->rightChild()->getChars(cx);
+            index -= rope->leftChild()->length();
+        }
+    } else {
+        chars = getChars(cx);
+    }
+
+    if (!chars)
+        return false;
+
+    *code = chars[index];
+    return true;
+}
+
 JS_ALWAYS_INLINE const jschar *
 JSString::getCharsZ(JSContext *cx)
 {
     if (JSFlatString *str = ensureFlat(cx))
         return str->chars();
     return NULL;
 }