1 /*

     2  * Copyright 1999-2006 Sun Microsystems, Inc.  All Rights Reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Sun designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Sun in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    22  * CA 95054 USA or visit www.sun.com if you need additional information or

    23  * have any questions.

    24  */

    25 

    26 package com.sun.tools.javac.comp;

    27 

    28 import com.sun.tools.javac.util.*;

    29 import com.sun.tools.javac.util.List;

    30 import com.sun.tools.javac.code.*;

    31 import com.sun.tools.javac.code.Type.*;

    32 

    33 import static com.sun.tools.javac.code.Flags.*;

    34 import static com.sun.tools.javac.code.Kinds.*;

    35 import static com.sun.tools.javac.code.TypeTags.*;

    36 

    37 /** Helper class for type parameter inference, used by the attribution phase.

    38  *

    39  *  <p><b>This is NOT part of any API supported by Sun Microsystems.  If

    40  *  you write code that depends on this, you do so at your own risk.

    41  *  This code and its internal interfaces are subject to change or

    42  *  deletion without notice.</b>

    43  */

    44 public class Infer {

    45     protected static final Context.Key<Infer> inferKey =

    46         new Context.Key<Infer>();

    47 

    48     /** A value for prototypes that admit any type, including polymorphic ones. */

    49     public static final Type anyPoly = new Type(NONE, null);

    50 

    51     Symtab syms;

    52     Types types;

    53 

    54     public static Infer instance(Context context) {

    55         Infer instance = context.get(inferKey);

    56         if (instance == null)

    57             instance = new Infer(context);

    58         return instance;

    59     }

    60 

    61     protected Infer(Context context) {

    62         context.put(inferKey, this);

    63         syms = Symtab.instance(context);

    64         types = Types.instance(context);

    65     }

    66 

    67     public static class NoInstanceException extends RuntimeException {

    68         private static final long serialVersionUID = 0;

    69 

    70         boolean isAmbiguous; // exist several incomparable best instances?

    71 

    72         JCDiagnostic diagnostic;

    73 

    74         NoInstanceException(boolean isAmbiguous) {

    75             this.diagnostic = null;

    76             this.isAmbiguous = isAmbiguous;

    77         }

    78         NoInstanceException setMessage(String key) {

    79             this.diagnostic = JCDiagnostic.fragment(key);

    80             return this;

    81         }

    82         NoInstanceException setMessage(String key, Object arg1) {

    83             this.diagnostic = JCDiagnostic.fragment(key, arg1);

    84             return this;

    85         }

    86         NoInstanceException setMessage(String key, Object arg1, Object arg2) {

    87             this.diagnostic = JCDiagnostic.fragment(key, arg1, arg2);

    88             return this;

    89         }

    90         NoInstanceException setMessage(String key, Object arg1, Object arg2, Object arg3) {

    91             this.diagnostic = JCDiagnostic.fragment(key, arg1, arg2, arg3);

    92             return this;

    93         }

    94         public JCDiagnostic getDiagnostic() {

    95             return diagnostic;

    96         }

    97     }

    98     private final NoInstanceException ambiguousNoInstanceException =

    99         new NoInstanceException(true);

   100     private final NoInstanceException unambiguousNoInstanceException =

   101         new NoInstanceException(false);

   102 

   103 /***************************************************************************

   104  * Auxiliary type values and classes

   105  ***************************************************************************/

   106 

   107     /** A mapping that turns type variables into undetermined type variables.

   108      */

   109     Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") {

   110             public Type apply(Type t) {

   111                 if (t.tag == TYPEVAR) return new UndetVar(t);

   112                 else return t.map(this);

   113             }

   114         };

   115 

   116     /** A mapping that returns its type argument with every UndetVar replaced

   117      *  by its `inst' field. Throws a NoInstanceException

   118      *  if this not possible because an `inst' field is null.

   119      */

   120     Mapping getInstFun = new Mapping("getInstFun") {

   121             public Type apply(Type t) {

   122                 switch (t.tag) {

   123                 case UNKNOWN:

   124                     throw ambiguousNoInstanceException

   125                         .setMessage("undetermined.type");

   126                 case UNDETVAR:

   127                     UndetVar that = (UndetVar) t;

   128                     if (that.inst == null)

   129                         throw ambiguousNoInstanceException

   130                             .setMessage("type.variable.has.undetermined.type",

   131                                         that.qtype);

   132                     return apply(that.inst);

   133                 default:

   134                     return t.map(this);

   135                 }

   136             }

   137         };

   138 

   139 /***************************************************************************

   140  * Mini/Maximization of UndetVars

   141  ***************************************************************************/

   142 

   143     /** Instantiate undetermined type variable to its minimal upper bound.

   144      *  Throw a NoInstanceException if this not possible.

   145      */

   146     void maximizeInst(UndetVar that, Warner warn) throws NoInstanceException {

   147         if (that.inst == null) {

   148             if (that.hibounds.isEmpty())

   149                 that.inst = syms.objectType;

   150             else if (that.hibounds.tail.isEmpty())

   151                 that.inst = that.hibounds.head;

   152             else {

   153                 for (List<Type> bs = that.hibounds;

   154                      bs.nonEmpty() && that.inst == null;

   155                      bs = bs.tail) {

   156                     // System.out.println("hibounds = " + that.hibounds);//DEBUG

   157                     if (isSubClass(bs.head, that.hibounds))

   158                         that.inst = types.fromUnknownFun.apply(bs.head);

   159                 }

   160                 if (that.inst == null || !types.isSubtypeUnchecked(that.inst, that.hibounds, warn))

   161                     throw ambiguousNoInstanceException

   162                         .setMessage("no.unique.maximal.instance.exists",

   163                                     that.qtype, that.hibounds);

   164             }

   165         }

   166     }

   167     //where

   168         private boolean isSubClass(Type t, final List<Type> ts) {

   169             t = t.baseType();

   170             if (t.tag == TYPEVAR) {

   171                 List<Type> bounds = types.getBounds((TypeVar)t);

   172                 for (Type s : ts) {

   173                     if (!types.isSameType(t, s.baseType())) {

   174                         for (Type bound : bounds) {

   175                             if (!isSubClass(bound, List.of(s.baseType())))

   176                                 return false;

   177                         }

   178                     }

   179                 }

   180             } else {

   181                 for (Type s : ts) {

   182                     if (!t.tsym.isSubClass(s.baseType().tsym, types))

   183                         return false;

   184                 }

   185             }

   186             return true;

   187         }

   188 

   189     /** Instaniate undetermined type variable to the lub of all its lower bounds.

   190      *  Throw a NoInstanceException if this not possible.

   191      */

   192     void minimizeInst(UndetVar that, Warner warn) throws NoInstanceException {

   193         if (that.inst == null) {

   194             if (that.lobounds.isEmpty())

   195                 that.inst = syms.botType;

   196             else if (that.lobounds.tail.isEmpty())

   197                 that.inst = that.lobounds.head;

   198             else {

   199                 that.inst = types.lub(that.lobounds);

   200                 if (that.inst == null)

   201                     throw ambiguousNoInstanceException

   202                         .setMessage("no.unique.minimal.instance.exists",

   203                                     that.qtype, that.lobounds);

   204             }

   205             // VGJ: sort of inlined maximizeInst() below.  Adding

   206             // bounds can cause lobounds that are above hibounds.

   207             if (that.hibounds.isEmpty())

   208                 return;

   209             Type hb = null;

   210             if (that.hibounds.tail.isEmpty())

   211                 hb = that.hibounds.head;

   212             else for (List<Type> bs = that.hibounds;

   213                       bs.nonEmpty() && hb == null;

   214                       bs = bs.tail) {

   215                 if (isSubClass(bs.head, that.hibounds))

   216                     hb = types.fromUnknownFun.apply(bs.head);

   217             }

   218             if (hb == null ||

   219                 !types.isSubtypeUnchecked(hb, that.hibounds, warn) ||

   220                 !types.isSubtypeUnchecked(that.inst, hb, warn))

   221                 throw ambiguousNoInstanceException;

   222         }

   223     }

   224 

   225 /***************************************************************************

   226  * Exported Methods

   227  ***************************************************************************/

   228 

   229     /** Try to instantiate expression type `that' to given type `to'.

   230      *  If a maximal instantiation exists which makes this type

   231      *  a subtype of type `to', return the instantiated type.

   232      *  If no instantiation exists, or if several incomparable

   233      *  best instantiations exist throw a NoInstanceException.

   234      */

   235     public Type instantiateExpr(ForAll that,

   236                                 Type to,

   237                                 Warner warn) throws NoInstanceException {

   238         List<Type> undetvars = Type.map(that.tvars, fromTypeVarFun);

   239         for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail) {

   240             UndetVar v = (UndetVar) l.head;

   241             ListBuffer<Type> hibounds = new ListBuffer<Type>();

   242             for (List<Type> l1 = types.getBounds((TypeVar) v.qtype); l1.nonEmpty(); l1 = l1.tail) {

   243                 if (!l1.head.containsSome(that.tvars)) {

   244                     hibounds.append(l1.head);

   245                 }

   246             }

   247             v.hibounds = hibounds.toList();

   248         }

   249         Type qtype1 = types.subst(that.qtype, that.tvars, undetvars);

   250         if (!types.isSubtype(qtype1, to)) {

   251             throw unambiguousNoInstanceException

   252                 .setMessage("no.conforming.instance.exists",

   253                             that.tvars, that.qtype, to);

   254         }

   255         for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail)

   256             maximizeInst((UndetVar) l.head, warn);

   257         // System.out.println(" = " + qtype1.map(getInstFun));//DEBUG

   258 

   259         // check bounds

   260         List<Type> targs = Type.map(undetvars, getInstFun);

   261         targs = types.subst(targs, that.tvars, targs);

   262         checkWithinBounds(that.tvars, targs, warn);

   263 

   264         return getInstFun.apply(qtype1);

   265     }

   266 

   267     /** Instantiate method type `mt' by finding instantiations of

   268      *  `tvars' so that method can be applied to `argtypes'.

   269      */

   270     public Type instantiateMethod(List<Type> tvars,

   271                                   MethodType mt,

   272                                   List<Type> argtypes,

   273                                   boolean allowBoxing,

   274                                   boolean useVarargs,

   275                                   Warner warn) throws NoInstanceException {

   276         //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG

   277         List<Type> undetvars = Type.map(tvars, fromTypeVarFun);

   278         List<Type> formals = mt.argtypes;

   279 

   280         // instantiate all polymorphic argument types and

   281         // set up lower bounds constraints for undetvars

   282         Type varargsFormal = useVarargs ? formals.last() : null;

   283         while (argtypes.nonEmpty() && formals.head != varargsFormal) {

   284             Type ft = formals.head;

   285             Type at = argtypes.head.baseType();

   286             if (at.tag == FORALL)

   287                 at = instantiateArg((ForAll) at, ft, tvars, warn);

   288             Type sft = types.subst(ft, tvars, undetvars);

   289             boolean works = allowBoxing

   290                 ? types.isConvertible(at, sft, warn)

   291                 : types.isSubtypeUnchecked(at, sft, warn);

   292             if (!works) {

   293                 throw unambiguousNoInstanceException

   294                     .setMessage("no.conforming.assignment.exists",

   295                                 tvars, at, ft);

   296             }

   297             formals = formals.tail;

   298             argtypes = argtypes.tail;

   299         }

   300         if (formals.head != varargsFormal || // not enough args

   301             !useVarargs && argtypes.nonEmpty()) { // too many args

   302             // argument lists differ in length

   303             throw unambiguousNoInstanceException

   304                 .setMessage("arg.length.mismatch");

   305         }

   306 

   307         // for varargs arguments as well

   308         if (useVarargs) {

   309             Type elt = types.elemtype(varargsFormal);

   310             Type sft = types.subst(elt, tvars, undetvars);

   311             while (argtypes.nonEmpty()) {

   312                 Type ft = sft;

   313                 Type at = argtypes.head.baseType();

   314                 if (at.tag == FORALL)

   315                     at = instantiateArg((ForAll) at, ft, tvars, warn);

   316                 boolean works = types.isConvertible(at, sft, warn);

   317                 if (!works) {

   318                     throw unambiguousNoInstanceException

   319                         .setMessage("no.conforming.assignment.exists",

   320                                     tvars, at, ft);

   321                 }

   322                 argtypes = argtypes.tail;

   323             }

   324         }

   325 

   326         // minimize as yet undetermined type variables

   327         for (Type t : undetvars)

   328             minimizeInst((UndetVar) t, warn);

   329 

   330         /** Type variables instantiated to bottom */

   331         ListBuffer<Type> restvars = new ListBuffer<Type>();

   332 

   333         /** Instantiated types or TypeVars if under-constrained */

   334         ListBuffer<Type> insttypes = new ListBuffer<Type>();

   335 

   336         /** Instantiated types or UndetVars if under-constrained */

   337         ListBuffer<Type> undettypes = new ListBuffer<Type>();

   338 

   339         for (Type t : undetvars) {

   340             UndetVar uv = (UndetVar)t;

   341             if (uv.inst.tag == BOT) {

   342                 restvars.append(uv.qtype);

   343                 insttypes.append(uv.qtype);

   344                 undettypes.append(uv);

   345                 uv.inst = null;

   346             } else {

   347                 insttypes.append(uv.inst);

   348                 undettypes.append(uv.inst);

   349             }

   350         }

   351         checkWithinBounds(tvars, undettypes.toList(), warn);

   352 

   353         if (!restvars.isEmpty()) {

   354             // if there are uninstantiated variables,

   355             // quantify result type with them

   356             mt = new MethodType(mt.argtypes,

   357                                 new ForAll(restvars.toList(), mt.restype),

   358                                 mt.thrown, syms.methodClass);

   359         }

   360 

   361         // return instantiated version of method type

   362         return types.subst(mt, tvars, insttypes.toList());

   363     }

   364     //where

   365 

   366         /** Try to instantiate argument type `that' to given type `to'.

   367          *  If this fails, try to insantiate `that' to `to' where

   368          *  every occurrence of a type variable in `tvars' is replaced

   369          *  by an unknown type.

   370          */

   371         private Type instantiateArg(ForAll that,

   372                                     Type to,

   373                                     List<Type> tvars,

   374                                     Warner warn) throws NoInstanceException {

   375             List<Type> targs;

   376             try {

   377                 return instantiateExpr(that, to, warn);

   378             } catch (NoInstanceException ex) {

   379                 Type to1 = to;

   380                 for (List<Type> l = tvars; l.nonEmpty(); l = l.tail)

   381                     to1 = types.subst(to1, List.of(l.head), List.of(syms.unknownType));

   382                 return instantiateExpr(that, to1, warn);

   383             }

   384         }

   385 

   386     /** check that type parameters are within their bounds.

   387      */

   388     private void checkWithinBounds(List<Type> tvars,

   389                                    List<Type> arguments,

   390                                    Warner warn)

   391         throws NoInstanceException {

   392         for (List<Type> tvs = tvars, args = arguments;

   393              tvs.nonEmpty();

   394              tvs = tvs.tail, args = args.tail) {

   395             if (args.head instanceof UndetVar) continue;

   396             List<Type> bounds = types.subst(types.getBounds((TypeVar)tvs.head), tvars, arguments);

   397             if (!types.isSubtypeUnchecked(args.head, bounds, warn))

   398                 throw unambiguousNoInstanceException

   399                     .setMessage("inferred.do.not.conform.to.bounds",

   400                                 arguments, tvars);

   401         }

   402     }

   403 }