KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > typing > integer > TypeResolver


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-2000 Etienne Gagnon. All rights reserved.
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */

19
20 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */

25
26
27 package soot.jimple.toolkits.typing.integer;
28
29 import soot.*;
30 import soot.jimple.*;
31 import soot.util.*;
32 import java.util.*;
33 import soot.toolkits.graph.*;
34 import soot.toolkits.scalar.*;
35 import java.io.*;
36
37 /**
38  * This class resolves the type of local variables.
39  **/

40 public class TypeResolver
41 {
42   /** All type variable instances **/
43   private final List typeVariableList = new ArrayList();
44
45   /** Hashtable: [TypeNode or Local] -> TypeVariable **/
46   private final Map typeVariableMap = new HashMap();
47
48   private final JimpleBody stmtBody;
49
50   final TypeVariable BOOLEAN = typeVariable(ClassHierarchy.v().BOOLEAN);
51   final TypeVariable BYTE = typeVariable(ClassHierarchy.v().BYTE);
52   final TypeVariable SHORT = typeVariable(ClassHierarchy.v().SHORT);
53   final TypeVariable CHAR = typeVariable(ClassHierarchy.v().CHAR);
54   final TypeVariable INT = typeVariable(ClassHierarchy.v().INT);
55   final TypeVariable TOP = typeVariable(ClassHierarchy.v().TOP);
56   final TypeVariable R0_1 = typeVariable(ClassHierarchy.v().R0_1);
57   final TypeVariable R0_127 = typeVariable(ClassHierarchy.v().R0_127);
58   final TypeVariable R0_32767 = typeVariable(ClassHierarchy.v().R0_32767);
59
60   private static final boolean DEBUG = false;
61
62   // categories for type variables (solved = hard, unsolved = soft)
63
private List unsolved;
64   private List solved;
65
66   /** Get type variable for the given local. **/
67   TypeVariable typeVariable(Local local)
68   {
69     TypeVariable result = (TypeVariable) typeVariableMap.get(local);
70
71     if(result == null)
72       {
73     int id = typeVariableList.size();
74     typeVariableList.add(null);
75
76     result = new TypeVariable(id, this);
77
78     typeVariableList.set(id, result);
79     typeVariableMap.put(local, result);
80     
81     if(DEBUG)
82       {
83         G.v().out.println("[LOCAL VARIABLE \"" + local + "\" -> " + id + "]");
84       }
85       }
86     
87     return result;
88   }
89
90   /** Get type variable for the given type node. **/
91   public TypeVariable typeVariable(TypeNode typeNode)
92   {
93     TypeVariable result = (TypeVariable) typeVariableMap.get(typeNode);
94
95     if(result == null)
96       {
97     int id = typeVariableList.size();
98     typeVariableList.add(null);
99
100     result = new TypeVariable(id, this, typeNode);
101
102     typeVariableList.set(id, result);
103     typeVariableMap.put(typeNode, result);
104       }
105
106     return result;
107   }
108
109   /** Get type variable for the given type. **/
110   public TypeVariable typeVariable(Type type)
111   {
112     return typeVariable(ClassHierarchy.v().typeNode(type));
113   }
114
115   /** Get new type variable **/
116   public TypeVariable typeVariable()
117   {
118     int id = typeVariableList.size();
119     typeVariableList.add(null);
120     
121     TypeVariable result = new TypeVariable(id, this);
122     
123     typeVariableList.set(id, result);
124     
125     return result;
126   }
127
128   private TypeResolver(JimpleBody stmtBody)
129   {
130     this.stmtBody = stmtBody;
131   }
132
133   public static void resolve(JimpleBody stmtBody)
134   {
135     if(DEBUG)
136       {
137     G.v().out.println(stmtBody.getMethod());
138       }
139
140     try
141       {
142     TypeResolver resolver = new TypeResolver(stmtBody);
143     resolver.resolve_step_1();
144       }
145     catch(TypeException e1)
146       {
147     if(DEBUG)
148       {
149         G.v().out.println("[integer] Step 1 Exception-->" + e1.getMessage());
150       }
151     
152     try
153       {
154         TypeResolver resolver = new TypeResolver(stmtBody);
155         resolver.resolve_step_2();
156       }
157     catch(TypeException e2)
158       {
159               StringWriter st = new StringWriter();
160           PrintWriter pw = new PrintWriter(st);
161           e2.printStackTrace(pw);
162           pw.close();
163               throw new RuntimeException JavaDoc(st.toString());
164       }
165       }
166   }
167   
168   private void debug_vars(String JavaDoc message)
169   {
170     if(DEBUG)
171       {
172     int count = 0;
173     G.v().out.println("**** START:" + message);
174     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
175         final TypeVariable var = (TypeVariable) varIt.next();
176         G.v().out.println(count++ + " " + var);
177       }
178     G.v().out.println("**** END:" + message);
179       }
180   }
181
182   private void debug_body()
183   {
184     if(DEBUG)
185       {
186     G.v().out.println("-- Body Start --");
187     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
188         final Stmt stmt = (Stmt) stmtIt.next();
189         G.v().out.println(stmt);
190       }
191     G.v().out.println("-- Body End --");
192       }
193   }
194
195   private void resolve_step_1() throws TypeException
196   {
197     collect_constraints_1();
198     debug_vars("constraints");
199
200     compute_approximate_types();
201     merge_connected_components();
202     debug_vars("components");
203
204     merge_single_constraints();
205     debug_vars("single");
206
207     assign_types_1();
208     debug_vars("assign");
209
210     try
211       {
212     check_constraints();
213       }
214     catch(TypeException e)
215       {
216     if(DEBUG)
217       {
218         G.v().out.println("[integer] Step 1(check) Exception [" + stmtBody.getMethod() + "]-->" + e.getMessage());
219       }
220     
221     check_and_fix_constraints();
222       }
223   }
224
225   private void resolve_step_2() throws TypeException
226   {
227     collect_constraints_2();
228     compute_approximate_types();
229     assign_types_2();
230     check_and_fix_constraints();
231   }
232
233   private void collect_constraints_1()
234   {
235     ConstraintCollector collector = new ConstraintCollector(this, true);
236
237     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
238
239         final Stmt stmt = (Stmt) stmtIt.next();
240     if(DEBUG)
241       {
242         G.v().out.print("stmt: ");
243       }
244     collector.collect(stmt, stmtBody);
245     if(DEBUG)
246       {
247         G.v().out.println(stmt);
248       }
249       }
250   }
251
252   private void collect_constraints_2()
253   {
254     ConstraintCollector collector = new ConstraintCollector(this, false);
255
256     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
257
258         final Stmt stmt = (Stmt) stmtIt.next();
259     if(DEBUG)
260       {
261         G.v().out.print("stmt: ");
262       }
263     collector.collect(stmt, stmtBody);
264     if(DEBUG)
265       {
266         G.v().out.println(stmt);
267       }
268       }
269   }
270
271   private void merge_connected_components() throws TypeException
272   {
273     compute_solved();
274     List list = new LinkedList();
275     list.addAll(solved);
276     list.addAll(unsolved);
277     
278     StronglyConnectedComponents.merge(list);
279   }
280   
281   private void merge_single_constraints() throws TypeException
282   {
283     boolean modified = true;
284     
285     while(modified)
286       {
287     modified = false;
288     refresh_solved();
289     
290     for( Iterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
291     
292         final TypeVariable var = (TypeVariable) varIt.next();
293         List children_to_remove = new LinkedList();
294         TypeNode lca = null;
295         
296         var.fixChildren();
297         
298         for( Iterator childIt = var.children().iterator(); childIt.hasNext(); ) {
299         
300             final TypeVariable child = (TypeVariable) childIt.next();
301         TypeNode type = child.type();
302         
303         if(type != null)
304           {
305             children_to_remove.add(child);
306             
307             if(lca == null)
308               {
309             lca = type;
310               }
311             else
312               {
313             lca = lca.lca_1(type);
314               }
315           }
316           }
317         
318         if(lca != null)
319           {
320         if(DEBUG)
321           {
322             if(lca == ClassHierarchy.v().TOP)
323               {
324             G.v().out.println("*** TOP *** " + var);
325             for(Iterator j = children_to_remove.iterator(); j.hasNext();)
326               {
327                 G.v().out.println("-- " + j.next());
328               }
329               }
330           }
331         
332         for( Iterator childIt = children_to_remove.iterator(); childIt.hasNext(); ) {
333         
334             final TypeVariable child = (TypeVariable) childIt.next();
335             var.removeChild(child);
336           }
337         
338         var.addChild(typeVariable(lca));
339           }
340
341         if(var.children().size() == 1)
342           {
343         TypeVariable child = (TypeVariable) var.children().get(0);
344         TypeNode type = child.type();
345         
346         if(type == null || type.type() != null)
347           {
348             var.union(child);
349             modified = true;
350           }
351           }
352       }
353       
354     if(!modified)
355       {
356         for( Iterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
357             final TypeVariable var = (TypeVariable) varIt.next();
358         List parents_to_remove = new LinkedList();
359         TypeNode gcd = null;
360         
361         var.fixParents();
362         
363         for( Iterator parentIt = var.parents().iterator(); parentIt.hasNext(); ) {
364         
365             final TypeVariable parent = (TypeVariable) parentIt.next();
366             TypeNode type = parent.type();
367             
368             if(type != null)
369               {
370             parents_to_remove.add(parent);
371             
372             if(gcd == null)
373               {
374                 gcd = type;
375               }
376             else
377               {
378                 gcd = gcd.gcd_1(type);
379               }
380               }
381           }
382         
383         if(gcd != null)
384           {
385             for( Iterator parentIt = parents_to_remove.iterator(); parentIt.hasNext(); ) {
386                 final TypeVariable parent = (TypeVariable) parentIt.next();
387             var.removeParent(parent);
388               }
389             
390             var.addParent(typeVariable(gcd));
391           }
392         
393         if(var.parents().size() == 1)
394           {
395             TypeVariable parent = (TypeVariable) var.parents().get(0);
396             TypeNode type = parent.type();
397             
398             if(type == null || type.type() != null)
399               {
400             var.union(parent);
401             modified = true;
402               }
403           }
404           }
405       }
406
407     if(!modified)
408       {
409         for( Iterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
410             final TypeVariable var = (TypeVariable) varIt.next();
411         
412         if(var.type() == null && var.inv_approx() != null && var.inv_approx().type() != null)
413           {
414             if(DEBUG)
415               {
416             G.v().out.println("*** I->" + var.inv_approx().type() + " *** " + var);
417               }
418             
419             var.union(typeVariable(var.inv_approx()));
420             modified = true;
421           }
422           }
423       }
424
425     if(!modified)
426       {
427         for( Iterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
428             final TypeVariable var = (TypeVariable) varIt.next();
429         
430         if(var.type() == null && var.approx() != null && var.approx().type() != null)
431           {
432             if(DEBUG)
433               {
434             G.v().out.println("*** A->" + var.approx().type() + " *** " + var);
435               }
436             
437             var.union(typeVariable(var.approx()));
438             modified = true;
439           }
440           }
441       }
442
443     if(!modified)
444       {
445         for( Iterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
446             final TypeVariable var = (TypeVariable) varIt.next();
447         
448         if(var.type() == null && var.approx() == ClassHierarchy.v().R0_32767)
449           {
450             if(DEBUG)
451               {
452             G.v().out.println("*** R->SHORT *** " + var);
453               }
454             
455             var.union(SHORT);
456             modified = true;
457           }
458           }
459       }
460
461     if(!modified)
462       {
463         for( Iterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
464             final TypeVariable var = (TypeVariable) varIt.next();
465         
466         if(var.type() == null && var.approx() == ClassHierarchy.v().R0_127)
467           {
468             if(DEBUG)
469               {
470             G.v().out.println("*** R->BYTE *** " + var);
471               }
472             
473             var.union(BYTE);
474             modified = true;
475           }
476           }
477       }
478
479     if(!modified)
480       {
481         for( Iterator varIt = R0_1.parents().iterator(); varIt.hasNext(); ) {
482             final TypeVariable var = (TypeVariable) varIt.next();
483         
484         if(var.type() == null && var.approx() == ClassHierarchy.v().R0_1)
485           {
486             if(DEBUG)
487               {
488             G.v().out.println("*** R->BOOLEAN *** " + var);
489               }
490             var.union(BOOLEAN);
491             modified = true;
492           }
493           }
494       }
495       }
496   }
497
498   private void assign_types_1() throws TypeException
499   {
500     for( Iterator localIt = stmtBody.getLocals().iterator(); localIt.hasNext(); ) {
501         final Local local = (Local) localIt.next();
502
503     if(local.getType() instanceof IntegerType)
504       {
505         TypeVariable var = typeVariable(local);
506         
507         if(var.type() == null || var.type().type() == null)
508           {
509         TypeVariable.error("Type Error(21): Variable without type");
510           }
511         else
512           {
513         local.setType(var.type().type());
514           }
515         
516         if(DEBUG)
517           {
518         if((var != null) &&
519            (var.approx() != null) &&
520            (var.approx().type() != null) &&
521            (local != null) &&
522            (local.getType() != null) &&
523            !local.getType().equals(var.approx().type()))
524           {
525             G.v().out.println("local: " + local + ", type: " + local.getType() + ", approx: " + var.approx().type());
526           }
527           }
528       }
529       }
530   }
531   
532   private void assign_types_2() throws TypeException
533   {
534     for( Iterator localIt = stmtBody.getLocals().iterator(); localIt.hasNext(); ) {
535         final Local local = (Local) localIt.next();
536
537     if(local.getType() instanceof IntegerType)
538       {
539         TypeVariable var = typeVariable(local);
540         
541         if(var.inv_approx() != null && var.inv_approx().type() != null)
542           {
543         local.setType(var.inv_approx().type());
544           }
545         else if(var.approx().type() != null)
546           {
547         local.setType(var.approx().type());
548           }
549         else if(var.approx() == ClassHierarchy.v().R0_1)
550           {
551         local.setType(BooleanType.v());
552           }
553         else if(var.approx() == ClassHierarchy.v().R0_127)
554           {
555         local.setType(ByteType.v());
556           }
557         else
558           {
559         local.setType(ShortType.v());
560           }
561       }
562       }
563   }
564
565   private void check_constraints() throws TypeException
566   {
567     ConstraintChecker checker = new ConstraintChecker(this, false);
568     StringBuffer JavaDoc s = null;
569
570     if(DEBUG)
571       {
572     s = new StringBuffer JavaDoc("Checking:\n");
573       }
574
575     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
576
577         final Stmt stmt = (Stmt) stmtIt.next();
578     if(DEBUG)
579       {
580         s.append(" " + stmt + "\n");
581       }
582     try
583       {
584         checker.check(stmt, stmtBody);
585       }
586     catch(TypeException e)
587       {
588         if(DEBUG)
589           {
590         G.v().out.println(s);
591           }
592         throw e;
593       }
594       }
595   }
596
597   private void check_and_fix_constraints() throws TypeException
598   {
599     ConstraintChecker checker = new ConstraintChecker(this, true);
600     StringBuffer JavaDoc s = null;
601     PatchingChain units = stmtBody.getUnits();
602     Stmt[] stmts = new Stmt[units.size()];
603     units.toArray(stmts);
604
605     if(DEBUG)
606       {
607     s = new StringBuffer JavaDoc("Checking:\n");
608       }
609
610     for(int i = 0; i < stmts.length; i++)
611       {
612     Stmt stmt = stmts[i];
613
614     if(DEBUG)
615       {
616         s.append(" " + stmt + "\n");
617       }
618     try
619       {
620         checker.check(stmt, stmtBody);
621       }
622     catch(TypeException e)
623       {
624         if(DEBUG)
625           {
626         G.v().out.println(s);
627           }
628         throw e;
629       }
630       }
631   }
632
633   private void compute_approximate_types() throws TypeException
634   {
635     TreeSet workList = new TreeSet();
636
637     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
638
639         final TypeVariable var = (TypeVariable) varIt.next();
640
641     if(var.type() != null)
642       {
643         workList.add(var);
644       }
645       }
646
647     TypeVariable.computeApprox(workList);
648
649     workList = new TreeSet();
650
651     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
652
653         final TypeVariable var = (TypeVariable) varIt.next();
654     
655     if(var.type() != null)
656       {
657         workList.add(var);
658       }
659       }
660
661     TypeVariable.computeInvApprox(workList);
662
663     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
664
665         final TypeVariable var = (TypeVariable) varIt.next();
666
667     if (var.approx() == null)
668       {
669         var.union(INT);
670       }
671       }
672   }
673   
674   private void compute_solved()
675   {
676     Set unsolved_set = new TreeSet();
677     Set solved_set = new TreeSet();
678     
679     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
680     
681         final TypeVariable var = (TypeVariable) varIt.next();
682     
683     if(var.type() == null)
684       {
685         unsolved_set.add(var);
686       }
687     else
688       {
689         solved_set.add(var);
690       }
691       }
692     
693     solved = new LinkedList(solved_set);
694     unsolved = new LinkedList(unsolved_set);
695   }
696
697   private void refresh_solved() throws TypeException
698   {
699     Set unsolved_set = new TreeSet();
700     Set solved_set = new TreeSet(solved);
701     
702     for( Iterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
703     
704         final TypeVariable var = (TypeVariable) varIt.next();
705     
706     if(var.type() == null)
707       {
708         unsolved_set.add(var);
709       }
710     else
711       {
712         solved_set.add(var);
713       }
714       }
715     
716     solved = new LinkedList(solved_set);
717     unsolved = new LinkedList(unsolved_set);
718   }
719 }
720
Popular Tags