KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > jdt > internal > corext > refactoring > rename > RippleMethodFinder2


1 /*******************************************************************************
2  * Copyright (c) 2000, 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/

11 package org.eclipse.jdt.internal.corext.refactoring.rename;
12
13 import java.util.ArrayList JavaDoc;
14 import java.util.Collection JavaDoc;
15 import java.util.HashMap JavaDoc;
16 import java.util.HashSet JavaDoc;
17 import java.util.Iterator JavaDoc;
18 import java.util.List JavaDoc;
19 import java.util.Map JavaDoc;
20 import java.util.Set JavaDoc;
21
22 import org.eclipse.core.runtime.Assert;
23 import org.eclipse.core.runtime.CoreException;
24 import org.eclipse.core.runtime.IProgressMonitor;
25 import org.eclipse.core.runtime.OperationCanceledException;
26 import org.eclipse.core.runtime.SubProgressMonitor;
27
28
29 import org.eclipse.jdt.core.IMember;
30 import org.eclipse.jdt.core.IMethod;
31 import org.eclipse.jdt.core.IRegion;
32 import org.eclipse.jdt.core.IType;
33 import org.eclipse.jdt.core.ITypeHierarchy;
34 import org.eclipse.jdt.core.JavaCore;
35 import org.eclipse.jdt.core.JavaModelException;
36 import org.eclipse.jdt.core.WorkingCopyOwner;
37 import org.eclipse.jdt.core.search.IJavaSearchConstants;
38 import org.eclipse.jdt.core.search.IJavaSearchScope;
39 import org.eclipse.jdt.core.search.SearchMatch;
40 import org.eclipse.jdt.core.search.SearchPattern;
41
42 import org.eclipse.jdt.internal.corext.refactoring.RefactoringScopeFactory;
43 import org.eclipse.jdt.internal.corext.refactoring.RefactoringSearchEngine2;
44 import org.eclipse.jdt.internal.corext.util.JavaModelUtil;
45
46 public class RippleMethodFinder2 {
47     
48     private final IMethod fMethod;
49     private List JavaDoc/*<IMethod>*/ fDeclarations;
50     private ITypeHierarchy fHierarchy;
51     private Map JavaDoc/*IType, IMethod*/ fTypeToMethod;
52     private Set JavaDoc/*IType*/ fRootTypes;
53     private MultiMap/*IType, IType*/ fRootReps;
54     private Map JavaDoc/*IType, ITypeHierarchy*/ fRootHierarchies;
55     private UnionFind fUnionFind;
56     private boolean fExcludeBinaries;
57
58     private static class MultiMap {
59         HashMap JavaDoc/*<IType, Collection>*/ fImplementation= new HashMap JavaDoc();
60
61         public void put(IType key, IType value) {
62             Collection JavaDoc collection= (Collection JavaDoc) fImplementation.get(key);
63             if (collection == null) {
64                 collection= new HashSet JavaDoc();
65                 fImplementation.put(key, collection);
66             }
67             collection.add(value);
68         }
69         
70         public Collection JavaDoc get(IType key) {
71             return (Collection JavaDoc) fImplementation.get(key);
72         }
73     }
74     private static class UnionFind {
75         HashMap JavaDoc/*<IType, IType>*/ fElementToRepresentative= new HashMap JavaDoc();
76         
77         public void init(IType type) {
78             fElementToRepresentative.put(type, type);
79         }
80         
81         //path compression:
82
public IType find(IType element) {
83             IType root= element;
84             IType rep= (IType) fElementToRepresentative.get(root);
85             while (rep != null && ! rep.equals(root)) {
86                 root= rep;
87                 rep= (IType) fElementToRepresentative.get(root);
88             }
89             if (rep == null)
90                 return null;
91
92             rep= (IType) fElementToRepresentative.get(element);
93             while (! rep.equals(root)) {
94                 IType temp= element;
95                 element= rep;
96                 fElementToRepresentative.put(temp, root);
97                 rep= (IType) fElementToRepresentative.get(element);
98             }
99             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     
122     private RippleMethodFinder2(IMethod method, boolean excludeBinaries){
123         fMethod= method;
124         fExcludeBinaries= excludeBinaries;
125     }
126     
127     public static IMethod[] getRelatedMethods(IMethod method, boolean excludeBinaries, IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
128         try{
129             if (! MethodChecks.isVirtual(method))
130                 return new IMethod[]{ method };
131             
132             return new RippleMethodFinder2(method, excludeBinaries).getAllRippleMethods(pm, owner);
133         } finally{
134             pm.done();
135         }
136     }
137     public static IMethod[] getRelatedMethods(IMethod method, IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
138         return getRelatedMethods(method, true, pm, owner);
139     }
140     
141     private IMethod[] getAllRippleMethods(IProgressMonitor pm, WorkingCopyOwner owner) throws CoreException {
142         pm.beginTask("", 4); //$NON-NLS-1$
143

144         findAllDeclarations(new SubProgressMonitor(pm, 1), owner);
145         //TODO: report binary methods to an error status
146
//TODO: report assertion as error status and fall back to only return fMethod
147
//check for bug 81058:
148
Assert.isTrue(fDeclarations.contains(fMethod), "Search for method declaration did not find original element"); //$NON-NLS-1$
149

150         createHierarchyOfDeclarations(new SubProgressMonitor(pm, 1), owner);
151         createTypeToMethod();
152         createUnionFind();
153         if (pm.isCanceled())
154             throw new OperationCanceledException();
155
156         fHierarchy= null;
157         fRootTypes= null;
158
159         Map JavaDoc/*IType, List<IType>*/ partitioning= new HashMap JavaDoc();
160         for (Iterator JavaDoc iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
161             IType type= (IType) iter.next();
162             IType rep= fUnionFind.find(type);
163             List JavaDoc/*<IType>*/ types= (List JavaDoc) partitioning.get(rep);
164             if (types == null)
165                 types= new ArrayList JavaDoc();
166             types.add(type);
167             partitioning.put(rep, types);
168         }
169         Assert.isTrue(partitioning.size() > 0);
170         if (partitioning.size() == 1)
171             return (IMethod[]) fDeclarations.toArray(new IMethod[fDeclarations.size()]);
172         
173         //Multiple partitions; must look out for nasty marriage cases
174
//(types inheriting method from two ancestors, but without redeclaring it).
175
IType methodTypeRep= fUnionFind.find(fMethod.getDeclaringType());
176         List JavaDoc/*<IType>*/ relatedTypes= (List JavaDoc) partitioning.get(methodTypeRep);
177         boolean hasRelatedInterfaces= false;
178         List JavaDoc/*<IMethod>*/ relatedMethods= new ArrayList JavaDoc();
179         for (Iterator JavaDoc iter= relatedTypes.iterator(); iter.hasNext();) {
180             IType relatedType= (IType) iter.next();
181             relatedMethods.add(fTypeToMethod.get(relatedType));
182             if (relatedType.isInterface())
183                 hasRelatedInterfaces= true;
184         }
185         
186         //Definition: An alien type is a type that is not a related type. The set of
187
// alien types diminishes as new types become related (a.k.a marry a relatedType).
188

189         List JavaDoc/*<IMethod>*/ alienDeclarations= new ArrayList JavaDoc(fDeclarations);
190         fDeclarations= null;
191         alienDeclarations.removeAll(relatedMethods);
192         List JavaDoc/*<IType>*/ alienTypes= new ArrayList JavaDoc();
193         boolean hasAlienInterfaces= false;
194         for (Iterator JavaDoc iter= alienDeclarations.iterator(); iter.hasNext();) {
195             IMethod alienDeclaration= (IMethod) iter.next();
196             IType alienType= alienDeclaration.getDeclaringType();
197             alienTypes.add(alienType);
198             if (alienType.isInterface())
199                 hasAlienInterfaces= true;
200         }
201         if (alienTypes.size() == 0) //no nasty marriage scenarios without types to marry with...
202
return (IMethod[]) relatedMethods.toArray(new IMethod[relatedMethods.size()]);
203         if (! hasRelatedInterfaces && ! hasAlienInterfaces) //no nasty marriage scenarios without interfaces...
204
return (IMethod[]) relatedMethods.toArray(new IMethod[relatedMethods.size()]);
205         
206         //find all subtypes of related types:
207
HashSet JavaDoc/*<IType>*/ relatedSubTypes= new HashSet JavaDoc();
208         List JavaDoc/*<IType>*/ relatedTypesToProcess= new ArrayList JavaDoc(relatedTypes);
209         while (relatedTypesToProcess.size() > 0) {
210             //TODO: would only need subtype hierarchies of all top-of-ripple relatedTypesToProcess
211
for (Iterator JavaDoc iter= relatedTypesToProcess.iterator(); iter.hasNext();) {
212                 if (pm.isCanceled())
213                     throw new OperationCanceledException();
214                 IType relatedType= (IType) iter.next();
215                 ITypeHierarchy hierarchy= getCachedHierarchy(relatedType, owner, new SubProgressMonitor(pm, 1));
216                 if (hierarchy == null)
217                     hierarchy= relatedType.newTypeHierarchy(owner, new SubProgressMonitor(pm, 1));
218                 IType[] allSubTypes= hierarchy.getAllSubtypes(relatedType);
219                 for (int i= 0; i < allSubTypes.length; i++)
220                     relatedSubTypes.add(allSubTypes[i]);
221             }
222             relatedTypesToProcess.clear(); //processed; make sure loop terminates
223

224             HashSet JavaDoc/*<IType>*/ marriedAlienTypeReps= new HashSet JavaDoc();
225             for (Iterator JavaDoc iter= alienTypes.iterator(); iter.hasNext();) {
226                 if (pm.isCanceled())
227                     throw new OperationCanceledException();
228                 IType alienType= (IType) iter.next();
229                 IMethod alienMethod= (IMethod) fTypeToMethod.get(alienType);
230                 ITypeHierarchy hierarchy= getCachedHierarchy(alienType, owner, new SubProgressMonitor(pm, 1));
231                 if (hierarchy == null)
232                     hierarchy= alienType.newTypeHierarchy(owner, new SubProgressMonitor(pm, 1));
233                 IType[] allSubtypes= hierarchy.getAllSubtypes(alienType);
234                 for (int i= 0; i < allSubtypes.length; i++) {
235                     IType subtype= allSubtypes[i];
236                     if (relatedSubTypes.contains(subtype)) {
237                         if (JavaModelUtil.isVisibleInHierarchy(alienMethod, subtype.getPackageFragment())) {
238                             marriedAlienTypeReps.add(fUnionFind.find(alienType));
239                         } else {
240                             // not overridden
241
}
242                     }
243                 }
244             }
245             
246             if (marriedAlienTypeReps.size() == 0)
247                 return (IMethod[]) relatedMethods.toArray(new IMethod[relatedMethods.size()]);
248             
249             for (Iterator JavaDoc iter= marriedAlienTypeReps.iterator(); iter.hasNext();) {
250                 IType marriedAlienTypeRep= (IType) iter.next();
251                 List JavaDoc/*<IType>*/ marriedAlienTypes= (List JavaDoc) partitioning.get(marriedAlienTypeRep);
252                 for (Iterator JavaDoc iterator= marriedAlienTypes.iterator(); iterator.hasNext();) {
253                     IType marriedAlienInterfaceType= (IType) iterator.next();
254                     relatedMethods.add(fTypeToMethod.get(marriedAlienInterfaceType));
255                 }
256                 alienTypes.removeAll(marriedAlienTypes); //not alien any more
257
relatedTypesToProcess.addAll(marriedAlienTypes); //process freshly married types again
258
}
259         }
260
261         fRootReps= null;
262         fRootHierarchies= null;
263         fTypeToMethod= null;
264         fUnionFind= null;
265
266         return (IMethod[]) relatedMethods.toArray(new IMethod[relatedMethods.size()]);
267     }
268
269     private ITypeHierarchy getCachedHierarchy(IType type, WorkingCopyOwner owner, IProgressMonitor monitor) throws JavaModelException {
270         IType rep= fUnionFind.find(type);
271         if (rep != null) {
272             Collection JavaDoc collection= fRootReps.get(rep);
273             for (Iterator JavaDoc iter= collection.iterator(); iter.hasNext();) {
274                 IType root= (IType) iter.next();
275                 ITypeHierarchy hierarchy= (ITypeHierarchy) fRootHierarchies.get(root);
276                 if (hierarchy == null) {
277                     hierarchy= root.newTypeHierarchy(owner, new SubProgressMonitor(monitor, 1));
278                     fRootHierarchies.put(root, hierarchy);
279                 }
280                 if (hierarchy.contains(type))
281                     return hierarchy;
282             }
283         }
284         return null;
285     }
286
287     private void findAllDeclarations(IProgressMonitor monitor, WorkingCopyOwner owner) throws CoreException {
288         fDeclarations= new ArrayList JavaDoc();
289         final RefactoringSearchEngine2 engine= new RefactoringSearchEngine2(SearchPattern.createPattern(fMethod, IJavaSearchConstants.DECLARATIONS | IJavaSearchConstants.IGNORE_DECLARING_TYPE | IJavaSearchConstants.IGNORE_RETURN_TYPE, SearchPattern.R_ERASURE_MATCH | SearchPattern.R_CASE_SENSITIVE));
290         if (owner != null)
291             engine.setOwner(owner);
292         engine.setScope(RefactoringScopeFactory.createRelatedProjectsScope(fMethod.getJavaProject(), IJavaSearchScope.SOURCES | IJavaSearchScope.APPLICATION_LIBRARIES | IJavaSearchScope.SYSTEM_LIBRARIES));
293         engine.setFiltering(false, fExcludeBinaries);
294         engine.setGrouping(false);
295         engine.searchPattern(new SubProgressMonitor(monitor, 1));
296         final SearchMatch[] matches= (SearchMatch[]) engine.getResults();
297         IMethod method= null;
298         for (int index= 0; index < matches.length; index++) {
299             method= (IMethod) matches[index].getElement();
300             if (method != null)
301                 fDeclarations.add(method);
302         }
303     }
304
305     private void createHierarchyOfDeclarations(IProgressMonitor pm, WorkingCopyOwner owner) throws JavaModelException {
306         IRegion region= JavaCore.newRegion();
307         for (Iterator JavaDoc iter= fDeclarations.iterator(); iter.hasNext();) {
308             IType declaringType= ((IMethod) iter.next()).getDeclaringType();
309             region.add(declaringType);
310         }
311         fHierarchy= JavaCore.newTypeHierarchy(region, owner, pm);
312     }
313     
314     private void createTypeToMethod() {
315         fTypeToMethod= new HashMap JavaDoc();
316         for (Iterator JavaDoc iter= fDeclarations.iterator(); iter.hasNext();) {
317             IMethod declaration= (IMethod) iter.next();
318             fTypeToMethod.put(declaration.getDeclaringType(), declaration);
319         }
320     }
321
322     private void createUnionFind() throws JavaModelException {
323         fRootTypes= new HashSet JavaDoc(fTypeToMethod.keySet());
324         fUnionFind= new UnionFind();
325         for (Iterator JavaDoc iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
326             IType type= (IType) iter.next();
327             fUnionFind.init(type);
328         }
329         for (Iterator JavaDoc iter= fTypeToMethod.keySet().iterator(); iter.hasNext();) {
330             IType type= (IType) iter.next();
331             uniteWithSupertypes(type, type);
332         }
333         fRootReps= new MultiMap();
334         for (Iterator JavaDoc iter= fRootTypes.iterator(); iter.hasNext();) {
335             IType type= (IType) iter.next();
336             IType rep= fUnionFind.find(type);
337             if (rep != null)
338                 fRootReps.put(rep, type);
339         }
340         fRootHierarchies= new HashMap JavaDoc();
341     }
342
343     private void uniteWithSupertypes(IType anchor, IType type) throws JavaModelException {
344         IType[] supertypes= fHierarchy.getSupertypes(type);
345         for (int i= 0; i < supertypes.length; i++) {
346             IType supertype= supertypes[i];
347             IType superRep= fUnionFind.find(supertype);
348             if (superRep == null) {
349                 //Type doesn't declare method, but maybe supertypes?
350
uniteWithSupertypes(anchor, supertype);
351             } else {
352                 //check whether method in supertype is really overridden:
353
IMember superMethod= (IMember) fTypeToMethod.get(supertype);
354                 if (JavaModelUtil.isVisibleInHierarchy(superMethod, anchor.getPackageFragment())) {
355                     IType rep= fUnionFind.find(anchor);
356                     fUnionFind.union(rep, superRep);
357                     // current type is no root anymore
358
fRootTypes.remove(anchor);
359                     uniteWithSupertypes(supertype, supertype);
360                 } else {
361                     //Not overridden -> overriding chain ends here.
362
}
363             }
364         }
365     }
366 }
367
Popular Tags