On Thu, 14 Nov 2024 at 17:13, Jonathan Wakely <[email protected]> wrote:
>
> We already implement short-circuiting for random access iterators, but
> we also need to do so for ranges::equal and ranges::is_permutation when
> given sized ranges that are not random access ranges (e.g. std::list).
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/ranges_algo.h (__is_permutation_fn::operator()):
> Short-circuit for sized ranges with different sizes, as per LWG
> 3560.
> * include/bits/ranges_algobase.h (__equal_fn::operator()):
> Likewise.
> * include/bits/stl_algo.h (__is_permutation): Use if-constexpr
> for random access iterator branches.
> * include/bits/stl_algobase.h (__equal4): Likewise.
> * testsuite/25_algorithms/equal/lwg3560.cc: New test.
> * testsuite/25_algorithms/is_permutation/lwg3560.cc: New test.
> ---
>
> Tested x86_64-linux.
>
> Also available for review at:
> https://forge.sourceware.org/gcc/gcc-TEST/pulls/24
>
> libstdc++-v3/include/bits/ranges_algo.h | 7 +++
> libstdc++-v3/include/bits/ranges_algobase.h | 8 +++
> libstdc++-v3/include/bits/stl_algo.h | 13 ++---
> libstdc++-v3/include/bits/stl_algobase.h | 44 ++++++++--------
> .../testsuite/25_algorithms/equal/lwg3560.cc | 49 ++++++++++++++++++
> .../25_algorithms/is_permutation/lwg3560.cc | 51 +++++++++++++++++++
> 6 files changed, 146 insertions(+), 26 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/25_algorithms/equal/lwg3560.cc
> create mode 100644
> libstdc++-v3/testsuite/25_algorithms/is_permutation/lwg3560.cc
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> b/libstdc++-v3/include/bits/ranges_algo.h
> index bae36637b3e..80d4f5a0d57 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -595,6 +595,13 @@ namespace ranges
> operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
> _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
> {
> + // _GLIBCXX_RESOLVE_LIB_DEFECTS
> + // 3560. ranges::is_permutation should short-circuit for sized_ranges
> + if constexpr (sized_range<_Range1>)
> + if constexpr (sized_range<_Range2>)
> + if (ranges::distance(__r1) != ranges::distance(__r2))
> + return false;
> +
> return (*this)(ranges::begin(__r1), ranges::end(__r1),
> ranges::begin(__r2), ranges::end(__r2),
> std::move(__pred),
> diff --git a/libstdc++-v3/include/bits/ranges_algobase.h
> b/libstdc++-v3/include/bits/ranges_algobase.h
> index df4e770e7a6..3321085c4f6 100644
> --- a/libstdc++-v3/include/bits/ranges_algobase.h
> +++ b/libstdc++-v3/include/bits/ranges_algobase.h
> @@ -172,6 +172,14 @@ namespace ranges
> operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
> _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
> {
> + // _GLIBCXX_RESOLVE_LIB_DEFECTS
> + // 3560. ranges::equal [...] should short-circuit for sized_ranges
> + if constexpr (sized_range<_Range1>)
> + if constexpr (sized_range<_Range2>)
> + if (ranges::distance(__r1) != ranges::distance(__r2))
> + return false;
> +
> + if constexpr (sized_range<_Range1>)
I'm not sure how this extra line got in the version I posted. I've
removed that locally, and re-pushed to the forge.
> return (*this)(ranges::begin(__r1), ranges::end(__r1),
> ranges::begin(__r2), ranges::end(__r2),
> std::move(__pred),
> diff --git a/libstdc++-v3/include/bits/stl_algo.h
> b/libstdc++-v3/include/bits/stl_algo.h
> index 04bdaa66981..d8a7668ff83 100644
> --- a/libstdc++-v3/include/bits/stl_algo.h
> +++ b/libstdc++-v3/include/bits/stl_algo.h
> @@ -3471,6 +3471,8 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> }
>
> #if __cplusplus > 201103L
> +#pragma GCC diagnostic push
> +#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
> template<typename _ForwardIterator1, typename _ForwardIterator2,
> typename _BinaryPredicate>
> _GLIBCXX20_CONSTEXPR
> @@ -3485,12 +3487,10 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> = typename iterator_traits<_ForwardIterator2>::iterator_category;
> using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
> using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
> - constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
> - if (__ra_iters)
> + constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;
> + if constexpr (__ra_iters)
> {
> - auto __d1 = std::distance(__first1, __last1);
> - auto __d2 = std::distance(__first2, __last2);
> - if (__d1 != __d2)
> + if ((__last1 - __first1) != (__last2 - __first2))
> return false;
> }
>
> @@ -3501,7 +3501,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> if (!__pred(__first1, __first2))
> break;
>
> - if (__ra_iters)
> + if constexpr (__ra_iters)
> {
> if (__first1 == __last1)
> return true;
> @@ -3532,6 +3532,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> }
> return true;
> }
> +#pragma GCC diagnostic pop
>
> /**
> * @brief Checks whether a permutaion of the second sequence is equal
> diff --git a/libstdc++-v3/include/bits/stl_algobase.h
> b/libstdc++-v3/include/bits/stl_algobase.h
> index 9ecd0b216c1..d6f55dc575b 100644
> --- a/libstdc++-v3/include/bits/stl_algobase.h
> +++ b/libstdc++-v3/include/bits/stl_algobase.h
> @@ -1640,6 +1640,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> }
>
> #if __cplusplus >= 201103L
> +#pragma GCC diagnostic push
> +#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
> +
> // 4-iterator version of std::equal<It1, It2> for use in C++11.
> template<typename _II1, typename _II2>
> _GLIBCXX20_CONSTEXPR
> @@ -1650,20 +1653,20 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> using _Cat1 = typename iterator_traits<_II1>::iterator_category;
> using _Cat2 = typename iterator_traits<_II2>::iterator_category;
> using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2,
> _RATag>>;
> - if (_RAIters())
> + if constexpr (_RAIters::value)
> {
> - auto __d1 = std::distance(__first1, __last1);
> - auto __d2 = std::distance(__first2, __last2);
> - if (__d1 != __d2)
> + if ((__last1 - __first1) != (__last2 - __first2))
> return false;
> return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
> }
> -
> - for (; __first1 != __last1 && __first2 != __last2;
> - ++__first1, (void)++__first2)
> - if (!(*__first1 == *__first2))
> - return false;
> - return __first1 == __last1 && __first2 == __last2;
> + else
> + {
> + for (; __first1 != __last1 && __first2 != __last2;
> + ++__first1, (void)++__first2)
> + if (!(*__first1 == *__first2))
> + return false;
> + return __first1 == __last1 && __first2 == __last2;
> + }
> }
>
> // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11.
> @@ -1677,22 +1680,23 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> using _Cat1 = typename iterator_traits<_II1>::iterator_category;
> using _Cat2 = typename iterator_traits<_II2>::iterator_category;
> using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2,
> _RATag>>;
> - if (_RAIters())
> + if constexpr (_RAIters::value)
> {
> - auto __d1 = std::distance(__first1, __last1);
> - auto __d2 = std::distance(__first2, __last2);
> - if (__d1 != __d2)
> + if ((__last1 - __first1) != (__last2 - __first2))
> return false;
> return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
> __binary_pred);
> }
> -
> - for (; __first1 != __last1 && __first2 != __last2;
> - ++__first1, (void)++__first2)
> - if (!bool(__binary_pred(*__first1, *__first2)))
> - return false;
> - return __first1 == __last1 && __first2 == __last2;
> + else
> + {
> + for (; __first1 != __last1 && __first2 != __last2;
> + ++__first1, (void)++__first2)
> + if (!bool(__binary_pred(*__first1, *__first2)))
> + return false;
> + return __first1 == __last1 && __first2 == __last2;
> + }
> }
> +#pragma GCC diagnostic pop
> #endif // C++11
>
> #ifdef __glibcxx_robust_nonmodifying_seq_ops // C++ >= 14
> diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/lwg3560.cc
> b/libstdc++-v3/testsuite/25_algorithms/equal/lwg3560.cc
> new file mode 100644
> index 00000000000..7bf8486d1b3
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/equal/lwg3560.cc
> @@ -0,0 +1,49 @@
> +// { dg-do run { target c++20 } }
> +
> +// LWG 3560. ranges::equal and ranges::is_permutation should short-circuit
> +// for sized_ranges
> +
> +#include <algorithm>
> +#include <testsuite_iterators.h>
> +#include <testsuite_hooks.h>
> +
> +struct X
> +{
> + // Any equality comparison will cause the test to fail.
> + bool operator==(const X&) const { VERIFY(false); }
> +};
> +
> +void
> +test_std_equal()
> +{
> + X vals[3];
> + __gnu_test::random_access_container<X> r1(vals, vals+3);
> + __gnu_test::random_access_container<X> r2(vals, vals+2);
> + VERIFY( ! std::equal(r1.begin(), r1.end(), r2.begin(), r2.end()) );
> +
> + std::ranges::equal_to pred;
> + VERIFY( ! std::equal(r1.begin(), r1.end(), r2.begin(), r2.end(), pred) );
> +}
> +
> +void
> +test_std_ranges_equal()
> +{
> + X vals[3];
> + __gnu_test::test_random_access_range<X> r1(vals, vals+3);
> + __gnu_test::test_random_access_range<X> r2(vals, vals+2);
> +
> + // Any application of the projection will cause the test to fail.
> + auto proj = [](const X&) -> const X& { VERIFY(false); };
> + VERIFY( ! std::ranges::equal(r1.begin(), r1.end(), r2.begin(), r2.end(),
> {},
> + proj, proj) );
> +
> + __gnu_test::test_forward_sized_range<X> r3(vals, vals+3);
> + __gnu_test::test_forward_sized_range<X> r4(vals, vals+2);
> + VERIFY( ! std::ranges::equal(r3, r4, {}, proj, proj) );
> +}
> +
> +int main()
> +{
> + test_std_equal();
> + test_std_ranges_equal();
> +}
> diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/lwg3560.cc
> b/libstdc++-v3/testsuite/25_algorithms/is_permutation/lwg3560.cc
> new file mode 100644
> index 00000000000..f9469b08a2f
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/lwg3560.cc
> @@ -0,0 +1,51 @@
> +// { dg-do run { target c++20 } }
> +
> +// LWG 3560. ranges::equal and ranges::is_permutation should short-circuit
> +// for sized_ranges
> +
> +#include <algorithm>
> +#include <testsuite_iterators.h>
> +#include <testsuite_hooks.h>
> +
> +struct X
> +{
> + // Any equality comparison will cause the test to fail.
> + bool operator==(const X&) const { VERIFY(false); }
> +};
> +
> +void
> +test_std_is_permutation()
> +{
> + X vals[3];
> + __gnu_test::random_access_container<X> r1(vals, vals+3);
> + __gnu_test::random_access_container<X> r2(vals, vals+2);
> + VERIFY( ! std::is_permutation(r1.begin(), r1.end(), r2.begin(), r2.end())
> );
> +
> + std::ranges::equal_to pred;
> + VERIFY( ! std::is_permutation(r1.begin(), r1.end(), r2.begin(), r2.end(),
> + pred) );
> +}
> +
> +void
> +test_std_ranges_is_permutation()
> +{
> + X vals[3];
> + __gnu_test::test_random_access_range<X> r1(vals, vals+3);
> + __gnu_test::test_random_access_range<X> r2(vals, vals+2);
> +
> + // Any application of the projection will cause the test to fail.
> + auto proj = [](const X&) -> const X& { VERIFY(false); };
> + VERIFY( ! std::ranges::is_permutation(r1.begin(), r1.end(),
> + r2.begin(), r2.end(),
> + {}, proj, proj) );
> +
> + __gnu_test::test_forward_sized_range<X> r3(vals, vals+3);
> + __gnu_test::test_forward_sized_range<X> r4(vals, vals+2);
> + VERIFY( ! std::ranges::is_permutation(r3, r4, {}, proj, proj) );
> +}
> +
> +int main()
> +{
> + test_std_is_permutation();
> + test_std_ranges_is_permutation();
> +}
> --
> 2.47.0
>
