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
106 * list 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 the index of the instruction that must be returned.
129 * @return the instruction whose index is given.
130 * @throws IndexOutOfBoundsException if (index {@literal <} 0 || index {@literal >=} size()).
131 */
132 public AbstractInsnNode get(final int index) {
133 if (index < 0 || index >= size) {
134 throw new IndexOutOfBoundsException();
135 }
136 if (cache == null) {
137 cache = toArray();
138 }
139 return cache[index];
140 }
141
142 /**
143 * Returns <tt>true</tt> if the given instruction belongs to this list.
144 * This method always scans the instructions of this list until it finds the
145 * given instruction or reaches the end of the list.
146 *
147 * @param insn an instruction.
148 * @return <tt>true</tt> if the given instruction belongs to this list.
149 */
150 public boolean contains(final AbstractInsnNode insn) {
151 AbstractInsnNode i = first;
152 while (i != null && i != insn) {
153 i = i.next;
154 }
155 return i != null;
156 }
157
158 /**
159 * Returns the index of the given instruction in this list. This method
160 * builds a cache of the instruction indexes to avoid scanning the whole
161 * list each time it is called. Once the cache is built, this method run in
162 * constant time. The cache is invalidated by all the methods that modify
163 * the list.
164 *
165 * @param insn an instruction <i>of this list</i>.
166 * @return the index of the given instruction in this list. <i>The result of
167 * this method is undefined if the given instruction does not belong
168 * to this list</i>. Use {@link #contains contains} to test if an
169 * instruction belongs to an instruction list or not.
170 */
171 public int indexOf(final AbstractInsnNode insn) {
172 if (cache == null) {
173 cache = toArray();
174 }
175 return insn.index;
176 }
177
178 /**
179 * Makes the given visitor visit all of the instructions in this list.
180 *
181 * @param mv the method visitor that must visit the instructions.
182 */
183 public void accept(final MethodVisitor mv) {
184 AbstractInsnNode insn = first;
185 while (insn != null) {
186 insn.accept(mv);
187 insn = insn.next;
188 }
189 }
190
191 /**
192 * Returns an iterator over the instructions in this list.
193 *
194 * @return an iterator over the instructions in this list.
195 */
196 public ListIterator<AbstractInsnNode> iterator() {
197 return iterator(0);
198 }
199
200 /**
201 * Returns an iterator over the instructions in this list.
202 *
203 * @return an iterator over the instructions in this list.
204 */
205 @SuppressWarnings("unchecked")
206 public ListIterator<AbstractInsnNode> iterator(int index) {
207 return new InsnListIterator(index);
208 }
209
210 /**
211 * Returns an array containing all of the instructions in this list.
212 *
213 * @return an array containing all of the instructions in this list.
214 */
215 public AbstractInsnNode[] toArray() {
216 int i = 0;
217 AbstractInsnNode elem = first;
218 AbstractInsnNode[] insns = new AbstractInsnNode[size];
219 while (elem != null) {
220 insns[i] = elem;
221 elem.index = i++;
222 elem = elem.next;
223 }
224 return insns;
225 }
226
227 /**
228 * Replaces an instruction of this list with another instruction.
229 *
230 * @param location an instruction <i>of this list</i>.
231 * @param insn another instruction, <i>which must not belong to any
232 * {@link InsnList}</i>.
233 */
234 public void set(final AbstractInsnNode location, final AbstractInsnNode insn) {
235 AbstractInsnNode next = location.next;
236 insn.next = next;
237 if (next != null) {
238 next.prev = insn;
239 } else {
240 last = insn;
241 }
242 AbstractInsnNode prev = location.prev;
243 insn.prev = prev;
244 if (prev != null) {
245 prev.next = insn;
246 } else {
247 first = insn;
248 }
249 if (cache != null) {
250 int index = location.index;
251 cache[index] = insn;
252 insn.index = index;
253 } else {
254 insn.index = 0; // insn now belongs to an InsnList
255 }
256 location.index = -1; // i no longer belongs to an InsnList
257 location.prev = null;
258 location.next = null;
259 }
260
261 /**
262 * Adds the given instruction to the end of this list.
263 *
264 * @param insn an instruction, <i>which must not belong to any
265 * {@link InsnList}</i>.
266 */
267 public void add(final AbstractInsnNode insn) {
268 ++size;
269 if (last == null) {
270 first = insn;
271 last = insn;
272 } else {
273 last.next = insn;
274 insn.prev = last;
275 }
276 last = insn;
277 cache = null;
278 insn.index = 0; // insn now belongs to an InsnList
279 }
280
281 /**
282 * Adds the given instructions to the end of this list.
283 *
284 * @param insns an instruction list, which is cleared during the process.
285 * This list must be different from 'this'.
286 */
287 public void add(final InsnList insns) {
288 if (insns.size == 0) {
289 return;
290 }
291 size += insns.size;
292 if (last == null) {
293 first = insns.first;
294 last = insns.last;
295 } else {
296 AbstractInsnNode elem = insns.first;
297 last.next = elem;
298 elem.prev = last;
299 last = insns.last;
300 }
301 cache = null;
302 insns.removeAll(false);
303 }
304
305 /**
306 * Inserts the given instruction at the begining of this list.
307 *
308 * @param insn an instruction, <i>which must not belong to any
309 * {@link InsnList}</i>.
310 */
311 public void insert(final AbstractInsnNode insn) {
312 ++size;
313 if (first == null) {
314 first = insn;
315 last = insn;
316 } else {
317 first.prev = insn;
318 insn.next = first;
319 }
320 first = insn;
321 cache = null;
322 insn.index = 0; // insn now belongs to an InsnList
323 }
324
325 /**
326 * Inserts the given instructions at the begining of this list.
327 *
328 * @param insns an instruction list, which is cleared during the process.
329 * This list must be different from 'this'.
330 */
331 public void insert(final InsnList insns) {
332 if (insns.size == 0) {
333 return;
334 }
335 size += insns.size;
336 if (first == null) {
337 first = insns.first;
338 last = insns.last;
339 } else {
340 AbstractInsnNode elem = insns.last;
341 first.prev = elem;
342 elem.next = first;
343 first = insns.first;
344 }
345 cache = null;
346 insns.removeAll(false);
347 }
348
349 /**
350 * Inserts the given instruction after the specified instruction.
351 *
352 * @param location an instruction <i>of this list</i> after which insn must be
353 * inserted.
354 * @param insn the instruction to be inserted, <i>which must not belong to
355 * any {@link InsnList}</i>.
356 */
357 public void insert(final AbstractInsnNode location, final AbstractInsnNode insn) {
358 ++size;
359 AbstractInsnNode next = location.next;
360 if (next == null) {
361 last = insn;
362 } else {
363 next.prev = insn;
364 }
365 location.next = insn;
366 insn.next = next;
367 insn.prev = location;
368 cache = null;
369 insn.index = 0; // insn now belongs to an InsnList
370 }
371
372 /**
373 * Inserts the given instructions after the specified instruction.
374 *
375 * @param location an instruction <i>of this list</i> after which the
376 * instructions must be inserted.
377 * @param insns the instruction list to be inserted, which is cleared during
378 * the process. This list must be different from 'this'.
379 */
380 public void insert(final AbstractInsnNode location, final InsnList insns) {
381 if (insns.size == 0) {
382 return;
383 }
384 size += insns.size;
385 AbstractInsnNode ifirst = insns.first;
386 AbstractInsnNode ilast = insns.last;
387 AbstractInsnNode next = location.next;
388 if (next == null) {
389 last = ilast;
390 } else {
391 next.prev = ilast;
392 }
393 location.next = ifirst;
394 ilast.next = next;
395 ifirst.prev = location;
396 cache = null;
397 insns.removeAll(false);
398 }
399
400 /**
401 * Inserts the given instruction before the specified instruction.
402 *
403 * @param location an instruction <i>of this list</i> before which insn must be
404 * inserted.
405 * @param insn the instruction to be inserted, <i>which must not belong to
406 * any {@link InsnList}</i>.
407 */
408 public void insertBefore(final AbstractInsnNode location, final AbstractInsnNode insn) {
409 ++size;
410 AbstractInsnNode prev = location.prev;
411 if (prev == null) {
412 first = insn;
413 } else {
414 prev.next = insn;
415 }
416 location.prev = insn;
417 insn.next = location;
418 insn.prev = prev;
419 cache = null;
420 insn.index = 0; // insn now belongs to an InsnList
421 }
422
423 /**
424 * Inserts the given instructions before the specified instruction.
425 *
426 * @param location an instruction <i>of this list</i> before which the instructions
427 * must be inserted.
428 * @param insns the instruction list to be inserted, which is cleared during
429 * the process. This list must be different from 'this'.
430 */
431 public void insertBefore(final AbstractInsnNode location, final InsnList insns) {
432 if (insns.size == 0) {
433 return;
434 }
435 size += insns.size;
436 AbstractInsnNode ifirst = insns.first;
437 AbstractInsnNode ilast = insns.last;
438 AbstractInsnNode prev = location .prev;
439 if (prev == null) {
440 first = ifirst;
441 } else {
442 prev.next = ifirst;
443 }
444 location .prev = ilast;
445 ilast.next = location ;
446 ifirst.prev = prev;
447 cache = null;
448 insns.removeAll(false);
449 }
450
451
452
453 /**
454 * Removes the given instruction from this list.
455 *
456 * @param insn the instruction <i>of this list</i> that must be removed.
457 */
458 public void remove(final AbstractInsnNode insn) {
459 --size;
460 AbstractInsnNode next = insn.next;
461 AbstractInsnNode prev = insn.prev;
462 if (next == null) {
463 if (prev == null) {
464 first = null;
465 last = null;
466 } else {
467 prev.next = null;
468 last = prev;
469 }
470 } else {
471 if (prev == null) {
472 first = next;
473 next.prev = null;
474 } else {
475 prev.next = next;
476 next.prev = prev;
477 }
478 }
479 cache = null;
480 insn.index = -1; // insn no longer belongs to an InsnList
481 insn.prev = null;
482 insn.next = null;
483 }
484
485 /**
486 * Removes all of the instructions of this list.
487 *
488 * @param mark if the instructions must be marked as no longer belonging to
489 * any {@link InsnList}.
490 */
491 void removeAll(final boolean mark) {
492 if (mark) {
493 AbstractInsnNode insn = first;
494 while (insn != null) {
495 AbstractInsnNode next = insn.next;
496 insn.index = -1; // insn no longer belongs to an InsnList
497 insn.prev = null;
498 insn.next = null;
499 insn = next;
500 }
501 }
502 size = 0;
503 first = null;
504 last = null;
505 cache = null;
506 }
507
508 /**
509 * Removes all of the instructions of this list.
510 */
511 public void clear() {
512 removeAll(false);
513 }
514
515 /**
516 * Reset all labels in the instruction list. This method should be called
517 * before reusing same instructions list between several
518 * <code>ClassWriter</code>s.
519 */
520 public void resetLabels() {
521 AbstractInsnNode insn = first;
522 while (insn != null) {
523 if (insn instanceof LabelNode) {
524 ((LabelNode) insn).resetLabel();
525 }
526 insn = insn.next;
527 }
528 }
529
530 // this class is not generified because it will create bridges
531 private final class InsnListIterator implements ListIterator/*<AbstractInsnNode>*/ {
532
533 AbstractInsnNode next;
534
535 AbstractInsnNode prev;
536
537 InsnListIterator(int index) {
538 if(index==size()) {
539 next = null;
540 prev = getLast();
541 } else {
542 next = get(index);
543 prev = next.prev;
544 }
545 }
546
547 public boolean hasNext() {
548 return next != null;
549 }
550
551 public Object next() {
552 if (next == null) {
553 throw new NoSuchElementException();
554 }
555 AbstractInsnNode result = next;
556 prev = result;
557 next = result.next;
558 return result;
559 }
560
561 public void remove() {
562 InsnList.this.remove(prev);
563 prev = prev.prev;
564 }
565
566 public boolean hasPrevious() {
567 return prev != null;
568 }
569
570 public Object previous() {
571 AbstractInsnNode result = prev;
572 next = result;
573 prev = result.prev;
574 return result;
575 }
576
577 public int nextIndex() {
578 if (next == null) {
579 return size();
580 }
581 if (cache == null) {
582 cache = toArray();
583 }
584 return next.index;
585 }
586
587 public int previousIndex() {
588 if (prev == null) {
589 return -1;
590 }
591 if (cache == null) {
592 cache = toArray();
593 }
594 return prev.index;
595 }
596
597 public void add(Object o) {
598 InsnList.this.insertBefore(next, (AbstractInsnNode) o);
599 prev = (AbstractInsnNode) o;
600 }
601
602 public void set(Object o) {
603 InsnList.this.set(next.prev, (AbstractInsnNode) o);
604 prev = (AbstractInsnNode) o;
605 }
606 }
607 }