diff options
Diffstat (limited to 'java/java-analysis-impl/src/com/intellij/codeInspection')
31 files changed, 4174 insertions, 2342 deletions
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 index 47ef448c7484..01993d5e9dd0 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Analysis.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Analysis.java @@ -15,7 +15,10 @@ */ package com.intellij.codeInspection.bytecodeAnalysis; -import gnu.trove.TIntObjectHashMap; +import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph; +import com.intellij.codeInspection.bytecodeAnalysis.asm.DFSTree; +import com.intellij.codeInspection.bytecodeAnalysis.asm.RichControlFlow; +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.MethodNode; @@ -71,6 +74,12 @@ class AbstractValues { } } + static final BasicValue CLASS_VALUE = new NotNullValue(Type.getObjectType("java/lang/Class")); + static final BasicValue METHOD_VALUE = new NotNullValue(Type.getObjectType("java/lang/invoke/MethodType")); + static final BasicValue STRING_VALUE = new NotNullValue(Type.getObjectType("java/lang/String")); + static final BasicValue METHOD_HANDLE_VALUE = new NotNullValue(Type.getObjectType("java/lang/invoke/MethodHandle")); + + static boolean isInstance(Conf curr, Conf prev) { if (curr.insnIndex != prev.insnIndex) { return false; @@ -187,50 +196,30 @@ final class State { } } -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> { + public static final int STEPS_LIMIT = 30000; public static final int EQUATION_SIZE_LIMIT = 30; + + protected static final ThreadLocal<State[]> ourPendingStates = new ThreadLocal<State[]>() { + @Override + protected State[] initialValue() { + return new State[STEPS_LIMIT]; + } + }; + 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 protected List<State>[] computed; final Key aKey; Res earlyResult = null; - abstract Res identity(); - abstract Res combineResults(Res delta, List<Res> subResults) throws AnalyzerException; - 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; @@ -239,7 +228,7 @@ abstract class Analysis<Res> { method = new Method(controlFlow.className, methodNode.name, methodNode.desc); dfsTree = richControlFlow.dfsTree; aKey = new Key(method, direction, stable); - myIdentity = identity(); + computed = (List<State>[]) new List[controlFlow.transitions.length]; } final State createStartState() { @@ -269,87 +258,8 @@ abstract class Analysis<Res> { 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)); - } - } + @NotNull + protected abstract Equation<Key, Value> analyze() throws AnalyzerException; final Frame<BasicValue> createStartFrame() { Frame<BasicValue> frame = new Frame<BasicValue>(methodNode.maxLocals, methodNode.maxStack); @@ -396,4 +306,13 @@ abstract class Analysis<Res> { result.add(x); return result; } + + protected void addComputed(int i, State s) { + List<State> states = computed[i]; + if (states == null) { + states = new ArrayList<State>(); + computed[i] = states; + } + states.add(s); + } } 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 index 0239a661c4ee..84a5851e847d 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisConverter.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisConverter.java @@ -15,271 +15,208 @@ */ package com.intellij.codeInspection.bytecodeAnalysis; -import com.intellij.openapi.application.ApplicationManager; -import com.intellij.openapi.components.ApplicationComponent; import com.intellij.openapi.progress.ProgressManager; import com.intellij.openapi.util.text.StringUtil; import com.intellij.psi.*; import com.intellij.psi.util.PsiTreeUtil; import com.intellij.psi.util.TypeConversionUtil; -import gnu.trove.TLongArrayList; -import gnu.trove.TLongHashSet; -import gnu.trove.TLongObjectHashMap; -import gnu.trove.TLongObjectIterator; import org.jetbrains.annotations.NotNull; -import org.jetbrains.org.objectweb.asm.Type; +import org.jetbrains.annotations.Nullable; -import java.io.IOException; -import java.util.ArrayList; -import java.util.Collections; -import java.util.List; -import java.util.Set; +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.util.*; import static com.intellij.codeInspection.bytecodeAnalysis.ProjectBytecodeAnalysis.LOG; /** * @author lambdamix */ -public abstract class BytecodeAnalysisConverter implements ApplicationComponent { +public class BytecodeAnalysisConverter { - public static final int SHIFT = 4096; + // how many bytes are taken from class fqn digest + public static final int CLASS_HASH_SIZE = 10; + // how many bytes are taken from signature digest + public static final int SIGNATURE_HASH_SIZE = 4; + public static final int HASH_SIZE = CLASS_HASH_SIZE + SIGNATURE_HASH_SIZE; - public static BytecodeAnalysisConverter getInstance() { - return ApplicationManager.getApplication().getComponent(BytecodeAnalysisConverter.class); + public static MessageDigest getMessageDigest() throws NoSuchAlgorithmException { + return MessageDigest.getInstance("MD5"); } + /** + * Converts an equation over asm keys into equation over small hash keys. + */ @NotNull - @Override - public String getComponentName() { - return "BytecodeAnalysisConverter"; - } - - public abstract int getVersion(); - - protected abstract int enumerateString(@NotNull String s) throws IOException; - - protected abstract int enumerateCompoundKey(@NotNull int[] key) throws IOException; - - IdEquation convert(Equation<Key, Value> equation) throws IOException { + static DirectionResultPair convert(@NotNull Equation<Key, Value> equation, @NotNull MessageDigest md) { ProgressManager.checkCanceled(); Result<Key, Value> rhs = equation.rhs; - IdResult result; + HResult result; if (rhs instanceof Final) { - result = new IdFinal(((Final<Key, Value>)rhs).value); + result = new HFinal(((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()]; + HComponent[] components = new HComponent[sumOrigin.size()]; int componentI = 0; for (Product<Key, Value> prod : sumOrigin) { - long[] intProd = new long[prod.ids.size()]; + HKey[] intProd = new HKey[prod.ids.size()]; int idI = 0; for (Key id : prod.ids) { - long rawId = mkAsmKey(id); - if (rawId <= 0) { - LOG.error("raw key should be positive. rawId = " + rawId); - } - intProd[idI] = id.stable ? rawId : -rawId; + intProd[idI] = asmKey(id, md); idI++; } - IntIdComponent intIdComponent = new IntIdComponent(prod.value, intProd); + HComponent intIdComponent = new HComponent(prod.value, intProd); components[componentI] = intIdComponent; componentI++; } - result = new IdPending(components); + result = new HPending(components); } - - long rawKey = mkAsmKey(equation.id); - if (rawKey <= 0) { - LOG.error("raw key should be positive. rawKey = " + rawKey); - } - - long key = equation.id.stable ? rawKey : -rawKey; - return new IdEquation(key, result); + return new DirectionResultPair(mkDirectionKey(equation.id.direction), result); } - public long mkAsmKey(@NotNull Key key) throws IOException { - long baseKey = mkAsmSignatureKey(key.method); - long directionKey = mkDirectionKey(key.direction); - return baseKey * SHIFT + directionKey; + /** + * Converts an asm method key to a small hash key (HKey) + */ + @NotNull + public static HKey asmKey(@NotNull Key key, @NotNull MessageDigest md) { + byte[] classDigest = md.digest(key.method.internalClassName.getBytes()); + md.update(key.method.methodName.getBytes()); + md.update(key.method.methodDesc.getBytes()); + byte[] sigDigest = md.digest(); + byte[] digest = new byte[HASH_SIZE]; + System.arraycopy(classDigest, 0, digest, 0, CLASS_HASH_SIZE); + System.arraycopy(sigDigest, 0, digest, CLASS_HASH_SIZE, SIGNATURE_HASH_SIZE); + return new HKey(digest, mkDirectionKey(key.direction), key.stable); } - private static int mkDirectionKey(Direction dir) throws IOException { - if (dir instanceof Out) { - return 0; - } else if (dir instanceof In) { - In in = (In)dir; - return 8 * in.paramId() + 1; - } else { - InOut inOut = (InOut)dir; - return 8 * inOut.paramId() + 2 + inOut.valueId(); + /** + * Converts a Psi method to a small hash key (HKey). + * Returns null if conversion is impossible (something is not resolvable). + */ + @Nullable + public static HKey psiKey(@NotNull PsiMethod psiMethod, @NotNull Direction direction, @NotNull MessageDigest md) { + final PsiClass psiClass = PsiTreeUtil.getParentOfType(psiMethod, PsiClass.class, false); + if (psiClass == null) { + return null; } - } - - @NotNull - private static Direction extractDirection(int directionKey) { - if (directionKey == 0) { - return new Out(); + byte[] classDigest = psiClassDigest(psiClass, md); + if (classDigest == null) { + return null; } - else { - int paramId = directionKey / 8; - int subDirection = directionKey % 8; - if (subDirection == 1) { - return new In(paramId); - } - else { - return new InOut(paramId, Value.values()[subDirection - 2]); - } + byte[] sigDigest = methodDigest(psiMethod, md); + if (sigDigest == null) { + return null; } + byte[] digest = new byte[HASH_SIZE]; + System.arraycopy(classDigest, 0, digest, 0, CLASS_HASH_SIZE); + System.arraycopy(sigDigest, 0, digest, CLASS_HASH_SIZE, SIGNATURE_HASH_SIZE); + return new HKey(digest, mkDirectionKey(direction), true); } - // 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 enumerateCompoundKey(sigKey); - } - - private int mkAsmShortSignatureKey(@NotNull Method method) throws IOException { - Type[] argTypes = Type.getArgumentTypes(method.methodDesc); - int arity = argTypes.length; - int[] sigKey = new int[2 + arity]; - sigKey[0] = mkAsmTypeKey(Type.getReturnType(method.methodDesc)); - sigKey[1] = enumerateString(method.methodName); - for (int i = 0; i < argTypes.length; i++) { - sigKey[2 + i] = mkAsmTypeKey(argTypes[i]); + @Nullable + private static byte[] psiClassDigest(@NotNull PsiClass psiClass, @NotNull MessageDigest md) { + String descriptor = descriptor(psiClass, 0, false); + if (descriptor == null) { + return null; } - return enumerateCompoundKey(sigKey); + return md.digest(descriptor.getBytes()); } - 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; + @Nullable + private static byte[] methodDigest(@NotNull PsiMethod psiMethod, @NotNull MessageDigest md) { + String descriptor = descriptor(psiMethod); + if (descriptor == null) { + return null; } - int[] classKey = new int[]{enumerateString(packageName), enumerateString(simpleName)}; - return enumerateCompoundKey(classKey); + return md.digest(descriptor.getBytes()); } - public long 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; - } - long sigKey = mkPsiSignatureKey(psiMethod); - if (sigKey == -1) { - return -1; - } - long directionKey = mkDirectionKey(direction); - return sigKey * SHIFT + directionKey; - } - - private int mkPsiSignatureKey(@NotNull PsiMethod psiMethod) throws IOException { + @Nullable + private static String descriptor(@NotNull PsiMethod psiMethod) { + StringBuilder sb = new StringBuilder(); final PsiClass psiClass = PsiTreeUtil.getParentOfType(psiMethod, PsiClass.class, false); if (psiClass == null) { - LOG.debug("PsiClass was null for " + psiMethod.getName()); - return -1; + return null; } 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[2 + arity]; - if (returnType == null) { - shortSigKey[0] = mkPsiTypeKey(PsiType.VOID); - shortSigKey[1] = enumerateString("<init>"); - } else { - shortSigKey[0] = mkPsiTypeKey(returnType); - shortSigKey[1] = enumerateString(psiMethod.getName()); - } + sb.append(returnType == null ? "<init>" : psiMethod.getName()); + sb.append('('); + + String desc; + if (isInnerClassConstructor) { - shortSigKey[2] = mkPsiClassKey(outerClass, 0); - } - for (int i = 0; i < parameters.length; i++) { - PsiParameter parameter = parameters[i]; - shortSigKey[2 + i + shift] = mkPsiTypeKey(parameter.getType()); - } - for (int aShortSigKey : shortSigKey) { - if (aShortSigKey == -1) { - return -1; + desc = descriptor(outerClass, 0, true); + if (desc == null) { + return null; } + sb.append(desc); } - - int[] sigKey = new int[2]; - int classKey = mkPsiClassKey(psiClass, 0); - if (classKey == -1) { - return -1; + for (PsiParameter parameter : parameters) { + desc = descriptor(parameter.getType()); + if (desc == null) { + return null; + } + sb.append(desc); } - sigKey[0] = classKey; - sigKey[1] = enumerateCompoundKey(shortSigKey); - - return enumerateCompoundKey(sigKey); - } - - public TLongArrayList mkInOutKeys(@NotNull PsiMethod psiMethod, long primaryKey) throws IOException { - PsiParameter[] parameters = psiMethod.getParameterList().getParameters(); - TLongArrayList keys = new TLongArrayList(parameters.length * 2 + 1); - for (int i = 0; i < parameters.length; i++) { - PsiParameter parameter = parameters[i]; - PsiType parameterType = parameter.getType(); - if (parameterType instanceof PsiPrimitiveType) { - if (PsiType.BOOLEAN.equals(parameterType)) { - keys.add(primaryKey + mkDirectionKey(new InOut(i, Value.False))); - keys.add(primaryKey + mkDirectionKey(new InOut(i, Value.True))); - } + sb.append(')'); + if (returnType == null) { + sb.append('V'); + } else { + desc = descriptor(returnType); + if (desc == null) { + return null; } else { - keys.add(primaryKey + mkDirectionKey(new InOut(i, Value.NotNull))); - keys.add(primaryKey + mkDirectionKey(new InOut(i, Value.Null))); + sb.append(desc); } } - return keys; + return sb.toString(); } - - private int mkPsiClassKey(PsiClass psiClass, int dimensions) throws IOException { + @Nullable + private static String descriptor(@NotNull PsiClass psiClass, int dimensions, boolean full) { PsiFile containingFile = psiClass.getContainingFile(); if (!(containingFile instanceof PsiClassOwner)) { LOG.debug("containingFile was not resolved for " + psiClass.getQualifiedName()); - return -1; + return null; } PsiClassOwner psiFile = (PsiClassOwner)containingFile; String packageName = psiFile.getPackageName(); String qname = psiClass.getQualifiedName(); if (qname == null) { - return -1; + return null; } - String className = qname; + String className; if (packageName.length() > 0) { className = qname.substring(packageName.length() + 1).replace('.', '$'); - } - int[] classKey = new int[2]; - classKey[0] = enumerateString(packageName); - if (dimensions == 0) { - classKey[1] = enumerateString(className); } else { - StringBuilder sb = new StringBuilder(className); - for (int j = 0; j < dimensions; j++) { - sb.append("[]"); - } - classKey[1] = enumerateString(sb.toString()); + className = qname.replace('.', '$'); + } + StringBuilder sb = new StringBuilder(); + for (int i = 0; i < dimensions; i++) { + sb.append('['); + } + if (full) { + sb.append('L'); } - return enumerateCompoundKey(classKey); + if (packageName.length() > 0) { + sb.append(packageName.replace('.', '/')); + sb.append('/'); + } + sb.append(className); + if (full) { + sb.append(';'); + } + return sb.toString(); } - private int mkPsiTypeKey(PsiType psiType) throws IOException { + @Nullable + private static String descriptor(@NotNull PsiType psiType) { int dimensions = 0; psiType = TypeConversionUtil.erasure(psiType); if (psiType instanceof PsiArrayType) { @@ -289,56 +226,130 @@ public abstract class BytecodeAnalysisConverter implements ApplicationComponent } if (psiType instanceof PsiClassType) { - // no resolve() -> no package/class split PsiClass psiClass = ((PsiClassType)psiType).resolve(); if (psiClass != null) { - return mkPsiClassKey(psiClass, dimensions); + return descriptor(psiClass, dimensions, true); } else { LOG.debug("resolve was null for " + ((PsiClassType)psiType).getClassName()); - return -1; + return null; } } else if (psiType instanceof PsiPrimitiveType) { - String packageName = ""; - String className = psiType.getPresentableText(); - int[] classKey = new int[2]; - classKey[0] = enumerateString(packageName); - if (dimensions == 0) { - classKey[1] = enumerateString(className); - } else { - StringBuilder sb = new StringBuilder(className); - for (int j = 0; j < dimensions; j++) { - sb.append("[]"); - } - classKey[1] = enumerateString(sb.toString()); + StringBuilder sb = new StringBuilder(); + for (int i = 0; i < dimensions; i++) { + sb.append('['); + } + if (PsiType.VOID.equals(psiType)) { + sb.append('V'); + } + else if (PsiType.BOOLEAN.equals(psiType)) { + sb.append('Z'); + } + else if (PsiType.CHAR.equals(psiType)) { + sb.append('C'); + } + else if (PsiType.BYTE.equals(psiType)) { + sb.append('B'); + } + else if (PsiType.SHORT.equals(psiType)) { + sb.append('S'); + } + else if (PsiType.INT.equals(psiType)) { + sb.append('I'); } - return enumerateCompoundKey(classKey); + else if (PsiType.FLOAT.equals(psiType)) { + sb.append('F'); + } + else if (PsiType.LONG.equals(psiType)) { + sb.append('J'); + } + else if (PsiType.DOUBLE.equals(psiType)) { + sb.append('D'); + } + return sb.toString(); } - return -1; + return null; } - public void addMethodAnnotations(TLongObjectHashMap<Value> internalIdSolutions, Annotations annotations, long methodKey, int arity) { + private static int mkDirectionKey(Direction dir) { + if (dir instanceof Out) { + return 0; + } else if (dir instanceof In) { + In in = (In)dir; + // nullity mask is 0/1 + return 8 * in.paramId() + 1 + in.nullityMask; + } else { + InOut inOut = (InOut)dir; + return 8 * inOut.paramId() + 3 + inOut.valueId(); + } + } - List<String> clauses = new ArrayList<String>(); - TLongObjectIterator<Value> solutionsIterator = internalIdSolutions.iterator(); + @NotNull + private static Direction extractDirection(int directionKey) { + if (directionKey == 0) { + return new Out(); + } + else { + int paramId = directionKey / 8; + int subDirection = directionKey % 8; + if (subDirection <= 2) { + return new In(paramId, subDirection - 1); + } + else { + return new InOut(paramId, Value.values()[subDirection - 3]); + } + } + } + + /** + * Given a PSI method and its primary HKey enumerate all contract keys for it. + */ + @NotNull + public static ArrayList<HKey> mkInOutKeys(@NotNull PsiMethod psiMethod, @NotNull HKey primaryKey) { + PsiParameter[] parameters = psiMethod.getParameterList().getParameters(); + ArrayList<HKey> keys = new ArrayList<HKey>(parameters.length * 2 + 1); + for (int i = 0; i < parameters.length; i++) { + PsiParameter parameter = parameters[i]; + PsiType parameterType = parameter.getType(); + if (parameterType instanceof PsiPrimitiveType) { + if (PsiType.BOOLEAN.equals(parameterType)) { + keys.add(primaryKey.updateDirection(mkDirectionKey(new InOut(i, Value.False)))); + keys.add(primaryKey.updateDirection(mkDirectionKey(new InOut(i, Value.True)))); + } + } else { + keys.add(primaryKey.updateDirection(mkDirectionKey(new InOut(i, Value.NotNull)))); + keys.add(primaryKey.updateDirection(mkDirectionKey(new InOut(i, Value.Null)))); + } + } + return keys; + } - TLongHashSet notNulls = annotations.notNulls; - TLongObjectHashMap<String> contracts = annotations.contracts; - for (int i = internalIdSolutions.size(); i-- > 0;) { - solutionsIterator.advance(); - long key = Math.abs(solutionsIterator.key()); - Value value = solutionsIterator.value(); + /** + * Given `solution` of all dependencies of a method with the `methodKey`, converts this solution into annotations. + * + * @param solution solution of equations + * @param methodAnnotations annotations to which corresponding solutions should be added + * @param methodKey a primary key of a method being analyzed + * @param arity arity of this method (hint for constructing @Contract annotations) + */ + public static void addMethodAnnotations(@NotNull HashMap<HKey, Value> solution, @NotNull MethodAnnotations methodAnnotations, @NotNull HKey methodKey, int arity) { + List<String> clauses = new ArrayList<String>(); + HashSet<HKey> notNulls = methodAnnotations.notNulls; + HashMap<HKey, String> contracts = methodAnnotations.contracts; + for (Map.Entry<HKey, Value> entry : solution.entrySet()) { + HKey key = entry.getKey().mkStable(); + Value value = entry.getValue(); if (value == Value.Top || value == Value.Bot) { continue; } - Direction direction = extractDirection((int)(key % SHIFT)); - if (value == Value.NotNull && direction instanceof Out && key == methodKey) { + Direction direction = extractDirection(key.dirKey); + if (value == Value.NotNull && direction instanceof Out && methodKey.equals(key)) { notNulls.add(key); } else if (direction instanceof InOut) { - long baseKey = key - (key % SHIFT); - if (baseKey == methodKey) { + HKey baseKey = key.mkBase(); + if (methodKey.equals(baseKey)) { clauses.add(contractElement(arity, (InOut)direction, value)); } } @@ -353,24 +364,7 @@ public abstract class BytecodeAnalysisConverter implements ApplicationComponent } } - public void addParameterAnnotations(TLongObjectHashMap<Value> internalIdSolutions, Annotations annotations) { - TLongObjectIterator<Value> solutionsIterator = internalIdSolutions.iterator(); - TLongHashSet notNulls = annotations.notNulls; - for (int i = internalIdSolutions.size(); i-- > 0;) { - solutionsIterator.advance(); - long key = Math.abs(solutionsIterator.key()); - Value value = solutionsIterator.value(); - if (value == Value.Top || value == Value.Bot) { - continue; - } - Direction direction = extractDirection((int)(key % SHIFT)); - if (value == Value.NotNull && (direction instanceof In || direction instanceof Out)) { - notNulls.add(key); - } - } - } - - static String contractValueString(Value v) { + private static String contractValueString(@NotNull Value v) { switch (v) { case False: return "false"; case True: return "true"; @@ -380,7 +374,7 @@ public abstract class BytecodeAnalysisConverter implements ApplicationComponent } } - static String contractElement(int arity, InOut inOut, Value value) { + private static String contractElement(int arity, InOut inOut, Value value) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < arity; i++) { Value currentValue = Value.Top; diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisConverterImpl.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisConverterImpl.java deleted file mode 100644 index 067cc743679e..000000000000 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisConverterImpl.java +++ /dev/null @@ -1,206 +0,0 @@ -/* - * 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.util.ThrowableComputable; -import com.intellij.openapi.util.io.FileUtil; -import com.intellij.util.io.*; -import org.jetbrains.annotations.NotNull; -import org.jetbrains.annotations.Nullable; - -import java.io.*; -import java.io.DataOutputStream; -import java.util.Arrays; - -import static com.intellij.codeInspection.bytecodeAnalysis.ProjectBytecodeAnalysis.LOG; - -/** - * @author lambdamix - */ -public class BytecodeAnalysisConverterImpl extends BytecodeAnalysisConverter { - private static final int LOGIC_VERSION = 1; - private static final String ENUMERATORS_VERSION_KEY = "BytecodeAnalysisConverter.Enumerators"; - - private File myVersionFile; - private PersistentStringEnumerator myNamesEnumerator; - private PersistentEnumeratorDelegate<int[]> myCompoundKeyEnumerator; - private int version; - - @Override - public void initComponent() { - - // suffix as an indicator of version - final File keysDir = new File(PathManager.getIndexRoot(), "bytecodekeys"); - final File namesFile = new File(keysDir, "names" + LOGIC_VERSION); - final File compoundKeysFile = new File(keysDir, "compound" + LOGIC_VERSION); - myVersionFile = new File(keysDir, "version" + LOGIC_VERSION); - - version = PropertiesComponent.getInstance().getOrInitInt(ENUMERATORS_VERSION_KEY, 0); - if (ApplicationManager.getApplication().isUnitTestMode()) { - version = _readVersion(); - } - - if (!namesFile.exists() || !compoundKeysFile.exists() || !myVersionFile.exists()) { - LOG.info("No enumerators detected, re-initialization of enumerators."); - IOUtil.deleteAllFilesStartingWith(keysDir); - version++; - } - - 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); - } - PropertiesComponent.getInstance().setValue(ENUMERATORS_VERSION_KEY, String.valueOf(version)); - _saveVersion(); - } - - @Override - public void disposeComponent() { - try { - myNamesEnumerator.close(); - myCompoundKeyEnumerator.close(); - } - catch (IOException e) { - LOG.debug(e); - } - } - - public int _readVersion() { - try { - final DataInputStream is = new DataInputStream(new FileInputStream(myVersionFile)); - try { - return is.readInt(); - } - finally { - is.close(); - } - } - catch (FileNotFoundException ignored) { - } - catch (IOException ignored) { - } - return 0; - } - - private void _saveVersion() { - try { - FileUtil.createIfDoesntExist(myVersionFile); - final DataOutputStream os = new DataOutputStream(new FileOutputStream(myVersionFile)); - try { - os.writeInt(version); - } - finally { - os.close(); - } - } - catch (IOException ignored) { - } - } - - public int getVersion() { - return version; - } - - @Override - protected int enumerateString(@NotNull String s) throws IOException { - return myNamesEnumerator.enumerate(s); - } - - @Override - protected int enumerateCompoundKey(@NotNull int[] key) throws IOException { - return myCompoundKeyEnumerator.enumerate(key); - } - - private static class IntArrayKeyDescriptor implements KeyDescriptor<int[]>, DifferentSerializableBytesImplyNonEqualityPolicy { - - @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 index 297b2b694c62..a7070b882431 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisIndex.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/BytecodeAnalysisIndex.java @@ -16,8 +16,6 @@ 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.util.SystemProperties; import com.intellij.util.indexing.*; @@ -30,46 +28,42 @@ import org.jetbrains.annotations.NotNull; import java.io.DataInput; import java.io.DataOutput; import java.io.IOException; +import java.util.ArrayList; +import java.util.Arrays; /** * @author lambdamix */ -public class BytecodeAnalysisIndex extends FileBasedIndexExtension<Long, IdEquation> { - public static final ID<Long, IdEquation> NAME = ID.create("bytecodeAnalysis"); - private final EquationExternalizer myExternalizer = new EquationExternalizer(); - private static final DataIndexer<Long, IdEquation, FileContent> INDEXER = - new ClassDataIndexer(BytecodeAnalysisConverter.getInstance()); - private static final SmartLongKeyDescriptor KEY_DESCRIPTOR = new SmartLongKeyDescriptor(); - - private static final int ourInternalVersion = 3; - 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 class BytecodeAnalysisIndex extends FileBasedIndexExtension<Bytes, HEquations> { + public static final ID<Bytes, HEquations> NAME = ID.create("bytecodeAnalysis"); + private final HEquationsExternalizer myExternalizer = new HEquationsExternalizer(); + private static final ClassDataIndexer INDEXER = new ClassDataIndexer(); + private static final HKeyDescriptor KEY_DESCRIPTOR = new HKeyDescriptor(); + + private static final int ourInternalVersion = 1; + private static boolean ourEnabled = SystemProperties.getBooleanProperty("idea.enable.bytecode.contract.inference", true); @NotNull @Override - public ID<Long, IdEquation> getName() { + public ID<Bytes, HEquations> getName() { return NAME; } @NotNull @Override - public DataIndexer<Long, IdEquation, FileContent> getIndexer() { + public DataIndexer<Bytes, HEquations, FileContent> getIndexer() { return INDEXER; } @NotNull @Override - public KeyDescriptor<Long> getKeyDescriptor() { + public KeyDescriptor<Bytes> getKeyDescriptor() { return KEY_DESCRIPTOR; } @NotNull @Override - public DataExternalizer<IdEquation> getValueExternalizer() { + public DataExternalizer<HEquations> getValueExternalizer() { return myExternalizer; } @@ -91,111 +85,103 @@ public class BytecodeAnalysisIndex extends FileBasedIndexExtension<Long, IdEquat @Override public int getVersion() { - return ourInternalVersion + BytecodeAnalysisConverter.getInstance().getVersion() + (ourEnabled ? 0xFF : 0); + return ourInternalVersion + (ourEnabled ? 0xFF : 0); } - public static class EquationExternalizer implements DataExternalizer<IdEquation>, DifferentSerializableBytesImplyNonEqualityPolicy { + private static class HKeyDescriptor implements KeyDescriptor<Bytes>, DifferentSerializableBytesImplyNonEqualityPolicy { + @Override - public void save(@NotNull DataOutput out, IdEquation equation) throws IOException { - long id = equation.id; - int sign = id > 0 ? 1 : -1; - id = Math.abs(id); - int primaryId = (int)(id / BytecodeAnalysisConverter.SHIFT); - int secondaryId = (int)(id % BytecodeAnalysisConverter.SHIFT); - out.writeInt(sign * primaryId); - DataInputOutputUtil.writeINT(out, secondaryId); - IdResult rhs = equation.rhs; - if (rhs instanceof IdFinal) { - IdFinal finalResult = (IdFinal)rhs; - out.writeBoolean(true); // final flag - DataInputOutputUtil.writeINT(out, finalResult.value.ordinal()); - } else { - IdPending pendResult = (IdPending)rhs; - out.writeBoolean(false); // pending flag - DataInputOutputUtil.writeINT(out, pendResult.delta.length); - - for (IntIdComponent component : pendResult.delta) { - DataInputOutputUtil.writeINT(out, component.value.ordinal()); - long[] ids = component.ids; - DataInputOutputUtil.writeINT(out, ids.length); - for (long id1 : ids) { - sign = id1 > 0 ? 1 : -1; - id = Math.abs(id1); - primaryId = (int)(id / BytecodeAnalysisConverter.SHIFT); - secondaryId = (int)(id % BytecodeAnalysisConverter.SHIFT); - out.writeInt(sign * primaryId); - DataInputOutputUtil.writeINT(out, secondaryId); - } - } - } + public void save(@NotNull DataOutput out, Bytes value) throws IOException { + out.write(value.bytes); } @Override - public IdEquation read(@NotNull DataInput in) throws IOException { - long primaryId = in.readInt(); - int sign = primaryId > 0 ? 1 : -1; - primaryId = Math.abs(primaryId); - int secondaryId = DataInputOutputUtil.readINT(in); - long equationId = sign * (primaryId * BytecodeAnalysisConverter.SHIFT + secondaryId); - boolean isFinal = in.readBoolean(); // flag - if (isFinal) { - int ordinal = DataInputOutputUtil.readINT(in); - Value value = Value.values()[ordinal]; - return new IdEquation(equationId, new IdFinal(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); - long[] ids = new long[componentSize]; - for (int j = 0; j < componentSize; j++) { - primaryId = in.readInt(); - sign = primaryId > 0 ? 1 : -1; - primaryId = Math.abs(primaryId); - secondaryId = DataInputOutputUtil.readINT(in); - long id = sign * (primaryId * BytecodeAnalysisConverter.SHIFT + secondaryId); - ids[j] = id; - } - components[i] = new IntIdComponent(value, ids); - } - return new IdEquation(equationId, new IdPending(components)); + public Bytes read(@NotNull DataInput in) throws IOException { + byte[] bytes = new byte[BytecodeAnalysisConverter.HASH_SIZE]; + for (int i = 0; i < bytes.length; i++) { + bytes[i] = in.readByte(); } + return new Bytes(bytes); } - } - private static class SmartLongKeyDescriptor implements KeyDescriptor<Long>, DifferentSerializableBytesImplyNonEqualityPolicy { @Override - public void save(@NotNull DataOutput out, Long value) throws IOException { - long id = value.longValue(); - int sign = id > 0 ? 1 : -1; - id = Math.abs(id); - int primaryId = (int)(id / BytecodeAnalysisConverter.SHIFT); - int secondaryId = (int)(id % BytecodeAnalysisConverter.SHIFT); - out.writeInt(primaryId * sign); - DataInputOutputUtil.writeINT(out, secondaryId); + public int getHashCode(Bytes value) { + return Arrays.hashCode(value.bytes); } @Override - public Long read(@NotNull DataInput in) throws IOException { - long primaryId = in.readInt(); - int sign = primaryId > 0 ? 1 : -1; - primaryId = Math.abs(primaryId); - int secondaryId = DataInputOutputUtil.readINT(in); - return sign * (primaryId * BytecodeAnalysisConverter.SHIFT + secondaryId); + public boolean isEqual(Bytes val1, Bytes val2) { + return Arrays.equals(val1.bytes, val2.bytes); } + } + public static class HEquationsExternalizer implements DataExternalizer<HEquations>, DifferentSerializableBytesImplyNonEqualityPolicy { @Override - public int getHashCode(Long value) { - return value.hashCode(); + public void save(@NotNull DataOutput out, HEquations eqs) throws IOException { + out.writeBoolean(eqs.stable); + DataInputOutputUtil.writeINT(out, eqs.results.size()); + for (DirectionResultPair pair : eqs.results) { + DataInputOutputUtil.writeINT(out, pair.directionKey); + HResult rhs = pair.hResult; + if (rhs instanceof HFinal) { + HFinal finalResult = (HFinal)rhs; + out.writeBoolean(true); // final flag + DataInputOutputUtil.writeINT(out, finalResult.value.ordinal()); + } + else { + HPending pendResult = (HPending)rhs; + out.writeBoolean(false); // pending flag + DataInputOutputUtil.writeINT(out, pendResult.delta.length); + + for (HComponent component : pendResult.delta) { + DataInputOutputUtil.writeINT(out, component.value.ordinal()); + HKey[] ids = component.ids; + DataInputOutputUtil.writeINT(out, ids.length); + for (HKey hKey : ids) { + out.write(hKey.key); + DataInputOutputUtil.writeINT(out, hKey.dirKey); + out.writeBoolean(hKey.stable); + } + } + } + } } @Override - public boolean isEqual(Long val1, Long val2) { - return val1.longValue() == val2.longValue(); + public HEquations read(@NotNull DataInput in) throws IOException { + boolean stable = in.readBoolean(); + int size = DataInputOutputUtil.readINT(in); + ArrayList<DirectionResultPair> results = new ArrayList<DirectionResultPair>(size); + for (int k = 0; k < size; k++) { + int directionKey = DataInputOutputUtil.readINT(in); + boolean isFinal = in.readBoolean(); // flag + if (isFinal) { + int ordinal = DataInputOutputUtil.readINT(in); + Value value = Value.values()[ordinal]; + results.add(new DirectionResultPair(directionKey, new HFinal(value))); + } + else { + int sumLength = DataInputOutputUtil.readINT(in); + HComponent[] components = new HComponent[sumLength]; + + for (int i = 0; i < sumLength; i++) { + int ordinal = DataInputOutputUtil.readINT(in); + Value value = Value.values()[ordinal]; + int componentSize = DataInputOutputUtil.readINT(in); + HKey[] ids = new HKey[componentSize]; + for (int j = 0; j < componentSize; j++) { + byte[] bytes = new byte[BytecodeAnalysisConverter.HASH_SIZE]; + for (int bi = 0; bi < bytes.length; bi++) { + bytes[bi] = in.readByte(); + } + ids[j] = new HKey(bytes, DataInputOutputUtil.readINT(in), in.readBoolean()); + } + components[i] = new HComponent(value, ids); + } + results.add(new DirectionResultPair(directionKey, new HPending(components))); + } + } + return new HEquations(results, stable); } } } 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 index 9e656b98a7fb..316307896467 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ClassDataIndexer.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ClassDataIndexer.java @@ -15,17 +15,20 @@ */ package com.intellij.codeInspection.bytecodeAnalysis; +import com.intellij.codeInspection.bytecodeAnalysis.asm.*; import com.intellij.openapi.progress.ProcessCanceledException; import com.intellij.openapi.progress.ProgressManager; import com.intellij.openapi.util.NotNullLazyValue; +import com.intellij.openapi.util.NullableLazyValue; +import com.intellij.openapi.util.Pair; 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.security.MessageDigest; import java.util.*; import static com.intellij.codeInspection.bytecodeAnalysis.ProjectBytecodeAnalysis.LOG; @@ -33,29 +36,32 @@ import static com.intellij.codeInspection.bytecodeAnalysis.ProjectBytecodeAnalys /** * @author lambdamix */ -public class ClassDataIndexer implements DataIndexer<Long, IdEquation, FileContent> { - final BytecodeAnalysisConverter myConverter; +public class ClassDataIndexer implements DataIndexer<Bytes, HEquations, FileContent> { - public ClassDataIndexer(BytecodeAnalysisConverter converter) { - myConverter = converter; - } + private static final int STABLE_FLAGS = Opcodes.ACC_FINAL | Opcodes.ACC_PRIVATE | Opcodes.ACC_STATIC; + public static final Final<Key, Value> FINAL_TOP = new Final<Key, Value>(Value.Top); + public static final Final<Key, Value> FINAL_BOT = new Final<Key, Value>(Value.Bot); + public static final Final<Key, Value> FINAL_NOT_NULL = new Final<Key, Value>(Value.NotNull); + public static final Final<Key, Value> FINAL_NULL = new Final<Key, Value>(Value.Null); + private static final List<Equation<Key, Value>> EMPTY_EQUATIONS = Collections.EMPTY_LIST; @NotNull @Override - public Map<Long, IdEquation> map(@NotNull FileContent inputData) { - HashMap<Long, IdEquation> map = new HashMap<Long, IdEquation>(); + public Map<Bytes, HEquations> map(@NotNull FileContent inputData) { + HashMap<Bytes, HEquations> map = new HashMap<Bytes, HEquations>(); try { - ClassEquations rawEquations = processClass(new ClassReader(inputData.getContent())); - List<Equation<Key, Value>> rawParameterEquations = rawEquations.parameterEquations; - List<Equation<Key, Value>> rawContractEquations = rawEquations.contractEquations; + MessageDigest md = BytecodeAnalysisConverter.getMessageDigest(); + Map<Key, List<Equation<Key, Value>>> rawEquations = processClass(new ClassReader(inputData.getContent()), inputData.getFile().getPresentableUrl()); + for (Map.Entry<Key, List<Equation<Key, Value>>> entry: rawEquations.entrySet()) { + Key primaryKey = entry.getKey(); + Key serKey = new Key(primaryKey.method, primaryKey.direction, true); - for (Equation<Key, Value> rawParameterEquation: rawParameterEquations) { - IdEquation equation = myConverter.convert(rawParameterEquation); - map.put(equation.id, equation); - } - for (Equation<Key, Value> rawContractEquation: rawContractEquations) { - IdEquation equation = myConverter.convert(rawContractEquation); - map.put(equation.id, equation); + List<Equation<Key, Value>> equations = entry.getValue(); + List<DirectionResultPair> result = new ArrayList<DirectionResultPair>(equations.size()); + for (Equation<Key, Value> equation : equations) { + result.add(BytecodeAnalysisConverter.convert(equation, md)); + } + map.put(new Bytes(BytecodeAnalysisConverter.asmKey(serKey, md).key), new HEquations(result, primaryKey.stable)); } } catch (ProcessCanceledException e) { @@ -66,28 +72,21 @@ public class ClassDataIndexer implements DataIndexer<Long, IdEquation, FileConte // so here we suppose that exception is due to incorrect bytecode LOG.debug("Unexpected Error during indexing of bytecode", e); } + //return map; 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 Map<Key, List<Equation<Key, Value>>> processClass(final ClassReader classReader, final String presentableUrl) { - 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>>(); + final Map<Key, List<Equation<Key, Value>>> equations = new HashMap<Key, List<Equation<Key, Value>>>(); classReader.accept(new ClassVisitor(Opcodes.ASM5) { + private String className; private boolean stableClass; @Override public void visit(int version, int access, String name, String signature, String superName, String[] interfaces) { + className = name; stableClass = (access & Opcodes.ACC_FINAL) != 0; super.visit(version, access, name, signature, superName, interfaces); } @@ -96,164 +95,286 @@ public class ClassDataIndexer implements DataIndexer<Long, IdEquation, FileConte 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) { + private boolean jsr; + + @Override + public void visitJumpInsn(int opcode, Label label) { + if (opcode == Opcodes.JSR) { + jsr = true; + } + super.visitJumpInsn(opcode, label); + } + @Override public void visitEnd() { super.visitEnd(); - processMethod(classReader.getClassName(), node, stableClass); + Pair<Key, List<Equation<Key, Value>>> methodEquations = processMethod(node, jsr); + equations.put(methodEquations.first, methodEquations.second); } }; } - void processMethod(final String className, final MethodNode methodNode, boolean stableClass) { + private Pair<Key, List<Equation<Key, Value>>> processMethod(final MethodNode methodNode, boolean jsr) { 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; + final Type[] argumentTypes = Type.getArgumentTypes(methodNode.desc); + final Type resultType = Type.getReturnType(methodNode.desc); + final boolean isReferenceResult = ASMUtils.isReferenceType(resultType); + final boolean isBooleanResult = ASMUtils.isBooleanType(resultType); + final boolean isInterestingResult = isReferenceResult || isBooleanResult; + final Method method = new Method(className, methodNode.name, methodNode.desc); + final boolean stable = stableClass || (methodNode.access & STABLE_FLAGS) != 0 || "<init>".equals(methodNode.name); + + Key primaryKey = new Key(method, new Out(), stable); if (argumentTypes.length == 0 && !isInterestingResult) { - return; + return Pair.create(primaryKey, EMPTY_EQUATIONS); } - 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; + final ControlFlowGraph graph = ControlFlowGraph.build(className, methodNode, jsr); + if (graph.transitions.length > 0) { + final DFSTree dfs = DFSTree.build(graph.transitions, graph.edgeCount); + boolean branching = !dfs.back.isEmpty(); + if (!branching) { + for (int[] transition : graph.transitions) { + if (transition != null && transition.length > 1) { + branching = true; + break; + } + } + } + + if (branching) { + RichControlFlow richControlFlow = new RichControlFlow(graph, dfs); + if (richControlFlow.reducible()) { + return Pair.create(primaryKey, + processBranchingMethod(method, methodNode, richControlFlow, argumentTypes, isReferenceResult, isInterestingResult, stable, jsr)); + } + LOG.debug(method + ": CFG is not reducible"); + } + // simple + else { + return Pair.create(primaryKey, + processNonBranchingMethod(method, argumentTypes, graph, isReferenceResult, isBooleanResult, stable)); } } + return Pair.create(primaryKey, topEquations(method, argumentTypes, isReferenceResult, isInterestingResult, stable)); + } + 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 + " in " + presentableUrl, e); + return Pair.create(primaryKey, topEquations(method, argumentTypes, isReferenceResult, isInterestingResult, stable)); + } + } - 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; - } - } + private List<Equation<Key, Value>> processBranchingMethod(final Method method, + final MethodNode methodNode, + final RichControlFlow richControlFlow, + Type[] argumentTypes, + boolean isReferenceResult, + boolean isInterestingResult, + final boolean stable, + boolean jsr) throws AnalyzerException { + + List<Equation<Key, Value>> result = new ArrayList<Equation<Key, Value>>(argumentTypes.length * 4 + 1); + boolean maybeLeakingParameter = isInterestingResult; + for (Type argType : argumentTypes) { + if (ASMUtils.isReferenceType(argType) || (isReferenceResult && ASMUtils.isBooleanType(argType))) { + maybeLeakingParameter = true; + break; + } + } + + final LeakingParameters leakingParametersAndFrames = + maybeLeakingParameter ? leakingParametersAndFrames(method, methodNode, argumentTypes, jsr) : null; + boolean[] leakingParameters = + leakingParametersAndFrames != null ? leakingParametersAndFrames.parameters : null; + boolean[] leakingNullableParameters = + leakingParametersAndFrames != null ? leakingParametersAndFrames.nullableParameters : null; + + final NullableLazyValue<boolean[]> origins = new NullableLazyValue<boolean[]>() { + @Override + protected boolean[] compute() { + try { + return OriginsAnalysis.resultOrigins(leakingParametersAndFrames.frames, methodNode.instructions, richControlFlow.controlFlow); + } + catch (AnalyzerException e) { + LOG.debug("when processing " + method + " in " + presentableUrl, e); + return null; + } + } + }; + + NotNullLazyValue<Equation<Key, Value>> outEquation = new NotNullLazyValue<Equation<Key, Value>>() { + @NotNull + @Override + protected Equation<Key, Value> compute() { + if (origins.getValue() != null) { + try { + return new InOutAnalysis(richControlFlow, new Out(), origins.getValue(), stable).analyze(); + } + catch (AnalyzerException ignored) { } + } + return new Equation<Key, Value>(new Key(method, new Out(), stable), FINAL_TOP); + } + }; - 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 (isReferenceResult) { + result.add(outEquation.getValue()); + } + + for (int i = 0; i < argumentTypes.length; i++) { + boolean isReferenceArg = ASMUtils.isReferenceType(argumentTypes[i]); + boolean notNullParam = false; + + if (isReferenceArg) { + boolean possibleNPE = false; + if (leakingParameters[i]) { + NonNullInAnalysis notNullInAnalysis = new NonNullInAnalysis(richControlFlow, new In(i, In.NOT_NULL), stable); + Equation<Key, Value> notNullParamEquation = notNullInAnalysis.analyze(); + possibleNPE = notNullInAnalysis.possibleNPE; + notNullParam = notNullParamEquation.rhs.equals(FINAL_NOT_NULL); + result.add(notNullParamEquation); + } + else { + // parameter is not leaking, so it is definitely NOT @NotNull + result.add(new Equation<Key, Value>(new Key(method, new In(i, In.NOT_NULL), stable), FINAL_TOP)); + } + if (leakingNullableParameters[i]) { + if (notNullParam || possibleNPE) { + result.add(new Equation<Key, Value>(new Key(method, new In(i, In.NULLABLE), stable), FINAL_TOP)); + } + else { + result.add(new NullableInAnalysis(richControlFlow, new In(i, In.NULLABLE), stable).analyze()); + } + } + else { + result.add(new Equation<Key, Value>(new Key(method, new In(i, In.NULLABLE), stable), FINAL_NULL)); + } + } + if (isReferenceArg && isInterestingResult) { + if (leakingParameters[i]) { + if (origins.getValue() != null) { + // result origins analysis was ok + if (!notNullParam) { + // may be null on some branch, running "null->..." analysis + result.add(new InOutAnalysis(richControlFlow, new InOut(i, Value.Null), origins.getValue(), stable).analyze()); } - 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)); - } + else { + // @NotNull, so "null->fail" + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.Null), stable), FINAL_BOT)); } + result.add(new InOutAnalysis(richControlFlow, new InOut(i, Value.NotNull), origins.getValue(), stable).analyze()); } - if (isReferenceResult) { - if (resultEquation != null) { - contractEquations.add(resultEquation); - } else { - contractEquations.add(new InOutAnalysis(new RichControlFlow(graph, dfs), new Out(), resultOrigins.getValue(), stable).analyze()); - } + else { + // result origins analysis failed, approximating to Top + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.Null), stable), FINAL_TOP)); + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.NotNull), stable), FINAL_TOP)); } - added = true; } else { - LOG.debug("CFG for " + method + " is not reducible"); + // parameter is not leaking, so a contract is the same as for the whole method + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.Null), stable), outEquation.getValue().rhs)); + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.NotNull), stable), outEquation.getValue().rhs)); } } - - 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 (ASMUtils.isBooleanType(argumentTypes[i]) && isInterestingResult) { + if (leakingParameters[i]) { + if (origins.getValue() != null) { + // result origins analysis was ok + result.add(new InOutAnalysis(richControlFlow, new InOut(i, Value.False), origins.getValue(), stable).analyze()); + result.add(new InOutAnalysis(richControlFlow, new InOut(i, Value.True), origins.getValue(), stable).analyze()); } - 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))); + else { + // result origins analysis failed, approximating to Top + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.False), stable), FINAL_TOP)); + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.True), stable), FINAL_TOP)); } } - if (isReferenceResult) { - contractEquations.add(new Equation<Key, Value>(new Key(method, new Out(), stable), new Final<Key, Value>(Value.Top))); + else { + // parameter is not leaking, so a contract is the same as for the whole method + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.False), stable), outEquation.getValue().rhs)); + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.True), stable), outEquation.getValue().rhs)); } } } - catch (ProcessCanceledException e) { - throw e; + return result; + } + + private List<Equation<Key, Value>> processNonBranchingMethod(Method method, + Type[] argumentTypes, + ControlFlowGraph graph, + boolean isReferenceResult, + boolean isBooleanResult, + boolean stable) throws AnalyzerException { + List<Equation<Key, Value>> result = new ArrayList<Equation<Key, Value>>(argumentTypes.length * 4 + 1); + CombinedSingleAnalysis analyzer = new CombinedSingleAnalysis(method, graph); + analyzer.analyze(); + if (isReferenceResult) { + result.add(analyzer.outContractEquation(stable)); } - 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); + for (int i = 0; i < argumentTypes.length; i++) { + Type argType = argumentTypes[i]; + boolean isRefArg = ASMUtils.isReferenceType(argType); + if (isRefArg) { + result.add(analyzer.notNullParamEquation(i, stable)); + result.add(analyzer.nullableParamEquation(i, stable)); + } + if (isRefArg && (isReferenceResult || isBooleanResult)) { + result.add(analyzer.contractEquation(i, Value.Null, stable)); + result.add(analyzer.contractEquation(i, Value.NotNull, stable)); + } + if (ASMUtils.isBooleanType(argType) && (isReferenceResult || isBooleanResult)) { + result.add(analyzer.contractEquation(i, Value.True, stable)); + result.add(analyzer.contractEquation(i, Value.False, stable)); + } } + return result; + } + + private List<Equation<Key, Value>> topEquations(Method method, + Type[] argumentTypes, + boolean isReferenceResult, + boolean isInterestingResult, + boolean stable) { + List<Equation<Key, Value>> result = new ArrayList<Equation<Key, Value>>(argumentTypes.length * 3 + 1); + if (isReferenceResult) { + result.add(new Equation<Key, Value>(new Key(method, new Out(), stable), FINAL_TOP)); + } + for (int i = 0; i < argumentTypes.length; i++) { + Type argType = argumentTypes[i]; + boolean isReferenceArg = ASMUtils.isReferenceType(argType); + boolean isBooleanArg = ASMUtils.isBooleanType(argType); + + if (isReferenceArg) { + result.add(new Equation<Key, Value>(new Key(method, new In(i, In.NOT_NULL), stable), FINAL_TOP)); + result.add(new Equation<Key, Value>(new Key(method, new In(i, In.NULLABLE), stable), FINAL_TOP)); + } + if (isReferenceArg && isInterestingResult) { + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.Null), stable), FINAL_TOP)); + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.NotNull), stable), FINAL_TOP)); + } + if (isBooleanArg && isInterestingResult) { + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.False), stable), FINAL_TOP)); + result.add(new Equation<Key, Value>(new Key(method, new InOut(i, Value.True), stable), FINAL_TOP)); + } + } + return result; + } + + private LeakingParameters leakingParametersAndFrames(Method method, MethodNode methodNode, Type[] argumentTypes, boolean jsr) + throws AnalyzerException { + return argumentTypes.length < 32 ? + LeakingParameters.buildFast(method.internalClassName, methodNode, jsr) : + LeakingParameters.build(method.internalClassName, methodNode, jsr); } }, ClassReader.SKIP_DEBUG | ClassReader.SKIP_FRAMES); - return new ClassEquations(parameterEquations, contractEquations); + return equations; } } diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Combined.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Combined.java new file mode 100644 index 000000000000..645c00260af1 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Combined.java @@ -0,0 +1,465 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis; + +import com.intellij.codeInspection.bytecodeAnalysis.asm.ASMUtils; +import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph; +import com.intellij.util.SingletonSet; +import com.intellij.util.containers.HashSet; +import org.jetbrains.org.objectweb.asm.Handle; +import org.jetbrains.org.objectweb.asm.Opcodes; +import org.jetbrains.org.objectweb.asm.Type; +import org.jetbrains.org.objectweb.asm.tree.*; +import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException; +import org.jetbrains.org.objectweb.asm.tree.analysis.BasicInterpreter; +import org.jetbrains.org.objectweb.asm.tree.analysis.BasicValue; +import org.jetbrains.org.objectweb.asm.tree.analysis.Frame; + +import java.util.Collections; +import java.util.List; +import java.util.Set; + +import static com.intellij.codeInspection.bytecodeAnalysis.AbstractValues.*; +import static org.jetbrains.org.objectweb.asm.Opcodes.*; + +final class ParamKey { + final Method method; + final int i; + final boolean stable; + + + ParamKey(Method method, int i, boolean stable) { + this.method = method; + this.i = i; + this.stable = stable; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + ParamKey paramKey = (ParamKey)o; + + if (i != paramKey.i) return false; + if (stable != paramKey.stable) return false; + if (!method.equals(paramKey.method)) return false; + + return true; + } + + @Override + public int hashCode() { + int result = method.hashCode(); + result = 31 * result + i; + result = 31 * result + (stable ? 1 : 0); + return result; + } +} + +final class CombinedCall extends BasicValue { + final Method method; + final boolean stableCall; + final List<? extends BasicValue> args; + + CombinedCall(Type tp, Method method, boolean stableCall, List<? extends BasicValue> args) { + super(tp); + this.method = method; + this.stableCall = stableCall; + this.args = args; + } +} + +final class NParamValue extends BasicValue { + final int n; + public NParamValue(Type type, int n) { + super(type); + this.n = n; + } +} + +final class CombinedSingleAnalysis { + private final ControlFlowGraph controlFlow; + private final Method method; + private final CombinedInterpreter interpreter; + private BasicValue returnValue; + private boolean exception; + private final MethodNode methodNode; + + CombinedSingleAnalysis(Method method, ControlFlowGraph controlFlow) { + this.method = method; + this.controlFlow = controlFlow; + methodNode = controlFlow.methodNode; + interpreter = new CombinedInterpreter(Type.getArgumentTypes(methodNode.desc).length); + } + + final void analyze() throws AnalyzerException { + Frame<BasicValue> frame = createStartFrame(); + int insnIndex = 0; + + while (true) { + AbstractInsnNode insnNode = methodNode.instructions.get(insnIndex); + switch (insnNode.getType()) { + case AbstractInsnNode.LABEL: + case AbstractInsnNode.LINE: + case AbstractInsnNode.FRAME: + insnIndex = controlFlow.transitions[insnIndex][0]; + break; + default: + switch (insnNode.getOpcode()) { + case ATHROW: + exception = true; + return; + case ARETURN: + case IRETURN: + case LRETURN: + case FRETURN: + case DRETURN: + returnValue = frame.pop(); + return; + case RETURN: + // nothing to return + return; + default: + frame.execute(insnNode, interpreter); + insnIndex = controlFlow.transitions[insnIndex][0]; + } + } + } + } + + final Equation<Key, Value> notNullParamEquation(int i, boolean stable) { + final Key key = new Key(method, new In(i, In.NOT_NULL), stable); + final Result<Key, Value> result; + if (interpreter.dereferenced[i]) { + result = new Final<Key, Value>(Value.NotNull); + } + else { + Set<ParamKey> calls = interpreter.callDerefs[i]; + if (calls == null || calls.isEmpty()) { + result = new Final<Key, Value>(Value.Top); + } + else { + Set<Key> keys = new HashSet<Key>(); + for (ParamKey pk: calls) { + keys.add(new Key(pk.method, new In(pk.i, In.NOT_NULL), pk.stable)); + } + result = new Pending<Key, Value>(new SingletonSet<Product<Key, Value>>(new Product<Key, Value>(Value.Top, keys))); + } + } + return new Equation<Key, Value>(key, result); + } + + final Equation<Key, Value> nullableParamEquation(int i, boolean stable) { + final Key key = new Key(method, new In(i, In.NULLABLE), stable); + final Result<Key, Value> result; + if (interpreter.dereferenced[i] || interpreter.notNullable[i] || returnValue instanceof NParamValue && ((NParamValue)returnValue).n == i) { + result = new Final<Key, Value>(Value.Top); + } + else { + Set<ParamKey> calls = interpreter.callDerefs[i]; + if (calls == null || calls.isEmpty()) { + result = new Final<Key, Value>(Value.Null); + } + else { + Set<Product<Key, Value>> sum = new HashSet<Product<Key, Value>>(); + for (ParamKey pk: calls) { + sum.add(new Product<Key, Value>(Value.Top, Collections.singleton(new Key(pk.method, new In(pk.i, In.NULLABLE), pk.stable)))); + } + result = new Pending<Key, Value>(sum); + } + } + return new Equation<Key, Value>(key, result); + } + + final Equation<Key, Value> contractEquation(int i, Value inValue, boolean stable) { + final Key key = new Key(method, new InOut(i, inValue), stable); + final Result<Key, Value> result; + if (exception || (inValue == Value.Null && interpreter.dereferenced[i])) { + result = new Final<Key, Value>(Value.Bot); + } + else if (FalseValue == returnValue) { + result = new Final<Key, Value>(Value.False); + } + else if (TrueValue == returnValue) { + result = new Final<Key, Value>(Value.True); + } + else if (NullValue == returnValue) { + result = new Final<Key, Value>(Value.Null); + } + else if (returnValue instanceof NotNullValue) { + result = new Final<Key, Value>(Value.NotNull); + } + else if (returnValue instanceof NParamValue && ((NParamValue)returnValue).n == i) { + result = new Final<Key, Value>(inValue); + } + else if (returnValue instanceof CombinedCall) { + CombinedCall call = (CombinedCall)returnValue; + HashSet<Key> keys = new HashSet<Key>(); + for (int argI = 0; argI < call.args.size(); argI++) { + BasicValue arg = call.args.get(argI); + if (arg instanceof NParamValue) { + NParamValue npv = (NParamValue)arg; + if (npv.n == i) { + keys.add(new Key(call.method, new InOut(argI, inValue), call.stableCall)); + } + } + } + if (ASMUtils.isReferenceType(call.getType())) { + keys.add(new Key(call.method, new Out(), call.stableCall)); + } + if (keys.isEmpty()) { + result = new Final<Key, Value>(Value.Top); + } else { + result = new Pending<Key, Value>(new SingletonSet<Product<Key, Value>>(new Product<Key, Value>(Value.Top, keys))); + } + } + else { + result = new Final<Key, Value>(Value.Top); + } + return new Equation<Key, Value>(key, result); + } + + final Equation<Key, Value> outContractEquation(boolean stable) { + final Key key = new Key(method, new Out(), stable); + final Result<Key, Value> result; + if (exception) { + result = new Final<Key, Value>(Value.Bot); + } + else if (FalseValue == returnValue) { + result = new Final<Key, Value>(Value.False); + } + else if (TrueValue == returnValue) { + result = new Final<Key, Value>(Value.True); + } + else if (NullValue == returnValue) { + result = new Final<Key, Value>(Value.Null); + } + else if (returnValue instanceof NotNullValue) { + result = new Final<Key, Value>(Value.NotNull); + } + else if (returnValue instanceof CombinedCall) { + CombinedCall call = (CombinedCall)returnValue; + Key callKey = new Key(call.method, new Out(), call.stableCall); + Set<Key> keys = new SingletonSet<Key>(callKey); + result = new Pending<Key, Value>(new SingletonSet<Product<Key, Value>>(new Product<Key, Value>(Value.Top, keys))); + } + else { + result = new Final<Key, Value>(Value.Top); + } + return new Equation<Key, Value>(key, result); + } + + 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 = new NParamValue(args[i], 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; + } +} + +final class CombinedInterpreter extends BasicInterpreter { + final boolean[] dereferenced; + final boolean[] notNullable; + final Set<ParamKey>[] callDerefs; + + CombinedInterpreter(int arity) { + dereferenced = new boolean[arity]; + notNullable = new boolean[arity]; + callDerefs = new Set[arity]; + } + + @Override + public BasicValue newOperation(AbstractInsnNode insn) throws AnalyzerException { + 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 CLASS_VALUE; + } + if (type.getSort() == Type.METHOD) { + return METHOD_VALUE; + } + } + else if (cst instanceof String) { + return STRING_VALUE; + } + else if (cst instanceof Handle) { + return METHOD_HANDLE_VALUE; + } + 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 { + switch (insn.getOpcode()) { + case GETFIELD: + case ARRAYLENGTH: + case MONITORENTER: + if (value instanceof NParamValue) { + dereferenced[((NParamValue)value).n] = true; + } + return super.unaryOperation(insn, value); + case CHECKCAST: + if (value instanceof NParamValue) { + return new NParamValue(Type.getObjectType(((TypeInsnNode)insn).desc), ((NParamValue)value).n); + } + break; + case NEWARRAY: + case ANEWARRAY: + return new NotNullValue(super.unaryOperation(insn, value).getType()); + 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: + if (value1 instanceof NParamValue) { + dereferenced[((NParamValue)value1).n] = true; + } + break; + case PUTFIELD: + if (value1 instanceof NParamValue) { + dereferenced[((NParamValue)value1).n] = true; + } + if (value2 instanceof NParamValue) { + notNullable[((NParamValue)value2).n] = 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 BASTORE: + case CASTORE: + case SASTORE: + if (value1 instanceof NParamValue) { + dereferenced[((NParamValue)value1).n] = true; + } + break; + case AASTORE: + if (value1 instanceof NParamValue) { + dereferenced[((NParamValue)value1).n] = true; + } + if (value3 instanceof NParamValue) { + notNullable[((NParamValue)value3).n] = true; + } + break; + default: + } + return super.ternaryOperation(insn, value1, value2, value3); + } + + @Override + public BasicValue naryOperation(AbstractInsnNode insn, List<? extends BasicValue> values) throws AnalyzerException { + int opCode = insn.getOpcode(); + int shift = opCode == INVOKESTATIC ? 0 : 1; + + switch (opCode) { + case INVOKESPECIAL: + case INVOKEINTERFACE: + case INVOKEVIRTUAL: + if (values.get(0) instanceof NParamValue) { + dereferenced[((NParamValue)values.get(0)).n] = true; + } + } + + 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); + + for (int i = shift; i < values.size(); i++) { + if (values.get(i) instanceof NParamValue) { + int n = ((NParamValue)values.get(i)).n; + if (opCode == INVOKEINTERFACE) { + notNullable[n] = true; + } + else { + Set<ParamKey> npKeys = callDerefs[n]; + if (npKeys == null) { + npKeys = new HashSet<ParamKey>(); + callDerefs[n] = npKeys; + } + npKeys.add(new ParamKey(method, i - shift, stable)); + } + } + } + if (shift == 1) { + values.remove(0); + } + return new CombinedCall(retType, method, stable, values); + 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/Contracts.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Contracts.java index 7b6c52e75a63..c382148abb05 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Contracts.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Contracts.java @@ -15,7 +15,10 @@ */ package com.intellij.codeInspection.bytecodeAnalysis; -import gnu.trove.TIntHashSet; +import com.intellij.codeInspection.bytecodeAnalysis.asm.ASMUtils; +import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph.Edge; +import com.intellij.codeInspection.bytecodeAnalysis.asm.RichControlFlow; +import org.jetbrains.annotations.NotNull; import org.jetbrains.org.objectweb.asm.Handle; import org.jetbrains.org.objectweb.asm.Type; import org.jetbrains.org.objectweb.asm.tree.*; @@ -24,75 +27,104 @@ import org.jetbrains.org.objectweb.asm.tree.analysis.BasicInterpreter; import org.jetbrains.org.objectweb.asm.tree.analysis.BasicValue; import org.jetbrains.org.objectweb.asm.tree.analysis.Frame; -import java.util.*; +import java.util.Collections; +import java.util.HashSet; +import java.util.List; +import java.util.Set; 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 = + static final ResultUtil<Key, Value> resultUtil = new ResultUtil<Key, Value>(new ELattice<Value>(Value.Bot, Value.Top)); + final private State[] pending = ourPendingStates.get(); private final InOutInterpreter interpreter; private final Value inValue; + private final int generalizeShift; + private Result<Key, Value> internalResult; + private int id = 0; + private int pendingTop = 0; - protected InOutAnalysis(RichControlFlow richControlFlow, Direction direction, TIntHashSet resultOrigins, boolean stable) { + protected InOutAnalysis(RichControlFlow richControlFlow, Direction direction, boolean[] resultOrigins, boolean stable) { super(richControlFlow, direction, stable); interpreter = new InOutInterpreter(direction, richControlFlow.controlFlow.methodNode.instructions, resultOrigins); inValue = direction instanceof InOut ? ((InOut)direction).inValue : null; + generalizeShift = (methodNode.access & ACC_STATIC) == 0 ? 1 : 0; + internalResult = new Final<Key, Value>(Value.Bot); } - @Override - Result<Key, Value> identity() { - return new Final<Key, Value>(Value.Bot); + @NotNull + Equation<Key, Value> mkEquation(Result<Key, Value> res) { + return new Equation<Key, Value>(aKey, res); } - @Override - Result<Key, Value> combineResults(Result<Key, Value> delta, List<Result<Key, Value>> subResults) throws AnalyzerException { - Result<Key, Value> result = null; - for (Result<Key, Value> subResult : subResults) { - if (result == null) { - result = subResult; - } else { - result = resultUtil.join(result, subResult); + @NotNull + protected Equation<Key, Value> analyze() throws AnalyzerException { + pendingPush(createStartState()); + int steps = 0; + while (pendingTop > 0 && earlyResult == null) { + steps ++; + if (steps >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached, steps: " + steps + " in method " + method); + } + State state = pending[--pendingTop]; + int insnIndex = state.conf.insnIndex; + Conf conf = state.conf; + List<Conf> history = state.history; + + boolean fold = false; + if (dfsTree.loopEnters[insnIndex]) { + for (Conf prev : history) { + if (AbstractValues.isInstance(conf, prev)) { + fold = true; + break; + } + } + } + if (fold) { + addComputed(insnIndex, state); + } + else { + State baseState = null; + List<State> thisComputed = computed[insnIndex]; + if (thisComputed != null) { + for (State prevState : thisComputed) { + if (stateEquiv(state, prevState)) { + baseState = prevState; + break; + } + } + } + if (baseState == null) { + processState(state); + } } } - return result; - } - - @Override - boolean isEarlyResult(Result<Key, Value> res) { - if (res instanceof Final) { - return ((Final<?, Value>)res).value == Value.Top; + if (earlyResult != null) { + return mkEquation(earlyResult); + } else { + return mkEquation(internalResult); } - 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); + boolean loopEnter = dfsTree.loopEnters[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; + List<Conf> nextHistory = loopEnter ? append(history, conf) : history; Frame<BasicValue> nextFrame = execute(frame, insnNode); + addComputed(insnIndex, state); + if (interpreter.deReferenced) { - results.put(stateIndex, new Final<Key, Value>(Value.Bot)); - computed.put(insnIndex, append(computed.get(insnIndex), state)); return; } @@ -105,38 +137,36 @@ class InOutAnalysis extends Analysis<Result<Key, Value>> { case DRETURN: case RETURN: BasicValue stackTop = popValue(frame); + Result<Key, Value> subResult; if (FalseValue == stackTop) { - results.put(stateIndex, new Final<Key, Value>(Value.False)); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + subResult = new Final<Key, Value>(Value.False); } else if (TrueValue == stackTop) { - results.put(stateIndex, new Final<Key, Value>(Value.True)); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + subResult = new Final<Key, Value>(Value.True); } else if (NullValue == stackTop) { - results.put(stateIndex, new Final<Key, Value>(Value.Null)); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + subResult = new Final<Key, Value>(Value.Null); } else if (stackTop instanceof NotNullValue) { - results.put(stateIndex, new Final<Key, Value>(Value.NotNull)); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + subResult = new Final<Key, Value>(Value.NotNull); } else if (stackTop instanceof ParamValue) { - results.put(stateIndex, new Final<Key, Value>(inValue)); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + subResult = new Final<Key, Value>(inValue); } 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)); + subResult = new Pending<Key, Value>(Collections.singleton(new Product<Key, Value>(Value.Top, keys))); } else { earlyResult = new Final<Key, Value>(Value.Top); + return; + } + internalResult = resultUtil.join(internalResult, subResult); + if (internalResult instanceof Final && ((Final<?, Value>)internalResult).value == Value.Top) { + earlyResult = internalResult; } return; case ATHROW: - results.put(stateIndex, new Final<Key, Value>(Value.Bot)); - computed.put(insnIndex, append(computed.get(insnIndex), state)); return; default: } @@ -144,72 +174,62 @@ class InOutAnalysis extends Analysis<Result<Key, Value>> { 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)); + pendingPush(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)); + pendingPush(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)); + pendingPush(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)); + pendingPush(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)); + pendingPush(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)); + pendingPush(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]; + for (int nextInsnIndex : controlFlow.transitions[insnIndex]) { Frame<BasicValue> nextFrame1 = nextFrame; - if (controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { + if (controlFlow.errors[nextInsnIndex] && controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { nextFrame1 = new Frame<BasicValue>(frame); nextFrame1.clearStack(); - nextFrame1.push(new BasicValue(Type.getType("java/lang/Throwable"))); + nextFrame1.push(ASMUtils.THROWABLE_VALUE); } - nextStates.add(new State(++id, new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, false)); - subIndices[i] = id; + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, false)); } + } - pending.push(new MakeResult<Result<Key, Value>>(state, myIdentity, subIndices)); - for (State nextState : nextStates) { - pending.push(new ProceedState<Result<Key, Value>>(nextState)); + private void pendingPush(State st) throws AnalyzerException { + if (pendingTop >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached in method " + method); } + pending[pendingTop++] = st; } private Frame<BasicValue> execute(Frame<BasicValue> frame, AbstractInsnNode insnNode) throws AnalyzerException { @@ -226,9 +246,9 @@ class InOutAnalysis extends Analysis<Result<Key, Value>> { } } - private static Conf generalize(Conf conf) { + private Conf generalize(Conf conf) { Frame<BasicValue> frame = new Frame<BasicValue>(conf.frame); - for (int i = 0; i < frame.getLocals(); i++) { + for (int i = generalizeShift; i < frame.getLocals(); i++) { BasicValue value = frame.getLocal(i); Class<?> valueClass = value.getClass(); if (valueClass != BasicValue.class && valueClass != ParamValue.class) { @@ -258,12 +278,12 @@ class InOutAnalysis extends Analysis<Result<Key, Value>> { class InOutInterpreter extends BasicInterpreter { final Direction direction; final InsnList insns; - final TIntHashSet resultOrigins; + final boolean[] resultOrigins; final boolean nullAnalysis; boolean deReferenced = false; - InOutInterpreter(Direction direction, InsnList insns, TIntHashSet resultOrigins) { + InOutInterpreter(Direction direction, InsnList insns, boolean[] resultOrigins) { this.direction = direction; this.insns = insns; this.resultOrigins = resultOrigins; @@ -272,7 +292,7 @@ class InOutInterpreter extends BasicInterpreter { @Override public BasicValue newOperation(AbstractInsnNode insn) throws AnalyzerException { - boolean propagate = resultOrigins.contains(insns.indexOf(insn)); + boolean propagate = resultOrigins[insns.indexOf(insn)]; if (propagate) { switch (insn.getOpcode()) { case ICONST_0: @@ -286,17 +306,17 @@ class InOutInterpreter extends BasicInterpreter { 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")); + return CLASS_VALUE; } if (type.getSort() == Type.METHOD) { - return new NotNullValue(Type.getObjectType("java/lang/invoke/MethodType")); + return METHOD_VALUE; } } else if (cst instanceof String) { - return new NotNullValue(Type.getObjectType("java/lang/String")); + return STRING_VALUE; } else if (cst instanceof Handle) { - return new NotNullValue(Type.getObjectType("java/lang/invoke/MethodHandle")); + return METHOD_HANDLE_VALUE; } break; case NEW: @@ -309,7 +329,7 @@ class InOutInterpreter extends BasicInterpreter { @Override public BasicValue unaryOperation(AbstractInsnNode insn, BasicValue value) throws AnalyzerException { - boolean propagate = resultOrigins.contains(insns.indexOf(insn)); + boolean propagate = resultOrigins[insns.indexOf(insn)]; switch (insn.getOpcode()) { case GETFIELD: case ARRAYLENGTH: @@ -381,7 +401,7 @@ class InOutInterpreter extends BasicInterpreter { @Override public BasicValue naryOperation(AbstractInsnNode insn, List<? extends BasicValue> values) throws AnalyzerException { - boolean propagate = resultOrigins.contains(insns.indexOf(insn)); + boolean propagate = resultOrigins[insns.indexOf(insn)]; int opCode = insn.getOpcode(); int shift = opCode == INVOKESTATIC ? 0 : 1; 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 deleted file mode 100644 index 910d75b9a57f..000000000000 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ControlFlow.java +++ /dev/null @@ -1,1030 +0,0 @@ -/* - * 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 index 132c5643b2d6..55a842af684c 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Data.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Data.java @@ -52,20 +52,17 @@ 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(); -} +interface Direction {} final class In implements Direction { + static final int NOT_NULL = 0; + static final int NULLABLE = 1; final int paramIndex; + final int nullityMask; - In(int paramIndex) { + In(int paramIndex, int nullityMask) { this.paramIndex = paramIndex; + this.nullityMask = nullityMask; } @Override @@ -79,28 +76,19 @@ final class In implements Direction { if (o == null || getClass() != o.getClass()) return false; In in = (In) o; if (paramIndex != in.paramIndex) return false; + if (nullityMask != in.nullityMask) return false; return true; } @Override public int hashCode() { - return paramIndex; + return 31*paramIndex + nullityMask; } - @Override - public int directionId() { - return IN_DIRECTION; - } - - @Override public int paramId() { return paramIndex; } - @Override - public int valueId() { - return 0; - } } final class InOut implements Direction { @@ -137,17 +125,10 @@ final class InOut implements Direction { 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(); } @@ -168,21 +149,6 @@ final class Out implements Direction { 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 { @@ -219,8 +185,6 @@ final class Key { @Override public String toString() { - return "" + method + ' ' + direction + ' ' + stable; + return method + " " + direction + " " + stable; } } - - diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/HData.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/HData.java new file mode 100644 index 000000000000..7c938347ccb9 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/HData.java @@ -0,0 +1,311 @@ +/* + * 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.annotations.NotNull; + +import java.util.Arrays; +import java.util.List; + +/** + * Small size key, constructed by hashing method signature. + * @see com.intellij.codeInspection.bytecodeAnalysis.BytecodeAnalysisConverter for details of construction. + */ +final class HKey { + @NotNull + final byte[] key; + final int dirKey; + final boolean stable; + + HKey(@NotNull byte[] key, int dirKey, boolean stable) { + this.key = key; + this.dirKey = dirKey; + this.stable = stable; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + HKey hKey = (HKey)o; + if (dirKey != hKey.dirKey) return false; + if (stable != hKey.stable) return false; + if (!Arrays.equals(key, hKey.key)) return false; + return true; + } + + @Override + public int hashCode() { + int result = Arrays.hashCode(key); + result = 31 * result + dirKey; + result = 31 * result + (stable ? 1 : 0); + return result; + } + + HKey negate() { + return new HKey(key, dirKey, !stable); + } + + HKey mkStable() { + return stable ? this : new HKey(key, dirKey, true); + } + + HKey mkUnstable() { + return stable ? new HKey(key, dirKey, false) : this; + } + + public HKey mkBase() { + return dirKey == 0 ? this : new HKey(key, 0, stable); + } + + HKey updateDirection(int newDirKey) { + return new HKey(key, newDirKey, stable); + } +} + +final class HComponent { + @NotNull Value value; + @NotNull final HKey[] ids; + + HComponent(@NotNull Value value, @NotNull HKey[] 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; + + HComponent that = (HComponent)o; + + if (!Arrays.equals(ids, that.ids)) return false; + if (value != that.value) return false; + + return true; + } + + @Override + public int hashCode() { + int result = value.hashCode(); + result = 31 * result + Arrays.hashCode(ids); + return result; + } + + public boolean remove(@NotNull HKey id) { + return HUtils.remove(ids, id); + } + + public boolean isEmpty() { + return HUtils.isEmpty(ids); + } + + @NotNull + public HComponent copy() { + return new HComponent(value, ids.clone()); + } +} + +class HUtils { + + static boolean isEmpty(HKey[] ids) { + for (HKey id : ids) { + if (id != null) return false; + } + return true; + } + + static boolean remove(HKey[] ids, @NotNull HKey id) { + boolean removed = false; + for (int i = 0; i < ids.length; i++) { + if (id.equals(ids[i])) { + ids[i] = null; + removed = true; + } + } + return removed; + } +} + +final class HEquation { + @NotNull final HKey key; + @NotNull final HResult result; + + HEquation(@NotNull HKey key, @NotNull HResult result) { + this.key = key; + this.result = result; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + HEquation hEquation = (HEquation)o; + if (!key.equals(hEquation.key)) return false; + if (!result.equals(hEquation.result)) return false; + return true; + } + + @Override + public int hashCode() { + int result1 = key.hashCode(); + result1 = 31 * result1 + result.hashCode(); + return result1; + } +} +class Bytes { + @NotNull + final byte[] bytes; + Bytes(@NotNull byte[] bytes) { + this.bytes = bytes; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + Bytes bytes1 = (Bytes)o; + + if (!Arrays.equals(bytes, bytes1.bytes)) return false; + + return true; + } + + @Override + public int hashCode() { + return Arrays.hashCode(bytes); + } +} + +class HEquations { + @NotNull final List<DirectionResultPair> results; + final boolean stable; + + HEquations(@NotNull List<DirectionResultPair> results, boolean stable) { + this.results = results; + this.stable = stable; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + HEquations that = (HEquations)o; + + if (stable != that.stable) return false; + if (!results.equals(that.results)) return false; + + return true; + } + + @Override + public int hashCode() { + int result = results.hashCode(); + result = 31 * result + (stable ? 1 : 0); + return result; + } +} + +class DirectionResultPair { + final int directionKey; + @NotNull + final HResult hResult; + + DirectionResultPair(int directionKey, @NotNull HResult hResult) { + this.directionKey = directionKey; + this.hResult = hResult; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + DirectionResultPair that = (DirectionResultPair)o; + + if (directionKey != that.directionKey) return false; + if (!hResult.equals(that.hResult)) return false; + + return true; + } + + @Override + public int hashCode() { + int result = directionKey; + result = 31 * result + hResult.hashCode(); + return result; + } +} + +interface HResult {} +final class HFinal implements HResult { + @NotNull final Value value; + + HFinal(@NotNull Value value) { + this.value = value; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + HFinal hFinal = (HFinal)o; + + if (value != hFinal.value) return false; + + return true; + } + + @Override + public int hashCode() { + return value.ordinal(); + } +} + +final class HPending implements HResult { + @NotNull final HComponent[] delta; + + HPending(@NotNull HComponent[] delta) { + this.delta = delta; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + HPending hPending = (HPending)o; + if (!Arrays.equals(delta, hPending.delta)) return false; + return true; + } + + @Override + public int hashCode() { + return Arrays.hashCode(delta); + } + + @NotNull + HPending copy() { + HComponent[] delta1 = new HComponent[delta.length]; + for (int i = 0; i < delta.length; i++) { + delta1[i] = delta[i].copy(); + + } + return new HPending(delta1); + } +}
\ No newline at end of file diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java index 625eb8eed977..a7c25782d48b 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Parameters.java @@ -15,6 +15,10 @@ */ package com.intellij.codeInspection.bytecodeAnalysis; +import com.intellij.codeInspection.bytecodeAnalysis.asm.ASMUtils; +import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph.Edge; +import com.intellij.codeInspection.bytecodeAnalysis.asm.RichControlFlow; +import org.jetbrains.annotations.NotNull; import org.jetbrains.org.objectweb.asm.Type; import org.jetbrains.org.objectweb.asm.tree.AbstractInsnNode; import org.jetbrains.org.objectweb.asm.tree.JumpInsnNode; @@ -25,7 +29,9 @@ import org.jetbrains.org.objectweb.asm.tree.analysis.BasicInterpreter; import org.jetbrains.org.objectweb.asm.tree.analysis.BasicValue; import org.jetbrains.org.objectweb.asm.tree.analysis.Frame; -import java.util.*; +import java.util.HashSet; +import java.util.List; +import java.util.Set; import static com.intellij.codeInspection.bytecodeAnalysis.AbstractValues.InstanceOfCheckValue; import static com.intellij.codeInspection.bytecodeAnalysis.AbstractValues.ParamValue; @@ -101,6 +107,18 @@ abstract class PResults { } } + static PResult combineNullable(PResult r1, PResult r2) throws AnalyzerException { + if (Identity == r1) return r2; + if (Identity == r2) return r1; + if (Return == r1) return r2; + if (Return == r2) return r1; + if (NPE == r1) return NPE; + if (NPE == r2) return NPE; + ConditionalNPE cnpe1 = (ConditionalNPE) r1; + ConditionalNPE cnpe2 = (ConditionalNPE) r2; + return new ConditionalNPE(join(cnpe1.sop, cnpe2.sop)); + } + static PResult join(PResult r1, PResult r2) throws AnalyzerException { if (Identity == r1) return r2; if (Identity == r2) return r1; @@ -127,34 +145,62 @@ abstract class PResults { } +interface PendingAction {} +class ProceedState implements PendingAction { + final State state; + + ProceedState(State state) { + this.state = state; + } +} +class MakeResult implements PendingAction { + final State state; + final PResult subResult; + final int[] indices; + + MakeResult(State state, PResult subResult, int[] indices) { + this.state = state; + this.subResult = subResult; + this.indices = indices; + } +} + class NonNullInAnalysis extends Analysis<PResult> { + private static final ThreadLocal<PendingAction[]> ourPending = new ThreadLocal<PendingAction[]>() { + @Override + protected PendingAction[] initialValue() { + return new PendingAction[Analysis.STEPS_LIMIT]; + } + }; + private static final ThreadLocal<PResult[]> ourResults = new ThreadLocal<PResult[]>() { + @Override + protected PResult[] initialValue() { + return new PResult[Analysis.STEPS_LIMIT]; + } + }; + + final private PendingAction[] pending = ourPending.get(); - private final NonNullInInterpreter interpreter = new NonNullInInterpreter(); + private final NotNullInterpreter interpreter = new NotNullInterpreter(); + private PResult[] results; + + // Flag saying that at some branch NPE was found. Used later as an evidence that this param is *NOT* @Nullable (optimization). + boolean possibleNPE; protected NonNullInAnalysis(RichControlFlow richControlFlow, Direction direction, boolean stable) { super(richControlFlow, direction, stable); + results = ourResults.get(); } - @Override - PResult identity() { - return Identity; - } - - @Override - PResult combineResults(PResult delta, List<PResult> subResults) throws AnalyzerException { - PResult subResult = Identity; - for (PResult sr : subResults) { - subResult = join(subResult, sr); + PResult combineResults(PResult delta, int[] subResults) throws AnalyzerException { + PResult result = Identity; + for (int subResult : subResults) { + result = join(result, results[subResult]); } - return meet(delta, subResult); + return meet(delta, result); } - @Override - boolean isEarlyResult(PResult result) { - return false; - } - - @Override + @NotNull Equation<Key, Value> mkEquation(PResult result) { if (Identity == result || Return == result) { return new Equation<Key, Value>(aKey, new Final<Key, Value>(Value.Top)); @@ -176,8 +222,73 @@ class NonNullInAnalysis extends Analysis<PResult> { private Frame<BasicValue> nextFrame = null; private PResult subResult = null; - @Override - void processState(State state) throws AnalyzerException { + @NotNull + protected Equation<Key, Value> analyze() throws AnalyzerException { + pendingPush(new ProceedState(createStartState())); + int steps = 0; + while (pendingTop > 0 && earlyResult == null) { + steps ++; + if (steps >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached, steps: " + steps + " in method " + method); + } + PendingAction action = pending[--pendingTop]; + if (action instanceof MakeResult) { + MakeResult makeResult = (MakeResult) action; + PResult result = combineResults(makeResult.subResult, makeResult.indices); + State state = makeResult.state; + int insnIndex = state.conf.insnIndex; + results[state.index] = result; + addComputed(insnIndex, state); + } + else if (action instanceof ProceedState) { + ProceedState proceedState = (ProceedState) action; + State state = proceedState.state; + int insnIndex = state.conf.insnIndex; + Conf conf = state.conf; + List<Conf> history = state.history; + + boolean fold = false; + if (dfsTree.loopEnters[insnIndex]) { + for (Conf prev : history) { + if (AbstractValues.isInstance(conf, prev)) { + fold = true; + break; + } + } + } + if (fold) { + results[state.index] = Identity; + addComputed(insnIndex, state); + } + else { + State baseState = null; + List<State> thisComputed = computed[insnIndex]; + if (thisComputed != null) { + for (State prevState : thisComputed) { + if (stateEquiv(state, prevState)) { + baseState = prevState; + break; + } + } + } + if (baseState != null) { + results[state.index] = results[baseState.index]; + } else { + // the main call + processState(state); + } + + } + } + } + if (earlyResult != null) { + return mkEquation(earlyResult); + } else { + return mkEquation(results[0]); + } + } + + private void processState(State state) throws AnalyzerException { int stateIndex = state.index; Conf conf = state.conf; int insnIndex = conf.insnIndex; @@ -185,15 +296,16 @@ class NonNullInAnalysis extends Analysis<PResult> { boolean taken = state.taken; Frame<BasicValue> frame = conf.frame; AbstractInsnNode insnNode = methodNode.instructions.get(insnIndex); - List<Conf> nextHistory = dfsTree.loopEnters.contains(insnIndex) ? append(history, conf) : history; + List<Conf> nextHistory = dfsTree.loopEnters[insnIndex] ? append(history, conf) : history; boolean hasCompanions = state.hasCompanions; execute(frame, insnNode); boolean notEmptySubResult = subResult != Identity; if (subResult == NPE) { - results.put(stateIndex, NPE); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + results[stateIndex] = NPE; + possibleNPE = true; + addComputed(insnIndex, state); return; } @@ -208,8 +320,8 @@ class NonNullInAnalysis extends Analysis<PResult> { if (!hasCompanions) { earlyResult = Return; } else { - results.put(stateIndex, Return); - computed.put(insnIndex, append(computed.get(insnIndex), state)); + results[stateIndex] = Return; + addComputed(insnIndex, state); } return; default: @@ -217,70 +329,265 @@ class NonNullInAnalysis extends Analysis<PResult> { if (opcode == ATHROW) { if (taken) { - results.put(stateIndex, NPE); + results[stateIndex] = NPE; + possibleNPE = true; } else { - results.put(stateIndex, Identity); + results[stateIndex] = Identity; } - computed.put(insnIndex, append(computed.get(insnIndex), state)); + addComputed(insnIndex, state); return; } if (opcode == IFNONNULL && popValue(frame) instanceof ParamValue) { int nextInsnIndex = insnIndex + 1; State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, hasCompanions || notEmptySubResult); - pending.push(new MakeResult<PResult>(state, subResult, new int[]{nextState.index})); - pending.push(new ProceedState<PResult>(nextState)); + pendingPush(new MakeResult(state, subResult, new int[]{nextState.index})); + pendingPush(new ProceedState(nextState)); return; } if (opcode == IFNULL && popValue(frame) instanceof ParamValue) { int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, hasCompanions || notEmptySubResult); - pending.push(new MakeResult<PResult>(state, subResult, new int[]{nextState.index})); - pending.push(new ProceedState<PResult>(nextState)); + pendingPush(new MakeResult(state, subResult, new int[]{nextState.index})); + pendingPush(new ProceedState(nextState)); return; } if (opcode == IFEQ && popValue(frame) == InstanceOfCheckValue) { int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, hasCompanions || notEmptySubResult); - pending.push(new MakeResult<PResult>(state, subResult, new int[]{nextState.index})); - pending.push(new ProceedState<PResult>(nextState)); + pendingPush(new MakeResult(state, subResult, new int[]{nextState.index})); + pendingPush(new ProceedState(nextState)); return; } if (opcode == IFNE && popValue(frame) == InstanceOfCheckValue) { int nextInsnIndex = insnIndex + 1; State nextState = new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, hasCompanions || notEmptySubResult); - pending.push(new MakeResult<PResult>(state, subResult, new int[]{nextState.index})); - pending.push(new ProceedState<PResult>(nextState)); + pendingPush(new MakeResult(state, subResult, new int[]{nextState.index})); + pendingPush(new ProceedState(nextState)); return; } // general case int[] nextInsnIndices = controlFlow.transitions[insnIndex]; - List<State> nextStates = new ArrayList<State>(nextInsnIndices.length); int[] subIndices = new int[nextInsnIndices.length]; - + for (int i = 0; i < nextInsnIndices.length; i++) { + subIndices[i] = ++id; + } + pendingPush(new MakeResult(state, subResult, subIndices)); for (int i = 0; i < nextInsnIndices.length; i++) { int nextInsnIndex = nextInsnIndices[i]; Frame<BasicValue> nextFrame1 = nextFrame; - if (controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { + if (controlFlow.errors[nextInsnIndex] && controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { nextFrame1 = new Frame<BasicValue>(frame); nextFrame1.clearStack(); - nextFrame1.push(new BasicValue(Type.getType("java/lang/Throwable"))); + nextFrame1.push(ASMUtils.THROWABLE_VALUE); + } + pendingPush(new ProceedState(new State(subIndices[i], new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, hasCompanions || notEmptySubResult))); + } + + } + + private int pendingTop = 0; + + private void pendingPush(PendingAction action) throws AnalyzerException { + if (pendingTop >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached in method " + method); + } + pending[pendingTop++] = action; + } + + private void execute(Frame<BasicValue> frame, AbstractInsnNode insnNode) throws AnalyzerException { + switch (insnNode.getType()) { + case AbstractInsnNode.LABEL: + case AbstractInsnNode.LINE: + case AbstractInsnNode.FRAME: + nextFrame = frame; + subResult = Identity; + break; + default: + nextFrame = new Frame<BasicValue>(frame); + interpreter.reset(); + nextFrame.execute(insnNode, interpreter); + subResult = interpreter.getSubResult(); + } + } +} + +class NullableInAnalysis extends Analysis<PResult> { + final private State[] pending = ourPendingStates.get(); + + private final NullableInterpreter interpreter = new NullableInterpreter(); + + protected NullableInAnalysis(RichControlFlow richControlFlow, Direction direction, boolean stable) { + super(richControlFlow, direction, stable); + } + + @NotNull + Equation<Key, Value> mkEquation(PResult result) { + if (NPE == result) { + return new Equation<Key, Value>(aKey, new Final<Key, Value>(Value.Top)); + } + if (Identity == result || Return == result) { + return new Equation<Key, Value>(aKey, new Final<Key, Value>(Value.Null)); + } + else { + ConditionalNPE condNpe = (ConditionalNPE) result; + Set<Product<Key, Value>> components = new HashSet<Product<Key, Value>>(); + for (Set<Key> prod : condNpe.sop) { + components.add(new Product<Key, Value>(Value.Top, prod)); + } + return new Equation<Key, Value>(aKey, new Pending<Key, Value>(components)); + } + } + + private int id = 0; + private Frame<BasicValue> nextFrame = null; + private PResult myResult = Identity; + private PResult subResult = Identity; + private boolean top = false; + + @NotNull + protected Equation<Key, Value> analyze() throws AnalyzerException { + pendingPush(createStartState()); + int steps = 0; + while (pendingTop > 0 && earlyResult == null) { + steps ++; + if (steps >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached, steps: " + steps + " in method " + method); + } + State state = pending[--pendingTop]; + int insnIndex = state.conf.insnIndex; + Conf conf = state.conf; + List<Conf> history = state.history; + + boolean fold = false; + if (dfsTree.loopEnters[insnIndex]) { + for (Conf prev : history) { + if (AbstractValues.isInstance(conf, prev)) { + fold = true; + break; + } + } + } + if (fold) { + addComputed(insnIndex, state); + } + else { + State baseState = null; + List<State> thisComputed = computed[insnIndex]; + if (thisComputed != null) { + for (State prevState : thisComputed) { + if (stateEquiv(state, prevState)) { + baseState = prevState; + break; + } + } + } + if (baseState == null) { + processState(state); + } } - nextStates.add(new State(++id, new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, hasCompanions || notEmptySubResult)); - subIndices[i] = (id); + } + if (earlyResult != null) { + return mkEquation(earlyResult); + } else { + return mkEquation(myResult); + } + } + + private void processState(State state) throws AnalyzerException { + Conf conf = state.conf; + int insnIndex = conf.insnIndex; + List<Conf> history = state.history; + boolean taken = state.taken; + Frame<BasicValue> frame = conf.frame; + AbstractInsnNode insnNode = methodNode.instructions.get(insnIndex); + List<Conf> nextHistory = dfsTree.loopEnters[insnIndex] ? append(history, conf) : history; + + addComputed(insnIndex, state); + execute(frame, insnNode); + + if (subResult == NPE || top) { + earlyResult = NPE; + return; + } + + if (subResult instanceof ConditionalNPE) { + myResult = combineNullable(myResult, subResult); + } + + int opcode = insnNode.getOpcode(); + switch (opcode) { + case ARETURN: + if (popValue(frame) instanceof ParamValue) { + earlyResult = NPE; + } + return; + case IRETURN: + case LRETURN: + case FRETURN: + case DRETURN: + case RETURN: + return; + default: + } + + if (opcode == ATHROW) { + if (taken) { + earlyResult = NPE; + } + return; + } + + if (opcode == IFNONNULL && popValue(frame) instanceof ParamValue) { + int nextInsnIndex = insnIndex + 1; + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false)); + return; + } + + if (opcode == IFNULL && popValue(frame) instanceof ParamValue) { + int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false)); + return; + } + + if (opcode == IFEQ && popValue(frame) == InstanceOfCheckValue) { + int nextInsnIndex = methodNode.instructions.indexOf(((JumpInsnNode)insnNode).label); + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false)); + return; } - pending.push(new MakeResult<PResult>(state, subResult, subIndices)); - for (State nextState : nextStates) { - pending.push(new ProceedState<PResult>(nextState)); + if (opcode == IFNE && popValue(frame) == InstanceOfCheckValue) { + int nextInsnIndex = insnIndex + 1; + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame), nextHistory, true, false)); + return; + } + + // general case + for (int nextInsnIndex : controlFlow.transitions[insnIndex]) { + Frame<BasicValue> nextFrame1 = nextFrame; + if (controlFlow.errors[nextInsnIndex] && controlFlow.errorTransitions.contains(new Edge(insnIndex, nextInsnIndex))) { + nextFrame1 = new Frame<BasicValue>(frame); + nextFrame1.clearStack(); + nextFrame1.push(ASMUtils.THROWABLE_VALUE); + } + pendingPush(new State(++id, new Conf(nextInsnIndex, nextFrame1), nextHistory, taken, false)); } } + private int pendingTop = 0; + + private void pendingPush(State state) throws AnalyzerException { + if (pendingTop >= STEPS_LIMIT) { + throw new AnalyzerException(null, "limit is reached in method " + method); + } + pending[pendingTop++] = state; + } + private void execute(Frame<BasicValue> frame, AbstractInsnNode insnNode) throws AnalyzerException { switch (insnNode.getType()) { case AbstractInsnNode.LABEL: @@ -288,23 +595,37 @@ class NonNullInAnalysis extends Analysis<PResult> { case AbstractInsnNode.FRAME: nextFrame = frame; subResult = Identity; + top = false; break; default: nextFrame = new Frame<BasicValue>(frame); interpreter.reset(); nextFrame.execute(insnNode, interpreter); subResult = interpreter.getSubResult(); + top = interpreter.top; } } } -class NonNullInInterpreter extends BasicInterpreter { +abstract class NullityInterpreter extends BasicInterpreter { + boolean top = false; + final boolean nullableAnalysis; + final int nullityMask; private PResult subResult = Identity; + + NullityInterpreter(boolean nullableAnalysis, int nullityMask) { + this.nullableAnalysis = nullableAnalysis; + this.nullityMask = nullityMask; + } + + abstract PResult combine(PResult res1, PResult res2) throws AnalyzerException; + public PResult getSubResult() { return subResult; } void reset() { subResult = Identity; + top = false; } @Override @@ -344,10 +665,17 @@ class NonNullInInterpreter extends BasicInterpreter { case BALOAD: case CALOAD: case SALOAD: + if (value1 instanceof ParamValue) { + subResult = NPE; + } + break; case PUTFIELD: if (value1 instanceof ParamValue) { subResult = NPE; } + if (nullableAnalysis && value2 instanceof ParamValue) { + subResult = NPE; + } break; default: } @@ -361,13 +689,21 @@ class NonNullInInterpreter extends BasicInterpreter { case LASTORE: case FASTORE: case DASTORE: - case AASTORE: case BASTORE: case CASTORE: case SASTORE: if (value1 instanceof ParamValue) { subResult = NPE; } + break; + case AASTORE: + if (value1 instanceof ParamValue) { + subResult = NPE; + } + if (nullableAnalysis && value3 instanceof ParamValue) { + subResult = NPE; + } + break; default: } return super.ternaryOperation(insn, value1, value2, value3); @@ -382,20 +718,54 @@ class NonNullInInterpreter extends BasicInterpreter { subResult = NPE; } switch (opcode) { + case INVOKEINTERFACE: + if (nullableAnalysis) { + for (int i = shift; i < values.size(); i++) { + if (values.get(i) instanceof ParamValue) { + top = true; + return super.naryOperation(insn, values); + } + } + } + break; case INVOKESTATIC: case INVOKESPECIAL: case INVOKEVIRTUAL: - case INVOKEINTERFACE: boolean stable = opcode == INVOKESTATIC || opcode == INVOKESPECIAL; MethodInsnNode methodNode = (MethodInsnNode) insn; + Method method = new Method(methodNode.owner, methodNode.name, methodNode.desc); for (int i = shift; i < values.size(); i++) { if (values.get(i) instanceof ParamValue) { - Method method = new Method(methodNode.owner, methodNode.name, methodNode.desc); - subResult = meet(subResult, new ConditionalNPE(new Key(method, new In(i - shift), stable))); + subResult = combine(subResult, new ConditionalNPE(new Key(method, new In(i - shift, nullityMask), stable))); } } + break; default: } return super.naryOperation(insn, values); } } + +class NotNullInterpreter extends NullityInterpreter { + + NotNullInterpreter() { + super(false, In.NOT_NULL); + } + + @Override + PResult combine(PResult res1, PResult res2) throws AnalyzerException { + return meet(res1, res2); + } +} + +class NullableInterpreter extends NullityInterpreter { + + NullableInterpreter() { + super(true, In.NULLABLE); + } + + @Override + PResult combine(PResult res1, PResult res2) throws AnalyzerException { + return join(res1, res2); + } +} 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 index 23d9d5a9e1c5..aa44951961ad 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ProjectBytecodeAnalysis.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/ProjectBytecodeAnalysis.java @@ -30,16 +30,14 @@ import com.intellij.psi.util.CachedValueProvider; import com.intellij.psi.util.CachedValuesManager; import com.intellij.psi.util.PsiFormatUtil; import com.intellij.util.IncorrectOperationException; -import com.intellij.util.containers.LongStack; +import com.intellij.util.containers.Stack; import com.intellij.util.indexing.FileBasedIndex; -import gnu.trove.TLongArrayList; -import gnu.trove.TLongHashSet; -import gnu.trove.TLongObjectHashMap; import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.Nullable; -import java.io.IOException; -import java.util.List; +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.util.*; /** * @author lambdamix @@ -63,7 +61,7 @@ public class ProjectBytecodeAnalysis { if (!(listOwner instanceof PsiCompiledElement)) { return null; } - if (annotationFQN.equals(AnnotationUtil.NOT_NULL) || annotationFQN.equals(ControlFlowAnalyzer.ORG_JETBRAINS_ANNOTATIONS_CONTRACT)) { + if (annotationFQN.equals(AnnotationUtil.NOT_NULL) || annotationFQN.equals(AnnotationUtil.NULLABLE) || annotationFQN.equals(ControlFlowAnalyzer.ORG_JETBRAINS_ANNOTATIONS_CONTRACT)) { PsiAnnotation[] annotations = findInferredAnnotations(listOwner); for (PsiAnnotation annotation : annotations) { if (annotationFQN.equals(annotation.getQualifiedName())) { @@ -94,37 +92,45 @@ public class ProjectBytecodeAnalysis { @NotNull private PsiAnnotation[] collectInferredAnnotations(PsiModifierListOwner listOwner) { try { - long ownerKey = getKey(listOwner); - if (ownerKey == -1) { + MessageDigest md = BytecodeAnalysisConverter.getMessageDigest(); + HKey primaryKey = getKey(listOwner, md); + if (primaryKey == null) { return PsiAnnotation.EMPTY_ARRAY; } - TLongArrayList allKeys = contractKeys(listOwner, ownerKey); - Annotations annotations = loadAnnotations(listOwner, ownerKey, allKeys); - boolean notNull = annotations.notNulls.contains(ownerKey); - String contractValue = annotations.contracts.get(ownerKey); - - 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; + if (listOwner instanceof PsiMethod) { + ArrayList<HKey> allKeys = contractKeys((PsiMethod)listOwner, primaryKey); + MethodAnnotations methodAnnotations = loadMethodAnnotations((PsiMethod)listOwner, primaryKey, allKeys); + boolean notNull = methodAnnotations.notNulls.contains(primaryKey); + String contractValue = methodAnnotations.contracts.get(primaryKey); + 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 if (listOwner instanceof PsiParameter) { + ParameterAnnotations parameterAnnotations = loadParameterAnnotations(primaryKey); + if (parameterAnnotations.notNull) { + return new PsiAnnotation[]{ + getNotNullAnnotation() + }; + } + else if (parameterAnnotations.nullable) { + return new PsiAnnotation[]{ + getNullableAnnotation() + }; + } } - } - catch (IOException e) { - LOG.debug(e); return PsiAnnotation.EMPTY_ARRAY; } catch (EquationsLimitException e) { @@ -132,6 +138,10 @@ public class ProjectBytecodeAnalysis { LOG.info("Too many equations for " + externalName); return PsiAnnotation.EMPTY_ARRAY; } + catch (NoSuchAlgorithmException e) { + LOG.error(e); + return PsiAnnotation.EMPTY_ARRAY; + } } private PsiAnnotation getNotNullAnnotation() { @@ -144,14 +154,25 @@ public class ProjectBytecodeAnalysis { }); } + private PsiAnnotation getNullableAnnotation() { + return CachedValuesManager.getManager(myProject).getCachedValue(myProject, new CachedValueProvider<PsiAnnotation>() { + @Nullable + @Override + public Result<PsiAnnotation> compute() { + return Result.create(createAnnotationFromText("@" + AnnotationUtil.NULLABLE), ModificationTracker.NEVER_CHANGED); + } + }); + } + public PsiAnnotation createContractAnnotation(String contractValue) { return createAnnotationFromText("@org.jetbrains.annotations.Contract(" + contractValue + ")"); } - public static long getKey(@NotNull PsiModifierListOwner owner) throws IOException { + @Nullable + public static HKey getKey(@NotNull PsiModifierListOwner owner, MessageDigest md) { LOG.assertTrue(owner instanceof PsiCompiledElement, owner); if (owner instanceof PsiMethod) { - return BytecodeAnalysisConverter.getInstance().mkPsiKey((PsiMethod)owner, new Out()); + return BytecodeAnalysisConverter.psiKey((PsiMethod)owner, new Out(), md); } if (owner instanceof PsiParameter) { PsiElement parent = owner.getParent(); @@ -159,80 +180,93 @@ public class ProjectBytecodeAnalysis { 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 BytecodeAnalysisConverter.psiKey((PsiMethod)gParent, new In(index, In.NOT_NULL), md); } } } - - return -1; + return null; } - public static TLongArrayList contractKeys(@NotNull PsiModifierListOwner owner, long primaryKey) throws IOException { - if (owner instanceof PsiMethod) { - TLongArrayList result = BytecodeAnalysisConverter.getInstance().mkInOutKeys((PsiMethod)owner, primaryKey); - result.add(primaryKey); - return result; - } - TLongArrayList result = new TLongArrayList(1); + public static ArrayList<HKey> contractKeys(@NotNull PsiMethod owner, HKey primaryKey) { + ArrayList<HKey> result = BytecodeAnalysisConverter.mkInOutKeys(owner, primaryKey); result.add(primaryKey); return result; } - private Annotations loadAnnotations(@NotNull PsiModifierListOwner owner, long key, TLongArrayList allKeys) - throws IOException, EquationsLimitException { - Annotations result = new Annotations(); - if (owner instanceof PsiParameter) { - final Solver solver = new Solver(new ELattice<Value>(Value.NotNull, Value.Top)); - collectEquations(allKeys, solver); - TLongObjectHashMap<Value> solutions = solver.solve(); - BytecodeAnalysisConverter.getInstance().addParameterAnnotations(solutions, result); - } else if (owner instanceof PsiMethod) { - final Solver solver = new Solver(new ELattice<Value>(Value.Bot, Value.Top)); - collectEquations(allKeys, solver); - TLongObjectHashMap<Value> solutions = solver.solve(); - BytecodeAnalysisConverter.getInstance().addMethodAnnotations(solutions, result, key, - ((PsiMethod)owner).getParameterList().getParameters().length); - } + private ParameterAnnotations loadParameterAnnotations(@NotNull HKey notNullKey) + throws EquationsLimitException { + + final Solver notNullSolver = new Solver(new ELattice<Value>(Value.NotNull, Value.Top)); + collectEquations(Collections.singletonList(notNullKey), notNullSolver); + + HashMap<HKey, Value> notNullSolutions = notNullSolver.solve(); + boolean notNull = + (Value.NotNull == notNullSolutions.get(notNullKey)) || (Value.NotNull == notNullSolutions.get(notNullKey.mkUnstable())); + + final Solver nullableSolver = new Solver(new ELattice<Value>(Value.Null, Value.Top)); + final HKey nullableKey = new HKey(notNullKey.key, notNullKey.dirKey + 1, true); + collectEquations(Collections.singletonList(nullableKey), nullableSolver); + HashMap<HKey, Value> nullableSolutions = nullableSolver.solve(); + boolean nullable = + (Value.Null == nullableSolutions.get(nullableKey)) || (Value.Null == nullableSolutions.get(nullableKey.mkUnstable())); + return new ParameterAnnotations(notNull, nullable); + } + + private MethodAnnotations loadMethodAnnotations(@NotNull PsiMethod owner, @NotNull HKey key, ArrayList<HKey> allKeys) + throws EquationsLimitException { + MethodAnnotations result = new MethodAnnotations(); + final Solver solver = new Solver(new ELattice<Value>(Value.Bot, Value.Top)); + collectEquations(allKeys, solver); + HashMap<HKey, Value> solutions = solver.solve(); + int arity = owner.getParameterList().getParameters().length; + BytecodeAnalysisConverter.addMethodAnnotations(solutions, result, key, arity); return result; } - private void collectEquations(TLongArrayList keys, Solver solver) throws EquationsLimitException { + private void collectEquations(List<HKey> keys, Solver solver) throws EquationsLimitException { GlobalSearchScope librariesScope = ProjectScope.getLibrariesScope(myProject); - TLongHashSet queued = new TLongHashSet(); - LongStack queue = new LongStack(); + HashSet<HKey> queued = new HashSet<HKey>(); + Stack<HKey> queue = new Stack<HKey>(); - for (int i = 0; i < keys.size(); i++) { - long key = keys.get(i); + for (HKey key : keys) { queue.push(key); queued.add(key); - // stable/unstable - queue.push(-key); - queued.add(-key); } + HashMap<Bytes, List<HEquations>> cache = new HashMap<Bytes, List<HEquations>>(); FileBasedIndex index = FileBasedIndex.getInstance(); + while (!queue.empty()) { if (queued.size() > EQUATIONS_LIMIT) { throw new EquationsLimitException(); } ProgressManager.checkCanceled(); - List<IdEquation> equations = index.getValues(BytecodeAnalysisIndex.NAME, queue.pop(), librariesScope); - for (IdEquation equation : equations) { - IdResult rhs = equation.rhs; - solver.addEquation(equation); - if (rhs instanceof IdPending) { - IdPending intIdPending = (IdPending)rhs; - for (IntIdComponent component : intIdPending.delta) { - for (long depKey : component.ids) { - if (!queued.contains(depKey)) { - queue.push(depKey); - queued.add(depKey); - } - // stable/unstable - long swapped = -depKey; - if (!queued.contains(swapped)) { - queue.push(swapped); - queued.add(swapped); + HKey hKey = queue.pop(); + Bytes bytes = new Bytes(hKey.key); + + List<HEquations> hEquationss = cache.get(bytes); + if (hEquationss == null) { + hEquationss = index.getValues(BytecodeAnalysisIndex.NAME, bytes, librariesScope); + cache.put(bytes, hEquationss); + } + + for (HEquations hEquations : hEquationss) { + boolean stable = hEquations.stable; + for (DirectionResultPair pair : hEquations.results) { + int dirKey = pair.directionKey; + if (dirKey == hKey.dirKey) { + HResult result = pair.hResult; + + solver.addEquation(new HEquation(new HKey(bytes.bytes, dirKey, stable), result)); + if (result instanceof HPending) { + HPending pending = (HPending)result; + for (HComponent component : pending.delta) { + for (HKey depKey : component.ids) { + if (!queued.contains(depKey)) { + queue.push(depKey); + queued.add(depKey); + } + } } } } @@ -249,11 +283,21 @@ public class ProjectBytecodeAnalysis { } } -class Annotations { +class MethodAnnotations { // @NotNull keys - final TLongHashSet notNulls = new TLongHashSet(); + final HashSet<HKey> notNulls = new HashSet<HKey>(); // @Contracts - final TLongObjectHashMap<String> contracts = new TLongObjectHashMap<String>(); + final HashMap<HKey, String> contracts = new HashMap<HKey, String>(); +} + +class ParameterAnnotations { + final boolean notNull; + final boolean nullable; + + ParameterAnnotations(boolean notNull, boolean nullable) { + this.notNull = notNull; + this.nullable = nullable; + } } class EquationsLimitException extends Exception {} 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 index 1dec1de8a606..21e749e12b29 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java @@ -15,10 +15,8 @@ */ package com.intellij.codeInspection.bytecodeAnalysis; -import com.intellij.util.containers.LongStack; -import gnu.trove.TLongHashSet; -import gnu.trove.TLongIterator; -import gnu.trove.TLongObjectHashMap; +import com.intellij.util.ArrayFactory; +import com.intellij.util.ArrayUtil; import org.jetbrains.annotations.NotNull; import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException; @@ -48,88 +46,6 @@ final class ELattice<T extends Enum<T>> { } } -// component specialized for ints -final class IntIdComponent { - Value value; - final long[] ids; - - IntIdComponent(Value value, long[] 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(long 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 long nullId = 0; - - static boolean contains(long[] ids, int id) { - for (long id1 : ids) { - if (id1 == id) return true; - } - - return false; - } - - static boolean isEmpty(long[] ids) { - for (long 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(long[] ids, long 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; @@ -183,6 +99,55 @@ class ResultUtil<Id, T extends Enum<T>> { } } +class HResultUtil { + private static final HKey[] EMPTY_PRODUCT = new HKey[0]; + private static final ArrayFactory<HComponent> HCOMPONENT_ARRAY_FACTORY = new ArrayFactory<HComponent>() { + @NotNull + @Override + public HComponent[] create(int count) { + return new HComponent[count]; + } + }; + private final ELattice<Value> lattice; + final Value top; + + HResultUtil(ELattice<Value> lattice) { + this.lattice = lattice; + top = lattice.top; + } + + HResult join(HResult r1, HResult r2) { + if (r1 instanceof HFinal && ((HFinal) r1).value == top) { + return r1; + } + if (r2 instanceof HFinal && ((HFinal) r2).value == top) { + return r2; + } + if (r1 instanceof HFinal && r2 instanceof HFinal) { + return new HFinal(lattice.join(((HFinal) r1).value, ((HFinal) r2).value)); + } + if (r1 instanceof HFinal && r2 instanceof HPending) { + HFinal f1 = (HFinal)r1; + HPending pending = (HPending) r2; + HComponent[] delta = new HComponent[pending.delta.length + 1]; + delta[0] = new HComponent(f1.value, EMPTY_PRODUCT); + System.arraycopy(pending.delta, 0, delta, 1, pending.delta.length); + return new HPending(delta); + } + if (r1 instanceof HPending && r2 instanceof HFinal) { + HFinal f2 = (HFinal)r2; + HPending pending = (HPending) r1; + HComponent[] delta = new HComponent[pending.delta.length + 1]; + delta[0] = new HComponent(f2.value, EMPTY_PRODUCT); + System.arraycopy(pending.delta, 0, delta, 1, pending.delta.length); + return new HPending(delta); + } + HPending pending1 = (HPending) r1; + HPending pending2 = (HPending) r2; + return new HPending(ArrayUtil.mergeArrays(pending1.delta, pending2.delta, HCOMPONENT_ARRAY_FACTORY)); + } +} + final class Product<K, V> { @NotNull final V value; @NotNull final Set<K> ids; @@ -235,195 +200,150 @@ final class Pending<Id, T> implements Result<Id, T> { } -interface IdResult {} -// this just wrapper, no need for this really -final class IdFinal implements IdResult { - final Value value; - public IdFinal(Value value) { - this.value = value; - } - - @Override - public boolean equals(Object o) { - if (this == o) return true; - if (o == null || getClass() != o.getClass()) return false; - - IdFinal that = (IdFinal)o; - - if (value != that.value) return false; - - return true; - } - - @Override - public int hashCode() { - return value.ordinal(); - } +final class Solution<Id, Val> { + final Id id; + final Val value; - @Override - public String toString() { - return super.toString(); + Solution(Id id, Val value) { + this.id = id; + this.value = value; } } -final class IdPending implements IdResult { - final IntIdComponent[] delta; - - IdPending(IntIdComponent[] delta) { - this.delta = delta; - } +final class Equation<Id, T> { + final Id id; + final Result<Id, T> rhs; - @Override - public boolean equals(Object o) { - if (this == o) return true; - if (!(o instanceof IdPending)) return false; - IdPending pending = (IdPending)o; - return Arrays.equals(delta, pending.delta); + Equation(Id id, Result<Id, T> rhs) { + this.id = id; + this.rhs = rhs; } @Override - public int hashCode() { - return Arrays.hashCode(delta); - } - - IdPending copy() { - IntIdComponent[] delta1 = new IntIdComponent[delta.length]; - for (int i = 0; i < delta.length; i++) { - delta1[i] = delta[i].copy(); - } - return new IdPending(delta1); + public String toString() { + return "Equation{" + "id=" + id + ", rhs=" + rhs + '}'; } } -final class IdEquation { - final long id; - final IdResult rhs; +final class CoreHKey { + @NotNull + final byte[] key; + final int dirKey; - IdEquation(long id, IdResult rhs) { - this.id = id; - this.rhs = rhs; + CoreHKey(@NotNull byte[] key, int dirKey) { + this.key = key; + this.dirKey = dirKey; } @Override public boolean equals(Object o) { if (this == o) return true; - if (!(o instanceof IdEquation)) return false; - - IdEquation equation = (IdEquation)o; + if (o == null || getClass() != o.getClass()) return false; - if (id != equation.id) return false; - if (!rhs.equals(equation.rhs)) return false; + CoreHKey coreHKey = (CoreHKey)o; + if (dirKey != coreHKey.dirKey) return false; + if (!Arrays.equals(key, coreHKey.key)) return false; return true; } @Override public int hashCode() { - return 31 * ((int)(id ^ (id >>> 32))) + rhs.hashCode(); - } -} - -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 + '}'; + int result = Arrays.hashCode(key); + result = 31 * result + dirKey; + return result; } } final class Solver { - private int size = 0; private final ELattice<Value> lattice; - private final TLongObjectHashMap<TLongHashSet> dependencies = new TLongObjectHashMap<TLongHashSet>(); - private final TLongObjectHashMap<IdPending> pending = new TLongObjectHashMap<IdPending>(); - private final TLongObjectHashMap<Value> solved = new TLongObjectHashMap<Value>(); - private final LongStack moving = new LongStack(); + private final HashMap<HKey, HashSet<HKey>> dependencies = new HashMap<HKey, HashSet<HKey>>(); + private final HashMap<HKey, HPending> pending = new HashMap<HKey, HPending>(); + private final HashMap<HKey, Value> solved = new HashMap<HKey, Value>(); + private final Stack<HKey> moving = new Stack<HKey>(); - int getSize() { - return size; - } + private final HResultUtil resultUtil; + private final HashMap<CoreHKey, HEquation> equations = new HashMap<CoreHKey, HEquation>(); Solver(ELattice<Value> lattice) { this.lattice = lattice; + resultUtil = new HResultUtil(lattice); + } + + void addEquation(HEquation equation) { + HKey key = equation.key; + CoreHKey coreKey = new CoreHKey(key.key, key.dirKey); + + HEquation previousEquation = equations.get(coreKey); + if (previousEquation == null) { + equations.put(coreKey, equation); + } else { + HKey joinKey = new HKey(coreKey.key, coreKey.dirKey, equation.key.stable && previousEquation.key.stable); + HResult joinResult = resultUtil.join(equation.result, previousEquation.result); + HEquation joinEquation = new HEquation(joinKey, joinResult); + equations.put(coreKey, joinEquation); + } } - void addEquation(IdEquation equation) { - size ++; - IdResult rhs = equation.rhs; - if (rhs instanceof IdFinal) { - solved.put(equation.id, ((IdFinal) rhs).value); - moving.push(equation.id); - } else if (rhs instanceof IdPending) { - IdPending pendResult = ((IdPending)rhs).copy(); - IdResult norm = normalize(pendResult.delta); - if (norm instanceof IdFinal) { - solved.put(equation.id, ((IdFinal) norm).value); - moving.push(equation.id); + void queueEquation(HEquation equation) { + HResult rhs = equation.result; + if (rhs instanceof HFinal) { + solved.put(equation.key, ((HFinal) rhs).value); + moving.push(equation.key); + } else if (rhs instanceof HPending) { + HPending pendResult = ((HPending)rhs).copy(); + HResult norm = normalize(pendResult.delta); + if (norm instanceof HFinal) { + solved.put(equation.key, ((HFinal) norm).value); + moving.push(equation.key); } else { - IdPending pendResult1 = ((IdPending)rhs).copy(); - for (IntIdComponent component : pendResult1.delta) { - for (long trigger : component.ids) { - TLongHashSet set = dependencies.get(trigger); + HPending pendResult1 = ((HPending)rhs).copy(); + for (HComponent component : pendResult1.delta) { + for (HKey trigger : component.ids) { + HashSet<HKey> set = dependencies.get(trigger); if (set == null) { - set = new TLongHashSet(); + set = new HashSet<HKey>(); dependencies.put(trigger, set); } - set.add(equation.id); + set.add(equation.key); } - pending.put(equation.id, pendResult1); + pending.put(equation.key, pendResult1); } } } } - TLongObjectHashMap<Value> solve() { + HashMap<HKey, Value> solve() { + for (HEquation hEquation : equations.values()) { + queueEquation(hEquation); + } while (!moving.empty()) { - long id = moving.pop(); + HKey id = moving.pop(); Value value = solved.get(id); - boolean stable = id > 0; - long[] pIds = stable ? new long[]{id, -id} : new long[]{-id, id}; - Value[] pVals = stable ? new Value[]{value, value} : new Value[]{value, lattice.top}; + HKey[] pIds = id.stable ? new HKey[]{id, id.negate()} : new HKey[]{id.negate(), id}; + Value[] pVals = id.stable ? new Value[]{value, value} : new Value[]{value, lattice.top}; for (int i = 0; i < pIds.length; i++) { - long pId = pIds[i]; + HKey pId = pIds[i]; Value pVal = pVals[i]; - TLongHashSet dIds = dependencies.get(pId); + HashSet<HKey> dIds = dependencies.get(pId); if (dIds == null) { continue; } - TLongIterator dIdsIterator = dIds.iterator(); - while (dIdsIterator.hasNext()) { - long dId = dIdsIterator.next(); - IdPending pend = pending.remove(dId); + for (HKey dId : dIds) { + HPending pend = pending.remove(dId); if (pend != null) { - IdResult pend1 = substitute(pend, pId, pVal); - if (pend1 instanceof IdFinal) { - IdFinal fi = (IdFinal)pend1; + HResult pend1 = substitute(pend, pId, pVal); + if (pend1 instanceof HFinal) { + HFinal fi = (HFinal)pend1; solved.put(dId, fi.value); moving.push(dId); } else { - pending.put(dId, (IdPending)pend1); + pending.put(dId, (HPending)pend1); } } } @@ -434,9 +354,9 @@ final class Solver { } // substitute id -> value into pending - IdResult substitute(IdPending pending, long id, Value value) { - IntIdComponent[] sum = pending.delta; - for (IntIdComponent intIdComponent : sum) { + HResult substitute(@NotNull HPending pending, @NotNull HKey id, @NotNull Value value) { + HComponent[] sum = pending.delta; + for (HComponent intIdComponent : sum) { if (intIdComponent.remove(id)) { intIdComponent.value = lattice.meet(intIdComponent.value, value); } @@ -444,17 +364,17 @@ final class Solver { return normalize(sum); } - IdResult normalize(IntIdComponent[] sum) { + @NotNull HResult normalize(@NotNull HComponent[] sum) { Value acc = lattice.bot; boolean computableNow = true; - for (IntIdComponent prod : sum) { + for (HComponent prod : sum) { if (prod.isEmpty() || prod.value == lattice.bot) { acc = lattice.join(acc, prod.value); } else { computableNow = false; } } - return (acc == lattice.top || computableNow) ? new IdFinal(acc) : new IdPending(sum); + return (acc == lattice.top || computableNow) ? new HFinal(acc) : new HPending(sum); } } diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/ASMUtils.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/ASMUtils.java new file mode 100644 index 000000000000..a6bfdc38732e --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/ASMUtils.java @@ -0,0 +1,57 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import org.jetbrains.org.objectweb.asm.Type; +import org.jetbrains.org.objectweb.asm.tree.analysis.BasicValue; + +/** + * @author lambdamix + */ +public class ASMUtils { + public static final Type THROWABLE_TYPE = Type.getType("java/lang/Throwable"); + public static final BasicValue THROWABLE_VALUE = new BasicValue(THROWABLE_TYPE); + + public static boolean isReferenceType(Type tp) { + int sort = tp.getSort(); + return sort == Type.OBJECT || sort == Type.ARRAY; + } + + public static boolean isBooleanType(Type tp) { + return Type.BOOLEAN_TYPE.equals(tp); + } + + public static int getSizeFast(String desc) { + switch (desc.charAt(0)) { + case 'J': + case 'D': + return 2; + default: + return 1; + } + } + + public static int getReturnSizeFast(String methodDesc) { + switch (methodDesc.charAt(methodDesc.indexOf(')') + 1)) { + case 'J': + case 'D': + return 2; + default: + return 1; + } + } + +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/ControlFlowGraph.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/ControlFlowGraph.java new file mode 100644 index 000000000000..40a730190d2e --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/ControlFlowGraph.java @@ -0,0 +1,174 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph.Edge; +import gnu.trove.TIntArrayList; +import org.jetbrains.org.objectweb.asm.tree.MethodNode; +import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException; + +import java.util.HashSet; +import java.util.Set; + +/** + * @author lambdamix + */ +public final class ControlFlowGraph { + public static final class Edge { + public final int from, to; + + public 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; + } + } + + public final String className; + public final MethodNode methodNode; + public final int[][] transitions; + public final int edgeCount; + public final boolean[] errors; + public final Set<Edge> errorTransitions; + + ControlFlowGraph(String className, MethodNode methodNode, int[][] transitions, int edgeCount, boolean[] errors, Set<Edge> errorTransitions) { + this.className = className; + this.methodNode = methodNode; + this.transitions = transitions; + this.edgeCount = edgeCount; + this.errors = errors; + this.errorTransitions = errorTransitions; + } + + public static ControlFlowGraph build(String className, MethodNode methodNode, boolean jsr) throws AnalyzerException { + return jsr ? new ControlFlowBuilder(className, methodNode).buildCFG() : new LiteControlFlowBuilder(className, methodNode).buildCFG(); + } +} + +final class ControlFlowBuilder extends FramelessAnalyzer { + final String className; + final MethodNode methodNode; + final TIntArrayList[] transitions; + final Set<ControlFlowGraph.Edge> errorTransitions; + private final boolean[] errors; + private int edgeCount; + + ControlFlowBuilder(String className, MethodNode methodNode) { + this.className = className; + this.methodNode = methodNode; + transitions = new TIntArrayList[methodNode.instructions.size()]; + errors = new boolean[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, edgeCount, errors, errorTransitions); + } + + @Override + protected final void newControlFlowEdge(int insn, int successor) { + if (!transitions[insn].contains(successor)) { + transitions[insn].add(successor); + edgeCount++; + } + } + + @Override + protected final boolean newControlFlowExceptionEdge(int insn, int successor) { + if (!transitions[insn].contains(successor)) { + transitions[insn].add(successor); + edgeCount++; + errorTransitions.add(new Edge(insn, successor)); + errors[successor] = true; + } + return true; + } +} + +final class LiteControlFlowBuilder extends LiteFramelessAnalyzer { + final String className; + final MethodNode methodNode; + final TIntArrayList[] transitions; + final Set<ControlFlowGraph.Edge> errorTransitions; + private final boolean[] errors; + private int edgeCount; + + LiteControlFlowBuilder(String className, MethodNode methodNode) { + this.className = className; + this.methodNode = methodNode; + transitions = new TIntArrayList[methodNode.instructions.size()]; + errors = new boolean[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, edgeCount, errors, errorTransitions); + } + + @Override + protected final void newControlFlowEdge(int insn, int successor) { + if (!transitions[insn].contains(successor)) { + transitions[insn].add(successor); + edgeCount++; + } + } + + @Override + protected final boolean newControlFlowExceptionEdge(int insn, int successor) { + if (!transitions[insn].contains(successor)) { + transitions[insn].add(successor); + edgeCount++; + errorTransitions.add(new Edge(insn, successor)); + errors[successor] = true; + } + return true; + } +} + diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/DFSTree.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/DFSTree.java new file mode 100644 index 000000000000..85bc13fbda96 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/DFSTree.java @@ -0,0 +1,134 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph.Edge; + +import java.util.HashSet; +import java.util.Set; + +/** + * @author lambdamix + */ +public final class DFSTree { + public final int[] preOrder, postOrder; + public final Set<Edge> nonBack, back; + public final boolean[] loopEnters; + + DFSTree(int[] preOrder, + int[] postOrder, + Set<Edge> nonBack, + Set<Edge> back, + boolean[] loopEnters) { + this.preOrder = preOrder; + this.postOrder = postOrder; + this.nonBack = nonBack; + this.back = back; + this.loopEnters = loopEnters; + } + + public final boolean isDescendant(int child, int parent) { + return preOrder[parent] <= preOrder[child] && postOrder[child] <= postOrder[parent]; + } + + // Graphs: Theory and Algorithms. by K. Thulasiraman , M. N. S. Swamy (1992) + // 11.7.2 DFS of a directed graph + public static DFSTree build(int[][] transitions, int edgeCount) { + HashSet<Edge> nonBack = new HashSet<Edge>(); + HashSet<Edge> back = 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; + + boolean[] loopEnters = new boolean[transitions.length]; + + // enter 0 + entered ++; + preOrder[0] = entered; + marked[0] = true; + + boolean[] stackFlag = new boolean[edgeCount*2 + 1]; + int[] stackFrom = new int[edgeCount*2 + 1]; + int[] stackTo = new int[edgeCount*2 + 1]; + + int top = 0; + + // stack.push(new MarkScanned(0)); + stackFlag[top] = true; + stackTo[top] = 0; + top++; + + for (int to : transitions[0]) { + //stack.push(new ExamineEdge(0, to)); + stackFlag[top] = false; + stackFrom[top] = 0; + stackTo[top] = to; + top++; + } + + while (top > 0) { + top--; + //Action action = stack.pop(); + // markScanned + if (stackFlag[top]) { + completed ++; + postOrder[stackTo[top]] = completed; + scanned[stackTo[top]] = true; + } + else { + //ExamineEdge examineEdgeAction = (ExamineEdge) action; + int from = stackFrom[top]; + int to = stackTo[top]; + if (!marked[to]) { + nonBack.add(new Edge(from, to)); + // enter to + entered ++; + preOrder[to] = entered; + marked[to] = true; + + //stack.push(new MarkScanned(to)); + stackFlag[top] = true; + stackTo[top] = to; + top++; + + for (int to1 : transitions[to]) { + //stack.push(new ExamineEdge(to, to1)); + stackFlag[top] = false; + stackFrom[top] = to; + stackTo[top] = to1; + top++; + } + } + else if (preOrder[to] > preOrder[from]) { + nonBack.add(new Edge(from, to)); + } + else if (preOrder[to] < preOrder[from] && !scanned[to]) { + back.add(new Edge(from, to)); + loopEnters[to] = true; + } else { + nonBack.add(new Edge(from, to)); + } + } + } + + return new DFSTree(preOrder, postOrder, nonBack, back, loopEnters); + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/FramelessAnalyzer.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/FramelessAnalyzer.java new file mode 100644 index 000000000000..5804723e9ec1 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/FramelessAnalyzer.java @@ -0,0 +1,362 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import org.jetbrains.annotations.Nullable; +import org.jetbrains.org.objectweb.asm.Opcodes; +import org.jetbrains.org.objectweb.asm.tree.*; +import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Specialized 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. + */ +public class FramelessAnalyzer implements Opcodes { + static class Subroutine { + + LabelNode start; + boolean[] access; + List<JumpInsnNode> callers; + + private Subroutine() { + } + + Subroutine(@Nullable final LabelNode start, final int maxLocals, + @Nullable 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; + protected boolean[] wasQueued; + protected boolean[] queued; + protected int[] queue; + protected int top; + + public void analyze(final MethodNode m) throws AnalyzerException { + n = m.instructions.size(); + if ((m.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0 || n == 0) { + return; + } + 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); + } + } + } + + protected 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)); + } + + // ------------------------------------------------------------------------- + + protected void merge(final int insn, @Nullable 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; + } + } + + protected 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/asm/LeakingParameters.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/LeakingParameters.java new file mode 100644 index 000000000000..1a7ab15722f9 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/LeakingParameters.java @@ -0,0 +1,610 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import org.jetbrains.annotations.NotNull; +import org.jetbrains.org.objectweb.asm.Type; +import org.jetbrains.org.objectweb.asm.tree.*; +import org.jetbrains.org.objectweb.asm.tree.analysis.*; + +import java.util.Arrays; +import java.util.List; + +import static org.jetbrains.org.objectweb.asm.Opcodes.*; + +/** + * @author lambdamix + */ +public class LeakingParameters { + public final Frame<Value>[] frames; + public final boolean[] parameters; + public final boolean[] nullableParameters; + + public LeakingParameters(Frame<Value>[] frames, boolean[] parameters, boolean[] nullableParameters) { + this.frames = frames; + this.parameters = parameters; + this.nullableParameters = nullableParameters; + } + + public static LeakingParameters build(String className, MethodNode methodNode, boolean jsr) throws AnalyzerException { + Frame<ParamsValue>[] frames = jsr ? + new Analyzer<ParamsValue>(new ParametersUsage(methodNode)).analyze(className, methodNode) : + new LiteAnalyzer<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: + new Frame<ParamsValue>(frame).execute(insnNode, collector); + } + } + } + boolean[] notNullParameters = collector.leaking; + boolean[] nullableParameters = collector.nullableLeaking; + for (int i = 0; i < nullableParameters.length; i++) { + nullableParameters[i] |= notNullParameters[i]; + } + return new LeakingParameters((Frame<Value>[])(Frame<?>[])frames, notNullParameters, nullableParameters); + } + + public static LeakingParameters buildFast(String className, MethodNode methodNode, boolean jsr) throws AnalyzerException { + IParametersUsage parametersUsage = new IParametersUsage(methodNode); + Frame<?>[] frames = jsr ? + new Analyzer<IParamsValue>(parametersUsage).analyze(className, methodNode) : + new LiteAnalyzer<IParamsValue>(parametersUsage).analyze(className, methodNode); + int leakingMask = parametersUsage.leaking; + int nullableLeakingMask = parametersUsage.nullableLeaking; + boolean[] notNullParameters = new boolean[parametersUsage.arity]; + boolean[] nullableParameters = new boolean[parametersUsage.arity]; + for (int i = 0; i < notNullParameters.length; i++) { + notNullParameters[i] = (leakingMask & (1 << i)) != 0; + nullableParameters[i] = ((leakingMask | nullableLeakingMask) & (1 << i)) != 0; + } + return new LeakingParameters((Frame<Value>[])frames, notNullParameters, nullableParameters); + } +} + +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; + } +} + +// specialized version +final class IParamsValue implements Value { + final int params; + final int size; + + IParamsValue(int 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; + IParamsValue that = (IParamsValue)o; + return (this.size == that.size && this.params == that.params); + } + + @Override + public int hashCode() { + return 31 * 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 && (ASMUtils.isReferenceType(type) || ASMUtils.isBooleanType(type))) { + 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 value; + 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 IParametersUsage extends Interpreter<IParamsValue> { + static final IParamsValue val1 = new IParamsValue(0, 1); + static final IParamsValue val2 = new IParamsValue(0, 2); + int leaking = 0; + int nullableLeaking = 0; + int called = -1; + final int rangeStart; + final int rangeEnd; + final int arity; + final int shift; + + IParametersUsage(MethodNode methodNode) { + super(ASM5); + arity = Type.getArgumentTypes(methodNode.desc).length; + shift = (methodNode.access & ACC_STATIC) == 0 ? 2 : 1; + rangeStart = shift; + rangeEnd = arity + shift; + } + + @Override + public IParamsValue newValue(Type type) { + if (type == null) return val1; + called++; + if (type == Type.VOID_TYPE) return null; + if (called < rangeEnd && rangeStart <= called && (ASMUtils.isReferenceType(type) || ASMUtils.isBooleanType(type))) { + int n = called - shift; + return type.getSize() == 1 ? new IParamsValue(1 << n, 1) : new IParamsValue(1 << n, 2); + } + else { + return type.getSize() == 1 ? val1 : val2; + } + } + + @Override + public IParamsValue 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 = ASMUtils.getSizeFast(((FieldInsnNode)insn).desc); + break; + default: + size = 1; + } + return size == 1 ? val1 : val2; + } + + @Override + public IParamsValue copyOperation(AbstractInsnNode insn, IParamsValue value) { + return value; + } + + @Override + public IParamsValue unaryOperation(AbstractInsnNode insn, IParamsValue value) { + int size; + switch (insn.getOpcode()) { + case CHECKCAST: + return value; + case LNEG: + case DNEG: + case I2L: + case I2D: + case L2D: + case F2L: + case F2D: + case D2L: + size = 2; + break; + case GETFIELD: + size = ASMUtils.getSizeFast(((FieldInsnNode)insn).desc); + leaking |= value.params; + break; + case ARRAYLENGTH: + case MONITORENTER: + case INSTANCEOF: + case IRETURN: + case ARETURN: + case IFNONNULL: + case IFNULL: + case IFEQ: + case IFNE: + size = 1; + leaking |= value.params; + break; + default: + size = 1; + } + return size == 1 ? val1 : val2; + } + + @Override + public IParamsValue binaryOperation(AbstractInsnNode insn, IParamsValue value1, IParamsValue value2) { + int size; + switch (insn.getOpcode()) { + case LALOAD: + case DALOAD: + size = 2; + leaking |= value1.params; + break; + 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; + case IALOAD: + case FALOAD: + case AALOAD: + case BALOAD: + case CALOAD: + case SALOAD: + leaking |= value1.params; + size = 1; + break; + case PUTFIELD: + leaking |= value1.params; + nullableLeaking |= value2.params; + size = 1; + break; + default: + size = 1; + } + return size == 1 ? val1 : val2; + } + + @Override + public IParamsValue ternaryOperation(AbstractInsnNode insn, IParamsValue value1, IParamsValue value2, IParamsValue value3) { + switch (insn.getOpcode()) { + case IASTORE: + case LASTORE: + case FASTORE: + case DASTORE: + case BASTORE: + case CASTORE: + case SASTORE: + leaking |= value1.params; + break; + case AASTORE: + leaking |= value1.params; + nullableLeaking |= value3.params; + break; + default: + } + return val1; + } + + @Override + public IParamsValue naryOperation(AbstractInsnNode insn, List<? extends IParamsValue> values) { + int opcode = insn.getOpcode(); + switch (opcode) { + case INVOKESTATIC: + case INVOKESPECIAL: + case INVOKEVIRTUAL: + case INVOKEINTERFACE: + for (IParamsValue value : values) { + leaking |= value.params; + } + break; + default: + } + int size; + if (opcode == MULTIANEWARRAY) { + size = 1; + } else { + String desc = (opcode == INVOKEDYNAMIC) ? ((InvokeDynamicInsnNode) insn).desc : ((MethodInsnNode) insn).desc; + size = ASMUtils.getReturnSizeFast(desc); + } + return size == 1 ? val1 : val2; + } + + @Override + public void returnOperation(AbstractInsnNode insn, IParamsValue value, IParamsValue expected) {} + + @Override + public IParamsValue merge(IParamsValue v1, IParamsValue v2) { + if (v1.equals(v2)) return v1; + return new IParamsValue(v1.params | v2.params, Math.min(v1.size, v2.size)); + } +} + +class LeakingParametersCollector extends ParametersUsage { + final boolean[] leaking; + final boolean[] nullableLeaking; + LeakingParametersCollector(MethodNode methodNode) { + super(methodNode); + leaking = new boolean[arity]; + nullableLeaking = 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: + boolean[] params = value1.params; + for (int i = 0; i < arity; i++) { + leaking[i] |= params[i]; + } + break; + case PUTFIELD: + params = value1.params; + for (int i = 0; i < arity; i++) { + leaking[i] |= params[i]; + } + params = value2.params; + for (int i = 0; i < arity; i++) { + nullableLeaking[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 BASTORE: + case CASTORE: + case SASTORE: + boolean[] params = value1.params; + for (int i = 0; i < arity; i++) { + leaking[i] |= params[i]; + } + break; + case AASTORE: + params = value1.params; + for (int i = 0; i < arity; i++) { + leaking[i] |= params[i]; + } + params = value3.params; + for (int i = 0; i < arity; i++) { + nullableLeaking[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); + } +} + diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/LiteAnalyzer.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/LiteAnalyzer.java new file mode 100644 index 000000000000..22961208076b --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/LiteAnalyzer.java @@ -0,0 +1,189 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import org.jetbrains.org.objectweb.asm.Opcodes; +import org.jetbrains.org.objectweb.asm.Type; +import org.jetbrains.org.objectweb.asm.tree.*; +import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException; +import org.jetbrains.org.objectweb.asm.tree.analysis.Frame; +import org.jetbrains.org.objectweb.asm.tree.analysis.Interpreter; +import org.jetbrains.org.objectweb.asm.tree.analysis.Value; + +import java.util.ArrayList; +import java.util.List; + +/** + * Specialized lite version of {@link org.objectweb.asm.tree.analysis.Analyzer}. + * No processing of Subroutines. May be used for methods without JSR/RET instructions. + * + * @author lambdamix + */ +public class LiteAnalyzer<V extends Value> implements Opcodes { + + private final Interpreter<V> interpreter; + + private Frame<V>[] frames; + + private boolean[] queued; + + private int[] queue; + + private int top; + + public LiteAnalyzer(final Interpreter<V> interpreter) { + this.interpreter = interpreter; + } + + public Frame<V>[] analyze(final String owner, final MethodNode m) throws AnalyzerException { + if ((m.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0 || m.instructions.size() == 0) { + frames = (Frame<V>[]) new Frame<?>[0]; + return frames; + } + int n = m.instructions.size(); + InsnList insns = m.instructions; + List<TryCatchBlockNode>[] handlers = (List<TryCatchBlockNode>[]) new List<?>[n]; + frames = (Frame<V>[]) new Frame<?>[n]; + queued = 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); + } + } + + // initializes the data structures for the control flow analysis + Frame<V> current = new Frame<V>(m.maxLocals, m.maxStack); + Frame<V> handler = new Frame<V>(m.maxLocals, m.maxStack); + current.setReturn(interpreter.newValue(Type.getReturnType(m.desc))); + Type[] args = Type.getArgumentTypes(m.desc); + int local = 0; + if ((m.access & ACC_STATIC) == 0) { + Type ctype = Type.getObjectType(owner); + current.setLocal(local++, interpreter.newValue(ctype)); + } + for (int i = 0; i < args.length; ++i) { + current.setLocal(local++, interpreter.newValue(args[i])); + if (args[i].getSize() == 2) { + current.setLocal(local++, interpreter.newValue(null)); + } + } + while (local < m.maxLocals) { + current.setLocal(local++, interpreter.newValue(null)); + } + merge(0, current); + + // control flow analysis + while (top > 0) { + int insn = queue[--top]; + Frame<V> f = frames[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, f); + } else { + current.init(f).execute(insnNode, interpreter); + + if (insnNode instanceof JumpInsnNode) { + JumpInsnNode j = (JumpInsnNode) insnNode; + if (insnOpcode != GOTO && insnOpcode != JSR) { + merge(insn + 1, current); + } + int jump = insns.indexOf(j.label); + merge(jump, current); + } else if (insnNode instanceof LookupSwitchInsnNode) { + LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode; + int jump = insns.indexOf(lsi.dflt); + merge(jump, current); + for (int j = 0; j < lsi.labels.size(); ++j) { + LabelNode label = lsi.labels.get(j); + jump = insns.indexOf(label); + merge(jump, current); + } + } else if (insnNode instanceof TableSwitchInsnNode) { + TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode; + int jump = insns.indexOf(tsi.dflt); + merge(jump, current); + for (int j = 0; j < tsi.labels.size(); ++j) { + LabelNode label = tsi.labels.get(j); + jump = insns.indexOf(label); + merge(jump, current); + } + } else if (insnOpcode != ATHROW && (insnOpcode < IRETURN || insnOpcode > RETURN)) { + merge(insn + 1, current); + } + } + + List<TryCatchBlockNode> insnHandlers = handlers[insn]; + if (insnHandlers != null) { + for (int i = 0; i < insnHandlers.size(); ++i) { + TryCatchBlockNode tcb = insnHandlers.get(i); + int jump = insns.indexOf(tcb.handler); + handler.init(f); + handler.clearStack(); + handler.push(interpreter.newValue(ASMUtils.THROWABLE_TYPE)); + merge(jump, handler); + } + } + } 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); + } + } + + return frames; + } + + public Frame<V>[] getFrames() { + return frames; + } + + private void merge(final int insn, final Frame<V> frame) throws AnalyzerException { + Frame<V> oldFrame = frames[insn]; + boolean changes; + + if (oldFrame == null) { + frames[insn] = new Frame<V>(frame); + changes = true; + } else { + changes = oldFrame.merge(frame, interpreter); + } + if (changes && !queued[insn]) { + queued[insn] = true; + queue[top++] = insn; + } + } + +} + diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/LiteFramelessAnalyzer.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/LiteFramelessAnalyzer.java new file mode 100644 index 000000000000..0a9721018862 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/LiteFramelessAnalyzer.java @@ -0,0 +1,56 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import org.jetbrains.org.objectweb.asm.tree.AbstractInsnNode; +import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException; + +import java.util.List; + +/** + * Specialized lite version of {@link FramelessAnalyzer}. + * No processing of Subroutines. May be used for methods without JSR/RET instructions. + * + * @author lambdamix + */ +public class LiteFramelessAnalyzer extends FramelessAnalyzer { + + @Override + protected void findSubroutine(int insn, FramelessAnalyzer.Subroutine sub, List<AbstractInsnNode> calls) throws AnalyzerException { + } + + @Override + protected void merge(final int insn, final FramelessAnalyzer.Subroutine subroutine) throws AnalyzerException { + if (!wasQueued[insn]) { + wasQueued[insn] = true; + if (!queued[insn]) { + queued[insn] = true; + queue[top++] = insn; + } + } + } + + @Override + protected void merge(final int insn, final FramelessAnalyzer.Subroutine subroutineBeforeJSR, final boolean[] access) throws AnalyzerException { + if (!wasQueued[insn]) { + wasQueued[insn] = true; + if (!queued[insn]) { + queued[insn] = true; + queue[top++] = insn; + } + } + } +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/OriginsAnalysis.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/OriginsAnalysis.java new file mode 100644 index 000000000000..e154bf847730 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/OriginsAnalysis.java @@ -0,0 +1,193 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import gnu.trove.TIntArrayList; +import org.jetbrains.annotations.Nullable; +import org.jetbrains.org.objectweb.asm.Opcodes; +import org.jetbrains.org.objectweb.asm.tree.AbstractInsnNode; +import org.jetbrains.org.objectweb.asm.tree.InsnList; +import org.jetbrains.org.objectweb.asm.tree.analysis.*; + +import java.util.HashSet; +import java.util.LinkedList; + +/** + * @author lambdamix + */ +public class OriginsAnalysis { + + private static SourceInterpreter ourInterpreter = new SourceInterpreter() { + @Override + public SourceValue copyOperation(AbstractInsnNode insn, SourceValue value) { + return value; + } + }; + + private static class PreValue extends SourceValue { + final boolean local; + final int slot; + + public PreValue(boolean local, int slot, int size) { + super(size); + this.local = local; + this.slot = slot; + } + } + + private static class Location { + final boolean local; + final int slot; + + Location(boolean local, int slot) { + this.local = local; + this.slot = slot; + } + } + + private static class InsnLocation extends Location { + final int insnIndex; + + private InsnLocation(boolean local, int insnIndex, int slot) { + super(local, slot); + this.insnIndex = insnIndex; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null) return false; + InsnLocation insnLocation = (InsnLocation)o; + if (local != insnLocation.local) return false; + if (insnIndex != insnLocation.insnIndex) return false; + if (slot != insnLocation.slot) return false; + return true; + } + + @Override + public int hashCode() { + // +1 is to avoid collisions + int result = 31 * insnIndex + slot + 1; + return local ? result : -result; + } + } + + /** + * + * @param frames fixpoint of frames + * @param instructions method instructions + * @param graph method control flow graph + * @return array, array[i] == true means that the result of a method execution may originate at an i-th instruction + * @throws AnalyzerException + */ + public static boolean[] resultOrigins(Frame<Value>[] frames, InsnList instructions, ControlFlowGraph graph) throws AnalyzerException { + + TIntArrayList[] backTransitions = new TIntArrayList[instructions.size()]; + for (int i = 0; i < backTransitions.length; i++) { + backTransitions[i] = new TIntArrayList(); + } + LinkedList<InsnLocation> queue = new LinkedList<InsnLocation>(); + HashSet<InsnLocation> queued = new HashSet<InsnLocation>(); + for (int from = 0; from < instructions.size(); from++) { + for (int to : graph.transitions[from]) { + TIntArrayList froms = backTransitions[to]; + froms.add(from); + int opcode = instructions.get(to).getOpcode(); + if (opcode >= Opcodes.IRETURN && opcode <= Opcodes.ARETURN) { + InsnLocation sourceLoc = new InsnLocation(false, from, frames[to].getStackSize() - 1); + if (queued.add(sourceLoc)) { + queue.push(sourceLoc); + } + } + } + } + + boolean[] result = new boolean[instructions.size()]; + + while (!queue.isEmpty()) { + InsnLocation resultLocation = queue.pop(); + + int insnIndex = resultLocation.insnIndex; + AbstractInsnNode insn = instructions.get(insnIndex); + int opcode = insn.getOpcode(); + Location preLocation = previousLocation(frames[insnIndex], resultLocation, insn); + if (preLocation == null) { + if (opcode != Opcodes.INVOKEINTERFACE && opcode != Opcodes.GETFIELD && !(opcode >= Opcodes.IALOAD && opcode <= Opcodes.SALOAD)) { + result[insnIndex] = true; + } + } else { + TIntArrayList froms = backTransitions[insnIndex]; + for (int i = 0; i < froms.size(); i++) { + InsnLocation preILoc = new InsnLocation(preLocation.local, froms.getQuick(i), preLocation.slot); + if (queued.add(preILoc)) { + queue.push(preILoc); + } + } + } + } + + return result; + } + + /** + * + * @param frame a start frame with an interesting value + * @param location location of an interesting value *after* execution of an instruction + * @param insn an executed instruction + * @return location of an interesting value *before* execution of an instruction (in the past) or null if it is not traceable + * @throws AnalyzerException + */ + @Nullable + private static Location previousLocation(Frame<Value> frame, Location location, AbstractInsnNode insn) throws AnalyzerException { + int insnType = insn.getType(); + if (insnType == AbstractInsnNode.LABEL || insnType == AbstractInsnNode.LINE || insnType == AbstractInsnNode.FRAME) { + return location; + } + int opCode = insn.getOpcode(); + if (location.local && !((opCode >= Opcodes.ISTORE && opCode <= Opcodes.ASTORE) || opCode == Opcodes.IINC)) { + return location; + } + Frame<SourceValue> preFrame = makePreFrame(frame); + preFrame.execute(insn, ourInterpreter); + if (location.local) { + SourceValue preVal = preFrame.getLocal(location.slot); + if (preVal instanceof PreValue) { + PreValue val = (PreValue)preVal; + return new Location(val.local, val.slot); + } + } else { + SourceValue preVal = preFrame.getStack(location.slot); + if (preVal instanceof PreValue) { + PreValue val = (PreValue)preVal; + return new Location(val.local, val.slot); + } + } + return null; + } + + private static Frame<SourceValue> makePreFrame(Frame<Value> frame) { + Frame<SourceValue> preFrame = new Frame<SourceValue>(frame.getLocals(), frame.getMaxStackSize()); + for (int i = 0; i < frame.getLocals(); i++) { + preFrame.setLocal(i, new PreValue(true, i, frame.getLocal(i).getSize())); + } + for (int i = 0; i < frame.getStackSize(); i++) { + preFrame.push(new PreValue(false, i, frame.getStack(i).getSize())); + } + return preFrame; + } +} + + diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/RichControlFlow.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/RichControlFlow.java new file mode 100644 index 000000000000..ea8f69c2c870 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/asm/RichControlFlow.java @@ -0,0 +1,101 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.codeInspection.bytecodeAnalysis.asm; + +import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph.Edge; + +import gnu.trove.TIntArrayList; +import gnu.trove.TIntHashSet; +import gnu.trove.TIntIterator; + +/** + * @author lambdamix + */ +public final class RichControlFlow { + public final ControlFlowGraph controlFlow; + public final DFSTree dfsTree; + + public RichControlFlow(ControlFlowGraph controlFlow, DFSTree dfsTree) { + this.controlFlow = controlFlow; + this.dfsTree = dfsTree; + } + + // Tarjan. Testing flow graph reducibility. + // Journal of Computer and System Sciences 9.3 (1974): 355-365. + public boolean reducible() { + if (dfsTree.back.isEmpty()) { + return true; + } + int size = controlFlow.transitions.length; + boolean[] loopEnters = dfsTree.loopEnters; + TIntHashSet[] cycleIncomings = new TIntHashSet[size]; + // really this may be array, since dfs already ensures no duplicates + TIntArrayList[] nonCycleIncomings = new TIntArrayList[size]; + int[] collapsedTo = new int[size]; + int[] queue = new int[size]; + int top; + for (int i = 0; i < size; i++) { + if (loopEnters[i]) { + cycleIncomings[i] = new TIntHashSet(); + } + nonCycleIncomings[i] = new TIntArrayList(); + collapsedTo[i] = i; + } + + // from whom back connections + for (Edge edge : dfsTree.back) { + cycleIncomings[edge.to].add(edge.from); + } + // from whom ordinary connections + for (Edge edge : dfsTree.nonBack) { + nonCycleIncomings[edge.to].add(edge.from); + } + + for (int w = size - 1; w >= 0 ; w--) { + top = 0; + // NB - it is modified later! + TIntHashSet p = cycleIncomings[w]; + if (p == null) { + continue; + } + TIntIterator iter = p.iterator(); + while (iter.hasNext()) { + queue[top++] = iter.next(); + } + + while (top > 0) { + int x = queue[--top]; + TIntArrayList incoming = nonCycleIncomings[x]; + for (int i = 0; i < incoming.size(); i++) { + int y1 = collapsedTo[incoming.getQuick(i)]; + if (!dfsTree.isDescendant(y1, w)) { + return false; + } + if (y1 != w && p.add(y1)) { + queue[top++] = y1; + } + } + } + + iter = p.iterator(); + while (iter.hasNext()) { + collapsedTo[iter.next()] = w; + } + } + + return true; + } +} 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 bd207e58a0fe..7037fac8cfea 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 @@ -27,6 +27,7 @@ import com.intellij.psi.util.CachedValuesManager; import com.intellij.util.Function; import com.intellij.util.NullableFunction; import com.intellij.util.containers.ContainerUtil; +import com.siyeh.ig.psiutils.SideEffectChecker; import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.Nullable; @@ -213,6 +214,16 @@ class ContractInferenceInterpreter { } } + if (expr instanceof PsiNewExpression) { + return toContracts(states, NOT_NULL_VALUE); + } + if (expr instanceof PsiMethodCallExpression) { + PsiMethod method = ((PsiMethodCallExpression)expr).resolveMethod(); + if (method != null && NullableNotNullManager.isNotNull(method)) { + return toContracts(states, NOT_NULL_VALUE); + } + } + final ValueConstraint constraint = getLiteralConstraint(expr); if (constraint != null) { return toContracts(states, constraint); @@ -315,7 +326,7 @@ class ContractInferenceInterpreter { private List<MethodContract> visitStatements(List<ValueConstraint[]> states, PsiStatement... statements) { List<MethodContract> result = ContainerUtil.newArrayList(); for (PsiStatement statement : statements) { - if (statement instanceof PsiBlockStatement && ((PsiBlockStatement)statement).getCodeBlock().getStatements().length == 1) { + if (statement instanceof PsiBlockStatement) { result.addAll(visitStatements(states, ((PsiBlockStatement)statement).getCodeBlock().getStatements())); } else if (statement instanceof PsiIfStatement) { @@ -353,12 +364,36 @@ class ContractInferenceInterpreter { List<MethodContract> conditionResults = visitExpression(states, ((PsiAssertStatement)statement).getAssertCondition()); result.addAll(toContracts(antecedentsOf(filterReturning(conditionResults, FALSE_VALUE)), THROW_EXCEPTION)); } + else if (statement instanceof PsiDeclarationStatement && !mayHaveSideEffects((PsiDeclarationStatement)statement)) { + continue; + } + else if (statement instanceof PsiDoWhileStatement) { + result.addAll(visitStatements(states, ((PsiDoWhileStatement)statement).getBody())); + } + else if (statement instanceof PsiTryStatement) { + PsiCodeBlock block = ((PsiTryStatement)statement).getTryBlock(); + if (block != null) { + result.addAll(visitStatements(states, block.getStatements())); + } + } break; // visit only the first statement unless it's 'if' whose 'then' always returns and the next statement is effectively 'else' } return result; } + private static boolean mayHaveSideEffects(PsiDeclarationStatement statement) { + for (PsiElement element : statement.getDeclaredElements()) { + if (element instanceof PsiVariable) { + PsiExpression initializer = ((PsiVariable)element).getInitializer(); + if (initializer != null && SideEffectChecker.mayHaveSideEffects(initializer)) { + return true; + } + } + } + return false; + } + private static boolean alwaysReturns(@Nullable PsiStatement statement) { if (statement instanceof PsiReturnStatement || statement instanceof PsiThrowStatement) return true; if (statement instanceof PsiBlockStatement) { @@ -381,6 +416,7 @@ class ContractInferenceInterpreter { if (expr.textMatches(PsiKeyword.TRUE)) return TRUE_VALUE; if (expr.textMatches(PsiKeyword.FALSE)) return FALSE_VALUE; if (expr.textMatches(PsiKeyword.NULL)) return NULL_VALUE; + if (((PsiLiteralExpression)expr).getValue() instanceof String) return NOT_NULL_VALUE; } return null; } 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 7ef19f2b73d0..7539d7195701 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 @@ -591,12 +591,14 @@ public class ControlFlowAnalyzer extends JavaElementVisitor { generateBoxingUnboxingInstructionFor(caseExpression, PsiType.INT); final PsiClass psiClass = PsiUtil.resolveClassInType(caseExpression.getType()); - if (psiClass != null && psiClass.isEnum()) { + if (psiClass != null) { addInstruction(new FieldReferenceInstruction(caseExpression, "switch statement expression")); - enumValues = new HashSet<PsiEnumConstant>(); - for (PsiField f : psiClass.getFields()) { - if (f instanceof PsiEnumConstant) { - enumValues.add((PsiEnumConstant)f); + if (psiClass.isEnum()) { + enumValues = new HashSet<PsiEnumConstant>(); + for (PsiField f : psiClass.getFields()) { + if (f instanceof PsiEnumConstant) { + enumValues.add((PsiEnumConstant)f); + } } } } else { diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DfaMemoryStateImpl.java b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DfaMemoryStateImpl.java index 1b6d1dfedfec..3f0caf47679e 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DfaMemoryStateImpl.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/DfaMemoryStateImpl.java @@ -640,6 +640,13 @@ public class DfaMemoryStateImpl implements DfaMemoryState { return true; } + if (dfaLeft == dfaRight) { + if (dfaLeft instanceof DfaVariableValue && ((DfaVariableValue)dfaLeft).containsCalls()) { + return true; + } + return !isNegated; + } + if (isNull(dfaLeft) && isNotNull(dfaRight) || isNull(dfaRight) && isNotNull(dfaLeft)) { return isNegated; } 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 index ec9e02fce92d..7ebce779c3a8 100644 --- 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 @@ -155,7 +155,7 @@ public class DfaExpressionFactory { @Nullable private PsiVariable getArrayIndexVariable(@Nullable PsiExpression indexExpression) { Object constant = JavaConstantExpressionEvaluator.computeConstantExpression(indexExpression, false); - if (constant instanceof Integer) { + if (constant instanceof Integer && ((Integer)constant).intValue() >= 0) { PsiVariable mockVar = myMockIndices.get(constant); if (mockVar == null) { mockVar = JavaPsiFacade.getElementFactory(indexExpression.getProject()).createField("$array$index$" + constant, PsiType.INT); 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 3030bef32934..840103f5c993 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 @@ -221,4 +221,8 @@ public class DfaVariableValue extends DfaValue { return true; } + public boolean containsCalls() { + return myVariable instanceof PsiMethod || myQualifier != null && myQualifier.containsCalls(); + } + } diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/inheritance/ImplementedAtRuntimeCondition.java b/java/java-analysis-impl/src/com/intellij/codeInspection/inheritance/ImplementedAtRuntimeCondition.java new file mode 100644 index 000000000000..55918450f481 --- /dev/null +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/inheritance/ImplementedAtRuntimeCondition.java @@ -0,0 +1,29 @@ +/* + * 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; + +import com.intellij.openapi.extensions.ExtensionPointName; +import com.intellij.psi.PsiClass; +import org.jetbrains.annotations.NotNull; + +/** + * @author nik + */ +public abstract class ImplementedAtRuntimeCondition { + public static final ExtensionPointName<ImplementedAtRuntimeCondition> EP_NAME = ExtensionPointName.create("com.intellij.codeInsight.implementedAtRuntime"); + + public abstract boolean isImplementedAtRuntime(@NotNull PsiClass psiClass); +} diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/javaDoc/JavaDocLocalInspectionBase.java b/java/java-analysis-impl/src/com/intellij/codeInspection/javaDoc/JavaDocLocalInspectionBase.java index 5d6c4bcb59a1..36d7bc2f17ef 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/javaDoc/JavaDocLocalInspectionBase.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/javaDoc/JavaDocLocalInspectionBase.java @@ -1,5 +1,5 @@ /* - * Copyright 2000-2013 JetBrains s.r.o. + * 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. @@ -540,7 +540,7 @@ public class JavaDocLocalInspectionBase extends BaseJavaBatchLocalInspectionTool } if (required && superMethods.length == 0 && isTagRequired(psiMethod, "@throws") && psiMethod.getThrowsList().getReferencedTypes().length > 0) { - final Map<PsiClassType, PsiClass> declaredExceptions = new HashMap<PsiClassType, PsiClass>(); + final Map<PsiClassType, PsiClass> declaredExceptions = new LinkedHashMap<PsiClassType, PsiClass>(); final PsiClassType[] classTypes = psiMethod.getThrowsList().getReferencedTypes(); for (PsiClassType classType : classTypes) { final PsiClass psiClass = classType.resolve(); diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/unnecessaryModuleDependency/UnnecessaryModuleDependencyInspection.java b/java/java-analysis-impl/src/com/intellij/codeInspection/unnecessaryModuleDependency/UnnecessaryModuleDependencyInspection.java index f3884b30efeb..e51101c98460 100644 --- a/java/java-analysis-impl/src/com/intellij/codeInspection/unnecessaryModuleDependency/UnnecessaryModuleDependencyInspection.java +++ b/java/java-analysis-impl/src/com/intellij/codeInspection/unnecessaryModuleDependency/UnnecessaryModuleDependencyInspection.java @@ -45,7 +45,7 @@ public class UnnecessaryModuleDependencyInspection extends GlobalInspectionTool if (refEntity instanceof RefModule){ final RefModule refModule = (RefModule)refEntity; final Module module = refModule.getModule(); - if (module.isDisposed()) return CommonProblemDescriptor.EMPTY_ARRAY; + if (module.isDisposed() || !scope.containsModule(module)) return CommonProblemDescriptor.EMPTY_ARRAY; final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module); final OrderEntry[] declaredDependencies = moduleRootManager.getOrderEntries(); final Module[] declaredModuleDependencies = moduleRootManager.getDependencies(); 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 4db11dc0b0d0..6352731e322f 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 @@ -70,7 +70,7 @@ public class UnusedLibrariesInspection extends GlobalInspectionTool { if (refEntity instanceof RefModule) { final RefModule refModule = (RefModule)refEntity; final Module module = refModule.getModule(); - if (module.isDisposed()) return CommonProblemDescriptor.EMPTY_ARRAY; + if (module.isDisposed() || !scope.containsModule(module)) return CommonProblemDescriptor.EMPTY_ARRAY; final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module); final Set<VirtualFile> usedRoots = refModule.getUserData(UnusedLibraryGraphAnnotator.USED_LIBRARY_ROOTS); |