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