blob: e0db7701574d262bdece25ea787afe035400f7b3 [file] [log] [blame]
/*
* 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.psi.impl;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.progress.ProgressManager;
import com.intellij.openapi.project.Project;
import com.intellij.openapi.roots.ProjectRootModificationTracker;
import com.intellij.openapi.util.Key;
import com.intellij.openapi.util.Pair;
import com.intellij.psi.*;
import com.intellij.psi.impl.source.HierarchicalMethodSignatureImpl;
import com.intellij.psi.impl.source.PsiClassImpl;
import com.intellij.psi.search.searches.DeepestSuperMethodsSearch;
import com.intellij.psi.search.searches.SuperMethodsSearch;
import com.intellij.psi.util.*;
import com.intellij.util.*;
import gnu.trove.THashMap;
import gnu.trove.THashSet;
import gnu.trove.TObjectHashingStrategy;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;
import java.util.*;
public class PsiSuperMethodImplUtil {
private static final Logger LOG = Logger.getInstance("#com.intellij.psi.impl.PsiSuperMethodImplUtil");
private static final PsiCacheKey<Map<MethodSignature, HierarchicalMethodSignature>, PsiClass> SIGNATURES_FOR_CLASS_KEY = PsiCacheKey
.create("SIGNATURES_FOR_CLASS_KEY", new NotNullFunction<PsiClass, Map<MethodSignature, HierarchicalMethodSignature>>() {
@NotNull
@Override
public Map<MethodSignature, HierarchicalMethodSignature> fun(PsiClass dom) {
return buildMethodHierarchy(dom, PsiSubstitutor.EMPTY, true, new THashSet<PsiClass>(), false);
}
});
private PsiSuperMethodImplUtil() {
}
@NotNull
public static PsiMethod[] findSuperMethods(@NotNull PsiMethod method) {
return findSuperMethods(method, null);
}
@NotNull
public static PsiMethod[] findSuperMethods(@NotNull PsiMethod method, boolean checkAccess) {
if (!canHaveSuperMethod(method, checkAccess, false)) return PsiMethod.EMPTY_ARRAY;
return findSuperMethodsInternal(method, null);
}
@NotNull
public static PsiMethod[] findSuperMethods(@NotNull PsiMethod method, PsiClass parentClass) {
if (!canHaveSuperMethod(method, true, false)) return PsiMethod.EMPTY_ARRAY;
return findSuperMethodsInternal(method, parentClass);
}
@NotNull
private static PsiMethod[] findSuperMethodsInternal(@NotNull PsiMethod method, PsiClass parentClass) {
List<MethodSignatureBackedByPsiMethod> outputMethods = findSuperMethodSignatures(method, parentClass, false);
return MethodSignatureUtil.convertMethodSignaturesToMethods(outputMethods);
}
@NotNull
public static List<MethodSignatureBackedByPsiMethod> findSuperMethodSignaturesIncludingStatic(@NotNull PsiMethod method,
boolean checkAccess) {
if (!canHaveSuperMethod(method, checkAccess, true)) return Collections.emptyList();
return findSuperMethodSignatures(method, null, true);
}
@NotNull
private static List<MethodSignatureBackedByPsiMethod> findSuperMethodSignatures(@NotNull PsiMethod method,
PsiClass parentClass,
boolean allowStaticMethod) {
return new ArrayList<MethodSignatureBackedByPsiMethod>(SuperMethodsSearch.search(method, parentClass, true, allowStaticMethod).findAll());
}
private static boolean canHaveSuperMethod(@NotNull PsiMethod method, boolean checkAccess, boolean allowStaticMethod) {
if (method.isConstructor()) return false;
if (!allowStaticMethod && method.hasModifierProperty(PsiModifier.STATIC)) return false;
if (checkAccess && method.hasModifierProperty(PsiModifier.PRIVATE)) return false;
PsiClass parentClass = method.getContainingClass();
return parentClass != null && !CommonClassNames.JAVA_LANG_OBJECT.equals(parentClass.getQualifiedName());
}
@Nullable
public static PsiMethod findDeepestSuperMethod(@NotNull PsiMethod method) {
if (!canHaveSuperMethod(method, true, false)) return null;
return DeepestSuperMethodsSearch.search(method).findFirst();
}
@NotNull
public static PsiMethod[] findDeepestSuperMethods(@NotNull PsiMethod method) {
if (!canHaveSuperMethod(method, true, false)) return PsiMethod.EMPTY_ARRAY;
Collection<PsiMethod> collection = DeepestSuperMethodsSearch.search(method).findAll();
return collection.toArray(new PsiMethod[collection.size()]);
}
@NotNull
private static Map<MethodSignature, HierarchicalMethodSignature> buildMethodHierarchy(@NotNull PsiClass aClass,
@NotNull PsiSubstitutor substitutor,
final boolean includePrivates,
@NotNull final Set<PsiClass> visited,
boolean isInRawContext) {
ProgressManager.checkCanceled();
Map<MethodSignature, HierarchicalMethodSignature> result = new LinkedHashMap<MethodSignature, HierarchicalMethodSignature>();
final Map<MethodSignature, List<PsiMethod>> sameParameterErasureMethods = new THashMap<MethodSignature, List<PsiMethod>>(MethodSignatureUtil.METHOD_PARAMETERS_ERASURE_EQUALITY);
Map<MethodSignature, HierarchicalMethodSignatureImpl> map = new THashMap<MethodSignature, HierarchicalMethodSignatureImpl>(new TObjectHashingStrategy<MethodSignature>() {
@Override
public int computeHashCode(MethodSignature signature) {
return MethodSignatureUtil.METHOD_PARAMETERS_ERASURE_EQUALITY.computeHashCode(signature);
}
@Override
public boolean equals(MethodSignature o1, MethodSignature o2) {
if (!MethodSignatureUtil.METHOD_PARAMETERS_ERASURE_EQUALITY.equals(o1, o2)) return false;
List<PsiMethod> list = sameParameterErasureMethods.get(o1);
boolean toCheckReturnType = list != null && list.size() > 1;
if (!toCheckReturnType) return true;
PsiType returnType1 = ((MethodSignatureBackedByPsiMethod)o1).getMethod().getReturnType();
PsiType returnType2 = ((MethodSignatureBackedByPsiMethod)o2).getMethod().getReturnType();
if (returnType1 == null && returnType2 == null) return true;
if (returnType1 == null || returnType2 == null) return false;
PsiType erasure1 = TypeConversionUtil.erasure(o1.getSubstitutor().substitute(returnType1));
PsiType erasure2 = TypeConversionUtil.erasure(o2.getSubstitutor().substitute(returnType2));
return erasure1.equals(erasure2);
}
});
PsiMethod[] methods = aClass.getMethods();
if (aClass instanceof PsiClassImpl) {
final PsiMethod valuesMethod = ((PsiClassImpl)aClass).getValuesMethod();
if (valuesMethod != null) {
methods = ArrayUtil.append(methods, valuesMethod);
}
}
for (PsiMethod method : methods) {
if (!method.isValid()) {
throw new PsiInvalidElementAccessException(method, "class.valid=" + aClass.isValid() + "; name=" + method.getName());
}
if (!includePrivates && method.hasModifierProperty(PsiModifier.PRIVATE)) continue;
final MethodSignatureBackedByPsiMethod signature = MethodSignatureBackedByPsiMethod.create(method, substitutor, isInRawContext);
HierarchicalMethodSignatureImpl newH = new HierarchicalMethodSignatureImpl(signature);
List<PsiMethod> list = sameParameterErasureMethods.get(signature);
if (list == null) {
list = new SmartList<PsiMethod>();
sameParameterErasureMethods.put(signature, list);
}
list.add(method);
LOG.assertTrue(newH.getMethod().isValid());
result.put(signature, newH);
map.put(signature, newH);
}
for (PsiClassType superType : aClass.getSuperTypes()) {
PsiClassType.ClassResolveResult superTypeResolveResult = superType.resolveGenerics();
PsiClass superClass = superTypeResolveResult.getElement();
if (superClass == null) continue;
if (!visited.add(superClass)) continue; // cyclic inheritance
final PsiSubstitutor superSubstitutor = superTypeResolveResult.getSubstitutor();
PsiSubstitutor finalSubstitutor = obtainFinalSubstitutor(superClass, superSubstitutor, substitutor, isInRawContext);
final boolean isInRawContextSuper = (isInRawContext || PsiUtil.isRawSubstitutor(superClass, superSubstitutor)) && superClass.getTypeParameters().length != 0;
Map<MethodSignature, HierarchicalMethodSignature> superResult = buildMethodHierarchy(superClass, finalSubstitutor, false, visited, isInRawContextSuper);
visited.remove(superClass);
List<Pair<MethodSignature, HierarchicalMethodSignature>> flattened = new ArrayList<Pair<MethodSignature, HierarchicalMethodSignature>>();
for (Map.Entry<MethodSignature, HierarchicalMethodSignature> entry : superResult.entrySet()) {
HierarchicalMethodSignature hms = entry.getValue();
MethodSignature signature = entry.getKey();
PsiClass containingClass = hms.getMethod().getContainingClass();
List<HierarchicalMethodSignature> supers = new ArrayList<HierarchicalMethodSignature>(hms.getSuperSignatures());
for (HierarchicalMethodSignature aSuper : supers) {
PsiClass superContainingClass = aSuper.getMethod().getContainingClass();
if (containingClass != null && superContainingClass != null && !containingClass.isInheritor(superContainingClass, true)) {
// methods must be inherited from unrelated classes, so flatten hierarchy here
// class C implements SAM1, SAM2 { void methodimpl() {} }
//hms.getSuperSignatures().remove(aSuper);
flattened.add(Pair.create(signature, aSuper));
}
}
putInMap(aClass, result, map, hms, signature);
}
for (Pair<MethodSignature, HierarchicalMethodSignature> pair : flattened) {
putInMap(aClass, result, map, pair.second, pair.first);
}
}
for (Map.Entry<MethodSignature, HierarchicalMethodSignatureImpl> entry : map.entrySet()) {
HierarchicalMethodSignatureImpl hierarchicalMethodSignature = entry.getValue();
MethodSignature methodSignature = entry.getKey();
if (result.get(methodSignature) == null && PsiUtil.isAccessible(aClass.getProject(), hierarchicalMethodSignature.getMethod(), aClass, aClass)) {
LOG.assertTrue(hierarchicalMethodSignature.getMethod().isValid());
result.put(methodSignature, hierarchicalMethodSignature);
}
}
return result;
}
private static void putInMap(@NotNull PsiClass aClass,
@NotNull Map<MethodSignature, HierarchicalMethodSignature> result,
@NotNull Map<MethodSignature, HierarchicalMethodSignatureImpl> map,
@NotNull HierarchicalMethodSignature hierarchicalMethodSignature,
@NotNull MethodSignature signature) {
if (!PsiUtil.isAccessible(aClass.getProject(), hierarchicalMethodSignature.getMethod(), aClass, aClass)) return;
HierarchicalMethodSignatureImpl existing = map.get(signature);
if (existing == null) {
HierarchicalMethodSignatureImpl copy = copy(hierarchicalMethodSignature);
LOG.assertTrue(copy.getMethod().isValid());
map.put(signature, copy);
}
else if (isReturnTypeIsMoreSpecificThan(hierarchicalMethodSignature, existing) && isSuperMethod(aClass, hierarchicalMethodSignature, existing)) {
HierarchicalMethodSignatureImpl newSuper = copy(hierarchicalMethodSignature);
mergeSupers(newSuper, existing);
LOG.assertTrue(newSuper.getMethod().isValid());
map.put(signature, newSuper);
}
else if (isSuperMethod(aClass, existing, hierarchicalMethodSignature)) {
mergeSupers(existing, hierarchicalMethodSignature);
}
// just drop an invalid method declaration there - to highlight accordingly
else if (!result.containsKey(signature)) {
LOG.assertTrue(hierarchicalMethodSignature.getMethod().isValid());
result.put(signature, hierarchicalMethodSignature);
}
}
private static boolean isReturnTypeIsMoreSpecificThan(@NotNull HierarchicalMethodSignature thisSig, @NotNull HierarchicalMethodSignature thatSig) {
PsiType thisRet = thisSig.getSubstitutor().substitute(thisSig.getMethod().getReturnType());
PsiType thatRet = thatSig.getSubstitutor().substitute(thatSig.getMethod().getReturnType());
return thatRet != null && thisRet != null && !thatRet.equals(thisRet) && TypeConversionUtil.isAssignable(thatRet, thisRet, false);
}
private static void mergeSupers(@NotNull HierarchicalMethodSignatureImpl existing, @NotNull HierarchicalMethodSignature superSignature) {
for (HierarchicalMethodSignature existingSuper : existing.getSuperSignatures()) {
if (existingSuper.getMethod() == superSignature.getMethod()) {
for (HierarchicalMethodSignature signature : superSignature.getSuperSignatures()) {
mergeSupers((HierarchicalMethodSignatureImpl)existingSuper, signature);
}
return;
}
}
if (existing.getMethod() == superSignature.getMethod()) {
List<HierarchicalMethodSignature> existingSupers = existing.getSuperSignatures();
for (HierarchicalMethodSignature supers : superSignature.getSuperSignatures()) {
if (!existingSupers.contains(supers)) existing.addSuperSignature(copy(supers));
}
}
else {
HierarchicalMethodSignatureImpl copy = copy(superSignature);
existing.addSuperSignature(copy);
}
}
private static boolean isSuperMethod(@NotNull PsiClass aClass,
@NotNull HierarchicalMethodSignature hierarchicalMethodSignature,
@NotNull HierarchicalMethodSignature superSignatureHierarchical) {
PsiMethod superMethod = superSignatureHierarchical.getMethod();
PsiClass superClass = superMethod.getContainingClass();
PsiClass containingClass = hierarchicalMethodSignature.getMethod().getContainingClass();
if (!superMethod.isConstructor()) {
if (!aClass.equals(superClass)) {
if (PsiUtil.isAccessible(aClass.getProject(), superMethod, aClass, aClass)) {
if (MethodSignatureUtil.isSubsignature(superSignatureHierarchical, hierarchicalMethodSignature)) {
if (superClass != null) {
if (superClass.isInterface() ||
CommonClassNames.JAVA_LANG_OBJECT.equals(superClass.getQualifiedName())) {
if (superMethod.hasModifierProperty(PsiModifier.STATIC)) {
return false;
}
if (superMethod.hasModifierProperty(PsiModifier.DEFAULT) ||
hierarchicalMethodSignature.getMethod().hasModifierProperty(PsiModifier.DEFAULT)) {
return !InheritanceUtil.isInheritorOrSelf(superClass, containingClass, true);
}
return true;
}
if (containingClass != null) {
if (containingClass.isInterface()) {
return false;
}
if (!aClass.isInterface() && !InheritanceUtil.isInheritorOrSelf(superClass, containingClass, true)) {
return true;
}
}
}
}
}
}
}
return false;
}
@NotNull
private static HierarchicalMethodSignatureImpl copy(@NotNull HierarchicalMethodSignature hi) {
HierarchicalMethodSignatureImpl hierarchicalMethodSignature = new HierarchicalMethodSignatureImpl(hi);
for (HierarchicalMethodSignature his : hi.getSuperSignatures()) {
hierarchicalMethodSignature.addSuperSignature(copy(his));
}
return hierarchicalMethodSignature;
}
@NotNull
private static PsiSubstitutor obtainFinalSubstitutor(@NotNull PsiClass superClass,
@NotNull PsiSubstitutor superSubstitutor,
@NotNull PsiSubstitutor derivedSubstitutor,
boolean inRawContext) {
if (inRawContext) {
Set<PsiTypeParameter> typeParams = superSubstitutor.getSubstitutionMap().keySet();
PsiElementFactory factory = JavaPsiFacade.getElementFactory(superClass.getProject());
superSubstitutor = factory.createRawSubstitutor(derivedSubstitutor, typeParams.toArray(new PsiTypeParameter[typeParams.size()]));
}
Map<PsiTypeParameter, PsiType> map = null;
for (PsiTypeParameter typeParameter : PsiUtil.typeParametersIterable(superClass)) {
PsiType type = superSubstitutor.substitute(typeParameter);
final PsiType t = derivedSubstitutor.substitute(type);
if (map == null) {
map = new THashMap<PsiTypeParameter, PsiType>();
}
map.put(typeParameter, t);
}
return map == null ? PsiSubstitutor.EMPTY : JavaPsiFacade.getInstance(superClass.getProject()).getElementFactory().createSubstitutor(map);
}
@NotNull
public static Collection<HierarchicalMethodSignature> getVisibleSignatures(@NotNull PsiClass aClass) {
Map<MethodSignature, HierarchicalMethodSignature> map = getSignaturesMap(aClass);
return map.values();
}
@NotNull
public static HierarchicalMethodSignature getHierarchicalMethodSignature(@NotNull final PsiMethod method) {
Project project = method.getProject();
return CachedValuesManager.getManager(project).getParameterizedCachedValue(method, HIERARCHICAL_SIGNATURE_KEY,
HIERARCHICAL_SIGNATURE_PROVIDER, false, method);
}
private static final Key<ParameterizedCachedValue<HierarchicalMethodSignature, PsiMethod>> HIERARCHICAL_SIGNATURE_KEY = Key.create("HierarchicalMethodSignature");
private static final ParameterizedCachedValueProvider<HierarchicalMethodSignature, PsiMethod> HIERARCHICAL_SIGNATURE_PROVIDER =
new ParameterizedCachedValueProvider<HierarchicalMethodSignature, PsiMethod>() {
@Override
public CachedValueProvider.Result<HierarchicalMethodSignature> compute(PsiMethod method) {
PsiClass aClass = method.getContainingClass();
HierarchicalMethodSignature result = null;
if (aClass != null) {
result = getSignaturesMap(aClass).get(method.getSignature(PsiSubstitutor.EMPTY));
}
if (result == null) {
result = new HierarchicalMethodSignatureImpl((MethodSignatureBackedByPsiMethod)method.getSignature(PsiSubstitutor.EMPTY));
}
Project project = aClass == null ? method.getProject() : aClass.getProject();
// cache Cls method hierarchy until root changed
Object dependency = method instanceof PsiCompiledElement ? ProjectRootModificationTracker.getInstance(project) :
PsiModificationTracker.JAVA_STRUCTURE_MODIFICATION_COUNT;
return CachedValueProvider.Result.create(result, dependency);
}
};
@NotNull
private static Map<MethodSignature, HierarchicalMethodSignature> getSignaturesMap(@NotNull PsiClass aClass) {
return SIGNATURES_FOR_CLASS_KEY.getValue(aClass);
}
// uses hierarchy signature tree if available, traverses class structure by itself otherwise
public static boolean processDirectSuperMethodsSmart(@NotNull PsiMethod method, @NotNull Processor<PsiMethod> superMethodProcessor) {
//boolean old = PsiSuperMethodUtil.isSuperMethod(method, superMethod);
PsiClass aClass = method.getContainingClass();
if (aClass == null) return false;
if (!canHaveSuperMethod(method, true, false)) return false;
Map<MethodSignature, HierarchicalMethodSignature> cachedMap = SIGNATURES_FOR_CLASS_KEY.getCachedValueOrNull(aClass);
if (cachedMap != null) {
HierarchicalMethodSignature signature = cachedMap.get(method.getSignature(PsiSubstitutor.EMPTY));
if (signature != null) {
List<HierarchicalMethodSignature> superSignatures = signature.getSuperSignatures();
for (HierarchicalMethodSignature superSignature : superSignatures) {
if (!superMethodProcessor.process(superSignature.getMethod())) return false;
}
return true;
}
}
PsiClassType[] directSupers = aClass.getSuperTypes();
for (PsiClassType directSuper : directSupers) {
PsiClassType.ClassResolveResult resolveResult = directSuper.resolveGenerics();
if (resolveResult.getSubstitutor() != PsiSubstitutor.EMPTY) {
// generics
break;
}
PsiClass directSuperClass = resolveResult.getElement();
if (directSuperClass == null) continue;
PsiMethod[] candidates = directSuperClass.findMethodsBySignature(method, false);
for (PsiMethod candidate : candidates) {
if (PsiUtil.canBeOverriden(candidate)) {
if (!superMethodProcessor.process(candidate)) return false;
}
}
return true;
}
List<HierarchicalMethodSignature> superSignatures = method.getHierarchicalMethodSignature().getSuperSignatures();
for (HierarchicalMethodSignature superSignature : superSignatures) {
if (!superMethodProcessor.process(superSignature.getMethod())) return false;
}
return true;
}
// uses hierarchy signature tree if available, traverses class structure by itself otherwise
public static boolean isSuperMethodSmart(@NotNull PsiMethod method, @NotNull PsiMethod superMethod) {
//boolean old = PsiSuperMethodUtil.isSuperMethod(method, superMethod);
if (method == superMethod) return false;
PsiClass aClass = method.getContainingClass();
PsiClass superClass = superMethod.getContainingClass();
if (aClass == null || superClass == null || superClass == aClass) return false;
if (!canHaveSuperMethod(method, true, false)) return false;
PsiMethod[] superMethods = null;
Map<MethodSignature, HierarchicalMethodSignature> cachedMap = SIGNATURES_FOR_CLASS_KEY.getCachedValueOrNull(aClass);
if (cachedMap != null) {
HierarchicalMethodSignature signature = cachedMap.get(method.getSignature(PsiSubstitutor.EMPTY));
if (signature != null) {
superMethods = MethodSignatureUtil.convertMethodSignaturesToMethods(signature.getSuperSignatures());
}
}
if (superMethods == null) {
PsiClassType[] directSupers = aClass.getSuperTypes();
List<PsiMethod> found = null;
boolean canceled = false;
for (PsiClassType directSuper : directSupers) {
PsiClassType.ClassResolveResult resolveResult = directSuper.resolveGenerics();
if (resolveResult.getSubstitutor() != PsiSubstitutor.EMPTY) {
// generics
canceled = true;
break;
}
PsiClass directSuperClass = resolveResult.getElement();
if (directSuperClass == null) continue;
PsiMethod[] candidates = directSuperClass.findMethodsBySignature(method, false);
if (candidates.length != 0) {
if (found == null) found = new ArrayList<PsiMethod>();
for (PsiMethod candidate : candidates) {
if (PsiUtil.canBeOverriden(candidate)) found.add(candidate);
}
}
}
superMethods = canceled ? null : found == null ? PsiMethod.EMPTY_ARRAY : found.toArray(new PsiMethod[found.size()]);
}
if (superMethods == null) {
superMethods = MethodSignatureUtil.convertMethodSignaturesToMethods(method.getHierarchicalMethodSignature().getSuperSignatures());
}
for (PsiMethod superCandidate : superMethods) {
if (superMethod.equals(superCandidate) || isSuperMethodSmart(superCandidate, superMethod)) return true;
}
return false;
}
}