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

8016267: javac, TypeTag refactoring has provoked performance issues
Reviewed-by: jjg

     1 /*

     2  * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.

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

     4  *

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

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

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

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

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

    10  *

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

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

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

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

    15  * accompanied this code).

    16  *

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

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

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

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

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

    23  * questions.

    24  */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    44 import java.util.HashMap;

    45 import java.util.Map;

    46 import java.util.Set;

    48 import java.util.ArrayList;

    49 import java.util.Collections;

    50 import java.util.EnumSet;

    51 import java.util.HashSet;

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

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

    56  *

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

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

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

    60  *  deletion without notice.</b>

    61  */

    62 public class Infer {

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

    64         new Context.Key<Infer>();

    66     Resolve rs;

    67     Check chk;

    68     Symtab syms;

    69     Types types;

    70     JCDiagnostic.Factory diags;

    71     Log log;

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

    74     boolean allowGraphInference;

    76     public static Infer instance(Context context) {

    77         Infer instance = context.get(inferKey);

    78         if (instance == null)

    79             instance = new Infer(context);

    80         return instance;

    81     }

    83     protected Infer(Context context) {

    84         context.put(inferKey, this);

    86         rs = Resolve.instance(context);

    87         chk = Check.instance(context);

    88         syms = Symtab.instance(context);

    89         types = Types.instance(context);

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

    91         log = Log.instance(context);

    92         inferenceException = new InferenceException(diags);

    93         Options options = Options.instance(context);

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

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

    96     }

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

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

   101    /**

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

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

   104     */

   105     public static class InferenceException extends InapplicableMethodException {

   106         private static final long serialVersionUID = 0;

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

   110         InferenceException(JCDiagnostic.Factory diags) {

   111             super(diags);

   112         }

   114         @Override

   115         InapplicableMethodException setMessage(JCDiagnostic diag) {

   116             messages = messages.append(diag);

   117             return this;

   118         }

   120         @Override

   121         public JCDiagnostic getDiagnostic() {

   122             return messages.head;

   123         }

   125         void clear() {

   126             messages = List.nil();

   127         }

   128     }

   130     protected final InferenceException inferenceException;

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

   133     /**

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

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

   136      */

   137     public Type instantiateMethod(Env<AttrContext> env,

   138                                   List<Type> tvars,

   139                                   MethodType mt,

   140                                   Attr.ResultInfo resultInfo,

   141                                   Symbol msym,

   142                                   List<Type> argtypes,

   143                                   boolean allowBoxing,

   144                                   boolean useVarargs,

   145                                   Resolve.MethodResolutionContext resolveContext,

   146                                   Warner warn) throws InferenceException {

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

   148         final InferenceContext inferenceContext = new InferenceContext(tvars);

   149         inferenceException.clear();

   150         try {

   151             DeferredAttr.DeferredAttrContext deferredAttrContext =

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

   154             resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext,

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

   157             if (allowGraphInference &&

   158                     resultInfo != null &&

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

   160                 //inject return constraints earlier

   161                 checkWithinBounds(inferenceContext, warn); //propagation

   162                 generateReturnConstraints(resultInfo, mt, inferenceContext);

   163                 //propagate outwards if needed

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

   165                     //propagate inference context outwards and exit

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

   167                     deferredAttrContext.complete();

   168                     return mt;

   169                 }

   170             }

   172             deferredAttrContext.complete();

   174             // minimize as yet undetermined type variables

   175             if (allowGraphInference) {

   176                 inferenceContext.solve(warn);

   177             } else {

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

   179             }

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

   183             if (!allowGraphInference &&

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

   185                     resultInfo != null &&

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

   187                 generateReturnConstraints(resultInfo, mt, inferenceContext);

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

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

   190             }

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

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

   194             }

   196             // return instantiated version of method type

   197             return mt;

   198         } finally {

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

   200                 inferenceContext.notifyChange();

   201             } else {

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

   203             }

   204         }

   205     }

   207     /**

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

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

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

   211      */

   212     void generateReturnConstraints(Attr.ResultInfo resultInfo,

   213             MethodType mt, InferenceContext inferenceContext) {

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

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

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

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

   218         //we need to skip capture?

   219         Warner retWarn = new Warner();

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

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

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

   223             throw inferenceException

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

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

   226         }

   227     }

   228     //where

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

   230             if (from.hasTag(VOID)) {

   231                 return syms.voidType;

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

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

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

   235                 if (!allowGraphInference) {

   236                     //if legacy, just return boxed type

   237                     return types.boxedClass(to).type;

   238                 }

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

   240                 UndetVar uv = (UndetVar)from;

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

   242                     Type boundAsPrimitive = types.unboxedType(t);

   243                     if (boundAsPrimitive == null) continue;

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

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

   246                         return syms.objectType;

   247                     }

   248                 }

   249                 return types.boxedClass(to).type;

   250             } else {

   251                 return to;

   252             }

   253         }

   255     /**

   256       * Infer cyclic inference variables as described in 15.12.2.8.

   257       */

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

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

   260         //step 1 - create fresh tvars

   261         for (Type t : vars) {

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

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

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

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

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

   267                 todo.append(uv);

   268                 uv.inst = fresh_tvar.type;

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

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

   271             } else {

   272                 uv.inst = syms.objectType;

   273             }

   274         }

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

   276         List<Type> formals = vars;

   277         for (Type t : todo) {

   278             UndetVar uv = (UndetVar)t;

   279             TypeVar ct = (TypeVar)uv.inst;

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

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

   282                 //report inference error if glb fails

   283                 reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   284             }

   285             formals = formals.tail;

   286         }

   287     }

   289     /**

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

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

   292      * enclosing scope surrounding the polymorphic-signature call.

   293      */

   294     Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,

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

   296                                             Resolve.MethodResolutionContext resolveContext,

   297                                             List<Type> argtypes) {

   298         final Type restype;

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

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

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

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

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

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

   306         //the polymorphic signature call environment is nested.

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

   309             case TYPECAST:

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

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

   312                     castTree.clazz.type :

   313                     syms.objectType;

   314                 break;

   315             case EXEC:

   316                 JCTree.JCExpressionStatement execTree =

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

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

   319                     syms.voidType :

   320                     syms.objectType;

   321                 break;

   322             default:

   323                 restype = syms.objectType;

   324         }

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

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

   328             spMethod.getThrownTypes() :

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

   331         MethodType mtype = new MethodType(paramtypes,

   332                                           restype,

   333                                           exType,

   334                                           syms.methodClass);

   335         return mtype;

   336     }

   337     //where

   338         class ImplicitArgType extends DeferredAttr.DeferredTypeMap {

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

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

   342             }

   344             public Type apply(Type t) {

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

   346                 if (t.hasTag(BOT))

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

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

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

   350                 return t;

   351             }

   352         }

   354     /**

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

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

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

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

   359       */

   360     public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,

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

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

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

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

   365             return funcInterface;

   366         } else {

   367             Type formalInterface = funcInterface.tsym.type;

   368             InferenceContext funcInterfaceContext =

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

   371             Assert.check(paramTypes != null);

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

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

   374             //in the functional interface descriptors)

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

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

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

   378                 return types.createErrorType(funcInterface);

   379             }

   380             for (Type p : descParameterTypes) {

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

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

   383                     return types.createErrorType(funcInterface);

   384                 }

   385                 paramTypes = paramTypes.tail;

   386             }

   388             try {

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

   390             } catch (InferenceException ex) {

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

   392             }

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

   395             for (Type t : funcInterfaceContext.undetvars) {

   396                 UndetVar uv = (UndetVar)t;

   397                 if (uv.inst == null) {

   398                     uv.inst = actualTypeargs.head;

   399                 }

   400                 actualTypeargs = actualTypeargs.tail;

   401             }

   403             Type owntype = funcInterfaceContext.asInstType(formalInterface);

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

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

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

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

   408             }

   409             return owntype;

   410         }

   411     }

   412     // </editor-fold>

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

   415     /**

   416      * Check bounds and perform incorporation

   417      */

   418     void checkWithinBounds(InferenceContext inferenceContext,

   419                              Warner warn) throws InferenceException {

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

   421         try {

   422             while (true) {

   423                 mlistener.reset();

   424                 if (!allowGraphInference) {

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

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

   427                     for (Type t : inferenceContext.undetvars) {

   428                         UndetVar uv = (UndetVar)t;

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

   430                     }

   431                 }

   432                 for (Type t : inferenceContext.undetvars) {

   433                     UndetVar uv = (UndetVar)t;

   434                     //bound incorporation

   435                     EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?

   436                             incorporationStepsGraph : incorporationStepsLegacy;

   437                     for (IncorporationStep is : incorporationSteps) {

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

   439                     }

   440                 }

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

   442             }

   443         }

   444         finally {

   445             mlistener.detach();

   446         }

   447     }

   448     //where

   449         /**

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

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

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

   453          * left in a clean state.

   454          */

   455         class MultiUndetVarListener implements UndetVar.UndetVarListener {

   457             int rounds;

   458             boolean changed;

   459             List<Type> undetvars;

   461             public MultiUndetVarListener(List<Type> undetvars) {

   462                 this.undetvars = undetvars;

   463                 for (Type t : undetvars) {

   464                     UndetVar uv = (UndetVar)t;

   465                     uv.listener = this;

   466                 }

   467             }

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

   470                 //avoid non-termination

   471                 if (rounds < MAX_INCORPORATION_STEPS) {

   472                     changed = true;

   473                 }

   474             }

   476             void reset() {

   477                 rounds++;

   478                 changed = false;

   479             }

   481             void detach() {

   482                 for (Type t : undetvars) {

   483                     UndetVar uv = (UndetVar)t;

   484                     uv.listener = null;

   485                 }

   486             }

   487         };

   489         /** max number of incorporation rounds */

   490         static final int MAX_INCORPORATION_STEPS = 100;

   492     /**

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

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

   495      * logic into the basic bound checking routine

   496      */

   497     enum IncorporationStep {

   498         /**

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

   500          * inference variable compatible with its bounds?

   501          */

   502         CHECK_BOUNDS() {

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

   504                 Infer infer = inferenceContext.infer();

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

   506                 infer.checkCompatibleUpperBounds(uv, inferenceContext);

   507                 if (uv.inst != null) {

   508                     Type inst = uv.inst;

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

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

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

   512                         }

   513                     }

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

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

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

   517                         }

   518                     }

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

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

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

   522                         }

   523                     }

   524                 }

   525             }

   526         },

   527         /**

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

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

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

   531          */

   532         EQ_CHECK_LEGACY() {

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

   534                 Infer infer = inferenceContext.infer();

   535                 Type eq = null;

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

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

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

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

   540                     }

   541                     eq = e;

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

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

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

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

   546                         }

   547                     }

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

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

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

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

   552                         }

   553                     }

   554                 }

   555             }

   556         },

   557         /**

   558          * Check consistency of equality constraints.

   559          */

   560         EQ_CHECK() {

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

   562                 Infer infer = inferenceContext.infer();

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

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

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

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

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

   568                         }

   569                     }

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

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

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

   573                         }

   574                     }

   575                 }

   576             }

   577         },

   578         /**

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

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

   581          */

   582         CROSS_UPPER_LOWER() {

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

   584                 Infer infer = inferenceContext.infer();

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

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

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

   588                     }

   589                 }

   590             }

   591         },

   592         /**

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

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

   595          */

   596         CROSS_UPPER_EQ() {

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

   598                 Infer infer = inferenceContext.infer();

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

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

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

   602                     }

   603                 }

   604             }

   605         },

   606         /**

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

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

   609          */

   610         CROSS_EQ_LOWER() {

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

   612                 Infer infer = inferenceContext.infer();

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

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

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

   616                     }

   617                 }

   618             }

   619         },

   620         /**

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

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

   623          */

   624         CROSS_EQ_EQ() {

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

   626                 Infer infer = inferenceContext.infer();

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

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

   629                         if (b1 != b2) {

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

   631                         }

   632                     }

   633                 }

   634             }

   635         },

   636         /**

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

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

   639          */

   640         PROP_UPPER() {

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

   642                 Infer infer = inferenceContext.infer();

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

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

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

   646                         //alpha <: beta

   647                         //0. set beta :> alpha

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

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

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

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

   652                         }

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

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

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

   656                         }

   657                     }

   658                 }

   659             }

   660         },

   661         /**

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

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

   664          */

   665         PROP_LOWER() {

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

   667                 Infer infer = inferenceContext.infer();

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

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

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

   671                         //alpha :> beta

   672                         //0. set beta <: alpha

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

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

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

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

   677                         }

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

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

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

   681                         }

   682                     }

   683                 }

   684             }

   685         },

   686         /**

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

   688          * bounds from alpha to beta and back.

   689          */

   690         PROP_EQ() {

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

   692                 Infer infer = inferenceContext.infer();

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

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

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

   696                         //alpha == beta

   697                         //0. set beta == alpha

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

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

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

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

   702                                 if (b2 != uv2) {

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

   704                                 }

   705                             }

   706                         }

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

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

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

   710                                 if (b2 != uv) {

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

   712                                 }

   713                             }

   714                         }

   715                     }

   716                 }

   717             }

   718         };

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

   721     }

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

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

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

   727     EnumSet<IncorporationStep> incorporationStepsGraph =

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

   730     /**

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

   732      * variable by making sure that a glb exists.

   733      */

   734     void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {

   735         List<Type> hibounds =

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

   737         Type hb = null;

   738         if (hibounds.isEmpty())

   739             hb = syms.objectType;

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

   741             hb = hibounds.head;

   742         else

   743             hb = types.glb(hibounds);

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

   745             reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   746     }

   747     //where

   748         protected static class BoundFilter implements Filter<Type> {

   750             InferenceContext inferenceContext;

   752             public BoundFilter(InferenceContext inferenceContext) {

   753                 this.inferenceContext = inferenceContext;

   754             }

   756             @Override

   757             public boolean accepts(Type t) {

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

   759                         !t.hasTag(BOT);

   760             }

   761         };

   763     /**

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

   765      */

   766     enum BoundErrorKind {

   767         /**

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

   769          */

   770         BAD_UPPER() {

   771             @Override

   772             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   774                         uv.getBounds(InferenceBound.UPPER));

   775             }

   776         },

   777         /**

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

   779          */

   780         BAD_EQ_UPPER() {

   781             @Override

   782             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   785             }

   786         },

   787         /**

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

   789          */

   790         BAD_EQ_LOWER() {

   791             @Override

   792             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   795             }

   796         },

   797         /**

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

   799          */

   800         UPPER() {

   801             @Override

   802             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   804                         uv.getBounds(InferenceBound.UPPER));

   805             }

   806         },

   807         /**

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

   809          */

   810         LOWER() {

   811             @Override

   812             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   814                         uv.getBounds(InferenceBound.LOWER));

   815             }

   816         },

   817         /**

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

   819          */

   820         EQ() {

   821             @Override

   822             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   824                         uv.getBounds(InferenceBound.EQ));

   825             }

   826         };

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

   829     }

   831     /**

   832      * Report a bound-checking error of given kind

   833      */

   834     void reportBoundError(UndetVar uv, BoundErrorKind bk) {

   835         throw bk.setMessage(inferenceException, uv);

   836     }

   837     // </editor-fold>

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

   840     /**

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

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

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

   844      */

   845     interface GraphStrategy {

   846         /**

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

   848          */

   849         Node pickNode(InferenceGraph g);

   850         /**

   851          * Is this the last step?

   852          */

   853         boolean done();

   854     }

   856     /**

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

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

   859      */

   860     abstract class LeafSolver implements GraphStrategy {

   861         public Node pickNode(InferenceGraph g) {

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

   863             return g.nodes.get(0);

   864         }

   865     }

   867     /**

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

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

   870      * or more inference variables in a given list

   871      */

   872     abstract class BestLeafSolver extends LeafSolver {

   874         List<Type> varsToSolve;

   876         BestLeafSolver(List<Type> varsToSolve) {

   877             this.varsToSolve = varsToSolve;

   878         }

   880         /**

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

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

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

   884          * a given node

   885          */

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

   887             if (costMap.containsKey(n)) {

   888                 return;

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

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

   891             } else {

   892                 int subcost = Integer.MAX_VALUE;

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

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

   895                     computeCostIfNeeded(n2, costMap);

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

   897                 }

   898                 //update cost map to reflect real cost

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

   900                         Integer.MAX_VALUE :

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

   902             }

   903         }

   905         /**

   906          * Pick the leaf that minimize cost

   907          */

   908         @Override

   909         public Node pickNode(final InferenceGraph g) {

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

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

   912             for (Node n : g.nodes) {

   913                 computeCostIfNeeded(n, costMap);

   914                 if (n.isLeaf(n)) {

   915                     leaves.add(n);

   916                 }

   917             }

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

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

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

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

   922                 }

   923             });

   924             return leaves.get(0);

   925         }

   926     }

   928     /**

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

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

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

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

   933      */

   934     enum InferenceStep {

   936         /**

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

   938          * constraints

   939          */

   940         EQ(InferenceBound.EQ) {

   941             @Override

   942             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   943                 return filterBounds(uv, inferenceContext).head;

   944             }

   945         },

   946         /**

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

   948          * bounds are merged together using lub().

   949          */

   950         LOWER(InferenceBound.LOWER) {

   951             @Override

   952             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   953                 Infer infer = inferenceContext.infer();

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

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

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

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

   958                     throw infer.inferenceException

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

   960                                     uv.qtype, lobounds);

   961                 } else {

   962                     return owntype;

   963                 }

   964             }

   965         },

   966         /**

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

   968          * bounds are merged together using glb().

   969          */

   970         UPPER(InferenceBound.UPPER) {

   971             @Override

   972             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   973                 Infer infer = inferenceContext.infer();

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

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

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

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

   978                     throw infer.inferenceException

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

   980                                     uv.qtype, hibounds);

   981                 } else {

   982                     return owntype;

   983                 }

   984             }

   985         },

   986         /**

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

   988          * if all upper bounds are ground.

   989          */

   990         UPPER_LEGACY(InferenceBound.UPPER) {

   991             @Override

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

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

   994             }

   996             @Override

   997             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   998                 return UPPER.solve(uv, inferenceContext);

   999             }

  1000         };

  1002         final InferenceBound ib;

  1004         InferenceStep(InferenceBound ib) {

  1005             this.ib = ib;

  1006         }

  1008         /**

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

  1010          * a given inference context

  1011          */

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

  1014         /**

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

  1016          */

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

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

  1019         }

  1021         /**

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

  1023          */

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

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

  1026         }

  1027     }

  1029     /**

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

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

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

  1033      */

  1034     enum LegacyInferenceSteps {

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

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

  1039         final EnumSet<InferenceStep> steps;

  1041         LegacyInferenceSteps(EnumSet<InferenceStep> steps) {

  1042             this.steps = steps;

  1043         }

  1044     }

  1046     /**

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

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

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

  1050      */

  1051     enum GraphInferenceSteps {

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

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

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

  1057         final EnumSet<InferenceStep> steps;

  1059         GraphInferenceSteps(EnumSet<InferenceStep> steps) {

  1060             this.steps = steps;

  1061         }

  1062     }

  1064     /**

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

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

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

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

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

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

  1071      */

  1072     class GraphSolver {

  1074         InferenceContext inferenceContext;

  1075         Warner warn;

  1077         GraphSolver(InferenceContext inferenceContext, Warner warn) {

  1078             this.inferenceContext = inferenceContext;

  1079             this.warn = warn;

  1080         }

  1082         /**

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

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

  1085          * depends on the selected solver strategy.

  1086          */

  1087         void solve(GraphStrategy sstrategy) {

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

  1089             InferenceGraph inferenceGraph = new InferenceGraph();

  1090             while (!sstrategy.done()) {

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

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

  1093                 inferenceContext.save();

  1094                 try {

  1095                     //repeat until all variables are solved

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

  1097                         //for each inference phase

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

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

  1100                                 checkWithinBounds(inferenceContext, warn);

  1101                                 continue outer;

  1102                             }

  1103                         }

  1104                         //no progress

  1105                         throw inferenceException.setMessage();

  1106                     }

  1107                 }

  1108                 catch (InferenceException ex) {

  1109                     //did we fail because of interdependent ivars?

  1110                     inferenceContext.rollback();

  1111                     instantiateAsUninferredVars(varsToSolve, inferenceContext);

  1112                     checkWithinBounds(inferenceContext, warn);

  1113                 }

  1114                 inferenceGraph.deleteNode(nodeToSolve);

  1115             }

  1116         }

  1118         /**

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

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

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

  1122          */

  1123         class InferenceGraph {

  1125             /**

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

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

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

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

  1130              * keep dependencies in sync).

  1131              */

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

  1134                 Set<Node> deps;

  1136                 Node(Type ivar) {

  1137                     super(ListBuffer.of(ivar));

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

  1139                 }

  1141                 @Override

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

  1143                     return deps;

  1144                 }

  1146                 @Override

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

  1148                     StringBuilder buf = new StringBuilder();

  1149                     String sep = "";

  1150                     for (Type from : data) {

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

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

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

  1154                                 buf.append(sep);

  1155                                 buf.append(bound);

  1156                                 sep = ",";

  1157                             }

  1158                         }

  1159                     }

  1160                     return buf.toString();

  1161                 }

  1163                 boolean isLeaf(Node n) {

  1164                     //no deps, or only one self dep

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

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

  1167                 }

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

  1170                     for (Node n : nodes) {

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

  1172                         data.appendList(n.data);

  1173                         deps.addAll(n.deps);

  1174                     }

  1175                     //update deps

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

  1177                     for (Node d : deps) {

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

  1179                             deps2.add(this);

  1180                         } else {

  1181                             deps2.add(d);

  1182                         }

  1183                     }

  1184                     deps = deps2;

  1185                 }

  1187                 void graphChanged(Node from, Node to) {

  1188                     if (deps.contains(from)) {

  1189                         deps.remove(from);

  1190                         if (to != null) {

  1191                             deps.add(to);

  1192                         }

  1193                     }

  1194                 }

  1195             }

  1197             /** the nodes in the inference graph */

  1198             ArrayList<Node> nodes;

  1200             InferenceGraph() {

  1201                 initNodes();

  1202             }

  1204             /**

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

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

  1207              */

  1208             public void deleteNode(Node n) {

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

  1210                 nodes.remove(n);

  1211                 notifyUpdate(n, null);

  1212             }

  1214             /**

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

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

  1217              */

  1218             void notifyUpdate(Node from, Node to) {

  1219                 for (Node n : nodes) {

  1220                     n.graphChanged(from, to);

  1221                 }

  1222             }

  1224             /**

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

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

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

  1228                  * created, effectively replacing the original cyclic nodes.

  1229              */

  1230             void initNodes() {

  1231                 nodes = new ArrayList<Node>();

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

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

  1234                 }

  1235                 for (Node n_i : nodes) {

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

  1237                     for (Node n_j : nodes) {

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

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

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

  1241                             //update i's deps

  1242                             n_i.deps.add(n_j);

  1243                         }

  1244                     }

  1245                 }

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

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

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

  1249                         Node root = conSubGraph.head;

  1250                         root.mergeWith(conSubGraph.tail);

  1251                         for (Node n : conSubGraph) {

  1252                             notifyUpdate(n, root);

  1253                         }

  1254                     }

  1255                     acyclicNodes.add(conSubGraph.head);

  1256                 }

  1257                 nodes = acyclicNodes;

  1258             }

  1260             /**

  1261              * Debugging: dot representation of this graph

  1262              */

  1263             String toDot() {

  1264                 StringBuilder buf = new StringBuilder();

  1265                 for (Type t : inferenceContext.undetvars) {

  1266                     UndetVar uv = (UndetVar)t;

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

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

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

  1270                 }

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

  1272             }

  1273         }

  1274     }

  1275     // </editor-fold>

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

  1278     /**

  1279      * Functional interface for defining inference callbacks. Certain actions

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

  1281      * have been fixed.

  1282      */

  1283     interface FreeTypeListener {

  1284         void typesInferred(InferenceContext inferenceContext);

  1285     }

  1287     /**

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

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

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

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

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

  1293      * (see InferenceKind).

  1294      */

  1295      class InferenceContext {

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

  1298         List<Type> undetvars;

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

  1301         List<Type> inferencevars;

  1303         /** backed up inference variables */

  1304         List<Type> saved_undet;

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

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

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

  1311         public InferenceContext(List<Type> inferencevars) {

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

  1313             this.inferencevars = inferencevars;

  1314         }

  1315         //where

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

  1317                 // mapping that turns inference variables into undet vars

  1318                 public Type apply(Type t) {

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

  1320                     else return t.map(this);

  1321                 }

  1322             };

  1324         /**

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

  1326          * inference context

  1327          */

  1328         List<Type> inferenceVars() {

  1329             return inferencevars;

  1330         }

  1332         /**

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

  1334          * inference context

  1335          */

  1336         List<Type> restvars() {

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

  1338                 public boolean accepts(UndetVar uv) {

  1339                     return uv.inst == null;

  1340                 }

  1341             });

  1342         }

  1344         /**

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

  1346          * inference context

  1347          */

  1348         List<Type> instvars() {

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

  1350                 public boolean accepts(UndetVar uv) {

  1351                     return uv.inst != null;

  1352                 }

  1353             });

  1354         }

  1356         /**

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

  1358          * declared bounds).

  1359          */

  1360         final List<Type> boundedVars() {

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

  1362                 public boolean accepts(UndetVar uv) {

  1363                     return uv.getBounds(InferenceBound.UPPER)

  1364                             .diff(uv.getDeclaredBounds())

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

  1366                 }

  1367             });

  1368         }

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

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

  1372             for (Type t : undetvars) {

  1373                 UndetVar uv = (UndetVar)t;

  1374                 if (fu.accepts(uv)) {

  1375                     res.append(uv.qtype);

  1376                 }

  1377             }

  1378             return res.toList();

  1379         }

  1381         /**

  1382          * is this type free?

  1383          */

  1384         final boolean free(Type t) {

  1385             return t.containsAny(inferencevars);

  1386         }

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

  1389             for (Type t : ts) {

  1390                 if (free(t)) return true;

  1391             }

  1392             return false;

  1393         }

  1395         /**

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

  1397          */

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

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

  1400             for (Type iv : inferenceVars()) {

  1401                 if (t.contains(iv)) {

  1402                     buf.add(iv);

  1403                 }

  1404             }

  1405             return buf.toList();

  1406         }

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

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

  1410             for (Type t : ts) {

  1411                 buf.appendList(freeVarsIn(t));

  1412             }

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

  1414             for (Type t : buf) {

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

  1416                     buf2.add(t);

  1417                 }

  1418             }

  1419             return buf2.toList();

  1420         }

  1422         /**

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

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

  1425          * of inference constraints).

  1426          */

  1427         final Type asFree(Type t) {

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

  1429         }

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

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

  1433             for (Type t : ts) {

  1434                 buf.append(asFree(t));

  1435             }

  1436             return buf.toList();

  1437         }

  1439         List<Type> instTypes() {

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

  1441             for (Type t : undetvars) {

  1442                 UndetVar uv = (UndetVar)t;

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

  1444             }

  1445             return buf.toList();

  1446         }

  1448         /**

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

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

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

  1452          */

  1453         Type asInstType(Type t) {

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

  1455         }

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

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

  1459             for (Type t : ts) {

  1460                 buf.append(asInstType(t));

  1461             }

  1462             return buf.toList();

  1463         }

  1465         /**

  1466          * Add custom hook for performing post-inference action

  1467          */

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

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

  1470         }

  1472         /**

  1473          * Mark the inference context as complete and trigger evaluation

  1474          * of all deferred checks.

  1475          */

  1476         void notifyChange() {

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

  1478         }

  1480         void notifyChange(List<Type> inferredVars) {

  1481             InferenceException thrownEx = null;

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

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

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

  1485                     try {

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

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

  1488                     } catch (InferenceException ex) {

  1489                         if (thrownEx == null) {

  1490                             thrownEx = ex;

  1491                         }

  1492                     }

  1493                 }

  1494             }

  1495             //inference exception multiplexing - present any inference exception

  1496             //thrown when processing listeners as a single one

  1497             if (thrownEx != null) {

  1498                 throw thrownEx;

  1499             }

  1500         }

  1502         /**

  1503          * Save the state of this inference context

  1504          */

  1505         void save() {

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

  1507             for (Type t : undetvars) {

  1508                 UndetVar uv = (UndetVar)t;

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

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

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

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

  1513                     }

  1514                 }

  1515                 uv2.inst = uv.inst;

  1516                 buf.add(uv2);

  1517             }

  1518             saved_undet = buf.toList();

  1519         }

  1521         /**

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

  1523          */

  1524         void rollback() {

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

  1526             undetvars = saved_undet;

  1527             saved_undet = null;

  1528         }

  1530         /**

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

  1532          */

  1533         void dupTo(final InferenceContext that) {

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

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

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

  1537             //propagated vars are inferred in new context

  1538             for (Type t : inferencevars) {

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

  1540                     public void typesInferred(InferenceContext inferenceContext) {

  1541                         InferenceContext.this.notifyChange();

  1542                     }

  1543                 }, List.of(t));

  1544             }

  1545         }

  1547         /**

  1548          * Solve with given graph strategy.

  1549          */

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

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

  1552             s.solve(ss);

  1553         }

  1555         /**

  1556          * Solve all variables in this context.

  1557          */

  1558         public void solve(Warner warn) {

  1559             solve(new LeafSolver() {

  1560                 public boolean done() {

  1561                     return restvars().isEmpty();

  1562                 }

  1563             }, warn);

  1564         }

  1566         /**

  1567          * Solve all variables in the given list.

  1568          */

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

  1570             solve(new BestLeafSolver(vars) {

  1571                 public boolean done() {

  1572                     return !free(asInstTypes(vars));

  1573                 }

  1574             }, warn);

  1575         }

  1577         /**

  1578          * Solve at least one variable in given list.

  1579          */

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

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

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

  1583             if (boundedVars.isEmpty()) {

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

  1585                                 freeVarsIn(varsToSolve));

  1586             }

  1587             solve(new BestLeafSolver(boundedVars) {

  1588                 public boolean done() {

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

  1590                 }

  1591             }, warn);

  1592         }

  1594         /**

  1595          * Apply a set of inference steps

  1596          */

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

  1598             return solveBasic(inferencevars, steps);

  1599         }

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

  1602             boolean changed = false;

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

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

  1605                 for (InferenceStep step : steps) {

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

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

  1608                         changed = true;

  1609                         break;

  1610                     }

  1611                 }

  1612             }

  1613             return changed;

  1614         }

  1616         /**

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

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

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

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

  1621          * instantiation, until all variables are solved.

  1622          */

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

  1624             while (true) {

  1625                 boolean stuck = !solveBasic(steps);

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

  1627                     //all variables have been instantiated - exit

  1628                     break;

  1629                 } else if (stuck) {

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

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

  1632                     instantiateAsUninferredVars(restvars(), this);

  1633                     break;

  1634                 } else {

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

  1636                     //variables in remaining upper bounds and continue

  1637                     for (Type t : undetvars) {

  1638                         UndetVar uv = (UndetVar)t;

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

  1640                     }

  1641                 }

  1642             }

  1643             checkWithinBounds(this, warn);

  1644         }

  1646         private Infer infer() {

  1647             //back-door to infer

  1648             return Infer.this;

  1649         }

  1650     }

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

  1653     // </editor-fold>

  1654 }

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

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

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