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 }