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