/*

 * Copyright (c) 1994, 2021, 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;

import java.io.ObjectStreamField;

import java.io.UnsupportedEncodingException;

import java.lang.annotation.Native;

import java.lang.invoke.MethodHandles;

import java.lang.constant.Constable;

import java.lang.constant.ConstantDesc;

import java.nio.ByteBuffer;

import java.nio.CharBuffer;

import java.nio.charset.*;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Comparator;

import java.util.Formatter;

import java.util.List;

import java.util.Locale;

import java.util.Objects;

import java.util.Optional;

import java.util.Spliterator;

import java.util.function.Function;

import java.util.regex.Pattern;

import java.util.regex.PatternSyntaxException;

import java.util.stream.Collectors;

import java.util.stream.IntStream;

import java.util.stream.Stream;

import java.util.stream.StreamSupport;

import jdk.internal.vm.annotation.ForceInline;

import jdk.internal.vm.annotation.IntrinsicCandidate;

import jdk.internal.vm.annotation.Stable;

import sun.nio.cs.ArrayDecoder;

import sun.nio.cs.ArrayEncoder;

import sun.nio.cs.ISO_8859_1;

import sun.nio.cs.US_ASCII;

import sun.nio.cs.UTF_8;

/**

 * The {@code String} class represents character strings. All

 * string literals in Java programs, such as {@code "abc"}, are

 * implemented as instances of this class.

 * <p>

 * Strings are constant; their values cannot be changed after they

 * are created. String buffers support mutable strings.

 * Because String objects are immutable they can be shared. For example:

 * <blockquote><pre>

 *     String str = "abc";

 * </pre></blockquote><p>

 * is equivalent to:

 * <blockquote><pre>

 *     char data[] = {'a', 'b', 'c'};

 *     String str = new String(data);

 * </pre></blockquote><p>

 * Here are some more examples of how strings can be used:

 * <blockquote><pre>

 *     System.out.println("abc");

 *     String cde = "cde";

 *     System.out.println("abc" + cde);

 *     String c = "abc".substring(2, 3);

 *     String d = cde.substring(1, 2);

 * </pre></blockquote>

 * <p>

 * The class {@code String} includes methods for examining

 * individual characters of the sequence, for comparing strings, for

 * searching strings, for extracting substrings, and for creating a

 * copy of a string with all characters translated to uppercase or to

 * lowercase. Case mapping is based on the Unicode Standard version

 * specified by the {@link java.lang.Character Character} class.

 * <p>

 * The Java language provides special support for the string

 * concatenation operator ( + ), and for conversion of

 * other objects to strings. For additional information on string

 * concatenation and conversion, see <i>The Java Language Specification</i>.

 *

 * <p> Unless otherwise noted, passing a {@code null} argument to a constructor

 * or method in this class will cause a {@link NullPointerException} to be

 * thrown.

 *

 * <p>A {@code String} represents a string in the UTF-16 format

 * in which <em>supplementary characters</em> are represented by <em>surrogate

 * pairs</em> (see the section <a href="Character.html#unicode">Unicode

 * Character Representations</a> in the {@code Character} class for

 * more information).

 * Index values refer to {@code char} code units, so a supplementary

 * character uses two positions in a {@code String}.

 * <p>The {@code String} class provides methods for dealing with

 * Unicode code points (i.e., characters), in addition to those for

 * dealing with Unicode code units (i.e., {@code char} values).

 *

 * <p>Unless otherwise noted, methods for comparing Strings do not take locale

 * into account.  The {@link java.text.Collator} class provides methods for

 * finer-grain, locale-sensitive String comparison.

 *

 * @implNote The implementation of the string concatenation operator is left to

 * the discretion of a Java compiler, as long as the compiler ultimately conforms

 * to <i>The Java Language Specification</i>. For example, the {@code javac} compiler

 * may implement the operator with {@code StringBuffer}, {@code StringBuilder},

 * or {@code java.lang.invoke.StringConcatFactory} depending on the JDK version. The

 * implementation of string conversion is typically through the method {@code toString},

 * defined by {@code Object} and inherited by all classes in Java.

 *

 * @author  Lee Boynton

 * @author  Arthur van Hoff

 * @author  Martin Buchholz

 * @author  Ulf Zibis

 * @see     java.lang.Object#toString()

 * @see     java.lang.StringBuffer

 * @see     java.lang.StringBuilder

 * @see     java.nio.charset.Charset

 * @since   1.0

 * @jls     15.18.1 String Concatenation Operator +

 */

public final class String

    implements java.io.Serializable, Comparable<String>, CharSequence,

               Constable, ConstantDesc {

    /**

     * The value is used for character storage.

     *

     * @implNote This field is trusted by the VM, and is a subject to

     * constant folding if String instance is constant. Overwriting this

     * field after construction will cause problems.

     *

     * Additionally, it is marked with {@link Stable} to trust the contents

     * of the array. No other facility in JDK provides this functionality (yet).

     * {@link Stable} is safe here, because value is never null.

     */

    @Stable

    private final byte[] value;

    /**

     * The identifier of the encoding used to encode the bytes in

     * {@code value}. The supported values in this implementation are

     *

     * LATIN1

     * UTF16

     *

     * @implNote This field is trusted by the VM, and is a subject to

     * constant folding if String instance is constant. Overwriting this

     * field after construction will cause problems.

     */

    private final byte coder;

    /** Cache the hash code for the string */

    private int hash; // Default to 0

    /**

     * Cache if the hash has been calculated as actually being zero, enabling

     * us to avoid recalculating this.

     */

    private boolean hashIsZero; // Default to false;

    /** use serialVersionUID from JDK 1.0.2 for interoperability */

    @java.io.Serial

    private static final long serialVersionUID = -6849794470754667710L;

    /**

     * If String compaction is disabled, the bytes in {@code value} are

     * always encoded in UTF16.

     *

     * For methods with several possible implementation paths, when String

     * compaction is disabled, only one code path is taken.

     *

     * The instance field value is generally opaque to optimizing JIT

     * compilers. Therefore, in performance-sensitive place, an explicit

     * check of the static boolean {@code COMPACT_STRINGS} is done first

     * before checking the {@code coder} field since the static boolean

     * {@code COMPACT_STRINGS} would be constant folded away by an

     * optimizing JIT compiler. The idioms for these cases are as follows.

     *

     * For code such as:

     *

     *    if (coder == LATIN1) { ... }

     *

     * can be written more optimally as

     *

     *    if (coder() == LATIN1) { ... }

     *

     * or:

     *

     *    if (COMPACT_STRINGS && coder == LATIN1) { ... }

     *

     * An optimizing JIT compiler can fold the above conditional as:

     *

     *    COMPACT_STRINGS == true  => if (coder == LATIN1) { ... }

     *    COMPACT_STRINGS == false => if (false)           { ... }

     *

     * @implNote

     * The actual value for this field is injected by JVM. The static

     * initialization block is used to set the value here to communicate

     * that this static final field is not statically foldable, and to

     * avoid any possible circular dependency during vm initialization.

     */

    static final boolean COMPACT_STRINGS;

    static {

        COMPACT_STRINGS = true;

    }

    /**

     * Class String is special cased within the Serialization Stream Protocol.

     *

     * A String instance is written into an ObjectOutputStream according to

     * <a href="{@docRoot}/../specs/serialization/protocol.html#stream-elements">

     * Object Serialization Specification, Section 6.2, "Stream Elements"</a>

     */

    @java.io.Serial

    private static final ObjectStreamField[] serialPersistentFields =

        new ObjectStreamField[0];

    /**

     * Initializes a newly created {@code String} object so that it represents

     * an empty character sequence.  Note that use of this constructor is

     * unnecessary since Strings are immutable.

     */

    public String() {

        this.value = "".value;

        this.coder = "".coder;

    }

    /**

     * Initializes a newly created {@code String} object so that it represents

     * the same sequence of characters as the argument; in other words, the

     * newly created string is a copy of the argument string. Unless an

     * explicit copy of {@code original} is needed, use of this constructor is

     * unnecessary since Strings are immutable.

     *

     * @param  original

     *         A {@code String}

     */

    @IntrinsicCandidate

    public String(String original) {

        this.value = original.value;

        this.coder = original.coder;

        this.hash = original.hash;

    }

    /**

     * Allocates a new {@code String} so that it represents the sequence of

     * characters currently contained in the character array argument. The

     * contents of the character array are copied; subsequent modification of

     * the character array does not affect the newly created string.

     *

     * @param  value

     *         The initial value of the string

     */

    public String(char value[]) {

        this(value, 0, value.length, null);

    }

    /**

     * Allocates a new {@code String} that contains characters from a subarray

     * of the character array argument. The {@code offset} argument is the

     * index of the first character of the subarray and the {@code count}

     * argument specifies the length of the subarray. The contents of the

     * subarray are copied; subsequent modification of the character array does

     * not affect the newly created string.

     *

     * @param  value

     *         Array that is the source of characters

     *

     * @param  offset

     *         The initial offset

     *

     * @param  count

     *         The length

     *

     * @throws  IndexOutOfBoundsException

     *          If {@code offset} is negative, {@code count} is negative, or

     *          {@code offset} is greater than {@code value.length - count}

     */

    public String(char value[], int offset, int count) {

        this(value, offset, count, rangeCheck(value, offset, count));

    }

    private static Void rangeCheck(char[] value, int offset, int count) {

        checkBoundsOffCount(offset, count, value.length);

        return null;

    }

    /**

     * Allocates a new {@code String} that contains characters from a subarray

     * of the <a href="Character.html#unicode">Unicode code point</a> array

     * argument.  The {@code offset} argument is the index of the first code

     * point of the subarray and the {@code count} argument specifies the

     * length of the subarray.  The contents of the subarray are converted to

     * {@code char}s; subsequent modification of the {@code int} array does not

     * affect the newly created string.

     *

     * @param  codePoints

     *         Array that is the source of Unicode code points

     *

     * @param  offset

     *         The initial offset

     *

     * @param  count

     *         The length

     *

     * @throws  IllegalArgumentException

     *          If any invalid Unicode code point is found in {@code

     *          codePoints}

     *

     * @throws  IndexOutOfBoundsException

     *          If {@code offset} is negative, {@code count} is negative, or

     *          {@code offset} is greater than {@code codePoints.length - count}

     *

     * @since  1.5

     */

    public String(int[] codePoints, int offset, int count) {

        checkBoundsOffCount(offset, count, codePoints.length);

        if (count == 0) {

            this.value = "".value;

            this.coder = "".coder;

            return;

        }

        if (COMPACT_STRINGS) {

            byte[] val = StringLatin1.toBytes(codePoints, offset, count);

            if (val != null) {

                this.coder = LATIN1;

                this.value = val;

                return;

            }

        }

        this.coder = UTF16;

        this.value = StringUTF16.toBytes(codePoints, offset, count);

    }

    /**

     * Allocates a new {@code String} constructed from a subarray of an array

     * of 8-bit integer values.

     *

     * <p> The {@code offset} argument is the index of the first byte of the

     * subarray, and the {@code count} argument specifies the length of the

     * subarray.

     *

     * <p> Each {@code byte} in the subarray is converted to a {@code char} as

     * specified in the {@link #String(byte[],int) String(byte[],int)} constructor.

     *

     * @deprecated This method does not properly convert bytes into characters.

     * As of JDK 1.1, the preferred way to do this is via the

     * {@code String} constructors that take a {@link

     * java.nio.charset.Charset}, charset name, or that use the platform's

     * default charset.

     *

     * @param  ascii

     *         The bytes to be converted to characters

     *

     * @param  hibyte

     *         The top 8 bits of each 16-bit Unicode code unit

     *

     * @param  offset

     *         The initial offset

     * @param  count

     *         The length

     *

     * @throws  IndexOutOfBoundsException

     *          If {@code offset} is negative, {@code count} is negative, or

     *          {@code offset} is greater than {@code ascii.length - count}

     *

     * @see  #String(byte[], int)

     * @see  #String(byte[], int, int, java.lang.String)

     * @see  #String(byte[], int, int, java.nio.charset.Charset)

     * @see  #String(byte[], int, int)

     * @see  #String(byte[], java.lang.String)

     * @see  #String(byte[], java.nio.charset.Charset)

     * @see  #String(byte[])

     */

    @Deprecated(since="1.1")

    public String(byte ascii[], int hibyte, int offset, int count) {

        checkBoundsOffCount(offset, count, ascii.length);

        if (count == 0) {

            this.value = "".value;

            this.coder = "".coder;

            return;

        }

        if (COMPACT_STRINGS && (byte)hibyte == 0) {

            this.value = Arrays.copyOfRange(ascii, offset, offset + count);

            this.coder = LATIN1;

        } else {

            hibyte <<= 8;

            byte[] val = StringUTF16.newBytesFor(count);

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

                StringUTF16.putChar(val, i, hibyte | (ascii[offset++] & 0xff));

            }

            this.value = val;

            this.coder = UTF16;

        }

    }

    /**

     * Allocates a new {@code String} containing characters constructed from

     * an array of 8-bit integer values. Each character <i>c</i> in the

     * resulting string is constructed from the corresponding component

     * <i>b</i> in the byte array such that:

     *

     * <blockquote><pre>

     *     <b><i>c</i></b> == (char)(((hibyte &amp; 0xff) &lt;&lt; 8)

     *                         | (<b><i>b</i></b> &amp; 0xff))

     * </pre></blockquote>

     *

     * @deprecated  This method does not properly convert bytes into

     * characters.  As of JDK 1.1, the preferred way to do this is via the

     * {@code String} constructors that take a {@link

     * java.nio.charset.Charset}, charset name, or that use the platform's

     * default charset.

     *

     * @param  ascii

     *         The bytes to be converted to characters

     *

     * @param  hibyte

     *         The top 8 bits of each 16-bit Unicode code unit

     *

     * @see  #String(byte[], int, int, java.lang.String)

     * @see  #String(byte[], int, int, java.nio.charset.Charset)

     * @see  #String(byte[], int, int)

     * @see  #String(byte[], java.lang.String)

     * @see  #String(byte[], java.nio.charset.Charset)

     * @see  #String(byte[])

     */

    @Deprecated(since="1.1")

    public String(byte ascii[], int hibyte) {

        this(ascii, hibyte, 0, ascii.length);

    }

    /**

     * Constructs a new {@code String} by decoding the specified subarray of

     * bytes using the specified charset.  The length of the new {@code String}

     * is a function of the charset, and hence may not be equal to the length

     * of the subarray.

     *

     * <p> The behavior of this constructor when the given bytes are not valid

     * in the given charset is unspecified.  The {@link

     * java.nio.charset.CharsetDecoder} class should be used when more control

     * over the decoding process is required.

     *

     * @param  bytes

     *         The bytes to be decoded into characters

     *

     * @param  offset

     *         The index of the first byte to decode

     *

     * @param  length

     *         The number of bytes to decode

     *

     * @param  charsetName

     *         The name of a supported {@linkplain java.nio.charset.Charset

     *         charset}

     *

     * @throws  UnsupportedEncodingException

     *          If the named charset is not supported

     *

     * @throws  IndexOutOfBoundsException

     *          If {@code offset} is negative, {@code length} is negative, or

     *          {@code offset} is greater than {@code bytes.length - length}

     *

     * @since  1.1

     */

    public String(byte[] bytes, int offset, int length, String charsetName)

            throws UnsupportedEncodingException {

        this(bytes, offset, length, lookupCharset(charsetName));

    }

    /**

     * Constructs a new {@code String} by decoding the specified subarray of

     * bytes using the specified {@linkplain java.nio.charset.Charset charset}.

     * The length of the new {@code String} is a function of the charset, and

     * hence may not be equal to the length of the subarray.

     *

     * <p> This method always replaces malformed-input and unmappable-character

     * sequences with this charset's default replacement string.  The {@link

     * java.nio.charset.CharsetDecoder} class should be used when more control

     * over the decoding process is required.

     *

     * @param  bytes

     *         The bytes to be decoded into characters

     *

     * @param  offset

     *         The index of the first byte to decode

     *

     * @param  length

     *         The number of bytes to decode

     *

     * @param  charset

     *         The {@linkplain java.nio.charset.Charset charset} to be used to

     *         decode the {@code bytes}

     *

     * @throws  IndexOutOfBoundsException

     *          If {@code offset} is negative, {@code length} is negative, or

     *          {@code offset} is greater than {@code bytes.length - length}

     *

     * @since  1.6

     */

    @SuppressWarnings("removal")

    public String(byte[] bytes, int offset, int length, Charset charset) {

        Objects.requireNonNull(charset);

        checkBoundsOffCount(offset, length, bytes.length);

        if (length == 0) {

            this.value = "".value;

            this.coder = "".coder;

        } else if (charset == UTF_8.INSTANCE) {

            if (COMPACT_STRINGS && !StringCoding.hasNegatives(bytes, offset, length)) {

                this.value = Arrays.copyOfRange(bytes, offset, offset + length);

                this.coder = LATIN1;

            } else {

                int sl = offset + length;

                int dp = 0;

                byte[] dst = null;

                if (COMPACT_STRINGS) {

                    dst = new byte[length];

                    while (offset < sl) {

                        int b1 = bytes[offset];

                        if (b1 >= 0) {

                            dst[dp++] = (byte)b1;

                            offset++;

                            continue;

                        }

                        if ((b1 == (byte)0xc2 || b1 == (byte)0xc3) &&

                                offset + 1 < sl) {

                            int b2 = bytes[offset + 1];

                            if (!isNotContinuation(b2)) {

                                dst[dp++] = (byte)decode2(b1, b2);

                                offset += 2;

                                continue;

                            }

                        }

                        // anything not a latin1, including the repl

                        // we have to go with the utf16

                        break;

                    }

                    if (offset == sl) {

                        if (dp != dst.length) {

                            dst = Arrays.copyOf(dst, dp);

                        }

                        this.value = dst;

                        this.coder = LATIN1;

                        return;

                    }

                }

                if (dp == 0 || dst == null) {

                    dst = new byte[length << 1];

                } else {

                    byte[] buf = new byte[length << 1];

                    StringLatin1.inflate(dst, 0, buf, 0, dp);

                    dst = buf;

                }

                dp = decodeUTF8_UTF16(bytes, offset, sl, dst, dp, true);

                if (dp != length) {

                    dst = Arrays.copyOf(dst, dp << 1);

                }

                this.value = dst;

                this.coder = UTF16;

            }

        } else if (charset == ISO_8859_1.INSTANCE) {

            if (COMPACT_STRINGS) {

                this.value = Arrays.copyOfRange(bytes, offset, offset + length);

                this.coder = LATIN1;

            } else {

                this.value = StringLatin1.inflate(bytes, offset, length);

                this.coder = UTF16;

            }

        } else if (charset == US_ASCII.INSTANCE) {

            if (COMPACT_STRINGS && !StringCoding.hasNegatives(bytes, offset, length)) {

                this.value = Arrays.copyOfRange(bytes, offset, offset + length);

                this.coder = LATIN1;

            } else {

                byte[] dst = new byte[length << 1];

                int dp = 0;

                while (dp < length) {

                    int b = bytes[offset++];

                    StringUTF16.putChar(dst, dp++, (b >= 0) ? (char) b : REPL);

                }

                this.value = dst;

                this.coder = UTF16;

            }

        } else {

            // (1)We never cache the "external" cs, the only benefit of creating

            // an additional StringDe/Encoder object to wrap it is to share the

            // de/encode() method. These SD/E objects are short-lived, the young-gen

            // gc should be able to take care of them well. But the best approach

            // is still not to generate them if not really necessary.

            // (2)The defensive copy of the input byte/char[] has a big performance

            // impact, as well as the outgoing result byte/char[]. Need to do the

            // optimization check of (sm==null && classLoader0==null) for both.

            CharsetDecoder cd = charset.newDecoder();

            // ArrayDecoder fastpaths

            if (cd instanceof ArrayDecoder ad) {

                // ascii

                if (ad.isASCIICompatible() && !StringCoding.hasNegatives(bytes, offset, length)) {

                    if (COMPACT_STRINGS) {

                        this.value = Arrays.copyOfRange(bytes, offset, offset + length);

                        this.coder = LATIN1;

                        return;

                    }

                    this.value = StringLatin1.inflate(bytes, offset, length);

                    this.coder = UTF16;

                    return;

                }

                // fastpath for always Latin1 decodable single byte

                if (COMPACT_STRINGS && ad.isLatin1Decodable()) {

                    byte[] dst = new byte[length];

                    ad.decodeToLatin1(bytes, offset, length, dst);

                    this.value = dst;

                    this.coder = LATIN1;

                    return;

                }

                int en = scale(length, cd.maxCharsPerByte());

                cd.onMalformedInput(CodingErrorAction.REPLACE)

                        .onUnmappableCharacter(CodingErrorAction.REPLACE);

                char[] ca = new char[en];

                int clen = ad.decode(bytes, offset, length, ca);

                if (COMPACT_STRINGS) {

                    byte[] bs = StringUTF16.compress(ca, 0, clen);

                    if (bs != null) {

                        value = bs;

                        coder = LATIN1;

                        return;

                    }

                }

                coder = UTF16;

                value = StringUTF16.toBytes(ca, 0, clen);

                return;

            }

            // decode using CharsetDecoder

            int en = scale(length, cd.maxCharsPerByte());

            cd.onMalformedInput(CodingErrorAction.REPLACE)

                    .onUnmappableCharacter(CodingErrorAction.REPLACE);

            char[] ca = new char[en];

            if (charset.getClass().getClassLoader0() != null &&

                    System.getSecurityManager() != null) {

                bytes = Arrays.copyOfRange(bytes, offset, offset + length);

                offset = 0;

            }

            int caLen = decodeWithDecoder(cd, ca, bytes, offset, length);

            if (COMPACT_STRINGS) {

                byte[] bs = StringUTF16.compress(ca, 0, caLen);

                if (bs != null) {

                    value = bs;

                    coder = LATIN1;

                    return;

                }

            }

            coder = UTF16;

            value = StringUTF16.toBytes(ca, 0, caLen);

        }

    }

    /*

     * Throws iae, instead of replacing, if malformed or unmappable.

     */

    static String newStringUTF8NoRepl(byte[] bytes, int offset, int length) {

        checkBoundsOffCount(offset, length, bytes.length);

        if (length == 0) {

            return "";

        }

        if (COMPACT_STRINGS && !StringCoding.hasNegatives(bytes, offset, length)) {

            return new String(Arrays.copyOfRange(bytes, offset, offset + length), LATIN1);

        } else {

            int sl = offset + length;

            int dp = 0;

            byte[] dst = null;

            if (COMPACT_STRINGS) {

                dst = new byte[length];

                while (offset < sl) {

                    int b1 = bytes[offset];

                    if (b1 >= 0) {

                        dst[dp++] = (byte) b1;

                        offset++;

                        continue;

                    }

                    if ((b1 == (byte) 0xc2 || b1 == (byte) 0xc3) &&

                            offset + 1 < sl) {

                        int b2 = bytes[offset + 1];

                        if (!isNotContinuation(b2)) {

                            dst[dp++] = (byte) decode2(b1, b2);

                            offset += 2;

                            continue;

                        }

                    }

                    // anything not a latin1, including the REPL

                    // we have to go with the utf16

                    break;

                }

                if (offset == sl) {

                    if (dp != dst.length) {

                        dst = Arrays.copyOf(dst, dp);

                    }

                    return new String(dst, LATIN1);

                }

            }

            if (dp == 0 || dst == null) {

                dst = new byte[length << 1];

            } else {

                byte[] buf = new byte[length << 1];

                StringLatin1.inflate(dst, 0, buf, 0, dp);

                dst = buf;

            }

            dp = decodeUTF8_UTF16(bytes, offset, sl, dst, dp, false);

            if (dp != length) {

                dst = Arrays.copyOf(dst, dp << 1);

            }

            return new String(dst, UTF16);

        }

    }

    static String newStringNoRepl(byte[] src, Charset cs) throws CharacterCodingException {

        try {

            return newStringNoRepl1(src, cs);

        } catch (IllegalArgumentException e) {

            //newStringNoRepl1 throws IAE with MalformedInputException or CCE as the cause

            Throwable cause = e.getCause();

            if (cause instanceof MalformedInputException mie) {

                throw mie;

            }

            throw (CharacterCodingException)cause;

        }

    }

    @SuppressWarnings("removal")

    private static String newStringNoRepl1(byte[] src, Charset cs) {

        int len = src.length;

        if (len == 0) {

            return "";

        }

        if (cs == UTF_8.INSTANCE) {

            return newStringUTF8NoRepl(src, 0, src.length);

        }

        if (cs == ISO_8859_1.INSTANCE) {

            if (COMPACT_STRINGS)

                return new String(src, LATIN1);

            return new String(StringLatin1.inflate(src, 0, src.length), UTF16);

        }

        if (cs == US_ASCII.INSTANCE) {

            if (!StringCoding.hasNegatives(src, 0, src.length)) {

                if (COMPACT_STRINGS)

                    return new String(src, LATIN1);

                return new String(StringLatin1.inflate(src, 0, src.length), UTF16);

            } else {

                throwMalformed(src);

            }

        }

        CharsetDecoder cd = cs.newDecoder();

        // ascii fastpath

        if (cd instanceof ArrayDecoder ad &&

                ad.isASCIICompatible() &&

                !StringCoding.hasNegatives(src, 0, src.length)) {

            return new String(src, 0, src.length, ISO_8859_1.INSTANCE);

        }

        int en = scale(len, cd.maxCharsPerByte());

        char[] ca = new char[en];

        if (cs.getClass().getClassLoader0() != null &&

                System.getSecurityManager() != null) {

            src = Arrays.copyOf(src, len);

        }

        int caLen = decodeWithDecoder(cd, ca, src, 0, src.length);

        if (COMPACT_STRINGS) {

            byte[] bs = StringUTF16.compress(ca, 0, caLen);

            if (bs != null) {

                return new String(bs, LATIN1);

            }

        }

        return new String(StringUTF16.toBytes(ca, 0, caLen), UTF16);

    }

    private static final char REPL = '\ufffd';

    // Trim the given byte array to the given length

    @SuppressWarnings("removal")

    private static byte[] safeTrim(byte[] ba, int len, boolean isTrusted) {

        if (len == ba.length && (isTrusted || System.getSecurityManager() == null)) {

            return ba;

        } else {

            return Arrays.copyOf(ba, len);

        }

    }

    private static int scale(int len, float expansionFactor) {

        // We need to perform double, not float, arithmetic; otherwise

        // we lose low order bits when len is larger than 2**24.

        return (int)(len * (double)expansionFactor);

    }

    private static Charset lookupCharset(String csn) throws UnsupportedEncodingException {

        Objects.requireNonNull(csn);

        try {

            return Charset.forName(csn);

        } catch (UnsupportedCharsetException | IllegalCharsetNameException x) {

            throw new UnsupportedEncodingException(csn);

        }

    }

    private static byte[] encode(Charset cs, byte coder, byte[] val) {

        if (cs == UTF_8.INSTANCE) {

            return encodeUTF8(coder, val, true);

        }

        if (cs == ISO_8859_1.INSTANCE) {

            return encode8859_1(coder, val);

        }

        if (cs == US_ASCII.INSTANCE) {

            return encodeASCII(coder, val);

        }

        return encodeWithEncoder(cs, coder, val, true);

    }

    private static byte[] encodeWithEncoder(Charset cs, byte coder, byte[] val, boolean doReplace) {

        CharsetEncoder ce = cs.newEncoder();

        int len = val.length >> coder;  // assume LATIN1=0/UTF16=1;

        int en = scale(len, ce.maxBytesPerChar());

        if (ce instanceof ArrayEncoder ae) {

            // fastpath for ascii compatible

            if (coder == LATIN1 &&

                    ae.isASCIICompatible() &&

                    !StringCoding.hasNegatives(val, 0, val.length)) {

                return Arrays.copyOf(val, val.length);

            }

            byte[] ba = new byte[en];

            if (len == 0) {

                return ba;

            }

            if (doReplace) {

                ce.onMalformedInput(CodingErrorAction.REPLACE)

                        .onUnmappableCharacter(CodingErrorAction.REPLACE);

            }

            int blen = (coder == LATIN1) ? ae.encodeFromLatin1(val, 0, len, ba)

                    : ae.encodeFromUTF16(val, 0, len, ba);

            if (blen != -1) {

                return safeTrim(ba, blen, true);

            }

        }

        byte[] ba = new byte[en];

        if (len == 0) {

            return ba;

        }

        if (doReplace) {

            ce.onMalformedInput(CodingErrorAction.REPLACE)

                    .onUnmappableCharacter(CodingErrorAction.REPLACE);

        }

        char[] ca = (coder == LATIN1 ) ? StringLatin1.toChars(val)

                : StringUTF16.toChars(val);

        ByteBuffer bb = ByteBuffer.wrap(ba);

        CharBuffer cb = CharBuffer.wrap(ca, 0, len);

        try {

            CoderResult cr = ce.encode(cb, bb, true);

            if (!cr.isUnderflow())

                cr.throwException();

            cr = ce.flush(bb);

            if (!cr.isUnderflow())

                cr.throwException();

        } catch (CharacterCodingException x) {

            if (!doReplace) {

                throw new IllegalArgumentException(x);

            } else {

                throw new Error(x);

            }

        }

        return safeTrim(ba, bb.position(), cs.getClass().getClassLoader0() == null);

    }

    /*

     * Throws iae, instead of replacing, if unmappable.

     */

    static byte[] getBytesUTF8NoRepl(String s) {

        return encodeUTF8(s.coder(), s.value(), false);

    }

    private static boolean isASCII(byte[] src) {

        return !StringCoding.hasNegatives(src, 0, src.length);

    }

    /*

     * Throws CCE, instead of replacing, if unmappable.

     */

    static byte[] getBytesNoRepl(String s, Charset cs) throws CharacterCodingException {

        try {

            return getBytesNoRepl1(s, cs);

        } catch (IllegalArgumentException e) {

            //getBytesNoRepl1 throws IAE with UnmappableCharacterException or CCE as the cause

            Throwable cause = e.getCause();

            if (cause instanceof UnmappableCharacterException) {

                throw (UnmappableCharacterException)cause;

            }

            throw (CharacterCodingException)cause;

        }

    }

    private static byte[] getBytesNoRepl1(String s, Charset cs) {

        byte[] val = s.value();

        byte coder = s.coder();

        if (cs == UTF_8.INSTANCE) {

            if (coder == LATIN1 && isASCII(val)) {

                return val;

            }

            return encodeUTF8(coder, val, false);

        }

        if (cs == ISO_8859_1.INSTANCE) {

            if (coder == LATIN1) {

                return val;

            }

            return encode8859_1(coder, val, false);

        }

        if (cs == US_ASCII.INSTANCE) {

            if (coder == LATIN1) {

                if (isASCII(val)) {

                    return val;

                } else {

                    throwUnmappable(val);

                }

            }

        }

        return encodeWithEncoder(cs, coder, val, false);

    }

    private static byte[] encodeASCII(byte coder, byte[] val) {

        if (coder == LATIN1) {

            byte[] dst = Arrays.copyOf(val, val.length);

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

                if (dst[i] < 0) {

                    dst[i] = '?';

                }

            }

            return dst;

        }

        int len = val.length >> 1;

        byte[] dst = new byte[len];

        int dp = 0;

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

            char c = StringUTF16.getChar(val, i);

            if (c < 0x80) {

                dst[dp++] = (byte)c;

                continue;

            }

            if (Character.isHighSurrogate(c) && i + 1 < len &&

                    Character.isLowSurrogate(StringUTF16.getChar(val, i + 1))) {

                i++;

            }

            dst[dp++] = '?';

        }

        if (len == dp) {

            return dst;

        }

        return Arrays.copyOf(dst, dp);

    }

    private static byte[] encode8859_1(byte coder, byte[] val) {

        return encode8859_1(coder, val, true);

    }

    private static byte[] encode8859_1(byte coder, byte[] val, boolean doReplace) {

        if (coder == LATIN1) {

            return Arrays.copyOf(val, val.length);

        }

        int len = val.length >> 1;

        byte[] dst = new byte[len];

        int dp = 0;

        int sp = 0;

        int sl = len;

        while (sp < sl) {

            int ret = StringCoding.implEncodeISOArray(val, sp, dst, dp, len);

            sp = sp + ret;

            dp = dp + ret;

            if (ret != len) {

                if (!doReplace) {

                    throwUnmappable(sp);

                }

                char c = StringUTF16.getChar(val, sp++);

                if (Character.isHighSurrogate(c) && sp < sl &&

                        Character.isLowSurrogate(StringUTF16.getChar(val, sp))) {

                    sp++;

                }

                dst[dp++] = '?';

                len = sl - sp;

            }

        }

        if (dp == dst.length) {

            return dst;

        }

        return Arrays.copyOf(dst, dp);

    }

    //////////////////////////////// utf8 ////////////////////////////////////

    /**

     * Decodes ASCII from the source byte array into the destination

     * char array. Used via JavaLangAccess from UTF_8 and other charset

     * decoders.

     *

     * @return the number of bytes successfully decoded, at most len

     */

    /* package-private */

    static int decodeASCII(byte[] sa, int sp, char[] da, int dp, int len) {

        if (!StringCoding.hasNegatives(sa, sp, len)) {

            StringLatin1.inflate(sa, sp, da, dp, len);

            return len;

        } else {

            int start = sp;

            int end = sp + len;

            while (sp < end && sa[sp] >= 0) {

                da[dp++] = (char) sa[sp++];

            }

            return sp - start;

        }

    }

    private static boolean isNotContinuation(int b) {

        return (b & 0xc0) != 0x80;

    }

    private static boolean isMalformed3(int b1, int b2, int b3) {

        return (b1 == (byte)0xe0 && (b2 & 0xe0) == 0x80) ||

                (b2 & 0xc0) != 0x80 || (b3 & 0xc0) != 0x80;

    }

    private static boolean isMalformed3_2(int b1, int b2) {

        return (b1 == (byte)0xe0 && (b2 & 0xe0) == 0x80) ||

                (b2 & 0xc0) != 0x80;

    }

    private static boolean isMalformed4(int b2, int b3, int b4) {

        return (b2 & 0xc0) != 0x80 || (b3 & 0xc0) != 0x80 ||

                (b4 & 0xc0) != 0x80;

    }

    private static boolean isMalformed4_2(int b1, int b2) {

        return (b1 == 0xf0 && (b2 < 0x90 || b2 > 0xbf)) ||

                (b1 == 0xf4 && (b2 & 0xf0) != 0x80) ||

                (b2 & 0xc0) != 0x80;

    }

    private static boolean isMalformed4_3(int b3) {

        return (b3 & 0xc0) != 0x80;

    }

    private static char decode2(int b1, int b2) {

        return (char)(((b1 << 6) ^ b2) ^

                (((byte) 0xC0 << 6) ^

                        ((byte) 0x80 << 0)));

    }

    private static char decode3(int b1, int b2, int b3) {

        return (char)((b1 << 12) ^

                (b2 <<  6) ^

                (b3 ^

                        (((byte) 0xE0 << 12) ^

                                ((byte) 0x80 <<  6) ^

                                ((byte) 0x80 <<  0))));

    }

    private static int decode4(int b1, int b2, int b3, int b4) {

        return ((b1 << 18) ^

                (b2 << 12) ^

                (b3 <<  6) ^

                (b4 ^

                        (((byte) 0xF0 << 18) ^

                                ((byte) 0x80 << 12) ^

                                ((byte) 0x80 <<  6) ^

                                ((byte) 0x80 <<  0))));

    }

    private static int decodeUTF8_UTF16(byte[] src, int sp, int sl, byte[] dst, int dp, boolean doReplace) {

        while (sp < sl) {

            int b1 = src[sp++];

            if (b1 >= 0) {

                StringUTF16.putChar(dst, dp++, (char) b1);

            } else if ((b1 >> 5) == -2 && (b1 & 0x1e) != 0) {

                if (sp < sl) {

                    int b2 = src[sp++];

                    if (isNotContinuation(b2)) {

                        if (!doReplace) {

                            throwMalformed(sp - 1, 1);

                        }

                        StringUTF16.putChar(dst, dp++, REPL);

                        sp--;

                    } else {

                        StringUTF16.putChar(dst, dp++, decode2(b1, b2));

                    }

                    continue;

                }

                if (!doReplace) {

                    throwMalformed(sp, 1);  // underflow()

                }

                StringUTF16.putChar(dst, dp++, REPL);

                break;

            } else if ((b1 >> 4) == -2) {

                if (sp + 1 < sl) {

                    int b2 = src[sp++];

                    int b3 = src[sp++];

                    if (isMalformed3(b1, b2, b3)) {

                        if (!doReplace) {

                            throwMalformed(sp - 3, 3);

                        }

                        StringUTF16.putChar(dst, dp++, REPL);

                        sp -= 3;

                        sp += malformed3(src, sp);

                    } else {

                        char c = decode3(b1, b2, b3);

                        if (Character.isSurrogate(c)) {

                            if (!doReplace) {

                                throwMalformed(sp - 3, 3);

                            }

                            StringUTF16.putChar(dst, dp++, REPL);

                        } else {

                            StringUTF16.putChar(dst, dp++, c);

                        }

                    }

                    continue;

                }

                if (sp < sl && isMalformed3_2(b1, src[sp])) {

                    if (!doReplace) {

                        throwMalformed(sp - 1, 2);

                    }

                    StringUTF16.putChar(dst, dp++, REPL);

                    continue;

                }

                if (!doReplace) {

                    throwMalformed(sp, 1);

                }

                StringUTF16.putChar(dst, dp++, REPL);

                break;

            } else if ((b1 >> 3) == -2) {

                if (sp + 2 < sl) {

                    int b2 = src[sp++];

                    int b3 = src[sp++];

                    int b4 = src[sp++];

                    int uc = decode4(b1, b2, b3, b4);

                    if (isMalformed4(b2, b3, b4) ||

                            !Character.isSupplementaryCodePoint(uc)) { // shortest form check

                        if (!doReplace) {

                            throwMalformed(sp - 4, 4);

                        }

                        StringUTF16.putChar(dst, dp++, REPL);

                        sp -= 4;

                        sp += malformed4(src, sp);

                    } else {

                        StringUTF16.putChar(dst, dp++, Character.highSurrogate(uc));

                        StringUTF16.putChar(dst, dp++, Character.lowSurrogate(uc));

                    }

                    continue;

                }

                b1 &= 0xff;

                if (b1 > 0xf4 || sp < sl && isMalformed4_2(b1, src[sp] & 0xff)) {

                    if (!doReplace) {

                        throwMalformed(sp - 1, 1);  // or 2

                    }

                    StringUTF16.putChar(dst, dp++, REPL);

                    continue;

                }

                if (!doReplace) {

                    throwMalformed(sp - 1, 1);

                }

                sp++;

                StringUTF16.putChar(dst, dp++, REPL);

                if (sp < sl && isMalformed4_3(src[sp])) {

                    continue;

                }

                break;

            } else {

                if (!doReplace) {

                    throwMalformed(sp - 1, 1);

                }

                StringUTF16.putChar(dst, dp++, REPL);

            }

        }

        return dp;

    }

    private static int decodeWithDecoder(CharsetDecoder cd, char[] dst, byte[] src, int offset, int length) {

        ByteBuffer bb = ByteBuffer.wrap(src, offset, length);

        CharBuffer cb = CharBuffer.wrap(dst, 0, dst.length);

        try {

            CoderResult cr = cd.decode(bb, cb, true);

            if (!cr.isUnderflow())

                cr.throwException();

            cr = cd.flush(cb);

            if (!cr.isUnderflow())

                cr.throwException();

        } catch (CharacterCodingException x) {

            // Substitution is always enabled,

            // so this shouldn't happen

            throw new Error(x);

        }

        return cb.position();

    }

    private static int malformed3(byte[] src, int sp) {

        int b1 = src[sp++];

        int b2 = src[sp];    // no need to lookup b3

        return ((b1 == (byte)0xe0 && (b2 & 0xe0) == 0x80) ||

                isNotContinuation(b2)) ? 1 : 2;

    }

    private static int malformed4(byte[] src, int sp) {

        // we don't care the speed here

        int b1 = src[sp++] & 0xff;

        int b2 = src[sp++] & 0xff;

        if (b1 > 0xf4 ||

                (b1 == 0xf0 && (b2 < 0x90 || b2 > 0xbf)) ||

                (b1 == 0xf4 && (b2 & 0xf0) != 0x80) ||

                isNotContinuation(b2))

            return 1;

        if (isNotContinuation(src[sp]))

            return 2;

        return 3;

    }

    private static void throwMalformed(int off, int nb) {

        String msg = "malformed input off : " + off + ", length : " + nb;

        throw new IllegalArgumentException(msg, new MalformedInputException(nb));

    }

    private static void throwMalformed(byte[] val) {

        int dp = 0;

        while (dp < val.length && val[dp] >=0) { dp++; }

        throwMalformed(dp, 1);

    }

    private static void throwUnmappable(int off) {

        String msg = "malformed input off : " + off + ", length : 1";

        throw new IllegalArgumentException(msg, new UnmappableCharacterException(1));

    }

    private static void throwUnmappable(byte[] val) {

        int dp = 0;

        while (dp < val.length && val[dp] >=0) { dp++; }

        throwUnmappable(dp);

    }

    private static byte[] encodeUTF8(byte coder, byte[] val, boolean doReplace) {

        if (coder == UTF16)

            return encodeUTF8_UTF16(val, doReplace);

        if (!StringCoding.hasNegatives(val, 0, val.length))

            return Arrays.copyOf(val, val.length);

        int dp = 0;

        byte[] dst = new byte[val.length << 1];

        for (byte c : val) {

            if (c < 0) {

                dst[dp++] = (byte) (0xc0 | ((c & 0xff) >> 6));

                dst[dp++] = (byte) (0x80 | (c & 0x3f));

            } else {

                dst[dp++] = c;

            }

        }

        if (dp == dst.length)

            return dst;

        return Arrays.copyOf(dst, dp);

    }