1 /*
   2  * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.objects;
  27 
  28 import static jdk.nashorn.internal.runtime.ECMAErrors.rangeError;
  29 import static jdk.nashorn.internal.runtime.ECMAErrors.typeError;
  30 import static jdk.nashorn.internal.runtime.PropertyDescriptor.VALUE;
  31 import static jdk.nashorn.internal.runtime.PropertyDescriptor.WRITABLE;
  32 import static jdk.nashorn.internal.runtime.arrays.ArrayLikeIterator.arrayLikeIterator;
  33 import static jdk.nashorn.internal.runtime.arrays.ArrayLikeIterator.reverseArrayLikeIterator;
  34 
  35 import java.lang.invoke.MethodHandle;
  36 import java.util.ArrayList;
  37 import java.util.Arrays;
  38 import java.util.Collections;
  39 import java.util.Comparator;
  40 import java.util.Iterator;
  41 import java.util.List;
  42 import jdk.nashorn.internal.objects.annotations.Attribute;
  43 import jdk.nashorn.internal.objects.annotations.Constructor;
  44 import jdk.nashorn.internal.objects.annotations.Function;
  45 import jdk.nashorn.internal.objects.annotations.Getter;
  46 import jdk.nashorn.internal.objects.annotations.ScriptClass;
  47 import jdk.nashorn.internal.objects.annotations.Setter;
  48 import jdk.nashorn.internal.objects.annotations.SpecializedConstructor;
  49 import jdk.nashorn.internal.objects.annotations.Where;
  50 import jdk.nashorn.internal.runtime.JSType;
  51 import jdk.nashorn.internal.runtime.PropertyDescriptor;
  52 import jdk.nashorn.internal.runtime.ScriptFunction;
  53 import jdk.nashorn.internal.runtime.ScriptObject;
  54 import jdk.nashorn.internal.runtime.ScriptRuntime;
  55 import jdk.nashorn.internal.runtime.Undefined;
  56 import jdk.nashorn.internal.runtime.arrays.ArrayData;
  57 import jdk.nashorn.internal.runtime.arrays.ArrayIndex;
  58 import jdk.nashorn.internal.runtime.arrays.ArrayLikeIterator;
  59 import jdk.nashorn.internal.runtime.arrays.IteratorAction;
  60 import jdk.nashorn.internal.runtime.linker.Bootstrap;
  61 import jdk.nashorn.internal.runtime.linker.InvokeByName;
  62 
  63 /**
  64  * Runtime representation of a JavaScript array. NativeArray only holds numeric
  65  * keyed values. All other values are stored in spill.
  66  */
  67 @ScriptClass("Array")
  68 public final class NativeArray extends ScriptObject {
  69     private static final InvokeByName JOIN = new InvokeByName("join", ScriptObject.class);
  70 
  71     private static final MethodHandle EVERY_CALLBACK_INVOKER   = createIteratorCallbackInvoker(boolean.class);
  72     private static final MethodHandle SOME_CALLBACK_INVOKER    = createIteratorCallbackInvoker(boolean.class);
  73     private static final MethodHandle FOREACH_CALLBACK_INVOKER = createIteratorCallbackInvoker(void.class);
  74     private static final MethodHandle MAP_CALLBACK_INVOKER     = createIteratorCallbackInvoker(Object.class);
  75     private static final MethodHandle FILTER_CALLBACK_INVOKER  = createIteratorCallbackInvoker(boolean.class);
  76 
  77     private static final MethodHandle REDUCE_CALLBACK_INVOKER = Bootstrap.createDynamicInvoker("dyn:call", Object.class,
  78             Object.class, Undefined.class, Object.class, Object.class, int.class, Object.class);
  79     private static final MethodHandle CALL_CMP                = Bootstrap.createDynamicInvoker("dyn:call", int.class,
  80             ScriptFunction.class, Object.class, Object.class, Object.class);
  81 
  82     private static final InvokeByName TO_LOCALE_STRING = new InvokeByName("toLocaleString", ScriptObject.class, String.class);
  83 
  84 
  85     /*
  86      * Constructors.
  87      */
  88     NativeArray() {
  89         this(ArrayData.initialArray());
  90     }
  91 
  92     NativeArray(final long length) {
  93         // TODO assert valid index in long before casting
  94         this(ArrayData.allocate((int) length));
  95     }
  96 
  97     NativeArray(final int[] array) {
  98         this(ArrayData.allocate(array));
  99     }
 100 
 101     NativeArray(final long[] array) {
 102         this(ArrayData.allocate(array));
 103     }
 104 
 105     NativeArray(final double[] array) {
 106         this(ArrayData.allocate(array));
 107     }
 108 
 109     NativeArray(final Object[] array) {
 110         this(ArrayData.allocate(array.length));
 111 
 112         ArrayData arrayData = this.getArray();
 113         arrayData.ensure(array.length - 1);
 114 
 115         for (int index = 0; index < array.length; index++) {
 116             final Object value = array[index];
 117 
 118             if (value == ScriptRuntime.EMPTY) {
 119                 arrayData = arrayData.delete(index);
 120             } else {
 121                 arrayData = arrayData.set(index, value, isStrictContext());
 122             }
 123         }
 124 
 125         this.setArray(arrayData);
 126     }
 127 
 128     private NativeArray(final ArrayData arrayData) {
 129         setProto(Global.instance().getArrayPrototype());
 130         this.setArray(arrayData);
 131         this.setIsArray();
 132     }
 133 
 134     @Override
 135     public String getClassName() {
 136         return "Array";
 137     }
 138 
 139     @Override
 140     public Object getLength() {
 141         return getArray().length() & JSType.MAX_UINT;
 142     }
 143 
 144     /**
 145      * ECMA 15.4.5.1 [[DefineOwnProperty]] ( P, Desc, Throw )
 146      */
 147     @Override
 148     public boolean defineOwnProperty(final String key, final Object propertyDesc, final boolean reject) {
 149         final PropertyDescriptor desc = toPropertyDescriptor(Global.instance(), propertyDesc);
 150 
 151         // never be undefined as "length" is always defined and can't be deleted for arrays
 152         // Step 1
 153         final PropertyDescriptor oldLenDesc = (PropertyDescriptor) super.getOwnPropertyDescriptor("length");
 154 
 155         // Step 2
 156         // get old length and convert to long
 157         long oldLen = NativeArray.validLength(oldLenDesc.getValue(), true);
 158 
 159         // Step 3
 160         if ("length".equals(key)) {
 161             // Step 3a
 162             if (!desc.has(VALUE)) {
 163                 return super.defineOwnProperty("length", propertyDesc, reject);
 164             }
 165 
 166             // Step 3b
 167             final PropertyDescriptor newLenDesc = desc;
 168 
 169             // Step 3c and 3d - get new length and convert to long
 170             final long newLen = NativeArray.validLength(newLenDesc.getValue(), true);
 171 
 172             // Step 3e
 173             newLenDesc.setValue(newLen);
 174 
 175             // Step 3f
 176             // increasing array length - just need to set new length value (and attributes if any) and return
 177             if (newLen >= oldLen) {
 178                 return super.defineOwnProperty("length", newLenDesc, reject);
 179             }
 180 
 181             // Step 3g
 182             if (!oldLenDesc.isWritable()) {
 183                 if (reject) {
 184                     throw typeError("property.not.writable", "length", ScriptRuntime.safeToString(this));
 185                 }
 186                 return false;
 187             }
 188 
 189             // Step 3h and 3i
 190             final boolean newWritable = (!newLenDesc.has(WRITABLE) || newLenDesc.isWritable());
 191             if (!newWritable) {
 192                 newLenDesc.setWritable(true);
 193             }
 194 
 195             // Step 3j and 3k
 196             final boolean succeeded = super.defineOwnProperty("length", newLenDesc, reject);
 197             if (!succeeded) {
 198                 return false;
 199             }
 200 
 201             // Step 3l
 202             // make sure that length is set till the point we can delete the old elements
 203             while (newLen < oldLen) {
 204                 oldLen--;
 205                 final boolean deleteSucceeded = delete(oldLen, false);
 206                 if (!deleteSucceeded) {
 207                     newLenDesc.setValue(oldLen + 1);
 208                     if (!newWritable) {
 209                         newLenDesc.setWritable(false);
 210                     }
 211                     super.defineOwnProperty("length", newLenDesc, false);
 212                     if (reject) {
 213                         throw typeError("property.not.writable", "length", ScriptRuntime.safeToString(this));
 214                     }
 215                     return false;
 216                 }
 217             }
 218 
 219             // Step 3m
 220             if (!newWritable) {
 221                 // make 'length' property not writable
 222                 final ScriptObject newDesc = Global.newEmptyInstance();
 223                 newDesc.set(WRITABLE, false, false);
 224                 return super.defineOwnProperty("length", newDesc, false);
 225             }
 226 
 227             return true;
 228         }
 229 
 230         // Step 4a
 231         final int index = ArrayIndex.getArrayIndexNoThrow(key);
 232         if (ArrayIndex.isValidArrayIndex(index)) {
 233             final long longIndex = ArrayIndex.toLongIndex(index);
 234             // Step 4b
 235             // setting an element beyond current length, but 'length' is not writable
 236             if (longIndex >= oldLen && !oldLenDesc.isWritable()) {
 237                 if (reject) {
 238                     throw typeError("property.not.writable", Long.toString(longIndex), ScriptRuntime.safeToString(this));
 239                 }
 240                 return false;
 241             }
 242 
 243             // Step 4c
 244             // set the new array element
 245             final boolean succeeded = super.defineOwnProperty(key, propertyDesc, false);
 246 
 247             // Step 4d
 248             if (!succeeded) {
 249                 if (reject) {
 250                     throw typeError("cant.redefine.property", key, ScriptRuntime.safeToString(this));
 251                 }
 252                 return false;
 253             }
 254 
 255             // Step 4e -- adjust new length based on new element index that is set
 256             if (longIndex >= oldLen) {
 257                 oldLenDesc.setValue(longIndex + 1);
 258                 super.defineOwnProperty("length", oldLenDesc, false);
 259             }
 260 
 261             // Step 4f
 262             return true;
 263         }
 264 
 265         // not an index property
 266         return super.defineOwnProperty(key, propertyDesc, reject);
 267     }
 268 
 269     /**
 270      * Return the array contents upcasted as an ObjectArray, regardless of
 271      * representation
 272      *
 273      * @return an object array
 274      */
 275     public Object[] asObjectArray() {
 276         return getArray().asObjectArray();
 277     }
 278 
 279     /**
 280      * ECMA 15.4.3.2 Array.isArray ( arg )
 281      *
 282      * @param self self reference
 283      * @param arg  argument - object to check
 284      * @return true if argument is an array
 285      */
 286     @Function(attributes = Attribute.NOT_ENUMERABLE, where = Where.CONSTRUCTOR)
 287     public static Object isArray(final Object self, final Object arg) {
 288         return isArray(arg) || (arg == Global.instance().getArrayPrototype())
 289                 || (arg instanceof NativeRegExpExecResult);
 290     }
 291 
 292     /**
 293      * Length getter
 294      * @param self self reference
 295      * @return the length of the object
 296      */
 297     @Getter(attributes = Attribute.NOT_ENUMERABLE | Attribute.NOT_CONFIGURABLE)
 298     public static Object length(final Object self) {
 299         if (isArray(self)) {
 300             return ((NativeArray) self).getArray().length() & JSType.MAX_UINT;
 301         }
 302 
 303         return 0;
 304     }
 305 
 306     /**
 307      * Length setter
 308      * @param self   self reference
 309      * @param length new length property
 310      */
 311     @Setter(attributes = Attribute.NOT_ENUMERABLE | Attribute.NOT_CONFIGURABLE)
 312     public static void length(final Object self, final Object length) {
 313         if (isArray(self)) {
 314             ((NativeArray) self).setLength(validLength(length, true));
 315         }
 316     }
 317 
 318     static long validLength(final Object length, final boolean reject) {
 319         final double doubleLength = JSType.toNumber(length);
 320         if (!Double.isNaN(doubleLength) && JSType.isRepresentableAsLong(doubleLength)) {
 321             final long len = (long) doubleLength;
 322             if (len >= 0 && len <= JSType.MAX_UINT) {
 323                 return len;
 324             }
 325         }
 326         if (reject) {
 327             throw rangeError("inappropriate.array.length", ScriptRuntime.safeToString(length));
 328         }
 329         return -1;
 330     }
 331 
 332     /**
 333      * ECMA 15.4.4.2 Array.prototype.toString ( )
 334      *
 335      * @param self self reference
 336      * @return string representation of array
 337      */
 338     @Function(attributes = Attribute.NOT_ENUMERABLE)
 339     public static Object toString(final Object self) {
 340         final Object obj = Global.toObject(self);
 341         if (obj instanceof ScriptObject) {
 342             final ScriptObject sobj = (ScriptObject)obj;
 343             try {
 344                 final Object join = JOIN.getGetter().invokeExact(sobj);
 345                 if (join instanceof ScriptFunction) {
 346                     return JOIN.getInvoker().invokeExact(join, sobj);
 347                 }
 348             } catch (final RuntimeException | Error e) {
 349                 throw e;
 350             } catch (final Throwable t) {
 351                 throw new RuntimeException(t);
 352             }
 353         }
 354 
 355         // FIXME: should lookup Object.prototype.toString and call that?
 356         return ScriptRuntime.builtinObjectToString(self);
 357     }
 358 
 359     /**
 360      * ECMA 15.4.4.3 Array.prototype.toLocaleString ( )
 361      *
 362      * @param self self reference
 363      * @return locale specific string representation for array
 364      */
 365     @Function(attributes = Attribute.NOT_ENUMERABLE)
 366     public static Object toLocaleString(final Object self) {
 367         final StringBuilder sb = new StringBuilder();
 368         final Iterator<Object> iter = arrayLikeIterator(self, true);
 369 
 370         while (iter.hasNext()) {
 371             final Object obj = iter.next();
 372 
 373             if (obj != null && obj != ScriptRuntime.UNDEFINED) {
 374                 final Object val = JSType.toScriptObject(obj);
 375 
 376                 try {
 377                     if (val instanceof ScriptObject) {
 378                         final ScriptObject sobj           = (ScriptObject)val;
 379                         final Object       toLocaleString = TO_LOCALE_STRING.getGetter().invokeExact(sobj);
 380 
 381                         if (toLocaleString instanceof ScriptFunction) {
 382                             sb.append((String)TO_LOCALE_STRING.getInvoker().invokeExact(toLocaleString, sobj));
 383                         } else {
 384                             throw typeError("not.a.function", "toLocaleString");
 385                         }
 386                     }
 387                 } catch (final Error|RuntimeException t) {
 388                     throw t;
 389                 } catch (final Throwable t) {
 390                     throw new RuntimeException(t);
 391                 }
 392             }
 393 
 394             if (iter.hasNext()) {
 395                 sb.append(",");
 396             }
 397         }
 398 
 399         return sb.toString();
 400     }
 401 
 402     /**
 403      * ECMA 15.4.2.2 new Array (len)
 404      *
 405      * @param newObj was the new operator used to instantiate this array
 406      * @param self   self reference
 407      * @param args   arguments (length)
 408      * @return the new NativeArray
 409      */
 410     @Constructor(arity = 1)
 411     public static Object construct(final boolean newObj, final Object self, final Object... args) {
 412         switch (args.length) {
 413         case 0:
 414             return new NativeArray(0);
 415         case 1:
 416             final Object len = args[0];
 417             if (len instanceof Number) {
 418                 long length;
 419                 if (len instanceof Integer || len instanceof Long) {
 420                     length = ((Number) len).longValue();
 421                     if (length >= 0 && length < 0xffff_ffffL) {
 422                         return new NativeArray(length);
 423                     }
 424                 }
 425 
 426                 length = JSType.toUint32(len);
 427 
 428                 /*
 429                  * If the argument len is a Number and ToUint32(len) is equal to
 430                  * len, then the length property of the newly constructed object
 431                  * is set to ToUint32(len). If the argument len is a Number and
 432                  * ToUint32(len) is not equal to len, a RangeError exception is
 433                  * thrown.
 434                  */
 435                 final double numberLength = ((Number) len).doubleValue();
 436                 if (length != numberLength) {
 437                     throw rangeError("inappropriate.array.length", JSType.toString(numberLength));
 438                 }
 439 
 440                 return new NativeArray(length);
 441             }
 442             /*
 443              * If the argument len is not a Number, then the length property of
 444              * the newly constructed object is set to 1 and the 0 property of
 445              * the newly constructed object is set to len
 446              */
 447             return new NativeArray(new Object[]{args[0]});
 448             //fallthru
 449         default:
 450             return new NativeArray(args);
 451         }
 452     }
 453 
 454     /**
 455      * ECMA 15.4.2.2 new Array (len)
 456      *
 457      * Specialized constructor for zero arguments - empty array
 458      *
 459      * @param newObj was the new operator used to instantiate this array
 460      * @param self   self reference
 461      * @return the new NativeArray
 462      */
 463     @SpecializedConstructor
 464     public static Object construct(final boolean newObj, final Object self) {
 465         return new NativeArray(0);
 466     }
 467 
 468     /**
 469      * ECMA 15.4.2.2 new Array (len)
 470      *
 471      * Specialized constructor for one integer argument (length)
 472      *
 473      * @param newObj was the new operator used to instantiate this array
 474      * @param self   self reference
 475      * @param length array length
 476      * @return the new NativeArray
 477      */
 478     @SpecializedConstructor
 479     public static Object construct(final boolean newObj, final Object self, final int length) {
 480         if (length >= 0) {
 481             return new NativeArray(length);
 482         }
 483 
 484         return construct(newObj, self, new Object[]{length});
 485     }
 486 
 487     /**
 488      * ECMA 15.4.2.2 new Array (len)
 489      *
 490      * Specialized constructor for one long argument (length)
 491      *
 492      * @param newObj was the new operator used to instantiate this array
 493      * @param self   self reference
 494      * @param length array length
 495      * @return the new NativeArray
 496      */
 497     @SpecializedConstructor
 498     public static Object construct(final boolean newObj, final Object self, final long length) {
 499         if (length >= 0L && length <= JSType.MAX_UINT) {
 500             return new NativeArray(length);
 501         }
 502 
 503         return construct(newObj, self, new Object[]{length});
 504     }
 505 
 506     /**
 507      * ECMA 15.4.2.2 new Array (len)
 508      *
 509      * Specialized constructor for one double argument (length)
 510      *
 511      * @param newObj was the new operator used to instantiate this array
 512      * @param self   self reference
 513      * @param length array length
 514      * @return the new NativeArray
 515      */
 516     @SpecializedConstructor
 517     public static Object construct(final boolean newObj, final Object self, final double length) {
 518         final long uint32length = JSType.toUint32(length);
 519 
 520         if (uint32length == length) {
 521             return new NativeArray(uint32length);
 522         }
 523 
 524         return construct(newObj, self, new Object[]{length});
 525     }
 526 
 527     /**
 528      * ECMA 15.4.4.4 Array.prototype.concat ( [ item1 [ , item2 [ , ... ] ] ] )
 529      *
 530      * @param self self reference
 531      * @param args arguments to concat
 532      * @return resulting NativeArray
 533      */
 534     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 535     public static Object concat(final Object self, final Object... args) {
 536         final ArrayList<Object> list = new ArrayList<>();
 537         final Object selfToObject = Global.toObject(self);
 538 
 539         if (isArray(selfToObject)) {
 540             final Iterator<Object> iter = arrayLikeIterator(selfToObject, true);
 541             while (iter.hasNext()) {
 542                 list.add(iter.next());
 543             }
 544         } else {
 545             // single element, add it
 546             list.add(selfToObject);
 547         }
 548 
 549         for (final Object obj : args) {
 550             if (isArray(obj) || obj instanceof Iterable || (obj != null && obj.getClass().isArray())) {
 551                 final Iterator<Object> iter = arrayLikeIterator(obj, true);
 552                 if (iter.hasNext()) {
 553                     while (iter.hasNext()) {
 554                         list.add(iter.next());
 555                     }
 556                 } else if (!isArray(obj)) {
 557                     list.add(obj); // add empty object, but not an empty array
 558                 }
 559             } else {
 560                 // single element, add it
 561                 list.add(obj);
 562             }
 563         }
 564 
 565         return new NativeArray(list.toArray());
 566     }
 567 
 568     /**
 569      * ECMA 15.4.4.5 Array.prototype.join (separator)
 570      *
 571      * @param self      self reference
 572      * @param separator element separator
 573      * @return string representation after join
 574      */
 575     @Function(attributes = Attribute.NOT_ENUMERABLE)
 576     public static Object join(final Object self, final Object separator) {

 577         final StringBuilder    sb   = new StringBuilder();
 578         final Iterator<Object> iter = arrayLikeIterator(self, true);
 579         final String           sep  = separator == ScriptRuntime.UNDEFINED ? "," : JSType.toString(separator);
 580 
 581         while (iter.hasNext()) {
 582             final Object obj = iter.next();
 583 
 584             if (obj != null && obj != ScriptRuntime.UNDEFINED) {
 585                 sb.append(JSType.toString(obj));
 586             }
 587 
 588             if (iter.hasNext()) {
 589                 sb.append(sep);
 590             }
 591         }
 592 
 593         return sb.toString();
 594     }
 595 
 596     /**
 597      * ECMA 15.4.4.6 Array.prototype.pop ()
 598      *
 599      * @param self self reference
 600      * @return array after pop
 601      */
 602     @Function(attributes = Attribute.NOT_ENUMERABLE)
 603     public static Object pop(final Object self) {
 604         try {
 605             final ScriptObject sobj = (ScriptObject)self;
 606             final boolean strict    = sobj.isStrictContext();
 607 
 608             if (bulkable(sobj)) {
 609                 return sobj.getArray().pop();
 610             }
 611 
 612             final long len = JSType.toUint32(sobj.getLength());
 613 
 614             if (len == 0) {
 615                 sobj.set("length", 0, strict);
 616                 return ScriptRuntime.UNDEFINED;
 617             }
 618 
 619             final long   index   = len - 1;
 620             final Object element = sobj.get(index);
 621 
 622             sobj.delete(index, strict);
 623             sobj.set("length", index, strict);
 624 
 625             return element;
 626         } catch (final ClassCastException | NullPointerException e) {
 627             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 628         }
 629     }
 630 
 631     /**
 632      * ECMA 15.4.4.7 Array.prototype.push (args...)
 633      *
 634      * @param self self reference
 635      * @param args arguments to push
 636      * @return array after pushes
 637      */
 638     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 639     public static Object push(final Object self, final Object... args) {
 640         try {
 641             final ScriptObject sobj   = (ScriptObject)self;
 642             final boolean      strict = sobj.isStrictContext();
 643 
 644             if (bulkable(sobj)) {
 645                 final NativeArray nativeArray = (NativeArray)sobj;
 646                 if (nativeArray.getArray().length() + args.length <= JSType.MAX_UINT) {
 647                     final ArrayData newData = nativeArray.getArray().push(nativeArray.isStrictContext(), args);
 648                     nativeArray.setArray(newData);
 649                     return newData.length();
 650                 }
 651                 //fallthru
 652             }
 653 
 654             long len = JSType.toUint32(sobj.getLength());
 655             for (final Object element : args) {
 656                 sobj.set(len++, element, strict);
 657             }
 658             sobj.set("length", len, strict);
 659 
 660             return len;
 661         } catch (final ClassCastException | NullPointerException e) {
 662             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 663         }
 664     }
 665 
 666     /**
 667      * ECMA 15.4.4.8 Array.prototype.reverse ()
 668      *
 669      * @param self self reference
 670      * @return reversed array
 671      */
 672     @Function(attributes = Attribute.NOT_ENUMERABLE)
 673     public static Object reverse(final Object self) {
 674         try {
 675             final ScriptObject sobj   = (ScriptObject)self;
 676             final boolean      strict = sobj.isStrictContext();
 677             final long         len    = JSType.toUint32(sobj.getLength());
 678             final long         middle = len / 2;
 679 
 680             for (long lower = 0; lower != middle; lower++) {
 681                 final long    upper       = len - lower - 1;
 682                 final Object  lowerValue  = sobj.get(lower);
 683                 final Object  upperValue  = sobj.get(upper);
 684                 final boolean lowerExists = sobj.has(lower);
 685                 final boolean upperExists = sobj.has(upper);
 686 
 687                 if (lowerExists && upperExists) {
 688                     sobj.set(lower, upperValue, strict);
 689                     sobj.set(upper, lowerValue, strict);
 690                 } else if (!lowerExists && upperExists) {
 691                     sobj.set(lower, upperValue, strict);
 692                     sobj.delete(upper, strict);
 693                 } else if (lowerExists && !upperExists) {
 694                     sobj.delete(lower, strict);
 695                     sobj.set(upper, lowerValue, strict);
 696                 }
 697             }
 698             return sobj;
 699         } catch (final ClassCastException | NullPointerException e) {
 700             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 701         }
 702     }
 703 
 704     /**
 705      * ECMA 15.4.4.9 Array.prototype.shift ()
 706      *
 707      * @param self self reference
 708      * @return shifted array
 709      */
 710     @Function(attributes = Attribute.NOT_ENUMERABLE)
 711     public static Object shift(final Object self) {
 712         final Object obj = Global.toObject(self);
 713 
 714         Object first = ScriptRuntime.UNDEFINED;
 715 
 716         if (!(obj instanceof ScriptObject)) {
 717             return first;
 718         }
 719 
 720         final ScriptObject sobj   = (ScriptObject) obj;
 721         final boolean      strict = Global.isStrict();
 722 
 723         long len = JSType.toUint32(sobj.getLength());
 724 
 725         if (len > 0) {
 726             first = sobj.get(0);
 727 
 728             if (bulkable(sobj)) {
 729                 sobj.getArray().shiftLeft(1);
 730             } else {
 731                 for (long k = 1; k < len; k++) {
 732                     sobj.set(k - 1, sobj.get(k), strict);
 733                 }
 734             }
 735             sobj.delete(--len, strict);
 736         } else {
 737             len = 0;
 738         }
 739 
 740         sobj.set("length", len, strict);
 741 
 742         return first;
 743     }
 744 
 745     /**
 746      * ECMA 15.4.4.10 Array.prototype.slice ( start [ , end ] )
 747      *
 748      * @param self  self reference
 749      * @param start start of slice (inclusive)
 750      * @param end   end of slice (optional, exclusive)
 751      * @return sliced array
 752      */
 753     @Function(attributes = Attribute.NOT_ENUMERABLE)
 754     public static Object slice(final Object self, final Object start, final Object end) {
 755         final Object       obj                 = Global.toObject(self);
 756         final ScriptObject sobj                = (ScriptObject)obj;
 757         final long         len                 = JSType.toUint32(sobj.getLength());
 758         final double       startNum            = JSType.toNumber(start);
 759         final long         relativeStartUint32 = JSType.toUint32(startNum);
 760         final long         relativeStart       = JSType.toInteger(startNum);
 761 
 762         long k = relativeStart < 0 ?
 763                 Math.max(len + relativeStart, 0) :
 764                 Math.min(
 765                     Math.max(relativeStartUint32, relativeStart),
 766                     len);
 767 
 768         final double endNum = (end == ScriptRuntime.UNDEFINED)? Double.NaN : JSType.toNumber(end);
 769         final long relativeEndUint32 = (end == ScriptRuntime.UNDEFINED)? len : JSType.toUint32(endNum);
 770         final long relativeEnd       = (end == ScriptRuntime.UNDEFINED)? len : JSType.toInteger(endNum);
 771 
 772         final long finale = relativeEnd < 0 ?
 773                 Math.max(len + relativeEnd, 0) :
 774                 Math.min(
 775                     Math.max(relativeEndUint32, relativeEnd),
 776                     len);
 777 
 778         if (k >= finale) {
 779             return new NativeArray(0);
 780         }
 781 
 782         if (bulkable(sobj)) {
 783             final NativeArray narray = (NativeArray) sobj;
 784             return new NativeArray(narray.getArray().slice(k, finale));
 785         }
 786 
 787         final NativeArray copy = new NativeArray(0);
 788         for (long n = 0; k < finale; n++, k++) {
 789             copy.defineOwnProperty((int) n, sobj.get(k));
 790         }
 791 
 792         return copy;
 793     }
 794 
 795     private static ScriptFunction compareFunction(final Object comparefn) {
 796         try {
 797             return (ScriptFunction)comparefn;
 798         } catch (final ClassCastException e) {
 799             return null; //undefined or null
 800         }
 801     }
 802 
 803     private static Object[] sort(final Object[] array, final Object comparefn) {
 804         final ScriptFunction cmp = compareFunction(comparefn);
 805 
 806         final List<Object> list = Arrays.asList(array);
 807         final Object cmpThis = cmp == null || cmp.isStrict() ? ScriptRuntime.UNDEFINED : Global.instance();
 808 
 809         Collections.sort(list, new Comparator<Object>() {
 810             @Override
 811             public int compare(final Object x, final Object y) {
 812                 if (x == ScriptRuntime.UNDEFINED && y == ScriptRuntime.UNDEFINED) {
 813                     return 0;
 814                 } else if (x == ScriptRuntime.UNDEFINED) {
 815                     return 1;
 816                 } else if (y == ScriptRuntime.UNDEFINED) {
 817                     return -1;
 818                 }
 819 
 820                 if (cmp != null) {
 821                     try {
 822                         return (int)CALL_CMP.invokeExact(cmp, cmpThis, x, y);
 823                     } catch (final RuntimeException | Error e) {
 824                         throw e;
 825                     } catch (final Throwable t) {
 826                         throw new RuntimeException(t);
 827                     }
 828                 }
 829 
 830                 return JSType.toString(x).compareTo(JSType.toString(y));
 831             }
 832         });
 833 
 834         return list.toArray(new Object[array.length]);
 835     }
 836 
 837     /**
 838      * ECMA 15.4.4.11 Array.prototype.sort ( comparefn )
 839      *
 840      * @param self       self reference
 841      * @param comparefn  element comparison function
 842      * @return sorted array
 843      */
 844     @Function(attributes = Attribute.NOT_ENUMERABLE)
 845     public static Object sort(final Object self, final Object comparefn) {
 846         try {
 847             final ScriptObject sobj    = (ScriptObject) self;
 848             final boolean      strict  = sobj.isStrictContext();
 849             final long         len     = JSType.toUint32(sobj.getLength());
 850 
 851             if (len > 1) {
 852                 final Object[] src = new Object[(int) len];
 853                 for (int i = 0; i < src.length; i++) {
 854                     src[i] = sobj.get(i);
 855                 }
 856 
 857                 final Object[] sorted = sort(src, comparefn);
 858                 assert sorted.length == src.length;
 859 
 860                 for (int i = 0; i < sorted.length; i++) {
 861                     sobj.set(i, sorted[i], strict);
 862                 }
 863             }
 864 
 865             return sobj;
 866         } catch (final ClassCastException | NullPointerException e) {
 867             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
 868         }
 869     }
 870 
 871     /**
 872      * ECMA 15.4.4.12 Array.prototype.splice ( start, deleteCount [ item1 [ , item2 [ , ... ] ] ] )
 873      *
 874      * @param self self reference
 875      * @param args arguments
 876      * @return result of splice
 877      */
 878     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 2)
 879     public static Object splice(final Object self, final Object... args) {
 880         final Object obj = Global.toObject(self);
 881 
 882         if (!(obj instanceof ScriptObject)) {
 883             return ScriptRuntime.UNDEFINED;
 884         }
 885 
 886         final Object start = (args.length > 0) ? args[0] : ScriptRuntime.UNDEFINED;
 887         final Object deleteCount = (args.length > 1) ? args[1] : ScriptRuntime.UNDEFINED;
 888 
 889         Object[] items;
 890 
 891         if (args.length > 2) {
 892             items = new Object[args.length - 2];
 893             System.arraycopy(args, 2, items, 0, items.length);
 894         } else {
 895             items = ScriptRuntime.EMPTY_ARRAY;
 896         }
 897 
 898         final ScriptObject sobj                = (ScriptObject)obj;
 899         final boolean      strict              = Global.isStrict();
 900         final long         len                 = JSType.toUint32(sobj.getLength());
 901         final double       startNum            = JSType.toNumber(start);
 902         final long         relativeStartUint32 = JSType.toUint32(startNum);
 903         final long         relativeStart       = JSType.toInteger(startNum);
 904 
 905         //TODO: workaround overflow of relativeStart for start > Integer.MAX_VALUE
 906         final long actualStart = relativeStart < 0 ?
 907             Math.max(len + relativeStart, 0) :
 908             Math.min(
 909                 Math.max(relativeStartUint32, relativeStart),
 910                 len);
 911 
 912         final long actualDeleteCount =
 913             Math.min(
 914                 Math.max(JSType.toInteger(deleteCount), 0),
 915                 len - actualStart);
 916 
 917         final NativeArray array = new NativeArray(actualDeleteCount);
 918 
 919         for (long k = 0; k < actualDeleteCount; k++) {
 920             final long from = actualStart + k;
 921 
 922             if (sobj.has(from)) {
 923                 array.defineOwnProperty((int) k, sobj.get(from));
 924             }
 925         }
 926 
 927         if (items.length < actualDeleteCount) {
 928             for (long k = actualStart; k < (len - actualDeleteCount); k++) {
 929                 final long from = k + actualDeleteCount;
 930                 final long to   = k + items.length;
 931 
 932                 if (sobj.has(from)) {
 933                     sobj.set(to, sobj.get(from), strict);
 934                 } else {
 935                     sobj.delete(to, strict);
 936                 }
 937             }
 938 
 939             for (long k = len; k > (len - actualDeleteCount + items.length); k--) {
 940                 sobj.delete(k - 1, strict);
 941             }
 942         } else if (items.length > actualDeleteCount) {
 943             for (long k = len - actualDeleteCount; k > actualStart; k--) {
 944                 final long from = k + actualDeleteCount - 1;
 945                 final long to   = k + items.length - 1;
 946 
 947                 if (sobj.has(from)) {
 948                     final Object fromValue = sobj.get(from);
 949                     sobj.set(to, fromValue, strict);
 950                 } else {
 951                     sobj.delete(to, strict);
 952                 }
 953             }
 954         }
 955 
 956         long k = actualStart;
 957         for (int i = 0; i < items.length; i++, k++) {
 958             sobj.set(k, items[i], strict);
 959         }
 960 
 961         final long newLength = len - actualDeleteCount + items.length;
 962         sobj.set("length", newLength, strict);
 963 
 964         return array;
 965     }
 966 
 967     /**
 968      * ECMA 15.4.4.13 Array.prototype.unshift ( [ item1 [ , item2 [ , ... ] ] ] )
 969      *
 970      * @param self  self reference
 971      * @param items items for unshift
 972      * @return unshifted array
 973      */
 974     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
 975     public static Object unshift(final Object self, final Object... items) {
 976         final Object obj = Global.toObject(self);
 977 
 978         if (!(obj instanceof ScriptObject)) {
 979             return ScriptRuntime.UNDEFINED;
 980         }
 981 
 982         final ScriptObject sobj   = (ScriptObject)obj;
 983         final boolean      strict = Global.isStrict();
 984         final long         len    = JSType.toUint32(sobj.getLength());
 985 
 986         if (items == null) {
 987             return ScriptRuntime.UNDEFINED;
 988         }
 989 
 990         if (bulkable(sobj)) {
 991             final NativeArray nativeArray = (NativeArray) sobj;
 992             nativeArray.getArray().shiftRight(items.length);
 993 
 994             for (int j = 0; j < items.length; j++) {
 995                 nativeArray.setArray(nativeArray.getArray().set(j, items[j], sobj.isStrictContext()));
 996             }
 997         } else {
 998             for (long k = len; k > 0; k--) {
 999                 final long from = k - 1;
1000                 final long to = k + items.length - 1;
1001 
1002                 if (sobj.has(from)) {
1003                     final Object fromValue = sobj.get(from);
1004                     sobj.set(to, fromValue, strict);
1005                 } else {
1006                     sobj.delete(to, strict);
1007                 }
1008             }
1009 
1010             for (int j = 0; j < items.length; j++) {
1011                 sobj.set(j, items[j], strict);
1012             }
1013         }
1014 
1015         final long newLength = len + items.length;
1016         sobj.set("length", newLength, strict);
1017 
1018         return newLength;
1019     }
1020 
1021     /**
1022      * ECMA 15.4.4.14 Array.prototype.indexOf ( searchElement [ , fromIndex ] )
1023      *
1024      * @param self           self reference
1025      * @param searchElement  element to search for
1026      * @param fromIndex      start index of search
1027      * @return index of element, or -1 if not found
1028      */
1029     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1030     public static Object indexOf(final Object self, final Object searchElement, final Object fromIndex) {
1031         try {
1032             final ScriptObject sobj = (ScriptObject)Global.toObject(self);
1033             final long         len  = JSType.toUint32(sobj.getLength());
1034             final long         n    = JSType.toLong(fromIndex);
1035 
1036             if (len == 0 || n >= len) {
1037                 return -1;
1038             }
1039 
1040             for (long k = Math.max(0, (n < 0) ? (len - Math.abs(n)) : n); k < len; k++) {
1041                 if (sobj.has(k)) {
1042                     if (ScriptRuntime.EQ_STRICT(sobj.get(k), searchElement)) {
1043                         return k;
1044                     }
1045                 }
1046             }
1047         } catch (final ClassCastException | NullPointerException e) {
1048             //fallthru
1049         }
1050 
1051         return -1;
1052     }
1053 
1054     /**
1055      * ECMA 15.4.4.15 Array.prototype.lastIndexOf ( searchElement [ , fromIndex ] )
1056      *
1057      * @param self self reference
1058      * @param args arguments: element to search for and optional from index
1059      * @return index of element, or -1 if not found
1060      */
1061     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1062     public static Object lastIndexOf(final Object self, final Object... args) {
1063         try {
1064             final ScriptObject sobj = (ScriptObject)Global.toObject(self);
1065             final long         len  = JSType.toUint32(sobj.getLength());
1066 
1067             if (len == 0) {
1068                 return -1;
1069             }
1070 
1071             final Object searchElement = (args.length > 0) ? args[0] : ScriptRuntime.UNDEFINED;
1072             final long   n             = (args.length > 1) ? JSType.toLong(args[1]) : (len - 1);
1073 
1074             for (long k = (n < 0) ? (len - Math.abs(n)) : Math.min(n, len - 1); k >= 0; k--) {
1075                 if (sobj.has(k)) {
1076                     if (ScriptRuntime.EQ_STRICT(sobj.get(k), searchElement)) {
1077                         return k;
1078                     }
1079                 }
1080             }
1081         } catch (final ClassCastException | NullPointerException e) {
1082             throw typeError("not.an.object", ScriptRuntime.safeToString(self));
1083         }
1084 
1085         return -1;
1086     }
1087 
1088     /**
1089      * ECMA 15.4.4.16 Array.prototype.every ( callbackfn [ , thisArg ] )
1090      *
1091      * @param self        self reference
1092      * @param callbackfn  callback function per element
1093      * @param thisArg     this argument
1094      * @return true if callback function return true for every element in the array, false otherwise
1095      */
1096     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1097     public static Object every(final Object self, final Object callbackfn, final Object thisArg) {
1098         return applyEvery(Global.toObject(self), callbackfn, thisArg);
1099     }
1100 
1101     private static boolean applyEvery(final Object self, final Object callbackfn, final Object thisArg) {
1102         return new IteratorAction<Boolean>(Global.toObject(self), callbackfn, thisArg, true) {
1103             @Override
1104             protected boolean forEach(final Object val, final int i) throws Throwable {
1105                 return (result = (boolean)EVERY_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self));
1106             }
1107         }.apply();
1108     }
1109 
1110     /**
1111      * ECMA 15.4.4.17 Array.prototype.some ( callbackfn [ , thisArg ] )
1112      *
1113      * @param self        self reference
1114      * @param callbackfn  callback function per element
1115      * @param thisArg     this argument
1116      * @return true if callback function returned true for any element in the array, false otherwise
1117      */
1118     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1119     public static Object some(final Object self, final Object callbackfn, final Object thisArg) {
1120         return new IteratorAction<Boolean>(Global.toObject(self), callbackfn, thisArg, false) {
1121             @Override
1122             protected boolean forEach(final Object val, final int i) throws Throwable {
1123                 return !(result = (boolean)SOME_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self));
1124             }
1125         }.apply();
1126     }
1127 
1128     /**
1129      * ECMA 15.4.4.18 Array.prototype.forEach ( callbackfn [ , thisArg ] )
1130      *
1131      * @param self        self reference
1132      * @param callbackfn  callback function per element
1133      * @param thisArg     this argument
1134      * @return undefined
1135      */
1136     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1137     public static Object forEach(final Object self, final Object callbackfn, final Object thisArg) {
1138         return new IteratorAction<Object>(Global.toObject(self), callbackfn, thisArg, ScriptRuntime.UNDEFINED) {
1139             @Override
1140             protected boolean forEach(final Object val, final int i) throws Throwable {
1141                 FOREACH_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self);
1142                 return true;
1143             }
1144         }.apply();
1145     }
1146 
1147     /**
1148      * ECMA 15.4.4.19 Array.prototype.map ( callbackfn [ , thisArg ] )
1149      *
1150      * @param self        self reference
1151      * @param callbackfn  callback function per element
1152      * @param thisArg     this argument
1153      * @return array with elements transformed by map function
1154      */
1155     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1156     public static Object map(final Object self, final Object callbackfn, final Object thisArg) {
1157         return new IteratorAction<NativeArray>(Global.toObject(self), callbackfn, thisArg, null) {
1158             @Override
1159             protected boolean forEach(final Object val, final int i) throws Throwable {
1160                 final Object r = MAP_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self);
1161                 result.defineOwnProperty(index, r);
1162                 return true;
1163             }
1164 
1165             @Override
1166             public void applyLoopBegin(final ArrayLikeIterator<Object> iter0) {
1167                 // map return array should be of same length as source array
1168                 // even if callback reduces source array length
1169                 result = new NativeArray(iter0.getLength());
1170             }
1171         }.apply();
1172     }
1173 
1174     /**
1175      * ECMA 15.4.4.20 Array.prototype.filter ( callbackfn [ , thisArg ] )
1176      *
1177      * @param self        self reference
1178      * @param callbackfn  callback function per element
1179      * @param thisArg     this argument
1180      * @return filtered array
1181      */
1182     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1183     public static Object filter(final Object self, final Object callbackfn, final Object thisArg) {
1184         return new IteratorAction<NativeArray>(Global.toObject(self), callbackfn, thisArg, new NativeArray()) {
1185             private int to = 0;
1186 
1187             @Override
1188             protected boolean forEach(final Object val, final int i) throws Throwable {
1189                 if ((boolean)FILTER_CALLBACK_INVOKER.invokeExact(callbackfn, thisArg, val, i, self)) {
1190                     result.defineOwnProperty(to++, val);
1191                 }
1192                 return true;
1193             }
1194         }.apply();
1195     }
1196 
1197     private static Object reduceInner(final ArrayLikeIterator<Object> iter, final Object self, final Object... args) {
1198         final Object  callbackfn          = args.length > 0 ? args[0] : ScriptRuntime.UNDEFINED;
1199         final boolean initialValuePresent = args.length > 1;
1200 
1201         Object initialValue = initialValuePresent ? args[1] : ScriptRuntime.UNDEFINED;
1202 
1203         if (callbackfn == ScriptRuntime.UNDEFINED) {
1204             throw typeError("not.a.function", "undefined");
1205         }
1206 
1207         if (!initialValuePresent) {
1208             if (iter.hasNext()) {
1209                 initialValue = iter.next();
1210             } else {
1211                 throw typeError("array.reduce.invalid.init");
1212             }
1213         }
1214 
1215         //if initial value is ScriptRuntime.UNDEFINED - step forward once.
1216         return new IteratorAction<Object>(Global.toObject(self), callbackfn, ScriptRuntime.UNDEFINED, initialValue, iter) {
1217             @Override
1218             protected boolean forEach(final Object val, final int i) throws Throwable {
1219                 // TODO: why can't I declare the second arg as Undefined.class?
1220                 result = REDUCE_CALLBACK_INVOKER.invokeExact(callbackfn, ScriptRuntime.UNDEFINED, result, val, i, self);
1221                 return true;
1222             }
1223         }.apply();
1224     }
1225 
1226     /**
1227      * ECMA 15.4.4.21 Array.prototype.reduce ( callbackfn [ , initialValue ] )
1228      *
1229      * @param self self reference
1230      * @param args arguments to reduce
1231      * @return accumulated result
1232      */
1233     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1234     public static Object reduce(final Object self, final Object... args) {
1235         return reduceInner(arrayLikeIterator(self), self, args);
1236     }
1237 
1238     /**
1239      * ECMA 15.4.4.22 Array.prototype.reduceRight ( callbackfn [ , initialValue ] )
1240      *
1241      * @param self        self reference
1242      * @param args arguments to reduce
1243      * @return accumulated result
1244      */
1245     @Function(attributes = Attribute.NOT_ENUMERABLE, arity = 1)
1246     public static Object reduceRight(final Object self, final Object... args) {
1247         return reduceInner(reverseArrayLikeIterator(self), self, args);
1248     }
1249 
1250     /**
1251      * Determine if Java bulk array operations may be used on the underlying
1252      * storage. This is possible only if the object's prototype chain is empty
1253      * or each of the prototypes in the chain is empty.
1254      *
1255      * @param self the object to examine
1256      * @return true if optimizable
1257      */
1258     private static boolean bulkable(final ScriptObject self) {
1259         return self.isArray() && !hasInheritedArrayEntries(self);
1260     }
1261 
1262     private static boolean hasInheritedArrayEntries(final ScriptObject self) {
1263         ScriptObject proto = self.getProto();
1264         while (proto != null) {
1265             if (proto.hasArrayEntries()) {
1266                 return true;
1267             }
1268             proto = proto.getProto();
1269         }
1270 
1271         return false;
1272     }
1273 
1274     private static MethodHandle createIteratorCallbackInvoker(final Class<?> rtype) {
1275         return Bootstrap.createDynamicInvoker("dyn:call", rtype, Object.class, Object.class, Object.class,
1276                 int.class, Object.class);
1277 
1278     }
1279 }
--- EOF ---