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 selection-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.
---
Are we OK with full detection only for ranks <= 2 and some subset of
problematic layouts with rank >= 3? I think this is good sweet spot.
But I see how some may argue for consistency here, but then I would
put unique dection only in debug for all ranks.
Tested on x86_64-linux locally. *mdspan* test passed in all standard
modes and with _GLIBCXX_DEBUG. OK for trunk?
libstdc++-v3/include/std/mdspan | 83 ++++++++++++++++++-
.../mdspan/layouts/stride_neg.cc | 42 ++++++++++
2 files changed, 123 insertions(+), 2 deletions(-)
diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan
index 5e1c4d8b1a4..69dbe091884 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>(__strides[__i]);
+
+ __glibcxx_assert(_M_check_unique());
}
template<typename _OIndexType>
@@ -2027,6 +2029,85 @@ _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
+ _Strides __extents_arr, __strides_arr;
+ for (size_t __i = 0; __i < __rank; ++__i)
+ {
+ __strides_arr[__i] = _M_strides[__i];
+ __extents_arr[__i] = _M_extents.extent(__i);
+ }
+ span<index_type> __strides = __strides_arr;
+ span<index_type> __extents = __extents_arr;
+
+ auto __popmin = [](span<index_type>& __vals)
+ {
+ index_type& __front = __vals.front();
+ index_type* __min = &__front;
+ __vals = __vals.subspan(1);
+ for (index_type& __v : __vals)
+ if (__v < *__min)
+ __min = &__v;
+
+ std::swap(__front, *__min);
+ return __front;
+ };
+
+ // We use eager selection-sort based algorithm to permute the
__strides.
+ index_type __prev = __popmin(__strides);
+ while (!__strides.empty())
+ {
+ const index_type __next = __popmin(__strides);
+
+ // Find biggest extents that could map to this stride.
+ index_type* __max = nullptr;
+ for (index_type& __ext : __extents)
+ if (__next >= __prev * __ext)
+ if (!__max || __ext > *__max)
+ __max = &__ext;
+
+ // None of the extents passes check, non-unique layout.
+ if (!__max)
+ return false;
+
+ std::swap(__extents.front(), *__max);
+ __extents = __extents.subspan(1);
+ __prev = __next;
+ }
+#endif
+ return true;
+ }
+ }
+
#if __glibcxx_submdspan
template<typename... _Slices>
requires (extents_type::rank() == sizeof...(_Slices))
@@ -2047,8 +2128,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..96d3c63717a 100644
--- a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc
@@ -27,5 +27,47 @@ test_stride_negative()
}
static_assert(test_stride_negative()); // { dg-error "expansion of" }
+template<size_t Rank>
+ constexpr bool
+ test_is_unique(const std::array<size_t, Rank>& extents, const
std::array<size_t, Rank>& strides)
+ {
+ auto exts = std::dextents<size_t, Rank>(extents);
+ auto m = std::layout_stride::mapping(exts, strides); // { dg-error
"expansion of" }
+ (void) m;
+ return true;
+ }
+
+static_assert(test_is_unique<0>({}, {}));
+static_assert(test_is_unique<1>({0}, {0})); // empty special case
+static_assert(test_is_unique<1>({1}, {0})); // { dg-error "expansion of" }
+
+static_assert(test_is_unique<2>({0, 1}, {0, 0})); // empty special case
+static_assert(test_is_unique<2>({1, 5}, {1, 1}));
+static_assert(test_is_unique<2>({3, 4}, {3, 10}));
+static_assert(test_is_unique<2>({3, 4}, {10, 3}));
+static_assert(test_is_unique<2>({3, 4}, {2, 3})); // { dg-error "expansion of"
}
+static_assert(test_is_unique<2>({3, 4}, {1, 2})); // { dg-error "expansion of"
}
+
+static_assert(test_is_unique<3>({0, 1, 2}, {0, 0, 0})); // empty special case
+static_assert(test_is_unique<3>({1, 1, 5}, {1, 1, 1}));
+static_assert(test_is_unique<3>({3, 4, 5}, {2, 11, 35}));
+static_assert(test_is_unique<3>({3, 4, 5}, {35, 2, 11}));
+static_assert(test_is_unique<3>({3, 4, 5}, {1, 3, 11})); // { dg-error
"expansion of" }
+static_assert(test_is_unique<3>({3, 4, 5}, {1, 2, 12})); // { dg-error
"expansion of" }
+// Passes required_span_size check, detected only in debug mode
+static_assert(test_is_unique<3>({3, 4, 5}, {1, 2, 25})); // { dg-error
"expansion of" "" { target debug_mode } }
+static_assert(test_is_unique<3>({3, 4, 5}, {1, 5, 12})); // { dg-error
"expansion of" "" { target debug_mode } }
+
+static_assert(test_is_unique<4>({0, 1, 2, 3}, {0, 0, 0, 0})); // empty special
case
+static_assert(test_is_unique<4>({1, 1, 1, 5}, {1, 1, 1, 1}));
+static_assert(test_is_unique<4>({3, 4, 5, 6}, {3, 16, 65, 200}));
+static_assert(test_is_unique<4>({3, 4, 5, 6}, {200, 65, 3, 16}));
+static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 3, 12, 50})); // { dg-error
"expansion of" }
+static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 3, 11, 60})); // { dg-error
"expansion of" }
+static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 2, 12, 60})); // { dg-error
"expansion of" }
+// Passes required_span_size check, detected only in debug mode
+static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 2, 12, 100})); // { dg-error
"expansion of" "" { target debug_mode } }
+static_assert(test_is_unique<4>({3, 4, 5, 6}, {1, 5, 12, 60})); // { dg-error
"expansion of" "" { target debug_mode } }
+
// { dg-prune-output "non-constant condition for static assertion" }
// { dg-prune-output "__glibcxx_assert_fail()" }
--
2.54.0
