1 files changed, 193 insertions, 0 deletions
diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/OriginsAnalysis.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/OriginsAnalysis.java
new file mode 100644
index 000000000000..e154bf847730
--- /dev/null
+++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/OriginsAnalysis.java
@@ -0,0 +1,193 @@
+/*
+ * 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;
+  }
+}
+
+