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