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