1 /* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2014 Eric Lafortune (eric (at) graphics.cornell.edu) 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms of the GNU General Public License as published by the Free 9 * Software Foundation; either version 2 of the License, or (at your option) 10 * any later version. 11 * 12 * This program is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 15 * more details. 16 * 17 * You should have received a copy of the GNU General Public License along 18 * with this program; if not, write to the Free Software Foundation, Inc., 19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20 */ 21 package proguard.evaluation.value; 22 23 import proguard.classfile.*; 24 import proguard.classfile.util.ClassUtil; 25 import proguard.classfile.visitor.ClassCollector; 26 27 import java.util.*; 28 29 /** 30 * This ReferenceValue represents a partially evaluated reference value. 31 * It has a type and a flag that indicates whether the value could be 32 * <code>null</code>. If the type is <code>null</code>, the value is 33 * <code>null</code>. 34 * 35 * @author Eric Lafortune 36 */ 37 public class TypedReferenceValue extends ReferenceValue 38 { 39 private static final boolean DEBUG = false; 40 41 42 protected final String type; 43 protected final Clazz referencedClass; 44 protected final boolean mayBeNull; 45 46 47 /** 48 * Creates a new TypedReferenceValue. 49 */ 50 public TypedReferenceValue(String type, 51 Clazz referencedClass, 52 boolean mayBeNull) 53 { 54 this.type = type; 55 this.referencedClass = referencedClass; 56 this.mayBeNull = mayBeNull; 57 } 58 59 60 // Implementations for ReferenceValue. 61 62 public String getType() 63 { 64 return type; 65 } 66 67 68 public Clazz getReferencedClass() 69 { 70 return referencedClass; 71 } 72 73 74 // Implementations of unary methods of ReferenceValue. 75 76 public int isNull() 77 { 78 return type == null ? ALWAYS : 79 mayBeNull ? MAYBE : 80 NEVER; 81 } 82 83 84 public int instanceOf(String otherType, Clazz otherReferencedClass) 85 { 86 String thisType = this.type; 87 88 // If this type is null, it is never an instance of any class. 89 if (thisType == null) 90 { 91 return NEVER; 92 } 93 94 // Start taking into account the type dimensions. 95 int thisDimensionCount = ClassUtil.internalArrayTypeDimensionCount(thisType); 96 int otherDimensionCount = ClassUtil.internalArrayTypeDimensionCount(otherType); 97 int commonDimensionCount = Math.min(thisDimensionCount, otherDimensionCount); 98 99 // Strip any common array prefixes. 100 thisType = thisType.substring(commonDimensionCount); 101 otherType = otherType.substring(commonDimensionCount); 102 103 // If either stripped type is a primitive type, we can tell right away. 104 if (commonDimensionCount > 0 && 105 (ClassUtil.isInternalPrimitiveType(thisType.charAt(0)) || 106 ClassUtil.isInternalPrimitiveType(otherType.charAt(0)))) 107 { 108 return !thisType.equals(otherType) ? NEVER : 109 mayBeNull ? MAYBE : 110 ALWAYS; 111 } 112 113 // Strip the class type prefix and suffix of this type, if any. 114 if (thisDimensionCount == commonDimensionCount) 115 { 116 thisType = ClassUtil.internalClassNameFromClassType(thisType); 117 } 118 119 // Strip the class type prefix and suffix of the other type, if any. 120 if (otherDimensionCount == commonDimensionCount) 121 { 122 otherType = ClassUtil.internalClassNameFromClassType(otherType); 123 } 124 125 // If this type is an array type, and the other type is not 126 // java.lang.Object, java.lang.Cloneable, or java.io.Serializable, 127 // this type can never be an instance. 128 if (thisDimensionCount > otherDimensionCount && 129 !ClassUtil.isInternalArrayInterfaceName(otherType)) 130 { 131 return NEVER; 132 } 133 134 // If the other type is an array type, and this type is not 135 // java.lang.Object, java.lang.Cloneable, or java.io.Serializable, 136 // this type can never be an instance. 137 if (thisDimensionCount < otherDimensionCount && 138 !ClassUtil.isInternalArrayInterfaceName(thisType)) 139 { 140 return NEVER; 141 } 142 143 // If this type may be null, it might not be an instance of any class. 144 if (mayBeNull) 145 { 146 return MAYBE; 147 } 148 149 // If this type is equal to the other type, or if the other type is 150 // java.lang.Object, this type is always an instance. 151 if (thisType.equals(otherType) || 152 ClassConstants.NAME_JAVA_LANG_OBJECT.equals(otherType)) 153 { 154 return ALWAYS; 155 } 156 157 // If this type is an array type, it's ok. 158 if (thisDimensionCount > otherDimensionCount) 159 { 160 return ALWAYS; 161 } 162 163 // If the other type is an array type, it might be ok. 164 if (thisDimensionCount < otherDimensionCount) 165 { 166 return MAYBE; 167 } 168 169 // If the value extends the type, we're sure. 170 return referencedClass != null && 171 otherReferencedClass != null && 172 referencedClass.extendsOrImplements(otherReferencedClass) ? 173 ALWAYS : 174 MAYBE; 175 } 176 177 178 public ReferenceValue generalizeMayBeNull(boolean mayBeNull) 179 { 180 return this.mayBeNull == mayBeNull ? 181 this : 182 new TypedReferenceValue(type, referencedClass, true); 183 } 184 185 186 public ReferenceValue referenceArrayLoad(IntegerValue indexValue, ValueFactory valueFactory) 187 { 188 return 189 type == null ? ValueFactory.REFERENCE_VALUE_NULL : 190 !ClassUtil.isInternalArrayType(type) ? ValueFactory.REFERENCE_VALUE_JAVA_LANG_OBJECT_MAYBE_NULL : 191 valueFactory.createValue(type.substring(1), 192 referencedClass, 193 true).referenceValue(); 194 } 195 196 197 // Implementations of binary methods of ReferenceValue. 198 199 public ReferenceValue generalize(ReferenceValue other) 200 { 201 return other.generalize(this); 202 } 203 204 205 public int equal(ReferenceValue other) 206 { 207 return other.equal(this); 208 } 209 210 211 // Implementations of binary ReferenceValue methods with TypedReferenceValue 212 // arguments. 213 214 public ReferenceValue generalize(TypedReferenceValue other) 215 { 216 // If both types are identical, the generalization is the same too. 217 if (this.equals(other)) 218 { 219 return this; 220 } 221 222 String thisType = this.type; 223 String otherType = other.type; 224 225 // If both types are nul, the generalization is null too. 226 if (thisType == null && otherType == null) 227 { 228 return ValueFactory.REFERENCE_VALUE_NULL; 229 } 230 231 // If this type is null, the generalization is the other type, maybe null. 232 if (thisType == null) 233 { 234 return other.generalizeMayBeNull(true); 235 } 236 237 // If the other type is null, the generalization is this type, maybe null. 238 if (otherType == null) 239 { 240 return this.generalizeMayBeNull(true); 241 } 242 243 boolean mayBeNull = this.mayBeNull || other.mayBeNull; 244 245 // If the two types are equal, the generalization remains the same, maybe null. 246 if (thisType.equals(otherType)) 247 { 248 return typedReferenceValue(this, mayBeNull); 249 } 250 251 // Start taking into account the type dimensions. 252 int thisDimensionCount = ClassUtil.internalArrayTypeDimensionCount(thisType); 253 int otherDimensionCount = ClassUtil.internalArrayTypeDimensionCount(otherType); 254 int commonDimensionCount = Math.min(thisDimensionCount, otherDimensionCount); 255 256 if (thisDimensionCount == otherDimensionCount) 257 { 258 // See if we can take into account the referenced classes. 259 Clazz thisReferencedClass = this.referencedClass; 260 Clazz otherReferencedClass = other.referencedClass; 261 262 if (thisReferencedClass != null && 263 otherReferencedClass != null) 264 { 265 // Is one class simply an extension of the other one? 266 if (thisReferencedClass.extendsOrImplements(otherReferencedClass)) 267 { 268 return typedReferenceValue(other, mayBeNull); 269 } 270 271 if (otherReferencedClass.extendsOrImplements(thisReferencedClass)) 272 { 273 return typedReferenceValue(this, mayBeNull); 274 } 275 276 // Do the classes have a non-trivial common superclass? 277 Clazz commonClass = findCommonClass(thisReferencedClass, 278 otherReferencedClass, 279 false); 280 281 if (commonClass.getName().equals(ClassConstants.NAME_JAVA_LANG_OBJECT)) 282 { 283 // Otherwise, do the classes have a common interface? 284 Clazz commonInterface = findCommonClass(thisReferencedClass, 285 otherReferencedClass, 286 true); 287 if (commonInterface != null) 288 { 289 commonClass = commonInterface; 290 } 291 } 292 293 return new TypedReferenceValue(commonDimensionCount == 0 ? 294 commonClass.getName() : 295 ClassUtil.internalArrayTypeFromClassName(commonClass.getName(), 296 commonDimensionCount), 297 commonClass, 298 mayBeNull); 299 } 300 } 301 else if (thisDimensionCount > otherDimensionCount) 302 { 303 // See if the other type is an interface type of arrays. 304 if (ClassUtil.isInternalArrayInterfaceName(ClassUtil.internalClassNameFromClassType(otherType))) 305 { 306 return typedReferenceValue(other, mayBeNull); 307 } 308 } 309 else if (thisDimensionCount < otherDimensionCount) 310 { 311 // See if this type is an interface type of arrays. 312 if (ClassUtil.isInternalArrayInterfaceName(ClassUtil.internalClassNameFromClassType(thisType))) 313 { 314 return typedReferenceValue(this, mayBeNull); 315 } 316 } 317 318 // Reduce the common dimension count if either type is an array of 319 // primitives type of this dimension. 320 if (commonDimensionCount > 0 && 321 (ClassUtil.isInternalPrimitiveType(otherType.charAt(commonDimensionCount))) || 322 ClassUtil.isInternalPrimitiveType(thisType.charAt(commonDimensionCount))) 323 { 324 commonDimensionCount--; 325 } 326 327 // Fall back on a basic Object or array of Objects type. 328 return 329 commonDimensionCount != 0 ? 330 new TypedReferenceValue(ClassUtil.internalArrayTypeFromClassName(ClassConstants.NAME_JAVA_LANG_OBJECT, commonDimensionCount), 331 null, 332 mayBeNull) : 333 mayBeNull ? 334 ValueFactory.REFERENCE_VALUE_JAVA_LANG_OBJECT_MAYBE_NULL : 335 ValueFactory.REFERENCE_VALUE_JAVA_LANG_OBJECT_NOT_NULL; 336 } 337 338 339 /** 340 * Returns the most specific common superclass or interface of the given 341 * classes. 342 * @param class1 the first class. 343 * @param class2 the second class. 344 * @param interfaces specifies whether to look for a superclass or for an 345 * interface. 346 * @return the common class. 347 */ 348 private Clazz findCommonClass(Clazz class1, 349 Clazz class2, 350 boolean interfaces) 351 { 352 // Collect the superclasses or the interfaces of this class. 353 Set superClasses1 = new HashSet(); 354 class1.hierarchyAccept(!interfaces, 355 !interfaces, 356 interfaces, 357 false, 358 new ClassCollector(superClasses1)); 359 360 int superClasses1Count = superClasses1.size(); 361 if (superClasses1Count == 0) 362 { 363 if (interfaces) 364 { 365 return null; 366 } 367 else if (class1.getSuperName() != null) 368 { 369 throw new IllegalArgumentException("Can't find any super classes of ["+class1.getName()+"] (not even immediate super class ["+class1.getSuperName()+"])"); 370 } 371 } 372 373 // Collect the superclasses or the interfaces of the other class. 374 Set superClasses2 = new HashSet(); 375 class2.hierarchyAccept(!interfaces, 376 !interfaces, 377 interfaces, 378 false, 379 new ClassCollector(superClasses2)); 380 381 int superClasses2Count = superClasses2.size(); 382 if (superClasses2Count == 0) 383 { 384 if (interfaces) 385 { 386 return null; 387 } 388 else if (class2.getSuperName() != null) 389 { 390 throw new IllegalArgumentException("Can't find any super classes of ["+class2.getName()+"] (not even immediate super class ["+class2.getSuperName()+"])"); 391 } 392 } 393 394 if (DEBUG) 395 { 396 System.out.println("ReferenceValue.generalize this ["+class1.getName()+"] with other ["+class2.getName()+"] (interfaces = "+interfaces+")"); 397 System.out.println(" This super classes: "+superClasses1); 398 System.out.println(" Other super classes: "+superClasses2); 399 } 400 401 // Find the common superclasses. 402 superClasses1.retainAll(superClasses2); 403 404 if (DEBUG) 405 { 406 System.out.println(" Common super classes: "+superClasses1); 407 } 408 409 if (interfaces && superClasses1.isEmpty()) 410 { 411 return null; 412 } 413 414 // Find a class that is a subclass of all common superclasses, 415 // or that at least has the maximum number of common superclasses. 416 Clazz commonClass = null; 417 418 int maximumSuperClassCount = -1; 419 420 // Go over all common superclasses to find it. In case of 421 // multiple subclasses, keep the lowest one alphabetically, 422 // in order to ensure that the choice is deterministic. 423 Iterator commonSuperClasses = superClasses1.iterator(); 424 while (commonSuperClasses.hasNext()) 425 { 426 Clazz commonSuperClass = (Clazz)commonSuperClasses.next(); 427 428 int superClassCount = superClassCount(commonSuperClass, superClasses1); 429 if (maximumSuperClassCount < superClassCount || 430 (maximumSuperClassCount == superClassCount && 431 commonClass != null && 432 commonClass.getName().compareTo(commonSuperClass.getName()) > 0)) 433 { 434 commonClass = commonSuperClass; 435 maximumSuperClassCount = superClassCount; 436 } 437 } 438 439 if (commonClass == null) 440 { 441 throw new IllegalArgumentException("Can't find common super class of ["+ 442 class1.getName() +"] (with "+superClasses1Count +" known super classes) and ["+ 443 class2.getName()+"] (with "+superClasses2Count+" known super classes)"); 444 } 445 446 if (DEBUG) 447 { 448 System.out.println(" Best common class: ["+commonClass.getName()+"]"); 449 } 450 451 return commonClass; 452 } 453 454 455 /** 456 * Returns the given reference value that may or may not be null, ensuring 457 * that it is a TypedReferenceValue, not a subclass. 458 */ 459 private static ReferenceValue typedReferenceValue(TypedReferenceValue referenceValue, 460 boolean mayBeNull) 461 { 462 return referenceValue.getClass() == TypedReferenceValue.class ? 463 referenceValue.generalizeMayBeNull(mayBeNull) : 464 new TypedReferenceValue(referenceValue.type, 465 referenceValue.referencedClass, 466 mayBeNull); 467 } 468 469 470 /** 471 * Returns if the number of superclasses of the given class in the given 472 * set of classes. 473 */ 474 private int superClassCount(Clazz subClass, Set classes) 475 { 476 int count = 0; 477 478 Iterator iterator = classes.iterator(); 479 480 while (iterator.hasNext()) 481 { 482 Clazz clazz = (Clazz)iterator.next(); 483 if (subClass.extendsOrImplements(clazz)) 484 { 485 count++; 486 } 487 } 488 489 return count; 490 } 491 492 493 public int equal(TypedReferenceValue other) 494 { 495 return this.type == null && other.type == null ? ALWAYS : MAYBE; 496 } 497 498 499 // Implementations of binary ReferenceValue methods with 500 // IdentifiedReferenceValue arguments. 501 502 public ReferenceValue generalize(IdentifiedReferenceValue other) 503 { 504 return generalize((TypedReferenceValue)other); 505 } 506 507 508 public int equal(IdentifiedReferenceValue other) 509 { 510 return equal((TypedReferenceValue)other); 511 } 512 513 514 // Implementations of binary ReferenceValue methods with 515 // ArrayReferenceValue arguments. 516 517 public ReferenceValue generalize(ArrayReferenceValue other) 518 { 519 return generalize((TypedReferenceValue)other); 520 } 521 522 523 public int equal(ArrayReferenceValue other) 524 { 525 return equal((TypedReferenceValue)other); 526 } 527 528 529 // Implementations of binary ReferenceValue methods with 530 // IdentifiedArrayReferenceValue arguments. 531 532 public ReferenceValue generalize(IdentifiedArrayReferenceValue other) 533 { 534 return generalize((ArrayReferenceValue)other); 535 } 536 537 538 public int equal(IdentifiedArrayReferenceValue other) 539 { 540 return equal((ArrayReferenceValue)other); 541 } 542 543 544 // Implementations of binary ReferenceValue methods with 545 // DetailedArrayReferenceValue arguments. 546 547 public ReferenceValue generalize(DetailedArrayReferenceValue other) 548 { 549 return generalize((IdentifiedArrayReferenceValue)other); 550 } 551 552 553 public int equal(DetailedArrayReferenceValue other) 554 { 555 return equal((IdentifiedArrayReferenceValue)other); 556 } 557 558 559 // Implementations for Value. 560 561 public boolean isParticular() 562 { 563 return type == null; 564 } 565 566 567 public final String internalType() 568 { 569 return 570 type == null ? ClassConstants.TYPE_JAVA_LANG_OBJECT : 571 ClassUtil.isInternalArrayType(type) ? type : 572 ClassConstants.TYPE_CLASS_START + 573 type + 574 ClassConstants.TYPE_CLASS_END; 575 } 576 577 578 // Implementations for Object. 579 580 public boolean equals(Object object) 581 { 582 if (this == object) 583 { 584 return true; 585 } 586 587 if (object == null || 588 this.getClass() != object.getClass()) 589 { 590 return false; 591 } 592 593 TypedReferenceValue other = (TypedReferenceValue)object; 594 return this.type == null ? other.type == null : 595 (this.mayBeNull == other.mayBeNull && 596 this.type.equals(other.type)); 597 } 598 599 600 public int hashCode() 601 { 602 return this.getClass().hashCode() ^ 603 (type == null ? 0 : type.hashCode() ^ (mayBeNull ? 0 : 1)); 604 } 605 606 607 public String toString() 608 { 609 return type == null ? 610 "null" : 611 type + (referencedClass == null ? "?" : "") + (mayBeNull ? "" : "!"); 612 } 613 } 614