inference: don't distinguish parameterizations with 2 different interfaces (IDEA...
[idea/community.git] / java / java-psi-api / src / com / intellij / psi / util / TypesDistinctProver.java
1 /*
2  * Copyright 2000-2016 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.util;
17
18 import com.intellij.openapi.util.Comparing;
19 import com.intellij.psi.*;
20 import com.intellij.util.containers.HashSet;
21
22 import java.util.Set;
23
24 /**
25  * User: anna
26  * Date: Aug 12, 2010
27  */
28 public class TypesDistinctProver {
29   public static final Set<String> ARRAY_SUPER_CLASSES = new HashSet<String>();
30   static {
31     ARRAY_SUPER_CLASSES.add(CommonClassNames.JAVA_IO_SERIALIZABLE);
32     ARRAY_SUPER_CLASSES.add(CommonClassNames.JAVA_LANG_CLONEABLE);
33     ARRAY_SUPER_CLASSES.add(CommonClassNames.JAVA_LANG_OBJECT);
34   }
35
36   private TypesDistinctProver() {
37   }
38
39   public static boolean provablyDistinct(PsiType type1, PsiType type2) {
40     return provablyDistinct(type1, type2, 0);
41   }
42
43   protected static boolean provablyDistinct(PsiType type1, PsiType type2, int level) {
44     if (type1 instanceof PsiWildcardType) {
45       if (type2 instanceof PsiWildcardType) {
46         return provablyDistinct((PsiWildcardType)type1, (PsiWildcardType)type2, true, level);
47       }
48
49       if (level > 1) return true;
50       if (type2 instanceof PsiCapturedWildcardType) {
51         return provablyDistinct((PsiWildcardType)type1, ((PsiCapturedWildcardType)type2).getWildcard(), false, level);
52       }
53
54       if (type2 instanceof PsiClassType) {
55         final PsiClass psiClass2 = PsiUtil.resolveClassInType(type2);
56         if (psiClass2 == null) return false;
57
58         if (((PsiWildcardType)type1).isExtends()) {
59           final PsiType extendsBound = ((PsiWildcardType)type1).getExtendsBound();
60           if (extendsBound instanceof PsiArrayType &&
61               proveArrayTypeDistinct((PsiArrayType)extendsBound, type2)) return true;
62           final PsiClass boundClass1 = PsiUtil.resolveClassInType(extendsBound);
63           if (boundClass1 == null) return false;
64
65           if (CommonClassNames.JAVA_LANG_OBJECT.equals(psiClass2.getQualifiedName()) && !(boundClass1 instanceof PsiTypeParameter)) {
66             return !CommonClassNames.JAVA_LANG_OBJECT.equals(boundClass1.getQualifiedName());
67           }
68
69           return proveExtendsBoundsDistinct(type1, type2, boundClass1, psiClass2);
70         }
71
72         if (((PsiWildcardType)type1).isSuper()) {
73           final PsiType superBound = ((PsiWildcardType)type1).getSuperBound();
74           if (superBound instanceof PsiArrayType &&
75               proveArrayTypeDistinct((PsiArrayType)superBound, type2)) return true;
76
77           final PsiClass boundClass1 = PsiUtil.resolveClassInType(superBound);
78           if (boundClass1 == null) return false;
79           if (boundClass1 instanceof PsiTypeParameter) {
80             final PsiClassType[] extendsListTypes = boundClass1.getExtendsListTypes();
81             for (PsiClassType classType : extendsListTypes) {
82               final PsiClass psiClass = classType.resolve();
83               if (InheritanceUtil.isInheritorOrSelf(psiClass, psiClass2, true) || InheritanceUtil.isInheritorOrSelf(psiClass2, psiClass, true)) return false;
84             }
85             return extendsListTypes.length > 0;
86           }
87
88           return !InheritanceUtil.isInheritorOrSelf(boundClass1, psiClass2, true);
89         }
90
91         final PsiType bound = ((PsiWildcardType)type1).getBound();
92         return bound != null && !bound.equals(psiClass2);
93       }
94       
95       if (type2 instanceof PsiArrayType) {
96         return proveArrayTypeDistinct((PsiArrayType)type2, type1);
97       }
98     } else {
99
100       if (type2 instanceof PsiWildcardType) return provablyDistinct(type2, type1, level);
101
102       if (type1 instanceof PsiCapturedWildcardType) return provablyDistinct(((PsiCapturedWildcardType)type1).getWildcard(), type2, level);
103       if (type2 instanceof PsiCapturedWildcardType) return provablyDistinct(type2, type1, level);
104     }
105
106
107     final PsiClassType.ClassResolveResult classResolveResult1 = PsiUtil.resolveGenericsClassInType(type1);
108     final PsiClassType.ClassResolveResult classResolveResult2 = PsiUtil.resolveGenericsClassInType(type2);
109
110     final PsiClass boundClass1 = classResolveResult1.getElement();
111     final PsiClass boundClass2 = classResolveResult2.getElement();
112
113     if (boundClass1 instanceof PsiTypeParameter && level < 2) {
114       if (!distinguishFromTypeParam((PsiTypeParameter)boundClass1, boundClass2, type1)) return false;
115     }
116
117     if (boundClass2 instanceof PsiTypeParameter && level < 2) {
118       if (!distinguishFromTypeParam((PsiTypeParameter)boundClass2, boundClass1, type2)) return false;
119     }
120
121     if (Comparing.equal(TypeConversionUtil.erasure(type1), TypeConversionUtil.erasure(type2))) {
122       final PsiSubstitutor substitutor1 = classResolveResult1.getSubstitutor();
123       final PsiSubstitutor substitutor2 = classResolveResult2.getSubstitutor();
124       for (PsiTypeParameter parameter : substitutor1.getSubstitutionMap().keySet()) {
125         final PsiType substitutedType1 = substitutor1.substitute(parameter);
126         final PsiType substitutedType2 = substitutor2.substitute(parameter);
127         if (substitutedType1 == null && substitutedType2 == null){
128           continue;
129         }
130
131         if (substitutedType1 == null) {
132           if (type2 instanceof PsiClassType && ((PsiClassType)type2).hasParameters()) return true;
133         }
134         else if (substitutedType2 == null) {
135           if (type1 instanceof PsiClassType && ((PsiClassType)type1).hasParameters()) return true;
136         } else {
137           if (provablyDistinct(substitutedType1, substitutedType2, level + 1)) return true;
138         }
139       }
140       if (level < 2) return false;
141     }
142
143     if (boundClass1 == null || boundClass2 == null) {
144       return type1 != null && type2 != null && !type1.equals(type2);
145     }
146
147     return type2 != null && type1 != null && !type1.equals(type2) &&
148            !(boundClass1.isInterface() && boundClass2.isInterface()) &&
149            (!InheritanceUtil.isInheritorOrSelf(boundClass1, boundClass2, true) ||
150             !InheritanceUtil.isInheritorOrSelf(boundClass2, boundClass1, true));
151   }
152
153   private static boolean distinguishFromTypeParam(PsiTypeParameter typeParam, PsiClass boundClass, PsiType type1) {
154     final PsiClassType[] paramBounds = typeParam.getExtendsListTypes();
155     if (paramBounds.length == 0 && type1 instanceof PsiClassType) return false;
156     for (PsiClassType classType : paramBounds) {
157       final PsiClass paramBound = classType.resolve();
158       if (paramBound != null &&
159           (InheritanceUtil.isInheritorOrSelf(paramBound, boundClass, true) ||
160            InheritanceUtil.isInheritorOrSelf(boundClass, paramBound, true))) {
161         return false;
162       }
163     }
164     return true;
165   }
166
167   public static boolean provablyDistinct(PsiWildcardType type1, PsiWildcardType type2, boolean rejectInconsistentRaw, int level) {
168     if (type1.isSuper() && type2.isSuper()) return false;
169     if (type1.isExtends() && type2.isExtends()) {
170       final PsiType extendsBound1 = type1.getExtendsBound();
171       final PsiType extendsBound2 = type2.getExtendsBound();
172       if (extendsBound1 instanceof PsiArrayType && proveArrayTypeDistinct((PsiArrayType)extendsBound1, extendsBound2) ||
173           extendsBound2 instanceof PsiArrayType && proveArrayTypeDistinct((PsiArrayType)extendsBound2, extendsBound1)) return true;
174
175       final PsiClass boundClass1 = PsiUtil.resolveClassInType(extendsBound1);
176       final PsiClass boundClass2 = PsiUtil.resolveClassInType(extendsBound2);
177       if (boundClass1 != null && boundClass2 != null) {
178         if (rejectInconsistentRaw && level > 0 &&
179             extendsBound1 instanceof PsiClassType && extendsBound2 instanceof PsiClassType && 
180             (((PsiClassType)extendsBound1).isRaw() ^ ((PsiClassType)extendsBound2).isRaw())) return true;
181         return proveExtendsBoundsDistinct(type1, type2, boundClass1, boundClass2);
182       }
183       return provablyDistinct(extendsBound1, extendsBound2, 1);
184     }
185     if (type2.isExtends()) return provablyDistinct(type2, type1, rejectInconsistentRaw, level);
186     if (type1.isExtends() && !type2.isBounded() && level > 1) return PsiUtil.resolveClassInType(type1.getExtendsBound()) instanceof PsiTypeParameter;
187     if (type1.isExtends() && type2.isSuper()) {
188       final PsiType extendsBound = type1.getExtendsBound();
189       final PsiType superBound = type2.getSuperBound();
190       if (extendsBound instanceof PsiArrayType && proveArrayTypeDistinct((PsiArrayType)extendsBound, superBound) ||
191           superBound instanceof PsiArrayType && proveArrayTypeDistinct((PsiArrayType)superBound, extendsBound)) return true;
192
193       final PsiClass extendsBoundClass = PsiUtil.resolveClassInType(extendsBound);
194       final PsiClass superBoundClass = PsiUtil.resolveClassInType(superBound);
195       if (extendsBoundClass != null && superBoundClass != null) {
196         if (extendsBoundClass instanceof PsiTypeParameter) {
197           return try2ProveTypeParameterDistinct(type2, extendsBoundClass);
198         }
199         if (superBoundClass instanceof PsiTypeParameter) return false;
200         return !InheritanceUtil.isInheritorOrSelf(superBoundClass, extendsBoundClass, true);
201       }
202       return provablyDistinct(extendsBound, superBound);
203     }
204
205     if (!type1.isBounded() || !type2.isBounded()) {
206       return false;
207     }
208     return !type1.equals(type2);
209   }
210
211   public static boolean proveExtendsBoundsDistinct(PsiType type1,
212                                                     PsiType type2,
213                                                     PsiClass boundClass1,
214                                                     PsiClass boundClass2) {
215     if (boundClass1 == null || boundClass2 == null) {
216       return false;
217     }
218     if (boundClass1.isInterface() && boundClass2.isInterface()) return false;
219     if (boundClass1.isInterface()) {
220       return !(boundClass2.hasModifierProperty(PsiModifier.FINAL) ? InheritanceUtil.isInheritorOrSelf(boundClass2, boundClass1, true) : true);
221     }
222     if (boundClass2.isInterface()) {
223       return !(boundClass1.hasModifierProperty(PsiModifier.FINAL) ? InheritanceUtil.isInheritorOrSelf(boundClass1, boundClass2, true) : true);
224     }
225
226     if (boundClass1 instanceof PsiTypeParameter) {
227       return try2ProveTypeParameterDistinct(type2, boundClass1);
228     }
229
230     if (boundClass2 instanceof PsiTypeParameter) {
231       return try2ProveTypeParameterDistinct(type1, boundClass2);
232     }
233
234     return !InheritanceUtil.isInheritorOrSelf(boundClass1, boundClass2, true) && !InheritanceUtil.isInheritorOrSelf(boundClass2, boundClass1, true);
235   }
236
237   public static boolean try2ProveTypeParameterDistinct(PsiType type, PsiClass typeParameter) {
238     final PsiClassType[] types = typeParameter.getExtendsListTypes();
239     if (types.length == 0) return false;
240     return provablyDistinct(PsiWildcardType.createExtends(typeParameter.getManager(), types[0]), type);
241   }
242
243   public static boolean proveArrayTypeDistinct(PsiArrayType type, PsiType bound) {
244     if (type.getArrayDimensions() == bound.getArrayDimensions()) {
245       final PsiType componentType = type.getComponentType();
246       final PsiType boundComponentType = ((PsiArrayType)bound).getComponentType();
247       if (boundComponentType instanceof PsiClassType && componentType instanceof PsiClassType) {
248         return proveExtendsBoundsDistinct(boundComponentType, componentType, ((PsiClassType)boundComponentType).resolve(), ((PsiClassType)componentType).resolve());
249       }
250       else {
251         return !bound.equals(type);
252       }
253     }
254     else if (bound.getArrayDimensions() + 1 == type.getArrayDimensions() && bound.getDeepComponentType() instanceof PsiClassType) {
255       return !isSuperClassOfArrayType(((PsiClassType)bound.getDeepComponentType()).resolve());
256     }
257     else if (bound.getArrayDimensions() == type.getArrayDimensions() + 1 && type.getDeepComponentType() instanceof PsiClassType) {
258       return !isSuperClassOfArrayType(((PsiClassType)type.getDeepComponentType()).resolve());
259     }
260     else if (bound instanceof PsiClassType) {
261       return !isSuperClassOfArrayType(((PsiClassType)bound).resolve());
262     }
263     else if (bound instanceof PsiWildcardType) {
264       final PsiType boundBound = ((PsiWildcardType)bound).getBound();
265       if (boundBound != null && !boundBound.equals(type)) {
266         if (boundBound instanceof PsiArrayType && !((PsiWildcardType)bound).isSuper()) {
267           return proveArrayTypeDistinct(type, boundBound);
268         }
269         final PsiClass psiClass = PsiUtil.resolveClassInClassTypeOnly(boundBound);
270         if (psiClass == null) {
271           return true;
272         }
273         if (psiClass instanceof PsiTypeParameter) {
274           return try2ProveTypeParameterDistinct(type, psiClass);
275         }
276         return !(((PsiWildcardType)bound).isExtends() && isSuperClassOfArrayType(psiClass));
277       }
278       return false;
279     }
280     else if (bound instanceof PsiIntersectionType) {
281       for (PsiType conjunctBound : ((PsiIntersectionType)bound).getConjuncts()) {
282         if (!proveArrayTypeDistinct(type, conjunctBound)) return false;
283       }
284     }
285     else if (bound instanceof PsiCapturedWildcardType) {
286       return proveArrayTypeDistinct(type, ((PsiCapturedWildcardType)bound).getWildcard());
287     }
288     return true;
289   }
290
291   private static boolean isSuperClassOfArrayType(PsiClass psiClass) {
292     if (psiClass != null) {
293       final String qualifiedName = psiClass.getQualifiedName();
294       return qualifiedName != null && ARRAY_SUPER_CLASSES.contains(qualifiedName);
295     }
296     return false;
297   }
298 }