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