xref: /reactos/dll/win32/jscript/array.c (revision 23373acb) 
1 /*
2  * Copyright 2008 Jacek Caban for CodeWeavers
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
17  */
18 
19 #include "config.h"
20 #include "wine/port.h"
21 
22 #include <math.h>
23 #include <assert.h>
24 
25 #include "jscript.h"
26 
27 #include "wine/debug.h"
28 
29 WINE_DEFAULT_DEBUG_CHANNEL(jscript);
30 
31 typedef struct {
32     jsdisp_t dispex;
33 
34     DWORD length;
35 } ArrayInstance;
36 
37 static const WCHAR lengthW[] = {'l','e','n','g','t','h',0};
38 static const WCHAR concatW[] = {'c','o','n','c','a','t',0};
39 static const WCHAR forEachW[] = {'f','o','r','E','a','c','h',0};
40 static const WCHAR joinW[] = {'j','o','i','n',0};
41 static const WCHAR popW[] = {'p','o','p',0};
42 static const WCHAR pushW[] = {'p','u','s','h',0};
43 static const WCHAR reverseW[] = {'r','e','v','e','r','s','e',0};
44 static const WCHAR shiftW[] = {'s','h','i','f','t',0};
45 static const WCHAR sliceW[] = {'s','l','i','c','e',0};
46 static const WCHAR sortW[] = {'s','o','r','t',0};
47 static const WCHAR spliceW[] = {'s','p','l','i','c','e',0};
48 static const WCHAR toStringW[] = {'t','o','S','t','r','i','n','g',0};
49 static const WCHAR toLocaleStringW[] = {'t','o','L','o','c','a','l','e','S','t','r','i','n','g',0};
50 static const WCHAR unshiftW[] = {'u','n','s','h','i','f','t',0};
51 static const WCHAR indexOfW[] = {'i','n','d','e','x','O','f',0};
52 
53 static const WCHAR default_separatorW[] = {',',0};
54 
55 static inline ArrayInstance *array_from_jsdisp(jsdisp_t *jsdisp)
56 {
57     return CONTAINING_RECORD(jsdisp, ArrayInstance, dispex);
58 }
59 
60 static inline ArrayInstance *array_from_vdisp(vdisp_t *vdisp)
61 {
62     return array_from_jsdisp(vdisp->u.jsdisp);
63 }
64 
65 static inline ArrayInstance *array_this(vdisp_t *jsthis)
66 {
67     return is_vclass(jsthis, JSCLASS_ARRAY) ? array_from_vdisp(jsthis) : NULL;
68 }
69 
70 unsigned array_get_length(jsdisp_t *array)
71 {
72     assert(is_class(array, JSCLASS_ARRAY));
73     return array_from_jsdisp(array)->length;
74 }
75 
76 static HRESULT get_length(script_ctx_t *ctx, vdisp_t *vdisp, jsdisp_t **jsthis, DWORD *ret)
77 {
78     ArrayInstance *array;
79     jsval_t val;
80     HRESULT hres;
81 
82     array = array_this(vdisp);
83     if(array) {
84         *jsthis = &array->dispex;
85         *ret = array->length;
86         return S_OK;
87     }
88 
89     if(!is_jsdisp(vdisp))
90         return throw_type_error(ctx, JS_E_JSCRIPT_EXPECTED, NULL);
91 
92     hres = jsdisp_propget_name(vdisp->u.jsdisp, lengthW, &val);
93     if(FAILED(hres))
94         return hres;
95 
96     hres = to_uint32(ctx, val, ret);
97     jsval_release(val);
98     if(FAILED(hres))
99         return hres;
100 
101     *jsthis = vdisp->u.jsdisp;
102     return S_OK;
103 }
104 
105 static HRESULT set_length(jsdisp_t *obj, DWORD length)
106 {
107     if(is_class(obj, JSCLASS_ARRAY)) {
108         array_from_jsdisp(obj)->length = length;
109         return S_OK;
110     }
111 
112     return jsdisp_propput_name(obj, lengthW, jsval_number(length));
113 }
114 
115 static WCHAR *idx_to_str(DWORD idx, WCHAR *ptr)
116 {
117     if(!idx) {
118         *ptr = '0';
119         return ptr;
120     }
121 
122     while(idx) {
123         *ptr-- = '0' + (idx%10);
124         idx /= 10;
125     }
126 
127     return ptr+1;
128 }
129 
130 static HRESULT Array_get_length(script_ctx_t *ctx, jsdisp_t *jsthis, jsval_t *r)
131 {
132     TRACE("%p\n", jsthis);
133 
134     *r = jsval_number(array_from_jsdisp(jsthis)->length);
135     return S_OK;
136 }
137 
138 static HRESULT Array_set_length(script_ctx_t *ctx, jsdisp_t *jsthis, jsval_t value)
139 {
140     ArrayInstance *This = array_from_jsdisp(jsthis);
141     DOUBLE len = -1;
142     DWORD i;
143     HRESULT hres;
144 
145     TRACE("%p %d\n", This, This->length);
146 
147     hres = to_number(ctx, value, &len);
148     if(FAILED(hres))
149         return hres;
150 
151     len = floor(len);
152     if(len!=(DWORD)len)
153         return throw_range_error(ctx, JS_E_INVALID_LENGTH, NULL);
154 
155     for(i=len; i < This->length; i++) {
156         hres = jsdisp_delete_idx(&This->dispex, i);
157         if(FAILED(hres))
158             return hres;
159     }
160 
161     This->length = len;
162     return S_OK;
163 }
164 
165 static HRESULT concat_array(jsdisp_t *array, ArrayInstance *obj, DWORD *len)
166 {
167     jsval_t val;
168     DWORD i;
169     HRESULT hres;
170 
171     for(i=0; i < obj->length; i++) {
172         hres = jsdisp_get_idx(&obj->dispex, i, &val);
173         if(hres == DISP_E_UNKNOWNNAME)
174             continue;
175         if(FAILED(hres))
176             return hres;
177 
178         hres = jsdisp_propput_idx(array, *len+i, val);
179         jsval_release(val);
180         if(FAILED(hres))
181             return hres;
182     }
183 
184     *len += obj->length;
185     return S_OK;
186 }
187 
188 static HRESULT concat_obj(jsdisp_t *array, IDispatch *obj, DWORD *len)
189 {
190     jsdisp_t *jsobj;
191     HRESULT hres;
192 
193     jsobj = iface_to_jsdisp(obj);
194     if(jsobj) {
195         if(is_class(jsobj, JSCLASS_ARRAY)) {
196             hres = concat_array(array, array_from_jsdisp(jsobj), len);
197             jsdisp_release(jsobj);
198             return hres;
199         }
200         jsdisp_release(jsobj);
201     }
202 
203     return jsdisp_propput_idx(array, (*len)++, jsval_disp(obj));
204 }
205 
206 static HRESULT Array_concat(script_ctx_t *ctx, vdisp_t *jsthis, WORD flags, unsigned argc, jsval_t *argv,
207         jsval_t *r)
208 {
209     jsdisp_t *ret;
210     DWORD len = 0;
211     HRESULT hres;
212 
213     TRACE("\n");
214 
215     hres = create_array(ctx, 0, &ret);
216     if(FAILED(hres))
217         return hres;
218 
219     hres = concat_obj(ret, jsthis->u.disp, &len);
220     if(SUCCEEDED(hres)) {
221         DWORD i;
222 
223         for(i=0; i < argc; i++) {
224             if(is_object_instance(argv[i]))
225                 hres = concat_obj(ret, get_object(argv[i]), &len);
226             else
227                 hres = jsdisp_propput_idx(ret, len++, argv[i]);
228             if(FAILED(hres))
229                 break;
230         }
231     }
232 
233     if(FAILED(hres))
234         return hres;
235 
236     if(r)
237         *r = jsval_obj(ret);
238     else
239         jsdisp_release(ret);
240     return S_OK;
241 }
242 
243 static HRESULT array_join(script_ctx_t *ctx, jsdisp_t *array, DWORD length, const WCHAR *sep,
244         unsigned seplen, jsval_t *r)
245 {
246     jsstr_t **str_tab, *ret = NULL;
247     jsval_t val;
248     DWORD i;
249     HRESULT hres = E_FAIL;
250 
251     if(!length) {
252         if(r)
253             *r = jsval_string(jsstr_empty());
254         return S_OK;
255     }
256 
257     str_tab = heap_alloc_zero(length * sizeof(*str_tab));
258     if(!str_tab)
259         return E_OUTOFMEMORY;
260 
261     for(i=0; i < length; i++) {
262         hres = jsdisp_get_idx(array, i, &val);
263         if(hres == DISP_E_UNKNOWNNAME) {
264             hres = S_OK;
265             continue;
266         } else if(FAILED(hres))
267             break;
268 
269         if(!is_undefined(val) && !is_null(val)) {
270             hres = to_string(ctx, val, str_tab+i);
271             jsval_release(val);
272             if(FAILED(hres))
273                 break;
274         }
275     }
276 
277     if(SUCCEEDED(hres)) {
278         DWORD len = 0;
279 
280         if(str_tab[0])
281             len = jsstr_length(str_tab[0]);
282         for(i=1; i < length; i++) {
283             len += seplen;
284             if(str_tab[i])
285                 len += jsstr_length(str_tab[i]);
286             if(len > JSSTR_MAX_LENGTH) {
287                 hres = E_OUTOFMEMORY;
288                 break;
289             }
290         }
291 
292         if(SUCCEEDED(hres)) {
293             WCHAR *ptr = NULL;
294 
295             ret = jsstr_alloc_buf(len, &ptr);
296             if(ret) {
297                 if(str_tab[0])
298                     ptr += jsstr_flush(str_tab[0], ptr);
299 
300                 for(i=1; i < length; i++) {
301                     if(seplen) {
302                         memcpy(ptr, sep, seplen*sizeof(WCHAR));
303                         ptr += seplen;
304                     }
305 
306                     if(str_tab[i])
307                         ptr += jsstr_flush(str_tab[i], ptr);
308                 }
309             }else {
310                 hres = E_OUTOFMEMORY;
311             }
312         }
313     }
314 
315     for(i=0; i < length; i++) {
316         if(str_tab[i])
317             jsstr_release(str_tab[i]);
318     }
319     heap_free(str_tab);
320     if(FAILED(hres))
321         return hres;
322 
323     TRACE("= %s\n", debugstr_jsstr(ret));
324 
325     if(r)
326         *r = jsval_string(ret);
327     else
328         jsstr_release(ret);
329     return S_OK;
330 }
331 
332 /* ECMA-262 3rd Edition    15.4.4.5 */
333 static HRESULT Array_join(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
334         jsval_t *r)
335 {
336     jsdisp_t *jsthis;
337     DWORD length;
338     HRESULT hres;
339 
340     TRACE("\n");
341 
342     hres = get_length(ctx, vthis, &jsthis, &length);
343     if(FAILED(hres))
344         return hres;
345 
346     if(argc) {
347         const WCHAR *sep;
348         jsstr_t *sep_str;
349 
350         hres = to_flat_string(ctx, argv[0], &sep_str, &sep);
351         if(FAILED(hres))
352             return hres;
353 
354         hres = array_join(ctx, jsthis, length, sep, jsstr_length(sep_str), r);
355 
356         jsstr_release(sep_str);
357     }else {
358         hres = array_join(ctx, jsthis, length, default_separatorW, strlenW(default_separatorW), r);
359     }
360 
361     return hres;
362 }
363 
364 static HRESULT Array_pop(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
365         jsval_t *r)
366 {
367     jsdisp_t *jsthis;
368     jsval_t val;
369     DWORD length;
370     HRESULT hres;
371 
372     TRACE("\n");
373 
374     hres = get_length(ctx, vthis, &jsthis, &length);
375     if(FAILED(hres))
376         return hres;
377 
378     if(!length) {
379         hres = set_length(jsthis, 0);
380         if(FAILED(hres))
381             return hres;
382 
383         if(r)
384             *r = jsval_undefined();
385         return S_OK;
386     }
387 
388     length--;
389     hres = jsdisp_get_idx(jsthis, length, &val);
390     if(SUCCEEDED(hres))
391         hres = jsdisp_delete_idx(jsthis, length);
392     else if(hres == DISP_E_UNKNOWNNAME) {
393         val = jsval_undefined();
394         hres = S_OK;
395     }else
396         return hres;
397 
398     if(SUCCEEDED(hres))
399         hres = set_length(jsthis, length);
400 
401     if(FAILED(hres)) {
402         jsval_release(val);
403         return hres;
404     }
405 
406     if(r)
407         *r = val;
408     else
409         jsval_release(val);
410     return hres;
411 }
412 
413 /* ECMA-262 3rd Edition    15.4.4.7 */
414 static HRESULT Array_push(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
415         jsval_t *r)
416 {
417     jsdisp_t *jsthis;
418     DWORD length = 0;
419     unsigned i;
420     HRESULT hres;
421 
422     TRACE("\n");
423 
424     hres = get_length(ctx, vthis, &jsthis, &length);
425     if(FAILED(hres))
426         return hres;
427 
428     for(i=0; i < argc; i++) {
429         hres = jsdisp_propput_idx(jsthis, length+i, argv[i]);
430         if(FAILED(hres))
431             return hres;
432     }
433 
434     hres = set_length(jsthis, length+argc);
435     if(FAILED(hres))
436         return hres;
437 
438     if(r)
439         *r = jsval_number(length+argc);
440     return S_OK;
441 }
442 
443 static HRESULT Array_reverse(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
444         jsval_t *r)
445 {
446     jsdisp_t *jsthis;
447     DWORD length, k, l;
448     jsval_t v1, v2;
449     HRESULT hres1, hres2;
450 
451     TRACE("\n");
452 
453     hres1 = get_length(ctx, vthis, &jsthis, &length);
454     if(FAILED(hres1))
455         return hres1;
456 
457     for(k=0; k<length/2; k++) {
458         l = length-k-1;
459 
460         hres1 = jsdisp_get_idx(jsthis, k, &v1);
461         if(FAILED(hres1) && hres1!=DISP_E_UNKNOWNNAME)
462             return hres1;
463 
464         hres2 = jsdisp_get_idx(jsthis, l, &v2);
465         if(FAILED(hres2) && hres2!=DISP_E_UNKNOWNNAME) {
466             jsval_release(v1);
467             return hres2;
468         }
469 
470         if(hres1 == DISP_E_UNKNOWNNAME)
471             hres1 = jsdisp_delete_idx(jsthis, l);
472         else
473             hres1 = jsdisp_propput_idx(jsthis, l, v1);
474 
475         if(FAILED(hres1)) {
476             jsval_release(v1);
477             jsval_release(v2);
478             return hres1;
479         }
480 
481         if(hres2 == DISP_E_UNKNOWNNAME)
482             hres2 = jsdisp_delete_idx(jsthis, k);
483         else
484             hres2 = jsdisp_propput_idx(jsthis, k, v2);
485 
486         if(FAILED(hres2)) {
487             jsval_release(v2);
488             return hres2;
489         }
490     }
491 
492     if(r)
493         *r = jsval_obj(jsdisp_addref(jsthis));
494     return S_OK;
495 }
496 
497 /* ECMA-262 3rd Edition    15.4.4.9 */
498 static HRESULT Array_shift(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
499         jsval_t *r)
500 {
501     jsdisp_t *jsthis;
502     DWORD length = 0, i;
503     jsval_t v, ret;
504     HRESULT hres;
505 
506     TRACE("\n");
507 
508     hres = get_length(ctx, vthis, &jsthis, &length);
509     if(FAILED(hres))
510         return hres;
511 
512     if(!length) {
513         hres = set_length(jsthis, 0);
514         if(FAILED(hres))
515             return hres;
516 
517         if(r)
518             *r = jsval_undefined();
519         return S_OK;
520     }
521 
522     hres = jsdisp_get_idx(jsthis, 0, &ret);
523     if(hres == DISP_E_UNKNOWNNAME) {
524         ret = jsval_undefined();
525         hres = S_OK;
526     }
527 
528     for(i=1; SUCCEEDED(hres) && i<length; i++) {
529         hres = jsdisp_get_idx(jsthis, i, &v);
530         if(hres == DISP_E_UNKNOWNNAME)
531             hres = jsdisp_delete_idx(jsthis, i-1);
532         else if(SUCCEEDED(hres))
533             hres = jsdisp_propput_idx(jsthis, i-1, v);
534     }
535 
536     if(SUCCEEDED(hres)) {
537         hres = jsdisp_delete_idx(jsthis, length-1);
538         if(SUCCEEDED(hres))
539             hres = set_length(jsthis, length-1);
540     }
541 
542     if(FAILED(hres))
543         return hres;
544 
545     if(r)
546         *r = ret;
547     else
548         jsval_release(ret);
549     return hres;
550 }
551 
552 /* ECMA-262 3rd Edition    15.4.4.10 */
553 static HRESULT Array_slice(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv, jsval_t *r)
554 {
555     jsdisp_t *arr, *jsthis;
556     DOUBLE range;
557     DWORD length, start, end, idx;
558     HRESULT hres;
559 
560     TRACE("\n");
561 
562     hres = get_length(ctx, vthis, &jsthis, &length);
563     if(FAILED(hres))
564         return hres;
565 
566     if(argc) {
567         hres = to_number(ctx, argv[0], &range);
568         if(FAILED(hres))
569             return hres;
570 
571         range = floor(range);
572         if(-range>length || isnan(range)) start = 0;
573         else if(range < 0) start = range+length;
574         else if(range <= length) start = range;
575         else start = length;
576     }
577     else start = 0;
578 
579     if(argc > 1) {
580         hres = to_number(ctx, argv[1], &range);
581         if(FAILED(hres))
582             return hres;
583 
584         range = floor(range);
585         if(-range>length) end = 0;
586         else if(range < 0) end = range+length;
587         else if(range <= length) end = range;
588         else end = length;
589     }
590     else end = length;
591 
592     hres = create_array(ctx, (end>start)?end-start:0, &arr);
593     if(FAILED(hres))
594         return hres;
595 
596     for(idx=start; idx<end; idx++) {
597         jsval_t v;
598 
599         hres = jsdisp_get_idx(jsthis, idx, &v);
600         if(hres == DISP_E_UNKNOWNNAME)
601             continue;
602 
603         if(SUCCEEDED(hres)) {
604             hres = jsdisp_propput_idx(arr, idx-start, v);
605             jsval_release(v);
606         }
607 
608         if(FAILED(hres)) {
609             jsdisp_release(arr);
610             return hres;
611         }
612     }
613 
614     if(r)
615         *r = jsval_obj(arr);
616     else
617         jsdisp_release(arr);
618 
619     return S_OK;
620 }
621 
622 static HRESULT sort_cmp(script_ctx_t *ctx, jsdisp_t *cmp_func, jsval_t v1, jsval_t v2, INT *cmp)
623 {
624     HRESULT hres;
625 
626     if(cmp_func) {
627         jsval_t args[2];
628         jsval_t res;
629         double n;
630 
631         args[0] = v1;
632         args[1] = v2;
633 
634         hres = jsdisp_call_value(cmp_func, NULL, DISPATCH_METHOD, 2, args, &res);
635         if(FAILED(hres))
636             return hres;
637 
638         hres = to_number(ctx, res, &n);
639         jsval_release(res);
640         if(FAILED(hres))
641             return hres;
642 
643         if(n == 0)
644             *cmp = 0;
645         *cmp = n > 0.0 ? 1 : -1;
646     }else if(is_undefined(v1)) {
647         *cmp = is_undefined(v2) ? 0 : 1;
648     }else if(is_undefined(v2)) {
649         *cmp = -1;
650     }else if(is_number(v1) && is_number(v2)) {
651         double d = get_number(v1)-get_number(v2);
652         if(d > 0.0)
653             *cmp = 1;
654         else
655             *cmp = d < -0.0 ? -1 : 0;
656     }else {
657         jsstr_t *x, *y;
658 
659         hres = to_string(ctx, v1, &x);
660         if(FAILED(hres))
661             return hres;
662 
663         hres = to_string(ctx, v2, &y);
664         if(SUCCEEDED(hres)) {
665             *cmp = jsstr_cmp(x, y);
666             jsstr_release(y);
667         }
668         jsstr_release(x);
669         if(FAILED(hres))
670             return hres;
671     }
672 
673     return S_OK;
674 }
675 
676 /* ECMA-262 3rd Edition    15.4.4.11 */
677 static HRESULT Array_sort(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
678         jsval_t *r)
679 {
680     jsdisp_t *jsthis, *cmp_func = NULL;
681     jsval_t *vtab, **sorttab = NULL;
682     DWORD length;
683     DWORD i;
684     HRESULT hres = S_OK;
685 
686     TRACE("\n");
687 
688     hres = get_length(ctx, vthis, &jsthis, &length);
689     if(FAILED(hres))
690         return hres;
691 
692     if(argc > 1) {
693         WARN("invalid arg_cnt %d\n", argc);
694         return E_FAIL;
695     }
696 
697     if(argc == 1) {
698         if(!is_object_instance(argv[0])) {
699             WARN("arg is not dispatch\n");
700             return E_FAIL;
701         }
702 
703         cmp_func = iface_to_jsdisp(get_object(argv[0]));
704         if(!cmp_func || !is_class(cmp_func, JSCLASS_FUNCTION)) {
705             WARN("cmp_func is not a function\n");
706             if(cmp_func)
707                 jsdisp_release(cmp_func);
708             return E_FAIL;
709         }
710     }
711 
712     if(!length) {
713         if(cmp_func)
714             jsdisp_release(cmp_func);
715         if(r)
716             *r = jsval_obj(jsdisp_addref(jsthis));
717         return S_OK;
718     }
719 
720     vtab = heap_alloc_zero(length * sizeof(*vtab));
721     if(vtab) {
722         for(i=0; i<length; i++) {
723             hres = jsdisp_get_idx(jsthis, i, vtab+i);
724             if(hres == DISP_E_UNKNOWNNAME) {
725                 vtab[i] = jsval_undefined();
726                 hres = S_OK;
727             } else if(FAILED(hres)) {
728                 WARN("Could not get elem %d: %08x\n", i, hres);
729                 break;
730             }
731         }
732     }else {
733         hres = E_OUTOFMEMORY;
734     }
735 
736     if(SUCCEEDED(hres)) {
737         sorttab = heap_alloc(length*2*sizeof(*sorttab));
738         if(!sorttab)
739             hres = E_OUTOFMEMORY;
740     }
741 
742     /* merge-sort */
743     if(SUCCEEDED(hres)) {
744         jsval_t *tmpv, **tmpbuf;
745         INT cmp;
746 
747         tmpbuf = sorttab + length;
748         for(i=0; i < length; i++)
749             sorttab[i] = vtab+i;
750 
751         for(i=0; i < length/2; i++) {
752             hres = sort_cmp(ctx, cmp_func, *sorttab[2*i+1], *sorttab[2*i], &cmp);
753             if(FAILED(hres))
754                 break;
755 
756             if(cmp < 0) {
757                 tmpv = sorttab[2*i];
758                 sorttab[2*i] = sorttab[2*i+1];
759                 sorttab[2*i+1] = tmpv;
760             }
761         }
762 
763         if(SUCCEEDED(hres)) {
764             DWORD k, a, b, bend;
765 
766             for(k=2; k < length; k *= 2) {
767                 for(i=0; i+k < length; i += 2*k) {
768                     a = b = 0;
769                     if(i+2*k <= length)
770                         bend = k;
771                     else
772                         bend = length - (i+k);
773 
774                     memcpy(tmpbuf, sorttab+i, k*sizeof(jsval_t*));
775 
776                     while(a < k && b < bend) {
777                         hres = sort_cmp(ctx, cmp_func, *tmpbuf[a], *sorttab[i+k+b], &cmp);
778                         if(FAILED(hres))
779                             break;
780 
781                         if(cmp < 0) {
782                             sorttab[i+a+b] = tmpbuf[a];
783                             a++;
784                         }else {
785                             sorttab[i+a+b] = sorttab[i+k+b];
786                             b++;
787                         }
788                     }
789 
790                     if(FAILED(hres))
791                         break;
792 
793                     if(a < k)
794                         memcpy(sorttab+i+a+b, tmpbuf+a, (k-a)*sizeof(jsval_t*));
795                 }
796 
797                 if(FAILED(hres))
798                     break;
799             }
800         }
801 
802         for(i=0; SUCCEEDED(hres) && i < length; i++)
803             hres = jsdisp_propput_idx(jsthis, i, *sorttab[i]);
804     }
805 
806     if(vtab) {
807         for(i=0; i < length; i++)
808             jsval_release(vtab[i]);
809         heap_free(vtab);
810     }
811     heap_free(sorttab);
812     if(cmp_func)
813         jsdisp_release(cmp_func);
814 
815     if(FAILED(hres))
816         return hres;
817 
818     if(r)
819         *r = jsval_obj(jsdisp_addref(jsthis));
820     return S_OK;
821 }
822 
823 /* ECMA-262 3rd Edition    15.4.4.12 */
824 static HRESULT Array_splice(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
825         jsval_t *r)
826 {
827     DWORD length, start=0, delete_cnt=0, i, add_args = 0;
828     jsdisp_t *ret_array = NULL, *jsthis;
829     jsval_t val;
830     double d;
831     int n;
832     HRESULT hres = S_OK;
833 
834     TRACE("\n");
835 
836     hres = get_length(ctx, vthis, &jsthis, &length);
837     if(FAILED(hres))
838         return hres;
839 
840     if(argc) {
841         hres = to_integer(ctx, argv[0], &d);
842         if(FAILED(hres))
843             return hres;
844 
845         if(is_int32(d)) {
846             if((n = d) >= 0)
847                 start = min(n, length);
848             else
849                 start = -n > length ? 0 : length + n;
850         }else {
851             start = d < 0.0 ? 0 : length;
852         }
853     }
854 
855     if(argc >= 2) {
856         hres = to_integer(ctx, argv[1], &d);
857         if(FAILED(hres))
858             return hres;
859 
860         if(is_int32(d)) {
861             if((n = d) > 0)
862                 delete_cnt = min(n, length-start);
863         }else if(d > 0.0) {
864             delete_cnt = length-start;
865         }
866 
867         add_args = argc-2;
868     }
869 
870     if(r) {
871         hres = create_array(ctx, 0, &ret_array);
872         if(FAILED(hres))
873             return hres;
874 
875         for(i=0; SUCCEEDED(hres) && i < delete_cnt; i++) {
876             hres = jsdisp_get_idx(jsthis, start+i, &val);
877             if(hres == DISP_E_UNKNOWNNAME) {
878                 hres = S_OK;
879             }else if(SUCCEEDED(hres)) {
880                 hres = jsdisp_propput_idx(ret_array, i, val);
881                 jsval_release(val);
882             }
883         }
884 
885         if(SUCCEEDED(hres))
886             hres = jsdisp_propput_name(ret_array, lengthW, jsval_number(delete_cnt));
887     }
888 
889     if(add_args < delete_cnt) {
890         for(i = start; SUCCEEDED(hres) && i < length-delete_cnt; i++) {
891             hres = jsdisp_get_idx(jsthis, i+delete_cnt, &val);
892             if(hres == DISP_E_UNKNOWNNAME) {
893                 hres = jsdisp_delete_idx(jsthis, i+add_args);
894             }else if(SUCCEEDED(hres)) {
895                 hres = jsdisp_propput_idx(jsthis, i+add_args, val);
896                 jsval_release(val);
897             }
898         }
899 
900         for(i=length; SUCCEEDED(hres) && i != length-delete_cnt+add_args; i--)
901             hres = jsdisp_delete_idx(jsthis, i-1);
902     }else if(add_args > delete_cnt) {
903         for(i=length-delete_cnt; SUCCEEDED(hres) && i != start; i--) {
904             hres = jsdisp_get_idx(jsthis, i+delete_cnt-1, &val);
905             if(hres == DISP_E_UNKNOWNNAME) {
906                 hres = jsdisp_delete_idx(jsthis, i+add_args-1);
907             }else if(SUCCEEDED(hres)) {
908                 hres = jsdisp_propput_idx(jsthis, i+add_args-1, val);
909                 jsval_release(val);
910             }
911         }
912     }
913 
914     for(i=0; SUCCEEDED(hres) && i < add_args; i++)
915         hres = jsdisp_propput_idx(jsthis, start+i, argv[i+2]);
916 
917     if(SUCCEEDED(hres))
918         hres = jsdisp_propput_name(jsthis, lengthW, jsval_number(length-delete_cnt+add_args));
919 
920     if(FAILED(hres)) {
921         if(ret_array)
922             jsdisp_release(ret_array);
923         return hres;
924     }
925 
926     if(r)
927         *r = jsval_obj(ret_array);
928     return S_OK;
929 }
930 
931 /* ECMA-262 3rd Edition    15.4.4.2 */
932 static HRESULT Array_toString(script_ctx_t *ctx, vdisp_t *jsthis, WORD flags, unsigned argc, jsval_t *argv,
933         jsval_t *r)
934 {
935     ArrayInstance *array;
936 
937     TRACE("\n");
938 
939     array = array_this(jsthis);
940     if(!array)
941         return throw_type_error(ctx, JS_E_ARRAY_EXPECTED, NULL);
942 
943     return array_join(ctx, &array->dispex, array->length, default_separatorW,
944                       strlenW(default_separatorW), r);
945 }
946 
947 static HRESULT Array_toLocaleString(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
948         jsval_t *r)
949 {
950     FIXME("\n");
951     return E_NOTIMPL;
952 }
953 
954 static HRESULT Array_forEach(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
955         jsval_t *r)
956 {
957     jsval_t value, args[3], res;
958     jsdisp_t *jsthis;
959     unsigned length, i;
960     HRESULT hres;
961 
962     TRACE("\n");
963 
964     /* FIXME: Check IsCallable */
965     if(argc != 1 || !is_object_instance(argv[0])) {
966         FIXME("Unsupported arguments\n");
967         return E_NOTIMPL;
968     }
969 
970     hres = get_length(ctx, vthis, &jsthis, &length);
971     if(FAILED(hres))
972         return hres;
973 
974     for(i = 0; i < length; i++) {
975         hres = jsdisp_get_idx(jsthis, i, &value);
976         if(hres == DISP_E_UNKNOWNNAME)
977             continue;
978         if(FAILED(hres))
979             return hres;
980 
981         args[0] = value;
982         args[1] = jsval_number(i);
983         args[2] = jsval_obj(jsthis);
984         hres = disp_call_value(ctx, get_object(argv[0]), NULL, DISPATCH_METHOD, ARRAY_SIZE(args), args, &res);
985         jsval_release(value);
986         if(FAILED(hres))
987             return hres;
988         jsval_release(res);
989     }
990 
991     if(r) *r = jsval_undefined();
992     return S_OK;
993 }
994 
995 static HRESULT Array_indexOf(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
996         jsval_t *r)
997 {
998     jsdisp_t *jsthis;
999     unsigned length, i, from = 0;
1000     jsval_t search, value;
1001     BOOL eq;
1002     HRESULT hres;
1003 
1004     TRACE("\n");
1005 
1006     hres = get_length(ctx, vthis, &jsthis, &length);
1007     if(FAILED(hres))
1008         return hres;
1009     if(!length) {
1010         if(r) *r = jsval_number(-1);
1011         return S_OK;
1012     }
1013 
1014     search = argc ? argv[0] : jsval_undefined();
1015 
1016     if(argc > 1) {
1017         double from_arg;
1018 
1019         hres = to_integer(ctx, argv[1], &from_arg);
1020         if(FAILED(hres))
1021             return hres;
1022 
1023         if(from_arg >= 0)
1024             from = min(from_arg, length);
1025         else
1026             from = max(from_arg + length, 0);
1027     }
1028 
1029     for(i = from; i < length; i++) {
1030         hres = jsdisp_get_idx(jsthis, i, &value);
1031         if(hres == DISP_E_UNKNOWNNAME)
1032             continue;
1033         if(FAILED(hres))
1034             return hres;
1035 
1036         hres = jsval_strict_equal(value, search, &eq);
1037         jsval_release(value);
1038         if(FAILED(hres))
1039             return hres;
1040         if(eq) {
1041             if(r) *r = jsval_number(i);
1042             return S_OK;
1043         }
1044     }
1045 
1046     if(r) *r = jsval_number(-1);
1047     return S_OK;
1048 }
1049 
1050 /* ECMA-262 3rd Edition    15.4.4.13 */
1051 static HRESULT Array_unshift(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
1052         jsval_t *r)
1053 {
1054     jsdisp_t *jsthis;
1055     WCHAR buf[14], *buf_end, *str;
1056     DWORD i, length;
1057     jsval_t val;
1058     DISPID id;
1059     HRESULT hres;
1060 
1061     TRACE("\n");
1062 
1063     hres = get_length(ctx, vthis, &jsthis, &length);
1064     if(FAILED(hres))
1065         return hres;
1066 
1067     if(argc) {
1068         buf_end = buf + ARRAY_SIZE(buf)-1;
1069         *buf_end-- = 0;
1070         i = length;
1071 
1072         while(i--) {
1073             str = idx_to_str(i, buf_end);
1074 
1075             hres = jsdisp_get_id(jsthis, str, 0, &id);
1076             if(SUCCEEDED(hres)) {
1077                 hres = jsdisp_propget(jsthis, id, &val);
1078                 if(FAILED(hres))
1079                     return hres;
1080 
1081                 hres = jsdisp_propput_idx(jsthis, i+argc, val);
1082                 jsval_release(val);
1083             }else if(hres == DISP_E_UNKNOWNNAME) {
1084                 hres = IDispatchEx_DeleteMemberByDispID(vthis->u.dispex, id);
1085             }
1086         }
1087 
1088         if(FAILED(hres))
1089             return hres;
1090     }
1091 
1092     for(i=0; i<argc; i++) {
1093         hres = jsdisp_propput_idx(jsthis, i, argv[i]);
1094         if(FAILED(hres))
1095             return hres;
1096     }
1097 
1098     if(argc) {
1099         length += argc;
1100         hres = set_length(jsthis, length);
1101         if(FAILED(hres))
1102             return hres;
1103     }
1104 
1105     if(r)
1106         *r = ctx->version < 2 ? jsval_undefined() : jsval_number(length);
1107     return S_OK;
1108 }
1109 
1110 static HRESULT Array_get_value(script_ctx_t *ctx, jsdisp_t *jsthis, jsval_t *r)
1111 {
1112     ArrayInstance *array = array_from_jsdisp(jsthis);
1113 
1114     TRACE("\n");
1115 
1116     return array_join(ctx, &array->dispex, array->length, default_separatorW,
1117                       strlenW(default_separatorW), r);
1118 }
1119 
1120 static void Array_destructor(jsdisp_t *dispex)
1121 {
1122     heap_free(dispex);
1123 }
1124 
1125 static void Array_on_put(jsdisp_t *dispex, const WCHAR *name)
1126 {
1127     ArrayInstance *array = array_from_jsdisp(dispex);
1128     const WCHAR *ptr = name;
1129     DWORD id = 0;
1130 
1131     if(!isdigitW(*ptr))
1132         return;
1133 
1134     while(*ptr && isdigitW(*ptr)) {
1135         id = id*10 + (*ptr-'0');
1136         ptr++;
1137     }
1138 
1139     if(*ptr)
1140         return;
1141 
1142     if(id >= array->length)
1143         array->length = id+1;
1144 }
1145 
1146 static const builtin_prop_t Array_props[] = {
1147     {concatW,                Array_concat,               PROPF_METHOD|1},
1148     {forEachW,               Array_forEach,              PROPF_METHOD|PROPF_ES5|1},
1149     {indexOfW,               Array_indexOf,              PROPF_METHOD|PROPF_ES5|1},
1150     {joinW,                  Array_join,                 PROPF_METHOD|1},
1151     {lengthW,                NULL,0,                     Array_get_length, Array_set_length},
1152     {popW,                   Array_pop,                  PROPF_METHOD},
1153     {pushW,                  Array_push,                 PROPF_METHOD|1},
1154     {reverseW,               Array_reverse,              PROPF_METHOD},
1155     {shiftW,                 Array_shift,                PROPF_METHOD},
1156     {sliceW,                 Array_slice,                PROPF_METHOD|2},
1157     {sortW,                  Array_sort,                 PROPF_METHOD|1},
1158     {spliceW,                Array_splice,               PROPF_METHOD|2},
1159     {toLocaleStringW,        Array_toLocaleString,       PROPF_METHOD},
1160     {toStringW,              Array_toString,             PROPF_METHOD},
1161     {unshiftW,               Array_unshift,              PROPF_METHOD|1},
1162 };
1163 
1164 static const builtin_info_t Array_info = {
1165     JSCLASS_ARRAY,
1166     {NULL, NULL,0, Array_get_value},
1167     ARRAY_SIZE(Array_props),
1168     Array_props,
1169     Array_destructor,
1170     Array_on_put
1171 };
1172 
1173 static const builtin_prop_t ArrayInst_props[] = {
1174     {lengthW,                NULL,0,                     Array_get_length, Array_set_length}
1175 };
1176 
1177 static const builtin_info_t ArrayInst_info = {
1178     JSCLASS_ARRAY,
1179     {NULL, NULL,0, Array_get_value},
1180     ARRAY_SIZE(ArrayInst_props),
1181     ArrayInst_props,
1182     Array_destructor,
1183     Array_on_put
1184 };
1185 
1186 /* ECMA-262 5.1 Edition    15.4.3.2 */
1187 static HRESULT ArrayConstr_isArray(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv, jsval_t *r)
1188 {
1189     jsdisp_t *obj;
1190 
1191     TRACE("\n");
1192 
1193     if(!argc || !is_object_instance(argv[0])) {
1194         if(r) *r = jsval_bool(FALSE);
1195         return S_OK;
1196     }
1197 
1198     obj = iface_to_jsdisp(get_object(argv[0]));
1199     if(r) *r = jsval_bool(obj && is_class(obj, JSCLASS_ARRAY));
1200     if(obj) jsdisp_release(obj);
1201     return S_OK;
1202 }
1203 
1204 static HRESULT ArrayConstr_value(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
1205         jsval_t *r)
1206 {
1207     jsdisp_t *obj;
1208     DWORD i;
1209     HRESULT hres;
1210 
1211     TRACE("\n");
1212 
1213     switch(flags) {
1214     case DISPATCH_METHOD:
1215     case DISPATCH_CONSTRUCT: {
1216         if(argc == 1 && is_number(argv[0])) {
1217             double n = get_number(argv[0]);
1218 
1219             if(n < 0 || !is_int32(n))
1220                 return throw_range_error(ctx, JS_E_INVALID_LENGTH, NULL);
1221 
1222             hres = create_array(ctx, n, &obj);
1223             if(FAILED(hres))
1224                 return hres;
1225 
1226             *r = jsval_obj(obj);
1227             return S_OK;
1228         }
1229 
1230         hres = create_array(ctx, argc, &obj);
1231         if(FAILED(hres))
1232             return hres;
1233 
1234         for(i=0; i < argc; i++) {
1235             hres = jsdisp_propput_idx(obj, i, argv[i]);
1236             if(FAILED(hres))
1237                 break;
1238         }
1239         if(FAILED(hres)) {
1240             jsdisp_release(obj);
1241             return hres;
1242         }
1243 
1244         *r = jsval_obj(obj);
1245         break;
1246     }
1247     default:
1248         FIXME("unimplemented flags: %x\n", flags);
1249         return E_NOTIMPL;
1250     }
1251 
1252     return S_OK;
1253 }
1254 
1255 static HRESULT alloc_array(script_ctx_t *ctx, jsdisp_t *object_prototype, ArrayInstance **ret)
1256 {
1257     ArrayInstance *array;
1258     HRESULT hres;
1259 
1260     array = heap_alloc_zero(sizeof(ArrayInstance));
1261     if(!array)
1262         return E_OUTOFMEMORY;
1263 
1264     if(object_prototype)
1265         hres = init_dispex(&array->dispex, ctx, &Array_info, object_prototype);
1266     else
1267         hres = init_dispex_from_constr(&array->dispex, ctx, &ArrayInst_info, ctx->array_constr);
1268 
1269     if(FAILED(hres)) {
1270         heap_free(array);
1271         return hres;
1272     }
1273 
1274     *ret = array;
1275     return S_OK;
1276 }
1277 
1278 static const WCHAR isArrayW[] = {'i','s','A','r','r','a','y',0};
1279 
1280 static const builtin_prop_t ArrayConstr_props[] = {
1281     {isArrayW,    ArrayConstr_isArray,    PROPF_ES5|PROPF_METHOD|1}
1282 };
1283 
1284 static const builtin_info_t ArrayConstr_info = {
1285     JSCLASS_FUNCTION,
1286     DEFAULT_FUNCTION_VALUE,
1287     ARRAY_SIZE(ArrayConstr_props),
1288     ArrayConstr_props,
1289     NULL,
1290     NULL
1291 };
1292 
1293 HRESULT create_array_constr(script_ctx_t *ctx, jsdisp_t *object_prototype, jsdisp_t **ret)
1294 {
1295     ArrayInstance *array;
1296     HRESULT hres;
1297 
1298     static const WCHAR ArrayW[] = {'A','r','r','a','y',0};
1299 
1300     hres = alloc_array(ctx, object_prototype, &array);
1301     if(FAILED(hres))
1302         return hres;
1303 
1304     hres = create_builtin_constructor(ctx, ArrayConstr_value, ArrayW, &ArrayConstr_info, PROPF_CONSTR|1, &array->dispex, ret);
1305 
1306     jsdisp_release(&array->dispex);
1307     return hres;
1308 }
1309 
1310 HRESULT create_array(script_ctx_t *ctx, DWORD length, jsdisp_t **ret)
1311 {
1312     ArrayInstance *array;
1313     HRESULT hres;
1314 
1315     hres = alloc_array(ctx, NULL, &array);
1316     if(FAILED(hres))
1317         return hres;
1318 
1319     array->length = length;
1320 
1321     *ret = &array->dispex;
1322     return S_OK;
1323 }
1324