ArrayData.java revision 1036:f0b5e3900a10
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 26package jdk.nashorn.internal.runtime.arrays; 27 28import static jdk.nashorn.internal.codegen.CompilerConstants.staticCall; 29import java.lang.invoke.MethodHandle; 30import java.lang.invoke.MethodHandles; 31import java.nio.ByteBuffer; 32import jdk.internal.dynalink.CallSiteDescriptor; 33import jdk.internal.dynalink.linker.GuardedInvocation; 34import jdk.internal.dynalink.linker.LinkRequest; 35import jdk.nashorn.internal.codegen.CompilerConstants; 36import jdk.nashorn.internal.codegen.types.Type; 37import jdk.nashorn.internal.objects.Global; 38import jdk.nashorn.internal.runtime.JSType; 39import jdk.nashorn.internal.runtime.PropertyDescriptor; 40import jdk.nashorn.internal.runtime.UnwarrantedOptimismException; 41 42/** 43 * ArrayData - abstraction for wrapping array elements 44 */ 45public abstract class ArrayData { 46 /** Minimum chunk size for underlying arrays */ 47 protected static final int CHUNK_SIZE = 32; 48 49 /** Mask for getting a chunk */ 50 protected static final int CHUNK_MASK = CHUNK_SIZE - 1; 51 52 /** 53 * Immutable empty array to get ScriptObjects started. 54 */ 55 public static final ArrayData EMPTY_ARRAY = new NoTypeArrayData(); 56 57 /** 58 * Length of the array data. Not necessarily length of the wrapped array. 59 */ 60 protected long length; 61 62 /** 63 * Method handle to throw an {@link UnwarrantedOptimismException} when getting an element 64 * of the wrong type 65 */ 66 protected static final CompilerConstants.Call THROW_UNWARRANTED = staticCall(MethodHandles.lookup(), ArrayData.class, "throwUnwarranted", void.class, ArrayData.class, int.class, int.class); 67 68 /** 69 * Constructor 70 * @param length Virtual length of the array. 71 */ 72 protected ArrayData(final long length) { 73 this.length = length; 74 } 75 76 /** 77 * Factory method for unspecified array - start as int 78 * @return ArrayData 79 */ 80 public static ArrayData initialArray() { 81 return new IntArrayData(); 82 } 83 84 /** 85 * Unwarranted thrower 86 * 87 * @param data array data 88 * @param programPoint program point 89 * @param index array index 90 */ 91 protected static void throwUnwarranted(final ArrayData data, final int programPoint, final int index) { 92 throw new UnwarrantedOptimismException(data.getObject(index), programPoint); 93 } 94 95 private static int alignUp(final int size) { 96 return size + CHUNK_SIZE - 1 & ~(CHUNK_SIZE - 1); 97 } 98 99 /** 100 * Generic invalidation hook for script object to have call sites to this array indexing 101 * relinked, e.g. when a native array is marked as non extensible 102 */ 103 public void invalidateGetters() { 104 //subclass responsibility 105 } 106 107 /** 108 * Generic invalidation hook for script object to have call sites to this array indexing 109 * relinked, e.g. when a native array is marked as non extensible 110 */ 111 public void invalidateSetters() { 112 //subclass responsibility 113 } 114 115 /** 116 * Factory method for unspecified array with given length - start as int array data 117 * 118 * @param length the initial length 119 * @return ArrayData 120 */ 121 public static ArrayData allocate(final int length) { 122 if (length == 0) { 123 return new IntArrayData(); 124 } else if (length >= SparseArrayData.MAX_DENSE_LENGTH) { 125 return new SparseArrayData(EMPTY_ARRAY, length); 126 } else { 127 return new DeletedRangeArrayFilter(new IntArrayData(length), 0, length - 1); 128 } 129 } 130 131 /** 132 * Factory method for unspecified given an array object 133 * 134 * @param array the array 135 * @return ArrayData wrapping this array 136 */ 137 public static ArrayData allocate(final Object array) { 138 final Class<?> clazz = array.getClass(); 139 140 if (clazz == int[].class) { 141 return new IntArrayData((int[])array, ((int[])array).length); 142 } else if (clazz == long[].class) { 143 return new LongArrayData((long[])array, ((long[])array).length); 144 } else if (clazz == double[].class) { 145 return new NumberArrayData((double[])array, ((double[])array).length); 146 } else { 147 return new ObjectArrayData((Object[])array, ((Object[])array).length); 148 } 149 } 150 151 /** 152 * Allocate an ArrayData wrapping a given array 153 * 154 * @param array the array to use for initial elements 155 * @return the ArrayData 156 */ 157 public static ArrayData allocate(final int[] array) { 158 return new IntArrayData(array, array.length); 159 } 160 161 /** 162 * Allocate an ArrayData wrapping a given array 163 * 164 * @param array the array to use for initial elements 165 * @return the ArrayData 166 */ 167 public static ArrayData allocate(final long[] array) { 168 return new LongArrayData(array, array.length); 169 } 170 171 /** 172 * Allocate an ArrayData wrapping a given array 173 * 174 * @param array the array to use for initial elements 175 * @return the ArrayData 176 */ 177 public static ArrayData allocate(final double[] array) { 178 return new NumberArrayData(array, array.length); 179 } 180 181 /** 182 * Allocate an ArrayData wrapping a given array 183 * 184 * @param array the array to use for initial elements 185 * @return the ArrayData 186 */ 187 public static ArrayData allocate(final Object[] array) { 188 return new ObjectArrayData(array, array.length); 189 } 190 191 /** 192 * Allocate an ArrayData wrapping a given nio ByteBuffer 193 * 194 * @param buf the nio ByteBuffer to wrap 195 * @return the ArrayData 196 */ 197 public static ArrayData allocate(final ByteBuffer buf) { 198 return new ByteBufferArrayData(buf); 199 } 200 201 /** 202 * Apply a freeze filter to an ArrayData. 203 * 204 * @param underlying the underlying ArrayData to wrap in the freeze filter 205 * @return the frozen ArrayData 206 */ 207 public static ArrayData freeze(final ArrayData underlying) { 208 return new FrozenArrayFilter(underlying); 209 } 210 211 /** 212 * Apply a seal filter to an ArrayData. 213 * 214 * @param underlying the underlying ArrayData to wrap in the seal filter 215 * @return the sealed ArrayData 216 */ 217 public static ArrayData seal(final ArrayData underlying) { 218 return new SealedArrayFilter(underlying); 219 } 220 221 /** 222 * Return the length of the array data. This may differ from the actual 223 * length of the array this wraps as length may be set or gotten as any 224 * other JavaScript Property 225 * 226 * Even though a JavaScript array length may be a long, we only store 227 * int parts for the optimized array access. For long lengths there 228 * are special cases anyway. 229 * 230 * TODO: represent arrays with "long" lengths as a special ArrayData 231 * that basically maps to the ScriptObject directly for better abstraction 232 * 233 * @return the length of the data 234 */ 235 public final long length() { 236 return length; 237 } 238 239 /** 240 * Return a copy of the array that can be modified without affecting this instance. 241 * It is safe to return themselves for immutable subclasses. 242 * 243 * @return a new array 244 */ 245 public abstract ArrayData copy(); 246 247 /** 248 * Return a copy of the array data as an Object array. 249 * 250 * @return an Object array 251 */ 252 public abstract Object[] asObjectArray(); 253 254 /** 255 * Return a copy of the array data as an array of the specified type. 256 * 257 * @param componentType the type of elements in the array 258 * @return and array of the given type 259 */ 260 public Object asArrayOfType(final Class<?> componentType) { 261 return JSType.convertArray(asObjectArray(), componentType); 262 } 263 264 /** 265 * Set the length of the data array 266 * 267 * @param length the new length for the data array 268 */ 269 public void setLength(final long length) { 270 this.length = length; 271 } 272 273 /** 274 * Shift the array data left 275 * 276 * TODO: explore start at an index and not at zero, to make these operations 277 * even faster. Offset everything from the index. Costs memory but is probably 278 * worth it 279 * 280 * @param by offset to shift 281 */ 282 public abstract void shiftLeft(int by); 283 284 /** 285 * Shift the array right 286 * 287 * @param by offset to shift 288 289 * @return New arraydata (or same) 290 */ 291 public abstract ArrayData shiftRight(int by); 292 293 /** 294 * Ensure that the given index exists and won't fail subsequent 295 * 296 * @param safeIndex the index to ensure wont go out of bounds 297 * @return new array data (or same) 298 */ 299 public abstract ArrayData ensure(long safeIndex); 300 301 /** 302 * Shrink the array to a new length, may or may not retain the 303 * inner array 304 * 305 * @param newLength new max length 306 * 307 * @return new array data (or same) 308 */ 309 public abstract ArrayData shrink(long newLength); 310 311 /** 312 * Set an object value at a given index 313 * 314 * @param index the index 315 * @param value the value 316 * @param strict are we in strict mode 317 * @return new array data (or same) 318 */ 319 public abstract ArrayData set(int index, Object value, boolean strict); 320 321 /** 322 * Set an int value at a given index 323 * 324 * @param index the index 325 * @param value the value 326 * @param strict are we in strict mode 327 * @return new array data (or same) 328 */ 329 public abstract ArrayData set(int index, int value, boolean strict); 330 331 /** 332 * Set a long value at a given index 333 * 334 * @param index the index 335 * @param value the value 336 * @param strict are we in strict mode 337 * @return new array data (or same) 338 */ 339 public abstract ArrayData set(int index, long value, boolean strict); 340 341 /** 342 * Set an double value at a given index 343 * 344 * @param index the index 345 * @param value the value 346 * @param strict are we in strict mode 347 * @return new array data (or same) 348 */ 349 public abstract ArrayData set(int index, double value, boolean strict); 350 351 /** 352 * Set an empty value at a given index. Should only affect Object array. 353 * 354 * @param index the index 355 * @return new array data (or same) 356 */ 357 public ArrayData setEmpty(final int index) { 358 // Do nothing. 359 return this; 360 } 361 362 /** 363 * Set an empty value for a given range. Should only affect Object array. 364 * 365 * @param lo range low end 366 * @param hi range high end 367 * @return new array data (or same) 368 */ 369 public ArrayData setEmpty(final long lo, final long hi) { 370 // Do nothing. 371 return this; 372 } 373 374 /** 375 * Get an int value from a given index 376 * 377 * @param index the index 378 * @return the value 379 */ 380 public abstract int getInt(int index); 381 382 /** 383 * Returns the optimistic type of this array data. Basically, when an array data object needs to throw an 384 * {@link UnwarrantedOptimismException}, this type is used as the actual type of the return value. 385 * @return the optimistic type of this array data. 386 */ 387 public Type getOptimisticType() { 388 return Type.OBJECT; 389 } 390 391 /** 392 * Get optimistic int - default is that it's impossible. Overridden 393 * by arrays that actually represents ints 394 * 395 * @param index the index 396 * @param programPoint program point 397 * @return the value 398 */ 399 public int getIntOptimistic(final int index, final int programPoint) { 400 throw new UnwarrantedOptimismException(getObject(index), programPoint, getOptimisticType()); 401 } 402 403 /** 404 * Get a long value from a given index 405 * 406 * @param index the index 407 * @return the value 408 */ 409 public abstract long getLong(int index); 410 411 /** 412 * Get optimistic long - default is that it's impossible. Overridden 413 * by arrays that actually represents longs or narrower 414 * 415 * @param index the index 416 * @param programPoint program point 417 * @return the value 418 */ 419 public long getLongOptimistic(final int index, final int programPoint) { 420 throw new UnwarrantedOptimismException(getObject(index), programPoint, getOptimisticType()); 421 } 422 423 /** 424 * Get a double value from a given index 425 * 426 * @param index the index 427 * @return the value 428 */ 429 public abstract double getDouble(int index); 430 431 /** 432 * Get optimistic double - default is that it's impossible. Overridden 433 * by arrays that actually represents doubles or narrower 434 * 435 * @param index the index 436 * @param programPoint program point 437 * @return the value 438 */ 439 public double getDoubleOptimistic(final int index, final int programPoint) { 440 throw new UnwarrantedOptimismException(getObject(index), programPoint, getOptimisticType()); 441 } 442 443 /** 444 * Get an Object value from a given index 445 * 446 * @param index the index 447 * @return the value 448 */ 449 public abstract Object getObject(int index); 450 451 /** 452 * Tests to see if an entry exists (avoids boxing.) 453 * @param index the index 454 * @return true if entry exists 455 */ 456 public abstract boolean has(int index); 457 458 /** 459 * Returns if element at specific index can be deleted or not. 460 * 461 * @param index the index of the element 462 * @param strict are we in strict mode 463 * 464 * @return true if element can be deleted 465 */ 466 public boolean canDelete(final int index, final boolean strict) { 467 return true; 468 } 469 470 /** 471 * Returns if element at specific index range can be deleted or not. 472 * 473 * @param fromIndex the start index 474 * @param toIndex the end index 475 * @param strict are we in strict mode 476 * 477 * @return true if range can be deleted 478 */ 479 public boolean canDelete(final long fromIndex, final long toIndex, final boolean strict) { 480 return true; 481 } 482 483 /** 484 * Returns property descriptor for element at a given index 485 * 486 * @param global the global object 487 * @param index the index 488 * 489 * @return property descriptor for element 490 */ 491 public PropertyDescriptor getDescriptor(final Global global, final int index) { 492 return global.newDataDescriptor(getObject(index), true, true, true); 493 } 494 495 /** 496 * Delete an array value at the given index, substituting 497 * for an undefined 498 * 499 * @param index the index 500 * @return new array data (or same) 501 */ 502 public abstract ArrayData delete(int index); 503 504 /** 505 * Delete a given range from this array; 506 * 507 * @param fromIndex from index (inclusive) 508 * @param toIndex to index (inclusive) 509 * 510 * @return new ArrayData after deletion 511 */ 512 public abstract ArrayData delete(long fromIndex, long toIndex); 513 514 /** 515 * Convert the ArrayData to one with a different element type 516 * Currently Arrays are not collapsed to narrower types, just to 517 * wider ones. Attempting to narrow an array will assert 518 * 519 * @param type new element type 520 * @return new array data 521 */ 522 public abstract ArrayData convert(Class<?> type); 523 524 /** 525 * Push an array of items to the end of the array 526 * 527 * @param strict are we in strict mode 528 * @param items the items 529 * @return new array data (or same) 530 */ 531 public ArrayData push(final boolean strict, final Object... items) { 532 if (items.length == 0) { 533 return this; 534 } 535 536 final Class<?> widest = widestType(items); 537 538 ArrayData newData = convert(widest); 539 long pos = newData.length(); 540 for (final Object item : items) { 541 newData = newData.ensure(pos); //avoid sparse array 542 newData.set((int)pos++, item, strict); 543 } 544 return newData; 545 } 546 547 /** 548 * Push an array of items to the end of the array 549 * 550 * @param strict are we in strict mode 551 * @param item the item 552 * @return new array data (or same) 553 */ 554 public ArrayData push(final boolean strict, final Object item) { 555 return push(strict, new Object[] { item }); 556 } 557 558 /** 559 * Push an array of items to the end of the array 560 * 561 * @param strict are we in strict mode 562 * @param item the item 563 * @return new array data (or same) 564 */ 565 public ArrayData push(final boolean strict, final double item) { 566 return push(strict, item); 567 } 568 569 /** 570 * Push an array of items to the end of the array 571 * 572 * @param strict are we in strict mode 573 * @param item the item 574 * @return new array data (or same) 575 */ 576 public ArrayData push(final boolean strict, final long item) { 577 return push(strict, item); 578 } 579 580 /** 581 * Push an array of items to the end of the array 582 * 583 * @param strict are we in strict mode 584 * @param item the item 585 * @return new array data (or same) 586 */ 587 public ArrayData push(final boolean strict, final int item) { 588 return push(strict, item); 589 } 590 591 /** 592 * Pop an element from the end of the array 593 * 594 * @return the popped element 595 */ 596 public abstract Object pop(); 597 598 /** 599 * Slice out a section of the array and return that 600 * subsection as a new array data: [from, to) 601 * 602 * @param from start index 603 * @param to end index + 1 604 * @return new array data 605 */ 606 public abstract ArrayData slice(long from, long to); 607 608 /** 609 * Fast splice operation. This just modifies the array according to the number of 610 * elements added and deleted but does not insert the added elements. Throws 611 * {@code UnsupportedOperationException} if fast splice operation is not supported 612 * for this class or arguments. 613 * 614 * @param start start index of splice operation 615 * @param removed number of removed elements 616 * @param added number of added elements 617 * @throws UnsupportedOperationException if fast splice is not supported for the class or arguments. 618 * @return new arraydata, but this never happens because we always throw an exception 619 */ 620 public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException { 621 throw new UnsupportedOperationException(); 622 } 623 624 static Class<?> widestType(final Object... items) { 625 assert items.length > 0; 626 627 Class<?> widest = Integer.class; 628 629 for (final Object item : items) { 630 if (item == null) { 631 return Object.class; 632 } 633 final Class<?> itemClass = item.getClass(); 634 if (itemClass == Long.class) { 635 if (widest == Integer.class) { 636 widest = Long.class; 637 } 638 } else if (itemClass == Double.class || itemClass == Float.class) { 639 if (widest == Integer.class || widest == Long.class) { 640 widest = Double.class; 641 } 642 } else if (itemClass != Integer.class && itemClass != Short.class && itemClass != Byte.class) { 643 return Object.class; 644 } 645 } 646 647 return widest; 648 } 649 650 /** 651 * Exponential growth function for array size when in 652 * need of resizing. 653 * 654 * @param size current size 655 * @return next size to allocate for internal array 656 */ 657 public static int nextSize(final int size) { 658 return alignUp(size + 1) * 2; 659 } 660 661 /** 662 * Return the next valid index from a given one. Subclassed for various 663 * array representation 664 * 665 * @param index the current index 666 * 667 * @return the next index 668 */ 669 public long nextIndex(final long index) { 670 return index + 1; 671 } 672 673 static Object invoke(final MethodHandle mh, final Object arg) { 674 try { 675 return mh.invoke(arg); 676 } catch (final RuntimeException | Error e) { 677 throw e; 678 } catch (final Throwable t) { 679 throw new RuntimeException(t); 680 } 681 } 682 683 /** 684 * Find a fast call if one exists 685 * 686 * @param clazz array data class 687 * @param desc callsite descriptor 688 * @param request link request 689 * @return fast property getter if one is found 690 */ 691 public GuardedInvocation findFastCallMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) { 692 return null; 693 } 694 695 /** 696 * Find a fast property getter if one exists 697 * 698 * @param clazz array data class 699 * @param desc callsite descriptor 700 * @param request link request 701 * @param operator operator 702 * @return fast property getter if one is found 703 */ 704 public GuardedInvocation findFastGetMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request, final String operator) { 705 return null; 706 } 707 708 /** 709 * Find a fast element getter if one exists 710 * 711 * @param clazz array data class 712 * @param desc callsite descriptor 713 * @param request link request 714 * @return fast index getter if one is found 715 */ 716 public GuardedInvocation findFastGetIndexMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) { // array, index, value 717 return null; 718 } 719 720 /** 721 * Find a fast element setter if one exists 722 * 723 * @param clazz array data class 724 * @param desc callsite descriptor 725 * @param request link request 726 * @return fast index getter if one is found 727 */ 728 public GuardedInvocation findFastSetIndexMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) { // array, index, value 729 return null; 730 } 731 732} 733