Back to index

lightning-sunbird  0.9+nobinonly
jsarray.c
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  * vim: set sw=4 ts=8 et tw=80:
00003  *
00004  * ***** BEGIN LICENSE BLOCK *****
00005  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00006  *
00007  * The contents of this file are subject to the Mozilla Public License Version
00008  * 1.1 (the "License"); you may not use this file except in compliance with
00009  * the License. You may obtain a copy of the License at
00010  * http://www.mozilla.org/MPL/
00011  *
00012  * Software distributed under the License is distributed on an "AS IS" basis,
00013  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00014  * for the specific language governing rights and limitations under the
00015  * License.
00016  *
00017  * The Original Code is Mozilla Communicator client code, released
00018  * March 31, 1998.
00019  *
00020  * The Initial Developer of the Original Code is
00021  * Netscape Communications Corporation.
00022  * Portions created by the Initial Developer are Copyright (C) 1998
00023  * the Initial Developer. All Rights Reserved.
00024  *
00025  * Contributor(s):
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either of the GNU General Public License Version 2 or later (the "GPL"),
00029  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK ***** */
00040 
00041 /*
00042  * JS array class.
00043  */
00044 #include "jsstddef.h"
00045 #include <stdlib.h>
00046 #include <string.h>
00047 #include "jstypes.h"
00048 #include "jsutil.h" /* Added by JSIFY */
00049 #include "jsapi.h"
00050 #include "jsarray.h"
00051 #include "jsatom.h"
00052 #include "jsbool.h"
00053 #include "jscntxt.h"
00054 #include "jsconfig.h"
00055 #include "jsfun.h"
00056 #include "jsgc.h"
00057 #include "jsinterp.h"
00058 #include "jslock.h"
00059 #include "jsnum.h"
00060 #include "jsobj.h"
00061 #include "jsstr.h"
00062 
00063 /* 2^32 - 1 as a number and a string */
00064 #define MAXINDEX 4294967295u
00065 #define MAXSTR   "4294967295"
00066 
00067 /*
00068  * Determine if the id represents an array index or an XML property index.
00069  *
00070  * An id is an array index according to ECMA by (15.4):
00071  *
00072  * "Array objects give special treatment to a certain class of property names.
00073  * A property name P (in the form of a string value) is an array index if and
00074  * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
00075  * to 2^32-1."
00076  *
00077  * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
00078  * except that by using signed 32-bit integers we miss the top half of the
00079  * valid range. This function checks the string representation itself; note
00080  * that calling a standard conversion routine might allow strings such as
00081  * "08" or "4.0" as array indices, which they are not.
00082  */
00083 JSBool
00084 js_IdIsIndex(jsval id, jsuint *indexp)
00085 {
00086     JSString *str;
00087     jschar *cp;
00088 
00089     if (JSVAL_IS_INT(id)) {
00090         jsint i;
00091         i = JSVAL_TO_INT(id);
00092         if (i < 0)
00093             return JS_FALSE;
00094         *indexp = (jsuint)i;
00095         return JS_TRUE;
00096     }
00097 
00098     /* NB: id should be a string, but jsxml.c may call us with an object id. */
00099     if (!JSVAL_IS_STRING(id))
00100         return JS_FALSE;
00101 
00102     str = JSVAL_TO_STRING(id);
00103     cp = JSSTRING_CHARS(str);
00104     if (JS7_ISDEC(*cp) && JSSTRING_LENGTH(str) < sizeof(MAXSTR)) {
00105         jsuint index = JS7_UNDEC(*cp++);
00106         jsuint oldIndex = 0;
00107         jsuint c = 0;
00108         if (index != 0) {
00109             while (JS7_ISDEC(*cp)) {
00110                 oldIndex = index;
00111                 c = JS7_UNDEC(*cp);
00112                 index = 10*index + c;
00113                 cp++;
00114             }
00115         }
00116 
00117         /* Ensure that all characters were consumed and we didn't overflow. */
00118         if (*cp == 0 &&
00119              (oldIndex < (MAXINDEX / 10) ||
00120               (oldIndex == (MAXINDEX / 10) && c < (MAXINDEX % 10))))
00121         {
00122             *indexp = index;
00123             return JS_TRUE;
00124         }
00125     }
00126     return JS_FALSE;
00127 }
00128 
00129 static JSBool
00130 ValueIsLength(JSContext *cx, jsval v, jsuint *lengthp)
00131 {
00132     jsint i;
00133     jsdouble d;
00134 
00135     if (JSVAL_IS_INT(v)) {
00136         i = JSVAL_TO_INT(v);
00137         if (i < 0) {
00138             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
00139                                  JSMSG_BAD_ARRAY_LENGTH);
00140             return JS_FALSE;
00141         }
00142         *lengthp = (jsuint) i;
00143         return JS_TRUE;
00144     }
00145 
00146     if (!js_ValueToNumber(cx, v, &d)) {
00147         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
00148                              JSMSG_BAD_ARRAY_LENGTH);
00149         return JS_FALSE;
00150     }
00151     if (!js_DoubleToECMAUint32(cx, d, (uint32 *)lengthp)) {
00152         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
00153                              JSMSG_BAD_ARRAY_LENGTH);
00154         return JS_FALSE;
00155     }
00156     if (JSDOUBLE_IS_NaN(d) || d != *lengthp) {
00157         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
00158                              JSMSG_BAD_ARRAY_LENGTH);
00159         return JS_FALSE;
00160     }
00161     return JS_TRUE;
00162 }
00163 
00164 JSBool
00165 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
00166 {
00167     JSTempValueRooter tvr;
00168     jsid id;
00169     JSBool ok;
00170     jsint i;
00171 
00172     JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
00173     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
00174     ok = OBJ_GET_PROPERTY(cx, obj, id, &tvr.u.value);
00175     if (ok) {
00176         /*
00177          * Short-circuit, because js_ValueToECMAUint32 fails when called
00178          * during init time.
00179          */
00180         if (JSVAL_IS_INT(tvr.u.value)) {
00181             i = JSVAL_TO_INT(tvr.u.value);
00182             *lengthp = (jsuint)i;       /* jsuint cast does ToUint32 */
00183         } else {
00184             ok = js_ValueToECMAUint32(cx, tvr.u.value, (uint32 *)lengthp);
00185         }
00186     }
00187     JS_POP_TEMP_ROOT(cx, &tvr);
00188     return ok;
00189 }
00190 
00191 static JSBool
00192 IndexToValue(JSContext *cx, jsuint index, jsval *vp)
00193 {
00194     if (index <= JSVAL_INT_MAX) {
00195         *vp = INT_TO_JSVAL(index);
00196         return JS_TRUE;
00197     }
00198     return js_NewDoubleValue(cx, (jsdouble)index, vp);
00199 }
00200 
00201 static JSBool
00202 BigIndexToId(JSContext *cx, JSObject *obj, jsuint index, JSBool createAtom,
00203              jsid *idp)
00204 {
00205     jschar buf[10], *start;
00206     JSClass *clasp;
00207     JSAtom *atom;
00208     JS_STATIC_ASSERT((jsuint)-1 == 4294967295U);
00209 
00210     JS_ASSERT(index > JSVAL_INT_MAX);
00211 
00212     start = JS_ARRAY_END(buf);
00213     do {
00214         --start;
00215         *start = (jschar)('0' + index % 10);
00216         index /= 10;
00217     } while (index != 0);
00218 
00219     /*
00220      * Skip the atomization if the class is known to store atoms corresponding
00221      * to big indexes together with elements. In such case we know that the
00222      * array does not have an element at the given index if its atom does not
00223      * exist.
00224      */
00225     if (!createAtom &&
00226         ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_ArrayClass ||
00227          clasp == &js_ArgumentsClass ||
00228          clasp == &js_ObjectClass)) {
00229         atom = js_GetExistingStringAtom(cx, start, JS_ARRAY_END(buf) - start);
00230         if (!atom) {
00231             *idp = JSVAL_VOID;
00232             return JS_TRUE;
00233         }
00234     } else {
00235         atom = js_AtomizeChars(cx, start, JS_ARRAY_END(buf) - start, 0);
00236         if (!atom)
00237             return JS_FALSE;
00238     }
00239 
00240     *idp = ATOM_TO_JSID(atom);
00241     return JS_TRUE;
00242 }
00243 
00244 /*
00245  * If the property at the given index exists, get its value into location
00246  * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
00247  * to JSVAL_VOID. This function assumes that the location pointed by vp is
00248  * properly rooted and can be used as GC-protected storage for temporaries.
00249  */
00250 static JSBool
00251 GetArrayElement(JSContext *cx, JSObject *obj, jsuint index, JSBool *hole,
00252                 jsval *vp)
00253 {
00254     jsid id;
00255     JSObject *obj2;
00256     JSProperty *prop;
00257 
00258     if (index <= JSVAL_INT_MAX) {
00259         id = INT_TO_JSID(index);
00260     } else {
00261         if (!BigIndexToId(cx, obj, index, JS_FALSE, &id))
00262             return JS_FALSE;
00263         if (id == JSVAL_VOID) {
00264             *hole = JS_TRUE;
00265             *vp = JSVAL_VOID;
00266             return JS_TRUE;
00267         }
00268     }
00269 
00270     if (!OBJ_LOOKUP_PROPERTY(cx, obj, id, &obj2, &prop))
00271         return JS_FALSE;
00272     if (!prop) {
00273         *hole = JS_TRUE;
00274         *vp = JSVAL_VOID;
00275     } else {
00276         OBJ_DROP_PROPERTY(cx, obj2, prop);
00277         if (!OBJ_GET_PROPERTY(cx, obj, id, vp))
00278             return JS_FALSE;
00279         *hole = JS_FALSE;
00280     }
00281     return JS_TRUE;
00282 }
00283 
00284 /*
00285  * Set the value of the property at the given index to v assuming v is rooted.
00286  */
00287 static JSBool
00288 SetArrayElement(JSContext *cx, JSObject *obj, jsuint index, jsval v)
00289 {
00290     jsid id;
00291 
00292     if (index <= JSVAL_INT_MAX) {
00293         id = INT_TO_JSID(index);
00294     } else {
00295         if (!BigIndexToId(cx, obj, index, JS_TRUE, &id))
00296             return JS_FALSE;
00297         JS_ASSERT(id != JSVAL_VOID);
00298     }
00299     return OBJ_SET_PROPERTY(cx, obj, id, &v);
00300 }
00301 
00302 static JSBool
00303 DeleteArrayElement(JSContext *cx, JSObject *obj, jsuint index)
00304 {
00305     jsid id;
00306     jsval junk;
00307 
00308     if (index <= JSVAL_INT_MAX) {
00309         id = INT_TO_JSID(index);
00310     } else {
00311         if (!BigIndexToId(cx, obj, index, JS_FALSE, &id))
00312             return JS_FALSE;
00313         if (id == JSVAL_VOID)
00314             return JS_TRUE;
00315     }
00316     return OBJ_DELETE_PROPERTY(cx, obj, id, &junk);
00317 }
00318 
00319 /*
00320  * When hole is true, delete the property at the given index. Otherwise set
00321  * its value to v assuming v is rooted.
00322  */
00323 static JSBool
00324 SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsuint index,
00325                         JSBool hole, jsval v)
00326 {
00327     if (hole) {
00328         JS_ASSERT(v == JSVAL_VOID);
00329         return DeleteArrayElement(cx, obj, index);
00330     } else {
00331         return SetArrayElement(cx, obj, index, v);
00332     }
00333 }
00334 
00335 
00336 JSBool
00337 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsuint length)
00338 {
00339     jsval v;
00340     jsid id;
00341 
00342     if (!IndexToValue(cx, length, &v))
00343         return JS_FALSE;
00344     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
00345     return OBJ_SET_PROPERTY(cx, obj, id, &v);
00346 }
00347 
00348 JSBool
00349 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
00350 {
00351     JSErrorReporter older;
00352     JSTempValueRooter tvr;
00353     jsid id;
00354     JSBool ok;
00355 
00356     older = JS_SetErrorReporter(cx, NULL);
00357     JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
00358     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
00359     ok = OBJ_GET_PROPERTY(cx, obj, id, &tvr.u.value);
00360     JS_SetErrorReporter(cx, older);
00361     if (ok)
00362         ok = ValueIsLength(cx, tvr.u.value, lengthp);
00363     JS_POP_TEMP_ROOT(cx, &tvr);
00364     return ok;
00365 }
00366 
00367 JSBool
00368 js_IsArrayLike(JSContext *cx, JSObject *obj, JSBool *answerp, jsuint *lengthp)
00369 {
00370     JSClass *clasp;
00371 
00372     clasp = OBJ_GET_CLASS(cx, obj);
00373     *answerp = (clasp == &js_ArgumentsClass || clasp == &js_ArrayClass);
00374     if (!*answerp) {
00375         *lengthp = 0;
00376         return JS_TRUE;
00377     }
00378     return js_GetLengthProperty(cx, obj, lengthp);
00379 }
00380 
00381 /*
00382  * This get function is specific to Array.prototype.length and other array
00383  * instance length properties.  It calls back through the class get function
00384  * in case some magic happens there (see call_getProperty in jsfun.c).
00385  */
00386 static JSBool
00387 array_length_getter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
00388 {
00389     return OBJ_GET_CLASS(cx, obj)->getProperty(cx, obj, id, vp);
00390 }
00391 
00392 static JSBool
00393 array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
00394 {
00395     jsuint newlen, oldlen, gap, index;
00396     jsid id2;
00397     jsval junk;
00398     JSObject *iter;
00399     JSTempValueRooter tvr;
00400     JSBool ok;
00401 
00402     if (!ValueIsLength(cx, *vp, &newlen))
00403         return JS_FALSE;
00404     if (!js_GetLengthProperty(cx, obj, &oldlen))
00405         return JS_FALSE;
00406     if (oldlen > newlen) {
00407         if (oldlen - newlen < (1 << 24)) {
00408             do {
00409                 --oldlen;
00410                 if (!DeleteArrayElement(cx, obj, oldlen))
00411                     return JS_FALSE;
00412             } while (oldlen != newlen);
00413         } else {
00414             /*
00415              * We are going to remove a lot of indexes in a presumably sparse
00416              * array. So instead of looping through indexes between newlen and
00417              * oldlen, we iterate through all properties and remove those that
00418              * correspond to indexes from the [newlen, oldlen) range.
00419              * See bug 322135.
00420              */
00421             iter = JS_NewPropertyIterator(cx, obj);
00422             if (!iter)
00423                 return JS_FALSE;
00424 
00425             /* Protect iter against GC in OBJ_DELETE_PROPERTY. */
00426             JS_PUSH_TEMP_ROOT_OBJECT(cx, iter, &tvr);
00427             gap = oldlen - newlen;
00428             for (;;) {
00429                 ok = JS_NextProperty(cx, iter, &id2);
00430                 if (!ok)
00431                     break;
00432                 if (id2 == JSVAL_VOID)
00433                     break;
00434                 if (js_IdIsIndex(id2, &index) && index - newlen < gap) {
00435                     ok = OBJ_DELETE_PROPERTY(cx, obj, id2, &junk);
00436                     if (!ok)
00437                         break;
00438                 }
00439             }
00440             JS_POP_TEMP_ROOT(cx, &tvr);
00441             if (!ok)
00442                 return JS_FALSE;
00443         }
00444     }
00445     return IndexToValue(cx, newlen, vp);
00446 }
00447 
00448 static JSBool
00449 array_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
00450 {
00451     jsuint index, length;
00452 
00453     if (!js_IdIsIndex(id, &index))
00454         return JS_TRUE;
00455     if (!js_GetLengthProperty(cx, obj, &length))
00456         return JS_FALSE;
00457     if (index >= length) {
00458         length = index + 1;
00459         return js_SetLengthProperty(cx, obj, length);
00460     }
00461     return JS_TRUE;
00462 }
00463 
00464 static JSBool
00465 array_convert(JSContext *cx, JSObject *obj, JSType type, jsval *vp)
00466 {
00467     return js_TryValueOf(cx, obj, type, vp);
00468 }
00469 
00470 JSClass js_ArrayClass = {
00471     "Array",
00472     JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
00473     array_addProperty, JS_PropertyStub,   JS_PropertyStub,   JS_PropertyStub,
00474     JS_EnumerateStub,  JS_ResolveStub,    array_convert,     JS_FinalizeStub,
00475     JSCLASS_NO_OPTIONAL_MEMBERS
00476 };
00477 
00478 enum ArrayToStringOp {
00479     TO_STRING,
00480     TO_LOCALE_STRING,
00481     TO_SOURCE
00482 };
00483 
00484 /*
00485  * When op is TO_STRING or TO_LOCALE_STRING sep indicates a separator to use
00486  * or "," when sep is NULL.
00487  * When op is TO_SOURCE sep must be NULL.
00488  */
00489 static JSBool
00490 array_join_sub(JSContext *cx, JSObject *obj, enum ArrayToStringOp op,
00491                JSString *sep, jsval *rval)
00492 {
00493     JSBool ok, hole;
00494     jsuint length, index;
00495     jschar *chars, *ochars;
00496     size_t nchars, growth, seplen, tmplen, extratail;
00497     const jschar *sepstr;
00498     JSString *str;
00499     JSHashEntry *he;
00500     JSTempValueRooter tvr;
00501     JSAtom *atom;
00502     int stackDummy;
00503 
00504     if (!JS_CHECK_STACK_SIZE(cx, stackDummy)) {
00505         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_OVER_RECURSED);
00506         return JS_FALSE;
00507     }
00508 
00509     ok = js_GetLengthProperty(cx, obj, &length);
00510     if (!ok)
00511         return JS_FALSE;
00512 
00513     he = js_EnterSharpObject(cx, obj, NULL, &chars);
00514     if (!he)
00515         return JS_FALSE;
00516 #ifdef DEBUG
00517     growth = (size_t) -1;
00518 #endif
00519 
00520     if (op == TO_SOURCE) {
00521         if (IS_SHARP(he)) {
00522 #if JS_HAS_SHARP_VARS
00523             nchars = js_strlen(chars);
00524 #else
00525             chars[0] = '[';
00526             chars[1] = ']';
00527             chars[2] = 0;
00528             nchars = 2;
00529 #endif
00530             goto make_string;
00531         }
00532 
00533         /*
00534          * Always allocate 2 extra chars for closing ']' and terminating 0
00535          * and then preallocate 1 + extratail to include starting '['.
00536          */
00537         extratail = 2;
00538         growth = (1 + extratail) * sizeof(jschar);
00539         if (!chars) {
00540             nchars = 0;
00541             chars = (jschar *) malloc(growth);
00542             if (!chars)
00543                 goto done;
00544         } else {
00545             MAKE_SHARP(he);
00546             nchars = js_strlen(chars);
00547             growth += nchars * sizeof(jschar);
00548             chars = (jschar *)realloc((ochars = chars), growth);
00549             if (!chars) {
00550                 free(ochars);
00551                 goto done;
00552             }
00553         }
00554         chars[nchars++] = '[';
00555         JS_ASSERT(sep == NULL);
00556         sepstr = NULL;  /* indicates to use ", " as separator */
00557         seplen = 2;
00558     } else {
00559         /*
00560          * Free any sharp variable definition in chars.  Normally, we would
00561          * MAKE_SHARP(he) so that only the first sharp variable annotation is
00562          * a definition, and all the rest are references, but in the current
00563          * case of (op != TO_SOURCE), we don't need chars at all.
00564          */
00565         if (chars)
00566             JS_free(cx, chars);
00567         chars = NULL;
00568         nchars = 0;
00569         extratail = 1;  /* allocate extra char for terminating 0 */
00570 
00571         /* Return the empty string on a cycle as well as on empty join. */
00572         if (IS_BUSY(he) || length == 0) {
00573             js_LeaveSharpObject(cx, NULL);
00574             *rval = JS_GetEmptyStringValue(cx);
00575             return ok;
00576         }
00577 
00578         /* Flag he as BUSY so we can distinguish a cycle from a join-point. */
00579         MAKE_BUSY(he);
00580 
00581         if (sep) {
00582             sepstr = JSSTRING_CHARS(sep);
00583             seplen = JSSTRING_LENGTH(sep);
00584         } else {
00585             sepstr = NULL;      /* indicates to use "," as separator */
00586             seplen = 1;
00587         }
00588     }
00589 
00590     /* Use rval to locally root each element value as we loop and convert. */
00591 #define v (*rval)
00592 
00593     for (index = 0; index < length; index++) {
00594         ok = GetArrayElement(cx, obj, index, &hole, &v);
00595         if (!ok)
00596             goto done;
00597         if (hole ||
00598             (op != TO_SOURCE && (JSVAL_IS_VOID(v) || JSVAL_IS_NULL(v)))) {
00599             str = cx->runtime->emptyString;
00600         } else {
00601             if (op == TO_LOCALE_STRING) {
00602                 atom = cx->runtime->atomState.toLocaleStringAtom;
00603                 JS_PUSH_TEMP_ROOT_OBJECT(cx, NULL, &tvr);
00604                 ok = js_ValueToObject(cx, v, &tvr.u.object) &&
00605                      js_TryMethod(cx, tvr.u.object, atom, 0, NULL, &v);
00606                 JS_POP_TEMP_ROOT(cx, &tvr);
00607                 if (!ok)
00608                     goto done;
00609                 str = js_ValueToString(cx, v);
00610             } else if (op == TO_STRING) {
00611                 str = js_ValueToString(cx, v);
00612             } else {
00613                 JS_ASSERT(op == TO_SOURCE);
00614                 str = js_ValueToSource(cx, v);
00615             }
00616             if (!str) {
00617                 ok = JS_FALSE;
00618                 goto done;
00619             }
00620         }
00621 
00622         /*
00623          * Do not append separator after the last element unless it is a hole
00624          * and we are in toSource. In that case we append single ",".
00625          */
00626         if (index + 1 == length)
00627             seplen = (hole && op == TO_SOURCE) ? 1 : 0;
00628 
00629         /* Allocate 1 at end for closing bracket and zero. */
00630         tmplen = JSSTRING_LENGTH(str);
00631         growth = nchars + tmplen + seplen + extratail;
00632         if (nchars > growth || tmplen > growth ||
00633             growth > (size_t)-1 / sizeof(jschar)) {
00634             if (chars) {
00635                 free(chars);
00636                 chars = NULL;
00637             }
00638             goto done;
00639         }
00640         growth *= sizeof(jschar);
00641         if (!chars) {
00642             chars = (jschar *) malloc(growth);
00643             if (!chars)
00644                 goto done;
00645         } else {
00646             chars = (jschar *) realloc((ochars = chars), growth);
00647             if (!chars) {
00648                 free(ochars);
00649                 goto done;
00650             }
00651         }
00652 
00653         js_strncpy(&chars[nchars], JSSTRING_CHARS(str), tmplen);
00654         nchars += tmplen;
00655 
00656         if (seplen) {
00657             if (sepstr) {
00658                 js_strncpy(&chars[nchars], sepstr, seplen);
00659             } else {
00660                 JS_ASSERT(seplen == 1 || seplen == 2);
00661                 chars[nchars] = ',';
00662                 if (seplen == 2)
00663                     chars[nchars + 1] = ' ';
00664             }
00665             nchars += seplen;
00666         }
00667     }
00668 
00669   done:
00670     if (op == TO_SOURCE) {
00671         if (chars)
00672             chars[nchars++] = ']';
00673     } else {
00674         CLEAR_BUSY(he);
00675     }
00676     js_LeaveSharpObject(cx, NULL);
00677     if (!ok) {
00678         if (chars)
00679             free(chars);
00680         return ok;
00681     }
00682 
00683 #undef v
00684 
00685   make_string:
00686     if (!chars) {
00687         JS_ReportOutOfMemory(cx);
00688         return JS_FALSE;
00689     }
00690     chars[nchars] = 0;
00691     JS_ASSERT(growth == (size_t)-1 || (nchars + 1) * sizeof(jschar) == growth);
00692     str = js_NewString(cx, chars, nchars, 0);
00693     if (!str) {
00694         free(chars);
00695         return JS_FALSE;
00696     }
00697     *rval = STRING_TO_JSVAL(str);
00698     return JS_TRUE;
00699 }
00700 
00701 #if JS_HAS_TOSOURCE
00702 static JSBool
00703 array_toSource(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
00704                jsval *rval)
00705 {
00706     return array_join_sub(cx, obj, TO_SOURCE, NULL, rval);
00707 }
00708 #endif
00709 
00710 static JSBool
00711 array_toString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
00712                jsval *rval)
00713 {
00714     return array_join_sub(cx, obj, TO_STRING, NULL, rval);
00715 }
00716 
00717 static JSBool
00718 array_toLocaleString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
00719                jsval *rval)
00720 {
00721     /*
00722      *  Passing comma here as the separator. Need a way to get a
00723      *  locale-specific version.
00724      */
00725     return array_join_sub(cx, obj, TO_LOCALE_STRING, NULL, rval);
00726 }
00727 
00728 static JSBool
00729 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint end,
00730                   jsval *vector)
00731 {
00732     while (start != end) {
00733         if (!SetArrayElement(cx, obj, start++, *vector++))
00734             return JS_FALSE;
00735     }
00736     return JS_TRUE;
00737 }
00738 
00739 static JSBool
00740 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
00741 {
00742     jsval v;
00743     jsid id;
00744 
00745     if (!IndexToValue(cx, length, &v))
00746         return JS_FALSE;
00747     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
00748     if (!OBJ_DEFINE_PROPERTY(cx, obj, id, v,
00749                              array_length_getter, array_length_setter,
00750                              JSPROP_PERMANENT,
00751                              NULL)) {
00752           return JS_FALSE;
00753     }
00754     if (!vector)
00755         return JS_TRUE;
00756     return InitArrayElements(cx, obj, 0, length, vector);
00757 }
00758 
00759 /*
00760  * Perl-inspired join, reverse, and sort.
00761  */
00762 static JSBool
00763 array_join(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
00764 {
00765     JSString *str;
00766 
00767     if (JSVAL_IS_VOID(argv[0])) {
00768         str = NULL;
00769     } else {
00770         str = js_ValueToString(cx, argv[0]);
00771         if (!str)
00772             return JS_FALSE;
00773         argv[0] = STRING_TO_JSVAL(str);
00774     }
00775     return array_join_sub(cx, obj, TO_STRING, str, rval);
00776 }
00777 
00778 static JSBool
00779 array_reverse(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
00780               jsval *rval)
00781 {
00782     jsuint len, half, i;
00783     JSBool hole, hole2;
00784     jsval *tmproot, *tmproot2;
00785 
00786     if (!js_GetLengthProperty(cx, obj, &len))
00787         return JS_FALSE;
00788 
00789     /*
00790      * Use argv[argc] and argv[argc + 1] as local roots to hold temporarily
00791      * array elements for GC-safe swap.
00792      */
00793     tmproot = argv + argc;
00794     tmproot2 = argv + argc + 1;
00795     half = len / 2;
00796     for (i = 0; i < half; i++) {
00797         if (!GetArrayElement(cx, obj, i, &hole, tmproot) ||
00798             !GetArrayElement(cx, obj, len - i - 1, &hole2, tmproot2) ||
00799             !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, *tmproot) ||
00800             !SetOrDeleteArrayElement(cx, obj, i, hole2, *tmproot2)) {
00801             return JS_FALSE;
00802         }
00803     }
00804     *rval = OBJECT_TO_JSVAL(obj);
00805     return JS_TRUE;
00806 }
00807 
00808 typedef struct HSortArgs {
00809     void         *vec;
00810     size_t       elsize;
00811     void         *pivot;
00812     JSComparator cmp;
00813     void         *arg;
00814     JSBool       fastcopy;
00815 } HSortArgs;
00816 
00817 static JSBool
00818 sort_compare(void *arg, const void *a, const void *b, int *result);
00819 
00820 static int
00821 sort_compare_strings(void *arg, const void *a, const void *b, int *result);
00822 
00823 static JSBool
00824 HeapSortHelper(JSBool building, HSortArgs *hsa, size_t lo, size_t hi)
00825 {
00826     void *pivot, *vec, *vec2, *arg, *a, *b;
00827     size_t elsize;
00828     JSComparator cmp;
00829     JSBool fastcopy;
00830     size_t j, hiDiv2;
00831     int cmp_result;
00832 
00833     pivot = hsa->pivot;
00834     vec = hsa->vec;
00835     elsize = hsa->elsize;
00836     vec2 =  (char *)vec - 2 * elsize;
00837     cmp = hsa->cmp;
00838     arg = hsa->arg;
00839 
00840     fastcopy = hsa->fastcopy;
00841 #define MEMCPY(p,q,n) \
00842     (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
00843 #define CALL_CMP(a, b) \
00844     if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
00845 
00846     if (lo == 1) {
00847         j = 2;
00848         b = (char *)vec + elsize;
00849         if (j < hi) {
00850             CALL_CMP(vec, b);
00851             if (cmp_result < 0)
00852                 j++;
00853         }
00854         a = (char *)vec + (hi - 1) * elsize;
00855         b = (char *)vec2 + j * elsize;
00856 
00857         /*
00858          * During sorting phase b points to a member of heap that cannot be
00859          * bigger then biggest of vec[0] and vec[1], and cmp(a, b, arg) <= 0
00860          * always holds.
00861          */
00862         if (building || hi == 2) {
00863             CALL_CMP(a, b);
00864             if (cmp_result >= 0)
00865                 return JS_TRUE;
00866         }
00867 
00868         MEMCPY(pivot, a, elsize);
00869         MEMCPY(a, b, elsize);
00870         lo = j;
00871     } else {
00872         a = (char *)vec2 + lo * elsize;
00873         MEMCPY(pivot, a, elsize);
00874     }
00875 
00876     hiDiv2 = hi/2;
00877     while (lo <= hiDiv2) {
00878         j = lo + lo;
00879         a = (char *)vec2 + j * elsize;
00880         b = (char *)vec + (j - 1) * elsize;
00881         if (j < hi) {
00882             CALL_CMP(a, b);
00883             if (cmp_result < 0)
00884                 j++;
00885         }
00886         b = (char *)vec2 + j * elsize;
00887         CALL_CMP(pivot, b);
00888         if (cmp_result >= 0)
00889             break;
00890 
00891         a = (char *)vec2 + lo * elsize;
00892         MEMCPY(a, b, elsize);
00893         lo = j;
00894     }
00895 
00896     a = (char *)vec2 + lo * elsize;
00897     MEMCPY(a, pivot, elsize);
00898 
00899     return JS_TRUE;
00900 
00901 #undef CALL_CMP
00902 #undef MEMCPY
00903 
00904 }
00905 
00906 JSBool
00907 js_HeapSort(void *vec, size_t nel, void *pivot, size_t elsize,
00908             JSComparator cmp, void *arg)
00909 {
00910     HSortArgs hsa;
00911     size_t i;
00912 
00913     hsa.vec = vec;
00914     hsa.elsize = elsize;
00915     hsa.pivot = pivot;
00916     hsa.cmp = cmp;
00917     hsa.arg = arg;
00918     hsa.fastcopy = (cmp == sort_compare || cmp == sort_compare_strings);
00919 
00920     for (i = nel/2; i != 0; i--) {
00921         if (!HeapSortHelper(JS_TRUE, &hsa, i, nel))
00922             return JS_FALSE;
00923     }
00924     while (nel > 2) {
00925         if (!HeapSortHelper(JS_FALSE, &hsa, 1, --nel))
00926             return JS_FALSE;
00927     }
00928 
00929     return JS_TRUE;
00930 }
00931 
00932 typedef struct CompareArgs {
00933     JSContext   *context;
00934     jsval       fval;
00935     jsval       *localroot;     /* need one local root, for sort_compare */
00936 } CompareArgs;
00937 
00938 static JSBool
00939 sort_compare(void *arg, const void *a, const void *b, int *result)
00940 {
00941     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
00942     CompareArgs *ca = (CompareArgs *) arg;
00943     JSContext *cx = ca->context;
00944     jsval fval;
00945     JSBool ok;
00946 
00951     JS_ASSERT(av != JSVAL_VOID);
00952     JS_ASSERT(bv != JSVAL_VOID);
00953 
00954     *result = 0;
00955     ok = JS_TRUE;
00956     fval = ca->fval;
00957     if (fval == JSVAL_NULL) {
00958         JSString *astr, *bstr;
00959 
00960         if (av != bv) {
00961             /*
00962              * Set our local root to astr in case the second js_ValueToString
00963              * displaces the newborn root in cx, and the GC nests under that
00964              * call.  Don't bother guarding the local root store with an astr
00965              * non-null test.  If we tag null as a string, the GC will untag,
00966              * null-test, and avoid dereferencing null.
00967              */
00968             astr = js_ValueToString(cx, av);
00969             *ca->localroot = STRING_TO_JSVAL(astr);
00970             if (astr && (bstr = js_ValueToString(cx, bv)))
00971                 *result = js_CompareStrings(astr, bstr);
00972             else
00973                 ok = JS_FALSE;
00974         }
00975     } else {
00976         jsdouble cmp;
00977         jsval argv[2];
00978 
00979         argv[0] = av;
00980         argv[1] = bv;
00981         ok = js_InternalCall(cx,
00982                              OBJ_GET_PARENT(cx, JSVAL_TO_OBJECT(fval)),
00983                              fval, 2, argv, ca->localroot);
00984         if (ok) {
00985             ok = js_ValueToNumber(cx, *ca->localroot, &cmp);
00986 
00987             /* Clamp cmp to -1, 0, 1. */
00988             if (ok) {
00989                 if (JSDOUBLE_IS_NaN(cmp)) {
00990                     /*
00991                      * XXX report some kind of error here?  ECMA talks about
00992                      * 'consistent compare functions' that don't return NaN,
00993                      * but is silent about what the result should be.  So we
00994                      * currently ignore it.
00995                      */
00996                 } else if (cmp != 0) {
00997                     *result = cmp > 0 ? 1 : -1;
00998                 }
00999             }
01000         }
01001     }
01002     return ok;
01003 }
01004 
01005 static int
01006 sort_compare_strings(void *arg, const void *a, const void *b, int *result)
01007 {
01008     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
01009 
01010     *result = (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
01011     return JS_TRUE;
01012 }
01013 
01014 static JSBool
01015 array_sort(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
01016 {
01017     jsval fval, *vec, *pivotroot;
01018     CompareArgs ca;
01019     jsuint len, newlen, i, undefs;
01020     JSTempValueRooter tvr;
01021     JSBool hole, ok;
01022 
01023     /*
01024      * Optimize the default compare function case if all of obj's elements
01025      * have values of type string.
01026      */
01027     JSBool all_strings;
01028 
01029     if (argc > 0) {
01030         if (JSVAL_IS_PRIMITIVE(argv[0])) {
01031             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
01032                                  JSMSG_BAD_SORT_ARG);
01033             return JS_FALSE;
01034         }
01035         fval = argv[0];
01036         all_strings = JS_FALSE; /* non-default compare function */
01037     } else {
01038         fval = JSVAL_NULL;
01039         all_strings = JS_TRUE;  /* check for all string values */
01040     }
01041 
01042     if (!js_GetLengthProperty(cx, obj, &len))
01043         return JS_FALSE;
01044     if (len == 0) {
01045         *rval = OBJECT_TO_JSVAL(obj);
01046         return JS_TRUE;
01047     }
01048 
01049     /*
01050      * We need a temporary array of len jsvals to hold elements of the array.
01051      * Check that its size does not overflow size_t, which would allow for
01052      * indexing beyond the end of the malloc'd vector.
01053      */
01054     if (len > ((size_t) -1) / sizeof(jsval)) {
01055         JS_ReportOutOfMemory(cx);
01056         return JS_FALSE;
01057     }
01058 
01059     vec = (jsval *) JS_malloc(cx, ((size_t) len) * sizeof(jsval));
01060     if (!vec)
01061         return JS_FALSE;
01062 
01063     /*
01064      * Initialize vec as a root. We will clear elements of vec one by
01065      * one while increasing tvr.count when we know that the property at
01066      * the corresponding index exists and its value must be rooted.
01067      *
01068      * In this way when sorting a huge mostly sparse array we will not
01069      * access the tail of vec corresponding to properties that do not
01070      * exist, allowing OS to avoiding committing RAM. See bug 330812.
01071      *
01072      * After this point control must flow through label out: to exit.
01073      */
01074     JS_PUSH_TEMP_ROOT(cx, 0, vec, &tvr);
01075 
01076     /*
01077      * By ECMA 262, 15.4.4.11, a property that does not exist (which we
01078      * call a "hole") is always greater than an existing property with
01079      * value undefined and that is always greater than any other property.
01080      * Thus to sort holes and undefs we simply count them, sort the rest
01081      * of elements, append undefs after them and then make holes after
01082      * undefs.
01083      */
01084     undefs = 0;
01085     newlen = 0;
01086     for (i = 0; i < len; i++) {
01087         /* Clear vec[newlen] before including it in the rooted set. */
01088         vec[newlen] = JSVAL_NULL;
01089         tvr.count = newlen + 1;
01090         ok = GetArrayElement(cx, obj, i, &hole, &vec[newlen]);
01091         if (!ok)
01092             goto out;
01093 
01094         if (hole)
01095             continue;
01096 
01097         if (vec[newlen] == JSVAL_VOID) {
01098             ++undefs;
01099             continue;
01100         }
01101 
01102         /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
01103         all_strings &= JSVAL_IS_STRING(vec[newlen]);
01104 
01105         ++newlen;
01106     }
01107 
01108     /* Here len == newlen + undefs + number_of_holes. */
01109     ca.context = cx;
01110     ca.fval = fval;
01111     ca.localroot = argv + argc;       /* local GC root for temporary string */
01112     pivotroot    = argv + argc + 1;   /* local GC root for pivot val */
01113     ok = js_HeapSort(vec, (size_t) newlen, pivotroot, sizeof(jsval),
01114                      all_strings ? sort_compare_strings : sort_compare,
01115                      &ca);
01116     if (!ok)
01117         goto out;
01118 
01119     ok = InitArrayElements(cx, obj, 0, newlen, vec);
01120     if (!ok)
01121         goto out;
01122 
01123   out:
01124     JS_POP_TEMP_ROOT(cx, &tvr);
01125     JS_free(cx, vec);
01126     if (!ok)
01127         return JS_FALSE;
01128 
01129     /* Set undefs that sorted after the rest of elements. */
01130     while (undefs != 0) {
01131         --undefs;
01132         if (!SetArrayElement(cx, obj, newlen++, JSVAL_VOID))
01133             return JS_FALSE;
01134     }
01135 
01136     /* Re-create any holes that sorted to the end of the array. */
01137     while (len > newlen) {
01138         if (!DeleteArrayElement(cx, obj, --len))
01139             return JS_FALSE;
01140     }
01141     *rval = OBJECT_TO_JSVAL(obj);
01142     return JS_TRUE;
01143 }
01144 
01145 /*
01146  * Perl-inspired push, pop, shift, unshift, and splice methods.
01147  */
01148 static JSBool
01149 array_push(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
01150 {
01151     jsuint length, newlength;
01152 
01153     if (!js_GetLengthProperty(cx, obj, &length))
01154         return JS_FALSE;
01155     newlength = length + argc;
01156     if (!InitArrayElements(cx, obj, length, newlength, argv))
01157         return JS_FALSE;
01158 
01159     /* Per ECMA-262, return the new array length. */
01160     if (!IndexToValue(cx, newlength, rval))
01161         return JS_FALSE;
01162     return js_SetLengthProperty(cx, obj, newlength);
01163 }
01164 
01165 static JSBool
01166 array_pop(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
01167 {
01168     jsuint index;
01169     JSBool hole;
01170 
01171     if (!js_GetLengthProperty(cx, obj, &index))
01172         return JS_FALSE;
01173     if (index > 0) {
01174         index--;
01175 
01176         /* Get the to-be-deleted property's value into rval. */
01177         if (!GetArrayElement(cx, obj, index, &hole, rval))
01178             return JS_FALSE;
01179         if (!hole && !DeleteArrayElement(cx, obj, index))
01180             return JS_FALSE;
01181     }
01182     return js_SetLengthProperty(cx, obj, index);
01183 }
01184 
01185 static JSBool
01186 array_shift(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
01187 {
01188     jsuint length, i;
01189     JSBool hole;
01190 
01191     if (!js_GetLengthProperty(cx, obj, &length))
01192         return JS_FALSE;
01193     if (length == 0) {
01194         *rval = JSVAL_VOID;
01195     } else {
01196         length--;
01197 
01198         /* Get the to-be-deleted property's value into rval ASAP. */
01199         if (!GetArrayElement(cx, obj, 0, &hole, rval))
01200             return JS_FALSE;
01201 
01202         /*
01203          * Slide down the array above the first element.
01204          */
01205         for (i = 0; i != length; i++) {
01206             if (!GetArrayElement(cx, obj, i + 1, &hole, &argv[0]))
01207                 return JS_FALSE;
01208             if (!SetOrDeleteArrayElement(cx, obj, i, hole, argv[0]))
01209                 return JS_FALSE;
01210         }
01211 
01212         /* Delete the only or last element when it exist. */
01213         if (!hole && !DeleteArrayElement(cx, obj, length))
01214             return JS_FALSE;
01215     }
01216     return js_SetLengthProperty(cx, obj, length);
01217 }
01218 
01219 static JSBool
01220 array_unshift(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01221               jsval *rval)
01222 {
01223     jsuint length, last;
01224     jsval *vp;
01225     JSBool hole;
01226 
01227     if (!js_GetLengthProperty(cx, obj, &length))
01228         return JS_FALSE;
01229     if (argc > 0) {
01230         /* Slide up the array to make room for argc at the bottom. */
01231         if (length > 0) {
01232             last = length;
01233             vp = argv + argc;   /* local root */
01234             do {
01235                 --last;
01236                 if (!GetArrayElement(cx, obj, last, &hole, vp) ||
01237                     !SetOrDeleteArrayElement(cx, obj, last + argc, hole, *vp)) {
01238                     return JS_FALSE;
01239                 }
01240             } while (last != 0);
01241         }
01242 
01243         /* Copy from argv to the bottom of the array. */
01244         if (!InitArrayElements(cx, obj, 0, argc, argv))
01245             return JS_FALSE;
01246 
01247         length += argc;
01248         if (!js_SetLengthProperty(cx, obj, length))
01249             return JS_FALSE;
01250     }
01251 
01252     /* Follow Perl by returning the new array length. */
01253     return IndexToValue(cx, length, rval);
01254 }
01255 
01256 static JSBool
01257 array_splice(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
01258 {
01259     jsval *vp;
01260     jsuint length, begin, end, count, delta, last;
01261     jsdouble d;
01262     JSBool hole;
01263     JSObject *obj2;
01264 
01265     /*
01266      * Nothing to do if no args.  Otherwise point vp at our one explicit local
01267      * root and get length.
01268      */
01269     if (argc == 0)
01270         return JS_TRUE;
01271     vp = argv + argc;
01272     if (!js_GetLengthProperty(cx, obj, &length))
01273         return JS_FALSE;
01274 
01275     /* Convert the first argument into a starting index. */
01276     if (!js_ValueToNumber(cx, *argv, &d))
01277         return JS_FALSE;
01278     d = js_DoubleToInteger(d);
01279     if (d < 0) {
01280         d += length;
01281         if (d < 0)
01282             d = 0;
01283     } else if (d > length) {
01284         d = length;
01285     }
01286     begin = (jsuint)d; /* d has been clamped to uint32 */
01287     argc--;
01288     argv++;
01289 
01290     /* Convert the second argument from a count into a fencepost index. */
01291     delta = length - begin;
01292     if (argc == 0) {
01293         count = delta;
01294         end = length;
01295     } else {
01296         if (!js_ValueToNumber(cx, *argv, &d))
01297             return JS_FALSE;
01298         d = js_DoubleToInteger(d);
01299         if (d < 0)
01300             d = 0;
01301         else if (d > delta)
01302             d = delta;
01303         count = (jsuint)d;
01304         end = begin + count;
01305         argc--;
01306         argv++;
01307     }
01308 
01309 
01310     /*
01311      * Create a new array value to return.  Our ECMA v2 proposal specs
01312      * that splice always returns an array value, even when given no
01313      * arguments.  We think this is best because it eliminates the need
01314      * for callers to do an extra test to handle the empty splice case.
01315      */
01316     obj2 = js_NewArrayObject(cx, 0, NULL);
01317     if (!obj2)
01318         return JS_FALSE;
01319     *rval = OBJECT_TO_JSVAL(obj2);
01320 
01321     /* If there are elements to remove, put them into the return value. */
01322     if (count > 0) {
01323         for (last = begin; last < end; last++) {
01324             if (!GetArrayElement(cx, obj, last, &hole, vp))
01325                 return JS_FALSE;
01326 
01327             /* Copy *vp to new array unless it's a hole. */
01328             if (!hole && !SetArrayElement(cx, obj2, last - begin, *vp))
01329                 return JS_FALSE;
01330         }
01331 
01332         if (!js_SetLengthProperty(cx, obj2, end - begin))
01333             return JS_FALSE;
01334     }
01335 
01336     /* Find the direction (up or down) to copy and make way for argv. */
01337     if (argc > count) {
01338         delta = (jsuint)argc - count;
01339         last = length;
01340         /* (uint) end could be 0, so can't use vanilla >= test */
01341         while (last-- > end) {
01342             if (!GetArrayElement(cx, obj, last, &hole, vp) ||
01343                 !SetOrDeleteArrayElement(cx, obj, last + delta, hole, *vp)) {
01344                 return JS_FALSE;
01345             }
01346         }
01347         length += delta;
01348     } else if (argc < count) {
01349         delta = count - (jsuint)argc;
01350         for (last = end; last < length; last++) {
01351             if (!GetArrayElement(cx, obj, last, &hole, vp) ||
01352                 !SetOrDeleteArrayElement(cx, obj, last - delta, hole, *vp)) {
01353                 return JS_FALSE;
01354             }
01355         }
01356         length -= delta;
01357     }
01358 
01359     /* Copy from argv into the hole to complete the splice. */
01360     if (!InitArrayElements(cx, obj, begin, begin + argc, argv))
01361         return JS_FALSE;
01362 
01363     /* Update length in case we deleted elements from the end. */
01364     return js_SetLengthProperty(cx, obj, length);
01365 }
01366 
01367 /*
01368  * Python-esque sequence operations.
01369  */
01370 static JSBool
01371 array_concat(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
01372 {
01373     jsval *vp, v;
01374     JSObject *nobj, *aobj;
01375     jsuint length, alength, slot;
01376     uintN i;
01377     JSBool hole;
01378 
01379     /* Hoist the explicit local root address computation. */
01380     vp = argv + argc;
01381 
01382     /* Treat obj as the first argument; see ECMA 15.4.4.4. */
01383     --argv;
01384     JS_ASSERT(obj == JSVAL_TO_OBJECT(argv[0]));
01385 
01386     /* Create a new Array object and store it in the rval local root. */
01387     nobj = js_NewArrayObject(cx, 0, NULL);
01388     if (!nobj)
01389         return JS_FALSE;
01390     *rval = OBJECT_TO_JSVAL(nobj);
01391 
01392     /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
01393     length = 0;
01394     for (i = 0; i <= argc; i++) {
01395         v = argv[i];
01396         if (JSVAL_IS_OBJECT(v)) {
01397             aobj = JSVAL_TO_OBJECT(v);
01398             if (aobj && OBJ_GET_CLASS(cx, aobj) == &js_ArrayClass) {
01399                 if (!OBJ_GET_PROPERTY(cx, aobj,
01400                                       ATOM_TO_JSID(cx->runtime->atomState
01401                                                    .lengthAtom),
01402                                       vp)) {
01403                     return JS_FALSE;
01404                 }
01405                 if (!ValueIsLength(cx, *vp, &alength))
01406                     return JS_FALSE;
01407                 for (slot = 0; slot < alength; slot++) {
01408                     if (!GetArrayElement(cx, aobj, slot, &hole, vp))
01409                         return JS_FALSE;
01410 
01411                     /*
01412                      * Per ECMA 262, 15.4.4.4, step 9, ignore non-existent
01413                      * properties.
01414                      */
01415                     if (!hole && !SetArrayElement(cx, nobj, length + slot, *vp))
01416                         return JS_FALSE;
01417                 }
01418                 length += alength;
01419                 continue;
01420             }
01421         }
01422 
01423         if (!SetArrayElement(cx, nobj, length, v))
01424             return JS_FALSE;
01425         length++;
01426     }
01427 
01428     return js_SetLengthProperty(cx, nobj, length);
01429 }
01430 
01431 static JSBool
01432 array_slice(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
01433 {
01434     jsval *vp;
01435     JSObject *nobj;
01436     jsuint length, begin, end, slot;
01437     jsdouble d;
01438     JSBool hole;
01439 
01440     /* Hoist the explicit local root address computation. */
01441     vp = argv + argc;
01442 
01443     /* Create a new Array object and store it in the rval local root. */
01444     nobj = js_NewArrayObject(cx, 0, NULL);
01445     if (!nobj)
01446         return JS_FALSE;
01447     *rval = OBJECT_TO_JSVAL(nobj);
01448 
01449     if (!js_GetLengthProperty(cx, obj, &length))
01450         return JS_FALSE;
01451     begin = 0;
01452     end = length;
01453 
01454     if (argc > 0) {
01455         if (!js_ValueToNumber(cx, argv[0], &d))
01456             return JS_FALSE;
01457         d = js_DoubleToInteger(d);
01458         if (d < 0) {
01459             d += length;
01460             if (d < 0)
01461                 d = 0;
01462         } else if (d > length) {
01463             d = length;
01464         }
01465         begin = (jsuint)d;
01466 
01467         if (argc > 1) {
01468             if (!js_ValueToNumber(cx, argv[1], &d))
01469                 return JS_FALSE;
01470             d = js_DoubleToInteger(d);
01471             if (d < 0) {
01472                 d += length;
01473                 if (d < 0)
01474                     d = 0;
01475             } else if (d > length) {
01476                 d = length;
01477             }
01478             end = (jsuint)d;
01479         }
01480     }
01481 
01482     if (begin > end)
01483         begin = end;
01484 
01485     for (slot = begin; slot < end; slot++) {
01486         if (!GetArrayElement(cx, obj, slot, &hole, vp))
01487             return JS_FALSE;
01488         if (!hole && !SetArrayElement(cx, nobj, slot - begin, *vp))
01489             return JS_FALSE;
01490     }
01491     return js_SetLengthProperty(cx, nobj, end - begin);
01492 }
01493 
01494 #if JS_HAS_ARRAY_EXTRAS
01495 
01496 static JSBool
01497 array_indexOfHelper(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01498                     jsval *rval, JSBool isLast)
01499 {
01500     jsuint length, i, stop;
01501     jsint direction;
01502     JSBool hole;
01503 
01504     if (!js_GetLengthProperty(cx, obj, &length))
01505         return JS_FALSE;
01506     if (length == 0)
01507         goto not_found;
01508 
01509     if (argc <= 1) {
01510         i = isLast ? length - 1 : 0;
01511     } else {
01512         jsdouble start;
01513 
01514         if (!js_ValueToNumber(cx, argv[1], &start))
01515             return JS_FALSE;
01516         start = js_DoubleToInteger(start);
01517         if (start < 0) {
01518             start += length;
01519             if (start < 0) {
01520                 if (isLast)
01521                     goto not_found;
01522                 i = 0;
01523             } else {
01524                 i = (jsuint)start;
01525             }
01526         } else if (start >= length) {
01527             if (!isLast)
01528                 goto not_found;
01529             i = length - 1;
01530         } else {
01531             i = (jsuint)start;
01532         }
01533     }
01534 
01535     if (isLast) {
01536         stop = 0;
01537         direction = -1;
01538     } else {
01539         stop = length - 1;
01540         direction = 1;
01541     }
01542 
01543     for (;;) {
01544         if (!GetArrayElement(cx, obj, (jsuint)i, &hole, rval))
01545             return JS_FALSE;
01546         if (!hole && js_StrictlyEqual(*rval, argv[0]))
01547             return js_NewNumberValue(cx, i, rval);
01548         if (i == stop)
01549             goto not_found;
01550         i += direction;
01551     }
01552 
01553   not_found:
01554     *rval = INT_TO_JSVAL(-1);
01555     return JS_TRUE;
01556 }
01557 
01558 static JSBool
01559 array_indexOf(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01560               jsval *rval)
01561 {
01562     return array_indexOfHelper(cx, obj, argc, argv, rval, JS_FALSE);
01563 }
01564 
01565 static JSBool
01566 array_lastIndexOf(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01567                   jsval *rval)
01568 {
01569     return array_indexOfHelper(cx, obj, argc, argv, rval, JS_TRUE);
01570 }
01571 
01572 /* Order is important; extras that use a caller's predicate must follow MAP. */
01573 typedef enum ArrayExtraMode {
01574     FOREACH,
01575     MAP,
01576     FILTER,
01577     SOME,
01578     EVERY
01579 } ArrayExtraMode;
01580 
01581 static JSBool
01582 array_extra(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval,
01583             ArrayExtraMode mode)
01584 {
01585     jsval *vp, *sp, *origsp, *oldsp;
01586     jsuint length, newlen, i;
01587     JSObject *callable, *thisp, *newarr;
01588     void *mark;
01589     JSStackFrame *fp;
01590     JSBool ok, cond, hole;
01591 
01592     /* Hoist the explicit local root address computation. */
01593     vp = argv + argc;
01594 
01595     if (!js_GetLengthProperty(cx, obj, &length))
01596         return JS_FALSE;
01597 
01598     /*
01599      * First, get or compute our callee, so that we error out consistently
01600      * when passed a non-callable object.
01601      */
01602     callable = js_ValueToCallableObject(cx, &argv[0], JSV2F_SEARCH_STACK);
01603     if (!callable)
01604         return JS_FALSE;
01605 
01606     /*
01607      * Set our initial return condition, used for zero-length array cases
01608      * (and pre-size our map return to match our known length, for all cases).
01609      */
01610 #ifdef __GNUC__ /* quell GCC overwarning */
01611     newlen = 0;
01612     newarr = NULL;
01613     ok = JS_TRUE;
01614 #endif
01615     switch (mode) {
01616       case MAP:
01617       case FILTER:
01618         newlen = (mode == MAP) ? length : 0;
01619         newarr = js_NewArrayObject(cx, newlen, NULL);
01620         if (!newarr)
01621             return JS_FALSE;
01622         *rval = OBJECT_TO_JSVAL(newarr);
01623         break;
01624       case SOME:
01625         *rval = JSVAL_FALSE;
01626         break;
01627       case EVERY:
01628         *rval = JSVAL_TRUE;
01629         break;
01630       case FOREACH:
01631         break;
01632     }
01633 
01634     if (length == 0)
01635         return JS_TRUE;
01636 
01637     if (argc > 1) {
01638         if (!js_ValueToObject(cx, argv[1], &thisp))
01639             return JS_FALSE;
01640         argv[1] = OBJECT_TO_JSVAL(thisp);
01641     } else {
01642         thisp = NULL;
01643     }
01644 
01645     /* We call with 3 args (value, index, array), plus room for rval. */
01646     origsp = js_AllocStack(cx, 2 + 3 + 1, &mark);
01647     if (!origsp)
01648         return JS_FALSE;
01649 
01650     /* Lift current frame to include our args. */
01651     fp = cx->fp;
01652     oldsp = fp->sp;
01653 
01654     for (i = 0; i < length; i++) {
01655         ok = GetArrayElement(cx, obj, i, &hole, vp);
01656         if (!ok)
01657             break;
01658         if (hole)
01659             continue;
01660 
01661         /*
01662          * Push callable and 'this', then args. We must do this for every
01663          * iteration around the loop since js_Invoke uses origsp[0] for rval
01664          * storage and some native functions use origsp[1] for local rooting.
01665          */
01666         sp = origsp;
01667         *sp++ = OBJECT_TO_JSVAL(callable);
01668         *sp++ = OBJECT_TO_JSVAL(thisp);
01669         *sp++ = *vp;
01670         *sp++ = INT_TO_JSVAL(i);
01671         *sp++ = OBJECT_TO_JSVAL(obj);
01672 
01673         /* Do the call. */
01674         fp->sp = sp;
01675         ok = js_Invoke(cx, 3, JSINVOKE_INTERNAL);
01676         vp[1] = fp->sp[-1];
01677         fp->sp = oldsp;
01678         if (!ok)
01679             break;
01680 
01681         if (mode > MAP) {
01682             if (vp[1] == JSVAL_NULL) {
01683                 cond = JS_FALSE;
01684             } else if (JSVAL_IS_BOOLEAN(vp[1])) {
01685                 cond = JSVAL_TO_BOOLEAN(vp[1]);
01686             } else {
01687                 ok = js_ValueToBoolean(cx, vp[1], &cond);
01688                 if (!ok)
01689                     goto out;
01690             }
01691         }
01692 
01693         switch (mode) {
01694           case FOREACH:
01695             break;
01696           case MAP:
01697             ok = SetArrayElement(cx, newarr, i, vp[1]);
01698             if (!ok)
01699                 goto out;
01700             break;
01701           case FILTER:
01702             if (!cond)
01703                 break;
01704             /* Filter passed *vp, push as result. */
01705             ok = SetArrayElement(cx, newarr, newlen++, *vp);
01706             if (!ok)
01707                 goto out;
01708             break;
01709           case SOME:
01710             if (cond) {
01711                 *rval = JSVAL_TRUE;
01712                 goto out;
01713             }
01714             break;
01715           case EVERY:
01716             if (!cond) {
01717                 *rval = JSVAL_FALSE;
01718                 goto out;
01719             }
01720             break;
01721         }
01722     }
01723 
01724  out:
01725     js_FreeStack(cx, mark);
01726     if (ok && mode == FILTER)
01727         ok = js_SetLengthProperty(cx, newarr, newlen);
01728     return ok;
01729 }
01730 
01731 static JSBool
01732 array_forEach(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01733               jsval *rval)
01734 {
01735     return array_extra(cx, obj, argc, argv, rval, FOREACH);
01736 }
01737 
01738 static JSBool
01739 array_map(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01740           jsval *rval)
01741 {
01742     return array_extra(cx, obj, argc, argv, rval, MAP);
01743 }
01744 
01745 static JSBool
01746 array_filter(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01747              jsval *rval)
01748 {
01749     return array_extra(cx, obj, argc, argv, rval, FILTER);
01750 }
01751 
01752 static JSBool
01753 array_some(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01754            jsval *rval)
01755 {
01756     return array_extra(cx, obj, argc, argv, rval, SOME);
01757 }
01758 
01759 static JSBool
01760 array_every(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
01761            jsval *rval)
01762 {
01763     return array_extra(cx, obj, argc, argv, rval, EVERY);
01764 }
01765 #endif
01766 
01767 static JSFunctionSpec array_methods[] = {
01768 #if JS_HAS_TOSOURCE
01769     {js_toSource_str,       array_toSource,         0,0,0},
01770 #endif
01771     {js_toString_str,       array_toString,         0,0,0},
01772     {js_toLocaleString_str, array_toLocaleString,   0,0,0},
01773 
01774     /* Perl-ish methods. */
01775     {"join",                array_join,             1,JSFUN_GENERIC_NATIVE,0},
01776     {"reverse",             array_reverse,          0,JSFUN_GENERIC_NATIVE,2},
01777     {"sort",                array_sort,             1,JSFUN_GENERIC_NATIVE,2},
01778     {"push",                array_push,             1,JSFUN_GENERIC_NATIVE,0},
01779     {"pop",                 array_pop,              0,JSFUN_GENERIC_NATIVE,0},
01780     {"shift",               array_shift,            0,JSFUN_GENERIC_NATIVE,1},
01781     {"unshift",             array_unshift,          1,JSFUN_GENERIC_NATIVE,1},
01782     {"splice",              array_splice,           2,JSFUN_GENERIC_NATIVE,1},
01783 
01784     /* Python-esque sequence methods. */
01785     {"concat",              array_concat,           1,JSFUN_GENERIC_NATIVE,1},
01786     {"slice",               array_slice,            2,JSFUN_GENERIC_NATIVE,1},
01787 
01788 #if JS_HAS_ARRAY_EXTRAS
01789     {"indexOf",             array_indexOf,          1,JSFUN_GENERIC_NATIVE,0},
01790     {"lastIndexOf",         array_lastIndexOf,      1,JSFUN_GENERIC_NATIVE,0},
01791     {"forEach",             array_forEach,          1,JSFUN_GENERIC_NATIVE,2},
01792     {"map",                 array_map,              1,JSFUN_GENERIC_NATIVE,2},
01793     {"filter",              array_filter,           1,JSFUN_GENERIC_NATIVE,2},
01794     {"some",                array_some,             1,JSFUN_GENERIC_NATIVE,2},
01795     {"every",               array_every,            1,JSFUN_GENERIC_NATIVE,2},
01796 #endif
01797 
01798     {0,0,0,0,0}
01799 };
01800 
01801 static JSBool
01802 Array(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
01803 {
01804     jsuint length;
01805     jsval *vector;
01806 
01807     /* If called without new, replace obj with a new Array object. */
01808     if (!(cx->fp->flags & JSFRAME_CONSTRUCTING)) {
01809         obj = js_NewObject(cx, &js_ArrayClass, NULL, NULL);
01810         if (!obj)
01811             return JS_FALSE;
01812         *rval = OBJECT_TO_JSVAL(obj);
01813     }
01814 
01815     if (argc == 0) {
01816         length = 0;
01817         vector = NULL;
01818     } else if (argc > 1) {
01819         length = (jsuint) argc;
01820         vector = argv;
01821     } else if (!JSVAL_IS_NUMBER(argv[0])) {
01822         length = 1;
01823         vector = argv;
01824     } else {
01825         if (!ValueIsLength(cx, argv[0], &length))
01826             return JS_FALSE;
01827         vector = NULL;
01828     }
01829     return InitArrayObject(cx, obj, length, vector);
01830 }
01831 
01832 JSObject *
01833 js_InitArrayClass(JSContext *cx, JSObject *obj)
01834 {
01835     JSObject *proto;
01836 
01837     proto = JS_InitClass(cx, obj, NULL, &js_ArrayClass, Array, 1,
01838                          NULL, array_methods, NULL, NULL);
01839 
01840     /* Initialize the Array prototype object so it gets a length property. */
01841     if (!proto || !InitArrayObject(cx, proto, 0, NULL))
01842         return NULL;
01843     return proto;
01844 }
01845 
01846 JSObject *
01847 js_NewArrayObject(JSContext *cx, jsuint length, jsval *vector)
01848 {
01849     JSTempValueRooter tvr;
01850     JSObject *obj;
01851 
01852     obj = js_NewObject(cx, &js_ArrayClass, NULL, NULL);
01853     if (!obj)
01854         return NULL;
01855 
01856     JS_PUSH_TEMP_ROOT_OBJECT(cx, obj, &tvr);
01857     if (!InitArrayObject(cx, obj, length, vector))
01858         obj = NULL;
01859     JS_POP_TEMP_ROOT(cx, &tvr);
01860 
01861     /* Set/clear newborn root, in case we lost it.  */
01862     cx->weakRoots.newborn[GCX_OBJECT] = (JSGCThing *) obj;
01863     return obj;
01864 }