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