path: root/libstdc++-v3/include/std/mdspan

// <mdspan> -*- C++ -*-

// Copyright The GNU Toolchain Authors.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file mdspan
 *  This is a Standard C++ Library header.
 */

#ifndef _GLIBCXX_MDSPAN
#define _GLIBCXX_MDSPAN 1

#ifdef _GLIBCXX_SYSHDR
#pragma GCC system_header
#endif

#include <span>
#include <array>
#include <type_traits>
#include <limits>
#include <utility>

#define __glibcxx_want_mdspan
#include <bits/version.h>

#ifdef __glibcxx_mdspan

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_dyn_exts.
	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_dyn_exts[_S_dynamic_index[__r]];
	  else
	    return __se;
	}

	template<size_t _OtherRank, typename _GetOtherExtent>
	  static constexpr bool
	  _S_is_compatible_extents(_GetOtherExtent __get_extent) noexcept
	  {
	    if constexpr (_OtherRank == _S_rank)
	      for (size_t __i = 0; __i < _S_rank; ++__i)
		if (_Extents[__i] != dynamic_extent
		    && !cmp_equal(_Extents[__i], _S_int_cast(__get_extent(__i))))
		  return false;
	    return true;
	  }

	template<size_t _OtherRank, typename _GetOtherExtent>
	  constexpr void
	  _M_init_dynamic_extents(_GetOtherExtent __get_extent) noexcept
	  {
	    __glibcxx_assert(_S_is_compatible_extents<_OtherRank>(__get_extent));
	    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_dyn_exts[__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]; });
	  }

	static constexpr span<const size_t>
	_S_static_extents(size_t __begin, size_t __end) noexcept
	{
	  return {_Extents.data() + __begin, _Extents.data() + __end};
	}

	constexpr span<const _IndexType>
	_M_dynamic_extents(size_t __begin, size_t __end) const noexcept
	requires (_Extents.size() > 0)
	{
	  return {_M_dyn_exts + _S_dynamic_index[__begin],
		  _M_dyn_exts + _S_dynamic_index[__end]};
	}

      private:
	using _S_storage = __array_traits<_IndexType, _S_rank_dynamic>::_Type;
	[[no_unique_address]] _S_storage _M_dyn_exts{};
      };

    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();
  }

  namespace __mdspan
  {
    template<typename _Extents>
      constexpr span<const size_t>
      __static_extents(size_t __begin = 0, size_t __end = _Extents::rank())
      noexcept
      { return _Extents::_S_storage::_S_static_extents(__begin, __end); }

    template<typename _Extents>
      constexpr span<const typename _Extents::index_type>
      __dynamic_extents(const _Extents& __exts, size_t __begin = 0,
			size_t __end = _Extents::rank()) noexcept
      {
	return __exts._M_exts._M_dynamic_extents(__begin, __end);
      }
  }

  template<typename _IndexType, size_t... _Extents>
    class extents
    {
      static_assert(__is_standard_integer<_IndexType>::value,
		    "IndexType must be a signed or unsigned integer type");
      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_exts._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
	    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_exts(__other._M_exts)
	{ }

      template<__mdspan::__valid_index_type<index_type>... _OIndexTypes>
	requires (sizeof...(_OIndexTypes) == rank()
		  || sizeof...(_OIndexTypes) == rank_dynamic())
	constexpr explicit extents(_OIndexTypes... __exts) noexcept
	: _M_exts(span<const _IndexType, sizeof...(_OIndexTypes)>(
	    initializer_list{static_cast<_IndexType>(std::move(__exts))...}))
	{ }

      template<typename _OIndexType, size_t _Nm>
	requires __mdspan::__valid_index_type<const _OIndexType&, index_type>
	  && (_Nm == rank() || _Nm == rank_dynamic())
	constexpr explicit(_Nm != rank_dynamic())
	extents(span<_OIndexType, _Nm> __exts) noexcept
	: _M_exts(span<const _OIndexType, _Nm>(__exts))
	{ }

      template<typename _OIndexType, size_t _Nm>
	requires __mdspan::__valid_index_type<const _OIndexType&, index_type>
	  && (_Nm == rank() || _Nm == rank_dynamic())
	constexpr explicit(_Nm != rank_dynamic())
	extents(const array<_OIndexType, _Nm>& __exts) noexcept
	: _M_exts(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;
	  else
	    {
	      for (size_t __i = 0; __i < __self.rank(); ++__i)
		if (!cmp_equal(__self.extent(__i), __other.extent(__i)))
		  return false;
	      return true;
	    }
	}

    private:
      friend span<const size_t>
      __mdspan::__static_extents<extents>(size_t, size_t);

      friend span<const index_type>
      __mdspan::__dynamic_extents<extents>(const extents&, size_t, size_t);

      using _S_storage = __mdspan::_ExtentsStorage<
	_IndexType, array<size_t, sizeof...(_Extents)>{_Extents...}>;
      [[no_unique_address]] _S_storage _M_exts;

      template<typename _OIndexType, size_t... _OExtents>
	friend class extents;
    };

  namespace __mdspan
  {
    template<typename _Tp, size_t _Nm>
      constexpr bool
      __contains_zero(span<_Tp, _Nm> __exts) noexcept
      {
	for (size_t __i = 0; __i < __exts.size(); ++__i)
	  if (__exts[__i] == 0)
	    return true;
	return false;
      }

    template<typename _Extents>
      constexpr bool
      __empty(const _Extents& __exts) noexcept
      {
	if constexpr (__contains_zero(__static_extents<_Extents>()))
	  return true;
	else if constexpr (_Extents::rank_dynamic() > 0)
	  return __contains_zero(__dynamic_extents(__exts));
	else
	  return false;
      }

    constexpr size_t
    __static_extents_prod(const auto& __sta_exts) noexcept
    {
      size_t __ret = 1;
      for (auto __factor : __sta_exts)
	if (__factor != dynamic_extent)
	  __ret *= __factor;
      return __ret;
    }

    template<typename _Extents>
      constexpr typename _Extents::index_type
      __exts_prod(const _Extents& __exts, size_t __begin, size_t __end) noexcept
      {
	using _IndexType = typename _Extents::index_type;

	size_t __ret = 1;
	if constexpr (_Extents::rank_dynamic() != _Extents::rank())
	  {
	    auto __sta_exts = __static_extents<_Extents>(__begin, __end);
	    __ret = __static_extents_prod(__sta_exts);
	    if (__ret == 0)
	      return 0;
	  }

	if constexpr (_Extents::rank_dynamic() > 0)
	  for (auto __factor : __dynamic_extents(__exts, __begin, __end))
	    __ret *= size_t(__factor);
	return _IndexType(__ret);
      }

    template<typename _Extents>
      constexpr typename _Extents::index_type
      __fwd_prod(const _Extents& __exts, size_t __r) noexcept
      { return __exts_prod(__exts, 0, __r); }

    template<typename _Extents>
      constexpr typename _Extents::index_type
      __rev_prod(const _Extents& __exts, size_t __r) noexcept
      { return __exts_prod(__exts, __r + 1, __exts.rank()); }

    template<typename _Extents>
      constexpr typename _Extents::index_type
      __size(const _Extents& __exts) noexcept
      { return __fwd_prod(__exts, __exts.rank()); }

    template<typename _IndexType, size_t... _Counts>
      auto __build_dextents_type(integer_sequence<size_t, _Counts...>)
	-> extents<_IndexType, ((void) _Counts, 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, __detail::__maybe_static_ext<_Integrals>...>;

  struct layout_left
  {
    template<typename _Extents>
      class mapping;
  };

  struct layout_right
  {
    template<typename _Extents>
      class mapping;
  };

  struct layout_stride
  {
    template<typename _Extents>
      class mapping;
  };

  namespace __mdspan
  {
    template<typename _Tp>
      constexpr bool __is_extents = false;

    template<typename _IndexType, size_t... _Extents>
      constexpr bool __is_extents<extents<_IndexType, _Extents...>> = true;

    template<typename _Extents, typename... _Indices>
      constexpr typename _Extents::index_type
      __linear_index_left(const _Extents& __exts, _Indices... __indices)
      noexcept
      {
	using _IndexType = typename _Extents::index_type;
	_IndexType __res = 0;
	if constexpr (sizeof...(__indices) > 0)
	  {
	    _IndexType __mult = 1;
	    auto __update = [&, __pos = 0u](_IndexType __idx) mutable
	      {
		_GLIBCXX_DEBUG_ASSERT(cmp_less(__idx, __exts.extent(__pos)));
		__res += __idx * __mult;
		__mult *= __exts.extent(__pos);
		++__pos;
	      };
	    (__update(__indices), ...);
	  }
	return __res;
      }

    template<typename _Extents,
             typename _IndexType = typename _Extents::index_type>
      consteval _IndexType
      __static_quotient(_IndexType __nom = numeric_limits<_IndexType>::max())
      {
	auto __sta_exts = __static_extents<_Extents>();
	for (auto __factor : __sta_exts)
	  {
	    if (__factor != dynamic_extent)
	      __nom /= _IndexType(__factor);
	    if (__nom == 0)
	      break;
	  }
	return __nom;
      }

    template<typename _Extents>
      constexpr bool
      __is_representable_extents(const _Extents& __exts) noexcept
      {
	using _IndexType = _Extents::index_type;

	if constexpr (__contains_zero(__static_extents<_Extents>()))
	  return true;
	else
	  {
	    constexpr auto __sta_quo = __static_quotient<_Extents>();
	    if constexpr (_Extents::rank_dynamic() == 0)
	      return __sta_quo != 0;
	    else
	      {
		auto __dyn_exts = __dynamic_extents(__exts);
		if (__contains_zero(__dyn_exts))
		  return true;

		if constexpr (__sta_quo == 0)
		  return false;
		else
		  {
		    auto __dyn_quo = _IndexType(__sta_quo);
		    for (auto __factor : __dyn_exts)
		      {
			__dyn_quo /= __factor;
			if (__dyn_quo == 0)
			  return false;
		      }
		    return true;
		  }
	      }
	  }
      }

    template<typename _Extents, typename _IndexType>
      concept __representable_size = _Extents::rank_dynamic() != 0
	|| __contains_zero(__static_extents<_Extents>())
	|| (__static_quotient<_Extents, _IndexType>() != 0);

    template<typename _Layout, typename _Mapping>
      concept __mapping_of =
	is_same_v<typename _Layout::template mapping<typename _Mapping::extents_type>,
		  _Mapping>;

    template<typename _Mapping>
      concept __standardized_mapping = __mapping_of<layout_left, _Mapping>
				       || __mapping_of<layout_right, _Mapping>
				       || __mapping_of<layout_stride, _Mapping>;

    // A tag type to create internal ctors.
    class __internal_ctor
    { };
  }

  template<typename _Extents>
    class layout_left::mapping
    {
    public:
      using extents_type = _Extents;
      using index_type = typename extents_type::index_type;
      using size_type = typename extents_type::size_type;
      using rank_type = typename extents_type::rank_type;
      using layout_type = layout_left;

      static_assert(__mdspan::__representable_size<extents_type, index_type>,
	"The size of extents_type must be representable as index_type");

      constexpr
      mapping() noexcept = default;

      constexpr
      mapping(const mapping&) noexcept = default;

      constexpr
      mapping(const extents_type& __extents) noexcept
      : _M_extents(__extents)
      { __glibcxx_assert(__mdspan::__is_representable_extents(_M_extents)); }

      template<typename _OExtents>
	requires is_constructible_v<extents_type, _OExtents>
	constexpr explicit(!is_convertible_v<_OExtents, extents_type>)
	mapping(const mapping<_OExtents>& __other) noexcept
	: mapping(__other.extents(), __mdspan::__internal_ctor{})
	{ }

      template<typename _OExtents>
	requires (extents_type::rank() <= 1)
		  && is_constructible_v<extents_type, _OExtents>
	constexpr explicit(!is_convertible_v<_OExtents, extents_type>)
	mapping(const layout_right::mapping<_OExtents>& __other) noexcept
	: mapping(__other.extents(), __mdspan::__internal_ctor{})
	{ }

      // noexcept for consistency with other layouts.
      template<typename _OExtents>
	requires is_constructible_v<extents_type, _OExtents>
	constexpr explicit(extents_type::rank() > 0)
	mapping(const layout_stride::mapping<_OExtents>& __other) noexcept
	: mapping(__other.extents(), __mdspan::__internal_ctor{})
	{ __glibcxx_assert(*this == __other); }

      constexpr mapping&
      operator=(const mapping&) noexcept = default;

      constexpr const extents_type&
      extents() const noexcept { return _M_extents; }

      constexpr index_type
      required_span_size() const noexcept
      { return __mdspan::__size(_M_extents); }

      template<__mdspan::__valid_index_type<index_type>... _Indices>
	requires (sizeof...(_Indices) == extents_type::rank())
	constexpr index_type
	operator()(_Indices... __indices) const noexcept
	{
	  return __mdspan::__linear_index_left(_M_extents,
	    static_cast<index_type>(std::move(__indices))...);
	}

      static constexpr bool
      is_always_unique() noexcept { return true; }

      static constexpr bool
      is_always_exhaustive() noexcept { return true; }

      static constexpr bool
      is_always_strided() noexcept { return true; }

      static constexpr bool
      is_unique() noexcept { return true; }

      static constexpr bool
      is_exhaustive() noexcept { return true; }

      static constexpr bool
      is_strided() noexcept { return true; }

      constexpr index_type
      stride(rank_type __i) const noexcept
      requires (extents_type::rank() > 0)
      {
	__glibcxx_assert(__i < extents_type::rank());
	return __mdspan::__fwd_prod(_M_extents, __i);
      }

      template<typename _OExtents>
	requires (extents_type::rank() == _OExtents::rank())
	friend constexpr bool
	operator==(const mapping& __self, const mapping<_OExtents>& __other)
	noexcept
	{ return __self.extents() == __other.extents(); }

    private:
      template<typename _OExtents>
	constexpr explicit
	mapping(const _OExtents& __oexts, __mdspan::__internal_ctor) noexcept
	: _M_extents(__oexts)
	{
	  static_assert(__mdspan::__representable_size<_OExtents, index_type>,
	    "The size of OtherExtents must be representable as index_type");
	  __glibcxx_assert(__mdspan::__is_representable_extents(_M_extents));
	}

	[[no_unique_address]] extents_type _M_extents{};
    };

  namespace __mdspan
  {
    template<typename _Extents, typename... _Indices>
      constexpr typename _Extents::index_type
      __linear_index_right(const _Extents& __exts, _Indices... __indices)
      noexcept
      {
	using _IndexType = typename _Extents::index_type;
	array<_IndexType, sizeof...(__indices)> __ind_arr{__indices...};
	_IndexType __res = 0;
	if constexpr (sizeof...(__indices) > 0)
	  {
	    _IndexType __mult = 1;
	    auto __update = [&, __pos = __exts.rank()](_IndexType) mutable
	      {
		--__pos;
		_GLIBCXX_DEBUG_ASSERT(cmp_less(__ind_arr[__pos],
					       __exts.extent(__pos)));
		__res += __ind_arr[__pos] * __mult;
		__mult *= __exts.extent(__pos);
	      };
	    (__update(__indices), ...);
	  }
	return __res;
      }
  }

  template<typename _Extents>
    class layout_right::mapping
    {
    public:
      using extents_type = _Extents;
      using index_type = typename extents_type::index_type;
      using size_type = typename extents_type::size_type;
      using rank_type = typename extents_type::rank_type;
      using layout_type = layout_right;

      static_assert(__mdspan::__representable_size<extents_type, index_type>,
	"The size of extents_type must be representable as index_type");

      constexpr
      mapping() noexcept = default;

      constexpr
      mapping(const mapping&) noexcept = default;

      constexpr
      mapping(const extents_type& __extents) noexcept
      : _M_extents(__extents)
      { __glibcxx_assert(__mdspan::__is_representable_extents(_M_extents)); }

      template<typename _OExtents>
	requires is_constructible_v<extents_type, _OExtents>
	constexpr explicit(!is_convertible_v<_OExtents, extents_type>)
	mapping(const mapping<_OExtents>& __other) noexcept
	: mapping(__other.extents(), __mdspan::__internal_ctor{})
	{ }

      template<typename _OExtents>
	requires (extents_type::rank() <= 1)
	    && is_constructible_v<extents_type, _OExtents>
	constexpr explicit(!is_convertible_v<_OExtents, extents_type>)
	mapping(const layout_left::mapping<_OExtents>& __other) noexcept
	: mapping(__other.extents(), __mdspan::__internal_ctor{})
	{ }

      template<typename _OExtents>
	requires is_constructible_v<extents_type, _OExtents>
	constexpr explicit(extents_type::rank() > 0)
	mapping(const layout_stride::mapping<_OExtents>& __other) noexcept
	: mapping(__other.extents(), __mdspan::__internal_ctor{})
	{ __glibcxx_assert(*this == __other); }

      constexpr mapping&
      operator=(const mapping&) noexcept = default;

      constexpr const extents_type&
      extents() const noexcept { return _M_extents; }

      constexpr index_type
      required_span_size() const noexcept
      { return __mdspan::__size(_M_extents); }

      template<__mdspan::__valid_index_type<index_type>... _Indices>
	requires (sizeof...(_Indices) == extents_type::rank())
	constexpr index_type
	operator()(_Indices... __indices) const noexcept
	{
	  return __mdspan::__linear_index_right(
	    _M_extents, static_cast<index_type>(std::move(__indices))...);
	}

      static constexpr bool
      is_always_unique() noexcept
      { return true; }

      static constexpr bool
      is_always_exhaustive() noexcept
      { return true; }

      static constexpr bool
      is_always_strided() noexcept
      { return true; }

      static constexpr bool
      is_unique() noexcept
      { return true; }

      static constexpr bool
      is_exhaustive() noexcept
      { return true; }

      static constexpr bool
      is_strided() noexcept
      { return true; }

      constexpr index_type
      stride(rank_type __i) const noexcept
      requires (extents_type::rank() > 0)
      {
	__glibcxx_assert(__i < extents_type::rank());
	return __mdspan::__rev_prod(_M_extents, __i);
      }

      template<typename _OExtents>
	requires (extents_type::rank() == _OExtents::rank())
	friend constexpr bool
	operator==(const mapping& __self, const mapping<_OExtents>& __other)
	noexcept
	{ return __self.extents() == __other.extents(); }

    private:
      template<typename _OExtents>
	constexpr explicit
	mapping(const _OExtents& __oexts, __mdspan::__internal_ctor) noexcept
	: _M_extents(__oexts)
	{
	  static_assert(__mdspan::__representable_size<_OExtents, index_type>,
	    "The size of OtherExtents must be representable as index_type");
	  __glibcxx_assert(__mdspan::__is_representable_extents(_M_extents));
	}

	[[no_unique_address]] extents_type _M_extents{};
    };

  namespace __mdspan
  {
    template<typename _Mp>
      concept __mapping_alike = requires
      {
	requires __is_extents<typename _Mp::extents_type>;
	{ _Mp::is_always_strided() } -> same_as<bool>;
	{ _Mp::is_always_exhaustive() } -> same_as<bool>;
	{ _Mp::is_always_unique() } -> same_as<bool>;
	bool_constant<_Mp::is_always_strided()>::value;
	bool_constant<_Mp::is_always_exhaustive()>::value;
	bool_constant<_Mp::is_always_unique()>::value;
      };

    template<typename _Mapping>
      constexpr typename _Mapping::index_type
      __offset(const _Mapping& __m) noexcept
      {
	using _IndexType = typename _Mapping::index_type;
	constexpr auto __rank = _Mapping::extents_type::rank();

	if constexpr (__standardized_mapping<_Mapping>)
	  return 0;
	else if (__empty(__m.extents()))
	  return 0;
	else
	  {
	    auto __impl = [&__m]<size_t... _Counts>(index_sequence<_Counts...>)
	      { return __m(((void) _Counts, _IndexType(0))...); };
	    return __impl(make_index_sequence<__rank>());
	  }
      }

    template<typename _Mapping, typename... _Indices>
      constexpr typename _Mapping::index_type
      __linear_index_strides(const _Mapping& __m, _Indices... __indices)
      noexcept
      {
	using _IndexType = typename _Mapping::index_type;
	_IndexType __res = 0;
	if constexpr (sizeof...(__indices) > 0)
	  {
	    auto __update = [&, __pos = 0u](_IndexType __idx) mutable
	      {
		_GLIBCXX_DEBUG_ASSERT(cmp_less(__idx,
					       __m.extents().extent(__pos)));
		__res += __idx * __m.stride(__pos++);
	      };
	    (__update(__indices), ...);
	  }
	return __res;
      }
  }

  template<typename _Extents>
    class layout_stride::mapping
    {
    public:
      using extents_type = _Extents;
      using index_type = typename extents_type::index_type;
      using size_type = typename extents_type::size_type;
      using rank_type = typename extents_type::rank_type;
      using layout_type = layout_stride;

      static_assert(__mdspan::__representable_size<extents_type, index_type>,
	"The size of extents_type must be representable as index_type");

      constexpr
      mapping() noexcept
      {
	// The precondition is either statically asserted, or automatically
	// satisfied because dynamic extents are zero-initialized.
	size_t __stride = 1;
	for (size_t __i = extents_type::rank(); __i > 0; --__i)
	  {
	    _M_strides[__i - 1] = index_type(__stride);
	    __stride *= size_t(_M_extents.extent(__i - 1));
	  }
      }

      constexpr
      mapping(const mapping&) noexcept = default;

      template<typename _OIndexType>
	requires __mdspan::__valid_index_type<const _OIndexType&, index_type>
	constexpr
	mapping(const extents_type& __exts,
		span<_OIndexType, extents_type::rank()> __strides) noexcept
	: _M_extents(__exts)
	{
	  for (size_t __i = 0; __i < extents_type::rank(); ++__i)
	    _M_strides[__i] = index_type(as_const(__strides[__i]));
	}

      template<typename _OIndexType>
	requires __mdspan::__valid_index_type<const _OIndexType&, index_type>
	constexpr
	mapping(const extents_type& __exts,
		const array<_OIndexType, extents_type::rank()>& __strides)
	noexcept
	: mapping(__exts,
		  span<const _OIndexType, extents_type::rank()>(__strides))
	{ }

      template<__mdspan::__mapping_alike _StridedMapping>
	requires (is_constructible_v<extents_type,
				     typename _StridedMapping::extents_type>
		  && _StridedMapping::is_always_unique()
		  && _StridedMapping::is_always_strided())
	constexpr explicit(!(
	  is_convertible_v<typename _StridedMapping::extents_type, extents_type>
	  && __mdspan::__standardized_mapping<_StridedMapping>))
	mapping(const _StridedMapping& __other) noexcept
	: _M_extents(__other.extents())
	{
	  using _OIndexType = _StridedMapping::index_type;
	  using _OExtents = _StridedMapping::extents_type;

	  __glibcxx_assert(__mdspan::__offset(__other) == 0);
	  static_assert(__mdspan::__representable_size<_OExtents, index_type>,
	    "The size of StridedMapping::extents_type must be representable as"
	    " index_type");
	  if constexpr (cmp_greater(numeric_limits<_OIndexType>::max(),
				    numeric_limits<index_type>::max()))
	    __glibcxx_assert(!cmp_less(numeric_limits<index_type>::max(),
				       __other.required_span_size())
		&& "other.required_span_size() must be representable"
		   " as index_type");
	  if constexpr (extents_type::rank() > 0)
	    for (size_t __i = 0; __i < extents_type::rank(); ++__i)
	      _M_strides[__i] = index_type(__other.stride(__i));
	}

      constexpr mapping&
      operator=(const mapping&) noexcept = default;

      constexpr const extents_type&
      extents() const noexcept { return _M_extents; }

      constexpr array<index_type, extents_type::rank()>
      strides() const noexcept
      {
	array<index_type, extents_type::rank()> __ret;
	for (size_t __i = 0; __i < extents_type::rank(); ++__i)
	  __ret[__i] = _M_strides[__i];
	return __ret;
      }

      constexpr index_type
      required_span_size() const noexcept
      {
	if (__mdspan::__empty(_M_extents))
	  return 0;

	index_type __ret = 1;
	for (size_t __i = 0; __i < extents_type::rank(); ++__i)
	  __ret += (_M_extents.extent(__i) - 1) * _M_strides[__i];
	return __ret;
      }

      template<__mdspan::__valid_index_type<index_type>... _Indices>
	requires (sizeof...(_Indices) == extents_type::rank())
	constexpr index_type
	operator()(_Indices... __indices) const noexcept
	{
	  return __mdspan::__linear_index_strides(*this,
	    static_cast<index_type>(std::move(__indices))...);
	}

      static constexpr bool
      is_always_unique() noexcept { return true; }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 4266. layout_stride::mapping should treat empty mappings as exhaustive
      static constexpr bool
      is_always_exhaustive() noexcept
      {
	return (_Extents::rank() == 0) || __mdspan::__contains_zero(
	    __mdspan::__static_extents<extents_type>());
      }

      static constexpr bool
      is_always_strided() noexcept { return true; }

      static constexpr bool
      is_unique() noexcept { return true; }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 4266. layout_stride::mapping should treat empty mappings as exhaustive
      constexpr bool
      is_exhaustive() const noexcept
      {
	if constexpr (!is_always_exhaustive())
	  {
	    auto __size = __mdspan::__size(_M_extents);
	    if(__size > 0)
	      return __size == required_span_size();
	  }
	return true;
      }

      static constexpr bool
      is_strided() noexcept { return true; }

      constexpr index_type
      stride(rank_type __r) const noexcept { return _M_strides[__r]; }

      template<__mdspan::__mapping_alike _OMapping>
	requires ((extents_type::rank() == _OMapping::extents_type::rank())
		  && _OMapping::is_always_strided())
	friend constexpr bool
	operator==(const mapping& __self, const _OMapping& __other) noexcept
	{
	  if (__self.extents() != __other.extents())
	    return false;
	  if constexpr (extents_type::rank() > 0)
	    for (size_t __i = 0; __i < extents_type::rank(); ++__i)
	      if (!cmp_equal(__self.stride(__i), __other.stride(__i)))
		return false;
	  return __mdspan::__offset(__other) == 0;
	}

    private:
      using _S_strides_t = typename __array_traits<index_type,
						   extents_type::rank()>::_Type;
      [[no_unique_address]] extents_type _M_extents;
      [[no_unique_address]] _S_strides_t _M_strides;
    };

  template<typename _ElementType>
    struct default_accessor
    {
      static_assert(!is_array_v<_ElementType>,
	"ElementType must not be an array type");
      static_assert(!is_abstract_v<_ElementType>,
	"ElementType must not be an abstract class type");

      using offset_policy = default_accessor;
      using element_type = _ElementType;
      using reference = element_type&;
      using data_handle_type = element_type*;

      constexpr
      default_accessor() noexcept = default;

      template<typename _OElementType>
	requires is_convertible_v<_OElementType(*)[], element_type(*)[]>
	constexpr
	default_accessor(default_accessor<_OElementType>) noexcept
	{ }

      constexpr reference
      access(data_handle_type __p, size_t __i) const noexcept
      { return __p[__i]; }

      constexpr data_handle_type
      offset(data_handle_type __p, size_t __i) const noexcept
      { return __p + __i; }
    };

  namespace __mdspan
  {
    template<typename _Extents, typename _IndexType, size_t _Nm>
      constexpr bool
      __is_multi_index(const _Extents& __exts, span<_IndexType, _Nm> __indices)
      {
	static_assert(__exts.rank() == _Nm);
	for (size_t __i = 0; __i < __exts.rank(); ++__i)
	  if (__indices[__i] >= __exts.extent(__i))
	    return false;
	return true;
      }
  }

  template<typename _ElementType, typename _Extents,
	   typename _LayoutPolicy = layout_right,
	   typename _AccessorPolicy = default_accessor<_ElementType>>
    class mdspan
    {
      static_assert(!is_array_v<_ElementType>,
	"ElementType must not be an array type");
      static_assert(!is_abstract_v<_ElementType>,
	"ElementType must not be an abstract class type");
      static_assert(__mdspan::__is_extents<_Extents>,
	"Extents must be a specialization of std::extents");
      static_assert(is_same_v<_ElementType,
			      typename _AccessorPolicy::element_type>);

    public:
      using extents_type = _Extents;
      using layout_type = _LayoutPolicy;
      using accessor_type = _AccessorPolicy;
      using mapping_type = typename layout_type::template mapping<extents_type>;
      using element_type = _ElementType;
      using value_type = remove_cv_t<element_type>;
      using index_type = typename extents_type::index_type;
      using size_type = typename extents_type::size_type;
      using rank_type = typename extents_type::rank_type;
      using data_handle_type = typename accessor_type::data_handle_type;
      using reference = typename accessor_type::reference;

      static constexpr rank_type
      rank() noexcept { return extents_type::rank(); }

      static constexpr rank_type
      rank_dynamic() noexcept { return extents_type::rank_dynamic(); }

      static constexpr size_t
      static_extent(rank_type __r) noexcept
      { return extents_type::static_extent(__r); }

      constexpr index_type
      extent(rank_type __r) const noexcept { return extents().extent(__r); }

      constexpr
      mdspan()
      requires (rank_dynamic() > 0)
	  && is_default_constructible_v<data_handle_type>
	  && is_default_constructible_v<mapping_type>
	  && is_default_constructible_v<accessor_type> = default;

      constexpr
      mdspan(const mdspan& __other) = default;

      constexpr
      mdspan(mdspan&& __other) = default;

      template<__mdspan::__valid_index_type<index_type>... _OIndexTypes>
	requires (sizeof...(_OIndexTypes) == rank()
		   || sizeof...(_OIndexTypes) == rank_dynamic())
		 && is_constructible_v<mapping_type, extents_type>
		 && is_default_constructible_v<accessor_type>
	constexpr explicit
	mdspan(data_handle_type __handle, _OIndexTypes... __exts)
	: _M_accessor(),
	  _M_mapping(_Extents(static_cast<index_type>(std::move(__exts))...)),
	  _M_handle(std::move(__handle))
	{ }

      template<typename _OIndexType, size_t _Nm>
	requires __mdspan::__valid_index_type<const _OIndexType&, index_type>
		 && (_Nm == rank() || _Nm == rank_dynamic())
		 && is_constructible_v<mapping_type, extents_type>
		 && is_default_constructible_v<accessor_type>
	constexpr explicit(_Nm != rank_dynamic())
	mdspan(data_handle_type __handle, span<_OIndexType, _Nm> __exts)
	: _M_accessor(), _M_mapping(extents_type(__exts)),
	  _M_handle(std::move(__handle))
	{ }

      template<typename _OIndexType, size_t _Nm>
	requires __mdspan::__valid_index_type<const _OIndexType&, index_type>
		 && (_Nm == rank() || _Nm == rank_dynamic())
		 && is_constructible_v<mapping_type, extents_type>
		 && is_default_constructible_v<accessor_type>
	constexpr explicit(_Nm != rank_dynamic())
	mdspan(data_handle_type __handle, const array<_OIndexType, _Nm>& __exts)
	: _M_accessor(), _M_mapping(extents_type(__exts)),
	  _M_handle(std::move(__handle))
	{ }

      constexpr
      mdspan(data_handle_type __handle, const extents_type& __exts)
      requires is_constructible_v<mapping_type, const extents_type&>
	       && is_default_constructible_v<accessor_type>
      : _M_accessor(), _M_mapping(__exts), _M_handle(std::move(__handle))
      { }

      constexpr
      mdspan(data_handle_type __handle, const mapping_type& __mapping)
      requires is_default_constructible_v<accessor_type>
      : _M_accessor(), _M_mapping(__mapping), _M_handle(std::move(__handle))
      { }

      constexpr
      mdspan(data_handle_type __handle, const mapping_type& __mapping,
	     const accessor_type& __accessor)
      : _M_accessor(__accessor), _M_mapping(__mapping),
        _M_handle(std::move(__handle))
      { }

      template<typename _OElementType, typename _OExtents, typename _OLayout,
	       typename _OAccessor>
	requires is_constructible_v<mapping_type,
	      const typename _OLayout::template mapping<_OExtents>&>
	  && is_constructible_v<accessor_type, const _OAccessor&>
	constexpr explicit(!is_convertible_v<
	    const typename _OLayout::template mapping<_OExtents>&, mapping_type>
	  || !is_convertible_v<const _OAccessor&, accessor_type>)
	mdspan(const mdspan<_OElementType, _OExtents, _OLayout, _OAccessor>&
		 __other)
	: _M_accessor(__other.accessor()), _M_mapping(__other.mapping()),
	  _M_handle(__other.data_handle())
	{
	  static_assert(is_constructible_v<data_handle_type,
	      const typename _OAccessor::data_handle_type&>);
	  static_assert(is_constructible_v<extents_type, _OExtents>);
	}

      constexpr mdspan&
      operator=(const mdspan& __other) = default;

      constexpr mdspan&
      operator=(mdspan&& __other) = default;

      template<__mdspan::__valid_index_type<index_type>... _OIndexTypes>
	requires (sizeof...(_OIndexTypes) == rank())
	constexpr reference
	operator[](_OIndexTypes... __indices) const
	{
	  auto __checked_call = [this](auto... __idxs) -> index_type
	    {
	      if constexpr (sizeof...(__idxs) > 0)
		__glibcxx_assert(__mdspan::__is_multi_index(extents(),
		  span<const index_type, sizeof...(__idxs)>({__idxs...})));
	      return _M_mapping(__idxs...);
	    };

	  auto __index = __checked_call(
	    static_cast<index_type>(std::move(__indices))...);
	  return _M_accessor.access(_M_handle, __index);
	}

      template<typename _OIndexType>
	requires __mdspan::__valid_index_type<const _OIndexType&, index_type>
	constexpr reference
	operator[](span<_OIndexType, rank()> __indices) const
	{
	  auto __call = [&]<size_t... _Counts>(index_sequence<_Counts...>)
	    -> reference
	    { return (*this)[index_type(as_const(__indices[_Counts]))...]; };
	  return __call(make_index_sequence<rank()>());
	}

      template<typename _OIndexType>
	requires __mdspan::__valid_index_type<const _OIndexType&, index_type>
	constexpr reference
	operator[](const array<_OIndexType, rank()>& __indices) const
	{ return (*this)[span<const _OIndexType, rank()>(__indices)]; }

      constexpr size_type
      size() const noexcept
      {
	__glibcxx_assert(cmp_less_equal(_M_mapping.required_span_size(),
					numeric_limits<size_t>::max()));
	return size_type(__mdspan::__size(extents()));
      }

      [[nodiscard]]
      constexpr bool
      empty() const noexcept
      {
	return __mdspan::__empty(extents());
      }

      friend constexpr void
      swap(mdspan& __x, mdspan& __y) noexcept
      {
	using std::swap;
	swap(__x._M_mapping, __y._M_mapping);
	swap(__x._M_accessor, __y._M_accessor);
	swap(__x._M_handle, __y._M_handle);
      }

      constexpr const extents_type&
      extents() const noexcept { return _M_mapping.extents(); }

      constexpr const data_handle_type&
      data_handle() const noexcept { return _M_handle; }

      constexpr const mapping_type&
      mapping() const noexcept { return _M_mapping; }

      constexpr const accessor_type&
      accessor() const noexcept { return _M_accessor; }

      // Strengthened noexcept for all `is_*` methods.

      static constexpr bool
      is_always_unique() noexcept(noexcept(mapping_type::is_always_unique()))
      { return mapping_type::is_always_unique(); }

      static constexpr bool
      is_always_exhaustive()
      noexcept(noexcept(mapping_type::is_always_exhaustive()))
      { return mapping_type::is_always_exhaustive(); }

      static constexpr bool
      is_always_strided()
      noexcept(noexcept(mapping_type::is_always_strided()))
      { return mapping_type::is_always_strided(); }

      constexpr bool
      is_unique() const noexcept(noexcept(_M_mapping.is_unique()))
      { return _M_mapping.is_unique(); }

      constexpr bool
      is_exhaustive() const noexcept(noexcept(_M_mapping.is_exhaustive()))
      { return _M_mapping.is_exhaustive(); }

      constexpr bool
      is_strided() const noexcept(noexcept(_M_mapping.is_strided()))
      { return _M_mapping. is_strided(); }

      constexpr index_type
      stride(rank_type __r) const { return _M_mapping.stride(__r); }

    private:
      [[no_unique_address]] accessor_type _M_accessor = accessor_type();
      [[no_unique_address]] mapping_type _M_mapping = mapping_type();
      [[no_unique_address]] data_handle_type _M_handle = data_handle_type();
    };

  template<typename _CArray>
    requires is_array_v<_CArray> && (rank_v<_CArray> == 1)
    mdspan(_CArray&)
    -> mdspan<remove_all_extents_t<_CArray>,
	      extents<size_t, extent_v<_CArray, 0>>>;

  template<typename _Pointer>
    requires is_pointer_v<remove_reference_t<_Pointer>>
    mdspan(_Pointer&&)
    -> mdspan<remove_pointer_t<remove_reference_t<_Pointer>>, extents<size_t>>;

  template<typename _ElementType, typename... _Integrals>
    requires (is_convertible_v<_Integrals, size_t> && ...)
	      && (sizeof...(_Integrals) > 0)
    explicit mdspan(_ElementType*, _Integrals...)
    -> mdspan<_ElementType,
	      extents<size_t, __detail::__maybe_static_ext<_Integrals>...>>;

  template<typename _ElementType, typename _OIndexType, size_t _Nm>
    mdspan(_ElementType*, span<_OIndexType, _Nm>)
    -> mdspan<_ElementType, dextents<size_t, _Nm>>;

  template<typename _ElementType, typename _OIndexType, size_t _Nm>
    mdspan(_ElementType*, const array<_OIndexType, _Nm>&)
    -> mdspan<_ElementType, dextents<size_t, _Nm>>;

  template<typename _ElementType, typename _IndexType, size_t... _ExtentsPack>
    mdspan(_ElementType*, const extents<_IndexType, _ExtentsPack...>&)
    -> mdspan<_ElementType, extents<_IndexType, _ExtentsPack...>>;

  template<typename _ElementType, typename _MappingType>
    mdspan(_ElementType*, const _MappingType&)
    -> mdspan<_ElementType, typename _MappingType::extents_type,
	      typename _MappingType::layout_type>;

  template<typename _MappingType, typename _AccessorType>
    mdspan(const typename _AccessorType::data_handle_type&, const _MappingType&,
	   const _AccessorType&)
    -> mdspan<typename _AccessorType::element_type,
	      typename _MappingType::extents_type,
	      typename _MappingType::layout_type, _AccessorType>;

_GLIBCXX_END_NAMESPACE_VERSION
}
#endif
#endif