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