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