src/dom/js/jsarray.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set sw=4 ts=8 et tw=80:
   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 #include "jsstddef.h"
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include "jstypes.h"
  48 #include "jsutil.h" /* Added by JSIFY */
  49 #include "jsapi.h"
  50 #include "jsarray.h"
  51 #include "jsatom.h"
  52 #include "jsbool.h"
  53 #include "jscntxt.h"
  54 #include "jsconfig.h"
  55 #include "jsfun.h"
  56 #include "jsgc.h"
  57 #include "jsinterp.h"
  58 #include "jslock.h"
  59 #include "jsnum.h"
  60 #include "jsobj.h"
  61 #include "jsstr.h"
  62
  63 /* 2^32 - 1 as a number and a string */
  64 #define MAXINDEX 4294967295u
  65 #define MAXSTR   "4294967295"
  66
  67 /*
  68  * Determine if the id represents an array index or an XML property index.
  69  *
  70  * An id is an array index according to ECMA by (15.4):
  71  *
  72  * "Array objects give special treatment to a certain class of property names.
  73  * A property name P (in the form of a string value) is an array index if and
  74  * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
  75  * to 2^32-1."
  76  *
  77  * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
  78  * except that by using signed 32-bit integers we miss the top half of the
  79  * valid range. This function checks the string representation itself; note
  80  * that calling a standard conversion routine might allow strings such as
  81  * "08" or "4.0" as array indices, which they are not.
  82  */
  83 JSBool
  84 js_IdIsIndex(jsval id, jsuint *indexp)
  85 {
  86     JSString *str;
  87     jschar *cp;
  88
  89     if (JSVAL_IS_INT(id)) {
  90         jsint i;
  91         i = JSVAL_TO_INT(id);
  92         if (i < 0)
  93             return JS_FALSE;
  94         *indexp = (jsuint)i;
  95         return JS_TRUE;
  96     }
  97
  98     /* NB: id should be a string, but jsxml.c may call us with an object id. */
  99     if (!JSVAL_IS_STRING(id))
 100         return JS_FALSE;
 101
 102     str = JSVAL_TO_STRING(id);
 103     cp = JSSTRING_CHARS(str);
 104     if (JS7_ISDEC(*cp) && JSSTRING_LENGTH(str) < sizeof(MAXSTR)) {
 105         jsuint index = JS7_UNDEC(*cp++);
 106         jsuint oldIndex = 0;
 107         jsuint c = 0;
 108         if (index != 0) {
 109             while (JS7_ISDEC(*cp)) {
 110                 oldIndex = index;
 111                 c = JS7_UNDEC(*cp);
 112                 index = 10*index + c;
 113                 cp++;
 114             }
 115         }
 116
 117         /* Ensure that all characters were consumed and we didn't overflow. */
 118         if (*cp == 0 &&
 119              (oldIndex < (MAXINDEX / 10) ||
 120               (oldIndex == (MAXINDEX / 10) && c < (MAXINDEX % 10))))
 121         {
 122             *indexp = index;
 123             return JS_TRUE;
 124         }
 125     }
 126     return JS_FALSE;
 127 }
 128
 129 static JSBool
 130 ValueIsLength(JSContext *cx, jsval v, jsuint *lengthp)
 131 {
 132     jsint i;
 133     jsdouble d;
 134
 135     if (JSVAL_IS_INT(v)) {
 136         i = JSVAL_TO_INT(v);
 137         if (i < 0) {
 138             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
 139                                  JSMSG_BAD_ARRAY_LENGTH);
 140             return JS_FALSE;
 141         }
 142         *lengthp = (jsuint) i;
 143         return JS_TRUE;
 144     }
 145
 146     if (!js_ValueToNumber(cx, v, &d)) {
 147         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
 148                              JSMSG_BAD_ARRAY_LENGTH);
 149         return JS_FALSE;
 150     }
 151     if (!js_DoubleToECMAUint32(cx, d, (uint32 *)lengthp)) {
 152         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
 153                              JSMSG_BAD_ARRAY_LENGTH);
 154         return JS_FALSE;
 155     }
 156     if (JSDOUBLE_IS_NaN(d) || d != *lengthp) {
 157         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
 158                              JSMSG_BAD_ARRAY_LENGTH);
 159         return JS_FALSE;
 160     }
 161     return JS_TRUE;
 162 }
 163
 164 JSBool
 165 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
 166 {
 167     JSTempValueRooter tvr;
 168     jsid id;
 169     JSBool ok;
 170     jsint i;
 171
 172     JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
 173     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
 174     ok = OBJ_GET_PROPERTY(cx, obj, id, &tvr.u.value);
 175     if (ok) {
 176         /*
 177          * Short-circuit, because js_ValueToECMAUint32 fails when called
 178          * during init time.
 179          */
 180         if (JSVAL_IS_INT(tvr.u.value)) {
 181             i = JSVAL_TO_INT(tvr.u.value);
 182             *lengthp = (jsuint)i;       /* jsuint cast does ToUint32 */
 183         } else {
 184             ok = js_ValueToECMAUint32(cx, tvr.u.value, (uint32 *)lengthp);
 185         }
 186     }
 187     JS_POP_TEMP_ROOT(cx, &tvr);
 188     return ok;
 189 }
 190
 191 static JSBool
 192 IndexToValue(JSContext *cx, jsuint index, jsval *vp)
 193 {
 194     if (index <= JSVAL_INT_MAX) {
 195         *vp = INT_TO_JSVAL(index);
 196         return JS_TRUE;
 197     }
 198     return js_NewDoubleValue(cx, (jsdouble)index, vp);
 199 }
 200
 201 static JSBool
 202 IndexToId(JSContext *cx, jsuint index, jsid *idp)
 203 {
 204     JSString *str;
 205     JSAtom *atom;
 206
 207     if (index <= JSVAL_INT_MAX) {
 208         *idp = INT_TO_JSID(index);
 209     } else {
 210         str = js_NumberToString(cx, (jsdouble)index);
 211         if (!str)
 212             return JS_FALSE;
 213         atom = js_AtomizeString(cx, str, 0);
 214         if (!atom)
 215             return JS_FALSE;
 216         *idp = ATOM_TO_JSID(atom);
 217
 218     }
 219     return JS_TRUE;
 220 }
 221
 222 static JSBool
 223 PropertyExists(JSContext *cx, JSObject *obj, jsid id, JSBool *foundp)
 224 {
 225     JSObject *obj2;
 226     JSProperty *prop;
 227
 228     if (!OBJ_LOOKUP_PROPERTY(cx, obj, id, &obj2, &prop))
 229         return JS_FALSE;
 230
 231     *foundp = prop != NULL;
 232     if (*foundp) {
 233         OBJ_DROP_PROPERTY(cx, obj2, prop);
 234     }
 235
 236     return JS_TRUE;
 237 }
 238
 239 #define JSID_HOLE       JSVAL_NULL
 240
 241 static JSBool
 242 IndexToExistingId(JSContext *cx, JSObject *obj, jsuint index, jsid *idp)
 243 {
 244     JSBool exists;
 245
 246     if (!IndexToId(cx, index, idp))
 247         return JS_FALSE;
 248     if (!PropertyExists(cx, obj, *idp, &exists))
 249         return JS_FALSE;
 250     if (!exists)
 251         *idp = JSID_HOLE;
 252     return JS_TRUE;
 253 }
 254
 255 JSBool
 256 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsuint length)
 257 {
 258     jsval v;
 259     jsid id;
 260
 261     if (!IndexToValue(cx, length, &v))
 262         return JS_FALSE;
 263     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
 264     return OBJ_SET_PROPERTY(cx, obj, id, &v);
 265 }
 266
 267 JSBool
 268 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
 269 {
 270     JSErrorReporter older;
 271     JSTempValueRooter tvr;
 272     jsid id;
 273     JSBool ok;
 274
 275     older = JS_SetErrorReporter(cx, NULL);
 276     JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
 277     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
 278     ok = OBJ_GET_PROPERTY(cx, obj, id, &tvr.u.value);
 279     JS_SetErrorReporter(cx, older);
 280     if (ok)
 281         ok = ValueIsLength(cx, tvr.u.value, lengthp);
 282     JS_POP_TEMP_ROOT(cx, &tvr);
 283     return ok;
 284 }
 285
 286 /*
 287  * This get function is specific to Array.prototype.length and other array
 288  * instance length properties.  It calls back through the class get function
 289  * in case some magic happens there (see call_getProperty in jsfun.c).
 290  */
 291 static JSBool
 292 array_length_getter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
 293 {
 294     return OBJ_GET_CLASS(cx, obj)->getProperty(cx, obj, id, vp);
 295 }
 296
 297 static JSBool
 298 array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
 299 {
 300     jsuint newlen, oldlen, slot;
 301     jsid id2;
 302     jsval junk;
 303
 304     if (!ValueIsLength(cx, *vp, &newlen))
 305         return JS_FALSE;
 306     if (!js_GetLengthProperty(cx, obj, &oldlen))
 307         return JS_FALSE;
 308     slot = oldlen;
 309     while (slot > newlen) {
 310         --slot;
 311         if (!IndexToId(cx, slot, &id2))
 312             return JS_FALSE;
 313         if (!OBJ_DELETE_PROPERTY(cx, obj, id2, &junk))
 314             return JS_FALSE;
 315     }
 316     return IndexToValue(cx, newlen, vp);
 317 }
 318
 319 static JSBool
 320 array_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
 321 {
 322     jsuint index, length;
 323
 324     if (!js_IdIsIndex(id, &index))
 325         return JS_TRUE;
 326     if (!js_GetLengthProperty(cx, obj, &length))
 327         return JS_FALSE;
 328     if (index >= length) {
 329         length = index + 1;
 330         return js_SetLengthProperty(cx, obj, length);
 331     }
 332     return JS_TRUE;
 333 }
 334
 335 static JSBool
 336 array_convert(JSContext *cx, JSObject *obj, JSType type, jsval *vp)
 337 {
 338     jsuint length;
 339
 340     if (JS_VERSION_IS_1_2(cx)) {
 341         if (!js_GetLengthProperty(cx, obj, &length))
 342             return JS_FALSE;
 343         switch (type) {
 344           case JSTYPE_NUMBER:
 345             return IndexToValue(cx, length, vp);
 346           case JSTYPE_BOOLEAN:
 347             *vp = BOOLEAN_TO_JSVAL(length > 0);
 348             return JS_TRUE;
 349           default:
 350             return JS_TRUE;
 351         }
 352     }
 353     return js_TryValueOf(cx, obj, type, vp);
 354 }
 355
 356 JSClass js_ArrayClass = {
 357     "Array",
 358     0,
 359     array_addProperty, JS_PropertyStub,   JS_PropertyStub,   JS_PropertyStub,
 360     JS_EnumerateStub,  JS_ResolveStub,    array_convert,     JS_FinalizeStub,
 361     JSCLASS_NO_OPTIONAL_MEMBERS
 362 };
 363
 364 static JSBool
 365 array_join_sub(JSContext *cx, JSObject *obj, JSString *sep, JSBool literalize,
 366                jsval *rval, JSBool localeString)
 367 {
 368     JSBool ok;
 369     jsuint length, index;
 370     jschar *chars, *ochars;
 371     size_t nchars, growth, seplen, tmplen;
 372     const jschar *sepstr;
 373     JSString *str;
 374     JSHashEntry *he;
 375     JSTempValueRooter tvr;
 376     JSAtom *atom;
 377     int stackDummy;
 378
 379     if (!JS_CHECK_STACK_SIZE(cx, stackDummy)) {
 380         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_OVER_RECURSED);
 381         return JS_FALSE;
 382     }
 383
 384     ok = js_GetLengthProperty(cx, obj, &length);
 385     if (!ok)
 386         return JS_FALSE;
 387
 388     he = js_EnterSharpObject(cx, obj, NULL, &chars);
 389     if (!he)
 390         return JS_FALSE;
 391     if (literalize) {
 392         if (IS_SHARP(he)) {
 393 #if JS_HAS_SHARP_VARS
 394             nchars = js_strlen(chars);
 395 #else
 396             chars[0] = '[';
 397             chars[1] = ']';
 398             chars[2] = 0;
 399             nchars = 2;
 400 #endif
 401             goto make_string;
 402         }
 403
 404         /*
 405          * Allocate 1 + 3 + 1 for "[", the worst-case closing ", ]", and the
 406          * terminating 0.
 407          */
 408         growth = (1 + 3 + 1) * sizeof(jschar);
 409         if (!chars) {
 410             nchars = 0;
 411             chars = (jschar *) malloc(growth);
 412             if (!chars)
 413                 goto done;
 414         } else {
 415             MAKE_SHARP(he);
 416             nchars = js_strlen(chars);
 417             chars = (jschar *)
 418                 realloc((ochars = chars), nchars * sizeof(jschar) + growth);
 419             if (!chars) {
 420                 free(ochars);
 421                 goto done;
 422             }
 423         }
 424         chars[nchars++] = '[';
 425     } else {
 426         /*
 427          * Free any sharp variable definition in chars.  Normally, we would
 428          * MAKE_SHARP(he) so that only the first sharp variable annotation is
 429          * a definition, and all the rest are references, but in the current
 430          * case of (!literalize), we don't need chars at all.
 431          */
 432         if (chars)
 433             JS_free(cx, chars);
 434         chars = NULL;
 435         nchars = 0;
 436
 437         /* Return the empty string on a cycle as well as on empty join. */
 438         if (IS_BUSY(he) || length == 0) {
 439             js_LeaveSharpObject(cx, NULL);
 440             *rval = JS_GetEmptyStringValue(cx);
 441             return ok;
 442         }
 443
 444         /* Flag he as BUSY so we can distinguish a cycle from a join-point. */
 445         MAKE_BUSY(he);
 446     }
 447     sepstr = NULL;
 448     seplen = JSSTRING_LENGTH(sep);
 449
 450     /* Use rval to locally root each element value as we loop and convert. */
 451 #define v (*rval)
 452
 453     v = JSVAL_NULL;
 454     for (index = 0; index < length; index++) {
 455         ok = JS_GetElement(cx, obj, index, &v);
 456         if (!ok)
 457             goto done;
 458
 459         if ((!literalize || JS_VERSION_IS_1_2(cx)) &&
 460             (JSVAL_IS_VOID(v) || JSVAL_IS_NULL(v))) {
 461             str = cx->runtime->emptyString;
 462         } else {
 463             if (localeString) {
 464                 atom = cx->runtime->atomState.toLocaleStringAtom;
 465                 JS_PUSH_TEMP_ROOT_OBJECT(cx, NULL, &tvr);
 466                 ok = js_ValueToObject(cx, v, &tvr.u.object) &&
 467                      js_TryMethod(cx, tvr.u.object, atom, 0, NULL, &v);
 468                 JS_POP_TEMP_ROOT(cx, &tvr);
 469                 if (!ok)
 470                     goto done;
 471                 str = js_ValueToString(cx, v);
 472             } else {
 473                 str = (literalize ? js_ValueToSource : js_ValueToString)(cx, v);
 474             }
 475             if (!str) {
 476                 ok = JS_FALSE;
 477                 goto done;
 478             }
 479         }
 480
 481         /* Allocate 3 + 1 at end for ", ", closing bracket, and zero. */
 482         tmplen = JSSTRING_LENGTH(str);
 483         growth = (nchars + (sepstr ? seplen : 0) + tmplen + 3 + 1);
 484         if (nchars > growth || tmplen > growth ||
 485             growth > (size_t)-1 / sizeof(jschar)) {
 486             if (chars) {
 487                 free(chars);
 488                 chars = NULL;
 489             }
 490             JS_ReportOutOfMemory(cx);
 491             goto done;
 492         }
 493         growth *= sizeof(jschar);
 494         if (!chars) {
 495             chars = (jschar *) malloc(growth);
 496             if (!chars)
 497                 goto done;
 498         } else {
 499             chars = (jschar *) realloc((ochars = chars), growth);
 500             if (!chars) {
 501                 free(ochars);
 502                 goto done;
 503             }
 504         }
 505
 506         if (sepstr) {
 507             js_strncpy(&chars[nchars], sepstr, seplen);
 508             nchars += seplen;
 509         }
 510         sepstr = JSSTRING_CHARS(sep);
 511
 512         js_strncpy(&chars[nchars], JSSTRING_CHARS(str), tmplen);
 513         nchars += tmplen;
 514     }
 515
 516   done:
 517     if (literalize) {
 518         if (chars) {
 519             if (JSVAL_IS_VOID(v)) {
 520                 chars[nchars++] = ',';
 521                 chars[nchars++] = ' ';
 522             }
 523             chars[nchars++] = ']';
 524         }
 525     } else {
 526         CLEAR_BUSY(he);
 527     }
 528     js_LeaveSharpObject(cx, NULL);
 529     if (!ok) {
 530         if (chars)
 531             free(chars);
 532         return ok;
 533     }
 534
 535 #undef v
 536
 537   make_string:
 538     if (!chars) {
 539         JS_ReportOutOfMemory(cx);
 540         return JS_FALSE;
 541     }
 542     chars[nchars] = 0;
 543     str = js_NewString(cx, chars, nchars, 0);
 544     if (!str) {
 545         free(chars);
 546         return JS_FALSE;
 547     }
 548     *rval = STRING_TO_JSVAL(str);
 549     return JS_TRUE;
 550 }
 551
 552 static jschar   comma_space_ucstr[] = {',', ' ', 0};
 553 static jschar   comma_ucstr[]       = {',', 0};
 554 static JSString comma_space         = {2, comma_space_ucstr};
 555 static JSString comma               = {1, comma_ucstr};
 556
 557 #if JS_HAS_TOSOURCE
 558 static JSBool
 559 array_toSource(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
 560                jsval *rval)
 561 {
 562     return array_join_sub(cx, obj, &comma_space, JS_TRUE, rval, JS_FALSE);
 563 }
 564 #endif
 565
 566 static JSBool
 567 array_toString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
 568                jsval *rval)
 569 {
 570     JSBool literalize;
 571
 572     /*
 573      * JS1.2 arrays convert to array literals, with a comma followed by a space
 574      * between each element.
 575      */
 576     literalize = JS_VERSION_IS_1_2(cx);
 577     return array_join_sub(cx, obj, literalize ? &comma_space : &comma,
 578                           literalize, rval, JS_FALSE);
 579 }
 580
 581 static JSBool
 582 array_toLocaleString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
 583                jsval *rval)
 584 {
 585     /*
 586      *  Passing comma here as the separator. Need a way to get a
 587      *  locale-specific version.
 588      */
 589     return array_join_sub(cx, obj, &comma, JS_FALSE, rval, JS_TRUE);
 590 }
 591
 592 static JSBool
 593 InitArrayElements(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
 594 {
 595     jsuint index;
 596     jsid id;
 597
 598     for (index = 0; index < length; index++) {
 599         JS_ASSERT(vector[index] != JSVAL_HOLE);
 600
 601         if (!IndexToId(cx, index, &id))
 602             return JS_FALSE;
 603         if (!OBJ_SET_PROPERTY(cx, obj, id, &vector[index]))
 604             return JS_FALSE;
 605     }
 606     return JS_TRUE;
 607 }
 608
 609 static JSBool
 610 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
 611 {
 612     jsval v;
 613     jsid id;
 614
 615     if (!IndexToValue(cx, length, &v))
 616         return JS_FALSE;
 617     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
 618     if (!OBJ_DEFINE_PROPERTY(cx, obj, id, v,
 619                              array_length_getter, array_length_setter,
 620                              JSPROP_PERMANENT,
 621                              NULL)) {
 622           return JS_FALSE;
 623     }
 624     if (!vector)
 625         return JS_TRUE;
 626     return InitArrayElements(cx, obj, length, vector);
 627 }
 628
 629 #if JS_HAS_SOME_PERL_FUN
 630 /*
 631  * Perl-inspired join, reverse, and sort.
 632  */
 633 static JSBool
 634 array_join(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
 635 {
 636     JSString *str;
 637
 638     if (JSVAL_IS_VOID(argv[0]))
 639         return array_join_sub(cx, obj, &comma, JS_FALSE, rval, JS_FALSE);
 640     str = js_ValueToString(cx, argv[0]);
 641     if (!str)
 642         return JS_FALSE;
 643     argv[0] = STRING_TO_JSVAL(str);
 644     return array_join_sub(cx, obj, str, JS_FALSE, rval, JS_FALSE);
 645 }
 646
 647 static JSBool
 648 array_reverse(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
 649               jsval *rval)
 650 {
 651     jsuint len, half, i;
 652     jsid id, id2;
 653     jsval *tmproot, *tmproot2;
 654     JSBool idexists, id2exists, ok;
 655
 656     if (!js_GetLengthProperty(cx, obj, &len))
 657         return JS_FALSE;
 658
 659     /*
 660      * When len > JSVAL_INT_MAX + 1 the loop below accesses indexes greater
 661      * than JSVAL_INT_MAX. For such indexes the corresponding ids are atoms.
 662      * We use JS_KEEP_ATOMS to protect them against GC since OBJ_GET_PROPERTY
 663      * can potentially execute an arbitrary script. See bug 341956.
 664      *
 665      * After this point control must flow through label out: to exit.
 666      */
 667     if (len > JSVAL_INT_MAX + 1)
 668         JS_KEEP_ATOMS(cx->runtime);
 669
 670     /*
 671      * Use argv[argc] and argv[argc + 1] as local roots to hold temporarily
 672      * array elements for GC-safe swap.
 673      */
 674     tmproot = argv + argc;
 675     tmproot2 = argv + argc + 1;
 676     half = len / 2;
 677     for (i = 0; i < half; i++) {
 678         /*
 679          * Get both values while checking for holes to make sure they don't
 680          * get filled.
 681          */
 682         if (!IndexToId(cx, i, &id))
 683             goto bad;
 684         if (!PropertyExists(cx, obj, id, &idexists))
 685             goto bad;
 686         if (idexists && !OBJ_GET_PROPERTY(cx, obj, id, tmproot))
 687             goto bad;
 688
 689         if (!IndexToId(cx, len - i - 1, &id2))
 690             goto bad;
 691         if (!PropertyExists(cx, obj, id2, &id2exists))
 692             goto bad;
 693         if (id2exists && !OBJ_GET_PROPERTY(cx, obj, id2, tmproot2))
 694             goto bad;
 695
 696         /* Exchange the values. */
 697         if (idexists) {
 698             if (!OBJ_SET_PROPERTY(cx, obj, id2, tmproot))
 699                 goto bad;
 700         } else {
 701             if (!OBJ_DELETE_PROPERTY(cx, obj, id2, tmproot))
 702                 goto bad;
 703         }
 704         if (id2exists) {
 705             if (!OBJ_SET_PROPERTY(cx, obj, id, tmproot2))
 706                 goto bad;
 707         } else {
 708             if (!OBJ_DELETE_PROPERTY(cx, obj, id, tmproot2))
 709                 goto bad;
 710         }
 711     }
 712     ok = JS_TRUE;
 713
 714   out:
 715     if (len > JSVAL_INT_MAX + 1)
 716         JS_UNKEEP_ATOMS(cx->runtime);
 717     *rval = OBJECT_TO_JSVAL(obj);
 718     return ok;
 719
 720   bad:
 721     ok = JS_FALSE;
 722     goto out;
 723 }
 724
 725 typedef struct HSortArgs {
 726     void         *vec;
 727     size_t       elsize;
 728     void         *pivot;
 729     JSComparator cmp;
 730     void         *arg;
 731     JSBool       fastcopy;
 732 } HSortArgs;
 733
 734 static int
 735 sort_compare(const void *a, const void *b, void *arg);
 736
 737 static int
 738 sort_compare_strings(const void *a, const void *b, void *arg);
 739
 740 static void
 741 HeapSortHelper(JSBool building, HSortArgs *hsa, size_t lo, size_t hi)
 742 {
 743     void *pivot, *vec, *vec2, *arg, *a, *b;
 744     size_t elsize;
 745     JSComparator cmp;
 746     JSBool fastcopy;
 747     size_t j, hiDiv2;
 748
 749     pivot = hsa->pivot;
 750     vec = hsa->vec;
 751     elsize = hsa->elsize;
 752     vec2 =  (char *)vec - 2 * elsize;
 753     cmp = hsa->cmp;
 754     arg = hsa->arg;
 755
 756     fastcopy = hsa->fastcopy;
 757 #define MEMCPY(p,q,n) \
 758     (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
 759
 760     if (lo == 1) {
 761         j = 2;
 762         b = (char *)vec + elsize;
 763         if (j < hi && cmp(vec, b, arg) < 0)
 764             j++;
 765         a = (char *)vec + (hi - 1) * elsize;
 766         b = (char *)vec2 + j * elsize;
 767
 768         /*
 769          * During sorting phase b points to a member of heap that cannot be
 770          * bigger then biggest of vec[0] and vec[1], and cmp(a, b, arg) <= 0
 771          * always holds.
 772          */
 773         if ((building || hi == 2) && cmp(a, b, arg) >= 0)
 774             return;
 775
 776         MEMCPY(pivot, a, elsize);
 777         MEMCPY(a, b, elsize);
 778         lo = j;
 779     } else {
 780         a = (char *)vec2 + lo * elsize;
 781         MEMCPY(pivot, a, elsize);
 782     }
 783
 784     hiDiv2 = hi/2;
 785     while (lo <= hiDiv2) {
 786         j = lo + lo;
 787         a = (char *)vec2 + j * elsize;
 788         b = (char *)vec + (j - 1) * elsize;
 789         if (j < hi && cmp(a, b, arg) < 0)
 790             j++;
 791         b = (char *)vec2 + j * elsize;
 792         if (cmp(pivot, b, arg) >= 0)
 793             break;
 794
 795         a = (char *)vec2 + lo * elsize;
 796         MEMCPY(a, b, elsize);
 797         lo = j;
 798     }
 799
 800     a = (char *)vec2 + lo * elsize;
 801     MEMCPY(a, pivot, elsize);
 802 #undef MEMCPY
 803 }
 804
 805 void
 806 js_HeapSort(void *vec, size_t nel, void *pivot, size_t elsize,
 807             JSComparator cmp, void *arg)
 808 {
 809     HSortArgs hsa;
 810     size_t i;
 811
 812     hsa.vec = vec;
 813     hsa.elsize = elsize;
 814     hsa.pivot = pivot;
 815     hsa.cmp = cmp;
 816     hsa.arg = arg;
 817     hsa.fastcopy = (cmp == sort_compare || cmp == sort_compare_strings);
 818
 819     for (i = nel/2; i != 0; i--)
 820         HeapSortHelper(JS_TRUE, &hsa, i, nel);
 821     while (nel > 2)
 822         HeapSortHelper(JS_FALSE, &hsa, 1, --nel);
 823 }
 824
 825 typedef struct CompareArgs {
 826     JSContext   *context;
 827     jsval       fval;
 828     jsval       *localroot;     /* need one local root, for sort_compare */
 829     JSBool      status;
 830 } CompareArgs;
 831
 832 static int
 833 sort_compare(const void *a, const void *b, void *arg)
 834 {
 835     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
 836     CompareArgs *ca = (CompareArgs *) arg;
 837     JSContext *cx = ca->context;
 838     jsdouble cmp = -1;
 839     jsval fval, argv[2], special;
 840     JSBool ok;
 841
 842     fval = ca->fval;
 843
 844     /*
 845      * By ECMA 262, 15.4.4.11, existence of the property with value undefined
 846      * takes precedence over an undefined property (which we call a "hole").
 847      */
 848     if (av == JSVAL_HOLE || bv == JSVAL_HOLE)
 849         special = JSVAL_HOLE;
 850     else if (av == JSVAL_VOID || bv == JSVAL_VOID)
 851         special = JSVAL_VOID;
 852     else
 853         special = JSVAL_NULL;
 854
 855     if (special != JSVAL_NULL) {
 856         if (av == bv)
 857             cmp = 0;
 858         else if (av != special)
 859             cmp = -1;
 860         else
 861             cmp = 1;
 862     } else if (fval == JSVAL_NULL) {
 863         JSString *astr, *bstr;
 864
 865         if (av == bv) {
 866             cmp = 0;
 867         } else {
 868             /*
 869              * Set our local root to astr in case the second js_ValueToString
 870              * displaces the newborn root in cx, and the GC nests under that
 871              * call.  Don't bother guarding the local root store with an astr
 872              * non-null test.  If we tag null as a string, the GC will untag,
 873              * null-test, and avoid dereferencing null.
 874              */
 875             astr = js_ValueToString(cx, av);
 876             *ca->localroot = STRING_TO_JSVAL(astr);
 877             if (astr && (bstr = js_ValueToString(cx, bv)))
 878                 cmp = js_CompareStrings(astr, bstr);
 879             else
 880                 ca->status = JS_FALSE;
 881         }
 882     } else {
 883         argv[0] = av;
 884         argv[1] = bv;
 885         ok = js_InternalCall(cx,
 886                              OBJ_GET_PARENT(cx, JSVAL_TO_OBJECT(fval)),
 887                              fval, 2, argv, ca->localroot);
 888         if (ok) {
 889             ok = js_ValueToNumber(cx, *ca->localroot, &cmp);
 890
 891             /* Clamp cmp to -1, 0, 1. */
 892             if (ok) {
 893                 if (JSDOUBLE_IS_NaN(cmp)) {
 894                     /*
 895                      * XXX report some kind of error here?  ECMA talks about
 896                      * 'consistent compare functions' that don't return NaN,
 897                      * but is silent about what the result should be.  So we
 898                      * currently ignore it.
 899                      */
 900                     cmp = 0;
 901                 } else if (cmp != 0) {
 902                     cmp = cmp > 0 ? 1 : -1;
 903                 }
 904             }
 905         }
 906         if (!ok)
 907             ca->status = ok;
 908     }
 909     return (int)cmp;
 910 }
 911
 912 static int
 913 sort_compare_strings(const void *a, const void *b, void *arg)
 914 {
 915     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
 916
 917     return (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
 918 }
 919
 920 static JSBool
 921 array_sort(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
 922 {
 923     jsval fval, *vec, *pivotroot;
 924     CompareArgs ca;
 925     jsuint len, newlen, i;
 926     JSStackFrame *fp;
 927     jsid id;
 928     size_t nbytes;
 929
 930     /*
 931      * Optimize the default compare function case if all of obj's elements
 932      * have values of type string.
 933      */
 934     JSBool all_strings;
 935
 936     if (argc > 0) {
 937         if (JSVAL_IS_PRIMITIVE(argv[0])) {
 938             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
 939                                  JSMSG_BAD_SORT_ARG);
 940             return JS_FALSE;
 941         }
 942         fval = argv[0];
 943         all_strings = JS_FALSE; /* non-default compare function */
 944     } else {
 945         fval = JSVAL_NULL;
 946         all_strings = JS_TRUE;  /* check for all string values */
 947     }
 948
 949     if (!js_GetLengthProperty(cx, obj, &len))
 950         return JS_FALSE;
 951     if (len == 0) {
 952         *rval = OBJECT_TO_JSVAL(obj);
 953         return JS_TRUE;
 954     }
 955
 956     /*
 957      * We need a temporary array of len jsvals to hold elements of the array.
 958      * Check that its size does not overflow size_t, which would allow for
 959      * indexing beyond the end of the malloc'd vector.
 960      */
 961     if (len > ((size_t) -1) / sizeof(jsval)) {
 962         JS_ReportOutOfMemory(cx);
 963         return JS_FALSE;
 964     }
 965     nbytes = ((size_t) len) * sizeof(jsval);
 966
 967     vec = (jsval *) JS_malloc(cx, nbytes);
 968     if (!vec)
 969         return JS_FALSE;
 970
 971     /* Root vec, clearing it first in case a GC nests while we're filling it. */
 972     memset(vec, 0, nbytes);
 973     fp = cx->fp;
 974     fp->vars = vec;
 975     fp->nvars = len;
 976
 977     newlen = 0;
 978     for (i = 0; i < len; i++) {
 979         ca.status = IndexToExistingId(cx, obj, i, &id);
 980         if (!ca.status)
 981             goto out;
 982
 983         if (id == JSID_HOLE) {
 984             vec[i] = JSVAL_HOLE;
 985             all_strings = JS_FALSE;
 986             continue;
 987         }
 988         newlen++;
 989
 990         ca.status = OBJ_GET_PROPERTY(cx, obj, id, &vec[i]);
 991         if (!ca.status)
 992             goto out;
 993
 994         /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
 995         all_strings &= JSVAL_IS_STRING(vec[i]);
 996     }
 997
 998     ca.context = cx;
 999     ca.fval = fval;
1000     ca.localroot = argv + argc;       /* local GC root for temporary string */
1001     pivotroot    = argv + argc + 1;   /* local GC root for pivot val */
1002     ca.status = JS_TRUE;
1003     js_HeapSort(vec, (size_t) len, pivotroot, sizeof(jsval),
1004                 all_strings ? sort_compare_strings : sort_compare,
1005                 &ca);
1006
1007     if (ca.status) {
1008         ca.status = InitArrayElements(cx, obj, newlen, vec);
1009         if (ca.status)
1010             *rval = OBJECT_TO_JSVAL(obj);
1011
1012         /* Re-create any holes that sorted to the end of the array. */
1013         while (len > newlen) {
1014             jsval junk;
1015
1016             if (!IndexToId(cx, --len, &id))
1017                 return JS_FALSE;
1018             if (!OBJ_DELETE_PROPERTY(cx, obj, id, &junk))
1019                 return JS_FALSE;
1020         }
1021     }
1022
1023 out:
1024     if (vec)
1025         JS_free(cx, vec);
1026     return ca.status;
1027 }
1028 #endif /* JS_HAS_SOME_PERL_FUN */
1029
1030 #if JS_HAS_MORE_PERL_FUN
1031 /*
1032  * Perl-inspired push, pop, shift, unshift, and splice methods.
1033  */
1034 static JSBool
1035 array_push(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1036 {
1037     jsuint length;
1038     uintN i;
1039     jsid id;
1040
1041     if (!js_GetLengthProperty(cx, obj, &length))
1042         return JS_FALSE;
1043     for (i = 0; i < argc; i++) {
1044         if (!IndexToId(cx, length + i, &id))
1045             return JS_FALSE;
1046         if (!OBJ_SET_PROPERTY(cx, obj, id, &argv[i]))
1047             return JS_FALSE;
1048     }
1049
1050     /*
1051      * If JS1.2, follow Perl4 by returning the last thing pushed.  Otherwise,
1052      * return the new array length.
1053      */
1054     length += argc;
1055     if (JS_VERSION_IS_1_2(cx)) {
1056         *rval = argc ? argv[argc-1] : JSVAL_VOID;
1057     } else {
1058         if (!IndexToValue(cx, length, rval))
1059             return JS_FALSE;
1060     }
1061     return js_SetLengthProperty(cx, obj, length);
1062 }
1063
1064 static JSBool
1065 array_pop(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1066 {
1067     jsuint index;
1068     jsid id;
1069     JSBool ok;
1070     jsval junk;
1071
1072     if (!js_GetLengthProperty(cx, obj, &index))
1073         return JS_FALSE;
1074     if (index > 0) {
1075         index--;
1076
1077         /* Get the to-be-deleted property's value into rval. */
1078         if (!IndexToId(cx, index, &id))
1079             return JS_FALSE;
1080
1081         /* See comments in array_reverse. */
1082         if (index > JSVAL_INT_MAX)
1083             JS_KEEP_ATOMS(cx->runtime);
1084         ok = OBJ_GET_PROPERTY(cx, obj, id, rval) &&
1085              OBJ_DELETE_PROPERTY(cx, obj, id, &junk);
1086         if (index > JSVAL_INT_MAX)
1087             JS_UNKEEP_ATOMS(cx->runtime);
1088         if (!ok)
1089             return JS_FALSE;
1090     }
1091     return js_SetLengthProperty(cx, obj, index);
1092 }
1093
1094 static JSBool
1095 array_shift(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1096 {
1097     jsuint length, i;
1098     jsid id, id2;
1099     jsval junk;
1100
1101     if (!js_GetLengthProperty(cx, obj, &length))
1102         return JS_FALSE;
1103     if (length > 0) {
1104         length--;
1105         id = JSVAL_ZERO;
1106
1107         /* Get the to-be-deleted property's value into rval ASAP. */
1108         if (!OBJ_GET_PROPERTY(cx, obj, id, rval))
1109             return JS_FALSE;
1110
1111         /*
1112          * Slide down the array above the first element.
1113          */
1114         if (length > 0) {
1115             for (i = 1; i <= length; i++) {
1116                 if (!IndexToId(cx, i, &id))
1117                     return JS_FALSE;
1118                 if (!OBJ_GET_PROPERTY(cx, obj, id, &argv[0]))
1119                     return JS_FALSE;
1120
1121                 /* Get id after value to avoid nested GC hazards. */
1122                 if (!IndexToId(cx, i - 1, &id2))
1123                     return JS_FALSE;
1124                 if (!OBJ_SET_PROPERTY(cx, obj, id2, &argv[0]))
1125                     return JS_FALSE;
1126             }
1127         }
1128
1129         /*
1130          * Delete the only or the last element. We recreate id when it is an
1131          * atom to protect against a nested GC during the last iteration.
1132          */
1133         if (length > JSVAL_INT_MAX && !IndexToId(cx, length, &id))
1134             return JS_FALSE;
1135         if (!OBJ_DELETE_PROPERTY(cx, obj, id, &junk))
1136             return JS_FALSE;
1137     }
1138     return js_SetLengthProperty(cx, obj, length);
1139 }
1140
1141 static JSBool
1142 array_unshift(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1143               jsval *rval)
1144 {
1145     jsuint length, last;
1146     uintN i;
1147     jsid id, id2;
1148     jsval *vp, junk;
1149
1150     if (!js_GetLengthProperty(cx, obj, &length))
1151         return JS_FALSE;
1152     if (argc > 0) {
1153         /* Slide up the array to make room for argc at the bottom. */
1154         if (length > 0) {
1155             last = length;
1156             vp = argv + argc;
1157             while (last--) {
1158                 if (!IndexToExistingId(cx, obj, last, &id))
1159                     return JS_FALSE;
1160                 if (id != JSID_HOLE) {
1161                     if (!OBJ_GET_PROPERTY(cx, obj, id, vp))
1162                         return JS_FALSE;
1163                 }
1164
1165                 /* Get id after value to avoid nested GC hazards. */
1166                 if (!IndexToId(cx, last + argc, &id2))
1167                     return JS_FALSE;
1168                 if (id == JSID_HOLE) {
1169                     if (!OBJ_DELETE_PROPERTY(cx, obj, id2, &junk))
1170                         return JS_FALSE;
1171                 } else {
1172                     if (!OBJ_SET_PROPERTY(cx, obj, id2, vp))
1173                         return JS_FALSE;
1174                 }
1175             }
1176         }
1177
1178         /* Copy from argv to the bottom of the array. */
1179         for (i = 0; i < argc; i++) {
1180             if (!IndexToId(cx, i, &id))
1181                 return JS_FALSE;
1182             if (!OBJ_SET_PROPERTY(cx, obj, id, &argv[i]))
1183                 return JS_FALSE;
1184         }
1185
1186         /* Follow Perl by returning the new array length. */
1187         length += argc;
1188         if (!js_SetLengthProperty(cx, obj, length))
1189             return JS_FALSE;
1190     }
1191     return IndexToValue(cx, length, rval);
1192 }
1193
1194 static JSBool
1195 array_splice(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1196 {
1197     jsval *vp, junk;
1198     jsuint length, begin, end, count, delta, last;
1199     jsdouble d;
1200     jsid id, id2;
1201     JSObject *obj2;
1202     uintN i;
1203
1204     /*
1205      * Nothing to do if no args.  Otherwise point vp at our one explicit local
1206      * root and get length.
1207      */
1208     if (argc == 0)
1209         return JS_TRUE;
1210     vp = argv + argc;
1211     if (!js_GetLengthProperty(cx, obj, &length))
1212         return JS_FALSE;
1213
1214     /* Convert the first argument into a starting index. */
1215     if (!js_ValueToNumber(cx, *argv, &d))
1216         return JS_FALSE;
1217     d = js_DoubleToInteger(d);
1218     if (d < 0) {
1219         d += length;
1220         if (d < 0)
1221             d = 0;
1222     } else if (d > length) {
1223         d = length;
1224     }
1225     begin = (jsuint)d; /* d has been clamped to uint32 */
1226     argc--;
1227     argv++;
1228
1229     /* Convert the second argument from a count into a fencepost index. */
1230     delta = length - begin;
1231     if (argc == 0) {
1232         count = delta;
1233         end = length;
1234     } else {
1235         if (!js_ValueToNumber(cx, *argv, &d))
1236             return JS_FALSE;
1237         d = js_DoubleToInteger(d);
1238         if (d < 0)
1239             d = 0;
1240         else if (d > delta)
1241             d = delta;
1242         count = (jsuint)d;
1243         end = begin + count;
1244         argc--;
1245         argv++;
1246     }
1247
1248     if (count == 1 && JS_VERSION_IS_1_2(cx)) {
1249         /*
1250          * JS lacks "list context", whereby in Perl one turns the single
1251          * scalar that's spliced out into an array just by assigning it to
1252          * @single instead of $single, or by using it as Perl push's first
1253          * argument, for instance.
1254          *
1255          * JS1.2 emulated Perl too closely and returned a non-Array for
1256          * the single-splice-out case, requiring callers to test and wrap
1257          * in [] if necessary.  So JS1.3, default, and other versions all
1258          * return an array of length 1 for uniformity.
1259          */
1260         if (!IndexToId(cx, begin, &id))
1261             return JS_FALSE;
1262         if (!OBJ_GET_PROPERTY(cx, obj, id, rval))
1263             return JS_FALSE;
1264     } else {
1265         if (!JS_VERSION_IS_1_2(cx) || count > 0) {
1266             /*
1267              * Create a new array value to return.  Our ECMA v2 proposal specs
1268              * that splice always returns an array value, even when given no
1269              * arguments.  We think this is best because it eliminates the need
1270              * for callers to do an extra test to handle the empty splice case.
1271              */
1272             obj2 = js_NewArrayObject(cx, 0, NULL);
1273             if (!obj2)
1274                 return JS_FALSE;
1275             *rval = OBJECT_TO_JSVAL(obj2);
1276
1277             /* If there are elements to remove, put them into the return value. */
1278             if (count > 0) {
1279                 for (last = begin; last < end; last++) {
1280                     if (!IndexToExistingId(cx, obj, last, &id))
1281                         return JS_FALSE;
1282                     if (id == JSID_HOLE)
1283                         continue;       /* don't fill holes in the new array */
1284                     if (!OBJ_GET_PROPERTY(cx, obj, id, vp))
1285                         return JS_FALSE;
1286
1287                     /* Get id after value to avoid nested GC hazards. */
1288                     if (!IndexToId(cx, last - begin, &id2))
1289                         return JS_FALSE;
1290                     if (!OBJ_SET_PROPERTY(cx, obj2, id2, vp))
1291                         return JS_FALSE;
1292                 }
1293
1294                 if (!js_SetLengthProperty(cx, obj2, end - begin))
1295                     return JS_FALSE;
1296             }
1297         }
1298     }
1299
1300     /* Find the direction (up or down) to copy and make way for argv. */
1301     if (argc > count) {
1302         delta = (jsuint)argc - count;
1303         last = length;
1304         /* (uint) end could be 0, so can't use vanilla >= test */
1305         while (last-- > end) {
1306             if (!IndexToExistingId(cx, obj, last, &id))
1307                 return JS_FALSE;
1308             if (id != JSID_HOLE) {
1309                 if (!OBJ_GET_PROPERTY(cx, obj, id, vp))
1310                     return JS_FALSE;
1311             }
1312
1313             /* Get id after value to avoid nested GC hazards. */
1314             if (!IndexToId(cx, last + delta, &id2))
1315                 return JS_FALSE;
1316             if (id != JSID_HOLE) {
1317                 if (!OBJ_SET_PROPERTY(cx, obj, id2, vp))
1318                     return JS_FALSE;
1319             } else {
1320                 if (!OBJ_DELETE_PROPERTY(cx, obj, id2, &junk))
1321                     return JS_FALSE;
1322             }
1323         }
1324         length += delta;
1325     } else if (argc < count) {
1326         delta = count - (jsuint)argc;
1327         for (last = end; last < length; last++) {
1328             if (!IndexToExistingId(cx, obj, last, &id))
1329                 return JS_FALSE;
1330             if (id != JSID_HOLE) {
1331                 if (!OBJ_GET_PROPERTY(cx, obj, id, vp))
1332                     return JS_FALSE;
1333             }
1334
1335             /* Get id after value to avoid nested GC hazards. */
1336             if (!IndexToId(cx, last - delta, &id2))
1337                 return JS_FALSE;
1338             if (id != JSID_HOLE) {
1339                 if (!OBJ_SET_PROPERTY(cx, obj, id2, vp))
1340                     return JS_FALSE;
1341             } else {
1342                 if (!OBJ_DELETE_PROPERTY(cx, obj, id2, &junk))
1343                     return JS_FALSE;
1344             }
1345         }
1346         length -= delta;
1347     }
1348
1349     /* Copy from argv into the hole to complete the splice. */
1350     for (i = 0; i < argc; i++) {
1351         if (!IndexToId(cx, begin + i, &id))
1352             return JS_FALSE;
1353         if (!OBJ_SET_PROPERTY(cx, obj, id, &argv[i]))
1354             return JS_FALSE;
1355     }
1356
1357     /* Update length in case we deleted elements from the end. */
1358     return js_SetLengthProperty(cx, obj, length);
1359 }
1360 #endif /* JS_HAS_MORE_PERL_FUN */
1361
1362 #if JS_HAS_SEQUENCE_OPS
1363 /*
1364  * Python-esque sequence operations.
1365  */
1366 static JSBool
1367 array_concat(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1368 {
1369     jsval *vp, v;
1370     JSObject *nobj, *aobj;
1371     jsuint length, alength, slot;
1372     uintN i;
1373     jsid id, id2;
1374
1375     /* Hoist the explicit local root address computation. */
1376     vp = argv + argc;
1377
1378     /* Treat obj as the first argument; see ECMA 15.4.4.4. */
1379     --argv;
1380     JS_ASSERT(obj == JSVAL_TO_OBJECT(argv[0]));
1381
1382     /* Create a new Array object and store it in the rval local root. */
1383     nobj = js_NewArrayObject(cx, 0, NULL);
1384     if (!nobj)
1385         return JS_FALSE;
1386     *rval = OBJECT_TO_JSVAL(nobj);
1387
1388     /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
1389     length = 0;
1390     for (i = 0; i <= argc; i++) {
1391         v = argv[i];
1392         if (JSVAL_IS_OBJECT(v)) {
1393             aobj = JSVAL_TO_OBJECT(v);
1394             if (aobj && OBJ_GET_CLASS(cx, aobj) == &js_ArrayClass) {
1395                 if (!OBJ_GET_PROPERTY(cx, aobj,
1396                                       ATOM_TO_JSID(cx->runtime->atomState
1397                                                    .lengthAtom),
1398                                       vp)) {
1399                     return JS_FALSE;
1400                 }
1401                 if (!ValueIsLength(cx, *vp, &alength))
1402                     return JS_FALSE;
1403                 for (slot = 0; slot < alength; slot++) {
1404                     if (!IndexToExistingId(cx, aobj, slot, &id))
1405                         return JS_FALSE;
1406                     if (id == JSID_HOLE) {
1407                         /*
1408                          * Per ECMA 262, 15.4.4.4, step 9, ignore non-existent
1409                          * properties.
1410                          */
1411                         continue;
1412                     }
1413                     if (!OBJ_GET_PROPERTY(cx, aobj, id, vp))
1414                         return JS_FALSE;
1415
1416                     /* Get id after value to avoid nested GC hazards. */
1417                     if (!IndexToId(cx, length + slot, &id2))
1418                         return JS_FALSE;
1419                     if (!OBJ_SET_PROPERTY(cx, nobj, id2, vp))
1420                         return JS_FALSE;
1421                 }
1422                 length += alength;
1423                 continue;
1424             }
1425         }
1426
1427         *vp = v;
1428         if (!IndexToId(cx, length, &id))
1429             return JS_FALSE;
1430         if (!OBJ_SET_PROPERTY(cx, nobj, id, vp))
1431             return JS_FALSE;
1432         length++;
1433     }
1434
1435     return js_SetLengthProperty(cx, nobj, length);
1436 }
1437
1438 static JSBool
1439 array_slice(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1440 {
1441     jsval *vp;
1442     JSObject *nobj;
1443     jsuint length, begin, end, slot;
1444     jsdouble d;
1445     jsid id, id2;
1446
1447     /* Hoist the explicit local root address computation. */
1448     vp = argv + argc;
1449
1450     /* Create a new Array object and store it in the rval local root. */
1451     nobj = js_NewArrayObject(cx, 0, NULL);
1452     if (!nobj)
1453         return JS_FALSE;
1454     *rval = OBJECT_TO_JSVAL(nobj);
1455
1456     if (!js_GetLengthProperty(cx, obj, &length))
1457         return JS_FALSE;
1458     begin = 0;
1459     end = length;
1460
1461     if (argc > 0) {
1462         if (!js_ValueToNumber(cx, argv[0], &d))
1463             return JS_FALSE;
1464         d = js_DoubleToInteger(d);
1465         if (d < 0) {
1466             d += length;
1467             if (d < 0)
1468                 d = 0;
1469         } else if (d > length) {
1470             d = length;
1471         }
1472         begin = (jsuint)d;
1473
1474         if (argc > 1) {
1475             if (!js_ValueToNumber(cx, argv[1], &d))
1476                 return JS_FALSE;
1477             d = js_DoubleToInteger(d);
1478             if (d < 0) {
1479                 d += length;
1480                 if (d < 0)
1481                     d = 0;
1482             } else if (d > length) {
1483                 d = length;
1484             }
1485             end = (jsuint)d;
1486         }
1487     }
1488
1489     if (begin > end)
1490         begin = end;
1491
1492     for (slot = begin; slot < end; slot++) {
1493         if (!IndexToExistingId(cx, obj, slot, &id))
1494             return JS_FALSE;
1495         if (id == JSID_HOLE)
1496             continue;
1497         if (!OBJ_GET_PROPERTY(cx, obj, id, vp))
1498             return JS_FALSE;
1499
1500         /* Get id after value to avoid nested GC hazards. */
1501         if (!IndexToId(cx, slot - begin, &id2))
1502             return JS_FALSE;
1503         if (!OBJ_SET_PROPERTY(cx, nobj, id2, vp))
1504             return JS_FALSE;
1505     }
1506     return js_SetLengthProperty(cx, nobj, end - begin);
1507 }
1508 #endif /* JS_HAS_SEQUENCE_OPS */
1509
1510 #if JS_HAS_ARRAY_EXTRAS
1511
1512 static JSBool
1513 array_indexOfHelper(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1514                     jsval *rval, JSBool isLast)
1515 {
1516     jsuint length, i, stop;
1517     jsint direction;
1518
1519     if (!js_GetLengthProperty(cx, obj, &length))
1520         return JS_FALSE;
1521     if (length == 0)
1522         goto not_found;
1523
1524     if (argc <= 1) {
1525         i = isLast ? length - 1 : 0;
1526     } else {
1527         jsdouble start;
1528
1529         if (!js_ValueToNumber(cx, argv[1], &start))
1530             return JS_FALSE;
1531         start = js_DoubleToInteger(start);
1532         if (start < 0) {
1533             start += length;
1534             i = (start < 0) ? 0 : (jsuint)start;
1535         } else if (start >= length) {
1536             i = length - 1;
1537         } else {
1538             i = (jsuint)start;
1539         }
1540     }
1541
1542     if (isLast) {
1543         stop = 0;
1544         direction = -1;
1545     } else {
1546         stop = length - 1;
1547         direction = 1;
1548     }
1549
1550     for (;;) {
1551         jsid id;
1552         jsval v;
1553
1554         if (!IndexToExistingId(cx, obj, (jsuint)i, &id))
1555             return JS_FALSE;
1556         if (id != JSID_HOLE) {
1557             if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
1558                 return JS_FALSE;
1559             if (js_StrictlyEqual(v, argv[0]))
1560                 return js_NewNumberValue(cx, i, rval);
1561         }
1562
1563         if (i == stop)
1564             goto not_found;
1565         i += direction;
1566     }
1567
1568   not_found:
1569     *rval = INT_TO_JSVAL(-1);
1570     return JS_TRUE;
1571 }
1572
1573 static JSBool
1574 array_indexOf(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1575               jsval *rval)
1576 {
1577     return array_indexOfHelper(cx, obj, argc, argv, rval, JS_FALSE);
1578 }
1579
1580 static JSBool
1581 array_lastIndexOf(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1582                   jsval *rval)
1583 {
1584     return array_indexOfHelper(cx, obj, argc, argv, rval, JS_TRUE);
1585 }
1586
1587 /* Order is important; extras that use a caller's predicate must follow MAP. */
1588 typedef enum ArrayExtraMode {
1589     FOREACH,
1590     MAP,
1591     FILTER,
1592     SOME,
1593     EVERY
1594 } ArrayExtraMode;
1595
1596 static JSBool
1597 array_extra(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval,
1598             ArrayExtraMode mode)
1599 {
1600     jsval *vp, *sp, *origsp, *oldsp;
1601     jsuint length, newlen, i;
1602     JSObject *callable, *thisp, *newarr;
1603     void *mark;
1604     JSStackFrame *fp;
1605     JSBool ok, b;
1606
1607     /* Hoist the explicit local root address computation. */
1608     vp = argv + argc;
1609
1610     if (!js_GetLengthProperty(cx, obj, &length))
1611         return JS_FALSE;
1612
1613     /*
1614      * First, get or compute our callee, so that we error out consistently
1615      * when passed a non-callable object.
1616      */
1617     callable = js_ValueToCallableObject(cx, &argv[0], 0);
1618     if (!callable)
1619         return JS_FALSE;
1620
1621     /*
1622      * Set our initial return condition, used for zero-length array cases
1623      * (and pre-size our map return to match our known length, for all cases).
1624      */
1625 #ifdef __GNUC__ /* quell GCC overwarning */
1626     newlen = 0;
1627     newarr = NULL;
1628     ok = JS_TRUE;
1629 #endif
1630     switch (mode) {
1631       case MAP:
1632       case FILTER:
1633         newlen = (mode == MAP) ? length : 0;
1634         newarr = js_NewArrayObject(cx, newlen, NULL);
1635         if (!newarr)
1636             return JS_FALSE;
1637         *rval = OBJECT_TO_JSVAL(newarr);
1638         break;
1639       case SOME:
1640         *rval = JSVAL_FALSE;
1641         break;
1642       case EVERY:
1643         *rval = JSVAL_TRUE;
1644         break;
1645       case FOREACH:
1646         break;
1647     }
1648
1649     if (length == 0)
1650         return JS_TRUE;
1651
1652     if (argc > 1) {
1653         if (!js_ValueToObject(cx, argv[1], &thisp))
1654             return JS_FALSE;
1655         argv[1] = OBJECT_TO_JSVAL(thisp);
1656     } else {
1657         thisp = NULL;
1658     }
1659
1660     /* We call with 3 args (value, index, array), plus room for rval. */
1661     origsp = js_AllocStack(cx, 2 + 3 + 1, &mark);
1662     if (!origsp)
1663         return JS_FALSE;
1664
1665     /* Lift current frame to include our args. */
1666     fp = cx->fp;
1667     oldsp = fp->sp;
1668
1669     for (i = 0; i < length; i++) {
1670         jsid id;
1671         jsval rval2;
1672
1673         ok = IndexToExistingId(cx, obj, i, &id);
1674         if (!ok)
1675             break;
1676         if (id == JSID_HOLE)
1677             continue;
1678         ok = OBJ_GET_PROPERTY(cx, obj, id, vp);
1679         if (!ok)
1680             break;
1681
1682         /*
1683          * Push callable and 'this', then args. We must do this for every
1684          * iteration around the loop since js_Invoke uses origsp[0] for rval
1685          * storage and some native functions use origsp[1] for local rooting.
1686          */
1687         sp = origsp;
1688         *sp++ = OBJECT_TO_JSVAL(callable);
1689         *sp++ = OBJECT_TO_JSVAL(thisp);
1690         *sp++ = *vp;
1691         *sp++ = INT_TO_JSVAL(i);
1692         *sp++ = OBJECT_TO_JSVAL(obj);
1693
1694         /* Do the call. */
1695         fp->sp = sp;
1696         ok = js_Invoke(cx, 3, JSINVOKE_INTERNAL);
1697         rval2 = fp->sp[-1];
1698         fp->sp = oldsp;
1699         if (!ok)
1700             break;
1701
1702         if (mode > MAP) {
1703             if (rval2 == JSVAL_NULL) {
1704                 b = JS_FALSE;
1705             } else if (JSVAL_IS_BOOLEAN(rval2)) {
1706                 b = JSVAL_TO_BOOLEAN(rval2);
1707             } else {
1708                 ok = js_ValueToBoolean(cx, rval2, &b);
1709                 if (!ok)
1710                     goto out;
1711             }
1712         }
1713
1714         switch (mode) {
1715           case FOREACH:
1716             break;
1717           case MAP:
1718             /*
1719              * We reconstruct id once again when it is a GC thing since scripts
1720              * can trigger GC that collects it. See bug 341956.
1721              */
1722             if (i > JSVAL_INT_MAX) {
1723                 ok = IndexToId(cx, i, &id);
1724                 if (!ok)
1725                     goto out;
1726             }
1727             ok = OBJ_SET_PROPERTY(cx, newarr, id, &rval2);
1728             if (!ok)
1729                 goto out;
1730             break;
1731           case FILTER:
1732             if (!b)
1733                 break;
1734             /* Filter passed *vp, push as result. */
1735             ok = IndexToId(cx, newlen++, &id);
1736             if (!ok)
1737                 goto out;
1738             ok = OBJ_SET_PROPERTY(cx, newarr, id, vp);
1739             if (!ok)
1740                 goto out;
1741             break;
1742           case SOME:
1743             if (b) {
1744                 *rval = JSVAL_TRUE;
1745                 goto out;
1746             }
1747             break;
1748           case EVERY:
1749             if (!b) {
1750                 *rval = JSVAL_FALSE;
1751                 goto out;
1752             }
1753             break;
1754         }
1755     }
1756
1757  out:
1758     js_FreeStack(cx, mark);
1759     if (ok && mode == FILTER)
1760         ok = js_SetLengthProperty(cx, newarr, newlen);
1761     return ok;
1762 }
1763
1764 static JSBool
1765 array_forEach(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1766               jsval *rval)
1767 {
1768     return array_extra(cx, obj, argc, argv, rval, FOREACH);
1769 }
1770
1771 static JSBool
1772 array_map(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1773           jsval *rval)
1774 {
1775     return array_extra(cx, obj, argc, argv, rval, MAP);
1776 }
1777
1778 static JSBool
1779 array_filter(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1780              jsval *rval)
1781 {
1782     return array_extra(cx, obj, argc, argv, rval, FILTER);
1783 }
1784
1785 static JSBool
1786 array_some(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1787            jsval *rval)
1788 {
1789     return array_extra(cx, obj, argc, argv, rval, SOME);
1790 }
1791
1792 static JSBool
1793 array_every(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1794            jsval *rval)
1795 {
1796     return array_extra(cx, obj, argc, argv, rval, EVERY);
1797 }
1798 #endif
1799
1800 static JSFunctionSpec array_methods[] = {
1801 #if JS_HAS_TOSOURCE
1802     {js_toSource_str,       array_toSource,         0,0,0},
1803 #endif
1804     {js_toString_str,       array_toString,         0,0,0},
1805     {js_toLocaleString_str, array_toLocaleString,   0,0,0},
1806
1807     /* Perl-ish methods. */
1808 #if JS_HAS_SOME_PERL_FUN
1809     {"join",                array_join,             1,JSFUN_GENERIC_NATIVE,0},
1810     {"reverse",             array_reverse,          0,JSFUN_GENERIC_NATIVE,2},
1811     {"sort",                array_sort,             1,JSFUN_GENERIC_NATIVE,2},
1812 #endif
1813 #if JS_HAS_MORE_PERL_FUN
1814     {"push",                array_push,             1,JSFUN_GENERIC_NATIVE,0},
1815     {"pop",                 array_pop,              0,JSFUN_GENERIC_NATIVE,0},
1816     {"shift",               array_shift,            0,JSFUN_GENERIC_NATIVE,1},
1817     {"unshift",             array_unshift,          1,JSFUN_GENERIC_NATIVE,1},
1818     {"splice",              array_splice,           2,JSFUN_GENERIC_NATIVE,1},
1819 #endif
1820
1821     /* Python-esque sequence methods. */
1822 #if JS_HAS_SEQUENCE_OPS
1823     {"concat",              array_concat,           1,JSFUN_GENERIC_NATIVE,1},
1824     {"slice",               array_slice,            2,JSFUN_GENERIC_NATIVE,1},
1825 #endif
1826
1827 #if JS_HAS_ARRAY_EXTRAS
1828     {"indexOf",             array_indexOf,          1,JSFUN_GENERIC_NATIVE,0},
1829     {"lastIndexOf",         array_lastIndexOf,      1,JSFUN_GENERIC_NATIVE,0},
1830     {"forEach",             array_forEach,          1,JSFUN_GENERIC_NATIVE,1},
1831     {"map",                 array_map,              1,JSFUN_GENERIC_NATIVE,1},
1832     {"filter",              array_filter,           1,JSFUN_GENERIC_NATIVE,1},
1833     {"some",                array_some,             1,JSFUN_GENERIC_NATIVE,1},
1834     {"every",               array_every,            1,JSFUN_GENERIC_NATIVE,1},
1835 #endif
1836
1837     {0,0,0,0,0}
1838 };
1839
1840 static JSBool
1841 Array(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1842 {
1843     jsuint length;
1844     jsval *vector;
1845
1846     /* If called without new, replace obj with a new Array object. */
1847     if (!(cx->fp->flags & JSFRAME_CONSTRUCTING)) {
1848         obj = js_NewObject(cx, &js_ArrayClass, NULL, NULL);
1849         if (!obj)
1850             return JS_FALSE;
1851         *rval = OBJECT_TO_JSVAL(obj);
1852     }
1853
1854     if (argc == 0) {
1855         length = 0;
1856         vector = NULL;
1857     } else if (JS_VERSION_IS_1_2(cx)) {
1858         length = (jsuint) argc;
1859         vector = argv;
1860     } else if (argc > 1) {
1861         length = (jsuint) argc;
1862         vector = argv;
1863     } else if (!JSVAL_IS_NUMBER(argv[0])) {
1864         length = 1;
1865         vector = argv;
1866     } else {
1867         if (!ValueIsLength(cx, argv[0], &length))
1868             return JS_FALSE;
1869         vector = NULL;
1870     }
1871     return InitArrayObject(cx, obj, length, vector);
1872 }
1873
1874 JSObject *
1875 js_InitArrayClass(JSContext *cx, JSObject *obj)
1876 {
1877     JSObject *proto;
1878
1879     proto = JS_InitClass(cx, obj, NULL, &js_ArrayClass, Array, 1,
1880                          NULL, array_methods, NULL, NULL);
1881
1882     /* Initialize the Array prototype object so it gets a length property. */
1883     if (!proto || !InitArrayObject(cx, proto, 0, NULL))
1884         return NULL;
1885     return proto;
1886 }
1887
1888 JSObject *
1889 js_NewArrayObject(JSContext *cx, jsuint length, jsval *vector)
1890 {
1891     JSObject *obj;
1892
1893     obj = js_NewObject(cx, &js_ArrayClass, NULL, NULL);
1894     if (!obj)
1895         return NULL;
1896     if (!InitArrayObject(cx, obj, length, vector)) {
1897         cx->newborn[GCX_OBJECT] = NULL;
1898         return NULL;
1899     }
1900     return obj;
1901 }