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 ***** */
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"
61 /* 2^32 - 1 as a number and a string */
62 #define MAXINDEX 4294967295u
63 #define MAXSTR "4294967295"
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
82 IdIsIndex(jsid id, jsuint *indexp)
83 {
84 JSString *str;
85 jschar *cp;
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 }
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 }
125 static JSBool
126 ValueIsLength(JSContext *cx, jsval v, jsuint *lengthp)
127 {
128 jsint i;
129 jsdouble d;
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 }
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 }
160 JSBool
161 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
162 {
163 jsid id;
164 jsint i;
165 jsval v;
167 id = (jsid) cx->runtime->atomState.lengthAtom;
168 if (!OBJ_GET_PROPERTY(cx, obj, id, &v))
169 return JS_FALSE;
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 }
183 static JSBool
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 }
193 static JSBool
194 IndexToId(JSContext *cx, jsuint length, jsid *idp)
195 {
196 JSString *str;
197 JSAtom *atom;
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;
210 }
211 return JS_TRUE;
212 }
214 JSBool
215 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsuint length)
216 {
217 jsval v;
218 jsid id;
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 }
226 JSBool
227 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
228 {
229 JSErrorReporter older;
230 jsid id;
231 JSBool ok;
232 jsval v;
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 }
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
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 }
254 static JSBool
255 array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
256 {
257 jsuint newlen, oldlen, slot;
258 jsid id2;
259 jsval junk;
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 }
276 static JSBool
277 array_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
278 {
279 jsuint index, length;
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 }
292 static JSBool
293 array_convert(JSContext *cx, JSObject *obj, JSType type, jsval *vp)
294 {
295 jsuint length;
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 }
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 };
321 static JSBool
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;
335 ok = js_GetLengthProperty(cx, obj, &length);
336 if (!ok)
337 return JS_FALSE;
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 }
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;
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 }
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);
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;
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 }
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 }
444 if (sepstr) {
445 js_strncpy(&chars[nchars], sepstr, seplen);
446 nchars += seplen;
447 }
448 sepstr = JSSTRING_CHARS(sep);
450 tmplen = JSSTRING_LENGTH(str);
451 js_strncpy(&chars[nchars], JSSTRING_CHARS(str), tmplen);
452 nchars += tmplen;
453 }
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 }
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 }
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};
494 #if JS_HAS_TOSOURCE
495 static JSBool
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
503 static JSBool
504 array_toString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
505 jsval *rval)
506 {
507 JSBool literalize;
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 }
518 static JSBool
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 }
529 static JSBool
530 InitArrayElements(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
531 {
532 jsuint index;
533 jsid id;
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 }
544 static JSBool
545 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
546 {
547 jsval v;
548 jsid id;
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 }
564 #if JS_HAS_SOME_PERL_FUN
565 /*
566 * Perl-inspired join, reverse, and sort.
567 */
568 static JSBool
569 array_join(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
570 {
571 JSString *str;
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 }
582 static JSBool
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;
590 if (!js_GetLengthProperty(cx, obj, &len))
591 return JS_FALSE;
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;
604 #if JS_HAS_SPARSE_ARRAYS
605 /* This part isn't done yet. */
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
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 }
622 *rval = OBJECT_TO_JSVAL(obj);
623 return JS_TRUE;
624 }
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;
635 static int
636 sort_compare(const void *a, const void *b, void *arg);
638 static int
639 sort_compare_strings(const void *a, const void *b, void *arg);
641 static void
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;
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;
657 fastcopy = hsa->fastcopy;
658 #define MEMCPY(p,q,n) \
659 (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
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;
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;
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 }
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;
696 a = (char *)vec2 + lo * elsize;
697 MEMCPY(a, b, elsize);
698 lo = j;
699 }
701 a = (char *)vec2 + lo * elsize;
702 MEMCPY(a, pivot, elsize);
703 #undef MEMCPY
704 }
706 JSBool
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;
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);
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);
728 free(pivot);
729 return JS_TRUE;
730 }
732 typedef struct CompareArgs {
733 JSContext *context;
734 jsval fval;
735 JSBool status;
736 } CompareArgs;
738 static int
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;
748 fval = ca->fval;
749 if (fval == JSVAL_NULL) {
750 JSString *astr, *bstr;
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 }
789 static int
790 sort_compare_strings(const void *a, const void *b, void *arg)
791 {
792 jsval av = *(const jsval *)a, bv = *(const jsval *)b;
794 return (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
795 }
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
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;
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;
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 }
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 }
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;
850 #if JS_HAS_SPARSE_ARRAYS
851 newlen = 0;
852 #else
853 newlen = len;
854 #endif
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;
879 /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
880 all_strings &= JSVAL_IS_STRING(vec[i]);
881 }
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 }
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);
902 /* Delete any leftover properties greater than newlen. */
903 while (ca.status && newlen < len) {
904 jsval junk;
906 ca.status = !IndexToId(cx, newlen, &id) ||
907 !OBJ_DELETE_PROPERTY(cx, obj, id, &junk);
908 newlen++;
909 }
910 }
911 #endif
912 }
914 out:
915 if (vec)
916 JS_free(cx, vec);
917 return ca.status;
918 }
919 #endif /* JS_HAS_SOME_PERL_FUN */
921 #if JS_HAS_MORE_PERL_FUN
922 /*
923 * Perl-inspired push, pop, shift, unshift, and splice methods.
924 */
925 static JSBool
926 array_push(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
927 {
928 jsuint length;
929 uintN i;
930 jsid id;
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 }
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 }
955 static JSBool
956 array_pop(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
957 {
958 jsuint index;
959 jsid id;
960 jsval junk;
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;
969 /* Get the to-be-deleted property's value into rval. */
970 if (!OBJ_GET_PROPERTY(cx, obj, id, rval))
971 return JS_FALSE;
973 if (!OBJ_DELETE_PROPERTY(cx, obj, id, &junk))
974 return JS_FALSE;
975 }
976 return js_SetLengthProperty(cx, obj, index);
977 }
979 static JSBool
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;
986 if (!js_GetLengthProperty(cx, obj, &length))
987 return JS_FALSE;
988 if (length > 0) {
989 length--;
990 id = JSVAL_ZERO;
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;
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 }
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 }
1019 static JSBool
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
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 }
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 }
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 }
1075 static JSBool
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;
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;
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++;
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 }
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);
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 }
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 }
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 }
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 */
1214 #if JS_HAS_SEQUENCE_OPS
1215 /*
1216 * Python-esque sequence operations.
1217 */
1218 static JSBool
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;
1227 /* Treat obj as the first argument; see ECMA 15.4.4.4. */
1228 --argv;
1229 JS_ASSERT(obj == JSVAL_TO_OBJECT(argv[0]));
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);
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 }
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 }
1273 return JS_TRUE;
1274 }
1276 static JSBool
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;
1285 nobj = js_NewArrayObject(cx, 0, NULL);
1286 if (!nobj)
1287 return JS_FALSE;
1289 if (!js_GetLengthProperty(cx, obj, &length))
1290 return JS_FALSE;
1291 begin = 0;
1292 end = length;
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;
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 }
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 */
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},
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
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
1364 {0,0,0,0,0}
1365 };
1367 static JSBool
1368 Array(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
1369 {
1370 jsuint length;
1371 jsval *vector;
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 }
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 }
1401 JSObject *
1402 js_InitArrayClass(JSContext *cx, JSObject *obj)
1403 {
1404 JSObject *proto;
1406 proto = JS_InitClass(cx, obj, NULL, &js_ArrayClass, Array, 1,
1407 NULL, array_methods, NULL, NULL);
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 }
1415 JSObject *
1416 js_NewArrayObject(JSContext *cx, jsuint length, jsval *vector)
1417 {
1418 JSObject *obj;
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 }