1 /*
   2  * Copyright (c) 2003, 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package com.sun.tools.javac.code;
  27 
  28 import java.lang.ref.SoftReference;
  29 import java.util.HashSet;
  30 import java.util.HashMap;
  31 import java.util.Locale;
  32 import java.util.Map;
  33 import java.util.Set;
  34 import java.util.WeakHashMap;
  35 
  36 import javax.tools.JavaFileObject;
  37 
  38 import com.sun.tools.javac.code.Attribute.RetentionPolicy;
  39 import com.sun.tools.javac.code.Lint.LintCategory;
  40 import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
  41 import com.sun.tools.javac.comp.AttrContext;
  42 import com.sun.tools.javac.comp.Check;
  43 import com.sun.tools.javac.comp.Enter;
  44 import com.sun.tools.javac.comp.Env;
  45 import com.sun.tools.javac.jvm.ClassReader;
  46 import com.sun.tools.javac.tree.JCTree;
  47 import com.sun.tools.javac.util.*;
  48 import static com.sun.tools.javac.code.BoundKind.*;
  49 import static com.sun.tools.javac.code.Flags.*;
  50 import static com.sun.tools.javac.code.Kinds.MTH;
  51 import static com.sun.tools.javac.code.Scope.*;
  52 import static com.sun.tools.javac.code.Symbol.*;
  53 import static com.sun.tools.javac.code.Type.*;
  54 import static com.sun.tools.javac.code.TypeTag.*;
  55 import static com.sun.tools.javac.jvm.ClassFile.externalize;
  56 
  57 /**
  58  * Utility class containing various operations on types.
  59  *
  60  * <p>Unless other names are more illustrative, the following naming
  61  * conventions should be observed in this file:
  62  *
  63  * <dl>
  64  * <dt>t</dt>
  65  * <dd>If the first argument to an operation is a type, it should be named t.</dd>
  66  * <dt>s</dt>
  67  * <dd>Similarly, if the second argument to an operation is a type, it should be named s.</dd>
  68  * <dt>ts</dt>
  69  * <dd>If an operations takes a list of types, the first should be named ts.</dd>
  70  * <dt>ss</dt>
  71  * <dd>A second list of types should be named ss.</dd>
  72  * </dl>
  73  *
  74  * <p><b>This is NOT part of any supported API.
  75  * If you write code that depends on this, you do so at your own risk.
  76  * This code and its internal interfaces are subject to change or
  77  * deletion without notice.</b>
  78  */
  79 public class Types {
  80     protected static final Context.Key<Types> typesKey =
  81         new Context.Key<Types>();
  82 
  83     final Symtab syms;
  84     final JavacMessages messages;
  85     final Names names;
  86     final boolean allowBoxing;
  87     final boolean allowCovariantReturns;
  88     final boolean allowObjectToPrimitiveCast;
  89     final boolean allowDefaultMethods;
  90     final ClassReader reader;
  91     final Check chk;
  92     final Enter enter;
  93     JCDiagnostic.Factory diags;
  94     List<Warner> warnStack = List.nil();
  95     final Name capturedName;
  96     private final FunctionDescriptorLookupError functionDescriptorLookupError;
  97 
  98     public final Warner noWarnings;
  99 
 100     // <editor-fold defaultstate="collapsed" desc="Instantiating">
 101     public static Types instance(Context context) {
 102         Types instance = context.get(typesKey);
 103         if (instance == null)
 104             instance = new Types(context);
 105         return instance;
 106     }
 107 
 108     protected Types(Context context) {
 109         context.put(typesKey, this);
 110         syms = Symtab.instance(context);
 111         names = Names.instance(context);
 112         Source source = Source.instance(context);
 113         allowBoxing = source.allowBoxing();
 114         allowCovariantReturns = source.allowCovariantReturns();
 115         allowObjectToPrimitiveCast = source.allowObjectToPrimitiveCast();
 116         allowDefaultMethods = source.allowDefaultMethods();
 117         reader = ClassReader.instance(context);
 118         chk = Check.instance(context);
 119         enter = Enter.instance(context);
 120         capturedName = names.fromString("<captured wildcard>");
 121         messages = JavacMessages.instance(context);
 122         diags = JCDiagnostic.Factory.instance(context);
 123         functionDescriptorLookupError = new FunctionDescriptorLookupError();
 124         noWarnings = new Warner(null);
 125     }
 126     // </editor-fold>
 127 
 128      // <editor-fold defaultstate="collapsed" desc="bounds">
 129      /**
 130       * Get a wildcard's upper bound, returning non-wildcards unchanged.
 131       * @param t a type argument, either a wildcard or a type
 132       */
 133      public Type wildUpperBound(Type t) {
 134          if (t.hasTag(WILDCARD)) {
 135              WildcardType w = (WildcardType) t.unannotatedType();
 136              if (w.isSuperBound())
 137                  return w.bound == null ? syms.objectType : w.bound.bound;
 138              else
 139                  return wildUpperBound(w.type);
 140          }
 141          else return t.unannotatedType();
 142      }
 143 
 144      /**
 145       * Get a capture variable's upper bound, returning other types unchanged.
 146       * @param t a type
 147       */
 148      public Type cvarUpperBound(Type t) {
 149          if (t.hasTag(TYPEVAR)) {
 150              TypeVar v = (TypeVar) t.unannotatedType();
 151              return v.isCaptured() ? cvarUpperBound(v.bound) : v;
 152          }
 153          else return t.unannotatedType();
 154      }
 155 
 156     /**
 157      * Get a wildcard's lower bound, returning non-wildcards unchanged.
 158      * @param t a type argument, either a wildcard or a type
 159      */
 160     public Type wildLowerBound(Type t) {
 161         if (t.hasTag(WILDCARD)) {
 162             WildcardType w = (WildcardType) t.unannotatedType();
 163             return w.isExtendsBound() ? syms.botType : wildLowerBound(w.type);
 164         }
 165         else return t.unannotatedType();
 166     }
 167 
 168     /**
 169      * Get a capture variable's lower bound, returning other types unchanged.
 170      * @param t a type
 171      */
 172     public Type cvarLowerBound(Type t) {
 173         if (t.hasTag(TYPEVAR)) {
 174             TypeVar v = (TypeVar) t.unannotatedType();
 175             return v.isCaptured() ? cvarLowerBound(v.getLowerBound()) : v;
 176         }
 177         else return t.unannotatedType();
 178     }
 179     // </editor-fold>
 180 
 181     // <editor-fold defaultstate="collapsed" desc="isUnbounded">
 182     /**
 183      * Checks that all the arguments to a class are unbounded
 184      * wildcards or something else that doesn't make any restrictions
 185      * on the arguments. If a class isUnbounded, a raw super- or
 186      * subclass can be cast to it without a warning.
 187      * @param t a type
 188      * @return true iff the given type is unbounded or raw
 189      */
 190     public boolean isUnbounded(Type t) {
 191         return isUnbounded.visit(t);
 192     }
 193     // where
 194         private final UnaryVisitor<Boolean> isUnbounded = new UnaryVisitor<Boolean>() {
 195 
 196             public Boolean visitType(Type t, Void ignored) {
 197                 return true;
 198             }
 199 
 200             @Override
 201             public Boolean visitClassType(ClassType t, Void ignored) {
 202                 List<Type> parms = t.tsym.type.allparams();
 203                 List<Type> args = t.allparams();
 204                 while (parms.nonEmpty()) {
 205                     WildcardType unb = new WildcardType(syms.objectType,
 206                                                         BoundKind.UNBOUND,
 207                                                         syms.boundClass,
 208                                                         (TypeVar)parms.head.unannotatedType());
 209                     if (!containsType(args.head, unb))
 210                         return false;
 211                     parms = parms.tail;
 212                     args = args.tail;
 213                 }
 214                 return true;
 215             }
 216         };
 217     // </editor-fold>
 218 
 219     // <editor-fold defaultstate="collapsed" desc="asSub">
 220     /**
 221      * Return the least specific subtype of t that starts with symbol
 222      * sym.  If none exists, return null.  The least specific subtype
 223      * is determined as follows:
 224      *
 225      * <p>If there is exactly one parameterized instance of sym that is a
 226      * subtype of t, that parameterized instance is returned.<br>
 227      * Otherwise, if the plain type or raw type `sym' is a subtype of
 228      * type t, the type `sym' itself is returned.  Otherwise, null is
 229      * returned.
 230      */
 231     public Type asSub(Type t, Symbol sym) {
 232         return asSub.visit(t, sym);
 233     }
 234     // where
 235         private final SimpleVisitor<Type,Symbol> asSub = new SimpleVisitor<Type,Symbol>() {
 236 
 237             public Type visitType(Type t, Symbol sym) {
 238                 return null;
 239             }
 240 
 241             @Override
 242             public Type visitClassType(ClassType t, Symbol sym) {
 243                 if (t.tsym == sym)
 244                     return t;
 245                 Type base = asSuper(sym.type, t.tsym);
 246                 if (base == null)
 247                     return null;
 248                 ListBuffer<Type> from = new ListBuffer<Type>();
 249                 ListBuffer<Type> to = new ListBuffer<Type>();
 250                 try {
 251                     adapt(base, t, from, to);
 252                 } catch (AdaptFailure ex) {
 253                     return null;
 254                 }
 255                 Type res = subst(sym.type, from.toList(), to.toList());
 256                 if (!isSubtype(res, t))
 257                     return null;
 258                 ListBuffer<Type> openVars = new ListBuffer<Type>();
 259                 for (List<Type> l = sym.type.allparams();
 260                      l.nonEmpty(); l = l.tail)
 261                     if (res.contains(l.head) && !t.contains(l.head))
 262                         openVars.append(l.head);
 263                 if (openVars.nonEmpty()) {
 264                     if (t.isRaw()) {
 265                         // The subtype of a raw type is raw
 266                         res = erasure(res);
 267                     } else {
 268                         // Unbound type arguments default to ?
 269                         List<Type> opens = openVars.toList();
 270                         ListBuffer<Type> qs = new ListBuffer<Type>();
 271                         for (List<Type> iter = opens; iter.nonEmpty(); iter = iter.tail) {
 272                             qs.append(new WildcardType(syms.objectType, BoundKind.UNBOUND, syms.boundClass, (TypeVar) iter.head.unannotatedType()));
 273                         }
 274                         res = subst(res, opens, qs.toList());
 275                     }
 276                 }
 277                 return res;
 278             }
 279 
 280             @Override
 281             public Type visitErrorType(ErrorType t, Symbol sym) {
 282                 return t;
 283             }
 284         };
 285     // </editor-fold>
 286 
 287     // <editor-fold defaultstate="collapsed" desc="isConvertible">
 288     /**
 289      * Is t a subtype of or convertible via boxing/unboxing
 290      * conversion to s?
 291      */
 292     public boolean isConvertible(Type t, Type s, Warner warn) {
 293         if (t.hasTag(ERROR)) {
 294             return true;
 295         }
 296         boolean tPrimitive = t.isPrimitive();
 297         boolean sPrimitive = s.isPrimitive();
 298         if (tPrimitive == sPrimitive) {
 299             return isSubtypeUnchecked(t, s, warn);
 300         }
 301         if (!allowBoxing) return false;
 302         return tPrimitive
 303             ? isSubtype(boxedClass(t).type, s)
 304             : isSubtype(unboxedType(t), s);
 305     }
 306 
 307     /**
 308      * Is t a subtype of or convertible via boxing/unboxing
 309      * conversions to s?
 310      */
 311     public boolean isConvertible(Type t, Type s) {
 312         return isConvertible(t, s, noWarnings);
 313     }
 314     // </editor-fold>
 315 
 316     // <editor-fold defaultstate="collapsed" desc="findSam">
 317 
 318     /**
 319      * Exception used to report a function descriptor lookup failure. The exception
 320      * wraps a diagnostic that can be used to generate more details error
 321      * messages.
 322      */
 323     public static class FunctionDescriptorLookupError extends RuntimeException {
 324         private static final long serialVersionUID = 0;
 325 
 326         JCDiagnostic diagnostic;
 327 
 328         FunctionDescriptorLookupError() {
 329             this.diagnostic = null;
 330         }
 331 
 332         FunctionDescriptorLookupError setMessage(JCDiagnostic diag) {
 333             this.diagnostic = diag;
 334             return this;
 335         }
 336 
 337         public JCDiagnostic getDiagnostic() {
 338             return diagnostic;
 339         }
 340     }
 341 
 342     /**
 343      * A cache that keeps track of function descriptors associated with given
 344      * functional interfaces.
 345      */
 346     class DescriptorCache {
 347 
 348         private WeakHashMap<TypeSymbol, Entry> _map = new WeakHashMap<TypeSymbol, Entry>();
 349 
 350         class FunctionDescriptor {
 351             Symbol descSym;
 352 
 353             FunctionDescriptor(Symbol descSym) {
 354                 this.descSym = descSym;
 355             }
 356 
 357             public Symbol getSymbol() {
 358                 return descSym;
 359             }
 360 
 361             public Type getType(Type site) {
 362                 site = removeWildcards(site);
 363                 if (!chk.checkValidGenericType(site)) {
 364                     //if the inferred functional interface type is not well-formed,
 365                     //or if it's not a subtype of the original target, issue an error
 366                     throw failure(diags.fragment("no.suitable.functional.intf.inst", site));
 367                 }
 368                 return memberType(site, descSym);
 369             }
 370         }
 371 
 372         class Entry {
 373             final FunctionDescriptor cachedDescRes;
 374             final int prevMark;
 375 
 376             public Entry(FunctionDescriptor cachedDescRes,
 377                     int prevMark) {
 378                 this.cachedDescRes = cachedDescRes;
 379                 this.prevMark = prevMark;
 380             }
 381 
 382             boolean matches(int mark) {
 383                 return  this.prevMark == mark;
 384             }
 385         }
 386 
 387         FunctionDescriptor get(TypeSymbol origin) throws FunctionDescriptorLookupError {
 388             Entry e = _map.get(origin);
 389             CompoundScope members = membersClosure(origin.type, false);
 390             if (e == null ||
 391                     !e.matches(members.getMark())) {
 392                 FunctionDescriptor descRes = findDescriptorInternal(origin, members);
 393                 _map.put(origin, new Entry(descRes, members.getMark()));
 394                 return descRes;
 395             }
 396             else {
 397                 return e.cachedDescRes;
 398             }
 399         }
 400 
 401         /**
 402          * Compute the function descriptor associated with a given functional interface
 403          */
 404         public FunctionDescriptor findDescriptorInternal(TypeSymbol origin,
 405                 CompoundScope membersCache) throws FunctionDescriptorLookupError {
 406             if (!origin.isInterface() || (origin.flags() & ANNOTATION) != 0) {
 407                 //t must be an interface
 408                 throw failure("not.a.functional.intf", origin);
 409             }
 410 
 411             final ListBuffer<Symbol> abstracts = new ListBuffer<>();
 412             for (Symbol sym : membersCache.getElements(new DescriptorFilter(origin))) {
 413                 Type mtype = memberType(origin.type, sym);
 414                 if (abstracts.isEmpty() ||
 415                         (sym.name == abstracts.first().name &&
 416                         overrideEquivalent(mtype, memberType(origin.type, abstracts.first())))) {
 417                     abstracts.append(sym);
 418                 } else {
 419                     //the target method(s) should be the only abstract members of t
 420                     throw failure("not.a.functional.intf.1",  origin,
 421                             diags.fragment("incompatible.abstracts", Kinds.kindName(origin), origin));
 422                 }
 423             }
 424             if (abstracts.isEmpty()) {
 425                 //t must define a suitable non-generic method
 426                 throw failure("not.a.functional.intf.1", origin,
 427                             diags.fragment("no.abstracts", Kinds.kindName(origin), origin));
 428             } else if (abstracts.size() == 1) {
 429                 return new FunctionDescriptor(abstracts.first());
 430             } else { // size > 1
 431                 FunctionDescriptor descRes = mergeDescriptors(origin, abstracts.toList());
 432                 if (descRes == null) {
 433                     //we can get here if the functional interface is ill-formed
 434                     ListBuffer<JCDiagnostic> descriptors = new ListBuffer<>();
 435                     for (Symbol desc : abstracts) {
 436                         String key = desc.type.getThrownTypes().nonEmpty() ?
 437                                 "descriptor.throws" : "descriptor";
 438                         descriptors.append(diags.fragment(key, desc.name,
 439                                 desc.type.getParameterTypes(),
 440                                 desc.type.getReturnType(),
 441                                 desc.type.getThrownTypes()));
 442                     }
 443                     JCDiagnostic.MultilineDiagnostic incompatibleDescriptors =
 444                             new JCDiagnostic.MultilineDiagnostic(diags.fragment("incompatible.descs.in.functional.intf",
 445                             Kinds.kindName(origin), origin), descriptors.toList());
 446                     throw failure(incompatibleDescriptors);
 447                 }
 448                 return descRes;
 449             }
 450         }
 451 
 452         /**
 453          * Compute a synthetic type for the target descriptor given a list
 454          * of override-equivalent methods in the functional interface type.
 455          * The resulting method type is a method type that is override-equivalent
 456          * and return-type substitutable with each method in the original list.
 457          */
 458         private FunctionDescriptor mergeDescriptors(TypeSymbol origin, List<Symbol> methodSyms) {
 459             //pick argument types - simply take the signature that is a
 460             //subsignature of all other signatures in the list (as per JLS 8.4.2)
 461             List<Symbol> mostSpecific = List.nil();
 462             outer: for (Symbol msym1 : methodSyms) {
 463                 Type mt1 = memberType(origin.type, msym1);
 464                 for (Symbol msym2 : methodSyms) {
 465                     Type mt2 = memberType(origin.type, msym2);
 466                     if (!isSubSignature(mt1, mt2)) {
 467                         continue outer;
 468                     }
 469                 }
 470                 mostSpecific = mostSpecific.prepend(msym1);
 471             }
 472             if (mostSpecific.isEmpty()) {
 473                 return null;
 474             }
 475 
 476 
 477             //pick return types - this is done in two phases: (i) first, the most
 478             //specific return type is chosen using strict subtyping; if this fails,
 479             //a second attempt is made using return type substitutability (see JLS 8.4.5)
 480             boolean phase2 = false;
 481             Symbol bestSoFar = null;
 482             while (bestSoFar == null) {
 483                 outer: for (Symbol msym1 : mostSpecific) {
 484                     Type mt1 = memberType(origin.type, msym1);
 485                     for (Symbol msym2 : methodSyms) {
 486                         Type mt2 = memberType(origin.type, msym2);
 487                         if (phase2 ?
 488                                 !returnTypeSubstitutable(mt1, mt2) :
 489                                 !isSubtypeInternal(mt1.getReturnType(), mt2.getReturnType())) {
 490                             continue outer;
 491                         }
 492                     }
 493                     bestSoFar = msym1;
 494                 }
 495                 if (phase2) {
 496                     break;
 497                 } else {
 498                     phase2 = true;
 499                 }
 500             }
 501             if (bestSoFar == null) return null;
 502 
 503             //merge thrown types - form the intersection of all the thrown types in
 504             //all the signatures in the list
 505             boolean toErase = !bestSoFar.type.hasTag(FORALL);
 506             List<Type> thrown = null;
 507             Type mt1 = memberType(origin.type, bestSoFar);
 508             for (Symbol msym2 : methodSyms) {
 509                 Type mt2 = memberType(origin.type, msym2);
 510                 List<Type> thrown_mt2 = mt2.getThrownTypes();
 511                 if (toErase) {
 512                     thrown_mt2 = erasure(thrown_mt2);
 513                 } else {
 514                     /* If bestSoFar is generic then all the methods are generic.
 515                      * The opposite is not true: a non generic method can override
 516                      * a generic method (raw override) so it's safe to cast mt1 and
 517                      * mt2 to ForAll.
 518                      */
 519                     ForAll fa1 = (ForAll)mt1;
 520                     ForAll fa2 = (ForAll)mt2;
 521                     thrown_mt2 = subst(thrown_mt2, fa2.tvars, fa1.tvars);
 522                 }
 523                 thrown = (thrown == null) ?
 524                     thrown_mt2 :
 525                     chk.intersect(thrown_mt2, thrown);
 526             }
 527 
 528             final List<Type> thrown1 = thrown;
 529             return new FunctionDescriptor(bestSoFar) {
 530                 @Override
 531                 public Type getType(Type origin) {
 532                     Type mt = memberType(origin, getSymbol());
 533                     return createMethodTypeWithThrown(mt, thrown1);
 534                 }
 535             };
 536         }
 537 
 538         boolean isSubtypeInternal(Type s, Type t) {
 539             return (s.isPrimitive() && t.isPrimitive()) ?
 540                     isSameType(t, s) :
 541                     isSubtype(s, t);
 542         }
 543 
 544         FunctionDescriptorLookupError failure(String msg, Object... args) {
 545             return failure(diags.fragment(msg, args));
 546         }
 547 
 548         FunctionDescriptorLookupError failure(JCDiagnostic diag) {
 549             return functionDescriptorLookupError.setMessage(diag);
 550         }
 551     }
 552 
 553     private DescriptorCache descCache = new DescriptorCache();
 554 
 555     /**
 556      * Find the method descriptor associated to this class symbol - if the
 557      * symbol 'origin' is not a functional interface, an exception is thrown.
 558      */
 559     public Symbol findDescriptorSymbol(TypeSymbol origin) throws FunctionDescriptorLookupError {
 560         return descCache.get(origin).getSymbol();
 561     }
 562 
 563     /**
 564      * Find the type of the method descriptor associated to this class symbol -
 565      * if the symbol 'origin' is not a functional interface, an exception is thrown.
 566      */
 567     public Type findDescriptorType(Type origin) throws FunctionDescriptorLookupError {
 568         return descCache.get(origin.tsym).getType(origin);
 569     }
 570 
 571     /**
 572      * Is given type a functional interface?
 573      */
 574     public boolean isFunctionalInterface(TypeSymbol tsym) {
 575         try {
 576             findDescriptorSymbol(tsym);
 577             return true;
 578         } catch (FunctionDescriptorLookupError ex) {
 579             return false;
 580         }
 581     }
 582 
 583     public boolean isFunctionalInterface(Type site) {
 584         try {
 585             findDescriptorType(site);
 586             return true;
 587         } catch (FunctionDescriptorLookupError ex) {
 588             return false;
 589         }
 590     }
 591 
 592     public Type removeWildcards(Type site) {
 593         Type capturedSite = capture(site);
 594         if (capturedSite != site) {
 595             Type formalInterface = site.tsym.type;
 596             ListBuffer<Type> typeargs = new ListBuffer<>();
 597             List<Type> actualTypeargs = site.getTypeArguments();
 598             List<Type> capturedTypeargs = capturedSite.getTypeArguments();
 599             //simply replace the wildcards with its bound
 600             for (Type t : formalInterface.getTypeArguments()) {
 601                 if (actualTypeargs.head.hasTag(WILDCARD)) {
 602                     WildcardType wt = (WildcardType)actualTypeargs.head.unannotatedType();
 603                     Type bound;
 604                     switch (wt.kind) {
 605                         case EXTENDS:
 606                         case UNBOUND:
 607                             CapturedType capVar = (CapturedType)capturedTypeargs.head.unannotatedType();
 608                             //use declared bound if it doesn't depend on formal type-args
 609                             bound = capVar.bound.containsAny(capturedSite.getTypeArguments()) ?
 610                                     wt.type : capVar.bound;
 611                             break;
 612                         default:
 613                             bound = wt.type;
 614                     }
 615                     typeargs.append(bound);
 616                 } else {
 617                     typeargs.append(actualTypeargs.head);
 618                 }
 619                 actualTypeargs = actualTypeargs.tail;
 620                 capturedTypeargs = capturedTypeargs.tail;
 621             }
 622             return subst(formalInterface, formalInterface.getTypeArguments(), typeargs.toList());
 623         } else {
 624             return site;
 625         }
 626     }
 627 
 628     /**
 629      * Create a symbol for a class that implements a given functional interface
 630      * and overrides its functional descriptor. This routine is used for two
 631      * main purposes: (i) checking well-formedness of a functional interface;
 632      * (ii) perform functional interface bridge calculation.
 633      */
 634     public ClassSymbol makeFunctionalInterfaceClass(Env<AttrContext> env, Name name, List<Type> targets, long cflags) {
 635         if (targets.isEmpty()) {
 636             return null;
 637         }
 638         Symbol descSym = findDescriptorSymbol(targets.head.tsym);
 639         Type descType = findDescriptorType(targets.head);
 640         ClassSymbol csym = new ClassSymbol(cflags, name, env.enclClass.sym.outermostClass());
 641         csym.completer = null;
 642         csym.members_field = new Scope(csym);
 643         MethodSymbol instDescSym = new MethodSymbol(descSym.flags(), descSym.name, descType, csym);
 644         csym.members_field.enter(instDescSym);
 645         Type.ClassType ctype = new Type.ClassType(Type.noType, List.<Type>nil(), csym);
 646         ctype.supertype_field = syms.objectType;
 647         ctype.interfaces_field = targets;
 648         csym.type = ctype;
 649         csym.sourcefile = ((ClassSymbol)csym.owner).sourcefile;
 650         return csym;
 651     }
 652 
 653     /**
 654      * Find the minimal set of methods that are overridden by the functional
 655      * descriptor in 'origin'. All returned methods are assumed to have different
 656      * erased signatures.
 657      */
 658     public List<Symbol> functionalInterfaceBridges(TypeSymbol origin) {
 659         Assert.check(isFunctionalInterface(origin));
 660         Symbol descSym = findDescriptorSymbol(origin);
 661         CompoundScope members = membersClosure(origin.type, false);
 662         ListBuffer<Symbol> overridden = new ListBuffer<>();
 663         outer: for (Symbol m2 : members.getElementsByName(descSym.name, bridgeFilter)) {
 664             if (m2 == descSym) continue;
 665             else if (descSym.overrides(m2, origin, Types.this, false)) {
 666                 for (Symbol m3 : overridden) {
 667                     if (isSameType(m3.erasure(Types.this), m2.erasure(Types.this)) ||
 668                             (m3.overrides(m2, origin, Types.this, false) &&
 669                             (pendingBridges((ClassSymbol)origin, m3.enclClass()) ||
 670                             (((MethodSymbol)m2).binaryImplementation((ClassSymbol)m3.owner, Types.this) != null)))) {
 671                         continue outer;
 672                     }
 673                 }
 674                 overridden.add(m2);
 675             }
 676         }
 677         return overridden.toList();
 678     }
 679     //where
 680         private Filter<Symbol> bridgeFilter = new Filter<Symbol>() {
 681             public boolean accepts(Symbol t) {
 682                 return t.kind == Kinds.MTH &&
 683                         t.name != names.init &&
 684                         t.name != names.clinit &&
 685                         (t.flags() & SYNTHETIC) == 0;
 686             }
 687         };
 688         private boolean pendingBridges(ClassSymbol origin, TypeSymbol s) {
 689             //a symbol will be completed from a classfile if (a) symbol has
 690             //an associated file object with CLASS kind and (b) the symbol has
 691             //not been entered
 692             if (origin.classfile != null &&
 693                     origin.classfile.getKind() == JavaFileObject.Kind.CLASS &&
 694                     enter.getEnv(origin) == null) {
 695                 return false;
 696             }
 697             if (origin == s) {
 698                 return true;
 699             }
 700             for (Type t : interfaces(origin.type)) {
 701                 if (pendingBridges((ClassSymbol)t.tsym, s)) {
 702                     return true;
 703                 }
 704             }
 705             return false;
 706         }
 707     // </editor-fold>
 708 
 709    /**
 710     * Scope filter used to skip methods that should be ignored (such as methods
 711     * overridden by j.l.Object) during function interface conversion interface check
 712     */
 713     class DescriptorFilter implements Filter<Symbol> {
 714 
 715        TypeSymbol origin;
 716 
 717        DescriptorFilter(TypeSymbol origin) {
 718            this.origin = origin;
 719        }
 720 
 721        @Override
 722        public boolean accepts(Symbol sym) {
 723            return sym.kind == Kinds.MTH &&
 724                    (sym.flags() & (ABSTRACT | DEFAULT)) == ABSTRACT &&
 725                    !overridesObjectMethod(origin, sym) &&
 726                    (interfaceCandidates(origin.type, (MethodSymbol)sym).head.flags() & DEFAULT) == 0;
 727        }
 728     };
 729 
 730     // <editor-fold defaultstate="collapsed" desc="isSubtype">
 731     /**
 732      * Is t an unchecked subtype of s?
 733      */
 734     public boolean isSubtypeUnchecked(Type t, Type s) {
 735         return isSubtypeUnchecked(t, s, noWarnings);
 736     }
 737     /**
 738      * Is t an unchecked subtype of s?
 739      */
 740     public boolean isSubtypeUnchecked(Type t, Type s, Warner warn) {
 741         boolean result = isSubtypeUncheckedInternal(t, s, warn);
 742         if (result) {
 743             checkUnsafeVarargsConversion(t, s, warn);
 744         }
 745         return result;
 746     }
 747     //where
 748         private boolean isSubtypeUncheckedInternal(Type t, Type s, Warner warn) {
 749             if (t.hasTag(ARRAY) && s.hasTag(ARRAY)) {
 750                 t = t.unannotatedType();
 751                 s = s.unannotatedType();
 752                 if (((ArrayType)t).elemtype.isPrimitive()) {
 753                     return isSameType(elemtype(t), elemtype(s));
 754                 } else {
 755                     return isSubtypeUnchecked(elemtype(t), elemtype(s), warn);
 756                 }
 757             } else if (isSubtype(t, s)) {
 758                 return true;
 759             } else if (t.hasTag(TYPEVAR)) {
 760                 return isSubtypeUnchecked(t.getUpperBound(), s, warn);
 761             } else if (!s.isRaw()) {
 762                 Type t2 = asSuper(t, s.tsym);
 763                 if (t2 != null && t2.isRaw()) {
 764                     if (isReifiable(s)) {
 765                         warn.silentWarn(LintCategory.UNCHECKED);
 766                     } else {
 767                         warn.warn(LintCategory.UNCHECKED);
 768                     }
 769                     return true;
 770                 }
 771             }
 772             return false;
 773         }
 774 
 775         private void checkUnsafeVarargsConversion(Type t, Type s, Warner warn) {
 776             if (!t.hasTag(ARRAY) || isReifiable(t)) {
 777                 return;
 778             }
 779             t = t.unannotatedType();
 780             s = s.unannotatedType();
 781             ArrayType from = (ArrayType)t;
 782             boolean shouldWarn = false;
 783             switch (s.getTag()) {
 784                 case ARRAY:
 785                     ArrayType to = (ArrayType)s;
 786                     shouldWarn = from.isVarargs() &&
 787                             !to.isVarargs() &&
 788                             !isReifiable(from);
 789                     break;
 790                 case CLASS:
 791                     shouldWarn = from.isVarargs();
 792                     break;
 793             }
 794             if (shouldWarn) {
 795                 warn.warn(LintCategory.VARARGS);
 796             }
 797         }
 798 
 799     /**
 800      * Is t a subtype of s?<br>
 801      * (not defined for Method and ForAll types)
 802      */
 803     final public boolean isSubtype(Type t, Type s) {
 804         return isSubtype(t, s, true);
 805     }
 806     final public boolean isSubtypeNoCapture(Type t, Type s) {
 807         return isSubtype(t, s, false);
 808     }
 809     public boolean isSubtype(Type t, Type s, boolean capture) {
 810         if (t == s)
 811             return true;
 812 
 813         t = t.unannotatedType();
 814         s = s.unannotatedType();
 815 
 816         if (t == s)
 817             return true;
 818 
 819         if (s.isPartial())
 820             return isSuperType(s, t);
 821 
 822         if (s.isCompound()) {
 823             for (Type s2 : interfaces(s).prepend(supertype(s))) {
 824                 if (!isSubtype(t, s2, capture))
 825                     return false;
 826             }
 827             return true;
 828         }
 829 
 830         // Generally, if 's' is a type variable, recur on lower bound; but
 831         // for inference variables and intersections, we need to keep 's'
 832         // (see JLS 4.10.2 for intersections and 18.2.3 for inference vars)
 833         if (!t.hasTag(UNDETVAR) && !t.isCompound()) {
 834             // TODO: JDK-8039198, bounds checking sometimes passes in a wildcard as s
 835             Type lower = cvarLowerBound(wildLowerBound(s));
 836             if (s != lower)
 837                 return isSubtype(capture ? capture(t) : t, lower, false);
 838         }
 839 
 840         return isSubtype.visit(capture ? capture(t) : t, s);
 841     }
 842     // where
 843         private TypeRelation isSubtype = new TypeRelation()
 844         {
 845             @Override
 846             public Boolean visitType(Type t, Type s) {
 847                 switch (t.getTag()) {
 848                  case BYTE:
 849                      return (!s.hasTag(CHAR) && t.getTag().isSubRangeOf(s.getTag()));
 850                  case CHAR:
 851                      return (!s.hasTag(SHORT) && t.getTag().isSubRangeOf(s.getTag()));
 852                  case SHORT: case INT: case LONG:
 853                  case FLOAT: case DOUBLE:
 854                      return t.getTag().isSubRangeOf(s.getTag());
 855                  case BOOLEAN: case VOID:
 856                      return t.hasTag(s.getTag());
 857                  case TYPEVAR:
 858                      return isSubtypeNoCapture(t.getUpperBound(), s);
 859                  case BOT:
 860                      return
 861                          s.hasTag(BOT) || s.hasTag(CLASS) ||
 862                          s.hasTag(ARRAY) || s.hasTag(TYPEVAR);
 863                  case WILDCARD: //we shouldn't be here - avoids crash (see 7034495)
 864                  case NONE:
 865                      return false;
 866                  default:
 867                      throw new AssertionError("isSubtype " + t.getTag());
 868                  }
 869             }
 870 
 871             private Set<TypePair> cache = new HashSet<TypePair>();
 872 
 873             private boolean containsTypeRecursive(Type t, Type s) {
 874                 TypePair pair = new TypePair(t, s);
 875                 if (cache.add(pair)) {
 876                     try {
 877                         return containsType(t.getTypeArguments(),
 878                                             s.getTypeArguments());
 879                     } finally {
 880                         cache.remove(pair);
 881                     }
 882                 } else {
 883                     return containsType(t.getTypeArguments(),
 884                                         rewriteSupers(s).getTypeArguments());
 885                 }
 886             }
 887 
 888             private Type rewriteSupers(Type t) {
 889                 if (!t.isParameterized())
 890                     return t;
 891                 ListBuffer<Type> from = new ListBuffer<>();
 892                 ListBuffer<Type> to = new ListBuffer<>();
 893                 adaptSelf(t, from, to);
 894                 if (from.isEmpty())
 895                     return t;
 896                 ListBuffer<Type> rewrite = new ListBuffer<>();
 897                 boolean changed = false;
 898                 for (Type orig : to.toList()) {
 899                     Type s = rewriteSupers(orig);
 900                     if (s.isSuperBound() && !s.isExtendsBound()) {
 901                         s = new WildcardType(syms.objectType,
 902                                              BoundKind.UNBOUND,
 903                                              syms.boundClass);
 904                         changed = true;
 905                     } else if (s != orig) {
 906                         s = new WildcardType(wildUpperBound(s),
 907                                              BoundKind.EXTENDS,
 908                                              syms.boundClass);
 909                         changed = true;
 910                     }
 911                     rewrite.append(s);
 912                 }
 913                 if (changed)
 914                     return subst(t.tsym.type, from.toList(), rewrite.toList());
 915                 else
 916                     return t;
 917             }
 918 
 919             @Override
 920             public Boolean visitClassType(ClassType t, Type s) {
 921                 Type sup = asSuper(t, s.tsym);
 922                 if (sup == null) return false;
 923                 // If t is an intersection, sup might not be a class type
 924                 if (!sup.hasTag(CLASS)) return isSubtypeNoCapture(sup, s);
 925                 return sup.tsym == s.tsym
 926                      // Check type variable containment
 927                     && (!s.isParameterized() || containsTypeRecursive(s, sup))
 928                     && isSubtypeNoCapture(sup.getEnclosingType(),
 929                                           s.getEnclosingType());
 930             }
 931 
 932             @Override
 933             public Boolean visitArrayType(ArrayType t, Type s) {
 934                 if (s.hasTag(ARRAY)) {
 935                     if (t.elemtype.isPrimitive())
 936                         return isSameType(t.elemtype, elemtype(s));
 937                     else
 938                         return isSubtypeNoCapture(t.elemtype, elemtype(s));
 939                 }
 940 
 941                 if (s.hasTag(CLASS)) {
 942                     Name sname = s.tsym.getQualifiedName();
 943                     return sname == names.java_lang_Object
 944                         || sname == names.java_lang_Cloneable
 945                         || sname == names.java_io_Serializable;
 946                 }
 947 
 948                 return false;
 949             }
 950 
 951             @Override
 952             public Boolean visitUndetVar(UndetVar t, Type s) {
 953                 //todo: test against origin needed? or replace with substitution?
 954                 if (t == s || t.qtype == s || s.hasTag(ERROR) || s.hasTag(UNKNOWN)) {
 955                     return true;
 956                 } else if (s.hasTag(BOT)) {
 957                     //if 's' is 'null' there's no instantiated type U for which
 958                     //U <: s (but 'null' itself, which is not a valid type)
 959                     return false;
 960                 }
 961 
 962                 t.addBound(InferenceBound.UPPER, s, Types.this);
 963                 return true;
 964             }
 965 
 966             @Override
 967             public Boolean visitErrorType(ErrorType t, Type s) {
 968                 return true;
 969             }
 970         };
 971 
 972     /**
 973      * Is t a subtype of every type in given list `ts'?<br>
 974      * (not defined for Method and ForAll types)<br>
 975      * Allows unchecked conversions.
 976      */
 977     public boolean isSubtypeUnchecked(Type t, List<Type> ts, Warner warn) {
 978         for (List<Type> l = ts; l.nonEmpty(); l = l.tail)
 979             if (!isSubtypeUnchecked(t, l.head, warn))
 980                 return false;
 981         return true;
 982     }
 983 
 984     /**
 985      * Are corresponding elements of ts subtypes of ss?  If lists are
 986      * of different length, return false.
 987      */
 988     public boolean isSubtypes(List<Type> ts, List<Type> ss) {
 989         while (ts.tail != null && ss.tail != null
 990                /*inlined: ts.nonEmpty() && ss.nonEmpty()*/ &&
 991                isSubtype(ts.head, ss.head)) {
 992             ts = ts.tail;
 993             ss = ss.tail;
 994         }
 995         return ts.tail == null && ss.tail == null;
 996         /*inlined: ts.isEmpty() && ss.isEmpty();*/
 997     }
 998 
 999     /**
1000      * Are corresponding elements of ts subtypes of ss, allowing
1001      * unchecked conversions?  If lists are of different length,
1002      * return false.
1003      **/
1004     public boolean isSubtypesUnchecked(List<Type> ts, List<Type> ss, Warner warn) {
1005         while (ts.tail != null && ss.tail != null
1006                /*inlined: ts.nonEmpty() && ss.nonEmpty()*/ &&
1007                isSubtypeUnchecked(ts.head, ss.head, warn)) {
1008             ts = ts.tail;
1009             ss = ss.tail;
1010         }
1011         return ts.tail == null && ss.tail == null;
1012         /*inlined: ts.isEmpty() && ss.isEmpty();*/
1013     }
1014     // </editor-fold>
1015 
1016     // <editor-fold defaultstate="collapsed" desc="isSuperType">
1017     /**
1018      * Is t a supertype of s?
1019      */
1020     public boolean isSuperType(Type t, Type s) {
1021         switch (t.getTag()) {
1022         case ERROR:
1023             return true;
1024         case UNDETVAR: {
1025             UndetVar undet = (UndetVar)t;
1026             if (t == s ||
1027                 undet.qtype == s ||
1028                 s.hasTag(ERROR) ||
1029                 s.hasTag(BOT)) {
1030                 return true;
1031             }
1032             undet.addBound(InferenceBound.LOWER, s, this);
1033             return true;
1034         }
1035         default:
1036             return isSubtype(s, t);
1037         }
1038     }
1039     // </editor-fold>
1040 
1041     // <editor-fold defaultstate="collapsed" desc="isSameType">
1042     /**
1043      * Are corresponding elements of the lists the same type?  If
1044      * lists are of different length, return false.
1045      */
1046     public boolean isSameTypes(List<Type> ts, List<Type> ss) {
1047         return isSameTypes(ts, ss, false);
1048     }
1049     public boolean isSameTypes(List<Type> ts, List<Type> ss, boolean strict) {
1050         while (ts.tail != null && ss.tail != null
1051                /*inlined: ts.nonEmpty() && ss.nonEmpty()*/ &&
1052                isSameType(ts.head, ss.head, strict)) {
1053             ts = ts.tail;
1054             ss = ss.tail;
1055         }
1056         return ts.tail == null && ss.tail == null;
1057         /*inlined: ts.isEmpty() && ss.isEmpty();*/
1058     }
1059 
1060     /**
1061     * A polymorphic signature method (JLS SE 7, 8.4.1) is a method that
1062     * (i) is declared in the java.lang.invoke.MethodHandle class, (ii) takes
1063     * a single variable arity parameter (iii) whose declared type is Object[],
1064     * (iv) has a return type of Object and (v) is native.
1065     */
1066    public boolean isSignaturePolymorphic(MethodSymbol msym) {
1067        List<Type> argtypes = msym.type.getParameterTypes();
1068        return (msym.flags_field & NATIVE) != 0 &&
1069                msym.owner == syms.methodHandleType.tsym &&
1070                argtypes.tail.tail == null &&
1071                argtypes.head.hasTag(TypeTag.ARRAY) &&
1072                msym.type.getReturnType().tsym == syms.objectType.tsym &&
1073                ((ArrayType)argtypes.head).elemtype.tsym == syms.objectType.tsym;
1074    }
1075 
1076     /**
1077      * Is t the same type as s?
1078      */
1079     public boolean isSameType(Type t, Type s) {
1080         return isSameType(t, s, false);
1081     }
1082     public boolean isSameType(Type t, Type s, boolean strict) {
1083         return strict ?
1084                 isSameTypeStrict.visit(t, s) :
1085                 isSameTypeLoose.visit(t, s);
1086     }
1087     public boolean isSameAnnotatedType(Type t, Type s) {
1088         return isSameAnnotatedType.visit(t, s);
1089     }
1090     // where
1091         abstract class SameTypeVisitor extends TypeRelation {
1092 
1093             public Boolean visitType(Type t, Type s) {
1094                 if (t == s)
1095                     return true;
1096 
1097                 if (s.isPartial())
1098                     return visit(s, t);
1099 
1100                 switch (t.getTag()) {
1101                 case BYTE: case CHAR: case SHORT: case INT: case LONG: case FLOAT:
1102                 case DOUBLE: case BOOLEAN: case VOID: case BOT: case NONE:
1103                     return t.hasTag(s.getTag());
1104                 case TYPEVAR: {
1105                     if (s.hasTag(TYPEVAR)) {
1106                         //type-substitution does not preserve type-var types
1107                         //check that type var symbols and bounds are indeed the same
1108                         return sameTypeVars((TypeVar)t.unannotatedType(), (TypeVar)s.unannotatedType());
1109                     }
1110                     else {
1111                         //special case for s == ? super X, where upper(s) = u
1112                         //check that u == t, where u has been set by Type.withTypeVar
1113                         return s.isSuperBound() &&
1114                                 !s.isExtendsBound() &&
1115                                 visit(t, wildUpperBound(s));
1116                     }
1117                 }
1118                 default:
1119                     throw new AssertionError("isSameType " + t.getTag());
1120                 }
1121             }
1122 
1123             abstract boolean sameTypeVars(TypeVar tv1, TypeVar tv2);
1124 
1125             @Override
1126             public Boolean visitWildcardType(WildcardType t, Type s) {
1127                 if (s.isPartial())
1128                     return visit(s, t);
1129                 else
1130                     return false;
1131             }
1132 
1133             @Override
1134             public Boolean visitClassType(ClassType t, Type s) {
1135                 if (t == s)
1136                     return true;
1137 
1138                 if (s.isPartial())
1139                     return visit(s, t);
1140 
1141                 if (s.isSuperBound() && !s.isExtendsBound())
1142                     return visit(t, wildUpperBound(s)) && visit(t, wildLowerBound(s));
1143 
1144                 if (t.isCompound() && s.isCompound()) {
1145                     if (!visit(supertype(t), supertype(s)))
1146                         return false;
1147 
1148                     HashSet<UniqueType> set = new HashSet<UniqueType>();
1149                     for (Type x : interfaces(t))
1150                         set.add(new UniqueType(x.unannotatedType(), Types.this));
1151                     for (Type x : interfaces(s)) {
1152                         if (!set.remove(new UniqueType(x.unannotatedType(), Types.this)))
1153                             return false;
1154                     }
1155                     return (set.isEmpty());
1156                 }
1157                 return t.tsym == s.tsym
1158                     && visit(t.getEnclosingType(), s.getEnclosingType())
1159                     && containsTypes(t.getTypeArguments(), s.getTypeArguments());
1160             }
1161 
1162             abstract protected boolean containsTypes(List<Type> ts1, List<Type> ts2);
1163 
1164             @Override
1165             public Boolean visitArrayType(ArrayType t, Type s) {
1166                 if (t == s)
1167                     return true;
1168 
1169                 if (s.isPartial())
1170                     return visit(s, t);
1171 
1172                 return s.hasTag(ARRAY)
1173                     && containsTypeEquivalent(t.elemtype, elemtype(s));
1174             }
1175 
1176             @Override
1177             public Boolean visitMethodType(MethodType t, Type s) {
1178                 // isSameType for methods does not take thrown
1179                 // exceptions into account!
1180                 return hasSameArgs(t, s) && visit(t.getReturnType(), s.getReturnType());
1181             }
1182 
1183             @Override
1184             public Boolean visitPackageType(PackageType t, Type s) {
1185                 return t == s;
1186             }
1187 
1188             @Override
1189             public Boolean visitForAll(ForAll t, Type s) {
1190                 if (!s.hasTag(FORALL)) {
1191                     return false;
1192                 }
1193 
1194                 ForAll forAll = (ForAll)s;
1195                 return hasSameBounds(t, forAll)
1196                     && visit(t.qtype, subst(forAll.qtype, forAll.tvars, t.tvars));
1197             }
1198 
1199             @Override
1200             public Boolean visitUndetVar(UndetVar t, Type s) {
1201                 if (s.hasTag(WILDCARD)) {
1202                     // FIXME, this might be leftovers from before capture conversion
1203                     return false;
1204                 }
1205 
1206                 if (t == s || t.qtype == s || s.hasTag(ERROR) || s.hasTag(UNKNOWN)) {
1207                     return true;
1208                 }
1209 
1210                 t.addBound(InferenceBound.EQ, s, Types.this);
1211 
1212                 return true;
1213             }
1214 
1215             @Override
1216             public Boolean visitErrorType(ErrorType t, Type s) {
1217                 return true;
1218             }
1219         }
1220 
1221         /**
1222          * Standard type-equality relation - type variables are considered
1223          * equals if they share the same type symbol.
1224          */
1225         TypeRelation isSameTypeLoose = new LooseSameTypeVisitor();
1226 
1227         private class LooseSameTypeVisitor extends SameTypeVisitor {
1228 
1229             /** cache of the type-variable pairs being (recursively) tested. */
1230             private Set<TypePair> cache = new HashSet<>();
1231 
1232             @Override
1233             boolean sameTypeVars(TypeVar tv1, TypeVar tv2) {
1234                 return tv1.tsym == tv2.tsym && checkSameBounds(tv1, tv2);
1235             }
1236             @Override
1237             protected boolean containsTypes(List<Type> ts1, List<Type> ts2) {
1238                 return containsTypeEquivalent(ts1, ts2);
1239             }
1240 
1241             /**
1242              * Since type-variable bounds can be recursive, we need to protect against
1243              * infinite loops - where the same bounds are checked over and over recursively.
1244              */
1245             private boolean checkSameBounds(TypeVar tv1, TypeVar tv2) {
1246                 TypePair p = new TypePair(tv1, tv2, true);
1247                 if (cache.add(p)) {
1248                     try {
1249                         return visit(tv1.getUpperBound(), tv2.getUpperBound());
1250                     } finally {
1251                         cache.remove(p);
1252                     }
1253                 } else {
1254                     return false;
1255                 }
1256             }
1257         };
1258 
1259         /**
1260          * Strict type-equality relation - type variables are considered
1261          * equals if they share the same object identity.
1262          */
1263         TypeRelation isSameTypeStrict = new SameTypeVisitor() {
1264             @Override
1265             boolean sameTypeVars(TypeVar tv1, TypeVar tv2) {
1266                 return tv1 == tv2;
1267             }
1268             @Override
1269             protected boolean containsTypes(List<Type> ts1, List<Type> ts2) {
1270                 return isSameTypes(ts1, ts2, true);
1271             }
1272 
1273             @Override
1274             public Boolean visitWildcardType(WildcardType t, Type s) {
1275                 if (!s.hasTag(WILDCARD)) {
1276                     return false;
1277                 } else {
1278                     WildcardType t2 = (WildcardType)s.unannotatedType();
1279                     return t.kind == t2.kind &&
1280                             isSameType(t.type, t2.type, true);
1281                 }
1282             }
1283         };
1284 
1285         /**
1286          * A version of LooseSameTypeVisitor that takes AnnotatedTypes
1287          * into account.
1288          */
1289         TypeRelation isSameAnnotatedType = new LooseSameTypeVisitor() {
1290             @Override
1291             public Boolean visitAnnotatedType(AnnotatedType t, Type s) {
1292                 if (!s.isAnnotated())
1293                     return false;
1294                 if (!t.getAnnotationMirrors().containsAll(s.getAnnotationMirrors()))
1295                     return false;
1296                 if (!s.getAnnotationMirrors().containsAll(t.getAnnotationMirrors()))
1297                     return false;
1298                 return visit(t.unannotatedType(), s);
1299             }
1300         };
1301     // </editor-fold>
1302 
1303     // <editor-fold defaultstate="collapsed" desc="Contains Type">
1304     public boolean containedBy(Type t, Type s) {
1305         switch (t.getTag()) {
1306         case UNDETVAR:
1307             if (s.hasTag(WILDCARD)) {
1308                 UndetVar undetvar = (UndetVar)t;
1309                 WildcardType wt = (WildcardType)s.unannotatedType();
1310                 switch(wt.kind) {
1311                     case UNBOUND:
1312                         break;
1313                     case EXTENDS: {
1314                         Type bound = wildUpperBound(s);
1315                         undetvar.addBound(InferenceBound.UPPER, bound, this);
1316                         break;
1317                     }
1318                     case SUPER: {
1319                         Type bound = wildLowerBound(s);
1320                         undetvar.addBound(InferenceBound.LOWER, bound, this);
1321                         break;
1322                     }
1323                 }
1324                 return true;
1325             } else {
1326                 return isSameType(t, s);
1327             }
1328         case ERROR:
1329             return true;
1330         default:
1331             return containsType(s, t);
1332         }
1333     }
1334 
1335     boolean containsType(List<Type> ts, List<Type> ss) {
1336         while (ts.nonEmpty() && ss.nonEmpty()
1337                && containsType(ts.head, ss.head)) {
1338             ts = ts.tail;
1339             ss = ss.tail;
1340         }
1341         return ts.isEmpty() && ss.isEmpty();
1342     }
1343 
1344     /**
1345      * Check if t contains s.
1346      *
1347      * <p>T contains S if:
1348      *
1349      * <p>{@code L(T) <: L(S) && U(S) <: U(T)}
1350      *
1351      * <p>This relation is only used by ClassType.isSubtype(), that
1352      * is,
1353      *
1354      * <p>{@code C<S> <: C<T> if T contains S.}
1355      *
1356      * <p>Because of F-bounds, this relation can lead to infinite
1357      * recursion.  Thus we must somehow break that recursion.  Notice
1358      * that containsType() is only called from ClassType.isSubtype().
1359      * Since the arguments have already been checked against their
1360      * bounds, we know:
1361      *
1362      * <p>{@code U(S) <: U(T) if T is "super" bound (U(T) *is* the bound)}
1363      *
1364      * <p>{@code L(T) <: L(S) if T is "extends" bound (L(T) is bottom)}
1365      *
1366      * @param t a type
1367      * @param s a type
1368      */
1369     public boolean containsType(Type t, Type s) {
1370         return containsType.visit(t, s);
1371     }
1372     // where
1373         private TypeRelation containsType = new TypeRelation() {
1374 
1375             public Boolean visitType(Type t, Type s) {
1376                 if (s.isPartial())
1377                     return containedBy(s, t);
1378                 else
1379                     return isSameType(t, s);
1380             }
1381 
1382 //            void debugContainsType(WildcardType t, Type s) {
1383 //                System.err.println();
1384 //                System.err.format(" does %s contain %s?%n", t, s);
1385 //                System.err.format(" %s U(%s) <: U(%s) %s = %s%n",
1386 //                                  wildUpperBound(s), s, t, wildUpperBound(t),
1387 //                                  t.isSuperBound()
1388 //                                  || isSubtypeNoCapture(wildUpperBound(s), wildUpperBound(t)));
1389 //                System.err.format(" %s L(%s) <: L(%s) %s = %s%n",
1390 //                                  wildLowerBound(t), t, s, wildLowerBound(s),
1391 //                                  t.isExtendsBound()
1392 //                                  || isSubtypeNoCapture(wildLowerBound(t), wildLowerBound(s)));
1393 //                System.err.println();
1394 //            }
1395 
1396             @Override
1397             public Boolean visitWildcardType(WildcardType t, Type s) {
1398                 if (s.isPartial())
1399                     return containedBy(s, t);
1400                 else {
1401 //                    debugContainsType(t, s);
1402                     return isSameWildcard(t, s)
1403                         || t.type == s
1404                         || isCaptureOf(s, t)
1405                         || ((t.isExtendsBound() || isSubtypeNoCapture(wildLowerBound(t), cvarLowerBound(wildLowerBound(s)))) &&
1406                             // TODO: JDK-8039214, cvarUpperBound call here is incorrect
1407                             (t.isSuperBound() || isSubtypeNoCapture(cvarUpperBound(wildUpperBound(s)), wildUpperBound(t))));
1408                 }
1409             }
1410 
1411             @Override
1412             public Boolean visitUndetVar(UndetVar t, Type s) {
1413                 if (!s.hasTag(WILDCARD)) {
1414                     return isSameType(t, s);
1415                 } else {
1416                     return false;
1417                 }
1418             }
1419 
1420             @Override
1421             public Boolean visitErrorType(ErrorType t, Type s) {
1422                 return true;
1423             }
1424         };
1425 
1426     public boolean isCaptureOf(Type s, WildcardType t) {
1427         if (!s.hasTag(TYPEVAR) || !((TypeVar)s.unannotatedType()).isCaptured())
1428             return false;
1429         return isSameWildcard(t, ((CapturedType)s.unannotatedType()).wildcard);
1430     }
1431 
1432     public boolean isSameWildcard(WildcardType t, Type s) {
1433         if (!s.hasTag(WILDCARD))
1434             return false;
1435         WildcardType w = (WildcardType)s.unannotatedType();
1436         return w.kind == t.kind && w.type == t.type;
1437     }
1438 
1439     public boolean containsTypeEquivalent(List<Type> ts, List<Type> ss) {
1440         while (ts.nonEmpty() && ss.nonEmpty()
1441                && containsTypeEquivalent(ts.head, ss.head)) {
1442             ts = ts.tail;
1443             ss = ss.tail;
1444         }
1445         return ts.isEmpty() && ss.isEmpty();
1446     }
1447     // </editor-fold>
1448 
1449     /**
1450      * Can t and s be compared for equality?  Any primitive ==
1451      * primitive or primitive == object comparisons here are an error.
1452      * Unboxing and correct primitive == primitive comparisons are
1453      * already dealt with in Attr.visitBinary.
1454      *
1455      */
1456     public boolean isEqualityComparable(Type s, Type t, Warner warn) {
1457         if (t.isNumeric() && s.isNumeric())
1458             return true;
1459 
1460         boolean tPrimitive = t.isPrimitive();
1461         boolean sPrimitive = s.isPrimitive();
1462         if (!tPrimitive && !sPrimitive) {
1463             return isCastable(s, t, warn) || isCastable(t, s, warn);
1464         } else {
1465             return false;
1466         }
1467     }
1468 
1469     // <editor-fold defaultstate="collapsed" desc="isCastable">
1470     public boolean isCastable(Type t, Type s) {
1471         return isCastable(t, s, noWarnings);
1472     }
1473 
1474     /**
1475      * Is t is castable to s?<br>
1476      * s is assumed to be an erased type.<br>
1477      * (not defined for Method and ForAll types).
1478      */
1479     public boolean isCastable(Type t, Type s, Warner warn) {
1480         if (t == s)
1481             return true;
1482 
1483         if (t.isPrimitive() != s.isPrimitive())
1484             return allowBoxing && (
1485                     isConvertible(t, s, warn)
1486                     || (allowObjectToPrimitiveCast &&
1487                         s.isPrimitive() &&
1488                         isSubtype(boxedClass(s).type, t)));
1489         if (warn != warnStack.head) {
1490             try {
1491                 warnStack = warnStack.prepend(warn);
1492                 checkUnsafeVarargsConversion(t, s, warn);
1493                 return isCastable.visit(t,s);
1494             } finally {
1495                 warnStack = warnStack.tail;
1496             }
1497         } else {
1498             return isCastable.visit(t,s);
1499         }
1500     }
1501     // where
1502         private TypeRelation isCastable = new TypeRelation() {
1503 
1504             public Boolean visitType(Type t, Type s) {
1505                 if (s.hasTag(ERROR))
1506                     return true;
1507 
1508                 switch (t.getTag()) {
1509                 case BYTE: case CHAR: case SHORT: case INT: case LONG: case FLOAT:
1510                 case DOUBLE:
1511                     return s.isNumeric();
1512                 case BOOLEAN:
1513                     return s.hasTag(BOOLEAN);
1514                 case VOID:
1515                     return false;
1516                 case BOT:
1517                     return isSubtype(t, s);
1518                 default:
1519                     throw new AssertionError();
1520                 }
1521             }
1522 
1523             @Override
1524             public Boolean visitWildcardType(WildcardType t, Type s) {
1525                 return isCastable(wildUpperBound(t), s, warnStack.head);
1526             }
1527 
1528             @Override
1529             public Boolean visitClassType(ClassType t, Type s) {
1530                 if (s.hasTag(ERROR) || s.hasTag(BOT))
1531                     return true;
1532 
1533                 if (s.hasTag(TYPEVAR)) {
1534                     if (isCastable(t, s.getUpperBound(), noWarnings)) {
1535                         warnStack.head.warn(LintCategory.UNCHECKED);
1536                         return true;
1537                     } else {
1538                         return false;
1539                     }
1540                 }
1541 
1542                 if (t.isIntersection() || s.isIntersection()) {
1543                     return !t.isIntersection() ?
1544                             visitIntersectionType((IntersectionClassType)s.unannotatedType(), t, true) :
1545                             visitIntersectionType((IntersectionClassType)t.unannotatedType(), s, false);
1546                 }
1547 
1548                 if (s.hasTag(CLASS) || s.hasTag(ARRAY)) {
1549                     boolean upcast;
1550                     if ((upcast = isSubtype(erasure(t), erasure(s)))
1551                         || isSubtype(erasure(s), erasure(t))) {
1552                         if (!upcast && s.hasTag(ARRAY)) {
1553                             if (!isReifiable(s))
1554                                 warnStack.head.warn(LintCategory.UNCHECKED);
1555                             return true;
1556                         } else if (s.isRaw()) {
1557                             return true;
1558                         } else if (t.isRaw()) {
1559                             if (!isUnbounded(s))
1560                                 warnStack.head.warn(LintCategory.UNCHECKED);
1561                             return true;
1562                         }
1563                         // Assume |a| <: |b|
1564                         final Type a = upcast ? t : s;
1565                         final Type b = upcast ? s : t;
1566                         final boolean HIGH = true;
1567                         final boolean LOW = false;
1568                         final boolean DONT_REWRITE_TYPEVARS = false;
1569                         Type aHigh = rewriteQuantifiers(a, HIGH, DONT_REWRITE_TYPEVARS);
1570                         Type aLow  = rewriteQuantifiers(a, LOW,  DONT_REWRITE_TYPEVARS);
1571                         Type bHigh = rewriteQuantifiers(b, HIGH, DONT_REWRITE_TYPEVARS);
1572                         Type bLow  = rewriteQuantifiers(b, LOW,  DONT_REWRITE_TYPEVARS);
1573                         Type lowSub = asSub(bLow, aLow.tsym);
1574                         Type highSub = (lowSub == null) ? null : asSub(bHigh, aHigh.tsym);
1575                         if (highSub == null) {
1576                             final boolean REWRITE_TYPEVARS = true;
1577                             aHigh = rewriteQuantifiers(a, HIGH, REWRITE_TYPEVARS);
1578                             aLow  = rewriteQuantifiers(a, LOW,  REWRITE_TYPEVARS);
1579                             bHigh = rewriteQuantifiers(b, HIGH, REWRITE_TYPEVARS);
1580                             bLow  = rewriteQuantifiers(b, LOW,  REWRITE_TYPEVARS);
1581                             lowSub = asSub(bLow, aLow.tsym);
1582                             highSub = (lowSub == null) ? null : asSub(bHigh, aHigh.tsym);
1583                         }
1584                         if (highSub != null) {
1585                             if (!(a.tsym == highSub.tsym && a.tsym == lowSub.tsym)) {
1586                                 Assert.error(a.tsym + " != " + highSub.tsym + " != " + lowSub.tsym);
1587                             }
1588                             if (!disjointTypes(aHigh.allparams(), highSub.allparams())
1589                                 && !disjointTypes(aHigh.allparams(), lowSub.allparams())
1590                                 && !disjointTypes(aLow.allparams(), highSub.allparams())
1591                                 && !disjointTypes(aLow.allparams(), lowSub.allparams())) {
1592                                 if (upcast ? giveWarning(a, b) :
1593                                     giveWarning(b, a))
1594                                     warnStack.head.warn(LintCategory.UNCHECKED);
1595                                 return true;
1596                             }
1597                         }
1598                         if (isReifiable(s))
1599                             return isSubtypeUnchecked(a, b);
1600                         else
1601                             return isSubtypeUnchecked(a, b, warnStack.head);
1602                     }
1603 
1604                     // Sidecast
1605                     if (s.hasTag(CLASS)) {
1606                         if ((s.tsym.flags() & INTERFACE) != 0) {
1607                             return ((t.tsym.flags() & FINAL) == 0)
1608                                 ? sideCast(t, s, warnStack.head)
1609                                 : sideCastFinal(t, s, warnStack.head);
1610                         } else if ((t.tsym.flags() & INTERFACE) != 0) {
1611                             return ((s.tsym.flags() & FINAL) == 0)
1612                                 ? sideCast(t, s, warnStack.head)
1613                                 : sideCastFinal(t, s, warnStack.head);
1614                         } else {
1615                             // unrelated class types
1616                             return false;
1617                         }
1618                     }
1619                 }
1620                 return false;
1621             }
1622 
1623             boolean visitIntersectionType(IntersectionClassType ict, Type s, boolean reverse) {
1624                 Warner warn = noWarnings;
1625                 for (Type c : ict.getComponents()) {
1626                     warn.clear();
1627                     if (reverse ? !isCastable(s, c, warn) : !isCastable(c, s, warn))
1628                         return false;
1629                 }
1630                 if (warn.hasLint(LintCategory.UNCHECKED))
1631                     warnStack.head.warn(LintCategory.UNCHECKED);
1632                 return true;
1633             }
1634 
1635             @Override
1636             public Boolean visitArrayType(ArrayType t, Type s) {
1637                 switch (s.getTag()) {
1638                 case ERROR:
1639                 case BOT:
1640                     return true;
1641                 case TYPEVAR:
1642                     if (isCastable(s, t, noWarnings)) {
1643                         warnStack.head.warn(LintCategory.UNCHECKED);
1644                         return true;
1645                     } else {
1646                         return false;
1647                     }
1648                 case CLASS:
1649                     return isSubtype(t, s);
1650                 case ARRAY:
1651                     if (elemtype(t).isPrimitive() || elemtype(s).isPrimitive()) {
1652                         return elemtype(t).hasTag(elemtype(s).getTag());
1653                     } else {
1654                         return visit(elemtype(t), elemtype(s));
1655                     }
1656                 default:
1657                     return false;
1658                 }
1659             }
1660 
1661             @Override
1662             public Boolean visitTypeVar(TypeVar t, Type s) {
1663                 switch (s.getTag()) {
1664                 case ERROR:
1665                 case BOT:
1666                     return true;
1667                 case TYPEVAR:
1668                     if (isSubtype(t, s)) {
1669                         return true;
1670                     } else if (isCastable(t.bound, s, noWarnings)) {
1671                         warnStack.head.warn(LintCategory.UNCHECKED);
1672                         return true;
1673                     } else {
1674                         return false;
1675                     }
1676                 default:
1677                     return isCastable(t.bound, s, warnStack.head);
1678                 }
1679             }
1680 
1681             @Override
1682             public Boolean visitErrorType(ErrorType t, Type s) {
1683                 return true;
1684             }
1685         };
1686     // </editor-fold>
1687 
1688     // <editor-fold defaultstate="collapsed" desc="disjointTypes">
1689     public boolean disjointTypes(List<Type> ts, List<Type> ss) {
1690         while (ts.tail != null && ss.tail != null) {
1691             if (disjointType(ts.head, ss.head)) return true;
1692             ts = ts.tail;
1693             ss = ss.tail;
1694         }
1695         return false;
1696     }
1697 
1698     /**
1699      * Two types or wildcards are considered disjoint if it can be
1700      * proven that no type can be contained in both. It is
1701      * conservative in that it is allowed to say that two types are
1702      * not disjoint, even though they actually are.
1703      *
1704      * The type {@code C<X>} is castable to {@code C<Y>} exactly if
1705      * {@code X} and {@code Y} are not disjoint.
1706      */
1707     public boolean disjointType(Type t, Type s) {
1708         return disjointType.visit(t, s);
1709     }
1710     // where
1711         private TypeRelation disjointType = new TypeRelation() {
1712 
1713             private Set<TypePair> cache = new HashSet<TypePair>();
1714 
1715             @Override
1716             public Boolean visitType(Type t, Type s) {
1717                 if (s.hasTag(WILDCARD))
1718                     return visit(s, t);
1719                 else
1720                     return notSoftSubtypeRecursive(t, s) || notSoftSubtypeRecursive(s, t);
1721             }
1722 
1723             private boolean isCastableRecursive(Type t, Type s) {
1724                 TypePair pair = new TypePair(t, s);
1725                 if (cache.add(pair)) {
1726                     try {
1727                         return Types.this.isCastable(t, s);
1728                     } finally {
1729                         cache.remove(pair);
1730                     }
1731                 } else {
1732                     return true;
1733                 }
1734             }
1735 
1736             private boolean notSoftSubtypeRecursive(Type t, Type s) {
1737                 TypePair pair = new TypePair(t, s);
1738                 if (cache.add(pair)) {
1739                     try {
1740                         return Types.this.notSoftSubtype(t, s);
1741                     } finally {
1742                         cache.remove(pair);
1743                     }
1744                 } else {
1745                     return false;
1746                 }
1747             }
1748 
1749             @Override
1750             public Boolean visitWildcardType(WildcardType t, Type s) {
1751                 if (t.isUnbound())
1752                     return false;
1753 
1754                 if (!s.hasTag(WILDCARD)) {
1755                     if (t.isExtendsBound())
1756                         return notSoftSubtypeRecursive(s, t.type);
1757                     else
1758                         return notSoftSubtypeRecursive(t.type, s);
1759                 }
1760 
1761                 if (s.isUnbound())
1762                     return false;
1763 
1764                 if (t.isExtendsBound()) {
1765                     if (s.isExtendsBound())
1766                         return !isCastableRecursive(t.type, wildUpperBound(s));
1767                     else if (s.isSuperBound())
1768                         return notSoftSubtypeRecursive(wildLowerBound(s), t.type);
1769                 } else if (t.isSuperBound()) {
1770                     if (s.isExtendsBound())
1771                         return notSoftSubtypeRecursive(t.type, wildUpperBound(s));
1772                 }
1773                 return false;
1774             }
1775         };
1776     // </editor-fold>
1777 
1778     // <editor-fold defaultstate="collapsed" desc="cvarLowerBounds">
1779     public List<Type> cvarLowerBounds(List<Type> ts) {
1780         return map(ts, cvarLowerBoundMapping);
1781     }
1782     private final Mapping cvarLowerBoundMapping = new Mapping("cvarLowerBound") {
1783             public Type apply(Type t) {
1784                 return cvarLowerBound(t);
1785             }
1786         };
1787     // </editor-fold>
1788 
1789     // <editor-fold defaultstate="collapsed" desc="notSoftSubtype">
1790     /**
1791      * This relation answers the question: is impossible that
1792      * something of type `t' can be a subtype of `s'? This is
1793      * different from the question "is `t' not a subtype of `s'?"
1794      * when type variables are involved: Integer is not a subtype of T
1795      * where {@code <T extends Number>} but it is not true that Integer cannot
1796      * possibly be a subtype of T.
1797      */
1798     public boolean notSoftSubtype(Type t, Type s) {
1799         if (t == s) return false;
1800         if (t.hasTag(TYPEVAR)) {
1801             TypeVar tv = (TypeVar) t;
1802             return !isCastable(tv.bound,
1803                                relaxBound(s),
1804                                noWarnings);
1805         }
1806         if (!s.hasTag(WILDCARD))
1807             s = cvarUpperBound(s);
1808 
1809         return !isSubtype(t, relaxBound(s));
1810     }
1811 
1812     private Type relaxBound(Type t) {
1813         if (t.hasTag(TYPEVAR)) {
1814             while (t.hasTag(TYPEVAR))
1815                 t = t.getUpperBound();
1816             t = rewriteQuantifiers(t, true, true);
1817         }
1818         return t;
1819     }
1820     // </editor-fold>
1821 
1822     // <editor-fold defaultstate="collapsed" desc="isReifiable">
1823     public boolean isReifiable(Type t) {
1824         return isReifiable.visit(t);
1825     }
1826     // where
1827         private UnaryVisitor<Boolean> isReifiable = new UnaryVisitor<Boolean>() {
1828 
1829             public Boolean visitType(Type t, Void ignored) {
1830                 return true;
1831             }
1832 
1833             @Override
1834             public Boolean visitClassType(ClassType t, Void ignored) {
1835                 if (t.isCompound())
1836                     return false;
1837                 else {
1838                     if (!t.isParameterized())
1839                         return true;
1840 
1841                     for (Type param : t.allparams()) {
1842                         if (!param.isUnbound())
1843                             return false;
1844                     }
1845                     return true;
1846                 }
1847             }
1848 
1849             @Override
1850             public Boolean visitArrayType(ArrayType t, Void ignored) {
1851                 return visit(t.elemtype);
1852             }
1853 
1854             @Override
1855             public Boolean visitTypeVar(TypeVar t, Void ignored) {
1856                 return false;
1857             }
1858         };
1859     // </editor-fold>
1860 
1861     // <editor-fold defaultstate="collapsed" desc="Array Utils">
1862     public boolean isArray(Type t) {
1863         while (t.hasTag(WILDCARD))
1864             t = wildUpperBound(t);
1865         return t.hasTag(ARRAY);
1866     }
1867 
1868     /**
1869      * The element type of an array.
1870      */
1871     public Type elemtype(Type t) {
1872         switch (t.getTag()) {
1873         case WILDCARD:
1874             return elemtype(wildUpperBound(t));
1875         case ARRAY:
1876             t = t.unannotatedType();
1877             return ((ArrayType)t).elemtype;
1878         case FORALL:
1879             return elemtype(((ForAll)t).qtype);
1880         case ERROR:
1881             return t;
1882         default:
1883             return null;
1884         }
1885     }
1886 
1887     public Type elemtypeOrType(Type t) {
1888         Type elemtype = elemtype(t);
1889         return elemtype != null ?
1890             elemtype :
1891             t;
1892     }
1893 
1894     /**
1895      * Mapping to take element type of an arraytype
1896      */
1897     private Mapping elemTypeFun = new Mapping ("elemTypeFun") {
1898         public Type apply(Type t) {
1899             while (t.hasTag(TYPEVAR)) {
1900                 t = t.getUpperBound();
1901             }
1902             return elemtype(t);
1903         }
1904     };
1905 
1906     /**
1907      * The number of dimensions of an array type.
1908      */
1909     public int dimensions(Type t) {
1910         int result = 0;
1911         while (t.hasTag(ARRAY)) {
1912             result++;
1913             t = elemtype(t);
1914         }
1915         return result;
1916     }
1917 
1918     /**
1919      * Returns an ArrayType with the component type t
1920      *
1921      * @param t The component type of the ArrayType
1922      * @return the ArrayType for the given component
1923      */
1924     public ArrayType makeArrayType(Type t) {
1925         if (t.hasTag(VOID) || t.hasTag(PACKAGE)) {
1926             Assert.error("Type t must not be a VOID or PACKAGE type, " + t.toString());
1927         }
1928         return new ArrayType(t, syms.arrayClass);
1929     }
1930     // </editor-fold>
1931 
1932     // <editor-fold defaultstate="collapsed" desc="asSuper">
1933     /**
1934      * Return the (most specific) base type of t that starts with the
1935      * given symbol.  If none exists, return null.
1936      *
1937      * @param t a type
1938      * @param sym a symbol
1939      */
1940     public Type asSuper(Type t, Symbol sym) {
1941         /* Some examples:
1942          *
1943          * (Enum<E>, Comparable) => Comparable<E>
1944          * (c.s.s.d.AttributeTree.ValueKind, Enum) => Enum<c.s.s.d.AttributeTree.ValueKind>
1945          * (c.s.s.t.ExpressionTree, c.s.s.t.Tree) => c.s.s.t.Tree
1946          * (j.u.List<capture#160 of ? extends c.s.s.d.DocTree>, Iterable) =>
1947          *     Iterable<capture#160 of ? extends c.s.s.d.DocTree>
1948          */
1949         if (sym.type == syms.objectType) { //optimization
1950             return syms.objectType;
1951         }
1952         return asSuper.visit(t, sym);
1953     }
1954     // where
1955         private SimpleVisitor<Type,Symbol> asSuper = new SimpleVisitor<Type,Symbol>() {
1956 
1957             public Type visitType(Type t, Symbol sym) {
1958                 return null;
1959             }
1960 
1961             @Override
1962             public Type visitClassType(ClassType t, Symbol sym) {
1963                 if (t.tsym == sym)
1964                     return t;
1965 
1966                 Type st = supertype(t);
1967                 if (st.hasTag(CLASS) || st.hasTag(TYPEVAR)) {
1968                     Type x = asSuper(st, sym);
1969                     if (x != null)
1970                         return x;
1971                 }
1972                 if ((sym.flags() & INTERFACE) != 0) {
1973                     for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail) {
1974                         if (!l.head.hasTag(ERROR)) {
1975                             Type x = asSuper(l.head, sym);
1976                             if (x != null)
1977                                 return x;
1978                         }
1979                     }
1980                 }
1981                 return null;
1982             }
1983 
1984             @Override
1985             public Type visitArrayType(ArrayType t, Symbol sym) {
1986                 return isSubtype(t, sym.type) ? sym.type : null;
1987             }
1988 
1989             @Override
1990             public Type visitTypeVar(TypeVar t, Symbol sym) {
1991                 if (t.tsym == sym)
1992                     return t;
1993                 else
1994                     return asSuper(t.bound, sym);
1995             }
1996 
1997             @Override
1998             public Type visitErrorType(ErrorType t, Symbol sym) {
1999                 return t;
2000             }
2001         };
2002 
2003     /**
2004      * Return the base type of t or any of its outer types that starts
2005      * with the given symbol.  If none exists, return null.
2006      *
2007      * @param t a type
2008      * @param sym a symbol
2009      */
2010     public Type asOuterSuper(Type t, Symbol sym) {
2011         switch (t.getTag()) {
2012         case CLASS:
2013             do {
2014                 Type s = asSuper(t, sym);
2015                 if (s != null) return s;
2016                 t = t.getEnclosingType();
2017             } while (t.hasTag(CLASS));
2018             return null;
2019         case ARRAY:
2020             return isSubtype(t, sym.type) ? sym.type : null;
2021         case TYPEVAR:
2022             return asSuper(t, sym);
2023         case ERROR:
2024             return t;
2025         default:
2026             return null;
2027         }
2028     }
2029 
2030     /**
2031      * Return the base type of t or any of its enclosing types that
2032      * starts with the given symbol.  If none exists, return null.
2033      *
2034      * @param t a type
2035      * @param sym a symbol
2036      */
2037     public Type asEnclosingSuper(Type t, Symbol sym) {
2038         switch (t.getTag()) {
2039         case CLASS:
2040             do {
2041                 Type s = asSuper(t, sym);
2042                 if (s != null) return s;
2043                 Type outer = t.getEnclosingType();
2044                 t = (outer.hasTag(CLASS)) ? outer :
2045                     (t.tsym.owner.enclClass() != null) ? t.tsym.owner.enclClass().type :
2046                     Type.noType;
2047             } while (t.hasTag(CLASS));
2048             return null;
2049         case ARRAY:
2050             return isSubtype(t, sym.type) ? sym.type : null;
2051         case TYPEVAR:
2052             return asSuper(t, sym);
2053         case ERROR:
2054             return t;
2055         default:
2056             return null;
2057         }
2058     }
2059     // </editor-fold>
2060 
2061     // <editor-fold defaultstate="collapsed" desc="memberType">
2062     /**
2063      * The type of given symbol, seen as a member of t.
2064      *
2065      * @param t a type
2066      * @param sym a symbol
2067      */
2068     public Type memberType(Type t, Symbol sym) {
2069         return (sym.flags() & STATIC) != 0
2070             ? sym.type
2071             : memberType.visit(t, sym);
2072         }
2073     // where
2074         private SimpleVisitor<Type,Symbol> memberType = new SimpleVisitor<Type,Symbol>() {
2075 
2076             public Type visitType(Type t, Symbol sym) {
2077                 return sym.type;
2078             }
2079 
2080             @Override
2081             public Type visitWildcardType(WildcardType t, Symbol sym) {
2082                 return memberType(wildUpperBound(t), sym);
2083             }
2084 
2085             @Override
2086             public Type visitClassType(ClassType t, Symbol sym) {
2087                 Symbol owner = sym.owner;
2088                 long flags = sym.flags();
2089                 if (((flags & STATIC) == 0) && owner.type.isParameterized()) {
2090                     Type base = asOuterSuper(t, owner);
2091                     //if t is an intersection type T = CT & I1 & I2 ... & In
2092                     //its supertypes CT, I1, ... In might contain wildcards
2093                     //so we need to go through capture conversion
2094                     base = t.isCompound() ? capture(base) : base;
2095                     if (base != null) {
2096                         List<Type> ownerParams = owner.type.allparams();
2097                         List<Type> baseParams = base.allparams();
2098                         if (ownerParams.nonEmpty()) {
2099                             if (baseParams.isEmpty()) {
2100                                 // then base is a raw type
2101                                 return erasure(sym.type);
2102                             } else {
2103                                 return subst(sym.type, ownerParams, baseParams);
2104                             }
2105                         }
2106                     }
2107                 }
2108                 return sym.type;
2109             }
2110 
2111             @Override
2112             public Type visitTypeVar(TypeVar t, Symbol sym) {
2113                 return memberType(t.bound, sym);
2114             }
2115 
2116             @Override
2117             public Type visitErrorType(ErrorType t, Symbol sym) {
2118                 return t;
2119             }
2120         };
2121     // </editor-fold>
2122 
2123     // <editor-fold defaultstate="collapsed" desc="isAssignable">
2124     public boolean isAssignable(Type t, Type s) {
2125         return isAssignable(t, s, noWarnings);
2126     }
2127 
2128     /**
2129      * Is t assignable to s?<br>
2130      * Equivalent to subtype except for constant values and raw
2131      * types.<br>
2132      * (not defined for Method and ForAll types)
2133      */
2134     public boolean isAssignable(Type t, Type s, Warner warn) {
2135         if (t.hasTag(ERROR))
2136             return true;
2137         if (t.getTag().isSubRangeOf(INT) && t.constValue() != null) {
2138             int value = ((Number)t.constValue()).intValue();
2139             switch (s.getTag()) {
2140             case BYTE:
2141                 if (Byte.MIN_VALUE <= value && value <= Byte.MAX_VALUE)
2142                     return true;
2143                 break;
2144             case CHAR:
2145                 if (Character.MIN_VALUE <= value && value <= Character.MAX_VALUE)
2146                     return true;
2147                 break;
2148             case SHORT:
2149                 if (Short.MIN_VALUE <= value && value <= Short.MAX_VALUE)
2150                     return true;
2151                 break;
2152             case INT:
2153                 return true;
2154             case CLASS:
2155                 switch (unboxedType(s).getTag()) {
2156                 case BYTE:
2157                 case CHAR:
2158                 case SHORT:
2159                     return isAssignable(t, unboxedType(s), warn);
2160                 }
2161                 break;
2162             }
2163         }
2164         return isConvertible(t, s, warn);
2165     }
2166     // </editor-fold>
2167 
2168     // <editor-fold defaultstate="collapsed" desc="erasure">
2169     /**
2170      * The erasure of t {@code |t|} -- the type that results when all
2171      * type parameters in t are deleted.
2172      */
2173     public Type erasure(Type t) {
2174         return eraseNotNeeded(t)? t : erasure(t, false);
2175     }
2176     //where
2177     private boolean eraseNotNeeded(Type t) {
2178         // We don't want to erase primitive types and String type as that
2179         // operation is idempotent. Also, erasing these could result in loss
2180         // of information such as constant values attached to such types.
2181         return (t.isPrimitive()) || (syms.stringType.tsym == t.tsym);
2182     }
2183 
2184     private Type erasure(Type t, boolean recurse) {
2185         if (t.isPrimitive())
2186             return t; /* fast special case */
2187         else
2188             return erasure.visit(t, recurse);
2189         }
2190     // where
2191         private SimpleVisitor<Type, Boolean> erasure = new SimpleVisitor<Type, Boolean>() {
2192             public Type visitType(Type t, Boolean recurse) {
2193                 if (t.isPrimitive())
2194                     return t; /*fast special case*/
2195                 else
2196                     return t.map(recurse ? erasureRecFun : erasureFun);
2197             }
2198 
2199             @Override
2200             public Type visitWildcardType(WildcardType t, Boolean recurse) {
2201                 return erasure(wildUpperBound(t), recurse);
2202             }
2203 
2204             @Override
2205             public Type visitClassType(ClassType t, Boolean recurse) {
2206                 Type erased = t.tsym.erasure(Types.this);
2207                 if (recurse) {
2208                     erased = new ErasedClassType(erased.getEnclosingType(),erased.tsym);
2209                 }
2210                 return erased;
2211             }
2212 
2213             @Override
2214             public Type visitTypeVar(TypeVar t, Boolean recurse) {
2215                 return erasure(t.bound, recurse);
2216             }
2217 
2218             @Override
2219             public Type visitErrorType(ErrorType t, Boolean recurse) {
2220                 return t;
2221             }
2222 
2223             @Override
2224             public Type visitAnnotatedType(AnnotatedType t, Boolean recurse) {
2225                 Type erased = erasure(t.unannotatedType(), recurse);
2226                 if (erased.isAnnotated()) {
2227                     // This can only happen when the underlying type is a
2228                     // type variable and the upper bound of it is annotated.
2229                     // The annotation on the type variable overrides the one
2230                     // on the bound.
2231                     erased = ((AnnotatedType)erased).unannotatedType();
2232                 }
2233                 return erased.annotatedType(t.getAnnotationMirrors());
2234             }
2235         };
2236 
2237     private Mapping erasureFun = new Mapping ("erasure") {
2238             public Type apply(Type t) { return erasure(t); }
2239         };
2240 
2241     private Mapping erasureRecFun = new Mapping ("erasureRecursive") {
2242         public Type apply(Type t) { return erasureRecursive(t); }
2243     };
2244 
2245     public List<Type> erasure(List<Type> ts) {
2246         return Type.map(ts, erasureFun);
2247     }
2248 
2249     public Type erasureRecursive(Type t) {
2250         return erasure(t, true);
2251     }
2252 
2253     public List<Type> erasureRecursive(List<Type> ts) {
2254         return Type.map(ts, erasureRecFun);
2255     }
2256     // </editor-fold>
2257 
2258     // <editor-fold defaultstate="collapsed" desc="makeIntersectionType">
2259     /**
2260      * Make an intersection type from non-empty list of types.  The list should be ordered according to
2261      * {@link TypeSymbol#precedes(TypeSymbol, Types)}. Note that this might cause a symbol completion.
2262      * Hence, this version of makeIntersectionType may not be called during a classfile read.
2263      *
2264      * @param bounds    the types from which the intersection type is formed
2265      */
2266     public IntersectionClassType makeIntersectionType(List<Type> bounds) {
2267         return makeIntersectionType(bounds, bounds.head.tsym.isInterface());
2268     }
2269 
2270     /**
2271      * Make an intersection type from non-empty list of types.  The list should be ordered according to
2272      * {@link TypeSymbol#precedes(TypeSymbol, Types)}. This does not cause symbol completion as
2273      * an extra parameter indicates as to whether all bounds are interfaces - in which case the
2274      * supertype is implicitly assumed to be 'Object'.
2275      *
2276      * @param bounds        the types from which the intersection type is formed
2277      * @param allInterfaces are all bounds interface types?
2278      */
2279     public IntersectionClassType makeIntersectionType(List<Type> bounds, boolean allInterfaces) {
2280         Assert.check(bounds.nonEmpty());
2281         Type firstExplicitBound = bounds.head;
2282         if (allInterfaces) {
2283             bounds = bounds.prepend(syms.objectType);
2284         }
2285         ClassSymbol bc =
2286             new ClassSymbol(ABSTRACT|PUBLIC|SYNTHETIC|COMPOUND|ACYCLIC,
2287                             Type.moreInfo
2288                                 ? names.fromString(bounds.toString())
2289                                 : names.empty,
2290                             null,
2291                             syms.noSymbol);
2292         IntersectionClassType intersectionType = new IntersectionClassType(bounds, bc, allInterfaces);
2293         bc.type = intersectionType;
2294         bc.erasure_field = (bounds.head.hasTag(TYPEVAR)) ?
2295                 syms.objectType : // error condition, recover
2296                 erasure(firstExplicitBound);
2297         bc.members_field = new Scope(bc);
2298         return intersectionType;
2299     }
2300 
2301     /**
2302      * A convenience wrapper for {@link #makeIntersectionType(List)}; the
2303      * arguments are converted to a list and passed to the other
2304      * method.  Note that this might cause a symbol completion.
2305      * Hence, this version of makeIntersectionType may not be called
2306      * during a classfile read.
2307      */
2308     public Type makeIntersectionType(Type bound1, Type bound2) {
2309         return makeIntersectionType(List.of(bound1, bound2));
2310     }
2311     // </editor-fold>
2312 
2313     // <editor-fold defaultstate="collapsed" desc="supertype">
2314     public Type supertype(Type t) {
2315         return supertype.visit(t);
2316     }
2317     // where
2318         private UnaryVisitor<Type> supertype = new UnaryVisitor<Type>() {
2319 
2320             public Type visitType(Type t, Void ignored) {
2321                 // A note on wildcards: there is no good way to
2322                 // determine a supertype for a super bounded wildcard.
2323                 return Type.noType;
2324             }
2325 
2326             @Override
2327             public Type visitClassType(ClassType t, Void ignored) {
2328                 if (t.supertype_field == null) {
2329                     Type supertype = ((ClassSymbol)t.tsym).getSuperclass();
2330                     // An interface has no superclass; its supertype is Object.
2331                     if (t.isInterface())
2332                         supertype = ((ClassType)t.tsym.type).supertype_field;
2333                     if (t.supertype_field == null) {
2334                         List<Type> actuals = classBound(t).allparams();
2335                         List<Type> formals = t.tsym.type.allparams();
2336                         if (t.hasErasedSupertypes()) {
2337                             t.supertype_field = erasureRecursive(supertype);
2338                         } else if (formals.nonEmpty()) {
2339                             t.supertype_field = subst(supertype, formals, actuals);
2340                         }
2341                         else {
2342                             t.supertype_field = supertype;
2343                         }
2344                     }
2345                 }
2346                 return t.supertype_field;
2347             }
2348 
2349             /**
2350              * The supertype is always a class type. If the type
2351              * variable's bounds start with a class type, this is also
2352              * the supertype.  Otherwise, the supertype is
2353              * java.lang.Object.
2354              */
2355             @Override
2356             public Type visitTypeVar(TypeVar t, Void ignored) {
2357                 if (t.bound.hasTag(TYPEVAR) ||
2358                     (!t.bound.isCompound() && !t.bound.isInterface())) {
2359                     return t.bound;
2360                 } else {
2361                     return supertype(t.bound);
2362                 }
2363             }
2364 
2365             @Override
2366             public Type visitArrayType(ArrayType t, Void ignored) {
2367                 if (t.elemtype.isPrimitive() || isSameType(t.elemtype, syms.objectType))
2368                     return arraySuperType();
2369                 else
2370                     return new ArrayType(supertype(t.elemtype), t.tsym);
2371             }
2372 
2373             @Override
2374             public Type visitErrorType(ErrorType t, Void ignored) {
2375                 return Type.noType;
2376             }
2377         };
2378     // </editor-fold>
2379 
2380     // <editor-fold defaultstate="collapsed" desc="interfaces">
2381     /**
2382      * Return the interfaces implemented by this class.
2383      */
2384     public List<Type> interfaces(Type t) {
2385         return interfaces.visit(t);
2386     }
2387     // where
2388         private UnaryVisitor<List<Type>> interfaces = new UnaryVisitor<List<Type>>() {
2389 
2390             public List<Type> visitType(Type t, Void ignored) {
2391                 return List.nil();
2392             }
2393 
2394             @Override
2395             public List<Type> visitClassType(ClassType t, Void ignored) {
2396                 if (t.interfaces_field == null) {
2397                     List<Type> interfaces = ((ClassSymbol)t.tsym).getInterfaces();
2398                     if (t.interfaces_field == null) {
2399                         // If t.interfaces_field is null, then t must
2400                         // be a parameterized type (not to be confused
2401                         // with a generic type declaration).
2402                         // Terminology:
2403                         //    Parameterized type: List<String>
2404                         //    Generic type declaration: class List<E> { ... }
2405                         // So t corresponds to List<String> and
2406                         // t.tsym.type corresponds to List<E>.
2407                         // The reason t must be parameterized type is
2408                         // that completion will happen as a side
2409                         // effect of calling
2410                         // ClassSymbol.getInterfaces.  Since
2411                         // t.interfaces_field is null after
2412                         // completion, we can assume that t is not the
2413                         // type of a class/interface declaration.
2414                         Assert.check(t != t.tsym.type, t);
2415                         List<Type> actuals = t.allparams();
2416                         List<Type> formals = t.tsym.type.allparams();
2417                         if (t.hasErasedSupertypes()) {
2418                             t.interfaces_field = erasureRecursive(interfaces);
2419                         } else if (formals.nonEmpty()) {
2420                             t.interfaces_field = subst(interfaces, formals, actuals);
2421                         }
2422                         else {
2423                             t.interfaces_field = interfaces;
2424                         }
2425                     }
2426                 }
2427                 return t.interfaces_field;
2428             }
2429 
2430             @Override
2431             public List<Type> visitTypeVar(TypeVar t, Void ignored) {
2432                 if (t.bound.isCompound())
2433                     return interfaces(t.bound);
2434 
2435                 if (t.bound.isInterface())
2436                     return List.of(t.bound);
2437 
2438                 return List.nil();
2439             }
2440         };
2441 
2442     public List<Type> directSupertypes(Type t) {
2443         return directSupertypes.visit(t);
2444     }
2445     // where
2446         private final UnaryVisitor<List<Type>> directSupertypes = new UnaryVisitor<List<Type>>() {
2447 
2448             public List<Type> visitType(final Type type, final Void ignored) {
2449                 if (!type.isIntersection()) {
2450                     final Type sup = supertype(type);
2451                     return (sup == Type.noType || sup == type || sup == null)
2452                         ? interfaces(type)
2453                         : interfaces(type).prepend(sup);
2454                 } else {
2455                     return visitIntersectionType((IntersectionClassType) type);
2456                 }
2457             }
2458 
2459             private List<Type> visitIntersectionType(final IntersectionClassType it) {
2460                 return it.getExplicitComponents();
2461             }
2462 
2463         };
2464 
2465     public boolean isDirectSuperInterface(TypeSymbol isym, TypeSymbol origin) {
2466         for (Type i2 : interfaces(origin.type)) {
2467             if (isym == i2.tsym) return true;
2468         }
2469         return false;
2470     }
2471     // </editor-fold>
2472 
2473     // <editor-fold defaultstate="collapsed" desc="isDerivedRaw">
2474     Map<Type,Boolean> isDerivedRawCache = new HashMap<Type,Boolean>();
2475 
2476     public boolean isDerivedRaw(Type t) {
2477         Boolean result = isDerivedRawCache.get(t);
2478         if (result == null) {
2479             result = isDerivedRawInternal(t);
2480             isDerivedRawCache.put(t, result);
2481         }
2482         return result;
2483     }
2484 
2485     public boolean isDerivedRawInternal(Type t) {
2486         if (t.isErroneous())
2487             return false;
2488         return
2489             t.isRaw() ||
2490             supertype(t) != Type.noType && isDerivedRaw(supertype(t)) ||
2491             isDerivedRaw(interfaces(t));
2492     }
2493 
2494     public boolean isDerivedRaw(List<Type> ts) {
2495         List<Type> l = ts;
2496         while (l.nonEmpty() && !isDerivedRaw(l.head)) l = l.tail;
2497         return l.nonEmpty();
2498     }
2499     // </editor-fold>
2500 
2501     // <editor-fold defaultstate="collapsed" desc="setBounds">
2502     /**
2503      * Same as {@link Types#setBounds(TypeVar, List, boolean)}, except that third parameter is computed directly,
2504      * as follows: if all all bounds are interface types, the computed supertype is Object,otherwise
2505      * the supertype is simply left null (in this case, the supertype is assumed to be the head of
2506      * the bound list passed as second argument). Note that this check might cause a symbol completion.
2507      * Hence, this version of setBounds may not be called during a classfile read.
2508      *
2509      * @param t         a type variable
2510      * @param bounds    the bounds, must be nonempty
2511      */
2512     public void setBounds(TypeVar t, List<Type> bounds) {
2513         setBounds(t, bounds, bounds.head.tsym.isInterface());
2514     }
2515 
2516     /**
2517      * Set the bounds field of the given type variable to reflect a (possibly multiple) list of bounds.
2518      * This does not cause symbol completion as an extra parameter indicates as to whether all bounds
2519      * are interfaces - in which case the supertype is implicitly assumed to be 'Object'.
2520      *
2521      * @param t             a type variable
2522      * @param bounds        the bounds, must be nonempty
2523      * @param allInterfaces are all bounds interface types?
2524      */
2525     public void setBounds(TypeVar t, List<Type> bounds, boolean allInterfaces) {
2526         t.bound = bounds.tail.isEmpty() ?
2527                 bounds.head :
2528                 makeIntersectionType(bounds, allInterfaces);
2529         t.rank_field = -1;
2530     }
2531     // </editor-fold>
2532 
2533     // <editor-fold defaultstate="collapsed" desc="getBounds">
2534     /**
2535      * Return list of bounds of the given type variable.
2536      */
2537     public List<Type> getBounds(TypeVar t) {
2538         if (t.bound.hasTag(NONE))
2539             return List.nil();
2540         else if (t.bound.isErroneous() || !t.bound.isCompound())
2541             return List.of(t.bound);
2542         else if ((erasure(t).tsym.flags() & INTERFACE) == 0)
2543             return interfaces(t).prepend(supertype(t));
2544         else
2545             // No superclass was given in bounds.
2546             // In this case, supertype is Object, erasure is first interface.
2547             return interfaces(t);
2548     }
2549     // </editor-fold>
2550 
2551     // <editor-fold defaultstate="collapsed" desc="classBound">
2552     /**
2553      * If the given type is a (possibly selected) type variable,
2554      * return the bounding class of this type, otherwise return the
2555      * type itself.
2556      */
2557     public Type classBound(Type t) {
2558         return classBound.visit(t);
2559     }
2560     // where
2561         private UnaryVisitor<Type> classBound = new UnaryVisitor<Type>() {
2562 
2563             public Type visitType(Type t, Void ignored) {
2564                 return t;
2565             }
2566 
2567             @Override
2568             public Type visitClassType(ClassType t, Void ignored) {
2569                 Type outer1 = classBound(t.getEnclosingType());
2570                 if (outer1 != t.getEnclosingType())
2571                     return new ClassType(outer1, t.getTypeArguments(), t.tsym);
2572                 else
2573                     return t;
2574             }
2575 
2576             @Override
2577             public Type visitTypeVar(TypeVar t, Void ignored) {
2578                 return classBound(supertype(t));
2579             }
2580 
2581             @Override
2582             public Type visitErrorType(ErrorType t, Void ignored) {
2583                 return t;
2584             }
2585         };
2586     // </editor-fold>
2587 
2588     // <editor-fold defaultstate="collapsed" desc="sub signature / override equivalence">
2589     /**
2590      * Returns true iff the first signature is a <em>sub
2591      * signature</em> of the other.  This is <b>not</b> an equivalence
2592      * relation.
2593      *
2594      * @jls section 8.4.2.
2595      * @see #overrideEquivalent(Type t, Type s)
2596      * @param t first signature (possibly raw).
2597      * @param s second signature (could be subjected to erasure).
2598      * @return true if t is a sub signature of s.
2599      */
2600     public boolean isSubSignature(Type t, Type s) {
2601         return isSubSignature(t, s, true);
2602     }
2603 
2604     public boolean isSubSignature(Type t, Type s, boolean strict) {
2605         return hasSameArgs(t, s, strict) || hasSameArgs(t, erasure(s), strict);
2606     }
2607 
2608     /**
2609      * Returns true iff these signatures are related by <em>override
2610      * equivalence</em>.  This is the natural extension of
2611      * isSubSignature to an equivalence relation.
2612      *
2613      * @jls section 8.4.2.
2614      * @see #isSubSignature(Type t, Type s)
2615      * @param t a signature (possible raw, could be subjected to
2616      * erasure).
2617      * @param s a signature (possible raw, could be subjected to
2618      * erasure).
2619      * @return true if either argument is a sub signature of the other.
2620      */
2621     public boolean overrideEquivalent(Type t, Type s) {
2622         return hasSameArgs(t, s) ||
2623             hasSameArgs(t, erasure(s)) || hasSameArgs(erasure(t), s);
2624     }
2625 
2626     public boolean overridesObjectMethod(TypeSymbol origin, Symbol msym) {
2627         for (Scope.Entry e = syms.objectType.tsym.members().lookup(msym.name) ; e.scope != null ; e = e.next()) {
2628             if (msym.overrides(e.sym, origin, Types.this, true)) {
2629                 return true;
2630             }
2631         }
2632         return false;
2633     }
2634 
2635     // <editor-fold defaultstate="collapsed" desc="Determining method implementation in given site">
2636     class ImplementationCache {
2637 
2638         private WeakHashMap<MethodSymbol, SoftReference<Map<TypeSymbol, Entry>>> _map =
2639                 new WeakHashMap<MethodSymbol, SoftReference<Map<TypeSymbol, Entry>>>();
2640 
2641         class Entry {
2642             final MethodSymbol cachedImpl;
2643             final Filter<Symbol> implFilter;
2644             final boolean checkResult;
2645             final int prevMark;
2646 
2647             public Entry(MethodSymbol cachedImpl,
2648                     Filter<Symbol> scopeFilter,
2649                     boolean checkResult,
2650                     int prevMark) {
2651                 this.cachedImpl = cachedImpl;
2652                 this.implFilter = scopeFilter;
2653                 this.checkResult = checkResult;
2654                 this.prevMark = prevMark;
2655             }
2656 
2657             boolean matches(Filter<Symbol> scopeFilter, boolean checkResult, int mark) {
2658                 return this.implFilter == scopeFilter &&
2659                         this.checkResult == checkResult &&
2660                         this.prevMark == mark;
2661             }
2662         }
2663 
2664         MethodSymbol get(MethodSymbol ms, TypeSymbol origin, boolean checkResult, Filter<Symbol> implFilter) {
2665             SoftReference<Map<TypeSymbol, Entry>> ref_cache = _map.get(ms);
2666             Map<TypeSymbol, Entry> cache = ref_cache != null ? ref_cache.get() : null;
2667             if (cache == null) {
2668                 cache = new HashMap<TypeSymbol, Entry>();
2669                 _map.put(ms, new SoftReference<Map<TypeSymbol, Entry>>(cache));
2670             }
2671             Entry e = cache.get(origin);
2672             CompoundScope members = membersClosure(origin.type, true);
2673             if (e == null ||
2674                     !e.matches(implFilter, checkResult, members.getMark())) {
2675                 MethodSymbol impl = implementationInternal(ms, origin, checkResult, implFilter);
2676                 cache.put(origin, new Entry(impl, implFilter, checkResult, members.getMark()));
2677                 return impl;
2678             }
2679             else {
2680                 return e.cachedImpl;
2681             }
2682         }
2683 
2684         private MethodSymbol implementationInternal(MethodSymbol ms, TypeSymbol origin, boolean checkResult, Filter<Symbol> implFilter) {
2685             for (Type t = origin.type; t.hasTag(CLASS) || t.hasTag(TYPEVAR); t = supertype(t)) {
2686                 while (t.hasTag(TYPEVAR))
2687                     t = t.getUpperBound();
2688                 TypeSymbol c = t.tsym;
2689                 for (Scope.Entry e = c.members().lookup(ms.name, implFilter);
2690                      e.scope != null;
2691                      e = e.next(implFilter)) {
2692                     if (e.sym != null &&
2693                              e.sym.overrides(ms, origin, Types.this, checkResult))
2694                         return (MethodSymbol)e.sym;
2695                 }
2696             }
2697             return null;
2698         }
2699     }
2700 
2701     private ImplementationCache implCache = new ImplementationCache();
2702 
2703     public MethodSymbol implementation(MethodSymbol ms, TypeSymbol origin, boolean checkResult, Filter<Symbol> implFilter) {
2704         return implCache.get(ms, origin, checkResult, implFilter);
2705     }
2706     // </editor-fold>
2707 
2708     // <editor-fold defaultstate="collapsed" desc="compute transitive closure of all members in given site">
2709     class MembersClosureCache extends SimpleVisitor<Scope.CompoundScope, Void> {
2710 
2711         private Map<TypeSymbol, CompoundScope> _map = new HashMap<>();
2712 
2713         Set<TypeSymbol> seenTypes = new HashSet<>();
2714 
2715         class MembersScope extends CompoundScope {
2716 
2717             CompoundScope scope;
2718 
2719             public MembersScope(CompoundScope scope) {
2720                 super(scope.owner);
2721                 this.scope = scope;
2722             }
2723 
2724             Filter<Symbol> combine(final Filter<Symbol> sf) {
2725                 return new Filter<Symbol>() {
2726                     @Override
2727                     public boolean accepts(Symbol s) {
2728                         return !s.owner.isInterface() && (sf == null || sf.accepts(s));
2729                     }
2730                 };
2731             }
2732 
2733             @Override
2734             public Iterable<Symbol> getElements(Filter<Symbol> sf) {
2735                 return scope.getElements(combine(sf));
2736             }
2737 
2738             @Override
2739             public Iterable<Symbol> getElementsByName(Name name, Filter<Symbol> sf) {
2740                 return scope.getElementsByName(name, combine(sf));
2741             }
2742 
2743             @Override
2744             public int getMark() {
2745                 return scope.getMark();
2746             }
2747         }
2748 
2749         CompoundScope nilScope;
2750 
2751         /** members closure visitor methods **/
2752 
2753         public CompoundScope visitType(Type t, Void _unused) {
2754             if (nilScope == null) {
2755                 nilScope = new CompoundScope(syms.noSymbol);
2756             }
2757             return nilScope;
2758         }
2759 
2760         @Override
2761         public CompoundScope visitClassType(ClassType t, Void _unused) {
2762             if (!seenTypes.add(t.tsym)) {
2763                 //this is possible when an interface is implemented in multiple
2764                 //superclasses, or when a class hierarchy is circular - in such
2765                 //cases we don't need to recurse (empty scope is returned)
2766                 return new CompoundScope(t.tsym);
2767             }
2768             try {
2769                 seenTypes.add(t.tsym);
2770                 ClassSymbol csym = (ClassSymbol)t.tsym;
2771                 CompoundScope membersClosure = _map.get(csym);
2772                 if (membersClosure == null) {
2773                     membersClosure = new CompoundScope(csym);
2774                     for (Type i : interfaces(t)) {
2775                         membersClosure.addSubScope(visit(i, null));
2776                     }
2777                     membersClosure.addSubScope(visit(supertype(t), null));
2778                     membersClosure.addSubScope(csym.members());
2779                     _map.put(csym, membersClosure);
2780                 }
2781                 return membersClosure;
2782             }
2783             finally {
2784                 seenTypes.remove(t.tsym);
2785             }
2786         }
2787 
2788         @Override
2789         public CompoundScope visitTypeVar(TypeVar t, Void _unused) {
2790             return visit(t.getUpperBound(), null);
2791         }
2792     }
2793 
2794     private MembersClosureCache membersCache = new MembersClosureCache();
2795 
2796     public CompoundScope membersClosure(Type site, boolean skipInterface) {
2797         CompoundScope cs = membersCache.visit(site, null);
2798         if (cs == null)
2799             Assert.error("type " + site);
2800         return skipInterface ? membersCache.new MembersScope(cs) : cs;
2801     }
2802     // </editor-fold>
2803 
2804 
2805     /** Return first abstract member of class `sym'.
2806      */
2807     public MethodSymbol firstUnimplementedAbstract(ClassSymbol sym) {
2808         try {
2809             return firstUnimplementedAbstractImpl(sym, sym);
2810         } catch (CompletionFailure ex) {
2811             chk.completionError(enter.getEnv(sym).tree.pos(), ex);
2812             return null;
2813         }
2814     }
2815         //where:
2816         private MethodSymbol firstUnimplementedAbstractImpl(ClassSymbol impl, ClassSymbol c) {
2817             MethodSymbol undef = null;
2818             // Do not bother to search in classes that are not abstract,
2819             // since they cannot have abstract members.
2820             if (c == impl || (c.flags() & (ABSTRACT | INTERFACE)) != 0) {
2821                 Scope s = c.members();
2822                 for (Scope.Entry e = s.elems;
2823                      undef == null && e != null;
2824                      e = e.sibling) {
2825                     if (e.sym.kind == MTH &&
2826                         (e.sym.flags() & (ABSTRACT|IPROXY|DEFAULT)) == ABSTRACT) {
2827                         MethodSymbol absmeth = (MethodSymbol)e.sym;
2828                         MethodSymbol implmeth = absmeth.implementation(impl, this, true);
2829                         if (implmeth == null || implmeth == absmeth) {
2830                             //look for default implementations
2831                             if (allowDefaultMethods) {
2832                                 MethodSymbol prov = interfaceCandidates(impl.type, absmeth).head;
2833                                 if (prov != null && prov.overrides(absmeth, impl, this, true)) {
2834                                     implmeth = prov;
2835                                 }
2836                             }
2837                         }
2838                         if (implmeth == null || implmeth == absmeth) {
2839                             undef = absmeth;
2840                         }
2841                     }
2842                 }
2843                 if (undef == null) {
2844                     Type st = supertype(c.type);
2845                     if (st.hasTag(CLASS))
2846                         undef = firstUnimplementedAbstractImpl(impl, (ClassSymbol)st.tsym);
2847                 }
2848                 for (List<Type> l = interfaces(c.type);
2849                      undef == null && l.nonEmpty();
2850                      l = l.tail) {
2851                     undef = firstUnimplementedAbstractImpl(impl, (ClassSymbol)l.head.tsym);
2852                 }
2853             }
2854             return undef;
2855         }
2856 
2857 
2858     //where
2859     public List<MethodSymbol> interfaceCandidates(Type site, MethodSymbol ms) {
2860         Filter<Symbol> filter = new MethodFilter(ms, site);
2861         List<MethodSymbol> candidates = List.nil();
2862             for (Symbol s : membersClosure(site, false).getElements(filter)) {
2863                 if (!site.tsym.isInterface() && !s.owner.isInterface()) {
2864                     return List.of((MethodSymbol)s);
2865                 } else if (!candidates.contains(s)) {
2866                     candidates = candidates.prepend((MethodSymbol)s);
2867                 }
2868             }
2869             return prune(candidates);
2870         }
2871 
2872     public List<MethodSymbol> prune(List<MethodSymbol> methods) {
2873         ListBuffer<MethodSymbol> methodsMin = new ListBuffer<>();
2874         for (MethodSymbol m1 : methods) {
2875             boolean isMin_m1 = true;
2876             for (MethodSymbol m2 : methods) {
2877                 if (m1 == m2) continue;
2878                 if (m2.owner != m1.owner &&
2879                         asSuper(m2.owner.type, m1.owner) != null) {
2880                     isMin_m1 = false;
2881                     break;
2882                 }
2883             }
2884             if (isMin_m1)
2885                 methodsMin.append(m1);
2886         }
2887         return methodsMin.toList();
2888     }
2889     // where
2890             private class MethodFilter implements Filter<Symbol> {
2891 
2892                 Symbol msym;
2893                 Type site;
2894 
2895                 MethodFilter(Symbol msym, Type site) {
2896                     this.msym = msym;
2897                     this.site = site;
2898                 }
2899 
2900                 public boolean accepts(Symbol s) {
2901                     return s.kind == Kinds.MTH &&
2902                             s.name == msym.name &&
2903                             (s.flags() & SYNTHETIC) == 0 &&
2904                             s.isInheritedIn(site.tsym, Types.this) &&
2905                             overrideEquivalent(memberType(site, s), memberType(site, msym));
2906                 }
2907             };
2908     // </editor-fold>
2909 
2910     /**
2911      * Does t have the same arguments as s?  It is assumed that both
2912      * types are (possibly polymorphic) method types.  Monomorphic
2913      * method types "have the same arguments", if their argument lists
2914      * are equal.  Polymorphic method types "have the same arguments",
2915      * if they have the same arguments after renaming all type
2916      * variables of one to corresponding type variables in the other,
2917      * where correspondence is by position in the type parameter list.
2918      */
2919     public boolean hasSameArgs(Type t, Type s) {
2920         return hasSameArgs(t, s, true);
2921     }
2922 
2923     public boolean hasSameArgs(Type t, Type s, boolean strict) {
2924         return hasSameArgs(t, s, strict ? hasSameArgs_strict : hasSameArgs_nonstrict);
2925     }
2926 
2927     private boolean hasSameArgs(Type t, Type s, TypeRelation hasSameArgs) {
2928         return hasSameArgs.visit(t, s);
2929     }
2930     // where
2931         private class HasSameArgs extends TypeRelation {
2932 
2933             boolean strict;
2934 
2935             public HasSameArgs(boolean strict) {
2936                 this.strict = strict;
2937             }
2938 
2939             public Boolean visitType(Type t, Type s) {
2940                 throw new AssertionError();
2941             }
2942 
2943             @Override
2944             public Boolean visitMethodType(MethodType t, Type s) {
2945                 return s.hasTag(METHOD)
2946                     && containsTypeEquivalent(t.argtypes, s.getParameterTypes());
2947             }
2948 
2949             @Override
2950             public Boolean visitForAll(ForAll t, Type s) {
2951                 if (!s.hasTag(FORALL))
2952                     return strict ? false : visitMethodType(t.asMethodType(), s);
2953 
2954                 ForAll forAll = (ForAll)s;
2955                 return hasSameBounds(t, forAll)
2956                     && visit(t.qtype, subst(forAll.qtype, forAll.tvars, t.tvars));
2957             }
2958 
2959             @Override
2960             public Boolean visitErrorType(ErrorType t, Type s) {
2961                 return false;
2962             }
2963         };
2964 
2965         TypeRelation hasSameArgs_strict = new HasSameArgs(true);
2966         TypeRelation hasSameArgs_nonstrict = new HasSameArgs(false);
2967 
2968     // </editor-fold>
2969 
2970     // <editor-fold defaultstate="collapsed" desc="subst">
2971     public List<Type> subst(List<Type> ts,
2972                             List<Type> from,
2973                             List<Type> to) {
2974         return new Subst(from, to).subst(ts);
2975     }
2976 
2977     /**
2978      * Substitute all occurrences of a type in `from' with the
2979      * corresponding type in `to' in 't'. Match lists `from' and `to'
2980      * from the right: If lists have different length, discard leading
2981      * elements of the longer list.
2982      */
2983     public Type subst(Type t, List<Type> from, List<Type> to) {
2984         return new Subst(from, to).subst(t);
2985     }
2986 
2987     private class Subst extends UnaryVisitor<Type> {
2988         List<Type> from;
2989         List<Type> to;
2990 
2991         public Subst(List<Type> from, List<Type> to) {
2992             int fromLength = from.length();
2993             int toLength = to.length();
2994             while (fromLength > toLength) {
2995                 fromLength--;
2996                 from = from.tail;
2997             }
2998             while (fromLength < toLength) {
2999                 toLength--;
3000                 to = to.tail;
3001             }
3002             this.from = from;
3003             this.to = to;
3004         }
3005 
3006         Type subst(Type t) {
3007             if (from.tail == null)
3008                 return t;
3009             else
3010                 return visit(t);
3011             }
3012 
3013         List<Type> subst(List<Type> ts) {
3014             if (from.tail == null)
3015                 return ts;
3016             boolean wild = false;
3017             if (ts.nonEmpty() && from.nonEmpty()) {
3018                 Type head1 = subst(ts.head);
3019                 List<Type> tail1 = subst(ts.tail);
3020                 if (head1 != ts.head || tail1 != ts.tail)
3021                     return tail1.prepend(head1);
3022             }
3023             return ts;
3024         }
3025 
3026         public Type visitType(Type t, Void ignored) {
3027             return t;
3028         }
3029 
3030         @Override
3031         public Type visitMethodType(MethodType t, Void ignored) {
3032             List<Type> argtypes = subst(t.argtypes);
3033             Type restype = subst(t.restype);
3034             List<Type> thrown = subst(t.thrown);
3035             if (argtypes == t.argtypes &&
3036                 restype == t.restype &&
3037                 thrown == t.thrown)
3038                 return t;
3039             else
3040                 return new MethodType(argtypes, restype, thrown, t.tsym);
3041         }
3042 
3043         @Override
3044         public Type visitTypeVar(TypeVar t, Void ignored) {
3045             for (List<Type> from = this.from, to = this.to;
3046                  from.nonEmpty();
3047                  from = from.tail, to = to.tail) {
3048                 if (t == from.head) {
3049                     return to.head.withTypeVar(t);
3050                 }
3051             }
3052             return t;
3053         }
3054 
3055         @Override
3056         public Type visitUndetVar(UndetVar t, Void ignored) {
3057             //do nothing - we should not replace inside undet variables
3058             return t;
3059         }
3060 
3061         @Override
3062         public Type visitClassType(ClassType t, Void ignored) {
3063             if (!t.isCompound()) {
3064                 List<Type> typarams = t.getTypeArguments();
3065                 List<Type> typarams1 = subst(typarams);
3066                 Type outer = t.getEnclosingType();
3067                 Type outer1 = subst(outer);
3068                 if (typarams1 == typarams && outer1 == outer)
3069                     return t;
3070                 else
3071                     return new ClassType(outer1, typarams1, t.tsym);
3072             } else {
3073                 Type st = subst(supertype(t));
3074                 List<Type> is = subst(interfaces(t));
3075                 if (st == supertype(t) && is == interfaces(t))
3076                     return t;
3077                 else
3078                     return makeIntersectionType(is.prepend(st));
3079             }
3080         }
3081 
3082         @Override
3083         public Type visitWildcardType(WildcardType t, Void ignored) {
3084             Type bound = t.type;
3085             if (t.kind != BoundKind.UNBOUND)
3086                 bound = subst(bound);
3087             if (bound == t.type) {
3088                 return t;
3089             } else {
3090                 if (t.isExtendsBound() && bound.isExtendsBound())
3091                     bound = wildUpperBound(bound);
3092                 return new WildcardType(bound, t.kind, syms.boundClass, t.bound);
3093             }
3094         }
3095 
3096         @Override
3097         public Type visitArrayType(ArrayType t, Void ignored) {
3098             Type elemtype = subst(t.elemtype);
3099             if (elemtype == t.elemtype)
3100                 return t;
3101             else
3102                 return new ArrayType(elemtype, t.tsym);
3103         }
3104 
3105         @Override
3106         public Type visitForAll(ForAll t, Void ignored) {
3107             if (Type.containsAny(to, t.tvars)) {
3108                 //perform alpha-renaming of free-variables in 't'
3109                 //if 'to' types contain variables that are free in 't'
3110                 List<Type> freevars = newInstances(t.tvars);
3111                 t = new ForAll(freevars,
3112                         Types.this.subst(t.qtype, t.tvars, freevars));
3113             }
3114             List<Type> tvars1 = substBounds(t.tvars, from, to);
3115             Type qtype1 = subst(t.qtype);
3116             if (tvars1 == t.tvars && qtype1 == t.qtype) {
3117                 return t;
3118             } else if (tvars1 == t.tvars) {
3119                 return new ForAll(tvars1, qtype1);
3120             } else {
3121                 return new ForAll(tvars1, Types.this.subst(qtype1, t.tvars, tvars1));
3122             }
3123         }
3124 
3125         @Override
3126         public Type visitErrorType(ErrorType t, Void ignored) {
3127             return t;
3128         }
3129     }
3130 
3131     public List<Type> substBounds(List<Type> tvars,
3132                                   List<Type> from,
3133                                   List<Type> to) {
3134         if (tvars.isEmpty())
3135             return tvars;
3136         ListBuffer<Type> newBoundsBuf = new ListBuffer<>();
3137         boolean changed = false;
3138         // calculate new bounds
3139         for (Type t : tvars) {
3140             TypeVar tv = (TypeVar) t;
3141             Type bound = subst(tv.bound, from, to);
3142             if (bound != tv.bound)
3143                 changed = true;
3144             newBoundsBuf.append(bound);
3145         }
3146         if (!changed)
3147             return tvars;
3148         ListBuffer<Type> newTvars = new ListBuffer<>();
3149         // create new type variables without bounds
3150         for (Type t : tvars) {
3151             newTvars.append(new TypeVar(t.tsym, null, syms.botType));
3152         }
3153         // the new bounds should use the new type variables in place
3154         // of the old
3155         List<Type> newBounds = newBoundsBuf.toList();
3156         from = tvars;
3157         to = newTvars.toList();
3158         for (; !newBounds.isEmpty(); newBounds = newBounds.tail) {
3159             newBounds.head = subst(newBounds.head, from, to);
3160         }
3161         newBounds = newBoundsBuf.toList();
3162         // set the bounds of new type variables to the new bounds
3163         for (Type t : newTvars.toList()) {
3164             TypeVar tv = (TypeVar) t;
3165             tv.bound = newBounds.head;
3166             newBounds = newBounds.tail;
3167         }
3168         return newTvars.toList();
3169     }
3170 
3171     public TypeVar substBound(TypeVar t, List<Type> from, List<Type> to) {
3172         Type bound1 = subst(t.bound, from, to);
3173         if (bound1 == t.bound)
3174             return t;
3175         else {
3176             // create new type variable without bounds
3177             TypeVar tv = new TypeVar(t.tsym, null, syms.botType);
3178             // the new bound should use the new type variable in place
3179             // of the old
3180             tv.bound = subst(bound1, List.<Type>of(t), List.<Type>of(tv));
3181             return tv;
3182         }
3183     }
3184     // </editor-fold>
3185 
3186     // <editor-fold defaultstate="collapsed" desc="hasSameBounds">
3187     /**
3188      * Does t have the same bounds for quantified variables as s?
3189      */
3190     public boolean hasSameBounds(ForAll t, ForAll s) {
3191         List<Type> l1 = t.tvars;
3192         List<Type> l2 = s.tvars;
3193         while (l1.nonEmpty() && l2.nonEmpty() &&
3194                isSameType(l1.head.getUpperBound(),
3195                           subst(l2.head.getUpperBound(),
3196                                 s.tvars,
3197                                 t.tvars))) {
3198             l1 = l1.tail;
3199             l2 = l2.tail;
3200         }
3201         return l1.isEmpty() && l2.isEmpty();
3202     }
3203     // </editor-fold>
3204 
3205     // <editor-fold defaultstate="collapsed" desc="newInstances">
3206     /** Create new vector of type variables from list of variables
3207      *  changing all recursive bounds from old to new list.
3208      */
3209     public List<Type> newInstances(List<Type> tvars) {
3210         List<Type> tvars1 = Type.map(tvars, newInstanceFun);
3211         for (List<Type> l = tvars1; l.nonEmpty(); l = l.tail) {
3212             TypeVar tv = (TypeVar) l.head;
3213             tv.bound = subst(tv.bound, tvars, tvars1);
3214         }
3215         return tvars1;
3216     }
3217     private static final Mapping newInstanceFun = new Mapping("newInstanceFun") {
3218             public Type apply(Type t) { return new TypeVar(t.tsym, t.getUpperBound(), t.getLowerBound()); }
3219         };
3220     // </editor-fold>
3221 
3222     public Type createMethodTypeWithParameters(Type original, List<Type> newParams) {
3223         return original.accept(methodWithParameters, newParams);
3224     }
3225     // where
3226         private final MapVisitor<List<Type>> methodWithParameters = new MapVisitor<List<Type>>() {
3227             public Type visitType(Type t, List<Type> newParams) {
3228                 throw new IllegalArgumentException("Not a method type: " + t);
3229             }
3230             public Type visitMethodType(MethodType t, List<Type> newParams) {
3231                 return new MethodType(newParams, t.restype, t.thrown, t.tsym);
3232             }
3233             public Type visitForAll(ForAll t, List<Type> newParams) {
3234                 return new ForAll(t.tvars, t.qtype.accept(this, newParams));
3235             }
3236         };
3237 
3238     public Type createMethodTypeWithThrown(Type original, List<Type> newThrown) {
3239         return original.accept(methodWithThrown, newThrown);
3240     }
3241     // where
3242         private final MapVisitor<List<Type>> methodWithThrown = new MapVisitor<List<Type>>() {
3243             public Type visitType(Type t, List<Type> newThrown) {
3244                 throw new IllegalArgumentException("Not a method type: " + t);
3245             }
3246             public Type visitMethodType(MethodType t, List<Type> newThrown) {
3247                 return new MethodType(t.argtypes, t.restype, newThrown, t.tsym);
3248             }
3249             public Type visitForAll(ForAll t, List<Type> newThrown) {
3250                 return new ForAll(t.tvars, t.qtype.accept(this, newThrown));
3251             }
3252         };
3253 
3254     public Type createMethodTypeWithReturn(Type original, Type newReturn) {
3255         return original.accept(methodWithReturn, newReturn);
3256     }
3257     // where
3258         private final MapVisitor<Type> methodWithReturn = new MapVisitor<Type>() {
3259             public Type visitType(Type t, Type newReturn) {
3260                 throw new IllegalArgumentException("Not a method type: " + t);
3261             }
3262             public Type visitMethodType(MethodType t, Type newReturn) {
3263                 return new MethodType(t.argtypes, newReturn, t.thrown, t.tsym);
3264             }
3265             public Type visitForAll(ForAll t, Type newReturn) {
3266                 return new ForAll(t.tvars, t.qtype.accept(this, newReturn));
3267             }
3268         };
3269 
3270     // <editor-fold defaultstate="collapsed" desc="createErrorType">
3271     public Type createErrorType(Type originalType) {
3272         return new ErrorType(originalType, syms.errSymbol);
3273     }
3274 
3275     public Type createErrorType(ClassSymbol c, Type originalType) {
3276         return new ErrorType(c, originalType);
3277     }
3278 
3279     public Type createErrorType(Name name, TypeSymbol container, Type originalType) {
3280         return new ErrorType(name, container, originalType);
3281     }
3282     // </editor-fold>
3283 
3284     // <editor-fold defaultstate="collapsed" desc="rank">
3285     /**
3286      * The rank of a class is the length of the longest path between
3287      * the class and java.lang.Object in the class inheritance
3288      * graph. Undefined for all but reference types.
3289      */
3290     public int rank(Type t) {
3291         t = t.unannotatedType();
3292         switch(t.getTag()) {
3293         case CLASS: {
3294             ClassType cls = (ClassType)t;
3295             if (cls.rank_field < 0) {
3296                 Name fullname = cls.tsym.getQualifiedName();
3297                 if (fullname == names.java_lang_Object)
3298                     cls.rank_field = 0;
3299                 else {
3300                     int r = rank(supertype(cls));
3301                     for (List<Type> l = interfaces(cls);
3302                          l.nonEmpty();
3303                          l = l.tail) {
3304                         if (rank(l.head) > r)
3305                             r = rank(l.head);
3306                     }
3307                     cls.rank_field = r + 1;
3308                 }
3309             }
3310             return cls.rank_field;
3311         }
3312         case TYPEVAR: {
3313             TypeVar tvar = (TypeVar)t;
3314             if (tvar.rank_field < 0) {
3315                 int r = rank(supertype(tvar));
3316                 for (List<Type> l = interfaces(tvar);
3317                      l.nonEmpty();
3318                      l = l.tail) {
3319                     if (rank(l.head) > r) r = rank(l.head);
3320                 }
3321                 tvar.rank_field = r + 1;
3322             }
3323             return tvar.rank_field;
3324         }
3325         case ERROR:
3326         case NONE:
3327             return 0;
3328         default:
3329             throw new AssertionError();
3330         }
3331     }
3332     // </editor-fold>
3333 
3334     /**
3335      * Helper method for generating a string representation of a given type
3336      * accordingly to a given locale
3337      */
3338     public String toString(Type t, Locale locale) {
3339         return Printer.createStandardPrinter(messages).visit(t, locale);
3340     }
3341 
3342     /**
3343      * Helper method for generating a string representation of a given type
3344      * accordingly to a given locale
3345      */
3346     public String toString(Symbol t, Locale locale) {
3347         return Printer.createStandardPrinter(messages).visit(t, locale);
3348     }
3349 
3350     // <editor-fold defaultstate="collapsed" desc="toString">
3351     /**
3352      * This toString is slightly more descriptive than the one on Type.
3353      *
3354      * @deprecated Types.toString(Type t, Locale l) provides better support
3355      * for localization
3356      */
3357     @Deprecated
3358     public String toString(Type t) {
3359         if (t.hasTag(FORALL)) {
3360             ForAll forAll = (ForAll)t;
3361             return typaramsString(forAll.tvars) + forAll.qtype;
3362         }
3363         return "" + t;
3364     }
3365     // where
3366         private String typaramsString(List<Type> tvars) {
3367             StringBuilder s = new StringBuilder();
3368             s.append('<');
3369             boolean first = true;
3370             for (Type t : tvars) {
3371                 if (!first) s.append(", ");
3372                 first = false;
3373                 appendTyparamString(((TypeVar)t.unannotatedType()), s);
3374             }
3375             s.append('>');
3376             return s.toString();
3377         }
3378         private void appendTyparamString(TypeVar t, StringBuilder buf) {
3379             buf.append(t);
3380             if (t.bound == null ||
3381                 t.bound.tsym.getQualifiedName() == names.java_lang_Object)
3382                 return;
3383             buf.append(" extends "); // Java syntax; no need for i18n
3384             Type bound = t.bound;
3385             if (!bound.isCompound()) {
3386                 buf.append(bound);
3387             } else if ((erasure(t).tsym.flags() & INTERFACE) == 0) {
3388                 buf.append(supertype(t));
3389                 for (Type intf : interfaces(t)) {
3390                     buf.append('&');
3391                     buf.append(intf);
3392                 }
3393             } else {
3394                 // No superclass was given in bounds.
3395                 // In this case, supertype is Object, erasure is first interface.
3396                 boolean first = true;
3397                 for (Type intf : interfaces(t)) {
3398                     if (!first) buf.append('&');
3399                     first = false;
3400                     buf.append(intf);
3401                 }
3402             }
3403         }
3404     // </editor-fold>
3405 
3406     // <editor-fold defaultstate="collapsed" desc="Determining least upper bounds of types">
3407     /**
3408      * A cache for closures.
3409      *
3410      * <p>A closure is a list of all the supertypes and interfaces of
3411      * a class or interface type, ordered by ClassSymbol.precedes
3412      * (that is, subclasses come first, arbitrary but fixed
3413      * otherwise).
3414      */
3415     private Map<Type,List<Type>> closureCache = new HashMap<Type,List<Type>>();
3416 
3417     /**
3418      * Returns the closure of a class or interface type.
3419      */
3420     public List<Type> closure(Type t) {
3421         List<Type> cl = closureCache.get(t);
3422         if (cl == null) {
3423             Type st = supertype(t);
3424             if (!t.isCompound()) {
3425                 if (st.hasTag(CLASS)) {
3426                     cl = insert(closure(st), t);
3427                 } else if (st.hasTag(TYPEVAR)) {
3428                     cl = closure(st).prepend(t);
3429                 } else {
3430                     cl = List.of(t);
3431                 }
3432             } else {
3433                 cl = closure(supertype(t));
3434             }
3435             for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail)
3436                 cl = union(cl, closure(l.head));
3437             closureCache.put(t, cl);
3438         }
3439         return cl;
3440     }
3441 
3442     /**
3443      * Insert a type in a closure
3444      */
3445     public List<Type> insert(List<Type> cl, Type t) {
3446         if (cl.isEmpty()) {
3447             return cl.prepend(t);
3448         } else if (t.tsym == cl.head.tsym) {
3449             return cl;
3450         } else if (t.tsym.precedes(cl.head.tsym, this)) {
3451             return cl.prepend(t);
3452         } else {
3453             // t comes after head, or the two are unrelated
3454             return insert(cl.tail, t).prepend(cl.head);
3455         }
3456     }
3457 
3458     /**
3459      * Form the union of two closures
3460      */
3461     public List<Type> union(List<Type> cl1, List<Type> cl2) {
3462         if (cl1.isEmpty()) {
3463             return cl2;
3464         } else if (cl2.isEmpty()) {
3465             return cl1;
3466         } else if (cl1.head.tsym == cl2.head.tsym) {
3467             return union(cl1.tail, cl2.tail).prepend(cl1.head);
3468         } else if (cl1.head.tsym.precedes(cl2.head.tsym, this)) {
3469             return union(cl1.tail, cl2).prepend(cl1.head);
3470         } else if (cl2.head.tsym.precedes(cl1.head.tsym, this)) {
3471             return union(cl1, cl2.tail).prepend(cl2.head);
3472         } else {
3473             // unrelated types
3474             return union(cl1.tail, cl2).prepend(cl1.head);
3475         }
3476     }
3477 
3478     /**
3479      * Intersect two closures
3480      */
3481     public List<Type> intersect(List<Type> cl1, List<Type> cl2) {
3482         if (cl1 == cl2)
3483             return cl1;
3484         if (cl1.isEmpty() || cl2.isEmpty())
3485             return List.nil();
3486         if (cl1.head.tsym.precedes(cl2.head.tsym, this))
3487             return intersect(cl1.tail, cl2);
3488         if (cl2.head.tsym.precedes(cl1.head.tsym, this))
3489             return intersect(cl1, cl2.tail);
3490         if (isSameType(cl1.head, cl2.head))
3491             return intersect(cl1.tail, cl2.tail).prepend(cl1.head);
3492         if (cl1.head.tsym == cl2.head.tsym &&
3493             cl1.head.hasTag(CLASS) && cl2.head.hasTag(CLASS)) {
3494             if (cl1.head.isParameterized() && cl2.head.isParameterized()) {
3495                 Type merge = merge(cl1.head,cl2.head);
3496                 return intersect(cl1.tail, cl2.tail).prepend(merge);
3497             }
3498             if (cl1.head.isRaw() || cl2.head.isRaw())
3499                 return intersect(cl1.tail, cl2.tail).prepend(erasure(cl1.head));
3500         }
3501         return intersect(cl1.tail, cl2.tail);
3502     }
3503     // where
3504         class TypePair {
3505             final Type t1;
3506             final Type t2;
3507             boolean strict;
3508 
3509             TypePair(Type t1, Type t2) {
3510                 this(t1, t2, false);
3511             }
3512 
3513             TypePair(Type t1, Type t2, boolean strict) {
3514                 this.t1 = t1;
3515                 this.t2 = t2;
3516                 this.strict = strict;
3517             }
3518             @Override
3519             public int hashCode() {
3520                 return 127 * Types.this.hashCode(t1) + Types.this.hashCode(t2);
3521             }
3522             @Override
3523             public boolean equals(Object obj) {
3524                 if (!(obj instanceof TypePair))
3525                     return false;
3526                 TypePair typePair = (TypePair)obj;
3527                 return isSameType(t1, typePair.t1, strict)
3528                     && isSameType(t2, typePair.t2, strict);
3529             }
3530         }
3531         Set<TypePair> mergeCache = new HashSet<TypePair>();
3532         private Type merge(Type c1, Type c2) {
3533             ClassType class1 = (ClassType) c1;
3534             List<Type> act1 = class1.getTypeArguments();
3535             ClassType class2 = (ClassType) c2;
3536             List<Type> act2 = class2.getTypeArguments();
3537             ListBuffer<Type> merged = new ListBuffer<Type>();
3538             List<Type> typarams = class1.tsym.type.getTypeArguments();
3539 
3540             while (act1.nonEmpty() && act2.nonEmpty() && typarams.nonEmpty()) {
3541                 if (containsType(act1.head, act2.head)) {
3542                     merged.append(act1.head);
3543                 } else if (containsType(act2.head, act1.head)) {
3544                     merged.append(act2.head);
3545                 } else {
3546                     TypePair pair = new TypePair(c1, c2);
3547                     Type m;
3548                     if (mergeCache.add(pair)) {
3549                         m = new WildcardType(lub(wildUpperBound(act1.head),
3550                                                  wildUpperBound(act2.head)),
3551                                              BoundKind.EXTENDS,
3552                                              syms.boundClass);
3553                         mergeCache.remove(pair);
3554                     } else {
3555                         m = new WildcardType(syms.objectType,
3556                                              BoundKind.UNBOUND,
3557                                              syms.boundClass);
3558                     }
3559                     merged.append(m.withTypeVar(typarams.head));
3560                 }
3561                 act1 = act1.tail;
3562                 act2 = act2.tail;
3563                 typarams = typarams.tail;
3564             }
3565             Assert.check(act1.isEmpty() && act2.isEmpty() && typarams.isEmpty());
3566             return new ClassType(class1.getEnclosingType(), merged.toList(), class1.tsym);
3567         }
3568 
3569     /**
3570      * Return the minimum type of a closure, a compound type if no
3571      * unique minimum exists.
3572      */
3573     private Type compoundMin(List<Type> cl) {
3574         if (cl.isEmpty()) return syms.objectType;
3575         List<Type> compound = closureMin(cl);
3576         if (compound.isEmpty())
3577             return null;
3578         else if (compound.tail.isEmpty())
3579             return compound.head;
3580         else
3581             return makeIntersectionType(compound);
3582     }
3583 
3584     /**
3585      * Return the minimum types of a closure, suitable for computing
3586      * compoundMin or glb.
3587      */
3588     private List<Type> closureMin(List<Type> cl) {
3589         ListBuffer<Type> classes = new ListBuffer<>();
3590         ListBuffer<Type> interfaces = new ListBuffer<>();
3591         Set<Type> toSkip = new HashSet<>();
3592         while (!cl.isEmpty()) {
3593             Type current = cl.head;
3594             boolean keep = !toSkip.contains(current);
3595             if (keep && current.hasTag(TYPEVAR)) {
3596                 // skip lower-bounded variables with a subtype in cl.tail
3597                 for (Type t : cl.tail) {
3598                     if (isSubtypeNoCapture(t, current)) {
3599                         keep = false;
3600                         break;
3601                     }
3602                 }
3603             }
3604             if (keep) {
3605                 if (current.isInterface())
3606                     interfaces.append(current);
3607                 else
3608                     classes.append(current);
3609                 for (Type t : cl.tail) {
3610                     // skip supertypes of 'current' in cl.tail
3611                     if (isSubtypeNoCapture(current, t))
3612                         toSkip.add(t);
3613                 }
3614             }
3615             cl = cl.tail;
3616         }
3617         return classes.appendList(interfaces).toList();
3618     }
3619 
3620     /**
3621      * Return the least upper bound of list of types.  if the lub does
3622      * not exist return null.
3623      */
3624     public Type lub(List<Type> ts) {
3625         return lub(ts.toArray(new Type[ts.length()]));
3626     }
3627 
3628     /**
3629      * Return the least upper bound (lub) of set of types.  If the lub
3630      * does not exist return the type of null (bottom).
3631      */
3632     public Type lub(Type... ts) {
3633         final int UNKNOWN_BOUND = 0;
3634         final int ARRAY_BOUND = 1;
3635         final int CLASS_BOUND = 2;
3636 
3637         int[] kinds = new int[ts.length];
3638 
3639         int boundkind = UNKNOWN_BOUND;
3640         for (int i = 0 ; i < ts.length ; i++) {
3641             Type t = ts[i];
3642             switch (t.getTag()) {
3643             case CLASS:
3644                 boundkind |= kinds[i] = CLASS_BOUND;
3645                 break;
3646             case ARRAY:
3647                 boundkind |= kinds[i] = ARRAY_BOUND;
3648                 break;
3649             case  TYPEVAR:
3650                 do {
3651                     t = t.getUpperBound();
3652                 } while (t.hasTag(TYPEVAR));
3653                 if (t.hasTag(ARRAY)) {
3654                     boundkind |= kinds[i] = ARRAY_BOUND;
3655                 } else {
3656                     boundkind |= kinds[i] = CLASS_BOUND;
3657                 }
3658                 break;
3659             default:
3660                 kinds[i] = UNKNOWN_BOUND;
3661                 if (t.isPrimitive())
3662                     return syms.errType;
3663             }
3664         }
3665         switch (boundkind) {
3666         case 0:
3667             return syms.botType;
3668 
3669         case ARRAY_BOUND:
3670             // calculate lub(A[], B[])
3671             Type[] elements = new Type[ts.length];
3672             for (int i = 0 ; i < ts.length ; i++) {
3673                 Type elem = elements[i] = elemTypeFun.apply(ts[i]);
3674                 if (elem.isPrimitive()) {
3675                     // if a primitive type is found, then return
3676                     // arraySuperType unless all the types are the
3677                     // same
3678                     Type first = ts[0];
3679                     for (int j = 1 ; j < ts.length ; j++) {
3680                         if (!isSameType(first, ts[j])) {
3681                              // lub(int[], B[]) is Cloneable & Serializable
3682                             return arraySuperType();
3683                         }
3684                     }
3685                     // all the array types are the same, return one
3686                     // lub(int[], int[]) is int[]
3687                     return first;
3688                 }
3689             }
3690             // lub(A[], B[]) is lub(A, B)[]
3691             return new ArrayType(lub(elements), syms.arrayClass);
3692 
3693         case CLASS_BOUND:
3694             // calculate lub(A, B)
3695             int startIdx = 0;
3696             for (int i = 0; i < ts.length ; i++) {
3697                 Type t = ts[i];
3698                 if (t.hasTag(CLASS) || t.hasTag(TYPEVAR)) {
3699                     break;
3700                 } else {
3701                     startIdx++;
3702                 }
3703             }
3704             Assert.check(startIdx < ts.length);
3705             //step 1 - compute erased candidate set (EC)
3706             List<Type> cl = erasedSupertypes(ts[startIdx]);
3707             for (int i = startIdx + 1 ; i < ts.length ; i++) {
3708                 Type t = ts[i];
3709                 if (t.hasTag(CLASS) || t.hasTag(TYPEVAR))
3710                     cl = intersect(cl, erasedSupertypes(t));
3711             }
3712             //step 2 - compute minimal erased candidate set (MEC)
3713             List<Type> mec = closureMin(cl);
3714             //step 3 - for each element G in MEC, compute lci(Inv(G))
3715             List<Type> candidates = List.nil();
3716             for (Type erasedSupertype : mec) {
3717                 List<Type> lci = List.of(asSuper(ts[startIdx], erasedSupertype.tsym));
3718                 for (int i = startIdx + 1 ; i < ts.length ; i++) {
3719                     Type superType = asSuper(ts[i], erasedSupertype.tsym);
3720                     lci = intersect(lci, superType != null ? List.of(superType) : List.<Type>nil());
3721                 }
3722                 candidates = candidates.appendList(lci);
3723             }
3724             //step 4 - let MEC be { G1, G2 ... Gn }, then we have that
3725             //lub = lci(Inv(G1)) & lci(Inv(G2)) & ... & lci(Inv(Gn))
3726             return compoundMin(candidates);
3727 
3728         default:
3729             // calculate lub(A, B[])
3730             List<Type> classes = List.of(arraySuperType());
3731             for (int i = 0 ; i < ts.length ; i++) {
3732                 if (kinds[i] != ARRAY_BOUND) // Filter out any arrays
3733                     classes = classes.prepend(ts[i]);
3734             }
3735             // lub(A, B[]) is lub(A, arraySuperType)
3736             return lub(classes);
3737         }
3738     }
3739     // where
3740         List<Type> erasedSupertypes(Type t) {
3741             ListBuffer<Type> buf = new ListBuffer<>();
3742             for (Type sup : closure(t)) {
3743                 if (sup.hasTag(TYPEVAR)) {
3744                     buf.append(sup);
3745                 } else {
3746                     buf.append(erasure(sup));
3747                 }
3748             }
3749             return buf.toList();
3750         }
3751 
3752         private Type arraySuperType = null;
3753         private Type arraySuperType() {
3754             // initialized lazily to avoid problems during compiler startup
3755             if (arraySuperType == null) {
3756                 synchronized (this) {
3757                     if (arraySuperType == null) {
3758                         // JLS 10.8: all arrays implement Cloneable and Serializable.
3759                         arraySuperType = makeIntersectionType(List.of(syms.serializableType,
3760                                 syms.cloneableType), true);
3761                     }
3762                 }
3763             }
3764             return arraySuperType;
3765         }
3766     // </editor-fold>
3767 
3768     // <editor-fold defaultstate="collapsed" desc="Greatest lower bound">
3769     public Type glb(List<Type> ts) {
3770         Type t1 = ts.head;
3771         for (Type t2 : ts.tail) {
3772             if (t1.isErroneous())
3773                 return t1;
3774             t1 = glb(t1, t2);
3775         }
3776         return t1;
3777     }
3778     //where
3779     public Type glb(Type t, Type s) {
3780         if (s == null)
3781             return t;
3782         else if (t.isPrimitive() || s.isPrimitive())
3783             return syms.errType;
3784         else if (isSubtypeNoCapture(t, s))
3785             return t;
3786         else if (isSubtypeNoCapture(s, t))
3787             return s;
3788 
3789         List<Type> closure = union(closure(t), closure(s));
3790         return glbFlattened(closure, t);
3791     }
3792     //where
3793     /**
3794      * Perform glb for a list of non-primitive, non-error, non-compound types;
3795      * redundant elements are removed.  Bounds should be ordered according to
3796      * {@link Symbol#precedes(TypeSymbol,Types)}.
3797      *
3798      * @param flatBounds List of type to glb
3799      * @param errT Original type to use if the result is an error type
3800      */
3801     private Type glbFlattened(List<Type> flatBounds, Type errT) {
3802         List<Type> bounds = closureMin(flatBounds);
3803 
3804         if (bounds.isEmpty()) {             // length == 0
3805             return syms.objectType;
3806         } else if (bounds.tail.isEmpty()) { // length == 1
3807             return bounds.head;
3808         } else {                            // length > 1
3809             int classCount = 0;
3810             List<Type> lowers = List.nil();
3811             for (Type bound : bounds) {
3812                 if (!bound.isInterface()) {
3813                     classCount++;
3814                     Type lower = cvarLowerBound(bound);
3815                     if (bound != lower && !lower.hasTag(BOT))
3816                         lowers = insert(lowers, lower);
3817                 }
3818             }
3819             if (classCount > 1) {
3820                 if (lowers.isEmpty())
3821                     return createErrorType(errT);
3822                 else
3823                     return glbFlattened(union(bounds, lowers), errT);
3824             }
3825         }
3826         return makeIntersectionType(bounds);
3827     }
3828     // </editor-fold>
3829 
3830     // <editor-fold defaultstate="collapsed" desc="hashCode">
3831     /**
3832      * Compute a hash code on a type.
3833      */
3834     public int hashCode(Type t) {
3835         return hashCode.visit(t);
3836     }
3837     // where
3838         private static final UnaryVisitor<Integer> hashCode = new UnaryVisitor<Integer>() {
3839 
3840             public Integer visitType(Type t, Void ignored) {
3841                 return t.getTag().ordinal();
3842             }
3843 
3844             @Override
3845             public Integer visitClassType(ClassType t, Void ignored) {
3846                 int result = visit(t.getEnclosingType());
3847                 result *= 127;
3848                 result += t.tsym.flatName().hashCode();
3849                 for (Type s : t.getTypeArguments()) {
3850                     result *= 127;
3851                     result += visit(s);
3852                 }
3853                 return result;
3854             }
3855 
3856             @Override
3857             public Integer visitMethodType(MethodType t, Void ignored) {
3858                 int h = METHOD.ordinal();
3859                 for (List<Type> thisargs = t.argtypes;
3860                      thisargs.tail != null;
3861                      thisargs = thisargs.tail)
3862                     h = (h << 5) + visit(thisargs.head);
3863                 return (h << 5) + visit(t.restype);
3864             }
3865 
3866             @Override
3867             public Integer visitWildcardType(WildcardType t, Void ignored) {
3868                 int result = t.kind.hashCode();
3869                 if (t.type != null) {
3870                     result *= 127;
3871                     result += visit(t.type);
3872                 }
3873                 return result;
3874             }
3875 
3876             @Override
3877             public Integer visitArrayType(ArrayType t, Void ignored) {
3878                 return visit(t.elemtype) + 12;
3879             }
3880 
3881             @Override
3882             public Integer visitTypeVar(TypeVar t, Void ignored) {
3883                 return System.identityHashCode(t.tsym);
3884             }
3885 
3886             @Override
3887             public Integer visitUndetVar(UndetVar t, Void ignored) {
3888                 return System.identityHashCode(t);
3889             }
3890 
3891             @Override
3892             public Integer visitErrorType(ErrorType t, Void ignored) {
3893                 return 0;
3894             }
3895         };
3896     // </editor-fold>
3897 
3898     // <editor-fold defaultstate="collapsed" desc="Return-Type-Substitutable">
3899     /**
3900      * Does t have a result that is a subtype of the result type of s,
3901      * suitable for covariant returns?  It is assumed that both types
3902      * are (possibly polymorphic) method types.  Monomorphic method
3903      * types are handled in the obvious way.  Polymorphic method types
3904      * require renaming all type variables of one to corresponding
3905      * type variables in the other, where correspondence is by
3906      * position in the type parameter list. */
3907     public boolean resultSubtype(Type t, Type s, Warner warner) {
3908         List<Type> tvars = t.getTypeArguments();
3909         List<Type> svars = s.getTypeArguments();
3910         Type tres = t.getReturnType();
3911         Type sres = subst(s.getReturnType(), svars, tvars);
3912         return covariantReturnType(tres, sres, warner);
3913     }
3914 
3915     /**
3916      * Return-Type-Substitutable.
3917      * @jls section 8.4.5
3918      */
3919     public boolean returnTypeSubstitutable(Type r1, Type r2) {
3920         if (hasSameArgs(r1, r2))
3921             return resultSubtype(r1, r2, noWarnings);
3922         else
3923             return covariantReturnType(r1.getReturnType(),
3924                                        erasure(r2.getReturnType()),
3925                                        noWarnings);
3926     }
3927 
3928     public boolean returnTypeSubstitutable(Type r1,
3929                                            Type r2, Type r2res,
3930                                            Warner warner) {
3931         if (isSameType(r1.getReturnType(), r2res))
3932             return true;
3933         if (r1.getReturnType().isPrimitive() || r2res.isPrimitive())
3934             return false;
3935 
3936         if (hasSameArgs(r1, r2))
3937             return covariantReturnType(r1.getReturnType(), r2res, warner);
3938         if (!allowCovariantReturns)
3939             return false;
3940         if (isSubtypeUnchecked(r1.getReturnType(), r2res, warner))
3941             return true;
3942         if (!isSubtype(r1.getReturnType(), erasure(r2res)))
3943             return false;
3944         warner.warn(LintCategory.UNCHECKED);
3945         return true;
3946     }
3947 
3948     /**
3949      * Is t an appropriate return type in an overrider for a
3950      * method that returns s?
3951      */
3952     public boolean covariantReturnType(Type t, Type s, Warner warner) {
3953         return
3954             isSameType(t, s) ||
3955             allowCovariantReturns &&
3956             !t.isPrimitive() &&
3957             !s.isPrimitive() &&
3958             isAssignable(t, s, warner);
3959     }
3960     // </editor-fold>
3961 
3962     // <editor-fold defaultstate="collapsed" desc="Box/unbox support">
3963     /**
3964      * Return the class that boxes the given primitive.
3965      */
3966     public ClassSymbol boxedClass(Type t) {
3967         return reader.enterClass(syms.boxedName[t.getTag().ordinal()]);
3968     }
3969 
3970     /**
3971      * Return the boxed type if 't' is primitive, otherwise return 't' itself.
3972      */
3973     public Type boxedTypeOrType(Type t) {
3974         return t.isPrimitive() ?
3975             boxedClass(t).type :
3976             t;
3977     }
3978 
3979     /**
3980      * Return the primitive type corresponding to a boxed type.
3981      */
3982     public Type unboxedType(Type t) {
3983         if (allowBoxing) {
3984             for (int i=0; i<syms.boxedName.length; i++) {
3985                 Name box = syms.boxedName[i];
3986                 if (box != null &&
3987                     asSuper(t, reader.enterClass(box)) != null)
3988                     return syms.typeOfTag[i];
3989             }
3990         }
3991         return Type.noType;
3992     }
3993 
3994     /**
3995      * Return the unboxed type if 't' is a boxed class, otherwise return 't' itself.
3996      */
3997     public Type unboxedTypeOrType(Type t) {
3998         Type unboxedType = unboxedType(t);
3999         return unboxedType.hasTag(NONE) ? t : unboxedType;
4000     }
4001     // </editor-fold>
4002 
4003     // <editor-fold defaultstate="collapsed" desc="Capture conversion">
4004     /*
4005      * JLS 5.1.10 Capture Conversion:
4006      *
4007      * Let G name a generic type declaration with n formal type
4008      * parameters A1 ... An with corresponding bounds U1 ... Un. There
4009      * exists a capture conversion from G<T1 ... Tn> to G<S1 ... Sn>,
4010      * where, for 1 <= i <= n:
4011      *
4012      * + If Ti is a wildcard type argument (4.5.1) of the form ? then
4013      *   Si is a fresh type variable whose upper bound is
4014      *   Ui[A1 := S1, ..., An := Sn] and whose lower bound is the null
4015      *   type.
4016      *
4017      * + If Ti is a wildcard type argument of the form ? extends Bi,
4018      *   then Si is a fresh type variable whose upper bound is
4019      *   glb(Bi, Ui[A1 := S1, ..., An := Sn]) and whose lower bound is
4020      *   the null type, where glb(V1,... ,Vm) is V1 & ... & Vm. It is
4021      *   a compile-time error if for any two classes (not interfaces)
4022      *   Vi and Vj,Vi is not a subclass of Vj or vice versa.
4023      *
4024      * + If Ti is a wildcard type argument of the form ? super Bi,
4025      *   then Si is a fresh type variable whose upper bound is
4026      *   Ui[A1 := S1, ..., An := Sn] and whose lower bound is Bi.
4027      *
4028      * + Otherwise, Si = Ti.
4029      *
4030      * Capture conversion on any type other than a parameterized type
4031      * (4.5) acts as an identity conversion (5.1.1). Capture
4032      * conversions never require a special action at run time and
4033      * therefore never throw an exception at run time.
4034      *
4035      * Capture conversion is not applied recursively.
4036      */
4037     /**
4038      * Capture conversion as specified by the JLS.
4039      */
4040 
4041     public List<Type> capture(List<Type> ts) {
4042         List<Type> buf = List.nil();
4043         for (Type t : ts) {
4044             buf = buf.prepend(capture(t));
4045         }
4046         return buf.reverse();
4047     }
4048 
4049     public Type capture(Type t) {
4050         if (!t.hasTag(CLASS)) {
4051             return t;
4052         }
4053         if (t.getEnclosingType() != Type.noType) {
4054             Type capturedEncl = capture(t.getEnclosingType());
4055             if (capturedEncl != t.getEnclosingType()) {
4056                 Type type1 = memberType(capturedEncl, t.tsym);
4057                 t = subst(type1, t.tsym.type.getTypeArguments(), t.getTypeArguments());
4058             }
4059         }
4060         t = t.unannotatedType();
4061         ClassType cls = (ClassType)t;
4062         if (cls.isRaw() || !cls.isParameterized())
4063             return cls;
4064 
4065         ClassType G = (ClassType)cls.asElement().asType();
4066         List<Type> A = G.getTypeArguments();
4067         List<Type> T = cls.getTypeArguments();
4068         List<Type> S = freshTypeVariables(T);
4069 
4070         List<Type> currentA = A;
4071         List<Type> currentT = T;
4072         List<Type> currentS = S;
4073         boolean captured = false;
4074         while (!currentA.isEmpty() &&
4075                !currentT.isEmpty() &&
4076                !currentS.isEmpty()) {
4077             if (currentS.head != currentT.head) {
4078                 captured = true;
4079                 WildcardType Ti = (WildcardType)currentT.head.unannotatedType();
4080                 Type Ui = currentA.head.getUpperBound();
4081                 CapturedType Si = (CapturedType)currentS.head.unannotatedType();
4082                 if (Ui == null)
4083                     Ui = syms.objectType;
4084                 switch (Ti.kind) {
4085                 case UNBOUND:
4086                     Si.bound = subst(Ui, A, S);
4087                     Si.lower = syms.botType;
4088                     break;
4089                 case EXTENDS:
4090                     Si.bound = glb(Ti.getExtendsBound(), subst(Ui, A, S));
4091                     Si.lower = syms.botType;
4092                     break;
4093                 case SUPER:
4094                     Si.bound = subst(Ui, A, S);
4095                     Si.lower = Ti.getSuperBound();
4096                     break;
4097                 }
4098                 Type tmpBound = Si.bound.hasTag(UNDETVAR) ? ((UndetVar)Si.bound).qtype : Si.bound;
4099                 Type tmpLower = Si.lower.hasTag(UNDETVAR) ? ((UndetVar)Si.lower).qtype : Si.lower;
4100                 if (!Si.bound.hasTag(ERROR) &&
4101                     !Si.lower.hasTag(ERROR) &&
4102                     isSameType(tmpBound, tmpLower, false)) {
4103                     currentS.head = Si.bound;
4104                 }
4105             }
4106             currentA = currentA.tail;
4107             currentT = currentT.tail;
4108             currentS = currentS.tail;
4109         }
4110         if (!currentA.isEmpty() || !currentT.isEmpty() || !currentS.isEmpty())
4111             return erasure(t); // some "rare" type involved
4112 
4113         if (captured)
4114             return new ClassType(cls.getEnclosingType(), S, cls.tsym);
4115         else
4116             return t;
4117     }
4118     // where
4119         public List<Type> freshTypeVariables(List<Type> types) {
4120             ListBuffer<Type> result = new ListBuffer<>();
4121             for (Type t : types) {
4122                 if (t.hasTag(WILDCARD)) {
4123                     t = t.unannotatedType();
4124                     Type bound = ((WildcardType)t).getExtendsBound();
4125                     if (bound == null)
4126                         bound = syms.objectType;
4127                     result.append(new CapturedType(capturedName,
4128                                                    syms.noSymbol,
4129                                                    bound,
4130                                                    syms.botType,
4131                                                    (WildcardType)t));
4132                 } else {
4133                     result.append(t);
4134                 }
4135             }
4136             return result.toList();
4137         }
4138     // </editor-fold>
4139 
4140     // <editor-fold defaultstate="collapsed" desc="Internal utility methods">
4141     private boolean sideCast(Type from, Type to, Warner warn) {
4142         // We are casting from type $from$ to type $to$, which are
4143         // non-final unrelated types.  This method
4144         // tries to reject a cast by transferring type parameters
4145         // from $to$ to $from$ by common superinterfaces.
4146         boolean reverse = false;
4147         Type target = to;
4148         if ((to.tsym.flags() & INTERFACE) == 0) {
4149             Assert.check((from.tsym.flags() & INTERFACE) != 0);
4150             reverse = true;
4151             to = from;
4152             from = target;
4153         }
4154         List<Type> commonSupers = superClosure(to, erasure(from));
4155         boolean giveWarning = commonSupers.isEmpty();
4156         // The arguments to the supers could be unified here to
4157         // get a more accurate analysis
4158         while (commonSupers.nonEmpty()) {
4159             Type t1 = asSuper(from, commonSupers.head.tsym);
4160             Type t2 = commonSupers.head; // same as asSuper(to, commonSupers.head.tsym);
4161             if (disjointTypes(t1.getTypeArguments(), t2.getTypeArguments()))
4162                 return false;
4163             giveWarning = giveWarning || (reverse ? giveWarning(t2, t1) : giveWarning(t1, t2));
4164             commonSupers = commonSupers.tail;
4165         }
4166         if (giveWarning && !isReifiable(reverse ? from : to))
4167             warn.warn(LintCategory.UNCHECKED);
4168         if (!allowCovariantReturns)
4169             // reject if there is a common method signature with
4170             // incompatible return types.
4171             chk.checkCompatibleAbstracts(warn.pos(), from, to);
4172         return true;
4173     }
4174 
4175     private boolean sideCastFinal(Type from, Type to, Warner warn) {
4176         // We are casting from type $from$ to type $to$, which are
4177         // unrelated types one of which is final and the other of
4178         // which is an interface.  This method
4179         // tries to reject a cast by transferring type parameters
4180         // from the final class to the interface.
4181         boolean reverse = false;
4182         Type target = to;
4183         if ((to.tsym.flags() & INTERFACE) == 0) {
4184             Assert.check((from.tsym.flags() & INTERFACE) != 0);
4185             reverse = true;
4186             to = from;
4187             from = target;
4188         }
4189         Assert.check((from.tsym.flags() & FINAL) != 0);
4190         Type t1 = asSuper(from, to.tsym);
4191         if (t1 == null) return false;
4192         Type t2 = to;
4193         if (disjointTypes(t1.getTypeArguments(), t2.getTypeArguments()))
4194             return false;
4195         if (!allowCovariantReturns)
4196             // reject if there is a common method signature with
4197             // incompatible return types.
4198             chk.checkCompatibleAbstracts(warn.pos(), from, to);
4199         if (!isReifiable(target) &&
4200             (reverse ? giveWarning(t2, t1) : giveWarning(t1, t2)))
4201             warn.warn(LintCategory.UNCHECKED);
4202         return true;
4203     }
4204 
4205     private boolean giveWarning(Type from, Type to) {
4206         List<Type> bounds = to.isCompound() ?
4207                 ((IntersectionClassType)to.unannotatedType()).getComponents() : List.of(to);
4208         for (Type b : bounds) {
4209             Type subFrom = asSub(from, b.tsym);
4210             if (b.isParameterized() &&
4211                     (!(isUnbounded(b) ||
4212                     isSubtype(from, b) ||
4213                     ((subFrom != null) && containsType(b.allparams(), subFrom.allparams()))))) {
4214                 return true;
4215             }
4216         }
4217         return false;
4218     }
4219 
4220     private List<Type> superClosure(Type t, Type s) {
4221         List<Type> cl = List.nil();
4222         for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail) {
4223             if (isSubtype(s, erasure(l.head))) {
4224                 cl = insert(cl, l.head);
4225             } else {
4226                 cl = union(cl, superClosure(l.head, s));
4227             }
4228         }
4229         return cl;
4230     }
4231 
4232     private boolean containsTypeEquivalent(Type t, Type s) {
4233         return
4234             isSameType(t, s) || // shortcut
4235             containsType(t, s) && containsType(s, t);
4236     }
4237 
4238     // <editor-fold defaultstate="collapsed" desc="adapt">
4239     /**
4240      * Adapt a type by computing a substitution which maps a source
4241      * type to a target type.
4242      *
4243      * @param source    the source type
4244      * @param target    the target type
4245      * @param from      the type variables of the computed substitution
4246      * @param to        the types of the computed substitution.
4247      */
4248     public void adapt(Type source,
4249                        Type target,
4250                        ListBuffer<Type> from,
4251                        ListBuffer<Type> to) throws AdaptFailure {
4252         new Adapter(from, to).adapt(source, target);
4253     }
4254 
4255     class Adapter extends SimpleVisitor<Void, Type> {
4256 
4257         ListBuffer<Type> from;
4258         ListBuffer<Type> to;
4259         Map<Symbol,Type> mapping;
4260 
4261         Adapter(ListBuffer<Type> from, ListBuffer<Type> to) {
4262             this.from = from;
4263             this.to = to;
4264             mapping = new HashMap<Symbol,Type>();
4265         }
4266 
4267         public void adapt(Type source, Type target) throws AdaptFailure {
4268             visit(source, target);
4269             List<Type> fromList = from.toList();
4270             List<Type> toList = to.toList();
4271             while (!fromList.isEmpty()) {
4272                 Type val = mapping.get(fromList.head.tsym);
4273                 if (toList.head != val)
4274                     toList.head = val;
4275                 fromList = fromList.tail;
4276                 toList = toList.tail;
4277             }
4278         }
4279 
4280         @Override
4281         public Void visitClassType(ClassType source, Type target) throws AdaptFailure {
4282             if (target.hasTag(CLASS))
4283                 adaptRecursive(source.allparams(), target.allparams());
4284             return null;
4285         }
4286 
4287         @Override
4288         public Void visitArrayType(ArrayType source, Type target) throws AdaptFailure {
4289             if (target.hasTag(ARRAY))
4290                 adaptRecursive(elemtype(source), elemtype(target));
4291             return null;
4292         }
4293 
4294         @Override
4295         public Void visitWildcardType(WildcardType source, Type target) throws AdaptFailure {
4296             if (source.isExtendsBound())
4297                 adaptRecursive(wildUpperBound(source), wildUpperBound(target));
4298             else if (source.isSuperBound())
4299                 adaptRecursive(wildLowerBound(source), wildLowerBound(target));
4300             return null;
4301         }
4302 
4303         @Override
4304         public Void visitTypeVar(TypeVar source, Type target) throws AdaptFailure {
4305             // Check to see if there is
4306             // already a mapping for $source$, in which case
4307             // the old mapping will be merged with the new
4308             Type val = mapping.get(source.tsym);
4309             if (val != null) {
4310                 if (val.isSuperBound() && target.isSuperBound()) {
4311                     val = isSubtype(wildLowerBound(val), wildLowerBound(target))
4312                         ? target : val;
4313                 } else if (val.isExtendsBound() && target.isExtendsBound()) {
4314                     val = isSubtype(wildUpperBound(val), wildUpperBound(target))
4315                         ? val : target;
4316                 } else if (!isSameType(val, target)) {
4317                     throw new AdaptFailure();
4318                 }
4319             } else {
4320                 val = target;
4321                 from.append(source);
4322                 to.append(target);
4323             }
4324             mapping.put(source.tsym, val);
4325             return null;
4326         }
4327 
4328         @Override
4329         public Void visitType(Type source, Type target) {
4330             return null;
4331         }
4332 
4333         private Set<TypePair> cache = new HashSet<TypePair>();
4334 
4335         private void adaptRecursive(Type source, Type target) {
4336             TypePair pair = new TypePair(source, target);
4337             if (cache.add(pair)) {
4338                 try {
4339                     visit(source, target);
4340                 } finally {
4341                     cache.remove(pair);
4342                 }
4343             }
4344         }
4345 
4346         private void adaptRecursive(List<Type> source, List<Type> target) {
4347             if (source.length() == target.length()) {
4348                 while (source.nonEmpty()) {
4349                     adaptRecursive(source.head, target.head);
4350                     source = source.tail;
4351                     target = target.tail;
4352                 }
4353             }
4354         }
4355     }
4356 
4357     public static class AdaptFailure extends RuntimeException {
4358         static final long serialVersionUID = -7490231548272701566L;
4359     }
4360 
4361     private void adaptSelf(Type t,
4362                            ListBuffer<Type> from,
4363                            ListBuffer<Type> to) {
4364         try {
4365             //if (t.tsym.type != t)
4366                 adapt(t.tsym.type, t, from, to);
4367         } catch (AdaptFailure ex) {
4368             // Adapt should never fail calculating a mapping from
4369             // t.tsym.type to t as there can be no merge problem.
4370             throw new AssertionError(ex);
4371         }
4372     }
4373     // </editor-fold>
4374 
4375     /**
4376      * Rewrite all type variables (universal quantifiers) in the given
4377      * type to wildcards (existential quantifiers).  This is used to
4378      * determine if a cast is allowed.  For example, if high is true
4379      * and {@code T <: Number}, then {@code List<T>} is rewritten to
4380      * {@code List<?  extends Number>}.  Since {@code List<Integer> <:
4381      * List<? extends Number>} a {@code List<T>} can be cast to {@code
4382      * List<Integer>} with a warning.
4383      * @param t a type
4384      * @param high if true return an upper bound; otherwise a lower
4385      * bound
4386      * @param rewriteTypeVars only rewrite captured wildcards if false;
4387      * otherwise rewrite all type variables
4388      * @return the type rewritten with wildcards (existential
4389      * quantifiers) only
4390      */
4391     private Type rewriteQuantifiers(Type t, boolean high, boolean rewriteTypeVars) {
4392         return new Rewriter(high, rewriteTypeVars).visit(t);
4393     }
4394 
4395     class Rewriter extends UnaryVisitor<Type> {
4396 
4397         boolean high;
4398         boolean rewriteTypeVars;
4399 
4400         Rewriter(boolean high, boolean rewriteTypeVars) {
4401             this.high = high;
4402             this.rewriteTypeVars = rewriteTypeVars;
4403         }
4404 
4405         @Override
4406         public Type visitClassType(ClassType t, Void s) {
4407             ListBuffer<Type> rewritten = new ListBuffer<Type>();
4408             boolean changed = false;
4409             for (Type arg : t.allparams()) {
4410                 Type bound = visit(arg);
4411                 if (arg != bound) {
4412                     changed = true;
4413                 }
4414                 rewritten.append(bound);
4415             }
4416             if (changed)
4417                 return subst(t.tsym.type,
4418                         t.tsym.type.allparams(),
4419                         rewritten.toList());
4420             else
4421                 return t;
4422         }
4423 
4424         public Type visitType(Type t, Void s) {
4425             return t;
4426         }
4427 
4428         @Override
4429         public Type visitCapturedType(CapturedType t, Void s) {
4430             Type w_bound = t.wildcard.type;
4431             Type bound = w_bound.contains(t) ?
4432                         erasure(w_bound) :
4433                         visit(w_bound);
4434             return rewriteAsWildcardType(visit(bound), t.wildcard.bound, t.wildcard.kind);
4435         }
4436 
4437         @Override
4438         public Type visitTypeVar(TypeVar t, Void s) {
4439             if (rewriteTypeVars) {
4440                 Type bound = t.bound.contains(t) ?
4441                         erasure(t.bound) :
4442                         visit(t.bound);
4443                 return rewriteAsWildcardType(bound, t, EXTENDS);
4444             } else {
4445                 return t;
4446             }
4447         }
4448 
4449         @Override
4450         public Type visitWildcardType(WildcardType t, Void s) {
4451             Type bound2 = visit(t.type);
4452             return t.type == bound2 ? t : rewriteAsWildcardType(bound2, t.bound, t.kind);
4453         }
4454 
4455         private Type rewriteAsWildcardType(Type bound, TypeVar formal, BoundKind bk) {
4456             switch (bk) {
4457                case EXTENDS: return high ?
4458                        makeExtendsWildcard(B(bound), formal) :
4459                        makeExtendsWildcard(syms.objectType, formal);
4460                case SUPER: return high ?
4461                        makeSuperWildcard(syms.botType, formal) :
4462                        makeSuperWildcard(B(bound), formal);
4463                case UNBOUND: return makeExtendsWildcard(syms.objectType, formal);
4464                default:
4465                    Assert.error("Invalid bound kind " + bk);
4466                    return null;
4467             }
4468         }
4469 
4470         Type B(Type t) {
4471             while (t.hasTag(WILDCARD)) {
4472                 WildcardType w = (WildcardType)t.unannotatedType();
4473                 t = high ?
4474                     w.getExtendsBound() :
4475                     w.getSuperBound();
4476                 if (t == null) {
4477                     t = high ? syms.objectType : syms.botType;
4478                 }
4479             }
4480             return t;
4481         }
4482     }
4483 
4484 
4485     /**
4486      * Create a wildcard with the given upper (extends) bound; create
4487      * an unbounded wildcard if bound is Object.
4488      *
4489      * @param bound the upper bound
4490      * @param formal the formal type parameter that will be
4491      * substituted by the wildcard
4492      */
4493     private WildcardType makeExtendsWildcard(Type bound, TypeVar formal) {
4494         if (bound == syms.objectType) {
4495             return new WildcardType(syms.objectType,
4496                                     BoundKind.UNBOUND,
4497                                     syms.boundClass,
4498                                     formal);
4499         } else {
4500             return new WildcardType(bound,
4501                                     BoundKind.EXTENDS,
4502                                     syms.boundClass,
4503                                     formal);
4504         }
4505     }
4506 
4507     /**
4508      * Create a wildcard with the given lower (super) bound; create an
4509      * unbounded wildcard if bound is bottom (type of {@code null}).
4510      *
4511      * @param bound the lower bound
4512      * @param formal the formal type parameter that will be
4513      * substituted by the wildcard
4514      */
4515     private WildcardType makeSuperWildcard(Type bound, TypeVar formal) {
4516         if (bound.hasTag(BOT)) {
4517             return new WildcardType(syms.objectType,
4518                                     BoundKind.UNBOUND,
4519                                     syms.boundClass,
4520                                     formal);
4521         } else {
4522             return new WildcardType(bound,
4523                                     BoundKind.SUPER,
4524                                     syms.boundClass,
4525                                     formal);
4526         }
4527     }
4528 
4529     /**
4530      * A wrapper for a type that allows use in sets.
4531      */
4532     public static class UniqueType {
4533         public final Type type;
4534         final Types types;
4535 
4536         public UniqueType(Type type, Types types) {
4537             this.type = type;
4538             this.types = types;
4539         }
4540 
4541         public int hashCode() {
4542             return types.hashCode(type);
4543         }
4544 
4545         public boolean equals(Object obj) {
4546             return (obj instanceof UniqueType) &&
4547                 types.isSameAnnotatedType(type, ((UniqueType)obj).type);
4548         }
4549 
4550         public String toString() {
4551             return type.toString();
4552         }
4553 
4554     }
4555     // </editor-fold>
4556 
4557     // <editor-fold defaultstate="collapsed" desc="Visitors">
4558     /**
4559      * A default visitor for types.  All visitor methods except
4560      * visitType are implemented by delegating to visitType.  Concrete
4561      * subclasses must provide an implementation of visitType and can
4562      * override other methods as needed.
4563      *
4564      * @param <R> the return type of the operation implemented by this
4565      * visitor; use Void if no return type is needed.
4566      * @param <S> the type of the second argument (the first being the
4567      * type itself) of the operation implemented by this visitor; use
4568      * Void if a second argument is not needed.
4569      */
4570     public static abstract class DefaultTypeVisitor<R,S> implements Type.Visitor<R,S> {
4571         final public R visit(Type t, S s)               { return t.accept(this, s); }
4572         public R visitClassType(ClassType t, S s)       { return visitType(t, s); }
4573         public R visitWildcardType(WildcardType t, S s) { return visitType(t, s); }
4574         public R visitArrayType(ArrayType t, S s)       { return visitType(t, s); }
4575         public R visitMethodType(MethodType t, S s)     { return visitType(t, s); }
4576         public R visitPackageType(PackageType t, S s)   { return visitType(t, s); }
4577         public R visitTypeVar(TypeVar t, S s)           { return visitType(t, s); }
4578         public R visitCapturedType(CapturedType t, S s) { return visitType(t, s); }
4579         public R visitForAll(ForAll t, S s)             { return visitType(t, s); }
4580         public R visitUndetVar(UndetVar t, S s)         { return visitType(t, s); }
4581         public R visitErrorType(ErrorType t, S s)       { return visitType(t, s); }
4582         // Pretend annotations don't exist
4583         public R visitAnnotatedType(AnnotatedType t, S s) { return visit(t.unannotatedType(), s); }
4584     }
4585 
4586     /**
4587      * A default visitor for symbols.  All visitor methods except
4588      * visitSymbol are implemented by delegating to visitSymbol.  Concrete
4589      * subclasses must provide an implementation of visitSymbol and can
4590      * override other methods as needed.
4591      *
4592      * @param <R> the return type of the operation implemented by this
4593      * visitor; use Void if no return type is needed.
4594      * @param <S> the type of the second argument (the first being the
4595      * symbol itself) of the operation implemented by this visitor; use
4596      * Void if a second argument is not needed.
4597      */
4598     public static abstract class DefaultSymbolVisitor<R,S> implements Symbol.Visitor<R,S> {
4599         final public R visit(Symbol s, S arg)                   { return s.accept(this, arg); }
4600         public R visitClassSymbol(ClassSymbol s, S arg)         { return visitSymbol(s, arg); }
4601         public R visitMethodSymbol(MethodSymbol s, S arg)       { return visitSymbol(s, arg); }
4602         public R visitOperatorSymbol(OperatorSymbol s, S arg)   { return visitSymbol(s, arg); }
4603         public R visitPackageSymbol(PackageSymbol s, S arg)     { return visitSymbol(s, arg); }
4604         public R visitTypeSymbol(TypeSymbol s, S arg)           { return visitSymbol(s, arg); }
4605         public R visitVarSymbol(VarSymbol s, S arg)             { return visitSymbol(s, arg); }
4606     }
4607 
4608     /**
4609      * A <em>simple</em> visitor for types.  This visitor is simple as
4610      * captured wildcards, for-all types (generic methods), and
4611      * undetermined type variables (part of inference) are hidden.
4612      * Captured wildcards are hidden by treating them as type
4613      * variables and the rest are hidden by visiting their qtypes.
4614      *
4615      * @param <R> the return type of the operation implemented by this
4616      * visitor; use Void if no return type is needed.
4617      * @param <S> the type of the second argument (the first being the
4618      * type itself) of the operation implemented by this visitor; use
4619      * Void if a second argument is not needed.
4620      */
4621     public static abstract class SimpleVisitor<R,S> extends DefaultTypeVisitor<R,S> {
4622         @Override
4623         public R visitCapturedType(CapturedType t, S s) {
4624             return visitTypeVar(t, s);
4625         }
4626         @Override
4627         public R visitForAll(ForAll t, S s) {
4628             return visit(t.qtype, s);
4629         }
4630         @Override
4631         public R visitUndetVar(UndetVar t, S s) {
4632             return visit(t.qtype, s);
4633         }
4634     }
4635 
4636     /**
4637      * A plain relation on types.  That is a 2-ary function on the
4638      * form Type&nbsp;&times;&nbsp;Type&nbsp;&rarr;&nbsp;Boolean.
4639      * <!-- In plain text: Type x Type -> Boolean -->
4640      */
4641     public static abstract class TypeRelation extends SimpleVisitor<Boolean,Type> {}
4642 
4643     /**
4644      * A convenience visitor for implementing operations that only
4645      * require one argument (the type itself), that is, unary
4646      * operations.
4647      *
4648      * @param <R> the return type of the operation implemented by this
4649      * visitor; use Void if no return type is needed.
4650      */
4651     public static abstract class UnaryVisitor<R> extends SimpleVisitor<R,Void> {
4652         final public R visit(Type t) { return t.accept(this, null); }
4653     }
4654 
4655     /**
4656      * A visitor for implementing a mapping from types to types.  The
4657      * default behavior of this class is to implement the identity
4658      * mapping (mapping a type to itself).  This can be overridden in
4659      * subclasses.
4660      *
4661      * @param <S> the type of the second argument (the first being the
4662      * type itself) of this mapping; use Void if a second argument is
4663      * not needed.
4664      */
4665     public static class MapVisitor<S> extends DefaultTypeVisitor<Type,S> {
4666         final public Type visit(Type t) { return t.accept(this, null); }
4667         public Type visitType(Type t, S s) { return t; }
4668     }
4669     // </editor-fold>
4670 
4671 
4672     // <editor-fold defaultstate="collapsed" desc="Annotation support">
4673 
4674     public RetentionPolicy getRetention(Attribute.Compound a) {
4675         return getRetention(a.type.tsym);
4676     }
4677 
4678     public RetentionPolicy getRetention(Symbol sym) {
4679         RetentionPolicy vis = RetentionPolicy.CLASS; // the default
4680         Attribute.Compound c = sym.attribute(syms.retentionType.tsym);
4681         if (c != null) {
4682             Attribute value = c.member(names.value);
4683             if (value != null && value instanceof Attribute.Enum) {
4684                 Name levelName = ((Attribute.Enum)value).value.name;
4685                 if (levelName == names.SOURCE) vis = RetentionPolicy.SOURCE;
4686                 else if (levelName == names.CLASS) vis = RetentionPolicy.CLASS;
4687                 else if (levelName == names.RUNTIME) vis = RetentionPolicy.RUNTIME;
4688                 else ;// /* fail soft */ throw new AssertionError(levelName);
4689             }
4690         }
4691         return vis;
4692     }
4693     // </editor-fold>
4694 
4695     // <editor-fold defaultstate="collapsed" desc="Signature Generation">
4696 
4697     public static abstract class SignatureGenerator {
4698 
4699         private final Types types;
4700 
4701         protected abstract void append(char ch);
4702         protected abstract void append(byte[] ba);
4703         protected abstract void append(Name name);
4704         protected void classReference(ClassSymbol c) { /* by default: no-op */ }
4705 
4706         protected SignatureGenerator(Types types) {
4707             this.types = types;
4708         }
4709 
4710         /**
4711          * Assemble signature of given type in string buffer.
4712          */
4713         public void assembleSig(Type type) {
4714             type = type.unannotatedType();
4715             switch (type.getTag()) {
4716                 case BYTE:
4717                     append('B');
4718                     break;
4719                 case SHORT:
4720                     append('S');
4721                     break;
4722                 case CHAR:
4723                     append('C');
4724                     break;
4725                 case INT:
4726                     append('I');
4727                     break;
4728                 case LONG:
4729                     append('J');
4730                     break;
4731                 case FLOAT:
4732                     append('F');
4733                     break;
4734                 case DOUBLE:
4735                     append('D');
4736                     break;
4737                 case BOOLEAN:
4738                     append('Z');
4739                     break;
4740                 case VOID:
4741                     append('V');
4742                     break;
4743                 case CLASS:
4744                     append('L');
4745                     assembleClassSig(type);
4746                     append(';');
4747                     break;
4748                 case ARRAY:
4749                     ArrayType at = (ArrayType) type;
4750                     append('[');
4751                     assembleSig(at.elemtype);
4752                     break;
4753                 case METHOD:
4754                     MethodType mt = (MethodType) type;
4755                     append('(');
4756                     assembleSig(mt.argtypes);
4757                     append(')');
4758                     assembleSig(mt.restype);
4759                     if (hasTypeVar(mt.thrown)) {
4760                         for (List<Type> l = mt.thrown; l.nonEmpty(); l = l.tail) {
4761                             append('^');
4762                             assembleSig(l.head);
4763                         }
4764                     }
4765                     break;
4766                 case WILDCARD: {
4767                     Type.WildcardType ta = (Type.WildcardType) type;
4768                     switch (ta.kind) {
4769                         case SUPER:
4770                             append('-');
4771                             assembleSig(ta.type);
4772                             break;
4773                         case EXTENDS:
4774                             append('+');
4775                             assembleSig(ta.type);
4776                             break;
4777                         case UNBOUND:
4778                             append('*');
4779                             break;
4780                         default:
4781                             throw new AssertionError(ta.kind);
4782                     }
4783                     break;
4784                 }
4785                 case TYPEVAR:
4786                     append('T');
4787                     append(type.tsym.name);
4788                     append(';');
4789                     break;
4790                 case FORALL:
4791                     Type.ForAll ft = (Type.ForAll) type;
4792                     assembleParamsSig(ft.tvars);
4793                     assembleSig(ft.qtype);
4794                     break;
4795                 default:
4796                     throw new AssertionError("typeSig " + type.getTag());
4797             }
4798         }
4799 
4800         public boolean hasTypeVar(List<Type> l) {
4801             while (l.nonEmpty()) {
4802                 if (l.head.hasTag(TypeTag.TYPEVAR)) {
4803                     return true;
4804                 }
4805                 l = l.tail;
4806             }
4807             return false;
4808         }
4809 
4810         public void assembleClassSig(Type type) {
4811             type = type.unannotatedType();
4812             ClassType ct = (ClassType) type;
4813             ClassSymbol c = (ClassSymbol) ct.tsym;
4814             classReference(c);
4815             Type outer = ct.getEnclosingType();
4816             if (outer.allparams().nonEmpty()) {
4817                 boolean rawOuter =
4818                         c.owner.kind == Kinds.MTH || // either a local class
4819                         c.name == types.names.empty; // or anonymous
4820                 assembleClassSig(rawOuter
4821                         ? types.erasure(outer)
4822                         : outer);
4823                 append(rawOuter ? '$' : '.');
4824                 Assert.check(c.flatname.startsWith(c.owner.enclClass().flatname));
4825                 append(rawOuter
4826                         ? c.flatname.subName(c.owner.enclClass().flatname.getByteLength() + 1, c.flatname.getByteLength())
4827                         : c.name);
4828             } else {
4829                 append(externalize(c.flatname));
4830             }
4831             if (ct.getTypeArguments().nonEmpty()) {
4832                 append('<');
4833                 assembleSig(ct.getTypeArguments());
4834                 append('>');
4835             }
4836         }
4837 
4838         public void assembleParamsSig(List<Type> typarams) {
4839             append('<');
4840             for (List<Type> ts = typarams; ts.nonEmpty(); ts = ts.tail) {
4841                 Type.TypeVar tvar = (Type.TypeVar) ts.head;
4842                 append(tvar.tsym.name);
4843                 List<Type> bounds = types.getBounds(tvar);
4844                 if ((bounds.head.tsym.flags() & INTERFACE) != 0) {
4845                     append(':');
4846                 }
4847                 for (List<Type> l = bounds; l.nonEmpty(); l = l.tail) {
4848                     append(':');
4849                     assembleSig(l.head);
4850                 }
4851             }
4852             append('>');
4853         }
4854 
4855         private void assembleSig(List<Type> types) {
4856             for (List<Type> ts = types; ts.nonEmpty(); ts = ts.tail) {
4857                 assembleSig(ts.head);
4858             }
4859         }
4860     }
4861     // </editor-fold>
4862 }