Test LWG-4105 ranges::ends_with's Returns misses difference casting (#4897)

frederick-vs-ja · StephanTLavavej · web-flow · commit 20a1c9f0d2c5 · 2024-08-25T11:01:16.000-07:00
Co-authored-by: Stephan T. Lavavej &lt;stl@nuwen.net&gt;
diff --git a/tests/std/include/range_algorithm_support.hpp b/tests/std/include/range_algorithm_support.hpp
@@ -7,6 +7,7 @@
 #include <cstddef>
 #include <functional>
 #include <iterator>
+#include <memory>
 #include <ranges>
 #include <span>
 #include <type_traits>
@@ -935,6 +936,228 @@ namespace test {
             static_assert(false);
         }
     };
+
+    template <std::_Signed_integer_like I>
+    [[nodiscard]] constexpr auto to_unsigned(I n) noexcept {
+        if constexpr (std::signed_integral<I>) {
+            return static_cast<std::make_unsigned_t<I>>(n);
+        } else {
+            return static_cast<std::_Unsigned128>(n);
+        }
+    }
+
+    template <std::_Signed_integer_like Diff, std::input_iterator It>
+    struct redifference_iterator_category_base {};
+
+    template <std::_Signed_integer_like Diff, std::input_iterator It>
+        requires std::signed_integral<Diff> && requires { typename std::iterator_traits<It>::iterator_category; }
+    struct redifference_iterator_category_base<Diff, It> {
+        using iterator_category = std::iterator_traits<It>::iterator_category;
+        using iterator_concept  = decltype([] {
+            if constexpr (std::contiguous_iterator<It>) {
+                return std::contiguous_iterator_tag{};
+            } else if constexpr (std::random_access_iterator<It>) {
+                return std::random_access_iterator_tag{};
+            } else if constexpr (std::bidirectional_iterator<It>) {
+                return std::bidirectional_iterator_tag{};
+            } else if constexpr (std::forward_iterator<It>) {
+                return std::forward_iterator_tag{};
+            } else {
+                return std::input_iterator_tag{};
+            }
+        }());
+    };
+
+    template <std::_Signed_integer_like Diff, std::input_iterator It>
+    class redifference_iterator : public redifference_iterator_category_base<Diff, It> {
+    public:
+        using value_type      = std::iter_value_t<It>;
+        using difference_type = Diff;
+
+        redifference_iterator() = default;
+        constexpr explicit redifference_iterator(It it) : i_{std::move(it)} {}
+
+        [[nodiscard]] constexpr decltype(auto) operator*() const {
+            return *i_;
+        }
+
+        constexpr decltype(auto) operator->() const
+            requires std::contiguous_iterator<It> || (requires(const It& i) { i.operator->(); })
+        {
+            if constexpr (std::contiguous_iterator<It>) {
+                return std::to_address(i_);
+            } else {
+                return i_.operator->();
+            }
+        }
+
+        constexpr redifference_iterator& operator++() {
+            ++i_;
+            return *this;
+        }
+
+        constexpr decltype(auto) operator++(int) {
+            if constexpr (std::is_same_v<decltype(i_++), It>) {
+                return redifference_iterator{i_++};
+            } else {
+                return i_++;
+            }
+        }
+
+        constexpr redifference_iterator& operator--()
+            requires std::bidirectional_iterator<It>
+        {
+            --i_;
+            return *this;
+        }
+
+        constexpr redifference_iterator operator--(int)
+            requires std::bidirectional_iterator<It>
+        {
+            return redifference_iterator{--i_};
+        }
+
+        constexpr redifference_iterator& operator+=(std::same_as<difference_type> auto n)
+            requires std::random_access_iterator<It>
+        {
+            i_ += static_cast<std::iter_difference_t<It>>(n);
+            return *this;
+        }
+
+        constexpr redifference_iterator& operator-=(std::same_as<difference_type> auto n)
+            requires std::random_access_iterator<It>
+        {
+            i_ -= static_cast<std::iter_difference_t<It>>(n);
+            return *this;
+        }
+
+        [[nodiscard]] constexpr decltype(auto) operator[](std::same_as<difference_type> auto n) const
+            requires std::random_access_iterator<It>
+        {
+            return i_[static_cast<std::iter_difference_t<It>>(n)];
+        }
+
+        [[nodiscard]] friend constexpr bool operator==(const redifference_iterator& i, const redifference_iterator& j) {
+            return i.i_ == j.i_;
+        }
+
+        [[nodiscard]] friend constexpr redifference_iterator operator+(
+            const redifference_iterator& it, std::same_as<difference_type> auto n)
+            requires std::random_access_iterator<It>
+        {
+            return redifference_iterator{it.i_ + static_cast<std::iter_difference_t<It>>(n)};
+        }
+
+        [[nodiscard]] friend constexpr redifference_iterator operator+(
+            std::same_as<difference_type> auto n, const redifference_iterator& it)
+            requires std::random_access_iterator<It>
+        {
+            return redifference_iterator{it.i_ + static_cast<std::iter_difference_t<It>>(n)};
+        }
+
+        [[nodiscard]] friend constexpr redifference_iterator operator-(
+            const redifference_iterator& it, std::same_as<difference_type> auto n)
+            requires std::random_access_iterator<It>
+        {
+            return redifference_iterator{it.i_ - static_cast<std::iter_difference_t<It>>(n)};
+        }
+
+        [[nodiscard]] friend constexpr difference_type operator-(
+            const redifference_iterator& i, const redifference_iterator& j)
+            requires std::random_access_iterator<It>
+        {
+            return static_cast<Diff>(i.i_ - j.i_);
+        }
+
+        [[nodiscard]] friend constexpr auto operator<=>(const redifference_iterator& i, const redifference_iterator& j)
+            requires std::random_access_iterator<It>
+        {
+            if constexpr (std::three_way_comparable<It>) {
+                return i.i_ <=> j.i_;
+            } else {
+                if (i.i_ < j.i_) {
+                    return std::weak_ordering::less;
+                } else if (j.i_ < i.i_) {
+                    return std::weak_ordering::greater;
+                } else {
+                    return std::weak_ordering::equivalent;
+                }
+            }
+        }
+
+        [[nodiscard]] friend constexpr bool operator<(const redifference_iterator& i, const redifference_iterator& j)
+            requires std::random_access_iterator<It>
+        {
+            return i.i_ < j.i_;
+        }
+
+        [[nodiscard]] friend constexpr bool operator>(const redifference_iterator& i, const redifference_iterator& j)
+            requires std::random_access_iterator<It>
+        {
+            return j.i_ < i.i_;
+        }
+
+        [[nodiscard]] friend constexpr bool operator<=(const redifference_iterator& i, const redifference_iterator& j)
+            requires std::random_access_iterator<It>
+        {
+            return !(j.i_ < i.i_);
+        }
+
+        [[nodiscard]] friend constexpr bool operator>=(const redifference_iterator& i, const redifference_iterator& j)
+            requires std::random_access_iterator<It>
+        {
+            return !(i.i_ < j.i_);
+        }
+
+        [[nodiscard]] constexpr const It& base() const noexcept {
+            return i_;
+        }
+
+    private:
+        It i_;
+    };
+
+    template <std::copyable S>
+    struct redifference_sentinel {
+        S se_;
+
+        template <std::_Signed_integer_like Diff, class It>
+            requires std::sentinel_for<S, It>
+        [[nodiscard]] friend constexpr bool operator==(
+            const redifference_iterator<Diff, It>& i, const redifference_sentinel& s) {
+            return i.base() == s.se_;
+        }
+
+        template <std::_Signed_integer_like Diff, class It>
+            requires std::sized_sentinel_for<S, It>
+        [[nodiscard]] friend constexpr Diff operator-(
+            const redifference_iterator<Diff, It>& i, const redifference_sentinel& s) {
+            return static_cast<Diff>(i.base() - s.se_);
+        }
+        template <std::_Signed_integer_like Diff, class It>
+            requires std::sized_sentinel_for<S, It>
+        [[nodiscard]] friend constexpr Diff operator-(
+            const redifference_sentinel& s, const redifference_iterator<Diff, It>& i) {
+            return static_cast<Diff>(s.se_ - i.base());
+        }
+    };
+
+    template <std::_Signed_integer_like Diff, ranges::borrowed_range Rng>
+    [[nodiscard]] constexpr auto make_redifference_subrange(Rng&& r) {
+        constexpr bool is_sized =
+            ranges::sized_range<Rng> || std::sized_sentinel_for<ranges::sentinel_t<Rng>, ranges::iterator_t<Rng>>;
+        using rediff_iter = redifference_iterator<Diff, ranges::iterator_t<Rng>>;
+        using rediff_sent = redifference_sentinel<ranges::sentinel_t<Rng>>;
+
+        if constexpr (is_sized) {
+            const auto sz = to_unsigned(static_cast<Diff>(ranges::distance(r)));
+            return ranges::subrange<rediff_iter, rediff_sent, ranges::subrange_kind::sized>{
+                rediff_iter{r.begin()}, rediff_sent{r.end()}, sz};
+        } else {
+            return ranges::subrange<rediff_iter, rediff_sent, ranges::subrange_kind::unsized>{
+                rediff_iter{r.begin()}, rediff_sent{r.end()}};
+        }
+    }
 } // namespace test
 
 template <class Category, class Element, test::Sized IsSized, test::CanDifference Diff, test::Common IsCommon,
diff --git a/tests/std/test.lst b/tests/std/test.lst
@@ -261,6 +261,7 @@ tests\LWG3528_make_from_tuple_impl
 tests\LWG3545_pointer_traits_sfinae
 tests\LWG3561_discard_block_engine_counter
 tests\LWG3610_iota_view_size_and_integer_class
+tests\LWG4105_ranges_ends_with_and_integer_class
 tests\P0009R18_mdspan_default_accessor
 tests\P0009R18_mdspan_extents
 tests\P0009R18_mdspan_extents_death
diff --git a/tests/std/tests/LWG4105_ranges_ends_with_and_integer_class/env.lst b/tests/std/tests/LWG4105_ranges_ends_with_and_integer_class/env.lst
@@ -0,0 +1,4 @@
+# Copyright (c) Microsoft Corporation.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+
+RUNALL_INCLUDE ..\strict_latest_matrix.lst
diff --git a/tests/std/tests/LWG4105_ranges_ends_with_and_integer_class/test.cpp b/tests/std/tests/LWG4105_ranges_ends_with_and_integer_class/test.cpp
@@ -0,0 +1,120 @@
+// Copyright (c) Microsoft Corporation.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+
+#include <algorithm>
+#include <cassert>
+#include <functional>
+#include <ranges>
+#include <span>
+#include <utility>
+
+#include <range_algorithm_support.hpp>
+
+using namespace std;
+
+template <class T>
+concept testable_range = ranges::input_range<T> && (ranges::forward_range<T> || ranges::sized_range<T>);
+
+template <class T>
+concept testable_sentinel =
+    ranges::input_range<T>
+    && (ranges::forward_range<T> || sized_sentinel_for<ranges::sentinel_t<T>, ranges::iterator_t<T>>);
+
+struct instantiator {
+    static constexpr pair<int, int> haystack[]       = {{0, 42}, {1, 42}, {2, 42}, {4, 42}};
+    static constexpr pair<int, int> short_haystack[] = {{4, 42}};
+    static constexpr pair<long, long> long_needle[]  = {{13, 1}, {13, 2}, {13, 4}};
+    static constexpr pair<long, long> short_needle[] = {{13, 2}, {13, 4}};
+    static constexpr pair<long, long> wrong_needle[] = {{13, 2}, {13, 3}};
+
+    template <std::_Signed_integer_like Diff1, testable_range In1, std::_Signed_integer_like Diff2, testable_range In2>
+    static constexpr void test_range_rediff() {
+        using ranges::ends_with, ranges::equal_to;
+
+        {
+            In1 r1{haystack};
+            In2 r2{long_needle};
+            const same_as<bool> auto match = ends_with(test::make_redifference_subrange<Diff1>(r1),
+                test::make_redifference_subrange<Diff2>(r2), equal_to{}, get_first, get_second);
+            assert(match);
+        }
+        {
+            In1 r1{haystack};
+            In2 r2{short_needle};
+            const same_as<bool> auto match = ends_with(test::make_redifference_subrange<Diff1>(r1),
+                test::make_redifference_subrange<Diff2>(r2), equal_to{}, get_first, get_second);
+            assert(match);
+        }
+        {
+            In1 r1{haystack};
+            In2 r2{wrong_needle};
+            const same_as<bool> auto match = ends_with(test::make_redifference_subrange<Diff1>(r1),
+                test::make_redifference_subrange<Diff2>(r2), equal_to{}, get_first, get_second);
+            assert(!match);
+        }
+        {
+            In1 r1{short_haystack};
+            In2 r2{short_needle};
+            const same_as<bool> auto match = ends_with(test::make_redifference_subrange<Diff1>(r1),
+                test::make_redifference_subrange<Diff2>(r2), equal_to{}, get_first, get_second);
+            assert(!match);
+        }
+        {
+            In1 r1{haystack};
+            In2 r2{span<pair<long, long>, 0>{}};
+            const same_as<bool> auto match = ends_with(test::make_redifference_subrange<Diff1>(r1),
+                test::make_redifference_subrange<Diff2>(r2), equal_to{}, get_first, get_second);
+            assert(match);
+        }
+    }
+
+    template <ranges::input_range In1, ranges::input_range In2>
+    static void call() {
+        if constexpr (testable_range<In1> && testable_range<In2>) {
+            using int_class = ranges::range_difference_t<ranges::iota_view<long long>>;
+
+            test_range_rediff<int_class, In1, short, In2>();
+            static_assert((test_range_rediff<int_class, In1, short, In2>(), true));
+
+            test_range_rediff<short, In1, int_class, In2>();
+            static_assert((test_range_rediff<short, In1, int_class, In2>(), true));
+        }
+    }
+};
+
+#ifdef TEST_EVERYTHING
+int main() {
+#if !defined(_PREFAST_) && !defined(__EDG__) // TRANSITION, GH-1030 and GH-3567
+    test_in_in<instantiator, const pair<int, int>, const pair<long, long>>();
+#endif // ^^^ no workaround ^^^
+}
+#else // ^^^ test all permutations of range properties / test only interesting permutations vvv
+template <class R>
+void run_tests_inner() {
+    instantiator::call<R, test::range<test::input, const pair<long, long>, test::Sized::yes>>();
+    instantiator::call<R, test::range<test::fwd, const pair<long, long>, test::Sized::no>>();
+    instantiator::call<R, test::range<test::fwd, const pair<long, long>, test::Sized::yes>>();
+    instantiator::call<R, test::range<test::bidi, const pair<long, long>, test::Sized::no>>();
+    instantiator::call<R, test::range<test::bidi, const pair<long, long>, test::Sized::yes>>();
+    instantiator::call<R, test::range<test::random, const pair<long, long>, test::Sized::no>>();
+    instantiator::call<R, test::range<test::random, const pair<long, long>, test::Sized::yes>>();
+    instantiator::call<R, test::range<test::contiguous, const pair<long, long>, test::Sized::no>>();
+    instantiator::call<R, test::range<test::contiguous, const pair<long, long>, test::Sized::yes>>();
+}
+
+void run_tests() {
+    run_tests_inner<test::range<test::input, const pair<int, int>, test::Sized::yes>>();
+    run_tests_inner<test::range<test::fwd, const pair<int, int>, test::Sized::no>>();
+    run_tests_inner<test::range<test::fwd, const pair<int, int>, test::Sized::yes>>();
+    run_tests_inner<test::range<test::bidi, const pair<int, int>, test::Sized::no>>();
+    run_tests_inner<test::range<test::bidi, const pair<int, int>, test::Sized::yes>>();
+    run_tests_inner<test::range<test::random, const pair<int, int>, test::Sized::no>>();
+    run_tests_inner<test::range<test::random, const pair<int, int>, test::Sized::yes>>();
+    run_tests_inner<test::range<test::contiguous, const pair<int, int>, test::Sized::no>>();
+    run_tests_inner<test::range<test::contiguous, const pair<int, int>, test::Sized::yes>>();
+}
+
+int main() {
+    run_tests();
+}
+#endif // TEST_EVERYTHING
