|
1
19
20
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
40 public class TypeResolver
41 {
42
43 private final List typeVariableList = new ArrayList();
44
45
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 private List unsolved;
64 private List solved;
65
66
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
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
110 public TypeVariable typeVariable(Type type)
111 {
112 return typeVariable(ClassHierarchy.v().typeNode(type));
113 }
114
115
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  (st.toString());
164 }
165 }
166 }
167
168 private void debug_vars(String 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 s = null;
569
570 if(DEBUG)
571 {
572 s = new StringBuffer ("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 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 ("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 |
Java API By Example, From Geeks To Geeks.