1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _LIBCPP___ITERATOR_CONCEPTS_H
11 #define _LIBCPP___ITERATOR_CONCEPTS_H
12
13 #include <__concepts/arithmetic.h>
14 #include <__concepts/assignable.h>
15 #include <__concepts/common_reference_with.h>
16 #include <__concepts/constructible.h>
17 #include <__concepts/copyable.h>
18 #include <__concepts/derived_from.h>
19 #include <__concepts/equality_comparable.h>
20 #include <__concepts/invocable.h>
21 #include <__concepts/movable.h>
22 #include <__concepts/predicate.h>
23 #include <__concepts/regular.h>
24 #include <__concepts/relation.h>
25 #include <__concepts/same_as.h>
26 #include <__concepts/semiregular.h>
27 #include <__concepts/totally_ordered.h>
28 #include <__config>
29 #include <__functional/invoke.h>
30 #include <__iterator/incrementable_traits.h>
31 #include <__iterator/iter_move.h>
32 #include <__iterator/iterator_traits.h>
33 #include <__iterator/readable_traits.h>
34 #include <__memory/pointer_traits.h>
35 #include <__type_traits/add_pointer.h>
36 #include <__type_traits/common_reference.h>
37 #include <__type_traits/is_pointer.h>
38 #include <__type_traits/is_reference.h>
39 #include <__type_traits/remove_cv.h>
40 #include <__type_traits/remove_cvref.h>
41 #include <__utility/forward.h>
42
43 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
44 # pragma GCC system_header
45 #endif
46
47 _LIBCPP_BEGIN_NAMESPACE_STD
48
49 #if _LIBCPP_STD_VER >= 20
50
51 // [iterator.concept.readable]
52 template <class _In>
53 concept __indirectly_readable_impl =
requires(const _In __i)54 requires(const _In __i) {
55 typename iter_value_t<_In>;
56 typename iter_reference_t<_In>;
57 typename iter_rvalue_reference_t<_In>;
58 { *__i } -> same_as<iter_reference_t<_In>>;
59 { ranges::iter_move(__i) } -> same_as<iter_rvalue_reference_t<_In>>;
60 } && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> &&
61 common_reference_with<iter_reference_t<_In>&&, iter_rvalue_reference_t<_In>&&> &&
62 common_reference_with<iter_rvalue_reference_t<_In>&&, const iter_value_t<_In>&>;
63
64 template <class _In>
65 concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In>>;
66
67 template <indirectly_readable _Tp>
68 using iter_common_reference_t = common_reference_t<iter_reference_t<_Tp>, iter_value_t<_Tp>&>;
69
70 // [iterator.concept.writable]
71 template <class _Out, class _Tp>
requires(_Out && __o,_Tp && __t)72 concept indirectly_writable = requires(_Out&& __o, _Tp&& __t) {
73 *__o = std::forward<_Tp>(__t); // not required to be equality-preserving
74 *std::forward<_Out>(__o) = std::forward<_Tp>(__t); // not required to be equality-preserving
75 const_cast<const iter_reference_t<_Out>&&>(*__o) = std::forward<_Tp>(__t); // not required to be equality-preserving
76 const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o)) =
77 std::forward<_Tp>(__t); // not required to be equality-preserving
78 };
79
80 // [iterator.concept.winc]
81 template <class _Tp>
82 concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>;
83
84 template <class _Tp>
85 concept __signed_integer_like = signed_integral<_Tp>;
86
87 template <class _Ip>
88 concept weakly_incrementable =
89 // TODO: remove this once the clang bug is fixed (bugs.llvm.org/PR48173).
90 !same_as<_Ip, bool> && // Currently, clang does not handle bool correctly.
91 movable<_Ip> && requires(_Ip __i) {
92 typename iter_difference_t<_Ip>;
93 requires __signed_integer_like<iter_difference_t<_Ip>>;
94 { ++__i } -> same_as<_Ip&>; // not required to be equality-preserving
95 __i++; // not required to be equality-preserving
96 };
97
98 // [iterator.concept.inc]
99 template <class _Ip>
requires(_Ip __i)100 concept incrementable = regular<_Ip> && weakly_incrementable<_Ip> && requires(_Ip __i) {
101 { __i++ } -> same_as<_Ip>;
102 };
103
104 // [iterator.concept.iterator]
105 template <class _Ip>
requires(_Ip __i)106 concept input_or_output_iterator = requires(_Ip __i) {
107 { *__i } -> __can_reference;
108 } && weakly_incrementable<_Ip>;
109
110 // [iterator.concept.sentinel]
111 template <class _Sp, class _Ip>
112 concept sentinel_for = semiregular<_Sp> && input_or_output_iterator<_Ip> && __weakly_equality_comparable_with<_Sp, _Ip>;
113
114 template <class, class>
115 inline constexpr bool disable_sized_sentinel_for = false;
116
117 template <class _Sp, class _Ip>
118 concept sized_sentinel_for =
119 sentinel_for<_Sp, _Ip> && !disable_sized_sentinel_for<remove_cv_t<_Sp>, remove_cv_t<_Ip>> &&
120 requires(const _Ip& __i, const _Sp& __s) {
121 { __s - __i } -> same_as<iter_difference_t<_Ip>>;
122 { __i - __s } -> same_as<iter_difference_t<_Ip>>;
123 };
124
125 // [iterator.concept.input]
126 template <class _Ip>
127 concept input_iterator = input_or_output_iterator<_Ip> && indirectly_readable<_Ip> && requires {
128 typename _ITER_CONCEPT<_Ip>;
129 } && derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>;
130
131 // [iterator.concept.output]
132 template <class _Ip, class _Tp>
133 concept output_iterator =
requires(_Ip __it,_Tp && __t)134 input_or_output_iterator<_Ip> && indirectly_writable<_Ip, _Tp> && requires(_Ip __it, _Tp&& __t) {
135 *__it++ = std::forward<_Tp>(__t); // not required to be equality-preserving
136 };
137
138 // [iterator.concept.forward]
139 template <class _Ip>
140 concept forward_iterator =
141 input_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> && incrementable<_Ip> &&
142 sentinel_for<_Ip, _Ip>;
143
144 // [iterator.concept.bidir]
145 template <class _Ip>
146 concept bidirectional_iterator =
requires(_Ip __i)147 forward_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> && requires(_Ip __i) {
148 { --__i } -> same_as<_Ip&>;
149 { __i-- } -> same_as<_Ip>;
150 };
151
152 template <class _Ip>
153 concept random_access_iterator =
154 bidirectional_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> &&
155 totally_ordered<_Ip> && sized_sentinel_for<_Ip, _Ip> &&
requires(_Ip __i,const _Ip __j,const iter_difference_t<_Ip> __n)156 requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {
157 { __i += __n } -> same_as<_Ip&>;
158 { __j + __n } -> same_as<_Ip>;
159 { __n + __j } -> same_as<_Ip>;
160 { __i -= __n } -> same_as<_Ip&>;
161 { __j - __n } -> same_as<_Ip>;
162 { __j[__n] } -> same_as<iter_reference_t<_Ip>>;
163 };
164
165 template <class _Ip>
166 concept contiguous_iterator =
167 random_access_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> &&
168 is_lvalue_reference_v<iter_reference_t<_Ip>> && same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> &&
requires(const _Ip & __i)169 requires(const _Ip& __i) {
170 { std::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>;
171 };
172
173 template <class _Ip>
174 concept __has_arrow = input_iterator<_Ip> && (is_pointer_v<_Ip> || requires(_Ip __i) { __i.operator->(); });
175
176 // [indirectcallable.indirectinvocable]
177 template <class _Fp, class _It>
178 concept indirectly_unary_invocable =
179 indirectly_readable<_It> && copy_constructible<_Fp> && invocable<_Fp&, iter_value_t<_It>&> &&
180 invocable<_Fp&, iter_reference_t<_It>> &&
181 common_reference_with< invoke_result_t<_Fp&, iter_value_t<_It>&>, invoke_result_t<_Fp&, iter_reference_t<_It>>>;
182
183 template <class _Fp, class _It>
184 concept indirectly_regular_unary_invocable =
185 indirectly_readable<_It> && copy_constructible<_Fp> && regular_invocable<_Fp&, iter_value_t<_It>&> &&
186 regular_invocable<_Fp&, iter_reference_t<_It>> &&
187 common_reference_with< invoke_result_t<_Fp&, iter_value_t<_It>&>, invoke_result_t<_Fp&, iter_reference_t<_It>>>;
188
189 template <class _Fp, class _It>
190 concept indirect_unary_predicate =
191 indirectly_readable<_It> && copy_constructible<_Fp> && predicate<_Fp&, iter_value_t<_It>&> &&
192 predicate<_Fp&, iter_reference_t<_It>>;
193
194 template <class _Fp, class _It1, class _It2>
195 concept indirect_binary_predicate =
196 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
197 predicate<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> &&
198 predicate<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> &&
199 predicate<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> &&
200 predicate<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
201
202 template <class _Fp, class _It1, class _It2 = _It1>
203 concept indirect_equivalence_relation =
204 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
205 equivalence_relation<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> &&
206 equivalence_relation<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> &&
207 equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> &&
208 equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
209
210 template <class _Fp, class _It1, class _It2 = _It1>
211 concept indirect_strict_weak_order =
212 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
213 strict_weak_order<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> &&
214 strict_weak_order<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> &&
215 strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> &&
216 strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
217
218 template <class _Fp, class... _Its>
219 requires(indirectly_readable<_Its> && ...) && invocable<_Fp, iter_reference_t<_Its>...>
220 using indirect_result_t = invoke_result_t<_Fp, iter_reference_t<_Its>...>;
221
222 template <class _In, class _Out>
223 concept indirectly_movable = indirectly_readable<_In> && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;
224
225 template <class _In, class _Out>
226 concept indirectly_movable_storable =
227 indirectly_movable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>> &&
228 constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> &&
229 assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
230
231 template <class _In, class _Out>
232 concept indirectly_copyable = indirectly_readable<_In> && indirectly_writable<_Out, iter_reference_t<_In>>;
233
234 template <class _In, class _Out>
235 concept indirectly_copyable_storable =
236 indirectly_copyable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>&> &&
237 indirectly_writable<_Out, const iter_value_t<_In>&> && indirectly_writable<_Out, iter_value_t<_In>&&> &&
238 indirectly_writable<_Out, const iter_value_t<_In>&&> && copyable<iter_value_t<_In>> &&
239 constructible_from<iter_value_t<_In>, iter_reference_t<_In>> &&
240 assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
241
242 // Note: indirectly_swappable is located in iter_swap.h to prevent a dependency cycle
243 // (both iter_swap and indirectly_swappable require indirectly_readable).
244
245 #endif // _LIBCPP_STD_VER >= 20
246
247 template <class _Tp>
248 using __has_random_access_iterator_category_or_concept
249 #if _LIBCPP_STD_VER >= 20
250 = integral_constant<bool, random_access_iterator<_Tp>>;
251 #else // _LIBCPP_STD_VER < 20
252 = __has_random_access_iterator_category<_Tp>;
253 #endif // _LIBCPP_STD_VER
254
255 _LIBCPP_END_NAMESPACE_STD
256
257 #endif // _LIBCPP___ITERATOR_CONCEPTS_H
258