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, c++20
10 
11 // <ranges>
12 
13 // constexpr iterator& operator--();
14 // constexpr iterator operator--(int);
15 
16 #include <ranges>
17 
18 #include <array>
19 #include <cassert>
20 #include <concepts>
21 #include <functional>
22 #include <span>
23 #include <type_traits>
24 #include <utility>
25 
26 #include "../types.h"
27 #include "test_iterators.h"
28 #include "test_macros.h"
29 
30 template <class T>
31 concept HasPreDecrement = requires(T t) {
32   { --t };
33 };
34 
35 template <class T>
36 concept HasPostDecrement = requires(T t) {
37   { t-- };
38 };
39 
40 struct TrackingPred : TrackInitialization {
41   using TrackInitialization::TrackInitialization;
operator ()TrackingPred42   constexpr bool operator()(int x, int y) const { return x <= y; }
43 };
44 
45 template <class Iter, IsConst Constant, class Sent = sentinel_wrapper<Iter>>
test()46 constexpr void test() {
47   using Underlying      = View<Iter, Sent>;
48   using ChunkByView     = std::ranges::chunk_by_view<Underlying, std::ranges::less_equal>;
49   using ChunkByIterator = std::ranges::iterator_t<ChunkByView>;
50 
51   static_assert(HasPostDecrement<ChunkByIterator>);
52   static_assert(HasPreDecrement<ChunkByIterator>);
53 
54   auto make_chunk_by_view = [](auto& arr) {
55     View view{Iter{arr.data()}, Sent{Iter{arr.data() + arr.size()}}};
56     return ChunkByView{std::move(view), std::ranges::less_equal{}};
57   };
58 
59   // Test with a single chunk
60   {
61     std::array array{0, 1, 2, 3, 4};
62     ChunkByView view   = make_chunk_by_view(array);
63     ChunkByIterator it = std::ranges::next(view.begin(), view.end());
64 
65     std::same_as<ChunkByIterator&> decltype(auto) result = --it;
66     assert(&result == &it);
67     assert(base((*result).begin()) == array.data());
68   }
69 
70   // Test with two chunks
71   {
72     std::array array{0, 1, 2, 0, 1, 2};
73     ChunkByView view   = make_chunk_by_view(array);
74     ChunkByIterator it = std::ranges::next(view.begin(), view.end());
75 
76     std::same_as<ChunkByIterator&> decltype(auto) result = --it;
77     assert(&result == &it);
78     assert(base((*result).begin()) == array.data() + 3);
79 
80     --it;
81     assert(base((*result).begin()) == array.data());
82   }
83 
84   // Test going forward and then backward on the same iterator
85   {
86     std::array array{7, 8, 9, 4, 5, 6, 1, 2, 3, 0};
87     ChunkByView view   = make_chunk_by_view(array);
88     ChunkByIterator it = view.begin();
89 
90     ++it;
91     --it;
92     assert(base((*it).begin()) == array.data());
93     assert(base((*it).end()) == array.data() + 3);
94 
95     ++it;
96     ++it;
97     --it;
98     assert(base((*it).begin()) == array.data() + 3);
99     assert(base((*it).end()) == array.data() + 6);
100 
101     ++it;
102     ++it;
103     --it;
104     assert(base((*it).begin()) == array.data() + 6);
105     assert(base((*it).end()) == array.data() + 9);
106 
107     ++it;
108     ++it;
109     --it;
110     assert(base((*it).begin()) == array.data() + 9);
111   }
112 
113   // Decrement an iterator multiple times
114   if constexpr (std::ranges::common_range<Underlying>) {
115     std::array array{1, 2, 1, 2, 1};
116     ChunkByView view = make_chunk_by_view(array);
117 
118     ChunkByIterator it = view.end();
119     --it;
120     --it;
121     --it;
122     assert(base((*it).begin()) == array.data());
123   }
124 
125   // Test with a predicate that takes by non-const reference
126   if constexpr (!std::to_underlying(Constant)) {
127     std::array array{1, 2, 3, -3, -2, -1};
128     View v{Iter{array.data()}, Sent{Iter{array.data() + array.size()}}};
129     auto view = std::views::chunk_by(std::move(v), [](int& x, int& y) { return x <= y; });
130 
131     auto it = std::ranges::next(view.begin());
132     assert(base((*it).begin()) == array.data() + 3);
133     --it;
134     assert(base((*it).begin()) == array.data());
135   }
136 
137   // Test with a predicate that is invocable but not callable (i.e. cannot be called like regular function 'f()')
138   {
139     std::array array = {1, 2, 3, -3, -2, -1};
140     auto v           = View{Iter{array.data()}, Sent{Iter{array.data() + array.size()}}} |
141              std::views::transform([](int x) { return IntWrapper{x}; });
142     auto view = std::views::chunk_by(std::move(v), &IntWrapper::lessEqual);
143 
144     auto it = std::ranges::next(view.begin());
145     assert(base((*it).begin().base()) == array.data() + 3);
146     --it;
147     assert(base((*it).begin().base()) == array.data());
148   }
149 
150   // Make sure we do not make a copy of the predicate when we decrement
151   if constexpr (std::ranges::common_range<Underlying>) {
152     bool moved = false, copied = false;
153     std::array array{1, 2, 1, 3};
154     View v{Iter(array.data()), Sent(Iter(array.data() + array.size()))};
155     auto view = std::views::chunk_by(std::move(v), TrackingPred(&moved, &copied));
156     assert(std::exchange(moved, false));
157     auto it = view.end();
158     --it;
159     it--;
160     assert(!moved);
161     assert(!copied);
162   }
163 
164   // Check post-decrement
165   {
166     std::array array{0, 1, 2, -3, -2, -1, -6, -5, -4};
167     ChunkByView view   = make_chunk_by_view(array);
168     ChunkByIterator it = std::ranges::next(view.begin(), view.end());
169 
170     std::same_as<ChunkByIterator> decltype(auto) result = it--;
171     assert(result != it);
172     assert(result == std::default_sentinel);
173     assert(base((*it).begin()) == array.data() + 6);
174 
175     result = it--;
176     assert(base((*it).begin()) == array.data() + 3);
177     assert(base((*result).begin()) == array.data() + 6);
178 
179     result = it--;
180     assert(base((*it).begin()) == array.data());
181     assert(base((*result).begin()) == array.data() + 3);
182   }
183 }
184 
185 template <class Iterator, IsConst Constant>
test_with_pair()186 constexpr void test_with_pair() {
187   // Test with pair of iterators
188   test<Iterator, Constant>();
189 
190   // Test with iterator-sentinel pair
191   test<Iterator, Constant, Iterator>();
192 }
193 
tests()194 constexpr bool tests() {
195   test_with_pair<bidirectional_iterator<int*>, IsConst::no>();
196   test_with_pair<random_access_iterator<int*>, IsConst::no>();
197   test_with_pair<contiguous_iterator<int*>, IsConst::no>();
198   test_with_pair<int*, IsConst::no>();
199 
200   test_with_pair<bidirectional_iterator<int const*>, IsConst::yes>();
201   test_with_pair<random_access_iterator<int const*>, IsConst::yes>();
202   test_with_pair<contiguous_iterator<int const*>, IsConst::yes>();
203   test_with_pair<int const*, IsConst::yes>();
204 
205   // Make sure `operator--` isn't provided for non bidirectional ranges
206   {
207     using ForwardView = View<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>;
208     using ChunkByView = std::ranges::chunk_by_view<ForwardView, std::ranges::less_equal>;
209     static_assert(!HasPreDecrement<std::ranges::iterator_t<ChunkByView>>);
210     static_assert(!HasPostDecrement<std::ranges::iterator_t<ChunkByView>>);
211   }
212 
213   return true;
214 }
215 
main(int,char **)216 int main(int, char**) {
217   tests();
218   static_assert(tests());
219 
220   return 0;
221 }
222