reactos/lib/kjs/src/b_array.c

   1 /*
   2  * The builtin Array object.
   3  * Copyright (c) 1998 New Generation Software (NGS) Oy
   4  *
   5  * Author: Markku Rossi <mtr@ngs.fi>
   6  */
   7
   8 /*
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Library General Public
  11  * License as published by the Free Software Foundation; either
  12  * version 2 of the License, or (at your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Library General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Library General Public
  20  * License along with this library; if not, write to the Free
  21  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  22  * MA 02111-1307, USA
  23  */
  24
  25 /*
  26  * $Source: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/kjs/src/b_array.c,v $
  27  * $Id$
  28  */
  29
  30 /*
  31  * Mehtods:
  32  *
  33  *   concat (array) => array
  34  *   join ([glue]) => string
  35  *   pop () => last_element
  36  *   push (any...) => last_element_added
  37  *   reverse ()
  38  *   shift () => first_element
  39  *   slice (start, end) => array
  40  *   splice (index, how_many[, any...]) => array
  41  *   sort ([sort_function])
  42  *   toString () => string
  43  *   unshift (any...) => length_of_the_array
  44  *
  45  * Properties:
  46  *
  47  *   length
  48  */
  49
  50 #include "jsint.h"
  51 #include "mrgsort.h"
  52
  53 /*
  54  * Types and definitions.
  55  */
  56
  57 /* Class context. */
  58 struct array_ctx_st
  59 {
  60   JSSymbol s_concat;
  61   JSSymbol s_join;
  62   JSSymbol s_pop;
  63   JSSymbol s_push;
  64   JSSymbol s_reverse;
  65   JSSymbol s_shift;
  66   JSSymbol s_slice;
  67   JSSymbol s_splice;
  68   JSSymbol s_sort;
  69   JSSymbol s_unshift;
  70
  71   JSSymbol s_length;
  72 };
  73
  74 typedef struct array_ctx_st ArrayCtx;
  75
  76 /* Context for array sorts with JavaScript functions. */
  77 struct array_sort_ctx_st
  78 {
  79   JSVirtualMachine *vm;
  80   JSNode *func;
  81   JSNode argv[3];
  82 };
  83
  84 typedef struct array_sort_ctx_st ArraySortCtx;
  85
  86 /*
  87  * Prototypes for static functions.
  88  */
  89
  90 static void new_proc (JSVirtualMachine *vm, JSBuiltinInfo *builtin_info,
  91                       JSNode *args, JSNode *result_return);
  92
  93
  94 /*
  95  * Static functions.
  96  */
  97
  98 static int
  99 sort_default_cmp_func (const void *aptr, const void *bptr, void *context)
 100 {
 101   JSVirtualMachine *vm = context;
 102   const JSNode *a = aptr;
 103   const JSNode *b = bptr;
 104   JSNode astr, bstr;
 105
 106   if (a->type == JS_UNDEFINED)
 107     return 1;
 108   if (b->type == JS_UNDEFINED)
 109     return -1;
 110
 111   js_vm_to_string (vm, a, &astr);
 112   js_vm_to_string (vm, b, &bstr);
 113
 114   return js_compare_strings (&astr, &bstr);
 115 }
 116
 117
 118 static int
 119 sort_js_cmp_func (const void *aptr, const void *bptr, void *context)
 120 {
 121   ArraySortCtx *ctx = context;
 122   const JSNode *a = aptr;
 123   const JSNode *b = bptr;
 124
 125   /*
 126    * Finalize the argument array.  The argumnet count has already been set.
 127    * when the context were initialized.
 128    */
 129   JS_COPY (&ctx->argv[1], a);
 130   JS_COPY (&ctx->argv[2], b);
 131
 132   /* Call the function. */
 133   if (!js_vm_apply (ctx->vm, NULL, ctx->func, 3, ctx->argv))
 134     /* Raise an error. */
 135     js_vm_error (ctx->vm);
 136
 137   /* Fetch the return value. */
 138   if (ctx->vm->exec_result.type != JS_INTEGER)
 139     {
 140       sprintf (ctx->vm->error,
 141                "Array.sort(): comparison function didn't return integer");
 142       js_vm_error (ctx->vm);
 143     }
 144
 145   return ctx->vm->exec_result.u.vinteger;
 146 }
 147
 148
 149 /* Global method proc. */
 150 static void
 151 global_method (JSVirtualMachine *vm, JSBuiltinInfo *builtin_info,
 152                void *instance_context, JSNode *result_return,
 153                JSNode *args)
 154 {
 155   /* This does exactly the same as the new_proc. */
 156   new_proc (vm, builtin_info, args, result_return);
 157 }
 158
 159
 160 /* Method proc. */
 161 static int
 162 method (JSVirtualMachine *vm, JSBuiltinInfo *builtin_info,
 163         void *instance_context, JSSymbol method, JSNode *result_return,
 164         JSNode *args)
 165 {
 166   ArrayCtx *ctx = builtin_info->obj_context;
 167   JSNode *n = instance_context;
 168   int i;
 169
 170   /* XXX 15.7.4.3 toSource(). */
 171
 172   /* Handle static methods here. */
 173   if (instance_context == NULL)
 174     {
 175       if (method == vm->syms.s_toString)
 176         js_vm_make_static_string (vm, result_return, "Array", 5);
 177       /* ************************************************************ */
 178       else
 179         return JS_PROPERTY_UNKNOWN;
 180
 181       return JS_PROPERTY_FOUND;
 182     }
 183
 184   /* Handle the instance methods. */
 185
 186   /* Set the default result type. */
 187   result_return->type = JS_UNDEFINED;
 188
 189   if (method == ctx->s_concat)
 190     {
 191       int nlen;
 192       int pos;
 193
 194       /* Count the new len; */
 195
 196       nlen = n->u.varray->length;
 197       for (i = 0; i < args->u.vinteger; i++)
 198         {
 199           if (args[i + 1].type != JS_ARRAY)
 200             goto argument_error;
 201
 202           nlen += args[i + 1].u.varray->length;
 203         }
 204
 205       js_vm_make_array (vm, result_return, nlen);
 206
 207       /* Insert the items. */
 208       memcpy (result_return->u.varray->data, n->u.varray->data,
 209               n->u.varray->length * sizeof (JSNode));
 210       pos = n->u.varray->length;
 211
 212       for (i = 0; i < args->u.vinteger; i++)
 213         {
 214           memcpy (&result_return->u.varray->data[pos],
 215                   args[i + 1].u.varray->data,
 216                   args[i + 1].u.varray->length * sizeof (JSNode));
 217           pos += args[i + 1].u.varray->length;
 218         }
 219     }
 220   /* ********************************************************************** */
 221   else if (method == ctx->s_join || method == vm->syms.s_toString)
 222     {
 223       char *glue = NULL;
 224
 225       if (method == vm->syms.s_toString)
 226         {
 227           if (args->u.vinteger != 0)
 228             goto argument_error;
 229         }
 230       else
 231         {
 232           if (args->u.vinteger == 0)
 233             ;
 234           else if (args->u.vinteger == 1)
 235             {
 236               JSNode glue_result;
 237
 238               js_vm_to_string (vm, &args[1], &glue_result);
 239               glue = js_string_to_c_string (vm, &glue_result);
 240             }
 241           else
 242             goto argument_error;
 243         }
 244
 245       /* Ok, ready to run. */
 246       if (n->u.varray->length == 0)
 247         js_vm_make_static_string (vm, result_return, "", 0);
 248       else
 249         {
 250           int len;
 251           int glue_len = glue ? strlen (glue) : 1;
 252
 253           /* Estimate the result length. */
 254           len = (n->u.varray->length * 5
 255                  + (n->u.varray->length - 1) * glue_len);
 256
 257           js_vm_make_string (vm, result_return, NULL, len);
 258           result_return->u.vstring->len = 0;
 259
 260           /* Do the join. */
 261           for (i = 0; i < n->u.varray->length; i++)
 262             {
 263               JSNode sitem;
 264               int delta;
 265
 266               js_vm_to_string (vm, &n->u.varray->data[i], &sitem);
 267               delta = sitem.u.vstring->len;
 268
 269               if (i + 1 < n->u.varray->length)
 270                 delta += glue_len;
 271
 272               result_return->u.vstring->data
 273                 = js_vm_realloc (vm, result_return->u.vstring->data,
 274                                  result_return->u.vstring->len + delta);
 275
 276               memcpy (result_return->u.vstring->data
 277                       + result_return->u.vstring->len,
 278                       sitem.u.vstring->data,
 279                       sitem.u.vstring->len);
 280               result_return->u.vstring->len += sitem.u.vstring->len;
 281
 282               if (i + 1 < n->u.varray->length)
 283                 {
 284                   if (glue)
 285                     {
 286                       memcpy (result_return->u.vstring->data
 287                               + result_return->u.vstring->len,
 288                               glue, glue_len);
 289                       result_return->u.vstring->len += glue_len;
 290                     }
 291                   else
 292                     result_return->u.vstring->data
 293                       [result_return->u.vstring->len++] = ',';
 294                 }
 295             }
 296         }
 297
 298       if (glue)
 299         js_free (glue);
 300     }
 301   /* ********************************************************************** */
 302   else if (method == ctx->s_pop)
 303     {
 304       if (args->u.vinteger != 0)
 305         goto argument_error;
 306
 307       if (n->u.varray->length == 0)
 308         result_return->type = JS_UNDEFINED;
 309       else
 310         {
 311           JS_COPY (result_return, &n->u.varray->data[n->u.varray->length - 1]);
 312           n->u.varray->length--;
 313         }
 314     }
 315   /* ********************************************************************** */
 316   else if (method == ctx->s_push)
 317     {
 318       int old_len;
 319
 320       if (args->u.vinteger == 0)
 321         goto argument_error;
 322
 323       old_len = n->u.varray->length;
 324       js_vm_expand_array (vm, n, n->u.varray->length + args->u.vinteger);
 325
 326       for (i = 0; i < args->u.vinteger; i++)
 327         JS_COPY (&n->u.varray->data[old_len + i], &args[i + 1]);
 328
 329       JS_COPY (result_return, &args[i]);
 330     }
 331   /* ********************************************************************** */
 332   else if (method == ctx->s_reverse)
 333     {
 334       if (args->u.vinteger != 0)
 335         goto argument_error;
 336
 337       for (i = 0; i < n->u.varray->length / 2; i++)
 338         {
 339           JSNode tmp;
 340
 341           JS_COPY (&tmp, &n->u.varray->data[i]);
 342           JS_COPY (&n->u.varray->data[i],
 343                    &n->u.varray->data[n->u.varray->length - i - 1]);
 344           JS_COPY (&n->u.varray->data[n->u.varray->length - i - 1], &tmp);
 345         }
 346     }
 347   /* ********************************************************************** */
 348   else if (method == ctx->s_shift)
 349     {
 350       if (args->u.vinteger != 0)
 351         goto argument_error;
 352
 353       if (n->u.varray->length == 0)
 354         result_return->type = JS_UNDEFINED;
 355       else
 356         {
 357           JS_COPY (result_return, &n->u.varray->data[0]);
 358           memmove (&n->u.varray->data[0], &n->u.varray->data[1],
 359                    (n->u.varray->length - 1) * sizeof (JSNode));
 360           n->u.varray->length--;
 361         }
 362     }
 363   /* ********************************************************************** */
 364   else if (method == ctx->s_slice)
 365     {
 366       int start, end;
 367
 368       if (args->u.vinteger < 1 || args->u.vinteger > 2)
 369         goto argument_error;
 370
 371       if (args[1].type != JS_INTEGER)
 372         goto argument_type_error;
 373
 374       start = args[1].u.vinteger;
 375
 376       if (args->u.vinteger == 2)
 377         {
 378           if (args[2].type != JS_INTEGER)
 379             goto argument_type_error;
 380
 381           end = args[2].u.vinteger;
 382         }
 383       else
 384         end = n->u.varray->length;
 385
 386       if (end < 0)
 387         end += n->u.varray->length;
 388       if (end < 0)
 389         end = start;
 390
 391       js_vm_make_array (vm, result_return, end - start);
 392
 393       /* Copy items. */
 394       for (i = 0; i < end - start; i++)
 395         JS_COPY (&result_return->u.varray->data[i],
 396                  &n->u.varray->data[start + i]);
 397     }
 398   /* ********************************************************************** */
 399   else if (method == ctx->s_splice)
 400     {
 401       unsigned int new_length;
 402       unsigned int old_length;
 403       int delta;
 404
 405       if (args->u.vinteger < 2)
 406         goto argument_error;
 407       if (args[1].type != JS_INTEGER || args[2].type != JS_INTEGER)
 408         goto argument_type_error;
 409
 410       if (args[2].u.vinteger == 0 && args->u.vinteger == 2)
 411         /* No deletions: must specify at least one item to insert. */
 412         goto argument_error;
 413
 414       old_length = new_length = n->u.varray->length;
 415       if (args[1].u.vinteger < new_length)
 416         {
 417           if (args[2].u.vinteger > new_length - args[1].u.vinteger)
 418             {
 419               args[2].u.vinteger = new_length - args[1].u.vinteger;
 420               new_length = args[1].u.vinteger;
 421             }
 422           else
 423             new_length -= args[2].u.vinteger;
 424         }
 425       else
 426         {
 427           new_length = args[1].u.vinteger;
 428           args[2].u.vinteger = 0;
 429         }
 430
 431       new_length += args->u.vinteger - 2;
 432
 433       if (new_length > n->u.varray->length)
 434         js_vm_expand_array (vm, n, new_length);
 435       else
 436         /* Cut the array. */
 437         n->u.varray->length = new_length;
 438
 439       /* Do the stuffs we must do. */
 440
 441       /* Create the result array. */
 442       if (args[2].u.vinteger == 0)
 443         result_return->type = JS_UNDEFINED;
 444       else
 445         {
 446           js_vm_make_array (vm, result_return, args[2].u.vinteger);
 447           for (i = 0; i < args[2].u.vinteger; i++)
 448             JS_COPY (&result_return->u.varray->data[i],
 449                      &n->u.varray->data[args[1].u.vinteger + i]);
 450         }
 451
 452       /* Delete and move. */
 453       delta = args->u.vinteger - 2 - args[2].u.vinteger;
 454       memmove (&n->u.varray->data[args[1].u.vinteger + args[2].u.vinteger
 455                                  + delta],
 456                &n->u.varray->data[args[1].u.vinteger + args[2].u.vinteger],
 457                (old_length - (args[1].u.vinteger + args[2].u.vinteger))
 458                * sizeof (JSNode));
 459
 460       /* Insert. */
 461       for (i = 0; i < args->u.vinteger - 2; i++)
 462         JS_COPY (&n->u.varray->data[args[1].u.vinteger + i], &args[i + 3]);
 463     }
 464   /* ********************************************************************** */
 465   else if (method == ctx->s_sort)
 466     {
 467       MergesortCompFunc func;
 468       ArraySortCtx array_sort_ctx;
 469       void *func_ctx = NULL;    /* Initialized to keep compiler quiet. */
 470
 471       if (args->u.vinteger == 0)
 472         {
 473           func = sort_default_cmp_func;
 474           func_ctx = vm;
 475         }
 476       else if (args->u.vinteger == 1)
 477         {
 478           if (args[1].type != JS_FUNC && args[1].type != JS_BUILTIN)
 479             goto argument_type_error;
 480
 481           func = sort_js_cmp_func;
 482
 483           /* Init context. */
 484           array_sort_ctx.vm = vm;
 485           array_sort_ctx.func = &args[1];
 486
 487           /* Init the argc part of the argument vector here. */
 488           array_sort_ctx.argv[0].type = JS_INTEGER;
 489           array_sort_ctx.argv[0].u.vinteger = 3;
 490
 491           func_ctx = &array_sort_ctx;
 492         }
 493       else
 494         goto argument_error;
 495
 496       mergesort_r (n->u.varray->data, n->u.varray->length, sizeof (JSNode),
 497                    func, func_ctx);
 498     }
 499   /* ********************************************************************** */
 500   else if (method == ctx->s_unshift)
 501     {
 502       int old_len;
 503
 504       if (args->u.vinteger == 0)
 505         goto argument_error;
 506
 507       old_len = n->u.varray->length;
 508       js_vm_expand_array (vm, n, n->u.varray->length + args->u.vinteger);
 509
 510       memmove (&n->u.varray->data[args->u.vinteger], n->u.varray->data,
 511                old_len * sizeof (JSNode));
 512
 513       for (i = 0; i < args->u.vinteger; i++)
 514         JS_COPY (&n->u.varray->data[i], &args[args->u.vinteger - i]);
 515
 516       result_return->type = JS_INTEGER;
 517       result_return->u.vinteger = n->u.varray->length;
 518     }
 519   /* ********************************************************************** */
 520   else
 521     return JS_PROPERTY_UNKNOWN;
 522
 523   return JS_PROPERTY_FOUND;
 524
 525
 526   /*
 527    * Error handling.
 528    */
 529
 530  argument_error:
 531   sprintf (vm->error, "Array.%s(): illegal amount of arguments",
 532            js_vm_symname (vm, method));
 533   js_vm_error (vm);
 534
 535  argument_type_error:
 536   sprintf (vm->error, "Array.%s(): illegal argument",
 537            js_vm_symname (vm, method));
 538   js_vm_error (vm);
 539
 540   /* NOTREACHED */
 541   return 0;
 542 }
 543
 544 /* Property proc. */
 545 static int
 546 property (JSVirtualMachine *vm, JSBuiltinInfo *builtin_info,
 547           void *instance_context, JSSymbol property, int set, JSNode *node)
 548 {
 549   ArrayCtx *ctx = builtin_info->obj_context;
 550   JSNode *n = instance_context;
 551
 552   if (property == ctx->s_length)
 553     {
 554       if (set)
 555         goto immutable;
 556
 557       node->type = JS_INTEGER;
 558       node->u.vinteger = n->u.varray->length;
 559     }
 560   else
 561     {
 562       if (!set)
 563         node->type = JS_UNDEFINED;
 564
 565       return JS_PROPERTY_UNKNOWN;
 566     }
 567
 568   return JS_PROPERTY_FOUND;
 569
 570
 571   /*
 572    * Error handling.
 573    */
 574
 575  immutable:
 576   sprintf (vm->error, "Array.%s: immutable property",
 577            js_vm_symname (vm, property));
 578   js_vm_error (vm);
 579
 580   /* NOTREACHED */
 581   return 0;
 582 }
 583
 584 /* New proc. */
 585 static void
 586 new_proc (JSVirtualMachine *vm, JSBuiltinInfo *builtin_info, JSNode *args,
 587           JSNode *result_return)
 588 {
 589   int i;
 590
 591   if (args->u.vinteger == 1 && args[1].type == JS_INTEGER)
 592     {
 593       /* Create a fixed length array. */
 594       js_vm_make_array (vm, result_return, args[1].u.vinteger);
 595     }
 596   else
 597     {
 598       if (args->u.vinteger < 0)
 599         /* We are called from the array initializer. */
 600         args->u.vinteger = -args->u.vinteger;
 601
 602       js_vm_make_array (vm, result_return, args->u.vinteger);
 603       for (i = 0; i < args->u.vinteger; i++)
 604         JS_COPY (&result_return->u.varray->data[i], &args[i + 1]);
 605     }
 606   /* Set the [[Prototype]] and [[Class]] properties. */
 607   /* XXX 15.7.2.1 */
 608 }
 609
 610
 611 /*
 612  * Global functions.
 613  */
 614
 615 void
 616 js_builtin_Array (JSVirtualMachine *vm)
 617 {
 618   ArrayCtx *ctx;
 619   JSNode *n;
 620   JSBuiltinInfo *info;
 621
 622   ctx = js_calloc (vm, 1, sizeof (*ctx));
 623
 624   ctx->s_concat         = js_vm_intern (vm, "concat");
 625   ctx->s_join           = js_vm_intern (vm, "join");
 626   ctx->s_pop            = js_vm_intern (vm, "pop");
 627   ctx->s_push           = js_vm_intern (vm, "push");
 628   ctx->s_reverse        = js_vm_intern (vm, "reverse");
 629   ctx->s_shift          = js_vm_intern (vm, "shift");
 630   ctx->s_slice          = js_vm_intern (vm, "slice");
 631   ctx->s_splice         = js_vm_intern (vm, "splice");
 632   ctx->s_sort           = js_vm_intern (vm, "sort");
 633   ctx->s_unshift        = js_vm_intern (vm, "unshift");
 634
 635   ctx->s_length         = js_vm_intern (vm, "length");
 636
 637   info = js_vm_builtin_info_create (vm);
 638   vm->prim[JS_ARRAY] = info;
 639
 640   info->global_method_proc      = global_method;
 641   info->method_proc             = method;
 642   info->property_proc           = property;
 643   info->new_proc                = new_proc;
 644   info->obj_context             = ctx;
 645   info->obj_context_delete      = js_free;
 646
 647   /* Define it. */
 648   n = &vm->globals[js_vm_intern (vm, "Array")];
 649   js_vm_builtin_create (vm, n, info, NULL);
 650 }