jdk8-mips64-public/langtools: src/share/classes/com/sun/tools/javac/comp/Infer.java@37031963493e

     1 /*

     2  * Copyright (c) 1999, 2013, Oracle and/or its affiliates. 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.  Oracle designates this

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

     9  * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

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

    28 import com.sun.tools.javac.tree.JCTree;

    29 import com.sun.tools.javac.tree.JCTree.JCTypeCast;

    30 import com.sun.tools.javac.tree.TreeInfo;

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

    32 import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;

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

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

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

    36 import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;

    37 import com.sun.tools.javac.code.Symbol.*;

    38 import com.sun.tools.javac.comp.DeferredAttr.AttrMode;

    39 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph;

    40 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node;

    41 import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;

    42 import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;

    44 import java.util.HashMap;

    45 import java.util.Map;

    46 import java.util.Set;

    48 import java.util.ArrayList;

    49 import java.util.Collections;

    50 import java.util.EnumSet;

    51 import java.util.HashSet;

    53 import static com.sun.tools.javac.code.TypeTag.*;

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

    56  *

    57  *  <p><b>This is NOT part of any supported API.

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

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

    60  *  deletion without notice.</b>

    61  */

    62 public class Infer {

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

    64         new Context.Key<Infer>();

    66     Resolve rs;

    67     Check chk;

    68     Symtab syms;

    69     Types types;

    70     JCDiagnostic.Factory diags;

    71     Log log;

    73     /** should the graph solver be used? */

    74     boolean allowGraphInference;

    76     public static Infer instance(Context context) {

    77         Infer instance = context.get(inferKey);

    78         if (instance == null)

    79             instance = new Infer(context);

    80         return instance;

    81     }

    83     protected Infer(Context context) {

    84         context.put(inferKey, this);

    86         rs = Resolve.instance(context);

    87         chk = Check.instance(context);

    88         syms = Symtab.instance(context);

    89         types = Types.instance(context);

    90         diags = JCDiagnostic.Factory.instance(context);

    91         log = Log.instance(context);

    92         inferenceException = new InferenceException(diags);

    93         Options options = Options.instance(context);

    94         allowGraphInference = Source.instance(context).allowGraphInference()

    95                 && options.isUnset("useLegacyInference");

    96     }

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

    99     public static final Type anyPoly = new JCNoType();

   101    /**

   102     * This exception class is design to store a list of diagnostics corresponding

   103     * to inference errors that can arise during a method applicability check.

   104     */

   105     public static class InferenceException extends InapplicableMethodException {

   106         private static final long serialVersionUID = 0;

   108         List<JCDiagnostic> messages = List.nil();

   110         InferenceException(JCDiagnostic.Factory diags) {

   111             super(diags);

   112         }

   114         @Override

   115         InapplicableMethodException setMessage(JCDiagnostic diag) {

   116             messages = messages.append(diag);

   117             return this;

   118         }

   120         @Override

   121         public JCDiagnostic getDiagnostic() {

   122             return messages.head;

   123         }

   125         void clear() {

   126             messages = List.nil();

   127         }

   128     }

   130     protected final InferenceException inferenceException;

   132     // <editor-fold defaultstate="collapsed" desc="Inference routines">

   133     /**

   134      * Main inference entry point - instantiate a generic method type

   135      * using given argument types and (possibly) an expected target-type.

   136      */

   137     public Type instantiateMethod(Env<AttrContext> env,

   138                                   List<Type> tvars,

   139                                   MethodType mt,

   140                                   Attr.ResultInfo resultInfo,

   141                                   Symbol msym,

   142                                   List<Type> argtypes,

   143                                   boolean allowBoxing,

   144                                   boolean useVarargs,

   145                                   Resolve.MethodResolutionContext resolveContext,

   146                                   Warner warn) throws InferenceException {

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

   148         final InferenceContext inferenceContext = new InferenceContext(tvars);

   149         inferenceException.clear();

   150         try {

   151             DeferredAttr.DeferredAttrContext deferredAttrContext =

   152                     resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);

   154             resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext,

   155                     argtypes, mt.getParameterTypes(), warn);

   157             if (allowGraphInference &&

   158                     resultInfo != null &&

   159                     !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {

   160                 //inject return constraints earlier

   161                 checkWithinBounds(inferenceContext, warn); //propagation

   162                 generateReturnConstraints(resultInfo, mt, inferenceContext);

   163                 //propagate outwards if needed

   164                 if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) {

   165                     //propagate inference context outwards and exit

   166                     inferenceContext.dupTo(resultInfo.checkContext.inferenceContext());

   167                     deferredAttrContext.complete();

   168                     return mt;

   169                 }

   170             }

   172             deferredAttrContext.complete();

   174             // minimize as yet undetermined type variables

   175             if (allowGraphInference) {

   176                 inferenceContext.solve(warn);

   177             } else {

   178                 inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst

   179             }

   181             mt = (MethodType)inferenceContext.asInstType(mt);

   183             if (!allowGraphInference &&

   184                     inferenceContext.restvars().nonEmpty() &&

   185                     resultInfo != null &&

   186                     !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {

   187                 generateReturnConstraints(resultInfo, mt, inferenceContext);

   188                 inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst

   189                 mt = (MethodType)inferenceContext.asInstType(mt);

   190             }

   192             if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {

   193                 log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);

   194             }

   196             // return instantiated version of method type

   197             return mt;

   198         } finally {

   199             if (resultInfo != null || !allowGraphInference) {

   200                 inferenceContext.notifyChange();

   201             } else {

   202                 inferenceContext.notifyChange(inferenceContext.boundedVars());

   203             }

   204         }

   205     }

   207     /**

   208      * Generate constraints from the generic method's return type. If the method

   209      * call occurs in a context where a type T is expected, use the expected

   210      * type to derive more constraints on the generic method inference variables.

   211      */

   212     void generateReturnConstraints(Attr.ResultInfo resultInfo,

   213             MethodType mt, InferenceContext inferenceContext) {

   214         Type qtype1 = inferenceContext.asFree(mt.getReturnType());

   215         Type to = returnConstraintTarget(qtype1, resultInfo.pt);

   216         Assert.check(allowGraphInference || !resultInfo.checkContext.inferenceContext().free(to),

   217                 "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");

   218         //we need to skip capture?

   219         Warner retWarn = new Warner();

   220         if (!resultInfo.checkContext.compatible(qtype1, resultInfo.checkContext.inferenceContext().asFree(to), retWarn) ||

   221                 //unchecked conversion is not allowed in source 7 mode

   222                 (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) {

   223             throw inferenceException

   224                     .setMessage("infer.no.conforming.instance.exists",

   225                     inferenceContext.restvars(), mt.getReturnType(), to);

   226         }

   227     }

   228     //where

   229         private Type returnConstraintTarget(Type from, Type to) {

   230             if (from.hasTag(VOID)) {

   231                 return syms.voidType;

   232             } else if (to.hasTag(NONE)) {

   233                 return from.isPrimitive() ? from : syms.objectType;

   234             } else if (from.hasTag(UNDETVAR) && to.isPrimitive()) {

   235                 if (!allowGraphInference) {

   236                     //if legacy, just return boxed type

   237                     return types.boxedClass(to).type;

   238                 }

   239                 //if graph inference we need to skip conflicting boxed bounds...

   240                 UndetVar uv = (UndetVar)from;

   241                 for (Type t : uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {

   242                     Type boundAsPrimitive = types.unboxedType(t);

   243                     if (boundAsPrimitive == null) continue;

   244                     if (types.isConvertible(boundAsPrimitive, to)) {

   245                         //effectively skip return-type constraint generation (compatibility)

   246                         return syms.objectType;

   247                     }

   248                 }

   249                 return types.boxedClass(to).type;

   250             } else {

   251                 return to;

   252             }

   253         }

   255     /**

   256       * Infer cyclic inference variables as described in 15.12.2.8.

   257       */

   258     private void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) {

   259         ListBuffer<Type> todo = ListBuffer.lb();

   260         //step 1 - create fresh tvars

   261         for (Type t : vars) {

   262             UndetVar uv = (UndetVar)inferenceContext.asFree(t);

   263             List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER);

   264             if (Type.containsAny(upperBounds, vars)) {

   265                 TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);

   266                 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null);

   267                 todo.append(uv);

   268                 uv.inst = fresh_tvar.type;

   269             } else if (upperBounds.nonEmpty()) {

   270                 uv.inst = types.glb(upperBounds);

   271             } else {

   272                 uv.inst = syms.objectType;

   273             }

   274         }

   275         //step 2 - replace fresh tvars in their bounds

   276         List<Type> formals = vars;

   277         for (Type t : todo) {

   278             UndetVar uv = (UndetVar)t;

   279             TypeVar ct = (TypeVar)uv.inst;

   280             ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct)));

   281             if (ct.bound.isErroneous()) {

   282                 //report inference error if glb fails

   283                 reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   284             }

   285             formals = formals.tail;

   286         }

   287     }

   289     /**

   290      * Compute a synthetic method type corresponding to the requested polymorphic

   291      * method signature. The target return type is computed from the immediately

   292      * enclosing scope surrounding the polymorphic-signature call.

   293      */

   294     Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,

   295                                             MethodSymbol spMethod,  // sig. poly. method or null if none

   296                                             Resolve.MethodResolutionContext resolveContext,

   297                                             List<Type> argtypes) {

   298         final Type restype;

   300         //The return type for a polymorphic signature call is computed from

   301         //the enclosing tree E, as follows: if E is a cast, then use the

   302         //target type of the cast expression as a return type; if E is an

   303         //expression statement, the return type is 'void' - otherwise the

   304         //return type is simply 'Object'. A correctness check ensures that

   305         //env.next refers to the lexically enclosing environment in which

   306         //the polymorphic signature call environment is nested.

   308         switch (env.next.tree.getTag()) {

   309             case TYPECAST:

   310                 JCTypeCast castTree = (JCTypeCast)env.next.tree;

   311                 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?

   312                     castTree.clazz.type :

   313                     syms.objectType;

   314                 break;

   315             case EXEC:

   316                 JCTree.JCExpressionStatement execTree =

   317                         (JCTree.JCExpressionStatement)env.next.tree;

   318                 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?

   319                     syms.voidType :

   320                     syms.objectType;

   321                 break;

   322             default:

   323                 restype = syms.objectType;

   324         }

   326         List<Type> paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step));

   327         List<Type> exType = spMethod != null ?

   328             spMethod.getThrownTypes() :

   329             List.of(syms.throwableType); // make it throw all exceptions

   331         MethodType mtype = new MethodType(paramtypes,

   332                                           restype,

   333                                           exType,

   334                                           syms.methodClass);

   335         return mtype;

   336     }

   337     //where

   338         class ImplicitArgType extends DeferredAttr.DeferredTypeMap {

   340             public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {

   341                 rs.deferredAttr.super(AttrMode.SPECULATIVE, msym, phase);

   342             }

   344             public Type apply(Type t) {

   345                 t = types.erasure(super.apply(t));

   346                 if (t.hasTag(BOT))

   347                     // nulls type as the marker type Null (which has no instances)

   348                     // infer as java.lang.Void for now

   349                     t = types.boxedClass(syms.voidType).type;

   350                 return t;

   351             }

   352         }

   354     /**

   355       * This method is used to infer a suitable target SAM in case the original

   356       * SAM type contains one or more wildcards. An inference process is applied

   357       * so that wildcard bounds, as well as explicit lambda/method ref parameters

   358       * (where applicable) are used to constraint the solution.

   359       */

   360     public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,

   361             List<Type> paramTypes, Check.CheckContext checkContext) {

   362         if (types.capture(funcInterface) == funcInterface) {

   363             //if capture doesn't change the type then return the target unchanged

   364             //(this means the target contains no wildcards!)

   365             return funcInterface;

   366         } else {

   367             Type formalInterface = funcInterface.tsym.type;

   368             InferenceContext funcInterfaceContext =

   369                     new InferenceContext(funcInterface.tsym.type.getTypeArguments());

   371             Assert.check(paramTypes != null);

   372             //get constraints from explicit params (this is done by

   373             //checking that explicit param types are equal to the ones

   374             //in the functional interface descriptors)

   375             List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();

   376             if (descParameterTypes.size() != paramTypes.size()) {

   377                 checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda"));

   378                 return types.createErrorType(funcInterface);

   379             }

   380             for (Type p : descParameterTypes) {

   381                 if (!types.isSameType(funcInterfaceContext.asFree(p), paramTypes.head)) {

   382                     checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));

   383                     return types.createErrorType(funcInterface);

   384                 }

   385                 paramTypes = paramTypes.tail;

   386             }

   388             try {

   389                 funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings);

   390             } catch (InferenceException ex) {

   391                 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));

   392             }

   394             List<Type> actualTypeargs = funcInterface.getTypeArguments();

   395             for (Type t : funcInterfaceContext.undetvars) {

   396                 UndetVar uv = (UndetVar)t;

   397                 if (uv.inst == null) {

   398                     uv.inst = actualTypeargs.head;

   399                 }

   400                 actualTypeargs = actualTypeargs.tail;

   401             }

   403             Type owntype = funcInterfaceContext.asInstType(formalInterface);

   404             if (!chk.checkValidGenericType(owntype)) {

   405                 //if the inferred functional interface type is not well-formed,

   406                 //or if it's not a subtype of the original target, issue an error

   407                 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));

   408             }

   409             return owntype;

   410         }

   411     }

   412     // </editor-fold>

   414     // <editor-fold defaultstate="collapsed" desc="Bound checking">

   415     /**

   416      * Check bounds and perform incorporation

   417      */

   418     void checkWithinBounds(InferenceContext inferenceContext,

   419                              Warner warn) throws InferenceException {

   420         MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars);

   421         List<Type> saved_undet = inferenceContext.save();

   422         try {

   423             while (true) {

   424                 mlistener.reset();

   425                 if (!allowGraphInference) {

   426                     //in legacy mode we lack of transitivity, so bound check

   427                     //cannot be run in parallel with other incoprporation rounds

   428                     for (Type t : inferenceContext.undetvars) {

   429                         UndetVar uv = (UndetVar)t;

   430                         IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn);

   431                     }

   432                 }

   433                 for (Type t : inferenceContext.undetvars) {

   434                     UndetVar uv = (UndetVar)t;

   435                     //bound incorporation

   436                     EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?

   437                             incorporationStepsGraph : incorporationStepsLegacy;

   438                     for (IncorporationStep is : incorporationSteps) {

   439                         is.apply(uv, inferenceContext, warn);

   440                     }

   441                 }

   442                 if (!mlistener.changed || !allowGraphInference) break;

   443             }

   444         }

   445         finally {

   446             mlistener.detach();

   447             if (mlistener.rounds == MAX_INCORPORATION_STEPS) {

   448                 inferenceContext.rollback(saved_undet);

   449             }

   450         }

   451     }

   452     //where

   453         /**

   454          * This listener keeps track of changes on a group of inference variable

   455          * bounds. Note: the listener must be detached (calling corresponding

   456          * method) to make sure that the underlying inference variable is

   457          * left in a clean state.

   458          */

   459         class MultiUndetVarListener implements UndetVar.UndetVarListener {

   461             int rounds;

   462             boolean changed;

   463             List<Type> undetvars;

   465             public MultiUndetVarListener(List<Type> undetvars) {

   466                 this.undetvars = undetvars;

   467                 for (Type t : undetvars) {

   468                     UndetVar uv = (UndetVar)t;

   469                     uv.listener = this;

   470                 }

   471             }

   473             public void varChanged(UndetVar uv, Set<InferenceBound> ibs) {

   474                 //avoid non-termination

   475                 if (rounds < MAX_INCORPORATION_STEPS) {

   476                     changed = true;

   477                 }

   478             }

   480             void reset() {

   481                 rounds++;

   482                 changed = false;

   483             }

   485             void detach() {

   486                 for (Type t : undetvars) {

   487                     UndetVar uv = (UndetVar)t;

   488                     uv.listener = null;

   489                 }

   490             }

   491         };

   493         /** max number of incorporation rounds */

   494         static final int MAX_INCORPORATION_STEPS = 100;

   496     /**

   497      * This enumeration defines an entry point for doing inference variable

   498      * bound incorporation - it can be used to inject custom incorporation

   499      * logic into the basic bound checking routine

   500      */

   501     enum IncorporationStep {

   502         /**

   503          * Performs basic bound checking - i.e. is the instantiated type for a given

   504          * inference variable compatible with its bounds?

   505          */

   506         CHECK_BOUNDS() {

   507             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   508                 Infer infer = inferenceContext.infer();

   509                 uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types);

   510                 infer.checkCompatibleUpperBounds(uv, inferenceContext);

   511                 if (uv.inst != null) {

   512                     Type inst = uv.inst;

   513                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {

   514                         if (!infer.types.isSubtypeUnchecked(inst, inferenceContext.asFree(u), warn)) {

   515                             infer.reportBoundError(uv, BoundErrorKind.UPPER);

   516                         }

   517                     }

   518                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {

   519                         if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), inst, warn)) {

   520                             infer.reportBoundError(uv, BoundErrorKind.LOWER);

   521                         }

   522                     }

   523                     for (Type e : uv.getBounds(InferenceBound.EQ)) {

   524                         if (!infer.types.isSameType(inst, inferenceContext.asFree(e))) {

   525                             infer.reportBoundError(uv, BoundErrorKind.EQ);

   526                         }

   527                     }

   528                 }

   529             }

   530         },

   531         /**

   532          * Check consistency of equality constraints. This is a slightly more aggressive

   533          * inference routine that is designed as to maximize compatibility with JDK 7.

   534          * Note: this is not used in graph mode.

   535          */

   536         EQ_CHECK_LEGACY() {

   537             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   538                 Infer infer = inferenceContext.infer();

   539                 Type eq = null;

   540                 for (Type e : uv.getBounds(InferenceBound.EQ)) {

   541                     Assert.check(!inferenceContext.free(e));

   542                     if (eq != null && !infer.types.isSameType(e, eq)) {

   543                         infer.reportBoundError(uv, BoundErrorKind.EQ);

   544                     }

   545                     eq = e;

   546                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {

   547                         Assert.check(!inferenceContext.free(l));

   548                         if (!infer.types.isSubtypeUnchecked(l, e, warn)) {

   549                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);

   550                         }

   551                     }

   552                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {

   553                         if (inferenceContext.free(u)) continue;

   554                         if (!infer.types.isSubtypeUnchecked(e, u, warn)) {

   555                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);

   556                         }

   557                     }

   558                 }

   559             }

   560         },

   561         /**

   562          * Check consistency of equality constraints.

   563          */

   564         EQ_CHECK() {

   565             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   566                 Infer infer = inferenceContext.infer();

   567                 for (Type e : uv.getBounds(InferenceBound.EQ)) {

   568                     if (e.containsAny(inferenceContext.inferenceVars())) continue;

   569                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {

   570                         if (!infer.types.isSubtypeUnchecked(e, inferenceContext.asFree(u), warn)) {

   571                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);

   572                         }

   573                     }

   574                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {

   575                         if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), e, warn)) {

   576                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);

   577                         }

   578                     }

   579                 }

   580             }

   581         },

   582         /**

   583          * Given a bound set containing {@code alpha <: T} and {@code alpha :> S}

   584          * perform {@code S <: T} (which could lead to new bounds).

   585          */

   586         CROSS_UPPER_LOWER() {

   587             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   588                 Infer infer = inferenceContext.infer();

   589                 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {

   590                     for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {

   591                         infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));

   592                     }

   593                 }

   594             }

   595         },

   596         /**

   597          * Given a bound set containing {@code alpha <: T} and {@code alpha == S}

   598          * perform {@code S <: T} (which could lead to new bounds).

   599          */

   600         CROSS_UPPER_EQ() {

   601             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   602                 Infer infer = inferenceContext.infer();

   603                 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {

   604                     for (Type b2 : uv.getBounds(InferenceBound.EQ)) {

   605                         infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));

   606                     }

   607                 }

   608             }

   609         },

   610         /**

   611          * Given a bound set containing {@code alpha :> S} and {@code alpha == T}

   612          * perform {@code S <: T} (which could lead to new bounds).

   613          */

   614         CROSS_EQ_LOWER() {

   615             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   616                 Infer infer = inferenceContext.infer();

   617                 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {

   618                     for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {

   619                         infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));

   620                     }

   621                 }

   622             }

   623         },

   624         /**

   625          * Given a bound set containing {@code alpha == S} and {@code alpha == T}

   626          * perform {@code S == T} (which could lead to new bounds).

   627          */

   628         CROSS_EQ_EQ() {

   629             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   630                 Infer infer = inferenceContext.infer();

   631                 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {

   632                     for (Type b2 : uv.getBounds(InferenceBound.EQ)) {

   633                         if (b1 != b2) {

   634                             infer.types.isSameType(inferenceContext.asFree(b2), inferenceContext.asFree(b1));

   635                         }

   636                     }

   637                 }

   638             }

   639         },

   640         /**

   641          * Given a bound set containing {@code alpha <: beta} propagate lower bounds

   642          * from alpha to beta; also propagate upper bounds from beta to alpha.

   643          */

   644         PROP_UPPER() {

   645             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   646                 Infer infer = inferenceContext.infer();

   647                 for (Type b : uv.getBounds(InferenceBound.UPPER)) {

   648                     if (inferenceContext.inferenceVars().contains(b)) {

   649                         UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);

   650                         //alpha <: beta

   651                         //0. set beta :> alpha

   652                         uv2.addBound(InferenceBound.LOWER, uv, infer.types);

   653                         //1. copy alpha's lower to beta's

   654                         for (Type l : uv.getBounds(InferenceBound.LOWER)) {

   655                             uv2.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types);

   656                         }

   657                         //2. copy beta's upper to alpha's

   658                         for (Type u : uv2.getBounds(InferenceBound.UPPER)) {

   659                             uv.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types);

   660                         }

   661                     }

   662                 }

   663             }

   664         },

   665         /**

   666          * Given a bound set containing {@code alpha :> beta} propagate lower bounds

   667          * from beta to alpha; also propagate upper bounds from alpha to beta.

   668          */

   669         PROP_LOWER() {

   670             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   671                 Infer infer = inferenceContext.infer();

   672                 for (Type b : uv.getBounds(InferenceBound.LOWER)) {

   673                     if (inferenceContext.inferenceVars().contains(b)) {

   674                         UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);

   675                         //alpha :> beta

   676                         //0. set beta <: alpha

   677                         uv2.addBound(InferenceBound.UPPER, uv, infer.types);

   678                         //1. copy alpha's upper to beta's

   679                         for (Type u : uv.getBounds(InferenceBound.UPPER)) {

   680                             uv2.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types);

   681                         }

   682                         //2. copy beta's lower to alpha's

   683                         for (Type l : uv2.getBounds(InferenceBound.LOWER)) {

   684                             uv.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types);

   685                         }

   686                     }

   687                 }

   688             }

   689         },

   690         /**

   691          * Given a bound set containing {@code alpha == beta} propagate lower/upper

   692          * bounds from alpha to beta and back.

   693          */

   694         PROP_EQ() {

   695             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {

   696                 Infer infer = inferenceContext.infer();

   697                 for (Type b : uv.getBounds(InferenceBound.EQ)) {

   698                     if (inferenceContext.inferenceVars().contains(b)) {

   699                         UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);

   700                         //alpha == beta

   701                         //0. set beta == alpha

   702                         uv2.addBound(InferenceBound.EQ, uv, infer.types);

   703                         //1. copy all alpha's bounds to beta's

   704                         for (InferenceBound ib : InferenceBound.values()) {

   705                             for (Type b2 : uv.getBounds(ib)) {

   706                                 if (b2 != uv2) {

   707                                     uv2.addBound(ib, inferenceContext.asInstType(b2), infer.types);

   708                                 }

   709                             }

   710                         }

   711                         //2. copy all beta's bounds to alpha's

   712                         for (InferenceBound ib : InferenceBound.values()) {

   713                             for (Type b2 : uv2.getBounds(ib)) {

   714                                 if (b2 != uv) {

   715                                     uv.addBound(ib, inferenceContext.asInstType(b2), infer.types);

   716                                 }

   717                             }

   718                         }

   719                     }

   720                 }

   721             }

   722         };

   724         abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn);

   725     }

   727     /** incorporation steps to be executed when running in legacy mode */

   728     EnumSet<IncorporationStep> incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY);

   730     /** incorporation steps to be executed when running in graph mode */

   731     EnumSet<IncorporationStep> incorporationStepsGraph =

   732             EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY));

   734     /**

   735      * Make sure that the upper bounds we got so far lead to a solvable inference

   736      * variable by making sure that a glb exists.

   737      */

   738     void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {

   739         List<Type> hibounds =

   740                 Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));

   741         Type hb = null;

   742         if (hibounds.isEmpty())

   743             hb = syms.objectType;

   744         else if (hibounds.tail.isEmpty())

   745             hb = hibounds.head;

   746         else

   747             hb = types.glb(hibounds);

   748         if (hb == null || hb.isErroneous())

   749             reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   750     }

   751     //where

   752         protected static class BoundFilter implements Filter<Type> {

   754             InferenceContext inferenceContext;

   756             public BoundFilter(InferenceContext inferenceContext) {

   757                 this.inferenceContext = inferenceContext;

   758             }

   760             @Override

   761             public boolean accepts(Type t) {

   762                 return !t.isErroneous() && !inferenceContext.free(t) &&

   763                         !t.hasTag(BOT);

   764             }

   765         };

   767     /**

   768      * This enumeration defines all possible bound-checking related errors.

   769      */

   770     enum BoundErrorKind {

   771         /**

   772          * The (uninstantiated) inference variable has incompatible upper bounds.

   773          */

   774         BAD_UPPER() {

   775             @Override

   776             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

   777                 return ex.setMessage("incompatible.upper.bounds", uv.qtype,

   778                         uv.getBounds(InferenceBound.UPPER));

   779             }

   780         },

   781         /**

   782          * An equality constraint is not compatible with an upper bound.

   783          */

   784         BAD_EQ_UPPER() {

   785             @Override

   786             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

   787                 return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype,

   788                         uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER));

   789             }

   790         },

   791         /**

   792          * An equality constraint is not compatible with a lower bound.

   793          */

   794         BAD_EQ_LOWER() {

   795             @Override

   796             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

   797                 return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype,

   798                         uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER));

   799             }

   800         },

   801         /**

   802          * Instantiated inference variable is not compatible with an upper bound.

   803          */

   804         UPPER() {

   805             @Override

   806             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

   807                 return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst,

   808                         uv.getBounds(InferenceBound.UPPER));

   809             }

   810         },

   811         /**

   812          * Instantiated inference variable is not compatible with a lower bound.

   813          */

   814         LOWER() {

   815             @Override

   816             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

   817                 return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst,

   818                         uv.getBounds(InferenceBound.LOWER));

   819             }

   820         },

   821         /**

   822          * Instantiated inference variable is not compatible with an equality constraint.

   823          */

   824         EQ() {

   825             @Override

   826             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

   827                 return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst,

   828                         uv.getBounds(InferenceBound.EQ));

   829             }

   830         };

   832         abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);

   833     }

   835     /**

   836      * Report a bound-checking error of given kind

   837      */

   838     void reportBoundError(UndetVar uv, BoundErrorKind bk) {

   839         throw bk.setMessage(inferenceException, uv);

   840     }

   841     // </editor-fold>

   843     // <editor-fold defaultstate="collapsed" desc="Inference engine">

   844     /**

   845      * Graph inference strategy - act as an input to the inference solver; a strategy is

   846      * composed of two ingredients: (i) find a node to solve in the inference graph,

   847      * and (ii) tell th engine when we are done fixing inference variables

   848      */

   849     interface GraphStrategy {

   850         /**

   851          * Pick the next node (leaf) to solve in the graph

   852          */

   853         Node pickNode(InferenceGraph g);

   854         /**

   855          * Is this the last step?

   856          */

   857         boolean done();

   858     }

   860     /**

   861      * Simple solver strategy class that locates all leaves inside a graph

   862      * and picks the first leaf as the next node to solve

   863      */

   864     abstract class LeafSolver implements GraphStrategy {

   865         public Node pickNode(InferenceGraph g) {

   866                         Assert.check(!g.nodes.isEmpty(), "No nodes to solve!");

   867             return g.nodes.get(0);

   868         }

   869     }

   871     /**

   872      * This solver uses an heuristic to pick the best leaf - the heuristic

   873      * tries to select the node that has maximal probability to contain one

   874      * or more inference variables in a given list

   875      */

   876     abstract class BestLeafSolver extends LeafSolver {

   878         List<Type> varsToSolve;

   880         BestLeafSolver(List<Type> varsToSolve) {

   881             this.varsToSolve = varsToSolve;

   882         }

   884         /**

   885          * Computes the cost associated with a given node; the cost is computed

   886          * as the total number of type-variables that should be eagerly instantiated

   887          * in order to get to some of the variables in {@code varsToSolve} from

   888          * a given node

   889          */

   890         void computeCostIfNeeded(Node n, Map<Node, Integer> costMap) {

   891             if (costMap.containsKey(n)) {

   892                 return;

   893             } else if (!Collections.disjoint(n.data, varsToSolve)) {

   894                 costMap.put(n, n.data.size());

   895             } else {

   896                 int subcost = Integer.MAX_VALUE;

   897                 costMap.put(n, subcost); //avoid loops

   898                 for (Node n2 : n.getDependencies()) {

   899                     computeCostIfNeeded(n2, costMap);

   900                     subcost = Math.min(costMap.get(n2), subcost);

   901                 }

   902                 //update cost map to reflect real cost

   903                 costMap.put(n, subcost == Integer.MAX_VALUE ?

   904                         Integer.MAX_VALUE :

   905                         n.data.size() + subcost);

   906             }

   907         }

   909         /**

   910          * Pick the leaf that minimize cost

   911          */

   912         @Override

   913         public Node pickNode(final InferenceGraph g) {

   914             final Map<Node, Integer> costMap = new HashMap<Node, Integer>();

   915             ArrayList<Node> leaves = new ArrayList<Node>();

   916             for (Node n : g.nodes) {

   917                 computeCostIfNeeded(n, costMap);

   918                 if (n.isLeaf(n)) {

   919                     leaves.add(n);

   920                 }

   921             }

   922             Assert.check(!leaves.isEmpty(), "No nodes to solve!");

   923             Collections.sort(leaves, new java.util.Comparator<Node>() {

   924                 public int compare(Node n1, Node n2) {

   925                     return costMap.get(n1) - costMap.get(n2);

   926                 }

   927             });

   928             return leaves.get(0);

   929         }

   930     }

   932     /**

   933      * The inference process can be thought of as a sequence of steps. Each step

   934      * instantiates an inference variable using a subset of the inference variable

   935      * bounds, if certain condition are met. Decisions such as the sequence in which

   936      * steps are applied, or which steps are to be applied are left to the inference engine.

   937      */

   938     enum InferenceStep {

   940         /**

   941          * Instantiate an inference variables using one of its (ground) equality

   942          * constraints

   943          */

   944         EQ(InferenceBound.EQ) {

   945             @Override

   946             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   947                 return filterBounds(uv, inferenceContext).head;

   948             }

   949         },

   950         /**

   951          * Instantiate an inference variables using its (ground) lower bounds. Such

   952          * bounds are merged together using lub().

   953          */

   954         LOWER(InferenceBound.LOWER) {

   955             @Override

   956             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   957                 Infer infer = inferenceContext.infer();

   958                 List<Type> lobounds = filterBounds(uv, inferenceContext);

   959                 //note: lobounds should have at least one element

   960                 Type owntype = lobounds.tail.tail == null  ? lobounds.head : infer.types.lub(lobounds);

   961                 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {

   962                     throw infer.inferenceException

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

   964                                     uv.qtype, lobounds);

   965                 } else {

   966                     return owntype;

   967                 }

   968             }

   969         },

   970         /**

   971          * Instantiate an inference variables using its (ground) upper bounds. Such

   972          * bounds are merged together using glb().

   973          */

   974         UPPER(InferenceBound.UPPER) {

   975             @Override

   976             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   977                 Infer infer = inferenceContext.infer();

   978                 List<Type> hibounds = filterBounds(uv, inferenceContext);

   979                 //note: lobounds should have at least one element

   980                 Type owntype = hibounds.tail.tail == null  ? hibounds.head : infer.types.glb(hibounds);

   981                 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {

   982                     throw infer.inferenceException

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

   984                                     uv.qtype, hibounds);

   985                 } else {

   986                     return owntype;

   987                 }

   988             }

   989         },

   990         /**

   991          * Like the former; the only difference is that this step can only be applied

   992          * if all upper bounds are ground.

   993          */

   994         UPPER_LEGACY(InferenceBound.UPPER) {

   995             @Override

   996             public boolean accepts(UndetVar t, InferenceContext inferenceContext) {

   997                 return !inferenceContext.free(t.getBounds(ib));

   998             }

  1000             @Override

  1001             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1002                 return UPPER.solve(uv, inferenceContext);

  1003             }

  1004         };

  1006         final InferenceBound ib;

  1008         InferenceStep(InferenceBound ib) {

  1009             this.ib = ib;

  1010         }

  1012         /**

  1013          * Find an instantiated type for a given inference variable within

  1014          * a given inference context

  1015          */

  1016         abstract Type solve(UndetVar uv, InferenceContext inferenceContext);

  1018         /**

  1019          * Can the inference variable be instantiated using this step?

  1020          */

  1021         public boolean accepts(UndetVar t, InferenceContext inferenceContext) {

  1022             return filterBounds(t, inferenceContext).nonEmpty();

  1023         }

  1025         /**

  1026          * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)

  1027          */

  1028         List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) {

  1029             return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));

  1030         }

  1031     }

  1033     /**

  1034      * This enumeration defines the sequence of steps to be applied when the

  1035      * solver works in legacy mode. The steps in this enumeration reflect

  1036      * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).

  1037      */

  1038     enum LegacyInferenceSteps {

  1040         EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),

  1041         EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));

  1043         final EnumSet<InferenceStep> steps;

  1045         LegacyInferenceSteps(EnumSet<InferenceStep> steps) {

  1046             this.steps = steps;

  1047         }

  1048     }

  1050     /**

  1051      * This enumeration defines the sequence of steps to be applied when the

  1052      * graph solver is used. This order is defined so as to maximize compatibility

  1053      * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).

  1054      */

  1055     enum GraphInferenceSteps {

  1057         EQ(EnumSet.of(InferenceStep.EQ)),

  1058         EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),

  1059         EQ_LOWER_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER));

  1061         final EnumSet<InferenceStep> steps;

  1063         GraphInferenceSteps(EnumSet<InferenceStep> steps) {

  1064             this.steps = steps;

  1065         }

  1066     }

  1068     /**

  1069      * This is the graph inference solver - the solver organizes all inference variables in

  1070      * a given inference context by bound dependencies - in the general case, such dependencies

  1071      * would lead to a cyclic directed graph (hence the name); the dependency info is used to build

  1072      * an acyclic graph, where all cyclic variables are bundled together. An inference

  1073      * step corresponds to solving a node in the acyclic graph - this is done by

  1074      * relying on a given strategy (see GraphStrategy).

  1075      */

  1076     class GraphSolver {

  1078         InferenceContext inferenceContext;

  1079         Warner warn;

  1081         GraphSolver(InferenceContext inferenceContext, Warner warn) {

  1082             this.inferenceContext = inferenceContext;

  1083             this.warn = warn;

  1084         }

  1086         /**

  1087          * Solve variables in a given inference context. The amount of variables

  1088          * to be solved, and the way in which the underlying acyclic graph is explored

  1089          * depends on the selected solver strategy.

  1090          */

  1091         void solve(GraphStrategy sstrategy) {

  1092             checkWithinBounds(inferenceContext, warn); //initial propagation of bounds

  1093             InferenceGraph inferenceGraph = new InferenceGraph();

  1094             while (!sstrategy.done()) {

  1095                 InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);

  1096                 List<Type> varsToSolve = List.from(nodeToSolve.data);

  1097                 List<Type> saved_undet = inferenceContext.save();

  1098                 try {

  1099                     //repeat until all variables are solved

  1100                     outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {

  1101                         //for each inference phase

  1102                         for (GraphInferenceSteps step : GraphInferenceSteps.values()) {

  1103                             if (inferenceContext.solveBasic(varsToSolve, step.steps)) {

  1104                                 checkWithinBounds(inferenceContext, warn);

  1105                                 continue outer;

  1106                             }

  1107                         }

  1108                         //no progress

  1109                         throw inferenceException.setMessage();

  1110                     }

  1111                 }

  1112                 catch (InferenceException ex) {

  1113                     //did we fail because of interdependent ivars?

  1114                     inferenceContext.rollback(saved_undet);

  1115                     instantiateAsUninferredVars(varsToSolve, inferenceContext);

  1116                     checkWithinBounds(inferenceContext, warn);

  1117                 }

  1118                 inferenceGraph.deleteNode(nodeToSolve);

  1119             }

  1120         }

  1122         /**

  1123          * The dependencies between the inference variables that need to be solved

  1124          * form a (possibly cyclic) graph. This class reduces the original dependency graph

  1125          * to an acyclic version, where cyclic nodes are folded into a single 'super node'.

  1126          */

  1127         class InferenceGraph {

  1129             /**

  1130              * This class represents a node in the graph. Each node corresponds

  1131              * to an inference variable and has edges (dependencies) on other

  1132              * nodes. The node defines an entry point that can be used to receive

  1133              * updates on the structure of the graph this node belongs to (used to

  1134              * keep dependencies in sync).

  1135              */

  1136             class Node extends GraphUtils.TarjanNode<ListBuffer<Type>> {

  1138                 Set<Node> deps;

  1140                 Node(Type ivar) {

  1141                     super(ListBuffer.of(ivar));

  1142                     this.deps = new HashSet<Node>();

  1143                 }

  1145                 @Override

  1146                 public Iterable<? extends Node> getDependencies() {

  1147                     return deps;

  1148                 }

  1150                 @Override

  1151                 public String printDependency(GraphUtils.Node<ListBuffer<Type>> to) {

  1152                     StringBuilder buf = new StringBuilder();

  1153                     String sep = "";

  1154                     for (Type from : data) {

  1155                         UndetVar uv = (UndetVar)inferenceContext.asFree(from);

  1156                         for (Type bound : uv.getBounds(InferenceBound.values())) {

  1157                             if (bound.containsAny(List.from(to.data))) {

  1158                                 buf.append(sep);

  1159                                 buf.append(bound);

  1160                                 sep = ",";

  1161                             }

  1162                         }

  1163                     }

  1164                     return buf.toString();

  1165                 }

  1167                 boolean isLeaf(Node n) {

  1168                     //no deps, or only one self dep

  1169                     return (n.deps.isEmpty() ||

  1170                             n.deps.size() == 1 && n.deps.contains(n));

  1171                 }

  1173                 void mergeWith(List<? extends Node> nodes) {

  1174                     for (Node n : nodes) {

  1175                         Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");

  1176                         data.appendList(n.data);

  1177                         deps.addAll(n.deps);

  1178                     }

  1179                     //update deps

  1180                     Set<Node> deps2 = new HashSet<Node>();

  1181                     for (Node d : deps) {

  1182                         if (data.contains(d.data.first())) {

  1183                             deps2.add(this);

  1184                         } else {

  1185                             deps2.add(d);

  1186                         }

  1187                     }

  1188                     deps = deps2;

  1189                 }

  1191                 void graphChanged(Node from, Node to) {

  1192                     if (deps.contains(from)) {

  1193                         deps.remove(from);

  1194                         if (to != null) {

  1195                             deps.add(to);

  1196                         }

  1197                     }

  1198                 }

  1199             }

  1201             /** the nodes in the inference graph */

  1202             ArrayList<Node> nodes;

  1204             InferenceGraph() {

  1205                 initNodes();

  1206             }

  1208             /**

  1209              * Delete a node from the graph. This update the underlying structure

  1210              * of the graph (including dependencies) via listeners updates.

  1211              */

  1212             public void deleteNode(Node n) {

  1213                 Assert.check(nodes.contains(n));

  1214                 nodes.remove(n);

  1215                 notifyUpdate(n, null);

  1216             }

  1218             /**

  1219              * Notify all nodes of a change in the graph. If the target node is

  1220              * {@code null} the source node is assumed to be removed.

  1221              */

  1222             void notifyUpdate(Node from, Node to) {

  1223                 for (Node n : nodes) {

  1224                     n.graphChanged(from, to);

  1225                 }

  1226             }

  1228             /**

  1229              * Create the graph nodes. First a simple node is created for every inference

  1230              * variables to be solved. Then Tarjan is used to found all connected components

  1231              * in the graph. For each component containing more than one node, a super node is

  1232                  * created, effectively replacing the original cyclic nodes.

  1233              */

  1234             void initNodes() {

  1235                 nodes = new ArrayList<Node>();

  1236                 for (Type t : inferenceContext.restvars()) {

  1237                     nodes.add(new Node(t));

  1238                 }

  1239                 for (Node n_i : nodes) {

  1240                     Type i = n_i.data.first();

  1241                     for (Node n_j : nodes) {

  1242                         Type j = n_j.data.first();

  1243                         UndetVar uv_i = (UndetVar)inferenceContext.asFree(i);

  1244                         if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {

  1245                             //update i's deps

  1246                             n_i.deps.add(n_j);

  1247                         }

  1248                     }

  1249                 }

  1250                 ArrayList<Node> acyclicNodes = new ArrayList<Node>();

  1251                 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {

  1252                     if (conSubGraph.length() > 1) {

  1253                         Node root = conSubGraph.head;

  1254                         root.mergeWith(conSubGraph.tail);

  1255                         for (Node n : conSubGraph) {

  1256                             notifyUpdate(n, root);

  1257                         }

  1258                     }

  1259                     acyclicNodes.add(conSubGraph.head);

  1260                 }

  1261                 nodes = acyclicNodes;

  1262             }

  1264             /**

  1265              * Debugging: dot representation of this graph

  1266              */

  1267             String toDot() {

  1268                 StringBuilder buf = new StringBuilder();

  1269                 for (Type t : inferenceContext.undetvars) {

  1270                     UndetVar uv = (UndetVar)t;

  1271                     buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",

  1272                             uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),

  1273                             uv.getBounds(InferenceBound.EQ)));

  1274                 }

  1275                 return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());

  1276             }

  1277         }

  1278     }

  1279     // </editor-fold>

  1281     // <editor-fold defaultstate="collapsed" desc="Inference context">

  1282     /**

  1283      * Functional interface for defining inference callbacks. Certain actions

  1284      * (i.e. subtyping checks) might need to be redone after all inference variables

  1285      * have been fixed.

  1286      */

  1287     interface FreeTypeListener {

  1288         void typesInferred(InferenceContext inferenceContext);

  1289     }

  1291     /**

  1292      * An inference context keeps track of the set of variables that are free

  1293      * in the current context. It provides utility methods for opening/closing

  1294      * types to their corresponding free/closed forms. It also provide hooks for

  1295      * attaching deferred post-inference action (see PendingCheck). Finally,

  1296      * it can be used as an entry point for performing upper/lower bound inference

  1297      * (see InferenceKind).

  1298      */

  1299      class InferenceContext {

  1301         /** list of inference vars as undet vars */

  1302         List<Type> undetvars;

  1304         /** list of inference vars in this context */

  1305         List<Type> inferencevars;

  1307         /** backed up inference variables */

  1308         List<Type> saved_undet;

  1310         java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners =

  1311                 new java.util.HashMap<FreeTypeListener, List<Type>>();

  1313         List<FreeTypeListener> freetypeListeners = List.nil();

  1315         public InferenceContext(List<Type> inferencevars) {

  1316             this.undetvars = Type.map(inferencevars, fromTypeVarFun);

  1317             this.inferencevars = inferencevars;

  1318         }

  1319         //where

  1320             Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") {

  1321                 // mapping that turns inference variables into undet vars

  1322                 public Type apply(Type t) {

  1323                     if (t.hasTag(TYPEVAR)) return new UndetVar((TypeVar)t, types);

  1324                     else return t.map(this);

  1325                 }

  1326             };

  1328         /**

  1329          * returns the list of free variables (as type-variables) in this

  1330          * inference context

  1331          */

  1332         List<Type> inferenceVars() {

  1333             return inferencevars;

  1334         }

  1336         /**

  1337          * returns the list of uninstantiated variables (as type-variables) in this

  1338          * inference context

  1339          */

  1340         List<Type> restvars() {

  1341             return filterVars(new Filter<UndetVar>() {

  1342                 public boolean accepts(UndetVar uv) {

  1343                     return uv.inst == null;

  1344                 }

  1345             });

  1346         }

  1348         /**

  1349          * returns the list of instantiated variables (as type-variables) in this

  1350          * inference context

  1351          */

  1352         List<Type> instvars() {

  1353             return filterVars(new Filter<UndetVar>() {

  1354                 public boolean accepts(UndetVar uv) {

  1355                     return uv.inst != null;

  1356                 }

  1357             });

  1358         }

  1360         /**

  1361          * Get list of bounded inference variables (where bound is other than

  1362          * declared bounds).

  1363          */

  1364         final List<Type> boundedVars() {

  1365             return filterVars(new Filter<UndetVar>() {

  1366                 public boolean accepts(UndetVar uv) {

  1367                     return uv.getBounds(InferenceBound.UPPER)

  1368                             .diff(uv.getDeclaredBounds())

  1369                             .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty();

  1370                 }

  1371             });

  1372         }

  1374         private List<Type> filterVars(Filter<UndetVar> fu) {

  1375             ListBuffer<Type> res = ListBuffer.lb();

  1376             for (Type t : undetvars) {

  1377                 UndetVar uv = (UndetVar)t;

  1378                 if (fu.accepts(uv)) {

  1379                     res.append(uv.qtype);

  1380                 }

  1381             }

  1382             return res.toList();

  1383         }

  1385         /**

  1386          * is this type free?

  1387          */

  1388         final boolean free(Type t) {

  1389             return t.containsAny(inferencevars);

  1390         }

  1392         final boolean free(List<Type> ts) {

  1393             for (Type t : ts) {

  1394                 if (free(t)) return true;

  1395             }

  1396             return false;

  1397         }

  1399         /**

  1400          * Returns a list of free variables in a given type

  1401          */

  1402         final List<Type> freeVarsIn(Type t) {

  1403             ListBuffer<Type> buf = ListBuffer.lb();

  1404             for (Type iv : inferenceVars()) {

  1405                 if (t.contains(iv)) {

  1406                     buf.add(iv);

  1407                 }

  1408             }

  1409             return buf.toList();

  1410         }

  1412         final List<Type> freeVarsIn(List<Type> ts) {

  1413             ListBuffer<Type> buf = ListBuffer.lb();

  1414             for (Type t : ts) {

  1415                 buf.appendList(freeVarsIn(t));

  1416             }

  1417             ListBuffer<Type> buf2 = ListBuffer.lb();

  1418             for (Type t : buf) {

  1419                 if (!buf2.contains(t)) {

  1420                     buf2.add(t);

  1421                 }

  1422             }

  1423             return buf2.toList();

  1424         }

  1426         /**

  1427          * Replace all free variables in a given type with corresponding

  1428          * undet vars (used ahead of subtyping/compatibility checks to allow propagation

  1429          * of inference constraints).

  1430          */

  1431         final Type asFree(Type t) {

  1432             return types.subst(t, inferencevars, undetvars);

  1433         }

  1435         final List<Type> asFree(List<Type> ts) {

  1436             ListBuffer<Type> buf = ListBuffer.lb();

  1437             for (Type t : ts) {

  1438                 buf.append(asFree(t));

  1439             }

  1440             return buf.toList();

  1441         }

  1443         List<Type> instTypes() {

  1444             ListBuffer<Type> buf = ListBuffer.lb();

  1445             for (Type t : undetvars) {

  1446                 UndetVar uv = (UndetVar)t;

  1447                 buf.append(uv.inst != null ? uv.inst : uv.qtype);

  1448             }

  1449             return buf.toList();

  1450         }

  1452         /**

  1453          * Replace all free variables in a given type with corresponding

  1454          * instantiated types - if one or more free variable has not been

  1455          * fully instantiated, it will still be available in the resulting type.

  1456          */

  1457         Type asInstType(Type t) {

  1458             return types.subst(t, inferencevars, instTypes());

  1459         }

  1461         List<Type> asInstTypes(List<Type> ts) {

  1462             ListBuffer<Type> buf = ListBuffer.lb();

  1463             for (Type t : ts) {

  1464                 buf.append(asInstType(t));

  1465             }

  1466             return buf.toList();

  1467         }

  1469         /**

  1470          * Add custom hook for performing post-inference action

  1471          */

  1472         void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {

  1473             freeTypeListeners.put(ftl, freeVarsIn(types));

  1474         }

  1476         /**

  1477          * Mark the inference context as complete and trigger evaluation

  1478          * of all deferred checks.

  1479          */

  1480         void notifyChange() {

  1481             notifyChange(inferencevars.diff(restvars()));

  1482         }

  1484         void notifyChange(List<Type> inferredVars) {

  1485             InferenceException thrownEx = null;

  1486             for (Map.Entry<FreeTypeListener, List<Type>> entry :

  1487                     new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) {

  1488                 if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {

  1489                     try {

  1490                         entry.getKey().typesInferred(this);

  1491                         freeTypeListeners.remove(entry.getKey());

  1492                     } catch (InferenceException ex) {

  1493                         if (thrownEx == null) {

  1494                             thrownEx = ex;

  1495                         }

  1496                     }

  1497                 }

  1498             }

  1499             //inference exception multiplexing - present any inference exception

  1500             //thrown when processing listeners as a single one

  1501             if (thrownEx != null) {

  1502                 throw thrownEx;

  1503             }

  1504         }

  1506         /**

  1507          * Save the state of this inference context

  1508          */

  1509         List<Type> save() {

  1510             ListBuffer<Type> buf = ListBuffer.lb();

  1511             for (Type t : undetvars) {

  1512                 UndetVar uv = (UndetVar)t;

  1513                 UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types);

  1514                 for (InferenceBound ib : InferenceBound.values()) {

  1515                     for (Type b : uv.getBounds(ib)) {

  1516                         uv2.addBound(ib, b, types);

  1517                     }

  1518                 }

  1519                 uv2.inst = uv.inst;

  1520                 buf.add(uv2);

  1521             }

  1522             return buf.toList();

  1523         }

  1525         /**

  1526          * Restore the state of this inference context to the previous known checkpoint

  1527          */

  1528         void rollback(List<Type> saved_undet) {

  1529              Assert.check(saved_undet != null && saved_undet.length() == undetvars.length());

  1530             //restore bounds (note: we need to preserve the old instances)

  1531             for (Type t : undetvars) {

  1532                 UndetVar uv = (UndetVar)t;

  1533                 UndetVar uv_saved = (UndetVar)saved_undet.head;

  1534                 for (InferenceBound ib : InferenceBound.values()) {

  1535                     uv.setBounds(ib, uv_saved.getBounds(ib));

  1536                 }

  1537                 uv.inst = uv_saved.inst;

  1538                 saved_undet = saved_undet.tail;

  1539             }

  1540         }

  1542         /**

  1543          * Copy variable in this inference context to the given context

  1544          */

  1545         void dupTo(final InferenceContext that) {

  1546             that.inferencevars = that.inferencevars.appendList(inferencevars);

  1547             that.undetvars = that.undetvars.appendList(undetvars);

  1548             //set up listeners to notify original inference contexts as

  1549             //propagated vars are inferred in new context

  1550             for (Type t : inferencevars) {

  1551                 that.freeTypeListeners.put(new FreeTypeListener() {

  1552                     public void typesInferred(InferenceContext inferenceContext) {

  1553                         InferenceContext.this.notifyChange();

  1554                     }

  1555                 }, List.of(t));

  1556             }

  1557         }

  1559         /**

  1560          * Solve with given graph strategy.

  1561          */

  1562         private void solve(GraphStrategy ss, Warner warn) {

  1563             GraphSolver s = new GraphSolver(this, warn);

  1564             s.solve(ss);

  1565         }

  1567         /**

  1568          * Solve all variables in this context.

  1569          */

  1570         public void solve(Warner warn) {

  1571             solve(new LeafSolver() {

  1572                 public boolean done() {

  1573                     return restvars().isEmpty();

  1574                 }

  1575             }, warn);

  1576         }

  1578         /**

  1579          * Solve all variables in the given list.

  1580          */

  1581         public void solve(final List<Type> vars, Warner warn) {

  1582             solve(new BestLeafSolver(vars) {

  1583                 public boolean done() {

  1584                     return !free(asInstTypes(vars));

  1585                 }

  1586             }, warn);

  1587         }

  1589         /**

  1590          * Solve at least one variable in given list.

  1591          */

  1592         public void solveAny(List<Type> varsToSolve, Warner warn) {

  1593             checkWithinBounds(this, warn); //propagate bounds

  1594             List<Type> boundedVars = boundedVars().intersect(restvars()).intersect(varsToSolve);

  1595             if (boundedVars.isEmpty()) {

  1596                 throw inferenceException.setMessage("cyclic.inference",

  1597                                 freeVarsIn(varsToSolve));

  1598             }

  1599             solve(new BestLeafSolver(boundedVars) {

  1600                 public boolean done() {

  1601                     return instvars().intersect(varsToSolve).nonEmpty();

  1602                 }

  1603             }, warn);

  1604         }

  1606         /**

  1607          * Apply a set of inference steps

  1608          */

  1609         private boolean solveBasic(EnumSet<InferenceStep> steps) {

  1610             return solveBasic(inferencevars, steps);

  1611         }

  1613         private boolean solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) {

  1614             boolean changed = false;

  1615             for (Type t : varsToSolve.intersect(restvars())) {

  1616                 UndetVar uv = (UndetVar)asFree(t);

  1617                 for (InferenceStep step : steps) {

  1618                     if (step.accepts(uv, this)) {

  1619                         uv.inst = step.solve(uv, this);

  1620                         changed = true;

  1621                         break;

  1622                     }

  1623                 }

  1624             }

  1625             return changed;

  1626         }

  1628         /**

  1629          * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).

  1630          * During overload resolution, instantiation is done by doing a partial

  1631          * inference process using eq/lower bound instantiation. During check,

  1632          * we also instantiate any remaining vars by repeatedly using eq/upper

  1633          * instantiation, until all variables are solved.

  1634          */

  1635         public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) {

  1636             while (true) {

  1637                 boolean stuck = !solveBasic(steps);

  1638                 if (restvars().isEmpty() || partial) {

  1639                     //all variables have been instantiated - exit

  1640                     break;

  1641                 } else if (stuck) {

  1642                     //some variables could not be instantiated because of cycles in

  1643                     //upper bounds - provide a (possibly recursive) default instantiation

  1644                     instantiateAsUninferredVars(restvars(), this);

  1645                     break;

  1646                 } else {

  1647                     //some variables have been instantiated - replace newly instantiated

  1648                     //variables in remaining upper bounds and continue

  1649                     for (Type t : undetvars) {

  1650                         UndetVar uv = (UndetVar)t;

  1651                         uv.substBounds(inferenceVars(), instTypes(), types);

  1652                     }

  1653                 }

  1654             }

  1655             checkWithinBounds(this, warn);

  1656         }

  1658         private Infer infer() {

  1659             //back-door to infer

  1660             return Infer.this;

  1661         }

  1662     }

  1664     final InferenceContext emptyContext = new InferenceContext(List.<Type>nil());

  1665     // </editor-fold>

  1666 }

Mercurial > jdk8-mips64-public > langtools / file revision

src/share/classes/com/sun/tools/javac/comp/Infer.java@37031963493e

src/share/classes/com/sun/tools/javac/comp/Infer.java