InstructionList


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