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