src/org/objectweb/asm/tree/analysis/Analyzer.java

/***
 * 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 org.objectweb.asm.tree.analysis;

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

import org.objectweb.asm.Constants;
import org.objectweb.asm.Label;
import org.objectweb.asm.Type;
import org.objectweb.asm.tree.AbstractInsnNode;
import org.objectweb.asm.tree.ClassNode;
import org.objectweb.asm.tree.IincInsnNode;
import org.objectweb.asm.tree.JumpInsnNode;
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 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;

  /**
   * 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).  
   */
  
  public Frame[] analyze (final ClassNode c, final MethodNode m) {
    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);
        
        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) {
              subroutine = new Subroutine(j.label, m.maxLocals, j);
            }
            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 RuntimeException(
                "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, 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 RuntimeException(
          "Error at instruction " + insn + ": " + e.getMessage());
      }
    }

    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) 
  {
    if (insn > n - 1) {
      throw new RuntimeException("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);
      }

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

  private void merge (
    final int insn, 
    final Frame beforeJSR,
    final Frame afterRET,
    final boolean[] access)
  {
    if (insn > n - 1) {
      throw new RuntimeException("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 (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) {
      if (subroutine.start != start) {
        throw new RuntimeException("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;
    }
  }
}