new inference: collect additional constraints from lambda return expressions when...
[idea/community.git] / java / java-psi-impl / src / com / intellij / psi / impl / source / resolve / graphInference / InferenceSession.java
1 /*
2  * Copyright 2000-2015 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.psi.impl.source.resolve.graphInference;
17
18 import com.intellij.ide.highlighter.JavaFileType;
19 import com.intellij.openapi.diagnostic.Logger;
20 import com.intellij.openapi.util.Comparing;
21 import com.intellij.openapi.util.Computable;
22 import com.intellij.openapi.util.Key;
23 import com.intellij.openapi.util.Pair;
24 import com.intellij.openapi.util.text.StringUtil;
25 import com.intellij.psi.*;
26 import com.intellij.psi.impl.PsiImplUtil;
27 import com.intellij.psi.impl.source.resolve.graphInference.constraints.*;
28 import com.intellij.psi.infos.MethodCandidateInfo;
29 import com.intellij.psi.search.GlobalSearchScope;
30 import com.intellij.psi.util.*;
31 import com.intellij.util.ArrayUtilRt;
32 import com.intellij.util.Function;
33 import com.intellij.util.Processor;
34 import com.intellij.util.containers.ContainerUtil;
35 import org.jetbrains.annotations.NotNull;
36 import org.jetbrains.annotations.Nullable;
37
38 import java.util.*;
39
40 /**
41  * User: anna
42  */
43 public class InferenceSession {
44   private static final Logger LOG = Logger.getInstance("#" + InferenceSession.class.getName());
45   public static final Key<PsiType> LOWER_BOUND = Key.create("LowBound");
46   private static final Key<PsiElement> ORIGINAL_CONTEXT = Key.create("ORIGINAL_CONTEXT");
47   private static final Key<Boolean> ERASED = Key.create("UNCHECKED_CONVERSION");
48   private static final Function<Pair<PsiType, PsiType>, PsiType> UPPER_BOUND_FUNCTION = new Function<Pair<PsiType, PsiType>, PsiType>() {
49     @Override
50     public PsiType fun(Pair<PsiType, PsiType> pair) {
51       if (pair.first instanceof PsiArrayType && TypesDistinctProver.proveArrayTypeDistinct((PsiArrayType)pair.first, pair.second)) {
52         return null;
53       }
54       if (pair.second instanceof PsiArrayType && TypesDistinctProver.proveArrayTypeDistinct((PsiArrayType)pair.second, pair.first)) {
55         return null;
56       }
57       return GenericsUtil.getGreatestLowerBound(pair.first, pair.second);
58     }
59   };
60
61   private static final Key<Map<PsiTypeParameter, String>> INFERENCE_FAILURE_MESSAGE = Key.create("FAILURE_MESSAGE");
62   private static final String EQUALITY_CONSTRAINTS_PRESENTATION = "equality constraints";
63   private static final String UPPER_BOUNDS_PRESENTATION = "upper bounds";
64   private static final String LOWER_BOUNDS_PRESENTATION = "lower bounds";
65
66   private final Set<InferenceVariable> myInferenceVariables = new LinkedHashSet<InferenceVariable>();
67   private final List<ConstraintFormula> myConstraints = new ArrayList<ConstraintFormula>();
68   private final Set<ConstraintFormula> myConstraintsCopy = new HashSet<ConstraintFormula>();
69
70   private PsiSubstitutor mySiteSubstitutor;
71   private final PsiManager myManager;
72   private int myConstraintIdx = 0;
73   
74   private boolean myErased = false;
75
76   private final InferenceIncorporationPhase myIncorporationPhase = new InferenceIncorporationPhase(this);
77
78   private final PsiElement myContext;
79
80   private PsiSubstitutor myInferenceSubstitution = PsiSubstitutor.EMPTY;
81   private final Map<PsiElement, InferenceSession> myNestedSessions = new HashMap<PsiElement, InferenceSession>();
82   public void registerNestedSession(InferenceSession session) {
83     propagateVariables(session.getInferenceVariables());
84     myNestedSessions.put(session.getContext(), session);
85     myNestedSessions.putAll(session.myNestedSessions);
86   }
87
88   public InferenceSession(PsiTypeParameter[] typeParams,
89                           PsiType[] leftTypes, 
90                           PsiType[] rightTypes,
91                           PsiSubstitutor siteSubstitutor,
92                           PsiManager manager,
93                           PsiElement context) {
94     myManager = manager;
95     mySiteSubstitutor = siteSubstitutor;
96     myContext = context;
97
98     initBounds(typeParams);
99
100     LOG.assertTrue(leftTypes.length == rightTypes.length);
101     for (int i = 0; i < leftTypes.length; i++) {
102       final PsiType rightType = mySiteSubstitutor.substitute(rightTypes[i]);
103       if (rightType != null && leftTypes[i] != null) {
104         addConstraint(new TypeCompatibilityConstraint(substituteWithInferenceVariables(leftTypes[i]), substituteWithInferenceVariables(rightType)));
105       }
106     }
107   }
108   
109   public InferenceSession(PsiTypeParameter[] typeParams,
110                           PsiSubstitutor siteSubstitutor,
111                           PsiManager manager,
112                           PsiElement context) {
113     myManager = manager;
114     mySiteSubstitutor = siteSubstitutor;
115     myContext = context;
116
117     initBounds(typeParams);
118   }
119
120   public void initExpressionConstraints(PsiParameter[] parameters, PsiExpression[] args, PsiElement parent, PsiMethod method) {
121     final MethodCandidateInfo.CurrentCandidateProperties currentProperties = getCurrentProperties(parent);
122     initExpressionConstraints(parameters, args, parent, method, currentProperties != null && currentProperties.isVarargs());
123   }
124
125   public void initExpressionConstraints(PsiParameter[] parameters,
126                                         PsiExpression[] args,
127                                         PsiElement parent,
128                                         PsiMethod method,
129                                         boolean varargs) {
130     final MethodCandidateInfo.CurrentCandidateProperties currentProperties = getCurrentProperties(parent);
131     if (method == null) {
132       if (currentProperties != null) {
133         method = currentProperties.getMethod();
134       }
135     }
136     if (method != null) {
137       initThrowsConstraints(method);
138     }
139     if (parameters.length > 0) {
140       for (int i = 0; i < args.length; i++) {
141         if (args[i] != null && isPertinentToApplicability(args[i], method)) {
142           PsiType parameterType = getParameterType(parameters, i, mySiteSubstitutor, varargs);
143           addConstraint(new ExpressionCompatibilityConstraint(args[i], substituteWithInferenceVariables(parameterType)));
144         }
145       }
146     }
147   }
148
149   public void initThrowsConstraints(PsiMethod method) {
150     for (PsiClassType thrownType : method.getThrowsList().getReferencedTypes()) {
151       final InferenceVariable variable = getInferenceVariable(substituteWithInferenceVariables(thrownType));
152       if (variable != null) {
153         variable.setThrownBound();
154       }
155     }
156   }
157
158   private static MethodCandidateInfo.CurrentCandidateProperties getCurrentProperties(PsiElement parent) {
159     if (parent instanceof PsiCallExpression) {
160       return MethodCandidateInfo.getCurrentMethod(((PsiCallExpression)parent).getArgumentList());
161     }
162     return null;
163   }
164
165   /**
166    * Definition from 15.12.2.2 Phase 1: Identify Matching Arity Methods Applicable by Subtyping Strict Invocation
167    * An argument expression is considered pertinent to applicability for a potentially-applicable method m unless it has one of the following forms:
168
169    1)  An implicitly-typed lambda expression (15.27.1).
170    2) An inexact method reference (15.13.1).
171    3) If m is a generic method and the method invocation does not provide explicit type arguments, an explicitly-typed lambda expression or 
172       an exact method reference for which the corresponding target type (as derived from the signature of m) is a type parameter of m.
173    4) An explicitly-typed lambda expression whose body is an expression that is not pertinent to applicability.
174    5) An explicitly-typed lambda expression whose body is a block, where at least one result expression is not pertinent to applicability.
175    6) A parenthesized expression (15.8.5) whose contained expression is not pertinent to applicability.
176    7) A conditional expression (15.25) whose second or third operand is not pertinent to applicability. 
177   */
178   public static boolean isPertinentToApplicability(PsiExpression expr, PsiMethod method) {
179     return isPertinentToApplicability(expr, method, null);
180   }
181
182   private static boolean isPertinentToApplicability(PsiExpression expr, PsiMethod method, PsiType expectedReturnType) {
183     if (expr instanceof PsiLambdaExpression && ((PsiLambdaExpression)expr).hasFormalParameterTypes() ||
184         expr instanceof PsiMethodReferenceExpression && ((PsiMethodReferenceExpression)expr).isExact()) {
185       if (method != null && method.getTypeParameters().length > 0) {
186         final PsiElement parent = PsiUtil.skipParenthesizedExprUp(expr.getParent());
187         PsiType paramType = null;
188         if (parent instanceof PsiExpressionList) {
189           final PsiElement gParent = parent.getParent();
190           if (gParent instanceof PsiCallExpression && ((PsiCallExpression)gParent).getTypeArgumentList().getTypeParameterElements().length == 0) {
191             final int idx = LambdaUtil.getLambdaIdx(((PsiExpressionList)parent), expr);
192             final PsiParameter[] parameters = method.getParameterList().getParameters();
193             if (idx > parameters.length - 1) {
194               final PsiType lastParamType = parameters[parameters.length - 1].getType();
195               paramType = parameters[parameters.length - 1].isVarArgs() ? ((PsiEllipsisType)lastParamType).getComponentType() : lastParamType;
196             }
197             else {
198               paramType = parameters[idx].getType();
199             }
200             if (isTypeParameterType(method, paramType)) return false;
201           }
202         }
203         else if (expectedReturnType != null && parent instanceof PsiLambdaExpression) {
204           if (isTypeParameterType(method, expectedReturnType)) return false;
205           paramType = expectedReturnType;
206         }
207
208         if (expr instanceof PsiLambdaExpression) {
209           for (PsiExpression expression : LambdaUtil.getReturnExpressions((PsiLambdaExpression)expr)) {
210             if (!isPertinentToApplicability(expression, method, LambdaUtil.getFunctionalInterfaceReturnType(paramType))) return false;
211           }
212           return true;
213         }
214       }
215     }
216     if (expr instanceof PsiLambdaExpression) {
217       return ((PsiLambdaExpression)expr).hasFormalParameterTypes();
218     }
219     if (expr instanceof PsiMethodReferenceExpression) {
220       return ((PsiMethodReferenceExpression)expr).isExact();
221     }
222     if (expr instanceof PsiParenthesizedExpression) {
223       return isPertinentToApplicability(((PsiParenthesizedExpression)expr).getExpression(), method);
224     }
225     if (expr instanceof PsiConditionalExpression) {
226       final PsiExpression thenExpression = ((PsiConditionalExpression)expr).getThenExpression();
227       if (!isPertinentToApplicability(thenExpression, method)) return false;
228       final PsiExpression elseExpression = ((PsiConditionalExpression)expr).getElseExpression();
229       if (!isPertinentToApplicability(elseExpression, method)) return false;
230     }
231     return true;
232   }
233
234   private static boolean isTypeParameterType(PsiMethod method, PsiType paramType) {
235     final PsiClass psiClass = PsiUtil.resolveClassInType(paramType); //accept ellipsis here
236     if (psiClass instanceof PsiTypeParameter && ((PsiTypeParameter)psiClass).getOwner() == method) return true;
237     return false;
238   }
239
240   private static PsiType getParameterType(PsiParameter[] parameters, int i, @Nullable PsiSubstitutor substitutor, boolean varargs) {
241     if (substitutor == null) return null;
242     
243     final PsiParameter parameter = parameters[i < parameters.length ? i : parameters.length - 1];
244     final PsiType type = parameter.getType();
245     if (!type.isValid()) {
246       PsiUtil.ensureValidType(type, "Invalid type of parameter " + parameter + " of " + parameter.getClass());
247     }
248     
249     PsiType parameterType = substitutor.substitute(type);
250     if (parameterType instanceof PsiEllipsisType && varargs) {
251       parameterType = ((PsiEllipsisType)parameterType).getComponentType();
252     }
253     return parameterType;
254   }
255
256   @NotNull
257   public PsiSubstitutor infer() {
258     return infer(null, null, null);
259   }
260
261   @NotNull
262   public PsiSubstitutor infer(@Nullable PsiParameter[] parameters,
263                               @Nullable PsiExpression[] args,
264                               @Nullable PsiElement parent) {
265     final MethodCandidateInfo.CurrentCandidateProperties properties = getCurrentProperties(parent);
266     if (!repeatInferencePhases(true)) {
267       //inferred result would be checked as candidate won't be applicable
268       return resolveSubset(myInferenceVariables, mySiteSubstitutor);
269     }
270
271     if (properties != null && !properties.isApplicabilityCheck()) {
272       initReturnTypeConstraint(properties.getMethod(), (PsiCallExpression)parent);
273       if (!repeatInferencePhases(true)) {
274         return prepareSubstitution();
275       }
276
277       if (parameters != null && args != null) {
278         final Set<ConstraintFormula> additionalConstraints = new LinkedHashSet<ConstraintFormula>();
279         if (parameters.length > 0) {
280           collectAdditionalConstraints(parameters, args, properties.getMethod(), mySiteSubstitutor, additionalConstraints, properties.isVarargs());
281         }
282
283         if (!additionalConstraints.isEmpty() && !proceedWithAdditionalConstraints(additionalConstraints)) {
284           return prepareSubstitution().putAll(retrieveNonPrimitiveEqualsBounds(myInferenceVariables));
285         }
286       }
287     }
288
289     final PsiSubstitutor substitutor = resolveBounds(myInferenceVariables, PsiSubstitutor.EMPTY);
290     if (substitutor != null) {
291       if (myContext != null) {
292         myContext.putUserData(ERASED, myErased);
293       }
294       final Map<PsiTypeParameter, PsiType> map = substitutor.getSubstitutionMap();
295       for (PsiTypeParameter parameter : map.keySet()) {
296         final PsiType mapping = map.get(parameter);
297         PsiTypeParameter param;
298         if (parameter instanceof InferenceVariable) {
299           ((InferenceVariable)parameter).setInstantiation(mapping);
300           if (((InferenceVariable)parameter).getCallContext() != myContext) {
301             //don't include in result substitutor foreign inference variables
302             continue;
303           }
304           param = ((InferenceVariable)parameter).getParameter();
305         }
306         else {
307           param = parameter;
308         }
309         mySiteSubstitutor = mySiteSubstitutor.put(param, mapping);
310       }
311     } else {
312       return prepareSubstitution();
313     }
314
315     return prepareSubstitution();
316   }
317
318   private void collectAdditionalConstraints(PsiParameter[] parameters,
319                                             PsiExpression[] args,
320                                             PsiMethod parentMethod,
321                                             PsiSubstitutor siteSubstitutor,
322                                             Set<ConstraintFormula> additionalConstraints,
323                                             boolean varargs) {
324     for (int i = 0; i < args.length; i++) {
325       final PsiExpression arg = PsiUtil.skipParenthesizedExprDown(args[i]);
326       if (arg != null) {
327         if (MethodCandidateInfo.isOverloadCheck() && arg instanceof PsiLambdaExpression) {
328           for (Object expr : MethodCandidateInfo.ourOverloadGuard.currentStack()) {
329             if (PsiTreeUtil.getParentOfType((PsiElement)expr, PsiLambdaExpression.class) == arg) {
330               return;
331             }
332           }
333         }
334         final InferenceSession nestedCallSession = findNestedCallSession(arg);
335         final PsiType parameterType =
336           nestedCallSession.substituteWithInferenceVariables(getParameterType(parameters, i, siteSubstitutor, varargs));
337         if (!isPertinentToApplicability(arg, parentMethod)) {
338           additionalConstraints.add(new ExpressionCompatibilityConstraint(arg, parameterType));
339         }
340         additionalConstraints.add(new CheckedExceptionCompatibilityConstraint(arg, parameterType));
341         if (arg instanceof PsiCallExpression) {
342           //If the expression is a poly class instance creation expression (15.9) or a poly method invocation expression (15.12), 
343           //the set contains all constraint formulas that would appear in the set C when determining the poly expression's invocation type.
344           final PsiMethod calledMethod = getCalledMethod((PsiCallExpression)arg);
345           if (calledMethod != null && PsiPolyExpressionUtil.isMethodCallPolyExpression(arg, calledMethod)) {
346             collectAdditionalConstraints(additionalConstraints, (PsiCallExpression)arg);
347           }
348         }
349         else if (arg instanceof PsiLambdaExpression && 
350                  isPertinentToApplicability(arg, parentMethod) && 
351                  !isProperType(retrieveNonPrimitiveEqualsBounds(myInferenceVariables).substitute(parameterType))) {
352           collectLambdaReturnExpression(additionalConstraints, (PsiLambdaExpression)arg, parameterType);
353         }
354       }
355     }
356   }
357
358   private static PsiMethod getCalledMethod(PsiCallExpression arg) {
359     final PsiExpressionList argumentList = arg.getArgumentList();
360     if (argumentList == null) {
361       return null;
362     }
363
364     MethodCandidateInfo.CurrentCandidateProperties properties = MethodCandidateInfo.getCurrentMethod(argumentList);
365     if (properties != null) {
366       return properties.getMethod();
367     }
368     final JavaResolveResult resolveResult = getMethodResult(arg);
369     if (resolveResult instanceof MethodCandidateInfo) {
370       return (PsiMethod)resolveResult.getElement();
371     }
372     else {
373       return null;
374     }
375   }
376
377   private void collectLambdaReturnExpression(Set<ConstraintFormula> additionalConstraints,
378                                              PsiLambdaExpression lambdaExpression,
379                                              PsiType parameterType) {
380     final PsiType interfaceReturnType = LambdaUtil.getFunctionalInterfaceReturnType(parameterType);
381     if (interfaceReturnType != null) {
382       final List<PsiExpression> returnExpressions = LambdaUtil.getReturnExpressions(lambdaExpression);
383       for (PsiExpression returnExpression : returnExpressions) {
384         processReturnExpression(additionalConstraints, returnExpression, interfaceReturnType);
385       }
386     }
387   }
388
389   private void processReturnExpression(Set<ConstraintFormula> additionalConstraints,
390                                        PsiExpression returnExpression,
391                                        PsiType functionalType) {
392     if (returnExpression instanceof PsiCallExpression) {
393       final PsiMethod calledMethod = getCalledMethod((PsiCallExpression)returnExpression);
394       if (calledMethod != null && PsiPolyExpressionUtil.isMethodCallPolyExpression(returnExpression, calledMethod)) {
395         collectAdditionalConstraints(additionalConstraints, (PsiCallExpression)returnExpression);
396       }
397     }
398     else if (returnExpression instanceof PsiParenthesizedExpression) {
399       processReturnExpression(additionalConstraints, ((PsiParenthesizedExpression)returnExpression).getExpression(), functionalType);
400     }
401     else if (returnExpression instanceof PsiConditionalExpression) {
402       processReturnExpression(additionalConstraints, ((PsiConditionalExpression)returnExpression).getThenExpression(), functionalType);
403       processReturnExpression(additionalConstraints, ((PsiConditionalExpression)returnExpression).getElseExpression(), functionalType);
404     }
405     else if (returnExpression instanceof PsiLambdaExpression) {
406       collectLambdaReturnExpression(additionalConstraints, (PsiLambdaExpression)returnExpression, functionalType);
407     }
408   }
409
410   private void collectAdditionalConstraints(final Set<ConstraintFormula> additionalConstraints,
411                                             final PsiCallExpression callExpression) {
412     PsiExpressionList argumentList = callExpression.getArgumentList();
413     if (argumentList != null) {
414       final JavaResolveResult result = getMethodResult(callExpression);
415       MethodCandidateInfo.CurrentCandidateProperties properties = MethodCandidateInfo.getCurrentMethod(argumentList);
416       final PsiMethod method = result instanceof MethodCandidateInfo ? ((MethodCandidateInfo)result).getElement() : properties != null ? properties.getMethod() : null;
417       if (method != null) {
418         final PsiExpression[] newArgs = argumentList.getExpressions();
419         final PsiParameter[] newParams = method.getParameterList().getParameters();
420         if (newParams.length > 0) {
421           collectAdditionalConstraints(newParams, newArgs, method, result != null ? ((MethodCandidateInfo)result).getSiteSubstitutor() : properties.getSubstitutor(),
422                                        additionalConstraints, result != null ?  ((MethodCandidateInfo)result).isVarargs() : properties.isVarargs());
423         }
424       }
425     }
426   }
427
428   private static JavaResolveResult getMethodResult(final PsiCallExpression callExpression) {
429     final PsiExpressionList argumentList = callExpression.getArgumentList();
430
431     final PsiLambdaExpression expression = PsiTreeUtil.getParentOfType(argumentList, PsiLambdaExpression.class);
432     final Computable<JavaResolveResult> computableResolve = new Computable<JavaResolveResult>() {
433       @Override
434       public JavaResolveResult compute() {
435         return getResolveResult(callExpression, argumentList);
436       }
437     };
438     MethodCandidateInfo.CurrentCandidateProperties properties = MethodCandidateInfo.getCurrentMethod(argumentList);
439     return properties != null ? null :
440            expression == null || !PsiResolveHelper.ourGraphGuard.currentStack().contains(expression)
441            ? computableResolve.compute()
442            : PsiResolveHelper.ourGraphGuard.doPreventingRecursion(expression, false, computableResolve);
443   }
444
445   public static JavaResolveResult getResolveResult(PsiCallExpression callExpression, PsiExpressionList argumentList) {
446     if (callExpression instanceof PsiNewExpression) {
447       final PsiJavaCodeReferenceElement classReference = ((PsiNewExpression)callExpression).getClassOrAnonymousClassReference();
448       final JavaResolveResult resolveResult = classReference != null ? classReference.advancedResolve(false) : null;
449       final PsiElement psiClass = resolveResult != null ? resolveResult.getElement() : null;
450       if (psiClass instanceof PsiClass) {
451         final JavaPsiFacade facade = JavaPsiFacade.getInstance(callExpression.getProject());
452         final JavaResolveResult constructor = facade.getResolveHelper()
453           .resolveConstructor(facade.getElementFactory().createType((PsiClass)psiClass).rawType(), argumentList, callExpression);
454         return constructor.getElement() == null ? resolveResult : constructor;
455       }
456       else {
457         return JavaResolveResult.EMPTY;
458       }
459     }
460     return callExpression.resolveMethodGenerics();
461   }
462
463   public PsiSubstitutor retrieveNonPrimitiveEqualsBounds(Collection<InferenceVariable> variables) {
464     PsiSubstitutor substitutor = PsiSubstitutor.EMPTY;
465     for (InferenceVariable variable : variables) {
466       final PsiType equalsBound = getEqualsBound(variable, substitutor);
467       if (!(equalsBound instanceof PsiPrimitiveType)) {
468         substitutor = substitutor.put(variable, equalsBound);
469       }
470     }
471     return substitutor;
472   }
473   
474   private PsiSubstitutor prepareSubstitution() {
475     ArrayList<InferenceVariable> allVars = new ArrayList<InferenceVariable>(myInferenceVariables);
476     while (!allVars.isEmpty()) {
477       final List<InferenceVariable> variables = InferenceVariablesOrder.resolveOrder(allVars, this);
478       for (InferenceVariable inferenceVariable : variables) {
479         final PsiTypeParameter typeParameter = inferenceVariable.getParameter();
480         PsiType instantiation = inferenceVariable.getInstantiation();
481         //failed inference
482         if (instantiation == PsiType.NULL) {
483           checkBoundsConsistency(mySiteSubstitutor, inferenceVariable);
484           mySiteSubstitutor = mySiteSubstitutor
485             .put(typeParameter, JavaPsiFacade.getInstance(typeParameter.getProject()).getElementFactory().createType(typeParameter));
486         }
487       }
488       allVars.removeAll(variables);
489     }
490     return mySiteSubstitutor;
491   }
492
493   public void initBounds(PsiTypeParameter... typeParameters) {
494     initBounds(myContext, typeParameters);
495   }
496
497   public InferenceVariable[] initBounds(PsiElement context, PsiTypeParameter... typeParameters) {
498     List<InferenceVariable> result = new ArrayList<InferenceVariable>(typeParameters.length);
499     for (PsiTypeParameter parameter : typeParameters) {
500       InferenceVariable variable = new InferenceVariable(context, parameter);
501       result.add(variable);
502       myInferenceSubstitution = myInferenceSubstitution.put(parameter,
503                                                             JavaPsiFacade.getElementFactory(variable.getProject()).createType(variable));
504     }
505     for (InferenceVariable variable : result) {
506       PsiTypeParameter parameter = variable.getParameter();
507       boolean added = false;
508       final PsiClassType[] extendsListTypes = parameter.getExtendsListTypes();
509       for (PsiType classType : extendsListTypes) {
510         classType = substituteWithInferenceVariables(mySiteSubstitutor.substitute(classType));
511         if (isProperType(classType)) {
512           added = true;
513         }
514         variable.addBound(classType, InferenceBound.UPPER);
515       }
516       if (!added) {
517         variable.addBound(PsiType.getJavaLangObject(parameter.getManager(), parameter.getResolveScope()),
518                           InferenceBound.UPPER);
519       }
520     }
521     myInferenceVariables.addAll(result);
522     return result.toArray(new InferenceVariable[result.size()]);
523   }
524
525   private void initReturnTypeConstraint(PsiMethod method, final PsiCallExpression context) {
526     if (PsiPolyExpressionUtil.isMethodCallPolyExpression(context, method)) {
527       PsiType returnType = method.getReturnType();
528       if (!PsiType.VOID.equals(returnType) && returnType != null) {
529         PsiType targetType = getTargetType(context);
530         if (targetType != null && !PsiType.VOID.equals(targetType)) {
531           registerReturnTypeConstraints(
532             PsiUtil.isRawSubstitutor(method, mySiteSubstitutor) ? returnType : mySiteSubstitutor.substitute(returnType), targetType);
533         }
534       }
535     }
536   }
537
538   public void registerReturnTypeConstraints(PsiType returnType, PsiType targetType) {
539     returnType = substituteWithInferenceVariables(returnType);
540     final InferenceVariable inferenceVariable = shouldResolveAndInstantiate(returnType, targetType);
541     if (inferenceVariable != null) {
542       final PsiSubstitutor substitutor = resolveSubset(Collections.singletonList(inferenceVariable), mySiteSubstitutor);
543       final PsiType substitutedReturnType = substitutor.substitute(inferenceVariable.getParameter());
544       if (substitutedReturnType != null) {
545         addConstraint(new TypeCompatibilityConstraint(targetType, PsiImplUtil.normalizeWildcardTypeByPosition(substitutedReturnType, (PsiExpression)myContext)));
546       }
547     } 
548     else {
549       if (FunctionalInterfaceParameterizationUtil.isWildcardParameterized(returnType)) {
550         final PsiClassType.ClassResolveResult resolveResult = PsiUtil.resolveGenericsClassInType(returnType);
551         final PsiClass psiClass = resolveResult.getElement();
552         if (psiClass != null) {
553           LOG.assertTrue(returnType instanceof PsiClassType);
554           final PsiTypeParameter[] typeParameters = psiClass.getTypeParameters();
555           InferenceVariable[] copy = initBounds(null, typeParameters);
556           final PsiType substitutedCapture = PsiImplUtil.normalizeWildcardTypeByPosition(returnType, (PsiExpression)myContext);
557           myIncorporationPhase.addCapture(copy, (PsiClassType)substituteWithInferenceVariables(returnType));
558           addConstraint(new TypeCompatibilityConstraint(targetType, substitutedCapture));
559         }
560       } else {
561         addConstraint(new TypeCompatibilityConstraint(targetType, myErased ? TypeConversionUtil.erasure(returnType) : returnType));
562       }
563     }
564   }
565
566   private InferenceVariable shouldResolveAndInstantiate(PsiType returnType, PsiType targetType) {
567     final InferenceVariable inferenceVariable = getInferenceVariable(returnType);
568     if (inferenceVariable != null) {
569       if (targetType instanceof PsiPrimitiveType && hasPrimitiveWrapperBound(inferenceVariable)) {
570         return inferenceVariable;
571       }
572       if (targetType instanceof PsiClassType) {
573         if (myErased ||
574             hasUncheckedBounds(inferenceVariable, (PsiClassType)targetType) ||
575             hasWildcardParameterization(inferenceVariable, (PsiClassType)targetType)) {
576           return inferenceVariable;
577         }
578       }
579     }
580     return null;
581   }
582   
583   private static boolean hasPrimitiveWrapperBound(InferenceVariable inferenceVariable) {
584     final InferenceBound[] boundTypes = {InferenceBound.UPPER, InferenceBound.LOWER, InferenceBound.EQ};
585     for (InferenceBound inferenceBound : boundTypes) {
586       final List<PsiType> bounds = inferenceVariable.getBounds(inferenceBound);
587       for (PsiType bound : bounds) {
588         if (PsiPrimitiveType.getUnboxedType(bound) != null) {
589           return true;
590         }
591       }
592     }
593     return false;
594   }
595
596   private static boolean hasUncheckedBounds(InferenceVariable inferenceVariable, PsiClassType targetType) {
597     if (!targetType.isRaw()) {
598       final InferenceBound[] boundTypes = {InferenceBound.EQ, InferenceBound.LOWER};
599       for (InferenceBound inferenceBound : boundTypes) {
600         final List<PsiType> bounds = inferenceVariable.getBounds(inferenceBound);
601         for (PsiType bound : bounds) {
602           if (TypeCompatibilityConstraint.isUncheckedConversion(targetType, bound)) {
603             return true;
604           }
605         }
606       }
607     }
608     return false;
609   }
610
611   /**
612    * T is a reference type, but is not a wildcard-parameterized type, and either 
613    *  i)  B2 contains a bound of one of the forms α=S or S<:α, where S is a wildcard-parameterized type, or 
614    *  ii) B2 contains two bounds of the forms S1 <: α and S2 <: α,
615    *      where S1 and S2 have supertypes that are two different parameterizations of the same generic class or interface. 
616    */
617   private static boolean hasWildcardParameterization(InferenceVariable inferenceVariable, PsiClassType targetType) {
618     if (!FunctionalInterfaceParameterizationUtil.isWildcardParameterized(targetType)) {
619       final List<PsiType> bounds = inferenceVariable.getBounds(InferenceBound.LOWER);
620       final Processor<Pair<PsiType, PsiType>> differentParameterizationProcessor = new Processor<Pair<PsiType, PsiType>>() {
621         @Override
622         public boolean process(Pair<PsiType, PsiType> pair) {
623           return pair.first == null || pair.second == null || !TypesDistinctProver.provablyDistinct(pair.first, pair.second);
624         }
625       };
626       if (findParameterizationOfTheSameGenericClass(bounds, differentParameterizationProcessor) != null) return true;
627       final List<PsiType> eqBounds = inferenceVariable.getBounds(InferenceBound.EQ);
628       final List<PsiType> boundsToCheck = new ArrayList<PsiType>(bounds);
629       boundsToCheck.addAll(eqBounds);
630       for (PsiType lowBound : boundsToCheck) {
631         if (FunctionalInterfaceParameterizationUtil.isWildcardParameterized(lowBound)) {
632           return true;
633         }
634       }
635     }
636     return false;
637   }
638   
639   public static PsiType getTargetType(final PsiExpression context) {
640     PsiType targetType = PsiTypesUtil.getExpectedTypeByParent(context);
641     if (targetType != null) {
642       return targetType;
643     }
644     final PsiElement parent = PsiUtil.skipParenthesizedExprUp(context.getParent());
645     if (parent instanceof PsiExpressionList) {
646       PsiElement gParent = parent.getParent();
647       if (gParent instanceof PsiAnonymousClass) {
648         gParent = gParent.getParent();
649       }
650       if (gParent instanceof PsiCallExpression) {
651         final PsiExpressionList argumentList = ((PsiCallExpression)gParent).getArgumentList();
652         if (argumentList != null) {
653           final MethodCandidateInfo.CurrentCandidateProperties properties = MethodCandidateInfo.getCurrentMethod(argumentList);
654           if (properties != null && properties.isApplicabilityCheck()) {
655             return getTypeByMethod(context, argumentList, properties.getMethod(), properties.isVarargs(), properties.getSubstitutor());
656           }
657           final JavaResolveResult result = properties != null ? properties.getInfo() : ((PsiCallExpression)gParent).resolveMethodGenerics();
658           final boolean varargs = properties != null && properties.isVarargs() || result instanceof MethodCandidateInfo && ((MethodCandidateInfo)result).isVarargs();
659           PsiSubstitutor substitutor = PsiResolveHelper.ourGraphGuard.doPreventingRecursion(context, false,
660                                                                                             new Computable<PsiSubstitutor>() {
661                                                                                               @Override
662                                                                                               public PsiSubstitutor compute() {
663                                                                                                 return result.getSubstitutor();
664                                                                                               }
665                                                                                             }
666           );
667           if (substitutor == null && properties != null) {
668             substitutor = properties.getSubstitutor();
669           }
670           return getTypeByMethod(context, argumentList, result.getElement(), varargs, substitutor);
671         }
672       }
673     } else if (parent instanceof PsiConditionalExpression) {
674       return getTargetType((PsiExpression)parent);
675     }
676     else if (parent instanceof PsiLambdaExpression) {
677       return getTargetTypeByContainingLambda((PsiLambdaExpression)parent);
678     }
679     else if (parent instanceof PsiReturnStatement) {
680       return getTargetTypeByContainingLambda(PsiTreeUtil.getParentOfType(parent, PsiLambdaExpression.class));
681     }
682     return null;
683   }
684
685   private static PsiType getTargetTypeByContainingLambda(PsiLambdaExpression lambdaExpression) {
686     if (lambdaExpression != null) {
687       if (PsiUtil.skipParenthesizedExprUp(lambdaExpression.getParent()) instanceof PsiExpressionList) {
688         final PsiType typeTypeByParentCall = getTargetType(lambdaExpression);
689         return LambdaUtil.getFunctionalInterfaceReturnType(
690           FunctionalInterfaceParameterizationUtil.getGroundTargetType(typeTypeByParentCall, lambdaExpression));
691       }
692       return LambdaUtil.getFunctionalInterfaceReturnType(lambdaExpression.getFunctionalInterfaceType());
693     }
694     return null;
695   }
696
697   private static PsiType getTypeByMethod(PsiExpression context,
698                                          PsiExpressionList argumentList,
699                                          PsiElement parentMethod,
700                                          boolean varargs,
701                                          PsiSubstitutor substitutor) {
702     if (parentMethod instanceof PsiMethod) {
703       final PsiParameter[] parameters = ((PsiMethod)parentMethod).getParameterList().getParameters();
704       if (parameters.length == 0) return null;
705       final PsiExpression[] args = argumentList.getExpressions();
706       if (!((PsiMethod)parentMethod).isVarArgs() && parameters.length != args.length) return null;
707       PsiElement arg = context;
708       while (arg.getParent() instanceof PsiParenthesizedExpression) {
709         arg = arg.getParent();
710       }
711       final int i = ArrayUtilRt.find(args, arg);
712       if (i < 0) return null;
713       final PsiType parameterType = getParameterType(parameters, i, substitutor, varargs);
714       final boolean isRaw = substitutor != null && PsiUtil.isRawSubstitutor((PsiMethod)parentMethod, substitutor);
715       return isRaw ? TypeConversionUtil.erasure(parameterType) : parameterType;
716     }
717     return null;
718   }
719
720   public InferenceVariable getInferenceVariable(PsiType psiType) {
721     final PsiClass psiClass = PsiUtil.resolveClassInClassTypeOnly(psiType);
722     if (psiClass instanceof InferenceVariable) {
723       return (InferenceVariable)psiClass;
724     }
725     return null;
726   }
727
728   public boolean isProperType(@Nullable PsiType type) {
729     return collectDependencies(type, null);
730   }
731
732   public boolean collectDependencies(@Nullable PsiType type,
733                                      @Nullable final Set<InferenceVariable> dependencies) {
734     if (type == null) return true;
735     final Boolean isProper = type.accept(new PsiTypeVisitor<Boolean>() {
736       @Nullable
737       @Override
738       public Boolean visitType(PsiType type) {
739         return true;
740       }
741
742       @Nullable
743       @Override
744       public Boolean visitArrayType(PsiArrayType arrayType) {
745         return arrayType.getComponentType().accept(this);
746       }
747
748       @Nullable
749       @Override
750       public Boolean visitWildcardType(PsiWildcardType wildcardType) {
751         final PsiType bound = wildcardType.getBound();
752         if (bound == null) return true;
753         return bound.accept(this);
754       }
755
756       @Nullable
757       @Override
758       public Boolean visitClassType(PsiClassType classType) {
759         final InferenceVariable inferenceVariable = getInferenceVariable(classType);
760         if (inferenceVariable != null) {
761           if (dependencies != null) {
762             dependencies.add(inferenceVariable);
763             return true;
764           }
765           return false;
766         }
767         for (PsiType psiType : classType.getParameters()) {
768           if (!psiType.accept(this)) return false;
769         }
770         return true;
771       }
772     });
773     return dependencies != null ? !dependencies.isEmpty() : isProper;
774   }
775
776   public boolean repeatInferencePhases(boolean incorporate) {
777     do {
778       if (!reduceConstraints()) {
779         //inference error occurred
780         return false;
781       }
782
783       if (incorporate) {
784         if (!myIncorporationPhase.incorporate()) {
785           return false;
786         }
787       }
788     } while (incorporate && !myIncorporationPhase.isFullyIncorporated() || myConstraintIdx < myConstraints.size());
789
790     return true;
791   }
792
793   private boolean reduceConstraints() {
794     List<ConstraintFormula> newConstraints = new ArrayList<ConstraintFormula>();
795     for (int i = myConstraintIdx; i < myConstraints.size(); i++) {
796       ConstraintFormula constraint = myConstraints.get(i);
797       if (!constraint.reduce(this, newConstraints)) {
798         return false;
799       }
800     }
801     myConstraintIdx = myConstraints.size();
802     for (ConstraintFormula constraint : newConstraints) {
803       addConstraint(constraint);
804     }
805     return true;
806   }
807
808   private boolean isThrowable(List<PsiType> upperBounds) {
809     boolean commonThrowable = false;
810     for (PsiType upperBound : upperBounds) {
811       if (upperBound.equalsToText(CommonClassNames.JAVA_LANG_OBJECT) || !isProperType(upperBound)) continue;
812       if (upperBound.equalsToText(CommonClassNames.JAVA_LANG_EXCEPTION) ||
813           upperBound.equalsToText(CommonClassNames.JAVA_LANG_THROWABLE)) {
814         commonThrowable = true;
815       } else {
816         return false;
817       }
818     }
819     return commonThrowable;
820   }
821
822   private PsiType substituteNonProperBound(PsiType bound, PsiSubstitutor substitutor) {
823     final HashSet<InferenceVariable> dependencies = new LinkedHashSet<InferenceVariable>();
824     if (!collectDependencies(bound, dependencies)) {
825       return bound;
826     }
827     for (InferenceVariable dependency : dependencies) {
828       PsiType instantiation = dependency.getInstantiation();
829       if (instantiation != PsiType.NULL) {
830         substitutor = substitutor.put(dependency, instantiation);
831       }
832     }
833     return substitutor.substitute(bound);
834   }
835
836   private  boolean hasBoundProblems(final List<InferenceVariable> typeParams,
837                                     final PsiSubstitutor substitutor) {
838     for (InferenceVariable typeParameter : typeParams) {
839       final List<PsiType> extendsTypes = typeParameter.getBounds(InferenceBound.UPPER);
840       final PsiType[] bounds = extendsTypes.toArray(new PsiType[extendsTypes.size()]);
841       if (GenericsUtil.findTypeParameterBoundError(typeParameter, bounds, substitutor, myContext, true) != null) {
842         return true;
843       }
844     }
845     return false;
846   }
847
848   private PsiSubstitutor resolveBounds(final Collection<InferenceVariable> inferenceVariables,
849                                        PsiSubstitutor substitutor) {
850     final Collection<InferenceVariable> allVars = new ArrayList<InferenceVariable>(inferenceVariables);
851     while (!allVars.isEmpty()) {
852       final List<InferenceVariable> vars = InferenceVariablesOrder.resolveOrder(allVars, this);
853       if (!myIncorporationPhase.hasCaptureConstraints(vars)) {
854         PsiSubstitutor firstSubstitutor = resolveSubset(vars, substitutor);
855         if (firstSubstitutor != null && hasBoundProblems(vars, firstSubstitutor)) {
856           firstSubstitutor = null;
857         }
858         if (firstSubstitutor != null) {
859           substitutor = firstSubstitutor;
860           allVars.removeAll(vars);
861           continue;
862         }
863       }
864
865       final PsiElementFactory elementFactory = JavaPsiFacade.getElementFactory(getManager().getProject());
866       final PsiTypeParameter[] freshParameters = createFreshVariables(vars, substitutor);
867       for (int i = 0; i < freshParameters.length; i++) {
868         PsiTypeParameter parameter = freshParameters[i];
869         final InferenceVariable var = vars.get(i);
870         final PsiType lub = getLowerBound(var, substitutor);
871         if (lub != PsiType.NULL) {
872           for (PsiClassType upperBoundType : parameter.getExtendsListTypes()) {
873             if (!TypeConversionUtil.isAssignable(upperBoundType, lub)) {
874               return null;
875             }
876           }
877           parameter.putUserData(LOWER_BOUND, lub);
878         }
879         var.addBound(elementFactory.createType(parameter), InferenceBound.EQ);
880       }
881       myIncorporationPhase.forgetCaptures(vars);
882       if (!repeatInferencePhases(true)) {
883         return null;
884       }
885     }
886     return substitutor;
887   }
888
889   private PsiTypeParameter[] createFreshVariables(final List<InferenceVariable> vars, final PsiSubstitutor siteSubstitutor) {
890     final PsiElementFactory elementFactory = JavaPsiFacade.getElementFactory(getManager().getProject());
891
892     PsiSubstitutor substitutor = PsiSubstitutor.EMPTY;
893     final PsiTypeParameter[] yVars = new PsiTypeParameter[vars.size()];
894     for (int i = 0; i < vars.size(); i++) {
895       InferenceVariable var = vars.get(i);
896       final PsiTypeParameter parameter = var.getParameter();
897       yVars[i] = elementFactory.createTypeParameterFromText(getFreshVariableName(var), parameter);
898       substitutor = substitutor.put(var, elementFactory.createType(yVars[i]));
899     }
900
901
902     final PsiSubstitutor ySubstitutor = substitutor;
903     final String classText = "class I<" + StringUtil.join(vars, new Function<InferenceVariable, String>() {
904       @Override
905       public String fun(InferenceVariable variable) {
906         final PsiType glb = composeBound(variable, InferenceBound.UPPER, UPPER_BOUND_FUNCTION, ySubstitutor.putAll(siteSubstitutor), true);
907         return getFreshVariableName(variable) + " extends " + glb.getInternalCanonicalText();
908       }
909     }, ", ") + ">{}";
910
911     final PsiFile file =
912       PsiFileFactory.getInstance(getManager().getProject()).createFileFromText("inference_dummy.java", JavaFileType.INSTANCE, classText);
913     LOG.assertTrue(file instanceof PsiJavaFile, classText);
914     final PsiClass[] classes = ((PsiJavaFile)file).getClasses();
915     LOG.assertTrue(classes.length == 1, classText);
916     final PsiTypeParameter[] parameters = classes[0].getTypeParameters();
917     for (PsiTypeParameter parameter : parameters) {
918       parameter.putUserData(ORIGINAL_CONTEXT, myContext);
919     }
920     return parameters;
921   }
922
923   private static String getFreshVariableName(InferenceVariable var) {
924     return var.getName();
925   }
926
927   private PsiSubstitutor resolveSubset(Collection<InferenceVariable> vars, PsiSubstitutor substitutor) {
928     for (InferenceVariable var : vars) {
929       LOG.assertTrue(var.getInstantiation() == PsiType.NULL);
930       final PsiType type = checkBoundsConsistency(substitutor, var);
931       if (type != PsiType.NULL) {
932         substitutor = substitutor.put(var, type);
933       }
934     }
935
936     return substitutor;
937   }
938
939   private PsiType checkBoundsConsistency(PsiSubstitutor substitutor, InferenceVariable var) {
940     final PsiType eqBound = getEqualsBound(var, substitutor);
941     if (eqBound != PsiType.NULL && eqBound instanceof PsiPrimitiveType) return PsiType.NULL;
942     final PsiType lowerBound = getLowerBound(var, substitutor);
943     final PsiType upperBound = getUpperBound(var, substitutor);
944     PsiType type;
945     if (eqBound != PsiType.NULL && (myErased || eqBound != null)) {
946       if (lowerBound != PsiType.NULL && !TypeConversionUtil.isAssignable(eqBound, lowerBound)) {
947         registerIncompatibleErrorMessage(
948           incompatibleBoundsMessage(var, substitutor, InferenceBound.EQ, EQUALITY_CONSTRAINTS_PRESENTATION, InferenceBound.LOWER, LOWER_BOUNDS_PRESENTATION),
949           var.getParameter());
950         return PsiType.NULL;
951       } else {
952         type = eqBound;
953       }
954     }
955     else {
956       type = lowerBound;
957     }
958
959     if (type == PsiType.NULL) {
960       if (var.isThrownBound() && isThrowable(var.getBounds(InferenceBound.UPPER))) {
961         type =  PsiType.getJavaLangRuntimeException(myManager, GlobalSearchScope.allScope(myManager.getProject()));
962       }
963       else {
964         type = myErased ? null : upperBound;
965       }
966     }
967     else {
968       for (PsiType upperType : var.getBounds(InferenceBound.UPPER)) {
969         if (isProperType(upperType) ) {
970           String incompatibleBoundsMessage = null;
971           if (type != lowerBound && !TypeConversionUtil.isAssignable(substitutor.substitute(upperType), type)) {
972             incompatibleBoundsMessage = incompatibleBoundsMessage(var, substitutor, InferenceBound.EQ, EQUALITY_CONSTRAINTS_PRESENTATION, InferenceBound.UPPER, UPPER_BOUNDS_PRESENTATION);
973           }
974           else if (type == lowerBound && !TypeConversionUtil.isAssignable(substitutor.substitute(upperType), lowerBound)) {
975             incompatibleBoundsMessage = incompatibleBoundsMessage(var, substitutor, InferenceBound.LOWER, LOWER_BOUNDS_PRESENTATION, InferenceBound.UPPER, UPPER_BOUNDS_PRESENTATION);
976           }
977           if (incompatibleBoundsMessage != null) {
978             registerIncompatibleErrorMessage(incompatibleBoundsMessage, var.getParameter());
979             return PsiType.NULL;
980           }
981         }
982       }
983     }
984     return type;
985   }
986
987   private void registerIncompatibleErrorMessage(String value, PsiTypeParameter parameter) {
988     if (myContext != null) {
989       Map<PsiTypeParameter, String> errorMessage = myContext.getUserData(INFERENCE_FAILURE_MESSAGE);
990       if (errorMessage == null) {
991         errorMessage = new LinkedHashMap<PsiTypeParameter, String>();
992         myContext.putUserData(INFERENCE_FAILURE_MESSAGE, errorMessage);
993       }
994       errorMessage.put(parameter, value);
995     }
996   }
997
998   @Nullable
999   public static String getInferenceErrorMessage(PsiElement context) {
1000     final Map<PsiTypeParameter, String> errorsMap = context.getUserData(INFERENCE_FAILURE_MESSAGE);
1001     if (errorsMap != null) {
1002       return StringUtil.join(errorsMap.values(), "\n");
1003     }
1004     return null;
1005   }
1006
1007   private String incompatibleBoundsMessage(final InferenceVariable var,
1008                                                   final PsiSubstitutor substitutor,
1009                                                   final InferenceBound lowBound,
1010                                                   final String lowBoundName,
1011                                                   final InferenceBound upperBound,
1012                                                   final String upperBoundName) {
1013     final Function<PsiType, String> typePresentation = new Function<PsiType, String>() {
1014       @Override
1015       public String fun(PsiType type) {
1016         final PsiType substituted = substituteNonProperBound(type, substitutor);
1017         return (substituted != null ? substituted : type).getPresentableText();
1018       }
1019     };
1020     return "inference variable " + var.getName() + " has incompatible bounds:\n " + 
1021            lowBoundName  + ": " + StringUtil.join(var.getBounds(lowBound), typePresentation, ", ") + "\n" + 
1022            upperBoundName + ": " + StringUtil.join(var.getBounds(upperBound), typePresentation, ", ");
1023   }
1024
1025   private PsiType getLowerBound(InferenceVariable var, PsiSubstitutor substitutor) {
1026     return composeBound(var, InferenceBound.LOWER, new Function<Pair<PsiType, PsiType>, PsiType>() {
1027       @Override
1028       public PsiType fun(Pair<PsiType, PsiType> pair) {
1029         return GenericsUtil.getLeastUpperBound(pair.first, pair.second, myManager);
1030       }
1031     }, substitutor);
1032   }
1033
1034   private PsiType getUpperBound(InferenceVariable var, PsiSubstitutor substitutor) {
1035     return composeBound(var, InferenceBound.UPPER, UPPER_BOUND_FUNCTION, substitutor);
1036   }
1037
1038   public PsiType getEqualsBound(InferenceVariable var, PsiSubstitutor substitutor) {
1039     return composeBound(var, InferenceBound.EQ, new Function<Pair<PsiType, PsiType>, PsiType>() {
1040       @Override
1041       public PsiType fun(Pair<PsiType, PsiType> pair) {
1042         return !Comparing.equal(pair.first, pair.second) ? null : pair.first;
1043       }
1044     }, substitutor);
1045   }
1046
1047   private PsiType composeBound(InferenceVariable variable,
1048                                InferenceBound boundType,
1049                                Function<Pair<PsiType, PsiType>, PsiType> fun,
1050                                PsiSubstitutor substitutor) {
1051     return composeBound(variable, boundType, fun, substitutor, false);
1052   }
1053
1054   private PsiType composeBound(InferenceVariable variable,
1055                                InferenceBound boundType,
1056                                Function<Pair<PsiType, PsiType>, PsiType> fun,
1057                                PsiSubstitutor substitutor,
1058                                boolean includeNonProperBounds) {
1059     final List<PsiType> lowerBounds = variable.getBounds(boundType);
1060     PsiType lub = PsiType.NULL;
1061     for (PsiType lowerBound : lowerBounds) {
1062       lowerBound = substituteNonProperBound(lowerBound, substitutor);
1063       if (includeNonProperBounds || isProperType(lowerBound)) {
1064         if (lub == PsiType.NULL) {
1065           lub = lowerBound;
1066         }
1067         else {
1068           final Pair<PsiType, PsiType> pair = Pair.create(lub, lowerBound);
1069           lub = fun.fun(pair);
1070           if (lub == null) {
1071             return PsiType.NULL;
1072           }
1073         }
1074       }
1075     }
1076     return lub;
1077   }
1078
1079   public PsiManager getManager() {
1080     return myManager;
1081   }
1082
1083   public GlobalSearchScope getScope() {
1084     return GlobalSearchScope.allScope(myManager.getProject());
1085   }
1086
1087   public Collection<InferenceVariable> getInferenceVariables() {
1088     return myInferenceVariables;
1089   }
1090
1091   public void addConstraint(ConstraintFormula constraint) {
1092     if (myConstraintsCopy.add(constraint)) {
1093         myConstraints.add(constraint);
1094       }
1095   }
1096
1097   private boolean proceedWithAdditionalConstraints(Set<ConstraintFormula> additionalConstraints) {
1098     final PsiSubstitutor siteSubstitutor = mySiteSubstitutor;
1099
1100     while (!additionalConstraints.isEmpty()) {
1101       //extract subset of constraints
1102       final Set<ConstraintFormula> subset = buildSubset(additionalConstraints);
1103
1104       //collect all input variables of selection
1105       final Set<InferenceVariable> varsToResolve = new LinkedHashSet<InferenceVariable>();
1106       for (ConstraintFormula formula : subset) {
1107         if (formula instanceof InputOutputConstraintFormula) {
1108           collectVarsToResolve(varsToResolve, (InputOutputConstraintFormula)formula);
1109         }
1110       }
1111
1112       for (ConstraintFormula formula : subset) {
1113         if (!processOneConstraint(formula, siteSubstitutor, varsToResolve, additionalConstraints)) return false;
1114       }
1115     }
1116     return true;
1117   }
1118
1119   private void collectVarsToResolve(Set<InferenceVariable> varsToResolve, InputOutputConstraintFormula formula) {
1120     final Set<InferenceVariable> inputVariables = formula.getInputVariables(this);
1121     if (inputVariables != null) {
1122       for (InferenceVariable inputVariable : inputVariables) {
1123         varsToResolve.addAll(inputVariable.getDependencies(this));
1124       }
1125       varsToResolve.addAll(inputVariables);
1126     }
1127   }
1128
1129   private boolean processOneConstraint(ConstraintFormula formula,
1130                                        PsiSubstitutor siteSubstitutor,
1131                                        Set<InferenceVariable> varsToResolve,
1132                                        Set<ConstraintFormula> additionalConstraints) {
1133     if (formula instanceof ExpressionCompatibilityConstraint) {
1134       final PsiExpression expression = ((ExpressionCompatibilityConstraint)formula).getExpression();
1135       final PsiCallExpression callExpression = PsiTreeUtil.getParentOfType(expression, PsiCallExpression.class, false);
1136       if (callExpression != null) {
1137         final InferenceSession session = myNestedSessions.get(callExpression);
1138         if (session != null) {
1139           formula.apply(session.myInferenceSubstitution, true);
1140           collectVarsToResolve(varsToResolve, (InputOutputConstraintFormula)formula);
1141         }
1142       }
1143     }
1144
1145     //resolve input variables
1146     PsiSubstitutor substitutor = resolveSubset(varsToResolve, siteSubstitutor);
1147     if (substitutor == null) {
1148       return false;
1149     }
1150
1151     if (myContext instanceof PsiCallExpression) {
1152       PsiExpressionList argumentList = ((PsiCallExpression)myContext).getArgumentList();
1153       LOG.assertTrue(argumentList != null);
1154       MethodCandidateInfo.updateSubstitutor(argumentList, substitutor);
1155     }
1156
1157     try {
1158       formula.apply(substitutor, true);
1159
1160       myConstraints.add(formula);
1161       if (!repeatInferencePhases(true)) {
1162         return false;
1163       }
1164
1165       if (formula instanceof ExpressionCompatibilityConstraint) {
1166         PsiExpression expression = ((ExpressionCompatibilityConstraint)formula).getExpression();
1167         if (expression instanceof PsiLambdaExpression) {
1168           PsiType parameterType = ((ExpressionCompatibilityConstraint)formula).getT();
1169           if (!isProperType(parameterType)) {
1170             collectLambdaReturnExpression(additionalConstraints, (PsiLambdaExpression)expression, parameterType);
1171           }
1172         }
1173       }
1174     }
1175     finally {
1176       LambdaUtil.ourFunctionTypes.set(null);
1177     }
1178     return true;
1179   }
1180
1181   private Set<ConstraintFormula> buildSubset(final Set<ConstraintFormula> additionalConstraints) {
1182
1183     Set<ConstraintFormula> subset = new LinkedHashSet<ConstraintFormula>();
1184     final Set<InferenceVariable> outputVariables = new HashSet<InferenceVariable>();
1185     for (ConstraintFormula constraint : additionalConstraints) {
1186       if (constraint instanceof InputOutputConstraintFormula) {
1187         final Set<InferenceVariable> inputVariables = ((InputOutputConstraintFormula)constraint).getInputVariables(this);
1188         final Set<InferenceVariable> outputVars = ((InputOutputConstraintFormula)constraint).getOutputVariables(inputVariables, this);
1189         if (outputVars != null) {
1190           outputVariables.addAll(outputVars);
1191         }
1192       }
1193     }
1194
1195     Set<ConstraintFormula> noInputVariables = new LinkedHashSet<ConstraintFormula>();
1196     for (ConstraintFormula constraint : additionalConstraints) {
1197       if (constraint instanceof InputOutputConstraintFormula) {
1198         final Set<InferenceVariable> inputVariables = ((InputOutputConstraintFormula)constraint).getInputVariables(this);
1199         if (inputVariables != null) {
1200           boolean dependsOnOutput = false;
1201           for (InferenceVariable inputVariable : inputVariables) {
1202             if (dependsOnOutput) break;
1203             if (inputVariable.hasInstantiation(this)) continue;
1204             final Set<InferenceVariable> dependencies = inputVariable.getDependencies(this);
1205             dependencies.add(inputVariable);
1206             if (!hasCapture(inputVariable)) {
1207               for (InferenceVariable outputVariable : outputVariables) {
1208                 if (ContainerUtil.intersects(outputVariable.getDependencies(this), dependencies)) {
1209                   dependsOnOutput = true;
1210                   break;
1211                 }
1212               }
1213             }
1214
1215             dependencies.retainAll(outputVariables);
1216             if (!dependencies.isEmpty()) {
1217               dependsOnOutput = true;
1218               break;
1219             }
1220           }
1221           if (!dependsOnOutput) {
1222             subset.add(constraint);
1223
1224             if (inputVariables.isEmpty()) {
1225               noInputVariables.add(constraint);
1226             }
1227           }
1228         }
1229         else {
1230           subset.add(constraint);
1231           noInputVariables.add(constraint);
1232         }
1233       }
1234       else {
1235         subset.add(constraint);
1236       }
1237     }
1238     if (subset.isEmpty()) {
1239       subset.add(additionalConstraints.iterator().next()); //todo choose one constraint
1240     }
1241     
1242     if (!noInputVariables.isEmpty()) {
1243       subset = noInputVariables;
1244     }
1245
1246     additionalConstraints.removeAll(subset);
1247     return subset;
1248   }
1249
1250   public PsiSubstitutor collectApplicabilityConstraints(final PsiMethodReferenceExpression reference, 
1251                                                         final MethodCandidateInfo candidateInfo,
1252                                                         final PsiType functionalInterfaceType) {
1253     final PsiClassType.ClassResolveResult resolveResult = PsiUtil.resolveGenericsClassInType(functionalInterfaceType);
1254     final PsiMethod interfaceMethod = LambdaUtil.getFunctionalInterfaceMethod(resolveResult);
1255     LOG.assertTrue(interfaceMethod != null, myContext);
1256     final PsiSubstitutor functionalInterfaceSubstitutor = LambdaUtil.getSubstitutor(interfaceMethod, resolveResult);
1257     final MethodSignature signature = interfaceMethod.getSignature(functionalInterfaceSubstitutor);
1258
1259     final boolean varargs = candidateInfo.isVarargs();
1260     final PsiMethod method = candidateInfo.getElement();
1261     final PsiClass methodContainingClass = method.getContainingClass();
1262
1263     final PsiMethodReferenceUtil.QualifierResolveResult qualifierResolveResult = PsiMethodReferenceUtil.getQualifierResolveResult(reference);
1264
1265     final PsiClass containingClass = qualifierResolveResult.getContainingClass();
1266     if (containingClass == null) {
1267       return resolveSubset(myInferenceVariables, mySiteSubstitutor); 
1268     }
1269
1270     final PsiParameter[] functionalMethodParameters = interfaceMethod.getParameterList().getParameters();
1271     final PsiParameter[] parameters = method.getParameterList().getParameters();
1272
1273     final boolean isStatic = method.hasModifierProperty(PsiModifier.STATIC);
1274     PsiSubstitutor psiSubstitutor = qualifierResolveResult.getSubstitutor();
1275
1276     if (parameters.length == functionalMethodParameters.length && !varargs || isStatic && varargs) {//static methods
1277
1278       if (method.isConstructor() && PsiUtil.isRawSubstitutor(containingClass, psiSubstitutor)) {
1279         //15.13.1 If ClassType is a raw type, but is not a non-static member type of a raw type,
1280         //the candidate notional member methods are those specified in §15.9.3 for a
1281         //class instance creation expression that uses <> to elide the type arguments to a class
1282         initBounds(containingClass.getTypeParameters());
1283         psiSubstitutor = PsiSubstitutor.EMPTY;
1284       }
1285
1286       if (methodContainingClass != null) {
1287         psiSubstitutor = TypeConversionUtil.getClassSubstitutor(methodContainingClass, containingClass, psiSubstitutor);
1288         LOG.assertTrue(psiSubstitutor != null, "derived: " + containingClass + "; super: " + methodContainingClass);
1289       }
1290
1291       for (int i = 0; i < functionalMethodParameters.length; i++) {
1292         final PsiType pType = signature.getParameterTypes()[i];
1293         addConstraint(new TypeCompatibilityConstraint(substituteWithInferenceVariables(getParameterType(parameters, i, psiSubstitutor, varargs)),
1294                                                       PsiImplUtil.normalizeWildcardTypeByPosition(pType, reference)));
1295       }
1296     }
1297     else if (PsiMethodReferenceUtil.isResolvedBySecondSearch(reference, signature, varargs, isStatic, parameters.length)) { //instance methods
1298       initBounds(containingClass.getTypeParameters());
1299
1300       final PsiType pType = signature.getParameterTypes()[0];
1301
1302       // 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,
1303       // the type to search is the result of capture conversion (5.1.10) applied to T; 
1304       // 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.
1305       if (PsiUtil.isRawSubstitutor(containingClass, psiSubstitutor)) {
1306         PsiType normalizedPType = PsiImplUtil.normalizeWildcardTypeByPosition(pType, (PsiExpression)myContext);
1307         final PsiSubstitutor receiverSubstitutor = PsiMethodReferenceCompatibilityConstraint
1308           .getParameterizedTypeSubstitutor(containingClass, normalizedPType);
1309         if (receiverSubstitutor != null) {
1310           if (!method.hasTypeParameters()) {
1311             if (signature.getParameterTypes().length == 1 || PsiUtil.isRawSubstitutor(containingClass, receiverSubstitutor)) {
1312               return receiverSubstitutor;
1313             }
1314           }
1315           psiSubstitutor = receiverSubstitutor;
1316         }
1317       }
1318       else if (methodContainingClass != null) {
1319         psiSubstitutor = TypeConversionUtil.getClassSubstitutor(methodContainingClass, containingClass, psiSubstitutor);
1320         LOG.assertTrue(psiSubstitutor != null, "derived: " + containingClass + "; super: " + methodContainingClass);
1321       }
1322
1323       final PsiType qType = JavaPsiFacade.getElementFactory(method.getProject()).createType(containingClass, psiSubstitutor);
1324
1325       addConstraint(new TypeCompatibilityConstraint(substituteWithInferenceVariables(qType), pType));
1326
1327       for (int i = 0; i < signature.getParameterTypes().length - 1; i++) {
1328         final PsiType interfaceParamType = signature.getParameterTypes()[i + 1];
1329         addConstraint(new TypeCompatibilityConstraint(substituteWithInferenceVariables(getParameterType(parameters, i, psiSubstitutor, varargs)),
1330                                                       PsiImplUtil.normalizeWildcardTypeByPosition(interfaceParamType, reference)));
1331       }
1332     }
1333
1334     return null;
1335   }
1336
1337   public void setErased() {
1338     myErased = true;
1339   }
1340
1341   public InferenceVariable getInferenceVariable(PsiTypeParameter parameter) {
1342     return parameter instanceof InferenceVariable && myInferenceVariables.contains(parameter) ? (InferenceVariable)parameter : null;
1343   }
1344
1345   /**
1346    * 18.5.4 More Specific Method Inference 
1347    */
1348   public static boolean isMoreSpecific(PsiMethod m1,
1349                                        PsiMethod m2,
1350                                        PsiSubstitutor siteSubstitutor1, 
1351                                        PsiExpression[] args,
1352                                        PsiElement context,
1353                                        boolean varargs) {
1354     List<PsiTypeParameter> params = new ArrayList<PsiTypeParameter>();
1355     for (PsiTypeParameter param : PsiUtil.typeParametersIterable(m2)) {
1356       params.add(param);
1357     }
1358
1359     siteSubstitutor1 = getSiteSubstitutor(siteSubstitutor1, params);
1360
1361     final InferenceSession session = new InferenceSession(params.toArray(new PsiTypeParameter[params.size()]), siteSubstitutor1, m2.getManager(), context);
1362
1363     final PsiParameter[] parameters1 = m1.getParameterList().getParameters();
1364     final PsiParameter[] parameters2 = m2.getParameterList().getParameters();
1365     if (!varargs) {
1366       LOG.assertTrue(parameters1.length == parameters2.length);
1367     }
1368
1369     final int paramsLength = !varargs ? parameters1.length : parameters1.length - 1;
1370     for (int i = 0; i < paramsLength; i++) {
1371       PsiType sType = getParameterType(parameters1, i, siteSubstitutor1, false);
1372       PsiType tType = session.substituteWithInferenceVariables(getParameterType(parameters2, i, siteSubstitutor1, varargs));
1373       if (LambdaUtil.isFunctionalType(sType) && LambdaUtil.isFunctionalType(tType) && !relates(sType, tType)) {
1374         if (!isFunctionalTypeMoreSpecific(sType, tType, session, args[i])) {
1375           return false;
1376         }
1377       } else {
1378         if (session.isProperType(tType)) {
1379           if (!TypeConversionUtil.isAssignable(tType, sType)) {
1380             return false;
1381           }
1382         }
1383         session.addConstraint(new StrictSubtypingConstraint(tType, sType));
1384       }
1385     }
1386
1387     if (varargs) {
1388       PsiType sType = getParameterType(parameters1, paramsLength, siteSubstitutor1, true);
1389       PsiType tType = session.substituteWithInferenceVariables(getParameterType(parameters2, paramsLength, siteSubstitutor1, true));
1390       session.addConstraint(new StrictSubtypingConstraint(tType, sType));
1391     }
1392
1393     return session.repeatInferencePhases(true);
1394   }
1395
1396   private static PsiSubstitutor getSiteSubstitutor(PsiSubstitutor siteSubstitutor1, List<PsiTypeParameter> params) {
1397     PsiSubstitutor subst = PsiSubstitutor.EMPTY;
1398     for (PsiTypeParameter param : params) {
1399       subst = subst.put(param, siteSubstitutor1.substitute(param));
1400     }
1401     return subst;
1402   }
1403
1404   /**
1405    * 15.12.2.5 Choosing the Most Specific Method
1406    * "a functional interface type S is more specific than a functional interface type T for an expression exp" part
1407    */
1408   public static boolean isFunctionalTypeMoreSpecificOnExpression(PsiType sType,
1409                                                                  PsiType tType,
1410                                                                  PsiExpression arg) {
1411     return isFunctionalTypeMoreSpecific(sType, tType, null, arg);
1412   }
1413
1414   private static boolean isFunctionalTypeMoreSpecific(PsiType sType,
1415                                                       PsiType tType,
1416                                                       @Nullable InferenceSession session, 
1417                                                       PsiExpression... args) {
1418     final PsiType capturedSType = sType;//todo capture of Si session != null && sType != null ? PsiUtil.captureToplevelWildcards(sType, session.myContext) : sType;
1419     final PsiClassType.ClassResolveResult sResult = PsiUtil.resolveGenericsClassInType(capturedSType);
1420     final PsiMethod sInterfaceMethod = LambdaUtil.getFunctionalInterfaceMethod(sResult);
1421     LOG.assertTrue(sInterfaceMethod != null);
1422     final PsiSubstitutor sSubstitutor = LambdaUtil.getSubstitutor(sInterfaceMethod, sResult);
1423
1424     final PsiClassType.ClassResolveResult tResult = PsiUtil.resolveGenericsClassInType(tType);
1425     final PsiMethod tInterfaceMethod = LambdaUtil.getFunctionalInterfaceMethod(tResult);
1426     LOG.assertTrue(tInterfaceMethod != null);
1427     final PsiSubstitutor tSubstitutor = LambdaUtil.getSubstitutor(tInterfaceMethod, tResult);
1428
1429     for (PsiExpression arg : args) {
1430       if (!argConstraints(arg, session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor)) {
1431         return false;
1432       }
1433     }
1434     return true;
1435   }
1436
1437   protected static boolean argConstraints(PsiExpression arg,
1438                                           @Nullable InferenceSession session,
1439                                           PsiMethod sInterfaceMethod,
1440                                           PsiSubstitutor sSubstitutor, 
1441                                           PsiMethod tInterfaceMethod, 
1442                                           PsiSubstitutor tSubstitutor) {
1443     if (arg instanceof PsiLambdaExpression && ((PsiLambdaExpression)arg).hasFormalParameterTypes()) {
1444       final PsiType sReturnType = sSubstitutor.substitute(sInterfaceMethod.getReturnType());
1445       final PsiType tReturnType = tSubstitutor.substitute(tInterfaceMethod.getReturnType());
1446
1447       if (tReturnType == PsiType.VOID) {
1448         return true;
1449       }
1450
1451       final List<PsiExpression> returnExpressions = LambdaUtil.getReturnExpressions((PsiLambdaExpression)arg);
1452
1453       if (LambdaUtil.isFunctionalType(sReturnType) && LambdaUtil.isFunctionalType(tReturnType) &&
1454           !TypeConversionUtil.isAssignable(TypeConversionUtil.erasure(sReturnType), TypeConversionUtil.erasure(tReturnType)) &&
1455           !TypeConversionUtil.isAssignable(TypeConversionUtil.erasure(tReturnType), TypeConversionUtil.erasure(sReturnType))) {
1456
1457         //Otherwise, if R1 and R2 are functional interface types, and neither interface is a subinterface of the other, 
1458         //then these rules are applied recursively to R1 and R2, for each result expression in expi.
1459         if (!isFunctionalTypeMoreSpecific(sReturnType, tReturnType, session, returnExpressions.toArray(new PsiExpression[returnExpressions.size()]))) {
1460           return false;
1461         }
1462       } else {
1463         final boolean sPrimitive = sReturnType instanceof PsiPrimitiveType && sReturnType != PsiType.VOID;
1464         final boolean tPrimitive = tReturnType instanceof PsiPrimitiveType && tReturnType != PsiType.VOID;
1465         if (sPrimitive ^ tPrimitive) {
1466           for (PsiExpression returnExpression : returnExpressions) {
1467             if (!PsiPolyExpressionUtil.isPolyExpression(returnExpression)) {
1468               final PsiType returnExpressionType = returnExpression.getType();
1469               if (sPrimitive) {
1470                 if (!(returnExpressionType instanceof PsiPrimitiveType)) {
1471                   return false;
1472                 }
1473               } else {
1474                 if (!(returnExpressionType instanceof PsiClassType)) {
1475                   return false;
1476                 }
1477               }
1478             }
1479             else if (sPrimitive) {
1480               return false;
1481             }
1482           }
1483           return true;
1484         }
1485         if (session != null) {
1486           session.addConstraint(new StrictSubtypingConstraint(tReturnType, sReturnType));
1487           return true;
1488         } else {
1489           return sReturnType != null && tReturnType != null && TypeConversionUtil.isAssignable(tReturnType, sReturnType); 
1490         }
1491       }
1492     }
1493
1494     if (arg instanceof PsiMethodReferenceExpression && ((PsiMethodReferenceExpression)arg).isExact()) {
1495       final PsiParameter[] sParameters = sInterfaceMethod.getParameterList().getParameters();
1496       final PsiParameter[] tParameters = tInterfaceMethod.getParameterList().getParameters();
1497       LOG.assertTrue(sParameters.length == tParameters.length, 
1498                      "s: " + sInterfaceMethod.getParameterList().getText() + "; t: " + tInterfaceMethod.getParameterList().getText());
1499       for (int i = 0; i < tParameters.length; i++) {
1500         final PsiType tSubstituted = tSubstitutor.substitute(tParameters[i].getType());
1501         final PsiType sSubstituted = sSubstitutor.substitute(sParameters[i].getType());
1502         if (session != null) {
1503           session.addConstraint(new TypeEqualityConstraint(tSubstituted, sSubstituted));
1504         }
1505         else {
1506           if (!Comparing.equal(tSubstituted, sSubstituted)) {
1507             return false;
1508           }
1509         }
1510       }
1511       final PsiType sReturnType = sSubstitutor.substitute(sInterfaceMethod.getReturnType());
1512       final PsiType tReturnType = tSubstitutor.substitute(tInterfaceMethod.getReturnType());
1513       if (tReturnType == PsiType.VOID) {
1514         return true;
1515       }
1516
1517       final boolean sPrimitive = sReturnType instanceof PsiPrimitiveType && sReturnType != PsiType.VOID;
1518       final boolean tPrimitive = tReturnType instanceof PsiPrimitiveType && tReturnType != PsiType.VOID;
1519
1520       if (sPrimitive ^ tPrimitive) {
1521         final PsiMember member = ((PsiMethodReferenceExpression)arg).getPotentiallyApplicableMember();
1522         LOG.assertTrue(member != null, arg);
1523         if (member instanceof PsiMethod) {
1524           final PsiType methodReturnType = ((PsiMethod)member).getReturnType();
1525           if (sPrimitive && methodReturnType instanceof PsiPrimitiveType && methodReturnType != PsiType.VOID ||
1526               tPrimitive && methodReturnType instanceof PsiClassType) {
1527             return true;
1528           }
1529         }
1530         return false;
1531       }
1532
1533       if (session != null) {
1534         session.addConstraint(new StrictSubtypingConstraint(tReturnType, sReturnType));
1535         return true;
1536       } else {
1537         return sReturnType != null && tReturnType != null && TypeConversionUtil.isAssignable(tReturnType, sReturnType);
1538       }
1539     }
1540
1541     if (arg instanceof PsiParenthesizedExpression) {
1542       return argConstraints(((PsiParenthesizedExpression)arg).getExpression(), session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor);
1543     }
1544
1545     if (arg instanceof PsiConditionalExpression) {
1546       final PsiExpression thenExpression = ((PsiConditionalExpression)arg).getThenExpression();
1547       final PsiExpression elseExpression = ((PsiConditionalExpression)arg).getElseExpression();
1548       return argConstraints(thenExpression, session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor) &&
1549              argConstraints(elseExpression, session, sInterfaceMethod, sSubstitutor, tInterfaceMethod, tSubstitutor);
1550     }
1551     return false;
1552   }
1553
1554   /**
1555    *  if Si is a functional interface type and Ti is a parameterization of functional interface, I, and none of the following is true:
1556
1557    *  Si is a superinterface of I, or a parameterization of a superinterface of I.
1558    *  Si is subinterface of I, or a parameterization of a subinterface of I.
1559    *  Si is an intersection type and each element of the intersection is a superinterface of I, or a parameterization of a superinterface of I.
1560    *  Si is an intersection type and some element of the intersection is a subinterface of I, or a parameterization of a subinterface of I.
1561    */
1562   private static boolean relates(PsiType sType, PsiType tType) {
1563     final PsiType erasedType = TypeConversionUtil.erasure(tType);
1564     LOG.assertTrue(erasedType != null);  
1565     if (sType instanceof PsiIntersectionType) {
1566       boolean superRelation = true;
1567       boolean subRelation = false;
1568       for (PsiType sConjunct : ((PsiIntersectionType)sType).getConjuncts()) {
1569         final PsiType sConjunctErasure = TypeConversionUtil.erasure(sConjunct);
1570         if (sConjunctErasure != null) {
1571           superRelation &= TypeConversionUtil.isAssignable(sConjunctErasure, erasedType);
1572           subRelation |= TypeConversionUtil.isAssignable(erasedType, sConjunctErasure);
1573         }
1574       }
1575       return superRelation || subRelation;
1576     }
1577     if (sType instanceof PsiClassType) {
1578       final PsiType sTypeErasure = TypeConversionUtil.erasure(sType);
1579       if (sTypeErasure != null) {
1580         return TypeConversionUtil.isAssignable(sTypeErasure, erasedType) || TypeConversionUtil.isAssignable(erasedType, sTypeErasure);
1581       }
1582     }
1583     return false;
1584   }
1585
1586   public void collectCaptureDependencies(InferenceVariable inferenceVariable, Set<InferenceVariable> dependencies) {
1587     myIncorporationPhase.collectCaptureDependencies(inferenceVariable, dependencies);
1588   }
1589
1590   public boolean hasCapture(InferenceVariable inferenceVariable) {
1591     return myIncorporationPhase.hasCaptureConstraints(Arrays.asList(inferenceVariable));
1592   }
1593
1594   public static boolean wasUncheckedConversionPerformed(PsiElement call) {
1595     final Boolean erased = call.getUserData(ERASED);
1596     return erased != null && erased.booleanValue();
1597   }
1598
1599   public PsiElement getContext() {
1600     return myContext;
1601   }
1602
1603   public void propagateVariables(Collection<InferenceVariable> variables) {
1604     myInferenceVariables.addAll(variables);
1605   }
1606
1607   public PsiType substituteWithInferenceVariables(PsiType type) {
1608     return myInferenceSubstitution.substitute(type);
1609   }
1610
1611   public InferenceSession findNestedCallSession(PsiExpression arg) {
1612     InferenceSession session = myNestedSessions.get(PsiTreeUtil.getParentOfType(arg, PsiCallExpression.class));
1613     if (session == null) {
1614       session = this;
1615     }
1616     return session;
1617   }
1618
1619   public PsiType startWithFreshVars(PsiType type) {
1620     PsiSubstitutor s = PsiSubstitutor.EMPTY;
1621     for (InferenceVariable variable : myInferenceVariables) {
1622       s = s.put(variable, JavaPsiFacade.getElementFactory(variable.getProject()).createType(variable.getParameter()));
1623     }
1624     return s.substitute(type);
1625   }
1626
1627   public static boolean areSameFreshVariables(PsiTypeParameter p1, PsiTypeParameter p2) {
1628     final PsiElement originalContext = p1.getUserData(ORIGINAL_CONTEXT);
1629     return originalContext != null && originalContext == p2.getUserData(ORIGINAL_CONTEXT);
1630   }
1631
1632   public static PsiClass findParameterizationOfTheSameGenericClass(List<PsiType> upperBounds,
1633                                                                    Processor<Pair<PsiType, PsiType>> processor) {
1634     for (int i = 0; i < upperBounds.size(); i++) {
1635       final PsiType sBound = upperBounds.get(i);
1636       final PsiClass sClass = PsiUtil.resolveClassInClassTypeOnly(sBound);
1637       if (sClass == null) continue;
1638       final LinkedHashSet<PsiClass> superClasses = InheritanceUtil.getSuperClasses(sClass);
1639       superClasses.add(sClass);
1640       for (int j = i + 1; j < upperBounds.size(); j++) {
1641         final PsiType tBound = upperBounds.get(j);
1642         final PsiClass tClass = PsiUtil.resolveClassInClassTypeOnly(tBound);
1643         if (tClass != null) {
1644
1645           final LinkedHashSet<PsiClass> tSupers = InheritanceUtil.getSuperClasses(tClass);
1646           tSupers.add(tClass);
1647           tSupers.retainAll(superClasses);
1648
1649           for (PsiClass gClass : tSupers) {
1650             final PsiSubstitutor sSubstitutor = TypeConversionUtil.getSuperClassSubstitutor(gClass, (PsiClassType)sBound);
1651             final PsiSubstitutor tSubstitutor = TypeConversionUtil.getSuperClassSubstitutor(gClass, (PsiClassType)tBound);
1652             for (PsiTypeParameter typeParameter : gClass.getTypeParameters()) {
1653               final PsiType sType = sSubstitutor.substitute(typeParameter);
1654               final PsiType tType = tSubstitutor.substitute(typeParameter);
1655               final Pair<PsiType, PsiType> typePair = Pair.create(sType, tType);
1656               if (!processor.process(typePair)) {
1657                 return gClass;
1658               }
1659             }
1660           }
1661         }
1662       }
1663     }
1664     return null;
1665   }
1666 }