On Tue, Jul 7, 2026 at 12:21 PM Tomasz Kamiński <[email protected]> wrote:
> This add an assertions checking if the combination of strides
> and extents passed to layout_stride::mapping is unique.
>
> To avoid excessive performance impact, in non-debug mode only
> checks that are are O(rank) (i.e. similar cost as operator())
> are performed. To achieve that, for the ranks greater or equal,
> we perform two separate checks:
> * required_span_size() > mdspan::__size(_M_extents) - this is
> required by not sufficient condition, that is O(rank) and
> is always performed.
> * building an permutation using selection-sort based algorithm,
> this is O(rank^2) and is performed only in debug modes.
>
> The check for non-zero stride values (performed for all non-zero
> ranks) is done only if the size of the multidimensional index space
> is not empty. This follows the resolution of LWG4603, and provides
> consistent behavior for constructing layout_stride mapping from
> layout_left/right directly or from strides extracted from it.
>
> libstdc++-v3/ChangeLog:
>
> * include/std/mdspan (layout_stride::mapping::_M_check_unique):
> Define.
> (layout_stride::mapping(const extents_type&, span<....>):
> Add __glibcxx_assert on _M_check_unique.
> * testsuite/23_containers/mdspan/layouts/stride_neg.cc:
> Test for the new added assertions.
> ---
> Are we OK with full detection only for ranks <= 2 and some subset of
> problematic layouts with rank >= 3? I think this is good sweet spot.
> But I see how some may argue for consistency here, but then I would
> put unique dection only in debug for all ranks.
>
> Tested on x86_64-linux locally. *mdspan* test passed in all standard
> modes and with _GLIBCXX_DEBUG. OK for trunk?
>
> libstdc++-v3/include/std/mdspan | 83 ++++++++++++++++++-
> .../mdspan/layouts/stride_neg.cc | 42 ++++++++++
> 2 files changed, 123 insertions(+), 2 deletions(-)
>
> diff --git a/libstdc++-v3/include/std/mdspan
> b/libstdc++-v3/include/std/mdspan
> index 5e1c4d8b1a4..69dbe091884 100644
> --- a/libstdc++-v3/include/std/mdspan
> +++ b/libstdc++-v3/include/std/mdspan
> @@ -1893,6 +1893,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> for (size_t __i = 0; __i < extents_type::rank(); ++__i)
> _M_strides[__i]
> = __mdspan::__index_type_cast<index_type>(__strides[__i]);
> +
> + __glibcxx_assert(_M_check_unique());
> }
>
> template<typename _OIndexType>
> @@ -2027,6 +2029,85 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> }
>
> private:
> + using _Strides = typename __array_traits<index_type,
> +
> extents_type::rank()>::_Type;
> +
> + constexpr bool
> + _M_check_unique() const
> + {
> + constexpr size_t __rank = extents_type::rank();
> + if constexpr (__rank == 0)
> + return true;
> + // _GLIBCXX_RESOLVE_LIB_DEFECTS
> + // 4603. `layout_stride` should accept zero strides for empty
> `extents`
> + else if (__mdspan::__empty(_M_extents))
> + return true;
> + else if constexpr (__rank == 1)
> + return _M_strides[0] > 0;
> + else if (__mdspan::__contains_zero<const index_type,
> __rank>(_M_strides))
> + return false;
> + else if constexpr (__rank == 2)
> + return (_M_strides[1] >= _M_strides[0] * _M_extents.extent(0))
> + || (_M_strides[0] >= _M_strides[1] * _M_extents.extent(1));
> + else
> + {
> + // This is necessary, but not sufficient condition for
> uniquness.
> + // It requires computation in range of call of operator(), so
> check
> + // if first, also in non-debug mode.
> + if (required_span_size() < __mdspan::__size(_M_extents))
> + return false;
> +
> + // Checking if pertmuation of strides exists is O(rank^2) so
> enabled
> + // only in debug mode.
> +#ifdef _GLIBCXX_DEBUG
> + _Strides __extents_arr, __strides_arr;
> + for (size_t __i = 0; __i < __rank; ++__i)
> + {
> + __strides_arr[__i] = _M_strides[__i];
> + __extents_arr[__i] = _M_extents.extent(__i);
> + }
> + span<index_type> __strides = __strides_arr;
> + span<index_type> __extents = __extents_arr;
> +
> + auto __popmin = [](span<index_type>& __vals)
> + {
> + index_type& __front = __vals.front();
> + index_type* __min = &__front;
> + __vals = __vals.subspan(1);
> + for (index_type& __v : __vals)
> + if (__v < *__min)
> + __min = &__v;
> +
> + std::swap(__front, *__min);
> + return __front;
> + };
> +
> + // We use eager selection-sort based algorithm to permute the
> __strides.
> + index_type __prev = __popmin(__strides);
> + while (!__strides.empty())
> + {
> + const index_type __next = __popmin(__strides);
> +
> + // Find biggest extents that could map to this stride.
>
That should check extents at position where the minimum stride was. Will
post v2 later.
> + index_type* __max = nullptr;
> + for (index_type& __ext : __extents)
> + if (__next >= __prev * __ext)
> + if (!__max || __ext > *__max)
> + __max = &__ext;
> +
> + // None of the extents passes check, non-unique layout.
> + if (!__max)
> + return false;
> +
> + std::swap(__extents.front(), *__max);
> + __extents = __extents.subspan(1);
> + __prev = __next;
> + }
> +#endif
> + return true;
> + }
> + }
> +
> #if __glibcxx_submdspan
> template<typename... _Slices>
> requires (extents_type::rank() == sizeof...(_Slices))
> @@ -2047,8 +2128,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> }
> #endif
>
> - using _Strides = typename __array_traits<index_type,
> -
> extents_type::rank()>::_Type;
> [[no_unique_address]] extents_type _M_extents;
> [[no_unique_address]] _Strides _M_strides;
> };
> diff --git
> a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc
> b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc
> index 153560bc82f..96d3c63717a 100644
> --- a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc
> +++ b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc
> @@ -27,5 +27,47 @@ test_stride_negative()
> }
> static_assert(test_stride_negative()); // { dg-error "expansion of" }
>
> +template<size_t Rank>
> + constexpr bool
> + test_is_unique(const std::array<size_t, Rank>& extents, const
> std::array<size_t, Rank>& strides)
> + {
> + auto exts = std::dextents<size_t, Rank>(extents);
> + auto m = std::layout_stride::mapping(exts, strides); // { dg-error
> "expansion of" }
> + (void) m;
> + return true;
> + }
> +
> +static_assert(test_is_unique<0>({}, {}));
> +static_assert(test_is_unique<1>({0}, {0})); // empty special case
> +static_assert(test_is_unique<1>({1}, {0})); // { dg-error "expansion of" }
> +
> +static_assert(test_is_unique<2>({0, 1}, {0, 0})); // empty special case
> +static_assert(test_is_unique<2>({1, 5}, {1, 1}));
> +static_assert(test_is_unique<2>({3, 4}, {3, 10}));
> +static_assert(test_is_unique<2>({3, 4}, {10, 3}));
> +static_assert(test_is_unique<2>({3, 4}, {2, 3})); // { dg-error
> "expansion of" }
> +static_assert(test_is_unique<2>({3, 4}, {1, 2})); // { dg-error
> "expansion of" }
> +
> +static_assert(test_is_unique<3>({0, 1, 2}, {0, 0, 0})); // empty special
> case
> +static_assert(test_is_unique<3>({1, 1, 5}, {1, 1, 1}));
> +static_assert(test_is_unique<3>({3, 4, 5}, {2, 11, 35}));
>
This one is not unique, as 4*11 > 35;
> +static_assert(test_is_unique<3>({3, 4, 5}, {35, 2, 11}));
>
Same here, {11, 2, 35} or {11, 35, 2} are.
+static_assert(test_is_unique<3>({3, 4, 5}, {1, 3, 11})); // { dg-error
> "expansion of" }
> +static_assert(test_is_unique<3>({3, 4, 5}, {1, 2, 12})); // { dg-error
> "expansion of" }
> +// Passes required_span_size check, detected only in debug mode
> +static_assert(test_is_unique<3>({3, 4, 5}, {1, 2, 25})); // { dg-error
> "expansion of" "" { target debug_mode } }
> +static_assert(test_is_unique<3>({3, 4, 5}, {1, 5, 12})); // { dg-error
> "expansion of" "" { target debug_mode } }
> +
> +static_assert(test_is_unique<4>({0, 1, 2, 3}, {0, 0, 0, 0})); // empty
> special case
> +static_assert(test_is_unique<4>({1, 1, 1, 5}, {1, 1, 1, 1}));
> +static_assert(test_is_unique<4>({3, 4, 5, 6}, {3, 16, 65, 200}));
> +static_assert(test_is_unique<4>({3, 4, 5, 6}, {200, 65, 3, 16}));
> +static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 3, 12, 50})); // {
> dg-error "expansion of" }
> +static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 3, 11, 60})); // {
> dg-error "expansion of" }
> +static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 2, 12, 60})); // {
> dg-error "expansion of" }
> +// Passes required_span_size check, detected only in debug mode
> +static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 2, 12, 100})); // {
> dg-error "expansion of" "" { target debug_mode } }
> +static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 5, 12, 60})); // {
> dg-error "expansion of" "" { target debug_mode } }
> +
> // { dg-prune-output "non-constant condition for static assertion" }
> // { dg-prune-output "__glibcxx_assert_fail()" }
> --
> 2.54.0
>
>
