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