1 files changed, 134 insertions, 90 deletions

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 {}