1/* 2 * Javassist, a Java-bytecode translator toolkit. 3 * Copyright (C) 1999-2007 Shigeru Chiba, and others. All Rights Reserved. 4 * 5 * The contents of this file are subject to the Mozilla Public License Version 6 * 1.1 (the "License"); you may not use this file except in compliance with 7 * the License. Alternatively, the contents of this file may be used under 8 * the terms of the GNU Lesser General Public License Version 2.1 or later. 9 * 10 * Software distributed under the License is distributed on an "AS IS" basis, 11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 12 * for the specific language governing rights and limitations under the 13 * License. 14 */ 15package javassist.bytecode.analysis; 16 17import java.util.ArrayList; 18import java.util.HashMap; 19import java.util.IdentityHashMap; 20import java.util.Iterator; 21import java.util.Map; 22 23import javassist.ClassPool; 24import javassist.CtClass; 25import javassist.NotFoundException; 26 27/** 28 * Represents a JVM type in data-flow analysis. This abstraction is necessary since 29 * a JVM type not only includes all normal Java types, but also a few special types 30 * that are used by the JVM internally. See the static field types on this class for 31 * more info on these special types. 32 * 33 * All primitive and special types reuse the same instance, so identity comparison can 34 * be used when examining them. Normal java types must use {@link #equals(Object)} to 35 * compare type instances. 36 * 37 * In most cases, applications which consume this API, only need to call {@link #getCtClass()} 38 * to obtain the needed type information. 39 * 40 * @author Jason T. Greene 41 */ 42public class Type { 43 private final CtClass clazz; 44 private final boolean special; 45 46 private static final Map prims = new IdentityHashMap(); 47 /** Represents the double primitive type */ 48 public static final Type DOUBLE = new Type(CtClass.doubleType); 49 /** Represents the boolean primitive type */ 50 public static final Type BOOLEAN = new Type(CtClass.booleanType); 51 /** Represents the long primitive type */ 52 public static final Type LONG = new Type(CtClass.longType); 53 /** Represents the char primitive type */ 54 public static final Type CHAR = new Type(CtClass.charType); 55 /** Represents the byte primitive type */ 56 public static final Type BYTE = new Type(CtClass.byteType); 57 /** Represents the short primitive type */ 58 public static final Type SHORT = new Type(CtClass.shortType); 59 /** Represents the integer primitive type */ 60 public static final Type INTEGER = new Type(CtClass.intType); 61 /** Represents the float primitive type */ 62 public static final Type FLOAT = new Type(CtClass.floatType); 63 /** Represents the void primitive type */ 64 public static final Type VOID = new Type(CtClass.voidType); 65 66 /** 67 * Represents an unknown, or null type. This occurs when aconst_null is used. 68 * It is important not to treat this type as java.lang.Object, since a null can 69 * be assigned to any reference type. The analyzer will replace these with 70 * an actual known type if it can be determined by a merged path with known type 71 * information. If this type is encountered on a frame then it is guaranteed to 72 * be null, and the type information is simply not available. Any attempts to 73 * infer the type, without further information from the compiler would be a guess. 74 */ 75 public static final Type UNINIT = new Type(null); 76 77 /** 78 * Represents an internal JVM return address, which is used by the RET 79 * instruction to return to a JSR that invoked the subroutine. 80 */ 81 public static final Type RETURN_ADDRESS = new Type(null, true); 82 83 /** A placeholder used by the analyzer for the second word position of a double-word type */ 84 public static final Type TOP = new Type(null, true); 85 86 /** 87 * Represents a non-accessible value. Code cannot access the value this type 88 * represents. It occurs when bytecode reuses a local variable table 89 * position with non-mergable types. An example would be compiled code which 90 * uses the same position for a primitive type in one branch, and a reference type 91 * in another branch. 92 */ 93 public static final Type BOGUS = new Type(null, true); 94 95 /** Represents the java.lang.Object reference type */ 96 public static final Type OBJECT = lookupType("java.lang.Object"); 97 /** Represents the java.io.Serializable reference type */ 98 public static final Type SERIALIZABLE = lookupType("java.io.Serializable"); 99 /** Represents the java.lang.Coneable reference type */ 100 public static final Type CLONEABLE = lookupType("java.lang.Cloneable"); 101 /** Represents the java.lang.Throwable reference type */ 102 public static final Type THROWABLE = lookupType("java.lang.Throwable"); 103 104 static { 105 prims.put(CtClass.doubleType, DOUBLE); 106 prims.put(CtClass.longType, LONG); 107 prims.put(CtClass.charType, CHAR); 108 prims.put(CtClass.shortType, SHORT); 109 prims.put(CtClass.intType, INTEGER); 110 prims.put(CtClass.floatType, FLOAT); 111 prims.put(CtClass.byteType, BYTE); 112 prims.put(CtClass.booleanType, BOOLEAN); 113 prims.put(CtClass.voidType, VOID); 114 115 } 116 117 /** 118 * Obtain the Type for a given class. If the class is a primitive, 119 * the the unique type instance for the primitive will be returned. 120 * Otherwise a new Type instance representing the class is returned. 121 * 122 * @param clazz The java class 123 * @return a type instance for this class 124 */ 125 public static Type get(CtClass clazz) { 126 Type type = (Type)prims.get(clazz); 127 return type != null ? type : new Type(clazz); 128 } 129 130 private static Type lookupType(String name) { 131 try { 132 return new Type(ClassPool.getDefault().get(name)); 133 } catch (NotFoundException e) { 134 throw new RuntimeException(e); 135 } 136 } 137 138 Type(CtClass clazz) { 139 this(clazz, false); 140 } 141 142 private Type(CtClass clazz, boolean special) { 143 this.clazz = clazz; 144 this.special = special; 145 } 146 147 // Used to indicate a merge internally triggered a change 148 boolean popChanged() { 149 return false; 150 } 151 152 /** 153 * Gets the word size of this type. Double-word types, such as long and double 154 * will occupy two positions on the local variable table or stack. 155 * 156 * @return the number of words needed to hold this type 157 */ 158 public int getSize() { 159 return clazz == CtClass.doubleType || clazz == CtClass.longType || this == TOP ? 2 : 1; 160 } 161 162 /** 163 * Returns the class this type represents. If the type is special, null will be returned. 164 * 165 * @return the class for this type, or null if special 166 */ 167 public CtClass getCtClass() { 168 return clazz; 169 } 170 171 /** 172 * Returns whether or not this type is a normal java reference, i.e. it is or extends java.lang.Object. 173 * 174 * @return true if a java reference, false if a primitive or special 175 */ 176 public boolean isReference() { 177 return !special && (clazz == null || !clazz.isPrimitive()); 178 } 179 180 /** 181 * Returns whether or not the type is special. A special type is one that is either used 182 * for internal tracking, or is only used internally by the JVM. 183 * 184 * @return true if special, false if not 185 */ 186 public boolean isSpecial() { 187 return special; 188 } 189 190 /** 191 * Returns whether or not this type is an array. 192 * 193 * @return true if an array, false if not 194 */ 195 public boolean isArray() { 196 return clazz != null && clazz.isArray(); 197 } 198 199 /** 200 * Returns the number of dimensions of this array. If the type is not an 201 * array zero is returned. 202 * 203 * @return zero if not an array, otherwise the number of array dimensions. 204 */ 205 public int getDimensions() { 206 if (!isArray()) return 0; 207 208 String name = clazz.getName(); 209 int pos = name.length() - 1; 210 int count = 0; 211 while (name.charAt(pos) == ']' ) { 212 pos -= 2; 213 count++; 214 } 215 216 return count; 217 } 218 219 /** 220 * Returns the array component if this type is an array. If the type 221 * is not an array null is returned. 222 * 223 * @return the array component if an array, otherwise null 224 */ 225 public Type getComponent() { 226 if (this.clazz == null || !this.clazz.isArray()) 227 return null; 228 229 CtClass component; 230 try { 231 component = this.clazz.getComponentType(); 232 } catch (NotFoundException e) { 233 throw new RuntimeException(e); 234 } 235 236 Type type = (Type)prims.get(component); 237 return (type != null) ? type : new Type(component); 238 } 239 240 /** 241 * Determines whether this type is assignable, to the passed type. 242 * A type is assignable to another if it is either the same type, or 243 * a sub-type. 244 * 245 * @param type the type to test assignability to 246 * @return true if this is assignable to type, otherwise false 247 */ 248 public boolean isAssignableFrom(Type type) { 249 if (this == type) 250 return true; 251 252 if ((type == UNINIT && isReference()) || this == UNINIT && type.isReference()) 253 return true; 254 255 if (type instanceof MultiType) 256 return ((MultiType)type).isAssignableTo(this); 257 258 if (type instanceof MultiArrayType) 259 return ((MultiArrayType)type).isAssignableTo(this); 260 261 262 // Primitives and Special types must be identical 263 if (clazz == null || clazz.isPrimitive()) 264 return false; 265 266 try { 267 return type.clazz.subtypeOf(clazz); 268 } catch (Exception e) { 269 throw new RuntimeException(e); 270 } 271 } 272 273 /** 274 * Finds the common base type, or interface which both this and the specified 275 * type can be assigned. If there is more than one possible answer, then a {@link MultiType}, 276 * or a {@link MultiArrayType} is returned. Multi-types have special rules, 277 * and successive merges and assignment tests on them will alter their internal state, 278 * as well as other multi-types they have been merged with. This method is used by 279 * the data-flow analyzer to merge the type state from multiple branches. 280 * 281 * @param type the type to merge with 282 * @return the merged type 283 */ 284 public Type merge(Type type) { 285 if (type == this) 286 return this; 287 if (type == null) 288 return this; 289 if (type == Type.UNINIT) 290 return this; 291 if (this == Type.UNINIT) 292 return type; 293 294 // Unequal primitives and special types can not be merged 295 if (! type.isReference() || ! this.isReference()) 296 return BOGUS; 297 298 // Centralize merging of multi-interface types 299 if (type instanceof MultiType) 300 return type.merge(this); 301 302 if (type.isArray() && this.isArray()) 303 return mergeArray(type); 304 305 try { 306 return mergeClasses(type); 307 } catch (NotFoundException e) { 308 throw new RuntimeException(e); 309 } 310 } 311 312 Type getRootComponent(Type type) { 313 while (type.isArray()) 314 type = type.getComponent(); 315 316 return type; 317 } 318 319 private Type createArray(Type rootComponent, int dims) { 320 if (rootComponent instanceof MultiType) 321 return new MultiArrayType((MultiType) rootComponent, dims); 322 323 String name = arrayName(rootComponent.clazz.getName(), dims); 324 325 Type type; 326 try { 327 type = Type.get(getClassPool(rootComponent).get(name)); 328 } catch (NotFoundException e) { 329 throw new RuntimeException(e); 330 } 331 332 return type; 333 } 334 335 String arrayName(String component, int dims) { 336 // Using char[] since we have no StringBuilder in JDK4, and StringBuffer is slow. 337 // Although, this is more efficient even if we did have one. 338 int i = component.length(); 339 int size = i + dims * 2; 340 char[] string = new char[size]; 341 component.getChars(0, i, string, 0); 342 while (i < size) { 343 string[i++] = '['; 344 string[i++] = ']'; 345 } 346 component = new String(string); 347 return component; 348 } 349 350 private ClassPool getClassPool(Type rootComponent) { 351 ClassPool pool = rootComponent.clazz.getClassPool(); 352 return pool != null ? pool : ClassPool.getDefault(); 353 } 354 355 private Type mergeArray(Type type) { 356 Type typeRoot = getRootComponent(type); 357 Type thisRoot = getRootComponent(this); 358 int typeDims = type.getDimensions(); 359 int thisDims = this.getDimensions(); 360 361 // Array commponents can be merged when the dimensions are equal 362 if (typeDims == thisDims) { 363 Type mergedComponent = thisRoot.merge(typeRoot); 364 365 // If the components can not be merged (a primitive component mixed with a different type) 366 // then Object is the common type. 367 if (mergedComponent == Type.BOGUS) 368 return Type.OBJECT; 369 370 return createArray(mergedComponent, thisDims); 371 } 372 373 Type targetRoot; 374 int targetDims; 375 376 if (typeDims < thisDims) { 377 targetRoot = typeRoot; 378 targetDims = typeDims; 379 } else { 380 targetRoot = thisRoot; 381 targetDims = thisDims; 382 } 383 384 // Special case, arrays are cloneable and serializable, so prefer them when dimensions differ 385 if (eq(CLONEABLE.clazz, targetRoot.clazz) || eq(SERIALIZABLE.clazz, targetRoot.clazz)) 386 return createArray(targetRoot, targetDims); 387 388 return createArray(OBJECT, targetDims); 389 } 390 391 private static CtClass findCommonSuperClass(CtClass one, CtClass two) throws NotFoundException { 392 CtClass deep = one; 393 CtClass shallow = two; 394 CtClass backupShallow = shallow; 395 CtClass backupDeep = deep; 396 397 // Phase 1 - Find the deepest hierarchy, set deep and shallow correctly 398 for (;;) { 399 // In case we get lucky, and find a match early 400 if (eq(deep, shallow) && deep.getSuperclass() != null) 401 return deep; 402 403 CtClass deepSuper = deep.getSuperclass(); 404 CtClass shallowSuper = shallow.getSuperclass(); 405 406 if (shallowSuper == null) { 407 // right, now reset shallow 408 shallow = backupShallow; 409 break; 410 } 411 412 if (deepSuper == null) { 413 // wrong, swap them, since deep is now useless, its our tmp before we swap it 414 deep = backupDeep; 415 backupDeep = backupShallow; 416 backupShallow = deep; 417 418 deep = shallow; 419 shallow = backupShallow; 420 break; 421 } 422 423 deep = deepSuper; 424 shallow = shallowSuper; 425 } 426 427 // Phase 2 - Move deepBackup up by (deep end - deep) 428 for (;;) { 429 deep = deep.getSuperclass(); 430 if (deep == null) 431 break; 432 433 backupDeep = backupDeep.getSuperclass(); 434 } 435 436 deep = backupDeep; 437 438 // Phase 3 - The hierarchy positions are now aligned 439 // The common super class is easy to find now 440 while (!eq(deep, shallow)) { 441 deep = deep.getSuperclass(); 442 shallow = shallow.getSuperclass(); 443 } 444 445 return deep; 446 } 447 448 private Type mergeClasses(Type type) throws NotFoundException { 449 CtClass superClass = findCommonSuperClass(this.clazz, type.clazz); 450 451 // If its Object, then try and find a common interface(s) 452 if (superClass.getSuperclass() == null) { 453 Map interfaces = findCommonInterfaces(type); 454 if (interfaces.size() == 1) 455 return new Type((CtClass) interfaces.values().iterator().next()); 456 if (interfaces.size() > 1) 457 return new MultiType(interfaces); 458 459 // Only Object is in common 460 return new Type(superClass); 461 } 462 463 // Check for a common interface that is not on the found supertype 464 Map commonDeclared = findExclusiveDeclaredInterfaces(type, superClass); 465 if (commonDeclared.size() > 0) { 466 return new MultiType(commonDeclared, new Type(superClass)); 467 } 468 469 return new Type(superClass); 470 } 471 472 private Map findCommonInterfaces(Type type) { 473 Map typeMap = getAllInterfaces(type.clazz, null); 474 Map thisMap = getAllInterfaces(this.clazz, null); 475 476 return findCommonInterfaces(typeMap, thisMap); 477 } 478 479 private Map findExclusiveDeclaredInterfaces(Type type, CtClass exclude) { 480 Map typeMap = getDeclaredInterfaces(type.clazz, null); 481 Map thisMap = getDeclaredInterfaces(this.clazz, null); 482 Map excludeMap = getAllInterfaces(exclude, null); 483 484 Iterator i = excludeMap.keySet().iterator(); 485 while (i.hasNext()) { 486 Object intf = i.next(); 487 typeMap.remove(intf); 488 thisMap.remove(intf); 489 } 490 491 return findCommonInterfaces(typeMap, thisMap); 492 } 493 494 495 Map findCommonInterfaces(Map typeMap, Map alterMap) { 496 Iterator i = alterMap.keySet().iterator(); 497 while (i.hasNext()) { 498 if (! typeMap.containsKey(i.next())) 499 i.remove(); 500 } 501 502 // Reduce to subinterfaces 503 // This does not need to be recursive since we make a copy, 504 // and that copy contains all super types for the whole hierarchy 505 i = new ArrayList(alterMap.values()).iterator(); 506 while (i.hasNext()) { 507 CtClass intf = (CtClass) i.next(); 508 CtClass[] interfaces; 509 try { 510 interfaces = intf.getInterfaces(); 511 } catch (NotFoundException e) { 512 throw new RuntimeException(e); 513 } 514 515 for (int c = 0; c < interfaces.length; c++) 516 alterMap.remove(interfaces[c].getName()); 517 } 518 519 return alterMap; 520 } 521 522 Map getAllInterfaces(CtClass clazz, Map map) { 523 if (map == null) 524 map = new HashMap(); 525 526 if (clazz.isInterface()) 527 map.put(clazz.getName(), clazz); 528 do { 529 try { 530 CtClass[] interfaces = clazz.getInterfaces(); 531 for (int i = 0; i < interfaces.length; i++) { 532 CtClass intf = interfaces[i]; 533 map.put(intf.getName(), intf); 534 getAllInterfaces(intf, map); 535 } 536 537 clazz = clazz.getSuperclass(); 538 } catch (NotFoundException e) { 539 throw new RuntimeException(e); 540 } 541 } while (clazz != null); 542 543 return map; 544 } 545 546 Map getDeclaredInterfaces(CtClass clazz, Map map) { 547 if (map == null) 548 map = new HashMap(); 549 550 if (clazz.isInterface()) 551 map.put(clazz.getName(), clazz); 552 553 CtClass[] interfaces; 554 try { 555 interfaces = clazz.getInterfaces(); 556 } catch (NotFoundException e) { 557 throw new RuntimeException(e); 558 } 559 560 for (int i = 0; i < interfaces.length; i++) { 561 CtClass intf = interfaces[i]; 562 map.put(intf.getName(), intf); 563 getDeclaredInterfaces(intf, map); 564 } 565 566 return map; 567 } 568 569 public boolean equals(Object o) { 570 if (! (o instanceof Type)) 571 return false; 572 573 return o.getClass() == getClass() && eq(clazz, ((Type)o).clazz); 574 } 575 576 static boolean eq(CtClass one, CtClass two) { 577 return one == two || (one != null && two != null && one.getName().equals(two.getName())); 578 } 579 580 public String toString() { 581 if (this == BOGUS) 582 return "BOGUS"; 583 if (this == UNINIT) 584 return "UNINIT"; 585 if (this == RETURN_ADDRESS) 586 return "RETURN ADDRESS"; 587 if (this == TOP) 588 return "TOP"; 589 590 return clazz == null ? "null" : clazz.getName(); 591 } 592} 593