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;
27
28 import java.util.AbstractList;
29 import java.util.Deque;
30 import java.util.Iterator;
31 import java.util.ListIterator;
32 import java.util.NoSuchElementException;
33 import java.util.RandomAccess;
34 import java.util.concurrent.Callable;
35 import jdk.nashorn.api.scripting.JSObject;
36 import jdk.nashorn.api.scripting.ScriptObjectMirror;
37 import jdk.nashorn.internal.objects.Global;
38 import jdk.nashorn.internal.runtime.linker.Bootstrap;
39 import jdk.nashorn.internal.runtime.linker.InvokeByName;
40
41 /**
42 * An adapter that can wrap any ECMAScript Array-like object (that adheres to the array rules for the property
43 * {@code length} and having conforming {@code push}, {@code pop}, {@code shift}, {@code unshift}, and {@code splice}
44 * methods) and expose it as both a Java list and double-ended queue. While script arrays aren't necessarily efficient
45 * as dequeues, it's still slightly more efficient to be able to translate dequeue operations into pushes, pops, shifts,
46 * and unshifts, than to blindly translate all list's add/remove operations into splices. Also, it is conceivable that a
47 * custom script object that implements an Array-like API can have a background data representation that is optimized
48 * for dequeue-like access. Note that with ECMAScript arrays, {@code push} and {@code pop} operate at the end of the
49 * array, while in Java {@code Deque} they operate on the front of the queue and as such the Java dequeue
50 * {@link #push(Object)} and {@link #pop()} operations will translate to {@code unshift} and {@code shift} script
51 * operations respectively, while {@link #addLast(Object)} and {@link #removeLast()} will translate to {@code push} and
52 * {@code pop}.
53 */
54 public abstract class ListAdapter extends AbstractList<Object> implements RandomAccess, Deque<Object> {
55 // These add to the back and front of the list
56 private static final Object PUSH = new Object();
57 private static InvokeByName getPUSH() {
58 return Context.getGlobal().getInvokeByName(PUSH,
59 new Callable<InvokeByName>() {
60 @Override
61 public InvokeByName call() {
62 return new InvokeByName("push", Object.class, void.class, Object.class);
63 }
64 });
65 }
66
67 private static final Object UNSHIFT = new Object();
68 private static InvokeByName getUNSHIFT() {
69 return Context.getGlobal().getInvokeByName(UNSHIFT,
70 new Callable<InvokeByName>() {
71 @Override
72 public InvokeByName call() {
73 return new InvokeByName("unshift", Object.class, void.class, Object.class);
74 }
75 });
76 }
77
78 // These remove from the back and front of the list
79 private static final Object POP = new Object();
80 private static InvokeByName getPOP() {
81 return Context.getGlobal().getInvokeByName(POP,
82 new Callable<InvokeByName>() {
83 @Override
84 public InvokeByName call() {
85 return new InvokeByName("pop", Object.class, Object.class);
86 }
87 });
88 }
89
90 private static final Object SHIFT = new Object();
91 private static InvokeByName getSHIFT() {
92 return Context.getGlobal().getInvokeByName(SHIFT,
93 new Callable<InvokeByName>() {
94 @Override
95 public InvokeByName call() {
96 return new InvokeByName("shift", Object.class, Object.class);
97 }
98 });
99 }
100
101 // These insert and remove in the middle of the list
102 private static final Object SPLICE_ADD = new Object();
103 private static InvokeByName getSPLICE_ADD() {
104 return Context.getGlobal().getInvokeByName(SPLICE_ADD,
105 new Callable<InvokeByName>() {
106 @Override
107 public InvokeByName call() {
108 return new InvokeByName("splice", Object.class, void.class, int.class, int.class, Object.class);
109 }
110 });
111 }
112
113 private static final Object SPLICE_REMOVE = new Object();
114 private static InvokeByName getSPLICE_REMOVE() {
115 return Context.getGlobal().getInvokeByName(SPLICE_REMOVE,
116 new Callable<InvokeByName>() {
117 @Override
118 public InvokeByName call() {
119 return new InvokeByName("splice", Object.class, void.class, int.class, int.class);
120 }
121 });
122 }
123
124 /** wrapped object */
125 protected final Object obj;
126
127 // allow subclasses only in this package
128 ListAdapter(final Object obj) {
129 this.obj = obj;
130 }
131
132 /**
133 * Factory to create a ListAdapter for a given script object.
134 *
135 * @param obj script object to wrap as a ListAdapter
136 * @return A ListAdapter wrapper object
137 */
138 public static ListAdapter create(final Object obj) {
139 if (obj instanceof ScriptObject) {
140 final Object mirror = ScriptObjectMirror.wrap(obj, Context.getGlobal());
141 return new JSObjectListAdapter((JSObject)mirror);
142 } else if (obj instanceof JSObject) {
143 return new JSObjectListAdapter((JSObject)obj);
144 } else {
145 throw new IllegalArgumentException("ScriptObject or JSObject expected");
146 }
147 }
148
149 @Override
150 public final Object get(final int index) {
151 checkRange(index);
152 return getAt(index);
153 }
154
155 /**
156 * Get object at an index
157 * @param index index in list
158 * @return object
159 */
160 protected abstract Object getAt(final int index);
161
162 @Override
163 public Object set(final int index, final Object element) {
164 checkRange(index);
165 final Object prevValue = getAt(index);
166 setAt(index, element);
167 return prevValue;
168 }
169
170 /**
171 * Set object at an index
172 * @param index index in list
173 * @param element element
174 */
175 protected abstract void setAt(final int index, final Object element);
176
177 private void checkRange(int index) {
178 if(index < 0 || index >= size()) {
179 throw invalidIndex(index);
180 }
181 }
182
183 @Override
184 public final void push(final Object e) {
185 addFirst(e);
186 }
187
188 @Override
189 public final boolean add(final Object e) {
190 addLast(e);
191 return true;
192 }
193
194 @Override
195 public final void addFirst(final Object e) {
196 try {
197 final InvokeByName unshiftInvoker = getUNSHIFT();
198 final Object fn = unshiftInvoker.getGetter().invokeExact(obj);
199 checkFunction(fn, unshiftInvoker);
200 unshiftInvoker.getInvoker().invokeExact(fn, obj, e);
201 } catch(RuntimeException | Error ex) {
202 throw ex;
203 } catch(Throwable t) {
204 throw new RuntimeException(t);
205 }
206 }
207
208 @Override
209 public final void addLast(final Object e) {
210 try {
211 final InvokeByName pushInvoker = getPUSH();
212 final Object fn = pushInvoker.getGetter().invokeExact(obj);
213 checkFunction(fn, pushInvoker);
214 pushInvoker.getInvoker().invokeExact(fn, obj, e);
215 } catch(RuntimeException | Error ex) {
216 throw ex;
217 } catch(Throwable t) {
218 throw new RuntimeException(t);
219 }
220 }
221
222 @Override
223 public final void add(final int index, final Object e) {
224 try {
225 if(index < 0) {
226 throw invalidIndex(index);
227 } else if(index == 0) {
228 addFirst(e);
229 } else {
230 final int size = size();
231 if(index < size) {
232 final InvokeByName spliceAddInvoker = getSPLICE_ADD();
233 final Object fn = spliceAddInvoker.getGetter().invokeExact(obj);
234 checkFunction(fn, spliceAddInvoker);
235 spliceAddInvoker.getInvoker().invokeExact(fn, obj, index, 0, e);
236 } else if(index == size) {
237 addLast(e);
238 } else {
239 throw invalidIndex(index);
240 }
241 }
242 } catch(final RuntimeException | Error ex) {
243 throw ex;
244 } catch(final Throwable t) {
245 throw new RuntimeException(t);
246 }
247 }
248 private static void checkFunction(final Object fn, final InvokeByName invoke) {
249 if(!(Bootstrap.isCallable(fn))) {
250 throw new UnsupportedOperationException("The script object doesn't have a function named " + invoke.getName());
251 }
252 }
253
254 private static IndexOutOfBoundsException invalidIndex(final int index) {
255 return new IndexOutOfBoundsException(String.valueOf(index));
256 }
257
258 @Override
259 public final boolean offer(final Object e) {
260 return offerLast(e);
261 }
262
263 @Override
264 public final boolean offerFirst(final Object e) {
265 addFirst(e);
266 return true;
267 }
268
269 @Override
270 public final boolean offerLast(final Object e) {
271 addLast(e);
272 return true;
273 }
274
275 @Override
276 public final Object pop() {
277 return removeFirst();
278 }
279
280 @Override
281 public final Object remove() {
282 return removeFirst();
283 }
284
285 @Override
286 public final Object removeFirst() {
287 checkNonEmpty();
288 return invokeShift();
289 }
290
291 @Override
292 public final Object removeLast() {
293 checkNonEmpty();
294 return invokePop();
295 }
296
297 private void checkNonEmpty() {
298 if(isEmpty()) {
299 throw new NoSuchElementException();
300 }
301 }
302
303 @Override
304 public final Object remove(final int index) {
305 if(index < 0) {
306 throw invalidIndex(index);
307 } else if (index == 0) {
308 return invokeShift();
309 } else {
310 final int maxIndex = size() - 1;
311 if(index < maxIndex) {
312 final Object prevValue = get(index);
313 invokeSpliceRemove(index, 1);
314 return prevValue;
315 } else if(index == maxIndex) {
316 return invokePop();
317 } else {
318 throw invalidIndex(index);
319 }
320 }
321 }
322
323 private Object invokeShift() {
324 try {
325 final InvokeByName shiftInvoker = getSHIFT();
326 final Object fn = shiftInvoker.getGetter().invokeExact(obj);
327 checkFunction(fn, shiftInvoker);
328 return shiftInvoker.getInvoker().invokeExact(fn, obj);
329 } catch(RuntimeException | Error ex) {
330 throw ex;
331 } catch(Throwable t) {
332 throw new RuntimeException(t);
333 }
334 }
335
336 private Object invokePop() {
337 try {
338 final InvokeByName popInvoker = getPOP();
339 final Object fn = popInvoker.getGetter().invokeExact(obj);
340 checkFunction(fn, popInvoker);
341 return popInvoker.getInvoker().invokeExact(fn, obj);
342 } catch(RuntimeException | Error ex) {
343 throw ex;
344 } catch(Throwable t) {
345 throw new RuntimeException(t);
346 }
347 }
348
349 @Override
350 protected final void removeRange(final int fromIndex, final int toIndex) {
351 invokeSpliceRemove(fromIndex, toIndex - fromIndex);
352 }
353
354 private void invokeSpliceRemove(final int fromIndex, final int count) {
355 try {
356 final InvokeByName spliceRemoveInvoker = getSPLICE_REMOVE();
357 final Object fn = spliceRemoveInvoker.getGetter().invokeExact(obj);
358 checkFunction(fn, spliceRemoveInvoker);
359 spliceRemoveInvoker.getInvoker().invokeExact(fn, obj, fromIndex, count);
360 } catch(RuntimeException | Error ex) {
361 throw ex;
362 } catch(Throwable t) {
363 throw new RuntimeException(t);
364 }
365 }
366
367 @Override
368 public final Object poll() {
369 return pollFirst();
370 }
371
372 @Override
373 public final Object pollFirst() {
374 return isEmpty() ? null : invokeShift();
375 }
376
377 @Override
378 public final Object pollLast() {
379 return isEmpty() ? null : invokePop();
380 }
381
382 @Override
383 public final Object peek() {
384 return peekFirst();
385 }
386
387 @Override
388 public final Object peekFirst() {
389 return isEmpty() ? null : get(0);
390 }
391
392 @Override
393 public final Object peekLast() {
394 return isEmpty() ? null : get(size() - 1);
395 }
396
397 @Override
398 public final Object element() {
399 return getFirst();
400 }
401
402 @Override
403 public final Object getFirst() {
404 checkNonEmpty();
405 return get(0);
406 }
407
408 @Override
409 public final Object getLast() {
410 checkNonEmpty();
411 return get(size() - 1);
412 }
413
414 @Override
415 public final Iterator<Object> descendingIterator() {
416 final ListIterator<Object> it = listIterator(size());
417 return new Iterator<Object>() {
418 @Override
419 public boolean hasNext() {
420 return it.hasPrevious();
421 }
422
423 @Override
424 public Object next() {
425 return it.previous();
426 }
427
428 @Override
429 public void remove() {
430 it.remove();
431 }
432 };
433 }
434
435 @Override
436 public final boolean removeFirstOccurrence(final Object o) {
437 return removeOccurrence(o, iterator());
438 }
439
440 @Override
441 public final boolean removeLastOccurrence(final Object o) {
442 return removeOccurrence(o, descendingIterator());
443 }
444
445 private static boolean removeOccurrence(final Object o, final Iterator<Object> it) {
446 while(it.hasNext()) {
447 final Object e = it.next();
448 if(o == null ? e == null : o.equals(e)) {
449 it.remove();
450 return true;
451 }
452 }
453 return false;
454 }
455 }