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 <http://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 <http://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.
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.
+ {
+ 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...}>;
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 <http://std.cc.in>
b/libstdc++-v3/src/c++23/std.cc.in <http://std.cc.in>
index 12253b95c5a..481e39b2821 100644
--- a/libstdc++-v3/src/c++23/std.cc.in <http://std.cc.in>
+++ b/libstdc++-v3/src/c++23/std.cc.in <http://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
