InsnList


1   /***
2    * ASM: a very small and fast Java bytecode manipulation framework
3    * Copyright (c) 2000-2005 INRIA, France Telecom
4    * All rights reserved.
5    *
6    * Redistribution and use in source and binary forms, with or without
7    * modification, are permitted provided that the following conditions
8    * are met:
9    * 1. Redistributions of source code must retain the above copyright
10   *    notice, this list of conditions and the following disclaimer.
11   * 2. Redistributions in binary form must reproduce the above copyright
12   *    notice, this list of conditions and the following disclaimer in the
13   *    documentation and/or other materials provided with the distribution.
14   * 3. Neither the name of the copyright holders nor the names of its
15   *    contributors may be used to endorse or promote products derived from
16   *    this software without specific prior written permission.
17   *
18   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21   * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25   * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26   * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
28   * THE POSSIBILITY OF SUCH DAMAGE.
29   */
30  package org.objectweb.asm.tree;
31  
32  import java.util.ListIterator  ;
33  
34  import org.objectweb.asm.MethodVisitor;
35  
36  /**
37   * A doubly linked list of {@link AbstractInsnNode} objects. <i>This
38   * implementation is not thread safe</i>.
39   */
40  public class InsnList {
41  
42      /**
43       * Indicates if preconditions of methods of this class must be checked.
44       * <i>Checking preconditions causes the {@link #indexOf indexOf},
45       * {@link #set set}, {@link #insert(AbstractInsnNode, AbstractInsnNode)},
46       * {@link #insert(AbstractInsnNode, InsnList)}, {@link #remove remove} and
47       * {@link #clear} methods to execute in O(n) time instead of O(1)</i>.
48       */
49      public static boolean check;
50  
51      /**
52       * The number of instructions in this list.
53       */
54      private int size;
55  
56      /**
57       * The first instruction in this list. May be <tt>null</tt>.
58       */
59      private AbstractInsnNode first;
60  
61      /**
62       * The last instruction in this list. May be <tt>null</tt>.
63       */
64      private AbstractInsnNode last;
65  
66      /**
67       * A cache of the instructions of this list. This cache is used to improve
68       * the performance of the {@link #get} method.
69       */
70      private AbstractInsnNode[] cache;
71  
72      /**
73       * Returns the number of instructions in this list.
74       * 
75       * @return the number of instructions in this list.
76       */
77      public int size() {
78          return size;
79      }
80  
81      /**
82       * Returns the first instruction in this list.
83       * 
84       * @return the first instruction in this list, or <tt>null</tt> if the
85       *         list is empty.
86       */
87      public AbstractInsnNode getFirst() {
88          return first;
89      }
90  
91      /**
92       * Returns the last instruction in this list.
93       * 
94       * @return the last instruction in this list, or <tt>null</tt> if the list
95       *         is empty.
96       */
97      public AbstractInsnNode getLast() {
98          return last;
99      }
100 
101     /**
102      * Returns the instruction whose index is given. This method builds a cache
103      * of the instructions in this list to avoid scanning the whole list each
104      * time it is called. Once the cache is built, this method run in constant
105      * time. This cache is invalidated by all the methods that modify the list.
106      * 
107      * @param index the index of the instruction that must be returned.
108      * @return the instruction whose index is given.
109      * @throws IndexOutOfBoundsException if (index < 0 || index >= size()).
110      */
111     public AbstractInsnNode get(final int index) {
112         if (index < 0 || index >= size) {
113             throw new IndexOutOfBoundsException  ();
114         }
115         if (cache == null) {
116             cache = toArray();
117         }
118         return cache[index];
119     }
120 
121     /**
122      * Returns <tt>true</tt> if the given instruction belongs to this list.
123      * This method always scans the instructions of this list until it finds the
124      * given instruction or reaches the end of the list.
125      * 
126      * @param insn an instruction.
127      * @return <tt>true</tt> if the given instruction belongs to this list.
128      */
129     public boolean contains(final AbstractInsnNode insn) {
130         AbstractInsnNode i = first;
131         while (i != null && i != insn) {
132             i = i.next;
133         }
134         return i != null;
135     }
136 
137     /**
138      * Returns the index of the given instruction in this list. This method
139      * builds a cache of the instruction indexes to avoid scanning the whole
140      * list each time it is called. Once the cache is built, this method run in
141      * constant time. The cache is invalidated by all the methods that modify
142      * the list.
143      * 
144      * @param insn an instruction <i>of this list</i>.
145      * @return the index of the given instruction in this list. <i>The result of
146      *         this method is undefined if the given instruction does not belong
147      *         to this list</i>. Use {@link #contains contains} to test if an
148      *         instruction belongs to an instruction list or not.
149      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt> and
150      *         if insn does not belong to this list.
151      */
152     public int indexOf(final AbstractInsnNode insn) {
153         if (check && !contains(insn)) {
154             throw new IllegalArgumentException  ();
155         }
156         if (cache == null) {
157             cache = toArray();
158         }
159         return insn.index;
160     }
161 
162     /**
163      * Makes the given visitor visit all of the instructions in this list.
164      * 
165      * @param mv the method visitor that must visit the instructions.
166      */
167     public void accept(final MethodVisitor mv) {
168         AbstractInsnNode insn = first;
169         while (insn != null) {
170             insn.accept(mv);
171             insn = insn.next;
172         }
173     }
174 
175     /**
176      * Returns an iterator over the instructions in this list.
177      * 
178      * @return an iterator over the instructions in this list.
179      */
180     public ListIterator   iterator() {
181         return iterator(0);
182     }
183 
184     /**
185      * Returns an iterator over the instructions in this list.
186      * 
187      * @return an iterator over the instructions in this list.
188      */
189     public ListIterator   iterator(int index) {
190         return new InsnListIterator(index);
191     }
192     
193     /**
194      * Returns an array containing all of the instructions in this list.
195      * 
196      * @return an array containing all of the instructions in this list.
197      */
198     public AbstractInsnNode[] toArray() {
199         int i = 0;
200         AbstractInsnNode elem = first;
201         AbstractInsnNode[] insns = new AbstractInsnNode[size];
202         while (elem != null) {
203             insns[i] = elem;
204             elem.index = i++;
205             elem = elem.next;
206         }
207         return insns;
208     }
209 
210     /**
211      * Replaces an instruction of this list with another instruction.
212      * 
213      * @param location an instruction <i>of this list</i>.
214      * @param insn another instruction, <i>which must not belong to any
215      *        {@link InsnList}</i>.
216      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
217      *         and if i does not belong to this list or if insn belongs to an
218      *         instruction list.
219      */
220     public void set(final AbstractInsnNode location, final AbstractInsnNode insn) {
221         if (check && !(contains(location) && insn.index == -1)) {
222             throw new IllegalArgumentException  ();
223         }
224         AbstractInsnNode next = location.next;
225         insn.next = next;
226         if (next != null) {
227             next.prev = insn;
228         } else {
229             last = insn;
230         }
231         AbstractInsnNode prev = location.prev;
232         insn.prev = prev;
233         if (prev != null) {
234             prev.next = insn;
235         } else {
236             first = insn;
237         }
238         if (cache != null) {
239             int index = location.index;
240             cache[index] = insn;
241             insn.index = index;
242         } else {
243             insn.index = 0; // insn now belongs to an InsnList
244         }
245         location.index = -1; // i no longer belongs to an InsnList
246         location.prev = null;
247         location.next = null;
248     }
249 
250     /**
251      * Adds the given instruction to the end of this list.
252      * 
253      * @param insn an instruction, <i>which must not belong to any
254      *        {@link InsnList}</i>.
255      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
256      *         and if insn belongs to an instruction list.
257      */
258     public void add(final AbstractInsnNode insn) {
259         if (check && insn.index != -1) {
260             throw new IllegalArgumentException  ();
261         }
262         ++size;
263         if (last == null) {
264             first = insn;
265             last = insn;
266         } else {
267             last.next = insn;
268             insn.prev = last;
269         }
270         last = insn;
271         cache = null;
272         insn.index = 0; // insn now belongs to an InsnList
273     }
274 
275     /**
276      * Adds the given instructions to the end of this list.
277      * 
278      * @param insns an instruction list, which is cleared during the process.
279      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
280      *         and if insn == this.
281      */
282     public void add(final InsnList insns) {
283         if (check && insns == this) {
284             throw new IllegalArgumentException  ();
285         }
286         if (insns.size == 0) {
287             return;
288         }
289         size += insns.size;
290         if (last == null) {
291             first = insns.first;
292             last = insns.last;
293         } else {
294             AbstractInsnNode elem = insns.first;
295             last.next = elem;
296             elem.prev = last;
297             last = insns.last;
298         }
299         cache = null;
300         insns.removeAll(false);
301     }
302 
303     /**
304      * Inserts the given instruction at the begining of this list.
305      * 
306      * @param insn an instruction, <i>which must not belong to any
307      *        {@link InsnList}</i>.
308      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
309      *         and if insn belongs to an instruction list.
310      */
311     public void insert(final AbstractInsnNode insn) {
312         if (check && insn.index != -1) {
313             throw new IllegalArgumentException  ();
314         }
315         ++size;
316         if (first == null) {
317             first = insn;
318             last = insn;
319         } else {
320             first.prev = insn;
321             insn.next = first;
322         }
323         first = insn;
324         cache = null;
325         insn.index = 0; // insn now belongs to an InsnList
326     }
327 
328     /**
329      * Inserts the given instructions at the begining of this list.
330      * 
331      * @param insns an instruction list, which is cleared during the process.
332      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
333      *         and if insn == this.
334      */
335     public void insert(final InsnList insns) {
336         if (check && insns == this) {
337             throw new IllegalArgumentException  ();
338         }
339         if (insns.size == 0) {
340             return;
341         }
342         size += insns.size;
343         if (first == null) {
344             first = insns.first;
345             last = insns.last;
346         } else {
347             AbstractInsnNode elem = insns.last;
348             first.prev = elem;
349             elem.next = first;
350             first = insns.first;
351         }
352         cache = null;
353         insns.removeAll(false);
354     }
355 
356     /**
357      * Inserts the given instruction after the specified instruction.
358      * 
359      * @param location an instruction <i>of this list</i> after which insn must be
360      *        inserted.
361      * @param insn the instruction to be inserted, <i>which must not belong to
362      *        any {@link InsnList}</i>.
363      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
364      *         and if i does not belong to this list or if insn belongs to an
365      *         instruction list.
366      */
367     public void insert(final AbstractInsnNode location, final AbstractInsnNode insn) {
368         if (check && !(contains(location) && insn.index == -1)) {
369             throw new IllegalArgumentException  ();
370         }
371         ++size;
372         AbstractInsnNode next = location.next;
373         if (next == null) {
374             last = insn;
375         } else {
376             next.prev = insn;
377         }
378         location.next = insn;
379         insn.next = next;
380         insn.prev = location;
381         cache = null;
382         insn.index = 0; // insn now belongs to an InsnList
383     }
384 
385     /**
386      * Inserts the given instructions after the specified instruction.
387      * 
388      * @param location an instruction <i>of this list</i> after which the instructions
389      *        must be inserted.
390      * @param insns the instruction list to be inserted, which is cleared during
391      *        the process.
392      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
393      *         and if i does not belong to this list or if insns == this.
394      */
395     public void insert(final AbstractInsnNode location, final InsnList insns) {
396         if (check && !(contains(location) && insns != this)) {
397             throw new IllegalArgumentException  ();
398         }
399         if (insns.size == 0) {
400             return;
401         }
402         size += insns.size;
403         AbstractInsnNode ifirst = insns.first;
404         AbstractInsnNode ilast = insns.last;
405         AbstractInsnNode next = location.next;
406         if (next == null) {
407             last = ilast;
408         } else {
409             next.prev = ilast;
410         }
411         location.next = ifirst;
412         ilast.next = next;
413         ifirst.prev = location;
414         cache = null;
415         insns.removeAll(false);
416     }
417     
418     /**
419      * Inserts the given instruction before the specified instruction.
420      * 
421      * @param location an instruction <i>of this list</i> before which insn must be
422      *        inserted.
423      * @param insn the instruction to be inserted, <i>which must not belong to
424      *        any {@link InsnList}</i>.
425      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
426      *         and if i does not belong to this list or if insn belongs to an
427      *         instruction list.
428      */
429     public void insertBefore(final AbstractInsnNode location, final AbstractInsnNode insn) {
430         if (check && !(contains(location) && insn.index == -1)) {
431             throw new IllegalArgumentException  ();
432         }
433         ++size;
434         AbstractInsnNode prev = location.prev;
435         if (prev == null) {
436             first = insn;
437         } else {
438             prev.next = insn;
439         }
440         location.prev = insn;
441         insn.next = location;
442         insn.prev = prev;
443         cache = null;
444         insn.index = 0; // insn now belongs to an InsnList
445     }
446     
447     /**
448      * Inserts the given instructions before the specified instruction.
449      * 
450      * @param location  an instruction <i>of this list</i> before which the instructions
451      *        must be inserted.
452      * @param insns the instruction list to be inserted, which is cleared during
453      *        the process.
454      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
455      *         and if i does not belong to this list or if insns == this.
456      */
457     public void insertBefore(final AbstractInsnNode location, final InsnList insns) {
458         if (check && !(contains(location ) && insns != this)) {
459             throw new IllegalArgumentException  ();
460         }
461         if (insns.size == 0) {
462             return;
463         }
464         size += insns.size;
465         AbstractInsnNode ifirst = insns.first;
466         AbstractInsnNode ilast = insns.last;
467         AbstractInsnNode prev = location .prev;
468         if (prev == null) {
469             first = ifirst;
470         } else {
471             prev.next = ifirst;
472         }
473         location .prev = ilast;
474         ilast.next = location ;
475         ifirst.prev = prev;
476         cache = null;
477         insns.removeAll(false);
478     }
479     
480     
481 
482     /**
483      * Removes the given instruction from this list.
484      * 
485      * @param insn the instruction <i>of this list</i> that must be removed.
486      * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
487      *         and if insn does not belong to this list.
488      */
489     public void remove(final AbstractInsnNode insn) {
490         if (check && !contains(insn)) {
491             throw new IllegalArgumentException  ();
492         }
493         --size;
494         AbstractInsnNode next = insn.next;
495         AbstractInsnNode prev = insn.prev;
496         if (next == null) {
497             if (prev == null) {
498                 first = null;
499                 last = null;
500             } else {
501                 prev.next = null;
502                 last = prev;
503             }
504         } else {
505             if (prev == null) {
506                 first = next;
507                 next.prev = null;
508             } else {
509                 prev.next = next;
510                 next.prev = prev;
511             }
512         }
513         cache = null;
514         insn.index = -1; // insn no longer belongs to an InsnList
515         insn.prev = null;
516         insn.next = null;
517     }
518 
519     /**
520      * Removes all of the instructions of this list.
521      * 
522      * @param mark if the instructions must be marked as no longer belonging to
523      *        any {@link InsnList}.
524      */
525     private void removeAll(final boolean mark) {
526         if (mark) {
527             AbstractInsnNode insn = first;
528             while (insn != null) {
529                 AbstractInsnNode next = insn.next;
530                 insn.index = -1; // insn no longer belongs to an InsnList
531                 insn.prev = null;
532                 insn.next = null;
533                 insn = next;
534             }
535         }
536         size = 0;
537         first = null;
538         last = null;
539         cache = null;
540     }
541 
542     /**
543      * Removes all of the instructions of this list.
544      */
545     public void clear() {
546         removeAll(check);
547     }
548 
549     
550     private final class InsnListIterator implements ListIterator   {
551         AbstractInsnNode next;
552         AbstractInsnNode prev;
553 
554         public InsnListIterator(int index) {
555             if(index==size()) {
556                 next = null;
557                 prev = getLast();
558             } else {
559                 next = get(index);
560                 prev = next.prev;
561             }
562         }
563 
564         public boolean hasNext() {
565             return next != null;
566         }
567 
568         public Object   next() {
569             AbstractInsnNode result = next;
570             prev = result;
571             next = result.next;
572             return result;
573         }
574 
575         public void remove() {
576             InsnList.this.remove(prev);
577             prev = prev.prev;
578         }
579 
580         public boolean hasPrevious() {
581             return prev != null;
582         }
583 
584         public Object   previous() {
585             AbstractInsnNode result = prev;
586             next = result;
587             prev = result.prev;
588             return result;
589         }
590 
591         public int nextIndex() {
592             if (next == null) {
593                 return size();
594             }
595             if (cache == null) {
596                 cache = toArray();
597             }
598             return next.index;
599         }
600 
601         public int previousIndex() {
602             if (prev == null) {
603                 return -1;
604             }
605             if (cache == null) {
606                 cache = toArray();
607             }
608             return prev.index;
609         }
610 
611         public void add(Object   o) {
612             InsnList.this.insertBefore(next, (AbstractInsnNode) o);
613             prev = (AbstractInsnNode) o;
614         }
615 
616         public void set(Object   o) {
617             InsnList.this.set(next.prev, (AbstractInsnNode) o);
618             prev = (AbstractInsnNode) o;
619         }
620     }
621 
622 }
623
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags