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