//

// Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)

// Copyright (c) 2020 Krystian Stasiowski (sdkrystian@gmail.com)

//

// Distributed under the Boost Software License, Version 1.0. (See accompanying

// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

//

// Official repository: https://github.com/boostorg/json

//

#ifndef BOOST_JSON_STRING_HPP

#define BOOST_JSON_STRING_HPP

#include <boost/json/detail/config.hpp>

#include <boost/json/pilfer.hpp>

#include <boost/json/storage_ptr.hpp>

#include <boost/json/string_view.hpp>

#include <boost/json/detail/digest.hpp>

#include <boost/json/detail/except.hpp>

#include <boost/json/detail/string_impl.hpp>

#include <boost/json/detail/value.hpp>

#include <boost/system/result.hpp>

#include <cstring>

#include <iosfwd>

#include <iterator>

#include <new>

#include <type_traits>

#include <utility>

namespace boost {

namespace json {

class value;

/** The native type of string values.

    Instances of string store and manipulate sequences of `char` using the

    UTF-8 encoding. The elements of a string are stored contiguously. A pointer

    to any character in a string may be passed to functions that expect

    a pointer to the first element of a null-terminated `char` array. The type

    uses small buffer optimisation to avoid allocations for small strings.

    String iterators are regular `char` pointers.

    @attention `string` member functions do not validate any UTF-8 byte sequences

    passed to them.

    @par Thread Safety

    Non-const member functions may not be called concurrently with any other

    member functions.

    @par Satisfies

        [_ContiguousContainer_](https://en.cppreference.com/w/cpp/named_req/ContiguousContainer),

        [_ReversibleContainer_](https://en.cppreference.com/w/cpp/named_req/ReversibleContainer),

        and {req_SequenceContainer}.

*/

class string

{

    friend class value;

#ifndef BOOST_JSON_DOCS

    // VFALCO doc toolchain shouldn't show this but does

    friend struct detail::access;

#endif

    using string_impl = detail::string_impl;

    inline

    string(

        detail::key_t const&,

        string_view s,

        storage_ptr sp);

    inline

    string(

        detail::key_t const&,

        string_view s1,

        string_view s2,

        storage_ptr sp);

public:

    /// Associated [Allocator](https://en.cppreference.com/w/cpp/named_req/Allocator)

    using allocator_type = container::pmr::polymorphic_allocator<value>;

    /// The type of a character

    using value_type        = char;

    /// The type used to represent unsigned integers

    using size_type         = std::size_t;

    /// The type used to represent signed integers

    using difference_type   = std::ptrdiff_t;

    /// A pointer to an element

    using pointer           = char*;

    /// A const pointer to an element

    using const_pointer     = char const*;

    /// A reference to an element

    using reference         = char&;

    /// A const reference to an element

    using const_reference   = const char&;

    /// A random access iterator to an element

    using iterator          = char*;

    /// A random access const iterator to an element

    using const_iterator    = char const*;

    /// A reverse random access iterator to an element

    using reverse_iterator =

        std::reverse_iterator<iterator>;

    /// A reverse random access const iterator to an element

    using const_reverse_iterator =

        std::reverse_iterator<const_iterator>;

    /** A special index

        Represents the end of the string.

    */

    static constexpr std::size_t npos =

        string_view::npos;

private:

    template<class T>

    using is_inputit = typename std::enable_if<

        std::is_convertible<typename

            std::iterator_traits<T>::reference,

            char>::value>::type;

    storage_ptr sp_; // must come first

    string_impl impl_;

public:

    /** Destructor.

        Any dynamically allocated internal storage is freed.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    ~string() noexcept

    {

        impl_.destroy(sp_);

    }

    //------------------------------------------------------

    //

    // Construction

    //

    //------------------------------------------------------

    /** Constructors.

        Construct a string.

        @li **(1)**, **(2)** the string is empty with a non-zero,

            unspecified capacity.

        @li **(3)** the string is filled with `count` copies of character `ch`.

        @li **(4)** the string will contain a copy of the characters of `s`.

        @li **(5)** the string will contain a copy of the characters of the

            null-terminated string `s`.

        @li **(6)** the string will contain a copy of the characters in the

            range `[s, s + count)`.

        @li **(7)** the string will contain a copy of the characters in the

            range `[first, last)`.

        @li **(8)**, **(9)** the string contains a copy of the characters of

            `other`.

        @li **(10)** the string acquires ownership of the contents of `other`.

        @li **(11)** equivalent to **(10)** if `*sp == *other.storage()`;

            otherwise equivalent to **(9)**.

        @li **(12)** the string is acquires ownership of the contents of

            `other` using pilfer semantics. This is more efficient than move

            construction, when it is known that the moved-from object

            will be immediately destroyed afterwards.

        With **(2)**--**(7)**, **(9)**, **(11)** the constructed string uses

        memory resource of `sp`. With **(8)**, **(10)**, and **(12)** it uses

        `other`'s memory resource. In either case the string will share the

        ownership of the memory resource. With **(1)** it uses the

        \<\<default_memory_resource, default memory resource\>\>.

        After **(10)** `other` behaves as if newly constructed with its

        current storage pointer.

        After **(12)** `other` is not in a usable state and may only be

        destroyed.

        @par Constraints

        `InputIt` satisfies {req_InputIterator}.

        @par Complexity

        @li **(1)**, **(2)**, **(10)**, **(12)** constant.

        @li **(3)** linear in `count`.

        @li **(4)** linear in `s.size()`.

        @li **(5)** linear in `std::strlen(s)`.

        @li **(6)** linear in `count`.

        @li **(7)** linear in `std::distance(first, last)`.

        @li **(8)**, **(9)** linear in `other.size()`.

        @li **(11)** constant if `*sp == *other.storage()`; otherwise linear in

            `other.size()`.

        @par Exception Safety

        @li **(1)**, **(2)**, **(10)**, **(12)** no-throw guarantee.

        @li **(3)**--**(6)**, **(8)**, **(9)**, **(11)**  strong guarantee.

        @li **(7)** strong guarantee if `InputIt` satisfies

        {req_ForwardIterator}, basic guarantee otherwise.

        Calls to `memory_resource::allocate` may throw.

        @throw boost::system::system_error The constructed string's size would

               have exceeded @ref max_size().

        @see @ref pilfer,

            [Valueless Variants Considered Harmful](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0308r0.html).

        @{

    */

    string() = default;

    /** Overload

        @param sp A pointer to the @ref boost::container::pmr::memory_resource

        to use. The container will acquire shared ownership of the memory

        resource.

    */

    explicit

    string(storage_ptr sp)

        : sp_(std::move(sp))

    {

    }

    /** Overload

        @param count The size of the resulting string.

        @param ch The value to initialize characters of the string with.

        @param sp

    */

    BOOST_JSON_DECL

    explicit

    string(

        std::size_t count,

        char ch,

        storage_ptr sp = {});

    /** Overload

        @param s The string to copy from.

        @param sp

    */

    BOOST_JSON_DECL

    string(

        string_view s,

        storage_ptr sp = {});

    /// Overload

    BOOST_JSON_DECL

    string(

        char const* s,

        storage_ptr sp = {});

    /// Overload

    BOOST_JSON_DECL

    explicit

    string(

        char const* s,

        std::size_t count,

        storage_ptr sp = {});

    /** Overload

        @tparam InputIt The type of the iterators.

        @param first An input iterator pointing to the first character to

               insert, or pointing to the end of the range.

        @param last An input iterator pointing to the end of the range.

        @param sp

    */

    template<class InputIt

    #ifndef BOOST_JSON_DOCS

        ,class = is_inputit<InputIt>

    #endif

    >

    explicit

    string(

        InputIt first,

        InputIt last,

        storage_ptr sp = {});

    /** Overload

        @param other The source string.

    */

    BOOST_JSON_DECL

    string(string const& other);

    /// Overload

    BOOST_JSON_DECL

    explicit

    string(

        string const& other,

        storage_ptr sp);

    /// Overload

    string(string&& other) noexcept

        : sp_(other.sp_)

        , impl_(other.impl_)

    {

        ::new(&other.impl_) string_impl();

    }

    /// Overload

    BOOST_JSON_DECL

    explicit

    string(

        string&& other,

        storage_ptr sp);

    /// Overload

    string(pilfered<string> other) noexcept

        : sp_(std::move(other.get().sp_))

        , impl_(other.get().impl_)

    {

        ::new(&other.get().impl_) string_impl();

    }

    /// @}

    //------------------------------------------------------

    //

    // Assignment

    //

    //------------------------------------------------------

    /** Assignment operators.

        @li **(1)**, **(4)** the contents are replaced with an element-wise

            copy of `other`.

        @li **(2)** takes ownership of `other`'s element storage if

            `*storage() == *other.storage()`; otherwise equivalent to **(1)**.

        @li **(3)** the contents are replaced with an element-wise copy of

            null-terminated string `s`.

        After **(2)**, the moved-from array behaves as if newly constructed

        with its current storage pointer.

        @par Complexity

        @li **(1)**, **(4)** linear in `other.size()`.

        @li **(2)** constant if `*storage() == *other.storage()`; otherwise

            linear in `other.size()`.

        @li **(3)** linear in `std::strlen(s)`.

        @par Exception Safety

        {sp} **(2)** provides strong guarantee if

        `*storage() != *other.storage()` and no-throw guarantee otherwise.

        Other overloads provide strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @param other The string to copy.

        @return `*this`

        @{

    */

    BOOST_JSON_DECL

    string&

    operator=(string const& other);

    BOOST_JSON_DECL

    string&

    operator=(string&& other);

    /** Overload

        @param s The null-terminated character string.

        @throw boost::system::system_error `std::strlen(s) >` @ref max_size().

    */

    BOOST_JSON_DECL

    string&

    operator=(char const* s);

    /** Overload

        @throw `boost::system::system_error` `other.size() >` @ref max_size().

    */

    BOOST_JSON_DECL

    string&

    operator=(string_view other);

    /// @}

    /** Assign characters to a string.

        @li **(1)** replaces the contents with `count` copies of character

        `ch`.

        @li **(2)** replaces the contents with copies of the characters in the

        range `[s, s + count)`. This range can contain null characters.

        @li **(3)** replaces the contents with those of the null terminated

        string `s`. The length of the string is determined by the first null

        character.

        @li **(4)** replaces the contents with copies of characters in the

        range `[first, last)`.

        @li **(5)** Replaces the contents with those of string view `s`. This

        view can contain null characters.

        @li **(6)** replaces the contents with a copy of the characters of

        `other`.

        @li **(7)** if `*storage() == *other.storage()` takes ownership of the

        element storage of `other`; otherwise equivalent to **(6)**.

        Self-assignment using **(7)** does nothing.

        After **(7)** `other` is left in valid but unspecified state.

        @par Constraints

        `InputIt` satisfies {req_InputIterator}.

        @par Complexity

        @li **(1)**, **(2)** linear in `count`.

        @li **(3)** linear in `std::strlen(s)`.

        @li **(4)** linear in `std::distance(first, last)`.

        @li **(5)** linear in `s.size()`.

        @li **(6)** linear in `other.size()`.

        @li **(7)** constant if `*storage() == *other.storage()`, otherwise

            linear in `other.size()`.

        @par Exception Safety

        {sp} **(7)** provides strong guarantee if

        `*storage() != *other.storage()` and no-throw guarantee otherwise.

        Other overloads provide strong guarantee. Calls to

        `memory_resource::allocate` may throw.

        @return `*this`.

        @param count The number of the characters to use.

        @param ch The character to fill the string with.

        @throw boost::system::system_error The size of the string after the

        operation would exceed @ref max_size().

        @{

    */

    BOOST_JSON_DECL

    string&

    assign(

        std::size_t count,

        char ch);

    /** Overload

        @param s A pointer to a character string used to copy from.

        @param count

    */

    BOOST_JSON_DECL

    string&

    assign(

        char const* s,

        std::size_t count);

    /** Overload

        @param s

    */

    BOOST_JSON_DECL

    string&

    assign(

        char const* s);

    /** Overload

        @tparam InputIt The type of the iterators.

        @param first An input iterator pointing to the first character to

        insert, or pointing to the end of the range.

        @param last An input iterator pointing to the end of the range.

    */

    template<class InputIt

    #ifndef BOOST_JSON_DOCS

        ,class = is_inputit<InputIt>

    #endif

    >

    string&

    assign(

        InputIt first,

        InputIt last);

    /** Overload

        @param s The string view to copy from.

    */

    string&

    assign(string_view s)

    {

        return assign(s.data(), s.size());

    }

    /** Overload

        @param other Another string.

    */

    BOOST_JSON_DECL

    string&

    assign(

        string const& other);

    /** Overload

        @param other

    */

    BOOST_JSON_DECL

    string&

    assign(string&& other);

    /// @}

    /** Return the associated memory resource.

        This function returns a smart pointer to the

        @ref boost::container::pmr::memory_resource used by the container.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    storage_ptr const&

    storage() const noexcept

    {

        return sp_;

    }

    /** Return the associated allocator.

        This function returns an instance of @ref allocator_type constructed

        from the associated @ref boost::container::pmr::memory_resource.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    allocator_type

    get_allocator() const noexcept

    {

        return sp_.get();

    }

    //------------------------------------------------------

    //

    // Element Access

    //

    //------------------------------------------------------

    /** Return a character with bounds checking.

        Returns @ref boost::system::result containing a reference to the

        character specified at location `pos`, if `pos` is within the range of

        the string. Otherwise the result contains an `error_code`.

        @par Exception Safety

        Strong guarantee.

        @param pos A zero-based index to access.

        @par Complexity

        Constant.

        @{

    */

    BOOST_JSON_DECL

    system::result<char&>

    try_at(std::size_t pos) noexcept;

    BOOST_JSON_DECL

    system::result<char const&>

    try_at(std::size_t pos) const noexcept;

    /// @}

    /** Return a character with bounds checking.

        Returns a reference to the character specified at location `pos`.

        @par Complexity

        Constant.

        @par Exception Safety

        Strong guarantee.

        @param pos A zero-based index to access.

        @param loc `source_location` to use in thrown exception; the source

               location of the call site by default.

        @throw boost::system::system_error `pos >=` @ref size().

        @{

    */

    inline

    char&

    at(

        std::size_t pos,

        source_location const& loc = BOOST_CURRENT_LOCATION);

    BOOST_JSON_DECL

    char const&

    at(

        std::size_t pos,

        source_location const& loc = BOOST_CURRENT_LOCATION) const;

    /// @}

    /** Return a character without bounds checking.

        Returns a reference to the character specified at location `pos`.

        @par Complexity

        Constant.

        @pre

        @code

        pos < size()

        @endcode

        @param pos A zero-based index to access.

        @{

    */

    char&

    operator[](std::size_t pos)

    {

        return impl_.data()[pos];

    }

    const char&

    operator[](std::size_t pos) const

    {

        return impl_.data()[pos];

    }

    /// @}

    /** Return the first character.

        Returns a reference to the first character.

        @pre

        @code

        ! empty()

        @endcode

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

        @{

    */

    char&

    front()

    {

        return impl_.data()[0];

    }

    char const&

    front() const

    {

        return impl_.data()[0];

    }

    /// @}

    /** Return the last character.

        Returns a reference to the last character.

        @pre

        @code

        ! empty()

        @endcode

        @par Complexity

        Constant.

        @{

    */

    char&

    back()

    {

        return impl_.data()[impl_.size() - 1];

    }

    char const&

    back() const

    {

        return impl_.data()[impl_.size() - 1];

    }

    /// @}

    /** Return the underlying character array directly.

        Returns a pointer to the underlying array serving as storage. The value

        returned is such that the range `[data(), data() + size())` is always

        a valid range, even if the container is empty.

        @note The value returned from this function is never equal to

        `nullptr`.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

        @{

    */

    char*

    data() noexcept

    {

        return impl_.data();

    }

    char const*

    data() const noexcept

    {

        return impl_.data();

    }

    /// @@}

    /** Return the underlying character array directly.

        Returns a pointer to the underlying array serving as storage. The value

        returned is such that the range `[c_str(), c_str() + size())` is always

        a valid range, even if the container is empty.

        @note The value returned from this function is never equal to

        `nullptr`.

        @par Complexity

        Constant.

    */

    char const*

    c_str() const noexcept

    {

        return impl_.data();

    }

    /** Convert to a @ref string_view referring to the string.

        Returns a string view to the

        underlying character string. The size of the view

        does not include the null terminator.

        @par Complexity

        Constant.

    */

    operator string_view() const noexcept

    {

        return {data(), size()};

    }

#if ! defined(BOOST_NO_CXX17_HDR_STRING_VIEW)

    /** Convert to @ref std::string_view referring to the string.

        Returns a string view to the underlying character string. The size of

        the view does not include the null terminator.

        This overload is not defined when `BOOST_NO_CXX17_HDR_STRING_VIEW` is

        defined.

        @par Complexity

        Constant.

    */

    operator std::string_view() const noexcept

    {

        return {data(), size()};

    }

#endif

    //------------------------------------------------------

    //

    // Iterators

    //

    //------------------------------------------------------

    /** Return an iterator to the beginning.

        If the container is empty, @ref end() is returned.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

        @{

    */

    iterator

    begin() noexcept

    {

        return impl_.data();

    }

    const_iterator

    begin() const noexcept

    {

        return impl_.data();

    }

    /// @}

    /** Return a const iterator to the first element.

        If the container is empty, @ref cend() is returned.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    const_iterator

    cbegin() const noexcept

    {

        return impl_.data();

    }

    /** Return an iterator to the end.

        The returned iterator only acts as a sentinel. Dereferencing it results

        in undefined behavior.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

        @{

    */

    iterator

    end() noexcept

    {

        return impl_.end();

    }

    const_iterator

    end() const noexcept

    {

        return impl_.end();

    }

    /// @}

    /** Return a const iterator past the last element.

        The returned iterator only acts as a sentinel. Dereferencing it results

        in undefined behavior.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    const_iterator

    cend() const noexcept

    {

        return impl_.end();

    }

    /** Return a reverse iterator to the first character of the reversed container.

        Returns the pointed-to character that corresponds to the last character

        of the non-reversed container. If the container is empty, @ref rend()

        is returned.

        @par Complexity

        Constant.

        @{

    */

    reverse_iterator

    rbegin() noexcept

    {

        return reverse_iterator(impl_.end());

    }

    const_reverse_iterator

    rbegin() const noexcept

    {

        return const_reverse_iterator(impl_.end());

    }

    /// @}

    /** Return a const reverse iterator to the first element of the reversed container.

        Returns the pointed-to character that corresponds to the last character

        of the non-reversed container. If the container is empty, @ref crend()

        is returned.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    const_reverse_iterator

    crbegin() const noexcept

    {

        return const_reverse_iterator(impl_.end());

    }

    /** Return a reverse iterator to the character following the last character of the reversed container.

        The pointed-to element corresponds to the element preceding the first

        element of the non-reversed container. The returned iterator only acts

        as a sentinel. Dereferencing it results in undefined behavior.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

        @{

    */

    reverse_iterator

    rend() noexcept

    {

        return reverse_iterator(begin());

    }

    const_reverse_iterator

    rend() const noexcept

    {

        return const_reverse_iterator(begin());

    }

    /// @}

    /** Return a const reverse iterator to the character following the last character of the reversed container.

        The pointed-to character corresponds to the character preceding the

        first character of the non-reversed container. The returned iterator

        only acts as a sentinel. Dereferencing it results in undefined

        behavior.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    const_reverse_iterator

    crend() const noexcept

    {

        return const_reverse_iterator(begin());

    }

    //------------------------------------------------------

    //

    // Capacity

    //

    //------------------------------------------------------

    /** Check if the string has no characters.

        Returns `true` if there are no characters in the string, i.e. @ref

        size() returns 0.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    bool

    empty() const noexcept

    {

        return impl_.size() == 0;

    }

    /** Return the number of characters in the string.

        The value returned does not include the null terminator, which is

        always present.

        @par Complexity

        Constant.

    */

    std::size_t

    size() const noexcept

    {

        return impl_.size();

    }

    /** Return the maximum number of characters any string can hold.

        The maximum is an implementation-defined number. This value is

        a theoretical limit; at runtime, the actual maximum size may be less

        due to resource limits.

        @par Complexity

        Constant.

    */

    static

    constexpr

    std::size_t

    max_size() noexcept

    {

        return string_impl::max_size();

    }

    /** Return the number of characters that can be held in currently allocated memory.

        Returns the number of characters that the container has currently

        allocated space for. This number is never smaller than the value

        returned by @ref size().

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

    */

    std::size_t

    capacity() const noexcept

    {

        return impl_.capacity();

    }

    /** Increase the capacity to at least a certain amount.

        This increases the capacity of the array to a value that is greater

        than or equal to `new_capacity`. If `new_capacity > `@ref capacity(),

        new memory is allocated. Otherwise, the call has no effect. The number

        of elements and therefore the @ref size() of the container is not

        changed.

        If new memory is allocated, all iterators including any past-the-end

        iterators, and all references to the elements are invalidated.

        Otherwise, no iterators or references are invalidated.

        @par Complexity

        At most, linear in @ref size().

        @par Exception Safety

        Strong guarantee. Calls to `memory_resource::allocate` may throw.

        @param new_capacity The new capacity of the array.

        @throw boost::system::system_error `new_capacity > `@ref max_size().

    */

    void

    reserve(std::size_t new_capacity)

    {

        if(new_capacity <= capacity())

            return;

        reserve_impl(new_capacity);

    }

    /** Request the removal of unused capacity.

        This performs a non-binding request to reduce @ref capacity() to

        @ref size(). The request may or may not be fulfilled.

        @note If reallocation occurs, all iterators including  any past-the-end

        iterators, and all references to characters are invalidated. Otherwise,

        no iterators or references are invalidated.

        @par Complexity

        At most, linear in @ref size().

    */

    BOOST_JSON_DECL

    void

    shrink_to_fit();

    //------------------------------------------------------

    //

    // Operations

    //

    //------------------------------------------------------

    /** Clear the contents.

        Erases all characters from the string. After this call, @ref size()

        returns zero but @ref capacity() is unchanged. All references,

        pointers, or iterators referring to contained elements are invalidated.

        Any past-the-end iterators are also invalidated.

        @par Complexity

        Linear in @ref size().

        @par Exception Safety

        No-throw guarantee.

    */

    BOOST_JSON_DECL

    void

    clear() noexcept;

    /** Insert characters at the specified index.