IDEA-162158 (Inspection incorrectly suggests to collapse "catch" blocks)
[idea/community.git] / java / java-analysis-impl / src / com / intellij / refactoring / util / duplicates / DuplicatesFinder.java
1 /*
2  * Copyright 2000-2016 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.util.duplicates;
17
18 import com.intellij.codeInsight.PsiEquivalenceUtil;
19 import com.intellij.lang.ASTNode;
20 import com.intellij.openapi.diagnostic.Logger;
21 import com.intellij.openapi.util.Comparing;
22 import com.intellij.openapi.util.Key;
23 import com.intellij.openapi.util.Pair;
24 import com.intellij.psi.*;
25 import com.intellij.psi.controlFlow.*;
26 import com.intellij.psi.impl.source.PsiImmediateClassType;
27 import com.intellij.psi.tree.IElementType;
28 import com.intellij.psi.util.*;
29 import com.intellij.refactoring.extractMethod.InputVariables;
30 import com.intellij.refactoring.util.RefactoringChangeUtil;
31 import com.intellij.util.ArrayUtil;
32 import com.intellij.util.IncorrectOperationException;
33 import com.intellij.util.containers.ContainerUtil;
34 import com.intellij.util.containers.IntArrayList;
35 import org.jetbrains.annotations.NotNull;
36 import org.jetbrains.annotations.Nullable;
37
38 import java.util.*;
39
40 /**
41  * @author dsl
42  */
43 public class DuplicatesFinder {
44   private static final Logger LOG = Logger.getInstance("#com.intellij.refactoring.util.duplicates.DuplicatesFinder");
45   public static final Key<Pair<PsiVariable, PsiType>> PARAMETER = Key.create("PARAMETER");
46   private final PsiElement[] myPattern;
47   private final InputVariables myParameters;
48   private final List<? extends PsiVariable> myOutputParameters;
49   private final List<PsiElement> myPatternAsList;
50   private boolean myMultipleExitPoints;
51   @Nullable private final ReturnValue myReturnValue;
52
53   public DuplicatesFinder(PsiElement[] pattern,
54                           InputVariables parameters,
55                           @Nullable ReturnValue returnValue,
56                           @NotNull List<? extends PsiVariable> outputParameters
57   ) {
58     myReturnValue = returnValue;
59     LOG.assertTrue(pattern.length > 0);
60     myPattern = pattern;
61     myPatternAsList = Arrays.asList(myPattern);
62     myParameters = parameters;
63     myOutputParameters = outputParameters;
64
65     final PsiElement codeFragment = ControlFlowUtil.findCodeFragment(pattern[0]);
66     try {
67       final ControlFlow controlFlow = ControlFlowFactory.getInstance(codeFragment.getProject()).getControlFlow(codeFragment, new LocalsControlFlowPolicy(codeFragment), false);
68
69       int startOffset;
70       int i = 0;
71       do {
72         startOffset = controlFlow.getStartOffset(pattern[i++]);
73       } while(startOffset < 0 && i < pattern.length);
74
75       int endOffset;
76       int j = pattern.length - 1;
77       do {
78         endOffset = controlFlow.getEndOffset(pattern[j--]);
79       } while(endOffset < 0 && j >= 0);
80
81       IntArrayList exitPoints = new IntArrayList();
82       final Collection<PsiStatement> exitStatements = ControlFlowUtil
83           .findExitPointsAndStatements(controlFlow, startOffset, endOffset, exitPoints, ControlFlowUtil.DEFAULT_EXIT_STATEMENTS_CLASSES);
84       myMultipleExitPoints = exitPoints.size() > 1;
85
86       if (myMultipleExitPoints) {
87         myParameters.removeParametersUsedInExitsOnly(codeFragment, exitStatements, controlFlow, startOffset, endOffset);
88       }
89     }
90     catch (AnalysisCanceledException e) {
91     }
92   }
93
94   public DuplicatesFinder(final PsiElement[] pattern,
95                           final InputVariables psiParameters,
96                           final List<? extends PsiVariable> psiVariables) {
97     this(pattern, psiParameters, null, psiVariables);
98   }
99
100
101   public InputVariables getParameters() {
102     return myParameters;
103   }
104
105   public PsiElement[] getPattern() {
106     return myPattern;
107   }
108
109   @Nullable
110   public ReturnValue getReturnValue() {
111     return myReturnValue;
112   }
113
114   public List<Match> findDuplicates(PsiElement scope) {
115     annotatePattern();
116     final ArrayList<Match> result = new ArrayList<>();
117     findPatternOccurrences(result, scope);
118     deannotatePattern();
119     return result;
120   }
121
122   @Nullable
123   public Match isDuplicate(@NotNull PsiElement element, boolean ignoreParameterTypesAndPostVariableUsages) {
124     annotatePattern();
125     Match match = isDuplicateFragment(element, ignoreParameterTypesAndPostVariableUsages);
126     deannotatePattern();
127     return match;
128   }
129
130   private void annotatePattern() {
131     for (final PsiElement patternComponent : myPattern) {
132       patternComponent.accept(new JavaRecursiveElementWalkingVisitor() {
133         @Override public void visitReferenceElement(PsiJavaCodeReferenceElement reference) {
134           final PsiElement element = reference.resolve();
135           if (element instanceof PsiVariable) {
136             final PsiVariable variable = (PsiVariable)element;
137             PsiType type = variable.getType();
138             myParameters.annotateWithParameter(reference);
139             if (myOutputParameters.contains(element)) {
140               reference.putUserData(PARAMETER, Pair.create(variable, type));
141             }
142           }
143           PsiElement qualifier = reference.getQualifier();
144           if (qualifier != null) {
145             qualifier.accept(this);
146           }
147         }
148       });
149     }
150   }
151
152   private void deannotatePattern() {
153     for (final PsiElement patternComponent : myPattern) {
154       patternComponent.accept(new JavaRecursiveElementWalkingVisitor() {
155         @Override public void visitReferenceElement(PsiJavaCodeReferenceElement reference) {
156           if (reference.getUserData(PARAMETER) != null) {
157             reference.putUserData(PARAMETER, null);
158           }
159         }
160       });
161     }
162   }
163
164   private void findPatternOccurrences(List<Match> array, PsiElement scope) {
165     PsiElement[] children = scope.getChildren();
166     for (PsiElement child : children) {
167       final Match match = isDuplicateFragment(child, false);
168       if (match != null) {
169         array.add(match);
170         continue;
171       }
172       findPatternOccurrences(array, child);
173     }
174   }
175
176
177   @Nullable
178   private Match isDuplicateFragment(@NotNull PsiElement candidate, boolean ignoreParameterTypesAndPostVariableUsages) {
179     if (isSelf(candidate)) return null;
180     PsiElement sibling = candidate;
181     ArrayList<PsiElement> candidates = new ArrayList<>();
182     for (final PsiElement element : myPattern) {
183       if (sibling == null) return null;
184       if (!canBeEquivalent(element, sibling)) return null;
185       candidates.add(sibling);
186       sibling = PsiTreeUtil.skipSiblingsForward(sibling, PsiWhiteSpace.class, PsiComment.class, PsiEmptyStatement.class);
187     }
188     LOG.assertTrue(myPattern.length == candidates.size());
189     if (myPattern.length == 1 && myPattern[0] instanceof PsiExpression) {
190       if (candidates.get(0) instanceof PsiExpression) {
191         final PsiExpression candidateExpression = (PsiExpression)candidates.get(0);
192         if (PsiUtil.isAccessedForWriting(candidateExpression)) return null;
193         final PsiType patternType = ((PsiExpression)myPattern[0]).getType();
194         final PsiType candidateType = candidateExpression.getType();
195         PsiSubstitutor substitutor = PsiSubstitutor.EMPTY;
196         final PsiMethod method = PsiTreeUtil.getContextOfType(myPattern[0], PsiMethod.class);
197         if (method != null) {
198           final PsiResolveHelper resolveHelper = JavaPsiFacade.getInstance(candidate.getProject()).getResolveHelper();
199           substitutor = resolveHelper.inferTypeArguments(method.getTypeParameters(), new PsiType[]{patternType},
200                                                          new PsiType[]{candidateType}, PsiUtil.getLanguageLevel(method));
201         }
202         if (!canTypesBeEquivalent(substitutor.substitute(patternType), candidateType)) return null;
203       }
204       else {
205         return null;
206       }
207
208     }
209     final Match match = new Match(candidates.get(0), candidates.get(candidates.size() - 1), ignoreParameterTypesAndPostVariableUsages);
210     for (int i = 0; i < myPattern.length; i++) {
211       if (!matchPattern(myPattern[i], candidates.get(i), candidates, match)) return null;
212     }
213
214     if (!ignoreParameterTypesAndPostVariableUsages && checkPostVariableUsages(candidates, match)) return null;
215
216     return match;
217   }
218
219   protected boolean isSelf(@NotNull PsiElement candidate) {
220     for (PsiElement pattern : myPattern) {
221       if (PsiTreeUtil.isAncestor(pattern, candidate, false)) {
222         return true;
223       }
224     }
225     return false;
226   }
227
228   private boolean checkPostVariableUsages(final ArrayList<PsiElement> candidates, final Match match) {
229     final PsiElement codeFragment = ControlFlowUtil.findCodeFragment(candidates.get(0));
230     try {
231       final ControlFlow controlFlow = ControlFlowFactory.getInstance(codeFragment.getProject()).getControlFlow(codeFragment, new LocalsControlFlowPolicy(codeFragment), false);
232
233       int startOffset;
234       int i = 0;
235       do {
236         startOffset = controlFlow.getStartOffset(candidates.get(i++));
237       } while(startOffset < 0 && i < candidates.size());
238
239       int endOffset;
240       int j = candidates.size() - 1;
241       do {
242         endOffset = controlFlow.getEndOffset(candidates.get(j--));
243       } while(endOffset < 0 && j >= 0);
244
245       final IntArrayList exitPoints = new IntArrayList();
246       ControlFlowUtil.findExitPointsAndStatements(controlFlow, startOffset, endOffset, exitPoints, ControlFlowUtil.DEFAULT_EXIT_STATEMENTS_CLASSES);
247       final PsiVariable[] outVariables = ControlFlowUtil.getOutputVariables(controlFlow, startOffset, endOffset, exitPoints.toArray());
248
249       if (outVariables.length > 0) {
250         if (outVariables.length == 1) {
251           ReturnValue returnValue = match.getReturnValue();
252           if (returnValue == null) {
253             returnValue = myReturnValue;
254           }
255           if (returnValue instanceof VariableReturnValue) {
256             final ReturnValue value = match.getOutputVariableValue(((VariableReturnValue)returnValue).getVariable());
257             if (value != null) {
258               if (value.isEquivalent(new VariableReturnValue(outVariables[0]))) return false;
259               if (value instanceof ExpressionReturnValue) {
260                 final PsiExpression expression = ((ExpressionReturnValue)value).getExpression();
261                 if (expression instanceof PsiReferenceExpression) {
262                   final PsiElement variable = ((PsiReferenceExpression)expression).resolve();
263                   return variable == null || !PsiEquivalenceUtil.areElementsEquivalent(variable, outVariables[0]);
264                 }
265               }
266             }
267           }
268         }
269         return true;
270       }
271     }
272     catch (AnalysisCanceledException e) {
273     }
274     return false;
275   }
276
277   private static boolean canTypesBeEquivalent(PsiType type1, PsiType type2) {
278     if (type1 == null || type2 == null) return false;
279     if (!type2.isAssignableFrom(type1)) {
280       if (type1 instanceof PsiImmediateClassType && type2 instanceof PsiImmediateClassType) {
281         final PsiClass psiClass1 = ((PsiImmediateClassType)type1).resolve();
282         final PsiClass psiClass2 = ((PsiImmediateClassType)type2).resolve();
283         if (!(psiClass1 instanceof PsiAnonymousClass &&
284               psiClass2 instanceof PsiAnonymousClass &&
285               psiClass1.getManager().areElementsEquivalent(((PsiAnonymousClass)psiClass1).getBaseClassType().resolve(),
286                                                            ((PsiAnonymousClass)psiClass2).getBaseClassType().resolve()))) {
287           return false;
288         }
289       }
290       else {
291         return false;
292       }
293     }
294     return true;
295   }
296
297   private static boolean canBeEquivalent(final PsiElement pattern, PsiElement candidate) {
298     if (pattern instanceof PsiReturnStatement && candidate instanceof PsiExpressionStatement) return true;
299     if (pattern instanceof PsiReturnStatement && candidate instanceof PsiDeclarationStatement) return true;
300     if (pattern instanceof PsiThisExpression && candidate instanceof PsiReferenceExpression) return true;
301     final ASTNode node1 = pattern.getNode();
302     final ASTNode node2 = candidate.getNode();
303     if (node1 == null || node2 == null) return false;
304     return node1.getElementType() == node2.getElementType();
305   }
306
307   private boolean matchPattern(PsiElement pattern,
308                                PsiElement candidate,
309                                List<PsiElement> candidates,
310                                Match match) {
311     if (pattern == null || candidate == null) return pattern == candidate;
312     if (pattern.getUserData(PARAMETER) != null) {
313       final Pair<PsiVariable, PsiType> parameter = pattern.getUserData(PARAMETER);
314       return match.putParameter(parameter, candidate);
315     }
316
317     if (!canBeEquivalent(pattern, candidate)) return false; // Q : is it correct to check implementation classes?
318
319     if (pattern instanceof PsiExpressionList && candidate instanceof PsiExpressionList) { //check varargs
320       final PsiExpression[] expressions = ((PsiExpressionList)pattern).getExpressions();
321       final PsiExpression[] childExpressions = ((PsiExpressionList)candidate).getExpressions();
322       if (expressions.length > 0 && expressions[expressions.length - 1] instanceof PsiReferenceExpression) {
323         final PsiElement resolved = ((PsiReferenceExpression)expressions[expressions.length - 1]).resolve();
324         if (resolved instanceof PsiParameter && ((PsiParameter)resolved).getType() instanceof PsiEllipsisType) {
325           for(int i = 0; i < expressions.length - 1; i++) {
326             final Pair<PsiVariable, PsiType> parameter = expressions[i].getUserData(PARAMETER);
327             if (parameter == null) {
328               if (!matchPattern(expressions[i], childExpressions[i], candidates, match)) {
329                 return false;
330               }
331             } else if (!match.putParameter(parameter, childExpressions[i])) return false;
332           }
333           final Pair<PsiVariable, PsiType> param = expressions[expressions.length - 1].getUserData(PARAMETER);
334           if (param == null) return false;
335           for(int i = expressions.length - 1; i < childExpressions.length; i++) {
336             if (!match.putParameter(param, childExpressions[i])) return false;
337           }
338           return true;
339         }
340       }
341     }
342
343     if (pattern instanceof PsiAssignmentExpression) {
344       final PsiExpression lExpression = PsiUtil.skipParenthesizedExprDown(((PsiAssignmentExpression)pattern).getLExpression());
345       if (lExpression.getType() instanceof PsiPrimitiveType &&
346           lExpression instanceof PsiReferenceExpression &&
347           ((PsiReferenceExpression)lExpression).resolve() instanceof PsiParameter) {
348         return false;
349       }
350     } else if (pattern instanceof PsiPrefixExpression) {
351       if (checkParameterModification(((PsiPrefixExpression)pattern).getOperand(), ((PsiPrefixExpression)pattern).getOperationTokenType(),
352                                      ((PsiPrefixExpression)candidate).getOperand())) return false;
353     } else if (pattern instanceof PsiPostfixExpression) {
354       if (checkParameterModification(((PsiPostfixExpression)pattern).getOperand(), ((PsiPostfixExpression)pattern).getOperationTokenType(),
355                                      ((PsiPostfixExpression)candidate).getOperand())) return false;
356     }
357
358     if (pattern instanceof PsiJavaCodeReferenceElement) {
359       final PsiElement resolveResult1 = ((PsiJavaCodeReferenceElement)pattern).resolve();
360       final PsiElement resolveResult2 = ((PsiJavaCodeReferenceElement)candidate).resolve();
361       if (resolveResult1 instanceof PsiClass && resolveResult2 instanceof PsiClass) return true;
362       if (isUnder(resolveResult1, myPatternAsList) && isUnder(resolveResult2, candidates)) {
363         traverseParameter(resolveResult1, resolveResult2, match);
364         return match.putDeclarationCorrespondence(resolveResult1, resolveResult2);
365       }
366       final PsiElement qualifier2 = ((PsiJavaCodeReferenceElement)candidate).getQualifier();
367       if (!equivalentResolve(resolveResult1, resolveResult2, qualifier2)) {
368         return false;
369       }
370       PsiElement qualifier1 = ((PsiJavaCodeReferenceElement)pattern).getQualifier();
371       if (qualifier1 instanceof PsiReferenceExpression && qualifier2 instanceof PsiReferenceExpression &&
372           !match.areCorrespond(((PsiReferenceExpression)qualifier1).resolve(), ((PsiReferenceExpression)qualifier2).resolve())) {
373         return false;
374       }
375
376       if (qualifier1 == null && qualifier2 == null) {
377         final PsiClass patternClass = RefactoringChangeUtil.getThisClass(pattern);
378         final PsiClass candidateClass = RefactoringChangeUtil.getThisClass(candidate);
379         if (resolveResult1 == resolveResult2 &&
380             resolveResult1 instanceof PsiMember) {
381           final PsiClass containingClass = ((PsiMember)resolveResult1).getContainingClass();
382           if (!InheritanceUtil.isInheritorOrSelf(candidateClass, patternClass, true) &&
383               InheritanceUtil.isInheritorOrSelf(candidateClass, containingClass, true) &&
384               InheritanceUtil.isInheritorOrSelf(patternClass, containingClass, true)) {
385             return false;
386           }
387         }
388       }
389
390     }
391
392     if (pattern instanceof PsiTypeCastExpression) {
393       final PsiTypeElement castTypeElement1 = ((PsiTypeCastExpression)pattern).getCastType();
394       final PsiTypeElement castTypeElement2 = ((PsiTypeCastExpression)candidate).getCastType();
395       if (castTypeElement1 != null && castTypeElement2 != null) {
396         final PsiType type1 = TypeConversionUtil.erasure(castTypeElement1.getType());
397         final PsiType type2 = TypeConversionUtil.erasure(castTypeElement2.getType());
398         if (!type1.equals(type2)) return false;
399       }
400     } else if (pattern instanceof PsiNewExpression) {
401       final PsiType type1 = ((PsiNewExpression)pattern).getType();
402       final PsiType type2 = ((PsiNewExpression)candidate).getType();
403       if (type1 == null || type2 == null) return false;
404       final PsiMethod constructor1 = ((PsiNewExpression)pattern).resolveConstructor();
405       final PsiMethod constructor2 = ((PsiNewExpression)candidate).resolveConstructor();
406       if (constructor1 != null && constructor2 != null) {
407         if (!pattern.getManager().areElementsEquivalent(constructor1, constructor2)) return false;
408       }
409       else {
410         if (!canTypesBeEquivalent(type1, type2)) return false;
411       }
412     } else if (pattern instanceof PsiClassObjectAccessExpression) {
413       final PsiTypeElement operand1 = ((PsiClassObjectAccessExpression)pattern).getOperand();
414       final PsiTypeElement operand2 = ((PsiClassObjectAccessExpression)candidate).getOperand();
415       return operand1.getType().equals(operand2.getType());
416     } else if (pattern instanceof PsiInstanceOfExpression) {
417       final PsiTypeElement operand1 = ((PsiInstanceOfExpression)pattern).getCheckType();
418       final PsiTypeElement operand2 = ((PsiInstanceOfExpression)candidate).getCheckType();
419       if (operand1 == null || operand2 == null) return false;
420       if (!operand1.getType().equals(operand2.getType())) return false;
421     } else if (pattern instanceof PsiReturnStatement) {
422       final PsiReturnStatement patternReturnStatement = (PsiReturnStatement)pattern;
423       return matchReturnStatement(patternReturnStatement, candidate, candidates, match);
424     } else if (pattern instanceof PsiContinueStatement) {
425       match.registerReturnValue(new ContinueReturnValue());
426     } else if (pattern instanceof PsiBreakStatement) {
427       match.registerReturnValue(new BreakReturnValue());
428     }else if (pattern instanceof PsiMethodCallExpression) {
429       final PsiMethod patternMethod = ((PsiMethodCallExpression)pattern).resolveMethod();
430       final PsiMethod candidateMethod = ((PsiMethodCallExpression)candidate).resolveMethod();
431       if (patternMethod != null && candidateMethod != null) {
432         if (!MethodSignatureUtil.areSignaturesEqual(patternMethod, candidateMethod)) return false;
433       }
434     } else if (pattern instanceof PsiReferenceExpression) {
435       final PsiReferenceExpression patternRefExpr = (PsiReferenceExpression)pattern;
436       final PsiReferenceExpression candidateRefExpr = (PsiReferenceExpression)candidate;
437       final PsiExpression patternQualifier = patternRefExpr.getQualifierExpression();
438       final PsiExpression candidateQualifier = candidateRefExpr.getQualifierExpression();
439       if (patternQualifier == null) {
440         PsiClass contextClass = PsiTreeUtil.getContextOfType(pattern, PsiClass.class);
441         if (candidateQualifier instanceof PsiReferenceExpression) {
442           final PsiElement resolved = ((PsiReferenceExpression)candidateQualifier).resolve();
443           if (resolved instanceof PsiClass && contextClass != null && InheritanceUtil.isInheritorOrSelf(contextClass, (PsiClass)resolved, true)) {
444             return true;
445           }
446         }
447         return contextClass != null && match.registerInstanceExpression(candidateQualifier, contextClass);
448       } else {
449         if (candidateQualifier == null) {
450           if (patternQualifier instanceof PsiThisExpression) {
451             final PsiJavaCodeReferenceElement qualifier = ((PsiThisExpression)patternQualifier).getQualifier();
452             if (candidate instanceof PsiReferenceExpression) {
453               PsiElement contextClass = qualifier == null ? PsiTreeUtil.getContextOfType(pattern, PsiClass.class) : qualifier.resolve();
454               return contextClass instanceof PsiClass && match.registerInstanceExpression(((PsiReferenceExpression)candidate).getQualifierExpression(),
455                                                                                           (PsiClass)contextClass);
456             }
457           } else {
458             final PsiType type = patternQualifier.getType();
459             PsiClass contextClass = type instanceof PsiClassType ? ((PsiClassType)type).resolve() : null;
460             try {
461               final Pair<PsiVariable, PsiType> parameter = patternQualifier.getUserData(PARAMETER);
462
463               if (parameter != null) {
464                 final PsiClass thisClass = RefactoringChangeUtil.getThisClass(parameter.first);
465
466                 if (contextClass != null && InheritanceUtil.isInheritorOrSelf(thisClass, contextClass, true)) {
467                   contextClass = thisClass;
468                 }
469                 final PsiClass thisCandidate = RefactoringChangeUtil.getThisClass(candidate);
470                 if (thisCandidate != null && InheritanceUtil.isInheritorOrSelf(thisCandidate, contextClass, true)) {
471                   contextClass = thisCandidate;
472                 }
473                 return contextClass != null && match.putParameter(parameter, RefactoringChangeUtil
474                   .createThisExpression(patternQualifier.getManager(), contextClass));
475               } else if (patternQualifier instanceof PsiReferenceExpression) {
476                 final PsiElement resolved = ((PsiReferenceExpression)patternQualifier).resolve();
477                 if (resolved instanceof PsiClass) {
478                   final PsiClass classContext = PsiTreeUtil.getContextOfType(candidate, PsiClass.class);
479                   if (classContext != null && InheritanceUtil.isInheritorOrSelf(classContext, (PsiClass)resolved, true)) {
480                     return true;
481                   }
482                 }
483               }
484
485               return false;
486             }
487             catch (IncorrectOperationException e) {
488               LOG.error(e);
489             }
490           }
491         } else {
492           if (patternQualifier instanceof PsiThisExpression && candidateQualifier instanceof PsiThisExpression) {
493             final PsiJavaCodeReferenceElement thisPatternQualifier = ((PsiThisExpression)patternQualifier).getQualifier();
494             final PsiElement patternContextClass = thisPatternQualifier == null ? PsiTreeUtil.getContextOfType(patternQualifier, PsiClass.class) : thisPatternQualifier.resolve();
495             final PsiJavaCodeReferenceElement thisCandidateQualifier = ((PsiThisExpression)candidateQualifier).getQualifier();
496             final PsiElement candidateContextClass = thisCandidateQualifier == null ? PsiTreeUtil.getContextOfType(candidateQualifier, PsiClass.class) : thisCandidateQualifier.resolve();
497             return patternContextClass == candidateContextClass;
498           }
499         }
500       }
501     } else if (pattern instanceof PsiThisExpression) {
502       final PsiJavaCodeReferenceElement qualifier = ((PsiThisExpression)pattern).getQualifier();
503       final PsiElement contextClass = qualifier == null ? PsiTreeUtil.getContextOfType(pattern, PsiClass.class) : qualifier.resolve();
504       if (candidate instanceof PsiReferenceExpression) {
505         final PsiElement parent = candidate.getParent();
506         return parent instanceof PsiReferenceExpression && contextClass instanceof PsiClass && match.registerInstanceExpression(((PsiReferenceExpression)parent).getQualifierExpression(),
507                                                                                     (PsiClass)contextClass);
508       } else if (candidate instanceof PsiThisExpression) {
509         final PsiJavaCodeReferenceElement candidateQualifier = ((PsiThisExpression)candidate).getQualifier();
510         final PsiElement candidateContextClass = candidateQualifier == null ? PsiTreeUtil.getContextOfType(candidate, PsiClass.class) : candidateQualifier.resolve();
511         return contextClass == candidateContextClass;
512       }
513     } else if (pattern instanceof PsiSuperExpression) {
514       final PsiJavaCodeReferenceElement qualifier = ((PsiSuperExpression)pattern).getQualifier();
515       final PsiElement contextClass = qualifier == null ? PsiTreeUtil.getContextOfType(pattern, PsiClass.class) : qualifier.resolve();
516       if (candidate instanceof PsiSuperExpression) {
517         final PsiJavaCodeReferenceElement candidateQualifier = ((PsiSuperExpression)candidate).getQualifier();
518         return contextClass == (candidateQualifier != null ? candidateQualifier.resolve() : PsiTreeUtil.getContextOfType(candidate, PsiClass.class));
519       }
520     } else if (pattern instanceof PsiModifierList) {
521       return candidate instanceof PsiModifierList && matchModifierList((PsiModifierList)pattern, (PsiModifierList)candidate);
522     }
523
524     PsiElement[] children1 = getFilteredChildren(pattern);
525     PsiElement[] children2 = getFilteredChildren(candidate);
526     if (children1.length != children2.length) return false;
527
528
529     for (int i = 0; i < children1.length; i++) {
530       PsiElement child1 = children1[i];
531       PsiElement child2 = children2[i];
532       if (!matchPattern(child1, child2, candidates, match)) return false;
533     }
534
535     if (children1.length == 0) {
536       if (pattern.getParent() instanceof PsiVariable && ((PsiVariable)pattern.getParent()).getNameIdentifier() == pattern) {
537         return match.putDeclarationCorrespondence(pattern.getParent(), candidate.getParent());
538       }
539       if (!pattern.textMatches(candidate)) return false;
540     }
541
542     return true;
543   }
544
545   private static boolean matchModifierList(PsiModifierList modifierList1, PsiModifierList modifierList2) {
546     if (!(modifierList1.getParent() instanceof PsiLocalVariable)) {
547       // local variables can only have a final modifier, and are considered equivalent with or without it.
548       for (String modifier : PsiModifier.MODIFIERS) {
549         if (modifierList1.hasModifierProperty(modifier)) {
550           if (!modifierList2.hasModifierProperty(modifier)) {
551             return false;
552           }
553         }
554         else if (modifierList2.hasModifierProperty(modifier)) {
555           return false;
556         }
557       }
558     }
559     final List<PsiAnnotation> annotations1 = ContainerUtil.newArrayList(modifierList1.getAnnotations());
560     final List<PsiAnnotation> annotations2 = ContainerUtil.newArrayList(modifierList2.getAnnotations());
561     annotations1.removeIf(a -> CommonClassNames.JAVA_LANG_OVERRIDE.equals(a.getQualifiedName()));
562     annotations2.removeIf(a -> CommonClassNames.JAVA_LANG_OVERRIDE.equals(a.getQualifiedName()));
563     if (annotations1.size() != annotations2.size()) {
564       return false;
565     }
566     for (final Iterator<PsiAnnotation> iterator = annotations1.iterator(); iterator.hasNext(); ) {
567       final PsiAnnotation annotation1 = iterator.next();
568       for (final Iterator<PsiAnnotation> iterator2 = annotations2.iterator(); iterator2.hasNext(); ) {
569         final PsiAnnotation annotation2 = iterator2.next();
570         if (PsiEquivalenceUtil.areElementsEquivalent(annotation1, annotation2)) {
571           iterator.remove();
572           iterator2.remove();
573         }
574       }
575     }
576     return true;
577   }
578
579   private static boolean checkParameterModification(PsiExpression expression,
580                                                     final IElementType sign,
581                                                     PsiExpression candidate) {
582     expression = PsiUtil.skipParenthesizedExprDown(expression);
583     candidate = PsiUtil.skipParenthesizedExprDown(candidate);
584     if (expression instanceof PsiReferenceExpression && ((PsiReferenceExpression)expression).resolve() instanceof PsiParameter &&
585         (sign.equals(JavaTokenType.MINUSMINUS)|| sign.equals(JavaTokenType.PLUSPLUS))) {
586       if (candidate instanceof PsiReferenceExpression && ((PsiReferenceExpression)candidate).resolve() instanceof PsiParameter) {
587         return false;
588       }
589       return true;
590     }
591     return false;
592   }
593
594   private static void traverseParameter(PsiElement pattern, PsiElement candidate, Match match) {
595     if (pattern == null || candidate == null) return;
596     if (pattern.getUserData(PARAMETER) != null) {
597       final Pair<PsiVariable, PsiType> parameter = pattern.getUserData(PARAMETER);
598       match.putParameter(parameter, candidate);
599       return;
600     }
601
602     PsiElement[] children1 = getFilteredChildren(pattern);
603     PsiElement[] children2 = getFilteredChildren(candidate);
604     if (children1.length != children2.length) return;
605
606     for (int i = 0; i < children1.length; i++) {
607       PsiElement child1 = children1[i];
608       PsiElement child2 = children2[i];
609       traverseParameter(child1, child2, match);
610     }
611   }
612
613   private boolean matchReturnStatement(final PsiReturnStatement patternReturnStatement,
614                                        PsiElement candidate,
615                                        List<PsiElement> candidates,
616                                        Match match) {
617     if (candidate instanceof PsiExpressionStatement) {
618       final PsiExpression expression = ((PsiExpressionStatement)candidate).getExpression();
619       if (expression instanceof PsiAssignmentExpression) {
620         final PsiExpression returnValue = patternReturnStatement.getReturnValue();
621         final PsiExpression rExpression = ((PsiAssignmentExpression)expression).getRExpression();
622         if (!matchPattern(returnValue, rExpression, candidates, match)) return false;
623         final PsiExpression lExpression = ((PsiAssignmentExpression)expression).getLExpression();
624         return match.registerReturnValue(new ExpressionReturnValue(lExpression));
625       }
626       else return false;
627     }
628     else if (candidate instanceof PsiDeclarationStatement) {
629       final PsiElement[] declaredElements = ((PsiDeclarationStatement)candidate).getDeclaredElements();
630       if (declaredElements.length != 1) return false;
631       if (!(declaredElements[0] instanceof PsiVariable)) return false;
632       final PsiVariable variable = (PsiVariable)declaredElements[0];
633       if (!matchPattern(patternReturnStatement.getReturnValue(), variable.getInitializer(), candidates, match)) return false;
634       return match.registerReturnValue(new VariableReturnValue(variable));
635     }
636     else if (candidate instanceof PsiReturnStatement) {
637       final PsiExpression returnValue = PsiUtil.skipParenthesizedExprDown(((PsiReturnStatement)candidate).getReturnValue());
638       if (myMultipleExitPoints) {
639         return match.registerReturnValue(new ConditionalReturnStatementValue(returnValue));
640       }
641       else {
642         final PsiElement classOrLambda = PsiTreeUtil.getContextOfType(returnValue, PsiClass.class, PsiLambdaExpression.class);
643         final PsiElement commonParent = PsiTreeUtil.findCommonParent(match.getMatchStart(), match.getMatchEnd());
644         if (classOrLambda == null || !PsiTreeUtil.isAncestor(commonParent, classOrLambda, false)) {
645           if (returnValue != null && !match.registerReturnValue(ReturnStatementReturnValue.INSTANCE)) return false; //do not register return value for return; statement
646         }
647         return matchPattern(PsiUtil.skipParenthesizedExprDown(patternReturnStatement.getReturnValue()), returnValue, candidates, match);
648       }
649     }
650     else return false;
651   }
652
653   private static boolean equivalentResolve(final PsiElement resolveResult1, final PsiElement resolveResult2, PsiElement qualifier2) {
654     if (Comparing.equal(resolveResult1, resolveResult2)) return true;
655     if (resolveResult1 instanceof PsiMethod && resolveResult2 instanceof PsiMethod) {
656       final PsiMethod method1 = (PsiMethod)resolveResult1;
657       final PsiMethod method2 = (PsiMethod)resolveResult2;
658       if (method1.hasModifierProperty(PsiModifier.STATIC)) return false; // static methods don't inherit
659       if (ArrayUtil.find(method1.findSuperMethods(), method2) >= 0) return true;
660       if (ArrayUtil.find(method2.findSuperMethods(), method1) >= 0) return true;
661
662       if (method1.getName().equals(method2.getName())) {
663         PsiClass class2 = method2.getContainingClass();
664         if (qualifier2 instanceof PsiReferenceExpression) {
665           final PsiType type = ((PsiReferenceExpression)qualifier2).getType();
666           if (type instanceof PsiClassType){
667             final PsiClass resolvedClass = PsiUtil.resolveClassInType(type);
668             if (!(resolvedClass instanceof PsiTypeParameter)) {
669               class2 = resolvedClass;
670             }
671           }
672         }
673
674         if (class2 != null && PsiUtil.isAccessible(method1, class2, null)) {
675           final PsiMethod[] methods = class2.getAllMethods();
676           if (ArrayUtil.find(methods, method1) != -1) return true;
677         }
678       }
679       return false;
680     }
681     else {
682       return false;
683     }
684   }
685
686   private static boolean isUnder(PsiElement element, List<PsiElement> parents) {
687     if (element == null) return false;
688     for (final PsiElement parent : parents) {
689       if (PsiTreeUtil.isAncestor(parent, element, false)) return true;
690     }
691     return false;
692   }
693
694   public static PsiElement[] getFilteredChildren(PsiElement element1) {
695     PsiElement[] children1 = element1.getChildren();
696     ArrayList<PsiElement> array = new ArrayList<>();
697     for (PsiElement child : children1) {
698       if (!(child instanceof PsiWhiteSpace) && !(child instanceof PsiComment) && !(child instanceof PsiEmptyStatement)) {
699         if (child instanceof PsiBlockStatement) {
700           child = ((PsiBlockStatement)child).getCodeBlock();
701         }
702         if (child instanceof PsiCodeBlock) {
703           final PsiStatement[] statements = ((PsiCodeBlock)child).getStatements();
704           for (PsiStatement statement : statements) {
705             if (statement instanceof PsiBlockStatement) {
706               Collections.addAll(array, getFilteredChildren(statement));
707             } else if (!(statement instanceof PsiEmptyStatement)) {
708               array.add(statement);
709             }
710           }
711           continue;
712         } else if (child instanceof PsiParenthesizedExpression) {
713           array.add(PsiUtil.skipParenthesizedExprDown((PsiParenthesizedExpression)child));
714           continue;
715         }
716         array.add(child);
717       }
718     }
719     return PsiUtilCore.toPsiElementArray(array);
720   }
721
722 }