0001: /*
0002: * Copyright 2003-2006 Sun Microsystems, Inc. All Rights Reserved.
0003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004: *
0005: * This code is free software; you can redistribute it and/or modify it
0006: * under the terms of the GNU General Public License version 2 only, as
0007: * published by the Free Software Foundation. Sun designates this
0008: * particular file as subject to the "Classpath" exception as provided
0009: * by Sun in the LICENSE file that accompanied this code.
0010: *
0011: * This code is distributed in the hope that it will be useful, but WITHOUT
0012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014: * version 2 for more details (a copy is included in the LICENSE file that
0015: * accompanied this code).
0016: *
0017: * You should have received a copy of the GNU General Public License version
0018: * 2 along with this work; if not, write to the Free Software Foundation,
0019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020: *
0021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022: * CA 95054 USA or visit www.sun.com if you need additional information or
0023: * have any questions.
0024: */
0025:
0026: package com.sun.tools.javac.code;
0027:
0028: import java.util.*;
0029:
0030: import com.sun.tools.javac.util.*;
0031: import com.sun.tools.javac.util.List;
0032:
0033: import com.sun.tools.javac.jvm.ClassReader;
0034: import com.sun.tools.javac.comp.Infer;
0035: import com.sun.tools.javac.comp.Check;
0036:
0037: import static com.sun.tools.javac.code.Type.*;
0038: import static com.sun.tools.javac.code.TypeTags.*;
0039: import static com.sun.tools.javac.code.Symbol.*;
0040: import static com.sun.tools.javac.code.Flags.*;
0041: import static com.sun.tools.javac.code.BoundKind.*;
0042: import static com.sun.tools.javac.util.ListBuffer.lb;
0043:
0044: /**
0045: * Utility class containing various operations on types.
0046: *
0047: * <p>Unless other names are more illustrative, the following naming
0048: * conventions should be observed in this file:
0049: *
0050: * <dl>
0051: * <dt>t</dt>
0052: * <dd>If the first argument to an operation is a type, it should be named t.</dd>
0053: * <dt>s</dt>
0054: * <dd>Similarly, if the second argument to an operation is a type, it should be named s.</dd>
0055: * <dt>ts</dt>
0056: * <dd>If an operations takes a list of types, the first should be named ts.</dd>
0057: * <dt>ss</dt>
0058: * <dd>A second list of types should be named ss.</dd>
0059: * </dl>
0060: *
0061: * <p><b>This is NOT part of any API supported by Sun Microsystems.
0062: * If you write code that depends on this, you do so at your own risk.
0063: * This code and its internal interfaces are subject to change or
0064: * deletion without notice.</b>
0065: */
0066: @Version("@(#)Types.java 1.95 07/05/05")
0067: public class Types {
0068: protected static final Context.Key<Types> typesKey = new Context.Key<Types>();
0069:
0070: final Symtab syms;
0071: final Name.Table names;
0072: final boolean allowBoxing;
0073: final ClassReader reader;
0074: final Source source;
0075: final Check chk;
0076: List<Warner> warnStack = List.nil();
0077: final Name capturedName;
0078:
0079: // <editor-fold defaultstate="collapsed" desc="Instantiating">
0080: public static Types instance(Context context) {
0081: Types instance = context.get(typesKey);
0082: if (instance == null)
0083: instance = new Types(context);
0084: return instance;
0085: }
0086:
0087: protected Types(Context context) {
0088: context.put(typesKey, this );
0089: syms = Symtab.instance(context);
0090: names = Name.Table.instance(context);
0091: allowBoxing = Source.instance(context).allowBoxing();
0092: reader = ClassReader.instance(context);
0093: source = Source.instance(context);
0094: chk = Check.instance(context);
0095: capturedName = names.fromString("<captured wildcard>");
0096: }
0097:
0098: // </editor-fold>
0099:
0100: // <editor-fold defaultstate="collapsed" desc="upperBound">
0101: /**
0102: * The "rvalue conversion".<br>
0103: * The upper bound of most types is the type
0104: * itself. Wildcards, on the other hand have upper
0105: * and lower bounds.
0106: * @param t a type
0107: * @return the upper bound of the given type
0108: */
0109: public Type upperBound(Type t) {
0110: return upperBound.visit(t);
0111: }
0112:
0113: // where
0114: private final MapVisitor<Void> upperBound = new MapVisitor<Void>() {
0115:
0116: @Override
0117: public Type visitWildcardType(WildcardType t, Void ignored) {
0118: if (t.isSuperBound())
0119: return t.bound == null ? syms.objectType
0120: : t.bound.bound;
0121: else
0122: return visit(t.type);
0123: }
0124:
0125: @Override
0126: public Type visitCapturedType(CapturedType t, Void ignored) {
0127: return visit(t.bound);
0128: }
0129: };
0130:
0131: // </editor-fold>
0132:
0133: // <editor-fold defaultstate="collapsed" desc="lowerBound">
0134: /**
0135: * The "lvalue conversion".<br>
0136: * The lower bound of most types is the type
0137: * itself. Wildcards, on the other hand have upper
0138: * and lower bounds.
0139: * @param t a type
0140: * @return the lower bound of the given type
0141: */
0142: public Type lowerBound(Type t) {
0143: return lowerBound.visit(t);
0144: }
0145:
0146: // where
0147: private final MapVisitor<Void> lowerBound = new MapVisitor<Void>() {
0148:
0149: @Override
0150: public Type visitWildcardType(WildcardType t, Void ignored) {
0151: return t.isExtendsBound() ? syms.botType : visit(t.type);
0152: }
0153:
0154: @Override
0155: public Type visitCapturedType(CapturedType t, Void ignored) {
0156: return visit(t.getLowerBound());
0157: }
0158: };
0159:
0160: // </editor-fold>
0161:
0162: // <editor-fold defaultstate="collapsed" desc="isUnbounded">
0163: /**
0164: * Checks that all the arguments to a class are unbounded
0165: * wildcards or something else that doesn't make any restrictions
0166: * on the arguments. If a class isUnbounded, a raw super- or
0167: * subclass can be cast to it without a warning.
0168: * @param t a type
0169: * @return true iff the given type is unbounded or raw
0170: */
0171: public boolean isUnbounded(Type t) {
0172: return isUnbounded.visit(t);
0173: }
0174:
0175: // where
0176: private final UnaryVisitor<Boolean> isUnbounded = new UnaryVisitor<Boolean>() {
0177:
0178: public Boolean visitType(Type t, Void ignored) {
0179: return true;
0180: }
0181:
0182: @Override
0183: public Boolean visitClassType(ClassType t, Void ignored) {
0184: List<Type> parms = t.tsym.type.allparams();
0185: List<Type> args = t.allparams();
0186: while (parms.nonEmpty()) {
0187: WildcardType unb = new WildcardType(syms.objectType,
0188: BoundKind.UNBOUND, syms.boundClass,
0189: (TypeVar) parms.head);
0190: if (!containsType(args.head, unb))
0191: return false;
0192: parms = parms.tail;
0193: args = args.tail;
0194: }
0195: return true;
0196: }
0197: };
0198:
0199: // </editor-fold>
0200:
0201: // <editor-fold defaultstate="collapsed" desc="asSub">
0202: /**
0203: * Return the least specific subtype of t that starts with symbol
0204: * sym. If none exists, return null. The least specific subtype
0205: * is determined as follows:
0206: *
0207: * <p>If there is exactly one parameterized instance of sym that is a
0208: * subtype of t, that parameterized instance is returned.<br>
0209: * Otherwise, if the plain type or raw type `sym' is a subtype of
0210: * type t, the type `sym' itself is returned. Otherwise, null is
0211: * returned.
0212: */
0213: public Type asSub(Type t, Symbol sym) {
0214: return asSub.visit(t, sym);
0215: }
0216:
0217: // where
0218: private final SimpleVisitor<Type, Symbol> asSub = new SimpleVisitor<Type, Symbol>() {
0219:
0220: public Type visitType(Type t, Symbol sym) {
0221: return null;
0222: }
0223:
0224: @Override
0225: public Type visitClassType(ClassType t, Symbol sym) {
0226: if (t.tsym == sym)
0227: return t;
0228: Type base = asSuper(sym.type, t.tsym);
0229: if (base == null)
0230: return null;
0231: ListBuffer<Type> from = new ListBuffer<Type>();
0232: ListBuffer<Type> to = new ListBuffer<Type>();
0233: try {
0234: adapt(base, t, from, to);
0235: } catch (AdaptFailure ex) {
0236: return null;
0237: }
0238: Type res = subst(sym.type, from.toList(), to.toList());
0239: if (!isSubtype(res, t))
0240: return null;
0241: ListBuffer<Type> openVars = new ListBuffer<Type>();
0242: for (List<Type> l = sym.type.allparams(); l.nonEmpty(); l = l.tail)
0243: if (res.contains(l.head) && !t.contains(l.head))
0244: openVars.append(l.head);
0245: if (openVars.nonEmpty()) {
0246: if (t.isRaw()) {
0247: // The subtype of a raw type is raw
0248: res = erasure(res);
0249: } else {
0250: // Unbound type arguments default to ?
0251: List<Type> opens = openVars.toList();
0252: ListBuffer<Type> qs = new ListBuffer<Type>();
0253: for (List<Type> iter = opens; iter.nonEmpty(); iter = iter.tail) {
0254: qs.append(new WildcardType(syms.objectType,
0255: BoundKind.UNBOUND, syms.boundClass,
0256: (TypeVar) iter.head));
0257: }
0258: res = subst(res, opens, qs.toList());
0259: }
0260: }
0261: return res;
0262: }
0263:
0264: @Override
0265: public Type visitErrorType(ErrorType t, Symbol sym) {
0266: return t;
0267: }
0268: };
0269:
0270: // </editor-fold>
0271:
0272: // <editor-fold defaultstate="collapsed" desc="isConvertible">
0273: /**
0274: * Is t a subtype of or convertiable via boxing/unboxing
0275: * convertions to s?
0276: */
0277: public boolean isConvertible(Type t, Type s, Warner warn) {
0278: boolean tPrimitive = t.isPrimitive();
0279: boolean sPrimitive = s.isPrimitive();
0280: if (tPrimitive == sPrimitive)
0281: return isSubtypeUnchecked(t, s, warn);
0282: if (!allowBoxing)
0283: return false;
0284: return tPrimitive ? isSubtype(boxedClass(t).type, s)
0285: : isSubtype(unboxedType(t), s);
0286: }
0287:
0288: /**
0289: * Is t a subtype of or convertiable via boxing/unboxing
0290: * convertions to s?
0291: */
0292: public boolean isConvertible(Type t, Type s) {
0293: return isConvertible(t, s, Warner.noWarnings);
0294: }
0295:
0296: // </editor-fold>
0297:
0298: // <editor-fold defaultstate="collapsed" desc="isSubtype">
0299: /**
0300: * Is t an unchecked subtype of s?
0301: */
0302: public boolean isSubtypeUnchecked(Type t, Type s) {
0303: return isSubtypeUnchecked(t, s, Warner.noWarnings);
0304: }
0305:
0306: /**
0307: * Is t an unchecked subtype of s?
0308: */
0309: public boolean isSubtypeUnchecked(Type t, Type s, Warner warn) {
0310: if (t.tag == ARRAY && s.tag == ARRAY) {
0311: return (((ArrayType) t).elemtype.tag <= lastBaseTag) ? isSameType(
0312: elemtype(t), elemtype(s))
0313: : isSubtypeUnchecked(elemtype(t), elemtype(s), warn);
0314: } else if (isSubtype(t, s)) {
0315: return true;
0316: } else if (!s.isRaw()) {
0317: Type t2 = asSuper(t, s.tsym);
0318: if (t2 != null && t2.isRaw()) {
0319: if (isReifiable(s))
0320: warn.silentUnchecked();
0321: else
0322: warn.warnUnchecked();
0323: return true;
0324: }
0325: }
0326: return false;
0327: }
0328:
0329: /**
0330: * Is t a subtype of s?<br>
0331: * (not defined for Method and ForAll types)
0332: */
0333: final public boolean isSubtype(Type t, Type s) {
0334: return isSubtype(t, s, true);
0335: }
0336:
0337: final public boolean isSubtypeNoCapture(Type t, Type s) {
0338: return isSubtype(t, s, false);
0339: }
0340:
0341: public boolean isSubtype(Type t, Type s, boolean capture) {
0342: if (t == s)
0343: return true;
0344:
0345: if (s.tag >= firstPartialTag)
0346: return isSuperType(s, t);
0347:
0348: Type lower = lowerBound(s);
0349: if (s != lower)
0350: return isSubtype(capture ? capture(t) : t, lower, false);
0351:
0352: return isSubtype.visit(capture ? capture(t) : t, s);
0353: }
0354:
0355: // where
0356: private TypeRelation isSubtype = new TypeRelation() {
0357: public Boolean visitType(Type t, Type s) {
0358: switch (t.tag) {
0359: case BYTE:
0360: case CHAR:
0361: return (t.tag == s.tag || t.tag + 2 <= s.tag
0362: && s.tag <= DOUBLE);
0363: case SHORT:
0364: case INT:
0365: case LONG:
0366: case FLOAT:
0367: case DOUBLE:
0368: return t.tag <= s.tag && s.tag <= DOUBLE;
0369: case BOOLEAN:
0370: case VOID:
0371: return t.tag == s.tag;
0372: case TYPEVAR:
0373: return isSubtypeNoCapture(t.getUpperBound(), s);
0374: case BOT:
0375: return s.tag == BOT || s.tag == CLASS || s.tag == ARRAY
0376: || s.tag == TYPEVAR;
0377: case NONE:
0378: return false;
0379: default:
0380: throw new AssertionError("isSubtype " + t.tag);
0381: }
0382: }
0383:
0384: private Set<TypePair> cache = new HashSet<TypePair>();
0385:
0386: private boolean containsTypeRecursive(Type t, Type s) {
0387: TypePair pair = new TypePair(t, s);
0388: if (cache.add(pair)) {
0389: try {
0390: return containsType(t.getTypeArguments(), s
0391: .getTypeArguments());
0392: } finally {
0393: cache.remove(pair);
0394: }
0395: } else {
0396: return containsType(t.getTypeArguments(),
0397: rewriteSupers(s).getTypeArguments());
0398: }
0399: }
0400:
0401: private Type rewriteSupers(Type t) {
0402: if (!t.isParameterized())
0403: return t;
0404: ListBuffer<Type> from = lb();
0405: ListBuffer<Type> to = lb();
0406: adaptSelf(t, from, to);
0407: if (from.isEmpty())
0408: return t;
0409: ListBuffer<Type> rewrite = lb();
0410: boolean changed = false;
0411: for (Type orig : to.toList()) {
0412: Type s = rewriteSupers(orig);
0413: if (s.isSuperBound() && !s.isExtendsBound()) {
0414: s = new WildcardType(syms.objectType,
0415: BoundKind.UNBOUND, syms.boundClass);
0416: changed = true;
0417: } else if (s != orig) {
0418: s = new WildcardType(upperBound(s),
0419: BoundKind.EXTENDS, syms.boundClass);
0420: changed = true;
0421: }
0422: rewrite.append(s);
0423: }
0424: if (changed)
0425: return subst(t.tsym.type, from.toList(), rewrite
0426: .toList());
0427: else
0428: return t;
0429: }
0430:
0431: @Override
0432: public Boolean visitClassType(ClassType t, Type s) {
0433: Type sup = asSuper(t, s.tsym);
0434: return sup != null
0435: && sup.tsym == s.tsym
0436: // You're not allowed to write
0437: // Vector<Object> vec = new Vector<String>();
0438: // But with wildcards you can write
0439: // Vector<? extends Object> vec = new Vector<String>();
0440: // which means that subtype checking must be done
0441: // here instead of same-type checking (via containsType).
0442: && (!s.isParameterized() || containsTypeRecursive(
0443: s, sup))
0444: && isSubtypeNoCapture(sup.getEnclosingType(), s
0445: .getEnclosingType());
0446: }
0447:
0448: @Override
0449: public Boolean visitArrayType(ArrayType t, Type s) {
0450: if (s.tag == ARRAY) {
0451: if (t.elemtype.tag <= lastBaseTag)
0452: return isSameType(t.elemtype, elemtype(s));
0453: else
0454: return isSubtypeNoCapture(t.elemtype, elemtype(s));
0455: }
0456:
0457: if (s.tag == CLASS) {
0458: Name sname = s.tsym.getQualifiedName();
0459: return sname == names.java_lang_Object
0460: || sname == names.java_lang_Cloneable
0461: || sname == names.java_io_Serializable;
0462: }
0463:
0464: return false;
0465: }
0466:
0467: @Override
0468: public Boolean visitUndetVar(UndetVar t, Type s) {
0469: //todo: test against origin needed? or replace with substitution?
0470: if (t == s || t.qtype == s || s.tag == ERROR
0471: || s.tag == UNKNOWN)
0472: return true;
0473:
0474: if (t.inst != null)
0475: return isSubtypeNoCapture(t.inst, s); // TODO: ", warn"?
0476:
0477: t.hibounds = t.hibounds.prepend(s);
0478: return true;
0479: }
0480:
0481: @Override
0482: public Boolean visitErrorType(ErrorType t, Type s) {
0483: return true;
0484: }
0485: };
0486:
0487: /**
0488: * Is t a subtype of every type in given list `ts'?<br>
0489: * (not defined for Method and ForAll types)<br>
0490: * Allows unchecked conversions.
0491: */
0492: public boolean isSubtypeUnchecked(Type t, List<Type> ts, Warner warn) {
0493: for (List<Type> l = ts; l.nonEmpty(); l = l.tail)
0494: if (!isSubtypeUnchecked(t, l.head, warn))
0495: return false;
0496: return true;
0497: }
0498:
0499: /**
0500: * Are corresponding elements of ts subtypes of ss? If lists are
0501: * of different length, return false.
0502: */
0503: public boolean isSubtypes(List<Type> ts, List<Type> ss) {
0504: while (ts.tail != null
0505: && ss.tail != null
0506: /*inlined: ts.nonEmpty() && ss.nonEmpty()*/&& isSubtype(
0507: ts.head, ss.head)) {
0508: ts = ts.tail;
0509: ss = ss.tail;
0510: }
0511: return ts.tail == null && ss.tail == null;
0512: /*inlined: ts.isEmpty() && ss.isEmpty();*/
0513: }
0514:
0515: /**
0516: * Are corresponding elements of ts subtypes of ss, allowing
0517: * unchecked conversions? If lists are of different length,
0518: * return false.
0519: **/
0520: public boolean isSubtypesUnchecked(List<Type> ts, List<Type> ss,
0521: Warner warn) {
0522: while (ts.tail != null
0523: && ss.tail != null
0524: /*inlined: ts.nonEmpty() && ss.nonEmpty()*/&& isSubtypeUnchecked(
0525: ts.head, ss.head, warn)) {
0526: ts = ts.tail;
0527: ss = ss.tail;
0528: }
0529: return ts.tail == null && ss.tail == null;
0530: /*inlined: ts.isEmpty() && ss.isEmpty();*/
0531: }
0532:
0533: // </editor-fold>
0534:
0535: // <editor-fold defaultstate="collapsed" desc="isSuperType">
0536: /**
0537: * Is t a supertype of s?
0538: */
0539: public boolean isSuperType(Type t, Type s) {
0540: switch (t.tag) {
0541: case ERROR:
0542: return true;
0543: case UNDETVAR: {
0544: UndetVar undet = (UndetVar) t;
0545: if (t == s || undet.qtype == s || s.tag == ERROR
0546: || s.tag == BOT)
0547: return true;
0548: if (undet.inst != null)
0549: return isSubtype(s, undet.inst);
0550: undet.lobounds = undet.lobounds.prepend(s);
0551: return true;
0552: }
0553: default:
0554: return isSubtype(s, t);
0555: }
0556: }
0557:
0558: // </editor-fold>
0559:
0560: // <editor-fold defaultstate="collapsed" desc="isSameType">
0561: /**
0562: * Are corresponding elements of the lists the same type? If
0563: * lists are of different length, return false.
0564: */
0565: public boolean isSameTypes(List<Type> ts, List<Type> ss) {
0566: while (ts.tail != null
0567: && ss.tail != null
0568: /*inlined: ts.nonEmpty() && ss.nonEmpty()*/&& isSameType(
0569: ts.head, ss.head)) {
0570: ts = ts.tail;
0571: ss = ss.tail;
0572: }
0573: return ts.tail == null && ss.tail == null;
0574: /*inlined: ts.isEmpty() && ss.isEmpty();*/
0575: }
0576:
0577: /**
0578: * Is t the same type as s?
0579: */
0580: public boolean isSameType(Type t, Type s) {
0581: return isSameType.visit(t, s);
0582: }
0583:
0584: // where
0585: private TypeRelation isSameType = new TypeRelation() {
0586:
0587: public Boolean visitType(Type t, Type s) {
0588: if (t == s)
0589: return true;
0590:
0591: if (s.tag >= firstPartialTag)
0592: return visit(s, t);
0593:
0594: switch (t.tag) {
0595: case BYTE:
0596: case CHAR:
0597: case SHORT:
0598: case INT:
0599: case LONG:
0600: case FLOAT:
0601: case DOUBLE:
0602: case BOOLEAN:
0603: case VOID:
0604: case BOT:
0605: case NONE:
0606: return t.tag == s.tag;
0607: case TYPEVAR:
0608: return s.isSuperBound() && !s.isExtendsBound()
0609: && visit(t, upperBound(s));
0610: default:
0611: throw new AssertionError("isSameType " + t.tag);
0612: }
0613: }
0614:
0615: @Override
0616: public Boolean visitWildcardType(WildcardType t, Type s) {
0617: if (s.tag >= firstPartialTag)
0618: return visit(s, t);
0619: else
0620: return false;
0621: }
0622:
0623: @Override
0624: public Boolean visitClassType(ClassType t, Type s) {
0625: if (t == s)
0626: return true;
0627:
0628: if (s.tag >= firstPartialTag)
0629: return visit(s, t);
0630:
0631: if (s.isSuperBound() && !s.isExtendsBound())
0632: return visit(t, upperBound(s))
0633: && visit(t, lowerBound(s));
0634:
0635: if (t.isCompound() && s.isCompound()) {
0636: if (!visit(super type(t), super type(s)))
0637: return false;
0638:
0639: HashSet<SingletonType> set = new HashSet<SingletonType>();
0640: for (Type x : interfaces(t))
0641: set.add(new SingletonType(x));
0642: for (Type x : interfaces(s)) {
0643: if (!set.remove(new SingletonType(x)))
0644: return false;
0645: }
0646: return (set.size() == 0);
0647: }
0648: return t.tsym == s.tsym
0649: && visit(t.getEnclosingType(), s.getEnclosingType())
0650: && containsTypeEquivalent(t.getTypeArguments(), s
0651: .getTypeArguments());
0652: }
0653:
0654: @Override
0655: public Boolean visitArrayType(ArrayType t, Type s) {
0656: if (t == s)
0657: return true;
0658:
0659: if (s.tag >= firstPartialTag)
0660: return visit(s, t);
0661:
0662: return s.tag == ARRAY
0663: && containsTypeEquivalent(t.elemtype, elemtype(s));
0664: }
0665:
0666: @Override
0667: public Boolean visitMethodType(MethodType t, Type s) {
0668: // isSameType for methods does not take thrown
0669: // exceptions into account!
0670: return hasSameArgs(t, s)
0671: && visit(t.getReturnType(), s.getReturnType());
0672: }
0673:
0674: @Override
0675: public Boolean visitPackageType(PackageType t, Type s) {
0676: return t == s;
0677: }
0678:
0679: @Override
0680: public Boolean visitForAll(ForAll t, Type s) {
0681: if (s.tag != FORALL)
0682: return false;
0683:
0684: ForAll forAll = (ForAll) s;
0685: return hasSameBounds(t, forAll)
0686: && visit(t.qtype, subst(forAll.qtype, forAll.tvars,
0687: t.tvars));
0688: }
0689:
0690: @Override
0691: public Boolean visitUndetVar(UndetVar t, Type s) {
0692: if (s.tag == WILDCARD)
0693: // FIXME, this might be leftovers from before capture conversion
0694: return false;
0695:
0696: if (t == s || t.qtype == s || s.tag == ERROR
0697: || s.tag == UNKNOWN)
0698: return true;
0699:
0700: if (t.inst != null)
0701: return visit(t.inst, s);
0702:
0703: t.inst = fromUnknownFun.apply(s);
0704: for (List<Type> l = t.lobounds; l.nonEmpty(); l = l.tail) {
0705: if (!isSubtype(l.head, t.inst))
0706: return false;
0707: }
0708: for (List<Type> l = t.hibounds; l.nonEmpty(); l = l.tail) {
0709: if (!isSubtype(t.inst, l.head))
0710: return false;
0711: }
0712: return true;
0713: }
0714:
0715: @Override
0716: public Boolean visitErrorType(ErrorType t, Type s) {
0717: return true;
0718: }
0719: };
0720: // </editor-fold>
0721:
0722: // <editor-fold defaultstate="collapsed" desc="fromUnknownFun">
0723: /**
0724: * A mapping that turns all unknown types in this type to fresh
0725: * unknown variables.
0726: */
0727: public Mapping fromUnknownFun = new Mapping("fromUnknownFun") {
0728: public Type apply(Type t) {
0729: if (t.tag == UNKNOWN)
0730: return new UndetVar(t);
0731: else
0732: return t.map(this );
0733: }
0734: };
0735:
0736: // </editor-fold>
0737:
0738: // <editor-fold defaultstate="collapsed" desc="Contains Type">
0739: public boolean containedBy(Type t, Type s) {
0740: switch (t.tag) {
0741: case UNDETVAR:
0742: if (s.tag == WILDCARD) {
0743: UndetVar undetvar = (UndetVar) t;
0744:
0745: // Because of wildcard capture, s must be on the left
0746: // hand side of an assignment. Furthermore, t is an
0747: // underconstrained type variable, for example, one
0748: // that is only used in the return type of a method.
0749: // If the type variable is truly underconstrained, it
0750: // cannot have any low bounds:
0751: assert undetvar.lobounds.isEmpty() : undetvar;
0752:
0753: undetvar.inst = glb(upperBound(s), undetvar.inst);
0754: return true;
0755: } else {
0756: return isSameType(t, s);
0757: }
0758: case ERROR:
0759: return true;
0760: default:
0761: return containsType(s, t);
0762: }
0763: }
0764:
0765: boolean containsType(List<Type> ts, List<Type> ss) {
0766: while (ts.nonEmpty() && ss.nonEmpty()
0767: && containsType(ts.head, ss.head)) {
0768: ts = ts.tail;
0769: ss = ss.tail;
0770: }
0771: return ts.isEmpty() && ss.isEmpty();
0772: }
0773:
0774: /**
0775: * Check if t contains s.
0776: *
0777: * <p>T contains S if:
0778: *
0779: * <p>{@code L(T) <: L(S) && U(S) <: U(T)}
0780: *
0781: * <p>This relation is only used by ClassType.isSubtype(), that
0782: * is,
0783: *
0784: * <p>{@code C<S> <: C<T> if T contains S.}
0785: *
0786: * <p>Because of F-bounds, this relation can lead to infinite
0787: * recursion. Thus we must somehow break that recursion. Notice
0788: * that containsType() is only called from ClassType.isSubtype().
0789: * Since the arguments have already been checked against their
0790: * bounds, we know:
0791: *
0792: * <p>{@code U(S) <: U(T) if T is "super" bound (U(T) *is* the bound)}
0793: *
0794: * <p>{@code L(T) <: L(S) if T is "extends" bound (L(T) is bottom)}
0795: *
0796: * @param t a type
0797: * @param s a type
0798: */
0799: public boolean containsType(Type t, Type s) {
0800: return containsType.visit(t, s);
0801: }
0802:
0803: // where
0804: private TypeRelation containsType = new TypeRelation() {
0805:
0806: private Type U(Type t) {
0807: while (t.tag == WILDCARD) {
0808: WildcardType w = (WildcardType) t;
0809: if (w.isSuperBound())
0810: return w.bound == null ? syms.objectType
0811: : w.bound.bound;
0812: else
0813: t = w.type;
0814: }
0815: return t;
0816: }
0817:
0818: private Type L(Type t) {
0819: while (t.tag == WILDCARD) {
0820: WildcardType w = (WildcardType) t;
0821: if (w.isExtendsBound())
0822: return syms.botType;
0823: else
0824: t = w.type;
0825: }
0826: return t;
0827: }
0828:
0829: public Boolean visitType(Type t, Type s) {
0830: if (s.tag >= firstPartialTag)
0831: return containedBy(s, t);
0832: else
0833: return isSameType(t, s);
0834: }
0835:
0836: void debugContainsType(WildcardType t, Type s) {
0837: System.err.println();
0838: System.err.format(" does %s contain %s?%n", t, s);
0839: System.err.format(" %s U(%s) <: U(%s) %s = %s%n",
0840: upperBound(s), s, t, U(t), t.isSuperBound()
0841: || isSubtypeNoCapture(upperBound(s), U(t)));
0842: System.err.format(" %s L(%s) <: L(%s) %s = %s%n", L(t), t,
0843: s, lowerBound(s), t.isExtendsBound()
0844: || isSubtypeNoCapture(L(t), lowerBound(s)));
0845: System.err.println();
0846: }
0847:
0848: @Override
0849: public Boolean visitWildcardType(WildcardType t, Type s) {
0850: if (s.tag >= firstPartialTag)
0851: return containedBy(s, t);
0852: else {
0853: // debugContainsType(t, s);
0854: return isSameWildcard(t, s)
0855: || isCaptureOf(s, t)
0856: || ((t.isExtendsBound() || isSubtypeNoCapture(
0857: L(t), lowerBound(s))) && (t
0858: .isSuperBound() || isSubtypeNoCapture(
0859: upperBound(s), U(t))));
0860: }
0861: }
0862:
0863: @Override
0864: public Boolean visitUndetVar(UndetVar t, Type s) {
0865: if (s.tag != WILDCARD)
0866: return isSameType(t, s);
0867: else
0868: return false;
0869: }
0870:
0871: @Override
0872: public Boolean visitErrorType(ErrorType t, Type s) {
0873: return true;
0874: }
0875: };
0876:
0877: public boolean isCaptureOf(Type s, WildcardType t) {
0878: if (s.tag != TYPEVAR || !(s instanceof CapturedType))
0879: return false;
0880: return isSameWildcard(t, ((CapturedType) s).wildcard);
0881: }
0882:
0883: public boolean isSameWildcard(WildcardType t, Type s) {
0884: if (s.tag != WILDCARD)
0885: return false;
0886: WildcardType w = (WildcardType) s;
0887: return w.kind == t.kind && w.type == t.type;
0888: }
0889:
0890: public boolean containsTypeEquivalent(List<Type> ts, List<Type> ss) {
0891: while (ts.nonEmpty() && ss.nonEmpty()
0892: && containsTypeEquivalent(ts.head, ss.head)) {
0893: ts = ts.tail;
0894: ss = ss.tail;
0895: }
0896: return ts.isEmpty() && ss.isEmpty();
0897: }
0898:
0899: // </editor-fold>
0900:
0901: // <editor-fold defaultstate="collapsed" desc="isCastable">
0902: public boolean isCastable(Type t, Type s) {
0903: return isCastable(t, s, Warner.noWarnings);
0904: }
0905:
0906: /**
0907: * Is t is castable to s?<br>
0908: * s is assumed to be an erased type.<br>
0909: * (not defined for Method and ForAll types).
0910: */
0911: public boolean isCastable(Type t, Type s, Warner warn) {
0912: if (t == s)
0913: return true;
0914:
0915: if (t.isPrimitive() != s.isPrimitive())
0916: return allowBoxing && isConvertible(t, s, warn);
0917:
0918: if (warn != warnStack.head) {
0919: try {
0920: warnStack = warnStack.prepend(warn);
0921: return isCastable.visit(t, s);
0922: } finally {
0923: warnStack = warnStack.tail;
0924: }
0925: } else {
0926: return isCastable.visit(t, s);
0927: }
0928: }
0929:
0930: // where
0931: private TypeRelation isCastable = new TypeRelation() {
0932:
0933: public Boolean visitType(Type t, Type s) {
0934: if (s.tag == ERROR)
0935: return true;
0936:
0937: switch (t.tag) {
0938: case BYTE:
0939: case CHAR:
0940: case SHORT:
0941: case INT:
0942: case LONG:
0943: case FLOAT:
0944: case DOUBLE:
0945: return s.tag <= DOUBLE;
0946: case BOOLEAN:
0947: return s.tag == BOOLEAN;
0948: case VOID:
0949: return false;
0950: case BOT:
0951: return isSubtype(t, s);
0952: default:
0953: throw new AssertionError();
0954: }
0955: }
0956:
0957: @Override
0958: public Boolean visitWildcardType(WildcardType t, Type s) {
0959: return isCastable(upperBound(t), s, warnStack.head);
0960: }
0961:
0962: @Override
0963: public Boolean visitClassType(ClassType t, Type s) {
0964: if (s.tag == ERROR || s.tag == BOT)
0965: return true;
0966:
0967: if (s.tag == TYPEVAR) {
0968: if (isCastable(s.getUpperBound(), t, Warner.noWarnings)) {
0969: warnStack.head.warnUnchecked();
0970: return true;
0971: } else {
0972: return false;
0973: }
0974: }
0975:
0976: if (t.isCompound()) {
0977: if (!visit(super type(t), s))
0978: return false;
0979: for (Type intf : interfaces(t)) {
0980: if (!visit(intf, s))
0981: return false;
0982: }
0983: return true;
0984: }
0985:
0986: if (s.isCompound()) {
0987: // call recursively to reuse the above code
0988: return visitClassType((ClassType) s, t);
0989: }
0990:
0991: if (s.tag == CLASS || s.tag == ARRAY) {
0992: boolean upcast;
0993: if ((upcast = isSubtype(erasure(t), erasure(s)))
0994: || isSubtype(erasure(s), erasure(t))) {
0995: if (!upcast && s.tag == ARRAY) {
0996: if (!isReifiable(s))
0997: warnStack.head.warnUnchecked();
0998: return true;
0999: } else if (s.isRaw()) {
1000: return true;
1001: } else if (t.isRaw()) {
1002: if (!isUnbounded(s))
1003: warnStack.head.warnUnchecked();
1004: return true;
1005: }
1006: // Assume |a| <: |b|
1007: final Type a = upcast ? t : s;
1008: final Type b = upcast ? s : t;
1009: final boolean HIGH = true;
1010: final boolean LOW = false;
1011: final boolean DONT_REWRITE_TYPEVARS = false;
1012: Type aHigh = rewriteQuantifiers(a, HIGH,
1013: DONT_REWRITE_TYPEVARS);
1014: Type aLow = rewriteQuantifiers(a, LOW,
1015: DONT_REWRITE_TYPEVARS);
1016: Type bHigh = rewriteQuantifiers(b, HIGH,
1017: DONT_REWRITE_TYPEVARS);
1018: Type bLow = rewriteQuantifiers(b, LOW,
1019: DONT_REWRITE_TYPEVARS);
1020: Type lowSub = asSub(bLow, aLow.tsym);
1021: Type highSub = (lowSub == null) ? null : asSub(
1022: bHigh, aHigh.tsym);
1023: if (highSub == null) {
1024: final boolean REWRITE_TYPEVARS = true;
1025: aHigh = rewriteQuantifiers(a, HIGH,
1026: REWRITE_TYPEVARS);
1027: aLow = rewriteQuantifiers(a, LOW,
1028: REWRITE_TYPEVARS);
1029: bHigh = rewriteQuantifiers(b, HIGH,
1030: REWRITE_TYPEVARS);
1031: bLow = rewriteQuantifiers(b, LOW,
1032: REWRITE_TYPEVARS);
1033: lowSub = asSub(bLow, aLow.tsym);
1034: highSub = (lowSub == null) ? null : asSub(
1035: bHigh, aHigh.tsym);
1036: }
1037: if (highSub != null) {
1038: assert a.tsym == highSub.tsym
1039: && a.tsym == lowSub.tsym : a.tsym
1040: + " != " + highSub.tsym + " != "
1041: + lowSub.tsym;
1042: if (!disjointTypes(aHigh.getTypeArguments(),
1043: highSub.getTypeArguments())
1044: && !disjointTypes(aHigh
1045: .getTypeArguments(), lowSub
1046: .getTypeArguments())
1047: && !disjointTypes(aLow
1048: .getTypeArguments(), highSub
1049: .getTypeArguments())
1050: && !disjointTypes(aLow
1051: .getTypeArguments(), lowSub
1052: .getTypeArguments())) {
1053: if (upcast ? giveWarning(a, highSub)
1054: || giveWarning(a, lowSub)
1055: : giveWarning(highSub, a)
1056: || giveWarning(lowSub, a))
1057: warnStack.head.warnUnchecked();
1058: return true;
1059: }
1060: }
1061: if (isReifiable(s))
1062: return isSubtypeUnchecked(a, b);
1063: else
1064: return isSubtypeUnchecked(a, b, warnStack.head);
1065: }
1066:
1067: // Sidecast
1068: if (s.tag == CLASS) {
1069: if ((s.tsym.flags() & INTERFACE) != 0) {
1070: return ((t.tsym.flags() & FINAL) == 0) ? sideCast(
1071: t, s, warnStack.head)
1072: : sideCastFinal(t, s, warnStack.head);
1073: } else if ((t.tsym.flags() & INTERFACE) != 0) {
1074: return ((s.tsym.flags() & FINAL) == 0) ? sideCast(
1075: t, s, warnStack.head)
1076: : sideCastFinal(t, s, warnStack.head);
1077: } else {
1078: // unrelated class types
1079: return false;
1080: }
1081: }
1082: }
1083: return false;
1084: }
1085:
1086: @Override
1087: public Boolean visitArrayType(ArrayType t, Type s) {
1088: switch (s.tag) {
1089: case ERROR:
1090: case BOT:
1091: return true;
1092: case TYPEVAR:
1093: if (isCastable(s, t, Warner.noWarnings)) {
1094: warnStack.head.warnUnchecked();
1095: return true;
1096: } else {
1097: return false;
1098: }
1099: case CLASS:
1100: return isSubtype(t, s);
1101: case ARRAY:
1102: if (elemtype(t).tag <= lastBaseTag) {
1103: return elemtype(t).tag == elemtype(s).tag;
1104: } else {
1105: return visit(elemtype(t), elemtype(s));
1106: }
1107: default:
1108: return false;
1109: }
1110: }
1111:
1112: @Override
1113: public Boolean visitTypeVar(TypeVar t, Type s) {
1114: switch (s.tag) {
1115: case ERROR:
1116: case BOT:
1117: return true;
1118: case TYPEVAR:
1119: if (isSubtype(t, s)) {
1120: return true;
1121: } else if (isCastable(t.bound, s, Warner.noWarnings)) {
1122: warnStack.head.warnUnchecked();
1123: return true;
1124: } else {
1125: return false;
1126: }
1127: default:
1128: return isCastable(t.bound, s, warnStack.head);
1129: }
1130: }
1131:
1132: @Override
1133: public Boolean visitErrorType(ErrorType t, Type s) {
1134: return true;
1135: }
1136: };
1137:
1138: // </editor-fold>
1139:
1140: // <editor-fold defaultstate="collapsed" desc="disjointTypes">
1141: public boolean disjointTypes(List<Type> ts, List<Type> ss) {
1142: while (ts.tail != null && ss.tail != null) {
1143: if (disjointType(ts.head, ss.head))
1144: return true;
1145: ts = ts.tail;
1146: ss = ss.tail;
1147: }
1148: return false;
1149: }
1150:
1151: /**
1152: * Two types or wildcards are considered disjoint if it can be
1153: * proven that no type can be contained in both. It is
1154: * conservative in that it is allowed to say that two types are
1155: * not disjoint, even though they actually are.
1156: *
1157: * The type C<X> is castable to C<Y> exactly if X and Y are not
1158: * disjoint.
1159: */
1160: public boolean disjointType(Type t, Type s) {
1161: return disjointType.visit(t, s);
1162: }
1163:
1164: // where
1165: private TypeRelation disjointType = new TypeRelation() {
1166:
1167: private Set<TypePair> cache = new HashSet<TypePair>();
1168:
1169: public Boolean visitType(Type t, Type s) {
1170: if (s.tag == WILDCARD)
1171: return visit(s, t);
1172: else
1173: return notSoftSubtypeRecursive(t, s)
1174: || notSoftSubtypeRecursive(s, t);
1175: }
1176:
1177: private boolean isCastableRecursive(Type t, Type s) {
1178: TypePair pair = new TypePair(t, s);
1179: if (cache.add(pair)) {
1180: try {
1181: return Types.this .isCastable(t, s);
1182: } finally {
1183: cache.remove(pair);
1184: }
1185: } else {
1186: return true;
1187: }
1188: }
1189:
1190: private boolean notSoftSubtypeRecursive(Type t, Type s) {
1191: TypePair pair = new TypePair(t, s);
1192: if (cache.add(pair)) {
1193: try {
1194: return Types.this .notSoftSubtype(t, s);
1195: } finally {
1196: cache.remove(pair);
1197: }
1198: } else {
1199: return false;
1200: }
1201: }
1202:
1203: @Override
1204: public Boolean visitWildcardType(WildcardType t, Type s) {
1205: if (t.isUnbound())
1206: return false;
1207:
1208: if (s.tag != WILDCARD) {
1209: if (t.isExtendsBound())
1210: return notSoftSubtypeRecursive(s, t.type);
1211: else
1212: // isSuperBound()
1213: return notSoftSubtypeRecursive(t.type, s);
1214: }
1215:
1216: if (s.isUnbound())
1217: return false;
1218:
1219: if (t.isExtendsBound()) {
1220: if (s.isExtendsBound())
1221: return !isCastableRecursive(t.type, upperBound(s));
1222: else if (s.isSuperBound())
1223: return notSoftSubtypeRecursive(lowerBound(s),
1224: t.type);
1225: } else if (t.isSuperBound()) {
1226: if (s.isExtendsBound())
1227: return notSoftSubtypeRecursive(t.type,
1228: upperBound(s));
1229: }
1230: return false;
1231: }
1232: };
1233:
1234: // </editor-fold>
1235:
1236: // <editor-fold defaultstate="collapsed" desc="lowerBoundArgtypes">
1237: /**
1238: * Returns the lower bounds of the formals of a method.
1239: */
1240: public List<Type> lowerBoundArgtypes(Type t) {
1241: return map(t.getParameterTypes(), lowerBoundMapping);
1242: }
1243:
1244: private final Mapping lowerBoundMapping = new Mapping("lowerBound") {
1245: public Type apply(Type t) {
1246: return lowerBound(t);
1247: }
1248: };
1249:
1250: // </editor-fold>
1251:
1252: // <editor-fold defaultstate="collapsed" desc="notSoftSubtype">
1253: /**
1254: * This relation answers the question: is impossible that
1255: * something of type `t' can be a subtype of `s'? This is
1256: * different from the question "is `t' not a subtype of `s'?"
1257: * when type variables are involved: Integer is not a subtype of T
1258: * where <T extends Number> but it is not true that Integer cannot
1259: * possibly be a subtype of T.
1260: */
1261: public boolean notSoftSubtype(Type t, Type s) {
1262: if (t == s)
1263: return false;
1264: if (t.tag == TYPEVAR) {
1265: TypeVar tv = (TypeVar) t;
1266: if (s.tag == TYPEVAR)
1267: s = s.getUpperBound();
1268: return !isCastable(tv.bound, s, Warner.noWarnings);
1269: }
1270: if (s.tag != WILDCARD)
1271: s = upperBound(s);
1272: if (s.tag == TYPEVAR)
1273: s = s.getUpperBound();
1274: return !isSubtype(t, s);
1275: }
1276:
1277: // </editor-fold>
1278:
1279: // <editor-fold defaultstate="collapsed" desc="isReifiable">
1280: public boolean isReifiable(Type t) {
1281: return isReifiable.visit(t);
1282: }
1283:
1284: // where
1285: private UnaryVisitor<Boolean> isReifiable = new UnaryVisitor<Boolean>() {
1286:
1287: public Boolean visitType(Type t, Void ignored) {
1288: return true;
1289: }
1290:
1291: @Override
1292: public Boolean visitClassType(ClassType t, Void ignored) {
1293: if (!t.isParameterized())
1294: return true;
1295:
1296: for (Type param : t.allparams()) {
1297: if (!param.isUnbound())
1298: return false;
1299: }
1300: return true;
1301: }
1302:
1303: @Override
1304: public Boolean visitArrayType(ArrayType t, Void ignored) {
1305: return visit(t.elemtype);
1306: }
1307:
1308: @Override
1309: public Boolean visitTypeVar(TypeVar t, Void ignored) {
1310: return false;
1311: }
1312: };
1313:
1314: // </editor-fold>
1315:
1316: // <editor-fold defaultstate="collapsed" desc="Array Utils">
1317: public boolean isArray(Type t) {
1318: while (t.tag == WILDCARD)
1319: t = upperBound(t);
1320: return t.tag == ARRAY;
1321: }
1322:
1323: /**
1324: * The element type of an array.
1325: */
1326: public Type elemtype(Type t) {
1327: switch (t.tag) {
1328: case WILDCARD:
1329: return elemtype(upperBound(t));
1330: case ARRAY:
1331: return ((ArrayType) t).elemtype;
1332: case FORALL:
1333: return elemtype(((ForAll) t).qtype);
1334: case ERROR:
1335: return t;
1336: default:
1337: return null;
1338: }
1339: }
1340:
1341: /**
1342: * Mapping to take element type of an arraytype
1343: */
1344: private Mapping elemTypeFun = new Mapping("elemTypeFun") {
1345: public Type apply(Type t) {
1346: return elemtype(t);
1347: }
1348: };
1349:
1350: /**
1351: * The number of dimensions of an array type.
1352: */
1353: public int dimensions(Type t) {
1354: int result = 0;
1355: while (t.tag == ARRAY) {
1356: result++;
1357: t = elemtype(t);
1358: }
1359: return result;
1360: }
1361:
1362: // </editor-fold>
1363:
1364: // <editor-fold defaultstate="collapsed" desc="asSuper">
1365: /**
1366: * Return the (most specific) base type of t that starts with the
1367: * given symbol. If none exists, return null.
1368: *
1369: * @param t a type
1370: * @param sym a symbol
1371: */
1372: public Type asSuper(Type t, Symbol sym) {
1373: return asSuper.visit(t, sym);
1374: }
1375:
1376: // where
1377: private SimpleVisitor<Type, Symbol> asSuper = new SimpleVisitor<Type, Symbol>() {
1378:
1379: public Type visitType(Type t, Symbol sym) {
1380: return null;
1381: }
1382:
1383: @Override
1384: public Type visitClassType(ClassType t, Symbol sym) {
1385: if (t.tsym == sym)
1386: return t;
1387:
1388: Type st = super type(t);
1389: if (st.tag == CLASS || st.tag == ERROR) {
1390: Type x = asSuper(st, sym);
1391: if (x != null)
1392: return x;
1393: }
1394: if ((sym.flags() & INTERFACE) != 0) {
1395: for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail) {
1396: Type x = asSuper(l.head, sym);
1397: if (x != null)
1398: return x;
1399: }
1400: }
1401: return null;
1402: }
1403:
1404: @Override
1405: public Type visitArrayType(ArrayType t, Symbol sym) {
1406: return isSubtype(t, sym.type) ? sym.type : null;
1407: }
1408:
1409: @Override
1410: public Type visitTypeVar(TypeVar t, Symbol sym) {
1411: return asSuper(t.bound, sym);
1412: }
1413:
1414: @Override
1415: public Type visitErrorType(ErrorType t, Symbol sym) {
1416: return t;
1417: }
1418: };
1419:
1420: /**
1421: * Return the base type of t or any of its outer types that starts
1422: * with the given symbol. If none exists, return null.
1423: *
1424: * @param t a type
1425: * @param sym a symbol
1426: */
1427: public Type asOuterSuper(Type t, Symbol sym) {
1428: switch (t.tag) {
1429: case CLASS:
1430: do {
1431: Type s = asSuper(t, sym);
1432: if (s != null)
1433: return s;
1434: t = t.getEnclosingType();
1435: } while (t.tag == CLASS);
1436: return null;
1437: case ARRAY:
1438: return isSubtype(t, sym.type) ? sym.type : null;
1439: case TYPEVAR:
1440: return asSuper(t, sym);
1441: case ERROR:
1442: return t;
1443: default:
1444: return null;
1445: }
1446: }
1447:
1448: /**
1449: * Return the base type of t or any of its enclosing types that
1450: * starts with the given symbol. If none exists, return null.
1451: *
1452: * @param t a type
1453: * @param sym a symbol
1454: */
1455: public Type asEnclosingSuper(Type t, Symbol sym) {
1456: switch (t.tag) {
1457: case CLASS:
1458: do {
1459: Type s = asSuper(t, sym);
1460: if (s != null)
1461: return s;
1462: Type outer = t.getEnclosingType();
1463: t = (outer.tag == CLASS) ? outer : (t.tsym.owner
1464: .enclClass() != null) ? t.tsym.owner
1465: .enclClass().type : Type.noType;
1466: } while (t.tag == CLASS);
1467: return null;
1468: case ARRAY:
1469: return isSubtype(t, sym.type) ? sym.type : null;
1470: case TYPEVAR:
1471: return asSuper(t, sym);
1472: case ERROR:
1473: return t;
1474: default:
1475: return null;
1476: }
1477: }
1478:
1479: // </editor-fold>
1480:
1481: // <editor-fold defaultstate="collapsed" desc="memberType">
1482: /**
1483: * The type of given symbol, seen as a member of t.
1484: *
1485: * @param t a type
1486: * @param sym a symbol
1487: */
1488: public Type memberType(Type t, Symbol sym) {
1489: return (sym.flags() & STATIC) != 0 ? sym.type : memberType
1490: .visit(t, sym);
1491: }
1492:
1493: // where
1494: private SimpleVisitor<Type, Symbol> memberType = new SimpleVisitor<Type, Symbol>() {
1495:
1496: public Type visitType(Type t, Symbol sym) {
1497: return sym.type;
1498: }
1499:
1500: @Override
1501: public Type visitWildcardType(WildcardType t, Symbol sym) {
1502: return memberType(upperBound(t), sym);
1503: }
1504:
1505: @Override
1506: public Type visitClassType(ClassType t, Symbol sym) {
1507: Symbol owner = sym.owner;
1508: long flags = sym.flags();
1509: if (((flags & STATIC) == 0) && owner.type.isParameterized()) {
1510: Type base = asOuterSuper(t, owner);
1511: if (base != null) {
1512: List<Type> ownerParams = owner.type.allparams();
1513: List<Type> baseParams = base.allparams();
1514: if (ownerParams.nonEmpty()) {
1515: if (baseParams.isEmpty()) {
1516: // then base is a raw type
1517: return erasure(sym.type);
1518: } else {
1519: return subst(sym.type, ownerParams,
1520: baseParams);
1521: }
1522: }
1523: }
1524: }
1525: return sym.type;
1526: }
1527:
1528: @Override
1529: public Type visitTypeVar(TypeVar t, Symbol sym) {
1530: return memberType(t.bound, sym);
1531: }
1532:
1533: @Override
1534: public Type visitErrorType(ErrorType t, Symbol sym) {
1535: return t;
1536: }
1537: };
1538:
1539: // </editor-fold>
1540:
1541: // <editor-fold defaultstate="collapsed" desc="isAssignable">
1542: public boolean isAssignable(Type t, Type s) {
1543: return isAssignable(t, s, Warner.noWarnings);
1544: }
1545:
1546: /**
1547: * Is t assignable to s?<br>
1548: * Equivalent to subtype except for constant values and raw
1549: * types.<br>
1550: * (not defined for Method and ForAll types)
1551: */
1552: public boolean isAssignable(Type t, Type s, Warner warn) {
1553: if (t.tag == ERROR)
1554: return true;
1555: if (t.tag <= INT && t.constValue() != null) {
1556: int value = ((Number) t.constValue()).intValue();
1557: switch (s.tag) {
1558: case BYTE:
1559: if (Byte.MIN_VALUE <= value && value <= Byte.MAX_VALUE)
1560: return true;
1561: break;
1562: case CHAR:
1563: if (Character.MIN_VALUE <= value
1564: && value <= Character.MAX_VALUE)
1565: return true;
1566: break;
1567: case SHORT:
1568: if (Short.MIN_VALUE <= value
1569: && value <= Short.MAX_VALUE)
1570: return true;
1571: break;
1572: case INT:
1573: return true;
1574: case CLASS:
1575: switch (unboxedType(s).tag) {
1576: case BYTE:
1577: case CHAR:
1578: case SHORT:
1579: return isAssignable(t, unboxedType(s), warn);
1580: }
1581: break;
1582: }
1583: }
1584: return isConvertible(t, s, warn);
1585: }
1586:
1587: // </editor-fold>
1588:
1589: // <editor-fold defaultstate="collapsed" desc="erasure">
1590: /**
1591: * The erasure of t {@code |t|} -- the type that results when all
1592: * type parameters in t are deleted.
1593: */
1594: public Type erasure(Type t) {
1595: if (t.tag <= lastBaseTag)
1596: return t; /* fast special case */
1597: else
1598: return erasure.visit(t);
1599: }
1600:
1601: // where
1602: private UnaryVisitor<Type> erasure = new UnaryVisitor<Type>() {
1603: public Type visitType(Type t, Void ignored) {
1604: if (t.tag <= lastBaseTag)
1605: return t; /*fast special case*/
1606: else
1607: return t.map(erasureFun);
1608: }
1609:
1610: @Override
1611: public Type visitWildcardType(WildcardType t, Void ignored) {
1612: return erasure(upperBound(t));
1613: }
1614:
1615: @Override
1616: public Type visitClassType(ClassType t, Void ignored) {
1617: return t.tsym.erasure(Types.this );
1618: }
1619:
1620: @Override
1621: public Type visitTypeVar(TypeVar t, Void ignored) {
1622: return erasure(t.bound);
1623: }
1624:
1625: @Override
1626: public Type visitErrorType(ErrorType t, Void ignored) {
1627: return t;
1628: }
1629: };
1630: private Mapping erasureFun = new Mapping("erasure") {
1631: public Type apply(Type t) {
1632: return erasure(t);
1633: }
1634: };
1635:
1636: public List<Type> erasure(List<Type> ts) {
1637: return Type.map(ts, erasureFun);
1638: }
1639:
1640: // </editor-fold>
1641:
1642: // <editor-fold defaultstate="collapsed" desc="makeCompoundType">
1643: /**
1644: * Make a compound type from non-empty list of types
1645: *
1646: * @param bounds the types from which the compound type is formed
1647: * @param supertype is objectType if all bounds are interfaces,
1648: * null otherwise.
1649: */
1650: public Type makeCompoundType(List<Type> bounds, Type super type) {
1651: ClassSymbol bc = new ClassSymbol(ABSTRACT | PUBLIC | SYNTHETIC
1652: | COMPOUND | ACYCLIC, Type.moreInfo ? names
1653: .fromString(bounds.toString()) : names.empty,
1654: syms.noSymbol);
1655: if (bounds.head.tag == TYPEVAR)
1656: // error condition, recover
1657: bc.erasure_field = syms.objectType;
1658: else
1659: bc.erasure_field = erasure(bounds.head);
1660: bc.members_field = new Scope(bc);
1661: ClassType bt = (ClassType) bc.type;
1662: bt.allparams_field = List.nil();
1663: if (super type != null) {
1664: bt.super type_field = super type;
1665: bt.interfaces_field = bounds;
1666: } else {
1667: bt.super type_field = bounds.head;
1668: bt.interfaces_field = bounds.tail;
1669: }
1670: assert bt.super type_field.tsym.completer != null
1671: || !bt.super type_field.isInterface() : bt.super type_field;
1672: return bt;
1673: }
1674:
1675: /**
1676: * Same as {@link #makeCompoundType(List,Type)}, except that the
1677: * second parameter is computed directly. Note that this might
1678: * cause a symbol completion. Hence, this version of
1679: * makeCompoundType may not be called during a classfile read.
1680: */
1681: public Type makeCompoundType(List<Type> bounds) {
1682: Type super type = (bounds.head.tsym.flags() & INTERFACE) != 0 ? super type(bounds.head)
1683: : null;
1684: return makeCompoundType(bounds, super type);
1685: }
1686:
1687: /**
1688: * A convenience wrapper for {@link #makeCompoundType(List)}; the
1689: * arguments are converted to a list and passed to the other
1690: * method. Note that this might cause a symbol completion.
1691: * Hence, this version of makeCompoundType may not be called
1692: * during a classfile read.
1693: */
1694: public Type makeCompoundType(Type bound1, Type bound2) {
1695: return makeCompoundType(List.of(bound1, bound2));
1696: }
1697:
1698: // </editor-fold>
1699:
1700: // <editor-fold defaultstate="collapsed" desc="supertype">
1701: public Type super type(Type t) {
1702: return super type.visit(t);
1703: }
1704:
1705: // where
1706: private UnaryVisitor<Type> super type = new UnaryVisitor<Type>() {
1707:
1708: public Type visitType(Type t, Void ignored) {
1709: // A note on wildcards: there is no good way to
1710: // determine a supertype for a super bounded wildcard.
1711: return null;
1712: }
1713:
1714: @Override
1715: public Type visitClassType(ClassType t, Void ignored) {
1716: if (t.super type_field == null) {
1717: Type super type = ((ClassSymbol) t.tsym).getSuperclass();
1718: // An interface has no superclass; its supertype is Object.
1719: if (t.isInterface())
1720: super type = ((ClassType) t.tsym.type).super type_field;
1721: if (t.super type_field == null) {
1722: List<Type> actuals = classBound(t).allparams();
1723: List<Type> formals = t.tsym.type.allparams();
1724: if (actuals.isEmpty()) {
1725: if (formals.isEmpty())
1726: // Should not happen. See comments below in interfaces
1727: t.super type_field = super type;
1728: else
1729: t.super type_field = erasure(super type);
1730: } else {
1731: t.super type_field = subst(super type, formals,
1732: actuals);
1733: }
1734: }
1735: }
1736: return t.super type_field;
1737: }
1738:
1739: /**
1740: * The supertype is always a class type. If the type
1741: * variable's bounds start with a class type, this is also
1742: * the supertype. Otherwise, the supertype is
1743: * java.lang.Object.
1744: */
1745: @Override
1746: public Type visitTypeVar(TypeVar t, Void ignored) {
1747: if (t.bound.tag == TYPEVAR
1748: || (!t.bound.isCompound() && !t.bound.isInterface())) {
1749: return t.bound;
1750: } else {
1751: return super type(t.bound);
1752: }
1753: }
1754:
1755: @Override
1756: public Type visitArrayType(ArrayType t, Void ignored) {
1757: if (t.elemtype.isPrimitive()
1758: || isSameType(t.elemtype, syms.objectType))
1759: return arraySuperType();
1760: else
1761: return new ArrayType(super type(t.elemtype), t.tsym);
1762: }
1763:
1764: @Override
1765: public Type visitErrorType(ErrorType t, Void ignored) {
1766: return t;
1767: }
1768: };
1769:
1770: // </editor-fold>
1771:
1772: // <editor-fold defaultstate="collapsed" desc="interfaces">
1773: /**
1774: * Return the interfaces implemented by this class.
1775: */
1776: public List<Type> interfaces(Type t) {
1777: return interfaces.visit(t);
1778: }
1779:
1780: // where
1781: private UnaryVisitor<List<Type>> interfaces = new UnaryVisitor<List<Type>>() {
1782:
1783: public List<Type> visitType(Type t, Void ignored) {
1784: return List.nil();
1785: }
1786:
1787: @Override
1788: public List<Type> visitClassType(ClassType t, Void ignored) {
1789: if (t.interfaces_field == null) {
1790: List<Type> interfaces = ((ClassSymbol) t.tsym)
1791: .getInterfaces();
1792: if (t.interfaces_field == null) {
1793: // If t.interfaces_field is null, then t must
1794: // be a parameterized type (not to be confused
1795: // with a generic type declaration).
1796: // Terminology:
1797: // Parameterized type: List<String>
1798: // Generic type declaration: class List<E> { ... }
1799: // So t corresponds to List<String> and
1800: // t.tsym.type corresponds to List<E>.
1801: // The reason t must be parameterized type is
1802: // that completion will happen as a side
1803: // effect of calling
1804: // ClassSymbol.getInterfaces. Since
1805: // t.interfaces_field is null after
1806: // completion, we can assume that t is not the
1807: // type of a class/interface declaration.
1808: assert t != t.tsym.type : t.toString();
1809: List<Type> actuals = t.allparams();
1810: List<Type> formals = t.tsym.type.allparams();
1811: if (actuals.isEmpty()) {
1812: if (formals.isEmpty()) {
1813: // In this case t is not generic (nor raw).
1814: // So this should not happen.
1815: t.interfaces_field = interfaces;
1816: } else {
1817: t.interfaces_field = erasure(interfaces);
1818: }
1819: } else {
1820: t.interfaces_field = upperBounds(subst(
1821: interfaces, formals, actuals));
1822: }
1823: }
1824: }
1825: return t.interfaces_field;
1826: }
1827:
1828: @Override
1829: public List<Type> visitTypeVar(TypeVar t, Void ignored) {
1830: if (t.bound.isCompound())
1831: return interfaces(t.bound);
1832:
1833: if (t.bound.isInterface())
1834: return List.of(t.bound);
1835:
1836: return List.nil();
1837: }
1838: };
1839: // </editor-fold>
1840:
1841: // <editor-fold defaultstate="collapsed" desc="isDerivedRaw">
1842: Map<Type, Boolean> isDerivedRawCache = new HashMap<Type, Boolean>();
1843:
1844: public boolean isDerivedRaw(Type t) {
1845: Boolean result = isDerivedRawCache.get(t);
1846: if (result == null) {
1847: result = isDerivedRawInternal(t);
1848: isDerivedRawCache.put(t, result);
1849: }
1850: return result;
1851: }
1852:
1853: public boolean isDerivedRawInternal(Type t) {
1854: if (t.isErroneous())
1855: return false;
1856: return t.isRaw() || super type(t) != null
1857: && isDerivedRaw(super type(t))
1858: || isDerivedRaw(interfaces(t));
1859: }
1860:
1861: public boolean isDerivedRaw(List<Type> ts) {
1862: List<Type> l = ts;
1863: while (l.nonEmpty() && !isDerivedRaw(l.head))
1864: l = l.tail;
1865: return l.nonEmpty();
1866: }
1867:
1868: // </editor-fold>
1869:
1870: // <editor-fold defaultstate="collapsed" desc="setBounds">
1871: /**
1872: * Set the bounds field of the given type variable to reflect a
1873: * (possibly multiple) list of bounds.
1874: * @param t a type variable
1875: * @param bounds the bounds, must be nonempty
1876: * @param supertype is objectType if all bounds are interfaces,
1877: * null otherwise.
1878: */
1879: public void setBounds(TypeVar t, List<Type> bounds, Type super type) {
1880: if (bounds.tail.isEmpty())
1881: t.bound = bounds.head;
1882: else
1883: t.bound = makeCompoundType(bounds, super type);
1884: t.rank_field = -1;
1885: }
1886:
1887: /**
1888: * Same as {@link #setBounds(Type.TypeVar,List,Type)}, except that
1889: * third parameter is computed directly. Note that this test
1890: * might cause a symbol completion. Hence, this version of
1891: * setBounds may not be called during a classfile read.
1892: */
1893: public void setBounds(TypeVar t, List<Type> bounds) {
1894: Type super type = (bounds.head.tsym.flags() & INTERFACE) != 0 ? super type(bounds.head)
1895: : null;
1896: setBounds(t, bounds, super type);
1897: t.rank_field = -1;
1898: }
1899:
1900: // </editor-fold>
1901:
1902: // <editor-fold defaultstate="collapsed" desc="getBounds">
1903: /**
1904: * Return list of bounds of the given type variable.
1905: */
1906: public List<Type> getBounds(TypeVar t) {
1907: if (t.bound.isErroneous() || !t.bound.isCompound())
1908: return List.of(t.bound);
1909: else if ((erasure(t).tsym.flags() & INTERFACE) == 0)
1910: return interfaces(t).prepend(super type(t));
1911: else
1912: // No superclass was given in bounds.
1913: // In this case, supertype is Object, erasure is first interface.
1914: return interfaces(t);
1915: }
1916:
1917: // </editor-fold>
1918:
1919: // <editor-fold defaultstate="collapsed" desc="classBound">
1920: /**
1921: * If the given type is a (possibly selected) type variable,
1922: * return the bounding class of this type, otherwise return the
1923: * type itself.
1924: */
1925: public Type classBound(Type t) {
1926: return classBound.visit(t);
1927: }
1928:
1929: // where
1930: private UnaryVisitor<Type> classBound = new UnaryVisitor<Type>() {
1931:
1932: public Type visitType(Type t, Void ignored) {
1933: return t;
1934: }
1935:
1936: @Override
1937: public Type visitClassType(ClassType t, Void ignored) {
1938: Type outer1 = classBound(t.getEnclosingType());
1939: if (outer1 != t.getEnclosingType())
1940: return new ClassType(outer1, t.getTypeArguments(),
1941: t.tsym);
1942: else
1943: return t;
1944: }
1945:
1946: @Override
1947: public Type visitTypeVar(TypeVar t, Void ignored) {
1948: return classBound(super type(t));
1949: }
1950:
1951: @Override
1952: public Type visitErrorType(ErrorType t, Void ignored) {
1953: return t;
1954: }
1955: };
1956:
1957: // </editor-fold>
1958:
1959: // <editor-fold defaultstate="collapsed" desc="sub signature / override equivalence">
1960: /**
1961: * Returns true iff the first signature is a <em>sub
1962: * signature</em> of the other. This is <b>not</b> an equivalence
1963: * relation.
1964: *
1965: * @see "The Java Language Specification, Third Ed. (8.4.2)."
1966: * @see #overrideEquivalent(Type t, Type s)
1967: * @param t first signature (possibly raw).
1968: * @param s second signature (could be subjected to erasure).
1969: * @return true if t is a sub signature of s.
1970: */
1971: public boolean isSubSignature(Type t, Type s) {
1972: return hasSameArgs(t, s) || hasSameArgs(t, erasure(s));
1973: }
1974:
1975: /**
1976: * Returns true iff these signatures are related by <em>override
1977: * equivalence</em>. This is the natural extension of
1978: * isSubSignature to an equivalence relation.
1979: *
1980: * @see "The Java Language Specification, Third Ed. (8.4.2)."
1981: * @see #isSubSignature(Type t, Type s)
1982: * @param t a signature (possible raw, could be subjected to
1983: * erasure).
1984: * @param s a signature (possible raw, could be subjected to
1985: * erasure).
1986: * @return true if either argument is a sub signature of the other.
1987: */
1988: public boolean overrideEquivalent(Type t, Type s) {
1989: return hasSameArgs(t, s) || hasSameArgs(t, erasure(s))
1990: || hasSameArgs(erasure(t), s);
1991: }
1992:
1993: /**
1994: * Does t have the same arguments as s? It is assumed that both
1995: * types are (possibly polymorphic) method types. Monomorphic
1996: * method types "have the same arguments", if their argument lists
1997: * are equal. Polymorphic method types "have the same arguments",
1998: * if they have the same arguments after renaming all type
1999: * variables of one to corresponding type variables in the other,
2000: * where correspondence is by position in the type parameter list.
2001: */
2002: public boolean hasSameArgs(Type t, Type s) {
2003: return hasSameArgs.visit(t, s);
2004: }
2005:
2006: // where
2007: private TypeRelation hasSameArgs = new TypeRelation() {
2008:
2009: public Boolean visitType(Type t, Type s) {
2010: throw new AssertionError();
2011: }
2012:
2013: @Override
2014: public Boolean visitMethodType(MethodType t, Type s) {
2015: return s.tag == METHOD
2016: && containsTypeEquivalent(t.argtypes, s
2017: .getParameterTypes());
2018: }
2019:
2020: @Override
2021: public Boolean visitForAll(ForAll t, Type s) {
2022: if (s.tag != FORALL)
2023: return false;
2024:
2025: ForAll forAll = (ForAll) s;
2026: return hasSameBounds(t, forAll)
2027: && visit(t.qtype, subst(forAll.qtype, forAll.tvars,
2028: t.tvars));
2029: }
2030:
2031: @Override
2032: public Boolean visitErrorType(ErrorType t, Type s) {
2033: return false;
2034: }
2035: };
2036:
2037: // </editor-fold>
2038:
2039: // <editor-fold defaultstate="collapsed" desc="subst">
2040: public List<Type> subst(List<Type> ts, List<Type> from,
2041: List<Type> to) {
2042: return new Subst(from, to).subst(ts);
2043: }
2044:
2045: /**
2046: * Substitute all occurrences of a type in `from' with the
2047: * corresponding type in `to' in 't'. Match lists `from' and `to'
2048: * from the right: If lists have different length, discard leading
2049: * elements of the longer list.
2050: */
2051: public Type subst(Type t, List<Type> from, List<Type> to) {
2052: return new Subst(from, to).subst(t);
2053: }
2054:
2055: private class Subst extends UnaryVisitor<Type> {
2056: List<Type> from;
2057: List<Type> to;
2058:
2059: public Subst(List<Type> from, List<Type> to) {
2060: int fromLength = from.length();
2061: int toLength = to.length();
2062: while (fromLength > toLength) {
2063: fromLength--;
2064: from = from.tail;
2065: }
2066: while (fromLength < toLength) {
2067: toLength--;
2068: to = to.tail;
2069: }
2070: this .from = from;
2071: this .to = to;
2072: }
2073:
2074: Type subst(Type t) {
2075: if (from.tail == null)
2076: return t;
2077: else
2078: return visit(t);
2079: }
2080:
2081: List<Type> subst(List<Type> ts) {
2082: if (from.tail == null)
2083: return ts;
2084: boolean wild = false;
2085: if (ts.nonEmpty() && from.nonEmpty()) {
2086: Type head1 = subst(ts.head);
2087: List<Type> tail1 = subst(ts.tail);
2088: if (head1 != ts.head || tail1 != ts.tail)
2089: return tail1.prepend(head1);
2090: }
2091: return ts;
2092: }
2093:
2094: public Type visitType(Type t, Void ignored) {
2095: return t;
2096: }
2097:
2098: @Override
2099: public Type visitMethodType(MethodType t, Void ignored) {
2100: List<Type> argtypes = subst(t.argtypes);
2101: Type restype = subst(t.restype);
2102: List<Type> thrown = subst(t.thrown);
2103: if (argtypes == t.argtypes && restype == t.restype
2104: && thrown == t.thrown)
2105: return t;
2106: else
2107: return new MethodType(argtypes, restype, thrown, t.tsym);
2108: }
2109:
2110: @Override
2111: public Type visitTypeVar(TypeVar t, Void ignored) {
2112: for (List<Type> from = this .from, to = this .to; from
2113: .nonEmpty(); from = from.tail, to = to.tail) {
2114: if (t == from.head) {
2115: return to.head.withTypeVar(t);
2116: }
2117: }
2118: return t;
2119: }
2120:
2121: @Override
2122: public Type visitClassType(ClassType t, Void ignored) {
2123: if (!t.isCompound()) {
2124: List<Type> typarams = t.getTypeArguments();
2125: List<Type> typarams1 = subst(typarams);
2126: Type outer = t.getEnclosingType();
2127: Type outer1 = subst(outer);
2128: if (typarams1 == typarams && outer1 == outer)
2129: return t;
2130: else
2131: return new ClassType(outer1, typarams1, t.tsym);
2132: } else {
2133: Type st = subst(super type(t));
2134: List<Type> is = upperBounds(subst(interfaces(t)));
2135: if (st == super type(t) && is == interfaces(t))
2136: return t;
2137: else
2138: return makeCompoundType(is.prepend(st));
2139: }
2140: }
2141:
2142: @Override
2143: public Type visitWildcardType(WildcardType t, Void ignored) {
2144: Type bound = t.type;
2145: if (t.kind != BoundKind.UNBOUND)
2146: bound = subst(bound);
2147: if (bound == t.type) {
2148: return t;
2149: } else {
2150: if (t.isExtendsBound() && bound.isExtendsBound())
2151: bound = upperBound(bound);
2152: return new WildcardType(bound, t.kind, syms.boundClass,
2153: t.bound);
2154: }
2155: }
2156:
2157: @Override
2158: public Type visitArrayType(ArrayType t, Void ignored) {
2159: Type elemtype = subst(t.elemtype);
2160: if (elemtype == t.elemtype)
2161: return t;
2162: else
2163: return new ArrayType(upperBound(elemtype), t.tsym);
2164: }
2165:
2166: @Override
2167: public Type visitForAll(ForAll t, Void ignored) {
2168: List<Type> tvars1 = substBounds(t.tvars, from, to);
2169: Type qtype1 = subst(t.qtype);
2170: if (tvars1 == t.tvars && qtype1 == t.qtype) {
2171: return t;
2172: } else if (tvars1 == t.tvars) {
2173: return new ForAll(tvars1, qtype1);
2174: } else {
2175: return new ForAll(tvars1, Types.this .subst(qtype1,
2176: t.tvars, tvars1));
2177: }
2178: }
2179:
2180: @Override
2181: public Type visitErrorType(ErrorType t, Void ignored) {
2182: return t;
2183: }
2184: }
2185:
2186: public List<Type> substBounds(List<Type> tvars, List<Type> from,
2187: List<Type> to) {
2188: if (tvars.isEmpty())
2189: return tvars;
2190: if (tvars.tail.isEmpty())
2191: // fast common case
2192: return List.<Type> of(substBound((TypeVar) tvars.head,
2193: from, to));
2194: ListBuffer<Type> newBoundsBuf = lb();
2195: boolean changed = false;
2196: // calculate new bounds
2197: for (Type t : tvars) {
2198: TypeVar tv = (TypeVar) t;
2199: Type bound = subst(tv.bound, from, to);
2200: if (bound != tv.bound)
2201: changed = true;
2202: newBoundsBuf.append(bound);
2203: }
2204: if (!changed)
2205: return tvars;
2206: ListBuffer<Type> newTvars = lb();
2207: // create new type variables without bounds
2208: for (Type t : tvars) {
2209: newTvars.append(new TypeVar(t.tsym, null, syms.botType));
2210: }
2211: // the new bounds should use the new type variables in place
2212: // of the old
2213: List<Type> newBounds = newBoundsBuf.toList();
2214: from = tvars;
2215: to = newTvars.toList();
2216: for (; !newBounds.isEmpty(); newBounds = newBounds.tail) {
2217: newBounds.head = subst(newBounds.head, from, to);
2218: }
2219: newBounds = newBoundsBuf.toList();
2220: // set the bounds of new type variables to the new bounds
2221: for (Type t : newTvars.toList()) {
2222: TypeVar tv = (TypeVar) t;
2223: tv.bound = newBounds.head;
2224: newBounds = newBounds.tail;
2225: }
2226: return newTvars.toList();
2227: }
2228:
2229: public TypeVar substBound(TypeVar t, List<Type> from, List<Type> to) {
2230: Type bound1 = subst(t.bound, from, to);
2231: if (bound1 == t.bound)
2232: return t;
2233: else
2234: return new TypeVar(t.tsym, bound1, syms.botType);
2235: }
2236:
2237: // </editor-fold>
2238:
2239: // <editor-fold defaultstate="collapsed" desc="hasSameBounds">
2240: /**
2241: * Does t have the same bounds for quantified variables as s?
2242: */
2243: boolean hasSameBounds(ForAll t, ForAll s) {
2244: List<Type> l1 = t.tvars;
2245: List<Type> l2 = s.tvars;
2246: while (l1.nonEmpty()
2247: && l2.nonEmpty()
2248: && isSameType(l1.head.getUpperBound(), subst(l2.head
2249: .getUpperBound(), s.tvars, t.tvars))) {
2250: l1 = l1.tail;
2251: l2 = l2.tail;
2252: }
2253: return l1.isEmpty() && l2.isEmpty();
2254: }
2255:
2256: // </editor-fold>
2257:
2258: // <editor-fold defaultstate="collapsed" desc="newInstances">
2259: /** Create new vector of type variables from list of variables
2260: * changing all recursive bounds from old to new list.
2261: */
2262: public List<Type> newInstances(List<Type> tvars) {
2263: List<Type> tvars1 = Type.map(tvars, newInstanceFun);
2264: for (List<Type> l = tvars1; l.nonEmpty(); l = l.tail) {
2265: TypeVar tv = (TypeVar) l.head;
2266: tv.bound = subst(tv.bound, tvars, tvars1);
2267: }
2268: return tvars1;
2269: }
2270:
2271: static private Mapping newInstanceFun = new Mapping(
2272: "newInstanceFun") {
2273: public Type apply(Type t) {
2274: return new TypeVar(t.tsym, t.getUpperBound(), t
2275: .getLowerBound());
2276: }
2277: };
2278:
2279: // </editor-fold>
2280:
2281: // <editor-fold defaultstate="collapsed" desc="rank">
2282: /**
2283: * The rank of a class is the length of the longest path between
2284: * the class and java.lang.Object in the class inheritance
2285: * graph. Undefined for all but reference types.
2286: */
2287: public int rank(Type t) {
2288: switch (t.tag) {
2289: case CLASS: {
2290: ClassType cls = (ClassType) t;
2291: if (cls.rank_field < 0) {
2292: Name fullname = cls.tsym.getQualifiedName();
2293: if (fullname == fullname.table.java_lang_Object)
2294: cls.rank_field = 0;
2295: else {
2296: int r = rank(super type(cls));
2297: for (List<Type> l = interfaces(cls); l.nonEmpty(); l = l.tail) {
2298: if (rank(l.head) > r)
2299: r = rank(l.head);
2300: }
2301: cls.rank_field = r + 1;
2302: }
2303: }
2304: return cls.rank_field;
2305: }
2306: case TYPEVAR: {
2307: TypeVar tvar = (TypeVar) t;
2308: if (tvar.rank_field < 0) {
2309: int r = rank(super type(tvar));
2310: for (List<Type> l = interfaces(tvar); l.nonEmpty(); l = l.tail) {
2311: if (rank(l.head) > r)
2312: r = rank(l.head);
2313: }
2314: tvar.rank_field = r + 1;
2315: }
2316: return tvar.rank_field;
2317: }
2318: case ERROR:
2319: return 0;
2320: default:
2321: throw new AssertionError();
2322: }
2323: }
2324:
2325: // </editor-fold>
2326:
2327: // <editor-fold defaultstate="collapsed" desc="toString">
2328: /**
2329: * This toString is slightly more descriptive than the one on Type.
2330: */
2331: public String toString(Type t) {
2332: if (t.tag == FORALL) {
2333: ForAll forAll = (ForAll) t;
2334: return typaramsString(forAll.tvars) + forAll.qtype;
2335: }
2336: return "" + t;
2337: }
2338:
2339: // where
2340: private String typaramsString(List<Type> tvars) {
2341: StringBuffer s = new StringBuffer();
2342: s.append('<');
2343: boolean first = true;
2344: for (Type t : tvars) {
2345: if (!first)
2346: s.append(", ");
2347: first = false;
2348: appendTyparamString(((TypeVar) t), s);
2349: }
2350: s.append('>');
2351: return s.toString();
2352: }
2353:
2354: private void appendTyparamString(TypeVar t, StringBuffer buf) {
2355: buf.append(t);
2356: if (t.bound == null
2357: || t.bound.tsym.getQualifiedName() == names.java_lang_Object)
2358: return;
2359: buf.append(" extends "); // Java syntax; no need for i18n
2360: Type bound = t.bound;
2361: if (!bound.isCompound()) {
2362: buf.append(bound);
2363: } else if ((erasure(t).tsym.flags() & INTERFACE) == 0) {
2364: buf.append(super type(t));
2365: for (Type intf : interfaces(t)) {
2366: buf.append('&');
2367: buf.append(intf);
2368: }
2369: } else {
2370: // No superclass was given in bounds.
2371: // In this case, supertype is Object, erasure is first interface.
2372: boolean first = true;
2373: for (Type intf : interfaces(t)) {
2374: if (!first)
2375: buf.append('&');
2376: first = false;
2377: buf.append(intf);
2378: }
2379: }
2380: }
2381:
2382: // </editor-fold>
2383:
2384: // <editor-fold defaultstate="collapsed" desc="Determining least upper bounds of types">
2385: /**
2386: * A cache for closures.
2387: *
2388: * <p>A closure is a list of all the supertypes and interfaces of
2389: * a class or interface type, ordered by ClassSymbol.precedes
2390: * (that is, subclasses come first, arbitrary but fixed
2391: * otherwise).
2392: */
2393: private Map<Type, List<Type>> closureCache = new HashMap<Type, List<Type>>();
2394:
2395: /**
2396: * Returns the closure of a class or interface type.
2397: */
2398: public List<Type> closure(Type t) {
2399: List<Type> cl = closureCache.get(t);
2400: if (cl == null) {
2401: Type st = super type(t);
2402: if (!t.isCompound()) {
2403: if (st.tag == CLASS) {
2404: cl = insert(closure(st), t);
2405: } else if (st.tag == TYPEVAR) {
2406: cl = closure(st).prepend(t);
2407: } else {
2408: cl = List.of(t);
2409: }
2410: } else {
2411: cl = closure(super type(t));
2412: }
2413: for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail)
2414: cl = union(cl, closure(l.head));
2415: closureCache.put(t, cl);
2416: }
2417: return cl;
2418: }
2419:
2420: /**
2421: * Insert a type in a closure
2422: */
2423: public List<Type> insert(List<Type> cl, Type t) {
2424: if (cl.isEmpty() || t.tsym.precedes(cl.head.tsym, this )) {
2425: return cl.prepend(t);
2426: } else if (cl.head.tsym.precedes(t.tsym, this )) {
2427: return insert(cl.tail, t).prepend(cl.head);
2428: } else {
2429: return cl;
2430: }
2431: }
2432:
2433: /**
2434: * Form the union of two closures
2435: */
2436: public List<Type> union(List<Type> cl1, List<Type> cl2) {
2437: if (cl1.isEmpty()) {
2438: return cl2;
2439: } else if (cl2.isEmpty()) {
2440: return cl1;
2441: } else if (cl1.head.tsym.precedes(cl2.head.tsym, this )) {
2442: return union(cl1.tail, cl2).prepend(cl1.head);
2443: } else if (cl2.head.tsym.precedes(cl1.head.tsym, this )) {
2444: return union(cl1, cl2.tail).prepend(cl2.head);
2445: } else {
2446: return union(cl1.tail, cl2.tail).prepend(cl1.head);
2447: }
2448: }
2449:
2450: /**
2451: * Intersect two closures
2452: */
2453: public List<Type> intersect(List<Type> cl1, List<Type> cl2) {
2454: if (cl1 == cl2)
2455: return cl1;
2456: if (cl1.isEmpty() || cl2.isEmpty())
2457: return List.nil();
2458: if (cl1.head.tsym.precedes(cl2.head.tsym, this ))
2459: return intersect(cl1.tail, cl2);
2460: if (cl2.head.tsym.precedes(cl1.head.tsym, this ))
2461: return intersect(cl1, cl2.tail);
2462: if (isSameType(cl1.head, cl2.head))
2463: return intersect(cl1.tail, cl2.tail).prepend(cl1.head);
2464: if (cl1.head.tsym == cl2.head.tsym && cl1.head.tag == CLASS
2465: && cl2.head.tag == CLASS) {
2466: if (cl1.head.isParameterized()
2467: && cl2.head.isParameterized()) {
2468: Type merge = merge(cl1.head, cl2.head);
2469: return intersect(cl1.tail, cl2.tail).prepend(merge);
2470: }
2471: if (cl1.head.isRaw() || cl2.head.isRaw())
2472: return intersect(cl1.tail, cl2.tail).prepend(
2473: erasure(cl1.head));
2474: }
2475: return intersect(cl1.tail, cl2.tail);
2476: }
2477:
2478: // where
2479: class TypePair {
2480: final Type t1;
2481: final Type t2;
2482:
2483: TypePair(Type t1, Type t2) {
2484: this .t1 = t1;
2485: this .t2 = t2;
2486: }
2487:
2488: @Override
2489: public int hashCode() {
2490: return 127 * Types.this .hashCode(t1)
2491: + Types.this .hashCode(t2);
2492: }
2493:
2494: @Override
2495: public boolean equals(Object obj) {
2496: if (!(obj instanceof TypePair))
2497: return false;
2498: TypePair typePair = (TypePair) obj;
2499: return isSameType(t1, typePair.t1)
2500: && isSameType(t2, typePair.t2);
2501: }
2502: }
2503:
2504: Set<TypePair> mergeCache = new HashSet<TypePair>();
2505:
2506: private Type merge(Type c1, Type c2) {
2507: ClassType class1 = (ClassType) c1;
2508: List<Type> act1 = class1.getTypeArguments();
2509: ClassType class2 = (ClassType) c2;
2510: List<Type> act2 = class2.getTypeArguments();
2511: ListBuffer<Type> merged = new ListBuffer<Type>();
2512: List<Type> typarams = class1.tsym.type.getTypeArguments();
2513:
2514: while (act1.nonEmpty() && act2.nonEmpty()
2515: && typarams.nonEmpty()) {
2516: if (containsType(act1.head, act2.head)) {
2517: merged.append(act1.head);
2518: } else if (containsType(act2.head, act1.head)) {
2519: merged.append(act2.head);
2520: } else {
2521: TypePair pair = new TypePair(c1, c2);
2522: Type m;
2523: if (mergeCache.add(pair)) {
2524: m = new WildcardType(lub(upperBound(act1.head),
2525: upperBound(act2.head)), BoundKind.EXTENDS,
2526: syms.boundClass);
2527: mergeCache.remove(pair);
2528: } else {
2529: m = new WildcardType(syms.objectType,
2530: BoundKind.UNBOUND, syms.boundClass);
2531: }
2532: merged.append(m.withTypeVar(typarams.head));
2533: }
2534: act1 = act1.tail;
2535: act2 = act2.tail;
2536: typarams = typarams.tail;
2537: }
2538: assert (act1.isEmpty() && act2.isEmpty() && typarams.isEmpty());
2539: return new ClassType(class1.getEnclosingType(),
2540: merged.toList(), class1.tsym);
2541: }
2542:
2543: /**
2544: * Return the minimum type of a closure, a compound type if no
2545: * unique minimum exists.
2546: */
2547: private Type compoundMin(List<Type> cl) {
2548: if (cl.isEmpty())
2549: return syms.objectType;
2550: List<Type> compound = closureMin(cl);
2551: if (compound.isEmpty())
2552: return null;
2553: else if (compound.tail.isEmpty())
2554: return compound.head;
2555: else
2556: return makeCompoundType(compound);
2557: }
2558:
2559: /**
2560: * Return the minimum types of a closure, suitable for computing
2561: * compoundMin or glb.
2562: */
2563: private List<Type> closureMin(List<Type> cl) {
2564: ListBuffer<Type> classes = lb();
2565: ListBuffer<Type> interfaces = lb();
2566: while (!cl.isEmpty()) {
2567: Type current = cl.head;
2568: if (current.isInterface())
2569: interfaces.append(current);
2570: else
2571: classes.append(current);
2572: ListBuffer<Type> candidates = lb();
2573: for (Type t : cl.tail) {
2574: if (!isSubtypeNoCapture(current, t))
2575: candidates.append(t);
2576: }
2577: cl = candidates.toList();
2578: }
2579: return classes.appendList(interfaces).toList();
2580: }
2581:
2582: /**
2583: * Return the least upper bound of pair of types. if the lub does
2584: * not exist return null.
2585: */
2586: public Type lub(Type t1, Type t2) {
2587: return lub(List.of(t1, t2));
2588: }
2589:
2590: /**
2591: * Return the least upper bound (lub) of set of types. If the lub
2592: * does not exist return the type of null (bottom).
2593: */
2594: public Type lub(List<Type> ts) {
2595: final int ARRAY_BOUND = 1;
2596: final int CLASS_BOUND = 2;
2597: int boundkind = 0;
2598: for (Type t : ts) {
2599: switch (t.tag) {
2600: case CLASS:
2601: boundkind |= CLASS_BOUND;
2602: break;
2603: case ARRAY:
2604: boundkind |= ARRAY_BOUND;
2605: break;
2606: case TYPEVAR:
2607: do {
2608: t = t.getUpperBound();
2609: } while (t.tag == TYPEVAR);
2610: if (t.tag == ARRAY) {
2611: boundkind |= ARRAY_BOUND;
2612: } else {
2613: boundkind |= CLASS_BOUND;
2614: }
2615: break;
2616: default:
2617: if (t.isPrimitive())
2618: return syms.botType;
2619: }
2620: }
2621: switch (boundkind) {
2622: case 0:
2623: return syms.botType;
2624:
2625: case ARRAY_BOUND:
2626: // calculate lub(A[], B[])
2627: List<Type> elements = Type.map(ts, elemTypeFun);
2628: for (Type t : elements) {
2629: if (t.isPrimitive()) {
2630: // if a primitive type is found, then return
2631: // arraySuperType unless all the types are the
2632: // same
2633: Type first = ts.head;
2634: for (Type s : ts.tail) {
2635: if (!isSameType(first, s)) {
2636: // lub(int[], B[]) is Cloneable & Serializable
2637: return arraySuperType();
2638: }
2639: }
2640: // all the array types are the same, return one
2641: // lub(int[], int[]) is int[]
2642: return first;
2643: }
2644: }
2645: // lub(A[], B[]) is lub(A, B)[]
2646: return new ArrayType(lub(elements), syms.arrayClass);
2647:
2648: case CLASS_BOUND:
2649: // calculate lub(A, B)
2650: while (ts.head.tag != CLASS && ts.head.tag != TYPEVAR)
2651: ts = ts.tail;
2652: assert !ts.isEmpty();
2653: List<Type> cl = closure(ts.head);
2654: for (Type t : ts.tail) {
2655: if (t.tag == CLASS || t.tag == TYPEVAR)
2656: cl = intersect(cl, closure(t));
2657: }
2658: return compoundMin(cl);
2659:
2660: default:
2661: // calculate lub(A, B[])
2662: List<Type> classes = List.of(arraySuperType());
2663: for (Type t : ts) {
2664: if (t.tag != ARRAY) // Filter out any arrays
2665: classes = classes.prepend(t);
2666: }
2667: // lub(A, B[]) is lub(A, arraySuperType)
2668: return lub(classes);
2669: }
2670: }
2671:
2672: // where
2673: private Type arraySuperType = null;
2674:
2675: private Type arraySuperType() {
2676: // initialized lazily to avoid problems during compiler startup
2677: if (arraySuperType == null) {
2678: synchronized (this ) {
2679: if (arraySuperType == null) {
2680: // JLS 10.8: all arrays implement Cloneable and Serializable.
2681: arraySuperType = makeCompoundType(List.of(
2682: syms.serializableType, syms.cloneableType),
2683: syms.objectType);
2684: }
2685: }
2686: }
2687: return arraySuperType;
2688: }
2689:
2690: // </editor-fold>
2691:
2692: // <editor-fold defaultstate="collapsed" desc="Greatest lower bound">
2693: public Type glb(Type t, Type s) {
2694: if (s == null)
2695: return t;
2696: else if (isSubtypeNoCapture(t, s))
2697: return t;
2698: else if (isSubtypeNoCapture(s, t))
2699: return s;
2700:
2701: List<Type> closure = union(closure(t), closure(s));
2702: List<Type> bounds = closureMin(closure);
2703:
2704: if (bounds.isEmpty()) { // length == 0
2705: return syms.objectType;
2706: } else if (bounds.tail.isEmpty()) { // length == 1
2707: return bounds.head;
2708: } else { // length > 1
2709: int classCount = 0;
2710: for (Type bound : bounds)
2711: if (!bound.isInterface())
2712: classCount++;
2713: if (classCount > 1)
2714: return syms.errType;
2715: }
2716: return makeCompoundType(bounds);
2717: }
2718:
2719: // </editor-fold>
2720:
2721: // <editor-fold defaultstate="collapsed" desc="hashCode">
2722: /**
2723: * Compute a hash code on a type.
2724: */
2725: public static int hashCode(Type t) {
2726: return hashCode.visit(t);
2727: }
2728:
2729: // where
2730: private static final UnaryVisitor<Integer> hashCode = new UnaryVisitor<Integer>() {
2731:
2732: public Integer visitType(Type t, Void ignored) {
2733: return t.tag;
2734: }
2735:
2736: @Override
2737: public Integer visitClassType(ClassType t, Void ignored) {
2738: int result = visit(t.getEnclosingType());
2739: result *= 127;
2740: result += t.tsym.flatName().hashCode();
2741: for (Type s : t.getTypeArguments()) {
2742: result *= 127;
2743: result += visit(s);
2744: }
2745: return result;
2746: }
2747:
2748: @Override
2749: public Integer visitWildcardType(WildcardType t, Void ignored) {
2750: int result = t.kind.hashCode();
2751: if (t.type != null) {
2752: result *= 127;
2753: result += visit(t.type);
2754: }
2755: return result;
2756: }
2757:
2758: @Override
2759: public Integer visitArrayType(ArrayType t, Void ignored) {
2760: return visit(t.elemtype) + 12;
2761: }
2762:
2763: @Override
2764: public Integer visitTypeVar(TypeVar t, Void ignored) {
2765: return System.identityHashCode(t.tsym);
2766: }
2767:
2768: @Override
2769: public Integer visitUndetVar(UndetVar t, Void ignored) {
2770: return System.identityHashCode(t);
2771: }
2772:
2773: @Override
2774: public Integer visitErrorType(ErrorType t, Void ignored) {
2775: return 0;
2776: }
2777: };
2778:
2779: // </editor-fold>
2780:
2781: // <editor-fold defaultstate="collapsed" desc="Return-Type-Substitutable">
2782: /**
2783: * Does t have a result that is a subtype of the result type of s,
2784: * suitable for covariant returns? It is assumed that both types
2785: * are (possibly polymorphic) method types. Monomorphic method
2786: * types are handled in the obvious way. Polymorphic method types
2787: * require renaming all type variables of one to corresponding
2788: * type variables in the other, where correspondence is by
2789: * position in the type parameter list. */
2790: public boolean resultSubtype(Type t, Type s, Warner warner) {
2791: List<Type> tvars = t.getTypeArguments();
2792: List<Type> svars = s.getTypeArguments();
2793: Type tres = t.getReturnType();
2794: Type sres = subst(s.getReturnType(), svars, tvars);
2795: return covariantReturnType(tres, sres, warner);
2796: }
2797:
2798: /**
2799: * Return-Type-Substitutable.
2800: * @see <a href="http://java.sun.com/docs/books/jls/">The Java
2801: * Language Specification, Third Ed. (8.4.5)</a>
2802: */
2803: public boolean returnTypeSubstitutable(Type r1, Type r2) {
2804: if (hasSameArgs(r1, r2))
2805: return resultSubtype(r1, r2, Warner.noWarnings);
2806: else
2807: return covariantReturnType(r1.getReturnType(), erasure(r2
2808: .getReturnType()), Warner.noWarnings);
2809: }
2810:
2811: public boolean returnTypeSubstitutable(Type r1, Type r2,
2812: Type r2res, Warner warner) {
2813: if (isSameType(r1.getReturnType(), r2res))
2814: return true;
2815: if (r1.getReturnType().isPrimitive() || r2res.isPrimitive())
2816: return false;
2817:
2818: if (hasSameArgs(r1, r2))
2819: return covariantReturnType(r1.getReturnType(), r2res,
2820: warner);
2821: if (!source.allowCovariantReturns())
2822: return false;
2823: if (isSubtypeUnchecked(r1.getReturnType(), r2res, warner))
2824: return true;
2825: if (!isSubtype(r1.getReturnType(), erasure(r2res)))
2826: return false;
2827: warner.warnUnchecked();
2828: return true;
2829: }
2830:
2831: /**
2832: * Is t an appropriate return type in an overrider for a
2833: * method that returns s?
2834: */
2835: public boolean covariantReturnType(Type t, Type s, Warner warner) {
2836: return isSameType(t, s) || source.allowCovariantReturns()
2837: && !t.isPrimitive() && !s.isPrimitive()
2838: && isAssignable(t, s, warner);
2839: }
2840:
2841: // </editor-fold>
2842:
2843: // <editor-fold defaultstate="collapsed" desc="Box/unbox support">
2844: /**
2845: * Return the class that boxes the given primitive.
2846: */
2847: public ClassSymbol boxedClass(Type t) {
2848: return reader.enterClass(syms.boxedName[t.tag]);
2849: }
2850:
2851: /**
2852: * Return the primitive type corresponding to a boxed type.
2853: */
2854: public Type unboxedType(Type t) {
2855: if (allowBoxing) {
2856: for (int i = 0; i < syms.boxedName.length; i++) {
2857: Name box = syms.boxedName[i];
2858: if (box != null
2859: && asSuper(t, reader.enterClass(box)) != null)
2860: return syms.typeOfTag[i];
2861: }
2862: }
2863: return Type.noType;
2864: }
2865:
2866: // </editor-fold>
2867:
2868: // <editor-fold defaultstate="collapsed" desc="Capture conversion">
2869: /*
2870: * JLS 3rd Ed. 5.1.10 Capture Conversion:
2871: *
2872: * Let G name a generic type declaration with n formal type
2873: * parameters A1 ... An with corresponding bounds U1 ... Un. There
2874: * exists a capture conversion from G<T1 ... Tn> to G<S1 ... Sn>,
2875: * where, for 1 <= i <= n:
2876: *
2877: * + If Ti is a wildcard type argument (4.5.1) of the form ? then
2878: * Si is a fresh type variable whose upper bound is
2879: * Ui[A1 := S1, ..., An := Sn] and whose lower bound is the null
2880: * type.
2881: *
2882: * + If Ti is a wildcard type argument of the form ? extends Bi,
2883: * then Si is a fresh type variable whose upper bound is
2884: * glb(Bi, Ui[A1 := S1, ..., An := Sn]) and whose lower bound is
2885: * the null type, where glb(V1,... ,Vm) is V1 & ... & Vm. It is
2886: * a compile-time error if for any two classes (not interfaces)
2887: * Vi and Vj,Vi is not a subclass of Vj or vice versa.
2888: *
2889: * + If Ti is a wildcard type argument of the form ? super Bi,
2890: * then Si is a fresh type variable whose upper bound is
2891: * Ui[A1 := S1, ..., An := Sn] and whose lower bound is Bi.
2892: *
2893: * + Otherwise, Si = Ti.
2894: *
2895: * Capture conversion on any type other than a parameterized type
2896: * (4.5) acts as an identity conversion (5.1.1). Capture
2897: * conversions never require a special action at run time and
2898: * therefore never throw an exception at run time.
2899: *
2900: * Capture conversion is not applied recursively.
2901: */
2902: /**
2903: * Capture conversion as specified by JLS 3rd Ed.
2904: */
2905: public Type capture(Type t) {
2906: if (t.tag != CLASS)
2907: return t;
2908: ClassType cls = (ClassType) t;
2909: if (cls.isRaw() || !cls.isParameterized())
2910: return cls;
2911:
2912: ClassType G = (ClassType) cls.asElement().asType();
2913: List<Type> A = G.getTypeArguments();
2914: List<Type> T = cls.getTypeArguments();
2915: List<Type> S = freshTypeVariables(T);
2916:
2917: List<Type> currentA = A;
2918: List<Type> currentT = T;
2919: List<Type> currentS = S;
2920: boolean captured = false;
2921: while (!currentA.isEmpty() && !currentT.isEmpty()
2922: && !currentS.isEmpty()) {
2923: if (currentS.head != currentT.head) {
2924: captured = true;
2925: WildcardType Ti = (WildcardType) currentT.head;
2926: Type Ui = currentA.head.getUpperBound();
2927: CapturedType Si = (CapturedType) currentS.head;
2928: if (Ui == null)
2929: Ui = syms.objectType;
2930: switch (Ti.kind) {
2931: case UNBOUND:
2932: Si.bound = subst(Ui, A, S);
2933: Si.lower = syms.botType;
2934: break;
2935: case EXTENDS:
2936: Si.bound = glb(Ti.getExtendsBound(),
2937: subst(Ui, A, S));
2938: Si.lower = syms.botType;
2939: break;
2940: case SUPER:
2941: Si.bound = subst(Ui, A, S);
2942: Si.lower = Ti.getSuperBound();
2943: break;
2944: }
2945: if (Si.bound == Si.lower)
2946: currentS.head = Si.bound;
2947: }
2948: currentA = currentA.tail;
2949: currentT = currentT.tail;
2950: currentS = currentS.tail;
2951: }
2952: if (!currentA.isEmpty() || !currentT.isEmpty()
2953: || !currentS.isEmpty())
2954: return erasure(t); // some "rare" type involved
2955:
2956: if (captured)
2957: return new ClassType(cls.getEnclosingType(), S, cls.tsym);
2958: else
2959: return t;
2960: }
2961:
2962: // where
2963: private List<Type> freshTypeVariables(List<Type> types) {
2964: ListBuffer<Type> result = lb();
2965: for (Type t : types) {
2966: if (t.tag == WILDCARD) {
2967: Type bound = ((WildcardType) t).getExtendsBound();
2968: if (bound == null)
2969: bound = syms.objectType;
2970: result.append(new CapturedType(capturedName,
2971: syms.noSymbol, bound, syms.botType,
2972: (WildcardType) t));
2973: } else {
2974: result.append(t);
2975: }
2976: }
2977: return result.toList();
2978: }
2979:
2980: // </editor-fold>
2981:
2982: // <editor-fold defaultstate="collapsed" desc="Internal utility methods">
2983: private List<Type> upperBounds(List<Type> ss) {
2984: if (ss.isEmpty())
2985: return ss;
2986: Type head = upperBound(ss.head);
2987: List<Type> tail = upperBounds(ss.tail);
2988: if (head != ss.head || tail != ss.tail)
2989: return tail.prepend(head);
2990: else
2991: return ss;
2992: }
2993:
2994: private boolean sideCast(Type from, Type to, Warner warn) {
2995: // We are casting from type $from$ to type $to$, which are
2996: // non-final unrelated types. This method
2997: // tries to reject a cast by transferring type parameters
2998: // from $to$ to $from$ by common superinterfaces.
2999: boolean reverse = false;
3000: Type target = to;
3001: if ((to.tsym.flags() & INTERFACE) == 0) {
3002: assert (from.tsym.flags() & INTERFACE) != 0;
3003: reverse = true;
3004: to = from;
3005: from = target;
3006: }
3007: List<Type> commonSupers = super Closure(to, erasure(from));
3008: boolean giveWarning = commonSupers.isEmpty();
3009: // The arguments to the supers could be unified here to
3010: // get a more accurate analysis
3011: while (commonSupers.nonEmpty()) {
3012: Type t1 = asSuper(from, commonSupers.head.tsym);
3013: Type t2 = commonSupers.head; // same as asSuper(to, commonSupers.head.tsym);
3014: if (disjointTypes(t1.getTypeArguments(), t2
3015: .getTypeArguments()))
3016: return false;
3017: giveWarning = giveWarning
3018: || (reverse ? giveWarning(t2, t1) : giveWarning(t1,
3019: t2));
3020: commonSupers = commonSupers.tail;
3021: }
3022: if (giveWarning && !isReifiable(to))
3023: warn.warnUnchecked();
3024: if (!source.allowCovariantReturns())
3025: // reject if there is a common method signature with
3026: // incompatible return types.
3027: chk.checkCompatibleAbstracts(warn.pos(), from, to);
3028: return true;
3029: }
3030:
3031: private boolean sideCastFinal(Type from, Type to, Warner warn) {
3032: // We are casting from type $from$ to type $to$, which are
3033: // unrelated types one of which is final and the other of
3034: // which is an interface. This method
3035: // tries to reject a cast by transferring type parameters
3036: // from the final class to the interface.
3037: boolean reverse = false;
3038: Type target = to;
3039: if ((to.tsym.flags() & INTERFACE) == 0) {
3040: assert (from.tsym.flags() & INTERFACE) != 0;
3041: reverse = true;
3042: to = from;
3043: from = target;
3044: }
3045: assert (from.tsym.flags() & FINAL) != 0;
3046: Type t1 = asSuper(from, to.tsym);
3047: if (t1 == null)
3048: return false;
3049: Type t2 = to;
3050: if (disjointTypes(t1.getTypeArguments(), t2.getTypeArguments()))
3051: return false;
3052: if (!source.allowCovariantReturns())
3053: // reject if there is a common method signature with
3054: // incompatible return types.
3055: chk.checkCompatibleAbstracts(warn.pos(), from, to);
3056: if (!isReifiable(target)
3057: && (reverse ? giveWarning(t2, t1) : giveWarning(t1, t2)))
3058: warn.warnUnchecked();
3059: return true;
3060: }
3061:
3062: private boolean giveWarning(Type from, Type to) {
3063: // To and from are (possibly different) parameterizations
3064: // of the same class or interface
3065: return to.isParameterized()
3066: && !containsType(to.getTypeArguments(), from
3067: .getTypeArguments());
3068: }
3069:
3070: private List<Type> super Closure(Type t, Type s) {
3071: List<Type> cl = List.nil();
3072: for (List<Type> l = interfaces(t); l.nonEmpty(); l = l.tail) {
3073: if (isSubtype(s, erasure(l.head))) {
3074: cl = insert(cl, l.head);
3075: } else {
3076: cl = union(cl, super Closure(l.head, s));
3077: }
3078: }
3079: return cl;
3080: }
3081:
3082: private boolean containsTypeEquivalent(Type t, Type s) {
3083: return isSameType(t, s) || // shortcut
3084: containsType(t, s) && containsType(s, t);
3085: }
3086:
3087: /**
3088: * Adapt a type by computing a substitution which maps a source
3089: * type to a target type.
3090: *
3091: * @param source the source type
3092: * @param target the target type
3093: * @param from the type variables of the computed substitution
3094: * @param to the types of the computed substitution.
3095: */
3096: public void adapt(Type source, Type target, ListBuffer<Type> from,
3097: ListBuffer<Type> to) throws AdaptFailure {
3098: Map<Symbol, Type> mapping = new HashMap<Symbol, Type>();
3099: adaptRecursive(source, target, from, to, mapping);
3100: List<Type> fromList = from.toList();
3101: List<Type> toList = to.toList();
3102: while (!fromList.isEmpty()) {
3103: Type val = mapping.get(fromList.head.tsym);
3104: if (toList.head != val)
3105: toList.head = val;
3106: fromList = fromList.tail;
3107: toList = toList.tail;
3108: }
3109: }
3110:
3111: // where
3112: private void adaptRecursive(Type source, Type target,
3113: ListBuffer<Type> from, ListBuffer<Type> to,
3114: Map<Symbol, Type> mapping) throws AdaptFailure {
3115: if (source.tag == TYPEVAR) {
3116: // Check to see if there is
3117: // already a mapping for $source$, in which case
3118: // the old mapping will be merged with the new
3119: Type val = mapping.get(source.tsym);
3120: if (val != null) {
3121: if (val.isSuperBound() && target.isSuperBound()) {
3122: val = isSubtype(lowerBound(val), lowerBound(target)) ? target
3123: : val;
3124: } else if (val.isExtendsBound()
3125: && target.isExtendsBound()) {
3126: val = isSubtype(upperBound(val), upperBound(target)) ? val
3127: : target;
3128: } else if (!isSameType(val, target)) {
3129: throw new AdaptFailure();
3130: }
3131: } else {
3132: val = target;
3133: from.append(source);
3134: to.append(target);
3135: }
3136: mapping.put(source.tsym, val);
3137: } else if (source.tag == target.tag) {
3138: switch (source.tag) {
3139: case CLASS:
3140: adapt(source.allparams(), target.allparams(), from, to,
3141: mapping);
3142: break;
3143: case ARRAY:
3144: adaptRecursive(elemtype(source), elemtype(target),
3145: from, to, mapping);
3146: break;
3147: case WILDCARD:
3148: if (source.isExtendsBound()) {
3149: adaptRecursive(upperBound(source),
3150: upperBound(target), from, to, mapping);
3151: } else if (source.isSuperBound()) {
3152: adaptRecursive(lowerBound(source),
3153: lowerBound(target), from, to, mapping);
3154: }
3155: break;
3156: }
3157: }
3158: }
3159:
3160: public static class AdaptFailure extends Exception {
3161: static final long serialVersionUID = -7490231548272701566L;
3162: }
3163:
3164: /**
3165: * Adapt a type by computing a substitution which maps a list of
3166: * source types to a list of target types.
3167: *
3168: * @param source the source type
3169: * @param target the target type
3170: * @param from the type variables of the computed substitution
3171: * @param to the types of the computed substitution.
3172: */
3173: private void adapt(List<Type> source, List<Type> target,
3174: ListBuffer<Type> from, ListBuffer<Type> to,
3175: Map<Symbol, Type> mapping) throws AdaptFailure {
3176: if (source.length() == target.length()) {
3177: while (source.nonEmpty()) {
3178: adaptRecursive(source.head, target.head, from, to,
3179: mapping);
3180: source = source.tail;
3181: target = target.tail;
3182: }
3183: }
3184: }
3185:
3186: private void adaptSelf(Type t, ListBuffer<Type> from,
3187: ListBuffer<Type> to) {
3188: try {
3189: //if (t.tsym.type != t)
3190: adapt(t.tsym.type, t, from, to);
3191: } catch (AdaptFailure ex) {
3192: // Adapt should never fail calculating a mapping from
3193: // t.tsym.type to t as there can be no merge problem.
3194: throw new AssertionError(ex);
3195: }
3196: }
3197:
3198: /**
3199: * Rewrite all type variables (universal quantifiers) in the given
3200: * type to wildcards (existential quantifiers). This is used to
3201: * determine if a cast is allowed. For example, if high is true
3202: * and {@code T <: Number}, then {@code List<T>} is rewritten to
3203: * {@code List<? extends Number>}. Since {@code List<Integer> <:
3204: * List<? extends Number>} a {@code List<T>} can be cast to {@code
3205: * List<Integer>} with a warning.
3206: * @param t a type
3207: * @param high if true return an upper bound; otherwise a lower
3208: * bound
3209: * @param rewriteTypeVars only rewrite captured wildcards if false;
3210: * otherwise rewrite all type variables
3211: * @return the type rewritten with wildcards (existential
3212: * quantifiers) only
3213: */
3214: private Type rewriteQuantifiers(Type t, boolean high,
3215: boolean rewriteTypeVars) {
3216: ListBuffer<Type> from = new ListBuffer<Type>();
3217: ListBuffer<Type> to = new ListBuffer<Type>();
3218: adaptSelf(t, from, to);
3219: ListBuffer<Type> rewritten = new ListBuffer<Type>();
3220: List<Type> formals = from.toList();
3221: boolean changed = false;
3222: for (Type arg : to.toList()) {
3223: Type bound;
3224: if (rewriteTypeVars && arg.tag == TYPEVAR) {
3225: TypeVar tv = (TypeVar) arg;
3226: bound = high ? tv.bound : syms.botType;
3227: } else {
3228: bound = high ? upperBound(arg) : lowerBound(arg);
3229: }
3230: Type newarg = bound;
3231: if (arg != bound) {
3232: changed = true;
3233: newarg = high ? makeExtendsWildcard(bound,
3234: (TypeVar) formals.head) : makeSuperWildcard(
3235: bound, (TypeVar) formals.head);
3236: }
3237: rewritten.append(newarg);
3238: formals = formals.tail;
3239: }
3240: if (changed)
3241: return subst(t.tsym.type, from.toList(), rewritten.toList());
3242: else
3243: return t;
3244: }
3245:
3246: /**
3247: * Create a wildcard with the given upper (extends) bound; create
3248: * an unbounded wildcard if bound is Object.
3249: *
3250: * @param bound the upper bound
3251: * @param formal the formal type parameter that will be
3252: * substituted by the wildcard
3253: */
3254: private WildcardType makeExtendsWildcard(Type bound, TypeVar formal) {
3255: if (bound == syms.objectType) {
3256: return new WildcardType(syms.objectType, BoundKind.UNBOUND,
3257: syms.boundClass, formal);
3258: } else {
3259: return new WildcardType(bound, BoundKind.EXTENDS,
3260: syms.boundClass, formal);
3261: }
3262: }
3263:
3264: /**
3265: * Create a wildcard with the given lower (super) bound; create an
3266: * unbounded wildcard if bound is bottom (type of {@code null}).
3267: *
3268: * @param bound the lower bound
3269: * @param formal the formal type parameter that will be
3270: * substituted by the wildcard
3271: */
3272: private WildcardType makeSuperWildcard(Type bound, TypeVar formal) {
3273: if (bound.tag == BOT) {
3274: return new WildcardType(syms.objectType, BoundKind.UNBOUND,
3275: syms.boundClass, formal);
3276: } else {
3277: return new WildcardType(bound, BoundKind.SUPER,
3278: syms.boundClass, formal);
3279: }
3280: }
3281:
3282: /**
3283: * A wrapper for a type that allows use in sets.
3284: */
3285: class SingletonType {
3286: final Type t;
3287:
3288: SingletonType(Type t) {
3289: this .t = t;
3290: }
3291:
3292: public int hashCode() {
3293: return Types.this .hashCode(t);
3294: }
3295:
3296: public boolean equals(Object obj) {
3297: return (obj instanceof SingletonType)
3298: && isSameType(t, ((SingletonType) obj).t);
3299: }
3300:
3301: public String toString() {
3302: return t.toString();
3303: }
3304: }
3305:
3306: // </editor-fold>
3307:
3308: // <editor-fold defaultstate="collapsed" desc="Visitors">
3309: /**
3310: * A default visitor for types. All visitor methods except
3311: * visitType are implemented by delegating to visitType. Concrete
3312: * subclasses must provide an implementation of visitType and can
3313: * override other methods as needed.
3314: *
3315: * @param <R> the return type of the operation implemented by this
3316: * visitor; use Void if no return type is needed.
3317: * @param <S> the type of the second argument (the first being the
3318: * type itself) of the operation implemented by this visitor; use
3319: * Void if a second argument is not needed.
3320: */
3321: public static abstract class DefaultTypeVisitor<R, S> implements
3322: Type.Visitor<R, S> {
3323: final public R visit(Type t, S s) {
3324: return t.accept(this , s);
3325: }
3326:
3327: public R visitClassType(ClassType t, S s) {
3328: return visitType(t, s);
3329: }
3330:
3331: public R visitWildcardType(WildcardType t, S s) {
3332: return visitType(t, s);
3333: }
3334:
3335: public R visitArrayType(ArrayType t, S s) {
3336: return visitType(t, s);
3337: }
3338:
3339: public R visitMethodType(MethodType t, S s) {
3340: return visitType(t, s);
3341: }
3342:
3343: public R visitPackageType(PackageType t, S s) {
3344: return visitType(t, s);
3345: }
3346:
3347: public R visitTypeVar(TypeVar t, S s) {
3348: return visitType(t, s);
3349: }
3350:
3351: public R visitCapturedType(CapturedType t, S s) {
3352: return visitType(t, s);
3353: }
3354:
3355: public R visitForAll(ForAll t, S s) {
3356: return visitType(t, s);
3357: }
3358:
3359: public R visitUndetVar(UndetVar t, S s) {
3360: return visitType(t, s);
3361: }
3362:
3363: public R visitErrorType(ErrorType t, S s) {
3364: return visitType(t, s);
3365: }
3366: }
3367:
3368: /**
3369: * A <em>simple</em> visitor for types. This visitor is simple as
3370: * captured wildcards, for-all types (generic methods), and
3371: * undetermined type variables (part of inference) are hidden.
3372: * Captured wildcards are hidden by treating them as type
3373: * variables and the rest are hidden by visiting their qtypes.
3374: *
3375: * @param <R> the return type of the operation implemented by this
3376: * visitor; use Void if no return type is needed.
3377: * @param <S> the type of the second argument (the first being the
3378: * type itself) of the operation implemented by this visitor; use
3379: * Void if a second argument is not needed.
3380: */
3381: public static abstract class SimpleVisitor<R, S> extends
3382: DefaultTypeVisitor<R, S> {
3383: @Override
3384: public R visitCapturedType(CapturedType t, S s) {
3385: return visitTypeVar(t, s);
3386: }
3387:
3388: @Override
3389: public R visitForAll(ForAll t, S s) {
3390: return visit(t.qtype, s);
3391: }
3392:
3393: @Override
3394: public R visitUndetVar(UndetVar t, S s) {
3395: return visit(t.qtype, s);
3396: }
3397: }
3398:
3399: /**
3400: * A plain relation on types. That is a 2-ary function on the
3401: * form Type × Type → Boolean.
3402: * <!-- In plain text: Type x Type -> Boolean -->
3403: */
3404: public static abstract class TypeRelation extends
3405: SimpleVisitor<Boolean, Type> {
3406: }
3407:
3408: /**
3409: * A convenience visitor for implementing operations that only
3410: * require one argument (the type itself), that is, unary
3411: * operations.
3412: *
3413: * @param <R> the return type of the operation implemented by this
3414: * visitor; use Void if no return type is needed.
3415: */
3416: public static abstract class UnaryVisitor<R> extends
3417: SimpleVisitor<R, Void> {
3418: final public R visit(Type t) {
3419: return t.accept(this , null);
3420: }
3421: }
3422:
3423: /**
3424: * A visitor for implementing a mapping from types to types. The
3425: * default behavior of this class is to implement the identity
3426: * mapping (mapping a type to itself). This can be overridden in
3427: * subclasses.
3428: *
3429: * @param <S> the type of the second argument (the first being the
3430: * type itself) of this mapping; use Void if a second argument is
3431: * not needed.
3432: */
3433: public static class MapVisitor<S> extends
3434: DefaultTypeVisitor<Type, S> {
3435: final public Type visit(Type t) {
3436: return t.accept(this , null);
3437: }
3438:
3439: public Type visitType(Type t, S s) {
3440: return t;
3441: }
3442: }
3443: // </editor-fold>
3444: }
|