On Tue, Apr 15, 2025 at 10:43 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 direct initialization to perform the conversion, 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>
>
Looks really good, thanks. A bunch of small suggestions.
> ---
> libstdc++-v3/include/std/mdspan | 304 +++++++++++++++++++++++++++++++
> libstdc++-v3/src/c++23/std.cc.in | 6 +-
> 2 files changed, 309 insertions(+), 1 deletion(-)
>
> diff --git a/libstdc++-v3/include/std/mdspan
> b/libstdc++-v3/include/std/mdspan
> index 4094a416d1e..72ca3445d15 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>
>
> @@ -41,6 +45,306 @@
> namespace std _GLIBCXX_VISIBILITY(default)
> {
> _GLIBCXX_BEGIN_NAMESPACE_VERSION
> + namespace __mdspan
> + {
> + template<typename _Tp, size_t _Nm>
> + class __array
>
Any reason for using __array here, instead of std::array.
We already need to pull that header, because of the constructors.
> + {
> + public:
> + constexpr _Tp&
> + operator[](size_t __n) noexcept
> + {
> + return _M_elems[__n];
> + }
> +
> + constexpr const _Tp&
> + operator[](size_t __n) const noexcept
> + {
> + return _M_elems[__n];
> + }
> +
> + private:
> + array<_Tp, _Nm> _M_elems;
> + };
> +
> + template<typename _Tp>
> + class __array<_Tp, 0>
> + {
> + public:
> + constexpr _Tp&
> + operator[](size_t __n) noexcept
> + {
> + __builtin_trap();
> + }
> +
> + constexpr const _Tp&
> + operator[](size_t __n) const noexcept
> + {
> + __builtin_trap();
> + }
> + };
> +
> + template<typename _IndexType, size_t... _Extents>
>
I would use NTTP of the std::array here, and eliminate internal _S_exts.
Your __array is not structural, because it has private members.
> + class _ExtentsStorage
> + {
> + public:
> + static constexpr bool
> + _M_is_dyn(size_t __ext) noexcept
> + { return __ext == dynamic_extent; }
> +
> + template<typename _OIndexType>
> + static constexpr _IndexType
> + _M_int_cast(const _OIndexType& __other) noexcept
> + { return _IndexType(__other); }
> +
> + static constexpr size_t _S_rank = sizeof...(_Extents);
> + static constexpr array<size_t, _S_rank> _S_exts{_Extents...};
> +
> + // For __r in [0, _S_rank], _S_dynamic_index[__r] is the number
> + // of dynamic extents up to (and not including) __r.
> + //
> + // If __r is the index of a dynamic extent, then
> + // _S_dynamic_index[__r] is the index of that extent in
> + // _M_dynamic_extents.
> + static constexpr auto _S_dynamic_index = [] consteval
> + {
> + array<size_t, _S_rank+1> __ret;
> + size_t __dyn = 0;
> + for(size_t __i = 0; __i < _S_rank; ++__i)
> + {
> + __ret[__i] = __dyn;
> + __dyn += _M_is_dyn(_S_exts[__i]);
> + }
> + __ret[_S_rank] = __dyn;
> + return __ret;
> + }();
> +
> + static constexpr size_t _S_rank_dynamic =
> _S_dynamic_index[_S_rank];
> +
> + // For __r in [0, _S_rank_dynamic), _S_dynamic_index_inv[__r] is
> the
> + // index of the __r-th dynamic extent in _S_exts.
> + static constexpr auto _S_dynamic_index_inv = [] consteval
> + {
> + array<size_t, _S_rank_dynamic> __ret;
> + for (size_t __i = 0, __r = 0; __i < _S_rank; ++__i)
> + if (_M_is_dyn(_S_exts[__i]))
> + __ret[__r++] = __i;
> + return __ret;
> + }();
> +
> + static constexpr size_t
> + _M_static_extent(size_t __r) noexcept
> + { return _S_exts[__r]; }
> +
> + constexpr _IndexType
> + _M_extent(size_t __r) const noexcept
> + {
> + auto __se = _S_exts[__r];
> + if (__se == dynamic_extent)
> + return _M_dynamic_extents[_S_dynamic_index[__r]];
> + else
> + return __se;
> + }
> +
> + private:
>
This private is not needed here.
> + template<size_t _OtherRank, typename _GetOtherExtent>
> + constexpr void
> + _M_init_dynamic_extents(_GetOtherExtent __get_extent) noexcept
> + {
> + for(size_t __i = 0; __i < _S_rank_dynamic; ++__i)
> + {
> + size_t __di = __i;
> + if constexpr (_OtherRank != _S_rank_dynamic)
> + __di = _S_dynamic_index_inv[__i];
> + _M_dynamic_extents[__i] = _M_int_cast(__get_extent(__di));
> + }
> + }
> +
> + public:
> + constexpr
> + _ExtentsStorage() noexcept = default;
> +
> + template<typename _OIndexType, size_t... _OExtents>
> + constexpr
> + _ExtentsStorage(const _ExtentsStorage<_OIndexType, _OExtents...>&
> + __other) noexcept
> + {
> + _M_init_dynamic_extents<_S_rank>([&__other](auto __i)
> + { return __other._M_extent(__i); });
> + }
> +
> + template<typename _OIndexType, size_t _Nm>
> + constexpr
> + _ExtentsStorage(const span<_OIndexType, _Nm>& __exts) noexcept
> + {
> + _M_init_dynamic_extents<_Nm>(
> + [&__exts](auto __i) -> const _OIndexType&
> + { return __exts[__i]; });
> + }
> +
> + private:
> + using _S_storage_type = __array<_IndexType, _S_rank_dynamic>;
> + [[no_unique_address]] _S_storage_type _M_dynamic_extents;
> + };
> +
> + template<typename _OIndexType, typename _SIndexType>
> + concept __valid_index_type =
> + is_convertible_v<_OIndexType, _SIndexType> &&
> + is_nothrow_constructible_v<_SIndexType, _OIndexType>;
> + }
> +
> + 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.");
>
We are missing two compile-time checks here for
https://eel.is/c++draft/mdspan.extents#overview-1.2:
- each element of Extents is either equal to dynamic_extent, or is
representable as a value of type IndexType.
<https://eel.is/c++draft/mdspan.extents#overview-1.sentence-1>
> +
> + public:
> + using index_type = _IndexType;
> + using size_type = make_unsigned_t<index_type>;
> + using rank_type = size_t;
> +
> + static constexpr rank_type
> + rank() noexcept { return _S_storage::_S_rank; }
> +
> + static constexpr rank_type
> + rank_dynamic() noexcept { return _S_storage::_S_rank_dynamic; }
> +
> + static constexpr size_t
> + static_extent(rank_type __r) noexcept
> + {
> + __glibcxx_assert(__r < rank());
> + if constexpr (rank() == 0)
> + __builtin_trap();
> +
> + return _S_storage::_M_static_extent(__r);
> + }
> +
> + constexpr index_type
> + extent(rank_type __r) const noexcept
> + {
> + __glibcxx_assert(__r < rank());
> + if constexpr (rank() == 0)
> + __builtin_trap();
> +
> + return _M_dynamic_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 _OIndexType, size_t... _OExtents>
> + static constexpr bool
> + _M_ctor_explicit()
> + {
> + return (_M_is_less_dynamic(_Extents, _OExtents) || ...)
> + || (numeric_limits<index_type>::max()
> + < numeric_limits<_OIndexType>::max());
> + }
> +
> + 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_dynamic_extents(__other._M_dynamic_extents)
> + { }
> +
> + template<__mdspan::__valid_index_type<index_type>... _OIndexTypes>
> + requires (sizeof...(_OIndexTypes) == rank()
> + || sizeof...(_OIndexTypes) == rank_dynamic())
> + constexpr explicit extents(_OIndexTypes... __exts) noexcept
> + : extents(span<add_const_t<_IndexType>, sizeof...(_OIndexTypes)>(
>
Do we need to use add_const_t here, or just const _IndexType would be fine?
I would also construct _M_dynamic_extents directly here, if we implement
preconditions,
I would put them in _M_init_dynamic_extents.
> + initializer_list{_S_storage::_M_int_cast(__exts)...}))
> + { }
> +
> + template<__mdspan::__valid_index_type<index_type> _OIndexType,
> size_t _Nm>
> + requires (_Nm == rank() || _Nm == rank_dynamic())
> + constexpr explicit(_Nm != rank_dynamic())
> + extents(span<_OIndexType, _Nm> __exts) noexcept
> + : _M_dynamic_extents(__exts)
> + { }
> +
> +
> + template<__mdspan::__valid_index_type<index_type> _OIndexType,
> size_t _Nm>
> + requires (_Nm == rank() || _Nm == rank_dynamic())
> + constexpr explicit(_Nm != rank_dynamic())
> + extents(const array<_OIndexType, _Nm>& __exts) noexcept
> + : extents(span<add_const_t<_OIndexType>, _Nm>(__exts))
>
Same comment on constructing _M_dynamic_extents here.
> + { }
> +
> + template<typename _SIndexType, size_t... _SExtents, typename
> _OIndexType,
> + size_t... _OExtents>
> + friend constexpr bool
> + operator==(const extents&,
> + const extents<_OIndexType, _OExtents...>&) noexcept;
> +
> + private:
> + using _S_storage = __mdspan::_ExtentsStorage<_IndexType,
> _Extents...>;
> + [[no_unique_address]] _S_storage _M_dynamic_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 __mdspan
> + {
> + 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>
> + constexpr size_t
> + __dynamic_extent() { return dynamic_extent; }
> + }
> +
> + template<typename _IndexType, size_t _Rank>
> + using dextents = typename __mdspan::_Dextents<_IndexType, 0,
> _Rank>::type;
>
Instead of using recursion, this could be implemented as:
namespace __mdspan
{
template<typename _IndexType, size_t... _Ids>
auto __make_dextends(index_sequence<_Ids...>)
-> extents<_IndexType, (_Ids, dynamic_extent)...>;
}
template<typename _IndexType, size_t _Rank>
using dextents =
decltype(__mdspan::__make_dextends<IndexType>(make_index_sequence<_Rank>()));
> +
> + template<typename... _Integrals>
> + requires (is_convertible_v<_Integrals, size_t> && ...)
> + explicit extents(_Integrals...) ->
> + extents<size_t, __mdspan::__dynamic_extent<_Integrals>()...>;
>
> _GLIBCXX_END_NAMESPACE_VERSION
> }
> 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.48.1
>
>
