1161f68490be95df8c89e04abb3e0da2fce8eeff
[idea/community.git] / java / java-impl / src / com / intellij / refactoring / typeMigration / TypeMigrationLabeler.java
1 /*
2  * Copyright 2000-2014 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.typeMigration;
17
18 import com.intellij.lang.java.JavaLanguage;
19 import com.intellij.openapi.application.ApplicationManager;
20 import com.intellij.openapi.diagnostic.Logger;
21 import com.intellij.openapi.project.Project;
22 import com.intellij.openapi.ui.Messages;
23 import com.intellij.openapi.util.Comparing;
24 import com.intellij.openapi.util.Pair;
25 import com.intellij.openapi.util.text.StringUtil;
26 import com.intellij.psi.*;
27 import com.intellij.psi.impl.PsiImplUtil;
28 import com.intellij.psi.impl.source.PsiClassReferenceType;
29 import com.intellij.psi.impl.source.PsiImmediateClassType;
30 import com.intellij.psi.javadoc.PsiDocTagValue;
31 import com.intellij.psi.search.PsiSearchScopeUtil;
32 import com.intellij.psi.search.SearchScope;
33 import com.intellij.psi.search.searches.OverridingMethodsSearch;
34 import com.intellij.psi.search.searches.ReferencesSearch;
35 import com.intellij.psi.util.PsiTreeUtil;
36 import com.intellij.psi.util.PsiUtil;
37 import com.intellij.psi.util.TypeConversionUtil;
38 import com.intellij.refactoring.typeMigration.usageInfo.OverridenUsageInfo;
39 import com.intellij.refactoring.typeMigration.usageInfo.OverriderUsageInfo;
40 import com.intellij.refactoring.typeMigration.usageInfo.TypeMigrationUsageInfo;
41 import com.intellij.refactoring.util.RefactoringUtil;
42 import com.intellij.usageView.UsageInfo;
43 import com.intellij.util.*;
44 import com.intellij.util.containers.ContainerUtil;
45 import com.intellij.util.graph.DFSTBuilder;
46 import com.intellij.util.graph.GraphGenerator;
47 import org.jetbrains.annotations.NotNull;
48 import org.jetbrains.annotations.Nullable;
49 import org.jetbrains.annotations.TestOnly;
50
51 import javax.swing.*;
52 import java.util.*;
53
54 /**
55  * @author db
56  * Date: Sep 19, 2004
57  */
58 public class TypeMigrationLabeler {
59   private static final Logger LOG = Logger.getInstance("#com.intellij.refactoring.typeMigration.TypeMigrationLabeler");
60   private boolean myShowWarning = true;
61   private MigrateException myException;
62
63   public TypeMigrationRules getRules() {
64     return myRules;
65   }
66
67   private final TypeMigrationRules myRules;
68   private TypeEvaluator myTypeEvaluator;
69   private final LinkedHashMap<PsiElement, Object> myConversions;
70   private final HashSet<Pair<SmartPsiElementPointer<PsiExpression>, PsiType>> myFailedConversions;
71   private LinkedList<Pair<TypeMigrationUsageInfo, PsiType>> myMigrationRoots;
72   private final LinkedHashMap<TypeMigrationUsageInfo, PsiType> myNewExpressionTypeChange;
73   private final LinkedHashMap<TypeMigrationUsageInfo, PsiClassType> myClassTypeArgumentsChange;
74
75   private TypeMigrationUsageInfo[] myMigratedUsages = null;
76
77   private TypeMigrationUsageInfo myCurrentRoot;
78   private final Map<TypeMigrationUsageInfo, HashSet<Pair<TypeMigrationUsageInfo, PsiType>>> myRootsTree =
79       new HashMap<TypeMigrationUsageInfo, HashSet<Pair<TypeMigrationUsageInfo, PsiType>>>();
80   private final Map<Pair<TypeMigrationUsageInfo, TypeMigrationUsageInfo>, Set<PsiElement>> myRootUsagesTree = new HashMap<Pair<TypeMigrationUsageInfo, TypeMigrationUsageInfo>, Set<PsiElement>>();
81   private final Set<TypeMigrationUsageInfo> myProcessedRoots = new HashSet<TypeMigrationUsageInfo>();
82
83
84   public TypeMigrationLabeler(final TypeMigrationRules rules) {
85     myRules = rules;
86     
87     myConversions = new LinkedHashMap<PsiElement, Object>();
88     myFailedConversions = new HashSet<Pair<SmartPsiElementPointer<PsiExpression>, PsiType>>();
89     myNewExpressionTypeChange = new LinkedHashMap<TypeMigrationUsageInfo, PsiType>();
90     myClassTypeArgumentsChange = new LinkedHashMap<TypeMigrationUsageInfo, PsiClassType>();
91   }
92
93   public boolean hasFailedConversions() {
94     return myFailedConversions.size() > 0;
95   }
96
97   public String[] getFailedConversionsReport() {
98     final String[] report = new String[myFailedConversions.size()];
99     int j = 0;
100
101     for (final Pair<SmartPsiElementPointer<PsiExpression>, PsiType> p : myFailedConversions) {
102       final PsiExpression element = p.getFirst().getElement();
103       LOG.assertTrue(element != null);
104       final PsiType type = element.getType();
105       report[j++] = "Cannot convert type of expression <b>" + StringUtil.escapeXml(element.getText()) + "</b>" +
106                     (type != null
107                      ? " from <b>" + StringUtil.escapeXml(type.getCanonicalText()) + "</b>" +
108                        " to <b>" + StringUtil.escapeXml(p.getSecond().getCanonicalText()) + "</b>"
109                      : "")
110                     + "<br>";
111     }
112
113     return report;
114   }
115
116   public UsageInfo[] getFailedUsages() {
117     final List<UsageInfo> usages = new ArrayList<UsageInfo>(myFailedConversions.size());
118     for (final Pair<SmartPsiElementPointer<PsiExpression>, PsiType> p : myFailedConversions) {
119       final PsiExpression expr = p.getFirst().getElement();
120       if (expr != null) {
121         usages.add(new UsageInfo(expr) {
122           @Nullable
123           public String getTooltipText() {
124             final PsiType type = expr.isValid() ? expr.getType() : null;
125             if (type == null) return null;
126             return "Cannot convert type of the expression from " +
127                    type.getCanonicalText() + " to " + p.getSecond().getCanonicalText();
128           }
129         });
130       }
131     }
132
133     return usages.toArray(new UsageInfo[usages.size()]);
134   }
135
136   public TypeMigrationUsageInfo[] getMigratedUsages() {
137     final LinkedList<Pair<TypeMigrationUsageInfo, PsiType>> declarations = getTypeEvaluator().getMigratedDeclarations();
138     final TypeMigrationUsageInfo[] usages = new TypeMigrationUsageInfo[declarations.size() + myConversions.size() + myNewExpressionTypeChange.size() + myClassTypeArgumentsChange.size()];
139
140     int j = 0;
141
142     for (final PsiElement element : myConversions.keySet()) {
143       final Object conv = myConversions.get(element);
144       usages[j++] = new TypeMigrationUsageInfo(element) {
145         public String getTooltipText() {
146           if (conv instanceof String) {   //todo
147             final String conversion = (String)conv;
148             return "Replaced with " + conversion.replaceAll("\\$", element.getText());
149           }
150           else {
151             return "Replaced with " + conv.toString();
152           }
153         }
154
155         @Override
156         public boolean isExcluded() {
157           if (conv instanceof TypeConversionDescriptorBase) return ((TypeConversionDescriptorBase)conv).getRoot().isExcluded();
158           return super.isExcluded();
159         }
160
161         @Override
162         public TypeMigrationUsageInfo getOwnerRoot() {
163           return conv instanceof TypeConversionDescriptorBase ? ((TypeConversionDescriptorBase)conv).getRoot() : null;
164         }
165       };
166     }
167
168     for (final Pair<TypeMigrationUsageInfo, PsiType> p : declarations) {
169       final TypeMigrationUsageInfo element = p.getFirst();
170       usages[j++] = element;
171     }
172
173     for (TypeMigrationUsageInfo info : myClassTypeArgumentsChange.keySet()) {
174       usages[j++] = info;
175     }
176
177     for (final TypeMigrationUsageInfo expr : myNewExpressionTypeChange.keySet()) {
178       usages[j++] = expr;
179     }
180     return sortMigratedUsages(usages);
181   }
182
183   private TypeMigrationUsageInfo[] sortMigratedUsages(TypeMigrationUsageInfo[] infos) {
184     final DFSTBuilder<TypeMigrationUsageInfo> builder = new DFSTBuilder<TypeMigrationUsageInfo>(GraphGenerator.create(
185       new GraphGenerator.SemiGraph<TypeMigrationUsageInfo>() {
186         @Override
187         public Collection<TypeMigrationUsageInfo> getNodes() {
188           final Set<TypeMigrationUsageInfo> infos = new HashSet<TypeMigrationUsageInfo>();
189           for (Map.Entry<TypeMigrationUsageInfo, HashSet<Pair<TypeMigrationUsageInfo, PsiType>>> entry : myRootsTree.entrySet()) {
190             infos.add(entry.getKey());
191             infos.addAll(ContainerUtil.map(entry.getValue(), new Function<Pair<TypeMigrationUsageInfo, PsiType>, TypeMigrationUsageInfo>() {
192               @Override
193               public TypeMigrationUsageInfo fun(Pair<TypeMigrationUsageInfo, PsiType> pair) {
194                 return pair.getFirst();
195               }
196             }));
197           }
198           return infos;
199         }
200
201         @Override
202         public Iterator<TypeMigrationUsageInfo> getIn(TypeMigrationUsageInfo n) {
203           final HashSet<Pair<TypeMigrationUsageInfo, PsiType>> rawNodes = myRootsTree.get(n);
204           if (rawNodes == null) {
205             return Collections.<TypeMigrationUsageInfo>emptyList().iterator();
206           }
207           final List<TypeMigrationUsageInfo> in =
208             ContainerUtil.map(rawNodes, new Function<Pair<TypeMigrationUsageInfo, PsiType>, TypeMigrationUsageInfo>() {
209               @Override
210               public TypeMigrationUsageInfo fun(Pair<TypeMigrationUsageInfo, PsiType> pair) {
211                 return pair.getFirst();
212               }
213             });
214           return in.iterator();
215         }
216       }));
217     final Comparator<TypeMigrationUsageInfo> cmp = builder.comparator();
218
219     Arrays.sort(infos, new Comparator<TypeMigrationUsageInfo>() {
220       @Override
221       public int compare(final TypeMigrationUsageInfo info1, final TypeMigrationUsageInfo info2) {
222         final TypeMigrationUsageInfo i1 = info1.getOwnerRoot();
223         final TypeMigrationUsageInfo i2 = info2.getOwnerRoot();
224         if (i1 == null && i2 == null) {
225           return 0;
226         }
227         if (i1 == null) {
228           return 1;
229         }
230         if (i2 == null) {
231           return -1;
232         }
233
234         final int res = cmp.compare(i1, i2);
235         if (res != 0) {
236           return res;
237         }
238         final PsiElement element1 = info1.getElement();
239         final PsiElement element2 = info2.getElement();
240         LOG.assertTrue(element1 != null && element2 != null);
241         return element2.getTextRange().getStartOffset() - element1.getTextRange().getStartOffset();
242       }
243     });
244
245     return infos;
246   }
247
248
249   public void change(final TypeMigrationUsageInfo usageInfo, @NotNull  Consumer<PsiNewExpression> consumer) {
250     final PsiElement element = usageInfo.getElement();
251     if (element == null) return;
252     final Project project = element.getProject();
253     if (element instanceof PsiExpression) {
254       final PsiExpression expression = (PsiExpression)element;
255       if (element instanceof PsiNewExpression) {
256         for (Map.Entry<TypeMigrationUsageInfo, PsiType> info : myNewExpressionTypeChange.entrySet()) {
257           final PsiElement expressionToReplace = info.getKey().getElement();
258           if (expression.equals(expressionToReplace)) {
259             final PsiNewExpression newExpression =
260               TypeMigrationReplacementUtil.replaceNewExpressionType(project, (PsiNewExpression)expressionToReplace, info);
261             if (newExpression != null) {
262               consumer.consume(newExpression);
263             }
264           }
265         }
266       }
267       final Object conversion = myConversions.get(element);
268       if (conversion != null) {
269         myConversions.remove(element);
270         TypeMigrationReplacementUtil.replaceExpression(expression, project, conversion);
271       }
272     } else if (element instanceof PsiReferenceParameterList) {
273       for (Map.Entry<TypeMigrationUsageInfo, PsiClassType> entry : myClassTypeArgumentsChange.entrySet()) {
274         if (element.equals(entry.getKey().getElement())) { //todo check null
275           final PsiElementFactory factory = JavaPsiFacade.getInstance(project).getElementFactory();
276           try {
277             element.getParent().replace(factory.createReferenceElementByType(entry.getValue()));
278           }
279           catch (IncorrectOperationException e) {
280             LOG.error(e);
281           }
282         }
283       }
284     }
285     else {
286       TypeMigrationReplacementUtil.migratePsiMemberType(element, project, getTypeEvaluator().getType(usageInfo));
287     }
288   }
289
290   void postProcessNewExpression(@NotNull PsiNewExpression expression) {
291     TypeMigrationReplacementUtil.tryToReplaceWithDiamond(expression, null);
292   }
293
294   @Nullable
295   Object getConversion(PsiElement element) {
296     return myConversions.get(element);
297   }
298
299   public TypeMigrationUsageInfo[] getMigratedUsages(boolean autoMigrate, final PsiElement... roots) {
300     if (myMigratedUsages == null) {
301       myShowWarning = autoMigrate;
302       migrate(autoMigrate, roots);
303       myMigratedUsages = getMigratedUsages();
304     }
305     return myMigratedUsages;
306   }
307
308   @Nullable
309   public Set<PsiElement> getTypeUsages(final TypeMigrationUsageInfo element, final TypeMigrationUsageInfo currentRoot) {
310     return myRootUsagesTree.get(Pair.create(element, currentRoot));
311   }
312
313   void convertExpression(final PsiExpression expr, final PsiType toType, final PsiType fromType, final boolean isCovariantPosition) {
314     final TypeConversionDescriptorBase conversion = myRules.findConversion(fromType, toType, expr instanceof PsiMethodCallExpression ? ((PsiMethodCallExpression)expr).resolveMethod() : null, expr,
315                                                      isCovariantPosition, this);
316
317     if (conversion == null) {
318       markFailedConversion(Pair.create(fromType, toType), expr);
319     }
320     else {
321       setConversionMapping(expr, conversion);
322     }
323   }
324
325   public void migrateExpressionType(final PsiExpression expr, final PsiType migrationType, final PsiElement place, boolean alreadyProcessed, final boolean isCovariant) {
326     PsiType originalType = expr.getType();
327
328     if (originalType == null || originalType.equals(migrationType)) return;
329
330     if (originalType.equals(PsiType.NULL)) {
331       if (migrationType instanceof PsiPrimitiveType) {
332         markFailedConversion(Pair.create(originalType, migrationType), expr);
333       }
334       return;
335     }
336
337     if (expr instanceof PsiConditionalExpression) {
338       final PsiConditionalExpression condExpr = (PsiConditionalExpression)expr;
339       for (PsiExpression e : ContainerUtil.newArrayList(condExpr.getThenExpression(), condExpr.getElseExpression())) {
340         if (e != null) {
341           migrateExpressionType(e, migrationType, place, alreadyProcessed, false);
342         }
343       }
344       getTypeEvaluator().setType(new TypeMigrationUsageInfo(expr), migrationType);
345       return;
346     } else if (expr instanceof PsiClassObjectAccessExpression) {
347       if (!TypeConversionUtil.isAssignable(migrationType, expr.getType())) {
348         markFailedConversion(Pair.create(expr.getType(), migrationType), expr);
349         return;
350       }
351     } else if (expr instanceof PsiArrayInitializerExpression && migrationType instanceof PsiArrayType) {
352       final PsiExpression[] initializers = ((PsiArrayInitializerExpression)expr).getInitializers();
353       for (PsiExpression initializer : initializers) {
354         migrateExpressionType(initializer, ((PsiArrayType)migrationType).getComponentType(), expr, alreadyProcessed, true);
355       }
356       getTypeEvaluator().setType(new TypeMigrationUsageInfo(expr), migrationType);
357       return;
358     } else if (expr instanceof PsiArrayAccessExpression) {
359       migrateExpressionType(((PsiArrayAccessExpression)expr).getArrayExpression(), migrationType.createArrayType(), place, alreadyProcessed, isCovariant);
360       return;
361     }
362     else if (expr instanceof PsiReferenceExpression) {
363       final PsiElement resolved = ((PsiReferenceExpression)expr).resolve();
364       if (resolved != null) {
365         if (!addMigrationRoot(resolved, migrationType, place, alreadyProcessed, !isCovariant)) {
366           convertExpression(expr, migrationType, getTypeEvaluator().evaluateType(expr), isCovariant);
367         }
368       }
369       return;
370     }
371     else if (expr instanceof PsiMethodCallExpression) {
372       final PsiMethod resolved = ((PsiMethodCallExpression)expr).resolveMethod();
373       if (resolved != null) {
374         if (!addMigrationRoot(resolved, migrationType, place, alreadyProcessed, !isCovariant)) {
375           convertExpression(expr, migrationType, getTypeEvaluator().evaluateType(expr), isCovariant);
376         }
377       }
378       return;
379     }
380     else if (expr instanceof PsiNewExpression) {
381       if (originalType.getArrayDimensions() == migrationType.getArrayDimensions()) {
382         if (migrationType.getArrayDimensions() > 0) {
383           final PsiType elemenType = ((PsiArrayType)migrationType).getComponentType();
384
385           final PsiArrayInitializerExpression arrayInitializer = ((PsiNewExpression)expr).getArrayInitializer();
386
387           if (arrayInitializer != null) {
388             final PsiExpression[] initializers = arrayInitializer.getInitializers();
389             for (int i = initializers.length - 1; i >= 0; i--) {
390               migrateExpressionType(initializers[i], elemenType, place, alreadyProcessed, true);
391             }
392           }
393
394           if (isGenericsArrayType(elemenType)){
395             markFailedConversion(Pair.create(originalType, migrationType), expr);
396             return;
397           }
398
399           final TypeMigrationUsageInfo usageInfo = new TypeMigrationUsageInfo(expr);
400           usageInfo.setOwnerRoot(myCurrentRoot);
401           myNewExpressionTypeChange.put(usageInfo, migrationType);
402           getTypeEvaluator().setType(new TypeMigrationUsageInfo(expr), migrationType);
403           return;
404         } else {
405           if (migrationType instanceof PsiClassType && originalType instanceof PsiClassType && ((PsiClassType)migrationType).rawType().isAssignableFrom(((PsiClassType)originalType).rawType())) {
406             final PsiClass originalClass = PsiUtil.resolveClassInType(originalType);
407             if (originalClass instanceof PsiAnonymousClass) {
408               originalType = ((PsiAnonymousClass)originalClass).getBaseClassType();
409             }
410             final PsiType type = TypeEvaluator.substituteType(migrationType, originalType, true, ((PsiClassType)originalType).resolveGenerics().getElement(),
411                                                               JavaPsiFacade.getElementFactory(expr.getProject()).createType(((PsiClassType)originalType).resolve(), PsiSubstitutor.EMPTY));
412             if (type != null){
413               final TypeMigrationUsageInfo usageInfo = new TypeMigrationUsageInfo(expr);
414               usageInfo.setOwnerRoot(myCurrentRoot);
415               myNewExpressionTypeChange.put(usageInfo, type);
416               getTypeEvaluator().setType(new TypeMigrationUsageInfo(expr), type);
417               return;
418             }
419           }
420         }
421       }
422
423     }
424     else if (expr instanceof PsiLambdaExpression) {
425       //TODO conversion of lambda expression now works incorrectly [Dmitry Batkovich]
426       return;
427     }
428
429     convertExpression(expr, migrationType, originalType, isCovariant);
430   }
431
432   private static boolean isGenericsArrayType(final PsiType elemenType) {
433     if (elemenType instanceof PsiClassType && ((PsiClassType)elemenType).hasParameters()) {
434       return true;
435     } else if (elemenType instanceof PsiArrayType) {
436       final PsiType componentType = ((PsiArrayType)elemenType).getComponentType();
437       return isGenericsArrayType(componentType);
438     }
439     return false;
440   }
441
442   boolean addMigrationRoot(PsiElement element, PsiType type, final PsiElement place, boolean alreadyProcessed, final boolean isContraVariantPosition) {
443     return addMigrationRoot(element, type, place, alreadyProcessed, isContraVariantPosition, false);
444   }
445
446   boolean addMigrationRoot(PsiElement element,
447                            PsiType type,
448                            final PsiElement place,
449                            boolean alreadyProcessed,
450                            final boolean isContraVariantPosition,
451                            final boolean userDefinedType) {
452     if (type.equals(PsiType.NULL)) {
453       return false;
454     }
455
456     final PsiElement resolved = Util.normalizeElement(element);
457
458     final SearchScope searchScope = myRules.getSearchScope();
459     if (!resolved.isPhysical() || !PsiSearchScopeUtil.isInScope(searchScope, resolved)) {
460       return false;
461     }
462
463     final PsiType originalType = getElementType(resolved);
464
465     LOG.assertTrue(originalType != null);
466
467     type = userDefinedType ? type : TypeEvaluator.substituteType(type, originalType, isContraVariantPosition);
468
469     if (!userDefinedType) {
470       final Set<PsiTypeParameter> collector;
471       if (originalType instanceof PsiClassReferenceType) {
472         collector = new HashSet<PsiTypeParameter>();
473         final PsiJavaCodeReferenceElement reference = ((PsiClassReferenceType)originalType).getReference();
474         RefactoringUtil.collectTypeParameters(collector, reference);
475       } else {
476         collector = Collections.emptySet();
477       }
478       if (typeContainsTypeParameters(originalType, collector)) return false;
479     }
480
481     if (type instanceof PsiCapturedWildcardType) {
482       return false;
483     }
484
485     if (resolved instanceof PsiMethod) {
486       final PsiMethod method = ((PsiMethod)resolved);
487
488       final PsiClass containingClass = method.getContainingClass();
489       if (containingClass instanceof PsiAnonymousClass) {
490         final HierarchicalMethodSignature signature = method.getHierarchicalMethodSignature();
491         final List<HierarchicalMethodSignature> superSignatures = signature.getSuperSignatures();
492         if (!superSignatures.isEmpty()) {
493
494           final HierarchicalMethodSignature superSignature = superSignatures.get(0);
495
496           final PsiSubstitutor substitutor = superSignature.getSubstitutor();
497           if (!substitutor.getSubstitutionMap().isEmpty()) {
498             final PsiMethod superMethod = superSignature.getMethod();
499
500             final PsiType superReturnType = superMethod.getReturnType();
501             if (superReturnType instanceof PsiClassType) {
502               final PsiClass resolvedClass = ((PsiClassType)superReturnType).resolve();
503               if (resolvedClass instanceof PsiTypeParameter) {
504                 final PsiType expectedReturnType = substitutor.substitute((PsiTypeParameter)resolvedClass);
505                 if (Comparing.equal(expectedReturnType, method.getReturnType())) {
506                   final PsiClassType baseClassType = ((PsiAnonymousClass)containingClass).getBaseClassType();
507                   final PsiClassType.ClassResolveResult result = baseClassType.resolveGenerics();
508                   final PsiClass anonymousBaseClass = result.getElement();
509
510                   final PsiSubstitutor superHierarchySubstitutor = TypeConversionUtil
511                     .getClassSubstitutor(superMethod.getContainingClass(), anonymousBaseClass, PsiSubstitutor.EMPTY);
512                   final PsiType maybeTypeParameter = superHierarchySubstitutor.substitute((PsiTypeParameter)resolvedClass);
513
514                   if (maybeTypeParameter instanceof PsiClassType &&
515                       ((PsiClassType)maybeTypeParameter).resolve() instanceof PsiTypeParameter) {
516                     final PsiSubstitutor newSubstitutor = result.getSubstitutor().put(
517                       (PsiTypeParameter)((PsiClassType)maybeTypeParameter).resolve(), type);
518                     addRoot(new TypeMigrationUsageInfo(((PsiAnonymousClass)containingClass).getBaseClassReference().getParameterList()),
519                             new PsiImmediateClassType(anonymousBaseClass, newSubstitutor),
520                             place,
521                             alreadyProcessed);
522                   }
523                 }
524               }
525             }
526           }
527         }
528       }
529
530
531       final PsiMethod[] methods = OverridingMethodsSearch.search(method, true).toArray(PsiMethod.EMPTY_ARRAY);
532       final OverridenUsageInfo overridenUsageInfo = new OverridenUsageInfo(method);
533       final OverriderUsageInfo[] overriders = new OverriderUsageInfo[methods.length];
534       for (int i = -1; i < methods.length; i++) {
535         final TypeMigrationUsageInfo m;
536         if (i < 0) {
537           m = overridenUsageInfo;
538         }
539         else {
540           overriders[i] = new OverriderUsageInfo(methods[i], method);
541           m = overriders[i];
542         }
543
544         alreadyProcessed = addRoot(m, type, place, alreadyProcessed);
545       }
546       overridenUsageInfo.setOverriders(overriders);
547
548       return !alreadyProcessed;
549     }
550     else if (resolved instanceof PsiParameter && ((PsiParameter)resolved).getDeclarationScope() instanceof PsiMethod) {
551       final PsiMethod method = (PsiMethod)((PsiParameter)resolved).getDeclarationScope();
552
553       final int index = method.getParameterList().getParameterIndex(((PsiParameter)resolved));
554       final PsiMethod[] methods = OverridingMethodsSearch.search(method, true).toArray(PsiMethod.EMPTY_ARRAY);
555
556       final OverriderUsageInfo[] overriders = new OverriderUsageInfo[methods.length];
557       final OverridenUsageInfo overridenUsageInfo = new OverridenUsageInfo(method.getParameterList().getParameters()[index]);
558       for (int i = -1; i < methods.length; i++) {
559         final PsiMethod m = i < 0 ? method : methods[i];
560         final PsiParameter p = m.getParameterList().getParameters()[index];
561         final TypeMigrationUsageInfo paramUsageInfo;
562         if (i < 0) {
563           paramUsageInfo = overridenUsageInfo;
564         }
565         else {
566           overriders[i] = new OverriderUsageInfo(p, method);
567           paramUsageInfo = overriders[i];
568         }
569         alreadyProcessed = addRoot(paramUsageInfo, type, place, alreadyProcessed);
570       }
571
572       overridenUsageInfo.setOverriders(overriders);
573
574       return !alreadyProcessed;
575     }
576     else {
577       return !addRoot(new TypeMigrationUsageInfo(resolved), type, place, alreadyProcessed);
578     }
579   }
580
581   static boolean typeContainsTypeParameters(@Nullable PsiType originalType, @NotNull Set<PsiTypeParameter> excluded) {
582     if (originalType instanceof PsiClassType) {
583       final PsiClassType psiClassType = (PsiClassType)originalType;
584       if (psiClassType.resolve() instanceof PsiTypeParameter) {
585         return true;
586       }
587       for (PsiType paramType : psiClassType.getParameters()) {
588         if (paramType instanceof PsiClassType) {
589           final PsiClass resolved = ((PsiClassType)paramType).resolve();
590           if (resolved instanceof PsiTypeParameter && !excluded.contains(resolved)) return true;
591         }
592       }
593     }
594     return false;
595   }
596
597
598   @Nullable
599   public static PsiType getElementType(final PsiElement resolved) {
600     if (resolved instanceof PsiVariable) {
601       return ((PsiVariable)resolved).getType();
602     }
603     else {
604       if (resolved instanceof PsiMethod) {
605         return (((PsiMethod)resolved).getReturnType());
606       }
607       else if (resolved instanceof PsiExpression){
608         return (((PsiExpression)resolved).getType());
609       } else if (resolved instanceof PsiReferenceParameterList) {
610         PsiElement parent = resolved.getParent();
611         while (parent != null) {
612           LOG.assertTrue(parent instanceof PsiJavaCodeReferenceElement);
613           final PsiClass psiClass = (PsiClass)((PsiJavaCodeReferenceElement)parent).resolve();
614           final PsiClass containingClass = PsiTreeUtil.getParentOfType(parent, PsiClass.class);
615           if (psiClass != null && containingClass != null) {
616            final PsiSubstitutor classSubstitutor = TypeConversionUtil.getClassSubstitutor(psiClass, containingClass, PsiSubstitutor.EMPTY);
617            if (classSubstitutor != null) {
618              return JavaPsiFacade.getElementFactory(parent.getProject()).createType(psiClass, classSubstitutor);
619            }
620           }
621           parent = PsiTreeUtil.getParentOfType(parent, PsiJavaCodeReferenceElement.class, true);
622         }
623       } else if (resolved instanceof PsiClass) {
624         return JavaPsiFacade.getElementFactory(resolved.getProject()).createType((PsiClass)resolved, PsiSubstitutor.EMPTY);
625       }
626     }
627     return null;
628   }
629
630   public void clearStopException() {
631     myException = null;
632   }
633   
634   boolean addRoot(final TypeMigrationUsageInfo usageInfo, final PsiType type, final PsiElement place, boolean alreadyProcessed) {
635     if (myShowWarning && myMigrationRoots.size() > 10 && !ApplicationManager.getApplication().isUnitTestMode()) {
636       myShowWarning = false;
637       try {
638         final Runnable checkTimeToStopRunnable = new Runnable() {
639           public void run() {
640             if (Messages.showYesNoCancelDialog("Found more than 10 roots to migrate. Do you want to preview?", "Type Migration",
641                                                Messages.getWarningIcon()) == Messages.YES) {
642               myException = new MigrateException();
643             }
644           }
645         };
646         SwingUtilities.invokeLater(checkTimeToStopRunnable);
647       }
648       catch (Exception e) {
649         //do nothing
650       }
651     }
652     if (myException != null) throw myException;
653     rememberRootTrace(usageInfo, type, place, alreadyProcessed);
654     if (!alreadyProcessed && !getTypeEvaluator().setType(usageInfo, type)) {
655       alreadyProcessed = true;
656     }
657
658     if (!alreadyProcessed) myMigrationRoots.addFirst(Pair.create(usageInfo, type));
659     return alreadyProcessed;
660   }
661
662   private void rememberRootTrace(final TypeMigrationUsageInfo usageInfo, final PsiType type, final PsiElement place, final boolean alreadyProcessed) {
663     if (myCurrentRoot != null) {
664       if (!alreadyProcessed) {
665         myProcessedRoots.add(usageInfo);
666       }
667
668       if (myProcessedRoots.contains(usageInfo)) {
669         HashSet<Pair<TypeMigrationUsageInfo, PsiType>> infos = myRootsTree.get(myCurrentRoot);
670         if (infos == null) {
671           infos = new HashSet<Pair<TypeMigrationUsageInfo, PsiType>>();
672           myRootsTree.put(myCurrentRoot, infos);
673         }
674         infos.add(Pair.create(usageInfo, type));
675       }
676       if (!(usageInfo instanceof OverriderUsageInfo)) { //hide the same usage for all overriders
677         setTypeUsage(usageInfo, place);
678       }
679     }
680   }
681
682   private void setTypeUsage(final TypeMigrationUsageInfo usageInfo, final PsiElement place) {
683     if (place != null) {
684       final Pair<TypeMigrationUsageInfo, TypeMigrationUsageInfo> rooted = Pair.create(usageInfo, myCurrentRoot);
685       Set<PsiElement> usages = myRootUsagesTree.get(rooted);
686       if (usages == null) {
687         usages = new HashSet<PsiElement>();
688         myRootUsagesTree.put(rooted, usages);
689       }
690       usages.add(place);
691     }
692   }
693   
694   public void setTypeUsage(final PsiElement element, final PsiElement place) {
695     setTypeUsage(new TypeMigrationUsageInfo(element), place);
696   }
697
698   void markFailedConversion(final Pair<PsiType, PsiType> typePair, final PsiExpression expression) {
699     LOG.assertTrue(typePair.getSecond() != null);
700     myFailedConversions.add(Pair.create(SmartPointerManager.getInstance(expression.getProject()).createSmartPsiElementPointer(expression), typePair.getSecond()));
701   }
702
703   void setConversionMapping(final PsiExpression expression, final Object obj) {
704     if (myConversions.get(expression) != null) {
705       return;
706     }
707
708     if (obj instanceof TypeConversionDescriptorBase) {
709       ((TypeConversionDescriptorBase)obj).setRoot(myCurrentRoot);
710     }
711     myConversions.put(expression, obj);
712   }
713
714   public PsiReference[] markRootUsages(final PsiElement element, final PsiType migrationType) {
715     return markRootUsages(element, migrationType, ReferencesSearch.search(element, myRules.getSearchScope(), false).toArray(new PsiReference[0]));
716   }
717
718   PsiReference[] markRootUsages(final PsiElement element, final PsiType migrationType, final PsiReference[] refs) {
719     final List<PsiReference> validReferences = new ArrayList<PsiReference>();
720     for (PsiReference ref1 : refs) {
721       final PsiElement ref = ref1.getElement();
722
723       if (ref != null) {
724         if (element instanceof PsiMethod) {
725           final PsiElement parent = Util.getEssentialParent(ref);
726
727           if (!(parent instanceof PsiMethodCallExpression)) {
728             continue;
729           }
730
731           getTypeEvaluator().setType(new TypeMigrationUsageInfo(parent), migrationType);
732         }
733         else if (element instanceof PsiVariable) {
734           if (ref instanceof PsiReferenceExpression) {
735             getTypeEvaluator().setType(new TypeMigrationUsageInfo(ref), PsiImplUtil.normalizeWildcardTypeByPosition(migrationType, (PsiReferenceExpression)ref));
736           }
737         }
738         else {
739           LOG.error("Method call expression or reference expression expected but found " + element.getClass().getName());
740           continue;
741         }
742         validReferences.add(ref1);
743       }
744     }
745
746     Collections.sort(validReferences, new Comparator<PsiReference>() {
747       public int compare(final PsiReference o1, final PsiReference o2) {
748         return o1.getElement().getTextOffset() - o2.getElement().getTextOffset();
749       }
750     });
751
752     return validReferences.toArray(new PsiReference[validReferences.size()]);
753   }
754
755   public void setRootAndMigrate(final TypeMigrationUsageInfo newRootUsageInfo, final PsiType migrationType, final PsiReference[] usages) {
756     final TypeMigrationUsageInfo oldRoot = getCurrentRoot();
757     setCurrentRoot(newRootUsageInfo);
758     PsiElement root = newRootUsageInfo.getElement();
759     if (root instanceof PsiMethod) {
760       migrateMethodReturnExpression(migrationType, (PsiMethod)root);
761     }
762     else if (root instanceof PsiParameter && ((PsiParameter)root).getDeclarationScope() instanceof PsiMethod) {
763       migrateMethodCallExpressions(migrationType, (PsiParameter)root, null);
764     }
765     else if (root instanceof PsiVariable || root instanceof PsiExpression) {
766       final PsiElement element = getContainingStatement(root);
767       element.accept(new TypeMigrationStatementProcessor(element, this));
768     }
769     else if (root instanceof PsiReferenceParameterList) {
770       final TypeMigrationUsageInfo info = new TypeMigrationUsageInfo(root);
771       info.setOwnerRoot(oldRoot);
772       myClassTypeArgumentsChange.put(info, (PsiClassType)migrationType);
773       new ClassTypeArgumentMigrationProcessor(this).migrateClassTypeParameter((PsiReferenceParameterList)root, (PsiClassType)migrationType);
774     }
775
776     final Set<PsiElement> processed = new HashSet<PsiElement>();
777     for (PsiReference usage : usages) {
778       migrateRootUsageExpression(usage, processed);
779     }
780   }
781
782   private static PsiElement getContainingStatement(final PsiElement root) {
783     final PsiStatement statement = PsiTreeUtil.getParentOfType(root, PsiStatement.class);
784     final PsiField field = PsiTreeUtil.getParentOfType(root, PsiField.class);
785     return statement != null ? statement : field != null ? field : root;
786   }
787
788   void migrateRootUsageExpression(final PsiReference usage, final Set<PsiElement> processed) {
789     final PsiElement ref = usage.getElement();
790     if (ref != null && ref.getLanguage() == JavaLanguage.INSTANCE) {
791       final PsiElement element = getContainingStatement(ref);
792       if (element != null && !processed.contains(element)) {
793         processed.add(element);
794         element.accept(new TypeMigrationStatementProcessor(ref, this));
795       }
796     }
797   }
798
799   void migrateMethodCallExpressions(final PsiType migrationType, final PsiParameter param, final PsiClass psiClass) {
800     boolean checkNumberOfArguments = false;
801     if (param.getType() instanceof PsiEllipsisType && !(migrationType instanceof PsiEllipsisType)) {
802       checkNumberOfArguments = true;
803     }
804     final PsiType strippedType =
805                   migrationType instanceof PsiEllipsisType ? ((PsiEllipsisType)migrationType).getComponentType() : migrationType;
806     final PsiMethod method = (PsiMethod)param.getDeclarationScope();
807     final PsiParameterList parameterList = method.getParameterList();
808     final int parametersCount = parameterList.getParametersCount();
809     final int index = parameterList.getParameterIndex(param);
810     final List<PsiReference> refs = filterReferences(psiClass, ReferencesSearch.search(method, method.getUseScope().intersectWith(myRules.getSearchScope()), false));
811     for (PsiReference ref1 : refs) {
812       final PsiElement ref = ref1.getElement();
813       final PsiElement parent = Util.getEssentialParent(ref);
814       if (parent instanceof PsiCallExpression) {
815         final PsiExpressionList argumentList = ((PsiCallExpression)parent).getArgumentList();
816         if (argumentList != null) {
817           final PsiExpression[] expressions = argumentList.getExpressions();
818           if (checkNumberOfArguments && parametersCount != expressions.length) {
819             markFailedConversion(Pair.create(param.getType(), migrationType), (PsiCallExpression)parent);
820           }
821           if (index > -1 && index < expressions.length) {
822             for (int idx = index; idx < (param.isVarArgs() ? expressions.length : index + 1); idx++) {
823               final PsiExpression actual = expressions[idx];
824               final PsiType type = getTypeEvaluator().evaluateType(actual);
825               if (type != null) {
826                 migrateExpressionType(actual, strippedType, parent, TypeConversionUtil.isAssignable(strippedType, type), true);
827               }
828             }
829           }
830         }
831       } else if (ref instanceof PsiDocTagValue) {
832         myConversions.put(ref, method);
833       }
834     }
835   }
836
837   private void migrateMethodReturnExpression(final PsiType migrationType, final PsiMethod method) {
838     final PsiCodeBlock block = method.getBody();
839     if (block != null) {
840       block.accept(new JavaRecursiveElementWalkingVisitor() {
841         @Override
842         public void visitReturnStatement(PsiReturnStatement statement) {
843           final PsiExpression value = statement.getReturnValue();
844           if (value != null) {
845             final PsiType type = getTypeEvaluator().evaluateType(value);
846             if (type != null && !type.equals(migrationType)) {
847               migrateExpressionType(value, migrationType, statement, TypeConversionUtil.isAssignable(migrationType, type), true);
848             }
849           }
850         }
851
852         @Override
853         public void visitClass(PsiClass aClass) {}
854
855         @Override
856         public void visitLambdaExpression(PsiLambdaExpression expression) {}
857       });
858     }
859   }
860
861   private void iterate() {
862     final LinkedList<Pair<TypeMigrationUsageInfo, PsiType>> roots =
863         (LinkedList<Pair<TypeMigrationUsageInfo, PsiType>>)myMigrationRoots.clone();
864
865     myMigrationRoots = new LinkedList<Pair<TypeMigrationUsageInfo, PsiType>>();
866
867     final PsiReference[][] cachedUsages = new PsiReference[roots.size()][];
868     int j = 0;
869
870     for (final Pair<TypeMigrationUsageInfo, PsiType> p : roots) {
871       cachedUsages[j++] = markRootUsages(p.getFirst().getElement(), p.getSecond());
872     }
873
874     j = 0;
875
876     for (final Pair<TypeMigrationUsageInfo, PsiType> root : roots) {
877       setRootAndMigrate(root.getFirst(), root.getSecond(), cachedUsages[j++]);
878     }
879   }
880
881   private void migrate(boolean autoMigrate, final PsiElement... victims) {
882     myMigrationRoots = new LinkedList<Pair<TypeMigrationUsageInfo, PsiType>>();
883     myTypeEvaluator = new TypeEvaluator(myMigrationRoots, this);
884
885
886     final PsiType rootType = myRules.getMigrationRootType();
887     for (PsiElement victim : victims) {
888       addMigrationRoot(victim, rootType, null, false, true, true);
889     }
890
891     if (autoMigrate) {
892       while (myMigrationRoots.size() > 0) {
893         iterate();
894       }
895     }
896   }
897
898   public TypeEvaluator getTypeEvaluator() {
899     return myTypeEvaluator;
900   }
901
902   public Map<TypeMigrationUsageInfo, HashSet<Pair<TypeMigrationUsageInfo, PsiType>>> getRootsTree() {
903     return myRootsTree;
904   }
905
906   public void setCurrentRoot(final TypeMigrationUsageInfo currentRoot) {
907     myCurrentRoot = currentRoot;
908   }
909
910   TypeMigrationUsageInfo getCurrentRoot() {
911     return myCurrentRoot;
912   }
913
914   public LinkedList<Pair<TypeMigrationUsageInfo, PsiType>> getMigrationRoots() {
915     return myMigrationRoots;
916   }
917
918   public static List<PsiReference> filterReferences(final PsiClass psiClass, final Query<PsiReference> memberReferences) {
919     final List<PsiReference> refs = new ArrayList<PsiReference>();
920     for (PsiReference memberReference : memberReferences) {
921       if (psiClass == null) {
922         refs.add(memberReference);
923       } else {
924         final PsiElement referencedElement = memberReference.getElement();
925         if (referencedElement instanceof PsiReferenceExpression) {
926           final PsiExpression qualifierExpression = ((PsiReferenceExpression)referencedElement).getQualifierExpression();
927           if (qualifierExpression != null) {
928             final PsiType qualifierType = qualifierExpression.getType();
929             if (qualifierType instanceof PsiClassType && psiClass == ((PsiClassType)qualifierType).resolve()) {
930               refs.add(memberReference);
931             }
932           } else {
933             if (psiClass == PsiTreeUtil.getParentOfType(referencedElement, PsiClass.class)) {
934               refs.add(memberReference);
935             }
936           }
937         }
938       }
939     }
940     return refs;
941   }
942
943   @TestOnly
944   public String getMigrationReport() {
945     final StringBuilder buffer = new StringBuilder();
946
947     buffer.append("Types:\n").append(getTypeEvaluator().getReport()).append("\n");
948
949     buffer.append("Conversions:\n");
950
951     final String[] conversions = new String[myConversions.size()];
952     int k = 0;
953
954     for (final PsiElement expr : myConversions.keySet()) {
955       final Object conversion = myConversions.get(expr);
956
957       if (conversion instanceof Pair && ((Pair)conversion).first == null) {
958         conversions[k++] = (expr.getText() + " -> " + ((Pair)conversion).second + "\n");
959       } else {
960         conversions[k++] = (expr.getText() + " -> " + conversion + "\n");
961       }
962     }
963
964     Arrays.sort(conversions, new Comparator<String>() {
965       public int compare(String x, String y) {
966         return x.compareTo(y);
967       }
968     });
969
970     for (String conversion : conversions) {
971       buffer.append(conversion);
972     }
973
974     buffer.append("\nNew expression type changes:\n");
975
976     final String[] newChanges = new String[myNewExpressionTypeChange.size()];
977     k = 0;
978
979     for (final Map.Entry<TypeMigrationUsageInfo, PsiType> entry : myNewExpressionTypeChange.entrySet()) {
980       final PsiElement element = entry.getKey().getElement();
981       newChanges[k++] = (element != null ? element.getText() : entry.getKey()) + " -> " + entry.getValue().getCanonicalText() + "\n";
982     }
983
984     Arrays.sort(newChanges, new Comparator<String>() {
985       public int compare(String x, String y) {
986         return x.compareTo(y);
987       }
988     });
989
990     for (String change : newChanges) {
991       buffer.append(change);
992     }
993
994     buffer.append("Fails:\n");
995
996     final ArrayList<Pair<SmartPsiElementPointer<PsiExpression>, PsiType>>
997       failsList = new ArrayList<Pair<SmartPsiElementPointer<PsiExpression>, PsiType>>(myFailedConversions);
998     Collections.sort(failsList, new Comparator<Pair<SmartPsiElementPointer<PsiExpression>, PsiType>>() {
999       public int compare(final Pair<SmartPsiElementPointer<PsiExpression>, PsiType> o1, final Pair<SmartPsiElementPointer<PsiExpression>, PsiType> o2) {
1000         final PsiElement element1 = o1.getFirst().getElement();
1001         final PsiElement element2 = o2.getFirst().getElement();
1002         if (element1 == null || element2 == null) return 0;
1003         return element1.getText().compareTo(element2.getText());
1004       }
1005     });
1006
1007     for (final Pair<SmartPsiElementPointer<PsiExpression>, PsiType> p : failsList) {
1008       final PsiElement element = p.getFirst().getElement();
1009       if (element != null) {
1010         buffer.append(element.getText()).append("->").append(p.getSecond().getCanonicalText()).append("\n");
1011       }
1012     }
1013
1014     return buffer.toString();
1015   }
1016
1017   public static class MigrateException extends RuntimeException { }
1018 }