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