1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 // UNSUPPORTED: c++03, c++11, c++14, c++17
10 // UNSUPPORTED: libcpp-no-concepts
11 // UNSUPPORTED: gcc-10
12
13 // ranges::advance(it, n, sent)
14
15 #include <iterator>
16
17 #include <array>
18 #include <cassert>
19 #include <climits>
20
21 #include "test_iterators.h"
22
23 using range_t = std::array<int, 10>;
24
25 class distance_apriori_sentinel {
26 public:
27 distance_apriori_sentinel() = default;
distance_apriori_sentinel(std::ptrdiff_t const count)28 constexpr explicit distance_apriori_sentinel(std::ptrdiff_t const count) : count_(count) {}
29
operator ==(std::input_or_output_iterator auto const &) const30 constexpr bool operator==(std::input_or_output_iterator auto const&) const {
31 assert(false && "difference op should take precedence");
32 return false;
33 }
34
operator -(std::input_or_output_iterator auto const &,distance_apriori_sentinel const y)35 friend constexpr std::ptrdiff_t operator-(std::input_or_output_iterator auto const&,
36 distance_apriori_sentinel const y) {
37 return -y.count_;
38 }
39
operator -(distance_apriori_sentinel const x,std::input_or_output_iterator auto const &)40 friend constexpr std::ptrdiff_t operator-(distance_apriori_sentinel const x,
41 std::input_or_output_iterator auto const&) {
42 return x.count_;
43 }
44
45 private:
46 std::ptrdiff_t count_ = 0;
47 };
48
49 struct expected_t {
50 range_t::const_iterator coordinate;
51 std::ptrdiff_t result;
52 };
53
54 template <std::input_or_output_iterator It>
check_forward_sized_sentinel(std::ptrdiff_t n,expected_t expected,range_t & range)55 constexpr void check_forward_sized_sentinel(std::ptrdiff_t n, expected_t expected, range_t& range) {
56 using Difference = std::iter_difference_t<It>;
57 auto current = stride_counting_iterator(It(range.begin()));
58 Difference const result = std::ranges::advance(current, n, distance_apriori_sentinel(range.size()));
59 assert(current.base().base() == expected.coordinate);
60 assert(result == expected.result);
61
62 if constexpr (std::random_access_iterator<It>) {
63 assert(current.stride_count() == 0 || current.stride_count() == 1);
64 assert(current.stride_displacement() == current.stride_count());
65 } else {
66 assert(current.stride_count() == (n - result));
67 assert(current.stride_displacement() == (n - result));
68 }
69 }
70
71 template <std::random_access_iterator It>
check_backward_sized_sentinel(std::ptrdiff_t n,expected_t expected,range_t & range)72 constexpr void check_backward_sized_sentinel(std::ptrdiff_t n, expected_t expected, range_t& range) {
73 using Difference = std::iter_difference_t<It>;
74 auto current = stride_counting_iterator(It(range.end()));
75 Difference const result = std::ranges::advance(current, -n, stride_counting_iterator(It(range.begin())));
76 assert(current.base().base() == expected.coordinate);
77 assert(result == expected.result);
78
79 assert(current.stride_count() == 0 || current.stride_count() == 1);
80 assert(current.stride_displacement() == current.stride_count());
81 }
82
83 template <std::input_or_output_iterator It>
check_forward(std::ptrdiff_t n,expected_t expected,range_t & range)84 constexpr void check_forward(std::ptrdiff_t n, expected_t expected, range_t& range) {
85 using Difference = std::iter_difference_t<It>;
86 auto current = stride_counting_iterator(It(range.begin()));
87 Difference const result = std::ranges::advance(current, n, sentinel_wrapper(It(range.end())));
88 assert(current.base().base() == expected.coordinate);
89 assert(result == expected.result);
90 assert(current.stride_count() == n - result);
91 }
92
93 template <std::bidirectional_iterator It>
check_backward(std::ptrdiff_t n,expected_t expected,range_t & range)94 constexpr void check_backward(std::ptrdiff_t n, expected_t expected, range_t& range) {
95 using Difference = std::iter_difference_t<It>;
96 auto current = stride_counting_iterator(It(range.end()));
97 Difference const result = std::ranges::advance(current, -n, stride_counting_iterator(It(range.begin())));
98 assert(current.base().base() == expected.coordinate);
99 assert(result == expected.result);
100 assert(current.stride_count() == n + result);
101 assert(current.stride_count() == -current.stride_displacement());
102 }
103
104 struct iota_iterator {
105 using difference_type = int;
106 using value_type = int;
107
operator *iota_iterator108 constexpr int operator*() const { return x; }
operator ++iota_iterator109 constexpr iota_iterator& operator++() { ++x; return *this; }
operator ++iota_iterator110 constexpr iota_iterator operator++(int) { ++x; return iota_iterator{x - 1}; }
111 constexpr bool operator==(const iota_iterator&) const = default;
operator -iota_iterator112 constexpr int operator-(const iota_iterator& that) const { return x - that.x; }
operator --iota_iterator113 constexpr iota_iterator& operator--() { --x; return *this; }
operator --iota_iterator114 constexpr iota_iterator operator--(int) { --x; return iota_iterator{x + 1}; }
115
116 int x;
117 };
118 static_assert(std::bidirectional_iterator<iota_iterator>);
119 static_assert(std::sized_sentinel_for<iota_iterator, iota_iterator>);
120
test()121 constexpr bool test() {
122 auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
123 check_forward_sized_sentinel<cpp17_input_iterator<range_t::const_iterator> >(1, {range.begin() + 1, 0}, range);
124 // cpp20_input_iterator not copyable, so is omitted
125 check_forward_sized_sentinel<forward_iterator<range_t::const_iterator> >(3, {range.begin() + 3, 0}, range);
126 check_forward_sized_sentinel<bidirectional_iterator<range_t::const_iterator> >(4, {range.begin() + 4, 0}, range);
127 check_forward_sized_sentinel<random_access_iterator<range_t::const_iterator> >(5, {range.begin() + 5, 0}, range);
128 check_forward_sized_sentinel<contiguous_iterator<range_t::const_iterator> >(6, {range.begin() + 6, 0}, range);
129
130 // bidirectional_iterator omitted because the `n < 0` case requires `same_as<I, S>`
131 check_backward_sized_sentinel<random_access_iterator<range_t::const_iterator> >(5, {range.begin() + 5, 0}, range);
132 check_backward_sized_sentinel<contiguous_iterator<range_t::const_iterator> >(6, {range.begin() + 4, 0}, range);
133
134 // distance == range.size()
135 check_forward_sized_sentinel<forward_iterator<range_t::const_iterator> >(10, {range.end(), 0}, range);
136 check_backward_sized_sentinel<random_access_iterator<range_t::const_iterator> >(10, {range.begin(), 0}, range);
137
138 // distance > range.size()
139 check_forward_sized_sentinel<forward_iterator<range_t::const_iterator> >(1000, {range.end(), 990}, range);
140 check_backward_sized_sentinel<random_access_iterator<range_t::const_iterator> >(1000, {range.begin(), -990}, range);
141
142 check_forward<cpp17_input_iterator<range_t::const_iterator> >(1, {range.begin() + 1, 0}, range);
143 check_forward<forward_iterator<range_t::const_iterator> >(3, {range.begin() + 3, 0}, range);
144 check_forward<bidirectional_iterator<range_t::const_iterator> >(4, {range.begin() + 4, 0}, range);
145 check_forward<random_access_iterator<range_t::const_iterator> >(5, {range.begin() + 5, 0}, range);
146 check_forward<contiguous_iterator<range_t::const_iterator> >(6, {range.begin() + 6, 0}, range);
147 check_backward<bidirectional_iterator<range_t::const_iterator> >(8, {range.begin() + 2, 0}, range);
148
149 // distance == range.size()
150 check_forward<forward_iterator<range_t::const_iterator> >(10, {range.end(), 0}, range);
151 check_backward<bidirectional_iterator<range_t::const_iterator> >(10, {range.begin(), 0}, range);
152
153 // distance > range.size()
154 check_forward<forward_iterator<range_t::const_iterator> >(1000, {range.end(), 990}, range);
155 check_backward<bidirectional_iterator<range_t::const_iterator> >(1000, {range.begin(), -990}, range);
156
157 // regression-test that INT_MIN doesn't cause any undefined behavior
158 {
159 auto i = iota_iterator{+1};
160 assert(std::ranges::advance(i, INT_MIN, iota_iterator{-2}) == INT_MIN+3);
161 assert(i == iota_iterator{-2});
162 i = iota_iterator{+1};
163 assert(std::ranges::advance(i, -2, iota_iterator{INT_MIN+1}) == 0);
164 assert(i == iota_iterator{-1});
165 i = iota_iterator{+1};
166 assert(std::ranges::advance(i, INT_MIN, iota_iterator{INT_MIN+1}) == 0);
167 assert(i == iota_iterator{INT_MIN+1});
168 }
169
170 return true;
171 }
172
main(int,char **)173 int main(int, char**) {
174 assert(test());
175 static_assert(test());
176 return 0;
177 }
178