dlls/jscript/set.c

   1 /*
   2  * Copyright 2021 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 <assert.h>
  20 #include <math.h>
  21
  22 #include "jscript.h"
  23
  24 #include "wine/rbtree.h"
  25 #include "wine/debug.h"
  26
  27 WINE_DEFAULT_DEBUG_CHANNEL(jscript);
  28
  29 typedef struct {
  30     jsdisp_t dispex;
  31     struct wine_rb_tree map;
  32     struct list entries;
  33     size_t size;
  34 } MapInstance;
  35
  36 struct jsval_map_entry {
  37     struct wine_rb_entry entry;
  38     jsval_t key;
  39     jsval_t value;
  40
  41     /*
  42      * We need to maintain a list as well to support traversal in forEach.
  43      * If the entry is removed while being processed by forEach, it's
  44      * still kept in the list and released later, when it's safe.
  45      */
  46     struct list list_entry;
  47     unsigned int ref;
  48     BOOL deleted;
  49 };
  50
  51 static int jsval_map_compare(const void *k, const struct wine_rb_entry *e)
  52 {
  53     const struct jsval_map_entry *entry = WINE_RB_ENTRY_VALUE(e, const struct jsval_map_entry, entry);
  54     const jsval_t *key = k;
  55     union {
  56         double d;
  57         INT64 n;
  58     } bits1, bits2;
  59
  60     if(jsval_type(entry->key) != jsval_type(*key))
  61         return (int)jsval_type(entry->key) - (int)jsval_type(*key);
  62
  63     switch(jsval_type(*key)) {
  64     case JSV_UNDEFINED:
  65     case JSV_NULL:
  66         return 0;
  67     case JSV_OBJECT:
  68         if(get_object(*key) == get_object(entry->key)) return 0;
  69         return get_object(*key) < get_object(entry->key) ? -1 : 1;
  70     case JSV_STRING:
  71         return jsstr_cmp(get_string(*key), get_string(entry->key));
  72     case JSV_NUMBER:
  73         if(isnan(get_number(*key))) return isnan(get_number(entry->key)) ? 0 : -1;
  74         if(isnan(get_number(entry->key))) return 1;
  75
  76         /* native treats -0 differently than 0, so need to compare bitwise */
  77         bits1.d = get_number(*key);
  78         bits2.d = get_number(entry->key);
  79         return (bits1.n == bits2.n) ? 0 : (bits1.n < bits2.n ? -1 : 1);
  80     case JSV_BOOL:
  81         if(get_bool(*key) == get_bool(entry->key)) return 0;
  82         return get_bool(*key) ? 1 : -1;
  83     default:
  84         assert(0);
  85         return 0;
  86     }
  87 }
  88
  89 static HRESULT get_map_this(script_ctx_t *ctx, jsval_t vthis, MapInstance **ret)
  90 {
  91     jsdisp_t *jsdisp;
  92
  93     if(!is_object_instance(vthis))
  94         return JS_E_OBJECT_EXPECTED;
  95     if(!(jsdisp = to_jsdisp(get_object(vthis))) || !is_class(jsdisp, JSCLASS_MAP)) {
  96         WARN("not a Map object passed as 'this'\n");
  97         return throw_error(ctx, JS_E_WRONG_THIS, L"Map");
  98     }
  99
 100     *ret = CONTAINING_RECORD(jsdisp, MapInstance, dispex);
 101     return S_OK;
 102 }
 103
 104 static HRESULT get_set_this(script_ctx_t *ctx, jsval_t vthis, MapInstance **ret)
 105 {
 106     jsdisp_t *jsdisp;
 107
 108     if(!is_object_instance(vthis))
 109         return JS_E_OBJECT_EXPECTED;
 110     if(!(jsdisp = to_jsdisp(get_object(vthis))) || !is_class(jsdisp, JSCLASS_SET)) {
 111         WARN("not a Set object passed as 'this'\n");
 112         return throw_error(ctx, JS_E_WRONG_THIS, L"Set");
 113     }
 114
 115     *ret = CONTAINING_RECORD(jsdisp, MapInstance, dispex);
 116     return S_OK;
 117 }
 118
 119 static struct jsval_map_entry *get_map_entry(MapInstance *map, jsval_t key)
 120 {
 121     struct wine_rb_entry *entry;
 122     if(!(entry = wine_rb_get(&map->map, &key))) return NULL;
 123     return CONTAINING_RECORD(entry, struct jsval_map_entry, entry);
 124 }
 125
 126 static void grab_map_entry(struct jsval_map_entry *entry)
 127 {
 128     entry->ref++;
 129 }
 130
 131 static void release_map_entry(struct jsval_map_entry *entry)
 132 {
 133     if(--entry->ref) return;
 134     jsval_release(entry->key);
 135     jsval_release(entry->value);
 136     list_remove(&entry->list_entry);
 137     free(entry);
 138 }
 139
 140 static void delete_map_entry(MapInstance *map, struct jsval_map_entry *entry)
 141 {
 142     map->size--;
 143     wine_rb_remove(&map->map, &entry->entry);
 144     entry->deleted = TRUE;
 145     release_map_entry(entry);
 146 }
 147
 148 static HRESULT set_map_entry(MapInstance *map, jsval_t key, jsval_t value, jsval_t *r)
 149 {
 150     struct jsval_map_entry *entry;
 151     HRESULT hres;
 152
 153     if((entry = get_map_entry(map, key))) {
 154         jsval_t val;
 155         hres = jsval_copy(value, &val);
 156         if(FAILED(hres))
 157             return hres;
 158
 159         jsval_release(entry->value);
 160         entry->value = val;
 161     }else {
 162         if(!(entry = calloc(1, sizeof(*entry)))) return E_OUTOFMEMORY;
 163
 164         hres = jsval_copy(key, &entry->key);
 165         if(SUCCEEDED(hres)) {
 166             hres = jsval_copy(value, &entry->value);
 167             if(FAILED(hres))
 168                 jsval_release(entry->key);
 169         }
 170         if(FAILED(hres)) {
 171             free(entry);
 172             return hres;
 173         }
 174         grab_map_entry(entry);
 175         wine_rb_put(&map->map, &entry->key, &entry->entry);
 176         list_add_tail(&map->entries, &entry->list_entry);
 177         map->size++;
 178     }
 179
 180     if(r) *r = jsval_undefined();
 181     return S_OK;
 182 }
 183
 184 static HRESULT iterate_map(MapInstance *map, script_ctx_t *ctx, unsigned argc, jsval_t *argv, jsval_t *r)
 185 {
 186     struct list *iter = list_head(&map->entries);
 187     jsval_t context_this = jsval_undefined();
 188     HRESULT hres;
 189
 190     if(!argc || !is_object_instance(argv[0])) {
 191         FIXME("invalid callback %s\n", debugstr_jsval(argc ? argv[0] : jsval_undefined()));
 192         return E_FAIL;
 193     }
 194
 195     if(argc > 1)
 196         context_this = argv[1];
 197
 198     while(iter) {
 199         struct jsval_map_entry *entry = LIST_ENTRY(iter, struct jsval_map_entry, list_entry);
 200         jsval_t args[3], v;
 201
 202         if(entry->deleted) {
 203             iter = list_next(&map->entries, iter);
 204             continue;
 205         }
 206
 207         args[0] = entry->value;
 208         args[1] = entry->key;
 209         args[2] = jsval_obj(&map->dispex);
 210         grab_map_entry(entry);
 211         hres = disp_call_value(ctx, get_object(argv[0]), context_this, DISPATCH_METHOD, ARRAY_SIZE(args), args, &v);
 212         iter = list_next(&map->entries, iter);
 213         release_map_entry(entry);
 214         if(FAILED(hres))
 215             return hres;
 216         jsval_release(v);
 217     }
 218
 219     if(r) *r = jsval_undefined();
 220     return S_OK;
 221 }
 222
 223 static HRESULT Map_clear(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 224         jsval_t *r)
 225 {
 226     struct jsval_map_entry *entry, *entry2;
 227     MapInstance *map;
 228     HRESULT hres;
 229
 230     hres = get_map_this(ctx, vthis, &map);
 231     if(FAILED(hres))
 232         return hres;
 233
 234     TRACE("%p\n", map);
 235
 236     LIST_FOR_EACH_ENTRY_SAFE(entry, entry2, &map->entries, struct jsval_map_entry, list_entry)
 237         delete_map_entry(map, entry);
 238
 239     if(r) *r = jsval_undefined();
 240     return S_OK;
 241 }
 242
 243 static HRESULT Map_delete(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 244         jsval_t *r)
 245 {
 246     jsval_t key = argc >= 1 ? argv[0] : jsval_undefined();
 247     struct jsval_map_entry *entry;
 248     MapInstance *map;
 249     HRESULT hres;
 250
 251     hres = get_map_this(ctx, vthis, &map);
 252     if(FAILED(hres))
 253         return hres;
 254
 255     TRACE("%p (%s)\n", map, debugstr_jsval(key));
 256
 257     if((entry = get_map_entry(map, key))) delete_map_entry(map, entry);
 258     if(r) *r = jsval_bool(!!entry);
 259     return S_OK;
 260 }
 261
 262 static HRESULT Map_forEach(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 263         jsval_t *r)
 264 {
 265     MapInstance *map;
 266     HRESULT hres;
 267
 268     hres = get_map_this(ctx, vthis, &map);
 269     if(FAILED(hres))
 270         return hres;
 271
 272     TRACE("%p (%s)\n", map, debugstr_jsval(argc >= 1 ? argv[0] : jsval_undefined()));
 273
 274     return iterate_map(map, ctx, argc, argv, r);
 275 }
 276
 277 static HRESULT Map_get(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 278         jsval_t *r)
 279 {
 280     jsval_t key = argc >= 1 ? argv[0] : jsval_undefined();
 281     struct jsval_map_entry *entry;
 282     MapInstance *map;
 283     HRESULT hres;
 284
 285     hres = get_map_this(ctx, vthis, &map);
 286     if(FAILED(hres))
 287         return hres;
 288
 289     TRACE("%p (%s)\n", map, debugstr_jsval(key));
 290
 291     if(!(entry = get_map_entry(map, key))) {
 292         if(r) *r = jsval_undefined();
 293         return S_OK;
 294     }
 295
 296     return r ? jsval_copy(entry->value, r) : S_OK;
 297 }
 298
 299 static HRESULT Map_set(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 300         jsval_t *r)
 301 {
 302     jsval_t key = argc >= 1 ? argv[0] : jsval_undefined();
 303     jsval_t value = argc >= 2 ? argv[1] : jsval_undefined();
 304     MapInstance *map;
 305     HRESULT hres;
 306
 307     hres = get_map_this(ctx, vthis, &map);
 308     if(FAILED(hres))
 309         return hres;
 310
 311     TRACE("%p (%s %s)\n", map, debugstr_jsval(key), debugstr_jsval(value));
 312
 313     return set_map_entry(map, key, value, r);
 314 }
 315
 316 static HRESULT Map_has(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 317         jsval_t *r)
 318 {
 319     jsval_t key = argc >= 1 ? argv[0] : jsval_undefined();
 320     struct jsval_map_entry *entry;
 321     MapInstance *map;
 322     HRESULT hres;
 323
 324     hres = get_map_this(ctx, vthis, &map);
 325     if(FAILED(hres))
 326         return hres;
 327
 328     TRACE("%p (%s)\n", map, debugstr_jsval(key));
 329
 330     entry = get_map_entry(map, key);
 331     if(r) *r = jsval_bool(!!entry);
 332     return S_OK;
 333 }
 334
 335 static HRESULT Map_get_size(script_ctx_t *ctx, jsdisp_t *jsthis, jsval_t *r)
 336 {
 337     MapInstance *map = (MapInstance*)jsthis;
 338
 339     TRACE("%p\n", map);
 340
 341     *r = jsval_number(map->size);
 342     return S_OK;
 343 }
 344
 345 static HRESULT Map_value(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 346         jsval_t *r)
 347 {
 348     FIXME("\n");
 349     return E_NOTIMPL;
 350 }
 351
 352 static void Map_destructor(jsdisp_t *dispex)
 353 {
 354     MapInstance *map = (MapInstance*)dispex;
 355
 356     while(!list_empty(&map->entries)) {
 357         struct jsval_map_entry *entry = LIST_ENTRY(list_head(&map->entries),
 358                                                    struct jsval_map_entry, list_entry);
 359         assert(!entry->deleted);
 360         release_map_entry(entry);
 361     }
 362
 363     free(map);
 364 }
 365
 366 static HRESULT Map_gc_traverse(struct gc_ctx *gc_ctx, enum gc_traverse_op op, jsdisp_t *dispex)
 367 {
 368     MapInstance *map = (MapInstance*)dispex;
 369     struct jsval_map_entry *entry, *entry2;
 370     HRESULT hres;
 371
 372     if(op == GC_TRAVERSE_UNLINK) {
 373         LIST_FOR_EACH_ENTRY_SAFE(entry, entry2, &map->entries, struct jsval_map_entry, list_entry)
 374             release_map_entry(entry);
 375         wine_rb_destroy(&map->map, NULL, NULL);
 376         return S_OK;
 377     }
 378
 379     LIST_FOR_EACH_ENTRY(entry, &map->entries, struct jsval_map_entry, list_entry) {
 380         hres = gc_process_linked_val(gc_ctx, op, dispex, &entry->key);
 381         if(FAILED(hres))
 382             return hres;
 383         hres = gc_process_linked_val(gc_ctx, op, dispex, &entry->value);
 384         if(FAILED(hres))
 385             return hres;
 386     }
 387     return S_OK;
 388 }
 389
 390 static const builtin_prop_t Map_prototype_props[] = {
 391     {L"clear",      Map_clear,     PROPF_METHOD},
 392     {L"delete" ,    Map_delete,    PROPF_METHOD|1},
 393     {L"forEach",    Map_forEach,   PROPF_METHOD|1},
 394     {L"get",        Map_get,       PROPF_METHOD|1},
 395     {L"has",        Map_has,       PROPF_METHOD|1},
 396     {L"set",        Map_set,       PROPF_METHOD|2},
 397 };
 398
 399 static const builtin_prop_t Map_props[] = {
 400     {L"size",       NULL,0,        Map_get_size, builtin_set_const},
 401 };
 402
 403 static const builtin_info_t Map_prototype_info = {
 404     JSCLASS_OBJECT,
 405     Map_value,
 406     ARRAY_SIZE(Map_prototype_props),
 407     Map_prototype_props,
 408     NULL,
 409     NULL
 410 };
 411
 412 static const builtin_info_t Map_info = {
 413     JSCLASS_MAP,
 414     Map_value,
 415     ARRAY_SIZE(Map_props),
 416     Map_props,
 417     Map_destructor,
 418     NULL,
 419     NULL,
 420     NULL,
 421     NULL,
 422     Map_gc_traverse
 423 };
 424
 425 static HRESULT Map_constructor(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 426         jsval_t *r)
 427 {
 428     MapInstance *map;
 429     HRESULT hres;
 430
 431     switch(flags) {
 432     case DISPATCH_CONSTRUCT:
 433         TRACE("\n");
 434
 435         if(!r)
 436             return S_OK;
 437         if(!(map = calloc(1, sizeof(*map))))
 438             return E_OUTOFMEMORY;
 439
 440         hres = init_dispex(&map->dispex, ctx, &Map_info, ctx->map_prototype);
 441         if(FAILED(hres))
 442             return hres;
 443
 444         wine_rb_init(&map->map, jsval_map_compare);
 445         list_init(&map->entries);
 446         *r = jsval_obj(&map->dispex);
 447         return S_OK;
 448
 449     case DISPATCH_METHOD:
 450         return throw_error(ctx, JS_E_WRONG_THIS, L"Map");
 451
 452     default:
 453         FIXME("unimplemented flags %x\n", flags);
 454         return E_NOTIMPL;
 455     }
 456 }
 457
 458 static HRESULT Set_add(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 459         jsval_t *r)
 460 {
 461     jsval_t key = argc ? argv[0] : jsval_undefined();
 462     MapInstance *set;
 463     HRESULT hres;
 464
 465     hres = get_set_this(ctx, vthis, &set);
 466     if(FAILED(hres))
 467         return hres;
 468
 469     TRACE("%p (%s)\n", set, debugstr_jsval(key));
 470
 471     return set_map_entry(set, key, key, r);
 472 }
 473
 474 static HRESULT Set_clear(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 475         jsval_t *r)
 476 {
 477     struct jsval_map_entry *entry, *entry2;
 478     MapInstance *set;
 479     HRESULT hres;
 480
 481     hres = get_set_this(ctx, vthis, &set);
 482     if(FAILED(hres))
 483         return hres;
 484
 485     TRACE("%p\n", set);
 486
 487     LIST_FOR_EACH_ENTRY_SAFE(entry, entry2, &set->entries, struct jsval_map_entry, list_entry)
 488         delete_map_entry(set, entry);
 489
 490     if(r) *r = jsval_undefined();
 491     return S_OK;
 492 }
 493
 494 static HRESULT Set_delete(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 495         jsval_t *r)
 496 {
 497     jsval_t key = argc ? argv[0] : jsval_undefined();
 498     struct jsval_map_entry *entry;
 499     MapInstance *set;
 500     HRESULT hres;
 501
 502     hres = get_set_this(ctx, vthis, &set);
 503     if(FAILED(hres))
 504         return hres;
 505
 506     TRACE("%p (%s)\n", set, debugstr_jsval(key));
 507
 508     if((entry = get_map_entry(set, key))) delete_map_entry(set, entry);
 509     if(r) *r = jsval_bool(!!entry);
 510     return S_OK;
 511 }
 512
 513 static HRESULT Set_forEach(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 514         jsval_t *r)
 515 {
 516     MapInstance *set;
 517     HRESULT hres;
 518
 519     hres = get_set_this(ctx, vthis, &set);
 520     if(FAILED(hres))
 521         return hres;
 522
 523     TRACE("%p (%s)\n", set, debugstr_jsval(argc ? argv[0] : jsval_undefined()));
 524
 525     return iterate_map(set, ctx, argc, argv, r);
 526 }
 527
 528 static HRESULT Set_has(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 529         jsval_t *r)
 530 {
 531     jsval_t key = argc ? argv[0] : jsval_undefined();
 532     struct jsval_map_entry *entry;
 533     MapInstance *set;
 534     HRESULT hres;
 535
 536     hres = get_set_this(ctx, vthis, &set);
 537     if(FAILED(hres))
 538         return hres;
 539
 540     TRACE("%p (%s)\n", set, debugstr_jsval(key));
 541
 542     entry = get_map_entry(set, key);
 543     if(r) *r = jsval_bool(!!entry);
 544     return S_OK;
 545 }
 546
 547 static HRESULT Set_value(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 548         jsval_t *r)
 549 {
 550     FIXME("\n");
 551     return E_NOTIMPL;
 552 }
 553
 554 static const builtin_prop_t Set_prototype_props[] = {
 555     {L"add",        Set_add,       PROPF_METHOD|1},
 556     {L"clear",      Set_clear,     PROPF_METHOD},
 557     {L"delete" ,    Set_delete,    PROPF_METHOD|1},
 558     {L"forEach",    Set_forEach,   PROPF_METHOD|1},
 559     {L"has",        Set_has,       PROPF_METHOD|1},
 560 };
 561
 562 static const builtin_info_t Set_prototype_info = {
 563     JSCLASS_OBJECT,
 564     Set_value,
 565     ARRAY_SIZE(Set_prototype_props),
 566     Set_prototype_props,
 567     NULL,
 568     NULL
 569 };
 570
 571 static const builtin_info_t Set_info = {
 572     JSCLASS_SET,
 573     Set_value,
 574     ARRAY_SIZE(Map_props),
 575     Map_props,
 576     Map_destructor,
 577     NULL,
 578     NULL,
 579     NULL,
 580     NULL,
 581     Map_gc_traverse
 582 };
 583
 584 static HRESULT Set_constructor(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv,
 585         jsval_t *r)
 586 {
 587     MapInstance *set;
 588     HRESULT hres;
 589
 590     switch(flags) {
 591     case DISPATCH_CONSTRUCT:
 592         TRACE("\n");
 593
 594         if(!r)
 595             return S_OK;
 596         if(!(set = calloc(1, sizeof(*set))))
 597             return E_OUTOFMEMORY;
 598
 599         hres = init_dispex(&set->dispex, ctx, &Set_info, ctx->set_prototype);
 600         if(FAILED(hres))
 601             return hres;
 602
 603         wine_rb_init(&set->map, jsval_map_compare);
 604         list_init(&set->entries);
 605         *r = jsval_obj(&set->dispex);
 606         return S_OK;
 607
 608     case DISPATCH_METHOD:
 609         return throw_error(ctx, JS_E_WRONG_THIS, L"Set");
 610
 611     default:
 612         FIXME("unimplemented flags %x\n", flags);
 613         return E_NOTIMPL;
 614     }
 615 }
 616
 617 HRESULT init_set_constructor(script_ctx_t *ctx)
 618 {
 619     jsdisp_t *constructor;
 620     HRESULT hres;
 621
 622     if(ctx->version < SCRIPTLANGUAGEVERSION_ES6)
 623         return S_OK;
 624
 625     hres = create_dispex(ctx, &Set_prototype_info, ctx->object_prototype, &ctx->set_prototype);
 626     if(FAILED(hres))
 627         return hres;
 628
 629     hres = create_builtin_constructor(ctx, Set_constructor, L"Set", NULL,
 630                                       PROPF_CONSTR, ctx->set_prototype, &constructor);
 631     if(FAILED(hres))
 632         return hres;
 633
 634     hres = jsdisp_define_data_property(ctx->global, L"Set", PROPF_WRITABLE,
 635                                        jsval_obj(constructor));
 636     jsdisp_release(constructor);
 637     if(FAILED(hres))
 638         return hres;
 639
 640     hres = create_dispex(ctx, &Map_prototype_info, ctx->object_prototype, &ctx->map_prototype);
 641     if(FAILED(hres))
 642         return hres;
 643
 644     hres = create_builtin_constructor(ctx, Map_constructor, L"Map", NULL,
 645                                       PROPF_CONSTR, ctx->map_prototype, &constructor);
 646     if(FAILED(hres))
 647         return hres;
 648
 649     hres = jsdisp_define_data_property(ctx->global, L"Map", PROPF_WRITABLE,
 650                                        jsval_obj(constructor));
 651     jsdisp_release(constructor);
 652     return hres;
 653 }