1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2  *
3  * ***** BEGIN LICENSE BLOCK *****
4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5  *
6  * The contents of this file are subject to the Mozilla Public License Version
7  * 1.1 (the "License"); you may not use this file except in compliance with
8  * the License. You may obtain a copy of the License at
9  * http://www.mozilla.org/MPL/
10  *
11  * Software distributed under the License is distributed on an "AS IS" basis,
12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13  * for the specific language governing rights and limitations under the
14  * License.
15  *
16  * The Original Code is Mozilla Communicator client code, released
17  * March 31, 1998.
18  *
19  * The Initial Developer of the Original Code is
20  * Netscape Communications Corporation.
21  * Portions created by the Initial Developer are Copyright (C) 1998
22  * the Initial Developer. All Rights Reserved.
23  *
24  * Contributor(s):
25  *
26  * Alternatively, the contents of this file may be used under the terms of
27  * either of the GNU General Public License Version 2 or later (the "GPL"),
28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29  * in which case the provisions of the GPL or the LGPL are applicable instead
30  * of those above. If you wish to allow use of your version of this file only
31  * under the terms of either the GPL or the LGPL, and not to allow others to
32  * use your version of this file under the terms of the MPL, indicate your
33  * decision by deleting the provisions above and replace them with the notice
34  * and other provisions required by the GPL or the LGPL. If you do not delete
35  * the provisions above, a recipient may use your version of this file under
36  * the terms of any one of the MPL, the GPL or the LGPL.
37  *
38  * ***** END LICENSE BLOCK ***** */
39 
40 /*
41  * JS array class.
42  */
43 #include "jsstddef.h"
44 #include <stdlib.h>
45 #include <string.h>
46 #include "jstypes.h"
47 #include "jsutil.h" /* Added by JSIFY */
48 #include "jsapi.h"
49 #include "jsarray.h"
50 #include "jsatom.h"
51 #include "jscntxt.h"
52 #include "jsconfig.h"
53 #include "jsfun.h"
54 #include "jsgc.h"
55 #include "jsinterp.h"
56 #include "jslock.h"
57 #include "jsnum.h"
58 #include "jsobj.h"
59 #include "jsstr.h"
60 
61 /* 2^32 - 1 as a number and a string */
62 #define MAXINDEX 4294967295u
63 #define MAXSTR   "4294967295"
64 
65 /*
66  * Determine if the id represents an array index.
67  *
68  * An id is an array index according to ECMA by (15.4):
69  *
70  * "Array objects give special treatment to a certain class of property names.
71  * A property name P (in the form of a string value) is an array index if and
72  * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
73  * to 2^32-1."
74  *
75  * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
76  * except that by using signed 32-bit integers we miss the top half of the
77  * valid range. This function checks the string representation itself; note
78  * that calling a standard conversion routine might allow strings such as
79  * "08" or "4.0" as array indices, which they are not.
80  */
81 static JSBool
IdIsIndex(jsid id,jsuint * indexp)82 IdIsIndex(jsid id, jsuint *indexp)
83 {
84     JSString *str;
85     jschar *cp;
86 
87     if (JSVAL_IS_INT(id)) {
88         jsint i;
89         i = JSVAL_TO_INT(id);
90         if (i < 0)
91             return JS_FALSE;
92         *indexp = (jsuint)i;
93         return JS_TRUE;
94     }
95 
96     /* It must be a string. */
97     str = JSVAL_TO_STRING(id);
98     cp = JSSTRING_CHARS(str);
99     if (JS7_ISDEC(*cp) && JSSTRING_LENGTH(str) < sizeof(MAXSTR)) {
100         jsuint index = JS7_UNDEC(*cp++);
101         jsuint oldIndex = 0;
102         jsuint c = 0;
103         if (index != 0) {
104             while (JS7_ISDEC(*cp)) {
105                 oldIndex = index;
106                 c = JS7_UNDEC(*cp);
107                 index = 10*index + c;
108                 cp++;
109             }
110         }
111         /* Make sure all characters were consumed and that it couldn't
112          * have overflowed.
113          */
114         if (*cp == 0 &&
115              (oldIndex < (MAXINDEX / 10) ||
116               (oldIndex == (MAXINDEX / 10) && c < (MAXINDEX % 10))))
117         {
118             *indexp = index;
119             return JS_TRUE;
120         }
121     }
122     return JS_FALSE;
123 }
124 
125 static JSBool
ValueIsLength(JSContext * cx,jsval v,jsuint * lengthp)126 ValueIsLength(JSContext *cx, jsval v, jsuint *lengthp)
127 {
128     jsint i;
129     jsdouble d;
130 
131     if (JSVAL_IS_INT(v)) {
132         i = JSVAL_TO_INT(v);
133         if (i < 0) {
134             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
135                                  JSMSG_BAD_ARRAY_LENGTH);
136             return JS_FALSE;
137         }
138         *lengthp = (jsuint) i;
139         return JS_TRUE;
140     }
141 
142     if (!js_ValueToNumber(cx, v, &d)) {
143         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
144                              JSMSG_BAD_ARRAY_LENGTH);
145         return JS_FALSE;
146     }
147     if (!js_DoubleToECMAUint32(cx, d, (uint32 *)lengthp)) {
148         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
149                              JSMSG_BAD_ARRAY_LENGTH);
150         return JS_FALSE;
151     }
152     if (JSDOUBLE_IS_NaN(d) || d != *lengthp) {
153         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
154                              JSMSG_BAD_ARRAY_LENGTH);
155         return JS_FALSE;
156     }
157     return JS_TRUE;
158 }
159 
160 JSBool
js_GetLengthProperty(JSContext * cx,JSObject * obj,jsuint * lengthp)161 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
162 {
163     jsid id;
164     jsint i;
165     jsval v;
166 
167     id = (jsid) cx->runtime->atomState.lengthAtom;
168     if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
169         return JS_FALSE;
170 
171     /* Short-circuit, because js_ValueToECMAUint32 fails when
172      * called during init time.
173      */
174     if (JSVAL_IS_INT(v)) {
175         i = JSVAL_TO_INT(v);
176         /* jsuint cast does ToUint32. */
177         *lengthp = (jsuint)i;
178         return JS_TRUE;
179     }
180     return js_ValueToECMAUint32(cx, v, (uint32 *)lengthp);
181 }
182 
183 static JSBool
IndexToValue(JSContext * cx,jsuint length,jsval * vp)184 IndexToValue(JSContext *cx, jsuint length, jsval *vp)
185 {
186     if (length <= JSVAL_INT_MAX) {
187         *vp = INT_TO_JSVAL(length);
188         return JS_TRUE;
189     }
190     return js_NewDoubleValue(cx, (jsdouble)length, vp);
191 }
192 
193 static JSBool
IndexToId(JSContext * cx,jsuint length,jsid * idp)194 IndexToId(JSContext *cx, jsuint length, jsid *idp)
195 {
196     JSString *str;
197     JSAtom *atom;
198 
199     if (length <= JSVAL_INT_MAX) {
200         *idp = (jsid) INT_TO_JSVAL(length);
201     } else {
202         str = js_NumberToString(cx, (jsdouble)length);
203         if (!str)
204             return JS_FALSE;
205         atom = js_AtomizeString(cx, str, 0);
206         if (!atom)
207             return JS_FALSE;
208         *idp = (jsid)atom;
209 
210     }
211     return JS_TRUE;
212 }
213 
214 JSBool
js_SetLengthProperty(JSContext * cx,JSObject * obj,jsuint length)215 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsuint length)
216 {
217     jsval v;
218     jsid id;
219 
220     if (!IndexToValue(cx, length, &v))
221         return JS_FALSE;
222     id = (jsid) cx->runtime->atomState.lengthAtom;
223     return OBJ_SET_PROPERTY(cx, obj, id, &v);
224 }
225 
226 JSBool
js_HasLengthProperty(JSContext * cx,JSObject * obj,jsuint * lengthp)227 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
228 {
229     JSErrorReporter older;
230     jsid id;
231     JSBool ok;
232     jsval v;
233 
234     older = JS_SetErrorReporter(cx, NULL);
235     id = (jsid) cx->runtime->atomState.lengthAtom;
236     ok = OBJ_GET_PROPERTY(cx, obj, id, &v);
237     JS_SetErrorReporter(cx, older);
238     if (!ok)
239         return JS_FALSE;
240     return ValueIsLength(cx, v, lengthp);
241 }
242 
243 /*
244  * This get function is specific to Array.prototype.length and other array
245  * instance length properties.  It calls back through the class get function
246  * in case some magic happens there (see call_getProperty in jsfun.c).
247  */
248 static JSBool
array_length_getter(JSContext * cx,JSObject * obj,jsval id,jsval * vp)249 array_length_getter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
250 {
251     return OBJ_GET_CLASS(cx, obj)->getProperty(cx, obj, id, vp);
252 }
253 
254 static JSBool
array_length_setter(JSContext * cx,JSObject * obj,jsval id,jsval * vp)255 array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
256 {
257     jsuint newlen, oldlen, slot;
258     jsid id2;
259     jsval junk;
260 
261     if (!ValueIsLength(cx, *vp, &newlen))
262         return JS_FALSE;
263     if (!js_GetLengthProperty(cx, obj, &oldlen))
264         return JS_FALSE;
265     slot = oldlen;
266     while (slot > newlen) {
267         --slot;
268         if (!IndexToId(cx, slot, &id2))
269             return JS_FALSE;
270         if (!OBJ_DELETE_PROPERTY(cx, obj, id2, &junk))
271             return JS_FALSE;
272     }
273     return IndexToValue(cx, newlen, vp);
274 }
275 
276 static JSBool
array_addProperty(JSContext * cx,JSObject * obj,jsval id,jsval * vp)277 array_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
278 {
279     jsuint index, length;
280 
281     if (!(IdIsIndex(id, &index)))
282         return JS_TRUE;
283     if (!js_GetLengthProperty(cx, obj, &length))
284         return JS_FALSE;
285     if (index >= length) {
286         length = index + 1;
287         return js_SetLengthProperty(cx, obj, length);
288     }
289     return JS_TRUE;
290 }
291 
292 static JSBool
array_convert(JSContext * cx,JSObject * obj,JSType type,jsval * vp)293 array_convert(JSContext *cx, JSObject *obj, JSType type, jsval *vp)
294 {
295     jsuint length;
296 
297     if (cx->version == JSVERSION_1_2) {
298         if (!js_GetLengthProperty(cx, obj, &length))
299             return JS_FALSE;
300         switch (type) {
301           case JSTYPE_NUMBER:
302             return IndexToValue(cx, length, vp);
303           case JSTYPE_BOOLEAN:
304             *vp = BOOLEAN_TO_JSVAL(length > 0);
305             return JS_TRUE;
306           default:
307             return JS_TRUE;
308         }
309     }
310     return js_TryValueOf(cx, obj, type, vp);
311 }
312 
313 JSClass js_ArrayClass = {
314     "Array",
315     0,
316     array_addProperty, JS_PropertyStub,   JS_PropertyStub,   JS_PropertyStub,
317     JS_EnumerateStub,  JS_ResolveStub,    array_convert,     JS_FinalizeStub,
318     JSCLASS_NO_OPTIONAL_MEMBERS
319 };
320 
321 static JSBool
array_join_sub(JSContext * cx,JSObject * obj,JSString * sep,JSBool literalize,jsval * rval,JSBool localeString)322 array_join_sub(JSContext *cx, JSObject *obj, JSString *sep, JSBool literalize,
323                jsval *rval, JSBool localeString)
324 {
325     JSBool ok;
326     jsval v;
327     jsuint length, index;
328     jschar *chars, *ochars;
329     size_t nchars, growth, seplen, tmplen;
330     const jschar *sepstr;
331     JSString *str;
332     JSHashEntry *he;
333     JSObject *obj2;
334 
335     ok = js_GetLengthProperty(cx, obj, &length);
336     if (!ok)
337         return JS_FALSE;
338 
339     he = js_EnterSharpObject(cx, obj, NULL, &chars);
340     if (!he)
341         return JS_FALSE;
342     if (literalize) {
343         if (IS_SHARP(he)) {
344 #if JS_HAS_SHARP_VARS
345             nchars = js_strlen(chars);
346 #else
347             chars[0] = '[';
348             chars[1] = ']';
349             chars[2] = 0;
350             nchars = 2;
351 #endif
352             goto make_string;
353         }
354 
355         /*
356          * Allocate 1 + 3 + 1 for "[", the worst-case closing ", ]", and the
357          * terminating 0.
358          */
359         growth = (1 + 3 + 1) * sizeof(jschar);
360         if (!chars) {
361             nchars = 0;
362             chars = (jschar *) malloc(growth);
363             if (!chars)
364                 goto done;
365         } else {
366             MAKE_SHARP(he);
367             nchars = js_strlen(chars);
368             chars = (jschar *)
369                 realloc((ochars = chars), nchars * sizeof(jschar) + growth);
370             if (!chars) {
371                 free(ochars);
372                 goto done;
373             }
374         }
375         chars[nchars++] = '[';
376     } else {
377         /*
378          * Free any sharp variable definition in chars.  Normally, we would
379          * MAKE_SHARP(he) so that only the first sharp variable annotation is
380          * a definition, and all the rest are references, but in the current
381          * case of (!literalize), we don't need chars at all.
382          */
383         if (chars)
384             JS_free(cx, chars);
385         chars = NULL;
386         nchars = 0;
387 
388         /* Return the empty string on a cycle as well as on empty join. */
389         if (IS_BUSY(he) || length == 0) {
390             js_LeaveSharpObject(cx, NULL);
391             *rval = JS_GetEmptyStringValue(cx);
392             return ok;
393         }
394 
395         /* Flag he as BUSY so we can distinguish a cycle from a join-point. */
396         MAKE_BUSY(he);
397     }
398     sepstr = NULL;
399     seplen = JSSTRING_LENGTH(sep);
400 
401     v = JSVAL_NULL;
402     for (index = 0; index < length; index++) {
403         ok = JS_GetElement(cx, obj, index, &v);
404         if (!ok)
405             goto done;
406 
407         if (!literalize && (JSVAL_IS_VOID(v) || JSVAL_IS_NULL(v))) {
408             str = cx->runtime->emptyString;
409         } else {
410             if (localeString) {
411                 if (!js_ValueToObject(cx, v, &obj2) ||
412                     !js_TryMethod(cx, obj2,
413                                   cx->runtime->atomState.toLocaleStringAtom,
414                                   0, NULL, &v)) {
415                     str = NULL;
416                 } else {
417                     str = js_ValueToString(cx, v);
418                 }
419             } else {
420                 str = (literalize ? js_ValueToSource : js_ValueToString)(cx, v);
421             }
422             if (!str) {
423                 ok = JS_FALSE;
424                 goto done;
425             }
426         }
427 
428         /* Allocate 3 + 1 at end for ", ", closing bracket, and zero. */
429         growth = (nchars + (sepstr ? seplen : 0) +
430                   JSSTRING_LENGTH(str) +
431                   3 + 1) * sizeof(jschar);
432         if (!chars) {
433             chars = (jschar *) malloc(growth);
434             if (!chars)
435                 goto done;
436         } else {
437             chars = (jschar *) realloc((ochars = chars), growth);
438             if (!chars) {
439                 free(ochars);
440                 goto done;
441             }
442         }
443 
444         if (sepstr) {
445             js_strncpy(&chars[nchars], sepstr, seplen);
446             nchars += seplen;
447         }
448         sepstr = JSSTRING_CHARS(sep);
449 
450         tmplen = JSSTRING_LENGTH(str);
451         js_strncpy(&chars[nchars], JSSTRING_CHARS(str), tmplen);
452         nchars += tmplen;
453     }
454 
455   done:
456     if (literalize) {
457         if (chars) {
458             if (JSVAL_IS_VOID(v)) {
459                 chars[nchars++] = ',';
460                 chars[nchars++] = ' ';
461             }
462             chars[nchars++] = ']';
463         }
464     } else {
465         CLEAR_BUSY(he);
466     }
467     js_LeaveSharpObject(cx, NULL);
468     if (!ok) {
469         if (chars)
470             free(chars);
471         return ok;
472     }
473 
474   make_string:
475     if (!chars) {
476         JS_ReportOutOfMemory(cx);
477         return JS_FALSE;
478     }
479     chars[nchars] = 0;
480     str = js_NewString(cx, chars, nchars, 0);
481     if (!str) {
482         free(chars);
483         return JS_FALSE;
484     }
485     *rval = STRING_TO_JSVAL(str);
486     return JS_TRUE;
487 }
488 
489 static jschar   comma_space_ucstr[] = {',', ' ', 0};
490 static jschar   comma_ucstr[]       = {',', 0};
491 static JSString comma_space         = {2, comma_space_ucstr};
492 static JSString comma               = {1, comma_ucstr};
493 
494 #if JS_HAS_TOSOURCE
495 static JSBool
array_toSource(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)496 array_toSource(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
497                jsval *rval)
498 {
499     return array_join_sub(cx, obj, &comma_space, JS_TRUE, rval, JS_FALSE);
500 }
501 #endif
502 
503 static JSBool
array_toString(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)504 array_toString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
505                jsval *rval)
506 {
507     JSBool literalize;
508 
509     /*
510      * JS1.2 arrays convert to array literals, with a comma followed by a space
511      * between each element.
512      */
513     literalize = (cx->version == JSVERSION_1_2);
514     return array_join_sub(cx, obj, literalize ? &comma_space : &comma,
515                           literalize, rval, JS_FALSE);
516 }
517 
518 static JSBool
array_toLocaleString(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)519 array_toLocaleString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
520                jsval *rval)
521 {
522     /*
523      *  Passing comma here as the separator. Need a way to get a
524      *  locale-specific version.
525      */
526     return array_join_sub(cx, obj, &comma, JS_FALSE, rval, JS_TRUE);
527 }
528 
529 static JSBool
InitArrayElements(JSContext * cx,JSObject * obj,jsuint length,jsval * vector)530 InitArrayElements(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
531 {
532     jsuint index;
533     jsid id;
534 
535     for (index = 0; index < length; index++) {
536         if (!IndexToId(cx, index, &id))
537             return JS_FALSE;
538         if (!OBJ_SET_PROPERTY(cx, obj, id, &vector[index]))
539             return JS_FALSE;
540     }
541     return JS_TRUE;
542 }
543 
544 static JSBool
InitArrayObject(JSContext * cx,JSObject * obj,jsuint length,jsval * vector)545 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
546 {
547     jsval v;
548     jsid id;
549 
550     if (!IndexToValue(cx, length, &v))
551         return JS_FALSE;
552     id = (jsid) cx->runtime->atomState.lengthAtom;
553     if (!OBJ_DEFINE_PROPERTY(cx, obj, id, v,
554                              array_length_getter, array_length_setter,
555                              JSPROP_PERMANENT,
556                              NULL)) {
557           return JS_FALSE;
558     }
559     if (!vector)
560         return JS_TRUE;
561     return InitArrayElements(cx, obj, length, vector);
562 }
563 
564 #if JS_HAS_SOME_PERL_FUN
565 /*
566  * Perl-inspired join, reverse, and sort.
567  */
568 static JSBool
array_join(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)569 array_join(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
570 {
571     JSString *str;
572 
573     if (JSVAL_IS_VOID(argv[0]))
574         return array_join_sub(cx, obj, &comma, JS_FALSE, rval, JS_FALSE);
575     str = js_ValueToString(cx, argv[0]);
576     if (!str)
577         return JS_FALSE;
578     argv[0] = STRING_TO_JSVAL(str);
579     return array_join_sub(cx, obj, str, JS_FALSE, rval, JS_FALSE);
580 }
581 
582 static JSBool
array_reverse(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)583 array_reverse(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
584               jsval *rval)
585 {
586     jsuint len, half, i;
587     jsid id, id2;
588     jsval v, v2;
589 
590     if (!js_GetLengthProperty(cx, obj, &len))
591         return JS_FALSE;
592 
593     half = len / 2;
594     for (i = 0; i < half; i++) {
595         if (!IndexToId(cx, i, &id))
596             return JS_FALSE;
597         if (!IndexToId(cx, len - i - 1, &id2))
598             return JS_FALSE;
599         if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
600             return JS_FALSE;
601         if (!OBJ_GET_PROPERTY(cx, obj, id2, &v2))
602             return JS_FALSE;
603 
604 #if JS_HAS_SPARSE_ARRAYS
605         /* This part isn't done yet. */
606 
607         if (!OBJ_LOOKUP_PROPERTY(cx, obj, id, &obj2, &prop))
608             return JS_FALSE;
609         if (!prop) {
610             OBJ_DELETE_PROPERTY(cx, obj, id2, &v); /* v is junk. */
611             continue;
612         }
613         OBJ_DROP_PROPERTY(cx, obj2, prop);
614 #endif
615 
616         if (!OBJ_SET_PROPERTY(cx, obj, id, &v2))
617             return JS_FALSE;
618         if (!OBJ_SET_PROPERTY(cx, obj, id2, &v))
619             return JS_FALSE;
620     }
621 
622     *rval = OBJECT_TO_JSVAL(obj);
623     return JS_TRUE;
624 }
625 
626 typedef struct HSortArgs {
627     void         *vec;
628     size_t       elsize;
629     void         *pivot;
630     JSComparator cmp;
631     void         *arg;
632     JSBool       fastcopy;
633 } HSortArgs;
634 
635 static int
636 sort_compare(const void *a, const void *b, void *arg);
637 
638 static int
639 sort_compare_strings(const void *a, const void *b, void *arg);
640 
641 static void
HeapSortHelper(JSBool building,HSortArgs * hsa,size_t lo,size_t hi)642 HeapSortHelper(JSBool building, HSortArgs *hsa, size_t lo, size_t hi)
643 {
644     void *pivot, *vec, *vec2, *arg, *a, *b;
645     size_t elsize;
646     JSComparator cmp;
647     JSBool fastcopy;
648     size_t j, hiDiv2;
649 
650     pivot = hsa->pivot;
651     vec = hsa->vec;
652     elsize = hsa->elsize;
653     vec2 =  (char *)vec - 2 * elsize;
654     cmp = hsa->cmp;
655     arg = hsa->arg;
656 
657     fastcopy = hsa->fastcopy;
658 #define MEMCPY(p,q,n) \
659     (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
660 
661     if (lo == 1) {
662         j = 2;
663         b = (char *)vec + elsize;
664         if (j < hi && cmp(vec, b, arg) < 0)
665             j++;
666         a = (char *)vec + (hi - 1) * elsize;
667         b = (char *)vec2 + j * elsize;
668 
669         /*
670          * During sorting phase b points to a member of heap that cannot be
671          * bigger then biggest of vec[0] and vec[1], and cmp(a, b, arg) <= 0
672          * always holds.
673          */
674         if ((building || hi == 2) && cmp(a, b, arg) >= 0)
675             return;
676 
677         MEMCPY(pivot, a, elsize);
678         MEMCPY(a, b, elsize);
679         lo = j;
680     } else {
681         a = (char *)vec2 + lo * elsize;
682         MEMCPY(pivot, a, elsize);
683     }
684 
685     hiDiv2 = hi/2;
686     while (lo <= hiDiv2) {
687         j = lo + lo;
688         a = (char *)vec2 + j * elsize;
689         b = (char *)vec + (j - 1) * elsize;
690         if (j < hi && cmp(a, b, arg) < 0)
691             j++;
692         b = (char *)vec2 + j * elsize;
693         if (cmp(pivot, b, arg) >= 0)
694             break;
695 
696         a = (char *)vec2 + lo * elsize;
697         MEMCPY(a, b, elsize);
698         lo = j;
699     }
700 
701     a = (char *)vec2 + lo * elsize;
702     MEMCPY(a, pivot, elsize);
703 #undef MEMCPY
704 }
705 
706 JSBool
js_HeapSort(void * vec,size_t nel,size_t elsize,JSComparator cmp,void * arg)707 js_HeapSort(void *vec, size_t nel, size_t elsize, JSComparator cmp, void *arg)
708 {
709     void *pivot;
710     HSortArgs hsa;
711     size_t i;
712 
713     pivot = malloc(elsize);
714     if (!pivot)
715         return JS_FALSE;
716     hsa.vec = vec;
717     hsa.elsize = elsize;
718     hsa.pivot = pivot;
719     hsa.cmp = cmp;
720     hsa.arg = arg;
721     hsa.fastcopy = (cmp == sort_compare || cmp == sort_compare_strings);
722 
723     for (i = nel/2; i != 0; i--)
724         HeapSortHelper(JS_TRUE, &hsa, i, nel);
725     while (nel > 2)
726         HeapSortHelper(JS_FALSE, &hsa, 1, --nel);
727 
728     free(pivot);
729     return JS_TRUE;
730 }
731 
732 typedef struct CompareArgs {
733     JSContext  *context;
734     jsval      fval;
735     JSBool     status;
736 } CompareArgs;
737 
738 static int
sort_compare(const void * a,const void * b,void * arg)739 sort_compare(const void *a, const void *b, void *arg)
740 {
741     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
742     CompareArgs *ca = (CompareArgs *) arg;
743     JSContext *cx = ca->context;
744     jsdouble cmp = -1;
745     jsval fval, argv[2], rval;
746     JSBool ok;
747 
748     fval = ca->fval;
749     if (fval == JSVAL_NULL) {
750         JSString *astr, *bstr;
751 
752         if (av == bv) {
753             cmp = 0;
754         } else if (av == JSVAL_VOID || bv == JSVAL_VOID) {
755             /* Put undefined properties at the end. */
756             cmp = (av == JSVAL_VOID) ? 1 : -1;
757         } else if ((astr = js_ValueToString(cx, av)) != NULL &&
758                    (bstr = js_ValueToString(cx, bv)) != NULL) {
759             cmp = js_CompareStrings(astr, bstr);
760         } else {
761             ca->status = JS_FALSE;
762         }
763     } else {
764         argv[0] = av;
765         argv[1] = bv;
766         ok = js_InternalCall(cx,
767                              OBJ_GET_PARENT(cx, JSVAL_TO_OBJECT(fval)),
768                              fval, 2, argv, &rval);
769         if (ok) {
770             ok = js_ValueToNumber(cx, rval, &cmp);
771             /* Clamp cmp to -1, 0, 1. */
772             if (JSDOUBLE_IS_NaN(cmp)) {
773                 /* XXX report some kind of error here?  ECMA talks about
774                  * 'consistent compare functions' that don't return NaN, but is
775                  * silent about what the result should be.  So we currently
776                  * ignore it.
777                  */
778                 cmp = 0;
779             } else if (cmp != 0) {
780                 cmp = cmp > 0 ? 1 : -1;
781             }
782         } else {
783             ca->status = ok;
784         }
785     }
786     return (int)cmp;
787 }
788 
789 static int
sort_compare_strings(const void * a,const void * b,void * arg)790 sort_compare_strings(const void *a, const void *b, void *arg)
791 {
792     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
793 
794     return (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
795 }
796 
797 /* XXXmccabe do the sort helper functions need to take int?  (Or can we claim
798  * that 2^32 * 32 is too large to worry about?)  Something dumps when I change
799  * to unsigned int; is qsort using -1 as a fencepost?
800  */
801 static JSBool
array_sort(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)802 array_sort(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
803 {
804     jsval fval;
805     CompareArgs ca;
806     jsuint len, newlen, i;
807     jsval *vec;
808     jsid id;
809     size_t nbytes;
810 
811     /*
812      * Optimize the default compare function case if all of obj's elements
813      * have values of type string.
814      */
815     JSBool all_strings;
816 
817     if (argc > 0) {
818         if (JSVAL_IS_PRIMITIVE(argv[0])) {
819             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
820                                  JSMSG_BAD_SORT_ARG);
821             return JS_FALSE;
822         }
823         fval = argv[0];
824         all_strings = JS_FALSE; /* non-default compare function */
825     } else {
826         fval = JSVAL_NULL;
827         all_strings = JS_TRUE;  /* check for all string values */
828     }
829 
830     if (!js_GetLengthProperty(cx, obj, &len))
831         return JS_FALSE;
832     if (len == 0) {
833         *rval = OBJECT_TO_JSVAL(obj);
834         return JS_TRUE;
835     }
836 
837     /*
838      * Test for size_t overflow, which could lead to indexing beyond the end
839      * of the malloc'd vector.
840      */
841     nbytes = len * sizeof(jsval);
842     if (nbytes != (double) len * sizeof(jsval)) {
843         JS_ReportOutOfMemory(cx);
844         return JS_FALSE;
845     }
846     vec = (jsval *) JS_malloc(cx, nbytes);
847     if (!vec)
848         return JS_FALSE;
849 
850 #if JS_HAS_SPARSE_ARRAYS
851     newlen = 0;
852 #else
853     newlen = len;
854 #endif
855 
856     for (i = 0; i < len; i++) {
857         ca.status = IndexToId(cx, i, &id);
858         if (!ca.status)
859             goto out;
860 #if JS_HAS_SPARSE_ARRAYS
861         {
862             JSObject *obj2;
863             JSProperty *prop;
864             ca.status = OBJ_LOOKUP_PROPERTY(cx, obj, id, &obj2, &prop);
865             if (!ca.status)
866                 goto out;
867             if (!prop) {
868                 vec[i] = JSVAL_VOID;
869                 continue;
870             }
871             OBJ_DROP_PROPERTY(cx, obj2, prop);
872             newlen++;
873         }
874 #endif
875         ca.status = OBJ_GET_PROPERTY(cx, obj, id, &vec[i]);
876         if (!ca.status)
877             goto out;
878 
879         /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
880         all_strings &= JSVAL_IS_STRING(vec[i]);
881     }
882 
883     ca.context = cx;
884     ca.fval = fval;
885     ca.status = JS_TRUE;
886     if (!js_HeapSort(vec, (size_t) len, sizeof(jsval),
887                      all_strings ? sort_compare_strings : sort_compare,
888                      &ca)) {
889         JS_ReportOutOfMemory(cx);
890         ca.status = JS_FALSE;
891     }
892 
893     if (ca.status) {
894         ca.status = InitArrayElements(cx, obj, newlen, vec);
895         if (ca.status)
896             *rval = OBJECT_TO_JSVAL(obj);
897 #if JS_HAS_SPARSE_ARRAYS
898         /* set length of newly-created array object to old length. */
899         if (ca.status && newlen < len) {
900             ca.status = js_SetLengthProperty(cx, obj, len);
901 
902             /* Delete any leftover properties greater than newlen. */
903             while (ca.status && newlen < len) {
904                 jsval junk;
905 
906                 ca.status = !IndexToId(cx, newlen, &id) ||
907                     !OBJ_DELETE_PROPERTY(cx, obj, id, &junk);
908                 newlen++;
909             }
910         }
911 #endif
912     }
913 
914 out:
915     if (vec)
916         JS_free(cx, vec);
917     return ca.status;
918 }
919 #endif /* JS_HAS_SOME_PERL_FUN */
920 
921 #if JS_HAS_MORE_PERL_FUN
922 /*
923  * Perl-inspired push, pop, shift, unshift, and splice methods.
924  */
925 static JSBool
array_push(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)926 array_push(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
927 {
928     jsuint length;
929     uintN i;
930     jsid id;
931 
932     if (!js_GetLengthProperty(cx, obj, &length))
933         return JS_FALSE;
934     for (i = 0; i < argc; i++) {
935         if (!IndexToId(cx, length + i, &id))
936             return JS_FALSE;
937         if (!OBJ_SET_PROPERTY(cx, obj, id, &argv[i]))
938             return JS_FALSE;
939     }
940 
941     /*
942      * If JS1.2, follow Perl4 by returning the last thing pushed.  Otherwise,
943      * return the new array length.
944      */
945     length += argc;
946     if (cx->version == JSVERSION_1_2) {
947         *rval = argc ? argv[argc-1] : JSVAL_VOID;
948     } else {
949         if (!IndexToValue(cx, length, rval))
950             return JS_FALSE;
951     }
952     return js_SetLengthProperty(cx, obj, length);
953 }
954 
955 static JSBool
array_pop(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)956 array_pop(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
957 {
958     jsuint index;
959     jsid id;
960     jsval junk;
961 
962     if (!js_GetLengthProperty(cx, obj, &index))
963         return JS_FALSE;
964     if (index > 0) {
965         index--;
966         if (!IndexToId(cx, index, &id))
967             return JS_FALSE;
968 
969         /* Get the to-be-deleted property's value into rval. */
970         if (!OBJ_GET_PROPERTY(cx, obj, id, rval))
971             return JS_FALSE;
972 
973         if (!OBJ_DELETE_PROPERTY(cx, obj, id, &junk))
974             return JS_FALSE;
975     }
976     return js_SetLengthProperty(cx, obj, index);
977 }
978 
979 static JSBool
array_shift(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)980 array_shift(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
981 {
982     jsuint length, i;
983     jsid id, id2;
984     jsval v, junk;
985 
986     if (!js_GetLengthProperty(cx, obj, &length))
987         return JS_FALSE;
988     if (length > 0) {
989         length--;
990         id = JSVAL_ZERO;
991 
992         /* Get the to-be-deleted property's value into rval ASAP. */
993         if (!OBJ_GET_PROPERTY(cx, obj, id, rval))
994             return JS_FALSE;
995 
996         /*
997          * Slide down the array above the first element.
998          */
999         if (length > 0) {
1000             for (i = 1; i <= length; i++) {
1001                 if (!IndexToId(cx, i, &id))
1002                     return JS_FALSE;
1003                 if (!IndexToId(cx, i - 1, &id2))
1004                     return JS_FALSE;
1005                 if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
1006                     return JS_FALSE;
1007                 if (!OBJ_SET_PROPERTY(cx, obj, id2, &v))
1008                     return JS_FALSE;
1009             }
1010         }
1011 
1012         /* Delete the only or last element. */
1013         if (!OBJ_DELETE_PROPERTY(cx, obj, id, &junk))
1014             return JS_FALSE;
1015     }
1016     return js_SetLengthProperty(cx, obj, length);
1017 }
1018 
1019 static JSBool
array_unshift(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)1020 array_unshift(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
1021               jsval *rval)
1022 {
1023     jsuint length, last;
1024     uintN i;
1025     jsid id, id2;
1026     jsval v;
1027 #if JS_HAS_SPARSE_ARRAYS
1028     JSObject *obj2;
1029     JSProperty *prop;
1030 #endif
1031 
1032     if (!js_GetLengthProperty(cx, obj, &length))
1033         return JS_FALSE;
1034     if (argc > 0) {
1035         /* Slide up the array to make room for argc at the bottom. */
1036         if (length > 0) {
1037             last = length;
1038             while (last--) {
1039                 if (!IndexToId(cx, last, &id))
1040                     return JS_FALSE;
1041                 if (!IndexToId(cx, last + argc, &id2))
1042                     return JS_FALSE;
1043 #if JS_HAS_SPARSE_ARRAYS
1044                 if (!OBJ_LOOKUP_PROPERTY(cx, obj, id, &obj2, &prop))
1045                     return JS_FALSE;
1046                 if (!prop) {
1047                     OBJ_DELETE_PROPERTY(cx, obj, id2, &v); /* v is junk. */
1048                     continue;
1049                 }
1050                 OBJ_DROP_PROPERTY(cx, obj2, prop);
1051 #endif
1052                 if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
1053                     return JS_FALSE;
1054                 if (!OBJ_SET_PROPERTY(cx, obj, id2, &v))
1055                     return JS_FALSE;
1056             }
1057         }
1058 
1059         /* Copy from argv to the bottom of the array. */
1060         for (i = 0; i < argc; i++) {
1061             if (!IndexToId(cx, i, &id))
1062                 return JS_FALSE;
1063             if (!OBJ_SET_PROPERTY(cx, obj, id, &argv[i]))
1064                 return JS_FALSE;
1065         }
1066 
1067         /* Follow Perl by returning the new array length. */
1068         length += argc;
1069         if (!js_SetLengthProperty(cx, obj, length))
1070             return JS_FALSE;
1071     }
1072     return IndexToValue(cx, length, rval);
1073 }
1074 
1075 static JSBool
array_splice(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)1076 array_splice(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1077 {
1078     jsuint length, begin, end, count, delta, last;
1079     uintN i;
1080     jsdouble d;
1081     jsid id, id2;
1082     jsval v;
1083     JSObject *obj2;
1084 
1085     /* Nothing to do if no args.  Otherwise lock and load length. */
1086     if (argc == 0)
1087         return JS_TRUE;
1088     if (!js_GetLengthProperty(cx, obj, &length))
1089         return JS_FALSE;
1090 
1091     /* Convert the first argument into a starting index. */
1092     if (!js_ValueToNumber(cx, *argv, &d))
1093         return JS_FALSE;
1094     d = js_DoubleToInteger(d);
1095     if (d < 0) {
1096         d += length;
1097         if (d < 0)
1098             d = 0;
1099     } else if (d > length) {
1100         d = length;
1101     }
1102     begin = (jsuint)d; /* d has been clamped to uint32 */
1103     argc--;
1104     argv++;
1105 
1106     /* Convert the second argument from a count into a fencepost index. */
1107     delta = length - begin;
1108     if (argc == 0) {
1109         count = delta;
1110         end = length;
1111     } else {
1112         if (!js_ValueToNumber(cx, *argv, &d))
1113             return JS_FALSE;
1114         d = js_DoubleToInteger(d);
1115         if (d < 0)
1116             d = 0;
1117         else if (d > delta)
1118             d = delta;
1119         count = (jsuint)d;
1120         end = begin + count;
1121         argc--;
1122         argv++;
1123     }
1124 
1125     if (count == 1 && cx->version == JSVERSION_1_2) {
1126         /*
1127          * JS lacks "list context", whereby in Perl one turns the single
1128          * scalar that's spliced out into an array just by assigning it to
1129          * @single instead of $single, or by using it as Perl push's first
1130          * argument, for instance.
1131          *
1132          * JS1.2 emulated Perl too closely and returned a non-Array for
1133          * the single-splice-out case, requiring callers to test and wrap
1134          * in [] if necessary.  So JS1.3, default, and other versions all
1135          * return an array of length 1 for uniformity.
1136          */
1137         if (!IndexToId(cx, begin, &id))
1138             return JS_FALSE;
1139         if (!OBJ_GET_PROPERTY(cx, obj, id, rval))
1140             return JS_FALSE;
1141     } else {
1142         if (cx->version != JSVERSION_1_2 || count > 0) {
1143             /*
1144              * Create a new array value to return.  Our ECMA v2 proposal specs
1145              * that splice always returns an array value, even when given no
1146              * arguments.  We think this is best because it eliminates the need
1147              * for callers to do an extra test to handle the empty splice case.
1148              */
1149             obj2 = js_NewArrayObject(cx, 0, NULL);
1150             if (!obj2)
1151                 return JS_FALSE;
1152             *rval = OBJECT_TO_JSVAL(obj2);
1153 
1154             /* If there are elements to remove, put them into the return value. */
1155             if (count > 0) {
1156                 for (last = begin; last < end; last++) {
1157                     if (!IndexToId(cx, last, &id))
1158                         return JS_FALSE;
1159                     if (!IndexToId(cx, last - begin, &id2))
1160                         return JS_FALSE;
1161                     if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
1162                         return JS_FALSE;
1163                     if (!OBJ_SET_PROPERTY(cx, obj2, id2, &v))
1164                         return JS_FALSE;
1165                 }
1166             }
1167         }
1168     }
1169 
1170     /* Find the direction (up or down) to copy and make way for argv. */
1171     if (argc > count) {
1172         delta = (jsuint)argc - count;
1173         last = length;
1174         /* (uint) end could be 0, so can't use vanilla >= test */
1175         while (last-- > end) {
1176             if (!IndexToId(cx, last, &id))
1177                 return JS_FALSE;
1178             if (!IndexToId(cx, last + delta, &id2))
1179                 return JS_FALSE;
1180             if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
1181                 return JS_FALSE;
1182             if (!OBJ_SET_PROPERTY(cx, obj, id2, &v))
1183                 return JS_FALSE;
1184         }
1185         length += delta;
1186     } else if (argc < count) {
1187         delta = count - (jsuint)argc;
1188         for (last = end; last < length; last++) {
1189             if (!IndexToId(cx, last, &id))
1190                 return JS_FALSE;
1191             if (!IndexToId(cx, last - delta, &id2))
1192                 return JS_FALSE;
1193             if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
1194                 return JS_FALSE;
1195             if (!OBJ_SET_PROPERTY(cx, obj, id2, &v))
1196                 return JS_FALSE;
1197         }
1198         length -= delta;
1199     }
1200 
1201     /* Copy from argv into the hole to complete the splice. */
1202     for (i = 0; i < argc; i++) {
1203         if (!IndexToId(cx, begin + i, &id))
1204             return JS_FALSE;
1205         if (!OBJ_SET_PROPERTY(cx, obj, id, &argv[i]))
1206             return JS_FALSE;
1207     }
1208 
1209     /* Update length in case we deleted elements from the end. */
1210     return js_SetLengthProperty(cx, obj, length);
1211 }
1212 #endif /* JS_HAS_MORE_PERL_FUN */
1213 
1214 #if JS_HAS_SEQUENCE_OPS
1215 /*
1216  * Python-esque sequence operations.
1217  */
1218 static JSBool
array_concat(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)1219 array_concat(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1220 {
1221     JSObject *nobj, *aobj;
1222     jsuint length, alength, slot;
1223     uintN i;
1224     jsval v;
1225     jsid id, id2;
1226 
1227     /* Treat obj as the first argument; see ECMA 15.4.4.4. */
1228     --argv;
1229     JS_ASSERT(obj == JSVAL_TO_OBJECT(argv[0]));
1230 
1231     /* Create a new Array object and store it in the rval local root. */
1232     nobj = js_NewArrayObject(cx, 0, NULL);
1233     if (!nobj)
1234         return JS_FALSE;
1235     *rval = OBJECT_TO_JSVAL(nobj);
1236 
1237     /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
1238     length = 0;
1239     for (i = 0; i <= argc; i++) {
1240         v = argv[i];
1241         if (JSVAL_IS_OBJECT(v)) {
1242             aobj = JSVAL_TO_OBJECT(v);
1243             if (aobj && OBJ_GET_CLASS(cx, aobj) == &js_ArrayClass) {
1244                 if (!OBJ_GET_PROPERTY(cx, aobj,
1245                                       (jsid)cx->runtime->atomState.lengthAtom,
1246                                       &v)) {
1247                     return JS_FALSE;
1248                 }
1249                 if (!ValueIsLength(cx, v, &alength))
1250                     return JS_FALSE;
1251                 for (slot = 0; slot < alength; slot++) {
1252                     if (!IndexToId(cx, slot, &id))
1253                         return JS_FALSE;
1254                     if (!IndexToId(cx, length + slot, &id2))
1255                         return JS_FALSE;
1256                     if (!OBJ_GET_PROPERTY(cx, aobj, id, &v))
1257                         return JS_FALSE;
1258                     if (!OBJ_SET_PROPERTY(cx, nobj, id2, &v))
1259                         return JS_FALSE;
1260                 }
1261                 length += alength;
1262                 continue;
1263             }
1264         }
1265 
1266         if (!IndexToId(cx, length, &id))
1267             return JS_FALSE;
1268         if (!OBJ_SET_PROPERTY(cx, nobj, id, &v))
1269             return JS_FALSE;
1270         length++;
1271     }
1272 
1273     return JS_TRUE;
1274 }
1275 
1276 static JSBool
array_slice(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)1277 array_slice(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1278 {
1279     JSObject *nobj;
1280     jsuint length, begin, end, slot;
1281     jsdouble d;
1282     jsid id, id2;
1283     jsval v;
1284 
1285     nobj = js_NewArrayObject(cx, 0, NULL);
1286     if (!nobj)
1287         return JS_FALSE;
1288 
1289     if (!js_GetLengthProperty(cx, obj, &length))
1290         return JS_FALSE;
1291     begin = 0;
1292     end = length;
1293 
1294     if (argc > 0) {
1295         if (!js_ValueToNumber(cx, argv[0], &d))
1296             return JS_FALSE;
1297         d = js_DoubleToInteger(d);
1298         if (d < 0) {
1299             d += length;
1300             if (d < 0)
1301                 d = 0;
1302         } else if (d > length) {
1303             d = length;
1304         }
1305         begin = (jsuint)d;
1306 
1307         if (argc > 1) {
1308             if (!js_ValueToNumber(cx, argv[1], &d))
1309                 return JS_FALSE;
1310             d = js_DoubleToInteger(d);
1311             if (d < 0) {
1312                 d += length;
1313                 if (d < 0)
1314                     d = 0;
1315             } else if (d > length) {
1316                 d = length;
1317             }
1318             end = (jsuint)d;
1319         }
1320     }
1321 
1322     for (slot = begin; slot < end; slot++) {
1323         if (!IndexToId(cx, slot, &id))
1324             return JS_FALSE;
1325         if (!IndexToId(cx, slot - begin, &id2))
1326             return JS_FALSE;
1327         if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
1328             return JS_FALSE;
1329         if (!OBJ_SET_PROPERTY(cx, nobj, id2, &v))
1330             return JS_FALSE;
1331     }
1332     *rval = OBJECT_TO_JSVAL(nobj);
1333     return JS_TRUE;
1334 }
1335 #endif /* JS_HAS_SEQUENCE_OPS */
1336 
1337 static JSFunctionSpec array_methods[] = {
1338 #if JS_HAS_TOSOURCE
1339     {js_toSource_str,       array_toSource,         0,0,0},
1340 #endif
1341     {js_toString_str,       array_toString,         0,0,0},
1342     {js_toLocaleString_str, array_toLocaleString,   0,0,0},
1343 
1344     /* Perl-ish methods. */
1345 #if JS_HAS_SOME_PERL_FUN
1346     {"join",                array_join,             1,0,0},
1347     {"reverse",             array_reverse,          0,0,0},
1348     {"sort",                array_sort,             1,0,0},
1349 #endif
1350 #if JS_HAS_MORE_PERL_FUN
1351     {"push",                array_push,             1,0,0},
1352     {"pop",                 array_pop,              0,0,0},
1353     {"shift",               array_shift,            0,0,0},
1354     {"unshift",             array_unshift,          1,0,0},
1355     {"splice",              array_splice,           1,0,0},
1356 #endif
1357 
1358     /* Python-esque sequence methods. */
1359 #if JS_HAS_SEQUENCE_OPS
1360     {"concat",              array_concat,           0,0,0},
1361     {"slice",               array_slice,            0,0,0},
1362 #endif
1363 
1364     {0,0,0,0,0}
1365 };
1366 
1367 static JSBool
Array(JSContext * cx,JSObject * obj,uintN argc,jsval * argv,jsval * rval)1368 Array(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1369 {
1370     jsuint length;
1371     jsval *vector;
1372 
1373     /* If called without new, replace obj with a new Array object. */
1374     if (!(cx->fp->flags & JSFRAME_CONSTRUCTING)) {
1375         obj = js_NewObject(cx, &js_ArrayClass, NULL, NULL);
1376         if (!obj)
1377             return JS_FALSE;
1378         *rval = OBJECT_TO_JSVAL(obj);
1379     }
1380 
1381     if (argc == 0) {
1382         length = 0;
1383         vector = NULL;
1384     } else if (cx->version == JSVERSION_1_2) {
1385         length = (jsuint) argc;
1386         vector = argv;
1387     } else if (argc > 1) {
1388         length = (jsuint) argc;
1389         vector = argv;
1390     } else if (!JSVAL_IS_NUMBER(argv[0])) {
1391         length = 1;
1392         vector = argv;
1393     } else {
1394         if (!ValueIsLength(cx, argv[0], &length))
1395             return JS_FALSE;
1396         vector = NULL;
1397     }
1398     return InitArrayObject(cx, obj, length, vector);
1399 }
1400 
1401 JSObject *
js_InitArrayClass(JSContext * cx,JSObject * obj)1402 js_InitArrayClass(JSContext *cx, JSObject *obj)
1403 {
1404     JSObject *proto;
1405 
1406     proto = JS_InitClass(cx, obj, NULL, &js_ArrayClass, Array, 1,
1407                          NULL, array_methods, NULL, NULL);
1408 
1409     /* Initialize the Array prototype object so it gets a length property. */
1410     if (!proto || !InitArrayObject(cx, proto, 0, NULL))
1411         return NULL;
1412     return proto;
1413 }
1414 
1415 JSObject *
js_NewArrayObject(JSContext * cx,jsuint length,jsval * vector)1416 js_NewArrayObject(JSContext *cx, jsuint length, jsval *vector)
1417 {
1418     JSObject *obj;
1419 
1420     obj = js_NewObject(cx, &js_ArrayClass, NULL, NULL);
1421     if (!obj)
1422         return NULL;
1423     if (!InitArrayObject(cx, obj, length, vector)) {
1424         cx->newborn[GCX_OBJECT] = NULL;
1425         return NULL;
1426     }
1427     return obj;
1428 }
1429