KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > typing > TypeResolverBV


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;
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 TypeResolverBV
41 {
42   /** Reference to the class hierarchy **/
43   private ClassHierarchy hierarchy;
44
45   /** All type variable instances **/
46   private final List typeVariableList = new ArrayList();
47   private BitVector invalidIds = new BitVector();
48
49   /** Hashtable: [TypeNode or Local] -> TypeVariableBV **/
50   private final Map typeVariableMap = new HashMap();
51
52   private final JimpleBody stmtBody;
53
54   final TypeNode NULL;
55   private final TypeNode OBJECT;
56
57   private static final boolean DEBUG = false;
58
59   // categories for type variables (solved = hard, unsolved = soft)
60
private BitVector unsolved;
61   private BitVector solved;
62
63   // parent categories for unsolved type variables
64
private BitVector single_soft_parent;
65   private BitVector single_hard_parent;
66   private BitVector multiple_parents;
67
68   // child categories for unsolved type variables
69
private BitVector single_child_not_null;
70   private BitVector single_null_child;
71   private BitVector multiple_children;
72
73   public ClassHierarchy hierarchy()
74   {
75     return hierarchy;
76   }
77
78   public TypeNode typeNode(Type type)
79   {
80     return hierarchy.typeNode(type);
81   }
82
83   /** Get type variable for the given local. **/
84   TypeVariableBV typeVariable(Local local)
85   {
86     TypeVariableBV result = (TypeVariableBV) typeVariableMap.get(local);
87
88     if(result == null)
89       {
90     int id = typeVariableList.size();
91     typeVariableList.add(null);
92
93     result = new TypeVariableBV(id, this);
94
95     typeVariableList.set(id, result);
96     typeVariableMap.put(local, result);
97     
98     if(DEBUG)
99       {
100         G.v().out.println("[LOCAL VARIABLE \"" + local + "\" -> " + id + "]");
101       }
102       }
103     
104     return result;
105   }
106
107   /** Get type variable for the given type node. **/
108   public TypeVariableBV typeVariable(TypeNode typeNode)
109   {
110     TypeVariableBV result = (TypeVariableBV) typeVariableMap.get(typeNode);
111
112     if(result == null)
113       {
114     int id = typeVariableList.size();
115     typeVariableList.add(null);
116
117     result = new TypeVariableBV(id, this, typeNode);
118
119     typeVariableList.set(id, result);
120     typeVariableMap.put(typeNode, result);
121       }
122
123     return result;
124   }
125
126   /** Get type variable for the given soot class. **/
127   public TypeVariableBV typeVariable(SootClass sootClass)
128   {
129     return typeVariable(hierarchy.typeNode(sootClass.getType()));
130   }
131
132   /** Get type variable for the given type. **/
133   public TypeVariableBV typeVariable(Type type)
134   {
135     return typeVariable(hierarchy.typeNode(type));
136   }
137
138   /** Get new type variable **/
139   public TypeVariableBV typeVariable()
140   {
141     int id = typeVariableList.size();
142     typeVariableList.add(null);
143     
144     TypeVariableBV result = new TypeVariableBV(id, this);
145     
146     typeVariableList.set(id, result);
147     
148     return result;
149   }
150
151   private TypeResolverBV(JimpleBody stmtBody, Scene scene)
152   {
153     this.stmtBody = stmtBody;
154     hierarchy = ClassHierarchy.classHierarchy(scene);
155
156     OBJECT = hierarchy.OBJECT;
157     NULL = hierarchy.NULL;
158     typeVariable(OBJECT);
159     typeVariable(NULL);
160     
161     // hack for J2ME library, reported by Stephen Cheng
162
if (!G.v().isJ2ME) {
163       typeVariable(hierarchy.CLONEABLE);
164       typeVariable(hierarchy.SERIALIZABLE);
165     }
166   }
167
168   public static void resolve(JimpleBody stmtBody, Scene scene)
169   {
170     if(DEBUG)
171       {
172     G.v().out.println(stmtBody.getMethod());
173       }
174
175     try
176     {
177       TypeResolverBV resolver = new TypeResolverBV(stmtBody, scene);
178       resolver.resolve_step_1();
179     }
180   catch(TypeException e1)
181     {
182       if(DEBUG)
183         {
184           e1.printStackTrace();
185           G.v().out.println("Step 1 Exception-->" + e1.getMessage());
186         }
187     
188       try
189         {
190           TypeResolverBV resolver = new TypeResolverBV(stmtBody, scene);
191           resolver.resolve_step_2();
192         }
193       catch(TypeException e2)
194         {
195           if(DEBUG)
196             {
197           e2.printStackTrace();
198           G.v().out.println("Step 2 Exception-->" + e2.getMessage());
199             }
200           
201           try
202             {
203               TypeResolverBV resolver = new TypeResolverBV(stmtBody, scene);
204               resolver.resolve_step_3();
205             }
206           catch(TypeException e3)
207             {
208               StringWriter st = new StringWriter();
209               PrintWriter pw = new PrintWriter(st);
210               e3.printStackTrace(pw);
211               pw.close();
212               throw new RuntimeException JavaDoc(st.toString());
213             }
214         }
215     }
216     soot.jimple.toolkits.typing.integer.TypeResolver.resolve(stmtBody);
217   }
218   
219   private void debug_vars(String JavaDoc message)
220   {
221     if(DEBUG)
222       {
223     int count = 0;
224     G.v().out.println("**** START:" + message);
225     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
226         final TypeVariableBV var = (TypeVariableBV) varIt.next();
227         G.v().out.println(count++ + " " + var);
228       }
229     G.v().out.println("**** END:" + message);
230       }
231   }
232
233   private void debug_body()
234   {
235     if(DEBUG)
236       {
237     G.v().out.println("-- Body Start --");
238     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
239         final Stmt stmt = (Stmt) stmtIt.next();
240         G.v().out.println(stmt);
241       }
242     G.v().out.println("-- Body End --");
243       }
244   }
245
246   private void resolve_step_1() throws TypeException
247   {
248     // remove_spurious_locals();
249

250     collect_constraints_1_2();
251     debug_vars("constraints");
252
253     compute_array_depth();
254     propagate_array_constraints();
255     debug_vars("arrays");
256
257     merge_primitive_types();
258     debug_vars("primitive");
259
260     merge_connected_components();
261     debug_vars("components");
262
263     remove_transitive_constraints();
264     debug_vars("transitive");
265
266     merge_single_constraints();
267     debug_vars("single");
268
269     assign_types_1_2();
270     debug_vars("assign");
271
272     check_constraints();
273   }
274
275   private void resolve_step_2() throws TypeException
276   {
277     debug_body();
278     split_new();
279     debug_body();
280
281     collect_constraints_1_2();
282     debug_vars("constraints");
283
284     compute_array_depth();
285     propagate_array_constraints();
286     debug_vars("arrays");
287
288     merge_primitive_types();
289     debug_vars("primitive");
290
291     merge_connected_components();
292     debug_vars("components");
293
294     remove_transitive_constraints();
295     debug_vars("transitive");
296
297     merge_single_constraints();
298     debug_vars("single");
299
300     assign_types_1_2();
301     debug_vars("assign");
302
303     check_constraints();
304   }
305
306   private void resolve_step_3() throws TypeException
307   {
308     collect_constraints_3();
309     compute_approximate_types();
310     assign_types_3();
311     check_and_fix_constraints();
312   }
313
314   private void collect_constraints_1_2()
315   {
316     ConstraintCollectorBV collector = new ConstraintCollectorBV(this, true);
317
318     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
319
320         final Stmt stmt = (Stmt) stmtIt.next();
321     if(DEBUG)
322       {
323         G.v().out.print("stmt: ");
324       }
325     collector.collect(stmt, stmtBody);
326     if(DEBUG)
327       {
328         G.v().out.println(stmt);
329       }
330       }
331   }
332
333   private void collect_constraints_3()
334   {
335     ConstraintCollectorBV collector = new ConstraintCollectorBV(this, false);
336
337     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
338
339         final Stmt stmt = (Stmt) stmtIt.next();
340     if(DEBUG)
341       {
342         G.v().out.print("stmt: ");
343       }
344     collector.collect(stmt, stmtBody);
345     if(DEBUG)
346       {
347         G.v().out.println(stmt);
348       }
349       }
350   }
351
352   private void compute_array_depth() throws TypeException
353   {
354     compute_approximate_types();
355
356     TypeVariableBV[] vars = new TypeVariableBV[typeVariableList.size()];
357     vars = (TypeVariableBV[]) typeVariableList.toArray(vars);
358
359     for(int i = 0; i < vars.length; i++)
360       {
361     vars[i].fixDepth();
362       }
363   }
364
365   private void propagate_array_constraints()
366   {
367     // find max depth
368
int max = 0;
369     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
370         final TypeVariableBV var = (TypeVariableBV) varIt.next();
371     int depth = var.depth();
372
373     if(depth > max)
374       {
375         max = depth;
376       }
377       }
378
379     if(max > 1) {
380       // hack for J2ME library, reported by Stephen Cheng
381
if (!G.v().isJ2ME) {
382     typeVariable(ArrayType.v(RefType.v("java.lang.Cloneable"), max - 1));
383     typeVariable(ArrayType.v(RefType.v("java.io.Serializable"), max - 1));
384       }
385     }
386
387     // create lists for each array depth
388
LinkedList[] lists = new LinkedList[max + 1];
389     for(int i = 0; i <= max; i++)
390       {
391     lists[i] = new LinkedList();
392       }
393
394     // initialize lists
395
for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
396         final TypeVariableBV var = (TypeVariableBV) varIt.next();
397     int depth = var.depth();
398     
399     lists[depth].add(var);
400       }
401
402     // propagate constraints, starting with highest depth
403
for(int i = max; i >= 0; i--)
404       {
405     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
406         final TypeVariableBV var = (TypeVariableBV) varIt.next();
407
408         var.propagate();
409       }
410       }
411   }
412
413   private void merge_primitive_types() throws TypeException
414   {
415     // merge primitive types with all parents/children
416
compute_solved();
417
418     BitSetIterator varIt = solved.iterator();
419     while( varIt.hasNext() ) {
420         TypeVariableBV var = typeVariableForId(varIt.next());
421
422     if(var.type().type() instanceof IntType ||
423        var.type().type() instanceof LongType ||
424        var.type().type() instanceof FloatType ||
425        var.type().type() instanceof DoubleType)
426       {
427         BitVector parents;
428         BitVector children;
429         boolean finished;
430
431         do
432           {
433         finished = true;
434
435         parents = var.parents();
436         if(parents.length() != 0)
437           {
438             finished = false;
439             for(BitSetIterator j = parents.iterator(); j.hasNext(); )
440               {
441             if(DEBUG)
442               {
443                 G.v().out.print(".");
444               }
445     
446             TypeVariableBV parent = typeVariableForId(j.next());
447
448             var = var.union(parent);
449               }
450           }
451         
452         children = var.children();
453         if(children.length() != 0)
454           {
455             finished = false;
456             for(BitSetIterator j = children.iterator(); j.hasNext(); )
457               {
458             if(DEBUG)
459               {
460                 G.v().out.print(".");
461               }
462     
463             TypeVariableBV child = typeVariableForId(j.next());
464
465             var = var.union(child);
466               }
467           }
468           }
469         while(!finished);
470       }
471       }
472   }
473
474   private void merge_connected_components() throws TypeException
475   {
476     refresh_solved();
477     BitVector list = new BitVector();
478     list.or(solved);
479     list.or(unsolved);
480     
481     new StronglyConnectedComponentsBV(list, this);
482   }
483   
484   private void remove_transitive_constraints() throws TypeException
485   {
486     refresh_solved();
487     BitVector list = new BitVector();
488     list.or(solved);
489     list.or(unsolved);
490
491     for( BitSetIterator varIt = list.iterator(); varIt.hasNext(); ) {
492
493         final TypeVariableBV var = typeVariableForId(varIt.next());
494     
495     var.removeIndirectRelations();
496       }
497   }
498
499   private void merge_single_constraints() throws TypeException
500   {
501     boolean finished = false;
502     boolean modified = false;
503     while(true)
504       {
505     categorize();
506     
507     if(single_child_not_null.length() != 0)
508       {
509         finished = false;
510         modified = true;
511         
512             BitSetIterator i = single_child_not_null.iterator();
513             while( i.hasNext() )
514               {
515                 TypeVariableBV var = typeVariableForId(i.next());
516
517                 if(single_child_not_null.get(var.id()))
518           {
519             // PA: Potential difference to old algorithm - using the smallest element
520
// in the list rather than children().get(0);
521
TypeVariableBV child = typeVariableForId(var.children().iterator().next());
522         
523                     var = var.union(child);
524           }
525               }
526       }
527
528     if(finished)
529       {
530         if(single_soft_parent.length() != 0)
531           {
532         finished = false;
533         modified = true;
534         
535                 BitSetIterator i = single_soft_parent.iterator();
536                 while( i.hasNext() )
537                   {
538                     TypeVariableBV var = typeVariableForId(i.next());
539             
540             if(single_soft_parent.get(var.id()))
541               {
542                 // PA: See above.
543
TypeVariableBV parent = typeVariableForId(var.parents().iterator().next());
544             
545                 var = var.union(parent);
546               }
547                   }
548           }
549         
550         if(single_hard_parent.length() != 0)
551           {
552         finished = false;
553         modified = true;
554         
555                 BitSetIterator i = single_hard_parent.iterator();
556                 while( i.hasNext() )
557                   {
558                     TypeVariableBV var = typeVariableForId(i.next());
559             
560             if(single_hard_parent.get(var.id()))
561               {
562                 // PA: See above
563
TypeVariableBV parent = typeVariableForId(var.parents().iterator().next());
564             
565             debug_vars("union single parent\n " + var + "\n " + parent);
566             var = var.union(parent);
567               }
568           }
569           }
570
571         if(single_null_child.length() != 0)
572           {
573         finished = false;
574         modified = true;
575         
576                 BitSetIterator i = single_null_child.iterator();
577                 while( i.hasNext() )
578                   {
579                     TypeVariableBV var = typeVariableForId(i.next());
580             
581             if(single_null_child.get(var.id()))
582               {
583                 // PA: See above
584
TypeVariableBV child = typeVariableForId(var.children().iterator().next());
585             
586             var = var.union(child);
587               }
588           }
589           }
590         
591         if(finished)
592           {
593         break;
594           }
595         
596         continue;
597       }
598     
599     if(modified)
600       {
601         modified = false;
602         continue;
603       }
604
605     finished = true;
606     
607       multiple_children:
608     for( BitSetIterator varIt = multiple_children.iterator(); varIt.hasNext(); )
609           {
610         final TypeVariableBV var = typeVariableForId(varIt.next());
611         TypeNode lca = null;
612         BitVector children_to_remove = new BitVector();
613         
614         for( BitSetIterator childIt = var.children().iterator(); childIt.hasNext(); )
615               {
616         
617             final TypeVariableBV child = typeVariableForId(childIt.next());
618         TypeNode type = child.type();
619
620         if(type != null && type.isNull())
621           {
622             var.removeChild(child);
623           }
624         else if(type != null && type.isClass())
625           {
626             children_to_remove.set(child.id());
627             
628             if(lca == null)
629               {
630             lca = type;
631               }
632             else
633               {
634             lca = lca.lcaIfUnique(type);
635
636             if(lca == null)
637               {
638                 if(DEBUG)
639                   {
640                 G.v().out.println
641                   ("==++==" +
642                    stmtBody.getMethod().getDeclaringClass().getName() + "." +
643                    stmtBody.getMethod().getName());
644                   }
645                 
646                 continue multiple_children;
647               }
648               }
649           }
650           }
651         
652         if(lca != null)
653           {
654         for( BitSetIterator childIt = children_to_remove.iterator(); childIt.hasNext(); ) {
655             final TypeVariableBV child = typeVariableForId(childIt.next());
656             var.removeChild(child);
657           }
658
659         var.addChild(typeVariable(lca));
660           }
661       }
662     
663     for( BitSetIterator varIt = multiple_parents.iterator(); varIt.hasNext(); ) {
664     
665         final TypeVariableBV var = typeVariableForId(varIt.next());
666         LinkedList hp = new LinkedList(); // hard parents
667

668         for( BitSetIterator parentIt = var.parents().iterator(); parentIt.hasNext(); ) {
669         
670             final TypeVariableBV parent = typeVariableForId(parentIt.next());
671         TypeNode type = parent.type();
672         
673         if(type != null)
674           {
675                     Iterator k = hp.iterator();
676                     while( k.hasNext() ) {
677                         TypeVariableBV otherparent = (TypeVariableBV) k.next();
678             TypeNode othertype = otherparent.type();
679             
680             if(type.hasDescendant(othertype))
681               {
682                 var.removeParent(parent);
683                 type = null;
684                 break;
685               }
686             
687             if(type.hasAncestor(othertype))
688               {
689                 var.removeParent(otherparent);
690                 k.remove();
691               }
692               }
693             
694             if(type != null)
695               {
696             hp.add(parent);
697               }
698           }
699           }
700       }
701       }
702   }
703
704   private void assign_types_1_2() throws TypeException
705   {
706     for( Iterator localIt = stmtBody.getLocals().iterator(); localIt.hasNext(); ) {
707         final Local local = (Local) localIt.next();
708     TypeVariableBV var = typeVariable(local);
709     
710     if(var == null)
711       {
712         local.setType(RefType.v("java.lang.Object"));
713       }
714     else if (var.depth() == 0)
715       {
716         if(var.type() == null)
717           {
718         TypeVariableBV.error("Type Error(5): Variable without type");
719           }
720         else
721           {
722         local.setType(var.type().type());
723           }
724       }
725     else
726       {
727         TypeVariableBV element = var.element();
728         
729         for(int j = 1; j < var.depth(); j++)
730           {
731         element = element.element();
732           }
733
734         if(element.type() == null)
735           {
736         TypeVariableBV.error("Type Error(6): Array variable without base type");
737           }
738         else if(element.type().type() instanceof NullType)
739           {
740         local.setType(NullType.v());
741           }
742         else
743           {
744         Type t = element.type().type();
745         if(t instanceof IntType)
746           {
747             local.setType(var.approx().type());
748           }
749         else
750           {
751             local.setType(ArrayType.v(t, var.depth()));
752           }
753           }
754       }
755     
756     if(DEBUG)
757       {
758         if((var != null) &&
759            (var.approx() != null) &&
760            (var.approx().type() != null) &&
761            (local != null) &&
762            (local.getType() != null) &&
763            !local.getType().equals(var.approx().type()))
764           {
765         G.v().out.println("local: " + local + ", type: " + local.getType() + ", approx: " + var.approx().type());
766           }
767       }
768       }
769   }
770
771   private void assign_types_3() throws TypeException
772   {
773     for( Iterator localIt = stmtBody.getLocals().iterator(); localIt.hasNext(); ) {
774         final Local local = (Local) localIt.next();
775     TypeVariableBV var = typeVariable(local);
776     
777     if(var == null ||
778        var.approx() == null ||
779        var.approx().type() == null)
780       {
781         local.setType(RefType.v("java.lang.Object"));
782       }
783     else
784       {
785         local.setType(var.approx().type());
786       }
787       }
788   }
789
790   private void check_constraints() throws TypeException
791   {
792     ConstraintCheckerBV checker = new ConstraintCheckerBV(this, false);
793     StringBuffer JavaDoc s = null;
794
795     if(DEBUG)
796       {
797     s = new StringBuffer JavaDoc("Checking:\n");
798       }
799
800     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
801
802         final Stmt stmt = (Stmt) stmtIt.next();
803     if(DEBUG)
804       {
805         s.append(" " + stmt + "\n");
806       }
807     try
808       {
809         checker.check(stmt, stmtBody);
810       }
811     catch(TypeException e)
812       {
813         if(DEBUG)
814           {
815         G.v().out.println(s);
816           }
817         throw e;
818       }
819       }
820   }
821
822   private void check_and_fix_constraints() throws TypeException
823   {
824     ConstraintCheckerBV checker = new ConstraintCheckerBV(this, true);
825     StringBuffer JavaDoc s = null;
826     PatchingChain units = stmtBody.getUnits();
827     Stmt[] stmts = new Stmt[units.size()];
828     units.toArray(stmts);
829
830     if(DEBUG)
831       {
832     s = new StringBuffer JavaDoc("Checking:\n");
833       }
834
835     for(int i = 0; i < stmts.length; i++)
836       {
837     Stmt stmt = stmts[i];
838
839     if(DEBUG)
840       {
841         s.append(" " + stmt + "\n");
842       }
843     try
844       {
845         checker.check(stmt, stmtBody);
846       }
847     catch(TypeException e)
848       {
849         if(DEBUG)
850           {
851         G.v().out.println(s);
852           }
853         throw e;
854       }
855       }
856   }
857
858   private void compute_approximate_types() throws TypeException
859   {
860     TreeSet workList = new TreeSet();
861
862     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
863
864         final TypeVariableBV var = (TypeVariableBV) varIt.next();
865
866     if(var.type() != null)
867       {
868         workList.add(var);
869       }
870       }
871
872     TypeVariableBV.computeApprox(workList);
873
874     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
875
876         final TypeVariableBV var = (TypeVariableBV) varIt.next();
877
878     if(var.approx() == NULL)
879       {
880         var.union(typeVariable(NULL));
881       }
882     else if (var.approx() == null)
883       {
884         var.union(typeVariable(NULL));
885       }
886       }
887   }
888   
889   private void compute_solved()
890   {
891     unsolved = new BitVector();
892     solved = new BitVector();
893     
894     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
895     
896         final TypeVariableBV var = (TypeVariableBV) varIt.next();
897     
898     if(var.depth() == 0)
899       {
900         if(var.type() == null)
901           {
902         unsolved.set(var.id());
903           }
904         else
905           {
906         solved.set(var.id());
907           }
908       }
909       }
910   }
911
912   private void refresh_solved() throws TypeException
913   {
914     unsolved = new BitVector();
915     // solved stays the same
916

917     for( BitSetIterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
918     
919         final TypeVariableBV var = typeVariableForId(varIt.next());
920     
921     if(var.depth() == 0)
922       {
923         if(var.type() == null)
924           {
925         unsolved.set(var.id());
926           }
927         else
928           {
929         solved.set(var.id());
930           }
931       }
932       }
933
934     // validate();
935
}
936
937   private void categorize() throws TypeException
938   {
939     refresh_solved();
940    
941     single_soft_parent = new BitVector();
942     single_hard_parent = new BitVector();
943     multiple_parents = new BitVector();
944     single_child_not_null = new BitVector();
945     single_null_child = new BitVector();
946     multiple_children = new BitVector();
947     
948     for(BitSetIterator i = unsolved.iterator(); i .hasNext(); )
949       {
950     TypeVariableBV var = typeVariableForId(i.next());
951     
952     // parent category
953
{
954       BitVector parents = var.parents();
955       int size = parents.length();
956       
957       if(size == 0)
958         {
959           var.addParent(typeVariable(OBJECT));
960           single_soft_parent.set(var.id());
961         }
962       else if(size == 1)
963         {
964           TypeVariableBV parent = typeVariableForId(parents.iterator().next());
965           
966           if(parent.type() == null)
967         {
968           single_soft_parent.set(var.id());
969         }
970           else
971         {
972           single_hard_parent.set(var.id());
973         }
974         }
975       else
976         {
977           multiple_parents.set(var.id());
978         }
979     }
980     
981     // child category
982
{
983       BitVector children = var.children();
984       int size = children.size();
985       
986       if(size == 0)
987         {
988           var.addChild(typeVariable(NULL));
989           single_null_child.set(var.id());
990         }
991       else if(size == 1)
992         {
993           TypeVariableBV child = typeVariableForId(children.iterator().next());
994           
995           if(child.type() == NULL)
996         {
997           single_null_child.set(var.id());
998         }
999           else
1000        {
1001          single_child_not_null.set(var.id());
1002        }
1003        }
1004      else
1005        {
1006          multiple_children.set(var.id());
1007        }
1008    }
1009      }
1010  }
1011
1012  private void validate() throws TypeException
1013  {
1014    for( BitSetIterator varIt = solved.iterator(); varIt.hasNext(); ) {
1015        final TypeVariableBV var = typeVariableForId(varIt.next());
1016    
1017    try
1018      {
1019        var.validate();
1020      }
1021    catch(TypeException e)
1022      {
1023        debug_vars("Error while validating");
1024        throw(e);
1025      }
1026      }
1027  }
1028
1029  /*
1030  private void remove_spurious_locals()
1031  {
1032    boolean repeat;
1033
1034    do
1035      {
1036    ExceptionalUnitGraph graph = new ExceptionalUnitGraph(stmtBody);
1037    SimpleLocalDefs defs = new SimpleLocalDefs(graph);
1038    SimpleLocalUses uses = new SimpleLocalUses(graph, defs);
1039    PatchingChain units = stmtBody.getUnits();
1040    Stmt[] stmts = new Stmt[units.size()];
1041    HashSet deleted = new HashSet();
1042
1043    repeat = false;
1044    units.toArray(stmts);
1045    
1046    for(int i = 0; i < stmts.length; i++)
1047      {
1048        Stmt stmt = stmts[i];
1049        
1050        if(stmt instanceof AssignStmt)
1051          {
1052        AssignStmt assign1 = (AssignStmt) stmt;
1053        
1054        if(assign1.getLeftOp() instanceof Local)
1055          {
1056            List uselist = uses.getUsesOf(assign1);
1057            
1058            if(uselist.size() == 1)
1059              {
1060            UnitValueBoxPair pair = (UnitValueBoxPair) uselist.get(0);
1061            
1062            List deflist = defs.getDefsOfAt((Local) pair.getValueBox().getValue(), pair.getUnit());
1063            
1064            if(deflist.size() == 1)
1065              {
1066                if(pair.getValueBox().canContainValue(assign1.getRightOp()))
1067                  {
1068                // This is definitely a spurious local!
1069
1070                // Hmm.. use is in a deleted statement. Must wait till next iteration.
1071                if(deleted.contains(pair.getUnit()))
1072                  {
1073                    repeat = true;
1074                    continue;
1075                  }
1076                
1077                pair.getValueBox().setValue(assign1.getRightOp());
1078                deleted.add(assign1);
1079                units.remove(assign1);
1080                stmtBody.getLocals().remove(assign1.getLeftOp());
1081                
1082                  }
1083              }
1084              }
1085          }
1086          }
1087      }
1088      }
1089    while(repeat);
1090  }
1091  */

1092
1093  private void split_new()
1094  {
1095    ExceptionalUnitGraph graph = new ExceptionalUnitGraph(stmtBody);
1096    LocalDefs defs = new SmartLocalDefs(graph, new SimpleLiveLocals(graph));
1097    PatchingChain units = stmtBody.getUnits();
1098    Stmt[] stmts = new Stmt[units.size()];
1099
1100    units.toArray(stmts);
1101    
1102    for(int i = 0; i < stmts.length; i++)
1103      {
1104    Stmt stmt = stmts[i];
1105
1106    if(stmt instanceof InvokeStmt)
1107      {
1108        InvokeStmt invoke = (InvokeStmt) stmt;
1109        
1110        if(invoke.getInvokeExpr() instanceof SpecialInvokeExpr)
1111          {
1112        SpecialInvokeExpr special = (SpecialInvokeExpr) invoke.getInvokeExpr();
1113        
1114        if(special.getMethodRef().name().equals("<init>"))
1115          {
1116            List deflist = defs.getDefsOfAt((Local) special.getBase(), invoke);
1117            
1118            while(deflist.size() == 1)
1119              {
1120            Stmt stmt2 = (Stmt) deflist.get(0);
1121            
1122            if(stmt2 instanceof AssignStmt)
1123              {
1124                AssignStmt assign = (AssignStmt) stmt2;
1125                
1126                if(assign.getRightOp() instanceof Local)
1127                  {
1128                deflist = defs.getDefsOfAt((Local) assign.getRightOp(), assign);
1129                continue;
1130                  }
1131                else if(assign.getRightOp() instanceof NewExpr)
1132                  {
1133                // We split the local.
1134
//G.v().out.println("split: [" + assign + "] and [" + stmt + "]");
1135
Local newlocal = Jimple.v().newLocal("tmp", null);
1136                stmtBody.getLocals().add(newlocal);
1137                
1138                special.setBase(newlocal);
1139                
1140                units.insertAfter(Jimple.v().newAssignStmt(assign.getLeftOp(), newlocal), assign);
1141                assign.setLeftOp(newlocal);
1142                  }
1143              }
1144            break;
1145              }
1146          }
1147          }
1148      }
1149      }
1150  }
1151  
1152  public TypeVariableBV typeVariableForId(int idx) {
1153      return (TypeVariableBV)typeVariableList.get(idx);
1154  }
1155  
1156  public BitVector invalidIds() {
1157      return invalidIds;
1158  }
1159  
1160  public void invalidateId(int id) {
1161      invalidIds.set(id);
1162  }
1163}
1164
Popular Tags