java/java-impl/src/com/intellij/refactoring/util/duplicates/DuplicatesFinder.java

   1 /*
   2  * Copyright 2000-2009 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.InheritanceUtil;
  29 import com.intellij.psi.util.PsiTreeUtil;
  30 import com.intellij.psi.util.PsiUtil;
  31 import com.intellij.psi.util.TypeConversionUtil;
  32 import com.intellij.refactoring.extractMethod.InputVariables;
  33 import com.intellij.refactoring.util.RefactoringUtil;
  34 import com.intellij.util.ArrayUtil;
  35 import com.intellij.util.IncorrectOperationException;
  36 import com.intellij.util.containers.IntArrayList;
  37 import org.jetbrains.annotations.Nullable;
  38
  39 import java.util.*;
  40
  41 /**
  42  * @author dsl
  43  */
  44 public class DuplicatesFinder {
  45   private static final Logger LOG = Logger.getInstance("#com.intellij.refactoring.util.duplicates.DuplicatesFinder");
  46   public static final Key<Pair<PsiVariable, PsiType>> PARAMETER = Key.create("PARAMETER");
  47   private final PsiElement[] myPattern;
  48   private InputVariables myParameters;
  49   private final List<? extends PsiVariable> myOutputParameters;
  50   private final List<PsiElement> myPatternAsList;
  51   private boolean myMultipleExitPoints = false;
  52   private final ReturnValue myReturnValue;
  53
  54   public DuplicatesFinder(PsiElement[] pattern,
  55                           InputVariables parameters,
  56                           ReturnValue returnValue,
  57                           List<? extends PsiVariable> outputParameters
  58   ) {
  59     myReturnValue = returnValue;
  60     LOG.assertTrue(pattern.length > 0);
  61     myPattern = pattern;
  62     myPatternAsList = Arrays.asList(myPattern);
  63     myParameters = parameters;
  64     myOutputParameters = outputParameters;
  65
  66     final PsiElement codeFragment = ControlFlowUtil.findCodeFragment(pattern[0]);
  67     try {
  68       final ControlFlow controlFlow = ControlFlowFactory.getInstance(codeFragment.getProject()).getControlFlow(codeFragment, new LocalsControlFlowPolicy(codeFragment), false);
  69
  70       int startOffset;
  71       int i = 0;
  72       do {
  73         startOffset = controlFlow.getStartOffset(pattern[i++]);
  74       } while(startOffset < 0 && i < pattern.length);
  75
  76       int endOffset;
  77       int j = pattern.length - 1;
  78       do {
  79         endOffset = controlFlow.getEndOffset(pattern[j--]);
  80       } while(endOffset < 0 && j >= 0);
  81
  82       IntArrayList exitPoints = new IntArrayList();
  83       final Collection<PsiStatement> exitStatements = ControlFlowUtil
  84           .findExitPointsAndStatements(controlFlow, startOffset, endOffset, exitPoints, ControlFlowUtil.DEFAULT_EXIT_STATEMENTS_CLASSES);
  85       myMultipleExitPoints = exitPoints.size() > 1;
  86
  87       if (myMultipleExitPoints) {
  88         myParameters.removeParametersUsedInExitsOnly(codeFragment, exitStatements, controlFlow, startOffset, endOffset);
  89       }
  90     }
  91     catch (AnalysisCanceledException e) {
  92     }
  93   }
  94
  95   public DuplicatesFinder(final PsiElement[] pattern,
  96                           final InputVariables psiParameters,
  97                           final List<? extends PsiVariable> psiVariables) {
  98     this(pattern, psiParameters, null, psiVariables);
  99   }
 100
 101
 102
 103
 104   public List<Match> findDuplicates(PsiElement scope) {
 105     annotatePattern();
 106     final ArrayList<Match> result = new ArrayList<Match>();
 107     findPatternOccurrences(result, scope);
 108     deannotatePattern();
 109     return result;
 110   }
 111
 112   private void annotatePattern() {
 113     for (final PsiElement patternComponent : myPattern) {
 114       patternComponent.accept(new JavaRecursiveElementWalkingVisitor() {
 115         @Override public void visitReferenceElement(PsiJavaCodeReferenceElement reference) {
 116           final PsiElement element = reference.resolve();
 117           if (element instanceof PsiVariable) {
 118             final PsiVariable variable = (PsiVariable)element;
 119             PsiType type = variable.getType();
 120             myParameters.annotateWithParameter(reference);
 121             if (myOutputParameters.contains(element)) {
 122               reference.putUserData(PARAMETER, Pair.create(variable, type));
 123             }
 124           }
 125           PsiElement qualifier = reference.getQualifier();
 126           if (qualifier != null) {
 127             qualifier.accept(this);
 128           }
 129         }
 130       });
 131     }
 132   }
 133
 134   private void deannotatePattern() {
 135     for (final PsiElement patternComponent : myPattern) {
 136       patternComponent.accept(new JavaRecursiveElementWalkingVisitor() {
 137         @Override public void visitReferenceElement(PsiJavaCodeReferenceElement reference) {
 138           if (reference.getUserData(PARAMETER) != null) {
 139             reference.putUserData(PARAMETER, null);
 140           }
 141         }
 142       });
 143     }
 144   }
 145
 146   private void findPatternOccurrences(List<Match> array, PsiElement scope) {
 147     PsiElement[] children = scope.getChildren();
 148     for (PsiElement child : children) {
 149       final Match match = isDuplicateFragment(child);
 150       if (match != null) {
 151         array.add(match);
 152         continue;
 153       }
 154       findPatternOccurrences(array, child);
 155     }
 156   }
 157
 158
 159   @Nullable
 160   private Match isDuplicateFragment(PsiElement candidate) {
 161     if (PsiTreeUtil.isAncestor(myPattern[0], candidate, false)) return null;
 162     PsiElement sibling = candidate;
 163     ArrayList<PsiElement> candidates = new ArrayList<PsiElement>();
 164     for (final PsiElement element : myPattern) {
 165       if (sibling == null) return null;
 166       if (!canBeEquivalent(element, sibling)) return null;
 167       candidates.add(sibling);
 168       sibling = PsiTreeUtil.skipSiblingsForward(sibling, PsiWhiteSpace.class, PsiComment.class);
 169     }
 170     LOG.assertTrue(myPattern.length == candidates.size());
 171     if (myPattern.length == 1 && myPattern[0] instanceof PsiExpression) {
 172       if (candidates.get(0) instanceof PsiExpression) {
 173         final PsiExpression candidateExpression = (PsiExpression)candidates.get(0);
 174         if (PsiUtil.isAccessedForWriting(candidateExpression)) return null;
 175         final PsiType patternType = ((PsiExpression)myPattern[0]).getType();
 176         final PsiType candidateType = candidateExpression.getType();
 177         PsiSubstitutor substitutor = PsiSubstitutor.EMPTY;
 178         final PsiMethod method = PsiTreeUtil.getParentOfType(myPattern[0], PsiMethod.class);
 179         if (method != null) {
 180           final PsiResolveHelper resolveHelper = JavaPsiFacade.getInstance(candidate.getProject()).getResolveHelper();
 181           substitutor = resolveHelper.inferTypeArguments(method.getTypeParameters(), new PsiType[]{patternType},
 182                                                          new PsiType[]{candidateType}, PsiUtil.getLanguageLevel(method));
 183         }
 184         if (!canTypesBeEquivalent(substitutor.substitute(patternType), candidateType)) return null;
 185       }
 186       else {
 187         return null;
 188       }
 189
 190     }
 191     final Match match = new Match(candidates.get(0), candidates.get(candidates.size() - 1));
 192     for (int i = 0; i < myPattern.length; i++) {
 193       if (!matchPattern(myPattern[i], candidates.get(i), candidates, match)) return null;
 194     }
 195
 196     if (checkPostVariableUsages(candidates, match)) return null;
 197
 198     return match;
 199   }
 200
 201   private boolean checkPostVariableUsages(final ArrayList<PsiElement> candidates, final Match match) {
 202     final PsiElement codeFragment = ControlFlowUtil.findCodeFragment(candidates.get(0));
 203     try {
 204       final ControlFlow controlFlow = ControlFlowFactory.getInstance(codeFragment.getProject()).getControlFlow(codeFragment, new LocalsControlFlowPolicy(codeFragment), false);
 205
 206       int startOffset;
 207       int i = 0;
 208       do {
 209         startOffset = controlFlow.getStartOffset(candidates.get(i++));
 210       } while(startOffset < 0 && i < candidates.size());
 211
 212       int endOffset;
 213       int j = candidates.size() - 1;
 214       do {
 215         endOffset = controlFlow.getEndOffset(candidates.get(j--));
 216       } while(endOffset < 0 && j >= 0);
 217
 218       final IntArrayList exitPoints = new IntArrayList();
 219       ControlFlowUtil.findExitPointsAndStatements(controlFlow, startOffset, endOffset, exitPoints, ControlFlowUtil.DEFAULT_EXIT_STATEMENTS_CLASSES);
 220       final PsiVariable[] outVariables = ControlFlowUtil.getOutputVariables(controlFlow, startOffset, endOffset, exitPoints.toArray());
 221
 222       if (outVariables.length > 0) {
 223         if (outVariables.length == 1) {
 224           ReturnValue returnValue = match.getReturnValue();
 225           if (returnValue == null) {
 226             returnValue = myReturnValue;
 227           }
 228           if (returnValue instanceof VariableReturnValue) {
 229             final ReturnValue value = match.getOutputVariableValue(((VariableReturnValue)returnValue).getVariable());
 230             if (value != null) {
 231               if (value.isEquivalent(new VariableReturnValue(outVariables[0]))) return false;
 232               if (value instanceof ExpressionReturnValue) {
 233                 final PsiExpression expression = ((ExpressionReturnValue)value).getExpression();
 234                 if (expression instanceof PsiReferenceExpression) {
 235                   final PsiElement variable = ((PsiReferenceExpression)expression).resolve();
 236                   return variable == null || !PsiEquivalenceUtil.areElementsEquivalent(variable, outVariables[0]);
 237                 }
 238               }
 239             }
 240           }
 241         }
 242         return true;
 243       }
 244     }
 245     catch (AnalysisCanceledException e) {
 246     }
 247     return false;
 248   }
 249
 250   private static boolean canTypesBeEquivalent(PsiType type1, PsiType type2) {
 251     if (type1 == null || type2 == null) return false;
 252     if (!type2.isAssignableFrom(type1)) {
 253       if (type1 instanceof PsiImmediateClassType && type2 instanceof PsiImmediateClassType) {
 254         final PsiClass psiClass1 = ((PsiImmediateClassType)type1).resolve();
 255         final PsiClass psiClass2 = ((PsiImmediateClassType)type2).resolve();
 256         if (!(psiClass1 instanceof PsiAnonymousClass &&
 257               psiClass2 instanceof PsiAnonymousClass &&
 258               psiClass1.getManager().areElementsEquivalent(((PsiAnonymousClass)psiClass1).getBaseClassType().resolve(),
 259                                                            ((PsiAnonymousClass)psiClass2).getBaseClassType().resolve()))) {
 260           return false;
 261         }
 262       }
 263       else {
 264         return false;
 265       }
 266     }
 267     return true;
 268   }
 269
 270   private static boolean canBeEquivalent(final PsiElement pattern, PsiElement candidate) {
 271     if (pattern instanceof PsiReturnStatement && candidate instanceof PsiExpressionStatement) return true;
 272     if (pattern instanceof PsiReturnStatement && candidate instanceof PsiDeclarationStatement) return true;
 273     if (pattern instanceof PsiThisExpression && candidate instanceof PsiReferenceExpression) return true;
 274     final ASTNode node1 = pattern.getNode();
 275     final ASTNode node2 = candidate.getNode();
 276     if (node1 == null || node2 == null) return false;
 277     return node1.getElementType() == node2.getElementType();
 278   }
 279
 280   private boolean matchPattern(PsiElement pattern,
 281                                PsiElement candidate,
 282                                List<PsiElement> candidates,
 283                                Match match) {
 284     if (pattern == null || candidate == null) return pattern == candidate;
 285     if (pattern.getUserData(PARAMETER) != null) {
 286       final Pair<PsiVariable, PsiType> parameter = pattern.getUserData(PARAMETER);
 287       return match.putParameter(parameter, candidate);
 288     }
 289
 290     if (!canBeEquivalent(pattern, candidate)) return false; // Q : is it correct to check implementation classes?
 291
 292     if (pattern instanceof PsiExpressionList && candidate instanceof PsiExpressionList) { //check varargs
 293       final PsiExpression[] expressions = ((PsiExpressionList)pattern).getExpressions();
 294       final PsiExpression[] childExpressions = ((PsiExpressionList)candidate).getExpressions();
 295       if (expressions.length < childExpressions.length && expressions.length > 0 && expressions[expressions.length - 1] instanceof PsiReferenceExpression) {
 296         final PsiElement resolved = ((PsiReferenceExpression)expressions[expressions.length - 1]).resolve();
 297         if (resolved instanceof PsiParameter && ((PsiParameter)resolved).getType() instanceof PsiEllipsisType) {
 298           for(int i = 0; i < expressions.length - 1; i++) {
 299             final Pair<PsiVariable, PsiType> parameter = expressions[i].getUserData(PARAMETER);
 300             if (parameter == null) return false;
 301             if (!match.putParameter(parameter, childExpressions[i])) return false;
 302           }
 303           final Pair<PsiVariable, PsiType> param = expressions[expressions.length - 1].getUserData(PARAMETER);
 304           if (param == null) return false;
 305           for(int i = expressions.length - 1; i < childExpressions.length; i++) {
 306             if (!match.putParameter(param, childExpressions[i])) return false;
 307           }
 308           return true;
 309         }
 310       }
 311     }
 312
 313     if (pattern instanceof PsiAssignmentExpression) {
 314       final PsiExpression lExpression = ((PsiAssignmentExpression)pattern).getLExpression();
 315       if (lExpression.getType() instanceof PsiPrimitiveType &&
 316           lExpression instanceof PsiReferenceExpression &&
 317           ((PsiReferenceExpression)lExpression).resolve() instanceof PsiParameter) {
 318         return false;
 319       }
 320     } else if (pattern instanceof PsiPrefixExpression) {
 321       if (checkParameterModification(((PsiPrefixExpression)pattern).getOperand(), ((PsiPrefixExpression)pattern).getOperationTokenType())) return false;
 322     } else if (pattern instanceof PsiPostfixExpression) {
 323       if (checkParameterModification(((PsiPostfixExpression)pattern).getOperand(), ((PsiPostfixExpression)pattern).getOperationTokenType())) return false;
 324     }
 325
 326     if (pattern instanceof PsiJavaCodeReferenceElement) {
 327       final PsiElement resolveResult1 = ((PsiJavaCodeReferenceElement)pattern).resolve();
 328       final PsiElement resolveResult2 = ((PsiJavaCodeReferenceElement)candidate).resolve();
 329       if (resolveResult1 instanceof PsiClass && resolveResult2 instanceof PsiClass) return true;
 330       if (isUnder(resolveResult1, myPatternAsList) && isUnder(resolveResult2, candidates)) {
 331         traverseParameter(resolveResult1, resolveResult2, match);
 332         return match.putDeclarationCorrespondence(resolveResult1, resolveResult2);
 333       }
 334       final PsiElement qualifier2 = ((PsiJavaCodeReferenceElement)candidate).getQualifier();
 335       if (!equivalentResolve(resolveResult1, resolveResult2, qualifier2)) {
 336         return false;
 337       }
 338     }
 339
 340     if (pattern instanceof PsiTypeCastExpression) {
 341       final PsiTypeElement castTypeElement1 = ((PsiTypeCastExpression)pattern).getCastType();
 342       final PsiTypeElement castTypeElement2 = ((PsiTypeCastExpression)candidate).getCastType();
 343       if (castTypeElement1 != null && castTypeElement2 != null) {
 344         final PsiType type1 = TypeConversionUtil.erasure(castTypeElement1.getType());
 345         final PsiType type2 = TypeConversionUtil.erasure(castTypeElement2.getType());
 346         if (!type1.equals(type2)) return false;
 347       }
 348     } else if (pattern instanceof PsiNewExpression) {
 349       final PsiType type1 = ((PsiNewExpression)pattern).getType();
 350       final PsiType type2 = ((PsiNewExpression)candidate).getType();
 351       if (type1 == null || type2 == null) return false;
 352       final PsiJavaCodeReferenceElement classReference1 = ((PsiNewExpression)pattern).getClassReference();
 353       final PsiJavaCodeReferenceElement classReference2 = ((PsiNewExpression)candidate).getClassReference();
 354       if (classReference1 != null && classReference2 != null) {
 355         final PsiElement resolved1 = classReference1.resolve();
 356         final PsiElement resolved2 = classReference2.resolve();
 357         if (!pattern.getManager().areElementsEquivalent(resolved1, resolved2)) return false;
 358       }
 359       else {
 360         if (!canTypesBeEquivalent(type1, type2)) return false;
 361       }
 362     } else if (pattern instanceof PsiClassObjectAccessExpression) {
 363       final PsiTypeElement operand1 = ((PsiClassObjectAccessExpression)pattern).getOperand();
 364       final PsiTypeElement operand2 = ((PsiClassObjectAccessExpression)candidate).getOperand();
 365       return operand1.getType().equals(operand2.getType());
 366     } else if (pattern instanceof PsiInstanceOfExpression) {
 367       final PsiTypeElement operand1 = ((PsiInstanceOfExpression)pattern).getCheckType();
 368       final PsiTypeElement operand2 = ((PsiInstanceOfExpression)candidate).getCheckType();
 369       if (operand1 == null || operand2 == null) return false;
 370       if (!operand1.getType().equals(operand2.getType())) return false;
 371     } else if (pattern instanceof PsiReturnStatement) {
 372       final PsiReturnStatement patternReturnStatement = (PsiReturnStatement)pattern;
 373       return matchReturnStatement(patternReturnStatement, candidate, candidates, match);
 374     } else if (pattern instanceof PsiContinueStatement) {
 375       match.registerReturnValue(new ContinueReturnValue());
 376     } else if (pattern instanceof PsiBreakStatement) {
 377       match.registerReturnValue(new BreakReturnValue());
 378     } else if (pattern instanceof PsiReferenceExpression) {
 379       final PsiReferenceExpression patternRefExpr = (PsiReferenceExpression)pattern;
 380       final PsiReferenceExpression candidateRefExpr = (PsiReferenceExpression)candidate;
 381       final PsiExpression patternQualifier = patternRefExpr.getQualifierExpression();
 382       final PsiExpression candidateQualifier = candidateRefExpr.getQualifierExpression();
 383       if (patternQualifier == null) {
 384         PsiClass contextClass = PsiTreeUtil.getParentOfType(pattern, PsiClass.class);
 385         return contextClass != null && match.registerInstanceExpression(candidateQualifier, contextClass);
 386       } else {
 387         if (candidateQualifier == null) {
 388           if (patternQualifier instanceof PsiThisExpression) {
 389             final PsiJavaCodeReferenceElement qualifier = ((PsiThisExpression)patternQualifier).getQualifier();
 390             if (candidate instanceof PsiReferenceExpression) {
 391               PsiElement contextClass = qualifier == null ? PsiTreeUtil.getParentOfType(pattern, PsiClass.class) : qualifier.resolve();
 392               return contextClass instanceof PsiClass && match.registerInstanceExpression(((PsiReferenceExpression)candidate).getQualifierExpression(),
 393                                                                                           (PsiClass)contextClass);
 394             }
 395           } else {
 396             final PsiType type = patternQualifier.getType();
 397             PsiClass contextClass = type instanceof PsiClassType ? ((PsiClassType)type).resolve() : null;
 398             try {
 399               final Pair<PsiVariable, PsiType> parameter = patternQualifier.getUserData(PARAMETER);
 400
 401               if (parameter != null) {
 402                 final PsiClass thisClass = RefactoringUtil.getThisClass(parameter.first);
 403
 404                 if (contextClass != null && InheritanceUtil.isInheritorOrSelf(thisClass, contextClass, true)) {
 405                   contextClass = thisClass;
 406                 }
 407                 return contextClass != null && match.putParameter(parameter, RefactoringUtil.createThisExpression(patternQualifier.getManager(), contextClass));
 408               }
 409
 410               return false;
 411             }
 412             catch (IncorrectOperationException e) {
 413               LOG.error(e);
 414             }
 415           }
 416         } else {
 417           if (patternQualifier instanceof PsiThisExpression && candidateQualifier instanceof PsiThisExpression) {
 418             final PsiJavaCodeReferenceElement thisPatternQualifier = ((PsiThisExpression)patternQualifier).getQualifier();
 419             final PsiElement patternContextClass = thisPatternQualifier == null ? PsiTreeUtil.getParentOfType(patternQualifier, PsiClass.class) : thisPatternQualifier.resolve();
 420             final PsiJavaCodeReferenceElement thisCandidateQualifier = ((PsiThisExpression)candidateQualifier).getQualifier();
 421             final PsiElement candidateContextClass = thisCandidateQualifier == null ? PsiTreeUtil.getParentOfType(candidateQualifier, PsiClass.class) : thisCandidateQualifier.resolve();
 422             return patternContextClass == candidateContextClass;
 423           }
 424         }
 425       }
 426     } else if (pattern instanceof PsiThisExpression) {
 427       final PsiJavaCodeReferenceElement qualifier = ((PsiThisExpression)pattern).getQualifier();
 428       final PsiElement contextClass = qualifier == null ? PsiTreeUtil.getParentOfType(pattern, PsiClass.class) : qualifier.resolve();
 429       if (candidate instanceof PsiReferenceExpression) {
 430         final PsiElement parent = candidate.getParent();
 431         return parent instanceof PsiReferenceExpression && contextClass instanceof PsiClass && match.registerInstanceExpression(((PsiReferenceExpression)parent).getQualifierExpression(),
 432                                                                                     (PsiClass)contextClass);
 433       } else if (candidate instanceof PsiThisExpression) {
 434         final PsiJavaCodeReferenceElement candidateQualifier = ((PsiThisExpression)candidate).getQualifier();
 435         final PsiElement candidateContextClass = candidateQualifier == null ? PsiTreeUtil.getParentOfType(candidate, PsiClass.class) : candidateQualifier.resolve();
 436         return contextClass == candidateContextClass;
 437       }
 438     }
 439
 440     PsiElement[] children1 = getFilteredChildren(pattern);
 441     PsiElement[] children2 = getFilteredChildren(candidate);
 442     if (children1.length != children2.length) return false;
 443
 444
 445     for (int i = 0; i < children1.length; i++) {
 446       PsiElement child1 = children1[i];
 447       PsiElement child2 = children2[i];
 448       if (!matchPattern(child1, child2, candidates, match)) return false;
 449     }
 450
 451     if (children1.length == 0) {
 452       if (pattern.getParent() instanceof PsiVariable && ((PsiVariable)pattern.getParent()).getNameIdentifier() == pattern) {
 453         return match.putDeclarationCorrespondence(pattern.getParent(), candidate.getParent());
 454       }
 455       if (!pattern.textMatches(candidate)) return false;
 456     }
 457
 458     return true;
 459   }
 460
 461   private static boolean checkParameterModification(final PsiExpression expression, final IElementType sign) {
 462     if (expression instanceof PsiReferenceExpression && ((PsiReferenceExpression)expression).resolve() instanceof PsiParameter &&
 463         (sign.equals(JavaTokenType.MINUSMINUS)|| sign.equals(JavaTokenType.PLUSPLUS))) {
 464       return true;
 465     }
 466     return false;
 467   }
 468
 469   private static void traverseParameter(PsiElement pattern, PsiElement candidate, Match match) {
 470     if (pattern == null || candidate == null) return;
 471     if (pattern.getUserData(PARAMETER) != null) {
 472       final Pair<PsiVariable, PsiType> parameter = pattern.getUserData(PARAMETER);
 473       match.putParameter(parameter, candidate);
 474       return;
 475     }
 476
 477     PsiElement[] children1 = getFilteredChildren(pattern);
 478     PsiElement[] children2 = getFilteredChildren(candidate);
 479     if (children1.length != children2.length) return;
 480
 481     for (int i = 0; i < children1.length; i++) {
 482       PsiElement child1 = children1[i];
 483       PsiElement child2 = children2[i];
 484       traverseParameter(child1, child2, match);
 485     }
 486   }
 487
 488   private boolean matchReturnStatement(final PsiReturnStatement patternReturnStatement,
 489                                        PsiElement candidate,
 490                                        List<PsiElement> candidates,
 491                                        Match match) {
 492     if (candidate instanceof PsiExpressionStatement) {
 493       final PsiExpression expression = ((PsiExpressionStatement)candidate).getExpression();
 494       if (expression instanceof PsiAssignmentExpression) {
 495         final PsiExpression returnValue = patternReturnStatement.getReturnValue();
 496         final PsiExpression rExpression = ((PsiAssignmentExpression)expression).getRExpression();
 497         if (!matchPattern(returnValue, rExpression, candidates, match)) return false;
 498         final PsiExpression lExpression = ((PsiAssignmentExpression)expression).getLExpression();
 499         return match.registerReturnValue(new ExpressionReturnValue(lExpression));
 500       }
 501       else return false;
 502     }
 503     else if (candidate instanceof PsiDeclarationStatement) {
 504       final PsiElement[] declaredElements = ((PsiDeclarationStatement)candidate).getDeclaredElements();
 505       if (declaredElements.length != 1) return false;
 506       if (!(declaredElements[0] instanceof PsiVariable)) return false;
 507       final PsiVariable variable = (PsiVariable)declaredElements[0];
 508       if (!matchPattern(patternReturnStatement.getReturnValue(), variable.getInitializer(), candidates, match)) return false;
 509       return match.registerReturnValue(new VariableReturnValue(variable));
 510     }
 511     else if (candidate instanceof PsiReturnStatement) {
 512       final PsiExpression returnValue = ((PsiReturnStatement)candidate).getReturnValue();
 513       if (myMultipleExitPoints) {
 514         return match.registerReturnValue(new ConditionalReturnStatementValue(returnValue));
 515       }
 516       else {
 517         if (returnValue != null && !match.registerReturnValue(ReturnStatementReturnValue.INSTANCE)) return false; //do not register return value for return; statement
 518         return matchPattern(patternReturnStatement.getReturnValue(), returnValue, candidates, match);
 519       }
 520     }
 521     else return false;
 522   }
 523
 524   private static boolean equivalentResolve(final PsiElement resolveResult1, final PsiElement resolveResult2, PsiElement qualifier2) {
 525     final boolean b = Comparing.equal(resolveResult1, resolveResult2);
 526     if (b) return b;
 527     if (resolveResult1 instanceof PsiMethod && resolveResult2 instanceof PsiMethod) {
 528       final PsiMethod method1 = (PsiMethod)resolveResult1;
 529       final PsiMethod method2 = (PsiMethod)resolveResult2;
 530       if (ArrayUtil.find(method1.findSuperMethods(), method2) >= 0) return true;
 531       if (ArrayUtil.find(method2.findSuperMethods(), method1) >= 0) return true;
 532
 533       if (method1.getName().equals(method2.getName())) {
 534         PsiClass class2 = method2.getContainingClass();
 535         if (qualifier2 instanceof PsiReferenceExpression) {
 536           final PsiType type = ((PsiReferenceExpression)qualifier2).getType();
 537           if (type instanceof PsiClassType){
 538             final PsiClass resolvedClass = PsiUtil.resolveClassInType(type);
 539             if (!(resolvedClass instanceof PsiTypeParameter)) {
 540               class2 = resolvedClass;
 541             }
 542           }
 543         }
 544
 545         if (class2 != null) {
 546           final PsiMethod[] methods = class2.getAllMethods();
 547           if (ArrayUtil.find(methods, method1) != -1) return true;
 548         }
 549       }
 550       return false;
 551     }
 552     else {
 553       return false;
 554     }
 555   }
 556
 557   private static boolean isUnder(PsiElement element, List<PsiElement> parents) {
 558     if (element == null) return false;
 559     for (final PsiElement parent : parents) {
 560       if (PsiTreeUtil.isAncestor(parent, element, false)) return true;
 561     }
 562     return false;
 563   }
 564
 565   private static PsiElement[] getFilteredChildren(PsiElement element1) {
 566     PsiElement[] children1 = element1.getChildren();
 567     ArrayList<PsiElement> array = new ArrayList<PsiElement>();
 568     for (PsiElement child : children1) {
 569       if (!(child instanceof PsiWhiteSpace) && !(child instanceof PsiComment)) {
 570         if (child instanceof PsiBlockStatement) {
 571           Collections.addAll(array, getFilteredChildren(child));
 572           continue;
 573         } else if (child instanceof PsiCodeBlock) {
 574           final PsiStatement[] statements = ((PsiCodeBlock)child).getStatements();
 575           if (statements.length == 1) {
 576             array.add(statements[0]);
 577             continue;
 578           }
 579         }
 580         array.add(child);
 581       }
 582     }
 583     return array.toArray(new PsiElement[array.size()]);
 584   }
 585
 586 }