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

8008723: Graph Inference: bad graph calculation leads to assertion error
Summary: Dependencies are not propagated correctly through merged nodes during inference graph initialization
Reviewed-by: jjg

     1 /*

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

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

     4  *

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

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

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

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

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

    10  *

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

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

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

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

    15  * accompanied this code).

    16  *

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

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

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

    20  *

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

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

    23  * questions.

    24  */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    44 import java.util.HashMap;

    45 import java.util.Map;

    46 import java.util.Set;

    48 import java.util.ArrayList;

    49 import java.util.Collections;

    50 import java.util.EnumSet;

    51 import java.util.HashSet;

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

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

    56  *

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

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

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

    60  *  deletion without notice.</b>

    61  */

    62 public class Infer {

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

    64         new Context.Key<Infer>();

    66     Resolve rs;

    67     Check chk;

    68     Symtab syms;

    69     Types types;

    70     JCDiagnostic.Factory diags;

    71     Log log;

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

    74     boolean allowGraphInference;

    76     public static Infer instance(Context context) {

    77         Infer instance = context.get(inferKey);

    78         if (instance == null)

    79             instance = new Infer(context);

    80         return instance;

    81     }

    83     protected Infer(Context context) {

    84         context.put(inferKey, this);

    86         rs = Resolve.instance(context);

    87         chk = Check.instance(context);

    88         syms = Symtab.instance(context);

    89         types = Types.instance(context);

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

    91         log = Log.instance(context);

    92         inferenceException = new InferenceException(diags);

    93         Options options = Options.instance(context);

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

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

    96     }

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

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

   101    /**

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

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

   104     */

   105     public static class InferenceException extends InapplicableMethodException {

   106         private static final long serialVersionUID = 0;

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

   110         InferenceException(JCDiagnostic.Factory diags) {

   111             super(diags);

   112         }

   114         @Override

   115         InapplicableMethodException setMessage(JCDiagnostic diag) {

   116             messages = messages.append(diag);

   117             return this;

   118         }

   120         @Override

   121         public JCDiagnostic getDiagnostic() {

   122             return messages.head;

   123         }

   125         void clear() {

   126             messages = List.nil();

   127         }

   128     }

   130     protected final InferenceException inferenceException;

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

   133     /**

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

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

   136      */

   137     public Type instantiateMethod(Env<AttrContext> env,

   138                                   List<Type> tvars,

   139                                   MethodType mt,

   140                                   Attr.ResultInfo resultInfo,

   141                                   Symbol msym,

   142                                   List<Type> argtypes,

   143                                   boolean allowBoxing,

   144                                   boolean useVarargs,

   145                                   Resolve.MethodResolutionContext resolveContext,

   146                                   Resolve.MethodCheck methodCheck,

   147                                   Warner warn) throws InferenceException {

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

   149         final InferenceContext inferenceContext = new InferenceContext(tvars);

   150         inferenceException.clear();

   151         try {

   152             DeferredAttr.DeferredAttrContext deferredAttrContext =

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

   155             methodCheck.argumentsAcceptable(env, deferredAttrContext,

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

   158             if (allowGraphInference &&

   159                     resultInfo != null &&

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

   161                 //inject return constraints earlier

   162                 checkWithinBounds(inferenceContext, warn); //propagation

   163                 generateReturnConstraints(resultInfo, mt, inferenceContext);

   164                 //propagate outwards if needed

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

   166                     //propagate inference context outwards and exit

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

   168                     deferredAttrContext.complete();

   169                     return mt;

   170                 }

   171             }

   173             deferredAttrContext.complete();

   175             // minimize as yet undetermined type variables

   176             if (allowGraphInference) {

   177                 inferenceContext.solve(warn);

   178             } else {

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

   180             }

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

   184             if (!allowGraphInference &&

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

   186                     resultInfo != null &&

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

   188                 generateReturnConstraints(resultInfo, mt, inferenceContext);

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

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

   191             }

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

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

   195             }

   197             // return instantiated version of method type

   198             return mt;

   199         } finally {

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

   201                 inferenceContext.notifyChange();

   202             } else {

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

   204             }

   205         }

   206     }

   208     /**

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

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

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

   212      */

   213     void generateReturnConstraints(Attr.ResultInfo resultInfo,

   214             MethodType mt, InferenceContext inferenceContext) {

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

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

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

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

   219         //we need to skip capture?

   220         Warner retWarn = new Warner();

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

   222                 //unchecked conversion is not allowed

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

   224             throw inferenceException

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

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

   227         }

   228     }

   229     //where

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

   231             if (from.hasTag(VOID)) {

   232                 return syms.voidType;

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

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

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

   236                 if (!allowGraphInference) {

   237                     //if legacy, just return boxed type

   238                     return types.boxedClass(to).type;

   239                 }

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

   241                 UndetVar uv = (UndetVar)from;

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

   243                     Type boundAsPrimitive = types.unboxedType(t);

   244                     if (boundAsPrimitive == null) continue;

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

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

   247                         return syms.objectType;

   248                     }

   249                 }

   250                 return types.boxedClass(to).type;

   251             } else {

   252                 return to;

   253             }

   254         }

   256     /**

   257       * Infer cyclic inference variables as described in 15.12.2.8.

   258       */

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

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

   261         //step 1 - create fresh tvars

   262         for (Type t : vars) {

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

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

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

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

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

   268                 todo.append(uv);

   269                 uv.inst = fresh_tvar.type;

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

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

   272             } else {

   273                 uv.inst = syms.objectType;

   274             }

   275         }

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

   277         List<Type> formals = vars;

   278         for (Type t : todo) {

   279             UndetVar uv = (UndetVar)t;

   280             TypeVar ct = (TypeVar)uv.inst;

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

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

   283                 //report inference error if glb fails

   284                 reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   285             }

   286             formals = formals.tail;

   287         }

   288     }

   290     /**

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

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

   293      * enclosing scope surrounding the polymorphic-signature call.

   294      */

   295     Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,

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

   297                                             Resolve.MethodResolutionContext resolveContext,

   298                                             List<Type> argtypes) {

   299         final Type restype;

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

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

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

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

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

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

   307         //the polymorphic signature call environment is nested.

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

   310             case TYPECAST:

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

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

   313                     castTree.clazz.type :

   314                     syms.objectType;

   315                 break;

   316             case EXEC:

   317                 JCTree.JCExpressionStatement execTree =

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

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

   320                     syms.voidType :

   321                     syms.objectType;

   322                 break;

   323             default:

   324                 restype = syms.objectType;

   325         }

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

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

   329             spMethod.getThrownTypes() :

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

   332         MethodType mtype = new MethodType(paramtypes,

   333                                           restype,

   334                                           exType,

   335                                           syms.methodClass);

   336         return mtype;

   337     }

   338     //where

   339         class ImplicitArgType extends DeferredAttr.DeferredTypeMap {

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

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

   343             }

   345             public Type apply(Type t) {

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

   347                 if (t.hasTag(BOT))

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

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

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

   351                 return t;

   352             }

   353         }

   355     /**

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

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

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

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

   360       */

   361     public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,

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

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

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

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

   366             return funcInterface;

   367         } else {

   368             Type formalInterface = funcInterface.tsym.type;

   369             InferenceContext funcInterfaceContext =

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

   372             Assert.check(paramTypes != null);

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

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

   375             //in the functional interface descriptors)

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

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

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

   379                 return types.createErrorType(funcInterface);

   380             }

   381             for (Type p : descParameterTypes) {

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

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

   384                     return types.createErrorType(funcInterface);

   385                 }

   386                 paramTypes = paramTypes.tail;

   387             }

   389             try {

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

   391             } catch (InferenceException ex) {

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

   393             }

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

   396             for (Type t : funcInterfaceContext.undetvars) {

   397                 UndetVar uv = (UndetVar)t;

   398                 if (uv.inst == null) {

   399                     uv.inst = actualTypeargs.head;

   400                 }

   401                 actualTypeargs = actualTypeargs.tail;

   402             }

   404             Type owntype = funcInterfaceContext.asInstType(formalInterface);

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

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

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

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

   409             }

   410             return owntype;

   411         }

   412     }

   413     // </editor-fold>

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

   416     /**

   417      * Check bounds and perform incorporation

   418      */

   419     void checkWithinBounds(InferenceContext inferenceContext,

   420                              Warner warn) throws InferenceException {

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

   422         try {

   423             while (true) {

   424                 mlistener.reset();

   425                 if (!allowGraphInference) {

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

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

   428                     for (Type t : inferenceContext.undetvars) {

   429                         UndetVar uv = (UndetVar)t;

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

   431                     }

   432                 }

   433                 for (Type t : inferenceContext.undetvars) {

   434                     UndetVar uv = (UndetVar)t;

   435                     //bound incorporation

   436                     EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?

   437                             incorporationStepsGraph : incorporationStepsLegacy;

   438                     for (IncorporationStep is : incorporationSteps) {

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

   440                     }

   441                 }

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

   443             }

   444         }

   445         finally {

   446             mlistener.detach();

   447         }

   448     }

   449     //where

   450         /**

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

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

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

   454          * left in a clean state.

   455          */

   456         class MultiUndetVarListener implements UndetVar.UndetVarListener {

   458             int rounds;

   459             boolean changed;

   460             List<Type> undetvars;

   462             public MultiUndetVarListener(List<Type> undetvars) {

   463                 this.undetvars = undetvars;

   464                 for (Type t : undetvars) {

   465                     UndetVar uv = (UndetVar)t;

   466                     uv.listener = this;

   467                 }

   468             }

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

   471                 //avoid non-termination

   472                 if (rounds < MAX_INCORPORATION_STEPS) {

   473                     changed = true;

   474                 }

   475             }

   477             void reset() {

   478                 rounds++;

   479                 changed = false;

   480             }

   482             void detach() {

   483                 for (Type t : undetvars) {

   484                     UndetVar uv = (UndetVar)t;

   485                     uv.listener = null;

   486                 }

   487             }

   488         };

   490         /** max number of incorporation rounds */

   491         static final int MAX_INCORPORATION_STEPS = 100;

   493     /**

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

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

   496      * logic into the basic bound checking routine

   497      */

   498     enum IncorporationStep {

   499         /**

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

   501          * inference variable compatible with its bounds?

   502          */

   503         CHECK_BOUNDS() {

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

   505                 Infer infer = inferenceContext.infer();

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

   507                 infer.checkCompatibleUpperBounds(uv, inferenceContext);

   508                 if (uv.inst != null) {

   509                     Type inst = uv.inst;

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

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

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

   513                         }

   514                     }

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

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

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

   518                         }

   519                     }

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

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

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

   523                         }

   524                     }

   525                 }

   526             }

   527         },

   528         /**

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

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

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

   532          */

   533         EQ_CHECK_LEGACY() {

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

   535                 Infer infer = inferenceContext.infer();

   536                 Type eq = null;

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

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

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

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

   541                     }

   542                     eq = e;

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

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

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

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

   547                         }

   548                     }

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

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

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

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

   553                         }

   554                     }

   555                 }

   556             }

   557         },

   558         /**

   559          * Check consistency of equality constraints.

   560          */

   561         EQ_CHECK() {

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

   563                 Infer infer = inferenceContext.infer();

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

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

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

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

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

   569                         }

   570                     }

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

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

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

   574                         }

   575                     }

   576                 }

   577             }

   578         },

   579         /**

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

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

   582          */

   583         CROSS_UPPER_LOWER() {

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

   585                 Infer infer = inferenceContext.infer();

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

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

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

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

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

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

   592                         }

   593                     }

   594                 }

   595             }

   596         },

   597         /**

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

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

   600          */

   601         CROSS_UPPER_EQ() {

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

   603                 Infer infer = inferenceContext.infer();

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

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

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

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

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

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

   610                         }

   611                     }

   612                 }

   613             }

   614         },

   615         /**

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

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

   618          */

   619         CROSS_EQ_LOWER() {

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

   621                 Infer infer = inferenceContext.infer();

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

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

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

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

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

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

   628                         }

   629                     }

   630                 }

   631             }

   632         },

   633         /**

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

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

   636          */

   637         PROP_UPPER() {

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

   639                 Infer infer = inferenceContext.infer();

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

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

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

   643                         //alpha <: beta

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

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

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

   647                         }

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

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

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

   651                         }

   652                     }

   653                 }

   654             }

   655         },

   656         /**

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

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

   659          */

   660         PROP_LOWER() {

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

   662                 Infer infer = inferenceContext.infer();

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

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

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

   666                         //alpha :> beta

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

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

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

   670                         }

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

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

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

   674                         }

   675                     }

   676                 }

   677             }

   678         },

   679         /**

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

   681          * bounds from alpha to beta and back.

   682          */

   683         PROP_EQ() {

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

   685                 Infer infer = inferenceContext.infer();

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

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

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

   689                         //alpha == beta

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

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

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

   693                                 if (b2 != uv2) {

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

   695                                 }

   696                             }

   697                         }

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

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

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

   701                                 if (b2 != uv) {

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

   703                                 }

   704                             }

   705                         }

   706                     }

   707                 }

   708             }

   709         };

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

   712     }

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

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

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

   718     EnumSet<IncorporationStep> incorporationStepsGraph =

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

   721     /**

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

   723      * variable by making sure that a glb exists.

   724      */

   725     void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {

   726         List<Type> hibounds =

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

   728         Type hb = null;

   729         if (hibounds.isEmpty())

   730             hb = syms.objectType;

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

   732             hb = hibounds.head;

   733         else

   734             hb = types.glb(hibounds);

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

   736             reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   737     }

   738     //where

   739         protected static class BoundFilter implements Filter<Type> {

   741             InferenceContext inferenceContext;

   743             public BoundFilter(InferenceContext inferenceContext) {

   744                 this.inferenceContext = inferenceContext;

   745             }

   747             @Override

   748             public boolean accepts(Type t) {

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

   750                         !t.hasTag(BOT);

   751             }

   752         };

   754     /**

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

   756      */

   757     enum BoundErrorKind {

   758         /**

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

   760          */

   761         BAD_UPPER() {

   762             @Override

   763             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   765                         uv.getBounds(InferenceBound.UPPER));

   766             }

   767         },

   768         /**

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

   770          */

   771         BAD_EQ_UPPER() {

   772             @Override

   773             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   776             }

   777         },

   778         /**

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

   780          */

   781         BAD_EQ_LOWER() {

   782             @Override

   783             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   786             }

   787         },

   788         /**

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

   790          */

   791         UPPER() {

   792             @Override

   793             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   795                         uv.getBounds(InferenceBound.UPPER));

   796             }

   797         },

   798         /**

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

   800          */

   801         LOWER() {

   802             @Override

   803             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   805                         uv.getBounds(InferenceBound.LOWER));

   806             }

   807         },

   808         /**

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

   810          */

   811         EQ() {

   812             @Override

   813             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   815                         uv.getBounds(InferenceBound.EQ));

   816             }

   817         };

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

   820     }

   822     /**

   823      * Report a bound-checking error of given kind

   824      */

   825     void reportBoundError(UndetVar uv, BoundErrorKind bk) {

   826         throw bk.setMessage(inferenceException, uv);

   827     }

   828     // </editor-fold>

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

   831     /**

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

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

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

   835      */

   836     interface GraphStrategy {

   837         /**

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

   839          */

   840         Node pickNode(InferenceGraph g);

   841         /**

   842          * Is this the last step?

   843          */

   844         boolean done();

   845     }

   847     /**

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

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

   850      */

   851     abstract class LeafSolver implements GraphStrategy {

   852         public Node pickNode(InferenceGraph g) {

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

   854             return g.nodes.get(0);

   855         }

   856     }

   858     /**

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

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

   861      * or more inference variables in a given list

   862      */

   863     abstract class BestLeafSolver extends LeafSolver {

   865         List<Type> varsToSolve;

   867         BestLeafSolver(List<Type> varsToSolve) {

   868             this.varsToSolve = varsToSolve;

   869         }

   871         /**

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

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

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

   875          * a given node

   876          */

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

   878             if (costMap.containsKey(n)) {

   879                 return;

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

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

   882             } else {

   883                 int subcost = Integer.MAX_VALUE;

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

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

   886                     computeCostIfNeeded(n2, costMap);

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

   888                 }

   889                 //update cost map to reflect real cost

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

   891                         Integer.MAX_VALUE :

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

   893             }

   894         }

   896         /**

   897          * Pick the leaf that minimize cost

   898          */

   899         @Override

   900         public Node pickNode(final InferenceGraph g) {

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

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

   903             for (Node n : g.nodes) {

   904                 computeCostIfNeeded(n, costMap);

   905                 if (n.isLeaf(n)) {

   906                     leaves.add(n);

   907                 }

   908             }

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

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

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

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

   913                 }

   914             });

   915             return leaves.get(0);

   916         }

   917     }

   919     /**

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

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

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

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

   924      */

   925     enum InferenceStep {

   927         /**

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

   929          * constraints

   930          */

   931         EQ(InferenceBound.EQ) {

   932             @Override

   933             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   934                 return filterBounds(uv, inferenceContext).head;

   935             }

   936         },

   937         /**

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

   939          * bounds are merged together using lub().

   940          */

   941         LOWER(InferenceBound.LOWER) {

   942             @Override

   943             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   944                 Infer infer = inferenceContext.infer();

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

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

   947                 if (owntype.hasTag(ERROR)) {

   948                     throw infer.inferenceException

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

   950                                     uv.qtype, lobounds);

   951                 } else {

   952                     return owntype;

   953                 }

   954             }

   955         },

   956         /**

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

   958          * bounds are merged together using glb().

   959          */

   960         UPPER(InferenceBound.UPPER) {

   961             @Override

   962             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   963                 Infer infer = inferenceContext.infer();

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

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

   966                 if (owntype.isErroneous()) {

   967                     throw infer.inferenceException

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

   969                                     uv.qtype, hibounds);

   970                 } else {

   971                     return owntype;

   972                 }

   973             }

   974         },

   975         /**

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

   977          * if all upper bounds are ground.

   978          */

   979         UPPER_LEGACY(InferenceBound.UPPER) {

   980             @Override

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

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

   983             }

   985             @Override

   986             Type solve(UndetVar uv, InferenceContext inferenceContext) {

   987                 return UPPER.solve(uv, inferenceContext);

   988             }

   989         };

   991         final InferenceBound ib;

   993         InferenceStep(InferenceBound ib) {

   994             this.ib = ib;

   995         }

   997         /**

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

   999          * a given inference context

  1000          */

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

  1003         /**

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

  1005          */

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

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

  1008         }

  1010         /**

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

  1012          */

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

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

  1015         }

  1016     }

  1018     /**

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

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

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

  1022      */

  1023     enum LegacyInferenceSteps {

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

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

  1028         final EnumSet<InferenceStep> steps;

  1030         LegacyInferenceSteps(EnumSet<InferenceStep> steps) {

  1031             this.steps = steps;

  1032         }

  1033     }

  1035     /**

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

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

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

  1039      */

  1040     enum GraphInferenceSteps {

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

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

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

  1046         final EnumSet<InferenceStep> steps;

  1048         GraphInferenceSteps(EnumSet<InferenceStep> steps) {

  1049             this.steps = steps;

  1050         }

  1051     }

  1053     /**

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

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

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

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

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

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

  1060      */

  1061     class GraphSolver {

  1063         InferenceContext inferenceContext;

  1064         Warner warn;

  1066         GraphSolver(InferenceContext inferenceContext, Warner warn) {

  1067             this.inferenceContext = inferenceContext;

  1068             this.warn = warn;

  1069         }

  1071         /**

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

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

  1074          * depends on the selected solver strategy.

  1075          */

  1076         void solve(GraphStrategy sstrategy) {

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

  1078             InferenceGraph inferenceGraph = new InferenceGraph();

  1079             while (!sstrategy.done()) {

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

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

  1082                 inferenceContext.save();

  1083                 try {

  1084                     //repeat until all variables are solved

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

  1086                         //for each inference phase

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

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

  1089                                 checkWithinBounds(inferenceContext, warn);

  1090                                 continue outer;

  1091                             }

  1092                         }

  1093                         //no progress

  1094                         throw inferenceException;

  1095                     }

  1096                 }

  1097                 catch (InferenceException ex) {

  1098                     inferenceContext.rollback();

  1099                     instantiateAsUninferredVars(varsToSolve, inferenceContext);

  1100                     checkWithinBounds(inferenceContext, warn);

  1101                 }

  1102                 inferenceGraph.deleteNode(nodeToSolve);

  1103             }

  1104         }

  1106         /**

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

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

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

  1110          */

  1111         class InferenceGraph {

  1113             /**

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

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

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

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

  1118              * keep dependencies in sync).

  1119              */

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

  1122                 Set<Node> deps;

  1124                 Node(Type ivar) {

  1125                     super(ListBuffer.of(ivar));

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

  1127                 }

  1129                 @Override

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

  1131                     return deps;

  1132                 }

  1134                 @Override

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

  1136                     StringBuilder buf = new StringBuilder();

  1137                     String sep = "";

  1138                     for (Type from : data) {

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

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

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

  1142                                 buf.append(sep);

  1143                                 buf.append(bound);

  1144                                 sep = ",";

  1145                             }

  1146                         }

  1147                     }

  1148                     return buf.toString();

  1149                 }

  1151                 boolean isLeaf(Node n) {

  1152                     //no deps, or only one self dep

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

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

  1155                 }

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

  1158                     for (Node n : nodes) {

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

  1160                         data.appendList(n.data);

  1161                         deps.addAll(n.deps);

  1162                     }

  1163                     //update deps

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

  1165                     for (Node d : deps) {

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

  1167                             deps2.add(this);

  1168                         } else {

  1169                             deps2.add(d);

  1170                         }

  1171                     }

  1172                     deps = deps2;

  1173                 }

  1175                 void graphChanged(Node from, Node to) {

  1176                     if (deps.contains(from)) {

  1177                         deps.remove(from);

  1178                         if (to != null) {

  1179                             deps.add(to);

  1180                         }

  1181                     }

  1182                 }

  1183             }

  1185             /** the nodes in the inference graph */

  1186             ArrayList<Node> nodes;

  1188             InferenceGraph() {

  1189                 initNodes();

  1190             }

  1192             /**

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

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

  1195              */

  1196             public void deleteNode(Node n) {

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

  1198                 nodes.remove(n);

  1199                 notifyUpdate(n, null);

  1200             }

  1202             /**

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

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

  1205              */

  1206             void notifyUpdate(Node from, Node to) {

  1207                 for (Node n : nodes) {

  1208                     n.graphChanged(from, to);

  1209                 }

  1210             }

  1212             /**

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

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

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

  1216                  * created, effectively replacing the original cyclic nodes.

  1217              */

  1218             void initNodes() {

  1219                 nodes = new ArrayList<Node>();

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

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

  1222                 }

  1223                 for (Node n_i : nodes) {

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

  1225                     for (Node n_j : nodes) {

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

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

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

  1229                             //update i's deps

  1230                             n_i.deps.add(n_j);

  1231                             //update j's deps - only if i's bounds contain _exactly_ j

  1232                             if (uv_i.getBounds(InferenceBound.values()).contains(j)) {

  1233                                 n_j.deps.add(n_i);

  1234                             }

  1235                         }

  1236                     }

  1237                 }

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

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

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

  1241                         Node root = conSubGraph.head;

  1242                         root.mergeWith(conSubGraph.tail);

  1243                         for (Node n : conSubGraph) {

  1244                             notifyUpdate(n, root);

  1245                         }

  1246                     }

  1247                     acyclicNodes.add(conSubGraph.head);

  1248                 }

  1249                 nodes = acyclicNodes;

  1250             }

  1252             /**

  1253              * Debugging: dot representation of this graph

  1254              */

  1255             String toDot() {

  1256                 StringBuilder buf = new StringBuilder();

  1257                 for (Type t : inferenceContext.undetvars) {

  1258                     UndetVar uv = (UndetVar)t;

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

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

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

  1262                 }

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

  1264             }

  1265         }

  1266     }

  1267     // </editor-fold>

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

  1270     /**

  1271      * Functional interface for defining inference callbacks. Certain actions

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

  1273      * have been fixed.

  1274      */

  1275     interface FreeTypeListener {

  1276         void typesInferred(InferenceContext inferenceContext);

  1277     }

  1279     /**

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

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

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

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

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

  1285      * (see InferenceKind).

  1286      */

  1287      class InferenceContext {

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

  1290         List<Type> undetvars;

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

  1293         List<Type> inferencevars;

  1295         /** backed up inference variables */

  1296         List<Type> saved_undet;

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

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

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

  1303         public InferenceContext(List<Type> inferencevars) {

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

  1305             this.inferencevars = inferencevars;

  1306         }

  1307         //where

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

  1309                 // mapping that turns inference variables into undet vars

  1310                 public Type apply(Type t) {

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

  1312                     else return t.map(this);

  1313                 }

  1314             };

  1316         /**

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

  1318          * inference context

  1319          */

  1320         List<Type> inferenceVars() {

  1321             return inferencevars;

  1322         }

  1324         /**

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

  1326          * inference context

  1327          */

  1328         List<Type> restvars() {

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

  1330                 public boolean accepts(UndetVar uv) {

  1331                     return uv.inst == null;

  1332                 }

  1333             });

  1334         }

  1336         /**

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

  1338          * inference context

  1339          */

  1340         List<Type> instvars() {

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

  1342                 public boolean accepts(UndetVar uv) {

  1343                     return uv.inst != null;

  1344                 }

  1345             });

  1346         }

  1348         /**

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

  1350          * declared bounds).

  1351          */

  1352         final List<Type> boundedVars() {

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

  1354                 public boolean accepts(UndetVar uv) {

  1355                     return uv.getBounds(InferenceBound.UPPER)

  1356                             .diff(uv.getDeclaredBounds())

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

  1358                 }

  1359             });

  1360         }

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

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

  1364             for (Type t : undetvars) {

  1365                 UndetVar uv = (UndetVar)t;

  1366                 if (fu.accepts(uv)) {

  1367                     res.append(uv.qtype);

  1368                 }

  1369             }

  1370             return res.toList();

  1371         }

  1373         /**

  1374          * is this type free?

  1375          */

  1376         final boolean free(Type t) {

  1377             return t.containsAny(inferencevars);

  1378         }

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

  1381             for (Type t : ts) {

  1382                 if (free(t)) return true;

  1383             }

  1384             return false;

  1385         }

  1387         /**

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

  1389          */

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

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

  1392             for (Type iv : inferenceVars()) {

  1393                 if (t.contains(iv)) {

  1394                     buf.add(iv);

  1395                 }

  1396             }

  1397             return buf.toList();

  1398         }

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

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

  1402             for (Type t : ts) {

  1403                 buf.appendList(freeVarsIn(t));

  1404             }

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

  1406             for (Type t : buf) {

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

  1408                     buf2.add(t);

  1409                 }

  1410             }

  1411             return buf2.toList();

  1412         }

  1414         /**

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

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

  1417          * of inference constraints).

  1418          */

  1419         final Type asFree(Type t) {

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

  1421         }

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

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

  1425             for (Type t : ts) {

  1426                 buf.append(asFree(t));

  1427             }

  1428             return buf.toList();

  1429         }

  1431         List<Type> instTypes() {

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

  1433             for (Type t : undetvars) {

  1434                 UndetVar uv = (UndetVar)t;

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

  1436             }

  1437             return buf.toList();

  1438         }

  1440         /**

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

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

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

  1444          */

  1445         Type asInstType(Type t) {

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

  1447         }

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

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

  1451             for (Type t : ts) {

  1452                 buf.append(asInstType(t));

  1453             }

  1454             return buf.toList();

  1455         }

  1457         /**

  1458          * Add custom hook for performing post-inference action

  1459          */

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

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

  1462         }

  1464         /**

  1465          * Mark the inference context as complete and trigger evaluation

  1466          * of all deferred checks.

  1467          */

  1468         void notifyChange() {

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

  1470         }

  1472         void notifyChange(List<Type> inferredVars) {

  1473             InferenceException thrownEx = null;

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

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

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

  1477                     try {

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

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

  1480                     } catch (InferenceException ex) {

  1481                         if (thrownEx == null) {

  1482                             thrownEx = ex;

  1483                         }

  1484                     }

  1485                 }

  1486             }

  1487             //inference exception multiplexing - present any inference exception

  1488             //thrown when processing listeners as a single one

  1489             if (thrownEx != null) {

  1490                 throw thrownEx;

  1491             }

  1492         }

  1494         /**

  1495          * Save the state of this inference context

  1496          */

  1497         void save() {

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

  1499             for (Type t : undetvars) {

  1500                 UndetVar uv = (UndetVar)t;

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

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

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

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

  1505                     }

  1506                 }

  1507                 uv2.inst = uv.inst;

  1508                 buf.add(uv2);

  1509             }

  1510             saved_undet = buf.toList();

  1511         }

  1513         /**

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

  1515          */

  1516         void rollback() {

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

  1518             undetvars = saved_undet;

  1519             saved_undet = null;

  1520         }

  1522         /**

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

  1524          */

  1525         void dupTo(final InferenceContext that) {

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

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

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

  1529             //propagated vars are inferred in new context

  1530             for (Type t : inferencevars) {

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

  1532                     public void typesInferred(InferenceContext inferenceContext) {

  1533                         InferenceContext.this.notifyChange();

  1534                     }

  1535                 }, List.of(t));

  1536             }

  1537         }

  1539         /**

  1540          * Solve with given graph strategy.

  1541          */

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

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

  1544             s.solve(ss);

  1545         }

  1547         /**

  1548          * Solve all variables in this context.

  1549          */

  1550         public void solve(Warner warn) {

  1551             solve(new LeafSolver() {

  1552                 public boolean done() {

  1553                     return restvars().isEmpty();

  1554                 }

  1555             }, warn);

  1556         }

  1558         /**

  1559          * Solve all variables in the given list.

  1560          */

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

  1562             solve(new BestLeafSolver(vars) {

  1563                 public boolean done() {

  1564                     return !free(asInstTypes(vars));

  1565                 }

  1566             }, warn);

  1567         }

  1569         /**

  1570          * Solve at least one variable in given list.

  1571          */

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

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

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

  1575             if (boundedVars.isEmpty()) {

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

  1577                                 freeVarsIn(varsToSolve));

  1578             }

  1579             solve(new BestLeafSolver(boundedVars) {

  1580                 public boolean done() {

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

  1582                 }

  1583             }, warn);

  1584         }

  1586         /**

  1587          * Apply a set of inference steps

  1588          */

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

  1590             return solveBasic(inferencevars, steps);

  1591         }

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

  1594             boolean changed = false;

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

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

  1597                 for (InferenceStep step : steps) {

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

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

  1600                         changed = true;

  1601                         break;

  1602                     }

  1603                 }

  1604             }

  1605             return changed;

  1606         }

  1608         /**

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

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

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

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

  1613          * instantiation, until all variables are solved.

  1614          */

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

  1616             while (true) {

  1617                 boolean stuck = !solveBasic(steps);

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

  1619                     //all variables have been instantiated - exit

  1620                     break;

  1621                 } else if (stuck) {

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

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

  1624                     instantiateAsUninferredVars(restvars(), this);

  1625                     break;

  1626                 } else {

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

  1628                     //variables in remaining upper bounds and continue

  1629                     for (Type t : undetvars) {

  1630                         UndetVar uv = (UndetVar)t;

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

  1632                     }

  1633                 }

  1634             }

  1635             checkWithinBounds(this, warn);

  1636         }

  1638         private Infer infer() {

  1639             //back-door to infer

  1640             return Infer.this;

  1641         }

  1642     }

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

  1645     // </editor-fold>

  1646 }

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

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

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