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.isCompound() || s.isCompound()) {
1543                     return !t.isCompound() ?
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="makeCompoundType">
2259     /**
2260      * Make a compound type from non-empty list of types.  The list should be
2261      * ordered according to {@link Symbol#precedes(TypeSymbol,Types)}.
2262      *
2263      * @param bounds            the types from which the compound type is formed
2264      * @param supertype         is objectType if all bounds are interfaces,
2265      *                          null otherwise.
2266      */
2267     public Type makeCompoundType(List<Type> bounds) {
2268         return makeCompoundType(bounds, bounds.head.tsym.isInterface());
2269     }
2270     public Type makeCompoundType(List<Type> bounds, boolean allInterfaces) {
2271         Assert.check(bounds.nonEmpty());
2272         Type firstExplicitBound = bounds.head;
2273         if (allInterfaces) {
2274             bounds = bounds.prepend(syms.objectType);
2275         }
2276         ClassSymbol bc =
2277             new ClassSymbol(ABSTRACT|PUBLIC|SYNTHETIC|COMPOUND|ACYCLIC,
2278                             Type.moreInfo
2279                                 ? names.fromString(bounds.toString())
2280                                 : names.empty,
2281                             null,
2282                             syms.noSymbol);
2283         bc.type = new IntersectionClassType(bounds, bc, allInterfaces);
2284         bc.erasure_field = (bounds.head.hasTag(TYPEVAR)) ?
2285                 syms.objectType : // error condition, recover
2286                 erasure(firstExplicitBound);
2287         bc.members_field = new Scope(bc);
2288         return bc.type;
2289     }
2290 
2291     /**
2292      * A convenience wrapper for {@link #makeCompoundType(List)}; the
2293      * arguments are converted to a list and passed to the other
2294      * method.  Note that this might cause a symbol completion.
2295      * Hence, this version of makeCompoundType may not be called
2296      * during a classfile read.
2297      */
2298     public Type makeCompoundType(Type bound1, Type bound2) {
2299         return makeCompoundType(List.of(bound1, bound2));
2300     }
2301     // </editor-fold>
2302 
2303     // <editor-fold defaultstate="collapsed" desc="supertype">
2304     public Type supertype(Type t) {
2305         return supertype.visit(t);
2306     }
2307     // where
2308         private UnaryVisitor<Type> supertype = new UnaryVisitor<Type>() {
2309 
2310             public Type visitType(Type t, Void ignored) {
2311                 // A note on wildcards: there is no good way to
2312                 // determine a supertype for a super bounded wildcard.
2313                 return Type.noType;
2314             }
2315 
2316             @Override
2317             public Type visitClassType(ClassType t, Void ignored) {
2318                 if (t.supertype_field == null) {
2319                     Type supertype = ((ClassSymbol)t.tsym).getSuperclass();
2320                     // An interface has no superclass; its supertype is Object.
2321                     if (t.isInterface())
2322                         supertype = ((ClassType)t.tsym.type).supertype_field;
2323                     if (t.supertype_field == null) {
2324                         List<Type> actuals = classBound(t).allparams();
2325                         List<Type> formals = t.tsym.type.allparams();
2326                         if (t.hasErasedSupertypes()) {
2327                             t.supertype_field = erasureRecursive(supertype);
2328                         } else if (formals.nonEmpty()) {
2329                             t.supertype_field = subst(supertype, formals, actuals);
2330                         }
2331                         else {
2332                             t.supertype_field = supertype;
2333                         }
2334                     }
2335                 }
2336                 return t.supertype_field;
2337             }
2338 
2339             /**
2340              * The supertype is always a class type. If the type
2341              * variable's bounds start with a class type, this is also
2342              * the supertype.  Otherwise, the supertype is
2343              * java.lang.Object.
2344              */
2345             @Override
2346             public Type visitTypeVar(TypeVar t, Void ignored) {
2347                 if (t.bound.hasTag(TYPEVAR) ||
2348                     (!t.bound.isCompound() && !t.bound.isInterface())) {
2349                     return t.bound;
2350                 } else {
2351                     return supertype(t.bound);
2352                 }
2353             }
2354 
2355             @Override
2356             public Type visitArrayType(ArrayType t, Void ignored) {
2357                 if (t.elemtype.isPrimitive() || isSameType(t.elemtype, syms.objectType))
2358                     return arraySuperType();
2359                 else
2360                     return new ArrayType(supertype(t.elemtype), t.tsym);
2361             }
2362 
2363             @Override
2364             public Type visitErrorType(ErrorType t, Void ignored) {
2365                 return Type.noType;
2366             }
2367         };
2368     // </editor-fold>
2369 
2370     // <editor-fold defaultstate="collapsed" desc="interfaces">
2371     /**
2372      * Return the interfaces implemented by this class.
2373      */
2374     public List<Type> interfaces(Type t) {
2375         return interfaces.visit(t);
2376     }
2377     // where
2378         private UnaryVisitor<List<Type>> interfaces = new UnaryVisitor<List<Type>>() {
2379 
2380             public List<Type> visitType(Type t, Void ignored) {
2381                 return List.nil();
2382             }
2383 
2384             @Override
2385             public List<Type> visitClassType(ClassType t, Void ignored) {
2386                 if (t.interfaces_field == null) {
2387                     List<Type> interfaces = ((ClassSymbol)t.tsym).getInterfaces();
2388                     if (t.interfaces_field == null) {
2389                         // If t.interfaces_field is null, then t must
2390                         // be a parameterized type (not to be confused
2391                         // with a generic type declaration).
2392                         // Terminology:
2393                         //    Parameterized type: List<String>
2394                         //    Generic type declaration: class List<E> { ... }
2395                         // So t corresponds to List<String> and
2396                         // t.tsym.type corresponds to List<E>.
2397                         // The reason t must be parameterized type is
2398                         // that completion will happen as a side
2399                         // effect of calling
2400                         // ClassSymbol.getInterfaces.  Since
2401                         // t.interfaces_field is null after
2402                         // completion, we can assume that t is not the
2403                         // type of a class/interface declaration.
2404                         Assert.check(t != t.tsym.type, t);
2405                         List<Type> actuals = t.allparams();
2406                         List<Type> formals = t.tsym.type.allparams();
2407                         if (t.hasErasedSupertypes()) {
2408                             t.interfaces_field = erasureRecursive(interfaces);
2409                         } else if (formals.nonEmpty()) {
2410                             t.interfaces_field = subst(interfaces, formals, actuals);
2411                         }
2412                         else {
2413                             t.interfaces_field = interfaces;
2414                         }
2415                     }
2416                 }
2417                 return t.interfaces_field;
2418             }
2419 
2420             @Override
2421             public List<Type> visitTypeVar(TypeVar t, Void ignored) {
2422                 if (t.bound.isCompound())
2423                     return interfaces(t.bound);
2424 
2425                 if (t.bound.isInterface())
2426                     return List.of(t.bound);
2427 
2428                 return List.nil();
2429             }
2430         };
2431 
2432     public List<Type> directSupertypes(Type t) {
2433         return directSupertypes.visit(t);
2434     }
2435     // where
2436         private final UnaryVisitor<List<Type>> directSupertypes = new UnaryVisitor<List<Type>>() {
2437 
2438             public List<Type> visitType(final Type type, final Void ignored) {
2439                 if (!type.isCompound()) {
2440                     final Type sup = supertype(type);
2441                     return (sup == Type.noType || sup == type || sup == null)
2442                         ? interfaces(type)
2443                         : interfaces(type).prepend(sup);
2444                 } else {
2445                     return visitIntersectionType((IntersectionClassType) type);
2446                 }
2447             }
2448 
2449             private List<Type> visitIntersectionType(final IntersectionClassType it) {
2450                 return it.getExplicitComponents();
2451             }
2452 
2453         };
2454 
2455     public boolean isDirectSuperInterface(TypeSymbol isym, TypeSymbol origin) {
2456         for (Type i2 : interfaces(origin.type)) {
2457             if (isym == i2.tsym) return true;
2458         }
2459         return false;
2460     }
2461     // </editor-fold>
2462 
2463     // <editor-fold defaultstate="collapsed" desc="isDerivedRaw">
2464     Map<Type,Boolean> isDerivedRawCache = new HashMap<Type,Boolean>();
2465 
2466     public boolean isDerivedRaw(Type t) {
2467         Boolean result = isDerivedRawCache.get(t);
2468         if (result == null) {
2469             result = isDerivedRawInternal(t);
2470             isDerivedRawCache.put(t, result);
2471         }
2472         return result;
2473     }
2474 
2475     public boolean isDerivedRawInternal(Type t) {
2476         if (t.isErroneous())
2477             return false;
2478         return
2479             t.isRaw() ||
2480             supertype(t) != Type.noType && isDerivedRaw(supertype(t)) ||
2481             isDerivedRaw(interfaces(t));
2482     }
2483 
2484     public boolean isDerivedRaw(List<Type> ts) {
2485         List<Type> l = ts;
2486         while (l.nonEmpty() && !isDerivedRaw(l.head)) l = l.tail;
2487         return l.nonEmpty();
2488     }
2489     // </editor-fold>
2490 
2491     // <editor-fold defaultstate="collapsed" desc="setBounds">
2492     /**
2493      * Set the bounds field of the given type variable to reflect a
2494      * (possibly multiple) list of bounds.
2495      * @param t                 a type variable
2496      * @param bounds            the bounds, must be nonempty
2497      * @param supertype         is objectType if all bounds are interfaces,
2498      *                          null otherwise.
2499      */
2500     public void setBounds(TypeVar t, List<Type> bounds) {
2501         setBounds(t, bounds, bounds.head.tsym.isInterface());
2502     }
2503 
2504     /**
2505      * Same as {@link #setBounds(Type.TypeVar,List,Type)}, except that
2506      * third parameter is computed directly, as follows: if all
2507      * all bounds are interface types, the computed supertype is Object,
2508      * otherwise the supertype is simply left null (in this case, the supertype
2509      * is assumed to be the head of the bound list passed as second argument).
2510      * Note that this check might cause a symbol completion. Hence, this version of
2511      * setBounds may not be called during a classfile read.
2512      */
2513     public void setBounds(TypeVar t, List<Type> bounds, boolean allInterfaces) {
2514         t.bound = bounds.tail.isEmpty() ?
2515                 bounds.head :
2516                 makeCompoundType(bounds, allInterfaces);
2517         t.rank_field = -1;
2518     }
2519     // </editor-fold>
2520 
2521     // <editor-fold defaultstate="collapsed" desc="getBounds">
2522     /**
2523      * Return list of bounds of the given type variable.
2524      */
2525     public List<Type> getBounds(TypeVar t) {
2526         if (t.bound.hasTag(NONE))
2527             return List.nil();
2528         else if (t.bound.isErroneous() || !t.bound.isCompound())
2529             return List.of(t.bound);
2530         else if ((erasure(t).tsym.flags() & INTERFACE) == 0)
2531             return interfaces(t).prepend(supertype(t));
2532         else
2533             // No superclass was given in bounds.
2534             // In this case, supertype is Object, erasure is first interface.
2535             return interfaces(t);
2536     }
2537     // </editor-fold>
2538 
2539     // <editor-fold defaultstate="collapsed" desc="classBound">
2540     /**
2541      * If the given type is a (possibly selected) type variable,
2542      * return the bounding class of this type, otherwise return the
2543      * type itself.
2544      */
2545     public Type classBound(Type t) {
2546         return classBound.visit(t);
2547     }
2548     // where
2549         private UnaryVisitor<Type> classBound = new UnaryVisitor<Type>() {
2550 
2551             public Type visitType(Type t, Void ignored) {
2552                 return t;
2553             }
2554 
2555             @Override
2556             public Type visitClassType(ClassType t, Void ignored) {
2557                 Type outer1 = classBound(t.getEnclosingType());
2558                 if (outer1 != t.getEnclosingType())
2559                     return new ClassType(outer1, t.getTypeArguments(), t.tsym);
2560                 else
2561                     return t;
2562             }
2563 
2564             @Override
2565             public Type visitTypeVar(TypeVar t, Void ignored) {
2566                 return classBound(supertype(t));
2567             }
2568 
2569             @Override
2570             public Type visitErrorType(ErrorType t, Void ignored) {
2571                 return t;
2572             }
2573         };
2574     // </editor-fold>
2575 
2576     // <editor-fold defaultstate="collapsed" desc="sub signature / override equivalence">
2577     /**
2578      * Returns true iff the first signature is a <em>sub
2579      * signature</em> of the other.  This is <b>not</b> an equivalence
2580      * relation.
2581      *
2582      * @jls section 8.4.2.
2583      * @see #overrideEquivalent(Type t, Type s)
2584      * @param t first signature (possibly raw).
2585      * @param s second signature (could be subjected to erasure).
2586      * @return true if t is a sub signature of s.
2587      */
2588     public boolean isSubSignature(Type t, Type s) {
2589         return isSubSignature(t, s, true);
2590     }
2591 
2592     public boolean isSubSignature(Type t, Type s, boolean strict) {
2593         return hasSameArgs(t, s, strict) || hasSameArgs(t, erasure(s), strict);
2594     }
2595 
2596     /**
2597      * Returns true iff these signatures are related by <em>override
2598      * equivalence</em>.  This is the natural extension of
2599      * isSubSignature to an equivalence relation.
2600      *
2601      * @jls section 8.4.2.
2602      * @see #isSubSignature(Type t, Type s)
2603      * @param t a signature (possible raw, could be subjected to
2604      * erasure).
2605      * @param s a signature (possible raw, could be subjected to
2606      * erasure).
2607      * @return true if either argument is a sub signature of the other.
2608      */
2609     public boolean overrideEquivalent(Type t, Type s) {
2610         return hasSameArgs(t, s) ||
2611             hasSameArgs(t, erasure(s)) || hasSameArgs(erasure(t), s);
2612     }
2613 
2614     public boolean overridesObjectMethod(TypeSymbol origin, Symbol msym) {
2615         for (Scope.Entry e = syms.objectType.tsym.members().lookup(msym.name) ; e.scope != null ; e = e.next()) {
2616             if (msym.overrides(e.sym, origin, Types.this, true)) {
2617                 return true;
2618             }
2619         }
2620         return false;
2621     }
2622 
2623     // <editor-fold defaultstate="collapsed" desc="Determining method implementation in given site">
2624     class ImplementationCache {
2625 
2626         private WeakHashMap<MethodSymbol, SoftReference<Map<TypeSymbol, Entry>>> _map =
2627                 new WeakHashMap<MethodSymbol, SoftReference<Map<TypeSymbol, Entry>>>();
2628 
2629         class Entry {
2630             final MethodSymbol cachedImpl;
2631             final Filter<Symbol> implFilter;
2632             final boolean checkResult;
2633             final int prevMark;
2634 
2635             public Entry(MethodSymbol cachedImpl,
2636                     Filter<Symbol> scopeFilter,
2637                     boolean checkResult,
2638                     int prevMark) {
2639                 this.cachedImpl = cachedImpl;
2640                 this.implFilter = scopeFilter;
2641                 this.checkResult = checkResult;
2642                 this.prevMark = prevMark;
2643             }
2644 
2645             boolean matches(Filter<Symbol> scopeFilter, boolean checkResult, int mark) {
2646                 return this.implFilter == scopeFilter &&
2647                         this.checkResult == checkResult &&
2648                         this.prevMark == mark;
2649             }
2650         }
2651 
2652         MethodSymbol get(MethodSymbol ms, TypeSymbol origin, boolean checkResult, Filter<Symbol> implFilter) {
2653             SoftReference<Map<TypeSymbol, Entry>> ref_cache = _map.get(ms);
2654             Map<TypeSymbol, Entry> cache = ref_cache != null ? ref_cache.get() : null;
2655             if (cache == null) {
2656                 cache = new HashMap<TypeSymbol, Entry>();
2657                 _map.put(ms, new SoftReference<Map<TypeSymbol, Entry>>(cache));
2658             }
2659             Entry e = cache.get(origin);
2660             CompoundScope members = membersClosure(origin.type, true);
2661             if (e == null ||
2662                     !e.matches(implFilter, checkResult, members.getMark())) {
2663                 MethodSymbol impl = implementationInternal(ms, origin, checkResult, implFilter);
2664                 cache.put(origin, new Entry(impl, implFilter, checkResult, members.getMark()));
2665                 return impl;
2666             }
2667             else {
2668                 return e.cachedImpl;
2669             }
2670         }
2671 
2672         private MethodSymbol implementationInternal(MethodSymbol ms, TypeSymbol origin, boolean checkResult, Filter<Symbol> implFilter) {
2673             for (Type t = origin.type; t.hasTag(CLASS) || t.hasTag(TYPEVAR); t = supertype(t)) {
2674                 while (t.hasTag(TYPEVAR))
2675                     t = t.getUpperBound();
2676                 TypeSymbol c = t.tsym;
2677                 for (Scope.Entry e = c.members().lookup(ms.name, implFilter);
2678                      e.scope != null;
2679                      e = e.next(implFilter)) {
2680                     if (e.sym != null &&
2681                              e.sym.overrides(ms, origin, Types.this, checkResult))
2682                         return (MethodSymbol)e.sym;
2683                 }
2684             }
2685             return null;
2686         }
2687     }
2688 
2689     private ImplementationCache implCache = new ImplementationCache();
2690 
2691     public MethodSymbol implementation(MethodSymbol ms, TypeSymbol origin, boolean checkResult, Filter<Symbol> implFilter) {
2692         return implCache.get(ms, origin, checkResult, implFilter);
2693     }
2694     // </editor-fold>
2695 
2696     // <editor-fold defaultstate="collapsed" desc="compute transitive closure of all members in given site">
2697     class MembersClosureCache extends SimpleVisitor<Scope.CompoundScope, Void> {
2698 
2699         private Map<TypeSymbol, CompoundScope> _map = new HashMap<>();
2700 
2701         Set<TypeSymbol> seenTypes = new HashSet<>();
2702 
2703         class MembersScope extends CompoundScope {
2704 
2705             CompoundScope scope;
2706 
2707             public MembersScope(CompoundScope scope) {
2708                 super(scope.owner);
2709                 this.scope = scope;
2710             }
2711 
2712             Filter<Symbol> combine(final Filter<Symbol> sf) {
2713                 return new Filter<Symbol>() {
2714                     @Override
2715                     public boolean accepts(Symbol s) {
2716                         return !s.owner.isInterface() && (sf == null || sf.accepts(s));
2717                     }
2718                 };
2719             }
2720 
2721             @Override
2722             public Iterable<Symbol> getElements(Filter<Symbol> sf) {
2723                 return scope.getElements(combine(sf));
2724             }
2725 
2726             @Override
2727             public Iterable<Symbol> getElementsByName(Name name, Filter<Symbol> sf) {
2728                 return scope.getElementsByName(name, combine(sf));
2729             }
2730 
2731             @Override
2732             public int getMark() {
2733                 return scope.getMark();
2734             }
2735         }
2736 
2737         CompoundScope nilScope;
2738 
2739         /** members closure visitor methods **/
2740 
2741         public CompoundScope visitType(Type t, Void _unused) {
2742             if (nilScope == null) {
2743                 nilScope = new CompoundScope(syms.noSymbol);
2744             }
2745             return nilScope;
2746         }
2747 
2748         @Override
2749         public CompoundScope visitClassType(ClassType t, Void _unused) {
2750             if (!seenTypes.add(t.tsym)) {
2751                 //this is possible when an interface is implemented in multiple
2752                 //superclasses, or when a class hierarchy is circular - in such
2753                 //cases we don't need to recurse (empty scope is returned)
2754                 return new CompoundScope(t.tsym);
2755             }
2756             try {
2757                 seenTypes.add(t.tsym);
2758                 ClassSymbol csym = (ClassSymbol)t.tsym;
2759                 CompoundScope membersClosure = _map.get(csym);
2760                 if (membersClosure == null) {
2761                     membersClosure = new CompoundScope(csym);
2762                     for (Type i : interfaces(t)) {
2763                         membersClosure.addSubScope(visit(i, null));
2764                     }
2765                     membersClosure.addSubScope(visit(supertype(t), null));
2766                     membersClosure.addSubScope(csym.members());
2767                     _map.put(csym, membersClosure);
2768                 }
2769                 return membersClosure;
2770             }
2771             finally {
2772                 seenTypes.remove(t.tsym);
2773             }
2774         }
2775 
2776         @Override
2777         public CompoundScope visitTypeVar(TypeVar t, Void _unused) {
2778             return visit(t.getUpperBound(), null);
2779         }
2780     }
2781 
2782     private MembersClosureCache membersCache = new MembersClosureCache();
2783 
2784     public CompoundScope membersClosure(Type site, boolean skipInterface) {
2785         CompoundScope cs = membersCache.visit(site, null);
2786         if (cs == null)
2787             Assert.error("type " + site);
2788         return skipInterface ? membersCache.new MembersScope(cs) : cs;
2789     }
2790     // </editor-fold>
2791 
2792 
2793     /** Return first abstract member of class `sym'.
2794      */
2795     public MethodSymbol firstUnimplementedAbstract(ClassSymbol sym) {
2796         try {
2797             return firstUnimplementedAbstractImpl(sym, sym);
2798         } catch (CompletionFailure ex) {
2799             chk.completionError(enter.getEnv(sym).tree.pos(), ex);
2800             return null;
2801         }
2802     }
2803         //where:
2804         private MethodSymbol firstUnimplementedAbstractImpl(ClassSymbol impl, ClassSymbol c) {
2805             MethodSymbol undef = null;
2806             // Do not bother to search in classes that are not abstract,
2807             // since they cannot have abstract members.
2808             if (c == impl || (c.flags() & (ABSTRACT | INTERFACE)) != 0) {
2809                 Scope s = c.members();
2810                 for (Scope.Entry e = s.elems;
2811                      undef == null && e != null;
2812                      e = e.sibling) {
2813                     if (e.sym.kind == MTH &&
2814                         (e.sym.flags() & (ABSTRACT|IPROXY|DEFAULT)) == ABSTRACT) {
2815                         MethodSymbol absmeth = (MethodSymbol)e.sym;
2816                         MethodSymbol implmeth = absmeth.implementation(impl, this, true);
2817                         if (implmeth == null || implmeth == absmeth) {
2818                             //look for default implementations
2819                             if (allowDefaultMethods) {
2820                                 MethodSymbol prov = interfaceCandidates(impl.type, absmeth).head;
2821                                 if (prov != null && prov.overrides(absmeth, impl, this, true)) {
2822                                     implmeth = prov;
2823                                 }
2824                             }
2825                         }
2826                         if (implmeth == null || implmeth == absmeth) {
2827                             undef = absmeth;
2828                         }
2829                     }
2830                 }
2831                 if (undef == null) {
2832                     Type st = supertype(c.type);
2833                     if (st.hasTag(CLASS))
2834                         undef = firstUnimplementedAbstractImpl(impl, (ClassSymbol)st.tsym);
2835                 }
2836                 for (List<Type> l = interfaces(c.type);
2837                      undef == null && l.nonEmpty();
2838                      l = l.tail) {
2839                     undef = firstUnimplementedAbstractImpl(impl, (ClassSymbol)l.head.tsym);
2840                 }
2841             }
2842             return undef;
2843         }
2844 
2845 
2846     //where
2847     public List<MethodSymbol> interfaceCandidates(Type site, MethodSymbol ms) {
2848         Filter<Symbol> filter = new MethodFilter(ms, site);
2849         List<MethodSymbol> candidates = List.nil();
2850             for (Symbol s : membersClosure(site, false).getElements(filter)) {
2851                 if (!site.tsym.isInterface() && !s.owner.isInterface()) {
2852                     return List.of((MethodSymbol)s);
2853                 } else if (!candidates.contains(s)) {
2854                     candidates = candidates.prepend((MethodSymbol)s);
2855                 }
2856             }
2857             return prune(candidates);
2858         }
2859 
2860     public List<MethodSymbol> prune(List<MethodSymbol> methods) {
2861         ListBuffer<MethodSymbol> methodsMin = new ListBuffer<>();
2862         for (MethodSymbol m1 : methods) {
2863             boolean isMin_m1 = true;
2864             for (MethodSymbol m2 : methods) {
2865                 if (m1 == m2) continue;
2866                 if (m2.owner != m1.owner &&
2867                         asSuper(m2.owner.type, m1.owner) != null) {
2868                     isMin_m1 = false;
2869                     break;
2870                 }
2871             }
2872             if (isMin_m1)
2873                 methodsMin.append(m1);
2874         }
2875         return methodsMin.toList();
2876     }
2877     // where
2878             private class MethodFilter implements Filter<Symbol> {
2879 
2880                 Symbol msym;
2881                 Type site;
2882 
2883                 MethodFilter(Symbol msym, Type site) {
2884                     this.msym = msym;
2885                     this.site = site;
2886                 }
2887 
2888                 public boolean accepts(Symbol s) {
2889                     return s.kind == Kinds.MTH &&
2890                             s.name == msym.name &&
2891                             (s.flags() & SYNTHETIC) == 0 &&
2892                             s.isInheritedIn(site.tsym, Types.this) &&
2893                             overrideEquivalent(memberType(site, s), memberType(site, msym));
2894                 }
2895             };
2896     // </editor-fold>
2897 
2898     /**
2899      * Does t have the same arguments as s?  It is assumed that both
2900      * types are (possibly polymorphic) method types.  Monomorphic
2901      * method types "have the same arguments", if their argument lists
2902      * are equal.  Polymorphic method types "have the same arguments",
2903      * if they have the same arguments after renaming all type
2904      * variables of one to corresponding type variables in the other,
2905      * where correspondence is by position in the type parameter list.
2906      */
2907     public boolean hasSameArgs(Type t, Type s) {
2908         return hasSameArgs(t, s, true);
2909     }
2910 
2911     public boolean hasSameArgs(Type t, Type s, boolean strict) {
2912         return hasSameArgs(t, s, strict ? hasSameArgs_strict : hasSameArgs_nonstrict);
2913     }
2914 
2915     private boolean hasSameArgs(Type t, Type s, TypeRelation hasSameArgs) {
2916         return hasSameArgs.visit(t, s);
2917     }
2918     // where
2919         private class HasSameArgs extends TypeRelation {
2920 
2921             boolean strict;
2922 
2923             public HasSameArgs(boolean strict) {
2924                 this.strict = strict;
2925             }
2926 
2927             public Boolean visitType(Type t, Type s) {
2928                 throw new AssertionError();
2929             }
2930 
2931             @Override
2932             public Boolean visitMethodType(MethodType t, Type s) {
2933                 return s.hasTag(METHOD)
2934                     && containsTypeEquivalent(t.argtypes, s.getParameterTypes());
2935             }
2936 
2937             @Override
2938             public Boolean visitForAll(ForAll t, Type s) {
2939                 if (!s.hasTag(FORALL))
2940                     return strict ? false : visitMethodType(t.asMethodType(), s);
2941 
2942                 ForAll forAll = (ForAll)s;
2943                 return hasSameBounds(t, forAll)
2944                     && visit(t.qtype, subst(forAll.qtype, forAll.tvars, t.tvars));
2945             }
2946 
2947             @Override
2948             public Boolean visitErrorType(ErrorType t, Type s) {
2949                 return false;
2950             }
2951         };
2952 
2953         TypeRelation hasSameArgs_strict = new HasSameArgs(true);
2954         TypeRelation hasSameArgs_nonstrict = new HasSameArgs(false);
2955 
2956     // </editor-fold>
2957 
2958     // <editor-fold defaultstate="collapsed" desc="subst">
2959     public List<Type> subst(List<Type> ts,
2960                             List<Type> from,
2961                             List<Type> to) {
2962         return new Subst(from, to).subst(ts);
2963     }
2964 
2965     /**
2966      * Substitute all occurrences of a type in `from' with the
2967      * corresponding type in `to' in 't'. Match lists `from' and `to'
2968      * from the right: If lists have different length, discard leading
2969      * elements of the longer list.
2970      */
2971     public Type subst(Type t, List<Type> from, List<Type> to) {
2972         return new Subst(from, to).subst(t);
2973     }
2974 
2975     private class Subst extends UnaryVisitor<Type> {
2976         List<Type> from;
2977         List<Type> to;
2978 
2979         public Subst(List<Type> from, List<Type> to) {
2980             int fromLength = from.length();
2981             int toLength = to.length();
2982             while (fromLength > toLength) {
2983                 fromLength--;
2984                 from = from.tail;
2985             }
2986             while (fromLength < toLength) {
2987                 toLength--;
2988                 to = to.tail;
2989             }
2990             this.from = from;
2991             this.to = to;
2992         }
2993 
2994         Type subst(Type t) {
2995             if (from.tail == null)
2996                 return t;
2997             else
2998                 return visit(t);
2999             }
3000 
3001         List<Type> subst(List<Type> ts) {
3002             if (from.tail == null)
3003                 return ts;
3004             boolean wild = false;
3005             if (ts.nonEmpty() && from.nonEmpty()) {
3006                 Type head1 = subst(ts.head);
3007                 List<Type> tail1 = subst(ts.tail);
3008                 if (head1 != ts.head || tail1 != ts.tail)
3009                     return tail1.prepend(head1);
3010             }
3011             return ts;
3012         }
3013 
3014         public Type visitType(Type t, Void ignored) {
3015             return t;
3016         }
3017 
3018         @Override
3019         public Type visitMethodType(MethodType t, Void ignored) {
3020             List<Type> argtypes = subst(t.argtypes);
3021             Type restype = subst(t.restype);
3022             List<Type> thrown = subst(t.thrown);
3023             if (argtypes == t.argtypes &&
3024                 restype == t.restype &&
3025                 thrown == t.thrown)
3026                 return t;
3027             else
3028                 return new MethodType(argtypes, restype, thrown, t.tsym);
3029         }
3030 
3031         @Override
3032         public Type visitTypeVar(TypeVar t, Void ignored) {
3033             for (List<Type> from = this.from, to = this.to;
3034                  from.nonEmpty();
3035                  from = from.tail, to = to.tail) {
3036                 if (t == from.head) {
3037                     return to.head.withTypeVar(t);
3038                 }
3039             }
3040             return t;
3041         }
3042 
3043         @Override
3044         public Type visitUndetVar(UndetVar t, Void ignored) {
3045             //do nothing - we should not replace inside undet variables
3046             return t;
3047         }
3048 
3049         @Override
3050         public Type visitClassType(ClassType t, Void ignored) {
3051             if (!t.isCompound()) {
3052                 List<Type> typarams = t.getTypeArguments();
3053                 List<Type> typarams1 = subst(typarams);
3054                 Type outer = t.getEnclosingType();
3055                 Type outer1 = subst(outer);
3056                 if (typarams1 == typarams && outer1 == outer)
3057                     return t;
3058                 else
3059                     return new ClassType(outer1, typarams1, t.tsym);
3060             } else {
3061                 Type st = subst(supertype(t));
3062                 List<Type> is = subst(interfaces(t));
3063                 if (st == supertype(t) && is == interfaces(t))
3064                     return t;
3065                 else
3066                     return makeCompoundType(is.prepend(st));
3067             }
3068         }
3069 
3070         @Override
3071         public Type visitWildcardType(WildcardType t, Void ignored) {
3072             Type bound = t.type;
3073             if (t.kind != BoundKind.UNBOUND)
3074                 bound = subst(bound);
3075             if (bound == t.type) {
3076                 return t;
3077             } else {
3078                 if (t.isExtendsBound() && bound.isExtendsBound())
3079                     bound = wildUpperBound(bound);
3080                 return new WildcardType(bound, t.kind, syms.boundClass, t.bound);
3081             }
3082         }
3083 
3084         @Override
3085         public Type visitArrayType(ArrayType t, Void ignored) {
3086             Type elemtype = subst(t.elemtype);
3087             if (elemtype == t.elemtype)
3088                 return t;
3089             else
3090                 return new ArrayType(elemtype, t.tsym);
3091         }
3092 
3093         @Override
3094         public Type visitForAll(ForAll t, Void ignored) {
3095             if (Type.containsAny(to, t.tvars)) {
3096                 //perform alpha-renaming of free-variables in 't'
3097                 //if 'to' types contain variables that are free in 't'
3098                 List<Type> freevars = newInstances(t.tvars);
3099                 t = new ForAll(freevars,
3100                         Types.this.subst(t.qtype, t.tvars, freevars));
3101             }
3102             List<Type> tvars1 = substBounds(t.tvars, from, to);
3103             Type qtype1 = subst(t.qtype);
3104             if (tvars1 == t.tvars && qtype1 == t.qtype) {
3105                 return t;
3106             } else if (tvars1 == t.tvars) {
3107                 return new ForAll(tvars1, qtype1);
3108             } else {
3109                 return new ForAll(tvars1, Types.this.subst(qtype1, t.tvars, tvars1));
3110             }
3111         }
3112 
3113         @Override
3114         public Type visitErrorType(ErrorType t, Void ignored) {
3115             return t;
3116         }
3117     }
3118 
3119     public List<Type> substBounds(List<Type> tvars,
3120                                   List<Type> from,
3121                                   List<Type> to) {
3122         if (tvars.isEmpty())
3123             return tvars;
3124         ListBuffer<Type> newBoundsBuf = new ListBuffer<>();
3125         boolean changed = false;
3126         // calculate new bounds
3127         for (Type t : tvars) {
3128             TypeVar tv = (TypeVar) t;
3129             Type bound = subst(tv.bound, from, to);
3130             if (bound != tv.bound)
3131                 changed = true;
3132             newBoundsBuf.append(bound);
3133         }
3134         if (!changed)
3135             return tvars;
3136         ListBuffer<Type> newTvars = new ListBuffer<>();
3137         // create new type variables without bounds
3138         for (Type t : tvars) {
3139             newTvars.append(new TypeVar(t.tsym, null, syms.botType));
3140         }
3141         // the new bounds should use the new type variables in place
3142         // of the old
3143         List<Type> newBounds = newBoundsBuf.toList();
3144         from = tvars;
3145         to = newTvars.toList();
3146         for (; !newBounds.isEmpty(); newBounds = newBounds.tail) {
3147             newBounds.head = subst(newBounds.head, from, to);
3148         }
3149         newBounds = newBoundsBuf.toList();
3150         // set the bounds of new type variables to the new bounds
3151         for (Type t : newTvars.toList()) {
3152             TypeVar tv = (TypeVar) t;
3153             tv.bound = newBounds.head;
3154             newBounds = newBounds.tail;
3155         }
3156         return newTvars.toList();
3157     }
3158 
3159     public TypeVar substBound(TypeVar t, List<Type> from, List<Type> to) {
3160         Type bound1 = subst(t.bound, from, to);
3161         if (bound1 == t.bound)
3162             return t;
3163         else {
3164             // create new type variable without bounds
3165             TypeVar tv = new TypeVar(t.tsym, null, syms.botType);
3166             // the new bound should use the new type variable in place
3167             // of the old
3168             tv.bound = subst(bound1, List.<Type>of(t), List.<Type>of(tv));
3169             return tv;
3170         }
3171     }
3172     // </editor-fold>
3173 
3174     // <editor-fold defaultstate="collapsed" desc="hasSameBounds">
3175     /**
3176      * Does t have the same bounds for quantified variables as s?
3177      */
3178     public boolean hasSameBounds(ForAll t, ForAll s) {
3179         List<Type> l1 = t.tvars;
3180         List<Type> l2 = s.tvars;
3181         while (l1.nonEmpty() && l2.nonEmpty() &&
3182                isSameType(l1.head.getUpperBound(),
3183                           subst(l2.head.getUpperBound(),
3184                                 s.tvars,
3185                                 t.tvars))) {
3186             l1 = l1.tail;
3187             l2 = l2.tail;
3188         }
3189         return l1.isEmpty() && l2.isEmpty();
3190     }
3191     // </editor-fold>
3192 
3193     // <editor-fold defaultstate="collapsed" desc="newInstances">
3194     /** Create new vector of type variables from list of variables
3195      *  changing all recursive bounds from old to new list.
3196      */
3197     public List<Type> newInstances(List<Type> tvars) {
3198         List<Type> tvars1 = Type.map(tvars, newInstanceFun);
3199         for (List<Type> l = tvars1; l.nonEmpty(); l = l.tail) {
3200             TypeVar tv = (TypeVar) l.head;
3201             tv.bound = subst(tv.bound, tvars, tvars1);
3202         }
3203         return tvars1;
3204     }
3205     private static final Mapping newInstanceFun = new Mapping("newInstanceFun") {
3206             public Type apply(Type t) { return new TypeVar(t.tsym, t.getUpperBound(), t.getLowerBound()); }
3207         };
3208     // </editor-fold>
3209 
3210     public Type createMethodTypeWithParameters(Type original, List<Type> newParams) {
3211         return original.accept(methodWithParameters, newParams);
3212     }
3213     // where
3214         private final MapVisitor<List<Type>> methodWithParameters = new MapVisitor<List<Type>>() {
3215             public Type visitType(Type t, List<Type> newParams) {
3216                 throw new IllegalArgumentException("Not a method type: " + t);
3217             }
3218             public Type visitMethodType(MethodType t, List<Type> newParams) {
3219                 return new MethodType(newParams, t.restype, t.thrown, t.tsym);
3220             }
3221             public Type visitForAll(ForAll t, List<Type> newParams) {
3222                 return new ForAll(t.tvars, t.qtype.accept(this, newParams));
3223             }
3224         };
3225 
3226     public Type createMethodTypeWithThrown(Type original, List<Type> newThrown) {
3227         return original.accept(methodWithThrown, newThrown);
3228     }
3229     // where
3230         private final MapVisitor<List<Type>> methodWithThrown = new MapVisitor<List<Type>>() {
3231             public Type visitType(Type t, List<Type> newThrown) {
3232                 throw new IllegalArgumentException("Not a method type: " + t);
3233             }
3234             public Type visitMethodType(MethodType t, List<Type> newThrown) {
3235                 return new MethodType(t.argtypes, t.restype, newThrown, t.tsym);
3236             }
3237             public Type visitForAll(ForAll t, List<Type> newThrown) {
3238                 return new ForAll(t.tvars, t.qtype.accept(this, newThrown));
3239             }
3240         };
3241 
3242     public Type createMethodTypeWithReturn(Type original, Type newReturn) {
3243         return original.accept(methodWithReturn, newReturn);
3244     }
3245     // where
3246         private final MapVisitor<Type> methodWithReturn = new MapVisitor<Type>() {
3247             public Type visitType(Type t, Type newReturn) {
3248                 throw new IllegalArgumentException("Not a method type: " + t);
3249             }
3250             public Type visitMethodType(MethodType t, Type newReturn) {
3251                 return new MethodType(t.argtypes, newReturn, t.thrown, t.tsym);
3252             }
3253             public Type visitForAll(ForAll t, Type newReturn) {
3254                 return new ForAll(t.tvars, t.qtype.accept(this, newReturn));
3255             }
3256         };
3257 
3258     // <editor-fold defaultstate="collapsed" desc="createErrorType">
3259     public Type createErrorType(Type originalType) {
3260         return new ErrorType(originalType, syms.errSymbol);
3261     }
3262 
3263     public Type createErrorType(ClassSymbol c, Type originalType) {
3264         return new ErrorType(c, originalType);
3265     }
3266 
3267     public Type createErrorType(Name name, TypeSymbol container, Type originalType) {
3268         return new ErrorType(name, container, originalType);
3269     }
3270     // </editor-fold>
3271 
3272     // <editor-fold defaultstate="collapsed" desc="rank">
3273     /**
3274      * The rank of a class is the length of the longest path between
3275      * the class and java.lang.Object in the class inheritance
3276      * graph. Undefined for all but reference types.
3277      */
3278     public int rank(Type t) {
3279         t = t.unannotatedType();
3280         switch(t.getTag()) {
3281         case CLASS: {
3282             ClassType cls = (ClassType)t;
3283             if (cls.rank_field < 0) {
3284                 Name fullname = cls.tsym.getQualifiedName();
3285                 if (fullname == names.java_lang_Object)
3286                     cls.rank_field = 0;
3287                 else {
3288                     int r = rank(supertype(cls));
3289                     for (List<Type> l = interfaces(cls);
3290                          l.nonEmpty();
3291                          l = l.tail) {
3292                         if (rank(l.head) > r)
3293                             r = rank(l.head);
3294                     }
3295                     cls.rank_field = r + 1;
3296                 }
3297             }
3298             return cls.rank_field;
3299         }
3300         case TYPEVAR: {
3301             TypeVar tvar = (TypeVar)t;
3302             if (tvar.rank_field < 0) {
3303                 int r = rank(supertype(tvar));
3304                 for (List<Type> l = interfaces(tvar);
3305                      l.nonEmpty();
3306                      l = l.tail) {
3307                     if (rank(l.head) > r) r = rank(l.head);
3308                 }
3309                 tvar.rank_field = r + 1;
3310             }
3311             return tvar.rank_field;
3312         }
3313         case ERROR:
3314         case NONE:
3315             return 0;
3316         default:
3317             throw new AssertionError();
3318         }
3319     }
3320     // </editor-fold>
3321 
3322     /**
3323      * Helper method for generating a string representation of a given type
3324      * accordingly to a given locale
3325      */
3326     public String toString(Type t, Locale locale) {
3327         return Printer.createStandardPrinter(messages).visit(t, locale);
3328     }
3329 
3330     /**
3331      * Helper method for generating a string representation of a given type
3332      * accordingly to a given locale
3333      */
3334     public String toString(Symbol t, Locale locale) {
3335         return Printer.createStandardPrinter(messages).visit(t, locale);
3336     }
3337 
3338     // <editor-fold defaultstate="collapsed" desc="toString">
3339     /**
3340      * This toString is slightly more descriptive than the one on Type.
3341      *
3342      * @deprecated Types.toString(Type t, Locale l) provides better support
3343      * for localization
3344      */
3345     @Deprecated
3346     public String toString(Type t) {
3347         if (t.hasTag(FORALL)) {
3348             ForAll forAll = (ForAll)t;
3349             return typaramsString(forAll.tvars) + forAll.qtype;
3350         }
3351         return "" + t;
3352     }
3353     // where
3354         private String typaramsString(List<Type> tvars) {
3355             StringBuilder s = new StringBuilder();
3356             s.append('<');
3357             boolean first = true;
3358             for (Type t : tvars) {
3359                 if (!first) s.append(", ");
3360                 first = false;
3361                 appendTyparamString(((TypeVar)t.unannotatedType()), s);
3362             }
3363             s.append('>');
3364             return s.toString();
3365         }
3366         private void appendTyparamString(TypeVar t, StringBuilder buf) {
3367             buf.append(t);
3368             if (t.bound == null ||
3369                 t.bound.tsym.getQualifiedName() == names.java_lang_Object)
3370                 return;
3371             buf.append(" extends "); // Java syntax; no need for i18n
3372             Type bound = t.bound;
3373             if (!bound.isCompound()) {
3374                 buf.append(bound);
3375             } else if ((erasure(t).tsym.flags() & INTERFACE) == 0) {
3376                 buf.append(supertype(t));
3377                 for (Type intf : interfaces(t)) {
3378                     buf.append('&');
3379                     buf.append(intf);
3380                 }
3381             } else {
3382                 // No superclass was given in bounds.
3383                 // In this case, supertype is Object, erasure is first interface.
3384                 boolean first = true;
3385                 for (Type intf : interfaces(t)) {
3386                     if (!first) buf.append('&');
3387                     first = false;
3388                     buf.append(intf);
3389                 }
3390             }
3391         }
3392     // </editor-fold>
3393 
3394     // <editor-fold defaultstate="collapsed" desc="Determining least upper bounds of types">
3395     /**
3396      * A cache for closures.
3397      *
3398      * <p>A closure is a list of all the supertypes and interfaces of
3399      * a class or interface type, ordered by ClassSymbol.precedes
3400      * (that is, subclasses come first, arbitrary but fixed
3401      * otherwise).
3402      */
3403     private Map<Type,List<Type>> closureCache = new HashMap<Type,List<Type>>();
3404 
3405     /**
3406      * Returns the closure of a class or interface type.
3407      */
3408     public List<Type> closure(Type t) {
3409         List<Type> cl = closureCache.get(t);
3410         if (cl == null) {
3411             Type st = supertype(t);
3412             if (!t.isCompound()) {
3413                 if (st.hasTag(CLASS)) {
3414                     cl = insert(closure(st), t);
3415                 } else if (st.hasTag(TYPEVAR)) {
3416                     cl = closure(st).prepend(t);
3417                 } else {
3418                     cl = List.of(t);
3419                 }
3420             } else {
3421                 cl = closure(supertype(t));
3422             }
3423             for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail)
3424                 cl = union(cl, closure(l.head));
3425             closureCache.put(t, cl);
3426         }
3427         return cl;
3428     }
3429 
3430     /**
3431      * Insert a type in a closure
3432      */
3433     public List<Type> insert(List<Type> cl, Type t) {
3434         if (cl.isEmpty()) {
3435             return cl.prepend(t);
3436         } else if (t.tsym == cl.head.tsym) {
3437             return cl;
3438         } else if (t.tsym.precedes(cl.head.tsym, this)) {
3439             return cl.prepend(t);
3440         } else {
3441             // t comes after head, or the two are unrelated
3442             return insert(cl.tail, t).prepend(cl.head);
3443         }
3444     }
3445 
3446     /**
3447      * Form the union of two closures
3448      */
3449     public List<Type> union(List<Type> cl1, List<Type> cl2) {
3450         if (cl1.isEmpty()) {
3451             return cl2;
3452         } else if (cl2.isEmpty()) {
3453             return cl1;
3454         } else if (cl1.head.tsym == cl2.head.tsym) {
3455             return union(cl1.tail, cl2.tail).prepend(cl1.head);
3456         } else if (cl1.head.tsym.precedes(cl2.head.tsym, this)) {
3457             return union(cl1.tail, cl2).prepend(cl1.head);
3458         } else if (cl2.head.tsym.precedes(cl1.head.tsym, this)) {
3459             return union(cl1, cl2.tail).prepend(cl2.head);
3460         } else {
3461             // unrelated types
3462             return union(cl1.tail, cl2).prepend(cl1.head);
3463         }
3464     }
3465 
3466     /**
3467      * Intersect two closures
3468      */
3469     public List<Type> intersect(List<Type> cl1, List<Type> cl2) {
3470         if (cl1 == cl2)
3471             return cl1;
3472         if (cl1.isEmpty() || cl2.isEmpty())
3473             return List.nil();
3474         if (cl1.head.tsym.precedes(cl2.head.tsym, this))
3475             return intersect(cl1.tail, cl2);
3476         if (cl2.head.tsym.precedes(cl1.head.tsym, this))
3477             return intersect(cl1, cl2.tail);
3478         if (isSameType(cl1.head, cl2.head))
3479             return intersect(cl1.tail, cl2.tail).prepend(cl1.head);
3480         if (cl1.head.tsym == cl2.head.tsym &&
3481             cl1.head.hasTag(CLASS) && cl2.head.hasTag(CLASS)) {
3482             if (cl1.head.isParameterized() && cl2.head.isParameterized()) {
3483                 Type merge = merge(cl1.head,cl2.head);
3484                 return intersect(cl1.tail, cl2.tail).prepend(merge);
3485             }
3486             if (cl1.head.isRaw() || cl2.head.isRaw())
3487                 return intersect(cl1.tail, cl2.tail).prepend(erasure(cl1.head));
3488         }
3489         return intersect(cl1.tail, cl2.tail);
3490     }
3491     // where
3492         class TypePair {
3493             final Type t1;
3494             final Type t2;
3495             boolean strict;
3496 
3497             TypePair(Type t1, Type t2) {
3498                 this(t1, t2, false);
3499             }
3500 
3501             TypePair(Type t1, Type t2, boolean strict) {
3502                 this.t1 = t1;
3503                 this.t2 = t2;
3504                 this.strict = strict;
3505             }
3506             @Override
3507             public int hashCode() {
3508                 return 127 * Types.this.hashCode(t1) + Types.this.hashCode(t2);
3509             }
3510             @Override
3511             public boolean equals(Object obj) {
3512                 if (!(obj instanceof TypePair))
3513                     return false;
3514                 TypePair typePair = (TypePair)obj;
3515                 return isSameType(t1, typePair.t1, strict)
3516                     && isSameType(t2, typePair.t2, strict);
3517             }
3518         }
3519         Set<TypePair> mergeCache = new HashSet<TypePair>();
3520         private Type merge(Type c1, Type c2) {
3521             ClassType class1 = (ClassType) c1;
3522             List<Type> act1 = class1.getTypeArguments();
3523             ClassType class2 = (ClassType) c2;
3524             List<Type> act2 = class2.getTypeArguments();
3525             ListBuffer<Type> merged = new ListBuffer<Type>();
3526             List<Type> typarams = class1.tsym.type.getTypeArguments();
3527 
3528             while (act1.nonEmpty() && act2.nonEmpty() && typarams.nonEmpty()) {
3529                 if (containsType(act1.head, act2.head)) {
3530                     merged.append(act1.head);
3531                 } else if (containsType(act2.head, act1.head)) {
3532                     merged.append(act2.head);
3533                 } else {
3534                     TypePair pair = new TypePair(c1, c2);
3535                     Type m;
3536                     if (mergeCache.add(pair)) {
3537                         m = new WildcardType(lub(wildUpperBound(act1.head),
3538                                                  wildUpperBound(act2.head)),
3539                                              BoundKind.EXTENDS,
3540                                              syms.boundClass);
3541                         mergeCache.remove(pair);
3542                     } else {
3543                         m = new WildcardType(syms.objectType,
3544                                              BoundKind.UNBOUND,
3545                                              syms.boundClass);
3546                     }
3547                     merged.append(m.withTypeVar(typarams.head));
3548                 }
3549                 act1 = act1.tail;
3550                 act2 = act2.tail;
3551                 typarams = typarams.tail;
3552             }
3553             Assert.check(act1.isEmpty() && act2.isEmpty() && typarams.isEmpty());
3554             return new ClassType(class1.getEnclosingType(), merged.toList(), class1.tsym);
3555         }
3556 
3557     /**
3558      * Return the minimum type of a closure, a compound type if no
3559      * unique minimum exists.
3560      */
3561     private Type compoundMin(List<Type> cl) {
3562         if (cl.isEmpty()) return syms.objectType;
3563         List<Type> compound = closureMin(cl);
3564         if (compound.isEmpty())
3565             return null;
3566         else if (compound.tail.isEmpty())
3567             return compound.head;
3568         else
3569             return makeCompoundType(compound);
3570     }
3571 
3572     /**
3573      * Return the minimum types of a closure, suitable for computing
3574      * compoundMin or glb.
3575      */
3576     private List<Type> closureMin(List<Type> cl) {
3577         ListBuffer<Type> classes = new ListBuffer<>();
3578         ListBuffer<Type> interfaces = new ListBuffer<>();
3579         Set<Type> toSkip = new HashSet<>();
3580         while (!cl.isEmpty()) {
3581             Type current = cl.head;
3582             boolean keep = !toSkip.contains(current);
3583             if (keep && current.hasTag(TYPEVAR)) {
3584                 // skip lower-bounded variables with a subtype in cl.tail
3585                 for (Type t : cl.tail) {
3586                     if (isSubtypeNoCapture(t, current)) {
3587                         keep = false;
3588                         break;
3589                     }
3590                 }
3591             }
3592             if (keep) {
3593                 if (current.isInterface())
3594                     interfaces.append(current);
3595                 else
3596                     classes.append(current);
3597                 for (Type t : cl.tail) {
3598                     // skip supertypes of 'current' in cl.tail
3599                     if (isSubtypeNoCapture(current, t))
3600                         toSkip.add(t);
3601                 }
3602             }
3603             cl = cl.tail;
3604         }
3605         return classes.appendList(interfaces).toList();
3606     }
3607 
3608     /**
3609      * Return the least upper bound of list of types.  if the lub does
3610      * not exist return null.
3611      */
3612     public Type lub(List<Type> ts) {
3613         return lub(ts.toArray(new Type[ts.length()]));
3614     }
3615 
3616     /**
3617      * Return the least upper bound (lub) of set of types.  If the lub
3618      * does not exist return the type of null (bottom).
3619      */
3620     public Type lub(Type... ts) {
3621         final int UNKNOWN_BOUND = 0;
3622         final int ARRAY_BOUND = 1;
3623         final int CLASS_BOUND = 2;
3624 
3625         int[] kinds = new int[ts.length];
3626 
3627         int boundkind = UNKNOWN_BOUND;
3628         for (int i = 0 ; i < ts.length ; i++) {
3629             Type t = ts[i];
3630             switch (t.getTag()) {
3631             case CLASS:
3632                 boundkind |= kinds[i] = CLASS_BOUND;
3633                 break;
3634             case ARRAY:
3635                 boundkind |= kinds[i] = ARRAY_BOUND;
3636                 break;
3637             case  TYPEVAR:
3638                 do {
3639                     t = t.getUpperBound();
3640                 } while (t.hasTag(TYPEVAR));
3641                 if (t.hasTag(ARRAY)) {
3642                     boundkind |= kinds[i] = ARRAY_BOUND;
3643                 } else {
3644                     boundkind |= kinds[i] = CLASS_BOUND;
3645                 }
3646                 break;
3647             default:
3648                 kinds[i] = UNKNOWN_BOUND;
3649                 if (t.isPrimitive())
3650                     return syms.errType;
3651             }
3652         }
3653         switch (boundkind) {
3654         case 0:
3655             return syms.botType;
3656 
3657         case ARRAY_BOUND:
3658             // calculate lub(A[], B[])
3659             Type[] elements = new Type[ts.length];
3660             for (int i = 0 ; i < ts.length ; i++) {
3661                 Type elem = elements[i] = elemTypeFun.apply(ts[i]);
3662                 if (elem.isPrimitive()) {
3663                     // if a primitive type is found, then return
3664                     // arraySuperType unless all the types are the
3665                     // same
3666                     Type first = ts[0];
3667                     for (int j = 1 ; j < ts.length ; j++) {
3668                         if (!isSameType(first, ts[j])) {
3669                              // lub(int[], B[]) is Cloneable & Serializable
3670                             return arraySuperType();
3671                         }
3672                     }
3673                     // all the array types are the same, return one
3674                     // lub(int[], int[]) is int[]
3675                     return first;
3676                 }
3677             }
3678             // lub(A[], B[]) is lub(A, B)[]
3679             return new ArrayType(lub(elements), syms.arrayClass);
3680 
3681         case CLASS_BOUND:
3682             // calculate lub(A, B)
3683             int startIdx = 0;
3684             for (int i = 0; i < ts.length ; i++) {
3685                 Type t = ts[i];
3686                 if (t.hasTag(CLASS) || t.hasTag(TYPEVAR)) {
3687                     break;
3688                 } else {
3689                     startIdx++;
3690                 }
3691             }
3692             Assert.check(startIdx < ts.length);
3693             //step 1 - compute erased candidate set (EC)
3694             List<Type> cl = erasedSupertypes(ts[startIdx]);
3695             for (int i = startIdx + 1 ; i < ts.length ; i++) {
3696                 Type t = ts[i];
3697                 if (t.hasTag(CLASS) || t.hasTag(TYPEVAR))
3698                     cl = intersect(cl, erasedSupertypes(t));
3699             }
3700             //step 2 - compute minimal erased candidate set (MEC)
3701             List<Type> mec = closureMin(cl);
3702             //step 3 - for each element G in MEC, compute lci(Inv(G))
3703             List<Type> candidates = List.nil();
3704             for (Type erasedSupertype : mec) {
3705                 List<Type> lci = List.of(asSuper(ts[startIdx], erasedSupertype.tsym));
3706                 for (int i = startIdx + 1 ; i < ts.length ; i++) {
3707                     Type superType = asSuper(ts[i], erasedSupertype.tsym);
3708                     lci = intersect(lci, superType != null ? List.of(superType) : List.<Type>nil());
3709                 }
3710                 candidates = candidates.appendList(lci);
3711             }
3712             //step 4 - let MEC be { G1, G2 ... Gn }, then we have that
3713             //lub = lci(Inv(G1)) & lci(Inv(G2)) & ... & lci(Inv(Gn))
3714             return compoundMin(candidates);
3715 
3716         default:
3717             // calculate lub(A, B[])
3718             List<Type> classes = List.of(arraySuperType());
3719             for (int i = 0 ; i < ts.length ; i++) {
3720                 if (kinds[i] != ARRAY_BOUND) // Filter out any arrays
3721                     classes = classes.prepend(ts[i]);
3722             }
3723             // lub(A, B[]) is lub(A, arraySuperType)
3724             return lub(classes);
3725         }
3726     }
3727     // where
3728         List<Type> erasedSupertypes(Type t) {
3729             ListBuffer<Type> buf = new ListBuffer<>();
3730             for (Type sup : closure(t)) {
3731                 if (sup.hasTag(TYPEVAR)) {
3732                     buf.append(sup);
3733                 } else {
3734                     buf.append(erasure(sup));
3735                 }
3736             }
3737             return buf.toList();
3738         }
3739 
3740         private Type arraySuperType = null;
3741         private Type arraySuperType() {
3742             // initialized lazily to avoid problems during compiler startup
3743             if (arraySuperType == null) {
3744                 synchronized (this) {
3745                     if (arraySuperType == null) {
3746                         // JLS 10.8: all arrays implement Cloneable and Serializable.
3747                         arraySuperType = makeCompoundType(List.of(syms.serializableType,
3748                                                                   syms.cloneableType), true);
3749                     }
3750                 }
3751             }
3752             return arraySuperType;
3753         }
3754     // </editor-fold>
3755 
3756     // <editor-fold defaultstate="collapsed" desc="Greatest lower bound">
3757     public Type glb(List<Type> ts) {
3758         Type t1 = ts.head;
3759         for (Type t2 : ts.tail) {
3760             if (t1.isErroneous())
3761                 return t1;
3762             t1 = glb(t1, t2);
3763         }
3764         return t1;
3765     }
3766     //where
3767     public Type glb(Type t, Type s) {
3768         if (s == null)
3769             return t;
3770         else if (t.isPrimitive() || s.isPrimitive())
3771             return syms.errType;
3772         else if (isSubtypeNoCapture(t, s))
3773             return t;
3774         else if (isSubtypeNoCapture(s, t))
3775             return s;
3776 
3777         List<Type> closure = union(closure(t), closure(s));
3778         return glbFlattened(closure, t);
3779     }
3780     //where
3781     /**
3782      * Perform glb for a list of non-primitive, non-error, non-compound types;
3783      * redundant elements are removed.  Bounds should be ordered according to
3784      * {@link Symbol#precedes(TypeSymbol,Types)}.
3785      *
3786      * @param flatBounds List of type to glb
3787      * @param errT Original type to use if the result is an error type
3788      */
3789     private Type glbFlattened(List<Type> flatBounds, Type errT) {
3790         List<Type> bounds = closureMin(flatBounds);
3791 
3792         if (bounds.isEmpty()) {             // length == 0
3793             return syms.objectType;
3794         } else if (bounds.tail.isEmpty()) { // length == 1
3795             return bounds.head;
3796         } else {                            // length > 1
3797             int classCount = 0;
3798             List<Type> lowers = List.nil();
3799             for (Type bound : bounds) {
3800                 if (!bound.isInterface()) {
3801                     classCount++;
3802                     Type lower = cvarLowerBound(bound);
3803                     if (bound != lower && !lower.hasTag(BOT))
3804                         lowers = insert(lowers, lower);
3805                 }
3806             }
3807             if (classCount > 1) {
3808                 if (lowers.isEmpty())
3809                     return createErrorType(errT);
3810                 else
3811                     return glbFlattened(union(bounds, lowers), errT);
3812             }
3813         }
3814         return makeCompoundType(bounds);
3815     }
3816     // </editor-fold>
3817 
3818     // <editor-fold defaultstate="collapsed" desc="hashCode">
3819     /**
3820      * Compute a hash code on a type.
3821      */
3822     public int hashCode(Type t) {
3823         return hashCode.visit(t);
3824     }
3825     // where
3826         private static final UnaryVisitor<Integer> hashCode = new UnaryVisitor<Integer>() {
3827 
3828             public Integer visitType(Type t, Void ignored) {
3829                 return t.getTag().ordinal();
3830             }
3831 
3832             @Override
3833             public Integer visitClassType(ClassType t, Void ignored) {
3834                 int result = visit(t.getEnclosingType());
3835                 result *= 127;
3836                 result += t.tsym.flatName().hashCode();
3837                 for (Type s : t.getTypeArguments()) {
3838                     result *= 127;
3839                     result += visit(s);
3840                 }
3841                 return result;
3842             }
3843 
3844             @Override
3845             public Integer visitMethodType(MethodType t, Void ignored) {
3846                 int h = METHOD.ordinal();
3847                 for (List<Type> thisargs = t.argtypes;
3848                      thisargs.tail != null;
3849                      thisargs = thisargs.tail)
3850                     h = (h << 5) + visit(thisargs.head);
3851                 return (h << 5) + visit(t.restype);
3852             }
3853 
3854             @Override
3855             public Integer visitWildcardType(WildcardType t, Void ignored) {
3856                 int result = t.kind.hashCode();
3857                 if (t.type != null) {
3858                     result *= 127;
3859                     result += visit(t.type);
3860                 }
3861                 return result;
3862             }
3863 
3864             @Override
3865             public Integer visitArrayType(ArrayType t, Void ignored) {
3866                 return visit(t.elemtype) + 12;
3867             }
3868 
3869             @Override
3870             public Integer visitTypeVar(TypeVar t, Void ignored) {
3871                 return System.identityHashCode(t.tsym);
3872             }
3873 
3874             @Override
3875             public Integer visitUndetVar(UndetVar t, Void ignored) {
3876                 return System.identityHashCode(t);
3877             }
3878 
3879             @Override
3880             public Integer visitErrorType(ErrorType t, Void ignored) {
3881                 return 0;
3882             }
3883         };
3884     // </editor-fold>
3885 
3886     // <editor-fold defaultstate="collapsed" desc="Return-Type-Substitutable">
3887     /**
3888      * Does t have a result that is a subtype of the result type of s,
3889      * suitable for covariant returns?  It is assumed that both types
3890      * are (possibly polymorphic) method types.  Monomorphic method
3891      * types are handled in the obvious way.  Polymorphic method types
3892      * require renaming all type variables of one to corresponding
3893      * type variables in the other, where correspondence is by
3894      * position in the type parameter list. */
3895     public boolean resultSubtype(Type t, Type s, Warner warner) {
3896         List<Type> tvars = t.getTypeArguments();
3897         List<Type> svars = s.getTypeArguments();
3898         Type tres = t.getReturnType();
3899         Type sres = subst(s.getReturnType(), svars, tvars);
3900         return covariantReturnType(tres, sres, warner);
3901     }
3902 
3903     /**
3904      * Return-Type-Substitutable.
3905      * @jls section 8.4.5
3906      */
3907     public boolean returnTypeSubstitutable(Type r1, Type r2) {
3908         if (hasSameArgs(r1, r2))
3909             return resultSubtype(r1, r2, noWarnings);
3910         else
3911             return covariantReturnType(r1.getReturnType(),
3912                                        erasure(r2.getReturnType()),
3913                                        noWarnings);
3914     }
3915 
3916     public boolean returnTypeSubstitutable(Type r1,
3917                                            Type r2, Type r2res,
3918                                            Warner warner) {
3919         if (isSameType(r1.getReturnType(), r2res))
3920             return true;
3921         if (r1.getReturnType().isPrimitive() || r2res.isPrimitive())
3922             return false;
3923 
3924         if (hasSameArgs(r1, r2))
3925             return covariantReturnType(r1.getReturnType(), r2res, warner);
3926         if (!allowCovariantReturns)
3927             return false;
3928         if (isSubtypeUnchecked(r1.getReturnType(), r2res, warner))
3929             return true;
3930         if (!isSubtype(r1.getReturnType(), erasure(r2res)))
3931             return false;
3932         warner.warn(LintCategory.UNCHECKED);
3933         return true;
3934     }
3935 
3936     /**
3937      * Is t an appropriate return type in an overrider for a
3938      * method that returns s?
3939      */
3940     public boolean covariantReturnType(Type t, Type s, Warner warner) {
3941         return
3942             isSameType(t, s) ||
3943             allowCovariantReturns &&
3944             !t.isPrimitive() &&
3945             !s.isPrimitive() &&
3946             isAssignable(t, s, warner);
3947     }
3948     // </editor-fold>
3949 
3950     // <editor-fold defaultstate="collapsed" desc="Box/unbox support">
3951     /**
3952      * Return the class that boxes the given primitive.
3953      */
3954     public ClassSymbol boxedClass(Type t) {
3955         return reader.enterClass(syms.boxedName[t.getTag().ordinal()]);
3956     }
3957 
3958     /**
3959      * Return the boxed type if 't' is primitive, otherwise return 't' itself.
3960      */
3961     public Type boxedTypeOrType(Type t) {
3962         return t.isPrimitive() ?
3963             boxedClass(t).type :
3964             t;
3965     }
3966 
3967     /**
3968      * Return the primitive type corresponding to a boxed type.
3969      */
3970     public Type unboxedType(Type t) {
3971         if (allowBoxing) {
3972             for (int i=0; i<syms.boxedName.length; i++) {
3973                 Name box = syms.boxedName[i];
3974                 if (box != null &&
3975                     asSuper(t, reader.enterClass(box)) != null)
3976                     return syms.typeOfTag[i];
3977             }
3978         }
3979         return Type.noType;
3980     }
3981 
3982     /**
3983      * Return the unboxed type if 't' is a boxed class, otherwise return 't' itself.
3984      */
3985     public Type unboxedTypeOrType(Type t) {
3986         Type unboxedType = unboxedType(t);
3987         return unboxedType.hasTag(NONE) ? t : unboxedType;
3988     }
3989     // </editor-fold>
3990 
3991     // <editor-fold defaultstate="collapsed" desc="Capture conversion">
3992     /*
3993      * JLS 5.1.10 Capture Conversion:
3994      *
3995      * Let G name a generic type declaration with n formal type
3996      * parameters A1 ... An with corresponding bounds U1 ... Un. There
3997      * exists a capture conversion from G<T1 ... Tn> to G<S1 ... Sn>,
3998      * where, for 1 <= i <= n:
3999      *
4000      * + If Ti is a wildcard type argument (4.5.1) of the form ? then
4001      *   Si is a fresh type variable whose upper bound is
4002      *   Ui[A1 := S1, ..., An := Sn] and whose lower bound is the null
4003      *   type.
4004      *
4005      * + If Ti is a wildcard type argument of the form ? extends Bi,
4006      *   then Si is a fresh type variable whose upper bound is
4007      *   glb(Bi, Ui[A1 := S1, ..., An := Sn]) and whose lower bound is
4008      *   the null type, where glb(V1,... ,Vm) is V1 & ... & Vm. It is
4009      *   a compile-time error if for any two classes (not interfaces)
4010      *   Vi and Vj,Vi is not a subclass of Vj or vice versa.
4011      *
4012      * + If Ti is a wildcard type argument of the form ? super Bi,
4013      *   then Si is a fresh type variable whose upper bound is
4014      *   Ui[A1 := S1, ..., An := Sn] and whose lower bound is Bi.
4015      *
4016      * + Otherwise, Si = Ti.
4017      *
4018      * Capture conversion on any type other than a parameterized type
4019      * (4.5) acts as an identity conversion (5.1.1). Capture
4020      * conversions never require a special action at run time and
4021      * therefore never throw an exception at run time.
4022      *
4023      * Capture conversion is not applied recursively.
4024      */
4025     /**
4026      * Capture conversion as specified by the JLS.
4027      */
4028 
4029     public List<Type> capture(List<Type> ts) {
4030         List<Type> buf = List.nil();
4031         for (Type t : ts) {
4032             buf = buf.prepend(capture(t));
4033         }
4034         return buf.reverse();
4035     }
4036 
4037     public Type capture(Type t) {
4038         if (!t.hasTag(CLASS)) {
4039             return t;
4040         }
4041         if (t.getEnclosingType() != Type.noType) {
4042             Type capturedEncl = capture(t.getEnclosingType());
4043             if (capturedEncl != t.getEnclosingType()) {
4044                 Type type1 = memberType(capturedEncl, t.tsym);
4045                 t = subst(type1, t.tsym.type.getTypeArguments(), t.getTypeArguments());
4046             }
4047         }
4048         t = t.unannotatedType();
4049         ClassType cls = (ClassType)t;
4050         if (cls.isRaw() || !cls.isParameterized())
4051             return cls;
4052 
4053         ClassType G = (ClassType)cls.asElement().asType();
4054         List<Type> A = G.getTypeArguments();
4055         List<Type> T = cls.getTypeArguments();
4056         List<Type> S = freshTypeVariables(T);
4057 
4058         List<Type> currentA = A;
4059         List<Type> currentT = T;
4060         List<Type> currentS = S;
4061         boolean captured = false;
4062         while (!currentA.isEmpty() &&
4063                !currentT.isEmpty() &&
4064                !currentS.isEmpty()) {
4065             if (currentS.head != currentT.head) {
4066                 captured = true;
4067                 WildcardType Ti = (WildcardType)currentT.head.unannotatedType();
4068                 Type Ui = currentA.head.getUpperBound();
4069                 CapturedType Si = (CapturedType)currentS.head.unannotatedType();
4070                 if (Ui == null)
4071                     Ui = syms.objectType;
4072                 switch (Ti.kind) {
4073                 case UNBOUND:
4074                     Si.bound = subst(Ui, A, S);
4075                     Si.lower = syms.botType;
4076                     break;
4077                 case EXTENDS:
4078                     Si.bound = glb(Ti.getExtendsBound(), subst(Ui, A, S));
4079                     Si.lower = syms.botType;
4080                     break;
4081                 case SUPER:
4082                     Si.bound = subst(Ui, A, S);
4083                     Si.lower = Ti.getSuperBound();
4084                     break;
4085                 }
4086                 Type tmpBound = Si.bound.hasTag(UNDETVAR) ? ((UndetVar)Si.bound).qtype : Si.bound;
4087                 Type tmpLower = Si.lower.hasTag(UNDETVAR) ? ((UndetVar)Si.lower).qtype : Si.lower;
4088                 if (!Si.bound.hasTag(ERROR) &&
4089                     !Si.lower.hasTag(ERROR) &&
4090                     isSameType(tmpBound, tmpLower, false)) {
4091                     currentS.head = Si.bound;
4092                 }
4093             }
4094             currentA = currentA.tail;
4095             currentT = currentT.tail;
4096             currentS = currentS.tail;
4097         }
4098         if (!currentA.isEmpty() || !currentT.isEmpty() || !currentS.isEmpty())
4099             return erasure(t); // some "rare" type involved
4100 
4101         if (captured)
4102             return new ClassType(cls.getEnclosingType(), S, cls.tsym);
4103         else
4104             return t;
4105     }
4106     // where
4107         public List<Type> freshTypeVariables(List<Type> types) {
4108             ListBuffer<Type> result = new ListBuffer<>();
4109             for (Type t : types) {
4110                 if (t.hasTag(WILDCARD)) {
4111                     t = t.unannotatedType();
4112                     Type bound = ((WildcardType)t).getExtendsBound();
4113                     if (bound == null)
4114                         bound = syms.objectType;
4115                     result.append(new CapturedType(capturedName,
4116                                                    syms.noSymbol,
4117                                                    bound,
4118                                                    syms.botType,
4119                                                    (WildcardType)t));
4120                 } else {
4121                     result.append(t);
4122                 }
4123             }
4124             return result.toList();
4125         }
4126     // </editor-fold>
4127 
4128     // <editor-fold defaultstate="collapsed" desc="Internal utility methods">
4129     private boolean sideCast(Type from, Type to, Warner warn) {
4130         // We are casting from type $from$ to type $to$, which are
4131         // non-final unrelated types.  This method
4132         // tries to reject a cast by transferring type parameters
4133         // from $to$ to $from$ by common superinterfaces.
4134         boolean reverse = false;
4135         Type target = to;
4136         if ((to.tsym.flags() & INTERFACE) == 0) {
4137             Assert.check((from.tsym.flags() & INTERFACE) != 0);
4138             reverse = true;
4139             to = from;
4140             from = target;
4141         }
4142         List<Type> commonSupers = superClosure(to, erasure(from));
4143         boolean giveWarning = commonSupers.isEmpty();
4144         // The arguments to the supers could be unified here to
4145         // get a more accurate analysis
4146         while (commonSupers.nonEmpty()) {
4147             Type t1 = asSuper(from, commonSupers.head.tsym);
4148             Type t2 = commonSupers.head; // same as asSuper(to, commonSupers.head.tsym);
4149             if (disjointTypes(t1.getTypeArguments(), t2.getTypeArguments()))
4150                 return false;
4151             giveWarning = giveWarning || (reverse ? giveWarning(t2, t1) : giveWarning(t1, t2));
4152             commonSupers = commonSupers.tail;
4153         }
4154         if (giveWarning && !isReifiable(reverse ? from : to))
4155             warn.warn(LintCategory.UNCHECKED);
4156         if (!allowCovariantReturns)
4157             // reject if there is a common method signature with
4158             // incompatible return types.
4159             chk.checkCompatibleAbstracts(warn.pos(), from, to);
4160         return true;
4161     }
4162 
4163     private boolean sideCastFinal(Type from, Type to, Warner warn) {
4164         // We are casting from type $from$ to type $to$, which are
4165         // unrelated types one of which is final and the other of
4166         // which is an interface.  This method
4167         // tries to reject a cast by transferring type parameters
4168         // from the final class to the interface.
4169         boolean reverse = false;
4170         Type target = to;
4171         if ((to.tsym.flags() & INTERFACE) == 0) {
4172             Assert.check((from.tsym.flags() & INTERFACE) != 0);
4173             reverse = true;
4174             to = from;
4175             from = target;
4176         }
4177         Assert.check((from.tsym.flags() & FINAL) != 0);
4178         Type t1 = asSuper(from, to.tsym);
4179         if (t1 == null) return false;
4180         Type t2 = to;
4181         if (disjointTypes(t1.getTypeArguments(), t2.getTypeArguments()))
4182             return false;
4183         if (!allowCovariantReturns)
4184             // reject if there is a common method signature with
4185             // incompatible return types.
4186             chk.checkCompatibleAbstracts(warn.pos(), from, to);
4187         if (!isReifiable(target) &&
4188             (reverse ? giveWarning(t2, t1) : giveWarning(t1, t2)))
4189             warn.warn(LintCategory.UNCHECKED);
4190         return true;
4191     }
4192 
4193     private boolean giveWarning(Type from, Type to) {
4194         List<Type> bounds = to.isCompound() ?
4195                 ((IntersectionClassType)to.unannotatedType()).getComponents() : List.of(to);
4196         for (Type b : bounds) {
4197             Type subFrom = asSub(from, b.tsym);
4198             if (b.isParameterized() &&
4199                     (!(isUnbounded(b) ||
4200                     isSubtype(from, b) ||
4201                     ((subFrom != null) && containsType(b.allparams(), subFrom.allparams()))))) {
4202                 return true;
4203             }
4204         }
4205         return false;
4206     }
4207 
4208     private List<Type> superClosure(Type t, Type s) {
4209         List<Type> cl = List.nil();
4210         for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail) {
4211             if (isSubtype(s, erasure(l.head))) {
4212                 cl = insert(cl, l.head);
4213             } else {
4214                 cl = union(cl, superClosure(l.head, s));
4215             }
4216         }
4217         return cl;
4218     }
4219 
4220     private boolean containsTypeEquivalent(Type t, Type s) {
4221         return
4222             isSameType(t, s) || // shortcut
4223             containsType(t, s) && containsType(s, t);
4224     }
4225 
4226     // <editor-fold defaultstate="collapsed" desc="adapt">
4227     /**
4228      * Adapt a type by computing a substitution which maps a source
4229      * type to a target type.
4230      *
4231      * @param source    the source type
4232      * @param target    the target type
4233      * @param from      the type variables of the computed substitution
4234      * @param to        the types of the computed substitution.
4235      */
4236     public void adapt(Type source,
4237                        Type target,
4238                        ListBuffer<Type> from,
4239                        ListBuffer<Type> to) throws AdaptFailure {
4240         new Adapter(from, to).adapt(source, target);
4241     }
4242 
4243     class Adapter extends SimpleVisitor<Void, Type> {
4244 
4245         ListBuffer<Type> from;
4246         ListBuffer<Type> to;
4247         Map<Symbol,Type> mapping;
4248 
4249         Adapter(ListBuffer<Type> from, ListBuffer<Type> to) {
4250             this.from = from;
4251             this.to = to;
4252             mapping = new HashMap<Symbol,Type>();
4253         }
4254 
4255         public void adapt(Type source, Type target) throws AdaptFailure {
4256             visit(source, target);
4257             List<Type> fromList = from.toList();
4258             List<Type> toList = to.toList();
4259             while (!fromList.isEmpty()) {
4260                 Type val = mapping.get(fromList.head.tsym);
4261                 if (toList.head != val)
4262                     toList.head = val;
4263                 fromList = fromList.tail;
4264                 toList = toList.tail;
4265             }
4266         }
4267 
4268         @Override
4269         public Void visitClassType(ClassType source, Type target) throws AdaptFailure {
4270             if (target.hasTag(CLASS))
4271                 adaptRecursive(source.allparams(), target.allparams());
4272             return null;
4273         }
4274 
4275         @Override
4276         public Void visitArrayType(ArrayType source, Type target) throws AdaptFailure {
4277             if (target.hasTag(ARRAY))
4278                 adaptRecursive(elemtype(source), elemtype(target));
4279             return null;
4280         }
4281 
4282         @Override
4283         public Void visitWildcardType(WildcardType source, Type target) throws AdaptFailure {
4284             if (source.isExtendsBound())
4285                 adaptRecursive(wildUpperBound(source), wildUpperBound(target));
4286             else if (source.isSuperBound())
4287                 adaptRecursive(wildLowerBound(source), wildLowerBound(target));
4288             return null;
4289         }
4290 
4291         @Override
4292         public Void visitTypeVar(TypeVar source, Type target) throws AdaptFailure {
4293             // Check to see if there is
4294             // already a mapping for $source$, in which case
4295             // the old mapping will be merged with the new
4296             Type val = mapping.get(source.tsym);
4297             if (val != null) {
4298                 if (val.isSuperBound() && target.isSuperBound()) {
4299                     val = isSubtype(wildLowerBound(val), wildLowerBound(target))
4300                         ? target : val;
4301                 } else if (val.isExtendsBound() && target.isExtendsBound()) {
4302                     val = isSubtype(wildUpperBound(val), wildUpperBound(target))
4303                         ? val : target;
4304                 } else if (!isSameType(val, target)) {
4305                     throw new AdaptFailure();
4306                 }
4307             } else {
4308                 val = target;
4309                 from.append(source);
4310                 to.append(target);
4311             }
4312             mapping.put(source.tsym, val);
4313             return null;
4314         }
4315 
4316         @Override
4317         public Void visitType(Type source, Type target) {
4318             return null;
4319         }
4320 
4321         private Set<TypePair> cache = new HashSet<TypePair>();
4322 
4323         private void adaptRecursive(Type source, Type target) {
4324             TypePair pair = new TypePair(source, target);
4325             if (cache.add(pair)) {
4326                 try {
4327                     visit(source, target);
4328                 } finally {
4329                     cache.remove(pair);
4330                 }
4331             }
4332         }
4333 
4334         private void adaptRecursive(List<Type> source, List<Type> target) {
4335             if (source.length() == target.length()) {
4336                 while (source.nonEmpty()) {
4337                     adaptRecursive(source.head, target.head);
4338                     source = source.tail;
4339                     target = target.tail;
4340                 }
4341             }
4342         }
4343     }
4344 
4345     public static class AdaptFailure extends RuntimeException {
4346         static final long serialVersionUID = -7490231548272701566L;
4347     }
4348 
4349     private void adaptSelf(Type t,
4350                            ListBuffer<Type> from,
4351                            ListBuffer<Type> to) {
4352         try {
4353             //if (t.tsym.type != t)
4354                 adapt(t.tsym.type, t, from, to);
4355         } catch (AdaptFailure ex) {
4356             // Adapt should never fail calculating a mapping from
4357             // t.tsym.type to t as there can be no merge problem.
4358             throw new AssertionError(ex);
4359         }
4360     }
4361     // </editor-fold>
4362 
4363     /**
4364      * Rewrite all type variables (universal quantifiers) in the given
4365      * type to wildcards (existential quantifiers).  This is used to
4366      * determine if a cast is allowed.  For example, if high is true
4367      * and {@code T <: Number}, then {@code List<T>} is rewritten to
4368      * {@code List<?  extends Number>}.  Since {@code List<Integer> <:
4369      * List<? extends Number>} a {@code List<T>} can be cast to {@code
4370      * List<Integer>} with a warning.
4371      * @param t a type
4372      * @param high if true return an upper bound; otherwise a lower
4373      * bound
4374      * @param rewriteTypeVars only rewrite captured wildcards if false;
4375      * otherwise rewrite all type variables
4376      * @return the type rewritten with wildcards (existential
4377      * quantifiers) only
4378      */
4379     private Type rewriteQuantifiers(Type t, boolean high, boolean rewriteTypeVars) {
4380         return new Rewriter(high, rewriteTypeVars).visit(t);
4381     }
4382 
4383     class Rewriter extends UnaryVisitor<Type> {
4384 
4385         boolean high;
4386         boolean rewriteTypeVars;
4387 
4388         Rewriter(boolean high, boolean rewriteTypeVars) {
4389             this.high = high;
4390             this.rewriteTypeVars = rewriteTypeVars;
4391         }
4392 
4393         @Override
4394         public Type visitClassType(ClassType t, Void s) {
4395             ListBuffer<Type> rewritten = new ListBuffer<Type>();
4396             boolean changed = false;
4397             for (Type arg : t.allparams()) {
4398                 Type bound = visit(arg);
4399                 if (arg != bound) {
4400                     changed = true;
4401                 }
4402                 rewritten.append(bound);
4403             }
4404             if (changed)
4405                 return subst(t.tsym.type,
4406                         t.tsym.type.allparams(),
4407                         rewritten.toList());
4408             else
4409                 return t;
4410         }
4411 
4412         public Type visitType(Type t, Void s) {
4413             return t;
4414         }
4415 
4416         @Override
4417         public Type visitCapturedType(CapturedType t, Void s) {
4418             Type w_bound = t.wildcard.type;
4419             Type bound = w_bound.contains(t) ?
4420                         erasure(w_bound) :
4421                         visit(w_bound);
4422             return rewriteAsWildcardType(visit(bound), t.wildcard.bound, t.wildcard.kind);
4423         }
4424 
4425         @Override
4426         public Type visitTypeVar(TypeVar t, Void s) {
4427             if (rewriteTypeVars) {
4428                 Type bound = t.bound.contains(t) ?
4429                         erasure(t.bound) :
4430                         visit(t.bound);
4431                 return rewriteAsWildcardType(bound, t, EXTENDS);
4432             } else {
4433                 return t;
4434             }
4435         }
4436 
4437         @Override
4438         public Type visitWildcardType(WildcardType t, Void s) {
4439             Type bound2 = visit(t.type);
4440             return t.type == bound2 ? t : rewriteAsWildcardType(bound2, t.bound, t.kind);
4441         }
4442 
4443         private Type rewriteAsWildcardType(Type bound, TypeVar formal, BoundKind bk) {
4444             switch (bk) {
4445                case EXTENDS: return high ?
4446                        makeExtendsWildcard(B(bound), formal) :
4447                        makeExtendsWildcard(syms.objectType, formal);
4448                case SUPER: return high ?
4449                        makeSuperWildcard(syms.botType, formal) :
4450                        makeSuperWildcard(B(bound), formal);
4451                case UNBOUND: return makeExtendsWildcard(syms.objectType, formal);
4452                default:
4453                    Assert.error("Invalid bound kind " + bk);
4454                    return null;
4455             }
4456         }
4457 
4458         Type B(Type t) {
4459             while (t.hasTag(WILDCARD)) {
4460                 WildcardType w = (WildcardType)t.unannotatedType();
4461                 t = high ?
4462                     w.getExtendsBound() :
4463                     w.getSuperBound();
4464                 if (t == null) {
4465                     t = high ? syms.objectType : syms.botType;
4466                 }
4467             }
4468             return t;
4469         }
4470     }
4471 
4472 
4473     /**
4474      * Create a wildcard with the given upper (extends) bound; create
4475      * an unbounded wildcard if bound is Object.
4476      *
4477      * @param bound the upper bound
4478      * @param formal the formal type parameter that will be
4479      * substituted by the wildcard
4480      */
4481     private WildcardType makeExtendsWildcard(Type bound, TypeVar formal) {
4482         if (bound == syms.objectType) {
4483             return new WildcardType(syms.objectType,
4484                                     BoundKind.UNBOUND,
4485                                     syms.boundClass,
4486                                     formal);
4487         } else {
4488             return new WildcardType(bound,
4489                                     BoundKind.EXTENDS,
4490                                     syms.boundClass,
4491                                     formal);
4492         }
4493     }
4494 
4495     /**
4496      * Create a wildcard with the given lower (super) bound; create an
4497      * unbounded wildcard if bound is bottom (type of {@code null}).
4498      *
4499      * @param bound the lower bound
4500      * @param formal the formal type parameter that will be
4501      * substituted by the wildcard
4502      */
4503     private WildcardType makeSuperWildcard(Type bound, TypeVar formal) {
4504         if (bound.hasTag(BOT)) {
4505             return new WildcardType(syms.objectType,
4506                                     BoundKind.UNBOUND,
4507                                     syms.boundClass,
4508                                     formal);
4509         } else {
4510             return new WildcardType(bound,
4511                                     BoundKind.SUPER,
4512                                     syms.boundClass,
4513                                     formal);
4514         }
4515     }
4516 
4517     /**
4518      * A wrapper for a type that allows use in sets.
4519      */
4520     public static class UniqueType {
4521         public final Type type;
4522         final Types types;
4523 
4524         public UniqueType(Type type, Types types) {
4525             this.type = type;
4526             this.types = types;
4527         }
4528 
4529         public int hashCode() {
4530             return types.hashCode(type);
4531         }
4532 
4533         public boolean equals(Object obj) {
4534             return (obj instanceof UniqueType) &&
4535                 types.isSameAnnotatedType(type, ((UniqueType)obj).type);
4536         }
4537 
4538         public String toString() {
4539             return type.toString();
4540         }
4541 
4542     }
4543     // </editor-fold>
4544 
4545     // <editor-fold defaultstate="collapsed" desc="Visitors">
4546     /**
4547      * A default visitor for types.  All visitor methods except
4548      * visitType are implemented by delegating to visitType.  Concrete
4549      * subclasses must provide an implementation of visitType and can
4550      * override other methods as needed.
4551      *
4552      * @param <R> the return type of the operation implemented by this
4553      * visitor; use Void if no return type is needed.
4554      * @param <S> the type of the second argument (the first being the
4555      * type itself) of the operation implemented by this visitor; use
4556      * Void if a second argument is not needed.
4557      */
4558     public static abstract class DefaultTypeVisitor<R,S> implements Type.Visitor<R,S> {
4559         final public R visit(Type t, S s)               { return t.accept(this, s); }
4560         public R visitClassType(ClassType t, S s)       { return visitType(t, s); }
4561         public R visitWildcardType(WildcardType t, S s) { return visitType(t, s); }
4562         public R visitArrayType(ArrayType t, S s)       { return visitType(t, s); }
4563         public R visitMethodType(MethodType t, S s)     { return visitType(t, s); }
4564         public R visitPackageType(PackageType t, S s)   { return visitType(t, s); }
4565         public R visitTypeVar(TypeVar t, S s)           { return visitType(t, s); }
4566         public R visitCapturedType(CapturedType t, S s) { return visitType(t, s); }
4567         public R visitForAll(ForAll t, S s)             { return visitType(t, s); }
4568         public R visitUndetVar(UndetVar t, S s)         { return visitType(t, s); }
4569         public R visitErrorType(ErrorType t, S s)       { return visitType(t, s); }
4570         // Pretend annotations don't exist
4571         public R visitAnnotatedType(AnnotatedType t, S s) { return visit(t.unannotatedType(), s); }
4572     }
4573 
4574     /**
4575      * A default visitor for symbols.  All visitor methods except
4576      * visitSymbol are implemented by delegating to visitSymbol.  Concrete
4577      * subclasses must provide an implementation of visitSymbol and can
4578      * override other methods as needed.
4579      *
4580      * @param <R> the return type of the operation implemented by this
4581      * visitor; use Void if no return type is needed.
4582      * @param <S> the type of the second argument (the first being the
4583      * symbol itself) of the operation implemented by this visitor; use
4584      * Void if a second argument is not needed.
4585      */
4586     public static abstract class DefaultSymbolVisitor<R,S> implements Symbol.Visitor<R,S> {
4587         final public R visit(Symbol s, S arg)                   { return s.accept(this, arg); }
4588         public R visitClassSymbol(ClassSymbol s, S arg)         { return visitSymbol(s, arg); }
4589         public R visitMethodSymbol(MethodSymbol s, S arg)       { return visitSymbol(s, arg); }
4590         public R visitOperatorSymbol(OperatorSymbol s, S arg)   { return visitSymbol(s, arg); }
4591         public R visitPackageSymbol(PackageSymbol s, S arg)     { return visitSymbol(s, arg); }
4592         public R visitTypeSymbol(TypeSymbol s, S arg)           { return visitSymbol(s, arg); }
4593         public R visitVarSymbol(VarSymbol s, S arg)             { return visitSymbol(s, arg); }
4594     }
4595 
4596     /**
4597      * A <em>simple</em> visitor for types.  This visitor is simple as
4598      * captured wildcards, for-all types (generic methods), and
4599      * undetermined type variables (part of inference) are hidden.
4600      * Captured wildcards are hidden by treating them as type
4601      * variables and the rest are hidden by visiting their qtypes.
4602      *
4603      * @param <R> the return type of the operation implemented by this
4604      * visitor; use Void if no return type is needed.
4605      * @param <S> the type of the second argument (the first being the
4606      * type itself) of the operation implemented by this visitor; use
4607      * Void if a second argument is not needed.
4608      */
4609     public static abstract class SimpleVisitor<R,S> extends DefaultTypeVisitor<R,S> {
4610         @Override
4611         public R visitCapturedType(CapturedType t, S s) {
4612             return visitTypeVar(t, s);
4613         }
4614         @Override
4615         public R visitForAll(ForAll t, S s) {
4616             return visit(t.qtype, s);
4617         }
4618         @Override
4619         public R visitUndetVar(UndetVar t, S s) {
4620             return visit(t.qtype, s);
4621         }
4622     }
4623 
4624     /**
4625      * A plain relation on types.  That is a 2-ary function on the
4626      * form Type&nbsp;&times;&nbsp;Type&nbsp;&rarr;&nbsp;Boolean.
4627      * <!-- In plain text: Type x Type -> Boolean -->
4628      */
4629     public static abstract class TypeRelation extends SimpleVisitor<Boolean,Type> {}
4630 
4631     /**
4632      * A convenience visitor for implementing operations that only
4633      * require one argument (the type itself), that is, unary
4634      * operations.
4635      *
4636      * @param <R> the return type of the operation implemented by this
4637      * visitor; use Void if no return type is needed.
4638      */
4639     public static abstract class UnaryVisitor<R> extends SimpleVisitor<R,Void> {
4640         final public R visit(Type t) { return t.accept(this, null); }
4641     }
4642 
4643     /**
4644      * A visitor for implementing a mapping from types to types.  The
4645      * default behavior of this class is to implement the identity
4646      * mapping (mapping a type to itself).  This can be overridden in
4647      * subclasses.
4648      *
4649      * @param <S> the type of the second argument (the first being the
4650      * type itself) of this mapping; use Void if a second argument is
4651      * not needed.
4652      */
4653     public static class MapVisitor<S> extends DefaultTypeVisitor<Type,S> {
4654         final public Type visit(Type t) { return t.accept(this, null); }
4655         public Type visitType(Type t, S s) { return t; }
4656     }
4657     // </editor-fold>
4658 
4659 
4660     // <editor-fold defaultstate="collapsed" desc="Annotation support">
4661 
4662     public RetentionPolicy getRetention(Attribute.Compound a) {
4663         return getRetention(a.type.tsym);
4664     }
4665 
4666     public RetentionPolicy getRetention(Symbol sym) {
4667         RetentionPolicy vis = RetentionPolicy.CLASS; // the default
4668         Attribute.Compound c = sym.attribute(syms.retentionType.tsym);
4669         if (c != null) {
4670             Attribute value = c.member(names.value);
4671             if (value != null && value instanceof Attribute.Enum) {
4672                 Name levelName = ((Attribute.Enum)value).value.name;
4673                 if (levelName == names.SOURCE) vis = RetentionPolicy.SOURCE;
4674                 else if (levelName == names.CLASS) vis = RetentionPolicy.CLASS;
4675                 else if (levelName == names.RUNTIME) vis = RetentionPolicy.RUNTIME;
4676                 else ;// /* fail soft */ throw new AssertionError(levelName);
4677             }
4678         }
4679         return vis;
4680     }
4681     // </editor-fold>
4682 
4683     // <editor-fold defaultstate="collapsed" desc="Signature Generation">
4684 
4685     public static abstract class SignatureGenerator {
4686 
4687         private final Types types;
4688 
4689         protected abstract void append(char ch);
4690         protected abstract void append(byte[] ba);
4691         protected abstract void append(Name name);
4692         protected void classReference(ClassSymbol c) { /* by default: no-op */ }
4693 
4694         protected SignatureGenerator(Types types) {
4695             this.types = types;
4696         }
4697 
4698         /**
4699          * Assemble signature of given type in string buffer.
4700          */
4701         public void assembleSig(Type type) {
4702             type = type.unannotatedType();
4703             switch (type.getTag()) {
4704                 case BYTE:
4705                     append('B');
4706                     break;
4707                 case SHORT:
4708                     append('S');
4709                     break;
4710                 case CHAR:
4711                     append('C');
4712                     break;
4713                 case INT:
4714                     append('I');
4715                     break;
4716                 case LONG:
4717                     append('J');
4718                     break;
4719                 case FLOAT:
4720                     append('F');
4721                     break;
4722                 case DOUBLE:
4723                     append('D');
4724                     break;
4725                 case BOOLEAN:
4726                     append('Z');
4727                     break;
4728                 case VOID:
4729                     append('V');
4730                     break;
4731                 case CLASS:
4732                     append('L');
4733                     assembleClassSig(type);
4734                     append(';');
4735                     break;
4736                 case ARRAY:
4737                     ArrayType at = (ArrayType) type;
4738                     append('[');
4739                     assembleSig(at.elemtype);
4740                     break;
4741                 case METHOD:
4742                     MethodType mt = (MethodType) type;
4743                     append('(');
4744                     assembleSig(mt.argtypes);
4745                     append(')');
4746                     assembleSig(mt.restype);
4747                     if (hasTypeVar(mt.thrown)) {
4748                         for (List<Type> l = mt.thrown; l.nonEmpty(); l = l.tail) {
4749                             append('^');
4750                             assembleSig(l.head);
4751                         }
4752                     }
4753                     break;
4754                 case WILDCARD: {
4755                     Type.WildcardType ta = (Type.WildcardType) type;
4756                     switch (ta.kind) {
4757                         case SUPER:
4758                             append('-');
4759                             assembleSig(ta.type);
4760                             break;
4761                         case EXTENDS:
4762                             append('+');
4763                             assembleSig(ta.type);
4764                             break;
4765                         case UNBOUND:
4766                             append('*');
4767                             break;
4768                         default:
4769                             throw new AssertionError(ta.kind);
4770                     }
4771                     break;
4772                 }
4773                 case TYPEVAR:
4774                     append('T');
4775                     append(type.tsym.name);
4776                     append(';');
4777                     break;
4778                 case FORALL:
4779                     Type.ForAll ft = (Type.ForAll) type;
4780                     assembleParamsSig(ft.tvars);
4781                     assembleSig(ft.qtype);
4782                     break;
4783                 default:
4784                     throw new AssertionError("typeSig " + type.getTag());
4785             }
4786         }
4787 
4788         public boolean hasTypeVar(List<Type> l) {
4789             while (l.nonEmpty()) {
4790                 if (l.head.hasTag(TypeTag.TYPEVAR)) {
4791                     return true;
4792                 }
4793                 l = l.tail;
4794             }
4795             return false;
4796         }
4797 
4798         public void assembleClassSig(Type type) {
4799             type = type.unannotatedType();
4800             ClassType ct = (ClassType) type;
4801             ClassSymbol c = (ClassSymbol) ct.tsym;
4802             classReference(c);
4803             Type outer = ct.getEnclosingType();
4804             if (outer.allparams().nonEmpty()) {
4805                 boolean rawOuter =
4806                         c.owner.kind == Kinds.MTH || // either a local class
4807                         c.name == types.names.empty; // or anonymous
4808                 assembleClassSig(rawOuter
4809                         ? types.erasure(outer)
4810                         : outer);
4811                 append(rawOuter ? '$' : '.');
4812                 Assert.check(c.flatname.startsWith(c.owner.enclClass().flatname));
4813                 append(rawOuter
4814                         ? c.flatname.subName(c.owner.enclClass().flatname.getByteLength() + 1, c.flatname.getByteLength())
4815                         : c.name);
4816             } else {
4817                 append(externalize(c.flatname));
4818             }
4819             if (ct.getTypeArguments().nonEmpty()) {
4820                 append('<');
4821                 assembleSig(ct.getTypeArguments());
4822                 append('>');
4823             }
4824         }
4825 
4826         public void assembleParamsSig(List<Type> typarams) {
4827             append('<');
4828             for (List<Type> ts = typarams; ts.nonEmpty(); ts = ts.tail) {
4829                 Type.TypeVar tvar = (Type.TypeVar) ts.head;
4830                 append(tvar.tsym.name);
4831                 List<Type> bounds = types.getBounds(tvar);
4832                 if ((bounds.head.tsym.flags() & INTERFACE) != 0) {
4833                     append(':');
4834                 }
4835                 for (List<Type> l = bounds; l.nonEmpty(); l = l.tail) {
4836                     append(':');
4837                     assembleSig(l.head);
4838                 }
4839             }
4840             append('>');
4841         }
4842 
4843         private void assembleSig(List<Type> types) {
4844             for (List<Type> ts = types; ts.nonEmpty(); ts = ts.tail) {
4845                 assembleSig(ts.head);
4846             }
4847         }
4848     }
4849     // </editor-fold>
4850 }