java/java-impl/src/com/intellij/slicer/SliceNullnessAnalyzer.java

   1 /*
   2  * Copyright 2000-2010 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.slicer;
  17
  18 import com.intellij.codeInsight.AnnotationUtil;
  19 import com.intellij.codeInspection.dataFlow.DfaUtil;
  20 import com.intellij.ide.util.treeView.AbstractTreeNode;
  21 import com.intellij.ide.util.treeView.AbstractTreeStructure;
  22 import com.intellij.openapi.application.ApplicationManager;
  23 import com.intellij.openapi.progress.ProgressIndicator;
  24 import com.intellij.openapi.progress.ProgressManager;
  25 import com.intellij.openapi.progress.Task;
  26 import com.intellij.openapi.util.Computable;
  27 import com.intellij.openapi.util.Ref;
  28 import com.intellij.psi.*;
  29 import com.intellij.psi.util.PsiUtil;
  30 import com.intellij.util.NullableFunction;
  31 import com.intellij.util.containers.FactoryMap;
  32 import gnu.trove.THashMap;
  33 import gnu.trove.THashSet;
  34 import gnu.trove.TObjectHashingStrategy;
  35 import org.jetbrains.annotations.NotNull;
  36
  37 import java.util.ArrayList;
  38 import java.util.Collection;
  39 import java.util.Collections;
  40 import java.util.Map;
  41
  42 /**
  43  * User: cdr
  44  */
  45 public class SliceNullnessAnalyzer {
  46   private static void groupByNullness(NullAnalysisResult result, SliceRootNode oldRoot, final Map<SliceNode, NullAnalysisResult> map) {
  47     SliceRootNode root = createNewTree(result, oldRoot, map);
  48
  49     SliceUsage rootUsage = oldRoot.myCachedChildren.get(0).getValue();
  50     SliceManager.getInstance(root.getProject()).createToolWindow(true, root, true, SliceManager.getElementDescription(null, rootUsage.getElement(), " Grouped by Nullness") );
  51 }
  52
  53   public static SliceRootNode createNewTree(NullAnalysisResult result, SliceRootNode oldRoot, final Map<SliceNode, NullAnalysisResult> map) {
  54     SliceRootNode root = oldRoot.copy();
  55     assert oldRoot.myCachedChildren.size() == 1;
  56     SliceNode oldRootStart = oldRoot.myCachedChildren.get(0);
  57     root.setChanged();
  58     root.targetEqualUsages.clear();
  59     root.myCachedChildren = new ArrayList<SliceNode>();
  60
  61     if (!result.nulls.isEmpty()) {
  62       SliceLeafValueClassNode nullRoot = new SliceLeafValueClassNode(root.getProject(), root, "Null Values");
  63       root.myCachedChildren.add(nullRoot);
  64
  65       for (final PsiElement nullExpression : result.nulls) {
  66         SliceNode newRoot = SliceLeafAnalyzer.filterTree(oldRootStart, new NullableFunction<SliceNode, SliceNode>() {
  67           public SliceNode fun(SliceNode oldNode) {
  68             return oldNode.getDuplicate() == null && node(oldNode, map).nulls.contains(nullExpression) ? oldNode.copy() : null;
  69           }
  70         },null);
  71         nullRoot.myCachedChildren.add(new SliceLeafValueRootNode(root.getProject(), nullExpression, nullRoot, Collections.singletonList(newRoot),
  72                                                                  oldRoot.getValue().params));
  73       }
  74     }
  75     if (!result.notNulls.isEmpty()) {
  76       SliceLeafValueClassNode valueRoot = new SliceLeafValueClassNode(root.getProject(), root, "NotNull Values");
  77       root.myCachedChildren.add(valueRoot);
  78
  79       for (final PsiElement expression : result.notNulls) {
  80         SliceNode newRoot = SliceLeafAnalyzer.filterTree(oldRootStart, new NullableFunction<SliceNode, SliceNode>() {
  81           public SliceNode fun(SliceNode oldNode) {
  82             return oldNode.getDuplicate() == null && node(oldNode, map).notNulls.contains(expression) ? oldNode.copy() : null;
  83           }
  84         },null);
  85         valueRoot.myCachedChildren.add(new SliceLeafValueRootNode(root.getProject(), expression, valueRoot, Collections.singletonList(newRoot),
  86                                                                   oldRoot.getValue().params));
  87       }
  88     }
  89     if (!result.unknown.isEmpty()) {
  90       SliceLeafValueClassNode valueRoot = new SliceLeafValueClassNode(root.getProject(), root, "Other Values");
  91       root.myCachedChildren.add(valueRoot);
  92
  93       for (final PsiElement expression : result.unknown) {
  94         SliceNode newRoot = SliceLeafAnalyzer.filterTree(oldRootStart, new NullableFunction<SliceNode, SliceNode>() {
  95           public SliceNode fun(SliceNode oldNode) {
  96             return oldNode.getDuplicate() == null && node(oldNode, map).unknown.contains(expression) ? oldNode.copy() : null;
  97           }
  98         },null);
  99         valueRoot.myCachedChildren.add(new SliceLeafValueRootNode(root.getProject(), expression, valueRoot, Collections.singletonList(newRoot),
 100                                                                   oldRoot.getValue().params));
 101       }
 102     }
 103     return root;
 104   }
 105
 106   public static void startAnalyzeNullness(final AbstractTreeStructure treeStructure, final Runnable finish) {
 107     final SliceRootNode root = (SliceRootNode)treeStructure.getRootElement();
 108     final Ref<NullAnalysisResult> leafExpressions = Ref.create(null);
 109     final Map<SliceNode, NullAnalysisResult> map = createMap();
 110
 111     ProgressManager.getInstance().run(new Task.Backgroundable(root.getProject(), "Expanding all nodes... (may very well take the whole day)", true) {
 112       public void run(@NotNull final ProgressIndicator indicator) {
 113         NullAnalysisResult l = calcNullableLeaves(root, treeStructure, map);
 114         leafExpressions.set(l);
 115       }
 116
 117       @Override
 118       public void onCancel() {
 119         finish.run();
 120       }
 121
 122       @Override
 123       public void onSuccess() {
 124         try {
 125           NullAnalysisResult leaves = leafExpressions.get();
 126           if (leaves == null) return;  //cancelled
 127
 128           groupByNullness(leaves, root, map);
 129         }
 130         finally {
 131           finish.run();
 132         }
 133       }
 134     });
 135   }
 136
 137   public static Map<SliceNode, NullAnalysisResult> createMap() {
 138     return new FactoryMap<SliceNode, NullAnalysisResult>() {
 139       @Override
 140       protected NullAnalysisResult create(SliceNode key) {
 141         return new NullAnalysisResult();
 142       }
 143
 144       @Override
 145       protected Map<SliceNode, NullAnalysisResult> createMap() {
 146         return new THashMap<SliceNode, NullAnalysisResult>(TObjectHashingStrategy.IDENTITY);
 147       }
 148     };
 149   }
 150
 151   private static NullAnalysisResult node(SliceNode node, Map<SliceNode, NullAnalysisResult> nulls) {
 152     return nulls.get(node);
 153   }
 154
 155   @NotNull
 156   public static NullAnalysisResult calcNullableLeaves(@NotNull final SliceNode root, @NotNull AbstractTreeStructure treeStructure,
 157                                                        final Map<SliceNode, NullAnalysisResult> map) {
 158     final SliceLeafAnalyzer.SliceNodeGuide guide = new SliceLeafAnalyzer.SliceNodeGuide(treeStructure);
 159     WalkingState<SliceNode> walkingState = new WalkingState<SliceNode>(guide) {
 160       @Override
 161       public void visit(@NotNull SliceNode element) {
 162         element.update(null);
 163         node(element, map).clear();
 164         SliceNode duplicate = element.getDuplicate();
 165         if (duplicate != null) {
 166           node(element, map).add(node(duplicate, map));
 167         }
 168         else {
 169           SliceUsage sliceUsage = element.getValue();
 170           final PsiElement value = sliceUsage.getElement();
 171           DfaUtil.Nullness nullness = ApplicationManager.getApplication().runReadAction(new Computable<DfaUtil.Nullness>() {
 172             public DfaUtil.Nullness compute() {
 173               return checkNullness(value);
 174             }
 175           });
 176           if (nullness == DfaUtil.Nullness.NULL) {
 177             node(element, map).nulls.add(value);
 178           }
 179           else if (nullness == DfaUtil.Nullness.NOT_NULL) {
 180             node(element, map).notNulls.add(value);
 181           }
 182           else {
 183             Collection<? extends AbstractTreeNode> children = element.getChildren();
 184             if (children.isEmpty()) {
 185               node(element, map).unknown.add(value);
 186             }
 187             super.visit(element);
 188           }
 189         }
 190       }
 191
 192       @Override
 193       public void elementFinished(@NotNull SliceNode element) {
 194         SliceNode parent = guide.getParent(element);
 195         if (parent != null) {
 196           node(parent, map).add(node(element, map));
 197         }
 198       }
 199     };
 200     walkingState.visit(root);
 201
 202     return node(root, map);
 203   }
 204
 205   private static DfaUtil.Nullness checkNullness(final PsiElement element) {
 206     // null
 207     PsiElement value = element;
 208     if (value instanceof PsiExpression) {
 209       value = PsiUtil.deparenthesizeExpression((PsiExpression)value);
 210     }
 211     if (value instanceof PsiLiteralExpression) {
 212       return ((PsiLiteralExpression)value).getValue() == null ? DfaUtil.Nullness.NULL : DfaUtil.Nullness.NOT_NULL;
 213     }
 214
 215     // not null
 216     if (value instanceof PsiNewExpression) return DfaUtil.Nullness.NOT_NULL;
 217     if (value instanceof PsiThisExpression) return DfaUtil.Nullness.NOT_NULL;
 218     if (value instanceof PsiMethodCallExpression) {
 219       PsiMethod method = ((PsiMethodCallExpression)value).resolveMethod();
 220       if (method != null && AnnotationUtil.isNotNull(method)) return DfaUtil.Nullness.NOT_NULL;
 221       if (method != null && AnnotationUtil.isNullable(method)) return DfaUtil.Nullness.NULL;
 222     }
 223     if (value instanceof PsiBinaryExpression && ((PsiBinaryExpression)value).getOperationTokenType() == JavaTokenType.PLUS) {
 224       return DfaUtil.Nullness.NOT_NULL; // "xxx" + var
 225     }
 226
 227     // unfortunately have to resolve here, since there can be no subnodes
 228     PsiElement context = value;
 229     if (value instanceof PsiReference) {
 230       PsiElement resolved = ((PsiReference)value).resolve();
 231       if (resolved instanceof PsiCompiledElement) {
 232         resolved = resolved.getNavigationElement();
 233       }
 234       value = resolved;
 235     }
 236     if (value instanceof PsiParameter && ((PsiParameter)value).getDeclarationScope() instanceof PsiCatchSection) {
 237       // exception thrown is always not null
 238       return DfaUtil.Nullness.NOT_NULL;
 239     }
 240     if (value instanceof PsiModifierListOwner) {
 241       if (AnnotationUtil.isNotNull((PsiModifierListOwner)value)) return DfaUtil.Nullness.NOT_NULL;
 242       if (AnnotationUtil.isNullable((PsiModifierListOwner)value)) return DfaUtil.Nullness.NULL;
 243     }
 244
 245     if (value instanceof PsiLocalVariable || value instanceof PsiParameter) {
 246       return DfaUtil.checkNullness((PsiVariable)value, context);
 247     }
 248     return null;
 249   }
 250
 251   public static class NullAnalysisResult {
 252     public final Collection<PsiElement> nulls = new THashSet<PsiElement>(SliceLeafAnalyzer.LEAF_ELEMENT_EQUALITY);
 253     public final Collection<PsiElement> notNulls = new THashSet<PsiElement>(SliceLeafAnalyzer.LEAF_ELEMENT_EQUALITY);
 254     public final Collection<PsiElement> unknown = new THashSet<PsiElement>(SliceLeafAnalyzer.LEAF_ELEMENT_EQUALITY);
 255
 256     public void clear() {
 257       nulls.clear();
 258       notNulls.clear();
 259       unknown.clear();
 260     }
 261
 262     public void add(NullAnalysisResult duplicate) {
 263       nulls.addAll(duplicate.nulls);
 264       notNulls.addAll(duplicate.notNulls);
 265       unknown.addAll(duplicate.unknown);
 266     }
 267   }
 268 }