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

8009545: Graph inference: dependencies between inference variables should be set during incorporation
Summary: Move all transitivity checks into the incorporation round
Reviewed-by: jjg

     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 Type(NONE, null);

   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                                   Resolve.MethodCheck methodCheck,

   147                                   Warner warn) throws InferenceException {

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

   149         final InferenceContext inferenceContext = new InferenceContext(tvars);

   150         inferenceException.clear();

   151         try {

   152             DeferredAttr.DeferredAttrContext deferredAttrContext =

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

   155             methodCheck.argumentsAcceptable(env, deferredAttrContext,

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

   158             if (allowGraphInference &&

   159                     resultInfo != null &&

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

   161                 //inject return constraints earlier

   162                 checkWithinBounds(inferenceContext, warn); //propagation

   163                 generateReturnConstraints(resultInfo, mt, inferenceContext);

   164                 //propagate outwards if needed

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

   166                     //propagate inference context outwards and exit

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

   168                     deferredAttrContext.complete();

   169                     return mt;

   170                 }

   171             }

   173             deferredAttrContext.complete();

   175             // minimize as yet undetermined type variables

   176             if (allowGraphInference) {

   177                 inferenceContext.solve(warn);

   178             } else {

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

   180             }

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

   184             if (!allowGraphInference &&

   185                     inferenceContext.restvars().nonEmpty() &&

   186                     resultInfo != null &&

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

   188                 generateReturnConstraints(resultInfo, mt, inferenceContext);

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

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

   191             }

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

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

   195             }

   197             // return instantiated version of method type

   198             return mt;

   199         } finally {

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

   201                 inferenceContext.notifyChange();

   202             } else {

   203                 inferenceContext.notifyChange(inferenceContext.boundedVars());

   204             }

   205         }

   206     }

   208     /**

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

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

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

   212      */

   213     void generateReturnConstraints(Attr.ResultInfo resultInfo,

   214             MethodType mt, InferenceContext inferenceContext) {

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

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

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

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

   219         //we need to skip capture?

   220         Warner retWarn = new Warner();

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

   222                 //unchecked conversion is not allowed

   223                 retWarn.hasLint(Lint.LintCategory.UNCHECKED)) {

   224             throw inferenceException

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

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

   227         }

   228     }

   229     //where

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

   231             if (from.hasTag(VOID)) {

   232                 return syms.voidType;

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

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

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

   236                 if (!allowGraphInference) {

   237                     //if legacy, just return boxed type

   238                     return types.boxedClass(to).type;

   239                 }

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

   241                 UndetVar uv = (UndetVar)from;

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

   243                     Type boundAsPrimitive = types.unboxedType(t);

   244                     if (boundAsPrimitive == null) continue;

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

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

   247                         return syms.objectType;

   248                     }

   249                 }

   250                 return types.boxedClass(to).type;

   251             } else {

   252                 return to;

   253             }

   254         }

   256     /**

   257       * Infer cyclic inference variables as described in 15.12.2.8.

   258       */

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

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

   261         //step 1 - create fresh tvars

   262         for (Type t : vars) {

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

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

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

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

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

   268                 todo.append(uv);

   269                 uv.inst = fresh_tvar.type;

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

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

   272             } else {

   273                 uv.inst = syms.objectType;

   274             }

   275         }

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

   277         List<Type> formals = vars;

   278         for (Type t : todo) {

   279             UndetVar uv = (UndetVar)t;

   280             TypeVar ct = (TypeVar)uv.inst;

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

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

   283                 //report inference error if glb fails

   284                 reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   285             }

   286             formals = formals.tail;

   287         }

   288     }

   290     /**

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

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

   293      * enclosing scope surrounding the polymorphic-signature call.

   294      */

   295     Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,

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

   297                                             Resolve.MethodResolutionContext resolveContext,

   298                                             List<Type> argtypes) {

   299         final Type restype;

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

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

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

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

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

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

   307         //the polymorphic signature call environment is nested.

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

   310             case TYPECAST:

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

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

   313                     castTree.clazz.type :

   314                     syms.objectType;

   315                 break;

   316             case EXEC:

   317                 JCTree.JCExpressionStatement execTree =

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

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

   320                     syms.voidType :

   321                     syms.objectType;

   322                 break;

   323             default:

   324                 restype = syms.objectType;

   325         }

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

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

   329             spMethod.getThrownTypes() :

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

   332         MethodType mtype = new MethodType(paramtypes,

   333                                           restype,

   334                                           exType,

   335                                           syms.methodClass);

   336         return mtype;

   337     }

   338     //where

   339         class ImplicitArgType extends DeferredAttr.DeferredTypeMap {

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

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

   343             }

   345             public Type apply(Type t) {

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

   347                 if (t.hasTag(BOT))

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

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

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

   351                 return t;

   352             }

   353         }

   355     /**

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

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

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

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

   360       */

   361     public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,

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

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

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

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

   366             return funcInterface;

   367         } else {

   368             Type formalInterface = funcInterface.tsym.type;

   369             InferenceContext funcInterfaceContext =

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

   372             Assert.check(paramTypes != null);

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

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

   375             //in the functional interface descriptors)

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

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

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

   379                 return types.createErrorType(funcInterface);

   380             }

   381             for (Type p : descParameterTypes) {

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

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

   384                     return types.createErrorType(funcInterface);

   385                 }

   386                 paramTypes = paramTypes.tail;

   387             }

   389             try {

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

   391             } catch (InferenceException ex) {

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

   393             }

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

   396             for (Type t : funcInterfaceContext.undetvars) {

   397                 UndetVar uv = (UndetVar)t;

   398                 if (uv.inst == null) {

   399                     uv.inst = actualTypeargs.head;

   400                 }

   401                 actualTypeargs = actualTypeargs.tail;

   402             }

   404             Type owntype = funcInterfaceContext.asInstType(formalInterface);

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

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

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

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

   409             }

   410             return owntype;

   411         }

   412     }

   413     // </editor-fold>

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

   416     /**

   417      * Check bounds and perform incorporation

   418      */

   419     void checkWithinBounds(InferenceContext inferenceContext,

   420                              Warner warn) throws InferenceException {

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

   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         }

   448     }

   449     //where

   450         /**

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

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

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

   454          * left in a clean state.

   455          */

   456         class MultiUndetVarListener implements UndetVar.UndetVarListener {

   458             int rounds;

   459             boolean changed;

   460             List<Type> undetvars;

   462             public MultiUndetVarListener(List<Type> undetvars) {

   463                 this.undetvars = undetvars;

   464                 for (Type t : undetvars) {

   465                     UndetVar uv = (UndetVar)t;

   466                     uv.listener = this;

   467                 }

   468             }

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

   471                 //avoid non-termination

   472                 if (rounds < MAX_INCORPORATION_STEPS) {

   473                     changed = true;

   474                 }

   475             }

   477             void reset() {

   478                 rounds++;

   479                 changed = false;

   480             }

   482             void detach() {

   483                 for (Type t : undetvars) {

   484                     UndetVar uv = (UndetVar)t;

   485                     uv.listener = null;

   486                 }

   487             }

   488         };

   490         /** max number of incorporation rounds */

   491         static final int MAX_INCORPORATION_STEPS = 100;

   493     /**

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

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

   496      * logic into the basic bound checking routine

   497      */

   498     enum IncorporationStep {

   499         /**

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

   501          * inference variable compatible with its bounds?

   502          */

   503         CHECK_BOUNDS() {

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

   505                 Infer infer = inferenceContext.infer();

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

   507                 infer.checkCompatibleUpperBounds(uv, inferenceContext);

   508                 if (uv.inst != null) {

   509                     Type inst = uv.inst;

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

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

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

   513                         }

   514                     }

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

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

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

   518                         }

   519                     }

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

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

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

   523                         }

   524                     }

   525                 }

   526             }

   527         },

   528         /**

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

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

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

   532          */

   533         EQ_CHECK_LEGACY() {

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

   535                 Infer infer = inferenceContext.infer();

   536                 Type eq = null;

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

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

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

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

   541                     }

   542                     eq = e;

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

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

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

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

   547                         }

   548                     }

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

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

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

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

   553                         }

   554                     }

   555                 }

   556             }

   557         },

   558         /**

   559          * Check consistency of equality constraints.

   560          */

   561         EQ_CHECK() {

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

   563                 Infer infer = inferenceContext.infer();

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

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

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

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

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

   569                         }

   570                     }

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

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

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

   574                         }

   575                     }

   576                 }

   577             }

   578         },

   579         /**

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

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

   582          */

   583         CROSS_UPPER_LOWER() {

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

   585                 Infer infer = inferenceContext.infer();

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

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

   588                         if (!inferenceContext.inferenceVars().contains(b1) &&

   589                                 !inferenceContext.inferenceVars().contains(b2) &&

   590                                 infer.types.asSuper(b2, b1.tsym) != null) {

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

   592                         }

   593                     }

   594                 }

   595             }

   596         },

   597         /**

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

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

   600          */

   601         CROSS_UPPER_EQ() {

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

   603                 Infer infer = inferenceContext.infer();

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

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

   606                         if (!inferenceContext.inferenceVars().contains(b1) &&

   607                                 !inferenceContext.inferenceVars().contains(b2) &&

   608                                 infer.types.asSuper(b2, b1.tsym) != null) {

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

   610                         }

   611                     }

   612                 }

   613             }

   614         },

   615         /**

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

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

   618          */

   619         CROSS_EQ_LOWER() {

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

   621                 Infer infer = inferenceContext.infer();

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

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

   624                         if (!inferenceContext.inferenceVars().contains(b1) &&

   625                                 !inferenceContext.inferenceVars().contains(b2) &&

   626                                 infer.types.asSuper(b2, b1.tsym) != null) {

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

   628                         }

   629                     }

   630                 }

   631             }

   632         },

   633         /**

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

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

   636          */

   637         PROP_UPPER() {

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

   639                 Infer infer = inferenceContext.infer();

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

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

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

   643                         //alpha <: beta

   644                         //0. set beta :> alpha

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

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

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

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

   649                         }

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

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

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

   653                         }

   654                     }

   655                 }

   656             }

   657         },

   658         /**

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

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

   661          */

   662         PROP_LOWER() {

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

   664                 Infer infer = inferenceContext.infer();

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

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

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

   668                         //alpha :> beta

   669                         //0. set beta <: alpha

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

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

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

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

   674                         }

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

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

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

   678                         }

   679                     }

   680                 }

   681             }

   682         },

   683         /**

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

   685          * bounds from alpha to beta and back.

   686          */

   687         PROP_EQ() {

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

   689                 Infer infer = inferenceContext.infer();

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

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

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

   693                         //alpha == beta

   694                         //0. set beta == alpha

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

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

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

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

   699                                 if (b2 != uv2) {

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

   701                                 }

   702                             }

   703                         }

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

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

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

   707                                 if (b2 != uv) {

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

   709                                 }

   710                             }

   711                         }

   712                     }

   713                 }

   714             }

   715         };

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

   718     }

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

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

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

   724     EnumSet<IncorporationStep> incorporationStepsGraph =

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

   727     /**

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

   729      * variable by making sure that a glb exists.

   730      */

   731     void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {

   732         List<Type> hibounds =

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

   734         Type hb = null;

   735         if (hibounds.isEmpty())

   736             hb = syms.objectType;

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

   738             hb = hibounds.head;

   739         else

   740             hb = types.glb(hibounds);

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

   742             reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   743     }

   744     //where

   745         protected static class BoundFilter implements Filter<Type> {

   747             InferenceContext inferenceContext;

   749             public BoundFilter(InferenceContext inferenceContext) {

   750                 this.inferenceContext = inferenceContext;

   751             }

   753             @Override

   754             public boolean accepts(Type t) {

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

   756                         !t.hasTag(BOT);

   757             }

   758         };

   760     /**

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

   762      */

   763     enum BoundErrorKind {

   764         /**

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

   766          */

   767         BAD_UPPER() {

   768             @Override

   769             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   771                         uv.getBounds(InferenceBound.UPPER));

   772             }

   773         },

   774         /**

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

   776          */

   777         BAD_EQ_UPPER() {

   778             @Override

   779             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   782             }

   783         },

   784         /**

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

   786          */

   787         BAD_EQ_LOWER() {

   788             @Override

   789             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   792             }

   793         },

   794         /**

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

   796          */

   797         UPPER() {

   798             @Override

   799             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   801                         uv.getBounds(InferenceBound.UPPER));

   802             }

   803         },

   804         /**

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

   806          */

   807         LOWER() {

   808             @Override

   809             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   811                         uv.getBounds(InferenceBound.LOWER));

   812             }

   813         },

   814         /**

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

   816          */

   817         EQ() {

   818             @Override

   819             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   821                         uv.getBounds(InferenceBound.EQ));

   822             }

   823         };

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

   826     }

   828     /**

   829      * Report a bound-checking error of given kind

   830      */

   831     void reportBoundError(UndetVar uv, BoundErrorKind bk) {

   832         throw bk.setMessage(inferenceException, uv);

   833     }

   834     // </editor-fold>

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

   837     /**

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

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

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

   841      */

   842     interface GraphStrategy {

   843         /**

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

   845          */

   846         Node pickNode(InferenceGraph g);

   847         /**

   848          * Is this the last step?

   849          */

   850         boolean done();

   851     }

   853     /**

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

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

   856      */

   857     abstract class LeafSolver implements GraphStrategy {

   858         public Node pickNode(InferenceGraph g) {

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

   860             return g.nodes.get(0);

   861         }

   862     }

   864     /**

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

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

   867      * or more inference variables in a given list

   868      */

   869     abstract class BestLeafSolver extends LeafSolver {

   871         List<Type> varsToSolve;

   873         BestLeafSolver(List<Type> varsToSolve) {

   874             this.varsToSolve = varsToSolve;

   875         }

   877         /**

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

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

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

   881          * a given node

   882          */

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

   884             if (costMap.containsKey(n)) {

   885                 return;

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

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

   888             } else {

   889                 int subcost = Integer.MAX_VALUE;

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

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

   892                     computeCostIfNeeded(n2, costMap);

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

   894                 }

   895                 //update cost map to reflect real cost

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

   897                         Integer.MAX_VALUE :

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

   899             }

   900         }

   902         /**

   903          * Pick the leaf that minimize cost

   904          */

   905         @Override

   906         public Node pickNode(final InferenceGraph g) {

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

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

   909             for (Node n : g.nodes) {

   910                 computeCostIfNeeded(n, costMap);

   911                 if (n.isLeaf(n)) {

   912                     leaves.add(n);

   913                 }

   914             }

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

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

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

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

   919                 }

   920             });

   921             return leaves.get(0);

   922         }

   923     }

   925     /**

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

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

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

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

   930      */

   931     enum InferenceStep {

   933         /**

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

   935          * constraints

   936          */

   937         EQ(InferenceBound.EQ) {

   938             @Override

   939             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   940                 return filterBounds(uv, inferenceContext).head;

   941             }

   942         },

   943         /**

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

   945          * bounds are merged together using lub().

   946          */

   947         LOWER(InferenceBound.LOWER) {

   948             @Override

   949             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   950                 Infer infer = inferenceContext.infer();

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

   952                 Type owntype = infer.types.lub(lobounds);

   953                 if (owntype.hasTag(ERROR)) {

   954                     throw infer.inferenceException

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

   956                                     uv.qtype, lobounds);

   957                 } else {

   958                     return owntype;

   959                 }

   960             }

   961         },

   962         /**

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

   964          * bounds are merged together using glb().

   965          */

   966         UPPER(InferenceBound.UPPER) {

   967             @Override

   968             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   969                 Infer infer = inferenceContext.infer();

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

   971                 Type owntype = infer.types.glb(hibounds);

   972                 if (owntype.isErroneous()) {

   973                     throw infer.inferenceException

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

   975                                     uv.qtype, hibounds);

   976                 } else {

   977                     return owntype;

   978                 }

   979             }

   980         },

   981         /**

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

   983          * if all upper bounds are ground.

   984          */

   985         UPPER_LEGACY(InferenceBound.UPPER) {

   986             @Override

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

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

   989             }

   991             @Override

   992             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   993                 return UPPER.solve(uv, inferenceContext);

   994             }

   995         };

   997         final InferenceBound ib;

   999         InferenceStep(InferenceBound ib) {

  1000             this.ib = ib;

  1001         }

  1003         /**

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

  1005          * a given inference context

  1006          */

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

  1009         /**

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

  1011          */

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

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

  1014         }

  1016         /**

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

  1018          */

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

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

  1021         }

  1022     }

  1024     /**

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

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

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

  1028      */

  1029     enum LegacyInferenceSteps {

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

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

  1034         final EnumSet<InferenceStep> steps;

  1036         LegacyInferenceSteps(EnumSet<InferenceStep> steps) {

  1037             this.steps = steps;

  1038         }

  1039     }

  1041     /**

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

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

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

  1045      */

  1046     enum GraphInferenceSteps {

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

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

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

  1052         final EnumSet<InferenceStep> steps;

  1054         GraphInferenceSteps(EnumSet<InferenceStep> steps) {

  1055             this.steps = steps;

  1056         }

  1057     }

  1059     /**

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

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

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

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

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

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

  1066      */

  1067     class GraphSolver {

  1069         InferenceContext inferenceContext;

  1070         Warner warn;

  1072         GraphSolver(InferenceContext inferenceContext, Warner warn) {

  1073             this.inferenceContext = inferenceContext;

  1074             this.warn = warn;

  1075         }

  1077         /**

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

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

  1080          * depends on the selected solver strategy.

  1081          */

  1082         void solve(GraphStrategy sstrategy) {

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

  1084             InferenceGraph inferenceGraph = new InferenceGraph();

  1085             while (!sstrategy.done()) {

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

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

  1088                 inferenceContext.save();

  1089                 try {

  1090                     //repeat until all variables are solved

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

  1092                         //for each inference phase

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

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

  1095                                 checkWithinBounds(inferenceContext, warn);

  1096                                 continue outer;

  1097                             }

  1098                         }

  1099                         //no progress

  1100                         throw inferenceException;

  1101                     }

  1102                 }

  1103                 catch (InferenceException ex) {

  1104                     inferenceContext.rollback();

  1105                     instantiateAsUninferredVars(varsToSolve, inferenceContext);

  1106                     checkWithinBounds(inferenceContext, warn);

  1107                 }

  1108                 inferenceGraph.deleteNode(nodeToSolve);

  1109             }

  1110         }

  1112         /**

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

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

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

  1116          */

  1117         class InferenceGraph {

  1119             /**

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

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

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

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

  1124              * keep dependencies in sync).

  1125              */

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

  1128                 Set<Node> deps;

  1130                 Node(Type ivar) {

  1131                     super(ListBuffer.of(ivar));

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

  1133                 }

  1135                 @Override

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

  1137                     return deps;

  1138                 }

  1140                 @Override

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

  1142                     StringBuilder buf = new StringBuilder();

  1143                     String sep = "";

  1144                     for (Type from : data) {

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

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

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

  1148                                 buf.append(sep);

  1149                                 buf.append(bound);

  1150                                 sep = ",";

  1151                             }

  1152                         }

  1153                     }

  1154                     return buf.toString();

  1155                 }

  1157                 boolean isLeaf(Node n) {

  1158                     //no deps, or only one self dep

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

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

  1161                 }

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

  1164                     for (Node n : nodes) {

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

  1166                         data.appendList(n.data);

  1167                         deps.addAll(n.deps);

  1168                     }

  1169                     //update deps

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

  1171                     for (Node d : deps) {

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

  1173                             deps2.add(this);

  1174                         } else {

  1175                             deps2.add(d);

  1176                         }

  1177                     }

  1178                     deps = deps2;

  1179                 }

  1181                 void graphChanged(Node from, Node to) {

  1182                     if (deps.contains(from)) {

  1183                         deps.remove(from);

  1184                         if (to != null) {

  1185                             deps.add(to);

  1186                         }

  1187                     }

  1188                 }

  1189             }

  1191             /** the nodes in the inference graph */

  1192             ArrayList<Node> nodes;

  1194             InferenceGraph() {

  1195                 initNodes();

  1196             }

  1198             /**

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

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

  1201              */

  1202             public void deleteNode(Node n) {

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

  1204                 nodes.remove(n);

  1205                 notifyUpdate(n, null);

  1206             }

  1208             /**

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

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

  1211              */

  1212             void notifyUpdate(Node from, Node to) {

  1213                 for (Node n : nodes) {

  1214                     n.graphChanged(from, to);

  1215                 }

  1216             }

  1218             /**

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

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

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

  1222                  * created, effectively replacing the original cyclic nodes.

  1223              */

  1224             void initNodes() {

  1225                 nodes = new ArrayList<Node>();

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

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

  1228                 }

  1229                 for (Node n_i : nodes) {

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

  1231                     for (Node n_j : nodes) {

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

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

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

  1235                             //update i's deps

  1236                             n_i.deps.add(n_j);

  1237                         }

  1238                     }

  1239                 }

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

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

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

  1243                         Node root = conSubGraph.head;

  1244                         root.mergeWith(conSubGraph.tail);

  1245                         for (Node n : conSubGraph) {

  1246                             notifyUpdate(n, root);

  1247                         }

  1248                     }

  1249                     acyclicNodes.add(conSubGraph.head);

  1250                 }

  1251                 nodes = acyclicNodes;

  1252             }

  1254             /**

  1255              * Debugging: dot representation of this graph

  1256              */

  1257             String toDot() {

  1258                 StringBuilder buf = new StringBuilder();

  1259                 for (Type t : inferenceContext.undetvars) {

  1260                     UndetVar uv = (UndetVar)t;

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

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

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

  1264                 }

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

  1266             }

  1267         }

  1268     }

  1269     // </editor-fold>

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

  1272     /**

  1273      * Functional interface for defining inference callbacks. Certain actions

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

  1275      * have been fixed.

  1276      */

  1277     interface FreeTypeListener {

  1278         void typesInferred(InferenceContext inferenceContext);

  1279     }

  1281     /**

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

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

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

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

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

  1287      * (see InferenceKind).

  1288      */

  1289      class InferenceContext {

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

  1292         List<Type> undetvars;

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

  1295         List<Type> inferencevars;

  1297         /** backed up inference variables */

  1298         List<Type> saved_undet;

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

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

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

  1305         public InferenceContext(List<Type> inferencevars) {

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

  1307             this.inferencevars = inferencevars;

  1308         }

  1309         //where

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

  1311                 // mapping that turns inference variables into undet vars

  1312                 public Type apply(Type t) {

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

  1314                     else return t.map(this);

  1315                 }

  1316             };

  1318         /**

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

  1320          * inference context

  1321          */

  1322         List<Type> inferenceVars() {

  1323             return inferencevars;

  1324         }

  1326         /**

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

  1328          * inference context

  1329          */

  1330         List<Type> restvars() {

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

  1332                 public boolean accepts(UndetVar uv) {

  1333                     return uv.inst == null;

  1334                 }

  1335             });

  1336         }

  1338         /**

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

  1340          * inference context

  1341          */

  1342         List<Type> instvars() {

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

  1344                 public boolean accepts(UndetVar uv) {

  1345                     return uv.inst != null;

  1346                 }

  1347             });

  1348         }

  1350         /**

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

  1352          * declared bounds).

  1353          */

  1354         final List<Type> boundedVars() {

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

  1356                 public boolean accepts(UndetVar uv) {

  1357                     return uv.getBounds(InferenceBound.UPPER)

  1358                             .diff(uv.getDeclaredBounds())

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

  1360                 }

  1361             });

  1362         }

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

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

  1366             for (Type t : undetvars) {

  1367                 UndetVar uv = (UndetVar)t;

  1368                 if (fu.accepts(uv)) {

  1369                     res.append(uv.qtype);

  1370                 }

  1371             }

  1372             return res.toList();

  1373         }

  1375         /**

  1376          * is this type free?

  1377          */

  1378         final boolean free(Type t) {

  1379             return t.containsAny(inferencevars);

  1380         }

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

  1383             for (Type t : ts) {

  1384                 if (free(t)) return true;

  1385             }

  1386             return false;

  1387         }

  1389         /**

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

  1391          */

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

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

  1394             for (Type iv : inferenceVars()) {

  1395                 if (t.contains(iv)) {

  1396                     buf.add(iv);

  1397                 }

  1398             }

  1399             return buf.toList();

  1400         }

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

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

  1404             for (Type t : ts) {

  1405                 buf.appendList(freeVarsIn(t));

  1406             }

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

  1408             for (Type t : buf) {

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

  1410                     buf2.add(t);

  1411                 }

  1412             }

  1413             return buf2.toList();

  1414         }

  1416         /**

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

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

  1419          * of inference constraints).

  1420          */

  1421         final Type asFree(Type t) {

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

  1423         }

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

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

  1427             for (Type t : ts) {

  1428                 buf.append(asFree(t));

  1429             }

  1430             return buf.toList();

  1431         }

  1433         List<Type> instTypes() {

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

  1435             for (Type t : undetvars) {

  1436                 UndetVar uv = (UndetVar)t;

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

  1438             }

  1439             return buf.toList();

  1440         }

  1442         /**

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

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

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

  1446          */

  1447         Type asInstType(Type t) {

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

  1449         }

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

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

  1453             for (Type t : ts) {

  1454                 buf.append(asInstType(t));

  1455             }

  1456             return buf.toList();

  1457         }

  1459         /**

  1460          * Add custom hook for performing post-inference action

  1461          */

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

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

  1464         }

  1466         /**

  1467          * Mark the inference context as complete and trigger evaluation

  1468          * of all deferred checks.

  1469          */

  1470         void notifyChange() {

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

  1472         }

  1474         void notifyChange(List<Type> inferredVars) {

  1475             InferenceException thrownEx = null;

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

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

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

  1479                     try {

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

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

  1482                     } catch (InferenceException ex) {

  1483                         if (thrownEx == null) {

  1484                             thrownEx = ex;

  1485                         }

  1486                     }

  1487                 }

  1488             }

  1489             //inference exception multiplexing - present any inference exception

  1490             //thrown when processing listeners as a single one

  1491             if (thrownEx != null) {

  1492                 throw thrownEx;

  1493             }

  1494         }

  1496         /**

  1497          * Save the state of this inference context

  1498          */

  1499         void save() {

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

  1501             for (Type t : undetvars) {

  1502                 UndetVar uv = (UndetVar)t;

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

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

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

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

  1507                     }

  1508                 }

  1509                 uv2.inst = uv.inst;

  1510                 buf.add(uv2);

  1511             }

  1512             saved_undet = buf.toList();

  1513         }

  1515         /**

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

  1517          */

  1518         void rollback() {

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

  1520             undetvars = saved_undet;

  1521             saved_undet = null;

  1522         }

  1524         /**

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

  1526          */

  1527         void dupTo(final InferenceContext that) {

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

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

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

  1531             //propagated vars are inferred in new context

  1532             for (Type t : inferencevars) {

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

  1534                     public void typesInferred(InferenceContext inferenceContext) {

  1535                         InferenceContext.this.notifyChange();

  1536                     }

  1537                 }, List.of(t));

  1538             }

  1539         }

  1541         /**

  1542          * Solve with given graph strategy.

  1543          */

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

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

  1546             s.solve(ss);

  1547         }

  1549         /**

  1550          * Solve all variables in this context.

  1551          */

  1552         public void solve(Warner warn) {

  1553             solve(new LeafSolver() {

  1554                 public boolean done() {

  1555                     return restvars().isEmpty();

  1556                 }

  1557             }, warn);

  1558         }

  1560         /**

  1561          * Solve all variables in the given list.

  1562          */

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

  1564             solve(new BestLeafSolver(vars) {

  1565                 public boolean done() {

  1566                     return !free(asInstTypes(vars));

  1567                 }

  1568             }, warn);

  1569         }

  1571         /**

  1572          * Solve at least one variable in given list.

  1573          */

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

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

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

  1577             if (boundedVars.isEmpty()) {

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

  1579                                 freeVarsIn(varsToSolve));

  1580             }

  1581             solve(new BestLeafSolver(boundedVars) {

  1582                 public boolean done() {

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

  1584                 }

  1585             }, warn);

  1586         }

  1588         /**

  1589          * Apply a set of inference steps

  1590          */

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

  1592             return solveBasic(inferencevars, steps);

  1593         }

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

  1596             boolean changed = false;

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

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

  1599                 for (InferenceStep step : steps) {

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

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

  1602                         changed = true;

  1603                         break;

  1604                     }

  1605                 }

  1606             }

  1607             return changed;

  1608         }

  1610         /**

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

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

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

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

  1615          * instantiation, until all variables are solved.

  1616          */

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

  1618             while (true) {

  1619                 boolean stuck = !solveBasic(steps);

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

  1621                     //all variables have been instantiated - exit

  1622                     break;

  1623                 } else if (stuck) {

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

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

  1626                     instantiateAsUninferredVars(restvars(), this);

  1627                     break;

  1628                 } else {

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

  1630                     //variables in remaining upper bounds and continue

  1631                     for (Type t : undetvars) {

  1632                         UndetVar uv = (UndetVar)t;

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

  1634                     }

  1635                 }

  1636             }

  1637             checkWithinBounds(this, warn);

  1638         }

  1640         private Infer infer() {

  1641             //back-door to infer

  1642             return Infer.this;

  1643         }

  1644     }

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

  1647     // </editor-fold>

  1648 }

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

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

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