duke@1: /*
duke@1:  * Copyright 1999-2006 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.*;
duke@1: 
duke@1: import static com.sun.tools.javac.code.Flags.*;
duke@1: import static com.sun.tools.javac.code.Kinds.*;
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:  *  <p><b>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.</b>
duke@1:  */
duke@1: public class Infer {
duke@1:     protected static final Context.Key<Infer> inferKey =
duke@1:         new Context.Key<Infer>();
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;
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);
duke@1:     }
duke@1: 
duke@1:     public static class NoInstanceException extends RuntimeException {
duke@1:         private static final long serialVersionUID = 0;
duke@1: 
duke@1:         boolean isAmbiguous; // exist several incomparable best instances?
duke@1: 
duke@1:         JCDiagnostic diagnostic;
duke@1: 
duke@1:         NoInstanceException(boolean isAmbiguous) {
duke@1:             this.diagnostic = null;
duke@1:             this.isAmbiguous = isAmbiguous;
duke@1:         }
duke@1:         NoInstanceException setMessage(String key) {
duke@1:             this.diagnostic = JCDiagnostic.fragment(key);
duke@1:             return this;
duke@1:         }
duke@1:         NoInstanceException setMessage(String key, Object arg1) {
duke@1:             this.diagnostic = JCDiagnostic.fragment(key, arg1);
duke@1:             return this;
duke@1:         }
duke@1:         NoInstanceException setMessage(String key, Object arg1, Object arg2) {
duke@1:             this.diagnostic = JCDiagnostic.fragment(key, arg1, arg2);
duke@1:             return this;
duke@1:         }
duke@1:         NoInstanceException setMessage(String key, Object arg1, Object arg2, Object arg3) {
duke@1:             this.diagnostic = JCDiagnostic.fragment(key, arg1, arg2, arg3);
duke@1:             return this;
duke@1:         }
duke@1:         public JCDiagnostic getDiagnostic() {
duke@1:             return diagnostic;
duke@1:         }
duke@1:     }
duke@1:     private final NoInstanceException ambiguousNoInstanceException =
duke@1:         new NoInstanceException(true);
duke@1:     private final NoInstanceException unambiguousNoInstanceException =
duke@1:         new NoInstanceException(false);
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;
duke@1:             else {
duke@1:                 for (List<Type> bs = that.hibounds;
duke@1:                      bs.nonEmpty() && that.inst == null;
duke@1:                      bs = bs.tail) {
duke@1:                     // System.out.println("hibounds = " + that.hibounds);//DEBUG
duke@1:                     if (isSubClass(bs.head, that.hibounds))
duke@1:                         that.inst = types.fromUnknownFun.apply(bs.head);
duke@1:                 }
duke@1:                 if (that.inst == null || !types.isSubtypeUnchecked(that.inst, that.hibounds, warn))
duke@1:                     throw ambiguousNoInstanceException
duke@1:                         .setMessage("no.unique.maximal.instance.exists",
duke@1:                                     that.qtype, that.hibounds);
duke@1:             }
duke@1:         }
duke@1:     }
duke@1:     //where
duke@1:         private boolean isSubClass(Type t, final List<Type> ts) {
duke@1:             t = t.baseType();
duke@1:             if (t.tag == TYPEVAR) {
duke@1:                 List<Type> 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: 
duke@1:     /** Instaniate 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:             }
mcimadamore@5:             if (that.inst == null || that.inst == syms.errType)
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<Type> 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,
duke@1:                                 Warner warn) throws NoInstanceException {
duke@1:         List<Type> undetvars = Type.map(that.tvars, fromTypeVarFun);
duke@1:         for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail) {
duke@1:             UndetVar v = (UndetVar) l.head;
duke@1:             ListBuffer<Type> hibounds = new ListBuffer<Type>();
duke@1:             for (List<Type> 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<Type> 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<Type> targs = Type.map(undetvars, getInstFun);
duke@1:         targs = types.subst(targs, that.tvars, targs);
duke@1:         checkWithinBounds(that.tvars, targs, warn);
duke@1: 
duke@1:         return getInstFun.apply(qtype1);
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<Type> tvars,
duke@1:                                   MethodType mt,
duke@1:                                   List<Type> argtypes,
duke@1:                                   boolean allowBoxing,
duke@1:                                   boolean useVarargs,
duke@1:                                   Warner warn) throws NoInstanceException {
duke@1:         //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
duke@1:         List<Type> undetvars = Type.map(tvars, fromTypeVarFun);
duke@1:         List<Type> formals = mt.argtypes;
duke@1: 
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;
duke@1:         while (argtypes.nonEmpty() && formals.head != varargsFormal) {
duke@1:             Type ft = formals.head;
duke@1:             Type at = argtypes.head.baseType();
duke@1:             if (at.tag == FORALL)
duke@1:                 at = instantiateArg((ForAll) at, ft, tvars, warn);
duke@1:             Type sft = types.subst(ft, tvars, undetvars);
duke@1:             boolean works = allowBoxing
duke@1:                 ? types.isConvertible(at, sft, warn)
duke@1:                 : types.isSubtypeUnchecked(at, sft, warn);
duke@1:             if (!works) {
duke@1:                 throw unambiguousNoInstanceException
duke@1:                     .setMessage("no.conforming.assignment.exists",
duke@1:                                 tvars, at, ft);
duke@1:             }
duke@1:             formals = formals.tail;
duke@1:             argtypes = argtypes.tail;
duke@1:         }
duke@1:         if (formals.head != varargsFormal || // not enough args
duke@1:             !useVarargs && argtypes.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) {
duke@1:             Type elt = types.elemtype(varargsFormal);
duke@1:             Type sft = types.subst(elt, tvars, undetvars);
duke@1:             while (argtypes.nonEmpty()) {
duke@1:                 Type ft = sft;
duke@1:                 Type at = argtypes.head.baseType();
duke@1:                 if (at.tag == FORALL)
duke@1:                     at = instantiateArg((ForAll) at, ft, tvars, warn);
duke@1:                 boolean works = types.isConvertible(at, sft, warn);
duke@1:                 if (!works) {
duke@1:                     throw unambiguousNoInstanceException
duke@1:                         .setMessage("no.conforming.assignment.exists",
duke@1:                                     tvars, at, ft);
duke@1:                 }
duke@1:                 argtypes = argtypes.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<Type> restvars = new ListBuffer<Type>();
duke@1: 
duke@1:         /** Instantiated types or TypeVars if under-constrained */
duke@1:         ListBuffer<Type> insttypes = new ListBuffer<Type>();
duke@1: 
duke@1:         /** Instantiated types or UndetVars if under-constrained */
duke@1:         ListBuffer<Type> undettypes = new ListBuffer<Type>();
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: 
duke@1:         if (!restvars.isEmpty()) {
duke@1:             // if there are uninstantiated variables,
duke@1:             // quantify result type with them
duke@1:             mt = new MethodType(mt.argtypes,
duke@1:                                 new ForAll(restvars.toList(), mt.restype),
duke@1:                                 mt.thrown, syms.methodClass);
duke@1:         }
duke@1: 
duke@1:         // return instantiated version of method type
duke@1:         return types.subst(mt, tvars, insttypes.toList());
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<Type> tvars,
duke@1:                                     Warner warn) throws NoInstanceException {
duke@1:             List<Type> 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<Type> 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<Type> tvars,
duke@1:                                    List<Type> arguments,
duke@1:                                    Warner warn)
duke@1:         throws NoInstanceException {
duke@1:         for (List<Type> 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<Type> bounds = types.subst(types.getBounds((TypeVar)tvs.head), tvars, arguments);
duke@1:             if (!types.isSubtypeUnchecked(args.head, bounds, warn))
duke@1:                 throw unambiguousNoInstanceException
duke@1:                     .setMessage("inferred.do.not.conform.to.bounds",
duke@1:                                 arguments, tvars);
duke@1:         }
duke@1:     }
duke@1: }