trunk/js/jsarray.cpp

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set sw=4 ts=8 et tw=78:
 *
 * ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is Mozilla Communicator client code, released
 * March 31, 1998.
 *
 * The Initial Developer of the Original Code is
 * Netscape Communications Corporation.
 * Portions created by the Initial Developer are Copyright (C) 1998
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either of the GNU General Public License Version 2 or later (the "GPL"),
 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

/*
 * JS array class.
 *
 * Array objects begin as "dense" arrays, optimized for index-only property
 * access over a vector of slots (obj->dslots) with high load factor.  Array
 * methods optimize for denseness by testing that the object's class is
 * &js_ArrayClass, and can then directly manipulate the slots for efficiency.
 *
 * We track these pieces of metadata for arrays in dense mode:
 *  - the array's length property as a uint32, in JSSLOT_ARRAY_LENGTH,
 *  - the number of indices that are filled (non-holes), in JSSLOT_ARRAY_COUNT,
 *  - the net number of slots starting at dslots (capacity), in dslots[-1] if
 *    dslots is non-NULL.
 *
 * In dense mode, holes in the array are represented by JSVAL_HOLE.  The final
 * slot in fslots is unused.
 *
 * NB: the capacity and length of a dense array are entirely unrelated!  The
 * length may be greater than, less than, or equal to the capacity.  See
 * array_length_setter for an explanation of how the first, most surprising
 * case may occur.
 *
 * Arrays are converted to use js_SlowArrayClass when any of these conditions
 * are met:
 *  - the load factor (COUNT / capacity) is less than 0.25, and there are
 *    more than MIN_SPARSE_INDEX slots total
 *  - a property is set that is not indexed (and not "length"); or
 *  - a property is defined that has non-default property attributes.
 *
 * Dense arrays do not track property creation order, so unlike other native
 * objects and slow arrays, enumerating an array does not necessarily visit the
 * properties in the order they were created.  We could instead maintain the
 * scope to track property enumeration order, but still use the fast slot
 * access.  That would have the same memory cost as just using a
 * js_SlowArrayClass, but have the same performance characteristics as a dense
 * array for slot accesses, at some cost in code complexity.
 */
#include <stdlib.h>
#include <string.h>
#include "jstypes.h"
#include "jsstdint.h"
#include "jsutil.h" /* Added by JSIFY */
#include "jsapi.h"
#include "jsarray.h"
#include "jsatom.h"
#include "jsbit.h"
#include "jsbool.h"
#include "jstracer.h"
#include "jsbuiltins.h"
#include "jscntxt.h"
#include "jsversion.h"
#include "jsdbgapi.h" /* for js_TraceWatchPoints */
#include "jsdtoa.h"
#include "jsfun.h"
#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"

#include "jsatominlines.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

static inline bool
INDEX_TOO_BIG(jsuint index)
{
    return index > JS_BIT(29) - 1;
}

#define INDEX_TOO_SPARSE(array, index)                                         \
    (INDEX_TOO_BIG(index) ||                                                   \
     ((index) > js_DenseArrayCapacity(array) && (index) >= MIN_SPARSE_INDEX && \
      (index) > (uint32)((array)->fslots[JSSLOT_ARRAY_COUNT] + 1) * 4))

JS_STATIC_ASSERT(sizeof(JSScopeProperty) > 4 * sizeof(jsval));

#define ENSURE_SLOW_ARRAY(cx, obj)                                             \
    (OBJ_GET_CLASS(cx, obj) == &js_SlowArrayClass || js_MakeArraySlow(cx, obj))

/*
 * Determine if the id represents an array index or an XML property index.
 *
 * An id is an array index according to ECMA by (15.4):
 *
 * "Array objects give special treatment to a certain class of property names.
 * A property name P (in the form of a string value) is an array index if and
 * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
 * to 2^32-1."
 *
 * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
 * except that by using signed 32-bit integers we miss the top half of the
 * valid range. This function checks the string representation itself; note
 * that calling a standard conversion routine might allow strings such as
 * "08" or "4.0" as array indices, which they are not.
 */
JSBool
js_IdIsIndex(jsval id, jsuint *indexp)
{
    JSString *str;
    jschar *cp;

    if (JSVAL_IS_INT(id)) {
        jsint i;
        i = JSVAL_TO_INT(id);
        if (i < 0)
            return JS_FALSE;
        *indexp = (jsuint)i;
        return JS_TRUE;
    }

    /* NB: id should be a string, but jsxml.c may call us with an object id. */
    if (!JSVAL_IS_STRING(id))
        return JS_FALSE;

    str = JSVAL_TO_STRING(id);
    cp = str->chars();
    if (JS7_ISDEC(*cp) && str->length() < sizeof(MAXSTR)) {
        jsuint index = JS7_UNDEC(*cp++);
        jsuint oldIndex = 0;
        jsuint c = 0;
        if (index != 0) {
            while (JS7_ISDEC(*cp)) {
                oldIndex = index;
                c = JS7_UNDEC(*cp);
                index = 10*index + c;
                cp++;
            }
        }

        /* Ensure that all characters were consumed and we didn't overflow. */
        if (*cp == 0 &&
             (oldIndex < (MAXINDEX / 10) ||
              (oldIndex == (MAXINDEX / 10) && c < (MAXINDEX % 10))))
        {
            *indexp = index;
            return JS_TRUE;
        }
    }
    return JS_FALSE;
}

static jsuint
ValueIsLength(JSContext *cx, jsval* vp)
{
    jsint i;
    jsdouble d;
    jsuint length;

    if (JSVAL_IS_INT(*vp)) {
        i = JSVAL_TO_INT(*vp);
        if (i < 0)
            goto error;
        return (jsuint) i;
    }

    d = js_ValueToNumber(cx, vp);
    if (JSVAL_IS_NULL(*vp))
        goto error;

    if (JSDOUBLE_IS_NaN(d))
        goto error;
    length = (jsuint) d;
    if (d != (jsdouble) length)
        goto error;
    return length;

  error:
    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
                         JSMSG_BAD_ARRAY_LENGTH);
    *vp = JSVAL_NULL;
    return 0;
}

JSBool
js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
{
    if (OBJ_IS_ARRAY(cx, obj)) {
        *lengthp = obj->fslots[JSSLOT_ARRAY_LENGTH];
        return JS_TRUE;
    }

    JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
    if (!obj->getProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.lengthAtom), tvr.addr()))
        return JS_FALSE;

    if (JSVAL_IS_INT(tvr.value())) {
        *lengthp = jsuint(jsint(JSVAL_TO_INT(tvr.value()))); /* jsuint cast does ToUint32 */
        return JS_TRUE;
    }

    *lengthp = js_ValueToECMAUint32(cx, tvr.addr());
    return !JSVAL_IS_NULL(tvr.value());
}

static JSBool
IndexToValue(JSContext *cx, jsdouble index, jsval *vp)
{
    return js_NewWeaklyRootedNumber(cx, index, vp);
}

JSBool JS_FASTCALL
js_IndexToId(JSContext *cx, jsuint index, jsid *idp)
{
    JSString *str;

    if (index <= JSVAL_INT_MAX) {
        *idp = INT_TO_JSID(index);
        return JS_TRUE;
    }
    str = js_NumberToString(cx, index);
    if (!str)
        return JS_FALSE;
    return js_ValueToStringId(cx, STRING_TO_JSVAL(str), idp);
}

static JSBool
BigIndexToId(JSContext *cx, JSObject *obj, jsuint index, JSBool createAtom,
             jsid *idp)
{
    jschar buf[10], *start;
    JSClass *clasp;
    JSAtom *atom;
    JS_STATIC_ASSERT((jsuint)-1 == 4294967295U);

    JS_ASSERT(index > JSVAL_INT_MAX);

    start = JS_ARRAY_END(buf);
    do {
        --start;
        *start = (jschar)('0' + index % 10);
        index /= 10;
    } while (index != 0);

    /*
     * Skip the atomization if the class is known to store atoms corresponding
     * to big indexes together with elements. In such case we know that the
     * array does not have an element at the given index if its atom does not
     * exist.  Fast arrays (clasp == &js_ArrayClass) don't use atoms for
     * any indexes, though it would be rare to see them have a big index
     * in any case.
     */
    if (!createAtom &&
        ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_SlowArrayClass ||
         clasp == &js_ArgumentsClass ||
         clasp == &js_ObjectClass)) {
        atom = js_GetExistingStringAtom(cx, start, JS_ARRAY_END(buf) - start);
        if (!atom) {
            *idp = JSVAL_VOID;
            return JS_TRUE;
        }
    } else {
        atom = js_AtomizeChars(cx, start, JS_ARRAY_END(buf) - start, 0);
        if (!atom)
            return JS_FALSE;
    }

    *idp = ATOM_TO_JSID(atom);
    return JS_TRUE;
}

static JSBool
ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 newlen,
            bool initializeAllSlots = true)
{
    jsval *slots, *newslots;

    if (newlen == 0) {
        if (obj->dslots) {
            cx->free(obj->dslots - 1);
            obj->dslots = NULL;
        }
        return JS_TRUE;
    }

    if (newlen > MAX_DSLOTS_LENGTH) {
        js_ReportAllocationOverflow(cx);
        return JS_FALSE;
    }

    slots = obj->dslots ? obj->dslots - 1 : NULL;
    newslots = (jsval *) cx->realloc(slots, (size_t(newlen) + 1) * sizeof(jsval));
    if (!newslots)
        return JS_FALSE;

    obj->dslots = newslots + 1;
    js_SetDenseArrayCapacity(obj, newlen);

    if (initializeAllSlots) {
        for (slots = obj->dslots + oldlen; slots < obj->dslots + newlen; slots++)
            *slots = JSVAL_HOLE;
    }

    return JS_TRUE;
}

/*
 * When a dense array with CAPACITY_DOUBLING_MAX or fewer slots needs to grow,
 * double its capacity, to push() N elements in amortized O(N) time.
 *
 * Above this limit, grow by 12.5% each time. Speed is still amortized O(N),
 * with a higher constant factor, and we waste less space.
 */
#define CAPACITY_DOUBLING_MAX    (1024 * 1024)

/*
 * Round up all large allocations to a multiple of this (1MB), so as not to
 * waste space if malloc gives us 1MB-sized chunks (as jemalloc does).
 */
#define CAPACITY_CHUNK  (1024 * 1024 / sizeof(jsval))

static JSBool
EnsureCapacity(JSContext *cx, JSObject *obj, uint32 newcap,
               bool initializeAllSlots = true)
{
    uint32 oldcap = js_DenseArrayCapacity(obj);

    if (newcap > oldcap) {
        /*
         * If this overflows uint32, newcap is very large. nextsize will end
         * up being less than newcap, the code below will thus disregard it,
         * and ResizeSlots will fail.
         *
         * The way we use dslots[-1] forces a few +1s and -1s here. For
         * example, (oldcap * 2 + 1) produces the sequence 7, 15, 31, 63, ...
         * which makes the total allocation size (with dslots[-1]) a power
         * of two.
         */
        uint32 nextsize = (oldcap <= CAPACITY_DOUBLING_MAX)
                          ? oldcap * 2 + 1
                          : oldcap + (oldcap >> 3);

        uint32 actualCapacity = JS_MAX(newcap, nextsize);
        if (actualCapacity >= CAPACITY_CHUNK)
            actualCapacity = JS_ROUNDUP(actualCapacity + 1, CAPACITY_CHUNK) - 1; /* -1 for dslots[-1] */
        else if (actualCapacity < ARRAY_CAPACITY_MIN)
            actualCapacity = ARRAY_CAPACITY_MIN;
        if (!ResizeSlots(cx, obj, oldcap, actualCapacity, initializeAllSlots))
            return JS_FALSE;
        if (!initializeAllSlots) {
            /*
             * Initialize the slots caller didn't actually ask for.
             */
            for (jsval *slots = obj->dslots + newcap;
                 slots < obj->dslots + actualCapacity;
                 slots++) {
                *slots = JSVAL_HOLE;
            }
        }
    }
    return JS_TRUE;
}

static bool
ReallyBigIndexToId(JSContext* cx, jsdouble index, jsid* idp)
{
    JSAutoTempValueRooter dval(cx);
    if (!js_NewDoubleInRootedValue(cx, index, dval.addr()) ||
        !js_ValueToStringId(cx, dval.value(), idp)) {
        return JS_FALSE;
    }
    return JS_TRUE;
}

static bool
IndexToId(JSContext* cx, JSObject* obj, jsdouble index, JSBool* hole, jsid* idp,
          JSBool createAtom = JS_FALSE)
{
    if (index <= JSVAL_INT_MAX) {
        *idp = INT_TO_JSID(index);
        return JS_TRUE;
    }

    if (index <= jsuint(-1)) {
        if (!BigIndexToId(cx, obj, jsuint(index), createAtom, idp))
            return JS_FALSE;
        if (hole && JSVAL_IS_VOID(*idp))
            *hole = JS_TRUE;
        return JS_TRUE;
    }

    return ReallyBigIndexToId(cx, index, idp);
}

/*
 * If the property at the given index exists, get its value into location
 * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
 * to JSVAL_VOID. This function assumes that the location pointed by vp is
 * properly rooted and can be used as GC-protected storage for temporaries.
 */
static JSBool
GetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole,
                jsval *vp)
{
    JS_ASSERT(index >= 0);
    if (OBJ_IS_DENSE_ARRAY(cx, obj) && index < js_DenseArrayCapacity(obj) &&
        (*vp = obj->dslots[jsuint(index)]) != JSVAL_HOLE) {
        *hole = JS_FALSE;
        return JS_TRUE;
    }

    JSAutoTempIdRooter idr(cx);

    *hole = JS_FALSE;
    if (!IndexToId(cx, obj, index, hole, idr.addr()))
        return JS_FALSE;
    if (*hole) {
        *vp = JSVAL_VOID;
        return JS_TRUE;
    }

    JSObject *obj2;
    JSProperty *prop;
    if (!obj->lookupProperty(cx, idr.id(), &obj2, &prop))
        return JS_FALSE;
    if (!prop) {
        *hole = JS_TRUE;
        *vp = JSVAL_VOID;
    } else {
        obj2->dropProperty(cx, prop);
        if (!obj->getProperty(cx, idr.id(), vp))
            return JS_FALSE;
        *hole = JS_FALSE;
    }
    return JS_TRUE;
}

/*
 * Set the value of the property at the given index to v assuming v is rooted.
 */
static JSBool
SetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, jsval v)
{
    JS_ASSERT(index >= 0);

    if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
        /* Predicted/prefetched code should favor the remains-dense case. */
        if (index <= jsuint(-1)) {
            jsuint idx = jsuint(index);
            if (!INDEX_TOO_SPARSE(obj, idx)) {
                JS_ASSERT(idx + 1 > idx);
                if (!EnsureCapacity(cx, obj, idx + 1))
                    return JS_FALSE;
                if (idx >= uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]))
                    obj->fslots[JSSLOT_ARRAY_LENGTH] = idx + 1;
                if (obj->dslots[idx] == JSVAL_HOLE)
                    obj->fslots[JSSLOT_ARRAY_COUNT]++;
                obj->dslots[idx] = v;
                return JS_TRUE;
            }
        }

        if (!js_MakeArraySlow(cx, obj))
            return JS_FALSE;
    }

    JSAutoTempIdRooter idr(cx);

    if (!IndexToId(cx, obj, index, NULL, idr.addr(), JS_TRUE))
        return JS_FALSE;
    JS_ASSERT(!JSVAL_IS_VOID(idr.id()));

    return obj->setProperty(cx, idr.id(), &v);
}

static JSBool
DeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index)
{
    JS_ASSERT(index >= 0);
    if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
        if (index <= jsuint(-1)) {
            jsuint idx = jsuint(index);
            if (!INDEX_TOO_SPARSE(obj, idx) && idx < js_DenseArrayCapacity(obj)) {
                if (obj->dslots[idx] != JSVAL_HOLE)
                    obj->fslots[JSSLOT_ARRAY_COUNT]--;
                obj->dslots[idx] = JSVAL_HOLE;
                return JS_TRUE;
            }
        }
        return JS_TRUE;
    }

    JSAutoTempIdRooter idr(cx);

    if (!IndexToId(cx, obj, index, NULL, idr.addr()))
        return JS_FALSE;
    if (JSVAL_IS_VOID(idr.id()))
        return JS_TRUE;

    jsval junk;
    return obj->deleteProperty(cx, idr.id(), &junk);
}

/*
 * When hole is true, delete the property at the given index. Otherwise set
 * its value to v assuming v is rooted.
 */
static JSBool
SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index,
                        JSBool hole, jsval v)
{
    if (hole) {
        JS_ASSERT(JSVAL_IS_VOID(v));
        return DeleteArrayElement(cx, obj, index);
    }
    return SetArrayElement(cx, obj, index, v);
}

JSBool
js_SetLengthProperty(JSContext *cx, JSObject *obj, jsdouble length)
{
    jsval v;
    jsid id;

    if (!IndexToValue(cx, length, &v))
        return JS_FALSE;
    id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
    return obj->setProperty(cx, id, &v);
}

JSBool
js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
{
    JSErrorReporter older = JS_SetErrorReporter(cx, NULL);
    JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
    jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
    JSBool ok = obj->getProperty(cx, id, tvr.addr());
    JS_SetErrorReporter(cx, older);
    if (!ok)
        return false;

    *lengthp = ValueIsLength(cx, tvr.addr());
    return !JSVAL_IS_NULL(tvr.value());
}

JSBool
js_IsArrayLike(JSContext *cx, JSObject *obj, JSBool *answerp, jsuint *lengthp)
{
    JSClass *clasp;

    clasp = OBJ_GET_CLASS(cx, js_GetWrappedObject(cx, obj));
    *answerp = (clasp == &js_ArgumentsClass || clasp == &js_ArrayClass ||
                clasp == &js_SlowArrayClass);
    if (!*answerp) {
        *lengthp = 0;
        return JS_TRUE;
    }
    return js_GetLengthProperty(cx, obj, lengthp);
}

/*
 * The 'length' property of all native Array instances is a shared permanent
 * property of Array.prototype, so it appears to be a direct property of each
 * array instance delegating to that Array.prototype. It accesses the private
 * slot reserved by js_ArrayClass.
 *
 * Since SpiderMonkey supports cross-class prototype-based delegation, we have
 * to be careful about the length getter and setter being called on an object
 * not of Array class. For the getter, we search obj's prototype chain for the
 * array that caused this getter to be invoked. In the setter case to overcome
 * the JSPROP_SHARED attribute, we must define a shadowing length property.
 */
static JSBool
array_length_getter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
{
    do {
        if (OBJ_IS_ARRAY(cx, obj))
            return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);
    } while ((obj = OBJ_GET_PROTO(cx, obj)) != NULL);
    return JS_TRUE;
}

static JSBool
array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
{
    jsuint newlen, oldlen, gap, index;
    jsval junk;
    JSObject *iter;
    JSTempValueRooter tvr;
    JSBool ok;

    if (!OBJ_IS_ARRAY(cx, obj)) {
        jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);

        return obj->defineProperty(cx, lengthId, *vp, NULL, NULL, JSPROP_ENUMERATE);
    }

    newlen = ValueIsLength(cx, vp);
    if (JSVAL_IS_NULL(*vp))
        return JS_FALSE;
    oldlen = obj->fslots[JSSLOT_ARRAY_LENGTH];

    if (oldlen == newlen)
        return JS_TRUE;

    if (!IndexToValue(cx, newlen, vp))
        return JS_FALSE;

    if (oldlen < newlen) {
        obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;
        return JS_TRUE;
    }

    if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
        /* Don't reallocate if we're not actually shrinking our slots. */
        jsuint capacity = js_DenseArrayCapacity(obj);
        if (capacity > newlen && !ResizeSlots(cx, obj, capacity, newlen))
            return JS_FALSE;
    } else if (oldlen - newlen < (1 << 24)) {
        do {
            --oldlen;
            if (!JS_CHECK_OPERATION_LIMIT(cx) ||
                !DeleteArrayElement(cx, obj, oldlen)) {
                return JS_FALSE;
            }
        } while (oldlen != newlen);
    } else {
        /*
         * We are going to remove a lot of indexes in a presumably sparse
         * array. So instead of looping through indexes between newlen and
         * oldlen, we iterate through all properties and remove those that
         * correspond to indexes in the half-open range [newlen, oldlen).  See
         * bug 322135.
         */
        iter = JS_NewPropertyIterator(cx, obj);
        if (!iter)
            return JS_FALSE;

        /* Protect iter against GC under JSObject::deleteProperty. */
        JS_PUSH_TEMP_ROOT_OBJECT(cx, iter, &tvr);
        gap = oldlen - newlen;
        for (;;) {
            ok = (JS_CHECK_OPERATION_LIMIT(cx) &&
                  JS_NextProperty(cx, iter, &id));
            if (!ok)
                break;
            if (JSVAL_IS_VOID(id))
                break;
            if (js_IdIsIndex(id, &index) && index - newlen < gap) {
                ok = obj->deleteProperty(cx, id, &junk);
                if (!ok)
                    break;
            }
        }
        JS_POP_TEMP_ROOT(cx, &tvr);
        if (!ok)
            return JS_FALSE;
    }

    obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;
    return JS_TRUE;
}

/*
 * We have only indexed properties up to capacity (excepting holes), plus the
 * length property. For all else, we delegate to the prototype.
 */
static inline bool
IsDenseArrayId(JSContext *cx, JSObject *obj, jsid id)
{
    JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));

    uint32 i;
    return id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom) ||
           (js_IdIsIndex(id, &i) &&
            obj->fslots[JSSLOT_ARRAY_LENGTH] != 0 &&
            i < js_DenseArrayCapacity(obj) &&
            obj->dslots[i] != JSVAL_HOLE);
}

static JSBool
array_lookupProperty(JSContext *cx, JSObject *obj, jsid id, JSObject **objp,
                     JSProperty **propp)
{
    if (!OBJ_IS_DENSE_ARRAY(cx, obj))
        return js_LookupProperty(cx, obj, id, objp, propp);

    if (IsDenseArrayId(cx, obj, id)) {
        *propp = (JSProperty *) id;
        *objp = obj;
        return JS_TRUE;
    }

    JSObject *proto = STOBJ_GET_PROTO(obj);
    if (!proto) {
        *objp = NULL;
        *propp = NULL;
        return JS_TRUE;
    }
    return proto->lookupProperty(cx, id, objp, propp);
}

static void
array_dropProperty(JSContext *cx, JSObject *obj, JSProperty *prop)
{
    JS_ASSERT(IsDenseArrayId(cx, obj, (jsid) prop));
}

JSBool
js_GetDenseArrayElementValue(JSContext *cx, JSObject *obj, JSProperty *prop,
                             jsval *vp)
{
    jsid id = (jsid) prop;
    JS_ASSERT(IsDenseArrayId(cx, obj, id));

    uint32 i;
    if (!js_IdIsIndex(id, &i)) {
        JS_ASSERT(id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom));
        return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);
    }
    *vp = obj->dslots[i];
    return JS_TRUE;
}

static JSBool
array_getProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
{
    uint32 i;

    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
        return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);

    if (id == ATOM_TO_JSID(cx->runtime->atomState.protoAtom)) {
        *vp = OBJECT_TO_JSVAL(obj->getProto());
        return JS_TRUE;
    }

    if (!OBJ_IS_DENSE_ARRAY(cx, obj))
        return js_GetProperty(cx, obj, id, vp);

    if (!js_IdIsIndex(ID_TO_VALUE(id), &i) || i >= js_DenseArrayCapacity(obj) ||
        obj->dslots[i] == JSVAL_HOLE) {
        JSObject *obj2;
        JSProperty *prop;
        JSScopeProperty *sprop;

        JSObject *proto = STOBJ_GET_PROTO(obj);
        if (!proto) {
            *vp = JSVAL_VOID;
            return JS_TRUE;
        }

        *vp = JSVAL_VOID;
        if (js_LookupPropertyWithFlags(cx, proto, id, cx->resolveFlags,
                                       &obj2, &prop) < 0)
            return JS_FALSE;

        if (prop) {
            if (OBJ_IS_NATIVE(obj2)) {
                sprop = (JSScopeProperty *) prop;
                if (!js_NativeGet(cx, obj, obj2, sprop, vp))
                    return JS_FALSE;
            }
            obj2->dropProperty(cx, prop);
        }
        return JS_TRUE;
    }

    *vp = obj->dslots[i];
    return JS_TRUE;
}

static JSBool
slowarray_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
{
    jsuint index, length;

    if (!js_IdIsIndex(id, &index))
        return JS_TRUE;
    length = obj->fslots[JSSLOT_ARRAY_LENGTH];
    if (index >= length)
        obj->fslots[JSSLOT_ARRAY_LENGTH] = index + 1;
    return JS_TRUE;
}

static void
slowarray_trace(JSTracer *trc, JSObject *obj)
{
    uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];

    JS_ASSERT(STOBJ_GET_CLASS(obj) == &js_SlowArrayClass);

    /*
     * Move JSSLOT_ARRAY_LENGTH aside to prevent the GC from treating
     * untagged integer values as objects or strings.
     */
    obj->fslots[JSSLOT_ARRAY_LENGTH] = JSVAL_VOID;
    js_TraceObject(trc, obj);
    obj->fslots[JSSLOT_ARRAY_LENGTH] = length;
}

static JSObjectOps js_SlowArrayObjectOps;

static JSObjectOps *
slowarray_getObjectOps(JSContext *cx, JSClass *clasp)
{
    return &js_SlowArrayObjectOps;
}

static JSBool
array_setProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
{
    uint32 i;

    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
        return array_length_setter(cx, obj, id, vp);

    if (!OBJ_IS_DENSE_ARRAY(cx, obj))
        return js_SetProperty(cx, obj, id, vp);

    if (!js_IdIsIndex(id, &i) || INDEX_TOO_SPARSE(obj, i)) {
        if (!js_MakeArraySlow(cx, obj))
            return JS_FALSE;
        return js_SetProperty(cx, obj, id, vp);
    }

    if (!EnsureCapacity(cx, obj, i + 1))
        return JS_FALSE;

    if (i >= (uint32)obj->fslots[JSSLOT_ARRAY_LENGTH])
        obj->fslots[JSSLOT_ARRAY_LENGTH] = i + 1;
    if (obj->dslots[i] == JSVAL_HOLE)
        obj->fslots[JSSLOT_ARRAY_COUNT]++;
    obj->dslots[i] = *vp;
    return JS_TRUE;
}

JSBool
js_PrototypeHasIndexedProperties(JSContext *cx, JSObject *obj)
{
    /*
     * Walk up the prototype chain and see if this indexed element already
     * exists. If we hit the end of the prototype chain, it's safe to set the
     * element on the original object.
     */
    while ((obj = obj->getProto()) != NULL) {
        /*
         * If the prototype is a non-native object (possibly a dense array), or
         * a native object (possibly a slow array) that has indexed properties,
         * return true.
         */
        if (!OBJ_IS_NATIVE(obj))
            return JS_TRUE;
        if (OBJ_SCOPE(obj)->hadIndexedProperties())
            return JS_TRUE;
    }
    return JS_FALSE;
}

#ifdef JS_TRACER

static inline JSBool FASTCALL
dense_grow(JSContext* cx, JSObject* obj, jsint i, jsval v)
{
    /*
     * Let the interpreter worry about negative array indexes.
     */
    JS_ASSERT((MAX_DSLOTS_LENGTH > MAX_DSLOTS_LENGTH32) == (sizeof(jsval) != sizeof(uint32)));
    if (MAX_DSLOTS_LENGTH > MAX_DSLOTS_LENGTH32) {
        /*
         * Have to check for negative values bleeding through on 64-bit machines only,
         * since we can't allocate large enough arrays for this on 32-bit machines.
         */
        if (i < 0)
            return JS_FALSE;
    }

    /*
     * If needed, grow the array as long it remains dense, otherwise fall off trace.
     */
    jsuint u = jsuint(i);
    jsuint capacity = js_DenseArrayCapacity(obj);
    if ((u >= capacity) && (INDEX_TOO_SPARSE(obj, u) || !EnsureCapacity(cx, obj, u + 1)))
        return JS_FALSE;

    if (obj->dslots[u] == JSVAL_HOLE) {
        if (js_PrototypeHasIndexedProperties(cx, obj))
            return JS_FALSE;

        if (u >= jsuint(obj->fslots[JSSLOT_ARRAY_LENGTH]))
            obj->fslots[JSSLOT_ARRAY_LENGTH] = u + 1;
        ++obj->fslots[JSSLOT_ARRAY_COUNT];
    }

    obj->dslots[u] = v;
    return JS_TRUE;
}


JSBool FASTCALL
js_Array_dense_setelem(JSContext* cx, JSObject* obj, jsint i, jsval v)
{
    JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
    return dense_grow(cx, obj, i, v);
}
JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem, CONTEXT, OBJECT, INT32, JSVAL, 0, 0)

JSBool FASTCALL
js_Array_dense_setelem_int(JSContext* cx, JSObject* obj, jsint i, int32 j)
{
    JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));

    jsval v;
    if (JS_LIKELY(INT_FITS_IN_JSVAL(j))) {
        v = INT_TO_JSVAL(j);
    } else {
        jsdouble d = (jsdouble)j;
        if (!js_NewDoubleInRootedValue(cx, d, &v))
            return JS_FALSE;
    }

    return dense_grow(cx, obj, i, v);
}
JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem_int, CONTEXT, OBJECT, INT32, INT32, 0, 0)

JSBool FASTCALL
js_Array_dense_setelem_double(JSContext* cx, JSObject* obj, jsint i, jsdouble d)
{
    JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));

    jsval v;
    jsint j;

    if (JS_LIKELY(JSDOUBLE_IS_INT(d, j) && INT_FITS_IN_JSVAL(j))) {
        v = INT_TO_JSVAL(j);
    } else {
        if (!js_NewDoubleInRootedValue(cx, d, &v))
            return JS_FALSE;
    }

    return dense_grow(cx, obj, i, v);
}
JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem_double, CONTEXT, OBJECT, INT32, DOUBLE, 0, 0)
#endif

static JSBool
array_defineProperty(JSContext *cx, JSObject *obj, jsid id, jsval value,
                     JSPropertyOp getter, JSPropertyOp setter, uintN attrs)
{
    uint32 i;
    JSBool isIndex;

    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
        return JS_TRUE;

    isIndex = js_IdIsIndex(ID_TO_VALUE(id), &i);
    if (!isIndex || attrs != JSPROP_ENUMERATE || !OBJ_IS_DENSE_ARRAY(cx, obj) || INDEX_TOO_SPARSE(obj, i)) {
        if (!ENSURE_SLOW_ARRAY(cx, obj))
            return JS_FALSE;
        return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
    }

    return array_setProperty(cx, obj, id, &value);
}

static JSBool
array_getAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
                    uintN *attrsp)
{
    *attrsp = id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)
        ? JSPROP_PERMANENT : JSPROP_ENUMERATE;
    return JS_TRUE;
}

static JSBool
array_setAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
                    uintN *attrsp)
{
    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
                         JSMSG_CANT_SET_ARRAY_ATTRS);
    return JS_FALSE;
}

static JSBool
array_deleteProperty(JSContext *cx, JSObject *obj, jsval id, jsval *rval)
{
    uint32 i;

    if (!OBJ_IS_DENSE_ARRAY(cx, obj))
        return js_DeleteProperty(cx, obj, id, rval);

    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)) {
        *rval = JSVAL_FALSE;
        return JS_TRUE;
    }

    if (js_IdIsIndex(id, &i) && i < js_DenseArrayCapacity(obj) &&
        obj->dslots[i] != JSVAL_HOLE) {
        obj->fslots[JSSLOT_ARRAY_COUNT]--;
        obj->dslots[i] = JSVAL_HOLE;
    }

    *rval = JSVAL_TRUE;
    return JS_TRUE;
}

/*
 * JSObjectOps.enumerate implementation.
 *
 * For a fast array, JSENUMERATE_INIT captures in the enumeration state both
 * the length of the array and the bitmap indicating the positions of holes in
 * the array. This ensures that adding or deleting array elements does not
 * affect the sequence of indexes JSENUMERATE_NEXT returns.
 *
 * For a common case of an array without holes, to represent the state we pack
 * the (nextEnumerationIndex, arrayLength) pair as a pseudo-boolean jsval.
 * This is possible when length <= PACKED_UINT_PAIR_BITS. For arrays with
 * greater length or holes we allocate the JSIndexIterState structure and
 * store it as an int-tagged private pointer jsval. For a slow array we
 * delegate the enumeration implementation to js_Enumerate in
 * slowarray_enumerate.
 *
 * Array mutations can turn a fast array into a slow one after the enumeration
 * starts. When this happens, slowarray_enumerate receives a state created
 * when the array was fast. To distinguish such fast state from a slow state,
 * which is an int-tagged pointer that js_Enumerate creates, we set not one
 * but two lowest bits when tagging a JSIndexIterState pointer -- see
 * INDEX_ITER_TAG usage below. Thus, when slowarray_enumerate receives a state
 * tagged with JSVAL_SPECIAL or with two lowest bits set, it knows that this
 * is a fast state so it calls array_enumerate to continue enumerating the
 * indexes present in the original fast array.
 */

#define PACKED_UINT_PAIR_BITS           14
#define PACKED_UINT_PAIR_MASK           JS_BITMASK(PACKED_UINT_PAIR_BITS)

#define UINT_PAIR_TO_SPECIAL_JSVAL(i,j)                                \
    (JS_ASSERT((uint32) (i) <= PACKED_UINT_PAIR_MASK),                        \
     JS_ASSERT((uint32) (j) <= PACKED_UINT_PAIR_MASK),                        \
     ((jsval) (i) << (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)) |               \
     ((jsval) (j) << (JSVAL_TAGBITS)) |                                       \
     (jsval) JSVAL_SPECIAL)

#define SPECIAL_JSVAL_TO_UINT_PAIR(v,i,j)                              \
    (JS_ASSERT(JSVAL_IS_SPECIAL(v)),                                   \
     (i) = (uint32) ((v) >> (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)),         \
     (j) = (uint32) ((v) >> JSVAL_TAGBITS) & PACKED_UINT_PAIR_MASK,           \
     JS_ASSERT((i) <= PACKED_UINT_PAIR_MASK))

JS_STATIC_ASSERT(PACKED_UINT_PAIR_BITS * 2 + JSVAL_TAGBITS <= JS_BITS_PER_WORD);

typedef struct JSIndexIterState {
    uint32          index;
    uint32          length;
    JSBool          hasHoles;

    /*
     * Variable-length bitmap representing array's holes. It must not be
     * accessed when hasHoles is false.
     */
    jsbitmap        holes[1];
} JSIndexIterState;

#define INDEX_ITER_TAG      3

JS_STATIC_ASSERT(JSVAL_INT == 1);

static JSBool
array_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
                jsval *statep, jsid *idp)
{
    uint32 capacity, i;
    JSIndexIterState *ii;

    switch (enum_op) {
      case JSENUMERATE_INIT:
        JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
        capacity = js_DenseArrayCapacity(obj);
        if (idp)
            *idp = INT_TO_JSVAL(obj->fslots[JSSLOT_ARRAY_COUNT]);
        ii = NULL;
        for (i = 0; i != capacity; ++i) {
            if (obj->dslots[i] == JSVAL_HOLE) {
                if (!ii) {
                    ii = (JSIndexIterState *)
                         cx->malloc(offsetof(JSIndexIterState, holes) +
                                   JS_BITMAP_SIZE(capacity));
                    if (!ii)
                        return JS_FALSE;
                    ii->hasHoles = JS_TRUE;
                    memset(ii->holes, 0, JS_BITMAP_SIZE(capacity));
                }
                JS_SET_BIT(ii->holes, i);
            }
        }
        if (!ii) {
            /* Array has no holes. */
            if (capacity <= PACKED_UINT_PAIR_MASK) {
                *statep = UINT_PAIR_TO_SPECIAL_JSVAL(0, capacity);
                break;
            }
            ii = (JSIndexIterState *)
                 cx->malloc(offsetof(JSIndexIterState, holes));
            if (!ii)
                return JS_FALSE;
            ii->hasHoles = JS_FALSE;
        }
        ii->index = 0;
        ii->length = capacity;
        *statep = (jsval) ii | INDEX_ITER_TAG;
        JS_ASSERT(*statep & JSVAL_INT);
        break;

      case JSENUMERATE_NEXT:
        if (JSVAL_IS_SPECIAL(*statep)) {
            SPECIAL_JSVAL_TO_UINT_PAIR(*statep, i, capacity);
            if (i != capacity) {
                *idp = INT_TO_JSID(i);
                *statep = UINT_PAIR_TO_SPECIAL_JSVAL(i + 1, capacity);
                break;
            }
        } else {
            JS_ASSERT((*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG);
            ii = (JSIndexIterState *) (*statep & ~INDEX_ITER_TAG);
            i = ii->index;
            if (i != ii->length) {
                /* Skip holes if any. */
                if (ii->hasHoles) {
                    while (JS_TEST_BIT(ii->holes, i) && ++i != ii->length)
                        continue;
                }
                if (i != ii->length) {
                    ii->index = i + 1;
                    return js_IndexToId(cx, i, idp);
                }
            }
        }
        /* FALL THROUGH */

      case JSENUMERATE_DESTROY:
        if (!JSVAL_IS_SPECIAL(*statep)) {
            JS_ASSERT((*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG);
            ii = (JSIndexIterState *) (*statep & ~INDEX_ITER_TAG);
            cx->free(ii);
        }
        *statep = JSVAL_NULL;
        break;
    }
    return JS_TRUE;
}

static JSBool
slowarray_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
                    jsval *statep, jsid *idp)
{
    JSBool ok;

    /* Are we continuing an enumeration that started when we were dense? */
    if (enum_op != JSENUMERATE_INIT) {
        if (JSVAL_IS_SPECIAL(*statep) ||
            (*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG) {
            return array_enumerate(cx, obj, enum_op, statep, idp);
        }
        JS_ASSERT((*statep & INDEX_ITER_TAG) == JSVAL_INT);
    }
    ok = js_Enumerate(cx, obj, enum_op, statep, idp);
    JS_ASSERT(*statep == JSVAL_NULL || (*statep & INDEX_ITER_TAG) == JSVAL_INT);
    return ok;
}

static void
array_finalize(JSContext *cx, JSObject *obj)
{
    if (obj->dslots)
        cx->free(obj->dslots - 1);
    obj->dslots = NULL;
}

static void
array_trace(JSTracer *trc, JSObject *obj)
{
    uint32 capacity;
    size_t i;
    jsval v;

    JS_ASSERT(js_IsDenseArray(obj));
    obj->traceProtoAndParent(trc);

    capacity = js_DenseArrayCapacity(obj);
    for (i = 0; i < capacity; i++) {
        v = obj->dslots[i];
        if (JSVAL_IS_TRACEABLE(v)) {
            JS_SET_TRACING_INDEX(trc, "array_dslots", i);
            JS_CallTracer(trc, JSVAL_TO_TRACEABLE(v), JSVAL_TRACE_KIND(v));
        }
    }
}

extern JSObjectOps js_ArrayObjectOps;

static const JSObjectMap SharedArrayMap(&js_ArrayObjectOps, JSObjectMap::SHAPELESS);

JSObjectOps js_ArrayObjectOps = {
    &SharedArrayMap,
    array_lookupProperty, array_defineProperty,
    array_getProperty,    array_setProperty,
    array_getAttributes,  array_setAttributes,
    array_deleteProperty, js_DefaultValue,
    array_enumerate,      js_CheckAccess,
    NULL,                 array_dropProperty,
    NULL,                 NULL,
    js_HasInstance,       array_trace,
    NULL
};

static JSObjectOps *
array_getObjectOps(JSContext *cx, JSClass *clasp)
{
    return &js_ArrayObjectOps;
}

JSClass js_ArrayClass = {
    "Array",
    JSCLASS_HAS_RESERVED_SLOTS(2) |
    JSCLASS_HAS_CACHED_PROTO(JSProto_Array) |
    JSCLASS_NEW_ENUMERATE,
    JS_PropertyStub,    JS_PropertyStub,   JS_PropertyStub,   JS_PropertyStub,
    JS_EnumerateStub,   JS_ResolveStub,    js_TryValueOf,     array_finalize,
    array_getObjectOps, NULL,              NULL,              NULL,
    NULL,               NULL,              NULL,              NULL
};

JSClass js_SlowArrayClass = {
    "Array",
    JSCLASS_HAS_RESERVED_SLOTS(1) |
    JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
    slowarray_addProperty, JS_PropertyStub, JS_PropertyStub,  JS_PropertyStub,
    JS_EnumerateStub,      JS_ResolveStub,  js_TryValueOf,    NULL,
    slowarray_getObjectOps, NULL,           NULL,             NULL,
    NULL,                  NULL,            NULL,             NULL
};

/*
 * Convert an array object from fast-and-dense to slow-and-flexible.
 */
JSBool
js_MakeArraySlow(JSContext *cx, JSObject *obj)
{
    JS_ASSERT(obj->getClass() == &js_ArrayClass);

    /*
     * Create a native scope. All slow arrays other than Array.prototype get
     * the same initial shape.
     */
    uint32 emptyShape;
    JSObject *arrayProto = obj->getProto();
    if (arrayProto->getClass() == &js_ObjectClass) {
        /* obj is Array.prototype. */
        emptyShape = js_GenerateShape(cx, false);
    } else {
        /* arrayProto is Array.prototype. */
        JS_ASSERT(arrayProto->getClass() == &js_SlowArrayClass);
        emptyShape = OBJ_SCOPE(arrayProto)->emptyScope->shape;
    }
    JSScope *scope = JSScope::create(cx, &js_SlowArrayObjectOps, &js_SlowArrayClass, obj,
                                     emptyShape);
    if (!scope)
        return JS_FALSE;

    uint32 capacity = js_DenseArrayCapacity(obj);
    if (capacity) {
        scope->freeslot = STOBJ_NSLOTS(obj) + JS_INITIAL_NSLOTS;
        obj->dslots[-1] = JS_INITIAL_NSLOTS + capacity;
    } else {
        scope->freeslot = STOBJ_NSLOTS(obj);
    }

    /* Create new properties pointing to existing values in dslots */
    for (uint32 i = 0; i < capacity; i++) {
        jsid id;
        JSScopeProperty *sprop;

        if (!JS_ValueToId(cx, INT_TO_JSVAL(i), &id))
            goto out_bad;

        if (obj->dslots[i] == JSVAL_HOLE) {
            obj->dslots[i] = JSVAL_VOID;
            continue;
        }

        sprop = scope->add(cx, id, NULL, NULL, i + JS_INITIAL_NSLOTS,
                           JSPROP_ENUMERATE, 0, 0);
        if (!sprop)
            goto out_bad;
    }

    /*
     * Render our formerly-reserved count property GC-safe. If length fits in
     * a jsval, set our slow/sparse COUNT to the current length as a jsval, so
     * we can tell when only named properties have been added to a dense array
     * to make it slow-but-not-sparse.
     */
    {
        uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
        obj->fslots[JSSLOT_ARRAY_COUNT] = INT_FITS_IN_JSVAL(length)
                                          ? INT_TO_JSVAL(length)
                                          : JSVAL_VOID;
    }

    /* Make sure we preserve any flags borrowing bits in classword. */
    obj->classword ^= (jsuword) &js_ArrayClass;
    obj->classword |= (jsuword) &js_SlowArrayClass;

    obj->map = scope;
    return JS_TRUE;

  out_bad:
    JSScope::destroy(cx, scope);
    return JS_FALSE;
}

/* Transfer ownership of buffer to returned string. */
static inline JSBool
BufferToString(JSContext *cx, JSCharBuffer &cb, jsval *rval)
{
    JSString *str = js_NewStringFromCharBuffer(cx, cb);
    if (!str)
        return false;
    *rval = STRING_TO_JSVAL(str);
    return true;
}

#if JS_HAS_TOSOURCE
static JSBool
array_toSource(JSContext *cx, uintN argc, jsval *vp)
{
    JS_CHECK_RECURSION(cx, return 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 false;
    }

    /* Find joins or cycles in the reachable object graph. */
    jschar *sharpchars;
    JSHashEntry *he = js_EnterSharpObject(cx, obj, NULL, &sharpchars);
    if (!he)
        return false;
    bool initiallySharp = IS_SHARP(he);

    /* After this point, all paths exit through the 'out' label. */
    MUST_FLOW_THROUGH("out");
    bool ok = false;

    /*
     * This object will take responsibility for the jschar buffer until the
     * buffer is transferred to the returned JSString.
     */
    JSCharBuffer cb(cx);

    /* Cycles/joins are indicated by sharp objects. */
#if JS_HAS_SHARP_VARS
    if (IS_SHARP(he)) {
        JS_ASSERT(sharpchars != 0);
        cb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
        goto make_string;
    } else if (sharpchars) {
        MAKE_SHARP(he);
        cb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
    }
#else
    if (IS_SHARP(he)) {
        if (!js_AppendLiteral(cb, "[]"))
            goto out;
        cx->free(sharpchars);
        goto make_string;
    }
#endif

    if (!cb.append('['))
        goto out;

    jsuint length;
    if (!js_GetLengthProperty(cx, obj, &length))
        goto out;

    for (jsuint index = 0; index < length; index++) {
        /* Use vp to locally root each element value. */
        JSBool hole;
        if (!JS_CHECK_OPERATION_LIMIT(cx) ||
            !GetArrayElement(cx, obj, index, &hole, vp)) {
            goto out;
        }

        /* Get element's character string. */
        JSString *str;
        if (hole) {
            str = cx->runtime->emptyString;
        } else {
            str = js_ValueToSource(cx, *vp);
            if (!str)
                goto out;
        }
        *vp = STRING_TO_JSVAL(str);
        const jschar *chars;
        size_t charlen;
        str->getCharsAndLength(chars, charlen);

        /* Append element to buffer. */
        if (!cb.append(chars, charlen))
            goto out;
        if (index + 1 != length) {
            if (!js_AppendLiteral(cb, ", "))
                goto out;
        } else if (hole) {
            if (!cb.append(','))
                goto out;
        }
    }

    /* Finalize the buffer. */
    if (!cb.append(']'))
        goto out;

  make_string:
    if (!BufferToString(cx, cb, vp))
        goto out;

    ok = true;

  out:
    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;
}

bool
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 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 false;
        }
    } else {
        /* Cycle, so return empty string. */
        *rval = ATOM_KEY(cx->runtime->atomState.emptyAtom);
        return true;
    }

    JSAutoTempValueRooter tvr(cx, obj);

    /* After this point, all paths exit through the 'out' label. */
    MUST_FLOW_THROUGH("out");
    bool ok = false;

    /* 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 take responsibility for the jschar buffer until the
     * buffer is transferred to the returned JSString.
     */
    JSCharBuffer cb(cx);

    jsuint length;
    if (!js_GetLengthProperty(cx, obj, &length))
        goto out;

    for (jsuint index = 0; index < length; index++) {
        /* Use rval to locally root each element value. */
        JSBool hole;
        if (!JS_CHECK_OPERATION_LIMIT(cx) ||
            !GetArrayElement(cx, obj, index, &hole, rval)) {
            goto out;
        }

        /* Get element's character string. */
        if (!(hole || JSVAL_IS_VOID(*rval) || JSVAL_IS_NULL(*rval))) {
            if (locale) {
                /* Work on obj.toLocalString() instead. */
                JSObject *robj;

                if (!js_ValueToObject(cx, *rval, &robj))
                    goto out;
                *rval = OBJECT_TO_JSVAL(robj);
                JSAtom *atom = cx->runtime->atomState.toLocaleStringAtom;
                if (!js_TryMethod(cx, robj, atom, 0, NULL, rval))
                    goto out;
            }

            if (!js_ValueToCharBuffer(cx, *rval, cb))
                goto out;
        }

        /* Append the separator. */
        if (index + 1 != length) {
            if (!cb.append(sep, seplen))
                goto out;
        }
    }

    /* Finalize the buffer. */
    if (!BufferToString(cx, cb, rval))
        goto out;

    ok = true;

  out:
    /*
     * It is possible that 'hep' may have been invalidated by subsequent
     * RawAdd/Remove. Hence, 'RawRemove' must not be used.
     */
    JS_HashTableRemove(table, obj);
    return ok;
}

static JSBool
array_toString(JSContext *cx, uintN argc, jsval *vp)
{
    JSObject *obj;

    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_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 ||
        (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_toString_sub(cx, obj, JS_TRUE, NULL, vp);
}

enum TargetElementsType {
    TargetElementsAllHoles,
    TargetElementsMayContainValues
};

enum SourceVectorType {
    SourceVectorAllValues,
    SourceVectorMayContainHoles
};

static JSBool
InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, jsval *vector,
                  TargetElementsType targetType, SourceVectorType vectorType)
{
    JS_ASSERT(count < MAXINDEX);

    /*
     * Optimize for dense arrays so long as adding the given set of elements
     * wouldn't otherwise make the array slow.
     */
    if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
        start <= MAXINDEX - count && !INDEX_TOO_BIG(start + count)) {

#ifdef DEBUG_jwalden
        {
            /* Verify that overwriteType and writeType were accurate. */
            JSAutoTempIdRooter idr(cx, JSVAL_ZERO);
            for (jsuint i = 0; i < count; i++) {
                JS_ASSERT_IF(vectorType == SourceVectorAllValues, vector[i] != JSVAL_HOLE);

                jsdouble index = jsdouble(start) + i;
                if (targetType == TargetElementsAllHoles && index < jsuint(-1)) {
                    JS_ASSERT(ReallyBigIndexToId(cx, index, idr.addr()));
                    JSObject* obj2;
                    JSProperty* prop;
                    JS_ASSERT(obj->lookupProperty(cx, idr.id(), &obj2, &prop));
                    JS_ASSERT(!prop);
                }
            }
        }
#endif

        jsuint newlen = start + count;
        JS_ASSERT(jsdouble(start) + count == jsdouble(newlen));
        if (!EnsureCapacity(cx, obj, newlen))
            return JS_FALSE;

        if (newlen > uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]))
            obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;

        JS_ASSERT(count < size_t(-1) / sizeof(jsval));
        if (targetType == TargetElementsMayContainValues) {
            jsuint valueCount = 0;
            for (jsuint i = 0; i < count; i++) {
                 if (obj->dslots[start + i] != JSVAL_HOLE)
                     valueCount++;
            }
            JS_ASSERT(uint32(obj->fslots[JSSLOT_ARRAY_COUNT]) >= valueCount);
            obj->fslots[JSSLOT_ARRAY_COUNT] -= valueCount;
        }
        memcpy(obj->dslots + start, vector, sizeof(jsval) * count);
        if (vectorType == SourceVectorAllValues) {
            obj->fslots[JSSLOT_ARRAY_COUNT] += count;
        } else {
            jsuint valueCount = 0;
            for (jsuint i = 0; i < count; i++) {
                 if (obj->dslots[start + i] != JSVAL_HOLE)
                     valueCount++;
            }
            obj->fslots[JSSLOT_ARRAY_COUNT] += valueCount;
        }
        JS_ASSERT_IF(count != 0, obj->dslots[newlen - 1] != JSVAL_HOLE);
        return JS_TRUE;
    }

    jsval* end = vector + count;
    while (vector != end && start < MAXINDEX) {
        if (!JS_CHECK_OPERATION_LIMIT(cx) ||
            !SetArrayElement(cx, obj, start++, *vector++)) {
            return JS_FALSE;
        }
    }

    if (vector == end)
        return JS_TRUE;

    /* Finish out any remaining elements past the max array index. */
    if (OBJ_IS_DENSE_ARRAY(cx, obj) && !ENSURE_SLOW_ARRAY(cx, obj))
        return JS_FALSE;

    JS_ASSERT(start == MAXINDEX);
    jsval tmp[2] = {JSVAL_NULL, JSVAL_NULL};
    jsdouble* dp = js_NewWeaklyRootedDouble(cx, MAXINDEX);
    if (!dp)
        return JS_FALSE;
    tmp[0] = DOUBLE_TO_JSVAL(dp);
    JSAutoTempValueRooter tvr(cx, JS_ARRAY_LENGTH(tmp), tmp);
    JSAutoTempIdRooter idr(cx);
    do {
        tmp[1] = *vector++;
        if (!js_ValueToStringId(cx, tmp[0], idr.addr()) ||
            !obj->setProperty(cx, idr.id(), &tmp[1])) {
            return JS_FALSE;
        }
        *dp += 1;
    } while (vector != end);

    return JS_TRUE;
}

static JSBool
InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector,
                JSBool holey = JS_FALSE)
{
    JS_ASSERT(OBJ_IS_ARRAY(cx, obj));

    obj->fslots[JSSLOT_ARRAY_LENGTH] = length;

    if (vector) {
        if (!EnsureCapacity(cx, obj, length))
            return JS_FALSE;

        jsuint count = length;
        if (!holey) {
            memcpy(obj->dslots, vector, length * sizeof (jsval));
        } else {
            for (jsuint i = 0; i < length; i++) {
                if (vector[i] == JSVAL_HOLE)
                    --count;
                obj->dslots[i] = vector[i];
            }
        }
        obj->fslots[JSSLOT_ARRAY_COUNT] = count;
    } else {
        obj->fslots[JSSLOT_ARRAY_COUNT] = 0;
    }
    return JS_TRUE;
}

#ifdef JS_TRACER
static JSString* FASTCALL
Array_p_join(JSContext* cx, JSObject* obj, JSString *str)
{
    JSAutoTempValueRooter tvr(cx);
    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_toString_sub(cx, obj, JS_FALSE, NULL, tvr.addr())) {
        js_SetBuiltinError(cx);
        return NULL;
    }
    return JSVAL_TO_STRING(tvr.value());
}
#endif

/*
 * Perl-inspired join, reverse, and sort.
 */
static JSBool
array_join(JSContext *cx, uintN argc, jsval *vp)
{
    JSString *str;
    JSObject *obj;

    if (argc == 0 || JSVAL_IS_VOID(vp[2])) {
        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_toString_sub(cx, obj, JS_FALSE, str, vp);
}

static JSBool
array_reverse(JSContext *cx, uintN argc, jsval *vp)
{
    jsuint len;
    JSObject *obj = JS_THIS_OBJECT(cx, vp);
    if (!obj || !js_GetLengthProperty(cx, obj, &len))
        return JS_FALSE;
    *vp = OBJECT_TO_JSVAL(obj);

    if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj)) {
        /* An empty array or an array with no elements is already reversed. */
        if (len == 0 || !obj->dslots)
            return JS_TRUE;

        /*
         * It's actually surprisingly complicated to reverse an array due to the
         * orthogonality of array length and array capacity while handling
         * leading and trailing holes correctly.  Reversing seems less likely to
         * be a common operation than other array mass-mutation methods, so for
         * now just take a probably-small memory hit (in the absence of too many
         * holes in the array at its start) and ensure that the capacity is
         * sufficient to hold all the elements in the array if it were full.
         */
        if (!EnsureCapacity(cx, obj, len))
            return JS_FALSE;

        jsval* lo = &obj->dslots[0];
        jsval* hi = &obj->dslots[len - 1];
        for (; lo < hi; lo++, hi--) {
             jsval tmp = *lo;
             *lo = *hi;
             *hi = tmp;
        }

        /*
         * Per ECMA-262, don't update the length of the array, even if the new
         * array has trailing holes (and thus the original array began with
         * holes).
         */
        return JS_TRUE;
    }

    JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
    for (jsuint i = 0, half = len / 2; i < half; i++) {
        JSBool hole, hole2;
        if (!JS_CHECK_OPERATION_LIMIT(cx) ||
            !GetArrayElement(cx, obj, i, &hole, tvr.addr()) ||
            !GetArrayElement(cx, obj, len - i - 1, &hole2, vp) ||
            !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, tvr.value()) ||
            !SetOrDeleteArrayElement(cx, obj, i, hole2, *vp)) {
            return false;
        }
    }
    *vp = OBJECT_TO_JSVAL(obj);
    return true;
}

typedef struct MSortArgs {
    size_t       elsize;
    JSComparator cmp;
    void         *arg;
    JSBool       fastcopy;
} MSortArgs;

/* Helper function for js_MergeSort. */
static JSBool
MergeArrays(MSortArgs *msa, void *src, void *dest, size_t run1, size_t run2)
{
    void *arg, *a, *b, *c;
    size_t elsize, runtotal;
    int cmp_result;
    JSComparator cmp;
    JSBool fastcopy;

    runtotal = run1 + run2;

    elsize = msa->elsize;
    cmp = msa->cmp;
    arg = msa->arg;
    fastcopy = msa->fastcopy;

#define CALL_CMP(a, b) \
    if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;

    /* Copy runs already in sorted order. */
    b = (char *)src + run1 * elsize;
    a = (char *)b - elsize;
    CALL_CMP(a, b);
    if (cmp_result <= 0) {
        memcpy(dest, src, runtotal * elsize);
        return JS_TRUE;
    }

#define COPY_ONE(p,q,n) \
    (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))

    a = src;
    c = dest;
    for (; runtotal != 0; runtotal--) {
        JSBool from_a = run2 == 0;
        if (!from_a && run1 != 0) {
            CALL_CMP(a,b);
            from_a = cmp_result <= 0;
        }

        if (from_a) {
            COPY_ONE(c, a, elsize);
            run1--;
            a = (char *)a + elsize;
        } else {
            COPY_ONE(c, b, elsize);
            run2--;
            b = (char *)b + elsize;
        }
        c = (char *)c + elsize;
    }
#undef COPY_ONE
#undef CALL_CMP

    return JS_TRUE;
}

/*
 * This sort is stable, i.e. sequence of equal elements is preserved.
 * See also bug #224128.
 */
JSBool
js_MergeSort(void *src, size_t nel, size_t elsize,
             JSComparator cmp, void *arg, void *tmp)
{
    void *swap, *vec1, *vec2;
    MSortArgs msa;
    size_t i, j, lo, hi, run;
    JSBool fastcopy;
    int cmp_result;

    /* Avoid memcpy overhead for word-sized and word-aligned elements. */
    fastcopy = (elsize == sizeof(jsval) &&
                (((jsuword) src | (jsuword) tmp) & JSVAL_ALIGN) == 0);
#define COPY_ONE(p,q,n) \
    (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
#define CALL_CMP(a, b) \
    if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
#define INS_SORT_INT 4

    /*
     * Apply insertion sort to small chunks to reduce the number of merge
     * passes needed.
     */
    for (lo = 0; lo < nel; lo += INS_SORT_INT) {
        hi = lo + INS_SORT_INT;
        if (hi >= nel)
            hi = nel;
        for (i = lo + 1; i < hi; i++) {
            vec1 = (char *)src + i * elsize;
            vec2 = (char *)vec1 - elsize;
            for (j = i; j > lo; j--) {
                CALL_CMP(vec2, vec1);
                /* "<=" instead of "<" insures the sort is stable */
                if (cmp_result <= 0) {
                    break;
                }

                /* Swap elements, using "tmp" as tmp storage */
                COPY_ONE(tmp, vec2, elsize);
                COPY_ONE(vec2, vec1, elsize);
                COPY_ONE(vec1, tmp, elsize);
                vec1 = vec2;
                vec2 = (char *)vec1 - elsize;
            }
        }
    }
#undef CALL_CMP
#undef COPY_ONE

    msa.elsize = elsize;
    msa.cmp = cmp;
    msa.arg = arg;
    msa.fastcopy = fastcopy;

    vec1 = src;
    vec2 = tmp;
    for (run = INS_SORT_INT; run < nel; run *= 2) {
        for (lo = 0; lo < nel; lo += 2 * run) {
            hi = lo + run;
            if (hi >= nel) {
                memcpy((char *)vec2 + lo * elsize, (char *)vec1 + lo * elsize,
                       (nel - lo) * elsize);
                break;
            }
            if (!MergeArrays(&msa, (char *)vec1 + lo * elsize,
                             (char *)vec2 + lo * elsize, run,
                             hi + run > nel ? nel - hi : run)) {
                return JS_FALSE;
            }
        }
        swap = vec1;
        vec1 = vec2;
        vec2 = swap;
    }
    if (src != vec1)
        memcpy(src, tmp, nel * elsize);

    return JS_TRUE;
}

typedef struct CompareArgs {
    JSContext   *context;
    jsval       fval;
    jsval       *elemroot;      /* stack needed for js_Invoke */
} CompareArgs;

static JS_REQUIRES_STACK JSBool
sort_compare(void *arg, const void *a, const void *b, int *result)
{
    jsval av = *(const jsval *)a, bv = *(const jsval *)b;
    CompareArgs *ca = (CompareArgs *) arg;
    JSContext *cx = ca->context;
    jsval *invokevp, *sp;
    jsdouble cmp;

    /**
     * array_sort deals with holes and undefs on its own and they should not
     * come here.
     */
    JS_ASSERT(!JSVAL_IS_VOID(av));
    JS_ASSERT(!JSVAL_IS_VOID(bv));

    if (!JS_CHECK_OPERATION_LIMIT(cx))
        return JS_FALSE;

    invokevp = ca->elemroot;
    sp = invokevp;
    *sp++ = ca->fval;
    *sp++ = JSVAL_NULL;
    *sp++ = av;
    *sp++ = bv;

    if (!js_Invoke(cx, 2, invokevp, 0))
        return JS_FALSE;

    cmp = js_ValueToNumber(cx, invokevp);
    if (JSVAL_IS_NULL(*invokevp))
        return JS_FALSE;

    /* Clamp cmp to -1, 0, 1. */
    *result = 0;
    if (!JSDOUBLE_IS_NaN(cmp) && cmp != 0)
        *result = cmp > 0 ? 1 : -1;

    /*
     * XXX else report some kind of error here?  ECMA talks about 'consistent
     * compare functions' that don't return NaN, but is silent about what the
     * result should be.  So we currently ignore it.
     */

    return JS_TRUE;
}

typedef JSBool (JS_REQUIRES_STACK *JSRedComparator)(void*, const void*,
                                                    const void*, int *);

static inline JS_IGNORE_STACK JSComparator
comparator_stack_cast(JSRedComparator func)
{
    return func;
}

static int
sort_compare_strings(void *arg, const void *a, const void *b, int *result)
{
    jsval av = *(const jsval *)a, bv = *(const jsval *)b;

    JS_ASSERT(JSVAL_IS_STRING(av));
    JS_ASSERT(JSVAL_IS_STRING(bv));
    if (!JS_CHECK_OPERATION_LIMIT((JSContext *)arg))
        return JS_FALSE;

    *result = (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
    return JS_TRUE;
}

/*
 * The array_sort function below assumes JSVAL_NULL is zero in order to
 * perform initialization using memset.  Other parts of SpiderMonkey likewise
 * "know" that JSVAL_NULL is zero; this static assertion covers all cases.
 */
JS_STATIC_ASSERT(JSVAL_NULL == 0);

static JSBool
array_sort(JSContext *cx, uintN argc, jsval *vp)
{
    jsval *argv, fval, *vec, *mergesort_tmp, v;
    JSObject *obj;
    CompareArgs ca;
    jsuint len, newlen, i, undefs;
    JSTempValueRooter tvr;
    JSBool hole;
    JSBool ok;
    size_t elemsize;
    JSString *str;

    /*
     * Optimize the default compare function case if all of obj's elements
     * have values of type string.
     */
    JSBool all_strings;

    argv = JS_ARGV(cx, vp);
    if (argc > 0) {
        if (JSVAL_IS_PRIMITIVE(argv[0])) {
            JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
                                 JSMSG_BAD_SORT_ARG);
            return JS_FALSE;
        }
        fval = argv[0];     /* non-default compare function */
    } else {
        fval = JSVAL_NULL;
    }

    obj = JS_THIS_OBJECT(cx, vp);
    if (!obj || !js_GetLengthProperty(cx, obj, &len))
        return JS_FALSE;
    if (len == 0) {
        *vp = OBJECT_TO_JSVAL(obj);
        return JS_TRUE;
    }

    /*
     * We need a temporary array of 2 * len jsvals to hold the array elements
     * and the scratch space for merge sort. Check that its size does not
     * overflow size_t, which would allow for indexing beyond the end of the
     * malloc'd vector.
     */
#if JS_BITS_PER_WORD == 32
    if ((size_t)len > ~(size_t)0 / (2 * sizeof(jsval))) {
        js_ReportAllocationOverflow(cx);
        return JS_FALSE;
    }
#endif
    vec = (jsval *) cx->malloc(2 * (size_t) len * sizeof(jsval));
    if (!vec)
        return JS_FALSE;

    /*
     * Initialize vec as a root. We will clear elements of vec one by
     * one while increasing tvr.count when we know that the property at
     * the corresponding index exists and its value must be rooted.
     *
     * In this way when sorting a huge mostly sparse array we will not
     * access the tail of vec corresponding to properties that do not
     * exist, allowing OS to avoiding committing RAM. See bug 330812.
     *
     * After this point control must flow through label out: to exit.
     */
    JS_PUSH_TEMP_ROOT(cx, 0, vec, &tvr);

    /*
     * By ECMA 262, 15.4.4.11, a property that does not exist (which we
     * call a "hole") is always greater than an existing property with
     * value undefined and that is always greater than any other property.
     * Thus to sort holes and undefs we simply count them, sort the rest
     * of elements, append undefs after them and then make holes after
     * undefs.
     */
    undefs = 0;
    newlen = 0;
    all_strings = JS_TRUE;
    for (i = 0; i < len; i++) {
        ok = JS_CHECK_OPERATION_LIMIT(cx);
        if (!ok)
            goto out;

        /* Clear vec[newlen] before including it in the rooted set. */
        vec[newlen] = JSVAL_NULL;
        tvr.count = newlen + 1;
        ok = GetArrayElement(cx, obj, i, &hole, &vec[newlen]);
        if (!ok)
            goto out;

        if (hole)
            continue;

        if (JSVAL_IS_VOID(vec[newlen])) {
            ++undefs;
            continue;
        }

        /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
        all_strings &= JSVAL_IS_STRING(vec[newlen]);

        ++newlen;
    }

    if (newlen == 0) {
        /* The array has only holes and undefs. */
        ok = JS_TRUE;
        goto out;
    }

    /*
     * The first newlen elements of vec are copied from the array object
     * (above). The remaining newlen positions are used as GC-rooted scratch
     * space for mergesort. We must clear the space before including it to
     * the root set covered by tvr.count. We assume JSVAL_NULL==0 to optimize
     * initialization using memset.
     */
    mergesort_tmp = vec + newlen;
    memset(mergesort_tmp, 0, newlen * sizeof(jsval));
    tvr.count = newlen * 2;

    /* Here len == 2 * (newlen + undefs + number_of_holes). */
    if (fval == JSVAL_NULL) {
        /*
         * Sort using the default comparator converting all elements to
         * strings.
         */
        if (all_strings) {
            elemsize = sizeof(jsval);
        } else {
            /*
             * To avoid string conversion on each compare we do it only once
             * prior to sorting. But we also need the space for the original
             * values to recover the sorting result. To reuse
             * sort_compare_strings we move the original values to the odd
             * indexes in vec, put the string conversion results in the even
             * indexes and pass 2 * sizeof(jsval) as an element size to the
             * sorting function. In this way sort_compare_strings will only
             * see the string values when it casts the compare arguments as
             * pointers to jsval.
             *
             * This requires doubling the temporary storage including the
             * scratch space for the merge sort. Since vec already contains
             * the rooted scratch space for newlen elements at the tail, we
             * can use it to rearrange and convert to strings first and try
             * realloc only when we know that we successfully converted all
             * the elements.
             */
#if JS_BITS_PER_WORD == 32
            if ((size_t)newlen > ~(size_t)0 / (4 * sizeof(jsval))) {
                js_ReportAllocationOverflow(cx);
                ok = JS_FALSE;
                goto out;
            }
#endif

            /*
             * Rearrange and string-convert the elements of the vector from
             * the tail here and, after sorting, move the results back
             * starting from the start to prevent overwrite the existing
             * elements.
             */
            i = newlen;
            do {
                --i;
                ok = JS_CHECK_OPERATION_LIMIT(cx);
                if (!ok)
                    goto out;
                v = vec[i];
                str = js_ValueToString(cx, v);
                if (!str) {
                    ok = JS_FALSE;
                    goto out;
                }
                vec[2 * i] = STRING_TO_JSVAL(str);
                vec[2 * i + 1] = v;
            } while (i != 0);

            JS_ASSERT(tvr.u.array == vec);
            vec = (jsval *) cx->realloc(vec,
                                        4 * (size_t) newlen * sizeof(jsval));
            if (!vec) {
                vec = tvr.u.array;
                ok = JS_FALSE;
                goto out;
            }
            tvr.u.array = vec;
            mergesort_tmp = vec + 2 * newlen;
            memset(mergesort_tmp, 0, newlen * 2 * sizeof(jsval));
            tvr.count = newlen * 4;
            elemsize = 2 * sizeof(jsval);
        }
        ok = js_MergeSort(vec, (size_t) newlen, elemsize,
                          sort_compare_strings, cx, mergesort_tmp);
        if (!ok)
            goto out;
        if (!all_strings) {
            /*
             * We want to make the following loop fast and to unroot the
             * cached results of toString invocations before the operation
             * callback has a chance to run the GC. For this reason we do
             * not call JS_CHECK_OPERATION_LIMIT in the loop.
             */
            i = 0;
            do {
                vec[i] = vec[2 * i + 1];
            } while (++i != newlen);
        }
    } else {
        void *mark;

        js_LeaveTrace(cx);

        ca.context = cx;
        ca.fval = fval;
        ca.elemroot  = js_AllocStack(cx, 2 + 2, &mark);
        if (!ca.elemroot) {
            ok = JS_FALSE;
            goto out;
        }
        ok = js_MergeSort(vec, (size_t) newlen, sizeof(jsval),
                          comparator_stack_cast(sort_compare),
                          &ca, mergesort_tmp);
        js_FreeStack(cx, mark);
        if (!ok)
            goto out;
    }

    /*
     * We no longer need to root the scratch space for the merge sort, so
     * unroot it now to make the job of a potential GC under InitArrayElements
     * easier.
     */
    tvr.count = newlen;
    ok = InitArrayElements(cx, obj, 0, newlen, vec, TargetElementsMayContainValues,
                           SourceVectorAllValues);
    if (!ok)
        goto out;

  out:
    JS_POP_TEMP_ROOT(cx, &tvr);
    cx->free(vec);
    if (!ok)
        return JS_FALSE;

    /* Set undefs that sorted after the rest of elements. */
    while (undefs != 0) {
        --undefs;
        if (!JS_CHECK_OPERATION_LIMIT(cx) ||
            !SetArrayElement(cx, obj, newlen++, JSVAL_VOID)) {
            return JS_FALSE;
        }
    }

    /* Re-create any holes that sorted to the end of the array. */
    while (len > newlen) {
        if (!JS_CHECK_OPERATION_LIMIT(cx) ||
            !DeleteArrayElement(cx, obj, --len)) {
            return JS_FALSE;
        }
    }
    *vp = OBJECT_TO_JSVAL(obj);
    return JS_TRUE;
}

/*
 * Perl-inspired push, pop, shift, unshift, and splice methods.
 */
static JSBool
array_push_slowly(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
{
    jsuint length;

    if (!js_GetLengthProperty(cx, obj, &length))
        return JS_FALSE;
    if (!InitArrayElements(cx, obj, length, argc, argv, TargetElementsMayContainValues,
                           SourceVectorAllValues)) {
        return JS_FALSE;
    }

    /* Per ECMA-262, return the new array length. */
    jsdouble newlength = length + jsdouble(argc);
    if (!IndexToValue(cx, newlength, rval))
        return JS_FALSE;
    return js_SetLengthProperty(cx, obj, newlength);
}

static JSBool
array_push1_dense(JSContext* cx, JSObject* obj, jsval v, jsval *rval)
{
    uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
    if (INDEX_TOO_SPARSE(obj, length)) {
        if (!js_MakeArraySlow(cx, obj))
            return JS_FALSE;
        return array_push_slowly(cx, obj, 1, &v, rval);
    }

    if (!EnsureCapacity(cx, obj, length + 1))
        return JS_FALSE;
    obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;

    JS_ASSERT(obj->dslots[length] == JSVAL_HOLE);
    obj->fslots[JSSLOT_ARRAY_COUNT]++;
    obj->dslots[length] = v;
    return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], rval);
}

JSBool JS_FASTCALL
js_ArrayCompPush(JSContext *cx, JSObject *obj, jsval v)
{
    JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
    uint32_t length = (uint32_t) obj->fslots[JSSLOT_ARRAY_LENGTH];
    JS_ASSERT(length <= js_DenseArrayCapacity(obj));

    if (length == js_DenseArrayCapacity(obj)) {
        if (length > JS_ARGS_LENGTH_MAX) {
            JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
                                   JSMSG_ARRAY_INIT_TOO_BIG);
            return JS_FALSE;
        }

        if (!EnsureCapacity(cx, obj, length + 1))
            return JS_FALSE;
    }
    obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;
    obj->fslots[JSSLOT_ARRAY_COUNT]++;
    obj->dslots[length] = v;
    return JS_TRUE;
}
JS_DEFINE_CALLINFO_3(extern, BOOL, js_ArrayCompPush, CONTEXT, OBJECT, JSVAL, 0, 0)

#ifdef JS_TRACER
static jsval FASTCALL
Array_p_push1(JSContext* cx, JSObject* obj, jsval v)
{
    JSAutoTempValueRooter tvr(cx, v);
    if (OBJ_IS_DENSE_ARRAY(cx, obj)
        ? array_push1_dense(cx, obj, v, tvr.addr())
        : array_push_slowly(cx, obj, 1, tvr.addr(), tvr.addr())) {
        return tvr.value();
    }
    js_SetBuiltinError(cx);
    return JSVAL_VOID;
}
#endif

static JSBool
array_push(JSContext *cx, uintN argc, jsval *vp)
{
    JSObject *obj;

    /* Insist on one argument and obj of the expected class. */
    obj = JS_THIS_OBJECT(cx, vp);
    if (!obj)
        return JS_FALSE;
    if (argc != 1 || !OBJ_IS_DENSE_ARRAY(cx, obj))
        return array_push_slowly(cx, obj, argc, vp + 2, vp);

    return array_push1_dense(cx, obj, vp[2], vp);
}

static JSBool
array_pop_slowly(JSContext *cx, JSObject* obj, jsval *vp)
{
    jsuint index;
    JSBool hole;

    if (!js_GetLengthProperty(cx, obj, &index))
        return JS_FALSE;
    if (index == 0) {
        *vp = JSVAL_VOID;
    } else {
        index--;

        /* Get the to-be-deleted property's value into vp. */
        if (!GetArrayElement(cx, obj, index, &hole, vp))
            return JS_FALSE;
        if (!hole && !DeleteArrayElement(cx, obj, index))
            return JS_FALSE;
    }
    return js_SetLengthProperty(cx, obj, index);
}

static JSBool
array_pop_dense(JSContext *cx, JSObject* obj, jsval *vp)
{
    jsuint index;
    JSBool hole;

    index = obj->fslots[JSSLOT_ARRAY_LENGTH];
    if (index == 0) {
        *vp = JSVAL_VOID;
        return JS_TRUE;
    }
    index--;
    if (!GetArrayElement(cx, obj, index, &hole, vp))
        return JS_FALSE;
    if (!hole && !DeleteArrayElement(cx, obj, index))
        return JS_FALSE;
    obj->fslots[JSSLOT_ARRAY_LENGTH] = index;
    return JS_TRUE;
}

#ifdef JS_TRACER
static jsval FASTCALL
Array_p_pop(JSContext* cx, JSObject* obj)
{
    