org.eclipse.jdt.ui/core refactoring/org/eclipse/jdt/internal/corext/refactoring/rename/RippleMethodFinder2.java - jdt/eclipse.jdt.ui - Git at Google

 /*******************************************************************************
  * Copyright (c) 2000, 2011 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.jdt.internal.corext.refactoring.rename;

 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;

 import org.eclipse.core.runtime.Assert;
 import org.eclipse.core.runtime.CoreException;
 import org.eclipse.core.runtime.IProgressMonitor;
 import org.eclipse.core.runtime.OperationCanceledException;
 import org.eclipse.core.runtime.SubProgressMonitor;

 import org.eclipse.jdt.core.IMember;
 import org.eclipse.jdt.core.IMethod;
 import org.eclipse.jdt.core.IRegion;
 import org.eclipse.jdt.core.IType;
 import org.eclipse.jdt.core.ITypeHierarchy;
 import org.eclipse.jdt.core.JavaCore;
 import org.eclipse.jdt.core.JavaModelException;
 import org.eclipse.jdt.core.WorkingCopyOwner;
 import org.eclipse.jdt.core.search.IJavaSearchConstants;
 import org.eclipse.jdt.core.search.IJavaSearchScope;
 import org.eclipse.jdt.core.search.SearchEngine;
 import org.eclipse.jdt.core.search.SearchMatch;
 import org.eclipse.jdt.core.search.SearchParticipant;
 import org.eclipse.jdt.core.search.SearchPattern;
 import org.eclipse.jdt.core.search.SearchRequestor;

 import org.eclipse.jdt.internal.corext.refactoring.RefactoringScopeFactory;
 import org.eclipse.jdt.internal.corext.refactoring.base.ReferencesInBinaryContext;
 import org.eclipse.jdt.internal.corext.util.JavaModelUtil;
 import org.eclipse.jdt.internal.corext.util.SearchUtils;

 public class RippleMethodFinder2 {

 	private final IMethod fMethod;
 	private List<IMethod> fDeclarations;
 	private ITypeHierarchy fHierarchy;
 	private Map<IType, IMethod> fTypeToMethod;
 	private Set<IType> fRootTypes;
 	private MultiMap<IType, IType> fRootReps;
 	private Map<IType, ITypeHierarchy> fRootHierarchies;
 	private UnionFind fUnionFind;

 	private final boolean fExcludeBinaries;
 	private final ReferencesInBinaryContext fBinaryRefs;
 	private Map<IMethod, SearchMatch> fDeclarationToMatch;

 	private static class MultiMap<K, V> {
 		HashMap<K, Collection<V>> fImplementation= new HashMap<K, Collection<V>>();

 		public void put(K key, V value) {
 			Collection<V> collection= fImplementation.get(key);
 			if (collection == null) {
 				collection= new HashSet<V>();
 				fImplementation.put(key, collection);
 			}
 			collection.add(value);
 		}

 		public Collection<V> get(K key) {
 			return fImplementation.get(key);
 		}
 	}
 	private static class UnionFind {
 		HashMap<IType, IType> fElementToRepresentative= new HashMap<IType, IType>();

 		public void init(IType type) {
 			fElementToRepresentative.put(type, type);
 		}

 		//path compression:
 		public IType find(IType element) {
 			IType root= element;
 			IType rep= fElementToRepresentative.get(root);
 			while (rep != null && ! rep.equals(root)) {
 				root= rep;
 				rep= fElementToRepresentative.get(root);
 			}
 			if (rep == null)
 				return null;

 			rep= fElementToRepresentative.get(element);
 			while (! rep.equals(root)) {
 				IType temp= element;
 				element= rep;
 				fElementToRepresentative.put(temp, root);
 				rep= fElementToRepresentative.get(element);
 			}
 			return root;
 		}

 //		//straightforward:
 //		public IType find(IType element) {
 //			IType current= element;
 //			IType rep= (IType) fElementToRepresentative.get(current);
 //			while (rep != null && ! rep.equals(current)) {
 //				current= rep;
 //				rep= (IType) fElementToRepresentative.get(current);
 //			}
 //			if (rep == null)
 //				return null;
 //			else
 //				return current;
 //		}

 		public void union(IType rep1, IType rep2) {
 			fElementToRepresentative.put(rep1, rep2);
 		}
 	}


 	private RippleMethodFinder2(IMethod method, boolean excludeBinaries){
 		fMethod= method;
 		fExcludeBinaries= excludeBinaries;
 		fBinaryRefs= null;
 	}

 	private RippleMethodFinder2(IMethod method, ReferencesInBinaryContext binaryRefs) {
 		fMethod= method;
 		fExcludeBinaries= true;
 		fDeclarationToMatch= new HashMap<IMethod, SearchMatch>();
 		fBinaryRefs= binaryRefs;
 	}

 	public static IMethod[] getRelatedMethods(IMethod method, boolean excludeBinaries, IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
 		try{
 			if (! MethodChecks.isVirtual(method))
 				return new IMethod[]{ method };

 			return new RippleMethodFinder2(method, excludeBinaries).getAllRippleMethods(pm, owner);
 		} finally{
 			pm.done();
 		}
 	}
 	public static IMethod[] getRelatedMethods(IMethod method, IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
 		return getRelatedMethods(method, true, pm, owner);
 	}

 	public static IMethod[] getRelatedMethods(IMethod method, ReferencesInBinaryContext binaryRefs, IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
 		try {
 			if (! MethodChecks.isVirtual(method))
 				return new IMethod[]{ method };

 			return new RippleMethodFinder2(method, binaryRefs).getAllRippleMethods(pm, owner);
 		} finally{
 			pm.done();
 		}
 	}

 	private IMethod[] getAllRippleMethods(IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
 		IMethod[] rippleMethods= findAllRippleMethods(pm, owner);
 		if (fDeclarationToMatch == null)
 			return rippleMethods;

 		List<IMethod> rippleMethodsList= new ArrayList<IMethod>(Arrays.asList(rippleMethods));
 		for (Iterator<IMethod> iter= rippleMethodsList.iterator(); iter.hasNext(); ) {
 			Object match= fDeclarationToMatch.get(iter.next());
 			if (match != null) {
 				iter.remove();
 				fBinaryRefs.add((SearchMatch) match);
 			}
 		}
 		fDeclarationToMatch= null;
 		return rippleMethodsList.toArray(new IMethod[rippleMethodsList.size()]);
 	}

 	private IMethod[] findAllRippleMethods(IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
 		pm.beginTask("", 4); //$NON-NLS-1$

 		findAllDeclarations(new SubProgressMonitor(pm, 1), owner);

 		//TODO: report assertion as error status and fall back to only return fMethod
 		//check for bug 81058:
 		if (! fDeclarations.contains(fMethod))
 			Assert.isTrue(false, "Search for method declaration did not find original element: " + fMethod.toString()); //$NON-NLS-1$

 		createHierarchyOfDeclarations(new SubProgressMonitor(pm, 1), owner);
 		createTypeToMethod();
 		createUnionFind();
 		if (pm.isCanceled())
 			throw new OperationCanceledException();

 		fHierarchy= null;
 		fRootTypes= null;

 		Map<IType, List<IType>> partitioning= new HashMap<IType, List<IType>>();
 		for (Iterator<IType> iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
 			IType type= iter.next();
 			IType rep= fUnionFind.find(type);
 			List<IType> types= partitioning.get(rep);
 			if (types == null)
 				types= new ArrayList<IType>();
 			types.add(type);
 			partitioning.put(rep, types);
 		}
 		Assert.isTrue(partitioning.size() > 0);
 		if (partitioning.size() == 1)
 			return fDeclarations.toArray(new IMethod[fDeclarations.size()]);

 		//Multiple partitions; must look out for nasty marriage cases
 		//(types inheriting method from two ancestors, but without redeclaring it).
 		IType methodTypeRep= fUnionFind.find(fMethod.getDeclaringType());
 		List<IType> relatedTypes= partitioning.get(methodTypeRep);
 		boolean hasRelatedInterfaces= false;
 		List<IMethod> relatedMethods= new ArrayList<IMethod>();
 		for (Iterator<IType> iter= relatedTypes.iterator(); iter.hasNext();) {
 			IType relatedType= iter.next();
 			relatedMethods.add(fTypeToMethod.get(relatedType));
 			if (relatedType.isInterface())
 				hasRelatedInterfaces= true;
 		}

 		//Definition: An alien type is a type that is not a related type. The set of
 		// alien types diminishes as new types become related (a.k.a marry a relatedType).

 		List<IMethod> alienDeclarations= new ArrayList<IMethod>(fDeclarations);
 		fDeclarations= null;
 		alienDeclarations.removeAll(relatedMethods);
 		List<IType> alienTypes= new ArrayList<IType>();
 		boolean hasAlienInterfaces= false;
 		for (Iterator<IMethod> iter= alienDeclarations.iterator(); iter.hasNext();) {
 			IMethod alienDeclaration= iter.next();
 			IType alienType= alienDeclaration.getDeclaringType();
 			alienTypes.add(alienType);
 			if (alienType.isInterface())
 				hasAlienInterfaces= true;
 		}
 		if (alienTypes.size() == 0) //no nasty marriage scenarios without types to marry with...
 			return relatedMethods.toArray(new IMethod[relatedMethods.size()]);
 		if (! hasRelatedInterfaces && ! hasAlienInterfaces) //no nasty marriage scenarios without interfaces...
 			return relatedMethods.toArray(new IMethod[relatedMethods.size()]);

 		//find all subtypes of related types:
 		HashSet<IType> relatedSubTypes= new HashSet<IType>();
 		List<IType> relatedTypesToProcess= new ArrayList<IType>(relatedTypes);
 		while (relatedTypesToProcess.size() > 0) {
 			//TODO: would only need subtype hierarchies of all top-of-ripple relatedTypesToProcess
 			for (Iterator<IType> iter= relatedTypesToProcess.iterator(); iter.hasNext();) {
 				if (pm.isCanceled())
 					throw new OperationCanceledException();
 				IType relatedType= iter.next();
 				ITypeHierarchy hierarchy= getCachedHierarchy(relatedType, owner, new SubProgressMonitor(pm, 1));
 				if (hierarchy == null)
 					hierarchy= relatedType.newTypeHierarchy(owner, new SubProgressMonitor(pm, 1));
 				IType[] allSubTypes= hierarchy.getAllSubtypes(relatedType);
 				for (int i= 0; i < allSubTypes.length; i++)
 					relatedSubTypes.add(allSubTypes[i]);
 			}
 			relatedTypesToProcess.clear(); //processed; make sure loop terminates

 			HashSet<IType> marriedAlienTypeReps= new HashSet<IType>();
 			for (Iterator<IType> iter= alienTypes.iterator(); iter.hasNext();) {
 				if (pm.isCanceled())
 					throw new OperationCanceledException();
 				IType alienType= iter.next();
 				IMethod alienMethod= fTypeToMethod.get(alienType);
 				ITypeHierarchy hierarchy= getCachedHierarchy(alienType, owner, new SubProgressMonitor(pm, 1));
 				if (hierarchy == null)
 					hierarchy= alienType.newTypeHierarchy(owner, new SubProgressMonitor(pm, 1));
 				IType[] allSubtypes= hierarchy.getAllSubtypes(alienType);
 				for (int i= 0; i < allSubtypes.length; i++) {
 					IType subtype= allSubtypes[i];
 					if (relatedSubTypes.contains(subtype)) {
 						if (JavaModelUtil.isVisibleInHierarchy(alienMethod, subtype.getPackageFragment())) {
 							marriedAlienTypeReps.add(fUnionFind.find(alienType));
 						} else {
 							// not overridden
 						}
 					}
 				}
 			}

 			if (marriedAlienTypeReps.size() == 0)
 				return relatedMethods.toArray(new IMethod[relatedMethods.size()]);

 			for (Iterator<IType> iter= marriedAlienTypeReps.iterator(); iter.hasNext();) {
 				IType marriedAlienTypeRep= iter.next();
 				List<IType> marriedAlienTypes= partitioning.get(marriedAlienTypeRep);
 				for (Iterator<IType> iterator= marriedAlienTypes.iterator(); iterator.hasNext();) {
 					IType marriedAlienInterfaceType= iterator.next();
 					relatedMethods.add(fTypeToMethod.get(marriedAlienInterfaceType));
 				}
 				alienTypes.removeAll(marriedAlienTypes); //not alien any more
 				relatedTypesToProcess.addAll(marriedAlienTypes); //process freshly married types again
 			}
 		}

 		fRootReps= null;
 		fRootHierarchies= null;
 		fTypeToMethod= null;
 		fUnionFind= null;

 		return relatedMethods.toArray(new IMethod[relatedMethods.size()]);
 	}

 	private ITypeHierarchy getCachedHierarchy(IType type, WorkingCopyOwner owner, IProgressMonitor monitor) throws JavaModelException {
 		IType rep= fUnionFind.find(type);
 		if (rep != null) {
 			Collection<IType> collection= fRootReps.get(rep);
 			for (Iterator<IType> iter= collection.iterator(); iter.hasNext();) {
 				IType root= iter.next();
 				ITypeHierarchy hierarchy= fRootHierarchies.get(root);
 				if (hierarchy == null) {
 					hierarchy= root.newTypeHierarchy(owner, new SubProgressMonitor(monitor, 1));
 					fRootHierarchies.put(root, hierarchy);
 				}
 				if (hierarchy.contains(type))
 					return hierarchy;
 			}
 		}
 		return null;
 	}

 	private void findAllDeclarations(IProgressMonitor monitor, WorkingCopyOwner owner) throws CoreException {
 		fDeclarations= new ArrayList<IMethod>();

 		class MethodRequestor extends SearchRequestor {
 			@Override
 			public void acceptSearchMatch(SearchMatch match) throws CoreException {
 				IMethod method= (IMethod) match.getElement();
 				boolean isBinary= method.isBinary();
 				if (fBinaryRefs != null || ! (fExcludeBinaries && isBinary)) {
 					fDeclarations.add(method);
 				}
 				if (isBinary && fBinaryRefs != null) {
 					fDeclarationToMatch.put(method, match);
 				}
 			}
 		}

 		int limitTo = IJavaSearchConstants.DECLARATIONS | IJavaSearchConstants.IGNORE_DECLARING_TYPE | IJavaSearchConstants.IGNORE_RETURN_TYPE;
 		int matchRule= SearchPattern.R_ERASURE_MATCH | SearchPattern.R_CASE_SENSITIVE;
 		SearchPattern pattern= SearchPattern.createPattern(fMethod, limitTo, matchRule);
 		SearchParticipant[] participants= SearchUtils.getDefaultSearchParticipants();
 		IJavaSearchScope scope= RefactoringScopeFactory.createRelatedProjectsScope(fMethod.getJavaProject(), IJavaSearchScope.SOURCES | IJavaSearchScope.APPLICATION_LIBRARIES | IJavaSearchScope.SYSTEM_LIBRARIES);
 		MethodRequestor requestor= new MethodRequestor();
 		SearchEngine searchEngine= owner != null ? new SearchEngine(owner) : new SearchEngine();

 		searchEngine.search(pattern, participants, scope, requestor, monitor);
 	}

 	private void createHierarchyOfDeclarations(IProgressMonitor pm, WorkingCopyOwner owner) throws JavaModelException {
 		IRegion region= JavaCore.newRegion();
 		for (Iterator<IMethod> iter= fDeclarations.iterator(); iter.hasNext();) {
 			IType declaringType= iter.next().getDeclaringType();
 			region.add(declaringType);
 		}
 		fHierarchy= JavaCore.newTypeHierarchy(region, owner, pm);
 	}

 	private void createTypeToMethod() {
 		fTypeToMethod= new HashMap<IType, IMethod>();
 		for (Iterator<IMethod> iter= fDeclarations.iterator(); iter.hasNext();) {
 			IMethod declaration= iter.next();
 			fTypeToMethod.put(declaration.getDeclaringType(), declaration);
 		}
 	}

 	private void createUnionFind() throws JavaModelException {
 		fRootTypes= new HashSet<IType>(fTypeToMethod.keySet());
 		fUnionFind= new UnionFind();
 		for (Iterator<IType> iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
 			IType type= iter.next();
 			fUnionFind.init(type);
 		}
 		for (Iterator<IType> iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
 			IType type= iter.next();
 			uniteWithSupertypes(type, type);
 		}
 		fRootReps= new MultiMap<IType, IType>();
 		for (Iterator<IType> iter= fRootTypes.iterator(); iter.hasNext();) {
 			IType type= iter.next();
 			IType rep= fUnionFind.find(type);
 			if (rep != null)
 				fRootReps.put(rep, type);
 		}
 		fRootHierarchies= new HashMap<IType, ITypeHierarchy>();
 	}

 	private void uniteWithSupertypes(IType anchor, IType type) throws JavaModelException {
 		IType[] supertypes= fHierarchy.getSupertypes(type);
 		for (int i= 0; i < supertypes.length; i++) {
 			IType supertype= supertypes[i];
 			IType superRep= fUnionFind.find(supertype);
 			if (superRep == null) {
 				//Type doesn't declare method, but maybe supertypes?
 				uniteWithSupertypes(anchor, supertype);
 			} else {
 				//check whether method in supertype is really overridden:
 				IMember superMethod= fTypeToMethod.get(supertype);
 				if (JavaModelUtil.isVisibleInHierarchy(superMethod, anchor.getPackageFragment())) {
 					IType rep= fUnionFind.find(anchor);
 					fUnionFind.union(rep, superRep);
 					// current type is no root anymore
 					fRootTypes.remove(anchor);
 					uniteWithSupertypes(supertype, supertype);
 				} else {
 					//Not overridden -> overriding chain ends here.
 				}
 			}
 		}
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2000, 2011 IBM Corporation and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Contributors:
	* IBM Corporation - initial API and implementation
	*******************************************************************************/
	package org.eclipse.jdt.internal.corext.refactoring.rename;

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;

	import org.eclipse.core.runtime.Assert;
	import org.eclipse.core.runtime.CoreException;
	import org.eclipse.core.runtime.IProgressMonitor;
	import org.eclipse.core.runtime.OperationCanceledException;
	import org.eclipse.core.runtime.SubProgressMonitor;

	import org.eclipse.jdt.core.IMember;
	import org.eclipse.jdt.core.IMethod;
	import org.eclipse.jdt.core.IRegion;
	import org.eclipse.jdt.core.IType;
	import org.eclipse.jdt.core.ITypeHierarchy;
	import org.eclipse.jdt.core.JavaCore;
	import org.eclipse.jdt.core.JavaModelException;
	import org.eclipse.jdt.core.WorkingCopyOwner;
	import org.eclipse.jdt.core.search.IJavaSearchConstants;
	import org.eclipse.jdt.core.search.IJavaSearchScope;
	import org.eclipse.jdt.core.search.SearchEngine;
	import org.eclipse.jdt.core.search.SearchMatch;
	import org.eclipse.jdt.core.search.SearchParticipant;
	import org.eclipse.jdt.core.search.SearchPattern;
	import org.eclipse.jdt.core.search.SearchRequestor;

	import org.eclipse.jdt.internal.corext.refactoring.RefactoringScopeFactory;
	import org.eclipse.jdt.internal.corext.refactoring.base.ReferencesInBinaryContext;
	import org.eclipse.jdt.internal.corext.util.JavaModelUtil;
	import org.eclipse.jdt.internal.corext.util.SearchUtils;

	public class RippleMethodFinder2 {

	private final IMethod fMethod;
	private List<IMethod> fDeclarations;
	private ITypeHierarchy fHierarchy;
	private Map<IType, IMethod> fTypeToMethod;
	private Set<IType> fRootTypes;
	private MultiMap<IType, IType> fRootReps;
	private Map<IType, ITypeHierarchy> fRootHierarchies;
	private UnionFind fUnionFind;

	private final boolean fExcludeBinaries;
	private final ReferencesInBinaryContext fBinaryRefs;
	private Map<IMethod, SearchMatch> fDeclarationToMatch;

	private static class MultiMap<K, V> {
	HashMap<K, Collection<V>> fImplementation= new HashMap<K, Collection<V>>();

	public void put(K key, V value) {
	Collection<V> collection= fImplementation.get(key);
	if (collection == null) {
	collection= new HashSet<V>();
	fImplementation.put(key, collection);
	}
	collection.add(value);
	}

	public Collection<V> get(K key) {
	return fImplementation.get(key);
	}
	}
	private static class UnionFind {
	HashMap<IType, IType> fElementToRepresentative= new HashMap<IType, IType>();

	public void init(IType type) {
	fElementToRepresentative.put(type, type);
	}

	//path compression:
	public IType find(IType element) {
	IType root= element;
	IType rep= fElementToRepresentative.get(root);
	while (rep != null && ! rep.equals(root)) {
	root= rep;
	rep= fElementToRepresentative.get(root);
	}
	if (rep == null)
	return null;

	rep= fElementToRepresentative.get(element);
	while (! rep.equals(root)) {
	IType temp= element;
	element= rep;
	fElementToRepresentative.put(temp, root);
	rep= fElementToRepresentative.get(element);
	}
	return root;
	}

	// //straightforward:
	// public IType find(IType element) {
	// IType current= element;
	// IType rep= (IType) fElementToRepresentative.get(current);
	// while (rep != null && ! rep.equals(current)) {
	// current= rep;
	// rep= (IType) fElementToRepresentative.get(current);
	// }
	// if (rep == null)
	// return null;
	// else
	// return current;
	// }

	public void union(IType rep1, IType rep2) {
	fElementToRepresentative.put(rep1, rep2);
	}
	}


	private RippleMethodFinder2(IMethod method, boolean excludeBinaries){
	fMethod= method;
	fExcludeBinaries= excludeBinaries;
	fBinaryRefs= null;
	}

	private RippleMethodFinder2(IMethod method, ReferencesInBinaryContext binaryRefs) {
	fMethod= method;
	fExcludeBinaries= true;
	fDeclarationToMatch= new HashMap<IMethod, SearchMatch>();
	fBinaryRefs= binaryRefs;
	}

	public static IMethod[] getRelatedMethods(IMethod method, boolean excludeBinaries, IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
	try{
	if (! MethodChecks.isVirtual(method))
	return new IMethod[]{ method };

	return new RippleMethodFinder2(method, excludeBinaries).getAllRippleMethods(pm, owner);
	} finally{
	pm.done();
	}
	}
	public static IMethod[] getRelatedMethods(IMethod method, IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
	return getRelatedMethods(method, true, pm, owner);
	}

	public static IMethod[] getRelatedMethods(IMethod method, ReferencesInBinaryContext binaryRefs, IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
	try {
	if (! MethodChecks.isVirtual(method))
	return new IMethod[]{ method };

	return new RippleMethodFinder2(method, binaryRefs).getAllRippleMethods(pm, owner);
	} finally{
	pm.done();
	}
	}

	private IMethod[] getAllRippleMethods(IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
	IMethod[] rippleMethods= findAllRippleMethods(pm, owner);
	if (fDeclarationToMatch == null)
	return rippleMethods;

	List<IMethod> rippleMethodsList= new ArrayList<IMethod>(Arrays.asList(rippleMethods));
	for (Iterator<IMethod> iter= rippleMethodsList.iterator(); iter.hasNext(); ) {
	Object match= fDeclarationToMatch.get(iter.next());
	if (match != null) {
	iter.remove();
	fBinaryRefs.add((SearchMatch) match);
	}
	}
	fDeclarationToMatch= null;
	return rippleMethodsList.toArray(new IMethod[rippleMethodsList.size()]);
	}

	private IMethod[] findAllRippleMethods(IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
	pm.beginTask("", 4); //$NON-NLS-1$

	findAllDeclarations(new SubProgressMonitor(pm, 1), owner);

	//TODO: report assertion as error status and fall back to only return fMethod
	//check for bug 81058:
	if (! fDeclarations.contains(fMethod))
	Assert.isTrue(false, "Search for method declaration did not find original element: " + fMethod.toString()); //$NON-NLS-1$

	createHierarchyOfDeclarations(new SubProgressMonitor(pm, 1), owner);
	createTypeToMethod();
	createUnionFind();
	if (pm.isCanceled())
	throw new OperationCanceledException();

	fHierarchy= null;
	fRootTypes= null;

	Map<IType, List<IType>> partitioning= new HashMap<IType, List<IType>>();
	for (Iterator<IType> iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
	IType type= iter.next();
	IType rep= fUnionFind.find(type);
	List<IType> types= partitioning.get(rep);
	if (types == null)
	types= new ArrayList<IType>();
	types.add(type);
	partitioning.put(rep, types);
	}
	Assert.isTrue(partitioning.size() > 0);
	if (partitioning.size() == 1)
	return fDeclarations.toArray(new IMethod[fDeclarations.size()]);

	//Multiple partitions; must look out for nasty marriage cases
	//(types inheriting method from two ancestors, but without redeclaring it).
	IType methodTypeRep= fUnionFind.find(fMethod.getDeclaringType());
	List<IType> relatedTypes= partitioning.get(methodTypeRep);
	boolean hasRelatedInterfaces= false;
	List<IMethod> relatedMethods= new ArrayList<IMethod>();
	for (Iterator<IType> iter= relatedTypes.iterator(); iter.hasNext();) {
	IType relatedType= iter.next();
	relatedMethods.add(fTypeToMethod.get(relatedType));
	if (relatedType.isInterface())
	hasRelatedInterfaces= true;
	}

	//Definition: An alien type is a type that is not a related type. The set of
	// alien types diminishes as new types become related (a.k.a marry a relatedType).

	List<IMethod> alienDeclarations= new ArrayList<IMethod>(fDeclarations);
	fDeclarations= null;
	alienDeclarations.removeAll(relatedMethods);
	List<IType> alienTypes= new ArrayList<IType>();
	boolean hasAlienInterfaces= false;
	for (Iterator<IMethod> iter= alienDeclarations.iterator(); iter.hasNext();) {
	IMethod alienDeclaration= iter.next();
	IType alienType= alienDeclaration.getDeclaringType();
	alienTypes.add(alienType);
	if (alienType.isInterface())
	hasAlienInterfaces= true;
	}
	if (alienTypes.size() == 0) //no nasty marriage scenarios without types to marry with...
	return relatedMethods.toArray(new IMethod[relatedMethods.size()]);
	if (! hasRelatedInterfaces && ! hasAlienInterfaces) //no nasty marriage scenarios without interfaces...
	return relatedMethods.toArray(new IMethod[relatedMethods.size()]);

	//find all subtypes of related types:
	HashSet<IType> relatedSubTypes= new HashSet<IType>();
	List<IType> relatedTypesToProcess= new ArrayList<IType>(relatedTypes);
	while (relatedTypesToProcess.size() > 0) {
	//TODO: would only need subtype hierarchies of all top-of-ripple relatedTypesToProcess
	for (Iterator<IType> iter= relatedTypesToProcess.iterator(); iter.hasNext();) {
	if (pm.isCanceled())
	throw new OperationCanceledException();
	IType relatedType= iter.next();
	ITypeHierarchy hierarchy= getCachedHierarchy(relatedType, owner, new SubProgressMonitor(pm, 1));
	if (hierarchy == null)
	hierarchy= relatedType.newTypeHierarchy(owner, new SubProgressMonitor(pm, 1));
	IType[] allSubTypes= hierarchy.getAllSubtypes(relatedType);
	for (int i= 0; i < allSubTypes.length; i++)
	relatedSubTypes.add(allSubTypes[i]);
	}
	relatedTypesToProcess.clear(); //processed; make sure loop terminates

	HashSet<IType> marriedAlienTypeReps= new HashSet<IType>();
	for (Iterator<IType> iter= alienTypes.iterator(); iter.hasNext();) {
	if (pm.isCanceled())
	throw new OperationCanceledException();
	IType alienType= iter.next();
	IMethod alienMethod= fTypeToMethod.get(alienType);
	ITypeHierarchy hierarchy= getCachedHierarchy(alienType, owner, new SubProgressMonitor(pm, 1));
	if (hierarchy == null)
	hierarchy= alienType.newTypeHierarchy(owner, new SubProgressMonitor(pm, 1));
	IType[] allSubtypes= hierarchy.getAllSubtypes(alienType);
	for (int i= 0; i < allSubtypes.length; i++) {
	IType subtype= allSubtypes[i];
	if (relatedSubTypes.contains(subtype)) {
	if (JavaModelUtil.isVisibleInHierarchy(alienMethod, subtype.getPackageFragment())) {
	marriedAlienTypeReps.add(fUnionFind.find(alienType));
	} else {
	// not overridden
	}
	}
	}
	}

	if (marriedAlienTypeReps.size() == 0)
	return relatedMethods.toArray(new IMethod[relatedMethods.size()]);

	for (Iterator<IType> iter= marriedAlienTypeReps.iterator(); iter.hasNext();) {
	IType marriedAlienTypeRep= iter.next();
	List<IType> marriedAlienTypes= partitioning.get(marriedAlienTypeRep);
	for (Iterator<IType> iterator= marriedAlienTypes.iterator(); iterator.hasNext();) {
	IType marriedAlienInterfaceType= iterator.next();
	relatedMethods.add(fTypeToMethod.get(marriedAlienInterfaceType));
	}
	alienTypes.removeAll(marriedAlienTypes); //not alien any more
	relatedTypesToProcess.addAll(marriedAlienTypes); //process freshly married types again
	}
	}

	fRootReps= null;
	fRootHierarchies= null;
	fTypeToMethod= null;
	fUnionFind= null;

	return relatedMethods.toArray(new IMethod[relatedMethods.size()]);
	}

	private ITypeHierarchy getCachedHierarchy(IType type, WorkingCopyOwner owner, IProgressMonitor monitor) throws JavaModelException {
	IType rep= fUnionFind.find(type);
	if (rep != null) {
	Collection<IType> collection= fRootReps.get(rep);
	for (Iterator<IType> iter= collection.iterator(); iter.hasNext();) {
	IType root= iter.next();
	ITypeHierarchy hierarchy= fRootHierarchies.get(root);
	if (hierarchy == null) {
	hierarchy= root.newTypeHierarchy(owner, new SubProgressMonitor(monitor, 1));
	fRootHierarchies.put(root, hierarchy);
	}
	if (hierarchy.contains(type))
	return hierarchy;
	}
	}
	return null;
	}

	private void findAllDeclarations(IProgressMonitor monitor, WorkingCopyOwner owner) throws CoreException {
	fDeclarations= new ArrayList<IMethod>();

	class MethodRequestor extends SearchRequestor {
	@Override
	public void acceptSearchMatch(SearchMatch match) throws CoreException {
	IMethod method= (IMethod) match.getElement();
	boolean isBinary= method.isBinary();
	if (fBinaryRefs != null \|\| ! (fExcludeBinaries && isBinary)) {
	fDeclarations.add(method);
	}
	if (isBinary && fBinaryRefs != null) {
	fDeclarationToMatch.put(method, match);
	}
	}
	}

	int limitTo = IJavaSearchConstants.DECLARATIONS \| IJavaSearchConstants.IGNORE_DECLARING_TYPE \| IJavaSearchConstants.IGNORE_RETURN_TYPE;
	int matchRule= SearchPattern.R_ERASURE_MATCH \| SearchPattern.R_CASE_SENSITIVE;
	SearchPattern pattern= SearchPattern.createPattern(fMethod, limitTo, matchRule);
	SearchParticipant[] participants= SearchUtils.getDefaultSearchParticipants();
	IJavaSearchScope scope= RefactoringScopeFactory.createRelatedProjectsScope(fMethod.getJavaProject(), IJavaSearchScope.SOURCES \| IJavaSearchScope.APPLICATION_LIBRARIES \| IJavaSearchScope.SYSTEM_LIBRARIES);
	MethodRequestor requestor= new MethodRequestor();
	SearchEngine searchEngine= owner != null ? new SearchEngine(owner) : new SearchEngine();

	searchEngine.search(pattern, participants, scope, requestor, monitor);
	}

	private void createHierarchyOfDeclarations(IProgressMonitor pm, WorkingCopyOwner owner) throws JavaModelException {
	IRegion region= JavaCore.newRegion();
	for (Iterator<IMethod> iter= fDeclarations.iterator(); iter.hasNext();) {
	IType declaringType= iter.next().getDeclaringType();
	region.add(declaringType);
	}
	fHierarchy= JavaCore.newTypeHierarchy(region, owner, pm);
	}

	private void createTypeToMethod() {
	fTypeToMethod= new HashMap<IType, IMethod>();
	for (Iterator<IMethod> iter= fDeclarations.iterator(); iter.hasNext();) {
	IMethod declaration= iter.next();
	fTypeToMethod.put(declaration.getDeclaringType(), declaration);
	}
	}

	private void createUnionFind() throws JavaModelException {
	fRootTypes= new HashSet<IType>(fTypeToMethod.keySet());
	fUnionFind= new UnionFind();
	for (Iterator<IType> iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
	IType type= iter.next();
	fUnionFind.init(type);
	}
	for (Iterator<IType> iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
	IType type= iter.next();
	uniteWithSupertypes(type, type);
	}
	fRootReps= new MultiMap<IType, IType>();
	for (Iterator<IType> iter= fRootTypes.iterator(); iter.hasNext();) {
	IType type= iter.next();
	IType rep= fUnionFind.find(type);
	if (rep != null)
	fRootReps.put(rep, type);
	}
	fRootHierarchies= new HashMap<IType, ITypeHierarchy>();
	}

	private void uniteWithSupertypes(IType anchor, IType type) throws JavaModelException {
	IType[] supertypes= fHierarchy.getSupertypes(type);
	for (int i= 0; i < supertypes.length; i++) {
	IType supertype= supertypes[i];
	IType superRep= fUnionFind.find(supertype);
	if (superRep == null) {
	//Type doesn't declare method, but maybe supertypes?
	uniteWithSupertypes(anchor, supertype);
	} else {
	//check whether method in supertype is really overridden:
	IMember superMethod= fTypeToMethod.get(supertype);
	if (JavaModelUtil.isVisibleInHierarchy(superMethod, anchor.getPackageFragment())) {
	IType rep= fUnionFind.find(anchor);
	fUnionFind.union(rep, superRep);
	// current type is no root anymore
	fRootTypes.remove(anchor);
	uniteWithSupertypes(supertype, supertype);
	} else {
	//Not overridden -> overriding chain ends here.
	}
	}
	}
	}
	}