[PATCH] libstdc++: Correct implementation of uniquness check for layout_stride::mapping.
Tomasz Kaminski
tkaminsk@redhat.com
Fri Jul 24 15:13:40 GMT 2026
On Fri, Jul 24, 2026 at 3:15 PM Tomasz Kamiński <tkaminsk@redhat.com> wrote:
> As indicated by issue LWG4606, the previous wording for checking uniqueness
> of the mapping was incorrect, and rejected some valid combination of
> strides.
>
> Firstly, we observe that if new mapping N is produced by adding dimension
> (with at least two elements) to some unique mapping M, for N to remain
> unique,
> the stride on the newly added dimension needs to be greater than to maximum
> index produced by M, i.e:
> sum_[0,M::rank()) M.stride(1) * (M.extents().extent() - 1)
> As M.required_span_size() is 1 + above sum, equivalently stride needs to be
> greater than or equal to it.
>
> This patch, uses above to find permutation of dimension index (__perm),
> corresponding to order in which dimension are appended (for extent greater
> than one, this is equivalent to lowest to highest value of strides).
> Starting from zero-dimensional mapping (__cur_size == 1), in each iteration
> we compare the next __stride against required_span_size (__cur_span), and
> if check passes, we update it's value. The above also guarantees that are
> __stride values are greater than zero.
>
> As dimension of extent one (with one element), can be used only with index
> value of 0, they stride do not contribute to index value, and can be
> selected arbitrary (including having value zero). We handle above by moving
> indices corresponding such dimensions to front of __perm. To support that
> __popmin is modified to accept mapping from index to value.
>
> As mentioned above, stride value zero are acceptable also for dimension
> with extent equal to one (in addition to empty mappings). We remove
> unconditional check rejecting zero strides, and replace it with invocation
> of __stride_nonzero. This is done separately for mappings of rank one, two,
> three and larger. In the last case, a separate loop is only required in
> non-debug mode.
>
> As for the two dimension mappings, the above sum reduces to stride *
> (extent - 1), we continue validating them in non-debug mode. We handle
> degenerate mappings (at least one extent is one) first, reusing
> __stride_nonzero to check other dimension.
>
> libstdc++-v3/ChangeLog:
>
> * include/std/mdspan (layout_stride::mapping::_M_check_unique):
> Change the algorithm to correctly recognize examples from LWG4606
> as unique.
> (layout_stride::mapping(const extents_type&, span<....>)):
> Assert on _M_check_unique only for non-zero ranks.
> * testsuite/23_containers/mdspan/layouts/stride_neg.cc:
> Expand tests cases and moved some examples to...
> * testsuite/23_containers/mdspan/layouts/stride_debug_neg.cc:
> Separate test for issues detected only in debug mode.
> ---
> I have separate stride_debug_neg as DejaGNU was giving me strange failure
> on dg-bogus line, when there was error on that line on mdspan header. It
> is also easier to read the output that way.
>
> Given the little induction based "proof" for the condition above, I am
> pretty certain that I got it correctly.
>
And of course I found a counterexample for strides (3,5) and extents (5,3):
0 1 2 3 4
----------------------
0| 0 3 6 9 12
1| 5 8 11 14 17
2| 10 13 16 19 22
But such mapping cannot be produced by calling submdspan, I think.
>
> Testing on x86_64-linux. *mdspan* test passed in 32bits, debug and
> all standard modes. OK for trunk, either now or after issue is approved?
>
>
> libstdc++-v3/include/std/mdspan | 63 ++++++++++------
> .../mdspan/layouts/stride_debug_neg.cc | 42 +++++++++++
> .../mdspan/layouts/stride_neg.cc | 71 ++++++++-----------
> 3 files changed, 114 insertions(+), 62 deletions(-)
> create mode 100644
> libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_debug_neg.cc
>
> diff --git a/libstdc++-v3/include/std/mdspan
> b/libstdc++-v3/include/std/mdspan
> index 025ce4d75ab..08edcb905f4 100644
> --- a/libstdc++-v3/include/std/mdspan
> +++ b/libstdc++-v3/include/std/mdspan
> @@ -1894,7 +1894,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> _M_strides[__i] =
>
> __mdspan::__index_type_cast<index_type>(as_const(__strides[__i]));
>
> - __glibcxx_assert(_M_check_unique());
> + if constexpr (extents_type::rank() > 0)
> + __glibcxx_assert(_M_check_unique());
> }
>
> template<typename _OIndexType>
> @@ -2036,19 +2037,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> _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))
> + // 4606. Bullet (4.3) preconditions are too strict to implement
> submdspan
> +
> + 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;
> +
> + auto __stride_nonzero = [&](size_t __idx)
> + { return (_M_strides[__idx] > 0) || (_M_extents.extent(__idx) ==
> 1); };
> +
> + if constexpr (__rank == 1)
> + return __stride_nonzero(0);
> 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));
> + {
> + if (_M_extents.extent(0) == 1)
> + return __stride_nonzero(1);
> + if (_M_extents.extent(1) == 1)
> + return __stride_nonzero(0);
> + if (!_M_strides[0] || !_M_strides[1])
> + return false;
> + return (_M_strides[1] > _M_strides[0] * (_M_extents.extent(0)
> - 1))
> + || (_M_strides[0] > _M_strides[1] * (_M_extents.extent(1)
> - 1));
> + }
> else
> {
> // This is necessary, but not sufficient condition for
> uniqueness.
> @@ -2064,15 +2075,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> for (size_t __i = 0; __i < __rank; ++__i)
> __perm[__i] = __i;
>
> - auto __popmin = [&](size_t __from)
> + auto __getstride = [&](size_t __idx) { return
> _M_strides[__idx]; };
> + auto __getextent = [&](size_t __idx) { return
> _M_extents.extent(__idx); };
> + auto __popmin = [&](size_t __from, auto __getter)
> {
> size_t __min = __perm[__rank - 1];
> for (size_t __i = __rank - 1; __i > __from; --__i)
> {
> const size_t __cur = __perm[__i - 1];
> - const auto __res = _M_strides[__cur] <=>
> _M_strides[__min];
> - // Equal strides are allowed only for extent one, so
> apply it first.
> - if (__res < 0 || (__res == 0 && _M_extents.extent(__cur)
> == 1))
> + if (__getter(__cur) < __getter(__min))
> {
> __perm[__i] = __min;
> __min = __cur;
> @@ -2081,18 +2092,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> __perm[__i] = __cur;
> }
> __perm[__from] = __min;
> - return __min;
> + return __getter(__min);
> };
>
> // We use eager insertion-sort based algorithm to permute the
> __perm.
> - size_t __prev = __popmin(0);
> - for (size_t __i = 1; __i < __rank; ++__i)
> + size_t __idx = 0;
> +
> + // Stride valus are not revelant for dimension with single
> element
> + while (__popmin(__idx, __getextent) == 1)
> + if (++__idx == __rank)
> + return true;
> +
> + size_t __prev_span = 1;
> + for (; __idx < __rank; ++__idx)
> {
> - const size_t __next = __popmin(__i);
> - if (_M_strides[__next] < _M_strides[__prev] *
> _M_extents.extent(__prev))
> + const size_t __stride = __popmin(__idx, __getstride);
> + if (__stride < __prev_span)
> return false;
> - __prev = __next;
> + __prev_span += __stride * (__getextent(__perm[__idx]) - 1);
> }
> +#else
> + // Otherwise check obvious cases where stride is zero.
> + for (size_t __idx = 0; __idx < __rank; ++__idx)
> + if (!__stride_nonzero(__idx))
> + return false;
> #endif
> return true;
> }
> diff --git
> a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_debug_neg.cc
> b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_debug_neg.cc
> new file mode 100644
> index 00000000000..bc5f41489d7
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_debug_neg.cc
> @@ -0,0 +1,42 @@
> +// { dg-do compile { target c++23 } }
> +#include <mdspan>
> +#include <cstdint>
> +
> +using std::array;
> +template<size_t Rank>
> + using mapping = std::layout_stride::mapping<std::dextents<size_t, Rank>>;
> +
> +// Only some permutations are valid, invalid permutations detected only
> in debug mode.
> +
> +// Unique if stride 4 corresponds to extent 3
> +constexpr auto m28 = mapping<2>(array{3, 4}, array{4, 10}); // { dg-bogus
> "expansion of" }
> +constexpr auto m29 = mapping<2>(array{3, 4}, array{10, 4}); // { dg-error
> "expansion of" "" { target debug_mode } }
> +constexpr auto m30 = mapping<2>(array{4, 3}, array{10, 4}); // { dg-bogus
> "expansion of" }
> +constexpr auto m31 = mapping<2>(array{4, 3}, array{4, 10}); // { dg-error
> "expansion of" "" { target debug_mode } }
> +
> +// Unique if stride 11 corresponds to extent 3, 2 * (5-1) = 8 < 11, and
> 11 * (3-1) + 8 = 30 < 35
> +constexpr auto m32 = mapping<3>(array{3, 4, 5}, array{11, 2, 35}); // {
> dg-bogus "expansion of" }
> +constexpr auto m33 = mapping<3>(array{3, 4, 5}, array{11, 35, 2}); // {
> dg-bogus "expansion of" }
> +constexpr auto m34 = mapping<3>(array{3, 4, 5}, array{2, 11, 35}); // {
> dg-error "expansion of" "" { target debug_mode } }
> +constexpr auto m35 = mapping<3>(array{3, 4, 5}, array{35, 2, 11}); // {
> dg-error "expansion of" "" { target debug_mode } }
> +constexpr auto m36 = mapping<3>(array{5, 4, 3}, array{2, 35, 11}); // {
> dg-bogus "expansion of" }
> +constexpr auto m37 = mapping<3>(array{5, 4, 3}, array{2, 11, 35}); // {
> dg-error "expansion of" "" { target debug_mode } }
> +constexpr auto m38 = mapping<3>(array{5, 3, 4}, array{35, 11, 2}); // {
> dg-bogus "expansion of" }
> +constexpr auto m39 = mapping<3>(array{3, 5, 4}, array{35, 2, 11}); // {
> dg-error "expansion of" "" { target debug_mode } }
> +
> +// Unique for stride -> extent mapping: 3 * (5-1) = 12 < 16, 15 * (4-1) +
> 12 = 57 < 65, 65 * (3-1) + 57 = 187 < 200
> +constexpr auto m40 = mapping<4>(array{3, 4, 5, 6}, array{65, 16, 3,
> 200}); // { dg-bogus "expansion of" }
> +constexpr auto m41 = mapping<4>(array{3, 4, 5, 6}, array{3, 16, 65,
> 200}); // { dg-error "expansion of" "" { target debug_mode } }
> +constexpr auto m42 = mapping<4>(array{3, 4, 5, 6}, array{200, 65, 3,
> 16}); // { dg-error "expansion of" "" { target debug_mode } }
> +constexpr auto m43 = mapping<4>(array{5, 3, 6, 4}, array{3, 65, 200,
> 16}); // { dg-bogus "expansion of" }
> +constexpr auto m44 = mapping<4>(array{5, 3, 6, 4}, array{3, 16, 200,
> 65}); // { dg-error "expansion of" "" { target debug_mode } }
> +
> +// Examples based on one from LWG 4606
> +constexpr auto m45 = mapping<2>(array{2, 3}, array{5, 2}); // { dg-bogus
> "expansion of" }
> +constexpr auto m46 = mapping<3>(array{2, 3, 5}, array{5, 2, 10}); // {
> dg-bogus "expansion of" }
> +constexpr auto m47 = mapping<3>(array{2, 3, 1}, array{5, 2, 99}); // {
> dg-bogus "expansion of" }
> +constexpr auto m48 = mapping<4>(array{2, 3, 5, 4}, array{5, 2, 10, 50});
> // { dg-bogus "expansion of" }
> +constexpr auto m49 = mapping<4>(array{2, 1, 3, 5}, array{5, 99, 2, 10});
> // { dg-bogus "expansion of" }
> +
> +// { dg-prune-output "non-constant condition for static assertion" }
> +// { dg-prune-output "__glibcxx_assert_fail()" }
> 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 692caeac812..5a818042b5a 100644
> --- a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc
> +++ b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc
> @@ -19,12 +19,11 @@ constexpr bool
> test_stride_negative()
> {
> auto exts = std::extents<std::size_t, dyn, dyn>(1, 3);
> - auto m = std::layout_stride::mapping(exts, std::array{1, -4}); // {
> dg-error "expansion of" }
> + auto m = std::layout_stride::mapping(exts, std::array{1, -4}); // {
> dg-error "expansion of" }
> (void) m;
> return true;
> }
> -static_assert(test_stride_negative()); // { dg-error "expansion of" }
> -
> +static_assert(test_stride_negative()); // { dg-error "expansion of" }
>
> using std::array;
> template<size_t Rank>
> @@ -34,17 +33,25 @@ constexpr auto m0 = mapping<0>(array<int, 0>{},
> array<int, 0>{}); // { dg-bogus
>
> // Zero strides allowed for empty mappings
> constexpr auto m00 = mapping<1>(array{0}, array{0}); // { dg-bogus
> "expansion of" }
> -constexpr auto m01 = mapping<2>(array{0, 1}, array{3, 0}); // { dg-bogus
> "expansion of" }
> -constexpr auto m02 = mapping<2>(array{0, 1}, array{0, 0}); // { dg-bogus
> "expansion of" }
> -constexpr auto m03 = mapping<3>(array{0, 1, 2}, array{3, 0, 0}); // {
> dg-bogus "expansion of" }
> -constexpr auto m04 = mapping<3>(array{0, 1, 2}, array{3, 3, 0}); // {
> dg-bogus "expansion of" }
> -constexpr auto m05 = mapping<4>(array{0, 1, 2, 3}, array{5, 3, 0, 2}); //
> { dg-bogus "expansion of" }
> +constexpr auto m01 = mapping<2>(array{0, 2}, array{3, 0}); // { dg-bogus
> "expansion of" }
> +constexpr auto m02 = mapping<2>(array{0, 2}, array{0, 0}); // { dg-bogus
> "expansion of" }
> +constexpr auto m03 = mapping<3>(array{0, 2, 3}, array{3, 0, 0}); // {
> dg-bogus "expansion of" }
> +constexpr auto m04 = mapping<3>(array{0, 2, 3}, array{3, 3, 0}); // {
> dg-bogus "expansion of" }
> +constexpr auto m05 = mapping<4>(array{0, 2, 3, 4}, array{5, 3, 0, 2}); //
> { dg-bogus "expansion of" }
> +
> +// On dimensions with stride equal to 1
> +constexpr auto m0a = mapping<1>(array{1}, array{0}); // { dg-bogus
> "expansion of" }
> +constexpr auto m0b = mapping<2>(array{2, 1}, array{3, 0}); // { dg-bogus
> "expansion of" }
> +constexpr auto m0c = mapping<2>(array{1, 1}, array{0, 0}); // { dg-bogus
> "expansion of" }
> +constexpr auto m0d = mapping<3>(array{2, 1, 1}, array{3, 0, 0}); // {
> dg-bogus "expansion of" }
> +constexpr auto m0e = mapping<3>(array{2, 2, 1}, array{6, 3, 0}); // {
> dg-bogus "expansion of" }
> +constexpr auto m0f = mapping<4>(array{2, 2, 1, 2}, array{8, 4, 0, 2}); //
> { dg-bogus "expansion of" }
>
> // Otherwise leads to non-unique mappings.
> -constexpr auto m06 = mapping<1>(array{1}, array{0}); //
> { dg-error "expansion of" }
> -constexpr auto m07 = mapping<2>(array{1, 2}, array{3, 0}); //
> { dg-error "expansion of" }
> -constexpr auto m08 = mapping<3>(array{1, 2, 3}, array{3, 3, 0}); //
> { dg-error "expansion of" }
> -constexpr auto m09 = mapping<4>(array{1, 2, 3, 5}, array{5, 3, 0, 2}); //
> { dg-error "expansion of" }
> +constexpr auto m06 = mapping<1>(array{2}, array{0}); // { dg-error
> "expansion of" }
> +constexpr auto m07 = mapping<2>(array{2, 3}, array{3, 0}); // { dg-error
> "expansion of" }
> +constexpr auto m08 = mapping<3>(array{2, 3, 4}, array{3, 3, 0}); // {
> dg-error "expansion of" }
> +constexpr auto m09 = mapping<4>(array{2, 3, 4, 5}, array{5, 3, 0, 2}); //
> { dg-error "expansion of" }
>
> // required_span_size is smaller size of multidimensional index space
> constexpr auto m10 = mapping<2>(array{3, 4}, array{2, 3}); // { dg-error
> "expansion of" }
> @@ -61,39 +68,19 @@ constexpr auto m18 = mapping<3>(array{3, 4, 5},
> array{1, 5, 12}); // { dg-error
> constexpr auto m19 = mapping<4>(array{3, 4, 5, 6}, array{1, 2, 12, 100});
> // { dg-error "expansion of" "" { target debug_mode } }
> constexpr auto m20 = mapping<4>(array{3, 4, 5, 6}, array{1, 5, 12, 60});
> // { dg-error "expansion of" "" { target debug_mode } }
>
> -// Equal indicies allowed if extents are 1
> -constexpr auto m21 = mapping<2>(array{5, 1}, array{1, 1}); // { dg-bogus
> "expansion of" }
> -constexpr auto m22 = mapping<3>(array{1, 5, 1}, array{1, 1, 1}); // {
> dg-bogus "expansion of" }
> -constexpr auto m23 = mapping<4>(array{1, 1, 5, 1}, array{1, 1, 1, 1}); //
> { dg-bogus "expansion of" }
> +// Any stride values are allowed for extents 1
> +constexpr auto m21 = mapping<2>(array{1, 1}, array{88, 99}); // {
> dg-bogus "expansion of" }
> +constexpr auto m2a = mapping<2>(array{5, 1}, array{88, 99}); // {
> dg-bogus "expansion of" }
> +constexpr auto m22 = mapping<3>(array{1, 1, 1}, array{88, 99, 00}); // {
> dg-bogus "expansion of" }
> +constexpr auto m2b = mapping<3>(array{1, 5, 1}, array{88, 99, 77}); // {
> dg-bogus "expansion of" }
> +constexpr auto m23 = mapping<4>(array{1, 1, 1, 1}, array{77, 99, 00,
> 88}); // { dg-bogus "expansion of" }
> +constexpr auto m2c = mapping<4>(array{1, 1, 5, 1}, array{77, 99, 1, 88});
> // { dg-bogus "expansion of" }
> constexpr auto m24 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 3,
> 45}); // { dg-bogus "expansion of" }
> constexpr auto m25 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 10,
> 45}); // { dg-bogus "expansion of" }
> -constexpr auto m26 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 3,
> 45}); // { dg-bogus "expansion of" }
> +constexpr auto m26 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 3,
> 45}); // { dg-bogus "expansion of" }
> constexpr auto m27 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10,
> 10, 45}); // { dg-bogus "expansion of" }
> -
> -// Only some permutations are valid, invalid permutations detected only
> in debug mode.
> -
> -// Unique if stride 3 corresponds to extent 3
> -constexpr auto m28 = mapping<2>(array{3, 4}, array{3, 10}); // { dg-bogus
> "expansion of" }
> -constexpr auto m29 = mapping<2>(array{3, 4}, array{10, 3}); // { dg-error
> "expansion of" "" { target debug_mode } }
> -constexpr auto m30 = mapping<2>(array{4, 3}, array{10, 3}); // { dg-bogus
> "expansion of" }
> -constexpr auto m31 = mapping<2>(array{4, 3}, array{3, 10}); // { dg-error
> "expansion of" "" { target debug_mode } }
> -
> -// Unique if stride 11 corresponds to extent 3, as 11 * 3 < 35, and 2 * 5
> < 11
> -constexpr auto m32 = mapping<3>(array{3, 4, 5}, array{11, 2, 35}); // {
> dg-bogus "expansion of" }
> -constexpr auto m33 = mapping<3>(array{3, 4, 5}, array{11, 35, 2}); // {
> dg-bogus "expansion of" }
> -constexpr auto m34 = mapping<3>(array{3, 4, 5}, array{2, 11, 35}); // {
> dg-error "expansion of" "" { target debug_mode } }
> -constexpr auto m35 = mapping<3>(array{3, 4, 5}, array{35, 2, 11}); // {
> dg-error "expansion of" "" { target debug_mode } }
> -constexpr auto m36 = mapping<3>(array{5, 4, 3}, array{2, 35, 11}); // {
> dg-bogus "expansion of" }
> -constexpr auto m37 = mapping<3>(array{5, 4, 3}, array{2, 11, 35}); // {
> dg-error "expansion of" "" { target debug_mode } }
> -constexpr auto m38 = mapping<3>(array{5, 3, 4}, array{35, 11, 2}); // {
> dg-bogus "expansion of" }
> -constexpr auto m39 = mapping<3>(array{3, 5, 4}, array{35, 2, 11}); // {
> dg-error "expansion of" "" { target debug_mode } }
> -
> -// Unique for stride -> extent mapping: 3 * 5 < 16, 15 * 4 < 65, 65 * 3 <
> 200
> -constexpr auto m40 = mapping<4>(array{3, 4, 5, 6}, array{65, 16, 3,
> 200}); // { dg-bogus "expansion of" }
> -constexpr auto m41 = mapping<4>(array{3, 4, 5, 6}, array{3, 16, 65,
> 200}); // { dg-error "expansion of" "" { target debug_mode } }
> -constexpr auto m42 = mapping<4>(array{3, 4, 5, 6}, array{200, 65, 3,
> 16}); // { dg-error "expansion of" "" { target debug_mode } }
> -constexpr auto m43 = mapping<4>(array{5, 3, 6, 4}, array{3, 65, 200,
> 16}); // { dg-bogus "expansion of" }
> -constexpr auto m44 = mapping<4>(array{5, 3, 6, 4}, array{3, 16, 200,
> 65}); // { dg-error "expansion of" "" { target debug_mode } }
> +constexpr auto m2d = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 00,
> 99, 45}); // { dg-bogus "expansion of" }
> +constexpr auto m2e = mapping<5>(array{1, 1, 1, 1, 1}, array{00, 77, 88,
> 99, 00}); // { dg-bogus "expansion of" }
>
> // { dg-prune-output "non-constant condition for static assertion" }
> // { dg-prune-output "__glibcxx_assert_fail()" }
> --
> 2.55.0
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260724/1982fce6/attachment-0001.htm>
More information about the Libstdc++
mailing list