/*

 * Copyright (c) 2010, 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 jdk.nashorn.internal.runtime;

import static jdk.nashorn.internal.lookup.Lookup.MH;

import static jdk.nashorn.internal.runtime.UnwarrantedOptimismException.INVALID_PROGRAM_POINT;

import static jdk.nashorn.internal.runtime.UnwarrantedOptimismException.isValid;

import java.lang.invoke.CallSite;

import java.lang.invoke.MethodHandle;

import java.lang.invoke.MethodHandles;

import java.lang.invoke.MethodType;

import java.lang.invoke.MutableCallSite;

import java.lang.invoke.SwitchPoint;

import java.util.Collection;

import java.util.Collections;

import java.util.Iterator;

import java.util.Map;

import java.util.TreeMap;

import java.util.function.Supplier;

import java.util.logging.Level;

import jdk.internal.dynalink.linker.GuardedInvocation;

import jdk.nashorn.internal.codegen.Compiler;

import jdk.nashorn.internal.codegen.Compiler.CompilationPhases;

import jdk.nashorn.internal.codegen.TypeMap;

import jdk.nashorn.internal.codegen.types.ArrayType;

import jdk.nashorn.internal.codegen.types.Type;

import jdk.nashorn.internal.ir.FunctionNode;

import jdk.nashorn.internal.objects.annotations.SpecializedFunction.LinkLogic;

import jdk.nashorn.internal.runtime.events.RecompilationEvent;

import jdk.nashorn.internal.runtime.linker.Bootstrap;

import jdk.nashorn.internal.runtime.logging.DebugLogger;

/**

 * An version of a JavaScript function, native or JavaScript.

 * Supports lazily generating a constructor version of the invocation.

 */

final class CompiledFunction {

    private static final MethodHandle NEWFILTER = findOwnMH("newFilter", Object.class, Object.class, Object.class);

    private static final MethodHandle RELINK_COMPOSABLE_INVOKER = findOwnMH("relinkComposableInvoker", void.class, CallSite.class, CompiledFunction.class, boolean.class);

    private static final MethodHandle HANDLE_REWRITE_EXCEPTION = findOwnMH("handleRewriteException", MethodHandle.class, CompiledFunction.class, OptimismInfo.class, RewriteException.class);

    private static final MethodHandle RESTOF_INVOKER = MethodHandles.exactInvoker(MethodType.methodType(Object.class, RewriteException.class));

    private final DebugLogger log;

    static final Collection<CompiledFunction> NO_FUNCTIONS = Collections.emptySet();

    /**

     * The method type may be more specific than the invoker, if. e.g.

     * the invoker is guarded, and a guard with a generic object only

     * fallback, while the target is more specific, we still need the

     * more specific type for sorting

     */

    private MethodHandle invoker;

    private MethodHandle constructor;

    private OptimismInfo optimismInfo;

    private final int flags; // from FunctionNode

    private final MethodType callSiteType;

    private final Specialization specialization;

    CompiledFunction(final MethodHandle invoker) {

        this(invoker, null, null);

    }

    static CompiledFunction createBuiltInConstructor(final MethodHandle invoker, final Specialization specialization) {

        return new CompiledFunction(MH.insertArguments(invoker, 0, false), createConstructorFromInvoker(MH.insertArguments(invoker, 0, true)), specialization);

    }

    CompiledFunction(final MethodHandle invoker, final MethodHandle constructor, final Specialization specialization) {

        this(invoker, constructor, 0, null, specialization, DebugLogger.DISABLED_LOGGER);

    }

    CompiledFunction(final MethodHandle invoker, final MethodHandle constructor, final int flags, final MethodType callSiteType, final Specialization specialization, final DebugLogger log) {

        this.specialization = specialization;

        if (specialization != null && specialization.isOptimistic()) {

            /*

             * An optimistic builtin with isOptimistic=true works like any optimistic generated function, i.e. it

             * can throw unwarranted optimism exceptions. As native functions trivially can't have parts of them

             * regenerated as restof methods, this only works if the methods are atomic/functional in their behavior

             * and doesn't modify state before an UOE can be thrown. If they aren't, we can reexecute a wider version

             * of the same builtin in a recompilation handler for FinalScriptFunctionData. There are several

             * candidate methods in Native* that would benefit from this, but I haven't had time to implement any

             * of them currently. In order to fit in with the relinking framework, the current thinking is

             * that the methods still take a program point to fit in with other optimistic functions, but

             * it is set to "first", which is the beginning of the method. The relinker can tell the difference

             * between builtin and JavaScript functions. This might change. TODO

             */

            this.invoker = MH.insertArguments(invoker, invoker.type().parameterCount() - 1, UnwarrantedOptimismException.FIRST_PROGRAM_POINT);

            throw new AssertionError("Optimistic (UnwarrantedOptimismException throwing) builtin functions are currently not in use");

        }

        this.constructor = constructor;

        this.flags = flags;

        this.callSiteType = callSiteType;

        this.log = log;

    }

    CompiledFunction(final MethodHandle invoker, final RecompilableScriptFunctionData functionData,

            final Map<Integer, Type> invalidatedProgramPoints, final MethodType callSiteType, final int flags) {

        this(invoker, null, flags, callSiteType, null, functionData.getLogger());

        if ((flags & FunctionNode.IS_DEOPTIMIZABLE) != 0) {

            optimismInfo = new OptimismInfo(functionData, invalidatedProgramPoints);

        } else {

            optimismInfo = null;

        }

    }

    static CompiledFunction createBuiltInConstructor(final MethodHandle invoker) {

        return new CompiledFunction(MH.insertArguments(invoker, 0, false), createConstructorFromInvoker(MH.insertArguments(invoker, 0, true)), null);

    }

    boolean isSpecialization() {

        return specialization != null;

    }

    boolean hasLinkLogic() {

        return getLinkLogicClass() != null;

    }

    Class<? extends LinkLogic> getLinkLogicClass() {

        if (isSpecialization()) {

            final Class<? extends LinkLogic> linkLogicClass = specialization.getLinkLogicClass();

            assert !LinkLogic.isEmpty(linkLogicClass) : "empty link logic classes should have been removed by nasgen";

            return linkLogicClass;

        }

        return null;

    }

    int getFlags() {

        return flags;

    }

    /**

     * An optimistic specialization is one that can throw UnwarrantedOptimismException.

     * This is allowed for native methods, as long as they are functional, i.e. don't change

     * any state between entering and throwing the UOE. Then we can re-execute a wider version

     * of the method in the continuation. Rest-of method generation for optimistic builtins is

     * of course not possible, but this approach works and fits into the same relinking

     * framework

     *

     * @return true if optimistic builtin

     */

    boolean isOptimistic() {

        return isSpecialization() ? specialization.isOptimistic() : false;

    }

    boolean isApplyToCall() {

        return (flags & FunctionNode.HAS_APPLY_TO_CALL_SPECIALIZATION) != 0;

    }

    boolean isVarArg() {

        return isVarArgsType(invoker.type());

    }

    @Override

    public String toString() {

        final StringBuilder sb = new StringBuilder();

        final Class<? extends LinkLogic> linkLogicClass = getLinkLogicClass();

        sb.append("[invokerType=").

            append(invoker.type()).

            append(" ctor=").

            append(constructor).

            append(" weight=").

            append(weight()).

            append(" linkLogic=").

            append(linkLogicClass != null ? linkLogicClass.getSimpleName() : "none");

        return sb.toString();

    }

    boolean needsCallee() {

        return ScriptFunctionData.needsCallee(invoker);

    }

    /**

     * Returns an invoker method handle for this function. Note that the handle is safely composable in

     * the sense that you can compose it with other handles using any combinators even if you can't affect call site

     * invalidation. If this compiled function is non-optimistic, then it returns the same value as

     * {@link #getInvokerOrConstructor(boolean)}. However, if the function is optimistic, then this handle will

     * incur an overhead as it will add an intermediate internal call site that can relink itself when the function

     * needs to regenerate its code to always point at the latest generated code version.

     * @return a guaranteed composable invoker method handle for this function.

     */

    MethodHandle createComposableInvoker() {

        return createComposableInvoker(false);

    }

    /**

     * Returns an invoker method handle for this function when invoked as a constructor. Note that the handle should be

     * considered non-composable in the sense that you can only compose it with other handles using any combinators if

     * you can ensure that the composition is guarded by {@link #getOptimisticAssumptionsSwitchPoint()} if it's

     * non-null, and that you can relink the call site it is set into as a target if the switch point is invalidated. In

     * all other cases, use {@link #createComposableConstructor()}.

     * @return a direct constructor method handle for this function.

     */

    private MethodHandle getConstructor() {

        if (constructor == null) {

            constructor = createConstructorFromInvoker(createInvokerForPessimisticCaller());

        }

        return constructor;

    }

    /**

     * Creates a version of the invoker intended for a pessimistic caller (return type is Object, no caller optimistic

     * program point available).

     * @return a version of the invoker intended for a pessimistic caller.

     */

    private MethodHandle createInvokerForPessimisticCaller() {

        return createInvoker(Object.class, INVALID_PROGRAM_POINT);

    }

    /**

     * Compose a constructor from an invoker.

     *

     * @param invoker         invoker

     * @return the composed constructor

     */

    private static MethodHandle createConstructorFromInvoker(final MethodHandle invoker) {

        final boolean needsCallee = ScriptFunctionData.needsCallee(invoker);

        // If it was (callee, this, args...), permute it to (this, callee, args...). We're doing this because having

        // "this" in the first argument position is what allows the elegant folded composition of

        // (newFilter x constructor x allocator) further down below in the code. Also, ensure the composite constructor

        // always returns Object.

        final MethodHandle swapped = needsCallee ? swapCalleeAndThis(invoker) : invoker;

        final MethodHandle returnsObject = MH.asType(swapped, swapped.type().changeReturnType(Object.class));

        final MethodType ctorType = returnsObject.type();

        // Construct a dropping type list for NEWFILTER, but don't include constructor "this" into it, so it's actually

        // captured as "allocation" parameter of NEWFILTER after we fold the constructor into it.

        // (this, [callee, ]args...) => ([callee, ]args...)

        final Class<?>[] ctorArgs = ctorType.dropParameterTypes(0, 1).parameterArray();

        // Fold constructor into newFilter that replaces the return value from the constructor with the originally

        // allocated value when the originally allocated value is a JS primitive (String, Boolean, Number).

        // (result, this, [callee, ]args...) x (this, [callee, ]args...) => (this, [callee, ]args...)

        final MethodHandle filtered = MH.foldArguments(MH.dropArguments(NEWFILTER, 2, ctorArgs), returnsObject);

        // allocate() takes a ScriptFunction and returns a newly allocated ScriptObject...

        if (needsCallee) {

            // ...we either fold it into the previous composition, if we need both the ScriptFunction callee object and

            // the newly allocated object in the arguments, so (this, callee, args...) x (callee) => (callee, args...),

            // or...

            return MH.foldArguments(filtered, ScriptFunction.ALLOCATE);

        }

        // ...replace the ScriptFunction argument with the newly allocated object, if it doesn't need the callee

        // (this, args...) filter (callee) => (callee, args...)

        return MH.filterArguments(filtered, 0, ScriptFunction.ALLOCATE);

    }

    /**

     * Permutes the parameters in the method handle from {@code (callee, this, ...)} to {@code (this, callee, ...)}.

     * Used when creating a constructor handle.

     * @param mh a method handle with order of arguments {@code (callee, this, ...)}

     * @return a method handle with order of arguments {@code (this, callee, ...)}

     */

    private static MethodHandle swapCalleeAndThis(final MethodHandle mh) {

        final MethodType type = mh.type();

        assert type.parameterType(0) == ScriptFunction.class : type;

        assert type.parameterType(1) == Object.class : type;

        final MethodType newType = type.changeParameterType(0, Object.class).changeParameterType(1, ScriptFunction.class);

        final int[] reorder = new int[type.parameterCount()];

        reorder[0] = 1;

        assert reorder[1] == 0;

        for (int i = 2; i < reorder.length; ++i) {

            reorder[i] = i;

        }

        return MethodHandles.permuteArguments(mh, newType, reorder);

    }

    /**

     * Returns an invoker method handle for this function when invoked as a constructor. Note that the handle is safely

     * composable in the sense that you can compose it with other handles using any combinators even if you can't affect

     * call site invalidation. If this compiled function is non-optimistic, then it returns the same value as

     * {@link #getConstructor()}. However, if the function is optimistic, then this handle will incur an overhead as it

     * will add an intermediate internal call site that can relink itself when the function needs to regenerate its code

     * to always point at the latest generated code version.

     * @return a guaranteed composable constructor method handle for this function.

     */

    MethodHandle createComposableConstructor() {

        return createComposableInvoker(true);

    }

    boolean hasConstructor() {

        return constructor != null;

    }

    MethodType type() {

        return invoker.type();

    }

    int weight() {

        return weight(type());

    }

    private static int weight(final MethodType type) {

        if (isVarArgsType(type)) {

            return Integer.MAX_VALUE; //if there is a varargs it should be the heavist and last fallback

        }

        int weight = Type.typeFor(type.returnType()).getWeight();

        for (int i = 0 ; i < type.parameterCount() ; i++) {

            final Class<?> paramType = type.parameterType(i);

            final int pweight = Type.typeFor(paramType).getWeight() * 2; //params are more important than call types as return values are always specialized

            weight += pweight;

        }

        weight += type.parameterCount(); //more params outweigh few parameters

        return weight;

    }

    static boolean isVarArgsType(final MethodType type) {

        assert type.parameterCount() >= 1 : type;

        return type.parameterType(type.parameterCount() - 1) == Object[].class;

    }

    static boolean moreGenericThan(final MethodType mt0, final MethodType mt1) {

        return weight(mt0) > weight(mt1);

    }

    boolean betterThanFinal(final CompiledFunction other, final MethodType callSiteMethodType) {

        // Prefer anything over nothing, as we can't compile new versions.

        if (other == null) {

            return true;

        }

        return betterThanFinal(this, other, callSiteMethodType);

    }

    private static boolean betterThanFinal(final CompiledFunction cf, final CompiledFunction other, final MethodType callSiteMethodType) {

        final MethodType thisMethodType  = cf.type();

        final MethodType otherMethodType = other.type();

        final int thisParamCount = getParamCount(thisMethodType);

        final int otherParamCount = getParamCount(otherMethodType);

        final int callSiteRawParamCount = getParamCount(callSiteMethodType);

        final boolean csVarArg = callSiteRawParamCount == Integer.MAX_VALUE;

        // Subtract 1 for callee for non-vararg call sites

        final int callSiteParamCount = csVarArg ? callSiteRawParamCount : callSiteRawParamCount - 1;

        // Prefer the function that discards less parameters

        final int thisDiscardsParams = Math.max(callSiteParamCount - thisParamCount, 0);

        final int otherDiscardsParams = Math.max(callSiteParamCount - otherParamCount, 0);

        if(thisDiscardsParams < otherDiscardsParams) {

            return true;

        }

        if(thisDiscardsParams > otherDiscardsParams) {

            return false;

        }

        final boolean thisVarArg = thisParamCount == Integer.MAX_VALUE;

        final boolean otherVarArg = otherParamCount == Integer.MAX_VALUE;

        if(!(thisVarArg && otherVarArg && csVarArg)) {

            // At least one of them isn't vararg

            final Type[] thisType = toTypeWithoutCallee(thisMethodType, 0); // Never has callee

            final Type[] otherType = toTypeWithoutCallee(otherMethodType, 0); // Never has callee

            final Type[] callSiteType = toTypeWithoutCallee(callSiteMethodType, 1); // Always has callee

            int narrowWeightDelta = 0;

            int widenWeightDelta = 0;

            final int minParamsCount = Math.min(Math.min(thisParamCount, otherParamCount), callSiteParamCount);

            for(int i = 0; i < minParamsCount; ++i) {

                final int callSiteParamWeight = getParamType(i, callSiteType, csVarArg).getWeight();

                // Delta is negative for narrowing, positive for widening

                final int thisParamWeightDelta = getParamType(i, thisType, thisVarArg).getWeight() - callSiteParamWeight;

                final int otherParamWeightDelta = getParamType(i, otherType, otherVarArg).getWeight() - callSiteParamWeight;

                // Only count absolute values of narrowings

                narrowWeightDelta += Math.max(-thisParamWeightDelta, 0) - Math.max(-otherParamWeightDelta, 0);

                // Only count absolute values of widenings

                widenWeightDelta += Math.max(thisParamWeightDelta, 0) - Math.max(otherParamWeightDelta, 0);

            }

            // If both functions accept more arguments than what is passed at the call site, account for ability

            // to receive Undefined un-narrowed in the remaining arguments.

            if(!thisVarArg) {

                for(int i = callSiteParamCount; i < thisParamCount; ++i) {

                    narrowWeightDelta += Math.max(Type.OBJECT.getWeight() - thisType[i].getWeight(), 0);

                }

            }

            if(!otherVarArg) {

                for(int i = callSiteParamCount; i < otherParamCount; ++i) {

                    narrowWeightDelta -= Math.max(Type.OBJECT.getWeight() - otherType[i].getWeight(), 0);

                }

            }

            // Prefer function that narrows less

            if(narrowWeightDelta < 0) {

                return true;

            }

            if(narrowWeightDelta > 0) {

                return false;

            }

            // Prefer function that widens less

            if(widenWeightDelta < 0) {

                return true;

            }

            if(widenWeightDelta > 0) {

                return false;

            }

        }

        // Prefer the function that exactly matches the arity of the call site.

        if(thisParamCount == callSiteParamCount && otherParamCount != callSiteParamCount) {

            return true;

        }

        if(thisParamCount != callSiteParamCount && otherParamCount == callSiteParamCount) {

            return false;

        }

        // Otherwise, neither function matches arity exactly. We also know that at this point, they both can receive

        // more arguments than call site, otherwise we would've already chosen the one that discards less parameters.

        // Note that variable arity methods are preferred, as they actually match the call site arity better, since they

        // really have arbitrary arity.

        if(thisVarArg) {

            if(!otherVarArg) {

                return true; //

            }

        } else if(otherVarArg) {

            return false;

        }

        // Neither is variable arity; chose the one that has less extra parameters.

        final int fnParamDelta = thisParamCount - otherParamCount;

        if(fnParamDelta < 0) {

            return true;

        }

        if(fnParamDelta > 0) {

            return false;

        }

        final int callSiteRetWeight = Type.typeFor(callSiteMethodType.returnType()).getWeight();

        // Delta is negative for narrower return type, positive for wider return type

        final int thisRetWeightDelta = Type.typeFor(thisMethodType.returnType()).getWeight() - callSiteRetWeight;

        final int otherRetWeightDelta = Type.typeFor(otherMethodType.returnType()).getWeight() - callSiteRetWeight;

        // Prefer function that returns a less wide return type

        final int widenRetDelta = Math.max(thisRetWeightDelta, 0) - Math.max(otherRetWeightDelta, 0);

        if(widenRetDelta < 0) {

            return true;

        }

        if(widenRetDelta > 0) {

            return false;

        }

        // Prefer function that returns a less narrow return type

        final int narrowRetDelta = Math.max(-thisRetWeightDelta, 0) - Math.max(-otherRetWeightDelta, 0);

        if(narrowRetDelta < 0) {

            return true;

        }

        if(narrowRetDelta > 0) {

            return false;

        }

        //if they are equal, pick the specialized one first

        if (cf.isSpecialization() != other.isSpecialization()) {

            return cf.isSpecialization(); //always pick the specialized version if we can

        }

        if (cf.isSpecialization() && other.isSpecialization()) {

            return cf.getLinkLogicClass() != null; //pick link logic specialization above generic specializations

        }

        // Signatures are identical

        throw new AssertionError(thisMethodType + " identically applicable to " + otherMethodType + " for " + callSiteMethodType);

    }

    private static Type[] toTypeWithoutCallee(final MethodType type, final int thisIndex) {