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