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