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