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