001/*
002 * Copyright (C) 2006 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;
020
021import com.google.common.annotations.Beta;
022import com.google.common.annotations.VisibleForTesting;
023import com.google.common.base.Joiner;
024import com.google.common.base.Predicate;
025import com.google.common.collect.FluentIterable;
026import com.google.common.collect.ForwardingSet;
027import com.google.common.collect.ImmutableList;
028import com.google.common.collect.ImmutableMap;
029import com.google.common.collect.ImmutableSet;
030import com.google.common.collect.Maps;
031import com.google.common.collect.Ordering;
032import com.google.common.primitives.Primitives;
033import com.google.errorprone.annotations.CanIgnoreReturnValue;
034import java.io.Serializable;
035import java.lang.reflect.Constructor;
036import java.lang.reflect.GenericArrayType;
037import java.lang.reflect.Method;
038import java.lang.reflect.Modifier;
039import java.lang.reflect.ParameterizedType;
040import java.lang.reflect.Type;
041import java.lang.reflect.TypeVariable;
042import java.lang.reflect.WildcardType;
043import java.util.ArrayList;
044import java.util.Arrays;
045import java.util.Comparator;
046import java.util.List;
047import java.util.Map;
048import java.util.Set;
049import org.checkerframework.checker.nullness.qual.Nullable;
050
051/**
052 * A {@link Type} with generics.
053 *
054 * <p>Operations that are otherwise only available in {@link Class} are implemented to support
055 * {@code Type}, for example {@link #isSubtypeOf}, {@link #isArray} and {@link #getComponentType}.
056 * It also provides additional utilities such as {@link #getTypes}, {@link #resolveType}, etc.
057 *
058 * <p>There are three ways to get a {@code TypeToken} instance:
059 *
060 * <ul>
061 *   <li>Wrap a {@code Type} obtained via reflection. For example: {@code
062 *       TypeToken.of(method.getGenericReturnType())}.
063 *   <li>Capture a generic type with a (usually anonymous) subclass. For example:
064 *       <pre>{@code
065 * new TypeToken<List<String>>() {}
066 * }</pre>
067 *       <p>Note that it's critical that the actual type argument is carried by a subclass. The
068 *       following code is wrong because it only captures the {@code <T>} type variable of the
069 *       {@code listType()} method signature; while {@code <String>} is lost in erasure:
070 *       <pre>{@code
071 * class Util {
072 *   static <T> TypeToken<List<T>> listType() {
073 *     return new TypeToken<List<T>>() {};
074 *   }
075 * }
076 *
077 * TypeToken<List<String>> stringListType = Util.<String>listType();
078 * }</pre>
079 *   <li>Capture a generic type with a (usually anonymous) subclass and resolve it against a context
080 *       class that knows what the type parameters are. For example:
081 *       <pre>{@code
082 * abstract class IKnowMyType<T> {
083 *   TypeToken<T> type = new TypeToken<T>(getClass()) {};
084 * }
085 * new IKnowMyType<String>() {}.type => String
086 * }</pre>
087 * </ul>
088 *
089 * <p>{@code TypeToken} is serializable when no type variable is contained in the type.
090 *
091 * <p>Note to Guice users: {@code} TypeToken is similar to Guice's {@code TypeLiteral} class except
092 * that it is serializable and offers numerous additional utility methods.
093 *
094 * @author Bob Lee
095 * @author Sven Mawson
096 * @author Ben Yu
097 * @since 12.0
098 */
099@Beta
100@SuppressWarnings("serial") // SimpleTypeToken is the serialized form.
101public abstract class TypeToken<T> extends TypeCapture<T> implements Serializable {
102
103  private final Type runtimeType;
104
105  /** Resolver for resolving parameter and field types with {@link #runtimeType} as context. */
106  private transient @Nullable TypeResolver invariantTypeResolver;
107
108  /** Resolver for resolving covariant types with {@link #runtimeType} as context. */
109  private transient @Nullable TypeResolver covariantTypeResolver;
110
111  /**
112   * Constructs a new type token of {@code T}.
113   *
114   * <p>Clients create an empty anonymous subclass. Doing so embeds the type parameter in the
115   * anonymous class's type hierarchy so we can reconstitute it at runtime despite erasure.
116   *
117   * <p>For example:
118   *
119   * <pre>{@code
120   * TypeToken<List<String>> t = new TypeToken<List<String>>() {};
121   * }</pre>
122   */
123  protected TypeToken() {
124    this.runtimeType = capture();
125    checkState(
126        !(runtimeType instanceof TypeVariable),
127        "Cannot construct a TypeToken for a type variable.\n"
128            + "You probably meant to call new TypeToken<%s>(getClass()) "
129            + "that can resolve the type variable for you.\n"
130            + "If you do need to create a TypeToken of a type variable, "
131            + "please use TypeToken.of() instead.",
132        runtimeType);
133  }
134
135  /**
136   * Constructs a new type token of {@code T} while resolving free type variables in the context of
137   * {@code declaringClass}.
138   *
139   * <p>Clients create an empty anonymous subclass. Doing so embeds the type parameter in the
140   * anonymous class's type hierarchy so we can reconstitute it at runtime despite erasure.
141   *
142   * <p>For example:
143   *
144   * <pre>{@code
145   * abstract class IKnowMyType<T> {
146   *   TypeToken<T> getMyType() {
147   *     return new TypeToken<T>(getClass()) {};
148   *   }
149   * }
150   *
151   * new IKnowMyType<String>() {}.getMyType() => String
152   * }</pre>
153   */
154  protected TypeToken(Class<?> declaringClass) {
155    Type captured = super.capture();
156    if (captured instanceof Class) {
157      this.runtimeType = captured;
158    } else {
159      this.runtimeType = TypeResolver.covariantly(declaringClass).resolveType(captured);
160    }
161  }
162
163  private TypeToken(Type type) {
164    this.runtimeType = checkNotNull(type);
165  }
166
167  /** Returns an instance of type token that wraps {@code type}. */
168  public static <T> TypeToken<T> of(Class<T> type) {
169    return new SimpleTypeToken<T>(type);
170  }
171
172  /** Returns an instance of type token that wraps {@code type}. */
173  public static TypeToken<?> of(Type type) {
174    return new SimpleTypeToken<>(type);
175  }
176
177  /**
178   * Returns the raw type of {@code T}. Formally speaking, if {@code T} is returned by {@link
179   * java.lang.reflect.Method#getGenericReturnType}, the raw type is what's returned by {@link
180   * java.lang.reflect.Method#getReturnType} of the same method object. Specifically:
181   *
182   * <ul>
183   *   <li>If {@code T} is a {@code Class} itself, {@code T} itself is returned.
184   *   <li>If {@code T} is a {@link ParameterizedType}, the raw type of the parameterized type is
185   *       returned.
186   *   <li>If {@code T} is a {@link GenericArrayType}, the returned type is the corresponding array
187   *       class. For example: {@code List<Integer>[] => List[]}.
188   *   <li>If {@code T} is a type variable or a wildcard type, the raw type of the first upper bound
189   *       is returned. For example: {@code <X extends Foo> => Foo}.
190   * </ul>
191   */
192  public final Class<? super T> getRawType() {
193    // For wildcard or type variable, the first bound determines the runtime type.
194    Class<?> rawType = getRawTypes().iterator().next();
195    @SuppressWarnings("unchecked") // raw type is |T|
196    Class<? super T> result = (Class<? super T>) rawType;
197    return result;
198  }
199
200  /** Returns the represented type. */
201  public final Type getType() {
202    return runtimeType;
203  }
204
205  /**
206   * Returns a new {@code TypeToken} where type variables represented by {@code typeParam} are
207   * substituted by {@code typeArg}. For example, it can be used to construct {@code Map<K, V>} for
208   * any {@code K} and {@code V} type:
209   *
210   * <pre>{@code
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 =
225        new TypeResolver()
226            .where(
227                ImmutableMap.of(
228                    new TypeResolver.TypeVariableKey(typeParam.typeVariable), typeArg.runtimeType));
229    // If there's any type error, we'd report now rather than later.
230    return new SimpleTypeToken<T>(resolver.resolveType(runtimeType));
231  }
232
233  /**
234   * Returns a new {@code TypeToken} where type variables represented by {@code typeParam} are
235   * substituted by {@code typeArg}. For example, it can be used to construct {@code Map<K, V>} for
236   * any {@code K} and {@code V} type:
237   *
238   * <pre>{@code
239   * static <K, V> TypeToken<Map<K, V>> mapOf(
240   *     Class<K> keyType, Class<V> valueType) {
241   *   return new TypeToken<Map<K, V>>() {}
242   *       .where(new TypeParameter<K>() {}, keyType)
243   *       .where(new TypeParameter<V>() {}, valueType);
244   * }
245   * }</pre>
246   *
247   * @param <X> The parameter type
248   * @param typeParam the parameter type variable
249   * @param typeArg the actual type to substitute
250   */
251  public final <X> TypeToken<T> where(TypeParameter<X> typeParam, Class<X> typeArg) {
252    return where(typeParam, of(typeArg));
253  }
254
255  /**
256   * Resolves the given {@code type} against the type context represented by this type. For example:
257   *
258   * <pre>{@code
259   * new TypeToken<List<String>>() {}.resolveType(
260   *     List.class.getMethod("get", int.class).getGenericReturnType())
261   * => String.class
262   * }</pre>
263   */
264  public final TypeToken<?> resolveType(Type type) {
265    checkNotNull(type);
266    // Being conservative here because the user could use resolveType() to resolve a type in an
267    // invariant context.
268    return of(getInvariantTypeResolver().resolveType(type));
269  }
270
271  private TypeToken<?> resolveSupertype(Type type) {
272    TypeToken<?> supertype = of(getCovariantTypeResolver().resolveType(type));
273    // super types' type mapping is a subset of type mapping of this type.
274    supertype.covariantTypeResolver = covariantTypeResolver;
275    supertype.invariantTypeResolver = invariantTypeResolver;
276    return supertype;
277  }
278
279  /**
280   * Returns the generic superclass of this type or {@code null} if the type represents {@link
281   * Object} or an interface. This method is similar but different from {@link
282   * Class#getGenericSuperclass}. For example, {@code new TypeToken<StringArrayList>()
283   * {}.getGenericSuperclass()} will return {@code new TypeToken<ArrayList<String>>() {}}; while
284   * {@code StringArrayList.class.getGenericSuperclass()} will return {@code ArrayList<E>}, where
285   * {@code E} is the type variable declared by class {@code ArrayList}.
286   *
287   * <p>If this type is a type variable or wildcard, its first upper bound is examined and returned
288   * if the bound is a class or extends from a class. This means that the returned type could be a
289   * type variable too.
290   */
291  final @Nullable TypeToken<? super T> getGenericSuperclass() {
292    if (runtimeType instanceof TypeVariable) {
293      // First bound is always the super class, if one exists.
294      return boundAsSuperclass(((TypeVariable<?>) runtimeType).getBounds()[0]);
295    }
296    if (runtimeType instanceof WildcardType) {
297      // wildcard has one and only one upper bound.
298      return boundAsSuperclass(((WildcardType) runtimeType).getUpperBounds()[0]);
299    }
300    Type superclass = getRawType().getGenericSuperclass();
301    if (superclass == null) {
302      return null;
303    }
304    @SuppressWarnings("unchecked") // super class of T
305    TypeToken<? super T> superToken = (TypeToken<? super T>) resolveSupertype(superclass);
306    return superToken;
307  }
308
309  private @Nullable TypeToken<? super T> boundAsSuperclass(Type bound) {
310    TypeToken<?> token = of(bound);
311    if (token.getRawType().isInterface()) {
312      return null;
313    }
314    @SuppressWarnings("unchecked") // only upper bound of T is passed in.
315    TypeToken<? super T> superclass = (TypeToken<? super T>) token;
316    return superclass;
317  }
318
319  /**
320   * Returns the generic interfaces that this type directly {@code implements}. This method is
321   * similar but different from {@link Class#getGenericInterfaces()}. For example, {@code new
322   * TypeToken<List<String>>() {}.getGenericInterfaces()} will return a list that contains {@code
323   * new TypeToken<Iterable<String>>() {}}; while {@code List.class.getGenericInterfaces()} will
324   * return an array that contains {@code Iterable<T>}, where the {@code T} is the type variable
325   * declared by interface {@code Iterable}.
326   *
327   * <p>If this type is a type variable or wildcard, its upper bounds are examined and those that
328   * are either an interface or upper-bounded only by interfaces are returned. This means that the
329   * returned types could include type variables too.
330   */
331  final ImmutableList<TypeToken<? super T>> getGenericInterfaces() {
332    if (runtimeType instanceof TypeVariable) {
333      return boundsAsInterfaces(((TypeVariable<?>) runtimeType).getBounds());
334    }
335    if (runtimeType instanceof WildcardType) {
336      return boundsAsInterfaces(((WildcardType) runtimeType).getUpperBounds());
337    }
338    ImmutableList.Builder<TypeToken<? super T>> builder = ImmutableList.builder();
339    for (Type interfaceType : getRawType().getGenericInterfaces()) {
340      @SuppressWarnings("unchecked") // interface of T
341      TypeToken<? super T> resolvedInterface =
342          (TypeToken<? super T>) resolveSupertype(interfaceType);
343      builder.add(resolvedInterface);
344    }
345    return builder.build();
346  }
347
348  private ImmutableList<TypeToken<? super T>> boundsAsInterfaces(Type[] bounds) {
349    ImmutableList.Builder<TypeToken<? super T>> builder = ImmutableList.builder();
350    for (Type bound : bounds) {
351      @SuppressWarnings("unchecked") // upper bound of T
352      TypeToken<? super T> boundType = (TypeToken<? super T>) of(bound);
353      if (boundType.getRawType().isInterface()) {
354        builder.add(boundType);
355      }
356    }
357    return builder.build();
358  }
359
360  /**
361   * Returns the set of interfaces and classes that this type is or is a subtype of. The returned
362   * types are parameterized with proper type arguments.
363   *
364   * <p>Subtypes are always listed before supertypes. But the reverse is not true. A type isn't
365   * necessarily a subtype of all the types following. Order between types without subtype
366   * relationship is arbitrary and not guaranteed.
367   *
368   * <p>If this type is a type variable or wildcard, upper bounds that are themselves type variables
369   * aren't included (their super interfaces and superclasses are).
370   */
371  public final TypeSet getTypes() {
372    return new TypeSet();
373  }
374
375  /**
376   * Returns the generic form of {@code superclass}. For example, if this is {@code
377   * ArrayList<String>}, {@code Iterable<String>} is returned given the input {@code
378   * Iterable.class}.
379   */
380  public final TypeToken<? super T> getSupertype(Class<? super T> superclass) {
381    checkArgument(
382        this.someRawTypeIsSubclassOf(superclass),
383        "%s is not a super class of %s",
384        superclass,
385        this);
386    if (runtimeType instanceof TypeVariable) {
387      return getSupertypeFromUpperBounds(superclass, ((TypeVariable<?>) runtimeType).getBounds());
388    }
389    if (runtimeType instanceof WildcardType) {
390      return getSupertypeFromUpperBounds(superclass, ((WildcardType) runtimeType).getUpperBounds());
391    }
392    if (superclass.isArray()) {
393      return getArraySupertype(superclass);
394    }
395    @SuppressWarnings("unchecked") // resolved supertype
396    TypeToken<? super T> supertype =
397        (TypeToken<? super T>) resolveSupertype(toGenericType(superclass).runtimeType);
398    return supertype;
399  }
400
401  /**
402   * Returns subtype of {@code this} with {@code subclass} as the raw class. For example, if this is
403   * {@code Iterable<String>} and {@code subclass} is {@code List}, {@code List<String>} is
404   * returned.
405   */
406  public final TypeToken<? extends T> getSubtype(Class<?> subclass) {
407    checkArgument(
408        !(runtimeType instanceof TypeVariable), "Cannot get subtype of type variable <%s>", this);
409    if (runtimeType instanceof WildcardType) {
410      return getSubtypeFromLowerBounds(subclass, ((WildcardType) runtimeType).getLowerBounds());
411    }
412    // unwrap array type if necessary
413    if (isArray()) {
414      return getArraySubtype(subclass);
415    }
416    // At this point, it's either a raw class or parameterized type.
417    checkArgument(
418        getRawType().isAssignableFrom(subclass), "%s isn't a subclass of %s", subclass, this);
419    Type resolvedTypeArgs = resolveTypeArgsForSubclass(subclass);
420    @SuppressWarnings("unchecked") // guarded by the isAssignableFrom() statement above
421    TypeToken<? extends T> subtype = (TypeToken<? extends T>) of(resolvedTypeArgs);
422    checkArgument(
423        subtype.isSubtypeOf(this), "%s does not appear to be a subtype of %s", subtype, this);
424    return subtype;
425  }
426
427  /**
428   * Returns true if this type is a supertype of the given {@code type}. "Supertype" is defined
429   * according to <a
430   * href="http://docs.oracle.com/javase/specs/jls/se8/html/jls-4.html#jls-4.5.1">the rules for type
431   * arguments</a> introduced with Java generics.
432   *
433   * @since 19.0
434   */
435  public final boolean isSupertypeOf(TypeToken<?> type) {
436    return type.isSubtypeOf(getType());
437  }
438
439  /**
440   * Returns true if this type is a supertype of the given {@code type}. "Supertype" is defined
441   * according to <a
442   * href="http://docs.oracle.com/javase/specs/jls/se8/html/jls-4.html#jls-4.5.1">the rules for type
443   * arguments</a> introduced with Java generics.
444   *
445   * @since 19.0
446   */
447  public final boolean isSupertypeOf(Type type) {
448    return of(type).isSubtypeOf(getType());
449  }
450
451  /**
452   * Returns true if this type is a subtype of the given {@code type}. "Subtype" is defined
453   * according to <a
454   * href="http://docs.oracle.com/javase/specs/jls/se8/html/jls-4.html#jls-4.5.1">the rules for type
455   * arguments</a> introduced with Java generics.
456   *
457   * @since 19.0
458   */
459  public final boolean isSubtypeOf(TypeToken<?> type) {
460    return isSubtypeOf(type.getType());
461  }
462
463  /**
464   * Returns true if this type is a subtype of the given {@code type}. "Subtype" is defined
465   * according to <a
466   * href="http://docs.oracle.com/javase/specs/jls/se8/html/jls-4.html#jls-4.5.1">the rules for type
467   * arguments</a> introduced with Java generics.
468   *
469   * @since 19.0
470   */
471  public final boolean isSubtypeOf(Type supertype) {
472    checkNotNull(supertype);
473    if (supertype instanceof WildcardType) {
474      // if 'supertype' is <? super Foo>, 'this' can be:
475      // Foo, SubFoo, <? extends Foo>.
476      // if 'supertype' is <? extends Foo>, nothing is a subtype.
477      return any(((WildcardType) supertype).getLowerBounds()).isSupertypeOf(runtimeType);
478    }
479    // if 'this' is wildcard, it's a suptype of to 'supertype' if any of its "extends"
480    // bounds is a subtype of 'supertype'.
481    if (runtimeType instanceof WildcardType) {
482      // <? super Base> is of no use in checking 'from' being a subtype of 'to'.
483      return any(((WildcardType) runtimeType).getUpperBounds()).isSubtypeOf(supertype);
484    }
485    // if 'this' is type variable, it's a subtype if any of its "extends"
486    // bounds is a subtype of 'supertype'.
487    if (runtimeType instanceof TypeVariable) {
488      return runtimeType.equals(supertype)
489          || any(((TypeVariable<?>) runtimeType).getBounds()).isSubtypeOf(supertype);
490    }
491    if (runtimeType instanceof GenericArrayType) {
492      return of(supertype).isSupertypeOfArray((GenericArrayType) runtimeType);
493    }
494    // Proceed to regular Type subtype check
495    if (supertype instanceof Class) {
496      return this.someRawTypeIsSubclassOf((Class<?>) supertype);
497    } else if (supertype instanceof ParameterizedType) {
498      return this.isSubtypeOfParameterizedType((ParameterizedType) supertype);
499    } else if (supertype instanceof GenericArrayType) {
500      return this.isSubtypeOfArrayType((GenericArrayType) supertype);
501    } else { // to instanceof TypeVariable
502      return false;
503    }
504  }
505
506  /**
507   * Returns true if this type is known to be an array type, such as {@code int[]}, {@code T[]},
508   * {@code <? extends Map<String, Integer>[]>} etc.
509   */
510  public final boolean isArray() {
511    return getComponentType() != null;
512  }
513
514  /**
515   * Returns true if this type is one of the nine primitive types (including {@code void}).
516   *
517   * @since 15.0
518   */
519  public final boolean isPrimitive() {
520    return (runtimeType instanceof Class) && ((Class<?>) runtimeType).isPrimitive();
521  }
522
523  /**
524   * Returns the corresponding wrapper type if this is a primitive type; otherwise returns {@code
525   * this} itself. Idempotent.
526   *
527   * @since 15.0
528   */
529  public final TypeToken<T> wrap() {
530    if (isPrimitive()) {
531      @SuppressWarnings("unchecked") // this is a primitive class
532      Class<T> type = (Class<T>) runtimeType;
533      return of(Primitives.wrap(type));
534    }
535    return this;
536  }
537
538  private boolean isWrapper() {
539    return Primitives.allWrapperTypes().contains(runtimeType);
540  }
541
542  /**
543   * Returns the corresponding primitive type if this is a wrapper type; otherwise returns {@code
544   * this} itself. Idempotent.
545   *
546   * @since 15.0
547   */
548  public final TypeToken<T> unwrap() {
549    if (isWrapper()) {
550      @SuppressWarnings("unchecked") // this is a wrapper class
551      Class<T> type = (Class<T>) runtimeType;
552      return of(Primitives.unwrap(type));
553    }
554    return this;
555  }
556
557  /**
558   * Returns the array component type if this type represents an array ({@code int[]}, {@code T[]},
559   * {@code <? extends Map<String, Integer>[]>} etc.), or else {@code null} is returned.
560   */
561  public final @Nullable TypeToken<?> getComponentType() {
562    Type componentType = Types.getComponentType(runtimeType);
563    if (componentType == null) {
564      return null;
565    }
566    return of(componentType);
567  }
568
569  /**
570   * Returns the {@link Invokable} for {@code method}, which must be a member of {@code T}.
571   *
572   * @since 14.0
573   */
574  public final Invokable<T, Object> method(Method method) {
575    checkArgument(
576        this.someRawTypeIsSubclassOf(method.getDeclaringClass()),
577        "%s not declared by %s",
578        method,
579        this);
580    return new Invokable.MethodInvokable<T>(method) {
581      @Override
582      Type getGenericReturnType() {
583        return getCovariantTypeResolver().resolveType(super.getGenericReturnType());
584      }
585
586      @Override
587      Type[] getGenericParameterTypes() {
588        return getInvariantTypeResolver().resolveTypesInPlace(super.getGenericParameterTypes());
589      }
590
591      @Override
592      Type[] getGenericExceptionTypes() {
593        return getCovariantTypeResolver().resolveTypesInPlace(super.getGenericExceptionTypes());
594      }
595
596      @Override
597      public TypeToken<T> getOwnerType() {
598        return TypeToken.this;
599      }
600
601      @Override
602      public String toString() {
603        return getOwnerType() + "." + super.toString();
604      }
605    };
606  }
607
608  /**
609   * Returns the {@link Invokable} for {@code constructor}, which must be a member of {@code T}.
610   *
611   * @since 14.0
612   */
613  public final Invokable<T, T> constructor(Constructor<?> constructor) {
614    checkArgument(
615        constructor.getDeclaringClass() == getRawType(),
616        "%s not declared by %s",
617        constructor,
618        getRawType());
619    return new Invokable.ConstructorInvokable<T>(constructor) {
620      @Override
621      Type getGenericReturnType() {
622        return getCovariantTypeResolver().resolveType(super.getGenericReturnType());
623      }
624
625      @Override
626      Type[] getGenericParameterTypes() {
627        return getInvariantTypeResolver().resolveTypesInPlace(super.getGenericParameterTypes());
628      }
629
630      @Override
631      Type[] getGenericExceptionTypes() {
632        return getCovariantTypeResolver().resolveTypesInPlace(super.getGenericExceptionTypes());
633      }
634
635      @Override
636      public TypeToken<T> getOwnerType() {
637        return TypeToken.this;
638      }
639
640      @Override
641      public String toString() {
642        return getOwnerType() + "(" + Joiner.on(", ").join(getGenericParameterTypes()) + ")";
643      }
644    };
645  }
646
647  /**
648   * The set of interfaces and classes that {@code T} is or is a subtype of. {@link Object} is not
649   * included in the set if this type is an interface.
650   *
651   * @since 13.0
652   */
653  public class TypeSet extends ForwardingSet<TypeToken<? super T>> implements Serializable {
654
655    private transient @Nullable ImmutableSet<TypeToken<? super T>> types;
656
657    TypeSet() {}
658
659    /** Returns the types that are interfaces implemented by this type. */
660    public TypeSet interfaces() {
661      return new InterfaceSet(this);
662    }
663
664    /** Returns the types that are classes. */
665    public TypeSet classes() {
666      return new ClassSet();
667    }
668
669    @Override
670    protected Set<TypeToken<? super T>> delegate() {
671      ImmutableSet<TypeToken<? super T>> filteredTypes = types;
672      if (filteredTypes == null) {
673        // Java has no way to express ? super T when we parameterize TypeToken vs. Class.
674        @SuppressWarnings({"unchecked", "rawtypes"})
675        ImmutableList<TypeToken<? super T>> collectedTypes =
676            (ImmutableList) TypeCollector.FOR_GENERIC_TYPE.collectTypes(TypeToken.this);
677        return (types =
678            FluentIterable.from(collectedTypes)
679                .filter(TypeFilter.IGNORE_TYPE_VARIABLE_OR_WILDCARD)
680                .toSet());
681      } else {
682        return filteredTypes;
683      }
684    }
685
686    /** Returns the raw types of the types in this set, in the same order. */
687    public Set<Class<? super T>> rawTypes() {
688      // Java has no way to express ? super T when we parameterize TypeToken vs. Class.
689      @SuppressWarnings({"unchecked", "rawtypes"})
690      ImmutableList<Class<? super T>> collectedTypes =
691          (ImmutableList) TypeCollector.FOR_RAW_TYPE.collectTypes(getRawTypes());
692      return ImmutableSet.copyOf(collectedTypes);
693    }
694
695    private static final long serialVersionUID = 0;
696  }
697
698  private final class InterfaceSet extends TypeSet {
699
700    private final transient TypeSet allTypes;
701    private transient @Nullable ImmutableSet<TypeToken<? super T>> interfaces;
702
703    InterfaceSet(TypeSet allTypes) {
704      this.allTypes = allTypes;
705    }
706
707    @Override
708    protected Set<TypeToken<? super T>> delegate() {
709      ImmutableSet<TypeToken<? super T>> result = interfaces;
710      if (result == null) {
711        return (interfaces =
712            FluentIterable.from(allTypes).filter(TypeFilter.INTERFACE_ONLY).toSet());
713      } else {
714        return result;
715      }
716    }
717
718    @Override
719    public TypeSet interfaces() {
720      return this;
721    }
722
723    @Override
724    public Set<Class<? super T>> rawTypes() {
725      // Java has no way to express ? super T when we parameterize TypeToken vs. Class.
726      @SuppressWarnings({"unchecked", "rawtypes"})
727      ImmutableList<Class<? super T>> collectedTypes =
728          (ImmutableList) TypeCollector.FOR_RAW_TYPE.collectTypes(getRawTypes());
729      return FluentIterable.from(collectedTypes)
730          .filter(
731              new Predicate<Class<?>>() {
732                @Override
733                public boolean apply(Class<?> type) {
734                  return type.isInterface();
735                }
736              })
737          .toSet();
738    }
739
740    @Override
741    public TypeSet classes() {
742      throw new UnsupportedOperationException("interfaces().classes() not supported.");
743    }
744
745    private Object readResolve() {
746      return getTypes().interfaces();
747    }
748
749    private static final long serialVersionUID = 0;
750  }
751
752  private final class ClassSet extends TypeSet {
753
754    private transient @Nullable ImmutableSet<TypeToken<? super T>> classes;
755
756    @Override
757    protected Set<TypeToken<? super T>> delegate() {
758      ImmutableSet<TypeToken<? super T>> result = classes;
759      if (result == null) {
760        @SuppressWarnings({"unchecked", "rawtypes"})
761        ImmutableList<TypeToken<? super T>> collectedTypes =
762            (ImmutableList)
763                TypeCollector.FOR_GENERIC_TYPE.classesOnly().collectTypes(TypeToken.this);
764        return (classes =
765            FluentIterable.from(collectedTypes)
766                .filter(TypeFilter.IGNORE_TYPE_VARIABLE_OR_WILDCARD)
767                .toSet());
768      } else {
769        return result;
770      }
771    }
772
773    @Override
774    public TypeSet classes() {
775      return this;
776    }
777
778    @Override
779    public Set<Class<? super T>> rawTypes() {
780      // Java has no way to express ? super T when we parameterize TypeToken vs. Class.
781      @SuppressWarnings({"unchecked", "rawtypes"})
782      ImmutableList<Class<? super T>> collectedTypes =
783          (ImmutableList) TypeCollector.FOR_RAW_TYPE.classesOnly().collectTypes(getRawTypes());
784      return ImmutableSet.copyOf(collectedTypes);
785    }
786
787    @Override
788    public TypeSet interfaces() {
789      throw new UnsupportedOperationException("classes().interfaces() not supported.");
790    }
791
792    private Object readResolve() {
793      return getTypes().classes();
794    }
795
796    private static final long serialVersionUID = 0;
797  }
798
799  private enum TypeFilter implements Predicate<TypeToken<?>> {
800    IGNORE_TYPE_VARIABLE_OR_WILDCARD {
801      @Override
802      public boolean apply(TypeToken<?> type) {
803        return !(type.runtimeType instanceof TypeVariable
804            || type.runtimeType instanceof WildcardType);
805      }
806    },
807    INTERFACE_ONLY {
808      @Override
809      public boolean apply(TypeToken<?> type) {
810        return type.getRawType().isInterface();
811      }
812    }
813  }
814
815  /**
816   * Returns true if {@code o} is another {@code TypeToken} that represents the same {@link Type}.
817   */
818  @Override
819  public boolean equals(@Nullable Object o) {
820    if (o instanceof TypeToken) {
821      TypeToken<?> that = (TypeToken<?>) o;
822      return runtimeType.equals(that.runtimeType);
823    }
824    return false;
825  }
826
827  @Override
828  public int hashCode() {
829    return runtimeType.hashCode();
830  }
831
832  @Override
833  public String toString() {
834    return Types.toString(runtimeType);
835  }
836
837  /** Implemented to support serialization of subclasses. */
838  protected Object writeReplace() {
839    // TypeResolver just transforms the type to our own impls that are Serializable
840    // except TypeVariable.
841    return of(new TypeResolver().resolveType(runtimeType));
842  }
843
844  /**
845   * Ensures that this type token doesn't contain type variables, which can cause unchecked type
846   * errors for callers like {@link TypeToInstanceMap}.
847   */
848  @CanIgnoreReturnValue
849  final TypeToken<T> rejectTypeVariables() {
850    new TypeVisitor() {
851      @Override
852      void visitTypeVariable(TypeVariable<?> type) {
853        throw new IllegalArgumentException(
854            runtimeType + "contains a type variable and is not safe for the operation");
855      }
856
857      @Override
858      void visitWildcardType(WildcardType type) {
859        visit(type.getLowerBounds());
860        visit(type.getUpperBounds());
861      }
862
863      @Override
864      void visitParameterizedType(ParameterizedType type) {
865        visit(type.getActualTypeArguments());
866        visit(type.getOwnerType());
867      }
868
869      @Override
870      void visitGenericArrayType(GenericArrayType type) {
871        visit(type.getGenericComponentType());
872      }
873    }.visit(runtimeType);
874    return this;
875  }
876
877  private boolean someRawTypeIsSubclassOf(Class<?> superclass) {
878    for (Class<?> rawType : getRawTypes()) {
879      if (superclass.isAssignableFrom(rawType)) {
880        return true;
881      }
882    }
883    return false;
884  }
885
886  private boolean isSubtypeOfParameterizedType(ParameterizedType supertype) {
887    Class<?> matchedClass = of(supertype).getRawType();
888    if (!someRawTypeIsSubclassOf(matchedClass)) {
889      return false;
890    }
891    TypeVariable<?>[] typeVars = matchedClass.getTypeParameters();
892    Type[] supertypeArgs = supertype.getActualTypeArguments();
893    for (int i = 0; i < typeVars.length; i++) {
894      Type subtypeParam = getCovariantTypeResolver().resolveType(typeVars[i]);
895      // If 'supertype' is "List<? extends CharSequence>"
896      // and 'this' is StringArrayList,
897      // First step is to figure out StringArrayList "is-a" List<E> where <E> = String.
898      // String is then matched against <? extends CharSequence>, the supertypeArgs[0].
899      if (!of(subtypeParam).is(supertypeArgs[i], typeVars[i])) {
900        return false;
901      }
902    }
903    // We only care about the case when the supertype is a non-static inner class
904    // in which case we need to make sure the subclass's owner type is a subtype of the
905    // supertype's owner.
906    return Modifier.isStatic(((Class<?>) supertype.getRawType()).getModifiers())
907        || supertype.getOwnerType() == null
908        || isOwnedBySubtypeOf(supertype.getOwnerType());
909  }
910
911  private boolean isSubtypeOfArrayType(GenericArrayType supertype) {
912    if (runtimeType instanceof Class) {
913      Class<?> fromClass = (Class<?>) runtimeType;
914      if (!fromClass.isArray()) {
915        return false;
916      }
917      return of(fromClass.getComponentType()).isSubtypeOf(supertype.getGenericComponentType());
918    } else if (runtimeType instanceof GenericArrayType) {
919      GenericArrayType fromArrayType = (GenericArrayType) runtimeType;
920      return of(fromArrayType.getGenericComponentType())
921          .isSubtypeOf(supertype.getGenericComponentType());
922    } else {
923      return false;
924    }
925  }
926
927  private boolean isSupertypeOfArray(GenericArrayType subtype) {
928    if (runtimeType instanceof Class) {
929      Class<?> thisClass = (Class<?>) runtimeType;
930      if (!thisClass.isArray()) {
931        return thisClass.isAssignableFrom(Object[].class);
932      }
933      return of(subtype.getGenericComponentType()).isSubtypeOf(thisClass.getComponentType());
934    } else if (runtimeType instanceof GenericArrayType) {
935      return of(subtype.getGenericComponentType())
936          .isSubtypeOf(((GenericArrayType) runtimeType).getGenericComponentType());
937    } else {
938      return false;
939    }
940  }
941
942  /**
943   * {@code A.is(B)} is defined as {@code Foo<A>.isSubtypeOf(Foo<B>)}.
944   *
945   * <p>Specifically, returns true if any of the following conditions is met:
946   *
947   * <ol>
948   *   <li>'this' and {@code formalType} are equal.
949   *   <li>'this' and {@code formalType} have equal canonical form.
950   *   <li>{@code formalType} is {@code <? extends Foo>} and 'this' is a subtype of {@code Foo}.
951   *   <li>{@code formalType} is {@code <? super Foo>} and 'this' is a supertype of {@code Foo}.
952   * </ol>
953   *
954   * Note that condition 2 isn't technically accurate under the context of a recursively bounded
955   * type variables. For example, {@code Enum<? extends Enum<E>>} canonicalizes to {@code Enum<?>}
956   * where {@code E} is the type variable declared on the {@code Enum} class declaration. It's
957   * technically <em>not</em> true that {@code Foo<Enum<? extends Enum<E>>>} is a subtype of {@code
958   * Foo<Enum<?>>} according to JLS. See testRecursiveWildcardSubtypeBug() for a real example.
959   *
960   * <p>It appears that properly handling recursive type bounds in the presence of implicit type
961   * bounds is not easy. For now we punt, hoping that this defect should rarely cause issues in real
962   * code.
963   *
964   * @param formalType is {@code Foo<formalType>} a supertype of {@code Foo<T>}?
965   * @param declaration The type variable in the context of a parameterized type. Used to infer type
966   *     bound when {@code formalType} is a wildcard with implicit upper bound.
967   */
968  private boolean is(Type formalType, TypeVariable<?> declaration) {
969    if (runtimeType.equals(formalType)) {
970      return true;
971    }
972    if (formalType instanceof WildcardType) {
973      WildcardType your = canonicalizeWildcardType(declaration, (WildcardType) formalType);
974      // if "formalType" is <? extends Foo>, "this" can be:
975      // Foo, SubFoo, <? extends Foo>, <? extends SubFoo>, <T extends Foo> or
976      // <T extends SubFoo>.
977      // if "formalType" is <? super Foo>, "this" can be:
978      // Foo, SuperFoo, <? super Foo> or <? super SuperFoo>.
979      return every(your.getUpperBounds()).isSupertypeOf(runtimeType)
980          && every(your.getLowerBounds()).isSubtypeOf(runtimeType);
981    }
982    return canonicalizeWildcardsInType(runtimeType).equals(canonicalizeWildcardsInType(formalType));
983  }
984
985  /**
986   * In reflection, {@code Foo<?>.getUpperBounds()[0]} is always {@code Object.class}, even when Foo
987   * is defined as {@code Foo<T extends String>}. Thus directly calling {@code <?>.is(String.class)}
988   * will return false. To mitigate, we canonicalize wildcards by enforcing the following
989   * invariants:
990   *
991   * <ol>
992   *   <li>{@code canonicalize(t)} always produces the equal result for equivalent types. For
993   *       example both {@code Enum<?>} and {@code Enum<? extends Enum<?>>} canonicalize to {@code
994   *       Enum<? extends Enum<E>}.
995   *   <li>{@code canonicalize(t)} produces a "literal" supertype of t. For example: {@code Enum<?
996   *       extends Enum<?>>} canonicalizes to {@code Enum<?>}, which is a supertype (if we disregard
997   *       the upper bound is implicitly an Enum too).
998   *   <li>If {@code canonicalize(A) == canonicalize(B)}, then {@code Foo<A>.isSubtypeOf(Foo<B>)}
999   *       and vice versa. i.e. {@code A.is(B)} and {@code B.is(A)}.
1000   *   <li>{@code canonicalize(canonicalize(A)) == canonicalize(A)}.
1001   * </ol>
1002   */
1003  private static Type canonicalizeTypeArg(TypeVariable<?> declaration, Type typeArg) {
1004    return typeArg instanceof WildcardType
1005        ? canonicalizeWildcardType(declaration, ((WildcardType) typeArg))
1006        : canonicalizeWildcardsInType(typeArg);
1007  }
1008
1009  private static Type canonicalizeWildcardsInType(Type type) {
1010    if (type instanceof ParameterizedType) {
1011      return canonicalizeWildcardsInParameterizedType((ParameterizedType) type);
1012    }
1013    if (type instanceof GenericArrayType) {
1014      return Types.newArrayType(
1015          canonicalizeWildcardsInType(((GenericArrayType) type).getGenericComponentType()));
1016    }
1017    return type;
1018  }
1019
1020  // WARNING: the returned type may have empty upper bounds, which may violate common expectations
1021  // by user code or even some of our own code. It's fine for the purpose of checking subtypes.
1022  // Just don't ever let the user access it.
1023  private static WildcardType canonicalizeWildcardType(
1024      TypeVariable<?> declaration, WildcardType type) {
1025    Type[] declared = declaration.getBounds();
1026    List<Type> upperBounds = new ArrayList<>();
1027    for (Type bound : type.getUpperBounds()) {
1028      if (!any(declared).isSubtypeOf(bound)) {
1029        upperBounds.add(canonicalizeWildcardsInType(bound));
1030      }
1031    }
1032    return new Types.WildcardTypeImpl(type.getLowerBounds(), upperBounds.toArray(new Type[0]));
1033  }
1034
1035  private static ParameterizedType canonicalizeWildcardsInParameterizedType(
1036      ParameterizedType type) {
1037    Class<?> rawType = (Class<?>) type.getRawType();
1038    TypeVariable<?>[] typeVars = rawType.getTypeParameters();
1039    Type[] typeArgs = type.getActualTypeArguments();
1040    for (int i = 0; i < typeArgs.length; i++) {
1041      typeArgs[i] = canonicalizeTypeArg(typeVars[i], typeArgs[i]);
1042    }
1043    return Types.newParameterizedTypeWithOwner(type.getOwnerType(), rawType, typeArgs);
1044  }
1045
1046  private static Bounds every(Type[] bounds) {
1047    // Every bound must match. On any false, result is false.
1048    return new Bounds(bounds, false);
1049  }
1050
1051  private static Bounds any(Type[] bounds) {
1052    // Any bound matches. On any true, result is true.
1053    return new Bounds(bounds, true);
1054  }
1055
1056  private static class Bounds {
1057    private final Type[] bounds;
1058    private final boolean target;
1059
1060    Bounds(Type[] bounds, boolean target) {
1061      this.bounds = bounds;
1062      this.target = target;
1063    }
1064
1065    boolean isSubtypeOf(Type supertype) {
1066      for (Type bound : bounds) {
1067        if (of(bound).isSubtypeOf(supertype) == target) {
1068          return target;
1069        }
1070      }
1071      return !target;
1072    }
1073
1074    boolean isSupertypeOf(Type subtype) {
1075      TypeToken<?> type = of(subtype);
1076      for (Type bound : bounds) {
1077        if (type.isSubtypeOf(bound) == target) {
1078          return target;
1079        }
1080      }
1081      return !target;
1082    }
1083  }
1084
1085  private ImmutableSet<Class<? super T>> getRawTypes() {
1086    final ImmutableSet.Builder<Class<?>> builder = ImmutableSet.builder();
1087    new TypeVisitor() {
1088      @Override
1089      void visitTypeVariable(TypeVariable<?> t) {
1090        visit(t.getBounds());
1091      }
1092
1093      @Override
1094      void visitWildcardType(WildcardType t) {
1095        visit(t.getUpperBounds());
1096      }
1097
1098      @Override
1099      void visitParameterizedType(ParameterizedType t) {
1100        builder.add((Class<?>) t.getRawType());
1101      }
1102
1103      @Override
1104      void visitClass(Class<?> t) {
1105        builder.add(t);
1106      }
1107
1108      @Override
1109      void visitGenericArrayType(GenericArrayType t) {
1110        builder.add(Types.getArrayClass(of(t.getGenericComponentType()).getRawType()));
1111      }
1112    }.visit(runtimeType);
1113    // Cast from ImmutableSet<Class<?>> to ImmutableSet<Class<? super T>>
1114    @SuppressWarnings({"unchecked", "rawtypes"})
1115    ImmutableSet<Class<? super T>> result = (ImmutableSet) builder.build();
1116    return result;
1117  }
1118
1119  private boolean isOwnedBySubtypeOf(Type supertype) {
1120    for (TypeToken<?> type : getTypes()) {
1121      Type ownerType = type.getOwnerTypeIfPresent();
1122      if (ownerType != null && of(ownerType).isSubtypeOf(supertype)) {
1123        return true;
1124      }
1125    }
1126    return false;
1127  }
1128
1129  /**
1130   * Returns the owner type of a {@link ParameterizedType} or enclosing class of a {@link Class}, or
1131   * null otherwise.
1132   */
1133  private @Nullable Type getOwnerTypeIfPresent() {
1134    if (runtimeType instanceof ParameterizedType) {
1135      return ((ParameterizedType) runtimeType).getOwnerType();
1136    } else if (runtimeType instanceof Class<?>) {
1137      return ((Class<?>) runtimeType).getEnclosingClass();
1138    } else {
1139      return null;
1140    }
1141  }
1142
1143  /**
1144   * Returns the type token representing the generic type declaration of {@code cls}. For example:
1145   * {@code TypeToken.getGenericType(Iterable.class)} returns {@code Iterable<T>}.
1146   *
1147   * <p>If {@code cls} isn't parameterized and isn't a generic array, the type token of the class is
1148   * returned.
1149   */
1150  @VisibleForTesting
1151  static <T> TypeToken<? extends T> toGenericType(Class<T> cls) {
1152    if (cls.isArray()) {
1153      Type arrayOfGenericType =
1154          Types.newArrayType(
1155              // If we are passed with int[].class, don't turn it to GenericArrayType
1156              toGenericType(cls.getComponentType()).runtimeType);
1157      @SuppressWarnings("unchecked") // array is covariant
1158      TypeToken<? extends T> result = (TypeToken<? extends T>) of(arrayOfGenericType);
1159      return result;
1160    }
1161    TypeVariable<Class<T>>[] typeParams = cls.getTypeParameters();
1162    Type ownerType =
1163        cls.isMemberClass() && !Modifier.isStatic(cls.getModifiers())
1164            ? toGenericType(cls.getEnclosingClass()).runtimeType
1165            : null;
1166
1167    if ((typeParams.length > 0) || ((ownerType != null) && ownerType != cls.getEnclosingClass())) {
1168      @SuppressWarnings("unchecked") // Like, it's Iterable<T> for Iterable.class
1169      TypeToken<? extends T> type =
1170          (TypeToken<? extends T>)
1171              of(Types.newParameterizedTypeWithOwner(ownerType, cls, typeParams));
1172      return type;
1173    } else {
1174      return of(cls);
1175    }
1176  }
1177
1178  private TypeResolver getCovariantTypeResolver() {
1179    TypeResolver resolver = covariantTypeResolver;
1180    if (resolver == null) {
1181      resolver = (covariantTypeResolver = TypeResolver.covariantly(runtimeType));
1182    }
1183    return resolver;
1184  }
1185
1186  private TypeResolver getInvariantTypeResolver() {
1187    TypeResolver resolver = invariantTypeResolver;
1188    if (resolver == null) {
1189      resolver = (invariantTypeResolver = TypeResolver.invariantly(runtimeType));
1190    }
1191    return resolver;
1192  }
1193
1194  private TypeToken<? super T> getSupertypeFromUpperBounds(
1195      Class<? super T> supertype, Type[] upperBounds) {
1196    for (Type upperBound : upperBounds) {
1197      @SuppressWarnings("unchecked") // T's upperbound is <? super T>.
1198      TypeToken<? super T> bound = (TypeToken<? super T>) of(upperBound);
1199      if (bound.isSubtypeOf(supertype)) {
1200        @SuppressWarnings({"rawtypes", "unchecked"}) // guarded by the isSubtypeOf check.
1201        TypeToken<? super T> result = bound.getSupertype((Class) supertype);
1202        return result;
1203      }
1204    }
1205    throw new IllegalArgumentException(supertype + " isn't a super type of " + this);
1206  }
1207
1208  private TypeToken<? extends T> getSubtypeFromLowerBounds(Class<?> subclass, Type[] lowerBounds) {
1209    if (lowerBounds.length > 0) {
1210      @SuppressWarnings("unchecked") // T's lower bound is <? extends T>
1211      TypeToken<? extends T> bound = (TypeToken<? extends T>) of(lowerBounds[0]);
1212      // Java supports only one lowerbound anyway.
1213      return bound.getSubtype(subclass);
1214    }
1215    throw new IllegalArgumentException(subclass + " isn't a subclass of " + this);
1216  }
1217
1218  private TypeToken<? super T> getArraySupertype(Class<? super T> supertype) {
1219    // with component type, we have lost generic type information
1220    // Use raw type so that compiler allows us to call getSupertype()
1221    @SuppressWarnings("rawtypes")
1222    TypeToken componentType =
1223        checkNotNull(getComponentType(), "%s isn't a super type of %s", supertype, this);
1224    // array is covariant. component type is super type, so is the array type.
1225    @SuppressWarnings("unchecked") // going from raw type back to generics
1226    TypeToken<?> componentSupertype = componentType.getSupertype(supertype.getComponentType());
1227    @SuppressWarnings("unchecked") // component type is super type, so is array type.
1228    TypeToken<? super T> result =
1229        (TypeToken<? super T>)
1230            // If we are passed with int[].class, don't turn it to GenericArrayType
1231            of(newArrayClassOrGenericArrayType(componentSupertype.runtimeType));
1232    return result;
1233  }
1234
1235  private TypeToken<? extends T> getArraySubtype(Class<?> subclass) {
1236    // array is covariant. component type is subtype, so is the array type.
1237    TypeToken<?> componentSubtype = getComponentType().getSubtype(subclass.getComponentType());
1238    @SuppressWarnings("unchecked") // component type is subtype, so is array type.
1239    TypeToken<? extends T> result =
1240        (TypeToken<? extends T>)
1241            // If we are passed with int[].class, don't turn it to GenericArrayType
1242            of(newArrayClassOrGenericArrayType(componentSubtype.runtimeType));
1243    return result;
1244  }
1245
1246  private Type resolveTypeArgsForSubclass(Class<?> subclass) {
1247    // If both runtimeType and subclass are not parameterized, return subclass
1248    // If runtimeType is not parameterized but subclass is, process subclass as a parameterized type
1249    // If runtimeType is a raw type (i.e. is a parameterized type specified as a Class<?>), we
1250    // return subclass as a raw type
1251    if (runtimeType instanceof Class
1252        && ((subclass.getTypeParameters().length == 0)
1253            || (getRawType().getTypeParameters().length != 0))) {
1254      // no resolution needed
1255      return subclass;
1256    }
1257    // class Base<A, B> {}
1258    // class Sub<X, Y> extends Base<X, Y> {}
1259    // Base<String, Integer>.subtype(Sub.class):
1260
1261    // Sub<X, Y>.getSupertype(Base.class) => Base<X, Y>
1262    // => X=String, Y=Integer
1263    // => Sub<X, Y>=Sub<String, Integer>
1264    TypeToken<?> genericSubtype = toGenericType(subclass);
1265    @SuppressWarnings({"rawtypes", "unchecked"}) // subclass isn't <? extends T>
1266    Type supertypeWithArgsFromSubtype =
1267        genericSubtype.getSupertype((Class) getRawType()).runtimeType;
1268    return new TypeResolver()
1269        .where(supertypeWithArgsFromSubtype, runtimeType)
1270        .resolveType(genericSubtype.runtimeType);
1271  }
1272
1273  /**
1274   * Creates an array class if {@code componentType} is a class, or else, a {@link
1275   * GenericArrayType}. This is what Java7 does for generic array type parameters.
1276   */
1277  private static Type newArrayClassOrGenericArrayType(Type componentType) {
1278    return Types.JavaVersion.JAVA7.newArrayType(componentType);
1279  }
1280
1281  private static final class SimpleTypeToken<T> extends TypeToken<T> {
1282
1283    SimpleTypeToken(Type type) {
1284      super(type);
1285    }
1286
1287    private static final long serialVersionUID = 0;
1288  }
1289
1290  /**
1291   * Collects parent types from a sub type.
1292   *
1293   * @param <K> The type "kind". Either a TypeToken, or Class.
1294   */
1295  private abstract static class TypeCollector<K> {
1296
1297    static final TypeCollector<TypeToken<?>> FOR_GENERIC_TYPE =
1298        new TypeCollector<TypeToken<?>>() {
1299          @Override
1300          Class<?> getRawType(TypeToken<?> type) {
1301            return type.getRawType();
1302          }
1303
1304          @Override
1305          Iterable<? extends TypeToken<?>> getInterfaces(TypeToken<?> type) {
1306            return type.getGenericInterfaces();
1307          }
1308
1309          @Override
1310          @Nullable
1311          TypeToken<?> getSuperclass(TypeToken<?> type) {
1312            return type.getGenericSuperclass();
1313          }
1314        };
1315
1316    static final TypeCollector<Class<?>> FOR_RAW_TYPE =
1317        new TypeCollector<Class<?>>() {
1318          @Override
1319          Class<?> getRawType(Class<?> type) {
1320            return type;
1321          }
1322
1323          @Override
1324          Iterable<? extends Class<?>> getInterfaces(Class<?> type) {
1325            return Arrays.asList(type.getInterfaces());
1326          }
1327
1328          @Override
1329          @Nullable
1330          Class<?> getSuperclass(Class<?> type) {
1331            return type.getSuperclass();
1332          }
1333        };
1334
1335    /** For just classes, we don't have to traverse interfaces. */
1336    final TypeCollector<K> classesOnly() {
1337      return new ForwardingTypeCollector<K>(this) {
1338        @Override
1339        Iterable<? extends K> getInterfaces(K type) {
1340          return ImmutableSet.of();
1341        }
1342
1343        @Override
1344        ImmutableList<K> collectTypes(Iterable<? extends K> types) {
1345          ImmutableList.Builder<K> builder = ImmutableList.builder();
1346          for (K type : types) {
1347            if (!getRawType(type).isInterface()) {
1348              builder.add(type);
1349            }
1350          }
1351          return super.collectTypes(builder.build());
1352        }
1353      };
1354    }
1355
1356    final ImmutableList<K> collectTypes(K type) {
1357      return collectTypes(ImmutableList.of(type));
1358    }
1359
1360    ImmutableList<K> collectTypes(Iterable<? extends K> types) {
1361      // type -> order number. 1 for Object, 2 for anything directly below, so on so forth.
1362      Map<K, Integer> map = Maps.newHashMap();
1363      for (K type : types) {
1364        collectTypes(type, map);
1365      }
1366      return sortKeysByValue(map, Ordering.natural().reverse());
1367    }
1368
1369    /** Collects all types to map, and returns the total depth from T up to Object. */
1370    @CanIgnoreReturnValue
1371    private int collectTypes(K type, Map<? super K, Integer> map) {
1372      Integer existing = map.get(type);
1373      if (existing != null) {
1374        // short circuit: if set contains type it already contains its supertypes
1375        return existing;
1376      }
1377      // Interfaces should be listed before Object.
1378      int aboveMe = getRawType(type).isInterface() ? 1 : 0;
1379      for (K interfaceType : getInterfaces(type)) {
1380        aboveMe = Math.max(aboveMe, collectTypes(interfaceType, map));
1381      }
1382      K superclass = getSuperclass(type);
1383      if (superclass != null) {
1384        aboveMe = Math.max(aboveMe, collectTypes(superclass, map));
1385      }
1386      /*
1387       * TODO(benyu): should we include Object for interface? Also, CharSequence[] and Object[] for
1388       * String[]?
1389       *
1390       */
1391      map.put(type, aboveMe + 1);
1392      return aboveMe + 1;
1393    }
1394
1395    private static <K, V> ImmutableList<K> sortKeysByValue(
1396        final Map<K, V> map, final Comparator<? super V> valueComparator) {
1397      Ordering<K> keyOrdering =
1398          new Ordering<K>() {
1399            @Override
1400            public int compare(K left, K right) {
1401              return valueComparator.compare(map.get(left), map.get(right));
1402            }
1403          };
1404      return keyOrdering.immutableSortedCopy(map.keySet());
1405    }
1406
1407    abstract Class<?> getRawType(K type);
1408
1409    abstract Iterable<? extends K> getInterfaces(K type);
1410
1411    abstract @Nullable K getSuperclass(K type);
1412
1413    private static class ForwardingTypeCollector<K> extends TypeCollector<K> {
1414
1415      private final TypeCollector<K> delegate;
1416
1417      ForwardingTypeCollector(TypeCollector<K> delegate) {
1418        this.delegate = delegate;
1419      }
1420
1421      @Override
1422      Class<?> getRawType(K type) {
1423        return delegate.getRawType(type);
1424      }
1425
1426      @Override
1427      Iterable<? extends K> getInterfaces(K type) {
1428        return delegate.getInterfaces(type);
1429      }
1430
1431      @Override
1432      K getSuperclass(K type) {
1433        return delegate.getSuperclass(type);
1434      }
1435    }
1436  }
1437
1438  // This happens to be the hash of the class as of now. So setting it makes a backward compatible
1439  // change. Going forward, if any incompatible change is added, we can change the UID back to 1.
1440  private static final long serialVersionUID = 3637540370352322684L;
1441}