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.runtime.arrays;
  27 
  28 import static jdk.nashorn.internal.codegen.CompilerConstants.staticCall;
  29 
  30 import java.lang.invoke.MethodHandle;
  31 import java.lang.invoke.MethodHandles;
  32 import java.lang.reflect.Array;
  33 import java.nio.ByteBuffer;
  34 import java.util.ArrayList;
  35 import java.util.Iterator;
  36 import java.util.List;
  37 import jdk.internal.dynalink.CallSiteDescriptor;
  38 import jdk.internal.dynalink.linker.GuardedInvocation;
  39 import jdk.internal.dynalink.linker.LinkRequest;
  40 import jdk.nashorn.internal.codegen.CompilerConstants;
  41 import jdk.nashorn.internal.codegen.types.Type;
  42 import jdk.nashorn.internal.objects.Global;
  43 import jdk.nashorn.internal.runtime.JSType;
  44 import jdk.nashorn.internal.runtime.PropertyDescriptor;
  45 import jdk.nashorn.internal.runtime.ScriptRuntime;
  46 import jdk.nashorn.internal.runtime.UnwarrantedOptimismException;
  47 
  48 /**
  49  * ArrayData - abstraction for wrapping array elements
  50  */
  51 public abstract class ArrayData {
  52     /** Minimum chunk size for underlying arrays */
  53     protected static final int CHUNK_SIZE = 32;
  54 
  55     /** Mask for getting a chunk */
  56     protected static final int CHUNK_MASK = CHUNK_SIZE - 1;
  57 
  58     /** Untouched data - still link callsites as IntArrayData, but expands to
  59      *  a proper ArrayData when we try to write to it */
  60     public static final ArrayData EMPTY_ARRAY = new UntouchedArrayData();
  61 
  62     /**
  63      * Length of the array data. Not necessarily length of the wrapped array.
  64      * This is private to ensure that no one in a subclass is able to touch the length
  65      * without going through {@link #setLength}. This is used to implement
  66      * {@link LengthNotWritableFilter}s, ensuring that there are no ways past
  67      * a {@link #setLength} function replaced by a nop
  68      */
  69     private long length;
  70 
  71     /**
  72      * Method handle to throw an {@link UnwarrantedOptimismException} when getting an element
  73      * of the wrong type
  74      */
  75     protected static final CompilerConstants.Call THROW_UNWARRANTED = staticCall(MethodHandles.lookup(), ArrayData.class, "throwUnwarranted", void.class, ArrayData.class, int.class, int.class);
  76 
  77     /**
  78      * Immutable empty array to get ScriptObjects started.
  79      * Use the same array and convert it to mutable as soon as it is modified
  80      */
  81     private static class UntouchedArrayData extends ContinuousArrayData {
  82         private UntouchedArrayData() {
  83             super(0);
  84         }
  85 
  86         private ArrayData toRealArrayData() {
  87             return toRealArrayData(0);
  88         }
  89 
  90         private ArrayData toRealArrayData(final int index) {
  91             final IntArrayData newData = new IntArrayData(index + 1);
  92             if (index == 0) {
  93                 return newData;
  94             }
  95             return new DeletedRangeArrayFilter(newData, 0, index);
  96         }
  97 
  98         @Override
  99         public ContinuousArrayData copy() {
 100             assert length() == 0;
 101             return this;
 102         }
 103 
 104         @Override
 105         public Object asArrayOfType(final Class<?> componentType) {
 106             return Array.newInstance(componentType, 0);
 107         }
 108 
 109         @Override
 110         public Object[] asObjectArray() {
 111             return ScriptRuntime.EMPTY_ARRAY;
 112         }
 113 
 114         @Override
 115         public ArrayData ensure(final long safeIndex) {
 116             if (safeIndex > 0L) {
 117                 if (safeIndex >= SparseArrayData.MAX_DENSE_LENGTH) {
 118                     return new SparseArrayData(this, safeIndex + 1);
 119                 }
 120                 //known to fit in int
 121                 return toRealArrayData((int)safeIndex);
 122            }
 123            return this;
 124         }
 125 
 126         @Override
 127         public ArrayData convert(final Class<?> type) {
 128             return toRealArrayData(0).convert(type);
 129         }
 130 
 131         @Override
 132         public ArrayData delete(final int index) {
 133             return new DeletedRangeArrayFilter(this, index, index);
 134         }
 135 
 136         @Override
 137         public ArrayData delete(final long fromIndex, final long toIndex) {
 138             return new DeletedRangeArrayFilter(this, fromIndex, toIndex);
 139         }
 140 
 141         @Override
 142         public void shiftLeft(final int by) {
 143             //nop, always empty or we wouldn't be of this class
 144         }
 145 
 146         @Override
 147         public ArrayData shiftRight(final int by) {
 148             return this; //always empty or we wouldn't be of this class
 149         }
 150 
 151         @Override
 152         public ArrayData shrink(final long newLength) {
 153             return this;
 154         }
 155 
 156         @Override
 157         public ArrayData set(final int index, final Object value, final boolean strict) {
 158             return toRealArrayData(index).set(index, value, strict);
 159         }
 160 
 161         @Override
 162         public ArrayData set(final int index, final int value, final boolean strict) {
 163             return toRealArrayData(index).set(index, value, strict);
 164         }
 165 
 166         @Override
 167         public ArrayData set(final int index, final long value, final boolean strict) {
 168             return toRealArrayData(index).set(index, value, strict);
 169         }
 170 
 171         @Override
 172         public ArrayData set(final int index, final double value, final boolean strict) {
 173             return toRealArrayData(index).set(index, value, strict);
 174         }
 175 
 176         @Override
 177         public int getInt(final int index) {
 178             throw new ArrayIndexOutOfBoundsException(index); //empty
 179         }
 180 
 181         @Override
 182         public long getLong(final int index) {
 183             throw new ArrayIndexOutOfBoundsException(index); //empty
 184         }
 185 
 186         @Override
 187         public double getDouble(final int index) {
 188             throw new ArrayIndexOutOfBoundsException(index); //empty
 189         }
 190 
 191         @Override
 192         public Object getObject(final int index) {
 193             throw new ArrayIndexOutOfBoundsException(index); //empty
 194         }
 195 
 196         @Override
 197         public boolean has(final int index) {
 198             return false; //empty
 199         }
 200 
 201         @Override
 202         public Object pop() {
 203             return ScriptRuntime.UNDEFINED;
 204         }
 205 
 206         @Override
 207         public ArrayData push(final boolean strict, final Object item) {
 208             return toRealArrayData().push(strict, item);
 209         }
 210 
 211         @Override
 212         public ArrayData slice(final long from, final long to) {
 213             return this; //empty
 214         }
 215 
 216         @Override
 217         public ContinuousArrayData fastConcat(final ContinuousArrayData otherData) {
 218             return otherData.copy();
 219         }
 220 
 221         //no need to override fastPopInt, as the default behavior is to throw classcast exception so we
 222         //can relink and return an undefined, this is the IntArrayData default behavior
 223         @Override
 224         public String toString() {
 225             return getClass().getSimpleName();
 226         }
 227 
 228         @Override
 229         public MethodHandle getElementGetter(final Class<?> returnType, final int programPoint) {
 230             return null;
 231         }
 232 
 233         @Override
 234         public MethodHandle getElementSetter(final Class<?> elementType) {
 235             return null;
 236         }
 237 
 238         @Override
 239         public Class<?> getElementType() {
 240             return int.class;
 241         }
 242 
 243         @Override
 244         public Class<?> getBoxedElementType() {
 245             return Integer.class;
 246         }
 247     }
 248 
 249     /**
 250      * Constructor
 251      * @param length Virtual length of the array.
 252      */
 253     protected ArrayData(final long length) {
 254         this.length = length;
 255     }
 256 
 257     /**
 258      * Factory method for unspecified array - start as int
 259      * @return ArrayData
 260      */
 261     public final static ArrayData initialArray() {
 262         return new IntArrayData();
 263     }
 264 
 265     /**
 266      * Unwarranted thrower
 267      *
 268      * @param data         array data
 269      * @param programPoint program point
 270      * @param index        array index
 271      */
 272     protected static void throwUnwarranted(final ArrayData data, final int programPoint, final int index) {
 273         throw new UnwarrantedOptimismException(data.getObject(index), programPoint);
 274     }
 275 
 276     /**
 277      * Align an array size up to the nearest array chunk size
 278      * @param size size required
 279      * @return size given, always >= size
 280      */
 281     protected final static int alignUp(final int size) {
 282         return size + CHUNK_SIZE - 1 & ~(CHUNK_SIZE - 1);
 283     }
 284 
 285     /**
 286      * Factory method for unspecified array with given length - start as int array data
 287      *
 288      * @param length the initial length
 289      * @return ArrayData
 290      */
 291     public static final ArrayData allocate(final int length) {
 292         if (length == 0) {
 293             return new IntArrayData();
 294         } else if (length >= SparseArrayData.MAX_DENSE_LENGTH) {
 295             return new SparseArrayData(EMPTY_ARRAY, length);
 296         } else {
 297             return new DeletedRangeArrayFilter(new IntArrayData(length), 0, length - 1);
 298         }
 299     }
 300 
 301     /**
 302      * Factory method for unspecified given an array object
 303      *
 304      * @param  array the array
 305      * @return ArrayData wrapping this array
 306      */
 307     public static final ArrayData allocate(final Object array) {
 308         final Class<?> clazz = array.getClass();
 309 
 310         if (clazz == int[].class) {
 311             return new IntArrayData((int[])array, ((int[])array).length);
 312         } else if (clazz == long[].class) {
 313             return new LongArrayData((long[])array, ((long[])array).length);
 314         } else if (clazz == double[].class) {
 315             return new NumberArrayData((double[])array, ((double[])array).length);
 316         } else {
 317             return new ObjectArrayData((Object[])array, ((Object[])array).length);
 318         }
 319     }
 320 
 321     /**
 322      * Allocate an ArrayData wrapping a given array
 323      *
 324      * @param array the array to use for initial elements
 325      * @return the ArrayData
 326      */
 327     public static final ArrayData allocate(final int[] array) {
 328          return new IntArrayData(array, array.length);
 329     }
 330 
 331     /**
 332      * Allocate an ArrayData wrapping a given array
 333      *
 334      * @param array the array to use for initial elements
 335      * @return the ArrayData
 336      */
 337     public static final ArrayData allocate(final long[] array) {
 338         return new LongArrayData(array, array.length);
 339     }
 340 
 341     /**
 342      * Allocate an ArrayData wrapping a given array
 343      *
 344      * @param array the array to use for initial elements
 345      * @return the ArrayData
 346      */
 347     public static final ArrayData allocate(final double[] array) {
 348         return new NumberArrayData(array, array.length);
 349     }
 350 
 351     /**
 352      * Allocate an ArrayData wrapping a given array
 353      *
 354      * @param array the array to use for initial elements
 355      * @return the ArrayData
 356      */
 357     public static final ArrayData allocate(final Object[] array) {
 358         return new ObjectArrayData(array, array.length);
 359     }
 360 
 361     /**
 362      * Allocate an ArrayData wrapping a given nio ByteBuffer
 363      *
 364      * @param buf the nio ByteBuffer to wrap
 365      * @return the ArrayData
 366      */
 367     public static final ArrayData allocate(final ByteBuffer buf) {
 368         return new ByteBufferArrayData(buf);
 369     }
 370 
 371     /**
 372      * Apply a freeze filter to an ArrayData.
 373      *
 374      * @param underlying  the underlying ArrayData to wrap in the freeze filter
 375      * @return the frozen ArrayData
 376      */
 377     public static final ArrayData freeze(final ArrayData underlying) {
 378         return new FrozenArrayFilter(underlying);
 379     }
 380 
 381     /**
 382      * Apply a seal filter to an ArrayData.
 383      *
 384      * @param underlying  the underlying ArrayData to wrap in the seal filter
 385      * @return the sealed ArrayData
 386      */
 387     public static final ArrayData seal(final ArrayData underlying) {
 388         return new SealedArrayFilter(underlying);
 389     }
 390 
 391     /**
 392      * Prevent this array from being extended
 393      *
 394      * @param  underlying the underlying ArrayData to wrap in the non extensible filter
 395      * @return new array data, filtered
 396      */
 397     public static final ArrayData preventExtension(final ArrayData underlying) {
 398         return new NonExtensibleArrayFilter(underlying);
 399     }
 400 
 401     /**
 402      * Prevent this array from having its length reset
 403      *
 404      * @param underlying the underlying ArrayDAta to wrap in the non extensible filter
 405      * @return new array data, filtered
 406      */
 407     public static final ArrayData setIsLengthNotWritable(final ArrayData underlying) {
 408         return new LengthNotWritableFilter(underlying);
 409     }
 410 
 411     /**
 412      * Return the length of the array data. This may differ from the actual
 413      * length of the array this wraps as length may be set or gotten as any
 414      * other JavaScript Property
 415      *
 416      * Even though a JavaScript array length may be a long, we only store
 417      * int parts for the optimized array access. For long lengths there
 418      * are special cases anyway.
 419      *
 420      * TODO: represent arrays with "long" lengths as a special ArrayData
 421      * that basically maps to the ScriptObject directly for better abstraction
 422      *
 423      * @return the length of the data
 424      */
 425     public final long length() {
 426         return length;
 427     }
 428 
 429     /**
 430      * Return a copy of the array that can be modified without affecting this instance.
 431      * It is safe to return themselves for immutable subclasses.
 432      *
 433      * @return a new array
 434      */
 435     public abstract ArrayData copy();
 436 
 437     /**
 438      * Return a copy of the array data as an Object array.
 439      *
 440      * @return an Object array
 441      */
 442     public abstract Object[] asObjectArray();
 443 
 444     /**
 445      * Return a copy of the array data as an array of the specified type.
 446      *
 447      * @param componentType  the type of elements in the array
 448      * @return and array of the given type
 449      */
 450     public Object asArrayOfType(final Class<?> componentType) {
 451         return JSType.convertArray(asObjectArray(), componentType);
 452     }
 453 
 454     /**
 455      * Set the length of the data array
 456      *
 457      * @param length the new length for the data array
 458      */
 459     public void setLength(final long length) {
 460         this.length = length;
 461     }
 462 
 463     /**
 464      * Increase length by 1
 465      * @return the new length, not the old one (i.e. pre-increment)
 466      */
 467     protected final long increaseLength() {
 468         return ++this.length;
 469     }
 470 
 471     /**
 472      * Decrease length by 1.
 473      * @return the new length, not the old one (i.e. pre-decrement)
 474      */
 475     protected final long decreaseLength() {
 476         return --this.length;
 477     }
 478 
 479     /**
 480      * Shift the array data left
 481      *
 482      * TODO: explore start at an index and not at zero, to make these operations
 483      * even faster. Offset everything from the index. Costs memory but is probably
 484      * worth it
 485      *
 486      * @param by offset to shift
 487      */
 488     public abstract void shiftLeft(final int by);
 489 
 490     /**
 491      * Shift the array right
 492      *
 493      * @param by offset to shift
 494 
 495      * @return New arraydata (or same)
 496      */
 497     public abstract ArrayData shiftRight(final int by);
 498 
 499     /**
 500      * Ensure that the given index exists and won't fail in a subsequent access.
 501      * If {@code safeIndex} is equal or greater than the current length the length is
 502      * updated to {@code safeIndex + 1}.
 503      *
 504      * @param safeIndex the index to ensure wont go out of bounds
 505      * @return new array data (or same)
 506      */
 507     public abstract ArrayData ensure(final long safeIndex);
 508 
 509     /**
 510      * Shrink the array to a new length, may or may not retain the
 511      * inner array
 512      *
 513      * @param newLength new max length
 514      *
 515      * @return new array data (or same)
 516      */
 517     public abstract ArrayData shrink(final long newLength);
 518 
 519     /**
 520      * Set an object value at a given index
 521      *
 522      * @param index the index
 523      * @param value the value
 524      * @param strict are we in strict mode
 525      * @return new array data (or same)
 526      */
 527     public abstract ArrayData set(final int index, final Object value, final boolean strict);
 528 
 529     /**
 530      * Set an int value at a given index
 531      *
 532      * @param index the index
 533      * @param value the value
 534      * @param strict are we in strict mode
 535      * @return new array data (or same)
 536      */
 537     public abstract ArrayData set(final int index, final int value, final boolean strict);
 538 
 539     /**
 540      * Set a long value at a given index
 541      *
 542      * @param index the index
 543      * @param value the value
 544      * @param strict are we in strict mode
 545      * @return new array data (or same)
 546      */
 547     public abstract ArrayData set(final int index, final long value, final boolean strict);
 548 
 549     /**
 550      * Set an double value at a given index
 551      *
 552      * @param index the index
 553      * @param value the value
 554      * @param strict are we in strict mode
 555      * @return new array data (or same)
 556      */
 557     public abstract ArrayData set(final int index, final double value, final boolean strict);
 558 
 559     /**
 560      * Set an empty value at a given index. Should only affect Object array.
 561      *
 562      * @param index the index
 563      * @return new array data (or same)
 564      */
 565     public ArrayData setEmpty(final int index) {
 566         // Do nothing.
 567         return this;
 568     }
 569 
 570     /**
 571      * Set an empty value for a given range. Should only affect Object array.
 572      *
 573      * @param lo range low end
 574      * @param hi range high end
 575      * @return new array data (or same)
 576      */
 577     public ArrayData setEmpty(final long lo, final long hi) {
 578         // Do nothing.
 579         return this;
 580     }
 581 
 582     /**
 583      * Get an int value from a given index
 584      *
 585      * @param index the index
 586      * @return the value
 587      */
 588     public abstract int getInt(final int index);
 589 
 590     /**
 591      * Returns the optimistic type of this array data. Basically, when an array data object needs to throw an
 592      * {@link UnwarrantedOptimismException}, this type is used as the actual type of the return value.
 593      * @return the optimistic type of this array data.
 594      */
 595     public Type getOptimisticType() {
 596         return Type.OBJECT;
 597     }
 598 
 599     /**
 600      * Get optimistic int - default is that it's impossible. Overridden
 601      * by arrays that actually represents ints
 602      *
 603      * @param index        the index
 604      * @param programPoint program point
 605      * @return the value
 606      */
 607     public int getIntOptimistic(final int index, final int programPoint) {
 608         throw new UnwarrantedOptimismException(getObject(index), programPoint, getOptimisticType());
 609     }
 610 
 611     /**
 612      * Get a long value from a given index
 613      *
 614      * @param index the index
 615      * @return the value
 616      */
 617     public abstract long getLong(final int index);
 618 
 619     /**
 620      * Get optimistic long - default is that it's impossible. Overridden
 621      * by arrays that actually represents longs or narrower
 622      *
 623      * @param index        the index
 624      * @param programPoint program point
 625      * @return the value
 626      */
 627     public long getLongOptimistic(final int index, final int programPoint) {
 628         throw new UnwarrantedOptimismException(getObject(index), programPoint, getOptimisticType());
 629     }
 630 
 631     /**
 632      * Get a double value from a given index
 633      *
 634      * @param index the index
 635      * @return the value
 636      */
 637     public abstract double getDouble(final int index);
 638 
 639     /**
 640      * Get optimistic double - default is that it's impossible. Overridden
 641      * by arrays that actually represents doubles or narrower
 642      *
 643      * @param index        the index
 644      * @param programPoint program point
 645      * @return the value
 646      */
 647     public double getDoubleOptimistic(final int index, final int programPoint) {
 648         throw new UnwarrantedOptimismException(getObject(index), programPoint, getOptimisticType());
 649     }
 650 
 651     /**
 652      * Get an Object value from a given index
 653      *
 654      * @param index the index
 655      * @return the value
 656      */
 657     public abstract Object getObject(final int index);
 658 
 659     /**
 660      * Tests to see if an entry exists (avoids boxing.)
 661      * @param index the index
 662      * @return true if entry exists
 663      */
 664     public abstract boolean has(final int index);
 665 
 666     /**
 667      * Returns if element at specific index can be deleted or not.
 668      *
 669      * @param index the index of the element
 670      * @param strict are we in strict mode
 671      *
 672      * @return true if element can be deleted
 673      */
 674     public boolean canDelete(final int index, final boolean strict) {
 675         return true;
 676     }
 677 
 678     /**
 679      * Returns if element at specific index range can be deleted or not.
 680      *
 681      * @param fromIndex  the start index
 682      * @param toIndex    the end index
 683      * @param strict     are we in strict mode
 684      *
 685      * @return true if range can be deleted
 686      */
 687     public boolean canDelete(final long fromIndex, final long toIndex, final boolean strict) {
 688         return true;
 689     }
 690 
 691     /**
 692      * Returns property descriptor for element at a given index
 693      *
 694      * @param global the global object
 695      * @param index  the index
 696      *
 697      * @return property descriptor for element
 698      */
 699     public PropertyDescriptor getDescriptor(final Global global, final int index) {
 700         return global.newDataDescriptor(getObject(index), true, true, true);
 701     }
 702 
 703     /**
 704      * Delete an array value at the given index, substituting
 705      * for an undefined
 706      *
 707      * @param index the index
 708      * @return new array data (or same)
 709      */
 710     public abstract ArrayData delete(final int index);
 711 
 712     /**
 713      * Delete a given range from this array;
 714      *
 715      * @param fromIndex  from index (inclusive)
 716      * @param toIndex    to index (inclusive)
 717      *
 718      * @return new ArrayData after deletion
 719      */
 720     public abstract ArrayData delete(final long fromIndex, final long toIndex);
 721 
 722     /**
 723      * Convert the ArrayData to one with a different element type
 724      * Currently Arrays are not collapsed to narrower types, just to
 725      * wider ones. Attempting to narrow an array will assert
 726      *
 727      * @param type new element type
 728      * @return new array data
 729      */
 730     public abstract ArrayData convert(final Class<?> type);
 731 
 732     /**
 733      * Push an array of items to the end of the array
 734      *
 735      * @param strict are we in strict mode
 736      * @param items  the items
 737      * @return new array data (or same)
 738      */
 739     public ArrayData push(final boolean strict, final Object... items) {
 740         if (items.length == 0) {
 741             return this;
 742         }
 743 
 744         final Class<?>  widest  = widestType(items);
 745 
 746         ArrayData newData = convert(widest);
 747         long      pos     = newData.length;
 748         for (final Object item : items) {
 749             newData = newData.ensure(pos); //avoid sparse array
 750             newData.set((int)pos++, item, strict);
 751         }
 752         return newData;
 753     }
 754 
 755     /**
 756      * Push an array of items to the end of the array
 757      *
 758      * @param strict are we in strict mode
 759      * @param item   the item
 760      * @return new array data (or same)
 761      */
 762     public ArrayData push(final boolean strict, final Object item) {
 763         return push(strict, new Object[] { item });
 764     }
 765 
 766     /**
 767      * Pop an element from the end of the array
 768      *
 769      * @return the popped element
 770      */
 771     public abstract Object pop();
 772 
 773     /**
 774      * Slice out a section of the array and return that
 775      * subsection as a new array data: [from, to)
 776      *
 777      * @param from start index
 778      * @param to   end index + 1
 779      * @return new array data
 780      */
 781     public abstract ArrayData slice(final long from, final long to);
 782 
 783     /**
 784      * Fast splice operation. This just modifies the array according to the number of
 785      * elements added and deleted but does not insert the added elements. Throws
 786      * {@code UnsupportedOperationException} if fast splice operation is not supported
 787      * for this class or arguments.
 788      *
 789      * @param start start index of splice operation
 790      * @param removed number of removed elements
 791      * @param added number of added elements
 792      * @throws UnsupportedOperationException if fast splice is not supported for the class or arguments.
 793      * @return new arraydata, but this never happens because we always throw an exception
 794      */
 795     public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException {
 796         throw new UnsupportedOperationException();
 797     }
 798 
 799     static Class<?> widestType(final Object... items) {
 800         assert items.length > 0;
 801 
 802         Class<?> widest = Integer.class;
 803 
 804         for (final Object item : items) {
 805             if (item == null) {
 806                 return Object.class;
 807             }
 808             final Class<?> itemClass = item.getClass();
 809             if (itemClass == Long.class) {
 810                 if (widest == Integer.class) {
 811                     widest = Long.class;
 812                 }
 813             } else if (itemClass == Double.class || itemClass == Float.class) {
 814                 if (widest == Integer.class || widest == Long.class) {
 815                     widest = Double.class;
 816                 }
 817             } else if (itemClass != Integer.class && itemClass != Short.class && itemClass != Byte.class) {
 818                 return Object.class;
 819             }
 820         }
 821 
 822         return widest;
 823     }
 824 
 825     /**
 826      * Return a list of keys in the array for the iterators
 827      * @return iterator key list
 828      */
 829     protected List<Long> computeIteratorKeys() {
 830         final List<Long> keys = new ArrayList<>();
 831 
 832         final long len = length();
 833         for (long i = 0L; i < len; i = nextIndex(i)) {
 834             if (has((int)i)) {
 835                 keys.add(i);
 836             }
 837         }
 838 
 839         return keys;
 840     }
 841 
 842     /**
 843      * Return an iterator that goes through all indexes of elements
 844      * in this array. This includes those after array.length if
 845      * they exist
 846      *
 847      * @return iterator
 848      */
 849     public Iterator<Long> indexIterator() {
 850         return computeIteratorKeys().iterator();
 851     }
 852 
 853     /**
 854      * Exponential growth function for array size when in
 855      * need of resizing.
 856      *
 857      * @param size current size
 858      * @return next size to allocate for internal array
 859      */
 860     public static int nextSize(final int size) {
 861         return alignUp(size + 1) * 2;
 862     }
 863 
 864     /**
 865      * Return the next valid index from a given one. Subclassed for various
 866      * array representation
 867      *
 868      * @param index the current index
 869      *
 870      * @return the next index
 871      */
 872     long nextIndex(final long index) {
 873         return index + 1;
 874     }
 875 
 876     static Object invoke(final MethodHandle mh, final Object arg) {
 877         try {
 878             return mh.invoke(arg);
 879         } catch (final RuntimeException | Error e) {
 880             throw e;
 881         } catch (final Throwable t) {
 882             throw new RuntimeException(t);
 883         }
 884     }
 885 
 886    /**
 887      * Find a fast call if one exists
 888      *
 889      * @param clazz    array data class
 890      * @param desc     callsite descriptor
 891      * @param request  link request
 892      * @return fast property getter if one is found
 893      */
 894     public GuardedInvocation findFastCallMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) {
 895         return null;
 896     }
 897 
 898     /**
 899      * Find a fast property getter if one exists
 900      *
 901      * @param clazz    array data class
 902      * @param desc     callsite descriptor
 903      * @param request  link request
 904      * @param operator operator
 905      * @return fast property getter if one is found
 906      */
 907     public GuardedInvocation findFastGetMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request, final String operator) {
 908         return null;
 909     }
 910 
 911     /**
 912      * Find a fast element getter if one exists
 913      *
 914      * @param clazz   array data class
 915      * @param desc    callsite descriptor
 916      * @param request link request
 917      * @return fast index getter if one is found
 918      */
 919     public GuardedInvocation findFastGetIndexMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) { // array, index, value
 920         return null;
 921     }
 922 
 923     /**
 924      * Find a fast element setter if one exists
 925      *
 926      * @param clazz   array data class
 927      * @param desc    callsite descriptor
 928      * @param request link request
 929      * @return fast index getter if one is found
 930      */
 931     public GuardedInvocation findFastSetIndexMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) { // array, index, value
 932         return null;
 933     }
 934 }