001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.bcel.generic; 018 019import java.io.ByteArrayOutputStream; 020import java.io.DataOutputStream; 021import java.io.IOException; 022import java.util.ArrayList; 023import java.util.Arrays; 024import java.util.HashMap; 025import java.util.Iterator; 026import java.util.List; 027import java.util.Map; 028import java.util.NoSuchElementException; 029 030import org.apache.bcel.Const; 031import org.apache.bcel.classfile.Constant; 032import org.apache.bcel.util.ByteSequence; 033import org.apache.commons.lang3.ArrayUtils; 034 035/** 036 * This class is a container for a list of <a href="Instruction.html">Instruction</a> objects. Instructions can be 037 * appended, inserted, moved, deleted, etc.. Instructions are being wrapped into 038 * <a href="InstructionHandle.html">InstructionHandles</a> objects that are returned upon append/insert operations. They 039 * give the user (read only) access to the list structure, such that it can be traversed and manipulated in a controlled 040 * way. 041 * 042 * A list is finally dumped to a byte code array with <a href="#getByteCode()">getByteCode</a>. 043 * 044 * @see Instruction 045 * @see InstructionHandle 046 * @see BranchHandle 047 */ 048public class InstructionList implements Iterable<InstructionHandle> { 049 050 /** 051 * Find the target instruction (handle) that corresponds to the given target position (byte code offset). 052 * 053 * @param ihs array of instruction handles, i.e. il.getInstructionHandles() 054 * @param pos array of positions corresponding to ihs, i.e. il.getInstructionPositions() 055 * @param count length of arrays 056 * @param target target position to search for 057 * @return target position's instruction handle if available 058 */ 059 public static InstructionHandle findHandle(final InstructionHandle[] ihs, final int[] pos, final int count, final int target) { 060 int l = 0; 061 int r = count - 1; 062 /* 063 * Do a binary search since the pos array is orderd. 064 */ 065 do { 066 final int i = l + r >>> 1; 067 final int j = pos[i]; 068 if (j == target) { 069 return ihs[i]; 070 } 071 if (target < j) { 072 r = i - 1; 073 } else { 074 l = i + 1; 075 } 076 } while (l <= r); 077 return null; 078 } 079 080 private InstructionHandle start; 081 private InstructionHandle end; 082 private int length; // number of elements in list 083 084 private int[] bytePositions; // byte code offsets corresponding to instructions 085 086 private List<InstructionListObserver> observers; 087 088 /** 089 * Create (empty) instruction list. 090 */ 091 public InstructionList() { 092 } 093 094 /** 095 * Create instruction list containing one instruction. 096 * 097 * @param i initial instruction 098 */ 099 public InstructionList(final BranchInstruction i) { 100 append(i); 101 } 102 103 /** 104 * Initialize instruction list from byte array. 105 * 106 * @param code byte array containing the instructions 107 */ 108 public InstructionList(final byte[] code) { 109 int count = 0; // Contains actual length 110 int[] pos; 111 InstructionHandle[] ihs; 112 try (ByteSequence bytes = new ByteSequence(code)) { 113 ihs = new InstructionHandle[code.length]; 114 pos = new int[code.length]; // Can't be more than that 115 /* 116 * Pass 1: Create an object for each byte code and append them to the list. 117 */ 118 while (bytes.available() > 0) { 119 // Remember byte offset and associate it with the instruction 120 final int off = bytes.getIndex(); 121 pos[count] = off; 122 /* 123 * Read one instruction from the byte stream, the byte position is set accordingly. 124 */ 125 final Instruction i = Instruction.readInstruction(bytes); 126 InstructionHandle ih; 127 if (i instanceof BranchInstruction) { 128 ih = append((BranchInstruction) i); 129 } else { 130 ih = append(i); 131 } 132 ih.setPosition(off); 133 ihs[count] = ih; 134 count++; 135 } 136 } catch (final IOException e) { 137 throw new ClassGenException(e.toString(), e); 138 } 139 bytePositions = Arrays.copyOf(pos, count); // Trim to proper size 140 /* 141 * Pass 2: Look for BranchInstruction and update their targets, i.e., convert offsets to instruction handles. 142 */ 143 for (int i = 0; i < count; i++) { 144 if (ihs[i] instanceof BranchHandle) { 145 final BranchInstruction bi = (BranchInstruction) ihs[i].getInstruction(); 146 int target = bi.getPosition() + bi.getIndex(); /* 147 * Byte code position: relative -> absolute. 148 */ 149 // Search for target position 150 InstructionHandle ih = findHandle(ihs, pos, count, target); 151 if (ih == null) { 152 throw new ClassGenException("Couldn't find target for branch: " + bi); 153 } 154 bi.setTarget(ih); // Update target 155 // If it is a Select instruction, update all branch targets 156 if (bi instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH 157 final Select s = (Select) bi; 158 final int[] indices = s.getIndices(); 159 for (int j = 0; j < indices.length; j++) { 160 target = bi.getPosition() + indices[j]; 161 ih = findHandle(ihs, pos, count, target); 162 if (ih == null) { 163 throw new ClassGenException("Couldn't find target for switch: " + bi); 164 } 165 s.setTarget(j, ih); // Update target 166 } 167 } 168 } 169 } 170 } 171 172 /** 173 * Initialize list with (nonnull) compound instruction. Consumes argument list, i.e., it becomes empty. 174 * 175 * @param c compound instruction (list) 176 */ 177 public InstructionList(final CompoundInstruction c) { 178 append(c.getInstructionList()); 179 } 180 181 /** 182 * Create instruction list containing one instruction. 183 * 184 * @param i initial instruction 185 */ 186 public InstructionList(final Instruction i) { 187 append(i); 188 } 189 190 /** 191 * Add observer for this object. 192 */ 193 public void addObserver(final InstructionListObserver o) { 194 if (observers == null) { 195 observers = new ArrayList<>(); 196 } 197 observers.add(o); 198 } 199 200 /** 201 * Append a branch instruction to the end of this list. 202 * 203 * @param i branch instruction to append 204 * @return branch instruction handle of the appended instruction 205 */ 206 public BranchHandle append(final BranchInstruction i) { 207 final BranchHandle ih = BranchHandle.getBranchHandle(i); 208 append(ih); 209 return ih; 210 } 211 212 /** 213 * Append a compound instruction. 214 * 215 * @param c The composite instruction (containing an InstructionList) 216 * @return instruction handle of the first appended instruction 217 */ 218 public InstructionHandle append(final CompoundInstruction c) { 219 return append(c.getInstructionList()); 220 } 221 222 /** 223 * Append an instruction to the end of this list. 224 * 225 * @param i instruction to append 226 * @return instruction handle of the appended instruction 227 */ 228 public InstructionHandle append(final Instruction i) { 229 final InstructionHandle ih = InstructionHandle.getInstructionHandle(i); 230 append(ih); 231 return ih; 232 } 233 234 /** 235 * Append a compound instruction, after instruction i. 236 * 237 * @param i Instruction in list 238 * @param c The composite instruction (containing an InstructionList) 239 * @return instruction handle of the first appended instruction 240 */ 241 public InstructionHandle append(final Instruction i, final CompoundInstruction c) { 242 return append(i, c.getInstructionList()); 243 } 244 245 /** 246 * Append a single instruction j after another instruction i, which must be in this list of course! 247 * 248 * @param i Instruction in list 249 * @param j Instruction to append after i in list 250 * @return instruction handle of the first appended instruction 251 */ 252 public InstructionHandle append(final Instruction i, final Instruction j) { 253 return append(i, new InstructionList(j)); 254 } 255 256 /** 257 * Append another list after instruction i contained in this list. Consumes argument list, i.e., it becomes empty. 258 * 259 * @param i where to append the instruction list 260 * @param il Instruction list to append to this one 261 * @return instruction handle pointing to the <B>first</B> appended instruction 262 */ 263 public InstructionHandle append(final Instruction i, final InstructionList il) { 264 InstructionHandle ih; 265 if ((ih = findInstruction2(i)) == null) { 266 throw new ClassGenException("Instruction " + i + " is not contained in this list."); 267 } 268 return append(ih, il); 269 } 270 271 /** 272 * Append an instruction to the end of this list. 273 * 274 * @param ih instruction to append 275 */ 276 private void append(final InstructionHandle ih) { 277 if (isEmpty()) { 278 start = end = ih; 279 ih.setNext(ih.setPrev(null)); 280 } else { 281 end.setNext(ih); 282 ih.setPrev(end); 283 ih.setNext(null); 284 end = ih; 285 } 286 length++; // Update length 287 } 288 289 /** 290 * Append an instruction after instruction (handle) ih contained in this list. 291 * 292 * @param ih where to append the instruction list 293 * @param i Instruction to append 294 * @return instruction handle pointing to the <B>first</B> appended instruction 295 */ 296 public BranchHandle append(final InstructionHandle ih, final BranchInstruction i) { 297 final BranchHandle bh = BranchHandle.getBranchHandle(i); 298 final InstructionList il = new InstructionList(); 299 il.append(bh); 300 append(ih, il); 301 return bh; 302 } 303 304 /** 305 * Append a compound instruction. 306 * 307 * @param ih where to append the instruction list 308 * @param c The composite instruction (containing an InstructionList) 309 * @return instruction handle of the first appended instruction 310 */ 311 public InstructionHandle append(final InstructionHandle ih, final CompoundInstruction c) { 312 return append(ih, c.getInstructionList()); 313 } 314 315 /** 316 * Append an instruction after instruction (handle) ih contained in this list. 317 * 318 * @param ih where to append the instruction list 319 * @param i Instruction to append 320 * @return instruction handle pointing to the <B>first</B> appended instruction 321 */ 322 public InstructionHandle append(final InstructionHandle ih, final Instruction i) { 323 return append(ih, new InstructionList(i)); 324 } 325 326 /** 327 * Append another list after instruction (handle) ih contained in this list. Consumes argument list, i.e., it becomes 328 * empty. 329 * 330 * @param ih where to append the instruction list 331 * @param il Instruction list to append to this one 332 * @return instruction handle pointing to the <B>first</B> appended instruction 333 */ 334 public InstructionHandle append(final InstructionHandle ih, final InstructionList il) { 335 if (il == null) { 336 throw new ClassGenException("Appending null InstructionList"); 337 } 338 if (il.isEmpty()) { 339 return ih; 340 } 341 final InstructionHandle next = ih.getNext(); 342 final InstructionHandle ret = il.start; 343 ih.setNext(il.start); 344 il.start.setPrev(ih); 345 il.end.setNext(next); 346 if (next != null) { 347 next.setPrev(il.end); 348 } else { 349 end = il.end; // Update end ... 350 } 351 length += il.length; // Update length 352 il.clear(); 353 return ret; 354 } 355 356 /** 357 * Append another list to this one. Consumes argument list, i.e., it becomes empty. 358 * 359 * @param il list to append to end of this list 360 * @return instruction handle of the <B>first</B> appended instruction 361 */ 362 public InstructionHandle append(final InstructionList il) { 363 if (il == null) { 364 throw new ClassGenException("Appending null InstructionList"); 365 } 366 if (il.isEmpty()) { 367 return null; 368 } 369 if (isEmpty()) { 370 start = il.start; 371 end = il.end; 372 length = il.length; 373 il.clear(); 374 return start; 375 } 376 return append(end, il); // was end.instruction 377 } 378 379 private void clear() { 380 start = end = null; 381 length = 0; 382 } 383 384 public boolean contains(final Instruction i) { 385 return findInstruction1(i) != null; 386 } 387 388 public boolean contains(final InstructionHandle i) { 389 if (i == null) { 390 return false; 391 } 392 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 393 if (ih == i) { 394 return true; 395 } 396 } 397 return false; 398 } 399 400 /** 401 * @return complete, i.e., deep copy of this list 402 */ 403 public InstructionList copy() { 404 final Map<InstructionHandle, InstructionHandle> map = new HashMap<>(); 405 final InstructionList il = new InstructionList(); 406 /* 407 * Pass 1: Make copies of all instructions, append them to the new list and associate old instruction references with 408 * the new ones, i.e., a 1:1 mapping. 409 */ 410 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 411 final Instruction i = ih.getInstruction(); 412 final Instruction c = i.copy(); // Use clone for shallow copy 413 if (c instanceof BranchInstruction) { 414 map.put(ih, il.append((BranchInstruction) c)); 415 } else { 416 map.put(ih, il.append(c)); 417 } 418 } 419 /* 420 * Pass 2: Update branch targets. 421 */ 422 InstructionHandle ih = start; 423 InstructionHandle ch = il.start; 424 while (ih != null) { 425 final Instruction i = ih.getInstruction(); 426 final Instruction c = ch.getInstruction(); 427 if (i instanceof BranchInstruction) { 428 final BranchInstruction bi = (BranchInstruction) i; 429 final BranchInstruction bc = (BranchInstruction) c; 430 final InstructionHandle itarget = bi.getTarget(); // old target 431 // New target is in hash map 432 bc.setTarget(map.get(itarget)); 433 if (bi instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH 434 final InstructionHandle[] itargets = ((Select) bi).getTargets(); 435 final InstructionHandle[] ctargets = ((Select) bc).getTargets(); 436 for (int j = 0; j < itargets.length; j++) { // Update all targets 437 ctargets[j] = map.get(itargets[j]); 438 } 439 } 440 } 441 ih = ih.getNext(); 442 ch = ch.getNext(); 443 } 444 return il; 445 } 446 447 /** 448 * Remove instruction from this list. The corresponding Instruction handles must not be reused! 449 * 450 * @param i instruction to remove 451 */ 452 public void delete(final Instruction i) throws TargetLostException { 453 InstructionHandle ih; 454 if ((ih = findInstruction1(i)) == null) { 455 throw new ClassGenException("Instruction " + i + " is not contained in this list."); 456 } 457 delete(ih); 458 } 459 460 /** 461 * Remove instructions from instruction `from' to instruction `to' contained in this list. The user must ensure that 462 * `from' is an instruction before `to', or risk havoc. The corresponding Instruction handles must not be reused! 463 * 464 * @param from where to start deleting (inclusive) 465 * @param to where to end deleting (inclusive) 466 */ 467 public void delete(final Instruction from, final Instruction to) throws TargetLostException { 468 InstructionHandle fromIh; 469 InstructionHandle toIh; 470 if ((fromIh = findInstruction1(from)) == null) { 471 throw new ClassGenException("Instruction " + from + " is not contained in this list."); 472 } 473 if ((toIh = findInstruction2(to)) == null) { 474 throw new ClassGenException("Instruction " + to + " is not contained in this list."); 475 } 476 delete(fromIh, toIh); 477 } 478 479 /** 480 * Remove instruction from this list. The corresponding Instruction handles must not be reused! 481 * 482 * @param ih instruction (handle) to remove 483 */ 484 public void delete(final InstructionHandle ih) throws TargetLostException { 485 remove(ih.getPrev(), ih.getNext()); 486 } 487 488 /** 489 * Remove instructions from instruction `from' to instruction `to' contained in this list. The user must ensure that 490 * `from' is an instruction before `to', or risk havoc. The corresponding Instruction handles must not be reused! 491 * 492 * @param from where to start deleting (inclusive) 493 * @param to where to end deleting (inclusive) 494 */ 495 public void delete(final InstructionHandle from, final InstructionHandle to) throws TargetLostException { 496 remove(from.getPrev(), to.getNext()); 497 } 498 499 /** 500 * Delete contents of list. Provides better memory utilization, because the system then may reuse the instruction 501 * handles. This method is typically called right after {@link MethodGen#getMethod()}. 502 */ 503 public void dispose() { 504 // Traverse in reverse order, because ih.next is overwritten 505 for (InstructionHandle ih = end; ih != null; ih = ih.getPrev()) { 506 /* 507 * Causes BranchInstructions to release target and targeters, because it calls dispose() on the contained instruction. 508 */ 509 ih.dispose(); 510 } 511 clear(); 512 } 513 514 /** 515 * Get instruction handle for instruction at byte code position pos. This only works properly, if the list is freshly 516 * initialized from a byte array or setPositions() has been called before this method. 517 * 518 * @param pos byte code position to search for 519 * @return target position's instruction handle if available 520 */ 521 public InstructionHandle findHandle(final int pos) { 522 final int[] positions = bytePositions; 523 InstructionHandle ih = start; 524 for (int i = 0; i < length; i++) { 525 if (positions[i] == pos) { 526 return ih; 527 } 528 ih = ih.getNext(); 529 } 530 return null; 531 } 532 533 /** 534 * Search for given Instruction reference, start at beginning of list. 535 * 536 * @param i instruction to search for 537 * @return instruction found on success, null otherwise 538 */ 539 private InstructionHandle findInstruction1(final Instruction i) { 540 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 541 if (ih.getInstruction() == i) { 542 return ih; 543 } 544 } 545 return null; 546 } 547 548 /** 549 * Search for given Instruction reference, start at end of list 550 * 551 * @param i instruction to search for 552 * @return instruction found on success, null otherwise 553 */ 554 private InstructionHandle findInstruction2(final Instruction i) { 555 for (InstructionHandle ih = end; ih != null; ih = ih.getPrev()) { 556 if (ih.getInstruction() == i) { 557 return ih; 558 } 559 } 560 return null; 561 } 562 563 /** 564 * When everything is finished, use this method to convert the instruction list into an array of bytes. 565 * 566 * @return the byte code ready to be dumped 567 */ 568 public byte[] getByteCode() { 569 // Update position indices of instructions 570 setPositions(); 571 final ByteArrayOutputStream b = new ByteArrayOutputStream(); 572 final DataOutputStream out = new DataOutputStream(b); 573 try { 574 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 575 final Instruction i = ih.getInstruction(); 576 i.dump(out); // Traverse list 577 } 578 out.flush(); 579 } catch (final IOException e) { 580 System.err.println(e); 581 return ArrayUtils.EMPTY_BYTE_ARRAY; 582 } 583 return b.toByteArray(); 584 } 585 586 /** 587 * @return end of list 588 */ 589 public InstructionHandle getEnd() { 590 return end; 591 } 592 593 /** 594 * @return array containing all instructions (handles) 595 */ 596 public InstructionHandle[] getInstructionHandles() { 597 final InstructionHandle[] ihs = new InstructionHandle[length]; 598 InstructionHandle ih = start; 599 for (int i = 0; i < length; i++) { 600 ihs[i] = ih; 601 ih = ih.getNext(); 602 } 603 return ihs; 604 } 605 606 /** 607 * Get positions (offsets) of all instructions in the list. This relies on that the list has been freshly created from 608 * an byte code array, or that setPositions() has been called. Otherwise this may be inaccurate. 609 * 610 * @return array containing all instruction's offset in byte code 611 */ 612 public int[] getInstructionPositions() { 613 return bytePositions; 614 } 615 616 /** 617 * @return an array of instructions without target information for branch instructions. 618 */ 619 public Instruction[] getInstructions() { 620 final List<Instruction> instructions = new ArrayList<>(); 621 try (ByteSequence bytes = new ByteSequence(getByteCode())) { 622 while (bytes.available() > 0) { 623 instructions.add(Instruction.readInstruction(bytes)); 624 } 625 } catch (final IOException e) { 626 throw new ClassGenException(e.toString(), e); 627 } 628 return instructions.toArray(Instruction.EMPTY_ARRAY); 629 } 630 631 /** 632 * @return length of list (Number of instructions, not bytes) 633 */ 634 public int getLength() { 635 return length; 636 } 637 638 /** 639 * @return start of list 640 */ 641 public InstructionHandle getStart() { 642 return start; 643 } 644 645 /** 646 * Insert a branch instruction at start of this list. 647 * 648 * @param i branch instruction to insert 649 * @return branch instruction handle of the appended instruction 650 */ 651 public BranchHandle insert(final BranchInstruction i) { 652 final BranchHandle ih = BranchHandle.getBranchHandle(i); 653 insert(ih); 654 return ih; 655 } 656 657 /** 658 * Insert a compound instruction. 659 * 660 * @param c The composite instruction (containing an InstructionList) 661 * @return instruction handle of the first inserted instruction 662 */ 663 public InstructionHandle insert(final CompoundInstruction c) { 664 return insert(c.getInstructionList()); 665 } 666 667 /** 668 * Insert an instruction at start of this list. 669 * 670 * @param i instruction to insert 671 * @return instruction handle of the inserted instruction 672 */ 673 public InstructionHandle insert(final Instruction i) { 674 final InstructionHandle ih = InstructionHandle.getInstructionHandle(i); 675 insert(ih); 676 return ih; 677 } 678 679 /** 680 * Insert a compound instruction before instruction i. 681 * 682 * @param i Instruction in list 683 * @param c The composite instruction (containing an InstructionList) 684 * @return instruction handle of the first inserted instruction 685 */ 686 public InstructionHandle insert(final Instruction i, final CompoundInstruction c) { 687 return insert(i, c.getInstructionList()); 688 } 689 690 /** 691 * Insert a single instruction j before another instruction i, which must be in this list of course! 692 * 693 * @param i Instruction in list 694 * @param j Instruction to insert before i in list 695 * @return instruction handle of the first inserted instruction 696 */ 697 public InstructionHandle insert(final Instruction i, final Instruction j) { 698 return insert(i, new InstructionList(j)); 699 } 700 701 /** 702 * Insert another list before Instruction i contained in this list. Consumes argument list, i.e., it becomes empty. 703 * 704 * @param i where to append the instruction list 705 * @param il Instruction list to insert 706 * @return instruction handle pointing to the first inserted instruction, i.e., il.getStart() 707 */ 708 public InstructionHandle insert(final Instruction i, final InstructionList il) { 709 InstructionHandle ih; 710 if ((ih = findInstruction1(i)) == null) { 711 throw new ClassGenException("Instruction " + i + " is not contained in this list."); 712 } 713 return insert(ih, il); 714 } 715 716 /** 717 * Insert an instruction at start of this list. 718 * 719 * @param ih instruction to insert 720 */ 721 private void insert(final InstructionHandle ih) { 722 if (isEmpty()) { 723 start = end = ih; 724 ih.setNext(ih.setPrev(null)); 725 } else { 726 start.setPrev(ih); 727 ih.setNext(start); 728 ih.setPrev(null); 729 start = ih; 730 } 731 length++; 732 } 733 734 /** 735 * Insert an instruction before instruction (handle) ih contained in this list. 736 * 737 * @param ih where to insert to the instruction list 738 * @param i Instruction to insert 739 * @return instruction handle of the first inserted instruction 740 */ 741 public BranchHandle insert(final InstructionHandle ih, final BranchInstruction i) { 742 final BranchHandle bh = BranchHandle.getBranchHandle(i); 743 final InstructionList il = new InstructionList(); 744 il.append(bh); 745 insert(ih, il); 746 return bh; 747 } 748 749 /** 750 * Insert a compound instruction. 751 * 752 * @param ih where to insert the instruction list 753 * @param c The composite instruction (containing an InstructionList) 754 * @return instruction handle of the first inserted instruction 755 */ 756 public InstructionHandle insert(final InstructionHandle ih, final CompoundInstruction c) { 757 return insert(ih, c.getInstructionList()); 758 } 759 760 /** 761 * Insert an instruction before instruction (handle) ih contained in this list. 762 * 763 * @param ih where to insert to the instruction list 764 * @param i Instruction to insert 765 * @return instruction handle of the first inserted instruction 766 */ 767 public InstructionHandle insert(final InstructionHandle ih, final Instruction i) { 768 return insert(ih, new InstructionList(i)); 769 } 770 771 /** 772 * Insert another list before Instruction handle ih contained in this list. Consumes argument list, i.e., it becomes 773 * empty. 774 * 775 * @param ih where to append the instruction list 776 * @param il Instruction list to insert 777 * @return instruction handle of the first inserted instruction 778 */ 779 public InstructionHandle insert(final InstructionHandle ih, final InstructionList il) { 780 if (il == null) { 781 throw new ClassGenException("Inserting null InstructionList"); 782 } 783 if (il.isEmpty()) { 784 return ih; 785 } 786 final InstructionHandle prev = ih.getPrev(); 787 final InstructionHandle ret = il.start; 788 ih.setPrev(il.end); 789 il.end.setNext(ih); 790 il.start.setPrev(prev); 791 if (prev != null) { 792 prev.setNext(il.start); 793 } else { 794 start = il.start; // Update start ... 795 } 796 length += il.length; // Update length 797 il.clear(); 798 return ret; 799 } 800 801 /** 802 * Insert another list. 803 * 804 * @param il list to insert before start of this list 805 * @return instruction handle of the first inserted instruction 806 */ 807 public InstructionHandle insert(final InstructionList il) { 808 if (isEmpty()) { 809 append(il); // Code is identical for this case 810 return start; 811 } 812 return insert(start, il); 813 } 814 815 /** 816 * Test for empty list. 817 */ 818 public boolean isEmpty() { 819 return start == null; 820 } // && end == null 821 822 /** 823 * @return iterator that lists all instructions (handles) 824 */ 825 @Override 826 public Iterator<InstructionHandle> iterator() { 827 return new Iterator<InstructionHandle>() { 828 829 private InstructionHandle ih = start; 830 831 @Override 832 public boolean hasNext() { 833 return ih != null; 834 } 835 836 @Override 837 public InstructionHandle next() throws NoSuchElementException { 838 if (ih == null) { 839 throw new NoSuchElementException(); 840 } 841 final InstructionHandle i = ih; 842 ih = ih.getNext(); 843 return i; 844 } 845 846 @Override 847 public void remove() { 848 throw new UnsupportedOperationException(); 849 } 850 }; 851 } 852 853 /** 854 * Move a single instruction (handle) to a new location. 855 * 856 * @param ih moved instruction 857 * @param target new location of moved instruction 858 */ 859 public void move(final InstructionHandle ih, final InstructionHandle target) { 860 move(ih, ih, target); 861 } 862 863 /** 864 * Take all instructions (handles) from "start" to "end" and append them after the new location "target". Of course, 865 * "end" must be after "start" and target must not be located withing this range. If you want to move something to the 866 * start of the list use null as value for target. 867 * <p> 868 * Any instruction targeters pointing to handles within the block, keep their targets. 869 * </p> 870 * 871 * @param start of moved block 872 * @param end of moved block 873 * @param target of moved block 874 */ 875 public void move(final InstructionHandle start, final InstructionHandle end, final InstructionHandle target) { 876 // Step 1: Check constraints 877 if (start == null || end == null) { 878 throw new ClassGenException("Invalid null handle: From " + start + " to " + end); 879 } 880 if (target == start || target == end) { 881 throw new ClassGenException("Invalid range: From " + start + " to " + end + " contains target " + target); 882 } 883 for (InstructionHandle ih = start; ih != end.getNext(); ih = ih.getNext()) { 884 if (ih == null) { 885 throw new ClassGenException("Invalid range: From " + start + " to " + end); 886 } 887 if (ih == target) { 888 throw new ClassGenException("Invalid range: From " + start + " to " + end + " contains target " + target); 889 } 890 } 891 // Step 2: Temporarily remove the given instructions from the list 892 final InstructionHandle prev = start.getPrev(); 893 InstructionHandle next = end.getNext(); 894 if (prev != null) { 895 prev.setNext(next); 896 } else { 897 this.start = next; 898 } 899 if (next != null) { 900 next.setPrev(prev); 901 } else { 902 this.end = prev; 903 } 904 start.setPrev(end.setNext(null)); 905 // Step 3: append after target 906 if (target == null) { // append to start of list 907 if (this.start != null) { 908 this.start.setPrev(end); 909 } 910 end.setNext(this.start); 911 this.start = start; 912 } else { 913 next = target.getNext(); 914 target.setNext(start); 915 start.setPrev(target); 916 end.setNext(next); 917 if (next != null) { 918 next.setPrev(end); 919 } else { 920 this.end = end; 921 } 922 } 923 } 924 925 /** 926 * Redirect all references from oldTarget to newTarget, i.e., update targets of branch instructions. 927 * 928 * @param oldTarget the old target instruction handle 929 * @param newTarget the new target instruction handle 930 */ 931 public void redirectBranches(final InstructionHandle oldTarget, final InstructionHandle newTarget) { 932 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 933 final Instruction i = ih.getInstruction(); 934 if (i instanceof BranchInstruction) { 935 final BranchInstruction b = (BranchInstruction) i; 936 final InstructionHandle target = b.getTarget(); 937 if (target == oldTarget) { 938 b.setTarget(newTarget); 939 } 940 if (b instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH 941 final InstructionHandle[] targets = ((Select) b).getTargets(); 942 for (int j = 0; j < targets.length; j++) { 943 if (targets[j] == oldTarget) { 944 ((Select) b).setTarget(j, newTarget); 945 } 946 } 947 } 948 } 949 } 950 } 951 952 /** 953 * Redirect all references of exception handlers from oldTarget to newTarget. 954 * 955 * @param exceptions array of exception handlers 956 * @param oldTarget the old target instruction handle 957 * @param newTarget the new target instruction handle 958 * @see MethodGen 959 */ 960 public void redirectExceptionHandlers(final CodeExceptionGen[] exceptions, final InstructionHandle oldTarget, final InstructionHandle newTarget) { 961 for (final CodeExceptionGen exception : exceptions) { 962 if (exception.getStartPC() == oldTarget) { 963 exception.setStartPC(newTarget); 964 } 965 if (exception.getEndPC() == oldTarget) { 966 exception.setEndPC(newTarget); 967 } 968 if (exception.getHandlerPC() == oldTarget) { 969 exception.setHandlerPC(newTarget); 970 } 971 } 972 } 973 974 /** 975 * Redirect all references of local variables from oldTarget to newTarget. 976 * 977 * @param lg array of local variables 978 * @param oldTarget the old target instruction handle 979 * @param newTarget the new target instruction handle 980 * @see MethodGen 981 */ 982 public void redirectLocalVariables(final LocalVariableGen[] lg, final InstructionHandle oldTarget, final InstructionHandle newTarget) { 983 for (final LocalVariableGen element : lg) { 984 final InstructionHandle start = element.getStart(); 985 final InstructionHandle end = element.getEnd(); 986 if (start == oldTarget) { 987 element.setStart(newTarget); 988 } 989 if (end == oldTarget) { 990 element.setEnd(newTarget); 991 } 992 } 993 } 994 995 /** 996 * Remove from instruction `prev' to instruction `next' both contained in this list. Throws TargetLostException when one 997 * of the removed instruction handles is still being targeted. 998 * 999 * @param prev where to start deleting (predecessor, exclusive) 1000 * @param next where to end deleting (successor, exclusive) 1001 */ 1002 private void remove(final InstructionHandle prev, InstructionHandle next) throws TargetLostException { 1003 InstructionHandle first; 1004 InstructionHandle last; // First and last deleted instruction 1005 if (prev == null && next == null) { 1006 first = start; 1007 last = end; 1008 start = end = null; 1009 } else { 1010 if (prev == null) { // At start of list 1011 first = start; 1012 start = next; 1013 } else { 1014 first = prev.getNext(); 1015 prev.setNext(next); 1016 } 1017 if (next == null) { // At end of list 1018 last = end; 1019 end = prev; 1020 } else { 1021 last = next.getPrev(); 1022 next.setPrev(prev); 1023 } 1024 } 1025 first.setPrev(null); // Completely separated from rest of list 1026 last.setNext(null); 1027 final List<InstructionHandle> targetVec = new ArrayList<>(); 1028 for (InstructionHandle ih = first; ih != null; ih = ih.getNext()) { 1029 ih.getInstruction().dispose(); // e.g. BranchInstructions release their targets 1030 } 1031 final StringBuilder buf = new StringBuilder("{ "); 1032 for (InstructionHandle ih = first; ih != null; ih = next) { 1033 next = ih.getNext(); 1034 length--; 1035 if (ih.hasTargeters()) { // Still got targeters? 1036 targetVec.add(ih); 1037 buf.append(ih.toString(true)).append(" "); 1038 ih.setNext(ih.setPrev(null)); 1039 } else { 1040 ih.dispose(); 1041 } 1042 } 1043 buf.append("}"); 1044 if (!targetVec.isEmpty()) { 1045 throw new TargetLostException(targetVec.toArray(InstructionHandle.EMPTY_ARRAY), buf.toString()); 1046 } 1047 } 1048 1049 /** 1050 * Remove observer for this object. 1051 */ 1052 public void removeObserver(final InstructionListObserver o) { 1053 if (observers != null) { 1054 observers.remove(o); 1055 } 1056 } 1057 1058 /** 1059 * Replace all references to the old constant pool with references to the new constant pool 1060 */ 1061 public void replaceConstantPool(final ConstantPoolGen oldCp, final ConstantPoolGen newCp) { 1062 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 1063 final Instruction i = ih.getInstruction(); 1064 if (i instanceof CPInstruction) { 1065 final CPInstruction ci = (CPInstruction) i; 1066 final Constant c = oldCp.getConstant(ci.getIndex()); 1067 ci.setIndex(newCp.addConstant(c, oldCp)); 1068 } 1069 } 1070 } 1071 1072 public void setPositions() { // TODO could be package-protected? (some test code would need to be repackaged) 1073 setPositions(false); 1074 } 1075 1076 /** 1077 * Give all instructions their position number (offset in byte stream), i.e., make the list ready to be dumped. 1078 * 1079 * @param check Perform sanity checks, e.g. if all targeted instructions really belong to this list 1080 */ 1081 public void setPositions(final boolean check) { // called by code in other packages 1082 int maxAdditionalBytes = 0; 1083 int additionalBytes = 0; 1084 int index = 0; 1085 int count = 0; 1086 final int[] pos = new int[length]; 1087 /* 1088 * Pass 0: Sanity checks 1089 */ 1090 if (check) { 1091 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 1092 final Instruction i = ih.getInstruction(); 1093 if (i instanceof BranchInstruction) { // target instruction within list? 1094 Instruction inst = ((BranchInstruction) i).getTarget().getInstruction(); 1095 if (!contains(inst)) { 1096 throw new ClassGenException("Branch target of " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not in instruction list"); 1097 } 1098 if (i instanceof Select) { 1099 final InstructionHandle[] targets = ((Select) i).getTargets(); 1100 for (final InstructionHandle target : targets) { 1101 inst = target.getInstruction(); 1102 if (!contains(inst)) { 1103 throw new ClassGenException("Branch target of " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not in instruction list"); 1104 } 1105 } 1106 } 1107 if (!(ih instanceof BranchHandle)) { 1108 throw new ClassGenException( 1109 "Branch instruction " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not contained in BranchHandle."); 1110 } 1111 } 1112 } 1113 } 1114 /* 1115 * Pass 1: Set position numbers and sum up the maximum number of bytes an instruction may be shifted. 1116 */ 1117 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 1118 final Instruction i = ih.getInstruction(); 1119 ih.setPosition(index); 1120 pos[count++] = index; 1121 /* 1122 * Get an estimate about how many additional bytes may be added, because BranchInstructions may have variable length 1123 * depending on the target offset (short vs. int) or alignment issues (TABLESWITCH and LOOKUPSWITCH). 1124 */ 1125 switch (i.getOpcode()) { 1126 case Const.JSR: 1127 case Const.GOTO: 1128 maxAdditionalBytes += 2; 1129 break; 1130 case Const.TABLESWITCH: 1131 case Const.LOOKUPSWITCH: 1132 maxAdditionalBytes += 3; 1133 break; 1134 } 1135 index += i.getLength(); 1136 } 1137 /* 1138 * Pass 2: Expand the variable-length (Branch)Instructions depending on the target offset (short or int) and ensure that 1139 * branch targets are within this list. 1140 */ 1141 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 1142 additionalBytes += ih.updatePosition(additionalBytes, maxAdditionalBytes); 1143 } 1144 /* 1145 * Pass 3: Update position numbers (which may have changed due to the preceding expansions), like pass 1. 1146 */ 1147 index = count = 0; 1148 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 1149 final Instruction i = ih.getInstruction(); 1150 ih.setPosition(index); 1151 pos[count++] = index; 1152 index += i.getLength(); 1153 } 1154 bytePositions = new int[count]; // Trim to proper size 1155 System.arraycopy(pos, 0, bytePositions, 0, count); 1156 } 1157 1158 /** 1159 * @return length of list (Number of instructions, not bytes) 1160 */ 1161 public int size() { 1162 return length; 1163 } 1164 1165 @Override 1166 public String toString() { 1167 return toString(true); 1168 } 1169 1170 /** 1171 * @param verbose toggle output format 1172 * @return String containing all instructions in this list. 1173 */ 1174 public String toString(final boolean verbose) { 1175 final StringBuilder buf = new StringBuilder(); 1176 for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) { 1177 buf.append(ih.toString(verbose)).append("\n"); 1178 } 1179 return buf.toString(); 1180 } 1181 1182 /** 1183 * Call notify() method on all observers. This method is not called automatically whenever the state has changed, but 1184 * has to be called by the user after he has finished editing the object. 1185 */ 1186 public void update() { 1187 if (observers != null) { 1188 for (final InstructionListObserver observer : observers) { 1189 observer.notify(this); 1190 } 1191 } 1192 } 1193}