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