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;
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    /** Reference to the class hierarchy **/
43    private ClassHierarchy hierarchy;
44  
45    /** All type variable instances **/
46    private final List typeVariableList = new ArrayList();
47  
48    /** Hashtable: [TypeNode or Local] -> TypeVariable **/
49    private final Map typeVariableMap = new HashMap();
50  
51    private final JimpleBody stmtBody;
52  
53    final TypeNode NULL;
54    private final TypeNode OBJECT;
55  
56    private static final boolean DEBUG = false;
57  
58    // categories for type variables (solved = hard, unsolved = soft)
59    private List unsolved;
60    private List solved;
61  
62    // parent categories for unsolved type variables
63    private List single_soft_parent;
64    private List single_hard_parent;
65    private List multiple_parents;
66  
67    // child categories for unsolved type variables
68    private List single_child_not_null;
69    private List single_null_child;
70    private List multiple_children;
71  
72    public ClassHierarchy hierarchy()
73    {
74      return hierarchy;
75    }
76  
77    public TypeNode typeNode(Type type)
78    {
79      return hierarchy.typeNode(type);
80    }
81  
82    /** Get type variable for the given local. **/
83    TypeVariable typeVariable(Local local)
84    {
85      TypeVariable result = (TypeVariable) typeVariableMap.get(local);
86  
87      if(result == null)
88        {
89      int id = typeVariableList.size();
90      typeVariableList.add(null);
91  
92      result = new TypeVariable(id, this);
93  
94      typeVariableList.set(id, result);
95      typeVariableMap.put(local, result);
96      
97      if(DEBUG)
98        {
99          G.v().out.println("[LOCAL VARIABLE \"" + local + "\" -> " + id + "]");
100       }
101       }
102     
103     return result;
104   }
105 
106   /** Get type variable for the given type node. **/
107   public TypeVariable typeVariable(TypeNode typeNode)
108   {
109     TypeVariable result = (TypeVariable) typeVariableMap.get(typeNode);
110 
111     if(result == null)
112       {
113     int id = typeVariableList.size();
114     typeVariableList.add(null);
115 
116     result = new TypeVariable(id, this, typeNode);
117 
118     typeVariableList.set(id, result);
119     typeVariableMap.put(typeNode, result);
120       }
121 
122     return result;
123   }
124 
125   /** Get type variable for the given soot class. **/
126   public TypeVariable typeVariable(SootClass sootClass)
127   {
128     return typeVariable(hierarchy.typeNode(sootClass.getType()));
129   }
130 
131   /** Get type variable for the given type. **/
132   public TypeVariable typeVariable(Type type)
133   {
134     return typeVariable(hierarchy.typeNode(type));
135   }
136 
137   /** Get new type variable **/
138   public TypeVariable typeVariable()
139   {
140     int id = typeVariableList.size();
141     typeVariableList.add(null);
142     
143     TypeVariable result = new TypeVariable(id, this);
144     
145     typeVariableList.set(id, result);
146     
147     return result;
148   }
149 
150   private TypeResolver(JimpleBody stmtBody, Scene scene)
151   {
152     this.stmtBody = stmtBody;
153     hierarchy = ClassHierarchy.classHierarchy(scene);
154 
155     OBJECT = hierarchy.OBJECT;
156     NULL = hierarchy.NULL;
157     typeVariable(OBJECT);
158     typeVariable(NULL);
159     
160     // hack for J2ME library, reported by Stephen Cheng 
161     if (!G.v().isJ2ME) {
162       typeVariable(hierarchy.CLONEABLE);
163       typeVariable(hierarchy.SERIALIZABLE);
164     }
165   }
166 
167   public static void resolve(JimpleBody stmtBody, Scene scene)
168   {
169     if(DEBUG)
170       {
171     G.v().out.println(stmtBody.getMethod());
172       }
173 
174     // Disable bit-vector type assigner completely until it works correctly.
175     if(true || soot.options.Options.v().use_old_type_assigner()) {
176       try
177         {
178           TypeResolver resolver = new TypeResolver(stmtBody, scene);
179           resolver.resolve_step_1();
180         }
181       catch(TypeException e1)
182         {
183           if(DEBUG)
184             {
185               e1.printStackTrace();
186               G.v().out.println("Step 1 Exception-->" + e1.getMessage());
187             }
188         
189           try
190             {
191               TypeResolver resolver = new TypeResolver(stmtBody, scene);
192               resolver.resolve_step_2();
193             }
194           catch(TypeException e2)
195             {
196               if(DEBUG)
197                 {
198               e2.printStackTrace();
199               G.v().out.println("Step 2 Exception-->" + e2.getMessage());
200                 }
201               
202               try
203                 {
204                   TypeResolver resolver = new TypeResolver(stmtBody, scene);
205                   resolver.resolve_step_3();
206                 }
207               catch(TypeException e3)
208                 {
209                   StringWriter st = new StringWriter();
210                   PrintWriter pw = new PrintWriter(st);
211                   e3.printStackTrace(pw);
212                   pw.close();
213                   throw new RuntimeException  (st.toString());
214                 }
215             }
216         } 
217       soot.jimple.toolkits.typing.integer.TypeResolver.resolve(stmtBody);
218     }
219     else {
220         TypeResolverBV.resolve(stmtBody, scene);
221     }
222   }
223   
224   private void debug_vars(String   message)
225   {
226     if(DEBUG)
227       {
228     int count = 0;
229     G.v().out.println("**** START:" + message);
230     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
231         final TypeVariable var = (TypeVariable) varIt.next();
232         G.v().out.println(count++ + " " + var);
233       }
234     G.v().out.println("**** END:" + message);
235       }
236   }
237 
238   private void debug_body()
239   {
240     if(DEBUG)
241       {
242     G.v().out.println("-- Body Start --");
243     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
244         final Stmt stmt = (Stmt) stmtIt.next();
245         G.v().out.println(stmt);
246       }
247     G.v().out.println("-- Body End --");
248       }
249   }
250 
251   private void resolve_step_1() throws TypeException
252   {
253     //    remove_spurious_locals();
254 
255     collect_constraints_1_2();
256     debug_vars("constraints");
257 
258     compute_array_depth();
259     propagate_array_constraints();
260     debug_vars("arrays");
261 
262     merge_primitive_types();
263     debug_vars("primitive");
264 
265     merge_connected_components();
266     debug_vars("components");
267 
268     remove_transitive_constraints();
269     debug_vars("transitive");
270 
271     merge_single_constraints();
272     debug_vars("single");
273 
274     assign_types_1_2();
275     debug_vars("assign");
276 
277     check_constraints();
278   }
279 
280   private void resolve_step_2() throws TypeException
281   {
282     debug_body();
283     split_new();
284     debug_body();
285 
286     collect_constraints_1_2();
287     debug_vars("constraints");
288 
289     compute_array_depth();
290     propagate_array_constraints();
291     debug_vars("arrays");
292 
293     merge_primitive_types();
294     debug_vars("primitive");
295 
296     merge_connected_components();
297     debug_vars("components");
298 
299     remove_transitive_constraints();
300     debug_vars("transitive");
301 
302     merge_single_constraints();
303     debug_vars("single");
304 
305     assign_types_1_2();
306     debug_vars("assign");
307 
308     check_constraints();
309   }
310 
311   private void resolve_step_3() throws TypeException
312   {
313     collect_constraints_3();
314     compute_approximate_types();
315     assign_types_3();
316     check_and_fix_constraints();
317   }
318 
319   private void collect_constraints_1_2()
320   {
321     ConstraintCollector collector = new ConstraintCollector(this, true);
322 
323     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
324 
325         final Stmt stmt = (Stmt) stmtIt.next();
326     if(DEBUG)
327       {
328         G.v().out.print("stmt: ");
329       }
330     collector.collect(stmt, stmtBody);
331     if(DEBUG)
332       {
333         G.v().out.println(stmt);
334       }
335       }
336   }
337 
338   private void collect_constraints_3()
339   {
340     ConstraintCollector collector = new ConstraintCollector(this, false);
341 
342     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
343 
344         final Stmt stmt = (Stmt) stmtIt.next();
345     if(DEBUG)
346       {
347         G.v().out.print("stmt: ");
348       }
349     collector.collect(stmt, stmtBody);
350     if(DEBUG)
351       {
352         G.v().out.println(stmt);
353       }
354       }
355   }
356 
357   private void compute_array_depth() throws TypeException
358   {
359     compute_approximate_types();
360 
361     TypeVariable[] vars = new TypeVariable[typeVariableList.size()];
362     vars = (TypeVariable[]) typeVariableList.toArray(vars);
363 
364     for(int i = 0; i < vars.length; i++)
365       {
366     vars[i].fixDepth();
367       }
368   }
369 
370   private void propagate_array_constraints()
371   {
372     // find max depth
373     int max = 0;
374     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
375         final TypeVariable var = (TypeVariable) varIt.next();
376     int depth = var.depth();
377 
378     if(depth > max)
379       {
380         max = depth;
381       }
382       }
383 
384     if(max > 1) {
385       // hack for J2ME library, reported by Stephen Cheng 
386       if (!G.v().isJ2ME) {
387     typeVariable(ArrayType.v(RefType.v("java.lang.Cloneable"), max - 1));
388     typeVariable(ArrayType.v(RefType.v("java.io.Serializable"), max - 1));
389       }
390     }
391 
392     // create lists for each array depth
393     LinkedList[] lists = new LinkedList[max + 1];
394     for(int i = 0; i <= max; i++)
395       {
396     lists[i] = new LinkedList();
397       }
398 
399     // initialize lists
400     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
401         final TypeVariable var = (TypeVariable) varIt.next();
402     int depth = var.depth();
403     
404     lists[depth].add(var);
405       }
406 
407     // propagate constraints, starting with highest depth
408     for(int i = max; i >= 0; i--)
409       {
410     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
411         final TypeVariable var = (TypeVariable) varIt.next();
412 
413         var.propagate();
414       }
415       }
416   }
417 
418   private void merge_primitive_types() throws TypeException
419   {
420     // merge primitive types with all parents/children
421     compute_solved();
422 
423     Iterator varIt = solved.iterator();
424     while( varIt.hasNext() ) {
425         TypeVariable var = (TypeVariable) varIt.next();
426 
427     if(var.type().type() instanceof IntType ||
428        var.type().type() instanceof LongType ||
429        var.type().type() instanceof FloatType ||
430        var.type().type() instanceof DoubleType)
431       {
432         List parents;
433         List children;
434         boolean finished;
435 
436         do
437           {
438         finished = true;
439 
440         parents = var.parents();
441         if(parents.size() != 0)
442           {
443             finished = false;
444             for(Iterator j = parents.iterator(); j.hasNext(); )
445               {
446             if(DEBUG)
447               {
448                 G.v().out.print(".");
449               }
450     
451             TypeVariable parent = (TypeVariable) j.next();
452 
453             var = var.union(parent);
454               }
455           }
456         
457         children = var.children();
458         if(children.size() != 0)
459           {
460             finished = false;
461             for(Iterator j = children.iterator(); j.hasNext(); )
462               {
463             if(DEBUG)
464               {
465                 G.v().out.print(".");
466               }
467     
468             TypeVariable child = (TypeVariable) j.next();
469 
470             var = var.union(child);
471               }
472           }
473           }
474         while(!finished);
475       }
476       }
477   }
478 
479   private void merge_connected_components() throws TypeException
480   {
481     refresh_solved();
482     List list = new LinkedList();
483     list.addAll(solved);
484     list.addAll(unsolved);
485     
486     StronglyConnectedComponents.merge(list);
487   }
488   
489   private void remove_transitive_constraints() throws TypeException
490   {
491     refresh_solved();
492     List list = new LinkedList();
493     list.addAll(solved);
494     list.addAll(unsolved);
495 
496     for( Iterator varIt = list.iterator(); varIt.hasNext(); ) {
497 
498         final TypeVariable var = (TypeVariable) varIt.next();
499     
500     var.removeIndirectRelations();
501       }
502   }
503 
504   private void merge_single_constraints() throws TypeException
505   {
506     boolean finished = false;
507     boolean modified = false;
508     while(true)
509       {
510     categorize();
511     
512     if(single_child_not_null.size() != 0)
513       {
514         finished = false;
515         modified = true;
516         
517             Iterator i = single_child_not_null.iterator();
518             while( i.hasNext() ) {
519                 TypeVariable var = (TypeVariable) i.next();
520 
521         if(single_child_not_null.contains(var))
522           {
523             TypeVariable child = (TypeVariable) var.children().get(0);
524         
525             var = var.union(child);
526           }
527           }
528       }
529 
530     if(finished)
531       {
532         if(single_soft_parent.size() != 0)
533           {
534         finished = false;
535         modified = true;
536         
537                 Iterator i = single_soft_parent.iterator();
538                 while( i.hasNext() ) {
539                     TypeVariable var = (TypeVariable) i.next();
540             
541             if(single_soft_parent.contains(var))
542               {
543             TypeVariable parent = (TypeVariable) var.parents().get(0);
544             
545             var = var.union(parent);
546               }
547           }
548           }
549         
550         if(single_hard_parent.size() != 0)
551           {
552         finished = false;
553         modified = true;
554         
555                 Iterator i = single_hard_parent.iterator();
556                 while( i.hasNext() ) {
557                     TypeVariable var = (TypeVariable) i.next();
558             
559             if(single_hard_parent.contains(var))
560               {
561             TypeVariable parent = (TypeVariable) var.parents().get(0);
562             
563             debug_vars("union single parent\n " + var + "\n " + parent);
564             var = var.union(parent);
565               }
566           }
567           }
568 
569         if(single_null_child.size() != 0)
570           {
571         finished = false;
572         modified = true;
573         
574                 Iterator i = single_null_child.iterator();
575                 while( i.hasNext() ) {
576                     TypeVariable var = (TypeVariable) i.next();
577             
578             if(single_null_child.contains(var))
579               {
580             TypeVariable child = (TypeVariable) var.children().get(0);
581             
582             var = var.union(child);
583               }
584           }
585           }
586         
587         if(finished)
588           {
589         break;
590           }
591         
592         continue;
593       }
594     
595     if(modified)
596       {
597         modified = false;
598         continue;
599       }
600 
601     finished = true;
602     
603       multiple_children:
604     for( Iterator varIt = multiple_children.iterator(); varIt.hasNext(); ) {
605         final TypeVariable var = (TypeVariable) varIt.next();
606         TypeNode lca = null;
607         List children_to_remove = new LinkedList();
608         
609         var.fixChildren();
610         
611         for( Iterator childIt = var.children().iterator(); childIt.hasNext(); ) {
612         
613             final TypeVariable child = (TypeVariable) childIt.next();
614         TypeNode type = child.type();
615 
616         if(type != null && type.isNull())
617           {
618             var.removeChild(child);
619           }
620         else if(type != null && type.isClass())
621           {
622             children_to_remove.add(child);
623             
624             if(lca == null)
625               {
626             lca = type;
627               }
628             else
629               {
630             lca = lca.lcaIfUnique(type);
631 
632             if(lca == null)
633               {
634                 if(DEBUG)
635                   {
636                 G.v().out.println
637                   ("==++==" +
638                    stmtBody.getMethod().getDeclaringClass().getName() + "." + 
639                    stmtBody.getMethod().getName());
640                   }
641                 
642                 continue multiple_children;
643               }
644               }
645           }
646           }
647         
648         if(lca != null)
649           {
650         for( Iterator childIt = children_to_remove.iterator(); childIt.hasNext(); ) {
651             final TypeVariable child = (TypeVariable) childIt.next();
652             var.removeChild(child);
653           }
654 
655         var.addChild(typeVariable(lca));
656           }
657       }
658     
659     for( Iterator varIt = multiple_parents.iterator(); varIt.hasNext(); ) {
660     
661         final TypeVariable var = (TypeVariable) varIt.next();
662         LinkedList hp = new LinkedList(); // hard parents
663         
664         var.fixParents();
665         
666         for( Iterator parentIt = var.parents().iterator(); parentIt.hasNext(); ) {
667         
668             final TypeVariable parent = (TypeVariable) parentIt.next();
669         TypeNode type = parent.type();
670         
671         if(type != null)
672           {
673                     Iterator k = hp.iterator();
674                     while( k.hasNext() ) {
675                         TypeVariable otherparent = (TypeVariable) k.next();
676             TypeNode othertype = otherparent.type();
677             
678             if(type.hasDescendant(othertype))
679               {
680                 var.removeParent(parent);
681                 type = null;
682                 break;
683               }
684             
685             if(type.hasAncestor(othertype))
686               {
687                 var.removeParent(otherparent);
688                 k.remove();
689               }
690               }
691             
692             if(type != null)
693               {
694             hp.add(parent);
695               }
696           }
697           }
698       }
699       }
700   }
701 
702   private void assign_types_1_2() throws TypeException
703   {
704     for( Iterator localIt = stmtBody.getLocals().iterator(); localIt.hasNext(); ) {
705         final Local local = (Local) localIt.next();
706     TypeVariable var = typeVariable(local);
707     
708     if(var == null)
709       {
710         local.setType(RefType.v("java.lang.Object"));
711       }
712     else if (var.depth() == 0)
713       {
714         if(var.type() == null)
715           {
716         TypeVariable.error("Type Error(5):  Variable without type");
717           }
718         else
719           {
720         local.setType(var.type().type());
721           }
722       }
723     else
724       {
725         TypeVariable element = var.element();
726         
727         for(int j = 1; j < var.depth(); j++)
728           {
729         element = element.element();
730           }
731 
732         if(element.type() == null)
733           {
734         TypeVariable.error("Type Error(6):  Array variable without base type");
735           }
736         else if(element.type().type() instanceof NullType)
737           {
738         local.setType(NullType.v());
739           }
740         else
741           {
742         Type t = element.type().type();
743         if(t instanceof IntType)
744           {
745             local.setType(var.approx().type());
746           }
747         else
748           {
749             local.setType(ArrayType.v(t, var.depth()));
750           }
751           }
752       }
753     
754     if(DEBUG)
755       {
756         if((var != null) &&
757            (var.approx() != null) &&
758            (var.approx().type() != null) &&
759            (local != null) &&
760            (local.getType() != null) &&
761            !local.getType().equals(var.approx().type()))
762           {
763         G.v().out.println("local: " + local + ", type: " + local.getType() + ", approx: " + var.approx().type());
764           }
765       }
766       }
767   }
768 
769   private void assign_types_3() throws TypeException
770   {
771     for( Iterator localIt = stmtBody.getLocals().iterator(); localIt.hasNext(); ) {
772         final Local local = (Local) localIt.next();
773     TypeVariable var = typeVariable(local);
774     
775     if(var == null ||
776        var.approx() == null ||
777        var.approx().type() == null)
778       {
779         local.setType(RefType.v("java.lang.Object"));
780       }
781     else
782       {
783         local.setType(var.approx().type());
784       }
785       }
786   }
787 
788   private void check_constraints() throws TypeException
789   {
790     ConstraintChecker checker = new ConstraintChecker(this, false);
791     StringBuffer   s = null;
792 
793     if(DEBUG)
794       {
795     s = new StringBuffer  ("Checking:\n");
796       }
797 
798     for( Iterator stmtIt = stmtBody.getUnits().iterator(); stmtIt.hasNext(); ) {
799 
800         final Stmt stmt = (Stmt) stmtIt.next();
801     if(DEBUG)
802       {
803         s.append(" " + stmt + "\n");
804       }
805     try
806       {
807         checker.check(stmt, stmtBody);
808       }
809     catch(TypeException e)
810       {
811         if(DEBUG)
812           {
813         G.v().out.println(s);
814           }
815         throw e;
816       }
817       }
818   }
819 
820   private void check_and_fix_constraints() throws TypeException
821   {
822     ConstraintChecker checker = new ConstraintChecker(this, true);
823     StringBuffer   s = null;
824     PatchingChain units = stmtBody.getUnits();
825     Stmt[] stmts = new Stmt[units.size()];
826     units.toArray(stmts);
827 
828     if(DEBUG)
829       {
830     s = new StringBuffer  ("Checking:\n");
831       }
832 
833     for(int i = 0; i < stmts.length; i++)
834       {
835     Stmt stmt = stmts[i];
836 
837     if(DEBUG)
838       {
839         s.append(" " + stmt + "\n");
840       }
841     try
842       {
843         checker.check(stmt, stmtBody);
844       }
845     catch(TypeException e)
846       {
847         if(DEBUG)
848           {
849         G.v().out.println(s);
850           }
851         throw e;
852       }
853       }
854   }
855 
856   private void compute_approximate_types() throws TypeException
857   {
858     TreeSet workList = new TreeSet();
859 
860     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
861 
862         final TypeVariable var = (TypeVariable) varIt.next();
863 
864     if(var.type() != null)
865       {
866         workList.add(var);
867       }
868       }
869 
870     TypeVariable.computeApprox(workList);
871 
872     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
873 
874         final TypeVariable var = (TypeVariable) varIt.next();
875 
876     if(var.approx() == NULL)
877       {
878         var.union(typeVariable(NULL));
879       }
880     else if (var.approx() == null)
881       {
882         var.union(typeVariable(NULL));
883       }
884       }
885   }
886   
887   private void compute_solved()
888   {
889     Set unsolved_set = new TreeSet();
890     Set solved_set = new TreeSet();
891     
892     for( Iterator varIt = typeVariableList.iterator(); varIt.hasNext(); ) {
893     
894         final TypeVariable var = (TypeVariable) varIt.next();
895     
896     if(var.depth() == 0)
897       {
898         if(var.type() == null)
899           {
900         unsolved_set.add(var);
901           }
902         else
903           {
904         solved_set.add(var);
905           }
906       }
907       }
908 
909     solved = new LinkedList(solved_set);
910     unsolved = new LinkedList(unsolved_set);
911   }
912 
913   private void refresh_solved() throws TypeException
914   {
915     Set unsolved_set = new TreeSet();
916     Set solved_set = new TreeSet(solved);
917     
918     for( Iterator varIt = unsolved.iterator(); varIt.hasNext(); ) {
919     
920         final TypeVariable var = (TypeVariable) varIt.next();
921     
922     if(var.depth() == 0)
923       {
924         if(var.type() == null)
925           {
926         unsolved_set.add(var);
927           }
928         else
929           {
930         solved_set.add(var);
931           }
932       }
933       }
934 
935     solved = new LinkedList(solved_set);
936     unsolved = new LinkedList(unsolved_set);
937     
938     // validate();
939   }
940 
941   private void categorize() throws TypeException
942   {
943     refresh_solved();
944    
945     single_soft_parent = new LinkedList();
946     single_hard_parent = new LinkedList();
947     multiple_parents = new LinkedList();
948     single_child_not_null = new LinkedList();
949     single_null_child = new LinkedList();
950     multiple_children = new LinkedList();
951     
952     for(Iterator i = unsolved.iterator(); i .hasNext(); )
953       {
954     TypeVariable var = (TypeVariable) i.next();
955     
956     // parent category
957     {
958       List parents = var.parents();
959       int size = parents.size();
960       
961       if(size == 0)
962         {
963           var.addParent(typeVariable(OBJECT));
964           single_soft_parent.add(var);
965         }
966       else if(size == 1)
967         {
968           TypeVariable parent = (TypeVariable) parents.get(0);
969           
970           if(parent.type() == null)
971         {
972           single_soft_parent.add(var);
973         }
974           else
975         {
976           single_hard_parent.add(var);
977         }
978         }
979       else
980         {
981           multiple_parents.add(var);
982         }
983     }
984     
985     // child category
986     {
987       List children = var.children();
988       int size = children.size();
989       
990       if(size == 0)
991         {
992           var.addChild(typeVariable(NULL));
993           single_null_child.add(var);
994         }
995       else if(size == 1)
996         {
997           TypeVariable child = (TypeVariable) children.get(0);
998           
999           if(child.type() == NULL)
1000        {
1001          single_null_child.add(var);
1002        }
1003          else
1004        {
1005          single_child_not_null.add(var);
1006        }
1007        }
1008      else
1009        {
1010          multiple_children.add(var);
1011        }
1012    }
1013      }
1014  }
1015
1016  private void validate() throws TypeException
1017  {
1018    for( Iterator varIt = solved.iterator(); varIt.hasNext(); ) {
1019        final TypeVariable var = (TypeVariable) varIt.next();
1020    
1021    try
1022      {
1023        var.validate();
1024      }
1025    catch(TypeException e)
1026      {
1027        debug_vars("Error while validating");
1028        throw(e);
1029      }
1030      }
1031  }
1032
1033  /*
1034  private void remove_spurious_locals()
1035  {
1036    boolean repeat;
1037
1038    do
1039      {
1040    ExceptionalUnitGraph graph = new ExceptionalUnitGraph(stmtBody);
1041    SimpleLocalDefs defs = new SimpleLocalDefs(graph);
1042    SimpleLocalUses uses = new SimpleLocalUses(graph, defs);
1043    PatchingChain units = stmtBody.getUnits();
1044    Stmt[] stmts = new Stmt[units.size()];
1045    HashSet deleted = new HashSet();
1046
1047    repeat = false;
1048    units.toArray(stmts);
1049    
1050    for(int i = 0; i < stmts.length; i++)
1051      {
1052        Stmt stmt = stmts[i];
1053        
1054        if(stmt instanceof AssignStmt)
1055          {
1056        AssignStmt assign1 = (AssignStmt) stmt;
1057        
1058        if(assign1.getLeftOp() instanceof Local)
1059          {
1060            List uselist = uses.getUsesOf(assign1);
1061            
1062            if(uselist.size() == 1)
1063              {
1064            UnitValueBoxPair pair = (UnitValueBoxPair) uselist.get(0);
1065            
1066            List deflist = defs.getDefsOfAt((Local) pair.getValueBox().getValue(), pair.getUnit());
1067            
1068            if(deflist.size() == 1)
1069              {
1070                if(pair.getValueBox().canContainValue(assign1.getRightOp()))
1071                  {
1072                // This is definitely a spurious local!
1073
1074                // Hmm.. use is in a deleted statement.  Must wait till next iteration.
1075                if(deleted.contains(pair.getUnit()))
1076                  {
1077                    repeat = true;
1078                    continue;
1079                  }
1080                
1081                pair.getValueBox().setValue(assign1.getRightOp());
1082                deleted.add(assign1);
1083                units.remove(assign1);
1084                stmtBody.getLocals().remove(assign1.getLeftOp());
1085                
1086                  }
1087              }
1088              }
1089          }
1090          }
1091      }
1092      }
1093    while(repeat);
1094  }
1095  */
1096
1097  private void split_new()
1098  {
1099    ExceptionalUnitGraph graph = new ExceptionalUnitGraph(stmtBody);
1100    SimpleLocalDefs defs = new SimpleLocalDefs(graph);
1101    // SimpleLocalUses uses = new SimpleLocalUses(graph, defs);
1102    PatchingChain units = stmtBody.getUnits();
1103    Stmt[] stmts = new Stmt[units.size()];
1104
1105    units.toArray(stmts);
1106    
1107    for(int i = 0; i < stmts.length; i++)
1108      {
1109    Stmt stmt = stmts[i];
1110
1111    if(stmt instanceof InvokeStmt)
1112      {
1113        InvokeStmt invoke = (InvokeStmt) stmt;
1114        
1115        if(invoke.getInvokeExpr() instanceof SpecialInvokeExpr)
1116          {
1117        SpecialInvokeExpr special = (SpecialInvokeExpr) invoke.getInvokeExpr();
1118        
1119        if(special.getMethodRef().name().equals("<init>"))
1120          {
1121            List deflist = defs.getDefsOfAt((Local) special.getBase(), invoke);
1122            
1123            while(deflist.size() == 1)
1124              {
1125            Stmt stmt2 = (Stmt) deflist.get(0);
1126            
1127            if(stmt2 instanceof AssignStmt)
1128              {
1129                AssignStmt assign = (AssignStmt) stmt2;
1130                
1131                if(assign.getRightOp() instanceof Local)
1132                  {
1133                deflist = defs.getDefsOfAt((Local) assign.getRightOp(), assign);
1134                continue;
1135                  }
1136                else if(assign.getRightOp() instanceof NewExpr)
1137                  {         
1138                // We split the local.
1139                //G.v().out.println("split: [" + assign + "] and [" + stmt + "]");
1140                Local newlocal = Jimple.v().newLocal("tmp", null);
1141                stmtBody.getLocals().add(newlocal);
1142                
1143                special.setBase(newlocal);
1144                
1145                units.insertAfter(Jimple.v().newAssignStmt(assign.getLeftOp(), newlocal), assign);
1146                assign.setLeftOp(newlocal);
1147                  }
1148              }
1149            break;
1150              }
1151          }
1152          }
1153      }
1154      }
1155  }
1156}
1157
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags