Bug 609440, part 2 - do lazy allocation, dag-ify ropes (assume no oom) (r=njn)
authorLuke Wagner <lw@mozilla.com>
Tue, 30 Nov 2010 18:41:32 -0800
changeset 59888 114a969caad417c10651384adba2184efd7572c0
parent 59887 9ca89fc6beef8174a9c10a2e84f179201af29383
child 59889 cc6d97b432cc1911da7c8f5d5b3ed13322fefc4d
push id17820
push usercleary@mozilla.com
push dateTue, 04 Jan 2011 21:40:57 +0000
treeherdermozilla-central@969691cfe40e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnjn
bugs609440
milestone2.0b8pre
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 609440, part 2 - do lazy allocation, dag-ify ropes (assume no oom) (r=njn)
js/src/jsatom.cpp
js/src/jsgcinlines.h
js/src/jsstr.cpp
js/src/jsstr.h
js/src/jsstrinlines.h
js/src/jstracer.cpp
js/src/jstypes.h
js/src/jsvector.h
js/src/methodjit/Compiler.cpp
js/src/methodjit/MonoIC.cpp
js/src/methodjit/PolyIC.cpp
js/src/tracejit/Writer.cpp
js/src/tracejit/Writer.h
--- a/js/src/jsatom.cpp
+++ b/js/src/jsatom.cpp
@@ -509,17 +509,17 @@ js_AtomizeString(JSContext *cx, JSString
                 jschar *chars = str->chars();
                 if (flags & ATOM_NOCOPY) {
                     key = js_NewString(cx, chars, length);
                     if (!key)
                         return NULL;
 
                     /* Finish handing off chars to the GC'ed key string. */
                     JS_ASSERT(flags & ATOM_TMPSTR);
-                    str->mChars = NULL;
+                    str->u.chars = NULL;
                 } else {
                     key = js_NewStringCopyN(cx, chars, length);
                     if (!key)
                         return NULL;
                 }
             } else {
                 JS_ASSERT(str->isDependent());
                 if (!str->undepend(cx))
--- a/js/src/jsgcinlines.h
+++ b/js/src/jsgcinlines.h
@@ -267,18 +267,16 @@ MarkChildren(JSTracer *trc, JSObject *ob
 }
 
 static inline void
 MarkChildren(JSTracer *trc, JSString *str)
 {
     if (str->isDependent())
         MarkString(trc, str->dependentBase(), "base");
     else if (str->isRope()) {
-        if (str->isInteriorNode())
-            MarkString(trc, str->interiorNodeParent(), "parent");
         MarkString(trc, str->ropeLeft(), "left child");
         MarkString(trc, str->ropeRight(), "right child");
     }
 }
 
 #ifdef JS_HAS_XML_SUPPORT
 static inline void
 MarkChildren(JSTracer *trc, JSXML *xml)
@@ -345,44 +343,118 @@ TypedMarker(JSTracer *trc, JSFunction *t
 }
 
 static JS_ALWAYS_INLINE void
 TypedMarker(JSTracer *trc, JSShortString *thing)
 {
     thing->asCell()->markIfUnmarked();
 }
 
+}  /* namespace gc */
+
+namespace detail {
+
+static JS_ALWAYS_INLINE JSString *
+Tag(JSString *str)
+{
+    JS_ASSERT(!(size_t(str) & 1));
+    return (JSString *)(size_t(str) | 1);
+}
+
+static JS_ALWAYS_INLINE bool
+Tagged(JSString *str)
+{
+    return (size_t(str) & 1) != 0;
+}
+
+static JS_ALWAYS_INLINE JSString *
+Untag(JSString *str)
+{
+    JS_ASSERT((size_t(str) & 1) == 1);
+    return (JSString *)(size_t(str) & ~size_t(1));
+}
+
+static JS_ALWAYS_INLINE void
+NonRopeTypedMarker(JSString *str)
+{
+    JS_ASSERT(!str->isRope());
+    if (JSString::isStatic(str) ||
+        !str->asCell()->markIfUnmarked() ||
+        !str->isDependent()) {
+        return;
+    }
+    JSString *base = str->dependentBase();
+    if (JSString::isStatic(base))
+        return;
+    base->asCell()->markIfUnmarked();
+}
+
+}  /* namespace detail */
+
+namespace gc {
+
 static JS_ALWAYS_INLINE void
 TypedMarker(JSTracer *trc, JSString *str)
 {
+    using namespace detail;
+
+    if (!str->isRope()) {
+        NonRopeTypedMarker(str);
+        return;
+    }
+
     /*
-     * When marking any node of a rope, mark the entire rope. This means if
-     * a given rope node is already marked, we are done.
+     * This function must not fail, so a simple stack-based traversal must not
+     * be used (since it may oom if the stack grows large). Instead, strings
+     * are temporarily mutated to embed parent pointers as they are traversed.
+     * This algorithm is homomorphic to JSString::flatten.
      */
-    JSRopeNodeIterator iter;
-    if (str->isRope()) {
-        if (str->asCell()->isMarked())
-            return;
-        str = iter.init(str);
-        goto not_static;
+    JSString *parent = NULL;
+    first_visit_node: {
+        if (!str->asCell()->markIfUnmarked())
+            goto finish_node;
+        JSString *left = str->ropeLeft();
+        if (left->isRope()) {
+            JS_ASSERT(!Tagged(str->u.left) && !Tagged(str->s.right));
+            str->u.left = Tag(parent);
+            parent = str;
+            str = left;
+            goto first_visit_node;
+        }
+        NonRopeTypedMarker(left);
     }
-    do {
-        for (;;) {
-            if (JSString::isStatic(str))
-                break;
-          not_static:
-            JS_ASSERT(JSTRACE_STRING == GetFinalizableTraceKind(str->asCell()->arena()->header()->thingKind));
-            if (!str->asCell()->markIfUnmarked())
-                break;
-            if (!str->isDependent())
-                break;
-            str = str->dependentBase();
+    visit_right_child: {
+        JSString *right = str->ropeRight();
+        if (right->isRope()) {
+            JS_ASSERT(!Tagged(str->u.left) && !Tagged(str->s.right));
+            str->s.right = Tag(parent);
+            parent = str;
+            str = right;
+            goto first_visit_node;
         }
-        str = iter.next();
-    } while (str);
+        NonRopeTypedMarker(right);
+    }
+    finish_node: {
+        if (!parent)
+            return;
+        if (Tagged(parent->u.left)) {
+            JS_ASSERT(!Tagged(parent->s.right));
+            JSString *nextParent = Untag(parent->u.left);
+            parent->u.left = str;
+            str = parent;
+            parent = nextParent;
+            goto visit_right_child;
+        }
+        JS_ASSERT(Tagged(parent->s.right));
+        JSString *nextParent = Untag(parent->s.right);
+        parent->s.right = str;
+        str = parent;
+        parent = nextParent;
+        goto finish_node;
+    }
 }
 
 static inline void
 MarkAtomRange(JSTracer *trc, size_t len, JSAtom **vec, const char *name)
 {
     for (uint32 i = 0; i < len; i++) {
         if (JSAtom *atom = vec[i]) {
             JS_SET_TRACING_INDEX(trc, name, i);
--- a/js/src/jsstr.cpp
+++ b/js/src/jsstr.cpp
@@ -92,100 +92,122 @@ JS_STATIC_ASSERT(JSString::MAX_LENGTH <=
 const jschar *
 js_GetStringChars(JSContext *cx, JSString *str)
 {
     if (!js_MakeStringImmutable(cx, str))
         return NULL;
     return str->flatChars();
 }
 
+static JS_ALWAYS_INLINE size_t
+RopeCapacityFor(size_t length)
+{
+    static const size_t ROPE_DOUBLING_MAX = 1024 * 1024;
+
+    /*
+     * Grow by 12.5% if the buffer is very large. Otherwise, round up to the
+     * next power of 2. This is similar to what we do with arrays; see
+     * JSObject::ensureDenseArrayElements.
+     */
+    if (length > ROPE_DOUBLING_MAX)
+        return length + (length / 8);
+    return RoundUpPow2(length);
+}
+
 void
 JSString::flatten()
 {
     JS_ASSERT(isRope());
 
     /*
-     * This can be called from any string in the rope, so first traverse to the
-     * top node.
-     */
-    JSString *topNode = this;
-    while (topNode->isInteriorNode())
-        topNode = topNode->interiorNodeParent();
-
-    const size_t length = topNode->length();
-    const size_t capacity = topNode->topNodeCapacity();
-    jschar *const chars = (jschar *) topNode->topNodeBuffer();
-
-    /*
-     * To allow a homogeneous tree traversal, transform the top node into an
-     * internal node with null parent (which will be the stop condition).
-     */
-    topNode->e.mParent = NULL;
-#ifdef DEBUG
-    topNode->mLengthAndFlags = JSString::INTERIOR_NODE;
-#endif
-
-    /*
-     * Perform a depth-first tree traversal, splatting each node's characters
-     * into a contiguous buffer. Visit each node three times:
-     *  - the first time, record the position in the linear buffer, and recurse
-     *    into the left child.
-     *  - the second time, recurse into the right child.
-     *  - the third time, transform the node into a dependent string.
+     * Perform a depth-first dag traversal, splatting each node's characters
+     * into a contiguous buffer. Visit each rope node three times:
+     *  1. record position in the buffer and recurse into left child;
+     *  2. recurse into the right child;
+     *  3. transform the node into a dependent string.
      * To avoid maintaining a stack, tree nodes are mutated to indicate how
-     * many times they have been visited.
+     * many times they have been visited. Since ropes can be dags, a node may
+     * be encountered multiple times during traversal. However, step 3 above
+     * leaves a valid dependent string, so everythings works out.  This
+     * algorithm is homomorphic to TypedMarker(JSTracer *, JSString *).
+     *
+     * While ropes avoid all sorts of quadratic cases with string
+     * concatenation, they can't help when ropes are immediately flattened.
+     * One idiomatic case that we'd like to keep linear (and has traditionally
+     * been linear in SM and other JS engines) is:
+     *
+     *   while (...) {
+     *     s += ...
+     *     s.flatten
+     *   }
+     *
+     * To do this, when the buffer for a to-be-flattened rope is allocated, the
+     * allocation size is rounded up. Then, if the resulting flat string is the
+     * left-hand side of a new rope that gets flattened and there is enough
+     * capacity, the rope is flattened into the same buffer, thereby avoiding
+     * copying the left-hand side. Clearing the 'extensible' bit turns off this
+     * optimization. This is necessary, e.g., when the JSAPI hands out the raw
+     * null-terminated char array of a flat string.
      */
-    JSString *str = topNode;
-    jschar *pos = chars;
-    while (true) {
-        /* Visiting the node for the first time. */
-        JS_ASSERT(str->isInteriorNode());
-        {
-            JSString *next = str->mLeft;
-            str->mChars = pos;  /* N.B. aliases mLeft */
-            if (next->isInteriorNode()) {
-                str->mLengthAndFlags = 0x200;  /* N.B. flags invalidated */
-                str = next;
-                continue;  /* Visit node for the first time. */
-            } else {
-                size_t len = next->length();
-                PodCopy(pos, next->mChars, len);
-                pos += len;
-                goto visit_right_child;
-            }
+    const size_t wholeLength = length();
+    size_t wholeCapacity;
+    jschar *wholeChars;
+    JSString *str = this;
+    jschar *pos;
+
+    if (u.left->isExtensible() && u.left->s.capacity >= wholeLength) {
+        wholeCapacity = u.left->s.capacity;
+        wholeChars = u.left->u.chars;
+        pos = wholeChars + u.left->length();
+        u.left->finishTraversalConversion(this, wholeChars, pos);
+        goto visit_right_child;
+    }
+
+    wholeCapacity = RopeCapacityFor(wholeLength);
+    wholeChars = (jschar *)js_malloc((wholeCapacity + 1) * sizeof(jschar));
+    pos = wholeChars;
+    first_visit_node: {
+        JSString *left = str->u.left;           /* Read before clobbered. */
+        str->u.chars = pos;
+        if (left->isRope()) {
+            left->s.parent = str;               /* Return to this when 'left' done, */
+            left->lengthAndFlags = 0x200;       /* but goto visit_right_child. */
+            str = left;
+            goto first_visit_node;
         }
-
-      revisit_parent:
-        if (str->mLengthAndFlags == 0x200) {
-          visit_right_child:
-            JSString *next = str->e.mRight;
-            if (next->isInteriorNode()) {
-                str->mLengthAndFlags = 0x300;
-                str = next;
-                continue;  /* Visit 'str' for the first time. */
-            } else {
-                size_t len = next->length();
-                PodCopy(pos, next->mChars, len);
-                pos += len;
-                goto finish_node;
-            }
-        } else {
-            JS_ASSERT(str->mLengthAndFlags == 0x300);
-          finish_node:
-            JSString *next = str->e.mParent;
-            str->finishTraversalConversion(topNode, pos);
-            if (!next) {
-                JS_ASSERT(pos == chars + length);
-                *pos = 0;
-                topNode->initFlatExtensible(chars, length, capacity);
-                return;
-            }
-            str = next;
-            goto revisit_parent;  /* Visit 'str' for the second or third time */
+        size_t len = left->length();
+        PodCopy(pos, left->u.chars, len);
+        pos += len;
+    }
+    visit_right_child: {
+        JSString *right = str->s.right;
+        if (right->isRope()) {
+            right->s.parent = str;              /* Return to this node when 'right' done, */
+            right->lengthAndFlags = 0x300;      /* but goto finish_node. */
+            str = right;
+            goto first_visit_node;
         }
+        size_t len = right->length();
+        PodCopy(pos, right->u.chars, len);
+        pos += len;
+    }
+    finish_node: {
+        if (str == this) {
+            JS_ASSERT(pos == wholeChars + wholeLength);
+            *pos = '\0';
+            initFlatExtensible(wholeChars, wholeLength, wholeCapacity);
+            return;
+        }
+        size_t progress = str->lengthAndFlags;  /* Read before clobbered. */
+        JSString *parent = str->s.parent;
+        str->finishTraversalConversion(this, wholeChars, pos);
+        str = parent;
+        if (progress == 0x200)
+            goto visit_right_child;
+        goto finish_node;
     }
 }
 
 JS_STATIC_ASSERT(JSExternalString::TYPE_LIMIT == 8);
 JSStringFinalizeOp JSExternalString::str_finalizers[JSExternalString::TYPE_LIMIT] = {
     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL
 };
 
@@ -196,223 +218,57 @@ js_Flatten(JSString* str)
 {
     str->flatten();
     return 0;
 }
 JS_DEFINE_CALLINFO_1(extern, INT32, js_Flatten, STRING, 0, nanojit::ACCSET_STORE_ANY)
 
 #endif /* !JS_TRACER */
 
-static JS_ALWAYS_INLINE size_t
-RopeAllocSize(const size_t length, size_t *capacity)
-{
-    static const size_t ROPE_DOUBLING_MAX = 1024 * 1024;
-
-    size_t size;
-    size_t minCap = (length + 1) * sizeof(jschar);
-
-    /*
-     * Grow by 12.5% if the buffer is very large. Otherwise, round up to the
-     * next power of 2. This is similar to what we do with arrays; see
-     * JSObject::ensureDenseArrayElements.
-     */
-    if (length > ROPE_DOUBLING_MAX)
-        size = minCap + (minCap / 8);
-    else
-        size = RoundUpPow2(minCap);
-    *capacity = (size / sizeof(jschar)) - 1;
-    JS_ASSERT(size >= sizeof(JSRopeBufferInfo));
-    return size;
-}
-
-static JS_ALWAYS_INLINE JSRopeBufferInfo *
-ObtainRopeBuffer(JSContext *cx, bool usingLeft, bool usingRight,
-                 JSRopeBufferInfo *sourceBuffer, size_t length,
-                 JSString *left, JSString *right)
-{
-    JSRopeBufferInfo *buf;
-    size_t capacity;
-
-    /*
-     * We need to survive a GC upon failure and in case creating a new
-     * string header triggers a GC, but we've broken the invariant that
-     * rope top nodes always point to freeable JSRopeBufferInfo
-     * objects, so make them point to NULL.
-     */
-    if (usingLeft)
-        left->nullifyTopNodeBuffer();
-    if (usingRight)
-        right->nullifyTopNodeBuffer();
-
-    /*
-     * Try to reuse sourceBuffer. If it's not suitable, free it and create a
-     * suitable buffer.
-     */
-    if (length <= sourceBuffer->capacity) {
-        buf = sourceBuffer;
-    } else {
-        size_t allocSize = RopeAllocSize(length, &capacity);
-        cx->free(sourceBuffer);
-        buf = (JSRopeBufferInfo *) cx->malloc(allocSize);
-        if (!buf)
-            return NULL;
-        buf->capacity = capacity;
-    }
-    return buf;
-}
-
-static JS_ALWAYS_INLINE JSString *
-FinishConcat(JSContext *cx, bool usingLeft, bool usingRight,
-             JSString *left, JSString *right, size_t length,
-             JSRopeBufferInfo *buf)
-{
-    JSString *res = js_NewGCString(cx);
-    if (!res) {
-        cx->free(buf);
-        return NULL;
-    }
-    res->initTopNode(left, right, length, buf);
-    if (usingLeft)
-        left->convertToInteriorNode(res);
-    if (usingRight)
-        right->convertToInteriorNode(res);
-    return res;
-}
-
 JSString * JS_FASTCALL
 js_ConcatStrings(JSContext *cx, JSString *left, JSString *right)
 {
-    size_t length, leftLen, rightLen;
-    bool leftRopeTop, rightRopeTop;
-
-    leftLen = left->length();
+    size_t leftLen = left->length();
     if (leftLen == 0)
         return right;
-    rightLen = right->length();
+
+    size_t rightLen = right->length();
     if (rightLen == 0)
         return left;
 
-    length = leftLen + rightLen;
-
-    if (JSShortString::fitsIntoShortString(length)) {
+    size_t wholeLength = leftLen + rightLen;
+
+    if (JSShortString::fitsIntoShortString(wholeLength)) {
         JSShortString *shortStr = js_NewGCShortString(cx);
         if (!shortStr)
             return NULL;
 
-        jschar *buf = shortStr->init(length);
+        jschar *buf = shortStr->init(wholeLength);
         js_short_strncpy(buf, left->chars(), leftLen);
         js_short_strncpy(buf + leftLen, right->chars(), rightLen);
-        buf[length] = 0;
+        buf[wholeLength] = 0;
         return shortStr->header();
     }
 
-    /*
-     * We need to enforce a tree structure in ropes: every node needs to have a
-     * unique parent. So, we can't have the left or right child be in the middle
-     * of a rope tree. One potential solution is to traverse the subtree for the
-     * argument string and create a new flat string, but that would add
-     * complexity and is a rare case, so we simply flatten the entire rope that
-     * contains it. The case where left and right are part of the same rope is
-     * handled implicitly.
-     */
-    if (left->isInteriorNode())
-        left->flatten();
-    if (right->isInteriorNode())
-        right->flatten();
-
-    if (left->isExtensible() && !right->isRope() &&
-        left->flatCapacity() >= length) {
-        JS_ASSERT(left->isFlat());
-
-        /*
-         * If left has enough unused space at the end of its buffer that we can
-         * fit the entire new string there, just write there.
-         */
-        jschar *chars = left->chars();
-        js_strncpy(chars + leftLen, right->chars(), rightLen);
-        chars[length] = 0;
-        JSString *res = js_NewString(cx, chars, length);
-        if (!res)
-            return NULL;
-        res->initFlatExtensible(chars, length, left->flatCapacity());
-        left->initDependent(res, res->flatChars(), leftLen);
-        return res;
-    }
-
-    if (length > JSString::MAX_LENGTH) {
+    if (wholeLength > JSString::MAX_LENGTH) {
         if (JS_ON_TRACE(cx)) {
             if (!CanLeaveTrace(cx))
                 return NULL;
             LeaveTrace(cx);
         }
         js_ReportAllocationOverflow(cx);
         return NULL;
     }
 
-    leftRopeTop = left->isTopNode();
-    rightRopeTop = right->isTopNode();
-
-    /*
-     * To make traversal more manageable, we enforce that, unless the children
-     * are leaves, the two children of a rope node must be distinct.
-     */
-    if (left == right && leftRopeTop) {
-        left->flatten();
-        leftRopeTop = false;
-        rightRopeTop = false;
-        JS_ASSERT(leftLen == left->length());
-        JS_ASSERT(rightLen == right->length());
-        JS_ASSERT(!left->isTopNode());
-        JS_ASSERT(!right->isTopNode());
-    }
-
-    /*
-     * There are 4 cases, based on whether on whether the left or right is a
-     * rope or non-rope string.
-     */
-    JSRopeBufferInfo *buf = NULL;
-
-    if (leftRopeTop) {
-        /* Left child is a rope. */
-        JSRopeBufferInfo *leftBuf = left->topNodeBuffer();
-
-        /* If both children are ropes, steal the larger buffer. */
-        if (JS_UNLIKELY(rightRopeTop)) {
-            JSRopeBufferInfo *rightBuf = right->topNodeBuffer();
-
-            /* Put the larger buffer into 'leftBuf'. */
-            if (leftBuf->capacity >= rightBuf->capacity) {
-                cx->free(rightBuf);
-            } else {
-                cx->free(leftBuf);
-                leftBuf = rightBuf;
-            }
-        }
-
-        buf = ObtainRopeBuffer(cx, true, rightRopeTop, leftBuf, length, left, right);
-        if (!buf)
-            return NULL;
-    } else if (JS_UNLIKELY(rightRopeTop)) {
-        /* Right child is a rope: steal its buffer if big enough. */
-        JSRopeBufferInfo *rightBuf = right->topNodeBuffer();
-
-        buf = ObtainRopeBuffer(cx, false, true, rightBuf, length, left, right);
-        if (!buf)
-            return NULL;
-    } else {
-        /* Neither child is a rope: need to make a new buffer. */
-        size_t capacity;
-        size_t allocSize = RopeAllocSize(length, &capacity);
-        buf = (JSRopeBufferInfo *) cx->malloc(allocSize);
-        if (!buf)
-            return NULL;
-        buf->capacity = capacity;
-    }
-
-    return FinishConcat(cx, leftRopeTop, rightRopeTop, left, right, length, buf);
+    JSString *newRoot = js_NewGCString(cx);
+    if (!newRoot)
+        return NULL;
+
+    newRoot->initRopeNode(left, right, wholeLength);
+    return newRoot;
 }
 
 const jschar *
 JSString::undepend(JSContext *cx)
 {
     size_t n, size;
     jschar *s;
 
@@ -1354,60 +1210,79 @@ StringMatch(const jschar *text, jsuint t
            patlen > 128 ? UnrolledMatch<MemCmp>(text, textlen, pat, patlen)
                         :
 #endif
                           UnrolledMatch<ManualCmp>(text, textlen, pat, patlen);
 }
 
 static const size_t sRopeMatchThresholdRatioLog2 = 5;
 
-static jsint
-RopeMatch(JSString *textstr, const jschar *pat, jsuint patlen)
+/*
+ * RopeMatch takes the text to search, the patern to search for in the text.
+ * RopeMatch returns false on OOM and otherwise returns the match index through
+ * the 'match' outparam (-1 for not found).
+ */
+static bool
+RopeMatch(JSContext *cx, JSString *textstr, const jschar *pat, jsuint patlen, jsint *match)
 {
-    JS_ASSERT(textstr->isTopNode());
-
-    if (patlen == 0)
-        return 0;
-    if (textstr->length() < patlen)
-        return -1;
+    JS_ASSERT(textstr->isRope());
+
+    if (patlen == 0) {
+        *match = 0;
+        return true;
+    }
+    if (textstr->length() < patlen) {
+        *match = -1;
+        return true;
+    }
 
     /*
      * List of leaf nodes in the rope. If we run out of memory when trying to
      * append to this list, we can still fall back to StringMatch, so use the
      * system allocator so we don't report OOM in that case.
      */
     Vector<JSString *, 16, SystemAllocPolicy> strs;
 
     /*
      * We don't want to do rope matching if there is a poor node-to-char ratio,
      * since this means spending a lot of time in the match loop below. We also
      * need to build the list of leaf nodes. Do both here: iterate over the
      * nodes so long as there are not too many.
      */
-    size_t textstrlen = textstr->length();
-    size_t threshold = textstrlen >> sRopeMatchThresholdRatioLog2;
-    JSRopeLeafIterator iter;
-    for (JSString *str = iter.init(textstr); str; str = iter.next()) {
-        if (threshold-- == 0 || !strs.append(str))
-            return StringMatch(textstr->chars(), textstrlen, pat, patlen);
+    {
+        size_t textstrlen = textstr->length();
+        size_t threshold = textstrlen >> sRopeMatchThresholdRatioLog2;
+        StringSegmentRange r(cx);
+        if (!r.init(textstr))
+            return false;
+        while (!r.empty()) {
+            if (threshold-- == 0 || !strs.append(r.front())) {
+                *match = StringMatch(textstr->chars(), textstrlen, pat, patlen);
+                return true;
+            }
+            if (!r.popFront())
+                return false;
+        }
     }
 
     /* Absolute offset from the beginning of the logical string textstr. */
     jsint pos = 0;
 
     // TODO: consider branching to a simple loop if patlen == 1
 
     for (JSString **outerp = strs.begin(); outerp != strs.end(); ++outerp) {
         /* First try to match without spanning two nodes. */
         const jschar *chars;
         size_t len;
         (*outerp)->getCharsAndLength(chars, len);
         jsint matchResult = StringMatch(chars, len, pat, patlen);
-        if (matchResult != -1)
-            return pos + matchResult;
+        if (matchResult != -1) {
+            *match = pos + matchResult;
+            return true;
+        }
 
         /* Test the overlap. */
         JSString **innerp = outerp;
 
         /*
          * Start searching at the first place where StringMatch wouldn't have
          * found the match.
          */
@@ -1417,34 +1292,38 @@ RopeMatch(JSString *textstr, const jscha
         const jschar *const p1 = pat + 1;
         const jschar *const patend = pat + patlen;
         for (const jschar *t = text; t != textend; ) {
             if (*t++ != p0)
                 continue;
             const jschar *ttend = textend;
             for (const jschar *pp = p1, *tt = t; pp != patend; ++pp, ++tt) {
                 while (tt == ttend) {
-                    if (++innerp == strs.end())
-                        return -1;
+                    if (++innerp == strs.end()) {
+                        *match = -1;
+                        return true;
+                    }
                     (*innerp)->getCharsAndEnd(tt, ttend);
                 }
                 if (*pp != *tt)
                     goto break_continue;
             }
 
             /* Matched! */
-            return pos + (t - chars) - 1;  /* -1 because of *t++ above */
+            *match = pos + (t - chars) - 1;  /* -1 because of *t++ above */
+            return true;
 
           break_continue:;
         }
 
         pos += len;
     }
 
-    return -1;
+    *match = -1;
+    return true;
 }
 
 static JSBool
 str_indexOf(JSContext *cx, uintN argc, Value *vp)
 {
 
     JSString *str;
     NORMALIZE_THIS(cx, vp, str);
@@ -1729,19 +1608,22 @@ class RegExpGuard
     }
 
     /*
      * Attempt to match |patstr| to |textstr|. A flags argument, metachars in the
      * pattern string, or a lengthy pattern string can thwart this process.
      *
      * @param checkMetaChars    Look for regexp metachars in the pattern string.
      * @return                  Whether flat matching could be used.
+     *
+     * N.B. tryFlatMatch returns NULL on OOM, so the caller must check cx->throwing.
      */
     const FlatMatch *
-    tryFlatMatch(JSString *textstr, uintN optarg, uintN argc, bool checkMetaChars = true)
+    tryFlatMatch(JSContext *cx, JSString *textstr, uintN optarg, uintN argc,
+                 bool checkMetaChars = true)
     {
         if (rep.re_)
             return NULL;
 
         fm.patstr->getCharsAndLength(fm.pat, fm.patlen);
 
         if (optarg < argc)
             return NULL;
@@ -1750,18 +1632,19 @@ class RegExpGuard
             (fm.patlen > MAX_FLAT_PAT_LEN || RegExp::hasMetaChars(fm.pat, fm.patlen))) {
             return NULL;
         }
 
         /*
          * textstr could be a rope, so we want to avoid flattening it for as
          * long as possible.
          */
-        if (textstr->isTopNode()) {
-            fm.match_ = RopeMatch(textstr, fm.pat, fm.patlen);
+        if (textstr->isRope()) {
+            if (!RopeMatch(cx, textstr, fm.pat, fm.patlen, &fm.match_))
+                return NULL;
         } else {
             const jschar *text;
             size_t textlen;
             textstr->getCharsAndLength(text, textlen);
             fm.match_ = StringMatch(text, textlen, fm.pat, fm.patlen);
         }
         return &fm;
     }
@@ -1913,18 +1796,20 @@ static JSBool
 str_match(JSContext *cx, uintN argc, Value *vp)
 {
     JSString *str;
     NORMALIZE_THIS(cx, vp, str);
 
     RegExpGuard g(cx);
     if (!g.init(argc, vp))
         return false;
-    if (const FlatMatch *fm = g.tryFlatMatch(str, 1, argc))
+    if (const FlatMatch *fm = g.tryFlatMatch(cx, str, 1, argc))
         return BuildFlatMatchArray(cx, str, *fm, vp);
+    if (cx->throwing)  /* from tryFlatMatch */
+        return false;
 
     const RegExpPair *rep = g.normalizeRegExp(false, 1, argc, vp);
     if (!rep)
         return false;
 
     AutoObjectRooter array(cx);
     MatchArgType arg = array.addr();
     RegExpStatics *res = cx->regExpStatics();
@@ -1941,20 +1826,22 @@ static JSBool
 str_search(JSContext *cx, uintN argc, Value *vp)
 {
     JSString *str;
     NORMALIZE_THIS(cx, vp, str);
 
     RegExpGuard g(cx);
     if (!g.init(argc, vp))
         return false;
-    if (const FlatMatch *fm = g.tryFlatMatch(str, 1, argc)) {
+    if (const FlatMatch *fm = g.tryFlatMatch(cx, str, 1, argc)) {
         vp->setInt32(fm->match());
         return true;
     }
+    if (cx->throwing)  /* from tryFlatMatch */
+        return false;
     const RegExpPair *rep = g.normalizeRegExp(false, 1, argc, vp);
     if (!rep)
         return false;
 
     RegExpStatics *res = cx->regExpStatics();
     size_t i = 0;
     if (!rep->re().execute(cx, res, str, &i, true, vp))
         return false;
@@ -2268,28 +2155,31 @@ ReplaceCallback(JSContext *cx, RegExpSta
     DoReplace(cx, res, rdata, chars);
     return true;
 }
 
 static bool
 BuildFlatReplacement(JSContext *cx, JSString *textstr, JSString *repstr,
                      const FlatMatch &fm, Value *vp)
 {
-    JSRopeBuilder builder(cx);
-    size_t match = fm.match(); /* Avoid signed/unsigned warnings. */
+    RopeBuilder builder(cx);
+    size_t match = fm.match();
     size_t matchEnd = match + fm.patternLength();
 
-    if (textstr->isTopNode()) {
+    if (textstr->isRope()) {
         /*
          * If we are replacing over a rope, avoid flattening it by iterating
          * through it, building a new rope.
          */
-        JSRopeLeafIterator iter;
+        StringSegmentRange r(cx);
+        if (!r.init(textstr))
+            return false;
         size_t pos = 0;
-        for (JSString *str = iter.init(textstr); str; str = iter.next()) {
+        while (!r.empty()) {
+            JSString *str = r.front();
             size_t len = str->length();
             size_t strEnd = pos + len;
             if (pos < matchEnd && strEnd > match) {
                 /*
                  * We need to special-case any part of the rope that overlaps
                  * with the replacement string.
                  */
                 if (match >= pos) {
@@ -2317,32 +2207,34 @@ BuildFlatReplacement(JSContext *cx, JSSt
                     if (!rightSide || !builder.append(rightSide))
                         return false;
                 }
             } else {
                 if (!builder.append(str))
                     return false;
             }
             pos += str->length();
+            if (!r.popFront())
+                return false;
         }
     } else {
         JSString *leftSide = js_NewDependentString(cx, textstr, 0, match);
         if (!leftSide)
             return false;
         JSString *rightSide = js_NewDependentString(cx, textstr, match + fm.patternLength(),
                                                     textstr->length() - match - fm.patternLength());
         if (!rightSide ||
             !builder.append(leftSide) ||
             !builder.append(repstr) ||
             !builder.append(rightSide)) {
             return false;
         }
     }
 
-    vp->setString(builder.getStr());
+    vp->setString(builder.result());
     return true;
 }
 
 /*
  * Perform a linear-scan dollar substitution on the replacement text,
  * constructing a result string that looks like:
  *
  *      newstring = string[:matchStart] + dollarSub(replaceValue) + string[matchLimit:]
@@ -2406,23 +2298,23 @@ BuildDollarReplacement(JSContext *cx, JS
     JSString *newReplace = js_NewStringFromCharBuffer(cx, newReplaceChars);
     ENSURE(newReplace);
 
     JS_ASSERT(textstr->length() >= matchLimit);
     JSString *rightSide = js_NewDependentString(cx, textstr, matchLimit,
                                                 textstr->length() - matchLimit);
     ENSURE(rightSide);
 
-    JSRopeBuilder builder(cx);
+    RopeBuilder builder(cx);
     ENSURE(builder.append(leftSide) &&
            builder.append(newReplace) &&
            builder.append(rightSide));
 #undef ENSURE
 
-    vp->setString(builder.getStr());
+    vp->setString(builder.result());
     return true;
 }
 
 static inline bool
 str_replace_regexp(JSContext *cx, uintN argc, Value *vp, ReplaceData &rdata)
 {
     const RegExpPair *rep = rdata.g.normalizeRegExp(true, 2, argc, vp);
     if (!rep)
@@ -2492,24 +2384,24 @@ str_replace_flat_lambda(JSContext *cx, u
         return false;
 
     size_t matchLimit = fm.match() + fm.patternLength();
     JSString *rightSide = js_NewDependentString(cx, rdata.str, matchLimit,
                                                 rdata.str->length() - matchLimit);
     if (!rightSide)
         return false;
 
-    JSRopeBuilder builder(cx);
+    RopeBuilder builder(cx);
     if (!(builder.append(leftSide) &&
           builder.append(repstr) &&
           builder.append(rightSide))) {
         return false;
     }
 
-    vp->setString(builder.getStr());
+    vp->setString(builder.result());
     return true;
 }
 
 JSBool
 js::str_replace(JSContext *cx, uintN argc, Value *vp)
 {
     ReplaceData rdata(cx);
     NORMALIZE_THIS(cx, vp, rdata.str);
@@ -2578,18 +2470,20 @@ js::str_replace(JSContext *cx, uintN arg
      * its input to a regular expression. (Even if it contains metachars.)
      *
      * However, if the user invokes our (non-standard) |flags| argument
      * extension then we revert to creating a regular expression. Note that
      * this is observable behavior through the side-effect mutation of the
      * |RegExp| statics.
      */
 
-    const FlatMatch *fm = rdata.g.tryFlatMatch(rdata.str, optarg, argc, false);
+    const FlatMatch *fm = rdata.g.tryFlatMatch(cx, rdata.str, optarg, argc, false);
     if (!fm) {
+        if (cx->throwing)  /* from tryFlatMatch */
+            return false;
         JS_ASSERT_IF(!rdata.g.hasRegExpPair(), argc > optarg);
         return str_replace_regexp(cx, argc, vp, rdata);
     }
 
     if (fm->match() < 0) {
         vp->setString(rdata.str);
         return true;
     }
@@ -3199,24 +3093,27 @@ static JSFunctionSpec string_methods[] =
 #define R6(n)  R4(n),  R4((n) + (1 << 4)),   R4((n) + (2 << 4)),   R4((n) + (3 << 4))
 #define R8(n)  R6(n),  R6((n) + (1 << 6)),   R6((n) + (2 << 6)),   R6((n) + (3 << 6))
 #define R10(n) R8(n),  R8((n) + (1 << 8)),   R8((n) + (2 << 8)),   R8((n) + (3 << 8))
 #define R12(n) R10(n), R10((n) + (1 << 10)), R10((n) + (2 << 10)), R10((n) + (3 << 10))
 
 #define R3(n) R2(n), R2((n) + (1 << 2))
 #define R7(n) R6(n), R6((n) + (1 << 6))
 
+#define BUILD_LENGTH_AND_FLAGS(length, flags)                                 \
+    (((length) << JSString::LENGTH_SHIFT) | (flags))
+
 /*
  * Declare unit strings. Pack the string data itself into the mInlineChars
  * place in the header.
  */
 #define R(c) {                                                                \
-    JSString::FLAT | JSString::ATOMIZED | (1 << JSString::FLAGS_LENGTH_SHIFT),\
+    BUILD_LENGTH_AND_FLAGS(1, JSString::FLAT | JSString::ATOMIZED),           \
     { (jschar *)(((char *)(unitStringTable + (c))) +                          \
-      offsetof(JSString, mInlineStorage)) },                                  \
+      offsetof(JSString, inlineStorage)) },                                   \
     { {(c), 0x00} } }
 
 #ifdef __SUNPRO_CC
 #pragma pack(8)
 #else
 #pragma pack(push, 8)
 #endif
 
@@ -3264,19 +3161,19 @@ const jschar JSString::fromSmallChar[] =
 #undef R
 
 /*
  * For code-generation ease, length-2 strings are encoded as 12-bit int values,
  * where the upper 6 bits is the first character and the lower 6 bits is the
  * second character.
  */
 #define R(c) {                                                                \
-    JSString::FLAT | JSString::ATOMIZED | (2 << JSString::FLAGS_LENGTH_SHIFT),\
+    BUILD_LENGTH_AND_FLAGS(2, JSString::FLAT | JSString::ATOMIZED),           \
     { (jschar *)(((char *)(length2StringTable + (c))) +                       \
-      offsetof(JSString, mInlineStorage)) },                                  \
+      offsetof(JSString, inlineStorage)) },                                   \
     { {FROM_SMALL_CHAR((c) >> 6), FROM_SMALL_CHAR((c) & 0x3F), 0x00} } }
 
 #ifdef __SUNPRO_CC
 #pragma pack(8)
 #else
 #pragma pack(push, 8)
 #endif
 
@@ -3297,19 +3194,19 @@ const JSString JSString::length2StringTa
 /*
  * Declare int strings. Only int strings from 100 to 255 actually have to be
  * generated, since the rest are either unit strings or length-2 strings. To
  * avoid the runtime cost of figuring out where to look for the string for a
  * particular integer, we precompute a table of JSString*s which refer to the
  * correct location of the int string.
  */
 #define R(c) {                                                                \
-    JSString::FLAT | JSString::ATOMIZED | (3 << JSString::FLAGS_LENGTH_SHIFT),\
+    BUILD_LENGTH_AND_FLAGS(3, JSString::FLAT | JSString::ATOMIZED),           \
     { (jschar *)(((char *)(hundredStringTable + ((c) - 100))) +               \
-      offsetof(JSString, mInlineStorage)) },                                  \
+      offsetof(JSString, inlineStorage)) },                                   \
     { {((c) / 100) + '0', ((c) / 10 % 10) + '0', ((c) % 10) + '0', 0x00} } }
 
 
 JS_STATIC_ASSERT(100 + (1 << 7) + (1 << 4) + (1 << 3) + (1 << 2) == 256);
 
 #ifdef __SUNPRO_CC
 #pragma pack(8)
 #else
--- a/js/src/jsstr.h
+++ b/js/src/jsstr.h
@@ -52,19 +52,16 @@
 #include "jsapi.h"
 #include "jsprvtd.h"
 #include "jshashtable.h"
 #include "jslock.h"
 #include "jsobj.h"
 #include "jsvalue.h"
 #include "jscell.h"
 
-#define JSSTRING_BIT(n)             ((size_t)1 << (n))
-#define JSSTRING_BITMASK(n)         (JSSTRING_BIT(n) - 1)
-
 enum {
     UNIT_STRING_LIMIT        = 256U,
     SMALL_CHAR_LIMIT         = 128U, /* Bigger chars cannot be in a length-2 string. */
     NUM_SMALL_CHARS          = 64U,
     INT_STRING_LIMIT         = 256U,
     NUM_HUNDRED_STRINGS      = 156U
 };
 
@@ -103,336 +100,271 @@ namespace js { namespace mjit {
  * extending |str1 = "abc"| with the character |str2 = str1 + "d"| will place
  * "d" in the extra capacity from |str1|, make that the buffer for |str2|, and
  * turn |str1| into a dependent string of |str2|.
  *
  * Flat strings without the EXTENSIBLE flag can be safely accessed by multiple
  * threads.
  *
  * When the string is DEPENDENT, the string depends on characters of another
- * string strongly referenced by the mBase field. The base member may point to
+ * string strongly referenced by the base field. The base member may point to
  * another dependent string if chars() has not been called yet.
  *
- * To optimize js_ConcatStrings and some other cases, we lazily concatenate
- * strings when possible, creating concatenation trees, a.k.a. ropes. A string
- * is an INTERIOR_NODE if it is a non-root, non-leaf node in a rope, and a
- * string is a TOP_NODE if it is the root of a rope. In order to meet API
- * requirements, chars() is not allowed to fail, so we build ropes so that they
- * form a well-defined tree structure, and the top node of every rope contains
- * an (almost) empty buffer that is large enough to contain the entire string.
- * Whenever chars() is called on a rope, it traverses its tree and fills that
- * buffer in, and when concatenating strings, we reuse these empty buffers
- * whenever possible, so that we can build a string through concatenation in
- * linear time, and have relatively few malloc calls when doing so.
- *
- * NB: Always use the length() and chars() accessor methods.
+ * When a string is a ROPE, it represents the lazy concatenation of other
+ * strings. In general, the nodes reachable from any rope form a dag.
  */
-struct JSString {
+struct JSString
+{
     friend class js::TraceRecorder;
     friend class js::mjit::Compiler;
 
-    friend JSAtom *
-    js_AtomizeString(JSContext *cx, JSString *str, uintN flags);
- public:
+    friend JSAtom *js_AtomizeString(JSContext *cx, JSString *str, uintN flags);
+
     /*
-     * Not private because we want to be able to use static
-     * initializers for them. Don't use these directly!
+     * Not private because we want to be able to use static initializers for
+     * them. Don't use these directly! FIXME bug 614459.
      */
-    size_t                          mLengthAndFlags;  /* in all strings */
+    size_t                 lengthAndFlags;      /* in all strings */
     union {
-        jschar                      *mChars; /* in flat and dependent strings */
-        JSString                    *mLeft;  /* in rope interior and top nodes */
-    };
+        jschar             *chars;              /* in non-rope strings */
+        JSString           *left;               /* in rope strings */
+    } u;
     union {
-        /*
-         * We may keep more than 4 inline chars, but 4 is necessary for all of
-         * our static initialization.
-         */
-        jschar                      mInlineStorage[4]; /* In short strings. */
+        jschar             inlineStorage[4];    /* in short strings */
         struct {
             union {
-                size_t              mCapacity; /* in extensible flat strings (optional) */
-                JSString            *mParent; /* in rope interior nodes */
-                JSRopeBufferInfo    *mBufferWithInfo; /* in rope top nodes */
+                JSString   *right;              /* in rope strings */
+                JSString   *base;               /* in dependent strings */
+                size_t     capacity;            /* in extensible flat strings */
             };
             union {
-                JSString            *mBase;  /* in dependent strings */
-                JSString            *mRight; /* in rope interior and top nodes */
+                JSString   *parent;             /* temporarily used during flatten */
+                size_t     reserved;            /* may use for bug 615290 */
             };
-        } e;
-        uintN                       externalStringType; /* for external strings. */
+        } s;
+        size_t             externalStringType;  /* in external strings */
     };
 
     /*
-     * The mLengthAndFlags field in string headers has data arranged in the
+     * The lengthAndFlags field in string headers has data arranged in the
      * following way:
      *
      * [ length (bits 4-31) ][ flags (bits 2-3) ][ type (bits 0-1) ]
      *
-     * The length is packed in mLengthAndFlags, even in string types that don't
+     * The length is packed in lengthAndFlags, even in string types that don't
      * need 3 other fields, to make the length check simpler.
      *
      * When the string type is FLAT, the flags can contain ATOMIZED or
      * EXTENSIBLE.
-     *
-     * When the string type is INTERIOR_NODE or TOP_NODE, the flags area is
-     * used to store the rope traversal count.
      */
-    static const size_t FLAT =          0;
-    static const size_t DEPENDENT =     1;
-    static const size_t INTERIOR_NODE = 2;
-    static const size_t TOP_NODE =      3;
+    static const size_t TYPE_FLAGS_MASK = JS_BITMASK(4);
+    static const size_t LENGTH_SHIFT    = 4;
+
+    static const size_t TYPE_MASK       = JS_BITMASK(2);
+    static const size_t FLAT            = 0x0;
+    static const size_t DEPENDENT       = 0x1;
+    static const size_t ROPE            = 0x2;
 
-    /* Rope/non-rope can be checked by checking one bit. */
-    static const size_t ROPE_BIT = JSSTRING_BIT(1);
-
-    static const size_t ATOMIZED = JSSTRING_BIT(2);
-    static const size_t EXTENSIBLE = JSSTRING_BIT(3);
+    /* Allow checking 1 bit for dependent/rope strings. */
+    static const size_t DEPENDENT_BIT   = JS_BIT(0);
+    static const size_t ROPE_BIT        = JS_BIT(1);
 
-    static const size_t FLAGS_LENGTH_SHIFT = 4;
+    static const size_t ATOMIZED        = JS_BIT(2);
+    static const size_t EXTENSIBLE      = JS_BIT(3);
 
-    static const size_t TYPE_MASK = JSSTRING_BITMASK(2);
-    static const size_t TYPE_FLAGS_MASK = JSSTRING_BITMASK(4);
 
-    inline bool hasFlag(size_t flag) const {
-        return (mLengthAndFlags & flag) != 0;
+    size_t buildLengthAndFlags(size_t length, size_t flags) {
+        return (length << LENGTH_SHIFT) | flags;
     }
 
     inline js::gc::Cell *asCell() {
         return reinterpret_cast<js::gc::Cell *>(this);
     }
-    
+
     inline js::gc::FreeCell *asFreeCell() {
         return reinterpret_cast<js::gc::FreeCell *>(this);
     }
 
     /*
      * Generous but sane length bound; the "-1" is there for comptibility with
      * OOM tests.
      */
     static const size_t MAX_LENGTH = (1 << 28) - 1;
 
-    inline size_t type() const {
-        return mLengthAndFlags & TYPE_MASK;
-    }
-
     JS_ALWAYS_INLINE bool isDependent() const {
-        return type() == DEPENDENT;
+        return lengthAndFlags & DEPENDENT_BIT;
     }
 
     JS_ALWAYS_INLINE bool isFlat() const {
-        return type() == FLAT;
+        return (lengthAndFlags & TYPE_MASK) == FLAT;
     }
 
-    inline bool isExtensible() const {
-        return isFlat() && hasFlag(EXTENSIBLE);
-    }
-
-    inline bool isRope() const {
-        return hasFlag(ROPE_BIT);
+    JS_ALWAYS_INLINE bool isExtensible() const {
+        JS_ASSERT_IF(lengthAndFlags & EXTENSIBLE, isFlat());
+        return lengthAndFlags & EXTENSIBLE;
     }
 
     JS_ALWAYS_INLINE bool isAtomized() const {
-        return isFlat() && hasFlag(ATOMIZED);
+        JS_ASSERT_IF(lengthAndFlags & ATOMIZED, isFlat());
+        return lengthAndFlags & ATOMIZED;
     }
 
-    inline bool isInteriorNode() const {
-        return type() == INTERIOR_NODE;
-    }
-
-    inline bool isTopNode() const {
-        return type() == TOP_NODE;
+    JS_ALWAYS_INLINE bool isRope() const {
+        return lengthAndFlags & ROPE_BIT;
     }
 
     JS_ALWAYS_INLINE jschar *chars() {
-        if (JS_UNLIKELY(isRope()))
-            flatten();
-        return mChars;
+        ensureNotRope();
+        return u.chars;
     }
 
     JS_ALWAYS_INLINE size_t length() const {
-        return mLengthAndFlags >> FLAGS_LENGTH_SHIFT;
+        return lengthAndFlags >> LENGTH_SHIFT;
     }
 
     JS_ALWAYS_INLINE bool empty() const {
-        return length() == 0;
+        return lengthAndFlags <= TYPE_FLAGS_MASK;
     }
 
     JS_ALWAYS_INLINE void getCharsAndLength(const jschar *&chars, size_t &length) {
         chars = this->chars();
         length = this->length();
     }
 
     JS_ALWAYS_INLINE void getCharsAndEnd(const jschar *&chars, const jschar *&end) {
         end = length() + (chars = this->chars());
     }
 
-    JS_ALWAYS_INLINE jschar *inlineStorage() {
-        JS_ASSERT(isFlat());
-        return mInlineStorage;
-    }
-
     JS_ALWAYS_INLINE void initFlatNotTerminated(jschar *chars, size_t length) {
         JS_ASSERT(length <= MAX_LENGTH);
         JS_ASSERT(!isStatic(this));
-        e.mBase = NULL;
-        e.mCapacity = 0;
-        mLengthAndFlags = (length << FLAGS_LENGTH_SHIFT) | FLAT;
-        mChars = chars;
+        lengthAndFlags = buildLengthAndFlags(length, FLAT);
+        u.chars = chars;
     }
 
     /* Specific flat string initializer and accessor methods. */
     JS_ALWAYS_INLINE void initFlat(jschar *chars, size_t length) {
         initFlatNotTerminated(chars, length);
         JS_ASSERT(chars[length] == jschar(0));
     }
 
     JS_ALWAYS_INLINE void initShortString(jschar *chars, size_t length) {
         JS_ASSERT(length <= MAX_LENGTH);
+        JS_ASSERT(chars >= inlineStorage && chars < (jschar *)(this + 2));
         JS_ASSERT(!isStatic(this));
-        mLengthAndFlags = (length << FLAGS_LENGTH_SHIFT) | FLAT;
-        mChars = chars;
+        lengthAndFlags = buildLengthAndFlags(length, FLAT);
+        u.chars = chars;
     }
 
     JS_ALWAYS_INLINE void initFlatExtensible(jschar *chars, size_t length, size_t cap) {
         JS_ASSERT(length <= MAX_LENGTH);
         JS_ASSERT(chars[length] == jschar(0));
         JS_ASSERT(!isStatic(this));
-        e.mBase = NULL;
-        e.mCapacity = cap;
-        mLengthAndFlags = (length << FLAGS_LENGTH_SHIFT) | FLAT | EXTENSIBLE;
-        mChars = chars;
+        lengthAndFlags = buildLengthAndFlags(length, FLAT | EXTENSIBLE);
+        u.chars = chars;
+        s.capacity = cap;
     }
 
     JS_ALWAYS_INLINE jschar *flatChars() const {
         JS_ASSERT(isFlat());
-        return mChars;
+        return u.chars;
     }
 
     JS_ALWAYS_INLINE size_t flatLength() const {
         JS_ASSERT(isFlat());
         return length();
     }
 
-    JS_ALWAYS_INLINE size_t flatCapacity() const {
-        JS_ASSERT(isFlat());
-        return e.mCapacity;
-    }
-
     inline void flatSetAtomized() {
         JS_ASSERT(isFlat());
         JS_ASSERT(!isStatic(this));
-        mLengthAndFlags |= ATOMIZED;
+        lengthAndFlags |= ATOMIZED;
     }
 
     inline void flatClearExtensible() {
+        /*
+         * N.B. This may be called on static strings, which may be in read-only
+         * memory, so we cannot unconditionally apply the mask.
+         */
         JS_ASSERT(isFlat());
-
-        /*
-         * We cannot eliminate the flag check before writing to mLengthAndFlags as
-         * static strings may reside in write-protected memory. See bug 599481.
-         */
-        if (mLengthAndFlags & EXTENSIBLE)
-            mLengthAndFlags &= ~EXTENSIBLE;
+        if (lengthAndFlags & EXTENSIBLE)
+            lengthAndFlags &= ~EXTENSIBLE;
     }
 
     /*
-     * The chars pointer should point somewhere inside the buffer owned by bstr.
-     * The caller still needs to pass bstr for GC purposes.
+     * The chars pointer should point somewhere inside the buffer owned by base.
+     * The caller still needs to pass base for GC purposes.
      */
-    inline void initDependent(JSString *bstr, jschar *chars, size_t len) {
-        JS_ASSERT(len <= MAX_LENGTH);
+    inline void initDependent(JSString *base, jschar *chars, size_t length) {
         JS_ASSERT(!isStatic(this));
-        e.mParent = NULL;
-        mChars = chars;
-        mLengthAndFlags = DEPENDENT | (len << FLAGS_LENGTH_SHIFT);
-        e.mBase = bstr;
+        JS_ASSERT(base->isFlat());
+        JS_ASSERT(chars >= base->chars() && chars < base->chars() + base->length());
+        JS_ASSERT(length <= base->length() - (chars - base->chars()));
+        lengthAndFlags = buildLengthAndFlags(length, DEPENDENT);
+        u.chars = chars;
+        s.base = base;
     }
 
     inline JSString *dependentBase() const {
         JS_ASSERT(isDependent());
-        return e.mBase;
+        return s.base;
     }
 
     JS_ALWAYS_INLINE jschar *dependentChars() {
-        return mChars;
+        JS_ASSERT(isDependent());
+        return u.chars;
     }
 
     inline size_t dependentLength() const {
         JS_ASSERT(isDependent());
         return length();
     }
 
-    /* Rope-related initializers and accessors. */
-    inline void initTopNode(JSString *left, JSString *right, size_t len,
-                            JSRopeBufferInfo *buf) {
-        JS_ASSERT(left->length() + right->length() <= MAX_LENGTH);
-        JS_ASSERT(!isStatic(this));
-        mLengthAndFlags = TOP_NODE | (len << FLAGS_LENGTH_SHIFT);
-        mLeft = left;
-        e.mRight = right;
-        e.mBufferWithInfo = buf;
-    }
-
-    inline void convertToInteriorNode(JSString *parent) {
-        JS_ASSERT(isTopNode());
-        e.mParent = parent;
-        mLengthAndFlags = INTERIOR_NODE | (length() << FLAGS_LENGTH_SHIFT);
-    }
-
-    inline JSString *interiorNodeParent() const {
-        JS_ASSERT(isInteriorNode());
-        return e.mParent;
-    }
-
-    inline JSString *ropeLeft() const {
-        JS_ASSERT(isRope());
-        return mLeft;
-    }
-
-    inline JSString *ropeRight() const {
-        JS_ASSERT(isRope());
-        return e.mRight;
-    }
-
-    inline size_t topNodeCapacity() const {
-        JS_ASSERT(isTopNode());
-        return e.mBufferWithInfo->capacity;
-    }
-
-    inline JSRopeBufferInfo *topNodeBuffer() const {
-        JS_ASSERT(isTopNode());
-        return e.mBufferWithInfo;
-    }
-
-    inline void nullifyTopNodeBuffer() {
-        JS_ASSERT(isTopNode());
-        e.mBufferWithInfo = NULL;
-    }
-
-    inline void finishTraversalConversion(JSString *base, jschar *end) {
-        mLengthAndFlags = JSString::DEPENDENT |
-                          ((end - mChars) << JSString::FLAGS_LENGTH_SHIFT);
-        e.mBase = base;
-    }
+    const jschar *undepend(JSContext *cx);
 
     inline bool ensureNotDependent(JSContext *cx) {
         return !isDependent() || undepend(cx);
     }
 
-    inline void ensureNotRope() {
+    const jschar *nonRopeChars() const {
+        JS_ASSERT(!isRope());
+        return u.chars;
+    }
+
+    /* Rope-related initializers and accessors. */
+    inline void initRopeNode(JSString *left, JSString *right, size_t length) {
+        JS_ASSERT(left->length() + right->length() == length);
+        lengthAndFlags = buildLengthAndFlags(length, ROPE);
+        u.left = left;
+        s.right = right;
+    }
+
+    inline JSString *ropeLeft() const {
+        JS_ASSERT(isRope());
+        return u.left;
+    }
+
+    inline JSString *ropeRight() const {
+        JS_ASSERT(isRope());
+        return s.right;
+    }
+
+    inline void finishTraversalConversion(JSString *base, jschar *baseBegin, jschar *end) {
+        JS_ASSERT(baseBegin <= u.chars && u.chars <= end);
+        lengthAndFlags = buildLengthAndFlags(end - u.chars, DEPENDENT);
+        s.base = base;
+    }
+
+    void flatten();
+
+    void ensureNotRope() {
         if (isRope())
             flatten();
     }
 
-    const jschar *undepend(JSContext *cx);
-
-    /* By design, this is not allowed to fail. */
-    void flatten();
-
     typedef uint8 SmallChar;
 
     static inline bool fitsInSmallChar(jschar c) {
         return c < SMALL_CHAR_LIMIT && toSmallChar[c] != INVALID_SMALL_CHAR;
     }
 
     static inline bool isUnitString(void *ptr) {
         jsuword delta = reinterpret_cast<jsuword>(ptr) -
@@ -490,21 +422,35 @@ struct JSString {
 
     static JSString *unitString(jschar c);
     static JSString *getUnitString(JSContext *cx, JSString *str, size_t index);
     static JSString *length2String(jschar c1, jschar c2);
     static JSString *length2String(uint32 i);
     static JSString *intString(jsint i);
 
     static JSString *lookupStaticString(const jschar *chars, size_t length);
-    
+
     JS_ALWAYS_INLINE void finalize(JSContext *cx);
+
+    static size_t offsetOfLengthAndFlags() {
+        return offsetof(JSString, lengthAndFlags);
+    }
+
+    static size_t offsetOfChars() {
+        return offsetof(JSString, u.chars);
+    }
+
+    static void staticAsserts() {
+        JS_STATIC_ASSERT(((JSString::MAX_LENGTH << JSString::LENGTH_SHIFT) >>
+                           JSString::LENGTH_SHIFT) == JSString::MAX_LENGTH);
+    }
 };
 
-struct JSExternalString : JSString {
+struct JSExternalString : JSString
+{
     static const uintN TYPE_LIMIT = 8;
     static JSStringFinalizeOp str_finalizers[TYPE_LIMIT];
 
     static intN changeFinalizer(JSStringFinalizeOp oldop,
                                 JSStringFinalizeOp newop) {
         for (uintN i = 0; i != JS_ARRAY_LENGTH(str_finalizers); i++) {
             if (str_finalizers[i] == oldop) {
                 str_finalizers[i] = newop;
@@ -520,189 +466,88 @@ struct JSExternalString : JSString {
 
 JS_STATIC_ASSERT(sizeof(JSString) == sizeof(JSExternalString));
 
 /*
  * Short strings should be created in cases where it's worthwhile to avoid
  * mallocing the string buffer for a small string. We keep 2 string headers'
  * worth of space in short strings so that more strings can be stored this way.
  */
-struct JSShortString : js::gc::Cell {
+class JSShortString : public js::gc::Cell
+{
     JSString mHeader;
     JSString mDummy;
 
+  public:
     /*
      * Set the length of the string, and return a buffer for the caller to write
      * to. This buffer must be written immediately, and should not be modified
      * afterward.
      */
     inline jschar *init(size_t length) {
         JS_ASSERT(length <= MAX_SHORT_STRING_LENGTH);
-        mHeader.initShortString(mHeader.inlineStorage(), length);
-        return mHeader.inlineStorage();
+        mHeader.initShortString(mHeader.inlineStorage, length);
+        return mHeader.inlineStorage;
     }
 
     inline jschar *getInlineStorageBeforeInit() {
-        return mHeader.mInlineStorage;
+        return mHeader.inlineStorage;
     }
 
     inline void initAtOffsetInBuffer(jschar *p, size_t length) {
-        JS_ASSERT(p >= mHeader.mInlineStorage && p < mHeader.mInlineStorage + MAX_SHORT_STRING_LENGTH);
+        JS_ASSERT(p >= mHeader.inlineStorage && p < mHeader.inlineStorage + MAX_SHORT_STRING_LENGTH);
         mHeader.initShortString(p, length);
     }
 
     inline void resetLength(size_t length) {
         mHeader.initShortString(mHeader.flatChars(), length);
     }
 
     inline JSString *header() {
         return &mHeader;
     }
 
+    static const size_t FREE_STRING_WORDS = 2;
+
     static const size_t MAX_SHORT_STRING_LENGTH =
-            ((sizeof(JSString) + 2 * sizeof(size_t)) / sizeof(jschar)) - 1;
+            ((sizeof(JSString) + FREE_STRING_WORDS * sizeof(size_t)) / sizeof(jschar)) - 1;
 
     static inline bool fitsIntoShortString(size_t length) {
         return length <= MAX_SHORT_STRING_LENGTH;
     }
 
     JS_ALWAYS_INLINE void finalize(JSContext *cx);
-};
 
-/*
- * We're doing some tricks to give us more space for short strings, so make
- * sure that space is ordered in the way we expect.
- */
-JS_STATIC_ASSERT(offsetof(JSString, mInlineStorage) == 2 * sizeof(void *));
-JS_STATIC_ASSERT(offsetof(JSShortString, mDummy) == sizeof(JSString));
-JS_STATIC_ASSERT(offsetof(JSString, mInlineStorage) +
-                 sizeof(jschar) * (JSShortString::MAX_SHORT_STRING_LENGTH + 1) ==
-                 sizeof(JSShortString));
-
-/*
- * An iterator that iterates through all nodes in a rope (the top node, the
- * interior nodes, and the leaves) without writing to any of the nodes.
- *
- * It is safe to iterate through a rope in this way, even when something else is
- * already iterating through it.
- *
- * To use, pass any node of the rope into the constructor. The first call should
- * be to init, which returns the first node, and each subsequent call should
- * be to next. NULL is returned when there are no more nodes to return.
- */
-class JSRopeNodeIterator {
-  private:
-    JSString *mStr;
-    size_t mUsedFlags;
-
-    static const size_t DONE_LEFT = 0x1;
-    static const size_t DONE_RIGHT = 0x2;
-
-  public:
-    JSRopeNodeIterator()
-      : mStr(NULL), mUsedFlags(0)
-    {}
-
-    JSString *init(JSString *str) {
-        /* Move to the farthest-left leaf in the rope. */
-        mStr = str;
-        while (mStr->isInteriorNode())
-            mStr = mStr->interiorNodeParent();
-        while (mStr->ropeLeft()->isInteriorNode())
-            mStr = mStr->ropeLeft();
-        JS_ASSERT(mUsedFlags == 0);
-        return mStr;
-    }
-
-    JSString *next() {
-        if (!mStr)
-            return NULL;
-        if (!mStr->ropeLeft()->isInteriorNode() && !(mUsedFlags & DONE_LEFT)) {
-            mUsedFlags |= DONE_LEFT;
-            return mStr->ropeLeft();
-        }
-        if (!mStr->ropeRight()->isInteriorNode() && !(mUsedFlags & DONE_RIGHT)) {
-            mUsedFlags |= DONE_RIGHT;
-            return mStr->ropeRight();
-        }
-        if (mStr->ropeRight()->isInteriorNode()) {
-            /*
-             * If we have a right child, go right once, then left as far as
-             * possible.
-             */
-            mStr = mStr->ropeRight();
-            while (mStr->ropeLeft()->isInteriorNode())
-                mStr = mStr->ropeLeft();
-        } else {
-            /*
-             * If we have no right child, follow our parent until we move
-             * up-right.
-             */
-            JSString *prev;
-            do {
-                prev = mStr;
-                /* Set the string to NULL if we reach the end of the tree. */
-                mStr = mStr->isInteriorNode() ? mStr->interiorNodeParent() : NULL;
-            } while (mStr && mStr->ropeRight() == prev);
-        }
-        mUsedFlags = 0;
-        return mStr;
+    static void staticAsserts() {
+        JS_STATIC_ASSERT(offsetof(JSString, inlineStorage) ==
+                         sizeof(JSString) - JSShortString::FREE_STRING_WORDS * sizeof(void *));
+        JS_STATIC_ASSERT(offsetof(JSShortString, mDummy) == sizeof(JSString));
+        JS_STATIC_ASSERT(offsetof(JSString, inlineStorage) +
+                         sizeof(jschar) * (JSShortString::MAX_SHORT_STRING_LENGTH + 1) ==
+                         sizeof(JSShortString));
     }
 };
 
-/*
- * An iterator that returns the leaves of a rope (which hold the actual string
- * data) in order. The usage is the same as JSRopeNodeIterator.
- */
-class JSRopeLeafIterator {
-  private:
-    JSRopeNodeIterator mNodeIterator;
-
-  public:
-    inline JSString *init(JSString *str) {
-        JS_ASSERT(str->isTopNode());
-        str = mNodeIterator.init(str);
-        while (str->isRope()) {
-            str = mNodeIterator.next();
-            JS_ASSERT(str);
-        }
-        return str;
-    }
+namespace js {
 
-    inline JSString *next() {
-        JSString *str;
-        do {
-            str = mNodeIterator.next();
-        } while (str && str->isRope());
-        return str;
-    }
-};
-
-class JSRopeBuilder {
-    JSContext   * const cx;
-    JSString    *mStr;
-
-  public:
-    JSRopeBuilder(JSContext *cx);
+/*
+ * When an algorithm does not need a string represented as a single linear
+ * array of characters, this range utility may be used to traverse the string a
+ * sequence of linear arrays of characters. This avoids flattening ropes.
+ *
+ * Implemented in jsstrinlines.h.
+ */
+class StringSegmentRange;
 
-    inline bool append(JSString *str) {
-        mStr = js_ConcatStrings(cx, mStr, str);
-        return !!mStr;
-    }
+/*
+ * Utility for building a rope (lazy concatenation) of strings.
+ */
+class RopeBuilder;
 
-    inline JSString *getStr() {
-        return mStr;
-    }
-};
-     
-JS_STATIC_ASSERT(JSString::INTERIOR_NODE & JSString::ROPE_BIT);
-JS_STATIC_ASSERT(JSString::TOP_NODE & JSString::ROPE_BIT);
-
-JS_STATIC_ASSERT(((JSString::MAX_LENGTH << JSString::FLAGS_LENGTH_SHIFT) >>
-                   JSString::FLAGS_LENGTH_SHIFT) == JSString::MAX_LENGTH);
+}  /* namespace js */
 
 extern const jschar *
 js_GetStringChars(JSContext *cx, JSString *str);
 
 extern const jschar *
 js_UndependString(JSContext *cx, JSString *str);
 
 extern JSBool
--- a/js/src/jsstrinlines.h
+++ b/js/src/jsstrinlines.h
@@ -128,26 +128,24 @@ JSString::finalize(JSContext *cx) {
         JS_ASSERT(dependentBase());
         JS_RUNTIME_UNMETER(cx->runtime, liveDependentStrings);
     } else if (isFlat()) {
         /*
          * flatChars for stillborn string is null, but cx->free checks
          * for a null pointer on its own.
          */
         cx->free(flatChars());
-    } else if (isTopNode()) {
-        cx->free(topNodeBuffer());
     }
 }
 
 inline void
 JSShortString::finalize(JSContext *cx)
 {
-    JS_ASSERT(!JSString::isStatic(header()));
-    JS_ASSERT(header()->isFlat());
+    JS_ASSERT(!JSString::isStatic(&mHeader));
+    JS_ASSERT(mHeader.isFlat());
     JS_RUNTIME_UNMETER(cx->runtime, liveStrings);
 }
 
 inline void
 JSExternalString::finalize(JSContext *cx)
 {
     JS_ASSERT(unsigned(externalStringType) < JS_ARRAY_LENGTH(str_finalizers));
     JS_ASSERT(!isStatic(this));
@@ -172,13 +170,80 @@ JSExternalString::finalize()
         /*
          * Assume that the finalizer for the permanently interned
          * string knows how to deal with null context.
          */
         finalizer(NULL, this);
     }
 }
 
-inline
-JSRopeBuilder::JSRopeBuilder(JSContext *cx)
-  : cx(cx), mStr(cx->runtime->emptyString) {}
+namespace js {
+
+class RopeBuilder {
+    JSContext *cx;
+    JSString *res;
+
+  public:
+    RopeBuilder(JSContext *cx)
+      : cx(cx), res(cx->runtime->emptyString)
+    {}
+
+    inline bool append(JSString *str) {
+        res = js_ConcatStrings(cx, res, str);
+        return !!res;
+    }
+
+    inline JSString *result() {
+        return res;
+    }
+};
+
+class StringSegmentRange
+{
+    /*
+     * If malloc() shows up in any profiles from this vector, we can add a new
+     * StackAllocPolicy which stashes a reusable freed-at-gc buffer in the cx.
+     */
+    Vector<JSString *, 32> stack;
+    JSString *cur;
+
+    bool settle(JSString *str) {
+        while (str->isRope()) {
+            if (!stack.append(str->ropeRight()))
+                return false;
+            str = str->ropeLeft();
+        }
+        cur = str;
+        return true;
+    }
+
+  public:
+    StringSegmentRange(JSContext *cx)
+      : stack(cx), cur(NULL)
+    {}
+
+    JS_WARN_UNUSED_RESULT bool init(JSString *str) {
+        JS_ASSERT(stack.empty());
+        return settle(str);
+    }
+
+    bool empty() const {
+        return cur == NULL;
+    }
+
+    JSString *front() const {
+        JS_ASSERT(!cur->isRope());
+        return cur;
+    }
+
+    JS_WARN_UNUSED_RESULT bool popFront() {
+        JS_ASSERT(!empty());
+        if (stack.empty()) {
+            cur = NULL;
+            return true;
+        }
+        return settle(stack.popCopy());
+    }
+};
+
+}  /* namespace js */
 
 #endif /* jsstrinlines_h___ */
--- a/js/src/jstracer.cpp
+++ b/js/src/jstracer.cpp
@@ -12425,17 +12425,17 @@ TraceRecorder::getCharCodeAt(JSString *s
     LIns *lengthAndFlags_ins = w.ldpStringLengthAndFlags(str_ins);
     if (MaybeBranch mbr = w.jt(w.eqp0(w.andp(lengthAndFlags_ins, w.nameImmw(JSString::ROPE_BIT)))))
     {
         w.call(&js_Flatten_ci, &str_ins);
         w.label(mbr);
     }
 
     guard(true,
-          w.ltup(idx_ins, w.rshupN(lengthAndFlags_ins, JSString::FLAGS_LENGTH_SHIFT)),
+          w.ltup(idx_ins, w.rshupN(lengthAndFlags_ins, JSString::LENGTH_SHIFT)),
           snapshot(MISMATCH_EXIT));
     *out = w.i2d(w.getStringChar(str_ins, idx_ins));
     return RECORD_CONTINUE;
 }
 
 JS_STATIC_ASSERT(sizeof(JSString) == 16 || sizeof(JSString) == 32);
 
 
@@ -12456,17 +12456,17 @@ TraceRecorder::getCharAt(JSString *str, 
     LIns *lengthAndFlags_ins = w.ldpStringLengthAndFlags(str_ins);
     if (MaybeBranch mbr = w.jt(w.eqp0(w.andp(lengthAndFlags_ins,
                                              w.nameImmw(JSString::ROPE_BIT)))))
     {
         w.call(&js_Flatten_ci, &str_ins);
         w.label(mbr);
     }
 
-    LIns* inRange = w.ltup(idx_ins, w.rshupN(lengthAndFlags_ins, JSString::FLAGS_LENGTH_SHIFT));
+    LIns* inRange = w.ltup(idx_ins, w.rshupN(lengthAndFlags_ins, JSString::LENGTH_SHIFT));
 
     if (mode == JSOP_GETELEM) {
         guard(true, inRange, MISMATCH_EXIT);
 
         *out = getUnitString(str_ins, idx_ins);
     } else {
         LIns *phi_ins = w.allocp(sizeof(JSString *));
         w.stAlloc(w.nameImmpNonGC(cx->runtime->emptyString), phi_ins);
--- a/js/src/jstypes.h
+++ b/js/src/jstypes.h
@@ -216,16 +216,24 @@
 #  define JS_NEVER_INLINE __declspec(noinline)
 # elif defined __GNUC__
 #  define JS_NEVER_INLINE __attribute__((noinline))
 # else
 #  define JS_NEVER_INLINE
 # endif
 #endif
 
+#ifndef JS_WARN_UNUSED_RESULT
+# if defined __GNUC__
+#  define JS_WARN_UNUSED_RESULT __attribute__((warn_unused_result))
+# else
+#  define JS_WARN_UNUSED_RESULT
+# endif
+#endif
+
 #ifdef NS_STATIC_CHECKING
 /*
  * Attributes for static analysis. Functions declared with JS_REQUIRES_STACK
  * always have a valid cx->fp and can access it freely.  Other functions can
  * access cx->fp only after calling a function that "forces" the stack
  * (i.e. lazily instantiates it as needed).
  */
 # define JS_REQUIRES_STACK   __attribute__((user("JS_REQUIRES_STACK")))
--- a/js/src/jsvector.h
+++ b/js/src/jsvector.h
@@ -337,16 +337,18 @@ class Vector : AllocPolicy
     bool append(const T &t);
     bool appendN(const T &t, size_t n);
     template <class U> bool append(const U *begin, const U *end);
     template <class U> bool append(const U *begin, size_t length);
     template <class U, size_t O, class BP> bool append(const Vector<U,O,BP> &other);
 
     void popBack();
 
+    T popCopy();
+
     /*
      * Transfers ownership of the internal buffer used by Vector to the caller.
      * After this call, the Vector is empty. Since the returned buffer may need
      * to be allocated (if the elements are currently stored in-place), the
      * call can fail, returning NULL.
      *
      * N.B. Although a T*, only the range [0, length()) is constructed.
      */
@@ -686,16 +688,25 @@ Vector<T,N,AP>::popBack()
 {
     REENTRANCY_GUARD_ET_AL;
     JS_ASSERT(!empty());
     --mLength;
     endNoCheck()->~T();
 }
 
 template <class T, size_t N, class AP>
+JS_ALWAYS_INLINE T
+Vector<T,N,AP>::popCopy()
+{
+    T ret = back();
+    popBack();
+    return ret;
+}
+
+template <class T, size_t N, class AP>
 inline T *
 Vector<T,N,AP>::extractRawBuffer()
 {
     T *ret;
     if (usingInlineStorage()) {
         ret = reinterpret_cast<T *>(this->malloc(mLength * sizeof(T)));
         if (!ret)
             return NULL;
--- a/js/src/methodjit/Compiler.cpp
+++ b/js/src/methodjit/Compiler.cpp
@@ -2956,18 +2956,18 @@ mjit::Compiler::jsop_length()
         if (top->isConstant()) {
             JSString *str = top->getValue().toString();
             Value v;
             v.setNumber(uint32(str->length()));
             frame.pop();
             frame.push(v);
         } else {
             RegisterID str = frame.ownRegForData(top);
-            masm.loadPtr(Address(str, offsetof(JSString, mLengthAndFlags)), str);
-            masm.rshiftPtr(Imm32(JSString::FLAGS_LENGTH_SHIFT), str);
+            masm.loadPtr(Address(str, JSString::offsetOfLengthAndFlags()), str);
+            masm.rshiftPtr(Imm32(JSString::LENGTH_SHIFT), str);
             frame.pop();
             frame.pushTypedPayload(JSVAL_TYPE_INT32, str);
         }
         return true;
     }
 
 #if defined JS_POLYIC
     return jsop_getprop(cx->runtime->atomState.lengthAtom);
--- a/js/src/methodjit/MonoIC.cpp
+++ b/js/src/methodjit/MonoIC.cpp
@@ -287,23 +287,23 @@ class EqualityCompiler : public BaseComp
             linkToStub(rhsFail);
         }
 
         RegisterID tmp = ic.tempReg;
         
         /* Test if lhs/rhs are atomized. */
         Imm32 atomizedFlags(JSString::FLAT | JSString::ATOMIZED);
         
-        masm.load32(Address(lvr.dataReg(), offsetof(JSString, mLengthAndFlags)), tmp);
+        masm.load32(Address(lvr.dataReg(), JSString::offsetOfLengthAndFlags()), tmp);
         masm.and32(Imm32(JSString::TYPE_FLAGS_MASK), tmp);
         Jump lhsNotAtomized = masm.branch32(Assembler::NotEqual, tmp, atomizedFlags);
         linkToStub(lhsNotAtomized);
 
         if (!rvr.isConstant()) {
-            masm.load32(Address(rvr.dataReg(), offsetof(JSString, mLengthAndFlags)), tmp);
+            masm.load32(Address(rvr.dataReg(), JSString::offsetOfLengthAndFlags()), tmp);
             masm.and32(Imm32(JSString::TYPE_FLAGS_MASK), tmp);
             Jump rhsNotAtomized = masm.branch32(Assembler::NotEqual, tmp, atomizedFlags);
             linkToStub(rhsNotAtomized);
         }
 
         if (rvr.isConstant()) {
             JSString *str = rvr.value().toString();
             JS_ASSERT(str->isAtomized());
--- a/js/src/methodjit/PolyIC.cpp
+++ b/js/src/methodjit/PolyIC.cpp
@@ -972,19 +972,19 @@ class GetPropCompiler : public PICStubCo
 
     LookupStatus generateStringLengthStub()
     {
         JS_ASSERT(pic.hasTypeCheck());
 
         Assembler masm;
         Jump notString = masm.branchPtr(Assembler::NotEqual, pic.typeReg(),
                                         ImmType(JSVAL_TYPE_STRING));
-        masm.loadPtr(Address(pic.objReg, offsetof(JSString, mLengthAndFlags)), pic.objReg);
+        masm.loadPtr(Address(pic.objReg, JSString::offsetOfLengthAndFlags()), pic.objReg);
         // String length is guaranteed to be no more than 2**28, so the 32-bit operation is OK.
-        masm.urshift32(Imm32(JSString::FLAGS_LENGTH_SHIFT), pic.objReg);
+        masm.urshift32(Imm32(JSString::LENGTH_SHIFT), pic.objReg);
         masm.move(ImmType(JSVAL_TYPE_INT32), pic.shapeReg);
         Jump done = masm.jump();
 
         PICLinker buffer(masm, pic);
         if (!buffer.init(cx))
             return error();
 
         if (!buffer.verifyRange(pic.lastCodeBlock(f.jit())) ||
--- a/js/src/tracejit/Writer.cpp
+++ b/js/src/tracejit/Writer.cpp
@@ -479,27 +479,27 @@ void ValidateWriter::checkAccSet(LOpcode
         //
         // base = <JSString>
         // ins  = {ld,st}X.str base[<disp within JSString>]
         ok = dispWithin(JSString) &&
              couldBeObjectOrString(base);
         break;
 
       case ACCSET_STRING_MCHARS:
-        // base = ldp.string ...[offsetof(JSString, mChars)]
+        // base = ldp.string ...[offsetof(JSString, chars)]
         // ins  = ldus2ui.strchars/c base[0]
         //   OR
-        // base_oprnd1 = ldp.string ...[offsetof(JSString, mChars)]
+        // base_oprnd1 = ldp.string ...[offsetof(JSString, chars)]
         // base        = addp base_oprnd1, ...
         // ins         = ldus2ui.strchars/c base[0]
         ok = op == LIR_ldus2ui &&
              disp == 0 &&
-             (match(base, LIR_ldp, ACCSET_STRING, offsetof(JSString, mChars)) ||
+             (match(base, LIR_ldp, ACCSET_STRING, JSString::offsetOfChars()) ||
               (base->isop(LIR_addp) &&
-               match(base->oprnd1(), LIR_ldp, ACCSET_STRING, offsetof(JSString, mChars))));
+               match(base->oprnd1(), LIR_ldp, ACCSET_STRING, JSString::offsetOfChars())));
         break;
 
       case ACCSET_TYPEMAP:
         // This check is imperfect, things get complicated once you get back
         // farther than 'base'.  But the parts we check are pretty distinctive
         // and should be good enough.
         //
         // base = addp base_oprnd1, ...
--- a/js/src/tracejit/Writer.h
+++ b/js/src/tracejit/Writer.h
@@ -593,24 +593,24 @@ class Writer
     }
 
     nj::LIns *stpIterCursor(nj::LIns *cursor, nj::LIns *iter) const {
         return lir->insStore(nj::LIR_stp, cursor, iter, offsetof(NativeIterator, props_cursor),
                              ACCSET_ITER);
     }
 
     nj::LIns *ldpStringLengthAndFlags(nj::LIns *str) const {
-        return name(lir->insLoad(nj::LIR_ldp, str, offsetof(JSString, mLengthAndFlags),
+        return name(lir->insLoad(nj::LIR_ldp, str, JSString::offsetOfLengthAndFlags(),
                                  ACCSET_STRING),
-                    "mLengthAndFlags");
+                    "lengthAndFlags");
     }
 
     nj::LIns *ldpStringChars(nj::LIns *str) const {
-        return name(lir->insLoad(nj::LIR_ldp, str, offsetof(JSString, mChars), ACCSET_STRING),
-                    "mChars");
+        return name(lir->insLoad(nj::LIR_ldp, str, JSString::offsetOfChars(), ACCSET_STRING),
+                    "chars");
     }
 
     nj::LIns *lduc2uiConstTypeMapEntry(nj::LIns *typemap, nj::LIns *index) const {
         nj::LIns *entry = addp(typemap, ui2p(muli(index, name(immi(sizeof(JSValueType)),
                                                               "sizeof(JSValueType)"))));
         return lir->insLoad(nj::LIR_lduc2ui, entry, 0, ACCSET_TYPEMAP, nj::LOAD_CONST);
     }
 
@@ -1183,17 +1183,17 @@ class Writer
     nj::LIns *getDslotAddress(nj::LIns *obj, nj::LIns *idx) const {
         JS_ASSERT(sizeof(Value) == 8); // The |3| in the following statement requires this.
         nj::LIns *offset = lshpN(ui2p(idx), 3);
         nj::LIns *slots = ldpObjSlots(obj);
         return addp(slots, offset);
     }
 
     nj::LIns *getStringLength(nj::LIns *str) const {
-        return name(rshupN(ldpStringLengthAndFlags(str), JSString::FLAGS_LENGTH_SHIFT),
+        return name(rshupN(ldpStringLengthAndFlags(str), JSString::LENGTH_SHIFT),
                     "strLength");
     }
 
     nj::LIns *getStringChar(nj::LIns *str, nj::LIns *idx) const {
         nj::LIns *chars = ldpStringChars(str);
         return name(lir->insLoad(nj::LIR_ldus2ui, addp(chars, lshpN(idx, 1)), 0,
                                  ACCSET_STRING_MCHARS, nj::LOAD_CONST),
                     "strChar");