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

8020147: Spurious errors when compiling nested stuck lambdas
Summary: Scope of deferred types is not copied correctly; postAttr analyzer should not run on stuck expressions
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 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                 Type newRestype = generateReturnConstraints(resultInfo, mt, inferenceContext);

   163                 mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype);

   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     Type generateReturnConstraints(Attr.ResultInfo resultInfo,

   214             MethodType mt, InferenceContext inferenceContext) {

   215         Type from = mt.getReturnType();

   216         if (mt.getReturnType().containsAny(inferenceContext.inferencevars) &&

   217                 resultInfo.checkContext.inferenceContext() != emptyContext) {

   218             from = types.capture(from);

   219             //add synthetic captured ivars

   220             for (Type t : from.getTypeArguments()) {

   221                 if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) {

   222                     inferenceContext.addVar((TypeVar)t);

   223                 }

   224             }

   225         }

   226         Type qtype1 = inferenceContext.asFree(from);

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

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

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

   230         //we need to skip capture?

   231         Warner retWarn = new Warner();

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

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

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

   235             throw inferenceException

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

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

   238         }

   239         return from;

   240     }

   242     Type returnConstraintTarget(Type from, Type to) {

   243         if (from.hasTag(VOID)) {

   244             return syms.voidType;

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

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

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

   248             if (!allowGraphInference) {

   249                 //if legacy, just return boxed type

   250                 return types.boxedClass(to).type;

   251             }

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

   253             UndetVar uv = (UndetVar)from;

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

   255                 Type boundAsPrimitive = types.unboxedType(t);

   256                 if (boundAsPrimitive == null) continue;

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

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

   259                     return syms.objectType;

   260                 }

   261             }

   262             return types.boxedClass(to).type;

   263         } else {

   264             return to;

   265         }

   266     }

   268     /**

   269       * Infer cyclic inference variables as described in 15.12.2.8.

   270       */

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

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

   273         //step 1 - create fresh tvars

   274         for (Type t : vars) {

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

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

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

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

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

   280                 todo.append(uv);

   281                 uv.inst = fresh_tvar.type;

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

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

   284             } else {

   285                 uv.inst = syms.objectType;

   286             }

   287         }

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

   289         List<Type> formals = vars;

   290         for (Type t : todo) {

   291             UndetVar uv = (UndetVar)t;

   292             TypeVar ct = (TypeVar)uv.inst;

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

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

   295                 //report inference error if glb fails

   296                 reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   297             }

   298             formals = formals.tail;

   299         }

   300     }

   302     /**

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

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

   305      * enclosing scope surrounding the polymorphic-signature call.

   306      */

   307     Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,

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

   309                                             Resolve.MethodResolutionContext resolveContext,

   310                                             List<Type> argtypes) {

   311         final Type restype;

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

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

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

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

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

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

   319         //the polymorphic signature call environment is nested.

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

   322             case TYPECAST:

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

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

   325                     castTree.clazz.type :

   326                     syms.objectType;

   327                 break;

   328             case EXEC:

   329                 JCTree.JCExpressionStatement execTree =

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

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

   332                     syms.voidType :

   333                     syms.objectType;

   334                 break;

   335             default:

   336                 restype = syms.objectType;

   337         }

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

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

   341             spMethod.getThrownTypes() :

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

   344         MethodType mtype = new MethodType(paramtypes,

   345                                           restype,

   346                                           exType,

   347                                           syms.methodClass);

   348         return mtype;

   349     }

   350     //where

   351         class ImplicitArgType extends DeferredAttr.DeferredTypeMap {

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

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

   355             }

   357             public Type apply(Type t) {

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

   359                 if (t.hasTag(BOT))

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

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

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

   363                 return t;

   364             }

   365         }

   367     /**

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

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

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

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

   372       */

   373     public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,

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

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

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

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

   378             return funcInterface;

   379         } else {

   380             Type formalInterface = funcInterface.tsym.type;

   381             InferenceContext funcInterfaceContext =

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

   384             Assert.check(paramTypes != null);

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

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

   387             //in the functional interface descriptors)

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

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

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

   391                 return types.createErrorType(funcInterface);

   392             }

   393             for (Type p : descParameterTypes) {

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

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

   396                     return types.createErrorType(funcInterface);

   397                 }

   398                 paramTypes = paramTypes.tail;

   399             }

   401             try {

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

   403             } catch (InferenceException ex) {

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

   405             }

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

   408             for (Type t : funcInterfaceContext.undetvars) {

   409                 UndetVar uv = (UndetVar)t;

   410                 if (uv.inst == null) {

   411                     uv.inst = actualTypeargs.head;

   412                 }

   413                 actualTypeargs = actualTypeargs.tail;

   414             }

   416             Type owntype = funcInterfaceContext.asInstType(formalInterface);

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

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

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

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

   421             }

   422             return owntype;

   423         }

   424     }

   425     // </editor-fold>

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

   428     /**

   429      * Check bounds and perform incorporation

   430      */

   431     void checkWithinBounds(InferenceContext inferenceContext,

   432                              Warner warn) throws InferenceException {

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

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

   435         try {

   436             while (true) {

   437                 mlistener.reset();

   438                 if (!allowGraphInference) {

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

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

   441                     for (Type t : inferenceContext.undetvars) {

   442                         UndetVar uv = (UndetVar)t;

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

   444                     }

   445                 }

   446                 for (Type t : inferenceContext.undetvars) {

   447                     UndetVar uv = (UndetVar)t;

   448                     //bound incorporation

   449                     EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?

   450                             incorporationStepsGraph : incorporationStepsLegacy;

   451                     for (IncorporationStep is : incorporationSteps) {

   452                         if (is.accepts(uv, inferenceContext)) {

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

   454                         }

   455                     }

   456                 }

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

   458             }

   459         }

   460         finally {

   461             mlistener.detach();

   462             if (mlistener.rounds == MAX_INCORPORATION_STEPS) {

   463                 inferenceContext.rollback(saved_undet);

   464             }

   465         }

   466     }

   467     //where

   468         /**

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

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

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

   472          * left in a clean state.

   473          */

   474         class MultiUndetVarListener implements UndetVar.UndetVarListener {

   476             int rounds;

   477             boolean changed;

   478             List<Type> undetvars;

   480             public MultiUndetVarListener(List<Type> undetvars) {

   481                 this.undetvars = undetvars;

   482                 for (Type t : undetvars) {

   483                     UndetVar uv = (UndetVar)t;

   484                     uv.listener = this;

   485                 }

   486             }

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

   489                 //avoid non-termination

   490                 if (rounds < MAX_INCORPORATION_STEPS) {

   491                     changed = true;

   492                 }

   493             }

   495             void reset() {

   496                 rounds++;

   497                 changed = false;

   498             }

   500             void detach() {

   501                 for (Type t : undetvars) {

   502                     UndetVar uv = (UndetVar)t;

   503                     uv.listener = null;

   504                 }

   505             }

   506         };

   508         /** max number of incorporation rounds */

   509         static final int MAX_INCORPORATION_STEPS = 100;

   511     /**

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

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

   514      * logic into the basic bound checking routine

   515      */

   516     enum IncorporationStep {

   517         /**

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

   519          * inference variable compatible with its bounds?

   520          */

   521         CHECK_BOUNDS() {

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

   523                 Infer infer = inferenceContext.infer();

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

   525                 infer.checkCompatibleUpperBounds(uv, inferenceContext);

   526                 if (uv.inst != null) {

   527                     Type inst = uv.inst;

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

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

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

   531                         }

   532                     }

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

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

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

   536                         }

   537                     }

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

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

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

   541                         }

   542                     }

   543                 }

   544             }

   545             @Override

   546             boolean accepts(UndetVar uv, InferenceContext inferenceContext) {

   547                 //applies to all undetvars

   548                 return true;

   549             }

   550         },

   551         /**

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

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

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

   555          */

   556         EQ_CHECK_LEGACY() {

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

   558                 Infer infer = inferenceContext.infer();

   559                 Type eq = null;

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

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

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

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

   564                     }

   565                     eq = e;

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

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

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

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

   570                         }

   571                     }

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

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

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

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

   576                         }

   577                     }

   578                 }

   579             }

   580         },

   581         /**

   582          * Check consistency of equality constraints.

   583          */

   584         EQ_CHECK() {

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

   586                 Infer infer = inferenceContext.infer();

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

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

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

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

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

   592                         }

   593                     }

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

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

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

   597                         }

   598                     }

   599                 }

   600             }

   601         },

   602         /**

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

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

   605          */

   606         CROSS_UPPER_LOWER() {

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

   608                 Infer infer = inferenceContext.infer();

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

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

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

   612                     }

   613                 }

   614             }

   615         },

   616         /**

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

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

   619          */

   620         CROSS_UPPER_EQ() {

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

   622                 Infer infer = inferenceContext.infer();

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

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

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

   626                     }

   627                 }

   628             }

   629         },

   630         /**

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

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

   633          */

   634         CROSS_EQ_LOWER() {

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

   636                 Infer infer = inferenceContext.infer();

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

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

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

   640                     }

   641                 }

   642             }

   643         },

   644         /**

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

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

   647          */

   648         CROSS_EQ_EQ() {

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

   650                 Infer infer = inferenceContext.infer();

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

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

   653                         if (b1 != b2) {

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

   655                         }

   656                     }

   657                 }

   658             }

   659         },

   660         /**

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

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

   663          */

   664         PROP_UPPER() {

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

   666                 Infer infer = inferenceContext.infer();

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

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

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

   670                         if (uv2.isCaptured()) continue;

   671                         //alpha <: beta

   672                         //0. set beta :> alpha

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

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

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

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

   677                         }

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

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

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

   681                         }

   682                     }

   683                 }

   684             }

   685         },

   686         /**

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

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

   689          */

   690         PROP_LOWER() {

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

   692                 Infer infer = inferenceContext.infer();

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

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

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

   696                         if (uv2.isCaptured()) continue;

   697                         //alpha :> beta

   698                         //0. set beta <: alpha

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

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

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

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

   703                         }

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

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

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

   707                         }

   708                     }

   709                 }

   710             }

   711         },

   712         /**

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

   714          * bounds from alpha to beta and back.

   715          */

   716         PROP_EQ() {

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

   718                 Infer infer = inferenceContext.infer();

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

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

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

   722                         if (uv2.isCaptured()) continue;

   723                         //alpha == beta

   724                         //0. set beta == alpha

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

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

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

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

   729                                 if (b2 != uv2) {

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

   731                                 }

   732                             }

   733                         }

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

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

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

   737                                 if (b2 != uv) {

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

   739                                 }

   740                             }

   741                         }

   742                     }

   743                 }

   744             }

   745         };

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

   749         boolean accepts(UndetVar uv, InferenceContext inferenceContext) {

   750             return !uv.isCaptured();

   751         }

   752     }

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

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

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

   758     EnumSet<IncorporationStep> incorporationStepsGraph =

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

   761     /**

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

   763      * variable by making sure that a glb exists.

   764      */

   765     void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {

   766         List<Type> hibounds =

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

   768         Type hb = null;

   769         if (hibounds.isEmpty())

   770             hb = syms.objectType;

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

   772             hb = hibounds.head;

   773         else

   774             hb = types.glb(hibounds);

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

   776             reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   777     }

   778     //where

   779         protected static class BoundFilter implements Filter<Type> {

   781             InferenceContext inferenceContext;

   783             public BoundFilter(InferenceContext inferenceContext) {

   784                 this.inferenceContext = inferenceContext;

   785             }

   787             @Override

   788             public boolean accepts(Type t) {

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

   790                         !t.hasTag(BOT);

   791             }

   792         };

   794     /**

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

   796      */

   797     enum BoundErrorKind {

   798         /**

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

   800          */

   801         BAD_UPPER() {

   802             @Override

   803             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   805                         uv.getBounds(InferenceBound.UPPER));

   806             }

   807         },

   808         /**

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

   810          */

   811         BAD_EQ_UPPER() {

   812             @Override

   813             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   816             }

   817         },

   818         /**

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

   820          */

   821         BAD_EQ_LOWER() {

   822             @Override

   823             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   826             }

   827         },

   828         /**

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

   830          */

   831         UPPER() {

   832             @Override

   833             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   835                         uv.getBounds(InferenceBound.UPPER));

   836             }

   837         },

   838         /**

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

   840          */

   841         LOWER() {

   842             @Override

   843             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   845                         uv.getBounds(InferenceBound.LOWER));

   846             }

   847         },

   848         /**

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

   850          */

   851         EQ() {

   852             @Override

   853             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   855                         uv.getBounds(InferenceBound.EQ));

   856             }

   857         };

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

   860     }

   862     /**

   863      * Report a bound-checking error of given kind

   864      */

   865     void reportBoundError(UndetVar uv, BoundErrorKind bk) {

   866         throw bk.setMessage(inferenceException, uv);

   867     }

   868     // </editor-fold>

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

   871     /**

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

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

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

   875      */

   876     interface GraphStrategy {

   877         /**

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

   879          */

   880         Node pickNode(InferenceGraph g);

   881         /**

   882          * Is this the last step?

   883          */

   884         boolean done();

   885     }

   887     /**

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

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

   890      */

   891     abstract class LeafSolver implements GraphStrategy {

   892         public Node pickNode(InferenceGraph g) {

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

   894             return g.nodes.get(0);

   895         }

   896     }

   898     /**

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

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

   901      * or more inference variables in a given list

   902      */

   903     abstract class BestLeafSolver extends LeafSolver {

   905         List<Type> varsToSolve;

   907         BestLeafSolver(List<Type> varsToSolve) {

   908             this.varsToSolve = varsToSolve;

   909         }

   911         /**

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

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

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

   915          * a given node

   916          */

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

   918             if (costMap.containsKey(n)) {

   919                 return;

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

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

   922             } else {

   923                 int subcost = Integer.MAX_VALUE;

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

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

   926                     computeCostIfNeeded(n2, costMap);

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

   928                 }

   929                 //update cost map to reflect real cost

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

   931                         Integer.MAX_VALUE :

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

   933             }

   934         }

   936         /**

   937          * Pick the leaf that minimize cost

   938          */

   939         @Override

   940         public Node pickNode(final InferenceGraph g) {

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

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

   943             for (Node n : g.nodes) {

   944                 computeCostIfNeeded(n, costMap);

   945                 if (n.isLeaf(n)) {

   946                     leaves.add(n);

   947                 }

   948             }

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

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

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

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

   953                 }

   954             });

   955             return leaves.get(0);

   956         }

   957     }

   959     /**

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

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

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

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

   964      */

   965     enum InferenceStep {

   967         /**

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

   969          * constraints

   970          */

   971         EQ(InferenceBound.EQ) {

   972             @Override

   973             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   974                 return filterBounds(uv, inferenceContext).head;

   975             }

   976         },

   977         /**

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

   979          * bounds are merged together using lub().

   980          */

   981         LOWER(InferenceBound.LOWER) {

   982             @Override

   983             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   984                 Infer infer = inferenceContext.infer();

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

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

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

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

   989                     throw infer.inferenceException

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

   991                                     uv.qtype, lobounds);

   992                 } else {

   993                     return owntype;

   994                 }

   995             }

   996         },

   997         /**

   998          * Infer uninstantiated/unbound inference variables occurring in 'throws'

   999          * clause as RuntimeException

  1000          */

  1001         THROWS(InferenceBound.UPPER) {

  1002             @Override

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

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

  1005                     //not a throws undet var

  1006                     return false;

  1007                 }

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

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

  1010                     //not an unbounded undet var

  1011                     return false;

  1012                 }

  1013                 Infer infer = inferenceContext.infer();

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

  1015                     if (t.isInterface()) continue;

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

  1017                         //declared bound is a supertype of RuntimeException

  1018                         return true;

  1019                     }

  1020                 }

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

  1022                 return false;

  1023             }

  1025             @Override

  1026             Type solve(UndetVar uv, InferenceContext inferenceContext) {

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

  1028             }

  1029         },

  1030         /**

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

  1032          * bounds are merged together using glb().

  1033          */

  1034         UPPER(InferenceBound.UPPER) {

  1035             @Override

  1036             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1037                 Infer infer = inferenceContext.infer();

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

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

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

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

  1042                     throw infer.inferenceException

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

  1044                                     uv.qtype, hibounds);

  1045                 } else {

  1046                     return owntype;

  1047                 }

  1048             }

  1049         },

  1050         /**

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

  1052          * if all upper bounds are ground.

  1053          */

  1054         UPPER_LEGACY(InferenceBound.UPPER) {

  1055             @Override

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

  1057                 return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured();

  1058             }

  1060             @Override

  1061             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1062                 return UPPER.solve(uv, inferenceContext);

  1063             }

  1064         },

  1065         /**

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

  1067          * if all upper/lower bounds are ground.

  1068          */

  1069         CAPTURED(InferenceBound.UPPER) {

  1070             @Override

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

  1072                 return !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER));

  1073             }

  1075             @Override

  1076             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1077                 Infer infer = inferenceContext.infer();

  1078                 Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ?

  1079                         UPPER.solve(uv, inferenceContext) :

  1080                         infer.syms.objectType;

  1081                 Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ?

  1082                         LOWER.solve(uv, inferenceContext) :

  1083                         infer.syms.botType;

  1084                 CapturedType prevCaptured = (CapturedType)uv.qtype;

  1085                 return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, upper, lower, prevCaptured.wildcard);

  1086             }

  1087         };

  1089         final InferenceBound ib;

  1091         InferenceStep(InferenceBound ib) {

  1092             this.ib = ib;

  1093         }

  1095         /**

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

  1097          * a given inference context

  1098          */

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

  1101         /**

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

  1103          */

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

  1105             return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured();

  1106         }

  1108         /**

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

  1110          */

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

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

  1113         }

  1114     }

  1116     /**

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

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

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

  1120      */

  1121     enum LegacyInferenceSteps {

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

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

  1126         final EnumSet<InferenceStep> steps;

  1128         LegacyInferenceSteps(EnumSet<InferenceStep> steps) {

  1129             this.steps = steps;

  1130         }

  1131     }

  1133     /**

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

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

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

  1137      */

  1138     enum GraphInferenceSteps {

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

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

  1142         EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED));

  1144         final EnumSet<InferenceStep> steps;

  1146         GraphInferenceSteps(EnumSet<InferenceStep> steps) {

  1147             this.steps = steps;

  1148         }

  1149     }

  1151     /**

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

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

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

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

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

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

  1158      */

  1159     class GraphSolver {

  1161         InferenceContext inferenceContext;

  1162         Warner warn;

  1164         GraphSolver(InferenceContext inferenceContext, Warner warn) {

  1165             this.inferenceContext = inferenceContext;

  1166             this.warn = warn;

  1167         }

  1169         /**

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

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

  1172          * depends on the selected solver strategy.

  1173          */

  1174         void solve(GraphStrategy sstrategy) {

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

  1176             InferenceGraph inferenceGraph = new InferenceGraph();

  1177             while (!sstrategy.done()) {

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

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

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

  1181                 try {

  1182                     //repeat until all variables are solved

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

  1184                         //for each inference phase

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

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

  1187                                 checkWithinBounds(inferenceContext, warn);

  1188                                 continue outer;

  1189                             }

  1190                         }

  1191                         //no progress

  1192                         throw inferenceException.setMessage();

  1193                     }

  1194                 }

  1195                 catch (InferenceException ex) {

  1196                     //did we fail because of interdependent ivars?

  1197                     inferenceContext.rollback(saved_undet);

  1198                     instantiateAsUninferredVars(varsToSolve, inferenceContext);

  1199                     checkWithinBounds(inferenceContext, warn);

  1200                 }

  1201                 inferenceGraph.deleteNode(nodeToSolve);

  1202             }

  1203         }

  1205         /**

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

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

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

  1209          */

  1210         class InferenceGraph {

  1212             /**

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

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

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

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

  1217              * keep dependencies in sync).

  1218              */

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

  1221                 Set<Node> deps;

  1223                 Node(Type ivar) {

  1224                     super(ListBuffer.of(ivar));

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

  1226                 }

  1228                 @Override

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

  1230                     return deps;

  1231                 }

  1233                 @Override

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

  1235                     StringBuilder buf = new StringBuilder();

  1236                     String sep = "";

  1237                     for (Type from : data) {

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

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

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

  1241                                 buf.append(sep);

  1242                                 buf.append(bound);

  1243                                 sep = ",";

  1244                             }

  1245                         }

  1246                     }

  1247                     return buf.toString();

  1248                 }

  1250                 boolean isLeaf(Node n) {

  1251                     //no deps, or only one self dep

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

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

  1254                 }

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

  1257                     for (Node n : nodes) {

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

  1259                         data.appendList(n.data);

  1260                         deps.addAll(n.deps);

  1261                     }

  1262                     //update deps

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

  1264                     for (Node d : deps) {

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

  1266                             deps2.add(this);

  1267                         } else {

  1268                             deps2.add(d);

  1269                         }

  1270                     }

  1271                     deps = deps2;

  1272                 }

  1274                 void graphChanged(Node from, Node to) {

  1275                     if (deps.contains(from)) {

  1276                         deps.remove(from);

  1277                         if (to != null) {

  1278                             deps.add(to);

  1279                         }

  1280                     }

  1281                 }

  1282             }

  1284             /** the nodes in the inference graph */

  1285             ArrayList<Node> nodes;

  1287             InferenceGraph() {

  1288                 initNodes();

  1289             }

  1291             /**

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

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

  1294              */

  1295             public void deleteNode(Node n) {

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

  1297                 nodes.remove(n);

  1298                 notifyUpdate(n, null);

  1299             }

  1301             /**

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

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

  1304              */

  1305             void notifyUpdate(Node from, Node to) {

  1306                 for (Node n : nodes) {

  1307                     n.graphChanged(from, to);

  1308                 }

  1309             }

  1311             /**

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

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

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

  1315                  * created, effectively replacing the original cyclic nodes.

  1316              */

  1317             void initNodes() {

  1318                 nodes = new ArrayList<Node>();

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

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

  1321                 }

  1322                 for (Node n_i : nodes) {

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

  1324                     for (Node n_j : nodes) {

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

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

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

  1328                             //update i's deps

  1329                             n_i.deps.add(n_j);

  1330                         }

  1331                     }

  1332                 }

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

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

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

  1336                         Node root = conSubGraph.head;

  1337                         root.mergeWith(conSubGraph.tail);

  1338                         for (Node n : conSubGraph) {

  1339                             notifyUpdate(n, root);

  1340                         }

  1341                     }

  1342                     acyclicNodes.add(conSubGraph.head);

  1343                 }

  1344                 nodes = acyclicNodes;

  1345             }

  1347             /**

  1348              * Debugging: dot representation of this graph

  1349              */

  1350             String toDot() {

  1351                 StringBuilder buf = new StringBuilder();

  1352                 for (Type t : inferenceContext.undetvars) {

  1353                     UndetVar uv = (UndetVar)t;

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

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

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

  1357                 }

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

  1359             }

  1360         }

  1361     }

  1362     // </editor-fold>

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

  1365     /**

  1366      * Functional interface for defining inference callbacks. Certain actions

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

  1368      * have been fixed.

  1369      */

  1370     interface FreeTypeListener {

  1371         void typesInferred(InferenceContext inferenceContext);

  1372     }

  1374     /**

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

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

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

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

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

  1380      * (see InferenceKind).

  1381      */

  1382      class InferenceContext {

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

  1385         List<Type> undetvars;

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

  1388         List<Type> inferencevars;

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

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

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

  1395         public InferenceContext(List<Type> inferencevars) {

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

  1397             this.inferencevars = inferencevars;

  1398         }

  1399         //where

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

  1401                 // mapping that turns inference variables into undet vars

  1402                 public Type apply(Type t) {

  1403                     if (t.hasTag(TYPEVAR)) {

  1404                         TypeVar tv = (TypeVar)t;

  1405                         return tv.isCaptured() ?

  1406                                 new CapturedUndetVar((CapturedType)tv, types) :

  1407                                 new UndetVar(tv, types);

  1408                     } else {

  1409                         return t.map(this);

  1410                     }

  1411                 }

  1412             };

  1414         /**

  1415          * add a new inference var to this inference context

  1416          */

  1417         void addVar(TypeVar t) {

  1418             this.undetvars = this.undetvars.prepend(fromTypeVarFun.apply(t));

  1419             this.inferencevars = this.inferencevars.prepend(t);

  1420         }

  1422         /**

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

  1424          * inference context

  1425          */

  1426         List<Type> inferenceVars() {

  1427             return inferencevars;

  1428         }

  1430         /**

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

  1432          * inference context

  1433          */

  1434         List<Type> restvars() {

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

  1436                 public boolean accepts(UndetVar uv) {

  1437                     return uv.inst == null;

  1438                 }

  1439             });

  1440         }

  1442         /**

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

  1444          * inference context

  1445          */

  1446         List<Type> instvars() {

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

  1448                 public boolean accepts(UndetVar uv) {

  1449                     return uv.inst != null;

  1450                 }

  1451             });

  1452         }

  1454         /**

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

  1456          * declared bounds).

  1457          */

  1458         final List<Type> boundedVars() {

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

  1460                 public boolean accepts(UndetVar uv) {

  1461                     return uv.getBounds(InferenceBound.UPPER)

  1462                             .diff(uv.getDeclaredBounds())

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

  1464                 }

  1465             });

  1466         }

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

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

  1470             for (Type t : undetvars) {

  1471                 UndetVar uv = (UndetVar)t;

  1472                 if (fu.accepts(uv)) {

  1473                     res.append(uv.qtype);

  1474                 }

  1475             }

  1476             return res.toList();

  1477         }

  1479         /**

  1480          * is this type free?

  1481          */

  1482         final boolean free(Type t) {

  1483             return t.containsAny(inferencevars);

  1484         }

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

  1487             for (Type t : ts) {

  1488                 if (free(t)) return true;

  1489             }

  1490             return false;

  1491         }

  1493         /**

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

  1495          */

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

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

  1498             for (Type iv : inferenceVars()) {

  1499                 if (t.contains(iv)) {

  1500                     buf.add(iv);

  1501                 }

  1502             }

  1503             return buf.toList();

  1504         }

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

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

  1508             for (Type t : ts) {

  1509                 buf.appendList(freeVarsIn(t));

  1510             }

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

  1512             for (Type t : buf) {

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

  1514                     buf2.add(t);

  1515                 }

  1516             }

  1517             return buf2.toList();

  1518         }

  1520         /**

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

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

  1523          * of inference constraints).

  1524          */

  1525         final Type asFree(Type t) {

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

  1527         }

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

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

  1531             for (Type t : ts) {

  1532                 buf.append(asFree(t));

  1533             }

  1534             return buf.toList();

  1535         }

  1537         List<Type> instTypes() {

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

  1539             for (Type t : undetvars) {

  1540                 UndetVar uv = (UndetVar)t;

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

  1542             }

  1543             return buf.toList();

  1544         }

  1546         /**

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

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

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

  1550          */

  1551         Type asInstType(Type t) {

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

  1553         }

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

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

  1557             for (Type t : ts) {

  1558                 buf.append(asInstType(t));

  1559             }

  1560             return buf.toList();

  1561         }

  1563         /**

  1564          * Add custom hook for performing post-inference action

  1565          */

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

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

  1568         }

  1570         /**

  1571          * Mark the inference context as complete and trigger evaluation

  1572          * of all deferred checks.

  1573          */

  1574         void notifyChange() {

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

  1576         }

  1578         void notifyChange(List<Type> inferredVars) {

  1579             InferenceException thrownEx = null;

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

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

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

  1583                     try {

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

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

  1586                     } catch (InferenceException ex) {

  1587                         if (thrownEx == null) {

  1588                             thrownEx = ex;

  1589                         }

  1590                     }

  1591                 }

  1592             }

  1593             //inference exception multiplexing - present any inference exception

  1594             //thrown when processing listeners as a single one

  1595             if (thrownEx != null) {

  1596                 throw thrownEx;

  1597             }

  1598         }

  1600         /**

  1601          * Save the state of this inference context

  1602          */

  1603         List<Type> save() {

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

  1605             for (Type t : undetvars) {

  1606                 UndetVar uv = (UndetVar)t;

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

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

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

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

  1611                     }

  1612                 }

  1613                 uv2.inst = uv.inst;

  1614                 buf.add(uv2);

  1615             }

  1616             return buf.toList();

  1617         }

  1619         /**

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

  1621          */

  1622         void rollback(List<Type> saved_undet) {

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

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

  1625             for (Type t : undetvars) {

  1626                 UndetVar uv = (UndetVar)t;

  1627                 UndetVar uv_saved = (UndetVar)saved_undet.head;

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

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

  1630                 }

  1631                 uv.inst = uv_saved.inst;

  1632                 saved_undet = saved_undet.tail;

  1633             }

  1634         }

  1636         /**

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

  1638          */

  1639         void dupTo(final InferenceContext that) {

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

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

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

  1643             //propagated vars are inferred in new context

  1644             for (Type t : inferencevars) {

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

  1646                     public void typesInferred(InferenceContext inferenceContext) {

  1647                         InferenceContext.this.notifyChange();

  1648                     }

  1649                 }, List.of(t));

  1650             }

  1651         }

  1653         /**

  1654          * Solve with given graph strategy.

  1655          */

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

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

  1658             s.solve(ss);

  1659         }

  1661         /**

  1662          * Solve all variables in this context.

  1663          */

  1664         public void solve(Warner warn) {

  1665             solve(new LeafSolver() {

  1666                 public boolean done() {

  1667                     return restvars().isEmpty();

  1668                 }

  1669             }, warn);

  1670         }

  1672         /**

  1673          * Solve all variables in the given list.

  1674          */

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

  1676             solve(new BestLeafSolver(vars) {

  1677                 public boolean done() {

  1678                     return !free(asInstTypes(vars));

  1679                 }

  1680             }, warn);

  1681         }

  1683         /**

  1684          * Solve at least one variable in given list.

  1685          */

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

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

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

  1689             if (boundedVars.isEmpty()) {

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

  1691                                 freeVarsIn(varsToSolve));

  1692             }

  1693             solve(new BestLeafSolver(boundedVars) {

  1694                 public boolean done() {

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

  1696                 }

  1697             }, warn);

  1698         }

  1700         /**

  1701          * Apply a set of inference steps

  1702          */

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

  1704             return solveBasic(inferencevars, steps);

  1705         }

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

  1708             boolean changed = false;

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

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

  1711                 for (InferenceStep step : steps) {

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

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

  1714                         changed = true;

  1715                         break;

  1716                     }

  1717                 }

  1718             }

  1719             return changed;

  1720         }

  1722         /**

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

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

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

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

  1727          * instantiation, until all variables are solved.

  1728          */

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

  1730             while (true) {

  1731                 boolean stuck = !solveBasic(steps);

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

  1733                     //all variables have been instantiated - exit

  1734                     break;

  1735                 } else if (stuck) {

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

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

  1738                     instantiateAsUninferredVars(restvars(), this);

  1739                     break;

  1740                 } else {

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

  1742                     //variables in remaining upper bounds and continue

  1743                     for (Type t : undetvars) {

  1744                         UndetVar uv = (UndetVar)t;

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

  1746                     }

  1747                 }

  1748             }

  1749             checkWithinBounds(this, warn);

  1750         }

  1752         private Infer infer() {

  1753             //back-door to infer

  1754             return Infer.this;

  1755         }

  1756     }

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

  1759     // </editor-fold>

  1760 }

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

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

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