001: /***
002: * ASM: a very small and fast Java bytecode manipulation framework
003: * Copyright (c) 2000-2005 INRIA, France Telecom
004: * All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: * 1. Redistributions of source code must retain the above copyright
010: * notice, this list of conditions and the following disclaimer.
011: * 2. Redistributions in binary form must reproduce the above copyright
012: * notice, this list of conditions and the following disclaimer in the
013: * documentation and/or other materials provided with the distribution.
014: * 3. Neither the name of the copyright holders nor the names of its
015: * contributors may be used to endorse or promote products derived from
016: * this software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
022: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
023: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
024: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
025: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
026: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
027: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
028: * THE POSSIBILITY OF SUCH DAMAGE.
029: */package com.tc.asm.tree;
030:
031: import java.util.ListIterator;
032:
033: import com.tc.asm.MethodVisitor;
034:
035: /**
036: * A doubly linked list of {@link AbstractInsnNode} objects. <i>This
037: * implementation is not thread safe</i>.
038: */
039: public class InsnList {
040:
041: /**
042: * Indicates if preconditions of methods of this class must be checked.
043: * <i>Checking preconditions causes the {@link #indexOf indexOf},
044: * {@link #set set}, {@link #insert(AbstractInsnNode, AbstractInsnNode)},
045: * {@link #insert(AbstractInsnNode, InsnList)}, {@link #remove remove} and
046: * {@link #clear} methods to execute in O(n) time instead of O(1)</i>.
047: */
048: public static boolean check;
049:
050: /**
051: * The number of instructions in this list.
052: */
053: private int size;
054:
055: /**
056: * The first instruction in this list. May be <tt>null</tt>.
057: */
058: private AbstractInsnNode first;
059:
060: /**
061: * The last instruction in this list. May be <tt>null</tt>.
062: */
063: private AbstractInsnNode last;
064:
065: /**
066: * A cache of the instructions of this list. This cache is used to improve
067: * the performance of the {@link #get} method.
068: */
069: private AbstractInsnNode[] cache;
070:
071: /**
072: * Returns the number of instructions in this list.
073: *
074: * @return the number of instructions in this list.
075: */
076: public int size() {
077: return size;
078: }
079:
080: /**
081: * Returns the first instruction in this list.
082: *
083: * @return the first instruction in this list, or <tt>null</tt> if the
084: * list is empty.
085: */
086: public AbstractInsnNode getFirst() {
087: return first;
088: }
089:
090: /**
091: * Returns the last instruction in this list.
092: *
093: * @return the last instruction in this list, or <tt>null</tt> if the list
094: * is empty.
095: */
096: public AbstractInsnNode getLast() {
097: return last;
098: }
099:
100: /**
101: * Returns the instruction whose index is given. This method builds a cache
102: * of the instructions in this list to avoid scanning the whole list each
103: * time it is called. Once the cache is built, this method run in constant
104: * time. This cache is invalidated by all the methods that modify the list.
105: *
106: * @param index the index of the instruction that must be returned.
107: * @return the instruction whose index is given.
108: * @throws IndexOutOfBoundsException if (index < 0 || index >= size()).
109: */
110: public AbstractInsnNode get(final int index) {
111: if (index < 0 || index >= size) {
112: throw new IndexOutOfBoundsException();
113: }
114: if (cache == null) {
115: cache = toArray();
116: }
117: return cache[index];
118: }
119:
120: /**
121: * Returns <tt>true</tt> if the given instruction belongs to this list.
122: * This method always scans the instructions of this list until it finds the
123: * given instruction or reaches the end of the list.
124: *
125: * @param insn an instruction.
126: * @return <tt>true</tt> if the given instruction belongs to this list.
127: */
128: public boolean contains(final AbstractInsnNode insn) {
129: AbstractInsnNode i = first;
130: while (i != null && i != insn) {
131: i = i.next;
132: }
133: return i != null;
134: }
135:
136: /**
137: * Returns the index of the given instruction in this list. This method
138: * builds a cache of the instruction indexes to avoid scanning the whole
139: * list each time it is called. Once the cache is built, this method run in
140: * constant time. The cache is invalidated by all the methods that modify
141: * the list.
142: *
143: * @param insn an instruction <i>of this list</i>.
144: * @return the index of the given instruction in this list. <i>The result of
145: * this method is undefined if the given instruction does not belong
146: * to this list</i>. Use {@link #contains contains} to test if an
147: * instruction belongs to an instruction list or not.
148: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt> and
149: * if insn does not belong to this list.
150: */
151: public int indexOf(final AbstractInsnNode insn) {
152: if (check && !contains(insn)) {
153: throw new IllegalArgumentException();
154: }
155: if (cache == null) {
156: cache = toArray();
157: }
158: return insn.index;
159: }
160:
161: /**
162: * Makes the given visitor visit all of the instructions in this list.
163: *
164: * @param mv the method visitor that must visit the instructions.
165: */
166: public void accept(final MethodVisitor mv) {
167: AbstractInsnNode insn = first;
168: while (insn != null) {
169: insn.accept(mv);
170: insn = insn.next;
171: }
172: }
173:
174: /**
175: * Returns an iterator over the instructions in this list.
176: *
177: * @return an iterator over the instructions in this list.
178: */
179: public ListIterator iterator() {
180: return iterator(0);
181: }
182:
183: /**
184: * Returns an iterator over the instructions in this list.
185: *
186: * @return an iterator over the instructions in this list.
187: */
188: public ListIterator iterator(int index) {
189: return new InsnListIterator(index);
190: }
191:
192: /**
193: * Returns an array containing all of the instructions in this list.
194: *
195: * @return an array containing all of the instructions in this list.
196: */
197: public AbstractInsnNode[] toArray() {
198: int i = 0;
199: AbstractInsnNode elem = first;
200: AbstractInsnNode[] insns = new AbstractInsnNode[size];
201: while (elem != null) {
202: insns[i] = elem;
203: elem.index = i++;
204: elem = elem.next;
205: }
206: return insns;
207: }
208:
209: /**
210: * Replaces an instruction of this list with another instruction.
211: *
212: * @param location an instruction <i>of this list</i>.
213: * @param insn another instruction, <i>which must not belong to any
214: * {@link InsnList}</i>.
215: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
216: * and if i does not belong to this list or if insn belongs to an
217: * instruction list.
218: */
219: public void set(final AbstractInsnNode location,
220: 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,
368: final AbstractInsnNode insn) {
369: if (check && !(contains(location) && insn.index == -1)) {
370: throw new IllegalArgumentException();
371: }
372: ++size;
373: AbstractInsnNode next = location.next;
374: if (next == null) {
375: last = insn;
376: } else {
377: next.prev = insn;
378: }
379: location.next = insn;
380: insn.next = next;
381: insn.prev = location;
382: cache = null;
383: insn.index = 0; // insn now belongs to an InsnList
384: }
385:
386: /**
387: * Inserts the given instructions after the specified instruction.
388: *
389: * @param location an instruction <i>of this list</i> after which the instructions
390: * must be inserted.
391: * @param insns the instruction list to be inserted, which is cleared during
392: * the process.
393: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
394: * and if i does not belong to this list or if insns == this.
395: */
396: public void insert(final AbstractInsnNode location,
397: final InsnList insns) {
398: if (check && !(contains(location) && insns != this )) {
399: throw new IllegalArgumentException();
400: }
401: if (insns.size == 0) {
402: return;
403: }
404: size += insns.size;
405: AbstractInsnNode ifirst = insns.first;
406: AbstractInsnNode ilast = insns.last;
407: AbstractInsnNode next = location.next;
408: if (next == null) {
409: last = ilast;
410: } else {
411: next.prev = ilast;
412: }
413: location.next = ifirst;
414: ilast.next = next;
415: ifirst.prev = location;
416: cache = null;
417: insns.removeAll(false);
418: }
419:
420: /**
421: * Inserts the given instruction before the specified instruction.
422: *
423: * @param location an instruction <i>of this list</i> before which insn must be
424: * inserted.
425: * @param insn the instruction to be inserted, <i>which must not belong to
426: * any {@link InsnList}</i>.
427: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
428: * and if i does not belong to this list or if insn belongs to an
429: * instruction list.
430: */
431: public void insertBefore(final AbstractInsnNode location,
432: final AbstractInsnNode insn) {
433: if (check && !(contains(location) && insn.index == -1)) {
434: throw new IllegalArgumentException();
435: }
436: ++size;
437: AbstractInsnNode prev = location.prev;
438: if (prev == null) {
439: first = insn;
440: } else {
441: prev.next = insn;
442: }
443: location.prev = insn;
444: insn.next = location;
445: insn.prev = prev;
446: cache = null;
447: insn.index = 0; // insn now belongs to an InsnList
448: }
449:
450: /**
451: * Inserts the given instructions before the specified instruction.
452: *
453: * @param location an instruction <i>of this list</i> before which the instructions
454: * must be inserted.
455: * @param insns the instruction list to be inserted, which is cleared during
456: * the process.
457: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
458: * and if i does not belong to this list or if insns == this.
459: */
460: public void insertBefore(final AbstractInsnNode location,
461: final InsnList insns) {
462: if (check && !(contains(location) && insns != this )) {
463: throw new IllegalArgumentException();
464: }
465: if (insns.size == 0) {
466: return;
467: }
468: size += insns.size;
469: AbstractInsnNode ifirst = insns.first;
470: AbstractInsnNode ilast = insns.last;
471: AbstractInsnNode prev = location.prev;
472: if (prev == null) {
473: first = ifirst;
474: } else {
475: prev.next = ifirst;
476: }
477: location.prev = ilast;
478: ilast.next = location;
479: ifirst.prev = prev;
480: cache = null;
481: insns.removeAll(false);
482: }
483:
484: /**
485: * Removes the given instruction from this list.
486: *
487: * @param insn the instruction <i>of this list</i> that must be removed.
488: * @throws IllegalArgumentException if {@link #check} is <tt>true</tt>,
489: * and if insn does not belong to this list.
490: */
491: public void remove(final AbstractInsnNode insn) {
492: if (check && !contains(insn)) {
493: throw new IllegalArgumentException();
494: }
495: --size;
496: AbstractInsnNode next = insn.next;
497: AbstractInsnNode prev = insn.prev;
498: if (next == null) {
499: if (prev == null) {
500: first = null;
501: last = null;
502: } else {
503: prev.next = null;
504: last = prev;
505: }
506: } else {
507: if (prev == null) {
508: first = next;
509: next.prev = null;
510: } else {
511: prev.next = next;
512: next.prev = prev;
513: }
514: }
515: cache = null;
516: insn.index = -1; // insn no longer belongs to an InsnList
517: insn.prev = null;
518: insn.next = null;
519: }
520:
521: /**
522: * Removes all of the instructions of this list.
523: *
524: * @param mark if the instructions must be marked as no longer belonging to
525: * any {@link InsnList}.
526: */
527: private void removeAll(final boolean mark) {
528: if (mark) {
529: AbstractInsnNode insn = first;
530: while (insn != null) {
531: AbstractInsnNode next = insn.next;
532: insn.index = -1; // insn no longer belongs to an InsnList
533: insn.prev = null;
534: insn.next = null;
535: insn = next;
536: }
537: }
538: size = 0;
539: first = null;
540: last = null;
541: cache = null;
542: }
543:
544: /**
545: * Removes all of the instructions of this list.
546: */
547: public void clear() {
548: removeAll(check);
549: }
550:
551: private final class InsnListIterator implements ListIterator {
552: AbstractInsnNode next;
553: AbstractInsnNode prev;
554:
555: public InsnListIterator(int index) {
556: if (index == size()) {
557: next = null;
558: prev = getLast();
559: } else {
560: next = get(index);
561: prev = next.prev;
562: }
563: }
564:
565: public boolean hasNext() {
566: return next != null;
567: }
568:
569: public Object next() {
570: AbstractInsnNode result = next;
571: prev = result;
572: next = result.next;
573: return result;
574: }
575:
576: public void remove() {
577: InsnList.this .remove(prev);
578: prev = prev.prev;
579: }
580:
581: public boolean hasPrevious() {
582: return prev != null;
583: }
584:
585: public Object previous() {
586: AbstractInsnNode result = prev;
587: next = result;
588: prev = result.prev;
589: return result;
590: }
591:
592: public int nextIndex() {
593: if (next == null) {
594: return size();
595: }
596: if (cache == null) {
597: cache = toArray();
598: }
599: return next.index;
600: }
601:
602: public int previousIndex() {
603: if (prev == null) {
604: return -1;
605: }
606: if (cache == null) {
607: cache = toArray();
608: }
609: return prev.index;
610: }
611:
612: public void add(Object o) {
613: InsnList.this .insertBefore(next, (AbstractInsnNode) o);
614: prev = (AbstractInsnNode) o;
615: }
616:
617: public void set(Object o) {
618: InsnList.this .set(next.prev, (AbstractInsnNode) o);
619: prev = (AbstractInsnNode) o;
620: }
621: }
622:
623: }
|