src/org/mozilla/javascript/NativeArray.java

   1 /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-\r
   2  *\r
   3  * The contents of this file are subject to the Netscape Public\r
   4  * License Version 1.1 (the "License"); you may not use this file\r
   5  * except in compliance with the License. You may obtain a copy of\r
   6  * the License at http://www.mozilla.org/NPL/\r
   7  *\r
   8  * Software distributed under the License is distributed on an "AS\r
   9  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express oqr\r
  10  * implied. See the License for the specific language governing\r
  11  * rights and limitations under the License.\r
  12  *\r
  13  * The Original Code is Rhino code, released\r
  14  * May 6, 1999.\r
  15  *\r
  16  * The Initial Developer of the Original Code is Netscape\r
  17  * Communications Corporation.  Portions created by Netscape are\r
  18  * Copyright (C) 1997-1999 Netscape Communications Corporation. All\r
  19  * Rights Reserved.\r
  20  *\r
  21  * Contributor(s): \r
  22  * Norris Boyd\r
  23  * Mike McCabe\r
  24  * Igor Bukanov\r
  25  *\r
  26  * Alternatively, the contents of this file may be used under the\r
  27  * terms of the GNU Public License (the "GPL"), in which case the\r
  28  * provisions of the GPL are applicable instead of those above.\r
  29  * If you wish to allow use of your version of this file only\r
  30  * under the terms of the GPL and not to allow others to use your\r
  31  * version of this file under the NPL, indicate your decision by\r
  32  * deleting the provisions above and replace them with the notice\r
  33  * and other provisions required by the GPL.  If you do not delete\r
  34  * the provisions above, a recipient may use your version of this\r
  35  * file under either the NPL or the GPL.\r
  36  */\r
  37 \r
  38 package org.mozilla.javascript;\r
  39 import java.util.Hashtable;\r
  40 \r
  41 /**\r
  42  * This class implements the Array native object.\r
  43  * @author Norris Boyd\r
  44  * @author Mike McCabe\r
  45  */\r
  46 public class NativeArray extends IdScriptable {\r
  47 \r
  48     /*\r
  49      * Optimization possibilities and open issues:\r
  50      * - Long vs. double schizophrenia.  I suspect it might be better\r
  51      * to use double throughout.\r
  52 \r
  53      * - Most array operations go through getElem or setElem (defined\r
  54      * in this file) to handle the full 2^32 range; it might be faster\r
  55      * to have versions of most of the loops in this file for the\r
  56      * (infinitely more common) case of indices < 2^31.\r
  57 \r
  58      * - Functions that need a new Array call "new Array" in the\r
  59      * current scope rather than using a hardwired constructor;\r
  60      * "Array" could be redefined.  It turns out that js calls the\r
  61      * equivalent of "new Array" in the current scope, except that it\r
  62      * always gets at least an object back, even when Array == null.\r
  63      */\r
  64 \r
  65     public static void init(Context cx, Scriptable scope, boolean sealed) {\r
  66         NativeArray obj = new NativeArray();\r
  67         obj.prototypeFlag = true;\r
  68         obj.addAsPrototype(MAX_PROTOTYPE_ID, cx, scope, sealed);\r
  69     }\r
  70 \r
  71     /**\r
  72      * Zero-parameter constructor: just used to create Array.prototype\r
  73      */\r
  74     public NativeArray() {\r
  75         dense = null;\r
  76         this.length = 0;\r
  77     }\r
  78 \r
  79     public NativeArray(long length) {\r
  80         int intLength = (int) length;\r
  81         if (intLength == length && intLength > 0) {\r
  82             if (intLength > maximumDenseLength)\r
  83                 intLength = maximumDenseLength;\r
  84             dense = new Object[intLength];\r
  85             for (int i=0; i < intLength; i++)\r
  86                 dense[i] = NOT_FOUND;\r
  87         }\r
  88         this.length = length;\r
  89     }\r
  90 \r
  91     public NativeArray(Object[] array) {\r
  92         dense = array;\r
  93         this.length = array.length;\r
  94     }\r
  95 \r
  96     public String getClassName() {\r
  97         return "Array";\r
  98     }\r
  99 \r
 100     protected int getIdDefaultAttributes(int id) {\r
 101         if (id == Id_length) {\r
 102             return DONTENUM | PERMANENT;\r
 103         }\r
 104         return super.getIdDefaultAttributes(id);\r
 105     }\r
 106 \r
 107     protected Object getIdValue(int id) {\r
 108         if (id == Id_length) {\r
 109             return wrap_double(length);\r
 110         }\r
 111         return super.getIdValue(id);\r
 112     }\r
 113     \r
 114     protected void setIdValue(int id, Object value) {\r
 115         if (id == Id_length) {\r
 116             jsSet_length(value); return;\r
 117         }\r
 118         super.setIdValue(id, value);\r
 119     }\r
 120     \r
 121     public int methodArity(int methodId) {\r
 122         if (prototypeFlag) {\r
 123             switch (methodId) {\r
 124                 case Id_constructor:     return 1;\r
 125                 case Id_toString:        return 0;\r
 126                 case Id_toLocaleString:  return 1;\r
 127                 case Id_join:            return 1;\r
 128                 case Id_reverse:         return 0;\r
 129                 case Id_sort:            return 1;\r
 130                 case Id_push:            return 1;\r
 131                 case Id_pop:             return 1;\r
 132                 case Id_shift:           return 1;\r
 133                 case Id_unshift:         return 1;\r
 134                 case Id_splice:          return 1;\r
 135                 case Id_concat:          return 1;\r
 136                 case Id_slice:           return 1;\r
 137             }\r
 138         }\r
 139         return super.methodArity(methodId);\r
 140     }\r
 141 \r
 142     public Object execMethod\r
 143         (int methodId, IdFunction f,\r
 144          Context cx, Scriptable scope, Scriptable thisObj, Object[] args)\r
 145         throws JavaScriptException\r
 146     {\r
 147         if (prototypeFlag) {\r
 148             switch (methodId) {\r
 149                 case Id_constructor:\r
 150                     return jsConstructor(cx, scope, args, f, thisObj == null);\r
 151 \r
 152                 case Id_toString:\r
 153                     return jsFunction_toString(cx, thisObj, args);\r
 154 \r
 155                 case Id_toLocaleString:\r
 156                     return jsFunction_toLocaleString(cx, thisObj, args);\r
 157 \r
 158                 case Id_join:\r
 159                     return jsFunction_join(cx, thisObj, args);\r
 160 \r
 161                 case Id_reverse:\r
 162                     return jsFunction_reverse(cx, thisObj, args);\r
 163 \r
 164                 case Id_sort:\r
 165                     return jsFunction_sort(cx, scope, thisObj, args);\r
 166 \r
 167                 case Id_push:\r
 168                     return jsFunction_push(cx, thisObj, args);\r
 169 \r
 170                 case Id_pop:\r
 171                     return jsFunction_pop(cx, thisObj, args);\r
 172 \r
 173                 case Id_shift:\r
 174                     return jsFunction_shift(cx, thisObj, args);\r
 175 \r
 176                 case Id_unshift:\r
 177                     return jsFunction_unshift(cx, thisObj, args);\r
 178 \r
 179                 case Id_splice:\r
 180                     return jsFunction_splice(cx, scope, thisObj, args);\r
 181 \r
 182                 case Id_concat:\r
 183                     return jsFunction_concat(cx, scope, thisObj, args);\r
 184 \r
 185                 case Id_slice:\r
 186                     return jsFunction_slice(cx, thisObj, args);\r
 187             }\r
 188         }\r
 189         return super.execMethod(methodId, f, cx, scope, thisObj, args);\r
 190     }\r
 191 \r
 192     public Object get(int index, Scriptable start) {\r
 193         if (dense != null && 0 <= index && index < dense.length)\r
 194             return dense[index];\r
 195         return super.get(index, start);\r
 196     }\r
 197 \r
 198     public boolean has(int index, Scriptable start) {\r
 199         if (dense != null && 0 <= index && index < dense.length)\r
 200             return dense[index] != NOT_FOUND;\r
 201         return super.has(index, start);\r
 202     }\r
 203 \r
 204     public void put(String id, Scriptable start, Object value) {\r
 205         if (start == this) {\r
 206             // only set the array length if given an array index (ECMA 15.4.0)\r
 207 \r
 208             // try to get an array index from id\r
 209             double d = ScriptRuntime.toNumber(id);\r
 210 \r
 211             if (ScriptRuntime.toUint32(d) == d &&\r
 212                 ScriptRuntime.numberToString(d, 10).equals(id) &&\r
 213                 this.length <= d && d != 4294967295.0)\r
 214             {\r
 215                 this.length = (long)d + 1;\r
 216             }\r
 217         }\r
 218         super.put(id, start, value);\r
 219     }\r
 220 \r
 221     public void put(int index, Scriptable start, Object value) {\r
 222         if (start == this) {\r
 223             // only set the array length if given an array index (ECMA 15.4.0)\r
 224             if (this.length <= index) {\r
 225                 // avoid overflowing index!\r
 226                 this.length = (long)index + 1;\r
 227             }\r
 228 \r
 229             if (dense != null && 0 <= index && index < dense.length) {\r
 230                 dense[index] = value;\r
 231                 return;\r
 232             }\r
 233         }\r
 234         super.put(index, start, value);\r
 235     }\r
 236 \r
 237     public void delete(int index) {\r
 238         if (!isSealed()) {\r
 239             if (dense != null && 0 <= index && index < dense.length) {\r
 240                 dense[index] = NOT_FOUND;\r
 241                 return;\r
 242             }\r
 243         }\r
 244         super.delete(index);\r
 245     }\r
 246 \r
 247     public Object[] getIds() {\r
 248         Object[] superIds = super.getIds();\r
 249         if (dense == null)\r
 250             return superIds;\r
 251         int count = 0;\r
 252         int last = dense.length;\r
 253         if (last > length)\r
 254             last = (int) length;\r
 255         for (int i=last-1; i >= 0; i--) {\r
 256             if (dense[i] != NOT_FOUND)\r
 257                 count++;\r
 258         }\r
 259         count += superIds.length;\r
 260         Object[] result = new Object[count];\r
 261         System.arraycopy(superIds, 0, result, 0, superIds.length);\r
 262         for (int i=last-1; i >= 0; i--) {\r
 263             if (dense[i] != NOT_FOUND)\r
 264                 result[--count] = new Integer(i);\r
 265         }\r
 266         return result;\r
 267     }\r
 268     \r
 269     public Object getDefaultValue(Class hint) {\r
 270         if (hint == ScriptRuntime.NumberClass) {\r
 271             Context cx = Context.getContext();\r
 272             if (cx.getLanguageVersion() == Context.VERSION_1_2)\r
 273                 return new Long(length);\r
 274         }\r
 275         return super.getDefaultValue(hint);\r
 276     }\r
 277 \r
 278     /**\r
 279      * See ECMA 15.4.1,2\r
 280      */\r
 281     private static Object jsConstructor(Context cx, Scriptable scope, \r
 282                                         Object[] args, IdFunction ctorObj,\r
 283                                         boolean inNewExpr)\r
 284         throws JavaScriptException\r
 285     {\r
 286         if (!inNewExpr) {\r
 287             // FunctionObject.construct will set up parent, proto\r
 288             return ctorObj.construct(cx, scope, args);\r
 289         }\r
 290         if (args.length == 0)\r
 291             return new NativeArray();\r
 292 \r
 293         // Only use 1 arg as first element for version 1.2; for\r
 294         // any other version (including 1.3) follow ECMA and use it as\r
 295         // a length.\r
 296         if (cx.getLanguageVersion() == cx.VERSION_1_2) {\r
 297             return new NativeArray(args);\r
 298         }\r
 299         else {\r
 300             if ((args.length > 1) || (!(args[0] instanceof Number)))\r
 301                 return new NativeArray(args);\r
 302             else {\r
 303                 long len = ScriptRuntime.toUint32(args[0]);\r
 304                 if (len != (((Number)(args[0])).doubleValue()))\r
 305                     throw Context.reportRuntimeError0("msg.arraylength.bad");\r
 306                 return new NativeArray(len);\r
 307             }\r
 308         }\r
 309     }\r
 310 \r
 311     public long jsGet_length() {\r
 312         return length;\r
 313     }\r
 314 \r
 315     private void jsSet_length(Object val) {\r
 316         /* XXX do we satisfy this?\r
 317          * 15.4.5.1 [[Put]](P, V):\r
 318          * 1. Call the [[CanPut]] method of A with name P.\r
 319          * 2. If Result(1) is false, return.\r
 320          * ?\r
 321          */\r
 322 \r
 323         if (!(val instanceof Number))\r
 324             throw Context.reportRuntimeError0("msg.arraylength.bad");\r
 325         \r
 326         long longVal = ScriptRuntime.toUint32(val);\r
 327         if (longVal != (((Number)val).doubleValue()))\r
 328             throw Context.reportRuntimeError0("msg.arraylength.bad");\r
 329 \r
 330         if (longVal < length) {\r
 331             // remove all properties between longVal and length\r
 332             if (length - longVal > 0x1000) {\r
 333                 // assume that the representation is sparse\r
 334                 Object[] e = getIds(); // will only find in object itself\r
 335                 for (int i=0; i < e.length; i++) {\r
 336                     if (e[i] instanceof String) {\r
 337                         // > MAXINT will appear as string\r
 338                         String id = (String) e[i];\r
 339                         double d = ScriptRuntime.toNumber(id);\r
 340                         if (d == d && d < length)\r
 341                             delete(id);\r
 342                         continue;\r
 343                     }\r
 344                     int index = ((Number) e[i]).intValue();\r
 345                     if (index >= longVal)\r
 346                         delete(index);\r
 347                 }\r
 348             } else {\r
 349                 // assume a dense representation\r
 350                 for (long i=longVal; i < length; i++) {\r
 351                     // only delete if defined in the object itself\r
 352                     if (hasElem(this, i))\r
 353                         ScriptRuntime.delete(this, new Long(i));\r
 354                 }\r
 355             }\r
 356         }\r
 357         length = longVal;\r
 358     }\r
 359 \r
 360     /* Support for generic Array-ish objects.  Most of the Array\r
 361      * functions try to be generic; anything that has a length\r
 362      * property is assumed to be an array.  hasLengthProperty is\r
 363      * needed in addition to getLengthProperty, because\r
 364      * getLengthProperty always succeeds - tries to convert strings, etc.\r
 365      */\r
 366     static double getLengthProperty(Scriptable obj) {\r
 367         // These will both give numeric lengths within Uint32 range.\r
 368         if (obj instanceof NativeString)\r
 369             return (double)((NativeString)obj).jsGet_length();\r
 370         if (obj instanceof NativeArray)\r
 371             return (double)((NativeArray)obj).jsGet_length();\r
 372         return ScriptRuntime.toUint32(ScriptRuntime\r
 373                                       .getProp(obj, "length", obj));\r
 374     }\r
 375 \r
 376     static boolean hasLengthProperty(Object obj) {\r
 377         if (!(obj instanceof Scriptable) || obj == Context.getUndefinedValue())\r
 378             return false;\r
 379         if (obj instanceof NativeString || obj instanceof NativeArray)\r
 380             return true;\r
 381         Scriptable sobj = (Scriptable)obj;\r
 382 \r
 383         // XXX some confusion as to whether or not to walk to get the length\r
 384         // property.  Pending review of js/[new ecma submission] treatment\r
 385         // of 'arrayness'.\r
 386 \r
 387         Object property = ScriptRuntime.getProp(sobj, "length", sobj);\r
 388         return property instanceof Number;\r
 389     }\r
 390 \r
 391     /* Utility functions to encapsulate index > Integer.MAX_VALUE\r
 392      * handling.  Also avoids unnecessary object creation that would\r
 393      * be necessary to use the general ScriptRuntime.get/setElem\r
 394      * functions... though this is probably premature optimization.\r
 395      */\r
 396     private static boolean hasElem(Scriptable target, long index) {\r
 397         return index > Integer.MAX_VALUE\r
 398                ? target.has(Long.toString(index), target)\r
 399                : target.has((int)index, target);\r
 400     }\r
 401 \r
 402     private static Object getElem(Scriptable target, long index) {\r
 403         if (index > Integer.MAX_VALUE) {\r
 404             String id = Long.toString(index);\r
 405             return ScriptRuntime.getElem(target, id, target);\r
 406         } else {\r
 407             return ScriptRuntime.getElem(target, (int)index);\r
 408         }\r
 409     }\r
 410 \r
 411     private static void setElem(Scriptable target, long index, Object value) {\r
 412         if (index > Integer.MAX_VALUE) {\r
 413             String id = Long.toString(index);\r
 414             ScriptRuntime.setElem(target, id, value, target);\r
 415         } else {\r
 416             ScriptRuntime.setElem(target, (int)index, value);\r
 417         }\r
 418     }\r
 419 \r
 420     private static String jsFunction_toString(Context cx, Scriptable thisObj,\r
 421                                               Object[] args)\r
 422         throws JavaScriptException\r
 423     {\r
 424         return toStringHelper(cx, thisObj, \r
 425                               cx.getLanguageVersion() == cx.VERSION_1_2,\r
 426                               false);\r
 427     }\r
 428     \r
 429     private static String jsFunction_toLocaleString(Context cx, \r
 430                                                     Scriptable thisObj,\r
 431                                                     Object[] args)\r
 432         throws JavaScriptException\r
 433     {\r
 434         return toStringHelper(cx, thisObj, false, true);\r
 435     }\r
 436     \r
 437     private static String toStringHelper(Context cx, Scriptable thisObj,\r
 438                                          boolean toSource, boolean toLocale)\r
 439         throws JavaScriptException\r
 440     {\r
 441         /* It's probably redundant to handle long lengths in this\r
 442          * function; StringBuffers are limited to 2^31 in java.\r
 443          */\r
 444 \r
 445         long length = (long)getLengthProperty(thisObj);\r
 446 \r
 447         StringBuffer result = new StringBuffer();\r
 448 \r
 449         if (cx.iterating == null)\r
 450             cx.iterating = new Hashtable(31);\r
 451         boolean iterating = cx.iterating.get(thisObj) == Boolean.TRUE;\r
 452 \r
 453         // whether to return '4,unquoted,5' or '[4, "quoted", 5]'\r
 454         String separator;\r
 455 \r
 456         if (toSource) {\r
 457             result.append('[');\r
 458             separator = ", ";\r
 459         } else {\r
 460             separator = ",";\r
 461         }\r
 462 \r
 463         boolean haslast = false;\r
 464         long i = 0;\r
 465 \r
 466         if (!iterating) {\r
 467             for (i = 0; i < length; i++) {\r
 468                 if (i > 0)\r
 469                     result.append(separator);\r
 470                 Object elem = getElem(thisObj, i);\r
 471                 if (elem == null || elem == Undefined.instance) {\r
 472                     haslast = false;\r
 473                     continue;\r
 474                 }\r
 475                 haslast = true;\r
 476 \r
 477                 if (elem instanceof String) {\r
 478                     if (toSource) {\r
 479                         result.append('\"');\r
 480                         result.append(ScriptRuntime.escapeString\r
 481                                       (ScriptRuntime.toString(elem)));\r
 482                         result.append('\"');\r
 483                     } else {\r
 484                         result.append(ScriptRuntime.toString(elem));\r
 485                     }\r
 486                 } else {\r
 487                     /* wrap changes to cx.iterating in a try/finally\r
 488                      * so that the reference always gets removed, and\r
 489                      * we don't leak memory.  Good place for weak\r
 490                      * references, if we had them.  */\r
 491                     try {\r
 492                         // stop recursion.\r
 493                         cx.iterating.put(thisObj, Boolean.TRUE);\r
 494                         if (toLocale && elem != Undefined.instance && \r
 495                             elem != null) \r
 496                         {\r
 497                             Scriptable obj = cx.toObject(elem, thisObj);\r
 498                             Object tls = ScriptRuntime.getProp(obj, \r
 499                                              "toLocaleString", thisObj);\r
 500                             elem = ScriptRuntime.call(cx, tls, elem, \r
 501                                                       ScriptRuntime.emptyArgs);\r
 502                         }\r
 503                         result.append(ScriptRuntime.toString(elem));\r
 504                     } finally {\r
 505                         cx.iterating.remove(thisObj);\r
 506                     }\r
 507                 }\r
 508             }\r
 509         }\r
 510 \r
 511         if (toSource) {\r
 512             //for [,,].length behavior; we want toString to be symmetric.\r
 513             if (!haslast && i > 0)\r
 514                 result.append(", ]");\r
 515             else\r
 516                 result.append(']');\r
 517         }\r
 518         return result.toString();\r
 519     }\r
 520 \r
 521     /**\r
 522      * See ECMA 15.4.4.3\r
 523      */\r
 524     private static String jsFunction_join(Context cx, Scriptable thisObj,\r
 525                                           Object[] args) \r
 526     {\r
 527         StringBuffer result = new StringBuffer();\r
 528         String separator;\r
 529 \r
 530         double length = getLengthProperty(thisObj);\r
 531 \r
 532         // if no args, use "," as separator\r
 533         if (args.length < 1) {\r
 534             separator = ",";\r
 535         } else {\r
 536             separator = ScriptRuntime.toString(args[0]);\r
 537         }\r
 538         for (long i=0; i < length; i++) {\r
 539             if (i > 0)\r
 540                 result.append(separator);\r
 541             Object temp = getElem(thisObj, i);\r
 542             if (temp == null || temp == Undefined.instance)\r
 543                 continue;\r
 544             result.append(ScriptRuntime.toString(temp));\r
 545         }\r
 546         return result.toString();\r
 547     }\r
 548 \r
 549     /**\r
 550      * See ECMA 15.4.4.4\r
 551      */\r
 552     private static Scriptable jsFunction_reverse(Context cx, \r
 553                                                  Scriptable thisObj, \r
 554                                                  Object[] args) \r
 555     {\r
 556         long len = (long)getLengthProperty(thisObj);\r
 557 \r
 558         long half = len / 2;\r
 559         for(long i=0; i < half; i++) {\r
 560             long j = len - i - 1;\r
 561             Object temp1 = getElem(thisObj, i);\r
 562             Object temp2 = getElem(thisObj, j);\r
 563             setElem(thisObj, i, temp2);\r
 564             setElem(thisObj, j, temp1);\r
 565         }\r
 566         return thisObj;\r
 567     }\r
 568 \r
 569     /**\r
 570      * See ECMA 15.4.4.5\r
 571      */\r
 572     private static Scriptable jsFunction_sort(Context cx, Scriptable scope,\r
 573                                               Scriptable thisObj, \r
 574                                               Object[] args)\r
 575         throws JavaScriptException\r
 576     {\r
 577         long length = (long)getLengthProperty(thisObj);\r
 578 \r
 579         Object compare;\r
 580         if (args.length > 0 && Undefined.instance != args[0])\r
 581             // sort with given compare function\r
 582             compare = args[0];\r
 583         else\r
 584             // sort with default compare\r
 585             compare = null;\r
 586 \r
 587 \r
 588         // OPT: Would it make sense to use the extended sort for very small\r
 589         // arrays?\r
 590 \r
 591         // Should we use the extended sort function, or the faster one?\r
 592         if (length >= Integer.MAX_VALUE) {\r
 593             qsort_extended(cx, compare, thisObj, 0, length - 1);\r
 594         } else {\r
 595             // copy the JS array into a working array, so it can be\r
 596             // sorted cheaply.\r
 597             Object[] working = new Object[(int)length];\r
 598             for (int i=0; i<length; i++) {\r
 599                 working[i] = getElem(thisObj, i);\r
 600             }\r
 601 \r
 602             qsort(cx, compare, working, 0, (int)length - 1, scope);\r
 603 \r
 604             // copy the working array back into thisObj\r
 605             for (int i=0; i<length; i++) {\r
 606                 setElem(thisObj, i, working[i]);\r
 607             }\r
 608         }\r
 609         return thisObj;\r
 610     }\r
 611 \r
 612     private static double qsortCompare(Context cx, Object jsCompare, Object x,\r
 613                                        Object y, Scriptable scope)\r
 614         throws JavaScriptException\r
 615     {\r
 616         Object undef = Undefined.instance;\r
 617 \r
 618         // sort undefined to end\r
 619         if (undef == x || undef == y) {\r
 620             if (undef != x)\r
 621                 return -1;\r
 622             if (undef != y)\r
 623                 return 1;\r
 624             return 0;\r
 625         }\r
 626 \r
 627         if (jsCompare == null) {\r
 628             // if no compare function supplied, sort lexicographically\r
 629             String a = ScriptRuntime.toString(x);\r
 630             String b = ScriptRuntime.toString(y);\r
 631 \r
 632             return a.compareTo(b);\r
 633         } else {\r
 634             // assemble args and call supplied JS compare function\r
 635             // OPT: put this argument creation in the caller and reuse it.\r
 636             // XXX what to do when compare function returns NaN?  ECMA states\r
 637             // that it's then not a 'consistent compararison function'... but\r
 638             // then what do we do?  Back out and start over with the generic\r
 639             // compare function when we see a NaN?  Throw an error?\r
 640             Object[] args = {x, y};\r
 641 //             return ScriptRuntime.toNumber(ScriptRuntime.call(jsCompare, null,\r
 642 //                                                              args));\r
 643             // for now, just ignore it:\r
 644             double d = ScriptRuntime.\r
 645                 toNumber(ScriptRuntime.call(cx, jsCompare, null, args, scope));\r
 646 \r
 647             return (d == d) ? d : 0;\r
 648         }\r
 649     }\r
 650 \r
 651     private static void qsort(Context cx, Object jsCompare, Object[] working,\r
 652                               int lo, int hi, Scriptable scope)\r
 653         throws JavaScriptException\r
 654     {\r
 655         Object pivot;\r
 656         int i, j;\r
 657         int a, b;\r
 658 \r
 659         while (lo < hi) {\r
 660             i = lo;\r
 661             j = hi;\r
 662             a = i;\r
 663             pivot = working[a];\r
 664             while (i < j) {\r
 665                 for(;;) {\r
 666                     b = j;\r
 667                     if (qsortCompare(cx, jsCompare, working[j], pivot, \r
 668                                      scope) <= 0)\r
 669                         break;\r
 670                     j--;\r
 671                 }\r
 672                 working[a] = working[b];\r
 673                 while (i < j && qsortCompare(cx, jsCompare, working[a],\r
 674                                              pivot, scope) <= 0)\r
 675                 {\r
 676                     i++;\r
 677                     a = i;\r
 678                 }\r
 679                 working[b] = working[a];\r
 680             }\r
 681             working[a] = pivot;\r
 682             if (i - lo < hi - i) {\r
 683                 qsort(cx, jsCompare, working, lo, i - 1, scope);\r
 684                 lo = i + 1;\r
 685             } else {\r
 686                 qsort(cx, jsCompare, working, i + 1, hi, scope);\r
 687                 hi = i - 1;\r
 688             }\r
 689         }\r
 690     }\r
 691 \r
 692     // A version that knows about long indices and doesn't use\r
 693     // a working array.  Probably will never be used.\r
 694     private static void qsort_extended(Context cx, Object jsCompare,\r
 695                                        Scriptable target, long lo, long hi)\r
 696         throws JavaScriptException\r
 697     {\r
 698         Object pivot;\r
 699         long i, j;\r
 700         long a, b;\r
 701 \r
 702         while (lo < hi) {\r
 703             i = lo;\r
 704             j = hi;\r
 705             a = i;\r
 706             pivot = getElem(target, a);\r
 707             while (i < j) {\r
 708                 for(;;) {\r
 709                     b = j;\r
 710                     if (qsortCompare(cx, jsCompare, getElem(target, j),\r
 711                                      pivot, target) <= 0)\r
 712                         break;\r
 713                     j--;\r
 714                 }\r
 715                 setElem(target, a, getElem(target, b));\r
 716                 while (i < j && qsortCompare(cx, jsCompare,\r
 717                                              getElem(target, a), \r
 718                                              pivot, target) <= 0)\r
 719                 {\r
 720                     i++;\r
 721                     a = i;\r
 722                 }\r
 723                 setElem(target, b, getElem(target, a));\r
 724             }\r
 725             setElem(target, a, pivot);\r
 726             if (i - lo < hi - i) {\r
 727                 qsort_extended(cx, jsCompare, target, lo, i - 1);\r
 728                 lo = i + 1;\r
 729             } else {\r
 730                 qsort_extended(cx, jsCompare, target, i + 1, hi);\r
 731                 hi = i - 1;\r
 732             }\r
 733         }\r
 734     }\r
 735 \r
 736     /**\r
 737      * Non-ECMA methods.\r
 738      */\r
 739 \r
 740     private static Object jsFunction_push(Context cx, Scriptable thisObj,\r
 741                                           Object[] args)\r
 742     {\r
 743         double length = getLengthProperty(thisObj);\r
 744         for (int i = 0; i < args.length; i++) {\r
 745             setElem(thisObj, (long)length + i, args[i]);\r
 746         }\r
 747 \r
 748         length += args.length;\r
 749         ScriptRuntime.setProp(thisObj, "length", new Double(length), thisObj);\r
 750 \r
 751         /*\r
 752          * If JS1.2, follow Perl4 by returning the last thing pushed.\r
 753          * Otherwise, return the new array length.\r
 754          */\r
 755         if (cx.getLanguageVersion() == Context.VERSION_1_2)\r
 756             // if JS1.2 && no arguments, return undefined.\r
 757             return args.length == 0\r
 758                 ? Context.getUndefinedValue()\r
 759                 : args[args.length - 1];\r
 760 \r
 761         else\r
 762             return new Long((long)length);\r
 763     }\r
 764 \r
 765     private static Object jsFunction_pop(Context cx, Scriptable thisObj,\r
 766                                          Object[] args) {\r
 767         Object result;\r
 768         double length = getLengthProperty(thisObj);\r
 769         if (length > 0) {\r
 770             length--;\r
 771 \r
 772             // Get the to-be-deleted property's value.\r
 773             result = getElem(thisObj, (long)length);\r
 774 \r
 775             // We don't need to delete the last property, because\r
 776             // setLength does that for us.\r
 777         } else {\r
 778             result = Context.getUndefinedValue();\r
 779         }\r
 780         // necessary to match js even when length < 0; js pop will give a\r
 781         // length property to any target it is called on.\r
 782         ScriptRuntime.setProp(thisObj, "length", new Double(length), thisObj);\r
 783 \r
 784         return result;\r
 785     }\r
 786 \r
 787     private static Object jsFunction_shift(Context cx, Scriptable thisObj,\r
 788                                            Object[] args)\r
 789     {\r
 790         Object result;\r
 791         double length = getLengthProperty(thisObj);\r
 792         if (length > 0) {\r
 793             long i = 0;\r
 794             length--;\r
 795 \r
 796             // Get the to-be-deleted property's value.\r
 797             result = getElem(thisObj, i);\r
 798 \r
 799             /*\r
 800              * Slide down the array above the first element.  Leave i\r
 801              * set to point to the last element.\r
 802              */\r
 803             if (length > 0) {\r
 804                 for (i = 1; i <= length; i++) {\r
 805                     Object temp = getElem(thisObj, i);\r
 806                     setElem(thisObj, i - 1, temp);\r
 807                 }\r
 808             }\r
 809             // We don't need to delete the last property, because\r
 810             // setLength does that for us.\r
 811         } else {\r
 812             result = Context.getUndefinedValue();\r
 813         }\r
 814         ScriptRuntime.setProp(thisObj, "length", new Double(length), thisObj);\r
 815         return result;\r
 816     }\r
 817 \r
 818     private static Object jsFunction_unshift(Context cx, Scriptable thisObj,\r
 819                                              Object[] args)\r
 820     {\r
 821         Object result;\r
 822         double length = (double)getLengthProperty(thisObj);\r
 823         int argc = args.length;\r
 824 \r
 825         if (args.length > 0) {\r
 826             /*  Slide up the array to make room for args at the bottom */\r
 827             if (length > 0) {\r
 828                 for (long last = (long)length - 1; last >= 0; last--) {\r
 829                     Object temp = getElem(thisObj, last);\r
 830                     setElem(thisObj, last + argc, temp);\r
 831                 }\r
 832             }\r
 833 \r
 834             /* Copy from argv to the bottom of the array. */\r
 835             for (int i = 0; i < args.length; i++) {\r
 836                 setElem(thisObj, i, args[i]);\r
 837             }\r
 838 \r
 839             /* Follow Perl by returning the new array length. */\r
 840             length += args.length;\r
 841             ScriptRuntime.setProp(thisObj, "length",\r
 842                                   new Double(length), thisObj);\r
 843         }\r
 844         return new Long((long)length);\r
 845     }\r
 846 \r
 847     private static Object jsFunction_splice(Context cx, Scriptable scope,\r
 848                                             Scriptable thisObj, Object[] args)\r
 849     {\r
 850         /* create an empty Array to return. */\r
 851         scope = getTopLevelScope(scope);\r
 852         Object result = ScriptRuntime.newObject(cx, scope, "Array", null);\r
 853         int argc = args.length;\r
 854         if (argc == 0)\r
 855             return result;\r
 856         double length = getLengthProperty(thisObj);\r
 857 \r
 858         /* Convert the first argument into a starting index. */\r
 859         double begin = ScriptRuntime.toInteger(args[0]);\r
 860         double end;\r
 861         double delta;\r
 862         double count;\r
 863 \r
 864         if (begin < 0) {\r
 865             begin += length;\r
 866             if (begin < 0)\r
 867                 begin = 0;\r
 868         } else if (begin > length) {\r
 869             begin = length;\r
 870         }\r
 871         argc--;\r
 872 \r
 873         /* Convert the second argument from a count into a fencepost index. */\r
 874         delta = length - begin;\r
 875 \r
 876         if (args.length == 1) {\r
 877             count = delta;\r
 878             end = length;\r
 879         } else {\r
 880             count = ScriptRuntime.toInteger(args[1]);\r
 881             if (count < 0)\r
 882                 count = 0;\r
 883             else if (count > delta)\r
 884                 count = delta;\r
 885             end = begin + count;\r
 886 \r
 887             argc--;\r
 888         }\r
 889 \r
 890         long lbegin = (long)begin;\r
 891         long lend = (long)end;\r
 892 \r
 893         /* If there are elements to remove, put them into the return value. */\r
 894         if (count > 0) {\r
 895             if (count == 1\r
 896                 && (cx.getLanguageVersion() == Context.VERSION_1_2))\r
 897             {\r
 898                 /*\r
 899                  * JS lacks "list context", whereby in Perl one turns the\r
 900                  * single scalar that's spliced out into an array just by\r
 901                  * assigning it to @single instead of $single, or by using it\r
 902                  * as Perl push's first argument, for instance.\r
 903                  *\r
 904                  * JS1.2 emulated Perl too closely and returned a non-Array for\r
 905                  * the single-splice-out case, requiring callers to test and\r
 906                  * wrap in [] if necessary.  So JS1.3, default, and other\r
 907                  * versions all return an array of length 1 for uniformity.\r
 908                  */\r
 909                 result = getElem(thisObj, lbegin);\r
 910             } else {\r
 911                 for (long last = lbegin; last < lend; last++) {\r
 912                     Scriptable resultArray = (Scriptable)result;\r
 913                     Object temp = getElem(thisObj, last);\r
 914                     setElem(resultArray, last - lbegin, temp);\r
 915                 }\r
 916             }\r
 917         } else if (count == 0\r
 918                    && cx.getLanguageVersion() == Context.VERSION_1_2)\r
 919         {\r
 920             /* Emulate C JS1.2; if no elements are removed, return undefined. */\r
 921             result = Context.getUndefinedValue();\r
 922         }\r
 923 \r
 924         /* Find the direction (up or down) to copy and make way for argv. */\r
 925         delta = argc - count;\r
 926 \r
 927         if (delta > 0) {\r
 928             for (long last = (long)length - 1; last >= lend; last--) {\r
 929                 Object temp = getElem(thisObj, last);\r
 930                 setElem(thisObj, last + (long)delta, temp);\r
 931             }\r
 932         } else if (delta < 0) {\r
 933             for (long last = lend; last < length; last++) {\r
 934                 Object temp = getElem(thisObj, last);\r
 935                 setElem(thisObj, last + (long)delta, temp);\r
 936             }\r
 937         }\r
 938 \r
 939         /* Copy from argv into the hole to complete the splice. */\r
 940         int argoffset = args.length - argc;\r
 941         for (int i = 0; i < argc; i++) {\r
 942             setElem(thisObj, lbegin + i, args[i + argoffset]);\r
 943         }\r
 944 \r
 945         /* Update length in case we deleted elements from the end. */\r
 946         ScriptRuntime.setProp(thisObj, "length",\r
 947                               new Double(length + delta), thisObj);\r
 948         return result;\r
 949     }\r
 950 \r
 951     /*\r
 952      * Python-esque sequence operations.\r
 953      */\r
 954     private static Scriptable jsFunction_concat(Context cx, Scriptable scope, \r
 955                                                 Scriptable thisObj,\r
 956                                                 Object[] args)\r
 957     {\r
 958         /* Concat tries to keep the definition of an array as general\r
 959          * as possible; if it finds that an object has a numeric\r
 960          * 'length' property, then it treats that object as an array.\r
 961          * This treats string atoms and string objects differently; as\r
 962          * string objects have a length property and are accessible by\r
 963          * index, they get exploded into arrays when added, while\r
 964          * atomic strings are just added as strings.\r
 965          */\r
 966 \r
 967         // create an empty Array to return.\r
 968         scope = getTopLevelScope(scope);\r
 969         Scriptable result = ScriptRuntime.newObject(cx, scope, "Array", null);\r
 970         double length;\r
 971         long slot = 0;\r
 972 \r
 973         /* Put the target in the result array; only add it as an array\r
 974          * if it looks like one.\r
 975          */\r
 976         if (hasLengthProperty(thisObj)) {\r
 977             length = getLengthProperty(thisObj);\r
 978 \r
 979             // Copy from the target object into the result\r
 980             for (slot = 0; slot < length; slot++) {\r
 981                 Object temp = getElem(thisObj, slot);\r
 982                 setElem(result, slot, temp);\r
 983             }\r
 984         } else {\r
 985             setElem(result, slot++, thisObj);\r
 986         }\r
 987 \r
 988         /* Copy from the arguments into the result.  If any argument\r
 989          * has a numeric length property, treat it as an array and add\r
 990          * elements separately; otherwise, just copy the argument.\r
 991          */\r
 992         for (int i = 0; i < args.length; i++) {\r
 993             if (hasLengthProperty(args[i])) {\r
 994                 // hasLengthProperty => instanceOf Scriptable.\r
 995                 Scriptable arg = (Scriptable)args[i];\r
 996                 length = getLengthProperty(arg);\r
 997                 for (long j = 0; j < length; j++, slot++) {\r
 998                     Object temp = getElem(arg, j);\r
 999                     setElem(result, slot, temp);\r
1000                 }\r
1001             } else {\r
1002                 setElem(result, slot++, args[i]);\r
1003             }\r
1004         }\r
1005         return result;\r
1006     }\r
1007 \r
1008     private Scriptable jsFunction_slice(Context cx, Scriptable thisObj,\r
1009                                         Object[] args)\r
1010     {\r
1011         Scriptable scope = getTopLevelScope(this);\r
1012         Scriptable result = ScriptRuntime.newObject(cx, scope, "Array", null);\r
1013         double length = getLengthProperty(thisObj);\r
1014 \r
1015         double begin = 0;\r
1016         double end = length;\r
1017 \r
1018         if (args.length > 0) {\r
1019             begin = ScriptRuntime.toInteger(args[0]);\r
1020             if (begin < 0) {\r
1021                 begin += length;\r
1022                 if (begin < 0)\r
1023                     begin = 0;\r
1024             } else if (begin > length) {\r
1025                 begin = length;\r
1026             }\r
1027 \r
1028             if (args.length > 1) {\r
1029                 end = ScriptRuntime.toInteger(args[1]);\r
1030                 if (end < 0) {\r
1031                     end += length;\r
1032                     if (end < 0)\r
1033                         end = 0;\r
1034                 } else if (end > length) {\r
1035                     end = length;\r
1036                 }\r
1037             }\r
1038         }\r
1039 \r
1040         long lbegin = (long)begin;\r
1041         long lend = (long)end;\r
1042         for (long slot = lbegin; slot < lend; slot++) {\r
1043             Object temp = getElem(thisObj, slot);\r
1044             setElem(result, slot - lbegin, temp);\r
1045         }\r
1046 \r
1047         return result;\r
1048     }\r
1049 \r
1050     protected int maxInstanceId() { return MAX_INSTANCE_ID; }\r
1051 \r
1052     protected String getIdName(int id) {\r
1053         if (id == Id_length) { return "length"; }\r
1054 \r
1055         if (prototypeFlag) {\r
1056             switch (id) {\r
1057                 case Id_constructor:     return "constructor";\r
1058                 case Id_toString:        return "toString";\r
1059                 case Id_toLocaleString:  return "toLocaleString";\r
1060                 case Id_join:            return "join";\r
1061                 case Id_reverse:         return "reverse";\r
1062                 case Id_sort:            return "sort";\r
1063                 case Id_push:            return "push";\r
1064                 case Id_pop:             return "pop";\r
1065                 case Id_shift:           return "shift";\r
1066                 case Id_unshift:         return "unshift";\r
1067                 case Id_splice:          return "splice";\r
1068                 case Id_concat:          return "concat";\r
1069                 case Id_slice:           return "slice";\r
1070             }\r
1071         }\r
1072         return null;\r
1073     }\r
1074 \r
1075     private static final int\r
1076         Id_length        =  1,\r
1077         MAX_INSTANCE_ID  =  1;\r
1078 \r
1079     protected int mapNameToId(String s) {\r
1080         if (s.equals("length")) { return Id_length; }\r
1081         else if (prototypeFlag) { \r
1082             return toPrototypeId(s); \r
1083         }\r
1084         return 0;\r
1085     }\r
1086 \r
1087 // #string_id_map#\r
1088 \r
1089     private static int toPrototypeId(String s) {\r
1090         int id;\r
1091 // #generated# Last update: 2001-04-23 11:46:01 GMT+02:00\r
1092         L0: { id = 0; String X = null; int c;\r
1093             L: switch (s.length()) {\r
1094             case 3: X="pop";id=Id_pop; break L;\r
1095             case 4: c=s.charAt(0);\r
1096                 if (c=='j') { X="join";id=Id_join; }\r
1097                 else if (c=='p') { X="push";id=Id_push; }\r
1098                 else if (c=='s') { X="sort";id=Id_sort; }\r
1099                 break L;\r
1100             case 5: c=s.charAt(1);\r
1101                 if (c=='h') { X="shift";id=Id_shift; }\r
1102                 else if (c=='l') { X="slice";id=Id_slice; }\r
1103                 break L;\r
1104             case 6: c=s.charAt(0);\r
1105                 if (c=='c') { X="concat";id=Id_concat; }\r
1106                 else if (c=='l') { X="length";id=Id_length; }\r
1107                 else if (c=='s') { X="splice";id=Id_splice; }\r
1108                 break L;\r
1109             case 7: c=s.charAt(0);\r
1110                 if (c=='r') { X="reverse";id=Id_reverse; }\r
1111                 else if (c=='u') { X="unshift";id=Id_unshift; }\r
1112                 break L;\r
1113             case 8: X="toString";id=Id_toString; break L;\r
1114             case 11: X="constructor";id=Id_constructor; break L;\r
1115             case 14: X="toLocaleString";id=Id_toLocaleString; break L;\r
1116             }\r
1117             if (X!=null && X!=s && !X.equals(s)) id = 0;\r
1118         }\r
1119 // #/generated#\r
1120         return id;\r
1121     }\r
1122 \r
1123     private static final int\r
1124         Id_constructor          = MAX_INSTANCE_ID + 1,\r
1125         Id_toString             = MAX_INSTANCE_ID + 2,\r
1126         Id_toLocaleString       = MAX_INSTANCE_ID + 3,\r
1127         Id_join                 = MAX_INSTANCE_ID + 4,\r
1128         Id_reverse              = MAX_INSTANCE_ID + 5,\r
1129         Id_sort                 = MAX_INSTANCE_ID + 6,\r
1130         Id_push                 = MAX_INSTANCE_ID + 7,\r
1131         Id_pop                  = MAX_INSTANCE_ID + 8,\r
1132         Id_shift                = MAX_INSTANCE_ID + 9,\r
1133         Id_unshift              = MAX_INSTANCE_ID + 10,\r
1134         Id_splice               = MAX_INSTANCE_ID + 11,\r
1135         Id_concat               = MAX_INSTANCE_ID + 12,\r
1136         Id_slice                = MAX_INSTANCE_ID + 13,\r
1137 \r
1138         MAX_PROTOTYPE_ID        = MAX_INSTANCE_ID + 13;\r
1139 \r
1140 // #/string_id_map#\r
1141 \r
1142     private long length;\r
1143     private Object[] dense;\r
1144     private static final int maximumDenseLength = 10000;\r
1145     \r
1146     private boolean prototypeFlag;\r
1147 }\r