/*

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

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 jdk.internal.vm.annotation.ForceInline;

import jdk.internal.misc.Unsafe;

import java.lang.invoke.MethodHandles.Lookup;

import java.security.AccessController;

import java.security.PrivilegedAction;

import java.util.*;

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 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 final Strategy STRATEGY;

    /**

     * Default strategy to use for concatenation.

     */

    private static final Strategy DEFAULT_STRATEGY = Strategy.BC_SB;

    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;

    static {

        // Poke the privileged block once, taking everything we need:

        AccessController.doPrivileged((PrivilegedAction<Object>) () -> {

            values[0] = System.getProperty("java.lang.invoke.stringConcat");

            values[1] = Boolean.getBoolean("java.lang.invoke.stringConcat.cache");

            values[2] = Boolean.getBoolean("java.lang.invoke.stringConcat.debug");

            return null;

        });

        final String strategy = (String)  values[0];

        CACHE_ENABLE          = (Boolean) values[1];

        DEBUG                 = (Boolean) values[2];

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

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

    }

    private static final class Key {

        final MethodType mt;

        final Recipe recipe;

        public Key(MethodType mt, Recipe recipe) {

            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 (!mt.equals(key.mt)) return false;

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

            return true;

        }

        @Override

        public int hashCode() {

            int 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;

        private final List<RecipeElement> elementsRev;

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

                    }

                    if (c == TAG_ARG) {

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

                    }

                } else {

                    // Not a special characters, 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 = new ArrayList<>(el);

            Collections.reverse(el);

            elementsRev = el;

        }

        public Collection<RecipeElement> getElements() {

            return elements;

        }

        public Collection<RecipeElement> getElementsReversed() {

            return elementsRev;

        }

        @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 int hashCode() {

            return elements.hashCode();

        }

    }

    private static final class RecipeElement {

        private final Object value;

        private final int argPos;

        private final Tag tag;

        public RecipeElement(Object cnst) {

            this.value = 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 Object getValue() {

            assert (tag == Tag.CONST);

            return value;

        }

        public int getArgPos() {

            assert (tag == Tag.ARG);

            return argPos;

        }

        public Tag 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 (tag != that.tag) return false;

            if (tag == Tag.CONST && (!value.equals(that.value))) return false;

            if (tag == Tag.ARG && (argPos != that.argPos)) return false;

            return true;

        }

        @Override

        public int hashCode() {

            return tag.hashCode();

        }

    }

    private enum Tag {

        CONST, ARG

    }

    /**

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

     * The arguments are concatenated as per requirements stated in JLS 15.18.1

     * "String Concatenation Operator +". Notably, the inputs are converted as

     * per JLS 5.1.11 "String Conversion", and combined from left to right.

     *

     * <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 parameter count 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.  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.

     * @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. The arguments are concatenated as per requirements

     * stated in JLS 15.18.1 "String Concatenation Operator +". Notably, the inputs

     * are converted as per JLS 5.1.11 "String Conversion", and combined from left

     * to right.

     *

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

     *   concatenation method invocation. This input can be null.</li>

     *

     *   <li><em>\2 (Unicode point 0002):</em> a constant. This input passed

     *   through static bootstrap argument. This constant can be any value

     *   representable in constant pool. If necessary, the factory would call

     *   {@code toString} to perform a one-time String conversion.</li>

     *

     *   <li><em>Any other char value:</em> a single character constant.</li>

     * </ul>

     *

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

     *

     * <ul>

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

     *   <li>{@code recipe}, describing the String recipe</li>

     *   <li>{@code constants}, the vararg array of constants</li>

     * </ul>

     *

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

     *

     * <ul>

     *   <li>The parameter count in {@code concatType} is less than or equal to

     *   200</li>

     *

     *   <li>The parameter count in {@code concatType} equals to number of \1 tags

     *   in {@code recipe}</li>

     *

     *   <li>The return type in {@code concatType} is assignable

     *   from {@link java.lang.String}, and matches the return type of the

     *   returned {@link MethodHandle}</li>

     *

     *   <li>The number of elements in {@code constants} equals to number of \2

     *   tags in {@code recipe}</li>

     * </ul>

     *

     * @param lookup    Represents a lookup context with the accessibility

     *                  privileges of the caller. 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 dynamic 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.

     * @param recipe    Concatenation recipe, described above.

     * @param constants A vararg parameter representing the constants passed to

     *                  the linkage method.

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

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

     *                              any constant in {@code recipe} is null.

     *                              This will never happen when a bootstrap method

     *                              is called with invokedynamic.

     * @apiNote Code generators have three distinct ways to process a constant

     * string operand S in a string concatenation expression.  First, S can be

     * materialized as a reference (using ldc) and passed as an ordinary argument