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

8016081: field initialized with lambda in annotation types doesn't compile
Summary: check for annotation attributes should skip over synthetic methods
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.Comparator;

    45 import java.util.HashMap;

    46 import java.util.Map;

    47 import java.util.Set;

    48 import java.util.TreeSet;

    50 import java.util.ArrayList;

    51 import java.util.Collections;

    52 import java.util.EnumSet;

    53 import java.util.HashSet;

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

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

    58  *

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

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

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

    62  *  deletion without notice.</b>

    63  */

    64 public class Infer {

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

    66         new Context.Key<Infer>();

    68     Resolve rs;

    69     Check chk;

    70     Symtab syms;

    71     Types types;

    72     JCDiagnostic.Factory diags;

    73     Log log;

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

    76     boolean allowGraphInference;

    78     public static Infer instance(Context context) {

    79         Infer instance = context.get(inferKey);

    80         if (instance == null)

    81             instance = new Infer(context);

    82         return instance;

    83     }

    85     protected Infer(Context context) {

    86         context.put(inferKey, this);

    88         rs = Resolve.instance(context);

    89         chk = Check.instance(context);

    90         syms = Symtab.instance(context);

    91         types = Types.instance(context);

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

    93         log = Log.instance(context);

    94         inferenceException = new InferenceException(diags);

    95         Options options = Options.instance(context);

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

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

    98     }

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

   101     public static final Type anyPoly = new JCNoType();

   103    /**

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

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

   106     */

   107     public static class InferenceException extends InapplicableMethodException {

   108         private static final long serialVersionUID = 0;

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

   112         InferenceException(JCDiagnostic.Factory diags) {

   113             super(diags);

   114         }

   116         @Override

   117         InapplicableMethodException setMessage(JCDiagnostic diag) {

   118             messages = messages.append(diag);

   119             return this;

   120         }

   122         @Override

   123         public JCDiagnostic getDiagnostic() {

   124             return messages.head;

   125         }

   127         void clear() {

   128             messages = List.nil();

   129         }

   130     }

   132     protected final InferenceException inferenceException;

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

   135     /**

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

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

   138      */

   139     public Type instantiateMethod(Env<AttrContext> env,

   140                                   List<Type> tvars,

   141                                   MethodType mt,

   142                                   Attr.ResultInfo resultInfo,

   143                                   Symbol msym,

   144                                   List<Type> argtypes,

   145                                   boolean allowBoxing,

   146                                   boolean useVarargs,

   147                                   Resolve.MethodResolutionContext resolveContext,

   148                                   Warner warn) throws InferenceException {

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

   150         final InferenceContext inferenceContext = new InferenceContext(tvars);

   151         inferenceException.clear();

   152         try {

   153             DeferredAttr.DeferredAttrContext deferredAttrContext =

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

   156             resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext,

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

   159             if (allowGraphInference &&

   160                     resultInfo != null &&

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

   162                 //inject return constraints earlier

   163                 checkWithinBounds(inferenceContext, warn); //propagation

   164                 Type newRestype = generateReturnConstraints(resultInfo, mt, inferenceContext);

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

   166                 //propagate outwards if needed

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

   168                     //propagate inference context outwards and exit

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

   170                     deferredAttrContext.complete();

   171                     return mt;

   172                 }

   173             }

   175             deferredAttrContext.complete();

   177             // minimize as yet undetermined type variables

   178             if (allowGraphInference) {

   179                 inferenceContext.solve(warn);

   180             } else {

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

   182             }

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

   186             if (!allowGraphInference &&

   187                     inferenceContext.restvars().nonEmpty() &&

   188                     resultInfo != null &&

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

   190                 generateReturnConstraints(resultInfo, mt, inferenceContext);

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

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

   193             }

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

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

   197             }

   199             // return instantiated version of method type

   200             return mt;

   201         } finally {

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

   203                 inferenceContext.notifyChange();

   204             } else {

   205                 inferenceContext.notifyChange(inferenceContext.boundedVars());

   206             }

   207         }

   208     }

   210     /**

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

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

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

   214      */

   215     Type generateReturnConstraints(Attr.ResultInfo resultInfo,

   216             MethodType mt, InferenceContext inferenceContext) {

   217         Type from = mt.getReturnType();

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

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

   220             from = types.capture(from);

   221             //add synthetic captured ivars

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

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

   224                     inferenceContext.addVar((TypeVar)t);

   225                 }

   226             }

   227         }

   228         Type qtype1 = inferenceContext.asFree(from);

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

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

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

   232         //we need to skip capture?

   233         Warner retWarn = new Warner();

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

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

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

   237             throw inferenceException

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

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

   240         }

   241         return from;

   242     }

   244     Type returnConstraintTarget(Type from, Type to) {

   245         if (from.hasTag(VOID)) {

   246             return syms.voidType;

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

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

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

   250             if (!allowGraphInference) {

   251                 //if legacy, just return boxed type

   252                 return types.boxedClass(to).type;

   253             }

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

   255             UndetVar uv = (UndetVar)from;

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

   257                 Type boundAsPrimitive = types.unboxedType(t);

   258                 if (boundAsPrimitive == null) continue;

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

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

   261                     return syms.objectType;

   262                 }

   263             }

   264             return types.boxedClass(to).type;

   265         } else {

   266             return to;

   267         }

   268     }

   270     /**

   271       * Infer cyclic inference variables as described in 15.12.2.8.

   272       */

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

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

   275         //step 1 - create fresh tvars

   276         for (Type t : vars) {

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

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

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

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

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

   282                 todo.append(uv);

   283                 uv.inst = fresh_tvar.type;

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

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

   286             } else {

   287                 uv.inst = syms.objectType;

   288             }

   289         }

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

   291         List<Type> formals = vars;

   292         for (Type t : todo) {

   293             UndetVar uv = (UndetVar)t;

   294             TypeVar ct = (TypeVar)uv.inst;

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

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

   297                 //report inference error if glb fails

   298                 reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   299             }

   300             formals = formals.tail;

   301         }

   302     }

   304     /**

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

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

   307      * enclosing scope surrounding the polymorphic-signature call.

   308      */

   309     Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,

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

   311                                             Resolve.MethodResolutionContext resolveContext,

   312                                             List<Type> argtypes) {

   313         final Type restype;

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

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

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

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

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

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

   321         //the polymorphic signature call environment is nested.

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

   324             case TYPECAST:

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

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

   327                     castTree.clazz.type :

   328                     syms.objectType;

   329                 break;

   330             case EXEC:

   331                 JCTree.JCExpressionStatement execTree =

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

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

   334                     syms.voidType :

   335                     syms.objectType;

   336                 break;

   337             default:

   338                 restype = syms.objectType;

   339         }

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

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

   343             spMethod.getThrownTypes() :

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

   346         MethodType mtype = new MethodType(paramtypes,

   347                                           restype,

   348                                           exType,

   349                                           syms.methodClass);

   350         return mtype;

   351     }

   352     //where

   353         class ImplicitArgType extends DeferredAttr.DeferredTypeMap {

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

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

   357             }

   359             public Type apply(Type t) {

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

   361                 if (t.hasTag(BOT))

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

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

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

   365                 return t;

   366             }

   367         }

   369     /**

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

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

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

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

   374       */

   375     public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,

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

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

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

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

   380             return funcInterface;

   381         } else {

   382             Type formalInterface = funcInterface.tsym.type;

   383             InferenceContext funcInterfaceContext =

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

   386             Assert.check(paramTypes != null);

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

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

   389             //in the functional interface descriptors)

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

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

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

   393                 return types.createErrorType(funcInterface);

   394             }

   395             for (Type p : descParameterTypes) {

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

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

   398                     return types.createErrorType(funcInterface);

   399                 }

   400                 paramTypes = paramTypes.tail;

   401             }

   403             try {

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

   405             } catch (InferenceException ex) {

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

   407             }

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

   410             for (Type t : funcInterfaceContext.undetvars) {

   411                 UndetVar uv = (UndetVar)t;

   412                 if (uv.inst == null) {

   413                     uv.inst = actualTypeargs.head;

   414                 }

   415                 actualTypeargs = actualTypeargs.tail;

   416             }

   418             Type owntype = funcInterfaceContext.asInstType(formalInterface);

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

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

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

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

   423             }

   424             return owntype;

   425         }

   426     }

   427     // </editor-fold>

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

   430     /**

   431      * Check bounds and perform incorporation

   432      */

   433     void checkWithinBounds(InferenceContext inferenceContext,

   434                              Warner warn) throws InferenceException {

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

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

   437         try {

   438             while (true) {

   439                 mlistener.reset();

   440                 if (!allowGraphInference) {

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

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

   443                     for (Type t : inferenceContext.undetvars) {

   444                         UndetVar uv = (UndetVar)t;

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

   446                     }

   447                 }

   448                 for (Type t : inferenceContext.undetvars) {

   449                     UndetVar uv = (UndetVar)t;

   450                     //bound incorporation

   451                     EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?

   452                             incorporationStepsGraph : incorporationStepsLegacy;

   453                     for (IncorporationStep is : incorporationSteps) {

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

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

   456                         }

   457                     }

   458                 }

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

   460             }

   461         }

   462         finally {

   463             mlistener.detach();

   464             if (incorporationCache.size() == MAX_INCORPORATION_STEPS) {

   465                 inferenceContext.rollback(saved_undet);

   466             }

   467             incorporationCache.clear();

   468         }

   469     }

   470     //where

   471         /**

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

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

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

   475          * left in a clean state.

   476          */

   477         class MultiUndetVarListener implements UndetVar.UndetVarListener {

   479             boolean changed;

   480             List<Type> undetvars;

   482             public MultiUndetVarListener(List<Type> undetvars) {

   483                 this.undetvars = undetvars;

   484                 for (Type t : undetvars) {

   485                     UndetVar uv = (UndetVar)t;

   486                     uv.listener = this;

   487                 }

   488             }

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

   491                 //avoid non-termination

   492                 if (incorporationCache.size() < MAX_INCORPORATION_STEPS) {

   493                     changed = true;

   494                 }

   495             }

   497             void reset() {

   498                 changed = false;

   499             }

   501             void detach() {

   502                 for (Type t : undetvars) {

   503                     UndetVar uv = (UndetVar)t;

   504                     uv.listener = null;

   505                 }

   506             }

   507         };

   509         /** max number of incorporation rounds */

   510         static final int MAX_INCORPORATION_STEPS = 100;

   512     /**

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

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

   515      * logic into the basic bound checking routine

   516      */

   517     enum IncorporationStep {

   518         /**

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

   520          * inference variable compatible with its bounds?

   521          */

   522         CHECK_BOUNDS() {

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

   524                 Infer infer = inferenceContext.infer();

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

   526                 infer.checkCompatibleUpperBounds(uv, inferenceContext);

   527                 if (uv.inst != null) {

   528                     Type inst = uv.inst;

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

   530                         if (!isSubtype(inst, inferenceContext.asFree(u), warn, infer)) {

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

   532                         }

   533                     }

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

   535                         if (!isSubtype(inferenceContext.asFree(l), inst, warn, infer)) {

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

   537                         }

   538                     }

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

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

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

   542                         }

   543                     }

   544                 }

   545             }

   546             @Override

   547             boolean accepts(UndetVar uv, InferenceContext inferenceContext) {

   548                 //applies to all undetvars

   549                 return true;

   550             }

   551         },

   552         /**

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

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

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

   556          */

   557         EQ_CHECK_LEGACY() {

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

   559                 Infer infer = inferenceContext.infer();

   560                 Type eq = null;

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

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

   563                     if (eq != null && !isSameType(e, eq, infer)) {

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

   565                     }

   566                     eq = e;

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

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

   569                         if (!isSubtype(l, e, warn, infer)) {

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

   571                         }

   572                     }

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

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

   575                         if (!isSubtype(e, u, warn, infer)) {

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

   577                         }

   578                     }

   579                 }

   580             }

   581         },

   582         /**

   583          * Check consistency of equality constraints.

   584          */

   585         EQ_CHECK() {

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

   587                 Infer infer = inferenceContext.infer();

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

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

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

   591                         if (!isSubtype(e, inferenceContext.asFree(u), warn, infer)) {

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

   593                         }

   594                     }

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

   596                         if (!isSubtype(inferenceContext.asFree(l), e, warn, infer)) {

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

   598                         }

   599                     }

   600                 }

   601             }

   602         },

   603         /**

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

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

   606          */

   607         CROSS_UPPER_LOWER() {

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

   609                 Infer infer = inferenceContext.infer();

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

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

   612                         isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn , infer);

   613                     }

   614                 }

   615             }

   616         },

   617         /**

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

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

   620          */

   621         CROSS_UPPER_EQ() {

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

   623                 Infer infer = inferenceContext.infer();

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

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

   626                         isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn, infer);

   627                     }

   628                 }

   629             }

   630         },

   631         /**

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

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

   634          */

   635         CROSS_EQ_LOWER() {

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

   637                 Infer infer = inferenceContext.infer();

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

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

   640                         isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn, infer);

   641                     }

   642                 }

   643             }

   644         },

   645         /**

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

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

   648          */

   649         CROSS_EQ_EQ() {

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

   651                 Infer infer = inferenceContext.infer();

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

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

   654                         if (b1 != b2) {

   655                             isSameType(inferenceContext.asFree(b2), inferenceContext.asFree(b1), infer);

   656                         }

   657                     }

   658                 }

   659             }

   660         },

   661         /**

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

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

   664          */

   665         PROP_UPPER() {

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

   667                 Infer infer = inferenceContext.infer();

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

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

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

   671                         if (uv2.isCaptured()) continue;

   672                         //alpha <: beta

   673                         //0. set beta :> alpha

   674                         addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(uv.qtype), infer);

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

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

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

   678                         }

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

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

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

   682                         }

   683                     }

   684                 }

   685             }

   686         },

   687         /**

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

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

   690          */

   691         PROP_LOWER() {

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

   693                 Infer infer = inferenceContext.infer();

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

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

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

   697                         if (uv2.isCaptured()) continue;

   698                         //alpha :> beta

   699                         //0. set beta <: alpha

   700                         addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(uv.qtype), infer);

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

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

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

   704                         }

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

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

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

   708                         }

   709                     }

   710                 }

   711             }

   712         },

   713         /**

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

   715          * bounds from alpha to beta and back.

   716          */

   717         PROP_EQ() {

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

   719                 Infer infer = inferenceContext.infer();

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

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

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

   723                         if (uv2.isCaptured()) continue;

   724                         //alpha == beta

   725                         //0. set beta == alpha

   726                         addBound(InferenceBound.EQ, uv2, inferenceContext.asInstType(uv.qtype), infer);

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

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

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

   730                                 if (b2 != uv2) {

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

   732                                 }

   733                             }

   734                         }

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

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

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

   738                                 if (b2 != uv) {

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

   740                                 }

   741                             }

   742                         }

   743                     }

   744                 }

   745             }

   746         };

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

   750         boolean accepts(UndetVar uv, InferenceContext inferenceContext) {

   751             return !uv.isCaptured();

   752         }

   754         boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {

   755             return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);

   756         }

   758         boolean isSameType(Type s, Type t, Infer infer) {

   759             return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);

   760         }

   762         void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {

   763             doIncorporationOp(opFor(ib), uv, b, null, infer);

   764         }

   766         IncorporationBinaryOpKind opFor(InferenceBound boundKind) {

   767             switch (boundKind) {

   768                 case EQ:

   769                     return IncorporationBinaryOpKind.ADD_EQ_BOUND;

   770                 case LOWER:

   771                     return IncorporationBinaryOpKind.ADD_LOWER_BOUND;

   772                 case UPPER:

   773                     return IncorporationBinaryOpKind.ADD_UPPER_BOUND;

   774                 default:

   775                     Assert.error("Can't get here!");

   776                     return null;

   777             }

   778         }

   780         boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {

   781             IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);

   782             Boolean res = infer.incorporationCache.get(newOp);

   783             if (res == null) {

   784                 infer.incorporationCache.put(newOp, res = newOp.apply(warn));

   785             }

   786             return res;

   787         }

   788     }

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

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

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

   794     EnumSet<IncorporationStep> incorporationStepsGraph =

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

   797     /**

   798      * Three kinds of basic operation are supported as part of an incorporation step:

   799      * (i) subtype check, (ii) same type check and (iii) bound addition (either

   800      * upper/lower/eq bound).

   801      */

   802     enum IncorporationBinaryOpKind {

   803         IS_SUBTYPE() {

   804             @Override

   805             boolean apply(Type op1, Type op2, Warner warn, Types types) {

   806                 return types.isSubtypeUnchecked(op1, op2, warn);

   807             }

   808         },

   809         IS_SAME_TYPE() {

   810             @Override

   811             boolean apply(Type op1, Type op2, Warner warn, Types types) {

   812                 return types.isSameType(op1, op2);

   813             }

   814         },

   815         ADD_UPPER_BOUND() {

   816             @Override

   817             boolean apply(Type op1, Type op2, Warner warn, Types types) {

   818                 UndetVar uv = (UndetVar)op1;

   819                 uv.addBound(InferenceBound.UPPER, op2, types);

   820                 return true;

   821             }

   822         },

   823         ADD_LOWER_BOUND() {

   824             @Override

   825             boolean apply(Type op1, Type op2, Warner warn, Types types) {

   826                 UndetVar uv = (UndetVar)op1;

   827                 uv.addBound(InferenceBound.LOWER, op2, types);

   828                 return true;

   829             }

   830         },

   831         ADD_EQ_BOUND() {

   832             @Override

   833             boolean apply(Type op1, Type op2, Warner warn, Types types) {

   834                 UndetVar uv = (UndetVar)op1;

   835                 uv.addBound(InferenceBound.EQ, op2, types);

   836                 return true;

   837             }

   838         };

   840         abstract boolean apply(Type op1, Type op2, Warner warn, Types types);

   841     }

   843     /**

   844      * This class encapsulates a basic incorporation operation; incorporation

   845      * operations takes two type operands and a kind. Each operation performed

   846      * during an incorporation round is stored in a cache, so that operations

   847      * are not executed unnecessarily (which would potentially lead to adding

   848      * same bounds over and over).

   849      */

   850     class IncorporationBinaryOp {

   852         IncorporationBinaryOpKind opKind;

   853         Type op1;

   854         Type op2;

   856         IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) {

   857             this.opKind = opKind;

   858             this.op1 = op1;

   859             this.op2 = op2;

   860         }

   862         @Override

   863         public boolean equals(Object o) {

   864             if (!(o instanceof IncorporationBinaryOp)) {

   865                 return false;

   866             } else {

   867                 IncorporationBinaryOp that = (IncorporationBinaryOp)o;

   868                 return opKind == that.opKind &&

   869                         types.isSameType(op1, that.op1, true) &&

   870                         types.isSameType(op2, that.op2, true);

   871             }

   872         }

   874         @Override

   875         public int hashCode() {

   876             int result = opKind.hashCode();

   877             result *= 127;

   878             result += types.hashCode(op1);

   879             result *= 127;

   880             result += types.hashCode(op2);

   881             return result;

   882         }

   884         boolean apply(Warner warn) {

   885             return opKind.apply(op1, op2, warn, types);

   886         }

   887     }

   889     /** an incorporation cache keeps track of all executed incorporation-related operations */

   890     Map<IncorporationBinaryOp, Boolean> incorporationCache =

   891             new HashMap<IncorporationBinaryOp, Boolean>();

   893     /**

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

   895      * variable by making sure that a glb exists.

   896      */

   897     void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {

   898         List<Type> hibounds =

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

   900         Type hb = null;

   901         if (hibounds.isEmpty())

   902             hb = syms.objectType;

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

   904             hb = hibounds.head;

   905         else

   906             hb = types.glb(hibounds);

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

   908             reportBoundError(uv, BoundErrorKind.BAD_UPPER);

   909     }

   910     //where

   911         protected static class BoundFilter implements Filter<Type> {

   913             InferenceContext inferenceContext;

   915             public BoundFilter(InferenceContext inferenceContext) {

   916                 this.inferenceContext = inferenceContext;

   917             }

   919             @Override

   920             public boolean accepts(Type t) {

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

   922                         !t.hasTag(BOT);

   923             }

   924         };

   926     /**

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

   928      */

   929     enum BoundErrorKind {

   930         /**

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

   932          */

   933         BAD_UPPER() {

   934             @Override

   935             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   937                         uv.getBounds(InferenceBound.UPPER));

   938             }

   939         },

   940         /**

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

   942          */

   943         BAD_EQ_UPPER() {

   944             @Override

   945             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   948             }

   949         },

   950         /**

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

   952          */

   953         BAD_EQ_LOWER() {

   954             @Override

   955             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

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

   958             }

   959         },

   960         /**

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

   962          */

   963         UPPER() {

   964             @Override

   965             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   967                         uv.getBounds(InferenceBound.UPPER));

   968             }

   969         },

   970         /**

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

   972          */

   973         LOWER() {

   974             @Override

   975             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   977                         uv.getBounds(InferenceBound.LOWER));

   978             }

   979         },

   980         /**

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

   982          */

   983         EQ() {

   984             @Override

   985             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {

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

   987                         uv.getBounds(InferenceBound.EQ));

   988             }

   989         };

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

   992     }

   994     /**

   995      * Report a bound-checking error of given kind

   996      */

   997     void reportBoundError(UndetVar uv, BoundErrorKind bk) {

   998         throw bk.setMessage(inferenceException, uv);

   999     }

  1000     // </editor-fold>

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

  1003     /**

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

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

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

  1007      */

  1008     interface GraphStrategy {

  1009         /**

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

  1011          */

  1012         Node pickNode(InferenceGraph g);

  1013         /**

  1014          * Is this the last step?

  1015          */

  1016         boolean done();

  1017     }

  1019     /**

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

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

  1022      */

  1023     abstract class LeafSolver implements GraphStrategy {

  1024         public Node pickNode(InferenceGraph g) {

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

  1026             return g.nodes.get(0);

  1027         }

  1029         boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {

  1030             return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);

  1031         }

  1033         boolean isSameType(Type s, Type t, Infer infer) {

  1034             return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);

  1035         }

  1037         void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {

  1038             doIncorporationOp(opFor(ib), uv, b, null, infer);

  1039         }

  1041         IncorporationBinaryOpKind opFor(InferenceBound boundKind) {

  1042             switch (boundKind) {

  1043                 case EQ:

  1044                     return IncorporationBinaryOpKind.ADD_EQ_BOUND;

  1045                 case LOWER:

  1046                     return IncorporationBinaryOpKind.ADD_LOWER_BOUND;

  1047                 case UPPER:

  1048                     return IncorporationBinaryOpKind.ADD_UPPER_BOUND;

  1049                 default:

  1050                     Assert.error("Can't get here!");

  1051                     return null;

  1052             }

  1053         }

  1055         boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {

  1056             IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);

  1057             Boolean res = infer.incorporationCache.get(newOp);

  1058             if (res == null) {

  1059                 infer.incorporationCache.put(newOp, res = newOp.apply(warn));

  1060             }

  1061             return res;

  1062         }

  1063     }

  1065     /**

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

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

  1068      * or more inference variables in a given list

  1069      */

  1070     abstract class BestLeafSolver extends LeafSolver {

  1072         List<Type> varsToSolve;

  1074         BestLeafSolver(List<Type> varsToSolve) {

  1075             this.varsToSolve = varsToSolve;

  1076         }

  1078         /**

  1079          * Computes the minimum path that goes from a given node to any of the nodes

  1080          * containing a variable in {@code varsToSolve}. For any given path, the cost

  1081          * is computed as the total number of type-variables that should be eagerly

  1082          * instantiated across that path.

  1083          */

  1084         int computeMinPath(InferenceGraph g, Node n) {

  1085             return computeMinPath(g, n, List.<Node>nil(), 0);

  1086         }

  1088         int computeMinPath(InferenceGraph g, Node n, List<Node> path, int cost) {

  1089             if (path.contains(n)) return Integer.MAX_VALUE;

  1090             List<Node> path2 = path.prepend(n);

  1091             int cost2 = cost + n.data.size();

  1092             if (!Collections.disjoint(n.data, varsToSolve)) {

  1093                 return cost2;

  1094             } else {

  1095                int bestPath = Integer.MAX_VALUE;

  1096                for (Node n2 : g.nodes) {

  1097                    if (n2.deps.contains(n)) {

  1098                        int res = computeMinPath(g, n2, path2, cost2);

  1099                        if (res < bestPath) {

  1100                            bestPath = res;

  1101                        }

  1102                    }

  1103                 }

  1104                return bestPath;

  1105             }

  1106         }

  1108         /**

  1109          * Pick the leaf that minimize cost

  1110          */

  1111         @Override

  1112         public Node pickNode(final InferenceGraph g) {

  1113             final Map<Node, Integer> leavesMap = new HashMap<Node, Integer>();

  1114             for (Node n : g.nodes) {

  1115                 if (n.isLeaf(n)) {

  1116                     leavesMap.put(n, computeMinPath(g, n));

  1117                 }

  1118             }

  1119             Assert.check(!leavesMap.isEmpty(), "No nodes to solve!");

  1120             TreeSet<Node> orderedLeaves = new TreeSet<Node>(new Comparator<Node>() {

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

  1122                     return leavesMap.get(n1) - leavesMap.get(n2);

  1123                 }

  1124             });

  1125             orderedLeaves.addAll(leavesMap.keySet());

  1126             return orderedLeaves.first();

  1127         }

  1128     }

  1130     /**

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

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

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

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

  1135      */

  1136     enum InferenceStep {

  1138         /**

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

  1140          * constraints

  1141          */

  1142         EQ(InferenceBound.EQ) {

  1143             @Override

  1144             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1145                 return filterBounds(uv, inferenceContext).head;

  1146             }

  1147         },

  1148         /**

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

  1150          * bounds are merged together using lub().

  1151          */

  1152         LOWER(InferenceBound.LOWER) {

  1153             @Override

  1154             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1155                 Infer infer = inferenceContext.infer();

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

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

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

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

  1160                     throw infer.inferenceException

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

  1162                                     uv.qtype, lobounds);

  1163                 } else {

  1164                     return owntype;

  1165                 }

  1166             }

  1167         },

  1168         /**

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

  1170          * clause as RuntimeException

  1171          */

  1172         THROWS(InferenceBound.UPPER) {

  1173             @Override

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

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

  1176                     //not a throws undet var

  1177                     return false;

  1178                 }

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

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

  1181                     //not an unbounded undet var

  1182                     return false;

  1183                 }

  1184                 Infer infer = inferenceContext.infer();

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

  1186                     if (t.isInterface()) continue;

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

  1188                         //declared bound is a supertype of RuntimeException

  1189                         return true;

  1190                     }

  1191                 }

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

  1193                 return false;

  1194             }

  1196             @Override

  1197             Type solve(UndetVar uv, InferenceContext inferenceContext) {

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

  1199             }

  1200         },

  1201         /**

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

  1203          * bounds are merged together using glb().

  1204          */

  1205         UPPER(InferenceBound.UPPER) {

  1206             @Override

  1207             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1208                 Infer infer = inferenceContext.infer();

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

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

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

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

  1213                     throw infer.inferenceException

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

  1215                                     uv.qtype, hibounds);

  1216                 } else {

  1217                     return owntype;

  1218                 }

  1219             }

  1220         },

  1221         /**

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

  1223          * if all upper bounds are ground.

  1224          */

  1225         UPPER_LEGACY(InferenceBound.UPPER) {

  1226             @Override

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

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

  1229             }

  1231             @Override

  1232             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1233                 return UPPER.solve(uv, inferenceContext);

  1234             }

  1235         },

  1236         /**

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

  1238          * if all upper/lower bounds are ground.

  1239          */

  1240         CAPTURED(InferenceBound.UPPER) {

  1241             @Override

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

  1243                 return t.isCaptured() &&

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

  1245             }

  1247             @Override

  1248             Type solve(UndetVar uv, InferenceContext inferenceContext) {

  1249                 Infer infer = inferenceContext.infer();

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

  1251                         UPPER.solve(uv, inferenceContext) :

  1252                         infer.syms.objectType;

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

  1254                         LOWER.solve(uv, inferenceContext) :

  1255                         infer.syms.botType;

  1256                 CapturedType prevCaptured = (CapturedType)uv.qtype;

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

  1258             }

  1259         };

  1261         final InferenceBound ib;

  1263         InferenceStep(InferenceBound ib) {

  1264             this.ib = ib;

  1265         }

  1267         /**

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

  1269          * a given inference context

  1270          */

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

  1273         /**

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

  1275          */

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

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

  1278         }

  1280         /**

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

  1282          */

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

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

  1285         }

  1286     }

  1288     /**

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

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

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

  1292      */

  1293     enum LegacyInferenceSteps {

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

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

  1298         final EnumSet<InferenceStep> steps;

  1300         LegacyInferenceSteps(EnumSet<InferenceStep> steps) {

  1301             this.steps = steps;

  1302         }

  1303     }

  1305     /**

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

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

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

  1309      */

  1310     enum GraphInferenceSteps {

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

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

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

  1316         final EnumSet<InferenceStep> steps;

  1318         GraphInferenceSteps(EnumSet<InferenceStep> steps) {

  1319             this.steps = steps;

  1320         }

  1321     }

  1323     /**

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

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

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

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

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

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

  1330      */

  1331     class GraphSolver {

  1333         InferenceContext inferenceContext;

  1334         Warner warn;

  1336         GraphSolver(InferenceContext inferenceContext, Warner warn) {

  1337             this.inferenceContext = inferenceContext;

  1338             this.warn = warn;

  1339         }

  1341         /**

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

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

  1344          * depends on the selected solver strategy.

  1345          */

  1346         void solve(GraphStrategy sstrategy) {

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

  1348             InferenceGraph inferenceGraph = new InferenceGraph();

  1349             while (!sstrategy.done()) {

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

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

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

  1353                 try {

  1354                     //repeat until all variables are solved

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

  1356                         //for each inference phase

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

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

  1359                                 checkWithinBounds(inferenceContext, warn);

  1360                                 continue outer;

  1361                             }

  1362                         }

  1363                         //no progress

  1364                         throw inferenceException.setMessage();

  1365                     }

  1366                 }

  1367                 catch (InferenceException ex) {

  1368                     //did we fail because of interdependent ivars?

  1369                     inferenceContext.rollback(saved_undet);

  1370                     instantiateAsUninferredVars(varsToSolve, inferenceContext);

  1371                     checkWithinBounds(inferenceContext, warn);

  1372                 }

  1373                 inferenceGraph.deleteNode(nodeToSolve);

  1374             }

  1375         }

  1377         /**

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

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

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

  1381          */

  1382         class InferenceGraph {

  1384             /**

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

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

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

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

  1389              * keep dependencies in sync).

  1390              */

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

  1393                 Set<Node> deps;

  1395                 Node(Type ivar) {

  1396                     super(ListBuffer.of(ivar));

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

  1398                 }

  1400                 @Override

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

  1402                     return deps;

  1403                 }

  1405                 @Override

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

  1407                     StringBuilder buf = new StringBuilder();

  1408                     String sep = "";

  1409                     for (Type from : data) {

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

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

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

  1413                                 buf.append(sep);

  1414                                 buf.append(bound);

  1415                                 sep = ",";

  1416                             }

  1417                         }

  1418                     }

  1419                     return buf.toString();

  1420                 }

  1422                 boolean isLeaf(Node n) {

  1423                     //no deps, or only one self dep

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

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

  1426                 }

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

  1429                     for (Node n : nodes) {

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

  1431                         data.appendList(n.data);

  1432                         deps.addAll(n.deps);

  1433                     }

  1434                     //update deps

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

  1436                     for (Node d : deps) {

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

  1438                             deps2.add(this);

  1439                         } else {

  1440                             deps2.add(d);

  1441                         }

  1442                     }

  1443                     deps = deps2;

  1444                 }

  1446                 void graphChanged(Node from, Node to) {

  1447                     if (deps.contains(from)) {

  1448                         deps.remove(from);

  1449                         if (to != null) {

  1450                             deps.add(to);

  1451                         }

  1452                     }

  1453                 }

  1454             }

  1456             /** the nodes in the inference graph */

  1457             ArrayList<Node> nodes;

  1459             InferenceGraph() {

  1460                 initNodes();

  1461             }

  1463             /**

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

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

  1466              */

  1467             public void deleteNode(Node n) {

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

  1469                 nodes.remove(n);

  1470                 notifyUpdate(n, null);

  1471             }

  1473             /**

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

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

  1476              */

  1477             void notifyUpdate(Node from, Node to) {

  1478                 for (Node n : nodes) {

  1479                     n.graphChanged(from, to);

  1480                 }

  1481             }

  1483             /**

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

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

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

  1487                  * created, effectively replacing the original cyclic nodes.

  1488              */

  1489             void initNodes() {

  1490                 nodes = new ArrayList<Node>();

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

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

  1493                 }

  1494                 for (Node n_i : nodes) {

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

  1496                     for (Node n_j : nodes) {

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

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

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

  1500                             //update i's deps

  1501                             n_i.deps.add(n_j);

  1502                         }

  1503                     }

  1504                 }

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

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

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

  1508                         Node root = conSubGraph.head;

  1509                         root.mergeWith(conSubGraph.tail);

  1510                         for (Node n : conSubGraph) {

  1511                             notifyUpdate(n, root);

  1512                         }

  1513                     }

  1514                     acyclicNodes.add(conSubGraph.head);

  1515                 }

  1516                 nodes = acyclicNodes;

  1517             }

  1519             /**

  1520              * Debugging: dot representation of this graph

  1521              */

  1522             String toDot() {

  1523                 StringBuilder buf = new StringBuilder();

  1524                 for (Type t : inferenceContext.undetvars) {

  1525                     UndetVar uv = (UndetVar)t;

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

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

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

  1529                 }

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

  1531             }

  1532         }

  1533     }

  1534     // </editor-fold>

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

  1537     /**

  1538      * Functional interface for defining inference callbacks. Certain actions

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

  1540      * have been fixed.

  1541      */

  1542     interface FreeTypeListener {

  1543         void typesInferred(InferenceContext inferenceContext);

  1544     }

  1546     /**

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

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

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

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

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

  1552      * (see InferenceKind).

  1553      */

  1554      class InferenceContext {

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

  1557         List<Type> undetvars;

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

  1560         List<Type> inferencevars;

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

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

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

  1567         public InferenceContext(List<Type> inferencevars) {

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

  1569             this.inferencevars = inferencevars;

  1570         }

  1571         //where

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

  1573                 // mapping that turns inference variables into undet vars

  1574                 public Type apply(Type t) {

  1575                     if (t.hasTag(TYPEVAR)) {

  1576                         TypeVar tv = (TypeVar)t;

  1577                         return tv.isCaptured() ?

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

  1579                                 new UndetVar(tv, types);

  1580                     } else {

  1581                         return t.map(this);

  1582                     }

  1583                 }

  1584             };

  1586         /**

  1587          * add a new inference var to this inference context

  1588          */

  1589         void addVar(TypeVar t) {

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

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

  1592         }

  1594         /**

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

  1596          * inference context

  1597          */

  1598         List<Type> inferenceVars() {

  1599             return inferencevars;

  1600         }

  1602         /**

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

  1604          * inference context

  1605          */

  1606         List<Type> restvars() {

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

  1608                 public boolean accepts(UndetVar uv) {

  1609                     return uv.inst == null;

  1610                 }

  1611             });

  1612         }

  1614         /**

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

  1616          * inference context

  1617          */

  1618         List<Type> instvars() {

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

  1620                 public boolean accepts(UndetVar uv) {

  1621                     return uv.inst != null;

  1622                 }

  1623             });

  1624         }

  1626         /**

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

  1628          * declared bounds).

  1629          */

  1630         final List<Type> boundedVars() {

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

  1632                 public boolean accepts(UndetVar uv) {

  1633                     return uv.getBounds(InferenceBound.UPPER)

  1634                             .diff(uv.getDeclaredBounds())

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

  1636                 }

  1637             });

  1638         }

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

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

  1642             for (Type t : undetvars) {

  1643                 UndetVar uv = (UndetVar)t;

  1644                 if (fu.accepts(uv)) {

  1645                     res.append(uv.qtype);

  1646                 }

  1647             }

  1648             return res.toList();

  1649         }

  1651         /**

  1652          * is this type free?

  1653          */

  1654         final boolean free(Type t) {

  1655             return t.containsAny(inferencevars);

  1656         }

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

  1659             for (Type t : ts) {

  1660                 if (free(t)) return true;

  1661             }

  1662             return false;

  1663         }

  1665         /**

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

  1667          */

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

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

  1670             for (Type iv : inferenceVars()) {

  1671                 if (t.contains(iv)) {

  1672                     buf.add(iv);

  1673                 }

  1674             }

  1675             return buf.toList();

  1676         }

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

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

  1680             for (Type t : ts) {

  1681                 buf.appendList(freeVarsIn(t));

  1682             }

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

  1684             for (Type t : buf) {

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

  1686                     buf2.add(t);

  1687                 }

  1688             }

  1689             return buf2.toList();

  1690         }

  1692         /**

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

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

  1695          * of inference constraints).

  1696          */

  1697         final Type asFree(Type t) {

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

  1699         }

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

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

  1703             for (Type t : ts) {

  1704                 buf.append(asFree(t));

  1705             }

  1706             return buf.toList();

  1707         }

  1709         List<Type> instTypes() {

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

  1711             for (Type t : undetvars) {

  1712                 UndetVar uv = (UndetVar)t;

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

  1714             }

  1715             return buf.toList();

  1716         }

  1718         /**

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

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

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

  1722          */

  1723         Type asInstType(Type t) {

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

  1725         }

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

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

  1729             for (Type t : ts) {

  1730                 buf.append(asInstType(t));

  1731             }

  1732             return buf.toList();

  1733         }

  1735         /**

  1736          * Add custom hook for performing post-inference action

  1737          */

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

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

  1740         }

  1742         /**

  1743          * Mark the inference context as complete and trigger evaluation

  1744          * of all deferred checks.

  1745          */

  1746         void notifyChange() {

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

  1748         }

  1750         void notifyChange(List<Type> inferredVars) {

  1751             InferenceException thrownEx = null;

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

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

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

  1755                     try {

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

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

  1758                     } catch (InferenceException ex) {

  1759                         if (thrownEx == null) {

  1760                             thrownEx = ex;

  1761                         }

  1762                     }

  1763                 }

  1764             }

  1765             //inference exception multiplexing - present any inference exception

  1766             //thrown when processing listeners as a single one

  1767             if (thrownEx != null) {

  1768                 throw thrownEx;

  1769             }

  1770         }

  1772         /**

  1773          * Save the state of this inference context

  1774          */

  1775         List<Type> save() {

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

  1777             for (Type t : undetvars) {

  1778                 UndetVar uv = (UndetVar)t;

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

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

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

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

  1783                     }

  1784                 }

  1785                 uv2.inst = uv.inst;

  1786                 buf.add(uv2);

  1787             }

  1788             return buf.toList();

  1789         }

  1791         /**

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

  1793          */

  1794         void rollback(List<Type> saved_undet) {

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

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

  1797             for (Type t : undetvars) {

  1798                 UndetVar uv = (UndetVar)t;

  1799                 UndetVar uv_saved = (UndetVar)saved_undet.head;

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

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

  1802                 }

  1803                 uv.inst = uv_saved.inst;

  1804                 saved_undet = saved_undet.tail;

  1805             }

  1806         }

  1808         /**

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

  1810          */

  1811         void dupTo(final InferenceContext that) {

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

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

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

  1815             //propagated vars are inferred in new context

  1816             for (Type t : inferencevars) {

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

  1818                     public void typesInferred(InferenceContext inferenceContext) {

  1819                         InferenceContext.this.notifyChange();

  1820                     }

  1821                 }, List.of(t));

  1822             }

  1823         }

  1825         /**

  1826          * Solve with given graph strategy.

  1827          */

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

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

  1830             s.solve(ss);

  1831         }

  1833         /**

  1834          * Solve all variables in this context.

  1835          */

  1836         public void solve(Warner warn) {

  1837             solve(new LeafSolver() {

  1838                 public boolean done() {

  1839                     return restvars().isEmpty();

  1840                 }

  1841             }, warn);

  1842         }

  1844         /**

  1845          * Solve all variables in the given list.

  1846          */

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

  1848             solve(new BestLeafSolver(vars) {

  1849                 public boolean done() {

  1850                     return !free(asInstTypes(vars));

  1851                 }

  1852             }, warn);

  1853         }

  1855         /**

  1856          * Solve at least one variable in given list.

  1857          */

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

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

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

  1861             if (boundedVars.isEmpty()) {

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

  1863                                 freeVarsIn(varsToSolve));

  1864             }

  1865             solve(new BestLeafSolver(boundedVars) {

  1866                 public boolean done() {

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

  1868                 }

  1869             }, warn);

  1870         }

  1872         /**

  1873          * Apply a set of inference steps

  1874          */

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

  1876             return solveBasic(inferencevars, steps);

  1877         }

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

  1880             boolean changed = false;

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

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

  1883                 for (InferenceStep step : steps) {

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

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

  1886                         changed = true;

  1887                         break;

  1888                     }

  1889                 }

  1890             }

  1891             return changed;

  1892         }

  1894         /**

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

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

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

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

  1899          * instantiation, until all variables are solved.

  1900          */

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

  1902             while (true) {

  1903                 boolean stuck = !solveBasic(steps);

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

  1905                     //all variables have been instantiated - exit

  1906                     break;

  1907                 } else if (stuck) {

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

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

  1910                     instantiateAsUninferredVars(restvars(), this);

  1911                     break;

  1912                 } else {

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

  1914                     //variables in remaining upper bounds and continue

  1915                     for (Type t : undetvars) {

  1916                         UndetVar uv = (UndetVar)t;

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

  1918                     }

  1919                 }

  1920             }

  1921             checkWithinBounds(this, warn);

  1922         }

  1924         private Infer infer() {

  1925             //back-door to infer

  1926             return Infer.this;

  1927         }

  1928     }

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

  1931     // </editor-fold>

  1932 }

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

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

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