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) && ...

>
>
> >>
> >> +         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
> >>
>
>

Reply via email to