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