java/java-impl/src/com/intellij/psi/impl/PsiSuperMethodImplUtil.java

   1 /*
   2  * Copyright 2000-2009 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.psi.impl;
  17
  18 import com.intellij.openapi.util.Key;
  19 import com.intellij.openapi.util.Pair;
  20 import com.intellij.openapi.util.UserDataHolderEx;
  21 import com.intellij.psi.*;
  22 import com.intellij.psi.impl.source.HierarchicalMethodSignatureImpl;
  23 import com.intellij.psi.search.searches.DeepestSuperMethodsSearch;
  24 import com.intellij.psi.search.searches.SuperMethodsSearch;
  25 import com.intellij.psi.util.*;
  26 import com.intellij.util.SmartList;
  27 import gnu.trove.THashMap;
  28 import gnu.trove.THashSet;
  29 import gnu.trove.TObjectHashingStrategy;
  30 import org.jetbrains.annotations.NotNull;
  31 import org.jetbrains.annotations.Nullable;
  32
  33 import java.util.*;
  34
  35 public class PsiSuperMethodImplUtil {
  36   private static final Key<CachedValue<Map<MethodSignature, HierarchicalMethodSignature>>> SIGNATURES_KEY = Key.create("MAP_KEY");
  37
  38   private PsiSuperMethodImplUtil() {
  39   }
  40
  41   @NotNull
  42   public static PsiMethod[] findSuperMethods(PsiMethod method) {
  43     return findSuperMethods(method, null);
  44   }
  45
  46   @NotNull
  47   public static PsiMethod[] findSuperMethods(PsiMethod method, boolean checkAccess) {
  48     if (!canHaveSuperMethod(method, checkAccess, false)) return PsiMethod.EMPTY_ARRAY;
  49     return findSuperMethodsInternal(method, null);
  50   }
  51
  52   @NotNull
  53   public static PsiMethod[] findSuperMethods(PsiMethod method, PsiClass parentClass) {
  54     if (!canHaveSuperMethod(method, true, false)) return PsiMethod.EMPTY_ARRAY;
  55     return findSuperMethodsInternal(method, parentClass);
  56   }
  57
  58
  59   @NotNull
  60   private static PsiMethod[] findSuperMethodsInternal(PsiMethod method, PsiClass parentClass) {
  61     List<MethodSignatureBackedByPsiMethod> outputMethods = findSuperMethodSignatures(method, parentClass, false);
  62
  63     return MethodSignatureUtil.convertMethodSignaturesToMethods(outputMethods);
  64   }
  65
  66   @NotNull
  67   public static List<MethodSignatureBackedByPsiMethod> findSuperMethodSignaturesIncludingStatic(PsiMethod method,
  68                                                                                                          boolean checkAccess) {
  69     if (!canHaveSuperMethod(method, checkAccess, true)) return Collections.emptyList();
  70     return findSuperMethodSignatures(method, null, true);
  71   }
  72
  73   @NotNull
  74   private static List<MethodSignatureBackedByPsiMethod> findSuperMethodSignatures(PsiMethod method,
  75                                                                                            PsiClass parentClass,
  76                                                                                            boolean allowStaticMethod) {
  77
  78     return new ArrayList<MethodSignatureBackedByPsiMethod>(SuperMethodsSearch.search(method, parentClass, true, allowStaticMethod).findAll());
  79   }
  80
  81   private static boolean canHaveSuperMethod(PsiMethod method, boolean checkAccess, boolean allowStaticMethod) {
  82     if (method.isConstructor()) return false;
  83     if (!allowStaticMethod && method.hasModifierProperty(PsiModifier.STATIC)) return false;
  84     if (checkAccess && method.hasModifierProperty(PsiModifier.PRIVATE)) return false;
  85     PsiClass parentClass = method.getContainingClass();
  86     return parentClass != null && !"java.lang.Object".equals(parentClass.getQualifiedName());
  87   }
  88
  89   @Nullable
  90   public static PsiMethod findDeepestSuperMethod(PsiMethod method) {
  91     if (!canHaveSuperMethod(method, true, false)) return null;
  92     return DeepestSuperMethodsSearch.search(method).findFirst();
  93   }
  94
  95   public static PsiMethod[] findDeepestSuperMethods(PsiMethod method) {
  96     if (!canHaveSuperMethod(method, true, false)) return PsiMethod.EMPTY_ARRAY;
  97     Collection<PsiMethod> collection = DeepestSuperMethodsSearch.search(method).findAll();
  98     return collection.toArray(new PsiMethod[collection.size()]);
  99   }
 100
 101   private static Map<MethodSignature, HierarchicalMethodSignature> buildMethodHierarchy(PsiClass aClass,
 102                                                                                         PsiSubstitutor substitutor,
 103                                                                                         final boolean includePrivates,
 104                                                                                         final Set<PsiClass> visited,
 105                                                                                         boolean isInRawContext) {
 106     Map<MethodSignature, HierarchicalMethodSignature> result = new LinkedHashMap<MethodSignature, HierarchicalMethodSignature>();
 107     final Map<MethodSignature, List<PsiMethod>> sameParameterErasureMethods = new THashMap<MethodSignature, List<PsiMethod>>(MethodSignatureUtil.METHOD_PARAMETERS_ERASURE_EQUALITY);
 108
 109     Map<MethodSignature, HierarchicalMethodSignatureImpl> map = new THashMap<MethodSignature, HierarchicalMethodSignatureImpl>(new TObjectHashingStrategy<MethodSignature>() {
 110       public int computeHashCode(MethodSignature signature) {
 111         return MethodSignatureUtil.METHOD_PARAMETERS_ERASURE_EQUALITY.computeHashCode(signature);
 112       }
 113
 114       public boolean equals(MethodSignature o1, MethodSignature o2) {
 115         if (!MethodSignatureUtil.METHOD_PARAMETERS_ERASURE_EQUALITY.equals(o1, o2)) return false;
 116         List<PsiMethod> list = sameParameterErasureMethods.get(o1);
 117         boolean toCheckReturnType = list != null && list.size() > 1;
 118         if (!toCheckReturnType) return true;
 119         PsiType returnType1 = ((MethodSignatureBackedByPsiMethod)o1).getMethod().getReturnType();
 120         PsiType returnType2 = ((MethodSignatureBackedByPsiMethod)o2).getMethod().getReturnType();
 121         if (returnType1 == null && returnType2 == null) return true;
 122         if (returnType1 == null || returnType2 == null) return false;
 123
 124         PsiType erasure1 = TypeConversionUtil.erasure(o1.getSubstitutor().substitute(returnType1));
 125         PsiType erasure2 = TypeConversionUtil.erasure(o2.getSubstitutor().substitute(returnType2));
 126         return erasure1.equals(erasure2);
 127       }
 128     });
 129
 130     for (PsiMethod method : aClass.getMethods()) {
 131       if (!includePrivates && method.hasModifierProperty(PsiModifier.PRIVATE)) continue;
 132       final MethodSignatureBackedByPsiMethod signature = MethodSignatureBackedByPsiMethod.create(method, substitutor, isInRawContext);
 133       HierarchicalMethodSignatureImpl newH = new HierarchicalMethodSignatureImpl(signature);
 134
 135       List<PsiMethod> list = sameParameterErasureMethods.get(signature);
 136       if (list == null) {
 137         list = new SmartList<PsiMethod>();
 138         sameParameterErasureMethods.put(signature, list);
 139       }
 140       list.add(method);
 141
 142       result.put(signature, newH);
 143       map.put(signature, newH);
 144     }
 145
 146     for (PsiClassType superType : aClass.getSuperTypes()) {
 147       PsiClassType.ClassResolveResult superTypeResolveResult = superType.resolveGenerics();
 148       PsiClass superClass = superTypeResolveResult.getElement();
 149       if (superClass == null) continue;
 150       if (!visited.add(superClass)) continue; // cyclic inheritance
 151       final PsiSubstitutor superSubstitutor = superTypeResolveResult.getSubstitutor();
 152       PsiSubstitutor finalSubstitutor = obtainFinalSubstitutor(superClass, superSubstitutor, substitutor);
 153
 154       final boolean isInRawContextSuper = (isInRawContext || PsiUtil.isRawSubstitutor(superClass, superSubstitutor)) && superClass.getTypeParameters().length != 0;
 155       Map<MethodSignature, HierarchicalMethodSignature> superResult = buildMethodHierarchy(superClass, finalSubstitutor, false, visited, isInRawContextSuper);
 156       visited.remove(superClass);
 157
 158       List<Pair<MethodSignature, HierarchicalMethodSignature>> flattened = new ArrayList<Pair<MethodSignature, HierarchicalMethodSignature>>();
 159       for (Map.Entry<MethodSignature, HierarchicalMethodSignature> entry : superResult.entrySet()) {
 160         HierarchicalMethodSignature hms = entry.getValue();
 161         MethodSignature signature = entry.getKey();
 162         PsiClass containingClass = hms.getMethod().getContainingClass();
 163         List<HierarchicalMethodSignature> supers = new ArrayList<HierarchicalMethodSignature>(hms.getSuperSignatures());
 164         for (HierarchicalMethodSignature aSuper : supers) {
 165           PsiClass superContainingClass = aSuper.getMethod().getContainingClass();
 166           if (containingClass != null && superContainingClass != null && !containingClass.isInheritor(superContainingClass, true)) {
 167             // methods must be inherited from unrelated classes, so flatten hierarchy here
 168             // class C implements SAM1, SAM2 { void methodimpl() {} }
 169             //hms.getSuperSignatures().remove(aSuper);
 170             flattened.add(new Pair<MethodSignature, HierarchicalMethodSignature>(signature, aSuper));
 171           }
 172         }
 173         putInMap(aClass, result, map, hms, signature);
 174       }
 175       for (Pair<MethodSignature, HierarchicalMethodSignature> pair : flattened) {
 176         putInMap(aClass, result, map, pair.second, pair.first);
 177       }
 178     }
 179
 180
 181     for (Map.Entry<MethodSignature, HierarchicalMethodSignatureImpl> entry : map.entrySet()) {
 182       HierarchicalMethodSignatureImpl hierarchicalMethodSignature = entry.getValue();
 183       MethodSignature methodSignature = entry.getKey();
 184       if (result.get(methodSignature) == null && PsiUtil.isAccessible(hierarchicalMethodSignature.getMethod(), aClass, aClass)) {
 185         result.put(methodSignature, hierarchicalMethodSignature);
 186       }
 187     }
 188
 189     return result;
 190   }
 191
 192   private static void putInMap(PsiClass aClass, Map<MethodSignature, HierarchicalMethodSignature> result,
 193                            Map<MethodSignature, HierarchicalMethodSignatureImpl> map, HierarchicalMethodSignature hierarchicalMethodSignature,
 194                            MethodSignature signature) {
 195     if (!PsiUtil.isAccessible(hierarchicalMethodSignature.getMethod(), aClass, aClass)) return;
 196     HierarchicalMethodSignatureImpl existing = map.get(signature);
 197     if (existing == null) {
 198       map.put(signature, copy(hierarchicalMethodSignature));
 199     }
 200     else if (isReturnTypeIsMoreSpecificThan(hierarchicalMethodSignature, existing) && isSuperMethod(aClass, hierarchicalMethodSignature, existing)) {
 201       HierarchicalMethodSignatureImpl newSuper = copy(hierarchicalMethodSignature);
 202       mergeSupers(newSuper, existing);
 203       map.put(signature, newSuper);
 204     }
 205     else if (isSuperMethod(aClass, existing, hierarchicalMethodSignature)) {
 206       mergeSupers(existing, hierarchicalMethodSignature);
 207     }
 208     // just drop an invalid method declaration there - to highlight accordingly
 209     else if (!result.containsKey(signature)) {
 210       result.put(signature, hierarchicalMethodSignature);
 211     }
 212   }
 213
 214   private static boolean isReturnTypeIsMoreSpecificThan(@NotNull HierarchicalMethodSignature thisSig, @NotNull HierarchicalMethodSignature thatSig) {
 215     PsiType thisRet = thisSig.getMethod().getReturnType();
 216     PsiType thatRet = thatSig.getMethod().getReturnType();
 217     return thatRet != null && thisRet != null && !thatRet.equals(thisRet) && TypeConversionUtil.isAssignable(thatRet, thisRet);
 218   }
 219
 220   private static void mergeSupers(final HierarchicalMethodSignatureImpl existing, final HierarchicalMethodSignature superSignature) {
 221     for (HierarchicalMethodSignature existingSuper : existing.getSuperSignatures()) {
 222       if (existingSuper.getMethod() == superSignature.getMethod()) {
 223         for (HierarchicalMethodSignature signature : superSignature.getSuperSignatures()) {
 224           mergeSupers((HierarchicalMethodSignatureImpl)existingSuper, signature);
 225         }
 226         return;
 227       }
 228     }
 229     if (existing.getMethod() == superSignature.getMethod()) {
 230       List<HierarchicalMethodSignature> existingSupers = existing.getSuperSignatures();
 231       for (HierarchicalMethodSignature supers : superSignature.getSuperSignatures()) {
 232         if (!existingSupers.contains(supers)) existing.addSuperSignature(copy(supers));
 233       }
 234     }
 235     else {
 236       HierarchicalMethodSignatureImpl copy = copy(superSignature);
 237       existing.addSuperSignature(copy);
 238     }
 239   }
 240
 241   private static boolean isSuperMethod(PsiClass aClass,
 242                                        HierarchicalMethodSignature hierarchicalMethodSignature,
 243                                        HierarchicalMethodSignature superSignatureHierarchical) {
 244     PsiMethod superMethod = superSignatureHierarchical.getMethod();
 245     PsiClass superClass = superMethod.getContainingClass();
 246     PsiClass containingClass = hierarchicalMethodSignature.getMethod().getContainingClass();
 247     return !superMethod.isConstructor()
 248            && !aClass.equals(superClass)
 249            && PsiUtil.isAccessible(superMethod, aClass, aClass)
 250            && MethodSignatureUtil.isSubsignature(superSignatureHierarchical, hierarchicalMethodSignature)
 251            && superClass != null
 252            && (containingClass != null && containingClass.isInterface() == superClass.isInterface() || superClass.isInterface() || "java.lang.Object".equals(superClass.getQualifiedName()))
 253       ;
 254   }
 255
 256   private static HierarchicalMethodSignatureImpl copy(HierarchicalMethodSignature hi) {
 257     HierarchicalMethodSignatureImpl hierarchicalMethodSignature = new HierarchicalMethodSignatureImpl(hi);
 258     for (HierarchicalMethodSignature his : hi.getSuperSignatures()) {
 259       hierarchicalMethodSignature.addSuperSignature(copy(his));
 260     }
 261     return hierarchicalMethodSignature;
 262   }
 263
 264   private static PsiSubstitutor obtainFinalSubstitutor(PsiClass superClass,
 265                                                        PsiSubstitutor superSubstitutor,
 266                                                        PsiSubstitutor derivedSubstitutor) {
 267     Map<PsiTypeParameter, PsiType> map = null;
 268     for (PsiTypeParameter typeParameter : PsiUtil.typeParametersIterable(superClass)) {
 269       PsiType type = superSubstitutor.substitute(typeParameter);
 270       final PsiType t = derivedSubstitutor.substitute(type);
 271       if (map == null) {
 272         map = new THashMap<PsiTypeParameter, PsiType>();
 273       }
 274       map.put(typeParameter, t);
 275     }
 276
 277     return map == null ? PsiSubstitutor.EMPTY : JavaPsiFacade.getInstance(superClass.getProject()).getElementFactory().createSubstitutor(map);
 278   }
 279
 280   public static Collection<HierarchicalMethodSignature> getVisibleSignatures(PsiClass aClass) {
 281     Map<MethodSignature, HierarchicalMethodSignature> map = getSignaturesMap(aClass);
 282     return map.values();
 283   }
 284
 285   @NotNull public static HierarchicalMethodSignature getHierarchicalMethodSignature(PsiMethod method) {
 286     PsiClass aClass = method.getContainingClass();
 287     HierarchicalMethodSignature result = null;
 288     if (aClass != null) {
 289       result = getSignaturesMap(aClass).get(method.getSignature(PsiSubstitutor.EMPTY));
 290     }
 291     if (result == null) {
 292       result = new HierarchicalMethodSignatureImpl((MethodSignatureBackedByPsiMethod)method.getSignature(PsiSubstitutor.EMPTY));
 293     }
 294     return result;
 295   }
 296
 297   private static Map<MethodSignature, HierarchicalMethodSignature> getSignaturesMap(final PsiClass aClass) {
 298     CachedValue<Map<MethodSignature, HierarchicalMethodSignature>> value = aClass.getUserData(SIGNATURES_KEY);
 299     if (value == null) {
 300       BySignaturesCachedValueProvider provider = new BySignaturesCachedValueProvider(aClass);
 301       value = CachedValuesManager.getManager(aClass.getProject()).createCachedValue(provider, false);
 302       //Do not cache for nonphysical elements
 303       if (aClass.isPhysical()) {
 304         UserDataHolderEx dataHolder = (UserDataHolderEx)aClass;
 305         value = dataHolder.putUserDataIfAbsent(SIGNATURES_KEY, value);
 306       }
 307     }
 308
 309     return value.getValue();
 310   }
 311
 312   private static class BySignaturesCachedValueProvider implements CachedValueProvider<Map<MethodSignature, HierarchicalMethodSignature>> {
 313     private final PsiClass myClass;
 314
 315     private BySignaturesCachedValueProvider(final PsiClass aClass) {
 316       myClass = aClass;
 317     }
 318
 319     public Result<Map<MethodSignature, HierarchicalMethodSignature>> compute() {
 320       Map<MethodSignature, HierarchicalMethodSignature> result = buildMethodHierarchy(myClass, PsiSubstitutor.EMPTY, true, new THashSet<PsiClass>(), false);
 321       assert result != null;
 322
 323
 324       return new Result<Map<MethodSignature, HierarchicalMethodSignature>>(result, PsiModificationTracker.JAVA_STRUCTURE_MODIFICATION_COUNT);
 325     }
 326   }
 327 }