001: /*******************************************************************************
002: * Copyright (c) 2000, 2006 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.jdt.internal.corext.refactoring.rename;
011:
012: import java.util.ArrayList;
013: import java.util.Collection;
014: import java.util.HashMap;
015: import java.util.HashSet;
016: import java.util.Iterator;
017: import java.util.List;
018: import java.util.Map;
019: import java.util.Set;
020:
021: import org.eclipse.core.runtime.Assert;
022: import org.eclipse.core.runtime.CoreException;
023: import org.eclipse.core.runtime.IProgressMonitor;
024: import org.eclipse.core.runtime.OperationCanceledException;
025: import org.eclipse.core.runtime.SubProgressMonitor;
026:
027: import org.eclipse.jdt.core.IMember;
028: import org.eclipse.jdt.core.IMethod;
029: import org.eclipse.jdt.core.IRegion;
030: import org.eclipse.jdt.core.IType;
031: import org.eclipse.jdt.core.ITypeHierarchy;
032: import org.eclipse.jdt.core.JavaCore;
033: import org.eclipse.jdt.core.JavaModelException;
034: import org.eclipse.jdt.core.WorkingCopyOwner;
035: import org.eclipse.jdt.core.search.IJavaSearchConstants;
036: import org.eclipse.jdt.core.search.IJavaSearchScope;
037: import org.eclipse.jdt.core.search.SearchMatch;
038: import org.eclipse.jdt.core.search.SearchPattern;
039:
040: import org.eclipse.jdt.internal.corext.refactoring.RefactoringScopeFactory;
041: import org.eclipse.jdt.internal.corext.refactoring.RefactoringSearchEngine2;
042: import org.eclipse.jdt.internal.corext.util.JavaModelUtil;
043:
044: public class RippleMethodFinder2 {
045:
046: private final IMethod fMethod;
047: private List/*<IMethod>*/fDeclarations;
048: private ITypeHierarchy fHierarchy;
049: private Map/*IType, IMethod*/fTypeToMethod;
050: private Set/*IType*/fRootTypes;
051: private MultiMap/*IType, IType*/fRootReps;
052: private Map/*IType, ITypeHierarchy*/fRootHierarchies;
053: private UnionFind fUnionFind;
054: private boolean fExcludeBinaries;
055:
056: private static class MultiMap {
057: HashMap/*<IType, Collection>*/fImplementation = new HashMap();
058:
059: public void put(IType key, IType value) {
060: Collection collection = (Collection) fImplementation
061: .get(key);
062: if (collection == null) {
063: collection = new HashSet();
064: fImplementation.put(key, collection);
065: }
066: collection.add(value);
067: }
068:
069: public Collection get(IType key) {
070: return (Collection) fImplementation.get(key);
071: }
072: }
073:
074: private static class UnionFind {
075: HashMap/*<IType, IType>*/fElementToRepresentative = new HashMap();
076:
077: public void init(IType type) {
078: fElementToRepresentative.put(type, type);
079: }
080:
081: //path compression:
082: public IType find(IType element) {
083: IType root = element;
084: IType rep = (IType) fElementToRepresentative.get(root);
085: while (rep != null && !rep.equals(root)) {
086: root = rep;
087: rep = (IType) fElementToRepresentative.get(root);
088: }
089: if (rep == null)
090: return null;
091:
092: rep = (IType) fElementToRepresentative.get(element);
093: while (!rep.equals(root)) {
094: IType temp = element;
095: element = rep;
096: fElementToRepresentative.put(temp, root);
097: rep = (IType) fElementToRepresentative.get(element);
098: }
099: return root;
100: }
101:
102: // //straightforward:
103: // public IType find(IType element) {
104: // IType current= element;
105: // IType rep= (IType) fElementToRepresentative.get(current);
106: // while (rep != null && ! rep.equals(current)) {
107: // current= rep;
108: // rep= (IType) fElementToRepresentative.get(current);
109: // }
110: // if (rep == null)
111: // return null;
112: // else
113: // return current;
114: // }
115:
116: public void union(IType rep1, IType rep2) {
117: fElementToRepresentative.put(rep1, rep2);
118: }
119: }
120:
121: private RippleMethodFinder2(IMethod method, boolean excludeBinaries) {
122: fMethod = method;
123: fExcludeBinaries = excludeBinaries;
124: }
125:
126: public static IMethod[] getRelatedMethods(IMethod method,
127: boolean excludeBinaries, IProgressMonitor pm,
128: WorkingCopyOwner owner) throws CoreException {
129: try {
130: if (!MethodChecks.isVirtual(method))
131: return new IMethod[] { method };
132:
133: return new RippleMethodFinder2(method, excludeBinaries)
134: .getAllRippleMethods(pm, owner);
135: } finally {
136: pm.done();
137: }
138: }
139:
140: public static IMethod[] getRelatedMethods(IMethod method,
141: IProgressMonitor pm, WorkingCopyOwner owner)
142: throws CoreException {
143: return getRelatedMethods(method, true, pm, owner);
144: }
145:
146: private IMethod[] getAllRippleMethods(IProgressMonitor pm,
147: WorkingCopyOwner owner) throws CoreException {
148: pm.beginTask("", 4); //$NON-NLS-1$
149:
150: findAllDeclarations(new SubProgressMonitor(pm, 1), owner);
151: //TODO: report binary methods to an error status
152: //TODO: report assertion as error status and fall back to only return fMethod
153: //check for bug 81058:
154: Assert
155: .isTrue(fDeclarations.contains(fMethod),
156: "Search for method declaration did not find original element"); //$NON-NLS-1$
157:
158: createHierarchyOfDeclarations(new SubProgressMonitor(pm, 1),
159: owner);
160: createTypeToMethod();
161: createUnionFind();
162: if (pm.isCanceled())
163: throw new OperationCanceledException();
164:
165: fHierarchy = null;
166: fRootTypes = null;
167:
168: Map/*IType, List<IType>*/partitioning = new HashMap();
169: for (Iterator iter = fTypeToMethod.keySet().iterator(); iter
170: .hasNext();) {
171: IType type = (IType) iter.next();
172: IType rep = fUnionFind.find(type);
173: List/*<IType>*/types = (List) partitioning.get(rep);
174: if (types == null)
175: types = new ArrayList();
176: types.add(type);
177: partitioning.put(rep, types);
178: }
179: Assert.isTrue(partitioning.size() > 0);
180: if (partitioning.size() == 1)
181: return (IMethod[]) fDeclarations
182: .toArray(new IMethod[fDeclarations.size()]);
183:
184: //Multiple partitions; must look out for nasty marriage cases
185: //(types inheriting method from two ancestors, but without redeclaring it).
186: IType methodTypeRep = fUnionFind.find(fMethod
187: .getDeclaringType());
188: List/*<IType>*/relatedTypes = (List) partitioning
189: .get(methodTypeRep);
190: boolean hasRelatedInterfaces = false;
191: List/*<IMethod>*/relatedMethods = new ArrayList();
192: for (Iterator iter = relatedTypes.iterator(); iter.hasNext();) {
193: IType relatedType = (IType) iter.next();
194: relatedMethods.add(fTypeToMethod.get(relatedType));
195: if (relatedType.isInterface())
196: hasRelatedInterfaces = true;
197: }
198:
199: //Definition: An alien type is a type that is not a related type. The set of
200: // alien types diminishes as new types become related (a.k.a marry a relatedType).
201:
202: List/*<IMethod>*/alienDeclarations = new ArrayList(
203: fDeclarations);
204: fDeclarations = null;
205: alienDeclarations.removeAll(relatedMethods);
206: List/*<IType>*/alienTypes = new ArrayList();
207: boolean hasAlienInterfaces = false;
208: for (Iterator iter = alienDeclarations.iterator(); iter
209: .hasNext();) {
210: IMethod alienDeclaration = (IMethod) iter.next();
211: IType alienType = alienDeclaration.getDeclaringType();
212: alienTypes.add(alienType);
213: if (alienType.isInterface())
214: hasAlienInterfaces = true;
215: }
216: if (alienTypes.size() == 0) //no nasty marriage scenarios without types to marry with...
217: return (IMethod[]) relatedMethods
218: .toArray(new IMethod[relatedMethods.size()]);
219: if (!hasRelatedInterfaces && !hasAlienInterfaces) //no nasty marriage scenarios without interfaces...
220: return (IMethod[]) relatedMethods
221: .toArray(new IMethod[relatedMethods.size()]);
222:
223: //find all subtypes of related types:
224: HashSet/*<IType>*/relatedSubTypes = new HashSet();
225: List/*<IType>*/relatedTypesToProcess = new ArrayList(
226: relatedTypes);
227: while (relatedTypesToProcess.size() > 0) {
228: //TODO: would only need subtype hierarchies of all top-of-ripple relatedTypesToProcess
229: for (Iterator iter = relatedTypesToProcess.iterator(); iter
230: .hasNext();) {
231: if (pm.isCanceled())
232: throw new OperationCanceledException();
233: IType relatedType = (IType) iter.next();
234: ITypeHierarchy hierarchy = getCachedHierarchy(
235: relatedType, owner, new SubProgressMonitor(pm,
236: 1));
237: if (hierarchy == null)
238: hierarchy = relatedType.newTypeHierarchy(owner,
239: new SubProgressMonitor(pm, 1));
240: IType[] allSubTypes = hierarchy
241: .getAllSubtypes(relatedType);
242: for (int i = 0; i < allSubTypes.length; i++)
243: relatedSubTypes.add(allSubTypes[i]);
244: }
245: relatedTypesToProcess.clear(); //processed; make sure loop terminates
246:
247: HashSet/*<IType>*/marriedAlienTypeReps = new HashSet();
248: for (Iterator iter = alienTypes.iterator(); iter.hasNext();) {
249: if (pm.isCanceled())
250: throw new OperationCanceledException();
251: IType alienType = (IType) iter.next();
252: IMethod alienMethod = (IMethod) fTypeToMethod
253: .get(alienType);
254: ITypeHierarchy hierarchy = getCachedHierarchy(
255: alienType, owner, new SubProgressMonitor(pm, 1));
256: if (hierarchy == null)
257: hierarchy = alienType.newTypeHierarchy(owner,
258: new SubProgressMonitor(pm, 1));
259: IType[] allSubtypes = hierarchy
260: .getAllSubtypes(alienType);
261: for (int i = 0; i < allSubtypes.length; i++) {
262: IType subtype = allSubtypes[i];
263: if (relatedSubTypes.contains(subtype)) {
264: if (JavaModelUtil.isVisibleInHierarchy(
265: alienMethod, subtype
266: .getPackageFragment())) {
267: marriedAlienTypeReps.add(fUnionFind
268: .find(alienType));
269: } else {
270: // not overridden
271: }
272: }
273: }
274: }
275:
276: if (marriedAlienTypeReps.size() == 0)
277: return (IMethod[]) relatedMethods
278: .toArray(new IMethod[relatedMethods.size()]);
279:
280: for (Iterator iter = marriedAlienTypeReps.iterator(); iter
281: .hasNext();) {
282: IType marriedAlienTypeRep = (IType) iter.next();
283: List/*<IType>*/marriedAlienTypes = (List) partitioning
284: .get(marriedAlienTypeRep);
285: for (Iterator iterator = marriedAlienTypes.iterator(); iterator
286: .hasNext();) {
287: IType marriedAlienInterfaceType = (IType) iterator
288: .next();
289: relatedMethods.add(fTypeToMethod
290: .get(marriedAlienInterfaceType));
291: }
292: alienTypes.removeAll(marriedAlienTypes); //not alien any more
293: relatedTypesToProcess.addAll(marriedAlienTypes); //process freshly married types again
294: }
295: }
296:
297: fRootReps = null;
298: fRootHierarchies = null;
299: fTypeToMethod = null;
300: fUnionFind = null;
301:
302: return (IMethod[]) relatedMethods
303: .toArray(new IMethod[relatedMethods.size()]);
304: }
305:
306: private ITypeHierarchy getCachedHierarchy(IType type,
307: WorkingCopyOwner owner, IProgressMonitor monitor)
308: throws JavaModelException {
309: IType rep = fUnionFind.find(type);
310: if (rep != null) {
311: Collection collection = fRootReps.get(rep);
312: for (Iterator iter = collection.iterator(); iter.hasNext();) {
313: IType root = (IType) iter.next();
314: ITypeHierarchy hierarchy = (ITypeHierarchy) fRootHierarchies
315: .get(root);
316: if (hierarchy == null) {
317: hierarchy = root.newTypeHierarchy(owner,
318: new SubProgressMonitor(monitor, 1));
319: fRootHierarchies.put(root, hierarchy);
320: }
321: if (hierarchy.contains(type))
322: return hierarchy;
323: }
324: }
325: return null;
326: }
327:
328: private void findAllDeclarations(IProgressMonitor monitor,
329: WorkingCopyOwner owner) throws CoreException {
330: fDeclarations = new ArrayList();
331: final RefactoringSearchEngine2 engine = new RefactoringSearchEngine2(
332: SearchPattern
333: .createPattern(
334: fMethod,
335: IJavaSearchConstants.DECLARATIONS
336: | IJavaSearchConstants.IGNORE_DECLARING_TYPE
337: | IJavaSearchConstants.IGNORE_RETURN_TYPE,
338: SearchPattern.R_ERASURE_MATCH
339: | SearchPattern.R_CASE_SENSITIVE));
340: if (owner != null)
341: engine.setOwner(owner);
342: engine
343: .setScope(RefactoringScopeFactory
344: .createRelatedProjectsScope(
345: fMethod.getJavaProject(),
346: IJavaSearchScope.SOURCES
347: | IJavaSearchScope.APPLICATION_LIBRARIES
348: | IJavaSearchScope.SYSTEM_LIBRARIES));
349: engine.setFiltering(false, fExcludeBinaries);
350: engine.setGrouping(false);
351: engine.searchPattern(new SubProgressMonitor(monitor, 1));
352: final SearchMatch[] matches = (SearchMatch[]) engine
353: .getResults();
354: IMethod method = null;
355: for (int index = 0; index < matches.length; index++) {
356: method = (IMethod) matches[index].getElement();
357: if (method != null)
358: fDeclarations.add(method);
359: }
360: }
361:
362: private void createHierarchyOfDeclarations(IProgressMonitor pm,
363: WorkingCopyOwner owner) throws JavaModelException {
364: IRegion region = JavaCore.newRegion();
365: for (Iterator iter = fDeclarations.iterator(); iter.hasNext();) {
366: IType declaringType = ((IMethod) iter.next())
367: .getDeclaringType();
368: region.add(declaringType);
369: }
370: fHierarchy = JavaCore.newTypeHierarchy(region, owner, pm);
371: }
372:
373: private void createTypeToMethod() {
374: fTypeToMethod = new HashMap();
375: for (Iterator iter = fDeclarations.iterator(); iter.hasNext();) {
376: IMethod declaration = (IMethod) iter.next();
377: fTypeToMethod.put(declaration.getDeclaringType(),
378: declaration);
379: }
380: }
381:
382: private void createUnionFind() throws JavaModelException {
383: fRootTypes = new HashSet(fTypeToMethod.keySet());
384: fUnionFind = new UnionFind();
385: for (Iterator iter = fTypeToMethod.keySet().iterator(); iter
386: .hasNext();) {
387: IType type = (IType) iter.next();
388: fUnionFind.init(type);
389: }
390: for (Iterator iter = fTypeToMethod.keySet().iterator(); iter
391: .hasNext();) {
392: IType type = (IType) iter.next();
393: uniteWithSupertypes(type, type);
394: }
395: fRootReps = new MultiMap();
396: for (Iterator iter = fRootTypes.iterator(); iter.hasNext();) {
397: IType type = (IType) iter.next();
398: IType rep = fUnionFind.find(type);
399: if (rep != null)
400: fRootReps.put(rep, type);
401: }
402: fRootHierarchies = new HashMap();
403: }
404:
405: private void uniteWithSupertypes(IType anchor, IType type)
406: throws JavaModelException {
407: IType[] super types = fHierarchy.getSupertypes(type);
408: for (int i = 0; i < super types.length; i++) {
409: IType super type = super types[i];
410: IType super Rep = fUnionFind.find(super type);
411: if (super Rep == null) {
412: //Type doesn't declare method, but maybe supertypes?
413: uniteWithSupertypes(anchor, super type);
414: } else {
415: //check whether method in supertype is really overridden:
416: IMember super Method = (IMember) fTypeToMethod
417: .get(super type);
418: if (JavaModelUtil.isVisibleInHierarchy(super Method,
419: anchor.getPackageFragment())) {
420: IType rep = fUnionFind.find(anchor);
421: fUnionFind.union(rep, super Rep);
422: // current type is no root anymore
423: fRootTypes.remove(anchor);
424: uniteWithSupertypes(super type, super type);
425: } else {
426: //Not overridden -> overriding chain ends here.
427: }
428: }
429: }
430: }
431: }
|