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
11// ranges::advance(it, n, sent)
12
13#include <iterator>
14
15#include <cassert>
16#include <climits>
17#include <concepts>
18#include <cstddef>
19
20#include "test_iterators.h"
21#include "../types.h"
22
23template <bool Count, typename It>
24constexpr void
25check_forward(int* first, int* last, std::iter_difference_t<It> n, int* expected, int expected_equals_count = -1) {
26 using Difference = std::iter_difference_t<It>;
27 Difference const M = (expected - first); // expected travel distance
28 // `expected_equals_count` is only relevant when `Count` is true.
29 assert(Count || expected_equals_count == -1);
30
31 {
32 It it(first);
33 auto sent = sentinel_wrapper(It(last));
34 std::same_as<Difference> auto result = std::ranges::advance(it, n, sent);
35 assert(result == n - M);
36 assert(base(it) == expected);
37 }
38
39 // Count operations
40 if constexpr (Count) {
41 IteratorOpCounts ops;
42 auto it = operation_counting_iterator(It(first), &ops);
43 auto sent = sentinel_wrapper(operation_counting_iterator(It(last), &ops));
44 (void)std::ranges::advance(it, n, sent);
45 // We don't have a sized sentinel, so we have to increment one-by-one
46 // regardless of the iterator category.
47 assert(static_cast<Difference>(ops.increments) == M);
48 assert(static_cast<Difference>(ops.decrements) == 0);
49 assert(ops.zero_moves == 0);
50 assert(ops.equal_cmps == static_cast<std::size_t>(expected_equals_count));
51 }
52}
53
54template <typename It>
55constexpr void check_forward_sized_sentinel(int* first, int* last, std::iter_difference_t<It> n, int* expected) {
56 using Difference = std::iter_difference_t<It>;
57 Difference const size = (last - first);
58 Difference const M = (expected - first); // expected travel distance
59
60 {
61 It it(first);
62 auto sent = distance_apriori_sentinel(size);
63 std::same_as<Difference> auto result = std::ranges::advance(it, n, sent);
64 assert(result == n - M);
65 assert(base(it) == expected);
66 }
67
68 // Count operations
69 {
70 IteratorOpCounts ops;
71 auto it = operation_counting_iterator(It(first), &ops);
72 auto sent = distance_apriori_sentinel(size);
73 (void)std::ranges::advance(it, n, sent);
74 if constexpr (std::random_access_iterator<It>) {
75 assert(ops.increments + ops.zero_moves == 1);
76 assert(ops.decrements == 0);
77 } else {
78 assert(static_cast<Difference>(ops.increments) == M);
79 assert(ops.decrements == 0);
80 assert(ops.zero_moves == 0);
81 }
82 }
83}
84
85template <bool Count, typename It>
86constexpr void
87check_backward(int* first, int* last, std::iter_difference_t<It> n, int* expected, IteratorOpCounts expected_counts) {
88 // Check preconditions for `advance` when called with negative `n`
89 // (see [range.iter.op.advance]). In addition, allow `n == 0`.
90 assert(n <= 0);
91 static_assert(std::bidirectional_iterator<It>);
92
93 using Difference = std::iter_difference_t<It>;
94 Difference const M = (expected - last); // expected travel distance (which is negative)
95
96 {
97 It it(last);
98 It sent(first);
99 std::same_as<Difference> auto result = std::ranges::advance(it, n, sent);
100 assert(result == n - M);
101 assert(base(it) == expected);
102 }
103
104 // Count operations
105 {
106 IteratorOpCounts ops;
107 auto it = operation_counting_iterator(It(last), &ops);
108 auto sent = operation_counting_iterator(It(first), &ops);
109 static_assert(std::bidirectional_iterator<operation_counting_iterator<It>>);
110 static_assert(Count == !std::sized_sentinel_for<It, It>);
111
112 (void)std::ranges::advance(it, n, sent);
113
114 assert(ops.increments == expected_counts.increments);
115 assert(ops.decrements == expected_counts.decrements);
116 assert(ops.zero_moves == expected_counts.zero_moves);
117 assert(ops.equal_cmps == expected_counts.equal_cmps);
118 }
119}
120
121struct iota_iterator {
122 using difference_type = int;
123 using value_type = int;
124
125 constexpr int operator*() const { return x; }
126 constexpr iota_iterator& operator++() { ++x; return *this; }
127 constexpr iota_iterator operator++(int) { ++x; return iota_iterator{.x: x - 1}; }
128 constexpr bool operator==(const iota_iterator&) const = default;
129 constexpr int operator-(const iota_iterator& that) const { return x - that.x; }
130 constexpr iota_iterator& operator--() { --x; return *this; }
131 constexpr iota_iterator operator--(int) { --x; return iota_iterator{.x: x + 1}; }
132
133 int x;
134};
135static_assert(std::bidirectional_iterator<iota_iterator>);
136static_assert(std::sized_sentinel_for<iota_iterator, iota_iterator>);
137
138constexpr bool test() {
139 int range[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
140
141 // Basic functionality test: advance forward, bound has the same type
142 {
143 int *p;
144 p = range+5; assert(std::ranges::advance(p, 0, range+7) == 0); assert(p == range+5);
145 p = range+5; assert(std::ranges::advance(p, 1, range+7) == 0); assert(p == range+6);
146 p = range+5; assert(std::ranges::advance(p, 2, range+7) == 0); assert(p == range+7);
147 p = range+5; assert(std::ranges::advance(p, 3, range+7) == 1); assert(p == range+7);
148 }
149
150 // Basic functionality test: advance forward, bound is not the same type and not assignable
151 {
152 int *p;
153 using ConstPtr = const int*;
154 p = range+5; assert(std::ranges::advance(p, 0, ConstPtr(range+7)) == 0); assert(p == range+5);
155 p = range+5; assert(std::ranges::advance(p, 1, ConstPtr(range+7)) == 0); assert(p == range+6);
156 p = range+5; assert(std::ranges::advance(p, 2, ConstPtr(range+7)) == 0); assert(p == range+7);
157 p = range+5; assert(std::ranges::advance(p, 3, ConstPtr(range+7)) == 1); assert(p == range+7);
158 }
159
160 // Basic functionality test: advance forward, bound has different type but assignable
161 {
162 const int *pc;
163 pc = range+5; assert(std::ranges::advance(pc, 0, range+7) == 0); assert(pc == range+5);
164 pc = range+5; assert(std::ranges::advance(pc, 1, range+7) == 0); assert(pc == range+6);
165 pc = range+5; assert(std::ranges::advance(pc, 2, range+7) == 0); assert(pc == range+7);
166 pc = range+5; assert(std::ranges::advance(pc, 3, range+7) == 1); assert(pc == range+7);
167 }
168
169 // Basic functionality test: advance backward, bound has the same type
170 // Note that we don't test advancing backward with a bound of a different type because that's UB
171 {
172 int *p;
173 p = range+5; assert(std::ranges::advance(p, 0, range+3) == 0); assert(p == range+5);
174 p = range+5; assert(std::ranges::advance(p, -1, range+3) == 0); assert(p == range+4);
175 p = range+5; assert(std::ranges::advance(p, -2, range+3) == 0); assert(p == range+3);
176 p = range+5; assert(std::ranges::advance(p, -3, range+3) == -1); assert(p == range+3);
177 }
178
179 // Basic functionality test: advance backward with an array as a sentinel
180 {
181 int* p;
182 p = range+5; assert(std::ranges::advance(p, 0, range) == 0); assert(p == range+5);
183 p = range+5; assert(std::ranges::advance(p, -1, range) == 0); assert(p == range+4);
184 p = range+5; assert(std::ranges::advance(p, -5, range) == 0); assert(p == range);
185 p = range+5; assert(std::ranges::advance(p, -6, range) == -1); assert(p == range);
186 }
187
188 // Exhaustive checks for n and range sizes
189 for (int size = 0; size != 10; ++size) {
190 for (int n = 0; n != 20; ++n) {
191
192 {
193 int* expected = n > size ? range + size : range + n;
194 int equals_count = n > size ? size + 1 : n;
195
196 // clang-format off
197 check_forward<false, cpp17_input_iterator<int*>>( range, range+size, n, expected);
198 check_forward<false, cpp20_input_iterator<int*>>( range, range+size, n, expected);
199 check_forward<true, forward_iterator<int*>>( range, range+size, n, expected, equals_count);
200 check_forward<true, bidirectional_iterator<int*>>(range, range+size, n, expected, equals_count);
201 check_forward<true, random_access_iterator<int*>>(range, range+size, n, expected, equals_count);
202 check_forward<true, contiguous_iterator<int*>>( range, range+size, n, expected, equals_count);
203 check_forward<true, int*>( range, range+size, n, expected, equals_count);
204 // clang-format on
205
206 check_forward_sized_sentinel<cpp17_input_iterator<int*>>( range, range+size, n, expected);
207 check_forward_sized_sentinel<cpp20_input_iterator<int*>>( range, range+size, n, expected);
208 check_forward_sized_sentinel<forward_iterator<int*>>( range, range+size, n, expected);
209 check_forward_sized_sentinel<bidirectional_iterator<int*>>(range, range+size, n, expected);
210 check_forward_sized_sentinel<random_access_iterator<int*>>(range, range+size, n, expected);
211 check_forward_sized_sentinel<contiguous_iterator<int*>>( range, range+size, n, expected);
212 check_forward_sized_sentinel<int*>( range, range+size, n, expected);
213 }
214
215 // Input and forward iterators are not tested as the backwards case does
216 // not apply for them.
217 {
218 int* expected = n > size ? range : range + size - n;
219 {
220 IteratorOpCounts expected_counts = {
221 .increments = 0,
222 .decrements = static_cast<std::size_t>(range + size - expected),
223 .equal_cmps = static_cast<std::size_t>(n > size ? size + 1 : n),
224 };
225
226 check_backward<true, bidirectional_iterator<int*>>(range, range + size, -n, expected, expected_counts);
227 }
228 {
229 IteratorOpCounts expected_counts = {
230 // If `n >= size`, the algorithm can just do `it = std::move(sent);`
231 // instead of doing iterator arithmetic.
232 .increments = 0,
233 .decrements = static_cast<std::size_t>((n == 0 || n >= size) ? 0 : 1),
234 .zero_moves = static_cast<std::size_t>(n == 0 && size != 0 ? 1 : 0),
235 .equal_cmps = 0,
236 };
237
238 check_backward<false, random_access_iterator<int*>>(range, range + size, -n, expected, expected_counts);
239 check_backward<false, contiguous_iterator<int*>>(range, range + size, -n, expected, expected_counts);
240 check_backward<false, int*>(range, range + size, -n, expected, expected_counts);
241 }
242 }
243 }
244 }
245
246 // Regression-test that INT_MIN doesn't cause any undefined behavior
247 {
248 auto i = iota_iterator{.x: +1};
249 assert(std::ranges::advance(i, INT_MIN, iota_iterator{-2}) == INT_MIN+3);
250 assert(i == iota_iterator{-2});
251 i = iota_iterator{.x: +1};
252 assert(std::ranges::advance(i, -2, iota_iterator{INT_MIN+1}) == 0);
253 assert(i == iota_iterator{-1});
254 i = iota_iterator{.x: +1};
255 assert(std::ranges::advance(i, INT_MIN, iota_iterator{INT_MIN+1}) == 0);
256 assert(i == iota_iterator{INT_MIN+1});
257 }
258
259 return true;
260}
261
262int main(int, char**) {
263 assert(test());
264 static_assert(test());
265 return 0;
266}
267

source code of libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/iterator_count_sentinel.pass.cpp