StringView.h#

// Copyright (c) 2020-2024, NVIDIA CORPORATION. All rights reserved.
//
// NVIDIA CORPORATION and its licensors retain all intellectual property
// and proprietary rights in and to this software, related documentation
// and any modifications thereto. Any use, reproduction, disclosure or
// distribution of this software and related documentation without an express
// license agreement from NVIDIA CORPORATION is strictly prohibited.
//

#pragma once

#include "../Defines.h"

#include "../../omni/detail/PointerIterator.h"
#include "detail/CharTraits.h"
#include "TypeTraits.h"

#include <cstddef>
#include <iterator>
#include <string> // for std::string and std::hash
#include <stdexcept>
#include <type_traits>
#include <utility>

namespace carb
{
namespace cpp
{

template <class CharT, class Traits>
class basic_string_view;

namespace detail
{

template <class T>
struct IsBasicStringView : public std::false_type
{
};

template <class T, class Traits>
struct IsBasicStringView<basic_string_view<T, Traits>> : public std::true_type
{
};

template <class T, class OpType, class = void>
struct HasOperator : public std::false_type
{
};

template <class T, class OpType>
struct HasOperator<T, OpType, void_t<decltype(std::declval<T>().operator OpType())>> : public std::true_type
{
};

template <class T>
struct IsReverseIterator : public std::false_type
{
};

template <class It>
struct IsReverseIterator<std::reverse_iterator<It>> : public std::true_type
{
};

// GCC instantiates some functions always so they cannot use static_assert, but throwing an exception is allowed from a
// constexpr function (which will act as a compile failure if constexpr) so fall back to that.
#if CARB_EXCEPTIONS_ENABLED
#    define CARB_ALWAYS_FAIL(msg) throw std::out_of_range(msg)
#    define CARB_THROW_OR_CHECK(check, msg)                                                                            \
        if (!CARB_LIKELY(check))                                                                                       \
        throw std::out_of_range(msg)
#else
#    define CARB_THROW_OR_CHECK(check, msg) CARB_CHECK((check), msg)
#    if CARB_COMPILER_MSC
#        define CARB_ALWAYS_FAIL(msg) static_assert(false, msg)
#    else
#        define CARB_ALWAYS_FAIL(msg) CARB_FATAL_UNLESS(false, msg)
#    endif
#endif

} // namespace detail

template <class CharT, class Traits = ::carb::cpp::char_traits<CharT>>
class CARB_VIZ basic_string_view
{
    static_assert(!std::is_array<CharT>::value, "CharT must not be an array type");
    static_assert(std::is_trivial<CharT>::value && std::is_standard_layout<CharT>::value,
                  "CharT must be trivial and standard layout");
    static_assert(std::is_same<CharT, typename Traits::char_type>::value, "CharT and Traits::char_type must be the same");

public:
    using traits_type = Traits;
    using value_type = CharT;
    using pointer = CharT*;
    using const_pointer = const CharT*;
    using reference = CharT&;
    using const_reference = const CharT&;
    using const_iterator = omni::detail::PointerIterator<const_pointer, basic_string_view>;
    using iterator = const_iterator;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    using reverse_iterator = const_reverse_iterator;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;

    static constexpr size_type npos = size_type(-1);

    constexpr basic_string_view() noexcept = default;

    constexpr basic_string_view(const basic_string_view& other) noexcept = default;

    constexpr basic_string_view(const CharT* s, size_type count) : m_data(s), m_count(count)
    {
    }

    template <size_t N>
    constexpr basic_string_view(const CharT (&s)[N]) noexcept : m_data(s), m_count(traits_type::length(s))
    {
    }

    template <class T,
              std::enable_if_t<!is_bounded_array_v<remove_cvref_t<T>> && std::is_convertible<T, const_pointer>::value, bool> = false>
    constexpr basic_string_view(T&& s) : m_data(s), m_count(traits_type::length(s))
    {
    }

    template <class It CARB_NO_DOC(
        ,
        std::enable_if_t<std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
                             !detail::IsReverseIterator<It>::value,
                         bool> = false)>
    constexpr basic_string_view(It first, It last) : m_data(std::addressof(*first)), m_count(std::distance(first, last))
    {
    }

    template <class R CARB_NO_DOC(
        ,
        std::enable_if_t<
            cpp::detail::IsConvertibleRange<remove_cvref_t<R>, const_pointer>::value &&
                !detail::IsBasicStringView<remove_cvref_t<R>>::value && !is_bounded_array_v<remove_cvref_t<R>> &&
                !std::is_same<std::basic_string<CharT, Traits, typename std::decay_t<R>::allocator_type>, std::decay_t<R>>::value &&
                !std::is_convertible<R, const CharT*>::value && !detail::HasOperator<remove_cvref_t<R>, basic_string_view>::value,
            bool> = false)>
    constexpr explicit basic_string_view(R&& r) : m_data(r.data()), m_count(r.size())
    {
    }

    template <typename Traits_, typename Alloc_>
    constexpr basic_string_view(const std::basic_string<CharT, Traits_, Alloc_>& s)
        : m_data(s.data()), m_count(s.size())
    {
    }

    constexpr basic_string_view(std::nullptr_t) = delete;

    constexpr basic_string_view& operator=(const basic_string_view& view) noexcept = default;

    constexpr const_iterator begin() const noexcept
    {
        return const_iterator(m_data);
    }

    constexpr const_iterator cbegin() const noexcept
    {
        return const_iterator(m_data);
    }

    constexpr const_iterator end() const noexcept
    {
        return const_iterator(m_data + m_count);
    }

    constexpr const_iterator cend() const noexcept
    {
        return const_iterator(m_data + m_count);
    }

    constexpr const_reverse_iterator rbegin() const noexcept
    {
        return const_reverse_iterator(end());
    }

    constexpr const_reverse_iterator crbegin() const noexcept
    {
        return const_reverse_iterator(cend());
    }

    constexpr const_reverse_iterator rend() const noexcept
    {
        return const_reverse_iterator(begin());
    }

    constexpr const_reverse_iterator crend() const noexcept
    {
        return const_reverse_iterator(cbegin());
    }

    constexpr const_reference operator[](size_type pos) const noexcept /*strengthened*/
    {
        // Though the standard says no bounds checking we do assert
        CARB_ASSERT(pos < m_count);
        return m_data[pos];
    }

    constexpr const_reference at(size_type pos) const
    {
        CARB_THROW_OR_CHECK(pos < m_count, "pos >= size()");
        return m_data[pos];
    }

    constexpr const_reference front() const noexcept /*strengthened*/
    {
        CARB_ASSERT(!empty(), "Undefined since empty()");
        return *m_data;
    }

    constexpr const_reference back() const noexcept /*strengthened*/
    {
        CARB_ASSERT(!empty(), "Undefined since empty()");
        return m_data[m_count - 1];
    }

    constexpr const_pointer data() const noexcept
    {
        return m_data;
    }

    constexpr size_type size() const noexcept
    {
        return m_count;
    }

    constexpr size_type length() const noexcept
    {
        return m_count;
    }

    constexpr size_type max_size() const noexcept
    {
        return npos - 1;
    }

    CARB_NODISCARD constexpr bool empty() const noexcept
    {
        return m_count == 0;
    }

    constexpr void remove_prefix(size_type n) noexcept /*strengthened*/
    {
        CARB_ASSERT(n <= size(), "Undefined since n > size()");
        m_data += n;
        m_count -= n;
    }

    constexpr void remove_suffix(size_type n) noexcept /*strengthened*/
    {
        CARB_ASSERT(n <= size(), "Undefined since n > size()");
        m_count = m_count - n;
    }

    constexpr void swap(basic_string_view& v) noexcept
    {
        std::swap(m_data, v.m_data);
        std::swap(m_count, v.m_count);
    }

    constexpr size_type copy(CharT* dest, size_type count, size_type pos = 0) const
    {
        CARB_THROW_OR_CHECK(pos <= size(), "pos > size()");
        size_type rcount = ::carb_min(count, size() - pos);
        Traits::copy(dest, m_data + pos, rcount);
        return rcount;
    }

    constexpr basic_string_view substr(size_t pos, size_t count = npos) const
    {
        CARB_THROW_OR_CHECK(pos <= size(), "pos > size()");
        size_t rcount = ::carb_min(count, size() - pos);
        return { m_data + pos, rcount };
    }

    constexpr int compare(basic_string_view v) const noexcept
    {
        size_type rlen = ::carb_min(size(), v.size());
        int result = traits_type::compare(data(), v.data(), rlen);
        if (result != 0 || size() == v.size())
            return result;
        return (size() < v.size()) ? -1 : 1;
    }

    constexpr int compare(size_type pos1, size_type count1, basic_string_view v) const
    {
        return substr(pos1, count1).compare(v);
    }

    constexpr int compare(size_type pos1, size_type count1, basic_string_view v, size_type pos2, size_type count2) const
    {
        return substr(pos1, count1).compare(v.substr(pos2, count2));
    }

    constexpr int compare(const CharT* s) const
    {
        return compare(basic_string_view(s));
    }

    constexpr int compare(size_type pos1, size_type count1, const CharT* s) const
    {
        return substr(pos1, count1).compare(basic_string_view(s));
    }

    constexpr int compare(size_type pos1, size_type count1, const CharT* s, size_type count2) const
    {
        return substr(pos1, count1).compare(basic_string_view(s, count2));
    }

    constexpr bool starts_with(basic_string_view sv) const noexcept
    {
        return substr(0, sv.size()) == sv;
    }

    constexpr bool starts_with(CharT ch) const noexcept
    {
        return !empty() && traits_type::eq(front(), ch);
    }

    constexpr bool starts_with(const CharT* s) const
    {
        return starts_with(basic_string_view(s));
    }

    constexpr bool ends_with(basic_string_view sv) const noexcept
    {
        return size() >= sv.size() && compare(size() - sv.size(), npos, sv) == 0;
    }

    constexpr bool ends_with(CharT ch) const noexcept
    {
        return !empty() && traits_type::eq(back(), ch);
    }

    constexpr bool ends_with(const CharT* s) const
    {
        return ends_with(basic_string_view(s));
    }

    constexpr bool contains(basic_string_view sv) const noexcept
    {
        return find(sv) != npos;
    }

    constexpr bool contains(CharT c) const noexcept
    {
        return find(c) != npos;
    }

    constexpr bool contains(const CharT* s) const
    {
        return find(s) != npos;
    }

    constexpr size_type find(basic_string_view v, size_type pos = 0) const noexcept
    {
        // [strings.view.find] in the Standard.
        size_type xpos = pos;

        while (xpos + v.size() <= size())
        {
            if (traits_type::compare(v.data(), data() + xpos, v.size()) == 0)
            {
                return xpos;
            }
            xpos++;
        }
        return npos;
    }

    constexpr size_type find(CharT ch, size_type pos = 0) const noexcept
    {
        size_type xpos = pos;

        while (xpos < size())
        {
            if (traits_type::eq(data()[xpos], ch))
            {
                return xpos;
            }
            xpos++;
        }
        return npos;
    }

    constexpr size_type find(const CharT* s, size_type pos, size_type count) const
    {
        return find(basic_string_view(s, count), pos);
    }

    constexpr size_type find(const CharT* s, size_type pos = 0) const
    {
        return find(basic_string_view(s), pos);
    }

    constexpr size_type rfind(basic_string_view v, size_type pos = npos) const noexcept
    {
        if (v.size() > size())
        {
            return npos;
        }

        // Clip the position to our string length.
        for (size_type xpos = ::carb_min(pos, size() - v.size());; xpos--)
        {
            if (traits_type::compare(v.data(), data() + xpos, v.size()) == 0)
            {
                return xpos;
            }
            if (xpos == 0)
            {
                break;
            }
        }
        return npos;
    }

    constexpr size_type rfind(CharT ch, size_type pos = npos) const noexcept
    {
        if (empty())
        {
            return npos;
        }

        // Clip the position to our string length.
        for (size_type xpos = ::carb_min(pos, size() - 1);; xpos--)
        {
            if (traits_type::eq(ch, data()[xpos]))
            {
                return xpos;
            }
            if (xpos == 0)
            {
                break;
            }
        }
        return npos;
    }

    constexpr size_type rfind(const CharT* s, size_type pos, size_type count) const
    {
        return rfind(basic_string_view(s, count), pos);
    }

    constexpr size_type rfind(const CharT* s, size_type pos = npos) const
    {
        return rfind(basic_string_view(s), pos);
    }

    constexpr size_type find_first_of(basic_string_view v, size_type pos = 0) const noexcept
    {
        if (v.empty())
        {
            return npos;
        }
        size_type xpos = pos;

        while (xpos < size())
        {
            if (v.find(m_data[xpos]) != npos)
            {
                return xpos;
            }
            xpos++;
        }
        return npos;
    }

    constexpr size_type find_first_of(CharT ch, size_type pos = 0) const noexcept
    {
        return find(ch, pos);
    }

    constexpr size_type find_first_of(const CharT* s, size_type pos, size_type count) const
    {
        return find_first_of(basic_string_view(s, count), pos);
    }

    constexpr size_type find_first_of(const CharT* s, size_type pos = 0) const
    {
        return find_first_of(basic_string_view(s), pos);
    }

    constexpr size_type find_last_of(basic_string_view v, size_type pos = npos) const noexcept
    {
        if (v.empty() || empty())
        {
            return npos;
        }

        // Clip the position to our string length.
        for (size_type xpos = ::carb_min(pos, size() - 1);; xpos--)
        {
            if (v.find(data()[xpos]) != npos)
            {
                return xpos;
            }
            if (xpos == 0)
            {
                break;
            }
        }
        return npos;
    }

    constexpr size_type find_last_of(CharT ch, size_type pos = npos) const noexcept
    {
        return rfind(ch, pos);
    }

    constexpr size_type find_last_of(const CharT* s, size_type pos, size_type count) const
    {
        return find_last_of(basic_string_view(s, count), pos);
    }

    constexpr size_type find_last_of(const CharT* s, size_type pos = npos) const
    {
        return find_last_of(basic_string_view(s), pos);
    }

    constexpr size_type find_first_not_of(basic_string_view v, size_type pos = 0) const noexcept
    {
        size_type xpos = pos;

        while (xpos < size())
        {
            if (v.find(data()[xpos]) == npos)
            {
                return xpos;
            }
            xpos++;
        }
        return npos;
    }

    constexpr size_type find_first_not_of(CharT ch, size_type pos = 0) const noexcept
    {
        size_type xpos = pos;

        while (xpos < size())
        {
            if (!traits_type::eq(ch, m_data[xpos]))
            {
                return xpos;
            }
            xpos++;
        }
        return npos;
    }

    constexpr size_type find_first_not_of(const CharT* s, size_type pos, size_type count) const
    {
        return find_first_not_of(basic_string_view(s, count), pos);
    }

    constexpr size_type find_first_not_of(const CharT* s, size_type pos = 0) const
    {
        return find_first_not_of(basic_string_view(s), pos);
    }

    constexpr size_type find_last_not_of(basic_string_view v, size_type pos = 0) const noexcept
    {
        if (empty())
        {
            return npos;
        }

        // Clip the position to our string length.
        for (size_type xpos = ::carb_min(pos, size() - 1);; xpos--)
        {
            if (v.find(data()[xpos]) == npos)
            {
                return xpos;
            }
            if (xpos == 0)
            {
                break;
            }
        }
        return npos;
    }

    constexpr size_type find_last_not_of(CharT ch, size_type pos = 0) const noexcept
    {
        if (empty())
        {
            return npos;
        }

        // Clip the position to our string length.
        for (size_type xpos = ::carb_min(pos, size() - 1);; xpos--)
        {
            if (!traits_type::eq(data()[xpos], ch))
            {
                return xpos;
            }
            if (xpos == 0)
            {
                break;
            }
        }
        return npos;
    }

    constexpr size_type find_last_not_of(const CharT* s, size_type pos, size_type count) const
    {
        return find_last_not_of(basic_string_view(s, count), pos);
    }

    constexpr size_type find_last_not_of(const CharT* s, size_type pos = 0) const
    {
        return find_last_not_of(basic_string_view(s), pos);
    }

private:
    CARB_VIZ const_pointer m_data = nullptr;
    CARB_VIZ size_type m_count = 0;
};

using string_view = basic_string_view<char>;
using wstring_view = basic_string_view<wchar_t>;

#if CARB_HAS_CPP20 && defined(__cpp_char8_t)
using u8string_view = basic_string_view<char8_t>;
#endif

using u16string_view = basic_string_view<char16_t>;
using u32string_view = basic_string_view<char32_t>;

// Ensure these for ABI safety
#define CARB_IMPL_ENSURE_ABI(cls)                                                                                      \
    static_assert(std::is_standard_layout<cls>::value, #cls " must be standard layout");                               \
    static_assert(std::is_trivially_copyable<cls>::value, #cls " must be trivially copyable"); /* C++23 requirement */ \
    static_assert(sizeof(cls) == (2 * sizeof(size_t)), #cls "ABI change violation")
CARB_IMPL_ENSURE_ABI(string_view);
CARB_IMPL_ENSURE_ABI(wstring_view);
#if CARB_HAS_CPP20 && defined(__cpp_char8_t)
CARB_IMPL_ENSURE_ABI(u8string_view);
#endif
CARB_IMPL_ENSURE_ABI(u16string_view);
CARB_IMPL_ENSURE_ABI(u32string_view);
#undef CARB_IMPL_ENSURE_ABI

// [string.view.comparison]

// type_identity_t is used to create a non-deduced context so that one argument participates
// in template argument deduction and the other one gets implicitly converted.
// To overcome an MSVC issue with name mangling some overloads have a dummy default parameter.

template <class CharT, class Traits>
constexpr bool operator==(basic_string_view<CharT, Traits> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) == 0;
}

#ifndef DOXYGEN_BUILD

template <class CharT, class Traits, int = 1>
constexpr bool operator==(basic_string_view<CharT, Traits> a, type_identity_t<basic_string_view<CharT, Traits>> b)
{
    return a.compare(b) == 0;
}

#endif

#if !CARB_HAS_CPP20 || defined DOXYGEN_BUILD

template <class CharT, class Traits>
constexpr bool operator!=(basic_string_view<CharT, Traits> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) != 0;
}

template <class CharT, class Traits>
constexpr bool operator<(basic_string_view<CharT, Traits> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) < 0;
}

template <class CharT, class Traits>
constexpr bool operator>(basic_string_view<CharT, Traits> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) > 0;
}

template <class CharT, class Traits>
constexpr bool operator<=(basic_string_view<CharT, Traits> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) <= 0;
}

template <class CharT, class Traits>
constexpr bool operator>=(basic_string_view<CharT, Traits> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) >= 0;
}

#    ifndef DOXYGEN_BUILD

template <class CharT, class Traits, int = 1>
constexpr bool operator!=(basic_string_view<CharT, Traits> a, type_identity_t<basic_string_view<CharT, Traits>> b)
{
    return a.compare(b) != 0;
}

template <class CharT, class Traits, int = 1>
constexpr bool operator<(basic_string_view<CharT, Traits> a, type_identity_t<basic_string_view<CharT, Traits>> b)
{
    return a.compare(b) < 0;
}

template <class CharT, class Traits, int = 1>
constexpr bool operator>(basic_string_view<CharT, Traits> a, type_identity_t<basic_string_view<CharT, Traits>> b)
{
    return a.compare(b) > 0;
}

template <class CharT, class Traits, int = 1>
constexpr bool operator<=(basic_string_view<CharT, Traits> a, type_identity_t<basic_string_view<CharT, Traits>> b)
{
    return a.compare(b) <= 0;
}

template <class CharT, class Traits, int = 1>
constexpr bool operator>=(basic_string_view<CharT, Traits> a, type_identity_t<basic_string_view<CharT, Traits>> b)
{
    return a.compare(b) >= 0;
}

template <class CharT, class Traits, int = 2>
constexpr bool operator==(type_identity_t<basic_string_view<CharT, Traits>> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) == 0;
}

template <class CharT, class Traits, int = 2>
constexpr bool operator!=(type_identity_t<basic_string_view<CharT, Traits>> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) != 0;
}

template <class CharT, class Traits, int = 2>
constexpr bool operator<(type_identity_t<basic_string_view<CharT, Traits>> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) < 0;
}

template <class CharT, class Traits, int = 2>
constexpr bool operator>(type_identity_t<basic_string_view<CharT, Traits>> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) > 0;
}

template <class CharT, class Traits, int = 2>
constexpr bool operator<=(type_identity_t<basic_string_view<CharT, Traits>> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) <= 0;
}

template <class CharT, class Traits, int = 2>
constexpr bool operator>=(type_identity_t<basic_string_view<CharT, Traits>> a, basic_string_view<CharT, Traits> b)
{
    return a.compare(b) >= 0;
}

#    endif

#else

template <class CharT, class Traits>
constexpr auto operator<=>(const basic_string_view<CharT, Traits> a, const basic_string_view<CharT, Traits> b)
{
    return a.compare(b) <=> 0;
}

template <class CharT, class Traits>
constexpr auto operator<=>(const basic_string_view<CharT, Traits> a, type_identity_t<basic_string_view<CharT, Traits>> b)
{
    return a.compare(b) <=> 0;
}

#endif

// Note that literal suffixes that don't start with _ are reserved, in addition we probably don't want to compete with
// the C++17 suffix either.
constexpr string_view operator""_sv(const char* str, std::size_t len) noexcept
{
    return string_view(str, len);
}

// C++ 20 and above have char8_t.
#if CARB_HAS_CPP20 && defined(__cpp_char8_t)
constexpr u8string_view operator""_sv(const char8_t* str, std::size_t len) noexcept
{
    return u8string_view(str, len);
}
#endif

constexpr u16string_view operator""_sv(const char16_t* str, std::size_t len) noexcept
{
    return u16string_view(str, len);
}

constexpr u32string_view operator""_sv(const char32_t* str, std::size_t len) noexcept
{
    return u32string_view(str, len);
}

constexpr wstring_view operator""_sv(const wchar_t* str, std::size_t len) noexcept
{
    return wstring_view(str, len);
}

} // namespace cpp
} // namespace carb

template <class CharT, class Traits>
struct std::hash<carb::cpp::basic_string_view<CharT, Traits>>
{
    size_t operator()(const carb::cpp::basic_string_view<CharT, Traits>& v) const
    {
        return carb::hashBuffer(v.data(), (uintptr_t)(v.data() + v.size()) - (uintptr_t)(v.data()));
    }
};

#undef CARB_ALWAYS_FAIL
#undef CARB_THROW_OR_CHECK