type migration tests fixed
[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       final PsiType rootInitialType = getElementType(getCurrentRoot().getElement());
472       if (rootInitialType  instanceof PsiClassReferenceType) {
473         collector = new HashSet<PsiTypeParameter>();
474         final PsiJavaCodeReferenceElement reference = ((PsiClassReferenceType)rootInitialType).getReference();
475         RefactoringUtil.collectTypeParameters(collector, reference);
476       } else {
477         collector = Collections.emptySet();
478       }
479       if (typeContainsTypeParameters(originalType, collector)) return false;
480     }
481
482     if (type instanceof PsiCapturedWildcardType) {
483       return false;
484     }
485
486     if (resolved instanceof PsiMethod) {
487       final PsiMethod method = ((PsiMethod)resolved);
488
489       final PsiClass containingClass = method.getContainingClass();
490       if (containingClass instanceof PsiAnonymousClass) {
491         final HierarchicalMethodSignature signature = method.getHierarchicalMethodSignature();
492         final List<HierarchicalMethodSignature> superSignatures = signature.getSuperSignatures();
493         if (!superSignatures.isEmpty()) {
494
495           final HierarchicalMethodSignature superSignature = superSignatures.get(0);
496
497           final PsiSubstitutor substitutor = superSignature.getSubstitutor();
498           if (!substitutor.getSubstitutionMap().isEmpty()) {
499             final PsiMethod superMethod = superSignature.getMethod();
500
501             final PsiType superReturnType = superMethod.getReturnType();
502             if (superReturnType instanceof PsiClassType) {
503               final PsiClass resolvedClass = ((PsiClassType)superReturnType).resolve();
504               if (resolvedClass instanceof PsiTypeParameter) {
505                 final PsiType expectedReturnType = substitutor.substitute((PsiTypeParameter)resolvedClass);
506                 if (Comparing.equal(expectedReturnType, method.getReturnType())) {
507                   final PsiClassType baseClassType = ((PsiAnonymousClass)containingClass).getBaseClassType();
508                   final PsiClassType.ClassResolveResult result = baseClassType.resolveGenerics();
509                   final PsiClass anonymousBaseClass = result.getElement();
510
511                   final PsiSubstitutor superHierarchySubstitutor = TypeConversionUtil
512                     .getClassSubstitutor(superMethod.getContainingClass(), anonymousBaseClass, PsiSubstitutor.EMPTY);
513                   final PsiType maybeTypeParameter = superHierarchySubstitutor.substitute((PsiTypeParameter)resolvedClass);
514
515                   if (maybeTypeParameter instanceof PsiClassType &&
516                       ((PsiClassType)maybeTypeParameter).resolve() instanceof PsiTypeParameter) {
517                     final PsiSubstitutor newSubstitutor = result.getSubstitutor().put(
518                       (PsiTypeParameter)((PsiClassType)maybeTypeParameter).resolve(), type);
519                     addRoot(new TypeMigrationUsageInfo(((PsiAnonymousClass)containingClass).getBaseClassReference().getParameterList()),
520                             new PsiImmediateClassType(anonymousBaseClass, newSubstitutor),
521                             place,
522                             alreadyProcessed);
523                   }
524                 }
525               }
526             }
527           }
528         }
529       }
530
531
532       final PsiMethod[] methods = OverridingMethodsSearch.search(method, true).toArray(PsiMethod.EMPTY_ARRAY);
533       final OverridenUsageInfo overridenUsageInfo = new OverridenUsageInfo(method);
534       final OverriderUsageInfo[] overriders = new OverriderUsageInfo[methods.length];
535       for (int i = -1; i < methods.length; i++) {
536         final TypeMigrationUsageInfo m;
537         if (i < 0) {
538           m = overridenUsageInfo;
539         }
540         else {
541           overriders[i] = new OverriderUsageInfo(methods[i], method);
542           m = overriders[i];
543         }
544
545         alreadyProcessed = addRoot(m, type, place, alreadyProcessed);
546       }
547       overridenUsageInfo.setOverriders(overriders);
548
549       return !alreadyProcessed;
550     }
551     else if (resolved instanceof PsiParameter && ((PsiParameter)resolved).getDeclarationScope() instanceof PsiMethod) {
552       final PsiMethod method = (PsiMethod)((PsiParameter)resolved).getDeclarationScope();
553
554       final int index = method.getParameterList().getParameterIndex(((PsiParameter)resolved));
555       final PsiMethod[] methods = OverridingMethodsSearch.search(method, true).toArray(PsiMethod.EMPTY_ARRAY);
556
557       final OverriderUsageInfo[] overriders = new OverriderUsageInfo[methods.length];
558       final OverridenUsageInfo overridenUsageInfo = new OverridenUsageInfo(method.getParameterList().getParameters()[index]);
559       for (int i = -1; i < methods.length; i++) {
560         final PsiMethod m = i < 0 ? method : methods[i];
561         final PsiParameter p = m.getParameterList().getParameters()[index];
562         final TypeMigrationUsageInfo paramUsageInfo;
563         if (i < 0) {
564           paramUsageInfo = overridenUsageInfo;
565         }
566         else {
567           overriders[i] = new OverriderUsageInfo(p, method);
568           paramUsageInfo = overriders[i];
569         }
570         alreadyProcessed = addRoot(paramUsageInfo, type, place, alreadyProcessed);
571       }
572
573       overridenUsageInfo.setOverriders(overriders);
574
575       return !alreadyProcessed;
576     }
577     else {
578       return !addRoot(new TypeMigrationUsageInfo(resolved), type, place, alreadyProcessed);
579     }
580   }
581
582   static boolean typeContainsTypeParameters(@Nullable PsiType originalType, @NotNull Set<PsiTypeParameter> excluded) {
583     if (originalType instanceof PsiClassType) {
584       final PsiClassType psiClassType = (PsiClassType)originalType;
585       if (psiClassType.resolve() instanceof PsiTypeParameter) {
586         return true;
587       }
588       for (PsiType paramType : psiClassType.getParameters()) {
589         if (paramType instanceof PsiClassType) {
590           final PsiClass resolved = ((PsiClassType)paramType).resolve();
591           if (resolved instanceof PsiTypeParameter && !excluded.contains(resolved)) return true;
592         }
593       }
594     }
595     return false;
596   }
597
598
599   @Nullable
600   public static PsiType getElementType(final PsiElement resolved) {
601     if (resolved instanceof PsiVariable) {
602       return ((PsiVariable)resolved).getType();
603     }
604     else {
605       if (resolved instanceof PsiMethod) {
606         return (((PsiMethod)resolved).getReturnType());
607       }
608       else if (resolved instanceof PsiExpression){
609         return (((PsiExpression)resolved).getType());
610       } else if (resolved instanceof PsiReferenceParameterList) {
611         PsiElement parent = resolved.getParent();
612         while (parent != null) {
613           LOG.assertTrue(parent instanceof PsiJavaCodeReferenceElement);
614           final PsiClass psiClass = (PsiClass)((PsiJavaCodeReferenceElement)parent).resolve();
615           final PsiClass containingClass = PsiTreeUtil.getParentOfType(parent, PsiClass.class);
616           if (psiClass != null && containingClass != null) {
617            final PsiSubstitutor classSubstitutor = TypeConversionUtil.getClassSubstitutor(psiClass, containingClass, PsiSubstitutor.EMPTY);
618            if (classSubstitutor != null) {
619              return JavaPsiFacade.getElementFactory(parent.getProject()).createType(psiClass, classSubstitutor);
620            }
621           }
622           parent = PsiTreeUtil.getParentOfType(parent, PsiJavaCodeReferenceElement.class, true);
623         }
624       } else if (resolved instanceof PsiClass) {
625         return JavaPsiFacade.getElementFactory(resolved.getProject()).createType((PsiClass)resolved, PsiSubstitutor.EMPTY);
626       }
627     }
628     return null;
629   }
630
631   public void clearStopException() {
632     myException = null;
633   }
634   
635   boolean addRoot(final TypeMigrationUsageInfo usageInfo, final PsiType type, final PsiElement place, boolean alreadyProcessed) {
636     if (myShowWarning && myMigrationRoots.size() > 10 && !ApplicationManager.getApplication().isUnitTestMode()) {
637       myShowWarning = false;
638       try {
639         final Runnable checkTimeToStopRunnable = new Runnable() {
640           public void run() {
641             if (Messages.showYesNoCancelDialog("Found more than 10 roots to migrate. Do you want to preview?", "Type Migration",
642                                                Messages.getWarningIcon()) == Messages.YES) {
643               myException = new MigrateException();
644             }
645           }
646         };
647         SwingUtilities.invokeLater(checkTimeToStopRunnable);
648       }
649       catch (Exception e) {
650         //do nothing
651       }
652     }
653     if (myException != null) throw myException;
654     rememberRootTrace(usageInfo, type, place, alreadyProcessed);
655     if (!alreadyProcessed && !getTypeEvaluator().setType(usageInfo, type)) {
656       alreadyProcessed = true;
657     }
658
659     if (!alreadyProcessed) myMigrationRoots.addFirst(Pair.create(usageInfo, type));
660     return alreadyProcessed;
661   }
662
663   private void rememberRootTrace(final TypeMigrationUsageInfo usageInfo, final PsiType type, final PsiElement place, final boolean alreadyProcessed) {
664     if (myCurrentRoot != null) {
665       if (!alreadyProcessed) {
666         myProcessedRoots.add(usageInfo);
667       }
668
669       if (myProcessedRoots.contains(usageInfo)) {
670         HashSet<Pair<TypeMigrationUsageInfo, PsiType>> infos = myRootsTree.get(myCurrentRoot);
671         if (infos == null) {
672           infos = new HashSet<Pair<TypeMigrationUsageInfo, PsiType>>();
673           myRootsTree.put(myCurrentRoot, infos);
674         }
675         infos.add(Pair.create(usageInfo, type));
676       }
677       if (!(usageInfo instanceof OverriderUsageInfo)) { //hide the same usage for all overriders
678         setTypeUsage(usageInfo, place);
679       }
680     }
681   }
682
683   private void setTypeUsage(final TypeMigrationUsageInfo usageInfo, final PsiElement place) {
684     if (place != null) {
685       final Pair<TypeMigrationUsageInfo, TypeMigrationUsageInfo> rooted = Pair.create(usageInfo, myCurrentRoot);
686       Set<PsiElement> usages = myRootUsagesTree.get(rooted);
687       if (usages == null) {
688         usages = new HashSet<PsiElement>();
689         myRootUsagesTree.put(rooted, usages);
690       }
691       usages.add(place);
692     }
693   }
694   
695   public void setTypeUsage(final PsiElement element, final PsiElement place) {
696     setTypeUsage(new TypeMigrationUsageInfo(element), place);
697   }
698
699   void markFailedConversion(final Pair<PsiType, PsiType> typePair, final PsiExpression expression) {
700     LOG.assertTrue(typePair.getSecond() != null);
701     myFailedConversions.add(Pair.create(SmartPointerManager.getInstance(expression.getProject()).createSmartPsiElementPointer(expression), typePair.getSecond()));
702   }
703
704   void setConversionMapping(final PsiExpression expression, final Object obj) {
705     if (myConversions.get(expression) != null) {
706       return;
707     }
708
709     if (obj instanceof TypeConversionDescriptorBase) {
710       ((TypeConversionDescriptorBase)obj).setRoot(myCurrentRoot);
711     }
712     myConversions.put(expression, obj);
713   }
714
715   public PsiReference[] markRootUsages(final PsiElement element, final PsiType migrationType) {
716     return markRootUsages(element, migrationType, ReferencesSearch.search(element, myRules.getSearchScope(), false).toArray(new PsiReference[0]));
717   }
718
719   PsiReference[] markRootUsages(final PsiElement element, final PsiType migrationType, final PsiReference[] refs) {
720     final List<PsiReference> validReferences = new ArrayList<PsiReference>();
721     for (PsiReference ref1 : refs) {
722       final PsiElement ref = ref1.getElement();
723
724       if (ref != null) {
725         if (element instanceof PsiMethod) {
726           final PsiElement parent = Util.getEssentialParent(ref);
727
728           if (!(parent instanceof PsiMethodCallExpression)) {
729             continue;
730           }
731
732           getTypeEvaluator().setType(new TypeMigrationUsageInfo(parent), migrationType);
733         }
734         else if (element instanceof PsiVariable) {
735           if (ref instanceof PsiReferenceExpression) {
736             getTypeEvaluator().setType(new TypeMigrationUsageInfo(ref), PsiImplUtil.normalizeWildcardTypeByPosition(migrationType, (PsiReferenceExpression)ref));
737           }
738         }
739         else {
740           LOG.error("Method call expression or reference expression expected but found " + element.getClass().getName());
741           continue;
742         }
743         validReferences.add(ref1);
744       }
745     }
746
747     Collections.sort(validReferences, new Comparator<PsiReference>() {
748       public int compare(final PsiReference o1, final PsiReference o2) {
749         return o1.getElement().getTextOffset() - o2.getElement().getTextOffset();
750       }
751     });
752
753     return validReferences.toArray(new PsiReference[validReferences.size()]);
754   }
755
756   public void setRootAndMigrate(final TypeMigrationUsageInfo newRootUsageInfo, final PsiType migrationType, final PsiReference[] usages) {
757     final TypeMigrationUsageInfo oldRoot = getCurrentRoot();
758     setCurrentRoot(newRootUsageInfo);
759     PsiElement root = newRootUsageInfo.getElement();
760     if (root instanceof PsiMethod) {
761       migrateMethodReturnExpression(migrationType, (PsiMethod)root);
762     }
763     else if (root instanceof PsiParameter && ((PsiParameter)root).getDeclarationScope() instanceof PsiMethod) {
764       migrateMethodCallExpressions(migrationType, (PsiParameter)root, null);
765     }
766     else if (root instanceof PsiVariable || root instanceof PsiExpression) {
767       final PsiElement element = getContainingStatement(root);
768       element.accept(new TypeMigrationStatementProcessor(element, this));
769     }
770     else if (root instanceof PsiReferenceParameterList) {
771       final TypeMigrationUsageInfo info = new TypeMigrationUsageInfo(root);
772       info.setOwnerRoot(oldRoot);
773       myClassTypeArgumentsChange.put(info, (PsiClassType)migrationType);
774       new ClassTypeArgumentMigrationProcessor(this).migrateClassTypeParameter((PsiReferenceParameterList)root, (PsiClassType)migrationType);
775     }
776
777     final Set<PsiElement> processed = new HashSet<PsiElement>();
778     for (PsiReference usage : usages) {
779       migrateRootUsageExpression(usage, processed);
780     }
781   }
782
783   private static PsiElement getContainingStatement(final PsiElement root) {
784     final PsiStatement statement = PsiTreeUtil.getParentOfType(root, PsiStatement.class);
785     final PsiField field = PsiTreeUtil.getParentOfType(root, PsiField.class);
786     return statement != null ? statement : field != null ? field : root;
787   }
788
789   void migrateRootUsageExpression(final PsiReference usage, final Set<PsiElement> processed) {
790     final PsiElement ref = usage.getElement();
791     if (ref != null && ref.getLanguage() == JavaLanguage.INSTANCE) {
792       final PsiElement element = getContainingStatement(ref);
793       if (element != null && !processed.contains(element)) {
794         processed.add(element);
795         element.accept(new TypeMigrationStatementProcessor(ref, this));
796       }
797     }
798   }
799
800   void migrateMethodCallExpressions(final PsiType migrationType, final PsiParameter param, final PsiClass psiClass) {
801     boolean checkNumberOfArguments = false;
802     if (param.getType() instanceof PsiEllipsisType && !(migrationType instanceof PsiEllipsisType)) {
803       checkNumberOfArguments = true;
804     }
805     final PsiType strippedType =
806                   migrationType instanceof PsiEllipsisType ? ((PsiEllipsisType)migrationType).getComponentType() : migrationType;
807     final PsiMethod method = (PsiMethod)param.getDeclarationScope();
808     final PsiParameterList parameterList = method.getParameterList();
809     final int parametersCount = parameterList.getParametersCount();
810     final int index = parameterList.getParameterIndex(param);
811     final List<PsiReference> refs = filterReferences(psiClass, ReferencesSearch.search(method, method.getUseScope().intersectWith(myRules.getSearchScope()), false));
812     for (PsiReference ref1 : refs) {
813       final PsiElement ref = ref1.getElement();
814       final PsiElement parent = Util.getEssentialParent(ref);
815       if (parent instanceof PsiCallExpression) {
816         final PsiExpressionList argumentList = ((PsiCallExpression)parent).getArgumentList();
817         if (argumentList != null) {
818           final PsiExpression[] expressions = argumentList.getExpressions();
819           if (checkNumberOfArguments && parametersCount != expressions.length) {
820             markFailedConversion(Pair.create(param.getType(), migrationType), (PsiCallExpression)parent);
821           }
822           if (index > -1 && index < expressions.length) {
823             for (int idx = index; idx < (param.isVarArgs() ? expressions.length : index + 1); idx++) {
824               final PsiExpression actual = expressions[idx];
825               final PsiType type = getTypeEvaluator().evaluateType(actual);
826               if (type != null) {
827                 migrateExpressionType(actual, strippedType, parent, TypeConversionUtil.isAssignable(strippedType, type), true);
828               }
829             }
830           }
831         }
832       } else if (ref instanceof PsiDocTagValue) {
833         myConversions.put(ref, method);
834       }
835     }
836   }
837
838   private void migrateMethodReturnExpression(final PsiType migrationType, final PsiMethod method) {
839     final PsiCodeBlock block = method.getBody();
840     if (block != null) {
841       block.accept(new JavaRecursiveElementWalkingVisitor() {
842         @Override
843         public void visitReturnStatement(PsiReturnStatement statement) {
844           final PsiExpression value = statement.getReturnValue();
845           if (value != null) {
846             final PsiType type = getTypeEvaluator().evaluateType(value);
847             if (type != null && !type.equals(migrationType)) {
848               migrateExpressionType(value, migrationType, statement, TypeConversionUtil.isAssignable(migrationType, type), true);
849             }
850           }
851         }
852
853         @Override
854         public void visitClass(PsiClass aClass) {}
855
856         @Override
857         public void visitLambdaExpression(PsiLambdaExpression expression) {}
858       });
859     }
860   }
861
862   private void iterate() {
863     final LinkedList<Pair<TypeMigrationUsageInfo, PsiType>> roots =
864         (LinkedList<Pair<TypeMigrationUsageInfo, PsiType>>)myMigrationRoots.clone();
865
866     myMigrationRoots = new LinkedList<Pair<TypeMigrationUsageInfo, PsiType>>();
867
868     final PsiReference[][] cachedUsages = new PsiReference[roots.size()][];
869     int j = 0;
870
871     for (final Pair<TypeMigrationUsageInfo, PsiType> p : roots) {
872       cachedUsages[j++] = markRootUsages(p.getFirst().getElement(), p.getSecond());
873     }
874
875     j = 0;
876
877     for (final Pair<TypeMigrationUsageInfo, PsiType> root : roots) {
878       setRootAndMigrate(root.getFirst(), root.getSecond(), cachedUsages[j++]);
879     }
880   }
881
882   private void migrate(boolean autoMigrate, final PsiElement... victims) {
883     myMigrationRoots = new LinkedList<Pair<TypeMigrationUsageInfo, PsiType>>();
884     myTypeEvaluator = new TypeEvaluator(myMigrationRoots, this);
885
886
887     final PsiType rootType = myRules.getMigrationRootType();
888     for (PsiElement victim : victims) {
889       addMigrationRoot(victim, rootType, null, false, true, true);
890     }
891
892     if (autoMigrate) {
893       while (myMigrationRoots.size() > 0) {
894         iterate();
895       }
896     }
897   }
898
899   public TypeEvaluator getTypeEvaluator() {
900     return myTypeEvaluator;
901   }
902
903   public Map<TypeMigrationUsageInfo, HashSet<Pair<TypeMigrationUsageInfo, PsiType>>> getRootsTree() {
904     return myRootsTree;
905   }
906
907   public void setCurrentRoot(final TypeMigrationUsageInfo currentRoot) {
908     myCurrentRoot = currentRoot;
909   }
910
911   TypeMigrationUsageInfo getCurrentRoot() {
912     return myCurrentRoot;
913   }
914
915   public LinkedList<Pair<TypeMigrationUsageInfo, PsiType>> getMigrationRoots() {
916     return myMigrationRoots;
917   }
918
919   public static List<PsiReference> filterReferences(final PsiClass psiClass, final Query<PsiReference> memberReferences) {
920     final List<PsiReference> refs = new ArrayList<PsiReference>();
921     for (PsiReference memberReference : memberReferences) {
922       if (psiClass == null) {
923         refs.add(memberReference);
924       } else {
925         final PsiElement referencedElement = memberReference.getElement();
926         if (referencedElement instanceof PsiReferenceExpression) {
927           final PsiExpression qualifierExpression = ((PsiReferenceExpression)referencedElement).getQualifierExpression();
928           if (qualifierExpression != null) {
929             final PsiType qualifierType = qualifierExpression.getType();
930             if (qualifierType instanceof PsiClassType && psiClass == ((PsiClassType)qualifierType).resolve()) {
931               refs.add(memberReference);
932             }
933           } else {
934             if (psiClass == PsiTreeUtil.getParentOfType(referencedElement, PsiClass.class)) {
935               refs.add(memberReference);
936             }
937           }
938         }
939       }
940     }
941     return refs;
942   }
943
944   @TestOnly
945   public String getMigrationReport() {
946     final StringBuilder buffer = new StringBuilder();
947
948     buffer.append("Types:\n").append(getTypeEvaluator().getReport()).append("\n");
949
950     buffer.append("Conversions:\n");
951
952     final String[] conversions = new String[myConversions.size()];
953     int k = 0;
954
955     for (final PsiElement expr : myConversions.keySet()) {
956       final Object conversion = myConversions.get(expr);
957
958       if (conversion instanceof Pair && ((Pair)conversion).first == null) {
959         conversions[k++] = (expr.getText() + " -> " + ((Pair)conversion).second + "\n");
960       } else {
961         conversions[k++] = (expr.getText() + " -> " + conversion + "\n");
962       }
963     }
964
965     Arrays.sort(conversions, new Comparator<String>() {
966       public int compare(String x, String y) {
967         return x.compareTo(y);
968       }
969     });
970
971     for (String conversion : conversions) {
972       buffer.append(conversion);
973     }
974
975     buffer.append("\nNew expression type changes:\n");
976
977     final String[] newChanges = new String[myNewExpressionTypeChange.size()];
978     k = 0;
979
980     for (final Map.Entry<TypeMigrationUsageInfo, PsiType> entry : myNewExpressionTypeChange.entrySet()) {
981       final PsiElement element = entry.getKey().getElement();
982       newChanges[k++] = (element != null ? element.getText() : entry.getKey()) + " -> " + entry.getValue().getCanonicalText() + "\n";
983     }
984
985     Arrays.sort(newChanges, new Comparator<String>() {
986       public int compare(String x, String y) {
987         return x.compareTo(y);
988       }
989     });
990
991     for (String change : newChanges) {
992       buffer.append(change);
993     }
994
995     buffer.append("Fails:\n");
996
997     final ArrayList<Pair<SmartPsiElementPointer<PsiExpression>, PsiType>>
998       failsList = new ArrayList<Pair<SmartPsiElementPointer<PsiExpression>, PsiType>>(myFailedConversions);
999     Collections.sort(failsList, new Comparator<Pair<SmartPsiElementPointer<PsiExpression>, PsiType>>() {
1000       public int compare(final Pair<SmartPsiElementPointer<PsiExpression>, PsiType> o1, final Pair<SmartPsiElementPointer<PsiExpression>, PsiType> o2) {
1001         final PsiElement element1 = o1.getFirst().getElement();
1002         final PsiElement element2 = o2.getFirst().getElement();
1003         if (element1 == null || element2 == null) return 0;
1004         return element1.getText().compareTo(element2.getText());
1005       }
1006     });
1007
1008     for (final Pair<SmartPsiElementPointer<PsiExpression>, PsiType> p : failsList) {
1009       final PsiElement element = p.getFirst().getElement();
1010       if (element != null) {
1011         buffer.append(element.getText()).append("->").append(p.getSecond().getCanonicalText()).append("\n");
1012       }
1013     }
1014
1015     return buffer.toString();
1016   }
1017
1018   public static class MigrateException extends RuntimeException { }
1019 }