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