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