duke@1: /* xdono@229: * Copyright 1999-2009 Sun Microsystems, Inc. All Rights Reserved. duke@1: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. duke@1: * duke@1: * This code is free software; you can redistribute it and/or modify it duke@1: * under the terms of the GNU General Public License version 2 only, as duke@1: * published by the Free Software Foundation. Sun designates this duke@1: * particular file as subject to the "Classpath" exception as provided duke@1: * by Sun in the LICENSE file that accompanied this code. duke@1: * duke@1: * This code is distributed in the hope that it will be useful, but WITHOUT duke@1: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or duke@1: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License duke@1: * version 2 for more details (a copy is included in the LICENSE file that duke@1: * accompanied this code). duke@1: * duke@1: * You should have received a copy of the GNU General Public License version duke@1: * 2 along with this work; if not, write to the Free Software Foundation, duke@1: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. duke@1: * duke@1: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, duke@1: * CA 95054 USA or visit www.sun.com if you need additional information or duke@1: * have any questions. duke@1: */ duke@1: duke@1: package com.sun.tools.javac.comp; duke@1: duke@1: import com.sun.tools.javac.util.*; duke@1: import com.sun.tools.javac.util.List; duke@1: import com.sun.tools.javac.code.*; duke@1: import com.sun.tools.javac.code.Type.*; mcimadamore@396: import com.sun.tools.javac.code.Type.ForAll.ConstraintKind; mcimadamore@299: import com.sun.tools.javac.code.Symbol.*; mcimadamore@89: import com.sun.tools.javac.util.JCDiagnostic; duke@1: duke@1: import static com.sun.tools.javac.code.TypeTags.*; duke@1: duke@1: /** Helper class for type parameter inference, used by the attribution phase. duke@1: * duke@1: *

This is NOT part of any API supported by Sun Microsystems. If duke@1: * you write code that depends on this, you do so at your own risk. duke@1: * This code and its internal interfaces are subject to change or duke@1: * deletion without notice. duke@1: */ duke@1: public class Infer { duke@1: protected static final Context.Key inferKey = duke@1: new Context.Key(); duke@1: duke@1: /** A value for prototypes that admit any type, including polymorphic ones. */ duke@1: public static final Type anyPoly = new Type(NONE, null); duke@1: duke@1: Symtab syms; duke@1: Types types; mcimadamore@396: Check chk; mcimadamore@299: Resolve rs; mcimadamore@89: JCDiagnostic.Factory diags; duke@1: duke@1: public static Infer instance(Context context) { duke@1: Infer instance = context.get(inferKey); duke@1: if (instance == null) duke@1: instance = new Infer(context); duke@1: return instance; duke@1: } duke@1: duke@1: protected Infer(Context context) { duke@1: context.put(inferKey, this); duke@1: syms = Symtab.instance(context); duke@1: types = Types.instance(context); mcimadamore@299: rs = Resolve.instance(context); mcimadamore@396: chk = Check.instance(context); mcimadamore@89: diags = JCDiagnostic.Factory.instance(context); mcimadamore@89: ambiguousNoInstanceException = mcimadamore@89: new NoInstanceException(true, diags); mcimadamore@89: unambiguousNoInstanceException = mcimadamore@89: new NoInstanceException(false, diags); mcimadamore@299: invalidInstanceException = mcimadamore@299: new InvalidInstanceException(diags); mcimadamore@299: duke@1: } duke@1: mcimadamore@299: public static class InferenceException extends RuntimeException { duke@1: private static final long serialVersionUID = 0; duke@1: duke@1: JCDiagnostic diagnostic; mcimadamore@89: JCDiagnostic.Factory diags; duke@1: mcimadamore@299: InferenceException(JCDiagnostic.Factory diags) { duke@1: this.diagnostic = null; mcimadamore@89: this.diags = diags; duke@1: } mcimadamore@299: mcimadamore@299: InferenceException setMessage(String key, Object... args) { mcimadamore@299: this.diagnostic = diags.fragment(key, args); duke@1: return this; duke@1: } mcimadamore@299: duke@1: public JCDiagnostic getDiagnostic() { mcimadamore@299: return diagnostic; mcimadamore@299: } mcimadamore@299: } mcimadamore@299: mcimadamore@299: public static class NoInstanceException extends InferenceException { mcimadamore@299: private static final long serialVersionUID = 1; mcimadamore@299: mcimadamore@299: boolean isAmbiguous; // exist several incomparable best instances? mcimadamore@299: mcimadamore@299: NoInstanceException(boolean isAmbiguous, JCDiagnostic.Factory diags) { mcimadamore@299: super(diags); mcimadamore@299: this.isAmbiguous = isAmbiguous; duke@1: } duke@1: } mcimadamore@299: mcimadamore@299: public static class InvalidInstanceException extends InferenceException { mcimadamore@299: private static final long serialVersionUID = 2; mcimadamore@299: mcimadamore@299: InvalidInstanceException(JCDiagnostic.Factory diags) { mcimadamore@299: super(diags); mcimadamore@299: } mcimadamore@299: } mcimadamore@299: mcimadamore@89: private final NoInstanceException ambiguousNoInstanceException; mcimadamore@89: private final NoInstanceException unambiguousNoInstanceException; mcimadamore@299: private final InvalidInstanceException invalidInstanceException; duke@1: duke@1: /*************************************************************************** duke@1: * Auxiliary type values and classes duke@1: ***************************************************************************/ duke@1: duke@1: /** A mapping that turns type variables into undetermined type variables. duke@1: */ duke@1: Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") { duke@1: public Type apply(Type t) { duke@1: if (t.tag == TYPEVAR) return new UndetVar(t); duke@1: else return t.map(this); duke@1: } duke@1: }; duke@1: duke@1: /** A mapping that returns its type argument with every UndetVar replaced duke@1: * by its `inst' field. Throws a NoInstanceException duke@1: * if this not possible because an `inst' field is null. duke@1: */ duke@1: Mapping getInstFun = new Mapping("getInstFun") { duke@1: public Type apply(Type t) { duke@1: switch (t.tag) { duke@1: case UNKNOWN: duke@1: throw ambiguousNoInstanceException duke@1: .setMessage("undetermined.type"); duke@1: case UNDETVAR: duke@1: UndetVar that = (UndetVar) t; duke@1: if (that.inst == null) duke@1: throw ambiguousNoInstanceException duke@1: .setMessage("type.variable.has.undetermined.type", duke@1: that.qtype); duke@1: return apply(that.inst); duke@1: default: duke@1: return t.map(this); duke@1: } duke@1: } duke@1: }; duke@1: duke@1: /*************************************************************************** duke@1: * Mini/Maximization of UndetVars duke@1: ***************************************************************************/ duke@1: duke@1: /** Instantiate undetermined type variable to its minimal upper bound. duke@1: * Throw a NoInstanceException if this not possible. duke@1: */ duke@1: void maximizeInst(UndetVar that, Warner warn) throws NoInstanceException { duke@1: if (that.inst == null) { duke@1: if (that.hibounds.isEmpty()) duke@1: that.inst = syms.objectType; duke@1: else if (that.hibounds.tail.isEmpty()) duke@1: that.inst = that.hibounds.head; mcimadamore@210: else mcimadamore@210: that.inst = types.glb(that.hibounds); duke@1: } mcimadamore@210: if (that.inst == null || mcimadamore@298: that.inst.isErroneous()) mcimadamore@210: throw ambiguousNoInstanceException mcimadamore@210: .setMessage("no.unique.maximal.instance.exists", mcimadamore@210: that.qtype, that.hibounds); duke@1: } duke@1: //where duke@1: private boolean isSubClass(Type t, final List ts) { duke@1: t = t.baseType(); duke@1: if (t.tag == TYPEVAR) { duke@1: List bounds = types.getBounds((TypeVar)t); duke@1: for (Type s : ts) { duke@1: if (!types.isSameType(t, s.baseType())) { duke@1: for (Type bound : bounds) { duke@1: if (!isSubClass(bound, List.of(s.baseType()))) duke@1: return false; duke@1: } duke@1: } duke@1: } duke@1: } else { duke@1: for (Type s : ts) { duke@1: if (!t.tsym.isSubClass(s.baseType().tsym, types)) duke@1: return false; duke@1: } duke@1: } duke@1: return true; duke@1: } duke@1: jjg@110: /** Instantiate undetermined type variable to the lub of all its lower bounds. duke@1: * Throw a NoInstanceException if this not possible. duke@1: */ duke@1: void minimizeInst(UndetVar that, Warner warn) throws NoInstanceException { duke@1: if (that.inst == null) { duke@1: if (that.lobounds.isEmpty()) duke@1: that.inst = syms.botType; duke@1: else if (that.lobounds.tail.isEmpty()) mcimadamore@5: that.inst = that.lobounds.head.isPrimitive() ? syms.errType : that.lobounds.head; duke@1: else { duke@1: that.inst = types.lub(that.lobounds); mcimadamore@5: } jjg@110: if (that.inst == null || that.inst.tag == ERROR) duke@1: throw ambiguousNoInstanceException duke@1: .setMessage("no.unique.minimal.instance.exists", duke@1: that.qtype, that.lobounds); duke@1: // VGJ: sort of inlined maximizeInst() below. Adding duke@1: // bounds can cause lobounds that are above hibounds. duke@1: if (that.hibounds.isEmpty()) duke@1: return; duke@1: Type hb = null; duke@1: if (that.hibounds.tail.isEmpty()) duke@1: hb = that.hibounds.head; duke@1: else for (List bs = that.hibounds; duke@1: bs.nonEmpty() && hb == null; duke@1: bs = bs.tail) { duke@1: if (isSubClass(bs.head, that.hibounds)) duke@1: hb = types.fromUnknownFun.apply(bs.head); duke@1: } duke@1: if (hb == null || duke@1: !types.isSubtypeUnchecked(hb, that.hibounds, warn) || duke@1: !types.isSubtypeUnchecked(that.inst, hb, warn)) duke@1: throw ambiguousNoInstanceException; duke@1: } duke@1: } duke@1: duke@1: /*************************************************************************** duke@1: * Exported Methods duke@1: ***************************************************************************/ duke@1: duke@1: /** Try to instantiate expression type `that' to given type `to'. duke@1: * If a maximal instantiation exists which makes this type duke@1: * a subtype of type `to', return the instantiated type. duke@1: * If no instantiation exists, or if several incomparable duke@1: * best instantiations exist throw a NoInstanceException. duke@1: */ duke@1: public Type instantiateExpr(ForAll that, duke@1: Type to, mcimadamore@299: Warner warn) throws InferenceException { duke@1: List undetvars = Type.map(that.tvars, fromTypeVarFun); duke@1: for (List l = undetvars; l.nonEmpty(); l = l.tail) { mcimadamore@396: UndetVar uv = (UndetVar) l.head; mcimadamore@396: TypeVar tv = (TypeVar)uv.qtype; duke@1: ListBuffer hibounds = new ListBuffer(); mcimadamore@396: for (Type t : that.getConstraints(tv, ConstraintKind.EXTENDS).prependList(types.getBounds(tv))) { mcimadamore@396: if (!t.containsSome(that.tvars) && t.tag != BOT) { mcimadamore@396: hibounds.append(t); duke@1: } duke@1: } mcimadamore@396: List inst = that.getConstraints(tv, ConstraintKind.EQUAL); mcimadamore@396: if (inst.nonEmpty() && inst.head.tag != BOT) { mcimadamore@396: uv.inst = inst.head; mcimadamore@396: } mcimadamore@396: uv.hibounds = hibounds.toList(); duke@1: } duke@1: Type qtype1 = types.subst(that.qtype, that.tvars, undetvars); duke@1: if (!types.isSubtype(qtype1, to)) { duke@1: throw unambiguousNoInstanceException duke@1: .setMessage("no.conforming.instance.exists", duke@1: that.tvars, that.qtype, to); duke@1: } duke@1: for (List l = undetvars; l.nonEmpty(); l = l.tail) duke@1: maximizeInst((UndetVar) l.head, warn); duke@1: // System.out.println(" = " + qtype1.map(getInstFun));//DEBUG duke@1: duke@1: // check bounds duke@1: List targs = Type.map(undetvars, getInstFun); duke@1: targs = types.subst(targs, that.tvars, targs); duke@1: checkWithinBounds(that.tvars, targs, warn); mcimadamore@396: return chk.checkType(warn.pos(), that.inst(targs, types), to); duke@1: } duke@1: duke@1: /** Instantiate method type `mt' by finding instantiations of duke@1: * `tvars' so that method can be applied to `argtypes'. duke@1: */ mcimadamore@547: public Type instantiateMethod(final Env env, mcimadamore@547: List tvars, duke@1: MethodType mt, mcimadamore@299: final List argtypes, mcimadamore@299: final boolean allowBoxing, mcimadamore@299: final boolean useVarargs, mcimadamore@299: final Warner warn) throws InferenceException { duke@1: //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG duke@1: List undetvars = Type.map(tvars, fromTypeVarFun); duke@1: List formals = mt.argtypes; mcimadamore@299: //need to capture exactly once - otherwise subsequent mcimadamore@299: //applicability checks might fail mcimadamore@299: final List capturedArgs = types.capture(argtypes); mcimadamore@299: List actuals = capturedArgs; mcimadamore@299: List actualsNoCapture = argtypes; duke@1: // instantiate all polymorphic argument types and duke@1: // set up lower bounds constraints for undetvars duke@1: Type varargsFormal = useVarargs ? formals.last() : null; mcimadamore@299: while (actuals.nonEmpty() && formals.head != varargsFormal) { mcimadamore@299: Type formal = formals.head; mcimadamore@299: Type actual = actuals.head.baseType(); mcimadamore@299: Type actualNoCapture = actualsNoCapture.head.baseType(); mcimadamore@299: if (actual.tag == FORALL) mcimadamore@299: actual = instantiateArg((ForAll)actual, formal, tvars, warn); mcimadamore@299: Type undetFormal = types.subst(formal, tvars, undetvars); duke@1: boolean works = allowBoxing mcimadamore@299: ? types.isConvertible(actual, undetFormal, warn) mcimadamore@299: : types.isSubtypeUnchecked(actual, undetFormal, warn); duke@1: if (!works) { duke@1: throw unambiguousNoInstanceException duke@1: .setMessage("no.conforming.assignment.exists", mcimadamore@299: tvars, actualNoCapture, formal); duke@1: } duke@1: formals = formals.tail; mcimadamore@299: actuals = actuals.tail; mcimadamore@299: actualsNoCapture = actualsNoCapture.tail; duke@1: } duke@1: if (formals.head != varargsFormal || // not enough args mcimadamore@299: !useVarargs && actuals.nonEmpty()) { // too many args duke@1: // argument lists differ in length duke@1: throw unambiguousNoInstanceException duke@1: .setMessage("arg.length.mismatch"); duke@1: } duke@1: duke@1: // for varargs arguments as well duke@1: if (useVarargs) { mcimadamore@299: Type elemType = types.elemtype(varargsFormal); mcimadamore@299: Type elemUndet = types.subst(elemType, tvars, undetvars); mcimadamore@299: while (actuals.nonEmpty()) { mcimadamore@299: Type actual = actuals.head.baseType(); mcimadamore@299: Type actualNoCapture = actualsNoCapture.head.baseType(); mcimadamore@299: if (actual.tag == FORALL) mcimadamore@299: actual = instantiateArg((ForAll)actual, elemType, tvars, warn); mcimadamore@299: boolean works = types.isConvertible(actual, elemUndet, warn); duke@1: if (!works) { duke@1: throw unambiguousNoInstanceException duke@1: .setMessage("no.conforming.assignment.exists", mcimadamore@299: tvars, actualNoCapture, elemType); duke@1: } mcimadamore@299: actuals = actuals.tail; mcimadamore@299: actualsNoCapture = actualsNoCapture.tail; duke@1: } duke@1: } duke@1: duke@1: // minimize as yet undetermined type variables duke@1: for (Type t : undetvars) duke@1: minimizeInst((UndetVar) t, warn); duke@1: duke@1: /** Type variables instantiated to bottom */ duke@1: ListBuffer restvars = new ListBuffer(); duke@1: mcimadamore@396: /** Undet vars instantiated to bottom */ mcimadamore@396: final ListBuffer restundet = new ListBuffer(); mcimadamore@396: duke@1: /** Instantiated types or TypeVars if under-constrained */ duke@1: ListBuffer insttypes = new ListBuffer(); duke@1: duke@1: /** Instantiated types or UndetVars if under-constrained */ duke@1: ListBuffer undettypes = new ListBuffer(); duke@1: duke@1: for (Type t : undetvars) { duke@1: UndetVar uv = (UndetVar)t; duke@1: if (uv.inst.tag == BOT) { duke@1: restvars.append(uv.qtype); mcimadamore@396: restundet.append(uv); duke@1: insttypes.append(uv.qtype); duke@1: undettypes.append(uv); duke@1: uv.inst = null; duke@1: } else { duke@1: insttypes.append(uv.inst); duke@1: undettypes.append(uv.inst); duke@1: } duke@1: } duke@1: checkWithinBounds(tvars, undettypes.toList(), warn); duke@1: mcimadamore@299: mt = (MethodType)types.subst(mt, tvars, insttypes.toList()); mcimadamore@299: duke@1: if (!restvars.isEmpty()) { duke@1: // if there are uninstantiated variables, duke@1: // quantify result type with them mcimadamore@299: final List inferredTypes = insttypes.toList(); mcimadamore@299: final List all_tvars = tvars; //this is the wrong tvars mcimadamore@299: final MethodType mt2 = new MethodType(mt.argtypes, null, mt.thrown, syms.methodClass); mcimadamore@299: mt2.restype = new ForAll(restvars.toList(), mt.restype) { mcimadamore@299: @Override mcimadamore@396: public List getConstraints(TypeVar tv, ConstraintKind ck) { mcimadamore@396: for (Type t : restundet.toList()) { mcimadamore@396: UndetVar uv = (UndetVar)t; mcimadamore@396: if (uv.qtype == tv) { mcimadamore@396: switch (ck) { mcimadamore@396: case EXTENDS: return uv.hibounds; mcimadamore@396: case SUPER: return uv.lobounds; mcimadamore@396: case EQUAL: return uv.inst != null ? List.of(uv.inst) : List.nil(); mcimadamore@396: } mcimadamore@396: } mcimadamore@396: } mcimadamore@396: return List.nil(); mcimadamore@396: } mcimadamore@396: mcimadamore@396: @Override mcimadamore@299: public Type inst(List inferred, Types types) throws NoInstanceException { mcimadamore@299: List formals = types.subst(mt2.argtypes, tvars, inferred); mcimadamore@396: if (!rs.argumentsAcceptable(capturedArgs, formals, mcimadamore@299: allowBoxing, useVarargs, warn)) { mcimadamore@299: // inferred method is not applicable mcimadamore@299: throw invalidInstanceException.setMessage("inferred.do.not.conform.to.params", formals, argtypes); mcimadamore@396: } mcimadamore@396: // check that inferred bounds conform to their bounds mcimadamore@396: checkWithinBounds(all_tvars, mcimadamore@299: types.subst(inferredTypes, tvars, inferred), warn); mcimadamore@547: if (useVarargs) { mcimadamore@547: chk.checkVararg(env.tree.pos(), formals); mcimadamore@547: } mcimadamore@396: return super.inst(inferred, types); mcimadamore@299: }}; mcimadamore@299: return mt2; duke@1: } mcimadamore@299: else if (!rs.argumentsAcceptable(capturedArgs, mt.getParameterTypes(), allowBoxing, useVarargs, warn)) { mcimadamore@299: // inferred method is not applicable mcimadamore@299: throw invalidInstanceException.setMessage("inferred.do.not.conform.to.params", mt.getParameterTypes(), argtypes); mcimadamore@299: } mcimadamore@299: else { mcimadamore@299: // return instantiated version of method type mcimadamore@299: return mt; mcimadamore@299: } duke@1: } duke@1: //where duke@1: duke@1: /** Try to instantiate argument type `that' to given type `to'. duke@1: * If this fails, try to insantiate `that' to `to' where duke@1: * every occurrence of a type variable in `tvars' is replaced duke@1: * by an unknown type. duke@1: */ duke@1: private Type instantiateArg(ForAll that, duke@1: Type to, duke@1: List tvars, mcimadamore@299: Warner warn) throws InferenceException { duke@1: List targs; duke@1: try { duke@1: return instantiateExpr(that, to, warn); duke@1: } catch (NoInstanceException ex) { duke@1: Type to1 = to; duke@1: for (List l = tvars; l.nonEmpty(); l = l.tail) duke@1: to1 = types.subst(to1, List.of(l.head), List.of(syms.unknownType)); duke@1: return instantiateExpr(that, to1, warn); duke@1: } duke@1: } duke@1: duke@1: /** check that type parameters are within their bounds. duke@1: */ duke@1: private void checkWithinBounds(List tvars, duke@1: List arguments, duke@1: Warner warn) mcimadamore@299: throws InvalidInstanceException { duke@1: for (List tvs = tvars, args = arguments; duke@1: tvs.nonEmpty(); duke@1: tvs = tvs.tail, args = args.tail) { duke@1: if (args.head instanceof UndetVar) continue; duke@1: List bounds = types.subst(types.getBounds((TypeVar)tvs.head), tvars, arguments); duke@1: if (!types.isSubtypeUnchecked(args.head, bounds, warn)) mcimadamore@299: throw invalidInstanceException duke@1: .setMessage("inferred.do.not.conform.to.bounds", mcimadamore@299: args.head, bounds); duke@1: } duke@1: } duke@1: }