//

// 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 <algorithm>

#include <cstring>

#include <initializer_list>

#include <iosfwd>

#include <iterator>

#include <limits>

#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.

    @note `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

        <a href="https://en.cppreference.com/w/cpp/named_req/ContiguousContainer"><em>ContiguousContainer</em></a>,

        <a href="https://en.cppreference.com/w/cpp/named_req/ReversibleContainer"><em>ReversibleContainer</em></a>, and

        <a href="https://en.cppreference.com/w/cpp/named_req/SequenceContainer"><em>SequenceContainer</em></a>.

*/

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:

    /** The type of _Allocator_ returned by @ref get_allocator

        This type is a @ref polymorphic_allocator.

    */

#ifdef BOOST_JSON_DOCS

    // VFALCO doc toolchain renders this incorrectly

    using allocator_type = __see_below__;

#else

    using allocator_type = polymorphic_allocator<value>;

#endif

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

    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>::value_type,

            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

    //

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

    /** Default constructor.

        The string will have a zero size and a non-zero,

        unspecified capacity, using the [default memory resource].

        @par Complexity

        Constant.

        [default memory resource]: json/allocators/storage_ptr.html#json.allocators.storage_ptr.default_memory_resource

    */

    string() = default;

    /** Pilfer constructor.

        The string is constructed by acquiring 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.

        @par Complexity

        Constant.

        @par Exception Safety

        No-throw guarantee.

        @param other The value to pilfer. After pilfer

        construction, `other` is not in a usable state

        and may only be destroyed.

        @see @ref pilfer,

            <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0308r0.html">

                Valueless Variants Considered Harmful</a>

    */

    string(pilfered<string> other) noexcept

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

        , impl_(other.get().impl_)

    {

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

    }

    /** Constructor.

        The string will have zero size and a non-zero,

        unspecified capacity, obtained from the specified

        memory resource.

        @par Complexity

        Constant.

        @param sp A pointer to the @ref memory_resource

        to use. The container will acquire shared

        ownership of the memory resource.

    */

    explicit

    string(storage_ptr sp)

        : sp_(std::move(sp))

    {

    }

    /** Constructor.

        Construct the contents with `count` copies of

        character `ch`.

        @par Complexity

        Linear in `count`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @param count The size of the resulting string.

        @param ch The value to initialize characters

        of the string with.

        @param sp An optional pointer to the @ref memory_resource

        to use. The container will acquire shared

        ownership of the memory resource.

        The default argument for this parameter is `{}`.

        @throw system_error `count > max_size()`.

    */

    BOOST_JSON_DECL

    explicit

    string(

        std::size_t count,

        char ch,

        storage_ptr sp = {});

    /** Constructor.

        Construct the contents with those of the null

        terminated string pointed to by `s`. The length

        of the string is determined by the first null

        character.

        @par Complexity

        Linear in `strlen(s)`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @param s A pointer to a character string used to

        copy from.

        @param sp An optional pointer to the @ref memory_resource

        to use. The container will acquire shared

        ownership of the memory resource.

        The default argument for this parameter is `{}`.

        @throw system_error `strlen(s) > max_size()`.

    */

    BOOST_JSON_DECL

    string(

        char const* s,

        storage_ptr sp = {});

    /** Constructor.

        Construct the contents with copies of the

        characters in the range `{s, s+count)`.

        This range can contain null characters.

        @par Complexity

        Linear in `count`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @param count The number of characters to copy.

        @param s A pointer to a character string used to

        copy from.

        @param sp An optional pointer to the @ref memory_resource

        to use. The container will acquire shared

        ownership of the memory resource.

        The default argument for this parameter is `{}`.

        @throw system_error `count > max_size()`.

    */

    BOOST_JSON_DECL

    explicit

    string(

        char const* s,

        std::size_t count,

        storage_ptr sp = {});

    /** Constructor.

        Construct the contents with copies of characters

        in the range `{first, last)`.

        @par Complexity

        Linear in `std::distance(first, last)`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @tparam InputIt The type of the iterators.

        @par Constraints

        `InputIt` satisfies __InputIterator__.

        @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 An optional pointer to the @ref memory_resource

        to use. The container will acquire shared

        ownership of the memory resource.

        The default argument for this parameter is `{}`.

        @throw system_error `std::distance(first, last) > max_size()`.

    */

    template<class InputIt

    #ifndef BOOST_JSON_DOCS

        ,class = is_inputit<InputIt>

    #endif

    >

    explicit

    string(

        InputIt first,

        InputIt last,

        storage_ptr sp = {});

    /** Copy constructor.

        Construct the contents with a copy of `other`.

        @par Complexity

        Linear in `other.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @param other The string to use as a source

        to copy from.

    */

    BOOST_JSON_DECL

    string(string const& other);

    /** Constructor.

        Construct the contents with a copy of `other`.

        @par Complexity

        Linear in `other.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @param other The string to use as a source

        to copy from.

        @param sp An optional pointer to the @ref memory_resource

        to use. The container will acquire shared

        ownership of the memory resource.

        The default argument for this parameter is `{}`.

    */

    BOOST_JSON_DECL

    explicit

    string(

        string const& other,

        storage_ptr sp);

    /** Move constructor.

        Constructs the string with the contents of `other`

        using move semantics. Ownership of the underlying

        memory is transferred.

        The container acquires shared ownership of the

        @ref memory_resource used by `other`. After construction,

        the moved-from string behaves as if newly

        constructed with its current memory resource.

        @par Complexity

        Constant.

        @param other The string to move

    */

    string(string&& other) noexcept

        : sp_(other.sp_)

        , impl_(other.impl_)

    {

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

    }

    /** Constructor.

        Construct the contents with those of `other`

        using move semantics.

        @li If `*other.storage() == *sp`,

        ownership of the underlying memory is transferred

        in constant time, with no possibility

        of exceptions. After construction, the moved-from

        string behaves as if newly constructed with

        its current @ref memory_resource. Otherwise,

        @li If `*other.storage() != *sp`,

        a copy of the characters in `other` is made. In

        this case, the moved-from string is not changed.

        @par Complexity

        Constant or linear in `other.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @param other The string to assign from.

        @param sp An optional pointer to the @ref memory_resource

        to use. The container will acquire shared

        ownership of the memory resource.

        The default argument for this parameter is `{}`.

    */

    BOOST_JSON_DECL

    explicit

    string(

        string&& other,

        storage_ptr sp);

    /** Constructor.

        Construct the contents with those of a

        string view. This view can contain

        null characters.

        @par Complexity

        Linear in `s.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @param s The string view to copy from.

        @param sp An optional pointer to the @ref memory_resource

        to use. The container will acquire shared

        ownership of the memory resource.

        The default argument for this parameter is `{}`.

        @throw system_error `s.size() > max_size()`.

    */

    BOOST_JSON_DECL

    string(

        string_view s,

        storage_ptr sp = {});

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

    //

    // Assignment

    //

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

    /** Copy assignment.

        Replace the contents with a copy of `other`.

        @par Complexity

        Linear in `other.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param other The string to use as a source

        to copy from.

    */

    BOOST_JSON_DECL

    string&

    operator=(string const& other);

    /** Move assignment.

        Replace the contents with those of `other`

        using move semantics.

        @li If `&other == this`, do nothing. Otherwise,

        @li If `*other.storage() == *this->storage()`,

        ownership of the underlying memory is transferred

        in constant time, with no possibility

        of exceptions. After construction, the moved-from

        string behaves as if newly constructed with its

        current @ref memory_resource. Otherwise,

        @li a copy of the characters in `other` is made. In

        this case, the moved-from container is not changed.

        @par Complexity

        Constant or linear in `other.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param other The string to use as a source

        to move from.

    */

    BOOST_JSON_DECL

    string&

    operator=(string&& other);

    /** Assign a value to the string.

        Replaces the contents with those of the null

        terminated string pointed to by `s`. The length

        of the string is determined by the first null

        character.

        @par Complexity

        Linear in `std::strlen(s)`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param s The null-terminated character string.

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

    */

    BOOST_JSON_DECL

    string&

    operator=(char const* s);

    /** Assign a value to the string.

        Replaces the contents with those of a

        string view. This view can contain

        null characters.

        @par Complexity

        Linear in `s.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param s The string view to copy from.

        @throw system_error `s.size() > max_size()`.

    */

    BOOST_JSON_DECL

    string&

    operator=(string_view s);

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

    /** Assign characters to a string.

        Replace the contents with `count` copies of

        character `ch`.

        @par Complexity

        Linear in `count`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param count The size of the resulting string.

        @param ch The value to initialize characters

        of the string with.

        @throw system_error `count > max_size()`.

    */

    BOOST_JSON_DECL

    string&

    assign(

        std::size_t count,

        char ch);

    /** Assign characters to a string.

        Replace the contents with a copy of `other`.

        @par Complexity

        Linear in `other.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param other The string to use as a source

        to copy from.

    */

    BOOST_JSON_DECL

    string&

    assign(

        string const& other);

    /** Assign characters to a string.

        Replace the contents with those of `other`

        using move semantics.

        @li If `&other == this`, do nothing. Otherwise,

        @li If `*other.storage() == *this->storage()`,

        ownership of the underlying memory is transferred

        in constant time, with no possibility of

        exceptions. After construction, the moved-from

        string behaves as if newly constructed with

        its current  @ref memory_resource, otherwise

        @li If `*other.storage() != *this->storage()`,

        a copy of the characters in `other` is made.

        In this case, the moved-from container

        is not changed.

        @par Complexity

        Constant or linear in `other.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param other The string to assign from.

    */

    BOOST_JSON_DECL

    string&

    assign(string&& other);

    /** Assign characters to a string.

        Replaces the contents with copies of the

        characters in the range `{s, s+count)`. This

        range can contain null characters.

        @par Complexity

        Linear in `count`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param count The number of characters to copy.

        @param s A pointer to a character string used to

        copy from.

        @throw system_error `count > max_size()`.

    */

    BOOST_JSON_DECL

    string&

    assign(

        char const* s,

        std::size_t count);

    /** Assign characters to a string.

        Replaces the contents with those of the null

        terminated string pointed to by `s`. The length

        of the string is determined by the first null

        character.

        @par Complexity

        Linear in `strlen(s)`.

        @par Exception Safety

        Strong guarantee.

        @note

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param s A pointer to a character string used to

        copy from.

        @throw system_error `strlen(s) > max_size()`.

    */

    BOOST_JSON_DECL

    string&

    assign(

        char const* s);

    /** Assign characters to a string.

        Replaces the contents with copies of characters

        in the range `{first, last)`.

        @par Complexity

        Linear in `std::distance(first, last)`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @tparam InputIt The type of the iterators.

        @par Constraints

        `InputIt` satisfies __InputIterator__.

        @return `*this`

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

        @throw system_error `std::distance(first, last) > max_size()`.

    */

    template<class InputIt

    #ifndef BOOST_JSON_DOCS

        ,class = is_inputit<InputIt>

    #endif

    >

    string&

    assign(

        InputIt first,

        InputIt last);

    /** Assign characters to a string.

        Replaces the contents with those of a

        string view. This view can contain

        null characters.

        @par Complexity

        Linear in `s.size()`.

        @par Exception Safety

        Strong guarantee.

        Calls to `memory_resource::allocate` may throw.

        @return `*this`

        @param s The string view to copy from.

        @throw system_error `s.size() > max_size()`.

    */

    string&

    assign(string_view s)

    {

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

    }

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

    /** Return the associated @ref memory_resource

        This returns the @ref 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 @ref memory_resource

        This function returns an instance of

        @ref polymorphic_allocator constructed from the

        associated @ref 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 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.

        @throw system_error `pos >= size()`

    */

    /** @{ */

    char&

    at(std::size_t pos)

    {

        auto const& self = *this;

        return const_cast< char& >( self.at(pos) );

    }

    char const&

    at(std::size_t pos) const

    {

        if(pos >= size())

        {

            BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;

            detail::throw_system_error( error::out_of_range, &loc );

        }

        return impl_.data()[pos];

    }

    /** @} */

    /** Return a character without bounds checking.

        Returns a reference to the character specified at

        location `pos`.

        @par Complexity

        Constant.

        @par Precondition

        @code

        pos >= size

        @endcode

        @param pos A zero-based index to access.

    */

    char&

    operator[](std::size_t pos)

    {

        return impl_.data()[pos];

    }

   /**  Return a character without bounds checking.

        Returns a reference to the character specified at

        location `pos`.

        @par Complexity

        Constant.

        @par Precondition

        @code

        pos >= size

        @endcode

        @param pos A zero-based index to access.

    */

    const char&

    operator[](std::size_t pos) const

    {

        return impl_.data()[pos];

    }

    /** Return the first character.

        Returns a reference to the first character.

        @par Complexity

        Constant.

        @par Precondition

        @code

        not empty()

        @endcode

    */

    char&

    front()

    {

        return impl_.data()[0];

    }

    /** Return the first character.

        Returns a reference to the first character.

        @par Complexity

        Constant.

        @par Precondition

        @code

        not empty()

        @endcode

    */

    char const&

    front() const

    {

        return impl_.data()[0];

    }

    /** Return the last character.

        Returns a reference to the last character.

        @par Complexity

        Constant.

        @par Precondition

        @code

        not empty()

        @endcode

    */

    char&

    back()

    {

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

    }

    /** Return the last character.

        Returns a reference to the last character.

        @par Complexity

        Constant.

        @par Precondition

        @code

        not empty()

        @endcode

    */

    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.

        @par Complexity

        Constant.

        @note The value returned from

        this function is never equal to `nullptr`.

    */

    char*

    data() noexcept

    {

        return impl_.data();

    }

    /** Return the underlying character array directly.

        Returns a pointer to the underlying array

        serving as storage.

        @note The value returned is such that

        the range `{data(), data() + size())` is always a

        valid range, even if the container is empty.

        The value returned from

        this function is never equal to `nullptr`.

        @par Complexity

        Constant.

    */

    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.

        @par Complexity

        Constant.

        @note The value returned from

        this function is never equal to `nullptr`.

    */

    char const*

    c_str() const noexcept

    {

        return impl_.data();

    }

    /** Convert to a `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 a `std::string_view` referring to the string.

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