dlls/jscript/array.c

   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] = {v1, v2};
 628         jsval_t res;
 629         double n;
 630
 631         hres = jsdisp_call_value(cmp_func, NULL, DISPATCH_METHOD, 2, args, &res);
 632         if(FAILED(hres))
 633             return hres;
 634
 635         hres = to_number(ctx, res, &n);
 636         jsval_release(res);
 637         if(FAILED(hres))
 638             return hres;
 639
 640         if(n == 0)
 641             *cmp = 0;
 642         *cmp = n > 0.0 ? 1 : -1;
 643     }else if(is_undefined(v1)) {
 644         *cmp = is_undefined(v2) ? 0 : 1;
 645     }else if(is_undefined(v2)) {
 646         *cmp = -1;
 647     }else if(is_number(v1) && is_number(v2)) {
 648         double d = get_number(v1)-get_number(v2);
 649         if(d > 0.0)
 650             *cmp = 1;
 651         else
 652             *cmp = d < -0.0 ? -1 : 0;
 653     }else {
 654         jsstr_t *x, *y;
 655
 656         hres = to_string(ctx, v1, &x);
 657         if(FAILED(hres))
 658             return hres;
 659
 660         hres = to_string(ctx, v2, &y);
 661         if(SUCCEEDED(hres)) {
 662             *cmp = jsstr_cmp(x, y);
 663             jsstr_release(y);
 664         }
 665         jsstr_release(x);
 666         if(FAILED(hres))
 667             return hres;
 668     }
 669
 670     return S_OK;
 671 }
 672
 673 /* ECMA-262 3rd Edition    15.4.4.11 */
 674 static HRESULT Array_sort(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
 675         jsval_t *r)
 676 {
 677     jsdisp_t *jsthis, *cmp_func = NULL;
 678     jsval_t *vtab, **sorttab = NULL;
 679     DWORD length;
 680     DWORD i;
 681     HRESULT hres = S_OK;
 682
 683     TRACE("\n");
 684
 685     hres = get_length(ctx, vthis, &jsthis, &length);
 686     if(FAILED(hres))
 687         return hres;
 688
 689     if(argc > 1) {
 690         WARN("invalid arg_cnt %d\n", argc);
 691         return E_FAIL;
 692     }
 693
 694     if(argc == 1) {
 695         if(!is_object_instance(argv[0])) {
 696             WARN("arg is not dispatch\n");
 697             return E_FAIL;
 698         }
 699
 700         cmp_func = iface_to_jsdisp(get_object(argv[0]));
 701         if(!cmp_func || !is_class(cmp_func, JSCLASS_FUNCTION)) {
 702             WARN("cmp_func is not a function\n");
 703             if(cmp_func)
 704                 jsdisp_release(cmp_func);
 705             return E_FAIL;
 706         }
 707     }
 708
 709     if(!length) {
 710         if(cmp_func)
 711             jsdisp_release(cmp_func);
 712         if(r)
 713             *r = jsval_obj(jsdisp_addref(jsthis));
 714         return S_OK;
 715     }
 716
 717     vtab = heap_alloc_zero(length * sizeof(*vtab));
 718     if(vtab) {
 719         for(i=0; i<length; i++) {
 720             hres = jsdisp_get_idx(jsthis, i, vtab+i);
 721             if(hres == DISP_E_UNKNOWNNAME) {
 722                 vtab[i] = jsval_undefined();
 723                 hres = S_OK;
 724             } else if(FAILED(hres)) {
 725                 WARN("Could not get elem %d: %08x\n", i, hres);
 726                 break;
 727             }
 728         }
 729     }else {
 730         hres = E_OUTOFMEMORY;
 731     }
 732
 733     if(SUCCEEDED(hres)) {
 734         sorttab = heap_alloc(length*2*sizeof(*sorttab));
 735         if(!sorttab)
 736             hres = E_OUTOFMEMORY;
 737     }
 738
 739     /* merge-sort */
 740     if(SUCCEEDED(hres)) {
 741         jsval_t *tmpv, **tmpbuf;
 742         INT cmp;
 743
 744         tmpbuf = sorttab + length;
 745         for(i=0; i < length; i++)
 746             sorttab[i] = vtab+i;
 747
 748         for(i=0; i < length/2; i++) {
 749             hres = sort_cmp(ctx, cmp_func, *sorttab[2*i+1], *sorttab[2*i], &cmp);
 750             if(FAILED(hres))
 751                 break;
 752
 753             if(cmp < 0) {
 754                 tmpv = sorttab[2*i];
 755                 sorttab[2*i] = sorttab[2*i+1];
 756                 sorttab[2*i+1] = tmpv;
 757             }
 758         }
 759
 760         if(SUCCEEDED(hres)) {
 761             DWORD k, a, b, bend;
 762
 763             for(k=2; k < length; k *= 2) {
 764                 for(i=0; i+k < length; i += 2*k) {
 765                     a = b = 0;
 766                     if(i+2*k <= length)
 767                         bend = k;
 768                     else
 769                         bend = length - (i+k);
 770
 771                     memcpy(tmpbuf, sorttab+i, k*sizeof(jsval_t*));
 772
 773                     while(a < k && b < bend) {
 774                         hres = sort_cmp(ctx, cmp_func, *tmpbuf[a], *sorttab[i+k+b], &cmp);
 775                         if(FAILED(hres))
 776                             break;
 777
 778                         if(cmp < 0) {
 779                             sorttab[i+a+b] = tmpbuf[a];
 780                             a++;
 781                         }else {
 782                             sorttab[i+a+b] = sorttab[i+k+b];
 783                             b++;
 784                         }
 785                     }
 786
 787                     if(FAILED(hres))
 788                         break;
 789
 790                     if(a < k)
 791                         memcpy(sorttab+i+a+b, tmpbuf+a, (k-a)*sizeof(jsval_t*));
 792                 }
 793
 794                 if(FAILED(hres))
 795                     break;
 796             }
 797         }
 798
 799         for(i=0; SUCCEEDED(hres) && i < length; i++)
 800             hres = jsdisp_propput_idx(jsthis, i, *sorttab[i]);
 801     }
 802
 803     if(vtab) {
 804         for(i=0; i < length; i++)
 805             jsval_release(vtab[i]);
 806         heap_free(vtab);
 807     }
 808     heap_free(sorttab);
 809     if(cmp_func)
 810         jsdisp_release(cmp_func);
 811
 812     if(FAILED(hres))
 813         return hres;
 814
 815     if(r)
 816         *r = jsval_obj(jsdisp_addref(jsthis));
 817     return S_OK;
 818 }
 819
 820 /* ECMA-262 3rd Edition    15.4.4.12 */
 821 static HRESULT Array_splice(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
 822         jsval_t *r)
 823 {
 824     DWORD length, start=0, delete_cnt=0, i, add_args = 0;
 825     jsdisp_t *ret_array = NULL, *jsthis;
 826     jsval_t val;
 827     double d;
 828     int n;
 829     HRESULT hres = S_OK;
 830
 831     TRACE("\n");
 832
 833     hres = get_length(ctx, vthis, &jsthis, &length);
 834     if(FAILED(hres))
 835         return hres;
 836
 837     if(argc) {
 838         hres = to_integer(ctx, argv[0], &d);
 839         if(FAILED(hres))
 840             return hres;
 841
 842         if(is_int32(d)) {
 843             if((n = d) >= 0)
 844                 start = min(n, length);
 845             else
 846                 start = -n > length ? 0 : length + n;
 847         }else {
 848             start = d < 0.0 ? 0 : length;
 849         }
 850     }
 851
 852     if(argc >= 2) {
 853         hres = to_integer(ctx, argv[1], &d);
 854         if(FAILED(hres))
 855             return hres;
 856
 857         if(is_int32(d)) {
 858             if((n = d) > 0)
 859                 delete_cnt = min(n, length-start);
 860         }else if(d > 0.0) {
 861             delete_cnt = length-start;
 862         }
 863
 864         add_args = argc-2;
 865     }
 866
 867     if(r) {
 868         hres = create_array(ctx, 0, &ret_array);
 869         if(FAILED(hres))
 870             return hres;
 871
 872         for(i=0; SUCCEEDED(hres) && i < delete_cnt; i++) {
 873             hres = jsdisp_get_idx(jsthis, start+i, &val);
 874             if(hres == DISP_E_UNKNOWNNAME) {
 875                 hres = S_OK;
 876             }else if(SUCCEEDED(hres)) {
 877                 hres = jsdisp_propput_idx(ret_array, i, val);
 878                 jsval_release(val);
 879             }
 880         }
 881
 882         if(SUCCEEDED(hres))
 883             hres = jsdisp_propput_name(ret_array, lengthW, jsval_number(delete_cnt));
 884     }
 885
 886     if(add_args < delete_cnt) {
 887         for(i = start; SUCCEEDED(hres) && i < length-delete_cnt; i++) {
 888             hres = jsdisp_get_idx(jsthis, i+delete_cnt, &val);
 889             if(hres == DISP_E_UNKNOWNNAME) {
 890                 hres = jsdisp_delete_idx(jsthis, i+add_args);
 891             }else if(SUCCEEDED(hres)) {
 892                 hres = jsdisp_propput_idx(jsthis, i+add_args, val);
 893                 jsval_release(val);
 894             }
 895         }
 896
 897         for(i=length; SUCCEEDED(hres) && i != length-delete_cnt+add_args; i--)
 898             hres = jsdisp_delete_idx(jsthis, i-1);
 899     }else if(add_args > delete_cnt) {
 900         for(i=length-delete_cnt; SUCCEEDED(hres) && i != start; i--) {
 901             hres = jsdisp_get_idx(jsthis, i+delete_cnt-1, &val);
 902             if(hres == DISP_E_UNKNOWNNAME) {
 903                 hres = jsdisp_delete_idx(jsthis, i+add_args-1);
 904             }else if(SUCCEEDED(hres)) {
 905                 hres = jsdisp_propput_idx(jsthis, i+add_args-1, val);
 906                 jsval_release(val);
 907             }
 908         }
 909     }
 910
 911     for(i=0; SUCCEEDED(hres) && i < add_args; i++)
 912         hres = jsdisp_propput_idx(jsthis, start+i, argv[i+2]);
 913
 914     if(SUCCEEDED(hres))
 915         hres = jsdisp_propput_name(jsthis, lengthW, jsval_number(length-delete_cnt+add_args));
 916
 917     if(FAILED(hres)) {
 918         if(ret_array)
 919             jsdisp_release(ret_array);
 920         return hres;
 921     }
 922
 923     if(r)
 924         *r = jsval_obj(ret_array);
 925     return S_OK;
 926 }
 927
 928 /* ECMA-262 3rd Edition    15.4.4.2 */
 929 static HRESULT Array_toString(script_ctx_t *ctx, vdisp_t *jsthis, WORD flags, unsigned argc, jsval_t *argv,
 930         jsval_t *r)
 931 {
 932     ArrayInstance *array;
 933
 934     TRACE("\n");
 935
 936     array = array_this(jsthis);
 937     if(!array)
 938         return throw_type_error(ctx, JS_E_ARRAY_EXPECTED, NULL);
 939
 940     return array_join(ctx, &array->dispex, array->length, default_separatorW,
 941                       strlenW(default_separatorW), r);
 942 }
 943
 944 static HRESULT Array_toLocaleString(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
 945         jsval_t *r)
 946 {
 947     FIXME("\n");
 948     return E_NOTIMPL;
 949 }
 950
 951 static HRESULT Array_forEach(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
 952         jsval_t *r)
 953 {
 954     jsval_t value, args[3], res;
 955     jsdisp_t *jsthis;
 956     unsigned length, i;
 957     HRESULT hres;
 958
 959     TRACE("\n");
 960
 961     /* FIXME: Check IsCallable */
 962     if(argc != 1 || !is_object_instance(argv[0])) {
 963         FIXME("Unsupported arguments\n");
 964         return E_NOTIMPL;
 965     }
 966
 967     hres = get_length(ctx, vthis, &jsthis, &length);
 968     if(FAILED(hres))
 969         return hres;
 970
 971     for(i = 0; i < length; i++) {
 972         hres = jsdisp_get_idx(jsthis, i, &value);
 973         if(hres == DISP_E_UNKNOWNNAME)
 974             continue;
 975         if(FAILED(hres))
 976             return hres;
 977
 978         args[0] = value;
 979         args[1] = jsval_number(i);
 980         args[2] = jsval_obj(jsthis);
 981         hres = disp_call_value(ctx, get_object(argv[0]), NULL, DISPATCH_METHOD, ARRAY_SIZE(args), args, &res);
 982         jsval_release(value);
 983         if(FAILED(hres))
 984             return hres;
 985         jsval_release(res);
 986     }
 987
 988     if(r) *r = jsval_undefined();
 989     return S_OK;
 990 }
 991
 992 static HRESULT Array_indexOf(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
 993         jsval_t *r)
 994 {
 995     jsdisp_t *jsthis;
 996     unsigned length, i, from = 0;
 997     jsval_t search, value;
 998     BOOL eq;
 999     HRESULT hres;
1000
1001     TRACE("\n");
1002
1003     hres = get_length(ctx, vthis, &jsthis, &length);
1004     if(FAILED(hres))
1005         return hres;
1006     if(!length) {
1007         if(r) *r = jsval_number(-1);
1008         return S_OK;
1009     }
1010
1011     search = argc ? argv[0] : jsval_undefined();
1012
1013     if(argc > 1) {
1014         double from_arg;
1015
1016         hres = to_integer(ctx, argv[1], &from_arg);
1017         if(FAILED(hres))
1018             return hres;
1019
1020         if(from_arg >= 0)
1021             from = min(from_arg, length);
1022         else
1023             from = max(from_arg + length, 0);
1024     }
1025
1026     for(i = from; i < length; i++) {
1027         hres = jsdisp_get_idx(jsthis, i, &value);
1028         if(hres == DISP_E_UNKNOWNNAME)
1029             continue;
1030         if(FAILED(hres))
1031             return hres;
1032
1033         hres = jsval_strict_equal(value, search, &eq);
1034         jsval_release(value);
1035         if(FAILED(hres))
1036             return hres;
1037         if(eq) {
1038             if(r) *r = jsval_number(i);
1039             return S_OK;
1040         }
1041     }
1042
1043     if(r) *r = jsval_number(-1);
1044     return S_OK;
1045 }
1046
1047 /* ECMA-262 3rd Edition    15.4.4.13 */
1048 static HRESULT Array_unshift(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
1049         jsval_t *r)
1050 {
1051     jsdisp_t *jsthis;
1052     WCHAR buf[14], *buf_end, *str;
1053     DWORD i, length;
1054     jsval_t val;
1055     DISPID id;
1056     HRESULT hres;
1057
1058     TRACE("\n");
1059
1060     hres = get_length(ctx, vthis, &jsthis, &length);
1061     if(FAILED(hres))
1062         return hres;
1063
1064     if(argc) {
1065         buf_end = buf + ARRAY_SIZE(buf)-1;
1066         *buf_end-- = 0;
1067         i = length;
1068
1069         while(i--) {
1070             str = idx_to_str(i, buf_end);
1071
1072             hres = jsdisp_get_id(jsthis, str, 0, &id);
1073             if(SUCCEEDED(hres)) {
1074                 hres = jsdisp_propget(jsthis, id, &val);
1075                 if(FAILED(hres))
1076                     return hres;
1077
1078                 hres = jsdisp_propput_idx(jsthis, i+argc, val);
1079                 jsval_release(val);
1080             }else if(hres == DISP_E_UNKNOWNNAME) {
1081                 hres = IDispatchEx_DeleteMemberByDispID(vthis->u.dispex, id);
1082             }
1083         }
1084
1085         if(FAILED(hres))
1086             return hres;
1087     }
1088
1089     for(i=0; i<argc; i++) {
1090         hres = jsdisp_propput_idx(jsthis, i, argv[i]);
1091         if(FAILED(hres))
1092             return hres;
1093     }
1094
1095     if(argc) {
1096         length += argc;
1097         hres = set_length(jsthis, length);
1098         if(FAILED(hres))
1099             return hres;
1100     }
1101
1102     if(r)
1103         *r = ctx->version < 2 ? jsval_undefined() : jsval_number(length);
1104     return S_OK;
1105 }
1106
1107 static HRESULT Array_get_value(script_ctx_t *ctx, jsdisp_t *jsthis, jsval_t *r)
1108 {
1109     ArrayInstance *array = array_from_jsdisp(jsthis);
1110
1111     TRACE("\n");
1112
1113     return array_join(ctx, &array->dispex, array->length, default_separatorW,
1114                       strlenW(default_separatorW), r);
1115 }
1116
1117 static void Array_destructor(jsdisp_t *dispex)
1118 {
1119     heap_free(dispex);
1120 }
1121
1122 static void Array_on_put(jsdisp_t *dispex, const WCHAR *name)
1123 {
1124     ArrayInstance *array = array_from_jsdisp(dispex);
1125     const WCHAR *ptr = name;
1126     DWORD id = 0;
1127
1128     if(!isdigitW(*ptr))
1129         return;
1130
1131     while(*ptr && isdigitW(*ptr)) {
1132         id = id*10 + (*ptr-'0');
1133         ptr++;
1134     }
1135
1136     if(*ptr)
1137         return;
1138
1139     if(id >= array->length)
1140         array->length = id+1;
1141 }
1142
1143 static const builtin_prop_t Array_props[] = {
1144     {concatW,                Array_concat,               PROPF_METHOD|1},
1145     {forEachW,               Array_forEach,              PROPF_METHOD|PROPF_ES5|1},
1146     {indexOfW,               Array_indexOf,              PROPF_METHOD|PROPF_ES5|1},
1147     {joinW,                  Array_join,                 PROPF_METHOD|1},
1148     {lengthW,                NULL,0,                     Array_get_length, Array_set_length},
1149     {popW,                   Array_pop,                  PROPF_METHOD},
1150     {pushW,                  Array_push,                 PROPF_METHOD|1},
1151     {reverseW,               Array_reverse,              PROPF_METHOD},
1152     {shiftW,                 Array_shift,                PROPF_METHOD},
1153     {sliceW,                 Array_slice,                PROPF_METHOD|2},
1154     {sortW,                  Array_sort,                 PROPF_METHOD|1},
1155     {spliceW,                Array_splice,               PROPF_METHOD|2},
1156     {toLocaleStringW,        Array_toLocaleString,       PROPF_METHOD},
1157     {toStringW,              Array_toString,             PROPF_METHOD},
1158     {unshiftW,               Array_unshift,              PROPF_METHOD|1},
1159 };
1160
1161 static const builtin_info_t Array_info = {
1162     JSCLASS_ARRAY,
1163     {NULL, NULL,0, Array_get_value},
1164     ARRAY_SIZE(Array_props),
1165     Array_props,
1166     Array_destructor,
1167     Array_on_put
1168 };
1169
1170 static const builtin_prop_t ArrayInst_props[] = {
1171     {lengthW,                NULL,0,                     Array_get_length, Array_set_length}
1172 };
1173
1174 static const builtin_info_t ArrayInst_info = {
1175     JSCLASS_ARRAY,
1176     {NULL, NULL,0, Array_get_value},
1177     ARRAY_SIZE(ArrayInst_props),
1178     ArrayInst_props,
1179     Array_destructor,
1180     Array_on_put
1181 };
1182
1183 /* ECMA-262 5.1 Edition    15.4.3.2 */
1184 static HRESULT ArrayConstr_isArray(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv, jsval_t *r)
1185 {
1186     jsdisp_t *obj;
1187
1188     TRACE("\n");
1189
1190     if(!argc || !is_object_instance(argv[0])) {
1191         if(r) *r = jsval_bool(FALSE);
1192         return S_OK;
1193     }
1194
1195     obj = iface_to_jsdisp(get_object(argv[0]));
1196     if(r) *r = jsval_bool(obj && is_class(obj, JSCLASS_ARRAY));
1197     if(obj) jsdisp_release(obj);
1198     return S_OK;
1199 }
1200
1201 static HRESULT ArrayConstr_value(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
1202         jsval_t *r)
1203 {
1204     jsdisp_t *obj;
1205     DWORD i;
1206     HRESULT hres;
1207
1208     TRACE("\n");
1209
1210     switch(flags) {
1211     case DISPATCH_METHOD:
1212     case DISPATCH_CONSTRUCT: {
1213         if(argc == 1 && is_number(argv[0])) {
1214             double n = get_number(argv[0]);
1215
1216             if(n < 0 || !is_int32(n))
1217                 return throw_range_error(ctx, JS_E_INVALID_LENGTH, NULL);
1218
1219             hres = create_array(ctx, n, &obj);
1220             if(FAILED(hres))
1221                 return hres;
1222
1223             *r = jsval_obj(obj);
1224             return S_OK;
1225         }
1226
1227         hres = create_array(ctx, argc, &obj);
1228         if(FAILED(hres))
1229             return hres;
1230
1231         for(i=0; i < argc; i++) {
1232             hres = jsdisp_propput_idx(obj, i, argv[i]);
1233             if(FAILED(hres))
1234                 break;
1235         }
1236         if(FAILED(hres)) {
1237             jsdisp_release(obj);
1238             return hres;
1239         }
1240
1241         *r = jsval_obj(obj);
1242         break;
1243     }
1244     default:
1245         FIXME("unimplemented flags: %x\n", flags);
1246         return E_NOTIMPL;
1247     }
1248
1249     return S_OK;
1250 }
1251
1252 static HRESULT alloc_array(script_ctx_t *ctx, jsdisp_t *object_prototype, ArrayInstance **ret)
1253 {
1254     ArrayInstance *array;
1255     HRESULT hres;
1256
1257     array = heap_alloc_zero(sizeof(ArrayInstance));
1258     if(!array)
1259         return E_OUTOFMEMORY;
1260
1261     if(object_prototype)
1262         hres = init_dispex(&array->dispex, ctx, &Array_info, object_prototype);
1263     else
1264         hres = init_dispex_from_constr(&array->dispex, ctx, &ArrayInst_info, ctx->array_constr);
1265
1266     if(FAILED(hres)) {
1267         heap_free(array);
1268         return hres;
1269     }
1270
1271     *ret = array;
1272     return S_OK;
1273 }
1274
1275 static const WCHAR isArrayW[] = {'i','s','A','r','r','a','y',0};
1276
1277 static const builtin_prop_t ArrayConstr_props[] = {
1278     {isArrayW,    ArrayConstr_isArray,    PROPF_ES5|PROPF_METHOD|1}
1279 };
1280
1281 static const builtin_info_t ArrayConstr_info = {
1282     JSCLASS_FUNCTION,
1283     DEFAULT_FUNCTION_VALUE,
1284     ARRAY_SIZE(ArrayConstr_props),
1285     ArrayConstr_props,
1286     NULL,
1287     NULL
1288 };
1289
1290 HRESULT create_array_constr(script_ctx_t *ctx, jsdisp_t *object_prototype, jsdisp_t **ret)
1291 {
1292     ArrayInstance *array;
1293     HRESULT hres;
1294
1295     static const WCHAR ArrayW[] = {'A','r','r','a','y',0};
1296
1297     hres = alloc_array(ctx, object_prototype, &array);
1298     if(FAILED(hres))
1299         return hres;
1300
1301     hres = create_builtin_constructor(ctx, ArrayConstr_value, ArrayW, &ArrayConstr_info, PROPF_CONSTR|1, &array->dispex, ret);
1302
1303     jsdisp_release(&array->dispex);
1304     return hres;
1305 }
1306
1307 HRESULT create_array(script_ctx_t *ctx, DWORD length, jsdisp_t **ret)
1308 {
1309     ArrayInstance *array;
1310     HRESULT hres;
1311
1312     hres = alloc_array(ctx, NULL, &array);
1313     if(FAILED(hres))
1314         return hres;
1315
1316     array->length = length;
1317
1318     *ret = &array->dispex;
1319     return S_OK;
1320 }