java/java-impl/src/com/intellij/refactoring/typeCook/deductive/resolver/BindingFactory.java

   1 /*
   2  * Copyright 2000-2009 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.refactoring.typeCook.deductive.resolver;
  17
  18 import com.intellij.openapi.diagnostic.Logger;
  19 import com.intellij.openapi.project.Project;
  20 import com.intellij.openapi.util.Pair;
  21 import com.intellij.psi.*;
  22 import com.intellij.psi.search.GlobalSearchScope;
  23 import com.intellij.psi.search.searches.ClassInheritorsSearch;
  24 import com.intellij.psi.util.InheritanceUtil;
  25 import com.intellij.psi.util.TypeConversionUtil;
  26 import com.intellij.refactoring.typeCook.Util;
  27 import com.intellij.refactoring.typeCook.deductive.PsiExtendedTypeVisitor;
  28 import com.intellij.refactoring.typeCook.deductive.PsiTypeVariableFactory;
  29 import com.intellij.refactoring.typeCook.deductive.builder.Constraint;
  30 import com.intellij.refactoring.typeCook.deductive.builder.ReductionSystem;
  31 import com.intellij.refactoring.typeCook.deductive.builder.Subtype;
  32 import com.intellij.util.IncorrectOperationException;
  33 import gnu.trove.TIntObjectHashMap;
  34 import gnu.trove.TObjectProcedure;
  35
  36 import java.util.HashSet;
  37 import java.util.LinkedHashSet;
  38 import java.util.LinkedList;
  39 import java.util.Set;
  40
  41 /**
  42  * @author db
  43  */
  44 @SuppressWarnings({"SuspiciousNameCombination"})
  45 public class BindingFactory {
  46   private static final Logger LOG = Logger.getInstance("#com.intellij.refactoring.typeCook.deductive.resolver.BindingFactory");
  47
  48   private final HashSet<PsiTypeVariable> myBoundVariables;
  49   private final Project myProject;
  50   private final PsiTypeVariableFactory myFactory;
  51
  52   private PsiClass[] getGreatestLowerClasses(final PsiClass aClass, final PsiClass bClass) {
  53     if (InheritanceUtil.isInheritorOrSelf(aClass, bClass, true)) {
  54       return new PsiClass[]{aClass};
  55     }
  56
  57     if (InheritanceUtil.isInheritorOrSelf(bClass, aClass, true)) {
  58       return new PsiClass[]{bClass};
  59     }
  60
  61     final Set<PsiClass> descendants = new LinkedHashSet<PsiClass>();
  62
  63     new Object() {
  64       public void getGreatestLowerClasses(final PsiClass aClass, final PsiClass bClass, final Set<PsiClass> descendants) {
  65         if (bClass.hasModifierProperty(PsiModifier.FINAL)) return;
  66         if (aClass.isInheritor(bClass, true)) {
  67           descendants.add(aClass);
  68         }
  69         else {
  70           for (PsiClass bInheritor : ClassInheritorsSearch.search(bClass, bClass.getUseScope(), false)) {
  71             getGreatestLowerClasses(bInheritor, aClass, descendants);
  72           }
  73         }
  74       }
  75     }.getGreatestLowerClasses(aClass, bClass, descendants);
  76
  77     return descendants.toArray(new PsiClass[descendants.size()]);
  78   }
  79
  80   private class BindingImpl extends Binding {
  81     private final TIntObjectHashMap<PsiType> myBindings;
  82     private boolean myCyclic;
  83
  84     BindingImpl(final PsiTypeVariable var, final PsiType type) {
  85       myBindings = new TIntObjectHashMap<PsiType>();
  86       myCyclic = type instanceof PsiTypeVariable;
  87
  88       myBindings.put(var.getIndex(), type);
  89     }
  90
  91     BindingImpl(final int index, final PsiType type) {
  92       myBindings = new TIntObjectHashMap<PsiType>();
  93       myCyclic = type instanceof PsiTypeVariable;
  94
  95       myBindings.put(index, type);
  96
  97       if (type instanceof Bottom) {
  98         final HashSet<PsiTypeVariable> cluster = myFactory.getClusterOf(index);
  99
 100         if (cluster != null) {
 101           for (PsiTypeVariable var : cluster) {
 102             myBindings.put(var.getIndex(), type);
 103           }
 104         }
 105       }
 106     }
 107
 108     BindingImpl() {
 109       myBindings = new TIntObjectHashMap<PsiType>();
 110       myCyclic = false;
 111     }
 112
 113     public PsiType apply(final PsiType type) {
 114       if (type instanceof PsiTypeVariable) {
 115         final PsiType t = myBindings.get(((PsiTypeVariable) type).getIndex());
 116         return t == null ? type : t;
 117       }
 118       else if (type instanceof PsiArrayType) {
 119         return apply(((PsiArrayType)type).getComponentType()).createArrayType();
 120       }
 121       else if (type instanceof PsiClassType) {
 122         final PsiClassType.ClassResolveResult result = Util.resolveType(type);
 123         final PsiClass theClass = result.getElement();
 124         final PsiSubstitutor aSubst = result.getSubstitutor();
 125
 126         PsiSubstitutor theSubst = PsiSubstitutor.EMPTY;
 127
 128         if (theClass != null) {
 129           for (final PsiTypeParameter aParm : aSubst.getSubstitutionMap().keySet()) {
 130             final PsiType aType = aSubst.substitute(aParm);
 131
 132             theSubst = theSubst.put(aParm, apply(aType));
 133           }
 134
 135           return JavaPsiFacade.getInstance(theClass.getProject()).getElementFactory().createType(theClass, theSubst);
 136         }
 137         else {
 138           return type;
 139         }
 140       }
 141       else if (type instanceof PsiWildcardType) {
 142         final PsiWildcardType wcType = (PsiWildcardType)type;
 143         final PsiType bound = wcType.getBound();
 144
 145         if (bound != null) {
 146           final PsiType abound = apply(bound);
 147
 148           if (abound instanceof PsiWildcardType) {
 149             return null;
 150           }
 151
 152           return
 153             wcType.isExtends()
 154             ? PsiWildcardType.createExtends(PsiManager.getInstance(myProject), abound)
 155             : PsiWildcardType.createSuper(PsiManager.getInstance(myProject), abound);
 156         }
 157
 158         return type;
 159       }
 160       else {
 161         return type;
 162       }
 163     }
 164
 165     public boolean equals(final Object o) {
 166       if (this == o) return true;
 167       if (!(o instanceof BindingImpl)) return false;
 168
 169       final BindingImpl binding = (BindingImpl)o;
 170
 171       if (!myBindings.equals(binding.myBindings)) {
 172         return false;
 173       }
 174
 175       return true;
 176     }
 177
 178     public Binding compose(final Binding b) {
 179       LOG.assertTrue(b instanceof BindingImpl);
 180
 181       final BindingImpl b1 = this;
 182       final BindingImpl b2 = (BindingImpl)b;
 183
 184       final BindingImpl b3 = new BindingImpl();
 185
 186       for (PsiTypeVariable boundVariable : myBoundVariables) {
 187         final int i = boundVariable.getIndex();
 188
 189         final PsiType b1i = b1.myBindings.get(i);
 190         final PsiType b2i = b2.myBindings.get(i);
 191
 192         final int flag = (b1i == null ? 0 : 1) + (b2i == null ? 0 : 2);
 193
 194         switch (flag) {
 195           case 0:
 196             break;
 197
 198           case 1: /* b1(i)\b2(i) */
 199             {
 200               final PsiType type = b2.apply(b1i);
 201
 202               if (type == null) {
 203                 return null;
 204               }
 205
 206               b3.myBindings.put(i, type);
 207               b3.myCyclic = type instanceof PsiTypeVariable;
 208             }
 209             break;
 210
 211           case 2: /* b2(i)\b1(i) */
 212             {
 213               final PsiType type = b1.apply(b2i);
 214
 215               if (type == null) {
 216                 return null;
 217               }
 218
 219               b3.myBindings.put(i, type);
 220               b3.myCyclic = type instanceof PsiTypeVariable;
 221             }
 222             break;
 223
 224           case 3:  /* b2(i) \cap b1(i) */
 225           {
 226             final Binding common = rise(b1i, b2i, null);
 227
 228             if (common == null) {
 229               return null;
 230             }
 231
 232             final PsiType type = common.apply(b1i);
 233             if (type == null) {
 234               return null;
 235             }
 236
 237             if (type == null) {
 238               return null;
 239             }
 240
 241             b3.myBindings.put(i, type);
 242             b3.myCyclic = type instanceof PsiTypeVariable;
 243           }
 244         }
 245       }
 246
 247       return b3;
 248     }
 249
 250     public String toString() {
 251       final StringBuffer buffer = new StringBuffer();
 252
 253       for (PsiTypeVariable boundVariable : myBoundVariables) {
 254         final int i = boundVariable.getIndex();
 255         final PsiType binding = myBindings.get(i);
 256
 257         if (binding != null) {
 258           buffer.append("#").append(i).append(" -> ").append(binding.getPresentableText()).append("; ");
 259         }
 260       }
 261
 262       return buffer.toString();
 263     }
 264
 265     private PsiType normalize(final PsiType t) {
 266       if (t == null || t instanceof PsiTypeVariable) {
 267         return Bottom.BOTTOM;
 268       }
 269
 270       if (t instanceof PsiWildcardType) {
 271         return ((PsiWildcardType)t).getBound();
 272       }
 273
 274       return t;
 275     }
 276
 277     public int compare(final Binding binding) {
 278       final BindingImpl b2 = (BindingImpl)binding;
 279       final BindingImpl b1 = this;
 280
 281       int directoin = Binding.NONCOMPARABLE;
 282       boolean first = true;
 283
 284       for (PsiTypeVariable boundVariable : myBoundVariables) {
 285         final int index = boundVariable.getIndex();
 286
 287         final PsiType x = normalize(b1.myBindings.get(index));
 288         final PsiType y = normalize(b2.myBindings.get(index));
 289
 290         final int comp = new Object() {
 291           int compare(final PsiType x, final PsiType y) {
 292             final int[] kinds = new Object() {
 293               private int classify(final PsiType type) {
 294                 if (type == null) {
 295                   return 0;
 296                 }
 297
 298                 if (type instanceof PsiPrimitiveType) {
 299                   return 1;
 300                 }
 301
 302                 if (type instanceof PsiArrayType) {
 303                   return 2;
 304                 }
 305
 306                 if (type instanceof PsiClassType) {
 307                   return 3;
 308                 }
 309
 310                 return 4; // Bottom
 311               }
 312
 313               int[] classify2(final PsiType x, final PsiType y) {
 314                 return new int[]{classify(x), classify(y)};
 315               }
 316             }.classify2(x, y);
 317
 318             final int kindX = kinds[0];
 319             final int kindY = kinds[1];
 320
 321             // Break your brain here...
 322             if (kindX + kindY == 0) {
 323               return Binding.SAME;
 324             }
 325
 326             if (kindX * kindY == 0) {
 327               if (kindX == 0) {
 328                 return Binding.WORSE;
 329               }
 330
 331               return Binding.BETTER;
 332             }
 333
 334             if (kindX * kindY == 1) {
 335               if (x.equals(y)) {
 336                 return Binding.SAME;
 337               }
 338
 339               return Binding.NONCOMPARABLE;
 340             }
 341
 342             if (kindX != kindY) {
 343               if (kindX == 4) {
 344                 return Binding.WORSE;
 345               }
 346
 347               if (kindY == 4) {
 348                 return Binding.BETTER;
 349               }
 350
 351               if (kindX + kindY == 5) {
 352                 try {
 353                   final PsiElementFactory f = JavaPsiFacade.getInstance(myProject).getElementFactory();
 354                   final PsiType cloneable = f.createTypeFromText("java.lang.Cloneable", null);
 355                   final PsiType object = f.createTypeFromText("java.lang.Object", null);
 356                   final PsiType serializable = f.createTypeFromText("java.io.Serializable", null);
 357
 358                   PsiType type;
 359                   int flag;
 360
 361                   if (kindX == 3) {
 362                     type = x;
 363                     flag = Binding.WORSE;
 364                   }
 365                   else {
 366                     type = y;
 367                     flag = Binding.BETTER;
 368                   }
 369
 370                   if (type.equals(object) || type.equals(cloneable) || type.equals(serializable)) {
 371                     return flag;
 372                   }
 373                 }
 374                 catch (IncorrectOperationException e) {
 375                   LOG.error(e);
 376                 }
 377               }
 378
 379               return Binding.NONCOMPARABLE;
 380             }
 381
 382             if (kindX == 2) {
 383               return compare(((PsiArrayType)x).getComponentType(), ((PsiArrayType)y).getComponentType());
 384             }
 385
 386             if (x.equals(y)) {
 387               return Binding.SAME;
 388             }
 389             // End of breaking...
 390
 391             final PsiClassType.ClassResolveResult resultX = Util.resolveType(x);
 392             final PsiClassType.ClassResolveResult resultY = Util.resolveType(y);
 393
 394             final PsiClass xClass = resultX.getElement();
 395             final PsiClass yClass = resultY.getElement();
 396
 397             final PsiSubstitutor xSubst = resultX.getSubstitutor();
 398             final PsiSubstitutor ySubst = resultY.getSubstitutor();
 399
 400             if (xClass == null || yClass == null) {
 401               return Binding.NONCOMPARABLE;
 402             }
 403
 404             if (xClass.equals(yClass)) {
 405               boolean first = true;
 406               int direction = Binding.SAME;
 407
 408               for (final PsiTypeParameter p : xSubst.getSubstitutionMap().keySet()) {
 409                 final PsiType xParm = xSubst.substitute(p);
 410                 final PsiType yParm = ySubst.substitute(p);
 411
 412                 final int comp = compare(xParm, yParm);
 413
 414                 if (comp == Binding.NONCOMPARABLE) {
 415                   return Binding.NONCOMPARABLE;
 416                 }
 417
 418                 if (first) {
 419                   first = false;
 420                   direction = comp;
 421                 }
 422
 423                 if (direction != comp) {
 424                   return Binding.NONCOMPARABLE;
 425                 }
 426               }
 427
 428               return direction;
 429             }
 430             else {
 431               if (InheritanceUtil.isCorrectDescendant(xClass, yClass, true)) {
 432                 return Binding.BETTER;
 433               }
 434               else if (InheritanceUtil.isCorrectDescendant(yClass, xClass, true)) {
 435                 return Binding.WORSE;
 436               }
 437
 438               return Binding.NONCOMPARABLE;
 439             }
 440           }
 441         }.compare(x, y);
 442
 443         if (comp == Binding.NONCOMPARABLE) {
 444           return Binding.NONCOMPARABLE;
 445         }
 446
 447         if (first) {
 448           first = false;
 449           directoin = comp;
 450         }
 451
 452         if (directoin != SAME) {
 453           if (comp != Binding.SAME && directoin != comp) {
 454             return Binding.NONCOMPARABLE;
 455           }
 456         }
 457         else if (comp != SAME) {
 458           directoin = comp;
 459         }
 460       }
 461
 462       return directoin;
 463     }
 464
 465     public boolean nonEmpty() {
 466       return myBindings.size() > 0;
 467     }
 468
 469     public boolean isCyclic() {
 470       return myCyclic;
 471     }
 472
 473     public Binding reduceRecursive() {
 474       final BindingImpl binding = (BindingImpl)create();
 475
 476       for (final PsiTypeVariable var : myBoundVariables) {
 477         final int index = var.getIndex();
 478         final PsiType type = myBindings.get(index);
 479
 480         if (type != null) {
 481           class Verifier extends PsiExtendedTypeVisitor<Void> {
 482             boolean myFlag = false;
 483
 484             @Override public Void visitTypeVariable(final PsiTypeVariable var) {
 485               if (var.getIndex() == index) {
 486                 myFlag = true;
 487               }
 488
 489               return null;
 490             }
 491           }
 492
 493           final Verifier verifier = new Verifier();
 494
 495           type.accept(verifier);
 496
 497           if (verifier.myFlag) {
 498             myBindings.put(index, Bottom.BOTTOM);
 499             binding.myBindings.put(index, Bottom.BOTTOM);
 500           }
 501           else {
 502             binding.myBindings.put(index, type);
 503           }
 504         }
 505         else {
 506           binding.myBindings.put(index, type);
 507         }
 508       }
 509
 510       for (final PsiTypeVariable var : myBoundVariables) {
 511         final int index = var.getIndex();
 512         final PsiType type = myBindings.get(index);
 513
 514         if (type != null) {
 515           myBindings.put(index, binding.apply(type));
 516         }
 517       }
 518
 519       return this;
 520     }
 521
 522     public boolean binds(final PsiTypeVariable var) {
 523       return myBindings.get(var.getIndex()) != null;
 524     }
 525
 526     public void merge(final Binding b, final boolean removeObject) {
 527       for (final PsiTypeVariable var : b.getBoundVariables()) {
 528         final int index = var.getIndex();
 529
 530         if (myBindings.get(index) != null) {
 531           LOG.error("Oops... Binding conflict...");
 532         }
 533         else {
 534           final PsiType type = b.apply(var);
 535           final PsiClassType javaLangObject =
 536             PsiType.getJavaLangObject(PsiManager.getInstance(myProject), GlobalSearchScope.allScope(myProject));
 537
 538           if (removeObject &&
 539               javaLangObject.equals(type)) {
 540             final HashSet<PsiTypeVariable> cluster = myFactory.getClusterOf(var.getIndex());
 541
 542             if (cluster != null) {
 543               for (final PsiTypeVariable war : cluster) {
 544                 final PsiType wtype = b.apply(war);
 545
 546                 if (!javaLangObject.equals(wtype)) {
 547                   myBindings.put(index, type);
 548                   break;
 549                 }
 550               }
 551             }
 552           }
 553           else {
 554             myBindings.put(index, type);
 555           }
 556         }
 557       }
 558     }
 559
 560     public HashSet<PsiTypeVariable> getBoundVariables() {
 561       return myBoundVariables;
 562     }
 563
 564     public int getWidth() {
 565       class MyProcecure implements TObjectProcedure<PsiType> {
 566         int width = 0;
 567         public boolean execute(PsiType type) {
 568           if (substitute(type)  != null) width++;
 569           return true;
 570         }
 571
 572         public int getWidth() {
 573           return width;
 574         }
 575       }
 576
 577       MyProcecure procedure = new MyProcecure();
 578       myBindings.forEachValue(procedure);
 579       return procedure.getWidth();
 580     }
 581
 582     public boolean isValid() {
 583       for (final PsiTypeVariable var : myBoundVariables) {
 584         final PsiType type = substitute(var);
 585
 586         if (!var.isValidInContext(type)) {
 587           return false;
 588         }
 589       }
 590
 591       return true;
 592     }
 593
 594     public void addTypeVariable(final PsiTypeVariable var) {
 595       myBoundVariables.add(var);
 596     }
 597
 598     public PsiType substitute(final PsiType t) {
 599       if (t instanceof PsiWildcardType) {
 600         final PsiWildcardType wcType = (PsiWildcardType)t;
 601         final PsiType bound = wcType.getBound();
 602
 603         if (bound == null) {
 604           return t;
 605         }
 606
 607         final PsiManager manager = PsiManager.getInstance(myProject);
 608         final PsiType subst = substitute(bound);
 609         if (subst == null) return null;
 610         return subst instanceof PsiWildcardType ? subst : wcType.isExtends()
 611                                                           ? PsiWildcardType.createExtends(manager, subst)
 612                                                           : PsiWildcardType.createSuper(manager, subst);
 613       }
 614       else if (t instanceof PsiTypeVariable) {
 615         final PsiType b = apply(t);
 616
 617         if (b instanceof Bottom || b instanceof PsiTypeVariable) {
 618           return null;
 619         }
 620
 621         return substitute(b);
 622       }
 623       else if (t instanceof Bottom) {
 624         return null;
 625       }
 626       else if (t instanceof PsiArrayType) {
 627         return substitute(((PsiArrayType)t).getComponentType()).createArrayType();
 628       }
 629       else if (t instanceof PsiClassType) {
 630         final PsiClassType.ClassResolveResult result = ((PsiClassType)t).resolveGenerics();
 631
 632         final PsiClass aClass = result.getElement();
 633         final PsiSubstitutor aSubst = result.getSubstitutor();
 634
 635         if (aClass != null) {
 636           PsiSubstitutor theSubst = PsiSubstitutor.EMPTY;
 637
 638           for (final PsiTypeParameter parm : aSubst.getSubstitutionMap().keySet()) {
 639             final PsiType type = aSubst.substitute(parm);
 640
 641             theSubst = theSubst.put(parm, substitute(type));
 642           }
 643
 644           return JavaPsiFacade.getInstance(aClass.getProject()).getElementFactory().createType(aClass, theSubst);
 645         }
 646       }
 647       return t;
 648     }
 649   }
 650
 651   interface Balancer {
 652     Binding varType(PsiTypeVariable x, PsiType y);
 653
 654     Binding varVar(PsiTypeVariable x, PsiTypeVariable y);
 655
 656     Binding typeVar(PsiType x, PsiTypeVariable y);
 657   }
 658
 659   interface Unifier {
 660     Binding unify(PsiType x, PsiType y);
 661   }
 662
 663   public Binding balance(final PsiType x, final PsiType y, final Balancer balancer, final HashSet<Constraint> constraints) {
 664     final int indicator = (x instanceof PsiTypeVariable ? 1 : 0) + (y instanceof PsiTypeVariable ? 2 : 0);
 665
 666     switch (indicator) {
 667     case 0:
 668          if (x instanceof PsiWildcardType || y instanceof PsiWildcardType) {
 669            final PsiType xType = x instanceof PsiWildcardType ? ((PsiWildcardType)x).getBound() : x;
 670            final PsiType yType = y instanceof PsiWildcardType ? ((PsiWildcardType)y).getBound() : y;
 671
 672            switch ((x instanceof PsiWildcardType ? 1 : 0) + (y instanceof PsiWildcardType ? 2 : 0)) {
 673            case 1:
 674                 if (((PsiWildcardType)x).isExtends()) {
 675                   /* ? extends T1, T2 */
 676                   return null;
 677                 }
 678                 else {
 679                   /* ? super T1, T2 */
 680                   if (xType != null && !"java.lang.Object".equals(xType.getCanonicalText())) {
 681                     return null;
 682                   }
 683                   return create();
 684                 }
 685
 686            case 2:
 687                 if (((PsiWildcardType)y).isExtends()) {
 688                   /* T1, ? extends T2 */
 689                  if (yType instanceof PsiTypeVariable) {
 690                    final PsiTypeVariable beta = myFactory.create();
 691
 692                    if (constraints != null) {
 693                      constraints.add (new Subtype(beta, yType));
 694                      if (x != null) {
 695                        constraints.add (new Subtype(x, yType));
 696                      }
 697                    }
 698
 699                    return create ();
 700                   }
 701                   else {
 702                     if (constraints != null && xType != null && yType != null) {
 703                       constraints.add(new Subtype(xType, yType));
 704                     }
 705
 706                     return balance(xType, yType, balancer, constraints);
 707                   }
 708                 }
 709                 else {/* T1, ? super T2 */
 710                   if (yType instanceof PsiTypeVariable) {
 711                     final PsiTypeVariable beta = myFactory.create();
 712
 713                     if (constraints != null) {
 714                       if (x != null) constraints.add (new Subtype(x, beta));
 715                       constraints.add (new Subtype(yType, beta));
 716                     }
 717
 718                     return create();
 719                   }
 720                   else {
 721                     if (constraints != null && yType != null && xType != null) {
 722                       constraints.add(new Subtype(yType, xType));
 723                     }
 724
 725                     return balance(xType, yType, balancer, constraints);
 726                   }
 727                 }
 728
 729            case 3:
 730                 switch ((((PsiWildcardType)x).isExtends() ? 0 : 1) + (((PsiWildcardType)y).isExtends() ? 0 : 2)) {
 731                 case 0: /* ? super T1, ? super T2 */
 732                      if (constraints != null && xType != null && yType != null) {
 733                        constraints.add(new Subtype(yType, xType));
 734                      }
 735                      return balance(xType, yType, balancer, constraints);
 736
 737                 case 1: /* ? extends T1, ? super T2 */
 738                      if (constraints != null && xType != null && yType != null) {
 739                        constraints.add(new Subtype(xType, yType));
 740                      }
 741                      return balance(xType, yType, balancer, constraints);
 742
 743                 case 2: /* ? super T1, ? extends T2*/
 744                      return null;
 745
 746                 case 3: /* ? extends T1, ? extends T2*/
 747                      if (constraints != null && xType != null && yType != null) {
 748                        constraints.add(new Subtype(xType, yType));
 749                      }
 750                      return balance(xType, yType, balancer, constraints);
 751                 }
 752            }
 753
 754            return create();
 755          }
 756          else if (x instanceof PsiArrayType || y instanceof PsiArrayType) {
 757            final PsiType xType = x instanceof PsiArrayType ? ((PsiArrayType)x).getComponentType() : x;
 758            final PsiType yType = y instanceof PsiArrayType ? ((PsiArrayType)y).getComponentType() : y;
 759
 760            return balance(xType, yType, balancer, constraints);
 761          }
 762          else if (x instanceof PsiClassType && y instanceof PsiClassType) {
 763            final PsiClassType.ClassResolveResult resultX = Util.resolveType(x);
 764            final PsiClassType.ClassResolveResult resultY = Util.resolveType(y);
 765
 766            final PsiClass xClass = resultX.getElement();
 767            final PsiClass yClass = resultY.getElement();
 768
 769            if (xClass != null && yClass != null) {
 770              final PsiSubstitutor ySubst = resultY.getSubstitutor();
 771
 772              PsiSubstitutor xSubst = TypeConversionUtil.getClassSubstitutor(yClass, xClass, resultX.getSubstitutor());
 773              if (xSubst == null) return null;
 774
 775              Binding b = create();
 776
 777              for (final PsiTypeParameter aParm : xSubst.getSubstitutionMap().keySet()) {
 778                final PsiType xType = xSubst.substitute(aParm);
 779                final PsiType yType = ySubst.substitute(aParm);
 780
 781                final Binding b1 = unify(xType, yType, new Unifier() {
 782                  public Binding unify(final PsiType x, final PsiType y) {
 783                    return balance(x, y, balancer, constraints);
 784                  }
 785                });
 786
 787                if (b1 == null) {
 788                  return null;
 789                }
 790
 791                b = b.compose(b1);
 792              }
 793
 794              return b;
 795            }
 796          }
 797          else if (y instanceof Bottom) {
 798            return create();
 799          }
 800          else {
 801            return null;
 802          }
 803     break;
 804
 805     case 1:
 806          return balancer.varType((PsiTypeVariable)x, y);
 807
 808     case 2:
 809          return balancer.typeVar(x, (PsiTypeVariable)y);
 810
 811     case 3:
 812          return balancer.varVar((PsiTypeVariable)x, (PsiTypeVariable)y);
 813     }
 814
 815     return null;
 816   }
 817
 818   private Binding unify(final PsiType x, final PsiType y, final Unifier unifier) {
 819     final int indicator = (x instanceof PsiTypeVariable ? 1 : 0) + (y instanceof PsiTypeVariable ? 2 : 0);
 820
 821     switch (indicator) {
 822     case 0:
 823            if (x instanceof PsiWildcardType || y instanceof PsiWildcardType) {
 824              return unifier.unify(x, y);
 825            }
 826            else if (x instanceof PsiArrayType || y instanceof PsiArrayType) {
 827              final PsiType xType = x instanceof PsiArrayType ? ((PsiArrayType)x).getComponentType() : x;
 828              final PsiType yType = y instanceof PsiArrayType ? ((PsiArrayType)y).getComponentType() : y;
 829
 830              return unify(xType, yType, unifier);
 831            }
 832            else if (x instanceof PsiClassType && y instanceof PsiClassType) {
 833              final PsiClassType.ClassResolveResult resultX = Util.resolveType(x);
 834              final PsiClassType.ClassResolveResult resultY = Util.resolveType(y);
 835
 836              final PsiClass xClass = resultX.getElement();
 837              final PsiClass yClass = resultY.getElement();
 838
 839              if (xClass != null && yClass != null) {
 840                final PsiSubstitutor ySubst = resultY.getSubstitutor();
 841
 842                final PsiSubstitutor xSubst = resultX.getSubstitutor();
 843
 844                if (!xClass.equals(yClass)) {
 845                  return null;
 846                }
 847
 848                Binding b = create();
 849
 850                for (final PsiTypeParameter aParm : xSubst.getSubstitutionMap().keySet()) {
 851                  final PsiType xType = xSubst.substitute(aParm);
 852                  final PsiType yType = ySubst.substitute(aParm);
 853
 854                  final Binding b1 = unify(xType, yType, unifier);
 855
 856                  if (b1 == null) {
 857                    return null;
 858                  }
 859
 860                  b = b.compose(b1);
 861                }
 862
 863                return b;
 864              }
 865            }
 866            else if (y instanceof Bottom) {
 867              return create();
 868            }
 869            else {
 870              return null;
 871            }
 872
 873     default:
 874            return unifier.unify(x, y);
 875     }
 876   }
 877
 878   public Binding riseWithWildcard(final PsiType x, final PsiType y, final HashSet<Constraint> constraints) {
 879     final Binding binding = balance(x, y, new Balancer() {
 880                                       public Binding varType(final PsiTypeVariable x, final PsiType y) {
 881                                         if (y instanceof Bottom) {
 882                                           return create();
 883                                         }
 884
 885                                         if (y == null || y instanceof PsiWildcardType) {
 886                                           return null;
 887                                         }
 888
 889                                         final PsiTypeVariable var = myFactory.create();
 890                                         final Binding binding =
 891                                         create(x, PsiWildcardType.createSuper(PsiManager.getInstance(myProject), var));
 892
 893                                         binding.addTypeVariable(var);
 894                                         constraints.add(new Subtype(var, y));
 895
 896                                         return binding;
 897                                       }
 898
 899                                       public Binding varVar(final PsiTypeVariable x, final PsiTypeVariable y) {
 900                                         final int xi = x.getIndex();
 901                                         final int yi = y.getIndex();
 902
 903                                         if (xi == yi)
 904                                           return create ();
 905
 906                                         return create (y, PsiWildcardType.createExtends(PsiManager.getInstance(myProject), x));
 907                                         /* if (xi < yi) {
 908                                          return create(x, y);
 909                                        }
 910                                        else if (yi < xi) {
 911                                          return create(y, x);
 912                                        }
 913                                        else {
 914                                          return create();
 915                                        } */
 916                                       }
 917
 918                                       public Binding typeVar(final PsiType x, final PsiTypeVariable y) {
 919                                         if (x == null) {
 920                                           return create(y, Bottom.BOTTOM);
 921                                         }
 922
 923                                         if (x instanceof PsiWildcardType) {
 924                                           return null;
 925                                         }
 926
 927                                         final PsiTypeVariable var = myFactory.create();
 928                                         final Binding binding =
 929                                         create(y, PsiWildcardType.createExtends(PsiManager.getInstance(myProject), var));
 930
 931                                         binding.addTypeVariable(var);
 932                                         constraints.add(new Subtype(x, var));
 933
 934                                         return binding;
 935                                       }
 936                                     }, constraints);
 937
 938     return binding != null ? binding.reduceRecursive() : null;
 939   }
 940
 941   public Binding rise(final PsiType x, final PsiType y, final HashSet<Constraint> constraints) {
 942     final Binding binding = balance(x, y, new Balancer() {
 943                                       public Binding varType(final PsiTypeVariable x, final PsiType y) {
 944                                         if (y instanceof Bottom || y instanceof PsiWildcardType) {
 945                                           return create();
 946                                         }
 947
 948                                         return create(x, y);
 949                                       }
 950
 951                                       public Binding varVar(final PsiTypeVariable x, final PsiTypeVariable y) {
 952                                         final int xi = x.getIndex();
 953                                         final int yi = y.getIndex();
 954
 955                                         if (xi < yi) {
 956                                           return create(x, y);
 957                                         }
 958                                         else if (yi < xi) {
 959                                           return create(y, x);
 960                                         }
 961                                         else {
 962                                           return create();
 963                                         }
 964                                       }
 965
 966                                       public Binding typeVar(final PsiType x, final PsiTypeVariable y) {
 967                                         if (x == null) return create(y, Bottom.BOTTOM);
 968                                         if (x instanceof PsiWildcardType) return create();
 969
 970                                         return create(y, x);
 971                                       }
 972                                     }, constraints);
 973
 974     return binding != null ? binding.reduceRecursive() : null;
 975   }
 976
 977   public Binding sink(final PsiType x, final PsiType y, final HashSet<Constraint> constraints) {
 978     return balance(x, y, new Balancer() {
 979                      public Binding varType(final PsiTypeVariable x, final PsiType y) {
 980                        return create(x, y);
 981                      }
 982
 983                      public Binding varVar(final PsiTypeVariable x, final PsiTypeVariable y) {
 984                        return create(y, Bottom.BOTTOM);
 985                      }
 986
 987                      public Binding typeVar(final PsiType x, final PsiTypeVariable y) {
 988                        return create(y, Bottom.BOTTOM);
 989                      }
 990                    }, constraints);
 991   }
 992
 993   public LinkedList<Pair<PsiType, Binding>> union(final PsiType x, final PsiType y) {
 994     final LinkedList<Pair<PsiType, Binding>> list = new LinkedList<Pair<PsiType, Binding>>();
 995
 996     new Object() {
 997       void union(final PsiType x, final PsiType y, final LinkedList<Pair<PsiType, Binding>> list) {
 998         if (x instanceof PsiArrayType && y instanceof PsiArrayType) {
 999           union(((PsiArrayType)x).getComponentType(), ((PsiArrayType)y).getComponentType(), list);
1000         }
1001         else if (x instanceof PsiClassType && y instanceof PsiClassType) {
1002           final PsiClassType.ClassResolveResult xResult = Util.resolveType(x);
1003           final PsiClassType.ClassResolveResult yResult = Util.resolveType(y);
1004
1005           final PsiClass xClass = xResult.getElement();
1006           final PsiClass yClass = yResult.getElement();
1007
1008           final PsiSubstitutor xSubst = xResult.getSubstitutor();
1009           final PsiSubstitutor ySubst = yResult.getSubstitutor();
1010
1011           if (xClass == null || yClass == null) {
1012             return;
1013           }
1014
1015           if (xClass.equals(yClass)) {
1016             final Binding risen = rise(x, y, null);
1017
1018             if (risen == null) {
1019               return;
1020             }
1021
1022             list.addFirst(new Pair<PsiType, Binding>(risen.apply(x), risen));
1023           }
1024           else {
1025             final PsiClass[] descendants = getGreatestLowerClasses(xClass, yClass);
1026
1027             for (final PsiClass descendant : descendants) {
1028               final PsiSubstitutor x2aSubst = TypeConversionUtil.getClassSubstitutor(xClass, descendant, xSubst);
1029               final PsiSubstitutor y2aSubst = TypeConversionUtil.getClassSubstitutor(yClass, descendant, ySubst);
1030               LOG.assertTrue(x2aSubst != null && y2aSubst != null);
1031
1032               final PsiElementFactory factory = JavaPsiFacade.getInstance(xClass.getProject()).getElementFactory();
1033
1034               union(factory.createType(descendant, x2aSubst), factory.createType(descendant, y2aSubst), list);
1035             }
1036           }
1037         }
1038       }
1039     }.union(x, y, list);
1040
1041     return list;
1042   }
1043
1044   public LinkedList<Pair<PsiType, Binding>> intersect(final PsiType x, final PsiType y) {
1045     final LinkedList<Pair<PsiType, Binding>> list = new LinkedList<Pair<PsiType, Binding>>();
1046
1047     new Object() {
1048       void intersect(final PsiType x, final PsiType y, final LinkedList<Pair<PsiType, Binding>> list) {
1049         if (x instanceof PsiWildcardType || y instanceof PsiWildcardType) {
1050           final PsiType xType = x instanceof PsiWildcardType ? ((PsiWildcardType)x).getBound() : x;
1051           final PsiType yType = y instanceof PsiWildcardType ? ((PsiWildcardType)y).getBound() : y;
1052
1053           intersect(xType, yType, list);
1054         }
1055         if (x instanceof PsiArrayType || y instanceof PsiArrayType) {
1056           if (x instanceof PsiClassType || y instanceof PsiClassType) {
1057             try {
1058               final PsiElementFactory f = JavaPsiFacade.getInstance(myProject).getElementFactory();
1059               final PsiType keyType = x instanceof PsiClassType ? x : y;
1060
1061               final PsiType object = f.createTypeFromText("java.lang.Object", null);
1062               final PsiType cloneable = f.createTypeFromText("java.lang.Cloneable", null);
1063               final PsiType serializable = f.createTypeFromText("java.io.Serializable", null);
1064
1065               intersect(keyType, object, list);
1066               intersect(keyType, cloneable, list);
1067               intersect(keyType, serializable, list);
1068             }
1069             catch (IncorrectOperationException e) {
1070               LOG.error("Exception " + e);
1071             }
1072           }
1073           else if (x instanceof PsiArrayType && y instanceof PsiArrayType) {
1074             intersect(((PsiArrayType)x).getComponentType(), ((PsiArrayType)y).getComponentType(), list);
1075           }
1076         }
1077         else if (x instanceof PsiClassType && y instanceof PsiClassType) {
1078           final PsiClassType.ClassResolveResult xResult = Util.resolveType(x);
1079           final PsiClassType.ClassResolveResult yResult = Util.resolveType(y);
1080
1081           final PsiClass xClass = xResult.getElement();
1082           final PsiClass yClass = yResult.getElement();
1083
1084           final PsiSubstitutor xSubst = xResult.getSubstitutor();
1085           final PsiSubstitutor ySubst = yResult.getSubstitutor();
1086
1087           if (xClass == null || yClass == null) {
1088             return;
1089           }
1090
1091           if (xClass.equals(yClass)) {
1092             final Binding risen = rise(x, y, null);
1093
1094             if (risen == null) {
1095               final PsiElementFactory factory = JavaPsiFacade.getInstance(xClass.getProject()).getElementFactory();
1096
1097               list.addFirst(new Pair<PsiType, Binding>(Util.banalize(factory.createType(xClass, factory.createRawSubstitutor(xClass))),
1098                                                        create()));
1099             }
1100             else {
1101               list.addFirst(new Pair<PsiType, Binding>(risen.apply(x), risen));
1102             }
1103           }
1104           else {
1105             final PsiClass[] ancestors = GenericsUtil.getLeastUpperClasses(xClass, yClass);
1106
1107             for (final PsiClass ancestor : ancestors) {
1108               if ("java.lang.Object".equals(ancestor.getQualifiedName()) && ancestors.length > 1) {
1109                 continue;
1110               }
1111
1112               final PsiSubstitutor x2aSubst = TypeConversionUtil.getSuperClassSubstitutor(ancestor, xClass, xSubst);
1113               final PsiSubstitutor y2aSubst = TypeConversionUtil.getSuperClassSubstitutor(ancestor, yClass, ySubst);
1114
1115               final PsiElementFactory factory = JavaPsiFacade.getInstance(xClass.getProject()).getElementFactory();
1116
1117               intersect(factory.createType(ancestor, x2aSubst), factory.createType(ancestor, y2aSubst), list);
1118             }
1119           }
1120         }
1121       }
1122     }.intersect(x, y, list);
1123
1124     return list;
1125   }
1126
1127   public BindingFactory(final ReductionSystem system) {
1128     myBoundVariables = system.getBoundVariables();
1129     myProject = system.getProject();
1130     myFactory = system.getVariableFactory();
1131   }
1132
1133   public Binding create(final PsiTypeVariable var, final PsiType type) {
1134     return new BindingImpl(var, type);
1135   }
1136
1137   public Binding create() {
1138     return new BindingImpl();
1139   }
1140
1141   public HashSet<PsiTypeVariable> getBoundVariables() {
1142     return myBoundVariables;
1143   }
1144 }