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
26package jdk.nashorn.internal.runtime;
27
28import java.lang.invoke.MethodHandle;
29import java.util.AbstractList;
30import java.util.Deque;
31import java.util.Iterator;
32import java.util.ListIterator;
33import java.util.NoSuchElementException;
34import java.util.Objects;
35import java.util.RandomAccess;
36import java.util.concurrent.Callable;
37import jdk.nashorn.api.scripting.JSObject;
38import jdk.nashorn.api.scripting.ScriptObjectMirror;
39import jdk.nashorn.internal.objects.Global;
40import 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 */
55public 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}
412