CollectionFinder xref

View Javadoc

1   /*
2    * Created on Feb 1, 2004
3    *
4    * To change the template for this generated file go to
5    * Window>Preferences>Java>Code Generation>Code and Comments
6    */
7   package joeq.Compiler.Analysis.IPA;
8   
9   import java.util.Collection;
10  import java.util.HashMap;
11  import java.util.HashSet;
12  import java.util.Iterator;
13  import java.util.LinkedList;
14  import java.util.Map;
15  import java.util.Set;
16  import java.io.DataOutputStream;
17  import java.io.FileOutputStream;
18  import java.io.IOException;
19  import java.io.PrintStream;
20  import java.math.BigInteger;
21  import joeq.Class.jq_Class;
22  import joeq.Class.jq_Field;
23  import joeq.Class.jq_Initializer;
24  import joeq.Class.jq_InstanceMethod;
25  import joeq.Class.jq_Method;
26  import joeq.Class.jq_Reference;
27  import joeq.Class.jq_Type;
28  import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
29  import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.Node;
30  import joeq.Compiler.Analysis.IPSSA.IPSSABuilder;
31  import joeq.Compiler.Analysis.IPSSA.IPSSABuilder.Application;
32  import jwutil.util.Assert;
33  import net.sf.javabdd.BDD;
34  import net.sf.javabdd.TypedBDDFactory;
35  import net.sf.javabdd.TypedBDDFactory.TypedBDD;
36  
37  /***
38   * Finds and outputs information about polymorphic:
39   *  - fields
40   *  - method parameters
41   * 
42   * The result is output in XML.
43   * */
44  public class CollectionFinder extends Application {    
45      static final String OBJECT_SIGNATURE = "Ljava.lang.Object;";
46  
47      public static String xmlEscape(String s) {
48          s = s.replaceAll("<", "&lt;");
49          s = s.replaceAll("<", "&gt;");
50  
51          return s;
52      }
53      private final static String _outFile = "polyclasses.xml";
54      private PA          _r               = null;
55      private static final boolean TRACE = false;
56  
57      public CollectionFinder() {
58          this(null,null,null);
59      }
60      public CollectionFinder(IPSSABuilder builder, String name, String[] args) {
61          super(builder, name, args);        
62      }
63      
64      private Collection buildList(BDD e) {
65          Collection c = new LinkedList();
66          for (Iterator i = e.iterator(_r.T2set); i.hasNext(); ) {
67              BDD b = (BDD) i.next();
68              BDD d = b.relprod(_r.aT, _r.T2set);
69              b.free();
70              
71              //c.add(_r.getResults().toString((TypedBDDFactory.TypedBDD)d, -1));
72              c.add(d.toString());
73          }
74          
75          return c;
76      }
77      
78      public BDD calculateCommonSupertype(BDD types) {
79          if (types.isZero()) return _r.bdd.zero();
80          BDD bestTypes = _r.T1.domain();
81          
82          // TODO: need to skip NULL, which is T1(0) = T2(0)
83          //System.out.println("Looking for supertype of "+types.toStringWithDomains(r.TS));
84          for (Iterator i = types.iterator(_r.T2set); i.hasNext(); ) {
85              BDD b = (BDD) i.next();
86              BDD c = b.relprod(_r.aT, _r.T2set);
87              b.free();
88              bestTypes.andWith(c); // T1
89          }
90          
91          //System.err.println( "bestTypes: " + bestTypes.toStringWithDomains() );
92          for (Iterator i = bestTypes.iterator(_r.T1set); i.hasNext(); ) {
93              BDD b = (BDD) i.next();
94              BDD c = b.relprod(_r.aT, _r.T1set); // T2
95              b.free();
96              
97              /*if(!c.and(_r.T2.ithVar(0)).isZero()) {
98                  System.out.println( 
99                      c.toStringWithDomains(_r.TS) + " is " + 
100                     !c.and(_r.T2.ithVar(0)).isZero() );
101 
102                 System.err.println("Before: " + c.toStringWithDomains(_r.TS));
103                 c.restrictWith(_r.T2.ithVar(0));
104                 System.err.println("After : " + c.toStringWithDomains(_r.TS));
105             }*/
106             
107             c.replaceWith(_r.T2toT1); // T1
108             c.andWith(bestTypes.id()); // T1
109                                    
110             if (c.satCount(_r.T1set) == 1.0) {
111                 return c;
112             }
113         }
114         System.out.println("No subtype matches! "+bestTypes.toStringWithDomains(_r.TS));
115         return _r.bdd.zero();
116     }
117     
118     public BDD calculateConcreteTypes(BDD types, boolean removeNull) {
119         TypedBDD tb = (TypedBDD)types;
120         BDD t = tb.getDomainSet().contains(_r.H1c) ? 
121                 types.relprod(_r.hT, _r.H1set.union(_r.H1cset)) :
122                 types.relprod(_r.hT, _r.H1set);
123         
124         // Remove NULL if it's present
125         if(removeNull && !t.and(_r.T2.ithVar(0)).isZero()) {
126             //System.out.println( t.toStringWithDomains(_r.TS) + " is " + 
127             //        !t.and(_r.T2.ithVar(0)).isZero() );
128 
129             t.restrictWith(_r.T2.ithVar(0));
130         }
131         
132         //System.err.println("Types: " + t.toStringWithDomains(_r.TS));        
133         
134         return t;
135     }
136 
137     public jq_Reference getType(TypedBDD types) {              
138         BigInteger[] indeces = _r.T2.getVarIndices(types);
139         Assert._assert(indeces.length == 1, "There are " + indeces.length + " indeces in " + types.toStringWithDomains());
140         BigInteger index = indeces[0];
141         jq_Reference type = (jq_Reference)_r.Tmap.get(index.intValue());
142         //System.out.println("Index: " + index + " type: " + type);
143  
144         return type;        
145     }
146     
147     protected void parseParams(String[] args) {}
148 
149     private void printFields(PrintStream out, Collection c, String name) {
150         out.println("<fieldset name = \"" + name + "\">");
151         for(Iterator iter = c.iterator(); iter.hasNext();) {
152             jq_Field f = (jq_Field)iter.next();
153             
154             out.println("\t<field name=\""  + f + "\" type=\"" + f.getType() + "\">");            
155             out.println("\t</field>");
156         }
157         out.println("</fieldset>");
158     }
159     
160     private void printFieldsWithPointeeTypes(PrintStream out, Collection c, Map map, String name) {
161         out.println("<fieldset name = \"" + name + "\">");
162         for(Iterator iter = c.iterator(); iter.hasNext();) {
163             jq_Field f = (jq_Field)iter.next();
164             
165             out.println("\t<field name=\""  + f + "\" type=\"" + f.getType() + "\">");
166             if(map != null && map.containsKey(f)) {
167                 String s = (String)map.get(f);
168                 
169                 //out.println("\t\t<![CDATA[" + s + "]]>");
170                 out.println(s);
171             }
172             
173             out.println("\t</field>");
174         }
175         out.println("</fieldset>");
176     }
177 
178     private void printNodesWithPointeeTypes(PrintStream out, Map methodMap, Map map, String name) {        
179         for(Iterator methodIter = methodMap.keySet().iterator(); methodIter.hasNext();) {
180             jq_Class clazz = (jq_Class)methodIter.next();
181             out.println("<paramset name = \"" + xmlEscape(clazz.toString()) + "\">");
182             Collection c = (Collection)methodMap.get(clazz);
183             for(Iterator iter = c.iterator(); iter.hasNext();) {
184                 MethodSummary.ParamNode n = (MethodSummary.ParamNode)iter.next();
185                 out.println(
186                         "\t<param method=\""  + xmlEscape(n.getDefiningMethod().toString()) + 
187                         //" \" name=\"" + method. 
188                         " \" number=\"" + n.getIndex() + "\">");
189                 if(map != null && map.containsKey(n)) {
190                     String s = (String)map.get(n);
191                     
192                     //out.println("\t\t<![CDATA[" + s + "]]>");
193                     out.println(s);
194                 }
195                 
196                 out.println("\t</param>");
197             }
198             out.println("</paramset>");
199         }        
200     }
201     
202     void printPolyFieldInfo(PrintStream out) throws IOException {
203         _r = _builder.getPAResults().getPAResults();
204         
205         BDD fh2 = _r.hP.exist(_r.H1set); // FxH2
206         //int singleTypeFields = 0, singleObjectFields = 0, unusedFields = 0, refinedTypeFields = 0;
207         Collection singleTypeFields     = new LinkedList();
208         Collection singleObjectFields   = new LinkedList();
209         Collection unusedFields         = new LinkedList();
210         Collection refinedTypeFields    = new LinkedList();
211         Collection nullFields           = new LinkedList();
212         
213         Map refinedData                 = new HashMap();
214         Set polyClasses                 = new HashSet();
215         
216         for (int i = 0; i < _r.Fmap.size(); ++i) {
217             jq_Field f = (jq_Field) _r.Fmap.get(i);
218             BDD b = _r.F.ithVar(i);
219             BDD c = fh2.restrict(b); // H2
220             if (c.isZero()) {
221                 unusedFields.add(f);
222                 if(TRACE) System.err.println("Unused field " + f);
223                 continue;
224             }
225             c.replaceWith(_r.H2toH1); // H1
226             if (c.satCount(_r.H1set) == 1.0) {
227                 singleObjectFields.add(f);
228                 if(TRACE) System.err.println("Single object field " + f);
229             }
230             BDD d = c.relprod(_r.hT, _r.H1set); // T2
231             
232             if (d.satCount(_r.T2set) == 1.0) {
233                 singleTypeFields.add(f);
234                 if(TRACE) System.err.println("Single type field " + f);
235             } else {
236                 if (f != null && !f.isStatic()) {
237                     if(TRACE) System.err.println("Poly class " + f.getDeclaringClass());
238                     polyClasses.add(f.getDeclaringClass());
239                 }
240             }
241 
242             // e is the common supertype of the pointees
243             //BDD e = calculateCommonSupertype(d); // T1
244             BDD e = calculateConcreteTypes(c, true); // T1
245             if(f == null) continue;
246             if(e.isOne()) {
247                 // formerly removed NULL
248                 nullFields.add(f);
249             }else
250             if(e.satCount(_r.T2set) > 1){
251                 refinedTypeFields.add(f);
252                 
253                 refinedData.put(f, typesetToString(e));
254                 //refinedData.put(f, e.toStringWithDomains(_r.TS));
255                 //System.err.println("Refined type field " + f);
256             }
257             /*
258             if (f != null) {
259                 int T_i = _r.Tmap.get(f.getType());
260                 BDD g = _r.T1.ithVar(T_i);      // g is the declared type
261                 if (!e.equals(g)) {
262                     e.replaceWith(_r.T1toT2);
263                     // declared type coinsides with the least precise type put into the field
264                     //if (e.andWith(g).and(_r.aT).isZero()) {
265                         //System.out.println("Field "+f);
266                         //System.out.println(" Declared: "+f.getType()+" Computed: "+e.toStringWithDomains(_r.TS));
267                     } else {
268                         // means that the types of the pointees are different from the declared type --
269                         // the declared type is wider than the use type
270                                           
271                         if(c.satCount(_r.T2set) > 1){
272                             refinedTypeFields.add(f);
273                             refinedData.put(f, e.toStringWithDomains(_r.TS));
274                             //System.err.println("Refined type field " + f);
275                         }
276                     //}   
277                 }
278                 g.free();
279             }*/
280             d.free();
281             e.free();
282             c.free();
283             b.free();
284         }
285         
286         // output the results
287         printFieldsWithPointeeTypes(out, refinedTypeFields, refinedData, "multitype (polymorphic) fields");
288         //printFields(out, unusedFields,      "unused fields");
289         printFields(out, nullFields,        "null fields");            
290         
291         if(TRACE) { 
292             System.out.println("Refined-type fields: "+refinedTypeFields+" / "+_r.Fmap.size()+" = "+(double)refinedTypeFields.size()/_r.Fmap.size());
293             System.out.println("Single-type fields: "+singleTypeFields+" / "+_r.Fmap.size()+" = "+(double)singleTypeFields.size()/_r.Fmap.size());
294             System.out.println("Single-object fields: "+singleObjectFields+" / "+_r.Fmap.size()+" = "+(double)singleObjectFields.size()/_r.Fmap.size());
295             System.out.println("Unused fields: "+unusedFields+" / "+_r.Fmap.size()+" = "+(double)unusedFields.size()/_r.Fmap.size());
296             System.out.println("Poly classes: "+polyClasses.size());
297         }
298     }
299     
300     void printPolyParamInfo(PrintStream out) throws IOException {
301         _r = _builder.getPAResults().getPAResults();
302         
303         Map polyMethods     = new HashMap();
304         Map polyParamsData  = new HashMap();
305  
306         for(int i = 0; i < _r.Vmap.size(); ++i) {
307             Node node = (Node)_r.Vmap.get(i);
308             if(node instanceof MethodSummary.ParamNode) {
309                 BDD param = _r.V1.ithVar(i);
310                 MethodSummary.ParamNode pnode = (MethodSummary.ParamNode)node;
311                 
312                 BDD h = param.relprod(_r.vP, _r.V1set);
313                 BDD e = calculateConcreteTypes(h, true);
314                 jq_Method method = node.getDefiningMethod();
315                 if(method instanceof jq_Initializer) {
316                     // skip the constructors
317                     continue;
318                 }
319                 
320                 if(pnode.getIndex() == 0 && method instanceof jq_InstanceMethod && 
321                         !((jq_InstanceMethod)method).isStatic())
322                 {              
323                     // polymorphic in "this" argument
324                     continue;
325                 }              
326                 if( !((TypedBDD)e).getDomainSet().isEmpty() && e.satCount(_r.T2set) > 1 ){
327                     //System.out.println(
328                     //    method + ": " + node + ": " + method.getParamTypes()[pnode.getIndex()] + " " +
329                     //    e.toStringWithDomains(_r.TS));
330 
331                     jq_Class clazz = method.getDeclaringClass();
332                     Collection c = (Collection)polyMethods.get(clazz); 
333                     if(c == null) {
334                         c = new LinkedList();
335                         polyMethods.put(clazz, c);
336                     }
337                     c.add(node);                    
338                     polyParamsData.put(node, typesetToString(e));
339                     //polyParamsData.put(node, e.toStringWithDomains(_r.TS));
340                     //System.err.println("Refined type field " + f);
341                 }
342                 param.free();
343                 h.free();
344             }
345         }
346         
347         printNodesWithPointeeTypes(out, polyMethods, polyParamsData, "polymorphic parameters");   
348     }
349 
350     public void run() {
351         try {
352             PrintStream out = new PrintStream(new DataOutputStream(new FileOutputStream(_outFile)));
353             out.println("<?xml version=\"1.0\"?>");
354             out.println("<root>");            
355                 // do the field stat
356                 printPolyFieldInfo(out);
357                 // do the param stat
358                 printPolyParamInfo(out);
359             out.println("</root>");
360             out.close();
361         } catch (IOException e) {
362             e.printStackTrace();
363         }
364     }
365         
366     private String typesetToString(BDD e) {
367         TypedBDDFactory.TypedBDD te = (TypedBDD)e;
368         //System.err.println(te.getDomainSet());
369         if(te.getDomainSet().isEmpty()){
370             return "";
371         }
372         Assert._assert(te.getDomainSet().contains(_r.T2));
373 
374         StringBuffer result = 
375             new StringBuffer("\t\t<typeset size=\"" + (int)e.satCount(_r.T2set) + "\"> \n"); 
376         for(Iterator iter2 = e.iterator(_r.T2set); iter2.hasNext();) {
377             BDD tt = (BDD)iter2.next();
378             jq_Type type = getType((TypedBDD)tt);
379             Assert._assert(type != null);
380             boolean isAbstract  = type instanceof jq_Class && ((jq_Class)type).isAbstract();
381             boolean isInterface = type instanceof jq_Class && ((jq_Class)type).isInterface();
382             
383             result.append(
384                     "\t\t\t<type " +
385                     "abstract=\""  + (isAbstract ?"yes":"no") + "\" " + 
386                     "interface=\"" + (isInterface?"yes":"no") +
387                     "\">" +  
388                     "<![CDATA[" + type.toString() + "]]>"
389                     + "</type> \n");
390         }
391         
392         result.append("\t\t</typeset>\n");
393         
394         return result.toString();
395     }
396 }
397