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