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

   1 /*
   2  * Copyright 2000-2015 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.psi.impl.source.resolve.graphInference;
  17
  18 import com.intellij.openapi.diagnostic.Logger;
  19 import com.intellij.openapi.util.Pair;
  20 import com.intellij.openapi.util.registry.Registry;
  21 import com.intellij.psi.*;
  22 import com.intellij.psi.impl.source.resolve.graphInference.constraints.ConstraintFormula;
  23 import com.intellij.psi.impl.source.resolve.graphInference.constraints.StrictSubtypingConstraint;
  24 import com.intellij.psi.impl.source.resolve.graphInference.constraints.TypeCompatibilityConstraint;
  25 import com.intellij.psi.impl.source.resolve.graphInference.constraints.TypeEqualityConstraint;
  26 import com.intellij.psi.util.PsiUtil;
  27 import com.intellij.psi.util.TypeConversionUtil;
  28 import com.intellij.util.Processor;
  29 import com.intellij.util.containers.ContainerUtil;
  30
  31 import java.util.*;
  32
  33 /**
  34  * User: anna
  35  */
  36 public class InferenceIncorporationPhase {
  37   private static final Logger LOG = Logger.getInstance("#" + InferenceIncorporationPhase.class.getName());
  38   private final InferenceSession mySession;
  39   private final List<Pair<InferenceVariable[], PsiClassType>> myCaptures = new ArrayList<Pair<InferenceVariable[], PsiClassType>>();
  40   private final Map<InferenceVariable, Map<InferenceBound, Set<PsiType>>> myCurrentBounds =
  41     new HashMap<InferenceVariable, Map<InferenceBound, Set<PsiType>>>();
  42
  43   public InferenceIncorporationPhase(InferenceSession session) {
  44     mySession = session;
  45   }
  46
  47   public void addCapture(InferenceVariable[] typeParameters, PsiClassType rightType) {
  48     myCaptures.add(Pair.create(typeParameters, rightType));
  49   }
  50
  51   public void forgetCaptures(List<InferenceVariable> variables) {
  52     for (InferenceVariable variable : variables) {
  53       for (Iterator<Pair<InferenceVariable[], PsiClassType>> iterator = myCaptures.iterator(); iterator.hasNext(); ) {
  54         Pair<InferenceVariable[], PsiClassType> capture = iterator.next();
  55         if (isCapturedVariable(variable, capture)) {
  56           iterator.remove();
  57         }
  58       }
  59     }
  60   }
  61
  62   public boolean hasCaptureConstraints(Iterable<InferenceVariable> variables) {
  63     for (InferenceVariable variable : variables) {
  64       for (Pair<InferenceVariable[], PsiClassType> capture : myCaptures) {
  65         if (isCapturedVariable(variable, capture)) {
  66           return true;
  67         }
  68       }
  69     }
  70     return false;
  71   }
  72
  73   private static boolean isCapturedVariable(InferenceVariable variable, Pair<InferenceVariable[], PsiClassType> capture) {
  74     for (InferenceVariable capturedVariable : capture.first) {
  75       if (variable == capturedVariable){
  76         return true;
  77       }
  78     }
  79     return false;
  80   }
  81
  82   public void collectCaptureDependencies(InferenceVariable variable, Set<InferenceVariable> dependencies) {
  83     for (Pair<InferenceVariable[], PsiClassType> capture : myCaptures) {
  84       if (isCapturedVariable(variable, capture)) {
  85         mySession.collectDependencies(capture.second, dependencies);
  86         ContainerUtil.addAll(dependencies, capture.first);
  87       }
  88     }
  89   }
  90
  91   public List<Pair<InferenceVariable[], PsiClassType>> getCaptures() {
  92     return myCaptures;
  93   }
  94
  95   public boolean incorporate() {
  96     final Collection<InferenceVariable> inferenceVariables = mySession.getInferenceVariables();
  97     for (InferenceVariable inferenceVariable : inferenceVariables) {
  98       if (inferenceVariable.getInstantiation() != PsiType.NULL) continue;
  99       final Map<InferenceBound, Set<PsiType>> boundsMap = myCurrentBounds.get(inferenceVariable);
 100       if (boundsMap == null) continue;
 101       final List<PsiType> eqBounds = inferenceVariable.getBounds(InferenceBound.EQ);
 102       final List<PsiType> upperBounds = inferenceVariable.getBounds(InferenceBound.UPPER);
 103       final List<PsiType> lowerBounds = inferenceVariable.getBounds(InferenceBound.LOWER);
 104
 105       final Collection<PsiType> changedEqBounds = boundsMap.get(InferenceBound.EQ);
 106       final Collection<PsiType> changedUpperBounds = boundsMap.get(InferenceBound.UPPER);
 107       final Collection<PsiType> changedLowerBounds = boundsMap.get(InferenceBound.LOWER);
 108
 109       //no new eq constraints were added -> no new constraints could be inferred
 110       if (changedEqBounds != null) {
 111         eqEq(eqBounds, changedEqBounds);
 112       }
 113
 114       upDown(lowerBounds, changedLowerBounds, upperBounds, changedUpperBounds);
 115       upDown(eqBounds, changedEqBounds, upperBounds, changedUpperBounds);
 116       upDown(lowerBounds, changedLowerBounds, eqBounds, changedEqBounds);
 117
 118       if (changedUpperBounds != null) {
 119         upUp(upperBounds);
 120       }
 121     }
 122
 123     for (Pair<InferenceVariable[], PsiClassType> capture : myCaptures) {
 124       final PsiClassType right = capture.second;
 125       final PsiClass gClass = right.resolve();
 126       LOG.assertTrue(gClass != null);
 127       final InferenceVariable[] parameters = capture.first;
 128       PsiType[] typeArgs = right.getParameters();
 129       if (parameters.length != typeArgs.length) continue;
 130       for (int i = 0; i < typeArgs.length; i++) {
 131         final PsiType aType = typeArgs[i];
 132         final InferenceVariable inferenceVariable = parameters[i];
 133
 134         final List<PsiType> eqBounds = inferenceVariable.getBounds(InferenceBound.EQ);
 135         final List<PsiType> upperBounds = inferenceVariable.getBounds(InferenceBound.UPPER);
 136         final List<PsiType> lowerBounds = inferenceVariable.getBounds(InferenceBound.LOWER);
 137
 138         if (aType instanceof PsiWildcardType) {
 139
 140           for (PsiType eqBound : eqBounds) {
 141             if (!isInferenceVariableOrFreshTypeParameter(eqBound)) {
 142               return false;
 143             }
 144           }
 145
 146           final PsiClassType[] paramBounds = inferenceVariable.getParameter().getExtendsListTypes();
 147
 148           PsiType glb = null;
 149           for (PsiClassType paramBound : paramBounds) {
 150             if (glb == null) {
 151               glb = paramBound;
 152             }
 153             else {
 154               glb = GenericsUtil.getGreatestLowerBound(glb, paramBound);
 155             }
 156           }
 157
 158           if (!((PsiWildcardType)aType).isBounded()) {
 159
 160             for (PsiType upperBound : upperBounds) {
 161               if (glb != null && mySession.getInferenceVariable(upperBound) == null) {
 162                 addConstraint(new StrictSubtypingConstraint(upperBound, mySession.substituteWithInferenceVariables(glb)));
 163               }
 164             }
 165
 166             for (PsiType lowerBound : lowerBounds) {
 167               if (isInferenceVariableOrFreshTypeParameter(lowerBound)) {
 168                 return false;
 169               }
 170             }
 171
 172           } else if (((PsiWildcardType)aType).isExtends()) {
 173
 174             final PsiType extendsBound = ((PsiWildcardType)aType).getExtendsBound();
 175
 176             for (PsiType upperBound : upperBounds) {
 177               if (mySession.getInferenceVariable(upperBound) == null) {
 178                 if (paramBounds.length == 1 && paramBounds[0].equalsToText(CommonClassNames.JAVA_LANG_OBJECT) || paramBounds.length == 0) {
 179                   addConstraint(new StrictSubtypingConstraint(upperBound, extendsBound));
 180                 }
 181                 else if (extendsBound.equalsToText(CommonClassNames.JAVA_LANG_OBJECT) && glb != null) {
 182                   addConstraint(new StrictSubtypingConstraint(upperBound, mySession.substituteWithInferenceVariables(glb)));
 183                 }
 184               }
 185             }
 186
 187             for (PsiType lowerBound : lowerBounds) {
 188               if (isInferenceVariableOrFreshTypeParameter(lowerBound)) {
 189                 return false;
 190               }
 191             }
 192
 193           } else {
 194             LOG.assertTrue(((PsiWildcardType)aType).isSuper());
 195             final PsiType superBound = ((PsiWildcardType)aType).getSuperBound();
 196
 197             for (PsiType upperBound : upperBounds) {
 198               if (glb != null && mySession.getInferenceVariable(upperBound) == null) {
 199                 addConstraint(new StrictSubtypingConstraint(mySession.substituteWithInferenceVariables(glb), upperBound));
 200               }
 201             }
 202
 203             for (PsiType lowerBound : lowerBounds) {
 204               if (mySession.getInferenceVariable(lowerBound) == null) {
 205                 addConstraint(new StrictSubtypingConstraint(superBound, lowerBound));
 206               }
 207             }
 208           }
 209         } else {
 210           inferenceVariable.addBound(aType, InferenceBound.EQ, this);
 211         }
 212       }
 213     }
 214     return true;
 215   }
 216
 217   protected void upDown(List<PsiType> lowerBounds,
 218                         Collection<PsiType> changedLowerBounds,
 219                         List<PsiType> upperBounds,
 220                         Collection<PsiType> changedUpperBounds) {
 221     if (changedLowerBounds != null) {
 222       upDown(changedLowerBounds, upperBounds);
 223     }
 224     if (changedUpperBounds != null) {
 225       upDown(lowerBounds, changedUpperBounds);
 226     }
 227   }
 228
 229   private static Boolean isInferenceVariableOrFreshTypeParameter(PsiType eqBound) {
 230     final PsiClass psiClass = PsiUtil.resolveClassInClassTypeOnly(eqBound);
 231     if (psiClass instanceof InferenceVariable ||
 232         psiClass instanceof PsiTypeParameter && TypeConversionUtil.isFreshVariable((PsiTypeParameter)psiClass)) return true;
 233     return false;
 234   }
 235
 236   boolean isFullyIncorporated() {
 237     boolean needFurtherIncorporation = false;
 238     for (InferenceVariable inferenceVariable : mySession.getInferenceVariables()) {
 239       if (inferenceVariable.getInstantiation() != PsiType.NULL) continue;
 240       Map<InferenceBound, Set<PsiType>> boundsMap = myCurrentBounds.remove(inferenceVariable);
 241       if (boundsMap == null) continue;
 242       final Set<PsiType> upperBounds = boundsMap.get(InferenceBound.UPPER);
 243       final Set<PsiType> lowerBounds = boundsMap.get(InferenceBound.LOWER);
 244       if (upperBounds != null) {
 245         needFurtherIncorporation |= crossVariables(inferenceVariable, upperBounds, lowerBounds, InferenceBound.LOWER);
 246       }
 247       if (lowerBounds != null) {
 248         needFurtherIncorporation |= crossVariables(inferenceVariable, lowerBounds, upperBounds, InferenceBound.UPPER);
 249       }
 250     }
 251     return !needFurtherIncorporation;
 252   }
 253
 254   /**
 255    * a < b & S <: a & b <: T imply S <: b & a <: T
 256    */
 257   private boolean crossVariables(InferenceVariable inferenceVariable,
 258                                  Collection<PsiType> upperBounds,
 259                                  Collection<PsiType> lowerBounds,
 260                                  InferenceBound inferenceBound) {
 261
 262     final InferenceBound oppositeBound = inferenceBound == InferenceBound.LOWER
 263                                                            ? InferenceBound.UPPER
 264                                                            : InferenceBound.LOWER;
 265     boolean result = false;
 266     for (PsiType upperBound : upperBounds) {
 267       final InferenceVariable inferenceVar = mySession.getInferenceVariable(upperBound);
 268       if (inferenceVar != null && inferenceVariable != inferenceVar) {
 269
 270         if (lowerBounds != null) {
 271           for (PsiType lowerBound : lowerBounds) {
 272             result |= inferenceVar.addBound(lowerBound, inferenceBound, this);
 273           }
 274         }
 275
 276         for (PsiType varUpperBound : inferenceVar.getBounds(oppositeBound)) {
 277           result |= inferenceVariable.addBound(varUpperBound, oppositeBound, this);
 278         }
 279       }
 280     }
 281     return result;
 282   }
 283
 284   /**
 285    * a = S & a <: T imply S <: T
 286    *           or
 287    * a = S & T <: a imply T <: S
 288    *           or
 289    * S <: a & a <: T imply S <: T
 290    */
 291   private void upDown(Collection<PsiType> eqBounds, Collection<PsiType> upperBounds) {
 292     for (PsiType upperBound : upperBounds) {
 293       if (upperBound == null || PsiType.NULL.equals(upperBound) || upperBound instanceof PsiWildcardType) continue;
 294
 295       for (PsiType eqBound : eqBounds) {
 296         if (eqBound == null || PsiType.NULL.equals(eqBound) || eqBound instanceof PsiWildcardType) continue;
 297         if (Registry.is("javac.unchecked.subtyping.during.incorporation", true)) {
 298           if (TypeCompatibilityConstraint.isUncheckedConversion(upperBound, eqBound)) {
 299             if (PsiUtil.resolveClassInType(eqBound) instanceof PsiTypeParameter) {
 300               mySession.setErased();
 301             }
 302             continue;
 303           }
 304
 305           if (!mySession.isProperType(upperBound) &&
 306               eqBound instanceof PsiCapturedWildcardType &&
 307               TypeCompatibilityConstraint.isUncheckedConversion(upperBound, ((PsiCapturedWildcardType)eqBound).getUpperBound())) {
 308             mySession.setErased();
 309             continue;
 310           }
 311         }
 312
 313         addConstraint(new StrictSubtypingConstraint(upperBound, eqBound));
 314       }
 315     }
 316   }
 317
 318   /**
 319    * a = S & a = T imply S = T
 320    */
 321   private void eqEq(List<PsiType> eqBounds, Collection<PsiType> changedEqBounds) {
 322     for (int i = 0; i < eqBounds.size(); i++) {
 323       PsiType sBound = eqBounds.get(i);
 324       boolean changed = changedEqBounds.contains(sBound);
 325       for (int j = i + 1; j < eqBounds.size(); j++) {
 326         final PsiType tBound = eqBounds.get(j);
 327         if (changed || changedEqBounds.contains(tBound)) {
 328           addConstraint(new TypeEqualityConstraint(tBound, sBound));
 329         }
 330       }
 331     }
 332   }
 333
 334
 335   /**
 336    * If two bounds have the form α <: S and α <: T, and if for some generic class or interface, G,
 337    * there exists a supertype (4.10) of S of the form G<S1, ..., Sn> and a supertype of T of the form G<T1, ..., Tn>,
 338    * then for all i, 1 ≤ i ≤ n, if Si and Ti are types (not wildcards), the constraint ⟨Si = Ti⟩ is implied.
 339    */
 340   private boolean upUp(List<PsiType> upperBounds) {
 341     return InferenceSession.findParameterizationOfTheSameGenericClass(upperBounds, new Processor<Pair<PsiType, PsiType>>() {
 342       @Override
 343       public boolean process(Pair<PsiType, PsiType> pair) {
 344         final PsiType sType = pair.first;
 345         final PsiType tType = pair.second;
 346         if (!(sType instanceof PsiWildcardType) && !(tType instanceof PsiWildcardType) && sType != null && tType != null) {
 347           addConstraint(new TypeEqualityConstraint(sType, tType));
 348         }
 349         return false;
 350       }
 351     }) != null;
 352   }
 353
 354   private void addConstraint(ConstraintFormula constraint) {
 355     mySession.addConstraint(constraint);
 356   }
 357
 358   public void addBound(InferenceVariable variable, PsiType type, InferenceBound bound) {
 359     Map<InferenceBound, Set<PsiType>> bounds = myCurrentBounds.get(variable);
 360     if (bounds == null) {
 361       bounds = new HashMap<InferenceBound, Set<PsiType>>();
 362       myCurrentBounds.put(variable, bounds);
 363     }
 364     Set<PsiType> types = bounds.get(bound);
 365     if (types == null) {
 366       types = new LinkedHashSet<PsiType>();
 367       bounds.put(bound, types);
 368     }
 369     types.add(type);
 370   }
 371 }