Bug 1008421 - Remove JSString::parent. r=luke
authorJan de Mooij <jdemooij@mozilla.com>
Wed, 14 May 2014 13:32:22 +0200
changeset 195580 45bbd4baf80c8520c156be5f8cb19102cd32ee38
parent 195579 967ee3262d27ca61c3ea18e5d7fdb3f0959a579a
child 195581 28ceedf9734dcd9992aee7fe4c6a8faf69e49eb0
push idunknown
push userunknown
push dateunknown
reviewersluke
bugs1008421
milestone32.0a1
Bug 1008421 - Remove JSString::parent. r=luke
js/src/vm/String-inl.h
js/src/vm/String.cpp
js/src/vm/String.h
--- a/js/src/vm/String-inl.h
+++ b/js/src/vm/String-inl.h
@@ -82,17 +82,17 @@ JSString::validateLength(js::ThreadSafeC
     }
 
     return true;
 }
 
 MOZ_ALWAYS_INLINE void
 JSRope::init(js::ThreadSafeContext *cx, JSString *left, JSString *right, size_t length)
 {
-    d.lengthAndFlags = buildLengthAndFlags(length, ROPE_FLAGS);
+    d.u0.lengthAndFlags = buildLengthAndFlags(length, ROPE_FLAGS);
     d.u1.left = left;
     d.s.u2.right = right;
     js::StringWriteBarrierPost(cx, &d.u1.left);
     js::StringWriteBarrierPost(cx, &d.s.u2.right);
 }
 
 template <js::AllowGC allowGC>
 MOZ_ALWAYS_INLINE JSRope *
@@ -117,17 +117,17 @@ JSRope::markChildren(JSTracer *trc)
     js::gc::MarkStringUnbarriered(trc, &d.s.u2.right, "right child");
 }
 
 MOZ_ALWAYS_INLINE void
 JSDependentString::init(js::ThreadSafeContext *cx, JSLinearString *base, const jschar *chars,
                         size_t length)
 {
     JS_ASSERT(!js::IsPoisonedPtr(base));
-    d.lengthAndFlags = buildLengthAndFlags(length, DEPENDENT_FLAGS);
+    d.u0.lengthAndFlags = buildLengthAndFlags(length, DEPENDENT_FLAGS);
     d.u1.chars = chars;
     d.s.u2.base = base;
     js::StringWriteBarrierPost(cx, reinterpret_cast<JSString **>(&d.s.u2.base));
 }
 
 MOZ_ALWAYS_INLINE JSLinearString *
 JSDependentString::new_(js::ExclusiveContext *cx,
                         JSLinearString *baseArg, const jschar *chars, size_t length)
@@ -180,17 +180,17 @@ JSString::markBase(JSTracer *trc)
 {
     JS_ASSERT(hasBase());
     js::gc::MarkStringUnbarriered(trc, &d.s.u2.base, "base");
 }
 
 MOZ_ALWAYS_INLINE void
 JSFlatString::init(const jschar *chars, size_t length)
 {
-    d.lengthAndFlags = buildLengthAndFlags(length, FIXED_FLAGS);
+    d.u0.lengthAndFlags = buildLengthAndFlags(length, FIXED_FLAGS);
     d.u1.chars = chars;
 }
 
 template <js::AllowGC allowGC>
 MOZ_ALWAYS_INLINE JSFlatString *
 JSFlatString::new_(js::ThreadSafeContext *cx, const jschar *chars, size_t length)
 {
     JS_ASSERT(chars[length] == jschar(0));
@@ -224,42 +224,42 @@ MOZ_ALWAYS_INLINE JSInlineString *
 JSInlineString::new_(js::ThreadSafeContext *cx)
 {
     return (JSInlineString *)js_NewGCString<allowGC>(cx);
 }
 
 MOZ_ALWAYS_INLINE jschar *
 JSInlineString::init(size_t length)
 {
-    d.lengthAndFlags = buildLengthAndFlags(length, FIXED_FLAGS);
+    d.u0.lengthAndFlags = buildLengthAndFlags(length, FIXED_FLAGS);
     d.u1.chars = d.inlineStorage;
     JS_ASSERT(lengthFits(length) || (isFatInline() && JSFatInlineString::lengthFits(length)));
     return d.inlineStorage;
 }
 
 MOZ_ALWAYS_INLINE void
 JSInlineString::resetLength(size_t length)
 {
-    d.lengthAndFlags = buildLengthAndFlags(length, FIXED_FLAGS);
+    d.u0.lengthAndFlags = buildLengthAndFlags(length, FIXED_FLAGS);
     JS_ASSERT(lengthFits(length) || (isFatInline() && JSFatInlineString::lengthFits(length)));
 }
 
 template <js::AllowGC allowGC>
 MOZ_ALWAYS_INLINE JSFatInlineString *
 JSFatInlineString::new_(js::ThreadSafeContext *cx)
 {
     return js_NewGCFatInlineString<allowGC>(cx);
 }
 
 MOZ_ALWAYS_INLINE void
 JSExternalString::init(const jschar *chars, size_t length, const JSStringFinalizer *fin)
 {
     JS_ASSERT(fin);
     JS_ASSERT(fin->finalize);
-    d.lengthAndFlags = buildLengthAndFlags(length, FIXED_FLAGS);
+    d.u0.lengthAndFlags = buildLengthAndFlags(length, FIXED_FLAGS);
     d.u1.chars = chars;
     d.s.u2.externalFinalizer = fin;
 }
 
 MOZ_ALWAYS_INLINE JSExternalString *
 JSExternalString::new_(JSContext *cx, const jschar *chars, size_t length,
                        const JSStringFinalizer *fin)
 {
--- a/js/src/vm/String.cpp
+++ b/js/src/vm/String.cpp
@@ -226,18 +226,17 @@ JSRope::flattenInternal(ExclusiveContext
      * 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. Since ropes can be dags, a node may be
      * encountered multiple times during traversal. However, step 3 above leaves
-     * a valid dependent string, so everything works out. This algorithm is
-     * homomorphic to marking code.
+     * a valid dependent string, so everything works out.
      *
      * 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 += ...
@@ -255,52 +254,60 @@ JSRope::flattenInternal(ExclusiveContext
      * N.B. This optimization can create chains of dependent strings.
      */
     const size_t wholeLength = length();
     size_t wholeCapacity;
     jschar *wholeChars;
     JSString *str = this;
     jschar *pos;
 
+    /*
+     * JSString::flattenData is a tagged pointer to the parent node.
+     * The tag indicates what to do when we return to the parent.
+     */
+    static const uintptr_t Tag_Mask = 0x3;
+    static const uintptr_t Tag_FinishNode = 0x0;
+    static const uintptr_t Tag_VisitRightChild = 0x1;
+
     /* 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
              */
+            JS_ASSERT(str->isRope());
             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;
+                JS_ASSERT(child->isRope());
                 str->d.u1.chars = left.chars();
-                child->d.s.u3.parent = str;
-                child->d.lengthAndFlags = 0x200;
+                child->d.u0.flattenData = uintptr_t(str) | Tag_VisitRightChild;
                 str = child;
             }
             if (b == WithIncrementalBarrier) {
                 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;
+            size_t bits = left.d.u0.lengthAndFlags;
             pos = wholeChars + (bits >> LENGTH_SHIFT);
             JS_STATIC_ASSERT(!(EXTENSIBLE_FLAGS & DEPENDENT_FLAGS));
-            left.d.lengthAndFlags = bits ^ (EXTENSIBLE_FLAGS | DEPENDENT_FLAGS);
+            left.d.u0.lengthAndFlags = bits ^ (EXTENSIBLE_FLAGS | DEPENDENT_FLAGS);
             left.d.s.u2.base = (JSLinearString *)this;  /* will be true on exit */
             StringWriteBarrierPostRemove(maybecx, &left.d.u1.left);
             StringWriteBarrierPost(maybecx, (JSString **)&left.d.s.u2.base);
             goto visit_right_child;
         }
     }
 
     if (!AllocChars(maybecx, wholeLength, &wholeChars, &wholeCapacity))
@@ -312,56 +319,56 @@ JSRope::flattenInternal(ExclusiveContext
             JSString::writeBarrierPre(str->d.u1.left);
             JSString::writeBarrierPre(str->d.s.u2.right);
         }
 
         JSString &left = *str->d.u1.left;
         str->d.u1.chars = pos;
         StringWriteBarrierPostRemove(maybecx, &str->d.u1.left);
         if (left.isRope()) {
-            left.d.s.u3.parent = str;          /* Return to this when 'left' done, */
-            left.d.lengthAndFlags = 0x200;     /* but goto visit_right_child. */
+            /* Return to this node when 'left' done, then goto visit_right_child. */
+            left.d.u0.flattenData = uintptr_t(str) | Tag_VisitRightChild;
             str = &left;
             goto first_visit_node;
         }
         size_t len = left.length();
         PodCopy(pos, left.d.u1.chars, len);
         pos += len;
     }
     visit_right_child: {
         JSString &right = *str->d.s.u2.right;
         if (right.isRope()) {
-            right.d.s.u3.parent = str;         /* Return to this node when 'right' done, */
-            right.d.lengthAndFlags = 0x300;    /* but goto finish_node. */
+            /* Return to this node when 'right' done, then goto finish_node. */
+            right.d.u0.flattenData = uintptr_t(str) | Tag_FinishNode;
             str = &right;
             goto first_visit_node;
         }
         size_t len = right.length();
         PodCopy(pos, right.d.u1.chars, len);
         pos += len;
     }
     finish_node: {
         if (str == this) {
             JS_ASSERT(pos == wholeChars + wholeLength);
             *pos = '\0';
-            str->d.lengthAndFlags = buildLengthAndFlags(wholeLength, EXTENSIBLE_FLAGS);
+            str->d.u0.lengthAndFlags = buildLengthAndFlags(wholeLength, EXTENSIBLE_FLAGS);
             str->d.u1.chars = wholeChars;
             str->d.s.u2.capacity = wholeCapacity;
             StringWriteBarrierPostRemove(maybecx, &str->d.u1.left);
             StringWriteBarrierPostRemove(maybecx, &str->d.s.u2.right);
             return &this->asFlat();
         }
-        size_t progress = str->d.lengthAndFlags;
-        str->d.lengthAndFlags = buildLengthAndFlags(pos - str->d.u1.chars, DEPENDENT_FLAGS);
+        uintptr_t flattenData = str->d.u0.flattenData;
+        str->d.u0.lengthAndFlags = buildLengthAndFlags(pos - str->d.u1.chars, DEPENDENT_FLAGS);
         str->d.s.u2.base = (JSLinearString *)this;       /* will be true on exit */
         StringWriteBarrierPost(maybecx, (JSString **)&str->d.s.u2.base);
-        str = str->d.s.u3.parent;
-        if (progress == 0x200)
+        str = (JSString *)(flattenData & ~Tag_Mask);
+        if ((flattenData & Tag_Mask) == Tag_VisitRightChild)
             goto visit_right_child;
-        JS_ASSERT(progress == 0x300);
+        JS_ASSERT((flattenData & Tag_Mask) == Tag_FinishNode);
         goto finish_node;
     }
 }
 
 JSFlatString *
 JSRope::flatten(ExclusiveContext *maybecx)
 {
 #if JSGC_INCREMENTAL
@@ -460,17 +467,17 @@ JSDependentString::undepend(ExclusiveCon
     PodCopy(s, chars(), n);
     s[n] = 0;
     d.u1.chars = s;
 
     /*
      * Transform *this into an undepended string so 'base' will remain rooted
      * for the benefit of any other dependent string that depends on *this.
      */
-    d.lengthAndFlags = buildLengthAndFlags(n, UNDEPENDED_FLAGS);
+    d.u0.lengthAndFlags = buildLengthAndFlags(n, UNDEPENDED_FLAGS);
 
     return &this->asFlat();
 }
 
 bool
 JSFlatString::isIndexSlow(uint32_t *indexp) const
 {
     const jschar *s = charsZ();
--- a/js/src/vm/String.h
+++ b/js/src/vm/String.h
@@ -131,34 +131,33 @@ static const size_t UINT32_CHAR_BUFFER_L
 class JSString : public js::gc::BarrieredCell<JSString>
 {
   protected:
     static const size_t NUM_INLINE_CHARS = 2 * sizeof(void *) / sizeof(jschar);
 
     /* Fields only apply to string types commented on the right. */
     struct Data
     {
-        size_t                     lengthAndFlags;      /* JSString */
+        union {
+            size_t                 lengthAndFlags;      /* JSString */
+            uintptr_t              flattenData;         /* JSRope (temporary while flattening) */
+        } u0;
         union {
             const jschar           *chars;              /* JSLinearString */
             JSString               *left;               /* JSRope */
         } u1;
         union {
             jschar                 inlineStorage[NUM_INLINE_CHARS]; /* JS(Inline|FatInline)String */
             struct {
                 union {
                     JSLinearString *base;               /* JS(Dependent|Undepended)String */
                     JSString       *right;              /* JSRope */
                     size_t         capacity;            /* JSFlatString (extensible) */
                     const JSStringFinalizer *externalFinalizer;/* JSExternalString */
                 } u2;
-                union {
-                    JSString       *parent;             /* JSRope (temporary) */
-                    size_t         reserved;            /* may use for bug 615290 */
-                } u3;
             } s;
         };
     } d;
 
   public:
     /* Flags exposed only for jits */
 
     /*
@@ -247,22 +246,22 @@ class JSString : public js::gc::Barriere
     /* Avoid lame compile errors in JSRope::flatten */
     friend class JSRope;
 
   public:
     /* All strings have length. */
 
     MOZ_ALWAYS_INLINE
     size_t length() const {
-        return d.lengthAndFlags >> LENGTH_SHIFT;
+        return d.u0.lengthAndFlags >> LENGTH_SHIFT;
     }
 
     MOZ_ALWAYS_INLINE
     bool empty() const {
-        return d.lengthAndFlags <= FLAGS_MASK;
+        return d.u0.lengthAndFlags <= FLAGS_MASK;
     }
 
     /*
      * All strings have a fallible operation to get an array of chars.
      * getCharsZ additionally ensures the array is null terminated.
      */
 
     inline const jschar *getChars(js::ExclusiveContext *cx);
@@ -294,17 +293,17 @@ class JSString : public js::gc::Barriere
     static bool ensureLinear(js::ExclusiveContext *cx, JSString *str) {
         return str->ensureLinear(cx) != nullptr;
     }
 
     /* Type query and debug-checked casts */
 
     MOZ_ALWAYS_INLINE
     bool isRope() const {
-        return (d.lengthAndFlags & FLAGS_MASK) == ROPE_FLAGS;
+        return (d.u0.lengthAndFlags & FLAGS_MASK) == ROPE_FLAGS;
     }
 
     MOZ_ALWAYS_INLINE
     JSRope &asRope() const {
         JS_ASSERT(isRope());
         return *(JSRope *)this;
     }
 
@@ -316,17 +315,17 @@ class JSString : public js::gc::Barriere
     MOZ_ALWAYS_INLINE
     JSLinearString &asLinear() const {
         JS_ASSERT(JSString::isLinear());
         return *(JSLinearString *)this;
     }
 
     MOZ_ALWAYS_INLINE
     bool isDependent() const {
-        return (d.lengthAndFlags & FLAGS_MASK) == DEPENDENT_FLAGS;
+        return (d.u0.lengthAndFlags & FLAGS_MASK) == DEPENDENT_FLAGS;
     }
 
     MOZ_ALWAYS_INLINE
     JSDependentString &asDependent() const {
         JS_ASSERT(isDependent());
         return *(JSDependentString *)this;
     }
 
@@ -338,17 +337,17 @@ class JSString : public js::gc::Barriere
     MOZ_ALWAYS_INLINE
     JSFlatString &asFlat() const {
         JS_ASSERT(isFlat());
         return *(JSFlatString *)this;
     }
 
     MOZ_ALWAYS_INLINE
     bool isExtensible() const {
-        return (d.lengthAndFlags & FLAGS_MASK) == EXTENSIBLE_FLAGS;
+        return (d.u0.lengthAndFlags & FLAGS_MASK) == EXTENSIBLE_FLAGS;
     }
 
     MOZ_ALWAYS_INLINE
     JSExtensibleString &asExtensible() const {
         JS_ASSERT(isExtensible());
         return *(JSExtensibleString *)this;
     }
 
@@ -371,40 +370,40 @@ class JSString : public js::gc::Barriere
     MOZ_ALWAYS_INLINE
     JSExternalString &asExternal() const {
         JS_ASSERT(isExternal());
         return *(JSExternalString *)this;
     }
 
     MOZ_ALWAYS_INLINE
     bool isUndepended() const {
-        return (d.lengthAndFlags & FLAGS_MASK) == UNDEPENDED_FLAGS;
+        return (d.u0.lengthAndFlags & FLAGS_MASK) == UNDEPENDED_FLAGS;
     }
 
     MOZ_ALWAYS_INLINE
     bool isAtom() const {
-        return d.lengthAndFlags & ATOM_BIT;
+        return d.u0.lengthAndFlags & ATOM_BIT;
     }
 
     MOZ_ALWAYS_INLINE
     bool isPermanentAtom() const {
-        return (d.lengthAndFlags & FLAGS_MASK) == PERMANENT_ATOM_FLAGS;
+        return (d.u0.lengthAndFlags & FLAGS_MASK) == PERMANENT_ATOM_FLAGS;
     }
 
     MOZ_ALWAYS_INLINE
     JSAtom &asAtom() const {
         JS_ASSERT(isAtom());
         return *(JSAtom *)this;
     }
 
     /* Only called by the GC for dependent or undepended strings. */
 
     inline bool hasBase() const {
         JS_STATIC_ASSERT((DEPENDENT_FLAGS | JS_BIT(1)) == UNDEPENDED_FLAGS);
-        return d.lengthAndFlags & HAS_BASE_BIT;
+        return d.u0.lengthAndFlags & HAS_BASE_BIT;
     }
 
     inline JSLinearString *base() const;
 
     inline void markBase(JSTracer *trc);
 
     /* Only called by the GC for strings with the FINALIZE_STRING kind. */
 
@@ -412,17 +411,17 @@ class JSString : public js::gc::Barriere
 
     /* Gets the number of bytes that the chars take on the heap. */
 
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
 
     /* Offsets for direct field from jit code. */
 
     static size_t offsetOfLengthAndFlags() {
-        return offsetof(JSString, d.lengthAndFlags);
+        return offsetof(JSString, d.u0.lengthAndFlags);
     }
 
     static size_t offsetOfChars() {
         return offsetof(JSString, d.u1.chars);
     }
 
     js::gc::AllocKind getAllocKind() const { return tenuredGetAllocKind(); }
 
@@ -589,21 +588,21 @@ class JSFlatString : public JSLinearStri
      */
     inline js::PropertyName *toPropertyName(JSContext *cx);
 
     /*
      * Once a JSFlatString sub-class has been added to the atom state, this
      * operation changes the string to the JSAtom type, in place.
      */
     MOZ_ALWAYS_INLINE JSAtom *morphAtomizedStringIntoAtom() {
-        d.lengthAndFlags = buildLengthAndFlags(length(), ATOM_BIT);
+        d.u0.lengthAndFlags = buildLengthAndFlags(length(), ATOM_BIT);
         return &asAtom();
     }
     MOZ_ALWAYS_INLINE JSAtom *morphAtomizedStringIntoPermanentAtom() {
-        d.lengthAndFlags = buildLengthAndFlags(length(), PERMANENT_ATOM_FLAGS);
+        d.u0.lengthAndFlags = buildLengthAndFlags(length(), PERMANENT_ATOM_FLAGS);
         return &asAtom();
     }
 
     inline void finalize(js::FreeOp *fop);
 };
 
 JS_STATIC_ASSERT(sizeof(JSFlatString) == sizeof(JSString));
 
@@ -735,23 +734,23 @@ class JSAtom : public JSFlatString
   public:
     /* Returns the PropertyName for this.  isIndex() must be false. */
     inline js::PropertyName *asPropertyName();
 
     inline void finalize(js::FreeOp *fop);
 
     MOZ_ALWAYS_INLINE
     bool isPermanent() const {
-        return d.lengthAndFlags & PERMANENT_BIT;
+        return d.u0.lengthAndFlags & PERMANENT_BIT;
     }
 
     // Transform this atom into a permanent atom. This is only done during
     // initialization of the runtime.
     MOZ_ALWAYS_INLINE void morphIntoPermanentAtom() {
-        d.lengthAndFlags = buildLengthAndFlags(length(), PERMANENT_ATOM_FLAGS);
+        d.u0.lengthAndFlags = buildLengthAndFlags(length(), PERMANENT_ATOM_FLAGS);
     }
 
 #ifdef DEBUG
     void dump();
 #endif
 };
 
 JS_STATIC_ASSERT(sizeof(JSAtom) == sizeof(JSString));