/*

 * Copyright (c) 1994, 2018, 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.nio.charset.Charset;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Comparator;

import java.util.Formatter;

import java.util.Locale;

import java.util.Objects;

import java.util.Spliterator;

import java.util.StringJoiner;

import java.util.regex.Matcher;

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.HotSpotIntrinsicCandidate;

import jdk.internal.vm.annotation.Stable;

import static java.util.function.Predicate.not;

/**

 * 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&trade; 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&trade; 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 {

    /**

     * 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

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

    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>

     */

    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}

     */

    @HotSpotIntrinsicCandidate

    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 {

        if (charsetName == null)

            throw new NullPointerException("charsetName");

        checkBoundsOffCount(offset, length, bytes.length);

        StringCoding.Result ret =

            StringCoding.decode(charsetName, bytes, offset, length);

        this.value = ret.value;

        this.coder = ret.coder;

    }

    /**

     * 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

     */

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

        if (charset == null)

            throw new NullPointerException("charset");

        checkBoundsOffCount(offset, length, bytes.length);