diff options
Diffstat (limited to 'java/java-analysis-impl/src')
31 files changed, 5007 insertions, 336 deletions
diff --git a/java/java-analysis-impl/src/com/intellij/codeInsight/InferredAnnotationsManagerImpl.java b/java/java-analysis-impl/src/com/intellij/codeInsight/InferredAnnotationsManagerImpl.java new file mode 100644 index 000000000000..813ff25caee2 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInsight/InferredAnnotationsManagerImpl.java @@ -0,0 +1,83 @@ +/* + * 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.codeInsight; + +import com.intellij.codeInspection.bytecodeAnalysis.ProjectBytecodeAnalysis; +import com.intellij.codeInspection.dataFlow.ContractInference; +import com.intellij.codeInspection.dataFlow.MethodContract; +import com.intellij.openapi.util.text.StringUtil; +import com.intellij.psi.PsiAnnotation; +import com.intellij.psi.PsiMethod; +import com.intellij.psi.PsiModifierListOwner; +import com.intellij.psi.util.PsiUtil; +import com.intellij.util.containers.ContainerUtil; +import org.jetbrains.annotations.NotNull; +import org.jetbrains.annotations.Nullable; + +import java.util.List; + +import static com.intellij.codeInspection.dataFlow.ControlFlowAnalyzer.ORG_JETBRAINS_ANNOTATIONS_CONTRACT; + +public class InferredAnnotationsManagerImpl extends InferredAnnotationsManager { + @Nullable + @Override + public PsiAnnotation findInferredAnnotation(@NotNull PsiModifierListOwner listOwner, @NotNull String annotationFQN) { + PsiAnnotation fromBytecode = ProjectBytecodeAnalysis.getInstance(listOwner.getProject()).findInferredAnnotation(listOwner, annotationFQN); + if (fromBytecode != null) { + return fromBytecode; + } + + if (ORG_JETBRAINS_ANNOTATIONS_CONTRACT.equals(annotationFQN) && canHaveContract(listOwner)) { + List<MethodContract> contracts = ContractInference.inferContracts((PsiMethod)listOwner); + if (!contracts.isEmpty()) { + return ProjectBytecodeAnalysis.getInstance(listOwner.getProject()).createContractAnnotation("\"" + StringUtil.join(contracts, "; ") + "\""); + } + } + + return null; + } + + private static boolean canHaveContract(PsiModifierListOwner listOwner) { + return listOwner instanceof PsiMethod && !PsiUtil.canBeOverriden((PsiMethod)listOwner); + } + + @NotNull + @Override + public PsiAnnotation[] findInferredAnnotations(@NotNull PsiModifierListOwner listOwner) { + List<PsiAnnotation> result = ContainerUtil.newArrayList(); + PsiAnnotation[] fromBytecode = ProjectBytecodeAnalysis.getInstance(listOwner.getProject()).findInferredAnnotations(listOwner); + for (PsiAnnotation annotation : fromBytecode) { + if (!ORG_JETBRAINS_ANNOTATIONS_CONTRACT.equals(annotation.getQualifiedName()) || canHaveContract(listOwner)) { + result.add(annotation); + } + } + + if (canHaveContract(listOwner)) { + List<MethodContract> contracts = ContractInference.inferContracts((PsiMethod)listOwner); + if (!contracts.isEmpty()) { + result.add(ProjectBytecodeAnalysis.getInstance(listOwner.getProject()) + .createContractAnnotation("\"" + StringUtil.join(contracts, "; ") + "\"")); + } + } + + return result.isEmpty() ? PsiAnnotation.EMPTY_ARRAY : result.toArray(new PsiAnnotation[result.size()]); + } + + @Override + public boolean isInferredAnnotation(@NotNull PsiAnnotation annotation) { + return annotation.getUserData(ProjectBytecodeAnalysis.INFERRED_ANNOTATION) != null; + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInsight/daemon/impl/quickfix/AddTypeCastFix.java b/java/java-analysis-impl/src/com/intellij/codeInsight/daemon/impl/quickfix/AddTypeCastFix.java index 0ccad5cadf48..9fc35a649504 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInsight/daemon/impl/quickfix/AddTypeCastFix.java +++ b/java/java-analysis-impl/src/com/intellij/codeInsight/daemon/impl/quickfix/AddTypeCastFix.java @@ -31,6 +31,7 @@ import com.intellij.openapi.editor.Editor; import com.intellij.openapi.project.Project; import com.intellij.psi.*; import com.intellij.psi.codeStyle.CodeStyleManager; +import com.intellij.psi.codeStyle.JavaCodeStyleManager; import com.intellij.psi.util.PsiUtil; import com.intellij.psi.util.TypeConversionUtil; import org.jetbrains.annotations.NotNull; @@ -91,6 +92,7 @@ public class AddTypeCastFix extends LocalQuickFixAndIntentionActionOnPsiElement String text = "(" + type.getCanonicalText(false) + ")value"; PsiElementFactory factory = JavaPsiFacade.getInstance(original.getProject()).getElementFactory(); PsiTypeCastExpression typeCast = (PsiTypeCastExpression)factory.createExpressionFromText(text, original); + typeCast = (PsiTypeCastExpression)JavaCodeStyleManager.getInstance(project).shortenClassReferences(typeCast); typeCast = (PsiTypeCastExpression)CodeStyleManager.getInstance(project).reformat(typeCast); if (expression instanceof PsiConditionalExpression) { diff --git a/java/java-analysis-impl/src/com/intellij/codeInsight/intention/AddAnnotationPsiFix.java b/java/java-analysis-impl/src/com/intellij/codeInsight/intention/AddAnnotationPsiFix.java index 84f704f64dcd..e5e4bb68d11e 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInsight/intention/AddAnnotationPsiFix.java +++ b/java/java-analysis-impl/src/com/intellij/codeInsight/intention/AddAnnotationPsiFix.java @@ -75,13 +75,16 @@ public class AddAnnotationPsiFix extends LocalQuickFixOnPsiElement { PsiElement element = file.findElementAt(offset); - PsiModifierListOwner listOwner = PsiTreeUtil.getParentOfType(element, PsiParameter.class, false); - if (listOwner != null) return listOwner; + PsiModifierListOwner listOwner = PsiTreeUtil.getParentOfType(element, PsiModifierListOwner.class, false); + if (listOwner instanceof PsiParameter) return listOwner; - final PsiIdentifier psiIdentifier = PsiTreeUtil.getParentOfType(element, PsiIdentifier.class, false); - if (psiIdentifier != null && psiIdentifier.getParent() instanceof PsiModifierListOwner) { - return (PsiModifierListOwner)psiIdentifier.getParent(); + if (listOwner instanceof PsiNameIdentifierOwner) { + PsiElement id = ((PsiNameIdentifierOwner)listOwner).getNameIdentifier(); + if (id != null && id.getTextRange().containsOffset(offset)) { // Groovy methods will pass this check as well + return listOwner; + } } + return null; } diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/AnonymousCanBeLambdaInspection.java b/java/java-analysis-impl/src/com/intellij/codeInspection/AnonymousCanBeLambdaInspection.java index 96066c34eefe..c1f127d3a1df 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/AnonymousCanBeLambdaInspection.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/AnonymousCanBeLambdaInspection.java @@ -32,10 +32,7 @@ import com.intellij.psi.controlFlow.ControlFlow; import com.intellij.psi.controlFlow.ControlFlowUtil; import com.intellij.psi.impl.source.resolve.DefaultParameterTypeInferencePolicy; import com.intellij.psi.infos.MethodCandidateInfo; -import com.intellij.psi.util.InheritanceUtil; -import com.intellij.psi.util.PsiTreeUtil; -import com.intellij.psi.util.PsiTypesUtil; -import com.intellij.psi.util.PsiUtil; +import com.intellij.psi.util.*; import com.intellij.util.ArrayUtilRt; import com.intellij.util.Function; import com.intellij.util.containers.ContainerUtilRt; @@ -91,16 +88,12 @@ public class AnonymousCanBeLambdaInspection extends BaseJavaBatchLocalInspection final PsiMethod[] methods = aClass.getMethods(); if (methods.length == 1 && aClass.getFields().length == 0) { final PsiCodeBlock body = methods[0].getBody(); - if (body != null) { - final ForbiddenRefsChecker checker = new ForbiddenRefsChecker(methods[0], aClass); - body.accept(checker); - if (!checker.hasForbiddenRefs()) { - final PsiElement lBrace = aClass.getLBrace(); - LOG.assertTrue(lBrace != null); - final TextRange rangeInElement = new TextRange(0, aClass.getStartOffsetInParent() + lBrace.getStartOffsetInParent()); - holder.registerProblem(aClass.getParent(), "Anonymous #ref #loc can be replaced with lambda", - ProblemHighlightType.LIKE_UNUSED_SYMBOL, rangeInElement, new ReplaceWithLambdaFix()); - } + if (body != null && !hasForbiddenRefsInsideBody(methods[0], aClass)) { + final PsiElement lBrace = aClass.getLBrace(); + LOG.assertTrue(lBrace != null); + final TextRange rangeInElement = new TextRange(0, aClass.getStartOffsetInParent() + lBrace.getStartOffsetInParent()); + holder.registerProblem(aClass.getParent(), "Anonymous #ref #loc can be replaced with lambda", + ProblemHighlightType.LIKE_UNUSED_SYMBOL, rangeInElement, new ReplaceWithLambdaFix()); } } } @@ -110,6 +103,14 @@ public class AnonymousCanBeLambdaInspection extends BaseJavaBatchLocalInspection }; } + public static boolean hasForbiddenRefsInsideBody(PsiMethod method, PsiAnonymousClass aClass) { + final ForbiddenRefsChecker checker = new ForbiddenRefsChecker(method, aClass); + final PsiCodeBlock body = method.getBody(); + LOG.assertTrue(body != null); + body.accept(checker); + return checker.hasForbiddenRefs(); + } + private static PsiType getInferredType(PsiAnonymousClass aClass) { final PsiExpression expression = (PsiExpression)aClass.getParent(); final PsiType psiType = PsiTypesUtil.getExpectedTypeByParent(expression); @@ -369,14 +370,14 @@ public class AnonymousCanBeLambdaInspection extends BaseJavaBatchLocalInspection private final PsiMethod myMethod; private final PsiAnonymousClass myAnonymClass; - private final boolean myRawType; + private final boolean myEqualInference; public ForbiddenRefsChecker(PsiMethod method, PsiAnonymousClass aClass) { myMethod = method; myAnonymClass = aClass; final PsiType inferredType = getInferredType(aClass); - myRawType = inferredType instanceof PsiClassType && ((PsiClassType)inferredType).isRaw(); + myEqualInference = !aClass.getBaseClassType().equals(inferredType); } @Override @@ -467,7 +468,7 @@ public class AnonymousCanBeLambdaInspection extends BaseJavaBatchLocalInspection } } - if (myRawType) { + if (myEqualInference) { final PsiElement resolved = expression.resolve(); if (resolved instanceof PsiParameter && ((PsiParameter)resolved).getDeclarationScope() == myMethod) { final int parameterIndex = myMethod.getParameterList().getParameterIndex((PsiParameter)resolved); diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/AnonymousCanBeMethodReferenceInspection.java b/java/java-analysis-impl/src/com/intellij/codeInspection/AnonymousCanBeMethodReferenceInspection.java index d6a884c8917c..c3363ec7eb12 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/AnonymousCanBeMethodReferenceInspection.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/AnonymousCanBeMethodReferenceInspection.java @@ -69,7 +69,7 @@ public class AnonymousCanBeMethodReferenceInspection extends BaseJavaBatchLocalI final PsiClassType baseClassType = aClass.getBaseClassType(); if (LambdaUtil.isFunctionalType(baseClassType)) { final PsiMethod[] methods = aClass.getMethods(); - if (methods.length == 1 && aClass.getFields().length == 0) { + if (methods.length == 1 && aClass.getFields().length == 0 && !AnonymousCanBeLambdaInspection.hasForbiddenRefsInsideBody(methods[0], aClass)) { final PsiCodeBlock body = methods[0].getBody(); final PsiCallExpression callExpression = LambdaCanBeMethodReferenceInspection diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/LambdaCanBeMethodReferenceInspection.java b/java/java-analysis-impl/src/com/intellij/codeInspection/LambdaCanBeMethodReferenceInspection.java index 1e887030dcb4..416226e9ac8f 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/LambdaCanBeMethodReferenceInspection.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/LambdaCanBeMethodReferenceInspection.java @@ -245,11 +245,14 @@ public class LambdaCanBeMethodReferenceInspection extends BaseJavaBatchLocalInsp PsiParameter[] candidateParams = method.getParameterList().getParameters(); if (candidateParams.length == 1) { if (TypeConversionUtil.areTypesConvertible(candidateParams[0].getType(), parameters[0].getType())) { - for (PsiMethod superMethod : psiMethod.findDeepestSuperMethods()) { - PsiMethod validSuperMethod = ensureNonAmbiguousMethod(parameters, superMethod); - if (validSuperMethod != null) return validSuperMethod; + final PsiMethod[] deepestSuperMethods = psiMethod.findDeepestSuperMethods(); + if (deepestSuperMethods.length > 0) { + for (PsiMethod superMethod : deepestSuperMethods) { + PsiMethod validSuperMethod = ensureNonAmbiguousMethod(parameters, superMethod); + if (validSuperMethod != null) return validSuperMethod; + } + return null; } - return null; } } } diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Analysis.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Analysis.java new file mode 100644 index 000000000000..44e493c63f0a --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Analysis.java @@ -0,0 +1,398 @@ +/* + * 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 gnu.trove.TIntObjectHashMap; +import org.jetbrains.org.objectweb.asm.Opcodes; +import org.jetbrains.org.objectweb.asm.Type; +import org.jetbrains.org.objectweb.asm.tree.MethodNode; +import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException; +import org.jetbrains.org.objectweb.asm.tree.analysis.BasicValue; +import org.jetbrains.org.objectweb.asm.tree.analysis.Frame; + +import java.util.*; + +class AbstractValues { + static final class ParamValue extends BasicValue { + ParamValue(Type tp) { + super(tp); + } + } + static final BasicValue InstanceOfCheckValue = new BasicValue(Type.INT_TYPE) { + @Override + public boolean equals(Object value) { + return this == value; + } + }; + + static final BasicValue TrueValue = new BasicValue(Type.INT_TYPE) { + @Override + public boolean equals(Object value) { + return this == value; + } + }; + + static final BasicValue FalseValue = new BasicValue(Type.INT_TYPE) { + @Override + public boolean equals(Object value) { + return this == value; + } + }; + + static final BasicValue NullValue = new BasicValue(Type.getObjectType("null")) { + @Override + public boolean equals(Object value) { + return this == value; + } + }; + static final class NotNullValue extends BasicValue { + NotNullValue(Type tp) { + super(tp); + } + } + static final class CallResultValue extends BasicValue { + final Set<Key> inters; + CallResultValue(Type tp, Set<Key> inters) { + super(tp); + this.inters = inters; + } + } + + static boolean isInstance(Conf curr, Conf prev) { + if (curr.insnIndex != prev.insnIndex) { + return false; + } + Frame<BasicValue> currFr = curr.frame; + Frame<BasicValue> prevFr = prev.frame; + for (int i = 0; i < currFr.getLocals(); i++) { + if (!isInstance(currFr.getLocal(i), prevFr.getLocal(i))) { + return false; + } + } + for (int i = 0; i < currFr.getStackSize(); i++) { + if (!isInstance(currFr.getStack(i), prevFr.getStack(i))) { + return false; + } + } + return true; + } + + static boolean isInstance(BasicValue curr, BasicValue prev) { + if (prev instanceof ParamValue) { + return curr instanceof ParamValue; + } + if (InstanceOfCheckValue == prev) { + return InstanceOfCheckValue == curr; + } + if (TrueValue == prev) { + return TrueValue == curr; + } + if (FalseValue == prev) { + return FalseValue == curr; + } + if (NullValue == prev) { + return NullValue == curr; + } + if (prev instanceof NotNullValue) { + return curr instanceof NotNullValue; + } + if (prev instanceof CallResultValue) { + if (curr instanceof CallResultValue) { + CallResultValue prevCall = (CallResultValue) prev; + CallResultValue currCall = (CallResultValue) curr; + return prevCall.inters.equals(currCall.inters); + } + else { + return false; + } + } + return true; + } + + static boolean equiv(Conf curr, Conf prev) { + Frame<BasicValue> currFr = curr.frame; + Frame<BasicValue> prevFr = prev.frame; + for (int i = currFr.getStackSize() - 1; i >= 0; i--) { + if (!equiv(currFr.getStack(i), prevFr.getStack(i))) { + return false; + } + } + for (int i = currFr.getLocals() - 1; i >= 0; i--) { + if (!equiv(currFr.getLocal(i), prevFr.getLocal(i))) { + return false; + } + } + return true; + } + + static boolean equiv(BasicValue curr, BasicValue prev) { + if (curr.getClass() == prev.getClass()) { + if (curr instanceof CallResultValue && prev instanceof CallResultValue) { + Set<Key> keys1 = ((CallResultValue)prev).inters; + Set<Key> keys2 = ((CallResultValue)curr).inters; + return keys1.equals(keys2); + } + else return true; + } + else return false; + } +} + +final class Conf { + final int insnIndex; + final Frame<BasicValue> frame; + final int fastHashCode; + + Conf(int insnIndex, Frame<BasicValue> frame) { + this.insnIndex = insnIndex; + this.frame = frame; + + int hash = 0; + for (int i = 0; i < frame.getLocals(); i++) { + hash = hash * 31 + frame.getLocal(i).getClass().hashCode(); + } + for (int i = 0; i < frame.getStackSize(); i++) { + hash = hash * 31 + frame.getStack(i).getClass().hashCode(); + } + fastHashCode = hash; + } +} + +final class State { + final int index; + final Conf conf; + final List<Conf> history; + final boolean taken; + final boolean hasCompanions; + + State(int index, Conf conf, List<Conf> history, boolean taken, boolean hasCompanions) { + this.index = index; + this.conf = conf; + this.history = history; + this.taken = taken; + this.hasCompanions = hasCompanions; + } +} + +interface PendingAction<Res> {} +class ProceedState<Res> implements PendingAction<Res> { + final State state; + + ProceedState(State state) { + this.state = state; + } +} +class MakeResult<Res> implements PendingAction<Res> { + final State state; + final Res subResult; + final int[] indices; + + MakeResult(State state, Res subResult, int[] indices) { + this.state = state; + this.subResult = subResult; + this.indices = indices; + } +} + +abstract class Analysis<Res> { + private static final int STEPS_LIMIT = 30000; + final RichControlFlow richControlFlow; + final Direction direction; + final ControlFlowGraph controlFlow; + final MethodNode methodNode; + final Method method; + final DFSTree dfsTree; + final Res myIdentity; + + final Deque<PendingAction<Res>> pending = new LinkedList<PendingAction<Res>>(); + final TIntObjectHashMap<List<State>> computed = new TIntObjectHashMap<List<State>>(); + final TIntObjectHashMap<Res> results = new TIntObjectHashMap<Res>(); + final Key aKey; + + Res earlyResult = null; + + abstract Res identity(); + abstract Res combineResults(Res delta, List<Res> subResults); + abstract boolean isEarlyResult(Res res); + abstract Equation<Key, Value> mkEquation(Res result); + abstract void processState(State state) throws AnalyzerException; + + protected Analysis(RichControlFlow richControlFlow, Direction direction, boolean stable) { + this.richControlFlow = richControlFlow; + this.direction = direction; + controlFlow = richControlFlow.controlFlow; + methodNode = controlFlow.methodNode; + method = new Method(controlFlow.className, methodNode.name, methodNode.desc); + dfsTree = richControlFlow.dfsTree; + aKey = new Key(method, direction, stable); + myIdentity = identity(); + } + + final State createStartState() { + return new State(0, new Conf(0, createStartFrame()), new ArrayList<Conf>(), false, false); + } + + static boolean stateEquiv(State curr, State prev) { + if (curr.taken != prev.taken) { + return false; + } + if (curr.conf.fastHashCode != prev.conf.fastHashCode) { + return false; + } + if (!AbstractValues.equiv(curr.conf, prev.conf)) { + return false; + } + if (curr.history.size() != prev.history.size()) { + return false; + } + for (int i = 0; i < curr.history.size(); i++) { + Conf curr1 = curr.history.get(i); + Conf prev1 = prev.history.get(i); + if (curr1.fastHashCode != prev1.fastHashCode || !AbstractValues.equiv(curr1, prev1)) { + return false; + } + } + return true; + } + + final Equation<Key, Value> analyze() throws AnalyzerException { + pending.push(new ProceedState<Res>(createStartState())); + int steps = 0; + while (!pending.isEmpty() && earlyResult == null) { + steps ++; + if (steps >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached, steps: " + steps + " in method " + method); + } + PendingAction<Res> action = pending.pop(); + if (action instanceof MakeResult) { + MakeResult<Res> makeResult = (MakeResult<Res>) action; + ArrayList<Res> subResults = new ArrayList<Res>(); + for (int index : makeResult.indices) { + subResults.add(results.get(index)); + } + Res result = combineResults(makeResult.subResult, subResults); + if (isEarlyResult(result)) { + earlyResult = result; + } else { + State state = makeResult.state; + int insnIndex = state.conf.insnIndex; + results.put(state.index, result); + List<State> thisComputed = computed.get(insnIndex); + if (thisComputed == null) { + thisComputed = new ArrayList<State>(); + computed.put(insnIndex, thisComputed); + } + thisComputed.add(state); + } + } + else if (action instanceof ProceedState) { + ProceedState<Res> proceedState = (ProceedState<Res>) 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.contains(insnIndex)) { + for (Conf prev : history) { + if (AbstractValues.isInstance(conf, prev)) { + fold = true; + } + } + } + if (fold) { + results.put(state.index, myIdentity); + List<State> thisComputed = computed.get(insnIndex); + if (thisComputed == null) { + thisComputed = new ArrayList<State>(); + computed.put(insnIndex, thisComputed); + } + thisComputed.add(state); + } + else { + State baseState = null; + List<State> thisComputed = computed.get(insnIndex); + if (thisComputed != null) { + for (State prevState : thisComputed) { + if (stateEquiv(state, prevState)) { + baseState = prevState; + break; + } + } + } + if (baseState != null) { + results.put(state.index, results.get(baseState.index)); + } else { + // the main call + processState(state); + } + + } + } + } + if (earlyResult != null) { + return mkEquation(earlyResult); + } else { + return mkEquation(results.get(0)); + } + } + + final Frame<BasicValue> createStartFrame() { + Frame<BasicValue> frame = new Frame<BasicValue>(methodNode.maxLocals, methodNode.maxStack); + Type returnType = Type.getReturnType(methodNode.desc); + BasicValue returnValue = Type.VOID_TYPE.equals(returnType) ? null : new BasicValue(returnType); + frame.setReturn(returnValue); + + Type[] args = Type.getArgumentTypes(methodNode.desc); + int local = 0; + if ((methodNode.access & Opcodes.ACC_STATIC) == 0) { + frame.setLocal(local++, new AbstractValues.NotNullValue(Type.getObjectType(controlFlow.className))); + } + for (int i = 0; i < args.length; i++) { + BasicValue value; + if (direction instanceof InOut && ((InOut)direction).paramIndex == i) { + value = new AbstractValues.ParamValue(args[i]); + } + else if (direction instanceof In && ((In)direction).paramIndex == i) { + value = new AbstractValues.ParamValue(args[i]); + } + else { + value = new BasicValue(args[i]); + } + frame.setLocal(local++, value); + if (args[i].getSize() == 2) { + frame.setLocal(local++, BasicValue.UNINITIALIZED_VALUE); + } + } + while (local < methodNode.maxLocals) { + frame.setLocal(local++, BasicValue.UNINITIALIZED_VALUE); + } + return frame; + } + + static BasicValue popValue(Frame<BasicValue> frame) { + return frame.getStack(frame.getStackSize() - 1); + } + + static <A> List<A> append(List<A> xs, A x) { + ArrayList<A> result = new ArrayList<A>(); + if (xs != null) { + result.addAll(xs); + } + result.add(x); + return result; + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisConverter.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisConverter.java new file mode 100644 index 000000000000..f29dd7f6cf0c --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisConverter.java @@ -0,0 +1,485 @@ +/* + * 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.ide.util.PropertiesComponent; +import com.intellij.openapi.application.ApplicationManager; +import com.intellij.openapi.application.PathManager; +import com.intellij.openapi.components.ApplicationComponent; +import com.intellij.openapi.progress.ProgressManager; +import com.intellij.openapi.util.ThrowableComputable; +import com.intellij.openapi.util.text.StringUtil; +import com.intellij.psi.*; +import com.intellij.psi.util.PsiTreeUtil; +import com.intellij.psi.util.TypeConversionUtil; +import com.intellij.util.io.*; +import gnu.trove.TIntHashSet; +import gnu.trove.TIntObjectHashMap; +import gnu.trove.TIntObjectIterator; +import org.jetbrains.annotations.NotNull; +import org.jetbrains.annotations.Nullable; +import org.jetbrains.org.objectweb.asm.Type; + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.File; +import java.io.IOException; +import java.util.*; + +import static com.intellij.codeInspection.bytecodeAnalysis.ProjectBytecodeAnalysis.LOG; + +/** + * @author lambdamix + */ +public class BytecodeAnalysisConverter implements ApplicationComponent { + + private static final String VERSION = "BytecodeAnalysisConverter.Enumerators"; + + public static BytecodeAnalysisConverter getInstance() { + return ApplicationManager.getApplication().getComponent(BytecodeAnalysisConverter.class); + } + + private PersistentStringEnumerator myNamesEnumerator; + private PersistentEnumeratorDelegate<int[]> myCompoundKeyEnumerator; + private int version; + + @Override + public void initComponent() { + version = PropertiesComponent.getInstance().getOrInitInt(VERSION, 0); + final File keysDir = new File(PathManager.getIndexRoot(), "bytecodekeys"); + final File namesFile = new File(keysDir, "names"); + final File compoundKeysFile = new File(keysDir, "compound"); + + try { + IOUtil.openCleanOrResetBroken(new ThrowableComputable<Void, IOException>() { + @Override + public Void compute() throws IOException { + myNamesEnumerator = new PersistentStringEnumerator(namesFile, true); + myCompoundKeyEnumerator = new IntArrayPersistentEnumerator(compoundKeysFile, new IntArrayKeyDescriptor()); + return null; + } + }, new Runnable() { + @Override + public void run() { + LOG.info("Error during initialization of enumerators in bytecode analysis. Re-initializing."); + IOUtil.deleteAllFilesStartingWith(keysDir); + version ++; + } + }); + } + catch (IOException e) { + LOG.error("Re-initialization of enumerators in bytecode analysis failed.", e); + } + // TODO: is it enough for rebuilding indices? + PropertiesComponent.getInstance().setValue(VERSION, String.valueOf(version)); + } + + @Override + public void disposeComponent() { + try { + myNamesEnumerator.close(); + myCompoundKeyEnumerator.close(); + } + catch (IOException e) { + LOG.debug(e); + } + } + + @NotNull + @Override + public String getComponentName() { + return "BytecodeAnalysisConverter"; + } + + IntIdEquation convert(Equation<Key, Value> equation) throws IOException { + ProgressManager.checkCanceled(); + + Result<Key, Value> rhs = equation.rhs; + IntIdResult result; + if (rhs instanceof Final) { + result = new IntIdFinal(((Final<Key, Value>)rhs).value); + } else { + Pending<Key, Value> pending = (Pending<Key, Value>)rhs; + Set<Product<Key, Value>> sumOrigin = pending.sum; + IntIdComponent[] components = new IntIdComponent[sumOrigin.size()]; + int componentI = 0; + for (Product<Key, Value> prod : sumOrigin) { + int[] intProd = new int[prod.ids.size()]; + int idI = 0; + for (Key id : prod.ids) { + int rawId = mkAsmKey(id); + if (rawId <= 0) { + LOG.error("raw key should be positive. rawId = " + rawId); + } + intProd[idI] = id.stable ? rawId : -rawId; + idI++; + } + IntIdComponent intIdComponent = new IntIdComponent(prod.value, intProd); + components[componentI] = intIdComponent; + componentI++; + } + result = new IntIdPending(components); + } + + int rawKey = mkAsmKey(equation.id); + if (rawKey <= 0) { + LOG.error("raw key should be positive. rawKey = " + rawKey); + } + + int key = equation.id.stable ? rawKey : -rawKey; + return new IntIdEquation(key, result); + } + + public int mkAsmKey(@NotNull Key key) throws IOException { + return myCompoundKeyEnumerator.enumerate(new int[]{mkDirectionKey(key.direction), mkAsmSignatureKey(key.method)}); + } + + private int mkDirectionKey(Direction dir) throws IOException { + return myCompoundKeyEnumerator.enumerate(new int[]{dir.directionId(), dir.paramId(), dir.valueId()}); + } + + // class + short signature + private int mkAsmSignatureKey(@NotNull Method method) throws IOException { + int[] sigKey = new int[2]; + sigKey[0] = mkAsmTypeKey(Type.getObjectType(method.internalClassName)); + sigKey[1] = mkAsmShortSignatureKey(method); + return myCompoundKeyEnumerator.enumerate(sigKey); + } + + private int mkAsmShortSignatureKey(@NotNull Method method) throws IOException { + Type[] argTypes = Type.getArgumentTypes(method.methodDesc); + int arity = argTypes.length; + int[] sigKey = new int[3 + arity]; + sigKey[0] = mkAsmTypeKey(Type.getReturnType(method.methodDesc)); + sigKey[1] = myNamesEnumerator.enumerate(method.methodName); + sigKey[2] = argTypes.length; + for (int i = 0; i < argTypes.length; i++) { + sigKey[3 + i] = mkAsmTypeKey(argTypes[i]); + } + return myCompoundKeyEnumerator.enumerate(sigKey); + } + + @Nullable + private static Direction extractDirection(int[] directionKey) { + switch (directionKey[0]) { + case Direction.OUT_DIRECTION: + return new Out(); + case Direction.IN_DIRECTION: + return new In(directionKey[1]); + case Direction.INOUT_DIRECTION: + return new InOut(directionKey[1], Value.values()[directionKey[2]]); + } + return null; + } + + private int mkAsmTypeKey(Type type) throws IOException { + String className = type.getClassName(); + int dotIndex = className.lastIndexOf('.'); + String packageName; + String simpleName; + if (dotIndex > 0) { + packageName = className.substring(0, dotIndex); + simpleName = className.substring(dotIndex + 1); + } else { + packageName = ""; + simpleName = className; + } + int[] classKey = new int[]{myNamesEnumerator.enumerate(packageName), myNamesEnumerator.enumerate(simpleName)}; + return myCompoundKeyEnumerator.enumerate(classKey); + } + + public int mkPsiKey(@NotNull PsiMethod psiMethod, Direction direction) throws IOException { + final PsiClass psiClass = PsiTreeUtil.getParentOfType(psiMethod, PsiClass.class, false); + if (psiClass == null) { + LOG.debug("PsiClass was null for " + psiMethod.getName()); + return -1; + } + int sigKey = mkPsiSignatureKey(psiMethod); + if (sigKey == -1) { + return -1; + } + return myCompoundKeyEnumerator.enumerate(new int[]{mkDirectionKey(direction), sigKey}); + + } + + private int mkPsiSignatureKey(@NotNull PsiMethod psiMethod) throws IOException { + final PsiClass psiClass = PsiTreeUtil.getParentOfType(psiMethod, PsiClass.class, false); + if (psiClass == null) { + LOG.debug("PsiClass was null for " + psiMethod.getName()); + return -1; + } + PsiClass outerClass = psiClass.getContainingClass(); + boolean isInnerClassConstructor = psiMethod.isConstructor() && (outerClass != null) && !psiClass.hasModifierProperty(PsiModifier.STATIC); + PsiParameter[] parameters = psiMethod.getParameterList().getParameters(); + PsiType returnType = psiMethod.getReturnType(); + + final int shift = isInnerClassConstructor ? 1 : 0; + final int arity = parameters.length + shift; + int[] shortSigKey = new int[3 + arity]; + if (returnType == null) { + shortSigKey[0] = mkPsiTypeKey(PsiType.VOID); + shortSigKey[1] = myNamesEnumerator.enumerate("<init>"); + } else { + shortSigKey[0] = mkPsiTypeKey(returnType); + shortSigKey[1] = myNamesEnumerator.enumerate(psiMethod.getName()); + } + shortSigKey[2] = arity; + if (isInnerClassConstructor) { + shortSigKey[3] = mkPsiClassKey(outerClass, 0); + } + for (int i = 0; i < parameters.length; i++) { + PsiParameter parameter = parameters[i]; + shortSigKey[3 + i + shift] = mkPsiTypeKey(parameter.getType()); + } + for (int aShortSigKey : shortSigKey) { + if (aShortSigKey == -1) { + return -1; + } + } + + int[] sigKey = new int[2]; + int classKey = mkPsiClassKey(psiClass, 0); + if (classKey == -1) { + return -1; + } + sigKey[0] = classKey; + sigKey[1] = myCompoundKeyEnumerator.enumerate(shortSigKey); + + return myCompoundKeyEnumerator.enumerate(sigKey); + } + + + private int mkPsiClassKey(PsiClass psiClass, int dimensions) throws IOException { + PsiFile containingFile = psiClass.getContainingFile(); + if (!(containingFile instanceof PsiClassOwner)) { + LOG.debug("containingFile was not resolved for " + psiClass.getQualifiedName()); + return -1; + } + PsiClassOwner psiFile = (PsiClassOwner)containingFile; + String packageName = psiFile.getPackageName(); + String qname = psiClass.getQualifiedName(); + if (qname == null) { + return -1; + } + String className = qname; + if (packageName.length() > 0) { + className = qname.substring(packageName.length() + 1).replace('.', '$'); + } + int[] classKey = new int[2]; + classKey[0] = myNamesEnumerator.enumerate(packageName); + if (dimensions == 0) { + classKey[1] = myNamesEnumerator.enumerate(className); + } else { + StringBuilder sb = new StringBuilder(className); + for (int j = 0; j < dimensions; j++) { + sb.append("[]"); + } + classKey[1] = myNamesEnumerator.enumerate(sb.toString()); + } + return myCompoundKeyEnumerator.enumerate(classKey); + } + + private int mkPsiTypeKey(PsiType psiType) throws IOException { + int dimensions = 0; + psiType = TypeConversionUtil.erasure(psiType); + if (psiType instanceof PsiArrayType) { + PsiArrayType arrayType = (PsiArrayType)psiType; + psiType = arrayType.getDeepComponentType(); + dimensions = arrayType.getArrayDimensions(); + } + + if (psiType instanceof PsiClassType) { + // no resolve() -> no package/class split + PsiClass psiClass = ((PsiClassType)psiType).resolve(); + if (psiClass != null) { + return mkPsiClassKey(psiClass, dimensions); + } + else { + LOG.debug("resolve was null for " + ((PsiClassType)psiType).getClassName()); + return -1; + } + } + else if (psiType instanceof PsiPrimitiveType) { + String packageName = ""; + String className = psiType.getPresentableText(); + int[] classKey = new int[2]; + classKey[0] = myNamesEnumerator.enumerate(packageName); + if (dimensions == 0) { + classKey[1] = myNamesEnumerator.enumerate(className); + } else { + StringBuilder sb = new StringBuilder(className); + for (int j = 0; j < dimensions; j++) { + sb.append("[]"); + } + classKey[1] = myNamesEnumerator.enumerate(sb.toString()); + } + return myCompoundKeyEnumerator.enumerate(classKey); + } + return -1; + } + + public void addAnnotations(TIntObjectHashMap<Value> internalIdSolutions, Annotations annotations) { + + TIntObjectHashMap<List<String>> contractClauses = new TIntObjectHashMap<List<String>>(); + TIntObjectIterator<Value> solutionsIterator = internalIdSolutions.iterator(); + + TIntHashSet notNulls = annotations.notNulls; + TIntObjectHashMap<String> contracts = annotations.contracts; + + for (int i = internalIdSolutions.size(); i-- > 0;) { + solutionsIterator.advance(); + int key = Math.abs(solutionsIterator.key()); + Value value = solutionsIterator.value(); + if (value == Value.Top || value == Value.Bot) { + continue; + } + try { + int[] compoundKey = myCompoundKeyEnumerator.valueOf(key); + Direction direction = extractDirection(myCompoundKeyEnumerator.valueOf(compoundKey[0])); + if (value == Value.NotNull && (direction instanceof In || direction instanceof Out)) { + notNulls.add(key); + } + else if (direction instanceof InOut) { + compoundKey = new int[]{mkDirectionKey(new Out()), compoundKey[1]}; + try { + int baseKey = myCompoundKeyEnumerator.enumerate(compoundKey); + List<String> clauses = contractClauses.get(baseKey); + if (clauses == null) { + clauses = new ArrayList<String>(); + contractClauses.put(baseKey, clauses); + } + int[] sig = myCompoundKeyEnumerator.valueOf(compoundKey[1]); + int[] shortSig = myCompoundKeyEnumerator.valueOf(sig[1]); + int arity = shortSig[2]; + clauses.add(contractElement(arity, (InOut)direction, value)); + } + catch (IOException e) { + LOG.debug(e); + } + } + } + catch (IOException e) { + LOG.debug(e); + } + } + + TIntObjectIterator<List<String>> buildersIterator = contractClauses.iterator(); + for (int i = contractClauses.size(); i-- > 0;) { + buildersIterator.advance(); + int key = buildersIterator.key(); + if (!notNulls.contains(key)) { + List<String> clauses = buildersIterator.value(); + Collections.sort(clauses); + StringBuilder sb = new StringBuilder("\""); + StringUtil.join(clauses, ";", sb); + sb.append('"'); + contracts.put(key, sb.toString().intern()); + } + } + } + + static String contractValueString(Value v) { + switch (v) { + case False: return "false"; + case True: return "true"; + case NotNull: return "!null"; + case Null: return "null"; + default: return "_"; + } + } + + static String contractElement(int arity, InOut inOut, Value value) { + StringBuilder sb = new StringBuilder(); + for (int i = 0; i < arity; i++) { + Value currentValue = Value.Top; + if (i == inOut.paramIndex) { + currentValue = inOut.inValue; + } + if (i > 0) { + sb.append(','); + } + sb.append(contractValueString(currentValue)); + } + sb.append("->"); + sb.append(contractValueString(value)); + return sb.toString(); + } + + public int getVersion() { + return version; + } + + private static class IntArrayKeyDescriptor implements KeyDescriptor<int[]> { + + @Override + public void save(@NotNull DataOutput out, int[] value) throws IOException { + DataInputOutputUtil.writeINT(out, value.length); + for (int i : value) { + DataInputOutputUtil.writeINT(out, i); + } + } + + @Override + public int[] read(@NotNull DataInput in) throws IOException { + int[] value = new int[DataInputOutputUtil.readINT(in)]; + for (int i = 0; i < value.length; i++) { + value[i] = DataInputOutputUtil.readINT(in); + } + return value; + } + + @Override + public int getHashCode(int[] value) { + return Arrays.hashCode(value); + } + + @Override + public boolean isEqual(int[] val1, int[] val2) { + return Arrays.equals(val1, val2); + } + } + + private static class IntArrayPersistentEnumerator extends PersistentEnumeratorDelegate<int[]> { + private final CachingEnumerator<int[]> myCache; + + public IntArrayPersistentEnumerator(File compoundKeysFile, IntArrayKeyDescriptor descriptor) throws IOException { + super(compoundKeysFile, descriptor, 1024 * 4); + myCache = new CachingEnumerator<int[]>(new DataEnumerator<int[]>() { + @Override + public int enumerate(@Nullable int[] value) throws IOException { + return IntArrayPersistentEnumerator.super.enumerate(value); + } + + @Nullable + @Override + public int[] valueOf(int idx) throws IOException { + return IntArrayPersistentEnumerator.super.valueOf(idx); + } + }, descriptor); + } + + @Override + public int enumerate(@Nullable int[] value) throws IOException { + return myCache.enumerate(value); + } + + @Nullable + @Override + public int[] valueOf(int idx) throws IOException { + return myCache.valueOf(idx); + } + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisIndex.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisIndex.java new file mode 100644 index 000000000000..6a4b32783c95 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisIndex.java @@ -0,0 +1,167 @@ +/* + * 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.ide.highlighter.JavaClassFileType; +import com.intellij.openapi.application.Application; +import com.intellij.openapi.application.ApplicationManager; +import com.intellij.openapi.vfs.VirtualFile; +import com.intellij.openapi.vfs.VirtualFileWithId; +import com.intellij.util.SystemProperties; +import com.intellij.util.indexing.*; +import com.intellij.util.io.DataExternalizer; +import com.intellij.util.io.DataInputOutputUtil; +import com.intellij.util.io.EnumeratorIntegerDescriptor; +import com.intellij.util.io.KeyDescriptor; +import org.jetbrains.annotations.NotNull; + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; +import java.util.ArrayList; +import java.util.Collection; + +/** + * @author lambdamix + */ +public class BytecodeAnalysisIndex extends FileBasedIndexExtension<Integer, Collection<IntIdEquation>> { + public static final ID<Integer, Collection<IntIdEquation>> NAME = ID.create("bytecodeAnalysis"); + private final EquationExternalizer myExternalizer = new EquationExternalizer(); + private static final DataIndexer<Integer, Collection<IntIdEquation>, FileContent> INDEXER = + new ClassDataIndexer(BytecodeAnalysisConverter.getInstance()); + + private static final int ourInternalVersion = 2; + private static boolean ourEnabled = SystemProperties.getBooleanProperty("idea.enable.bytecode.contract.inference", isEnabledByDefault()); + + private static boolean isEnabledByDefault() { + Application application = ApplicationManager.getApplication(); + return application.isInternal() || application.isUnitTestMode(); + } + + public static int indexKey(VirtualFile file, boolean parameters) { + return (file instanceof VirtualFileWithId ? ((VirtualFileWithId)file).getId() * 2 : -2) + (parameters ? 1 : 0); + } + + @NotNull + @Override + public ID<Integer, Collection<IntIdEquation>> getName() { + return NAME; + } + + @NotNull + @Override + public DataIndexer<Integer, Collection<IntIdEquation>, FileContent> getIndexer() { + return INDEXER; + } + + @NotNull + @Override + public KeyDescriptor<Integer> getKeyDescriptor() { + return EnumeratorIntegerDescriptor.INSTANCE; + } + + @NotNull + @Override + public DataExternalizer<Collection<IntIdEquation>> getValueExternalizer() { + return myExternalizer; + } + + @NotNull + @Override + public FileBasedIndex.InputFilter getInputFilter() { + return new DefaultFileTypeSpecificInputFilter(JavaClassFileType.INSTANCE) { + @Override + public boolean acceptInput(@NotNull VirtualFile file) { + return ourEnabled && super.acceptInput(file); + } + }; + } + + @Override + public boolean dependsOnFileContent() { + return true; + } + + @Override + public int getVersion() { + return ourInternalVersion + BytecodeAnalysisConverter.getInstance().getVersion() + (ourEnabled ? 0xFF : 0); + } + + public static class EquationExternalizer implements DataExternalizer<Collection<IntIdEquation>> { + @Override + public void save(@NotNull DataOutput out, Collection<IntIdEquation> equations) throws IOException { + DataInputOutputUtil.writeINT(out, equations.size()); + + for (IntIdEquation equation : equations) { + out.writeInt(equation.id); + IntIdResult rhs = equation.rhs; + if (rhs instanceof IntIdFinal) { + IntIdFinal finalResult = (IntIdFinal)rhs; + out.writeBoolean(true); // final flag + DataInputOutputUtil.writeINT(out, finalResult.value.ordinal()); + } else { + IntIdPending pendResult = (IntIdPending)rhs; + out.writeBoolean(false); // pending flag + DataInputOutputUtil.writeINT(out, pendResult.delta.length); + + for (IntIdComponent component : pendResult.delta) { + DataInputOutputUtil.writeINT(out, component.value.ordinal()); + int[] ids = component.ids; + DataInputOutputUtil.writeINT(out, ids.length); + for (int id : ids) { + out.writeInt(id); + } + } + } + } + } + + @Override + public Collection<IntIdEquation> read(@NotNull DataInput in) throws IOException { + + int size = DataInputOutputUtil.readINT(in); + ArrayList<IntIdEquation> result = new ArrayList<IntIdEquation>(size); + + for (int x = 0; x < size; x++) { + int equationId = in.readInt(); + boolean isFinal = in.readBoolean(); // flag + if (isFinal) { + int ordinal = DataInputOutputUtil.readINT(in); + Value value = Value.values()[ordinal]; + result.add(new IntIdEquation(equationId, new IntIdFinal(value))); + } else { + + int sumLength = DataInputOutputUtil.readINT(in); + IntIdComponent[] components = new IntIdComponent[sumLength]; + + for (int i = 0; i < sumLength; i++) { + int ordinal = DataInputOutputUtil.readINT(in); + Value value = Value.values()[ordinal]; + int componentSize = DataInputOutputUtil.readINT(in); + int[] ids = new int[componentSize]; + for (int j = 0; j < componentSize; j++) { + ids[j] = in.readInt(); + } + components[i] = new IntIdComponent(value, ids); + } + result.add(new IntIdEquation(equationId, new IntIdPending(components))); + } + } + + return result; + } + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ClassDataIndexer.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ClassDataIndexer.java new file mode 100644 index 000000000000..5e74a8b5dbb3 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ClassDataIndexer.java @@ -0,0 +1,264 @@ +/* + * 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.openapi.progress.ProcessCanceledException; +import com.intellij.openapi.progress.ProgressManager; +import com.intellij.openapi.util.NotNullLazyValue; +import com.intellij.util.indexing.DataIndexer; +import com.intellij.util.indexing.FileContent; +import gnu.trove.TIntHashSet; +import org.jetbrains.annotations.NotNull; +import org.jetbrains.org.objectweb.asm.*; +import org.jetbrains.org.objectweb.asm.tree.MethodNode; +import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException; + +import java.util.*; + +import static com.intellij.codeInspection.bytecodeAnalysis.ProjectBytecodeAnalysis.LOG; + +/** + * @author lambdamix + */ +public class ClassDataIndexer implements DataIndexer<Integer, Collection<IntIdEquation>, FileContent> { + final BytecodeAnalysisConverter myConverter; + + public ClassDataIndexer(BytecodeAnalysisConverter converter) { + myConverter = converter; + } + + @NotNull + @Override + public Map<Integer, Collection<IntIdEquation>> map(@NotNull FileContent inputData) { + HashMap<Integer, Collection<IntIdEquation>> map = new HashMap<Integer, Collection<IntIdEquation>>(2); + try { + ClassEquations rawEquations = processClass(new ClassReader(inputData.getContent())); + List<Equation<Key, Value>> rawParameterEquations = rawEquations.parameterEquations; + List<Equation<Key, Value>> rawContractEquations = rawEquations.contractEquations; + + Collection<IntIdEquation> idParameterEquations = new ArrayList<IntIdEquation>(rawParameterEquations.size()); + Collection<IntIdEquation> idContractEquations = new ArrayList<IntIdEquation>(rawContractEquations.size()); + + map.put(BytecodeAnalysisIndex.indexKey(inputData.getFile(), true), idParameterEquations); + map.put(BytecodeAnalysisIndex.indexKey(inputData.getFile(), false), idContractEquations); + + + for (Equation<Key, Value> rawParameterEquation: rawParameterEquations) { + idParameterEquations.add(myConverter.convert(rawParameterEquation)); + } + for (Equation<Key, Value> rawContractEquation: rawContractEquations) { + idContractEquations.add(myConverter.convert(rawContractEquation)); + } + } + catch (ProcessCanceledException e) { + throw e; + } + catch (Throwable e) { + // incorrect bytecode may result in Runtime exceptions during analysis + // so here we suppose that exception is due to incorrect bytecode + LOG.debug("Unexpected Error during indexing of bytecode", e); + } + return map; + } + + private static class ClassEquations { + final List<Equation<Key, Value>> parameterEquations; + final List<Equation<Key, Value>> contractEquations; + + private ClassEquations(List<Equation<Key, Value>> parameterEquations, List<Equation<Key, Value>> contractEquations) { + this.parameterEquations = parameterEquations; + this.contractEquations = contractEquations; + } + } + + public static ClassEquations processClass(final ClassReader classReader) { + final List<Equation<Key, Value>> parameterEquations = new ArrayList<Equation<Key, Value>>(); + final List<Equation<Key, Value>> contractEquations = new ArrayList<Equation<Key, Value>>(); + + classReader.accept(new ClassVisitor(Opcodes.ASM5) { + private boolean stableClass; + + @Override + public void visit(int version, int access, String name, String signature, String superName, String[] interfaces) { + stableClass = (access & Opcodes.ACC_FINAL) != 0; + super.visit(version, access, name, signature, superName, interfaces); + } + + @Override + public MethodVisitor visitMethod(int access, String name, String desc, String signature, String[] exceptions) { + final MethodNode node = new MethodNode(Opcodes.ASM5, access, name, desc, signature, exceptions); + return new MethodVisitor(Opcodes.ASM5, node) { + @Override + public void visitEnd() { + super.visitEnd(); + processMethod(classReader.getClassName(), node, stableClass); + } + }; + } + + void processMethod(final String className, final MethodNode methodNode, boolean stableClass) { + ProgressManager.checkCanceled(); + Type[] argumentTypes = Type.getArgumentTypes(methodNode.desc); + Type resultType = Type.getReturnType(methodNode.desc); + int resultSort = resultType.getSort(); + boolean isReferenceResult = resultSort == Type.OBJECT || resultSort == Type.ARRAY; + boolean isBooleanResult = Type.BOOLEAN_TYPE == resultType; + boolean isInterestingResult = isReferenceResult || isBooleanResult; + + if (argumentTypes.length == 0 && !isInterestingResult) { + return; + } + + Method method = new Method(className, methodNode.name, methodNode.desc); + int access = methodNode.access; + boolean stable = + stableClass || + (access & Opcodes.ACC_FINAL) != 0 || + (access & Opcodes.ACC_PRIVATE) != 0 || + (access & Opcodes.ACC_STATIC) != 0 || + "<init>".equals(methodNode.name); + try { + boolean added = false; + ControlFlowGraph graph = cfg.buildControlFlowGraph(className, methodNode); + + boolean maybeLeakingParameter = false; + for (Type argType : argumentTypes) { + int argSort = argType.getSort(); + if (argSort == Type.OBJECT || argSort == Type.ARRAY || (isInterestingResult && Type.BOOLEAN_TYPE.equals(argType))) { + maybeLeakingParameter = true; + break; + } + } + + if (graph.transitions.length > 0) { + DFSTree dfs = cfg.buildDFSTree(graph.transitions); + boolean reducible = dfs.back.isEmpty() || cfg.reducible(graph, dfs); + if (reducible) { + NotNullLazyValue<TIntHashSet> resultOrigins = new NotNullLazyValue<TIntHashSet>() { + @NotNull + @Override + protected TIntHashSet compute() { + try { + return cfg.resultOrigins(className, methodNode); + } + catch (AnalyzerException e) { + throw new RuntimeException(e); + } + } + }; + boolean[] leakingParameters = maybeLeakingParameter ? cfg.leakingParameters(className, methodNode) : null; + boolean shouldComputeResult = isReferenceResult; + + if (!shouldComputeResult && isInterestingResult && maybeLeakingParameter) { + loop: for (int i = 0; i < argumentTypes.length; i++) { + Type argType = argumentTypes[i]; + int argSort = argType.getSort(); + boolean isReferenceArg = argSort == Type.OBJECT || argSort == Type.ARRAY; + boolean isBooleanArg = Type.BOOLEAN_TYPE.equals(argType); + if ((isReferenceArg || isBooleanArg) && !leakingParameters[i]) { + shouldComputeResult = true; + break loop; + } + } + } + + Equation<Key, Value> resultEquation = + shouldComputeResult ? new InOutAnalysis(new RichControlFlow(graph, dfs), new Out(), resultOrigins.getValue(), stable).analyze() : null; + + for (int i = 0; i < argumentTypes.length; i++) { + Type argType = argumentTypes[i]; + int argSort = argType.getSort(); + boolean isReferenceArg = argSort == Type.OBJECT || argSort == Type.ARRAY; + boolean isBooleanArg = Type.BOOLEAN_TYPE.equals(argType); + if (isReferenceArg) { + if (leakingParameters[i]) { + parameterEquations.add(new NonNullInAnalysis(new RichControlFlow(graph, dfs), new In(i), stable).analyze()); + } else { + parameterEquations.add(new Equation<Key, Value>(new Key(method, new In(i), stable), new Final<Key, Value>(Value.Top))); + } + } + if (isReferenceArg && isInterestingResult) { + if (leakingParameters[i]) { + contractEquations.add(new InOutAnalysis(new RichControlFlow(graph, dfs), new InOut(i, Value.Null), resultOrigins.getValue(), stable).analyze()); + contractEquations.add(new InOutAnalysis(new RichControlFlow(graph, dfs), new InOut(i, Value.NotNull), resultOrigins.getValue(), stable).analyze()); + } else { + contractEquations.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.Null), stable), resultEquation.rhs)); + contractEquations.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.NotNull), stable), resultEquation.rhs)); + } + } + if (isBooleanArg && isInterestingResult) { + if (leakingParameters[i]) { + contractEquations.add(new InOutAnalysis(new RichControlFlow(graph, dfs), new InOut(i, Value.False), resultOrigins.getValue(), stable).analyze()); + contractEquations.add(new InOutAnalysis(new RichControlFlow(graph, dfs), new InOut(i, Value.True), resultOrigins.getValue(), stable).analyze()); + } else { + contractEquations.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.False), stable), resultEquation.rhs)); + contractEquations.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.True), stable), resultEquation.rhs)); + } + } + } + if (isReferenceResult) { + if (resultEquation != null) { + contractEquations.add(resultEquation); + } else { + contractEquations.add(new InOutAnalysis(new RichControlFlow(graph, dfs), new Out(), resultOrigins.getValue(), stable).analyze()); + } + } + added = true; + } + else { + LOG.debug("CFG for " + method + " is not reducible"); + } + } + + if (!added) { + method = new Method(className, methodNode.name, methodNode.desc); + for (int i = 0; i < argumentTypes.length; i++) { + Type argType = argumentTypes[i]; + int argSort = argType.getSort(); + boolean isReferenceArg = argSort == Type.OBJECT || argSort == Type.ARRAY; + boolean isBooleanArg = Type.BOOLEAN_TYPE.equals(argType); + + if (isReferenceArg) { + parameterEquations.add(new Equation<Key, Value>(new Key(method, new In(i), stable), new Final<Key, Value>(Value.Top))); + } + if (isReferenceArg && isInterestingResult) { + contractEquations.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.Null), stable), new Final<Key, Value>(Value.Top))); + contractEquations.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.NotNull), stable), new Final<Key, Value>(Value.Top))); + } + if (isBooleanArg && isInterestingResult) { + contractEquations.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.False), stable), new Final<Key, Value>(Value.Top))); + contractEquations.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.True), stable), new Final<Key, Value>(Value.Top))); + } + } + if (isReferenceResult) { + contractEquations.add(new Equation<Key, Value>(new Key(method, new Out(), stable), new Final<Key, Value>(Value.Top))); + } + } + } + catch (ProcessCanceledException e) { + throw e; + } + catch (Throwable e) { + // incorrect bytecode may result in Runtime exceptions during analysis + // so here we suppose that exception is due to incorrect bytecode + LOG.debug("Unexpected Error during processing of " + method, e); + } + } + }, ClassReader.SKIP_DEBUG | ClassReader.SKIP_FRAMES); + + return new ClassEquations(parameterEquations, contractEquations); + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Contracts.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Contracts.java new file mode 100644 index 000000000000..c837b127b74b --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Contracts.java @@ -0,0 +1,439 @@ +/* + * 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 gnu.trove.TIntHashSet; +import org.jetbrains.org.objectweb.asm.Handle; +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.*; + +import static com.intellij.codeInspection.bytecodeAnalysis.AbstractValues.*; +import static org.jetbrains.org.objectweb.asm.Opcodes.*; + +class InOutAnalysis extends Analysis<Result<Key, Value>> { + + final ResultUtil<Key, Value> resultUtil = + new ResultUtil<Key, Value>(new ELattice<Value>(Value.Bot, Value.Top)); + + private final InOutInterpreter interpreter; + private final Value inValue; + + protected InOutAnalysis(RichControlFlow richControlFlow, Direction direction, TIntHashSet resultOrigins, boolean stable) { + super(richControlFlow, direction, stable); + interpreter = new InOutInterpreter(direction, richControlFlow.controlFlow.methodNode.instructions, resultOrigins); + inValue = direction instanceof InOut ? ((InOut)direction).inValue : null; + } + + @Override + Result<Key, Value> identity() { + return new Final<Key, Value>(Value.Bot); + } + + @Override + Result<Key, Value> combineResults(Result<Key, Value> delta, List<Result<Key, Value>> subResults) { + Result<Key, Value> result = null; + for (Result<Key, Value> subResult : subResults) { + if (result == null) { + result = subResult; + } else { + result = resultUtil.join(result, subResult); + } + } + return result; + } + + @Override + boolean isEarlyResult(Result<Key, Value> res) { + if (res instanceof Final) { + return ((Final<?, Value>)res).value == Value.Top; + } + return false; + } + + @Override + Equation<Key, Value> mkEquation(Result<Key, Value> res) { + return new Equation<Key, Value>(aKey, res); + } + + private int id = 0; + + @Override + void processState(State state) throws AnalyzerException { + int stateIndex = state.index; + Conf preConf = state.conf; + int insnIndex = preConf.insnIndex; + boolean loopEnter = dfsTree.loopEnters.contains(insnIndex); + Conf conf = loopEnter ? generalize(preConf) : preConf; + 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.contains(insnIndex) ? append(history, conf) : history; + Frame<BasicValue> nextFrame = execute(frame, insnNode); + + if (interpreter.deReferenced) { + results.put(stateIndex, new Final<Key, Value>(Value.Bot)); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + return; + } + + int opcode = insnNode.getOpcode(); + switch (opcode) { + case ARETURN: + case IRETURN: + case LRETURN: + case FRETURN: + case DRETURN: + case RETURN: + BasicValue stackTop = popValue(frame); + if (FalseValue == stackTop) { + results.put(stateIndex, new Final<Key, Value>(Value.False)); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + } + else if (TrueValue == stackTop) { + results.put(stateIndex, new Final<Key, Value>(Value.True)); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + } + else if (NullValue == stackTop) { + results.put(stateIndex, new Final<Key, Value>(Value.Null)); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + } + else if (stackTop instanceof NotNullValue) { + results.put(stateIndex, new Final<Key, Value>(Value.NotNull)); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + } + else if (stackTop instanceof ParamValue) { + results.put(stateIndex, new Final<Key, Value>(inValue)); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + } + else if (stackTop instanceof CallResultValue) { + Set<Key> keys = ((CallResultValue) stackTop).inters; + results.put(stateIndex, new Pending<Key, Value>(Collections.singleton(new Product<Key, Value>(Value.Top, keys)))); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + } + else { + earlyResult = new Final<Key, Value>(Value.Top); + } + return; + case ATHROW: + results.put(stateIndex, new Final<Key, Value>(Value.Bot)); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + return; + default: + } + + if (opcode == IFNONNULL && popValue(frame) instanceof ParamValue) { + int nextInsnIndex = inValue == Value.Null ? insnIndex + 1 : methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false); + pending.push(new MakeResult<Result<Key, Value>>(state, myIdentity, new int[]{nextState.index})); + pending.push(new ProceedState<Result<Key, Value>>(nextState)); + return; + } + + if (opcode == IFNULL && popValue(frame) instanceof ParamValue) { + int nextInsnIndex = inValue == Value.NotNull ? insnIndex + 1 : methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false); + pending.push(new MakeResult<Result<Key, Value>>(state, myIdentity, new int[]{nextState.index})); + pending.push(new ProceedState<Result<Key, Value>>(nextState)); + return; + } + + if (opcode == IFEQ && popValue(frame) == InstanceOfCheckValue && inValue == Value.Null) { + int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false); + pending.push(new MakeResult<Result<Key, Value>>(state, myIdentity, new int[]{nextState.index})); + pending.push(new ProceedState<Result<Key, Value>>(nextState)); + return; + } + + if (opcode == IFNE && popValue(frame) == InstanceOfCheckValue && inValue == Value.Null) { + int nextInsnIndex = insnIndex + 1; + State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false); + pending.push(new MakeResult<Result<Key, Value>>(state, myIdentity, new int[]{nextState.index})); + pending.push(new ProceedState<Result<Key, Value>>(nextState)); + return; + } + + if (opcode == IFEQ && popValue(frame) instanceof ParamValue) { + int nextInsnIndex = inValue == Value.True ? insnIndex + 1 : methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false); + pending.push(new MakeResult<Result<Key, Value>>(state, myIdentity, new int[]{nextState.index})); + pending.push(new ProceedState<Result<Key, Value>>(nextState)); + return; + } + + if (opcode == IFNE && popValue(frame) instanceof ParamValue) { + int nextInsnIndex = inValue == Value.False ? insnIndex + 1 : methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false); + pending.push(new MakeResult<Result<Key, Value>>(state, myIdentity, new int[]{nextState.index})); + pending.push(new ProceedState<Result<Key, Value>>(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++) { + int nextInsnIndex = nextInsnIndices[i]; + Frame<BasicValue> nextFrame1 = nextFrame; + if (controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { + nextFrame1 = new Frame<BasicValue>(frame); + nextFrame1.clearStack(); + nextFrame1.push(new BasicValue(Type.getType("java/lang/Throwable"))); + } + nextStates.add(new State(++id, new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, false)); + subIndices[i] = id; + } + + pending.push(new MakeResult<Result<Key, Value>>(state, myIdentity, subIndices)); + for (State nextState : nextStates) { + pending.push(new ProceedState<Result<Key, Value>>(nextState)); + } + } + + private Frame<BasicValue> execute(Frame<BasicValue> frame, AbstractInsnNode insnNode) throws AnalyzerException { + interpreter.deReferenced = false; + switch (insnNode.getType()) { + case AbstractInsnNode.LABEL: + case AbstractInsnNode.LINE: + case AbstractInsnNode.FRAME: + return frame; + default: + Frame<BasicValue> nextFrame = new Frame<BasicValue>(frame); + nextFrame.execute(insnNode, interpreter); + return nextFrame; + } + } + + private static Conf generalize(Conf conf) { + Frame<BasicValue> frame = new Frame<BasicValue>(conf.frame); + for (int i = 0; i < frame.getLocals(); i++) { + BasicValue value = frame.getLocal(i); + Class<?> valueClass = value.getClass(); + if (valueClass != BasicValue.class && valueClass != ParamValue.class) { + frame.setLocal(i, new BasicValue(value.getType())); + } + } + + BasicValue[] stack = new BasicValue[frame.getStackSize()]; + for (int i = 0; i < frame.getStackSize(); i++) { + stack[i] = frame.getStack(i); + } + frame.clearStack(); + + for (BasicValue value : stack) { + Class<?> valueClass = value.getClass(); + if (valueClass != BasicValue.class && valueClass != ParamValue.class) { + frame.push(new BasicValue(value.getType())); + } else { + frame.push(value); + } + } + + return new Conf(conf.insnIndex, frame); + } +} + +class InOutInterpreter extends BasicInterpreter { + final Direction direction; + final InsnList insns; + final TIntHashSet resultOrigins; + final boolean nullAnalysis; + + boolean deReferenced = false; + + InOutInterpreter(Direction direction, InsnList insns, TIntHashSet resultOrigins) { + this.direction = direction; + this.insns = insns; + this.resultOrigins = resultOrigins; + nullAnalysis = (direction instanceof InOut) && (((InOut)direction).inValue) == Value.Null; + } + + @Override + public BasicValue newOperation(AbstractInsnNode insn) throws AnalyzerException { + boolean propagate = resultOrigins.contains(insns.indexOf(insn)); + if (propagate) { + switch (insn.getOpcode()) { + case ICONST_0: + return FalseValue; + case ICONST_1: + return TrueValue; + case ACONST_NULL: + return NullValue; + case LDC: + Object cst = ((LdcInsnNode)insn).cst; + if (cst instanceof Type) { + Type type = (Type)cst; + if (type.getSort() == Type.OBJECT || type.getSort() == Type.ARRAY) { + return new NotNullValue(Type.getObjectType("java/lang/Class")); + } + if (type.getSort() == Type.METHOD) { + return new NotNullValue(Type.getObjectType("java/lang/invoke/MethodType")); + } + } + else if (cst instanceof String) { + return new NotNullValue(Type.getObjectType("java/lang/String")); + } + else if (cst instanceof Handle) { + return new NotNullValue(Type.getObjectType("java/lang/invoke/MethodHandle")); + } + break; + case NEW: + return new NotNullValue(Type.getObjectType(((TypeInsnNode)insn).desc)); + default: + } + } + return super.newOperation(insn); + } + + @Override + public BasicValue unaryOperation(AbstractInsnNode insn, BasicValue value) throws AnalyzerException { + boolean propagate = resultOrigins.contains(insns.indexOf(insn)); + switch (insn.getOpcode()) { + case GETFIELD: + case ARRAYLENGTH: + case MONITORENTER: + if (nullAnalysis && value instanceof ParamValue) { + deReferenced = true; + } + return super.unaryOperation(insn, value); + case CHECKCAST: + if (value instanceof ParamValue) { + return new ParamValue(Type.getObjectType(((TypeInsnNode)insn).desc)); + } + break; + case INSTANCEOF: + if (value instanceof ParamValue) { + return InstanceOfCheckValue; + } + break; + case NEWARRAY: + case ANEWARRAY: + if (propagate) { + return new NotNullValue(super.unaryOperation(insn, value).getType()); + } + break; + default: + } + return super.unaryOperation(insn, value); + } + + @Override + public BasicValue binaryOperation(AbstractInsnNode insn, BasicValue value1, BasicValue value2) throws AnalyzerException { + switch (insn.getOpcode()) { + case IALOAD: + case LALOAD: + case FALOAD: + case DALOAD: + case AALOAD: + case BALOAD: + case CALOAD: + case SALOAD: + case PUTFIELD: + if (nullAnalysis && value1 instanceof ParamValue) { + deReferenced = true; + } + break; + default: + } + return super.binaryOperation(insn, value1, value2); + } + + @Override + public BasicValue ternaryOperation(AbstractInsnNode insn, BasicValue value1, BasicValue value2, BasicValue value3) throws AnalyzerException { + switch (insn.getOpcode()) { + case IASTORE: + case LASTORE: + case FASTORE: + case DASTORE: + case AASTORE: + case BASTORE: + case CASTORE: + case SASTORE: + if (nullAnalysis && value1 instanceof ParamValue) { + deReferenced = true; + } + default: + } + return super.ternaryOperation(insn, value1, value2, value3); + } + + @Override + public BasicValue naryOperation(AbstractInsnNode insn, List<? extends BasicValue> values) throws AnalyzerException { + boolean propagate = resultOrigins.contains(insns.indexOf(insn)); + int opCode = insn.getOpcode(); + int shift = opCode == INVOKESTATIC ? 0 : 1; + + switch (opCode) { + case INVOKESPECIAL: + case INVOKEINTERFACE: + case INVOKEVIRTUAL: + if (nullAnalysis && values.get(0) instanceof ParamValue) { + deReferenced = true; + return super.naryOperation(insn, values); + } + } + + if (propagate) { + switch (opCode) { + case INVOKESTATIC: + case INVOKESPECIAL: + case INVOKEVIRTUAL: + case INVOKEINTERFACE: + boolean stable = opCode == INVOKESTATIC || opCode == INVOKESPECIAL; + MethodInsnNode mNode = (MethodInsnNode)insn; + Method method = new Method(mNode.owner, mNode.name, mNode.desc); + Type retType = Type.getReturnType(mNode.desc); + boolean isRefRetType = retType.getSort() == Type.OBJECT || retType.getSort() == Type.ARRAY; + if (!Type.VOID_TYPE.equals(retType)) { + if (direction instanceof InOut) { + InOut inOut = (InOut)direction; + HashSet<Key> keys = new HashSet<Key>(); + for (int i = shift; i < values.size(); i++) { + if (values.get(i) instanceof ParamValue) { + keys.add(new Key(method, new InOut(i - shift, inOut.inValue), stable)); + } + } + if (isRefRetType) { + keys.add(new Key(method, new Out(), stable)); + } + if (!keys.isEmpty()) { + return new CallResultValue(retType, keys); + } + } + else if (isRefRetType) { + HashSet<Key> keys = new HashSet<Key>(); + keys.add(new Key(method, new Out(), stable)); + return new CallResultValue(retType, keys); + } + } + break; + case MULTIANEWARRAY: + return new NotNullValue(super.naryOperation(insn, values).getType()); + default: + } + } + return super.naryOperation(insn, values); + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ControlFlow.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ControlFlow.java new file mode 100644 index 000000000000..910d75b9a57f --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ControlFlow.java @@ -0,0 +1,1030 @@ +/* + * 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 gnu.trove.TIntArrayList; +import gnu.trove.TIntHashSet; +import org.jetbrains.annotations.NotNull; +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.*; +import org.jetbrains.org.objectweb.asm.tree.analysis.Value; + +import java.util.*; + +import static org.jetbrains.org.objectweb.asm.Opcodes.*; + +final class cfg { + static ControlFlowGraph buildControlFlowGraph(String className, MethodNode methodNode) throws AnalyzerException { + return new ControlFlowBuilder(className, methodNode).buildCFG(); + } + + static TIntHashSet resultOrigins(String className, MethodNode methodNode) throws AnalyzerException { + Frame<SourceValue>[] frames = new Analyzer<SourceValue>(MININAL_ORIGIN_INTERPRETER).analyze(className, methodNode); + InsnList insns = methodNode.instructions; + TIntHashSet result = new TIntHashSet(); + for (int i = 0; i < frames.length; i++) { + AbstractInsnNode insnNode = insns.get(i); + Frame<SourceValue> frame = frames[i]; + if (frame != null) { + switch (insnNode.getOpcode()) { + case ARETURN: + case IRETURN: + case LRETURN: + case FRETURN: + case DRETURN: + for (AbstractInsnNode sourceInsn : frame.pop().insns) { + result.add(insns.indexOf(sourceInsn)); + } + break; + + default: + break; + } + } + } + return result; + } + + static boolean[] leakingParameters(String className, MethodNode methodNode) throws AnalyzerException { + Frame<ParamsValue>[] frames = new Analyzer<ParamsValue>(new ParametersUsage(methodNode)).analyze(className, methodNode); + InsnList insns = methodNode.instructions; + LeakingParametersCollector collector = new LeakingParametersCollector(methodNode); + for (int i = 0; i < frames.length; i++) { + AbstractInsnNode insnNode = insns.get(i); + Frame<ParamsValue> frame = frames[i]; + if (frame != null) { + switch (insnNode.getType()) { + case AbstractInsnNode.LABEL: + case AbstractInsnNode.LINE: + case AbstractInsnNode.FRAME: + break; + default: + frame.execute(insnNode, collector); + } + } + } + return collector.leaking; + } + + static final Interpreter<SourceValue> MININAL_ORIGIN_INTERPRETER = new SourceInterpreter() { + final SourceValue[] sourceVals = {new SourceValue(1), new SourceValue(2)}; + + @Override + public SourceValue newOperation(AbstractInsnNode insn) { + SourceValue result = super.newOperation(insn); + switch (insn.getOpcode()) { + case ICONST_0: + case ICONST_1: + case ACONST_NULL: + case LDC: + case NEW: + return result; + default: + return sourceVals[result.getSize() - 1]; + } + } + + @Override + public SourceValue unaryOperation(AbstractInsnNode insn, SourceValue value) { + SourceValue result = super.unaryOperation(insn, value); + switch (insn.getOpcode()) { + case CHECKCAST: + case NEWARRAY: + case ANEWARRAY: + return result; + default: + return sourceVals[result.getSize() - 1]; + } + } + + @Override + public SourceValue binaryOperation(AbstractInsnNode insn, SourceValue value1, SourceValue value2) { + switch (insn.getOpcode()) { + case LALOAD: + case DALOAD: + case LADD: + case DADD: + case LSUB: + case DSUB: + case LMUL: + case DMUL: + case LDIV: + case DDIV: + case LREM: + case LSHL: + case LSHR: + case LUSHR: + case LAND: + case LOR: + case LXOR: + return sourceVals[1]; + default: + return sourceVals[0]; + } + } + + @Override + public SourceValue ternaryOperation(AbstractInsnNode insn, SourceValue value1, SourceValue value2, SourceValue value3) { + return sourceVals[0]; + } + + @Override + public SourceValue copyOperation(AbstractInsnNode insn, SourceValue value) { + return value; + } + + }; + + private interface Action {} + private static class MarkScanned implements Action { + final int node; + private MarkScanned(int node) { + this.node = node; + } + } + private static class ExamineEdge implements Action { + final int from; + final int to; + + private ExamineEdge(int from, int to) { + this.from = from; + this.to = to; + } + } + + // Graphs: Theory and Algorithms. by K. Thulasiraman , M. N. S. Swamy (1992) + // 11.7.2 DFS of a directed graph + static DFSTree buildDFSTree(int[][] transitions) { + Set<Edge> tree = new HashSet<Edge>(); + Set<Edge> forward = new HashSet<Edge>(); + Set<Edge> back = new HashSet<Edge>(); + Set<Edge> cross = new HashSet<Edge>(); + + boolean[] marked = new boolean[transitions.length]; + boolean[] scanned = new boolean[transitions.length]; + int[] preOrder = new int[transitions.length]; + int[] postOrder = new int[transitions.length]; + + int entered = 0; + int completed = 0; + + Deque<Action> stack = new LinkedList<Action>(); + Set<Integer> loopEnters = new HashSet<Integer>(); + + // enter 0 + entered ++; + preOrder[0] = entered; + marked[0] = true; + stack.push(new MarkScanned(0)); + for (int to : transitions[0]) { + stack.push(new ExamineEdge(0, to)); + } + + while (!stack.isEmpty()) { + Action action = stack.pop(); + if (action instanceof MarkScanned) { + MarkScanned markScannedAction = (MarkScanned) action; + completed ++; + postOrder[markScannedAction.node] = completed; + scanned[markScannedAction.node] = true; + } + else { + ExamineEdge examineEdgeAction = (ExamineEdge) action; + int from = examineEdgeAction.from; + int to = examineEdgeAction.to; + if (!marked[to]) { + tree.add(new Edge(from, to)); + // enter to + entered ++; + preOrder[to] = entered; + marked[to] = true; + stack.push(new MarkScanned(to)); + for (int to1 : transitions[to]) { + stack.push(new ExamineEdge(to, to1)); + } + } + else if (preOrder[to] > preOrder[from]) { + forward.add(new Edge(from, to)); + } + else if (preOrder[to] < preOrder[from] && !scanned[to]) { + back.add(new Edge(from, to)); + loopEnters.add(to); + } else { + cross.add(new Edge(from, to)); + } + } + } + + return new DFSTree(preOrder, postOrder, tree, forward, back, cross, loopEnters); + } + + // Tarjan. Testing flow graph reducibility. + // Journal of Computer and System Sciences 9.3 (1974): 355-365. + static boolean reducible(ControlFlowGraph cfg, DFSTree dfs) { + int size = cfg.transitions.length; + HashSet<Integer>[] cycles = new HashSet[size]; + HashSet<Integer>[] nonCycles = new HashSet[size]; + int[] collapsedTo = new int[size]; + for (int i = 0; i < size; i++) { + cycles[i] = new HashSet<Integer>(); + nonCycles[i] = new HashSet<Integer>(); + collapsedTo[i] = i; + } + + for (Edge edge : dfs.back) { + cycles[edge.to].add(edge.from); + } + for (Edge edge : dfs.tree) { + nonCycles[edge.to].add(edge.from); + } + for (Edge edge : dfs.forward) { + nonCycles[edge.to].add(edge.from); + } + for (Edge edge : dfs.cross) { + nonCycles[edge.to].add(edge.from); + } + + for (int w = size - 1; w >= 0 ; w--) { + HashSet<Integer> p = new HashSet<Integer>(cycles[w]); + Queue<Integer> queue = new LinkedList<Integer>(cycles[w]); + + while (!queue.isEmpty()) { + int x = queue.remove(); + for (int y : nonCycles[x]) { + int y1 = collapsedTo[y]; + if (!dfs.isDescendant(y1, w)) { + return false; + } + if (y1 != w && p.add(y1)) { + queue.add(y1); + } + } + } + + for (int x : p) { + collapsedTo[x] = w; + } + } + + return true; + } + +} + +final class Edge { + final int from, to; + + Edge(int from, int to) { + this.from = from; + this.to = to; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (!(o instanceof Edge)) { + return false; + } + Edge edge = (Edge) o; + return from == edge.from && to == edge.to; + } + + @Override + public int hashCode() { + return 31 * from + to; + } + + @Override + public String toString() { + return "(" + from + "," + to + ")"; + } +} + +final class ControlFlowGraph { + final String className; + final MethodNode methodNode; + final int[][] transitions; + final Set<Edge> errorTransitions; + + ControlFlowGraph(String className, MethodNode methodNode, int[][] transitions, Set<Edge> errorTransitions) { + this.className = className; + this.methodNode = methodNode; + this.transitions = transitions; + this.errorTransitions = errorTransitions; + } + + @Override + public String toString() { + return "CFG(" + + Arrays.toString(transitions) + "," + + errorTransitions + + ')'; + } +} + +final class RichControlFlow { + final ControlFlowGraph controlFlow; + final DFSTree dfsTree; + + RichControlFlow(ControlFlowGraph controlFlow, DFSTree dfsTree) { + this.controlFlow = controlFlow; + this.dfsTree = dfsTree; + } +} + +final class ControlFlowBuilder extends CfgAnalyzer { + final String className; + final MethodNode methodNode; + final TIntArrayList[] transitions; + final Set<Edge> errorTransitions; + + ControlFlowBuilder(String className, MethodNode methodNode) { + this.className = className; + this.methodNode = methodNode; + transitions = new TIntArrayList[methodNode.instructions.size()]; + for (int i = 0; i < transitions.length; i++) { + transitions[i] = new TIntArrayList(); + } + errorTransitions = new HashSet<Edge>(); + } + + final ControlFlowGraph buildCFG() throws AnalyzerException { + if ((methodNode.access & (ACC_ABSTRACT | ACC_NATIVE)) == 0) { + analyze(methodNode); + } + int[][] resultTransitions = new int[transitions.length][]; + for (int i = 0; i < resultTransitions.length; i++) { + resultTransitions[i] = transitions[i].toNativeArray(); + } + return new ControlFlowGraph(className, methodNode, resultTransitions, errorTransitions); + } + + @Override + protected final void newControlFlowEdge(int insn, int successor) { + if (!transitions[insn].contains(successor)) { + transitions[insn].add(successor); + } + } + + @Override + protected final boolean newControlFlowExceptionEdge(int insn, int successor) { + if (!transitions[insn].contains(successor)) { + transitions[insn].add(successor); + errorTransitions.add(new Edge(insn, successor)); + } + return true; + } +} + +final class DFSTree { + final int[] preOrder, postOrder; + final Set<Edge> tree, forward, back, cross; + final Set<Integer> loopEnters; + + DFSTree(int[] preOrder, + int[] postOrder, + Set<Edge> tree, + Set<Edge> forward, + Set<Edge> back, + Set<Edge> cross, + Set<Integer> loopEnters) { + this.preOrder = preOrder; + this.postOrder = postOrder; + this.tree = tree; + this.forward = forward; + this.back = back; + this.cross = cross; + this.loopEnters = loopEnters; + } + + final boolean isDescendant(int child, int parent) { + return preOrder[parent] <= preOrder[child] && postOrder[child] <= postOrder[parent]; + } +} + +final class ParamsValue implements Value { + @NotNull final boolean[] params; + final int size; + + ParamsValue(@NotNull boolean[] params, int size) { + this.params = params; + this.size = size; + } + + @Override + public int getSize() { + return size; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null) return false; + ParamsValue that = (ParamsValue)o; + return (this.size == that.size && Arrays.equals(this.params, that.params)); + } + + @Override + public int hashCode() { + return 31 * Arrays.hashCode(params) + size; + } +} + +class ParametersUsage extends Interpreter<ParamsValue> { + final ParamsValue val1; + final ParamsValue val2; + int called = -1; + final int rangeStart; + final int rangeEnd; + final int arity; + final int shift; + + ParametersUsage(MethodNode methodNode) { + super(ASM5); + arity = Type.getArgumentTypes(methodNode.desc).length; + boolean[] emptyParams = new boolean[arity]; + val1 = new ParamsValue(emptyParams, 1); + val2 = new ParamsValue(emptyParams, 2); + + shift = (methodNode.access & ACC_STATIC) == 0 ? 2 : 1; + rangeStart = shift; + rangeEnd = arity + shift; + } + + @Override + public ParamsValue newValue(Type type) { + if (type == null) return val1; + called++; + if (type == Type.VOID_TYPE) return null; + if (called < rangeEnd && rangeStart <= called) { + boolean[] params = new boolean[arity]; + params[called - shift] = true; + return type.getSize() == 1 ? new ParamsValue(params, 1) : new ParamsValue(params, 2); + } + else { + return type.getSize() == 1 ? val1 : val2; + } + } + + @Override + public ParamsValue newOperation(final AbstractInsnNode insn) { + int size; + switch (insn.getOpcode()) { + case LCONST_0: + case LCONST_1: + case DCONST_0: + case DCONST_1: + size = 2; + break; + case LDC: + Object cst = ((LdcInsnNode) insn).cst; + size = cst instanceof Long || cst instanceof Double ? 2 : 1; + break; + case GETSTATIC: + size = Type.getType(((FieldInsnNode) insn).desc).getSize(); + break; + default: + size = 1; + } + return size == 1 ? val1 : val2; + } + + @Override + public ParamsValue copyOperation(AbstractInsnNode insn, ParamsValue value) { + return value; + } + + @Override + public ParamsValue unaryOperation(AbstractInsnNode insn, ParamsValue value) { + int size; + switch (insn.getOpcode()) { + case CHECKCAST: + return new ParamsValue(value.params, Type.getObjectType(((TypeInsnNode)insn).desc).getSize()); + case LNEG: + case DNEG: + case I2L: + case I2D: + case L2D: + case F2L: + case F2D: + case D2L: + size = 2; + break; + case GETFIELD: + size = Type.getType(((FieldInsnNode) insn).desc).getSize(); + break; + default: + size = 1; + } + return size == 1 ? val1 : val2; + } + + @Override + public ParamsValue binaryOperation(AbstractInsnNode insn, ParamsValue value1, ParamsValue value2) { + int size; + switch (insn.getOpcode()) { + case LALOAD: + case DALOAD: + case LADD: + case DADD: + case LSUB: + case DSUB: + case LMUL: + case DMUL: + case LDIV: + case DDIV: + case LREM: + case DREM: + case LSHL: + case LSHR: + case LUSHR: + case LAND: + case LOR: + case LXOR: + size = 2; + break; + default: + size = 1; + } + return size == 1 ? val1 : val2; + } + + @Override + public ParamsValue ternaryOperation(AbstractInsnNode insn, ParamsValue value1, ParamsValue value2, ParamsValue value3) { + return val1; + } + + @Override + public ParamsValue naryOperation(AbstractInsnNode insn, List<? extends ParamsValue> values) { + int size; + int opcode = insn.getOpcode(); + if (opcode == MULTIANEWARRAY) { + size = 1; + } else { + String desc = (opcode == INVOKEDYNAMIC) ? ((InvokeDynamicInsnNode) insn).desc : ((MethodInsnNode) insn).desc; + size = Type.getReturnType(desc).getSize(); + } + return size == 1 ? val1 : val2; + } + + @Override + public void returnOperation(AbstractInsnNode insn, ParamsValue value, ParamsValue expected) {} + + @Override + public ParamsValue merge(ParamsValue v1, ParamsValue v2) { + if (v1.equals(v2)) return v1; + boolean[] params = new boolean[arity]; + boolean[] params1 = v1.params; + boolean[] params2 = v2.params; + for (int i = 0; i < arity; i++) { + params[i] = params1[i] || params2[i]; + } + return new ParamsValue(params, Math.min(v1.size, v2.size)); + } +} + +class LeakingParametersCollector extends ParametersUsage { + final boolean[] leaking; + LeakingParametersCollector(MethodNode methodNode) { + super(methodNode); + leaking = new boolean[arity]; + } + + @Override + public ParamsValue unaryOperation(AbstractInsnNode insn, ParamsValue value) { + switch (insn.getOpcode()) { + case GETFIELD: + case ARRAYLENGTH: + case MONITORENTER: + case INSTANCEOF: + case IRETURN: + case ARETURN: + case IFNONNULL: + case IFNULL: + case IFEQ: + case IFNE: + boolean[] params = value.params; + for (int i = 0; i < arity; i++) { + leaking[i] |= params[i]; + } + break; + default: + } + return super.unaryOperation(insn, value); + } + + @Override + public ParamsValue binaryOperation(AbstractInsnNode insn, ParamsValue value1, ParamsValue value2) { + switch (insn.getOpcode()) { + case IALOAD: + case LALOAD: + case FALOAD: + case DALOAD: + case AALOAD: + case BALOAD: + case CALOAD: + case SALOAD: + case PUTFIELD: + boolean[] params = value1.params; + for (int i = 0; i < arity; i++) { + leaking[i] |= params[i]; + } + break; + default: + } + return super.binaryOperation(insn, value1, value2); + } + + @Override + public ParamsValue ternaryOperation(AbstractInsnNode insn, ParamsValue value1, ParamsValue value2, ParamsValue value3) { + switch (insn.getOpcode()) { + case IASTORE: + case LASTORE: + case FASTORE: + case DASTORE: + case AASTORE: + case BASTORE: + case CASTORE: + case SASTORE: + boolean[] params = value1.params; + for (int i = 0; i < arity; i++) { + leaking[i] |= params[i]; + } + break; + default: + } + return super.ternaryOperation(insn, value1, value2, value3); + } + + @Override + public ParamsValue naryOperation(AbstractInsnNode insn, List<? extends ParamsValue> values) { + switch (insn.getOpcode()) { + case INVOKESTATIC: + case INVOKESPECIAL: + case INVOKEVIRTUAL: + case INVOKEINTERFACE: + for (ParamsValue value : values) { + boolean[] params = value.params; + for (int i = 0; i < arity; i++) { + leaking[i] |= params[i]; + } + } + break; + default: + } + return super.naryOperation(insn, values); + } +} + +/** + * Specialized lite version of {@link org.jetbrains.org.objectweb.asm.tree.analysis.Analyzer}. + * Calculation of fix-point of frames is removed, since frames are not needed to build control flow graph. + * So, the main point here is handling of subroutines (jsr) and try-catch-finally blocks. + */ +class CfgAnalyzer implements Opcodes { + static class Subroutine { + + LabelNode start; + + boolean[] access; + + List<JumpInsnNode> callers; + + private Subroutine() { + } + + Subroutine(final LabelNode start, final int maxLocals, + final JumpInsnNode caller) { + this.start = start; + this.access = new boolean[maxLocals]; + this.callers = new ArrayList<JumpInsnNode>(); + callers.add(caller); + } + + public Subroutine copy() { + Subroutine result = new Subroutine(); + result.start = start; + result.access = new boolean[access.length]; + System.arraycopy(access, 0, result.access, 0, access.length); + result.callers = new ArrayList<JumpInsnNode>(callers); + return result; + } + + public boolean merge(final Subroutine subroutine) throws AnalyzerException { + boolean changes = false; + for (int i = 0; i < access.length; ++i) { + if (subroutine.access[i] && !access[i]) { + access[i] = true; + changes = true; + } + } + if (subroutine.start == start) { + for (int i = 0; i < subroutine.callers.size(); ++i) { + JumpInsnNode caller = subroutine.callers.get(i); + if (!callers.contains(caller)) { + callers.add(caller); + changes = true; + } + } + } + return changes; + } + } + private int n; + private InsnList insns; + private List<TryCatchBlockNode>[] handlers; + private Subroutine[] subroutines; + private boolean[] wasQueued; + private boolean[] queued; + private int[] queue; + private int top; + + public void analyze(final MethodNode m) throws AnalyzerException { + n = m.instructions.size(); + insns = m.instructions; + handlers = (List<TryCatchBlockNode>[]) new List<?>[n]; + subroutines = new Subroutine[n]; + queued = new boolean[n]; + wasQueued = new boolean[n]; + queue = new int[n]; + top = 0; + + // computes exception handlers for each instruction + for (int i = 0; i < m.tryCatchBlocks.size(); ++i) { + TryCatchBlockNode tcb = m.tryCatchBlocks.get(i); + int begin = insns.indexOf(tcb.start); + int end = insns.indexOf(tcb.end); + for (int j = begin; j < end; ++j) { + List<TryCatchBlockNode> insnHandlers = handlers[j]; + if (insnHandlers == null) { + insnHandlers = new ArrayList<TryCatchBlockNode>(); + handlers[j] = insnHandlers; + } + insnHandlers.add(tcb); + } + } + + // computes the subroutine for each instruction: + Subroutine main = new Subroutine(null, m.maxLocals, null); + List<AbstractInsnNode> subroutineCalls = new ArrayList<AbstractInsnNode>(); + Map<LabelNode, Subroutine> subroutineHeads = new HashMap<LabelNode, Subroutine>(); + + findSubroutine(0, main, subroutineCalls); + while (!subroutineCalls.isEmpty()) { + JumpInsnNode jsr = (JumpInsnNode) subroutineCalls.remove(0); + Subroutine sub = subroutineHeads.get(jsr.label); + if (sub == null) { + sub = new Subroutine(jsr.label, m.maxLocals, jsr); + subroutineHeads.put(jsr.label, sub); + findSubroutine(insns.indexOf(jsr.label), sub, subroutineCalls); + } else { + sub.callers.add(jsr); + } + } + for (int i = 0; i < n; ++i) { + if (subroutines[i] != null && subroutines[i].start == null) { + subroutines[i] = null; + } + } + + merge(0, null); + // control flow analysis + while (top > 0) { + int insn = queue[--top]; + Subroutine subroutine = subroutines[insn]; + queued[insn] = false; + + AbstractInsnNode insnNode = null; + try { + insnNode = m.instructions.get(insn); + int insnOpcode = insnNode.getOpcode(); + int insnType = insnNode.getType(); + + if (insnType == AbstractInsnNode.LABEL || insnType == AbstractInsnNode.LINE || insnType == AbstractInsnNode.FRAME) { + merge(insn + 1, subroutine); + newControlFlowEdge(insn, insn + 1); + } else { + subroutine = subroutine == null ? null : subroutine.copy(); + + if (insnNode instanceof JumpInsnNode) { + JumpInsnNode j = (JumpInsnNode) insnNode; + if (insnOpcode != GOTO && insnOpcode != JSR) { + merge(insn + 1, subroutine); + newControlFlowEdge(insn, insn + 1); + } + int jump = insns.indexOf(j.label); + if (insnOpcode == JSR) { + merge(jump, new Subroutine(j.label, m.maxLocals, j)); + } else { + merge(jump, subroutine); + } + newControlFlowEdge(insn, jump); + } else if (insnNode instanceof LookupSwitchInsnNode) { + LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode; + int jump = insns.indexOf(lsi.dflt); + merge(jump, subroutine); + newControlFlowEdge(insn, jump); + for (int j = 0; j < lsi.labels.size(); ++j) { + LabelNode label = lsi.labels.get(j); + jump = insns.indexOf(label); + merge(jump, subroutine); + newControlFlowEdge(insn, jump); + } + } else if (insnNode instanceof TableSwitchInsnNode) { + TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode; + int jump = insns.indexOf(tsi.dflt); + merge(jump, subroutine); + newControlFlowEdge(insn, jump); + for (int j = 0; j < tsi.labels.size(); ++j) { + LabelNode label = tsi.labels.get(j); + jump = insns.indexOf(label); + merge(jump, subroutine); + newControlFlowEdge(insn, jump); + } + } else if (insnOpcode == RET) { + if (subroutine == null) { + throw new AnalyzerException(insnNode, "RET instruction outside of a sub routine"); + } + for (int i = 0; i < subroutine.callers.size(); ++i) { + JumpInsnNode caller = subroutine.callers.get(i); + int call = insns.indexOf(caller); + if (wasQueued[call]) { + merge(call + 1, subroutines[call], subroutine.access); + newControlFlowEdge(insn, call + 1); + } + } + } else if (insnOpcode != ATHROW && (insnOpcode < IRETURN || insnOpcode > RETURN)) { + if (subroutine != null) { + if (insnNode instanceof VarInsnNode) { + int var = ((VarInsnNode) insnNode).var; + subroutine.access[var] = true; + if (insnOpcode == LLOAD || insnOpcode == DLOAD + || insnOpcode == LSTORE + || insnOpcode == DSTORE) { + subroutine.access[var + 1] = true; + } + } else if (insnNode instanceof IincInsnNode) { + int var = ((IincInsnNode) insnNode).var; + subroutine.access[var] = true; + } + } + merge(insn + 1, subroutine); + newControlFlowEdge(insn, insn + 1); + } + } + + List<TryCatchBlockNode> insnHandlers = handlers[insn]; + if (insnHandlers != null) { + for (TryCatchBlockNode tcb : insnHandlers) { + newControlFlowExceptionEdge(insn, tcb); + merge(insns.indexOf(tcb.handler), subroutine); + } + } + } catch (AnalyzerException e) { + throw new AnalyzerException(e.node, "Error at instruction " + + insn + ": " + e.getMessage(), e); + } catch (Exception e) { + throw new AnalyzerException(insnNode, "Error at instruction " + + insn + ": " + e.getMessage(), e); + } + } + } + + private void findSubroutine(int insn, final Subroutine sub, + final List<AbstractInsnNode> calls) throws AnalyzerException { + while (true) { + if (insn < 0 || insn >= n) { + throw new AnalyzerException(null, "Execution can fall off end of the code"); + } + if (subroutines[insn] != null) { + return; + } + subroutines[insn] = sub.copy(); + AbstractInsnNode node = insns.get(insn); + + // calls findSubroutine recursively on normal successors + if (node instanceof JumpInsnNode) { + if (node.getOpcode() == JSR) { + // do not follow a JSR, it leads to another subroutine! + calls.add(node); + } else { + JumpInsnNode jnode = (JumpInsnNode) node; + findSubroutine(insns.indexOf(jnode.label), sub, calls); + } + } else if (node instanceof TableSwitchInsnNode) { + TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node; + findSubroutine(insns.indexOf(tsnode.dflt), sub, calls); + for (int i = tsnode.labels.size() - 1; i >= 0; --i) { + LabelNode l = tsnode.labels.get(i); + findSubroutine(insns.indexOf(l), sub, calls); + } + } else if (node instanceof LookupSwitchInsnNode) { + LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node; + findSubroutine(insns.indexOf(lsnode.dflt), sub, calls); + for (int i = lsnode.labels.size() - 1; i >= 0; --i) { + LabelNode l = lsnode.labels.get(i); + findSubroutine(insns.indexOf(l), sub, calls); + } + } + + // calls findSubroutine recursively on exception handler successors + List<TryCatchBlockNode> insnHandlers = handlers[insn]; + if (insnHandlers != null) { + for (int i = 0; i < insnHandlers.size(); ++i) { + TryCatchBlockNode tcb = insnHandlers.get(i); + findSubroutine(insns.indexOf(tcb.handler), sub, calls); + } + } + + // if insn does not falls through to the next instruction, return. + switch (node.getOpcode()) { + case GOTO: + case RET: + case TABLESWITCH: + case LOOKUPSWITCH: + case IRETURN: + case LRETURN: + case FRETURN: + case DRETURN: + case ARETURN: + case RETURN: + case ATHROW: + return; + } + insn++; + } + } + + protected void newControlFlowEdge(final int insn, final int successor) {} + + protected boolean newControlFlowExceptionEdge(final int insn, + final int successor) { + return true; + } + + protected boolean newControlFlowExceptionEdge(final int insn, + final TryCatchBlockNode tcb) { + return newControlFlowExceptionEdge(insn, insns.indexOf(tcb.handler)); + } + + // ------------------------------------------------------------------------- + + private void merge(final int insn, final Subroutine subroutine) throws AnalyzerException { + Subroutine oldSubroutine = subroutines[insn]; + boolean changes = false; + + if (!wasQueued[insn]) { + wasQueued[insn] = true; + changes = true; + } + + if (oldSubroutine == null) { + if (subroutine != null) { + subroutines[insn] = subroutine.copy(); + changes = true; + } + } else { + if (subroutine != null) { + changes |= oldSubroutine.merge(subroutine); + } + } + if (changes && !queued[insn]) { + queued[insn] = true; + queue[top++] = insn; + } + } + + private void merge(final int insn, final Subroutine subroutineBeforeJSR, final boolean[] access) throws AnalyzerException { + Subroutine oldSubroutine = subroutines[insn]; + boolean changes = false; + + if (!wasQueued[insn]) { + wasQueued[insn] = true; + changes = true; + } + + if (oldSubroutine != null && subroutineBeforeJSR != null) { + changes |= oldSubroutine.merge(subroutineBeforeJSR); + } + if (changes && !queued[insn]) { + queued[insn] = true; + queue[top++] = insn; + } + } +} + diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Data.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Data.java new file mode 100644 index 000000000000..132c5643b2d6 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Data.java @@ -0,0 +1,226 @@ +/* + * 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; + +final class Method { + final String internalClassName; + final String methodName; + final String methodDesc; + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + Method method = (Method) o; + return internalClassName.equals(method.internalClassName) && methodDesc.equals(method.methodDesc) && methodName.equals(method.methodName); + } + + @Override + public int hashCode() { + int result = internalClassName.hashCode(); + result = 31 * result + methodName.hashCode(); + result = 31 * result + methodDesc.hashCode(); + return result; + } + + Method(String internalClassName, String methodName, String methodDesc) { + this.internalClassName = internalClassName; + this.methodName = methodName; + this.methodDesc = methodDesc; + } + + @Override + public String toString() { + return internalClassName + ' ' + methodName + ' ' + methodDesc; + } +} + +enum Value { + Bot, NotNull, Null, True, False, Top +} + +interface Direction { + static final int OUT_DIRECTION = 0; + static final int IN_DIRECTION = 1; + static final int INOUT_DIRECTION = 2; + int directionId(); + int paramId(); + int valueId(); +} + +final class In implements Direction { + final int paramIndex; + + In(int paramIndex) { + this.paramIndex = paramIndex; + } + + @Override + public String toString() { + return "In " + paramIndex; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + In in = (In) o; + if (paramIndex != in.paramIndex) return false; + return true; + } + + @Override + public int hashCode() { + return paramIndex; + } + + @Override + public int directionId() { + return IN_DIRECTION; + } + + @Override + public int paramId() { + return paramIndex; + } + + @Override + public int valueId() { + return 0; + } +} + +final class InOut implements Direction { + final int paramIndex; + final Value inValue; + + InOut(int paramIndex, Value inValue) { + this.paramIndex = paramIndex; + this.inValue = inValue; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + InOut inOut = (InOut) o; + + if (paramIndex != inOut.paramIndex) return false; + if (inValue != inOut.inValue) return false; + + return true; + } + + @Override + public int hashCode() { + int result = paramIndex; + result = 31 * result + inValue.ordinal(); + return result; + } + + @Override + public String toString() { + return "InOut " + paramIndex + " " + inValue.toString(); + } + + @Override + public int directionId() { + return INOUT_DIRECTION; + } + + @Override + public int paramId() { + return paramIndex; + } + + @Override + public int valueId() { + return inValue.ordinal(); + } +} + +final class Out implements Direction { + @Override + public String toString() { + return "Out"; + } + + @Override + public int hashCode() { + return 1; + } + + @Override + public boolean equals(Object obj) { + return obj instanceof Out; + } + + @Override + public int directionId() { + return OUT_DIRECTION; + } + + @Override + public int paramId() { + return 0; + } + + @Override + public int valueId() { + return 0; + } +} + +final class Key { + final Method method; + final Direction direction; + final boolean stable; + + Key(Method method, Direction direction, boolean stable) { + this.method = method; + this.direction = direction; + this.stable = stable; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + Key key = (Key) o; + + if (!direction.equals(key.direction)) return false; + if (!method.equals(key.method)) return false; + if (stable != key.stable) return false; + return true; + } + + @Override + public int hashCode() { + int result = method.hashCode(); + result = 31 * result + direction.hashCode(); + result = 31 * result + (stable ? 1 : 0); + return result; + } + + @Override + public String toString() { + return "" + method + ' ' + direction + ' ' + stable; + } +} + + 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 new file mode 100644 index 000000000000..08c52c4d49b0 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java @@ -0,0 +1,390 @@ +/* + * 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 org.jetbrains.org.objectweb.asm.Type; +import org.jetbrains.org.objectweb.asm.tree.AbstractInsnNode; +import org.jetbrains.org.objectweb.asm.tree.JumpInsnNode; +import org.jetbrains.org.objectweb.asm.tree.MethodInsnNode; +import org.jetbrains.org.objectweb.asm.tree.TypeInsnNode; +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.*; + +import static com.intellij.codeInspection.bytecodeAnalysis.AbstractValues.InstanceOfCheckValue; +import static com.intellij.codeInspection.bytecodeAnalysis.AbstractValues.ParamValue; +import static com.intellij.codeInspection.bytecodeAnalysis.PResults.*; +import static org.jetbrains.org.objectweb.asm.Opcodes.*; + +abstract class PResults { + // SoP = sum of products + static Set<Set<Key>> join(Set<Set<Key>> sop1, Set<Set<Key>> sop2) { + Set<Set<Key>> sop = new HashSet<Set<Key>>(); + sop.addAll(sop1); + sop.addAll(sop2); + return sop; + } + + static Set<Set<Key>> meet(Set<Set<Key>> sop1, Set<Set<Key>> sop2) { + Set<Set<Key>> sop = new HashSet<Set<Key>>(); + for (Set<Key> prod1 : sop1) { + for (Set<Key> prod2 : sop2) { + Set<Key> prod = new HashSet<Key>(); + prod.addAll(prod1); + prod.addAll(prod2); + sop.add(prod); + } + } + return sop; + } + + // Results + interface PResult {} + static final PResult Identity = new PResult() { + @Override + public String toString() { + return "Identity"; + } + }; + // similar to top, maximal element + static final PResult Return = new PResult() { + @Override + public String toString() { + return "Return"; + } + }; + // minimal element + static final PResult NPE = new PResult() { + @Override + public String toString() { + return "NPE"; + } + }; + static final class ConditionalNPE implements PResult { + final Set<Set<Key>> sop; + public ConditionalNPE(Set<Set<Key>> sop) { + this.sop = sop; + } + + public ConditionalNPE(Key key) { + sop = new HashSet<Set<Key>>(); + Set<Key> prod = new HashSet<Key>(); + prod.add(key); + sop.add(prod); + } + } + + static PResult join(PResult r1, PResult r2) { + if (Identity == r1) return r2; + if (Identity == r2) return r1; + if (Return == r1) return Return; + if (Return == r2) return Return; + if (NPE == r1) return r2; + if (NPE == r2) return r1; + ConditionalNPE cnpe1 = (ConditionalNPE) r1; + ConditionalNPE cnpe2 = (ConditionalNPE) r2; + return new ConditionalNPE(join(cnpe1.sop, cnpe2.sop)); + } + + static PResult meet(PResult r1, PResult r2) { + if (Identity == r1) return r2; + if (Return == r1) return r2; + if (Return == r2) return r1; + if (NPE == r1) return NPE; + if (NPE == r2) return NPE; + if (Identity == r2) return Identity; + ConditionalNPE cnpe1 = (ConditionalNPE) r1; + ConditionalNPE cnpe2 = (ConditionalNPE) r2; + return new ConditionalNPE(meet(cnpe1.sop, cnpe2.sop)); + } + +} + +class NonNullInAnalysis extends Analysis<PResult> { + + private final NonNullInInterpreter interpreter = new NonNullInInterpreter(); + + protected NonNullInAnalysis(RichControlFlow richControlFlow, Direction direction, boolean stable) { + super(richControlFlow, direction, stable); + } + + @Override + PResult identity() { + return Identity; + } + + @Override + PResult combineResults(PResult delta, List<PResult> subResults) { + PResult subResult = Identity; + for (PResult sr : subResults) { + subResult = join(subResult, sr); + } + return meet(delta, subResult); + } + + @Override + boolean isEarlyResult(PResult result) { + return false; + } + + @Override + Equation<Key, Value> mkEquation(PResult result) { + if (Identity == result || Return == result) { + return new Equation<Key, Value>(aKey, new Final<Key, Value>(Value.Top)); + } + else if (NPE == result) { + return new Equation<Key, Value>(aKey, new Final<Key, Value>(Value.NotNull)); + } + 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 subResult = null; + + @Override + void processState(State state) throws AnalyzerException { + int stateIndex = state.index; + 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.contains(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)); + return; + } + + int opcode = insnNode.getOpcode(); + switch (opcode) { + case ARETURN: + case IRETURN: + case LRETURN: + case FRETURN: + case DRETURN: + case RETURN: + if (!hasCompanions) { + earlyResult = Return; + } else { + results.put(stateIndex, Return); + computed.put(insnIndex, append(computed.get(insnIndex), state)); + } + return; + default: + } + + if (opcode == ATHROW) { + if (taken) { + results.put(stateIndex, NPE); + } else { + results.put(stateIndex, Identity); + } + computed.put(insnIndex, append(computed.get(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)); + 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)); + 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)); + 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)); + 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++) { + int nextInsnIndex = nextInsnIndices[i]; + Frame<BasicValue> nextFrame1 = nextFrame; + if (controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { + nextFrame1 = new Frame<BasicValue>(frame); + nextFrame1.clearStack(); + nextFrame1.push(new BasicValue(Type.getType("java/lang/Throwable"))); + } + nextStates.add(new State(++id, new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, hasCompanions || notEmptySubResult)); + subIndices[i] = (id); + } + + pending.push(new MakeResult<PResult>(state, subResult, subIndices)); + for (State nextState : nextStates) { + pending.push(new ProceedState<PResult>(nextState)); + } + + } + + 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 NonNullInInterpreter extends BasicInterpreter { + private PResult subResult = Identity; + public PResult getSubResult() { + return subResult; + } + void reset() { + subResult = Identity; + } + + @Override + public BasicValue unaryOperation(AbstractInsnNode insn, BasicValue value) throws AnalyzerException { + switch (insn.getOpcode()) { + case GETFIELD: + case ARRAYLENGTH: + case MONITORENTER: + if (value instanceof ParamValue) { + subResult = NPE; + } + break; + case CHECKCAST: + if (value instanceof ParamValue) { + return new ParamValue(Type.getObjectType(((TypeInsnNode)insn).desc)); + } + break; + case INSTANCEOF: + if (value instanceof ParamValue) { + return InstanceOfCheckValue; + } + break; + default: + + } + return super.unaryOperation(insn, value); + } + + @Override + public BasicValue binaryOperation(AbstractInsnNode insn, BasicValue value1, BasicValue value2) throws AnalyzerException { + switch (insn.getOpcode()) { + case IALOAD: + case LALOAD: + case FALOAD: + case DALOAD: + case AALOAD: + case BALOAD: + case CALOAD: + case SALOAD: + case PUTFIELD: + if (value1 instanceof ParamValue) { + subResult = NPE; + } + break; + default: + } + return super.binaryOperation(insn, value1, value2); + } + + @Override + public BasicValue ternaryOperation(AbstractInsnNode insn, BasicValue value1, BasicValue value2, BasicValue value3) throws AnalyzerException { + switch (insn.getOpcode()) { + case IASTORE: + case LASTORE: + case FASTORE: + case DASTORE: + case AASTORE: + case BASTORE: + case CASTORE: + case SASTORE: + if (value1 instanceof ParamValue) { + subResult = NPE; + } + default: + } + return super.ternaryOperation(insn, value1, value2, value3); + } + + @Override + public BasicValue naryOperation(AbstractInsnNode insn, List<? extends BasicValue> values) throws AnalyzerException { + int opcode = insn.getOpcode(); + boolean isStaticInvoke = opcode == INVOKESTATIC; + int shift = isStaticInvoke ? 0 : 1; + if ((opcode == INVOKESPECIAL || opcode ==INVOKEINTERFACE || opcode == INVOKEVIRTUAL) && values.get(0) instanceof ParamValue) { + subResult = NPE; + } + switch (opcode) { + case INVOKESTATIC: + case INVOKESPECIAL: + case INVOKEVIRTUAL: + case INVOKEINTERFACE: + boolean stable = opcode == INVOKESTATIC || opcode == INVOKESPECIAL; + MethodInsnNode methodNode = (MethodInsnNode) insn; + 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))); + } + } + default: + } + return super.naryOperation(insn, values); + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ProjectBytecodeAnalysis.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ProjectBytecodeAnalysis.java new file mode 100644 index 000000000000..86b9dd101fd9 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ProjectBytecodeAnalysis.java @@ -0,0 +1,291 @@ +/* + * 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.ProjectTopics; +import com.intellij.codeInsight.AnnotationUtil; +import com.intellij.codeInspection.dataFlow.ControlFlowAnalyzer; +import com.intellij.openapi.components.ServiceManager; +import com.intellij.openapi.diagnostic.Logger; +import com.intellij.openapi.progress.ProgressManager; +import com.intellij.openapi.project.Project; +import com.intellij.openapi.roots.ContentIterator; +import com.intellij.openapi.roots.ModuleRootAdapter; +import com.intellij.openapi.roots.ModuleRootEvent; +import com.intellij.openapi.util.Key; +import com.intellij.openapi.util.ModificationTracker; +import com.intellij.openapi.vfs.VirtualFile; +import com.intellij.psi.*; +import com.intellij.psi.search.GlobalSearchScope; +import com.intellij.psi.search.ProjectScope; +import com.intellij.psi.util.CachedValueProvider; +import com.intellij.psi.util.CachedValuesManager; +import com.intellij.util.IncorrectOperationException; +import com.intellij.util.indexing.FileBasedIndex; +import com.intellij.util.messages.MessageBusConnection; +import gnu.trove.TIntHashSet; +import gnu.trove.TIntObjectHashMap; +import org.jetbrains.annotations.NotNull; +import org.jetbrains.annotations.Nullable; + +import java.io.IOException; +import java.util.Collection; + +/** + * @author lambdamix + */ +public class ProjectBytecodeAnalysis { + public static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.bytecodeAnalysis"); + public static final Key<Boolean> INFERRED_ANNOTATION = Key.create("INFERRED_ANNOTATION"); + private final Project myProject; + + private volatile Annotations myAnnotations = null; + + public static ProjectBytecodeAnalysis getInstance(@NotNull Project project) { + return ServiceManager.getService(project, ProjectBytecodeAnalysis.class); + } + + public ProjectBytecodeAnalysis(Project project) { + myProject = project; + final MessageBusConnection connection = myProject.getMessageBus().connect(); + connection.subscribe(ProjectTopics.PROJECT_ROOTS, new ModuleRootAdapter() { + @Override + public void rootsChanged(ModuleRootEvent event) { + unloadAnnotations(); + } + }); + } + + private void loadAnnotations() { + Annotations annotations = new Annotations(); + loadParameterAnnotations(annotations); + loadContractAnnotations(annotations); + myAnnotations = annotations; + LOG.debug("NotNull annotations: " + myAnnotations.notNulls.size()); + LOG.debug("Contract annotations: " + myAnnotations.contracts.size()); + } + + private void unloadAnnotations() { + myAnnotations = null; + LOG.debug("unloaded"); + } + + private void loadParameterAnnotations(Annotations annotations) { + LOG.debug("initializing parameter annotations"); + final IntIdSolver solver = new IntIdSolver(new ELattice<Value>(Value.NotNull, Value.Top)); + + processValues(true, new FileBasedIndex.ValueProcessor<Collection<IntIdEquation>>() { + @Override + public boolean process(VirtualFile file, Collection<IntIdEquation> value) { + for (IntIdEquation intIdEquation : value) { + solver.addEquation(intIdEquation); + } + return true; + } + }); + + LOG.debug("parameter equations are constructed"); + LOG.debug("equations: " + solver.getSize()); + TIntObjectHashMap<Value> solutions = solver.solve(); + LOG.debug("parameter equations are solved"); + BytecodeAnalysisConverter.getInstance().addAnnotations(solutions, annotations); + } + + private void processValues(final boolean parameters, final FileBasedIndex.ValueProcessor<Collection<IntIdEquation>> processor) { + final GlobalSearchScope libScope = ProjectScope.getLibrariesScope(myProject); + final FileBasedIndex index = FileBasedIndex.getInstance(); + index.iterateIndexableFiles(new ContentIterator() { + @Override + public boolean processFile(VirtualFile fileOrDir) { + ProgressManager.checkCanceled(); + if (!fileOrDir.isDirectory() && libScope.contains(fileOrDir)) { + index.processValues(BytecodeAnalysisIndex.NAME, BytecodeAnalysisIndex.indexKey(fileOrDir, parameters), + fileOrDir, processor, GlobalSearchScope.fileScope(myProject, fileOrDir)); + } + return false; + } + }, myProject, null); + } + + private void loadContractAnnotations(Annotations annotations) { + LOG.debug("initializing contract annotations"); + final IntIdSolver solver = new IntIdSolver(new ELattice<Value>(Value.Bot, Value.Top)); + processValues(false, new FileBasedIndex.ValueProcessor<Collection<IntIdEquation>>() { + @Override + public boolean process(VirtualFile file, Collection<IntIdEquation> value) { + for (IntIdEquation intIdEquation : value) { + solver.addEquation(intIdEquation); + } + return true; + } + }); + LOG.debug("contract equations are constructed"); + LOG.debug("equations: " + solver.getSize()); + TIntObjectHashMap<Value> solutions = solver.solve(); + LOG.debug("contract equations are solved"); + BytecodeAnalysisConverter.getInstance().addAnnotations(solutions, annotations); + } + + @Nullable + public PsiAnnotation findInferredAnnotation(@NotNull PsiModifierListOwner listOwner, @NotNull String annotationFQN) { + if (!(listOwner instanceof PsiCompiledElement)) { + return null; + } + if (annotationFQN.equals("org.jetbrains.annotations.NotNull")) { + return findNotNullAnnotation(listOwner); + } + else if (annotationFQN.equals("org.jetbrains.annotations.Contract")) { + return findContractAnnotation(listOwner); + } + else { + return null; + } + } + + @NotNull + public PsiAnnotation[] findInferredAnnotations(@NotNull PsiModifierListOwner listOwner) { + if (!(listOwner instanceof PsiCompiledElement)) { + return PsiAnnotation.EMPTY_ARRAY; + } + return collectInferredAnnotations(listOwner); + } + + // TODO the best way to synchronize? + @NotNull + private synchronized PsiAnnotation[] collectInferredAnnotations(PsiModifierListOwner listOwner) { + if (myAnnotations == null) { + loadAnnotations(); + } + try { + int key = getKey(listOwner); + if (key == -1) { + return PsiAnnotation.EMPTY_ARRAY; + } + boolean notNull = myAnnotations.notNulls.contains(key); + String contractValue = myAnnotations.contracts.get(key); + + if (notNull && contractValue != null) { + return new PsiAnnotation[]{ + getNotNullAnnotation(), + createAnnotationFromText("@" + ControlFlowAnalyzer.ORG_JETBRAINS_ANNOTATIONS_CONTRACT + "(" + contractValue + ")") + }; + } + else if (notNull) { + return new PsiAnnotation[]{ + getNotNullAnnotation() + }; + } + else if (contractValue != null) { + return new PsiAnnotation[]{ + createAnnotationFromText("@" + ControlFlowAnalyzer.ORG_JETBRAINS_ANNOTATIONS_CONTRACT + "(" + contractValue + ")") + }; + } + else { + return PsiAnnotation.EMPTY_ARRAY; + } + } + catch (IOException e) { + LOG.debug(e); + return PsiAnnotation.EMPTY_ARRAY; + } + } + + private PsiAnnotation getNotNullAnnotation() { + return CachedValuesManager.getManager(myProject).getCachedValue(myProject, new CachedValueProvider<PsiAnnotation>() { + @Nullable + @Override + public Result<PsiAnnotation> compute() { + return Result.create(createAnnotationFromText("@" + AnnotationUtil.NOT_NULL), ModificationTracker.NEVER_CHANGED); + } + }); + } + + @Nullable + private synchronized PsiAnnotation findNotNullAnnotation(PsiModifierListOwner listOwner) { + if (myAnnotations == null) { + loadAnnotations(); + } + try { + int key = getKey(listOwner); + if (key == -1) { + return null; + } + return myAnnotations.notNulls.contains(key) ? getNotNullAnnotation() : null; + } + catch (IOException e) { + LOG.debug(e); + return null; + } + } + + @Nullable + private synchronized PsiAnnotation findContractAnnotation(PsiModifierListOwner listOwner) { + if (myAnnotations == null) { + loadAnnotations(); + } + try { + int key = getKey(listOwner); + if (key == -1) { + return null; + } + String contractValue = myAnnotations.contracts.get(key); + return contractValue != null ? createContractAnnotation(contractValue) : null; + } + catch (IOException e) { + LOG.debug(e); + return null; + } + } + + public PsiAnnotation createContractAnnotation(String contractValue) { + return createAnnotationFromText("@org.jetbrains.annotations.Contract(" + contractValue + ")"); + } + + public static int getKey(@NotNull PsiModifierListOwner owner) throws IOException { + LOG.assertTrue(owner instanceof PsiCompiledElement, owner); + + if (owner instanceof PsiMethod) { + return BytecodeAnalysisConverter.getInstance().mkPsiKey((PsiMethod)owner, new Out()); + } + + if (owner instanceof PsiParameter) { + PsiElement parent = owner.getParent(); + if (parent instanceof PsiParameterList) { + PsiElement gParent = parent.getParent(); + if (gParent instanceof PsiMethod) { + final int index = ((PsiParameterList)parent).getParameterIndex((PsiParameter)owner); + return BytecodeAnalysisConverter.getInstance().mkPsiKey((PsiMethod)gParent, new In(index)); + } + } + } + + return -1; + } + + @NotNull + private PsiAnnotation createAnnotationFromText(@NotNull final String text) throws IncorrectOperationException { + PsiAnnotation annotation = JavaPsiFacade.getElementFactory(myProject).createAnnotationFromText(text, null); + annotation.putUserData(INFERRED_ANNOTATION, Boolean.TRUE); + return annotation; + } +} + +class Annotations { + // @NotNull keys + final TIntHashSet notNulls = new TIntHashSet(); + // @Contracts + final TIntObjectHashMap<String> contracts = new TIntObjectHashMap<String>(); +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java new file mode 100644 index 000000000000..47c97790d102 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java @@ -0,0 +1,440 @@ +/* + * 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.util.containers.IntStack; +import com.intellij.util.containers.IntToIntSetMap; +import gnu.trove.TIntObjectHashMap; +import org.jetbrains.annotations.NotNull; + +import java.util.*; + +final class ELattice<T extends Enum<T>> { + final T bot; + final T top; + + ELattice(T bot, T top) { + this.bot = bot; + this.top = top; + } + + final T join(T x, T y) { + if (x == bot) return y; + if (y == bot) return x; + if (x == y) return x; + return top; + } + + final T meet(T x, T y) { + if (x == top) return y; + if (y == top) return x; + if (x == y) return x; + return bot; + } +} + +// component specialized for ints +final class IntIdComponent { + Value value; + final int[] ids; + + IntIdComponent(Value value, int[] ids) { + this.value = value; + this.ids = ids; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + IntIdComponent that = (IntIdComponent)o; + + if (!Arrays.equals(ids, that.ids)) return false; + if (value != that.value) return false; + + return true; + } + + @Override + public int hashCode() { + return value.ordinal() + Arrays.hashCode(ids); + } + + public boolean remove(int id) { + return IdUtils.remove(ids, id); + } + + public boolean isEmpty() { + return IdUtils.isEmpty(ids); + } + + IntIdComponent copy() { + return new IntIdComponent(value, ids.clone()); + } +} + +class IdUtils { + // removed value + static final int nullId = 0; + + static boolean contains(int[] ids, int id) { + for (int id1 : ids) { + if (id1 == id) return true; + } + + return false; + } + + static boolean isEmpty(int[] ids) { + for (int id : ids) { + if (id != nullId) return false; + } + return true; + } + + static IntIdComponent[] toArray(Collection<IntIdComponent> set) { + IntIdComponent[] result = new IntIdComponent[set.size()]; + int i = 0; + for (IntIdComponent intIdComponent : set) { + result[i] = intIdComponent; + i++; + } + + return result; + } + + static boolean remove(int[] ids, int id) { + boolean removed = false; + for (int i = 0; i < ids.length; i++) { + if (ids[i] == id) { + ids[i] = nullId; + removed = true; + } + } + return removed; + } +} + +class ResultUtil<Id, T extends Enum<T>> { + private final ELattice<T> lattice; + final T top; + ResultUtil(ELattice<T> lattice) { + this.lattice = lattice; + top = lattice.top; + } + + Result<Id, T> join(Result<Id, T> r1, Result<Id, T> r2) { + if (r1 instanceof Final && ((Final) r1).value == top) { + return r1; + } + if (r2 instanceof Final && ((Final) r2).value == top) { + return r2; + } + if (r1 instanceof Final && r2 instanceof Final) { + return new Final<Id, T>(lattice.join(((Final<?, T>) r1).value, ((Final<?, T>) r2).value)); + } + if (r1 instanceof Final && r2 instanceof Pending) { + Final<?, T> f1 = (Final<?, T>)r1; + Pending<Id, T> pending = (Pending<Id, T>) r2; + Set<Product<Id, T>> sum1 = new HashSet<Product<Id, T>>(pending.sum); + sum1.add(new Product<Id, T>(f1.value, Collections.<Id>emptySet())); + return new Pending<Id, T>(sum1); + } + if (r1 instanceof Pending && r2 instanceof Final) { + Final<?, T> f2 = (Final<?, T>)r2; + Pending<Id, T> pending = (Pending<Id, T>) r1; + Set<Product<Id, T>> sum1 = new HashSet<Product<Id, T>>(pending.sum); + sum1.add(new Product<Id, T>(f2.value, Collections.<Id>emptySet())); + return new Pending<Id, T>(sum1); + } + Pending<Id, T> pending1 = (Pending<Id, T>) r1; + Pending<Id, T> pending2 = (Pending<Id, T>) r2; + Set<Product<Id, T>> sum = new HashSet<Product<Id, T>>(); + sum.addAll(pending1.sum); + sum.addAll(pending2.sum); + return new Pending<Id, T>(sum); + } +} + +final class Product<K, V> { + @NotNull final V value; + @NotNull final Set<K> ids; + + Product(@NotNull V value, @NotNull Set<K> ids) { + this.value = value; + this.ids = ids; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + Product product = (Product)o; + + if (!ids.equals(product.ids)) return false; + if (!value.equals(product.value)) return false; + + return true; + } + + @Override + public int hashCode() { + int result = value.hashCode(); + result = 31 * result + ids.hashCode(); + return result; + } +} + +interface Result<Id, T> {} +final class Final<Id, T> implements Result<Id, T> { + final T value; + Final(T value) { + this.value = value; + } + + @Override + public String toString() { + return "Final{" + "value=" + value + '}'; + } +} + +final class Pending<Id, T> implements Result<Id, T> { + final Set<Product<Id, T>> sum; + + Pending(Set<Product<Id, T>> sum) { + this.sum = sum; + } + +} + +interface IntIdResult {} +// this just wrapper, no need for this really +final class IntIdFinal implements IntIdResult { + final Value value; + public IntIdFinal(Value value) { + this.value = value; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + IntIdFinal that = (IntIdFinal)o; + + if (value != that.value) return false; + + return true; + } + + @Override + public int hashCode() { + return value.ordinal(); + } + + @Override + public String toString() { + return super.toString(); + } +} + +final class IntIdPending implements IntIdResult { + final IntIdComponent[] delta; + + IntIdPending(IntIdComponent[] delta) { + this.delta = delta; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (!(o instanceof IntIdPending)) return false; + IntIdPending pending = (IntIdPending)o; + return !Arrays.equals(delta, pending.delta); + } + + @Override + public int hashCode() { + return Arrays.hashCode(delta); + } + + IntIdPending copy() { + IntIdComponent[] delta1 = new IntIdComponent[delta.length]; + for (int i = 0; i < delta.length; i++) { + delta1[i] = delta[i].copy(); + } + return new IntIdPending(delta1); + } +} + +final class IntIdEquation { + final int id; + final IntIdResult rhs; + + IntIdEquation(int id, IntIdResult rhs) { + this.id = id; + this.rhs = rhs; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (!(o instanceof IntIdEquation)) return false; + + IntIdEquation equation = (IntIdEquation)o; + + if (id != equation.id) return false; + if (!rhs.equals(equation.rhs)) return false; + + return true; + } + + @Override + public int hashCode() { + int result = id; + result = 31 * result + rhs.hashCode(); + return result; + } +} + +final class Solution<Id, Val> { + final Id id; + final Val value; + + Solution(Id id, Val value) { + this.id = id; + this.value = value; + } +} + +final class Equation<Id, T> { + final Id id; + final Result<Id, T> rhs; + + Equation(Id id, Result<Id, T> rhs) { + this.id = id; + this.rhs = rhs; + } + + @Override + public String toString() { + return "Equation{" + "id=" + id + ", rhs=" + rhs + '}'; + } +} + +final class IntIdSolver { + + private int size = 0; + private final ELattice<Value> lattice; + private final IntToIntSetMap dependencies = new IntToIntSetMap(10000, 0.5f); + private final TIntObjectHashMap<IntIdPending> pending = new TIntObjectHashMap<IntIdPending>(); + private final TIntObjectHashMap<Value> solved = new TIntObjectHashMap<Value>(); + private final IntStack moving = new IntStack(); + + int getSize() { + return size; + } + + IntIdSolver(ELattice<Value> lattice) { + this.lattice = lattice; + } + + void addEquation(IntIdEquation equation) { + size ++; + IntIdResult rhs = equation.rhs; + if (rhs instanceof IntIdFinal) { + solved.put(equation.id, ((IntIdFinal) rhs).value); + moving.push(equation.id); + } else if (rhs instanceof IntIdPending) { + IntIdPending pendResult = ((IntIdPending)rhs).copy(); + IntIdResult norm = normalize(pendResult.delta); + if (norm instanceof IntIdFinal) { + solved.put(equation.id, ((IntIdFinal) norm).value); + moving.push(equation.id); + } + else { + IntIdPending pendResult1 = ((IntIdPending)rhs).copy(); + for (IntIdComponent component : pendResult1.delta) { + for (int trigger : component.ids) { + dependencies.addOccurence(trigger, equation.id); + } + pending.put(equation.id, pendResult1); + } + } + } + } + + TIntObjectHashMap<Value> solve() { + while (!moving.empty()) { + int id = moving.pop(); + Value value = solved.get(id); + + boolean stable = id > 0; + int[] pIds = stable ? new int[]{id, -id} : new int[]{-id, id}; + Value[] pVals = stable ? new Value[]{value, value} : new Value[]{value, lattice.top}; + + for (int i = 0; i < pIds.length; i++) { + int pId = pIds[i]; + Value pVal = pVals[i]; + // todo - remove + int[] dIds = dependencies.get(pId); + for (int dId : dIds) { + IntIdPending pend = pending.remove(dId); + if (pend != null) { + IntIdResult pend1 = substitute(pend, pId, pVal); + if (pend1 instanceof IntIdFinal) { + IntIdFinal fi = (IntIdFinal)pend1; + solved.put(dId, fi.value); + moving.push(dId); + } + else { + pending.put(dId, (IntIdPending)pend1); + } + } + } + } + } + pending.clear(); + return solved; + } + + // substitute id -> value into pending + IntIdResult substitute(IntIdPending pending, int id, Value value) { + IntIdComponent[] sum = pending.delta; + for (IntIdComponent intIdComponent : sum) { + if (intIdComponent.remove(id)) { + intIdComponent.value = lattice.meet(intIdComponent.value, value); + } + } + return normalize(sum); + } + + IntIdResult normalize(IntIdComponent[] sum) { + Value acc = lattice.bot; + boolean computableNow = true; + for (IntIdComponent prod : sum) { + if (prod.isEmpty() || prod.value == lattice.bot) { + acc = lattice.join(acc, prod.value); + } else { + computableNow = false; + } + } + return (acc == lattice.top || computableNow) ? new IntIdFinal(acc) : new IntIdPending(sum); + } + +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/ContractInference.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/ContractInference.java index 534d65b07531..a1c908837ad0 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/ContractInference.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/ContractInference.java @@ -15,6 +15,7 @@ */ package com.intellij.codeInspection.dataFlow; +import com.intellij.codeInsight.NullableNotNullManager; import com.intellij.codeInspection.dataFlow.MethodContract.ValueConstraint; import com.intellij.openapi.util.Computable; import com.intellij.openapi.util.Condition; @@ -41,6 +42,10 @@ public class ContractInference { @NotNull public static List<MethodContract> inferContracts(@NotNull final PsiMethod method) { + if (method instanceof PsiCompiledElement) { + return Collections.emptyList(); + } + return CachedValuesManager.getCachedValue(method, new CachedValueProvider<List<MethodContract>>() { @Nullable @Override @@ -70,7 +75,12 @@ class ContractInferenceInterpreter { } else if (statements[0] instanceof PsiExpressionStatement && ((PsiExpressionStatement)statements[0]).getExpression() instanceof PsiMethodCallExpression) { List<MethodContract> result = handleDelegation(((PsiExpressionStatement)statements[0]).getExpression(), false); - if (result != null) return result; + if (result != null) return ContainerUtil.findAll(result, new Condition<MethodContract>() { + @Override + public boolean value(MethodContract contract) { + return contract.returnValue == THROW_EXCEPTION || !textMatches(myMethod.getReturnTypeElement(), PsiKeyword.VOID); + } + }); } } @@ -103,7 +113,7 @@ class ContractInferenceInterpreter { return RecursionManager.doPreventingRecursion(myMethod, true, new Computable<List<MethodContract>>() { @Override public List<MethodContract> compute() { - List<MethodContract> delegateContracts = ContractInference.inferContracts(targetMethod); //todo use explicit contracts, too + List<MethodContract> delegateContracts = ControlFlowAnalyzer.getMethodContracts(targetMethod); return ContainerUtil.mapNotNull(delegateContracts, new NullableFunction<MethodContract, MethodContract>() { @Nullable @Override @@ -125,7 +135,7 @@ class ContractInferenceInterpreter { } } } - return new MethodContract(answer, negated ? negateConstraint(delegateContract.returnValue) : delegateContract.returnValue); + return answer == null ? null : new MethodContract(answer, negated ? negateConstraint(delegateContract.returnValue) : delegateContract.returnValue); } }); } @@ -173,10 +183,12 @@ class ContractInferenceInterpreter { if (expr instanceof PsiInstanceOfExpression) { final int parameter = resolveParameter(((PsiInstanceOfExpression)expr).getOperand()); if (parameter >= 0) { - return ContainerUtil.map(states, new Function<ValueConstraint[], MethodContract>() { + return ContainerUtil.mapNotNull(states, new Function<ValueConstraint[], MethodContract>() { @Override public MethodContract fun(ValueConstraint[] state) { - return new MethodContract(withConstraint(state, parameter, NULL_VALUE), FALSE_VALUE); + ValueConstraint paramConstraint = NULL_VALUE; + ValueConstraint returnValue = FALSE_VALUE; + return contractWithConstraint(state, parameter, paramConstraint, returnValue); } }); } @@ -187,17 +199,17 @@ class ContractInferenceInterpreter { return toContracts(states, constraint); } - int parameter = resolveParameter(expr); - if (parameter >= 0) { + int paramIndex = resolveParameter(expr); + if (paramIndex >= 0) { List<MethodContract> result = ContainerUtil.newArrayList(); for (ValueConstraint[] state : states) { - if (state[parameter] != ANY_VALUE) { + if (state[paramIndex] != ANY_VALUE) { // the second 'o' reference in cases like: if (o != null) return o; - result.add(new MethodContract(state, state[parameter])); - } else { + result.add(new MethodContract(state, state[paramIndex])); + } else if (textMatches(myMethod.getParameterList().getParameters()[paramIndex].getTypeElement(), PsiKeyword.BOOLEAN)) { // if (boolValue) ... - result.add(new MethodContract(withConstraint(state, parameter, TRUE_VALUE), TRUE_VALUE)); - result.add(new MethodContract(withConstraint(state, parameter, FALSE_VALUE), FALSE_VALUE)); + ContainerUtil.addIfNotNull(result, contractWithConstraint(state, paramIndex, TRUE_VALUE, TRUE_VALUE)); + ContainerUtil.addIfNotNull(result, contractWithConstraint(state, paramIndex, FALSE_VALUE, FALSE_VALUE)); } } return result; @@ -206,6 +218,18 @@ class ContractInferenceInterpreter { return Collections.emptyList(); } + @Nullable + private MethodContract contractWithConstraint(ValueConstraint[] state, + int parameter, ValueConstraint paramConstraint, + ValueConstraint returnValue) { + ValueConstraint[] newState = withConstraint(state, parameter, paramConstraint); + return newState == null ? null : new MethodContract(newState, returnValue); + } + + private static boolean textMatches(@Nullable PsiTypeElement typeElement, @NotNull String text) { + return typeElement != null && typeElement.textMatches(text); + } + private List<MethodContract> visitEqualityComparison(List<ValueConstraint[]> states, PsiExpression op1, PsiExpression op2, @@ -219,8 +243,9 @@ class ContractInferenceInterpreter { if (parameter >= 0 && constraint != null) { List<MethodContract> result = ContainerUtil.newArrayList(); for (ValueConstraint[] state : states) { - result.add(new MethodContract(withConstraint(state, parameter, constraint), equality ? TRUE_VALUE : FALSE_VALUE)); - result.add(new MethodContract(withConstraint(state, parameter, negateConstraint(constraint)), equality ? FALSE_VALUE : TRUE_VALUE)); + ContainerUtil.addIfNotNull(result, contractWithConstraint(state, parameter, constraint, equality ? TRUE_VALUE : FALSE_VALUE)); + ContainerUtil.addIfNotNull(result, contractWithConstraint(state, parameter, negateConstraint(constraint), + equality ? FALSE_VALUE : TRUE_VALUE)); } return result; } @@ -295,7 +320,15 @@ class ContractInferenceInterpreter { result.addAll(toContracts(states, THROW_EXCEPTION)); } else if (statement instanceof PsiReturnStatement) { - result.addAll(visitExpression(states, ((PsiReturnStatement)statement).getReturnValue())); + List<MethodContract> contracts = visitExpression(states, ((PsiReturnStatement)statement).getReturnValue()); + for (MethodContract contract : contracts) { + if ((contract.returnValue == TRUE_VALUE || contract.returnValue == FALSE_VALUE) && + !textMatches(myMethod.getReturnTypeElement(), PsiKeyword.BOOLEAN)) { + continue; + } + + result.add(contract); + } } else if (statement instanceof PsiAssertStatement) { List<MethodContract> conditionResults = visitExpression(states, ((PsiAssertStatement)statement).getAssertCondition()); @@ -357,7 +390,19 @@ class ContractInferenceInterpreter { return -1; } - private static ValueConstraint[] withConstraint(ValueConstraint[] constraints, int index, ValueConstraint constraint) { + @Nullable + private ValueConstraint[] withConstraint(ValueConstraint[] constraints, int index, ValueConstraint constraint) { + if (constraints[index] == constraint) return constraints; + + ValueConstraint negated = negateConstraint(constraint); + if (negated != constraint && constraints[index] == negated) { + return null; + } + + if (constraint == NULL_VALUE && NullableNotNullManager.isNotNull(myMethod.getParameterList().getParameters()[index])) { + return null; + } + ValueConstraint[] copy = constraints.clone(); copy[index] = constraint; return copy; diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/ControlFlowAnalyzer.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/ControlFlowAnalyzer.java index 65e7fd7c859a..7ef19f2b73d0 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/ControlFlowAnalyzer.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/ControlFlowAnalyzer.java @@ -20,7 +20,6 @@ import com.intellij.codeInspection.dataFlow.instructions.*; import com.intellij.codeInspection.dataFlow.value.*; import com.intellij.openapi.diagnostic.Logger; import com.intellij.openapi.util.Condition; -import com.intellij.openapi.util.registry.Registry; import com.intellij.psi.*; import com.intellij.psi.search.GlobalSearchScope; import com.intellij.psi.tree.IElementType; @@ -30,37 +29,15 @@ import com.intellij.util.containers.ContainerUtil; import com.intellij.util.containers.Stack; import com.siyeh.ig.numeric.UnnecessaryExplicitNumericCastInspection; import org.jetbrains.annotations.Contract; -import org.jetbrains.annotations.NonNls; import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.Nullable; import java.util.*; -import java.util.regex.Pattern; -import static com.intellij.codeInspection.dataFlow.MethodContract.ValueConstraint; import static com.intellij.psi.CommonClassNames.*; public class ControlFlowAnalyzer extends JavaElementVisitor { private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.dataFlow.ControlFlowAnalyzer"); - private static final Condition<String> FALSE_GETTERS = parseFalseGetters(); - - private static Condition<String> parseFalseGetters() { - try { - final Pattern pattern = Pattern.compile(Registry.stringValue("ide.dfa.getters.with.side.effects")); - return new Condition<String>() { - @Override - public boolean value(String s) { - return pattern.matcher(s).matches(); - } - }; - } - catch (Exception e) { - LOG.error(e); - //noinspection unchecked - return Condition.FALSE; - } - } - public static final String ORG_JETBRAINS_ANNOTATIONS_CONTRACT = Contract.class.getName(); private boolean myIgnoreAssertions; @@ -209,9 +186,23 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { } addInstruction(new AssignInstruction(rExpr)); + + flushArrayElementsOnUnknownIndexAssignment(lExpr); + finishElement(expression); } + private void flushArrayElementsOnUnknownIndexAssignment(PsiExpression lExpr) { + if (lExpr instanceof PsiArrayAccessExpression && + myFactory.createValue(lExpr) == null // check for unknown index, otherwise AssignInstruction will flush only that element + ) { + DfaValue arrayVar = myFactory.createValue(((PsiArrayAccessExpression)lExpr).getArrayExpression()); + if (arrayVar instanceof DfaVariableValue) { + addInstruction(new FlushVariableInstruction((DfaVariableValue)arrayVar)); + } + } + } + private void generateDefaultAssignmentBinOp(PsiExpression lExpr, PsiExpression rExpr, final PsiType exprType) { lExpr.accept(this); addInstruction(new DupInstruction()); @@ -635,7 +626,7 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { ((PsiReferenceExpression)caseExpression).getQualifierExpression() == null && JavaPsiFacade.getInstance(body.getProject()).getConstantEvaluationHelper().computeConstantExpression(caseValue) != null) { - addInstruction(new PushInstruction(getExpressionDfaValue((PsiReferenceExpression)caseExpression), caseExpression)); + addInstruction(new PushInstruction(myFactory.createValue(caseExpression), caseExpression)); caseValue.accept(this); addInstruction(new BinopInstruction(JavaTokenType.EQEQ, null, caseExpression.getProject())); } @@ -1030,7 +1021,8 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { addInstruction(new PopInstruction()); } - pushTypeOrUnknown(arrayExpression); + DfaValue toPush = myFactory.createValue(expression); + addInstruction(new PushInstruction(toPush != null ? toPush : myFactory.createTypeValue(expression.getType(), Nullness.UNKNOWN), null)); finishElement(expression); } @@ -1396,8 +1388,8 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { } addConditionalRuntimeThrow(); - List<MethodContract> contracts = method instanceof PsiMethod ? getMethodContracts((PsiMethod)method) : Collections.<MethodContract>emptyList(); - addInstruction(new MethodCallInstruction(expression, createChainedVariableValue(expression), contracts)); + List<MethodContract> contracts = method instanceof PsiMethod ? getMethodCallContracts((PsiMethod)method, expression) : Collections.<MethodContract>emptyList(); + addInstruction(new MethodCallInstruction(expression, myFactory.createValue(expression), contracts)); if (!contracts.isEmpty()) { // if a contract resulted in 'fail', handle it addInstruction(new DupInstruction()); @@ -1431,6 +1423,11 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { finishElement(expression); } + private static List<MethodContract> getMethodCallContracts(@NotNull final PsiMethod method, @NotNull PsiMethodCallExpression call) { + List<MethodContract> contracts = HardcodedContracts.getHardcodedContracts(method, call); + return !contracts.isEmpty() ? contracts : getMethodContracts(method); + } + static List<MethodContract> getMethodContracts(@NotNull final PsiMethod method) { final PsiAnnotation contractAnno = findContractAnnotation(method); final int paramCount = method.getParameterList().getParametersCount(); @@ -1458,45 +1455,6 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { }); } - @NonNls String methodName = method.getName(); - - PsiClass owner = method.getContainingClass(); - if (owner != null) { - final String className = owner.getQualifiedName(); - if ("java.lang.System".equals(className)) { - if ("exit".equals(methodName)) { - return Collections.singletonList(new MethodContract(MethodContract.createConstraintArray(paramCount), ValueConstraint.THROW_EXCEPTION)); - } - } - else if ("junit.framework.Assert".equals(className) || "org.junit.Assert".equals(className) || - "junit.framework.TestCase".equals(className) || "org.testng.Assert".equals(className) || "org.testng.AssertJUnit".equals(className)) { - boolean testng = className.startsWith("org.testng."); - if ("fail".equals(methodName)) { - return Collections.singletonList(new MethodContract(MethodContract.createConstraintArray(paramCount), ValueConstraint.THROW_EXCEPTION)); - } - - int checkedParam = testng ? 0 : paramCount - 1; - ValueConstraint[] constraints = MethodContract.createConstraintArray(paramCount); - if ("assertTrue".equals(methodName)) { - constraints[checkedParam] = ValueConstraint.FALSE_VALUE; - return Collections.singletonList(new MethodContract(constraints, ValueConstraint.THROW_EXCEPTION)); - } - if ("assertFalse".equals(methodName)) { - constraints[checkedParam] = ValueConstraint.TRUE_VALUE; - return Collections.singletonList(new MethodContract(constraints, ValueConstraint.THROW_EXCEPTION)); - } - if ("assertNull".equals(methodName)) { - constraints[checkedParam] = ValueConstraint.NOT_NULL_VALUE; - return Collections.singletonList(new MethodContract(constraints, ValueConstraint.THROW_EXCEPTION)); - } - if ("assertNotNull".equals(methodName)) { - constraints[checkedParam] = ValueConstraint.NULL_VALUE; - return Collections.singletonList(new MethodContract(constraints, ValueConstraint.THROW_EXCEPTION)); - } - return Collections.emptyList(); - } - } - return Collections.emptyList(); } @@ -1505,20 +1463,6 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { return AnnotationUtil.findAnnotation(method, ORG_JETBRAINS_ANNOTATIONS_CONTRACT); } - private void pushTypeOrUnknown(PsiExpression expr) { - PsiType type = expr.getType(); - - final DfaValue dfaValue; - if (type instanceof PsiClassType) { - dfaValue = myFactory.createTypeValue(type, Nullness.UNKNOWN); - } - else { - dfaValue = null; - } - - addInstruction(new PushInstruction(dfaValue, null)); - } - @Override public void visitNewExpression(PsiNewExpression expression) { startElement(expression); @@ -1657,88 +1601,11 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { } boolean referenceRead = PsiUtil.isAccessedForReading(expression) && !PsiUtil.isAccessedForWriting(expression); - addInstruction(new PushInstruction(getExpressionDfaValue(expression), expression, referenceRead)); + addInstruction(new PushInstruction(myFactory.createValue(expression), expression, referenceRead)); finishElement(expression); } - @Nullable - private DfaValue getExpressionDfaValue(PsiReferenceExpression expression) { - DfaValue dfaValue = myFactory.createReferenceValue(expression); - if (dfaValue == null) { - PsiElement resolved = expression.resolve(); - if (resolved instanceof PsiField) { - dfaValue = createDfaValueForAnotherInstanceMemberAccess(expression, (PsiField)resolved); - } - } - return dfaValue; - } - - @NotNull - private DfaValue createDfaValueForAnotherInstanceMemberAccess(PsiReferenceExpression expression, PsiField field) { - DfaValue dfaValue = null; - if (expression.getQualifierExpression() != null) { - dfaValue = createChainedVariableValue(expression); - } - if (dfaValue == null) { - PsiType type = expression.getType(); - return myFactory.createTypeValue(type, DfaPsiUtil.getElementNullability(type, field)); - } - return dfaValue; - } - - @Nullable - private DfaVariableValue createChainedVariableValue(@Nullable PsiExpression expression) { - if (expression instanceof PsiParenthesizedExpression) { - return createChainedVariableValue(((PsiParenthesizedExpression)expression).getExpression()); - } - - PsiReferenceExpression refExpr; - if (expression instanceof PsiMethodCallExpression) { - refExpr = ((PsiMethodCallExpression)expression).getMethodExpression(); - } - else if (expression instanceof PsiReferenceExpression) { - refExpr = (PsiReferenceExpression)expression; - } - else { - return null; - } - - PsiElement target = refExpr.resolve(); - PsiModifierListOwner var = getAccessedVariable(target); - if (var == null) { - return null; - } - - if (DfaValueFactory.isEffectivelyUnqualified(refExpr)) { - return myFactory.getVarFactory().createVariableValue(var, refExpr.getType(), false, null); - } - - if (!(var instanceof PsiField) || !var.hasModifierProperty(PsiModifier.TRANSIENT) && !var.hasModifierProperty(PsiModifier.VOLATILE)) { - DfaVariableValue qualifierValue = createChainedVariableValue(refExpr.getQualifierExpression()); - if (qualifierValue != null) { - return myFactory.getVarFactory().createVariableValue(var, refExpr.getType(), false, qualifierValue); - } - } - return null; - } - - @Nullable - private static PsiModifierListOwner getAccessedVariable(final PsiElement target) { - if (target instanceof PsiVariable) { - return (PsiVariable)target; - } - if (target instanceof PsiMethod) { - if (PropertyUtil.isSimplePropertyGetter((PsiMethod)target)) { - String qName = PsiUtil.getMemberQualifiedName((PsiMethod)target); - if (qName == null || !FALSE_GETTERS.value(qName)) { - return (PsiMethod)target; - } - } - } - return null; - } - @Override public void visitSuperExpression(PsiSuperExpression expression) { startElement(expression); addInstruction(new PushInstruction(myFactory.createTypeValue(expression.getType(), Nullness.NOT_NULL), null)); @@ -1769,7 +1636,7 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { generateBoxingUnboxingInstructionFor(operand, castExpression.getType()); } else { - pushTypeOrUnknown(castExpression); + addInstruction(new PushInstruction(myFactory.createTypeValue(castExpression.getType(), Nullness.UNKNOWN), null)); } final PsiTypeElement typeElement = castExpression.getCastType(); diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DataFlowInspectionBase.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DataFlowInspectionBase.java index 3e017e091084..d66d63bf85c3 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DataFlowInspectionBase.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DataFlowInspectionBase.java @@ -32,7 +32,8 @@ import com.intellij.codeInsight.daemon.impl.quickfix.SimplifyBooleanExpressionFi import com.intellij.codeInsight.intention.impl.AddNullableAnnotationFix; import com.intellij.codeInspection.*; import com.intellij.codeInspection.dataFlow.instructions.*; -import com.intellij.codeInspection.dataFlow.value.*; +import com.intellij.codeInspection.dataFlow.value.DfaConstValue; +import com.intellij.codeInspection.dataFlow.value.DfaValue; import com.intellij.openapi.diagnostic.Logger; import com.intellij.openapi.project.Project; import com.intellij.openapi.util.Condition; @@ -41,9 +42,9 @@ import com.intellij.openapi.util.WriteExternalException; import com.intellij.openapi.util.text.StringUtil; import com.intellij.pom.java.LanguageLevel; import com.intellij.psi.*; -import com.intellij.psi.codeStyle.JavaCodeStyleManager; import com.intellij.psi.util.PsiTreeUtil; import com.intellij.psi.util.PsiUtil; +import com.intellij.refactoring.extractMethod.ExtractMethodUtil; import com.intellij.util.ArrayUtil; import com.intellij.util.ArrayUtilRt; import com.intellij.util.IncorrectOperationException; @@ -106,7 +107,6 @@ public class DataFlowInspectionBase extends BaseJavaBatchLocalInspectionTool { public void visitIfStatement(PsiIfStatement statement) { PsiExpression condition = statement.getCondition(); if (BranchingInstruction.isBoolConst(condition)) { - assert condition != null; LocalQuickFix fix = createSimplifyBooleanExpressionFix(condition, condition.textMatches(PsiKeyword.TRUE)); holder.registerProblem(condition, "Condition is always " + condition.getText(), fix); } @@ -253,7 +253,7 @@ public class DataFlowInspectionBase extends BaseJavaBatchLocalInspectionTool { final Object value = pair.second.getValue(); PsiVariable constant = pair.second.getConstant(); final String presentableName = constant != null ? constant.getName() : String.valueOf(value); - final String exprText = getConstantValueText(value, constant); + final String exprText = String.valueOf(value); if (presentableName == null || exprText == null) { continue; } @@ -280,31 +280,23 @@ public class DataFlowInspectionBase extends BaseJavaBatchLocalInspectionTool { PsiElement problemElement = descriptor.getPsiElement(); if (problemElement == null) return; + PsiMethodCallExpression call = problemElement.getParent() instanceof PsiExpressionList && + problemElement.getParent().getParent() instanceof PsiMethodCallExpression ? + (PsiMethodCallExpression)problemElement.getParent().getParent() : + null; + PsiMethod targetMethod = call == null ? null : call.resolveMethod(); + JavaPsiFacade facade = JavaPsiFacade.getInstance(project); - PsiElement newElement = problemElement.replace(facade.getElementFactory().createExpressionFromText(exprText, null)); - newElement = JavaCodeStyleManager.getInstance(project).shortenClassReferences(newElement); - if (newElement instanceof PsiJavaCodeReferenceElement) { - PsiJavaCodeReferenceElement ref = (PsiJavaCodeReferenceElement)newElement; - PsiElement target = ref.resolve(); - String shortName = ref.getReferenceName(); - if (target != null && shortName != null && ref.isQualified() && - facade.getResolveHelper().resolveReferencedVariable(shortName, newElement) == target) { - newElement.replace(facade.getElementFactory().createExpressionFromText(shortName, null)); - } + problemElement.replace(facade.getElementFactory().createExpressionFromText(exprText, null)); + + if (targetMethod != null) { + ExtractMethodUtil.addCastsToEnsureResolveTarget(targetMethod, call); } } }); } } - private static String getConstantValueText(Object value, @Nullable PsiVariable constant) { - if (constant != null) { - return constant instanceof PsiMember ? PsiUtil.getMemberQualifiedName((PsiMember)constant) : constant.getName(); - } - - return value instanceof String ? "\"" + StringUtil.escapeStringCharacters((String)value) + "\"" : String.valueOf(value); - } - private void reportNullableArgumentsPassedToNonAnnotated(DataFlowInstructionVisitor visitor, ProblemsHolder holder, Set<PsiElement> reportedAnchors) { for (PsiElement expr : visitor.getProblems(NullabilityProblem.passingNullableArgumentToNonAnnotatedParameter)) { if (reportedAnchors.contains(expr)) continue; diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DfaPsiUtil.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DfaPsiUtil.java index e6c278e1414b..4dd2ac23c9ae 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DfaPsiUtil.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DfaPsiUtil.java @@ -17,16 +17,15 @@ package com.intellij.codeInspection.dataFlow; import com.intellij.codeInsight.NullableNotNullManager; import com.intellij.codeInspection.dataFlow.instructions.Instruction; +import com.intellij.codeInspection.dataFlow.instructions.MethodCallInstruction; import com.intellij.codeInspection.dataFlow.instructions.ReturnInstruction; +import com.intellij.codeInspection.dataFlow.value.DfaValueFactory; import com.intellij.openapi.util.Ref; import com.intellij.psi.*; import com.intellij.psi.search.LocalSearchScope; import com.intellij.psi.search.searches.ReferencesSearch; import com.intellij.psi.tree.IElementType; -import com.intellij.psi.util.CachedValueProvider; -import com.intellij.psi.util.CachedValuesManager; -import com.intellij.psi.util.PsiModificationTracker; -import com.intellij.psi.util.PsiTreeUtil; +import com.intellij.psi.util.*; import com.intellij.util.NullableFunction; import com.intellij.util.containers.ContainerUtil; import com.intellij.util.containers.MultiMap; @@ -126,11 +125,36 @@ public class DfaPsiUtil { shouldCheck = psiBlock == body; } + private boolean isCallExposingNonInitializedFields(Instruction instruction) { + if (!(instruction instanceof MethodCallInstruction) || + ((MethodCallInstruction)instruction).getMethodType() != MethodCallInstruction.MethodType.REGULAR_METHOD_CALL) { + return false; + } + + PsiCallExpression call = ((MethodCallInstruction)instruction).getCallExpression(); + if (call == null) return false; + + if (call instanceof PsiMethodCallExpression && + DfaValueFactory.isEffectivelyUnqualified(((PsiMethodCallExpression)call).getMethodExpression())) { + return true; + } + + PsiExpressionList argumentList = call.getArgumentList(); + if (argumentList != null) { + for (PsiExpression expression : argumentList.getExpressions()) { + if (expression instanceof PsiThisExpression) return true; + } + } + + return false; + } + @Override protected DfaInstructionState[] acceptInstruction(InstructionVisitor visitor, DfaInstructionState instructionState) { if (shouldCheck) { Instruction instruction = instructionState.getInstruction(); - if (instruction instanceof ReturnInstruction && !((ReturnInstruction)instruction).isViaException()) { + if (isCallExposingNonInitializedFields(instruction) || + instruction instanceof ReturnInstruction && !((ReturnInstruction)instruction).isViaException()) { for (PsiField field : containingClass.getFields()) { if (!instructionState.getMemoryState().isNotNull(getFactory().getVarFactory().createVariableValue(field, false))) { map.put(field, false); @@ -138,6 +162,7 @@ public class DfaPsiUtil { map.put(field, true); } } + return DfaInstructionState.EMPTY_ARRAY; } } return super.acceptInstruction(visitor, instructionState); diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/HardcodedContracts.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/HardcodedContracts.java new file mode 100644 index 000000000000..7e77dc281c1d --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/HardcodedContracts.java @@ -0,0 +1,133 @@ +/* + * 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.dataFlow; + +import com.intellij.psi.*; +import com.siyeh.ig.psiutils.ExpressionUtils; +import org.jetbrains.annotations.NotNull; + +import java.util.Collections; +import java.util.List; + +import static com.intellij.codeInspection.dataFlow.MethodContract.ValueConstraint.*; +import static com.intellij.codeInspection.dataFlow.MethodContract.createConstraintArray; + +/** + * @author peter + */ +class HardcodedContracts { + static List<MethodContract> getHardcodedContracts(@NotNull PsiMethod method, @NotNull PsiMethodCallExpression call) { + PsiClass owner = method.getContainingClass(); + if (owner == null) return Collections.emptyList(); + + final int paramCount = method.getParameterList().getParametersCount(); + String className = owner.getQualifiedName(); + String methodName = method.getName(); + + if ("java.lang.System".equals(className)) { + if ("exit".equals(methodName)) { + return Collections.singletonList(new MethodContract(createConstraintArray(paramCount), THROW_EXCEPTION)); + } + } + else if ("com.google.common.base.Preconditions".equals(className)) { + if ("checkNotNull".equals(methodName) && paramCount > 0) { + MethodContract.ValueConstraint[] constraints = createConstraintArray(paramCount); + constraints[0] = NULL_VALUE; + return Collections.singletonList(new MethodContract(constraints, THROW_EXCEPTION)); + } + } + else if ("junit.framework.Assert".equals(className) || + "org.junit.Assert".equals(className) || + "junit.framework.TestCase".equals(className) || + "org.testng.Assert".equals(className) || + "org.testng.AssertJUnit".equals(className)) { + return handleTestFrameworks(paramCount, className, methodName, call); + } + + return Collections.emptyList(); + } + + private static boolean isNotNullMatcher(PsiExpression expr) { + if (expr instanceof PsiMethodCallExpression) { + String calledName = ((PsiMethodCallExpression)expr).getMethodExpression().getReferenceName(); + if ("notNullValue".equals(calledName)) { + return true; + } + if ("not".equals(calledName)) { + PsiExpression[] notArgs = ((PsiMethodCallExpression)expr).getArgumentList().getExpressions(); + if (notArgs.length == 1 && + notArgs[0] instanceof PsiMethodCallExpression && + "equalTo".equals(((PsiMethodCallExpression)notArgs[0]).getMethodExpression().getReferenceName())) { + PsiExpression[] equalArgs = ((PsiMethodCallExpression)notArgs[0]).getArgumentList().getExpressions(); + if (equalArgs.length == 1 && ExpressionUtils.isNullLiteral(equalArgs[0])) { + return true; + } + } + } + } + return false; + } + + private static List<MethodContract> handleTestFrameworks(int paramCount, String className, String methodName, + @NotNull PsiMethodCallExpression call) { + if ("assertThat".equals(methodName)) { + PsiExpression[] args = call.getArgumentList().getExpressions(); + if (args.length == paramCount) { + for (int i = 1; i < args.length; i++) { + if (isNotNullMatcher(args[i])) { + MethodContract.ValueConstraint[] constraints = createConstraintArray(args.length); + constraints[i - 1] = NULL_VALUE; + return Collections.singletonList(new MethodContract(constraints, THROW_EXCEPTION)); + } + } + } + return Collections.emptyList(); + } + + if (!"junit.framework.Assert".equals(className) && + !"junit.framework.TestCase".equals(className) && + !"org.junit.Assert".equals(className) && + !"org.testng.Assert".equals(className) && + !"org.testng.AssertJUnit".equals(className)) { + return Collections.emptyList(); + } + + boolean testng = className.startsWith("org.testng."); + if ("fail".equals(methodName)) { + return Collections.singletonList(new MethodContract(createConstraintArray(paramCount), THROW_EXCEPTION)); + } + + int checkedParam = testng ? 0 : paramCount - 1; + MethodContract.ValueConstraint[] constraints = createConstraintArray(paramCount); + if ("assertTrue".equals(methodName)) { + constraints[checkedParam] = FALSE_VALUE; + return Collections.singletonList(new MethodContract(constraints, THROW_EXCEPTION)); + } + if ("assertFalse".equals(methodName)) { + constraints[checkedParam] = TRUE_VALUE; + return Collections.singletonList(new MethodContract(constraints, THROW_EXCEPTION)); + } + if ("assertNull".equals(methodName)) { + constraints[checkedParam] = NOT_NULL_VALUE; + return Collections.singletonList(new MethodContract(constraints, THROW_EXCEPTION)); + } + if ("assertNotNull".equals(methodName)) { + constraints[checkedParam] = NULL_VALUE; + return Collections.singletonList(new MethodContract(constraints, THROW_EXCEPTION)); + } + return Collections.emptyList(); + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/MethodContract.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/MethodContract.java index 160f69ba349e..691c2f00d985 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/MethodContract.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/MethodContract.java @@ -20,6 +20,7 @@ import com.intellij.codeInspection.dataFlow.value.DfaValueFactory; import com.intellij.openapi.util.text.StringUtil; import com.intellij.util.Function; import com.intellij.util.containers.ContainerUtil; +import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.Nullable; import java.util.List; @@ -31,7 +32,7 @@ public class MethodContract { public final ValueConstraint[] arguments; public final ValueConstraint returnValue; - public MethodContract(ValueConstraint[] arguments, ValueConstraint returnValue) { + public MethodContract(@NotNull ValueConstraint[] arguments, @NotNull ValueConstraint returnValue) { this.arguments = arguments; this.returnValue = returnValue; } diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/StandardInstructionVisitor.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/StandardInstructionVisitor.java index 522bd34a9cf7..013e24cbe07a 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/StandardInstructionVisitor.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/StandardInstructionVisitor.java @@ -455,10 +455,10 @@ public class StandardInstructionVisitor extends InstructionVisitor { DfaValue dfaRight, DfaValue dfaLeft, IElementType opSign) { if (dfaRight instanceof DfaConstValue && dfaLeft instanceof DfaVariableValue) { - PsiType varType = ((DfaVariableValue)dfaLeft).getVariableType(); Object value = ((DfaConstValue)dfaRight).getValue(); - if (varType instanceof PsiPrimitiveType && value instanceof Number) { - DfaInstructionState[] result = checkTypeRanges(instruction, runner, memState, opSign, varType, ((Number)value).longValue()); + if (value instanceof Number) { + DfaInstructionState[] result = checkComparingWithConstant(instruction, runner, memState, (DfaVariableValue)dfaLeft, opSign, + ((Number)value).doubleValue()); if (result != null) { return result; } @@ -485,33 +485,60 @@ public class StandardInstructionVisitor extends InstructionVisitor { return null; } - private static DfaInstructionState[] checkTypeRanges(BinopInstruction instruction, - DataFlowRunner runner, - DfaMemoryState memState, - IElementType opSign, PsiType varType, long constantValue) { - long minValue = varType == PsiType.BYTE ? Byte.MIN_VALUE : - varType == PsiType.SHORT ? Short.MIN_VALUE : - varType == PsiType.INT ? Integer.MIN_VALUE : - varType == PsiType.CHAR ? Character.MIN_VALUE : - Long.MIN_VALUE; - long maxValue = varType == PsiType.BYTE ? Byte.MAX_VALUE : - varType == PsiType.SHORT ? Short.MAX_VALUE : - varType == PsiType.INT ? Integer.MAX_VALUE : - varType == PsiType.CHAR ? Character.MAX_VALUE : - Long.MAX_VALUE; - - if (constantValue < minValue || constantValue > maxValue) { + @Nullable + private static DfaInstructionState[] checkComparingWithConstant(BinopInstruction instruction, + DataFlowRunner runner, + DfaMemoryState memState, + DfaVariableValue var, + IElementType opSign, double comparedWith) { + DfaConstValue knownConstantValue = memState.getConstantValue(var); + Object knownValue = knownConstantValue == null ? null : knownConstantValue.getValue(); + if (knownValue instanceof Number) { + double knownDouble = ((Number)knownValue).doubleValue(); + return checkComparisonWithKnownRange(instruction, runner, memState, opSign, comparedWith, knownDouble, knownDouble); + } + + PsiType varType = var.getVariableType(); + if (!(varType instanceof PsiPrimitiveType)) return null; + + double minValue = varType == PsiType.BYTE ? Byte.MIN_VALUE : + varType == PsiType.SHORT ? Short.MIN_VALUE : + varType == PsiType.INT ? Integer.MIN_VALUE : + varType == PsiType.CHAR ? Character.MIN_VALUE : + varType == PsiType.LONG ? Long.MIN_VALUE : + varType == PsiType.FLOAT ? Float.MIN_VALUE : + Double.MIN_VALUE; + double maxValue = varType == PsiType.BYTE ? Byte.MAX_VALUE : + varType == PsiType.SHORT ? Short.MAX_VALUE : + varType == PsiType.INT ? Integer.MAX_VALUE : + varType == PsiType.CHAR ? Character.MAX_VALUE : + varType == PsiType.LONG ? Long.MAX_VALUE : + varType == PsiType.FLOAT ? Float.MAX_VALUE : + Double.MAX_VALUE; + + return checkComparisonWithKnownRange(instruction, runner, memState, opSign, comparedWith, minValue, maxValue); + } + + @Nullable + private static DfaInstructionState[] checkComparisonWithKnownRange(BinopInstruction instruction, + DataFlowRunner runner, + DfaMemoryState memState, + IElementType opSign, + double comparedWith, + double rangeMin, + double rangeMax) { + if (comparedWith < rangeMin || comparedWith > rangeMax) { if (opSign == EQEQ) return alwaysFalse(instruction, runner, memState); if (opSign == NE) return alwaysTrue(instruction, runner, memState); } - if (opSign == LT && constantValue <= minValue) return alwaysFalse(instruction, runner, memState); - if (opSign == LT && constantValue > maxValue) return alwaysTrue(instruction, runner, memState); - if (opSign == LE && constantValue >= maxValue) return alwaysTrue(instruction, runner, memState); + if (opSign == LT && comparedWith <= rangeMin) return alwaysFalse(instruction, runner, memState); + if (opSign == LT && comparedWith > rangeMax) return alwaysTrue(instruction, runner, memState); + if (opSign == LE && comparedWith >= rangeMax) return alwaysTrue(instruction, runner, memState); - if (opSign == GT && constantValue >= maxValue) return alwaysFalse(instruction, runner, memState); - if (opSign == GT && constantValue < minValue) return alwaysTrue(instruction, runner, memState); - if (opSign == GE && constantValue <= minValue) return alwaysTrue(instruction, runner, memState); + if (opSign == GT && comparedWith >= rangeMax) return alwaysFalse(instruction, runner, memState); + if (opSign == GT && comparedWith < rangeMin) return alwaysTrue(instruction, runner, memState); + if (opSign == GE && comparedWith <= rangeMin) return alwaysTrue(instruction, runner, memState); return null; } diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaExpressionFactory.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaExpressionFactory.java new file mode 100644 index 000000000000..ec9e02fce92d --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaExpressionFactory.java @@ -0,0 +1,170 @@ +/* + * 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.dataFlow.value; + +import com.intellij.codeInspection.dataFlow.DfaPsiUtil; +import com.intellij.codeInspection.dataFlow.Nullness; +import com.intellij.openapi.diagnostic.Logger; +import com.intellij.openapi.util.Condition; +import com.intellij.openapi.util.registry.Registry; +import com.intellij.psi.*; +import com.intellij.psi.impl.JavaConstantExpressionEvaluator; +import com.intellij.psi.util.PropertyUtil; +import com.intellij.psi.util.PsiUtil; +import com.intellij.util.containers.ContainerUtil; +import org.jetbrains.annotations.NotNull; +import org.jetbrains.annotations.Nullable; + +import java.util.Map; +import java.util.regex.Pattern; + +/** + * @author peter + */ +public class DfaExpressionFactory { + private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.dataFlow.value.DfaExpressionFactory"); + private static final Condition<String> FALSE_GETTERS = parseFalseGetters(); + + private static Condition<String> parseFalseGetters() { + try { + final Pattern pattern = Pattern.compile(Registry.stringValue("ide.dfa.getters.with.side.effects")); + return new Condition<String>() { + @Override + public boolean value(String s) { + return pattern.matcher(s).matches(); + } + }; + } + catch (Exception e) { + LOG.error(e); + //noinspection unchecked + return Condition.FALSE; + } + } + + private final DfaValueFactory myFactory; + private Map<Integer, PsiVariable> myMockIndices = ContainerUtil.newHashMap(); + + public DfaExpressionFactory(DfaValueFactory factory) { + myFactory = factory; + } + + @Nullable + public DfaValue getExpressionDfaValue(@Nullable PsiExpression expression) { + if (expression == null) return null; + + if (expression instanceof PsiParenthesizedExpression) { + return getExpressionDfaValue(((PsiParenthesizedExpression)expression).getExpression()); + } + + if (expression instanceof PsiArrayAccessExpression) { + PsiExpression arrayExpression = ((PsiArrayAccessExpression)expression).getArrayExpression(); + DfaValue qualifier = getExpressionDfaValue(arrayExpression); + if (qualifier instanceof DfaVariableValue) { + PsiVariable indexVar = getArrayIndexVariable(((PsiArrayAccessExpression)expression).getIndexExpression()); + if (indexVar != null) { + return myFactory.getVarFactory().createVariableValue(indexVar, expression.getType(), false, (DfaVariableValue)qualifier); + } + } + return null; + } + + if (expression instanceof PsiMethodCallExpression) { + return createReferenceValue(((PsiMethodCallExpression)expression).getMethodExpression()); + } + + if (expression instanceof PsiReferenceExpression) { + return createReferenceValue((PsiReferenceExpression)expression); + } + + if (expression instanceof PsiLiteralExpression) { + return myFactory.createLiteralValue((PsiLiteralExpression)expression); + } + + if (expression instanceof PsiNewExpression) { + return myFactory.createTypeValue(expression.getType(), Nullness.NOT_NULL); + } + + final Object value = JavaConstantExpressionEvaluator.computeConstantExpression(expression, false); + PsiType type = expression.getType(); + if (value != null && type != null) { + if (value instanceof String) { + return myFactory.createTypeValue(type, Nullness.NOT_NULL); // Non-null string literal. + } + return myFactory.getConstFactory().createFromValue(value, type, null); + } + + return null; + } + + private DfaValue createReferenceValue(@NotNull PsiReferenceExpression refExpr) { + PsiModifierListOwner var = getAccessedVariableOrGetter(refExpr.resolve()); + if (var == null) { + return null; + } + + if (!var.hasModifierProperty(PsiModifier.VOLATILE) && !var.hasModifierProperty(PsiModifier.TRANSIENT)) { + if (var instanceof PsiVariable && var.hasModifierProperty(PsiModifier.FINAL)) { + DfaValue constValue = myFactory.getConstFactory().create((PsiVariable)var); + if (constValue != null) return constValue; + } + + if (DfaValueFactory.isEffectivelyUnqualified(refExpr)) { + return myFactory.getVarFactory().createVariableValue(var, refExpr.getType(), false, null); + } + + DfaValue qualifierValue = getExpressionDfaValue(refExpr.getQualifierExpression()); + if (qualifierValue instanceof DfaVariableValue) { + return myFactory.getVarFactory().createVariableValue(var, refExpr.getType(), false, (DfaVariableValue)qualifierValue); + } + } + + PsiType type = refExpr.getType(); + return myFactory.createTypeValue(type, DfaPsiUtil.getElementNullability(type, var)); + } + + @Nullable + private static PsiModifierListOwner getAccessedVariableOrGetter(final PsiElement target) { + if (target instanceof PsiVariable) { + return (PsiVariable)target; + } + if (target instanceof PsiMethod) { + if (PropertyUtil.isSimplePropertyGetter((PsiMethod)target)) { + String qName = PsiUtil.getMemberQualifiedName((PsiMethod)target); + if (qName == null || !FALSE_GETTERS.value(qName)) { + return (PsiMethod)target; + } + } + } + return null; + } + + @Nullable + private PsiVariable getArrayIndexVariable(@Nullable PsiExpression indexExpression) { + Object constant = JavaConstantExpressionEvaluator.computeConstantExpression(indexExpression, false); + if (constant instanceof Integer) { + PsiVariable mockVar = myMockIndices.get(constant); + if (mockVar == null) { + mockVar = JavaPsiFacade.getElementFactory(indexExpression.getProject()).createField("$array$index$" + constant, PsiType.INT); + myMockIndices.put((Integer)constant, mockVar); + } + return mockVar; + } + return null; + } + + +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaValueFactory.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaValueFactory.java index ba7772ba2ca2..da1d2d952634 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaValueFactory.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaValueFactory.java @@ -27,7 +27,6 @@ package com.intellij.codeInspection.dataFlow.value; import com.intellij.codeInspection.dataFlow.Nullness; import com.intellij.openapi.util.Pair; import com.intellij.psi.*; -import com.intellij.psi.impl.JavaConstantExpressionEvaluator; import com.intellij.psi.util.PsiTreeUtil; import com.intellij.psi.util.TypeConversionUtil; import com.intellij.util.containers.ContainerUtil; @@ -52,6 +51,7 @@ public class DfaValueFactory { myBoxedFactory = new DfaBoxedValue.Factory(this); myTypeFactory = new DfaTypeValue.Factory(this); myRelationFactory = new DfaRelationValue.Factory(this); + myExpressionFactory = new DfaExpressionFactory(this); } public boolean isHonorFieldInitializers() { @@ -83,28 +83,7 @@ public class DfaValueFactory { @Nullable public DfaValue createValue(PsiExpression psiExpression) { - if (psiExpression instanceof PsiReferenceExpression) { - return createReferenceValue((PsiReferenceExpression)psiExpression); - } - - if (psiExpression instanceof PsiLiteralExpression) { - return createLiteralValue((PsiLiteralExpression)psiExpression); - } - - if (psiExpression instanceof PsiNewExpression) { - return createTypeValue(psiExpression.getType(), Nullness.NOT_NULL); - } - - final Object value = JavaConstantExpressionEvaluator.computeConstantExpression(psiExpression, false); - PsiType type = psiExpression.getType(); - if (value != null && type != null) { - if (value instanceof String) { - return createTypeValue(type, Nullness.NOT_NULL); // Non-null string literal. - } - return getConstFactory().createFromValue(value, type, null); - } - - return null; + return myExpressionFactory.getExpressionDfaValue(psiExpression); } @Nullable @@ -116,26 +95,6 @@ public class DfaValueFactory { } @Nullable - public DfaValue createReferenceValue(PsiReferenceExpression referenceExpression) { - PsiElement psiSource = referenceExpression.resolve(); - if (!(psiSource instanceof PsiVariable)) { - return null; - } - - final PsiVariable variable = (PsiVariable)psiSource; - if (variable.hasModifierProperty(PsiModifier.FINAL) && !variable.hasModifierProperty(PsiModifier.TRANSIENT)) { - DfaValue constValue = getConstFactory().create(variable); - if (constValue != null) return constValue; - } - - if (!variable.hasModifierProperty(PsiModifier.VOLATILE) && isEffectivelyUnqualified(referenceExpression)) { - return getVarFactory().createVariableValue(variable, referenceExpression.getType(), false, null); - } - - return null; - } - - @Nullable public static PsiVariable resolveUnqualifiedVariable(PsiReferenceExpression refExpression) { if (isEffectivelyUnqualified(refExpression)) { PsiElement resolved = refExpression.resolve(); @@ -168,6 +127,7 @@ public class DfaValueFactory { private final DfaBoxedValue.Factory myBoxedFactory; private final DfaTypeValue.Factory myTypeFactory; private final DfaRelationValue.Factory myRelationFactory; + private final DfaExpressionFactory myExpressionFactory; @NotNull public DfaVariableValue.Factory getVarFactory() { diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaVariableValue.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaVariableValue.java index 31492bb38b9b..3030bef32934 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaVariableValue.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/value/DfaVariableValue.java @@ -105,7 +105,7 @@ public class DfaVariableValue extends DfaValue { return myTypeValue; } - @Nullable + @NotNull public PsiModifierListOwner getPsiVariable() { return myVariable; } diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/inheritance/search/InheritorsStatisticalDataSearch.java b/java/java-analysis-impl/src/com/intellij/codeInspection/inheritance/search/InheritorsStatisticalDataSearch.java index 8691d6b65f3e..4266b66cb6ed 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/inheritance/search/InheritorsStatisticalDataSearch.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/inheritance/search/InheritorsStatisticalDataSearch.java @@ -1,6 +1,21 @@ +/* + * 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.inheritance.search; -import com.intellij.openapi.util.Pair; +import com.intellij.openapi.util.Couple; import com.intellij.openapi.vfs.VirtualFile; import com.intellij.psi.PsiClass; import com.intellij.psi.search.GlobalSearchScope; @@ -32,7 +47,7 @@ public class InheritorsStatisticalDataSearch { disabledNames.add(aClassName); disabledNames.add(superClassName); final Set<InheritorsCountData> collector = new TreeSet<InheritorsCountData>(); - final Pair<Integer, Integer> collectingResult = collectInheritorsInfo(superClass, collector, disabledNames); + final Couple<Integer> collectingResult = collectInheritorsInfo(superClass, collector, disabledNames); final int allAnonymousInheritors = collectingResult.getSecond(); final int allInheritors = collectingResult.getFirst() + allAnonymousInheritors - 1; @@ -64,19 +79,19 @@ public class InheritorsStatisticalDataSearch { return result; } - private static Pair<Integer, Integer> collectInheritorsInfo(final PsiClass superClass, + private static Couple<Integer> collectInheritorsInfo(final PsiClass superClass, final Set<InheritorsCountData> collector, final Set<String> disabledNames) { return collectInheritorsInfo(superClass, collector, disabledNames, new HashSet<String>(), new HashSet<String>()); } - private static Pair<Integer, Integer> collectInheritorsInfo(final PsiClass aClass, + private static Couple<Integer> collectInheritorsInfo(final PsiClass aClass, final Set<InheritorsCountData> collector, final Set<String> disabledNames, final Set<String> processedElements, final Set<String> allNotAnonymousInheritors) { final String className = aClass.getName(); - if (!processedElements.add(className)) return Pair.create(0, 0); + if (!processedElements.add(className)) return Couple.of(0, 0); final MyInheritorsInfoProcessor processor = new MyInheritorsInfoProcessor(collector, disabledNames, processedElements); DirectClassInheritorsSearch.search(aClass).forEach(processor); @@ -87,7 +102,7 @@ public class InheritorsStatisticalDataSearch { if (!aClass.isInterface() && allInheritorsCount != 0 && !disabledNames.contains(className)) { collector.add(new InheritorsCountData(aClass, allInheritorsCount)); } - return Pair.create(allNotAnonymousInheritors.size(), processor.getAnonymousInheritorsCount()); + return Couple.of(allNotAnonymousInheritors.size(), processor.getAnonymousInheritorsCount()); } private static class MyInheritorsInfoProcessor implements Processor<PsiClass> { @@ -120,8 +135,11 @@ public class InheritorsStatisticalDataSearch { myAnonymousInheritorsCount++; } else { - final Pair<Integer, Integer> res = - collectInheritorsInfo(psiClass, myCollector, myDisabledNames, myProcessedElements, myAllNotAnonymousInheritors); + final Couple<Integer> res = collectInheritorsInfo(psiClass, + myCollector, + myDisabledNames, + myProcessedElements, + myAllNotAnonymousInheritors); myAnonymousInheritorsCount += res.getSecond(); if (!psiClass.isInterface()) { myAllNotAnonymousInheritors.add(inheritorName); diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/nullable/NullableStuffInspectionBase.java b/java/java-analysis-impl/src/com/intellij/codeInspection/nullable/NullableStuffInspectionBase.java index 38f8d46fe10c..47d32a03bf8f 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/nullable/NullableStuffInspectionBase.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/nullable/NullableStuffInspectionBase.java @@ -114,8 +114,8 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo ProblemHighlightType.GENERIC_ERROR_OR_WARNING, getterAnnoFix); } } - if (annotated.isDeclaredNotNull && manager.isNullable(getter, false) || - annotated.isDeclaredNullable && manager.isNotNull(getter, false)) { + if (annotated.isDeclaredNotNull && isNullableNotInferred(getter, false) || + annotated.isDeclaredNullable && isNotNullNotInferred(getter, false)) { holder.registerProblem(nameIdentifier, InspectionsBundle.message( "inspection.nullable.problems.annotated.field.getter.conflict", getPresentableAnnoName(field), getPresentableAnnoName(getter)), ProblemHighlightType.GENERIC_ERROR_OR_WARNING, getterAnnoFix); @@ -141,8 +141,8 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo addAnnoFix); } if (PropertyUtil.isSimpleSetter(setter)) { - if (annotated.isDeclaredNotNull && manager.isNullable(parameter, false) || - annotated.isDeclaredNullable && manager.isNotNull(parameter, false)) { + if (annotated.isDeclaredNotNull && isNullableNotInferred(parameter, false) || + annotated.isDeclaredNullable && isNotNullNotInferred(parameter, false)) { final PsiIdentifier nameIdentifier1 = parameter.getNameIdentifier(); assertValidElement(setter, parameter, nameIdentifier1); holder.registerProblem(nameIdentifier1, InspectionsBundle.message( @@ -154,7 +154,17 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo } } - for (PsiExpression rhs : DfaPsiUtil.findAllConstructorInitializers(field)) { + List<PsiExpression> initializers = DfaPsiUtil.findAllConstructorInitializers(field); + if (annotated.isDeclaredNotNull && initializers.isEmpty()) { + final PsiAnnotation annotation = AnnotationUtil.findAnnotation(field, manager.getNotNulls()); + if (annotation != null) { + holder.registerProblem(annotation.isPhysical() ? annotation : field.getNameIdentifier(), + "Not-null fields must be initialized", + ProblemHighlightType.GENERIC_ERROR_OR_WARNING); + } + } + + for (PsiExpression rhs : initializers) { if (rhs instanceof PsiReferenceExpression) { PsiElement target = ((PsiReferenceExpression)rhs).resolve(); if (target instanceof PsiParameter) { @@ -169,7 +179,7 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo ProblemHighlightType.GENERIC_ERROR_OR_WARNING, fix); continue; } - if (annotated.isDeclaredNullable && manager.isNotNull(parameter, false)) { + if (annotated.isDeclaredNullable && isNotNullNotInferred(parameter, false)) { boolean usedAsQualifier = !ReferencesSearch.search(parameter).forEach(new Processor<PsiReference>() { @Override public boolean process(PsiReference reference) { @@ -203,6 +213,33 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo if (!PsiUtil.isLanguageLevel5OrHigher(parameter)) return; check(parameter, holder, parameter.getType()); } + + @Override + public void visitAnnotation(PsiAnnotation annotation) { + if (!AnnotationUtil.NOT_NULL.equals(annotation.getQualifiedName())) return; + + PsiAnnotationMemberValue value = annotation.findDeclaredAttributeValue("exception"); + if (value instanceof PsiClassObjectAccessExpression) { + PsiClass psiClass = PsiUtil.resolveClassInClassTypeOnly(((PsiClassObjectAccessExpression)value).getOperand().getType()); + if (psiClass != null && !hasStringConstructor(psiClass)) { + holder.registerProblem(value, + "Custom exception class should have a constructor with a single message parameter of String type", + ProblemHighlightType.GENERIC_ERROR_OR_WARNING); + + } + } + } + + private boolean hasStringConstructor(PsiClass aClass) { + for (PsiMethod method : aClass.getConstructors()) { + PsiParameterList list = method.getParameterList(); + if (list.getParametersCount() == 1 && + list.getParameters()[0].getType().equalsToText(CommonClassNames.JAVA_LANG_STRING)) { + return true; + } + } + return false; + } }; } @@ -231,7 +268,7 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo PsiAnnotation isDeclaredNotNull = AnnotationUtil.findAnnotation(parameter, manager.getNotNulls()); PsiAnnotation isDeclaredNullable = AnnotationUtil.findAnnotation(parameter, manager.getNullables()); if (isDeclaredNullable != null && isDeclaredNotNull != null) { - reportNullableNotNullConflict(holder, parameter, isDeclaredNullable, isDeclaredNotNull); + reportNullableNotNullConflict(holder, parameter, isDeclaredNullable, isDeclaredNotNull); } if ((isDeclaredNotNull != null || isDeclaredNullable != null) && type != null && TypeConversionUtil.isPrimitive(type.getCanonicalText())) { PsiAnnotation annotation = isDeclaredNotNull == null ? isDeclaredNullable : isDeclaredNotNull; @@ -282,7 +319,7 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo if (!reported_nullable_method_overrides_notnull && REPORT_NOTNULL_PARAMETER_OVERRIDES_NULLABLE && annotated.isDeclaredNullable - && NullableNotNullManager.isNotNull(superMethod)) { + && isNotNullNotInferred(superMethod, true)) { reported_nullable_method_overrides_notnull = true; final PsiAnnotation annotation = AnnotationUtil.findAnnotation(method, nullableManager.getNullables(), true); holder.registerProblem(annotation != null ? annotation : method.getNameIdentifier(), @@ -293,7 +330,7 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo && REPORT_NOT_ANNOTATED_METHOD_OVERRIDES_NOTNULL && !annotated.isDeclaredNullable && !annotated.isDeclaredNotNull - && NullableNotNullManager.isNotNull(superMethod)) { + && isNotNullNotInferred(superMethod, true)) { reported_not_annotated_method_overrides_notnull = true; final String defaultNotNull = nullableManager.getDefaultNotNull(); final String[] annotationsToRemove = ArrayUtil.toStringArray(nullableManager.getNullables()); @@ -314,8 +351,8 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo PsiParameter parameter = parameters[i]; PsiParameter superParameter = superParameters[i]; if (!reported_notnull_parameter_overrides_nullable[i] && REPORT_NOTNULL_PARAMETER_OVERRIDES_NULLABLE && - nullableManager.isNotNull(parameter, false) && - nullableManager.isNullable(superParameter, false)) { + isNotNullNotInferred(parameter, false) && + isNullableNotInferred(superParameter, false)) { reported_notnull_parameter_overrides_nullable[i] = true; final PsiAnnotation annotation = AnnotationUtil.findAnnotation(parameter, nullableManager.getNotNulls(), true); holder.registerProblem(annotation != null ? annotation : parameter.getNameIdentifier(), @@ -325,7 +362,7 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo ProblemHighlightType.GENERIC_ERROR_OR_WARNING); } if (!reported_not_annotated_parameter_overrides_notnull[i] && REPORT_NOT_ANNOTATED_METHOD_OVERRIDES_NOTNULL) { - if (!nullableManager.hasNullability(parameter) && nullableManager.isNotNull(superParameter, false)) { + if (!nullableManager.hasNullability(parameter) && isNotNullNotInferred(superParameter, false)) { reported_not_annotated_parameter_overrides_notnull[i] = true; final LocalQuickFix fix = AnnotationUtil.isAnnotatingApplicable(parameter, nullableManager.getDefaultNotNull()) ? new AddNotNullAnnotationFix(parameter) @@ -346,7 +383,7 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo boolean hasAnnotatedParameter = false; for (int i = 0; i < parameters.length; i++) { PsiParameter parameter = parameters[i]; - parameterAnnotated[i] = nullableManager.isNotNull(parameter, false); + parameterAnnotated[i] = isNotNullNotInferred(parameter, false); hasAnnotatedParameter |= parameterAnnotated[i]; } if (hasAnnotatedParameter || annotated.isDeclaredNotNull) { @@ -362,8 +399,8 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo final boolean applicable = AnnotationUtil.isAnnotatingApplicable(overriding, defaultNotNull); if (!methodQuickFixSuggested && annotated.isDeclaredNotNull - && !nullableManager.isNotNull(overriding, false) - && (nullableManager.isNullable(overriding, false) || !nullableManager.isNullable(overriding, true))) { + && !isNotNullNotInferred(overriding, false) + && (isNullableNotInferred(overriding, false) || !isNullableNotInferred(overriding, true))) { method.getNameIdentifier(); //load tree PsiAnnotation annotation = AnnotationUtil.findAnnotation(method, nullableManager.getNotNulls()); final String[] annotationsToRemove = ArrayUtil.toStringArray(nullableManager.getNullables()); @@ -391,7 +428,7 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo for (int i = 0; i < psiParameters.length; i++) { if (parameterQuickFixSuggested[i]) continue; PsiParameter parameter = psiParameters[i]; - if (parameterAnnotated[i] && !nullableManager.isNotNull(parameter, false) && !nullableManager.isNullable(parameter, false)) { + if (parameterAnnotated[i] && !isNotNullNotInferred(parameter, false) && !isNullableNotInferred(parameter, false)) { parameters[i].getNameIdentifier(); //be sure that corresponding tree element available PsiAnnotation annotation = AnnotationUtil.findAnnotation(parameters[i], nullableManager.getNotNulls()); PsiElement psiElement = annotation; @@ -415,6 +452,24 @@ public class NullableStuffInspectionBase extends BaseJavaBatchLocalInspectionToo } } + private static boolean isNotNullNotInferred(@NotNull PsiModifierListOwner owner, boolean checkBases) { + Project project = owner.getProject(); + NullableNotNullManager manager = NullableNotNullManager.getInstance(project); + if (!manager.isNotNull(owner, checkBases)) return false; + + PsiAnnotation anno = manager.getNotNullAnnotation(owner, checkBases); + return !(anno != null && AnnotationUtil.isInferredAnnotation(anno)); + } + + private static boolean isNullableNotInferred(@NotNull PsiModifierListOwner owner, boolean checkBases) { + Project project = owner.getProject(); + NullableNotNullManager manager = NullableNotNullManager.getInstance(project); + if (!manager.isNullable(owner, checkBases)) return false; + + PsiAnnotation anno = manager.getNullableAnnotation(owner, checkBases); + return !(anno != null && AnnotationUtil.isInferredAnnotation(anno)); + } + @NotNull private static LocalQuickFix[] wrapFix(LocalQuickFix fix) { if (fix == null) return LocalQuickFix.EMPTY_ARRAY; diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/unusedLibraries/UnusedLibrariesInspection.java b/java/java-analysis-impl/src/com/intellij/codeInspection/unusedLibraries/UnusedLibrariesInspection.java index 5a419dfa9647..4db11dc0b0d0 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/unusedLibraries/UnusedLibrariesInspection.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/unusedLibraries/UnusedLibrariesInspection.java @@ -23,14 +23,15 @@ package com.intellij.codeInspection.unusedLibraries; import com.intellij.analysis.AnalysisScope; import com.intellij.codeInsight.daemon.GroupNames; import com.intellij.codeInspection.*; -import com.intellij.codeInspection.reference.*; +import com.intellij.codeInspection.reference.RefEntity; +import com.intellij.codeInspection.reference.RefGraphAnnotator; +import com.intellij.codeInspection.reference.RefManager; +import com.intellij.codeInspection.reference.RefModule; import com.intellij.openapi.application.ApplicationManager; import com.intellij.openapi.module.Module; import com.intellij.openapi.module.ModuleUtilCore; import com.intellij.openapi.project.Project; import com.intellij.openapi.roots.*; -import com.intellij.openapi.roots.impl.DirectoryIndex; -import com.intellij.openapi.roots.impl.DirectoryInfo; import com.intellij.openapi.roots.libraries.Library; import com.intellij.openapi.util.Comparing; import com.intellij.openapi.util.Key; @@ -185,12 +186,12 @@ public class UnusedLibrariesInspection extends GlobalInspectionTool { private static class UnusedLibraryGraphAnnotator extends RefGraphAnnotator { public static final Key<Set<VirtualFile>> USED_LIBRARY_ROOTS = Key.create("inspection.dependencies"); - private final DirectoryIndex myDirectoryIndex; + private final ProjectFileIndex myFileIndex; private RefManager myManager; public UnusedLibraryGraphAnnotator(RefManager manager) { myManager = manager; - myDirectoryIndex = DirectoryIndex.getInstance(manager.getProject()); + myFileIndex = ProjectRootManager.getInstance(manager.getProject()).getFileIndex(); } @Override @@ -199,8 +200,7 @@ public class UnusedLibrariesInspection extends GlobalInspectionTool { final VirtualFile virtualFile = PsiUtilCore.getVirtualFile(what); final VirtualFile containingDir = virtualFile != null ? virtualFile.getParent() : null; if (containingDir != null) { - final DirectoryInfo infoForDirectory = myDirectoryIndex.getInfoForDirectory(containingDir); - final VirtualFile libraryClassRoot = infoForDirectory != null ? infoForDirectory.getLibraryClassRoot() : null; + final VirtualFile libraryClassRoot = myFileIndex.getClassRootForFile(containingDir); if (libraryClassRoot != null) { final Module fromModule = ModuleUtilCore.findModuleForPsiElement(from); if (fromModule != null){ diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/varScopeCanBeNarrowed/FieldCanBeLocalInspectionBase.java b/java/java-analysis-impl/src/com/intellij/codeInspection/varScopeCanBeNarrowed/FieldCanBeLocalInspectionBase.java index f84abbb0e3d6..e13f3e66a198 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/varScopeCanBeNarrowed/FieldCanBeLocalInspectionBase.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/varScopeCanBeNarrowed/FieldCanBeLocalInspectionBase.java @@ -132,6 +132,7 @@ public class FieldCanBeLocalInspectionBase extends BaseJavaBatchLocalInspectionT final Set<PsiField> candidates, final Set<PsiField> usedFields, final boolean ignoreFieldsUsedInMultipleMethods) { + final Set<PsiField> ignored = new HashSet<PsiField>(); aClass.accept(new JavaRecursiveElementWalkingVisitor() { @Override public void visitElement(PsiElement element) { @@ -144,7 +145,7 @@ public class FieldCanBeLocalInspectionBase extends BaseJavaBatchLocalInspectionT final PsiCodeBlock body = method.getBody(); if (body != null) { - checkCodeBlock(body, candidates, usedFields, ignoreFieldsUsedInMultipleMethods); + checkCodeBlock(body, candidates, usedFields, ignoreFieldsUsedInMultipleMethods, ignored); } } @@ -153,14 +154,14 @@ public class FieldCanBeLocalInspectionBase extends BaseJavaBatchLocalInspectionT super.visitLambdaExpression(expression); final PsiElement body = expression.getBody(); if (body != null) { - checkCodeBlock(body, candidates, usedFields, ignoreFieldsUsedInMultipleMethods); + checkCodeBlock(body, candidates, usedFields, ignoreFieldsUsedInMultipleMethods, ignored); } } @Override public void visitClassInitializer(PsiClassInitializer initializer) { super.visitClassInitializer(initializer); - checkCodeBlock(initializer.getBody(), candidates, usedFields, ignoreFieldsUsedInMultipleMethods); + checkCodeBlock(initializer.getBody(), candidates, usedFields, ignoreFieldsUsedInMultipleMethods, ignored); } }); } @@ -168,20 +169,28 @@ public class FieldCanBeLocalInspectionBase extends BaseJavaBatchLocalInspectionT private static void checkCodeBlock(final PsiElement body, final Set<PsiField> candidates, Set<PsiField> usedFields, - boolean ignoreFieldsUsedInMultipleMethods) { + boolean ignoreFieldsUsedInMultipleMethods, + Set<PsiField> ignored) { try { + final Ref<Collection<PsiVariable>> writtenVariables = new Ref<Collection<PsiVariable>>(); final ControlFlow controlFlow = ControlFlowFactory.getInstance(body.getProject()).getControlFlow(body, AllVariablesControlFlowPolicy.getInstance()); final List<PsiVariable> usedVars = ControlFlowUtil.getUsedVariables(controlFlow, 0, controlFlow.getSize()); for (PsiVariable usedVariable : usedVars) { if (usedVariable instanceof PsiField) { final PsiField usedField = (PsiField)usedVariable; - if (!usedFields.add(usedField) && ignoreFieldsUsedInMultipleMethods) { + if (!getWrittenVariables(controlFlow, writtenVariables).contains(usedField)) { + ignored.add(usedField); + } + + if (!usedFields.add(usedField) && (ignoreFieldsUsedInMultipleMethods || ignored.contains(usedField))) { candidates.remove(usedField); //used in more than one code block } } } - final Ref<Collection<PsiVariable>> writtenVariables = new Ref<Collection<PsiVariable>>(); + + if (candidates.isEmpty()) return; + final List<PsiReferenceExpression> readBeforeWrites = ControlFlowUtil.getReadBeforeWrite(controlFlow); for (final PsiReferenceExpression readBeforeWrite : readBeforeWrites) { final PsiElement resolved = readBeforeWrite.resolve(); diff --git a/java/java-analysis-impl/src/com/intellij/refactoring/extractMethod/ExtractMethodUtil.java b/java/java-analysis-impl/src/com/intellij/refactoring/extractMethod/ExtractMethodUtil.java new file mode 100644 index 000000000000..82ed68a44228 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/refactoring/extractMethod/ExtractMethodUtil.java @@ -0,0 +1,147 @@ +/* + * Copyright 2000-2009 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.refactoring.extractMethod; + +import com.intellij.openapi.diagnostic.Logger; +import com.intellij.openapi.util.Key; +import com.intellij.psi.*; +import com.intellij.psi.search.SearchScope; +import com.intellij.psi.search.searches.ClassInheritorsSearch; +import com.intellij.psi.search.searches.ReferencesSearch; +import com.intellij.psi.util.PsiTreeUtil; +import com.intellij.psi.util.RedundantCastUtil; +import com.intellij.util.IncorrectOperationException; +import com.intellij.util.Processor; +import com.intellij.util.containers.HashMap; +import org.jetbrains.annotations.NotNull; + +import java.util.Map; + +/** + * @author ven + */ +public class ExtractMethodUtil { + private static final Key<PsiMethod> RESOLVE_TARGET_KEY = Key.create("RESOLVE_TARGET_KEY"); + private static final Logger LOG = Logger.getInstance("com.intellij.refactoring.extractMethod.ExtractMethodUtil"); + + private ExtractMethodUtil() { } + + static Map<PsiMethodCallExpression, PsiMethod> encodeOverloadTargets(final PsiClass targetClass, + final SearchScope processConflictsScope, + final String overloadName, + final PsiElement extractedFragment) { + final Map<PsiMethodCallExpression, PsiMethod> ret = new HashMap<PsiMethodCallExpression, PsiMethod>(); + encodeInClass(targetClass, overloadName, extractedFragment, ret); + + ClassInheritorsSearch.search(targetClass, processConflictsScope, true).forEach(new Processor<PsiClass>() { + public boolean process(PsiClass inheritor) { + encodeInClass(inheritor, overloadName, extractedFragment, ret); + return true; + } + }); + + return ret; + } + + private static void encodeInClass(final PsiClass aClass, + final String overloadName, + final PsiElement extractedFragment, + final Map<PsiMethodCallExpression, PsiMethod> ret) { + final PsiMethod[] overloads = aClass.findMethodsByName(overloadName, false); + for (final PsiMethod overload : overloads) { + for (final PsiReference ref : ReferencesSearch.search(overload)) { + final PsiElement element = ref.getElement(); + final PsiElement parent = element.getParent(); + if (parent instanceof PsiMethodCallExpression) { + final PsiMethodCallExpression call = (PsiMethodCallExpression)parent; + if (PsiTreeUtil.isAncestor(extractedFragment, element, false)) { + call.putCopyableUserData(RESOLVE_TARGET_KEY, overload); + } else { + //we assume element won't be invalidated as a result of extraction + ret.put(call, overload); + } + } + } + } + } + + public static void decodeOverloadTargets(Map<PsiMethodCallExpression, PsiMethod> oldResolves, final PsiMethod extracted, + final PsiElement oldFragment) { + final PsiCodeBlock body = extracted.getBody(); + assert body != null; + final JavaRecursiveElementVisitor visitor = new JavaRecursiveElementVisitor() { + + @Override public void visitMethodCallExpression(PsiMethodCallExpression expression) { + super.visitMethodCallExpression(expression); + final PsiMethod target = expression.getCopyableUserData(RESOLVE_TARGET_KEY); + if (target != null) { + expression.putCopyableUserData(RESOLVE_TARGET_KEY, null); + try { + addCastsToEnsureResolveTarget(target, expression); + } + catch (IncorrectOperationException e) { + LOG.error(e); + } + } + } + }; + body.accept(visitor); + oldFragment.accept(visitor); + + for (final Map.Entry<PsiMethodCallExpression, PsiMethod> entry : oldResolves.entrySet()) { + try { + addCastsToEnsureResolveTarget(entry.getValue(), entry.getKey()); + } + catch (IncorrectOperationException e) { + LOG.error(e); + } + } + } + + public static void addCastsToEnsureResolveTarget(@NotNull final PsiMethod oldTarget, @NotNull final PsiMethodCallExpression call) + throws IncorrectOperationException { + final PsiMethod newTarget = call.resolveMethod(); + final PsiManager manager = oldTarget.getManager(); + final PsiElementFactory factory = JavaPsiFacade.getInstance(manager.getProject()).getElementFactory(); + if (!manager.areElementsEquivalent(oldTarget, newTarget)) { + final PsiParameter[] oldParameters = oldTarget.getParameterList().getParameters(); + if (oldParameters.length > 0) { + final PsiMethodCallExpression copy = (PsiMethodCallExpression)call.copy(); + final PsiExpression[] args = copy.getArgumentList().getExpressions(); + for (int i = 0; i < args.length; i++) { + PsiExpression arg = args[i]; + PsiType paramType = i < oldParameters.length ? oldParameters[i].getType() : oldParameters[oldParameters.length - 1].getType(); + final PsiTypeCastExpression cast = (PsiTypeCastExpression)factory.createExpressionFromText("(a)b", null); + final PsiTypeElement typeElement = cast.getCastType(); + assert typeElement != null; + typeElement.replace(factory.createTypeElement(paramType)); + final PsiExpression operand = cast.getOperand(); + assert operand != null; + operand.replace(arg); + arg.replace(cast); + } + + for (int i = 0; i < copy.getArgumentList().getExpressions().length; i++) { + PsiExpression oldarg = call.getArgumentList().getExpressions()[i]; + PsiTypeCastExpression cast = (PsiTypeCastExpression)copy.getArgumentList().getExpressions()[i]; + if (!RedundantCastUtil.isCastRedundant(cast)) { + oldarg.replace(cast); + } + } + } + } + } +} |