/*

 * Copyright (c) 2015, 2019, 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 java.lang.invoke;

import jdk.internal.misc.Unsafe;

import jdk.internal.misc.VM;

import jdk.internal.org.objectweb.asm.ClassWriter;

import jdk.internal.org.objectweb.asm.Label;

import jdk.internal.org.objectweb.asm.MethodVisitor;

import jdk.internal.org.objectweb.asm.Opcodes;

import sun.invoke.util.Wrapper;

import java.lang.invoke.MethodHandles.Lookup;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import java.util.Objects;

import java.util.concurrent.ConcurrentHashMap;

import java.util.concurrent.ConcurrentMap;

import java.util.function.Function;

import static jdk.internal.org.objectweb.asm.Opcodes.*;

/**

 * <p>Methods to facilitate the creation of String concatenation methods, that

 * can be used to efficiently concatenate a known number of arguments of known

 * types, possibly after type adaptation and partial evaluation of arguments.

 * These methods are typically used as <em>bootstrap methods</em> for {@code

 * invokedynamic} call sites, to support the <em>string concatenation</em>

 * feature of the Java Programming Language.

 *

 * <p>Indirect access to the behavior specified by the provided {@code

 * MethodHandle} proceeds in order through two phases:

 *

 * <ol>

 *     <li><em>Linkage</em> occurs when the methods in this class are invoked.

 * They take as arguments a method type describing the concatenated arguments

 * count and types, and optionally the String <em>recipe</em>, plus the

 * constants that participate in the String concatenation. The details on

 * accepted recipe shapes are described further below. Linkage may involve

 * dynamically loading a new class that implements the expected concatenation

 * behavior. The {@code CallSite} holds the {@code MethodHandle} pointing to the

 * exact concatenation method. The concatenation methods may be shared among

 * different {@code CallSite}s, e.g. if linkage methods produce them as pure

 * functions.</li>

 *

 * <li><em>Invocation</em> occurs when a generated concatenation method is

 * invoked with the exact dynamic arguments. This may occur many times for a

 * single concatenation method. The method referenced by the behavior {@code

 * MethodHandle} is invoked with the static arguments and any additional dynamic

 * arguments provided on invocation, as if by {@link MethodHandle#invoke(Object...)}.</li>

 * </ol>

 *

 * <p> This class provides two forms of linkage methods: a simple version

 * ({@link #makeConcat(java.lang.invoke.MethodHandles.Lookup, String,

 * MethodType)}) using only the dynamic arguments, and an advanced version

 * ({@link #makeConcatWithConstants(java.lang.invoke.MethodHandles.Lookup,

 * String, MethodType, String, Object...)} using the advanced forms of capturing

 * the constant arguments. The advanced strategy can produce marginally better

 * invocation bytecode, at the expense of exploding the number of shapes of

 * string concatenation methods present at runtime, because those shapes would

 * include constant static arguments as well.

 *

 * @author Aleksey Shipilev

 * @author Remi Forax

 * @author Peter Levart

 *

 * @apiNote

 * <p>There is a JVM limit (classfile structural constraint): no method

 * can call with more than 255 slots. This limits the number of static and

 * dynamic arguments one can pass to bootstrap method. Since there are potential

 * concatenation strategies that use {@code MethodHandle} combinators, we need

 * to reserve a few empty slots on the parameter lists to capture the

 * temporal results. This is why bootstrap methods in this factory do not accept

 * more than 200 argument slots. Users requiring more than 200 argument slots in

 * concatenation are expected to split the large concatenation in smaller

 * expressions.

 *

 * @since 9

 */

public final class StringConcatFactory {

    /**

     * Tag used to demarcate an ordinary argument.

     */

    private static final char TAG_ARG = '\u0001';

    /**

     * Tag used to demarcate a constant.

     */

    private static final char TAG_CONST = '\u0002';

    /**

     * Maximum number of argument slots in String Concat call.

     *

     * While the maximum number of argument slots that indy call can handle is 253,

     * we do not use all those slots, to let the strategies with MethodHandle

     * combinators to use some arguments.

     */

    private static final int MAX_INDY_CONCAT_ARG_SLOTS = 200;

    /**

     * Concatenation strategy to use. See {@link Strategy} for possible options.

     * This option is controllable with -Djava.lang.invoke.stringConcat JDK option.

     */

    private static Strategy STRATEGY;

    /**

     * Default strategy to use for concatenation.

     */

    private static final Strategy DEFAULT_STRATEGY = Strategy.MH_INLINE_SIZED_EXACT;

    private enum Strategy {

        /**

         * Bytecode generator, calling into {@link java.lang.StringBuilder}.

         */

        BC_SB,

        /**

         * Bytecode generator, calling into {@link java.lang.StringBuilder};

         * but trying to estimate the required storage.

         */

        BC_SB_SIZED,

        /**

         * Bytecode generator, calling into {@link java.lang.StringBuilder};

         * but computing the required storage exactly.

         */

        BC_SB_SIZED_EXACT,

        /**

         * MethodHandle-based generator, that in the end calls into {@link java.lang.StringBuilder}.

         * This strategy also tries to estimate the required storage.

         */

        MH_SB_SIZED,

        /**

         * MethodHandle-based generator, that in the end calls into {@link java.lang.StringBuilder}.

         * This strategy also estimate the required storage exactly.

         */

        MH_SB_SIZED_EXACT,

        /**

         * MethodHandle-based generator, that constructs its own byte[] array from

         * the arguments. It computes the required storage exactly.

         */

        MH_INLINE_SIZED_EXACT

    }

    /**

     * Enables debugging: this may print debugging messages, perform additional (non-neutral for performance)

     * checks, etc.

     */

    private static final boolean DEBUG;

    /**

     * Enables caching of strategy stubs. This may improve the linkage time by reusing the generated

     * code, at the expense of contaminating the profiles.

     */

    private static final boolean CACHE_ENABLE;

    private static final ConcurrentMap<Key, MethodHandle> CACHE;

    /**

     * Dump generated classes to disk, for debugging purposes.

     */

    private static final ProxyClassesDumper DUMPER;

    private static final Class<?> STRING_HELPER;

    static {

        // In case we need to double-back onto the StringConcatFactory during this

        // static initialization, make sure we have the reasonable defaults to complete

        // the static initialization properly. After that, actual users would use

        // the proper values we have read from the properties.

        STRATEGY = DEFAULT_STRATEGY;

        // CACHE_ENABLE = false; // implied

        // CACHE = null;         // implied

        // DEBUG = false;        // implied

        // DUMPER = null;        // implied

        try {

            STRING_HELPER = Class.forName("java.lang.StringConcatHelper");

        } catch (Throwable e) {

            throw new AssertionError(e);

        }

        final String strategy =

                VM.getSavedProperty("java.lang.invoke.stringConcat");

        CACHE_ENABLE = Boolean.parseBoolean(

                VM.getSavedProperty("java.lang.invoke.stringConcat.cache"));

        DEBUG = Boolean.parseBoolean(

                VM.getSavedProperty("java.lang.invoke.stringConcat.debug"));

        final String dumpPath =

                VM.getSavedProperty("java.lang.invoke.stringConcat.dumpClasses");

        STRATEGY = (strategy == null) ? DEFAULT_STRATEGY : Strategy.valueOf(strategy);

        CACHE = CACHE_ENABLE ? new ConcurrentHashMap<>() : null;

        DUMPER = (dumpPath == null) ? null : ProxyClassesDumper.getInstance(dumpPath);

    }

    /**

     * Cache key is a composite of:

     *   - class name, that lets to disambiguate stubs, to avoid excess sharing

     *   - method type, describing the dynamic arguments for concatenation

     *   - concat recipe, describing the constants and concat shape

     */

    private static final class Key {

        final String className;

        final MethodType mt;

        final Recipe recipe;

        public Key(String className, MethodType mt, Recipe recipe) {

            this.className = className;

            this.mt = mt;

            this.recipe = recipe;

        }

        @Override

        public boolean equals(Object o) {

            if (this == o) return true;

            if (o == null || getClass() != o.getClass()) return false;

            Key key = (Key) o;

            if (!className.equals(key.className)) return false;

            if (!mt.equals(key.mt)) return false;

            if (!recipe.equals(key.recipe)) return false;

            return true;

        }

        @Override

        public int hashCode() {

            int result = className.hashCode();

            result = 31 * result + mt.hashCode();

            result = 31 * result + recipe.hashCode();

            return result;

        }

    }

    /**

     * Parses the recipe string, and produces the traversable collection of

     * {@link java.lang.invoke.StringConcatFactory.RecipeElement}-s for generator

     * strategies. Notably, this class parses out the constants from the recipe

     * and from other static arguments.

     */

    private static final class Recipe {

        private final List<RecipeElement> elements;

        public Recipe(String src, Object[] constants) {

            List<RecipeElement> el = new ArrayList<>();

            int constC = 0;

            int argC = 0;

            StringBuilder acc = new StringBuilder();

            for (int i = 0; i < src.length(); i++) {

                char c = src.charAt(i);

                if (c == TAG_CONST || c == TAG_ARG) {

                    // Detected a special tag, flush all accumulated characters

                    // as a constant first:

                    if (acc.length() > 0) {

                        el.add(new RecipeElement(acc.toString()));

                        acc.setLength(0);

                    }

                    if (c == TAG_CONST) {

                        Object cnst = constants[constC++];

                        el.add(new RecipeElement(cnst));

                    } else if (c == TAG_ARG) {

                        el.add(new RecipeElement(argC++));

                    }

                } else {

                    // Not a special character, this is a constant embedded into

                    // the recipe itself.

                    acc.append(c);

                }

            }

            // Flush the remaining characters as constant:

            if (acc.length() > 0) {

                el.add(new RecipeElement(acc.toString()));

            }

            elements = el;

        }

        public List<RecipeElement> getElements() {

            return elements;

        }

        @Override

        public boolean equals(Object o) {

            if (this == o) return true;

            if (o == null || getClass() != o.getClass()) return false;

            Recipe recipe = (Recipe) o;

            return elements.equals(recipe.elements);

        }

        @Override

        public String toString() {

            return "Recipe{" +

                    "elements=" + elements +

                    '}';

        }

        @Override

        public int hashCode() {

            return elements.hashCode();

        }

    }

    private static final class RecipeElement {

        private final String value;

        private final int argPos;

        private final char tag;

        public RecipeElement(Object cnst) {

            this.value = String.valueOf(Objects.requireNonNull(cnst));

            this.argPos = -1;

            this.tag = TAG_CONST;

        }

        public RecipeElement(int arg) {

            this.value = null;

            this.argPos = arg;

            this.tag = TAG_ARG;

        }

        public String getValue() {

            assert (tag == TAG_CONST);

            return value;

        }

        public int getArgPos() {

            assert (tag == TAG_ARG);

            return argPos;

        }

        public char getTag() {

            return tag;

        }

        @Override

        public boolean equals(Object o) {

            if (this == o) return true;

            if (o == null || getClass() != o.getClass()) return false;

            RecipeElement that = (RecipeElement) o;

            if (this.tag != that.tag) return false;

            if (this.tag == TAG_CONST && (!value.equals(that.value))) return false;

            if (this.tag == TAG_ARG && (argPos != that.argPos)) return false;

            return true;

        }

        @Override

        public String toString() {

            return "RecipeElement{" +

                    "value='" + value + '\'' +

                    ", argPos=" + argPos +

                    ", tag=" + tag +

                    '}';

        }

        @Override

        public int hashCode() {

            return (int)tag;

        }

    }

    // StringConcatFactory bootstrap methods are startup sensitive, and may be

    // special cased in java.lang.invokeBootstrapMethodInvoker to ensure

    // methods are invoked with exact type information to avoid generating

    // code for runtime checks. Take care any changes or additions here are

    // reflected there as appropriate.

    /**

     * Facilitates the creation of optimized String concatenation methods, that

     * can be used to efficiently concatenate a known number of arguments of

     * known types, possibly after type adaptation and partial evaluation of

     * arguments. Typically used as a <em>bootstrap method</em> for {@code

     * invokedynamic} call sites, to support the <em>string concatenation</em>

     * feature of the Java Programming Language.

     *

     * <p>When the target of the {@code CallSite} returned from this method is

     * invoked, it returns the result of String concatenation, taking all

     * function arguments passed to the linkage method as inputs for

     * concatenation. The target signature is given by {@code concatType}.

     * For a target accepting:

     * <ul>

     *     <li>zero inputs, concatenation results in an empty string;</li>

     *     <li>one input, concatenation results in the single

     *     input converted as per JLS 5.1.11 "String Conversion"; otherwise</li>

     *     <li>two or more inputs, the inputs are concatenated as per

     *     requirements stated in JLS 15.18.1 "String Concatenation Operator +".

     *     The inputs are converted as per JLS 5.1.11 "String Conversion",

     *     and combined from left to right.</li>

     * </ul>

     *

     * <p>Assume the linkage arguments are as follows:

     *

     * <ul>

     *     <li>{@code concatType}, describing the {@code CallSite} signature</li>

     * </ul>

     *

     * <p>Then the following linkage invariants must hold:

     *

     * <ul>

     *     <li>The number of parameter slots in {@code concatType} is

     *         less than or equal to 200</li>

     *     <li>The return type in {@code concatType} is assignable from {@link java.lang.String}</li>

     * </ul>

     *

     * @param lookup   Represents a lookup context with the accessibility

     *                 privileges of the caller. Specifically, the lookup

     *                 context must have

     *                 <a href="MethodHandles.Lookup.html#privacc">private access</a>

     *                 privileges.

     *                 When used with {@code invokedynamic}, this is stacked

     *                 automatically by the VM.

     * @param name     The name of the method to implement. This name is

     *                 arbitrary, and has no meaning for this linkage method.

     *                 When used with {@code invokedynamic}, this is provided by

     *                 the {@code NameAndType} of the {@code InvokeDynamic}

     *                 structure and is stacked automatically by the VM.

     * @param concatType The expected signature of the {@code CallSite}.  The

     *                   parameter types represent the types of concatenation

     *                   arguments; the return type is always assignable from {@link

     *                   java.lang.String}.  When used with {@code invokedynamic},

     *                   this is provided by the {@code NameAndType} of the {@code

     *                   InvokeDynamic} structure and is stacked automatically by

     *                   the VM.

     * @return a CallSite whose target can be used to perform String

     * concatenation, with dynamic concatenation arguments described by the given

     * {@code concatType}.

     * @throws StringConcatException If any of the linkage invariants described

     *                               here are violated, or the lookup context

     *                               does not have private access privileges.

     * @throws NullPointerException If any of the incoming arguments is null.

     *                              This will never happen when a bootstrap method

     *                              is called with invokedynamic.

     *

     * @jls  5.1.11 String Conversion

     * @jls 15.18.1 String Concatenation Operator +

     */

    public static CallSite makeConcat(MethodHandles.Lookup lookup,

                                      String name,

                                      MethodType concatType) throws StringConcatException {

        if (DEBUG) {

            System.out.println("StringConcatFactory " + STRATEGY + " is here for " + concatType);

        }

        return doStringConcat(lookup, name, concatType, true, null);

    }

    /**

     * Facilitates the creation of optimized String concatenation methods, that

     * can be used to efficiently concatenate a known number of arguments of

     * known types, possibly after type adaptation and partial evaluation of

     * arguments. Typically used as a <em>bootstrap method</em> for {@code

     * invokedynamic} call sites, to support the <em>string concatenation</em>

     * feature of the Java Programming Language.

     *

     * <p>When the target of the {@code CallSite} returned from this method is

     * invoked, it returns the result of String concatenation, taking all

     * function arguments and constants passed to the linkage method as inputs for

     * concatenation. The target signature is given by {@code concatType}, and

     * does not include constants.

     * For a target accepting:

     * <ul>

     *     <li>zero inputs, concatenation results in an empty string;</li>

     *     <li>one input, concatenation results in the single

     *     input converted as per JLS 5.1.11 "String Conversion"; otherwise</li>

     *     <li>two or more inputs, the inputs are concatenated as per

     *     requirements stated in JLS 15.18.1 "String Concatenation Operator +".

     *     The inputs are converted as per JLS 5.1.11 "String Conversion",

     *     and combined from left to right.</li>

     * </ul>

     *

     * <p>The concatenation <em>recipe</em> is a String description for the way to

     * construct a concatenated String from the arguments and constants. The

     * recipe is processed from left to right, and each character represents an

     * input to concatenation. Recipe characters mean:

     *

     * <ul>

     *

     *   <li><em>\1 (Unicode point 0001)</em>: an ordinary argument. This

     *   input is passed through dynamic argument, and is provided during the