On Tue, Apr 15, 2025 at 2:35 PM Luc Grosheintz <luc.groshei...@gmail.com>
wrote:
> Thank you! I left two comments. Everything not commented on, I'll just
> incorporate into the next iteration.
> On 4/15/25 11:18 AM, Tomasz Kaminski wrote:
>
>
>
> 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.
>
> Yes, this is related to [[no_unique_address]]. If all extents are static,
> then there's no dynamic extents that need to be stored. A similar
> situation is encountered in span. Where the size of the span can be
> a compile time constant. The implementation of span uses
> [[no_unique_address]], which is why I wanted to do the same.
>
You could use __array_traits<Tp, N>::_Type here, as it is either an empty
struct
with appropriate [] member or array.
> If I try to use [[no_unique_address]] with array<int, 0>, it has no effect.
> (I believe it's because array always contains a private member
> `_M_elems` and because array predates [[no_unique_address]] it
> can't use that attribute.) Here's an example of this on godbolt:
> https://godbolt.org/z/9vd5Gv31x
>
> This does raise a question about ABI, is it correct to use
> [[no_unique_address]]? When reading the standard, it's not clear to
> me whether using [[no_unique_address]] is permitted/prohibited.
>
It would be breaking to change the layout for the array, but I think it is
allowed,
and even desired from a QoI perspective, to put it there.
> + {
>> + 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.
>
> There were two weak reasons. The first was that the following
> line is a bit lengthy and breaks awkwardly:
>
> using _S_storage = __mdspan::_ExtentsStorage<_IndexType,
> array<size_t, sizeof...(_Extents)>{_Extents...}>;
>
You could use the CTAD deduction array{ _Extends... } or
to_array<size_t>({ _Extends... }).
I prefer the latter.
> when sizeof...(_Extents) == 0, it can't deduce the template arguments, so I
> couldn't make the shorter <_IndexType, {_Extents...}> work. During the
> implementation it was sometimes useful to be able to manipulate the
> extents as a pack; but now there's no such cases left anymore. I'll change
> it.
>
> + 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
>>
>>
