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, long.class, Object.class);
  79     private static final MethodHandle CALL_CMP                = Bootstrap.createDynamicInvoker("dyn:call", double.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, false);
 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             // check for length being made non-writable
 162             if (desc.has(WRITABLE) && !desc.isWritable()) {
 163                 setIsLengthNotWritable();
 164             }
 165 
 166             // Step 3a
 167             if (!desc.has(VALUE)) {
 168                 return super.defineOwnProperty("length", desc, reject);
 169             }
 170 
 171             // Step 3b
 172             final PropertyDescriptor newLenDesc = desc;
 173 
 174             // Step 3c and 3d - get new length and convert to long
 175             final long newLen = NativeArray.validLength(newLenDesc.getValue(), true);
 176 
 177             // Step 3e
 178             newLenDesc.setValue(newLen);
 179 
 180             // Step 3f
 181             // increasing array length - just need to set new length value (and attributes if any) and return
 182             if (newLen >= oldLen) {
 183                 return super.defineOwnProperty("length", newLenDesc, reject);
 184             }
 185 
 186             // Step 3g
 187             if (!oldLenDesc.isWritable()) {
 188                 if (reject) {
 189                     throw typeError("property.not.writable", "length", ScriptRuntime.safeToString(this));
 190                 }
 191                 return false;
 192             }
 193 
 194             // Step 3h and 3i
 195             final boolean newWritable = (!newLenDesc.has(WRITABLE) || newLenDesc.isWritable());
 196             if (!newWritable) {
 197                 newLenDesc.setWritable(true);
 198             }
 199 
 200             // Step 3j and 3k
 201             final boolean succeeded = super.defineOwnProperty("length", newLenDesc, reject);
 202             if (!succeeded) {
 203                 return false;
 204             }
 205 
 206             // Step 3l
 207             // make sure that length is set till the point we can delete the old elements
 208             while (newLen < oldLen) {
 209                 oldLen--;
 210                 final boolean deleteSucceeded = delete(oldLen, false);
 211                 if (!deleteSucceeded) {
 212                     newLenDesc.setValue(oldLen + 1);
 213                     if (!newWritable) {
 214                         newLenDesc.setWritable(false);
 215                     }
 216                     super.defineOwnProperty("length", newLenDesc, false);
 217                     if (reject) {
 218                         throw typeError("property.not.writable", "length", ScriptRuntime.safeToString(this));
 219                     }
 220                     return false;
 221                 }
 222             }
 223 
 224             // Step 3m
 225             if (!newWritable) {
 226                 // make 'length' property not writable
 227                 final ScriptObject newDesc = Global.newEmptyInstance();
 228                 newDesc.set(WRITABLE, false, false);
 229                 return super.defineOwnProperty("length", newDesc, false);
 230             }
 231 
 232             return true;
 233         }
 234 
 235         // Step 4a
 236         final int index = ArrayIndex.getArrayIndex(key);
 237         if (ArrayIndex.isValidArrayIndex(index)) {
 238             final long longIndex = ArrayIndex.toLongIndex(index);
 239             // Step 4b
 240             // setting an element beyond current length, but 'length' is not writable
 241             if (longIndex >= oldLen && !oldLenDesc.isWritable()) {
 242                 if (reject) {
 243                     throw typeError("property.not.writable", Long.toString(longIndex), ScriptRuntime.safeToString(this));
 244                 }
 245                 return false;
 246             }
 247 
 248             // Step 4c
 249             // set the new array element
 250             final boolean succeeded = super.defineOwnProperty(key, desc, false);
 251 
 252             // Step 4d
 253             if (!succeeded) {
 254                 if (reject) {
 255                     throw typeError("cant.redefine.property", key, ScriptRuntime.safeToString(this));
 256                 }
 257                 return false;
 258             }
 259 
 260             // Step 4e -- adjust new length based on new element index that is set
 261             if (longIndex >= oldLen) {
 262                 oldLenDesc.setValue(longIndex + 1);
 263                 super.defineOwnProperty("length", oldLenDesc, false);
 264             }
 265 
 266             // Step 4f
 267             return true;
 268         }
 269 
 270         // not an index property
 271         return super.defineOwnProperty(key, desc, reject);
 272     }
 273 
 274     /**
 275      * Return the array contents upcasted as an ObjectArray, regardless of
 276      * representation
 277      *
 278      * @return an object array
 279      */
 280     public Object[] asObjectArray() {
 281         return getArray().asObjectArray();
 282     }
 283 
 284     /**
 285      * ECMA 15.4.3.2 Array.isArray ( arg )
 286      *
 287      * @param self self reference
 288      * @param arg  argument - object to check
 289      * @return true if argument is an array
 290      */
 291     @Function(attributes = Attribute.NOT_ENUMERABLE, where = Where.CONSTRUCTOR)
 292     public static Object isArray(final Object self, final Object arg) {
 293         return isArray(arg) || (arg == Global.instance().getArrayPrototype())
 294                 || (arg instanceof NativeRegExpExecResult);
 295     }
 296 
 297     /**
 298      * Length getter
 299      * @param self self reference
 300      * @return the length of the object
 301      */
 302     @Getter(attributes = Attribute.NOT_ENUMERABLE | Attribute.NOT_CONFIGURABLE)
 303     public static Object length(final Object self) {
 304         if (isArray(self)) {
 305             return ((ScriptObject) self).getArray().length() & JSType.MAX_UINT;
 306         }
 307 
 308         return 0;
 309     }
 310 
 311     /**
 312      * Length setter
 313      * @param self   self reference
 314      * @param length new length property
 315      */
 316     @Setter(attributes = Attribute.NOT_ENUMERABLE | Attribute.NOT_CONFIGURABLE)
 317     public static void length(final Object self, final Object length) {
 318         if (isArray(self)) {
 319             ((ScriptObject) self).setLength(validLength(length, true));
 320         }
 321     }
 322 
 323     static long validLength(final Object length, final boolean reject) {
 324         final double doubleLength = JSType.toNumber(length);
 325         if (!Double.isNaN(doubleLength) && JSType.isRepresentableAsLong(doubleLength)) {
 326             final long len = (long) doubleLength;
 327             if (len >= 0 && len <= JSType.MAX_UINT) {
 328                 return len;
 329             }
 330         }
 331         if (reject) {
 332             throw rangeError("inappropriate.array.length", ScriptRuntime.safeToString(length));
 333         }
 334         return -1;
 335     }
 336 
 337     /**
 338      * ECMA 15.4.4.2 Array.prototype.toString ( )
 339      *
 340      * @param self self reference
 341      * @return string representation of array
 342      */
 343     @Function(attributes = Attribute.NOT_ENUMERABLE)
 344     public static Object toString(final Object self) {
 345         final Object obj = Global.toObject(self);
 346         if (obj instanceof ScriptObject) {
 347             final ScriptObject sobj = (ScriptObject)obj;
 348             try {
 349                 final Object join = JOIN.getGetter().invokeExact(sobj);
 350                 if (join instanceof ScriptFunction) {
 351                     return JOIN.getInvoker().invokeExact(join, sobj);
 352                 }
 353             } catch (final RuntimeException | Error e) {
 354                 throw e;
 355             } catch (final Throwable t) {
 356                 throw new RuntimeException(t);
 357             }
 358         }
 359 
 360         // FIXME: should lookup Object.prototype.toString and call that?
 361         return ScriptRuntime.builtinObjectToString(self);
 362     }
 363 
 364     /**
 365      * ECMA 15.4.4.3 Array.prototype.toLocaleString ( )
 366      *
 367      * @param self self reference
 368      * @return locale specific string representation for array
 369      */
 370     @Function(attributes = Attribute.NOT_ENUMERABLE)
 371     public static Object toLocaleString(final Object self) {
 372         final StringBuilder sb = new StringBuilder();
 373         final Iterator<Object> iter = arrayLikeIterator(self, true);
 374 
 375         while (iter.hasNext()) {
 376             final Object obj = iter.next();
 377 
 378             if (obj != null && obj != ScriptRuntime.UNDEFINED) {
 379                 final Object val = JSType.toScriptObject(obj);
 380 
 381                 try {
 382                     if (val instanceof ScriptObject) {
 383                         final ScriptObject sobj           = (ScriptObject)val;
 384                         final Object       toLocaleString = TO_LOCALE_STRING.getGetter().invokeExact(sobj);
 385 
 386                         if (toLocaleString instanceof ScriptFunction) {
 387                             sb.append((String)TO_LOCALE_STRING.getInvoker().invokeExact(toLocaleString, sobj));
 388                         } else {
 389                             throw typeError("not.a.function", "toLocaleString");
 390                         }
 391                     }
 392                 } catch (final Error|RuntimeException t) {
 393                     throw t;
 394                 } catch (final Throwable t) {
 395                     throw new RuntimeException(t);
 396                 }
 397             }
 398 
 399             if (iter.hasNext()) {
 400                 sb.append(",");
 401             }
 402         }
 403 
 404         return sb.toString();
 405     }
 406 
 407     /**
 408      * ECMA 15.4.2.2 new Array (len)
 409      *
 410      * @param newObj was the new operator used to instantiate this array
 411      * @param self   self reference
 412      * @param args   arguments (length)
 413      * @return the new NativeArray
 414      */
 415     @Constructor(arity = 1)
 416     public static Object construct(final boolean newObj, final Object self, final Object... args) {
 417         switch (args.length) {
 418         case 0:
 419             return new NativeArray(0);
 420         case 1:
 421             final Object len = args[0];
 422             if (len instanceof Number) {
 423                 long length;
 424                 if (len instanceof Integer || len instanceof Long) {
 425                     length = ((Number) len).longValue();
 426                     if (length >= 0 && length < JSType.MAX_UINT) {
 427                         return new NativeArray(length);
 428                     }
 429                 }
 430 
 431                 length = JSType.toUint32(len);
 432 
 433                 /*
 434                  * If the argument len is a Number and ToUint32(len) is equal to
 435                  * len, then the length property of the newly constructed object
 436                  * is set to ToUint32(len). If the argument len is a Number and
 437                  * ToUint32(len) is not equal to len, a RangeError exception is
 438                  * thrown.
 439                  */
 440                 final double numberLength = ((Number) len).doubleValue();
 441                 if (length != numberLength) {
 442                     throw rangeError("inappropriate.array.length", JSType.toString(numberLength));
 443                 }
 444 
 445                 return new NativeArray(length);
 446             }
 447             /*
 448              * If the argument len is not a Number, then the length property of
 449              * the newly constructed object is set to 1 and the 0 property of
 450              * the newly constructed object is set to len
 451              */
 452             return new NativeArray(new Object[]{args[0]});
 453             //fallthru
 454         default:
 455             return new NativeArray(args);
 456         }
 457     }
 458 
 459     /**
 460      * ECMA 15.4.2.2 new Array (len)
 461      *
 462      * Specialized constructor for zero arguments - empty array
 463      *
 464      * @param newObj was the new operator used to instantiate this array
 465      * @param self   self reference
 466      * @return the new NativeArray
 467      */
 468     @SpecializedConstructor
 469     public static Object construct(final boolean newObj, final Object self) {
 470         return new NativeArray(0);
 471     }
 472 
 473     /**
 474      * ECMA 15.4.2.2 new Array (len)
 475      *
 476      * Specialized constructor for one integer argument (length)
 477      *
 478      * @param newObj was the new operator used to instantiate this array
 479      * @param self   self reference
 480      * @param length array length
 481      * @return the new NativeArray
 482      */
 483     @SpecializedConstructor
 484     public static Object construct(final boolean newObj, final Object self, final int length) {
 485         if (length >= 0) {
 486             return new NativeArray(length);
 487         }
 488 
 489         return construct(newObj, self, new Object[]{length});
 490     }
 491 
 492     /**
 493      * ECMA 15.4.2.2 new Array (len)
 494      *
 495      * Specialized constructor for one long argument (length)
 496      *
 497      * @param newObj was the new operator used to instantiate this array
 498      * @param self   self reference
 499      * @param length array length
 500      * @return the new NativeArray
 501      */
 502     @SpecializedConstructor
 503     public static Object construct(final boolean newObj, final Object self, final long length) {
 504         if (length >= 0L && length <= JSType.MAX_UINT) {
 505             return new NativeArray(length);
 506         }
 507 
 508         return construct(newObj, self, new Object[]{length});
 509     }
 510 
 511     /**
 512      * ECMA 15.4.2.2 new Array (len)
 513      *
 514      * Specialized constructor for one double argument (length)
 515      *
 516      * @param newObj was the new operator used to instantiate this array
 517      * @param self   self reference
 518      * @param length array length
 519      * @return the new NativeArray
 520      */
 521     @SpecializedConstructor
 522     public static Object construct(final boolean newObj, final Object self, final double length) {
 523         final long uint32length = JSType.toUint32(length);
 524 
 525         if (uint32length == length) {
 526             return new NativeArray(uint32length);
 527         }
 528 
 529         return construct(newObj, self, new Object[]{length});
 530     }
 531 
 532     /**
 533      * ECMA 15.4.4.4 Array.prototype.concat ( [ item1 [ , item2 [ , ... ] ] ] )
 534      *
 535      * @param self self reference
 536      * @param args arguments to concat
 537      * @return resulting NativeArray
 538      */
 539     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 540     public static Object concat(final Object self, final Object... args) {
 541         final ArrayList<Object> list = new ArrayList<>();
 542         final Object selfToObject = Global.toObject(self);
 543 
 544         if (isArray(selfToObject)) {
 545             final Iterator<Object> iter = arrayLikeIterator(selfToObject, true);
 546             while (iter.hasNext()) {
 547                 list.add(iter.next());
 548             }
 549         } else {
 550             // single element, add it
 551             list.add(selfToObject);
 552         }
 553 
 554         for (final Object obj : args) {
 555             if (isArray(obj) || obj instanceof Iterable || (obj != null && obj.getClass().isArray())) {
 556                 final Iterator<Object> iter = arrayLikeIterator(obj, true);
 557                 if (iter.hasNext()) {
 558                     while (iter.hasNext()) {
 559                         list.add(iter.next());
 560                     }
 561                 } else if (!isArray(obj)) {
 562                     list.add(obj); // add empty object, but not an empty array
 563                 }
 564             } else {
 565                 // single element, add it
 566                 list.add(obj);
 567             }
 568         }
 569 
 570         return new NativeArray(list.toArray());
 571     }
 572 
 573     /**
 574      * ECMA 15.4.4.5 Array.prototype.join (separator)
 575      *
 576      * @param self      self reference
 577      * @param separator element separator
 578      * @return string representation after join
 579      */
 580     @Function(attributes = Attribute.NOT_ENUMERABLE)
 581     public static Object join(final Object self, final Object separator) {
 582         final StringBuilder    sb   = new StringBuilder();
 583         final Iterator<Object> iter = arrayLikeIterator(self, true);
 584         final String           sep  = separator == ScriptRuntime.UNDEFINED ? "," : JSType.toString(separator);
 585 
 586         while (iter.hasNext()) {
 587             final Object obj = iter.next();
 588 
 589             if (obj != null && obj != ScriptRuntime.UNDEFINED) {
 590                 sb.append(JSType.toString(obj));
 591             }
 592 
 593             if (iter.hasNext()) {
 594                 sb.append(sep);
 595             }
 596         }
 597 
 598         return sb.toString();
 599     }
 600 
 601     /**
 602      * ECMA 15.4.4.6 Array.prototype.pop ()
 603      *
 604      * @param self self reference
 605      * @return array after pop
 606      */
 607     @Function(attributes = Attribute.NOT_ENUMERABLE)
 608     public static Object pop(final Object self) {
 609         try {
 610             final ScriptObject sobj = (ScriptObject)self;
 611 
 612             if (bulkable(sobj)) {
 613                 return sobj.getArray().pop();
 614             }
 615 
 616             final long len = JSType.toUint32(sobj.getLength());
 617 
 618             if (len == 0) {
 619                 sobj.set("length", 0, true);
 620                 return ScriptRuntime.UNDEFINED;
 621             }
 622 
 623             final long   index   = len - 1;
 624             final Object element = sobj.get(index);
 625 
 626             sobj.delete(index, true);
 627             sobj.set("length", index, true);
 628 
 629             return element;
 630         } catch (final ClassCastException | NullPointerException e) {
 631             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 632         }
 633     }
 634 
 635     /**
 636      * ECMA 15.4.4.7 Array.prototype.push (args...)
 637      *
 638      * @param self self reference
 639      * @param args arguments to push
 640      * @return array after pushes
 641      */
 642     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 643     public static Object push(final Object self, final Object... args) {
 644         try {
 645             final ScriptObject sobj   = (ScriptObject)self;
 646 
 647             if (bulkable(sobj)) {
 648                 if (sobj.getArray().length() + args.length <= JSType.MAX_UINT) {
 649                     final ArrayData newData = sobj.getArray().push(true, args);
 650                     sobj.setArray(newData);
 651                     return newData.length();
 652                 }
 653                 //fallthru
 654             }
 655 
 656             long len = JSType.toUint32(sobj.getLength());
 657             for (final Object element : args) {
 658                 sobj.set(len++, element, true);
 659             }
 660             sobj.set("length", len, true);
 661 
 662             return len;
 663         } catch (final ClassCastException | NullPointerException e) {
 664             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 665         }
 666     }
 667 
 668     /**
 669      * ECMA 15.4.4.8 Array.prototype.reverse ()
 670      *
 671      * @param self self reference
 672      * @return reversed array
 673      */
 674     @Function(attributes = Attribute.NOT_ENUMERABLE)
 675     public static Object reverse(final Object self) {
 676         try {
 677             final ScriptObject sobj   = (ScriptObject)self;
 678             final long         len    = JSType.toUint32(sobj.getLength());
 679             final long         middle = len / 2;
 680 
 681             for (long lower = 0; lower != middle; lower++) {
 682                 final long    upper       = len - lower - 1;
 683                 final Object  lowerValue  = sobj.get(lower);
 684                 final Object  upperValue  = sobj.get(upper);
 685                 final boolean lowerExists = sobj.has(lower);
 686                 final boolean upperExists = sobj.has(upper);
 687 
 688                 if (lowerExists && upperExists) {
 689                     sobj.set(lower, upperValue, true);
 690                     sobj.set(upper, lowerValue, true);
 691                 } else if (!lowerExists && upperExists) {
 692                     sobj.set(lower, upperValue, true);
 693                     sobj.delete(upper, true);
 694                 } else if (lowerExists && !upperExists) {
 695                     sobj.delete(lower, true);
 696                     sobj.set(upper, lowerValue, true);
 697                 }
 698             }
 699             return sobj;
 700         } catch (final ClassCastException | NullPointerException e) {
 701             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 702         }
 703     }
 704 
 705     /**
 706      * ECMA 15.4.4.9 Array.prototype.shift ()
 707      *
 708      * @param self self reference
 709      * @return shifted array
 710      */
 711     @Function(attributes = Attribute.NOT_ENUMERABLE)
 712     public static Object shift(final Object self) {
 713         final Object obj = Global.toObject(self);
 714 
 715         Object first = ScriptRuntime.UNDEFINED;
 716 
 717         if (!(obj instanceof ScriptObject)) {
 718             return first;
 719         }
 720 
 721         final ScriptObject sobj   = (ScriptObject) obj;
 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), true);
 733                 }
 734             }
 735             sobj.delete(--len, true);
 736         } else {
 737             len = 0;
 738         }
 739 
 740         sobj.set("length", len, true);
 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 long         relativeStart       = JSType.toLong(start);
 759         final long         relativeEnd         = (end == ScriptRuntime.UNDEFINED) ? len : JSType.toLong(end);
 760 
 761         long k = relativeStart < 0 ? Math.max(len + relativeStart, 0) : Math.min(relativeStart, len);
 762         final long finale = relativeEnd < 0 ? Math.max(len + relativeEnd, 0) : Math.min(relativeEnd, len);
 763 
 764         if (k >= finale) {
 765             return new NativeArray(0);
 766         }
 767 
 768         if (bulkable(sobj)) {
 769             return new NativeArray(sobj.getArray().slice(k, finale));
 770         }
 771 
 772         final NativeArray copy = new NativeArray(0);
 773         for (long n = 0; k < finale; n++, k++) {
 774             copy.defineOwnProperty(ArrayIndex.getArrayIndex(n), sobj.get(k));
 775         }
 776 
 777         return copy;
 778     }
 779 
 780     private static ScriptFunction compareFunction(final Object comparefn) {
 781         if (comparefn == ScriptRuntime.UNDEFINED) {
 782             return null;
 783         }
 784 
 785         if (! (comparefn instanceof ScriptFunction)) {
 786             throw typeError("not.a.function", ScriptRuntime.safeToString(comparefn));
 787         }
 788 
 789         return (ScriptFunction)comparefn;
 790     }
 791 
 792     private static Object[] sort(final Object[] array, final Object comparefn) {
 793         final ScriptFunction cmp = compareFunction(comparefn);
 794 
 795         final List<Object> list = Arrays.asList(array);
 796         final Object cmpThis = cmp == null || cmp.isStrict() ? ScriptRuntime.UNDEFINED : Global.instance();
 797 
 798         Collections.sort(list, new Comparator<Object>() {
 799             @Override
 800             public int compare(final Object x, final Object y) {
 801                 if (x == ScriptRuntime.UNDEFINED && y == ScriptRuntime.UNDEFINED) {
 802                     return 0;
 803                 } else if (x == ScriptRuntime.UNDEFINED) {
 804                     return 1;
 805                 } else if (y == ScriptRuntime.UNDEFINED) {
 806                     return -1;
 807                 }
 808 
 809                 if (cmp != null) {
 810                     try {
 811                         return (int)Math.signum((double)CALL_CMP.invokeExact(cmp, cmpThis, x, y));
 812                     } catch (final RuntimeException | Error e) {
 813                         throw e;
 814                     } catch (final Throwable t) {
 815                         throw new RuntimeException(t);
 816                     }
 817                 }
 818 
 819                 return JSType.toString(x).compareTo(JSType.toString(y));
 820             }
 821         });
 822 
 823         return list.toArray(new Object[array.length]);
 824     }
 825 
 826     /**
 827      * ECMA 15.4.4.11 Array.prototype.sort ( comparefn )
 828      *
 829      * @param self       self reference
 830      * @param comparefn  element comparison function
 831      * @return sorted array
 832      */
 833     @Function(attributes = Attribute.NOT_ENUMERABLE)
 834     public static Object sort(final Object self, final Object comparefn) {
 835         try {
 836             final ScriptObject sobj    = (ScriptObject) self;
 837             final long         len     = JSType.toUint32(sobj.getLength());
 838             ArrayData          array   = sobj.getArray();
 839 
 840             if (len > 1) {
 841                 // Get only non-missing elements. Missing elements go at the end
 842                 // of the sorted array. So, just don't copy these to sort input.
 843                 final ArrayList<Object> src = new ArrayList<>();
 844                 for (long i = 0; i < len; i = array.nextIndex(i)) {
 845                     if (array.has((int) i)) {
 846                         src.add(array.getObject((int) i));
 847                     }
 848                 }
 849 
 850                 final Object[] sorted = sort(src.toArray(), comparefn);
 851 
 852                 for (int i = 0; i < sorted.length; i++) {
 853                     array = array.set(i, sorted[i], true);
 854                 }
 855 
 856                 // delete missing elements - which are at the end of sorted array
 857                 sobj.setArray(array.delete(sorted.length, len - 1));
 858             }
 859 
 860             return sobj;
 861         } catch (final ClassCastException | NullPointerException e) {
 862             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 863         }
 864     }
 865 
 866     /**
 867      * ECMA 15.4.4.12 Array.prototype.splice ( start, deleteCount [ item1 [ , item2 [ , ... ] ] ] )
 868      *
 869      * @param self self reference
 870      * @param args arguments
 871      * @return result of splice
 872      */
 873     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 2)
 874     public static Object splice(final Object self, final Object... args) {
 875         final Object obj = Global.toObject(self);
 876 
 877         if (!(obj instanceof ScriptObject)) {
 878             return ScriptRuntime.UNDEFINED;
 879         }
 880 
 881         final Object start = (args.length > 0) ? args[0] : ScriptRuntime.UNDEFINED;
 882         final Object deleteCount = (args.length > 1) ? args[1] : ScriptRuntime.UNDEFINED;
 883 
 884         Object[] items;
 885 
 886         if (args.length > 2) {
 887             items = new Object[args.length - 2];
 888             System.arraycopy(args, 2, items, 0, items.length);
 889         } else {
 890             items = ScriptRuntime.EMPTY_ARRAY;
 891         }
 892 
 893         final ScriptObject sobj                = (ScriptObject)obj;
 894         final long         len                 = JSType.toUint32(sobj.getLength());
 895         final long         relativeStart       = JSType.toLong(start);
 896 
 897         final long actualStart = relativeStart < 0 ? Math.max(len + relativeStart, 0) : Math.min(relativeStart, len);
 898         final long actualDeleteCount = Math.min(Math.max(JSType.toLong(deleteCount), 0), len - actualStart);
 899 
 900         final NativeArray array = new NativeArray(actualDeleteCount);
 901 
 902         for (long k = 0; k < actualDeleteCount; k++) {
 903             final long from = actualStart + k;
 904 
 905             if (sobj.has(from)) {
 906                 array.defineOwnProperty(ArrayIndex.getArrayIndex(k), sobj.get(from));
 907             }
 908         }
 909 
 910         if (items.length < actualDeleteCount) {
 911             for (long k = actualStart; k < (len - actualDeleteCount); k++) {
 912                 final long from = k + actualDeleteCount;
 913                 final long to   = k + items.length;
 914 
 915                 if (sobj.has(from)) {
 916                     sobj.set(to, sobj.get(from), true);
 917                 } else {
 918                     sobj.delete(to, true);
 919                 }
 920             }
 921 
 922             for (long k = len; k > (len - actualDeleteCount + items.length); k--) {
 923                 sobj.delete(k - 1, true);
 924             }
 925         } else if (items.length > actualDeleteCount) {
 926             for (long k = len - actualDeleteCount; k > actualStart; k--) {
 927                 final long from = k + actualDeleteCount - 1;
 928                 final long to   = k + items.length - 1;
 929 
 930                 if (sobj.has(from)) {
 931                     final Object fromValue = sobj.get(from);
 932                     sobj.set(to, fromValue, true);
 933                 } else {
 934                     sobj.delete(to, true);
 935                 }
 936             }
 937         }
 938 
 939         long k = actualStart;
 940         for (int i = 0; i < items.length; i++, k++) {
 941             sobj.set(k, items[i], true);
 942         }
 943 
 944         final long newLength = len - actualDeleteCount + items.length;
 945         sobj.set("length", newLength, true);
 946 
 947         return array;
 948     }
 949 
 950     /**
 951      * ECMA 15.4.4.13 Array.prototype.unshift ( [ item1 [ , item2 [ , ... ] ] ] )
 952      *
 953      * @param self  self reference
 954      * @param items items for unshift
 955      * @return unshifted array
 956      */
 957     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 958     public static Object unshift(final Object self, final Object... items) {
 959         final Object obj = Global.toObject(self);
 960 
 961         if (!(obj instanceof ScriptObject)) {
 962             return ScriptRuntime.UNDEFINED;
 963         }
 964 
 965         final ScriptObject sobj   = (ScriptObject)obj;
 966         final long         len    = JSType.toUint32(sobj.getLength());
 967 
 968         if (items == null) {
 969             return ScriptRuntime.UNDEFINED;
 970         }
 971 
 972         if (bulkable(sobj)) {
 973             sobj.getArray().shiftRight(items.length);
 974 
 975             for (int j = 0; j < items.length; j++) {
 976                 sobj.setArray(sobj.getArray().set(j, items[j], true));
 977             }
 978         } else {
 979             for (long k = len; k > 0; k--) {
 980                 final long from = k - 1;
 981                 final long to = k + items.length - 1;
 982 
 983                 if (sobj.has(from)) {
 984                     final Object fromValue = sobj.get(from);
 985                     sobj.set(to, fromValue, true);
 986                 } else {
 987                     sobj.delete(to, true);
 988                 }
 989             }
 990 
 991             for (int j = 0; j < items.length; j++) {
 992                  sobj.set(j, items[j], true);
 993             }
 994         }
 995 
 996         final long newLength = len + items.length;
 997         sobj.set("length", newLength, true);
 998 
 999         return newLength;
1000     }
1001 
1002     /**
1003      * ECMA 15.4.4.14 Array.prototype.indexOf ( searchElement [ , fromIndex ] )
1004      *
1005      * @param self           self reference
1006      * @param searchElement  element to search for
1007      * @param fromIndex      start index of search
1008      * @return index of element, or -1 if not found
1009      */
1010     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1011     public static Object indexOf(final Object self, final Object searchElement, final Object fromIndex) {
1012         try {
1013             final ScriptObject sobj = (ScriptObject)Global.toObject(self);
1014             final long         len  = JSType.toUint32(sobj.getLength());
1015             final long         n    = JSType.toLong(fromIndex);
1016 
1017             if (len == 0 || n >= len) {
1018                 return -1;
1019             }
1020 
1021             for (long k = Math.max(0, (n < 0) ? (len - Math.abs(n)) : n); k < len; k++) {
1022                 if (sobj.has(k)) {
1023                     if (ScriptRuntime.EQ_STRICT(sobj.get(k), searchElement)) {
1024                         return k;
1025                     }
1026                 }
1027             }
1028         } catch (final ClassCastException | NullPointerException e) {
1029             //fallthru
1030         }
1031 
1032         return -1;
1033     }
1034 
1035     /**
1036      * ECMA 15.4.4.15 Array.prototype.lastIndexOf ( searchElement [ , fromIndex ] )
1037      *
1038      * @param self self reference
1039      * @param args arguments: element to search for and optional from index
1040      * @return index of element, or -1 if not found
1041      */
1042     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1043     public static Object lastIndexOf(final Object self, final Object... args) {
1044         try {
1045             final ScriptObject sobj = (ScriptObject)Global.toObject(self);
1046             final long         len  = JSType.toUint32(sobj.getLength());
1047 
1048             if (len == 0) {
1049                 return -1;
1050             }
1051 
1052             final Object searchElement = (args.length > 0) ? args[0] : ScriptRuntime.UNDEFINED;
1053             final long   n             = (args.length > 1) ? JSType.toLong(args[1]) : (len - 1);
1054 
1055             for (long k = (n < 0) ? (len - Math.abs(n)) : Math.min(n, len - 1); k >= 0; k--) {
1056                 if (sobj.has(k)) {
1057                     if (ScriptRuntime.EQ_STRICT(sobj.get(k), searchElement)) {
1058                         return k;
1059                     }
1060                 }
1061             }
1062         } catch (final ClassCastException | NullPointerException e) {
1063             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
1064         }
1065 
1066         return -1;
1067     }
1068 
1069     /**
1070      * ECMA 15.4.4.16 Array.prototype.every ( callbackfn [ , thisArg ] )
1071      *
1072      * @param self        self reference
1073      * @param callbackfn  callback function per element
1074      * @param thisArg     this argument
1075      * @return true if callback function return true for every element in the array, false otherwise
1076      */
1077     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1078     public static Object every(final Object self, final Object callbackfn, final Object thisArg) {
1079         return applyEvery(Global.toObject(self), callbackfn, thisArg);
1080     }
1081 
1082     private static boolean applyEvery(final Object self, final Object callbackfn, final Object thisArg) {
1083         return new IteratorAction<Boolean>(Global.toObject(self), callbackfn, thisArg, true) {
1084             @Override
1085             protected boolean forEach(final Object val, final long i) throws Throwable {
1086                 return (result = (boolean)EVERY_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self));
1087             }
1088         }.apply();
1089     }
1090 
1091     /**
1092      * ECMA 15.4.4.17 Array.prototype.some ( callbackfn [ , thisArg ] )
1093      *
1094      * @param self        self reference
1095      * @param callbackfn  callback function per element
1096      * @param thisArg     this argument
1097      * @return true if callback function returned true for any element in the array, false otherwise
1098      */
1099     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1100     public static Object some(final Object self, final Object callbackfn, final Object thisArg) {
1101         return new IteratorAction<Boolean>(Global.toObject(self), callbackfn, thisArg, false) {
1102             @Override
1103             protected boolean forEach(final Object val, final long i) throws Throwable {
1104                 return !(result = (boolean)SOME_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self));
1105             }
1106         }.apply();
1107     }
1108 
1109     /**
1110      * ECMA 15.4.4.18 Array.prototype.forEach ( callbackfn [ , thisArg ] )
1111      *
1112      * @param self        self reference
1113      * @param callbackfn  callback function per element
1114      * @param thisArg     this argument
1115      * @return undefined
1116      */
1117     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1118     public static Object forEach(final Object self, final Object callbackfn, final Object thisArg) {
1119         return new IteratorAction<Object>(Global.toObject(self), callbackfn, thisArg, ScriptRuntime.UNDEFINED) {
1120             @Override
1121             protected boolean forEach(final Object val, final long i) throws Throwable {
1122                 FOREACH_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self);
1123                 return true;
1124             }
1125         }.apply();
1126     }
1127 
1128     /**
1129      * ECMA 15.4.4.19 Array.prototype.map ( callbackfn [ , thisArg ] )
1130      *
1131      * @param self        self reference
1132      * @param callbackfn  callback function per element
1133      * @param thisArg     this argument
1134      * @return array with elements transformed by map function
1135      */
1136     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1137     public static Object map(final Object self, final Object callbackfn, final Object thisArg) {
1138         return new IteratorAction<NativeArray>(Global.toObject(self), callbackfn, thisArg, null) {
1139             @Override
1140             protected boolean forEach(final Object val, final long i) throws Throwable {
1141                 final Object r = MAP_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self);
1142                 result.defineOwnProperty(ArrayIndex.getArrayIndex(index), r);
1143                 return true;
1144             }
1145 
1146             @Override
1147             public void applyLoopBegin(final ArrayLikeIterator<Object> iter0) {
1148                 // map return array should be of same length as source array
1149                 // even if callback reduces source array length
1150                 result = new NativeArray(iter0.getLength());
1151             }
1152         }.apply();
1153     }
1154 
1155     /**
1156      * ECMA 15.4.4.20 Array.prototype.filter ( callbackfn [ , thisArg ] )
1157      *
1158      * @param self        self reference
1159      * @param callbackfn  callback function per element
1160      * @param thisArg     this argument
1161      * @return filtered array
1162      */
1163     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1164     public static Object filter(final Object self, final Object callbackfn, final Object thisArg) {
1165         return new IteratorAction<NativeArray>(Global.toObject(self), callbackfn, thisArg, new NativeArray()) {
1166             private long to = 0;
1167 
1168             @Override
1169             protected boolean forEach(final Object val, final long i) throws Throwable {
1170                 if ((boolean)FILTER_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self)) {
1171                     result.defineOwnProperty(ArrayIndex.getArrayIndex(to++), val);
1172                 }
1173                 return true;
1174             }
1175         }.apply();
1176     }
1177 
1178     private static Object reduceInner(final ArrayLikeIterator<Object> iter, final Object self, final Object... args) {
1179         final Object  callbackfn          = args.length > 0 ? args[0] : ScriptRuntime.UNDEFINED;
1180         final boolean initialValuePresent = args.length > 1;
1181 
1182         Object initialValue = initialValuePresent ? args[1] : ScriptRuntime.UNDEFINED;
1183 
1184         if (callbackfn == ScriptRuntime.UNDEFINED) {
1185             throw typeError("not.a.function", "undefined");
1186         }
1187 
1188         if (!initialValuePresent) {
1189             if (iter.hasNext()) {
1190                 initialValue = iter.next();
1191             } else {
1192                 throw typeError("array.reduce.invalid.init");
1193             }
1194         }
1195 
1196         //if initial value is ScriptRuntime.UNDEFINED - step forward once.
1197         return new IteratorAction<Object>(Global.toObject(self), callbackfn, ScriptRuntime.UNDEFINED, initialValue, iter) {
1198             @Override
1199             protected boolean forEach(final Object val, final long i) throws Throwable {
1200                 // TODO: why can't I declare the second arg as Undefined.class?
1201                 result = REDUCE_CALLBACK_INVOKER.invokeExact(callbackfn, ScriptRuntime.UNDEFINED, result, val, i, self);
1202                 return true;
1203             }
1204         }.apply();
1205     }
1206 
1207     /**
1208      * ECMA 15.4.4.21 Array.prototype.reduce ( callbackfn [ , initialValue ] )
1209      *
1210      * @param self self reference
1211      * @param args arguments to reduce
1212      * @return accumulated result
1213      */
1214     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1215     public static Object reduce(final Object self, final Object... args) {
1216         return reduceInner(arrayLikeIterator(self), self, args);
1217     }
1218 
1219     /**
1220      * ECMA 15.4.4.22 Array.prototype.reduceRight ( callbackfn [ , initialValue ] )
1221      *
1222      * @param self        self reference
1223      * @param args arguments to reduce
1224      * @return accumulated result
1225      */
1226     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1227     public static Object reduceRight(final Object self, final Object... args) {
1228         return reduceInner(reverseArrayLikeIterator(self), self, args);
1229     }
1230 
1231     /**
1232      * Determine if Java bulk array operations may be used on the underlying
1233      * storage. This is possible only if the object's prototype chain is empty
1234      * or each of the prototypes in the chain is empty.
1235      *
1236      * @param self the object to examine
1237      * @return true if optimizable
1238      */
1239     private static boolean bulkable(final ScriptObject self) {
1240         return self.isArray() && !hasInheritedArrayEntries(self) && !self.isLengthNotWritable();
1241     }
1242 
1243     private static boolean hasInheritedArrayEntries(final ScriptObject self) {
1244         ScriptObject proto = self.getProto();
1245         while (proto != null) {
1246             if (proto.hasArrayEntries()) {
1247                 return true;
1248             }
1249             proto = proto.getProto();
1250         }
1251 
1252         return false;
1253     }
1254 
1255     private static MethodHandle createIteratorCallbackInvoker(final Class<?> rtype) {
1256         return Bootstrap.createDynamicInvoker("dyn:call", rtype, Object.class, Object.class, Object.class,
1257                 long.class, Object.class);
1258 
1259     }
1260 }