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

8016175: Add bottom-up type-checking support for unambiguous method references
Summary: Type-checking of non-overloaded method references should be independent from target-type
Reviewed-by: jjg, vromero

     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     }

   229     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          * Infer uninstantiated/unbound inference variables occurring in 'throws'

   972          * clause as RuntimeException

   973          */

   974         THROWS(InferenceBound.UPPER) {

   975             @Override

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

   977                 if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) {

   978                     //not a throws undet var

   979                     return false;

   980                 }

   981                 if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER)

   982                             .diff(t.getDeclaredBounds()).nonEmpty()) {

   983                     //not an unbounded undet var

   984                     return false;

   985                 }

   986                 Infer infer = inferenceContext.infer();

   987                 for (Type db : t.getDeclaredBounds()) {

   988                     if (t.isInterface()) continue;

   989                     if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) {

   990                         //declared bound is a supertype of RuntimeException

   991                         return true;

   992                     }

   993                 }

   994                 //declared bound is more specific then RuntimeException - give up

   995                 return false;

   996             }

   998             @Override

   999             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1000                 return inferenceContext.infer().syms.runtimeExceptionType;

  1001             }

  1002         },

  1003         /**

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

  1005          * bounds are merged together using glb().

  1006          */

  1007         UPPER(InferenceBound.UPPER) {

  1008             @Override

  1009             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1010                 Infer infer = inferenceContext.infer();

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

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

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

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

  1015                     throw infer.inferenceException

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

  1017                                     uv.qtype, hibounds);

  1018                 } else {

  1019                     return owntype;

  1020                 }

  1021             }

  1022         },

  1023         /**

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

  1025          * if all upper bounds are ground.

  1026          */

  1027         UPPER_LEGACY(InferenceBound.UPPER) {

  1028             @Override

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

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

  1031             }

  1033             @Override

  1034             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1035                 return UPPER.solve(uv, inferenceContext);

  1036             }

  1037         };

  1039         final InferenceBound ib;

  1041         InferenceStep(InferenceBound ib) {

  1042             this.ib = ib;

  1043         }

  1045         /**

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

  1047          * a given inference context

  1048          */

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

  1051         /**

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

  1053          */

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

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

  1056         }

  1058         /**

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

  1060          */

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

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

  1063         }

  1064     }

  1066     /**

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

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

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

  1070      */

  1071     enum LegacyInferenceSteps {

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

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

  1076         final EnumSet<InferenceStep> steps;

  1078         LegacyInferenceSteps(EnumSet<InferenceStep> steps) {

  1079             this.steps = steps;

  1080         }

  1081     }

  1083     /**

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

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

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

  1087      */

  1088     enum GraphInferenceSteps {

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

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

  1092         EQ_LOWER_THROWS_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.THROWS, InferenceStep.UPPER));

  1094         final EnumSet<InferenceStep> steps;

  1096         GraphInferenceSteps(EnumSet<InferenceStep> steps) {

  1097             this.steps = steps;

  1098         }

  1099     }

  1101     /**

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

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

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

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

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

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

  1108      */

  1109     class GraphSolver {

  1111         InferenceContext inferenceContext;

  1112         Warner warn;

  1114         GraphSolver(InferenceContext inferenceContext, Warner warn) {

  1115             this.inferenceContext = inferenceContext;

  1116             this.warn = warn;

  1117         }

  1119         /**

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

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

  1122          * depends on the selected solver strategy.

  1123          */

  1124         void solve(GraphStrategy sstrategy) {

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

  1126             InferenceGraph inferenceGraph = new InferenceGraph();

  1127             while (!sstrategy.done()) {

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

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

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

  1131                 try {

  1132                     //repeat until all variables are solved

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

  1134                         //for each inference phase

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

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

  1137                                 checkWithinBounds(inferenceContext, warn);

  1138                                 continue outer;

  1139                             }

  1140                         }

  1141                         //no progress

  1142                         throw inferenceException.setMessage();

  1143                     }

  1144                 }

  1145                 catch (InferenceException ex) {

  1146                     //did we fail because of interdependent ivars?

  1147                     inferenceContext.rollback(saved_undet);

  1148                     instantiateAsUninferredVars(varsToSolve, inferenceContext);

  1149                     checkWithinBounds(inferenceContext, warn);

  1150                 }

  1151                 inferenceGraph.deleteNode(nodeToSolve);

  1152             }

  1153         }

  1155         /**

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

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

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

  1159          */

  1160         class InferenceGraph {

  1162             /**

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

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

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

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

  1167              * keep dependencies in sync).

  1168              */

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

  1171                 Set<Node> deps;

  1173                 Node(Type ivar) {

  1174                     super(ListBuffer.of(ivar));

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

  1176                 }

  1178                 @Override

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

  1180                     return deps;

  1181                 }

  1183                 @Override

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

  1185                     StringBuilder buf = new StringBuilder();

  1186                     String sep = "";

  1187                     for (Type from : data) {

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

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

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

  1191                                 buf.append(sep);

  1192                                 buf.append(bound);

  1193                                 sep = ",";

  1194                             }

  1195                         }

  1196                     }

  1197                     return buf.toString();

  1198                 }

  1200                 boolean isLeaf(Node n) {

  1201                     //no deps, or only one self dep

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

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

  1204                 }

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

  1207                     for (Node n : nodes) {

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

  1209                         data.appendList(n.data);

  1210                         deps.addAll(n.deps);

  1211                     }

  1212                     //update deps

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

  1214                     for (Node d : deps) {

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

  1216                             deps2.add(this);

  1217                         } else {

  1218                             deps2.add(d);

  1219                         }

  1220                     }

  1221                     deps = deps2;

  1222                 }

  1224                 void graphChanged(Node from, Node to) {

  1225                     if (deps.contains(from)) {

  1226                         deps.remove(from);

  1227                         if (to != null) {

  1228                             deps.add(to);

  1229                         }

  1230                     }

  1231                 }

  1232             }

  1234             /** the nodes in the inference graph */

  1235             ArrayList<Node> nodes;

  1237             InferenceGraph() {

  1238                 initNodes();

  1239             }

  1241             /**

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

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

  1244              */

  1245             public void deleteNode(Node n) {

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

  1247                 nodes.remove(n);

  1248                 notifyUpdate(n, null);

  1249             }

  1251             /**

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

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

  1254              */

  1255             void notifyUpdate(Node from, Node to) {

  1256                 for (Node n : nodes) {

  1257                     n.graphChanged(from, to);

  1258                 }

  1259             }

  1261             /**

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

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

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

  1265                  * created, effectively replacing the original cyclic nodes.

  1266              */

  1267             void initNodes() {

  1268                 nodes = new ArrayList<Node>();

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

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

  1271                 }

  1272                 for (Node n_i : nodes) {

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

  1274                     for (Node n_j : nodes) {

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

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

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

  1278                             //update i's deps

  1279                             n_i.deps.add(n_j);

  1280                         }

  1281                     }

  1282                 }

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

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

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

  1286                         Node root = conSubGraph.head;

  1287                         root.mergeWith(conSubGraph.tail);

  1288                         for (Node n : conSubGraph) {

  1289                             notifyUpdate(n, root);

  1290                         }

  1291                     }

  1292                     acyclicNodes.add(conSubGraph.head);

  1293                 }

  1294                 nodes = acyclicNodes;

  1295             }

  1297             /**

  1298              * Debugging: dot representation of this graph

  1299              */

  1300             String toDot() {

  1301                 StringBuilder buf = new StringBuilder();

  1302                 for (Type t : inferenceContext.undetvars) {

  1303                     UndetVar uv = (UndetVar)t;

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

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

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

  1307                 }

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

  1309             }

  1310         }

  1311     }

  1312     // </editor-fold>

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

  1315     /**

  1316      * Functional interface for defining inference callbacks. Certain actions

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

  1318      * have been fixed.

  1319      */

  1320     interface FreeTypeListener {

  1321         void typesInferred(InferenceContext inferenceContext);

  1322     }

  1324     /**

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

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

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

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

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

  1330      * (see InferenceKind).

  1331      */

  1332      class InferenceContext {

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

  1335         List<Type> undetvars;

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

  1338         List<Type> inferencevars;

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

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

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

  1345         public InferenceContext(List<Type> inferencevars) {

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

  1347             this.inferencevars = inferencevars;

  1348         }

  1349         //where

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

  1351                 // mapping that turns inference variables into undet vars

  1352                 public Type apply(Type t) {

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

  1354                     else return t.map(this);

  1355                 }

  1356             };

  1358         /**

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

  1360          * inference context

  1361          */

  1362         List<Type> inferenceVars() {

  1363             return inferencevars;

  1364         }

  1366         /**

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

  1368          * inference context

  1369          */

  1370         List<Type> restvars() {

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

  1372                 public boolean accepts(UndetVar uv) {

  1373                     return uv.inst == null;

  1374                 }

  1375             });

  1376         }

  1378         /**

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

  1380          * inference context

  1381          */

  1382         List<Type> instvars() {

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

  1384                 public boolean accepts(UndetVar uv) {

  1385                     return uv.inst != null;

  1386                 }

  1387             });

  1388         }

  1390         /**

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

  1392          * declared bounds).

  1393          */

  1394         final List<Type> boundedVars() {

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

  1396                 public boolean accepts(UndetVar uv) {

  1397                     return uv.getBounds(InferenceBound.UPPER)

  1398                             .diff(uv.getDeclaredBounds())

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

  1400                 }

  1401             });

  1402         }

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

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

  1406             for (Type t : undetvars) {

  1407                 UndetVar uv = (UndetVar)t;

  1408                 if (fu.accepts(uv)) {

  1409                     res.append(uv.qtype);

  1410                 }

  1411             }

  1412             return res.toList();

  1413         }

  1415         /**

  1416          * is this type free?

  1417          */

  1418         final boolean free(Type t) {

  1419             return t.containsAny(inferencevars);

  1420         }

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

  1423             for (Type t : ts) {

  1424                 if (free(t)) return true;

  1425             }

  1426             return false;

  1427         }

  1429         /**

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

  1431          */

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

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

  1434             for (Type iv : inferenceVars()) {

  1435                 if (t.contains(iv)) {

  1436                     buf.add(iv);

  1437                 }

  1438             }

  1439             return buf.toList();

  1440         }

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

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

  1444             for (Type t : ts) {

  1445                 buf.appendList(freeVarsIn(t));

  1446             }

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

  1448             for (Type t : buf) {

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

  1450                     buf2.add(t);

  1451                 }

  1452             }

  1453             return buf2.toList();

  1454         }

  1456         /**

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

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

  1459          * of inference constraints).

  1460          */

  1461         final Type asFree(Type t) {

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

  1463         }

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

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

  1467             for (Type t : ts) {

  1468                 buf.append(asFree(t));

  1469             }

  1470             return buf.toList();

  1471         }

  1473         List<Type> instTypes() {

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

  1475             for (Type t : undetvars) {

  1476                 UndetVar uv = (UndetVar)t;

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

  1478             }

  1479             return buf.toList();

  1480         }

  1482         /**

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

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

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

  1486          */

  1487         Type asInstType(Type t) {

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

  1489         }

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

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

  1493             for (Type t : ts) {

  1494                 buf.append(asInstType(t));

  1495             }

  1496             return buf.toList();

  1497         }

  1499         /**

  1500          * Add custom hook for performing post-inference action

  1501          */

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

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

  1504         }

  1506         /**

  1507          * Mark the inference context as complete and trigger evaluation

  1508          * of all deferred checks.

  1509          */

  1510         void notifyChange() {

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

  1512         }

  1514         void notifyChange(List<Type> inferredVars) {

  1515             InferenceException thrownEx = null;

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

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

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

  1519                     try {

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

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

  1522                     } catch (InferenceException ex) {

  1523                         if (thrownEx == null) {

  1524                             thrownEx = ex;

  1525                         }

  1526                     }

  1527                 }

  1528             }

  1529             //inference exception multiplexing - present any inference exception

  1530             //thrown when processing listeners as a single one

  1531             if (thrownEx != null) {

  1532                 throw thrownEx;

  1533             }

  1534         }

  1536         /**

  1537          * Save the state of this inference context

  1538          */

  1539         List<Type> save() {

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

  1541             for (Type t : undetvars) {

  1542                 UndetVar uv = (UndetVar)t;

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

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

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

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

  1547                     }

  1548                 }

  1549                 uv2.inst = uv.inst;

  1550                 buf.add(uv2);

  1551             }

  1552             return buf.toList();

  1553         }

  1555         /**

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

  1557          */

  1558         void rollback(List<Type> saved_undet) {

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

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

  1561             for (Type t : undetvars) {

  1562                 UndetVar uv = (UndetVar)t;

  1563                 UndetVar uv_saved = (UndetVar)saved_undet.head;

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

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

  1566                 }

  1567                 uv.inst = uv_saved.inst;

  1568                 saved_undet = saved_undet.tail;

  1569             }

  1570         }

  1572         /**

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

  1574          */

  1575         void dupTo(final InferenceContext that) {

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

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

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

  1579             //propagated vars are inferred in new context

  1580             for (Type t : inferencevars) {

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

  1582                     public void typesInferred(InferenceContext inferenceContext) {

  1583                         InferenceContext.this.notifyChange();

  1584                     }

  1585                 }, List.of(t));

  1586             }

  1587         }

  1589         /**

  1590          * Solve with given graph strategy.

  1591          */

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

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

  1594             s.solve(ss);

  1595         }

  1597         /**

  1598          * Solve all variables in this context.

  1599          */

  1600         public void solve(Warner warn) {

  1601             solve(new LeafSolver() {

  1602                 public boolean done() {

  1603                     return restvars().isEmpty();

  1604                 }

  1605             }, warn);

  1606         }

  1608         /**

  1609          * Solve all variables in the given list.

  1610          */

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

  1612             solve(new BestLeafSolver(vars) {

  1613                 public boolean done() {

  1614                     return !free(asInstTypes(vars));

  1615                 }

  1616             }, warn);

  1617         }

  1619         /**

  1620          * Solve at least one variable in given list.

  1621          */

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

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

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

  1625             if (boundedVars.isEmpty()) {

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

  1627                                 freeVarsIn(varsToSolve));

  1628             }

  1629             solve(new BestLeafSolver(boundedVars) {

  1630                 public boolean done() {

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

  1632                 }

  1633             }, warn);

  1634         }

  1636         /**

  1637          * Apply a set of inference steps

  1638          */

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

  1640             return solveBasic(inferencevars, steps);

  1641         }

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

  1644             boolean changed = false;

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

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

  1647                 for (InferenceStep step : steps) {

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

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

  1650                         changed = true;

  1651                         break;

  1652                     }

  1653                 }

  1654             }

  1655             return changed;

  1656         }

  1658         /**

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

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

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

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

  1663          * instantiation, until all variables are solved.

  1664          */

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

  1666             while (true) {

  1667                 boolean stuck = !solveBasic(steps);

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

  1669                     //all variables have been instantiated - exit

  1670                     break;

  1671                 } else if (stuck) {

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

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

  1674                     instantiateAsUninferredVars(restvars(), this);

  1675                     break;

  1676                 } else {

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

  1678                     //variables in remaining upper bounds and continue

  1679                     for (Type t : undetvars) {

  1680                         UndetVar uv = (UndetVar)t;

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

  1682                     }

  1683                 }

  1684             }

  1685             checkWithinBounds(this, warn);

  1686         }

  1688         private Infer infer() {

  1689             //back-door to infer

  1690             return Infer.this;

  1691         }

  1692     }

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

  1695     // </editor-fold>

  1696 }

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

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

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