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 * @return an iterator over the instructions in this list.
209 */
210 @SuppressWarnings("unchecked")
211 public ListIterator<AbstractInsnNode> iterator(int index) {
212 return new InsnListIterator(index);
213 }
214
215 /**
216 * Returns an array containing all of the instructions in this list.
217 *
218 * @return an array containing all of the instructions in this list.
219 */
220 public AbstractInsnNode[] toArray() {
221 int i = 0;
222 AbstractInsnNode elem = first;
223 AbstractInsnNode[] insns = new AbstractInsnNode[size];
224 while (elem != null) {
225 insns[i] = elem;
226 elem.index = i++;
227 elem = elem.next;
228 }
229 return insns;
230 }
231
232 /**
233 * Replaces an instruction of this list with another instruction.
234 *
235 * @param location
236 * an instruction <i>of this list</i>.
237 * @param insn
238 * another instruction, <i>which must not belong to any
239 * {@link InsnList}</i>.
240 */
241 public void set(final AbstractInsnNode location, final AbstractInsnNode insn) {
242 AbstractInsnNode next = location.next;
243 insn.next = next;
244 if (next != null) {
245 next.prev = insn;
246 } else {
247 last = insn;
248 }
249 AbstractInsnNode prev = location.prev;
250 insn.prev = prev;
251 if (prev != null) {
252 prev.next = insn;
253 } else {
254 first = insn;
255 }
256 if (cache != null) {
257 int index = location.index;
258 cache[index] = insn;
259 insn.index = index;
260 } else {
261 insn.index = 0; // insn now belongs to an InsnList
262 }
263 location.index = -1; // i no longer belongs to an InsnList
264 location.prev = null;
265 location.next = null;
266 }
267
268 /**
269 * Adds the given instruction to the end of this list.
270 *
271 * @param insn
272 * an instruction, <i>which must not belong to any
273 * {@link InsnList}</i>.
274 */
275 public void add(final AbstractInsnNode insn) {
276 ++size;
277 if (last == null) {
278 first = insn;
279 last = insn;
280 } else {
281 last.next = insn;
282 insn.prev = last;
283 }
284 last = insn;
285 cache = null;
286 insn.index = 0; // insn now belongs to an InsnList
287 }
288
289 /**
290 * Adds the given instructions to the end of this list.
291 *
292 * @param insns
293 * an instruction list, which is cleared during the process. This
294 * list must be different from 'this'.
295 */
296 public void add(final InsnList insns) {
297 if (insns.size == 0) {
298 return;
299 }
300 size += insns.size;
301 if (last == null) {
302 first = insns.first;
303 last = insns.last;
304 } else {
305 AbstractInsnNode elem = insns.first;
306 last.next = elem;
307 elem.prev = last;
308 last = insns.last;
309 }
310 cache = null;
311 insns.removeAll(false);
312 }
313
314 /**
315 * Inserts the given instruction at the begining of this list.
316 *
317 * @param insn
318 * an instruction, <i>which must not belong to any
319 * {@link InsnList}</i>.
320 */
321 public void insert(final AbstractInsnNode insn) {
322 ++size;
323 if (first == null) {
324 first = insn;
325 last = insn;
326 } else {
327 first.prev = insn;
328 insn.next = first;
329 }
330 first = insn;
331 cache = null;
332 insn.index = 0; // insn now belongs to an InsnList
333 }
334
335 /**
336 * Inserts the given instructions at the begining of this list.
337 *
338 * @param insns
339 * an instruction list, which is cleared during the process. This
340 * list must be different from 'this'.
341 */
342 public void insert(final InsnList insns) {
343 if (insns.size == 0) {
344 return;
345 }
346 size += insns.size;
347 if (first == null) {
348 first = insns.first;
349 last = insns.last;
350 } else {
351 AbstractInsnNode elem = insns.last;
352 first.prev = elem;
353 elem.next = first;
354 first = insns.first;
355 }
356 cache = null;
357 insns.removeAll(false);
358 }
359
360 /**
361 * Inserts the given instruction after the specified instruction.
362 *
363 * @param location
364 * an instruction <i>of this list</i> after which insn must be
365 * inserted.
366 * @param insn
367 * the instruction to be inserted, <i>which must not belong to
368 * any {@link InsnList}</i>.
369 */
370 public void insert(final AbstractInsnNode location,
371 final AbstractInsnNode insn) {
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
390 * an instruction <i>of this list</i> after which the
391 * instructions must be inserted.
392 * @param insns
393 * the instruction list to be inserted, which is cleared during
394 * the process. This list must be different from 'this'.
395 */
396 public void insert(final AbstractInsnNode location, final InsnList insns) {
397 if (insns.size == 0) {
398 return;
399 }
400 size += insns.size;
401 AbstractInsnNode ifirst = insns.first;
402 AbstractInsnNode ilast = insns.last;
403 AbstractInsnNode next = location.next;
404 if (next == null) {
405 last = ilast;
406 } else {
407 next.prev = ilast;
408 }
409 location.next = ifirst;
410 ilast.next = next;
411 ifirst.prev = location;
412 cache = null;
413 insns.removeAll(false);
414 }
415
416 /**
417 * Inserts the given instruction before the specified instruction.
418 *
419 * @param location
420 * an instruction <i>of this list</i> before which insn must be
421 * inserted.
422 * @param insn
423 * the instruction to be inserted, <i>which must not belong to
424 * any {@link InsnList}</i>.
425 */
426 public void insertBefore(final AbstractInsnNode location,
427 final AbstractInsnNode insn) {
428 ++size;
429 AbstractInsnNode prev = location.prev;
430 if (prev == null) {
431 first = insn;
432 } else {
433 prev.next = insn;
434 }
435 location.prev = insn;
436 insn.next = location;
437 insn.prev = prev;
438 cache = null;
439 insn.index = 0; // insn now belongs to an InsnList
440 }
441
442 /**
443 * Inserts the given instructions before the specified instruction.
444 *
445 * @param location
446 * an instruction <i>of this list</i> before which the
447 * instructions must be inserted.
448 * @param insns
449 * the instruction list to be inserted, which is cleared during
450 * the process. This list must be different from 'this'.
451 */
452 public void insertBefore(final AbstractInsnNode location,
453 final InsnList insns) {
454 if (insns.size == 0) {
455 return;
456 }
457 size += insns.size;
458 AbstractInsnNode ifirst = insns.first;
459 AbstractInsnNode ilast = insns.last;
460 AbstractInsnNode prev = location.prev;
461 if (prev == null) {
462 first = ifirst;
463 } else {
464 prev.next = ifirst;
465 }
466 location.prev = ilast;
467 ilast.next = location;
468 ifirst.prev = prev;
469 cache = null;
470 insns.removeAll(false);
471 }
472
473 /**
474 * Removes the given instruction from this list.
475 *
476 * @param insn
477 * the instruction <i>of this list</i> that must be removed.
478 */
479 public void remove(final AbstractInsnNode insn) {
480 --size;
481 AbstractInsnNode next = insn.next;
482 AbstractInsnNode prev = insn.prev;
483 if (next == null) {
484 if (prev == null) {
485 first = null;
486 last = null;
487 } else {
488 prev.next = null;
489 last = prev;
490 }
491 } else {
492 if (prev == null) {
493 first = next;
494 next.prev = null;
495 } else {
496 prev.next = next;
497 next.prev = prev;
498 }
499 }
500 cache = null;
501 insn.index = -1; // insn no longer belongs to an InsnList
502 insn.prev = null;
503 insn.next = null;
504 }
505
506 /**
507 * Removes all of the instructions of this list.
508 *
509 * @param mark
510 * if the instructions must be marked as no longer belonging to
511 * any {@link InsnList}.
512 */
513 void removeAll(final boolean mark) {
514 if (mark) {
515 AbstractInsnNode insn = first;
516 while (insn != null) {
517 AbstractInsnNode next = insn.next;
518 insn.index = -1; // insn no longer belongs to an InsnList
519 insn.prev = null;
520 insn.next = null;
521 insn = next;
522 }
523 }
524 size = 0;
525 first = null;
526 last = null;
527 cache = null;
528 }
529
530 /**
531 * Removes all of the instructions of this list.
532 */
533 public void clear() {
534 removeAll(false);
535 }
536
537 /**
538 * Reset all labels in the instruction list. This method should be called
539 * before reusing same instructions list between several
540 * <code>ClassWriter</code>s.
541 */
542 public void resetLabels() {
543 AbstractInsnNode insn = first;
544 while (insn != null) {
545 if (insn instanceof LabelNode) {
546 ((LabelNode) insn).resetLabel();
547 }
548 insn = insn.next;
549 }
550 }
551
552 // this class is not generified because it will create bridges
553 private final class InsnListIterator implements ListIterator {
554
555 AbstractInsnNode next;
556
557 AbstractInsnNode prev;
558
559 InsnListIterator(int index) {
560 if (index == size()) {
561 next = null;
562 prev = getLast();
563 } else {
564 next = get(index);
565 prev = next.prev;
566 }
567 }
568
569 public boolean hasNext() {
570 return next != null;
571 }
572
573 public Object next() {
574 if (next == null) {
575 throw new NoSuchElementException();
576 }
577 AbstractInsnNode result = next;
578 prev = result;
579 next = result.next;
580 return result;
581 }
582
583 public void remove() {
584 InsnList.this.remove(prev);
585 prev = prev.prev;
586 }
587
588 public boolean hasPrevious() {
589 return prev != null;
590 }
591
592 public Object previous() {
593 AbstractInsnNode result = prev;
594 next = result;
595 prev = result.prev;
596 return result;
597 }
598
599 public int nextIndex() {
600 if (next == null) {
601 return size();
602 }
603 if (cache == null) {
604 cache = toArray();
605 }
606 return next.index;
607 }
608
609 public int previousIndex() {
610 if (prev == null) {
611 return -1;
612 }
613 if (cache == null) {
614 cache = toArray();
615 }
616 return prev.index;
617 }
618
619 public void add(Object o) {
620 InsnList.this.insertBefore(next, (AbstractInsnNode) o);
621 prev = (AbstractInsnNode) o;
622 }
623
624 public void set(Object o) {
625 InsnList.this.set(next.prev, (AbstractInsnNode) o);
626 prev = (AbstractInsnNode) o;
627 }
628 }
629 }