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 |