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