xref: /openjdk10/langtools/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java

/*
 * Copyright (c) 1999, 2016, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package com.sun.tools.javac.comp;

import com.sun.tools.javac.code.Type.UndetVar.UndetVarListener;
import com.sun.tools.javac.tree.JCTree;
import com.sun.tools.javac.tree.JCTree.JCTypeCast;
import com.sun.tools.javac.tree.TreeInfo;
import com.sun.tools.javac.util.*;
import com.sun.tools.javac.util.GraphUtils.DottableNode;
import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
import com.sun.tools.javac.util.List;
import com.sun.tools.javac.code.*;
import com.sun.tools.javac.code.Type.*;
import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
import com.sun.tools.javac.code.Symbol.*;
import com.sun.tools.javac.comp.DeferredAttr.AttrMode;
import com.sun.tools.javac.comp.DeferredAttr.DeferredAttrContext;
import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph;
import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node;
import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;

import java.io.IOException;
import java.io.Writer;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.EnumMap;
import java.util.EnumSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Properties;
import java.util.Set;
import java.util.function.BiFunction;
import java.util.function.BiPredicate;

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

/** Helper class for type parameter inference, used by the attribution phase.
 *
 *  <p><b>This is NOT part of any supported API.
 *  If you write code that depends on this, you do so at your own risk.
 *  This code and its internal interfaces are subject to change or
 *  deletion without notice.</b>
 */
public class Infer {
    protected static final Context.Key<Infer> inferKey = new Context.Key<>();

    Resolve rs;
    Check chk;
    Symtab syms;
    Types types;
    JCDiagnostic.Factory diags;
    Log log;

    /** should the graph solver be used? */
    boolean allowGraphInference;

    /**
     * folder in which the inference dependency graphs should be written.
     */
    final private String dependenciesFolder;

    /**
     * List of graphs awaiting to be dumped to a file.
     */
    private List<String> pendingGraphs;

    public static Infer instance(Context context) {
        Infer instance = context.get(inferKey);
        if (instance == null)
            instance = new Infer(context);
        return instance;
    }

    protected Infer(Context context) {
        context.put(inferKey, this);

        rs = Resolve.instance(context);
        chk = Check.instance(context);
        syms = Symtab.instance(context);
        types = Types.instance(context);
        diags = JCDiagnostic.Factory.instance(context);
        log = Log.instance(context);
        inferenceException = new InferenceException(diags);
        Options options = Options.instance(context);
        allowGraphInference = Source.instance(context).allowGraphInference()
                && options.isUnset("useLegacyInference");
        dependenciesFolder = options.get("dumpInferenceGraphsTo");
        pendingGraphs = List.nil();

        emptyContext = new InferenceContext(this, List.<Type>nil());
    }

    /** A value for prototypes that admit any type, including polymorphic ones. */
    public static final Type anyPoly = new JCNoType();

   /**
    * This exception class is design to store a list of diagnostics corresponding
    * to inference errors that can arise during a method applicability check.
    */
    public static class InferenceException extends InapplicableMethodException {
        private static final long serialVersionUID = 0;

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

        InferenceException(JCDiagnostic.Factory diags) {
            super(diags);
        }

        @Override
        InapplicableMethodException setMessage() {
            //no message to set
            return this;
        }

        @Override
        InapplicableMethodException setMessage(JCDiagnostic diag) {
            messages = messages.append(diag);
            return this;
        }

        @Override
        public JCDiagnostic getDiagnostic() {
            return messages.head;
        }

        void clear() {
            messages = List.nil();
        }
    }

    protected final InferenceException inferenceException;

    // <editor-fold defaultstate="collapsed" desc="Inference routines">
    /**
     * Main inference entry point - instantiate a generic method type
     * using given argument types and (possibly) an expected target-type.
     */
    Type instantiateMethod( Env<AttrContext> env,
                            List<Type> tvars,
                            MethodType mt,
                            Attr.ResultInfo resultInfo,
                            MethodSymbol msym,
                            List<Type> argtypes,
                            boolean allowBoxing,
                            boolean useVarargs,
                            Resolve.MethodResolutionContext resolveContext,
                            Warner warn) throws InferenceException {
        //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
        final InferenceContext inferenceContext = new InferenceContext(this, tvars);  //B0
        inferenceException.clear();
        try {
            DeferredAttr.DeferredAttrContext deferredAttrContext =
                        resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);

            resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext,   //B2
                    argtypes, mt.getParameterTypes(), warn);

            if (allowGraphInference && resultInfo != null && resultInfo.pt == anyPoly) {
                doIncorporation(inferenceContext, warn);
                //we are inside method attribution - just return a partially inferred type
                return new PartiallyInferredMethodType(mt, inferenceContext, env, warn);
            } else if (allowGraphInference &&
                    resultInfo != null &&
                    !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
                //inject return constraints earlier
                doIncorporation(inferenceContext, warn); //propagation

                boolean shouldPropagate = resultInfo.checkContext.inferenceContext().free(resultInfo.pt);

                InferenceContext minContext = shouldPropagate ?
                        inferenceContext.min(roots(mt, deferredAttrContext), true, warn) :
                        inferenceContext;

                Type newRestype = generateReturnConstraints(env.tree, resultInfo,  //B3
                        mt, minContext);
                mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype);

                //propagate outwards if needed
                if (shouldPropagate) {
                    //propagate inference context outwards and exit
                    minContext.dupTo(resultInfo.checkContext.inferenceContext());
                    deferredAttrContext.complete();
                    return mt;
                }
            }

            deferredAttrContext.complete();

            // minimize as yet undetermined type variables
            if (allowGraphInference) {
                inferenceContext.solve(warn);
            } else {
                inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst
            }

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

            if (!allowGraphInference &&
                    inferenceContext.restvars().nonEmpty() &&
                    resultInfo != null &&
                    !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
                generateReturnConstraints(env.tree, resultInfo, mt, inferenceContext);
                inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst
                mt = (MethodType)inferenceContext.asInstType(mt);
            }

            if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
                log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
            }

            // return instantiated version of method type
            return mt;
        } finally {
            if (resultInfo != null || !allowGraphInference) {
                inferenceContext.notifyChange();
            } else {
                inferenceContext.notifyChange(inferenceContext.boundedVars());
            }
            if (resultInfo == null) {
                /* if the is no result info then we can clear the capture types
                 * cache without affecting any result info check
                 */
                inferenceContext.captureTypeCache.clear();
            }
            dumpGraphsIfNeeded(env.tree, msym, resolveContext);
        }
    }
    //where
        private List<Type> roots(MethodType mt, DeferredAttrContext deferredAttrContext) {
            ListBuffer<Type> roots = new ListBuffer<>();
            roots.add(mt.getReturnType());
            if (deferredAttrContext != null && deferredAttrContext.mode == AttrMode.CHECK) {
                roots.addAll(mt.getThrownTypes());
                for (DeferredAttr.DeferredAttrNode n : deferredAttrContext.deferredAttrNodes) {
                    roots.addAll(n.deferredStuckPolicy.stuckVars());
                    roots.addAll(n.deferredStuckPolicy.depVars());
                }
            }
            return roots.toList();
        }

    /**
     * A partially infered method/constructor type; such a type can be checked multiple times
     * against different targets.
     */
    public class PartiallyInferredMethodType extends MethodType {
        public PartiallyInferredMethodType(MethodType mtype, InferenceContext inferenceContext, Env<AttrContext> env, Warner warn) {
            super(mtype.getParameterTypes(), mtype.getReturnType(), mtype.getThrownTypes(), mtype.tsym);
            this.inferenceContext = inferenceContext;
            this.env = env;
            this.warn = warn;
        }

        /** The inference context. */
        final InferenceContext inferenceContext;

        /** The attribution environment. */
        Env<AttrContext> env;

        /** The warner. */
        final Warner warn;

        @Override
        public boolean isPartial() {
            return true;
        }

        /**
         * Checks this type against a target; this means generating return type constraints, solve
         * and then roll back the results (to avoid poolluting the context).
         */
        Type check(Attr.ResultInfo resultInfo) {
            Warner noWarnings = new Warner(null);
            inferenceException.clear();
            List<Type> saved_undet = null;
            try {
                /** we need to save the inference context before generating target type constraints.
                 *  This constraints may pollute the inference context and make it useless in case we
                 *  need to use it several times: with several targets.
                 */
                saved_undet = inferenceContext.save();
                if (allowGraphInference && !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
                    boolean shouldPropagate = resultInfo.checkContext.inferenceContext().free(resultInfo.pt);

                    InferenceContext minContext = shouldPropagate ?
                            inferenceContext.min(roots(asMethodType(), null), false, warn) :
                            inferenceContext;

                    MethodType other = (MethodType)minContext.update(asMethodType());
                    Type newRestype = generateReturnConstraints(env.tree, resultInfo,  //B3
                            other, minContext);

                    if (shouldPropagate) {
                        //propagate inference context outwards and exit
                        minContext.dupTo(resultInfo.checkContext.inferenceContext(),
                                resultInfo.checkContext.deferredAttrContext().insideOverloadPhase());
                        return newRestype;
                    }
                }
                inferenceContext.solve(noWarnings);
                return inferenceContext.asInstType(this).getReturnType();
            } catch (InferenceException ex) {
                resultInfo.checkContext.report(null, ex.getDiagnostic());
                Assert.error(); //cannot get here (the above should throw)
                return null;
            } finally {
                if (saved_undet != null) {
                    inferenceContext.rollback(saved_undet);
                }
            }
        }
    }

    private void dumpGraphsIfNeeded(DiagnosticPosition pos, Symbol msym, Resolve.MethodResolutionContext rsContext) {
        int round = 0;
        try {
            for (String graph : pendingGraphs.reverse()) {
                Assert.checkNonNull(dependenciesFolder);
                Name name = msym.name == msym.name.table.names.init ?
                        msym.owner.name : msym.name;
                String filename = String.format("%s@%s[mode=%s,step=%s]_%d.dot",
                        name,
                        pos.getStartPosition(),
                        rsContext.attrMode(),
                        rsContext.step,
                        round);
                Path dotFile = Paths.get(dependenciesFolder, filename);
                try (Writer w = Files.newBufferedWriter(dotFile)) {
                    w.append(graph);
                }
                round++;
            }
        } catch (IOException ex) {
            Assert.error("Error occurred when dumping inference graph: " + ex.getMessage());
        } finally {
            pendingGraphs = List.nil();
        }
    }

    /**
     * Generate constraints from the generic method's return type. If the method
     * call occurs in a context where a type T is expected, use the expected
     * type to derive more constraints on the generic method inference variables.
     */
    Type generateReturnConstraints(JCTree tree, Attr.ResultInfo resultInfo,
            MethodType mt, InferenceContext inferenceContext) {
        InferenceContext rsInfoInfContext = resultInfo.checkContext.inferenceContext();
        Type from = mt.getReturnType();
        if (mt.getReturnType().containsAny(inferenceContext.inferencevars) &&
                rsInfoInfContext != emptyContext) {
            from = types.capture(from);
            //add synthetic captured ivars
            for (Type t : from.getTypeArguments()) {
                if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) {
                    inferenceContext.addVar((TypeVar)t);
                }
            }
        }
        Type qtype = inferenceContext.asUndetVar(from);
        Type to = resultInfo.pt;

        if (qtype.hasTag(VOID)) {
            to = syms.voidType;
        } else if (to.hasTag(NONE)) {
            to = from.isPrimitive() ? from : syms.objectType;
        } else if (qtype.hasTag(UNDETVAR)) {
            if (resultInfo.pt.isReference()) {
                to = generateReturnConstraintsUndetVarToReference(
                        tree, (UndetVar)qtype, to, resultInfo, inferenceContext);
            } else {
                if (to.isPrimitive()) {
                    to = generateReturnConstraintsPrimitive(tree, (UndetVar)qtype, to,
                        resultInfo, inferenceContext);
                }
            }
        } else if (rsInfoInfContext.free(resultInfo.pt)) {
            //propagation - cache captured vars
            qtype = inferenceContext.asUndetVar(rsInfoInfContext.cachedCapture(tree, from, false));
        }
        Assert.check(allowGraphInference || !rsInfoInfContext.free(to),
                "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");
        //we need to skip capture?
        Warner retWarn = new Warner();
        if (!resultInfo.checkContext.compatible(qtype, rsInfoInfContext.asUndetVar(to), retWarn) ||
                //unchecked conversion is not allowed in source 7 mode
                (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) {
            throw inferenceException
                    .setMessage("infer.no.conforming.instance.exists",
                    inferenceContext.restvars(), mt.getReturnType(), to);
        }
        return from;
    }

    private Type generateReturnConstraintsPrimitive(JCTree tree, UndetVar from,
            Type to, Attr.ResultInfo resultInfo, InferenceContext inferenceContext) {
        if (!allowGraphInference) {
            //if legacy, just return boxed type
            return types.boxedClass(to).type;
        }
        //if graph inference we need to skip conflicting boxed bounds...
        for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.UPPER,
                InferenceBound.LOWER)) {
            Type boundAsPrimitive = types.unboxedType(t);
            if (boundAsPrimitive == null || boundAsPrimitive.hasTag(NONE)) {
                continue;
            }
            return generateReferenceToTargetConstraint(tree, from, to,
                    resultInfo, inferenceContext);
        }
        return types.boxedClass(to).type;
    }

    private Type generateReturnConstraintsUndetVarToReference(JCTree tree,
            UndetVar from, Type to, Attr.ResultInfo resultInfo,
            InferenceContext inferenceContext) {
        Type captureOfTo = types.capture(to);
        /* T is a reference type, but is not a wildcard-parameterized type, and either
         */
        if (captureOfTo == to) { //not a wildcard parameterized type
            /* i) B2 contains a bound of one of the forms alpha = S or S <: alpha,
             *      where S is a wildcard-parameterized type, or
             */
            for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
                Type captureOfBound = types.capture(t);
                if (captureOfBound != t) {
                    return generateReferenceToTargetConstraint(tree, from, to,
                            resultInfo, inferenceContext);
                }
            }

            /* ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha,
             * where S1 and S2 have supertypes that are two different
             * parameterizations of the same generic class or interface.
             */
            for (Type aLowerBound : from.getBounds(InferenceBound.LOWER)) {
                for (Type anotherLowerBound : from.getBounds(InferenceBound.LOWER)) {
                    if (aLowerBound != anotherLowerBound &&
                            !inferenceContext.free(aLowerBound) &&
                            !inferenceContext.free(anotherLowerBound) &&
                            commonSuperWithDiffParameterization(aLowerBound, anotherLowerBound)) {
                        return generateReferenceToTargetConstraint(tree, from, to,
                            resultInfo, inferenceContext);
                    }
                }
            }
        }

        /* T is a parameterization of a generic class or interface, G,
         * and B2 contains a bound of one of the forms alpha = S or S <: alpha,
         * where there exists no type of the form G<...> that is a
         * supertype of S, but the raw type G is a supertype of S
         */
        if (to.isParameterized()) {
            for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
                Type sup = types.asSuper(t, to.tsym);
                if (sup != null && sup.isRaw()) {
                    return generateReferenceToTargetConstraint(tree, from, to,
                            resultInfo, inferenceContext);
                }
            }
        }
        return to;
    }

    private boolean commonSuperWithDiffParameterization(Type t, Type s) {
        for (Pair<Type, Type> supers : getParameterizedSupers(t, s)) {
            if (!types.isSameType(supers.fst, supers.snd)) return true;
        }
        return false;
    }

    private Type generateReferenceToTargetConstraint(JCTree tree, UndetVar from,
            Type to, Attr.ResultInfo resultInfo,
            InferenceContext inferenceContext) {
        inferenceContext.solve(List.of(from.qtype), new Warner());
        inferenceContext.notifyChange();
        Type capturedType = resultInfo.checkContext.inferenceContext()
                .cachedCapture(tree, from.getInst(), false);
        if (types.isConvertible(capturedType,
                resultInfo.checkContext.inferenceContext().asUndetVar(to))) {
            //effectively skip additional return-type constraint generation (compatibility)
            return syms.objectType;
        }
        return to;
    }

    /**
      * Infer cyclic inference variables as described in 15.12.2.8.
      */
    void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) {
        ListBuffer<Type> todo = new ListBuffer<>();
        //step 1 - create fresh tvars
        for (Type t : vars) {
            UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t);
            List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER);
            if (Type.containsAny(upperBounds, vars)) {
                TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
                fresh_tvar.type = new TypeVar(fresh_tvar, types.makeIntersectionType(uv.getBounds(InferenceBound.UPPER)), null);
                todo.append(uv);
                uv.setInst(fresh_tvar.type);
            } else if (upperBounds.nonEmpty()) {
                uv.setInst(types.glb(upperBounds));
            } else {
                uv.setInst(syms.objectType);
            }
        }
        //step 2 - replace fresh tvars in their bounds
        List<Type> formals = vars;
        for (Type t : todo) {
            UndetVar uv = (UndetVar)t;
            TypeVar ct = (TypeVar)uv.getInst();
            ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct)));
            if (ct.bound.isErroneous()) {
                //report inference error if glb fails
                reportBoundError(uv, InferenceBound.UPPER);
            }
            formals = formals.tail;
        }
    }

    /**
     * Compute a synthetic method type corresponding to the requested polymorphic
     * method signature. The target return type is computed from the immediately
     * enclosing scope surrounding the polymorphic-signature call.
     */
    Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
                                            MethodSymbol spMethod,  // sig. poly. method or null if none
                                            Resolve.MethodResolutionContext resolveContext,
                                            List<Type> argtypes) {
        final Type restype;

        //The return type for a polymorphic signature call is computed from
        //the enclosing tree E, as follows: if E is a cast, then use the
        //target type of the cast expression as a return type; if E is an
        //expression statement, the return type is 'void' - otherwise the
        //return type is simply 'Object'. A correctness check ensures that
        //env.next refers to the lexically enclosing environment in which
        //the polymorphic signature call environment is nested.

        switch (env.next.tree.getTag()) {
            case TYPECAST:
                JCTypeCast castTree = (JCTypeCast)env.next.tree;
                restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
                    castTree.clazz.type :
                    syms.objectType;
                break;
            case EXEC:
                JCTree.JCExpressionStatement execTree =
                        (JCTree.JCExpressionStatement)env.next.tree;
                restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
                    syms.voidType :
                    syms.objectType;
                break;
            default:
                restype = syms.objectType;
        }

        List<Type> paramtypes = argtypes.map(new ImplicitArgType(spMethod, resolveContext.step));
        List<Type> exType = spMethod != null ?
            spMethod.getThrownTypes() :
            List.of(syms.throwableType); // make it throw all exceptions

        MethodType mtype = new MethodType(paramtypes,
                                          restype,
                                          exType,
                                          syms.methodClass);
        return mtype;
    }
    //where
        class ImplicitArgType extends DeferredAttr.DeferredTypeMap {

            public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {
                (rs.deferredAttr).super(AttrMode.SPECULATIVE, msym, phase);
            }

            @Override
            public Type visitClassType(ClassType t, Void aVoid) {
                return types.erasure(t);
            }

            @Override
            public Type visitType(Type t, Void _unused) {
                if (t.hasTag(DEFERRED)) {
                    return visit(super.visitType(t, null));
                } else if (t.hasTag(BOT))
                    // nulls type as the marker type Null (which has no instances)
                    // infer as java.lang.Void for now
                    t = types.boxedClass(syms.voidType).type;
                return t;
            }
        }

    TypeMapping<Void> fromTypeVarFun = new TypeMapping<Void>() {
        @Override
        public Type visitTypeVar(TypeVar tv, Void aVoid) {
            return new UndetVar(tv, incorporationEngine(), types);
        }

        @Override
        public Type visitCapturedType(CapturedType t, Void aVoid) {
            return new CapturedUndetVar(t, incorporationEngine(), types);
        }
    };

    /**
      * This method is used to infer a suitable target SAM in case the original
      * SAM type contains one or more wildcards. An inference process is applied
      * so that wildcard bounds, as well as explicit lambda/method ref parameters
      * (where applicable) are used to constraint the solution.
      */
    public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,
            List<Type> paramTypes, Check.CheckContext checkContext) {
        if (types.capture(funcInterface) == funcInterface) {
            //if capture doesn't change the type then return the target unchanged
            //(this means the target contains no wildcards!)
            return funcInterface;
        } else {
            Type formalInterface = funcInterface.tsym.type;
            InferenceContext funcInterfaceContext =
                    new InferenceContext(this, funcInterface.tsym.type.getTypeArguments());

            Assert.check(paramTypes != null);
            //get constraints from explicit params (this is done by
            //checking that explicit param types are equal to the ones
            //in the functional interface descriptors)
            List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();
            if (descParameterTypes.size() != paramTypes.size()) {
                checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda"));
                return types.createErrorType(funcInterface);
            }
            for (Type p : descParameterTypes) {
                if (!types.isSameType(funcInterfaceContext.asUndetVar(p), paramTypes.head)) {
                    checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
                    return types.createErrorType(funcInterface);
                }
                paramTypes = paramTypes.tail;
            }

            try {
                funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings);
            } catch (InferenceException ex) {
                checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
            }

            List<Type> actualTypeargs = funcInterface.getTypeArguments();
            for (Type t : funcInterfaceContext.undetvars) {
                UndetVar uv = (UndetVar)t;
                if (uv.getInst() == null) {
                    uv.setInst(actualTypeargs.head);
                }
                actualTypeargs = actualTypeargs.tail;
            }

            Type owntype = funcInterfaceContext.asInstType(formalInterface);
            if (!chk.checkValidGenericType(owntype)) {
                //if the inferred functional interface type is not well-formed,
                //or if it's not a subtype of the original target, issue an error
                checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
            }
            //propagate constraints as per JLS 18.2.1
            checkContext.compatible(owntype, funcInterface, types.noWarnings);
            return owntype;
        }
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Incorporation">

    /**
     * This class is the root of all incorporation actions.
     */
    public abstract class IncorporationAction {
        UndetVar uv;
        Type t;

        IncorporationAction(UndetVar uv, Type t) {
            this.uv = uv;
            this.t = t;
        }

        /**
         * Incorporation action entry-point. Subclasses should define the logic associated with
         * this incorporation action.
         */
        abstract void apply(InferenceContext ic, Warner warn);

        /**
         * Helper function: perform subtyping through incorporation cache.
         */
        boolean isSubtype(Type s, Type t, Warner warn) {
            return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn);
        }

        /**
         * Helper function: perform type-equivalence through incorporation cache.
         */
        boolean isSameType(Type s, Type t) {
            return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null);
        }

        @Override
        public String toString() {
            return String.format("%s[undet=%s,t=%s]", getClass().getSimpleName(), uv.qtype, t);
        }
    }

    /**
     * Bound-check incorporation action. A newly added bound is checked against existing bounds,
     * to verify its compatibility; each bound is checked using either subtyping or type equivalence.
     */
    class CheckBounds extends IncorporationAction {

        InferenceBound from;
        BiFunction<InferenceContext, Type, Type> typeFunc;
        BiPredicate<InferenceContext, Type> optFilter;

        CheckBounds(UndetVar uv, Type t, InferenceBound from) {
            this(uv, t, InferenceContext::asUndetVar, null, from);
        }

        CheckBounds(UndetVar uv, Type t, BiFunction<InferenceContext, Type, Type> typeFunc,
                    BiPredicate<InferenceContext, Type> typeFilter, InferenceBound from) {
            super(uv, t);
            this.from = from;
            this.typeFunc = typeFunc;
            this.optFilter = typeFilter;
        }

        @Override
        void apply(InferenceContext inferenceContext, Warner warn) {
            t = typeFunc.apply(inferenceContext, t);
            if (optFilter != null && optFilter.test(inferenceContext, t)) return;
            for (InferenceBound to : boundsToCheck()) {
                for (Type b : uv.getBounds(to)) {
                    b = typeFunc.apply(inferenceContext, b);
                    if (optFilter != null && optFilter.test(inferenceContext, b)) continue;
                    boolean success = checkBound(t, b, from, to, warn);
                    if (!success) {
                        report(from, to);
                    }
                }
            }
        }

        /**
         * The list of bound kinds to be checked.
         */
        EnumSet<InferenceBound> boundsToCheck() {
            return (from == InferenceBound.EQ) ?
                            EnumSet.allOf(InferenceBound.class) :
                            EnumSet.complementOf(EnumSet.of(from));
        }

        /**
         * Is source type 's' compatible with target type 't' given source and target bound kinds?
         */
        boolean checkBound(Type s, Type t, InferenceBound ib_s, InferenceBound ib_t, Warner warn) {
            if (ib_s.lessThan(ib_t)) {
                return isSubtype(s, t, warn);
            } else if (ib_t.lessThan(ib_s)) {
                return isSubtype(t, s, warn);
            } else {
                return isSameType(s, t);
            }
        }

        /**
         * Report a bound check error.
         */
        void report(InferenceBound from, InferenceBound to) {
            //this is a workaround to preserve compatibility with existing messages
            if (from == to) {
                reportBoundError(uv, from);
            } else if (from == InferenceBound.LOWER || to == InferenceBound.EQ) {
                reportBoundError(uv, to, from);
            } else {
                reportBoundError(uv, from, to);
            }
        }

        @Override
        public String toString() {
            return String.format("%s[undet=%s,t=%s,bound=%s]", getClass().getSimpleName(), uv.qtype, t, from);
        }
    }

    /**
     * Custom check executed by the legacy incorporation engine. Newly added bounds are checked
     * against existing eq bounds.
     */
    class EqCheckLegacy extends CheckBounds {
        EqCheckLegacy(UndetVar uv, Type t, InferenceBound from) {
            super(uv, t, InferenceContext::asInstType, InferenceContext::free, from);
        }

        @Override
        EnumSet<InferenceBound> boundsToCheck() {
            return (from == InferenceBound.EQ) ?
                            EnumSet.allOf(InferenceBound.class) :
                            EnumSet.of(InferenceBound.EQ);
        }
    }

    /**
     * Check that the inferred type conforms to all bounds.
     */
    class CheckInst extends CheckBounds {

        EnumSet<InferenceBound> to;

        CheckInst(UndetVar uv, InferenceBound ib, InferenceBound... rest) {
            super(uv, uv.getInst(), InferenceBound.EQ);
            this.to = EnumSet.of(ib, rest);
        }

        @Override
        EnumSet<InferenceBound> boundsToCheck() {
            return to;
        }

        @Override
        void report(InferenceBound from, InferenceBound to) {
            reportInstError(uv, to);
        }
    }

    /**
     * Replace undetvars in bounds and check that the inferred type conforms to all bounds.
     */
    class SubstBounds extends CheckInst {
        SubstBounds(UndetVar uv) {
            super(uv, InferenceBound.LOWER, InferenceBound.EQ, InferenceBound.UPPER);
        }

        @Override
        void apply(InferenceContext inferenceContext, Warner warn) {
            for (Type undet : inferenceContext.undetvars) {
                //we could filter out variables not mentioning uv2...
                UndetVar uv2 = (UndetVar)undet;
                uv2.substBounds(List.of(uv.qtype), List.of(uv.getInst()), types);
                checkCompatibleUpperBounds(uv2, inferenceContext);
            }
            super.apply(inferenceContext, warn);
        }

        /**
         * Make sure that the upper bounds we got so far lead to a solvable inference
         * variable by making sure that a glb exists.
         */
        void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {
            List<Type> hibounds =
                    Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));
            final Type hb;
            if (hibounds.isEmpty())
                hb = syms.objectType;
            else if (hibounds.tail.isEmpty())
                hb = hibounds.head;
            else
                hb = types.glb(hibounds);
            if (hb == null || hb.isErroneous())
                reportBoundError(uv, InferenceBound.UPPER);
        }
    }

    /**
     * Perform pairwise comparison between common generic supertypes of two upper bounds.
     */
    class CheckUpperBounds extends IncorporationAction {

        public CheckUpperBounds(UndetVar uv, Type t) {
            super(uv, t);
        }

        @Override
        void apply(InferenceContext inferenceContext, Warner warn) {
            List<Type> boundList = uv.getBounds(InferenceBound.UPPER).stream()
                    .collect(types.closureCollector(true, types::isSameType));
            for (Type b2 : boundList) {
                if (t == b2) continue;
                    /* This wildcard check is temporary workaround. This code may need to be
                     * revisited once spec bug JDK-7034922 is fixed.
                     */
                if (t != b2 && !t.hasTag(WILDCARD) && !b2.hasTag(WILDCARD)) {
                    for (Pair<Type, Type> commonSupers : getParameterizedSupers(t, b2)) {
                        List<Type> allParamsSuperBound1 = commonSupers.fst.allparams();
                        List<Type> allParamsSuperBound2 = commonSupers.snd.allparams();
                        while (allParamsSuperBound1.nonEmpty() && allParamsSuperBound2.nonEmpty()) {
                            //traverse the list of all params comparing them
                            if (!allParamsSuperBound1.head.hasTag(WILDCARD) &&
                                    !allParamsSuperBound2.head.hasTag(WILDCARD)) {
                                if (!isSameType(inferenceContext.asUndetVar(allParamsSuperBound1.head),
                                        inferenceContext.asUndetVar(allParamsSuperBound2.head))) {
                                    reportBoundError(uv, InferenceBound.UPPER);
                                }
                            }
                            allParamsSuperBound1 = allParamsSuperBound1.tail;
                            allParamsSuperBound2 = allParamsSuperBound2.tail;
                        }
                        Assert.check(allParamsSuperBound1.isEmpty() && allParamsSuperBound2.isEmpty());
                    }
                }
            }
        }
    }

    /**
     * Perform propagation of bounds. Given a constraint of the kind {@code alpha <: T}, three
     * kind of propagation occur:
     *
     * <li>T is copied into all matching bounds (i.e. lower/eq bounds) B of alpha such that B=beta (forward propagation)</li>
     * <li>if T=beta, matching bounds (i.e. upper bounds) of beta are copied into alpha (backwards propagation)</li>
     * <li>if T=beta, sets a symmetric bound on beta (i.e. beta :> alpha) (symmetric propagation) </li>
     */
    class PropagateBounds extends IncorporationAction {

        InferenceBound ib;

        public PropagateBounds(UndetVar uv, Type t, InferenceBound ib) {
            super(uv, t);
            this.ib = ib;
        }

        void apply(InferenceContext inferenceContext, Warner warner) {
            Type undetT = inferenceContext.asUndetVar(t);
            if (undetT.hasTag(UNDETVAR) && !((UndetVar)undetT).isCaptured()) {
                UndetVar uv2 = (UndetVar)undetT;
                //symmetric propagation
                uv2.addBound(ib.complement(), uv, types);
                //backwards propagation
                for (InferenceBound ib2 : backwards()) {
                    for (Type b : uv2.getBounds(ib2)) {
                        uv.addBound(ib2, b, types);
                    }
                }
            }
            //forward propagation
            for (InferenceBound ib2 : forward()) {
                for (Type l : uv.getBounds(ib2)) {
                    Type undet = inferenceContext.asUndetVar(l);
                    if (undet.hasTag(TypeTag.UNDETVAR) && !((UndetVar)undet).isCaptured()) {
                        UndetVar uv2 = (UndetVar)undet;
                        uv2.addBound(ib, inferenceContext.asInstType(t), types);
                    }
                }
            }
        }

        EnumSet<InferenceBound> forward() {
            return (ib == InferenceBound.EQ) ?
                    EnumSet.of(InferenceBound.EQ) : EnumSet.complementOf(EnumSet.of(ib));
        }

        EnumSet<InferenceBound> backwards() {
            return (ib == InferenceBound.EQ) ?
                    EnumSet.allOf(InferenceBound.class) : EnumSet.of(ib);
        }

        @Override
        public String toString() {
            return String.format("%s[undet=%s,t=%s,bound=%s]", getClass().getSimpleName(), uv.qtype, t, ib);
        }
    }

    /**
     * This class models an incorporation engine. The engine is responsible for listening to
     * changes in inference variables and register incorporation actions accordingly.
     */
    abstract class AbstractIncorporationEngine implements UndetVarListener {

        @Override
        public void varInstantiated(UndetVar uv) {
            uv.incorporationActions.addFirst(new SubstBounds(uv));
        }

        @Override
        public void varBoundChanged(UndetVar uv, InferenceBound ib, Type bound, boolean update) {
            if (uv.isCaptured()) return;
            uv.incorporationActions.addAll(getIncorporationActions(uv, ib, bound, update));
        }

        abstract List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update);
    }

    /**
     * A legacy incorporation engine. Used for source <= 7.
     */
    AbstractIncorporationEngine legacyEngine = new AbstractIncorporationEngine() {

        List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update) {
            ListBuffer<IncorporationAction> actions = new ListBuffer<>();
            Type inst = uv.getInst();
            if (inst != null) {
                actions.add(new CheckInst(uv, ib));
            }
            actions.add(new EqCheckLegacy(uv, t, ib));
            return actions.toList();
        }
    };

    /**
     * The standard incorporation engine. Used for source >= 8.
     */
    AbstractIncorporationEngine graphEngine = new AbstractIncorporationEngine() {

        @Override
        List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update) {
            ListBuffer<IncorporationAction> actions = new ListBuffer<>();
            Type inst = uv.getInst();
            if (inst != null) {
                actions.add(new CheckInst(uv, ib));
            }
            actions.add(new CheckBounds(uv, t, ib));

            if (update) {
                return actions.toList();
            }

            if (ib == InferenceBound.UPPER) {
                actions.add(new CheckUpperBounds(uv, t));
            }

            actions.add(new PropagateBounds(uv, t, ib));

            return actions.toList();
        }
    };

    /**
     * Get the incorporation engine to be used in this compilation.
     */
    AbstractIncorporationEngine incorporationEngine() {
        return allowGraphInference ? graphEngine : legacyEngine;
    }

    /** max number of incorporation rounds. */
    static final int MAX_INCORPORATION_STEPS = 10000;

    /**
     * Check bounds and perform incorporation.
     */
    void doIncorporation(InferenceContext inferenceContext, Warner warn) throws InferenceException {
        try {
            boolean progress = true;
            int round = 0;
            while (progress && round < MAX_INCORPORATION_STEPS) {
                progress = false;
                for (Type t : inferenceContext.undetvars) {
                    UndetVar uv = (UndetVar)t;
                    if (!uv.incorporationActions.isEmpty()) {
                        progress = true;
                        uv.incorporationActions.removeFirst().apply(inferenceContext, warn);
                    }
                }
                round++;
            }
        } finally {
            incorporationCache.clear();
        }
    }

    /* If for two types t and s there is a least upper bound that contains
     * parameterized types G1, G2 ... Gn, then there exists supertypes of 't' of the form
     * G1<T1, ..., Tn>, G2<T1, ..., Tn>, ... Gn<T1, ..., Tn> and supertypes of 's' of the form
     * G1<S1, ..., Sn>, G2<S1, ..., Sn>, ... Gn<S1, ..., Sn> which will be returned by this method.
     * If no such common supertypes exists then an empty list is returned.
     *
     * As an example for the following input:
     *
     * t = java.util.ArrayList<java.lang.String>
     * s = java.util.List<T>
     *
     * we get this ouput (singleton list):
     *
     * [Pair[java.util.List<java.lang.String>,java.util.List<T>]]
     */
    private List<Pair<Type, Type>> getParameterizedSupers(Type t, Type s) {
        Type lubResult = types.lub(t, s);
        if (lubResult == syms.errType || lubResult == syms.botType) {
            return List.nil();
        }
        List<Type> supertypesToCheck = lubResult.isIntersection() ?
                ((IntersectionClassType)lubResult).getComponents() :
                List.of(lubResult);
        ListBuffer<Pair<Type, Type>> commonSupertypes = new ListBuffer<>();
        for (Type sup : supertypesToCheck) {
            if (sup.isParameterized()) {
                Type asSuperOfT = asSuper(t, sup);
                Type asSuperOfS = asSuper(s, sup);
                commonSupertypes.add(new Pair<>(asSuperOfT, asSuperOfS));
            }
        }
        return commonSupertypes.toList();
    }
    //where
        private Type asSuper(Type t, Type sup) {
            return (sup.hasTag(ARRAY)) ?
                    new ArrayType(asSuper(types.elemtype(t), types.elemtype(sup)), syms.arrayClass) :
                    types.asSuper(t, sup.tsym);
        }

    boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn) {
            IncorporationBinaryOp newOp = new IncorporationBinaryOp(opKind, op1, op2);
            Boolean res = incorporationCache.get(newOp);
            if (res == null) {
                incorporationCache.put(newOp, res = newOp.apply(warn));
            }
            return res;
        }

    /**
     * Three kinds of basic operation are supported as part of an incorporation step:
     * (i) subtype check, (ii) same type check and (iii) bound addition (either
     * upper/lower/eq bound).
     */
    enum IncorporationBinaryOpKind {
        IS_SUBTYPE() {
            @Override
            boolean apply(Type op1, Type op2, Warner warn, Types types) {
                return types.isSubtypeUnchecked(op1, op2, warn);
            }
        },
        IS_SAME_TYPE() {
            @Override
            boolean apply(Type op1, Type op2, Warner warn, Types types) {
                return types.isSameType(op1, op2);
            }
        };

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

    /**
     * This class encapsulates a basic incorporation operation; incorporation
     * operations takes two type operands and a kind. Each operation performed
     * during an incorporation round is stored in a cache, so that operations
     * are not executed unnecessarily (which would potentially lead to adding
     * same bounds over and over).
     */
    class IncorporationBinaryOp {

        IncorporationBinaryOpKind opKind;
        Type op1;
        Type op2;

        IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) {
            this.opKind = opKind;
            this.op1 = op1;
            this.op2 = op2;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof IncorporationBinaryOp)) {
                return false;
            } else {
                IncorporationBinaryOp that = (IncorporationBinaryOp)o;
                return opKind == that.opKind &&
                        types.isSameType(op1, that.op1, true) &&
                        types.isSameType(op2, that.op2, true);
            }
        }

        @Override
        public int hashCode() {
            int result = opKind.hashCode();
            result *= 127;
            result += types.hashCode(op1);
            result *= 127;
            result += types.hashCode(op2);
            return result;
        }

        boolean apply(Warner warn) {
            return opKind.apply(op1, op2, warn, types);
        }
    }

    /** an incorporation cache keeps track of all executed incorporation-related operations */
    Map<IncorporationBinaryOp, Boolean> incorporationCache = new HashMap<>();

    protected static class BoundFilter implements Filter<Type> {

        InferenceContext inferenceContext;

        public BoundFilter(InferenceContext inferenceContext) {
            this.inferenceContext = inferenceContext;
        }

        @Override
        public boolean accepts(Type t) {
            return !t.isErroneous() && !inferenceContext.free(t) &&
                    !t.hasTag(BOT);
        }
    }

    /**
     * Incorporation error: mismatch between inferred type and given bound.
     */
    void reportInstError(UndetVar uv, InferenceBound ib) {
        reportInferenceError(
                String.format("inferred.do.not.conform.to.%s.bounds", StringUtils.toLowerCase(ib.name())),
                uv.getInst(),
                uv.getBounds(ib));
    }

    /**
     * Incorporation error: mismatch between two (or more) bounds of same kind.
     */
    void reportBoundError(UndetVar uv, InferenceBound ib) {
        reportInferenceError(
                String.format("incompatible.%s.bounds", StringUtils.toLowerCase(ib.name())),
                uv.qtype,
                uv.getBounds(ib));
    }

    /**
     * Incorporation error: mismatch between two (or more) bounds of different kinds.
     */
    void reportBoundError(UndetVar uv, InferenceBound ib1, InferenceBound ib2) {
        reportInferenceError(
                String.format("incompatible.%s.%s.bounds",
                        StringUtils.toLowerCase(ib1.name()),
                        StringUtils.toLowerCase(ib2.name())),
                uv.qtype,
                uv.getBounds(ib1),
                uv.getBounds(ib2));
    }

    /**
     * Helper method: reports an inference error.
     */
    void reportInferenceError(String key, Object... args) {
        throw inferenceException.setMessage(key, args);
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Inference engine">
    /**
     * Graph inference strategy - act as an input to the inference solver; a strategy is
     * composed of two ingredients: (i) find a node to solve in the inference graph,
     * and (ii) tell th engine when we are done fixing inference variables
     */
    interface GraphStrategy {

        /**
         * A NodeNotFoundException is thrown whenever an inference strategy fails
         * to pick the next node to solve in the inference graph.
         */
        public static class NodeNotFoundException extends RuntimeException {
            private static final long serialVersionUID = 0;

            InferenceGraph graph;

            public NodeNotFoundException(InferenceGraph graph) {
                this.graph = graph;
            }
        }
        /**
         * Pick the next node (leaf) to solve in the graph
         */
        Node pickNode(InferenceGraph g) throws NodeNotFoundException;
        /**
         * Is this the last step?
         */
        boolean done();
    }

    /**
     * Simple solver strategy class that locates all leaves inside a graph
     * and picks the first leaf as the next node to solve
     */
    abstract class LeafSolver implements GraphStrategy {
        public Node pickNode(InferenceGraph g) {
            if (g.nodes.isEmpty()) {
                //should not happen
                throw new NodeNotFoundException(g);
            }
            return g.nodes.get(0);
        }
    }

    /**
     * This solver uses an heuristic to pick the best leaf - the heuristic
     * tries to select the node that has maximal probability to contain one
     * or more inference variables in a given list
     */
    abstract class BestLeafSolver extends LeafSolver {

        /** list of ivars of which at least one must be solved */
        List<Type> varsToSolve;

        BestLeafSolver(List<Type> varsToSolve) {
            this.varsToSolve = varsToSolve;
        }

        /**
         * Computes a path that goes from a given node to the leafs in the graph.
         * Typically this will start from a node containing a variable in
         * {@code varsToSolve}. For any given path, the cost is computed as the total
         * number of type-variables that should be eagerly instantiated across that path.
         */
        Pair<List<Node>, Integer> computeTreeToLeafs(Node n) {
            Pair<List<Node>, Integer> cachedPath = treeCache.get(n);
            if (cachedPath == null) {
                //cache miss
                if (n.isLeaf()) {
                    //if leaf, stop
                    cachedPath = new Pair<>(List.of(n), n.data.length());
                } else {
                    //if non-leaf, proceed recursively
                    Pair<List<Node>, Integer> path = new Pair<>(List.of(n), n.data.length());
                    for (Node n2 : n.getAllDependencies()) {
                        if (n2 == n) continue;
                        Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2);
                        path = new Pair<>(path.fst.prependList(subpath.fst),
                                          path.snd + subpath.snd);
                    }
                    cachedPath = path;
                }
                //save results in cache
                treeCache.put(n, cachedPath);
            }
            return cachedPath;
        }

        /** cache used to avoid redundant computation of tree costs */
        final Map<Node, Pair<List<Node>, Integer>> treeCache = new HashMap<>();

        /** constant value used to mark non-existent paths */
        final Pair<List<Node>, Integer> noPath = new Pair<>(null, Integer.MAX_VALUE);

        /**
         * Pick the leaf that minimize cost
         */
        @Override
        public Node pickNode(final InferenceGraph g) {
            treeCache.clear(); //graph changes at every step - cache must be cleared
            Pair<List<Node>, Integer> bestPath = noPath;
            for (Node n : g.nodes) {
                if (!Collections.disjoint(n.data, varsToSolve)) {
                    Pair<List<Node>, Integer> path = computeTreeToLeafs(n);
                    //discard all paths containing at least a node in the
                    //closure computed above
                    if (path.snd < bestPath.snd) {
                        bestPath = path;
                    }
                }
            }
            if (bestPath == noPath) {
                //no path leads there
                throw new NodeNotFoundException(g);
            }
            return bestPath.fst.head;
        }
    }

    /**
     * The inference process can be thought of as a sequence of steps. Each step
     * instantiates an inference variable using a subset of the inference variable
     * bounds, if certain condition are met. Decisions such as the sequence in which
     * steps are applied, or which steps are to be applied are left to the inference engine.
     */
    enum InferenceStep {

        /**
         * Instantiate an inference variables using one of its (ground) equality
         * constraints
         */
        EQ(InferenceBound.EQ) {
            @Override
            Type solve(UndetVar uv, InferenceContext inferenceContext) {
                return filterBounds(uv, inferenceContext).head;
            }
        },
        /**
         * Instantiate an inference variables using its (ground) lower bounds. Such
         * bounds are merged together using lub().
         */
        LOWER(InferenceBound.LOWER) {
            @Override
            Type solve(UndetVar uv, InferenceContext inferenceContext) {
                Infer infer = inferenceContext.infer;
                List<Type> lobounds = filterBounds(uv, inferenceContext);
                //note: lobounds should have at least one element
                Type owntype = lobounds.tail.tail == null  ? lobounds.head : infer.types.lub(lobounds);
                if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
                    throw infer.inferenceException
                        .setMessage("no.unique.minimal.instance.exists",
                                    uv.qtype, lobounds);
                } else {
                    return owntype;
                }
            }
        },
        /**
         * Infer uninstantiated/unbound inference variables occurring in 'throws'
         * clause as RuntimeException
         */
        THROWS(InferenceBound.UPPER) {
            @Override
            public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
                if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) {
                    //not a throws undet var
                    return false;
                }
                if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER)
                            .diff(t.getDeclaredBounds()).nonEmpty()) {
                    //not an unbounded undet var
                    return false;
                }
                Infer infer = inferenceContext.infer;
                for (Type db : t.getDeclaredBounds()) {
                    if (t.isInterface()) continue;
                    if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) {
                        //declared bound is a supertype of RuntimeException
                        return true;
                    }
                }
                //declared bound is more specific then RuntimeException - give up
                return false;
            }

            @Override
            Type solve(UndetVar uv, InferenceContext inferenceContext) {
                return inferenceContext.infer.syms.runtimeExceptionType;
            }
        },
        /**
         * Instantiate an inference variables using its (ground) upper bounds. Such
         * bounds are merged together using glb().
         */
        UPPER(InferenceBound.UPPER) {
            @Override
            Type solve(UndetVar uv, InferenceContext inferenceContext) {
                Infer infer = inferenceContext.infer;
                List<Type> hibounds = filterBounds(uv, inferenceContext);
                //note: hibounds should have at least one element
                Type owntype = hibounds.tail.tail == null  ? hibounds.head : infer.types.glb(hibounds);
                if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
                    throw infer.inferenceException
                        .setMessage("no.unique.maximal.instance.exists",
                                    uv.qtype, hibounds);
                } else {
                    return owntype;
                }
            }
        },
        /**
         * Like the former; the only difference is that this step can only be applied
         * if all upper bounds are ground.
         */
        UPPER_LEGACY(InferenceBound.UPPER) {
            @Override
            public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
                return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured();
            }

            @Override
            Type solve(UndetVar uv, InferenceContext inferenceContext) {
                return UPPER.solve(uv, inferenceContext);
            }
        },
        /**
         * Like the former; the only difference is that this step can only be applied
         * if all upper/lower bounds are ground.
         */
        CAPTURED(InferenceBound.UPPER) {
            @Override
            public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
                return t.isCaptured() &&
                        !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER));
            }

            @Override
            Type solve(UndetVar uv, InferenceContext inferenceContext) {
                Infer infer = inferenceContext.infer;
                Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ?
                        UPPER.solve(uv, inferenceContext) :
                        infer.syms.objectType;
                Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ?
                        LOWER.solve(uv, inferenceContext) :
                        infer.syms.botType;
                CapturedType prevCaptured = (CapturedType)uv.qtype;
                return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner,
                                        upper, lower, prevCaptured.wildcard);
            }
        };

        final InferenceBound ib;

        InferenceStep(InferenceBound ib) {
            this.ib = ib;
        }

        /**
         * Find an instantiated type for a given inference variable within
         * a given inference context
         */
        abstract Type solve(UndetVar uv, InferenceContext inferenceContext);

        /**
         * Can the inference variable be instantiated using this step?
         */
        public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
            return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured();
        }

        /**
         * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)
         */
        List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) {
            return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));
        }
    }

    /**
     * This enumeration defines the sequence of steps to be applied when the
     * solver works in legacy mode. The steps in this enumeration reflect
     * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
     */
    enum LegacyInferenceSteps {

        EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
        EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));

        final EnumSet<InferenceStep> steps;

        LegacyInferenceSteps(EnumSet<InferenceStep> steps) {
            this.steps = steps;
        }
    }

    /**
     * This enumeration defines the sequence of steps to be applied when the
     * graph solver is used. This order is defined so as to maximize compatibility
     * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
     */
    enum GraphInferenceSteps {

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

        final EnumSet<InferenceStep> steps;

        GraphInferenceSteps(EnumSet<InferenceStep> steps) {
            this.steps = steps;
        }
    }

    /**
     * There are two kinds of dependencies between inference variables. The basic
     * kind of dependency (or bound dependency) arises when a variable mention
     * another variable in one of its bounds. There's also a more subtle kind
     * of dependency that arises when a variable 'might' lead to better constraints
     * on another variable (this is typically the case with variables holding up
     * stuck expressions).
     */
    enum DependencyKind implements GraphUtils.DependencyKind {

        /** bound dependency */
        BOUND("dotted"),
        /** stuck dependency */
        STUCK("dashed");

        final String dotSyle;

        private DependencyKind(String dotSyle) {
            this.dotSyle = dotSyle;
        }
    }

    /**
     * This is the graph inference solver - the solver organizes all inference variables in
     * a given inference context by bound dependencies - in the general case, such dependencies
     * would lead to a cyclic directed graph (hence the name); the dependency info is used to build
     * an acyclic graph, where all cyclic variables are bundled together. An inference
     * step corresponds to solving a node in the acyclic graph - this is done by
     * relying on a given strategy (see GraphStrategy).
     */
    class GraphSolver {

        InferenceContext inferenceContext;
        Map<Type, Set<Type>> stuckDeps;
        Warner warn;

        GraphSolver(InferenceContext inferenceContext, Map<Type, Set<Type>> stuckDeps, Warner warn) {
            this.inferenceContext = inferenceContext;
            this.stuckDeps = stuckDeps;
            this.warn = warn;
        }

        /**
         * Solve variables in a given inference context. The amount of variables
         * to be solved, and the way in which the underlying acyclic graph is explored
         * depends on the selected solver strategy.
         */
        void solve(GraphStrategy sstrategy) {
            doIncorporation(inferenceContext, warn); //initial propagation of bounds
            InferenceGraph inferenceGraph = new InferenceGraph(stuckDeps);
            while (!sstrategy.done()) {
                if (dependenciesFolder != null) {
                    //add this graph to the pending queue
                    pendingGraphs = pendingGraphs.prepend(inferenceGraph.toDot());
                }
                InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);
                List<Type> varsToSolve = List.from(nodeToSolve.data);
                List<Type> saved_undet = inferenceContext.save();
                try {
                    //repeat until all variables are solved
                    outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {
                        //for each inference phase
                        for (GraphInferenceSteps step : GraphInferenceSteps.values()) {
                            if (inferenceContext.solveBasic(varsToSolve, step.steps).nonEmpty()) {
                                doIncorporation(inferenceContext, warn);
                                continue outer;
                            }
                        }
                        //no progress
                        throw inferenceException.setMessage();
                    }
                }
                catch (InferenceException ex) {
                    //did we fail because of interdependent ivars?
                    inferenceContext.rollback(saved_undet);
                    instantiateAsUninferredVars(varsToSolve, inferenceContext);
                    doIncorporation(inferenceContext, warn);
                }
                inferenceGraph.deleteNode(nodeToSolve);
            }
        }

        /**
         * The dependencies between the inference variables that need to be solved
         * form a (possibly cyclic) graph. This class reduces the original dependency graph
         * to an acyclic version, where cyclic nodes are folded into a single 'super node'.
         */
        class InferenceGraph {

            /**
             * This class represents a node in the graph. Each node corresponds
             * to an inference variable and has edges (dependencies) on other
             * nodes. The node defines an entry point that can be used to receive
             * updates on the structure of the graph this node belongs to (used to
             * keep dependencies in sync).
             */
            class Node extends GraphUtils.TarjanNode<ListBuffer<Type>, Node> implements DottableNode<ListBuffer<Type>, Node> {

                /** map listing all dependencies (grouped by kind) */
                EnumMap<DependencyKind, Set<Node>> deps;

                Node(Type ivar) {
                    super(ListBuffer.of(ivar));
                    this.deps = new EnumMap<>(DependencyKind.class);
                }

                @Override
                public GraphUtils.DependencyKind[] getSupportedDependencyKinds() {
                    return DependencyKind.values();
                }

                public Iterable<? extends Node> getAllDependencies() {
                    return getDependencies(DependencyKind.values());
                }

                @Override
                public Collection<? extends Node> getDependenciesByKind(GraphUtils.DependencyKind dk) {
                    return getDependencies((DependencyKind)dk);
                }

                /**
                 * Retrieves all dependencies with given kind(s).
                 */
                protected Set<Node> getDependencies(DependencyKind... depKinds) {
                    Set<Node> buf = new LinkedHashSet<>();
                    for (DependencyKind dk : depKinds) {
                        Set<Node> depsByKind = deps.get(dk);
                        if (depsByKind != null) {
                            buf.addAll(depsByKind);
                        }
                    }
                    return buf;
                }

                /**
                 * Adds dependency with given kind.
                 */
                protected void addDependency(DependencyKind dk, Node depToAdd) {
                    Set<Node> depsByKind = deps.get(dk);
                    if (depsByKind == null) {
                        depsByKind = new LinkedHashSet<>();
                        deps.put(dk, depsByKind);
                    }
                    depsByKind.add(depToAdd);
                }

                /**
                 * Add multiple dependencies of same given kind.
                 */
                protected void addDependencies(DependencyKind dk, Set<Node> depsToAdd) {
                    for (Node n : depsToAdd) {
                        addDependency(dk, n);
                    }
                }

                /**
                 * Remove a dependency, regardless of its kind.
                 */
                protected Set<DependencyKind> removeDependency(Node n) {
                    Set<DependencyKind> removedKinds = new HashSet<>();
                    for (DependencyKind dk : DependencyKind.values()) {
                        Set<Node> depsByKind = deps.get(dk);
                        if (depsByKind == null) continue;
                        if (depsByKind.remove(n)) {
                            removedKinds.add(dk);
                        }
                    }
                    return removedKinds;
                }

                /**
                 * Compute closure of a give node, by recursively walking
                 * through all its dependencies (of given kinds)
                 */
                protected Set<Node> closure(DependencyKind... depKinds) {
                    boolean progress = true;
                    Set<Node> closure = new HashSet<>();
                    closure.add(this);
                    while (progress) {
                        progress = false;
                        for (Node n1 : new HashSet<>(closure)) {
                            progress = closure.addAll(n1.getDependencies(depKinds));
                        }
                    }
                    return closure;
                }

                /**
                 * Is this node a leaf? This means either the node has no dependencies,
                 * or it just has self-dependencies.
                 */
                protected boolean isLeaf() {
                    //no deps, or only one self dep
                    Set<Node> allDeps = getDependencies(DependencyKind.BOUND, DependencyKind.STUCK);
                    if (allDeps.isEmpty()) return true;
                    for (Node n : allDeps) {
                        if (n != this) {
                            return false;
                        }
                    }
                    return true;
                }

                /**
                 * Merge this node with another node, acquiring its dependencies.
                 * This routine is used to merge all cyclic node together and
                 * form an acyclic graph.
                 */
                protected void mergeWith(List<? extends Node> nodes) {
                    for (Node n : nodes) {
                        Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");
                        data.appendList(n.data);
                        for (DependencyKind dk : DependencyKind.values()) {
                            addDependencies(dk, n.getDependencies(dk));
                        }
                    }
                    //update deps
                    EnumMap<DependencyKind, Set<Node>> deps2 = new EnumMap<>(DependencyKind.class);
                    for (DependencyKind dk : DependencyKind.values()) {
                        for (Node d : getDependencies(dk)) {
                            Set<Node> depsByKind = deps2.get(dk);
                            if (depsByKind == null) {
                                depsByKind = new LinkedHashSet<>();
                                deps2.put(dk, depsByKind);
                            }
                            if (data.contains(d.data.first())) {
                                depsByKind.add(this);
                            } else {
                                depsByKind.add(d);
                            }
                        }
                    }
                    deps = deps2;
                }

                /**
                 * Notify all nodes that something has changed in the graph
                 * topology.
                 */
                private void graphChanged(Node from, Node to) {
                    for (DependencyKind dk : removeDependency(from)) {
                        if (to != null) {
                            addDependency(dk, to);
                        }
                    }
                }

                @Override
                public Properties nodeAttributes() {
                    Properties p = new Properties();
                    p.put("label", "\"" + toString() + "\"");
                    return p;
                }

                @Override
                public Properties dependencyAttributes(Node sink, GraphUtils.DependencyKind dk) {
                    Properties p = new Properties();
                    p.put("style", ((DependencyKind)dk).dotSyle);
                    if (dk == DependencyKind.STUCK) return p;
                    else {
                        StringBuilder buf = new StringBuilder();
                        String sep = "";
                        for (Type from : data) {
                            UndetVar uv = (UndetVar)inferenceContext.asUndetVar(from);
                            for (Type bound : uv.getBounds(InferenceBound.values())) {
                                if (bound.containsAny(List.from(sink.data))) {
                                    buf.append(sep);
                                    buf.append(bound);
                                    sep = ",";
                                }
                            }
                        }
                        p.put("label", "\"" + buf.toString() + "\"");
                    }
                    return p;
                }
            }

            /** the nodes in the inference graph */
            ArrayList<Node> nodes;

            InferenceGraph(Map<Type, Set<Type>> optDeps) {
                initNodes(optDeps);
            }

            /**
             * Basic lookup helper for retrieving a graph node given an inference
             * variable type.
             */
            public Node findNode(Type t) {
                for (Node n : nodes) {
                    if (n.data.contains(t)) {
                        return n;
                    }
                }
                return null;
            }

            /**
             * Delete a node from the graph. This update the underlying structure
             * of the graph (including dependencies) via listeners updates.
             */
            public void deleteNode(Node n) {
                Assert.check(nodes.contains(n));
                nodes.remove(n);
                notifyUpdate(n, null);
            }

            /**
             * Notify all nodes of a change in the graph. If the target node is
             * {@code null} the source node is assumed to be removed.
             */
            void notifyUpdate(Node from, Node to) {
                for (Node n : nodes) {
                    n.graphChanged(from, to);
                }
            }

            /**
             * Create the graph nodes. First a simple node is created for every inference
             * variables to be solved. Then Tarjan is used to found all connected components
             * in the graph. For each component containing more than one node, a super node is
             * created, effectively replacing the original cyclic nodes.
             */
            void initNodes(Map<Type, Set<Type>> stuckDeps) {
                //add nodes
                nodes = new ArrayList<>();
                for (Type t : inferenceContext.restvars()) {
                    nodes.add(new Node(t));
                }
                //add dependencies
                for (Node n_i : nodes) {
                    Type i = n_i.data.first();
                    Set<Type> optDepsByNode = stuckDeps.get(i);
                    for (Node n_j : nodes) {
                        Type j = n_j.data.first();
                        UndetVar uv_i = (UndetVar)inferenceContext.asUndetVar(i);
                        if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {
                            //update i's bound dependencies
                            n_i.addDependency(DependencyKind.BOUND, n_j);
                        }
                        if (optDepsByNode != null && optDepsByNode.contains(j)) {
                            //update i's stuck dependencies
                            n_i.addDependency(DependencyKind.STUCK, n_j);
                        }
                    }
                }
                //merge cyclic nodes
                ArrayList<Node> acyclicNodes = new ArrayList<>();
                for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {
                    if (conSubGraph.length() > 1) {
                        Node root = conSubGraph.head;
                        root.mergeWith(conSubGraph.tail);
                        for (Node n : conSubGraph) {
                            notifyUpdate(n, root);
                        }
                    }
                    acyclicNodes.add(conSubGraph.head);
                }
                nodes = acyclicNodes;
            }

            /**
             * Debugging: dot representation of this graph
             */
            String toDot() {
                StringBuilder buf = new StringBuilder();
                for (Type t : inferenceContext.undetvars) {
                    UndetVar uv = (UndetVar)t;
                    buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",
                            uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),
                            uv.getBounds(InferenceBound.EQ)));
                }
                return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());
            }
        }
    }
    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="Inference context">
    /**
     * Functional interface for defining inference callbacks. Certain actions
     * (i.e. subtyping checks) might need to be redone after all inference variables
     * have been fixed.
     */
    interface FreeTypeListener {
        void typesInferred(InferenceContext inferenceContext);
    }

    final InferenceContext emptyContext;
    // </editor-fold>
}