https://gcc.gnu.org/g:0b3c5e87f6c5a93076227883fa2f882a4e879e63
commit r17-4885-g0b3c5e87f6c5a93076227883fa2f882a4e879e63 Author: Tomasz Kamiński <[email protected]> Date: Fri Jul 24 14:07:42 2026 +0200 libstdc++: Correct implementation of uniqueness check for layout_stride::mapping. 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(i) * (M.extents().extent(i) - 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 to 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. Reviewed-by: Jonathan Wakely <[email protected]> Diff: --- libstdc++-v3/include/std/mdspan | 63 +++++++++++++------ .../mdspan/layouts/stride_debug_neg.cc | 42 +++++++++++++ .../23_containers/mdspan/layouts/stride_neg.cc | 71 +++++++++------------- 3 files changed, 114 insertions(+), 62 deletions(-) diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan index 025ce4d75aba..6adc157a8766 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 values are not relevant 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 000000000000..bc5f41489d74 --- /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 692caeac8123..5a818042b5ab 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()" }
