On Thu, Apr 10, 2025 at 1:21 PM Tomasz Kaminski <tkami...@redhat.com> wrote:
>
>
> On Wed, Apr 9, 2025 at 9:28 AM Luc Grosheintz <luc.groshei...@gmail.com>
> wrote:
>
>> This implements std::extents from <mdspan> according to N4950 and
>> contains partial progress towards PR107761.
>>
>> If an extent changes its type, there's a precondition in the standard,
>> that the value is representable in the target integer type. This commit
>> uses a static_cast for all of these conversions, without any additional
>> checks.
>>
>> The precondition for 'extents::{static_,}extent' is that '__r < rank()'.
>> For extents<T> this precondition is always violated and results in
>> calling __builtin_trap. For all other specializations it's checked via
>> __glibcxx_assert.
>>
>> PR libstdc++/107761
>>
>> libstdc++-v3/ChangeLog:
>>
>> * include/std/mdspan (extents): New class.
>> * src/c++23/std.cc.in: Add 'using std::extents'.
>>
>> Signed-off-by: Luc Grosheintz <luc.groshei...@gmail.com>
>> ---
>>
> Thanks for working on this. One general comment, as this is c++23 feature,
> we can benefit for the extensions to consteval functions, and replace the
> usual metaprogramming
> recursion with consteval functions, like following:
> __static_extent(size_t count, initializer_list<size_t> extends)
> {
> // use normal for to compute the product
> }
> We will elminiate instantiotns of the class template in this way.
>
For more concrete illustration of the suggestion, here is very limited
implementation:
https://godbolt.org/z/Gq59b4x4P
I hope this help to clarify.
>
> libstdc++-v3/include/std/mdspan | 400 +++++++++++++++++++++++++++++++
>> libstdc++-v3/src/c++23/std.cc.in | 6 +-
>> 2 files changed, 405 insertions(+), 1 deletion(-)
>>
>> diff --git a/libstdc++-v3/include/std/mdspan
>> b/libstdc++-v3/include/std/mdspan
>> index 4094a416d1e..5c6a1868d62 100644
>> --- a/libstdc++-v3/include/std/mdspan
>> +++ b/libstdc++-v3/include/std/mdspan
>> @@ -33,6 +33,10 @@
>> #pragma GCC system_header
>> #endif
>>
>> +#include <span>
>> +#include <array>
>> +#include <type_traits>
>> +
>> #define __glibcxx_want_mdspan
>> #include <bits/version.h>
>>
>> @@ -42,6 +46,402 @@ namespace std _GLIBCXX_VISIBILITY(default)
>> {
>> _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>> + namespace __detail
>>
> I would use a dedicated internal namespace for mdspan, like __mdspan.
>
>> + {
>> + // Computed as: sum_i (i == __r) * E_i
>> + template<size_t _Count, size_t... _Extents>
>> + struct _StaticExtent;
>> +
>> + template<size_t _Count, size_t _Extent, size_t... _Extents>
>> + struct _StaticExtent<_Count, _Extent, _Extents...>
>> + {
>> + static constexpr size_t
>> + _M_value(size_t __r) noexcept
>> + {
>> + return (_Count == __r) * _Extent
>> + + _StaticExtent<_Count + 1, _Extents...>::_M_value(__r);
>> + }
>> + };
>> +
>> + template<size_t _Count>
>> + struct _StaticExtent<_Count>
>> + {
>> + static constexpr size_t
>> + _M_value(size_t __r) noexcept
>> + { return 0; }
>> + };
>>
> As mentioned, I would experiment with implementing this as a consteval
> function, that accepts _Count and
> extends as parameters. We could also declare them as static methods inside
> the extends class itself,
> and create a stack array of extends inside them:
> static consteval
> _static_extent(size_t i)
> {
> size_t __exts[]{ __Extents };
> return __exts[i];
> }
> Or I suggest below, we can pass extends as std::array NTTP and have access
> to it direclty.
>
>> +
>> + // Computed as: sum_i (i < __r) * (E_i == dynamic_extent)
>> + template<size_t _Count, size_t... _Extents>
>> + struct _DynamicIndex;
>> +
>> + template<size_t _Count, size_t _Extent, size_t... _Extents>
>> + struct _DynamicIndex<_Count, _Extent, _Extents...>
>> + {
>> + static constexpr size_t
>> + _M_value(size_t __r) noexcept
>> + {
>> + return (_Count < __r) * (_Extent == dynamic_extent)
>> + + _DynamicIndex<_Count + 1, _Extents...>::_M_value(__r);
>> + }
>> + };
>> +
>> + template<size_t _Count>
>> + struct _DynamicIndex<_Count>
>> + {
>> + static constexpr size_t
>> + _M_value(size_t __r) noexcept
>> + { return 0; }
>> + };
>> +
>> + // Computed by: counting the number of dynamic extents (_Dr); and
>> returning
>> + // the static index first time `__di == _Dr`.
>> + template<size_t _Si, size_t _Dr, size_t... _Extents>
>> + struct _DynamicIndexInv;
>> +
>> + template<size_t _Si, size_t _Dr, size_t _Extent, size_t... _Extents>
>> + struct _DynamicIndexInv<_Si, _Dr, _Extent, _Extents...>
>> + {
>> + static constexpr size_t
>> + _M_value(size_t __di) noexcept
>> + {
>> + if (_Extent == dynamic_extent && __di == _Dr)
>> + return _Si;
>> + else
>> + return _DynamicIndexInv<_Si+1, _Dr + (_Extent ==
>> dynamic_extent),
>> + _Extents...>
>> + ::_M_value(__di);
>> + }
>> + };
>> +
>> + template<size_t _Si, size_t _Dr, size_t _Extent>
>> + struct _DynamicIndexInv<_Si, _Dr, _Extent>
>> + {
>> + static constexpr size_t
>> + _M_value(size_t __di) noexcept
>> + {
>> + __glibcxx_assert(__di == _Dr);
>> + return _Si;
>> + }
>> + };
>> +
>> + // Aim: __ext[i] for template parameter packs.
>> + template<size_t _Count, typename... _IndexTypes>
>> + struct _GetPackElement;
>> +
>> + template<size_t _Count, typename _IndexType, typename... _IndexTypes>
>> + struct _GetPackElement<_Count, _IndexType, _IndexTypes...>
>> + {
>> + template<size_t _Index>
>> + static constexpr const auto&
>> + get(const _IndexType& __current, const _IndexTypes&... __rest)
>> + {
>> + if constexpr (_Index == _Count)
>> + return __current;
>> + else
>> + return _GetPackElement<_Count+1, _IndexTypes...>
>> + ::template get<_Index>(__rest...);
>> + }
>> + };
>> +
>> + template<size_t _Di, typename... _IndexTypes>
>> + constexpr const auto&
>> + __get_element(const _IndexTypes&... __exts)
>> + {
>> + return _GetPackElement<0, _IndexTypes...>
>> + ::template get<_Di>(__exts...);
>> + }
>> +
>> + template<size_t... _Extents>
>> + struct _DynamicRank
>> + {
>> + static constexpr size_t _S_value = ((_Extents == dynamic_extent)
>> + ...);
>> + };
>>
> You can use a binary fold, and eliminate the need for separate
> specialization.
>
>> +
>> + template<>
>> + struct _DynamicRank<>
>> + {
>> + static constexpr size_t _S_value = 0;
>> + };
>>
> +
>> + template<typename _IndexType, typename _DynamicIndexes, typename
>> _Indexes,
>> + size_t... _Extents>
>> + struct _ExtentsStorage;
>> +
>> + template<typename _IndexType, size_t... _DynamicIndexes, size_t...
>> _Indexes,
>> + size_t... _Extents>
>> + struct _ExtentsStorage<_IndexType,
>> index_sequence<_DynamicIndexes...>,
>> + index_sequence<_Indexes...>, _Extents...>
>>
> C++20 supports non-class types as template parameters, including
> std::array.
> Thus I would consider using std::array<size_t, sizeof...(_Extends)> as
> one here.
>
>> + {
>> + static constexpr size_t _S_rank = sizeof...(_Extents);
>> +
>> + static constexpr size_t _S_rank_dynamic =
>> + _DynamicRank<_Extents...>::_S_value;
>>
> I would inline the computation here.
>
>> +
>> + static constexpr array<size_t, _S_rank_dynamic>
>> _S_dynamic_index_inv{
>> + _DynamicIndexInv<0, 0, _Extents...>
>> ::_M_value(_DynamicIndexes)...};
>> +
>> + static constexpr array<size_t, _S_rank> _S_dynamic_index {
>> + _DynamicIndex<0, _Extents...>::_M_value(_Indexes)...};
>> +
>> + template<typename _Tp>
>> + static constexpr _IndexType
>> + _M_int_cast(const _Tp& __other)
>> + { return __other; }
>>
> As we check std::is_nothrow_constructible_v
> <http://en.cppreference.com/w/cpp/types/is_constructible><IndexType,
> OtherIndexType>, we should use an explicit conversion
> here: return _IndexType(__other);. And also mark this function as noexcept.
>
>> +
>> + constexpr _ExtentsStorage() = default;
>> +
>> + template<typename _OIndexType, typename _ODynamicIndexes,
>> + typename _OIndexes, size_t... _OExtents>
>> + constexpr _ExtentsStorage(
>> + const _ExtentsStorage<_OIndexType, _ODynamicIndexes,
>> _OIndexes,
>> + _OExtents...>& __other)
>> + : _M_dynamic_extents{_M_int_cast(__other._M_extent(
>> + _S_dynamic_index_inv[_DynamicIndexes]))...}
>> + { }
>> +
>> + template<size_t _Di, typename... _OIndexTypes>
>> + static constexpr const auto&
>> + _M_get_dynamic_element(const _OIndexTypes&... __exts)
>> + { return __get_element<_S_dynamic_index_inv[_Di]>(__exts...); }
>> +
>> + template<typename... _OIndexTypes>
>> + requires (sizeof...(_OIndexTypes) == _S_rank_dynamic)
>> + && (is_convertible_v<_OIndexTypes, _IndexType> && ...)
>> + constexpr
>> + _ExtentsStorage(const _OIndexTypes&... __exts)
>> + : _M_dynamic_extents{_M_int_cast(
>> + __get_element<_DynamicIndexes>(__exts...))...}
>> + { }
>>
> As `_ExtentsStorage` is built only by the extents class, I would consider
> having only
> following constructors available here. The index type is required to be
> integer type,
> so copying it is cheap. As such, so I do not think we need to use the
> integer_sequence trick here.
>
> constexpr _ExtentsStorage(span<OhterIndexTypes, _S_rank_dynamic> __ext)
> {
> auto __out = _M_dynamic_extents.data();
> for (std::size_t __i = 0; i < _S_rank; ++_i, ++_out)
> __out = __ext[i];
> }
> constexpr _ExtentsStorage(span<OhterIndexTypes, _S_rank> __ext)
> requires (_S_rank != _S_rank_dynamic)
> {
> auto __out = _M_dynamic_extents.data();
> for (std::size_t __i = 0; i < _S_rank; ++_i)
> if (_S_rank_dynamic(i) == dynamic_extent)
> {
> __out = __ext[i];
> ++__out;
> }
> }
>
> For array and span extends constructors they can be passed directly.
> For the one accepting const _OIndexTypes&... __exts, you can implement it
> as:
> _ExtendsStorage(span<index_type,
> sizeof...(_OIndexTypes)>(initializer_list<index_type>{
> _S_index_cast(_exts)...}))
>
> +
>> + template<typename... _OIndexTypes>
>> + requires (sizeof...(_OIndexTypes) != _S_rank_dynamic)
>> + && (is_convertible_v<_OIndexTypes, _IndexType> && ...)
>> + constexpr
>> + _ExtentsStorage(const _OIndexTypes&... __exts)
>> + : _M_dynamic_extents{_M_int_cast(
>> + _M_get_dynamic_element<_DynamicIndexes>(__exts...))...}
>> + { }
>> +
>> + template<typename _OIndexType, size_t _Nm>
>> + requires (_Nm == _S_rank_dynamic)
>> + constexpr
>> + _ExtentsStorage(const span<_OIndexType, _Nm>& __exts)
>> + : _M_dynamic_extents{_M_int_cast(
>> + as_const(__exts[_DynamicIndexes]))...}
>> + { }
>> +
>> + template<typename _OIndexType, size_t _Nm>
>> + requires (_Nm != _S_rank_dynamic)
>> + constexpr _ExtentsStorage(const span<_OIndexType, _Nm>& __exts)
>> + : _M_dynamic_extents{_M_int_cast(
>> + as_const(__exts[_S_dynamic_index_inv[_DynamicIndexes]]))...}
>> + { }
>> +
>> + template<typename _OIndexType, size_t _Nm>
>> + requires (_Nm == _S_rank_dynamic)
>> + constexpr
>> + _ExtentsStorage(const array<_OIndexType, _Nm>& __exts)
>> + : _M_dynamic_extents{_M_int_cast(
>> + as_const(__exts[_DynamicIndexes]))...}
>> + { }
>> +
>> + template<typename _OIndexType, size_t _Nm>
>> + requires (_Nm != _S_rank_dynamic)
>> + constexpr _ExtentsStorage(const array<_OIndexType, _Nm>& __exts)
>> + : _M_dynamic_extents{_M_int_cast(
>> + as_const(__exts[_S_dynamic_index_inv[_DynamicIndexes]]))...}
>> + { }
>> +
>> + static constexpr size_t
>> + _M_static_extent(size_t __r) noexcept
>> + { return _StaticExtent<0, _Extents...>::_M_value(__r); }
>> +
>> + constexpr _IndexType
>> + _M_extent(size_t __r) const noexcept
>> + {
>> + auto __se = _M_static_extent(__r);
>> + if (__se == dynamic_extent)
>> + return _M_dynamic_extents[_S_dynamic_index[__r]];
>> + else
>> + return __se;
>> + }
>> + private:
>> + [[no_unique_address]]
>> + array<_IndexType, _S_rank_dynamic> _M_dynamic_extents;
>> + };
>> +
>> + template<typename _IndexType, size_t... _Extents>
>> + using __extents_storage = _ExtentsStorage<
>> + _IndexType,
>> make_index_sequence<_DynamicRank<_Extents...>::_S_value>,
>> + make_index_sequence<sizeof...(_Extents)>, _Extents...>;
>> + }
>> +
>> + template<typename _IndexType, size_t... _Extents>
>> + class extents;
>> +
>> + template<typename _SIndexType, size_t... _SExtents, typename
>> _OIndexType,
>> + size_t... _OExtents>
>> + constexpr bool
>> + operator==(const extents<_SIndexType, _SExtents...>& __self,
>> + const extents<_OIndexType, _OExtents...>& __other)
>> noexcept;
>> +
>> + template<typename _IndexType, size_t... _Extents>
>> + class extents
>> + {
>> + static_assert(is_integral_v<_IndexType>, "_IndexType must be
>> integral.");
>> +
>> + public:
>> + using index_type = _IndexType;
>> + using size_type = make_signed_t<index_type>;
>> + using rank_type = size_t;
>> +
>> + static constexpr rank_type
>> + rank() noexcept { return _ExtentsStorage::_S_rank; }
>> +
>> + static constexpr rank_type
>> + rank_dynamic() noexcept { return _ExtentsStorage::_S_rank_dynamic;
>> }
>> +
>> + static constexpr size_t
>> + static_extent(rank_type __r) noexcept
>> + {
>> + if constexpr (rank() == 0)
>> + __builtin_trap();
>> +
>> + __glibcxx_assert(__r < rank());
>> + return _ExtentsStorage::_M_static_extent(__r);
>> + }
>> +
>> + constexpr index_type
>> + extent(rank_type __r) const noexcept
>> + {
>> + if constexpr (rank() == 0)
>> + __builtin_trap();
>> +
>> + __glibcxx_assert(__r < rank());
>> + return _M_extents._M_extent(__r);
>> + }
>> +
>> + constexpr
>> + extents() noexcept = default;
>> +
>> + private:
>> + static constexpr bool
>> + _M_is_less_dynamic(size_t __ext, size_t __oext)
>> + { return (__ext != dynamic_extent) && (__oext == dynamic_extent); }
>> +
>> + template<typename _Tp>
>> + static constexpr size_t
>> + _M_limits_max() { return numeric_limits<_Tp>::max(); }
>> +
>> + template<typename _OIndexType, size_t... _OExtents>
>> + static constexpr bool
>> + _M_ctor_explicit()
>> + {
>> + return (_M_is_less_dynamic(_Extents, _OExtents) || ...)
>> + || (_M_limits_max<index_type>() <
>> _M_limits_max<_OIndexType>());
>> + }
>> +
>> + public:
>> + template<typename _OIndexType, size_t... _OExtents>
>> + requires (sizeof...(_OExtents) == rank())
>> + && ((_OExtents == dynamic_extent || _Extents ==
>> dynamic_extent
>> + || _OExtents == _Extents) && ...)
>> + constexpr explicit(_M_ctor_explicit<_OIndexType, _OExtents...>())
>> + extents(const extents<_OIndexType, _OExtents...>& __other)
>> noexcept
>> + : _M_extents(__other._M_extents)
>> + { }
>> +
>> + template<typename... _OIndexTypes>
>> + requires (
>> + ((sizeof...(_OIndexTypes) == rank()
>> + || sizeof...(_OIndexTypes) == rank_dynamic()))
>> + && (is_convertible_v<_OIndexTypes, index_type> && ...)
>> + && (is_nothrow_constructible_v<index_type, _OIndexTypes> &&
>> ...))
>> + constexpr explicit extents(_OIndexTypes... __exts) noexcept
>> + : _M_extents(__exts...)
>> + { }
>> +
>> + template<typename _OIndexType, size_t _Nm>
>> + requires (is_convertible_v<const _OIndexType& , index_type>
>> + && is_nothrow_constructible_v<index_type, const
>> _OIndexType&>
>> + && (_Nm == rank_dynamic() || _Nm == rank()))
>> + constexpr explicit(_Nm != rank_dynamic())
>> + extents(span<_OIndexType, _Nm> __exts) noexcept
>> + : _M_extents(__exts)
>> + { }
>> +
>> + template<typename _OIndexType, size_t _Nm>
>> + requires (is_convertible_v<const _OIndexType& , index_type>
>> + && is_nothrow_constructible_v<index_type, const
>> _OIndexType&>
>> + && (_Nm == rank_dynamic() || _Nm == rank()))
>> + constexpr explicit(_Nm != rank_dynamic())
>> + extents(const array<_OIndexType, _Nm>& __exts) noexcept
>> + : _M_extents(__exts)
>> + { }
>> +
>> + template<typename _SIndexType, size_t... _SExtents, typename
>> _OIndexType,
>> + size_t... _OExtents>
>> + friend constexpr bool
>> + operator==(const extents&,
>> + const extents<_OIndexType, _OExtents...>&) noexcept;
>> +
>> + private:
>> + using _ExtentsStorage =
>> + typename __detail::__extents_storage<_IndexType, _Extents...>;
>> +
>> + [[no_unique_address]] _ExtentsStorage _M_extents;
>> +
>> + template<typename _OIndexType, size_t... _OExtents>
>> + friend class extents;
>> + };
>> +
>> + template<typename _SIndexType, size_t... _SExtents, typename
>> _OIndexType,
>> + size_t... _OExtents>
>> + constexpr bool
>> + operator==(const extents<_SIndexType, _SExtents...>& __self,
>> + const extents<_OIndexType, _OExtents...>& __other) noexcept
>> + {
>> + if constexpr (__self.rank() != __other.rank())
>> + return false;
>> +
>> + for (size_t __i = 0; __i < __self.rank(); ++__i)
>> + if (__self.extent(__i) != __other.extent(__i))
>> + return false;
>> + return true;
>> + }
>> +
>> + namespace __detail
>> + {
>> + template<typename _IndexType, size_t _Count, size_t _Rank,
>> + size_t... _Extents>
>> + struct _Dextents
>> + {
>> + using type = typename _Dextents<_IndexType, _Count+1, _Rank,
>> + _Extents...,
>> dynamic_extent>::type;
>> + };
>> +
>> + template<typename _IndexType, size_t _Rank, size_t... _Extents>
>> + struct _Dextents<_IndexType, _Rank, _Rank, _Extents...>
>> + {
>> + using type = extents<_IndexType, _Extents...>;
>> + };
>> +
>> + template<typename _Tp>
>> + struct _DynamicExtent
>> + {
>> + static constexpr size_t _S_dyn = dynamic_extent;
>> + };
>>
> I would replace this by consteval function. Again each instantiation
> generates a separate type.
>
>> + }
>> +
>> + template<typename _IndexType, size_t _Rank>
>> + using dextents = typename __detail::_Dextents<_IndexType, 0,
>> _Rank>::type;
>> +
>> + template<typename... _Integrals>
>> + requires (is_convertible_v<_Integrals, size_t> && ...)
>> + explicit extents(_Integrals...) ->
>> + extents<size_t, __detail::_DynamicExtent<_Integrals>::_S_dyn...>;
>> +
>> _GLIBCXX_END_NAMESPACE_VERSION
>> }
>> #endif
>> diff --git a/libstdc++-v3/src/c++23/std.cc.in b/libstdc++-v3/src/c++23/
>> std.cc.in
>> index 12253b95c5a..481e39b2821 100644
>> --- a/libstdc++-v3/src/c++23/std.cc.in
>> +++ b/libstdc++-v3/src/c++23/std.cc.in
>> @@ -1825,7 +1825,11 @@ export namespace std
>> }
>> }
>>
>> -// FIXME <mdspan>
>> +// <mdspan>
>> +{
>> + using std::extents;
>> + // FIXME layout_*, default_accessor and mdspan
>> +}
>>
>> // 20.2 <memory>
>> export namespace std
>> --
>> 2.49.0
>>
>>
