On Fri, Apr 18, 2025 at 7:48 PM Luc Grosheintz <luc.groshei...@gmail.com> wrote:
> > On 4/18/25 2:00 PM, Tomasz Kaminski wrote: > > > > > > > > On Fri, Apr 18, 2025 at 1:43 PM Luc Grosheintz <luc.groshei...@gmail.com > > <mailto: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 <http://std.cc.in>: Add 'using > > std::extents'. > > > > Signed-off-by: Luc Grosheintz <luc.groshei...@gmail.com > > <mailto:luc.groshei...@gmail.com>> > > --- > > > > LGTM. > > Below, I shared one idea that I found interesting, and you could look > into, > > but not necessary. > > > > libstdc++-v3/include/std/mdspan | 249 > +++++++++++++++++++++++++++++++ > > libstdc++-v3/src/c++23/std.cc.in <http://std.cc.in> | 6 +- > > 2 files changed, 254 insertions(+), 1 deletion(-) > > > > diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/ > > std/mdspan > > index 4094a416d1e..f7a47552485 100644 > > --- a/libstdc++-v3/include/std/mdspan > > +++ b/libstdc++-v3/include/std/mdspan > > @@ -33,6 +33,11 @@ > > #pragma GCC system_header > > #endif > > > > +#include <span> > > +#include <array> > > +#include <type_traits> > > +#include <limits> > > + > > #define __glibcxx_want_mdspan > > #include <bits/version.h> > > > > @@ -41,6 +46,250 @@ > > namespace std _GLIBCXX_VISIBILITY(default) > > { > > _GLIBCXX_BEGIN_NAMESPACE_VERSION > > + namespace __mdspan > > + { > > + template<typename _IndexType, array _Extents> > > + class _ExtentsStorage > > + { > > + public: > > + static constexpr 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(); > > + > > + 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(); > > + > > + 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()); > > + } > > + > > + public: > > + template<typename _OIndexType, size_t... _OExtents> > > + requires (sizeof...(_OExtents) == rank()) > > + && ((_OExtents == dynamic_extent || _Extents == > > dynamic_extent > > + || _OExtents == _Extents) && ...) > > > > Let's imagine that we have a _S_is_compatible_function(e1, e2) that > > encapsulates this condition. > > return e1 == dynamic_extent || e2 == dynamic_extent || e1 == e2. > > Then ... > > > > + 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 (__self.rank() != __other.rank()) > > + return false; > > > > .. in operator== we could add check: > > if constexpr (!(_S_is_compatible(_OExtents, _Extends) && ...)) > > return false; > > This would avoid doing any runtime checks in some cases. > > Very nice observation. I was hoping that in the cases where > everything could be determined at compile time, e.g. > > std::extents<int, 1, 2>{} == std::extents<short, 1, 2>{} > > the compiler would be able to reduce the expression to `true`. > We could add: if constexpr (__self.rank() != __other.rank()) return ralse; else if constexpr (!(_S_is_compatible(_OExtents, _Extends) && ...)) return false; // N.B. Extents are compatible, so they are dynamic or static and equal else if (((_Extends != dynamic_extent) && ...)) return true; else { /// for each loop } > > I'd like to check the code the compiler generates in some of > these cases. Taken literally, I think the proposal doesn't go > far enough, because there's also cases in which we know at > compile time that the answer is `true` (not just `false`). > > > > > + > > + for (size_t __i = 0; __i < __self.rank(); ++__i) > > + if (__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, (_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 <http://std.cc.in> b/ > > libstdc++-v3/src/c++23/std.cc.in <http://std.cc.in> > > index 5e18ad73908..e42f54df20e 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> > > @@ -1831,7 +1831,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 > > > >
