ListAdapter.java revision 1290:cdec24430159
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 final 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 private final JSObject obj; 82 private final Global global; 83 84 // allow subclasses only in this package 85 ListAdapter(final JSObject obj) { 86 this.obj = obj; 87 this.global = getGlobalNonNull(); 88 } 89 90 private static Global getGlobalNonNull() { 91 final Global global = Context.getGlobal(); 92 if (global != null) { 93 return global; 94 } 95 throw new IllegalStateException(ECMAErrors.getMessage("list.adapter.null.global")); 96 } 97 98 /** 99 * Factory to create a ListAdapter for a given script object. 100 * 101 * @param obj script object to wrap as a ListAdapter 102 * @return A ListAdapter wrapper object 103 */ 104 public static ListAdapter create(final Object obj) { 105 return new ListAdapter(getJSObject(obj)); 106 } 107 108 private static JSObject getJSObject(final Object obj) { 109 if (obj instanceof ScriptObject) { 110 return (JSObject)ScriptObjectMirror.wrap(obj, Context.getGlobal()); 111 } else if (obj instanceof JSObject) { 112 return (JSObject)obj; 113 } 114 throw new IllegalArgumentException("ScriptObject or JSObject expected"); 115 } 116 117 @Override 118 public final Object get(final int index) { 119 checkRange(index); 120 return getAt(index); 121 } 122 123 private Object getAt(final int index) { 124 return obj.getSlot(index); 125 } 126 127 @Override 128 public Object set(final int index, final Object element) { 129 checkRange(index); 130 final Object prevValue = getAt(index); 131 obj.setSlot(index, element); 132 return prevValue; 133 } 134 135 private void checkRange(final int index) { 136 if(index < 0 || index >= size()) { 137 throw invalidIndex(index); 138 } 139 } 140 141 @Override 142 public int size() { 143 return JSType.toInt32(obj.getMember("length")); 144 } 145 146 @Override 147 public final void push(final Object e) { 148 addFirst(e); 149 } 150 151 @Override 152 public final boolean add(final Object e) { 153 addLast(e); 154 return true; 155 } 156 157 @Override 158 public final void addFirst(final Object e) { 159 try { 160 getDynamicInvoker(UNSHIFT, ADD_INVOKER_CREATOR).invokeExact(getFunction("unshift"), obj, e); 161 } catch(RuntimeException | Error ex) { 162 throw ex; 163 } catch(final Throwable t) { 164 throw new RuntimeException(t); 165 } 166 } 167 168 @Override 169 public final void addLast(final Object e) { 170 try { 171 getDynamicInvoker(PUSH, ADD_INVOKER_CREATOR).invokeExact(getFunction("push"), obj, e); 172 } catch(RuntimeException | Error ex) { 173 throw ex; 174 } catch(final Throwable t) { 175 throw new RuntimeException(t); 176 } 177 } 178 179 @Override 180 public final void add(final int index, final Object e) { 181 try { 182 if(index < 0) { 183 throw invalidIndex(index); 184 } else if(index == 0) { 185 addFirst(e); 186 } else { 187 final int size = size(); 188 if(index < size) { 189 getDynamicInvoker(SPLICE_ADD, SPLICE_ADD_INVOKER_CREATOR).invokeExact(obj.getMember("splice"), obj, index, 0, e); 190 } else if(index == size) { 191 addLast(e); 192 } else { 193 throw invalidIndex(index); 194 } 195 } 196 } catch(final RuntimeException | Error ex) { 197 throw ex; 198 } catch(final Throwable t) { 199 throw new RuntimeException(t); 200 } 201 } 202 private Object getFunction(final String name) { 203 final Object fn = obj.getMember(name); 204 if(!(Bootstrap.isCallable(fn))) { 205 throw new UnsupportedOperationException("The script object doesn't have a function named " + name); 206 } 207 return fn; 208 } 209 210 private static IndexOutOfBoundsException invalidIndex(final int index) { 211 return new IndexOutOfBoundsException(String.valueOf(index)); 212 } 213 214 @Override 215 public final boolean offer(final Object e) { 216 return offerLast(e); 217 } 218 219 @Override 220 public final boolean offerFirst(final Object e) { 221 addFirst(e); 222 return true; 223 } 224 225 @Override 226 public final boolean offerLast(final Object e) { 227 addLast(e); 228 return true; 229 } 230 231 @Override 232 public final Object pop() { 233 return removeFirst(); 234 } 235 236 @Override 237 public final Object remove() { 238 return removeFirst(); 239 } 240 241 @Override 242 public final Object removeFirst() { 243 checkNonEmpty(); 244 return invokeShift(); 245 } 246 247 @Override 248 public final Object removeLast() { 249 checkNonEmpty(); 250 return invokePop(); 251 } 252 253 private void checkNonEmpty() { 254 if(isEmpty()) { 255 throw new NoSuchElementException(); 256 } 257 } 258 259 @Override 260 public final Object remove(final int index) { 261 if(index < 0) { 262 throw invalidIndex(index); 263 } else if (index == 0) { 264 return invokeShift(); 265 } else { 266 final int maxIndex = size() - 1; 267 if(index < maxIndex) { 268 final Object prevValue = get(index); 269 invokeSpliceRemove(index, 1); 270 return prevValue; 271 } else if(index == maxIndex) { 272 return invokePop(); 273 } else { 274 throw invalidIndex(index); 275 } 276 } 277 } 278 279 private Object invokeShift() { 280 try { 281 return getDynamicInvoker(SHIFT, REMOVE_INVOKER_CREATOR).invokeExact(getFunction("shift"), obj); 282 } catch(RuntimeException | Error ex) { 283 throw ex; 284 } catch(final Throwable t) { 285 throw new RuntimeException(t); 286 } 287 } 288 289 private Object invokePop() { 290 try { 291 return getDynamicInvoker(POP, REMOVE_INVOKER_CREATOR).invokeExact(getFunction("pop"), obj); 292 } catch(RuntimeException | Error ex) { 293 throw ex; 294 } catch(final Throwable t) { 295 throw new RuntimeException(t); 296 } 297 } 298 299 @Override 300 protected final void removeRange(final int fromIndex, final int toIndex) { 301 invokeSpliceRemove(fromIndex, toIndex - fromIndex); 302 } 303 304 private void invokeSpliceRemove(final int fromIndex, final int count) { 305 try { 306 getDynamicInvoker(SPLICE_REMOVE, SPLICE_REMOVE_INVOKER_CREATOR).invokeExact(getFunction("splice"), obj, fromIndex, count); 307 } catch(RuntimeException | Error ex) { 308 throw ex; 309 } catch(final Throwable t) { 310 throw new RuntimeException(t); 311 } 312 } 313 314 @Override 315 public final Object poll() { 316 return pollFirst(); 317 } 318 319 @Override 320 public final Object pollFirst() { 321 return isEmpty() ? null : invokeShift(); 322 } 323 324 @Override 325 public final Object pollLast() { 326 return isEmpty() ? null : invokePop(); 327 } 328 329 @Override 330 public final Object peek() { 331 return peekFirst(); 332 } 333 334 @Override 335 public final Object peekFirst() { 336 return isEmpty() ? null : get(0); 337 } 338 339 @Override 340 public final Object peekLast() { 341 return isEmpty() ? null : get(size() - 1); 342 } 343 344 @Override 345 public final Object element() { 346 return getFirst(); 347 } 348 349 @Override 350 public final Object getFirst() { 351 checkNonEmpty(); 352 return get(0); 353 } 354 355 @Override 356 public final Object getLast() { 357 checkNonEmpty(); 358 return get(size() - 1); 359 } 360 361 @Override 362 public final Iterator<Object> descendingIterator() { 363 final ListIterator<Object> it = listIterator(size()); 364 return new Iterator<Object>() { 365 @Override 366 public boolean hasNext() { 367 return it.hasPrevious(); 368 } 369 370 @Override 371 public Object next() { 372 return it.previous(); 373 } 374 375 @Override 376 public void remove() { 377 it.remove(); 378 } 379 }; 380 } 381 382 @Override 383 public final boolean removeFirstOccurrence(final Object o) { 384 return removeOccurrence(o, iterator()); 385 } 386 387 @Override 388 public final boolean removeLastOccurrence(final Object o) { 389 return removeOccurrence(o, descendingIterator()); 390 } 391 392 private static boolean removeOccurrence(final Object o, final Iterator<Object> it) { 393 while(it.hasNext()) { 394 if(Objects.equals(o, it.next())) { 395 it.remove(); 396 return true; 397 } 398 } 399 return false; 400 } 401 402 private static Callable<MethodHandle> invokerCreator(final Class<?> rtype, final Class<?>... ptypes) { 403 return new Callable<MethodHandle>() { 404 @Override 405 public MethodHandle call() { 406 return Bootstrap.createDynamicInvoker("dyn:call", rtype, ptypes); 407 } 408 }; 409 } 410 411 private MethodHandle getDynamicInvoker(final Object key, final Callable<MethodHandle> creator) { 412 return global.getDynamicInvoker(key, creator); 413 } 414} 415