001/*
002 * Copyright (C) 2006 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.reflect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.base.Preconditions.checkState;
022
023import com.google.common.annotations.Beta;
024import com.google.common.annotations.VisibleForTesting;
025import com.google.common.base.Predicate;
026import com.google.common.collect.FluentIterable;
027import com.google.common.collect.ForwardingSet;
028import com.google.common.collect.ImmutableList;
029import com.google.common.collect.ImmutableMap;
030import com.google.common.collect.ImmutableSet;
031import com.google.common.collect.Maps;
032import com.google.common.collect.Ordering;
033
034import java.io.Serializable;
035import java.lang.reflect.GenericArrayType;
036import java.lang.reflect.ParameterizedType;
037import java.lang.reflect.Type;
038import java.lang.reflect.TypeVariable;
039import java.lang.reflect.WildcardType;
040import java.util.Arrays;
041import java.util.Comparator;
042import java.util.Map;
043import java.util.Set;
044
045import javax.annotation.Nullable;
046
047/**
048 * A {@link Type} with generics.
049 *
050 * <p>Operations that are otherwise only available in {@link Class} are implemented to support
051 * {@code Type}, for example {@link #isAssignableFrom}, {@link #isArray} and {@link
052 * #getComponentType}. It also provides additional utilities such as {@link #getTypes} and {@link
053 * #resolveType} etc.
054 *
055 * <p>There are three ways to get a {@code TypeToken} instance: <ul>
056 * <li>Wrap a {@code Type} obtained via reflection. For example: {@code
057 * TypeToken.of(method.getGenericReturnType())}.
058 * <li>Capture a generic type with a (usually anonymous) subclass. For example: <pre>   {@code
059 *
060 *   new TypeToken<List<String>>() {}
061 * }</pre>
062 * Note that it's critical that the actual type argument is carried by a subclass.
063 * The following code is wrong because it only captures the {@code <T>} type variable
064 * of the {@code listType()} method signature; while {@code <String>} is lost in erasure:
065 * <pre>   {@code
066 *
067 *   class Util {
068 *     static <T> TypeToken<List<T>> listType() {
069 *       return new TypeToken<List<T>>() {};
070 *     }
071 *   }
072 *
073 *   TypeToken<List<String>> stringListType = Util.<String>listType();
074 * }</pre>
075 * <li>Capture a generic type with a (usually anonymous) subclass and resolve it against
076 * a context class that knows what the type parameters are. For example: <pre>   {@code
077 *   abstract class IKnowMyType<T> {
078 *     TypeToken<T> type = new TypeToken<T>(getClass()) {};
079 *   }
080 *   new IKnowMyType<String>() {}.type => String
081 * }</pre>
082 * </ul>
083 *
084 * <p>{@code TypeToken} is serializable when no type variable is contained in the type.
085 *
086 * <p>Note to Guice users: {@code} TypeToken is similar to Guice's {@code TypeLiteral} class,
087 * but with one important difference: it supports non-reified types such as {@code T},
088 * {@code List<T>} or even {@code List<? extends Number>}; while TypeLiteral does not.
089 * TypeToken is also serializable and offers numerous additional utility methods.
090 *
091 * @author Bob Lee
092 * @author Sven Mawson
093 * @author Ben Yu
094 * @since 12.0
095 */
096@Beta
097@SuppressWarnings("serial") // SimpleTypeToken is the serialized form.
098public abstract class TypeToken<T> extends TypeCapture<T> implements Serializable {
099
100  private final Type runtimeType;
101
102  /** Resolver for resolving types with {@link #runtimeType} as context. */
103  private transient TypeResolver typeResolver;
104
105  /**
106   * Constructs a new type token of {@code T}.
107   *
108   * <p>Clients create an empty anonymous subclass. Doing so embeds the type
109   * parameter in the anonymous class's type hierarchy so we can reconstitute
110   * it at runtime despite erasure.
111   *
112   * <p>For example: <pre>   {@code
113   *
114   *   TypeToken<List<String>> t = new TypeToken<List<String>>() {};
115   * }</pre>
116   */
117  protected TypeToken() {
118    this.runtimeType = capture();
119    checkState(!(runtimeType instanceof TypeVariable),
120        "Cannot construct a TypeToken for a type variable.\n" +
121        "You probably meant to call new TypeToken<%s>(getClass()) " +
122        "that can resolve the type variable for you.\n" +
123        "If you do need to create a TypeToken of a type variable, " +
124        "please use TypeToken.of() instead.", runtimeType);
125  }
126
127  /**
128   * Constructs a new type token of {@code T} while resolving free type variables in the context of
129   * {@code declaringClass}.
130   *
131   * <p>Clients create an empty anonymous subclass. Doing so embeds the type
132   * parameter in the anonymous class's type hierarchy so we can reconstitute
133   * it at runtime despite erasure.
134   *
135   * <p>For example: <pre>   {@code
136   *
137   *   abstract class IKnowMyType<T> {
138   *     TypeToken<T> getMyType() {
139   *       return new TypeToken<T>(getClass()) {};
140   *     }
141   *   }
142   *
143   *   new IKnowMyType<String>() {}.getMyType() => String
144   * }</pre>
145   */
146  protected TypeToken(Class<?> declaringClass) {
147    Type captured = super.capture();
148    if (captured instanceof Class) {
149      this.runtimeType = captured;
150    } else {
151      this.runtimeType = of(declaringClass).resolveType(captured).runtimeType;
152    }
153  }
154
155  private TypeToken(Type type) {
156    this.runtimeType = checkNotNull(type);
157  }
158
159  /** Returns an instance of type token that wraps {@code type}. */
160  public static <T> TypeToken<T> of(Class<T> type) {
161    return new SimpleTypeToken<T>(type);
162  }
163
164  /** Returns an instance of type token that wraps {@code type}. */
165  public static TypeToken<?> of(Type type) {
166    return new SimpleTypeToken<Object>(type);
167  }
168
169  /**
170   * Returns the raw type of {@code T}. Formally speaking, if {@code T} is returned by
171   * {@link java.lang.reflect.Method#getGenericReturnType}, the raw type is what's returned by
172   * {@link java.lang.reflect.Method#getReturnType} of the same method object. Specifically:
173   * <ul>
174   * <li>If {@code T} is a {@code Class} itself, {@code T} itself is returned.
175   * <li>If {@code T} is a {@link ParameterizedType}, the raw type of the parameterized type is
176   *     returned.
177   * <li>If {@code T} is a {@link GenericArrayType}, the returned type is the corresponding array
178   *     class. For example: {@code List<Integer>[] => List[]}.
179   * <li>If {@code T} is a type variable or a wildcard type, the raw type of the first upper bound
180   *     is returned. For example: {@code <X extends Foo> => Foo}.
181   * </ul>
182   */
183  public final Class<? super T> getRawType() {
184    Class<?> rawType = getRawType(runtimeType);
185    @SuppressWarnings("unchecked") // raw type is |T|
186    Class<? super T> result = (Class<? super T>) rawType;
187    return result;
188  }
189
190  /**
191   * Returns the raw type of the class or parameterized type; if {@code T} is type variable or
192   * wildcard type, the raw types of all its upper bounds are returned.
193   */
194  private ImmutableSet<Class<? super T>> getImmediateRawTypes() {
195    // Cast from ImmutableSet<Class<?>> to ImmutableSet<Class<? super T>>
196    @SuppressWarnings({"unchecked", "rawtypes"})
197    ImmutableSet<Class<? super T>> result = (ImmutableSet) getRawTypes(runtimeType);
198    return result;
199  }
200
201  /** Returns the represented type. */
202  public final Type getType() {
203    return runtimeType;
204  }
205
206  /**
207   * Returns a new {@code TypeToken} where type variables represented by {@code typeParam}
208   * are substituted by {@code typeArg}. For example, it can be used to construct
209   * {@code Map<K, V>} for any {@code K} and {@code V} type: <pre>   {@code
210   *
211   *   static <K, V> TypeToken<Map<K, V>> mapOf(
212   *       TypeToken<K> keyType, TypeToken<V> valueType) {
213   *     return new TypeToken<Map<K, V>>() {}
214   *         .where(new TypeParameter<K>() {}, keyType)
215   *         .where(new TypeParameter<V>() {}, valueType);
216   *   }
217   * }</pre>
218   *
219   * @param <X> The parameter type
220   * @param typeParam the parameter type variable
221   * @param typeArg the actual type to substitute
222   */
223  public final <X> TypeToken<T> where(TypeParameter<X> typeParam, TypeToken<X> typeArg) {
224    TypeResolver resolver = new TypeResolver()
225        .where(ImmutableMap.of(typeParam.typeVariable, typeArg.runtimeType));
226    // If there's any type error, we'd report now rather than later.
227    return new SimpleTypeToken<T>(resolver.resolveType(runtimeType));
228  }
229
230  /**
231   * Returns a new {@code TypeToken} where type variables represented by {@code typeParam}
232   * are substituted by {@code typeArg}. For example, it can be used to construct
233   * {@code Map<K, V>} for any {@code K} and {@code V} type: <pre>   {@code
234   *
235   *   static <K, V> TypeToken<Map<K, V>> mapOf(
236   *       Class<K> keyType, Class<V> valueType) {
237   *     return new TypeToken<Map<K, V>>() {}
238   *         .where(new TypeParameter<K>() {}, keyType)
239   *         .where(new TypeParameter<V>() {}, valueType);
240   *   }
241   * }</pre>
242   *
243   * @param <X> The parameter type
244   * @param typeParam the parameter type variable
245   * @param typeArg the actual type to substitute
246   */
247  public final <X> TypeToken<T> where(TypeParameter<X> typeParam, Class<X> typeArg) {
248    return where(typeParam, of(typeArg));
249  }
250
251  /**
252   * Resolves the given {@code type} against the type context represented by this type.
253   * For example: <pre>   {@code
254   *
255   *   new TypeToken<List<String>>() {}.resolveType(
256   *       List.class.getMethod("get", int.class).getGenericReturnType())
257   *   => String.class
258   * }</pre>
259   */
260  public final TypeToken<?> resolveType(Type type) {
261    checkNotNull(type);
262    TypeResolver resolver = typeResolver;
263    if (resolver == null) {
264      resolver = (typeResolver = TypeResolver.accordingTo(runtimeType));
265    }
266    return of(resolver.resolveType(type));
267  }
268
269  private TypeToken<?> resolveSupertype(Type type) {
270    TypeToken<?> supertype = resolveType(type);
271    // super types' type mapping is a subset of type mapping of this type.
272    supertype.typeResolver = typeResolver;
273    return supertype;
274  }
275
276  /**
277   * Returns the generic superclass of this type or {@code null} if the type represents
278   * {@link Object} or an interface. This method is similar but different from {@link
279   * Class#getGenericSuperclass}. For example, {@code
280   * new TypeToken<StringArrayList>() {}.getGenericSuperclass()} will return {@code
281   * new TypeToken<ArrayList<String>>() {}}; while {@code
282   * StringArrayList.class.getGenericSuperclass()} will return {@code ArrayList<E>}, where {@code E}
283   * is the type variable declared by class {@code ArrayList}.
284   *
285   * <p>If this type is a type variable or wildcard, its first upper bound is examined and returned
286   * if the bound is a class or extends from a class. This means that the returned type could be a
287   * type variable too.
288   */
289  @Nullable
290  final TypeToken<? super T> getGenericSuperclass() {
291    if (runtimeType instanceof TypeVariable) {
292      // First bound is always the super class, if one exists.
293      return boundAsSuperclass(((TypeVariable<?>) runtimeType).getBounds()[0]);
294    }
295    if (runtimeType instanceof WildcardType) {
296      // wildcard has one and only one upper bound.
297      return boundAsSuperclass(((WildcardType) runtimeType).getUpperBounds()[0]);
298    }
299    Type superclass = getRawType().getGenericSuperclass();
300    if (superclass == null) {
301      return null;
302    }
303    @SuppressWarnings("unchecked") // super class of T
304    TypeToken<? super T> superToken = (TypeToken<? super T>) resolveSupertype(superclass);
305    return superToken;
306  }
307
308  @Nullable private TypeToken<? super T> boundAsSuperclass(Type bound) {
309    TypeToken<?> token = of(bound);
310    if (token.getRawType().isInterface()) {
311      return null;
312    }
313    @SuppressWarnings("unchecked") // only upper bound of T is passed in.
314    TypeToken<? super T> superclass = (TypeToken<? super T>) token;
315    return superclass;
316  }
317
318  /**
319   * Returns the generic interfaces that this type directly {@code implements}. This method is
320   * similar but different from {@link Class#getGenericInterfaces()}. For example, {@code
321   * new TypeToken<List<String>>() {}.getGenericInterfaces()} will return a list that contains
322   * {@code new TypeToken<Iterable<String>>() {}}; while {@code List.class.getGenericInterfaces()}
323   * will return an array that contains {@code Iterable<T>}, where the {@code T} is the type
324   * variable declared by interface {@code Iterable}.
325   *
326   * <p>If this type is a type variable or wildcard, its upper bounds are examined and those that
327   * are either an interface or upper-bounded only by interfaces are returned. This means that the
328   * returned types could include type variables too.
329   */
330  final ImmutableList<TypeToken<? super T>> getGenericInterfaces() {
331    if (runtimeType instanceof TypeVariable) {
332      return boundsAsInterfaces(((TypeVariable<?>) runtimeType).getBounds());
333    }
334    if (runtimeType instanceof WildcardType) {
335      return boundsAsInterfaces(((WildcardType) runtimeType).getUpperBounds());
336    }
337    ImmutableList.Builder<TypeToken<? super T>> builder = ImmutableList.builder();
338    for (Type interfaceType : getRawType().getGenericInterfaces()) {
339      @SuppressWarnings("unchecked") // interface of T
340      TypeToken<? super T> resolvedInterface = (TypeToken<? super T>)
341          resolveSupertype(interfaceType);
342      builder.add(resolvedInterface);
343    }
344    return builder.build();
345  }
346
347  private ImmutableList<TypeToken<? super T>> boundsAsInterfaces(Type[] bounds) {
348    ImmutableList.Builder<TypeToken<? super T>> builder = ImmutableList.builder();
349    for (Type bound : bounds) {
350      @SuppressWarnings("unchecked") // upper bound of T
351      TypeToken<? super T> boundType = (TypeToken<? super T>) of(bound);
352      if (boundType.getRawType().isInterface()) {
353        builder.add(boundType);
354      }
355    }
356    return builder.build();
357  }
358
359  /**
360   * Returns the set of interfaces and classes that this type is or is a subtype of. The returned
361   * types are parameterized with proper type arguments.
362   *
363   * <p>Subtypes are always listed before supertypes. But the reverse is not true. A type isn't
364   * necessarily a subtype of all the types following. Order between types without subtype
365   * relationship is arbitrary and not guaranteed.
366   *
367   * <p>If this type is a type variable or wildcard, upper bounds that are themselves type variables
368   * aren't included (their super interfaces and superclasses are).
369   */
370  public final TypeSet getTypes() {
371    return new TypeSet();
372  }
373
374  /**
375   * Returns the generic form of {@code superclass}. For example, if this is
376   * {@code ArrayList<String>}, {@code Iterable<String>} is returned given the
377   * input {@code Iterable.class}.
378   */
379  public final TypeToken<? super T> getSupertype(Class<? super T> superclass) {
380    checkArgument(superclass.isAssignableFrom(getRawType()),
381        "%s is not a super class of %s", superclass, this);
382    if (runtimeType instanceof TypeVariable) {
383      return getSupertypeFromUpperBounds(superclass, ((TypeVariable<?>) runtimeType).getBounds());
384    }
385    if (runtimeType instanceof WildcardType) {
386      return getSupertypeFromUpperBounds(superclass, ((WildcardType) runtimeType).getUpperBounds());
387    }
388    if (superclass.isArray()) {
389      return getArraySupertype(superclass);
390    }
391    @SuppressWarnings("unchecked") // resolved supertype
392    TypeToken<? super T> supertype = (TypeToken<? super T>)
393        resolveSupertype(toGenericType(superclass).runtimeType);
394    return supertype;
395  }
396
397  /**
398   * Returns subtype of {@code this} with {@code subclass} as the raw class.
399   * For example, if this is {@code Iterable<String>} and {@code subclass} is {@code List},
400   * {@code List<String>} is returned.
401   */
402  public final TypeToken<? extends T> getSubtype(Class<?> subclass) {
403    checkArgument(!(runtimeType instanceof TypeVariable),
404        "Cannot get subtype of type variable <%s>", this);
405    if (runtimeType instanceof WildcardType) {
406      return getSubtypeFromLowerBounds(subclass, ((WildcardType) runtimeType).getLowerBounds());
407    }
408    checkArgument(getRawType().isAssignableFrom(subclass),
409        "%s isn't a subclass of %s", subclass, this);
410    // unwrap array type if necessary
411    if (isArray()) {
412      return getArraySubtype(subclass);
413    }
414    @SuppressWarnings("unchecked") // guarded by the isAssignableFrom() statement above
415    TypeToken<? extends T> subtype = (TypeToken<? extends T>)
416        of(resolveTypeArgsForSubclass(subclass));
417    return subtype;
418  }
419
420  /** Returns true if this type is assignable from the given {@code type}. */
421  public final boolean isAssignableFrom(TypeToken<?> type) {
422    return isAssignableFrom(type.runtimeType);
423  }
424
425  /** Check if this type is assignable from the given {@code type}. */
426  public final boolean isAssignableFrom(Type type) {
427    return isAssignable(checkNotNull(type), runtimeType);
428  }
429
430  /**
431   * Returns true if this type is known to be an array type, such as {@code int[]}, {@code T[]},
432   * {@code <? extends Map<String, Integer>[]>} etc.
433   */
434  public final boolean isArray() {
435    return getComponentType() != null;
436  }
437
438  /**
439   * Returns the array component type if this type represents an array ({@code int[]}, {@code T[]},
440   * {@code <? extends Map<String, Integer>[]>} etc.), or else {@code null} is returned.
441   */
442  @Nullable public final TypeToken<?> getComponentType() {
443    Type componentType = Types.getComponentType(runtimeType);
444    if (componentType == null) {
445      return null;
446    }
447    return of(componentType);
448  }
449
450  /**
451   * The set of interfaces and classes that {@code T} is or is a subtype of. {@link Object} is not
452   * included in the set if this type is an interface.
453   */
454  public class TypeSet extends ForwardingSet<TypeToken<? super T>> implements Serializable {
455
456    private transient ImmutableSet<TypeToken<? super T>> types;
457
458    TypeSet() {}
459
460    /** Returns the types that are interfaces implemented by this type. */
461    public TypeSet interfaces() {
462      return new InterfaceSet(this);
463    }
464
465    /** Returns the types that are classes. */
466    public TypeSet classes() {
467      return new ClassSet();
468    }
469
470    @Override protected Set<TypeToken<? super T>> delegate() {
471      ImmutableSet<TypeToken<? super T>> filteredTypes = types;
472      if (filteredTypes == null) {
473        // Java has no way to express ? super T when we parameterize TypeToken vs. Class.
474        @SuppressWarnings({"unchecked", "rawtypes"})
475        ImmutableList<TypeToken<? super T>> collectedTypes = (ImmutableList)
476            TypeCollector.FOR_GENERIC_TYPE.collectTypes(TypeToken.this);
477        return (types = FluentIterable.from(collectedTypes)
478                .filter(TypeFilter.IGNORE_TYPE_VARIABLE_OR_WILDCARD)
479                .toImmutableSet());
480      } else {
481        return filteredTypes;
482      }
483    }
484
485    /** Returns the raw types of the types in this set, in the same order. */
486    public Set<Class<? super T>> rawTypes() {
487      // Java has no way to express ? super T when we parameterize TypeToken vs. Class.
488      @SuppressWarnings({"unchecked", "rawtypes"})
489      ImmutableList<Class<? super T>> collectedTypes = (ImmutableList)
490          TypeCollector.FOR_RAW_TYPE.collectTypes(getImmediateRawTypes());
491      return ImmutableSet.copyOf(collectedTypes);
492    }
493
494    private static final long serialVersionUID = 0;
495  }
496
497  private final class InterfaceSet extends TypeSet {
498
499    private transient final TypeSet allTypes;
500    private transient ImmutableSet<TypeToken<? super T>> interfaces;
501
502    InterfaceSet(TypeSet allTypes) {
503      this.allTypes = allTypes;
504    }
505
506    @Override protected Set<TypeToken<? super T>> delegate() {
507      ImmutableSet<TypeToken<? super T>> result = interfaces;
508      if (result == null) {
509        return (interfaces = FluentIterable.from(allTypes)
510            .filter(TypeFilter.INTERFACE_ONLY)
511            .toImmutableSet());
512      } else {
513        return result;
514      }
515    }
516
517    @Override public TypeSet interfaces() {
518      return this;
519    }
520
521    @Override public Set<Class<? super T>> rawTypes() {
522      // Java has no way to express ? super T when we parameterize TypeToken vs. Class.
523      @SuppressWarnings({"unchecked", "rawtypes"})
524      ImmutableList<Class<? super T>> collectedTypes = (ImmutableList)
525          TypeCollector.FOR_RAW_TYPE.collectTypes(getImmediateRawTypes());
526      return FluentIterable.from(collectedTypes)
527          .filter(new Predicate<Class<?>>() {
528            @Override public boolean apply(Class<?> type) {
529              return type.isInterface();
530            }
531          })
532          .toImmutableSet();
533    }
534
535    @Override public TypeSet classes() {
536      throw new UnsupportedOperationException("interfaces().classes() not supported.");
537    }
538
539    private Object readResolve() {
540      return getTypes().interfaces();
541    }
542
543    private static final long serialVersionUID = 0;
544  }
545
546  private final class ClassSet extends TypeSet {
547
548    private transient ImmutableSet<TypeToken<? super T>> classes;
549
550    @Override protected Set<TypeToken<? super T>> delegate() {
551      ImmutableSet<TypeToken<? super T>> result = classes;
552      if (result == null) {
553        @SuppressWarnings({"unchecked", "rawtypes"})
554        ImmutableList<TypeToken<? super T>> collectedTypes = (ImmutableList)
555            TypeCollector.FOR_GENERIC_TYPE.classesOnly().collectTypes(TypeToken.this);
556        return (classes = FluentIterable.from(collectedTypes)
557            .filter(TypeFilter.IGNORE_TYPE_VARIABLE_OR_WILDCARD)
558            .toImmutableSet());
559      } else {
560        return result;
561      }
562    }
563
564    @Override public TypeSet classes() {
565      return this;
566    }
567
568    @Override public Set<Class<? super T>> rawTypes() {
569      // Java has no way to express ? super T when we parameterize TypeToken vs. Class.
570      @SuppressWarnings({"unchecked", "rawtypes"})
571      ImmutableList<Class<? super T>> collectedTypes = (ImmutableList)
572          TypeCollector.FOR_RAW_TYPE.classesOnly().collectTypes(getImmediateRawTypes());
573      return ImmutableSet.copyOf(collectedTypes);
574    }
575
576    @Override public TypeSet interfaces() {
577      throw new UnsupportedOperationException("classes().interfaces() not supported.");
578    }
579
580    private Object readResolve() {
581      return getTypes().classes();
582    }
583
584    private static final long serialVersionUID = 0;
585  }
586
587  private enum TypeFilter implements Predicate<TypeToken<?>> {
588
589    IGNORE_TYPE_VARIABLE_OR_WILDCARD {
590      @Override public boolean apply(TypeToken<?> type) {
591        return !(type.runtimeType instanceof TypeVariable
592            || type.runtimeType instanceof WildcardType);
593      }
594    },
595    INTERFACE_ONLY {
596      @Override public boolean apply(TypeToken<?> type) {
597        return type.getRawType().isInterface();
598      }
599    }
600  }
601
602  /**
603   * Returns true if {@code o} is another {@code TypeToken} that represents the same {@link Type}.
604   */
605  @Override public boolean equals(@Nullable Object o) {
606    if (o instanceof TypeToken) {
607      TypeToken<?> that = (TypeToken<?>) o;
608      return runtimeType.equals(that.runtimeType);
609    }
610    return false;
611  }
612
613  @Override public int hashCode() {
614    return runtimeType.hashCode();
615  }
616
617  @Override public String toString() {
618    return Types.toString(runtimeType);
619  }
620
621  /** Implemented to support serialization of subclasses. */
622  protected Object writeReplace() {
623    // TypeResolver just transforms the type to our own impls that are Serializable
624    // except TypeVariable.
625    return of(new TypeResolver().resolveType(runtimeType));
626  }
627
628  /**
629   * Ensures that this type token doesn't contain type variables, which can cause unchecked type
630   * errors for callers like {@link TypeToInstanceMap}.
631   */
632  final TypeToken<T> rejectTypeVariables() {
633    checkArgument(!Types.containsTypeVariable(runtimeType),
634        "%s contains a type variable and is not safe for the operation");
635    return this;
636  }
637
638  private static boolean isAssignable(Type from, Type to) {
639    if (to.equals(from)) {
640      return true;
641    }
642    if (to instanceof WildcardType) {
643      return isAssignableToWildcardType(from, (WildcardType) to);
644    }
645    // if "from" is type variable, it's assignable if any of its "extends"
646    // bounds is assignable to "to".
647    if (from instanceof TypeVariable) {
648      return isAssignableFromAny(((TypeVariable<?>) from).getBounds(), to);
649    }
650    // if "from" is wildcard, it'a assignable to "to" if any of its "extends"
651    // bounds is assignable to "to".
652    if (from instanceof WildcardType) {
653      return isAssignableFromAny(((WildcardType) from).getUpperBounds(), to);
654    }
655    if (from instanceof GenericArrayType) {
656      return isAssignableFromGenericArrayType((GenericArrayType) from, to);
657    }
658    // Proceed to regular Type assignability check
659    if (to instanceof Class) {
660      return isAssignableToClass(from, (Class<?>) to);
661    } else if (to instanceof ParameterizedType) {
662      return isAssignableToParameterizedType(from, (ParameterizedType) to);
663    } else if (to instanceof GenericArrayType) {
664      return isAssignableToGenericArrayType(from, (GenericArrayType) to);
665    } else { // to instanceof TypeVariable
666      return false;
667    }
668  }
669
670  private static boolean isAssignableFromAny(Type[] fromTypes, Type to) {
671    for (Type from : fromTypes) {
672      if (isAssignable(from, to)) {
673        return true;
674      }
675    }
676    return false;
677  }
678
679  private static boolean isAssignableToClass(Type from, Class<?> to) {
680    return to.isAssignableFrom(getRawType(from));
681  }
682
683  private static boolean isAssignableToWildcardType(
684      Type from, WildcardType to) {
685    // if "to" is <? extends Foo>, "from" can be:
686    // Foo, SubFoo, <? extends Foo>, <? extends SubFoo>, <T extends Foo> or
687    // <T extends SubFoo>.
688    // if "to" is <? super Foo>, "from" can be:
689    // Foo, SuperFoo, <? super Foo> or <? super SuperFoo>.
690    return isAssignable(from, supertypeBound(to)) && isAssignableBySubtypeBound(from, to);
691  }
692
693  private static boolean isAssignableBySubtypeBound(Type from, WildcardType to) {
694    Type toSubtypeBound = subtypeBound(to);
695    if (toSubtypeBound == null) {
696      return true;
697    }
698    Type fromSubtypeBound = subtypeBound(from);
699    if (fromSubtypeBound == null) {
700      return false;
701    }
702    return isAssignable(toSubtypeBound, fromSubtypeBound);
703  }
704
705  private static boolean isAssignableToParameterizedType(Type from, ParameterizedType to) {
706    Class<?> matchedClass = getRawType(to);
707    if (!matchedClass.isAssignableFrom(getRawType(from))) {
708      return false;
709    }
710    Type[] typeParams = matchedClass.getTypeParameters();
711    Type[] toTypeArgs = to.getActualTypeArguments();
712    TypeToken<?> fromTypeToken = of(from);
713    for (int i = 0; i < typeParams.length; i++) {
714      // If "to" is "List<? extends CharSequence>"
715      // and "from" is StringArrayList,
716      // First step is to figure out StringArrayList "is-a" List<E> and <E> is
717      // String.
718      // typeParams[0] is E and fromTypeToken.get(typeParams[0]) will resolve to
719      // String.
720      // String is then matched against <? extends CharSequence>.
721      Type fromTypeArg = fromTypeToken.resolveType(typeParams[i]).runtimeType;
722      if (!matchTypeArgument(fromTypeArg, toTypeArgs[i])) {
723        return false;
724      }
725    }
726    return true;
727  }
728
729  private static boolean isAssignableToGenericArrayType(Type from, GenericArrayType to) {
730    if (from instanceof Class) {
731      Class<?> fromClass = (Class<?>) from;
732      if (!fromClass.isArray()) {
733        return false;
734      }
735      return isAssignable(fromClass.getComponentType(), to.getGenericComponentType());
736    } else if (from instanceof GenericArrayType) {
737      GenericArrayType fromArrayType = (GenericArrayType) from;
738      return isAssignable(fromArrayType.getGenericComponentType(), to.getGenericComponentType());
739    } else {
740      return false;
741    }
742  }
743
744  private static boolean isAssignableFromGenericArrayType(GenericArrayType from, Type to) {
745    if (to instanceof Class) {
746      Class<?> toClass = (Class<?>) to;
747      if (!toClass.isArray()) {
748        return toClass == Object.class; // any T[] is assignable to Object
749      }
750      return isAssignable(from.getGenericComponentType(), toClass.getComponentType());
751    } else if (to instanceof GenericArrayType) {
752      GenericArrayType toArrayType = (GenericArrayType) to;
753      return isAssignable(from.getGenericComponentType(), toArrayType.getGenericComponentType());
754    } else {
755      return false;
756    }
757  }
758
759  private static boolean matchTypeArgument(Type from, Type to) {
760    if (from.equals(to)) {
761      return true;
762    }
763    if (to instanceof WildcardType) {
764      return isAssignableToWildcardType(from, (WildcardType) to);
765    }
766    return false;
767  }
768
769  private static Type supertypeBound(Type type) {
770    if (type instanceof WildcardType) {
771      return supertypeBound((WildcardType) type);
772    }
773    return type;
774  }
775
776  private static Type supertypeBound(WildcardType type) {
777    Type[] upperBounds = type.getUpperBounds();
778    if (upperBounds.length == 1) {
779      return supertypeBound(upperBounds[0]);
780    } else if (upperBounds.length == 0) {
781      return Object.class;
782    } else {
783      throw new AssertionError(
784          "There should be at most one upper bound for wildcard type: " + type);
785    }
786  }
787
788  @Nullable private static Type subtypeBound(Type type) {
789    if (type instanceof WildcardType) {
790      return subtypeBound((WildcardType) type);
791    } else {
792      return type;
793    }
794  }
795
796  @Nullable private static Type subtypeBound(WildcardType type) {
797    Type[] lowerBounds = type.getLowerBounds();
798    if (lowerBounds.length == 1) {
799      return subtypeBound(lowerBounds[0]);
800    } else if (lowerBounds.length == 0) {
801      return null;
802    } else {
803      throw new AssertionError(
804          "Wildcard should have at most one lower bound: " + type);
805    }
806  }
807
808  @VisibleForTesting static Class<?> getRawType(Type type) {
809    // For wildcard or type variable, the first bound determines the runtime type.
810    return getRawTypes(type).iterator().next();
811  }
812
813  @VisibleForTesting static ImmutableSet<Class<?>> getRawTypes(Type type) {
814    if (type instanceof Class) {
815      return ImmutableSet.<Class<?>>of((Class<?>) type);
816    } else if (type instanceof ParameterizedType) {
817      ParameterizedType parameterizedType = (ParameterizedType) type;
818      // JDK implementation declares getRawType() to return Class<?>
819      return ImmutableSet.<Class<?>>of((Class<?>) parameterizedType.getRawType());
820    } else if (type instanceof GenericArrayType) {
821      GenericArrayType genericArrayType = (GenericArrayType) type;
822      return ImmutableSet.<Class<?>>of(Types.getArrayClass(
823          getRawType(genericArrayType.getGenericComponentType())));
824    } else if (type instanceof TypeVariable) {
825      return getRawTypes(((TypeVariable<?>) type).getBounds());
826    } else if (type instanceof WildcardType) {
827      return getRawTypes(((WildcardType) type).getUpperBounds());
828    } else {
829      throw new AssertionError(type + " unsupported");
830    }
831  }
832
833  private static ImmutableSet<Class<?>> getRawTypes(Type[] types) {
834    ImmutableSet.Builder<Class<?>> builder = ImmutableSet.builder();
835    for (Type type : types) {
836      builder.addAll(getRawTypes(type));
837    }
838    return builder.build();
839  }
840
841  /**
842   * Returns the type token representing the generic type declaration of {@code cls}. For example:
843   * {@code TypeToken.getGenericType(Iterable.class)} returns {@code Iterable<T>}.
844   *
845   * <p>If {@code cls} isn't parameterized and isn't a generic array, the type token of the class is
846   * returned.
847   */
848  @VisibleForTesting static <T> TypeToken<? extends T> toGenericType(Class<T> cls) {
849    if (cls.isArray()) {
850      Type arrayOfGenericType = Types.newArrayType(
851          // If we are passed with int[].class, don't turn it to GenericArrayType
852          toGenericType(cls.getComponentType()).runtimeType);
853      @SuppressWarnings("unchecked") // array is covariant
854      TypeToken<? extends T> result = (TypeToken<? extends T>) of(arrayOfGenericType);
855      return result;
856    }
857    TypeVariable<Class<T>>[] typeParams = cls.getTypeParameters();
858    if (typeParams.length > 0) {
859      @SuppressWarnings("unchecked") // Like, it's Iterable<T> for Iterable.class
860      TypeToken<? extends T> type = (TypeToken<? extends T>)
861          of(Types.newParameterizedType(cls, typeParams));
862      return type;
863    } else {
864      return of(cls);
865    }
866  }
867
868  private TypeToken<? super T> getSupertypeFromUpperBounds(
869      Class<? super T> supertype, Type[] upperBounds) {
870    for (Type upperBound : upperBounds) {
871      @SuppressWarnings("unchecked") // T's upperbound is <? super T>.
872      TypeToken<? super T> bound = (TypeToken<? super T>) of(upperBound);
873      if (of(supertype).isAssignableFrom(bound)) {
874        @SuppressWarnings({"rawtypes", "unchecked"}) // guarded by the isAssignableFrom check.
875        TypeToken<? super T> result = bound.getSupertype((Class) supertype);
876        return result;
877      }
878    }
879    throw new IllegalArgumentException(supertype + " isn't a super type of " + this);
880  }
881
882  private TypeToken<? extends T> getSubtypeFromLowerBounds(Class<?> subclass, Type[] lowerBounds) {
883    for (Type lowerBound : lowerBounds) {
884      @SuppressWarnings("unchecked") // T's lower bound is <? extends T>
885      TypeToken<? extends T> bound = (TypeToken<? extends T>) of(lowerBound);
886      // Java supports only one lowerbound anyway.
887      return bound.getSubtype(subclass);
888    }
889    throw new IllegalArgumentException(subclass + " isn't a subclass of " + this);
890  }
891
892  private TypeToken<? super T> getArraySupertype(Class<? super T> supertype) {
893    // with component type, we have lost generic type information
894    // Use raw type so that compiler allows us to call getSupertype()
895    @SuppressWarnings("rawtypes")
896    TypeToken componentType = checkNotNull(getComponentType(),
897        "%s isn't a super type of %s", supertype, this);
898    // array is covariant. component type is super type, so is the array type.
899    @SuppressWarnings("unchecked") // going from raw type back to generics
900    TypeToken<?> componentSupertype = componentType.getSupertype(supertype.getComponentType());
901    @SuppressWarnings("unchecked") // component type is super type, so is array type.
902    TypeToken<? super T> result = (TypeToken<? super T>)
903        // If we are passed with int[].class, don't turn it to GenericArrayType
904        of(newArrayClassOrGenericArrayType(componentSupertype.runtimeType));
905    return result;
906  }
907
908  private TypeToken<? extends T> getArraySubtype(Class<?> subclass) {
909    // array is covariant. component type is subtype, so is the array type.
910    TypeToken<?> componentSubtype = getComponentType()
911        .getSubtype(subclass.getComponentType());
912    @SuppressWarnings("unchecked") // component type is subtype, so is array type.
913    TypeToken<? extends T> result = (TypeToken<? extends T>)
914        // If we are passed with int[].class, don't turn it to GenericArrayType
915        of(newArrayClassOrGenericArrayType(componentSubtype.runtimeType));
916    return result;
917  }
918
919  private Type resolveTypeArgsForSubclass(Class<?> subclass) {
920    if (runtimeType instanceof Class) {
921      // no resolution needed
922      return subclass;
923    }
924    // class Base<A, B> {}
925    // class Sub<X, Y> extends Base<X, Y> {}
926    // Base<String, Integer>.subtype(Sub.class):
927
928    // Sub<X, Y>.getSupertype(Base.class) => Base<X, Y>
929    // => X=String, Y=Integer
930    // => Sub<X, Y>=Sub<String, Integer>
931    TypeToken<?> genericSubtype = toGenericType(subclass);
932    @SuppressWarnings({"rawtypes", "unchecked"}) // subclass isn't <? extends T>
933    Type supertypeWithArgsFromSubtype = genericSubtype
934        .getSupertype((Class) getRawType())
935        .runtimeType;
936    return new TypeResolver().where(supertypeWithArgsFromSubtype, runtimeType)
937        .resolveType(genericSubtype.runtimeType);
938  }
939
940  /**
941   * Creates an array class if {@code componentType} is a class, or else, a
942   * {@link GenericArrayType}. This is what Java7 does for generic array type
943   * parameters.
944   */
945  private static Type newArrayClassOrGenericArrayType(Type componentType) {
946    return Types.JavaVersion.JAVA7.newArrayType(componentType);
947  }
948
949  private static final class SimpleTypeToken<T> extends TypeToken<T> {
950
951    SimpleTypeToken(Type type) {
952      super(type);
953    }
954
955    private static final long serialVersionUID = 0;
956  }
957
958  /**
959   * Collects parent types from a sub type.
960   *
961   * @param <K> The type "kind". Either a TypeToken, or Class.
962   */
963  private abstract static class TypeCollector<K> {
964
965    static final TypeCollector<TypeToken<?>> FOR_GENERIC_TYPE =
966        new TypeCollector<TypeToken<?>>() {
967          @Override Class<?> getRawType(TypeToken<?> type) {
968            return type.getRawType();
969          }
970
971          @Override Iterable<? extends TypeToken<?>> getInterfaces(TypeToken<?> type) {
972            return type.getGenericInterfaces();
973          }
974
975          @Nullable
976          @Override TypeToken<?> getSuperclass(TypeToken<?> type) {
977            return type.getGenericSuperclass();
978          }
979        };
980
981    static final TypeCollector<Class<?>> FOR_RAW_TYPE =
982        new TypeCollector<Class<?>>() {
983          @Override Class<?> getRawType(Class<?> type) {
984            return type;
985          }
986
987          @Override Iterable<? extends Class<?>> getInterfaces(Class<?> type) {
988            return Arrays.asList(type.getInterfaces());
989          }
990
991          @Nullable
992          @Override Class<?> getSuperclass(Class<?> type) {
993            return type.getSuperclass();
994          }
995        };
996
997    /** For just classes, we don't have to traverse interfaces. */
998    final TypeCollector<K> classesOnly() {
999      return new ForwardingTypeCollector<K>(this) {
1000        @Override Iterable<? extends K> getInterfaces(K type) {
1001          return ImmutableSet.of();
1002        }
1003        @Override ImmutableList<K> collectTypes(Iterable<? extends K> types) {
1004          ImmutableList.Builder<K> builder = ImmutableList.builder();
1005          for (K type : types) {
1006            if (!getRawType(type).isInterface()) {
1007              builder.add(type);
1008            }
1009          }
1010          return super.collectTypes(builder.build());
1011        }
1012      };
1013    }
1014
1015    final ImmutableList<K> collectTypes(K type) {
1016      return collectTypes(ImmutableList.of(type));
1017    }
1018
1019    ImmutableList<K> collectTypes(Iterable<? extends K> types) {
1020      // type -> order number. 1 for Object, 2 for anything directly below, so on so forth.
1021      Map<K, Integer> map = Maps.newHashMap();
1022      for (K type : types) {
1023        collectTypes(type, map);
1024      }
1025      return sortKeysByValue(map, Ordering.natural().reverse());
1026    }
1027
1028    /** Collects all types to map, and returns the total depth from T up to Object. */
1029    private int collectTypes(K type, Map<? super K, Integer> map) {
1030      Integer existing = map.get(this);
1031      if (existing != null) {
1032        // short circuit: if set contains type it already contains its supertypes
1033        return existing;
1034      }
1035      int aboveMe = getRawType(type).isInterface()
1036          ? 1 // interfaces should be listed before Object
1037          : 0;
1038      for (K interfaceType : getInterfaces(type)) {
1039        aboveMe = Math.max(aboveMe, collectTypes(interfaceType, map));
1040      }
1041      K superclass = getSuperclass(type);
1042      if (superclass != null) {
1043        aboveMe = Math.max(aboveMe, collectTypes(superclass, map));
1044      }
1045      // TODO(benyu): should we include Object for interface?
1046      // Also, CharSequence[] and Object[] for String[]?
1047      map.put(type, aboveMe + 1);
1048      return aboveMe + 1;
1049    }
1050
1051    private static <K, V> ImmutableList<K> sortKeysByValue(
1052        final Map<K, V> map, final Comparator<? super V> valueComparator) {
1053      Ordering<K> keyOrdering = new Ordering<K>() {
1054        @Override public int compare(K left, K right) {
1055          return valueComparator.compare(map.get(left), map.get(right));
1056        }
1057      };
1058      return keyOrdering.immutableSortedCopy(map.keySet());
1059    }
1060
1061    abstract Class<?> getRawType(K type);
1062    abstract Iterable<? extends K> getInterfaces(K type);
1063    @Nullable abstract K getSuperclass(K type);
1064
1065    private static class ForwardingTypeCollector<K> extends TypeCollector<K> {
1066
1067      private final TypeCollector<K> delegate;
1068
1069      ForwardingTypeCollector(TypeCollector<K> delegate) {
1070        this.delegate = delegate;
1071      }
1072
1073      @Override Class<?> getRawType(K type) {
1074        return delegate.getRawType(type);
1075      }
1076
1077      @Override Iterable<? extends K> getInterfaces(K type) {
1078        return delegate.getInterfaces(type);
1079      }
1080
1081      @Override K getSuperclass(K type) {
1082        return delegate.getSuperclass(type);
1083      }
1084    }
1085  }
1086}