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