carb/cpp/Span.h

File members: carb/cpp/Span.h

// Copyright (c) 2023, 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 "TypeTraits.h"
#include "detail/ImplData.h"
#include "StdDef.h"
#include "../../omni/detail/PointerIterator.h"

#include <array>

namespace carb
{
namespace cpp
{

constexpr size_t dynamic_extent = size_t(-1);

template <class T, size_t Extent>
class span;

namespace detail
{

template <class T>
constexpr T* to_address(T* p) noexcept
{
    static_assert(!std::is_function<T>::value, "Ill-formed if T is function type");
    return p;
}

template <class Ptr, std::enable_if_t<std::is_pointer<decltype(std::declval<Ptr>().operator->())>::value, bool> = false>
constexpr auto to_address(const Ptr& p) noexcept
{
    return to_address(p.operator->());
}

template <size_t Extent, size_t Offset, size_t Count>
struct DetermineSubspanExtent
{
    constexpr static size_t value = Count;
};

template <size_t Extent, size_t Offset>
struct DetermineSubspanExtent<Extent, Offset, dynamic_extent>
{
    constexpr static size_t value = Extent - Offset;
};

template <size_t Offset>
struct DetermineSubspanExtent<dynamic_extent, Offset, dynamic_extent>
{
    constexpr static size_t value = dynamic_extent;
};

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

template <class T, size_t N>
struct IsStdArray<std::array<T, N>> : public std::true_type
{
};

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

template <class T, size_t N>
struct IsSpan<span<T, N>> : 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 T, size_t Extent = dynamic_extent>
class span
{
    // NOTE: This implementation is used for Extent != 0 && Extent != dynamic_extent, both of which have specializations
public:
    using element_type = T;
    using value_type = std::remove_cv_t<T>;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;

    using iterator = omni::detail::PointerIterator<pointer, span>;
    using reverse_iterator = std::reverse_iterator<iterator>;

    constexpr static std::size_t extent = Extent;

#ifdef DOXYGEN_BUILD
    constexpr span() noexcept
    {
    }
#endif

    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,
                         bool> = false)>
    constexpr explicit span(It first, size_type count)
    {
        CARB_THROW_OR_CHECK(extent == count, "Behavior is undefined if count != extent");
        m_p = detail::to_address(first);
    }

    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,
                         bool> = false)>
    constexpr explicit span(It first, It last)
    {
        CARB_THROW_OR_CHECK((last - first) == extent, "Behavior is undefined if (last - first) != extent");
        m_p = detail::to_address(first);
    }

    template <std::size_t N>
    constexpr span(type_identity_t<element_type> (&arr)[N]) noexcept
    {
        static_assert(N == extent, "Undefined if N != extent");
        m_p = cpp::data(arr);
    }

    template <class U, std::size_t N CARB_NO_DOC(, std::enable_if_t<std::is_convertible<U, element_type>::value, bool> = false)>
    constexpr span(std::array<U, N>& arr) noexcept
    {
        static_assert(N == extent, "Undefined if N != extent");
        m_p = cpp::data(arr);
    }

    template <class U, std::size_t N CARB_NO_DOC(, std::enable_if_t<std::is_convertible<U, element_type>::value, bool> = false)>
    constexpr span(const std::array<U, N>& arr) noexcept
    {
        static_assert(N == extent, "Undefined if N != extent");
        m_p = cpp::data(arr);
    }

    // template< class R >
    // explicit(extent != dynamic_extent)
    // constexpr span( R&& range );
    // (Constructor not available without ranges, but approximate constructor follows)

    template <class R CARB_NO_DOC(
        ,
        std::enable_if_t<detail::IsConvertibleRange<cpp::remove_cvref_t<R>, pointer>::value &&
                             // These types have a separate constructor
                             !detail::IsStdArray<cpp::remove_cvref_t<R>>::value &&
                             !detail::IsSpan<cpp::remove_cvref_t<R>>::value && !std::is_array<cpp::remove_cvref_t<R>>::value,
                         bool> = false)>
    constexpr explicit span(R&& range)
    {
        CARB_THROW_OR_CHECK(range.size() == extent, "Behavior is undefined if R.size() != extent");
        m_p = range.data();
    }

#ifndef DOXYGEN_BUILD
    template <class U,
              std::size_t N,
              std::enable_if_t<N == dynamic_extent && std::is_convertible<U, element_type>::value, bool> = false>
    constexpr explicit span(const span<U, N>& source) noexcept : m_p(source.data())
    {
        CARB_CHECK(source.size() == extent); // specified as `noexcept` so we cannot throw
    }

    template <class U,
              std::size_t N,
              std::enable_if_t<N != dynamic_extent && std::is_convertible<U, element_type>::value, bool> = false>
#else
    template <class U, std::size_t N>
#endif
    constexpr span(const span<U, N>& source) noexcept : m_p(source.data())
    {
        static_assert(N == extent, "Undefined if N != extent");
    }

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

    constexpr span& operator=(const span& other) noexcept = default;

    constexpr iterator begin() const noexcept
    {
        return iterator(m_p);
    }

    constexpr iterator end() const noexcept
    {
        return iterator(m_p + extent);
    }

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

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

    constexpr reference front() const
    {
        return *m_p;
    }

    constexpr reference back() const
    {
        return m_p[extent - 1];
    }

    constexpr reference operator[](size_type index) const
    {
        CARB_THROW_OR_CHECK(index < extent, "Behavior is undefined when index exceeds size()");
        return m_p[index];
    }

    constexpr pointer data() const noexcept
    {
        return m_p;
    }

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

    constexpr size_type size_bytes() const noexcept
    {
        return sizeof(element_type) * extent;
    }

    CARB_NODISCARD constexpr bool empty() const noexcept
    {
        return false;
    }

    template <std::size_t Count>
    constexpr span<element_type, Count> first() const
    {
        static_assert(Count <= extent, "Program ill-formed if Count > extent");
        return span<element_type, Count>{ m_p, Count };
    }

    constexpr span<element_type, dynamic_extent> first(size_type Count) const
    {
        CARB_THROW_OR_CHECK(Count <= extent, "Program ill-formed if Count > extent");
        return span<element_type, dynamic_extent>{ m_p, Count };
    }

    template <std::size_t Count>
    constexpr span<element_type, Count> last() const
    {
        static_assert(Count <= extent, "Program ill-formed if Count > extent");
        return span<element_type, Count>{ m_p + (extent - Count), Count };
    }

    constexpr span<element_type, dynamic_extent> last(size_type Count) const
    {
        CARB_THROW_OR_CHECK(Count <= extent, "Program ill-formed if Count > extent");
        return span<element_type, dynamic_extent>{ m_p + (extent - Count), Count };
    }

    template <std::size_t Offset, std::size_t Count = dynamic_extent>
    constexpr span<element_type, detail::DetermineSubspanExtent<extent, Offset, Count>::value> subspan() const
    {
        static_assert(Offset <= extent, "Ill-formed");
        static_assert(Count == dynamic_extent || (Offset + Count) <= extent, "Ill-formed");
        return span<element_type, detail::DetermineSubspanExtent<extent, Offset, Count>::value>{
            data() + Offset, carb_min(size() - Offset, Count)
        };
    }

    constexpr span<element_type, dynamic_extent> subspan(size_type Offset, size_type Count = dynamic_extent) const
    {
        CARB_THROW_OR_CHECK(Offset <= extent, "Program ill-formed if Offset > extent");
        CARB_THROW_OR_CHECK(Count == dynamic_extent || (Offset + Count) <= extent,
                            "Program ill-formed if Count is not dynamic_extent and is greater than Extent - Offset");
        return { data() + Offset, carb_min(size() - Offset, Count) };
    }

private:
    pointer m_p;
};

CARB_ASSERT_INTEROP_SAFE(span<int, 1>);

// Doxygen can ignore the specializations
#ifndef DOXYGEN_BUILD
// Specialization for dynamic_extent
template <class T>
class span<T, dynamic_extent>
{
    // NOTE: This specialization is for Extent == dynamic_extent
public:
    using element_type = T;
    using value_type = std::remove_cv_t<T>;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using iterator = omni::detail::PointerIterator<pointer, span>;
    using reverse_iterator = std::reverse_iterator<iterator>;

    constexpr static std::size_t extent = dynamic_extent;

    constexpr span() noexcept : m_p(nullptr), m_size(0)
    {
    }

    template <class It,
              std::enable_if_t<std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value,
                               bool> = false>
    constexpr span(It first, size_type count)
    {
        m_p = detail::to_address(first);
        m_size = count;
    }

    template <class It,
              std::enable_if_t<std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value,
                               bool> = false>
    constexpr span(It first, It last)
    {
        m_p = detail::to_address(first);
        m_size = last - first;
    }

    template <std::size_t N>
    constexpr span(type_identity_t<element_type> (&arr)[N]) noexcept
    {
        m_p = cpp::data(arr);
        m_size = N;
    }

    template <class U, std::size_t N, std::enable_if_t<std::is_convertible<U, element_type>::value, bool> = false>
    constexpr span(std::array<U, N>& arr) noexcept
    {
        m_p = cpp::data(arr);
        m_size = N;
    }

    template <class U, std::size_t N, std::enable_if_t<std::is_convertible<U, element_type>::value, bool> = false>
    constexpr span(const std::array<U, N>& arr) noexcept
    {
        m_p = cpp::data(arr);
        m_size = N;
    }

    // template< class R >
    // explicit(extent != dynamic_extent)
    // constexpr span( R&& range );
    // (Constructor not available without ranges, but approximate constructor follows)

    template <class R,
              std::enable_if_t<detail::IsConvertibleRange<cpp::remove_cvref_t<R>, pointer>::value &&
                                   !detail::IsStdArray<cpp::remove_cvref_t<R>>::value && // has separate constructor
                                   !detail::IsSpan<cpp::remove_cvref_t<R>>::value && // has separate constructor
                                   !std::is_array<cpp::remove_cvref_t<R>>::value, // has separate constructor
                               bool> = false>
    constexpr span(R&& range)
    {
        m_p = range.data();
        m_size = range.size();
    }

    template <class U, std::size_t N, std::enable_if_t<std::is_convertible<U, element_type>::value, bool> = false>
    constexpr span(const span<U, N>& source) noexcept
    {
        m_p = source.data();
        m_size = source.size();
    }

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

    constexpr span& operator=(const span& other) noexcept = default;

    constexpr iterator begin() const noexcept
    {
        return iterator(m_p);
    }

    constexpr iterator end() const noexcept
    {
        return iterator(m_p + m_size);
    }

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

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

    constexpr reference front() const
    {
        CARB_THROW_OR_CHECK(!empty(), "Behavior is undefined when calling front() on an empty span");
        return *m_p;
    }

    constexpr reference back() const
    {
        CARB_THROW_OR_CHECK(!empty(), "Behavior is undefined when calling back() on an empty span");
        return m_p[m_size - 1];
    }

    constexpr reference operator[](size_type index) const
    {
        CARB_THROW_OR_CHECK(index < m_size, "Behavior is undefined when index exceeds size()");
        return m_p[index];
    }

    constexpr pointer data() const noexcept
    {
        return m_p;
    }

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

    constexpr size_type size_bytes() const noexcept
    {
        return sizeof(element_type) * m_size;
    }

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

    template <std::size_t Count>
    constexpr span<element_type, Count> first() const
    {
        CARB_THROW_OR_CHECK(Count <= m_size, "Behavior is undefined when Count > size()");
        return span<element_type, Count>{ m_p, Count };
    }

    constexpr span<element_type, dynamic_extent> first(size_type Count) const
    {
        CARB_THROW_OR_CHECK(Count <= m_size, "Behavior is undefined when Count > size()");
        return span<element_type, dynamic_extent>{ m_p, Count };
    }

    template <std::size_t Count>
    constexpr span<element_type, Count> last() const
    {
        CARB_THROW_OR_CHECK(Count <= m_size, "Behavior is undefined when Count > size()");
        return span<element_type, Count>{ m_p + (m_size - Count), Count };
    }

    constexpr span<element_type, dynamic_extent> last(size_type Count) const
    {
        CARB_THROW_OR_CHECK(Count <= m_size, "Behavior is undefined when Count > size()");
        return span<element_type, dynamic_extent>{ m_p + (m_size - Count), Count };
    }

    template <std::size_t Offset, std::size_t Count = dynamic_extent>
    constexpr span<element_type, detail::DetermineSubspanExtent<extent, Offset, Count>::value> subspan() const
    {
        CARB_THROW_OR_CHECK(Offset <= m_size, "Behavior is undefined when Offset > size()");
        CARB_THROW_OR_CHECK(Count == dynamic_extent || (Offset + Count) <= m_size,
                            "Behavior is undefined when Count != dynamic_extent and (Offset + Count) > size()");
        return span<element_type, detail::DetermineSubspanExtent<extent, Offset, Count>::value>{
            data() + Offset, carb_min(size() - Offset, Count)
        };
    }

    constexpr span<element_type, dynamic_extent> subspan(size_type Offset, size_type Count = dynamic_extent) const
    {
        CARB_THROW_OR_CHECK(Offset <= m_size, "Behavior is undefined when Offset > size()");
        CARB_THROW_OR_CHECK(Count == dynamic_extent || (Offset + Count) <= m_size,
                            "Behavior is undefined when Count != dynamic_extent and (Offset + Count) > size()");
        return { data() + Offset, carb_min(size() - Offset, Count) };
    }

private:
    pointer m_p;
    size_type m_size;
};

// Specialization for zero
template <class T>
class span<T, 0>
{
    // NOTE: This specialization is for Extent == 0
public:
    using element_type = T;
    using value_type = std::remove_cv_t<T>;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using iterator = omni::detail::PointerIterator<pointer, span>;
    using reverse_iterator = std::reverse_iterator<iterator>;

    constexpr static std::size_t extent = 0;

    constexpr span() noexcept = default;

    template <class It,
              std::enable_if_t<std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value,
                               bool> = false>
    constexpr explicit span(It first, size_type count)
    {
        CARB_UNUSED(first, count);
        CARB_THROW_OR_CHECK(count == 0, "Behavior is undefined if count != extent");
    }

    template <class It,
              std::enable_if_t<std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value,
                               bool> = false>
    constexpr explicit span(It first, It last)
    {
        CARB_UNUSED(first, last);
        CARB_THROW_OR_CHECK(first == last, "Behavior is undefined if (last - first) != extent");
    }

    template <std::size_t N>
    constexpr span(type_identity_t<element_type> (&arr)[N]) noexcept
    {
        CARB_UNUSED(arr);
        static_assert(N == extent, "Undefined if N != extent");
    }

    template <class U, std::size_t N, std::enable_if_t<std::is_convertible<U, element_type>::value, bool> = false>
    constexpr span(std::array<U, N>& arr) noexcept
    {
        CARB_UNUSED(arr);
        static_assert(N == extent, "Undefined if N != extent");
    }

    template <class U, std::size_t N, std::enable_if_t<std::is_convertible<U, element_type>::value, bool> = false>
    constexpr span(const std::array<U, N>& arr) noexcept
    {
        CARB_UNUSED(arr);
        static_assert(N == extent, "Undefined if N != extent");
    }

    // template< class R >
    // explicit(extent != dynamic_extent)
    // constexpr span( R&& range );
    // (Constructor not available without ranges, but approximate constructor follows)

    template <class R,
              std::enable_if_t<detail::IsConvertibleRange<cpp::remove_cvref_t<R>, pointer>::value &&
                                   !detail::IsStdArray<cpp::remove_cvref_t<R>>::value && // has separate constructor
                                   !detail::IsSpan<cpp::remove_cvref_t<R>>::value && // has separate constructor
                                   !std::is_array<cpp::remove_cvref_t<R>>::value, // has separate constructor
                               bool> = false>
    constexpr explicit span(R&& range)
    {
        CARB_THROW_OR_CHECK(range.size() == extent, "Behavior is undefined if R.size() != extent");
    }

    template <class U,
              std::size_t N,
              std::enable_if_t<N == dynamic_extent && std::is_convertible<U, element_type>::value, bool> = false>
    constexpr explicit span(const span<U, N>& source) noexcept
    {
        CARB_UNUSED(source);
        CARB_THROW_OR_CHECK(N == extent, "Behavior is undefined if N != extent");
    }

    template <class U,
              std::size_t N,
              std::enable_if_t<N != dynamic_extent && std::is_convertible<U, element_type>::value, bool> = false>
    constexpr explicit span(const span<U, N>& source) noexcept
    {
        CARB_UNUSED(source);
        CARB_THROW_OR_CHECK(N == extent, "Behavior is undefined if N != extent");
    }

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

    constexpr span& operator=(const span& other) noexcept = default;

    constexpr iterator begin() const noexcept
    {
        return end();
    }

    constexpr iterator end() const noexcept
    {
        return iterator(nullptr);
    }

    constexpr reverse_iterator rbegin() const noexcept
    {
        return rend();
    }

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

    constexpr reference front() const
    {
        CARB_ALWAYS_FAIL("Behavior is undefined if front() is called on an empty span");
    }

    constexpr reference back() const
    {
        CARB_ALWAYS_FAIL("Behavior is undefined if back() is called on an empty span");
    }

    constexpr reference operator[](size_type index) const
    {
        CARB_UNUSED(index);
        CARB_ALWAYS_FAIL("Behavior is undefined if index >= size()");
    }

    constexpr pointer data() const noexcept
    {
        return nullptr;
    }

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

    constexpr size_type size_bytes() const noexcept
    {
        return 0;
    }

    CARB_NODISCARD constexpr bool empty() const noexcept
    {
        return true;
    }

    template <std::size_t Count>
    constexpr span<element_type, Count> first() const
    {
        static_assert(Count <= extent, "Program ill-formed if Count > extent");
        return span<element_type, Count>{};
    }

    constexpr span<element_type, dynamic_extent> first(size_type Count) const
    {
        CARB_UNUSED(Count);
        CARB_THROW_OR_CHECK(Count == 0, "Behavior is undefined if Count > extent");
        return span<element_type, dynamic_extent>{};
    }

    template <std::size_t Count>
    constexpr span<element_type, Count> last() const
    {
        CARB_THROW_OR_CHECK(Count == 0, "Behavior is undefined if Count > extent");
        return span<element_type, Count>{};
    }

    constexpr span<element_type, dynamic_extent> last(size_type Count) const
    {
        CARB_UNUSED(Count);
        CARB_THROW_OR_CHECK(Count == 0, "Behavior is undefined if Count > extent");
        return span<element_type, dynamic_extent>{};
    }

    template <std::size_t Offset, std::size_t Count = dynamic_extent>
    constexpr span<element_type, detail::DetermineSubspanExtent<extent, Offset, Count>::value> subspan() const
    {
        static_assert(Offset <= extent, "Ill-formed");
        static_assert(Count == dynamic_extent || (Offset + Count) <= extent, "Ill-formed");
        return {};
    }

    constexpr span<element_type, dynamic_extent> subspan(size_type Offset, size_type Count = dynamic_extent) const
    {
        CARB_UNUSED(Offset, Count);
        CARB_THROW_OR_CHECK(Offset <= extent, "Behavior is undefined if Offset > extent");
        CARB_THROW_OR_CHECK(Count == dynamic_extent || (Offset + Count) <= extent,
                            "Behavior is undefined if Count != dynamic_extent and (Offset + Count) > extent");
        return {};
    }
};

CARB_ASSERT_INTEROP_SAFE(span<int, 0>);
CARB_ASSERT_INTEROP_SAFE(span<int, dynamic_extent>);
#endif

#ifndef DOXYGEN_BUILD
template <class T, std::size_t N, std::enable_if_t<N == dynamic_extent, bool> = false>
span<const cpp::byte, dynamic_extent> as_bytes(span<T, N> s) noexcept
{
    return { reinterpret_cast<const cpp::byte*>(s.data()), s.size_bytes() };
}

template <class T, std::size_t N, std::enable_if_t<N != dynamic_extent, bool> = false>
span<const cpp::byte, sizeof(T) * N> as_bytes(span<T, N> s) noexcept
#else
template <class T, std::size_t N>
auto as_bytes(span<T, N> s) noexcept
#endif
{
    return span<const cpp::byte, sizeof(T) * N>{ reinterpret_cast<const cpp::byte*>(s.data()), s.size_bytes() };
}

#ifndef DOXYGEN_BUILD
template <class T, std::size_t N, std::enable_if_t<N == dynamic_extent, bool> = false>
span<cpp::byte, dynamic_extent> as_writable_bytes(span<T, N> s) noexcept
{
    return { reinterpret_cast<cpp::byte*>(s.data()), s.size_bytes() };
}

template <class T, std::size_t N, std::enable_if_t<N != dynamic_extent, bool> = false>
span<cpp::byte, sizeof(T) * N> as_writable_bytes(span<T, N> s) noexcept
#else
template <class T, std::size_t N>
auto as_writable_bytes(span<T, N> s) noexcept
#endif
{
    return span<cpp::byte, sizeof(T) * N>{ reinterpret_cast<cpp::byte*>(s.data()), s.size_bytes() };
}

#undef CARB_ALWAYS_FAIL
#undef CARB_THROW_OR_CHECK

} // namespace cpp
} // namespace carb