diff mbox series

libstdc++: Assert that produced layout_stride::mapping is unique.

Message ID 20260708100932.424948-1-tkaminsk@redhat.com
State New
Headers
Series libstdc++: Assert that produced layout_stride::mapping is unique. |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed

Commit Message

Tomasz Kaminski July 8, 2026, 9:57 a.m. UTC 
  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 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.
	* testsuite/23_containers/mdspan/layouts/stride_unique.cc:
	Test verifying no assertions for unique subset of above.
---
v2 properly detects an stride sequence that is non-unique, but
when assigned to different extents will produce unique layout.
This is done, by keeping the relation of stride with the corresponding
extents, by permuting the indicies (producing P vector from wording).

Changed the __popmin to use insertion sort, that should be optimal
for resonable ranks (max few dozens) and expanded the test cases.
Added separate stride_unique.cc test file, that checks that
no-assertions is triggered from them. For other test, it was still
passing if the error was emmitted for line without "dg-error" -
I assume this is because them being produced from some source line.
The test still fails if error is expected, but not produced.

Tested on x86_64-linux locally. *mdspan* test passed with all standard
modes and _GLIBCXX_DEBUG. OK for trunk?

 libstdc++-v3/include/std/mdspan               | 73 ++++++++++++++++++-
 .../mdspan/layouts/stride_neg.cc              | 72 +++++++++++++++++-
 .../mdspan/layouts/stride_unique.cc           | 42 +++++++++++
 3 files changed, 183 insertions(+), 4 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_unique.cc
diff mbox series

Patch

diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan
index 23304e71b9d..02db9f71d55 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 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
+	    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 153560bc82f..80f8902176c 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>{});
+
+// Zero strides allowed for empty mappings
+constexpr auto m00 = mapping<1>(array{0}, array{0});
+constexpr auto m01 = mapping<2>(array{0, 1}, array{3, 0});
+constexpr auto m02 = mapping<2>(array{0, 1}, array{0, 0});
+constexpr auto m03 = mapping<3>(array{0, 1, 2}, array{3, 0, 0});
+constexpr auto m04 = mapping<3>(array{0, 1, 2}, array{3, 3, 0});
+constexpr auto m05 = mapping<4>(array{0, 1, 2, 3}, array{5, 3, 0, 2});
+
+// 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});
+constexpr auto m22 = mapping<3>(array{1, 5, 1}, array{1, 1, 1});
+constexpr auto m23 = mapping<4>(array{1, 1, 5, 1}, array{1, 1, 1, 1});
+constexpr auto m24 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 3, 45});
+constexpr auto m25 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 10, 45});
+constexpr auto m26 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 3, 45});
+constexpr auto m27 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 10, 45});
+
+// 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});
+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});
+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});
+constexpr auto m33 = mapping<3>(array{3, 4, 5}, array{11, 35, 2});
+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});
+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});
+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});
+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});
+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()" }
diff --git a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_unique.cc b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_unique.cc
new file mode 100644
index 00000000000..767e5f2fedf
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_unique.cc
@@ -0,0 +1,42 @@ 
+// { dg-do compile { target c++23 } }
+#include <mdspan>
+
+constexpr size_t dyn = std::dynamic_extent;
+
+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>{});
+
+// Zero strides allowed for empty mappings
+constexpr auto m00 = mapping<1>(array{0}, array{0});
+constexpr auto m01 = mapping<2>(array{0, 1}, array{3, 0});
+constexpr auto m02 = mapping<2>(array{0, 1}, array{0, 0});
+constexpr auto m03 = mapping<3>(array{0, 1, 2}, array{3, 0, 0});
+constexpr auto m04 = mapping<3>(array{0, 1, 2}, array{3, 3, 0});
+constexpr auto m05 = mapping<4>(array{0, 1, 2, 3}, array{5, 3, 0, 2});
+
+// Equal indicies allowed if extents are 1
+constexpr auto m21 = mapping<2>(array{5, 1}, array{1, 1});
+constexpr auto m22 = mapping<3>(array{1, 5, 1}, array{1, 1, 1});
+constexpr auto m23 = mapping<4>(array{1, 1, 5, 1}, array{1, 1, 1, 1});
+constexpr auto m24 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 3, 45});
+constexpr auto m25 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 10, 45});
+constexpr auto m26 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 3, 45});
+constexpr auto m27 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 10, 45});
+
+// Unique if stride 3 corresponds to extent 3
+constexpr auto m28 = mapping<2>(array{3, 4}, array{3, 10});
+constexpr auto m30 = mapping<2>(array{4, 3}, array{10, 3});
+
+// 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});
+constexpr auto m33 = mapping<3>(array{3, 4, 5}, array{11, 35, 2});
+constexpr auto m36 = mapping<3>(array{5, 4, 3}, array{2, 35, 11});
+constexpr auto m38 = mapping<3>(array{5, 3, 4}, array{35, 11, 2});
+
+// 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});
+constexpr auto m43 = mapping<4>(array{5, 3, 6, 4}, array{3, 65, 200, 16});
+