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