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.Arrays;
044import java.util.Comparator;
045import java.util.Map;
046import java.util.Set;
047import javax.annotation.Nullable;
048
049/**
050 * A {@link Type} with generics.
051 *
052 * <p>Operations that are otherwise only available in {@link Class} are implemented to support
053 * {@code Type}, for example {@link #isSubtypeOf}, {@link #isArray} and {@link #getComponentType}.
054 * It also provides additional utilities such as {@link #getTypes}, {@link #resolveType}, etc.
055 *
056 * <p>There are three ways to get a {@code TypeToken} instance:
057 *
058 * <ul>
059 *
060 * <li>Wrap a {@code Type} obtained via reflection. For example:
061 *     {@code TypeToken.of(method.getGenericReturnType())}.
062 *
063 * <li>Capture a generic type with a (usually anonymous) subclass. For example: <pre>   {@code
064 *   new TypeToken<List<String>>() {}}</pre>
065 *
066 *     <p>Note that it's critical that the actual type argument is carried by a subclass. The
067 *     following code is wrong because it only captures the {@code <T>} type variable of the {@code
068 *     listType()} method signature; while {@code <String>} is lost in erasure:
069 *
070 * <pre>   {@code
071 *   class Util {
072 *     static <T> TypeToken<List<T>> listType() {
073 *       return new TypeToken<List<T>>() {};
074 *     }
075 *   }
076 *
077 *   TypeToken<List<String>> stringListType = Util.<String>listType();}</pre>
078 *
079 * <li>Capture a generic type with a (usually anonymous) subclass and resolve it against a context
080 *     class that knows what the type parameters are. For example: <pre>   {@code
081 *   abstract class IKnowMyType<T> {
082 *     TypeToken<T> type = new TypeToken<T>(getClass()) {};
083 *   }
084 *   new IKnowMyType<String>() {}.type => String}</pre>
085 *
086 * </ul>
087 *
088 * <p>{@code TypeToken} is serializable when no type variable is contained in the type.
089 *
090 * <p>Note to Guice users: {@code} TypeToken is similar to Guice's {@code TypeLiteral} class except
091 * that it is serializable and offers numerous additional utility methods.
092 *
093 * @author Bob Lee
094 * @author Sven Mawson
095 * @author Ben Yu
096 * @since 12.0
097 */
098@Beta
099@SuppressWarnings("serial") // SimpleTypeToken is the serialized form.
100public 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<Object>(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}