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