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