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 }