path: root/tools/external/asm/org/objectweb/asm/tree/analysis/Analyzer.java

/***
 * ASM: a very small and fast Java bytecode manipulation framework
 * Copyright (c) 2000-2005 INRIA, France Telecom
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the copyright holders nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.objectweb.asm.tree.analysis;

import java.util.ArrayList;
import java.util.List;

import org.objectweb.asm.Opcodes;
import org.objectweb.asm.Label;
import org.objectweb.asm.Type;
import org.objectweb.asm.tree.AbstractInsnNode;
import org.objectweb.asm.tree.IincInsnNode;
import org.objectweb.asm.tree.JumpInsnNode;
import org.objectweb.asm.tree.LabelNode;
import org.objectweb.asm.tree.LookupSwitchInsnNode;
import org.objectweb.asm.tree.MethodNode;
import org.objectweb.asm.tree.TableSwitchInsnNode;
import org.objectweb.asm.tree.TryCatchBlockNode;
import org.objectweb.asm.tree.VarInsnNode;

/**
 * A semantic bytecode analyzer.
 * 
 * @author Eric Bruneton
 */
public class Analyzer implements Opcodes {

    private Interpreter interpreter;

    private int n;

    private IntMap indexes;

    private List[] handlers;

    private Frame[] frames;

    private Subroutine[] subroutines;

    private boolean[] queued;

    private int[] queue;

    private int top;

    private boolean jsr;

    /**
     * Constructs a new {@link Analyzer}.
     * 
     * @param interpreter the interpreter to be used to symbolically interpret
     *        the bytecode instructions.
     */
    public Analyzer(final Interpreter interpreter) {
        this.interpreter = interpreter;
    }

    /**
     * Analyzes the given method.
     * 
     * @param owner the internal name of the class to which the method belongs.
     * @param m the method to be analyzed.
     * @return the symbolic state of the execution stack frame at each bytecode
     *         instruction of the method. The size of the returned array is
     *         equal to the number of instructions (and labels) of the method. A
     *         given frame is <tt>null</tt> if and only if the corresponding
     *         instruction cannot be reached (dead code).
     * @throws AnalyzerException if a problem occurs during the analysis.
     */
    public Frame[] analyze(final String owner, final MethodNode m)
            throws AnalyzerException
    {
        n = m.instructions.size();
        indexes = new IntMap(2 * n);
        handlers = new List[n];
        frames = new Frame[n];
        subroutines = new Subroutine[n];
        queued = new boolean[n];
        queue = new int[n];
        top = 0;

        // computes instruction indexes
        for (int i = 0; i < n; ++i) {
            Object insn = m.instructions.get(i);
            if (insn instanceof LabelNode) {
                insn = ((LabelNode) insn).label;
            }
            indexes.put(insn, i);
        }

        // computes exception handlers for each instruction
        for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
            TryCatchBlockNode tcb = (TryCatchBlockNode) m.tryCatchBlocks.get(i);
            int begin = indexes.get(tcb.start);
            int end = indexes.get(tcb.end);
            for (int j = begin; j < end; ++j) {
                List insnHandlers = handlers[j];
                if (insnHandlers == null) {
                    insnHandlers = new ArrayList();
                    handlers[j] = insnHandlers;
                }
                insnHandlers.add(tcb);
            }
        }

        // initializes the data structures for the control flow analysis
        // algorithm
        Frame current = newFrame(m.maxLocals, m.maxStack);
        Frame handler = newFrame(m.maxLocals, m.maxStack);
        Type[] args = Type.getArgumentTypes(m.desc);
        int local = 0;
        if ((m.access & ACC_STATIC) == 0) {
            Type ctype = Type.getType("L" + owner + ";");
            current.setLocal(local++, interpreter.newValue(ctype));
        }
        for (int i = 0; i < args.length; ++i) {
            current.setLocal(local++, interpreter.newValue(args[i]));
            if (args[i].getSize() == 2) {
                current.setLocal(local++, interpreter.newValue(null));
            }
        }
        while (local < m.maxLocals) {
            current.setLocal(local++, interpreter.newValue(null));
        }
        merge(0, current, null);

        // control flow analysis
        while (top > 0) {
            int insn = queue[--top];
            Frame f = frames[insn];
            Subroutine subroutine = subroutines[insn];
            queued[insn] = false;

            try {
                Object o = m.instructions.get(insn);
                jsr = false;

                if (o instanceof LabelNode) {
                    merge(insn + 1, f, subroutine);
                } else {
                    AbstractInsnNode insnNode = (AbstractInsnNode) o;
                    int insnOpcode = insnNode.getOpcode();

                    current.init(f).execute(insnNode, interpreter);
                    subroutine = subroutine == null ? null : subroutine.copy();

                    if (insnNode instanceof JumpInsnNode) {
                        JumpInsnNode j = (JumpInsnNode) insnNode;
                        if (insnOpcode != GOTO && insnOpcode != JSR) {
                            merge(insn + 1, current, subroutine);
                        }
                        if (insnOpcode == JSR) {
                            jsr = true;
                            merge(indexes.get(j.label),
                                    current,
                                    new Subroutine(j.label, m.maxLocals, j));
                        } else {
                            merge(indexes.get(j.label), current, subroutine);
                        }
                    } else if (insnNode instanceof LookupSwitchInsnNode) {
                        LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode;
                        merge(indexes.get(lsi.dflt), current, subroutine);
                        for (int j = 0; j < lsi.labels.size(); ++j) {
                            Label label = (Label) lsi.labels.get(j);
                            merge(indexes.get(label), current, subroutine);
                        }
                    } else if (insnNode instanceof TableSwitchInsnNode) {
                        TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode;
                        merge(indexes.get(tsi.dflt), current, subroutine);
                        for (int j = 0; j < tsi.labels.size(); ++j) {
                            Label label = (Label) tsi.labels.get(j);
                            merge(indexes.get(label), current, subroutine);
                        }
                    } else if (insnOpcode == RET) {
                        if (subroutine == null) {
                            throw new AnalyzerException("RET instruction outside of a sub routine");
                        }
                        for (int i = 0; i < subroutine.callers.size(); ++i) {
                            int caller = indexes.get(subroutine.callers.get(i));
                            merge(caller + 1,
                                    frames[caller],
                                    current,
                                    subroutines[caller],
                                    subroutine.access);
                        }
                    } else if (insnOpcode != ATHROW
                            && (insnOpcode < IRETURN || insnOpcode > RETURN))
                    {
                        if (subroutine != null) {
                            if (insnNode instanceof VarInsnNode) {
                                int var = ((VarInsnNode) insnNode).var;
                                subroutine.access[var] = true;
                                if (insnOpcode == LLOAD || insnOpcode == DLOAD
                                        || insnOpcode == LSTORE
                                        || insnOpcode == DSTORE)
                                {
                                    subroutine.access[var + 1] = true;
                                }
                            } else if (insnNode instanceof IincInsnNode) {
                                int var = ((IincInsnNode) insnNode).var;
                                subroutine.access[var] = true;
                            }
                        }
                        merge(insn + 1, current, subroutine);
                    }
                }

                List insnHandlers = handlers[insn];
                if (insnHandlers != null) {
                    for (int i = 0; i < insnHandlers.size(); ++i) {
                        TryCatchBlockNode tcb = (TryCatchBlockNode) insnHandlers.get(i);
                        Type type;
                        if (tcb.type == null) {
                            type = Type.getType("Ljava/lang/Throwable;");
                        } else {
                            type = Type.getType("L" + tcb.type + ";");
                        }
                        handler.init(f);
                        handler.clearStack();
                        handler.push(interpreter.newValue(type));
                        merge(indexes.get(tcb.handler), handler, subroutine);
                    }
                }
            } catch (AnalyzerException e) {
                throw new AnalyzerException("Error at instruction " + insn
                        + ": " + e.getMessage(), e);
            } catch(Exception e) {
                throw new AnalyzerException("Error at instruction " + insn
                        + ": " + e.getMessage(), e);
            }
        }

        return frames;
    }

    /**
     * Returns the symbolic stack frame for each instruction of the last
     * recently analyzed method.
     * 
     * @return the symbolic state of the execution stack frame at each bytecode
     *         instruction of the method. The size of the returned array is
     *         equal to the number of instructions (and labels) of the method. A
     *         given frame is <tt>null</tt> if the corresponding instruction
     *         cannot be reached, or if an error occured during the analysis of
     *         the method.
     */
    public Frame[] getFrames() {
        return frames;
    }

    /**
     * Returns the index of the given instruction.
     * 
     * @param insn a {@link Label} or {@link AbstractInsnNode} of the last
     *        recently analyzed method.
     * @return the index of the given instruction of the last recently analyzed
     *         method.
     */
    public int getIndex(final Object insn) {
        return indexes.get(insn);
    }

    /**
     * Returns the exception handlers for the given instruction.
     * 
     * @param insn the index of an instruction of the last recently analyzed
     *        method.
     * @return a list of {@link TryCatchBlockNode} objects.
     */
    public List getHandlers(final int insn) {
        return handlers[insn];
    }

    /**
     * Constructs a new frame with the given size.
     * 
     * @param nLocals the maximum number of local variables of the frame.
     * @param nStack the maximum stack size of the frame.
     * @return the created frame.
     */
    protected Frame newFrame(final int nLocals, final int nStack) {
        return new Frame(nLocals, nStack);
    }

    /**
     * Constructs a new frame that is identical to the given frame.
     * 
     * @param src a frame.
     * @return the created frame.
     */
    protected Frame newFrame(final Frame src) {
        return new Frame(src);
    }

    /**
     * Creates a control flow graph edge. The default implementation of this
     * method does nothing. It can be overriden in order to construct the
     * control flow graph of a method (this method is called by the
     * {@link #analyze analyze} method during its visit of the method's code).
     * 
     * @param frame the frame corresponding to an instruction.
     * @param successor the frame corresponding to a successor instruction.
     */
    protected void newControlFlowEdge(final Frame frame, final Frame successor)
    {
    }

    // -------------------------------------------------------------------------

    private void merge(
        final int insn,
        final Frame frame,
        final Subroutine subroutine) throws AnalyzerException
    {
        if (insn > n - 1) {
            throw new AnalyzerException("Execution can fall off end of the code");
        }

        Frame oldFrame = frames[insn];
        Subroutine oldSubroutine = subroutines[insn];
        boolean changes = false;

        if (oldFrame == null) {
            frames[insn] = newFrame(frame);
            changes = true;
        } else {
            changes |= oldFrame.merge(frame, interpreter);
        }

        newControlFlowEdge(frame, oldFrame);

        if (oldSubroutine == null) {
            if (subroutine != null) {
                subroutines[insn] = subroutine.copy();
                changes = true;
            }
        } else {
            if (subroutine != null) {
                changes |= oldSubroutine.merge(subroutine, !jsr);
            }
        }
        if (changes && !queued[insn]) {
            queued[insn] = true;
            queue[top++] = insn;
        }
    }

    private void merge(
        final int insn,
        final Frame beforeJSR,
        final Frame afterRET,
        final Subroutine subroutineBeforeJSR,
        final boolean[] access) throws AnalyzerException
    {
        if (insn > n - 1) {
            throw new AnalyzerException("Execution can fall off end of the code");
        }

        Frame oldFrame = frames[insn];
        Subroutine oldSubroutine = subroutines[insn];
        boolean changes = false;

        afterRET.merge(beforeJSR, access);

        if (oldFrame == null) {
            frames[insn] = newFrame(afterRET);
            changes = true;
        } else {
            changes |= oldFrame.merge(afterRET, access);
        }

        newControlFlowEdge(afterRET, oldFrame);

        if (oldSubroutine == null) {
            if (subroutineBeforeJSR != null) {
                subroutines[insn] = subroutineBeforeJSR.copy();
                changes = true;
            }
        } else {
            if (subroutineBeforeJSR != null) {
                changes |= oldSubroutine.merge(subroutineBeforeJSR, !jsr);
            }
        }
        if (changes && !queued[insn]) {
            queued[insn] = true;
            queue[top++] = insn;
        }
    }
}