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