java/java-impl/src/com/intellij/refactoring/typeCook/deductive/resolver/ResolverTree.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.util.PsiUtil;
  24 import com.intellij.psi.util.TypeConversionUtil;
  25 import com.intellij.refactoring.typeCook.Settings;
  26 import com.intellij.refactoring.typeCook.Util;
  27 import com.intellij.refactoring.typeCook.deductive.PsiExtendedTypeVisitor;
  28 import com.intellij.refactoring.typeCook.deductive.builder.Constraint;
  29 import com.intellij.refactoring.typeCook.deductive.builder.ReductionSystem;
  30 import com.intellij.refactoring.typeCook.deductive.builder.Subtype;
  31 import com.intellij.util.graph.DFSTBuilder;
  32 import com.intellij.util.graph.Graph;
  33 import gnu.trove.TIntArrayList;
  34 import gnu.trove.TIntProcedure;
  35 import gnu.trove.TObjectIntHashMap;
  36
  37 import java.util.*;
  38
  39 /**
  40  * @author db
  41  */
  42 public class ResolverTree {
  43   private static final Logger LOG = Logger.getInstance("#com.intellij.refactoring.typeCook.deductive.resolver.ResolverTree");
  44
  45   private ResolverTree[] mySons = new ResolverTree[0];
  46   private final BindingFactory myBindingFactory;
  47   private Binding myCurrentBinding;
  48   private final SolutionHolder mySolutions;
  49   private final Project myProject;
  50   private final TObjectIntHashMap<PsiTypeVariable> myBindingDegree; //How many times this type variable is bound in the system
  51   private final Settings mySettings;
  52   private boolean mySolutionFound = false;
  53
  54   private HashSet<Constraint> myConstraints;
  55
  56   public ResolverTree(final ReductionSystem system) {
  57     myBindingFactory = new BindingFactory(system);
  58     mySolutions = new SolutionHolder();
  59     myCurrentBinding = myBindingFactory.create();
  60     myConstraints = system.getConstraints();
  61     myProject = system.getProject();
  62     myBindingDegree = calculateDegree();
  63     mySettings = system.getSettings();
  64
  65     reduceCyclicVariables();
  66   }
  67
  68   private ResolverTree(final ResolverTree parent, final HashSet<Constraint> constraints, final Binding binding) {
  69     myBindingFactory = parent.myBindingFactory;
  70     myCurrentBinding = binding;
  71     mySolutions = parent.mySolutions;
  72     myConstraints = constraints;
  73     myProject = parent.myProject;
  74     myBindingDegree = calculateDegree();
  75     mySettings = parent.mySettings;
  76   }
  77
  78   private static class PsiTypeVarCollector extends PsiExtendedTypeVisitor {
  79     final HashSet<PsiTypeVariable> mySet = new HashSet<PsiTypeVariable>();
  80
  81     public Object visitTypeVariable(final PsiTypeVariable var) {
  82       mySet.add(var);
  83
  84       return null;
  85     }
  86
  87     public HashSet<PsiTypeVariable> getSet(final PsiType type) {
  88       type.accept(this);
  89       return mySet;
  90     }
  91   }
  92
  93   private boolean isBoundElseWhere(final PsiTypeVariable var) {
  94     return myBindingDegree.get(var) != 1;
  95   }
  96
  97   private boolean canBePruned(final Binding b) {
  98     if (mySettings.exhaustive()) return false;
  99     for (final PsiTypeVariable var : b.getBoundVariables()) {
 100       final PsiType type = b.apply(var);
 101
 102       if (!(type instanceof PsiTypeVariable) && isBoundElseWhere(var)) {
 103         return false;
 104       }
 105     }
 106
 107     return true;
 108   }
 109
 110   private TObjectIntHashMap<PsiTypeVariable> calculateDegree() {
 111     final TObjectIntHashMap<PsiTypeVariable> result = new TObjectIntHashMap<PsiTypeVariable>();
 112
 113     for (final Constraint constr : myConstraints) {
 114       final PsiTypeVarCollector collector = new PsiTypeVarCollector();
 115
 116       setDegree(collector.getSet(constr.getRight()), result);
 117     }
 118
 119     return result;
 120   }
 121
 122   private void setDegree(final HashSet<PsiTypeVariable> set, TObjectIntHashMap<PsiTypeVariable> result) {
 123     for (final PsiTypeVariable var : set) {
 124       result.increment(var);
 125     }
 126   }
 127
 128   private HashSet<Constraint> apply(final Binding b) {
 129     final HashSet<Constraint> result = new HashSet<Constraint>();
 130
 131     for (final Constraint constr : myConstraints) {
 132       result.add(constr.apply(b));
 133     }
 134
 135     return result;
 136   }
 137
 138   private HashSet<Constraint> apply(final Binding b, final HashSet<Constraint> additional) {
 139     final HashSet<Constraint> result = new HashSet<Constraint>();
 140
 141     for (final Constraint constr : myConstraints) {
 142       result.add(constr.apply(b));
 143     }
 144
 145     for (final Constraint constr : additional) {
 146       result.add(constr.apply(b));
 147     }
 148
 149     return result;
 150   }
 151
 152   private ResolverTree applyRule(final Binding b) {
 153     final Binding newBinding = b != null ? myCurrentBinding.compose(b) : null;
 154
 155     return newBinding == null ? null : new ResolverTree(this, apply(b), newBinding);
 156   }
 157
 158   private ResolverTree applyRule(final Binding b, final HashSet<Constraint> additional) {
 159     final Binding newBinding = b != null ? myCurrentBinding.compose(b) : null;
 160
 161     return newBinding == null ? null : new ResolverTree(this, apply(b, additional), newBinding);
 162   }
 163
 164   private void reduceCyclicVariables() {
 165     final HashSet<PsiTypeVariable> nodes = new HashSet<PsiTypeVariable>();
 166     final HashSet<Constraint> candidates = new HashSet<Constraint>();
 167
 168     final HashMap<PsiTypeVariable, HashSet<PsiTypeVariable>> ins = new HashMap<PsiTypeVariable, HashSet<PsiTypeVariable>>();
 169     final HashMap<PsiTypeVariable, HashSet<PsiTypeVariable>> outs = new HashMap<PsiTypeVariable, HashSet<PsiTypeVariable>>();
 170
 171     for (final Constraint constraint : myConstraints) {
 172       final PsiType left = constraint.getLeft();
 173       final PsiType right = constraint.getRight();
 174
 175       if (left instanceof PsiTypeVariable && right instanceof PsiTypeVariable) {
 176         final PsiTypeVariable leftVar = (PsiTypeVariable)left;
 177         final PsiTypeVariable rightVar = (PsiTypeVariable)right;
 178
 179         candidates.add(constraint);
 180
 181         nodes.add(leftVar);
 182         nodes.add(rightVar);
 183
 184         final HashSet<PsiTypeVariable> in = ins.get(leftVar);
 185         final HashSet<PsiTypeVariable> out = outs.get(rightVar);
 186
 187         if (in == null) {
 188           final HashSet<PsiTypeVariable> newIn = new HashSet<PsiTypeVariable>();
 189
 190           newIn.add(rightVar);
 191
 192           ins.put(leftVar, newIn);
 193         }
 194         else {
 195           in.add(rightVar);
 196         }
 197
 198         if (out == null) {
 199           final HashSet<PsiTypeVariable> newOut = new HashSet<PsiTypeVariable>();
 200
 201           newOut.add(leftVar);
 202
 203           outs.put(rightVar, newOut);
 204         }
 205         else {
 206           out.add(leftVar);
 207         }
 208       }
 209     }
 210
 211     final DFSTBuilder<PsiTypeVariable> dfstBuilder = new DFSTBuilder<PsiTypeVariable>(new Graph<PsiTypeVariable>() {
 212       public Collection<PsiTypeVariable> getNodes() {
 213         return nodes;
 214       }
 215
 216       public Iterator<PsiTypeVariable> getIn(final PsiTypeVariable n) {
 217         final HashSet<PsiTypeVariable> in = ins.get(n);
 218
 219         if (in == null) {
 220           return new HashSet<PsiTypeVariable>().iterator();
 221         }
 222
 223         return in.iterator();
 224       }
 225
 226       public Iterator<PsiTypeVariable> getOut(final PsiTypeVariable n) {
 227         final HashSet<PsiTypeVariable> out = outs.get(n);
 228
 229         if (out == null) {
 230           return new HashSet<PsiTypeVariable>().iterator();
 231         }
 232
 233         return out.iterator();
 234       }
 235
 236     });
 237
 238     final TIntArrayList sccs = dfstBuilder.getSCCs();
 239     final HashMap<PsiTypeVariable, Integer> index = new HashMap<PsiTypeVariable, Integer>();
 240
 241     sccs.forEach(new TIntProcedure() {
 242       int myTNumber = 0;
 243
 244       public boolean execute(int size) {
 245         for (int j = 0; j < size; j++) {
 246           index.put(dfstBuilder.getNodeByTNumber(myTNumber + j), myTNumber);
 247         }
 248         myTNumber += size;
 249         return true;
 250       }
 251     });
 252
 253     for (final Constraint constraint : candidates) {
 254       if (index.get(constraint.getLeft()).equals(index.get(constraint.getRight()))) {
 255         myConstraints.remove(constraint);
 256       }
 257     }
 258
 259     Binding binding = myBindingFactory.create();
 260
 261     for (final PsiTypeVariable fromVar : index.keySet()) {
 262       final PsiTypeVariable toVar = dfstBuilder.getNodeByNNumber(index.get(fromVar).intValue());
 263
 264       if (!fromVar.equals(toVar)) {
 265         binding = binding.compose(myBindingFactory.create(fromVar, toVar));
 266
 267         if (binding == null) {
 268           break;
 269         }
 270       }
 271     }
 272
 273     if (binding != null && binding.nonEmpty()) {
 274       myCurrentBinding = myCurrentBinding.compose(binding);
 275       myConstraints = apply(binding);
 276     }
 277   }
 278
 279   private void reduceTypeType(final Constraint constr) {
 280     final PsiType left = constr.getLeft();
 281     final PsiType right = constr.getRight();
 282     final HashSet<Constraint> addendumRise = new HashSet<Constraint>();
 283     final HashSet<Constraint> addendumSink = new HashSet<Constraint>();
 284     final HashSet<Constraint> addendumWcrd = new HashSet<Constraint>();
 285
 286     int numSons = 0;
 287     Binding riseBinding = myBindingFactory.rise(left, right, addendumRise);
 288     if (riseBinding != null) numSons++;
 289     Binding sinkBinding = myBindingFactory.sink(left, right, addendumSink);
 290     if (sinkBinding != null) numSons++;
 291     Binding wcrdBinding = mySettings.cookToWildcards() ? myBindingFactory.riseWithWildcard(left, right, addendumWcrd) : null;
 292     if (wcrdBinding != null) numSons++;
 293     Binding omitBinding = null;
 294
 295     if (mySettings.exhaustive()) {
 296       final PsiClassType.ClassResolveResult rightResult = Util.resolveType(right);
 297       final PsiClassType.ClassResolveResult leftResult = Util.resolveType(left);
 298
 299       final PsiClass rightClass = rightResult.getElement();
 300       final PsiClass leftClass = leftResult.getElement();
 301
 302       if (rightClass != null && leftClass != null && rightClass.getManager().areElementsEquivalent(rightClass, leftClass)) {
 303         if (PsiUtil.typeParametersIterator(rightClass).hasNext()) {
 304           omitBinding = myBindingFactory.create();
 305           numSons++;
 306           for (PsiType type : rightResult.getSubstitutor().getSubstitutionMap().values()) {
 307             if (! (type instanceof Bottom)) {
 308               numSons--;
 309               omitBinding = null;
 310               break;
 311             }
 312           }
 313         }
 314       }
 315     }
 316
 317     if (numSons == 0) return;
 318
 319     if ((riseBinding != null && sinkBinding != null && riseBinding.equals(sinkBinding)) || canBePruned(riseBinding)) {
 320       numSons--;
 321       sinkBinding = null;
 322     }
 323
 324     if (riseBinding != null && wcrdBinding != null && riseBinding.equals(wcrdBinding)) {
 325       numSons--;
 326       wcrdBinding = null;
 327     }
 328
 329     myConstraints.remove(constr);
 330
 331     mySons = new ResolverTree[numSons];
 332
 333     int n = 0;
 334
 335     if (riseBinding != null) {
 336       mySons[n++] = applyRule(riseBinding, addendumRise);
 337     }
 338
 339     if (wcrdBinding != null) {
 340       mySons[n++] = applyRule(wcrdBinding, addendumWcrd);
 341     }
 342
 343     if (omitBinding != null) {
 344       mySons[n++] = applyRule(omitBinding, addendumWcrd);
 345     }
 346
 347     if (sinkBinding != null) {
 348       mySons[n++] = applyRule(sinkBinding, addendumSink);
 349     }
 350   }
 351
 352   private void fillTypeRange(final PsiType lowerBound,
 353                              final PsiType upperBound,
 354                              final HashSet<PsiType> holder) {
 355     if (lowerBound instanceof PsiClassType && upperBound instanceof PsiClassType) {
 356       final PsiClassType.ClassResolveResult resultLower = ((PsiClassType)lowerBound).resolveGenerics();
 357       final PsiClassType.ClassResolveResult resultUpper = ((PsiClassType)upperBound).resolveGenerics();
 358
 359       final PsiClass lowerClass = resultLower.getElement();
 360       final PsiClass upperClass = resultUpper.getElement();
 361
 362       if (lowerClass != null && upperClass != null && !lowerClass.equals(upperClass)) {
 363         final PsiSubstitutor upperSubst = resultUpper.getSubstitutor();
 364         final PsiClass[] parents = upperClass.getSupers();
 365         final PsiElementFactory factory = JavaPsiFacade.getInstance(myProject).getElementFactory();
 366
 367         for (final PsiClass parent : parents) {
 368           final PsiSubstitutor superSubstitutor = TypeConversionUtil.getClassSubstitutor(parent, upperClass, upperSubst);
 369           if (superSubstitutor != null) {
 370             final PsiClassType type = factory.createType(parent, superSubstitutor);
 371             holder.add(type);
 372             fillTypeRange(lowerBound, type, holder);
 373           }
 374         }
 375       }
 376     }
 377     else if (lowerBound instanceof PsiArrayType && upperBound instanceof PsiArrayType) {
 378       fillTypeRange(((PsiArrayType)lowerBound).getComponentType(), ((PsiArrayType)upperBound).getComponentType(), holder);
 379     }
 380   }
 381
 382   private PsiType[] getTypeRange(final PsiType lowerBound, final PsiType upperBound) {
 383     final HashSet<PsiType> range = new HashSet<PsiType>();
 384
 385     range.add(lowerBound);
 386     range.add(upperBound);
 387
 388     fillTypeRange(lowerBound, upperBound, range);
 389
 390     return range.toArray(new PsiType[]{});
 391   }
 392
 393   private void reduceInterval(final Constraint left, final Constraint right) {
 394     final PsiType leftType = left.getLeft();
 395     final PsiType rightType = right.getRight();
 396     final PsiTypeVariable var = (PsiTypeVariable)left.getRight();
 397
 398     if (leftType.equals(rightType)) {
 399       final Binding binding = myBindingFactory.create(var, leftType);
 400
 401       myConstraints.remove(left);
 402       myConstraints.remove(right);
 403
 404       mySons = new ResolverTree[]{applyRule(binding)};
 405
 406       return;
 407     }
 408
 409     Binding riseBinding = myBindingFactory.rise(leftType, rightType, null);
 410     Binding sinkBinding = myBindingFactory.sink(leftType, rightType, null);
 411
 412     int indicator = (riseBinding == null ? 0 : 1) + (sinkBinding == null ? 0 : 1);
 413
 414     if (indicator == 0) {
 415       return;
 416     }
 417     else if ((indicator == 2 && riseBinding.equals(sinkBinding)) || canBePruned(riseBinding)) {
 418       indicator = 1;
 419       sinkBinding = null;
 420     }
 421
 422     PsiType[] riseRange = PsiType.EMPTY_ARRAY;
 423     PsiType[] sinkRange = PsiType.EMPTY_ARRAY;
 424
 425     if (riseBinding != null) {
 426       riseRange = getTypeRange(riseBinding.apply(rightType), riseBinding.apply(leftType));
 427     }
 428
 429     if (sinkBinding != null) {
 430       sinkRange = getTypeRange(sinkBinding.apply(rightType), sinkBinding.apply(leftType));
 431     }
 432
 433     if (riseRange.length + sinkRange.length > 0) {
 434       myConstraints.remove(left);
 435       myConstraints.remove(right);
 436     }
 437
 438     mySons = new ResolverTree[riseRange.length + sinkRange.length];
 439
 440     for (int i = 0; i < riseRange.length; i++) {
 441       final PsiType type = riseRange[i];
 442
 443       mySons[i] = applyRule(riseBinding.compose(myBindingFactory.create(var, type)));
 444     }
 445
 446     for (int i = 0; i < sinkRange.length; i++) {
 447       final PsiType type = sinkRange[i];
 448
 449       mySons[i + riseRange.length] = applyRule(sinkBinding.compose(myBindingFactory.create(var, type)));
 450     }
 451   }
 452
 453   private void reduce() {
 454     if (myConstraints.size() == 0) {
 455       return;
 456     }
 457
 458     if (myCurrentBinding.isCyclic()) {
 459       reduceCyclicVariables();
 460     }
 461
 462     final HashMap<PsiTypeVariable, Constraint> myTypeVarConstraints = new HashMap<PsiTypeVariable, Constraint>();
 463     final HashMap<PsiTypeVariable, Constraint> myVarTypeConstraints = new HashMap<PsiTypeVariable, Constraint>();
 464
 465     for (final Constraint constr : myConstraints) {
 466       final PsiType left = constr.getLeft();
 467       final PsiType right = constr.getRight();
 468
 469       switch ((left instanceof PsiTypeVariable ? 0 : 1) + (right instanceof PsiTypeVariable ? 0 : 2)) {
 470         case 0:
 471           continue;
 472
 473         case 1:
 474           {
 475             final Constraint c = myTypeVarConstraints.get(right);
 476
 477             if (c == null) {
 478               final Constraint d = myVarTypeConstraints.get(right);
 479
 480               if (d != null) {
 481                 reduceInterval(constr, d);
 482                 return;
 483               }
 484
 485               myTypeVarConstraints.put((PsiTypeVariable)right, constr);
 486             }
 487             else {
 488               reduceTypeVar(constr, c);
 489               return;
 490             }
 491           }
 492           break;
 493
 494         case 2:
 495         {
 496           final Constraint c = myVarTypeConstraints.get(left);
 497
 498           if (c == null) {
 499             final Constraint d = myTypeVarConstraints.get(left);
 500
 501             if (d != null) {
 502               reduceInterval(d, constr);
 503               return;
 504             }
 505
 506             myVarTypeConstraints.put((PsiTypeVariable)left, constr);
 507           }
 508           else {
 509             reduceVarType(constr, c);
 510             return;
 511           }
 512           break;
 513         }
 514
 515         case 3:
 516           reduceTypeType(constr);
 517           return;
 518       }
 519     }
 520
 521     //T1 < a < b ... < T2
 522     {
 523       for (final Constraint constr : myConstraints) {
 524         final PsiType left = constr.getLeft();
 525         final PsiType right = constr.getRight();
 526
 527         if (!(left instanceof PsiTypeVariable) && right instanceof PsiTypeVariable) {
 528           final HashSet<PsiTypeVariable> bound = new PsiTypeVarCollector().getSet(left);
 529
 530           if (bound.contains(right)) {
 531             myConstraints.remove(constr);
 532             mySons = new ResolverTree[]{applyRule(myBindingFactory.create(((PsiTypeVariable)right), Bottom.BOTTOM))};
 533
 534             return;
 535           }
 536
 537           final PsiManager manager = PsiManager.getInstance(myProject);
 538           final PsiType leftType = left instanceof PsiWildcardType ? ((PsiWildcardType)left).getBound() : left;
 539           final PsiType[] types = getTypeRange(PsiType.getJavaLangObject(manager, GlobalSearchScope.allScope(myProject)), leftType);
 540
 541           mySons = new ResolverTree[types.length];
 542
 543           if (types.length > 0) {
 544             myConstraints.remove(constr);
 545           }
 546
 547           for (int i = 0; i < types.length; i++) {
 548             final PsiType type = types[i];
 549             mySons[i] = applyRule(myBindingFactory.create(((PsiTypeVariable)right), type));
 550           }
 551
 552           return;
 553         }
 554       }
 555     }
 556
 557     //T1 < a < b < ...
 558     {
 559       final HashSet<PsiTypeVariable> haveLeftBound = new HashSet<PsiTypeVariable>();
 560
 561       Constraint target = null;
 562       final HashSet<PsiTypeVariable> boundVariables = new HashSet<PsiTypeVariable>();
 563
 564       for (final Constraint constr : myConstraints) {
 565         final PsiType leftType = constr.getLeft();
 566         final PsiType rightType = constr.getRight();
 567
 568         if (leftType instanceof PsiTypeVariable) {
 569           boundVariables.add((PsiTypeVariable)leftType);
 570
 571           if (rightType instanceof PsiTypeVariable) {
 572             boundVariables.add((PsiTypeVariable)rightType);
 573             haveLeftBound.add(((PsiTypeVariable)rightType));
 574           }
 575           else if (!Util.bindsTypeVariables(rightType)) {
 576             target = constr;
 577           }
 578         }
 579       }
 580
 581       if (target == null) {
 582         if (mySettings.exhaustive()) {
 583           for (final Constraint constr : myConstraints) {
 584             final PsiType left = constr.getLeft();
 585             final PsiType right = constr.getRight();
 586
 587             PsiType[] range = null;
 588             PsiTypeVariable var = null;
 589
 590             if (left instanceof PsiTypeVariable && !(right instanceof PsiTypeVariable)) {
 591               range = getTypeRange(PsiType.getJavaLangObject(PsiManager.getInstance(myProject), GlobalSearchScope.allScope(myProject)),
 592                                    right);
 593               var = (PsiTypeVariable)left;
 594             }
 595
 596             if (range == null && right instanceof PsiTypeVariable && !(left instanceof PsiTypeVariable)) {
 597               range = new PsiType[]{right};
 598               var = (PsiTypeVariable)right;
 599             }
 600
 601             if (range != null) {
 602               mySons = new ResolverTree[range.length];
 603
 604               for (int i = 0; i < range.length; i++) {
 605                 mySons[i] = applyRule(myBindingFactory.create(var, range[i]));
 606               }
 607
 608               return;
 609             }
 610           }
 611         }
 612
 613         Binding binding = myBindingFactory.create();
 614
 615         for (final PsiTypeVariable var : myBindingFactory.getBoundVariables()) {
 616           if (!myCurrentBinding.binds(var) && !boundVariables.contains(var)) {
 617             binding = binding.compose(myBindingFactory.create(var, Bottom.BOTTOM));
 618           }
 619         }
 620
 621         if (!binding.nonEmpty()) {
 622           myConstraints.clear();
 623         }
 624
 625         mySons = new ResolverTree[]{applyRule(binding)};
 626       }
 627       else {
 628         final PsiType type = target.getRight();
 629         final PsiTypeVariable var = (PsiTypeVariable)target.getLeft();
 630
 631         final Binding binding =
 632           (haveLeftBound.contains(var) || type instanceof PsiWildcardType) || !mySettings.cookToWildcards()
 633           ? myBindingFactory.create(var, type)
 634           : myBindingFactory.create(var, PsiWildcardType.createExtends(PsiManager.getInstance(myProject), type));
 635
 636         myConstraints.remove(target);
 637
 638         mySons = new ResolverTree[]{applyRule(binding)};
 639       }
 640     }
 641   }
 642
 643   private void logSolution() {
 644     LOG.debug("Reduced system:");
 645
 646     for (final Constraint constr : myConstraints) {
 647       LOG.debug(constr.toString());
 648     }
 649
 650     LOG.debug("End of Reduced system.");
 651     LOG.debug("Reduced binding:");
 652     LOG.debug(myCurrentBinding.toString());
 653     LOG.debug("End of Reduced binding.");
 654   }
 655
 656   private interface Reducer {
 657     LinkedList<Pair<PsiType, Binding>> unify(PsiType x, PsiType y);
 658
 659     Constraint create(PsiTypeVariable var, PsiType type);
 660
 661     PsiType getType(Constraint c);
 662
 663     PsiTypeVariable getVar(Constraint c);
 664   }
 665
 666   private void reduceTypeVar(final Constraint x, final Constraint y) {
 667     reduceSideVar(x, y, new Reducer() {
 668       public LinkedList<Pair<PsiType, Binding>> unify(final PsiType x, final PsiType y) {
 669         return myBindingFactory.intersect(x, y);
 670       }
 671
 672       public Constraint create(final PsiTypeVariable var, final PsiType type) {
 673         return new Subtype(type, var);
 674       }
 675
 676       public PsiType getType(final Constraint c) {
 677         return c.getLeft();
 678       }
 679
 680       public PsiTypeVariable getVar(final Constraint c) {
 681         return (PsiTypeVariable)c.getRight();
 682       }
 683     });
 684   }
 685
 686   private void reduceVarType(final Constraint x, final Constraint y) {
 687     reduceSideVar(x, y, new Reducer() {
 688       public LinkedList<Pair<PsiType, Binding>> unify(final PsiType x, final PsiType y) {
 689         return myBindingFactory.union(x, y);
 690       }
 691
 692       public Constraint create(final PsiTypeVariable var, final PsiType type) {
 693         return new Subtype(var, type);
 694       }
 695
 696       public PsiType getType(final Constraint c) {
 697         return c.getRight();
 698       }
 699
 700       public PsiTypeVariable getVar(final Constraint c) {
 701         return (PsiTypeVariable)c.getLeft();
 702       }
 703     });
 704   }
 705
 706   private void reduceSideVar(final Constraint x, final Constraint y, final Reducer reducer) {
 707     final PsiTypeVariable var = reducer.getVar(x);
 708
 709     final PsiType xType = reducer.getType(x);
 710     final PsiType yType = reducer.getType(y);
 711
 712     final LinkedList<Pair<PsiType, Binding>> union = reducer.unify(xType, yType);
 713
 714     if (union.size() == 0) {
 715       return;
 716     }
 717
 718     myConstraints.remove(x);
 719     myConstraints.remove(y);
 720
 721     mySons = new ResolverTree[union.size()];
 722     int i = 0;
 723
 724     Constraint prev = null;
 725
 726     for (final Pair<PsiType, Binding> pair : union) {
 727       if (prev != null) {
 728         myConstraints.remove(prev);
 729       }
 730
 731       prev = reducer.create(var, pair.getFirst());
 732       myConstraints.add(prev);
 733
 734       mySons[i++] = applyRule(pair.getSecond());
 735     }
 736   }
 737
 738   public void resolve() {
 739     reduce();
 740
 741     if (mySons.length > 0) {
 742       for (int i = 0; i < mySons.length; i++) {
 743
 744         if (mySons[i] != null) {
 745           mySons[i].resolve();
 746           if (!mySettings.exhaustive() && mySettings.cookToWildcards() && mySons[i].mySolutionFound) break;
 747           mySons[i] = null;
 748         }
 749       }
 750     }
 751     else {
 752       if (myConstraints.size() == 0) {
 753         logSolution();
 754
 755         mySolutions.putSolution(myCurrentBinding);
 756         mySolutionFound = true;
 757       }
 758     }
 759   }
 760
 761   public Binding getBestSolution() {
 762     return mySolutions.getBestSolution();
 763   }
 764 }