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