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 }