constructor reference: don't ignore constructor parameters during method reference...
[idea/community.git] / java / java-psi-impl / src / com / intellij / psi / impl / source / resolve / PsiOldInferenceHelper.java
1 // Copyright 2000-2017 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
2 package com.intellij.psi.impl.source.resolve;
3
4 import com.intellij.openapi.diagnostic.Logger;
5 import com.intellij.openapi.projectRoots.JavaSdkVersion;
6 import com.intellij.openapi.projectRoots.JavaVersionService;
7 import com.intellij.openapi.util.Pair;
8 import com.intellij.openapi.util.RecursionGuard;
9 import com.intellij.openapi.util.RecursionManager;
10 import com.intellij.pom.java.LanguageLevel;
11 import com.intellij.psi.*;
12 import com.intellij.psi.infos.MethodCandidateInfo;
13 import com.intellij.psi.search.GlobalSearchScope;
14 import com.intellij.psi.util.PsiTypesUtil;
15 import com.intellij.psi.util.PsiUtil;
16 import com.intellij.psi.util.TypeConversionUtil;
17 import com.intellij.util.ArrayUtil;
18 import org.jetbrains.annotations.NotNull;
19 import org.jetbrains.annotations.Nullable;
20
21 public class PsiOldInferenceHelper implements PsiInferenceHelper {
22   private static final Logger LOG = Logger.getInstance(PsiOldInferenceHelper.class);
23     public static final Pair<PsiType,ConstraintType> RAW_INFERENCE = new Pair<>(null, ConstraintType.EQUALS);
24     private final PsiManager myManager;
25   
26     public PsiOldInferenceHelper(PsiManager manager) {
27       myManager = manager;
28     }
29
30   private Pair<PsiType, ConstraintType> inferTypeForMethodTypeParameterInner(@NotNull PsiTypeParameter typeParameter,
31                                                                                     @NotNull PsiParameter[] parameters,
32                                                                                     @NotNull PsiExpression[] arguments,
33                                                                                     @NotNull PsiSubstitutor partialSubstitutor,
34                                                                                     final PsiElement parent,
35                                                                                     @NotNull ParameterTypeInferencePolicy policy) {
36       PsiType[] paramTypes = PsiType.createArray(arguments.length);
37       PsiType[] argTypes = PsiType.createArray(arguments.length);
38       if (parameters.length > 0) {
39         for (int j = 0; j < argTypes.length; j++) {
40           final PsiExpression argument = arguments[j];
41           if (argument == null) continue;
42           if (argument instanceof PsiMethodCallExpression && PsiResolveHelper.ourGuard.currentStack().contains(argument)) continue;
43
44           RecursionGuard.StackStamp stackStamp = RecursionManager.markStack();
45           argTypes[j] = argument.getType();
46           if (!stackStamp.mayCacheNow()) {
47             argTypes[j] = null;
48             continue;
49           }
50
51           final PsiParameter parameter = parameters[Math.min(j, parameters.length - 1)];
52           if (j >= parameters.length && !parameter.isVarArgs()) break;
53           paramTypes[j] = parameter.getType();
54           if (paramTypes[j] instanceof PsiEllipsisType) {
55             paramTypes[j] = ((PsiEllipsisType)paramTypes[j]).getComponentType();
56             if (arguments.length == parameters.length &&
57                 argTypes[j] instanceof PsiArrayType &&
58                 !(((PsiArrayType)argTypes[j]).getComponentType() instanceof PsiPrimitiveType)) {
59               argTypes[j] = ((PsiArrayType)argTypes[j]).getComponentType();
60             }
61           }
62         }
63       }
64       return inferTypeForMethodTypeParameterInner(typeParameter, paramTypes, argTypes, partialSubstitutor, parent, policy);
65     }
66
67   private Pair<PsiType, ConstraintType> inferTypeForMethodTypeParameterInner(@NotNull PsiTypeParameter typeParameter,
68                                                                                     @NotNull PsiType[] paramTypes,
69                                                                                     @NotNull PsiType[] argTypes,
70                                                                                     @NotNull PsiSubstitutor partialSubstitutor,
71                                                                                     @Nullable PsiElement parent,
72                                                                                     @NotNull ParameterTypeInferencePolicy policy) {
73     PsiWildcardType wildcardToCapture = null;
74     Pair<PsiType, ConstraintType> rawInference = null;
75     PsiType lowerBound = PsiType.NULL;
76     PsiType upperBound = PsiType.NULL;
77     if (paramTypes.length > 0) {
78       for (int j = 0; j < argTypes.length; j++) {
79         PsiType argumentType = argTypes[j];
80         if (argumentType == null) continue;
81         if (j >= paramTypes.length) break;
82
83         PsiType parameterType = paramTypes[j];
84         if (parameterType == null) break;
85
86         if (parameterType instanceof PsiEllipsisType) {
87           parameterType = ((PsiEllipsisType)parameterType).getComponentType();
88           if (argTypes.length == paramTypes.length && argumentType instanceof PsiArrayType && !(((PsiArrayType)argumentType).getComponentType() instanceof PsiPrimitiveType)) {
89             argumentType = ((PsiArrayType)argumentType).getComponentType();
90           }
91         }
92         final Pair<PsiType,ConstraintType> currentSubstitution;
93         currentSubstitution = getSubstitutionForTypeParameterConstraint(typeParameter, parameterType,
94                                                                         argumentType, true, PsiUtil.getLanguageLevel(typeParameter));
95         if (currentSubstitution == null) continue;
96         if (currentSubstitution == FAILED_INFERENCE) {
97           return getFailedInferenceConstraint(typeParameter);
98         }
99
100         final ConstraintType constraintType = currentSubstitution.getSecond();
101         final PsiType type = currentSubstitution.getFirst();
102         if (type == null) {
103           rawInference = RAW_INFERENCE;
104           continue;
105         }
106         switch(constraintType) {
107           case EQUALS:
108             if (!(type instanceof PsiWildcardType)) return currentSubstitution;
109             if (wildcardToCapture != null) return getFailedInferenceConstraint(typeParameter);
110             wildcardToCapture = (PsiWildcardType) type;
111             break;
112           case SUPERTYPE:
113             if (PsiType.NULL.equals(lowerBound)) {
114               lowerBound = type;
115             }
116             else if (!lowerBound.equals(type)) {
117               lowerBound = GenericsUtil.getLeastUpperBound(lowerBound, type, myManager);
118               if (lowerBound == null) return getFailedInferenceConstraint(typeParameter);
119             }
120             break;
121           case SUBTYPE:
122             if (PsiType.NULL.equals(upperBound) || TypeConversionUtil.isAssignable(upperBound, type)) {
123               upperBound = type;
124             }
125         }
126       }
127     }
128
129     if (wildcardToCapture != null) {
130       if (lowerBound != PsiType.NULL) {
131         if (!wildcardToCapture.isAssignableFrom(lowerBound)) return getFailedInferenceConstraint(typeParameter);
132         if (wildcardToCapture.isSuper()) {
133           return new Pair<>(wildcardToCapture, ConstraintType.SUPERTYPE);
134         }
135         lowerBound = GenericsUtil.getLeastUpperBound(lowerBound, wildcardToCapture, myManager);
136       }
137       else {
138         if (upperBound != PsiType.NULL && !upperBound.isAssignableFrom(wildcardToCapture)) return getFailedInferenceConstraint(typeParameter);
139         return new Pair<>(wildcardToCapture, ConstraintType.EQUALS);
140       }
141     }
142
143     if (rawInference != null) return rawInference;
144     if (lowerBound != PsiType.NULL) return Pair.create(lowerBound, ConstraintType.EQUALS);
145
146     if (parent != null) {
147       final Pair<PsiType, ConstraintType> constraint =
148         inferMethodTypeParameterFromParent(typeParameter, partialSubstitutor, parent, policy);
149       if (constraint != null) {
150         if (constraint.getSecond() != ConstraintType.SUBTYPE) {
151           return constraint;
152         }
153
154         if (upperBound != PsiType.NULL) {
155           return Pair.create(upperBound, ConstraintType.SUBTYPE);
156         }
157
158         return constraint;
159       }
160     }
161
162     if (upperBound != PsiType.NULL) return Pair.create(upperBound, ConstraintType.SUBTYPE);
163     return null;
164   }
165
166   private static Pair<PsiType, ConstraintType> getFailedInferenceConstraint(@NotNull PsiTypeParameter typeParameter) {
167     return new Pair<>(JavaPsiFacade.getElementFactory(typeParameter.getProject()).createType(typeParameter),
168                       ConstraintType.EQUALS);
169   }
170
171   @Override
172   public PsiType inferTypeForMethodTypeParameter(@NotNull final PsiTypeParameter typeParameter,
173                                                  @NotNull final PsiParameter[] parameters,
174                                                  @NotNull PsiExpression[] arguments,
175                                                  @NotNull PsiSubstitutor partialSubstitutor,
176                                                  PsiElement parent,
177                                                  @NotNull final ParameterTypeInferencePolicy policy) {
178
179     final Pair<PsiType, ConstraintType> constraint =
180       inferTypeForMethodTypeParameterInner(typeParameter, parameters, arguments, partialSubstitutor, parent, policy);
181     if (constraint == null) return PsiType.NULL;
182     return constraint.getFirst();
183   }
184
185   @NotNull
186   @Override
187   public PsiSubstitutor inferTypeArguments(@NotNull PsiTypeParameter[] typeParameters,
188                                            @NotNull PsiParameter[] parameters,
189                                            @NotNull PsiExpression[] arguments,
190                                            @Nullable MethodCandidateInfo currentMethod, @NotNull PsiSubstitutor partialSubstitutor,
191                                            @NotNull PsiElement parent,
192                                            @NotNull ParameterTypeInferencePolicy policy,
193                                            @NotNull LanguageLevel languageLevel) {
194     PsiType[] substitutions = PsiType.createArray(typeParameters.length);
195     @SuppressWarnings("unchecked")
196     Pair<PsiType, ConstraintType>[] constraints = new Pair[typeParameters.length];
197     for (int i = 0; i < typeParameters.length; i++) {
198       if (substitutions[i] != null) continue;
199       final Pair<PsiType, ConstraintType> constraint =
200         inferTypeForMethodTypeParameterInner(typeParameters[i], parameters, arguments, partialSubstitutor, null, policy);
201       constraints[i] = constraint;
202       if (constraint != null && constraint.getSecond() != ConstraintType.SUBTYPE) {
203         substitutions[i] = constraint.getFirst();
204
205         if (substitutions[i] != null && languageLevel.isAtLeast(LanguageLevel.JDK_1_8)) { //try once more
206           partialSubstitutor = partialSubstitutor.put(typeParameters[i], substitutions[i]);
207           i = -1;
208         }
209       }
210     }
211
212     for (int i = 0; i < typeParameters.length; i++) {
213       PsiTypeParameter typeParameter = typeParameters[i];
214       if (substitutions[i] == null) {
215         PsiType substitutionFromBounds = PsiType.NULL;
216         OtherParameters:
217         for (int j = 0; j < typeParameters.length; j++) {
218           if (i != j) {
219             PsiTypeParameter other = typeParameters[j];
220             final PsiType otherSubstitution = substitutions[j];
221             if (otherSubstitution == null) continue;
222             final PsiClassType[] bounds = other.getExtendsListTypes();
223             for (PsiClassType bound : bounds) {
224               final PsiType substitutedBound = partialSubstitutor.substitute(bound);
225               final Pair<PsiType, ConstraintType> currentConstraint =
226                 getSubstitutionForTypeParameterConstraint(typeParameter, substitutedBound, otherSubstitution, true, languageLevel);
227               if (currentConstraint == null) continue;
228               final PsiType currentSubstitution = currentConstraint.getFirst();
229               final ConstraintType currentConstraintType = currentConstraint.getSecond();
230               if (currentConstraintType == ConstraintType.EQUALS) {
231                 substitutionFromBounds = currentSubstitution;
232                 if (currentSubstitution == null) {
233                   constraints[i] = FAILED_INFERENCE;
234                 }
235                 break OtherParameters;
236               }
237               else if (currentConstraintType == ConstraintType.SUPERTYPE && !JavaVersionService.getInstance().isAtLeast(parent, JavaSdkVersion.JDK_1_7)) {
238                 if (PsiType.NULL.equals(substitutionFromBounds)) {
239                   substitutionFromBounds = currentSubstitution;
240                 }
241                 else {
242                   substitutionFromBounds = GenericsUtil.getLeastUpperBound(substitutionFromBounds, currentSubstitution, myManager);
243                 }
244               }
245             }
246           }
247         }
248
249         if (substitutionFromBounds != PsiType.NULL) substitutions[i] = substitutionFromBounds;
250       }
251     }
252
253     for (int i = 0; i < typeParameters.length; i++) {
254       PsiTypeParameter typeParameter = typeParameters[i];
255       PsiType substitution = substitutions[i];
256       if (substitution != PsiType.NULL) {
257         partialSubstitutor = partialSubstitutor.put(typeParameter, substitution);
258       }
259     }
260
261     for (int i = 0; i < typeParameters.length; i++) {
262       PsiTypeParameter typeParameter = typeParameters[i];
263       PsiType substitution = substitutions[i];
264       if (substitution != null) continue;
265
266       Pair<PsiType, ConstraintType> constraint = constraints[i];
267       if (constraint == null) {
268         constraint = inferMethodTypeParameterFromParent(typeParameter, partialSubstitutor, parent, policy);
269       }
270       else if (constraint.getSecond() == ConstraintType.SUBTYPE) {
271         Pair<PsiType, ConstraintType> otherConstraint =
272           inferMethodTypeParameterFromParent(typeParameter, partialSubstitutor, parent, policy);
273         if (otherConstraint != null) {
274           if (otherConstraint.getSecond() == ConstraintType.EQUALS || otherConstraint.getSecond() == ConstraintType.SUPERTYPE || 
275               compareSubtypes(constraint.getFirst(), otherConstraint.getFirst())) {
276             constraint = otherConstraint;
277           }
278         }
279       }
280
281       if (constraint != null) {
282         substitution = constraint.getFirst();
283       }
284
285       if (substitution == null) {
286         PsiElementFactory factory = JavaPsiFacade.getElementFactory(myManager.getProject());
287         return factory.createRawSubstitutor(partialSubstitutor, typeParameters);
288       }
289       if (substitution != PsiType.NULL) {
290         partialSubstitutor = partialSubstitutor.put(typeParameter, substitution);
291       }
292     }
293     return partialSubstitutor;
294   }
295
296   @NotNull
297   @Override
298   public PsiSubstitutor inferTypeArguments(@NotNull PsiTypeParameter[] typeParameters,
299                                            @NotNull PsiType[] leftTypes,
300                                            @NotNull PsiType[] rightTypes,
301                                            @NotNull LanguageLevel languageLevel) {
302     return inferTypeArguments(typeParameters, leftTypes, rightTypes, PsiSubstitutor.EMPTY, languageLevel);
303   }
304
305   private static boolean compareSubtypes(final PsiType type, final PsiType parentType) {
306     return type != null && parentType != null && TypeConversionUtil.isAssignable(type, parentType);
307   }
308
309   @Override
310   @NotNull
311   public PsiSubstitutor inferTypeArguments(@NotNull PsiTypeParameter[] typeParameters,
312                                            @NotNull PsiType[] leftTypes,
313                                            @NotNull PsiType[] rightTypes,
314                                            @NotNull PsiSubstitutor partialSubstitutor,
315                                            @NotNull LanguageLevel languageLevel) {
316     if (leftTypes.length != rightTypes.length) throw new IllegalArgumentException("Types must be of the same length");
317     PsiSubstitutor substitutor = PsiSubstitutor.EMPTY;
318     for (PsiTypeParameter typeParameter : typeParameters) {
319       PsiType substitution = PsiType.NULL;
320       PsiType lowerBound = PsiType.NULL;
321       for (int i1 = 0; i1 < leftTypes.length; i1++) {
322         PsiType leftType = leftTypes[i1];
323         PsiType rightType = rightTypes[i1];
324         final Pair<PsiType, ConstraintType> constraint =
325             getSubstitutionForTypeParameterConstraint(typeParameter, leftType, rightType, true, languageLevel);
326         if (constraint != null) {
327           final ConstraintType constraintType = constraint.getSecond();
328           final PsiType current = constraint.getFirst();
329           if (constraintType == ConstraintType.EQUALS) {
330             substitution = current;
331             break;
332           }
333           else if (constraintType == ConstraintType.SUBTYPE) {
334             if (PsiType.NULL.equals(substitution)) {
335               substitution = current;
336             }
337             else {
338               substitution = GenericsUtil.getLeastUpperBound(substitution, current, myManager);
339             }
340           }
341           else {
342             if (PsiType.NULL.equals(lowerBound)) {
343               lowerBound = current;
344             }
345             else {
346               lowerBound = GenericsUtil.getLeastUpperBound(lowerBound, current, myManager);
347             }
348           }
349         }
350       }
351
352       if (PsiType.NULL.equals(substitution)) {
353         substitution = lowerBound;
354       }
355
356       if (substitution != PsiType.NULL) {
357         substitutor = substitutor.put(typeParameter, substitution);
358       }
359     }
360     for (int i = 0; i < typeParameters.length; i++) {
361       PsiTypeParameter typeParameter = typeParameters[i];
362       if (!substitutor.getSubstitutionMap().containsKey(typeParameter)) {
363         PsiType substitutionFromBounds = PsiType.NULL;
364         OtherParameters:
365         for (int j = 0; j < typeParameters.length; j++) {
366           if (i != j) {
367             PsiTypeParameter other = typeParameters[j];
368             final PsiType otherSubstitution = substitutor.substitute(other);
369             if (otherSubstitution == null) continue;
370             final PsiClassType[] bounds = other.getExtendsListTypes();
371             for (PsiClassType bound : bounds) {
372               final PsiType substitutedBound = substitutor.substitute(bound);
373               final Pair<PsiType, ConstraintType> currentConstraint =
374                 getSubstitutionForTypeParameterConstraint(typeParameter, substitutedBound, otherSubstitution, true, languageLevel);
375               if (currentConstraint == null) continue;
376               final PsiType currentSubstitution = currentConstraint.getFirst();
377               final ConstraintType currentConstraintType = currentConstraint.getSecond();
378               if (currentConstraintType == ConstraintType.EQUALS) {
379                 substitutionFromBounds = currentSubstitution;
380                 break OtherParameters;
381               }
382               else if (currentConstraintType == ConstraintType.SUPERTYPE) {
383                 if (PsiType.NULL.equals(substitutionFromBounds)) {
384                   substitutionFromBounds = currentSubstitution;
385                 }
386                 else {
387                   substitutionFromBounds = GenericsUtil.getLeastUpperBound(substitutionFromBounds, currentSubstitution, myManager);
388                 }
389               }
390             }
391           }
392         }
393         if (substitutionFromBounds != PsiType.NULL) {
394           substitutor = substitutor.put(typeParameter, substitutionFromBounds);
395         }
396       }
397     }
398     return substitutor;
399   }
400
401   @Nullable
402   private static Pair<PsiType, ConstraintType> processArgType(PsiType arg, final ConstraintType constraintType,
403                                                               final boolean captureWildcard) {
404     if (arg instanceof PsiWildcardType && !captureWildcard) return FAILED_INFERENCE;
405     if (arg != PsiType.NULL) {
406       return Pair.create(arg, constraintType);
407     }
408     return null;
409   }
410
411   private Pair<PsiType, ConstraintType> inferMethodTypeParameterFromParent(@NotNull PsiTypeParameter typeParameter,
412                                                                                   @NotNull PsiSubstitutor substitutor,
413                                                                                   @NotNull PsiElement parent,
414                                                                                   @NotNull ParameterTypeInferencePolicy policy) {
415     PsiTypeParameterListOwner owner = typeParameter.getOwner();
416     Pair<PsiType, ConstraintType> substitution = null;
417     if (owner instanceof PsiMethod && parent instanceof PsiCallExpression) {
418       PsiCallExpression methodCall = (PsiCallExpression)parent;
419       substitution = inferMethodTypeParameterFromParent(PsiUtil.skipParenthesizedExprUp(methodCall.getParent()), methodCall, typeParameter, substitutor, policy);
420     }
421     return substitution;
422   }
423
424   @Override
425   public PsiType getSubstitutionForTypeParameter(PsiTypeParameter typeParam,
426                                                  PsiType param,
427                                                  PsiType arg,
428                                                  boolean isContraVariantPosition,
429                                                  final LanguageLevel languageLevel) {
430     final Pair<PsiType, ConstraintType> constraint = getSubstitutionForTypeParameterConstraint(typeParam, param, arg, isContraVariantPosition,
431                                                                                                languageLevel);
432     return constraint == null ? PsiType.NULL : constraint.getFirst();
433   }
434
435   @Nullable
436   public Pair<PsiType, ConstraintType> getSubstitutionForTypeParameterConstraint(PsiTypeParameter typeParam,
437                                                                                  PsiType param,
438                                                                                  PsiType arg,
439                                                                                  boolean isContraVariantPosition,
440                                                                                  final LanguageLevel languageLevel) {
441     if (param instanceof PsiArrayType && arg instanceof PsiArrayType) {
442       return getSubstitutionForTypeParameterConstraint(typeParam, ((PsiArrayType)param).getComponentType(), ((PsiArrayType)arg).getComponentType(),
443                                              isContraVariantPosition, languageLevel);
444     }
445
446     if (!(param instanceof PsiClassType)) return null;
447     if (arg instanceof PsiPrimitiveType) {
448       if (!JavaVersionService.getInstance().isAtLeast(typeParam, JavaSdkVersion.JDK_1_7) && !isContraVariantPosition) return null;
449       arg = ((PsiPrimitiveType)arg).getBoxedType(typeParam);
450       if (arg == null) return null;
451     }
452
453     if (arg instanceof PsiCapturedWildcardType) {
454       arg = ((PsiCapturedWildcardType)arg).getUpperBound();
455     }
456
457     JavaResolveResult paramResult = ((PsiClassType)param).resolveGenerics();
458     PsiClass paramClass = (PsiClass)paramResult.getElement();
459     if (typeParam == paramClass) {
460       final PsiClass psiClass = PsiUtil.resolveClassInType(arg);
461       if (arg == null ||
462           arg.getDeepComponentType() instanceof PsiPrimitiveType ||
463           arg instanceof PsiIntersectionType ||
464           (psiClass != null && (isContraVariantPosition || !CommonClassNames.JAVA_LANG_OBJECT.equals(psiClass.getQualifiedName()) || (arg instanceof PsiArrayType)))) {
465         PsiType bound = intersectAllExtends(typeParam, arg);
466         return Pair.create(bound, ConstraintType.SUPERTYPE);
467       }
468       if (psiClass == null && arg instanceof PsiClassType) {
469         return Pair.create(arg, ConstraintType.EQUALS);
470       }
471       return null;
472     }
473     if (paramClass == null) return null;
474
475     if (!(arg instanceof PsiClassType)) return null;
476
477     JavaResolveResult argResult = ((PsiClassType)arg).resolveGenerics();
478     PsiClass argClass = (PsiClass)argResult.getElement();
479     if (argClass == null) return null;
480
481     PsiElementFactory factory = JavaPsiFacade.getElementFactory(myManager.getProject());
482     PsiType patternType = factory.createType(typeParam);
483     if (isContraVariantPosition) {
484       PsiSubstitutor substitutor = TypeConversionUtil.getClassSubstitutor(paramClass, argClass, argResult.getSubstitutor());
485       if (substitutor == null) return null;
486       arg = factory.createType(paramClass, substitutor, languageLevel);
487     }
488     else {
489       PsiSubstitutor substitutor = TypeConversionUtil.getClassSubstitutor(argClass, paramClass, paramResult.getSubstitutor());
490       if (substitutor == null) return null;
491       param = factory.createType(argClass, substitutor, languageLevel);
492     }
493
494     return getSubstitutionForTypeParameterInner(param, arg, patternType, ConstraintType.SUPERTYPE, 0);
495   }
496
497   private static PsiType intersectAllExtends(PsiTypeParameter typeParam, PsiType arg) {
498     if (arg == null) return null;
499     PsiClassType[] superTypes = typeParam.getSuperTypes();
500     PsiType[] erasureTypes = PsiType.createArray(superTypes.length);
501     for (int i = 0; i < superTypes.length; i++) {
502       erasureTypes[i] = TypeConversionUtil.erasure(superTypes[i]);
503     }
504     PsiType[] types = ArrayUtil.append(erasureTypes, arg, PsiType.class);
505     assert types.length != 0;
506     return PsiIntersectionType.createIntersection(types);
507   }
508
509   //represents the result of failed type inference: in case we failed inferring from parameters, do not perform inference from context
510   private static final Pair<PsiType, ConstraintType> FAILED_INFERENCE = new Pair<>(PsiType.NULL, ConstraintType.EQUALS);
511
512   @Nullable
513   private Pair<PsiType, ConstraintType> getSubstitutionForTypeParameterInner(PsiType param,
514                                                                                     PsiType arg,
515                                                                                     PsiType patternType,
516                                                                                     final ConstraintType constraintType,
517                                                                                     final int depth) {
518     if (patternType.equals(param)) {
519       return processArgType(arg, constraintType, depth < 2);
520     }
521
522     if (arg instanceof PsiCapturedWildcardType && (depth < 2 || 
523                                                    constraintType != ConstraintType.EQUALS || 
524                                                    param instanceof PsiWildcardType)) {
525       arg = ((PsiCapturedWildcardType)arg).getWildcard(); //reopen
526     }
527
528     if (param instanceof PsiWildcardType) {
529       final PsiWildcardType wildcardParam = (PsiWildcardType)param;
530       final PsiType paramBound = wildcardParam.getBound();
531       if (paramBound == null) return null;
532       ConstraintType constrType = wildcardParam.isExtends() ? ConstraintType.SUPERTYPE : ConstraintType.SUBTYPE;
533       if (arg instanceof PsiWildcardType) {
534         if (((PsiWildcardType)arg).isExtends() == wildcardParam.isExtends() && ((PsiWildcardType)arg).isBounded() == wildcardParam.isBounded()) {
535           Pair<PsiType, ConstraintType> res = getSubstitutionForTypeParameterInner(paramBound, ((PsiWildcardType)arg).getBound(),
536                                                                                    patternType, constrType, depth);
537           if (res != null) return res;
538         }
539       }
540       else if (patternType.equals(paramBound)) {
541         Pair<PsiType, ConstraintType> res = getSubstitutionForTypeParameterInner(paramBound, arg,
542                                                                                    patternType, constrType, depth);
543         if (res != null) return res;
544       }
545       else if (paramBound instanceof PsiArrayType && arg instanceof PsiArrayType) {
546         Pair<PsiType, ConstraintType> res = getSubstitutionForTypeParameterInner(((PsiArrayType) paramBound).getComponentType(),
547                                                                                  ((PsiArrayType) arg).getComponentType(),
548                                                                                  patternType, constrType, depth);
549         if (res != null) return res;
550       }
551       else if (paramBound instanceof PsiClassType && arg instanceof PsiClassType) {
552         final PsiClassType.ClassResolveResult boundResult = ((PsiClassType)paramBound).resolveGenerics();
553         final PsiClass boundClass = boundResult.getElement();
554         if (boundClass != null) {
555           final PsiClassType.ClassResolveResult argResult = ((PsiClassType)arg).resolveGenerics();
556           final PsiClass argClass = argResult.getElement();
557           if (argClass != null) {
558             if (wildcardParam.isExtends()) {
559               PsiSubstitutor superSubstitutor = TypeConversionUtil.getClassSubstitutor(boundClass, argClass, argResult.getSubstitutor());
560               if (superSubstitutor != null) {
561                 for (PsiTypeParameter typeParameter : PsiUtil.typeParametersIterable(boundClass)) {
562                   PsiType substituted = superSubstitutor.substitute(typeParameter);
563                   if (substituted != null) {
564                     Pair<PsiType, ConstraintType> res = getSubstitutionForTypeParameterInner(
565                       boundResult.getSubstitutor().substitute(typeParameter), substituted, patternType, ConstraintType.EQUALS, depth + 1);
566                     if (res != null) return res;
567                   }
568                 }
569               }
570             }
571             else {
572               PsiSubstitutor superSubstitutor = TypeConversionUtil.getClassSubstitutor(argClass, boundClass, boundResult.getSubstitutor());
573               if (superSubstitutor != null) {
574                 for (PsiTypeParameter typeParameter : PsiUtil.typeParametersIterable(argClass)) {
575                   PsiType substituted = argResult.getSubstitutor().substitute(typeParameter);
576                   if (substituted != null) {
577                     Pair<PsiType, ConstraintType> res = getSubstitutionForTypeParameterInner(
578                       superSubstitutor.substitute(typeParameter), substituted, patternType, ConstraintType.EQUALS, depth + 1);
579                     if (res != null) {
580                       if (res == FAILED_INFERENCE) continue;
581                       return res;
582                     }
583                   }
584                 }
585               }
586             }
587           }
588         }
589       }
590     }
591
592     if (param instanceof PsiArrayType && arg instanceof PsiArrayType) {
593       return getSubstitutionForTypeParameterInner(((PsiArrayType)param).getComponentType(), ((PsiArrayType)arg).getComponentType(),
594                                                   patternType, constraintType, depth);
595     }
596
597     if (param instanceof PsiClassType && arg instanceof PsiClassType) {
598       PsiClassType.ClassResolveResult paramResult = ((PsiClassType)param).resolveGenerics();
599       PsiClass paramClass = paramResult.getElement();
600       if (paramClass == null) return null;
601
602       PsiClassType.ClassResolveResult argResult = ((PsiClassType)arg).resolveGenerics();
603       PsiClass argClass = argResult.getElement();
604       if (!paramClass.isEquivalentTo(argClass)) {
605         return null;
606       }
607
608       PsiType lowerBound = PsiType.NULL;
609       PsiType upperBound = PsiType.NULL;
610       Pair<PsiType,ConstraintType> wildcardCaptured = null;
611       for (PsiTypeParameter typeParameter : PsiUtil.typeParametersIterable(paramClass)) {
612         PsiType paramType = paramResult.getSubstitutor().substitute(typeParameter);
613         PsiType argType = argResult.getSubstitutor().substituteWithBoundsPromotion(typeParameter);
614
615         if (wildcardCaptured != null) {
616           boolean alreadyFound = false;
617           for (PsiTypeParameter typeParam : PsiUtil.typeParametersIterable(paramClass)) {
618             if (typeParam != typeParameter &&
619                 paramType != null &&
620                 argResult.getSubstitutor().substituteWithBoundsPromotion(typeParam) == argType &&
621                 paramType.equals(paramResult.getSubstitutor().substitute(typeParam))) {
622               alreadyFound = true;
623             }
624           }
625           if (alreadyFound) continue;
626         }
627
628         Pair<PsiType,ConstraintType> res = getSubstitutionForTypeParameterInner(paramType, argType, patternType, ConstraintType.EQUALS, depth + 1);
629
630         if (res != null) {
631           final PsiType type = res.getFirst();
632           switch (res.getSecond()) {
633             case EQUALS:
634               if (!(type instanceof PsiWildcardType)) return res;
635               if (wildcardCaptured != null) return FAILED_INFERENCE;
636               wildcardCaptured = res;
637               break;
638             case SUPERTYPE:
639               wildcardCaptured = res;
640               if (PsiType.NULL.equals(lowerBound)) {
641                 lowerBound = type;
642               }
643               else if (!lowerBound.equals(type)) {
644                 lowerBound = GenericsUtil.getLeastUpperBound(lowerBound, type, myManager);
645                 if (lowerBound == null) return FAILED_INFERENCE;
646               }
647               break;
648             case SUBTYPE:
649               wildcardCaptured = res;
650               if (PsiType.NULL.equals(upperBound) || TypeConversionUtil.isAssignable(upperBound, type)) {
651                 upperBound = type;
652               }
653           }
654         }
655       }
656
657       if (lowerBound != PsiType.NULL) return Pair.create(lowerBound, ConstraintType.SUPERTYPE);
658       if (upperBound != PsiType.NULL) return Pair.create(upperBound, ConstraintType.SUBTYPE);
659
660       return wildcardCaptured;
661     }
662
663     return null;
664   }
665
666   private Pair<PsiType, ConstraintType> inferMethodTypeParameterFromParent(@NotNull final PsiElement parent,
667                                                                                   @NotNull PsiExpression methodCall,
668                                                                                   @NotNull PsiTypeParameter typeParameter,
669                                                                                   @NotNull PsiSubstitutor substitutor,
670                                                                                   @NotNull ParameterTypeInferencePolicy policy) {
671     Pair<PsiType, ConstraintType> constraint = null;
672     PsiType expectedType = PsiTypesUtil.getExpectedTypeByParent(methodCall);
673
674     if (expectedType == null) {
675       if (parent instanceof PsiExpressionList) {
676         final PsiElement pParent = parent.getParent();
677         if (pParent instanceof PsiCallExpression && parent.equals(((PsiCallExpression)pParent).getArgumentList())) {
678           constraint = policy.inferTypeConstraintFromCallContext(methodCall, (PsiExpressionList)parent, (PsiCallExpression)pParent, typeParameter);
679         }
680       }
681     }
682
683     final GlobalSearchScope scope = parent.getResolveScope();
684     PsiType returnType = null;
685     if (constraint == null) {
686       if (expectedType == null) {
687         expectedType = methodCall instanceof PsiCallExpression ? policy.getDefaultExpectedType((PsiCallExpression)methodCall) : null;
688       }
689
690       if (policy.requestForBoxingExplicitly() && TypeConversionUtil.isPrimitiveAndNotNull(expectedType)) {
691         expectedType = ((PsiPrimitiveType)expectedType).getBoxedType(typeParameter);
692       }
693
694       returnType = ((PsiMethod)typeParameter.getOwner()).getReturnType();
695
696       constraint =
697         getSubstitutionForTypeParameterConstraint(typeParameter, returnType, expectedType, false, PsiUtil.getLanguageLevel(parent));
698
699       if (constraint != null) {
700         PsiType guess = constraint.getFirst();
701         if (guess != null &&
702             !guess.equals(PsiType.NULL) &&
703             constraint.getSecond() == ConstraintType.SUPERTYPE &&
704             guess instanceof PsiIntersectionType &&
705             !JavaVersionService.getInstance().isAtLeast(parent, JavaSdkVersion.JDK_1_7)) {
706           for (PsiType conjuct : ((PsiIntersectionType)guess).getConjuncts()) {
707             if (!conjuct.isAssignableFrom(expectedType)) {
708               return FAILED_INFERENCE;
709             }
710           }
711         }
712       }
713     }
714
715     PsiType[] superTypes = typeParameter.getSuperTypes();
716     final PsiType[] types = PsiType.createArray(superTypes.length);
717     for (int i = 0; i < superTypes.length; i++) {
718       PsiType superType = substitutor.substitute(superTypes[i]);
719       if (superType instanceof PsiClassType && ((PsiClassType)superType).isRaw()) {
720         superType = TypeConversionUtil.erasure(superType);
721       }
722       if (superType == null) superType = PsiType.getJavaLangObject(myManager, scope);
723       types[i] = superType;
724     }
725
726     if (constraint == null) {
727       if (methodCall instanceof PsiCallExpression) {
728         if (types.length == 0) return null;
729         return policy.getInferredTypeWithNoConstraint(myManager, PsiIntersectionType.createIntersection(types));
730       }
731       return null;
732     }
733     PsiType guess = constraint.getFirst();
734     if (guess != null && types.length > 0) {
735       guess = GenericsUtil.getGreatestLowerBound(guess, PsiIntersectionType.createIntersection(types));
736     }
737     guess = policy.adjustInferredType(myManager, guess, constraint.getSecond());
738
739     //The following code is the result of deep thought, do not shit it out before discussing with [ven]
740     if (returnType instanceof PsiClassType && typeParameter.equals(((PsiClassType)returnType).resolve())) {
741       PsiClassType[] extendsTypes = typeParameter.getExtendsListTypes();
742       PsiSubstitutor newSubstitutor = substitutor.put(typeParameter, guess);
743       for (PsiClassType extendsType1 : extendsTypes) {
744         PsiType extendsType = newSubstitutor.substitute(extendsType1);
745         if (guess != null && extendsType != null && !extendsType.isAssignableFrom(guess)) {
746           if (guess.isAssignableFrom(extendsType)) {
747             guess = extendsType;
748             newSubstitutor = substitutor.put(typeParameter, guess);
749           }
750           else {
751             break;
752           }
753         }
754       }
755     }
756
757     return Pair.create(guess, constraint.getSecond());
758   }
759 }