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