summaryrefslogtreecommitdiff
path: root/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java
diff options
context:
space:
mode:
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.java472
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);
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-23 06:05:33 +0000