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