Subtypes


1   /*
2    * Bytecode Analysis Framework
3    * Copyright (C) 2003-2005 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.ba.ch;
21  
22  import java.util.HashMap  ;
23  import java.util.HashSet  ;
24  import java.util.Map  ;
25  import java.util.Set  ;
26  
27  import org.apache.bcel.Repository;
28  import org.apache.bcel.classfile.Constant;
29  import org.apache.bcel.classfile.ConstantCP;
30  import org.apache.bcel.classfile.ConstantClass;
31  import org.apache.bcel.classfile.ConstantDouble;
32  import org.apache.bcel.classfile.ConstantLong;
33  import org.apache.bcel.classfile.ConstantNameAndType;
34  import org.apache.bcel.classfile.ConstantPool;
35  import org.apache.bcel.classfile.ConstantUtf8;
36  import org.apache.bcel.classfile.Field;
37  import org.apache.bcel.classfile.JavaClass;
38  import org.apache.bcel.classfile.Method;
39  
40  import edu.umd.cs.findbugs.SystemProperties;
41  import edu.umd.cs.findbugs.ba.AnalysisContext;
42  import edu.umd.cs.findbugs.ba.XFactory;
43  
44  /**
45   * Support for class hierarchy queries.
46   * 
47   * @author Bill Pugh
48   * @author David Hovemeyer
49   */
50  public class Subtypes {
51      private static final boolean DEBUG_HIERARCHY = false || SystemProperties.getBoolean("findbugs.debug.hierarchy");
52  
53      private boolean computed = false;
54  
55      private Set  <String  > referenced = new HashSet  <String  >();
56  
57      private Set  <JavaClass> allClasses = new HashSet  <JavaClass>();
58  
59      private Set  <JavaClass> applicationClasses = new HashSet  <JavaClass>();
60  
61      private Set  <JavaClass> parentsAdded = new HashSet  <JavaClass>();
62  
63      private Map  <JavaClass, Set  <JavaClass>> immediateSubtypes = new HashMap  <JavaClass, Set  <JavaClass>>();
64  
65      private Map  <JavaClass, Set  <JavaClass>> transitiveSubtypes = new HashMap  <JavaClass, Set  <JavaClass>>();
66  
67      public Subtypes() {
68      }
69      
70      /**
71       * Get immediate subtypes of given class or interface.
72       * 
73       * @param c a class or interface
74       * @return set of immediate subtypes
75       */
76      public Set  <JavaClass> getImmediateSubtypes(JavaClass c) {
77          if (!allClasses.contains(c))
78              addClass(c);
79          compute();
80          return immediateSubtypes.get(c);
81      }
82  
83      /**
84       * Determine if a class or interface has subtypes
85       * 
86       * @param c a class or interface
87       * @return true if c has any subtypes/interfaces
88       */
89      public boolean hasSubtypes(JavaClass c) {
90          if (!allClasses.contains(c))
91              addClass(c);
92          compute();
93          return !immediateSubtypes.get(c).isEmpty();
94      }
95  
96      /**
97       * Get set of all known classes and interfaces. 
98       * 
99       * @return set of all known classes and interfaces
100      */
101     public Set  <JavaClass> getAllClasses() {
102         compute();
103         return allClasses;
104     }
105 
106     /**
107      * Get set of all transitive subtypes of given class or interface,
108      * <em>not including the class or interface itself</em>.
109      * 
110      * @param c a class or interface
111      * @return set of all transitive subtypes
112      */
113     public Set  <JavaClass> getTransitiveSubtypes(JavaClass c) {
114         if (!allClasses.contains(c))
115             addClass(c);
116         compute();
117         return transitiveSubtypes.get(c);
118     }
119     
120     /**
121      * Get set of all known transitive classes and interfaces which are subtypes of
122      * both of the given classes and/or interfaces.  Note that in this method,
123      * we consider a class to be a subtype of itself.  Therefore, this method
124      * can be used to determine, e.g., if there are any classes implementing
125      * both of two given interfaces.
126      * 
127      * @param a a class or interface
128      * @param b another class or interface
129      * @return set of all common subtypes of <i>a</i> and <i>b</i>
130      */
131     public Set  <JavaClass> getTransitiveCommonSubtypes(JavaClass a, JavaClass b) {
132         Set  <JavaClass> result = new HashSet  <JavaClass>();
133         
134         // Get all subtypes of A, inclusive
135         result.addAll(getTransitiveSubtypes(a));
136         result.add(a);
137         
138         // Is B a subtype of A?
139         boolean bIsSubtypeOfA = result.contains(b); 
140         
141         // Remove all subtypes of A which aren't proper subtypes of B
142         result.retainAll(getTransitiveSubtypes(b));
143         
144         // Fix up: if B is a subtype of A, then we were wrong to
145         // remove it.  Add it back if appropriate.
146         if (bIsSubtypeOfA)
147             result.add(b);
148         
149         return result;
150     }
151 
152     private void addReferencedClasses(JavaClass c) {
153         if (DEBUG_HIERARCHY)
154             System.out.println("adding referenced classes for "
155                     + c.getClassName());
156         ConstantPool cp = c.getConstantPool();
157         Constant[] constants = cp.getConstantPool();
158         for (int i = 0; i < constants.length; i++) {
159             Constant co = constants[i];
160             if (co instanceof ConstantDouble || co instanceof ConstantLong)
161                 i++;
162             if (co instanceof ConstantClass) {
163                 String   name = ((ConstantClass) co).getBytes(cp);
164                 name = extractClassName(name);
165                 if (DEBUG_HIERARCHY)
166                     System.out.println(i + " : " + name);
167                 addNamedClass(name);
168             } else if (co instanceof ConstantCP) {
169                 ConstantCP co2 = (ConstantCP) co;
170                 ConstantNameAndType nt = (ConstantNameAndType) cp
171                         .getConstant(co2.getNameAndTypeIndex());
172                 String   sig = ((ConstantUtf8) cp.getConstant(nt
173                         .getSignatureIndex())).getBytes();
174                 while (true) {
175                     int j = sig.indexOf('L');
176                     if (j == -1)
177                         break;
178                     int k = sig.indexOf(';', j);
179                     String   name = sig.substring(j + 1, k);
180                     if (DEBUG_HIERARCHY)
181                         System.out.println(i + " : " + name);
182                     addNamedClass(name);
183                     sig = sig.substring(k + 1);
184                 }
185 
186             }
187         }
188     }
189 
190     public static void learnFieldsAndMethods(JavaClass c) {
191         for(Field f : c.getFields())
192             XFactory.createXField(c, f);
193         for(Method m : c.getMethods())
194             XFactory.createXMethod(c, m);
195     }
196     public void addNamedClass(String   name) {
197         name = name.replace('/', '.');
198 
199         if (referenced.add(name))
200             try {
201                 
202                 JavaClass clazz = Repository.lookupClass(name);
203                 learnFieldsAndMethods(clazz);
204                 addClass(clazz);
205             } catch (ClassNotFoundException   e) {
206                 
207                 if (name.length() > 1) {
208                     AnalysisContext.reportMissingClass(e);
209                     // e.printStackTrace(System.out);
210                 }
211             }
212     }
213 
214     public void addApplicationClass(JavaClass c) {
215         if (c == null)
216             return;
217         if (DEBUG_HIERARCHY)
218             System.out.println("Adding application class " + c.getClassName());
219         if (applicationClasses.add(c)) {
220             learnFieldsAndMethods(c);
221             if (DEBUG_HIERARCHY && computed)
222                 System.out.println("Need to recompute");
223             computed = false;
224         }
225 
226     }
227 
228     public void addClass(JavaClass c) {
229         if (c == null)
230             return;
231         if (allClasses.add(c)) {
232             if (DEBUG_HIERARCHY)
233                 System.out.println("ADDING " + c.getClassName() + " " + System.identityHashCode(c) + " " + c.hashCode());
234             
235             immediateSubtypes.put(c, new HashSet  <JavaClass>());
236             if (DEBUG_HIERARCHY && computed)
237                 System.out.println("Need to recompute");
238             computed = false;
239         } else if (!immediateSubtypes.containsKey(c)) {
240             if (DEBUG_HIERARCHY)
241                 System.out.println("INITIALIZING " + c.getClassName() + " " + System.identityHashCode(c) + " " + c.hashCode());
242             immediateSubtypes.put(c, new HashSet  <JavaClass>());
243             }
244     }
245 
246     private void addParents(JavaClass c) {
247         if (!parentsAdded.add(c))
248             return;
249         try {
250             addParent(c.getSuperClass(), c);
251             for (JavaClass i : c.getInterfaces())
252                 addParent(i, c);
253         } catch (ClassNotFoundException   e) {
254             AnalysisContext.reportMissingClass(e);
255         }
256     }
257 
258     private void addParent(JavaClass p, JavaClass c) {
259         if (p == null)
260             return;
261         if (DEBUG_HIERARCHY)
262             System.out.println("adding " + c.getClassName() + " is a "
263                     + p.getClassName());
264         addClass(p);
265         addParents(p);
266         Set  <JavaClass> children = immediateSubtypes.get(p);
267         children.add(c);
268     }
269 
270     private void compute() {
271         if (computed) return;
272         if (DEBUG_HIERARCHY)
273             System.out.println("Computing {");
274         transitiveSubtypes.clear();
275         for (JavaClass c : applicationClasses) {
276             addClass(c);
277             addReferencedClasses(c);
278         }
279 
280         for (JavaClass c : new HashSet  <JavaClass>(allClasses)) {
281             addParents(c);
282         }
283         for (JavaClass c : allClasses) {
284             compute(c);
285         }
286         parentsAdded.clear();
287         if (DEBUG_HIERARCHY)
288             System.out.println("} Done Computing");
289         computed = true;
290     }
291 
292     private Set  <JavaClass> compute(JavaClass c) {
293         if (DEBUG_HIERARCHY)
294             System.out.println(" compute " + c.getClassName()
295             + " " 
296             + System.identityHashCode(c)
297             + " " 
298             + c.hashCode()
299             + " " 
300             + (immediateSubtypes.get(c) == null 
301                ? " id is null" : " id is non null"));
302         Set  <JavaClass> descendents = transitiveSubtypes.get(c);
303         if (descendents != null) {
304             if (!descendents.contains(c))
305                 System.out.println("This is wrong for " + c.getClassName());
306             return descendents;
307         }
308         descendents = new HashSet  <JavaClass>();
309         descendents.add(c);
310         transitiveSubtypes.put(c, descendents);
311         if (DEBUG_HIERARCHY)
312             System.out.println("immediate subtypes of "
313                 + c.getClassName()
314                 + " " 
315                 + System.identityHashCode(c)
316                 + " " 
317                 + c.hashCode()
318                 + (immediateSubtypes.get(c) == null 
319                    ? " is null" : " is non null"));
320                 
321         for (JavaClass child : immediateSubtypes.get(c)) {
322             if (DEBUG_HIERARCHY)
323                 System.out.println("Updating child " 
324                     + child.getClassName()
325                     + " of " 
326                     + c.getClassName());
327             descendents.addAll(compute(child));
328         }
329         if (DEBUG_HIERARCHY)
330             System.out.println(c.getClassName() + " has " + descendents.size()
331                     + " decendents");
332         return descendents;
333     }
334 
335     public static String   extractClassName(String   name) {
336         if (name.charAt(0) != '[' && name.charAt(name.length() - 1) != ';')
337             return name;
338         while (name.charAt(0) == '[')
339             name = name.substring(1);
340         if (name.charAt(0) == 'L' && name.charAt(name.length() - 1) == ';')
341             name = name.substring(1, name.length() - 1);
342         return name;
343     }
344 
345     /**
346      * Determine whether or not the given class is an application class.
347      * 
348      * @param javaClass a class
349      * @return true if it's an application class, false if not
350      */
351     public boolean isApplicationClass(JavaClass javaClass) {
352         boolean isAppClass = applicationClasses.contains(javaClass);
353         if (DEBUG_HIERARCHY) {
354             System.out.println(javaClass.getClassName() + " ==> " + (isAppClass ? "IS" : "IS NOT") + " an application class (" + applicationClasses.size() + " entries in app class map)");
355         }
356         return isAppClass;
357     }
358 }
359
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags