path: root/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/NullableMethodAnalysis.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;

import com.intellij.codeInspection.bytecodeAnalysis.asm.AnalyzerExt;
import com.intellij.codeInspection.bytecodeAnalysis.asm.InterpreterExt;
import com.intellij.codeInspection.bytecodeAnalysis.asm.LiteAnalyzerExt;
import org.jetbrains.org.objectweb.asm.Opcodes;
import org.jetbrains.org.objectweb.asm.Type;
import org.jetbrains.org.objectweb.asm.tree.*;
import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException;
import org.jetbrains.org.objectweb.asm.tree.analysis.BasicInterpreter;
import org.jetbrains.org.objectweb.asm.tree.analysis.BasicValue;
import org.jetbrains.org.objectweb.asm.tree.analysis.Frame;

import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import static com.intellij.codeInspection.bytecodeAnalysis.NullableMethodAnalysisData.*;

interface NullableMethodAnalysisData {
  Type NullType = Type.getObjectType("null");
  Type ThisType = Type.getObjectType("this");
  Type CallType = Type.getObjectType("/Call");

  final class LabeledNull extends BasicValue {
    final int origins;

    public LabeledNull(int origins) {
      super(NullType);
      this.origins = origins;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      LabeledNull that = (LabeledNull)o;
      return origins == that.origins;
    }

    @Override
    public int hashCode() {
      return origins;
    }
  }

  final class Calls extends BasicValue {
    final int mergedLabels;

    public Calls(int mergedLabels) {
      super(CallType);
      this.mergedLabels = mergedLabels;
    }

    @Override
    public boolean equals(Object o) {
      if (o == null || getClass() != o.getClass()) return false;
      Calls calls = (Calls)o;
      return mergedLabels == calls.mergedLabels;
    }

    @Override
    public int hashCode() {
      return mergedLabels;
    }
  }

  final class Constraint {
    final static Constraint EMPTY = new Constraint(0, 0);

    final int calls;
    final int nulls;

    public Constraint(int calls, int nulls) {
      this.calls = calls;
      this.nulls = nulls;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      Constraint that = (Constraint)o;

      if (calls != that.calls) return false;
      if (nulls != that.nulls) return false;

      return true;
    }

    @Override
    public int hashCode() {
      int result = calls;
      result = 31 * result + nulls;
      return result;
    }
  }

  BasicValue ThisValue = new BasicValue(ThisType);
}

class NullableMethodAnalysis {

  static Result<Key, Value> FinalNull = new Final<Key, Value>(Value.Null);
  static Result<Key, Value> FinalBot = new Final<Key, Value>(Value.Bot);
  static BasicValue lNull = new LabeledNull(0);

  static Result<Key, Value> analyze(MethodNode methodNode, boolean[] origins, boolean jsr) throws AnalyzerException {
    InsnList insns = methodNode.instructions;
    Constraint[] data = new Constraint[insns.size()];
    int[] originsMapping = mapOrigins(origins);

    NullableMethodInterpreter interpreter = new NullableMethodInterpreter(insns, origins, originsMapping);
    Frame<BasicValue>[] frames =
      jsr ?
      new AnalyzerExt<BasicValue, Constraint, NullableMethodInterpreter>(interpreter, data, Constraint.EMPTY).analyze("this", methodNode) :
      new LiteAnalyzerExt<BasicValue, Constraint, NullableMethodInterpreter>(interpreter, data, Constraint.EMPTY).analyze("this", methodNode);

    BasicValue result = BasicValue.REFERENCE_VALUE;
    for (int i = 0; i < frames.length; i++) {
      Frame<BasicValue> frame = frames[i];
      if (frame != null && insns.get(i).getOpcode() == Opcodes.ARETURN) {
        BasicValue stackTop = frame.pop();
        result = combine(result, stackTop, data[i]);
      }
    }
    if (result instanceof LabeledNull) {
      return FinalNull;
    }
    if (result instanceof Calls) {
      Calls calls = ((Calls)result);
      int mergedMappedLabels = calls.mergedLabels;
      if (mergedMappedLabels != 0) {
        Set<Product<Key, Value>> sum = new HashSet<Product<Key, Value>>();
        Key[] createdKeys = interpreter.keys;
        for (int origin = 0; origin < originsMapping.length; origin++) {
          int mappedOrigin = originsMapping[origin];
          Key createdKey = createdKeys[origin];
          if (createdKey != null && (mergedMappedLabels & (1 << mappedOrigin)) != 0) {
            sum.add(new Product<Key, Value>(Value.Null, Collections.singleton(createdKey)));
          }
        }
        if (!sum.isEmpty()) {
          return new Pending<Key, Value>(sum);
        }
      }
    }
    return FinalBot;
  }

  private static int[] mapOrigins(boolean[] origins) {
    int[] originsMapping = new int[origins.length];
    int mapped = 0;
    for (int i = 0; i < origins.length; i++) {
      originsMapping[i] = origins[i] ? mapped++ : -1;
    }
    return originsMapping;
  }

  static BasicValue combine(BasicValue v1, BasicValue v2, Constraint constraint) {
    if (v1 instanceof LabeledNull) {
      return lNull;
    }
    else if (v2 instanceof LabeledNull) {
      int v2Origins = ((LabeledNull)v2).origins;
      int constraintOrigins = constraint.nulls;
      int intersect = v2Origins & constraintOrigins;
      return intersect == v2Origins ? v1 : lNull;
    }
    else if (v1 instanceof Calls) {
      if (v2 instanceof Calls) {
        Calls calls1 = (Calls)v1;
        Calls calls2 = (Calls)v2;
        int labels2 = calls2.mergedLabels;
        int aliveLabels2 = labels2 - (labels2 & constraint.calls);
        return new Calls(calls1.mergedLabels | aliveLabels2);
      } else {
        return v1;
      }
    }
    else if (v2 instanceof Calls) {
      Calls calls2 = (Calls)v2;
      int labels2 = calls2.mergedLabels;
      int aliveLabels2 = labels2 - (labels2 & constraint.calls);
      return new Calls(aliveLabels2);
    }
    return BasicValue.REFERENCE_VALUE;
  }
}

class NullableMethodInterpreter extends BasicInterpreter implements InterpreterExt<Constraint> {
  final InsnList insns;
  final boolean[] origins;
  private final int[] originsMapping;
  final Key[] keys;

  Constraint constraint = null;
  int delta = 0;
  int nullsDelta = 0;
  int notNullInsn = -1;
  int notNullCall = 0;
  int notNullNull = 0;

  NullableMethodInterpreter(InsnList insns, boolean[] origins, int[] originsMapping) {
    this.insns = insns;
    this.origins = origins;
    this.originsMapping = originsMapping;
    keys = new Key[originsMapping.length];
  }

  @Override
  public BasicValue newValue(Type type) {
    return ThisType.equals(type) ? ThisValue : super.newValue(type);
  }

  @Override
  public BasicValue newOperation(AbstractInsnNode insn) throws AnalyzerException {
    if (insn.getOpcode() == Opcodes.ACONST_NULL) {
      int insnIndex = insns.indexOf(insn);
      if (origins[insnIndex]) {
        return new LabeledNull(1 << originsMapping[insnIndex]);
      }
    }
    return super.newOperation(insn);
  }

  @Override
  public BasicValue unaryOperation(AbstractInsnNode insn, BasicValue value) throws AnalyzerException {
    switch (insn.getOpcode()) {
      case GETFIELD:
      case ARRAYLENGTH:
      case MONITORENTER:
        if (value instanceof Calls) {
          delta = ((Calls)value).mergedLabels;
        }
        break;
      case IFNULL:
        if (value instanceof Calls) {
          notNullInsn = insns.indexOf(insn) + 1;
          notNullCall = ((Calls)value).mergedLabels;
        }
        else if (value instanceof LabeledNull) {
          notNullInsn = insns.indexOf(insn) + 1;
          notNullNull = ((LabeledNull)value).origins;
        }
        break;
      case IFNONNULL:
        if (value instanceof Calls) {
          notNullInsn = insns.indexOf(((JumpInsnNode)insn).label);
          notNullCall = ((Calls)value).mergedLabels;
        }
        else if (value instanceof LabeledNull) {
          notNullInsn = insns.indexOf(((JumpInsnNode)insn).label);
          notNullNull = ((LabeledNull)value).origins;
        }
        break;
      default:

    }
    return super.unaryOperation(insn, value);
  }

  @Override
  public BasicValue binaryOperation(AbstractInsnNode insn, BasicValue value1, BasicValue value2) throws AnalyzerException {
    switch (insn.getOpcode()) {
      case PUTFIELD:
      case IALOAD:
      case LALOAD:
      case FALOAD:
      case DALOAD:
      case AALOAD:
      case BALOAD:
      case CALOAD:
      case SALOAD:
        if (value1 instanceof Calls) {
          delta = ((Calls)value1).mergedLabels;
        }
        if (value1 instanceof LabeledNull){
          nullsDelta = ((LabeledNull)value1).origins;
        }
        break;
      default:
    }
    return super.binaryOperation(insn, value1, value2);
  }

  @Override
  public BasicValue ternaryOperation(AbstractInsnNode insn, BasicValue value1, BasicValue value2, BasicValue value3)
    throws AnalyzerException {
    if (value1 instanceof Calls) {
      delta = ((Calls)value1).mergedLabels;
    }
    if (value1 instanceof LabeledNull){
      nullsDelta = ((LabeledNull)value1).origins;
    }
    return null;
  }

  @Override
  public BasicValue naryOperation(AbstractInsnNode insn, List<? extends BasicValue> values) throws AnalyzerException {
    int opCode = insn.getOpcode();
    switch (opCode) {
      case INVOKESPECIAL:
      case INVOKEINTERFACE:
      case INVOKEVIRTUAL:
        BasicValue receiver = values.get(0);
        if (receiver instanceof Calls) {
          delta = ((Calls)receiver).mergedLabels;
        }
        if (receiver instanceof LabeledNull){
          nullsDelta = ((LabeledNull)receiver).origins;
        }
        break;
      default:
    }

    switch (opCode) {
      case INVOKESTATIC:
      case INVOKESPECIAL:
      case INVOKEVIRTUAL:
        int insnIndex = insns.indexOf(insn);
        if (origins[insnIndex]) {
          boolean stable = (opCode == INVOKESTATIC) ||
                           (opCode == INVOKESPECIAL) ||
                           (values.get(0) == ThisValue);
          MethodInsnNode mNode = ((MethodInsnNode)insn);
          Method method = new Method(mNode.owner, mNode.name, mNode.desc);
          int label = 1 << originsMapping[insnIndex];
          if (keys[insnIndex] == null) {
            keys[insnIndex] = new Key(method, Direction.NullableOut, stable);
          }
          return new Calls(label);
        }
        break;
      default:
    }
    return super.naryOperation(insn, values);
  }

  @Override
  public BasicValue merge(BasicValue v1, BasicValue v2) {
    if (v1 instanceof LabeledNull) {
      if (v2 instanceof LabeledNull) {
        return new LabeledNull(((LabeledNull)v1).origins | ((LabeledNull)v2).origins);
      }
      else {
        return v1;
      }
    }
    else if (v2 instanceof LabeledNull) {
      return v2;
    }
    else if (v1 instanceof Calls) {
      if (v2 instanceof Calls) {
        Calls calls1 = (Calls)v1;
        Calls calls2 = (Calls)v2;
        return new Calls(calls1.mergedLabels | calls2.mergedLabels);
      }
      else {
        return v1;
      }
    }
    else if (v2 instanceof Calls) {
      return v2;
    }
    return super.merge(v1, v2);
  }

  // ---------- InterpreterExt<Constraint> --------------

  @Override
  public void init(Constraint previous) {
    constraint = previous;
    delta = 0;
    nullsDelta = 0;

    notNullInsn = -1;
    notNullCall = 0;
    notNullNull = 0;
  }

  @Override
  public Constraint getAfterData(int insn) {
    Constraint afterData = mkAfterData();
    if (notNullInsn == insn) {
      return new Constraint(afterData.calls | notNullCall, afterData.nulls | notNullNull);
    }
    return afterData;
  }

  private Constraint mkAfterData() {
    if (delta == 0 && nullsDelta == 0 && notNullInsn == -1) {
      return constraint;
    }
    return new Constraint(constraint.calls | delta, constraint.nulls | nullsDelta);
  }

  @Override
  public Constraint merge(Constraint data1, Constraint data2) {
    if (data1.equals(data2)) {
      return data1;
    } else {
      return new Constraint(data1.calls | data2.calls, data1.nulls | data2.nulls);
    }
  }
}