|
1
19
20
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
34
35 class TypeVariableBV implements Comparable 
36 {
37 private static final boolean DEBUG = false;
38
39 private final int id;
40 private final TypeResolverBV resolver;
41
42 private TypeVariableBV rep = this;
43 private int rank = 0;
44
45 private TypeNode approx;
46
47 private TypeNode type;
48 private TypeVariableBV array;
49 private TypeVariableBV element;
50 private int depth;
51
52 private BitVector parents = new BitVector();
53 private BitVector children = new BitVector();
54 private BitVector ancestors;
55 private BitVector indirectAncestors;
56
57 public TypeVariableBV(int id, TypeResolverBV resolver)
58 {
59 this.id = id;
60 this.resolver = resolver;
61 }
62
63 public TypeVariableBV(int id, TypeResolverBV resolver, TypeNode type)
64 {
65 this.id = id;
66 this.resolver = resolver;
67 this.type = type;
68 approx = type;
69
70 for( Iterator parentIt = type.parents().iterator(); parentIt.hasNext(); ) {
71
72 final TypeNode parent = (TypeNode) parentIt.next();
73
74 addParent(resolver.typeVariable(parent));
75 }
76
77 if(type.hasElement())
78 {
79 element = resolver.typeVariable(type.element());
80 element.array = this;
81 }
82 }
83
84 public int hashCode()
85 {
86 if(rep != this)
87 {
88 return ecr().hashCode();
89 }
90
91 return id;
92 }
93
94 public boolean equals(Object obj)
95 {
96 if(rep != this)
97 {
98 return ecr().equals(obj);
99 }
100
101 if(obj == null)
102 {
103 return false;
104 }
105
106 if(!obj.getClass().equals(getClass()))
107 {
108 return false;
109 }
110
111 TypeVariableBV ecr = ((TypeVariableBV) obj).ecr();
112
113 if(ecr != this)
114 {
115 return false;
116 }
117
118 return true;
119 }
120
121 public int compareTo(Object o)
122 {
123 if(rep != this)
124 {
125 return ecr().compareTo(o);
126 }
127
128 return id - ((TypeVariableBV) o).ecr().id;
129 }
130
131 private TypeVariableBV ecr()
132 {
133 if(rep != this)
134 {
135 rep = rep.ecr();
136 }
137
138 return rep;
139 }
140
141 public TypeVariableBV union(TypeVariableBV var) throws TypeException
142 {
143 if(rep != this)
144 {
145 return ecr().union(var);
146 }
147
148 TypeVariableBV y = var.ecr();
149
150 if(this == y)
151 {
152 parents.clear(var.ownId());
153 children.clear(var.ownId());
154 return this;
155 }
156
157 if(rank > y.rank)
158 {
159 resolver.invalidateId(y.id());
160 y.rep = this;
161
162 merge(y);
163 y.clear();
164
165 return this;
166 }
167
168 resolver.invalidateId(this.id());
169 rep = y;
170 if(rank == y.rank)
171 {
172 y.rank++;
173 }
174
175 y.merge(this);
176 clear();
177
178 return y;
179 }
180
181 private void clear()
182 {
183 approx = null;
184 type = null;
185 element = null;
186 array = null;
187 parents = null;
188 children = null;
189 ancestors = null;
190 indirectAncestors = null;
191 }
192
193 private void merge(TypeVariableBV var) throws TypeException
194 {
195 if(depth != 0 || var.depth != 0)
196 {
197 throw new InternalTypingException();
198 }
199
200 if(type == null)
202 {
203 type = var.type;
204 }
205 else if(var.type != null)
206 {
207 error("Type Error(1): Attempt to merge two types.");
208 }
209
210 parents.or(var.parents);
211 parents.clear(var.ownId());
212 parents.clear(this.ownId());
213 children.or(var.children);
214 children.clear(var.ownId());
215 children.clear(this.ownId());
216 }
217
218 void validate() throws TypeException
219 {
220 if(rep != this)
221 {
222 ecr().validate();
223 return;
224 }
225
226 if(type != null)
228 {
229 for(BitSetIterator i = parents.iterator(); i.hasNext();)
230 {
231 TypeVariableBV parent = resolver.typeVariableForId(i.next()).ecr();
232
233 if(parent.type != null)
234 {
235 if(!type.hasAncestor(parent.type))
236 {
237 if(DEBUG)
238 {
239 G.v().out.println(parent.type + " is not a parent of " + type);
240 }
241
242 error("Type Error(2): Parent type is not a valid ancestor.");
243 }
244 }
245 }
246
247 for(BitSetIterator i = children.iterator(); i.hasNext();)
248 {
249 TypeVariableBV child = resolver.typeVariableForId(i.next()).ecr();
250
251 if(child.type != null)
252 {
253 if(!type.hasDescendant(child.type))
254 {
255 if(DEBUG)
256 {
257 G.v().out.println(child.type + "(" + child + ") is not a child of " + type + "(" + this + ")");
258 }
259
260 error("Type Error(3): Child type is not a valid descendant.");
261 }
262 }
263 }
264 }
265 }
266
267 public void removeIndirectRelations()
268 {
269 if(rep != this)
270 {
271 ecr().removeIndirectRelations();
272 return;
273 }
274
275 if(indirectAncestors == null)
276 {
277 fixAncestors();
278 }
279
280 BitVector parentsToRemove = new BitVector();
281 for( BitSetIterator parentIt = parents.iterator(); parentIt.hasNext(); ) {
282
283 final int parent = parentIt.next();
284 if(indirectAncestors.get(parent))
285 {
286 parentsToRemove.set(parent);
287 }
288 }
289
290 for(BitSetIterator i = parentsToRemove.iterator(); i.hasNext(); ) {
291 removeParent(resolver.typeVariableForId(i.next()));
292 }
293 }
294
295 private void fixAncestors()
296 {
297 BitVector ancestors = new BitVector(0);
298 BitVector indirectAncestors = new BitVector(0);
299 fixParents();
300 for(BitSetIterator i = parents.iterator(); i.hasNext();)
301 {
302 TypeVariableBV parent = resolver.typeVariableForId(i.next()).ecr();
303
304 if(parent.ancestors == null)
305 {
306 parent.fixAncestors();
307 }
308
309 ancestors.set(parent.id);
310 ancestors.or(parent.ancestors);
311 indirectAncestors.or(parent.ancestors);
312 }
313
314 this.ancestors = ancestors;
315 this.indirectAncestors = indirectAncestors;
316 }
317
318 private void fixParents()
319 {
320 if(rep != this) {
321 ecr().fixParents();
322 }
323
324 BitVector invalid = new BitVector(); invalid.or(parents);
325 invalid.and(resolver.invalidIds());
326 for(BitSetIterator i = invalid.iterator(); i.hasNext();) {
327 parents.set(resolver.typeVariableForId(i.next()).id());
328 }
329 parents.clear(this.id);
330 parents.clear(this.id());
331 parents.andNot(invalid);
332 }
333
334 public int id()
335 {
336 if(rep != this)
337 {
338 return ecr().id();
339 }
340
341 return id;
342 }
343
344 public int ownId()
345 {
346 return id;
347 }
348
349 public void addParent(TypeVariableBV variable)
350 {
351 if(rep != this)
352 {
353 ecr().addParent(variable);
354 return;
355 }
356
357 TypeVariableBV var = variable.ecr();
358
359 if(var == this)
360 {
361 return;
362 }
363
364 parents.set(var.id);
365 var.children.set(this.id);
366 }
367
368 public void removeParent(TypeVariableBV variable)
369 {
370 if(rep != this)
371 {
372 ecr().removeParent(variable);
373 return;
374 }
375
376 parents.clear(variable.id());
377 parents.clear(variable.ownId());
378 variable.children().clear(this.id);
379 }
380
381 public void addChild(TypeVariableBV variable)
382 {
383 if(rep != this)
384 {
385 ecr().addChild(variable);
386 return;
387 }
388
389 TypeVariableBV var = variable.ecr();
390
391 if(var == this)
392 {
393 return;
394 }
395
396 children.set(var.id);
397 parents.set(var.id);
398 }
399
400 public void removeChild(TypeVariableBV variable)
401 {
402 if(rep != this)
403 {
404 ecr().removeChild(variable);
405 return;
406 }
407
408 TypeVariableBV var = variable.ecr();
409
410 children.clear(var.id);
411 var.parents.clear(var.id);
412 }
413
414 public int depth()
415 {
416 if(rep != this)
417 {
418 return ecr().depth();
419 }
420
421 return depth;
422 }
423
424 public void makeElement()
425 {
426 if(rep != this)
427 {
428 ecr().makeElement();
429 return;
430 }
431
432 if(element == null)
433 {
434 element = resolver.typeVariable();
435 element.array = this;
436 }
437 }
438
439 public TypeVariableBV element()
440 {
441 if(rep != this)
442 {
443 return ecr().element();
444 }
445
446 return (element == null) ? null : element.ecr();
447 }
448
449 public TypeVariableBV array()
450 {
451 if(rep != this)
452 {
453 return ecr().array();
454 }
455
456 return (array == null) ? null : array.ecr();
457 }
458
459 public BitVector parents()
460 {
461 if(rep != this)
462 {
463 return ecr().parents();
464 }
465
466 return parents;
467 }
468
469 public BitVector children()
470 {
471 if(rep != this)
472 {
473 return ecr().children();
474 }
475
476 return children;
477 }
478
479 public TypeNode approx()
480 {
481 if(rep != this)
482 {
483 return ecr().approx();
484 }
485
486 return approx;
487 }
488
489 public TypeNode type()
490 {
491 if(rep != this)
492 {
493 return ecr().type();
494 }
495
496 return type;
497 }
498
499 static void error(String message) throws TypeException
500 {
501 try
502 {
503 throw new TypeException(message);
504 }
505 catch(TypeException e)
506 {
507 if(DEBUG)
508 {
509 e.printStackTrace();
510 }
511 throw e;
512 }
513 }
514
515
517 public static void computeApprox(TreeSet workList) throws TypeException
518 {
519 while(workList.size() > 0)
520 {
521 TypeVariableBV var = (TypeVariableBV) workList.first();
522 workList.remove(var);
523
524 var.fixApprox(workList);
525 }
526 }
527
528 private void fixApprox(TreeSet workList) throws TypeException
529 {
530 if(rep != this)
531 {
532 ecr().fixApprox(workList);
533 return;
534 }
535
536 if(type == null && approx != resolver.hierarchy().NULL)
537 {
538 TypeVariableBV element = element();
539
540 if(element != null)
541 {
542 if(!approx.hasElement())
543 {
544 G.v().out.println("*** " + this + " ***");
545
546 error("Type Error(4)");
547 }
548
549 TypeNode temp = approx.element();
550
551 if(element.approx == null)
552 {
553 element.approx = temp;
554 workList.add(element);
555 }
556 else
557 {
558 TypeNode type = element.approx.lca(temp);
559
560 if(type != element.approx)
561 {
562 element.approx = type;
563 workList.add(element);
564 }
565 else if(element.approx != resolver.hierarchy().INT)
566 {
567 type = approx.lca(element.approx.array());
568
569 if(type != approx)
570 {
571 approx = type;
572 workList.add(this);
573 }
574 }
575 }
576 }
577
578 TypeVariableBV array = array();
579
580 if(array != null &&
581 approx != resolver.hierarchy().NULL &&
582 approx != resolver.hierarchy().INT)
583 {
584 TypeNode temp = approx.array();
585
586 if(array.approx == null)
587 {
588 array.approx = temp;
589 workList.add(array);
590 }
591 else
592 {
593 TypeNode type = array.approx.lca(temp);
594
595 if(type != array.approx)
596 {
597 array.approx = type;
598 workList.add(array);
599 }
600 else
601 {
602 type = approx.lca(array.approx.element());
603
604 if(type != approx)
605 {
606 approx = type;
607 workList.add(this);
608 }
609 }
610 }
611 }
612 }
613
614 for(BitSetIterator i = parents.iterator(); i.hasNext();)
615 {
616 TypeVariableBV parent = resolver.typeVariableForId(i.next()).ecr();
617
618 if(parent.approx == null)
619 {
620 parent.approx = approx;
621 workList.add(parent);
622 }
623 else
624 {
625 TypeNode type = parent.approx.lca(approx);
626
627 if(type != parent.approx)
628 {
629 parent.approx = type;
630 workList.add(parent);
631 }
632 }
633 }
634
635 if(type != null)
636 {
637 approx = type;
638 }
639 }
640
641 public void fixDepth() throws TypeException
642 {
643 if(rep != this)
644 {
645 ecr().fixDepth();
646 return;
647 }
648
649 if(type != null)
650 {
651 if(type.type() instanceof ArrayType)
652 {
653 ArrayType at = (ArrayType) type.type();
654
655 depth = at.numDimensions;
656 }
657 else
658 {
659 depth = 0;
660 }
661 }
662 else
663 {
664 if(approx.type() instanceof ArrayType)
665 {
666 ArrayType at = (ArrayType) approx.type();
667
668 depth = at.numDimensions;
669 }
670 else
671 {
672 depth = 0;
673 }
674 }
675
676 if(depth == 0 && element() != null)
678 {
679 error("Type Error(11)");
680 }
681 else if(depth > 0 && element() == null)
682 {
683 makeElement();
684 TypeVariableBV element = element();
685 element.depth = depth - 1;
686
687 while(element.depth != 0)
688 {
689 element.makeElement();
690 element.element().depth = element.depth - 1;
691 element = element.element();
692 }
693 }
694 }
695
696 public void propagate()
697 {
698 if(rep != this)
699 {
700 ecr().propagate();
701 }
702
703 if(depth == 0)
704 {
705 return;
706 }
707
708 for(BitSetIterator i = parents.iterator(); i.hasNext(); )
709 {
710 TypeVariableBV var = resolver.typeVariableForId(i.next()).ecr();
711
712 if(var.depth() == depth)
713 {
714 element().addParent(var.element());
715 }
716 else if(var.depth() == 0)
717 {
718 if(var.type() == null) {
719 if (!G.v().isJ2ME) {
721 var.addChild(resolver.typeVariable(resolver.hierarchy().CLONEABLE));
722 var.addChild(resolver.typeVariable(resolver.hierarchy().SERIALIZABLE));
723 }
724 }
725 }
726 else
727 {
728 if(var.type() == null) {
729 if (!G.v().isJ2ME) {
731 var.addChild(resolver.typeVariable(ArrayType.v(RefType.v("java.lang.Cloneable"), var.depth())));
732 var.addChild(resolver.typeVariable(ArrayType.v(RefType.v("java.io.Serializable"), var.depth())));
733 }
734 }
735 }
736 }
737
738 for( BitSetIterator varIt = parents.iterator(); varIt.hasNext(); ) {
739
740 final TypeVariableBV var = resolver.typeVariableForId(varIt.next());
741 removeParent(var);
742 }
743 }
744
745 public String toString()
746 {
747 if(rep != this)
748 {
749 return ecr().toString();
750 }
751
752 StringBuffer s = new StringBuffer ();
753 s.append(",[parents:");
754
755 {
756 boolean comma = false;
757
758 for(BitSetIterator i = parents.iterator(); i.hasNext(); )
759 {
760 if(comma)
761 {
762 s.append(",");
763 }
764 else
765 {
766 comma = true;
767 }
768 s.append(i.next());
769 }
770 }
771
772 s.append("],[children:");
773
774 {
775 boolean comma = false;
776
777 for(BitSetIterator i = children.iterator(); i.hasNext(); )
778 {
779 if(comma)
780 {
781 s.append(",");
782 }
783 else
784 {
785 comma = true;
786 }
787 s.append(i.next());
788 }
789 }
790
791 s.append("]");
792 return "[id:" + id + ",depth:" + depth + ((type != null) ? (",type:" + type) : "") + ",approx:" + approx + s +
793 (element == null ? "" : ",arrayof:" + element.id()) + "]";
794 }
795
796 }
797 |
Popular Tags |
Java API By Example, From Geeks To Geeks.