On 4/30/25 4:37 AM, Tomasz Kaminski wrote:
On Tue, Apr 29, 2025 at 11:52 PM Jonathan Wakely <jwak...@redhat.com> wrote:
On Tue, 29 Apr 2025 at 14:55, Tomasz Kaminski <tkami...@redhat.com> wrote:
On Tue, Apr 29, 2025 at 2:55 PM 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
precondition is not checked at runtime.
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>
---
libstdc++-v3/include/std/mdspan | 262 +++++++++++++++++++++++++++++++
libstdc++-v3/src/c++23/std.cc.in | 6 +-
2 files changed, 267 insertions(+), 1 deletion(-)
diff --git a/libstdc++-v3/include/std/mdspan
b/libstdc++-v3/include/std/mdspan
index 4094a416d1e..39ced1d6301 100644
--- a/libstdc++-v3/include/std/mdspan
+++ b/libstdc++-v3/include/std/mdspan
@@ -33,6 +33,12 @@
#pragma GCC system_header
#endif
+#include <span>
+#include <array>
+#include <type_traits>
+#include <limits>
+#include <utility>
+
#define __glibcxx_want_mdspan
#include <bits/version.h>
@@ -41,6 +47,262 @@
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
+ namespace __mdspan
+ {
+ template<typename _IndexType, array _Extents>
+ class _ExtentsStorage
+ {
+ public:
+ static consteval bool
+ _S_is_dyn(size_t __ext) noexcept
+ { return __ext == dynamic_extent; }
+
+ template<typename _OIndexType>
+ static constexpr _IndexType
+ _S_int_cast(const _OIndexType& __other) noexcept
+ { return _IndexType(__other); }
+
+ static constexpr size_t _S_rank = _Extents.size();
+
+ // 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 += _S_is_dyn(_Extents[__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 _Extents.
+ 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 (_S_is_dyn(_Extents[__i]))
+ __ret[__r++] = __i;
+ return __ret;
+ }();
+
+ static constexpr size_t
+ _S_static_extent(size_t __r) noexcept
+ { return _Extents[__r]; }
+
+ constexpr _IndexType
+ _M_extent(size_t __r) const noexcept
+ {
+ auto __se = _Extents[__r];
+ if (__se == dynamic_extent)
+ return _M_dynamic_extents[_S_dynamic_index[__r]];
+ else
+ return __se;
+ }
+
+ 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] =
_S_int_cast(__get_extent(__di));
+ }
+ }
+
+ constexpr
+ _ExtentsStorage() noexcept = default;
+
+ template<typename _OIndexType, array _OExtents>
+ constexpr
+ _ExtentsStorage(const _ExtentsStorage<_OIndexType, _OExtents>&
+ __other) noexcept
+ {
+ _M_init_dynamic_extents<_S_rank>([&__other](size_t __i)
+ { return __other._M_extent(__i); });
+ }
+
+ template<typename _OIndexType, size_t _Nm>
+ constexpr
+ _ExtentsStorage(span<const _OIndexType, _Nm> __exts) noexcept
+ {
+ _M_init_dynamic_extents<_Nm>(
+ [&__exts](size_t __i) -> const _OIndexType&
+ { return __exts[__i]; });
+ }
+
+ private:
+ using _S_storage = __array_traits<_IndexType,
_S_rank_dynamic>::_Type;
+ [[no_unique_address]] _S_storage _M_dynamic_extents;
+ };
+
+ template<typename _OIndexType, typename _SIndexType>
+ concept __valid_index_type =
+ is_convertible_v<_OIndexType, _SIndexType> &&
+ is_nothrow_constructible_v<_SIndexType, _OIndexType>;
+
+ template<size_t _Extent, typename _IndexType>
+ concept
+ __valid_static_extent = _Extent == dynamic_extent
+ || _Extent <= numeric_limits<_IndexType>::max();
+ }
+
+ template<typename _IndexType, size_t... _Extents>
+ class extents
+ {
+ static_assert(is_integral_v<_IndexType>, "_IndexType must be
integral.");
+ static_assert(
+ (__mdspan::__valid_static_extent<_Extents, _IndexType> &&
...),
+ "Extents must either be dynamic or representable as
_IndexType");
+
+ 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();
+ else
+ return _S_storage::_S_static_extent(__r);
+ }
+
+ constexpr index_type
+ extent(rank_type __r) const noexcept
+ {
+ __glibcxx_assert(__r < rank());
+ if constexpr (rank() == 0)
+ __builtin_trap();
+ else
+ return _M_dynamic_extents._M_extent(__r);
+ }
+
+ constexpr
+ extents() noexcept = default;
+
+ private:
+ static consteval bool
+ _S_is_less_dynamic(size_t __ext, size_t __oext)
+ { return (__ext != dynamic_extent) && (__oext ==
dynamic_extent); }
+
+ template<typename _OIndexType, size_t... _OExtents>
+ static consteval bool
+ _S_ctor_explicit()
+ {
+ return (_S_is_less_dynamic(_Extents, _OExtents) || ...)
+ || (numeric_limits<index_type>::max()
+ < numeric_limits<_OIndexType>::max());
+ }
+
+ template<size_t... _OExtents>
+ static consteval bool
+ _S_is_compatible_extents()
+ {
+ if constexpr (sizeof...(_OExtents) != rank())
+ return false;
+ else {
We do not need braces here.
+ return ((_OExtents == dynamic_extent || _Extents ==
dynamic_extent
+ || _OExtents == _Extents) && ...);
+ }
+ }
+
+ public:
+ template<typename _OIndexType, size_t... _OExtents>
+ requires (_S_is_compatible_extents<_OExtents...>())
+ constexpr explicit(_S_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
+ : _M_dynamic_extents(span<const _IndexType,
sizeof...(_OIndexTypes)>(
+ initializer_list{_S_storage::_S_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(span<const _OIndexType, _Nm>(__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
+ : _M_dynamic_extents(span<const _OIndexType, _Nm>(__exts))
+ { }
+
+ template<typename _OIndexType, size_t... _OExtents>
+ friend constexpr bool
+ operator==(const extents& __self,
+ const extents<_OIndexType, _OExtents...>& __other)
noexcept
+ {
+ if constexpr (!_S_is_compatible_extents<_OExtents...>())
+ return false;
We can add here:
// N.B. if extents are compatible and static, it implies
that they are equal
else if constexpr ((_Extents != dynamic_extent) && ...)
return true;
Can't we have a case where _OExtents==dynamic_extent and
_Extents!=dynamic_extents, which would mean they're compatible, but
not equal?
Ah, indeed the conditions needs to be:
(_Extents != dynamic_extent && _Extents == _OExtents) && ...
The reason I didn't follow through with this is because when looking
at the generated code I saw no advantage of the additional constexpr
branch. Therefore, I preferred the simplicity of Tomasz first proposal,
i.e. the current implementation.
Would you still like me to add the additional `else if constexpr`
branch?
Here's the output of objdump when compiling with `-O2`:
bool same1(const std::extents<int, 1, 2, 3>& e1,
const std::extents<int, 1, 2, 3>& e2)
{ return e1 == e2; }
0: b8 01 00 00 00 mov $0x1,%eax
5: c3 ret
bool same2(const std::extents<int, 2, 2, 3>& e1,
const std::extents<int, 1, 2, 3>& e2)
{ return e1 == e2; }
0: 31 c0 xor %eax,%eax
2: c3 ret
bool same3(const std::extents<int, 2, dyn, 3>& e1,
const std::extents<int, 1, 2, 3>& e2)
{ return e1 == e2; }
0: 31 c0 xor %eax,%eax
2: c3 ret
bool same4(const std::extents<int, 2, dyn, 3>& e1,
const std::extents<int, dyn, 2, 4>& e2)
{ return e1 == e2; }
0: 31 c0 xor %eax,%eax
2: c3 ret
bool same5(const std::extents<int, dyn>& e1,
const std::extents<int, dyn, dyn>& e2)
{ return e1 == e2; }
0: 31 c0 xor %eax,%eax
2: c3 ret
+ else
+ {
+ for (size_t __i = 0; __i < __self.rank(); ++__i)
+ if (!cmp_equal(__self.extent(__i), __other.extent(__i)))
+ return false;
+ return true;
+ }
+ }
+
+ private:
+ using _S_storage = __mdspan::_ExtentsStorage<
+ _IndexType, array<size_t, sizeof...(_Extents)>{_Extents...}>;
+ [[no_unique_address]] _S_storage _M_dynamic_extents;
+
+ template<typename _OIndexType, size_t... _OExtents>
+ friend class extents;
+ };
+
+ namespace __mdspan
+ {
+ template<typename _IndexType, size_t... _Counts>
+ auto __build_dextents_type(integer_sequence<size_t, _Counts...>)
+ -> extents<_IndexType, ((void) _Counts, dynamic_extent)...>;
+
+ template<typename _Tp>
+ consteval size_t
+ __dynamic_extent() { return dynamic_extent; }
+ }
+
+ template<typename _IndexType, size_t _Rank>
+ using dextents =
decltype(__mdspan::__build_dextents_type<_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 930a489ff44..0df27cd7e7d 100644
--- a/libstdc++-v3/src/c++23/std.cc.in
+++ b/libstdc++-v3/src/c++23/std.cc.in
@@ -1833,7 +1833,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