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