1/*** 2 * ASM: a very small and fast Java bytecode manipulation framework 3 * Copyright (c) 2000-2007 INRIA, France Telecom 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. Neither the name of the copyright holders nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 28 * THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30package org.mockito.asm.tree; 31 32import java.util.ListIterator; 33import java.util.NoSuchElementException; 34 35import org.mockito.asm.MethodVisitor; 36 37/** 38 * A doubly linked list of {@link AbstractInsnNode} objects. <i>This 39 * implementation is not thread safe</i>. 40 */ 41public class InsnList { 42 43 /** 44 * Indicates if preconditions of methods of this class must be checked. 45 * <i>Checking preconditions causes the {@link #indexOf indexOf}, 46 * {@link #set set}, {@link #insert(AbstractInsnNode, AbstractInsnNode)}, 47 * {@link #insert(AbstractInsnNode, InsnList)}, {@link #remove remove} and 48 * {@link #clear} methods to execute in O(n) time instead of O(1)</i>. 49 */ 50 public static boolean check; 51 52 /** 53 * The number of instructions in this list. 54 */ 55 private int size; 56 57 /** 58 * The first instruction in this list. May be <tt>null</tt>. 59 */ 60 private AbstractInsnNode first; 61 62 /** 63 * The last instruction in this list. May be <tt>null</tt>. 64 */ 65 private AbstractInsnNode last; 66 67 /** 68 * A cache of the instructions of this list. This cache is used to improve 69 * the performance of the {@link #get} method. 70 */ 71 private AbstractInsnNode[] cache; 72 73 /** 74 * Returns the number of instructions in this list. 75 * 76 * @return the number of instructions in this list. 77 */ 78 public int size() { 79 return size; 80 } 81 82 /** 83 * Returns the first instruction in this list. 84 * 85 * @return the first instruction in this list, or <tt>null</tt> if the 86 * list is empty. 87 */ 88 public AbstractInsnNode getFirst() { 89 return first; 90 } 91 92 /** 93 * Returns the last instruction in this list. 94 * 95 * @return the last instruction in this list, or <tt>null</tt> if the list 96 * is empty. 97 */ 98 public AbstractInsnNode getLast() { 99 return last; 100 } 101 102 /** 103 * Returns the instruction whose index is given. This method builds a cache 104 * of the instructions in this list to avoid scanning the whole list each 105 * time it is called. Once the cache is built, this method run in constant 106 * time. This cache is invalidated by all the methods that modify the list. 107 * 108 * @param index the index of the instruction that must be returned. 109 * @return the instruction whose index is given. 110 * @throws IndexOutOfBoundsException if (index < 0 || index >= size()). 111 */ 112 public AbstractInsnNode get(final int index) { 113 if (index < 0 || index >= size) { 114 throw new IndexOutOfBoundsException(); 115 } 116 if (cache == null) { 117 cache = toArray(); 118 } 119 return cache[index]; 120 } 121 122 /** 123 * Returns <tt>true</tt> if the given instruction belongs to this list. 124 * This method always scans the instructions of this list until it finds the 125 * given instruction or reaches the end of the list. 126 * 127 * @param insn an instruction. 128 * @return <tt>true</tt> if the given instruction belongs to this list. 129 */ 130 public boolean contains(final AbstractInsnNode insn) { 131 AbstractInsnNode i = first; 132 while (i != null && i != insn) { 133 i = i.next; 134 } 135 return i != null; 136 } 137 138 /** 139 * Returns the index of the given instruction in this list. This method 140 * builds a cache of the instruction indexes to avoid scanning the whole 141 * list each time it is called. Once the cache is built, this method run in 142 * constant time. The cache is invalidated by all the methods that modify 143 * the list. 144 * 145 * @param insn an instruction <i>of this list</i>. 146 * @return the index of the given instruction in this list. <i>The result of 147 * this method is undefined if the given instruction does not belong 148 * to this list</i>. Use {@link #contains contains} to test if an 149 * instruction belongs to an instruction list or not. 150 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt> and 151 * if insn does not belong to this list. 152 */ 153 public int indexOf(final AbstractInsnNode insn) { 154 if (check && !contains(insn)) { 155 throw new IllegalArgumentException(); 156 } 157 if (cache == null) { 158 cache = toArray(); 159 } 160 return insn.index; 161 } 162 163 /** 164 * Makes the given visitor visit all of the instructions in this list. 165 * 166 * @param mv the method visitor that must visit the instructions. 167 */ 168 public void accept(final MethodVisitor mv) { 169 AbstractInsnNode insn = first; 170 while (insn != null) { 171 insn.accept(mv); 172 insn = insn.next; 173 } 174 } 175 176 /** 177 * Returns an iterator over the instructions in this list. 178 * 179 * @return an iterator over the instructions in this list. 180 */ 181 public ListIterator iterator() { 182 return iterator(0); 183 } 184 185 /** 186 * Returns an iterator over the instructions in this list. 187 * 188 * @return an iterator over the instructions in this list. 189 */ 190 public ListIterator iterator(int index) { 191 return new InsnListIterator(index); 192 } 193 194 /** 195 * Returns an array containing all of the instructions in this list. 196 * 197 * @return an array containing all of the instructions in this list. 198 */ 199 public AbstractInsnNode[] toArray() { 200 int i = 0; 201 AbstractInsnNode elem = first; 202 AbstractInsnNode[] insns = new AbstractInsnNode[size]; 203 while (elem != null) { 204 insns[i] = elem; 205 elem.index = i++; 206 elem = elem.next; 207 } 208 return insns; 209 } 210 211 /** 212 * Replaces an instruction of this list with another instruction. 213 * 214 * @param location an instruction <i>of this list</i>. 215 * @param insn another instruction, <i>which must not belong to any 216 * {@link InsnList}</i>. 217 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 218 * and if i does not belong to this list or if insn belongs to an 219 * instruction list. 220 */ 221 public void set(final AbstractInsnNode location, final AbstractInsnNode insn) { 222 if (check && !(contains(location) && insn.index == -1)) { 223 throw new IllegalArgumentException(); 224 } 225 AbstractInsnNode next = location.next; 226 insn.next = next; 227 if (next != null) { 228 next.prev = insn; 229 } else { 230 last = insn; 231 } 232 AbstractInsnNode prev = location.prev; 233 insn.prev = prev; 234 if (prev != null) { 235 prev.next = insn; 236 } else { 237 first = insn; 238 } 239 if (cache != null) { 240 int index = location.index; 241 cache[index] = insn; 242 insn.index = index; 243 } else { 244 insn.index = 0; // insn now belongs to an InsnList 245 } 246 location.index = -1; // i no longer belongs to an InsnList 247 location.prev = null; 248 location.next = null; 249 } 250 251 /** 252 * Adds the given instruction to the end of this list. 253 * 254 * @param insn an instruction, <i>which must not belong to any 255 * {@link InsnList}</i>. 256 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 257 * and if insn belongs to an instruction list. 258 */ 259 public void add(final AbstractInsnNode insn) { 260 if (check && insn.index != -1) { 261 throw new IllegalArgumentException(); 262 } 263 ++size; 264 if (last == null) { 265 first = insn; 266 last = insn; 267 } else { 268 last.next = insn; 269 insn.prev = last; 270 } 271 last = insn; 272 cache = null; 273 insn.index = 0; // insn now belongs to an InsnList 274 } 275 276 /** 277 * Adds the given instructions to the end of this list. 278 * 279 * @param insns an instruction list, which is cleared during the process. 280 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 281 * and if insn == this. 282 */ 283 public void add(final InsnList insns) { 284 if (check && insns == this) { 285 throw new IllegalArgumentException(); 286 } 287 if (insns.size == 0) { 288 return; 289 } 290 size += insns.size; 291 if (last == null) { 292 first = insns.first; 293 last = insns.last; 294 } else { 295 AbstractInsnNode elem = insns.first; 296 last.next = elem; 297 elem.prev = last; 298 last = insns.last; 299 } 300 cache = null; 301 insns.removeAll(false); 302 } 303 304 /** 305 * Inserts the given instruction at the begining of this list. 306 * 307 * @param insn an instruction, <i>which must not belong to any 308 * {@link InsnList}</i>. 309 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 310 * and if insn belongs to an instruction list. 311 */ 312 public void insert(final AbstractInsnNode insn) { 313 if (check && insn.index != -1) { 314 throw new IllegalArgumentException(); 315 } 316 ++size; 317 if (first == null) { 318 first = insn; 319 last = insn; 320 } else { 321 first.prev = insn; 322 insn.next = first; 323 } 324 first = insn; 325 cache = null; 326 insn.index = 0; // insn now belongs to an InsnList 327 } 328 329 /** 330 * Inserts the given instructions at the begining of this list. 331 * 332 * @param insns an instruction list, which is cleared during the process. 333 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 334 * and if insn == this. 335 */ 336 public void insert(final InsnList insns) { 337 if (check && insns == this) { 338 throw new IllegalArgumentException(); 339 } 340 if (insns.size == 0) { 341 return; 342 } 343 size += insns.size; 344 if (first == null) { 345 first = insns.first; 346 last = insns.last; 347 } else { 348 AbstractInsnNode elem = insns.last; 349 first.prev = elem; 350 elem.next = first; 351 first = insns.first; 352 } 353 cache = null; 354 insns.removeAll(false); 355 } 356 357 /** 358 * Inserts the given instruction after the specified instruction. 359 * 360 * @param location an instruction <i>of this list</i> after which insn must be 361 * inserted. 362 * @param insn the instruction to be inserted, <i>which must not belong to 363 * any {@link InsnList}</i>. 364 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 365 * and if i does not belong to this list or if insn belongs to an 366 * instruction list. 367 */ 368 public void insert(final AbstractInsnNode location, final AbstractInsnNode insn) { 369 if (check && !(contains(location) && insn.index == -1)) { 370 throw new IllegalArgumentException(); 371 } 372 ++size; 373 AbstractInsnNode next = location.next; 374 if (next == null) { 375 last = insn; 376 } else { 377 next.prev = insn; 378 } 379 location.next = insn; 380 insn.next = next; 381 insn.prev = location; 382 cache = null; 383 insn.index = 0; // insn now belongs to an InsnList 384 } 385 386 /** 387 * Inserts the given instructions after the specified instruction. 388 * 389 * @param location an instruction <i>of this list</i> after which the instructions 390 * must be inserted. 391 * @param insns the instruction list to be inserted, which is cleared during 392 * the process. 393 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 394 * and if i does not belong to this list or if insns == this. 395 */ 396 public void insert(final AbstractInsnNode location, final InsnList insns) { 397 if (check && !(contains(location) && insns != this)) { 398 throw new IllegalArgumentException(); 399 } 400 if (insns.size == 0) { 401 return; 402 } 403 size += insns.size; 404 AbstractInsnNode ifirst = insns.first; 405 AbstractInsnNode ilast = insns.last; 406 AbstractInsnNode next = location.next; 407 if (next == null) { 408 last = ilast; 409 } else { 410 next.prev = ilast; 411 } 412 location.next = ifirst; 413 ilast.next = next; 414 ifirst.prev = location; 415 cache = null; 416 insns.removeAll(false); 417 } 418 419 /** 420 * Inserts the given instruction before the specified instruction. 421 * 422 * @param location an instruction <i>of this list</i> before which insn must be 423 * inserted. 424 * @param insn the instruction to be inserted, <i>which must not belong to 425 * any {@link InsnList}</i>. 426 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 427 * and if i does not belong to this list or if insn belongs to an 428 * instruction list. 429 */ 430 public void insertBefore(final AbstractInsnNode location, final AbstractInsnNode insn) { 431 if (check && !(contains(location) && insn.index == -1)) { 432 throw new IllegalArgumentException(); 433 } 434 ++size; 435 AbstractInsnNode prev = location.prev; 436 if (prev == null) { 437 first = insn; 438 } else { 439 prev.next = insn; 440 } 441 location.prev = insn; 442 insn.next = location; 443 insn.prev = prev; 444 cache = null; 445 insn.index = 0; // insn now belongs to an InsnList 446 } 447 448 /** 449 * Inserts the given instructions before the specified instruction. 450 * 451 * @param location an instruction <i>of this list</i> before which the instructions 452 * must be inserted. 453 * @param insns the instruction list to be inserted, which is cleared during 454 * the process. 455 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 456 * and if i does not belong to this list or if insns == this. 457 */ 458 public void insertBefore(final AbstractInsnNode location, final InsnList insns) { 459 if (check && !(contains(location ) && insns != this)) { 460 throw new IllegalArgumentException(); 461 } 462 if (insns.size == 0) { 463 return; 464 } 465 size += insns.size; 466 AbstractInsnNode ifirst = insns.first; 467 AbstractInsnNode ilast = insns.last; 468 AbstractInsnNode prev = location .prev; 469 if (prev == null) { 470 first = ifirst; 471 } else { 472 prev.next = ifirst; 473 } 474 location .prev = ilast; 475 ilast.next = location ; 476 ifirst.prev = prev; 477 cache = null; 478 insns.removeAll(false); 479 } 480 481 482 483 /** 484 * Removes the given instruction from this list. 485 * 486 * @param insn the instruction <i>of this list</i> that must be removed. 487 * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>, 488 * and if insn does not belong to this list. 489 */ 490 public void remove(final AbstractInsnNode insn) { 491 if (check && !contains(insn)) { 492 throw new IllegalArgumentException(); 493 } 494 --size; 495 AbstractInsnNode next = insn.next; 496 AbstractInsnNode prev = insn.prev; 497 if (next == null) { 498 if (prev == null) { 499 first = null; 500 last = null; 501 } else { 502 prev.next = null; 503 last = prev; 504 } 505 } else { 506 if (prev == null) { 507 first = next; 508 next.prev = null; 509 } else { 510 prev.next = next; 511 next.prev = prev; 512 } 513 } 514 cache = null; 515 insn.index = -1; // insn no longer belongs to an InsnList 516 insn.prev = null; 517 insn.next = null; 518 } 519 520 /** 521 * Removes all of the instructions of this list. 522 * 523 * @param mark if the instructions must be marked as no longer belonging to 524 * any {@link InsnList}. 525 */ 526 private void removeAll(final boolean mark) { 527 if (mark) { 528 AbstractInsnNode insn = first; 529 while (insn != null) { 530 AbstractInsnNode next = insn.next; 531 insn.index = -1; // insn no longer belongs to an InsnList 532 insn.prev = null; 533 insn.next = null; 534 insn = next; 535 } 536 } 537 size = 0; 538 first = null; 539 last = null; 540 cache = null; 541 } 542 543 /** 544 * Removes all of the instructions of this list. 545 */ 546 public void clear() { 547 removeAll(check); 548 } 549 550 /** 551 * Reset all labels in the instruction list. This method should be called 552 * before reusing same instructions list between several 553 * <code>ClassWriter</code>s. 554 */ 555 public void resetLabels() { 556 AbstractInsnNode insn = first; 557 while (insn != null) { 558 if (insn instanceof LabelNode) { 559 ((LabelNode) insn).resetLabel(); 560 } 561 insn = insn.next; 562 } 563 } 564 565 private final class InsnListIterator implements ListIterator { 566 AbstractInsnNode next; 567 AbstractInsnNode prev; 568 569 private InsnListIterator(int index) { 570 if(index==size()) { 571 next = null; 572 prev = getLast(); 573 } else { 574 next = get(index); 575 prev = next.prev; 576 } 577 } 578 579 public boolean hasNext() { 580 return next != null; 581 } 582 583 public Object next() { 584 if (next == null) { 585 throw new NoSuchElementException(); 586 } 587 AbstractInsnNode result = next; 588 prev = result; 589 next = result.next; 590 return result; 591 } 592 593 public void remove() { 594 InsnList.this.remove(prev); 595 prev = prev.prev; 596 } 597 598 public boolean hasPrevious() { 599 return prev != null; 600 } 601 602 public Object previous() { 603 AbstractInsnNode result = prev; 604 next = result; 605 prev = result.prev; 606 return result; 607 } 608 609 public int nextIndex() { 610 if (next == null) { 611 return size(); 612 } 613 if (cache == null) { 614 cache = toArray(); 615 } 616 return next.index; 617 } 618 619 public int previousIndex() { 620 if (prev == null) { 621 return -1; 622 } 623 if (cache == null) { 624 cache = toArray(); 625 } 626 return prev.index; 627 } 628 629 public void add(Object o) { 630 InsnList.this.insertBefore(next, (AbstractInsnNode) o); 631 prev = (AbstractInsnNode) o; 632 } 633 634 public void set(Object o) { 635 InsnList.this.set(next.prev, (AbstractInsnNode) o); 636 prev = (AbstractInsnNode) o; 637 } 638 } 639 640} 641