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 &lt; 0 || index &gt;= 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     @SuppressWarnings("rawtypes")
 554     private final class InsnListIterator implements ListIterator {
 555 
 556         AbstractInsnNode next;
 557 
 558         AbstractInsnNode prev;
 559 
 560         AbstractInsnNode remove;
 561 
 562         InsnListIterator(int index) {
 563             if (index == size()) {
 564                 next = null;
 565                 prev = getLast();
 566             } else {
 567                 next = get(index);
 568                 prev = next.prev;
 569             }
 570         }
 571 
 572         public boolean hasNext() {
 573             return next != null;
 574         }
 575 
 576         public Object next() {
 577             if (next == null) {
 578                 throw new NoSuchElementException();
 579             }
 580             AbstractInsnNode result = next;
 581             prev = result;
 582             next = result.next;
 583             remove = result;
 584             return result;
 585         }
 586 
 587         public void remove() {
 588             if (remove != null) {
 589                 if (remove == next) {
 590                     next = next.next;
 591                 } else {
 592                     prev = prev.prev;
 593                 }
 594                 InsnList.this.remove(remove);
 595                 remove = null;
 596             } else {
 597                 throw new IllegalStateException();
 598             }
 599         }
 600 
 601         public boolean hasPrevious() {
 602             return prev != null;
 603         }
 604 
 605         public Object previous() {
 606             AbstractInsnNode result = prev;
 607             next = result;
 608             prev = result.prev;
 609             remove = result;
 610             return result;
 611         }
 612 
 613         public int nextIndex() {
 614             if (next == null) {
 615                 return size();
 616             }
 617             if (cache == null) {
 618                 cache = toArray();
 619             }
 620             return next.index;
 621         }
 622 
 623         public int previousIndex() {
 624             if (prev == null) {
 625                 return -1;
 626             }
 627             if (cache == null) {
 628                 cache = toArray();
 629             }
 630             return prev.index;
 631         }
 632 
 633         public void add(Object o) {
 634             InsnList.this.insertBefore(next, (AbstractInsnNode) o);
 635             prev = (AbstractInsnNode) o;
 636             remove = null;
 637         }
 638 
 639         public void set(Object o) {
 640             InsnList.this.set(next.prev, (AbstractInsnNode) o);
 641             prev = (AbstractInsnNode) o;
 642         }
 643     }
 644 }