InstructionList


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