Re: [PATCH] libstdc++: Correct implementation of uniquness check for layout_stride::mapping.

[Jonathan Wakely]

Typo in "uniquness" in the subject line.

On Fri, 24 Jul 2026 at 15:09 +0200, Tomasz Kamiński 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

"corresponding to"

__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.

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?

OK for trunk with the typos above and below fixed, thanks.

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

"values" and "relevant"

+           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