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