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 }
--- EOF ---