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