/***
* ASM: a very small and fast Java bytecode manipulation framework
* Copyright (c) 2000,2002,2003 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 oracle.toplink.libraries.asm.tree.analysis;
import java.util.ArrayList;
import java.util.List;
import oracle.toplink.libraries.asm.Constants;
import oracle.toplink.libraries.asm.Label;
import oracle.toplink.libraries.asm.Type;
import oracle.toplink.libraries.asm.tree.AbstractInsnNode;
import oracle.toplink.libraries.asm.tree.ClassNode;
import oracle.toplink.libraries.asm.tree.IincInsnNode;
import oracle.toplink.libraries.asm.tree.JumpInsnNode;
import oracle.toplink.libraries.asm.tree.LookupSwitchInsnNode;
import oracle.toplink.libraries.asm.tree.MethodNode;
import oracle.toplink.libraries.asm.tree.TableSwitchInsnNode;
import oracle.toplink.libraries.asm.tree.TryCatchBlockNode;
import oracle.toplink.libraries.asm.tree.VarInsnNode;
/**
* A semantic bytecode analyzer.
*
* @author Eric Bruneton
*/
public class Analyzer implements Constants {
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 c 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 ClassNode c, 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) {
indexes.put(m.instructions.get(i), 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" + c.name + ";");
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 Label) {
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");
} else {
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 (Exception e) {
throw new AnalyzerException(
"Error at instruction " + insn + ": " + e.getMessage());
}
}
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");
} else {
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");
} else {
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;
}
}
}
private static class IntMap {
private int size;
private Object[] keys;
private int[] values;
private IntMap (final int size) {
this.size = size;
this.keys = new Object[size];
this.values = new int[size];
}
public int get (final Object key) {
int n = size;
int i = (key.hashCode() & 0x7FFFFFFF)%n;
while (keys[i] != key) {
i = (i+1)%n;
}
return values[i];
}
public void put (final Object key, final int value) {
int n = size;
int i = (key.hashCode() & 0x7FFFFFFF)%n;
while (keys[i] != null) {
i = (i+1)%n;
}
keys[i] = key;
values[i] = value;
}
}
private static class Subroutine {
Label start;
boolean[] access;
List callers;
private Subroutine () {
}
public Subroutine (final Label start, final int maxLocals, final JumpInsnNode caller) {
this.start = start;
this.access = new boolean[maxLocals];
this.callers = new ArrayList();
callers.add(caller);
}
public Subroutine copy () {
Subroutine result = new Subroutine();
result.start = start;
result.access = new boolean[access.length];
System.arraycopy(access, 0, result.access, 0, access.length);
result.callers = new ArrayList(callers);
return result;
}
public boolean merge (final Subroutine subroutine, boolean checkOverlap) throws AnalyzerException {
if (checkOverlap && subroutine.start != start) {
throw new AnalyzerException("Overlapping sub routines");
}
boolean changes = false;
for (int i = 0; i < access.length; ++i) {
if (subroutine.access[i] && !access[i]) {
access[i] = true;
changes = true;
}
}
for (int i = 0; i < subroutine.callers.size(); ++i) {
Object caller = subroutine.callers.get(i);
if (!callers.contains(caller)) {
callers.add(caller);
changes = true;
}
}
return changes;
}
}
}
|
