dlls/jscript/array.c

   1 /*
   2  * Copyright 2008 Jacek Caban for CodeWeavers
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  17  */
  18
  19 #include "config.h"
  20 #include "wine/port.h"
  21
  22 #include <math.h>
  23 #include <assert.h>
  24
  25 #include "jscript.h"
  26
  27 #include "wine/debug.h"
  28
  29 WINE_DEFAULT_DEBUG_CHANNEL(jscript);
  30
  31 typedef struct {
  32     jsdisp_t dispex;
  33
  34     DWORD length;
  35 } ArrayInstance;
  36
  37 static const WCHAR lengthW[] = {'l','e','n','g','t','h',0};
  38 static const WCHAR concatW[] = {'c','o','n','c','a','t',0};
  39 static const WCHAR joinW[] = {'j','o','i','n',0};
  40 static const WCHAR popW[] = {'p','o','p',0};
  41 static const WCHAR pushW[] = {'p','u','s','h',0};
  42 static const WCHAR reverseW[] = {'r','e','v','e','r','s','e',0};
  43 static const WCHAR shiftW[] = {'s','h','i','f','t',0};
  44 static const WCHAR sliceW[] = {'s','l','i','c','e',0};
  45 static const WCHAR sortW[] = {'s','o','r','t',0};
  46 static const WCHAR spliceW[] = {'s','p','l','i','c','e',0};
  47 static const WCHAR toStringW[] = {'t','o','S','t','r','i','n','g',0};
  48 static const WCHAR toLocaleStringW[] = {'t','o','L','o','c','a','l','e','S','t','r','i','n','g',0};
  49 static const WCHAR unshiftW[] = {'u','n','s','h','i','f','t',0};
  50 static const WCHAR indexOfW[] = {'i','n','d','e','x','O','f',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 throw_type_error(ctx, JS_E_JSCRIPT_EXPECTED, NULL);
  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 throw_range_error(ctx, JS_E_INVALID_LENGTH, NULL);
 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, strlenW(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 throw_type_error(ctx, JS_E_ARRAY_EXPECTED, NULL);
 938
 939     return array_join(ctx, &array->dispex, array->length, default_separatorW,
 940                       strlenW(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_indexOf(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
 951         jsval_t *r)
 952 {
 953     jsdisp_t *jsthis;
 954     unsigned length, i, from = 0;
 955     jsval_t search, value;
 956     BOOL eq;
 957     HRESULT hres;
 958
 959     TRACE("\n");
 960
 961     hres = get_length(ctx, vthis, &jsthis, &length);
 962     if(FAILED(hres))
 963         return hres;
 964     if(!length) {
 965         if(r) *r = jsval_number(-1);
 966         return S_OK;
 967     }
 968
 969     search = argc ? argv[0] : jsval_undefined();
 970
 971     if(argc > 1) {
 972         double from_arg;
 973
 974         hres = to_integer(ctx, argv[1], &from_arg);
 975         if(FAILED(hres))
 976             return hres;
 977
 978         if(from_arg >= 0)
 979             from = min(from_arg, length);
 980         else
 981             from = max(from_arg + length, 0);
 982     }
 983
 984     for(i = from; i < length; i++) {
 985         hres = jsdisp_get_idx(jsthis, i, &value);
 986         if(hres == DISP_E_UNKNOWNNAME)
 987             continue;
 988         if(FAILED(hres))
 989             return hres;
 990
 991         hres = jsval_strict_equal(value, search, &eq);
 992         jsval_release(value);
 993         if(FAILED(hres))
 994             return hres;
 995         if(eq) {
 996             if(r) *r = jsval_number(i);
 997             return S_OK;
 998         }
 999     }
1000
1001     if(r) *r = jsval_number(-1);
1002     return S_OK;
1003 }
1004
1005 /* ECMA-262 3rd Edition    15.4.4.13 */
1006 static HRESULT Array_unshift(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
1007         jsval_t *r)
1008 {
1009     jsdisp_t *jsthis;
1010     WCHAR buf[14], *buf_end, *str;
1011     DWORD i, length;
1012     jsval_t val;
1013     DISPID id;
1014     HRESULT hres;
1015
1016     TRACE("\n");
1017
1018     hres = get_length(ctx, vthis, &jsthis, &length);
1019     if(FAILED(hres))
1020         return hres;
1021
1022     if(argc) {
1023         buf_end = buf + ARRAY_SIZE(buf)-1;
1024         *buf_end-- = 0;
1025         i = length;
1026
1027         while(i--) {
1028             str = idx_to_str(i, buf_end);
1029
1030             hres = jsdisp_get_id(jsthis, str, 0, &id);
1031             if(SUCCEEDED(hres)) {
1032                 hres = jsdisp_propget(jsthis, id, &val);
1033                 if(FAILED(hres))
1034                     return hres;
1035
1036                 hres = jsdisp_propput_idx(jsthis, i+argc, val);
1037                 jsval_release(val);
1038             }else if(hres == DISP_E_UNKNOWNNAME) {
1039                 hres = IDispatchEx_DeleteMemberByDispID(vthis->u.dispex, id);
1040             }
1041         }
1042
1043         if(FAILED(hres))
1044             return hres;
1045     }
1046
1047     for(i=0; i<argc; i++) {
1048         hres = jsdisp_propput_idx(jsthis, i, argv[i]);
1049         if(FAILED(hres))
1050             return hres;
1051     }
1052
1053     if(argc) {
1054         length += argc;
1055         hres = set_length(jsthis, length);
1056         if(FAILED(hres))
1057             return hres;
1058     }
1059
1060     if(r)
1061         *r = ctx->version < 2 ? jsval_undefined() : jsval_number(length);
1062     return S_OK;
1063 }
1064
1065 static HRESULT Array_get_value(script_ctx_t *ctx, jsdisp_t *jsthis, jsval_t *r)
1066 {
1067     ArrayInstance *array = array_from_jsdisp(jsthis);
1068
1069     TRACE("\n");
1070
1071     return array_join(ctx, &array->dispex, array->length, default_separatorW,
1072                       strlenW(default_separatorW), r);
1073 }
1074
1075 static void Array_destructor(jsdisp_t *dispex)
1076 {
1077     heap_free(dispex);
1078 }
1079
1080 static void Array_on_put(jsdisp_t *dispex, const WCHAR *name)
1081 {
1082     ArrayInstance *array = array_from_jsdisp(dispex);
1083     const WCHAR *ptr = name;
1084     DWORD id = 0;
1085
1086     if(!isdigitW(*ptr))
1087         return;
1088
1089     while(*ptr && isdigitW(*ptr)) {
1090         id = id*10 + (*ptr-'0');
1091         ptr++;
1092     }
1093
1094     if(*ptr)
1095         return;
1096
1097     if(id >= array->length)
1098         array->length = id+1;
1099 }
1100
1101 static const builtin_prop_t Array_props[] = {
1102     {concatW,                Array_concat,               PROPF_METHOD|1},
1103     {indexOfW,               Array_indexOf,              PROPF_ES5|PROPF_METHOD|1},
1104     {joinW,                  Array_join,                 PROPF_METHOD|1},
1105     {lengthW,                NULL,0,                     Array_get_length, Array_set_length},
1106     {popW,                   Array_pop,                  PROPF_METHOD},
1107     {pushW,                  Array_push,                 PROPF_METHOD|1},
1108     {reverseW,               Array_reverse,              PROPF_METHOD},
1109     {shiftW,                 Array_shift,                PROPF_METHOD},
1110     {sliceW,                 Array_slice,                PROPF_METHOD|2},
1111     {sortW,                  Array_sort,                 PROPF_METHOD|1},
1112     {spliceW,                Array_splice,               PROPF_METHOD|2},
1113     {toLocaleStringW,        Array_toLocaleString,       PROPF_METHOD},
1114     {toStringW,              Array_toString,             PROPF_METHOD},
1115     {unshiftW,               Array_unshift,              PROPF_METHOD|1},
1116 };
1117
1118 static const builtin_info_t Array_info = {
1119     JSCLASS_ARRAY,
1120     {NULL, NULL,0, Array_get_value},
1121     ARRAY_SIZE(Array_props),
1122     Array_props,
1123     Array_destructor,
1124     Array_on_put
1125 };
1126
1127 static const builtin_prop_t ArrayInst_props[] = {
1128     {lengthW,                NULL,0,                     Array_get_length, Array_set_length}
1129 };
1130
1131 static const builtin_info_t ArrayInst_info = {
1132     JSCLASS_ARRAY,
1133     {NULL, NULL,0, Array_get_value},
1134     ARRAY_SIZE(ArrayInst_props),
1135     ArrayInst_props,
1136     Array_destructor,
1137     Array_on_put
1138 };
1139
1140 /* ECMA-262 5.1 Edition    15.4.3.2 */
1141 static HRESULT ArrayConstr_isArray(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv, jsval_t *r)
1142 {
1143     jsdisp_t *obj;
1144
1145     TRACE("\n");
1146
1147     if(!argc || !is_object_instance(argv[0])) {
1148         if(r) *r = jsval_bool(FALSE);
1149         return S_OK;
1150     }
1151
1152     obj = iface_to_jsdisp(get_object(argv[0]));
1153     if(r) *r = jsval_bool(obj && is_class(obj, JSCLASS_ARRAY));
1154     if(obj) jsdisp_release(obj);
1155     return S_OK;
1156 }
1157
1158 static HRESULT ArrayConstr_value(script_ctx_t *ctx, vdisp_t *vthis, WORD flags, unsigned argc, jsval_t *argv,
1159         jsval_t *r)
1160 {
1161     jsdisp_t *obj;
1162     DWORD i;
1163     HRESULT hres;
1164
1165     TRACE("\n");
1166
1167     switch(flags) {
1168     case DISPATCH_METHOD:
1169     case DISPATCH_CONSTRUCT: {
1170         if(argc == 1 && is_number(argv[0])) {
1171             double n = get_number(argv[0]);
1172
1173             if(n < 0 || !is_int32(n))
1174                 return throw_range_error(ctx, JS_E_INVALID_LENGTH, NULL);
1175
1176             hres = create_array(ctx, n, &obj);
1177             if(FAILED(hres))
1178                 return hres;
1179
1180             *r = jsval_obj(obj);
1181             return S_OK;
1182         }
1183
1184         hres = create_array(ctx, argc, &obj);
1185         if(FAILED(hres))
1186             return hres;
1187
1188         for(i=0; i < argc; i++) {
1189             hres = jsdisp_propput_idx(obj, i, argv[i]);
1190             if(FAILED(hres))
1191                 break;
1192         }
1193         if(FAILED(hres)) {
1194             jsdisp_release(obj);
1195             return hres;
1196         }
1197
1198         *r = jsval_obj(obj);
1199         break;
1200     }
1201     default:
1202         FIXME("unimplemented flags: %x\n", flags);
1203         return E_NOTIMPL;
1204     }
1205
1206     return S_OK;
1207 }
1208
1209 static HRESULT alloc_array(script_ctx_t *ctx, jsdisp_t *object_prototype, ArrayInstance **ret)
1210 {
1211     ArrayInstance *array;
1212     HRESULT hres;
1213
1214     array = heap_alloc_zero(sizeof(ArrayInstance));
1215     if(!array)
1216         return E_OUTOFMEMORY;
1217
1218     if(object_prototype)
1219         hres = init_dispex(&array->dispex, ctx, &Array_info, object_prototype);
1220     else
1221         hres = init_dispex_from_constr(&array->dispex, ctx, &ArrayInst_info, ctx->array_constr);
1222
1223     if(FAILED(hres)) {
1224         heap_free(array);
1225         return hres;
1226     }
1227
1228     *ret = array;
1229     return S_OK;
1230 }
1231
1232 static const WCHAR isArrayW[] = {'i','s','A','r','r','a','y',0};
1233
1234 static const builtin_prop_t ArrayConstr_props[] = {
1235     {isArrayW,    ArrayConstr_isArray,    PROPF_ES5|PROPF_METHOD|1}
1236 };
1237
1238 static const builtin_info_t ArrayConstr_info = {
1239     JSCLASS_FUNCTION,
1240     DEFAULT_FUNCTION_VALUE,
1241     ARRAY_SIZE(ArrayConstr_props),
1242     ArrayConstr_props,
1243     NULL,
1244     NULL
1245 };
1246
1247 HRESULT create_array_constr(script_ctx_t *ctx, jsdisp_t *object_prototype, jsdisp_t **ret)
1248 {
1249     ArrayInstance *array;
1250     HRESULT hres;
1251
1252     static const WCHAR ArrayW[] = {'A','r','r','a','y',0};
1253
1254     hres = alloc_array(ctx, object_prototype, &array);
1255     if(FAILED(hres))
1256         return hres;
1257
1258     hres = create_builtin_constructor(ctx, ArrayConstr_value, ArrayW, &ArrayConstr_info, PROPF_CONSTR|1, &array->dispex, ret);
1259
1260     jsdisp_release(&array->dispex);
1261     return hres;
1262 }
1263
1264 HRESULT create_array(script_ctx_t *ctx, DWORD length, jsdisp_t **ret)
1265 {
1266     ArrayInstance *array;
1267     HRESULT hres;
1268
1269     hres = alloc_array(ctx, NULL, &array);
1270     if(FAILED(hres))
1271         return hres;
1272
1273     array->length = length;
1274
1275     *ret = &array->dispex;
1276     return S_OK;
1277 }