1 /*
   2  * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.objects;
  27 
  28 import static jdk.nashorn.internal.runtime.ECMAErrors.rangeError;
  29 import static jdk.nashorn.internal.runtime.ECMAErrors.typeError;
  30 import static jdk.nashorn.internal.runtime.PropertyDescriptor.VALUE;
  31 import static jdk.nashorn.internal.runtime.PropertyDescriptor.WRITABLE;
  32 import static jdk.nashorn.internal.runtime.arrays.ArrayLikeIterator.arrayLikeIterator;
  33 import static jdk.nashorn.internal.runtime.arrays.ArrayLikeIterator.reverseArrayLikeIterator;
  34 
  35 import java.lang.invoke.MethodHandle;
  36 import java.util.ArrayList;
  37 import java.util.Arrays;
  38 import java.util.Collections;
  39 import java.util.Comparator;
  40 import java.util.Iterator;
  41 import java.util.List;
  42 import jdk.nashorn.internal.objects.annotations.Attribute;
  43 import jdk.nashorn.internal.objects.annotations.Constructor;
  44 import jdk.nashorn.internal.objects.annotations.Function;
  45 import jdk.nashorn.internal.objects.annotations.Getter;
  46 import jdk.nashorn.internal.objects.annotations.ScriptClass;
  47 import jdk.nashorn.internal.objects.annotations.Setter;
  48 import jdk.nashorn.internal.objects.annotations.SpecializedConstructor;
  49 import jdk.nashorn.internal.objects.annotations.Where;
  50 import jdk.nashorn.internal.runtime.JSType;
  51 import jdk.nashorn.internal.runtime.PropertyDescriptor;
  52 import jdk.nashorn.internal.runtime.ScriptFunction;
  53 import jdk.nashorn.internal.runtime.ScriptObject;
  54 import jdk.nashorn.internal.runtime.ScriptRuntime;
  55 import jdk.nashorn.internal.runtime.Undefined;
  56 import jdk.nashorn.internal.runtime.arrays.ArrayData;
  57 import jdk.nashorn.internal.runtime.arrays.ArrayIndex;
  58 import jdk.nashorn.internal.runtime.arrays.ArrayLikeIterator;
  59 import jdk.nashorn.internal.runtime.arrays.IteratorAction;
  60 import jdk.nashorn.internal.runtime.linker.Bootstrap;
  61 import jdk.nashorn.internal.runtime.linker.InvokeByName;
  62 
  63 /**
  64  * Runtime representation of a JavaScript array. NativeArray only holds numeric
  65  * keyed values. All other values are stored in spill.
  66  */
  67 @ScriptClass("Array")
  68 public final class NativeArray extends ScriptObject {
  69     private static final InvokeByName JOIN = new InvokeByName("join", ScriptObject.class);
  70 
  71     private static final MethodHandle EVERY_CALLBACK_INVOKER   = createIteratorCallbackInvoker(boolean.class);
  72     private static final MethodHandle SOME_CALLBACK_INVOKER    = createIteratorCallbackInvoker(boolean.class);
  73     private static final MethodHandle FOREACH_CALLBACK_INVOKER = createIteratorCallbackInvoker(void.class);
  74     private static final MethodHandle MAP_CALLBACK_INVOKER     = createIteratorCallbackInvoker(Object.class);
  75     private static final MethodHandle FILTER_CALLBACK_INVOKER  = createIteratorCallbackInvoker(boolean.class);
  76 
  77     private static final MethodHandle REDUCE_CALLBACK_INVOKER = Bootstrap.createDynamicInvoker("dyn:call", Object.class,
  78             Object.class, Undefined.class, Object.class, Object.class, int.class, Object.class);
  79     private static final MethodHandle CALL_CMP                = Bootstrap.createDynamicInvoker("dyn:call", int.class,
  80             ScriptFunction.class, Object.class, Object.class, Object.class);
  81 
  82     private static final InvokeByName TO_LOCALE_STRING = new InvokeByName("toLocaleString", ScriptObject.class, String.class);
  83 
  84 
  85     /*
  86      * Constructors.
  87      */
  88     NativeArray() {
  89         this(ArrayData.initialArray());
  90     }
  91 
  92     NativeArray(final long length) {
  93         // TODO assert valid index in long before casting
  94         this(ArrayData.allocate((int) length));
  95     }
  96 
  97     NativeArray(final int[] array) {
  98         this(ArrayData.allocate(array));
  99     }
 100 
 101     NativeArray(final long[] array) {
 102         this(ArrayData.allocate(array));
 103     }
 104 
 105     NativeArray(final double[] array) {
 106         this(ArrayData.allocate(array));
 107     }
 108 
 109     NativeArray(final Object[] array) {
 110         this(ArrayData.allocate(array.length));
 111 
 112         ArrayData arrayData = this.getArray();
 113         arrayData.ensure(array.length - 1);
 114 
 115         for (int index = 0; index < array.length; index++) {
 116             final Object value = array[index];
 117 
 118             if (value == ScriptRuntime.EMPTY) {
 119                 arrayData = arrayData.delete(index);
 120             } else {
 121                 arrayData = arrayData.set(index, value, isStrictContext());
 122             }
 123         }
 124 
 125         this.setArray(arrayData);
 126     }
 127 
 128     private NativeArray(final ArrayData arrayData) {
 129         setProto(Global.instance().getArrayPrototype());
 130         this.setArray(arrayData);
 131         this.setIsArray();
 132     }
 133 
 134     @Override
 135     public String getClassName() {
 136         return "Array";
 137     }
 138 
 139     @Override
 140     public Object getLength() {
 141         return getArray().length() & JSType.MAX_UINT;
 142     }
 143 
 144     /**
 145      * ECMA 15.4.5.1 [[DefineOwnProperty]] ( P, Desc, Throw )
 146      */
 147     @Override
 148     public boolean defineOwnProperty(final String key, final Object propertyDesc, final boolean reject) {
 149         final PropertyDescriptor desc = toPropertyDescriptor(Global.instance(), propertyDesc);
 150 
 151         // never be undefined as "length" is always defined and can't be deleted for arrays
 152         // Step 1
 153         final PropertyDescriptor oldLenDesc = (PropertyDescriptor) super.getOwnPropertyDescriptor("length");
 154 
 155         // Step 2
 156         // get old length and convert to long
 157         long oldLen = NativeArray.validLength(oldLenDesc.getValue(), true);
 158 
 159         // Step 3
 160         if ("length".equals(key)) {
 161             // Step 3a
 162             if (!desc.has(VALUE)) {
 163                 return super.defineOwnProperty("length", propertyDesc, reject);
 164             }
 165 
 166             // Step 3b
 167             final PropertyDescriptor newLenDesc = desc;
 168 
 169             // Step 3c and 3d - get new length and convert to long
 170             final long newLen = NativeArray.validLength(newLenDesc.getValue(), true);
 171 
 172             // Step 3e
 173             newLenDesc.setValue(newLen);
 174 
 175             // Step 3f
 176             // increasing array length - just need to set new length value (and attributes if any) and return
 177             if (newLen >= oldLen) {
 178                 return super.defineOwnProperty("length", newLenDesc, reject);
 179             }
 180 
 181             // Step 3g
 182             if (!oldLenDesc.isWritable()) {
 183                 if (reject) {
 184                     throw typeError("property.not.writable", "length", ScriptRuntime.safeToString(this));
 185                 }
 186                 return false;
 187             }
 188 
 189             // Step 3h and 3i
 190             final boolean newWritable = (!newLenDesc.has(WRITABLE) || newLenDesc.isWritable());
 191             if (!newWritable) {
 192                 newLenDesc.setWritable(true);
 193             }
 194 
 195             // Step 3j and 3k
 196             final boolean succeeded = super.defineOwnProperty("length", newLenDesc, reject);
 197             if (!succeeded) {
 198                 return false;
 199             }
 200 
 201             // Step 3l
 202             // make sure that length is set till the point we can delete the old elements
 203             while (newLen < oldLen) {
 204                 oldLen--;
 205                 final boolean deleteSucceeded = delete(oldLen, false);
 206                 if (!deleteSucceeded) {
 207                     newLenDesc.setValue(oldLen + 1);
 208                     if (!newWritable) {
 209                         newLenDesc.setWritable(false);
 210                     }
 211                     super.defineOwnProperty("length", newLenDesc, false);
 212                     if (reject) {
 213                         throw typeError("property.not.writable", "length", ScriptRuntime.safeToString(this));
 214                     }
 215                     return false;
 216                 }
 217             }
 218 
 219             // Step 3m
 220             if (!newWritable) {
 221                 // make 'length' property not writable
 222                 final ScriptObject newDesc = Global.newEmptyInstance();
 223                 newDesc.set(WRITABLE, false, false);
 224                 return super.defineOwnProperty("length", newDesc, false);
 225             }
 226 
 227             return true;
 228         }
 229 
 230         // Step 4a
 231         final int index = ArrayIndex.getArrayIndexNoThrow(key);
 232         if (ArrayIndex.isValidArrayIndex(index)) {
 233             final long longIndex = ArrayIndex.toLongIndex(index);
 234             // Step 4b
 235             // setting an element beyond current length, but 'length' is not writable
 236             if (longIndex >= oldLen && !oldLenDesc.isWritable()) {
 237                 if (reject) {
 238                     throw typeError("property.not.writable", Long.toString(longIndex), ScriptRuntime.safeToString(this));
 239                 }
 240                 return false;
 241             }
 242 
 243             // Step 4c
 244             // set the new array element
 245             final boolean succeeded = super.defineOwnProperty(key, propertyDesc, false);
 246 
 247             // Step 4d
 248             if (!succeeded) {
 249                 if (reject) {
 250                     throw typeError("cant.redefine.property", key, ScriptRuntime.safeToString(this));
 251                 }
 252                 return false;
 253             }
 254 
 255             // Step 4e -- adjust new length based on new element index that is set
 256             if (longIndex >= oldLen) {
 257                 oldLenDesc.setValue(longIndex + 1);
 258                 super.defineOwnProperty("length", oldLenDesc, false);
 259             }
 260 
 261             // Step 4f
 262             return true;
 263         }
 264 
 265         // not an index property
 266         return super.defineOwnProperty(key, propertyDesc, reject);
 267     }
 268 
 269     /**
 270      * Return the array contents upcasted as an ObjectArray, regardless of
 271      * representation
 272      *
 273      * @return an object array
 274      */
 275     public Object[] asObjectArray() {
 276         return getArray().asObjectArray();
 277     }
 278 
 279     /**
 280      * ECMA 15.4.3.2 Array.isArray ( arg )
 281      *
 282      * @param self self reference
 283      * @param arg  argument - object to check
 284      * @return true if argument is an array
 285      */
 286     @Function(attributes = Attribute.NOT_ENUMERABLE, where = Where.CONSTRUCTOR)
 287     public static Object isArray(final Object self, final Object arg) {
 288         return isArray(arg) || (arg == Global.instance().getArrayPrototype())
 289                 || (arg instanceof NativeRegExpExecResult);
 290     }
 291 
 292     /**
 293      * Length getter
 294      * @param self self reference
 295      * @return the length of the object
 296      */
 297     @Getter(attributes = Attribute.NOT_ENUMERABLE | Attribute.NOT_CONFIGURABLE)
 298     public static Object length(final Object self) {
 299         if (isArray(self)) {
 300             return ((NativeArray) self).getArray().length() & JSType.MAX_UINT;
 301         }
 302 
 303         return 0;
 304     }
 305 
 306     /**
 307      * Length setter
 308      * @param self   self reference
 309      * @param length new length property
 310      */
 311     @Setter(attributes = Attribute.NOT_ENUMERABLE | Attribute.NOT_CONFIGURABLE)
 312     public static void length(final Object self, final Object length) {
 313         if (isArray(self)) {
 314             ((NativeArray) self).setLength(validLength(length, true));
 315         }
 316     }
 317 
 318     static long validLength(final Object length, final boolean reject) {
 319         final double doubleLength = JSType.toNumber(length);
 320         if (!Double.isNaN(doubleLength) && JSType.isRepresentableAsLong(doubleLength)) {
 321             final long len = (long) doubleLength;
 322             if (len >= 0 && len <= JSType.MAX_UINT) {
 323                 return len;
 324             }
 325         }
 326         if (reject) {
 327             throw rangeError("inappropriate.array.length", ScriptRuntime.safeToString(length));
 328         }
 329         return -1;
 330     }
 331 
 332     /**
 333      * ECMA 15.4.4.2 Array.prototype.toString ( )
 334      *
 335      * @param self self reference
 336      * @return string representation of array
 337      */
 338     @Function(attributes = Attribute.NOT_ENUMERABLE)
 339     public static Object toString(final Object self) {
 340         if (self instanceof ScriptObject) {
 341             final ScriptObject sobj = (ScriptObject) self;
 342             try {
 343                 final Object join = JOIN.getGetter().invokeExact(sobj);
 344                 if (join instanceof ScriptFunction) {
 345                     return JOIN.getInvoker().invokeExact(join, sobj);
 346                 }
 347             } catch (final RuntimeException | Error e) {
 348                 throw e;
 349             } catch (final Throwable t) {
 350                 throw new RuntimeException(t);
 351             }
 352         }
 353 
 354         // FIXME: should lookup Object.prototype.toString and call that?
 355         return ScriptRuntime.builtinObjectToString(self);
 356     }
 357 
 358     /**
 359      * ECMA 15.4.4.3 Array.prototype.toLocaleString ( )
 360      *
 361      * @param self self reference
 362      * @return locale specific string representation for array
 363      */
 364     @Function(attributes = Attribute.NOT_ENUMERABLE)
 365     public static Object toLocaleString(final Object self) {
 366         final StringBuilder sb = new StringBuilder();
 367         final Iterator<Object> iter = arrayLikeIterator(self, true);
 368 
 369         while (iter.hasNext()) {
 370             final Object obj = iter.next();
 371 
 372             if (obj != null && obj != ScriptRuntime.UNDEFINED) {
 373                 final Object val = JSType.toScriptObject(obj);
 374 
 375                 try {
 376                     if (val instanceof ScriptObject) {
 377                         final ScriptObject sobj           = (ScriptObject)val;
 378                         final Object       toLocaleString = TO_LOCALE_STRING.getGetter().invokeExact(sobj);
 379 
 380                         if (toLocaleString instanceof ScriptFunction) {
 381                             sb.append((String)TO_LOCALE_STRING.getInvoker().invokeExact(toLocaleString, sobj));
 382                         } else {
 383                             throw typeError("not.a.function", "toLocaleString");
 384                         }
 385                     }
 386                 } catch (final Error|RuntimeException t) {
 387                     throw t;
 388                 } catch (final Throwable t) {
 389                     throw new RuntimeException(t);
 390                 }
 391             }
 392 
 393             if (iter.hasNext()) {
 394                 sb.append(",");
 395             }
 396         }
 397 
 398         return sb.toString();
 399     }
 400 
 401     /**
 402      * ECMA 15.4.2.2 new Array (len)
 403      *
 404      * @param newObj was the new operator used to instantiate this array
 405      * @param self   self reference
 406      * @param args   arguments (length)
 407      * @return the new NativeArray
 408      */
 409     @Constructor(arity = 1)
 410     public static Object construct(final boolean newObj, final Object self, final Object... args) {
 411         switch (args.length) {
 412         case 0:
 413             return new NativeArray(0);
 414         case 1:
 415             final Object len = args[0];
 416             if (len instanceof Number) {
 417                 long length;
 418                 if (len instanceof Integer || len instanceof Long) {
 419                     length = ((Number) len).longValue();
 420                     if (length >= 0 && length < 0xffff_ffffL) {
 421                         return new NativeArray(length);
 422                     }
 423                 }
 424 
 425                 length = JSType.toUint32(len);
 426 
 427                 /*
 428                  * If the argument len is a Number and ToUint32(len) is equal to
 429                  * len, then the length property of the newly constructed object
 430                  * is set to ToUint32(len). If the argument len is a Number and
 431                  * ToUint32(len) is not equal to len, a RangeError exception is
 432                  * thrown.
 433                  */
 434                 final double numberLength = ((Number) len).doubleValue();
 435                 if (length != numberLength) {
 436                     throw rangeError("inappropriate.array.length", JSType.toString(numberLength));
 437                 }
 438 
 439                 return new NativeArray(length);
 440             }
 441             /*
 442              * If the argument len is not a Number, then the length property of
 443              * the newly constructed object is set to 1 and the 0 property of
 444              * the newly constructed object is set to len
 445              */
 446             return new NativeArray(new Object[]{args[0]});
 447             //fallthru
 448         default:
 449             return new NativeArray(args);
 450         }
 451     }
 452 
 453     /**
 454      * ECMA 15.4.2.2 new Array (len)
 455      *
 456      * Specialized constructor for zero arguments - empty array
 457      *
 458      * @param newObj was the new operator used to instantiate this array
 459      * @param self   self reference
 460      * @return the new NativeArray
 461      */
 462     @SpecializedConstructor
 463     public static Object construct(final boolean newObj, final Object self) {
 464         return new NativeArray(0);
 465     }
 466 
 467     /**
 468      * ECMA 15.4.2.2 new Array (len)
 469      *
 470      * Specialized constructor for one integer argument (length)
 471      *
 472      * @param newObj was the new operator used to instantiate this array
 473      * @param self   self reference
 474      * @param length array length
 475      * @return the new NativeArray
 476      */
 477     @SpecializedConstructor
 478     public static Object construct(final boolean newObj, final Object self, final int length) {
 479         if (length >= 0) {
 480             return new NativeArray(length);
 481         }
 482 
 483         return construct(newObj, self, new Object[]{length});
 484     }
 485 
 486     /**
 487      * ECMA 15.4.2.2 new Array (len)
 488      *
 489      * Specialized constructor for one long argument (length)
 490      *
 491      * @param newObj was the new operator used to instantiate this array
 492      * @param self   self reference
 493      * @param length array length
 494      * @return the new NativeArray
 495      */
 496     @SpecializedConstructor
 497     public static Object construct(final boolean newObj, final Object self, final long length) {
 498         if (length >= 0L && length <= JSType.MAX_UINT) {
 499             return new NativeArray(length);
 500         }
 501 
 502         return construct(newObj, self, new Object[]{length});
 503     }
 504 
 505     /**
 506      * ECMA 15.4.2.2 new Array (len)
 507      *
 508      * Specialized constructor for one double argument (length)
 509      *
 510      * @param newObj was the new operator used to instantiate this array
 511      * @param self   self reference
 512      * @param length array length
 513      * @return the new NativeArray
 514      */
 515     @SpecializedConstructor
 516     public static Object construct(final boolean newObj, final Object self, final double length) {
 517         final long uint32length = JSType.toUint32(length);
 518 
 519         if (uint32length == length) {
 520             return new NativeArray(uint32length);
 521         }
 522 
 523         return construct(newObj, self, new Object[]{length});
 524     }
 525 
 526     /**
 527      * ECMA 15.4.4.4 Array.prototype.concat ( [ item1 [ , item2 [ , ... ] ] ] )
 528      *
 529      * @param self self reference
 530      * @param args arguments to concat
 531      * @return resulting NativeArray
 532      */
 533     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 534     public static Object concat(final Object self, final Object... args) {
 535         final ArrayList<Object> list = new ArrayList<>();
 536         final Object selfToObject = Global.toObject(self);
 537 
 538         if (isArray(selfToObject)) {
 539             final Iterator<Object> iter = arrayLikeIterator(selfToObject, true);
 540             while (iter.hasNext()) {
 541                 list.add(iter.next());
 542             }
 543         } else {
 544             // single element, add it
 545             list.add(selfToObject);
 546         }
 547 
 548         for (final Object obj : args) {
 549             if (isArray(obj) || obj instanceof Iterable || (obj != null && obj.getClass().isArray())) {
 550                 final Iterator<Object> iter = arrayLikeIterator(obj, true);
 551                 if (iter.hasNext()) {
 552                     while (iter.hasNext()) {
 553                         list.add(iter.next());
 554                     }
 555                 } else if (!isArray(obj)) {
 556                     list.add(obj); // add empty object, but not an empty array
 557                 }
 558             } else {
 559                 // single element, add it
 560                 list.add(obj);
 561             }
 562         }
 563 
 564         return new NativeArray(list.toArray());
 565     }
 566 
 567     /**
 568      * ECMA 15.4.4.5 Array.prototype.join (separator)
 569      *
 570      * @param self      self reference
 571      * @param separator element separator
 572      * @return string representation after join
 573      */
 574     @Function(attributes = Attribute.NOT_ENUMERABLE)
 575     public static Object join(final Object self, final Object separator) {
 576         final String           sep  = separator == ScriptRuntime.UNDEFINED ? "," : JSType.toString(separator);
 577         final StringBuilder    sb   = new StringBuilder();
 578         final Iterator<Object> iter = arrayLikeIterator(self, true);
 579 
 580         while (iter.hasNext()) {
 581             final Object obj = iter.next();
 582 
 583             if (obj != null && obj != ScriptRuntime.UNDEFINED) {
 584                 sb.append(JSType.toString(obj));
 585             }
 586 
 587             if (iter.hasNext()) {
 588                 sb.append(sep);
 589             }
 590         }
 591 
 592         return sb.toString();
 593     }
 594 
 595     /**
 596      * ECMA 15.4.4.6 Array.prototype.pop ()
 597      *
 598      * @param self self reference
 599      * @return array after pop
 600      */
 601     @Function(attributes = Attribute.NOT_ENUMERABLE)
 602     public static Object pop(final Object self) {
 603         try {
 604             final ScriptObject sobj = (ScriptObject)self;
 605             final boolean strict    = sobj.isStrictContext();
 606 
 607             if (bulkable(sobj)) {
 608                 return sobj.getArray().pop();
 609             }
 610 
 611             final long len = JSType.toUint32(sobj.getLength());
 612 
 613             if (len == 0) {
 614                 sobj.set("length", 0, strict);
 615                 return ScriptRuntime.UNDEFINED;
 616             }
 617 
 618             final long   index   = len - 1;
 619             final Object element = sobj.get(index);
 620 
 621             sobj.delete(index, strict);
 622             sobj.set("length", index, strict);
 623 
 624             return element;
 625         } catch (final ClassCastException | NullPointerException e) {
 626             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 627         }
 628     }
 629 
 630     /**
 631      * ECMA 15.4.4.7 Array.prototype.push (args...)
 632      *
 633      * @param self self reference
 634      * @param args arguments to push
 635      * @return array after pushes
 636      */
 637     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 638     public static Object push(final Object self, final Object... args) {
 639         try {
 640             final ScriptObject sobj   = (ScriptObject)self;
 641             final boolean      strict = sobj.isStrictContext();
 642 
 643             if (bulkable(sobj)) {
 644                 final NativeArray nativeArray = (NativeArray)sobj;
 645                 if (nativeArray.getArray().length() + args.length <= JSType.MAX_UINT) {
 646                     final ArrayData newData = nativeArray.getArray().push(nativeArray.isStrictContext(), args);
 647                     nativeArray.setArray(newData);
 648                     return newData.length();
 649                 }
 650                 //fallthru
 651             }
 652 
 653             long len = JSType.toUint32(sobj.getLength());
 654             for (final Object element : args) {
 655                 sobj.set(len++, element, strict);
 656             }
 657             sobj.set("length", len, strict);
 658 
 659             return len;
 660         } catch (final ClassCastException | NullPointerException e) {
 661             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 662         }
 663     }
 664 
 665     /**
 666      * ECMA 15.4.4.8 Array.prototype.reverse ()
 667      *
 668      * @param self self reference
 669      * @return reversed array
 670      */
 671     @Function(attributes = Attribute.NOT_ENUMERABLE)
 672     public static Object reverse(final Object self) {
 673         try {
 674             final ScriptObject sobj   = (ScriptObject)self;
 675             final boolean      strict = sobj.isStrictContext();
 676             final long         len    = JSType.toUint32(sobj.getLength());
 677             final long         middle = len / 2;
 678 
 679             for (long lower = 0; lower != middle; lower++) {
 680                 final long    upper       = len - lower - 1;
 681                 final Object  lowerValue  = sobj.get(lower);
 682                 final Object  upperValue  = sobj.get(upper);
 683                 final boolean lowerExists = sobj.has(lower);
 684                 final boolean upperExists = sobj.has(upper);
 685 
 686                 if (lowerExists && upperExists) {
 687                     sobj.set(lower, upperValue, strict);
 688                     sobj.set(upper, lowerValue, strict);
 689                 } else if (!lowerExists && upperExists) {
 690                     sobj.set(lower, upperValue, strict);
 691                     sobj.delete(upper, strict);
 692                 } else if (lowerExists && !upperExists) {
 693                     sobj.delete(lower, strict);
 694                     sobj.set(upper, lowerValue, strict);
 695                 }
 696             }
 697             return sobj;
 698         } catch (final ClassCastException | NullPointerException e) {
 699             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 700         }
 701     }
 702 
 703     /**
 704      * ECMA 15.4.4.9 Array.prototype.shift ()
 705      *
 706      * @param self self reference
 707      * @return shifted array
 708      */
 709     @Function(attributes = Attribute.NOT_ENUMERABLE)
 710     public static Object shift(final Object self) {
 711         final Object obj = Global.toObject(self);
 712 
 713         Object first = ScriptRuntime.UNDEFINED;
 714 
 715         if (!(obj instanceof ScriptObject)) {
 716             return first;
 717         }
 718 
 719         final ScriptObject sobj   = (ScriptObject) obj;
 720         final boolean      strict = Global.isStrict();
 721 
 722         long len = JSType.toUint32(sobj.getLength());
 723 
 724         if (len > 0) {
 725             first = sobj.get(0);
 726 
 727             if (bulkable(sobj)) {
 728                 sobj.getArray().shiftLeft(1);
 729             } else {
 730                 for (long k = 1; k < len; k++) {
 731                     sobj.set(k - 1, sobj.get(k), strict);
 732                 }
 733             }
 734             sobj.delete(--len, strict);
 735         } else {
 736             len = 0;
 737         }
 738 
 739         sobj.set("length", len, strict);
 740 
 741         return first;
 742     }
 743 
 744     /**
 745      * ECMA 15.4.4.10 Array.prototype.slice ( start [ , end ] )
 746      *
 747      * @param self  self reference
 748      * @param start start of slice (inclusive)
 749      * @param end   end of slice (optional, exclusive)
 750      * @return sliced array
 751      */
 752     @Function(attributes = Attribute.NOT_ENUMERABLE)
 753     public static Object slice(final Object self, final Object start, final Object end) {
 754         final Object       obj                 = Global.toObject(self);
 755         final ScriptObject sobj                = (ScriptObject)obj;
 756         final long         len                 = JSType.toUint32(sobj.getLength());
 757         final double       startNum            = JSType.toNumber(start);
 758         final long         relativeStartUint32 = JSType.toUint32(startNum);
 759         final long         relativeStart       = JSType.toInteger(startNum);
 760 
 761         long k = relativeStart < 0 ?
 762                 Math.max(len + relativeStart, 0) :
 763                 Math.min(
 764                     Math.max(relativeStartUint32, relativeStart),
 765                     len);
 766 
 767         final double endNum = (end == ScriptRuntime.UNDEFINED)? Double.NaN : JSType.toNumber(end);
 768         final long relativeEndUint32 = (end == ScriptRuntime.UNDEFINED)? len : JSType.toUint32(endNum);
 769         final long relativeEnd       = (end == ScriptRuntime.UNDEFINED)? len : JSType.toInteger(endNum);
 770 
 771         final long finale = relativeEnd < 0 ?
 772                 Math.max(len + relativeEnd, 0) :
 773                 Math.min(
 774                     Math.max(relativeEndUint32, relativeEnd),
 775                     len);
 776 
 777         if (k >= finale) {
 778             return new NativeArray(0);
 779         }
 780 
 781         if (bulkable(sobj)) {
 782             final NativeArray narray = (NativeArray) sobj;
 783             return new NativeArray(narray.getArray().slice(k, finale));
 784         }
 785 
 786         final NativeArray copy = new NativeArray(0);
 787         for (long n = 0; k < finale; n++, k++) {
 788             copy.defineOwnProperty((int) n, sobj.get(k));
 789         }
 790 
 791         return copy;
 792     }
 793 
 794     private static ScriptFunction compareFunction(final Object comparefn) {
 795         try {
 796             return (ScriptFunction)comparefn;
 797         } catch (final ClassCastException e) {
 798             return null; //undefined or null
 799         }
 800     }
 801 
 802     private static Object[] sort(final Object[] array, final Object comparefn) {
 803         final ScriptFunction cmp = compareFunction(comparefn);
 804 
 805         final List<Object> list = Arrays.asList(array);
 806         final Object cmpThis = cmp == null || cmp.isStrict() ? ScriptRuntime.UNDEFINED : Global.instance();
 807 
 808         Collections.sort(list, new Comparator<Object>() {
 809             @Override
 810             public int compare(final Object x, final Object y) {
 811                 if (x == ScriptRuntime.UNDEFINED && y == ScriptRuntime.UNDEFINED) {
 812                     return 0;
 813                 } else if (x == ScriptRuntime.UNDEFINED) {
 814                     return 1;
 815                 } else if (y == ScriptRuntime.UNDEFINED) {
 816                     return -1;
 817                 }
 818 
 819                 if (cmp != null) {
 820                     try {
 821                         return (int)CALL_CMP.invokeExact(cmp, cmpThis, x, y);
 822                     } catch (final RuntimeException | Error e) {
 823                         throw e;
 824                     } catch (final Throwable t) {
 825                         throw new RuntimeException(t);
 826                     }
 827                 }
 828 
 829                 return JSType.toString(x).compareTo(JSType.toString(y));
 830             }
 831         });
 832 
 833         return list.toArray(new Object[array.length]);
 834     }
 835 
 836     /**
 837      * ECMA 15.4.4.11 Array.prototype.sort ( comparefn )
 838      *
 839      * @param self       self reference
 840      * @param comparefn  element comparison function
 841      * @return sorted array
 842      */
 843     @Function(attributes = Attribute.NOT_ENUMERABLE)
 844     public static Object sort(final Object self, final Object comparefn) {
 845         try {
 846             final ScriptObject sobj    = (ScriptObject) self;
 847             final boolean      strict  = sobj.isStrictContext();
 848             final long         len     = JSType.toUint32(sobj.getLength());
 849 
 850             if (len > 1) {
 851                 final Object[] src = new Object[(int) len];
 852                 for (int i = 0; i < src.length; i++) {
 853                     src[i] = sobj.get(i);
 854                 }
 855 
 856                 final Object[] sorted = sort(src, comparefn);
 857                 assert sorted.length == src.length;
 858 
 859                 for (int i = 0; i < sorted.length; i++) {
 860                     sobj.set(i, sorted[i], strict);
 861                 }
 862             }
 863 
 864             return sobj;
 865         } catch (final ClassCastException | NullPointerException e) {
 866             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 867         }
 868     }
 869 
 870     /**
 871      * ECMA 15.4.4.12 Array.prototype.splice ( start, deleteCount [ item1 [ , item2 [ , ... ] ] ] )
 872      *
 873      * @param self self reference
 874      * @param args arguments
 875      * @return result of splice
 876      */
 877     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 2)
 878     public static Object splice(final Object self, final Object... args) {
 879         final Object obj = Global.toObject(self);
 880 
 881         if (!(obj instanceof ScriptObject)) {
 882             return ScriptRuntime.UNDEFINED;
 883         }
 884 
 885         final Object start = (args.length > 0) ? args[0] : ScriptRuntime.UNDEFINED;
 886         final Object deleteCount = (args.length > 1) ? args[1] : ScriptRuntime.UNDEFINED;
 887 
 888         Object[] items;
 889 
 890         if (args.length > 2) {
 891             items = new Object[args.length - 2];
 892             System.arraycopy(args, 2, items, 0, items.length);
 893         } else {
 894             items = ScriptRuntime.EMPTY_ARRAY;
 895         }
 896 
 897         final ScriptObject sobj                = (ScriptObject)obj;
 898         final boolean      strict              = Global.isStrict();
 899         final long         len                 = JSType.toUint32(sobj.getLength());
 900         final double       startNum            = JSType.toNumber(start);
 901         final long         relativeStartUint32 = JSType.toUint32(startNum);
 902         final long         relativeStart       = JSType.toInteger(startNum);
 903 
 904         //TODO: workaround overflow of relativeStart for start > Integer.MAX_VALUE
 905         final long actualStart = relativeStart < 0 ?
 906             Math.max(len + relativeStart, 0) :
 907             Math.min(
 908                 Math.max(relativeStartUint32, relativeStart),
 909                 len);
 910 
 911         final long actualDeleteCount =
 912             Math.min(
 913                 Math.max(JSType.toInteger(deleteCount), 0),
 914                 len - actualStart);
 915 
 916         final NativeArray array = new NativeArray(actualDeleteCount);
 917 
 918         for (long k = 0; k < actualDeleteCount; k++) {
 919             final long from = actualStart + k;
 920 
 921             if (sobj.has(from)) {
 922                 array.defineOwnProperty((int) k, sobj.get(from));
 923             }
 924         }
 925 
 926         if (items.length < actualDeleteCount) {
 927             for (long k = actualStart; k < (len - actualDeleteCount); k++) {
 928                 final long from = k + actualDeleteCount;
 929                 final long to   = k + items.length;
 930 
 931                 if (sobj.has(from)) {
 932                     sobj.set(to, sobj.get(from), strict);
 933                 } else {
 934                     sobj.delete(to, strict);
 935                 }
 936             }
 937 
 938             for (long k = len; k > (len - actualDeleteCount + items.length); k--) {
 939                 sobj.delete(k - 1, strict);
 940             }
 941         } else if (items.length > actualDeleteCount) {
 942             for (long k = len - actualDeleteCount; k > actualStart; k--) {
 943                 final long from = k + actualDeleteCount - 1;
 944                 final long to   = k + items.length - 1;
 945 
 946                 if (sobj.has(from)) {
 947                     final Object fromValue = sobj.get(from);
 948                     sobj.set(to, fromValue, strict);
 949                 } else {
 950                     sobj.delete(to, strict);
 951                 }
 952             }
 953         }
 954 
 955         long k = actualStart;
 956         for (int i = 0; i < items.length; i++, k++) {
 957             sobj.set(k, items[i], strict);
 958         }
 959 
 960         final long newLength = len - actualDeleteCount + items.length;
 961         sobj.set("length", newLength, strict);
 962 
 963         return array;
 964     }
 965 
 966     /**
 967      * ECMA 15.4.4.13 Array.prototype.unshift ( [ item1 [ , item2 [ , ... ] ] ] )
 968      *
 969      * @param self  self reference
 970      * @param items items for unshift
 971      * @return unshifted array
 972      */
 973     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 974     public static Object unshift(final Object self, final Object... items) {
 975         final Object obj = Global.toObject(self);
 976 
 977         if (!(obj instanceof ScriptObject)) {
 978             return ScriptRuntime.UNDEFINED;
 979         }
 980 
 981         final ScriptObject sobj   = (ScriptObject)obj;
 982         final boolean      strict = Global.isStrict();
 983         final long         len    = JSType.toUint32(sobj.getLength());
 984 
 985         if (items == null) {
 986             return ScriptRuntime.UNDEFINED;
 987         }
 988 
 989         if (bulkable(sobj)) {
 990             final NativeArray nativeArray = (NativeArray) sobj;
 991             nativeArray.getArray().shiftRight(items.length);
 992 
 993             for (int j = 0; j < items.length; j++) {
 994                 nativeArray.setArray(nativeArray.getArray().set(j, items[j], sobj.isStrictContext()));
 995             }
 996         } else {
 997             for (long k = len; k > 0; k--) {
 998                 final long from = k - 1;
 999                 final long to = k + items.length - 1;
1000 
1001                 if (sobj.has(from)) {
1002                     final Object fromValue = sobj.get(from);
1003                     sobj.set(to, fromValue, strict);
1004                 } else {
1005                     sobj.delete(to, strict);
1006                 }
1007             }
1008 
1009             for (int j = 0; j < items.length; j++) {
1010                 sobj.set(j, items[j], strict);
1011             }
1012         }
1013 
1014         final long newLength = len + items.length;
1015         sobj.set("length", newLength, strict);
1016 
1017         return newLength;
1018     }
1019 
1020     /**
1021      * ECMA 15.4.4.14 Array.prototype.indexOf ( searchElement [ , fromIndex ] )
1022      *
1023      * @param self           self reference
1024      * @param searchElement  element to search for
1025      * @param fromIndex      start index of search
1026      * @return index of element, or -1 if not found
1027      */
1028     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1029     public static Object indexOf(final Object self, final Object searchElement, final Object fromIndex) {
1030         try {
1031             final ScriptObject sobj = (ScriptObject)Global.toObject(self);
1032             final long         len  = JSType.toUint32(sobj.getLength());
1033             final long         n    = JSType.toLong(fromIndex);
1034 
1035             if (len == 0 || n >= len) {
1036                 return -1;
1037             }
1038 
1039             for (long k = Math.max(0, (n < 0) ? (len - Math.abs(n)) : n); k < len; k++) {
1040                 if (sobj.has(k)) {
1041                     if (ScriptRuntime.EQ_STRICT(sobj.get(k), searchElement)) {
1042                         return k;
1043                     }
1044                 }
1045             }
1046         } catch (final ClassCastException | NullPointerException e) {
1047             //fallthru
1048         }
1049 
1050         return -1;
1051     }
1052 
1053     /**
1054      * ECMA 15.4.4.15 Array.prototype.lastIndexOf ( searchElement [ , fromIndex ] )
1055      *
1056      * @param self self reference
1057      * @param args arguments: element to search for and optional from index
1058      * @return index of element, or -1 if not found
1059      */
1060     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1061     public static Object lastIndexOf(final Object self, final Object... args) {
1062         try {
1063             final ScriptObject sobj = (ScriptObject)Global.toObject(self);
1064             final long         len  = JSType.toUint32(sobj.getLength());
1065 
1066             if (len == 0) {
1067                 return -1;
1068             }
1069 
1070             final Object searchElement = (args.length > 0) ? args[0] : ScriptRuntime.UNDEFINED;
1071             final long   n             = (args.length > 1) ? JSType.toLong(args[1]) : (len - 1);
1072 
1073             for (long k = (n < 0) ? (len - Math.abs(n)) : Math.min(n, len - 1); k >= 0; k--) {
1074                 if (sobj.has(k)) {
1075                     if (ScriptRuntime.EQ_STRICT(sobj.get(k), searchElement)) {
1076                         return k;
1077                     }
1078                 }
1079             }
1080         } catch (final ClassCastException | NullPointerException e) {
1081             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
1082         }
1083 
1084         return -1;
1085     }
1086 
1087     /**
1088      * ECMA 15.4.4.16 Array.prototype.every ( callbackfn [ , thisArg ] )
1089      *
1090      * @param self        self reference
1091      * @param callbackfn  callback function per element
1092      * @param thisArg     this argument
1093      * @return true if callback function return true for every element in the array, false otherwise
1094      */
1095     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1096     public static Object every(final Object self, final Object callbackfn, final Object thisArg) {
1097         return applyEvery(Global.toObject(self), callbackfn, thisArg);
1098     }
1099 
1100     private static boolean applyEvery(final Object self, final Object callbackfn, final Object thisArg) {
1101         return new IteratorAction<Boolean>(Global.toObject(self), callbackfn, thisArg, true) {
1102             @Override
1103             protected boolean forEach(final Object val, final int i) throws Throwable {
1104                 return (result = (boolean)EVERY_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self));
1105             }
1106         }.apply();
1107     }
1108 
1109     /**
1110      * ECMA 15.4.4.17 Array.prototype.some ( callbackfn [ , thisArg ] )
1111      *
1112      * @param self        self reference
1113      * @param callbackfn  callback function per element
1114      * @param thisArg     this argument
1115      * @return true if callback function returned true for any element in the array, false otherwise
1116      */
1117     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1118     public static Object some(final Object self, final Object callbackfn, final Object thisArg) {
1119         return new IteratorAction<Boolean>(Global.toObject(self), callbackfn, thisArg, false) {
1120             @Override
1121             protected boolean forEach(final Object val, final int i) throws Throwable {
1122                 return !(result = (boolean)SOME_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self));
1123             }
1124         }.apply();
1125     }
1126 
1127     /**
1128      * ECMA 15.4.4.18 Array.prototype.forEach ( callbackfn [ , thisArg ] )
1129      *
1130      * @param self        self reference
1131      * @param callbackfn  callback function per element
1132      * @param thisArg     this argument
1133      * @return undefined
1134      */
1135     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1136     public static Object forEach(final Object self, final Object callbackfn, final Object thisArg) {
1137         return new IteratorAction<Object>(Global.toObject(self), callbackfn, thisArg, ScriptRuntime.UNDEFINED) {
1138             @Override
1139             protected boolean forEach(final Object val, final int i) throws Throwable {
1140                 FOREACH_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self);
1141                 return true;
1142             }
1143         }.apply();
1144     }
1145 
1146     /**
1147      * ECMA 15.4.4.19 Array.prototype.map ( callbackfn [ , thisArg ] )
1148      *
1149      * @param self        self reference
1150      * @param callbackfn  callback function per element
1151      * @param thisArg     this argument
1152      * @return array with elements transformed by map function
1153      */
1154     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1155     public static Object map(final Object self, final Object callbackfn, final Object thisArg) {
1156         return new IteratorAction<NativeArray>(Global.toObject(self), callbackfn, thisArg, null) {
1157             @Override
1158             protected boolean forEach(final Object val, final int i) throws Throwable {
1159                 final Object r = MAP_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self);
1160                 result.defineOwnProperty(index, r);
1161                 return true;
1162             }
1163 
1164             @Override
1165             public void applyLoopBegin(final ArrayLikeIterator<Object> iter0) {
1166                 // map return array should be of same length as source array
1167                 // even if callback reduces source array length
1168                 result = new NativeArray(iter0.getLength());
1169             }
1170         }.apply();
1171     }
1172 
1173     /**
1174      * ECMA 15.4.4.20 Array.prototype.filter ( callbackfn [ , thisArg ] )
1175      *
1176      * @param self        self reference
1177      * @param callbackfn  callback function per element
1178      * @param thisArg     this argument
1179      * @return filtered array
1180      */
1181     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1182     public static Object filter(final Object self, final Object callbackfn, final Object thisArg) {
1183         return new IteratorAction<NativeArray>(Global.toObject(self), callbackfn, thisArg, new NativeArray()) {
1184             private int to = 0;
1185 
1186             @Override
1187             protected boolean forEach(final Object val, final int i) throws Throwable {
1188                 if ((boolean)FILTER_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self)) {
1189                     result.defineOwnProperty(to++, val);
1190                 }
1191                 return true;
1192             }
1193         }.apply();
1194     }
1195 
1196     private static Object reduceInner(final ArrayLikeIterator<Object> iter, final Object self, final Object... args) {
1197         final Object  callbackfn          = args.length > 0 ? args[0] : ScriptRuntime.UNDEFINED;
1198         final boolean initialValuePresent = args.length > 1;
1199 
1200         Object initialValue = initialValuePresent ? args[1] : ScriptRuntime.UNDEFINED;
1201 
1202         if (callbackfn == ScriptRuntime.UNDEFINED) {
1203             throw typeError("not.a.function", "undefined");
1204         }
1205 
1206         if (!initialValuePresent) {
1207             if (iter.hasNext()) {
1208                 initialValue = iter.next();
1209             } else {
1210                 throw typeError("array.reduce.invalid.init");
1211             }
1212         }
1213 
1214         //if initial value is ScriptRuntime.UNDEFINED - step forward once.
1215         return new IteratorAction<Object>(Global.toObject(self), callbackfn, ScriptRuntime.UNDEFINED, initialValue, iter) {
1216             @Override
1217             protected boolean forEach(final Object val, final int i) throws Throwable {
1218                 // TODO: why can't I declare the second arg as Undefined.class?
1219                 result = REDUCE_CALLBACK_INVOKER.invokeExact(callbackfn, ScriptRuntime.UNDEFINED, result, val, i, self);
1220                 return true;
1221             }
1222         }.apply();
1223     }
1224 
1225     /**
1226      * ECMA 15.4.4.21 Array.prototype.reduce ( callbackfn [ , initialValue ] )
1227      *
1228      * @param self self reference
1229      * @param args arguments to reduce
1230      * @return accumulated result
1231      */
1232     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1233     public static Object reduce(final Object self, final Object... args) {
1234         return reduceInner(arrayLikeIterator(self), self, args);
1235     }
1236 
1237     /**
1238      * ECMA 15.4.4.22 Array.prototype.reduceRight ( callbackfn [ , initialValue ] )
1239      *
1240      * @param self        self reference
1241      * @param args arguments to reduce
1242      * @return accumulated result
1243      */
1244     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1245     public static Object reduceRight(final Object self, final Object... args) {
1246         return reduceInner(reverseArrayLikeIterator(self), self, args);
1247     }
1248 
1249     /**
1250      * Determine if Java bulk array operations may be used on the underlying
1251      * storage. This is possible only if the object's prototype chain is empty
1252      * or each of the prototypes in the chain is empty.
1253      *
1254      * @param self the object to examine
1255      * @return true if optimizable
1256      */
1257     private static boolean bulkable(final ScriptObject self) {
1258         return self.isArray() && !hasInheritedArrayEntries(self);
1259     }
1260 
1261     private static boolean hasInheritedArrayEntries(final ScriptObject self) {
1262         ScriptObject proto = self.getProto();
1263         while (proto != null) {
1264             if (proto.hasArrayEntries()) {
1265                 return true;
1266             }
1267             proto = proto.getProto();
1268         }
1269 
1270         return false;
1271     }
1272 
1273     private static MethodHandle createIteratorCallbackInvoker(final Class<?> rtype) {
1274         return Bootstrap.createDynamicInvoker("dyn:call", rtype, Object.class, Object.class, Object.class,
1275                 int.class, Object.class);
1276 
1277     }
1278 }