java: prohibit caching when using thread-local types imposed on expressions and decla...
[idea/community.git] / java / java-psi-impl / src / com / intellij / psi / impl / source / resolve / graphInference / InferenceSession.java
1 // Copyright 2000-2018 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.graphInference;
3
4 import com.intellij.openapi.diagnostic.Logger;
5 import com.intellij.openapi.util.Comparing;
6 import com.intellij.openapi.util.Key;
7 import com.intellij.openapi.util.Pair;
8 import com.intellij.openapi.util.Ref;
9 import com.intellij.openapi.util.registry.Registry;
10 import com.intellij.openapi.util.text.StringUtil;
11 import com.intellij.psi.*;
12 import com.intellij.psi.impl.source.resolve.DefaultParameterTypeInferencePolicy;
13 import com.intellij.psi.impl.source.resolve.ParameterTypeInferencePolicy;
14 import com.intellij.psi.impl.source.resolve.graphInference.constraints.*;
15 import com.intellij.psi.infos.MethodCandidateInfo;
16 import com.intellij.psi.search.GlobalSearchScope;
17 import com.intellij.psi.util.*;
18 import com.intellij.util.Function;
19 import com.intellij.util.Processor;
20 import com.intellij.util.containers.ContainerUtil;
21 import com.intellij.util.text.UniqueNameGenerator;
22 import org.jetbrains.annotations.NotNull;
23 import org.jetbrains.annotations.Nullable;
24
25 import java.util.*;
26
27 public class InferenceSession {
28   private static final Logger LOG = Logger.getInstance(InferenceSession.class);
29   private static final Function<Pair<PsiType, PsiType>, PsiType> UPPER_BOUND_FUNCTION = pair -> GenericsUtil.getGreatestLowerBound(pair.first, pair.second);
30
31   private static final String EQUALITY_CONSTRAINTS_PRESENTATION = "equality constraints";
32   private static final String UPPER_BOUNDS_PRESENTATION = "upper bounds";
33   private static final String LOWER_BOUNDS_PRESENTATION = "lower bounds";
34   static final Key<PsiCapturedWildcardType> ORIGINAL_CAPTURE = Key.create("ORIGINAL_CAPTURE");
35
36   protected final Set<InferenceVariable> myInferenceVariables = new LinkedHashSet<>();
37   private final List<ConstraintFormula> myConstraints = new ArrayList<>();
38   private final Set<ConstraintFormula> myConstraintsCopy = new HashSet<>();
39   private final InferenceSessionContainer myInferenceSessionContainer;
40
41   private PsiSubstitutor mySiteSubstitutor;
42   private final PsiManager myManager;
43   private int myConstraintIdx;
44   
45   private List<String> myErrorMessages;
46   
47   private boolean myErased;
48
49   public final InferenceIncorporationPhase myIncorporationPhase = new InferenceIncorporationPhase(this);
50
51   private final PsiElement myContext;
52   private final ParameterTypeInferencePolicy myPolicy;
53
54   private PsiSubstitutor myInferenceSubstitution = PsiSubstitutor.EMPTY;
55   private PsiSubstitutor myRestoreNameSubstitution = PsiSubstitutor.EMPTY;
56   private MethodCandidateInfo myCurrentMethod;
57   private ThreadLocalTypes myTempTypes;
58
59   public InferenceSession(InitialInferenceState initialState, ParameterTypeInferencePolicy policy) {
60     myContext = initialState.getContext();
61     myManager = myContext.getManager();
62
63     myInferenceSubstitution = initialState.getInferenceSubstitutor();
64     myInferenceVariables.addAll(initialState.getInferenceVariables());
65     mySiteSubstitutor = initialState.getSiteSubstitutor();
66
67     for (Pair<InferenceVariable[], PsiClassType> capture : initialState.getCaptures()) {
68       myIncorporationPhase.addCapture(capture.first, capture.second);
69     }
70     myInferenceSessionContainer = initialState.getInferenceSessionContainer();
71     myErased = initialState.isErased();
72     myPolicy = policy;
73   }
74
75   public InferenceSession(PsiTypeParameter[] typeParams,
76                           PsiType[] leftTypes,
77                           PsiType[] rightTypes,
78                           PsiSubstitutor siteSubstitutor,
79                           PsiManager manager,
80                           PsiElement context) {
81     myManager = manager;
82     mySiteSubstitutor = siteSubstitutor;
83     myContext = context;
84
85     initBounds(typeParams);
86
87     LOG.assertTrue(leftTypes.length == rightTypes.length);
88     for (int i = 0; i < leftTypes.length; i++) {
89       final PsiType rightType = mySiteSubstitutor.substitute(rightTypes[i]);
90       PsiType t = substituteWithInferenceVariables(leftTypes[i]);
91       PsiType s = substituteWithInferenceVariables(rightType);
92       if (t != null && s != null) {
93         addConstraint(new TypeCompatibilityConstraint(t, s));
94       }
95     }
96     myPolicy = DefaultParameterTypeInferencePolicy.INSTANCE;
97     myInferenceSessionContainer = new InferenceSessionContainer();
98   }
99
100   public InferenceSession(PsiTypeParameter[] typeParams,
101                           PsiSubstitutor siteSubstitutor,
102                           PsiManager manager,
103                           PsiElement context) {
104     this(typeParams, siteSubstitutor, manager, context, DefaultParameterTypeInferencePolicy.INSTANCE);
105   }
106
107   public InferenceSession(PsiTypeParameter[] typeParams,
108                           PsiSubstitutor siteSubstitutor,
109                           PsiManager manager,
110                           PsiElement context,
111                           ParameterTypeInferencePolicy policy) {
112     myManager = manager;
113     mySiteSubstitutor = siteSubstitutor;
114     myContext = context;
115     myPolicy = policy;
116
117     initBounds(typeParams);
118     myInferenceSessionContainer = new InferenceSessionContainer();
119   }
120
121   public MethodCandidateInfo getCurrentMethod(PsiExpressionList argumentList) {
122     return myCurrentMethod != null && myCurrentMethod.isOnArgumentList(argumentList) ? myCurrentMethod : null;
123   }
124
125   public void setCurrentMethod(MethodCandidateInfo currentMethod) {
126     myCurrentMethod = currentMethod;
127   }
128
129   @NotNull
130   public ParameterTypeInferencePolicy getInferencePolicy() {
131     return myPolicy;
132   }
133
134   public static PsiType createTypeParameterTypeWithUpperBound(@NotNull PsiType upperBound, @NotNull PsiElement place) {
135     final PsiElementFactory elementFactory = JavaPsiFacade.getElementFactory(place.getProject());
136
137     final PsiTypeParameter parameter = elementFactory.createTypeParameterFromText("T", place);
138     TypeConversionUtil.setInferredBoundsForSynthetic(parameter, null, upperBound);
139
140     return elementFactory.createType(parameter);
141   }
142
143   public void initExpressionConstraints(PsiParameter[] parameters,
144                                         PsiExpression[] args,
145                                         PsiMethod method,
146                                         boolean varargs) {
147     if (method != null) {
148       initThrowsConstraints(method);
149     }
150     if (parameters.length > 0) {
151       for (int i = 0; i < args.length; i++) {
152         //don't infer anything if number of parameters differ and method is not vararg
153         if (!varargs && i >= parameters.length) {
154           continue;
155         }
156
157         if (args[i] != null && isPertinentToApplicability(args[i], method)) {
158           PsiType parameterType = getParameterType(parameters, i, mySiteSubstitutor, varargs);
159           addConstraint(new ExpressionCompatibilityConstraint(args[i], substituteWithInferenceVariables(parameterType)));
160         }
161       }
162     }
163   }
164
165   public void initThrowsConstraints(PsiMethod method) {
166     for (PsiClassType thrownType : method.getThrowsList().getReferencedTypes()) {
167       final InferenceVariable variable = getInferenceVariable(substituteWithInferenceVariables(thrownType));
168       if (variable != null) {
169         variable.setThrownBound();
170       }
171     }
172   }
173   
174   static PsiExpressionList getArgumentList(PsiElement parent) {
175     if (parent instanceof PsiCall) {
176       return ((PsiCall)parent).getArgumentList();
177     }
178     if (parent instanceof PsiAnonymousClass) {
179       return getArgumentList(parent.getParent());
180     }
181     return null;
182   }
183
184   /**
185    * Definition from 15.12.2.2 Phase 1: Identify Matching Arity Methods Applicable by Subtyping Strict Invocation
186    * An argument expression is considered pertinent to applicability for a potentially-applicable method m unless it has one of the following forms:
187
188    1)  An implicitly-typed lambda expression (15.27.1).
189    2) An inexact method reference (15.13.1).
190    3) If m is a generic method and the method invocation does not provide explicit type arguments, an explicitly-typed lambda expression or 
191       an exact method reference for which the corresponding target type (as derived from the signature of m) is a type parameter of m.
192    4) An explicitly-typed lambda expression whose body is an expression that is not pertinent to applicability.
193    5) An explicitly-typed lambda expression whose body is a block, where at least one result expression is not pertinent to applicability.
194    6) A parenthesized expression (15.8.5) whose contained expression is not pertinent to applicability.
195    7) A conditional expression (15.25) whose second or third operand is not pertinent to applicability. 
196   */
197   public static boolean isPertinentToApplicability(PsiExpression expr, PsiMethod method) {
198     return isPertinentToApplicability(expr, method, null);
199   }
200
201   private static boolean isPertinentToApplicability(PsiExpression expr, PsiMethod method, PsiType expectedReturnType) {
202     if (expr instanceof PsiLambdaExpression && ((PsiLambdaExpression)expr).hasFormalParameterTypes() ||
203         expr instanceof PsiMethodReferenceExpression && ((PsiMethodReferenceExpression)expr).isExact()) {
204       if (method != null) {
205         final PsiElement parent = PsiUtil.skipParenthesizedExprUp(expr.getParent());
206         PsiType paramType = null;
207         if (parent instanceof PsiExpressionList) {
208           final PsiElement gParent = parent.getParent();
209           PsiTypeParameterListOwner owner = getTypeParameterOwner(method, gParent);
210           if (owner != null) {
211             final int idx = LambdaUtil.getLambdaIdx((PsiExpressionList)parent, expr);
212             final PsiParameter[] parameters = method.getParameterList().getParameters();
213             if (idx > parameters.length - 1) {
214               final PsiType lastParamType = parameters[parameters.length - 1].getType();
215               paramType = parameters[parameters.length - 1].isVarArgs() ? ((PsiEllipsisType)lastParamType).getComponentType() : lastParamType;
216             }
217             else {
218               paramType = parameters[idx].getType();
219             }
220             if (isTypeParameterType(owner, paramType)) return false;
221           }
222         }
223         else if (expectedReturnType != null && (parent instanceof PsiLambdaExpression ||
224                                                 parent instanceof PsiReturnStatement && PsiTreeUtil.getParentOfType(parent, PsiLambdaExpression.class, true, PsiMethod.class) != null)) {
225           if (isTypeParameterType(method, expectedReturnType)) return false;
226           paramType = expectedReturnType;
227         }
228
229         if (expr instanceof PsiLambdaExpression) {
230           for (PsiExpression expression : LambdaUtil.getReturnExpressions((PsiLambdaExpression)expr)) {
231             if (!isPertinentToApplicability(expression, method, LambdaUtil.getFunctionalInterfaceReturnType(paramType))) return false;
232           }
233           return true;
234         }
235       }
236     }
237     if (expr instanceof PsiLambdaExpression) {
238       return ((PsiLambdaExpression)expr).hasFormalParameterTypes();
239     }
240     if (expr instanceof PsiMethodReferenceExpression) {
241       return ((PsiMethodReferenceExpression)expr).isExact();
242     }
243     if (expr instanceof PsiParenthesizedExpression) {
244       return isPertinentToApplicability(((PsiParenthesizedExpression)expr).getExpression(), method);
245     }
246     if (expr instanceof PsiConditionalExpression) {
247       final PsiExpression thenExpression = ((PsiConditionalExpression)expr).getThenExpression();
248       if (!isPertinentToApplicability(thenExpression, method)) return false;
249       final PsiExpression elseExpression = ((PsiConditionalExpression)expr).getElseExpression();
250       if (!isPertinentToApplicability(elseExpression, method)) return false;
251     }
252     return true;
253   }
254
255   private static PsiTypeParameterListOwner getTypeParameterOwner(@NotNull PsiMethod method, PsiElement gParent) {
256     PsiTypeParameterListOwner owner = null;
257     if (method.getTypeParameters().length > 0 && gParent instanceof PsiCallExpression && ((PsiCallExpression)gParent).getTypeArgumentList().getTypeParameterElements().length == 0) {
258       owner = method;
259     }
260     else if (method.isConstructor() && gParent instanceof PsiNewExpression) {
261       final PsiClass containingClass = method.getContainingClass();
262       if (containingClass != null && containingClass.hasTypeParameters() && PsiDiamondType.hasDiamond((PsiNewExpression)gParent)) {
263         owner = containingClass;
264       }
265     }
266     return owner;
267   }
268
269   private static boolean isTypeParameterType(PsiTypeParameterListOwner method, PsiType paramType) {
270     final PsiClass psiClass = PsiUtil.resolveClassInType(paramType); //accept ellipsis here
271     if (psiClass instanceof PsiTypeParameter && ((PsiTypeParameter)psiClass).getOwner() == method) return true;
272     return false;
273   }
274
275   private static PsiType getParameterType(PsiParameter[] parameters, int i, @Nullable PsiSubstitutor substitutor, boolean varargs) {
276     if (substitutor == null) return null;
277     return substitutor.substitute(PsiTypesUtil.getParameterType(parameters, i, varargs));
278   }
279
280   @NotNull
281   public PsiSubstitutor infer() {
282     return infer(null, null, null, null);
283   }
284
285
286   PsiSubstitutor collectAdditionalAndInfer(@NotNull PsiParameter[] parameters,
287                                            @NotNull PsiExpression[] args,
288                                            @NotNull MethodCandidateInfo properties,
289                                            @NotNull PsiSubstitutor psiSubstitutor) {
290     return performGuardedInference(parameters, args, myContext, properties, psiSubstitutor);
291   }
292
293   @NotNull
294   public PsiSubstitutor infer(@Nullable PsiParameter[] parameters,
295                               @Nullable PsiExpression[] args,
296                               @Nullable PsiElement parent,
297                               @Nullable MethodCandidateInfo currentMethod) {
298     return performGuardedInference(parameters, args, parent, currentMethod, PsiSubstitutor.EMPTY);
299   }
300
301   @NotNull
302   private PsiSubstitutor performGuardedInference(@Nullable PsiParameter[] parameters,
303                                                  @Nullable PsiExpression[] args,
304                                                  @Nullable PsiElement parent,
305                                                  @Nullable MethodCandidateInfo currentMethod,
306                                                  @NotNull PsiSubstitutor initialSubstitutor) {
307     return ThreadLocalTypes.performWithTypes(types -> {
308       myTempTypes = types;
309       try {
310         doInfer(parameters, args, parent, currentMethod, initialSubstitutor);
311         return prepareSubstitution();
312       }
313       finally {
314         if (currentMethod != null) {
315           if (myErrorMessages != null) {
316             currentMethod.setApplicabilityError(StringUtil.join(myErrorMessages, "\n"));
317           }
318           currentMethod.setErased(myErased);
319         }
320         myTempTypes = null;
321       }
322     });
323   }
324
325   private void doInfer(@Nullable PsiParameter[] parameters,
326                        @Nullable PsiExpression[] args,
327                        @Nullable PsiElement parent,
328                        @Nullable MethodCandidateInfo properties,
329                        @NotNull PsiSubstitutor initialSubstitutor) {
330     if (!repeatInferencePhases()) {
331       return;
332     }
333
334     PsiExpressionList argumentList = getArgumentList(parent);
335     if (properties != null && argumentList != null && !MethodCandidateInfo.isOverloadCheck(argumentList)) {
336       String expectedActualErrorMessage = null;
337       final PsiMethod method = properties.getElement();
338       if (parent instanceof PsiCallExpression && PsiPolyExpressionUtil.isMethodCallPolyExpression((PsiExpression)parent, method)) {
339         final PsiType returnType = method.getReturnType();
340         if (!PsiType.VOID.equals(returnType) && returnType != null) {
341           final Ref<String> errorMessage = new Ref<>();
342           final PsiType targetType = getTargetTypeFromParent(parent, errorMessage, false);
343           if (targetType == null && errorMessage.get() != null) {
344             return;
345           }
346
347           if (targetType != null && !PsiType.VOID.equals(targetType)) {
348             PsiType actualType = PsiUtil.isRawSubstitutor(method, mySiteSubstitutor) ? returnType : mySiteSubstitutor.substitute(returnType);
349             registerReturnTypeConstraints(actualType, targetType, myContext);
350             expectedActualErrorMessage = "Incompatible types. Required " + targetType.getPresentableText() + " but '" + method.getName() + "' was inferred to " + actualType.getPresentableText() + ":";
351           }
352         }
353       }
354
355       if (!repeatInferencePhases()) {
356         if (expectedActualErrorMessage != null && myErrorMessages != null) {
357           myErrorMessages.add(0, expectedActualErrorMessage);
358         }
359         if (isPertinentToApplicabilityCheckOnContainingCall(parent)) {
360           return;
361         }
362       }
363       //proceed to B3 constraints
364       else if (parameters != null && parameters.length > 0 && args != null && !isPertinentToApplicabilityCheckOnContainingCall(parent)) {
365         final Set<ConstraintFormula> additionalConstraints = new LinkedHashSet<>();
366         final HashSet<ConstraintFormula> ignoredConstraints = new HashSet<>();
367         collectAdditionalConstraints(parameters, args, method, mySiteSubstitutor, additionalConstraints,
368                                      ignoredConstraints, properties.isVarargs(), initialSubstitutor);
369
370         proceedWithAdditionalConstraints(additionalConstraints, ignoredConstraints);
371       }
372     }
373
374     resolveBounds(myInferenceVariables, initialSubstitutor);
375   }
376
377   private static boolean isPertinentToApplicabilityCheckOnContainingCall(@NotNull PsiElement parent) {
378     return ThreadLocalTypes.hasBindingFor(parent);
379   }
380
381   private void collectAdditionalConstraints(PsiParameter[] parameters,
382                                             PsiExpression[] args,
383                                             PsiMethod parentMethod,
384                                             PsiSubstitutor siteSubstitutor,
385                                             Set<ConstraintFormula> additionalConstraints,
386                                             Set<ConstraintFormula> ignoredConstraints,
387                                             boolean varargs,
388                                             PsiSubstitutor initialSubstitutor) {
389     for (int i = 0; i < args.length; i++) {
390       final PsiExpression arg = PsiUtil.skipParenthesizedExprDown(args[i]);
391       if (arg != null) {
392         final PsiSubstitutor nestedSubstitutor = myInferenceSessionContainer.findNestedSubstitutor(arg, myInferenceSubstitution);
393         final PsiType parameterType = nestedSubstitutor.substitute(getParameterType(parameters, i, siteSubstitutor, varargs));
394         if (!isPertinentToApplicability(arg, parentMethod)) {
395           ExpressionCompatibilityConstraint compatibilityConstraint = new ExpressionCompatibilityConstraint(arg, parameterType);
396           if (arg instanceof PsiLambdaExpression && ignoreLambdaConstraintTree(arg) || dependsOnIgnoredConstraint(ignoredConstraints, compatibilityConstraint)) {
397             ignoredConstraints.add(compatibilityConstraint);
398             continue;
399           }
400
401           additionalConstraints.add(compatibilityConstraint);
402         }
403         additionalConstraints.add(new CheckedExceptionCompatibilityConstraint(arg, parameterType));
404         if (arg instanceof PsiCall) {
405           //If the expression is a poly class instance creation expression (15.9) or a poly method invocation expression (15.12), 
406           //the set contains all constraint formulas that would appear in the set C when determining the poly expression's invocation type.
407           final JavaResolveResult resolveResult = PsiDiamondType.getDiamondsAwareResolveResult((PsiCall)arg);
408           final PsiMethod calledMethod = resolveResult instanceof MethodCandidateInfo ? (PsiMethod)resolveResult.getElement() : null;
409           if (calledMethod != null && PsiPolyExpressionUtil.isMethodCallPolyExpression(arg, calledMethod)) {
410             collectAdditionalConstraints(additionalConstraints, ignoredConstraints, (PsiCall)arg, initialSubstitutor);
411           }
412         }
413         else if (arg instanceof PsiLambdaExpression &&
414                  isPertinentToApplicability(arg, parentMethod)) {
415           collectLambdaReturnExpression(additionalConstraints, ignoredConstraints, (PsiLambdaExpression)arg,
416                                         ((PsiLambdaExpression)arg).getGroundTargetType(parameterType),
417                                         !isProperType(initialSubstitutor.substitute(parameterType)),
418                                         initialSubstitutor);
419         }
420       }
421     }
422   }
423
424   private boolean dependsOnIgnoredConstraint(Set<ConstraintFormula> ignoredConstraints, ExpressionCompatibilityConstraint compatibilityConstraint) {
425     if (!ignoredConstraints.isEmpty()) {
426       Set<InferenceVariable> inputVariables = compatibilityConstraint.getInputVariables(this);
427
428       if (inputVariables != null) {
429         for (ConstraintFormula ignoredConstraint : ignoredConstraints) {
430           if (ignoredConstraint instanceof InputOutputConstraintFormula) {
431             Set<InferenceVariable> inputsOfIgnored = ((InputOutputConstraintFormula)ignoredConstraint).getInputVariables(this);
432             Set<InferenceVariable> outputVariables = ((InputOutputConstraintFormula)ignoredConstraint).getOutputVariables(inputsOfIgnored, this);
433             if (outputVariables != null && ContainerUtil.intersects(outputVariables, inputVariables)) return true;
434           }
435         }
436       }
437     }
438     return false;
439   }
440   
441   public static boolean ignoreLambdaConstraintTree(PsiExpression arg) {
442     for (PsiElement expr : MethodCandidateInfo.ourOverloadGuard.currentStack()) {
443       if (PsiTreeUtil.getParentOfType(expr, PsiLambdaExpression.class) == arg) {
444         return true;
445       }
446     }
447     return false;
448   }
449
450   private void collectLambdaReturnExpression(Set<ConstraintFormula> additionalConstraints,
451                                              Set<ConstraintFormula> ignoredConstraints, 
452                                              PsiLambdaExpression lambdaExpression,
453                                              PsiType parameterType,
454                                              boolean addConstraint,
455                                              PsiSubstitutor initialSubstitutor) {
456     final PsiType interfaceReturnType = LambdaUtil.getFunctionalInterfaceReturnType(parameterType);
457     if (interfaceReturnType != null && !PsiType.VOID.equals(interfaceReturnType)) {
458       final List<PsiExpression> returnExpressions = LambdaUtil.getReturnExpressions(lambdaExpression);
459       for (PsiExpression returnExpression : returnExpressions) {
460         processReturnExpression(additionalConstraints, ignoredConstraints, returnExpression, interfaceReturnType, addConstraint, initialSubstitutor);
461       }
462     }
463   }
464
465   private void processReturnExpression(Set<ConstraintFormula> additionalConstraints,
466                                        Set<ConstraintFormula> ignoredConstraints,
467                                        PsiExpression returnExpression,
468                                        PsiType functionalType,
469                                        boolean addConstraint,
470                                        PsiSubstitutor initialSubstitutor) {
471     if (returnExpression instanceof PsiCallExpression) {
472       if (addConstraint) {
473         final JavaResolveResult resolveResult = PsiDiamondType.getDiamondsAwareResolveResult((PsiCallExpression)returnExpression);
474         if (resolveResult instanceof MethodCandidateInfo && 
475             PsiPolyExpressionUtil.isMethodCallPolyExpression(returnExpression, ((MethodCandidateInfo)resolveResult).getElement())) {
476           collectAdditionalConstraints(additionalConstraints, ignoredConstraints, (PsiCallExpression)returnExpression, initialSubstitutor);
477         }
478       }
479       else {
480         getInferenceSessionContainer().registerNestedSession(this, functionalType, returnExpression);
481       }
482     }
483     else if (returnExpression instanceof PsiParenthesizedExpression) {
484       processReturnExpression(additionalConstraints, ignoredConstraints, ((PsiParenthesizedExpression)returnExpression).getExpression(), functionalType, addConstraint, initialSubstitutor);
485     }
486     else if (returnExpression instanceof PsiConditionalExpression) {
487       processReturnExpression(additionalConstraints, ignoredConstraints, ((PsiConditionalExpression)returnExpression).getThenExpression(), functionalType, addConstraint, initialSubstitutor);
488       processReturnExpression(additionalConstraints, ignoredConstraints, ((PsiConditionalExpression)returnExpression).getElseExpression(), functionalType, addConstraint, initialSubstitutor);
489     }
490     else if (returnExpression instanceof PsiSwitchExpression) {
491       for (PsiExpression resultExpression : PsiUtil.getSwitchResultExpressions((PsiSwitchExpression)returnExpression)) {
492         processReturnExpression(additionalConstraints, ignoredConstraints, resultExpression, functionalType, addConstraint, initialSubstitutor);
493       }
494     }
495     else if (returnExpression instanceof PsiLambdaExpression) {
496       collectLambdaReturnExpression(additionalConstraints, ignoredConstraints, (PsiLambdaExpression)returnExpression, functionalType, myErased, initialSubstitutor);
497     }
498   }
499
500   private void collectAdditionalConstraints(final Set<ConstraintFormula> additionalConstraints,
501                                             final Set<ConstraintFormula> ignoredConstraints, 
502                                             final PsiCall callExpression,
503                                             PsiSubstitutor initialSubstitutor) {
504     PsiExpressionList argumentList = callExpression.getArgumentList();
505     if (argumentList != null) {
506       final JavaResolveResult result = PsiDiamondType.getDiamondsAwareResolveResult(callExpression);
507       final PsiMethod method = result instanceof MethodCandidateInfo ? ((MethodCandidateInfo)result).getElement() :  null;
508       if (method != null) {
509         final PsiExpression[] newArgs = argumentList.getExpressions();
510         final PsiParameter[] newParams = method.getParameterList().getParameters();
511         if (newParams.length > 0) {
512           collectAdditionalConstraints(newParams, newArgs, method, chooseSiteSubstitutor(null, result, method), additionalConstraints,
513                                        ignoredConstraints, chooseVarargsMode(null, result), initialSubstitutor);
514         }
515       }
516     }
517   }
518
519   public static PsiSubstitutor chooseSiteSubstitutor(MethodCandidateInfo currentMethod,
520                                                      JavaResolveResult resolveResult, PsiMethod method) {
521     return resolveResult instanceof MethodCandidateInfo && method != null && !method.isConstructor() //constructor reference was erased 
522            ? ((MethodCandidateInfo)resolveResult).getSiteSubstitutor() 
523            : currentMethod != null ? currentMethod.getSiteSubstitutor() : PsiSubstitutor.EMPTY;
524   }
525
526
527   public static boolean chooseVarargsMode(MethodCandidateInfo currentMethod,
528                                           JavaResolveResult resolveResult) {
529     return resolveResult instanceof MethodCandidateInfo && ((MethodCandidateInfo)resolveResult).isVarargs() ||
530            currentMethod != null && currentMethod.isVarargs();
531   }
532
533   PsiSubstitutor getInstantiations(Collection<InferenceVariable> variables) {
534     PsiSubstitutor substitutor = PsiSubstitutor.EMPTY;
535     for (InferenceVariable variable : variables) {
536       final PsiType equalsBound = getEqualsBound(variable, substitutor);
537       if (equalsBound != null && !PsiType.NULL.equals(equalsBound)) {
538         substitutor = substitutor.put(variable.getParameter(), equalsBound);
539       }
540     }
541     return substitutor;
542   }
543   
544   protected PsiSubstitutor prepareSubstitution() {
545     boolean foundErrorMessage = false;
546     Iterator<List<InferenceVariable>> iterator = InferenceVariablesOrder.resolveOrderIterator(myInferenceVariables, this);
547     while (iterator.hasNext()) {
548       final List<InferenceVariable> variables = iterator.next();
549       for (InferenceVariable inferenceVariable : variables) {
550         final PsiTypeParameter typeParameter = inferenceVariable.getParameter();
551         PsiType instantiation = inferenceVariable.getInstantiation();
552         //failed inference
553         if (instantiation == PsiType.NULL) {
554           if (!foundErrorMessage) {
555             foundErrorMessage = checkBoundsConsistency(mySiteSubstitutor, inferenceVariable) == PsiType.NULL;
556           }
557           mySiteSubstitutor = mySiteSubstitutor
558             .put(typeParameter, JavaPsiFacade.getElementFactory(myManager.getProject()).createType(typeParameter));
559         }
560       }
561     }
562     return mySiteSubstitutor;
563   }
564
565   InitialInferenceState createInitialState(InferenceSessionContainer container,
566                                            Collection<InferenceVariable> variables,
567                                            PsiSubstitutor topInferenceSubstitutor) {
568     return new InitialInferenceState(variables,
569                                      topInferenceSubstitutor,
570                                      myContext, 
571                                      myInferenceSubstitution, 
572                                      mySiteSubstitutor, 
573                                      myIncorporationPhase.getCaptures(),
574                                      myErased,
575                                      container);
576   }
577
578   private void initBounds(PsiTypeParameter... typeParameters) {
579     initBounds(myContext, typeParameters);
580   }
581
582   public InferenceVariable[] initBounds(PsiElement context, PsiTypeParameter... typeParameters) {
583     return initBounds(context, mySiteSubstitutor, typeParameters);
584   }
585
586   public InferenceVariable[] initBounds(PsiElement context,
587                                         final PsiSubstitutor siteSubstitutor,
588                                         PsiTypeParameter... typeParameters) {
589     List<InferenceVariable> result = new ArrayList<>(typeParameters.length);
590     for (PsiTypeParameter parameter : typeParameters) {
591       String name = parameter.getName();
592       if (myContext != null) {
593         name += Math.abs(myContext.hashCode());
594       }
595       InferenceVariable variable = new InferenceVariable(context, parameter, name);
596       result.add(variable);
597       final PsiElementFactory elementFactory = JavaPsiFacade.getElementFactory(myManager.getProject());
598       myInferenceSubstitution = myInferenceSubstitution.put(parameter, elementFactory.createType(variable));
599       myRestoreNameSubstitution = myRestoreNameSubstitution.put(variable, elementFactory.createType(parameter));
600       myInferenceVariables.add(variable);
601     }
602     for (InferenceVariable variable : result) {
603       PsiTypeParameter parameter = variable.getParameter();
604       boolean added = false;
605       final PsiClassType[] extendsListTypes = parameter.getExtendsListTypes();
606       for (PsiType classType : extendsListTypes) {
607         classType = substituteWithInferenceVariables(siteSubstitutor.substitute(classType));
608         if (isProperType(classType)) {
609           added = true;
610         }
611         variable.addBound(classType, InferenceBound.UPPER, null);
612       }
613       if (!added) {
614         variable.addBound(PsiType.getJavaLangObject(parameter.getManager(), parameter.getResolveScope()),
615                           InferenceBound.UPPER, null);
616       }
617     }
618     return result.toArray(new InferenceVariable[0]);
619   }
620
621   public void registerReturnTypeConstraints(PsiType returnType, PsiType targetType, PsiElement context) {
622     returnType = substituteWithInferenceVariables(returnType);
623     if (myErased) {
624       PsiSubstitutor currentSubstitutor = resolveSubset(myInferenceVariables, mySiteSubstitutor);
625       addConstraint(new TypeCompatibilityConstraint(targetType,
626                                                     TypeConversionUtil.erasure(currentSubstitutor.substitute(returnType))));
627     }
628     else if (FunctionalInterfaceParameterizationUtil.isWildcardParameterized(returnType)) {
629       final PsiClassType.ClassResolveResult resolveResult = PsiUtil.resolveGenericsClassInType(returnType);
630       final PsiClass psiClass = resolveResult.getElement();
631       if (psiClass != null) {
632         LOG.assertTrue(returnType instanceof PsiClassType);
633         PsiClassType substitutedCapture = (PsiClassType)PsiUtil.captureToplevelWildcards(returnType, context);
634         final PsiTypeParameter[] typeParameters = psiClass.getTypeParameters();
635         final PsiType[] parameters = substitutedCapture.getParameters();
636         final InferenceVariable[] copy = initFreshVariablesForCapturedBounds(typeParameters, parameters);
637         final PsiType[] newParameters = new PsiType[parameters.length];
638         final PsiElementFactory elementFactory = JavaPsiFacade.getElementFactory(myManager.getProject());
639         int idx = 0;
640         for (int i = 0; i < parameters.length; i++) {
641           newParameters[i] = parameters[i];
642           if (parameters[i] instanceof PsiCapturedWildcardType) {
643             newParameters[i] = elementFactory.createType(copy[idx++]);
644           }
645         }
646         substitutedCapture = elementFactory.createType(psiClass, newParameters);
647
648         myIncorporationPhase.addCapture(copy, (PsiClassType)returnType);
649         addConstraint(new TypeCompatibilityConstraint(targetType, substitutedCapture));
650       }
651     } else {
652       final InferenceVariable inferenceVariable = shouldResolveAndInstantiate(returnType, targetType);
653       if (inferenceVariable != null) {
654         final PsiSubstitutor substitutor = resolveSubset(Collections.singletonList(inferenceVariable), mySiteSubstitutor);
655         final PsiType substitutedReturnType = substitutor.substitute(inferenceVariable);
656         if (substitutedReturnType != null) {
657           addConstraint(new TypeCompatibilityConstraint(targetType, PsiUtil.captureToplevelWildcards(substitutedReturnType, context)));
658         }
659       }
660       else {
661         addConstraint(new TypeCompatibilityConstraint(targetType, returnType));
662       }
663     }
664   }
665
666   private InferenceVariable[] initFreshVariablesForCapturedBounds(PsiTypeParameter[] typeParameters, PsiType[] parameters) {
667     if (Registry.is("javac.fresh.variables.for.captured.wildcards.only")) {
668       final List<PsiTypeParameter> capturedParams = new ArrayList<>();
669
670       PsiSubstitutor restParamSubstitution = PsiSubstitutor.EMPTY;
671       for (int i = 0; i < parameters.length; i++) {
672         PsiType parameter = parameters[i];
673         if (parameter instanceof PsiCapturedWildcardType) {
674           capturedParams.add(typeParameters[i]);
675         }
676         else {
677           restParamSubstitution = restParamSubstitution.put(typeParameters[i], parameter);
678         }
679       }
680       InferenceVariable[] variables = initBounds(null, restParamSubstitution, capturedParams.toArray(PsiTypeParameter.EMPTY_ARRAY));
681       int idx = 0;
682       for (PsiType parameter : parameters) {
683         if (parameter instanceof PsiCapturedWildcardType) {
684           InferenceVariable variable = variables[idx++];
685           if (isProperType(((PsiCapturedWildcardType)parameter).getWildcard())) {
686             variable.putUserData(ORIGINAL_CAPTURE, (PsiCapturedWildcardType)parameter);
687           }
688         }
689       }
690       return variables;
691     }
692     return initBounds(null, typeParameters);
693   }
694
695   private InferenceVariable shouldResolveAndInstantiate(PsiType returnType, PsiType targetType) {
696     final InferenceVariable inferenceVariable = getInferenceVariable(returnType);
697     if (inferenceVariable != null) {
698       if (targetType instanceof PsiPrimitiveType && hasPrimitiveWrapperBound(inferenceVariable)) {
699         return inferenceVariable;
700       }
701       if (targetType instanceof PsiClassType) {
702         if (hasUncheckedBounds(inferenceVariable, (PsiClassType)targetType, this) ||
703             hasWildcardParameterization(inferenceVariable, (PsiClassType)targetType)) {
704           return inferenceVariable;
705         }
706       }
707     }
708     return null;
709   }
710   
711   private static boolean hasPrimitiveWrapperBound(InferenceVariable inferenceVariable) {
712     final InferenceBound[] boundTypes = {InferenceBound.UPPER, InferenceBound.LOWER, InferenceBound.EQ};
713     for (InferenceBound inferenceBound : boundTypes) {
714       final List<PsiType> bounds = inferenceVariable.getBounds(inferenceBound);
715       for (PsiType bound : bounds) {
716         if (PsiPrimitiveType.getUnboxedType(bound) != null) {
717           return true;
718         }
719       }
720     }
721     return false;
722   }
723
724   private static boolean hasUncheckedBounds(InferenceVariable inferenceVariable,
725                                             PsiClassType targetType,
726                                             InferenceSession session) {
727     if (!targetType.isRaw()) {
728       final InferenceBound[] boundTypes = {InferenceBound.EQ, InferenceBound.LOWER};
729       for (InferenceBound inferenceBound : boundTypes) {
730         final List<PsiType> bounds = inferenceVariable.getBounds(inferenceBound);
731         for (PsiType bound : bounds) {
732           if (TypeCompatibilityConstraint.isUncheckedConversion(targetType, bound, session)) {
733             return true;
734           }
735         }
736       }
737     }
738     return false;
739   }
740
741   /**
742    * T is a reference type, but is not a wildcard-parameterized type, and either 
743    *  i)  B2 contains a bound of one of the forms alpha=S or S<:alpha, where S is a wildcard-parameterized type, or
744    *  ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha,
745    *      where S1 and S2 have supertypes that are two different parameterizations of the same generic class or interface. 
746    */
747   private static boolean hasWildcardParameterization(InferenceVariable inferenceVariable, PsiClassType targetType) {
748     if (!FunctionalInterfaceParameterizationUtil.isWildcardParameterized(targetType)) {
749       final List<PsiType> bounds = inferenceVariable.getBounds(InferenceBound.LOWER);
750       final Processor<Pair<PsiType, PsiType>> differentParameterizationProcessor =
751         pair -> pair.first == null || pair.second == null || !TypesDistinctProver.provablyDistinct(pair.first, pair.second);
752       if (findParameterizationOfTheSameGenericClass(bounds, differentParameterizationProcessor) != null) return true;
753       final List<PsiType> eqBounds = inferenceVariable.getBounds(InferenceBound.EQ);
754       final List<PsiType> boundsToCheck = new ArrayList<>(bounds);
755       boundsToCheck.addAll(eqBounds);
756       for (PsiType lowBound : boundsToCheck) {
757         if (FunctionalInterfaceParameterizationUtil.isWildcardParameterized(lowBound)) {
758           return true;
759         }
760       }
761     }
762     return false;
763   }
764
765   public static PsiType getTargetType(final PsiElement context) {
766     PsiType targetType = getTargetTypeFromParent(context, new Ref<>(), true);
767     if (targetType instanceof PsiClassType) {
768       return ((PsiClassType)targetType).setLanguageLevel(PsiUtil.getLanguageLevel(context));
769     }
770     return targetType;
771   }
772
773   /**
774    * @param inferParent false during inference; 
775    *                    conditional expression type can't be asked during inference as it is a poly expression and 
776    *                    {@link ExpressionCompatibilityConstraint} should be created instead 
777    */
778   private static PsiType getTargetTypeFromParent(final PsiElement context, Ref<String> errorMessage, boolean inferParent) {
779     PsiType targetType = PsiTypesUtil.getExpectedTypeByParent(context);
780     if (targetType != null) {
781       return targetType;
782     }
783     final PsiElement parent = PsiUtil.skipParenthesizedExprUp(context.getParent());
784     if (parent instanceof PsiExpressionList) {
785       PsiElement gParent = parent.getParent();
786       if (gParent instanceof PsiAnonymousClass) {
787         gParent = gParent.getParent();
788       }
789       if (gParent instanceof PsiCall) {
790         final PsiExpressionList argumentList = ((PsiCall)gParent).getArgumentList();
791         if (argumentList != null) {
792           if (MethodCandidateInfo.isOverloadCheck(argumentList)) {
793             return ThreadLocalTypes.getElementType(context);
794           }
795
796           final JavaResolveResult result = PsiDiamondType.getDiamondsAwareResolveResult((PsiCall)gParent);
797           final PsiElement element = result.getElement();
798           if (element == null) {
799             errorMessage.set("Overload resolution failed");
800             return null;
801           }
802           if (element instanceof PsiMethod && (inferParent || !((PsiMethod)element).hasTypeParameters())) {
803             final boolean varargs = result instanceof MethodCandidateInfo && ((MethodCandidateInfo)result).isVarargs();
804             return PsiTypesUtil.getTypeByMethod(context, argumentList, result.getElement(), varargs, result.getSubstitutor(), inferParent);
805           }
806         }
807       }
808     }
809     else if (parent instanceof PsiConditionalExpression) {
810       return getTargetTypeFromParent(parent, errorMessage, inferParent);
811     }
812     else if (parent instanceof PsiLambdaExpression) {
813       return getTargetTypeFromParentLambda((PsiLambdaExpression)parent, errorMessage, inferParent);
814     }
815     else if (parent instanceof PsiReturnStatement) {
816       return getTargetTypeFromParentLambda(PsiTreeUtil.getParentOfType(parent, PsiLambdaExpression.class, true, PsiMethod.class),
817                                            errorMessage, inferParent);
818     }
819     PsiSwitchExpression switchExpression = PsiTreeUtil.getParentOfType(parent, PsiSwitchExpression.class);
820     if (switchExpression  != null && PsiUtil.getSwitchResultExpressions(switchExpression).contains(context)) {
821       return getTargetType(switchExpression);
822     }
823     return null;
824   }
825
826   private static PsiType getTargetTypeFromParentLambda(PsiLambdaExpression lambdaExpression, Ref<String> errorMessage, boolean inferParent) {
827     if (lambdaExpression != null) {
828       final PsiType typeTypeByParentCall = getTargetTypeFromParent(lambdaExpression, errorMessage, inferParent);
829       if (typeTypeByParentCall != null) {
830         return LambdaUtil.getFunctionalInterfaceReturnType(lambdaExpression.getGroundTargetType(typeTypeByParentCall));
831       }
832
833       //during checked exception constraint processing
834       //we may need to infer types for nested calls to infer unhandled exceptions inside lambda body
835       //at this time, types of interface method parameter types must be already calculated
836       // that's why walkUp in InferenceSessionContainer stops at this point and
837       //that's why we can reuse this type here
838       PsiType cachedLambdaType = ThreadLocalTypes.getElementType(lambdaExpression);
839       if (cachedLambdaType != null) {
840         return LambdaUtil.getFunctionalInterfaceReturnType(lambdaExpression.getGroundTargetType(cachedLambdaType));
841       }
842
843       return inferParent || !(PsiUtil.skipParenthesizedExprUp(lambdaExpression.getParent()) instanceof PsiExpressionList) 
844              ? LambdaUtil.getFunctionalInterfaceReturnType(lambdaExpression.getFunctionalInterfaceType()) : null;
845     }
846     return null;
847   }
848
849   public InferenceVariable getInferenceVariable(PsiType psiType) {
850     final PsiClass psiClass = PsiUtil.resolveClassInClassTypeOnly(psiType);
851     return psiClass instanceof InferenceVariable ? getInferenceVariable((PsiTypeParameter)psiClass) : null;
852   }
853
854   public boolean isProperType(@Nullable PsiType type) {
855     return collectDependencies(type, null);
856   }
857
858   public boolean collectDependencies(@Nullable PsiType type,
859                                      @Nullable final Set<? super InferenceVariable> dependencies) {
860     return collectDependencies(type, dependencies, classType -> getInferenceVariable(classType));
861   }
862
863   public static boolean collectDependencies(@Nullable PsiType type,
864                                             @Nullable final Set<? super InferenceVariable> dependencies,
865                                             final Function<? super PsiClassType, ? extends InferenceVariable> fun) {
866     if (type == null) return true;
867     final Boolean isProper = type.accept(new PsiTypeVisitor<Boolean>() {
868       @Override
869       public Boolean visitType(PsiType type) {
870         return true;
871       }
872
873       @Override
874       public Boolean visitCapturedWildcardType(PsiCapturedWildcardType capturedWildcardType) {
875         return true;
876       }
877
878       @Override
879       public Boolean visitArrayType(PsiArrayType arrayType) {
880         return arrayType.getComponentType().accept(this);
881       }
882
883       @Override
884       public Boolean visitWildcardType(PsiWildcardType wildcardType) {
885         final PsiType bound = wildcardType.getBound();
886         if (bound == null) return true;
887         return bound.accept(this);
888       }
889
890       @Override
891       public Boolean visitClassType(PsiClassType classType) {
892         final InferenceVariable inferenceVariable = fun.fun(classType);
893         if (inferenceVariable != null) {
894           if (dependencies != null) {
895             dependencies.add(inferenceVariable);
896             return true;
897           }
898           return false;
899         }
900         PsiClassType.ClassResolveResult result = classType.resolveGenerics();
901         PsiClass aClass = result.getElement();
902         if (aClass != null) {
903           PsiSubstitutor substitutor = result.getSubstitutor();
904           for (PsiTypeParameter typeParameter : PsiUtil.typeParametersIterable(aClass)) {
905             PsiType psiType = substitutor.substitute(typeParameter);
906             if (psiType != null && !psiType.accept(this)) return false;
907           }
908         }
909         return true;
910       }
911     });
912     return dependencies != null ? !dependencies.isEmpty() : isProper;
913   }
914
915   public boolean repeatInferencePhases() {
916     do {
917       if (!reduceConstraints()) {
918         //inference error occurred
919         return false;
920       }
921
922       if (!myIncorporationPhase.incorporate()) {
923         return false;
924       }
925     } while (!myIncorporationPhase.isFullyIncorporated() || myConstraintIdx < myConstraints.size());
926
927     return true;
928   }
929
930   private boolean reduceConstraints() {
931     List<ConstraintFormula> newConstraints = new ArrayList<>();
932     for (int i = myConstraintIdx; i < myConstraints.size(); i++) {
933       ConstraintFormula constraint = myConstraints.get(i);
934       if (!constraint.reduce(this, newConstraints)) {
935         return false;
936       }
937     }
938     myConstraintIdx = myConstraints.size();
939     for (ConstraintFormula constraint : newConstraints) {
940       addConstraint(constraint);
941     }
942     return true;
943   }
944
945   private boolean isThrowable(List<PsiType> upperBounds) {
946     boolean commonThrowable = false;
947     for (PsiType upperBound : upperBounds) {
948       if (upperBound.equalsToText(CommonClassNames.JAVA_LANG_OBJECT) || !isProperType(upperBound)) continue;
949       if (upperBound.equalsToText(CommonClassNames.JAVA_LANG_EXCEPTION) ||
950           upperBound.equalsToText(CommonClassNames.JAVA_LANG_THROWABLE)) {
951         commonThrowable = true;
952       } else {
953         return false;
954       }
955     }
956     return commonThrowable;
957   }
958
959   private PsiType substituteNonProperBound(PsiType bound, PsiSubstitutor substitutor) {
960     final HashSet<InferenceVariable> dependencies = new LinkedHashSet<>();
961     if (!collectDependencies(bound, dependencies)) {
962       return bound;
963     }
964     for (InferenceVariable dependency : dependencies) {
965       PsiType instantiation = dependency.getInstantiation();
966       if (instantiation != PsiType.NULL) {
967         substitutor = substitutor.put(dependency, instantiation);
968       }
969     }
970     return substitutor.substitute(bound);
971   }
972
973   private  boolean hasBoundProblems(final List<InferenceVariable> typeParams,
974                                     final PsiSubstitutor substitutor) {
975     for (InferenceVariable typeParameter : typeParams) {
976       if (typeParameter.getInstantiation() != PsiType.NULL) continue;
977       if (typeParameter.getUserData(ORIGINAL_CAPTURE) != null) continue;
978       final PsiType type = substitutor.substitute(typeParameter);
979       if (type instanceof PsiClassType) {
980         final PsiClass aClass = ((PsiClassType)type).resolve();
981         if (aClass instanceof PsiTypeParameter && TypeConversionUtil.isFreshVariable((PsiTypeParameter)aClass)) {
982           continue;
983         }
984       }
985       final List<PsiType> extendsTypes = typeParameter.getBounds(InferenceBound.UPPER);
986       final PsiType[] bounds = extendsTypes.toArray(PsiType.EMPTY_ARRAY);
987       if (GenericsUtil.findTypeParameterBoundError(typeParameter, bounds, substitutor, myContext, true) != null) {
988         return true;
989       }
990     }
991     return false;
992   }
993
994   protected void resolveBounds(final Collection<InferenceVariable> inferenceVariables,
995                              @NotNull PsiSubstitutor substitutor) {
996     final UniqueNameGenerator uniqueNameGenerator = new UniqueNameGenerator();
997     final Collection<InferenceVariable> allVars = new ArrayList<>(inferenceVariables);
998     while (!allVars.isEmpty()) {
999       final List<InferenceVariable> vars = InferenceVariablesOrder.resolveOrder(allVars, this);
1000       List<InferenceVariable> unresolved = new ArrayList<>();
1001       for (InferenceVariable var : vars) {
1002         final PsiType eqBound = getEqualsBound(var, substitutor);
1003         if (eqBound == PsiType.NULL) {
1004           unresolved.add(var);
1005         }
1006       }
1007       if (!unresolved.isEmpty() && vars.size() > unresolved.size()) {
1008         vars.removeAll(unresolved);
1009         vars.addAll(unresolved);
1010       }
1011       if (!myIncorporationPhase.hasCaptureConstraints(unresolved)) {
1012         PsiSubstitutor firstSubstitutor = resolveSubset(vars, substitutor);
1013         if (myErrorMessages == null && hasBoundProblems(vars, firstSubstitutor)) {
1014           firstSubstitutor = null;
1015           unresolved = vars;
1016         }
1017         if (firstSubstitutor != null) {
1018           substitutor = firstSubstitutor;
1019           allVars.removeAll(vars);
1020           continue;
1021         }
1022       }
1023
1024       if (!initFreshVariables(substitutor, unresolved, uniqueNameGenerator)) {
1025         return;
1026       }
1027
1028       myIncorporationPhase.forgetCaptures(vars);
1029       if (!repeatInferencePhases()) {
1030         return;
1031       }
1032     }
1033
1034     final Map<PsiTypeParameter, PsiType> map = substitutor.getSubstitutionMap();
1035     for (PsiTypeParameter parameter : map.keySet()) {
1036       final PsiType mapping = map.get(parameter);
1037       PsiTypeParameter param;
1038       if (parameter instanceof InferenceVariable) {
1039         ((InferenceVariable)parameter).setInstantiation(mapping);
1040         if (((InferenceVariable)parameter).getCallContext() != myContext) {
1041           //don't include in result substitutor foreign inference variables
1042           continue;
1043         }
1044         param = ((InferenceVariable)parameter).getParameter();
1045       }
1046       else {
1047         param = parameter;
1048       }
1049       mySiteSubstitutor = mySiteSubstitutor.put(param, mapping);
1050     }
1051   }
1052
1053   private boolean initFreshVariables(PsiSubstitutor substitutor, List<InferenceVariable> vars, UniqueNameGenerator nameGenerator) {
1054     final PsiElementFactory elementFactory = JavaPsiFacade.getElementFactory(getManager().getProject());
1055     PsiSubstitutor ySubstitutor = PsiSubstitutor.EMPTY;
1056     final PsiTypeParameter[] yVars = new PsiTypeParameter[vars.size()];
1057     for (int i = 0; i < vars.size(); i++) {
1058       InferenceVariable var = vars.get(i);
1059       final PsiTypeParameter parameter = var.getParameter();
1060       yVars[i] = elementFactory.createTypeParameterFromText(nameGenerator.generateUniqueName(parameter.getName()), parameter);
1061       ySubstitutor = ySubstitutor.put(var, elementFactory.createType(yVars[i]));
1062     }
1063     for (int i = 0; i < yVars.length; i++) {
1064       PsiTypeParameter parameter = yVars[i];
1065       final InferenceVariable var = vars.get(i);
1066       final PsiType upperBound = composeBound(var, InferenceBound.UPPER, UPPER_BOUND_FUNCTION, ySubstitutor.putAll(substitutor), true);
1067       final PsiType lub = getLowerBound(var, substitutor);
1068       PsiType lowerBound;
1069       if (lub != PsiType.NULL) {
1070         for (PsiClassType upperBoundType : parameter.getExtendsListTypes()) {
1071           if (!TypeConversionUtil.isAssignable(upperBoundType, lub)) {
1072             return false;
1073           }
1074         }
1075         lowerBound = lub;
1076       }
1077       else if (myPolicy.inferLowerBoundForFreshVariables()) {
1078         lowerBound = upperBound;
1079       }
1080       else {
1081         lowerBound = null;
1082       }
1083       TypeConversionUtil.setInferredBoundsForSynthetic(parameter, lowerBound, upperBound);
1084       TypeConversionUtil.markAsFreshVariable(parameter, myContext);
1085       if (!var.addBound(elementFactory.createType(parameter), InferenceBound.EQ, myIncorporationPhase)) {
1086         return false;
1087       }
1088     }
1089     return true;
1090   }
1091
1092   private PsiSubstitutor resolveSubsetOrdered(Set<InferenceVariable> varsToResolve, PsiSubstitutor siteSubstitutor) {
1093     PsiSubstitutor substitutor = siteSubstitutor;
1094     final Iterator<List<InferenceVariable>> varsIterator = InferenceVariablesOrder.resolveOrderIterator(varsToResolve, this);
1095     while (varsIterator.hasNext()) {
1096       List<InferenceVariable> vars = varsIterator.next();
1097       final PsiSubstitutor resolveSubset = resolveSubset(vars, substitutor);
1098       substitutor = substitutor.putAll(resolveSubset);
1099     }
1100     return substitutor;
1101   }
1102
1103   @NotNull
1104   private PsiSubstitutor resolveSubset(Collection<InferenceVariable> vars, PsiSubstitutor substitutor) {
1105     if (myErased) {
1106       for (InferenceVariable var : vars) {
1107         substitutor = substitutor.put(var, null);
1108       }
1109     }
1110
1111     for (InferenceVariable var : vars) {
1112       final PsiType instantiation = var.getInstantiation();
1113       final PsiType type = instantiation == PsiType.NULL ? checkBoundsConsistency(substitutor, var) : instantiation;
1114       if (type != PsiType.NULL) {
1115         substitutor = substitutor.put(var, type);
1116       }
1117     }
1118
1119     return substitutor;
1120   }
1121
1122   private PsiType checkBoundsConsistency(PsiSubstitutor substitutor, InferenceVariable var) {
1123     PsiType eqBound = getEqualsBound(var, substitutor);
1124     if (eqBound != PsiType.NULL && eqBound instanceof PsiPrimitiveType) return PsiType.NULL;
1125     PsiType lowerBound = getLowerBound(var, substitutor); 
1126     if (eqBound == PsiType.NULL) {
1127       lowerBound = myPolicy.adjustInferredType(myManager, lowerBound, ConstraintType.SUBTYPE);
1128     }
1129     final PsiType upperBound = getUpperBound(var, substitutor);
1130     PsiType type;
1131     if (eqBound != PsiType.NULL && (myErased || eqBound != null)) {
1132       PsiClass aClass = PsiUtil.resolveClassInClassTypeOnly(eqBound);
1133       if (aClass instanceof PsiTypeParameter && TypeConversionUtil.isFreshVariable((PsiTypeParameter)aClass)) {
1134         PsiCapturedWildcardType capturedWildcard = var.getUserData(ORIGINAL_CAPTURE);
1135
1136         //restore captured wildcard from method return type when no additional constraints were inferred
1137         //to preserve equality of type arguments
1138         if (capturedWildcard != null &&
1139             capturedWildcard.getUpperBound().equals(TypeConversionUtil.getInferredUpperBoundForSynthetic((PsiTypeParameter)aClass))) {
1140           eqBound = capturedWildcard;
1141         }
1142       }
1143       if (isLowerBoundNotAssignable(var, eqBound, true)) {
1144         final String incompatibleBoundsMessage =
1145           incompatibleBoundsMessage(var, substitutor, InferenceBound.EQ, EQUALITY_CONSTRAINTS_PRESENTATION, InferenceBound.LOWER, LOWER_BOUNDS_PRESENTATION);
1146         registerIncompatibleErrorMessage(incompatibleBoundsMessage);
1147         return PsiType.NULL;
1148       } else {
1149         type = eqBound;
1150
1151         if (isLowerBoundNotAssignable(var, eqBound, false)) {
1152           setErased();
1153         }
1154
1155       }
1156     }
1157     else {
1158       type = InferenceVariable.modifyAnnotations(lowerBound, (lb, modifier) -> modifier.modifyLowerBoundAnnotations(lb, upperBound));
1159     }
1160
1161     if (type == PsiType.NULL) {
1162       if (var.isThrownBound() && myPolicy.inferRuntimeExceptionForThrownBoundWithNoConstraints() && isThrowable(var.getBounds(InferenceBound.UPPER))) {
1163         type =  PsiType.getJavaLangRuntimeException(myManager, GlobalSearchScope.allScope(myManager.getProject()));
1164       }
1165       else {
1166         type = var.getBounds(InferenceBound.UPPER).size() == 1 ? myPolicy.getInferredTypeWithNoConstraint(myManager, upperBound).first : upperBound;
1167       }
1168
1169       if (myErrorMessages == null && type instanceof PsiIntersectionType) {
1170         String conflictingConjunctsMessage = ((PsiIntersectionType)type).getConflictingConjunctsMessage();
1171         if (conflictingConjunctsMessage == null) {
1172           if (findParameterizationOfTheSameGenericClass(var.getBounds(InferenceBound.UPPER),
1173                                                         pair -> pair.first == null || pair.second == null ||
1174                                                                 Comparing.equal(substituteNonProperBound(pair.first, substitutor),
1175                                                                                 substituteNonProperBound(pair.second, substitutor))) != null) {
1176             //warn if upper bounds has same generic class with different type arguments
1177             conflictingConjunctsMessage = type.getPresentableText(false);
1178           }
1179           else {
1180             conflictingConjunctsMessage = getConjunctsConflict((PsiIntersectionType)type);
1181           }
1182         }
1183         if (conflictingConjunctsMessage != null) {
1184           registerIncompatibleErrorMessage("Type parameter " + var.getParameter().getName() + " has incompatible upper bounds: " + conflictingConjunctsMessage);
1185           return PsiType.NULL;
1186         }
1187       }
1188     }
1189     else {
1190       for (PsiType upperType : var.getBounds(InferenceBound.UPPER)) {
1191         if (myErrorMessages == null && isProperType(upperType)) {
1192           if (type != lowerBound && !TypeConversionUtil.isAssignable(upperType, type)) {
1193             registerIncompatibleErrorMessage(incompatibleBoundsMessage(var, substitutor, InferenceBound.EQ, EQUALITY_CONSTRAINTS_PRESENTATION, InferenceBound.UPPER, UPPER_BOUNDS_PRESENTATION));
1194             return PsiType.NULL;
1195           }
1196           else if (type == lowerBound) {
1197             for (PsiType lowerBoundConjunct : var.getBounds(InferenceBound.LOWER)) {
1198               if (isProperType(lowerBoundConjunct) && !TypeConversionUtil.isAssignable(upperType, lowerBoundConjunct)) {
1199                 registerIncompatibleErrorMessage(incompatibleBoundsMessage(var, substitutor, InferenceBound.LOWER, LOWER_BOUNDS_PRESENTATION, InferenceBound.UPPER, UPPER_BOUNDS_PRESENTATION));
1200                 return PsiType.NULL;
1201               }
1202             }
1203           }
1204         }
1205       }
1206     }
1207     if (type == PsiType.NULL) {
1208       registerIncompatibleErrorMessage("Incompatible upper bounds: " + StringUtil.join(var.getBounds(InferenceBound.UPPER), bound -> {
1209         final PsiType substituted = substituteNonProperBound(bound, substitutor);
1210         return getPresentableText(substituted != null ? substituted : bound);
1211       }, ", "));
1212     }
1213     return type;
1214   }
1215
1216   private boolean isLowerBoundNotAssignable(InferenceVariable var, PsiType eqBound, boolean allowUncheckedConversion) {
1217     return var
1218       .getBounds(InferenceBound.LOWER)
1219       .stream()
1220       .anyMatch(lBound -> isProperType(lBound) && !TypeConversionUtil.isAssignable(eqBound, lBound, allowUncheckedConversion));
1221   }
1222
1223   private static String getConjunctsConflict(PsiIntersectionType type) {
1224     PsiType[] conjuncts = type.getConjuncts();
1225     for (int i = 0; i < conjuncts.length; i++) {
1226       PsiClass conjunct = PsiUtil.resolveClassInClassTypeOnly(conjuncts[i]);
1227       for (int i1 = 0; i1 < conjuncts.length; i1++) {
1228         if (i == i1) continue;
1229         PsiClass oppositeConjunct = PsiUtil.resolveClassInClassTypeOnly(conjuncts[i1]);
1230         if (conjunct == null || oppositeConjunct == null) {
1231           if (conjuncts[i] instanceof PsiArrayType &&
1232                 TypesDistinctProver.proveArrayTypeDistinct((PsiArrayType)conjuncts[i], conjuncts[i1]) ||
1233               conjuncts[i] instanceof PsiCapturedWildcardType &&
1234                 oppositeConjunct != null && !oppositeConjunct.isInterface() && !(oppositeConjunct instanceof PsiTypeParameter)) {
1235             return conjuncts[i].getPresentableText() + " and " + conjuncts[i1].getPresentableText();
1236           }
1237         }
1238       }
1239     }
1240     return null;
1241   }
1242
1243   public String getPresentableText(PsiType psiType) {
1244     final PsiType substituted = myRestoreNameSubstitution.substitute(psiType);
1245     return substituted != null ? substituted.getPresentableText() : null;
1246   }
1247
1248   public void registerIncompatibleErrorMessage(Collection<InferenceVariable> variables, String incompatibleTypesMessage) {
1249     variables = new ArrayList<>(variables);
1250     ((ArrayList<InferenceVariable>)variables).sort((v1, v2) -> Comparing.compare(v1.getName(), v2.getName()));
1251     final String variablesEnumeration = StringUtil.join(variables, variable -> variable.getParameter().getName(), ", ");
1252     registerIncompatibleErrorMessage("no instance(s) of type variable(s) " + variablesEnumeration + 
1253                                      (variablesEnumeration.isEmpty() ? "" : " ") + "exist so that " + incompatibleTypesMessage);
1254   }
1255   
1256   public void registerIncompatibleErrorMessage(@NotNull String incompatibleBoundsMessage) {
1257     if (myErrorMessages == null) {
1258       myErrorMessages = new ArrayList<>();
1259     }
1260     if (!myErrorMessages.contains(incompatibleBoundsMessage)) {
1261       myErrorMessages.add(incompatibleBoundsMessage);
1262     }
1263   }
1264
1265   private String incompatibleBoundsMessage(final InferenceVariable var,
1266                                                   final PsiSubstitutor substitutor,
1267                                                   final InferenceBound lowBound,
1268                                                   final String lowBoundName,
1269                                                   final InferenceBound upperBound,
1270                                                   final String upperBoundName) {
1271     final Function<PsiType, String> typePresentation = type -> {
1272       final PsiType substituted = substituteNonProperBound(type, substitutor);
1273       return getPresentableText(substituted != null ? substituted : type);
1274     };
1275     return "inference variable " + var.getParameter().getName() + " has incompatible bounds:\n " + 
1276            lowBoundName  + ": " + StringUtil.join(var.getBounds(lowBound), typePresentation, ", ") + "\n" + 
1277            upperBoundName + ": " + StringUtil.join(var.getBounds(upperBound), typePresentation, ", ");
1278   }
1279
1280   private PsiType getLowerBound(InferenceVariable var, PsiSubstitutor substitutor) {
1281     return composeBound(var, InferenceBound.LOWER, pair -> GenericsUtil.getLeastUpperBound(pair.first, pair.second, myManager), substitutor);
1282   }
1283
1284   private PsiType getUpperBound(InferenceVariable var, PsiSubstitutor substitutor) {
1285     return composeBound(var, InferenceBound.UPPER, UPPER_BOUND_FUNCTION, substitutor);
1286   }
1287
1288   private PsiType getEqualsBound(InferenceVariable var, PsiSubstitutor substitutor) {
1289     return composeBound(var, InferenceBound.EQ, pair -> !Comparing.equal(pair.first, pair.second) ? null : pair.first, substitutor);
1290   }
1291
1292   private PsiType composeBound(InferenceVariable variable,
1293                                InferenceBound boundType,
1294                                Function<? super Pair<PsiType, PsiType>, ? extends PsiType> fun,
1295                                PsiSubstitutor substitutor) {
1296     return composeBound(variable, boundType, fun, substitutor, false);
1297   }
1298
1299   private PsiType composeBound(InferenceVariable variable,
1300                                InferenceBound boundType,
1301                                Function<? super Pair<PsiType, PsiType>, ? extends PsiType> fun,
1302                                PsiSubstitutor substitutor,
1303                                boolean includeNonProperBounds) {
1304     final List<PsiType> bounds = variable.getBounds(boundType);
1305     PsiType lub = PsiType.NULL;
1306     for (PsiType bound : bounds) {
1307       bound = substituteNonProperBound(bound, substitutor);
1308       if (includeNonProperBounds || isProperType(bound)) {
1309         if (lub == PsiType.NULL) {
1310           lub = bound;
1311         }
1312         else {
1313           final Pair<PsiType, PsiType> pair = Pair.create(lub, bound);
1314           lub = fun.fun(pair);
1315           if (lub == null) {
1316             return PsiType.NULL;
1317           }
1318         }
1319       }
1320     }
1321     return lub;
1322   }
1323
1324   public PsiManager getManager() {
1325     return myManager;
1326   }
1327
1328   public GlobalSearchScope getScope() {
1329     if (myContext != null) {
1330       return myContext.getResolveScope();
1331     }
1332     return GlobalSearchScope.allScope(myManager.getProject());
1333   }
1334
1335   public Collection<InferenceVariable> getInferenceVariables() {
1336     return myInferenceVariables;
1337   }
1338
1339   public void addConstraint(ConstraintFormula constraint) {
1340     if (myConstraintsCopy.add(constraint)) {
1341         myConstraints.add(constraint);
1342       }
1343   }
1344
1345   private boolean proceedWithAdditionalConstraints(Set<ConstraintFormula> additionalConstraints, Set<ConstraintFormula> ignoredConstraints) {
1346     //empty substitutor should be used to resolve input variables:
1347     //all types in additional constraints are already substituted during collecting phase, 
1348     //recursive site substitutors (T -> List<T>) would make additional constraints work with multiple times substituted types, which is incorrect.
1349     //at the same time, recursive substitutions should not appear during inference but appear rather on site,
1350     //so the problem should not influence consequence substitution of additional constraints
1351     final PsiSubstitutor siteSubstitutor = PsiSubstitutor.EMPTY;
1352
1353     while (!additionalConstraints.isEmpty()) {
1354       //extract subset of constraints
1355       final Set<ConstraintFormula> subset = buildSubset(additionalConstraints, ignoredConstraints);
1356
1357       //collect all input variables of selection
1358       final Set<InferenceVariable> varsToResolve = new LinkedHashSet<>();
1359       for (ConstraintFormula formula : subset) {
1360         if (formula instanceof InputOutputConstraintFormula) {
1361           collectVarsToResolve(varsToResolve, (InputOutputConstraintFormula)formula);
1362         }
1363       }
1364
1365       final PsiSubstitutor substitutor = resolveSubsetOrdered(varsToResolve, siteSubstitutor);
1366       for (ConstraintFormula formula : subset) {
1367         if (!processOneConstraint(formula, additionalConstraints, substitutor, ignoredConstraints)) return false;
1368       }
1369     }
1370     return true;
1371   }
1372
1373   private void collectVarsToResolve(Set<? super InferenceVariable> varsToResolve, InputOutputConstraintFormula formula) {
1374     final Set<InferenceVariable> inputVariables = formula.getInputVariables(this);
1375     if (inputVariables != null) {
1376       for (InferenceVariable inputVariable : inputVariables) {
1377         varsToResolve.addAll(inputVariable.getDependencies(this));
1378       }
1379       varsToResolve.addAll(inputVariables);
1380     }
1381   }
1382
1383   private boolean processOneConstraint(ConstraintFormula formula,
1384                                        Set<ConstraintFormula> additionalConstraints,
1385                                        PsiSubstitutor substitutor, 
1386                                        Set<ConstraintFormula> ignoredConstraints) {
1387     formula.apply(substitutor, true);
1388     if (formula instanceof InputOutputConstraintFormula) {
1389       myTempTypes.forceType(((InputOutputConstraintFormula)formula).getExpression(),
1390                             ((InputOutputConstraintFormula)formula).getCurrentType());
1391     }
1392
1393     addConstraint(formula);
1394     if (!repeatInferencePhases()) {
1395       return false;
1396     }
1397
1398     if (formula instanceof ExpressionCompatibilityConstraint) {
1399       PsiExpression expression = ((ExpressionCompatibilityConstraint)formula).getExpression();
1400       if (expression instanceof PsiLambdaExpression) {
1401         PsiType parameterType = ((PsiLambdaExpression)expression).getGroundTargetType(((ExpressionCompatibilityConstraint)formula).getCurrentType());
1402         collectLambdaReturnExpression(additionalConstraints, ignoredConstraints, (PsiLambdaExpression)expression, parameterType, !isProperType(parameterType), substitutor);
1403       }
1404     }
1405     return true;
1406   }
1407
1408   private Set<ConstraintFormula> buildSubset(final Set<ConstraintFormula> additionalConstraints,
1409                                              final Set<ConstraintFormula> ignoredConstraints) {
1410
1411     final Set<InferenceVariable> outputVariables = getOutputVariables(additionalConstraints);
1412     final Set<InferenceVariable> ignoredOutputVariables = getOutputVariables(ignoredConstraints);
1413
1414     Set<ConstraintFormula> subset = new LinkedHashSet<>();
1415
1416     Set<ConstraintFormula> noInputVariables = new LinkedHashSet<>();
1417     for (ConstraintFormula constraint : additionalConstraints) {
1418       if (constraint instanceof InputOutputConstraintFormula) {
1419         final Set<InferenceVariable> inputVariables = ((InputOutputConstraintFormula)constraint).getInputVariables(this);
1420         if (inputVariables != null) {
1421           boolean dependsOnOutput = false;
1422           for (InferenceVariable inputVariable : inputVariables) {
1423             if (dependsOnOutput) break;
1424             final Set<InferenceVariable> dependencies = inputVariable.getDependencies(this);
1425             dependencies.add(inputVariable);
1426             if (!hasCapture(inputVariable)) {
1427               if (dependsOnOutput(ignoredOutputVariables, dependencies)) {
1428                 dependsOnOutput = true;
1429                 ignoredConstraints.add(constraint);
1430                 break;
1431               }
1432               else {
1433                 dependsOnOutput = dependsOnOutput(outputVariables, dependencies);
1434               }
1435             }
1436
1437             dependencies.retainAll(outputVariables);
1438             if (!dependencies.isEmpty()) {
1439               dependsOnOutput = true;
1440               break;
1441             }
1442           }
1443           if (!dependsOnOutput) {
1444             subset.add(constraint);
1445
1446             if (inputVariables.isEmpty()) {
1447               noInputVariables.add(constraint);
1448             }
1449           }
1450         }
1451         else {
1452           subset.add(constraint);
1453           noInputVariables.add(constraint);
1454         }
1455       }
1456       else {
1457         subset.add(constraint);
1458       }
1459     }
1460     if (subset.isEmpty()) {
1461       additionalConstraints.removeAll(ignoredConstraints);
1462       if (!additionalConstraints.isEmpty()) {
1463         subset.add(additionalConstraints.iterator().next()); //todo choose one constraint
1464       }
1465     }
1466     
1467     if (!noInputVariables.isEmpty()) {
1468       subset = noInputVariables;
1469     }
1470
1471     additionalConstraints.removeAll(subset);
1472     return subset;
1473   }
1474
1475   private boolean dependsOnOutput(Set<InferenceVariable> outputVariables, Set<InferenceVariable> dependencies) {
1476     for (InferenceVariable outputVariable : outputVariables) {
1477       if (ContainerUtil.intersects(outputVariable.getDependencies(this), dependencies)) {
1478         return true;
1479       }
1480     }
1481     return false;
1482   }
1483
1484   @NotNull
1485   private Set<InferenceVariable> getOutputVariables(Set<ConstraintFormula> constraintFormulas) {
1486     final Set<InferenceVariable> outputVariables = new HashSet<>();
1487     for (ConstraintFormula constraint : constraintFormulas) {
1488       if (constraint instanceof InputOutputConstraintFormula) {
1489         final Set<InferenceVariable> inputVariables = ((InputOutputConstraintFormula)constraint).getInputVariables(this);
1490         final Set<InferenceVariable> outputVars = ((InputOutputConstraintFormula)constraint).getOutputVariables(inputVariables, this);
1491         if (outputVars != null) {
1492           outputVariables.addAll(outputVars);
1493         }
1494       }
1495     }
1496     return outputVariables;
1497   }
1498
1499   public PsiSubstitutor collectApplicabilityConstraints(final PsiMethodReferenceExpression reference, 
1500                                                         final MethodCandidateInfo candidateInfo,
1501                                                         final PsiType functionalInterfaceType) {
1502     final PsiClassType.ClassResolveResult resolveResult = PsiUtil.resolveGenericsClassInType(functionalInterfaceType);
1503     final PsiMethod interfaceMethod = LambdaUtil.getFunctionalInterfaceMethod(resolveResult);
1504     LOG.assertTrue(interfaceMethod != null, myContext);
1505     final PsiSubstitutor functionalInterfaceSubstitutor = LambdaUtil.getSubstitutor(interfaceMethod, resolveResult);
1506     final MethodSignature signature = interfaceMethod.getSignature(functionalInterfaceSubstitutor);
1507
1508     final boolean varargs = candidateInfo.isVarargs();
1509     final PsiMethod method = candidateInfo.getElement();
1510     final PsiClass methodContainingClass = method.getContainingClass();
1511
1512     final PsiMethodReferenceUtil.QualifierResolveResult qualifierResolveResult = PsiMethodReferenceUtil.getQualifierResolveResult(reference);
1513
1514     final PsiClass containingClass = qualifierResolveResult.getContainingClass();
1515     if (containingClass == null) {
1516       return resolveSubset(myInferenceVariables, mySiteSubstitutor); 
1517     }
1518
1519     final PsiParameter[] functionalMethodParameters = interfaceMethod.getParameterList().getParameters();
1520     final PsiParameter[] parameters = method.getParameterList().getParameters();
1521
1522     final boolean isStatic = method.hasModifierProperty(PsiModifier.STATIC);
1523     PsiSubstitutor psiSubstitutor = qualifierResolveResult.getSubstitutor();
1524
1525     if (parameters.length == functionalMethodParameters.length && !varargs || isStatic && varargs) {//static methods
1526
1527       if (method.isConstructor() && PsiUtil.isRawSubstitutor(containingClass, psiSubstitutor)) {
1528         //15.13.1 If ClassType is a raw type, but is not a non-static member type of a raw type,
1529         //the candidate notional member methods are those specified in p15.9.3 for a
1530         //class instance creation expression that uses <> to elide the type arguments to a class
1531         initBounds(containingClass.getTypeParameters());
1532         psiSubstitutor = PsiSubstitutor.EMPTY;
1533       }
1534
1535       if (methodContainingClass != null) {
1536         psiSubstitutor = JavaClassSupers.getInstance().getSuperClassSubstitutor(methodContainingClass, containingClass, reference.getResolveScope(), psiSubstitutor);
1537         if (psiSubstitutor == null) {
1538           LOG.error("derived: " + containingClass +
1539                     "; super: " + methodContainingClass +
1540                     "; reference: " + reference.getText() +
1541                     "; containingFile: " + reference.getContainingFile().getName());
1542         }
1543       }
1544
1545       for (int i = 0; i < functionalMethodParameters.length; i++) {
1546         final PsiType pType = signature.getParameterTypes()[i];
1547         addConstraint(new TypeCompatibilityConstraint(substituteWithInferenceVariables(getParameterType(parameters, i, psiSubstitutor, varargs)),
1548                                                       PsiUtil.captureToplevelWildcards(pType, functionalMethodParameters[i])));
1549       }
1550     }
1551     else if (PsiMethodReferenceUtil.isResolvedBySecondSearch(reference, signature, varargs, isStatic, parameters.length)) { //instance methods
1552       final PsiType pType = signature.getParameterTypes()[0];
1553
1554       // 15.13.1 If the ReferenceType is a raw type, and there exists a parameterization of this type, T, that is a supertype of P1,
1555       // the type to search is the result of capture conversion (5.1.10) applied to T;
1556       // otherwise, the type to search is the same as the type of the first search. Again, the type arguments, if any, are given by the method reference.
1557       if (PsiUtil.isRawSubstitutor(containingClass, psiSubstitutor)) {
1558         PsiClassType subclassType = StrictSubtypingConstraint.getSubclassType(containingClass, pType, true);
1559         final PsiSubstitutor receiverSubstitutor = subclassType != null
1560                                                    ? TypeConversionUtil.getSuperClassSubstitutor(containingClass, (PsiClassType)PsiUtil.captureToplevelWildcards(subclassType, myContext))
1561                                                    : null;
1562         if (receiverSubstitutor != null) {
1563           if (!method.hasTypeParameters()) {
1564             if (signature.getParameterTypes().length == 1 || PsiUtil.isRawSubstitutor(containingClass, receiverSubstitutor)) {
1565               return methodContainingClass != null ? JavaClassSupers.getInstance().getSuperClassSubstitutor(methodContainingClass, containingClass, reference.getResolveScope(), receiverSubstitutor)
1566                                                    : receiverSubstitutor;
1567             }
1568           }
1569           mySiteSubstitutor = mySiteSubstitutor.putAll(receiverSubstitutor);
1570
1571           if (methodContainingClass != null) {
1572             final PsiSubstitutor superSubstitutor = JavaClassSupers.getInstance().getSuperClassSubstitutor(methodContainingClass, containingClass, reference.getResolveScope(), receiverSubstitutor);
1573             LOG.assertTrue(superSubstitutor != null, "mContainingClass: " + methodContainingClass.getName() + "; containingClass: " + containingClass.getName());
1574             mySiteSubstitutor = mySiteSubstitutor.putAll(superSubstitutor);
1575           }
1576
1577           psiSubstitutor = receiverSubstitutor;
1578         }
1579       }
1580
1581       //no additional constraints for array creation
1582       PsiElementFactory factory = JavaPsiFacade.getElementFactory(myManager.getProject());
1583       if (PsiUtil.isArrayClass(containingClass)) {
1584         return null;
1585       }
1586
1587       final PsiType qType = factory.createType(containingClass, psiSubstitutor);
1588
1589       addConstraint(new TypeCompatibilityConstraint(substituteWithInferenceVariables(qType), 
1590                                                     PsiUtil.captureToplevelWildcards(pType, reference)));
1591
1592       if (methodContainingClass != null) {
1593         psiSubstitutor = JavaClassSupers.getInstance().getSuperClassSubstitutor(methodContainingClass, containingClass, reference.getResolveScope(), psiSubstitutor);
1594         LOG.assertTrue(psiSubstitutor != null, "derived: " + containingClass +
1595                                                "; super: " + methodContainingClass +
1596                                                "; reference: " + reference.getText() +
1597                                                "; containingFile: " + reference.getContainingFile().getName());
1598       }
1599
1600       for (int i = 0; i < signature.getParameterTypes().length - 1; i++) {
1601         final PsiType interfaceParamType = signature.getParameterTypes()[i + 1];
1602         addConstraint(new TypeCompatibilityConstraint(substituteWithInferenceVariables(getParameterType(parameters, i, psiSubstitutor, varargs)),
1603                                                       PsiUtil.captureToplevelWildcards(interfaceParamType, functionalMethodParameters[i])));
1604       }
1605     }
1606
1607     return null;
1608   }
1609
1610   public void setErased() {
1611     myErased = true;
1612   }
1613
1614   private InferenceVariable getInferenceVariable(PsiTypeParameter parameter) {
1615     return parameter instanceof InferenceVariable && myInferenceVariables.contains(parameter) ? (InferenceVariable)parameter : null;
1616   }
1617
1618   /**
1619    * 18.5.4 More Specific Method Inference 
1620    */
1621   public static boolean isMoreSpecific(final PsiMethod m1,
1622                                        final PsiMethod m2,
1623                                        final PsiSubstitutor siteSubstitutor1,
1624                                        final PsiExpression[] args,
1625                                        final PsiElement context,
1626                                        final boolean varargs) {
1627     return LambdaUtil.performWithSubstitutedParameterBounds(m1.getTypeParameters(), siteSubstitutor1,
1628                                                             () -> isMoreSpecificInternal(m1, m2, siteSubstitutor1, args, context, varargs));
1629   }
1630
1631   private static boolean isMoreSpecificInternal(PsiMethod m1,
1632                                                 PsiMethod m2,
1633                                                 PsiSubstitutor siteSubstitutor1,
1634                                                 PsiExpression[] args,
1635                                                 PsiElement context,
1636                                                 boolean varargs) {
1637
1638     List<PsiTypeParameter> params = new ArrayList<>();
1639     for (PsiTypeParameter param : PsiUtil.typeParametersIterable(m2)) {
1640       params.add(param);
1641     }
1642
1643     siteSubstitutor1 = getSiteSubstitutor(siteSubstitutor1, params);
1644
1645     final InferenceSession session = new InferenceSession(params.toArray(PsiTypeParameter.EMPTY_ARRAY), siteSubstitutor1, m2.getManager(), context);
1646
1647     final PsiParameter[] parameters1 = m1.getParameterList().getParameters();
1648     final PsiParameter[] parameters2 = m2.getParameterList().getParameters();
1649     if (!varargs) {
1650       LOG.assertTrue(parameters1.length == parameters2.length);
1651     }
1652
1653     final int paramsLength = !varargs ? parameters1.length : Math.max(parameters1.length, parameters2.length) - 1;
1654     for (int i = 0; i < paramsLength; i++) {
1655       PsiType sType = getParameterType(parameters1, i, siteSubstitutor1, false);
1656       PsiType tType = session.substituteWithInferenceVariables(getParameterType(parameters2, i, siteSubstitutor1, varargs));
1657       if (PsiUtil.isRawSubstitutor(m2, siteSubstitutor1)) {
1658         tType = TypeConversionUtil.erasure(tType);
1659       }
1660       if (sType instanceof PsiClassType &&
1661           tType instanceof PsiClassType &&
1662           LambdaUtil.isFunctionalType(sType) && LambdaUtil.isFunctionalType(tType) && !relates(sType, tType)) {
1663         if (!isFunctionalTypeMoreSpecific(sType, tType, session, args[i])) {
1664           return false;
1665         }
1666       } else {
1667         if (session.isProperType(tType)) {
1668           if (!TypeConversionUtil.isAssignable(tType, sType)) {
1669             return false;
1670           }
1671         }
1672         session.addConstraint(new StrictSubtypingConstraint(tType, sType));
1673       }
1674     }
1675
1676     if (varargs) {
1677       PsiType sType = getParameterType(parameters1, paramsLength, siteSubstitutor1, true);
1678       PsiType tType = session.substituteWithInferenceVariables(getParameterType(parameters2, paramsLength, siteSubstitutor1, true));
1679       session.addConstraint(new StrictSubtypingConstraint(tType, sType));
1680     }
1681
1682     return session.repeatInferencePhases();
1683   }
1684
1685   private static PsiSubstitutor getSiteSubstitutor(PsiSubstitutor siteSubstitutor1, List<PsiTypeParameter> params) {
1686     PsiSubstitutor subst = PsiSubstitutor.EMPTY;
1687     for (PsiTypeParameter param : params) {
1688       subst = subst.put(param, siteSubstitutor1.substitute(param));
1689     }
1690     return subst;
1691   }
1692
1693   /**
1694    * 15.12.2.5 Choosing the Most Specific Method
1695    * "a functional interface type S is more specific than a functional interface type T for an expression exp" part
1696    */
1697   public static boolean isFunctionalTypeMoreSpecificOnExpression(PsiType sType,
1698                                                                  PsiType tType,
1699                                                                  PsiExpression arg) {
1700     return isFunctionalTypeMoreSpecific(sType, tType, null, arg);
1701   }
1702
1703   private static boolean isFunctionalTypeMoreSpecific(PsiType sType,
1704                                                       PsiType tType,
1705                                                       @Nullable InferenceSession session, 
1706                                                       PsiExpression... args) {
1707     final PsiType capturedSType = sType;//todo capture of Si session != null && sType != null ? PsiUtil.captureToplevelWildcards(sType, session.myContext) : sType;
1708     final PsiClassType.ClassResolveResult sResult = PsiUtil.resolveGenericsClassInType(capturedSType);
1709     final PsiMethod sInterfaceMethod = LambdaUtil.getFunctionalInterfaceMethod(sResult);
1710     LOG.assertTrue(sInterfaceMethod != null);
1711     final PsiSubstitutor sSubstitutor = LambdaUtil.getSubstitutor(sInterfaceMethod, sResult);
1712
1713     final PsiClassType.ClassResolveResult tResult = PsiUtil.resolveGenericsClassInType(tType);
1714     final PsiMethod tInterfaceMethod = LambdaUtil.getFunctionalInterfaceMethod(tResult);
1715     LOG.assertTrue(tInterfaceMethod != null);
1716     final PsiSubstitutor tSubstitutor = LambdaUtil.getSubstitutor(tInterfaceMethod, tResult);
1717
1718     for (PsiExpression arg : args) {
1719       if (!argConstraints(arg, session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor)) {
1720         return false;
1721       }
1722     }
1723     return true;
1724   }
1725
1726   private static boolean argConstraints(PsiExpression arg,
1727                                         @Nullable InferenceSession session,
1728                                         PsiMethod sInterfaceMethod,
1729                                         PsiSubstitutor sSubstitutor,
1730                                         PsiMethod tInterfaceMethod,
1731                                         PsiSubstitutor tSubstitutor) {
1732     if (arg instanceof PsiLambdaExpression && ((PsiLambdaExpression)arg).hasFormalParameterTypes()) {
1733       final PsiType sReturnType = sSubstitutor.substitute(sInterfaceMethod.getReturnType());
1734       final PsiType tReturnType = tSubstitutor.substitute(tInterfaceMethod.getReturnType());
1735
1736       if (PsiType.VOID.equals(tReturnType)) {
1737         return true;
1738       }
1739
1740       final List<PsiExpression> returnExpressions = LambdaUtil.getReturnExpressions((PsiLambdaExpression)arg);
1741
1742       if (sReturnType instanceof PsiClassType && tReturnType instanceof PsiClassType &&
1743           LambdaUtil.isFunctionalType(sReturnType) && LambdaUtil.isFunctionalType(tReturnType) &&
1744           !TypeConversionUtil.isAssignable(TypeConversionUtil.erasure(sReturnType), TypeConversionUtil.erasure(tReturnType)) &&
1745           !TypeConversionUtil.isAssignable(TypeConversionUtil.erasure(tReturnType), TypeConversionUtil.erasure(sReturnType))) {
1746
1747         //Otherwise, if R1 and R2 are functional interface types, and neither interface is a subinterface of the other, 
1748         //then these rules are applied recursively to R1 and R2, for each result expression in expi.
1749         if (!isFunctionalTypeMoreSpecific(sReturnType, tReturnType, session, returnExpressions.toArray(PsiExpression.EMPTY_ARRAY))) {
1750           return false;
1751         }
1752       } else {
1753         final boolean sPrimitive = sReturnType instanceof PsiPrimitiveType && !PsiType.VOID.equals(sReturnType);
1754         final boolean tPrimitive = tReturnType instanceof PsiPrimitiveType && !PsiType.VOID.equals(tReturnType);
1755         if (sPrimitive ^ tPrimitive) {
1756           for (PsiExpression returnExpression : returnExpressions) {
1757             if (!PsiPolyExpressionUtil.isPolyExpression(returnExpression)) {
1758               final PsiType returnExpressionType = returnExpression.getType();
1759               if (sPrimitive) {
1760                 if (!(returnExpressionType instanceof PsiPrimitiveType)) {
1761                   return false;
1762                 }
1763               } else {
1764                 if (!(returnExpressionType instanceof PsiClassType)) {
1765                   return false;
1766                 }
1767               }
1768             }
1769             else if (sPrimitive) {
1770               return false;
1771             }
1772           }
1773           return true;
1774         }
1775         if (session != null) {
1776           session.addConstraint(new StrictSubtypingConstraint(tReturnType, sReturnType));
1777           return true;
1778         } else {
1779           return sReturnType != null && tReturnType != null && TypeConversionUtil.isAssignable(tReturnType, sReturnType); 
1780         }
1781       }
1782     }
1783
1784     if (arg instanceof PsiMethodReferenceExpression && ((PsiMethodReferenceExpression)arg).isExact()) {
1785       final PsiParameter[] sParameters = sInterfaceMethod.getParameterList().getParameters();
1786       final PsiParameter[] tParameters = tInterfaceMethod.getParameterList().getParameters();
1787       LOG.assertTrue(sParameters.length == tParameters.length, 
1788                      "s: " + sInterfaceMethod.getParameterList().getText() + "; t: " + tInterfaceMethod.getParameterList().getText());
1789       for (int i = 0; i < tParameters.length; i++) {
1790         final PsiType tSubstituted = tSubstitutor.substitute(tParameters[i].getType());
1791         final PsiType sSubstituted = sSubstitutor.substitute(sParameters[i].getType());
1792         if (session != null) {
1793           session.addConstraint(new TypeEqualityConstraint(tSubstituted, sSubstituted));
1794         }
1795         else {
1796           if (!Comparing.equal(tSubstituted, sSubstituted)) {
1797             return false;
1798           }
1799         }
1800       }
1801       final PsiType sReturnType = sSubstitutor.substitute(sInterfaceMethod.getReturnType());
1802       final PsiType tReturnType = tSubstitutor.substitute(tInterfaceMethod.getReturnType());
1803       if (PsiType.VOID.equals(tReturnType)) {
1804         return true;
1805       }
1806
1807       final boolean sPrimitive = sReturnType instanceof PsiPrimitiveType && !PsiType.VOID.equals(sReturnType);
1808       final boolean tPrimitive = tReturnType instanceof PsiPrimitiveType && !PsiType.VOID.equals(tReturnType);
1809
1810       if (sPrimitive ^ tPrimitive) {
1811         final PsiMember member = ((PsiMethodReferenceExpression)arg).getPotentiallyApplicableMember();
1812         LOG.assertTrue(member != null, arg);
1813         if (member instanceof PsiMethod) {
1814           final PsiType methodReturnType = ((PsiMethod)member).getReturnType();
1815           if (sPrimitive && methodReturnType instanceof PsiPrimitiveType && !PsiType.VOID.equals(methodReturnType) ||
1816               tPrimitive && methodReturnType instanceof PsiClassType) {
1817             return true;
1818           }
1819         }
1820         return false;
1821       }
1822
1823       if (session != null) {
1824         session.addConstraint(new StrictSubtypingConstraint(tReturnType, sReturnType));
1825         return true;
1826       } else {
1827         return sReturnType != null && tReturnType != null && TypeConversionUtil.isAssignable(tReturnType, sReturnType);
1828       }
1829     }
1830
1831     if (arg instanceof PsiParenthesizedExpression) {
1832       return argConstraints(((PsiParenthesizedExpression)arg).getExpression(), session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor);
1833     }
1834
1835     if (arg instanceof PsiConditionalExpression) {
1836       final PsiExpression thenExpression = ((PsiConditionalExpression)arg).getThenExpression();
1837       final PsiExpression elseExpression = ((PsiConditionalExpression)arg).getElseExpression();
1838       return argConstraints(thenExpression, session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor) &&
1839              argConstraints(elseExpression, session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor);
1840     }
1841
1842     if (arg instanceof PsiSwitchExpression) {
1843       return PsiUtil.getSwitchResultExpressions((PsiSwitchExpression)arg).stream()
1844         .allMatch(resultExpression -> argConstraints(resultExpression, session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor));
1845     }
1846     return false;
1847   }
1848
1849   /**
1850    *  if Si is a functional interface type and Ti is a parameterization of functional interface, I, and none of the following is true:
1851
1852    *  Si is a superinterface of I, or a parameterization of a superinterface of I.
1853    *  Si is subinterface of I, or a parameterization of a subinterface of I.
1854    *  Si is an intersection type and each element of the intersection is a superinterface of I, or a parameterization of a superinterface of I.
1855    *  Si is an intersection type and some element of the intersection is a subinterface of I, or a parameterization of a subinterface of I.
1856    */
1857   private static boolean relates(PsiType sType, PsiType tType) {
1858     final PsiType erasedType = TypeConversionUtil.erasure(tType);
1859     LOG.assertTrue(erasedType != null);  
1860     if (sType instanceof PsiIntersectionType) {
1861       boolean superRelation = true;
1862       boolean subRelation = false;
1863       for (PsiType sConjunct : ((PsiIntersectionType)sType).getConjuncts()) {
1864         final PsiType sConjunctErasure = TypeConversionUtil.erasure(sConjunct);
1865         if (sConjunctErasure != null) {
1866           superRelation &= TypeConversionUtil.isAssignable(sConjunctErasure, erasedType);
1867           subRelation |= TypeConversionUtil.isAssignable(erasedType, sConjunctErasure);
1868         }
1869       }
1870       return superRelation || subRelation;
1871     }
1872     if (sType instanceof PsiClassType) {
1873       final PsiType sTypeErasure = TypeConversionUtil.erasure(sType);
1874       if (sTypeErasure != null) {
1875         return TypeConversionUtil.isAssignable(sTypeErasure, erasedType) || TypeConversionUtil.isAssignable(erasedType, sTypeErasure);
1876       }
1877     }
1878     return false;
1879   }
1880
1881   void collectCaptureDependencies(InferenceVariable inferenceVariable, Set<? super InferenceVariable> dependencies) {
1882     myIncorporationPhase.collectCaptureDependencies(inferenceVariable, dependencies);
1883   }
1884
1885   boolean hasCapture(InferenceVariable inferenceVariable) {
1886     return myIncorporationPhase.hasCaptureConstraints(Collections.singletonList(inferenceVariable));
1887   }
1888
1889   public PsiElement getContext() {
1890     return myContext;
1891   }
1892
1893   public final void propagateVariables(@NotNull InferenceSession from) {
1894     myInferenceVariables.addAll(from.getInferenceVariables());
1895     myRestoreNameSubstitution = myRestoreNameSubstitution.putAll(from.getRestoreNameSubstitution());
1896   }
1897
1898   public PsiType substituteWithInferenceVariables(@Nullable PsiType type) {
1899     return myInferenceSubstitution.substitute(type);
1900   }
1901
1902   public PsiSubstitutor getInferenceSubstitution() {
1903     return myInferenceSubstitution;
1904   }
1905
1906   public PsiSubstitutor getRestoreNameSubstitution() {
1907     return myRestoreNameSubstitution;
1908   }
1909
1910   public InferenceSessionContainer getInferenceSessionContainer() {
1911     return myInferenceSessionContainer;
1912   }
1913
1914   public PsiType startWithFreshVars(PsiType type) {
1915     PsiSubstitutor s = PsiSubstitutor.EMPTY;
1916     for (InferenceVariable variable : myInferenceVariables) {
1917       s = s.put(variable, JavaPsiFacade.getElementFactory(myManager.getProject()).createType(variable.getParameter()));
1918     }
1919     return s.substitute(type);
1920   }
1921
1922   public static PsiClass findParameterizationOfTheSameGenericClass(List<? extends PsiType> upperBounds,
1923                                                                    Processor<? super Pair<PsiType, PsiType>> processor) {
1924     for (int i = 0; i < upperBounds.size(); i++) {
1925       final PsiType sBound = upperBounds.get(i);
1926       final PsiClass sClass = PsiUtil.resolveClassInClassTypeOnly(sBound);
1927       if (sClass == null) continue;
1928       final LinkedHashSet<PsiClass> superClasses = InheritanceUtil.getSuperClasses(sClass);
1929       superClasses.add(sClass);
1930       for (int j = i + 1; j < upperBounds.size(); j++) {
1931         final PsiType tBound = upperBounds.get(j);
1932         final PsiClass tClass = PsiUtil.resolveClassInClassTypeOnly(tBound);
1933         if (tClass != null) {
1934
1935           final LinkedHashSet<PsiClass> tSupers = new LinkedHashSet<>();
1936           tSupers.add(tClass);
1937           tSupers.addAll(InheritanceUtil.getSuperClasses(tClass));
1938           tSupers.retainAll(superClasses);
1939
1940           for (PsiClass gClass : tSupers) {
1941             final PsiSubstitutor sSubstitutor = TypeConversionUtil.getSuperClassSubstitutor(gClass, (PsiClassType)sBound);
1942             final PsiSubstitutor tSubstitutor = TypeConversionUtil.getSuperClassSubstitutor(gClass, (PsiClassType)tBound);
1943             boolean found = false;
1944             for (PsiTypeParameter typeParameter : gClass.getTypeParameters()) {
1945               final PsiType sType = sSubstitutor.substituteWithBoundsPromotion(typeParameter);
1946               final PsiType tType = tSubstitutor.substituteWithBoundsPromotion(typeParameter);
1947               final Pair<PsiType, PsiType> typePair = Pair.create(sType, tType);
1948               if (!processor.process(typePair)) {
1949                 found = true;
1950               }
1951             }
1952             if (found) return gClass;
1953           }
1954         }
1955       }
1956     }
1957     return null;
1958   }
1959
1960   public List<String> getIncompatibleErrorMessages() {
1961     return myErrorMessages;
1962   }
1963
1964   public boolean isErased() {
1965     return myErased;
1966   }
1967 }