Mon, 29 Sep 2008 11:38:56 -0700
6739427: -Xlint:processing not recognized as an option
Reviewed-by: darcy, jjg
Contributed-by: lipeng@google.com
1 /*
2 * Copyright 2003-2008 Sun Microsystems, Inc. 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. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any questions.
24 */
26 package com.sun.tools.javac.code;
28 import java.util.*;
30 import com.sun.tools.javac.util.*;
31 import com.sun.tools.javac.util.List;
33 import com.sun.tools.javac.jvm.ClassReader;
34 import com.sun.tools.javac.comp.Check;
36 import static com.sun.tools.javac.code.Type.*;
37 import static com.sun.tools.javac.code.TypeTags.*;
38 import static com.sun.tools.javac.code.Symbol.*;
39 import static com.sun.tools.javac.code.Flags.*;
40 import static com.sun.tools.javac.code.BoundKind.*;
41 import static com.sun.tools.javac.util.ListBuffer.lb;
43 /**
44 * Utility class containing various operations on types.
45 *
46 * <p>Unless other names are more illustrative, the following naming
47 * conventions should be observed in this file:
48 *
49 * <dl>
50 * <dt>t</dt>
51 * <dd>If the first argument to an operation is a type, it should be named t.</dd>
52 * <dt>s</dt>
53 * <dd>Similarly, if the second argument to an operation is a type, it should be named s.</dd>
54 * <dt>ts</dt>
55 * <dd>If an operations takes a list of types, the first should be named ts.</dd>
56 * <dt>ss</dt>
57 * <dd>A second list of types should be named ss.</dd>
58 * </dl>
59 *
60 * <p><b>This is NOT part of any API supported by Sun Microsystems.
61 * If you write code that depends on this, you do so at your own risk.
62 * This code and its internal interfaces are subject to change or
63 * deletion without notice.</b>
64 */
65 public class Types {
66 protected static final Context.Key<Types> typesKey =
67 new Context.Key<Types>();
69 final Symtab syms;
70 final Messages messages;
71 final Names names;
72 final boolean allowBoxing;
73 final ClassReader reader;
74 final Source source;
75 final Check chk;
76 List<Warner> warnStack = List.nil();
77 final Name capturedName;
79 // <editor-fold defaultstate="collapsed" desc="Instantiating">
80 public static Types instance(Context context) {
81 Types instance = context.get(typesKey);
82 if (instance == null)
83 instance = new Types(context);
84 return instance;
85 }
87 protected Types(Context context) {
88 context.put(typesKey, this);
89 syms = Symtab.instance(context);
90 names = Names.instance(context);
91 allowBoxing = Source.instance(context).allowBoxing();
92 reader = ClassReader.instance(context);
93 source = Source.instance(context);
94 chk = Check.instance(context);
95 capturedName = names.fromString("<captured wildcard>");
96 messages = Messages.instance(context);
97 }
98 // </editor-fold>
100 // <editor-fold defaultstate="collapsed" desc="upperBound">
101 /**
102 * The "rvalue conversion".<br>
103 * The upper bound of most types is the type
104 * itself. Wildcards, on the other hand have upper
105 * and lower bounds.
106 * @param t a type
107 * @return the upper bound of the given type
108 */
109 public Type upperBound(Type t) {
110 return upperBound.visit(t);
111 }
112 // where
113 private final MapVisitor<Void> upperBound = new MapVisitor<Void>() {
115 @Override
116 public Type visitWildcardType(WildcardType t, Void ignored) {
117 if (t.isSuperBound())
118 return t.bound == null ? syms.objectType : t.bound.bound;
119 else
120 return visit(t.type);
121 }
123 @Override
124 public Type visitCapturedType(CapturedType t, Void ignored) {
125 return visit(t.bound);
126 }
127 };
128 // </editor-fold>
130 // <editor-fold defaultstate="collapsed" desc="lowerBound">
131 /**
132 * The "lvalue conversion".<br>
133 * The lower bound of most types is the type
134 * itself. Wildcards, on the other hand have upper
135 * and lower bounds.
136 * @param t a type
137 * @return the lower bound of the given type
138 */
139 public Type lowerBound(Type t) {
140 return lowerBound.visit(t);
141 }
142 // where
143 private final MapVisitor<Void> lowerBound = new MapVisitor<Void>() {
145 @Override
146 public Type visitWildcardType(WildcardType t, Void ignored) {
147 return t.isExtendsBound() ? syms.botType : visit(t.type);
148 }
150 @Override
151 public Type visitCapturedType(CapturedType t, Void ignored) {
152 return visit(t.getLowerBound());
153 }
154 };
155 // </editor-fold>
157 // <editor-fold defaultstate="collapsed" desc="isUnbounded">
158 /**
159 * Checks that all the arguments to a class are unbounded
160 * wildcards or something else that doesn't make any restrictions
161 * on the arguments. If a class isUnbounded, a raw super- or
162 * subclass can be cast to it without a warning.
163 * @param t a type
164 * @return true iff the given type is unbounded or raw
165 */
166 public boolean isUnbounded(Type t) {
167 return isUnbounded.visit(t);
168 }
169 // where
170 private final UnaryVisitor<Boolean> isUnbounded = new UnaryVisitor<Boolean>() {
172 public Boolean visitType(Type t, Void ignored) {
173 return true;
174 }
176 @Override
177 public Boolean visitClassType(ClassType t, Void ignored) {
178 List<Type> parms = t.tsym.type.allparams();
179 List<Type> args = t.allparams();
180 while (parms.nonEmpty()) {
181 WildcardType unb = new WildcardType(syms.objectType,
182 BoundKind.UNBOUND,
183 syms.boundClass,
184 (TypeVar)parms.head);
185 if (!containsType(args.head, unb))
186 return false;
187 parms = parms.tail;
188 args = args.tail;
189 }
190 return true;
191 }
192 };
193 // </editor-fold>
195 // <editor-fold defaultstate="collapsed" desc="asSub">
196 /**
197 * Return the least specific subtype of t that starts with symbol
198 * sym. If none exists, return null. The least specific subtype
199 * is determined as follows:
200 *
201 * <p>If there is exactly one parameterized instance of sym that is a
202 * subtype of t, that parameterized instance is returned.<br>
203 * Otherwise, if the plain type or raw type `sym' is a subtype of
204 * type t, the type `sym' itself is returned. Otherwise, null is
205 * returned.
206 */
207 public Type asSub(Type t, Symbol sym) {
208 return asSub.visit(t, sym);
209 }
210 // where
211 private final SimpleVisitor<Type,Symbol> asSub = new SimpleVisitor<Type,Symbol>() {
213 public Type visitType(Type t, Symbol sym) {
214 return null;
215 }
217 @Override
218 public Type visitClassType(ClassType t, Symbol sym) {
219 if (t.tsym == sym)
220 return t;
221 Type base = asSuper(sym.type, t.tsym);
222 if (base == null)
223 return null;
224 ListBuffer<Type> from = new ListBuffer<Type>();
225 ListBuffer<Type> to = new ListBuffer<Type>();
226 try {
227 adapt(base, t, from, to);
228 } catch (AdaptFailure ex) {
229 return null;
230 }
231 Type res = subst(sym.type, from.toList(), to.toList());
232 if (!isSubtype(res, t))
233 return null;
234 ListBuffer<Type> openVars = new ListBuffer<Type>();
235 for (List<Type> l = sym.type.allparams();
236 l.nonEmpty(); l = l.tail)
237 if (res.contains(l.head) && !t.contains(l.head))
238 openVars.append(l.head);
239 if (openVars.nonEmpty()) {
240 if (t.isRaw()) {
241 // The subtype of a raw type is raw
242 res = erasure(res);
243 } else {
244 // Unbound type arguments default to ?
245 List<Type> opens = openVars.toList();
246 ListBuffer<Type> qs = new ListBuffer<Type>();
247 for (List<Type> iter = opens; iter.nonEmpty(); iter = iter.tail) {
248 qs.append(new WildcardType(syms.objectType, BoundKind.UNBOUND, syms.boundClass, (TypeVar) iter.head));
249 }
250 res = subst(res, opens, qs.toList());
251 }
252 }
253 return res;
254 }
256 @Override
257 public Type visitErrorType(ErrorType t, Symbol sym) {
258 return t;
259 }
260 };
261 // </editor-fold>
263 // <editor-fold defaultstate="collapsed" desc="isConvertible">
264 /**
265 * Is t a subtype of or convertiable via boxing/unboxing
266 * convertions to s?
267 */
268 public boolean isConvertible(Type t, Type s, Warner warn) {
269 boolean tPrimitive = t.isPrimitive();
270 boolean sPrimitive = s.isPrimitive();
271 if (tPrimitive == sPrimitive)
272 return isSubtypeUnchecked(t, s, warn);
273 if (!allowBoxing) return false;
274 return tPrimitive
275 ? isSubtype(boxedClass(t).type, s)
276 : isSubtype(unboxedType(t), s);
277 }
279 /**
280 * Is t a subtype of or convertiable via boxing/unboxing
281 * convertions to s?
282 */
283 public boolean isConvertible(Type t, Type s) {
284 return isConvertible(t, s, Warner.noWarnings);
285 }
286 // </editor-fold>
288 // <editor-fold defaultstate="collapsed" desc="isSubtype">
289 /**
290 * Is t an unchecked subtype of s?
291 */
292 public boolean isSubtypeUnchecked(Type t, Type s) {
293 return isSubtypeUnchecked(t, s, Warner.noWarnings);
294 }
295 /**
296 * Is t an unchecked subtype of s?
297 */
298 public boolean isSubtypeUnchecked(Type t, Type s, Warner warn) {
299 if (t.tag == ARRAY && s.tag == ARRAY) {
300 return (((ArrayType)t).elemtype.tag <= lastBaseTag)
301 ? isSameType(elemtype(t), elemtype(s))
302 : isSubtypeUnchecked(elemtype(t), elemtype(s), warn);
303 } else if (isSubtype(t, s)) {
304 return true;
305 }
306 else if (t.tag == TYPEVAR) {
307 return isSubtypeUnchecked(t.getUpperBound(), s, warn);
308 }
309 else if (s.tag == UNDETVAR) {
310 UndetVar uv = (UndetVar)s;
311 if (uv.inst != null)
312 return isSubtypeUnchecked(t, uv.inst, warn);
313 }
314 else if (!s.isRaw()) {
315 Type t2 = asSuper(t, s.tsym);
316 if (t2 != null && t2.isRaw()) {
317 if (isReifiable(s))
318 warn.silentUnchecked();
319 else
320 warn.warnUnchecked();
321 return true;
322 }
323 }
324 return false;
325 }
327 /**
328 * Is t a subtype of s?<br>
329 * (not defined for Method and ForAll types)
330 */
331 final public boolean isSubtype(Type t, Type s) {
332 return isSubtype(t, s, true);
333 }
334 final public boolean isSubtypeNoCapture(Type t, Type s) {
335 return isSubtype(t, s, false);
336 }
337 public boolean isSubtype(Type t, Type s, boolean capture) {
338 if (t == s)
339 return true;
341 if (s.tag >= firstPartialTag)
342 return isSuperType(s, t);
344 Type lower = lowerBound(s);
345 if (s != lower)
346 return isSubtype(capture ? capture(t) : t, lower, false);
348 return isSubtype.visit(capture ? capture(t) : t, s);
349 }
350 // where
351 private TypeRelation isSubtype = new TypeRelation()
352 {
353 public Boolean visitType(Type t, Type s) {
354 switch (t.tag) {
355 case BYTE: case CHAR:
356 return (t.tag == s.tag ||
357 t.tag + 2 <= s.tag && s.tag <= DOUBLE);
358 case SHORT: case INT: case LONG: case FLOAT: case DOUBLE:
359 return t.tag <= s.tag && s.tag <= DOUBLE;
360 case BOOLEAN: case VOID:
361 return t.tag == s.tag;
362 case TYPEVAR:
363 return isSubtypeNoCapture(t.getUpperBound(), s);
364 case BOT:
365 return
366 s.tag == BOT || s.tag == CLASS ||
367 s.tag == ARRAY || s.tag == TYPEVAR;
368 case NONE:
369 return false;
370 default:
371 throw new AssertionError("isSubtype " + t.tag);
372 }
373 }
375 private Set<TypePair> cache = new HashSet<TypePair>();
377 private boolean containsTypeRecursive(Type t, Type s) {
378 TypePair pair = new TypePair(t, s);
379 if (cache.add(pair)) {
380 try {
381 return containsType(t.getTypeArguments(),
382 s.getTypeArguments());
383 } finally {
384 cache.remove(pair);
385 }
386 } else {
387 return containsType(t.getTypeArguments(),
388 rewriteSupers(s).getTypeArguments());
389 }
390 }
392 private Type rewriteSupers(Type t) {
393 if (!t.isParameterized())
394 return t;
395 ListBuffer<Type> from = lb();
396 ListBuffer<Type> to = lb();
397 adaptSelf(t, from, to);
398 if (from.isEmpty())
399 return t;
400 ListBuffer<Type> rewrite = lb();
401 boolean changed = false;
402 for (Type orig : to.toList()) {
403 Type s = rewriteSupers(orig);
404 if (s.isSuperBound() && !s.isExtendsBound()) {
405 s = new WildcardType(syms.objectType,
406 BoundKind.UNBOUND,
407 syms.boundClass);
408 changed = true;
409 } else if (s != orig) {
410 s = new WildcardType(upperBound(s),
411 BoundKind.EXTENDS,
412 syms.boundClass);
413 changed = true;
414 }
415 rewrite.append(s);
416 }
417 if (changed)
418 return subst(t.tsym.type, from.toList(), rewrite.toList());
419 else
420 return t;
421 }
423 @Override
424 public Boolean visitClassType(ClassType t, Type s) {
425 Type sup = asSuper(t, s.tsym);
426 return sup != null
427 && sup.tsym == s.tsym
428 // You're not allowed to write
429 // Vector<Object> vec = new Vector<String>();
430 // But with wildcards you can write
431 // Vector<? extends Object> vec = new Vector<String>();
432 // which means that subtype checking must be done
433 // here instead of same-type checking (via containsType).
434 && (!s.isParameterized() || containsTypeRecursive(s, sup))
435 && isSubtypeNoCapture(sup.getEnclosingType(),
436 s.getEnclosingType());
437 }
439 @Override
440 public Boolean visitArrayType(ArrayType t, Type s) {
441 if (s.tag == ARRAY) {
442 if (t.elemtype.tag <= lastBaseTag)
443 return isSameType(t.elemtype, elemtype(s));
444 else
445 return isSubtypeNoCapture(t.elemtype, elemtype(s));
446 }
448 if (s.tag == CLASS) {
449 Name sname = s.tsym.getQualifiedName();
450 return sname == names.java_lang_Object
451 || sname == names.java_lang_Cloneable
452 || sname == names.java_io_Serializable;
453 }
455 return false;
456 }
458 @Override
459 public Boolean visitUndetVar(UndetVar t, Type s) {
460 //todo: test against origin needed? or replace with substitution?
461 if (t == s || t.qtype == s || s.tag == ERROR || s.tag == UNKNOWN)
462 return true;
464 if (t.inst != null)
465 return isSubtypeNoCapture(t.inst, s); // TODO: ", warn"?
467 t.hibounds = t.hibounds.prepend(s);
468 return true;
469 }
471 @Override
472 public Boolean visitErrorType(ErrorType t, Type s) {
473 return true;
474 }
475 };
477 /**
478 * Is t a subtype of every type in given list `ts'?<br>
479 * (not defined for Method and ForAll types)<br>
480 * Allows unchecked conversions.
481 */
482 public boolean isSubtypeUnchecked(Type t, List<Type> ts, Warner warn) {
483 for (List<Type> l = ts; l.nonEmpty(); l = l.tail)
484 if (!isSubtypeUnchecked(t, l.head, warn))
485 return false;
486 return true;
487 }
489 /**
490 * Are corresponding elements of ts subtypes of ss? If lists are
491 * of different length, return false.
492 */
493 public boolean isSubtypes(List<Type> ts, List<Type> ss) {
494 while (ts.tail != null && ss.tail != null
495 /*inlined: ts.nonEmpty() && ss.nonEmpty()*/ &&
496 isSubtype(ts.head, ss.head)) {
497 ts = ts.tail;
498 ss = ss.tail;
499 }
500 return ts.tail == null && ss.tail == null;
501 /*inlined: ts.isEmpty() && ss.isEmpty();*/
502 }
504 /**
505 * Are corresponding elements of ts subtypes of ss, allowing
506 * unchecked conversions? If lists are of different length,
507 * return false.
508 **/
509 public boolean isSubtypesUnchecked(List<Type> ts, List<Type> ss, Warner warn) {
510 while (ts.tail != null && ss.tail != null
511 /*inlined: ts.nonEmpty() && ss.nonEmpty()*/ &&
512 isSubtypeUnchecked(ts.head, ss.head, warn)) {
513 ts = ts.tail;
514 ss = ss.tail;
515 }
516 return ts.tail == null && ss.tail == null;
517 /*inlined: ts.isEmpty() && ss.isEmpty();*/
518 }
519 // </editor-fold>
521 // <editor-fold defaultstate="collapsed" desc="isSuperType">
522 /**
523 * Is t a supertype of s?
524 */
525 public boolean isSuperType(Type t, Type s) {
526 switch (t.tag) {
527 case ERROR:
528 return true;
529 case UNDETVAR: {
530 UndetVar undet = (UndetVar)t;
531 if (t == s ||
532 undet.qtype == s ||
533 s.tag == ERROR ||
534 s.tag == BOT) return true;
535 if (undet.inst != null)
536 return isSubtype(s, undet.inst);
537 undet.lobounds = undet.lobounds.prepend(s);
538 return true;
539 }
540 default:
541 return isSubtype(s, t);
542 }
543 }
544 // </editor-fold>
546 // <editor-fold defaultstate="collapsed" desc="isSameType">
547 /**
548 * Are corresponding elements of the lists the same type? If
549 * lists are of different length, return false.
550 */
551 public boolean isSameTypes(List<Type> ts, List<Type> ss) {
552 while (ts.tail != null && ss.tail != null
553 /*inlined: ts.nonEmpty() && ss.nonEmpty()*/ &&
554 isSameType(ts.head, ss.head)) {
555 ts = ts.tail;
556 ss = ss.tail;
557 }
558 return ts.tail == null && ss.tail == null;
559 /*inlined: ts.isEmpty() && ss.isEmpty();*/
560 }
562 /**
563 * Is t the same type as s?
564 */
565 public boolean isSameType(Type t, Type s) {
566 return isSameType.visit(t, s);
567 }
568 // where
569 private TypeRelation isSameType = new TypeRelation() {
571 public Boolean visitType(Type t, Type s) {
572 if (t == s)
573 return true;
575 if (s.tag >= firstPartialTag)
576 return visit(s, t);
578 switch (t.tag) {
579 case BYTE: case CHAR: case SHORT: case INT: case LONG: case FLOAT:
580 case DOUBLE: case BOOLEAN: case VOID: case BOT: case NONE:
581 return t.tag == s.tag;
582 case TYPEVAR:
583 return s.isSuperBound()
584 && !s.isExtendsBound()
585 && visit(t, upperBound(s));
586 default:
587 throw new AssertionError("isSameType " + t.tag);
588 }
589 }
591 @Override
592 public Boolean visitWildcardType(WildcardType t, Type s) {
593 if (s.tag >= firstPartialTag)
594 return visit(s, t);
595 else
596 return false;
597 }
599 @Override
600 public Boolean visitClassType(ClassType t, Type s) {
601 if (t == s)
602 return true;
604 if (s.tag >= firstPartialTag)
605 return visit(s, t);
607 if (s.isSuperBound() && !s.isExtendsBound())
608 return visit(t, upperBound(s)) && visit(t, lowerBound(s));
610 if (t.isCompound() && s.isCompound()) {
611 if (!visit(supertype(t), supertype(s)))
612 return false;
614 HashSet<SingletonType> set = new HashSet<SingletonType>();
615 for (Type x : interfaces(t))
616 set.add(new SingletonType(x));
617 for (Type x : interfaces(s)) {
618 if (!set.remove(new SingletonType(x)))
619 return false;
620 }
621 return (set.size() == 0);
622 }
623 return t.tsym == s.tsym
624 && visit(t.getEnclosingType(), s.getEnclosingType())
625 && containsTypeEquivalent(t.getTypeArguments(), s.getTypeArguments());
626 }
628 @Override
629 public Boolean visitArrayType(ArrayType t, Type s) {
630 if (t == s)
631 return true;
633 if (s.tag >= firstPartialTag)
634 return visit(s, t);
636 return s.tag == ARRAY
637 && containsTypeEquivalent(t.elemtype, elemtype(s));
638 }
640 @Override
641 public Boolean visitMethodType(MethodType t, Type s) {
642 // isSameType for methods does not take thrown
643 // exceptions into account!
644 return hasSameArgs(t, s) && visit(t.getReturnType(), s.getReturnType());
645 }
647 @Override
648 public Boolean visitPackageType(PackageType t, Type s) {
649 return t == s;
650 }
652 @Override
653 public Boolean visitForAll(ForAll t, Type s) {
654 if (s.tag != FORALL)
655 return false;
657 ForAll forAll = (ForAll)s;
658 return hasSameBounds(t, forAll)
659 && visit(t.qtype, subst(forAll.qtype, forAll.tvars, t.tvars));
660 }
662 @Override
663 public Boolean visitUndetVar(UndetVar t, Type s) {
664 if (s.tag == WILDCARD)
665 // FIXME, this might be leftovers from before capture conversion
666 return false;
668 if (t == s || t.qtype == s || s.tag == ERROR || s.tag == UNKNOWN)
669 return true;
671 if (t.inst != null)
672 return visit(t.inst, s);
674 t.inst = fromUnknownFun.apply(s);
675 for (List<Type> l = t.lobounds; l.nonEmpty(); l = l.tail) {
676 if (!isSubtype(l.head, t.inst))
677 return false;
678 }
679 for (List<Type> l = t.hibounds; l.nonEmpty(); l = l.tail) {
680 if (!isSubtype(t.inst, l.head))
681 return false;
682 }
683 return true;
684 }
686 @Override
687 public Boolean visitErrorType(ErrorType t, Type s) {
688 return true;
689 }
690 };
691 // </editor-fold>
693 // <editor-fold defaultstate="collapsed" desc="fromUnknownFun">
694 /**
695 * A mapping that turns all unknown types in this type to fresh
696 * unknown variables.
697 */
698 public Mapping fromUnknownFun = new Mapping("fromUnknownFun") {
699 public Type apply(Type t) {
700 if (t.tag == UNKNOWN) return new UndetVar(t);
701 else return t.map(this);
702 }
703 };
704 // </editor-fold>
706 // <editor-fold defaultstate="collapsed" desc="Contains Type">
707 public boolean containedBy(Type t, Type s) {
708 switch (t.tag) {
709 case UNDETVAR:
710 if (s.tag == WILDCARD) {
711 UndetVar undetvar = (UndetVar)t;
713 // Because of wildcard capture, s must be on the left
714 // hand side of an assignment. Furthermore, t is an
715 // underconstrained type variable, for example, one
716 // that is only used in the return type of a method.
717 // If the type variable is truly underconstrained, it
718 // cannot have any low bounds:
719 assert undetvar.lobounds.isEmpty() : undetvar;
721 undetvar.inst = glb(upperBound(s), undetvar.inst);
722 return true;
723 } else {
724 return isSameType(t, s);
725 }
726 case ERROR:
727 return true;
728 default:
729 return containsType(s, t);
730 }
731 }
733 boolean containsType(List<Type> ts, List<Type> ss) {
734 while (ts.nonEmpty() && ss.nonEmpty()
735 && containsType(ts.head, ss.head)) {
736 ts = ts.tail;
737 ss = ss.tail;
738 }
739 return ts.isEmpty() && ss.isEmpty();
740 }
742 /**
743 * Check if t contains s.
744 *
745 * <p>T contains S if:
746 *
747 * <p>{@code L(T) <: L(S) && U(S) <: U(T)}
748 *
749 * <p>This relation is only used by ClassType.isSubtype(), that
750 * is,
751 *
752 * <p>{@code C<S> <: C<T> if T contains S.}
753 *
754 * <p>Because of F-bounds, this relation can lead to infinite
755 * recursion. Thus we must somehow break that recursion. Notice
756 * that containsType() is only called from ClassType.isSubtype().
757 * Since the arguments have already been checked against their
758 * bounds, we know:
759 *
760 * <p>{@code U(S) <: U(T) if T is "super" bound (U(T) *is* the bound)}
761 *
762 * <p>{@code L(T) <: L(S) if T is "extends" bound (L(T) is bottom)}
763 *
764 * @param t a type
765 * @param s a type
766 */
767 public boolean containsType(Type t, Type s) {
768 return containsType.visit(t, s);
769 }
770 // where
771 private TypeRelation containsType = new TypeRelation() {
773 private Type U(Type t) {
774 while (t.tag == WILDCARD) {
775 WildcardType w = (WildcardType)t;
776 if (w.isSuperBound())
777 return w.bound == null ? syms.objectType : w.bound.bound;
778 else
779 t = w.type;
780 }
781 return t;
782 }
784 private Type L(Type t) {
785 while (t.tag == WILDCARD) {
786 WildcardType w = (WildcardType)t;
787 if (w.isExtendsBound())
788 return syms.botType;
789 else
790 t = w.type;
791 }
792 return t;
793 }
795 public Boolean visitType(Type t, Type s) {
796 if (s.tag >= firstPartialTag)
797 return containedBy(s, t);
798 else
799 return isSameType(t, s);
800 }
802 void debugContainsType(WildcardType t, Type s) {
803 System.err.println();
804 System.err.format(" does %s contain %s?%n", t, s);
805 System.err.format(" %s U(%s) <: U(%s) %s = %s%n",
806 upperBound(s), s, t, U(t),
807 t.isSuperBound()
808 || isSubtypeNoCapture(upperBound(s), U(t)));
809 System.err.format(" %s L(%s) <: L(%s) %s = %s%n",
810 L(t), t, s, lowerBound(s),
811 t.isExtendsBound()
812 || isSubtypeNoCapture(L(t), lowerBound(s)));
813 System.err.println();
814 }
816 @Override
817 public Boolean visitWildcardType(WildcardType t, Type s) {
818 if (s.tag >= firstPartialTag)
819 return containedBy(s, t);
820 else {
821 // debugContainsType(t, s);
822 return isSameWildcard(t, s)
823 || isCaptureOf(s, t)
824 || ((t.isExtendsBound() || isSubtypeNoCapture(L(t), lowerBound(s))) &&
825 (t.isSuperBound() || isSubtypeNoCapture(upperBound(s), U(t))));
826 }
827 }
829 @Override
830 public Boolean visitUndetVar(UndetVar t, Type s) {
831 if (s.tag != WILDCARD)
832 return isSameType(t, s);
833 else
834 return false;
835 }
837 @Override
838 public Boolean visitErrorType(ErrorType t, Type s) {
839 return true;
840 }
841 };
843 public boolean isCaptureOf(Type s, WildcardType t) {
844 if (s.tag != TYPEVAR || !((TypeVar)s).isCaptured())
845 return false;
846 return isSameWildcard(t, ((CapturedType)s).wildcard);
847 }
849 public boolean isSameWildcard(WildcardType t, Type s) {
850 if (s.tag != WILDCARD)
851 return false;
852 WildcardType w = (WildcardType)s;
853 return w.kind == t.kind && w.type == t.type;
854 }
856 public boolean containsTypeEquivalent(List<Type> ts, List<Type> ss) {
857 while (ts.nonEmpty() && ss.nonEmpty()
858 && containsTypeEquivalent(ts.head, ss.head)) {
859 ts = ts.tail;
860 ss = ss.tail;
861 }
862 return ts.isEmpty() && ss.isEmpty();
863 }
864 // </editor-fold>
866 // <editor-fold defaultstate="collapsed" desc="isCastable">
867 public boolean isCastable(Type t, Type s) {
868 return isCastable(t, s, Warner.noWarnings);
869 }
871 /**
872 * Is t is castable to s?<br>
873 * s is assumed to be an erased type.<br>
874 * (not defined for Method and ForAll types).
875 */
876 public boolean isCastable(Type t, Type s, Warner warn) {
877 if (t == s)
878 return true;
880 if (t.isPrimitive() != s.isPrimitive())
881 return allowBoxing && isConvertible(t, s, warn);
883 if (warn != warnStack.head) {
884 try {
885 warnStack = warnStack.prepend(warn);
886 return isCastable.visit(t, s);
887 } finally {
888 warnStack = warnStack.tail;
889 }
890 } else {
891 return isCastable.visit(t, s);
892 }
893 }
894 // where
895 private TypeRelation isCastable = new TypeRelation() {
897 public Boolean visitType(Type t, Type s) {
898 if (s.tag == ERROR)
899 return true;
901 switch (t.tag) {
902 case BYTE: case CHAR: case SHORT: case INT: case LONG: case FLOAT:
903 case DOUBLE:
904 return s.tag <= DOUBLE;
905 case BOOLEAN:
906 return s.tag == BOOLEAN;
907 case VOID:
908 return false;
909 case BOT:
910 return isSubtype(t, s);
911 default:
912 throw new AssertionError();
913 }
914 }
916 @Override
917 public Boolean visitWildcardType(WildcardType t, Type s) {
918 return isCastable(upperBound(t), s, warnStack.head);
919 }
921 @Override
922 public Boolean visitClassType(ClassType t, Type s) {
923 if (s.tag == ERROR || s.tag == BOT)
924 return true;
926 if (s.tag == TYPEVAR) {
927 if (isCastable(s.getUpperBound(), t, Warner.noWarnings)) {
928 warnStack.head.warnUnchecked();
929 return true;
930 } else {
931 return false;
932 }
933 }
935 if (t.isCompound()) {
936 if (!visit(supertype(t), s))
937 return false;
938 for (Type intf : interfaces(t)) {
939 if (!visit(intf, s))
940 return false;
941 }
942 return true;
943 }
945 if (s.isCompound()) {
946 // call recursively to reuse the above code
947 return visitClassType((ClassType)s, t);
948 }
950 if (s.tag == CLASS || s.tag == ARRAY) {
951 boolean upcast;
952 if ((upcast = isSubtype(erasure(t), erasure(s)))
953 || isSubtype(erasure(s), erasure(t))) {
954 if (!upcast && s.tag == ARRAY) {
955 if (!isReifiable(s))
956 warnStack.head.warnUnchecked();
957 return true;
958 } else if (s.isRaw()) {
959 return true;
960 } else if (t.isRaw()) {
961 if (!isUnbounded(s))
962 warnStack.head.warnUnchecked();
963 return true;
964 }
965 // Assume |a| <: |b|
966 final Type a = upcast ? t : s;
967 final Type b = upcast ? s : t;
968 final boolean HIGH = true;
969 final boolean LOW = false;
970 final boolean DONT_REWRITE_TYPEVARS = false;
971 Type aHigh = rewriteQuantifiers(a, HIGH, DONT_REWRITE_TYPEVARS);
972 Type aLow = rewriteQuantifiers(a, LOW, DONT_REWRITE_TYPEVARS);
973 Type bHigh = rewriteQuantifiers(b, HIGH, DONT_REWRITE_TYPEVARS);
974 Type bLow = rewriteQuantifiers(b, LOW, DONT_REWRITE_TYPEVARS);
975 Type lowSub = asSub(bLow, aLow.tsym);
976 Type highSub = (lowSub == null) ? null : asSub(bHigh, aHigh.tsym);
977 if (highSub == null) {
978 final boolean REWRITE_TYPEVARS = true;
979 aHigh = rewriteQuantifiers(a, HIGH, REWRITE_TYPEVARS);
980 aLow = rewriteQuantifiers(a, LOW, REWRITE_TYPEVARS);
981 bHigh = rewriteQuantifiers(b, HIGH, REWRITE_TYPEVARS);
982 bLow = rewriteQuantifiers(b, LOW, REWRITE_TYPEVARS);
983 lowSub = asSub(bLow, aLow.tsym);
984 highSub = (lowSub == null) ? null : asSub(bHigh, aHigh.tsym);
985 }
986 if (highSub != null) {
987 assert a.tsym == highSub.tsym && a.tsym == lowSub.tsym
988 : a.tsym + " != " + highSub.tsym + " != " + lowSub.tsym;
989 if (!disjointTypes(aHigh.getTypeArguments(), highSub.getTypeArguments())
990 && !disjointTypes(aHigh.getTypeArguments(), lowSub.getTypeArguments())
991 && !disjointTypes(aLow.getTypeArguments(), highSub.getTypeArguments())
992 && !disjointTypes(aLow.getTypeArguments(), lowSub.getTypeArguments())) {
993 if (upcast ? giveWarning(a, highSub) || giveWarning(a, lowSub)
994 : giveWarning(highSub, a) || giveWarning(lowSub, a))
995 warnStack.head.warnUnchecked();
996 return true;
997 }
998 }
999 if (isReifiable(s))
1000 return isSubtypeUnchecked(a, b);
1001 else
1002 return isSubtypeUnchecked(a, b, warnStack.head);
1003 }
1005 // Sidecast
1006 if (s.tag == CLASS) {
1007 if ((s.tsym.flags() & INTERFACE) != 0) {
1008 return ((t.tsym.flags() & FINAL) == 0)
1009 ? sideCast(t, s, warnStack.head)
1010 : sideCastFinal(t, s, warnStack.head);
1011 } else if ((t.tsym.flags() & INTERFACE) != 0) {
1012 return ((s.tsym.flags() & FINAL) == 0)
1013 ? sideCast(t, s, warnStack.head)
1014 : sideCastFinal(t, s, warnStack.head);
1015 } else {
1016 // unrelated class types
1017 return false;
1018 }
1019 }
1020 }
1021 return false;
1022 }
1024 @Override
1025 public Boolean visitArrayType(ArrayType t, Type s) {
1026 switch (s.tag) {
1027 case ERROR:
1028 case BOT:
1029 return true;
1030 case TYPEVAR:
1031 if (isCastable(s, t, Warner.noWarnings)) {
1032 warnStack.head.warnUnchecked();
1033 return true;
1034 } else {
1035 return false;
1036 }
1037 case CLASS:
1038 return isSubtype(t, s);
1039 case ARRAY:
1040 if (elemtype(t).tag <= lastBaseTag) {
1041 return elemtype(t).tag == elemtype(s).tag;
1042 } else {
1043 return visit(elemtype(t), elemtype(s));
1044 }
1045 default:
1046 return false;
1047 }
1048 }
1050 @Override
1051 public Boolean visitTypeVar(TypeVar t, Type s) {
1052 switch (s.tag) {
1053 case ERROR:
1054 case BOT:
1055 return true;
1056 case TYPEVAR:
1057 if (isSubtype(t, s)) {
1058 return true;
1059 } else if (isCastable(t.bound, s, Warner.noWarnings)) {
1060 warnStack.head.warnUnchecked();
1061 return true;
1062 } else {
1063 return false;
1064 }
1065 default:
1066 return isCastable(t.bound, s, warnStack.head);
1067 }
1068 }
1070 @Override
1071 public Boolean visitErrorType(ErrorType t, Type s) {
1072 return true;
1073 }
1074 };
1075 // </editor-fold>
1077 // <editor-fold defaultstate="collapsed" desc="disjointTypes">
1078 public boolean disjointTypes(List<Type> ts, List<Type> ss) {
1079 while (ts.tail != null && ss.tail != null) {
1080 if (disjointType(ts.head, ss.head)) return true;
1081 ts = ts.tail;
1082 ss = ss.tail;
1083 }
1084 return false;
1085 }
1087 /**
1088 * Two types or wildcards are considered disjoint if it can be
1089 * proven that no type can be contained in both. It is
1090 * conservative in that it is allowed to say that two types are
1091 * not disjoint, even though they actually are.
1092 *
1093 * The type C<X> is castable to C<Y> exactly if X and Y are not
1094 * disjoint.
1095 */
1096 public boolean disjointType(Type t, Type s) {
1097 return disjointType.visit(t, s);
1098 }
1099 // where
1100 private TypeRelation disjointType = new TypeRelation() {
1102 private Set<TypePair> cache = new HashSet<TypePair>();
1104 public Boolean visitType(Type t, Type s) {
1105 if (s.tag == WILDCARD)
1106 return visit(s, t);
1107 else
1108 return notSoftSubtypeRecursive(t, s) || notSoftSubtypeRecursive(s, t);
1109 }
1111 private boolean isCastableRecursive(Type t, Type s) {
1112 TypePair pair = new TypePair(t, s);
1113 if (cache.add(pair)) {
1114 try {
1115 return Types.this.isCastable(t, s);
1116 } finally {
1117 cache.remove(pair);
1118 }
1119 } else {
1120 return true;
1121 }
1122 }
1124 private boolean notSoftSubtypeRecursive(Type t, Type s) {
1125 TypePair pair = new TypePair(t, s);
1126 if (cache.add(pair)) {
1127 try {
1128 return Types.this.notSoftSubtype(t, s);
1129 } finally {
1130 cache.remove(pair);
1131 }
1132 } else {
1133 return false;
1134 }
1135 }
1137 @Override
1138 public Boolean visitWildcardType(WildcardType t, Type s) {
1139 if (t.isUnbound())
1140 return false;
1142 if (s.tag != WILDCARD) {
1143 if (t.isExtendsBound())
1144 return notSoftSubtypeRecursive(s, t.type);
1145 else // isSuperBound()
1146 return notSoftSubtypeRecursive(t.type, s);
1147 }
1149 if (s.isUnbound())
1150 return false;
1152 if (t.isExtendsBound()) {
1153 if (s.isExtendsBound())
1154 return !isCastableRecursive(t.type, upperBound(s));
1155 else if (s.isSuperBound())
1156 return notSoftSubtypeRecursive(lowerBound(s), t.type);
1157 } else if (t.isSuperBound()) {
1158 if (s.isExtendsBound())
1159 return notSoftSubtypeRecursive(t.type, upperBound(s));
1160 }
1161 return false;
1162 }
1163 };
1164 // </editor-fold>
1166 // <editor-fold defaultstate="collapsed" desc="lowerBoundArgtypes">
1167 /**
1168 * Returns the lower bounds of the formals of a method.
1169 */
1170 public List<Type> lowerBoundArgtypes(Type t) {
1171 return map(t.getParameterTypes(), lowerBoundMapping);
1172 }
1173 private final Mapping lowerBoundMapping = new Mapping("lowerBound") {
1174 public Type apply(Type t) {
1175 return lowerBound(t);
1176 }
1177 };
1178 // </editor-fold>
1180 // <editor-fold defaultstate="collapsed" desc="notSoftSubtype">
1181 /**
1182 * This relation answers the question: is impossible that
1183 * something of type `t' can be a subtype of `s'? This is
1184 * different from the question "is `t' not a subtype of `s'?"
1185 * when type variables are involved: Integer is not a subtype of T
1186 * where <T extends Number> but it is not true that Integer cannot
1187 * possibly be a subtype of T.
1188 */
1189 public boolean notSoftSubtype(Type t, Type s) {
1190 if (t == s) return false;
1191 if (t.tag == TYPEVAR) {
1192 TypeVar tv = (TypeVar) t;
1193 if (s.tag == TYPEVAR)
1194 s = s.getUpperBound();
1195 return !isCastable(tv.bound,
1196 s,
1197 Warner.noWarnings);
1198 }
1199 if (s.tag != WILDCARD)
1200 s = upperBound(s);
1201 if (s.tag == TYPEVAR)
1202 s = s.getUpperBound();
1203 return !isSubtype(t, s);
1204 }
1205 // </editor-fold>
1207 // <editor-fold defaultstate="collapsed" desc="isReifiable">
1208 public boolean isReifiable(Type t) {
1209 return isReifiable.visit(t);
1210 }
1211 // where
1212 private UnaryVisitor<Boolean> isReifiable = new UnaryVisitor<Boolean>() {
1214 public Boolean visitType(Type t, Void ignored) {
1215 return true;
1216 }
1218 @Override
1219 public Boolean visitClassType(ClassType t, Void ignored) {
1220 if (!t.isParameterized())
1221 return true;
1223 for (Type param : t.allparams()) {
1224 if (!param.isUnbound())
1225 return false;
1226 }
1227 return true;
1228 }
1230 @Override
1231 public Boolean visitArrayType(ArrayType t, Void ignored) {
1232 return visit(t.elemtype);
1233 }
1235 @Override
1236 public Boolean visitTypeVar(TypeVar t, Void ignored) {
1237 return false;
1238 }
1239 };
1240 // </editor-fold>
1242 // <editor-fold defaultstate="collapsed" desc="Array Utils">
1243 public boolean isArray(Type t) {
1244 while (t.tag == WILDCARD)
1245 t = upperBound(t);
1246 return t.tag == ARRAY;
1247 }
1249 /**
1250 * The element type of an array.
1251 */
1252 public Type elemtype(Type t) {
1253 switch (t.tag) {
1254 case WILDCARD:
1255 return elemtype(upperBound(t));
1256 case ARRAY:
1257 return ((ArrayType)t).elemtype;
1258 case FORALL:
1259 return elemtype(((ForAll)t).qtype);
1260 case ERROR:
1261 return t;
1262 default:
1263 return null;
1264 }
1265 }
1267 /**
1268 * Mapping to take element type of an arraytype
1269 */
1270 private Mapping elemTypeFun = new Mapping ("elemTypeFun") {
1271 public Type apply(Type t) { return elemtype(t); }
1272 };
1274 /**
1275 * The number of dimensions of an array type.
1276 */
1277 public int dimensions(Type t) {
1278 int result = 0;
1279 while (t.tag == ARRAY) {
1280 result++;
1281 t = elemtype(t);
1282 }
1283 return result;
1284 }
1285 // </editor-fold>
1287 // <editor-fold defaultstate="collapsed" desc="asSuper">
1288 /**
1289 * Return the (most specific) base type of t that starts with the
1290 * given symbol. If none exists, return null.
1291 *
1292 * @param t a type
1293 * @param sym a symbol
1294 */
1295 public Type asSuper(Type t, Symbol sym) {
1296 return asSuper.visit(t, sym);
1297 }
1298 // where
1299 private SimpleVisitor<Type,Symbol> asSuper = new SimpleVisitor<Type,Symbol>() {
1301 public Type visitType(Type t, Symbol sym) {
1302 return null;
1303 }
1305 @Override
1306 public Type visitClassType(ClassType t, Symbol sym) {
1307 if (t.tsym == sym)
1308 return t;
1310 Type st = supertype(t);
1311 if (st.tag == CLASS || st.tag == TYPEVAR || st.tag == ERROR) {
1312 Type x = asSuper(st, sym);
1313 if (x != null)
1314 return x;
1315 }
1316 if ((sym.flags() & INTERFACE) != 0) {
1317 for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail) {
1318 Type x = asSuper(l.head, sym);
1319 if (x != null)
1320 return x;
1321 }
1322 }
1323 return null;
1324 }
1326 @Override
1327 public Type visitArrayType(ArrayType t, Symbol sym) {
1328 return isSubtype(t, sym.type) ? sym.type : null;
1329 }
1331 @Override
1332 public Type visitTypeVar(TypeVar t, Symbol sym) {
1333 if (t.tsym == sym)
1334 return t;
1335 else
1336 return asSuper(t.bound, sym);
1337 }
1339 @Override
1340 public Type visitErrorType(ErrorType t, Symbol sym) {
1341 return t;
1342 }
1343 };
1345 /**
1346 * Return the base type of t or any of its outer types that starts
1347 * with the given symbol. If none exists, return null.
1348 *
1349 * @param t a type
1350 * @param sym a symbol
1351 */
1352 public Type asOuterSuper(Type t, Symbol sym) {
1353 switch (t.tag) {
1354 case CLASS:
1355 do {
1356 Type s = asSuper(t, sym);
1357 if (s != null) return s;
1358 t = t.getEnclosingType();
1359 } while (t.tag == CLASS);
1360 return null;
1361 case ARRAY:
1362 return isSubtype(t, sym.type) ? sym.type : null;
1363 case TYPEVAR:
1364 return asSuper(t, sym);
1365 case ERROR:
1366 return t;
1367 default:
1368 return null;
1369 }
1370 }
1372 /**
1373 * Return the base type of t or any of its enclosing types that
1374 * starts with the given symbol. If none exists, return null.
1375 *
1376 * @param t a type
1377 * @param sym a symbol
1378 */
1379 public Type asEnclosingSuper(Type t, Symbol sym) {
1380 switch (t.tag) {
1381 case CLASS:
1382 do {
1383 Type s = asSuper(t, sym);
1384 if (s != null) return s;
1385 Type outer = t.getEnclosingType();
1386 t = (outer.tag == CLASS) ? outer :
1387 (t.tsym.owner.enclClass() != null) ? t.tsym.owner.enclClass().type :
1388 Type.noType;
1389 } while (t.tag == CLASS);
1390 return null;
1391 case ARRAY:
1392 return isSubtype(t, sym.type) ? sym.type : null;
1393 case TYPEVAR:
1394 return asSuper(t, sym);
1395 case ERROR:
1396 return t;
1397 default:
1398 return null;
1399 }
1400 }
1401 // </editor-fold>
1403 // <editor-fold defaultstate="collapsed" desc="memberType">
1404 /**
1405 * The type of given symbol, seen as a member of t.
1406 *
1407 * @param t a type
1408 * @param sym a symbol
1409 */
1410 public Type memberType(Type t, Symbol sym) {
1411 return (sym.flags() & STATIC) != 0
1412 ? sym.type
1413 : memberType.visit(t, sym);
1414 }
1415 // where
1416 private SimpleVisitor<Type,Symbol> memberType = new SimpleVisitor<Type,Symbol>() {
1418 public Type visitType(Type t, Symbol sym) {
1419 return sym.type;
1420 }
1422 @Override
1423 public Type visitWildcardType(WildcardType t, Symbol sym) {
1424 return memberType(upperBound(t), sym);
1425 }
1427 @Override
1428 public Type visitClassType(ClassType t, Symbol sym) {
1429 Symbol owner = sym.owner;
1430 long flags = sym.flags();
1431 if (((flags & STATIC) == 0) && owner.type.isParameterized()) {
1432 Type base = asOuterSuper(t, owner);
1433 if (base != null) {
1434 List<Type> ownerParams = owner.type.allparams();
1435 List<Type> baseParams = base.allparams();
1436 if (ownerParams.nonEmpty()) {
1437 if (baseParams.isEmpty()) {
1438 // then base is a raw type
1439 return erasure(sym.type);
1440 } else {
1441 return subst(sym.type, ownerParams, baseParams);
1442 }
1443 }
1444 }
1445 }
1446 return sym.type;
1447 }
1449 @Override
1450 public Type visitTypeVar(TypeVar t, Symbol sym) {
1451 return memberType(t.bound, sym);
1452 }
1454 @Override
1455 public Type visitErrorType(ErrorType t, Symbol sym) {
1456 return t;
1457 }
1458 };
1459 // </editor-fold>
1461 // <editor-fold defaultstate="collapsed" desc="isAssignable">
1462 public boolean isAssignable(Type t, Type s) {
1463 return isAssignable(t, s, Warner.noWarnings);
1464 }
1466 /**
1467 * Is t assignable to s?<br>
1468 * Equivalent to subtype except for constant values and raw
1469 * types.<br>
1470 * (not defined for Method and ForAll types)
1471 */
1472 public boolean isAssignable(Type t, Type s, Warner warn) {
1473 if (t.tag == ERROR)
1474 return true;
1475 if (t.tag <= INT && t.constValue() != null) {
1476 int value = ((Number)t.constValue()).intValue();
1477 switch (s.tag) {
1478 case BYTE:
1479 if (Byte.MIN_VALUE <= value && value <= Byte.MAX_VALUE)
1480 return true;
1481 break;
1482 case CHAR:
1483 if (Character.MIN_VALUE <= value && value <= Character.MAX_VALUE)
1484 return true;
1485 break;
1486 case SHORT:
1487 if (Short.MIN_VALUE <= value && value <= Short.MAX_VALUE)
1488 return true;
1489 break;
1490 case INT:
1491 return true;
1492 case CLASS:
1493 switch (unboxedType(s).tag) {
1494 case BYTE:
1495 case CHAR:
1496 case SHORT:
1497 return isAssignable(t, unboxedType(s), warn);
1498 }
1499 break;
1500 }
1501 }
1502 return isConvertible(t, s, warn);
1503 }
1504 // </editor-fold>
1506 // <editor-fold defaultstate="collapsed" desc="erasure">
1507 /**
1508 * The erasure of t {@code |t|} -- the type that results when all
1509 * type parameters in t are deleted.
1510 */
1511 public Type erasure(Type t) {
1512 return erasure(t, false);
1513 }
1514 //where
1515 private Type erasure(Type t, boolean recurse) {
1516 if (t.tag <= lastBaseTag)
1517 return t; /* fast special case */
1518 else
1519 return erasure.visit(t, recurse);
1520 }
1521 // where
1522 private SimpleVisitor<Type, Boolean> erasure = new SimpleVisitor<Type, Boolean>() {
1523 public Type visitType(Type t, Boolean recurse) {
1524 if (t.tag <= lastBaseTag)
1525 return t; /*fast special case*/
1526 else
1527 return t.map(recurse ? erasureRecFun : erasureFun);
1528 }
1530 @Override
1531 public Type visitWildcardType(WildcardType t, Boolean recurse) {
1532 return erasure(upperBound(t), recurse);
1533 }
1535 @Override
1536 public Type visitClassType(ClassType t, Boolean recurse) {
1537 Type erased = t.tsym.erasure(Types.this);
1538 if (recurse) {
1539 erased = new ErasedClassType(erased.getEnclosingType(),erased.tsym);
1540 }
1541 return erased;
1542 }
1544 @Override
1545 public Type visitTypeVar(TypeVar t, Boolean recurse) {
1546 return erasure(t.bound, recurse);
1547 }
1549 @Override
1550 public Type visitErrorType(ErrorType t, Boolean recurse) {
1551 return t;
1552 }
1553 };
1555 private Mapping erasureFun = new Mapping ("erasure") {
1556 public Type apply(Type t) { return erasure(t); }
1557 };
1559 private Mapping erasureRecFun = new Mapping ("erasureRecursive") {
1560 public Type apply(Type t) { return erasureRecursive(t); }
1561 };
1563 public List<Type> erasure(List<Type> ts) {
1564 return Type.map(ts, erasureFun);
1565 }
1567 public Type erasureRecursive(Type t) {
1568 return erasure(t, true);
1569 }
1571 public List<Type> erasureRecursive(List<Type> ts) {
1572 return Type.map(ts, erasureRecFun);
1573 }
1574 // </editor-fold>
1576 // <editor-fold defaultstate="collapsed" desc="makeCompoundType">
1577 /**
1578 * Make a compound type from non-empty list of types
1579 *
1580 * @param bounds the types from which the compound type is formed
1581 * @param supertype is objectType if all bounds are interfaces,
1582 * null otherwise.
1583 */
1584 public Type makeCompoundType(List<Type> bounds,
1585 Type supertype) {
1586 ClassSymbol bc =
1587 new ClassSymbol(ABSTRACT|PUBLIC|SYNTHETIC|COMPOUND|ACYCLIC,
1588 Type.moreInfo
1589 ? names.fromString(bounds.toString())
1590 : names.empty,
1591 syms.noSymbol);
1592 if (bounds.head.tag == TYPEVAR)
1593 // error condition, recover
1594 bc.erasure_field = syms.objectType;
1595 else
1596 bc.erasure_field = erasure(bounds.head);
1597 bc.members_field = new Scope(bc);
1598 ClassType bt = (ClassType)bc.type;
1599 bt.allparams_field = List.nil();
1600 if (supertype != null) {
1601 bt.supertype_field = supertype;
1602 bt.interfaces_field = bounds;
1603 } else {
1604 bt.supertype_field = bounds.head;
1605 bt.interfaces_field = bounds.tail;
1606 }
1607 assert bt.supertype_field.tsym.completer != null
1608 || !bt.supertype_field.isInterface()
1609 : bt.supertype_field;
1610 return bt;
1611 }
1613 /**
1614 * Same as {@link #makeCompoundType(List,Type)}, except that the
1615 * second parameter is computed directly. Note that this might
1616 * cause a symbol completion. Hence, this version of
1617 * makeCompoundType may not be called during a classfile read.
1618 */
1619 public Type makeCompoundType(List<Type> bounds) {
1620 Type supertype = (bounds.head.tsym.flags() & INTERFACE) != 0 ?
1621 supertype(bounds.head) : null;
1622 return makeCompoundType(bounds, supertype);
1623 }
1625 /**
1626 * A convenience wrapper for {@link #makeCompoundType(List)}; the
1627 * arguments are converted to a list and passed to the other
1628 * method. Note that this might cause a symbol completion.
1629 * Hence, this version of makeCompoundType may not be called
1630 * during a classfile read.
1631 */
1632 public Type makeCompoundType(Type bound1, Type bound2) {
1633 return makeCompoundType(List.of(bound1, bound2));
1634 }
1635 // </editor-fold>
1637 // <editor-fold defaultstate="collapsed" desc="supertype">
1638 public Type supertype(Type t) {
1639 return supertype.visit(t);
1640 }
1641 // where
1642 private UnaryVisitor<Type> supertype = new UnaryVisitor<Type>() {
1644 public Type visitType(Type t, Void ignored) {
1645 // A note on wildcards: there is no good way to
1646 // determine a supertype for a super bounded wildcard.
1647 return null;
1648 }
1650 @Override
1651 public Type visitClassType(ClassType t, Void ignored) {
1652 if (t.supertype_field == null) {
1653 Type supertype = ((ClassSymbol)t.tsym).getSuperclass();
1654 // An interface has no superclass; its supertype is Object.
1655 if (t.isInterface())
1656 supertype = ((ClassType)t.tsym.type).supertype_field;
1657 if (t.supertype_field == null) {
1658 List<Type> actuals = classBound(t).allparams();
1659 List<Type> formals = t.tsym.type.allparams();
1660 if (t.hasErasedSupertypes()) {
1661 t.supertype_field = erasureRecursive(supertype);
1662 } else if (formals.nonEmpty()) {
1663 t.supertype_field = subst(supertype, formals, actuals);
1664 }
1665 else {
1666 t.supertype_field = supertype;
1667 }
1668 }
1669 }
1670 return t.supertype_field;
1671 }
1673 /**
1674 * The supertype is always a class type. If the type
1675 * variable's bounds start with a class type, this is also
1676 * the supertype. Otherwise, the supertype is
1677 * java.lang.Object.
1678 */
1679 @Override
1680 public Type visitTypeVar(TypeVar t, Void ignored) {
1681 if (t.bound.tag == TYPEVAR ||
1682 (!t.bound.isCompound() && !t.bound.isInterface())) {
1683 return t.bound;
1684 } else {
1685 return supertype(t.bound);
1686 }
1687 }
1689 @Override
1690 public Type visitArrayType(ArrayType t, Void ignored) {
1691 if (t.elemtype.isPrimitive() || isSameType(t.elemtype, syms.objectType))
1692 return arraySuperType();
1693 else
1694 return new ArrayType(supertype(t.elemtype), t.tsym);
1695 }
1697 @Override
1698 public Type visitErrorType(ErrorType t, Void ignored) {
1699 return t;
1700 }
1701 };
1702 // </editor-fold>
1704 // <editor-fold defaultstate="collapsed" desc="interfaces">
1705 /**
1706 * Return the interfaces implemented by this class.
1707 */
1708 public List<Type> interfaces(Type t) {
1709 return interfaces.visit(t);
1710 }
1711 // where
1712 private UnaryVisitor<List<Type>> interfaces = new UnaryVisitor<List<Type>>() {
1714 public List<Type> visitType(Type t, Void ignored) {
1715 return List.nil();
1716 }
1718 @Override
1719 public List<Type> visitClassType(ClassType t, Void ignored) {
1720 if (t.interfaces_field == null) {
1721 List<Type> interfaces = ((ClassSymbol)t.tsym).getInterfaces();
1722 if (t.interfaces_field == null) {
1723 // If t.interfaces_field is null, then t must
1724 // be a parameterized type (not to be confused
1725 // with a generic type declaration).
1726 // Terminology:
1727 // Parameterized type: List<String>
1728 // Generic type declaration: class List<E> { ... }
1729 // So t corresponds to List<String> and
1730 // t.tsym.type corresponds to List<E>.
1731 // The reason t must be parameterized type is
1732 // that completion will happen as a side
1733 // effect of calling
1734 // ClassSymbol.getInterfaces. Since
1735 // t.interfaces_field is null after
1736 // completion, we can assume that t is not the
1737 // type of a class/interface declaration.
1738 assert t != t.tsym.type : t.toString();
1739 List<Type> actuals = t.allparams();
1740 List<Type> formals = t.tsym.type.allparams();
1741 if (t.hasErasedSupertypes()) {
1742 t.interfaces_field = erasureRecursive(interfaces);
1743 } else if (formals.nonEmpty()) {
1744 t.interfaces_field =
1745 upperBounds(subst(interfaces, formals, actuals));
1746 }
1747 else {
1748 t.interfaces_field = interfaces;
1749 }
1750 }
1751 }
1752 return t.interfaces_field;
1753 }
1755 @Override
1756 public List<Type> visitTypeVar(TypeVar t, Void ignored) {
1757 if (t.bound.isCompound())
1758 return interfaces(t.bound);
1760 if (t.bound.isInterface())
1761 return List.of(t.bound);
1763 return List.nil();
1764 }
1765 };
1766 // </editor-fold>
1768 // <editor-fold defaultstate="collapsed" desc="isDerivedRaw">
1769 Map<Type,Boolean> isDerivedRawCache = new HashMap<Type,Boolean>();
1771 public boolean isDerivedRaw(Type t) {
1772 Boolean result = isDerivedRawCache.get(t);
1773 if (result == null) {
1774 result = isDerivedRawInternal(t);
1775 isDerivedRawCache.put(t, result);
1776 }
1777 return result;
1778 }
1780 public boolean isDerivedRawInternal(Type t) {
1781 if (t.isErroneous())
1782 return false;
1783 return
1784 t.isRaw() ||
1785 supertype(t) != null && isDerivedRaw(supertype(t)) ||
1786 isDerivedRaw(interfaces(t));
1787 }
1789 public boolean isDerivedRaw(List<Type> ts) {
1790 List<Type> l = ts;
1791 while (l.nonEmpty() && !isDerivedRaw(l.head)) l = l.tail;
1792 return l.nonEmpty();
1793 }
1794 // </editor-fold>
1796 // <editor-fold defaultstate="collapsed" desc="setBounds">
1797 /**
1798 * Set the bounds field of the given type variable to reflect a
1799 * (possibly multiple) list of bounds.
1800 * @param t a type variable
1801 * @param bounds the bounds, must be nonempty
1802 * @param supertype is objectType if all bounds are interfaces,
1803 * null otherwise.
1804 */
1805 public void setBounds(TypeVar t, List<Type> bounds, Type supertype) {
1806 if (bounds.tail.isEmpty())
1807 t.bound = bounds.head;
1808 else
1809 t.bound = makeCompoundType(bounds, supertype);
1810 t.rank_field = -1;
1811 }
1813 /**
1814 * Same as {@link #setBounds(Type.TypeVar,List,Type)}, except that
1815 * third parameter is computed directly. Note that this test
1816 * might cause a symbol completion. Hence, this version of
1817 * setBounds may not be called during a classfile read.
1818 */
1819 public void setBounds(TypeVar t, List<Type> bounds) {
1820 Type supertype = (bounds.head.tsym.flags() & INTERFACE) != 0 ?
1821 supertype(bounds.head) : null;
1822 setBounds(t, bounds, supertype);
1823 t.rank_field = -1;
1824 }
1825 // </editor-fold>
1827 // <editor-fold defaultstate="collapsed" desc="getBounds">
1828 /**
1829 * Return list of bounds of the given type variable.
1830 */
1831 public List<Type> getBounds(TypeVar t) {
1832 if (t.bound.isErroneous() || !t.bound.isCompound())
1833 return List.of(t.bound);
1834 else if ((erasure(t).tsym.flags() & INTERFACE) == 0)
1835 return interfaces(t).prepend(supertype(t));
1836 else
1837 // No superclass was given in bounds.
1838 // In this case, supertype is Object, erasure is first interface.
1839 return interfaces(t);
1840 }
1841 // </editor-fold>
1843 // <editor-fold defaultstate="collapsed" desc="classBound">
1844 /**
1845 * If the given type is a (possibly selected) type variable,
1846 * return the bounding class of this type, otherwise return the
1847 * type itself.
1848 */
1849 public Type classBound(Type t) {
1850 return classBound.visit(t);
1851 }
1852 // where
1853 private UnaryVisitor<Type> classBound = new UnaryVisitor<Type>() {
1855 public Type visitType(Type t, Void ignored) {
1856 return t;
1857 }
1859 @Override
1860 public Type visitClassType(ClassType t, Void ignored) {
1861 Type outer1 = classBound(t.getEnclosingType());
1862 if (outer1 != t.getEnclosingType())
1863 return new ClassType(outer1, t.getTypeArguments(), t.tsym);
1864 else
1865 return t;
1866 }
1868 @Override
1869 public Type visitTypeVar(TypeVar t, Void ignored) {
1870 return classBound(supertype(t));
1871 }
1873 @Override
1874 public Type visitErrorType(ErrorType t, Void ignored) {
1875 return t;
1876 }
1877 };
1878 // </editor-fold>
1880 // <editor-fold defaultstate="collapsed" desc="sub signature / override equivalence">
1881 /**
1882 * Returns true iff the first signature is a <em>sub
1883 * signature</em> of the other. This is <b>not</b> an equivalence
1884 * relation.
1885 *
1886 * @see "The Java Language Specification, Third Ed. (8.4.2)."
1887 * @see #overrideEquivalent(Type t, Type s)
1888 * @param t first signature (possibly raw).
1889 * @param s second signature (could be subjected to erasure).
1890 * @return true if t is a sub signature of s.
1891 */
1892 public boolean isSubSignature(Type t, Type s) {
1893 return hasSameArgs(t, s) || hasSameArgs(t, erasure(s));
1894 }
1896 /**
1897 * Returns true iff these signatures are related by <em>override
1898 * equivalence</em>. This is the natural extension of
1899 * isSubSignature to an equivalence relation.
1900 *
1901 * @see "The Java Language Specification, Third Ed. (8.4.2)."
1902 * @see #isSubSignature(Type t, Type s)
1903 * @param t a signature (possible raw, could be subjected to
1904 * erasure).
1905 * @param s a signature (possible raw, could be subjected to
1906 * erasure).
1907 * @return true if either argument is a sub signature of the other.
1908 */
1909 public boolean overrideEquivalent(Type t, Type s) {
1910 return hasSameArgs(t, s) ||
1911 hasSameArgs(t, erasure(s)) || hasSameArgs(erasure(t), s);
1912 }
1914 /**
1915 * Does t have the same arguments as s? It is assumed that both
1916 * types are (possibly polymorphic) method types. Monomorphic
1917 * method types "have the same arguments", if their argument lists
1918 * are equal. Polymorphic method types "have the same arguments",
1919 * if they have the same arguments after renaming all type
1920 * variables of one to corresponding type variables in the other,
1921 * where correspondence is by position in the type parameter list.
1922 */
1923 public boolean hasSameArgs(Type t, Type s) {
1924 return hasSameArgs.visit(t, s);
1925 }
1926 // where
1927 private TypeRelation hasSameArgs = new TypeRelation() {
1929 public Boolean visitType(Type t, Type s) {
1930 throw new AssertionError();
1931 }
1933 @Override
1934 public Boolean visitMethodType(MethodType t, Type s) {
1935 return s.tag == METHOD
1936 && containsTypeEquivalent(t.argtypes, s.getParameterTypes());
1937 }
1939 @Override
1940 public Boolean visitForAll(ForAll t, Type s) {
1941 if (s.tag != FORALL)
1942 return false;
1944 ForAll forAll = (ForAll)s;
1945 return hasSameBounds(t, forAll)
1946 && visit(t.qtype, subst(forAll.qtype, forAll.tvars, t.tvars));
1947 }
1949 @Override
1950 public Boolean visitErrorType(ErrorType t, Type s) {
1951 return false;
1952 }
1953 };
1954 // </editor-fold>
1956 // <editor-fold defaultstate="collapsed" desc="subst">
1957 public List<Type> subst(List<Type> ts,
1958 List<Type> from,
1959 List<Type> to) {
1960 return new Subst(from, to).subst(ts);
1961 }
1963 /**
1964 * Substitute all occurrences of a type in `from' with the
1965 * corresponding type in `to' in 't'. Match lists `from' and `to'
1966 * from the right: If lists have different length, discard leading
1967 * elements of the longer list.
1968 */
1969 public Type subst(Type t, List<Type> from, List<Type> to) {
1970 return new Subst(from, to).subst(t);
1971 }
1973 private class Subst extends UnaryVisitor<Type> {
1974 List<Type> from;
1975 List<Type> to;
1977 public Subst(List<Type> from, List<Type> to) {
1978 int fromLength = from.length();
1979 int toLength = to.length();
1980 while (fromLength > toLength) {
1981 fromLength--;
1982 from = from.tail;
1983 }
1984 while (fromLength < toLength) {
1985 toLength--;
1986 to = to.tail;
1987 }
1988 this.from = from;
1989 this.to = to;
1990 }
1992 Type subst(Type t) {
1993 if (from.tail == null)
1994 return t;
1995 else
1996 return visit(t);
1997 }
1999 List<Type> subst(List<Type> ts) {
2000 if (from.tail == null)
2001 return ts;
2002 boolean wild = false;
2003 if (ts.nonEmpty() && from.nonEmpty()) {
2004 Type head1 = subst(ts.head);
2005 List<Type> tail1 = subst(ts.tail);
2006 if (head1 != ts.head || tail1 != ts.tail)
2007 return tail1.prepend(head1);
2008 }
2009 return ts;
2010 }
2012 public Type visitType(Type t, Void ignored) {
2013 return t;
2014 }
2016 @Override
2017 public Type visitMethodType(MethodType t, Void ignored) {
2018 List<Type> argtypes = subst(t.argtypes);
2019 Type restype = subst(t.restype);
2020 List<Type> thrown = subst(t.thrown);
2021 if (argtypes == t.argtypes &&
2022 restype == t.restype &&
2023 thrown == t.thrown)
2024 return t;
2025 else
2026 return new MethodType(argtypes, restype, thrown, t.tsym);
2027 }
2029 @Override
2030 public Type visitTypeVar(TypeVar t, Void ignored) {
2031 for (List<Type> from = this.from, to = this.to;
2032 from.nonEmpty();
2033 from = from.tail, to = to.tail) {
2034 if (t == from.head) {
2035 return to.head.withTypeVar(t);
2036 }
2037 }
2038 return t;
2039 }
2041 @Override
2042 public Type visitClassType(ClassType t, Void ignored) {
2043 if (!t.isCompound()) {
2044 List<Type> typarams = t.getTypeArguments();
2045 List<Type> typarams1 = subst(typarams);
2046 Type outer = t.getEnclosingType();
2047 Type outer1 = subst(outer);
2048 if (typarams1 == typarams && outer1 == outer)
2049 return t;
2050 else
2051 return new ClassType(outer1, typarams1, t.tsym);
2052 } else {
2053 Type st = subst(supertype(t));
2054 List<Type> is = upperBounds(subst(interfaces(t)));
2055 if (st == supertype(t) && is == interfaces(t))
2056 return t;
2057 else
2058 return makeCompoundType(is.prepend(st));
2059 }
2060 }
2062 @Override
2063 public Type visitWildcardType(WildcardType t, Void ignored) {
2064 Type bound = t.type;
2065 if (t.kind != BoundKind.UNBOUND)
2066 bound = subst(bound);
2067 if (bound == t.type) {
2068 return t;
2069 } else {
2070 if (t.isExtendsBound() && bound.isExtendsBound())
2071 bound = upperBound(bound);
2072 return new WildcardType(bound, t.kind, syms.boundClass, t.bound);
2073 }
2074 }
2076 @Override
2077 public Type visitArrayType(ArrayType t, Void ignored) {
2078 Type elemtype = subst(t.elemtype);
2079 if (elemtype == t.elemtype)
2080 return t;
2081 else
2082 return new ArrayType(upperBound(elemtype), t.tsym);
2083 }
2085 @Override
2086 public Type visitForAll(ForAll t, Void ignored) {
2087 List<Type> tvars1 = substBounds(t.tvars, from, to);
2088 Type qtype1 = subst(t.qtype);
2089 if (tvars1 == t.tvars && qtype1 == t.qtype) {
2090 return t;
2091 } else if (tvars1 == t.tvars) {
2092 return new ForAll(tvars1, qtype1);
2093 } else {
2094 return new ForAll(tvars1, Types.this.subst(qtype1, t.tvars, tvars1));
2095 }
2096 }
2098 @Override
2099 public Type visitErrorType(ErrorType t, Void ignored) {
2100 return t;
2101 }
2102 }
2104 public List<Type> substBounds(List<Type> tvars,
2105 List<Type> from,
2106 List<Type> to) {
2107 if (tvars.isEmpty())
2108 return tvars;
2109 if (tvars.tail.isEmpty())
2110 // fast common case
2111 return List.<Type>of(substBound((TypeVar)tvars.head, from, to));
2112 ListBuffer<Type> newBoundsBuf = lb();
2113 boolean changed = false;
2114 // calculate new bounds
2115 for (Type t : tvars) {
2116 TypeVar tv = (TypeVar) t;
2117 Type bound = subst(tv.bound, from, to);
2118 if (bound != tv.bound)
2119 changed = true;
2120 newBoundsBuf.append(bound);
2121 }
2122 if (!changed)
2123 return tvars;
2124 ListBuffer<Type> newTvars = lb();
2125 // create new type variables without bounds
2126 for (Type t : tvars) {
2127 newTvars.append(new TypeVar(t.tsym, null, syms.botType));
2128 }
2129 // the new bounds should use the new type variables in place
2130 // of the old
2131 List<Type> newBounds = newBoundsBuf.toList();
2132 from = tvars;
2133 to = newTvars.toList();
2134 for (; !newBounds.isEmpty(); newBounds = newBounds.tail) {
2135 newBounds.head = subst(newBounds.head, from, to);
2136 }
2137 newBounds = newBoundsBuf.toList();
2138 // set the bounds of new type variables to the new bounds
2139 for (Type t : newTvars.toList()) {
2140 TypeVar tv = (TypeVar) t;
2141 tv.bound = newBounds.head;
2142 newBounds = newBounds.tail;
2143 }
2144 return newTvars.toList();
2145 }
2147 public TypeVar substBound(TypeVar t, List<Type> from, List<Type> to) {
2148 Type bound1 = subst(t.bound, from, to);
2149 if (bound1 == t.bound)
2150 return t;
2151 else
2152 return new TypeVar(t.tsym, bound1, syms.botType);
2153 }
2154 // </editor-fold>
2156 // <editor-fold defaultstate="collapsed" desc="hasSameBounds">
2157 /**
2158 * Does t have the same bounds for quantified variables as s?
2159 */
2160 boolean hasSameBounds(ForAll t, ForAll s) {
2161 List<Type> l1 = t.tvars;
2162 List<Type> l2 = s.tvars;
2163 while (l1.nonEmpty() && l2.nonEmpty() &&
2164 isSameType(l1.head.getUpperBound(),
2165 subst(l2.head.getUpperBound(),
2166 s.tvars,
2167 t.tvars))) {
2168 l1 = l1.tail;
2169 l2 = l2.tail;
2170 }
2171 return l1.isEmpty() && l2.isEmpty();
2172 }
2173 // </editor-fold>
2175 // <editor-fold defaultstate="collapsed" desc="newInstances">
2176 /** Create new vector of type variables from list of variables
2177 * changing all recursive bounds from old to new list.
2178 */
2179 public List<Type> newInstances(List<Type> tvars) {
2180 List<Type> tvars1 = Type.map(tvars, newInstanceFun);
2181 for (List<Type> l = tvars1; l.nonEmpty(); l = l.tail) {
2182 TypeVar tv = (TypeVar) l.head;
2183 tv.bound = subst(tv.bound, tvars, tvars1);
2184 }
2185 return tvars1;
2186 }
2187 static private Mapping newInstanceFun = new Mapping("newInstanceFun") {
2188 public Type apply(Type t) { return new TypeVar(t.tsym, t.getUpperBound(), t.getLowerBound()); }
2189 };
2190 // </editor-fold>
2192 // <editor-fold defaultstate="collapsed" desc="createErrorType">
2193 public Type createErrorType(Type originalType) {
2194 return new ErrorType(originalType, syms.errSymbol);
2195 }
2197 public Type createErrorType(ClassSymbol c, Type originalType) {
2198 return new ErrorType(c, originalType);
2199 }
2201 public Type createErrorType(Name name, TypeSymbol container, Type originalType) {
2202 return new ErrorType(name, container, originalType);
2203 }
2204 // </editor-fold>
2206 // <editor-fold defaultstate="collapsed" desc="rank">
2207 /**
2208 * The rank of a class is the length of the longest path between
2209 * the class and java.lang.Object in the class inheritance
2210 * graph. Undefined for all but reference types.
2211 */
2212 public int rank(Type t) {
2213 switch(t.tag) {
2214 case CLASS: {
2215 ClassType cls = (ClassType)t;
2216 if (cls.rank_field < 0) {
2217 Name fullname = cls.tsym.getQualifiedName();
2218 if (fullname == names.java_lang_Object)
2219 cls.rank_field = 0;
2220 else {
2221 int r = rank(supertype(cls));
2222 for (List<Type> l = interfaces(cls);
2223 l.nonEmpty();
2224 l = l.tail) {
2225 if (rank(l.head) > r)
2226 r = rank(l.head);
2227 }
2228 cls.rank_field = r + 1;
2229 }
2230 }
2231 return cls.rank_field;
2232 }
2233 case TYPEVAR: {
2234 TypeVar tvar = (TypeVar)t;
2235 if (tvar.rank_field < 0) {
2236 int r = rank(supertype(tvar));
2237 for (List<Type> l = interfaces(tvar);
2238 l.nonEmpty();
2239 l = l.tail) {
2240 if (rank(l.head) > r) r = rank(l.head);
2241 }
2242 tvar.rank_field = r + 1;
2243 }
2244 return tvar.rank_field;
2245 }
2246 case ERROR:
2247 return 0;
2248 default:
2249 throw new AssertionError();
2250 }
2251 }
2252 // </editor-fold>
2254 // <editor-fold defaultstate="collapsed" desc="printType">
2255 /**
2256 * Visitor for generating a string representation of a given type
2257 * accordingly to a given locale
2258 */
2259 public String toString(Type t, Locale locale) {
2260 return typePrinter.visit(t, locale);
2261 }
2262 // where
2263 private TypePrinter typePrinter = new TypePrinter();
2265 public class TypePrinter extends DefaultTypeVisitor<String, Locale> {
2267 public String visit(List<Type> ts, Locale locale) {
2268 ListBuffer<String> sbuf = lb();
2269 for (Type t : ts) {
2270 sbuf.append(visit(t, locale));
2271 }
2272 return sbuf.toList().toString();
2273 }
2275 @Override
2276 public String visitCapturedType(CapturedType t, Locale locale) {
2277 return messages.getLocalizedString("compiler.misc.type.captureof",
2278 (t.hashCode() & 0xFFFFFFFFL) % Type.CapturedType.PRIME,
2279 visit(t.wildcard, locale));
2280 }
2282 @Override
2283 public String visitForAll(ForAll t, Locale locale) {
2284 return "<" + visit(t.tvars, locale) + ">" + visit(t.qtype, locale);
2285 }
2287 @Override
2288 public String visitUndetVar(UndetVar t, Locale locale) {
2289 if (t.inst != null) {
2290 return visit(t.inst, locale);
2291 } else {
2292 return visit(t.qtype, locale) + "?";
2293 }
2294 }
2296 @Override
2297 public String visitArrayType(ArrayType t, Locale locale) {
2298 return visit(t.elemtype, locale) + "[]";
2299 }
2301 @Override
2302 public String visitClassType(ClassType t, Locale locale) {
2303 StringBuffer buf = new StringBuffer();
2304 if (t.getEnclosingType().tag == CLASS && t.tsym.owner.kind == Kinds.TYP) {
2305 buf.append(visit(t.getEnclosingType(), locale));
2306 buf.append(".");
2307 buf.append(className(t, false, locale));
2308 } else {
2309 buf.append(className(t, true, locale));
2310 }
2311 if (t.getTypeArguments().nonEmpty()) {
2312 buf.append('<');
2313 buf.append(visit(t.getTypeArguments(), locale));
2314 buf.append(">");
2315 }
2316 return buf.toString();
2317 }
2319 @Override
2320 public String visitMethodType(MethodType t, Locale locale) {
2321 return "(" + printMethodArgs(t.argtypes, false, locale) + ")" + visit(t.restype, locale);
2322 }
2324 @Override
2325 public String visitPackageType(PackageType t, Locale locale) {
2326 return t.tsym.getQualifiedName().toString();
2327 }
2329 @Override
2330 public String visitWildcardType(WildcardType t, Locale locale) {
2331 StringBuffer s = new StringBuffer();
2332 s.append(t.kind);
2333 if (t.kind != UNBOUND) {
2334 s.append(visit(t.type, locale));
2335 }
2336 return s.toString();
2337 }
2340 public String visitType(Type t, Locale locale) {
2341 String s = (t.tsym == null || t.tsym.name == null)
2342 ? messages.getLocalizedString("compiler.misc.type.none")
2343 : t.tsym.name.toString();
2344 return s;
2345 }
2347 protected String className(ClassType t, boolean longform, Locale locale) {
2348 Symbol sym = t.tsym;
2349 if (sym.name.length() == 0 && (sym.flags() & COMPOUND) != 0) {
2350 StringBuffer s = new StringBuffer(visit(supertype(t), locale));
2351 for (List<Type> is = interfaces(t); is.nonEmpty(); is = is.tail) {
2352 s.append("&");
2353 s.append(visit(is.head, locale));
2354 }
2355 return s.toString();
2356 } else if (sym.name.length() == 0) {
2357 String s;
2358 ClassType norm = (ClassType) t.tsym.type;
2359 if (norm == null) {
2360 s = getLocalizedString(locale, "compiler.misc.anonymous.class", (Object) null);
2361 } else if (interfaces(norm).nonEmpty()) {
2362 s = getLocalizedString(locale, "compiler.misc.anonymous.class",
2363 visit(interfaces(norm).head, locale));
2364 } else {
2365 s = getLocalizedString(locale, "compiler.misc.anonymous.class",
2366 visit(supertype(norm), locale));
2367 }
2368 return s;
2369 } else if (longform) {
2370 return sym.getQualifiedName().toString();
2371 } else {
2372 return sym.name.toString();
2373 }
2374 }
2376 protected String printMethodArgs(List<Type> args, boolean varArgs, Locale locale) {
2377 if (!varArgs) {
2378 return visit(args, locale);
2379 } else {
2380 StringBuffer buf = new StringBuffer();
2381 while (args.tail.nonEmpty()) {
2382 buf.append(visit(args.head, locale));
2383 args = args.tail;
2384 buf.append(',');
2385 }
2386 if (args.head.tag == ARRAY) {
2387 buf.append(visit(((ArrayType) args.head).elemtype, locale));
2388 buf.append("...");
2389 } else {
2390 buf.append(visit(args.head, locale));
2391 }
2392 return buf.toString();
2393 }
2394 }
2396 protected String getLocalizedString(Locale locale, String key, Object... args) {
2397 return messages.getLocalizedString(key, args);
2398 }
2399 };
2400 // </editor-fold>
2402 // <editor-fold defaultstate="collapsed" desc="printSymbol">
2403 /**
2404 * Visitor for generating a string representation of a given symbol
2405 * accordingly to a given locale
2406 */
2407 public String toString(Symbol t, Locale locale) {
2408 return symbolPrinter.visit(t, locale);
2409 }
2410 // where
2411 private SymbolPrinter symbolPrinter = new SymbolPrinter();
2413 public class SymbolPrinter extends DefaultSymbolVisitor<String, Locale> {
2415 @Override
2416 public String visitClassSymbol(ClassSymbol sym, Locale locale) {
2417 return sym.name.isEmpty()
2418 ? getLocalizedString(locale, "compiler.misc.anonymous.class", sym.flatname)
2419 : sym.fullname.toString();
2420 }
2422 @Override
2423 public String visitMethodSymbol(MethodSymbol s, Locale locale) {
2424 if ((s.flags() & BLOCK) != 0) {
2425 return s.owner.name.toString();
2426 } else {
2427 String ms = (s.name == names.init)
2428 ? s.owner.name.toString()
2429 : s.name.toString();
2430 if (s.type != null) {
2431 if (s.type.tag == FORALL) {
2432 ms = "<" + typePrinter.visit(s.type.getTypeArguments(), locale) + ">" + ms;
2433 }
2434 ms += "(" + typePrinter.printMethodArgs(
2435 s.type.getParameterTypes(),
2436 (s.flags() & VARARGS) != 0,
2437 locale) + ")";
2438 }
2439 return ms;
2440 }
2441 }
2443 @Override
2444 public String visitOperatorSymbol(OperatorSymbol s, Locale locale) {
2445 return visitMethodSymbol(s, locale);
2446 }
2448 @Override
2449 public String visitPackageSymbol(PackageSymbol s, Locale locale) {
2450 return s.name.isEmpty()
2451 ? getLocalizedString(locale, "compiler.misc.unnamed.package")
2452 : s.fullname.toString();
2453 }
2455 @Override
2456 public String visitSymbol(Symbol s, Locale locale) {
2457 return s.name.toString();
2458 }
2460 public String visit(List<Symbol> ts, Locale locale) {
2461 ListBuffer<String> sbuf = lb();
2462 for (Symbol t : ts) {
2463 sbuf.append(visit(t, locale));
2464 }
2465 return sbuf.toList().toString();
2466 }
2468 protected String getLocalizedString(Locale locale, String key, Object... args) {
2469 return messages.getLocalizedString(key, args);
2470 }
2471 };
2472 // </editor-fold>
2474 // <editor-fold defaultstate="collapsed" desc="toString">
2475 /**
2476 * This toString is slightly more descriptive than the one on Type.
2477 *
2478 * @deprecated Types.toString(Type t, Locale l) provides better support
2479 * for localization
2480 */
2481 @Deprecated
2482 public String toString(Type t) {
2483 if (t.tag == FORALL) {
2484 ForAll forAll = (ForAll)t;
2485 return typaramsString(forAll.tvars) + forAll.qtype;
2486 }
2487 return "" + t;
2488 }
2489 // where
2490 private String typaramsString(List<Type> tvars) {
2491 StringBuffer s = new StringBuffer();
2492 s.append('<');
2493 boolean first = true;
2494 for (Type t : tvars) {
2495 if (!first) s.append(", ");
2496 first = false;
2497 appendTyparamString(((TypeVar)t), s);
2498 }
2499 s.append('>');
2500 return s.toString();
2501 }
2502 private void appendTyparamString(TypeVar t, StringBuffer buf) {
2503 buf.append(t);
2504 if (t.bound == null ||
2505 t.bound.tsym.getQualifiedName() == names.java_lang_Object)
2506 return;
2507 buf.append(" extends "); // Java syntax; no need for i18n
2508 Type bound = t.bound;
2509 if (!bound.isCompound()) {
2510 buf.append(bound);
2511 } else if ((erasure(t).tsym.flags() & INTERFACE) == 0) {
2512 buf.append(supertype(t));
2513 for (Type intf : interfaces(t)) {
2514 buf.append('&');
2515 buf.append(intf);
2516 }
2517 } else {
2518 // No superclass was given in bounds.
2519 // In this case, supertype is Object, erasure is first interface.
2520 boolean first = true;
2521 for (Type intf : interfaces(t)) {
2522 if (!first) buf.append('&');
2523 first = false;
2524 buf.append(intf);
2525 }
2526 }
2527 }
2528 // </editor-fold>
2530 // <editor-fold defaultstate="collapsed" desc="Determining least upper bounds of types">
2531 /**
2532 * A cache for closures.
2533 *
2534 * <p>A closure is a list of all the supertypes and interfaces of
2535 * a class or interface type, ordered by ClassSymbol.precedes
2536 * (that is, subclasses come first, arbitrary but fixed
2537 * otherwise).
2538 */
2539 private Map<Type,List<Type>> closureCache = new HashMap<Type,List<Type>>();
2541 /**
2542 * Returns the closure of a class or interface type.
2543 */
2544 public List<Type> closure(Type t) {
2545 List<Type> cl = closureCache.get(t);
2546 if (cl == null) {
2547 Type st = supertype(t);
2548 if (!t.isCompound()) {
2549 if (st.tag == CLASS) {
2550 cl = insert(closure(st), t);
2551 } else if (st.tag == TYPEVAR) {
2552 cl = closure(st).prepend(t);
2553 } else {
2554 cl = List.of(t);
2555 }
2556 } else {
2557 cl = closure(supertype(t));
2558 }
2559 for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail)
2560 cl = union(cl, closure(l.head));
2561 closureCache.put(t, cl);
2562 }
2563 return cl;
2564 }
2566 /**
2567 * Insert a type in a closure
2568 */
2569 public List<Type> insert(List<Type> cl, Type t) {
2570 if (cl.isEmpty() || t.tsym.precedes(cl.head.tsym, this)) {
2571 return cl.prepend(t);
2572 } else if (cl.head.tsym.precedes(t.tsym, this)) {
2573 return insert(cl.tail, t).prepend(cl.head);
2574 } else {
2575 return cl;
2576 }
2577 }
2579 /**
2580 * Form the union of two closures
2581 */
2582 public List<Type> union(List<Type> cl1, List<Type> cl2) {
2583 if (cl1.isEmpty()) {
2584 return cl2;
2585 } else if (cl2.isEmpty()) {
2586 return cl1;
2587 } else if (cl1.head.tsym.precedes(cl2.head.tsym, this)) {
2588 return union(cl1.tail, cl2).prepend(cl1.head);
2589 } else if (cl2.head.tsym.precedes(cl1.head.tsym, this)) {
2590 return union(cl1, cl2.tail).prepend(cl2.head);
2591 } else {
2592 return union(cl1.tail, cl2.tail).prepend(cl1.head);
2593 }
2594 }
2596 /**
2597 * Intersect two closures
2598 */
2599 public List<Type> intersect(List<Type> cl1, List<Type> cl2) {
2600 if (cl1 == cl2)
2601 return cl1;
2602 if (cl1.isEmpty() || cl2.isEmpty())
2603 return List.nil();
2604 if (cl1.head.tsym.precedes(cl2.head.tsym, this))
2605 return intersect(cl1.tail, cl2);
2606 if (cl2.head.tsym.precedes(cl1.head.tsym, this))
2607 return intersect(cl1, cl2.tail);
2608 if (isSameType(cl1.head, cl2.head))
2609 return intersect(cl1.tail, cl2.tail).prepend(cl1.head);
2610 if (cl1.head.tsym == cl2.head.tsym &&
2611 cl1.head.tag == CLASS && cl2.head.tag == CLASS) {
2612 if (cl1.head.isParameterized() && cl2.head.isParameterized()) {
2613 Type merge = merge(cl1.head,cl2.head);
2614 return intersect(cl1.tail, cl2.tail).prepend(merge);
2615 }
2616 if (cl1.head.isRaw() || cl2.head.isRaw())
2617 return intersect(cl1.tail, cl2.tail).prepend(erasure(cl1.head));
2618 }
2619 return intersect(cl1.tail, cl2.tail);
2620 }
2621 // where
2622 class TypePair {
2623 final Type t1;
2624 final Type t2;
2625 TypePair(Type t1, Type t2) {
2626 this.t1 = t1;
2627 this.t2 = t2;
2628 }
2629 @Override
2630 public int hashCode() {
2631 return 127 * Types.this.hashCode(t1) + Types.this.hashCode(t2);
2632 }
2633 @Override
2634 public boolean equals(Object obj) {
2635 if (!(obj instanceof TypePair))
2636 return false;
2637 TypePair typePair = (TypePair)obj;
2638 return isSameType(t1, typePair.t1)
2639 && isSameType(t2, typePair.t2);
2640 }
2641 }
2642 Set<TypePair> mergeCache = new HashSet<TypePair>();
2643 private Type merge(Type c1, Type c2) {
2644 ClassType class1 = (ClassType) c1;
2645 List<Type> act1 = class1.getTypeArguments();
2646 ClassType class2 = (ClassType) c2;
2647 List<Type> act2 = class2.getTypeArguments();
2648 ListBuffer<Type> merged = new ListBuffer<Type>();
2649 List<Type> typarams = class1.tsym.type.getTypeArguments();
2651 while (act1.nonEmpty() && act2.nonEmpty() && typarams.nonEmpty()) {
2652 if (containsType(act1.head, act2.head)) {
2653 merged.append(act1.head);
2654 } else if (containsType(act2.head, act1.head)) {
2655 merged.append(act2.head);
2656 } else {
2657 TypePair pair = new TypePair(c1, c2);
2658 Type m;
2659 if (mergeCache.add(pair)) {
2660 m = new WildcardType(lub(upperBound(act1.head),
2661 upperBound(act2.head)),
2662 BoundKind.EXTENDS,
2663 syms.boundClass);
2664 mergeCache.remove(pair);
2665 } else {
2666 m = new WildcardType(syms.objectType,
2667 BoundKind.UNBOUND,
2668 syms.boundClass);
2669 }
2670 merged.append(m.withTypeVar(typarams.head));
2671 }
2672 act1 = act1.tail;
2673 act2 = act2.tail;
2674 typarams = typarams.tail;
2675 }
2676 assert(act1.isEmpty() && act2.isEmpty() && typarams.isEmpty());
2677 return new ClassType(class1.getEnclosingType(), merged.toList(), class1.tsym);
2678 }
2680 /**
2681 * Return the minimum type of a closure, a compound type if no
2682 * unique minimum exists.
2683 */
2684 private Type compoundMin(List<Type> cl) {
2685 if (cl.isEmpty()) return syms.objectType;
2686 List<Type> compound = closureMin(cl);
2687 if (compound.isEmpty())
2688 return null;
2689 else if (compound.tail.isEmpty())
2690 return compound.head;
2691 else
2692 return makeCompoundType(compound);
2693 }
2695 /**
2696 * Return the minimum types of a closure, suitable for computing
2697 * compoundMin or glb.
2698 */
2699 private List<Type> closureMin(List<Type> cl) {
2700 ListBuffer<Type> classes = lb();
2701 ListBuffer<Type> interfaces = lb();
2702 while (!cl.isEmpty()) {
2703 Type current = cl.head;
2704 if (current.isInterface())
2705 interfaces.append(current);
2706 else
2707 classes.append(current);
2708 ListBuffer<Type> candidates = lb();
2709 for (Type t : cl.tail) {
2710 if (!isSubtypeNoCapture(current, t))
2711 candidates.append(t);
2712 }
2713 cl = candidates.toList();
2714 }
2715 return classes.appendList(interfaces).toList();
2716 }
2718 /**
2719 * Return the least upper bound of pair of types. if the lub does
2720 * not exist return null.
2721 */
2722 public Type lub(Type t1, Type t2) {
2723 return lub(List.of(t1, t2));
2724 }
2726 /**
2727 * Return the least upper bound (lub) of set of types. If the lub
2728 * does not exist return the type of null (bottom).
2729 */
2730 public Type lub(List<Type> ts) {
2731 final int ARRAY_BOUND = 1;
2732 final int CLASS_BOUND = 2;
2733 int boundkind = 0;
2734 for (Type t : ts) {
2735 switch (t.tag) {
2736 case CLASS:
2737 boundkind |= CLASS_BOUND;
2738 break;
2739 case ARRAY:
2740 boundkind |= ARRAY_BOUND;
2741 break;
2742 case TYPEVAR:
2743 do {
2744 t = t.getUpperBound();
2745 } while (t.tag == TYPEVAR);
2746 if (t.tag == ARRAY) {
2747 boundkind |= ARRAY_BOUND;
2748 } else {
2749 boundkind |= CLASS_BOUND;
2750 }
2751 break;
2752 default:
2753 if (t.isPrimitive())
2754 return syms.errType;
2755 }
2756 }
2757 switch (boundkind) {
2758 case 0:
2759 return syms.botType;
2761 case ARRAY_BOUND:
2762 // calculate lub(A[], B[])
2763 List<Type> elements = Type.map(ts, elemTypeFun);
2764 for (Type t : elements) {
2765 if (t.isPrimitive()) {
2766 // if a primitive type is found, then return
2767 // arraySuperType unless all the types are the
2768 // same
2769 Type first = ts.head;
2770 for (Type s : ts.tail) {
2771 if (!isSameType(first, s)) {
2772 // lub(int[], B[]) is Cloneable & Serializable
2773 return arraySuperType();
2774 }
2775 }
2776 // all the array types are the same, return one
2777 // lub(int[], int[]) is int[]
2778 return first;
2779 }
2780 }
2781 // lub(A[], B[]) is lub(A, B)[]
2782 return new ArrayType(lub(elements), syms.arrayClass);
2784 case CLASS_BOUND:
2785 // calculate lub(A, B)
2786 while (ts.head.tag != CLASS && ts.head.tag != TYPEVAR)
2787 ts = ts.tail;
2788 assert !ts.isEmpty();
2789 List<Type> cl = closure(ts.head);
2790 for (Type t : ts.tail) {
2791 if (t.tag == CLASS || t.tag == TYPEVAR)
2792 cl = intersect(cl, closure(t));
2793 }
2794 return compoundMin(cl);
2796 default:
2797 // calculate lub(A, B[])
2798 List<Type> classes = List.of(arraySuperType());
2799 for (Type t : ts) {
2800 if (t.tag != ARRAY) // Filter out any arrays
2801 classes = classes.prepend(t);
2802 }
2803 // lub(A, B[]) is lub(A, arraySuperType)
2804 return lub(classes);
2805 }
2806 }
2807 // where
2808 private Type arraySuperType = null;
2809 private Type arraySuperType() {
2810 // initialized lazily to avoid problems during compiler startup
2811 if (arraySuperType == null) {
2812 synchronized (this) {
2813 if (arraySuperType == null) {
2814 // JLS 10.8: all arrays implement Cloneable and Serializable.
2815 arraySuperType = makeCompoundType(List.of(syms.serializableType,
2816 syms.cloneableType),
2817 syms.objectType);
2818 }
2819 }
2820 }
2821 return arraySuperType;
2822 }
2823 // </editor-fold>
2825 // <editor-fold defaultstate="collapsed" desc="Greatest lower bound">
2826 public Type glb(Type t, Type s) {
2827 if (s == null)
2828 return t;
2829 else if (isSubtypeNoCapture(t, s))
2830 return t;
2831 else if (isSubtypeNoCapture(s, t))
2832 return s;
2834 List<Type> closure = union(closure(t), closure(s));
2835 List<Type> bounds = closureMin(closure);
2837 if (bounds.isEmpty()) { // length == 0
2838 return syms.objectType;
2839 } else if (bounds.tail.isEmpty()) { // length == 1
2840 return bounds.head;
2841 } else { // length > 1
2842 int classCount = 0;
2843 for (Type bound : bounds)
2844 if (!bound.isInterface())
2845 classCount++;
2846 if (classCount > 1)
2847 return createErrorType(t);
2848 }
2849 return makeCompoundType(bounds);
2850 }
2851 // </editor-fold>
2853 // <editor-fold defaultstate="collapsed" desc="hashCode">
2854 /**
2855 * Compute a hash code on a type.
2856 */
2857 public static int hashCode(Type t) {
2858 return hashCode.visit(t);
2859 }
2860 // where
2861 private static final UnaryVisitor<Integer> hashCode = new UnaryVisitor<Integer>() {
2863 public Integer visitType(Type t, Void ignored) {
2864 return t.tag;
2865 }
2867 @Override
2868 public Integer visitClassType(ClassType t, Void ignored) {
2869 int result = visit(t.getEnclosingType());
2870 result *= 127;
2871 result += t.tsym.flatName().hashCode();
2872 for (Type s : t.getTypeArguments()) {
2873 result *= 127;
2874 result += visit(s);
2875 }
2876 return result;
2877 }
2879 @Override
2880 public Integer visitWildcardType(WildcardType t, Void ignored) {
2881 int result = t.kind.hashCode();
2882 if (t.type != null) {
2883 result *= 127;
2884 result += visit(t.type);
2885 }
2886 return result;
2887 }
2889 @Override
2890 public Integer visitArrayType(ArrayType t, Void ignored) {
2891 return visit(t.elemtype) + 12;
2892 }
2894 @Override
2895 public Integer visitTypeVar(TypeVar t, Void ignored) {
2896 return System.identityHashCode(t.tsym);
2897 }
2899 @Override
2900 public Integer visitUndetVar(UndetVar t, Void ignored) {
2901 return System.identityHashCode(t);
2902 }
2904 @Override
2905 public Integer visitErrorType(ErrorType t, Void ignored) {
2906 return 0;
2907 }
2908 };
2909 // </editor-fold>
2911 // <editor-fold defaultstate="collapsed" desc="Return-Type-Substitutable">
2912 /**
2913 * Does t have a result that is a subtype of the result type of s,
2914 * suitable for covariant returns? It is assumed that both types
2915 * are (possibly polymorphic) method types. Monomorphic method
2916 * types are handled in the obvious way. Polymorphic method types
2917 * require renaming all type variables of one to corresponding
2918 * type variables in the other, where correspondence is by
2919 * position in the type parameter list. */
2920 public boolean resultSubtype(Type t, Type s, Warner warner) {
2921 List<Type> tvars = t.getTypeArguments();
2922 List<Type> svars = s.getTypeArguments();
2923 Type tres = t.getReturnType();
2924 Type sres = subst(s.getReturnType(), svars, tvars);
2925 return covariantReturnType(tres, sres, warner);
2926 }
2928 /**
2929 * Return-Type-Substitutable.
2930 * @see <a href="http://java.sun.com/docs/books/jls/">The Java
2931 * Language Specification, Third Ed. (8.4.5)</a>
2932 */
2933 public boolean returnTypeSubstitutable(Type r1, Type r2) {
2934 if (hasSameArgs(r1, r2))
2935 return resultSubtype(r1, r2, Warner.noWarnings);
2936 else
2937 return covariantReturnType(r1.getReturnType(),
2938 erasure(r2.getReturnType()),
2939 Warner.noWarnings);
2940 }
2942 public boolean returnTypeSubstitutable(Type r1,
2943 Type r2, Type r2res,
2944 Warner warner) {
2945 if (isSameType(r1.getReturnType(), r2res))
2946 return true;
2947 if (r1.getReturnType().isPrimitive() || r2res.isPrimitive())
2948 return false;
2950 if (hasSameArgs(r1, r2))
2951 return covariantReturnType(r1.getReturnType(), r2res, warner);
2952 if (!source.allowCovariantReturns())
2953 return false;
2954 if (isSubtypeUnchecked(r1.getReturnType(), r2res, warner))
2955 return true;
2956 if (!isSubtype(r1.getReturnType(), erasure(r2res)))
2957 return false;
2958 warner.warnUnchecked();
2959 return true;
2960 }
2962 /**
2963 * Is t an appropriate return type in an overrider for a
2964 * method that returns s?
2965 */
2966 public boolean covariantReturnType(Type t, Type s, Warner warner) {
2967 return
2968 isSameType(t, s) ||
2969 source.allowCovariantReturns() &&
2970 !t.isPrimitive() &&
2971 !s.isPrimitive() &&
2972 isAssignable(t, s, warner);
2973 }
2974 // </editor-fold>
2976 // <editor-fold defaultstate="collapsed" desc="Box/unbox support">
2977 /**
2978 * Return the class that boxes the given primitive.
2979 */
2980 public ClassSymbol boxedClass(Type t) {
2981 return reader.enterClass(syms.boxedName[t.tag]);
2982 }
2984 /**
2985 * Return the primitive type corresponding to a boxed type.
2986 */
2987 public Type unboxedType(Type t) {
2988 if (allowBoxing) {
2989 for (int i=0; i<syms.boxedName.length; i++) {
2990 Name box = syms.boxedName[i];
2991 if (box != null &&
2992 asSuper(t, reader.enterClass(box)) != null)
2993 return syms.typeOfTag[i];
2994 }
2995 }
2996 return Type.noType;
2997 }
2998 // </editor-fold>
3000 // <editor-fold defaultstate="collapsed" desc="Capture conversion">
3001 /*
3002 * JLS 3rd Ed. 5.1.10 Capture Conversion:
3003 *
3004 * Let G name a generic type declaration with n formal type
3005 * parameters A1 ... An with corresponding bounds U1 ... Un. There
3006 * exists a capture conversion from G<T1 ... Tn> to G<S1 ... Sn>,
3007 * where, for 1 <= i <= n:
3008 *
3009 * + If Ti is a wildcard type argument (4.5.1) of the form ? then
3010 * Si is a fresh type variable whose upper bound is
3011 * Ui[A1 := S1, ..., An := Sn] and whose lower bound is the null
3012 * type.
3013 *
3014 * + If Ti is a wildcard type argument of the form ? extends Bi,
3015 * then Si is a fresh type variable whose upper bound is
3016 * glb(Bi, Ui[A1 := S1, ..., An := Sn]) and whose lower bound is
3017 * the null type, where glb(V1,... ,Vm) is V1 & ... & Vm. It is
3018 * a compile-time error if for any two classes (not interfaces)
3019 * Vi and Vj,Vi is not a subclass of Vj or vice versa.
3020 *
3021 * + If Ti is a wildcard type argument of the form ? super Bi,
3022 * then Si is a fresh type variable whose upper bound is
3023 * Ui[A1 := S1, ..., An := Sn] and whose lower bound is Bi.
3024 *
3025 * + Otherwise, Si = Ti.
3026 *
3027 * Capture conversion on any type other than a parameterized type
3028 * (4.5) acts as an identity conversion (5.1.1). Capture
3029 * conversions never require a special action at run time and
3030 * therefore never throw an exception at run time.
3031 *
3032 * Capture conversion is not applied recursively.
3033 */
3034 /**
3035 * Capture conversion as specified by JLS 3rd Ed.
3036 */
3037 public Type capture(Type t) {
3038 if (t.tag != CLASS)
3039 return t;
3040 ClassType cls = (ClassType)t;
3041 if (cls.isRaw() || !cls.isParameterized())
3042 return cls;
3044 ClassType G = (ClassType)cls.asElement().asType();
3045 List<Type> A = G.getTypeArguments();
3046 List<Type> T = cls.getTypeArguments();
3047 List<Type> S = freshTypeVariables(T);
3049 List<Type> currentA = A;
3050 List<Type> currentT = T;
3051 List<Type> currentS = S;
3052 boolean captured = false;
3053 while (!currentA.isEmpty() &&
3054 !currentT.isEmpty() &&
3055 !currentS.isEmpty()) {
3056 if (currentS.head != currentT.head) {
3057 captured = true;
3058 WildcardType Ti = (WildcardType)currentT.head;
3059 Type Ui = currentA.head.getUpperBound();
3060 CapturedType Si = (CapturedType)currentS.head;
3061 if (Ui == null)
3062 Ui = syms.objectType;
3063 switch (Ti.kind) {
3064 case UNBOUND:
3065 Si.bound = subst(Ui, A, S);
3066 Si.lower = syms.botType;
3067 break;
3068 case EXTENDS:
3069 Si.bound = glb(Ti.getExtendsBound(), subst(Ui, A, S));
3070 Si.lower = syms.botType;
3071 break;
3072 case SUPER:
3073 Si.bound = subst(Ui, A, S);
3074 Si.lower = Ti.getSuperBound();
3075 break;
3076 }
3077 if (Si.bound == Si.lower)
3078 currentS.head = Si.bound;
3079 }
3080 currentA = currentA.tail;
3081 currentT = currentT.tail;
3082 currentS = currentS.tail;
3083 }
3084 if (!currentA.isEmpty() || !currentT.isEmpty() || !currentS.isEmpty())
3085 return erasure(t); // some "rare" type involved
3087 if (captured)
3088 return new ClassType(cls.getEnclosingType(), S, cls.tsym);
3089 else
3090 return t;
3091 }
3092 // where
3093 private List<Type> freshTypeVariables(List<Type> types) {
3094 ListBuffer<Type> result = lb();
3095 for (Type t : types) {
3096 if (t.tag == WILDCARD) {
3097 Type bound = ((WildcardType)t).getExtendsBound();
3098 if (bound == null)
3099 bound = syms.objectType;
3100 result.append(new CapturedType(capturedName,
3101 syms.noSymbol,
3102 bound,
3103 syms.botType,
3104 (WildcardType)t));
3105 } else {
3106 result.append(t);
3107 }
3108 }
3109 return result.toList();
3110 }
3111 // </editor-fold>
3113 // <editor-fold defaultstate="collapsed" desc="Internal utility methods">
3114 private List<Type> upperBounds(List<Type> ss) {
3115 if (ss.isEmpty()) return ss;
3116 Type head = upperBound(ss.head);
3117 List<Type> tail = upperBounds(ss.tail);
3118 if (head != ss.head || tail != ss.tail)
3119 return tail.prepend(head);
3120 else
3121 return ss;
3122 }
3124 private boolean sideCast(Type from, Type to, Warner warn) {
3125 // We are casting from type $from$ to type $to$, which are
3126 // non-final unrelated types. This method
3127 // tries to reject a cast by transferring type parameters
3128 // from $to$ to $from$ by common superinterfaces.
3129 boolean reverse = false;
3130 Type target = to;
3131 if ((to.tsym.flags() & INTERFACE) == 0) {
3132 assert (from.tsym.flags() & INTERFACE) != 0;
3133 reverse = true;
3134 to = from;
3135 from = target;
3136 }
3137 List<Type> commonSupers = superClosure(to, erasure(from));
3138 boolean giveWarning = commonSupers.isEmpty();
3139 // The arguments to the supers could be unified here to
3140 // get a more accurate analysis
3141 while (commonSupers.nonEmpty()) {
3142 Type t1 = asSuper(from, commonSupers.head.tsym);
3143 Type t2 = commonSupers.head; // same as asSuper(to, commonSupers.head.tsym);
3144 if (disjointTypes(t1.getTypeArguments(), t2.getTypeArguments()))
3145 return false;
3146 giveWarning = giveWarning || (reverse ? giveWarning(t2, t1) : giveWarning(t1, t2));
3147 commonSupers = commonSupers.tail;
3148 }
3149 if (giveWarning && !isReifiable(to))
3150 warn.warnUnchecked();
3151 if (!source.allowCovariantReturns())
3152 // reject if there is a common method signature with
3153 // incompatible return types.
3154 chk.checkCompatibleAbstracts(warn.pos(), from, to);
3155 return true;
3156 }
3158 private boolean sideCastFinal(Type from, Type to, Warner warn) {
3159 // We are casting from type $from$ to type $to$, which are
3160 // unrelated types one of which is final and the other of
3161 // which is an interface. This method
3162 // tries to reject a cast by transferring type parameters
3163 // from the final class to the interface.
3164 boolean reverse = false;
3165 Type target = to;
3166 if ((to.tsym.flags() & INTERFACE) == 0) {
3167 assert (from.tsym.flags() & INTERFACE) != 0;
3168 reverse = true;
3169 to = from;
3170 from = target;
3171 }
3172 assert (from.tsym.flags() & FINAL) != 0;
3173 Type t1 = asSuper(from, to.tsym);
3174 if (t1 == null) return false;
3175 Type t2 = to;
3176 if (disjointTypes(t1.getTypeArguments(), t2.getTypeArguments()))
3177 return false;
3178 if (!source.allowCovariantReturns())
3179 // reject if there is a common method signature with
3180 // incompatible return types.
3181 chk.checkCompatibleAbstracts(warn.pos(), from, to);
3182 if (!isReifiable(target) &&
3183 (reverse ? giveWarning(t2, t1) : giveWarning(t1, t2)))
3184 warn.warnUnchecked();
3185 return true;
3186 }
3188 private boolean giveWarning(Type from, Type to) {
3189 // To and from are (possibly different) parameterizations
3190 // of the same class or interface
3191 return to.isParameterized() && !containsType(to.getTypeArguments(), from.getTypeArguments());
3192 }
3194 private List<Type> superClosure(Type t, Type s) {
3195 List<Type> cl = List.nil();
3196 for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail) {
3197 if (isSubtype(s, erasure(l.head))) {
3198 cl = insert(cl, l.head);
3199 } else {
3200 cl = union(cl, superClosure(l.head, s));
3201 }
3202 }
3203 return cl;
3204 }
3206 private boolean containsTypeEquivalent(Type t, Type s) {
3207 return
3208 isSameType(t, s) || // shortcut
3209 containsType(t, s) && containsType(s, t);
3210 }
3212 /**
3213 * Adapt a type by computing a substitution which maps a source
3214 * type to a target type.
3215 *
3216 * @param source the source type
3217 * @param target the target type
3218 * @param from the type variables of the computed substitution
3219 * @param to the types of the computed substitution.
3220 */
3221 public void adapt(Type source,
3222 Type target,
3223 ListBuffer<Type> from,
3224 ListBuffer<Type> to) throws AdaptFailure {
3225 Map<Symbol,Type> mapping = new HashMap<Symbol,Type>();
3226 adaptRecursive(source, target, from, to, mapping);
3227 List<Type> fromList = from.toList();
3228 List<Type> toList = to.toList();
3229 while (!fromList.isEmpty()) {
3230 Type val = mapping.get(fromList.head.tsym);
3231 if (toList.head != val)
3232 toList.head = val;
3233 fromList = fromList.tail;
3234 toList = toList.tail;
3235 }
3236 }
3237 // where
3238 private void adaptRecursive(Type source,
3239 Type target,
3240 ListBuffer<Type> from,
3241 ListBuffer<Type> to,
3242 Map<Symbol,Type> mapping) throws AdaptFailure {
3243 if (source.tag == TYPEVAR) {
3244 // Check to see if there is
3245 // already a mapping for $source$, in which case
3246 // the old mapping will be merged with the new
3247 Type val = mapping.get(source.tsym);
3248 if (val != null) {
3249 if (val.isSuperBound() && target.isSuperBound()) {
3250 val = isSubtype(lowerBound(val), lowerBound(target))
3251 ? target : val;
3252 } else if (val.isExtendsBound() && target.isExtendsBound()) {
3253 val = isSubtype(upperBound(val), upperBound(target))
3254 ? val : target;
3255 } else if (!isSameType(val, target)) {
3256 throw new AdaptFailure();
3257 }
3258 } else {
3259 val = target;
3260 from.append(source);
3261 to.append(target);
3262 }
3263 mapping.put(source.tsym, val);
3264 } else if (source.tag == target.tag) {
3265 switch (source.tag) {
3266 case CLASS:
3267 adapt(source.allparams(), target.allparams(),
3268 from, to, mapping);
3269 break;
3270 case ARRAY:
3271 adaptRecursive(elemtype(source), elemtype(target),
3272 from, to, mapping);
3273 break;
3274 case WILDCARD:
3275 if (source.isExtendsBound()) {
3276 adaptRecursive(upperBound(source), upperBound(target),
3277 from, to, mapping);
3278 } else if (source.isSuperBound()) {
3279 adaptRecursive(lowerBound(source), lowerBound(target),
3280 from, to, mapping);
3281 }
3282 break;
3283 }
3284 }
3285 }
3286 public static class AdaptFailure extends Exception {
3287 static final long serialVersionUID = -7490231548272701566L;
3288 }
3290 /**
3291 * Adapt a type by computing a substitution which maps a list of
3292 * source types to a list of target types.
3293 *
3294 * @param source the source type
3295 * @param target the target type
3296 * @param from the type variables of the computed substitution
3297 * @param to the types of the computed substitution.
3298 */
3299 private void adapt(List<Type> source,
3300 List<Type> target,
3301 ListBuffer<Type> from,
3302 ListBuffer<Type> to,
3303 Map<Symbol,Type> mapping) throws AdaptFailure {
3304 if (source.length() == target.length()) {
3305 while (source.nonEmpty()) {
3306 adaptRecursive(source.head, target.head, from, to, mapping);
3307 source = source.tail;
3308 target = target.tail;
3309 }
3310 }
3311 }
3313 private void adaptSelf(Type t,
3314 ListBuffer<Type> from,
3315 ListBuffer<Type> to) {
3316 try {
3317 //if (t.tsym.type != t)
3318 adapt(t.tsym.type, t, from, to);
3319 } catch (AdaptFailure ex) {
3320 // Adapt should never fail calculating a mapping from
3321 // t.tsym.type to t as there can be no merge problem.
3322 throw new AssertionError(ex);
3323 }
3324 }
3326 /**
3327 * Rewrite all type variables (universal quantifiers) in the given
3328 * type to wildcards (existential quantifiers). This is used to
3329 * determine if a cast is allowed. For example, if high is true
3330 * and {@code T <: Number}, then {@code List<T>} is rewritten to
3331 * {@code List<? extends Number>}. Since {@code List<Integer> <:
3332 * List<? extends Number>} a {@code List<T>} can be cast to {@code
3333 * List<Integer>} with a warning.
3334 * @param t a type
3335 * @param high if true return an upper bound; otherwise a lower
3336 * bound
3337 * @param rewriteTypeVars only rewrite captured wildcards if false;
3338 * otherwise rewrite all type variables
3339 * @return the type rewritten with wildcards (existential
3340 * quantifiers) only
3341 */
3342 private Type rewriteQuantifiers(Type t, boolean high, boolean rewriteTypeVars) {
3343 ListBuffer<Type> from = new ListBuffer<Type>();
3344 ListBuffer<Type> to = new ListBuffer<Type>();
3345 adaptSelf(t, from, to);
3346 ListBuffer<Type> rewritten = new ListBuffer<Type>();
3347 List<Type> formals = from.toList();
3348 boolean changed = false;
3349 for (Type arg : to.toList()) {
3350 Type bound;
3351 if (rewriteTypeVars && arg.tag == TYPEVAR) {
3352 TypeVar tv = (TypeVar)arg;
3353 bound = high ? tv.bound : syms.botType;
3354 } else {
3355 bound = high ? upperBound(arg) : lowerBound(arg);
3356 }
3357 Type newarg = bound;
3358 if (arg != bound) {
3359 changed = true;
3360 newarg = high ? makeExtendsWildcard(bound, (TypeVar)formals.head)
3361 : makeSuperWildcard(bound, (TypeVar)formals.head);
3362 }
3363 rewritten.append(newarg);
3364 formals = formals.tail;
3365 }
3366 if (changed)
3367 return subst(t.tsym.type, from.toList(), rewritten.toList());
3368 else
3369 return t;
3370 }
3372 /**
3373 * Create a wildcard with the given upper (extends) bound; create
3374 * an unbounded wildcard if bound is Object.
3375 *
3376 * @param bound the upper bound
3377 * @param formal the formal type parameter that will be
3378 * substituted by the wildcard
3379 */
3380 private WildcardType makeExtendsWildcard(Type bound, TypeVar formal) {
3381 if (bound == syms.objectType) {
3382 return new WildcardType(syms.objectType,
3383 BoundKind.UNBOUND,
3384 syms.boundClass,
3385 formal);
3386 } else {
3387 return new WildcardType(bound,
3388 BoundKind.EXTENDS,
3389 syms.boundClass,
3390 formal);
3391 }
3392 }
3394 /**
3395 * Create a wildcard with the given lower (super) bound; create an
3396 * unbounded wildcard if bound is bottom (type of {@code null}).
3397 *
3398 * @param bound the lower bound
3399 * @param formal the formal type parameter that will be
3400 * substituted by the wildcard
3401 */
3402 private WildcardType makeSuperWildcard(Type bound, TypeVar formal) {
3403 if (bound.tag == BOT) {
3404 return new WildcardType(syms.objectType,
3405 BoundKind.UNBOUND,
3406 syms.boundClass,
3407 formal);
3408 } else {
3409 return new WildcardType(bound,
3410 BoundKind.SUPER,
3411 syms.boundClass,
3412 formal);
3413 }
3414 }
3416 /**
3417 * A wrapper for a type that allows use in sets.
3418 */
3419 class SingletonType {
3420 final Type t;
3421 SingletonType(Type t) {
3422 this.t = t;
3423 }
3424 public int hashCode() {
3425 return Types.this.hashCode(t);
3426 }
3427 public boolean equals(Object obj) {
3428 return (obj instanceof SingletonType) &&
3429 isSameType(t, ((SingletonType)obj).t);
3430 }
3431 public String toString() {
3432 return t.toString();
3433 }
3434 }
3435 // </editor-fold>
3437 // <editor-fold defaultstate="collapsed" desc="Visitors">
3438 /**
3439 * A default visitor for types. All visitor methods except
3440 * visitType are implemented by delegating to visitType. Concrete
3441 * subclasses must provide an implementation of visitType and can
3442 * override other methods as needed.
3443 *
3444 * @param <R> the return type of the operation implemented by this
3445 * visitor; use Void if no return type is needed.
3446 * @param <S> the type of the second argument (the first being the
3447 * type itself) of the operation implemented by this visitor; use
3448 * Void if a second argument is not needed.
3449 */
3450 public static abstract class DefaultTypeVisitor<R,S> implements Type.Visitor<R,S> {
3451 final public R visit(Type t, S s) { return t.accept(this, s); }
3452 public R visitClassType(ClassType t, S s) { return visitType(t, s); }
3453 public R visitWildcardType(WildcardType t, S s) { return visitType(t, s); }
3454 public R visitArrayType(ArrayType t, S s) { return visitType(t, s); }
3455 public R visitMethodType(MethodType t, S s) { return visitType(t, s); }
3456 public R visitPackageType(PackageType t, S s) { return visitType(t, s); }
3457 public R visitTypeVar(TypeVar t, S s) { return visitType(t, s); }
3458 public R visitCapturedType(CapturedType t, S s) { return visitType(t, s); }
3459 public R visitForAll(ForAll t, S s) { return visitType(t, s); }
3460 public R visitUndetVar(UndetVar t, S s) { return visitType(t, s); }
3461 public R visitErrorType(ErrorType t, S s) { return visitType(t, s); }
3462 }
3464 /**
3465 * A default visitor for symbols. All visitor methods except
3466 * visitSymbol are implemented by delegating to visitSymbol. Concrete
3467 * subclasses must provide an implementation of visitSymbol and can
3468 * override other methods as needed.
3469 *
3470 * @param <R> the return type of the operation implemented by this
3471 * visitor; use Void if no return type is needed.
3472 * @param <S> the type of the second argument (the first being the
3473 * symbol itself) of the operation implemented by this visitor; use
3474 * Void if a second argument is not needed.
3475 */
3476 public static abstract class DefaultSymbolVisitor<R,S> implements Symbol.Visitor<R,S> {
3477 final public R visit(Symbol s, S arg) { return s.accept(this, arg); }
3478 public R visitClassSymbol(ClassSymbol s, S arg) { return visitSymbol(s, arg); }
3479 public R visitMethodSymbol(MethodSymbol s, S arg) { return visitSymbol(s, arg); }
3480 public R visitOperatorSymbol(OperatorSymbol s, S arg) { return visitSymbol(s, arg); }
3481 public R visitPackageSymbol(PackageSymbol s, S arg) { return visitSymbol(s, arg); }
3482 public R visitTypeSymbol(TypeSymbol s, S arg) { return visitSymbol(s, arg); }
3483 public R visitVarSymbol(VarSymbol s, S arg) { return visitSymbol(s, arg); }
3484 }
3486 /**
3487 * A <em>simple</em> visitor for types. This visitor is simple as
3488 * captured wildcards, for-all types (generic methods), and
3489 * undetermined type variables (part of inference) are hidden.
3490 * Captured wildcards are hidden by treating them as type
3491 * variables and the rest are hidden by visiting their qtypes.
3492 *
3493 * @param <R> the return type of the operation implemented by this
3494 * visitor; use Void if no return type is needed.
3495 * @param <S> the type of the second argument (the first being the
3496 * type itself) of the operation implemented by this visitor; use
3497 * Void if a second argument is not needed.
3498 */
3499 public static abstract class SimpleVisitor<R,S> extends DefaultTypeVisitor<R,S> {
3500 @Override
3501 public R visitCapturedType(CapturedType t, S s) {
3502 return visitTypeVar(t, s);
3503 }
3504 @Override
3505 public R visitForAll(ForAll t, S s) {
3506 return visit(t.qtype, s);
3507 }
3508 @Override
3509 public R visitUndetVar(UndetVar t, S s) {
3510 return visit(t.qtype, s);
3511 }
3512 }
3514 /**
3515 * A plain relation on types. That is a 2-ary function on the
3516 * form Type × Type → Boolean.
3517 * <!-- In plain text: Type x Type -> Boolean -->
3518 */
3519 public static abstract class TypeRelation extends SimpleVisitor<Boolean,Type> {}
3521 /**
3522 * A convenience visitor for implementing operations that only
3523 * require one argument (the type itself), that is, unary
3524 * operations.
3525 *
3526 * @param <R> the return type of the operation implemented by this
3527 * visitor; use Void if no return type is needed.
3528 */
3529 public static abstract class UnaryVisitor<R> extends SimpleVisitor<R,Void> {
3530 final public R visit(Type t) { return t.accept(this, null); }
3531 }
3533 /**
3534 * A visitor for implementing a mapping from types to types. The
3535 * default behavior of this class is to implement the identity
3536 * mapping (mapping a type to itself). This can be overridden in
3537 * subclasses.
3538 *
3539 * @param <S> the type of the second argument (the first being the
3540 * type itself) of this mapping; use Void if a second argument is
3541 * not needed.
3542 */
3543 public static class MapVisitor<S> extends DefaultTypeVisitor<Type,S> {
3544 final public Type visit(Type t) { return t.accept(this, null); }
3545 public Type visitType(Type t, S s) { return t; }
3546 }
3547 // </editor-fold>
3548 }