java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/OriginsAnalysis.java

/*
 * Copyright 2000-2014 JetBrains s.r.o.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.intellij.codeInspection.bytecodeAnalysis.asm;

import gnu.trove.TIntArrayList;
import org.jetbrains.annotations.Nullable;
import org.jetbrains.org.objectweb.asm.Opcodes;
import org.jetbrains.org.objectweb.asm.tree.AbstractInsnNode;
import org.jetbrains.org.objectweb.asm.tree.InsnList;
import org.jetbrains.org.objectweb.asm.tree.analysis.*;

import java.util.HashSet;
import java.util.LinkedList;

/**
 * @author lambdamix
 */
public class OriginsAnalysis {

  private static SourceInterpreter ourInterpreter = new SourceInterpreter() {
    @Override
    public SourceValue copyOperation(AbstractInsnNode insn, SourceValue value) {
      return value;
    }
  };

  private static class PreValue extends SourceValue {
    final boolean local;
    final int slot;

    public PreValue(boolean local, int slot, int size) {
      super(size);
      this.local = local;
      this.slot = slot;
    }
  }

  private static class Location {
    final boolean local;
    final int slot;

    Location(boolean local, int slot) {
      this.local = local;
      this.slot = slot;
    }
  }

  private static class InsnLocation extends Location {
    final int insnIndex;

    private InsnLocation(boolean local, int insnIndex, int slot) {
      super(local, slot);
      this.insnIndex = insnIndex;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null) return false;
      InsnLocation insnLocation = (InsnLocation)o;
      if (local != insnLocation.local) return false;
      if (insnIndex != insnLocation.insnIndex) return false;
      if (slot != insnLocation.slot) return false;
      return true;
    }

    @Override
    public int hashCode() {
      // +1 is to avoid collisions
      int result = 31 * insnIndex + slot + 1;
      return local ? result : -result;
    }
  }

  /**
   *
   * @param frames fixpoint of frames
   * @param instructions method instructions
   * @param graph method control flow graph
   * @return array, array[i] == true means that the result of a method execution may originate at an i-th instruction
   * @throws AnalyzerException
   */
  public static boolean[] resultOrigins(Frame<Value>[] frames, InsnList instructions, ControlFlowGraph graph) throws AnalyzerException {

    TIntArrayList[] backTransitions = new TIntArrayList[instructions.size()];
    for (int i = 0; i < backTransitions.length; i++) {
      backTransitions[i] = new TIntArrayList();
    }
    LinkedList<InsnLocation> queue = new LinkedList<InsnLocation>();
    HashSet<InsnLocation> queued = new HashSet<InsnLocation>();
    for (int from = 0; from < instructions.size(); from++) {
      for (int to : graph.transitions[from]) {
        TIntArrayList froms = backTransitions[to];
        froms.add(from);
        int opcode = instructions.get(to).getOpcode();
        if (opcode >= Opcodes.IRETURN && opcode <= Opcodes.ARETURN) {
          InsnLocation sourceLoc = new InsnLocation(false, from, frames[to].getStackSize() - 1);
          if (queued.add(sourceLoc)) {
            queue.push(sourceLoc);
          }
        }
      }
    }

    boolean[] result = new boolean[instructions.size()];

    while (!queue.isEmpty()) {
      InsnLocation resultLocation = queue.pop();

      int insnIndex = resultLocation.insnIndex;
      AbstractInsnNode insn = instructions.get(insnIndex);
      int opcode = insn.getOpcode();
      Location preLocation = previousLocation(frames[insnIndex], resultLocation, insn);
      if (preLocation == null) {
        if (opcode != Opcodes.INVOKEINTERFACE && opcode != Opcodes.GETFIELD && !(opcode >= Opcodes.IALOAD && opcode <= Opcodes.SALOAD)) {
          result[insnIndex] = true;
        }
      } else {
        TIntArrayList froms = backTransitions[insnIndex];
        for (int i = 0; i < froms.size(); i++) {
          InsnLocation preILoc = new InsnLocation(preLocation.local, froms.getQuick(i), preLocation.slot);
          if (queued.add(preILoc)) {
            queue.push(preILoc);
          }
        }
      }
    }

    return result;
  }

  /**
   *
   * @param frame a start frame with an interesting value
   * @param location location of an interesting value *after* execution of an instruction
   * @param insn an executed instruction
   * @return location of an interesting value *before* execution of an instruction (in the past) or null if it is not traceable
   * @throws AnalyzerException
   */
  @Nullable
  private static Location previousLocation(Frame<Value> frame, Location location, AbstractInsnNode insn) throws AnalyzerException {
    int insnType = insn.getType();
    if (insnType == AbstractInsnNode.LABEL || insnType == AbstractInsnNode.LINE || insnType == AbstractInsnNode.FRAME) {
      return location;
    }
    int opCode = insn.getOpcode();
    if (location.local && !((opCode >= Opcodes.ISTORE && opCode <= Opcodes.ASTORE) || opCode == Opcodes.IINC)) {
      return location;
    }
    Frame<SourceValue> preFrame = makePreFrame(frame);
    preFrame.execute(insn, ourInterpreter);
    if (location.local) {
      SourceValue preVal = preFrame.getLocal(location.slot);
      if (preVal instanceof PreValue) {
        PreValue val = (PreValue)preVal;
        return new Location(val.local, val.slot);
      }
    } else {
      SourceValue preVal = preFrame.getStack(location.slot);
      if (preVal instanceof PreValue) {
        PreValue val = (PreValue)preVal;
        return new Location(val.local, val.slot);
      }
    }
    return null;
  }

  private static Frame<SourceValue> makePreFrame(Frame<Value> frame) {
    Frame<SourceValue> preFrame = new Frame<SourceValue>(frame.getLocals(), frame.getMaxStackSize());
    for (int i = 0; i < frame.getLocals(); i++) {
      preFrame.setLocal(i, new PreValue(true, i, frame.getLocal(i).getSize()));
    }
    for (int i = 0; i < frame.getStackSize(); i++) {
      preFrame.push(new PreValue(false, i, frame.getStack(i).getSize()));
    }
    return preFrame;
  }
}