duke@1: /*
vromero@2302:  * Copyright (c) 1999, 2014, Oracle and/or its affiliates. All rights reserved.
duke@1:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1:  *
duke@1:  * This code is free software; you can redistribute it and/or modify it
duke@1:  * under the terms of the GNU General Public License version 2 only, as
ohair@554:  * published by the Free Software Foundation.  Oracle designates this
duke@1:  * particular file as subject to the "Classpath" exception as provided
ohair@554:  * by Oracle in the LICENSE file that accompanied this code.
duke@1:  *
duke@1:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@1:  * version 2 for more details (a copy is included in the LICENSE file that
duke@1:  * accompanied this code).
duke@1:  *
duke@1:  * You should have received a copy of the GNU General Public License version
duke@1:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@1:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1:  *
ohair@554:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ohair@554:  * or visit www.oracle.com if you need additional information or have any
ohair@554:  * questions.
duke@1:  */
duke@1: 
duke@1: package com.sun.tools.javac.comp;
duke@1: 
mcimadamore@674: import com.sun.tools.javac.tree.JCTree;
mcimadamore@674: import com.sun.tools.javac.tree.JCTree.JCTypeCast;
mcimadamore@820: import com.sun.tools.javac.tree.TreeInfo;
duke@1: import com.sun.tools.javac.util.*;
mcimadamore@1562: import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
duke@1: import com.sun.tools.javac.util.List;
mcimadamore@1562: import com.sun.tools.javac.code.*;
mcimadamore@1562: import com.sun.tools.javac.code.Type.*;
mcimadamore@1562: import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
mcimadamore@1562: import com.sun.tools.javac.code.Symbol.*;
mcimadamore@1562: import com.sun.tools.javac.comp.DeferredAttr.AttrMode;
mcimadamore@1562: import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph;
mcimadamore@1562: import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node;
mcimadamore@1562: import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
mcimadamore@1562: import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;
vromero@2000: import com.sun.tools.javac.util.GraphUtils.TarjanNode;
mcimadamore@1562: 
mcimadamore@1562: import java.util.ArrayList;
mcimadamore@1562: import java.util.Collections;
vromero@2000: import java.util.EnumMap;
mcimadamore@1562: import java.util.EnumSet;
vromero@2000: import java.util.HashMap;
mcimadamore@1562: import java.util.HashSet;
vromero@2000: import java.util.LinkedHashSet;
vromero@2000: import java.util.Map;
vromero@2000: import java.util.Set;
mcimadamore@1337: 
jjg@1374: import static com.sun.tools.javac.code.TypeTag.*;
duke@1: 
duke@1: /** Helper class for type parameter inference, used by the attribution phase.
duke@1:  *
jjg@581:  *  <p><b>This is NOT part of any supported API.
jjg@581:  *  If you write code that depends on this, you do so at your own risk.
duke@1:  *  This code and its internal interfaces are subject to change or
duke@1:  *  deletion without notice.</b>
duke@1:  */
duke@1: public class Infer {
duke@1:     protected static final Context.Key<Infer> inferKey =
duke@1:         new Context.Key<Infer>();
duke@1: 
mcimadamore@1562:     Resolve rs;
mcimadamore@1562:     Check chk;
duke@1:     Symtab syms;
duke@1:     Types types;
mcimadamore@1562:     JCDiagnostic.Factory diags;
mcimadamore@1114:     Log log;
duke@1: 
mcimadamore@1562:     /** should the graph solver be used? */
mcimadamore@1562:     boolean allowGraphInference;
mcimadamore@1510: 
duke@1:     public static Infer instance(Context context) {
duke@1:         Infer instance = context.get(inferKey);
duke@1:         if (instance == null)
duke@1:             instance = new Infer(context);
duke@1:         return instance;
duke@1:     }
duke@1: 
duke@1:     protected Infer(Context context) {
duke@1:         context.put(inferKey, this);
mcimadamore@1562: 
mcimadamore@1562:         rs = Resolve.instance(context);
mcimadamore@1562:         chk = Check.instance(context);
duke@1:         syms = Symtab.instance(context);
duke@1:         types = Types.instance(context);
mcimadamore@1562:         diags = JCDiagnostic.Factory.instance(context);
mcimadamore@1114:         log = Log.instance(context);
mcimadamore@1298:         inferenceException = new InferenceException(diags);
mcimadamore@1562:         Options options = Options.instance(context);
mcimadamore@1562:         allowGraphInference = Source.instance(context).allowGraphInference()
mcimadamore@1562:                 && options.isUnset("useLegacyInference");
duke@1:     }
duke@1: 
mcimadamore@1562:     /** A value for prototypes that admit any type, including polymorphic ones. */
vromero@1853:     public static final Type anyPoly = new JCNoType();
mcimadamore@1562: 
mcimadamore@1337:    /**
mcimadamore@1337:     * This exception class is design to store a list of diagnostics corresponding
mcimadamore@1337:     * to inference errors that can arise during a method applicability check.
mcimadamore@1337:     */
mcimadamore@1186:     public static class InferenceException extends InapplicableMethodException {
duke@1:         private static final long serialVersionUID = 0;
duke@1: 
mcimadamore@1337:         List<JCDiagnostic> messages = List.nil();
mcimadamore@1337: 
mcimadamore@299:         InferenceException(JCDiagnostic.Factory diags) {
mcimadamore@689:             super(diags);
duke@1:         }
mcimadamore@1337: 
mcimadamore@1337:         @Override
vromero@2000:         InapplicableMethodException setMessage() {
vromero@2000:             //no message to set
vromero@2000:             return this;
vromero@2000:         }
vromero@2000: 
vromero@2000:         @Override
mcimadamore@1337:         InapplicableMethodException setMessage(JCDiagnostic diag) {
mcimadamore@1337:             messages = messages.append(diag);
mcimadamore@1337:             return this;
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         @Override
mcimadamore@1337:         public JCDiagnostic getDiagnostic() {
mcimadamore@1337:             return messages.head;
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         void clear() {
mcimadamore@1337:             messages = List.nil();
mcimadamore@1337:         }
mcimadamore@299:     }
mcimadamore@299: 
mcimadamore@1562:     protected final InferenceException inferenceException;
duke@1: 
mcimadamore@1562:     // <editor-fold defaultstate="collapsed" desc="Inference routines">
mcimadamore@1337:     /**
mcimadamore@1562:      * Main inference entry point - instantiate a generic method type
mcimadamore@1562:      * using given argument types and (possibly) an expected target-type.
duke@1:      */
vromero@2382:     Type instantiateMethod( Env<AttrContext> env,
vromero@2382:                             List<Type> tvars,
vromero@2382:                             MethodType mt,
vromero@2382:                             Attr.ResultInfo resultInfo,
vromero@2382:                             MethodSymbol msym,
vromero@2382:                             List<Type> argtypes,
vromero@2382:                             boolean allowBoxing,
vromero@2382:                             boolean useVarargs,
vromero@2382:                             Resolve.MethodResolutionContext resolveContext,
vromero@2382:                             Warner warn) throws InferenceException {
duke@1:         //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
vromero@2382:         final InferenceContext inferenceContext = new InferenceContext(tvars);  //B0
mcimadamore@1337:         inferenceException.clear();
mcimadamore@1562:         try {
mcimadamore@1562:             DeferredAttr.DeferredAttrContext deferredAttrContext =
mcimadamore@1897:                         resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);
mcimadamore@689: 
vromero@2382:             resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext,   //B2
mcimadamore@1562:                     argtypes, mt.getParameterTypes(), warn);
mcimadamore@1479: 
mcimadamore@1562:             if (allowGraphInference &&
mcimadamore@1562:                     resultInfo != null &&
mcimadamore@1510:                     !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
mcimadamore@1562:                 //inject return constraints earlier
mcimadamore@1562:                 checkWithinBounds(inferenceContext, warn); //propagation
vromero@2382:                 Type newRestype = generateReturnConstraints(env.tree, resultInfo,  //B3
vromero@2382:                         mt, inferenceContext);
mcimadamore@1898:                 mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype);
mcimadamore@1562:                 //propagate outwards if needed
mcimadamore@1562:                 if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) {
mcimadamore@1562:                     //propagate inference context outwards and exit
mcimadamore@1562:                     inferenceContext.dupTo(resultInfo.checkContext.inferenceContext());
mcimadamore@1562:                     deferredAttrContext.complete();
mcimadamore@1562:                     return mt;
mcimadamore@1562:                 }
mcimadamore@1510:             }
mcimadamore@1510: 
mcimadamore@1479:             deferredAttrContext.complete();
duke@1: 
mcimadamore@1337:             // minimize as yet undetermined type variables
mcimadamore@1562:             if (allowGraphInference) {
mcimadamore@1562:                 inferenceContext.solve(warn);
mcimadamore@1562:             } else {
mcimadamore@1562:                 inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst
mcimadamore@1337:             }
duke@1: 
mcimadamore@1550:             mt = (MethodType)inferenceContext.asInstType(mt);
mcimadamore@396: 
mcimadamore@1562:             if (!allowGraphInference &&
mcimadamore@1562:                     inferenceContext.restvars().nonEmpty() &&
mcimadamore@1562:                     resultInfo != null &&
mcimadamore@1562:                     !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
vromero@2382:                 generateReturnConstraints(env.tree, resultInfo, mt, inferenceContext);
mcimadamore@1562:                 inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst
mcimadamore@1562:                 mt = (MethodType)inferenceContext.asInstType(mt);
mcimadamore@1562:             }
duke@1: 
mcimadamore@1562:             if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
mcimadamore@1562:                 log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
mcimadamore@1337:             }
duke@1: 
mcimadamore@1337:             // return instantiated version of method type
mcimadamore@1337:             return mt;
mcimadamore@1337:         } finally {
mcimadamore@1562:             if (resultInfo != null || !allowGraphInference) {
mcimadamore@1562:                 inferenceContext.notifyChange();
mcimadamore@1562:             } else {
mcimadamore@1562:                 inferenceContext.notifyChange(inferenceContext.boundedVars());
mcimadamore@1338:             }
vromero@2382:             if (resultInfo == null) {
vromero@2382:                 /* if the is no result info then we can clear the capture types
vromero@2382:                  * cache without affecting any result info check
vromero@2382:                  */
vromero@2382:                 inferenceContext.captureTypeCache.clear();
vromero@2382:             }
duke@1:         }
mcimadamore@895:     }
duke@1: 
mcimadamore@1562:     /**
mcimadamore@1562:      * Generate constraints from the generic method's return type. If the method
mcimadamore@1562:      * call occurs in a context where a type T is expected, use the expected
mcimadamore@1562:      * type to derive more constraints on the generic method inference variables.
mcimadamore@1562:      */
vromero@2382:     Type generateReturnConstraints(JCTree tree, Attr.ResultInfo resultInfo,
mcimadamore@1562:             MethodType mt, InferenceContext inferenceContext) {
vromero@2368:         InferenceContext rsInfoInfContext = resultInfo.checkContext.inferenceContext();
mcimadamore@1898:         Type from = mt.getReturnType();
mcimadamore@1898:         if (mt.getReturnType().containsAny(inferenceContext.inferencevars) &&
vromero@2368:                 rsInfoInfContext != emptyContext) {
mcimadamore@1898:             from = types.capture(from);
mcimadamore@1898:             //add synthetic captured ivars
mcimadamore@1898:             for (Type t : from.getTypeArguments()) {
mcimadamore@1898:                 if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) {
mcimadamore@1898:                     inferenceContext.addVar((TypeVar)t);
mcimadamore@1898:                 }
mcimadamore@1898:             }
mcimadamore@1898:         }
vromero@2382:         Type qtype = inferenceContext.asUndetVar(from);
vromero@2382:         Type to = resultInfo.pt;
vromero@2382: 
vromero@2382:         if (qtype.hasTag(VOID)) {
vromero@2382:             to = syms.voidType;
vromero@2382:         } else if (to.hasTag(NONE)) {
vromero@2382:             to = from.isPrimitive() ? from : syms.objectType;
vromero@2382:         } else if (qtype.hasTag(UNDETVAR)) {
vromero@2382:             if (resultInfo.pt.isReference()) {
vromero@2382:                 to = generateReturnConstraintsUndetVarToReference(
vromero@2382:                         tree, (UndetVar)qtype, to, resultInfo, inferenceContext);
vromero@2382:             } else {
vromero@2382:                 if (to.isPrimitive()) {
vromero@2382:                     to = generateReturnConstraintsPrimitive(tree, (UndetVar)qtype, to,
vromero@2382:                         resultInfo, inferenceContext);
vromero@2382:                 }
vromero@2382:             }
vromero@2382:         }
vromero@2368:         Assert.check(allowGraphInference || !rsInfoInfContext.free(to),
mcimadamore@1562:                 "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");
mcimadamore@1562:         //we need to skip capture?
mcimadamore@1562:         Warner retWarn = new Warner();
vromero@2382:         if (!resultInfo.checkContext.compatible(qtype, rsInfoInfContext.asUndetVar(to), retWarn) ||
mcimadamore@1800:                 //unchecked conversion is not allowed in source 7 mode
mcimadamore@1800:                 (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) {
mcimadamore@1562:             throw inferenceException
mcimadamore@1562:                     .setMessage("infer.no.conforming.instance.exists",
mcimadamore@1562:                     inferenceContext.restvars(), mt.getReturnType(), to);
mcimadamore@1562:         }
mcimadamore@1898:         return from;
mcimadamore@1562:     }
mcimadamore@1897: 
vromero@2382:     private Type generateReturnConstraintsPrimitive(JCTree tree, UndetVar from,
vromero@2382:             Type to, Attr.ResultInfo resultInfo, InferenceContext inferenceContext) {
vromero@2382:         if (!allowGraphInference) {
vromero@2382:             //if legacy, just return boxed type
vromero@2382:             return types.boxedClass(to).type;
vromero@2382:         }
vromero@2382:         //if graph inference we need to skip conflicting boxed bounds...
vromero@2382:         for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.UPPER,
vromero@2382:                 InferenceBound.LOWER)) {
vromero@2382:             Type boundAsPrimitive = types.unboxedType(t);
vromero@2382:             if (boundAsPrimitive == null || boundAsPrimitive.hasTag(NONE)) {
vromero@2382:                 continue;
mcimadamore@1897:             }
vromero@2382:             return generateReferenceToTargetConstraint(tree, from, to,
vromero@2382:                     resultInfo, inferenceContext);
vromero@2382:         }
vromero@2382:         return types.boxedClass(to).type;
vromero@2382:     }
vromero@2382: 
vromero@2382:     private Type generateReturnConstraintsUndetVarToReference(JCTree tree,
vromero@2382:             UndetVar from, Type to, Attr.ResultInfo resultInfo,
vromero@2382:             InferenceContext inferenceContext) {
vromero@2382:         Type captureOfTo = types.capture(to);
vromero@2382:         /* T is a reference type, but is not a wildcard-parameterized type, and either
vromero@2382:          */
vromero@2382:         if (captureOfTo == to) { //not a wildcard parameterized type
vromero@2382:             /* i) B2 contains a bound of one of the forms alpha = S or S <: alpha,
vromero@2382:              *      where S is a wildcard-parameterized type, or
vromero@2382:              */
vromero@2382:             for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
vromero@2382:                 Type captureOfBound = types.capture(t);
vromero@2382:                 if (captureOfBound != t) {
vromero@2382:                     return generateReferenceToTargetConstraint(tree, from, to,
vromero@2382:                             resultInfo, inferenceContext);
mcimadamore@1562:                 }
mcimadamore@1251:             }
vromero@2382: 
vromero@2382:             /* ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha,
vromero@2382:              * where S1 and S2 have supertypes that are two different
vromero@2382:              * parameterizations of the same generic class or interface.
vromero@2382:              */
vromero@2382:             for (Type aLowerBound : from.getBounds(InferenceBound.LOWER)) {
vromero@2382:                 for (Type anotherLowerBound : from.getBounds(InferenceBound.LOWER)) {
vromero@2382:                     if (aLowerBound != anotherLowerBound &&
vromero@2382:                         commonSuperWithDiffParameterization(aLowerBound, anotherLowerBound)) {
vromero@2382:                         /* self comment check if any lower bound may be and undetVar,
vromero@2382:                          * in that case the result of this call may be a false positive.
vromero@2382:                          * Should this be restricted to non free types?
vromero@2382:                          */
vromero@2382:                         return generateReferenceToTargetConstraint(tree, from, to,
vromero@2382:                             resultInfo, inferenceContext);
vromero@2382:                     }
vromero@2382:                 }
vromero@2382:             }
duke@1:         }
vromero@2382: 
vromero@2382:         /* T is a parameterization of a generic class or interface, G,
vromero@2382:          * and B2 contains a bound of one of the forms alpha = S or S <: alpha,
vromero@2382:          * where there exists no type of the form G<...> that is a
vromero@2382:          * supertype of S, but the raw type G is a supertype of S
vromero@2382:          */
vromero@2382:         if (to.isParameterized()) {
vromero@2382:             for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
vromero@2382:                 Type sup = types.asSuper(t, to.tsym);
vromero@2382:                 if (sup != null && sup.isRaw()) {
vromero@2382:                     return generateReferenceToTargetConstraint(tree, from, to,
vromero@2382:                             resultInfo, inferenceContext);
vromero@2382:                 }
vromero@2382:             }
vromero@2382:         }
vromero@2382:         return to;
vromero@2382:     }
vromero@2382: 
vromero@2382:     private boolean commonSuperWithDiffParameterization(Type t, Type s) {
vromero@2382:         Pair<Type, Type> supers = getParameterizedSupers(t, s);
vromero@2382:         return (supers != null && !types.isSameType(supers.fst, supers.snd));
vromero@2382:     }
vromero@2382: 
vromero@2382:     private Type generateReferenceToTargetConstraint(JCTree tree, UndetVar from,
vromero@2382:             Type to, Attr.ResultInfo resultInfo,
vromero@2382:             InferenceContext inferenceContext) {
vromero@2382:         inferenceContext.solve(List.of(from.qtype), new Warner());
vromero@2543:         inferenceContext.notifyChange();
vromero@2382:         Type capturedType = resultInfo.checkContext.inferenceContext()
vromero@2382:                 .cachedCapture(tree, from.inst, false);
vromero@2382:         if (types.isConvertible(capturedType,
vromero@2382:                 resultInfo.checkContext.inferenceContext().asUndetVar(to))) {
vromero@2382:             //effectively skip additional return-type constraint generation (compatibility)
vromero@2382:             return syms.objectType;
vromero@2382:         }
vromero@2382:         return to;
mcimadamore@1897:     }
mcimadamore@1251: 
mcimadamore@1562:     /**
mcimadamore@1562:       * Infer cyclic inference variables as described in 15.12.2.8.
mcimadamore@1562:       */
mcimadamore@1562:     private void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) {
alundblad@2047:         ListBuffer<Type> todo = new ListBuffer<>();
mcimadamore@1562:         //step 1 - create fresh tvars
mcimadamore@1562:         for (Type t : vars) {
vromero@2368:             UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t);
mcimadamore@1562:             List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER);
mcimadamore@1562:             if (Type.containsAny(upperBounds, vars)) {
jfranck@1689:                 TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
mcimadamore@1562:                 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null);
mcimadamore@1562:                 todo.append(uv);
mcimadamore@1562:                 uv.inst = fresh_tvar.type;
mcimadamore@1562:             } else if (upperBounds.nonEmpty()) {
mcimadamore@1562:                 uv.inst = types.glb(upperBounds);
mcimadamore@1562:             } else {
mcimadamore@1562:                 uv.inst = syms.objectType;
mcimadamore@1338:             }
mcimadamore@1562:         }
mcimadamore@1562:         //step 2 - replace fresh tvars in their bounds
mcimadamore@1562:         List<Type> formals = vars;
mcimadamore@1562:         for (Type t : todo) {
mcimadamore@1562:             UndetVar uv = (UndetVar)t;
mcimadamore@1562:             TypeVar ct = (TypeVar)uv.inst;
mcimadamore@1562:             ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct)));
mcimadamore@1562:             if (ct.bound.isErroneous()) {
mcimadamore@1562:                 //report inference error if glb fails
mcimadamore@1562:                 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
mcimadamore@1338:             }
mcimadamore@1562:             formals = formals.tail;
mcimadamore@1348:         }
mcimadamore@1348:     }
mcimadamore@1348: 
mcimadamore@674:     /**
mcimadamore@674:      * Compute a synthetic method type corresponding to the requested polymorphic
mcimadamore@820:      * method signature. The target return type is computed from the immediately
mcimadamore@820:      * enclosing scope surrounding the polymorphic-signature call.
mcimadamore@674:      */
mcimadamore@1239:     Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
mcimadamore@674:                                             MethodSymbol spMethod,  // sig. poly. method or null if none
mcimadamore@1347:                                             Resolve.MethodResolutionContext resolveContext,
mcimadamore@820:                                             List<Type> argtypes) {
mcimadamore@674:         final Type restype;
mcimadamore@716: 
mcimadamore@820:         //The return type for a polymorphic signature call is computed from
mcimadamore@820:         //the enclosing tree E, as follows: if E is a cast, then use the
mcimadamore@820:         //target type of the cast expression as a return type; if E is an
mcimadamore@820:         //expression statement, the return type is 'void' - otherwise the
mcimadamore@820:         //return type is simply 'Object'. A correctness check ensures that
mcimadamore@820:         //env.next refers to the lexically enclosing environment in which
mcimadamore@820:         //the polymorphic signature call environment is nested.
mcimadamore@820: 
mcimadamore@820:         switch (env.next.tree.getTag()) {
jjg@1127:             case TYPECAST:
mcimadamore@820:                 JCTypeCast castTree = (JCTypeCast)env.next.tree;
mcimadamore@820:                 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
mcimadamore@820:                     castTree.clazz.type :
mcimadamore@820:                     syms.objectType;
mcimadamore@820:                 break;
jjg@1127:             case EXEC:
mcimadamore@820:                 JCTree.JCExpressionStatement execTree =
mcimadamore@820:                         (JCTree.JCExpressionStatement)env.next.tree;
mcimadamore@820:                 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
mcimadamore@820:                     syms.voidType :
mcimadamore@820:                     syms.objectType;
mcimadamore@820:                 break;
mcimadamore@820:             default:
mcimadamore@820:                 restype = syms.objectType;
mcimadamore@674:         }
mcimadamore@674: 
mcimadamore@1347:         List<Type> paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step));
mcimadamore@674:         List<Type> exType = spMethod != null ?
mcimadamore@674:             spMethod.getThrownTypes() :
mcimadamore@674:             List.of(syms.throwableType); // make it throw all exceptions
mcimadamore@674: 
mcimadamore@674:         MethodType mtype = new MethodType(paramtypes,
mcimadamore@674:                                           restype,
mcimadamore@674:                                           exType,
mcimadamore@674:                                           syms.methodClass);
mcimadamore@674:         return mtype;
mcimadamore@674:     }
mcimadamore@674:     //where
mcimadamore@1347:         class ImplicitArgType extends DeferredAttr.DeferredTypeMap {
mcimadamore@1347: 
mcimadamore@1347:             public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {
vromero@2543:                 (rs.deferredAttr).super(AttrMode.SPECULATIVE, msym, phase);
mcimadamore@1347:             }
mcimadamore@1347: 
mcimadamore@1347:             public Type apply(Type t) {
mcimadamore@1347:                 t = types.erasure(super.apply(t));
jjg@1374:                 if (t.hasTag(BOT))
mcimadamore@1347:                     // nulls type as the marker type Null (which has no instances)
mcimadamore@1347:                     // infer as java.lang.Void for now
mcimadamore@1347:                     t = types.boxedClass(syms.voidType).type;
mcimadamore@1347:                 return t;
mcimadamore@1347:             }
mcimadamore@1347:         }
mcimadamore@1337: 
mcimadamore@1337:     /**
mcimadamore@1562:       * This method is used to infer a suitable target SAM in case the original
mcimadamore@1562:       * SAM type contains one or more wildcards. An inference process is applied
mcimadamore@1562:       * so that wildcard bounds, as well as explicit lambda/method ref parameters
mcimadamore@1562:       * (where applicable) are used to constraint the solution.
mcimadamore@1562:       */
mcimadamore@1562:     public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,
mcimadamore@1562:             List<Type> paramTypes, Check.CheckContext checkContext) {
mcimadamore@1562:         if (types.capture(funcInterface) == funcInterface) {
mcimadamore@1562:             //if capture doesn't change the type then return the target unchanged
mcimadamore@1562:             //(this means the target contains no wildcards!)
mcimadamore@1562:             return funcInterface;
mcimadamore@1562:         } else {
mcimadamore@1562:             Type formalInterface = funcInterface.tsym.type;
mcimadamore@1562:             InferenceContext funcInterfaceContext =
mcimadamore@1562:                     new InferenceContext(funcInterface.tsym.type.getTypeArguments());
mcimadamore@1562: 
mcimadamore@1562:             Assert.check(paramTypes != null);
mcimadamore@1562:             //get constraints from explicit params (this is done by
mcimadamore@1562:             //checking that explicit param types are equal to the ones
mcimadamore@1562:             //in the functional interface descriptors)
mcimadamore@1562:             List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();
mcimadamore@1562:             if (descParameterTypes.size() != paramTypes.size()) {
mcimadamore@1562:                 checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda"));
mcimadamore@1562:                 return types.createErrorType(funcInterface);
mcimadamore@1562:             }
mcimadamore@1562:             for (Type p : descParameterTypes) {
vromero@2368:                 if (!types.isSameType(funcInterfaceContext.asUndetVar(p), paramTypes.head)) {
mcimadamore@1562:                     checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562:                     return types.createErrorType(funcInterface);
mcimadamore@1562:                 }
mcimadamore@1562:                 paramTypes = paramTypes.tail;
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             try {
mcimadamore@1562:                 funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings);
mcimadamore@1562:             } catch (InferenceException ex) {
mcimadamore@1562:                 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             List<Type> actualTypeargs = funcInterface.getTypeArguments();
mcimadamore@1562:             for (Type t : funcInterfaceContext.undetvars) {
mcimadamore@1562:                 UndetVar uv = (UndetVar)t;
mcimadamore@1562:                 if (uv.inst == null) {
mcimadamore@1562:                     uv.inst = actualTypeargs.head;
mcimadamore@1562:                 }
mcimadamore@1562:                 actualTypeargs = actualTypeargs.tail;
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             Type owntype = funcInterfaceContext.asInstType(formalInterface);
mcimadamore@1562:             if (!chk.checkValidGenericType(owntype)) {
mcimadamore@1562:                 //if the inferred functional interface type is not well-formed,
mcimadamore@1562:                 //or if it's not a subtype of the original target, issue an error
mcimadamore@1562:                 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562:             }
vromero@2543:             //propagate constraints as per JLS 18.2.1
vromero@2543:             checkContext.compatible(owntype, funcInterface, types.noWarnings);
mcimadamore@1562:             return owntype;
mcimadamore@1562:         }
mcimadamore@1562:     }
mcimadamore@1562:     // </editor-fold>
mcimadamore@1562: 
mcimadamore@1562:     // <editor-fold defaultstate="collapsed" desc="Bound checking">
mcimadamore@1562:     /**
mcimadamore@1562:      * Check bounds and perform incorporation
mcimadamore@1562:      */
mcimadamore@1562:     void checkWithinBounds(InferenceContext inferenceContext,
mcimadamore@1562:                              Warner warn) throws InferenceException {
mcimadamore@1562:         MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars);
mcimadamore@1891:         List<Type> saved_undet = inferenceContext.save();
mcimadamore@1562:         try {
mcimadamore@1562:             while (true) {
mcimadamore@1562:                 mlistener.reset();
mcimadamore@1562:                 if (!allowGraphInference) {
mcimadamore@1562:                     //in legacy mode we lack of transitivity, so bound check
mcimadamore@1562:                     //cannot be run in parallel with other incoprporation rounds
mcimadamore@1562:                     for (Type t : inferenceContext.undetvars) {
mcimadamore@1562:                         UndetVar uv = (UndetVar)t;
mcimadamore@1562:                         IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn);
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:                 for (Type t : inferenceContext.undetvars) {
mcimadamore@1562:                     UndetVar uv = (UndetVar)t;
mcimadamore@1562:                     //bound incorporation
mcimadamore@1562:                     EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?
mcimadamore@1562:                             incorporationStepsGraph : incorporationStepsLegacy;
mcimadamore@1562:                     for (IncorporationStep is : incorporationSteps) {
mcimadamore@1898:                         if (is.accepts(uv, inferenceContext)) {
mcimadamore@1898:                             is.apply(uv, inferenceContext, warn);
mcimadamore@1898:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:                 if (!mlistener.changed || !allowGraphInference) break;
mcimadamore@1562:             }
mcimadamore@1562:         }
mcimadamore@1562:         finally {
mcimadamore@1562:             mlistener.detach();
mcimadamore@1905:             if (incorporationCache.size() == MAX_INCORPORATION_STEPS) {
mcimadamore@1891:                 inferenceContext.rollback(saved_undet);
mcimadamore@1891:             }
mcimadamore@1905:             incorporationCache.clear();
mcimadamore@1562:         }
mcimadamore@1562:     }
mcimadamore@1562:     //where
mcimadamore@1562:         /**
mcimadamore@1562:          * This listener keeps track of changes on a group of inference variable
mcimadamore@1562:          * bounds. Note: the listener must be detached (calling corresponding
mcimadamore@1562:          * method) to make sure that the underlying inference variable is
mcimadamore@1562:          * left in a clean state.
mcimadamore@1562:          */
mcimadamore@1562:         class MultiUndetVarListener implements UndetVar.UndetVarListener {
mcimadamore@1562: 
mcimadamore@1562:             boolean changed;
mcimadamore@1562:             List<Type> undetvars;
mcimadamore@1562: 
mcimadamore@1562:             public MultiUndetVarListener(List<Type> undetvars) {
mcimadamore@1562:                 this.undetvars = undetvars;
mcimadamore@1562:                 for (Type t : undetvars) {
mcimadamore@1562:                     UndetVar uv = (UndetVar)t;
mcimadamore@1562:                     uv.listener = this;
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             public void varChanged(UndetVar uv, Set<InferenceBound> ibs) {
mcimadamore@1562:                 //avoid non-termination
mcimadamore@1905:                 if (incorporationCache.size() < MAX_INCORPORATION_STEPS) {
mcimadamore@1562:                     changed = true;
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             void reset() {
mcimadamore@1562:                 changed = false;
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             void detach() {
mcimadamore@1562:                 for (Type t : undetvars) {
mcimadamore@1562:                     UndetVar uv = (UndetVar)t;
mcimadamore@1562:                     uv.listener = null;
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         };
mcimadamore@1562: 
mcimadamore@1562:         /** max number of incorporation rounds */
mcimadamore@1562:         static final int MAX_INCORPORATION_STEPS = 100;
mcimadamore@1562: 
vromero@2369:     /* If for two types t and s there is a least upper bound that is a
vromero@2369:      * parameterized type G, then there exists a supertype of 't' of the form
vromero@2369:      * G<T1, ..., Tn> and a supertype of 's' of the form G<S1, ..., Sn>
vromero@2369:      * which will be returned by this method. If no such supertypes exists then
vromero@2369:      * null is returned.
vromero@2369:      *
vromero@2369:      * As an example for the following input:
vromero@2369:      *
vromero@2369:      * t = java.util.ArrayList<java.lang.String>
vromero@2369:      * s = java.util.List<T>
vromero@2369:      *
vromero@2369:      * we get this ouput:
vromero@2369:      *
vromero@2369:      * Pair[java.util.List<java.lang.String>,java.util.List<T>]
vromero@2369:      */
vromero@2369:     private Pair<Type, Type> getParameterizedSupers(Type t, Type s) {
vromero@2369:         Type lubResult = types.lub(t, s);
vromero@2369:         if (lubResult == syms.errType || lubResult == syms.botType ||
vromero@2369:                 !lubResult.isParameterized()) {
vromero@2369:             return null;
vromero@2369:         }
vromero@2369:         Type asSuperOfT = types.asSuper(t, lubResult.tsym);
vromero@2369:         Type asSuperOfS = types.asSuper(s, lubResult.tsym);
vromero@2369:         return new Pair<>(asSuperOfT, asSuperOfS);
vromero@2369:     }
vromero@2369: 
mcimadamore@1562:     /**
mcimadamore@1562:      * This enumeration defines an entry point for doing inference variable
mcimadamore@1562:      * bound incorporation - it can be used to inject custom incorporation
mcimadamore@1562:      * logic into the basic bound checking routine
mcimadamore@1562:      */
mcimadamore@1562:     enum IncorporationStep {
mcimadamore@1562:         /**
mcimadamore@1562:          * Performs basic bound checking - i.e. is the instantiated type for a given
mcimadamore@1562:          * inference variable compatible with its bounds?
mcimadamore@1562:          */
mcimadamore@1562:         CHECK_BOUNDS() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types);
mcimadamore@1562:                 infer.checkCompatibleUpperBounds(uv, inferenceContext);
mcimadamore@1562:                 if (uv.inst != null) {
mcimadamore@1562:                     Type inst = uv.inst;
mcimadamore@1562:                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {
vromero@2368:                         if (!isSubtype(inst, inferenceContext.asUndetVar(u), warn, infer)) {
mcimadamore@1562:                             infer.reportBoundError(uv, BoundErrorKind.UPPER);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {
vromero@2368:                         if (!isSubtype(inferenceContext.asUndetVar(l), inst, warn, infer)) {
mcimadamore@1562:                             infer.reportBoundError(uv, BoundErrorKind.LOWER);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                     for (Type e : uv.getBounds(InferenceBound.EQ)) {
vromero@2368:                         if (!isSameType(inst, inferenceContext.asUndetVar(e), infer)) {
mcimadamore@1562:                             infer.reportBoundError(uv, BoundErrorKind.EQ);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
vromero@2368: 
mcimadamore@1898:             @Override
mcimadamore@1898:             boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1898:                 //applies to all undetvars
mcimadamore@1898:                 return true;
mcimadamore@1898:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Check consistency of equality constraints. This is a slightly more aggressive
mcimadamore@1562:          * inference routine that is designed as to maximize compatibility with JDK 7.
mcimadamore@1562:          * Note: this is not used in graph mode.
mcimadamore@1562:          */
mcimadamore@1562:         EQ_CHECK_LEGACY() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 Type eq = null;
mcimadamore@1562:                 for (Type e : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562:                     Assert.check(!inferenceContext.free(e));
mcimadamore@1905:                     if (eq != null && !isSameType(e, eq, infer)) {
mcimadamore@1562:                         infer.reportBoundError(uv, BoundErrorKind.EQ);
mcimadamore@1562:                     }
mcimadamore@1562:                     eq = e;
mcimadamore@1562:                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562:                         Assert.check(!inferenceContext.free(l));
mcimadamore@1905:                         if (!isSubtype(l, e, warn, infer)) {
mcimadamore@1562:                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562:                         if (inferenceContext.free(u)) continue;
mcimadamore@1905:                         if (!isSubtype(e, u, warn, infer)) {
mcimadamore@1562:                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Check consistency of equality constraints.
mcimadamore@1562:          */
mcimadamore@1562:         EQ_CHECK() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 for (Type e : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562:                     if (e.containsAny(inferenceContext.inferenceVars())) continue;
mcimadamore@1562:                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {
vromero@2368:                         if (!isSubtype(e, inferenceContext.asUndetVar(u), warn, infer)) {
mcimadamore@1562:                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {
vromero@2368:                         if (!isSubtype(inferenceContext.asUndetVar(l), e, warn, infer)) {
mcimadamore@1562:                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Given a bound set containing {@code alpha <: T} and {@code alpha :> S}
mcimadamore@1562:          * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562:          */
mcimadamore@1562:         CROSS_UPPER_LOWER() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562:                     for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
vromero@2368:                         isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn , infer);
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Given a bound set containing {@code alpha <: T} and {@code alpha == S}
mcimadamore@1562:          * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562:          */
mcimadamore@1562:         CROSS_UPPER_EQ() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562:                     for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
vromero@2368:                         isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn, infer);
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Given a bound set containing {@code alpha :> S} and {@code alpha == T}
mcimadamore@1562:          * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562:          */
mcimadamore@1562:         CROSS_EQ_LOWER() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562:                     for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
vromero@2368:                         isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn, infer);
mcimadamore@1655:                     }
mcimadamore@1655:                 }
mcimadamore@1655:             }
mcimadamore@1655:         },
mcimadamore@1655:         /**
vromero@2369:          * Given a bound set containing {@code alpha <: P<T>} and
vromero@2369:          * {@code alpha <: P<S>} where P is a parameterized type,
vromero@2369:          * perform {@code T = S} (which could lead to new bounds).
vromero@2369:          */
vromero@2369:         CROSS_UPPER_UPPER() {
vromero@2369:             @Override
vromero@2369:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
vromero@2369:                 Infer infer = inferenceContext.infer();
vromero@2369:                 List<Type> boundList = uv.getBounds(InferenceBound.UPPER);
vromero@2369:                 List<Type> boundListTail = boundList.tail;
vromero@2369:                 while (boundList.nonEmpty()) {
vromero@2369:                     List<Type> tmpTail = boundListTail;
vromero@2369:                     while (tmpTail.nonEmpty()) {
vromero@2369:                         Type b1 = boundList.head;
vromero@2369:                         Type b2 = tmpTail.head;
vromero@2369:                         if (b1 != b2) {
vromero@2369:                             Pair<Type, Type> commonSupers = infer.getParameterizedSupers(b1, b2);
vromero@2369:                             if (commonSupers != null) {
vromero@2369:                                 List<Type> allParamsSuperBound1 = commonSupers.fst.allparams();
vromero@2369:                                 List<Type> allParamsSuperBound2 = commonSupers.snd.allparams();
vromero@2369:                                 while (allParamsSuperBound1.nonEmpty() && allParamsSuperBound2.nonEmpty()) {
vromero@2369:                                     //traverse the list of all params comparing them
vromero@2369:                                     if (!allParamsSuperBound1.head.hasTag(WILDCARD) &&
vromero@2369:                                         !allParamsSuperBound2.head.hasTag(WILDCARD)) {
vromero@2369:                                         isSameType(inferenceContext.asUndetVar(allParamsSuperBound1.head),
vromero@2369:                                             inferenceContext.asUndetVar(allParamsSuperBound2.head), infer);
vromero@2369:                                     }
vromero@2369:                                     allParamsSuperBound1 = allParamsSuperBound1.tail;
vromero@2369:                                     allParamsSuperBound2 = allParamsSuperBound2.tail;
vromero@2369:                                 }
vromero@2369:                                 Assert.check(allParamsSuperBound1.isEmpty() && allParamsSuperBound2.isEmpty());
vromero@2369:                             }
vromero@2369:                         }
vromero@2369:                         tmpTail = tmpTail.tail;
vromero@2369:                     }
vromero@2369:                     boundList = boundList.tail;
vromero@2369:                     boundListTail = boundList.tail;
vromero@2369:                 }
vromero@2369:             }
vromero@2369: 
vromero@2369:             @Override
vromero@2369:             boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
vromero@2369:                 return !uv.isCaptured() &&
vromero@2369:                         uv.getBounds(InferenceBound.UPPER).nonEmpty();
vromero@2369:             }
vromero@2369:         },
vromero@2369:         /**
mcimadamore@1655:          * Given a bound set containing {@code alpha == S} and {@code alpha == T}
mcimadamore@1655:          * perform {@code S == T} (which could lead to new bounds).
mcimadamore@1655:          */
mcimadamore@1655:         CROSS_EQ_EQ() {
mcimadamore@1655:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1655:                 Infer infer = inferenceContext.infer();
mcimadamore@1655:                 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1655:                     for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1655:                         if (b1 != b2) {
vromero@2368:                             isSameType(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), infer);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Given a bound set containing {@code alpha <: beta} propagate lower bounds
mcimadamore@1562:          * from alpha to beta; also propagate upper bounds from beta to alpha.
mcimadamore@1562:          */
mcimadamore@1562:         PROP_UPPER() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 for (Type b : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562:                     if (inferenceContext.inferenceVars().contains(b)) {
vromero@2368:                         UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
mcimadamore@1898:                         if (uv2.isCaptured()) continue;
mcimadamore@1562:                         //alpha <: beta
mcimadamore@1628:                         //0. set beta :> alpha
mcimadamore@1905:                         addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(uv.qtype), infer);
mcimadamore@1562:                         //1. copy alpha's lower to beta's
mcimadamore@1562:                         for (Type l : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1905:                             addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(l), infer);
mcimadamore@1562:                         }
mcimadamore@1562:                         //2. copy beta's upper to alpha's
mcimadamore@1562:                         for (Type u : uv2.getBounds(InferenceBound.UPPER)) {
mcimadamore@1905:                             addBound(InferenceBound.UPPER, uv, inferenceContext.asInstType(u), infer);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Given a bound set containing {@code alpha :> beta} propagate lower bounds
mcimadamore@1562:          * from beta to alpha; also propagate upper bounds from alpha to beta.
mcimadamore@1562:          */
mcimadamore@1562:         PROP_LOWER() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 for (Type b : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562:                     if (inferenceContext.inferenceVars().contains(b)) {
vromero@2368:                         UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
mcimadamore@1898:                         if (uv2.isCaptured()) continue;
mcimadamore@1562:                         //alpha :> beta
mcimadamore@1628:                         //0. set beta <: alpha
mcimadamore@1905:                         addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(uv.qtype), infer);
mcimadamore@1562:                         //1. copy alpha's upper to beta's
mcimadamore@1562:                         for (Type u : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1905:                             addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(u), infer);
mcimadamore@1562:                         }
mcimadamore@1562:                         //2. copy beta's lower to alpha's
mcimadamore@1562:                         for (Type l : uv2.getBounds(InferenceBound.LOWER)) {
mcimadamore@1905:                             addBound(InferenceBound.LOWER, uv, inferenceContext.asInstType(l), infer);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Given a bound set containing {@code alpha == beta} propagate lower/upper
mcimadamore@1562:          * bounds from alpha to beta and back.
mcimadamore@1562:          */
mcimadamore@1562:         PROP_EQ() {
mcimadamore@1562:             public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 for (Type b : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562:                     if (inferenceContext.inferenceVars().contains(b)) {
vromero@2368:                         UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
mcimadamore@1898:                         if (uv2.isCaptured()) continue;
mcimadamore@1562:                         //alpha == beta
mcimadamore@1628:                         //0. set beta == alpha
mcimadamore@1905:                         addBound(InferenceBound.EQ, uv2, inferenceContext.asInstType(uv.qtype), infer);
mcimadamore@1562:                         //1. copy all alpha's bounds to beta's
mcimadamore@1562:                         for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562:                             for (Type b2 : uv.getBounds(ib)) {
mcimadamore@1562:                                 if (b2 != uv2) {
mcimadamore@1905:                                     addBound(ib, uv2, inferenceContext.asInstType(b2), infer);
mcimadamore@1562:                                 }
mcimadamore@1562:                             }
mcimadamore@1562:                         }
mcimadamore@1562:                         //2. copy all beta's bounds to alpha's
mcimadamore@1562:                         for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562:                             for (Type b2 : uv2.getBounds(ib)) {
mcimadamore@1562:                                 if (b2 != uv) {
mcimadamore@1905:                                     addBound(ib, uv, inferenceContext.asInstType(b2), infer);
mcimadamore@1562:                                 }
mcimadamore@1562:                             }
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         };
mcimadamore@1562: 
mcimadamore@1562:         abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn);
mcimadamore@1898: 
mcimadamore@1898:         boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1898:             return !uv.isCaptured();
mcimadamore@1898:         }
mcimadamore@1905: 
mcimadamore@1905:         boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
mcimadamore@1905:             return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         boolean isSameType(Type s, Type t, Infer infer) {
mcimadamore@1905:             return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
mcimadamore@1905:             doIncorporationOp(opFor(ib), uv, b, null, infer);
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
mcimadamore@1905:             switch (boundKind) {
mcimadamore@1905:                 case EQ:
mcimadamore@1905:                     return IncorporationBinaryOpKind.ADD_EQ_BOUND;
mcimadamore@1905:                 case LOWER:
mcimadamore@1905:                     return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
mcimadamore@1905:                 case UPPER:
mcimadamore@1905:                     return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
mcimadamore@1905:                 default:
mcimadamore@1905:                     Assert.error("Can't get here!");
mcimadamore@1905:                     return null;
mcimadamore@1905:             }
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
mcimadamore@1905:             IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
mcimadamore@1905:             Boolean res = infer.incorporationCache.get(newOp);
mcimadamore@1905:             if (res == null) {
mcimadamore@1905:                 infer.incorporationCache.put(newOp, res = newOp.apply(warn));
mcimadamore@1905:             }
mcimadamore@1905:             return res;
mcimadamore@1905:         }
mcimadamore@1562:     }
mcimadamore@1562: 
mcimadamore@1562:     /** incorporation steps to be executed when running in legacy mode */
mcimadamore@1562:     EnumSet<IncorporationStep> incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY);
mcimadamore@1562: 
mcimadamore@1562:     /** incorporation steps to be executed when running in graph mode */
mcimadamore@1562:     EnumSet<IncorporationStep> incorporationStepsGraph =
mcimadamore@1562:             EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY));
mcimadamore@1562: 
mcimadamore@1562:     /**
mcimadamore@1905:      * Three kinds of basic operation are supported as part of an incorporation step:
mcimadamore@1905:      * (i) subtype check, (ii) same type check and (iii) bound addition (either
mcimadamore@1905:      * upper/lower/eq bound).
mcimadamore@1905:      */
mcimadamore@1905:     enum IncorporationBinaryOpKind {
mcimadamore@1905:         IS_SUBTYPE() {
mcimadamore@1905:             @Override
mcimadamore@1905:             boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905:                 return types.isSubtypeUnchecked(op1, op2, warn);
mcimadamore@1905:             }
mcimadamore@1905:         },
mcimadamore@1905:         IS_SAME_TYPE() {
mcimadamore@1905:             @Override
mcimadamore@1905:             boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905:                 return types.isSameType(op1, op2);
mcimadamore@1905:             }
mcimadamore@1905:         },
mcimadamore@1905:         ADD_UPPER_BOUND() {
mcimadamore@1905:             @Override
mcimadamore@1905:             boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905:                 UndetVar uv = (UndetVar)op1;
mcimadamore@1905:                 uv.addBound(InferenceBound.UPPER, op2, types);
mcimadamore@1905:                 return true;
mcimadamore@1905:             }
mcimadamore@1905:         },
mcimadamore@1905:         ADD_LOWER_BOUND() {
mcimadamore@1905:             @Override
mcimadamore@1905:             boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905:                 UndetVar uv = (UndetVar)op1;
mcimadamore@1905:                 uv.addBound(InferenceBound.LOWER, op2, types);
mcimadamore@1905:                 return true;
mcimadamore@1905:             }
mcimadamore@1905:         },
mcimadamore@1905:         ADD_EQ_BOUND() {
mcimadamore@1905:             @Override
mcimadamore@1905:             boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905:                 UndetVar uv = (UndetVar)op1;
mcimadamore@1905:                 uv.addBound(InferenceBound.EQ, op2, types);
mcimadamore@1905:                 return true;
mcimadamore@1905:             }
mcimadamore@1905:         };
mcimadamore@1905: 
mcimadamore@1905:         abstract boolean apply(Type op1, Type op2, Warner warn, Types types);
mcimadamore@1905:     }
mcimadamore@1905: 
mcimadamore@1905:     /**
mcimadamore@1905:      * This class encapsulates a basic incorporation operation; incorporation
mcimadamore@1905:      * operations takes two type operands and a kind. Each operation performed
mcimadamore@1905:      * during an incorporation round is stored in a cache, so that operations
mcimadamore@1905:      * are not executed unnecessarily (which would potentially lead to adding
mcimadamore@1905:      * same bounds over and over).
mcimadamore@1905:      */
mcimadamore@1905:     class IncorporationBinaryOp {
mcimadamore@1905: 
mcimadamore@1905:         IncorporationBinaryOpKind opKind;
mcimadamore@1905:         Type op1;
mcimadamore@1905:         Type op2;
mcimadamore@1905: 
mcimadamore@1905:         IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) {
mcimadamore@1905:             this.opKind = opKind;
mcimadamore@1905:             this.op1 = op1;
mcimadamore@1905:             this.op2 = op2;
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         @Override
mcimadamore@1905:         public boolean equals(Object o) {
mcimadamore@1905:             if (!(o instanceof IncorporationBinaryOp)) {
mcimadamore@1905:                 return false;
mcimadamore@1905:             } else {
mcimadamore@1905:                 IncorporationBinaryOp that = (IncorporationBinaryOp)o;
mcimadamore@1905:                 return opKind == that.opKind &&
mcimadamore@1905:                         types.isSameType(op1, that.op1, true) &&
mcimadamore@1905:                         types.isSameType(op2, that.op2, true);
mcimadamore@1905:             }
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         @Override
mcimadamore@1905:         public int hashCode() {
mcimadamore@1905:             int result = opKind.hashCode();
mcimadamore@1905:             result *= 127;
mcimadamore@1905:             result += types.hashCode(op1);
mcimadamore@1905:             result *= 127;
mcimadamore@1905:             result += types.hashCode(op2);
mcimadamore@1905:             return result;
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         boolean apply(Warner warn) {
mcimadamore@1905:             return opKind.apply(op1, op2, warn, types);
mcimadamore@1905:         }
mcimadamore@1905:     }
mcimadamore@1905: 
mcimadamore@1905:     /** an incorporation cache keeps track of all executed incorporation-related operations */
mcimadamore@1905:     Map<IncorporationBinaryOp, Boolean> incorporationCache =
mcimadamore@1905:             new HashMap<IncorporationBinaryOp, Boolean>();
mcimadamore@1905: 
mcimadamore@1905:     /**
mcimadamore@1562:      * Make sure that the upper bounds we got so far lead to a solvable inference
mcimadamore@1562:      * variable by making sure that a glb exists.
mcimadamore@1562:      */
mcimadamore@1562:     void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562:         List<Type> hibounds =
mcimadamore@1562:                 Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));
mcimadamore@1562:         Type hb = null;
mcimadamore@1562:         if (hibounds.isEmpty())
mcimadamore@1562:             hb = syms.objectType;
mcimadamore@1562:         else if (hibounds.tail.isEmpty())
mcimadamore@1562:             hb = hibounds.head;
mcimadamore@1562:         else
mcimadamore@1562:             hb = types.glb(hibounds);
mcimadamore@1562:         if (hb == null || hb.isErroneous())
mcimadamore@1562:             reportBoundError(uv, BoundErrorKind.BAD_UPPER);
mcimadamore@1562:     }
mcimadamore@1562:     //where
mcimadamore@1562:         protected static class BoundFilter implements Filter<Type> {
mcimadamore@1562: 
mcimadamore@1562:             InferenceContext inferenceContext;
mcimadamore@1562: 
mcimadamore@1562:             public BoundFilter(InferenceContext inferenceContext) {
mcimadamore@1562:                 this.inferenceContext = inferenceContext;
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             @Override
mcimadamore@1562:             public boolean accepts(Type t) {
mcimadamore@1562:                 return !t.isErroneous() && !inferenceContext.free(t) &&
mcimadamore@1562:                         !t.hasTag(BOT);
mcimadamore@1562:             }
mcimadamore@1562:         };
mcimadamore@1562: 
mcimadamore@1562:     /**
mcimadamore@1562:      * This enumeration defines all possible bound-checking related errors.
mcimadamore@1562:      */
mcimadamore@1562:     enum BoundErrorKind {
mcimadamore@1562:         /**
mcimadamore@1562:          * The (uninstantiated) inference variable has incompatible upper bounds.
mcimadamore@1562:          */
mcimadamore@1562:         BAD_UPPER() {
mcimadamore@1562:             @Override
mcimadamore@1562:             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562:                 return ex.setMessage("incompatible.upper.bounds", uv.qtype,
mcimadamore@1562:                         uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * An equality constraint is not compatible with an upper bound.
mcimadamore@1562:          */
mcimadamore@1562:         BAD_EQ_UPPER() {
mcimadamore@1562:             @Override
mcimadamore@1562:             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562:                 return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype,
mcimadamore@1562:                         uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * An equality constraint is not compatible with a lower bound.
mcimadamore@1562:          */
mcimadamore@1562:         BAD_EQ_LOWER() {
mcimadamore@1562:             @Override
mcimadamore@1562:             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562:                 return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype,
mcimadamore@1562:                         uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER));
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Instantiated inference variable is not compatible with an upper bound.
mcimadamore@1562:          */
mcimadamore@1562:         UPPER() {
mcimadamore@1562:             @Override
mcimadamore@1562:             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562:                 return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst,
mcimadamore@1562:                         uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Instantiated inference variable is not compatible with a lower bound.
mcimadamore@1562:          */
mcimadamore@1562:         LOWER() {
mcimadamore@1562:             @Override
mcimadamore@1562:             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562:                 return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst,
mcimadamore@1562:                         uv.getBounds(InferenceBound.LOWER));
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Instantiated inference variable is not compatible with an equality constraint.
mcimadamore@1562:          */
mcimadamore@1562:         EQ() {
mcimadamore@1562:             @Override
mcimadamore@1562:             InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562:                 return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst,
mcimadamore@1562:                         uv.getBounds(InferenceBound.EQ));
mcimadamore@1562:             }
mcimadamore@1562:         };
mcimadamore@1562: 
mcimadamore@1562:         abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
mcimadamore@1562:     }
mcimadamore@1562: 
mcimadamore@1562:     /**
mcimadamore@1562:      * Report a bound-checking error of given kind
mcimadamore@1562:      */
mcimadamore@1562:     void reportBoundError(UndetVar uv, BoundErrorKind bk) {
mcimadamore@1562:         throw bk.setMessage(inferenceException, uv);
mcimadamore@1562:     }
mcimadamore@1562:     // </editor-fold>
mcimadamore@1562: 
mcimadamore@1562:     // <editor-fold defaultstate="collapsed" desc="Inference engine">
mcimadamore@1562:     /**
mcimadamore@1562:      * Graph inference strategy - act as an input to the inference solver; a strategy is
mcimadamore@1562:      * composed of two ingredients: (i) find a node to solve in the inference graph,
mcimadamore@1562:      * and (ii) tell th engine when we are done fixing inference variables
mcimadamore@1562:      */
mcimadamore@1562:     interface GraphStrategy {
vromero@2000: 
vromero@2000:         /**
vromero@2000:          * A NodeNotFoundException is thrown whenever an inference strategy fails
vromero@2000:          * to pick the next node to solve in the inference graph.
vromero@2000:          */
vromero@2000:         public static class NodeNotFoundException extends RuntimeException {
vromero@2000:             private static final long serialVersionUID = 0;
vromero@2000: 
vromero@2000:             InferenceGraph graph;
vromero@2000: 
vromero@2000:             public NodeNotFoundException(InferenceGraph graph) {
vromero@2000:                 this.graph = graph;
vromero@2000:             }
vromero@2000:         }
mcimadamore@1562:         /**
mcimadamore@1562:          * Pick the next node (leaf) to solve in the graph
mcimadamore@1562:          */
vromero@2000:         Node pickNode(InferenceGraph g) throws NodeNotFoundException;
mcimadamore@1562:         /**
mcimadamore@1562:          * Is this the last step?
mcimadamore@1562:          */
mcimadamore@1562:         boolean done();
mcimadamore@1562:     }
mcimadamore@1562: 
mcimadamore@1562:     /**
mcimadamore@1562:      * Simple solver strategy class that locates all leaves inside a graph
mcimadamore@1562:      * and picks the first leaf as the next node to solve
mcimadamore@1562:      */
mcimadamore@1562:     abstract class LeafSolver implements GraphStrategy {
mcimadamore@1562:         public Node pickNode(InferenceGraph g) {
vromero@2000:             if (g.nodes.isEmpty()) {
vromero@2000:                 //should not happen
vromero@2000:                 throw new NodeNotFoundException(g);
vromero@2000:             };
mcimadamore@1562:             return g.nodes.get(0);
mcimadamore@1562:         }
mcimadamore@1905: 
mcimadamore@1905:         boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
mcimadamore@1905:             return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         boolean isSameType(Type s, Type t, Infer infer) {
mcimadamore@1905:             return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
mcimadamore@1905:             doIncorporationOp(opFor(ib), uv, b, null, infer);
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
mcimadamore@1905:             switch (boundKind) {
mcimadamore@1905:                 case EQ:
mcimadamore@1905:                     return IncorporationBinaryOpKind.ADD_EQ_BOUND;
mcimadamore@1905:                 case LOWER:
mcimadamore@1905:                     return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
mcimadamore@1905:                 case UPPER:
mcimadamore@1905:                     return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
mcimadamore@1905:                 default:
mcimadamore@1905:                     Assert.error("Can't get here!");
mcimadamore@1905:                     return null;
mcimadamore@1905:             }
mcimadamore@1905:         }
mcimadamore@1905: 
mcimadamore@1905:         boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
mcimadamore@1905:             IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
mcimadamore@1905:             Boolean res = infer.incorporationCache.get(newOp);
mcimadamore@1905:             if (res == null) {
mcimadamore@1905:                 infer.incorporationCache.put(newOp, res = newOp.apply(warn));
mcimadamore@1905:             }
mcimadamore@1905:             return res;
mcimadamore@1905:         }
mcimadamore@1562:     }
mcimadamore@1562: 
mcimadamore@1562:     /**
mcimadamore@1562:      * This solver uses an heuristic to pick the best leaf - the heuristic
mcimadamore@1562:      * tries to select the node that has maximal probability to contain one
mcimadamore@1562:      * or more inference variables in a given list
mcimadamore@1562:      */
mcimadamore@1562:     abstract class BestLeafSolver extends LeafSolver {
mcimadamore@1562: 
vromero@2000:         /** list of ivars of which at least one must be solved */
mcimadamore@1562:         List<Type> varsToSolve;
mcimadamore@1562: 
mcimadamore@1562:         BestLeafSolver(List<Type> varsToSolve) {
mcimadamore@1562:             this.varsToSolve = varsToSolve;
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
vromero@2000:          * Computes a path that goes from a given node to the leafs in the graph.
vromero@2000:          * Typically this will start from a node containing a variable in
vromero@2000:          * {@code varsToSolve}. For any given path, the cost is computed as the total
vromero@2000:          * number of type-variables that should be eagerly instantiated across that path.
mcimadamore@1562:          */
vromero@2000:         Pair<List<Node>, Integer> computeTreeToLeafs(Node n) {
vromero@2000:             Pair<List<Node>, Integer> cachedPath = treeCache.get(n);
vromero@2000:             if (cachedPath == null) {
vromero@2000:                 //cache miss
vromero@2000:                 if (n.isLeaf()) {
vromero@2000:                     //if leaf, stop
vromero@2000:                     cachedPath = new Pair<List<Node>, Integer>(List.of(n), n.data.length());
vromero@2000:                 } else {
vromero@2000:                     //if non-leaf, proceed recursively
vromero@2000:                     Pair<List<Node>, Integer> path = new Pair<List<Node>, Integer>(List.of(n), n.data.length());
vromero@2000:                     for (Node n2 : n.getAllDependencies()) {
vromero@2000:                         if (n2 == n) continue;
vromero@2000:                         Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2);
vromero@2000:                         path = new Pair<List<Node>, Integer>(
vromero@2000:                                 path.fst.prependList(subpath.fst),
vromero@2000:                                 path.snd + subpath.snd);
vromero@2000:                     }
vromero@2000:                     cachedPath = path;
vromero@2000:                 }
vromero@2000:                 //save results in cache
vromero@2000:                 treeCache.put(n, cachedPath);
vromero@2000:             }
vromero@2000:             return cachedPath;
mcimadamore@1903:         }
mcimadamore@1903: 
vromero@2000:         /** cache used to avoid redundant computation of tree costs */
vromero@2000:         final Map<Node, Pair<List<Node>, Integer>> treeCache =
vromero@2000:                 new HashMap<Node, Pair<List<Node>, Integer>>();
vromero@2000: 
vromero@2000:         /** constant value used to mark non-existent paths */
vromero@2000:         final Pair<List<Node>, Integer> noPath =
vromero@2000:                 new Pair<List<Node>, Integer>(null, Integer.MAX_VALUE);
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Pick the leaf that minimize cost
mcimadamore@1562:          */
mcimadamore@1562:         @Override
mcimadamore@1562:         public Node pickNode(final InferenceGraph g) {
vromero@2000:             treeCache.clear(); //graph changes at every step - cache must be cleared
vromero@2000:             Pair<List<Node>, Integer> bestPath = noPath;
mcimadamore@1562:             for (Node n : g.nodes) {
vromero@2000:                 if (!Collections.disjoint(n.data, varsToSolve)) {
vromero@2000:                     Pair<List<Node>, Integer> path = computeTreeToLeafs(n);
vromero@2000:                     //discard all paths containing at least a node in the
vromero@2000:                     //closure computed above
vromero@2000:                     if (path.snd < bestPath.snd) {
vromero@2000:                         bestPath = path;
vromero@2000:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
vromero@2000:             if (bestPath == noPath) {
vromero@2000:                 //no path leads there
vromero@2000:                 throw new NodeNotFoundException(g);
vromero@2000:             }
vromero@2000:             return bestPath.fst.head;
mcimadamore@1562:         }
mcimadamore@1562:     }
mcimadamore@1562: 
mcimadamore@1562:     /**
mcimadamore@1562:      * The inference process can be thought of as a sequence of steps. Each step
mcimadamore@1562:      * instantiates an inference variable using a subset of the inference variable
mcimadamore@1562:      * bounds, if certain condition are met. Decisions such as the sequence in which
mcimadamore@1562:      * steps are applied, or which steps are to be applied are left to the inference engine.
mcimadamore@1562:      */
mcimadamore@1562:     enum InferenceStep {
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Instantiate an inference variables using one of its (ground) equality
mcimadamore@1562:          * constraints
mcimadamore@1562:          */
mcimadamore@1562:         EQ(InferenceBound.EQ) {
mcimadamore@1562:             @Override
mcimadamore@1562:             Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562:                 return filterBounds(uv, inferenceContext).head;
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Instantiate an inference variables using its (ground) lower bounds. Such
mcimadamore@1562:          * bounds are merged together using lub().
mcimadamore@1562:          */
mcimadamore@1562:         LOWER(InferenceBound.LOWER) {
mcimadamore@1562:             @Override
mcimadamore@1562:             Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 List<Type> lobounds = filterBounds(uv, inferenceContext);
vromero@1826:                 //note: lobounds should have at least one element
vromero@1826:                 Type owntype = lobounds.tail.tail == null  ? lobounds.head : infer.types.lub(lobounds);
vromero@1826:                 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
mcimadamore@1562:                     throw infer.inferenceException
mcimadamore@1562:                         .setMessage("no.unique.minimal.instance.exists",
mcimadamore@1562:                                     uv.qtype, lobounds);
mcimadamore@1562:                 } else {
mcimadamore@1562:                     return owntype;
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1896:          * Infer uninstantiated/unbound inference variables occurring in 'throws'
mcimadamore@1896:          * clause as RuntimeException
mcimadamore@1896:          */
mcimadamore@1896:         THROWS(InferenceBound.UPPER) {
mcimadamore@1896:             @Override
mcimadamore@1896:             public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1896:                 if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) {
mcimadamore@1896:                     //not a throws undet var
mcimadamore@1896:                     return false;
mcimadamore@1896:                 }
mcimadamore@1896:                 if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER)
mcimadamore@1896:                             .diff(t.getDeclaredBounds()).nonEmpty()) {
mcimadamore@1896:                     //not an unbounded undet var
mcimadamore@1896:                     return false;
mcimadamore@1896:                 }
mcimadamore@1896:                 Infer infer = inferenceContext.infer();
mcimadamore@1896:                 for (Type db : t.getDeclaredBounds()) {
mcimadamore@1896:                     if (t.isInterface()) continue;
mcimadamore@1896:                     if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) {
mcimadamore@1896:                         //declared bound is a supertype of RuntimeException
mcimadamore@1896:                         return true;
mcimadamore@1896:                     }
mcimadamore@1896:                 }
mcimadamore@1896:                 //declared bound is more specific then RuntimeException - give up
mcimadamore@1896:                 return false;
mcimadamore@1896:             }
mcimadamore@1896: 
mcimadamore@1896:             @Override
mcimadamore@1896:             Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1896:                 return inferenceContext.infer().syms.runtimeExceptionType;
mcimadamore@1896:             }
mcimadamore@1896:         },
mcimadamore@1896:         /**
mcimadamore@1562:          * Instantiate an inference variables using its (ground) upper bounds. Such
mcimadamore@1562:          * bounds are merged together using glb().
mcimadamore@1562:          */
mcimadamore@1562:         UPPER(InferenceBound.UPPER) {
mcimadamore@1562:             @Override
mcimadamore@1562:             Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562:                 Infer infer = inferenceContext.infer();
mcimadamore@1562:                 List<Type> hibounds = filterBounds(uv, inferenceContext);
dlsmith@2384:                 //note: hibounds should have at least one element
vromero@1826:                 Type owntype = hibounds.tail.tail == null  ? hibounds.head : infer.types.glb(hibounds);
vromero@1826:                 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
mcimadamore@1562:                     throw infer.inferenceException
mcimadamore@1562:                         .setMessage("no.unique.maximal.instance.exists",
mcimadamore@1562:                                     uv.qtype, hibounds);
mcimadamore@1562:                 } else {
mcimadamore@1562:                     return owntype;
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562:         },
mcimadamore@1562:         /**
mcimadamore@1562:          * Like the former; the only difference is that this step can only be applied
mcimadamore@1562:          * if all upper bounds are ground.
mcimadamore@1562:          */
mcimadamore@1562:         UPPER_LEGACY(InferenceBound.UPPER) {
mcimadamore@1562:             @Override
mcimadamore@1562:             public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1898:                 return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured();
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             @Override
mcimadamore@1562:             Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562:                 return UPPER.solve(uv, inferenceContext);
mcimadamore@1562:             }
mcimadamore@1898:         },
mcimadamore@1898:         /**
mcimadamore@1898:          * Like the former; the only difference is that this step can only be applied
mcimadamore@1898:          * if all upper/lower bounds are ground.
mcimadamore@1898:          */
mcimadamore@1898:         CAPTURED(InferenceBound.UPPER) {
mcimadamore@1898:             @Override
mcimadamore@1898:             public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1919:                 return t.isCaptured() &&
mcimadamore@1919:                         !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER));
mcimadamore@1898:             }
mcimadamore@1898: 
mcimadamore@1898:             @Override
mcimadamore@1898:             Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1898:                 Infer infer = inferenceContext.infer();
mcimadamore@1898:                 Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ?
mcimadamore@1898:                         UPPER.solve(uv, inferenceContext) :
mcimadamore@1898:                         infer.syms.objectType;
mcimadamore@1898:                 Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ?
mcimadamore@1898:                         LOWER.solve(uv, inferenceContext) :
mcimadamore@1898:                         infer.syms.botType;
mcimadamore@1898:                 CapturedType prevCaptured = (CapturedType)uv.qtype;
mcimadamore@1898:                 return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, upper, lower, prevCaptured.wildcard);
mcimadamore@1898:             }
mcimadamore@1562:         };
mcimadamore@1562: 
mcimadamore@1562:         final InferenceBound ib;
mcimadamore@1562: 
mcimadamore@1562:         InferenceStep(InferenceBound ib) {
mcimadamore@1562:             this.ib = ib;
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Find an instantiated type for a given inference variable within
mcimadamore@1562:          * a given inference context
mcimadamore@1562:          */
mcimadamore@1562:         abstract Type solve(UndetVar uv, InferenceContext inferenceContext);
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Can the inference variable be instantiated using this step?
mcimadamore@1562:          */
mcimadamore@1562:         public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1898:             return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured();
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)
mcimadamore@1562:          */
mcimadamore@1562:         List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562:             return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));
mcimadamore@1562:         }
mcimadamore@1562:     }
mcimadamore@1562: 
mcimadamore@1562:     /**
mcimadamore@1562:      * This enumeration defines the sequence of steps to be applied when the
mcimadamore@1562:      * solver works in legacy mode. The steps in this enumeration reflect
mcimadamore@1562:      * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
mcimadamore@1562:      */
mcimadamore@1562:     enum LegacyInferenceSteps {
mcimadamore@1562: 
mcimadamore@1562:         EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
mcimadamore@1562:         EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));
mcimadamore@1562: 
mcimadamore@1562:         final EnumSet<InferenceStep> steps;
mcimadamore@1562: 
mcimadamore@1562:         LegacyInferenceSteps(EnumSet<InferenceStep> steps) {
mcimadamore@1562:             this.steps = steps;
mcimadamore@1562:         }
mcimadamore@1562:     }
mcimadamore@1562: 
mcimadamore@1562:     /**
mcimadamore@1562:      * This enumeration defines the sequence of steps to be applied when the
mcimadamore@1562:      * graph solver is used. This order is defined so as to maximize compatibility
mcimadamore@1562:      * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
mcimadamore@1562:      */
mcimadamore@1562:     enum GraphInferenceSteps {
mcimadamore@1562: 
mcimadamore@1562:         EQ(EnumSet.of(InferenceStep.EQ)),
mcimadamore@1562:         EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
mcimadamore@1898:         EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED));
mcimadamore@1562: 
mcimadamore@1562:         final EnumSet<InferenceStep> steps;
mcimadamore@1562: 
mcimadamore@1562:         GraphInferenceSteps(EnumSet<InferenceStep> steps) {
mcimadamore@1562:             this.steps = steps;
mcimadamore@1562:         }
mcimadamore@1562:     }
mcimadamore@1562: 
mcimadamore@1562:     /**
vromero@2000:      * There are two kinds of dependencies between inference variables. The basic
vromero@2000:      * kind of dependency (or bound dependency) arises when a variable mention
vromero@2000:      * another variable in one of its bounds. There's also a more subtle kind
vromero@2000:      * of dependency that arises when a variable 'might' lead to better constraints
vromero@2000:      * on another variable (this is typically the case with variables holding up
vromero@2000:      * stuck expressions).
vromero@2000:      */
vromero@2000:     enum DependencyKind implements GraphUtils.DependencyKind {
vromero@2000: 
vromero@2000:         /** bound dependency */
vromero@2000:         BOUND("dotted"),
vromero@2000:         /** stuck dependency */
vromero@2000:         STUCK("dashed");
vromero@2000: 
vromero@2000:         final String dotSyle;
vromero@2000: 
vromero@2000:         private DependencyKind(String dotSyle) {
vromero@2000:             this.dotSyle = dotSyle;
vromero@2000:         }
vromero@2000: 
vromero@2000:         @Override
vromero@2000:         public String getDotStyle() {
vromero@2000:             return dotSyle;
vromero@2000:         }
vromero@2000:     }
vromero@2000: 
vromero@2000:     /**
mcimadamore@1562:      * This is the graph inference solver - the solver organizes all inference variables in
mcimadamore@1562:      * a given inference context by bound dependencies - in the general case, such dependencies
mcimadamore@1562:      * would lead to a cyclic directed graph (hence the name); the dependency info is used to build
mcimadamore@1562:      * an acyclic graph, where all cyclic variables are bundled together. An inference
mcimadamore@1562:      * step corresponds to solving a node in the acyclic graph - this is done by
mcimadamore@1562:      * relying on a given strategy (see GraphStrategy).
mcimadamore@1562:      */
mcimadamore@1562:     class GraphSolver {
mcimadamore@1562: 
mcimadamore@1562:         InferenceContext inferenceContext;
vromero@2000:         Map<Type, Set<Type>> stuckDeps;
mcimadamore@1562:         Warner warn;
mcimadamore@1562: 
vromero@2000:         GraphSolver(InferenceContext inferenceContext, Map<Type, Set<Type>> stuckDeps, Warner warn) {
mcimadamore@1562:             this.inferenceContext = inferenceContext;
vromero@2000:             this.stuckDeps = stuckDeps;
mcimadamore@1562:             this.warn = warn;
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Solve variables in a given inference context. The amount of variables
mcimadamore@1562:          * to be solved, and the way in which the underlying acyclic graph is explored
mcimadamore@1562:          * depends on the selected solver strategy.
mcimadamore@1562:          */
mcimadamore@1562:         void solve(GraphStrategy sstrategy) {
mcimadamore@1562:             checkWithinBounds(inferenceContext, warn); //initial propagation of bounds
vromero@2000:             InferenceGraph inferenceGraph = new InferenceGraph(stuckDeps);
mcimadamore@1562:             while (!sstrategy.done()) {
mcimadamore@1562:                 InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);
mcimadamore@1562:                 List<Type> varsToSolve = List.from(nodeToSolve.data);
mcimadamore@1891:                 List<Type> saved_undet = inferenceContext.save();
mcimadamore@1562:                 try {
mcimadamore@1562:                     //repeat until all variables are solved
mcimadamore@1562:                     outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {
mcimadamore@1562:                         //for each inference phase
mcimadamore@1562:                         for (GraphInferenceSteps step : GraphInferenceSteps.values()) {
mcimadamore@1562:                             if (inferenceContext.solveBasic(varsToSolve, step.steps)) {
mcimadamore@1562:                                 checkWithinBounds(inferenceContext, warn);
mcimadamore@1562:                                 continue outer;
mcimadamore@1562:                             }
mcimadamore@1562:                         }
mcimadamore@1562:                         //no progress
vromero@1826:                         throw inferenceException.setMessage();
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:                 catch (InferenceException ex) {
vromero@1826:                     //did we fail because of interdependent ivars?
mcimadamore@1891:                     inferenceContext.rollback(saved_undet);
mcimadamore@1562:                     instantiateAsUninferredVars(varsToSolve, inferenceContext);
mcimadamore@1562:                     checkWithinBounds(inferenceContext, warn);
mcimadamore@1562:                 }
mcimadamore@1562:                 inferenceGraph.deleteNode(nodeToSolve);
mcimadamore@1562:             }
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * The dependencies between the inference variables that need to be solved
mcimadamore@1562:          * form a (possibly cyclic) graph. This class reduces the original dependency graph
mcimadamore@1562:          * to an acyclic version, where cyclic nodes are folded into a single 'super node'.
mcimadamore@1562:          */
mcimadamore@1562:         class InferenceGraph {
mcimadamore@1562: 
mcimadamore@1562:             /**
mcimadamore@1562:              * This class represents a node in the graph. Each node corresponds
mcimadamore@1562:              * to an inference variable and has edges (dependencies) on other
mcimadamore@1562:              * nodes. The node defines an entry point that can be used to receive
mcimadamore@1562:              * updates on the structure of the graph this node belongs to (used to
mcimadamore@1562:              * keep dependencies in sync).
mcimadamore@1562:              */
mcimadamore@1562:             class Node extends GraphUtils.TarjanNode<ListBuffer<Type>> {
mcimadamore@1562: 
vromero@2000:                 /** map listing all dependencies (grouped by kind) */
vromero@2000:                 EnumMap<DependencyKind, Set<Node>> deps;
mcimadamore@1562: 
mcimadamore@1562:                 Node(Type ivar) {
mcimadamore@1562:                     super(ListBuffer.of(ivar));
vromero@2000:                     this.deps = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class);
mcimadamore@1562:                 }
mcimadamore@1562: 
mcimadamore@1562:                 @Override
vromero@2000:                 public GraphUtils.DependencyKind[] getSupportedDependencyKinds() {
vromero@2000:                     return DependencyKind.values();
mcimadamore@1562:                 }
mcimadamore@1562: 
mcimadamore@1562:                 @Override
vromero@2000:                 public String getDependencyName(GraphUtils.Node<ListBuffer<Type>> to, GraphUtils.DependencyKind dk) {
vromero@2000:                     if (dk == DependencyKind.STUCK) return "";
vromero@2000:                     else {
vromero@2000:                         StringBuilder buf = new StringBuilder();
vromero@2000:                         String sep = "";
vromero@2000:                         for (Type from : data) {
vromero@2368:                             UndetVar uv = (UndetVar)inferenceContext.asUndetVar(from);
vromero@2000:                             for (Type bound : uv.getBounds(InferenceBound.values())) {
vromero@2000:                                 if (bound.containsAny(List.from(to.data))) {
vromero@2000:                                     buf.append(sep);
vromero@2000:                                     buf.append(bound);
vromero@2000:                                     sep = ",";
vromero@2000:                                 }
mcimadamore@1562:                             }
mcimadamore@1562:                         }
vromero@2000:                         return buf.toString();
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562: 
vromero@2000:                 @Override
vromero@2000:                 public Iterable<? extends Node> getAllDependencies() {
vromero@2000:                     return getDependencies(DependencyKind.values());
mcimadamore@1562:                 }
mcimadamore@1562: 
vromero@2000:                 @Override
vromero@2000:                 public Iterable<? extends TarjanNode<ListBuffer<Type>>> getDependenciesByKind(GraphUtils.DependencyKind dk) {
vromero@2000:                     return getDependencies((DependencyKind)dk);
vromero@2000:                 }
vromero@2000: 
vromero@2000:                 /**
vromero@2000:                  * Retrieves all dependencies with given kind(s).
vromero@2000:                  */
vromero@2000:                 protected Set<Node> getDependencies(DependencyKind... depKinds) {
vromero@2000:                     Set<Node> buf = new LinkedHashSet<Node>();
vromero@2000:                     for (DependencyKind dk : depKinds) {
vromero@2000:                         Set<Node> depsByKind = deps.get(dk);
vromero@2000:                         if (depsByKind != null) {
vromero@2000:                             buf.addAll(depsByKind);
vromero@2000:                         }
vromero@2000:                     }
vromero@2000:                     return buf;
vromero@2000:                 }
vromero@2000: 
vromero@2000:                 /**
vromero@2000:                  * Adds dependency with given kind.
vromero@2000:                  */
vromero@2000:                 protected void addDependency(DependencyKind dk, Node depToAdd) {
vromero@2000:                     Set<Node> depsByKind = deps.get(dk);
vromero@2000:                     if (depsByKind == null) {
vromero@2000:                         depsByKind = new LinkedHashSet<Node>();
vromero@2000:                         deps.put(dk, depsByKind);
vromero@2000:                     }
vromero@2000:                     depsByKind.add(depToAdd);
vromero@2000:                 }
vromero@2000: 
vromero@2000:                 /**
vromero@2000:                  * Add multiple dependencies of same given kind.
vromero@2000:                  */
vromero@2000:                 protected void addDependencies(DependencyKind dk, Set<Node> depsToAdd) {
vromero@2000:                     for (Node n : depsToAdd) {
vromero@2000:                         addDependency(dk, n);
vromero@2000:                     }
vromero@2000:                 }
vromero@2000: 
vromero@2000:                 /**
vromero@2000:                  * Remove a dependency, regardless of its kind.
vromero@2000:                  */
vromero@2000:                 protected Set<DependencyKind> removeDependency(Node n) {
vromero@2000:                     Set<DependencyKind> removedKinds = new HashSet<>();
vromero@2000:                     for (DependencyKind dk : DependencyKind.values()) {
vromero@2000:                         Set<Node> depsByKind = deps.get(dk);
vromero@2000:                         if (depsByKind == null) continue;
vromero@2000:                         if (depsByKind.remove(n)) {
vromero@2000:                             removedKinds.add(dk);
vromero@2000:                         }
vromero@2000:                     }
vromero@2000:                     return removedKinds;
vromero@2000:                 }
vromero@2000: 
vromero@2000:                 /**
vromero@2000:                  * Compute closure of a give node, by recursively walking
vromero@2000:                  * through all its dependencies (of given kinds)
vromero@2000:                  */
vromero@2000:                 protected Set<Node> closure(DependencyKind... depKinds) {
vromero@2000:                     boolean progress = true;
vromero@2000:                     Set<Node> closure = new HashSet<Node>();
vromero@2000:                     closure.add(this);
vromero@2000:                     while (progress) {
vromero@2000:                         progress = false;
vromero@2000:                         for (Node n1 : new HashSet<Node>(closure)) {
vromero@2000:                             progress = closure.addAll(n1.getDependencies(depKinds));
vromero@2000:                         }
vromero@2000:                     }
vromero@2000:                     return closure;
vromero@2000:                 }
vromero@2000: 
vromero@2000:                 /**
vromero@2000:                  * Is this node a leaf? This means either the node has no dependencies,
vromero@2000:                  * or it just has self-dependencies.
vromero@2000:                  */
vromero@2000:                 protected boolean isLeaf() {
vromero@2000:                     //no deps, or only one self dep
vromero@2000:                     Set<Node> allDeps = getDependencies(DependencyKind.BOUND, DependencyKind.STUCK);
vromero@2000:                     if (allDeps.isEmpty()) return true;
vromero@2000:                     for (Node n : allDeps) {
vromero@2000:                         if (n != this) {
vromero@2000:                             return false;
vromero@2000:                         }
vromero@2000:                     }
vromero@2000:                     return true;
vromero@2000:                 }
vromero@2000: 
vromero@2000:                 /**
vromero@2000:                  * Merge this node with another node, acquiring its dependencies.
vromero@2000:                  * This routine is used to merge all cyclic node together and
vromero@2000:                  * form an acyclic graph.
vromero@2000:                  */
vromero@2000:                 protected void mergeWith(List<? extends Node> nodes) {
mcimadamore@1562:                     for (Node n : nodes) {
mcimadamore@1562:                         Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");
mcimadamore@1562:                         data.appendList(n.data);
vromero@2000:                         for (DependencyKind dk : DependencyKind.values()) {
vromero@2000:                             addDependencies(dk, n.getDependencies(dk));
vromero@2000:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                     //update deps
vromero@2000:                     EnumMap<DependencyKind, Set<Node>> deps2 = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class);
vromero@2000:                     for (DependencyKind dk : DependencyKind.values()) {
vromero@2000:                         for (Node d : getDependencies(dk)) {
vromero@2000:                             Set<Node> depsByKind = deps2.get(dk);
vromero@2000:                             if (depsByKind == null) {
vromero@2000:                                 depsByKind = new LinkedHashSet<Node>();
vromero@2000:                                 deps2.put(dk, depsByKind);
vromero@2000:                             }
vromero@2000:                             if (data.contains(d.data.first())) {
vromero@2000:                                 depsByKind.add(this);
vromero@2000:                             } else {
vromero@2000:                                 depsByKind.add(d);
vromero@2000:                             }
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                     deps = deps2;
mcimadamore@1562:                 }
mcimadamore@1562: 
vromero@2000:                 /**
vromero@2000:                  * Notify all nodes that something has changed in the graph
vromero@2000:                  * topology.
vromero@2000:                  */
vromero@2000:                 private void graphChanged(Node from, Node to) {
vromero@2000:                     for (DependencyKind dk : removeDependency(from)) {
mcimadamore@1562:                         if (to != null) {
vromero@2000:                             addDependency(dk, to);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             /** the nodes in the inference graph */
mcimadamore@1562:             ArrayList<Node> nodes;
mcimadamore@1562: 
vromero@2000:             InferenceGraph(Map<Type, Set<Type>> optDeps) {
vromero@2000:                 initNodes(optDeps);
vromero@2000:             }
vromero@2000: 
vromero@2000:             /**
vromero@2000:              * Basic lookup helper for retrieving a graph node given an inference
vromero@2000:              * variable type.
vromero@2000:              */
vromero@2000:             public Node findNode(Type t) {
vromero@2000:                 for (Node n : nodes) {
vromero@2000:                     if (n.data.contains(t)) {
vromero@2000:                         return n;
vromero@2000:                     }
vromero@2000:                 }
vromero@2000:                 return null;
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             /**
mcimadamore@1562:              * Delete a node from the graph. This update the underlying structure
mcimadamore@1562:              * of the graph (including dependencies) via listeners updates.
mcimadamore@1562:              */
mcimadamore@1562:             public void deleteNode(Node n) {
mcimadamore@1562:                 Assert.check(nodes.contains(n));
mcimadamore@1562:                 nodes.remove(n);
mcimadamore@1562:                 notifyUpdate(n, null);
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             /**
mcimadamore@1562:              * Notify all nodes of a change in the graph. If the target node is
mcimadamore@1562:              * {@code null} the source node is assumed to be removed.
mcimadamore@1562:              */
mcimadamore@1562:             void notifyUpdate(Node from, Node to) {
mcimadamore@1562:                 for (Node n : nodes) {
mcimadamore@1562:                     n.graphChanged(from, to);
mcimadamore@1562:                 }
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             /**
mcimadamore@1562:              * Create the graph nodes. First a simple node is created for every inference
mcimadamore@1562:              * variables to be solved. Then Tarjan is used to found all connected components
mcimadamore@1562:              * in the graph. For each component containing more than one node, a super node is
vromero@2000:              * created, effectively replacing the original cyclic nodes.
mcimadamore@1562:              */
vromero@2000:             void initNodes(Map<Type, Set<Type>> stuckDeps) {
vromero@2000:                 //add nodes
mcimadamore@1608:                 nodes = new ArrayList<Node>();
mcimadamore@1562:                 for (Type t : inferenceContext.restvars()) {
mcimadamore@1562:                     nodes.add(new Node(t));
mcimadamore@1562:                 }
vromero@2000:                 //add dependencies
mcimadamore@1562:                 for (Node n_i : nodes) {
mcimadamore@1562:                     Type i = n_i.data.first();
vromero@2000:                     Set<Type> optDepsByNode = stuckDeps.get(i);
mcimadamore@1562:                     for (Node n_j : nodes) {
mcimadamore@1562:                         Type j = n_j.data.first();
vromero@2368:                         UndetVar uv_i = (UndetVar)inferenceContext.asUndetVar(i);
mcimadamore@1562:                         if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {
vromero@2000:                             //update i's bound dependencies
vromero@2000:                             n_i.addDependency(DependencyKind.BOUND, n_j);
vromero@2000:                         }
vromero@2000:                         if (optDepsByNode != null && optDepsByNode.contains(j)) {
vromero@2000:                             //update i's stuck dependencies
vromero@2000:                             n_i.addDependency(DependencyKind.STUCK, n_j);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1562:                 }
vromero@2000:                 //merge cyclic nodes
mcimadamore@1608:                 ArrayList<Node> acyclicNodes = new ArrayList<Node>();
mcimadamore@1562:                 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {
mcimadamore@1562:                     if (conSubGraph.length() > 1) {
mcimadamore@1562:                         Node root = conSubGraph.head;
mcimadamore@1562:                         root.mergeWith(conSubGraph.tail);
mcimadamore@1562:                         for (Node n : conSubGraph) {
mcimadamore@1562:                             notifyUpdate(n, root);
mcimadamore@1562:                         }
mcimadamore@1562:                     }
mcimadamore@1608:                     acyclicNodes.add(conSubGraph.head);
mcimadamore@1562:                 }
mcimadamore@1608:                 nodes = acyclicNodes;
mcimadamore@1562:             }
mcimadamore@1562: 
mcimadamore@1562:             /**
mcimadamore@1562:              * Debugging: dot representation of this graph
mcimadamore@1562:              */
mcimadamore@1562:             String toDot() {
mcimadamore@1562:                 StringBuilder buf = new StringBuilder();
mcimadamore@1562:                 for (Type t : inferenceContext.undetvars) {
mcimadamore@1562:                     UndetVar uv = (UndetVar)t;
mcimadamore@1562:                     buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",
mcimadamore@1562:                             uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),
mcimadamore@1562:                             uv.getBounds(InferenceBound.EQ)));
mcimadamore@1562:                 }
mcimadamore@1562:                 return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());
mcimadamore@1562:             }
mcimadamore@1562:         }
mcimadamore@1562:     }
mcimadamore@1562:     // </editor-fold>
mcimadamore@1562: 
mcimadamore@1562:     // <editor-fold defaultstate="collapsed" desc="Inference context">
mcimadamore@1562:     /**
mcimadamore@1550:      * Functional interface for defining inference callbacks. Certain actions
mcimadamore@1550:      * (i.e. subtyping checks) might need to be redone after all inference variables
mcimadamore@1550:      * have been fixed.
mcimadamore@1337:      */
mcimadamore@1550:     interface FreeTypeListener {
mcimadamore@1550:         void typesInferred(InferenceContext inferenceContext);
mcimadamore@1550:     }
mcimadamore@1337: 
mcimadamore@1337:     /**
mcimadamore@1337:      * An inference context keeps track of the set of variables that are free
mcimadamore@1337:      * in the current context. It provides utility methods for opening/closing
mcimadamore@1337:      * types to their corresponding free/closed forms. It also provide hooks for
mcimadamore@1337:      * attaching deferred post-inference action (see PendingCheck). Finally,
mcimadamore@1337:      * it can be used as an entry point for performing upper/lower bound inference
mcimadamore@1337:      * (see InferenceKind).
mcimadamore@1337:      */
mcimadamore@1562:      class InferenceContext {
mcimadamore@1337: 
mcimadamore@1337:         /** list of inference vars as undet vars */
mcimadamore@1337:         List<Type> undetvars;
mcimadamore@1337: 
mcimadamore@1337:         /** list of inference vars in this context */
mcimadamore@1337:         List<Type> inferencevars;
mcimadamore@1337: 
mcimadamore@1337:         java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners =
mcimadamore@1337:                 new java.util.HashMap<FreeTypeListener, List<Type>>();
mcimadamore@1337: 
mcimadamore@1337:         List<FreeTypeListener> freetypeListeners = List.nil();
mcimadamore@1337: 
mcimadamore@1550:         public InferenceContext(List<Type> inferencevars) {
mcimadamore@1550:             this.undetvars = Type.map(inferencevars, fromTypeVarFun);
mcimadamore@1337:             this.inferencevars = inferencevars;
mcimadamore@1337:         }
mcimadamore@1550:         //where
mcimadamore@1550:             Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") {
mcimadamore@1550:                 // mapping that turns inference variables into undet vars
mcimadamore@1550:                 public Type apply(Type t) {
mcimadamore@1898:                     if (t.hasTag(TYPEVAR)) {
mcimadamore@1898:                         TypeVar tv = (TypeVar)t;
vromero@2157:                         if (tv.isCaptured()) {
vromero@2157:                             return new CapturedUndetVar((CapturedType)tv, types);
vromero@2157:                         } else {
vromero@2157:                             return new UndetVar(tv, types);
vromero@2157:                         }
mcimadamore@1898:                     } else {
mcimadamore@1898:                         return t.map(this);
mcimadamore@1898:                     }
mcimadamore@1550:                 }
mcimadamore@1550:             };
mcimadamore@1337: 
mcimadamore@1337:         /**
mcimadamore@1898:          * add a new inference var to this inference context
mcimadamore@1898:          */
mcimadamore@1898:         void addVar(TypeVar t) {
mcimadamore@1898:             this.undetvars = this.undetvars.prepend(fromTypeVarFun.apply(t));
mcimadamore@1898:             this.inferencevars = this.inferencevars.prepend(t);
mcimadamore@1898:         }
mcimadamore@1898: 
mcimadamore@1898:         /**
mcimadamore@1337:          * returns the list of free variables (as type-variables) in this
mcimadamore@1337:          * inference context
mcimadamore@1337:          */
mcimadamore@1337:         List<Type> inferenceVars() {
mcimadamore@1337:             return inferencevars;
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         /**
mcimadamore@1337:          * returns the list of uninstantiated variables (as type-variables) in this
mcimadamore@1550:          * inference context
mcimadamore@1337:          */
mcimadamore@1337:         List<Type> restvars() {
mcimadamore@1550:             return filterVars(new Filter<UndetVar>() {
mcimadamore@1550:                 public boolean accepts(UndetVar uv) {
mcimadamore@1550:                     return uv.inst == null;
mcimadamore@1337:                 }
mcimadamore@1550:             });
mcimadamore@1550:         }
mcimadamore@1550: 
mcimadamore@1550:         /**
mcimadamore@1550:          * returns the list of instantiated variables (as type-variables) in this
mcimadamore@1550:          * inference context
mcimadamore@1550:          */
mcimadamore@1550:         List<Type> instvars() {
mcimadamore@1550:             return filterVars(new Filter<UndetVar>() {
mcimadamore@1550:                 public boolean accepts(UndetVar uv) {
mcimadamore@1550:                     return uv.inst != null;
mcimadamore@1550:                 }
mcimadamore@1550:             });
mcimadamore@1550:         }
mcimadamore@1550: 
mcimadamore@1550:         /**
mcimadamore@1550:          * Get list of bounded inference variables (where bound is other than
mcimadamore@1550:          * declared bounds).
mcimadamore@1550:          */
mcimadamore@1550:         final List<Type> boundedVars() {
mcimadamore@1550:             return filterVars(new Filter<UndetVar>() {
mcimadamore@1550:                 public boolean accepts(UndetVar uv) {
mcimadamore@1550:                     return uv.getBounds(InferenceBound.UPPER)
vromero@2000:                              .diff(uv.getDeclaredBounds())
vromero@2000:                              .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty();
mcimadamore@1550:                 }
mcimadamore@1550:             });
mcimadamore@1550:         }
mcimadamore@1550: 
vromero@2368:         /* Returns the corresponding inference variables.
vromero@2368:          */
mcimadamore@1550:         private List<Type> filterVars(Filter<UndetVar> fu) {
alundblad@2047:             ListBuffer<Type> res = new ListBuffer<>();
mcimadamore@1550:             for (Type t : undetvars) {
mcimadamore@1550:                 UndetVar uv = (UndetVar)t;
mcimadamore@1550:                 if (fu.accepts(uv)) {
mcimadamore@1550:                     res.append(uv.qtype);
mcimadamore@1550:                 }
mcimadamore@1337:             }
mcimadamore@1550:             return res.toList();
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         /**
mcimadamore@1337:          * is this type free?
mcimadamore@1337:          */
mcimadamore@1337:         final boolean free(Type t) {
mcimadamore@1337:             return t.containsAny(inferencevars);
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         final boolean free(List<Type> ts) {
mcimadamore@1337:             for (Type t : ts) {
mcimadamore@1337:                 if (free(t)) return true;
mcimadamore@1337:             }
mcimadamore@1337:             return false;
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         /**
mcimadamore@1337:          * Returns a list of free variables in a given type
mcimadamore@1337:          */
mcimadamore@1337:         final List<Type> freeVarsIn(Type t) {
alundblad@2047:             ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337:             for (Type iv : inferenceVars()) {
mcimadamore@1337:                 if (t.contains(iv)) {
mcimadamore@1337:                     buf.add(iv);
mcimadamore@1337:                 }
mcimadamore@1337:             }
mcimadamore@1337:             return buf.toList();
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         final List<Type> freeVarsIn(List<Type> ts) {
alundblad@2047:             ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337:             for (Type t : ts) {
mcimadamore@1337:                 buf.appendList(freeVarsIn(t));
mcimadamore@1337:             }
alundblad@2047:             ListBuffer<Type> buf2 = new ListBuffer<>();
mcimadamore@1337:             for (Type t : buf) {
mcimadamore@1337:                 if (!buf2.contains(t)) {
mcimadamore@1337:                     buf2.add(t);
mcimadamore@1337:                 }
mcimadamore@1337:             }
mcimadamore@1337:             return buf2.toList();
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         /**
mcimadamore@1337:          * Replace all free variables in a given type with corresponding
mcimadamore@1337:          * undet vars (used ahead of subtyping/compatibility checks to allow propagation
mcimadamore@1337:          * of inference constraints).
mcimadamore@1337:          */
vromero@2368:         final Type asUndetVar(Type t) {
mcimadamore@1337:             return types.subst(t, inferencevars, undetvars);
mcimadamore@1337:         }
mcimadamore@1337: 
vromero@2368:         final List<Type> asUndetVars(List<Type> ts) {
alundblad@2047:             ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337:             for (Type t : ts) {
vromero@2368:                 buf.append(asUndetVar(t));
mcimadamore@1337:             }
mcimadamore@1337:             return buf.toList();
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         List<Type> instTypes() {
alundblad@2047:             ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337:             for (Type t : undetvars) {
mcimadamore@1337:                 UndetVar uv = (UndetVar)t;
mcimadamore@1337:                 buf.append(uv.inst != null ? uv.inst : uv.qtype);
mcimadamore@1337:             }
mcimadamore@1337:             return buf.toList();
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         /**
mcimadamore@1337:          * Replace all free variables in a given type with corresponding
mcimadamore@1337:          * instantiated types - if one or more free variable has not been
mcimadamore@1337:          * fully instantiated, it will still be available in the resulting type.
mcimadamore@1337:          */
mcimadamore@1550:         Type asInstType(Type t) {
mcimadamore@1337:             return types.subst(t, inferencevars, instTypes());
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1550:         List<Type> asInstTypes(List<Type> ts) {
alundblad@2047:             ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337:             for (Type t : ts) {
mcimadamore@1550:                 buf.append(asInstType(t));
mcimadamore@1337:             }
mcimadamore@1337:             return buf.toList();
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         /**
mcimadamore@1337:          * Add custom hook for performing post-inference action
mcimadamore@1337:          */
mcimadamore@1337:         void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {
mcimadamore@1337:             freeTypeListeners.put(ftl, freeVarsIn(types));
mcimadamore@1337:         }
mcimadamore@1337: 
mcimadamore@1337:         /**
mcimadamore@1337:          * Mark the inference context as complete and trigger evaluation
mcimadamore@1337:          * of all deferred checks.
mcimadamore@1337:          */
mcimadamore@1550:         void notifyChange() {
mcimadamore@1562:             notifyChange(inferencevars.diff(restvars()));
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         void notifyChange(List<Type> inferredVars) {
mcimadamore@1337:             InferenceException thrownEx = null;
mcimadamore@1337:             for (Map.Entry<FreeTypeListener, List<Type>> entry :
mcimadamore@1337:                     new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) {
mcimadamore@1562:                 if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {
mcimadamore@1337:                     try {
mcimadamore@1337:                         entry.getKey().typesInferred(this);
mcimadamore@1337:                         freeTypeListeners.remove(entry.getKey());
mcimadamore@1337:                     } catch (InferenceException ex) {
mcimadamore@1337:                         if (thrownEx == null) {
mcimadamore@1337:                             thrownEx = ex;
mcimadamore@1337:                         }
mcimadamore@1337:                     }
mcimadamore@1337:                 }
mcimadamore@1337:             }
mcimadamore@1337:             //inference exception multiplexing - present any inference exception
mcimadamore@1337:             //thrown when processing listeners as a single one
mcimadamore@1337:             if (thrownEx != null) {
mcimadamore@1337:                 throw thrownEx;
mcimadamore@1337:             }
mcimadamore@1337:         }
mcimadamore@1347: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Save the state of this inference context
mcimadamore@1562:          */
mcimadamore@1891:         List<Type> save() {
alundblad@2047:             ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1562:             for (Type t : undetvars) {
mcimadamore@1562:                 UndetVar uv = (UndetVar)t;
mcimadamore@1562:                 UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types);
mcimadamore@1562:                 for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562:                     for (Type b : uv.getBounds(ib)) {
mcimadamore@1562:                         uv2.addBound(ib, b, types);
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1562:                 uv2.inst = uv.inst;
mcimadamore@1562:                 buf.add(uv2);
mcimadamore@1562:             }
mcimadamore@1891:             return buf.toList();
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Restore the state of this inference context to the previous known checkpoint
mcimadamore@1562:          */
mcimadamore@1891:         void rollback(List<Type> saved_undet) {
mcimadamore@1891:              Assert.check(saved_undet != null && saved_undet.length() == undetvars.length());
mcimadamore@1891:             //restore bounds (note: we need to preserve the old instances)
mcimadamore@1891:             for (Type t : undetvars) {
mcimadamore@1891:                 UndetVar uv = (UndetVar)t;
mcimadamore@1891:                 UndetVar uv_saved = (UndetVar)saved_undet.head;
mcimadamore@1891:                 for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1891:                     uv.setBounds(ib, uv_saved.getBounds(ib));
mcimadamore@1891:                 }
mcimadamore@1891:                 uv.inst = uv_saved.inst;
mcimadamore@1891:                 saved_undet = saved_undet.tail;
mcimadamore@1891:             }
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Copy variable in this inference context to the given context
mcimadamore@1562:          */
mcimadamore@1562:         void dupTo(final InferenceContext that) {
vromero@2382:             that.inferencevars = that.inferencevars.appendList(
vromero@2382:                     inferencevars.diff(that.inferencevars));
vromero@2382:             that.undetvars = that.undetvars.appendList(
vromero@2382:                     undetvars.diff(that.undetvars));
mcimadamore@1562:             //set up listeners to notify original inference contexts as
mcimadamore@1562:             //propagated vars are inferred in new context
mcimadamore@1562:             for (Type t : inferencevars) {
mcimadamore@1562:                 that.freeTypeListeners.put(new FreeTypeListener() {
mcimadamore@1562:                     public void typesInferred(InferenceContext inferenceContext) {
mcimadamore@1562:                         InferenceContext.this.notifyChange();
mcimadamore@1562:                     }
mcimadamore@1562:                 }, List.of(t));
mcimadamore@1562:             }
mcimadamore@1562:         }
mcimadamore@1562: 
vromero@2000:         private void solve(GraphStrategy ss, Warner warn) {
vromero@2000:             solve(ss, new HashMap<Type, Set<Type>>(), warn);
vromero@2000:         }
vromero@2000: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Solve with given graph strategy.
mcimadamore@1562:          */
vromero@2000:         private void solve(GraphStrategy ss, Map<Type, Set<Type>> stuckDeps, Warner warn) {
vromero@2000:             GraphSolver s = new GraphSolver(this, stuckDeps, warn);
mcimadamore@1562:             s.solve(ss);
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Solve all variables in this context.
mcimadamore@1562:          */
mcimadamore@1562:         public void solve(Warner warn) {
mcimadamore@1562:             solve(new LeafSolver() {
mcimadamore@1562:                 public boolean done() {
mcimadamore@1562:                     return restvars().isEmpty();
mcimadamore@1562:                 }
mcimadamore@1562:             }, warn);
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Solve all variables in the given list.
mcimadamore@1562:          */
mcimadamore@1562:         public void solve(final List<Type> vars, Warner warn) {
mcimadamore@1562:             solve(new BestLeafSolver(vars) {
mcimadamore@1562:                 public boolean done() {
mcimadamore@1562:                     return !free(asInstTypes(vars));
mcimadamore@1562:                 }
mcimadamore@1562:             }, warn);
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Solve at least one variable in given list.
mcimadamore@1562:          */
vromero@2000:         public void solveAny(List<Type> varsToSolve, Map<Type, Set<Type>> optDeps, Warner warn) {
vromero@2000:             solve(new BestLeafSolver(varsToSolve.intersect(restvars())) {
mcimadamore@1562:                 public boolean done() {
mcimadamore@1562:                     return instvars().intersect(varsToSolve).nonEmpty();
mcimadamore@1562:                 }
vromero@2000:             }, optDeps, warn);
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Apply a set of inference steps
mcimadamore@1562:          */
mcimadamore@1562:         private boolean solveBasic(EnumSet<InferenceStep> steps) {
mcimadamore@1562:             return solveBasic(inferencevars, steps);
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         private boolean solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) {
mcimadamore@1562:             boolean changed = false;
mcimadamore@1562:             for (Type t : varsToSolve.intersect(restvars())) {
vromero@2368:                 UndetVar uv = (UndetVar)asUndetVar(t);
mcimadamore@1562:                 for (InferenceStep step : steps) {
mcimadamore@1562:                     if (step.accepts(uv, this)) {
mcimadamore@1562:                         uv.inst = step.solve(uv, this);
mcimadamore@1562:                         changed = true;
mcimadamore@1562:                         break;
mcimadamore@1347:                     }
mcimadamore@1347:                 }
mcimadamore@1347:             }
mcimadamore@1562:             return changed;
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         /**
mcimadamore@1562:          * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).
mcimadamore@1562:          * During overload resolution, instantiation is done by doing a partial
mcimadamore@1562:          * inference process using eq/lower bound instantiation. During check,
mcimadamore@1562:          * we also instantiate any remaining vars by repeatedly using eq/upper
mcimadamore@1562:          * instantiation, until all variables are solved.
mcimadamore@1562:          */
mcimadamore@1562:         public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) {
mcimadamore@1562:             while (true) {
mcimadamore@1562:                 boolean stuck = !solveBasic(steps);
mcimadamore@1562:                 if (restvars().isEmpty() || partial) {
mcimadamore@1562:                     //all variables have been instantiated - exit
mcimadamore@1562:                     break;
mcimadamore@1562:                 } else if (stuck) {
mcimadamore@1562:                     //some variables could not be instantiated because of cycles in
mcimadamore@1562:                     //upper bounds - provide a (possibly recursive) default instantiation
mcimadamore@1562:                     instantiateAsUninferredVars(restvars(), this);
mcimadamore@1562:                     break;
mcimadamore@1562:                 } else {
mcimadamore@1562:                     //some variables have been instantiated - replace newly instantiated
mcimadamore@1562:                     //variables in remaining upper bounds and continue
mcimadamore@1562:                     for (Type t : undetvars) {
mcimadamore@1562:                         UndetVar uv = (UndetVar)t;
mcimadamore@1562:                         uv.substBounds(inferenceVars(), instTypes(), types);
mcimadamore@1562:                     }
mcimadamore@1562:                 }
mcimadamore@1347:             }
mcimadamore@1562:             checkWithinBounds(this, warn);
mcimadamore@1562:         }
mcimadamore@1562: 
mcimadamore@1562:         private Infer infer() {
mcimadamore@1562:             //back-door to infer
mcimadamore@1562:             return Infer.this;
mcimadamore@1347:         }
vromero@2302: 
vromero@2302:         @Override
vromero@2302:         public String toString() {
vromero@2302:             return "Inference vars: " + inferencevars + '\n' +
vromero@2302:                    "Undet vars: " + undetvars;
vromero@2302:         }
vromero@2382: 
vromero@2382:         /* Method Types.capture() generates a new type every time it's applied
vromero@2382:          * to a wildcard parameterized type. This is intended functionality but
vromero@2382:          * there are some cases when what you need is not to generate a new
vromero@2382:          * captured type but to check that a previously generated captured type
vromero@2382:          * is correct. There are cases when caching a captured type for later
vromero@2382:          * reuse is sound. In general two captures from the same AST are equal.
vromero@2382:          * This is why the tree is used as the key of the map below. This map
vromero@2382:          * stores a Type per AST.
vromero@2382:          */
vromero@2382:         Map<JCTree, Type> captureTypeCache = new HashMap<>();
vromero@2382: 
vromero@2382:         Type cachedCapture(JCTree tree, Type t, boolean readOnly) {
vromero@2382:             Type captured = captureTypeCache.get(tree);
vromero@2382:             if (captured != null) {
vromero@2382:                 return captured;
vromero@2382:             }
vromero@2382: 
vromero@2382:             Type result = types.capture(t);
vromero@2382:             if (result != t && !readOnly) { // then t is a wildcard parameterized type
vromero@2382:                 captureTypeCache.put(tree, result);
vromero@2382:             }
vromero@2382:             return result;
vromero@2382:         }
mcimadamore@895:     }
mcimadamore@1337: 
mcimadamore@1550:     final InferenceContext emptyContext = new InferenceContext(List.<Type>nil());
mcimadamore@1550:     // </editor-fold>
mcimadamore@1337: }