diff options
Diffstat (limited to 'java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java')
-rw-r--r-- | java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java | 472 |
1 files changed, 421 insertions, 51 deletions
diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java index 625eb8eed977..a7c25782d48b 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java @@ -15,6 +15,10 @@ */ package com.intellij.codeInspection.bytecodeAnalysis; +import com.intellij.codeInspection.bytecodeAnalysis.asm.ASMUtils; +import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph.Edge; +import com.intellij.codeInspection.bytecodeAnalysis.asm.RichControlFlow; +import org.jetbrains.annotations.NotNull; import org.jetbrains.org.objectweb.asm.Type; import org.jetbrains.org.objectweb.asm.tree.AbstractInsnNode; import org.jetbrains.org.objectweb.asm.tree.JumpInsnNode; @@ -25,7 +29,9 @@ 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.*; +import java.util.HashSet; +import java.util.List; +import java.util.Set; import static com.intellij.codeInspection.bytecodeAnalysis.AbstractValues.InstanceOfCheckValue; import static com.intellij.codeInspection.bytecodeAnalysis.AbstractValues.ParamValue; @@ -101,6 +107,18 @@ abstract class PResults { } } + static PResult combineNullable(PResult r1, PResult r2) throws AnalyzerException { + if (Identity == r1) return r2; + if (Identity == r2) return r1; + if (Return == r1) return r2; + if (Return == r2) return r1; + if (NPE == r1) return NPE; + if (NPE == r2) return NPE; + ConditionalNPE cnpe1 = (ConditionalNPE) r1; + ConditionalNPE cnpe2 = (ConditionalNPE) r2; + return new ConditionalNPE(join(cnpe1.sop, cnpe2.sop)); + } + static PResult join(PResult r1, PResult r2) throws AnalyzerException { if (Identity == r1) return r2; if (Identity == r2) return r1; @@ -127,34 +145,62 @@ abstract class PResults { } +interface PendingAction {} +class ProceedState implements PendingAction { + final State state; + + ProceedState(State state) { + this.state = state; + } +} +class MakeResult implements PendingAction { + final State state; + final PResult subResult; + final int[] indices; + + MakeResult(State state, PResult subResult, int[] indices) { + this.state = state; + this.subResult = subResult; + this.indices = indices; + } +} + class NonNullInAnalysis extends Analysis<PResult> { + private static final ThreadLocal<PendingAction[]> ourPending = new ThreadLocal<PendingAction[]>() { + @Override + protected PendingAction[] initialValue() { + return new PendingAction[Analysis.STEPS_LIMIT]; + } + }; + private static final ThreadLocal<PResult[]> ourResults = new ThreadLocal<PResult[]>() { + @Override + protected PResult[] initialValue() { + return new PResult[Analysis.STEPS_LIMIT]; + } + }; + + final private PendingAction[] pending = ourPending.get(); - private final NonNullInInterpreter interpreter = new NonNullInInterpreter(); + private final NotNullInterpreter interpreter = new NotNullInterpreter(); + private PResult[] results; + + // Flag saying that at some branch NPE was found. Used later as an evidence that this param is *NOT* @Nullable (optimization). + boolean possibleNPE; protected NonNullInAnalysis(RichControlFlow richControlFlow, Direction direction, boolean stable) { super(richControlFlow, direction, stable); + results = ourResults.get(); } - @Override - PResult identity() { - return Identity; - } - - @Override - PResult combineResults(PResult delta, List<PResult> subResults) throws AnalyzerException { - PResult subResult = Identity; - for (PResult sr : subResults) { - subResult = join(subResult, sr); + PResult combineResults(PResult delta, int[] subResults) throws AnalyzerException { + PResult result = Identity; + for (int subResult : subResults) { + result = join(result, results[subResult]); } - return meet(delta, subResult); + return meet(delta, result); } - @Override - boolean isEarlyResult(PResult result) { - return false; - } - - @Override + @NotNull Equation<Key, Value> mkEquation(PResult result) { if (Identity == result || Return == result) { return new Equation<Key, Value>(aKey, new Final<Key, Value>(Value.Top)); @@ -176,8 +222,73 @@ class NonNullInAnalysis extends Analysis<PResult> { private Frame<BasicValue> nextFrame = null; private PResult subResult = null; - @Override - void processState(State state) throws AnalyzerException { + @NotNull + protected Equation<Key, Value> analyze() throws AnalyzerException { + pendingPush(new ProceedState(createStartState())); + int steps = 0; + while (pendingTop > 0 && earlyResult == null) { + steps ++; + if (steps >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached, steps: " + steps + " in method " + method); + } + PendingAction action = pending[--pendingTop]; + if (action instanceof MakeResult) { + MakeResult makeResult = (MakeResult) action; + PResult result = combineResults(makeResult.subResult, makeResult.indices); + State state = makeResult.state; + int insnIndex = state.conf.insnIndex; + results[state.index] = result; + addComputed(insnIndex, state); + } + else if (action instanceof ProceedState) { + ProceedState proceedState = (ProceedState) action; + State state = proceedState.state; + int insnIndex = state.conf.insnIndex; + Conf conf = state.conf; + List<Conf> history = state.history; + + boolean fold = false; + if (dfsTree.loopEnters[insnIndex]) { + for (Conf prev : history) { + if (AbstractValues.isInstance(conf, prev)) { + fold = true; + break; + } + } + } + if (fold) { + results[state.index] = Identity; + addComputed(insnIndex, state); + } + else { + State baseState = null; + List<State> thisComputed = computed[insnIndex]; + if (thisComputed != null) { + for (State prevState : thisComputed) { + if (stateEquiv(state, prevState)) { + baseState = prevState; + break; + } + } + } + if (baseState != null) { + results[state.index] = results[baseState.index]; + } else { + // the main call + processState(state); + } + + } + } + } + if (earlyResult != null) { + return mkEquation(earlyResult); + } else { + return mkEquation(results[0]); + } + } + + private void processState(State state) throws AnalyzerException { int stateIndex = state.index; Conf conf = state.conf; int insnIndex = conf.insnIndex; @@ -185,15 +296,16 @@ class NonNullInAnalysis extends Analysis<PResult> { boolean taken = state.taken; Frame<BasicValue> frame = conf.frame; AbstractInsnNode insnNode = methodNode.instructions.get(insnIndex); - List<Conf> nextHistory = dfsTree.loopEnters.contains(insnIndex) ? append(history, conf) : history; + List<Conf> nextHistory = dfsTree.loopEnters[insnIndex] ? append(history, conf) : history; boolean hasCompanions = state.hasCompanions; execute(frame, insnNode); boolean notEmptySubResult = subResult != Identity; if (subResult == NPE) { - results.put(stateIndex, NPE); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + results[stateIndex] = NPE; + possibleNPE = true; + addComputed(insnIndex, state); return; } @@ -208,8 +320,8 @@ class NonNullInAnalysis extends Analysis<PResult> { if (!hasCompanions) { earlyResult = Return; } else { - results.put(stateIndex, Return); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + results[stateIndex] = Return; + addComputed(insnIndex, state); } return; default: @@ -217,70 +329,265 @@ class NonNullInAnalysis extends Analysis<PResult> { if (opcode == ATHROW) { if (taken) { - results.put(stateIndex, NPE); + results[stateIndex] = NPE; + possibleNPE = true; } else { - results.put(stateIndex, Identity); + results[stateIndex] = Identity; } - computed.put(insnIndex, append(computed.get(insnIndex), state)); + addComputed(insnIndex, state); return; } if (opcode == IFNONNULL && popValue(frame) instanceof ParamValue) { int nextInsnIndex = insnIndex + 1; State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, hasCompanions || notEmptySubResult); - pending.push(new MakeResult<PResult>(state, subResult, new int[]{nextState.index})); - pending.push(new ProceedState<PResult>(nextState)); + pendingPush(new MakeResult(state, subResult, new int[]{nextState.index})); + pendingPush(new ProceedState(nextState)); return; } if (opcode == IFNULL && popValue(frame) instanceof ParamValue) { int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, hasCompanions || notEmptySubResult); - pending.push(new MakeResult<PResult>(state, subResult, new int[]{nextState.index})); - pending.push(new ProceedState<PResult>(nextState)); + pendingPush(new MakeResult(state, subResult, new int[]{nextState.index})); + pendingPush(new ProceedState(nextState)); return; } if (opcode == IFEQ && popValue(frame) == InstanceOfCheckValue) { int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, hasCompanions || notEmptySubResult); - pending.push(new MakeResult<PResult>(state, subResult, new int[]{nextState.index})); - pending.push(new ProceedState<PResult>(nextState)); + pendingPush(new MakeResult(state, subResult, new int[]{nextState.index})); + pendingPush(new ProceedState(nextState)); return; } if (opcode == IFNE && popValue(frame) == InstanceOfCheckValue) { int nextInsnIndex = insnIndex + 1; State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, hasCompanions || notEmptySubResult); - pending.push(new MakeResult<PResult>(state, subResult, new int[]{nextState.index})); - pending.push(new ProceedState<PResult>(nextState)); + pendingPush(new MakeResult(state, subResult, new int[]{nextState.index})); + pendingPush(new ProceedState(nextState)); return; } // general case int[] nextInsnIndices = controlFlow.transitions[insnIndex]; - List<State> nextStates = new ArrayList<State>(nextInsnIndices.length); int[] subIndices = new int[nextInsnIndices.length]; - + for (int i = 0; i < nextInsnIndices.length; i++) { + subIndices[i] = ++id; + } + pendingPush(new MakeResult(state, subResult, subIndices)); for (int i = 0; i < nextInsnIndices.length; i++) { int nextInsnIndex = nextInsnIndices[i]; Frame<BasicValue> nextFrame1 = nextFrame; - if (controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { + if (controlFlow.errors[nextInsnIndex] && controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { nextFrame1 = new Frame<BasicValue>(frame); nextFrame1.clearStack(); - nextFrame1.push(new BasicValue(Type.getType("java/lang/Throwable"))); + nextFrame1.push(ASMUtils.THROWABLE_VALUE); + } + pendingPush(new ProceedState(new State(subIndices[i], new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, hasCompanions || notEmptySubResult))); + } + + } + + private int pendingTop = 0; + + private void pendingPush(PendingAction action) throws AnalyzerException { + if (pendingTop >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached in method " + method); + } + pending[pendingTop++] = action; + } + + private void execute(Frame<BasicValue> frame, AbstractInsnNode insnNode) throws AnalyzerException { + switch (insnNode.getType()) { + case AbstractInsnNode.LABEL: + case AbstractInsnNode.LINE: + case AbstractInsnNode.FRAME: + nextFrame = frame; + subResult = Identity; + break; + default: + nextFrame = new Frame<BasicValue>(frame); + interpreter.reset(); + nextFrame.execute(insnNode, interpreter); + subResult = interpreter.getSubResult(); + } + } +} + +class NullableInAnalysis extends Analysis<PResult> { + final private State[] pending = ourPendingStates.get(); + + private final NullableInterpreter interpreter = new NullableInterpreter(); + + protected NullableInAnalysis(RichControlFlow richControlFlow, Direction direction, boolean stable) { + super(richControlFlow, direction, stable); + } + + @NotNull + Equation<Key, Value> mkEquation(PResult result) { + if (NPE == result) { + return new Equation<Key, Value>(aKey, new Final<Key, Value>(Value.Top)); + } + if (Identity == result || Return == result) { + return new Equation<Key, Value>(aKey, new Final<Key, Value>(Value.Null)); + } + else { + ConditionalNPE condNpe = (ConditionalNPE) result; + Set<Product<Key, Value>> components = new HashSet<Product<Key, Value>>(); + for (Set<Key> prod : condNpe.sop) { + components.add(new Product<Key, Value>(Value.Top, prod)); + } + return new Equation<Key, Value>(aKey, new Pending<Key, Value>(components)); + } + } + + private int id = 0; + private Frame<BasicValue> nextFrame = null; + private PResult myResult = Identity; + private PResult subResult = Identity; + private boolean top = false; + + @NotNull + protected Equation<Key, Value> analyze() throws AnalyzerException { + pendingPush(createStartState()); + int steps = 0; + while (pendingTop > 0 && earlyResult == null) { + steps ++; + if (steps >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached, steps: " + steps + " in method " + method); + } + State state = pending[--pendingTop]; + int insnIndex = state.conf.insnIndex; + Conf conf = state.conf; + List<Conf> history = state.history; + + boolean fold = false; + if (dfsTree.loopEnters[insnIndex]) { + for (Conf prev : history) { + if (AbstractValues.isInstance(conf, prev)) { + fold = true; + break; + } + } + } + if (fold) { + addComputed(insnIndex, state); + } + else { + State baseState = null; + List<State> thisComputed = computed[insnIndex]; + if (thisComputed != null) { + for (State prevState : thisComputed) { + if (stateEquiv(state, prevState)) { + baseState = prevState; + break; + } + } + } + if (baseState == null) { + processState(state); + } } - nextStates.add(new State(++id, new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, hasCompanions || notEmptySubResult)); - subIndices[i] = (id); + } + if (earlyResult != null) { + return mkEquation(earlyResult); + } else { + return mkEquation(myResult); + } + } + + private void processState(State state) throws AnalyzerException { + Conf conf = state.conf; + int insnIndex = conf.insnIndex; + List<Conf> history = state.history; + boolean taken = state.taken; + Frame<BasicValue> frame = conf.frame; + AbstractInsnNode insnNode = methodNode.instructions.get(insnIndex); + List<Conf> nextHistory = dfsTree.loopEnters[insnIndex] ? append(history, conf) : history; + + addComputed(insnIndex, state); + execute(frame, insnNode); + + if (subResult == NPE || top) { + earlyResult = NPE; + return; + } + + if (subResult instanceof ConditionalNPE) { + myResult = combineNullable(myResult, subResult); + } + + int opcode = insnNode.getOpcode(); + switch (opcode) { + case ARETURN: + if (popValue(frame) instanceof ParamValue) { + earlyResult = NPE; + } + return; + case IRETURN: + case LRETURN: + case FRETURN: + case DRETURN: + case RETURN: + return; + default: + } + + if (opcode == ATHROW) { + if (taken) { + earlyResult = NPE; + } + return; + } + + if (opcode == IFNONNULL && popValue(frame) instanceof ParamValue) { + int nextInsnIndex = insnIndex + 1; + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false)); + return; + } + + if (opcode == IFNULL && popValue(frame) instanceof ParamValue) { + int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false)); + return; + } + + if (opcode == IFEQ && popValue(frame) == InstanceOfCheckValue) { + int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false)); + return; } - pending.push(new MakeResult<PResult>(state, subResult, subIndices)); - for (State nextState : nextStates) { - pending.push(new ProceedState<PResult>(nextState)); + if (opcode == IFNE && popValue(frame) == InstanceOfCheckValue) { + int nextInsnIndex = insnIndex + 1; + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false)); + return; + } + + // general case + for (int nextInsnIndex : controlFlow.transitions[insnIndex]) { + Frame<BasicValue> nextFrame1 = nextFrame; + if (controlFlow.errors[nextInsnIndex] && controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { + nextFrame1 = new Frame<BasicValue>(frame); + nextFrame1.clearStack(); + nextFrame1.push(ASMUtils.THROWABLE_VALUE); + } + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, false)); } } + private int pendingTop = 0; + + private void pendingPush(State state) throws AnalyzerException { + if (pendingTop >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached in method " + method); + } + pending[pendingTop++] = state; + } + private void execute(Frame<BasicValue> frame, AbstractInsnNode insnNode) throws AnalyzerException { switch (insnNode.getType()) { case AbstractInsnNode.LABEL: @@ -288,23 +595,37 @@ class NonNullInAnalysis extends Analysis<PResult> { case AbstractInsnNode.FRAME: nextFrame = frame; subResult = Identity; + top = false; break; default: nextFrame = new Frame<BasicValue>(frame); interpreter.reset(); nextFrame.execute(insnNode, interpreter); subResult = interpreter.getSubResult(); + top = interpreter.top; } } } -class NonNullInInterpreter extends BasicInterpreter { +abstract class NullityInterpreter extends BasicInterpreter { + boolean top = false; + final boolean nullableAnalysis; + final int nullityMask; private PResult subResult = Identity; + + NullityInterpreter(boolean nullableAnalysis, int nullityMask) { + this.nullableAnalysis = nullableAnalysis; + this.nullityMask = nullityMask; + } + + abstract PResult combine(PResult res1, PResult res2) throws AnalyzerException; + public PResult getSubResult() { return subResult; } void reset() { subResult = Identity; + top = false; } @Override @@ -344,10 +665,17 @@ class NonNullInInterpreter extends BasicInterpreter { case BALOAD: case CALOAD: case SALOAD: + if (value1 instanceof ParamValue) { + subResult = NPE; + } + break; case PUTFIELD: if (value1 instanceof ParamValue) { subResult = NPE; } + if (nullableAnalysis && value2 instanceof ParamValue) { + subResult = NPE; + } break; default: } @@ -361,13 +689,21 @@ class NonNullInInterpreter extends BasicInterpreter { case LASTORE: case FASTORE: case DASTORE: - case AASTORE: case BASTORE: case CASTORE: case SASTORE: if (value1 instanceof ParamValue) { subResult = NPE; } + break; + case AASTORE: + if (value1 instanceof ParamValue) { + subResult = NPE; + } + if (nullableAnalysis && value3 instanceof ParamValue) { + subResult = NPE; + } + break; default: } return super.ternaryOperation(insn, value1, value2, value3); @@ -382,20 +718,54 @@ class NonNullInInterpreter extends BasicInterpreter { subResult = NPE; } switch (opcode) { + case INVOKEINTERFACE: + if (nullableAnalysis) { + for (int i = shift; i < values.size(); i++) { + if (values.get(i) instanceof ParamValue) { + top = true; + return super.naryOperation(insn, values); + } + } + } + break; case INVOKESTATIC: case INVOKESPECIAL: case INVOKEVIRTUAL: - case INVOKEINTERFACE: boolean stable = opcode == INVOKESTATIC || opcode == INVOKESPECIAL; MethodInsnNode methodNode = (MethodInsnNode) insn; + Method method = new Method(methodNode.owner, methodNode.name, methodNode.desc); for (int i = shift; i < values.size(); i++) { if (values.get(i) instanceof ParamValue) { - Method method = new Method(methodNode.owner, methodNode.name, methodNode.desc); - subResult = meet(subResult, new ConditionalNPE(new Key(method, new In(i - shift), stable))); + subResult = combine(subResult, new ConditionalNPE(new Key(method, new In(i - shift, nullityMask), stable))); } } + break; default: } return super.naryOperation(insn, values); } } + +class NotNullInterpreter extends NullityInterpreter { + + NotNullInterpreter() { + super(false, In.NOT_NULL); + } + + @Override + PResult combine(PResult res1, PResult res2) throws AnalyzerException { + return meet(res1, res2); + } +} + +class NullableInterpreter extends NullityInterpreter { + + NullableInterpreter() { + super(true, In.NULLABLE); + } + + @Override + PResult combine(PResult res1, PResult res2) throws AnalyzerException { + return join(res1, res2); + } +} |