https://gcc.gnu.org/g:1a4d8dc0d2dc045bbb93654ae66fb80276dc6690
commit r17-2356-g1a4d8dc0d2dc045bbb93654ae66fb80276dc6690 Author: Tomasz Kamiński <[email protected]> Date: Tue Jul 7 10:27:33 2026 +0200 libstdc++: Assert that produced layout_stride::mapping is unique. 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 a necessary but not sufficient condition, that is O(rank) and is always performed. * building a permutation using insertion-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. Reviewed-by: Jonathan Wakely <[email protected]> Signed-off-by: Tomasz Kamiński <[email protected]> Diff: --- libstdc++-v3/include/std/mdspan | 73 +++++++++++++++++++++- .../23_containers/mdspan/layouts/stride_neg.cc | 72 ++++++++++++++++++++- 2 files changed, 141 insertions(+), 4 deletions(-) diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan index 23304e71b9df..025ce4d75aba 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>(as_const(__strides[__i])); + + __glibcxx_assert(_M_check_unique()); } template<typename _OIndexType> @@ -2027,6 +2029,75 @@ _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 uniqueness. + // 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 for a valid permutation of strides is O(rank^2) so + // so enabled only in debug mode. +#ifdef _GLIBCXX_DEBUG + size_t __perm[__rank]; + for (size_t __i = 0; __i < __rank; ++__i) + __perm[__i] = __i; + + auto __popmin = [&](size_t __from) + { + 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)) + { + __perm[__i] = __min; + __min = __cur; + } + else + __perm[__i] = __cur; + } + __perm[__from] = __min; + return __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) + { + const size_t __next = __popmin(__i); + if (_M_strides[__next] < _M_strides[__prev] * _M_extents.extent(__prev)) + return false; + __prev = __next; + } +#endif + return true; + } + } + #if __glibcxx_submdspan template<typename... _Slices> requires (extents_type::rank() == sizeof...(_Slices)) @@ -2047,8 +2118,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 153560bc82ff..692caeac8123 100644 --- a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc @@ -1,7 +1,5 @@ // { dg-do compile { target c++23 } } #include <mdspan> - -#include "../layout_traits.h" #include <cstdint> constexpr size_t dyn = std::dynamic_extent; @@ -27,5 +25,75 @@ test_stride_negative() } static_assert(test_stride_negative()); // { dg-error "expansion of" } + +using std::array; +template<size_t Rank> + using mapping = std::layout_stride::mapping<std::dextents<size_t, Rank>>; + +constexpr auto m0 = mapping<0>(array<int, 0>{}, array<int, 0>{}); // { dg-bogus "expansion of" } + +// 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" } + +// 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" } + +// 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" } +constexpr auto m11 = mapping<2>(array{3, 4}, array{1, 2}); // { dg-error "expansion of" } +constexpr auto m12 = mapping<3>(array{3, 4, 5}, array{1, 3, 11}); // { dg-error "expansion of" } +constexpr auto m13 = mapping<3>(array{3, 4, 5}, array{1, 2, 12}); // { dg-error "expansion of" } +constexpr auto m14 = mapping<4>(array{3, 4, 5, 6}, array{1, 3, 12, 50}); // { dg-error "expansion of" } +constexpr auto m15 = mapping<4>(array{3, 4, 5, 6}, array{1, 3, 11, 60}); // { dg-error "expansion of" } +constexpr auto m16 = mapping<4>(array{3, 4, 5, 6}, array{1, 2, 12, 60}); // { dg-error "expansion of" } + +// Passes required_span_size check (smaller and bigger stride), detected only in debug mode +constexpr auto m17 = mapping<3>(array{3, 4, 5}, array{1, 2, 25}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m18 = mapping<3>(array{3, 4, 5}, array{1, 5, 12}); // { dg-error "expansion of" "" { target debug_mode } } +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" } +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 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 } } + // { dg-prune-output "non-constant condition for static assertion" } // { dg-prune-output "__glibcxx_assert_fail()" }
