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 // Check that all STL classic algorithms can be instantiated with a C++20-hostile iterator
10 
11 // ADDITIONAL_COMPILE_FLAGS: -Wno-ambiguous-reversed-operator
12 
13 #include <algorithm>
14 #include <functional>
15 #include <iterator>
16 #include <random>
17 
18 #include "test_macros.h"
19 
20 template <class Sub, class Iterator>
21 struct IteratorAdaptorBase {
22   using OutTraits = std::iterator_traits<Iterator>;
23   using iterator_category = typename OutTraits::iterator_category;
24   using value_type = typename OutTraits::value_type;
25   using pointer = typename OutTraits::pointer;
26   using reference = typename OutTraits::reference;
27   using difference_type = typename OutTraits::difference_type;
28 
29   IteratorAdaptorBase() {}
30   IteratorAdaptorBase(Iterator) {}
31 
32   Sub& sub() { return static_cast<Sub&>(*this); }
33   const Sub& sub() const { return static_cast<Sub&>(*this); }
34 
35   const Iterator& base() const { return it_; }
36 
37   reference get() const { return *it_; }
38   reference operator*() const { return *it_; }
39   pointer operator->() const { return it_; }
40   reference operator[](difference_type) const { return *it_; }
41 
42   Sub& operator++() { return static_cast<Sub&>(*this); }
43   Sub& operator--() { return static_cast<Sub&>(*this); }
44   Sub operator++(int) { return static_cast<Sub&>(*this); }
45   Sub operator--(int) { return static_cast<Sub&>(*this); }
46 
47   Sub& operator+=(difference_type) { return static_cast<Sub&>(*this); }
48   Sub& operator-=(difference_type) { return static_cast<Sub&>(*this); }
49   bool operator==(Sub) const { return false; }
50   bool operator!=(Sub) const { return false; }
51   bool operator==(Iterator b) const { return *this == Sub(b); }
52   bool operator!=(Iterator b) const { return *this != Sub(b); }
53 
54   friend Sub operator+(Sub, difference_type) { return Sub(); }
55   friend Sub operator+(difference_type, Sub) { return Sub(); }
56   friend Sub operator-(Sub, difference_type) { return Sub(); }
57   friend difference_type operator-(Sub, Sub) { return 0; }
58 
59   friend bool operator<(Sub, Sub) { return false; }
60   friend bool operator>(Sub, Sub) { return false; }
61   friend bool operator<=(Sub, Sub) { return false; }
62   friend bool operator>=(Sub, Sub) { return false; }
63 
64  private:
65   Iterator it_;
66 };
67 
68 template <typename It>
69 struct Cpp20HostileIterator
70     : IteratorAdaptorBase<Cpp20HostileIterator<It>, It> {
71   Cpp20HostileIterator() {}
72   Cpp20HostileIterator(It) {}
73 };
74 
75 struct Pred {
76   bool operator()(int, int) const { return false; }
77   bool operator()(int) const { return false; }
78   int operator()() const { return 0; }
79 };
80 
81 void test() {
82   Cpp20HostileIterator<int*> it;
83   Pred pred;
84   std::mt19937_64 rng;
85 
86   (void) std::adjacent_find(it, it);
87   (void) std::adjacent_find(it, it, pred);
88   (void) std::all_of(it, it, pred);
89   (void) std::any_of(it, it, pred);
90   (void) std::binary_search(it, it, 0);
91   (void) std::binary_search(it, it, 0, pred);
92   (void) std::copy_backward(it, it, it);
93   (void) std::copy_if(it, it, it, pred);
94   (void) std::copy_n(it, 0, it);
95   (void) std::copy(it, it, it);
96   (void) std::count_if(it, it, pred);
97   (void) std::count(it, it, 0);
98   (void) std::equal_range(it, it, 0);
99   (void) std::equal_range(it, it, 0, pred);
100   (void) std::equal(it, it, it);
101   (void) std::equal(it, it, it, pred);
102 #if TEST_STD_VER > 11
103   (void) std::equal(it, it, it, it);
104   (void) std::equal(it, it, it, it, pred);
105 #endif
106   (void) std::fill_n(it, 0, 0);
107   (void) std::fill(it, it, 0);
108   (void) std::find_end(it, it, it, it);
109   (void) std::find_end(it, it, it, it, pred);
110   (void) std::find_first_of(it, it, it, it);
111   (void) std::find_first_of(it, it, it, it, pred);
112   (void) std::find_if_not(it, it, pred);
113   (void) std::find_if(it, it, pred);
114   (void) std::find(it, it, 0);
115 #if TEST_STD_VER > 14
116   (void) std::for_each_n(it, 0, pred);
117 #endif
118   (void) std::for_each(it, it, pred);
119   (void) std::generate_n(it, 0, pred);
120   (void) std::generate(it, it, pred);
121   (void) std::includes(it, it, it, it);
122   (void) std::includes(it, it, it, it, pred);
123   (void) std::inplace_merge(it, it, it);
124   (void) std::inplace_merge(it, it, it, pred);
125   (void) std::is_heap_until(it, it);
126   (void) std::is_heap_until(it, it, pred);
127   (void) std::is_heap(it, it);
128   (void) std::is_heap(it, it, pred);
129   (void) std::is_partitioned(it, it, pred);
130   (void) std::is_permutation(it, it, it);
131   (void) std::is_permutation(it, it, it, pred);
132 #if TEST_STD_VER > 11
133   (void) std::is_permutation(it, it, it, it);
134   (void) std::is_permutation(it, it, it, it, pred);
135 #endif
136   (void) std::is_sorted_until(it, it);
137   (void) std::is_sorted_until(it, it, pred);
138   (void) std::is_sorted(it, it);
139   (void) std::is_sorted(it, it, pred);
140   (void) std::lexicographical_compare(it, it, it, it);
141   (void) std::lexicographical_compare(it, it, it, it, pred);
142 #if TEST_STD_VER > 17
143   (void)std::lexicographical_compare_three_way(it, it, it, it);
144   (void)std::lexicographical_compare_three_way(it, it, it, it, std::compare_three_way());
145 #endif
146   (void) std::lower_bound(it, it, 0);
147   (void) std::lower_bound(it, it, 0, pred);
148   (void) std::make_heap(it, it);
149   (void) std::make_heap(it, it, pred);
150   (void) std::max_element(it, it);
151   (void) std::max_element(it, it, pred);
152   (void) std::merge(it, it, it, it, it);
153   (void) std::merge(it, it, it, it, it, pred);
154   (void) std::min_element(it, it);
155   (void) std::min_element(it, it, pred);
156   (void) std::minmax_element(it, it);
157   (void) std::minmax_element(it, it, pred);
158   (void) std::mismatch(it, it, it);
159   (void) std::mismatch(it, it, it, pred);
160   (void) std::move_backward(it, it, it);
161   (void) std::move(it, it, it);
162   (void) std::next_permutation(it, it);
163   (void) std::next_permutation(it, it, pred);
164   (void) std::none_of(it, it, pred);
165   (void) std::nth_element(it, it, it);
166   (void) std::nth_element(it, it, it, pred);
167   (void) std::partial_sort_copy(it, it, it, it);
168   (void) std::partial_sort_copy(it, it, it, it, pred);
169   (void) std::partial_sort(it, it, it);
170   (void) std::partial_sort(it, it, it, pred);
171   (void) std::partition_copy(it, it, it, it, pred);
172   (void) std::partition_point(it, it, pred);
173   (void) std::partition(it, it, pred);
174   (void) std::pop_heap(it, it);
175   (void) std::pop_heap(it, it, pred);
176   (void) std::prev_permutation(it, it);
177   (void) std::prev_permutation(it, it, pred);
178   (void) std::push_heap(it, it);
179   (void) std::push_heap(it, it, pred);
180   (void) std::remove_copy_if(it, it, it, pred);
181   (void) std::remove_copy(it, it, it, 0);
182   (void) std::remove_if(it, it, pred);
183   (void) std::remove(it, it, 0);
184   (void) std::replace_copy_if(it, it, it, pred, 0);
185   (void) std::replace_copy(it, it, it, 0, 0);
186   (void) std::replace_if(it, it, pred, 0);
187   (void) std::replace(it, it, 0, 0);
188   (void) std::reverse_copy(it, it, it);
189   (void) std::reverse(it, it);
190   (void) std::rotate_copy(it, it, it, it);
191   (void) std::rotate(it, it, it);
192 #if TEST_STD_VER > 14
193   (void) std::sample(it, it, it, 0, rng);
194 #endif
195   (void) std::search(it, it, it, it);
196   (void) std::search(it, it, it, it, pred);
197 #if TEST_STD_VER > 14
198   (void) std::search(it, it, std::default_searcher<Cpp20HostileIterator<int*>>(it, it));
199 #endif
200   (void) std::set_difference(it, it, it, it, it);
201   (void) std::set_difference(it, it, it, it, it, pred);
202   (void) std::set_intersection(it, it, it, it, it);
203   (void) std::set_intersection(it, it, it, it, it, pred);
204   (void) std::set_symmetric_difference(it, it, it, it, it);
205   (void) std::set_symmetric_difference(it, it, it, it, it, pred);
206   (void) std::set_union(it, it, it, it, it);
207   (void) std::set_union(it, it, it, it, it, pred);
208 #if TEST_STD_VER > 17
209   (void) std::shift_left(it, it, 0);
210   (void) std::shift_right(it, it, 0);
211 #endif
212   (void) std::shuffle(it, it, rng);
213   (void) std::sort_heap(it, it);
214   (void) std::sort_heap(it, it, pred);
215   (void) std::sort(it, it);
216   (void) std::sort(it, it, pred);
217   (void) std::stable_partition(it, it, pred);
218   (void) std::stable_sort(it, it);
219   (void) std::swap_ranges(it, it, it);
220   (void) std::transform(it, it, it, pred);
221   (void) std::transform(it, it, it, it, pred);
222   (void) std::unique_copy(it, it, it);
223   (void) std::unique(it, it);
224   (void) std::upper_bound(it, it, 0);
225 }
226