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