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