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