/*

 * Copyright (c) 1999, 2013, 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.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.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.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 com.sun.tools.javac.util.GraphUtils.TarjanNode;

import java.util.ArrayList;

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.Set;

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 {

    Resolve rs;

    Check chk;

    Symtab syms;

    Types types;

    JCDiagnostic.Factory diags;

    Log log;

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

    boolean allowGraphInference;

    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");

    }

    /** 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.

     */

    public Type instantiateMethod(Env<AttrContext> env,

                                  List<Type> tvars,

                                  MethodType mt,

                                  Attr.ResultInfo resultInfo,

                                  Symbol 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(tvars);

        inferenceException.clear();

        try {

            DeferredAttr.DeferredAttrContext deferredAttrContext =

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

            resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext,

                    argtypes, mt.getParameterTypes(), warn);

            if (allowGraphInference &&

                    resultInfo != null &&

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

                //inject return constraints earlier

                checkWithinBounds(inferenceContext, warn); //propagation

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

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

                //propagate outwards if needed

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

                    //propagate inference context outwards and exit

                    inferenceContext.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(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());

            }

        }

    }

    /**

     * 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(Attr.ResultInfo resultInfo,

            MethodType mt, InferenceContext inferenceContext) {

        Type from = mt.getReturnType();

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

                resultInfo.checkContext.inferenceContext() != 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 qtype1 = inferenceContext.asFree(from);

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

        Assert.check(allowGraphInference || !resultInfo.checkContext.inferenceContext().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(qtype1, resultInfo.checkContext.inferenceContext().asFree(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;

    }

    Type returnConstraintTarget(Type from, Type to) {

        if (from.hasTag(VOID)) {

            return syms.voidType;

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

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

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

            if (!allowGraphInference) {

                //if legacy, just return boxed type

                return types.boxedClass(to).type;

            }

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

            UndetVar uv = (UndetVar)from;

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

                Type boundAsPrimitive = types.unboxedType(t);

                if (boundAsPrimitive == null) continue;

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

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

                    return syms.objectType;

                }

            }

            return types.boxedClass(to).type;

        } else {

            return to;

        }

    }

    /**

      * Infer cyclic inference variables as described in 15.12.2.8.

      */

    private 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.asFree(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.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null);

                todo.append(uv);

                uv.inst = fresh_tvar.type;

            } else if (upperBounds.nonEmpty()) {

                uv.inst = types.glb(upperBounds);

            } else {

                uv.inst = 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.inst;

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

            if (ct.bound.isErroneous()) {

                //report inference error if glb fails

                reportBoundError(uv, BoundErrorKind.BAD_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 = Type.map(argtypes, 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);

            }

            public Type apply(Type t) {

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

                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;

            }

        }

    /**

      * 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(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.asFree(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.inst == null) {

                    uv.inst = 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));

            }

            return owntype;

        }

    }

    // </editor-fold>

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

    /**

     * Check bounds and perform incorporation

     */

    void checkWithinBounds(InferenceContext inferenceContext,

                             Warner warn) throws InferenceException {

        MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars);

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

        try {

            while (true) {

                mlistener.reset();

                if (!allowGraphInference) {

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

                    //cannot be run in parallel with other incoprporation rounds

                    for (Type t : inferenceContext.undetvars) {

                        UndetVar uv = (UndetVar)t;

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

                    }

                }

                for (Type t : inferenceContext.undetvars) {

                    UndetVar uv = (UndetVar)t;

                    //bound incorporation

                    EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?

                            incorporationStepsGraph : incorporationStepsLegacy;

                    for (IncorporationStep is : incorporationSteps) {

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

                            is.apply(uv, inferenceContext, warn);

                        }

                    }

                }

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

            }

        }

        finally {

            mlistener.detach();

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

                inferenceContext.rollback(saved_undet);

            }

            incorporationCache.clear();

        }

    }

    //where

        /**

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

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

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

         * left in a clean state.

         */

        class MultiUndetVarListener implements UndetVar.UndetVarListener {

            boolean changed;

            List<Type> undetvars;

            public MultiUndetVarListener(List<Type> undetvars) {

                this.undetvars = undetvars;

                for (Type t : undetvars) {