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 <math.h>
  20
  21 #include "jscript.h"
  22
  23 #include "wine/debug.h"
  24
  25 WINE_DEFAULT_DEBUG_CHANNEL(jscript);
  26
  27 typedef struct {
  28     DispatchEx dispex;
  29
  30     DWORD length;
  31 } ArrayInstance;
  32
  33 static const WCHAR lengthW[] = {'l','e','n','g','t','h',0};
  34 static const WCHAR concatW[] = {'c','o','n','c','a','t',0};
  35 static const WCHAR joinW[] = {'j','o','i','n',0};
  36 static const WCHAR popW[] = {'p','o','p',0};
  37 static const WCHAR pushW[] = {'p','u','s','h',0};
  38 static const WCHAR reverseW[] = {'r','e','v','e','r','s','e',0};
  39 static const WCHAR shiftW[] = {'s','h','i','f','t',0};
  40 static const WCHAR sliceW[] = {'s','l','i','c','e',0};
  41 static const WCHAR sortW[] = {'s','o','r','t',0};
  42 static const WCHAR spliceW[] = {'s','p','l','i','c','e',0};
  43 static const WCHAR toStringW[] = {'t','o','S','t','r','i','n','g',0};
  44 static const WCHAR toLocaleStringW[] = {'t','o','L','o','c','a','l','e','S','t','r','i','n','g',0};
  45 static const WCHAR unshiftW[] = {'u','n','s','h','i','f','t',0};
  46
  47 static const WCHAR default_separatorW[] = {',',0};
  48
  49 static HRESULT get_jsdisp_length(DispatchEx *obj, LCID lcid, jsexcept_t *ei, DWORD *ret)
  50 {
  51     VARIANT var;
  52     HRESULT hres;
  53
  54     hres = jsdisp_propget_name(obj, lengthW, lcid, &var, ei, NULL/*FIXME*/);
  55     if(FAILED(hres))
  56         return hres;
  57
  58     hres = to_uint32(obj->ctx, &var, ei, ret);
  59     VariantClear(&var);
  60     return hres;
  61 }
  62
  63 static HRESULT set_jsdisp_length(DispatchEx *obj, LCID lcid, jsexcept_t *ei, DWORD length)
  64 {
  65     VARIANT var;
  66
  67     V_VT(&var) = VT_I4;
  68     V_I4(&var) = length;
  69     return jsdisp_propput_name(obj, lengthW, lcid, &var, ei, NULL/*FIXME*/);
  70 }
  71
  72 static HRESULT Array_length(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
  73         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
  74 {
  75     ArrayInstance *This = (ArrayInstance*)dispex;
  76
  77     TRACE("%p %d\n", This, This->length);
  78
  79     switch(flags) {
  80     case DISPATCH_PROPERTYGET:
  81         V_VT(retv) = VT_I4;
  82         V_I4(retv) = This->length;
  83         break;
  84     case DISPATCH_PROPERTYPUT: {
  85         VARIANT num;
  86         DOUBLE len = -1;
  87         DWORD i;
  88         HRESULT hres;
  89
  90         hres = to_number(dispex->ctx, get_arg(dp, 0), ei, &num);
  91         if(V_VT(&num) == VT_I4)
  92             len = V_I4(&num);
  93         else
  94             len = floor(V_R8(&num));
  95
  96         if(len!=(DWORD)len)
  97             return throw_range_error(dispex->ctx, ei, IDS_INVALID_LENGTH, NULL);
  98
  99         for(i=len; i<This->length; i++) {
 100             hres = jsdisp_delete_idx(dispex, i);
 101             if(FAILED(hres))
 102                 return hres;
 103         }
 104
 105         This->length = len;
 106         break;
 107     }
 108     default:
 109         FIXME("unimplemented flags %x\n", flags);
 110         return E_NOTIMPL;
 111     }
 112
 113     return S_OK;
 114 }
 115
 116 static HRESULT concat_array(DispatchEx *array, ArrayInstance *obj, DWORD *len, LCID lcid,
 117         jsexcept_t *ei, IServiceProvider *caller)
 118 {
 119     VARIANT var;
 120     DWORD i;
 121     HRESULT hres;
 122
 123     for(i=0; i < obj->length; i++) {
 124         hres = jsdisp_propget_idx(&obj->dispex, i, lcid, &var, ei, caller);
 125         if(hres == DISP_E_UNKNOWNNAME)
 126             continue;
 127         if(FAILED(hres))
 128             return hres;
 129
 130         hres = jsdisp_propput_idx(array, *len+i, lcid, &var, ei, caller);
 131         VariantClear(&var);
 132         if(FAILED(hres))
 133             return hres;
 134     }
 135
 136     *len += obj->length;
 137     return S_OK;
 138 }
 139
 140 static HRESULT concat_obj(DispatchEx *array, IDispatch *obj, DWORD *len, LCID lcid, jsexcept_t *ei, IServiceProvider *caller)
 141 {
 142     DispatchEx *jsobj;
 143     VARIANT var;
 144     HRESULT hres;
 145
 146     jsobj = iface_to_jsdisp((IUnknown*)obj);
 147     if(jsobj) {
 148         if(is_class(jsobj, JSCLASS_ARRAY)) {
 149             hres = concat_array(array, (ArrayInstance*)jsobj, len, lcid, ei, caller);
 150             jsdisp_release(jsobj);
 151             return hres;
 152         }
 153         jsdisp_release(jsobj);
 154     }
 155
 156     V_VT(&var) = VT_DISPATCH;
 157     V_DISPATCH(&var) = obj;
 158     return jsdisp_propput_idx(array, (*len)++, lcid, &var, ei, caller);
 159 }
 160
 161 static HRESULT Array_concat(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 162         VARIANT *retv, jsexcept_t *ei, IServiceProvider *caller)
 163 {
 164     DispatchEx *ret;
 165     DWORD len = 0;
 166     HRESULT hres;
 167
 168     TRACE("\n");
 169
 170     hres = create_array(dispex->ctx, 0, &ret);
 171     if(FAILED(hres))
 172         return hres;
 173
 174     hres = concat_obj(ret, (IDispatch*)_IDispatchEx_(dispex), &len, lcid, ei, caller);
 175     if(SUCCEEDED(hres)) {
 176         VARIANT *arg;
 177         DWORD i;
 178
 179         for(i=0; i < arg_cnt(dp); i++) {
 180             arg = get_arg(dp, i);
 181             if(V_VT(arg) == VT_DISPATCH)
 182                 hres = concat_obj(ret, V_DISPATCH(arg), &len, lcid, ei, caller);
 183             else
 184                 hres = jsdisp_propput_idx(ret, len++, lcid, arg, ei, caller);
 185             if(FAILED(hres))
 186                 break;
 187         }
 188     }
 189
 190     if(FAILED(hres))
 191         return hres;
 192
 193     if(retv) {
 194         V_VT(retv) = VT_DISPATCH;
 195         V_DISPATCH(retv) = (IDispatch*)_IDispatchEx_(ret);
 196     }else {
 197         jsdisp_release(ret);
 198     }
 199     return S_OK;
 200 }
 201
 202 static HRESULT array_join(DispatchEx *array, LCID lcid, DWORD length, const WCHAR *sep, VARIANT *retv,
 203         jsexcept_t *ei, IServiceProvider *caller)
 204 {
 205     BSTR *str_tab, ret = NULL;
 206     VARIANT var;
 207     DWORD i;
 208     HRESULT hres = E_FAIL;
 209
 210     if(!length) {
 211         if(retv) {
 212             V_VT(retv) = VT_BSTR;
 213             V_BSTR(retv) = SysAllocStringLen(NULL, 0);
 214             if(!V_BSTR(retv))
 215                 return E_OUTOFMEMORY;
 216         }
 217         return S_OK;
 218     }
 219
 220     str_tab = heap_alloc_zero(length * sizeof(BSTR));
 221     if(!str_tab)
 222         return E_OUTOFMEMORY;
 223
 224     for(i=0; i < length; i++) {
 225         hres = jsdisp_propget_idx(array, i, lcid, &var, ei, caller);
 226         if(FAILED(hres))
 227             break;
 228
 229         if(V_VT(&var) != VT_EMPTY && V_VT(&var) != VT_NULL)
 230             hres = to_string(array->ctx, &var, ei, str_tab+i);
 231         VariantClear(&var);
 232         if(FAILED(hres))
 233             break;
 234     }
 235
 236     if(SUCCEEDED(hres)) {
 237         DWORD seplen = 0, len = 0;
 238         WCHAR *ptr;
 239
 240         seplen = strlenW(sep);
 241
 242         if(str_tab[0])
 243             len = SysStringLen(str_tab[0]);
 244         for(i=1; i < length; i++)
 245             len += seplen + SysStringLen(str_tab[i]);
 246
 247         ret = SysAllocStringLen(NULL, len);
 248         if(ret) {
 249             DWORD tmplen = 0;
 250
 251             if(str_tab[0]) {
 252                 tmplen = SysStringLen(str_tab[0]);
 253                 memcpy(ret, str_tab[0], tmplen*sizeof(WCHAR));
 254             }
 255
 256             ptr = ret + tmplen;
 257             for(i=1; i < length; i++) {
 258                 if(seplen) {
 259                     memcpy(ptr, sep, seplen*sizeof(WCHAR));
 260                     ptr += seplen;
 261                 }
 262
 263                 if(str_tab[i]) {
 264                     tmplen = SysStringLen(str_tab[i]);
 265                     memcpy(ptr, str_tab[i], tmplen*sizeof(WCHAR));
 266                     ptr += tmplen;
 267                 }
 268             }
 269             *ptr=0;
 270         }else {
 271             hres = E_OUTOFMEMORY;
 272         }
 273     }
 274
 275     for(i=0; i < length; i++)
 276         SysFreeString(str_tab[i]);
 277     heap_free(str_tab);
 278     if(FAILED(hres))
 279         return hres;
 280
 281     TRACE("= %s\n", debugstr_w(ret));
 282
 283     if(retv) {
 284         if(!ret) {
 285             ret = SysAllocStringLen(NULL, 0);
 286             if(!ret)
 287                 return E_OUTOFMEMORY;
 288         }
 289
 290         V_VT(retv) = VT_BSTR;
 291         V_BSTR(retv) = ret;
 292     }else {
 293         SysFreeString(ret);
 294     }
 295
 296     return S_OK;
 297 }
 298
 299 /* ECMA-262 3rd Edition    15.4.4.5 */
 300 static HRESULT Array_join(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 301         VARIANT *retv, jsexcept_t *ei, IServiceProvider *caller)
 302 {
 303     DWORD length;
 304     HRESULT hres;
 305
 306     TRACE("\n");
 307
 308     if(is_class(dispex, JSCLASS_ARRAY)) {
 309         length = ((ArrayInstance*)dispex)->length;
 310     }else {
 311         FIXME("dispid is not Array\n");
 312         return E_NOTIMPL;
 313     }
 314
 315     if(arg_cnt(dp)) {
 316         BSTR sep;
 317
 318         hres = to_string(dispex->ctx, dp->rgvarg + dp->cArgs-1, ei, &sep);
 319         if(FAILED(hres))
 320             return hres;
 321
 322         hres = array_join(dispex, lcid, length, sep, retv, ei, caller);
 323
 324         SysFreeString(sep);
 325     }else {
 326         hres = array_join(dispex, lcid, length, default_separatorW, retv, ei, caller);
 327     }
 328
 329     return hres;
 330 }
 331
 332 static HRESULT Array_pop(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 333         VARIANT *retv, jsexcept_t *ei, IServiceProvider *caller)
 334 {
 335     VARIANT val;
 336     DWORD length;
 337     WCHAR buf[14];
 338     DISPID id;
 339     HRESULT hres;
 340
 341     static const WCHAR formatW[] = {'%','d',0};
 342
 343     TRACE("\n");
 344
 345     if(is_class(dispex, JSCLASS_ARRAY)) {
 346         ArrayInstance *array = (ArrayInstance*)dispex;
 347         length = array->length;
 348     }else {
 349         FIXME("not Array this\n");
 350         return E_NOTIMPL;
 351     }
 352
 353     if(!length) {
 354         if(retv)
 355             V_VT(retv) = VT_EMPTY;
 356         return S_OK;
 357     }
 358
 359     sprintfW(buf, formatW, --length);
 360     hres = jsdisp_get_id(dispex, buf, 0, &id);
 361     if(SUCCEEDED(hres)) {
 362         hres = jsdisp_propget(dispex, id, lcid, &val, ei, caller);
 363         if(FAILED(hres))
 364             return hres;
 365
 366         hres = IDispatchEx_DeleteMemberByDispID(_IDispatchEx_(dispex), id);
 367     }else if(hres == DISP_E_UNKNOWNNAME) {
 368         V_VT(&val) = VT_EMPTY;
 369         hres = S_OK;
 370     }else {
 371         return hres;
 372     }
 373
 374     if(SUCCEEDED(hres)) {
 375         if(is_class(dispex, JSCLASS_ARRAY)) {
 376             ArrayInstance *array = (ArrayInstance*)dispex;
 377             array->length = length;
 378         }
 379     }
 380
 381     if(FAILED(hres)) {
 382         VariantClear(&val);
 383         return hres;
 384     }
 385
 386     if(retv)
 387         *retv = val;
 388     else
 389         VariantClear(&val);
 390     return S_OK;
 391 }
 392
 393 /* ECMA-262 3rd Edition    15.4.4.7 */
 394 static HRESULT Array_push(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 395         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 396 {
 397     DWORD length = 0;
 398     int i, n;
 399     HRESULT hres;
 400
 401     TRACE("\n");
 402
 403     if(dispex->builtin_info->class == JSCLASS_ARRAY) {
 404         length = ((ArrayInstance*)dispex)->length;
 405     }else {
 406         hres = get_jsdisp_length(dispex, lcid, ei, &length);
 407         if(FAILED(hres))
 408             return hres;
 409     }
 410
 411     n = arg_cnt(dp);
 412     for(i=0; i < n; i++) {
 413         hres = jsdisp_propput_idx(dispex, length+i, lcid, get_arg(dp, i), ei, sp);
 414         if(FAILED(hres))
 415             return hres;
 416     }
 417
 418     if(!is_class(dispex, JSCLASS_ARRAY)) {
 419         hres = set_jsdisp_length(dispex, lcid, ei, length+n);
 420         if(FAILED(hres))
 421             return hres;
 422     }
 423
 424     if(retv) {
 425         V_VT(retv) = VT_I4;
 426         V_I4(retv) = length+n;
 427     }
 428     return S_OK;
 429 }
 430
 431 static HRESULT Array_reverse(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 432         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 433 {
 434     FIXME("\n");
 435     return E_NOTIMPL;
 436 }
 437
 438 static HRESULT Array_shift(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 439         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 440 {
 441     FIXME("\n");
 442     return E_NOTIMPL;
 443 }
 444
 445 static HRESULT Array_slice(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 446         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 447 {
 448     DispatchEx *arr;
 449     VARIANT v;
 450     DOUBLE range;
 451     DWORD length, start, end, idx;
 452     HRESULT hres;
 453
 454     TRACE("\n");
 455
 456     if(is_class(dispex, JSCLASS_ARRAY)) {
 457         length = ((ArrayInstance*)dispex)->length;
 458     }else {
 459         FIXME("not Array this\n");
 460         return E_NOTIMPL;
 461     }
 462
 463     if(arg_cnt(dp)) {
 464         hres = to_number(dispex->ctx, get_arg(dp, 0), ei, &v);
 465         if(FAILED(hres))
 466             return hres;
 467
 468         if(V_VT(&v) == VT_I4)
 469             range = V_I4(&v);
 470         else
 471             range = floor(V_R8(&v));
 472
 473         if(-range>length || isnan(range)) start = 0;
 474         else if(range < 0) start = range+length;
 475         else if(range <= length) start = range;
 476         else start = length;
 477     }
 478     else start = 0;
 479
 480     if(arg_cnt(dp)>1) {
 481         hres = to_number(dispex->ctx, get_arg(dp, 1), ei, &v);
 482         if(FAILED(hres))
 483             return hres;
 484
 485         if(V_VT(&v) == VT_I4)
 486             range = V_I4(&v);
 487         else
 488             range = floor(V_R8(&v));
 489
 490         if(-range>length) end = 0;
 491         else if(range < 0) end = range+length;
 492         else if(range <= length) end = range;
 493         else end = length;
 494     }
 495     else end = length;
 496
 497     hres = create_array(dispex->ctx, (end>start)?end-start:0, &arr);
 498     if(FAILED(hres))
 499         return hres;
 500
 501     for(idx=start; idx<end; idx++) {
 502         hres = jsdisp_propget_idx(dispex, idx, lcid, &v, ei, sp);
 503         if(hres == DISP_E_UNKNOWNNAME)
 504             continue;
 505
 506         if(SUCCEEDED(hres))
 507             hres = jsdisp_propput_idx(arr, idx-start, lcid, &v, ei, sp);
 508
 509         if(FAILED(hres)) {
 510             jsdisp_release(arr);
 511             return hres;
 512         }
 513     }
 514
 515     if(retv) {
 516         V_VT(retv) = VT_DISPATCH;
 517         V_DISPATCH(retv) = (IDispatch*)_IDispatchEx_(arr);
 518     }
 519     else
 520         jsdisp_release(arr);
 521
 522     return S_OK;
 523 }
 524
 525 static HRESULT sort_cmp(script_ctx_t *ctx, DispatchEx *cmp_func, VARIANT *v1, VARIANT *v2, jsexcept_t *ei,
 526         IServiceProvider *caller, INT *cmp)
 527 {
 528     HRESULT hres;
 529
 530     if(cmp_func) {
 531         VARIANTARG args[2];
 532         DISPPARAMS dp = {args, NULL, 2, 0};
 533         VARIANT tmp;
 534         VARIANT res;
 535
 536         args[0] = *v2;
 537         args[1] = *v1;
 538
 539         hres = jsdisp_call_value(cmp_func, ctx->lcid, DISPATCH_METHOD, &dp, &res, ei, caller);
 540         if(FAILED(hres))
 541             return hres;
 542
 543         hres = to_number(ctx, &res, ei, &tmp);
 544         VariantClear(&res);
 545         if(FAILED(hres))
 546             return hres;
 547
 548         if(V_VT(&tmp) == VT_I4)
 549             *cmp = V_I4(&tmp);
 550         else
 551             *cmp = V_R8(&tmp) > 0.0 ? 1 : -1;
 552     }else if(is_num_vt(V_VT(v1))) {
 553         if(is_num_vt(V_VT(v2))) {
 554             DOUBLE d = num_val(v1)-num_val(v2);
 555             if(d > 0.0)
 556                 *cmp = 1;
 557             else if(d < -0.0)
 558                 *cmp = -1;
 559             else
 560                 *cmp = 0;
 561         }else {
 562             *cmp = -1;
 563         }
 564     }else if(is_num_vt(V_VT(v2))) {
 565         *cmp = 1;
 566     }else if(V_VT(v1) == VT_BSTR) {
 567         if(V_VT(v2) == VT_BSTR)
 568             *cmp = strcmpW(V_BSTR(v1), V_BSTR(v2));
 569         else
 570             *cmp = -1;
 571     }else if(V_VT(v2) == VT_BSTR) {
 572         *cmp = 1;
 573     }else {
 574         *cmp = 0;
 575     }
 576
 577     return S_OK;
 578 }
 579
 580 /* ECMA-262 3rd Edition    15.4.4.11 */
 581 static HRESULT Array_sort(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 582         VARIANT *retv, jsexcept_t *ei, IServiceProvider *caller)
 583 {
 584     DispatchEx *cmp_func = NULL;
 585     VARIANT *vtab, **sorttab = NULL;
 586     DWORD length;
 587     DWORD i;
 588     HRESULT hres = S_OK;
 589
 590     TRACE("\n");
 591
 592     if(is_class(dispex, JSCLASS_ARRAY)) {
 593         length = ((ArrayInstance*)dispex)->length;
 594     }else {
 595         FIXME("unsupported this not array\n");
 596         return E_NOTIMPL;
 597     }
 598
 599     if(arg_cnt(dp) > 1) {
 600         WARN("invalid arg_cnt %d\n", arg_cnt(dp));
 601         return E_FAIL;
 602     }
 603
 604     if(arg_cnt(dp) == 1) {
 605         VARIANT *arg = get_arg(dp, 0);
 606
 607         if(V_VT(arg) != VT_DISPATCH) {
 608             WARN("arg is not dispatch\n");
 609             return E_FAIL;
 610         }
 611
 612
 613         cmp_func = iface_to_jsdisp((IUnknown*)V_DISPATCH(arg));
 614         if(!cmp_func || !is_class(cmp_func, JSCLASS_FUNCTION)) {
 615             WARN("cmp_func is not a function\n");
 616             if(cmp_func)
 617                 jsdisp_release(cmp_func);
 618             return E_FAIL;
 619         }
 620     }
 621
 622     if(!length) {
 623         if(cmp_func)
 624             jsdisp_release(cmp_func);
 625         if(retv) {
 626             V_VT(retv) = VT_DISPATCH;
 627             V_DISPATCH(retv) = (IDispatch*)_IDispatchEx_(dispex);
 628             IDispatchEx_AddRef(_IDispatchEx_(dispex));
 629         }
 630         return S_OK;
 631     }
 632
 633     vtab = heap_alloc_zero(length * sizeof(VARIANT));
 634     if(vtab) {
 635         for(i=0; i<length; i++) {
 636             hres = jsdisp_propget_idx(dispex, i, lcid, vtab+i, ei, caller);
 637             if(FAILED(hres) && hres != DISP_E_UNKNOWNNAME) {
 638                 WARN("Could not get elem %d: %08x\n", i, hres);
 639                 break;
 640             }
 641         }
 642     }else {
 643         hres = E_OUTOFMEMORY;
 644     }
 645
 646     if(SUCCEEDED(hres)) {
 647         sorttab = heap_alloc(length*2*sizeof(VARIANT*));
 648         if(!sorttab)
 649             hres = E_OUTOFMEMORY;
 650     }
 651
 652     /* merge-sort */
 653     if(SUCCEEDED(hres)) {
 654         VARIANT *tmpv, **tmpbuf;
 655         INT cmp;
 656
 657         tmpbuf = sorttab + length;
 658         for(i=0; i < length; i++)
 659             sorttab[i] = vtab+i;
 660
 661         for(i=0; i < length/2; i++) {
 662             hres = sort_cmp(dispex->ctx, cmp_func, sorttab[2*i+1], sorttab[2*i], ei, caller, &cmp);
 663             if(FAILED(hres))
 664                 break;
 665
 666             if(cmp < 0) {
 667                 tmpv = sorttab[2*i];
 668                 sorttab[2*i] = sorttab[2*i+1];
 669                 sorttab[2*i+1] = tmpv;
 670             }
 671         }
 672
 673         if(SUCCEEDED(hres)) {
 674             DWORD k, a, b, bend;
 675
 676             for(k=2; k < length; k *= 2) {
 677                 for(i=0; i+k < length; i += 2*k) {
 678                     a = b = 0;
 679                     if(i+2*k <= length)
 680                         bend = k;
 681                     else
 682                         bend = length - (i+k);
 683
 684                     memcpy(tmpbuf, sorttab+i, k*sizeof(VARIANT*));
 685
 686                     while(a < k && b < bend) {
 687                         hres = sort_cmp(dispex->ctx, cmp_func, tmpbuf[a], sorttab[i+k+b], ei, caller, &cmp);
 688                         if(FAILED(hres))
 689                             break;
 690
 691                         if(cmp < 0) {
 692                             sorttab[i+a+b] = tmpbuf[a];
 693                             a++;
 694                         }else {
 695                             sorttab[i+a+b] = sorttab[i+k+b];
 696                             b++;
 697                         }
 698                     }
 699
 700                     if(FAILED(hres))
 701                         break;
 702
 703                     if(a < k)
 704                         memcpy(sorttab+i+a+b, tmpbuf+a, (k-a)*sizeof(VARIANT*));
 705                 }
 706
 707                 if(FAILED(hres))
 708                     break;
 709             }
 710         }
 711
 712         for(i=0; SUCCEEDED(hres) && i < length; i++)
 713             hres = jsdisp_propput_idx(dispex, i, lcid, sorttab[i], ei, caller);
 714     }
 715
 716     if(vtab) {
 717         for(i=0; i < length; i++)
 718             VariantClear(vtab+i);
 719         heap_free(vtab);
 720     }
 721     heap_free(sorttab);
 722     if(cmp_func)
 723         jsdisp_release(cmp_func);
 724
 725     if(FAILED(hres))
 726         return hres;
 727
 728     if(retv) {
 729         V_VT(retv) = VT_DISPATCH;
 730         V_DISPATCH(retv) = (IDispatch*)_IDispatchEx_(dispex);
 731         IDispatch_AddRef(_IDispatchEx_(dispex));
 732     }
 733
 734     return S_OK;
 735 }
 736
 737 static HRESULT Array_splice(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 738         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 739 {
 740     FIXME("\n");
 741     return E_NOTIMPL;
 742 }
 743
 744 /* ECMA-262 3rd Edition    15.4.4.2 */
 745 static HRESULT Array_toString(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 746         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 747 {
 748     TRACE("\n");
 749
 750     if(!is_class(dispex, JSCLASS_ARRAY)) {
 751         WARN("not Array object\n");
 752         return E_FAIL;
 753     }
 754
 755     return array_join(dispex, lcid, ((ArrayInstance*)dispex)->length, default_separatorW, retv, ei, sp);
 756 }
 757
 758 static HRESULT Array_toLocaleString(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 759         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 760 {
 761     FIXME("\n");
 762     return E_NOTIMPL;
 763 }
 764
 765 static HRESULT Array_unshift(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 766         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 767 {
 768     FIXME("\n");
 769     return E_NOTIMPL;
 770 }
 771
 772 static HRESULT Array_value(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 773         VARIANT *retv, jsexcept_t *ei, IServiceProvider *sp)
 774 {
 775     TRACE("\n");
 776
 777     switch(flags) {
 778     case INVOKE_FUNC:
 779         return throw_type_error(dispex->ctx, ei, IDS_NOT_FUNC, NULL);
 780     case INVOKE_PROPERTYGET:
 781         return array_join(dispex, lcid, ((ArrayInstance*)dispex)->length, default_separatorW, retv, ei, sp);
 782     default:
 783         FIXME("unimplemented flags %x\n", flags);
 784         return E_NOTIMPL;
 785     }
 786
 787     return S_OK;
 788 }
 789
 790 static void Array_destructor(DispatchEx *dispex)
 791 {
 792     heap_free(dispex);
 793 }
 794
 795 static void Array_on_put(DispatchEx *dispex, const WCHAR *name)
 796 {
 797     ArrayInstance *array = (ArrayInstance*)dispex;
 798     const WCHAR *ptr = name;
 799     DWORD id = 0;
 800
 801     if(!isdigitW(*ptr))
 802         return;
 803
 804     while(*ptr && isdigitW(*ptr)) {
 805         id = id*10 + (*ptr-'0');
 806         ptr++;
 807     }
 808
 809     if(*ptr)
 810         return;
 811
 812     if(id >= array->length)
 813         array->length = id+1;
 814 }
 815
 816 static const builtin_prop_t Array_props[] = {
 817     {concatW,                Array_concat,               PROPF_METHOD|1},
 818     {joinW,                  Array_join,                 PROPF_METHOD|1},
 819     {lengthW,                Array_length,               0},
 820     {popW,                   Array_pop,                  PROPF_METHOD},
 821     {pushW,                  Array_push,                 PROPF_METHOD|1},
 822     {reverseW,               Array_reverse,              PROPF_METHOD},
 823     {shiftW,                 Array_shift,                PROPF_METHOD},
 824     {sliceW,                 Array_slice,                PROPF_METHOD|2},
 825     {sortW,                  Array_sort,                 PROPF_METHOD|1},
 826     {spliceW,                Array_splice,               PROPF_METHOD|2},
 827     {toLocaleStringW,        Array_toLocaleString,       PROPF_METHOD},
 828     {toStringW,              Array_toString,             PROPF_METHOD},
 829     {unshiftW,               Array_unshift,              PROPF_METHOD|1},
 830 };
 831
 832 static const builtin_info_t Array_info = {
 833     JSCLASS_ARRAY,
 834     {NULL, Array_value, 0},
 835     sizeof(Array_props)/sizeof(*Array_props),
 836     Array_props,
 837     Array_destructor,
 838     Array_on_put
 839 };
 840
 841 static HRESULT ArrayConstr_value(DispatchEx *dispex, LCID lcid, WORD flags, DISPPARAMS *dp,
 842         VARIANT *retv, jsexcept_t *ei, IServiceProvider *caller)
 843 {
 844     DispatchEx *obj;
 845     VARIANT *arg_var;
 846     DWORD i;
 847     HRESULT hres;
 848
 849     TRACE("\n");
 850
 851     switch(flags) {
 852     case DISPATCH_METHOD:
 853     case DISPATCH_CONSTRUCT: {
 854         if(arg_cnt(dp) == 1 && V_VT((arg_var = get_arg(dp, 0))) == VT_I4) {
 855             if(V_I4(arg_var) < 0)
 856                 return throw_range_error(dispex->ctx, ei, IDS_INVALID_LENGTH, NULL);
 857
 858             hres = create_array(dispex->ctx, V_I4(arg_var), &obj);
 859             if(FAILED(hres))
 860                 return hres;
 861
 862             V_VT(retv) = VT_DISPATCH;
 863             V_DISPATCH(retv) = (IDispatch*)_IDispatchEx_(obj);
 864             return S_OK;
 865         }
 866
 867         hres = create_array(dispex->ctx, arg_cnt(dp), &obj);
 868         if(FAILED(hres))
 869             return hres;
 870
 871         for(i=0; i < arg_cnt(dp); i++) {
 872             hres = jsdisp_propput_idx(obj, i, lcid, get_arg(dp, i), ei, caller);
 873             if(FAILED(hres))
 874                 break;
 875         }
 876         if(FAILED(hres)) {
 877             jsdisp_release(obj);
 878             return hres;
 879         }
 880
 881         V_VT(retv) = VT_DISPATCH;
 882         V_DISPATCH(retv) = (IDispatch*)_IDispatchEx_(obj);
 883         break;
 884     }
 885     default:
 886         FIXME("unimplemented flags: %x\n", flags);
 887         return E_NOTIMPL;
 888     }
 889
 890     return S_OK;
 891 }
 892
 893 static HRESULT alloc_array(script_ctx_t *ctx, DispatchEx *object_prototype, ArrayInstance **ret)
 894 {
 895     ArrayInstance *array;
 896     HRESULT hres;
 897
 898     array = heap_alloc_zero(sizeof(ArrayInstance));
 899     if(!array)
 900         return E_OUTOFMEMORY;
 901
 902     if(object_prototype)
 903         hres = init_dispex(&array->dispex, ctx, &Array_info, object_prototype);
 904     else
 905         hres = init_dispex_from_constr(&array->dispex, ctx, &Array_info, ctx->array_constr);
 906
 907     if(FAILED(hres)) {
 908         heap_free(array);
 909         return hres;
 910     }
 911
 912     *ret = array;
 913     return S_OK;
 914 }
 915
 916 HRESULT create_array_constr(script_ctx_t *ctx, DispatchEx *object_prototype, DispatchEx **ret)
 917 {
 918     ArrayInstance *array;
 919     HRESULT hres;
 920
 921     hres = alloc_array(ctx, object_prototype, &array);
 922     if(FAILED(hres))
 923         return hres;
 924
 925     hres = create_builtin_function(ctx, ArrayConstr_value, NULL, PROPF_CONSTR, &array->dispex, ret);
 926
 927     IDispatchEx_Release(_IDispatchEx_(&array->dispex));
 928     return hres;
 929 }
 930
 931 HRESULT create_array(script_ctx_t *ctx, DWORD length, DispatchEx **ret)
 932 {
 933     ArrayInstance *array;
 934     HRESULT hres;
 935
 936     hres = alloc_array(ctx, NULL, &array);
 937     if(FAILED(hres))
 938         return hres;
 939
 940     array->length = length;
 941
 942     *ret = &array->dispex;
 943     return S_OK;
 944 }