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