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