java/java-psi-impl/src/com/intellij/psi/impl/source/resolve/graphInference/InferenceSession.java

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