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