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@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@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@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) {
duke@1: UndetVar v = (UndetVar) l.head;
duke@1: ListBuffer hibounds = new ListBuffer();
duke@1: for (List l1 = types.getBounds((TypeVar) v.qtype); l1.nonEmpty(); l1 = l1.tail) {
duke@1: if (!l1.head.containsSome(that.tvars)) {
duke@1: hibounds.append(l1.head);
duke@1: }
duke@1: }
duke@1: v.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@299: return that.inst(targs, types);
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: */
duke@1: public Type instantiateMethod(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:
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);
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@299: public Type inst(List inferred, Types types) throws NoInstanceException {
mcimadamore@299: List formals = types.subst(mt2.argtypes, tvars, inferred);
mcimadamore@299: 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@299: }
mcimadamore@299: // check that inferred bounds conform to their bounds
mcimadamore@299: checkWithinBounds(all_tvars,
mcimadamore@299: types.subst(inferredTypes, tvars, inferred), warn);
mcimadamore@299: 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: }