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", desc, 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, desc, 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, desc, 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         final Object obj = Global.toObject(self);
 341         if (obj instanceof ScriptObject) {
 342             final ScriptObject sobj = (ScriptObject)obj;
 343             try {
 344                 final Object join = JOIN.getGetter().invokeExact(sobj);
 345                 if (join instanceof ScriptFunction) {
 346                     return JOIN.getInvoker().invokeExact(join, sobj);
 347                 }
 348             } catch (final RuntimeException | Error e) {
 349                 throw e;
 350             } catch (final Throwable t) {
 351                 throw new RuntimeException(t);
 352             }
 353         }
 354 
 355         // FIXME: should lookup Object.prototype.toString and call that?
 356         return ScriptRuntime.builtinObjectToString(self);
 357     }
 358 
 359     /**
 360      * ECMA 15.4.4.3 Array.prototype.toLocaleString ( )
 361      *
 362      * @param self self reference
 363      * @return locale specific string representation for array
 364      */
 365     @Function(attributes = Attribute.NOT_ENUMERABLE)
 366     public static Object toLocaleString(final Object self) {
 367         final StringBuilder sb = new StringBuilder();
 368         final Iterator<Object> iter = arrayLikeIterator(self, true);
 369 
 370         while (iter.hasNext()) {
 371             final Object obj = iter.next();
 372 
 373             if (obj != null && obj != ScriptRuntime.UNDEFINED) {
 374                 final Object val = JSType.toScriptObject(obj);
 375 
 376                 try {
 377                     if (val instanceof ScriptObject) {
 378                         final ScriptObject sobj           = (ScriptObject)val;
 379                         final Object       toLocaleString = TO_LOCALE_STRING.getGetter().invokeExact(sobj);
 380 
 381                         if (toLocaleString instanceof ScriptFunction) {
 382                             sb.append((String)TO_LOCALE_STRING.getInvoker().invokeExact(toLocaleString, sobj));
 383                         } else {
 384                             throw typeError("not.a.function", "toLocaleString");
 385                         }
 386                     }
 387                 } catch (final Error|RuntimeException t) {
 388                     throw t;
 389                 } catch (final Throwable t) {
 390                     throw new RuntimeException(t);
 391                 }
 392             }
 393 
 394             if (iter.hasNext()) {
 395                 sb.append(",");
 396             }
 397         }
 398 
 399         return sb.toString();
 400     }
 401 
 402     /**
 403      * ECMA 15.4.2.2 new Array (len)
 404      *
 405      * @param newObj was the new operator used to instantiate this array
 406      * @param self   self reference
 407      * @param args   arguments (length)
 408      * @return the new NativeArray
 409      */
 410     @Constructor(arity = 1)
 411     public static Object construct(final boolean newObj, final Object self, final Object... args) {
 412         switch (args.length) {
 413         case 0:
 414             return new NativeArray(0);
 415         case 1:
 416             final Object len = args[0];
 417             if (len instanceof Number) {
 418                 long length;
 419                 if (len instanceof Integer || len instanceof Long) {
 420                     length = ((Number) len).longValue();
 421                     if (length >= 0 && length < 0xffff_ffffL) {
 422                         return new NativeArray(length);
 423                     }
 424                 }
 425 
 426                 length = JSType.toUint32(len);
 427 
 428                 /*
 429                  * If the argument len is a Number and ToUint32(len) is equal to
 430                  * len, then the length property of the newly constructed object
 431                  * is set to ToUint32(len). If the argument len is a Number and
 432                  * ToUint32(len) is not equal to len, a RangeError exception is
 433                  * thrown.
 434                  */
 435                 final double numberLength = ((Number) len).doubleValue();
 436                 if (length != numberLength) {
 437                     throw rangeError("inappropriate.array.length", JSType.toString(numberLength));
 438                 }
 439 
 440                 return new NativeArray(length);
 441             }
 442             /*
 443              * If the argument len is not a Number, then the length property of
 444              * the newly constructed object is set to 1 and the 0 property of
 445              * the newly constructed object is set to len
 446              */
 447             return new NativeArray(new Object[]{args[0]});
 448             //fallthru
 449         default:
 450             return new NativeArray(args);
 451         }
 452     }
 453 
 454     /**
 455      * ECMA 15.4.2.2 new Array (len)
 456      *
 457      * Specialized constructor for zero arguments - empty array
 458      *
 459      * @param newObj was the new operator used to instantiate this array
 460      * @param self   self reference
 461      * @return the new NativeArray
 462      */
 463     @SpecializedConstructor
 464     public static Object construct(final boolean newObj, final Object self) {
 465         return new NativeArray(0);
 466     }
 467 
 468     /**
 469      * ECMA 15.4.2.2 new Array (len)
 470      *
 471      * Specialized constructor for one integer argument (length)
 472      *
 473      * @param newObj was the new operator used to instantiate this array
 474      * @param self   self reference
 475      * @param length array length
 476      * @return the new NativeArray
 477      */
 478     @SpecializedConstructor
 479     public static Object construct(final boolean newObj, final Object self, final int length) {
 480         if (length >= 0) {
 481             return new NativeArray(length);
 482         }
 483 
 484         return construct(newObj, self, new Object[]{length});
 485     }
 486 
 487     /**
 488      * ECMA 15.4.2.2 new Array (len)
 489      *
 490      * Specialized constructor for one long argument (length)
 491      *
 492      * @param newObj was the new operator used to instantiate this array
 493      * @param self   self reference
 494      * @param length array length
 495      * @return the new NativeArray
 496      */
 497     @SpecializedConstructor
 498     public static Object construct(final boolean newObj, final Object self, final long length) {
 499         if (length >= 0L && length <= JSType.MAX_UINT) {
 500             return new NativeArray(length);
 501         }
 502 
 503         return construct(newObj, self, new Object[]{length});
 504     }
 505 
 506     /**
 507      * ECMA 15.4.2.2 new Array (len)
 508      *
 509      * Specialized constructor for one double argument (length)
 510      *
 511      * @param newObj was the new operator used to instantiate this array
 512      * @param self   self reference
 513      * @param length array length
 514      * @return the new NativeArray
 515      */
 516     @SpecializedConstructor
 517     public static Object construct(final boolean newObj, final Object self, final double length) {
 518         final long uint32length = JSType.toUint32(length);
 519 
 520         if (uint32length == length) {
 521             return new NativeArray(uint32length);
 522         }
 523 
 524         return construct(newObj, self, new Object[]{length});
 525     }
 526 
 527     /**
 528      * ECMA 15.4.4.4 Array.prototype.concat ( [ item1 [ , item2 [ , ... ] ] ] )
 529      *
 530      * @param self self reference
 531      * @param args arguments to concat
 532      * @return resulting NativeArray
 533      */
 534     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 535     public static Object concat(final Object self, final Object... args) {
 536         final ArrayList<Object> list = new ArrayList<>();
 537         final Object selfToObject = Global.toObject(self);
 538 
 539         if (isArray(selfToObject)) {
 540             final Iterator<Object> iter = arrayLikeIterator(selfToObject, true);
 541             while (iter.hasNext()) {
 542                 list.add(iter.next());
 543             }
 544         } else {
 545             // single element, add it
 546             list.add(selfToObject);
 547         }
 548 
 549         for (final Object obj : args) {
 550             if (isArray(obj) || obj instanceof Iterable || (obj != null && obj.getClass().isArray())) {
 551                 final Iterator<Object> iter = arrayLikeIterator(obj, true);
 552                 if (iter.hasNext()) {
 553                     while (iter.hasNext()) {
 554                         list.add(iter.next());
 555                     }
 556                 } else if (!isArray(obj)) {
 557                     list.add(obj); // add empty object, but not an empty array
 558                 }
 559             } else {
 560                 // single element, add it
 561                 list.add(obj);
 562             }
 563         }
 564 
 565         return new NativeArray(list.toArray());
 566     }
 567 
 568     /**
 569      * ECMA 15.4.4.5 Array.prototype.join (separator)
 570      *
 571      * @param self      self reference
 572      * @param separator element separator
 573      * @return string representation after join
 574      */
 575     @Function(attributes = Attribute.NOT_ENUMERABLE)
 576     public static Object join(final Object self, final Object separator) {
 577         final StringBuilder    sb   = new StringBuilder();
 578         final Iterator<Object> iter = arrayLikeIterator(self, true);
 579         final String           sep  = separator == ScriptRuntime.UNDEFINED ? "," : JSType.toString(separator);
 580 
 581         while (iter.hasNext()) {
 582             final Object obj = iter.next();
 583 
 584             if (obj != null && obj != ScriptRuntime.UNDEFINED) {
 585                 sb.append(JSType.toString(obj));
 586             }
 587 
 588             if (iter.hasNext()) {
 589                 sb.append(sep);
 590             }
 591         }
 592 
 593         return sb.toString();
 594     }
 595 
 596     /**
 597      * ECMA 15.4.4.6 Array.prototype.pop ()
 598      *
 599      * @param self self reference
 600      * @return array after pop
 601      */
 602     @Function(attributes = Attribute.NOT_ENUMERABLE)
 603     public static Object pop(final Object self) {
 604         try {
 605             final ScriptObject sobj = (ScriptObject)self;
 606             final boolean strict    = sobj.isStrictContext();
 607 
 608             if (bulkable(sobj)) {
 609                 return sobj.getArray().pop();
 610             }
 611 
 612             final long len = JSType.toUint32(sobj.getLength());
 613 
 614             if (len == 0) {
 615                 sobj.set("length", 0, strict);
 616                 return ScriptRuntime.UNDEFINED;
 617             }
 618 
 619             final long   index   = len - 1;
 620             final Object element = sobj.get(index);
 621 
 622             sobj.delete(index, strict);
 623             sobj.set("length", index, strict);
 624 
 625             return element;
 626         } catch (final ClassCastException | NullPointerException e) {
 627             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 628         }
 629     }
 630 
 631     /**
 632      * ECMA 15.4.4.7 Array.prototype.push (args...)
 633      *
 634      * @param self self reference
 635      * @param args arguments to push
 636      * @return array after pushes
 637      */
 638     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 639     public static Object push(final Object self, final Object... args) {
 640         try {
 641             final ScriptObject sobj   = (ScriptObject)self;
 642             final boolean      strict = sobj.isStrictContext();
 643 
 644             if (bulkable(sobj)) {
 645                 final NativeArray nativeArray = (NativeArray)sobj;
 646                 if (nativeArray.getArray().length() + args.length <= JSType.MAX_UINT) {
 647                     final ArrayData newData = nativeArray.getArray().push(nativeArray.isStrictContext(), args);
 648                     nativeArray.setArray(newData);
 649                     return newData.length();
 650                 }
 651                 //fallthru
 652             }
 653 
 654             long len = JSType.toUint32(sobj.getLength());
 655             for (final Object element : args) {
 656                 sobj.set(len++, element, strict);
 657             }
 658             sobj.set("length", len, strict);
 659 
 660             return len;
 661         } catch (final ClassCastException | NullPointerException e) {
 662             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 663         }
 664     }
 665 
 666     /**
 667      * ECMA 15.4.4.8 Array.prototype.reverse ()
 668      *
 669      * @param self self reference
 670      * @return reversed array
 671      */
 672     @Function(attributes = Attribute.NOT_ENUMERABLE)
 673     public static Object reverse(final Object self) {
 674         try {
 675             final ScriptObject sobj   = (ScriptObject)self;
 676             final boolean      strict = sobj.isStrictContext();
 677             final long         len    = JSType.toUint32(sobj.getLength());
 678             final long         middle = len / 2;
 679 
 680             for (long lower = 0; lower != middle; lower++) {
 681                 final long    upper       = len - lower - 1;
 682                 final Object  lowerValue  = sobj.get(lower);
 683                 final Object  upperValue  = sobj.get(upper);
 684                 final boolean lowerExists = sobj.has(lower);
 685                 final boolean upperExists = sobj.has(upper);
 686 
 687                 if (lowerExists && upperExists) {
 688                     sobj.set(lower, upperValue, strict);
 689                     sobj.set(upper, lowerValue, strict);
 690                 } else if (!lowerExists && upperExists) {
 691                     sobj.set(lower, upperValue, strict);
 692                     sobj.delete(upper, strict);
 693                 } else if (lowerExists && !upperExists) {
 694                     sobj.delete(lower, strict);
 695                     sobj.set(upper, lowerValue, strict);
 696                 }
 697             }
 698             return sobj;
 699         } catch (final ClassCastException | NullPointerException e) {
 700             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 701         }
 702     }
 703 
 704     /**
 705      * ECMA 15.4.4.9 Array.prototype.shift ()
 706      *
 707      * @param self self reference
 708      * @return shifted array
 709      */
 710     @Function(attributes = Attribute.NOT_ENUMERABLE)
 711     public static Object shift(final Object self) {
 712         final Object obj = Global.toObject(self);
 713 
 714         Object first = ScriptRuntime.UNDEFINED;
 715 
 716         if (!(obj instanceof ScriptObject)) {
 717             return first;
 718         }
 719 
 720         final ScriptObject sobj   = (ScriptObject) obj;
 721         final boolean      strict = Global.isStrict();
 722 
 723         long len = JSType.toUint32(sobj.getLength());
 724 
 725         if (len > 0) {
 726             first = sobj.get(0);
 727 
 728             if (bulkable(sobj)) {
 729                 sobj.getArray().shiftLeft(1);
 730             } else {
 731                 for (long k = 1; k < len; k++) {
 732                     sobj.set(k - 1, sobj.get(k), strict);
 733                 }
 734             }
 735             sobj.delete(--len, strict);
 736         } else {
 737             len = 0;
 738         }
 739 
 740         sobj.set("length", len, strict);
 741 
 742         return first;
 743     }
 744 
 745     /**
 746      * ECMA 15.4.4.10 Array.prototype.slice ( start [ , end ] )
 747      *
 748      * @param self  self reference
 749      * @param start start of slice (inclusive)
 750      * @param end   end of slice (optional, exclusive)
 751      * @return sliced array
 752      */
 753     @Function(attributes = Attribute.NOT_ENUMERABLE)
 754     public static Object slice(final Object self, final Object start, final Object end) {
 755         final Object       obj                 = Global.toObject(self);
 756         final ScriptObject sobj                = (ScriptObject)obj;
 757         final long         len                 = JSType.toUint32(sobj.getLength());
 758         final double       startNum            = JSType.toNumber(start);
 759         final long         relativeStartUint32 = JSType.toUint32(startNum);
 760         final long         relativeStart       = JSType.toInteger(startNum);
 761 
 762         long k = relativeStart < 0 ?
 763                 Math.max(len + relativeStart, 0) :
 764                 Math.min(
 765                     Math.max(relativeStartUint32, relativeStart),
 766                     len);
 767 
 768         final double endNum = (end == ScriptRuntime.UNDEFINED)? Double.NaN : JSType.toNumber(end);
 769         final long relativeEndUint32 = (end == ScriptRuntime.UNDEFINED)? len : JSType.toUint32(endNum);
 770         final long relativeEnd       = (end == ScriptRuntime.UNDEFINED)? len : JSType.toInteger(endNum);
 771 
 772         final long finale = relativeEnd < 0 ?
 773                 Math.max(len + relativeEnd, 0) :
 774                 Math.min(
 775                     Math.max(relativeEndUint32, relativeEnd),
 776                     len);
 777 
 778         if (k >= finale) {
 779             return new NativeArray(0);
 780         }
 781 
 782         if (bulkable(sobj)) {
 783             final NativeArray narray = (NativeArray) sobj;
 784             return new NativeArray(narray.getArray().slice(k, finale));
 785         }
 786 
 787         final NativeArray copy = new NativeArray(0);
 788         for (long n = 0; k < finale; n++, k++) {
 789             copy.defineOwnProperty((int) n, sobj.get(k));
 790         }
 791 
 792         return copy;
 793     }
 794 
 795     private static ScriptFunction compareFunction(final Object comparefn) {
 796         if (comparefn == ScriptRuntime.UNDEFINED) {
 797             return null;
 798         }
 799 
 800         if (! (comparefn instanceof ScriptFunction)) {
 801             throw typeError("not.a.function", ScriptRuntime.safeToString(comparefn));
 802         }
 803 
 804         return (ScriptFunction)comparefn;
 805     }
 806 
 807     private static Object[] sort(final Object[] array, final Object comparefn) {
 808         final ScriptFunction cmp = compareFunction(comparefn);
 809 
 810         final List<Object> list = Arrays.asList(array);
 811         final Object cmpThis = cmp == null || cmp.isStrict() ? ScriptRuntime.UNDEFINED : Global.instance();
 812 
 813         Collections.sort(list, new Comparator<Object>() {
 814             @Override
 815             public int compare(final Object x, final Object y) {
 816                 if (x == ScriptRuntime.UNDEFINED && y == ScriptRuntime.UNDEFINED) {
 817                     return 0;
 818                 } else if (x == ScriptRuntime.UNDEFINED) {
 819                     return 1;
 820                 } else if (y == ScriptRuntime.UNDEFINED) {
 821                     return -1;
 822                 }
 823 
 824                 if (cmp != null) {
 825                     try {
 826                         return (int)CALL_CMP.invokeExact(cmp, cmpThis, x, y);
 827                     } catch (final RuntimeException | Error e) {
 828                         throw e;
 829                     } catch (final Throwable t) {
 830                         throw new RuntimeException(t);
 831                     }
 832                 }
 833 
 834                 return JSType.toString(x).compareTo(JSType.toString(y));
 835             }
 836         });
 837 
 838         return list.toArray(new Object[array.length]);
 839     }
 840 
 841     /**
 842      * ECMA 15.4.4.11 Array.prototype.sort ( comparefn )
 843      *
 844      * @param self       self reference
 845      * @param comparefn  element comparison function
 846      * @return sorted array
 847      */
 848     @Function(attributes = Attribute.NOT_ENUMERABLE)
 849     public static Object sort(final Object self, final Object comparefn) {
 850         try {
 851             final ScriptObject sobj    = (ScriptObject) self;
 852             final boolean      strict  = sobj.isStrictContext();
 853             final long         len     = JSType.toUint32(sobj.getLength());
 854 
 855             if (len > 1) {
 856                 // Get only non-missing elements. Missing elements go at the end
 857                 // of the sorted array. So, just don't copy these to sort input.
 858 
 859                 final ArrayList<Object> src = new ArrayList<>();
 860                 for (int i = 0; i < (int)len; i++) {
 861                     if (sobj.has(i)) {
 862                         src.add(sobj.get(i));
 863                     }
 864                 }
 865 
 866                 final Object[] sorted = sort(src.toArray(), comparefn);
 867 
 868                 for (int i = 0; i < sorted.length; i++) {
 869                     sobj.set(i, sorted[i], strict);
 870                 }
 871 
 872                 // delete missing elements - which are at the end of sorted array
 873                 for (int j = sorted.length; j < (int)len; j++) {
 874                     sobj.delete(j, strict);
 875                 }
 876             }
 877 
 878             return sobj;
 879         } catch (final ClassCastException | NullPointerException e) {
 880             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 881         }
 882     }
 883 
 884     /**
 885      * ECMA 15.4.4.12 Array.prototype.splice ( start, deleteCount [ item1 [ , item2 [ , ... ] ] ] )
 886      *
 887      * @param self self reference
 888      * @param args arguments
 889      * @return result of splice
 890      */
 891     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 2)
 892     public static Object splice(final Object self, final Object... args) {
 893         final Object obj = Global.toObject(self);
 894 
 895         if (!(obj instanceof ScriptObject)) {
 896             return ScriptRuntime.UNDEFINED;
 897         }
 898 
 899         final Object start = (args.length > 0) ? args[0] : ScriptRuntime.UNDEFINED;
 900         final Object deleteCount = (args.length > 1) ? args[1] : ScriptRuntime.UNDEFINED;
 901 
 902         Object[] items;
 903 
 904         if (args.length > 2) {
 905             items = new Object[args.length - 2];
 906             System.arraycopy(args, 2, items, 0, items.length);
 907         } else {
 908             items = ScriptRuntime.EMPTY_ARRAY;
 909         }
 910 
 911         final ScriptObject sobj                = (ScriptObject)obj;
 912         final boolean      strict              = Global.isStrict();
 913         final long         len                 = JSType.toUint32(sobj.getLength());
 914         final double       startNum            = JSType.toNumber(start);
 915         final long         relativeStartUint32 = JSType.toUint32(startNum);
 916         final long         relativeStart       = JSType.toInteger(startNum);
 917 
 918         //TODO: workaround overflow of relativeStart for start > Integer.MAX_VALUE
 919         final long actualStart = relativeStart < 0 ?
 920             Math.max(len + relativeStart, 0) :
 921             Math.min(
 922                 Math.max(relativeStartUint32, relativeStart),
 923                 len);
 924 
 925         final long actualDeleteCount =
 926             Math.min(
 927                 Math.max(JSType.toInteger(deleteCount), 0),
 928                 len - actualStart);
 929 
 930         final NativeArray array = new NativeArray(actualDeleteCount);
 931 
 932         for (long k = 0; k < actualDeleteCount; k++) {
 933             final long from = actualStart + k;
 934 
 935             if (sobj.has(from)) {
 936                 array.defineOwnProperty((int) k, sobj.get(from));
 937             }
 938         }
 939 
 940         if (items.length < actualDeleteCount) {
 941             for (long k = actualStart; k < (len - actualDeleteCount); k++) {
 942                 final long from = k + actualDeleteCount;
 943                 final long to   = k + items.length;
 944 
 945                 if (sobj.has(from)) {
 946                     sobj.set(to, sobj.get(from), strict);
 947                 } else {
 948                     sobj.delete(to, strict);
 949                 }
 950             }
 951 
 952             for (long k = len; k > (len - actualDeleteCount + items.length); k--) {
 953                 sobj.delete(k - 1, strict);
 954             }
 955         } else if (items.length > actualDeleteCount) {
 956             for (long k = len - actualDeleteCount; k > actualStart; k--) {
 957                 final long from = k + actualDeleteCount - 1;
 958                 final long to   = k + items.length - 1;
 959 
 960                 if (sobj.has(from)) {
 961                     final Object fromValue = sobj.get(from);
 962                     sobj.set(to, fromValue, strict);
 963                 } else {
 964                     sobj.delete(to, strict);
 965                 }
 966             }
 967         }
 968 
 969         long k = actualStart;
 970         for (int i = 0; i < items.length; i++, k++) {
 971             sobj.set(k, items[i], strict);
 972         }
 973 
 974         final long newLength = len - actualDeleteCount + items.length;
 975         sobj.set("length", newLength, strict);
 976 
 977         return array;
 978     }
 979 
 980     /**
 981      * ECMA 15.4.4.13 Array.prototype.unshift ( [ item1 [ , item2 [ , ... ] ] ] )
 982      *
 983      * @param self  self reference
 984      * @param items items for unshift
 985      * @return unshifted array
 986      */
 987     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 988     public static Object unshift(final Object self, final Object... items) {
 989         final Object obj = Global.toObject(self);
 990 
 991         if (!(obj instanceof ScriptObject)) {
 992             return ScriptRuntime.UNDEFINED;
 993         }
 994 
 995         final ScriptObject sobj   = (ScriptObject)obj;
 996         final boolean      strict = Global.isStrict();
 997         final long         len    = JSType.toUint32(sobj.getLength());
 998 
 999         if (items == null) {
1000             return ScriptRuntime.UNDEFINED;
1001         }
1002 
1003         if (bulkable(sobj)) {
1004             final NativeArray nativeArray = (NativeArray) sobj;
1005             nativeArray.getArray().shiftRight(items.length);
1006 
1007             for (int j = 0; j < items.length; j++) {
1008                 nativeArray.setArray(nativeArray.getArray().set(j, items[j], sobj.isStrictContext()));
1009             }
1010         } else {
1011             for (long k = len; k > 0; k--) {
1012                 final long from = k - 1;
1013                 final long to = k + items.length - 1;
1014 
1015                 if (sobj.has(from)) {
1016                     final Object fromValue = sobj.get(from);
1017                     sobj.set(to, fromValue, strict);
1018                 } else {
1019                     sobj.delete(to, strict);
1020                 }
1021             }
1022 
1023             for (int j = 0; j < items.length; j++) {
1024                 sobj.set(j, items[j], strict);
1025             }
1026         }
1027 
1028         final long newLength = len + items.length;
1029         sobj.set("length", newLength, strict);
1030 
1031         return newLength;
1032     }
1033 
1034     /**
1035      * ECMA 15.4.4.14 Array.prototype.indexOf ( searchElement [ , fromIndex ] )
1036      *
1037      * @param self           self reference
1038      * @param searchElement  element to search for
1039      * @param fromIndex      start index of search
1040      * @return index of element, or -1 if not found
1041      */
1042     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1043     public static Object indexOf(final Object self, final Object searchElement, final Object fromIndex) {
1044         try {
1045             final ScriptObject sobj = (ScriptObject)Global.toObject(self);
1046             final long         len  = JSType.toUint32(sobj.getLength());
1047             final long         n    = JSType.toLong(fromIndex);
1048 
1049             if (len == 0 || n >= len) {
1050                 return -1;
1051             }
1052 
1053             for (long k = Math.max(0, (n < 0) ? (len - Math.abs(n)) : n); k < len; k++) {
1054                 if (sobj.has(k)) {
1055                     if (ScriptRuntime.EQ_STRICT(sobj.get(k), searchElement)) {
1056                         return k;
1057                     }
1058                 }
1059             }
1060         } catch (final ClassCastException | NullPointerException e) {
1061             //fallthru
1062         }
1063 
1064         return -1;
1065     }
1066 
1067     /**
1068      * ECMA 15.4.4.15 Array.prototype.lastIndexOf ( searchElement [ , fromIndex ] )
1069      *
1070      * @param self self reference
1071      * @param args arguments: element to search for and optional from index
1072      * @return index of element, or -1 if not found
1073      */
1074     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1075     public static Object lastIndexOf(final Object self, final Object... args) {
1076         try {
1077             final ScriptObject sobj = (ScriptObject)Global.toObject(self);
1078             final long         len  = JSType.toUint32(sobj.getLength());
1079 
1080             if (len == 0) {
1081                 return -1;
1082             }
1083 
1084             final Object searchElement = (args.length > 0) ? args[0] : ScriptRuntime.UNDEFINED;
1085             final long   n             = (args.length > 1) ? JSType.toLong(args[1]) : (len - 1);
1086 
1087             for (long k = (n < 0) ? (len - Math.abs(n)) : Math.min(n, len - 1); k >= 0; k--) {
1088                 if (sobj.has(k)) {
1089                     if (ScriptRuntime.EQ_STRICT(sobj.get(k), searchElement)) {
1090                         return k;
1091                     }
1092                 }
1093             }
1094         } catch (final ClassCastException | NullPointerException e) {
1095             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
1096         }
1097 
1098         return -1;
1099     }
1100 
1101     /**
1102      * ECMA 15.4.4.16 Array.prototype.every ( callbackfn [ , thisArg ] )
1103      *
1104      * @param self        self reference
1105      * @param callbackfn  callback function per element
1106      * @param thisArg     this argument
1107      * @return true if callback function return true for every element in the array, false otherwise
1108      */
1109     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1110     public static Object every(final Object self, final Object callbackfn, final Object thisArg) {
1111         return applyEvery(Global.toObject(self), callbackfn, thisArg);
1112     }
1113 
1114     private static boolean applyEvery(final Object self, final Object callbackfn, final Object thisArg) {
1115         return new IteratorAction<Boolean>(Global.toObject(self), callbackfn, thisArg, true) {
1116             @Override
1117             protected boolean forEach(final Object val, final int i) throws Throwable {
1118                 return (result = (boolean)EVERY_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self));
1119             }
1120         }.apply();
1121     }
1122 
1123     /**
1124      * ECMA 15.4.4.17 Array.prototype.some ( callbackfn [ , thisArg ] )
1125      *
1126      * @param self        self reference
1127      * @param callbackfn  callback function per element
1128      * @param thisArg     this argument
1129      * @return true if callback function returned true for any element in the array, false otherwise
1130      */
1131     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1132     public static Object some(final Object self, final Object callbackfn, final Object thisArg) {
1133         return new IteratorAction<Boolean>(Global.toObject(self), callbackfn, thisArg, false) {
1134             @Override
1135             protected boolean forEach(final Object val, final int i) throws Throwable {
1136                 return !(result = (boolean)SOME_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self));
1137             }
1138         }.apply();
1139     }
1140 
1141     /**
1142      * ECMA 15.4.4.18 Array.prototype.forEach ( callbackfn [ , thisArg ] )
1143      *
1144      * @param self        self reference
1145      * @param callbackfn  callback function per element
1146      * @param thisArg     this argument
1147      * @return undefined
1148      */
1149     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1150     public static Object forEach(final Object self, final Object callbackfn, final Object thisArg) {
1151         return new IteratorAction<Object>(Global.toObject(self), callbackfn, thisArg, ScriptRuntime.UNDEFINED) {
1152             @Override
1153             protected boolean forEach(final Object val, final int i) throws Throwable {
1154                 FOREACH_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self);
1155                 return true;
1156             }
1157         }.apply();
1158     }
1159 
1160     /**
1161      * ECMA 15.4.4.19 Array.prototype.map ( callbackfn [ , thisArg ] )
1162      *
1163      * @param self        self reference
1164      * @param callbackfn  callback function per element
1165      * @param thisArg     this argument
1166      * @return array with elements transformed by map function
1167      */
1168     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1169     public static Object map(final Object self, final Object callbackfn, final Object thisArg) {
1170         return new IteratorAction<NativeArray>(Global.toObject(self), callbackfn, thisArg, null) {
1171             @Override
1172             protected boolean forEach(final Object val, final int i) throws Throwable {
1173                 final Object r = MAP_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self);
1174                 result.defineOwnProperty(index, r);
1175                 return true;
1176             }
1177 
1178             @Override
1179             public void applyLoopBegin(final ArrayLikeIterator<Object> iter0) {
1180                 // map return array should be of same length as source array
1181                 // even if callback reduces source array length
1182                 result = new NativeArray(iter0.getLength());
1183             }
1184         }.apply();
1185     }
1186 
1187     /**
1188      * ECMA 15.4.4.20 Array.prototype.filter ( callbackfn [ , thisArg ] )
1189      *
1190      * @param self        self reference
1191      * @param callbackfn  callback function per element
1192      * @param thisArg     this argument
1193      * @return filtered array
1194      */
1195     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1196     public static Object filter(final Object self, final Object callbackfn, final Object thisArg) {
1197         return new IteratorAction<NativeArray>(Global.toObject(self), callbackfn, thisArg, new NativeArray()) {
1198             private int to = 0;
1199 
1200             @Override
1201             protected boolean forEach(final Object val, final int i) throws Throwable {
1202                 if ((boolean)FILTER_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self)) {
1203                     result.defineOwnProperty(to++, val);
1204                 }
1205                 return true;
1206             }
1207         }.apply();
1208     }
1209 
1210     private static Object reduceInner(final ArrayLikeIterator<Object> iter, final Object self, final Object... args) {
1211         final Object  callbackfn          = args.length > 0 ? args[0] : ScriptRuntime.UNDEFINED;
1212         final boolean initialValuePresent = args.length > 1;
1213 
1214         Object initialValue = initialValuePresent ? args[1] : ScriptRuntime.UNDEFINED;
1215 
1216         if (callbackfn == ScriptRuntime.UNDEFINED) {
1217             throw typeError("not.a.function", "undefined");
1218         }
1219 
1220         if (!initialValuePresent) {
1221             if (iter.hasNext()) {
1222                 initialValue = iter.next();
1223             } else {
1224                 throw typeError("array.reduce.invalid.init");
1225             }
1226         }
1227 
1228         //if initial value is ScriptRuntime.UNDEFINED - step forward once.
1229         return new IteratorAction<Object>(Global.toObject(self), callbackfn, ScriptRuntime.UNDEFINED, initialValue, iter) {
1230             @Override
1231             protected boolean forEach(final Object val, final int i) throws Throwable {
1232                 // TODO: why can't I declare the second arg as Undefined.class?
1233                 result = REDUCE_CALLBACK_INVOKER.invokeExact(callbackfn, ScriptRuntime.UNDEFINED, result, val, i, self);
1234                 return true;
1235             }
1236         }.apply();
1237     }
1238 
1239     /**
1240      * ECMA 15.4.4.21 Array.prototype.reduce ( callbackfn [ , initialValue ] )
1241      *
1242      * @param self self reference
1243      * @param args arguments to reduce
1244      * @return accumulated result
1245      */
1246     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1247     public static Object reduce(final Object self, final Object... args) {
1248         return reduceInner(arrayLikeIterator(self), self, args);
1249     }
1250 
1251     /**
1252      * ECMA 15.4.4.22 Array.prototype.reduceRight ( callbackfn [ , initialValue ] )
1253      *
1254      * @param self        self reference
1255      * @param args arguments to reduce
1256      * @return accumulated result
1257      */
1258     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1259     public static Object reduceRight(final Object self, final Object... args) {
1260         return reduceInner(reverseArrayLikeIterator(self), self, args);
1261     }
1262 
1263     /**
1264      * Determine if Java bulk array operations may be used on the underlying
1265      * storage. This is possible only if the object's prototype chain is empty
1266      * or each of the prototypes in the chain is empty.
1267      *
1268      * @param self the object to examine
1269      * @return true if optimizable
1270      */
1271     private static boolean bulkable(final ScriptObject self) {
1272         return self.isArray() && !hasInheritedArrayEntries(self);
1273     }
1274 
1275     private static boolean hasInheritedArrayEntries(final ScriptObject self) {
1276         ScriptObject proto = self.getProto();
1277         while (proto != null) {
1278             if (proto.hasArrayEntries()) {
1279                 return true;
1280             }
1281             proto = proto.getProto();
1282         }
1283 
1284         return false;
1285     }
1286 
1287     private static MethodHandle createIteratorCallbackInvoker(final Class<?> rtype) {
1288         return Bootstrap.createDynamicInvoker("dyn:call", rtype, Object.class, Object.class, Object.class,
1289                 int.class, Object.class);
1290 
1291     }
1292 }