001/* 002 * Copyright (C) 2009 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.reflect; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019import static com.google.common.base.Preconditions.checkState; 020import static java.util.Arrays.asList; 021 022import com.google.common.base.Joiner; 023import com.google.common.base.Objects; 024import com.google.common.collect.ImmutableMap; 025import com.google.common.collect.Maps; 026import java.lang.reflect.GenericArrayType; 027import java.lang.reflect.ParameterizedType; 028import java.lang.reflect.Type; 029import java.lang.reflect.TypeVariable; 030import java.lang.reflect.WildcardType; 031import java.util.Arrays; 032import java.util.LinkedHashSet; 033import java.util.Map; 034import java.util.Map.Entry; 035import java.util.Set; 036import java.util.concurrent.atomic.AtomicInteger; 037import javax.annotation.CheckForNull; 038 039/** 040 * An object of this class encapsulates type mappings from type variables. Mappings are established 041 * with {@link #where} and types are resolved using {@link #resolveType}. 042 * 043 * <p>Note that usually type mappings are already implied by the static type hierarchy (for example, 044 * the {@code E} type variable declared by class {@code List} naturally maps to {@code String} in 045 * the context of {@code class MyStringList implements List<String>}. In such case, prefer to use 046 * {@link TypeToken#resolveType} since it's simpler and more type safe. This class should only be 047 * used when the type mapping isn't implied by the static type hierarchy, but provided through other 048 * means such as an annotation or external configuration file. 049 * 050 * @author Ben Yu 051 * @since 15.0 052 */ 053@ElementTypesAreNonnullByDefault 054public final class TypeResolver { 055 056 private final TypeTable typeTable; 057 058 public TypeResolver() { 059 this.typeTable = new TypeTable(); 060 } 061 062 private TypeResolver(TypeTable typeTable) { 063 this.typeTable = typeTable; 064 } 065 066 /** 067 * Returns a resolver that resolves types "covariantly". 068 * 069 * <p>For example, when resolving {@code List<T>} in the context of {@code ArrayList<?>}, {@code 070 * <T>} is covariantly resolved to {@code <?>} such that return type of {@code List::get} is 071 * {@code <?>}. 072 */ 073 static TypeResolver covariantly(Type contextType) { 074 return new TypeResolver().where(TypeMappingIntrospector.getTypeMappings(contextType)); 075 } 076 077 /** 078 * Returns a resolver that resolves types "invariantly". 079 * 080 * <p>For example, when resolving {@code List<T>} in the context of {@code ArrayList<?>}, {@code 081 * <T>} cannot be invariantly resolved to {@code <?>} because otherwise the parameter type of 082 * {@code List::set} will be {@code <?>} and it'll falsely say any object can be passed into 083 * {@code ArrayList<?>::set}. 084 * 085 * <p>Instead, {@code <?>} will be resolved to a capture in the form of a type variable {@code 086 * <capture-of-? extends Object>}, effectively preventing {@code set} from accepting any type. 087 */ 088 static TypeResolver invariantly(Type contextType) { 089 Type invariantContext = WildcardCapturer.INSTANCE.capture(contextType); 090 return new TypeResolver().where(TypeMappingIntrospector.getTypeMappings(invariantContext)); 091 } 092 093 /** 094 * Returns a new {@code TypeResolver} with type variables in {@code formal} mapping to types in 095 * {@code actual}. 096 * 097 * <p>For example, if {@code formal} is a {@code TypeVariable T}, and {@code actual} is {@code 098 * String.class}, then {@code new TypeResolver().where(formal, actual)} will {@linkplain 099 * #resolveType resolve} {@code ParameterizedType List<T>} to {@code List<String>}, and resolve 100 * {@code Map<T, Something>} to {@code Map<String, Something>} etc. Similarly, {@code formal} and 101 * {@code actual} can be {@code Map<K, V>} and {@code Map<String, Integer>} respectively, or they 102 * can be {@code E[]} and {@code String[]} respectively, or even any arbitrary combination 103 * thereof. 104 * 105 * @param formal The type whose type variables or itself is mapped to other type(s). It's almost 106 * always a bug if {@code formal} isn't a type variable and contains no type variable. Make 107 * sure you are passing the two parameters in the right order. 108 * @param actual The type that the formal type variable(s) are mapped to. It can be or contain yet 109 * other type variables, in which case these type variables will be further resolved if 110 * corresponding mappings exist in the current {@code TypeResolver} instance. 111 */ 112 public TypeResolver where(Type formal, Type actual) { 113 Map<TypeVariableKey, Type> mappings = Maps.newHashMap(); 114 populateTypeMappings(mappings, checkNotNull(formal), checkNotNull(actual)); 115 return where(mappings); 116 } 117 118 /** Returns a new {@code TypeResolver} with {@code variable} mapping to {@code type}. */ 119 TypeResolver where(Map<TypeVariableKey, ? extends Type> mappings) { 120 return new TypeResolver(typeTable.where(mappings)); 121 } 122 123 private static void populateTypeMappings( 124 Map<TypeVariableKey, Type> mappings, Type from, Type to) { 125 if (from.equals(to)) { 126 return; 127 } 128 new TypeVisitor() { 129 @Override 130 void visitTypeVariable(TypeVariable<?> typeVariable) { 131 mappings.put(new TypeVariableKey(typeVariable), to); 132 } 133 134 @Override 135 void visitWildcardType(WildcardType fromWildcardType) { 136 if (!(to instanceof WildcardType)) { 137 return; // okay to say <?> is anything 138 } 139 WildcardType toWildcardType = (WildcardType) to; 140 Type[] fromUpperBounds = fromWildcardType.getUpperBounds(); 141 Type[] toUpperBounds = toWildcardType.getUpperBounds(); 142 Type[] fromLowerBounds = fromWildcardType.getLowerBounds(); 143 Type[] toLowerBounds = toWildcardType.getLowerBounds(); 144 checkArgument( 145 fromUpperBounds.length == toUpperBounds.length 146 && fromLowerBounds.length == toLowerBounds.length, 147 "Incompatible type: %s vs. %s", 148 fromWildcardType, 149 to); 150 for (int i = 0; i < fromUpperBounds.length; i++) { 151 populateTypeMappings(mappings, fromUpperBounds[i], toUpperBounds[i]); 152 } 153 for (int i = 0; i < fromLowerBounds.length; i++) { 154 populateTypeMappings(mappings, fromLowerBounds[i], toLowerBounds[i]); 155 } 156 } 157 158 @Override 159 void visitParameterizedType(ParameterizedType fromParameterizedType) { 160 if (to instanceof WildcardType) { 161 return; // Okay to say Foo<A> is <?> 162 } 163 ParameterizedType toParameterizedType = expectArgument(ParameterizedType.class, to); 164 if (fromParameterizedType.getOwnerType() != null 165 && toParameterizedType.getOwnerType() != null) { 166 populateTypeMappings( 167 mappings, fromParameterizedType.getOwnerType(), toParameterizedType.getOwnerType()); 168 } 169 checkArgument( 170 fromParameterizedType.getRawType().equals(toParameterizedType.getRawType()), 171 "Inconsistent raw type: %s vs. %s", 172 fromParameterizedType, 173 to); 174 Type[] fromArgs = fromParameterizedType.getActualTypeArguments(); 175 Type[] toArgs = toParameterizedType.getActualTypeArguments(); 176 checkArgument( 177 fromArgs.length == toArgs.length, 178 "%s not compatible with %s", 179 fromParameterizedType, 180 toParameterizedType); 181 for (int i = 0; i < fromArgs.length; i++) { 182 populateTypeMappings(mappings, fromArgs[i], toArgs[i]); 183 } 184 } 185 186 @Override 187 void visitGenericArrayType(GenericArrayType fromArrayType) { 188 if (to instanceof WildcardType) { 189 return; // Okay to say A[] is <?> 190 } 191 Type componentType = Types.getComponentType(to); 192 checkArgument(componentType != null, "%s is not an array type.", to); 193 populateTypeMappings(mappings, fromArrayType.getGenericComponentType(), componentType); 194 } 195 196 @Override 197 void visitClass(Class<?> fromClass) { 198 if (to instanceof WildcardType) { 199 return; // Okay to say Foo is <?> 200 } 201 // Can't map from a raw class to anything other than itself or a wildcard. 202 // You can't say "assuming String is Integer". 203 // And we don't support "assuming String is T"; user has to say "assuming T is String". 204 throw new IllegalArgumentException("No type mapping from " + fromClass + " to " + to); 205 } 206 }.visit(from); 207 } 208 209 /** 210 * Resolves all type variables in {@code type} and all downstream types and returns a 211 * corresponding type with type variables resolved. 212 */ 213 public Type resolveType(Type type) { 214 checkNotNull(type); 215 if (type instanceof TypeVariable) { 216 return typeTable.resolve((TypeVariable<?>) type); 217 } else if (type instanceof ParameterizedType) { 218 return resolveParameterizedType((ParameterizedType) type); 219 } else if (type instanceof GenericArrayType) { 220 return resolveGenericArrayType((GenericArrayType) type); 221 } else if (type instanceof WildcardType) { 222 return resolveWildcardType((WildcardType) type); 223 } else { 224 // if Class<?>, no resolution needed, we are done. 225 return type; 226 } 227 } 228 229 Type[] resolveTypesInPlace(Type[] types) { 230 for (int i = 0; i < types.length; i++) { 231 types[i] = resolveType(types[i]); 232 } 233 return types; 234 } 235 236 private Type[] resolveTypes(Type[] types) { 237 Type[] result = new Type[types.length]; 238 for (int i = 0; i < types.length; i++) { 239 result[i] = resolveType(types[i]); 240 } 241 return result; 242 } 243 244 private WildcardType resolveWildcardType(WildcardType type) { 245 Type[] lowerBounds = type.getLowerBounds(); 246 Type[] upperBounds = type.getUpperBounds(); 247 return new Types.WildcardTypeImpl(resolveTypes(lowerBounds), resolveTypes(upperBounds)); 248 } 249 250 private Type resolveGenericArrayType(GenericArrayType type) { 251 Type componentType = type.getGenericComponentType(); 252 Type resolvedComponentType = resolveType(componentType); 253 return Types.newArrayType(resolvedComponentType); 254 } 255 256 private ParameterizedType resolveParameterizedType(ParameterizedType type) { 257 Type owner = type.getOwnerType(); 258 Type resolvedOwner = (owner == null) ? null : resolveType(owner); 259 Type resolvedRawType = resolveType(type.getRawType()); 260 261 Type[] args = type.getActualTypeArguments(); 262 Type[] resolvedArgs = resolveTypes(args); 263 return Types.newParameterizedTypeWithOwner( 264 resolvedOwner, (Class<?>) resolvedRawType, resolvedArgs); 265 } 266 267 private static <T> T expectArgument(Class<T> type, Object arg) { 268 try { 269 return type.cast(arg); 270 } catch (ClassCastException e) { 271 throw new IllegalArgumentException(arg + " is not a " + type.getSimpleName()); 272 } 273 } 274 275 /** A TypeTable maintains mapping from {@link TypeVariable} to types. */ 276 private static class TypeTable { 277 private final ImmutableMap<TypeVariableKey, Type> map; 278 279 TypeTable() { 280 this.map = ImmutableMap.of(); 281 } 282 283 private TypeTable(ImmutableMap<TypeVariableKey, Type> map) { 284 this.map = map; 285 } 286 287 /** Returns a new {@code TypeResolver} with {@code variable} mapping to {@code type}. */ 288 final TypeTable where(Map<TypeVariableKey, ? extends Type> mappings) { 289 ImmutableMap.Builder<TypeVariableKey, Type> builder = ImmutableMap.builder(); 290 builder.putAll(map); 291 for (Entry<TypeVariableKey, ? extends Type> mapping : mappings.entrySet()) { 292 TypeVariableKey variable = mapping.getKey(); 293 Type type = mapping.getValue(); 294 checkArgument(!variable.equalsType(type), "Type variable %s bound to itself", variable); 295 builder.put(variable, type); 296 } 297 return new TypeTable(builder.buildOrThrow()); 298 } 299 300 final Type resolve(TypeVariable<?> var) { 301 TypeTable unguarded = this; 302 TypeTable guarded = 303 new TypeTable() { 304 @Override 305 public Type resolveInternal(TypeVariable<?> intermediateVar, TypeTable forDependent) { 306 if (intermediateVar.getGenericDeclaration().equals(var.getGenericDeclaration())) { 307 return intermediateVar; 308 } 309 return unguarded.resolveInternal(intermediateVar, forDependent); 310 } 311 }; 312 return resolveInternal(var, guarded); 313 } 314 315 /** 316 * Resolves {@code var} using the encapsulated type mapping. If it maps to yet another 317 * non-reified type or has bounds, {@code forDependants} is used to do further resolution, which 318 * doesn't try to resolve any type variable on generic declarations that are already being 319 * resolved. 320 * 321 * <p>Should only be called and overridden by {@link #resolve(TypeVariable)}. 322 */ 323 Type resolveInternal(TypeVariable<?> var, TypeTable forDependants) { 324 Type type = map.get(new TypeVariableKey(var)); 325 if (type == null) { 326 Type[] bounds = var.getBounds(); 327 if (bounds.length == 0) { 328 return var; 329 } 330 Type[] resolvedBounds = new TypeResolver(forDependants).resolveTypes(bounds); 331 /* 332 * We'd like to simply create our own TypeVariable with the newly resolved bounds. There's 333 * just one problem: Starting with JDK 7u51, the JDK TypeVariable's equals() method doesn't 334 * recognize instances of our TypeVariable implementation. This is a problem because users 335 * compare TypeVariables from the JDK against TypeVariables returned by TypeResolver. To 336 * work with all JDK versions, TypeResolver must return the appropriate TypeVariable 337 * implementation in each of the three possible cases: 338 * 339 * 1. Prior to JDK 7u51, the JDK TypeVariable implementation interoperates with ours. 340 * Therefore, we can always create our own TypeVariable. 341 * 342 * 2. Starting with JDK 7u51, the JDK TypeVariable implementations does not interoperate 343 * with ours. Therefore, we have to be careful about whether we create our own TypeVariable: 344 * 345 * 2a. If the resolved types are identical to the original types, then we can return the 346 * original, identical JDK TypeVariable. By doing so, we sidestep the problem entirely. 347 * 348 * 2b. If the resolved types are different from the original types, things are trickier. The 349 * only way to get a TypeVariable instance for the resolved types is to create our own. The 350 * created TypeVariable will not interoperate with any JDK TypeVariable. But this is OK: We 351 * don't _want_ our new TypeVariable to be equal to the JDK TypeVariable because it has 352 * _different bounds_ than the JDK TypeVariable. And it wouldn't make sense for our new 353 * TypeVariable to be equal to any _other_ JDK TypeVariable, either, because any other JDK 354 * TypeVariable must have a different declaration or name. The only TypeVariable that our 355 * new TypeVariable _will_ be equal to is an equivalent TypeVariable that was also created 356 * by us. And that equality is guaranteed to hold because it doesn't involve the JDK 357 * TypeVariable implementation at all. 358 */ 359 if (Types.NativeTypeVariableEquals.NATIVE_TYPE_VARIABLE_ONLY 360 && Arrays.equals(bounds, resolvedBounds)) { 361 return var; 362 } 363 return Types.newArtificialTypeVariable( 364 var.getGenericDeclaration(), var.getName(), resolvedBounds); 365 } 366 // in case the type is yet another type variable. 367 return new TypeResolver(forDependants).resolveType(type); 368 } 369 } 370 371 private static final class TypeMappingIntrospector extends TypeVisitor { 372 373 private final Map<TypeVariableKey, Type> mappings = Maps.newHashMap(); 374 375 /** 376 * Returns type mappings using type parameters and type arguments found in the generic 377 * superclass and the super interfaces of {@code contextClass}. 378 */ 379 static ImmutableMap<TypeVariableKey, Type> getTypeMappings(Type contextType) { 380 checkNotNull(contextType); 381 TypeMappingIntrospector introspector = new TypeMappingIntrospector(); 382 introspector.visit(contextType); 383 return ImmutableMap.copyOf(introspector.mappings); 384 } 385 386 @Override 387 void visitClass(Class<?> clazz) { 388 visit(clazz.getGenericSuperclass()); 389 visit(clazz.getGenericInterfaces()); 390 } 391 392 @Override 393 void visitParameterizedType(ParameterizedType parameterizedType) { 394 Class<?> rawClass = (Class<?>) parameterizedType.getRawType(); 395 TypeVariable<?>[] vars = rawClass.getTypeParameters(); 396 Type[] typeArgs = parameterizedType.getActualTypeArguments(); 397 checkState(vars.length == typeArgs.length); 398 for (int i = 0; i < vars.length; i++) { 399 map(new TypeVariableKey(vars[i]), typeArgs[i]); 400 } 401 visit(rawClass); 402 visit(parameterizedType.getOwnerType()); 403 } 404 405 @Override 406 void visitTypeVariable(TypeVariable<?> t) { 407 visit(t.getBounds()); 408 } 409 410 @Override 411 void visitWildcardType(WildcardType t) { 412 visit(t.getUpperBounds()); 413 } 414 415 private void map(TypeVariableKey var, Type arg) { 416 if (mappings.containsKey(var)) { 417 // Mapping already established 418 // This is possible when following both superClass -> enclosingClass 419 // and enclosingclass -> superClass paths. 420 // Since we follow the path of superclass first, enclosing second, 421 // superclass mapping should take precedence. 422 return; 423 } 424 // First, check whether var -> arg forms a cycle 425 for (Type t = arg; t != null; t = mappings.get(TypeVariableKey.forLookup(t))) { 426 if (var.equalsType(t)) { 427 // cycle detected, remove the entire cycle from the mapping so that 428 // each type variable resolves deterministically to itself. 429 // Otherwise, a F -> T cycle will end up resolving both F and T 430 // nondeterministically to either F or T. 431 for (Type x = arg; x != null; x = mappings.remove(TypeVariableKey.forLookup(x))) {} 432 return; 433 } 434 } 435 mappings.put(var, arg); 436 } 437 } 438 439 // This is needed when resolving types against a context with wildcards 440 // For example: 441 // class Holder<T> { 442 // void set(T data) {...} 443 // } 444 // Holder<List<?>> should *not* resolve the set() method to set(List<?> data). 445 // Instead, it should create a capture of the wildcard so that set() rejects any List<T>. 446 private static class WildcardCapturer { 447 448 static final WildcardCapturer INSTANCE = new WildcardCapturer(); 449 450 private final AtomicInteger id; 451 452 private WildcardCapturer() { 453 this(new AtomicInteger()); 454 } 455 456 private WildcardCapturer(AtomicInteger id) { 457 this.id = id; 458 } 459 460 final Type capture(Type type) { 461 checkNotNull(type); 462 if (type instanceof Class) { 463 return type; 464 } 465 if (type instanceof TypeVariable) { 466 return type; 467 } 468 if (type instanceof GenericArrayType) { 469 GenericArrayType arrayType = (GenericArrayType) type; 470 return Types.newArrayType( 471 notForTypeVariable().capture(arrayType.getGenericComponentType())); 472 } 473 if (type instanceof ParameterizedType) { 474 ParameterizedType parameterizedType = (ParameterizedType) type; 475 Class<?> rawType = (Class<?>) parameterizedType.getRawType(); 476 TypeVariable<?>[] typeVars = rawType.getTypeParameters(); 477 Type[] typeArgs = parameterizedType.getActualTypeArguments(); 478 for (int i = 0; i < typeArgs.length; i++) { 479 typeArgs[i] = forTypeVariable(typeVars[i]).capture(typeArgs[i]); 480 } 481 return Types.newParameterizedTypeWithOwner( 482 notForTypeVariable().captureNullable(parameterizedType.getOwnerType()), 483 rawType, 484 typeArgs); 485 } 486 if (type instanceof WildcardType) { 487 WildcardType wildcardType = (WildcardType) type; 488 Type[] lowerBounds = wildcardType.getLowerBounds(); 489 if (lowerBounds.length == 0) { // ? extends something changes to capture-of 490 return captureAsTypeVariable(wildcardType.getUpperBounds()); 491 } else { 492 // TODO(benyu): handle ? super T somehow. 493 return type; 494 } 495 } 496 throw new AssertionError("must have been one of the known types"); 497 } 498 499 TypeVariable<?> captureAsTypeVariable(Type[] upperBounds) { 500 String name = 501 "capture#" + id.incrementAndGet() + "-of ? extends " + Joiner.on('&').join(upperBounds); 502 return Types.newArtificialTypeVariable(WildcardCapturer.class, name, upperBounds); 503 } 504 505 private WildcardCapturer forTypeVariable(TypeVariable<?> typeParam) { 506 return new WildcardCapturer(id) { 507 @Override 508 TypeVariable<?> captureAsTypeVariable(Type[] upperBounds) { 509 Set<Type> combined = new LinkedHashSet<>(asList(upperBounds)); 510 // Since this is an artificially generated type variable, we don't bother checking 511 // subtyping between declared type bound and actual type bound. So it's possible that we 512 // may generate something like <capture#1-of ? extends Foo&SubFoo>. 513 // Checking subtype between declared and actual type bounds 514 // adds recursive isSubtypeOf() call and feels complicated. 515 // There is no contract one way or another as long as isSubtypeOf() works as expected. 516 combined.addAll(asList(typeParam.getBounds())); 517 if (combined.size() > 1) { // Object is implicit and only useful if it's the only bound. 518 combined.remove(Object.class); 519 } 520 return super.captureAsTypeVariable(combined.toArray(new Type[0])); 521 } 522 }; 523 } 524 525 private WildcardCapturer notForTypeVariable() { 526 return new WildcardCapturer(id); 527 } 528 529 @CheckForNull 530 private Type captureNullable(@CheckForNull Type type) { 531 if (type == null) { 532 return null; 533 } 534 return capture(type); 535 } 536 } 537 538 /** 539 * Wraps around {@code TypeVariable<?>} to ensure that any two type variables are equal as long as 540 * they are declared by the same {@link java.lang.reflect.GenericDeclaration} and have the same 541 * name, even if their bounds differ. 542 * 543 * <p>While resolving a type variable from a {@code var -> type} map, we don't care whether the 544 * type variable's bound has been partially resolved. As long as the type variable "identity" 545 * matches. 546 * 547 * <p>On the other hand, if for example we are resolving {@code List<A extends B>} to {@code 548 * List<A extends String>}, we need to compare that {@code <A extends B>} is unequal to {@code <A 549 * extends String>} in order to decide to use the transformed type instead of the original type. 550 */ 551 static final class TypeVariableKey { 552 private final TypeVariable<?> var; 553 554 TypeVariableKey(TypeVariable<?> var) { 555 this.var = checkNotNull(var); 556 } 557 558 @Override 559 public int hashCode() { 560 return Objects.hashCode(var.getGenericDeclaration(), var.getName()); 561 } 562 563 @Override 564 public boolean equals(@CheckForNull Object obj) { 565 if (obj instanceof TypeVariableKey) { 566 TypeVariableKey that = (TypeVariableKey) obj; 567 return equalsTypeVariable(that.var); 568 } else { 569 return false; 570 } 571 } 572 573 @Override 574 public String toString() { 575 return var.toString(); 576 } 577 578 /** Wraps {@code t} in a {@code TypeVariableKey} if it's a type variable. */ 579 @CheckForNull 580 static TypeVariableKey forLookup(Type t) { 581 if (t instanceof TypeVariable) { 582 return new TypeVariableKey((TypeVariable<?>) t); 583 } else { 584 return null; 585 } 586 } 587 588 /** 589 * Returns true if {@code type} is a {@code TypeVariable} with the same name and declared by the 590 * same {@code GenericDeclaration}. 591 */ 592 boolean equalsType(Type type) { 593 if (type instanceof TypeVariable) { 594 return equalsTypeVariable((TypeVariable<?>) type); 595 } else { 596 return false; 597 } 598 } 599 600 private boolean equalsTypeVariable(TypeVariable<?> that) { 601 return var.getGenericDeclaration().equals(that.getGenericDeclaration()) 602 && var.getName().equals(that.getName()); 603 } 604 } 605}