js/src/jsarray.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set sw=4 ts=8 et tw=78:
   3  *
   4  * ***** BEGIN LICENSE BLOCK *****
   5  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   6  *
   7  * The contents of this file are subject to the Mozilla Public License Version
   8  * 1.1 (the "License"); you may not use this file except in compliance with
   9  * the License. You may obtain a copy of the License at
  10  * http://www.mozilla.org/MPL/
  11  *
  12  * Software distributed under the License is distributed on an "AS IS" basis,
  13  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  14  * for the specific language governing rights and limitations under the
  15  * License.
  16  *
  17  * The Original Code is Mozilla Communicator client code, released
  18  * March 31, 1998.
  19  *
  20  * The Initial Developer of the Original Code is
  21  * Netscape Communications Corporation.
  22  * Portions created by the Initial Developer are Copyright (C) 1998
  23  * the Initial Developer. All Rights Reserved.
  24  *
  25  * Contributor(s):
  26  *
  27  * Alternatively, the contents of this file may be used under the terms of
  28  * either of the GNU General Public License Version 2 or later (the "GPL"),
  29  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  30  * in which case the provisions of the GPL or the LGPL are applicable instead
  31  * of those above. If you wish to allow use of your version of this file only
  32  * under the terms of either the GPL or the LGPL, and not to allow others to
  33  * use your version of this file under the terms of the MPL, indicate your
  34  * decision by deleting the provisions above and replace them with the notice
  35  * and other provisions required by the GPL or the LGPL. If you do not delete
  36  * the provisions above, a recipient may use your version of this file under
  37  * the terms of any one of the MPL, the GPL or the LGPL.
  38  *
  39  * ***** END LICENSE BLOCK ***** */
  40
  41 /*
  42  * JS array class.
  43  *
  44  * Array objects begin as "dense" arrays, optimized for index-only property
  45  * access over a vector of slots with high load factor.  Array methods
  46  * optimize for denseness by testing that the object's class is
  47  * &js_ArrayClass, and can then directly manipulate the slots for efficiency.
  48  *
  49  * We track these pieces of metadata for arrays in dense mode:
  50  *  - The array's length property as a uint32, accessible with
  51  *    getArrayLength(), setArrayLength().
  52  *  - The number of element slots (capacity), gettable with
  53  *    getDenseArrayCapacity().
  54  *
  55  * In dense mode, holes in the array are represented by
  56  * MagicValue(JS_ARRAY_HOLE) invalid values.
  57  *
  58  * NB: the capacity and length of a dense array are entirely unrelated!  The
  59  * length may be greater than, less than, or equal to the capacity. The first
  60  * case may occur when the user writes "new Array(100), in which case the
  61  * length is 100 while the capacity remains 0 (indices below length and above
  62  * capaicty must be treated as holes). See array_length_setter for another
  63  * explanation of how the first case may occur.
  64  *
  65  * Arrays are converted to use js_SlowArrayClass when any of these conditions
  66  * are met:
  67  *  - there are more than MIN_SPARSE_INDEX slots total
  68  *  - the load factor (COUNT / capacity) is less than 0.25
  69  *  - a property is set that is not indexed (and not "length")
  70  *  - a property is defined that has non-default property attributes.
  71  *
  72  * Dense arrays do not track property creation order, so unlike other native
  73  * objects and slow arrays, enumerating an array does not necessarily visit the
  74  * properties in the order they were created.  We could instead maintain the
  75  * scope to track property enumeration order, but still use the fast slot
  76  * access.  That would have the same memory cost as just using a
  77  * js_SlowArrayClass, but have the same performance characteristics as a dense
  78  * array for slot accesses, at some cost in code complexity.
  79  */
  80 #include <stdlib.h>
  81 #include <string.h>
  82 #include "jstypes.h"
  83 #include "jsstdint.h"
  84 #include "jsutil.h"
  85 #include "jsapi.h"
  86 #include "jsarray.h"
  87 #include "jsatom.h"
  88 #include "jsbit.h"
  89 #include "jsbool.h"
  90 #include "jstracer.h"
  91 #include "jsbuiltins.h"
  92 #include "jscntxt.h"
  93 #include "jsversion.h"
  94 #include "jsdbgapi.h" /* for js_TraceWatchPoints */
  95 #include "jsfun.h"
  96 #include "jsgc.h"
  97 #include "jsinterp.h"
  98 #include "jsiter.h"
  99 #include "jslock.h"
 100 #include "jsnum.h"
 101 #include "jsobj.h"
 102 #include "jsscope.h"
 103 #include "jsstr.h"
 104 #include "jsstaticcheck.h"
 105 #include "jsvector.h"
 106 #include "jswrapper.h"
 107
 108 #include "jsatominlines.h"
 109 #include "jscntxtinlines.h"
 110 #include "jsinterpinlines.h"
 111 #include "jsobjinlines.h"
 112
 113 using namespace js;
 114 using namespace js::gc;
 115
 116 /* 2^32 - 1 as a number and a string */
 117 #define MAXINDEX 4294967295u
 118 #define MAXSTR   "4294967295"
 119
 120 static inline bool
 121 ENSURE_SLOW_ARRAY(JSContext *cx, JSObject *obj)
 122 {
 123     return obj->getClass() == &js_SlowArrayClass ||
 124            obj->makeDenseArraySlow(cx);
 125 }
 126
 127 /*
 128  * Determine if the id represents an array index or an XML property index.
 129  *
 130  * An id is an array index according to ECMA by (15.4):
 131  *
 132  * "Array objects give special treatment to a certain class of property names.
 133  * A property name P (in the form of a string value) is an array index if and
 134  * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
 135  * to 2^32-1."
 136  *
 137  * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
 138  * except that by using signed 31-bit integers we miss the top half of the
 139  * valid range. This function checks the string representation itself; note
 140  * that calling a standard conversion routine might allow strings such as
 141  * "08" or "4.0" as array indices, which they are not.
 142  *
 143  * 'id' is passed as a jsboxedword since the given id need not necessarily hold
 144  * an atomized string.
 145  */
 146 bool
 147 js_StringIsIndex(JSLinearString *str, jsuint *indexp)
 148 {
 149     const jschar *cp = str->chars();
 150     if (JS7_ISDEC(*cp) && str->length() < sizeof(MAXSTR)) {
 151         jsuint index = JS7_UNDEC(*cp++);
 152         jsuint oldIndex = 0;
 153         jsuint c = 0;
 154         if (index != 0) {
 155             while (JS7_ISDEC(*cp)) {
 156                 oldIndex = index;
 157                 c = JS7_UNDEC(*cp);
 158                 index = 10*index + c;
 159                 cp++;
 160             }
 161         }
 162
 163         /* Ensure that all characters were consumed and we didn't overflow. */
 164         if (*cp == 0 &&
 165              (oldIndex < (MAXINDEX / 10) ||
 166               (oldIndex == (MAXINDEX / 10) && c < (MAXINDEX % 10))))
 167         {
 168             *indexp = index;
 169             return true;
 170         }
 171     }
 172     return false;
 173 }
 174
 175 static bool
 176 ValueToLength(JSContext *cx, Value* vp, jsuint* plength)
 177 {
 178     if (vp->isInt32()) {
 179         int32_t i = vp->toInt32();
 180         if (i < 0)
 181             goto error;
 182
 183         *plength = (jsuint)(i);
 184         return true;
 185     }
 186
 187     jsdouble d;
 188     if (!ValueToNumber(cx, *vp, &d))
 189         goto error;
 190
 191     if (JSDOUBLE_IS_NaN(d))
 192         goto error;
 193
 194     jsuint length;
 195     length = (jsuint) d;
 196     if (d != (jsdouble) length)
 197         goto error;
 198
 199
 200     *plength = length;
 201     return true;
 202
 203 error:
 204     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
 205                          JSMSG_BAD_ARRAY_LENGTH);
 206     return false;
 207 }
 208
 209 JSBool
 210 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
 211 {
 212     if (obj->isArray()) {
 213         *lengthp = obj->getArrayLength();
 214         return true;
 215     }
 216
 217     if (obj->isArguments() && !obj->isArgsLengthOverridden()) {
 218         *lengthp = obj->getArgsInitialLength();
 219         return true;
 220     }
 221
 222     AutoValueRooter tvr(cx);
 223     if (!obj->getProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.lengthAtom), tvr.addr()))
 224         return false;
 225
 226     if (tvr.value().isInt32()) {
 227         *lengthp = jsuint(jsint(tvr.value().toInt32())); /* jsuint cast does ToUint32 */
 228         return true;
 229     }
 230
 231     JS_STATIC_ASSERT(sizeof(jsuint) == sizeof(uint32_t));
 232     return ValueToECMAUint32(cx, tvr.value(), (uint32_t *)lengthp);
 233 }
 234
 235 JSBool JS_FASTCALL
 236 js_IndexToId(JSContext *cx, jsuint index, jsid *idp)
 237 {
 238     JSString *str;
 239
 240     if (index <= JSID_INT_MAX) {
 241         *idp = INT_TO_JSID(index);
 242         return JS_TRUE;
 243     }
 244     str = js_NumberToString(cx, index);
 245     if (!str)
 246         return JS_FALSE;
 247     return js_ValueToStringId(cx, StringValue(str), idp);
 248 }
 249
 250 static JSBool
 251 BigIndexToId(JSContext *cx, JSObject *obj, jsuint index, JSBool createAtom,
 252              jsid *idp)
 253 {
 254     jschar buf[10], *start;
 255     Class *clasp;
 256     JSAtom *atom;
 257     JS_STATIC_ASSERT((jsuint)-1 == 4294967295U);
 258
 259     JS_ASSERT(index > JSID_INT_MAX);
 260
 261     start = JS_ARRAY_END(buf);
 262     do {
 263         --start;
 264         *start = (jschar)('0' + index % 10);
 265         index /= 10;
 266     } while (index != 0);
 267
 268     /*
 269      * Skip the atomization if the class is known to store atoms corresponding
 270      * to big indexes together with elements. In such case we know that the
 271      * array does not have an element at the given index if its atom does not
 272      * exist.  Fast arrays (clasp == &js_ArrayClass) don't use atoms for
 273      * any indexes, though it would be rare to see them have a big index
 274      * in any case.
 275      */
 276     if (!createAtom &&
 277         ((clasp = obj->getClass()) == &js_SlowArrayClass ||
 278          clasp == &js_ArgumentsClass ||
 279          clasp == &js_ObjectClass)) {
 280         atom = js_GetExistingStringAtom(cx, start, JS_ARRAY_END(buf) - start);
 281         if (!atom) {
 282             *idp = JSID_VOID;
 283             return JS_TRUE;
 284         }
 285     } else {
 286         atom = js_AtomizeChars(cx, start, JS_ARRAY_END(buf) - start, 0);
 287         if (!atom)
 288             return JS_FALSE;
 289     }
 290
 291     *idp = ATOM_TO_JSID(atom);
 292     return JS_TRUE;
 293 }
 294
 295 bool
 296 JSObject::willBeSparseDenseArray(uintN requiredCapacity, uintN newElementsHint)
 297 {
 298     JS_ASSERT(isDenseArray());
 299     JS_ASSERT(requiredCapacity > MIN_SPARSE_INDEX);
 300
 301     uintN cap = numSlots();
 302     JS_ASSERT(requiredCapacity >= cap);
 303
 304     if (requiredCapacity >= JSObject::NSLOTS_LIMIT)
 305         return true;
 306
 307     uintN minimalDenseCount = requiredCapacity / 4;
 308     if (newElementsHint >= minimalDenseCount)
 309         return false;
 310     minimalDenseCount -= newElementsHint;
 311
 312     if (minimalDenseCount > cap)
 313         return true;
 314
 315     Value *elems = getDenseArrayElements();
 316     for (uintN i = 0; i < cap; i++) {
 317         if (!elems[i].isMagic(JS_ARRAY_HOLE) && !--minimalDenseCount)
 318             return false;
 319     }
 320     return true;
 321 }
 322
 323 static bool
 324 ReallyBigIndexToId(JSContext* cx, jsdouble index, jsid* idp)
 325 {
 326     return js_ValueToStringId(cx, DoubleValue(index), idp);
 327 }
 328
 329 static bool
 330 IndexToId(JSContext* cx, JSObject* obj, jsdouble index, JSBool* hole, jsid* idp,
 331           JSBool createAtom = JS_FALSE)
 332 {
 333     if (index <= JSID_INT_MAX) {
 334         *idp = INT_TO_JSID(int(index));
 335         return JS_TRUE;
 336     }
 337
 338     if (index <= jsuint(-1)) {
 339         if (!BigIndexToId(cx, obj, jsuint(index), createAtom, idp))
 340             return JS_FALSE;
 341         if (hole && JSID_IS_VOID(*idp))
 342             *hole = JS_TRUE;
 343         return JS_TRUE;
 344     }
 345
 346     return ReallyBigIndexToId(cx, index, idp);
 347 }
 348
 349 /*
 350  * If the property at the given index exists, get its value into location
 351  * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
 352  * to JSVAL_VOID. This function assumes that the location pointed by vp is
 353  * properly rooted and can be used as GC-protected storage for temporaries.
 354  */
 355 static JSBool
 356 GetElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole, Value *vp)
 357 {
 358     JS_ASSERT(index >= 0);
 359     if (obj->isDenseArray() && index < obj->getDenseArrayCapacity() &&
 360         !(*vp = obj->getDenseArrayElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
 361         *hole = JS_FALSE;
 362         return JS_TRUE;
 363     }
 364     if (obj->isArguments() &&
 365         index < obj->getArgsInitialLength() &&
 366         !(*vp = obj->getArgsElement(uint32(index))).isMagic(JS_ARGS_HOLE)) {
 367         *hole = JS_FALSE;
 368         JSStackFrame *fp = (JSStackFrame *)obj->getPrivate();
 369         if (fp != JS_ARGUMENTS_OBJECT_ON_TRACE) {
 370             if (fp)
 371                 *vp = fp->canonicalActualArg(index);
 372             return JS_TRUE;
 373         }
 374     }
 375
 376     AutoIdRooter idr(cx);
 377
 378     *hole = JS_FALSE;
 379     if (!IndexToId(cx, obj, index, hole, idr.addr()))
 380         return JS_FALSE;
 381     if (*hole) {
 382         vp->setUndefined();
 383         return JS_TRUE;
 384     }
 385
 386     JSObject *obj2;
 387     JSProperty *prop;
 388     if (!obj->lookupProperty(cx, idr.id(), &obj2, &prop))
 389         return JS_FALSE;
 390     if (!prop) {
 391         *hole = JS_TRUE;
 392         vp->setUndefined();
 393     } else {
 394         if (!obj->getProperty(cx, idr.id(), vp))
 395             return JS_FALSE;
 396         *hole = JS_FALSE;
 397     }
 398     return JS_TRUE;
 399 }
 400
 401 namespace js {
 402
 403 bool
 404 GetElements(JSContext *cx, JSObject *aobj, jsuint length, Value *vp)
 405 {
 406     if (aobj->isDenseArray() && length <= aobj->getDenseArrayCapacity() &&
 407         !js_PrototypeHasIndexedProperties(cx, aobj)) {
 408         /* The prototype does not have indexed properties so hole = undefined */
 409         Value *srcbeg = aobj->getDenseArrayElements();
 410         Value *srcend = srcbeg + length;
 411         for (Value *dst = vp, *src = srcbeg; src < srcend; ++dst, ++src)
 412             *dst = src->isMagic(JS_ARRAY_HOLE) ? UndefinedValue() : *src;
 413     } else if (aobj->isArguments() && !aobj->isArgsLengthOverridden() &&
 414                !js_PrototypeHasIndexedProperties(cx, aobj)) {
 415         /*
 416          * Two cases, two loops: note how in the case of an active stack frame
 417          * backing aobj, even though we copy from fp->argv, we still must check
 418          * aobj->getArgsElement(i) for a hole, to handle a delete on the
 419          * corresponding arguments element. See args_delProperty.
 420          */
 421         if (JSStackFrame *fp = (JSStackFrame *) aobj->getPrivate()) {
 422             JS_ASSERT(fp->numActualArgs() <= JS_ARGS_LENGTH_MAX);
 423             fp->forEachCanonicalActualArg(CopyNonHoleArgsTo(aobj, vp));
 424         } else {
 425             Value *srcbeg = aobj->getArgsElements();
 426             Value *srcend = srcbeg + length;
 427             for (Value *dst = vp, *src = srcbeg; src < srcend; ++dst, ++src)
 428                 *dst = src->isMagic(JS_ARGS_HOLE) ? UndefinedValue() : *src;
 429         }
 430     } else {
 431         for (uintN i = 0; i < length; i++) {
 432             if (!aobj->getProperty(cx, INT_TO_JSID(jsint(i)), &vp[i]))
 433                 return JS_FALSE;
 434         }
 435     }
 436
 437     return true;
 438 }
 439
 440 }
 441
 442 /*
 443  * Set the value of the property at the given index to v assuming v is rooted.
 444  */
 445 static JSBool
 446 SetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, const Value &v)
 447 {
 448     JS_ASSERT(index >= 0);
 449
 450     if (obj->isDenseArray()) {
 451         /* Predicted/prefetched code should favor the remains-dense case. */
 452         JSObject::EnsureDenseResult result = JSObject::ED_SPARSE;
 453         do {
 454             if (index > jsuint(-1))
 455                 break;
 456             jsuint idx = jsuint(index);
 457             result = obj->ensureDenseArrayElements(cx, idx, 1);
 458             if (result != JSObject::ED_OK)
 459                 break;
 460             if (idx >= obj->getArrayLength())
 461                 obj->setArrayLength(idx + 1);
 462             obj->setDenseArrayElement(idx, v);
 463             return true;
 464         } while (false);
 465
 466         if (result == JSObject::ED_FAILED)
 467             return false;
 468         JS_ASSERT(result == JSObject::ED_SPARSE);
 469         if (!obj->makeDenseArraySlow(cx))
 470             return JS_FALSE;
 471     }
 472
 473     AutoIdRooter idr(cx);
 474
 475     if (!IndexToId(cx, obj, index, NULL, idr.addr(), JS_TRUE))
 476         return JS_FALSE;
 477     JS_ASSERT(!JSID_IS_VOID(idr.id()));
 478
 479     Value tmp = v;
 480     return obj->setProperty(cx, idr.id(), &tmp, true);
 481 }
 482
 483 #ifdef JS_TRACER
 484 JSBool JS_FASTCALL
 485 js_EnsureDenseArrayCapacity(JSContext *cx, JSObject *obj, jsint i)
 486 {
 487 #ifdef DEBUG
 488     Class *origObjClasp = obj->clasp;
 489 #endif
 490     jsuint u = jsuint(i);
 491     JSBool ret = (obj->ensureDenseArrayElements(cx, u, 1) == JSObject::ED_OK);
 492
 493     /* Partially check the CallInfo's storeAccSet is correct. */
 494     JS_ASSERT(obj->clasp == origObjClasp);
 495     return ret;
 496 }
 497 /* This function and its callees do not touch any object's .clasp field. */
 498 JS_DEFINE_CALLINFO_3(extern, BOOL, js_EnsureDenseArrayCapacity, CONTEXT, OBJECT, INT32,
 499                      0, nanojit::ACCSET_STORE_ANY & ~tjit::ACCSET_OBJ_CLASP)
 500 #endif
 501
 502 /*
 503  * Delete the element |index| from |obj|. If |strict|, do a strict
 504  * deletion: throw if the property is not configurable.
 505  *
 506  * - Return 1 if the deletion succeeds (that is, ES5's [[Delete]] would
 507  *   return true)
 508  *
 509  * - Return 0 if the deletion fails because the property is not
 510  *   configurable (that is, [[Delete]] would return false). Note that if
 511  *   |strict| is true we will throw, not return zero.
 512  *
 513  * - Return -1 if an exception occurs (that is, [[Delete]] would throw).
 514  */
 515 static int
 516 DeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index, bool strict)
 517 {
 518     JS_ASSERT(index >= 0);
 519     if (obj->isDenseArray()) {
 520         if (index <= jsuint(-1)) {
 521             jsuint idx = jsuint(index);
 522             if (idx < obj->getDenseArrayCapacity()) {
 523                 obj->setDenseArrayElement(idx, MagicValue(JS_ARRAY_HOLE));
 524                 if (!js_SuppressDeletedIndexProperties(cx, obj, idx, idx+1))
 525                     return -1;
 526             }
 527         }
 528         return 1;
 529     }
 530
 531     AutoIdRooter idr(cx);
 532
 533     if (!IndexToId(cx, obj, index, NULL, idr.addr()))
 534         return -1;
 535     if (JSID_IS_VOID(idr.id()))
 536         return 1;
 537
 538     Value v;
 539     if (!obj->deleteProperty(cx, idr.id(), &v, strict))
 540         return -1;
 541     return v.isTrue() ? 1 : 0;
 542 }
 543
 544 /*
 545  * When hole is true, delete the property at the given index. Otherwise set
 546  * its value to v assuming v is rooted.
 547  */
 548 static JSBool
 549 SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index,
 550                         JSBool hole, const Value &v)
 551 {
 552     if (hole) {
 553         JS_ASSERT(v.isUndefined());
 554         return DeleteArrayElement(cx, obj, index, true) >= 0;
 555     }
 556     return SetArrayElement(cx, obj, index, v);
 557 }
 558
 559 JSBool
 560 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsdouble length)
 561 {
 562     Value v;
 563     jsid id;
 564
 565     v.setNumber(length);
 566     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
 567     /* We don't support read-only array length yet. */
 568     return obj->setProperty(cx, id, &v, false);
 569 }
 570
 571 JSBool
 572 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
 573 {
 574     JSErrorReporter older = JS_SetErrorReporter(cx, NULL);
 575     AutoValueRooter tvr(cx);
 576     jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
 577     JSBool ok = obj->getProperty(cx, id, tvr.addr());
 578     JS_SetErrorReporter(cx, older);
 579     if (!ok)
 580         return false;
 581
 582     if (!ValueToLength(cx, tvr.addr(), lengthp))
 583         return false;
 584
 585     return true;
 586 }
 587
 588 /*
 589  * Since SpiderMonkey supports cross-class prototype-based delegation, we have
 590  * to be careful about the length getter and setter being called on an object
 591  * not of Array class. For the getter, we search obj's prototype chain for the
 592  * array that caused this getter to be invoked. In the setter case to overcome
 593  * the JSPROP_SHARED attribute, we must define a shadowing length property.
 594  */
 595 static JSBool
 596 array_length_getter(JSContext *cx, JSObject *obj, jsid id, Value *vp)
 597 {
 598     do {
 599         if (obj->isArray()) {
 600             vp->setNumber(obj->getArrayLength());
 601             return JS_TRUE;
 602         }
 603     } while ((obj = obj->getProto()) != NULL);
 604     return JS_TRUE;
 605 }
 606
 607 static JSBool
 608 array_length_setter(JSContext *cx, JSObject *obj, jsid id, JSBool strict, Value *vp)
 609 {
 610     jsuint newlen, oldlen, gap, index;
 611     Value junk;
 612
 613     if (!obj->isArray()) {
 614         jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
 615
 616         return obj->defineProperty(cx, lengthId, *vp, NULL, NULL, JSPROP_ENUMERATE);
 617     }
 618
 619     if (!ValueToLength(cx, vp, &newlen))
 620         return false;
 621
 622     oldlen = obj->getArrayLength();
 623
 624     if (oldlen == newlen)
 625         return true;
 626
 627     vp->setNumber(newlen);
 628     if (oldlen < newlen) {
 629         obj->setArrayLength(newlen);
 630         return true;
 631     }
 632
 633     if (obj->isDenseArray()) {
 634         /*
 635          * Don't reallocate if we're not actually shrinking our slots. If we do
 636          * shrink slots here, ensureDenseArrayElements will fill all slots to the
 637          * right of newlen with JS_ARRAY_HOLE. This permits us to disregard
 638          * length when reading from arrays as long we are within the capacity.
 639          */
 640         jsuint oldcap = obj->getDenseArrayCapacity();
 641         if (oldcap > newlen)
 642             obj->shrinkDenseArrayElements(cx, newlen);
 643         obj->setArrayLength(newlen);
 644     } else if (oldlen - newlen < (1 << 24)) {
 645         do {
 646             --oldlen;
 647             if (!JS_CHECK_OPERATION_LIMIT(cx)) {
 648                 obj->setArrayLength(oldlen + 1);
 649                 return false;
 650             }
 651             int deletion = DeleteArrayElement(cx, obj, oldlen, strict);
 652             if (deletion <= 0) {
 653                 obj->setArrayLength(oldlen + 1);
 654                 return deletion >= 0;
 655             }
 656         } while (oldlen != newlen);
 657         obj->setArrayLength(newlen);
 658     } else {
 659         /*
 660          * We are going to remove a lot of indexes in a presumably sparse
 661          * array. So instead of looping through indexes between newlen and
 662          * oldlen, we iterate through all properties and remove those that
 663          * correspond to indexes in the half-open range [newlen, oldlen).  See
 664          * bug 322135.
 665          */
 666         JSObject *iter = JS_NewPropertyIterator(cx, obj);
 667         if (!iter)
 668             return false;
 669
 670         /* Protect iter against GC under JSObject::deleteProperty. */
 671         AutoObjectRooter tvr(cx, iter);
 672
 673         gap = oldlen - newlen;
 674         for (;;) {
 675             if (!JS_CHECK_OPERATION_LIMIT(cx) || !JS_NextProperty(cx, iter, &id))
 676                 return false;
 677             if (JSID_IS_VOID(id))
 678                 break;
 679             if (js_IdIsIndex(id, &index) && index - newlen < gap &&
 680                 !obj->deleteProperty(cx, id, &junk, false)) {
 681                 return false;
 682             }
 683         }
 684         obj->setArrayLength(newlen);
 685     }
 686
 687     return true;
 688 }
 689
 690 /*
 691  * We have only indexed properties up to capacity (excepting holes), plus the
 692  * length property. For all else, we delegate to the prototype.
 693  */
 694 static inline bool
 695 IsDenseArrayId(JSContext *cx, JSObject *obj, jsid id)
 696 {
 697     JS_ASSERT(obj->isDenseArray());
 698
 699     uint32 i;
 700     return JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom) ||
 701            (js_IdIsIndex(id, &i) &&
 702             obj->getArrayLength() != 0 &&
 703             i < obj->getDenseArrayCapacity() &&
 704             !obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE));
 705 }
 706
 707 static JSBool
 708 array_lookupProperty(JSContext *cx, JSObject *obj, jsid id, JSObject **objp,
 709                      JSProperty **propp)
 710 {
 711     if (!obj->isDenseArray())
 712         return js_LookupProperty(cx, obj, id, objp, propp);
 713
 714     if (IsDenseArrayId(cx, obj, id)) {
 715         *propp = (JSProperty *) 1;  /* non-null to indicate found */
 716         *objp = obj;
 717         return JS_TRUE;
 718     }
 719
 720     JSObject *proto = obj->getProto();
 721     if (!proto) {
 722         *objp = NULL;
 723         *propp = NULL;
 724         return JS_TRUE;
 725     }
 726     return proto->lookupProperty(cx, id, objp, propp);
 727 }
 728
 729 JSBool
 730 js_GetDenseArrayElementValue(JSContext *cx, JSObject *obj, jsid id, Value *vp)
 731 {
 732     JS_ASSERT(obj->isDenseArray());
 733
 734     uint32 i;
 735     if (!js_IdIsIndex(id, &i)) {
 736         JS_ASSERT(JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom));
 737         vp->setNumber(obj->getArrayLength());
 738         return JS_TRUE;
 739     }
 740     *vp = obj->getDenseArrayElement(i);
 741     return JS_TRUE;
 742 }
 743
 744 static JSBool
 745 array_getProperty(JSContext *cx, JSObject *obj, JSObject *receiver, jsid id, Value *vp)
 746 {
 747     uint32 i;
 748
 749     if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom)) {
 750         vp->setNumber(obj->getArrayLength());
 751         return JS_TRUE;
 752     }
 753
 754     if (JSID_IS_ATOM(id, cx->runtime->atomState.protoAtom)) {
 755         vp->setObjectOrNull(obj->getProto());
 756         return JS_TRUE;
 757     }
 758
 759     if (!obj->isDenseArray())
 760         return js_GetProperty(cx, obj, id, vp);
 761
 762     if (!js_IdIsIndex(id, &i) || i >= obj->getDenseArrayCapacity() ||
 763         obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) {
 764         JSObject *obj2;
 765         JSProperty *prop;
 766         const Shape *shape;
 767
 768         JSObject *proto = obj->getProto();
 769         if (!proto) {
 770             vp->setUndefined();
 771             return JS_TRUE;
 772         }
 773
 774         vp->setUndefined();
 775         if (js_LookupPropertyWithFlags(cx, proto, id, cx->resolveFlags,
 776                                        &obj2, &prop) < 0)
 777             return JS_FALSE;
 778
 779         if (prop && obj2->isNative()) {
 780             shape = (const Shape *) prop;
 781             if (!js_NativeGet(cx, obj, obj2, shape, JSGET_METHOD_BARRIER, vp))
 782                 return JS_FALSE;
 783         }
 784         return JS_TRUE;
 785     }
 786
 787     *vp = obj->getDenseArrayElement(i);
 788     return JS_TRUE;
 789 }
 790
 791 static JSBool
 792 slowarray_addProperty(JSContext *cx, JSObject *obj, jsid id, Value *vp)
 793 {
 794     jsuint index, length;
 795
 796     if (!js_IdIsIndex(id, &index))
 797         return JS_TRUE;
 798     length = obj->getArrayLength();
 799     if (index >= length)
 800         obj->setArrayLength(index + 1);
 801     return JS_TRUE;
 802 }
 803
 804 static JSType
 805 array_typeOf(JSContext *cx, JSObject *obj)
 806 {
 807     return JSTYPE_OBJECT;
 808 }
 809
 810 static JSBool
 811 array_setProperty(JSContext *cx, JSObject *obj, jsid id, Value *vp, JSBool strict)
 812 {
 813     uint32 i;
 814
 815     if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom))
 816         return array_length_setter(cx, obj, id, strict, vp);
 817
 818     if (!obj->isDenseArray())
 819         return js_SetProperty(cx, obj, id, vp, strict);
 820
 821     do {
 822         if (!js_IdIsIndex(id, &i))
 823             break;
 824         if (js_PrototypeHasIndexedProperties(cx, obj))
 825             break;
 826
 827         JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, i, 1);
 828         if (result != JSObject::ED_OK) {
 829             if (result == JSObject::ED_FAILED)
 830                 return false;
 831             JS_ASSERT(result == JSObject::ED_SPARSE);
 832             break;
 833         }
 834
 835         if (i >= obj->getArrayLength())
 836             obj->setArrayLength(i + 1);
 837         obj->setDenseArrayElement(i, *vp);
 838         return true;
 839     } while (false);
 840
 841     if (!obj->makeDenseArraySlow(cx))
 842         return false;
 843     return js_SetProperty(cx, obj, id, vp, strict);
 844 }
 845
 846 JSBool
 847 js_PrototypeHasIndexedProperties(JSContext *cx, JSObject *obj)
 848 {
 849     /*
 850      * Walk up the prototype chain and see if this indexed element already
 851      * exists. If we hit the end of the prototype chain, it's safe to set the
 852      * element on the original object.
 853      */
 854     while ((obj = obj->getProto()) != NULL) {
 855         /*
 856          * If the prototype is a non-native object (possibly a dense array), or
 857          * a native object (possibly a slow array) that has indexed properties,
 858          * return true.
 859          */
 860         if (!obj->isNative())
 861             return JS_TRUE;
 862         if (obj->isIndexed())
 863             return JS_TRUE;
 864     }
 865     return JS_FALSE;
 866 }
 867
 868 static JSBool
 869 array_defineProperty(JSContext *cx, JSObject *obj, jsid id, const Value *value,
 870                      PropertyOp getter, StrictPropertyOp setter, uintN attrs)
 871 {
 872     if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom))
 873         return JS_TRUE;
 874
 875     if (!obj->isDenseArray())
 876         return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
 877
 878     do {
 879         uint32 i = 0;       // init to shut GCC up
 880         bool isIndex = js_IdIsIndex(id, &i);
 881         if (!isIndex || attrs != JSPROP_ENUMERATE)
 882             break;
 883
 884         JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, i, 1);
 885         if (result != JSObject::ED_OK) {
 886             if (result == JSObject::ED_FAILED)
 887                 return false;
 888             JS_ASSERT(result == JSObject::ED_SPARSE);
 889             break;
 890         }
 891
 892         if (i >= obj->getArrayLength())
 893             obj->setArrayLength(i + 1);
 894         obj->setDenseArrayElement(i, *value);
 895         return true;
 896     } while (false);
 897
 898     if (!obj->makeDenseArraySlow(cx))
 899         return false;
 900     return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
 901 }
 902
 903 static JSBool
 904 array_getAttributes(JSContext *cx, JSObject *obj, jsid id, uintN *attrsp)
 905 {
 906     *attrsp = JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom)
 907         ? JSPROP_PERMANENT : JSPROP_ENUMERATE;
 908     return JS_TRUE;
 909 }
 910
 911 static JSBool
 912 array_setAttributes(JSContext *cx, JSObject *obj, jsid id, uintN *attrsp)
 913 {
 914     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
 915                          JSMSG_CANT_SET_ARRAY_ATTRS);
 916     return JS_FALSE;
 917 }
 918
 919 static JSBool
 920 array_deleteProperty(JSContext *cx, JSObject *obj, jsid id, Value *rval, JSBool strict)
 921 {
 922     uint32 i;
 923
 924     if (!obj->isDenseArray())
 925         return js_DeleteProperty(cx, obj, id, rval, strict);
 926
 927     if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom)) {
 928         rval->setBoolean(false);
 929         return JS_TRUE;
 930     }
 931
 932     if (js_IdIsIndex(id, &i) && i < obj->getDenseArrayCapacity())
 933         obj->setDenseArrayElement(i, MagicValue(JS_ARRAY_HOLE));
 934
 935     if (!js_SuppressDeletedProperty(cx, obj, id))
 936         return false;
 937
 938     rval->setBoolean(true);
 939     return JS_TRUE;
 940 }
 941
 942 static void
 943 array_trace(JSTracer *trc, JSObject *obj)
 944 {
 945     JS_ASSERT(obj->isDenseArray());
 946
 947     uint32 capacity = obj->getDenseArrayCapacity();
 948     for (uint32 i = 0; i < capacity; i++)
 949         MarkValue(trc, obj->getDenseArrayElement(i), "dense_array_elems");
 950 }
 951
 952 static JSBool
 953 array_fix(JSContext *cx, JSObject *obj, bool *success, AutoIdVector *props)
 954 {
 955     JS_ASSERT(obj->isDenseArray());
 956
 957     /*
 958      * We must slowify dense arrays; otherwise, we'd need to detect assignments to holes,
 959      * since that is effectively adding a new property to the array.
 960      */
 961     if (!obj->makeDenseArraySlow(cx) ||
 962         !GetPropertyNames(cx, obj, JSITER_HIDDEN | JSITER_OWNONLY, props))
 963         return false;
 964
 965     *success = true;
 966     return true;
 967 }
 968
 969 Class js_ArrayClass = {
 970     "Array",
 971     Class::NON_NATIVE |
 972     JSCLASS_HAS_PRIVATE |
 973     JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
 974     PropertyStub,         /* addProperty */
 975     PropertyStub,         /* delProperty */
 976     PropertyStub,         /* getProperty */
 977     StrictPropertyStub,   /* setProperty */
 978     EnumerateStub,
 979     ResolveStub,
 980     js_TryValueOf,
 981     NULL,
 982     NULL,           /* reserved0   */
 983     NULL,           /* checkAccess */
 984     NULL,           /* call        */
 985     NULL,           /* construct   */
 986     NULL,           /* xdrObject   */
 987     NULL,           /* hasInstance */
 988     NULL,           /* mark        */
 989     JS_NULL_CLASS_EXT,
 990     {
 991         array_lookupProperty,
 992         array_defineProperty,
 993         array_getProperty,
 994         array_setProperty,
 995         array_getAttributes,
 996         array_setAttributes,
 997         array_deleteProperty,
 998         NULL,       /* enumerate      */
 999         array_typeOf,
1000         array_trace,
1001         array_fix,
1002         NULL,       /* thisObject     */
1003         NULL,       /* clear          */
1004     }
1005 };
1006
1007 Class js_SlowArrayClass = {
1008     "Array",
1009     JSCLASS_HAS_PRIVATE |
1010     JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
1011     slowarray_addProperty,
1012     PropertyStub,         /* delProperty */
1013     PropertyStub,         /* getProperty */
1014     StrictPropertyStub,   /* setProperty */
1015     EnumerateStub,
1016     ResolveStub,
1017     js_TryValueOf
1018 };
1019
1020 static bool
1021 AddLengthProperty(JSContext *cx, JSObject *obj)
1022 {
1023     const jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
1024     JS_ASSERT(!obj->nativeLookup(lengthId));
1025
1026     return obj->addProperty(cx, lengthId, array_length_getter, array_length_setter,
1027                             SHAPE_INVALID_SLOT, JSPROP_PERMANENT | JSPROP_SHARED, 0, 0);
1028 }
1029
1030 /*
1031  * Convert an array object from fast-and-dense to slow-and-flexible.
1032  */
1033 JSBool
1034 JSObject::makeDenseArraySlow(JSContext *cx)
1035 {
1036     JS_ASSERT(isDenseArray());
1037
1038     /*
1039      * Save old map now, before calling InitScopeForObject. We'll have to undo
1040      * on error. This is gross, but a better way is not obvious.
1041      */
1042     JSObjectMap *oldMap = map;
1043
1044     /* Create a native scope. */
1045     JSObject *arrayProto = getProto();
1046     js::gc::FinalizeKind kind = js::gc::FinalizeKind(arena()->header()->thingKind);
1047     if (!InitScopeForObject(cx, this, &js_SlowArrayClass, arrayProto, kind))
1048         return false;
1049
1050     uint32 capacity = getDenseArrayCapacity();
1051
1052     /*
1053      * Begin with the length property to share more of the property tree.
1054      * The getter/setter here will directly access the object's private value.
1055      */
1056     if (!AddLengthProperty(cx, this)) {
1057         setMap(oldMap);
1058         return false;
1059     }
1060
1061     /*
1062      * Create new properties pointing to existing elements. Pack the array to
1063      * remove holes, so that shapes use successive slots (as for other objects).
1064      */
1065     uint32 next = 0;
1066     for (uint32 i = 0; i < capacity; i++) {
1067         jsid id;
1068         if (!ValueToId(cx, Int32Value(i), &id)) {
1069             setMap(oldMap);
1070             return false;
1071         }
1072
1073         if (getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE))
1074             continue;
1075
1076         setDenseArrayElement(next, getDenseArrayElement(i));
1077
1078         if (!addDataProperty(cx, id, next, JSPROP_ENUMERATE)) {
1079             setMap(oldMap);
1080             return false;
1081         }
1082
1083         next++;
1084     }
1085
1086     /*
1087      * Dense arrays with different numbers of slots but the same number of fixed
1088      * slots and the same non-hole indexes must use their fixed slots consistently.
1089      */
1090     if (hasSlotsArray() && next <= numFixedSlots())
1091         revertToFixedSlots(cx);
1092
1093     ClearValueRange(slots + next, this->capacity - next, false);
1094
1095     /*
1096      * Finally, update class. If |this| is Array.prototype, then js_InitClass
1097      * will create an emptyShape whose class is &js_SlowArrayClass, to ensure
1098      * that delegating instances can share shapes in the tree rooted at the
1099      * proto's empty shape.
1100      */
1101     clasp = &js_SlowArrayClass;
1102     return true;
1103 }
1104
1105 /* Transfer ownership of buffer to returned string. */
1106 static inline JSBool
1107 BufferToString(JSContext *cx, StringBuffer &sb, Value *rval)
1108 {
1109     JSString *str = sb.finishString();
1110     if (!str)
1111         return false;
1112     rval->setString(str);
1113     return true;
1114 }
1115
1116 #if JS_HAS_TOSOURCE
1117 static JSBool
1118 array_toSource(JSContext *cx, uintN argc, Value *vp)
1119 {
1120     JS_CHECK_RECURSION(cx, return false);
1121
1122     JSObject *obj = ToObject(cx, &vp[1]);
1123     if (!obj)
1124         return false;
1125     if (!obj->isSlowArray() && !InstanceOf(cx, obj, &js_ArrayClass, vp + 2))
1126         return false;
1127
1128     /* Find joins or cycles in the reachable object graph. */
1129     jschar *sharpchars;
1130     JSHashEntry *he = js_EnterSharpObject(cx, obj, NULL, &sharpchars);
1131     if (!he)
1132         return false;
1133     bool initiallySharp = IS_SHARP(he);
1134
1135     /* After this point, all paths exit through the 'out' label. */
1136     MUST_FLOW_THROUGH("out");
1137     bool ok = false;
1138
1139     /*
1140      * This object will take responsibility for the jschar buffer until the
1141      * buffer is transferred to the returned JSString.
1142      */
1143     StringBuffer sb(cx);
1144
1145     /* Cycles/joins are indicated by sharp objects. */
1146 #if JS_HAS_SHARP_VARS
1147     if (IS_SHARP(he)) {
1148         JS_ASSERT(sharpchars != 0);
1149         sb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1150         goto make_string;
1151     } else if (sharpchars) {
1152         MAKE_SHARP(he);
1153         sb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1154     }
1155 #else
1156     if (IS_SHARP(he)) {
1157         if (!sb.append("[]"))
1158             goto out;
1159         cx->free(sharpchars);
1160         goto make_string;
1161     }
1162 #endif
1163
1164     if (!sb.append('['))
1165         goto out;
1166
1167     jsuint length;
1168     if (!js_GetLengthProperty(cx, obj, &length))
1169         goto out;
1170
1171     for (jsuint index = 0; index < length; index++) {
1172         /* Use vp to locally root each element value. */
1173         JSBool hole;
1174         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1175             !GetElement(cx, obj, index, &hole, vp)) {
1176             goto out;
1177         }
1178
1179         /* Get element's character string. */
1180         JSString *str;
1181         if (hole) {
1182             str = cx->runtime->emptyString;
1183         } else {
1184             str = js_ValueToSource(cx, *vp);
1185             if (!str)
1186                 goto out;
1187         }
1188         vp->setString(str);
1189
1190         const jschar *chars = str->getChars(cx);
1191         if (!chars)
1192             goto out;
1193
1194         /* Append element to buffer. */
1195         if (!sb.append(chars, chars + str->length()))
1196             goto out;
1197         if (index + 1 != length) {
1198             if (!sb.append(", "))
1199                 goto out;
1200         } else if (hole) {
1201             if (!sb.append(','))
1202                 goto out;
1203         }
1204     }
1205
1206     /* Finalize the buffer. */
1207     if (!sb.append(']'))
1208         goto out;
1209
1210   make_string:
1211     if (!BufferToString(cx, sb, vp))
1212         goto out;
1213
1214     ok = true;
1215
1216   out:
1217     if (!initiallySharp)
1218         js_LeaveSharpObject(cx, NULL);
1219     return ok;
1220 }
1221 #endif
1222
1223 static JSBool
1224 array_toString_sub(JSContext *cx, JSObject *obj, JSBool locale,
1225                    JSString *sepstr, Value *rval)
1226 {
1227     JS_CHECK_RECURSION(cx, return false);
1228
1229     /* Get characters to use for the separator. */
1230     static const jschar comma = ',';
1231     const jschar *sep;
1232     size_t seplen;
1233     if (sepstr) {
1234         seplen = sepstr->length();
1235         sep = sepstr->getChars(cx);
1236         if (!sep)
1237             return false;
1238     } else {
1239         sep = &comma;
1240         seplen = 1;
1241     }
1242
1243     /*
1244      * Use HashTable entry as the cycle indicator. On first visit, create the
1245      * entry, and, when leaving, remove the entry.
1246      */
1247     BusyArraysMap::AddPtr hashp = cx->busyArrays.lookupForAdd(obj);
1248     uint32 genBefore;
1249     if (!hashp) {
1250         /* Not in hash table, so not a cycle. */
1251         if (!cx->busyArrays.add(hashp, obj))
1252             return false;
1253         genBefore = cx->busyArrays.generation();
1254     } else {
1255         /* Cycle, so return empty string. */
1256         rval->setString(ATOM_TO_STRING(cx->runtime->atomState.emptyAtom));
1257         return true;
1258     }
1259
1260     AutoObjectRooter tvr(cx, obj);
1261
1262     /* After this point, all paths exit through the 'out' label. */
1263     MUST_FLOW_THROUGH("out");
1264     bool ok = false;
1265
1266     /*
1267      * This object will take responsibility for the jschar buffer until the
1268      * buffer is transferred to the returned JSString.
1269      */
1270     StringBuffer sb(cx);
1271
1272     jsuint length;
1273     if (!js_GetLengthProperty(cx, obj, &length))
1274         goto out;
1275
1276     for (jsuint index = 0; index < length; index++) {
1277         /* Use rval to locally root each element value. */
1278         JSBool hole;
1279         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1280             !GetElement(cx, obj, index, &hole, rval)) {
1281             goto out;
1282         }
1283
1284         /* Get element's character string. */
1285         if (!(hole || rval->isNullOrUndefined())) {
1286             if (locale) {
1287                 /* Work on obj.toLocalString() instead. */
1288                 JSObject *robj;
1289
1290                 if (!js_ValueToObjectOrNull(cx, *rval, &robj))
1291                     goto out;
1292                 rval->setObjectOrNull(robj);
1293                 JSAtom *atom = cx->runtime->atomState.toLocaleStringAtom;
1294                 if (!js_TryMethod(cx, robj, atom, 0, NULL, rval))
1295                     goto out;
1296             }
1297
1298             if (!ValueToStringBuffer(cx, *rval, sb))
1299                 goto out;
1300         }
1301
1302         /* Append the separator. */
1303         if (index + 1 != length) {
1304             if (!sb.append(sep, seplen))
1305                 goto out;
1306         }
1307     }
1308
1309     /* Finalize the buffer. */
1310     if (!BufferToString(cx, sb, rval))
1311         goto out;
1312
1313     ok = true;
1314
1315   out:
1316     if (genBefore == cx->busyArrays.generation())
1317         cx->busyArrays.remove(hashp);
1318     else
1319         cx->busyArrays.remove(obj);
1320     return ok;
1321 }
1322
1323 /* ES5 15.4.4.2. NB: The algorithm here differs from the one in ES3. */
1324 static JSBool
1325 array_toString(JSContext *cx, uintN argc, Value *vp)
1326 {
1327     JSObject *obj = ToObject(cx, &vp[1]);
1328     if (!obj)
1329         return false;
1330
1331     Value &join = vp[0];
1332     if (!obj->getProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.joinAtom), &join))
1333         return false;
1334
1335     if (!js_IsCallable(join)) {
1336         JSString *str = obj_toStringHelper(cx, obj);
1337         if (!str)
1338             return false;
1339         vp->setString(str);
1340         return true;
1341     }
1342
1343     LeaveTrace(cx);
1344     InvokeArgsGuard args;
1345     if (!cx->stack().pushInvokeArgs(cx, 0, &args))
1346         return false;
1347
1348     args.callee() = join;
1349     args.thisv().setObject(*obj);
1350
1351     /* Do the call. */
1352     if (!Invoke(cx, args, 0))
1353         return false;
1354     *vp = args.rval();
1355     return true;
1356 }
1357
1358 static JSBool
1359 array_toLocaleString(JSContext *cx, uintN argc, Value *vp)
1360 {
1361     JSObject *obj = ToObject(cx, &vp[1]);
1362     if (!obj)
1363         return false;
1364
1365     /*
1366      *  Passing comma here as the separator. Need a way to get a
1367      *  locale-specific version.
1368      */
1369     return array_toString_sub(cx, obj, JS_TRUE, NULL, vp);
1370 }
1371
1372 static JSBool
1373 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, Value *vector)
1374 {
1375     JS_ASSERT(count < MAXINDEX);
1376
1377     /*
1378      * Optimize for dense arrays so long as adding the given set of elements
1379      * wouldn't otherwise make the array slow.
1380      */
1381     do {
1382         if (!obj->isDenseArray())
1383             break;
1384         if (js_PrototypeHasIndexedProperties(cx, obj))
1385             break;
1386
1387         JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, start, count);
1388         if (result != JSObject::ED_OK) {
1389             if (result == JSObject::ED_FAILED)
1390                 return false;
1391             JS_ASSERT(result == JSObject::ED_SPARSE);
1392             break;
1393         }
1394         jsuint newlen = start + count;
1395         if (newlen > obj->getArrayLength())
1396             obj->setArrayLength(newlen);
1397
1398         JS_ASSERT(count < uint32(-1) / sizeof(Value));
1399         memcpy(obj->getDenseArrayElements() + start, vector, sizeof(jsval) * count);
1400         JS_ASSERT_IF(count != 0, !obj->getDenseArrayElement(newlen - 1).isMagic(JS_ARRAY_HOLE));
1401         return true;
1402     } while (false);
1403
1404     Value* end = vector + count;
1405     while (vector != end && start < MAXINDEX) {
1406         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1407             !SetArrayElement(cx, obj, start++, *vector++)) {
1408             return JS_FALSE;
1409         }
1410     }
1411
1412     if (vector == end)
1413         return JS_TRUE;
1414
1415     /* Finish out any remaining elements past the max array index. */
1416     if (obj->isDenseArray() && !ENSURE_SLOW_ARRAY(cx, obj))
1417         return JS_FALSE;
1418
1419     JS_ASSERT(start == MAXINDEX);
1420     AutoValueRooter tvr(cx);
1421     AutoIdRooter idr(cx);
1422     Value idval = DoubleValue(MAXINDEX);
1423     do {
1424         *tvr.addr() = *vector++;
1425         if (!js_ValueToStringId(cx, idval, idr.addr()) ||
1426             !obj->setProperty(cx, idr.id(), tvr.addr(), true)) {
1427             return JS_FALSE;
1428         }
1429         idval.getDoubleRef() += 1;
1430     } while (vector != end);
1431
1432     return JS_TRUE;
1433 }
1434
1435 static JSBool
1436 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, const Value *vector)
1437 {
1438     JS_ASSERT(obj->isArray());
1439
1440     JS_ASSERT(obj->isDenseArray());
1441     obj->setArrayLength(length);
1442     if (!vector || !length)
1443         return true;
1444
1445     /* Avoid ensureDenseArrayElements to skip sparse array checks there. */
1446     if (!obj->ensureSlots(cx, length))
1447         return false;
1448     memcpy(obj->getDenseArrayElements(), vector, length * sizeof(Value));
1449     return true;
1450 }
1451
1452 /*
1453  * Perl-inspired join, reverse, and sort.
1454  */
1455 static JSBool
1456 array_join(JSContext *cx, uintN argc, Value *vp)
1457 {
1458     JSString *str;
1459     if (argc == 0 || vp[2].isUndefined()) {
1460         str = NULL;
1461     } else {
1462         str = js_ValueToString(cx, vp[2]);
1463         if (!str)
1464             return JS_FALSE;
1465         vp[2].setString(str);
1466     }
1467     JSObject *obj = ToObject(cx, &vp[1]);
1468     if (!obj)
1469         return false;
1470     return array_toString_sub(cx, obj, JS_FALSE, str, vp);
1471 }
1472
1473 static JSBool
1474 array_reverse(JSContext *cx, uintN argc, Value *vp)
1475 {
1476     JSObject *obj = ToObject(cx, &vp[1]);
1477     if (!obj)
1478         return false;
1479
1480     jsuint len;
1481     if (!js_GetLengthProperty(cx, obj, &len))
1482         return false;
1483     vp->setObject(*obj);
1484
1485     do {
1486         if (!obj->isDenseArray())
1487             break;
1488         if (js_PrototypeHasIndexedProperties(cx, obj))
1489             break;
1490
1491         /* An empty array or an array with no elements is already reversed. */
1492         if (len == 0 || obj->getDenseArrayCapacity() == 0)
1493             return true;
1494
1495         /*
1496          * It's actually surprisingly complicated to reverse an array due to the
1497          * orthogonality of array length and array capacity while handling
1498          * leading and trailing holes correctly.  Reversing seems less likely to
1499          * be a common operation than other array mass-mutation methods, so for
1500          * now just take a probably-small memory hit (in the absence of too many
1501          * holes in the array at its start) and ensure that the capacity is
1502          * sufficient to hold all the elements in the array if it were full.
1503          */
1504         JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, len, 0);
1505         if (result != JSObject::ED_OK) {
1506             if (result == JSObject::ED_FAILED)
1507                 return false;
1508             JS_ASSERT(result == JSObject::ED_SPARSE);
1509             break;
1510         }
1511
1512         uint32 lo = 0, hi = len - 1;
1513         for (; lo < hi; lo++, hi--) {
1514             Value origlo = obj->getDenseArrayElement(lo);
1515             Value orighi = obj->getDenseArrayElement(hi);
1516             obj->setDenseArrayElement(lo, orighi);
1517             if (orighi.isMagic(JS_ARRAY_HOLE) &&
1518                 !js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(lo))) {
1519                 return false;
1520             }
1521             obj->setDenseArrayElement(hi, origlo);
1522             if (origlo.isMagic(JS_ARRAY_HOLE) &&
1523                 !js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(hi))) {
1524                 return false;
1525             }
1526         }
1527
1528         /*
1529          * Per ECMA-262, don't update the length of the array, even if the new
1530          * array has trailing holes (and thus the original array began with
1531          * holes).
1532          */
1533         return true;
1534     } while (false);
1535
1536     AutoValueRooter tvr(cx);
1537     for (jsuint i = 0, half = len / 2; i < half; i++) {
1538         JSBool hole, hole2;
1539         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1540             !GetElement(cx, obj, i, &hole, tvr.addr()) ||
1541             !GetElement(cx, obj, len - i - 1, &hole2, vp) ||
1542             !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, tvr.value()) ||
1543             !SetOrDeleteArrayElement(cx, obj, i, hole2, *vp)) {
1544             return false;
1545         }
1546     }
1547     vp->setObject(*obj);
1548     return true;
1549 }
1550
1551 typedef struct MSortArgs {
1552     size_t       elsize;
1553     JSComparator cmp;
1554     void         *arg;
1555     JSBool       isValue;
1556 } MSortArgs;
1557
1558 /* Helper function for js_MergeSort. */
1559 static JSBool
1560 MergeArrays(MSortArgs *msa, void *src, void *dest, size_t run1, size_t run2)
1561 {
1562     void *arg, *a, *b, *c;
1563     size_t elsize, runtotal;
1564     int cmp_result;
1565     JSComparator cmp;
1566     JSBool isValue;
1567
1568     runtotal = run1 + run2;
1569
1570     elsize = msa->elsize;
1571     cmp = msa->cmp;
1572     arg = msa->arg;
1573     isValue = msa->isValue;
1574
1575 #define CALL_CMP(a, b) \
1576     if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1577
1578     /* Copy runs already in sorted order. */
1579     b = (char *)src + run1 * elsize;
1580     a = (char *)b - elsize;
1581     CALL_CMP(a, b);
1582     if (cmp_result <= 0) {
1583         memcpy(dest, src, runtotal * elsize);
1584         return JS_TRUE;
1585     }
1586
1587 #define COPY_ONE(p,q,n) \
1588     (isValue ? (void)(*(Value*)p = *(Value*)q) : (void)memcpy(p, q, n))
1589
1590     a = src;
1591     c = dest;
1592     for (; runtotal != 0; runtotal--) {
1593         JSBool from_a = run2 == 0;
1594         if (!from_a && run1 != 0) {
1595             CALL_CMP(a,b);
1596             from_a = cmp_result <= 0;
1597         }
1598
1599         if (from_a) {
1600             COPY_ONE(c, a, elsize);
1601             run1--;
1602             a = (char *)a + elsize;
1603         } else {
1604             COPY_ONE(c, b, elsize);
1605             run2--;
1606             b = (char *)b + elsize;
1607         }
1608         c = (char *)c + elsize;
1609     }
1610 #undef COPY_ONE
1611 #undef CALL_CMP
1612
1613     return JS_TRUE;
1614 }
1615
1616 /*
1617  * This sort is stable, i.e. sequence of equal elements is preserved.
1618  * See also bug #224128.
1619  */
1620 bool
1621 js_MergeSort(void *src, size_t nel, size_t elsize,
1622              JSComparator cmp, void *arg, void *tmp,
1623              JSMergeSortElemType elemType)
1624 {
1625     void *swap, *vec1, *vec2;
1626     MSortArgs msa;
1627     size_t i, j, lo, hi, run;
1628     int cmp_result;
1629
1630     JS_ASSERT_IF(JS_SORTING_VALUES, elsize == sizeof(Value));
1631     bool isValue = elemType == JS_SORTING_VALUES;
1632
1633     /* Avoid memcpy overhead for word-sized and word-aligned elements. */
1634 #define COPY_ONE(p,q,n) \
1635     (isValue ? (void)(*(Value*)p = *(Value*)q) : (void)memcpy(p, q, n))
1636 #define CALL_CMP(a, b) \
1637     if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1638 #define INS_SORT_INT 4
1639
1640     /*
1641      * Apply insertion sort to small chunks to reduce the number of merge
1642      * passes needed.
1643      */
1644     for (lo = 0; lo < nel; lo += INS_SORT_INT) {
1645         hi = lo + INS_SORT_INT;
1646         if (hi >= nel)
1647             hi = nel;
1648         for (i = lo + 1; i < hi; i++) {
1649             vec1 = (char *)src + i * elsize;
1650             vec2 = (char *)vec1 - elsize;
1651             for (j = i; j > lo; j--) {
1652                 CALL_CMP(vec2, vec1);
1653                 /* "<=" instead of "<" insures the sort is stable */
1654                 if (cmp_result <= 0) {
1655                     break;
1656                 }
1657
1658                 /* Swap elements, using "tmp" as tmp storage */
1659                 COPY_ONE(tmp, vec2, elsize);
1660                 COPY_ONE(vec2, vec1, elsize);
1661                 COPY_ONE(vec1, tmp, elsize);
1662                 vec1 = vec2;
1663                 vec2 = (char *)vec1 - elsize;
1664             }
1665         }
1666     }
1667 #undef CALL_CMP
1668 #undef COPY_ONE
1669
1670     msa.elsize = elsize;
1671     msa.cmp = cmp;
1672     msa.arg = arg;
1673     msa.isValue = isValue;
1674
1675     vec1 = src;
1676     vec2 = tmp;
1677     for (run = INS_SORT_INT; run < nel; run *= 2) {
1678         for (lo = 0; lo < nel; lo += 2 * run) {
1679             hi = lo + run;
1680             if (hi >= nel) {
1681                 memcpy((char *)vec2 + lo * elsize, (char *)vec1 + lo * elsize,
1682                        (nel - lo) * elsize);
1683                 break;
1684             }
1685             if (!MergeArrays(&msa, (char *)vec1 + lo * elsize,
1686                              (char *)vec2 + lo * elsize, run,
1687                              hi + run > nel ? nel - hi : run)) {
1688                 return JS_FALSE;
1689             }
1690         }
1691         swap = vec1;
1692         vec1 = vec2;
1693         vec2 = swap;
1694     }
1695     if (src != vec1)
1696         memcpy(src, tmp, nel * elsize);
1697
1698     return JS_TRUE;
1699 }
1700
1701 struct CompareArgs
1702 {
1703     JSContext          *context;
1704     InvokeSessionGuard session;
1705
1706     CompareArgs(JSContext *cx)
1707       : context(cx)
1708     {}
1709 };
1710
1711 static JS_REQUIRES_STACK JSBool
1712 sort_compare(void *arg, const void *a, const void *b, int *result)
1713 {
1714     const Value *av = (const Value *)a, *bv = (const Value *)b;
1715     CompareArgs *ca = (CompareArgs *) arg;
1716     JSContext *cx = ca->context;
1717
1718     /*
1719      * array_sort deals with holes and undefs on its own and they should not
1720      * come here.
1721      */
1722     JS_ASSERT(!av->isMagic() && !av->isUndefined());
1723     JS_ASSERT(!av->isMagic() && !bv->isUndefined());
1724
1725     if (!JS_CHECK_OPERATION_LIMIT(cx))
1726         return JS_FALSE;
1727
1728     InvokeSessionGuard &session = ca->session;
1729     session[0] = *av;
1730     session[1] = *bv;
1731
1732     if (!session.invoke(cx))
1733         return JS_FALSE;
1734
1735     jsdouble cmp;
1736     if (!ValueToNumber(cx, session.rval(), &cmp))
1737         return JS_FALSE;
1738
1739     /* Clamp cmp to -1, 0, 1. */
1740     *result = 0;
1741     if (!JSDOUBLE_IS_NaN(cmp) && cmp != 0)
1742         *result = cmp > 0 ? 1 : -1;
1743
1744     /*
1745      * XXX else report some kind of error here?  ECMA talks about 'consistent
1746      * compare functions' that don't return NaN, but is silent about what the
1747      * result should be.  So we currently ignore it.
1748      */
1749
1750     return JS_TRUE;
1751 }
1752
1753 typedef JSBool (JS_REQUIRES_STACK *JSRedComparator)(void*, const void*,
1754                                                     const void*, int *);
1755
1756 static inline JS_IGNORE_STACK JSComparator
1757 comparator_stack_cast(JSRedComparator func)
1758 {
1759     return func;
1760 }
1761
1762 static int
1763 sort_compare_strings(void *arg, const void *a, const void *b, int *result)
1764 {
1765     JSContext *cx = (JSContext *)arg;
1766     JSString *astr = ((const Value *)a)->toString();
1767     JSString *bstr = ((const Value *)b)->toString();
1768     return JS_CHECK_OPERATION_LIMIT(cx) && CompareStrings(cx, astr, bstr, result);
1769 }
1770
1771 JSBool
1772 js::array_sort(JSContext *cx, uintN argc, Value *vp)
1773 {
1774     jsuint len, newlen, i, undefs;
1775     size_t elemsize;
1776     JSString *str;
1777
1778     Value *argv = JS_ARGV(cx, vp);
1779     Value fval;
1780     if (argc > 0 && !argv[0].isUndefined()) {
1781         if (argv[0].isPrimitive()) {
1782             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_BAD_SORT_ARG);
1783             return false;
1784         }
1785         fval = argv[0];     /* non-default compare function */
1786     } else {
1787         fval.setNull();
1788     }
1789
1790     JSObject *obj = ToObject(cx, &vp[1]);
1791     if (!obj)
1792         return false;
1793     if (!js_GetLengthProperty(cx, obj, &len))
1794         return false;
1795     if (len == 0) {
1796         vp->setObject(*obj);
1797         return true;
1798     }
1799
1800     /*
1801      * We need a temporary array of 2 * len Value to hold the array elements
1802      * and the scratch space for merge sort. Check that its size does not
1803      * overflow size_t, which would allow for indexing beyond the end of the
1804      * malloc'd vector.
1805      */
1806 #if JS_BITS_PER_WORD == 32
1807     if (size_t(len) > size_t(-1) / (2 * sizeof(Value))) {
1808         js_ReportAllocationOverflow(cx);
1809         return false;
1810     }
1811 #endif
1812
1813     /*
1814      * Initialize vec as a root. We will clear elements of vec one by
1815      * one while increasing the rooted amount of vec when we know that the
1816      * property at the corresponding index exists and its value must be rooted.
1817      *
1818      * In this way when sorting a huge mostly sparse array we will not
1819      * access the tail of vec corresponding to properties that do not
1820      * exist, allowing OS to avoiding committing RAM. See bug 330812.
1821      */
1822     {
1823         Value *vec = (Value *) cx->malloc(2 * size_t(len) * sizeof(Value));
1824         if (!vec)
1825             return false;
1826
1827         DEFINE_LOCAL_CLASS_OF_STATIC_FUNCTION(AutoFreeVector) {
1828             JSContext *const cx;
1829             Value *&vec;
1830            public:
1831             AutoFreeVector(JSContext *cx, Value *&vec) : cx(cx), vec(vec) { }
1832             ~AutoFreeVector() {
1833                 cx->free(vec);
1834             }
1835         } free(cx, vec);
1836
1837         AutoArrayRooter tvr(cx, 0, vec);
1838
1839         /*
1840          * By ECMA 262, 15.4.4.11, a property that does not exist (which we
1841          * call a "hole") is always greater than an existing property with
1842          * value undefined and that is always greater than any other property.
1843          * Thus to sort holes and undefs we simply count them, sort the rest
1844          * of elements, append undefs after them and then make holes after
1845          * undefs.
1846          */
1847         undefs = 0;
1848         newlen = 0;
1849         bool allStrings = true;
1850         for (i = 0; i < len; i++) {
1851             if (!JS_CHECK_OPERATION_LIMIT(cx))
1852                 return false;
1853
1854             /* Clear vec[newlen] before including it in the rooted set. */
1855             JSBool hole;
1856             vec[newlen].setNull();
1857             tvr.changeLength(newlen + 1);
1858             if (!GetElement(cx, obj, i, &hole, &vec[newlen]))
1859                 return false;
1860
1861             if (hole)
1862                 continue;
1863
1864             if (vec[newlen].isUndefined()) {
1865                 ++undefs;
1866                 continue;
1867             }
1868
1869             allStrings = allStrings && vec[newlen].isString();
1870
1871             ++newlen;
1872         }
1873
1874         if (newlen == 0) {
1875             vp->setObject(*obj);
1876             return true; /* The array has only holes and undefs. */
1877         }
1878
1879         /*
1880          * The first newlen elements of vec are copied from the array object
1881          * (above). The remaining newlen positions are used as GC-rooted scratch
1882          * space for mergesort. We must clear the space before including it to
1883          * the root set covered by tvr.count.
1884          */
1885         Value *mergesort_tmp = vec + newlen;
1886         MakeRangeGCSafe(mergesort_tmp, newlen);
1887         tvr.changeLength(newlen * 2);
1888
1889         /* Here len == 2 * (newlen + undefs + number_of_holes). */
1890         if (fval.isNull()) {
1891             /*
1892              * Sort using the default comparator converting all elements to
1893              * strings.
1894              */
1895             if (allStrings) {
1896                 elemsize = sizeof(Value);
1897             } else {
1898                 /*
1899                  * To avoid string conversion on each compare we do it only once
1900                  * prior to sorting. But we also need the space for the original
1901                  * values to recover the sorting result. To reuse
1902                  * sort_compare_strings we move the original values to the odd
1903                  * indexes in vec, put the string conversion results in the even
1904                  * indexes and pass 2 * sizeof(Value) as an element size to the
1905                  * sorting function. In this way sort_compare_strings will only
1906                  * see the string values when it casts the compare arguments as
1907                  * pointers to Value.
1908                  *
1909                  * This requires doubling the temporary storage including the
1910                  * scratch space for the merge sort. Since vec already contains
1911                  * the rooted scratch space for newlen elements at the tail, we
1912                  * can use it to rearrange and convert to strings first and try
1913                  * realloc only when we know that we successfully converted all
1914                  * the elements.
1915                  */
1916 #if JS_BITS_PER_WORD == 32
1917                 if (size_t(newlen) > size_t(-1) / (4 * sizeof(Value))) {
1918                     js_ReportAllocationOverflow(cx);
1919                     return false;
1920                 }
1921 #endif
1922
1923                 /*
1924                  * Rearrange and string-convert the elements of the vector from
1925                  * the tail here and, after sorting, move the results back
1926                  * starting from the start to prevent overwrite the existing
1927                  * elements.
1928                  */
1929                 i = newlen;
1930                 do {
1931                     --i;
1932                     if (!JS_CHECK_OPERATION_LIMIT(cx))
1933                         return false;
1934                     const Value &v = vec[i];
1935                     str = js_ValueToString(cx, v);
1936                     if (!str)
1937                         return false;
1938                     // Copying v must come first, because the following line overwrites v
1939                     // when i == 0.
1940                     vec[2 * i + 1] = v;
1941                     vec[2 * i].setString(str);
1942                 } while (i != 0);
1943
1944                 JS_ASSERT(tvr.array == vec);
1945                 vec = (Value *) cx->realloc(vec, 4 * size_t(newlen) * sizeof(Value));
1946                 if (!vec) {
1947                     vec = tvr.array;  /* N.B. AutoFreeVector */
1948                     return false;
1949                 }
1950                 mergesort_tmp = vec + 2 * newlen;
1951                 MakeRangeGCSafe(mergesort_tmp, 2 * newlen);
1952                 tvr.changeArray(vec, newlen * 4);
1953                 elemsize = 2 * sizeof(Value);
1954             }
1955             if (!js_MergeSort(vec, size_t(newlen), elemsize,
1956                               sort_compare_strings, cx, mergesort_tmp,
1957                               JS_SORTING_GENERIC)) {
1958                 return false;
1959             }
1960             if (!allStrings) {
1961                 /*
1962                  * We want to make the following loop fast and to unroot the
1963                  * cached results of toString invocations before the operation
1964                  * callback has a chance to run the GC. For this reason we do
1965                  * not call JS_CHECK_OPERATION_LIMIT in the loop.
1966                  */
1967                 i = 0;
1968                 do {
1969                     vec[i] = vec[2 * i + 1];
1970                 } while (++i != newlen);
1971             }
1972         } else {
1973             CompareArgs ca(cx);
1974             if (!ca.session.start(cx, fval, UndefinedValue(), 2))
1975                 return false;
1976
1977             if (!js_MergeSort(vec, size_t(newlen), sizeof(Value),
1978                               comparator_stack_cast(sort_compare),
1979                               &ca, mergesort_tmp,
1980                               JS_SORTING_VALUES)) {
1981                 return false;
1982             }
1983         }
1984
1985         /*
1986          * We no longer need to root the scratch space for the merge sort, so
1987          * unroot it now to make the job of a potential GC under
1988          * InitArrayElements easier.
1989          */
1990         tvr.changeLength(newlen);
1991         if (!InitArrayElements(cx, obj, 0, newlen, vec))
1992             return false;
1993     }
1994
1995     /* Set undefs that sorted after the rest of elements. */
1996     while (undefs != 0) {
1997         --undefs;
1998         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1999             !SetArrayElement(cx, obj, newlen++, UndefinedValue())) {
2000             return false;
2001         }
2002     }
2003
2004     /* Re-create any holes that sorted to the end of the array. */
2005     while (len > newlen) {
2006         if (!JS_CHECK_OPERATION_LIMIT(cx) || DeleteArrayElement(cx, obj, --len, true) < 0)
2007             return false;
2008     }
2009     vp->setObject(*obj);
2010     return true;
2011 }
2012
2013 /*
2014  * Perl-inspired push, pop, shift, unshift, and splice methods.
2015  */
2016 static JSBool
2017 array_push_slowly(JSContext *cx, JSObject *obj, uintN argc, Value *argv, Value *rval)
2018 {
2019     jsuint length;
2020
2021     if (!js_GetLengthProperty(cx, obj, &length))
2022         return JS_FALSE;
2023     if (!InitArrayElements(cx, obj, length, argc, argv))
2024         return JS_FALSE;
2025
2026     /* Per ECMA-262, return the new array length. */
2027     jsdouble newlength = length + jsdouble(argc);
2028     rval->setNumber(newlength);
2029     return js_SetLengthProperty(cx, obj, newlength);
2030 }
2031
2032 static JSBool
2033 array_push1_dense(JSContext* cx, JSObject* obj, const Value &v, Value *rval)
2034 {
2035     uint32 length = obj->getArrayLength();
2036     do {
2037         JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, 1);
2038         if (result != JSObject::ED_OK) {
2039             if (result == JSObject::ED_FAILED)
2040                 return false;
2041             JS_ASSERT(result == JSObject::ED_SPARSE);
2042             break;
2043         }
2044
2045         obj->setArrayLength(length + 1);
2046
2047         JS_ASSERT(obj->getDenseArrayElement(length).isMagic(JS_ARRAY_HOLE));
2048         obj->setDenseArrayElement(length, v);
2049         rval->setNumber(obj->getArrayLength());
2050         return true;
2051     } while (false);
2052
2053     if (!obj->makeDenseArraySlow(cx))
2054         return false;
2055     Value tmp = v;
2056     return array_push_slowly(cx, obj, 1, &tmp, rval);
2057 }
2058
2059 JS_ALWAYS_INLINE JSBool
2060 ArrayCompPushImpl(JSContext *cx, JSObject *obj, const Value &v)
2061 {
2062     JS_ASSERT(obj->isDenseArray());
2063     uint32_t length = obj->getArrayLength();
2064     JS_ASSERT(length <= obj->getDenseArrayCapacity());
2065
2066     if (length == obj->getDenseArrayCapacity()) {
2067         if (length > JS_ARGS_LENGTH_MAX) {
2068             JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
2069                                    JSMSG_ARRAY_INIT_TOO_BIG);
2070             return JS_FALSE;
2071         }
2072
2073         /*
2074          * Array comprehension cannot add holes to the array and never leaks
2075          * the array before it is fully initialized. So we can use ensureSlots
2076          * instead of ensureDenseArrayElements.
2077          */
2078         if (!obj->ensureSlots(cx, length + 1))
2079             return false;
2080     }
2081     obj->setArrayLength(length + 1);
2082     obj->setDenseArrayElement(length, v);
2083     return JS_TRUE;
2084 }
2085
2086 JSBool
2087 js_ArrayCompPush(JSContext *cx, JSObject *obj, const Value &vp)
2088 {
2089     return ArrayCompPushImpl(cx, obj, vp);
2090 }
2091
2092 #ifdef JS_TRACER
2093 JSBool JS_FASTCALL
2094 js_ArrayCompPush_tn(JSContext *cx, JSObject *obj, ValueArgType v)
2095 {
2096     TraceMonitor *tm = JS_TRACE_MONITOR_ON_TRACE(cx);
2097
2098     if (!ArrayCompPushImpl(cx, obj, ValueArgToConstRef(v))) {
2099         SetBuiltinError(tm);
2100         return JS_FALSE;
2101     }
2102
2103     return WasBuiltinSuccessful(tm);
2104 }
2105 JS_DEFINE_CALLINFO_3(extern, BOOL_FAIL, js_ArrayCompPush_tn, CONTEXT, OBJECT,
2106                      VALUE, 0, nanojit::ACCSET_STORE_ANY)
2107 #endif
2108
2109 static JSBool
2110 array_push(JSContext *cx, uintN argc, Value *vp)
2111 {
2112     JSObject *obj = ToObject(cx, &vp[1]);
2113     if (!obj)
2114         return false;
2115
2116     /* Insist on one argument and obj of the expected class. */
2117     if (argc != 1 || !obj->isDenseArray())
2118         return array_push_slowly(cx, obj, argc, vp + 2, vp);
2119
2120     return array_push1_dense(cx, obj, vp[2], vp);
2121 }
2122
2123 static JSBool
2124 array_pop_slowly(JSContext *cx, JSObject* obj, Value *vp)
2125 {
2126     jsuint index;
2127     JSBool hole;
2128
2129     if (!js_GetLengthProperty(cx, obj, &index))
2130         return JS_FALSE;
2131     if (index == 0) {
2132         vp->setUndefined();
2133     } else {
2134         index--;
2135
2136         /* Get the to-be-deleted property's value into vp. */
2137         if (!GetElement(cx, obj, index, &hole, vp))
2138             return JS_FALSE;
2139         if (!hole && DeleteArrayElement(cx, obj, index, true) < 0)
2140             return JS_FALSE;
2141     }
2142     return js_SetLengthProperty(cx, obj, index);
2143 }
2144
2145 static JSBool
2146 array_pop_dense(JSContext *cx, JSObject* obj, Value *vp)
2147 {
2148     jsuint index;
2149     JSBool hole;
2150
2151     index = obj->getArrayLength();
2152     if (index == 0) {
2153         vp->setUndefined();
2154         return JS_TRUE;
2155     }
2156     index--;
2157     if (!GetElement(cx, obj, index, &hole, vp))
2158         return JS_FALSE;
2159     if (!hole && DeleteArrayElement(cx, obj, index, true) < 0)
2160         return JS_FALSE;
2161     obj->setArrayLength(index);
2162     return JS_TRUE;
2163 }
2164
2165 static JSBool
2166 array_pop(JSContext *cx, uintN argc, Value *vp)
2167 {
2168     JSObject *obj = ToObject(cx, &vp[1]);
2169     if (!obj)
2170         return false;
2171     if (obj->isDenseArray())
2172         return array_pop_dense(cx, obj, vp);
2173     return array_pop_slowly(cx, obj, vp);
2174 }
2175
2176 static JSBool
2177 array_shift(JSContext *cx, uintN argc, Value *vp)
2178 {
2179     JSObject *obj = ToObject(cx, &vp[1]);
2180     if (!obj)
2181         return JS_FALSE;
2182
2183     jsuint length;
2184     if (!js_GetLengthProperty(cx, obj, &length))
2185         return JS_FALSE;
2186
2187     if (length == 0) {
2188         vp->setUndefined();
2189     } else {
2190         length--;
2191
2192         if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
2193             length < obj->getDenseArrayCapacity()) {
2194             *vp = obj->getDenseArrayElement(0);
2195             if (vp->isMagic(JS_ARRAY_HOLE))
2196                 vp->setUndefined();
2197             Value *elems = obj->getDenseArrayElements();
2198             memmove(elems, elems + 1, length * sizeof(jsval));
2199             obj->setDenseArrayElement(length, MagicValue(JS_ARRAY_HOLE));
2200             obj->setArrayLength(length);
2201             if (!js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(length)))
2202                 return JS_FALSE;
2203             return JS_TRUE;
2204         }
2205
2206         /* Get the to-be-deleted property's value into vp ASAP. */
2207         JSBool hole;
2208         if (!GetElement(cx, obj, 0, &hole, vp))
2209             return JS_FALSE;
2210
2211         /* Slide down the array above the first element. */
2212         AutoValueRooter tvr(cx);
2213         for (jsuint i = 0; i < length; i++) {
2214             if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2215                 !GetElement(cx, obj, i + 1, &hole, tvr.addr()) ||
2216                 !SetOrDeleteArrayElement(cx, obj, i, hole, tvr.value())) {
2217                 return JS_FALSE;
2218             }
2219         }
2220
2221         /* Delete the only or last element when it exists. */
2222         if (!hole && DeleteArrayElement(cx, obj, length, true) < 0)
2223             return JS_FALSE;
2224     }
2225     return js_SetLengthProperty(cx, obj, length);
2226 }
2227
2228 static JSBool
2229 array_unshift(JSContext *cx, uintN argc, Value *vp)
2230 {
2231     Value *argv;
2232     JSBool hole;
2233     jsdouble last, newlen;
2234
2235     JSObject *obj = ToObject(cx, &vp[1]);
2236     if (!obj)
2237         return false;
2238
2239     jsuint length;
2240     if (!js_GetLengthProperty(cx, obj, &length))
2241         return JS_FALSE;
2242     newlen = length;
2243     if (argc > 0) {
2244         /* Slide up the array to make room for argc at the bottom. */
2245         argv = JS_ARGV(cx, vp);
2246         if (length > 0) {
2247             bool optimized = false;
2248             do {
2249                 if (!obj->isDenseArray())
2250                     break;
2251                 if (js_PrototypeHasIndexedProperties(cx, obj))
2252                     break;
2253                 JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, argc);
2254                 if (result != JSObject::ED_OK) {
2255                     if (result == JSObject::ED_FAILED)
2256                         return false;
2257                     JS_ASSERT(result == JSObject::ED_SPARSE);
2258                     break;
2259                 }
2260                 Value *elems = obj->getDenseArrayElements();
2261                 memmove(elems + argc, elems, length * sizeof(jsval));
2262                 for (uint32 i = 0; i < argc; i++)
2263                     obj->setDenseArrayElement(i, MagicValue(JS_ARRAY_HOLE));
2264                 optimized = true;
2265             } while (false);
2266
2267             if (!optimized) {
2268                 last = length;
2269                 jsdouble upperIndex = last + argc;
2270                 AutoValueRooter tvr(cx);
2271                 do {
2272                     --last, --upperIndex;
2273                     if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2274                         !GetElement(cx, obj, last, &hole, tvr.addr()) ||
2275                         !SetOrDeleteArrayElement(cx, obj, upperIndex, hole, tvr.value())) {
2276                         return JS_FALSE;
2277                     }
2278                 } while (last != 0);
2279             }
2280         }
2281
2282         /* Copy from argv to the bottom of the array. */
2283         if (!InitArrayElements(cx, obj, 0, argc, argv))
2284             return JS_FALSE;
2285
2286         newlen += argc;
2287     }
2288     if (!js_SetLengthProperty(cx, obj, newlen))
2289         return JS_FALSE;
2290
2291     /* Follow Perl by returning the new array length. */
2292     vp->setNumber(newlen);
2293     return JS_TRUE;
2294 }
2295
2296 static JSBool
2297 array_splice(JSContext *cx, uintN argc, Value *vp)
2298 {
2299     JSObject *obj = ToObject(cx, &vp[1]);
2300     if (!obj)
2301         return false;
2302
2303     jsuint length, begin, end, count, delta, last;
2304     JSBool hole;
2305
2306     /* Create a new array value to return. */
2307     JSObject *obj2 = NewDenseEmptyArray(cx);
2308     if (!obj2)
2309         return JS_FALSE;
2310     vp->setObject(*obj2);
2311
2312     /* Nothing to do if no args.  Otherwise get length. */
2313     if (argc == 0)
2314         return JS_TRUE;
2315     Value *argv = JS_ARGV(cx, vp);
2316     if (!js_GetLengthProperty(cx, obj, &length))
2317         return JS_FALSE;
2318     jsuint origlength = length;
2319
2320     /* Convert the first argument into a starting index. */
2321     jsdouble d;
2322     if (!ValueToNumber(cx, *argv, &d))
2323         return JS_FALSE;
2324     d = js_DoubleToInteger(d);
2325     if (d < 0) {
2326         d += length;
2327         if (d < 0)
2328             d = 0;
2329     } else if (d > length) {
2330         d = length;
2331     }
2332     begin = (jsuint)d; /* d has been clamped to uint32 */
2333     argc--;
2334     argv++;
2335
2336     /* Convert the second argument from a count into a fencepost index. */
2337     delta = length - begin;
2338     if (argc == 0) {
2339         count = delta;
2340         end = length;
2341     } else {
2342         if (!ValueToNumber(cx, *argv, &d))
2343             return JS_FALSE;
2344         d = js_DoubleToInteger(d);
2345         if (d < 0)
2346             d = 0;
2347         else if (d > delta)
2348             d = delta;
2349         count = (jsuint)d;
2350         end = begin + count;
2351         argc--;
2352         argv++;
2353     }
2354
2355     AutoValueRooter tvr(cx);
2356
2357     /* If there are elements to remove, put them into the return value. */
2358     if (count > 0) {
2359         if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
2360             end <= obj->getDenseArrayCapacity()) {
2361             if (!InitArrayObject(cx, obj2, count, obj->getDenseArrayElements() + begin))
2362                 return JS_FALSE;
2363         } else {
2364             for (last = begin; last < end; last++) {
2365                 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2366                     !GetElement(cx, obj, last, &hole, tvr.addr())) {
2367                     return JS_FALSE;
2368                 }
2369
2370                 /* Copy tvr.value() to the new array unless it's a hole. */
2371                 if (!hole && !SetArrayElement(cx, obj2, last - begin, tvr.value()))
2372                     return JS_FALSE;
2373             }
2374
2375             if (!js_SetLengthProperty(cx, obj2, count))
2376                 return JS_FALSE;
2377         }
2378     }
2379
2380     /* Find the direction (up or down) to copy and make way for argv. */
2381     if (argc > count) {
2382         delta = (jsuint)argc - count;
2383         last = length;
2384         bool optimized = false;
2385         do {
2386             if (!obj->isDenseArray())
2387                 break;
2388             if (js_PrototypeHasIndexedProperties(cx, obj))
2389                 break;
2390             if (length > obj->getDenseArrayCapacity())
2391                 break;
2392             if (length != 0 && obj->getDenseArrayElement(length - 1).isMagic(JS_ARRAY_HOLE))
2393                 break;
2394             JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, delta);
2395             if (result != JSObject::ED_OK) {
2396                 if (result == JSObject::ED_FAILED)
2397                     return false;
2398                 JS_ASSERT(result == JSObject::ED_SPARSE);
2399                 break;
2400             }
2401             Value *arraybeg = obj->getDenseArrayElements();
2402             Value *srcbeg = arraybeg + last - 1;
2403             Value *srcend = arraybeg + end - 1;
2404             Value *dstbeg = srcbeg + delta;
2405             for (Value *src = srcbeg, *dst = dstbeg; src > srcend; --src, --dst)
2406                 *dst = *src;
2407
2408             obj->setArrayLength(obj->getArrayLength() + delta);
2409             optimized = true;
2410         } while (false);
2411
2412         if (!optimized) {
2413             /* (uint) end could be 0, so we can't use a vanilla >= test. */
2414             while (last-- > end) {
2415                 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2416                     !GetElement(cx, obj, last, &hole, tvr.addr()) ||
2417                     !SetOrDeleteArrayElement(cx, obj, last + delta, hole, tvr.value())) {
2418                     return JS_FALSE;
2419                 }
2420             }
2421         }
2422         length += delta;
2423     } else if (argc < count) {
2424         delta = count - (jsuint)argc;
2425         if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
2426             length <= obj->getDenseArrayCapacity()) {
2427
2428             Value *arraybeg = obj->getDenseArrayElements();
2429             Value *srcbeg = arraybeg + end;
2430             Value *srcend = arraybeg + length;
2431             Value *dstbeg = srcbeg - delta;
2432             for (Value *src = srcbeg, *dst = dstbeg; src < srcend; ++src, ++dst)
2433                 *dst = *src;
2434         } else {
2435             for (last = end; last < length; last++) {
2436                 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2437                     !GetElement(cx, obj, last, &hole, tvr.addr()) ||
2438                     !SetOrDeleteArrayElement(cx, obj, last - delta, hole, tvr.value())) {
2439                     return JS_FALSE;
2440                 }
2441             }
2442         }
2443         length -= delta;
2444     }
2445
2446     if (length < origlength && !js_SuppressDeletedIndexProperties(cx, obj, length, origlength))
2447         return JS_FALSE;
2448
2449     /*
2450      * Copy from argv into the hole to complete the splice, and update length in
2451      * case we deleted elements from the end.
2452      */
2453     return InitArrayElements(cx, obj, begin, argc, argv) &&
2454            js_SetLengthProperty(cx, obj, length);
2455 }
2456
2457 /*
2458  * Python-esque sequence operations.
2459  */
2460 static JSBool
2461 array_concat(JSContext *cx, uintN argc, Value *vp)
2462 {
2463     /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
2464     Value *p = JS_ARGV(cx, vp) - 1;
2465
2466     /* Create a new Array object and root it using *vp. */
2467     JSObject *aobj = ToObject(cx, &vp[1]);
2468     if (!aobj)
2469         return false;
2470
2471     JSObject *nobj;
2472     jsuint length;
2473     if (aobj->isDenseArray()) {
2474         /*
2475          * Clone aobj but pass the minimum of its length and capacity, to
2476          * handle a = [1,2,3]; a.length = 10000 "dense" cases efficiently. In
2477          * the normal case where length is <= capacity, nobj and aobj will have
2478          * the same capacity.
2479          */
2480         length = aobj->getArrayLength();
2481         jsuint capacity = aobj->getDenseArrayCapacity();
2482         nobj = NewDenseCopiedArray(cx, JS_MIN(length, capacity), aobj->getDenseArrayElements());
2483         if (!nobj)
2484             return JS_FALSE;
2485         nobj->setArrayLength(length);
2486         vp->setObject(*nobj);
2487         if (argc == 0)
2488             return JS_TRUE;
2489         argc--;
2490         p++;
2491     } else {
2492         nobj = NewDenseEmptyArray(cx);
2493         if (!nobj)
2494             return JS_FALSE;
2495         vp->setObject(*nobj);
2496         length = 0;
2497     }
2498
2499     AutoValueRooter tvr(cx);
2500
2501     /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
2502     for (uintN i = 0; i <= argc; i++) {
2503         if (!JS_CHECK_OPERATION_LIMIT(cx))
2504             return false;
2505         const Value &v = p[i];
2506         if (v.isObject()) {
2507             aobj = &v.toObject();
2508             if (aobj->isArray() ||
2509                 (aobj->isWrapper() && JSWrapper::wrappedObject(aobj)->isArray())) {
2510                 jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
2511                 if (!aobj->getProperty(cx, id, tvr.addr()))
2512                     return false;
2513                 jsuint alength;
2514                 if (!ValueToLength(cx, tvr.addr(), &alength))
2515                     return false;
2516                 for (jsuint slot = 0; slot < alength; slot++) {
2517                     JSBool hole;
2518                     if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2519                         !GetElement(cx, aobj, slot, &hole, tvr.addr())) {
2520                         return false;
2521                     }
2522
2523                     /*
2524                      * Per ECMA 262, 15.4.4.4, step 9, ignore nonexistent
2525                      * properties.
2526                      */
2527                     if (!hole &&
2528                         !SetArrayElement(cx, nobj, length+slot, tvr.value())) {
2529                         return false;
2530                     }
2531                 }
2532                 length += alength;
2533                 continue;
2534             }
2535         }
2536
2537         if (!SetArrayElement(cx, nobj, length, v))
2538             return false;
2539         length++;
2540     }
2541
2542     return js_SetLengthProperty(cx, nobj, length);
2543 }
2544
2545 static JSBool
2546 array_slice(JSContext *cx, uintN argc, Value *vp)
2547 {
2548     Value *argv;
2549     JSObject *nobj;
2550     jsuint length, begin, end, slot;
2551     JSBool hole;
2552
2553     argv = JS_ARGV(cx, vp);
2554
2555     JSObject *obj = ToObject(cx, &vp[1]);
2556     if (!obj)
2557         return false;
2558
2559     if (!js_GetLengthProperty(cx, obj, &length))
2560         return JS_FALSE;
2561     begin = 0;
2562     end = length;
2563
2564     if (argc > 0) {
2565         jsdouble d;
2566         if (!ValueToNumber(cx, argv[0], &d))
2567             return JS_FALSE;
2568         d = js_DoubleToInteger(d);
2569         if (d < 0) {
2570             d += length;
2571             if (d < 0)
2572                 d = 0;
2573         } else if (d > length) {
2574             d = length;
2575         }
2576         begin = (jsuint)d;
2577
2578         if (argc > 1 && !argv[1].isUndefined()) {
2579             if (!ValueToNumber(cx, argv[1], &d))
2580                 return JS_FALSE;
2581             d = js_DoubleToInteger(d);
2582             if (d < 0) {
2583                 d += length;
2584                 if (d < 0)
2585                     d = 0;
2586             } else if (d > length) {
2587                 d = length;
2588             }
2589             end = (jsuint)d;
2590         }
2591     }
2592
2593     if (begin > end)
2594         begin = end;
2595
2596     if (obj->isDenseArray() && end <= obj->getDenseArrayCapacity() &&
2597         !js_PrototypeHasIndexedProperties(cx, obj)) {
2598         nobj = NewDenseCopiedArray(cx, end - begin, obj->getDenseArrayElements() + begin);
2599         if (!nobj)
2600             return JS_FALSE;
2601         vp->setObject(*nobj);
2602         return JS_TRUE;
2603     }
2604
2605     /* Create a new Array object and root it using *vp. */
2606     nobj = NewDenseAllocatedArray(cx, end - begin);
2607     if (!nobj)
2608         return JS_FALSE;
2609     vp->setObject(*nobj);
2610
2611     AutoValueRooter tvr(cx);
2612     for (slot = begin; slot < end; slot++) {
2613         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2614             !GetElement(cx, obj, slot, &hole, tvr.addr())) {
2615             return JS_FALSE;
2616         }
2617         if (!hole && !SetArrayElement(cx, nobj, slot - begin, tvr.value()))
2618             return JS_FALSE;
2619     }
2620
2621     return JS_TRUE;
2622 }
2623
2624 #if JS_HAS_ARRAY_EXTRAS
2625
2626 static JSBool
2627 array_indexOfHelper(JSContext *cx, JSBool isLast, uintN argc, Value *vp)
2628 {
2629     jsuint length, i, stop;
2630     Value tosearch;
2631     jsint direction;
2632     JSBool hole;
2633
2634     JSObject *obj = ToObject(cx, &vp[1]);
2635     if (!obj)
2636         return false;
2637     if (!js_GetLengthProperty(cx, obj, &length))
2638         return JS_FALSE;
2639     if (length == 0)
2640         goto not_found;
2641
2642     if (argc <= 1) {
2643         i = isLast ? length - 1 : 0;
2644         tosearch = (argc != 0) ? vp[2] : UndefinedValue();
2645     } else {
2646         jsdouble start;
2647
2648         tosearch = vp[2];
2649         if (!ValueToNumber(cx, vp[3], &start))
2650             return JS_FALSE;
2651         start = js_DoubleToInteger(start);
2652         if (start < 0) {
2653             start += length;
2654             if (start < 0) {
2655                 if (isLast)
2656                     goto not_found;
2657                 i = 0;
2658             } else {
2659                 i = (jsuint)start;
2660             }
2661         } else if (start >= length) {
2662             if (!isLast)
2663                 goto not_found;
2664             i = length - 1;
2665         } else {
2666             i = (jsuint)start;
2667         }
2668     }
2669
2670     if (isLast) {
2671         stop = 0;
2672         direction = -1;
2673     } else {
2674         stop = length - 1;
2675         direction = 1;
2676     }
2677
2678     for (;;) {
2679         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2680             !GetElement(cx, obj, (jsuint)i, &hole, vp)) {
2681             return JS_FALSE;
2682         }
2683         if (!hole) {
2684             JSBool equal;
2685             if (!StrictlyEqual(cx, *vp, tosearch, &equal))
2686                 return JS_FALSE;
2687             if (equal) {
2688                 vp->setNumber(i);
2689                 return JS_TRUE;
2690             }
2691         }
2692         if (i == stop)
2693             goto not_found;
2694         i += direction;
2695     }
2696
2697   not_found:
2698     vp->setInt32(-1);
2699     return JS_TRUE;
2700 }
2701
2702 static JSBool
2703 array_indexOf(JSContext *cx, uintN argc, Value *vp)
2704 {
2705     return array_indexOfHelper(cx, JS_FALSE, argc, vp);
2706 }
2707
2708 static JSBool
2709 array_lastIndexOf(JSContext *cx, uintN argc, Value *vp)
2710 {
2711     return array_indexOfHelper(cx, JS_TRUE, argc, vp);
2712 }
2713
2714 /* Order is important; extras that take a predicate funarg must follow MAP. */
2715 typedef enum ArrayExtraMode {
2716     FOREACH,
2717     REDUCE,
2718     REDUCE_RIGHT,
2719     MAP,
2720     FILTER,
2721     SOME,
2722     EVERY
2723 } ArrayExtraMode;
2724
2725 #define REDUCE_MODE(mode) ((mode) == REDUCE || (mode) == REDUCE_RIGHT)
2726
2727 static JSBool
2728 array_extra(JSContext *cx, ArrayExtraMode mode, uintN argc, Value *vp)
2729 {
2730     JSObject *obj = ToObject(cx, &vp[1]);
2731     if (!obj)
2732         return false;
2733
2734     jsuint length;
2735     if (!js_GetLengthProperty(cx, obj, &length))
2736         return JS_FALSE;
2737
2738     /*
2739      * First, get or compute our callee, so that we error out consistently
2740      * when passed a non-callable object.
2741      */
2742     if (argc == 0) {
2743         js_ReportMissingArg(cx, *vp, 0);
2744         return JS_FALSE;
2745     }
2746     Value *argv = vp + 2;
2747     JSObject *callable = js_ValueToCallableObject(cx, &argv[0], JSV2F_SEARCH_STACK);
2748     if (!callable)
2749         return JS_FALSE;
2750
2751     /*
2752      * Set our initial return condition, used for zero-length array cases
2753      * (and pre-size our map return to match our known length, for all cases).
2754      */
2755     jsuint newlen;
2756     JSObject *newarr;
2757 #ifdef __GNUC__ /* quell GCC overwarning */
2758     newlen = 0;
2759     newarr = NULL;
2760 #endif
2761     jsint start = 0, end = length, step = 1;
2762
2763     switch (mode) {
2764       case REDUCE_RIGHT:
2765         start = length - 1, end = -1, step = -1;
2766         /* FALL THROUGH */
2767       case REDUCE:
2768         if (length == 0 && argc == 1) {
2769             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
2770                                  JSMSG_EMPTY_ARRAY_REDUCE);
2771             return JS_FALSE;
2772         }
2773         if (argc >= 2) {
2774             *vp = argv[1];
2775         } else {
2776             JSBool hole;
2777             do {
2778                 if (!GetElement(cx, obj, start, &hole, vp))
2779                     return JS_FALSE;
2780                 start += step;
2781             } while (hole && start != end);
2782
2783             if (hole && start == end) {
2784                 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
2785                                      JSMSG_EMPTY_ARRAY_REDUCE);
2786                 return JS_FALSE;
2787             }
2788         }
2789         break;
2790       case MAP:
2791       case FILTER:
2792         newlen = (mode == MAP) ? length : 0;
2793         newarr = NewDenseAllocatedArray(cx, newlen);
2794         if (!newarr)
2795             return JS_FALSE;
2796         vp->setObject(*newarr);
2797         break;
2798       case SOME:
2799         vp->setBoolean(false);
2800         break;
2801       case EVERY:
2802         vp->setBoolean(true);
2803         break;
2804       case FOREACH:
2805         vp->setUndefined();
2806         break;
2807     }
2808
2809     if (length == 0)
2810         return JS_TRUE;
2811
2812     Value thisv = (argc > 1 && !REDUCE_MODE(mode)) ? argv[1] : UndefinedValue();
2813
2814     /*
2815      * For all but REDUCE, we call with 3 args (value, index, array). REDUCE
2816      * requires 4 args (accum, value, index, array).
2817      */
2818     argc = 3 + REDUCE_MODE(mode);
2819
2820     InvokeSessionGuard session;
2821     if (!session.start(cx, ObjectValue(*callable), thisv, argc))
2822         return JS_FALSE;
2823
2824     MUST_FLOW_THROUGH("out");
2825     JSBool ok = JS_TRUE;
2826     JSBool cond;
2827
2828     Value objv = ObjectValue(*obj);
2829     AutoValueRooter tvr(cx);
2830     for (jsint i = start; i != end; i += step) {
2831         JSBool hole;
2832         ok = JS_CHECK_OPERATION_LIMIT(cx) &&
2833              GetElement(cx, obj, i, &hole, tvr.addr());
2834         if (!ok)
2835             goto out;
2836         if (hole)
2837             continue;
2838
2839         /*
2840          * Push callable and 'this', then args. We must do this for every
2841          * iteration around the loop since Invoke clobbers its arguments.
2842          */
2843         uintN argi = 0;
2844         if (REDUCE_MODE(mode))
2845             session[argi++] = *vp;
2846         session[argi++] = tvr.value();
2847         session[argi++] = Int32Value(i);
2848         session[argi]   = objv;
2849
2850         /* Do the call. */
2851         ok = session.invoke(cx);
2852         if (!ok)
2853             break;
2854
2855         const Value &rval = session.rval();
2856
2857         if (mode > MAP)
2858             cond = js_ValueToBoolean(rval);
2859 #ifdef __GNUC__ /* quell GCC overwarning */
2860         else
2861             cond = JS_FALSE;
2862 #endif
2863
2864         switch (mode) {
2865           case FOREACH:
2866             break;
2867           case REDUCE:
2868           case REDUCE_RIGHT:
2869             *vp = rval;
2870             break;
2871           case MAP:
2872             ok = SetArrayElement(cx, newarr, i, rval);
2873             if (!ok)
2874                 goto out;
2875             break;
2876           case FILTER:
2877             if (!cond)
2878                 break;
2879             /* The element passed the filter, so push it onto our result. */
2880             ok = SetArrayElement(cx, newarr, newlen++, tvr.value());
2881             if (!ok)
2882                 goto out;
2883             break;
2884           case SOME:
2885             if (cond) {
2886                 vp->setBoolean(true);
2887                 goto out;
2888             }
2889             break;
2890           case EVERY:
2891             if (!cond) {
2892                 vp->setBoolean(false);
2893                 goto out;
2894             }
2895             break;
2896         }
2897     }
2898
2899   out:
2900     if (ok && mode == FILTER)
2901         ok = js_SetLengthProperty(cx, newarr, newlen);
2902     return ok;
2903 }
2904
2905 static JSBool
2906 array_forEach(JSContext *cx, uintN argc, Value *vp)
2907 {
2908     return array_extra(cx, FOREACH, argc, vp);
2909 }
2910
2911 static JSBool
2912 array_map(JSContext *cx, uintN argc, Value *vp)
2913 {
2914     return array_extra(cx, MAP, argc, vp);
2915 }
2916
2917 static JSBool
2918 array_reduce(JSContext *cx, uintN argc, Value *vp)
2919 {
2920     return array_extra(cx, REDUCE, argc, vp);
2921 }
2922
2923 static JSBool
2924 array_reduceRight(JSContext *cx, uintN argc, Value *vp)
2925 {
2926     return array_extra(cx, REDUCE_RIGHT, argc, vp);
2927 }
2928
2929 static JSBool
2930 array_filter(JSContext *cx, uintN argc, Value *vp)
2931 {
2932     return array_extra(cx, FILTER, argc, vp);
2933 }
2934
2935 static JSBool
2936 array_some(JSContext *cx, uintN argc, Value *vp)
2937 {
2938     return array_extra(cx, SOME, argc, vp);
2939 }
2940
2941 static JSBool
2942 array_every(JSContext *cx, uintN argc, Value *vp)
2943 {
2944     return array_extra(cx, EVERY, argc, vp);
2945 }
2946 #endif
2947
2948 static JSBool
2949 array_isArray(JSContext *cx, uintN argc, Value *vp)
2950 {
2951     JSObject *obj;
2952     vp->setBoolean(argc > 0 &&
2953                    vp[2].isObject() &&
2954                    ((obj = &vp[2].toObject())->isArray() ||
2955                     (obj->isWrapper() && JSWrapper::wrappedObject(obj)->isArray())));
2956     return true;
2957 }
2958
2959 static JSFunctionSpec array_methods[] = {
2960 #if JS_HAS_TOSOURCE
2961     JS_FN(js_toSource_str,      array_toSource,     0,0),
2962 #endif
2963     JS_FN(js_toString_str,      array_toString,     0,0),
2964     JS_FN(js_toLocaleString_str,array_toLocaleString,0,0),
2965
2966     /* Perl-ish methods. */
2967     JS_FN("join",               array_join,         1,JSFUN_GENERIC_NATIVE),
2968     JS_FN("reverse",            array_reverse,      0,JSFUN_GENERIC_NATIVE),
2969     JS_FN("sort",               array_sort,         1,JSFUN_GENERIC_NATIVE),
2970     JS_FN("push",               array_push,         1,JSFUN_GENERIC_NATIVE),
2971     JS_FN("pop",                array_pop,          0,JSFUN_GENERIC_NATIVE),
2972     JS_FN("shift",              array_shift,        0,JSFUN_GENERIC_NATIVE),
2973     JS_FN("unshift",            array_unshift,      1,JSFUN_GENERIC_NATIVE),
2974     JS_FN("splice",             array_splice,       2,JSFUN_GENERIC_NATIVE),
2975
2976     /* Pythonic sequence methods. */
2977     JS_FN("concat",             array_concat,       1,JSFUN_GENERIC_NATIVE),
2978     JS_FN("slice",              array_slice,        2,JSFUN_GENERIC_NATIVE),
2979
2980 #if JS_HAS_ARRAY_EXTRAS
2981     JS_FN("indexOf",            array_indexOf,      1,JSFUN_GENERIC_NATIVE),
2982     JS_FN("lastIndexOf",        array_lastIndexOf,  1,JSFUN_GENERIC_NATIVE),
2983     JS_FN("forEach",            array_forEach,      1,JSFUN_GENERIC_NATIVE),
2984     JS_FN("map",                array_map,          1,JSFUN_GENERIC_NATIVE),
2985     JS_FN("reduce",             array_reduce,       1,JSFUN_GENERIC_NATIVE),
2986     JS_FN("reduceRight",        array_reduceRight,  1,JSFUN_GENERIC_NATIVE),
2987     JS_FN("filter",             array_filter,       1,JSFUN_GENERIC_NATIVE),
2988     JS_FN("some",               array_some,         1,JSFUN_GENERIC_NATIVE),
2989     JS_FN("every",              array_every,        1,JSFUN_GENERIC_NATIVE),
2990 #endif
2991
2992     JS_FS_END
2993 };
2994
2995 static JSFunctionSpec array_static_methods[] = {
2996     JS_FN("isArray",            array_isArray,      1,0),
2997     JS_FS_END
2998 };
2999
3000 JSBool
3001 js_Array(JSContext *cx, uintN argc, Value *vp)
3002 {
3003     JSObject *obj;
3004
3005     if (argc == 0) {
3006         obj = NewDenseEmptyArray(cx);
3007     } else if (argc > 1) {
3008         obj = NewDenseCopiedArray(cx, argc, vp + 2);
3009     } else if (!vp[2].isNumber()) {
3010         obj = NewDenseCopiedArray(cx, 1, vp + 2);
3011     } else {
3012         jsuint length;
3013         if (!ValueToLength(cx, vp + 2, &length))
3014             return JS_FALSE;
3015         obj = NewDenseUnallocatedArray(cx, length);
3016     }
3017
3018     if (!obj)
3019         return JS_FALSE;
3020     vp->setObject(*obj);
3021
3022     return JS_TRUE;
3023 }
3024
3025 JSObject *
3026 js_InitArrayClass(JSContext *cx, JSObject *obj)
3027 {
3028     JSObject *proto = js_InitClass(cx, obj, NULL, &js_ArrayClass, js_Array, 1,
3029                                    NULL, array_methods, NULL, array_static_methods);
3030     if (!proto)
3031         return NULL;
3032
3033     /*
3034      * Assert that js_InitClass used the correct (slow array, not dense array)
3035      * class for proto's emptyShape class.
3036      */
3037     JS_ASSERT(proto->emptyShapes && proto->emptyShapes[0]->getClass() == proto->getClass());
3038
3039     proto->setArrayLength(0);
3040     return proto;
3041 }
3042
3043 /*
3044  * Array allocation functions.
3045  */
3046 namespace js {
3047
3048 template<bool allocateCapacity>
3049 static JS_ALWAYS_INLINE JSObject *
3050 NewArray(JSContext *cx, jsuint length, JSObject *proto)
3051 {
3052     JS_ASSERT_IF(proto, proto->isArray());
3053
3054     gc::FinalizeKind kind = GuessObjectGCKind(length, true);
3055     JSObject *obj = detail::NewObject<WithProto::Class, false>(cx, &js_ArrayClass, proto, NULL, kind);
3056     if (!obj)
3057         return NULL;
3058
3059     obj->setArrayLength(length);
3060
3061     if (allocateCapacity && !obj->ensureSlots(cx, length))
3062         return NULL;
3063
3064     return obj;
3065 }
3066
3067 JSObject * JS_FASTCALL
3068 NewDenseEmptyArray(JSContext *cx, JSObject *proto)
3069 {
3070     return NewArray<false>(cx, 0, proto);
3071 }
3072
3073 JSObject * JS_FASTCALL
3074 NewDenseAllocatedArray(JSContext *cx, uint32 length, JSObject *proto)
3075 {
3076     return NewArray<true>(cx, length, proto);
3077 }
3078
3079 JSObject * JS_FASTCALL
3080 NewDenseUnallocatedArray(JSContext *cx, uint32 length, JSObject *proto)
3081 {
3082     return NewArray<false>(cx, length, proto);
3083 }
3084
3085 JSObject *
3086 NewDenseCopiedArray(JSContext *cx, uintN length, Value *vp, JSObject *proto)
3087 {
3088     JSObject* obj = NewArray<true>(cx, length, proto);
3089     if (!obj)
3090         return NULL;
3091
3092     JS_ASSERT(obj->getDenseArrayCapacity() >= length);
3093
3094     if (vp)
3095         memcpy(obj->getDenseArrayElements(), vp, length * sizeof(Value));
3096
3097     return obj;
3098 }
3099
3100 #ifdef JS_TRACER
3101 JS_DEFINE_CALLINFO_2(extern, OBJECT, NewDenseEmptyArray, CONTEXT, OBJECT, 0,
3102                      nanojit::ACCSET_STORE_ANY)
3103 JS_DEFINE_CALLINFO_3(extern, OBJECT, NewDenseAllocatedArray, CONTEXT, UINT32, OBJECT, 0,
3104                      nanojit::ACCSET_STORE_ANY)
3105 JS_DEFINE_CALLINFO_3(extern, OBJECT, NewDenseUnallocatedArray, CONTEXT, UINT32, OBJECT, 0,
3106                      nanojit::ACCSET_STORE_ANY)
3107 #endif
3108
3109
3110
3111 JSObject *
3112 NewSlowEmptyArray(JSContext *cx)
3113 {
3114     JSObject *obj = NewNonFunction<WithProto::Class>(cx, &js_SlowArrayClass, NULL, NULL);
3115     if (!obj || !AddLengthProperty(cx, obj))
3116         return NULL;
3117
3118     obj->setArrayLength(0);
3119     return obj;
3120 }
3121
3122 }
3123
3124
3125 #ifdef DEBUG
3126 JSBool
3127 js_ArrayInfo(JSContext *cx, uintN argc, jsval *vp)
3128 {
3129     uintN i;
3130     JSObject *array;
3131
3132     for (i = 0; i < argc; i++) {
3133         Value arg = Valueify(JS_ARGV(cx, vp)[i]);
3134
3135         char *bytes = DecompileValueGenerator(cx, JSDVG_SEARCH_STACK, arg, NULL);
3136         if (!bytes)
3137             return JS_FALSE;
3138         if (arg.isPrimitive() ||
3139             !(array = arg.toObjectOrNull())->isArray()) {
3140             fprintf(stderr, "%s: not array\n", bytes);
3141             cx->free(bytes);
3142             continue;
3143         }
3144         fprintf(stderr, "%s: %s (len %u", bytes,
3145                 array->isDenseArray() ? "dense" : "sparse",
3146                 array->getArrayLength());
3147         if (array->isDenseArray()) {
3148             fprintf(stderr, ", capacity %u",
3149                     array->getDenseArrayCapacity());
3150         }
3151         fputs(")\n", stderr);
3152         cx->free(bytes);
3153     }
3154
3155     JS_SET_RVAL(cx, vp, JSVAL_VOID);
3156     return true;
3157 }
3158 #endif
3159
3160 JS_FRIEND_API(JSBool)
3161 js_CoerceArrayToCanvasImageData(JSObject *obj, jsuint offset, jsuint count,
3162                                 JSUint8 *dest)
3163 {
3164     uint32 length;
3165
3166     if (!obj || !obj->isDenseArray())
3167         return JS_FALSE;
3168
3169     length = obj->getArrayLength();
3170     if (length < offset + count)
3171         return JS_FALSE;
3172
3173     JSUint8 *dp = dest;
3174     for (uintN i = offset; i < offset+count; i++) {
3175         const Value &v = obj->getDenseArrayElement(i);
3176         if (v.isInt32()) {
3177             jsint vi = v.toInt32();
3178             if (jsuint(vi) > 255)
3179                 vi = (vi < 0) ? 0 : 255;
3180             *dp++ = JSUint8(vi);
3181         } else if (v.isDouble()) {
3182             jsdouble vd = v.toDouble();
3183             if (!(vd >= 0)) /* Not < so that NaN coerces to 0 */
3184                 *dp++ = 0;
3185             else if (vd > 255)
3186                 *dp++ = 255;
3187             else {
3188                 jsdouble toTruncate = vd + 0.5;
3189                 JSUint8 val = JSUint8(toTruncate);
3190
3191                 /*
3192                  * now val is rounded to nearest, ties rounded up.  We want
3193                  * rounded to nearest ties to even, so check whether we had a
3194                  * tie.
3195                  */
3196                 if (val == toTruncate) {
3197                   /*
3198                    * It was a tie (since adding 0.5 gave us the exact integer
3199                    * we want).  Since we rounded up, we either already have an
3200                    * even number or we have an odd number but the number we
3201                    * want is one less.  So just unconditionally masking out the
3202                    * ones bit should do the trick to get us the value we
3203                    * want.
3204                    */
3205                   *dp++ = (val & ~1);
3206                 } else {
3207                   *dp++ = val;
3208                 }
3209             }
3210         } else {
3211             return JS_FALSE;
3212         }
3213     }
3214
3215     return JS_TRUE;
3216 }
3217
3218 JS_FRIEND_API(JSBool)
3219 js_IsDensePrimitiveArray(JSObject *obj)
3220 {
3221     if (!obj || !obj->isDenseArray())
3222         return JS_FALSE;
3223
3224     jsuint capacity = obj->getDenseArrayCapacity();
3225     for (jsuint i = 0; i < capacity; i++) {
3226         if (obj->getDenseArrayElement(i).isObject())
3227             return JS_FALSE;
3228     }
3229
3230     return JS_TRUE;
3231 }
3232
3233 JS_FRIEND_API(JSBool)
3234 js_CloneDensePrimitiveArray(JSContext *cx, JSObject *obj, JSObject **clone)
3235 {
3236     JS_ASSERT(obj);
3237     if (!obj->isDenseArray()) {
3238         /*
3239          * This wasn't a dense array. Return JS_TRUE but a NULL clone to signal
3240          * that no exception was encountered.
3241          */
3242         *clone = NULL;
3243         return JS_TRUE;
3244     }
3245
3246     jsuint length = obj->getArrayLength();
3247
3248     /*
3249      * Must use the minimum of original array's length and capacity, to handle
3250      * |a = [1,2,3]; a.length = 10000| "dense" cases efficiently. In the normal
3251      * case where length is <= capacity, the clone and original array will have
3252      * the same capacity.
3253      */
3254     jsuint jsvalCount = JS_MIN(obj->getDenseArrayCapacity(), length);
3255
3256     js::AutoValueVector vector(cx);
3257     if (!vector.reserve(jsvalCount))
3258         return JS_FALSE;
3259
3260     for (jsuint i = 0; i < jsvalCount; i++) {
3261         const Value &val = obj->getDenseArrayElement(i);
3262
3263         if (val.isString()) {
3264             // Strings must be made immutable before being copied to a clone.
3265             if (!js_MakeStringImmutable(cx, val.toString()))
3266                 return JS_FALSE;
3267         } else if (val.isObject()) {
3268             /*
3269              * This wasn't an array of primitives. Return JS_TRUE but a null
3270              * clone to signal that no exception was encountered.
3271              */
3272             *clone = NULL;
3273             return JS_TRUE;
3274         }
3275
3276         vector.append(val);
3277     }
3278
3279     *clone = NewDenseCopiedArray(cx, jsvalCount, vector.begin());
3280     if (!*clone)
3281         return JS_FALSE;
3282
3283     /* The length will be set to the JS_MIN, above, but length might be larger. */
3284     (*clone)->setArrayLength(length);
3285     return JS_TRUE;
3286 }