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