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 java.lang.invoke.MethodHandle;
  29 import java.nio.ByteBuffer;
  30 import jdk.nashorn.internal.objects.Global;
  31 import jdk.nashorn.internal.runtime.JSType;
  32 import jdk.nashorn.internal.runtime.PropertyDescriptor;
  33 
  34 /**
  35  * ArrayData - abstraction for wrapping array elements
  36  */
  37 public abstract class ArrayData {
  38 
  39     /** Minimum chunk size for underlying arrays */
  40     protected static final int CHUNK_SIZE = 16;
  41 
  42     /** Mask for getting a chunk */
  43     protected static final int CHUNK_MASK = CHUNK_SIZE - 1;
  44 
  45     /**
  46      * Immutable empty array to get ScriptObjects started.
  47      */
  48     public static final ArrayData EMPTY_ARRAY = new NoTypeArrayData();
  49 
  50     /**
  51      * Length of the array data. Not necessarily length of the wrapped array.
  52      */
  53     private long length;
  54 
  55     /**
  56      * Constructor
  57      * @param length Virtual length of the array.
  58      */
  59     protected ArrayData(final long length) {
  60         this.length = length;
  61     }
  62 
  63     /**
  64      * Factory method for unspecified array - start as int
  65      * @return ArrayData
  66      */
  67     public static ArrayData initialArray() {
  68         return new IntArrayData();
  69     }
  70 
  71     /**
  72      * Factory method for unspecified array with given length - start as int array data
  73      *
  74      * @param length the initial length
  75      * @return ArrayData
  76      */
  77     public static ArrayData allocate(final int length) {
  78         if (length == 0) {
  79             return new IntArrayData();
  80         } else if (length >= SparseArrayData.MAX_DENSE_LENGTH) {
  81             return new SparseArrayData(EMPTY_ARRAY, length);
  82         } else {
  83             return new DeletedRangeArrayFilter(new IntArrayData(length), 0, length - 1);
  84         }
  85     }
  86 
  87     /**
  88      * Factory method for unspecified given an array object
  89      *
  90      * @param  array the array
  91      * @return ArrayData wrapping this array
  92      */
  93     public static ArrayData allocate(final Object array) {
  94         final Class<?> clazz = array.getClass();
  95 
  96         if (clazz == int[].class) {
  97             return new IntArrayData((int[])array, ((int[])array).length);
  98         } else if (clazz == long[].class) {
  99             return new LongArrayData((long[])array, ((long[])array).length);
 100         } else if (clazz == double[].class) {
 101             return new NumberArrayData((double[])array, ((double[])array).length);
 102         } else {
 103             return new ObjectArrayData((Object[])array, ((Object[])array).length);
 104         }
 105     }
 106 
 107     /**
 108      * Allocate an ArrayData wrapping a given array
 109      *
 110      * @param array the array to use for initial elements
 111      * @return the ArrayData
 112      */
 113     public static ArrayData allocate(final int[] array) {
 114          return new IntArrayData(array, array.length);
 115     }
 116 
 117     /**
 118      * Allocate an ArrayData wrapping a given array
 119      *
 120      * @param array the array to use for initial elements
 121      * @return the ArrayData
 122      */
 123     public static ArrayData allocate(final long[] array) {
 124         return new LongArrayData(array, array.length);
 125     }
 126 
 127     /**
 128      * Allocate an ArrayData wrapping a given array
 129      *
 130      * @param array the array to use for initial elements
 131      * @return the ArrayData
 132      */
 133     public static ArrayData allocate(final double[] array) {
 134         return new NumberArrayData(array, array.length);
 135     }
 136 
 137     /**
 138      * Allocate an ArrayData wrapping a given array
 139      *
 140      * @param array the array to use for initial elements
 141      * @return the ArrayData
 142      */
 143     public static ArrayData allocate(final Object[] array) {
 144         return new ObjectArrayData(array, array.length);
 145     }
 146 
 147     /**
 148      * Allocate an ArrayData wrapping a given nio ByteBuffer
 149      *
 150      * @param buf the nio ByteBuffer to wrap
 151      * @return the ArrayData
 152      */
 153     public static ArrayData allocate(final ByteBuffer buf) {
 154         return new ByteBufferArrayData((ByteBuffer)buf);
 155     }
 156 
 157     /**
 158      * Apply a freeze filter to an ArrayData.
 159      *
 160      * @param underlying  the underlying ArrayData to wrap in the freeze filter
 161      * @return the frozen ArrayData
 162      */
 163     public static ArrayData freeze(final ArrayData underlying) {
 164         return new FrozenArrayFilter(underlying);
 165     }
 166 
 167     /**
 168      * Apply a seal filter to an ArrayData.
 169      *
 170      * @param underlying  the underlying ArrayData to wrap in the seal filter
 171      * @return the sealed ArrayData
 172      */
 173     public static ArrayData seal(final ArrayData underlying) {
 174         return new SealedArrayFilter(underlying);
 175     }
 176 
 177     /**
 178      * Return the length of the array data. This may differ from the actual
 179      * length of the array this wraps as length may be set or gotten as any
 180      * other JavaScript Property
 181      *
 182      * Even though a JavaScript array length may be a long, we only store
 183      * int parts for the optimized array access. For long lengths there
 184      * are special cases anyway.
 185      *
 186      * TODO: represent arrays with "long" lengths as a special ArrayData
 187      * that basically maps to the ScriptObject directly for better abstraction
 188      *
 189      * @return the length of the data
 190      */
 191     public final long length() {
 192         return length;
 193     }
 194 
 195     /**
 196      * Return a copy of the array that can be modified without affecting this instance.
 197      * It is safe to return themselves for immutable subclasses.
 198      *
 199      * @return a new array
 200      */
 201     public abstract ArrayData copy();
 202 
 203     /**
 204      * Return a copy of the array data as an Object array.
 205      *
 206      * @return an Object array
 207      */
 208     public abstract Object[] asObjectArray();
 209 
 210     /**
 211      * Return a copy of the array data as an array of the specified type.
 212      *
 213      * @param componentType  the type of elements in the array
 214      * @return and array of the given type
 215      */
 216     public Object asArrayOfType(final Class<?> componentType) {
 217         return JSType.convertArray(asObjectArray(), componentType);
 218     }
 219 
 220     /**
 221      * Set the length of the data array
 222      *
 223      * @param length the new length for the data array
 224      */
 225     public void setLength(final long length) {
 226         this.length = length;
 227     }
 228 
 229     /**
 230      * Shift the array data left
 231      *
 232      * TODO: explore start at an index and not at zero, to make these operations
 233      * even faster. Offset everything from the index. Costs memory but is probably
 234      * worth it
 235      *
 236      * @param by offset to shift
 237      */
 238     public abstract void shiftLeft(int by);
 239 
 240     /**
 241      * Shift the array right
 242      *
 243      * @param by offset to shift
 244 
 245      * @return New arraydata (or same)
 246      */
 247     public abstract ArrayData shiftRight(int by);
 248 
 249     /**
 250      * Ensure that the given index exists and won't fail subsequent
 251      *
 252      * @param safeIndex the index to ensure wont go out of bounds
 253      * @return new array data (or same)
 254      */
 255     public abstract ArrayData ensure(long safeIndex);
 256 
 257     /**
 258      * Shrink the array to a new length, may or may not retain the
 259      * inner array
 260      *
 261      * @param newLength new max length
 262      *
 263      * @return new array data (or same)
 264      */
 265     public abstract ArrayData shrink(long newLength);
 266 
 267     /**
 268      * Set an object value at a given index
 269      *
 270      * @param index the index
 271      * @param value the value
 272      * @param strict are we in strict mode
 273      * @return new array data (or same)
 274      */
 275     public abstract ArrayData set(int index, Object value, boolean strict);
 276 
 277     /**
 278      * Set an int value at a given index
 279      *
 280      * @param index the index
 281      * @param value the value
 282      * @param strict are we in strict mode
 283      * @return new array data (or same)
 284      */
 285     public abstract ArrayData set(int index, int value, boolean strict);
 286 
 287     /**
 288      * Set a long value at a given index
 289      *
 290      * @param index the index
 291      * @param value the value
 292      * @param strict are we in strict mode
 293      * @return new array data (or same)
 294      */
 295     public abstract ArrayData set(int index, long value, boolean strict);
 296 
 297     /**
 298      * Set an double value at a given index
 299      *
 300      * @param index the index
 301      * @param value the value
 302      * @param strict are we in strict mode
 303      * @return new array data (or same)
 304      */
 305     public abstract ArrayData set(int index, double value, boolean strict);
 306 
 307     /**
 308      * Set an empty value at a given index. Should only affect Object array.
 309      *
 310      * @param index the index
 311      * @return new array data (or same)
 312      */
 313     public ArrayData setEmpty(final int index) {
 314         // Do nothing.
 315         return this;
 316     }
 317 
 318     /**
 319      * Set an empty value for a given range. Should only affect Object array.
 320      *
 321      * @param lo range low end
 322      * @param hi range high end
 323      * @return new array data (or same)
 324      */
 325     public ArrayData setEmpty(final long lo, final long hi) {
 326         // Do nothing.
 327         return this;
 328     }
 329 
 330     /**
 331      * Get an int value from a given index
 332      *
 333      * @param index the index
 334      * @return the value
 335      */
 336     public abstract int getInt(int index);
 337 
 338     /**
 339      * Get a long value from a given index
 340      *
 341      * @param index the index
 342      * @return the value
 343      */
 344     public abstract long getLong(int index);
 345 
 346     /**
 347      * Get a double value from a given index
 348      *
 349      * @param index the index
 350      * @return the value
 351      */
 352     public abstract double getDouble(int index);
 353 
 354     /**
 355      * Get an Object value from a given index
 356      *
 357      * @param index the index
 358      * @return the value
 359      */
 360     public abstract Object getObject(int index);
 361 
 362     /**
 363      * Tests to see if an entry exists (avoids boxing.)
 364      * @param index the index
 365      * @return true if entry exists
 366      */
 367     public abstract boolean has(int index);
 368 
 369     /**
 370      * Returns if element at specific index can be deleted or not.
 371      *
 372      * @param index the index of the element
 373      * @param strict are we in strict mode
 374      *
 375      * @return true if element can be deleted
 376      */
 377     public boolean canDelete(final int index, final boolean strict) {
 378         return true;
 379     }
 380 
 381     /**
 382      * Returns if element at specific index range can be deleted or not.
 383      *
 384      * @param fromIndex  the start index
 385      * @param toIndex    the end index
 386      * @param strict     are we in strict mode
 387      *
 388      * @return true if range can be deleted
 389      */
 390     public boolean canDelete(final long fromIndex, final long toIndex, final boolean strict) {
 391         return true;
 392     }
 393 
 394     /**
 395      * Returns property descriptor for element at a given index
 396      *
 397      * @param global the global object
 398      * @param index  the index
 399      *
 400      * @return property descriptor for element
 401      */
 402     public PropertyDescriptor getDescriptor(final Global global, final int index) {
 403         return global.newDataDescriptor(getObject(index), true, true, true);
 404     }
 405 
 406     /**
 407      * Delete an array value at the given index, substituting
 408      * for an undefined
 409      *
 410      * @param index the index
 411      * @return new array data (or same)
 412      */
 413     public abstract ArrayData delete(int index);
 414 
 415     /**
 416      * Delete a given range from this array;
 417      *
 418      * @param fromIndex  from index (inclusive)
 419      * @param toIndex    to index (inclusive)
 420      *
 421      * @return new ArrayData after deletion
 422      */
 423     public abstract ArrayData delete(long fromIndex, long toIndex);
 424 
 425     /**
 426      * Convert the ArrayData to one with a different element type
 427      * Currently Arrays are not collapsed to narrower types, just to
 428      * wider ones. Attempting to narrow an array will assert
 429      *
 430      * @param type new element type
 431      * @return new array data
 432      */
 433     protected abstract ArrayData convert(Class<?> type);
 434 
 435     /**
 436      * Push an array of items to the end of the array
 437      *
 438      * @param strict are we in strict mode
 439      * @param items  the items
 440      * @return new array data (or same)
 441      */
 442     public ArrayData push(final boolean strict, final Object... items) {
 443         if (items.length == 0) {
 444             return this;
 445         }
 446 
 447         final Class<?>  widest  = widestType(items);
 448 
 449         ArrayData newData = convert(widest);
 450         long      pos     = newData.length();
 451         for (final Object item : items) {
 452             newData = newData.ensure(pos); //avoid sparse array
 453             newData.set((int)pos++, item, strict);
 454         }
 455         return newData;
 456     }
 457 
 458     /**
 459      * Pop an element from the end of the array
 460      *
 461      * @return the popped element
 462      */
 463     public abstract Object pop();
 464 
 465     /**
 466      * Slice out a section of the array and return that
 467      * subsection as a new array data: [from, to)
 468      *
 469      * @param from start index
 470      * @param to   end index + 1
 471      * @return new array data
 472      */
 473     public abstract ArrayData slice(long from, long to);
 474 
 475     /**
 476      * Fast splice operation. This just modifies the array according to the number of
 477      * elements added and deleted but does not insert the added elements. Throws
 478      * {@code UnsupportedOperationException} if fast splice operation is not supported
 479      * for this class or arguments.
 480      *
 481      * @param start start index of splice operation
 482      * @param removed number of removed elements
 483      * @param added number of added elements
 484      * @throws UnsupportedOperationException if fast splice is not supported for the class or arguments.
 485      */
 486     public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException {
 487         throw new UnsupportedOperationException();
 488     }
 489 
 490 
 491     static Class<?> widestType(final Object... items) {
 492         assert items.length > 0;
 493 
 494         Class<?> widest = Integer.class;
 495 
 496         for (final Object item : items) {
 497             final Class<?> itemClass = item == null ? null : item.getClass();
 498             if (itemClass == Long.class) {
 499                 if (widest == Integer.class) {
 500                     widest = Long.class;
 501                 }
 502             } else if (itemClass == Double.class) {
 503                 if (widest == Integer.class || widest == Long.class) {
 504                     widest = Double.class;
 505                 }
 506             } else if (!(item instanceof Number)) {
 507                 widest = Object.class;
 508                 break;
 509             }
 510         }
 511 
 512         return widest;
 513     }
 514 
 515     /**
 516      * Exponential growth function for array size when in
 517      * need of resizing.
 518      *
 519      * @param size current size
 520      * @return next size to allocate for internal array
 521      */
 522     protected static int nextSize(final int size) {
 523         if (size == 0) {
 524             return CHUNK_SIZE;
 525         }
 526 
 527         int i = size;
 528         while ((i & CHUNK_MASK) != 0) {
 529             i++;
 530         }
 531 
 532         return i << 1;
 533     }
 534 
 535     /**
 536      * Return the next valid index from a given one. Subclassed for various
 537      * array representation
 538      *
 539      * @param index the current index
 540      *
 541      * @return the next index
 542      */
 543     public long nextIndex(final long index) {
 544         return index + 1;
 545     }
 546 
 547     static Object invoke(final MethodHandle mh, final Object arg) {
 548         try {
 549             return mh.invoke(arg);
 550         } catch (final RuntimeException | Error e) {
 551             throw e;
 552         } catch (final Throwable t) {
 553             throw new RuntimeException(t);
 554         }
 555     }
 556 }