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.analysis;
  60 
  61 import java.util.ArrayList;
  62 import java.util.HashMap;
  63 import java.util.List;
  64 import java.util.Map;
  65 
  66 import jdk.internal.org.objectweb.asm.Opcodes;
  67 import jdk.internal.org.objectweb.asm.Type;
  68 import jdk.internal.org.objectweb.asm.tree.AbstractInsnNode;
  69 import jdk.internal.org.objectweb.asm.tree.IincInsnNode;
  70 import jdk.internal.org.objectweb.asm.tree.InsnList;
  71 import jdk.internal.org.objectweb.asm.tree.JumpInsnNode;
  72 import jdk.internal.org.objectweb.asm.tree.LabelNode;
  73 import jdk.internal.org.objectweb.asm.tree.LookupSwitchInsnNode;
  74 import jdk.internal.org.objectweb.asm.tree.MethodNode;
  75 import jdk.internal.org.objectweb.asm.tree.TableSwitchInsnNode;
  76 import jdk.internal.org.objectweb.asm.tree.TryCatchBlockNode;
  77 import jdk.internal.org.objectweb.asm.tree.VarInsnNode;
  78 
  79 /**
  80  * A semantic bytecode analyzer. <i>This class does not fully check that JSR and
  81  * RET instructions are valid.</i>
  82  *
  83  * @param <V>
  84  *            type of the Value used for the analysis.
  85  *
  86  * @author Eric Bruneton
  87  */
  88 public class Analyzer<V extends Value> implements Opcodes {
  89 
  90     private final Interpreter<V> interpreter;
  91 
  92     private int n;
  93 
  94     private InsnList insns;
  95 
  96     private List<TryCatchBlockNode>[] handlers;
  97 
  98     private Frame<V>[] frames;
  99 
 100     private Subroutine[] subroutines;
 101 
 102     private boolean[] queued;
 103 
 104     private int[] queue;
 105 
 106     private int top;
 107 
 108     /**
 109      * Constructs a new {@link Analyzer}.
 110      *
 111      * @param interpreter
 112      *            the interpreter to be used to symbolically interpret the
 113      *            bytecode instructions.
 114      */
 115     public Analyzer(final Interpreter<V> interpreter) {
 116         this.interpreter = interpreter;
 117     }
 118 
 119     /**
 120      * Analyzes the given method.
 121      *
 122      * @param owner
 123      *            the internal name of the class to which the method belongs.
 124      * @param m
 125      *            the method to be analyzed.
 126      * @return the symbolic state of the execution stack frame at each bytecode
 127      *         instruction of the method. The size of the returned array is
 128      *         equal to the number of instructions (and labels) of the method. A
 129      *         given frame is <tt>null</tt> if and only if the corresponding
 130      *         instruction cannot be reached (dead code).
 131      * @throws AnalyzerException
 132      *             if a problem occurs during the analysis.
 133      */
 134     public Frame<V>[] analyze(final String owner, final MethodNode m)
 135             throws AnalyzerException {
 136         if ((m.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0) {
 137             frames = (Frame<V>[]) new Frame<?>[0];
 138             return frames;
 139         }
 140         n = m.instructions.size();
 141         insns = m.instructions;
 142         handlers = (List<TryCatchBlockNode>[]) new List<?>[n];
 143         frames = (Frame<V>[]) new Frame<?>[n];
 144         subroutines = new Subroutine[n];
 145         queued = new boolean[n];
 146         queue = new int[n];
 147         top = 0;
 148 
 149         // computes exception handlers for each instruction
 150         for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
 151             TryCatchBlockNode tcb = m.tryCatchBlocks.get(i);
 152             int begin = insns.indexOf(tcb.start);
 153             int end = insns.indexOf(tcb.end);
 154             for (int j = begin; j < end; ++j) {
 155                 List<TryCatchBlockNode> insnHandlers = handlers[j];
 156                 if (insnHandlers == null) {
 157                     insnHandlers = new ArrayList<TryCatchBlockNode>();
 158                     handlers[j] = insnHandlers;
 159                 }
 160                 insnHandlers.add(tcb);
 161             }
 162         }
 163 
 164         // computes the subroutine for each instruction:
 165         Subroutine main = new Subroutine(null, m.maxLocals, null);
 166         List<AbstractInsnNode> subroutineCalls = new ArrayList<AbstractInsnNode>();
 167         Map<LabelNode, Subroutine> subroutineHeads = new HashMap<LabelNode, Subroutine>();
 168         findSubroutine(0, main, subroutineCalls);
 169         while (!subroutineCalls.isEmpty()) {
 170             JumpInsnNode jsr = (JumpInsnNode) subroutineCalls.remove(0);
 171             Subroutine sub = subroutineHeads.get(jsr.label);
 172             if (sub == null) {
 173                 sub = new Subroutine(jsr.label, m.maxLocals, jsr);
 174                 subroutineHeads.put(jsr.label, sub);
 175                 findSubroutine(insns.indexOf(jsr.label), sub, subroutineCalls);
 176             } else {
 177                 sub.callers.add(jsr);
 178             }
 179         }
 180         for (int i = 0; i < n; ++i) {
 181             if (subroutines[i] != null && subroutines[i].start == null) {
 182                 subroutines[i] = null;
 183             }
 184         }
 185 
 186         // initializes the data structures for the control flow analysis
 187         Frame<V> current = newFrame(m.maxLocals, m.maxStack);
 188         Frame<V> handler = newFrame(m.maxLocals, m.maxStack);
 189         current.setReturn(interpreter.newValue(Type.getReturnType(m.desc)));
 190         Type[] args = Type.getArgumentTypes(m.desc);
 191         int local = 0;
 192         if ((m.access & ACC_STATIC) == 0) {
 193             Type ctype = Type.getObjectType(owner);
 194             current.setLocal(local++, interpreter.newValue(ctype));
 195         }
 196         for (int i = 0; i < args.length; ++i) {
 197             current.setLocal(local++, interpreter.newValue(args[i]));
 198             if (args[i].getSize() == 2) {
 199                 current.setLocal(local++, interpreter.newValue(null));
 200             }
 201         }
 202         while (local < m.maxLocals) {
 203             current.setLocal(local++, interpreter.newValue(null));
 204         }
 205         merge(0, current, null);
 206 
 207         init(owner, m);
 208 
 209         // control flow analysis
 210         while (top > 0) {
 211             int insn = queue[--top];
 212             Frame<V> f = frames[insn];
 213             Subroutine subroutine = subroutines[insn];
 214             queued[insn] = false;
 215 
 216             AbstractInsnNode insnNode = null;
 217             try {
 218                 insnNode = m.instructions.get(insn);
 219                 int insnOpcode = insnNode.getOpcode();
 220                 int insnType = insnNode.getType();
 221 
 222                 if (insnType == AbstractInsnNode.LABEL
 223                         || insnType == AbstractInsnNode.LINE
 224                         || insnType == AbstractInsnNode.FRAME) {
 225                     merge(insn + 1, f, subroutine);
 226                     newControlFlowEdge(insn, insn + 1);
 227                 } else {
 228                     current.init(f).execute(insnNode, interpreter);
 229                     subroutine = subroutine == null ? null : subroutine.copy();
 230 
 231                     if (insnNode instanceof JumpInsnNode) {
 232                         JumpInsnNode j = (JumpInsnNode) insnNode;
 233                         if (insnOpcode != GOTO && insnOpcode != JSR) {
 234                             merge(insn + 1, current, subroutine);
 235                             newControlFlowEdge(insn, insn + 1);
 236                         }
 237                         int jump = insns.indexOf(j.label);
 238                         if (insnOpcode == JSR) {
 239                             merge(jump, current, new Subroutine(j.label,
 240                                     m.maxLocals, j));
 241                         } else {
 242                             merge(jump, current, subroutine);
 243                         }
 244                         newControlFlowEdge(insn, jump);
 245                     } else if (insnNode instanceof LookupSwitchInsnNode) {
 246                         LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode;
 247                         int jump = insns.indexOf(lsi.dflt);
 248                         merge(jump, current, subroutine);
 249                         newControlFlowEdge(insn, jump);
 250                         for (int j = 0; j < lsi.labels.size(); ++j) {
 251                             LabelNode label = lsi.labels.get(j);
 252                             jump = insns.indexOf(label);
 253                             merge(jump, current, subroutine);
 254                             newControlFlowEdge(insn, jump);
 255                         }
 256                     } else if (insnNode instanceof TableSwitchInsnNode) {
 257                         TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode;
 258                         int jump = insns.indexOf(tsi.dflt);
 259                         merge(jump, current, subroutine);
 260                         newControlFlowEdge(insn, jump);
 261                         for (int j = 0; j < tsi.labels.size(); ++j) {
 262                             LabelNode label = tsi.labels.get(j);
 263                             jump = insns.indexOf(label);
 264                             merge(jump, current, subroutine);
 265                             newControlFlowEdge(insn, jump);
 266                         }
 267                     } else if (insnOpcode == RET) {
 268                         if (subroutine == null) {
 269                             throw new AnalyzerException(insnNode,
 270                                     "RET instruction outside of a sub routine");
 271                         }
 272                         for (int i = 0; i < subroutine.callers.size(); ++i) {
 273                             JumpInsnNode caller = subroutine.callers.get(i);
 274                             int call = insns.indexOf(caller);
 275                             if (frames[call] != null) {
 276                                 merge(call + 1, frames[call], current,
 277                                         subroutines[call], subroutine.access);
 278                                 newControlFlowEdge(insn, call + 1);
 279                             }
 280                         }
 281                     } else if (insnOpcode != ATHROW
 282                             && (insnOpcode < IRETURN || insnOpcode > RETURN)) {
 283                         if (subroutine != null) {
 284                             if (insnNode instanceof VarInsnNode) {
 285                                 int var = ((VarInsnNode) insnNode).var;
 286                                 subroutine.access[var] = true;
 287                                 if (insnOpcode == LLOAD || insnOpcode == DLOAD
 288                                         || insnOpcode == LSTORE
 289                                         || insnOpcode == DSTORE) {
 290                                     subroutine.access[var + 1] = true;
 291                                 }
 292                             } else if (insnNode instanceof IincInsnNode) {
 293                                 int var = ((IincInsnNode) insnNode).var;
 294                                 subroutine.access[var] = true;
 295                             }
 296                         }
 297                         merge(insn + 1, current, subroutine);
 298                         newControlFlowEdge(insn, insn + 1);
 299                     }
 300                 }
 301 
 302                 List<TryCatchBlockNode> insnHandlers = handlers[insn];
 303                 if (insnHandlers != null) {
 304                     for (int i = 0; i < insnHandlers.size(); ++i) {
 305                         TryCatchBlockNode tcb = insnHandlers.get(i);
 306                         Type type;
 307                         if (tcb.type == null) {
 308                             type = Type.getObjectType("java/lang/Throwable");
 309                         } else {
 310                             type = Type.getObjectType(tcb.type);
 311                         }
 312                         int jump = insns.indexOf(tcb.handler);
 313                         if (newControlFlowExceptionEdge(insn, tcb)) {
 314                             handler.init(f);
 315                             handler.clearStack();
 316                             handler.push(interpreter.newValue(type));
 317                             merge(jump, handler, subroutine);
 318                         }
 319                     }
 320                 }
 321             } catch (AnalyzerException e) {
 322                 throw new AnalyzerException(e.node, "Error at instruction "
 323                         + insn + ": " + e.getMessage(), e);
 324             } catch (Exception e) {
 325                 throw new AnalyzerException(insnNode, "Error at instruction "
 326                         + insn + ": " + e.getMessage(), e);
 327             }
 328         }
 329 
 330         return frames;
 331     }
 332 
 333     private void findSubroutine(int insn, final Subroutine sub,
 334             final List<AbstractInsnNode> calls) throws AnalyzerException {
 335         while (true) {
 336             if (insn < 0 || insn >= n) {
 337                 throw new AnalyzerException(null,
 338                         "Execution can fall off end of the code");
 339             }
 340             if (subroutines[insn] != null) {
 341                 return;
 342             }
 343             subroutines[insn] = sub.copy();
 344             AbstractInsnNode node = insns.get(insn);
 345 
 346             // calls findSubroutine recursively on normal successors
 347             if (node instanceof JumpInsnNode) {
 348                 if (node.getOpcode() == JSR) {
 349                     // do not follow a JSR, it leads to another subroutine!
 350                     calls.add(node);
 351                 } else {
 352                     JumpInsnNode jnode = (JumpInsnNode) node;
 353                     findSubroutine(insns.indexOf(jnode.label), sub, calls);
 354                 }
 355             } else if (node instanceof TableSwitchInsnNode) {
 356                 TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node;
 357                 findSubroutine(insns.indexOf(tsnode.dflt), sub, calls);
 358                 for (int i = tsnode.labels.size() - 1; i >= 0; --i) {
 359                     LabelNode l = tsnode.labels.get(i);
 360                     findSubroutine(insns.indexOf(l), sub, calls);
 361                 }
 362             } else if (node instanceof LookupSwitchInsnNode) {
 363                 LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node;
 364                 findSubroutine(insns.indexOf(lsnode.dflt), sub, calls);
 365                 for (int i = lsnode.labels.size() - 1; i >= 0; --i) {
 366                     LabelNode l = lsnode.labels.get(i);
 367                     findSubroutine(insns.indexOf(l), sub, calls);
 368                 }
 369             }
 370 
 371             // calls findSubroutine recursively on exception handler successors
 372             List<TryCatchBlockNode> insnHandlers = handlers[insn];
 373             if (insnHandlers != null) {
 374                 for (int i = 0; i < insnHandlers.size(); ++i) {
 375                     TryCatchBlockNode tcb = insnHandlers.get(i);
 376                     findSubroutine(insns.indexOf(tcb.handler), sub, calls);
 377                 }
 378             }
 379 
 380             // if insn does not falls through to the next instruction, return.
 381             switch (node.getOpcode()) {
 382             case GOTO:
 383             case RET:
 384             case TABLESWITCH:
 385             case LOOKUPSWITCH:
 386             case IRETURN:
 387             case LRETURN:
 388             case FRETURN:
 389             case DRETURN:
 390             case ARETURN:
 391             case RETURN:
 392             case ATHROW:
 393                 return;
 394             }
 395             insn++;
 396         }
 397     }
 398 
 399     /**
 400      * Returns the symbolic stack frame for each instruction of the last
 401      * recently analyzed method.
 402      *
 403      * @return the symbolic state of the execution stack frame at each bytecode
 404      *         instruction of the method. The size of the returned array is
 405      *         equal to the number of instructions (and labels) of the method. A
 406      *         given frame is <tt>null</tt> if the corresponding instruction
 407      *         cannot be reached, or if an error occured during the analysis of
 408      *         the method.
 409      */
 410     public Frame<V>[] getFrames() {
 411         return frames;
 412     }
 413 
 414     /**
 415      * Returns the exception handlers for the given instruction.
 416      *
 417      * @param insn
 418      *            the index of an instruction of the last recently analyzed
 419      *            method.
 420      * @return a list of {@link TryCatchBlockNode} objects.
 421      */
 422     public List<TryCatchBlockNode> getHandlers(final int insn) {
 423         return handlers[insn];
 424     }
 425 
 426     /**
 427      * Initializes this analyzer. This method is called just before the
 428      * execution of control flow analysis loop in #analyze. The default
 429      * implementation of this method does nothing.
 430      *
 431      * @param owner
 432      *            the internal name of the class to which the method belongs.
 433      * @param m
 434      *            the method to be analyzed.
 435      * @throws AnalyzerException
 436      *             if a problem occurs.
 437      */
 438     protected void init(String owner, MethodNode m) throws AnalyzerException {
 439     }
 440 
 441     /**
 442      * Constructs a new frame with the given size.
 443      *
 444      * @param nLocals
 445      *            the maximum number of local variables of the frame.
 446      * @param nStack
 447      *            the maximum stack size of the frame.
 448      * @return the created frame.
 449      */
 450     protected Frame<V> newFrame(final int nLocals, final int nStack) {
 451         return new Frame<V>(nLocals, nStack);
 452     }
 453 
 454     /**
 455      * Constructs a new frame that is identical to the given frame.
 456      *
 457      * @param src
 458      *            a frame.
 459      * @return the created frame.
 460      */
 461     protected Frame<V> newFrame(final Frame<? extends V> src) {
 462         return new Frame<V>(src);
 463     }
 464 
 465     /**
 466      * Creates a control flow graph edge. The default implementation of this
 467      * method does nothing. It can be overriden in order to construct the
 468      * control flow graph of a method (this method is called by the
 469      * {@link #analyze analyze} method during its visit of the method's code).
 470      *
 471      * @param insn
 472      *            an instruction index.
 473      * @param successor
 474      *            index of a successor instruction.
 475      */
 476     protected void newControlFlowEdge(final int insn, final int successor) {
 477     }
 478 
 479     /**
 480      * Creates a control flow graph edge corresponding to an exception handler.
 481      * The default implementation of this method does nothing. It can be
 482      * overridden in order to construct the control flow graph of a method (this
 483      * method is called by the {@link #analyze analyze} method during its visit
 484      * of the method's code).
 485      *
 486      * @param insn
 487      *            an instruction index.
 488      * @param successor
 489      *            index of a successor instruction.
 490      * @return true if this edge must be considered in the data flow analysis
 491      *         performed by this analyzer, or false otherwise. The default
 492      *         implementation of this method always returns true.
 493      */
 494     protected boolean newControlFlowExceptionEdge(final int insn,
 495             final int successor) {
 496         return true;
 497     }
 498 
 499     /**
 500      * Creates a control flow graph edge corresponding to an exception handler.
 501      * The default implementation of this method delegates to
 502      * {@link #newControlFlowExceptionEdge(int, int)
 503      * newControlFlowExceptionEdge(int, int)}. It can be overridden in order to
 504      * construct the control flow graph of a method (this method is called by
 505      * the {@link #analyze analyze} method during its visit of the method's
 506      * code).
 507      *
 508      * @param insn
 509      *            an instruction index.
 510      * @param tcb
 511      *            TryCatchBlockNode corresponding to this edge.
 512      * @return true if this edge must be considered in the data flow analysis
 513      *         performed by this analyzer, or false otherwise. The default
 514      *         implementation of this method delegates to
 515      *         {@link #newControlFlowExceptionEdge(int, int)
 516      *         newControlFlowExceptionEdge(int, int)}.
 517      */
 518     protected boolean newControlFlowExceptionEdge(final int insn,
 519             final TryCatchBlockNode tcb) {
 520         return newControlFlowExceptionEdge(insn, insns.indexOf(tcb.handler));
 521     }
 522 
 523     // -------------------------------------------------------------------------
 524 
 525     private void merge(final int insn, final Frame<V> frame,
 526             final Subroutine subroutine) throws AnalyzerException {
 527         Frame<V> oldFrame = frames[insn];
 528         Subroutine oldSubroutine = subroutines[insn];
 529         boolean changes;
 530 
 531         if (oldFrame == null) {
 532             frames[insn] = newFrame(frame);
 533             changes = true;
 534         } else {
 535             changes = oldFrame.merge(frame, interpreter);
 536         }
 537 
 538         if (oldSubroutine == null) {
 539             if (subroutine != null) {
 540                 subroutines[insn] = subroutine.copy();
 541                 changes = true;
 542             }
 543         } else {
 544             if (subroutine != null) {
 545                 changes |= oldSubroutine.merge(subroutine);
 546             }
 547         }
 548         if (changes && !queued[insn]) {
 549             queued[insn] = true;
 550             queue[top++] = insn;
 551         }
 552     }
 553 
 554     private void merge(final int insn, final Frame<V> beforeJSR,
 555             final Frame<V> afterRET, final Subroutine subroutineBeforeJSR,
 556             final boolean[] access) throws AnalyzerException {
 557         Frame<V> oldFrame = frames[insn];
 558         Subroutine oldSubroutine = subroutines[insn];
 559         boolean changes;
 560 
 561         afterRET.merge(beforeJSR, access);
 562 
 563         if (oldFrame == null) {
 564             frames[insn] = newFrame(afterRET);
 565             changes = true;
 566         } else {
 567             changes = oldFrame.merge(afterRET, interpreter);
 568         }
 569 
 570         if (oldSubroutine != null && subroutineBeforeJSR != null) {
 571             changes |= oldSubroutine.merge(subroutineBeforeJSR);
 572         }
 573         if (changes && !queued[insn]) {
 574             queued[insn] = true;
 575             queue[top++] = insn;
 576         }
 577     }
 578 }