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 import java.lang.invoke.MethodHandle;
  30 import java.lang.invoke.MethodHandles;
  31 import java.lang.reflect.Array;
  32 import java.nio.ByteBuffer;
  33 import java.util.ArrayList;
  34 import java.util.Iterator;
  35 import java.util.List;
  36 import jdk.internal.dynalink.CallSiteDescriptor;
  37 import jdk.internal.dynalink.linker.GuardedInvocation;
  38 import jdk.internal.dynalink.linker.LinkRequest;
  39 import jdk.nashorn.internal.codegen.CompilerConstants;
  40 import jdk.nashorn.internal.codegen.types.Type;
  41 import jdk.nashorn.internal.objects.Global;
  42 import jdk.nashorn.internal.runtime.JSType;
  43 import jdk.nashorn.internal.runtime.PropertyDescriptor;
  44 import jdk.nashorn.internal.runtime.ScriptRuntime;
  45 import jdk.nashorn.internal.runtime.UnwarrantedOptimismException;
  46 
  47 /**
  48  * ArrayData - abstraction for wrapping array elements
  49  */
  50 public abstract class ArrayData {
  51     /** Minimum chunk size for underlying arrays */
  52     protected static final int CHUNK_SIZE = 32;
  53 
  54     /** Mask for getting a chunk */
  55     protected static final int CHUNK_MASK = CHUNK_SIZE - 1;
  56 
  57     /** Untouched data - still link callsites as IntArrayData, but expands to
  58      *  a proper ArrayData when we try to write to it */
  59     public static final ArrayData EMPTY_ARRAY = new UntouchedArrayData();
  60 
  61     /**
  62      * Length of the array data. Not necessarily length of the wrapped array.
  63      * This is private to ensure that no one in a subclass is able to touch the length
  64      * without going through {@link setLength}. This is used to implement
  65      * {@link LengthNotWritableFilter}s, ensuring that there are no ways past
  66      * a {@link setLength} function replaced by a nop
  67      */
  68     private long length;
  69 
  70     /**
  71      * Method handle to throw an {@link UnwarrantedOptimismException} when getting an element
  72      * of the wrong type
  73      */
  74     protected static final CompilerConstants.Call THROW_UNWARRANTED = staticCall(MethodHandles.lookup(), ArrayData.class, "throwUnwarranted", void.class, ArrayData.class, int.class, int.class);
  75 
  76     /**
  77      * Immutable empty array to get ScriptObjects started.
  78      * Use the same array and convert it to mutable as soon as it is modified
  79      */
  80     private static class UntouchedArrayData extends ContinuousArrayData {
  81         private UntouchedArrayData() {
  82             this(0);
  83         }
  84 
  85         private UntouchedArrayData(final int length) {
  86             super(length);
  87         }
  88 
  89         private ArrayData toRealArrayData() {
  90             return toRealArrayData(0);
  91         }
  92 
  93         private ArrayData toRealArrayData(final int index) {
  94             final IntArrayData newData = new IntArrayData(index + 1);
  95             if (index == 0) {
  96                 return newData;
  97             }
  98             return new DeletedRangeArrayFilter(newData, 0, index);
  99         }
 100 
 101         @Override
 102         public ContinuousArrayData copy() {
 103             return new UntouchedArrayData((int)length());
 104         }
 105 
 106         @Override
 107         public Object asArrayOfType(final Class<?> componentType) {
 108             return Array.newInstance(componentType, 0);
 109         }
 110 
 111         @Override
 112         public Object[] asObjectArray() {
 113             return ScriptRuntime.EMPTY_ARRAY;
 114         }
 115 
 116         @Override
 117         public ArrayData ensure(final long safeIndex) {
 118             if (safeIndex > 0L) {
 119                 if (safeIndex >= SparseArrayData.MAX_DENSE_LENGTH) {
 120                     return new SparseArrayData(this, safeIndex + 1);
 121                 }
 122                 //known to fit in int
 123                 return toRealArrayData((int)safeIndex).ensure(safeIndex);
 124            }
 125            return this;
 126         }
 127 
 128         @Override
 129         public ArrayData convert(final Class<?> type) {
 130             return toRealArrayData(0).convert(type);
 131         }
 132 
 133         @Override
 134         public ArrayData delete(final int index) {
 135             return new DeletedRangeArrayFilter(this, index, index);
 136         }
 137 
 138         @Override
 139         public ArrayData delete(final long fromIndex, final long toIndex) {
 140             return new DeletedRangeArrayFilter(this, fromIndex, toIndex);
 141         }
 142 
 143         @Override
 144         public void shiftLeft(final int by) {
 145             //nop, always empty or we wouldn't be of this class
 146         }
 147 
 148         @Override
 149         public ArrayData shiftRight(final int by) {
 150             return this; //always empty or we wouldn't be of this class
 151         }
 152 
 153         @Override
 154         public ArrayData shrink(final long newLength) {
 155             return this;
 156         }
 157 
 158         @Override
 159         public ArrayData set(final int index, final Object value, final boolean strict) {
 160             return toRealArrayData(index).set(index, value, strict);
 161         }
 162 
 163         @Override
 164         public ArrayData set(final int index, final int value, final boolean strict) {
 165             return toRealArrayData(index).set(index, value, strict);
 166         }
 167 
 168         @Override
 169         public ArrayData set(final int index, final long value, final boolean strict) {
 170             return toRealArrayData(index).set(index, value, strict);
 171         }
 172 
 173         @Override
 174         public ArrayData set(final int index, final double value, final boolean strict) {
 175             return toRealArrayData(index).set(index, value, strict);
 176         }
 177 
 178         @Override
 179         public int getInt(final int index) {
 180             throw new ArrayIndexOutOfBoundsException(index); //empty
 181         }
 182 
 183         @Override
 184         public long getLong(final int index) {
 185             throw new ArrayIndexOutOfBoundsException(index); //empty
 186         }
 187 
 188         @Override
 189         public double getDouble(final int index) {
 190             throw new ArrayIndexOutOfBoundsException(index); //empty
 191         }
 192 
 193         @Override
 194         public Object getObject(final int index) {
 195             throw new ArrayIndexOutOfBoundsException(index); //empty
 196         }
 197 
 198         @Override
 199         public boolean has(final int index) {
 200             return false; //empty
 201         }
 202 
 203         @Override
 204         public Object pop() {
 205             return ScriptRuntime.UNDEFINED;
 206         }
 207 
 208         @Override
 209         public ArrayData push(final boolean strict, final Object item) {
 210             return toRealArrayData().push(strict, item);
 211         }
 212 
 213         @Override
 214         public ArrayData slice(final long from, final long to) {
 215             return this; //empty
 216         }
 217 
 218         @Override
 219         public ContinuousArrayData fastConcat(final ContinuousArrayData otherData) {
 220             return otherData.copy();
 221         }
 222 
 223         //no need to override fastPopInt, as the default behavior is to throw classcast exception so we
 224         //can relink and return an undefined, this is the IntArrayData default behavior
 225         @Override
 226         public String toString() {
 227             return getClass().getSimpleName();
 228         }
 229 
 230         @Override
 231         public MethodHandle getElementGetter(final Class<?> returnType, final int programPoint) {
 232             return null;
 233         }
 234 
 235         @Override
 236         public MethodHandle getElementSetter(final Class<?> elementType) {
 237             return null;
 238         }
 239 
 240         @Override
 241         public Class<?> getElementType() {
 242             return int.class;
 243         }
 244 
 245         @Override
 246         public Class<?> getBoxedElementType() {
 247             return Integer.class;
 248         }
 249     };
 250 
 251     /**
 252      * Constructor
 253      * @param length Virtual length of the array.
 254      */
 255     protected ArrayData(final long length) {
 256         this.length = length;
 257     }
 258 
 259     /**
 260      * Factory method for unspecified array - start as int
 261      * @return ArrayData
 262      */
 263     public final static ArrayData initialArray() {
 264         return new IntArrayData();
 265     }
 266 
 267     /**
 268      * Unwarranted thrower
 269      *
 270      * @param data         array data
 271      * @param programPoint program point
 272      * @param index        array index
 273      */
 274     protected static void throwUnwarranted(final ArrayData data, final int programPoint, final int index) {
 275         throw new UnwarrantedOptimismException(data.getObject(index), programPoint);
 276     }
 277 
 278     /**
 279      * Align an array size up to the nearest array chunk size
 280      * @param size size required
 281      * @return size given, always >= size
 282      */
 283     protected final static int alignUp(final int size) {
 284         return size + CHUNK_SIZE - 1 & ~(CHUNK_SIZE - 1);
 285     }
 286 
 287     /**
 288      * Factory method for unspecified array with given length - start as int array data
 289      *
 290      * @param length the initial length
 291      * @return ArrayData
 292      */
 293     public static final ArrayData allocate(final int length) {
 294         if (length == 0) {
 295             return new IntArrayData();
 296         } else if (length >= SparseArrayData.MAX_DENSE_LENGTH) {
 297             return new SparseArrayData(EMPTY_ARRAY, length);
 298         } else {
 299             return new DeletedRangeArrayFilter(new IntArrayData(length), 0, length - 1);
 300         }
 301     }
 302 
 303     /**
 304      * Factory method for unspecified given an array object
 305      *
 306      * @param  array the array
 307      * @return ArrayData wrapping this array
 308      */
 309     public static final ArrayData allocate(final Object array) {
 310         final Class<?> clazz = array.getClass();
 311 
 312         if (clazz == int[].class) {
 313             return new IntArrayData((int[])array, ((int[])array).length);
 314         } else if (clazz == long[].class) {
 315             return new LongArrayData((long[])array, ((long[])array).length);
 316         } else if (clazz == double[].class) {
 317             return new NumberArrayData((double[])array, ((double[])array).length);
 318         } else {
 319             return new ObjectArrayData((Object[])array, ((Object[])array).length);
 320         }
 321     }
 322 
 323     /**
 324      * Allocate an ArrayData wrapping a given array
 325      *
 326      * @param array the array to use for initial elements
 327      * @return the ArrayData
 328      */
 329     public static final ArrayData allocate(final int[] array) {
 330          return new IntArrayData(array, array.length);
 331     }
 332 
 333     /**
 334      * Allocate an ArrayData wrapping a given array
 335      *
 336      * @param array the array to use for initial elements
 337      * @return the ArrayData
 338      */
 339     public static final ArrayData allocate(final long[] array) {
 340         return new LongArrayData(array, array.length);
 341     }
 342 
 343     /**
 344      * Allocate an ArrayData wrapping a given array
 345      *
 346      * @param array the array to use for initial elements
 347      * @return the ArrayData
 348      */
 349     public static final ArrayData allocate(final double[] array) {
 350         return new NumberArrayData(array, array.length);
 351     }
 352 
 353     /**
 354      * Allocate an ArrayData wrapping a given array
 355      *
 356      * @param array the array to use for initial elements
 357      * @return the ArrayData
 358      */
 359     public static final ArrayData allocate(final Object[] array) {
 360         return new ObjectArrayData(array, array.length);
 361     }
 362 
 363     /**
 364      * Allocate an ArrayData wrapping a given nio ByteBuffer
 365      *
 366      * @param buf the nio ByteBuffer to wrap
 367      * @return the ArrayData
 368      */
 369     public static final ArrayData allocate(final ByteBuffer buf) {
 370         return new ByteBufferArrayData(buf);
 371     }
 372 
 373     /**
 374      * Apply a freeze filter to an ArrayData.
 375      *
 376      * @param underlying  the underlying ArrayData to wrap in the freeze filter
 377      * @return the frozen ArrayData
 378      */
 379     public static final ArrayData freeze(final ArrayData underlying) {
 380         return new FrozenArrayFilter(underlying);
 381     }
 382 
 383     /**
 384      * Apply a seal filter to an ArrayData.
 385      *
 386      * @param underlying  the underlying ArrayData to wrap in the seal filter
 387      * @return the sealed ArrayData
 388      */
 389     public static final ArrayData seal(final ArrayData underlying) {
 390         return new SealedArrayFilter(underlying);
 391     }
 392 
 393     /**
 394      * Prevent this array from being extended
 395      *
 396      * @param  underlying the underlying ArrayData to wrap in the non extensible filter
 397      * @return new array data, filtered
 398      */
 399     public static final ArrayData preventExtension(final ArrayData underlying) {
 400         return new NonExtensibleArrayFilter(underlying);
 401     }
 402 
 403     /**
 404      * Prevent this array from having its length reset
 405      *
 406      * @param underlying the underlying ArrayDAta to wrap in the non extensible filter
 407      * @return new array data, filtered
 408      */
 409     public static final ArrayData setIsLengthNotWritable(final ArrayData underlying) {
 410         return new LengthNotWritableFilter(underlying);
 411     }
 412 
 413     /**
 414      * Return the length of the array data. This may differ from the actual
 415      * length of the array this wraps as length may be set or gotten as any
 416      * other JavaScript Property
 417      *
 418      * Even though a JavaScript array length may be a long, we only store
 419      * int parts for the optimized array access. For long lengths there
 420      * are special cases anyway.
 421      *
 422      * TODO: represent arrays with "long" lengths as a special ArrayData
 423      * that basically maps to the ScriptObject directly for better abstraction
 424      *
 425      * @return the length of the data
 426      */
 427     public final long length() {
 428         return length;
 429     }
 430 
 431     /**
 432      * Return a copy of the array that can be modified without affecting this instance.
 433      * It is safe to return themselves for immutable subclasses.
 434      *
 435      * @return a new array
 436      */
 437     public abstract ArrayData copy();
 438 
 439     /**
 440      * Return a copy of the array data as an Object array.
 441      *
 442      * @return an Object array
 443      */
 444     public abstract Object[] asObjectArray();
 445 
 446     /**
 447      * Return a copy of the array data as an array of the specified type.
 448      *
 449      * @param componentType  the type of elements in the array
 450      * @return and array of the given type
 451      */
 452     public Object asArrayOfType(final Class<?> componentType) {
 453         return JSType.convertArray(asObjectArray(), componentType);
 454     }
 455 
 456     /**
 457      * Set the length of the data array
 458      *
 459      * @param length the new length for the data array
 460      */
 461     public void setLength(final long length) {
 462         this.length = length;
 463     }
 464 
 465     /**
 466      * Increase length by 1
 467      * @return the new length, not the old one (i.e. pre-increment)
 468      */
 469     protected final long increaseLength() {
 470         return ++this.length;
 471     }
 472 
 473     /**
 474      * Decrease length by 1.
 475      * @return the new length, not the old one (i.e. pre-decrement)
 476      */
 477     protected final long decreaseLength() {
 478         return --this.length;
 479     }
 480 
 481     /**
 482      * Shift the array data left
 483      *
 484      * TODO: explore start at an index and not at zero, to make these operations
 485      * even faster. Offset everything from the index. Costs memory but is probably
 486      * worth it
 487      *
 488      * @param by offset to shift
 489      */
 490     public abstract void shiftLeft(final int by);
 491 
 492     /**
 493      * Shift the array right
 494      *
 495      * @param by offset to shift
 496 
 497      * @return New arraydata (or same)
 498      */
 499     public abstract ArrayData shiftRight(final int by);
 500 
 501     /**
 502      * Ensure that the given index exists and won't fail subsequent
 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      * Push an array of items to the end of the array
 768      *
 769      * @param strict are we in strict mode
 770      * @param item   the item
 771      * @return new array data (or same)
 772      */
 773     public ArrayData push(final boolean strict, final double item) {
 774         return push(strict, item);
 775     }
 776 
 777     /**
 778      * Push an array of items to the end of the array
 779      *
 780      * @param strict are we in strict mode
 781      * @param item   the item
 782      * @return new array data (or same)
 783      */
 784     public ArrayData push(final boolean strict, final long item) {
 785         return push(strict, item);
 786     }
 787 
 788     /**
 789      * Push an array of items to the end of the array
 790      *
 791      * @param strict are we in strict mode
 792      * @param item   the item
 793      * @return new array data (or same)
 794      */
 795     public ArrayData push(final boolean strict, final int item) {
 796         return push(strict, item);
 797     }
 798 
 799     /**
 800      * Pop an element from the end of the array
 801      *
 802      * @return the popped element
 803      */
 804     public abstract Object pop();
 805 
 806     /**
 807      * Slice out a section of the array and return that
 808      * subsection as a new array data: [from, to)
 809      *
 810      * @param from start index
 811      * @param to   end index + 1
 812      * @return new array data
 813      */
 814     public abstract ArrayData slice(final long from, final long to);
 815 
 816     /**
 817      * Fast splice operation. This just modifies the array according to the number of
 818      * elements added and deleted but does not insert the added elements. Throws
 819      * {@code UnsupportedOperationException} if fast splice operation is not supported
 820      * for this class or arguments.
 821      *
 822      * @param start start index of splice operation
 823      * @param removed number of removed elements
 824      * @param added number of added elements
 825      * @throws UnsupportedOperationException if fast splice is not supported for the class or arguments.
 826      * @return new arraydata, but this never happens because we always throw an exception
 827      */
 828     public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException {
 829         throw new UnsupportedOperationException();
 830     }
 831 
 832     static Class<?> widestType(final Object... items) {
 833         assert items.length > 0;
 834 
 835         Class<?> widest = Integer.class;
 836 
 837         for (final Object item : items) {
 838             if (item == null) {
 839                 return Object.class;
 840             }
 841             final Class<?> itemClass = item.getClass();
 842             if (itemClass == Long.class) {
 843                 if (widest == Integer.class) {
 844                     widest = Long.class;
 845                 }
 846             } else if (itemClass == Double.class || itemClass == Float.class) {
 847                 if (widest == Integer.class || widest == Long.class) {
 848                     widest = Double.class;
 849                 }
 850             } else if (itemClass != Integer.class && itemClass != Short.class && itemClass != Byte.class) {
 851                 return Object.class;
 852             }
 853         }
 854 
 855         return widest;
 856     }
 857 
 858     /**
 859      * Return a list of keys in the array for the iterators
 860      * @return iterator key list
 861      */
 862     protected List<Long> computeIteratorKeys() {
 863         final List<Long> keys = new ArrayList<>();
 864 
 865         final long len = length();
 866         for (long i = 0L; i < len; i = nextIndex(i)) {
 867             if (has((int)i)) {
 868                 keys.add(i);
 869             }
 870         }
 871 
 872         return keys;
 873     }
 874 
 875     /**
 876      * Return an iterator that goes through all indexes of elements
 877      * in this array. This includes those after array.length if
 878      * they exist
 879      *
 880      * @return iterator
 881      */
 882     public Iterator<Long> indexIterator() {
 883         return computeIteratorKeys().iterator();
 884     }
 885 
 886     /**
 887      * Exponential growth function for array size when in
 888      * need of resizing.
 889      *
 890      * @param size current size
 891      * @return next size to allocate for internal array
 892      */
 893     public static int nextSize(final int size) {
 894         return alignUp(size + 1) * 2;
 895     }
 896 
 897     /**
 898      * Return the next valid index from a given one. Subclassed for various
 899      * array representation
 900      *
 901      * @param index the current index
 902      *
 903      * @return the next index
 904      */
 905     long nextIndex(final long index) {
 906         return index + 1;
 907     }
 908 
 909     static Object invoke(final MethodHandle mh, final Object arg) {
 910         try {
 911             return mh.invoke(arg);
 912         } catch (final RuntimeException | Error e) {
 913             throw e;
 914         } catch (final Throwable t) {
 915             throw new RuntimeException(t);
 916         }
 917     }
 918 
 919    /**
 920      * Find a fast call if one exists
 921      *
 922      * @param clazz    array data class
 923      * @param desc     callsite descriptor
 924      * @param request  link request
 925      * @return fast property getter if one is found
 926      */
 927     public GuardedInvocation findFastCallMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) {
 928         return null;
 929     }
 930 
 931     /**
 932      * Find a fast property getter if one exists
 933      *
 934      * @param clazz    array data class
 935      * @param desc     callsite descriptor
 936      * @param request  link request
 937      * @param operator operator
 938      * @return fast property getter if one is found
 939      */
 940     public GuardedInvocation findFastGetMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request, final String operator) {
 941         return null;
 942     }
 943 
 944     /**
 945      * Find a fast element getter if one exists
 946      *
 947      * @param clazz   array data class
 948      * @param desc    callsite descriptor
 949      * @param request link request
 950      * @return fast index getter if one is found
 951      */
 952     public GuardedInvocation findFastGetIndexMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) { // array, index, value
 953         return null;
 954     }
 955 
 956     /**
 957      * Find a fast element setter if one exists
 958      *
 959      * @param clazz   array data class
 960      * @param desc    callsite descriptor
 961      * @param request link request
 962      * @return fast index getter if one is found
 963      */
 964     public GuardedInvocation findFastSetIndexMethod(final Class<? extends ArrayData> clazz, final CallSiteDescriptor desc, final LinkRequest request) { // array, index, value
 965         return null;
 966     }
 967 }