/*

 * 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.EnumSet;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Optional;

import java.util.Properties;

import java.util.Set;

import java.util.function.BiFunction;

import java.util.function.BiPredicate;

import com.sun.tools.javac.main.Option;

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.

     */

    private final 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("debug.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 = shouldPropagate(mt.getReturnType(), resultInfo, inferenceContext);

                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 boolean shouldPropagate(Type restype, Attr.ResultInfo target, InferenceContext inferenceContext) {

            return target.checkContext.inferenceContext() != emptyContext && //enclosing context is a generic method

                        inferenceContext.free(restype) && //return type contains inference vars

                        (!inferenceContext.inferencevars.contains(restype) || //no eager instantiation is required (as per 18.5.2)

                                !needsEagerInstantiation((UndetVar)inferenceContext.asUndetVar(restype), target.pt, inferenceContext));

        }

        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 = shouldPropagate(getReturnType(), resultInfo, inferenceContext);

                    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()) {

                if (needsEagerInstantiation((UndetVar)qtype, to, inferenceContext)) {

                    to = generateReferenceToTargetConstraint(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 boolean needsEagerInstantiation(UndetVar from, Type to, 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 true;

                }

            }

            /* 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 true;

                    }

                }

            }

        }

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