Bug 200505 - Optimization of jsref array_join_sub() function. r=waldo
☠☠ backed out by d69b121d3f68 ☠ ☠
authorLuke Wagner <lw@mozilla.com>
Tue, 30 Jun 2009 11:29:43 -0700
changeset 30018 b2256abf53c0f6ce601e03d23f13deaa6a7e97c0
parent 29916 1c7827f6893b122cedee91d878e4999b8a84b6c7
child 30019 31f30d06b803bc06f5ce49201676bc8c5ed2279d
child 30021 d69b121d3f680dea8521de881202c6a01bedcea4
push idunknown
push userunknown
push dateunknown
reviewerswaldo
bugs200505
milestone1.9.2a1pre
Bug 200505 - Optimization of jsref array_join_sub() function. r=waldo
js/src/jsarray.cpp
js/src/jsarray.h
js/src/jsbool.cpp
js/src/jsbool.h
js/src/jscntxt.cpp
js/src/jscntxt.h
js/src/jsdtoa.cpp
js/src/jsnum.cpp
js/src/jsnum.h
js/src/jsprvtd.h
js/src/jsstr.cpp
js/src/jsstr.h
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -94,16 +94,17 @@
 #include "jsgc.h"
 #include "jsinterp.h"
 #include "jslock.h"
 #include "jsnum.h"
 #include "jsobj.h"
 #include "jsscope.h"
 #include "jsstr.h"
 #include "jsstaticcheck.h"
+#include "jsvector.h"
 
 /* 2^32 - 1 as a number and a string */
 #define MAXINDEX 4294967295u
 #define MAXSTR   "4294967295"
 
 /* Small arrays are dense, no matter what. */
 #define MIN_SPARSE_INDEX 256
 
@@ -1296,285 +1297,302 @@ js_MakeArraySlow(JSContext *cx, JSObject
     obj->map = &scope->map;
     return JS_TRUE;
 
   out_bad:
     js_DestroyScope(cx, scope);
     return JS_FALSE;
 }
 
-enum ArrayToStringOp {
-    TO_STRING,
-    TO_LOCALE_STRING,
-    TO_SOURCE
-};
-
-/*
- * When op is TO_STRING or TO_LOCALE_STRING sep indicates a separator to use
- * or "," when sep is NULL.
- * When op is TO_SOURCE sep must be NULL.
- */
+/* Transfer ownership of buffer to returned string. */
 static JSBool
-array_join_sub(JSContext *cx, JSObject *obj, enum ArrayToStringOp op,
-               JSString *sep, jsval *rval)
+BufferToString(JSContext *cx, JSTempVector<jschar> &buf, jsval *rval)
 {
-    JSBool ok, hole;
-    jsuint length, index;
-    jschar *chars, *ochars;
-    size_t nchars, growth, seplen, tmplen, extratail;
-    const jschar *sepstr;
-    JSString *str;
-    JSHashEntry *he;
-    JSAtom *atom;
-
-    JS_CHECK_RECURSION(cx, return JS_FALSE);
-
-    ok = js_GetLengthProperty(cx, obj, &length);
-    if (!ok)
-        return JS_FALSE;
-
-    he = js_EnterSharpObject(cx, obj, NULL, &chars);
-    if (!he)
-        return JS_FALSE;
-#ifdef DEBUG
-    growth = (size_t) -1;
-#endif
-
-    /*
-     * We must check for the sharp bit and skip js_LeaveSharpObject when it is
-     * set even when op is not TO_SOURCE. A script can overwrite the default
-     * toSource implementation and trigger a call, for example, to the
-     * toString method during serialization of the object graph (bug 369696).
-     */
-    if (IS_SHARP(he)) {
-#if JS_HAS_SHARP_VARS
-        nchars = js_strlen(chars);
-#else
-        chars[0] = '[';
-        chars[1] = ']';
-        chars[2] = 0;
-        nchars = 2;
-#endif
-        goto make_string;
-    }
-
-    if (op == TO_SOURCE) {
-        /*
-         * Always allocate 2 extra chars for closing ']' and terminating 0
-         * and then preallocate 1 + extratail to include starting '['.
-         */
-        extratail = 2;
-        growth = (1 + extratail) * sizeof(jschar);
-        if (!chars) {
-            nchars = 0;
-            chars = (jschar *) malloc(growth);
-            if (!chars)
-                goto done;
-        } else {
-            MAKE_SHARP(he);
-            nchars = js_strlen(chars);
-            growth += nchars * sizeof(jschar);
-            chars = (jschar *)realloc((ochars = chars), growth);
-            if (!chars) {
-                free(ochars);
-                goto done;
-            }
-        }
-        chars[nchars++] = '[';
-        JS_ASSERT(sep == NULL);
-        sepstr = NULL;  /* indicates to use ", " as separator */
-        seplen = 2;
-    } else {
-        /*
-         * Free any sharp variable definition in chars.  Normally, we would
-         * MAKE_SHARP(he) so that only the first sharp variable annotation is
-         * a definition, and all the rest are references, but in the current
-         * case of (op != TO_SOURCE), we don't need chars at all.
-         */
-        if (chars)
-            JS_free(cx, chars);
-        chars = NULL;
-        nchars = 0;
-        extratail = 1;  /* allocate extra char for terminating 0 */
-
-        /* Return the empty string on a cycle as well as on empty join. */
-        if (IS_BUSY(he) || length == 0) {
-            js_LeaveSharpObject(cx, NULL);
-            *rval = JS_GetEmptyStringValue(cx);
-            return ok;
-        }
-
-        /* Flag he as BUSY so we can distinguish a cycle from a join-point. */
-        MAKE_BUSY(he);
-
-        if (sep) {
-            sep->getCharsAndLength(sepstr, seplen);
-        } else {
-            sepstr = NULL;      /* indicates to use "," as separator */
-            seplen = 1;
-        }
-    }
-
-    /* Use rval to locally root each element value as we loop and convert. */
-    for (index = 0; index < length; index++) {
-        ok = (JS_CHECK_OPERATION_LIMIT(cx) &&
-              GetArrayElement(cx, obj, index, &hole, rval));
-        if (!ok)
-            goto done;
-        if (hole ||
-            (op != TO_SOURCE &&
-             (JSVAL_IS_VOID(*rval) || JSVAL_IS_NULL(*rval)))) {
-            str = cx->runtime->emptyString;
-        } else {
-            if (op == TO_LOCALE_STRING) {
-                JSObject *robj;
-
-                atom = cx->runtime->atomState.toLocaleStringAtom;
-                ok = js_ValueToObject(cx, *rval, &robj);
-                if (ok) {
-                    /* Re-use *rval to protect robj temporarily. */
-                    *rval = OBJECT_TO_JSVAL(robj);
-                    ok = js_TryMethod(cx, robj, atom, 0, NULL, rval);
-                }
-                if (!ok)
-                    goto done;
-                str = js_ValueToString(cx, *rval);
-            } else if (op == TO_STRING) {
-                str = js_ValueToString(cx, *rval);
-            } else {
-                JS_ASSERT(op == TO_SOURCE);
-                str = js_ValueToSource(cx, *rval);
-            }
-            if (!str) {
-                ok = JS_FALSE;
-                goto done;
-            }
-        }
-
-        /*
-         * Do not append separator after the last element unless it is a hole
-         * and we are in toSource. In that case we append single ",".
-         */
-        if (index + 1 == length)
-            seplen = (hole && op == TO_SOURCE) ? 1 : 0;
-
-        /* Allocate 1 at end for closing bracket and zero. */
-        tmplen = str->length();
-        growth = nchars + tmplen + seplen + extratail;
-        if (nchars > growth || tmplen > growth ||
-            growth > (size_t)-1 / sizeof(jschar)) {
-            if (chars) {
-                free(chars);
-                chars = NULL;
-            }
-            goto done;
-        }
-        growth *= sizeof(jschar);
-        if (!chars) {
-            chars = (jschar *) malloc(growth);
-            if (!chars)
-                goto done;
-        } else {
-            chars = (jschar *) realloc((ochars = chars), growth);
-            if (!chars) {
-                free(ochars);
-                goto done;
-            }
-        }
-
-        js_strncpy(&chars[nchars], str->chars(), tmplen);
-        nchars += tmplen;
-
-        if (seplen) {
-            if (sepstr) {
-                js_strncpy(&chars[nchars], sepstr, seplen);
-            } else {
-                JS_ASSERT(seplen == 1 || seplen == 2);
-                chars[nchars] = ',';
-                if (seplen == 2)
-                    chars[nchars + 1] = ' ';
-            }
-            nchars += seplen;
-        }
-    }
-
-  done:
-    if (op == TO_SOURCE) {
-        if (chars)
-            chars[nchars++] = ']';
-    } else {
-        CLEAR_BUSY(he);
-    }
-    js_LeaveSharpObject(cx, NULL);
-    if (!ok) {
-        if (chars)
-            free(chars);
-        return ok;
-    }
-
-  make_string:
-    if (!chars) {
-        JS_ReportOutOfMemory(cx);
-        return JS_FALSE;
-    }
-    chars[nchars] = 0;
-    JS_ASSERT(growth == (size_t)-1 || (nchars + 1) * sizeof(jschar) == growth);
-    str = js_NewString(cx, chars, nchars);
+    size_t length = buf.size() - 1;
+    jschar *chars = buf.extractRawBuffer();
+    JSString *str = js_NewString(cx, chars, length);
     if (!str) {
-        free(chars);
+        JS_free(cx, chars);
         return JS_FALSE;
     }
     *rval = STRING_TO_JSVAL(str);
     return JS_TRUE;
 }
 
 #if JS_HAS_TOSOURCE
 static JSBool
 array_toSource(JSContext *cx, uintN argc, jsval *vp)
 {
-    JSObject *obj;
-
-    obj = JS_THIS_OBJECT(cx, vp);
-    if (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
-        !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2)) {
+    JS_CHECK_RECURSION(cx, return JS_FALSE);
+
+    JSObject *obj = JS_THIS_OBJECT(cx, vp);
+    if (!obj ||
+        (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
+         !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
         return JS_FALSE;
     }
-    return array_join_sub(cx, obj, TO_SOURCE, NULL, vp);
+
+    /* Find joins or cycles in the reachable object graph. */
+    jschar *sharpchars;
+    JSHashEntry *he = js_EnterSharpObject(cx, obj, NULL, &sharpchars);
+    if (!he)
+        return JS_FALSE;
+    JSBool initiallySharp = IS_SHARP(he) ? JS_TRUE : JS_FALSE;
+
+    /* After this point, all paths exit through the 'done' label. */
+    MUST_FLOW_THROUGH("done");
+    JSBool ok = JS_TRUE;
+
+    /*
+     * This object will takes responsibility for the jschar buffer until it is 
+     * transferred to the returned JSString.
+     */
+    JSTempVector<jschar> buf(cx);
+    if (!(ok = buf.reserve(3)))
+        goto done;
+
+    /* Cycles/joins are indicated by sharp objects. */
+#if JS_HAS_SHARP_VARS
+    if (IS_SHARP(he)) {
+        JS_ASSERT(sharpchars != 0);
+        /* +1 to include the trailing '\0' */
+        buf.replaceRawBuffer(sharpchars, js_strlen(sharpchars) + 1);
+        goto make_string;
+    } else if (sharpchars) {
+        MAKE_SHARP(he);
+        buf.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
+    }
+#else
+    if (IS_SHARP(he)) {
+        static const jschar arr[] = { '[', ']', 0 };
+        if (!(ok = buf.pushBack(arr, arr + 3)))
+            goto done;
+        if (sharpchars)
+            JS_free(cx, sharpchars);
+        goto make_string;
+    }
+#endif
+
+    if (!(ok = buf.pushBack('[')))
+        goto done;
+
+    jsuint length;
+    ok = js_GetLengthProperty(cx, obj, &length);
+    if (!ok)
+        goto done;
+
+    for (jsuint index = 0; index < length; index++) {
+        /* Use vp to locally root each element value. */
+        JSBool hole;
+        ok = (JS_CHECK_OPERATION_LIMIT(cx) &&
+              GetArrayElement(cx, obj, index, &hole, vp));
+        if (!ok)
+            goto done;
+
+        /* Get element's character string. */
+        JSString *str;
+        if (hole) {
+            str = cx->runtime->emptyString;
+        } else {
+            str = js_ValueToSource(cx, *vp);
+            if (!str) {
+                ok = JS_FALSE;
+                goto done;
+            }
+        }
+        *vp = STRING_TO_JSVAL(str);
+        const jschar *chars;
+        size_t charlen;
+        str->getCharsAndLength(chars, charlen);
+
+        /* Append element to buffer. */
+        if (!(ok = buf.pushBack(chars, chars + charlen)))
+            goto done;
+        if (index + 1 != length) {
+            if (!(ok = buf.pushBack(',')) || !(ok = buf.pushBack(' ')))
+                goto done;
+        } else if (hole) {
+            if (!(ok = buf.pushBack(',')))
+                goto done;
+        }
+    }
+
+    /* Finalize the buffer. */
+    if (!(ok = buf.pushBack(']')) || !(ok = buf.pushBack(0)))
+        goto done;
+
+  make_string:
+    if (!(ok = BufferToString(cx, buf, vp)))
+        goto done;
+
+  done:
+    if (!initiallySharp)
+        js_LeaveSharpObject(cx, NULL);
+    return ok;
 }
 #endif
 
+static JSHashNumber
+js_hash_array(const void *key)
+{
+    return (JSHashNumber)JS_PTR_TO_UINT32(key) >> JSVAL_TAGBITS;
+}
+
+JSBool
+js_InitContextBusyArrayTable(JSContext *cx)
+{
+    cx->busyArrayTable = JS_NewHashTable(4, js_hash_array, JS_CompareValues,
+                                         JS_CompareValues, NULL, NULL);
+    return cx->busyArrayTable != NULL;
+}
+
+static JSBool
+array_toString_sub(JSContext *cx, JSObject *obj, JSBool locale,
+                   JSString *sepstr, jsval *rval)
+{
+    JS_CHECK_RECURSION(cx, return JS_FALSE);
+
+    /*
+     * This hash table is shared between toString invocations and must be empty 
+     * after the root invocation completes.
+     */
+    JSHashTable *table = cx->busyArrayTable;
+
+    /*
+     * Use HashTable entry as the cycle indicator.  On first visit, create the 
+     * entry, and, when leaving, remove the entry.
+     */
+    JSHashNumber hash = js_hash_array(obj);
+    JSHashEntry **hep = JS_HashTableRawLookup(table, hash, obj);
+    JSHashEntry *he = *hep;
+    if (!he) {
+        /* Not in hash table, so not a cycle. */
+        he = JS_HashTableRawAdd(table, hep, hash, obj, NULL);
+        if (!he) {
+            JS_ReportOutOfMemory(cx);
+            return JS_FALSE;
+        }
+    } else {
+        /* Cycle, so return empty string. */
+        *rval = ATOM_KEY(cx->runtime->atomState.emptyAtom);
+        return JS_TRUE;
+    }
+
+    JSAutoTempValueRooter tvr(cx, obj);
+
+    /* After this point, all paths exit through the 'done' label. */
+    MUST_FLOW_THROUGH("done");
+    JSBool ok = JS_TRUE;
+
+    /* Get characters to use for the separator. */
+    static const jschar comma = ',';
+    const jschar *sep;
+    size_t seplen;
+    if (sepstr) {
+        sepstr->getCharsAndLength(sep, seplen);
+    } else {
+        sep = &comma;
+        seplen = 1;
+    }
+    
+    /*
+     * This object will takes responsibility for the jschar buffer until it is 
+     * transferred to the returned JSString.
+     */
+    JSTempVector<jschar> buf(cx);
+
+    jsuint length;
+    ok = js_GetLengthProperty(cx, obj, &length);
+    if (!ok)
+        goto done;
+
+    for (jsuint index = 0; index < length; index++) {
+        /* Use rval to locally root each element value. */
+        JSBool hole;
+        ok = JS_CHECK_OPERATION_LIMIT(cx) &&
+             GetArrayElement(cx, obj, index, &hole, rval);
+        if (!ok)
+            goto done;
+
+        /* Get element's character string. */
+        if (!(hole || JSVAL_IS_VOID(*rval) || JSVAL_IS_NULL(*rval))) {
+            if (locale) {
+                JSObject *robj;
+
+                JSAtom *atom = cx->runtime->atomState.toLocaleStringAtom;
+                ok = js_ValueToObject(cx, *rval, &robj);
+                if (ok) {
+                    /* Re-use *rval to protect robj temporarily. */
+                    *rval = OBJECT_TO_JSVAL(robj);
+                    ok = js_TryMethod(cx, robj, atom, 0, NULL, rval);
+                }
+                if (!ok)
+                    goto done;
+            }
+
+            ok = js_ValueToStringBuffer(cx, *rval, buf);
+            if (!ok)
+                goto done;
+        }
+
+        /* Append the separator. */
+        if (index + 1 != length) {
+            if (!(ok = buf.pushBack(sep, sep + seplen)))
+                goto done;
+        }
+    }
+
+    /* Finalize the buffer. */
+    if (buf.empty()) {
+        *rval = ATOM_KEY(cx->runtime->atomState.emptyAtom);
+        goto done;
+    } 
+
+    ok = buf.pushBack(0) &&
+         BufferToString(cx, buf, rval);
+    if (!ok)
+        goto done;
+
+  done:
+    JS_HashTableRawRemove(table, hep, he);
+    return ok;
+}
+
 static JSBool
 array_toString(JSContext *cx, uintN argc, jsval *vp)
 {
     JSObject *obj;
 
     obj = JS_THIS_OBJECT(cx, vp);
-    if (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
-        !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2)) {
+    if (!obj ||
+        (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
+         !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
         return JS_FALSE;
     }
-    return array_join_sub(cx, obj, TO_STRING, NULL, vp);
+
+    return array_toString_sub(cx, obj, JS_FALSE, NULL, vp);
 }
 
 static JSBool
 array_toLocaleString(JSContext *cx, uintN argc, jsval *vp)
 {
     JSObject *obj;
 
     obj = JS_THIS_OBJECT(cx, vp);
-    if (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
-        !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2)) {
+    if (!obj ||
+        (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
+         !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
         return JS_FALSE;
     }
 
     /*
      *  Passing comma here as the separator. Need a way to get a
      *  locale-specific version.
      */
-    return array_join_sub(cx, obj, TO_LOCALE_STRING, NULL, vp);
+    return array_toString_sub(cx, obj, JS_TRUE, NULL, vp);
 }
 
 enum TargetElementsType {
     TargetElementsAllHoles,
     TargetElementsMayContainValues
 };
 
 enum SourceVectorType {
@@ -1711,28 +1729,28 @@ InitArrayObject(JSContext *cx, JSObject 
     return JS_TRUE;
 }
 
 #ifdef JS_TRACER
 static JSString* FASTCALL
 Array_p_join(JSContext* cx, JSObject* obj, JSString *str)
 {
     JSAutoTempValueRooter tvr(cx);
-    if (!array_join_sub(cx, obj, TO_STRING, str, tvr.addr())) {
+    if (!array_toString_sub(cx, obj, JS_FALSE, str, tvr.addr())) {
         js_SetBuiltinError(cx);
         return NULL;
     }
     return JSVAL_TO_STRING(tvr.value());
 }
 
 static JSString* FASTCALL
 Array_p_toString(JSContext* cx, JSObject* obj)
 {
     JSAutoTempValueRooter tvr(cx);
-    if (!array_join_sub(cx, obj, TO_STRING, NULL, tvr.addr())) {
+    if (!array_toString_sub(cx, obj, JS_FALSE, NULL, tvr.addr())) {
         js_SetBuiltinError(cx);
         return NULL;
     }
     return JSVAL_TO_STRING(tvr.value());
 }
 #endif
 
 /*
@@ -1748,17 +1766,17 @@ array_join(JSContext *cx, uintN argc, js
         str = NULL;
     } else {
         str = js_ValueToString(cx, vp[2]);
         if (!str)
             return JS_FALSE;
         vp[2] = STRING_TO_JSVAL(str);
     }
     obj = JS_THIS_OBJECT(cx, vp);
-    return obj && array_join_sub(cx, obj, TO_STRING, str, vp);
+    return obj && array_toString_sub(cx, obj, JS_FALSE, str, vp);
 }
 
 static JSBool
 array_reverse(JSContext *cx, uintN argc, jsval *vp)
 {
     JSObject *obj;
     JSTempValueRooter tvr;
     jsuint len, half, i;
--- a/js/src/jsarray.h
+++ b/js/src/jsarray.h
@@ -92,16 +92,19 @@ static JS_INLINE JSObject *
 js_GetProtoIfDenseArray(JSContext *cx, JSObject *obj)
 {
     return OBJ_IS_DENSE_ARRAY(cx, obj) ? OBJ_GET_PROTO(cx, obj) : obj;
 }
 
 extern JSObject *
 js_InitArrayClass(JSContext *cx, JSObject *obj);
 
+extern JSBool
+js_InitContextBusyArrayTable(JSContext *);
+
 extern JSObject *
 js_NewArrayObject(JSContext *cx, jsuint length, jsval *vector,
                   JSBool holey = JS_FALSE);
 
 /* Create an array object that starts out already made slow/sparse. */
 extern JSObject *
 js_NewSlowArrayObject(JSContext *cx);
 
--- a/js/src/jsbool.cpp
+++ b/js/src/jsbool.cpp
@@ -47,16 +47,17 @@
 #include "jsatom.h"
 #include "jsbool.h"
 #include "jscntxt.h"
 #include "jsversion.h"
 #include "jslock.h"
 #include "jsnum.h"
 #include "jsobj.h"
 #include "jsstr.h"
+#include "jsvector.h"
 
 /* Check pseudo-booleans values. */
 JS_STATIC_ASSERT(!(JSVAL_TRUE & JSVAL_HOLE_FLAG));
 JS_STATIC_ASSERT(!(JSVAL_FALSE & JSVAL_HOLE_FLAG));
 JS_STATIC_ASSERT(!(JSVAL_VOID & JSVAL_HOLE_FLAG));
 JS_STATIC_ASSERT((JSVAL_HOLE & JSVAL_HOLE_FLAG));
 JS_STATIC_ASSERT((JSVAL_HOLE & ~JSVAL_HOLE_FLAG) == JSVAL_VOID);
 JS_STATIC_ASSERT(!(JSVAL_ARETURN & JSVAL_HOLE_FLAG));
@@ -157,16 +158,26 @@ js_InitBooleanClass(JSContext *cx, JSObj
 }
 
 JSString *
 js_BooleanToString(JSContext *cx, JSBool b)
 {
     return ATOM_TO_STRING(cx->runtime->atomState.booleanAtoms[b ? 1 : 0]);
 }
 
+/* This function implements E-262-3 section 9.8, toString. */
+JSBool
+js_BooleanToStringBuffer(JSContext *cx, JSBool b, JSTempVector<jschar> &buf) 
+{
+    static const jschar trueChars[] = { 't', 'r', 'u', 'e' },
+                        falseChars[] = { 'f', 'a', 'l', 's', 'e' };
+    return b ? buf.pushBack(trueChars, trueChars + JS_ARRAY_LENGTH(trueChars))
+             : buf.pushBack(falseChars, falseChars + JS_ARRAY_LENGTH(falseChars));
+}
+
 JSBool
 js_ValueToBoolean(jsval v)
 {
     if (JSVAL_IS_NULL(v) || JSVAL_IS_VOID(v))
         return JS_FALSE;
     if (JSVAL_IS_OBJECT(v))
         return JS_TRUE;
     if (JSVAL_IS_STRING(v))
--- a/js/src/jsbool.h
+++ b/js/src/jsbool.h
@@ -76,13 +76,16 @@ extern JSClass js_BooleanClass;
 
 extern JSObject *
 js_InitBooleanClass(JSContext *cx, JSObject *obj);
 
 extern JSString *
 js_BooleanToString(JSContext *cx, JSBool b);
 
 extern JSBool
+js_BooleanToStringBuffer(JSContext *cx, JSBool b, JSTempVector<jschar> &buf);
+
+extern JSBool
 js_ValueToBoolean(jsval v);
 
 JS_END_EXTERN_C
 
 #endif /* jsbool_h___ */
--- a/js/src/jscntxt.cpp
+++ b/js/src/jscntxt.cpp
@@ -382,16 +382,21 @@ js_NewContext(JSRuntime *rt, size_t stac
 
     JS_INIT_ARENA_POOL(&cx->tempPool, "temp",
                        1024,  /* FIXME: bug 421435 */
                        sizeof(jsdouble), &cx->scriptStackQuota);
 
     js_InitRegExpStatics(cx);
     JS_ASSERT(cx->resolveFlags == 0);
 
+    if (!js_InitContextBusyArrayTable(cx)) {
+        FreeContext(cx);
+        return NULL;
+    }
+
 #ifdef JS_THREADSAFE
     if (!js_InitContextThread(cx)) {
         FreeContext(cx);
         return NULL;
     }
 #endif
 
     /*
@@ -738,16 +743,22 @@ FreeContext(JSContext *cx)
     /* Remove any argument formatters. */
     map = cx->argumentFormatMap;
     while (map) {
         JSArgumentFormatMap *temp = map;
         map = map->next;
         JS_free(cx, temp);
     }
 
+    /* Destroy the busy array table. */
+    if (cx->busyArrayTable) {
+        JS_HashTableDestroy(cx->busyArrayTable);
+        cx->busyArrayTable = NULL;
+    }
+
     /* Destroy the resolve recursion damper. */
     if (cx->resolvingTable) {
         JS_DHashTableDestroy(cx->resolvingTable);
         cx->resolvingTable = NULL;
     }
 
     lrs = cx->localRootStack;
     if (lrs) {
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -51,16 +51,17 @@
 #include "jsdhash.h"
 #include "jsgc.h"
 #include "jsinterp.h"
 #include "jsobj.h"
 #include "jsprvtd.h"
 #include "jspubtd.h"
 #include "jsregexp.h"
 #include "jsutil.h"
+#include "jsarray.h"
 
 JS_BEGIN_EXTERN_C
 
 /*
  * js_GetSrcNote cache to avoid O(n^2) growth in finding a source note for a
  * given pc in a script. We use the script->code pointer to tag the cache,
  * instead of the script address itself, so that source notes are always found
  * by offset from the bytecode with which they were generated.
@@ -950,16 +951,17 @@ struct JSContext {
     /* Storage to root recently allocated GC things and script result. */
     JSWeakRoots         weakRoots;
 
     /* Regular expression class statics (XXX not shared globally). */
     JSRegExpStatics     regExpStatics;
 
     /* State for object and array toSource conversion. */
     JSSharpObjectMap    sharpObjectMap;
+    JSHashTable         *busyArrayTable;
 
     /* Argument formatter support for JS_{Convert,Push}Arguments{,VA}. */
     JSArgumentFormatMap *argumentFormatMap;
 
     /* Last message string and trace file for debugging. */
     char                *lastMessage;
 #ifdef DEBUG
     void                *tracefp;
--- a/js/src/jsdtoa.cpp
+++ b/js/src/jsdtoa.cpp
@@ -41,17 +41,17 @@
  * Portable double to alphanumeric string and back converters.
  */
 #include "jslibmath.h"
 #include "jstypes.h"
 #include "jsstdint.h"
 #include "jsdtoa.h"
 #include "jsprf.h"
 #include "jsutil.h" /* Added by JSIFY */
-#include "jspubtd.h"
+#include "jsprvtd.h"
 #include "jsnum.h"
 #include "jsbit.h"
 
 #ifdef JS_THREADSAFE
 #include "jslock.h"
 #endif
 
 #ifdef IS_LITTLE_ENDIAN
--- a/js/src/jsnum.cpp
+++ b/js/src/jsnum.cpp
@@ -66,16 +66,17 @@
 #include "jsgc.h"
 #include "jsinterp.h"
 #include "jsnum.h"
 #include "jsobj.h"
 #include "jsopcode.h"
 #include "jsprf.h"
 #include "jsscope.h"
 #include "jsstr.h"
+#include "jsvector.h"
 
 static JSBool
 num_isNaN(JSContext *cx, uintN argc, jsval *vp)
 {
     jsdouble x;
 
     if (argc == 0) {
         *vp = JSVAL_TRUE;
@@ -856,16 +857,51 @@ NumberToStringWithBase(JSContext *cx, js
 }
 
 JSString * JS_FASTCALL
 js_NumberToString(JSContext *cx, jsdouble d)
 {
     return NumberToStringWithBase(cx, d, 10);
 }
 
+JSBool JS_FASTCALL
+js_NumberValueToStringBuffer(JSContext *cx, jsval v, JSTempVector<jschar> &buf)
+{
+    /* Convert to C-string. */
+    static const size_t arrSize = DTOSTR_STANDARD_BUFFER_SIZE;
+    char arr[arrSize];
+    const char *cstr;
+    if (JSVAL_IS_INT(v)) {
+        cstr = IntToCString(JSVAL_TO_INT(v), 10, arr, arrSize);
+    } else {
+        JS_ASSERT(JSVAL_IS_DOUBLE(v));
+        cstr = JS_dtostr(arr, arrSize, DTOSTR_STANDARD, 0, *JSVAL_TO_DOUBLE(v));
+    }
+    if (!cstr)
+        return JS_FALSE;
+
+    /*
+     * Inflate to jschar string.  The input C-string characters are < 127, so 
+     * even if jschars are UTF-8, all chars should map to one jschar.
+     */
+    size_t cstrlen = strlen(cstr);
+    JS_ASSERT(cstrlen < arrSize);
+    size_t sizeBefore = buf.size();
+    if (!buf.growBy(cstrlen))
+        return JS_FALSE;
+    jschar *appendBegin = buf.begin() + sizeBefore;
+#ifdef DEBUG
+    size_t oldcstrlen = cstrlen;
+    JSBool ok = 
+#endif
+        js_InflateStringToBuffer(cx, cstr, cstrlen, appendBegin, &cstrlen);
+    JS_ASSERT(ok && cstrlen == oldcstrlen);
+    return JS_TRUE;
+}
+
 jsdouble
 js_ValueToNumber(JSContext *cx, jsval *vp)
 {
     jsval v;
     JSString *str;
     const jschar *bp, *end, *ep;
     jsdouble d, *dp;
     JSObject *obj;
--- a/js/src/jsnum.h
+++ b/js/src/jsnum.h
@@ -184,16 +184,23 @@ js_NewNumberInRootedValue(JSContext *cx,
  */
 extern JSBool
 js_NewWeaklyRootedNumber(JSContext *cx, jsdouble d, jsval *vp);
 
 /* Convert a number to a GC'ed string. */
 extern JSString * JS_FASTCALL
 js_NumberToString(JSContext *cx, jsdouble d);
 
+/* 
+ * Convert an integer or double (contained in the given jsval) to a string and 
+ * append to the given buffer.
+ */
+extern JSBool JS_FASTCALL
+js_NumberValueToStringBuffer(JSContext *, jsval, JSTempVector<jschar> &);
+
 /*
  * Convert a value to a number. On exit JSVAL_IS_NULL(*vp) iff there was an
  * error. If on exit JSVAL_IS_NUMBER(*vp), then *vp holds the jsval that
  * matches the result. Otherwise *vp is JSVAL_TRUE indicating that the jsval
  * for result has to be created explicitly using, for example, the
  * js_NewNumberInRootedValue function.
  */
 extern jsdouble
--- a/js/src/jsprvtd.h
+++ b/js/src/jsprvtd.h
@@ -129,16 +129,19 @@ typedef struct JSScopeProperty      JSSc
 typedef struct JSStackHeader        JSStackHeader;
 typedef struct JSStringBuffer       JSStringBuffer;
 typedef struct JSSubString          JSSubString;
 typedef struct JSTraceableNative    JSTraceableNative;
 typedef struct JSXML                JSXML;
 typedef struct JSXMLArray           JSXMLArray;
 typedef struct JSXMLArrayCursor     JSXMLArrayCursor;
 
+/* Template forward declarations. */
+template <class T> class JSTempVector;
+
 /* "Friend" types used by jscntxt.h and jsdbgapi.h. */
 typedef enum JSTrapStatus {
     JSTRAP_ERROR,
     JSTRAP_CONTINUE,
     JSTRAP_RETURN,
     JSTRAP_THROW,
     JSTRAP_LIMIT
 } JSTrapStatus;
--- a/js/src/jsstr.cpp
+++ b/js/src/jsstr.cpp
@@ -68,16 +68,17 @@
 #include "jsnum.h"
 #include "jsobj.h"
 #include "jsopcode.h"
 #include "jsregexp.h"
 #include "jsscope.h"
 #include "jsstaticcheck.h"
 #include "jsstr.h"
 #include "jsbit.h"
+#include "jsvector.h"
 
 #define JSSTRDEP_RECURSION_LIMIT        100
 
 static size_t
 MinimizeDependentStrings(JSString *str, int level, JSString **basep)
 {
     JSString *base;
     size_t start, length;
@@ -241,45 +242,46 @@ js_MakeStringImmutable(JSContext *cx, JS
     }
     str->flatClearMutable();
     return JS_TRUE;
 }
 
 static JSString *
 ArgToRootedString(JSContext *cx, uintN argc, jsval *vp, uintN arg)
 {
-    JSObject *obj;
-    JSString *str;
-
     if (arg >= argc)
         return ATOM_TO_STRING(cx->runtime->atomState.typeAtoms[JSTYPE_VOID]);
     vp += 2 + arg;
 
-    if (JSVAL_IS_OBJECT(*vp)) {
-        obj = JSVAL_TO_OBJECT(*vp);
-        if (!obj)
-            return ATOM_TO_STRING(cx->runtime->atomState.nullAtom);
-        if (!OBJ_DEFAULT_VALUE(cx, obj, JSTYPE_STRING, vp))
-            return NULL;
+    if (!JSVAL_IS_PRIMITIVE(*vp) &&
+        !OBJ_DEFAULT_VALUE(cx, JSVAL_TO_OBJECT(*vp), JSTYPE_STRING, vp)) {
+        return NULL;
     }
-    if (JSVAL_IS_STRING(*vp))
-        return JSVAL_TO_STRING(*vp);
-    if (JSVAL_IS_INT(*vp)) {
-        str = js_NumberToString(cx, JSVAL_TO_INT(*vp));
-    } else if (JSVAL_IS_DOUBLE(*vp)) {
-        str = js_NumberToString(cx, *JSVAL_TO_DOUBLE(*vp));
+
+    JSString *str;
+    if (JSVAL_IS_STRING(*vp)) {
+        str = JSVAL_TO_STRING(*vp);
     } else if (JSVAL_IS_BOOLEAN(*vp)) {
-        return ATOM_TO_STRING(cx->runtime->atomState.booleanAtoms[
+        str = ATOM_TO_STRING(cx->runtime->atomState.booleanAtoms[
                                   JSVAL_TO_BOOLEAN(*vp)? 1 : 0]);
-    } else {
-        JS_ASSERT(JSVAL_IS_VOID(*vp));
-        return ATOM_TO_STRING(cx->runtime->atomState.typeAtoms[JSTYPE_VOID]);
+    } else if (JSVAL_IS_NULL(*vp)) {
+        str = ATOM_TO_STRING(cx->runtime->atomState.nullAtom);
+    } else if (JSVAL_IS_VOID(*vp)) {
+        str = ATOM_TO_STRING(cx->runtime->atomState.typeAtoms[JSTYPE_VOID]);
     }
-    if (str)
-        *vp = STRING_TO_JSVAL(str);
+    else {
+        if (JSVAL_IS_INT(*vp)) {
+            str = js_NumberToString(cx, JSVAL_TO_INT(*vp));
+        } else {
+            JS_ASSERT(JSVAL_IS_DOUBLE(*vp));
+            str = js_NumberToString(cx, *JSVAL_TO_DOUBLE(*vp));
+        }
+        if (str)
+            *vp = STRING_TO_JSVAL(str);
+    }
     return str;
 }
 
 /*
  * Forward declarations for URI encode/decode and helper routines
  */
 static JSBool
 str_decodeURI(JSContext *cx, uintN argc, jsval *vp);
@@ -2961,40 +2963,75 @@ js_ValueToPrintable(JSContext *cx, jsval
     if (!str)
         return NULL;
     return js_GetStringBytes(cx, str);
 }
 
 JS_FRIEND_API(JSString *)
 js_ValueToString(JSContext *cx, jsval v)
 {
-    JSObject *obj;
     JSString *str;
 
-    if (JSVAL_IS_OBJECT(v)) {
-        obj = JSVAL_TO_OBJECT(v);
-        if (!obj)
-            return ATOM_TO_STRING(cx->runtime->atomState.nullAtom);
-        if (!OBJ_DEFAULT_VALUE(cx, obj, JSTYPE_STRING, &v))
-            return NULL;
+    if (!JSVAL_IS_PRIMITIVE(v) &&
+        !OBJ_DEFAULT_VALUE(cx, JSVAL_TO_OBJECT(v), JSTYPE_STRING, &v)) {
+        return NULL;
     }
+
     if (JSVAL_IS_STRING(v)) {
         str = JSVAL_TO_STRING(v);
     } else if (JSVAL_IS_INT(v)) {
         str = js_NumberToString(cx, JSVAL_TO_INT(v));
     } else if (JSVAL_IS_DOUBLE(v)) {
         str = js_NumberToString(cx, *JSVAL_TO_DOUBLE(v));
     } else if (JSVAL_IS_BOOLEAN(v)) {
         str = js_BooleanToString(cx, JSVAL_TO_BOOLEAN(v));
+    } else if (JSVAL_IS_NULL(v)) {
+        str = ATOM_TO_STRING(cx->runtime->atomState.nullAtom);
     } else {
         str = ATOM_TO_STRING(cx->runtime->atomState.typeAtoms[JSTYPE_VOID]);
     }
     return str;
 }
 
+static inline JSBool 
+pushAtom(JSAtom *atom, JSTempVector<jschar> &buf)
+{
+    JSString *str = ATOM_TO_STRING(atom);
+    const jschar *chars;
+    size_t length;
+    str->getCharsAndLength(chars, length);
+    return buf.pushBack(chars, chars + length);
+}
+
+/* This function implements E-262-3 section 9.8, toString. */
+JS_FRIEND_API(JSBool)
+js_ValueToStringBuffer(JSContext *cx, jsval v, JSTempVector<jschar> &buf)
+{
+    if (!JSVAL_IS_PRIMITIVE(v) &&
+        !OBJ_DEFAULT_VALUE(cx, JSVAL_TO_OBJECT(v), JSTYPE_STRING, &v)) {
+        return JS_FALSE;
+    }
+
+    if (JSVAL_IS_STRING(v)) {
+        JSString *str = JSVAL_TO_STRING(v);
+        const jschar *chars;
+        size_t length;
+        str->getCharsAndLength(chars, length);
+        return buf.pushBack(chars, chars + length);
+    } 
+    if (JSVAL_IS_NUMBER(v))
+        return js_NumberValueToStringBuffer(cx, v, buf);
+    if (JSVAL_IS_BOOLEAN(v))
+        return js_BooleanToStringBuffer(cx, JSVAL_TO_BOOLEAN(v), buf);
+    if (JSVAL_IS_NULL(v))
+        return pushAtom(cx->runtime->atomState.nullAtom, buf);
+    JS_ASSERT(JSVAL_IS_VOID(v));
+    return pushAtom(cx->runtime->atomState.typeAtoms[JSTYPE_VOID], buf);
+}
+
 JS_FRIEND_API(JSString *)
 js_ValueToSource(JSContext *cx, jsval v)
 {
     JSTempValueRooter tvr;
     JSString *str;
 
     if (JSVAL_IS_VOID(v))
         return ATOM_TO_STRING(cx->runtime->atomState.void0Atom);
--- a/js/src/jsstr.h
+++ b/js/src/jsstr.h
@@ -598,16 +598,24 @@ js_ValueToPrintable(JSContext *cx, jsval
 /*
  * Convert a value to a string, returning null after reporting an error,
  * otherwise returning a new string reference.
  */
 extern JS_FRIEND_API(JSString *)
 js_ValueToString(JSContext *cx, jsval v);
 
 /*
+ * This function implements E-262-3 section 9.8, toString.  Convert the given 
+ * value to a string of jschars appended to the given buffer.  On error, the 
+ * passed buffer may have partial results appended.
+ */
+extern JS_FRIEND_API(JSBool)
+js_ValueToStringBuffer(JSContext *, jsval, JSTempVector<jschar> &);
+
+/*
  * Convert a value to its source expression, returning null after reporting
  * an error, otherwise returning a new string reference.
  */
 extern JS_FRIEND_API(JSString *)
 js_ValueToSource(JSContext *cx, jsval v);
 
 /*
  * Compute a hash function from str. The caller can call this function even if