JTypeOracle


1   /*
2    * Copyright 2007 Google Inc.
3    * 
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5    * use this file except in compliance with the License. You may obtain a copy of
6    * 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, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations under
14   * the License.
15   */
16  package com.google.gwt.dev.jjs.ast;
17  
18  import java.util.ArrayList  ;
19  import java.util.HashMap  ;
20  import java.util.HashSet  ;
21  import java.util.IdentityHashMap  ;
22  import java.util.Iterator  ;
23  import java.util.List  ;
24  import java.util.Map  ;
25  import java.util.Set  ;
26  
27  /**
28   * Oracle that can answer questions regarding the types in a program.
29   */
30  public class JTypeOracle {
31  
32    private final Map  /* <JInterfaceType, Set<JClassType>> */couldBeImplementedMap = new IdentityHashMap  ();
33  
34    private final Map  /* <JClassType, Set<JInterfaceType>> */couldImplementMap = new IdentityHashMap  ();
35  
36    private final Set  /* <JReferenceType> */hasClinitSet = new HashSet  ();
37  
38    private final Map  /* <JClassType, Set<JInterfaceType>> */implementsMap = new IdentityHashMap  ();
39  
40    private final Set  /* <JReferenceType> */instantiatedTypes = new HashSet  ();
41  
42    private final Map  /* <JInterfaceType, Set<JClassType>> */isImplementedMap = new IdentityHashMap  ();
43  
44    private JClassType javaLangObject = null;
45  
46    private final JProgram program;
47  
48    private final Map  /* <JClassType, Set<JClassType>> */subClassMap = new IdentityHashMap  ();
49  
50    private final Map  /* <JInterfaceType, Set<JInterfaceType>> */subInterfaceMap = new IdentityHashMap  ();
51  
52    private final Map  /* <JClassType, Set<JClassType>> */superClassMap = new IdentityHashMap  ();
53  
54    private final Map  /* <JInterfaceType, Set<JInterfaceType>> */superInterfaceMap = new IdentityHashMap  ();
55  
56    private final Map  /* <JMethod, Map<JClassType, Set<JMethod>>> */virtualUpRefMap = new IdentityHashMap  ();
57  
58    public JTypeOracle(JProgram program) {
59      this.program = program;
60    }
61  
62    public boolean canTheoreticallyCast(JReferenceType type, JReferenceType qType) {
63      JClassType jlo = program.getTypeJavaLangObject();
64      if (type == qType || type == jlo) {
65        return true;
66      }
67  
68      if (canTriviallyCast(type, qType)) {
69        return true;
70      }
71  
72      if (type instanceof JArrayType) {
73  
74        JArrayType aType = (JArrayType) type;
75        if (qType instanceof JArrayType) {
76          JArrayType qaType = (JArrayType) qType;
77          JType leafType = aType.getLeafType();
78          JType qLeafType = qaType.getLeafType();
79          int dims = aType.getDims();
80          int qDims = qaType.getDims();
81  
82          // null[] or Object[] -> int[][] might work, other combinations won't
83          if (dims < qDims && leafType != program.getTypeJavaLangObject()
84              && !(leafType instanceof JNullType)) {
85            return false;
86          }
87  
88          if (dims == qDims) {
89            if (leafType instanceof JReferenceType
90                && qLeafType instanceof JReferenceType) {
91              return canTheoreticallyCast((JReferenceType) leafType,
92                  (JReferenceType) qLeafType);
93            }
94          }
95        }
96  
97      } else if (type instanceof JClassType) {
98  
99        JClassType cType = (JClassType) type;
100       if (qType instanceof JClassType) {
101         return isSubClass(cType, (JClassType) qType);
102       } else if (qType instanceof JInterfaceType) {
103         return getOrCreate(couldImplementMap, cType).contains(qType);
104       }
105     } else if (type instanceof JInterfaceType) {
106 
107       JInterfaceType iType = (JInterfaceType) type;
108       if (qType instanceof JClassType) {
109         return getOrCreate(couldBeImplementedMap, iType).contains(qType);
110       }
111     } else if (type instanceof JNullType) {
112     }
113 
114     return true;
115   }
116 
117   public boolean canTriviallyCast(JReferenceType type, JReferenceType qType) {
118     JClassType jlo = program.getTypeJavaLangObject();
119     if (type == qType || qType == jlo) {
120       return true;
121     }
122 
123     if (type instanceof JArrayType) {
124 
125       JArrayType aType = (JArrayType) type;
126       if (qType instanceof JArrayType) {
127         JArrayType qaType = (JArrayType) qType;
128         JType leafType = aType.getLeafType();
129         JType qLeafType = qaType.getLeafType();
130         int dims = aType.getDims();
131         int qDims = qaType.getDims();
132 
133         // int[][] -> Object[] or null[] trivially true
134         if (dims > qDims
135             && (qLeafType == jlo || qLeafType instanceof JNullType)) {
136           return true;
137         }
138 
139         if (dims == qDims) {
140           if (leafType instanceof JReferenceType
141               && qLeafType instanceof JReferenceType) {
142             return canTriviallyCast((JReferenceType) leafType,
143                 (JReferenceType) qLeafType);
144           }
145         }
146       }
147     } else if (type instanceof JClassType) {
148 
149       JClassType cType = (JClassType) type;
150       if (qType instanceof JClassType) {
151         return isSuperClass(cType, (JClassType) qType);
152       } else if (qType instanceof JInterfaceType) {
153         return implementsInterface(cType, (JInterfaceType) qType);
154       }
155     } else if (type instanceof JInterfaceType) {
156 
157       JInterfaceType iType = (JInterfaceType) type;
158       if (qType instanceof JInterfaceType) {
159         return extendsInterface(iType, (JInterfaceType) qType);
160       }
161     } else if (type instanceof JNullType) {
162 
163       return true;
164     }
165 
166     return false;
167   }
168 
169   /**
170    * Returns <code>true</code> if a static field access of <code>toType</code>
171    * from within <code>fromType</code> should generate a clinit call. This
172    * will be true in cases where <code>toType</code> has a live clinit method
173    * which we cannot statically know has already run. We can statically know the
174    * clinit method has already run when:
175    * <ol>
176    * <li><code>fromType == toType</code></li>
177    * <li><code>toType</code> is a superclass of <code>fromType</code>
178    * (because <code>toType</code>'s clinit would have already run
179    * <code>fromType</code>'s clinit; see JLS 12.4)</li>
180    * </ol>
181    */
182   public boolean checkClinit(JReferenceType fromType, JReferenceType toType) {
183     if (fromType == toType) {
184       return false;
185     }
186     if (!hasClinit(toType)) {
187       return false;
188     }
189     if (fromType instanceof JClassType && toType instanceof JClassType
190         && isSuperClass((JClassType) fromType, (JClassType) toType)) {
191       return false;
192     }
193     return true;
194   }
195 
196   public void computeAfterAST() {
197     recomputeClinits();
198   }
199 
200   public void computeBeforeAST() {
201     javaLangObject = program.getTypeJavaLangObject();
202     superClassMap.clear();
203     subClassMap.clear();
204     superInterfaceMap.clear();
205     subInterfaceMap.clear();
206     implementsMap.clear();
207     couldImplementMap.clear();
208     isImplementedMap.clear();
209     couldBeImplementedMap.clear();
210 
211     for (int i = 0; i < program.getDeclaredTypes().size(); ++i) {
212       JReferenceType type = (JReferenceType) program.getDeclaredTypes().get(i);
213       if (type instanceof JClassType) {
214         recordSuperSubInfo((JClassType) type);
215       } else {
216         recordSuperSubInfo((JInterfaceType) type);
217       }
218     }
219     for (int i = 0; i < program.getDeclaredTypes().size(); ++i) {
220       JReferenceType type = (JReferenceType) program.getDeclaredTypes().get(i);
221       if (type instanceof JClassType) {
222         computeImplements((JClassType) type);
223       }
224     }
225     for (int i = 0; i < program.getDeclaredTypes().size(); ++i) {
226       JReferenceType type = (JReferenceType) program.getDeclaredTypes().get(i);
227       if (type instanceof JClassType) {
228         computeCouldImplement((JClassType) type);
229       }
230     }
231     for (int i = 0; i < program.getDeclaredTypes().size(); ++i) {
232       JReferenceType type = (JReferenceType) program.getDeclaredTypes().get(i);
233       if (type instanceof JClassType) {
234         computeVirtualUpRefs((JClassType) type);
235       }
236     }
237   }
238 
239   /**
240    * Returns true if qType is a superinterface of type, directly or indirectly.
241    */
242   public boolean extendsInterface(JInterfaceType type, JInterfaceType qType) {
243     return getOrCreate(superInterfaceMap, type).contains(qType);
244   }
245 
246   public JMethod[] getAllVirtualOverrides(JMethod method) {
247     Set  /* <JMethod> */results = new HashSet  /* <JMethod> */();
248     Map  /* <JClassType, Set<JMethod>> */overrideMap = getOrCreateMap(
249         virtualUpRefMap, method);
250     for (Iterator   it = overrideMap.keySet().iterator(); it.hasNext();) {
251       JClassType classType = (JClassType) it.next();
252       if (instantiatedTypes.contains(classType)) {
253         Set  /* <JMethod> */set = (Set  ) overrideMap.get(classType);
254         results.addAll(set);
255       }
256     }
257     return (JMethod[]) results.toArray(new JMethod[results.size()]);
258   }
259 
260   public Set  /* <JReferenceType> */getInstantiatedTypes() {
261     return instantiatedTypes;
262   }
263 
264   public boolean hasClinit(JReferenceType type) {
265     if (hasDirectClinit(type)) {
266       return true;
267     }
268     if (type != null && type.extnds != null) {
269       return hasClinit(type.extnds);
270     }
271     return false;
272   }
273 
274   public boolean hasDirectClinit(JReferenceType type) {
275     return hasClinitSet.contains(type);
276   }
277 
278   /**
279    * Returns true if qType is an implemented interface of type, directly or
280    * indirectly.
281    */
282   public boolean implementsInterface(JClassType type, JInterfaceType qType) {
283     return getOrCreate(implementsMap, type).contains(qType);
284   }
285 
286   public boolean isInstantiatedType(JReferenceType type) {
287     if (type instanceof JNullType) {
288       return true;
289     }
290 
291     if (type instanceof JArrayType) {
292       JArrayType arrayType = (JArrayType) type;
293       if (arrayType.getLeafType() instanceof JNullType) {
294         return true;
295       }
296     }
297     return instantiatedTypes.contains(type);
298   }
299 
300   /**
301    * Returns true if qType is a subclass of type, directly or indirectly.
302    */
303   public boolean isSubClass(JClassType type, JClassType qType) {
304     return getOrCreate(subClassMap, type).contains(qType);
305   }
306 
307   /**
308    * Returns true if qType is a superclass of type, directly or indirectly.
309    */
310   public boolean isSuperClass(JClassType type, JClassType qType) {
311     return getOrCreate(superClassMap, type).contains(qType);
312   }
313 
314   public void recomputeClinits() {
315     hasClinitSet.clear();
316     for (int i = 0; i < program.getDeclaredTypes().size(); ++i) {
317       JReferenceType type = (JReferenceType) program.getDeclaredTypes().get(i);
318       computeHasClinit(type);
319     }
320   }
321 
322   public void setInstantiatedTypes(Set  /* <JReferenceType> */instantiatedTypes) {
323     this.instantiatedTypes.clear();
324     this.instantiatedTypes.addAll(instantiatedTypes);
325   }
326 
327   private/* <K, V> */void add(Map  /* <K, Set<V>> */map, Object   key,
328       Object   value) {
329     getOrCreate(map, key).add(value);
330   }
331 
332   /**
333    * Compute all of the things I might conceivably implement, either through
334    * super types or sub types.
335    */
336   private void computeCouldImplement(JClassType type) {
337     Set  /* <JInterfaceType> */couldImplementSet = getOrCreate(
338         couldImplementMap, type);
339     // all of my direct implements are trivially true
340     couldImplementSet.addAll(getOrCreate(implementsMap, type));
341     List  /* <JClassType> */subclasses = new ArrayList  /* <JClassType> */();
342     subclasses.addAll(getOrCreate(subClassMap, type));
343     for (Iterator   itSub = subclasses.iterator(); itSub.hasNext();) {
344       JClassType subclass = (JClassType) itSub.next();
345       for (Iterator   itIntf = subclass.implments.iterator(); itIntf.hasNext();) {
346         JInterfaceType intf = (JInterfaceType) itIntf.next();
347         couldImplementSet.add(intf);
348         for (Iterator   itIsUp = getOrCreate(superInterfaceMap, intf).iterator(); itIsUp.hasNext();) {
349           JInterfaceType isup = (JInterfaceType) itIsUp.next();
350           couldImplementSet.add(isup);
351         }
352       }
353     }
354     for (Iterator   itCouldImpl = couldImplementSet.iterator(); itCouldImpl.hasNext();) {
355       JInterfaceType couldImpl = (JInterfaceType) itCouldImpl.next();
356       add(couldBeImplementedMap, couldImpl, type);
357     }
358   }
359 
360   private void computeHasClinit(JReferenceType type) {
361     JMethod method = (JMethod) type.methods.get(0);
362     if (!method.body.statements.isEmpty()) {
363       hasClinitSet.add(type);
364     }
365   }
366 
367   /**
368    * Compute all of the things I implement directly, through super types.
369    */
370   private void computeImplements(JClassType type) {
371     Set  /* <JInterfaceType> */implementsSet = getOrCreate(implementsMap, type);
372     List  /* <JClassType> */list = new ArrayList  /* <JClassType> */();
373     list.add(type);
374     list.addAll(getOrCreate(superClassMap, type));
375     for (Iterator   itSuper = list.iterator(); itSuper.hasNext();) {
376       JClassType superclass = (JClassType) itSuper.next();
377       for (Iterator   itIntf = superclass.implments.iterator(); itIntf.hasNext();) {
378         JInterfaceType intf = (JInterfaceType) itIntf.next();
379         implementsSet.add(intf);
380         for (Iterator   itIsUp = getOrCreate(superInterfaceMap, intf).iterator(); itIsUp.hasNext();) {
381           JInterfaceType isup = (JInterfaceType) itIsUp.next();
382           implementsSet.add(isup);
383         }
384       }
385     }
386     for (Iterator   itImpl = implementsSet.iterator(); itImpl.hasNext();) {
387       JInterfaceType impl = (JInterfaceType) itImpl.next();
388       add(isImplementedMap, impl, type);
389     }
390   }
391 
392   /**
393    * WEIRD: Suppose class Foo declares void f(){} and unrelated interface I also
394    * declares void f(). Then suppose Bar extends Foo implements I and doesn't
395    * override f(). We need to record a "virtual" upref from Foo.f() to I.f() so
396    * that if I.f() is rescued AND Bar is instantiable, Foo.f() does not get
397    * pruned.
398    */
399   private void computeVirtualUpRefs(JClassType type) {
400     if (type.extnds == null || type.extnds == javaLangObject) {
401       return;
402     }
403 
404     /*
405      * For each interface I directly implement, check all methods and make sure
406      * I define implementations for them. If I don't, then check all my super
407      * classes to find virtual overrides.
408      */
409     for (Iterator   itIntf = type.implments.iterator(); itIntf.hasNext();) {
410       JInterfaceType intf = (JInterfaceType) itIntf.next();
411       computeVirtualUpRefs(type, intf);
412       Set  /* <JInterfaceType> */superIntfs = getOrCreate(superInterfaceMap,
413           intf);
414       for (Iterator   itSuper = superIntfs.iterator(); itSuper.hasNext();) {
415         JInterfaceType superIntf = (JInterfaceType) itSuper.next();
416         computeVirtualUpRefs(type, superIntf);
417       }
418     }
419   }
420 
421   /**
422    * For each interface I directly implement, check all methods and make sure I
423    * define implementations for them. If I don't, then check all my super
424    * classes to find virtual overrides.
425    */
426   private void computeVirtualUpRefs(JClassType type, JInterfaceType intf) {
427     outer : for (Iterator   itIntf = intf.methods.iterator(); itIntf.hasNext();) {
428       JMethod intfMethod = (JMethod) itIntf.next();
429       for (Iterator   itType = type.methods.iterator(); itType.hasNext();) {
430         JMethod classMethod = (JMethod) itType.next();
431         if (JProgram.methodsDoMatch(intfMethod, classMethod)) {
432           // this class directly implements the interface method
433           continue outer;
434         }
435       }
436 
437       // this class does not directly implement the interface method
438       // if any super classes do, create a virtual up ref
439       for (JClassType superType = type.extnds; superType != javaLangObject; superType = superType.extnds) {
440         for (Iterator   itSuper = superType.methods.iterator(); itSuper.hasNext();) {
441           JMethod superMethod = (JMethod) itSuper.next();
442           if (JProgram.methodsDoMatch(intfMethod, superMethod)) {
443             // this super class directly implements the interface method
444             // create a virtual up ref
445 
446             // System.out.println("Virtual upref from " + superType.getName()
447             // + "." + superMethod.getName() + " to " + intf.getName() + "."
448             // + intfMethod.getName() + " via " + type.getName());
449 
450             Map  /* <JClassType, Set<JMethod>> */classToMethodMap = getOrCreateMap(
451                 virtualUpRefMap, superMethod);
452             Set  /* <JMethod> */methodSet = getOrCreate(classToMethodMap, type);
453             methodSet.add(intfMethod);
454 
455             // do not search additional super types
456             continue outer;
457           }
458         }
459       }
460     }
461   }
462 
463   private/* <K, V> */Set  /* <V> */getOrCreate(Map  /* <K, Set<V>> */map,
464       Object   key) {
465     Set  /* <V> */set = (Set  ) map.get(key);
466     if (set == null) {
467       set = new HashSet  /* <V> */();
468       map.put(key, set);
469     }
470     return set;
471   }
472 
473   private/* <K, K2, V> */Map  /* <K2, V> */getOrCreateMap(
474       Map  /* <K, Map<K2, V>> */map, Object   key) {
475     Map  /* <K2, V> */map2 = (Map  ) map.get(key);
476     if (map2 == null) {
477       map2 = new HashMap  /* <K2, V> */();
478       map.put(key, map2);
479     }
480     return map2;
481   }
482 
483   /**
484    * Record the all of my super classes (and myself as a subclass of them).
485    */
486   private void recordSuperSubInfo(JClassType type) {
487     Set  /* <JClassType> */superSet = getOrCreate(superClassMap, type);
488     for (JClassType t = type.extnds; t != null; t = t.extnds) {
489       superSet.add(t);
490       add(subClassMap, t, type);
491     }
492   }
493 
494   /**
495    * Record the all of my super interfaces (and myself as a sub interface of
496    * them).
497    */
498   private void recordSuperSubInfo(JInterfaceType type) {
499     Set  /* <JInterfaceType> */superSet = getOrCreate(superInterfaceMap, type);
500     recordSuperSubInfo(type, superSet, type);
501   }
502 
503   /**
504    * Recursively record all of my super interfaces.
505    */
506   private void recordSuperSubInfo(JInterfaceType base,
507       Set  /* <JInterfaceType> */superSet, JInterfaceType cur) {
508     for (Iterator   it = cur.implments.iterator(); it.hasNext();) {
509       JInterfaceType intf = (JInterfaceType) it.next();
510       superSet.add(intf);
511       add(subInterfaceMap, intf, base);
512       recordSuperSubInfo(base, superSet, intf);
513     }
514   }
515 
516 }
517
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags