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 > 17
50 
51 // [iterator.concept.readable]
52 template<class _In>
53 concept __indirectly_readable_impl =
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   } &&
61   common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> &&
62   common_reference_with<iter_reference_t<_In>&&, iter_rvalue_reference_t<_In>&&> &&
63   common_reference_with<iter_rvalue_reference_t<_In>&&, const iter_value_t<_In>&>;
64 
65 template<class _In>
66 concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In>>;
67 
68 template<indirectly_readable _Tp>
69 using iter_common_reference_t = common_reference_t<iter_reference_t<_Tp>, iter_value_t<_Tp>&>;
70 
71 // [iterator.concept.writable]
72 template<class _Out, class _Tp>
73 concept indirectly_writable =
74   requires(_Out&& __o, _Tp&& __t) {
75     *__o = _VSTD::forward<_Tp>(__t);                        // not required to be equality-preserving
76     *_VSTD::forward<_Out>(__o) = _VSTD::forward<_Tp>(__t);  // not required to be equality-preserving
77     const_cast<const iter_reference_t<_Out>&&>(*__o) = _VSTD::forward<_Tp>(__t);                       // not required to be equality-preserving
78     const_cast<const iter_reference_t<_Out>&&>(*_VSTD::forward<_Out>(__o)) = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving
79   };
80 
81 // [iterator.concept.winc]
82 template<class _Tp>
83 concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>;
84 
85 template<class _Tp>
86 concept __signed_integer_like = signed_integral<_Tp>;
87 
88 template<class _Ip>
89 concept weakly_incrementable =
90   // TODO: remove this once the clang bug is fixed (bugs.llvm.org/PR48173).
91   !same_as<_Ip, bool> && // Currently, clang does not handle bool correctly.
92   movable<_Ip> &&
93   requires(_Ip __i) {
94     typename iter_difference_t<_Ip>;
95     requires __signed_integer_like<iter_difference_t<_Ip>>;
96     { ++__i } -> same_as<_Ip&>;   // not required to be equality-preserving
97     __i++;                        // not required to be equality-preserving
98   };
99 
100 // [iterator.concept.inc]
101 template<class _Ip>
102 concept incrementable =
103   regular<_Ip> &&
104   weakly_incrementable<_Ip> &&
105   requires(_Ip __i) {
106     { __i++ } -> same_as<_Ip>;
107   };
108 
109 // [iterator.concept.iterator]
110 template<class _Ip>
111 concept input_or_output_iterator =
112   requires(_Ip __i) {
113     { *__i } -> __can_reference;
114   } &&
115   weakly_incrementable<_Ip>;
116 
117 // [iterator.concept.sentinel]
118 template<class _Sp, class _Ip>
119 concept sentinel_for =
120   semiregular<_Sp> &&
121   input_or_output_iterator<_Ip> &&
122   __weakly_equality_comparable_with<_Sp, _Ip>;
123 
124 template<class, class>
125 inline constexpr bool disable_sized_sentinel_for = false;
126 
127 template<class _Sp, class _Ip>
128 concept sized_sentinel_for =
129   sentinel_for<_Sp, _Ip> &&
130   !disable_sized_sentinel_for<remove_cv_t<_Sp>, remove_cv_t<_Ip>> &&
131   requires(const _Ip& __i, const _Sp& __s) {
132     { __s - __i } -> same_as<iter_difference_t<_Ip>>;
133     { __i - __s } -> same_as<iter_difference_t<_Ip>>;
134   };
135 
136 // [iterator.concept.input]
137 template<class _Ip>
138 concept input_iterator =
139   input_or_output_iterator<_Ip> &&
140   indirectly_readable<_Ip> &&
141   requires { typename _ITER_CONCEPT<_Ip>; } &&
142   derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>;
143 
144 // [iterator.concept.output]
145 template<class _Ip, class _Tp>
146 concept output_iterator =
147   input_or_output_iterator<_Ip> &&
148   indirectly_writable<_Ip, _Tp> &&
149   requires (_Ip __it, _Tp&& __t) {
150     *__it++ = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving
151   };
152 
153 // [iterator.concept.forward]
154 template<class _Ip>
155 concept forward_iterator =
156   input_iterator<_Ip> &&
157   derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> &&
158   incrementable<_Ip> &&
159   sentinel_for<_Ip, _Ip>;
160 
161 // [iterator.concept.bidir]
162 template<class _Ip>
163 concept bidirectional_iterator =
164   forward_iterator<_Ip> &&
165   derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> &&
166   requires(_Ip __i) {
167     { --__i } -> same_as<_Ip&>;
168     { __i-- } -> same_as<_Ip>;
169   };
170 
171 template<class _Ip>
172 concept random_access_iterator =
173   bidirectional_iterator<_Ip> &&
174   derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> &&
175   totally_ordered<_Ip> &&
176   sized_sentinel_for<_Ip, _Ip> &&
177   requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {
178     { __i += __n } -> same_as<_Ip&>;
179     { __j +  __n } -> same_as<_Ip>;
180     { __n +  __j } -> same_as<_Ip>;
181     { __i -= __n } -> same_as<_Ip&>;
182     { __j -  __n } -> same_as<_Ip>;
183     {  __j[__n]  } -> same_as<iter_reference_t<_Ip>>;
184   };
185 
186 template<class _Ip>
187 concept contiguous_iterator =
188   random_access_iterator<_Ip> &&
189   derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> &&
190   is_lvalue_reference_v<iter_reference_t<_Ip>> &&
191   same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> &&
192   requires(const _Ip& __i) {
193     { _VSTD::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>;
194   };
195 
196 template<class _Ip>
197 concept __has_arrow = input_iterator<_Ip> && (is_pointer_v<_Ip> || requires(_Ip __i) { __i.operator->(); });
198 
199 // [indirectcallable.indirectinvocable]
200 template<class _Fp, class _It>
201 concept indirectly_unary_invocable =
202   indirectly_readable<_It> &&
203   copy_constructible<_Fp> &&
204   invocable<_Fp&, iter_value_t<_It>&> &&
205   invocable<_Fp&, iter_reference_t<_It>> &&
206   invocable<_Fp&, iter_common_reference_t<_It>> &&
207   common_reference_with<
208     invoke_result_t<_Fp&, iter_value_t<_It>&>,
209     invoke_result_t<_Fp&, iter_reference_t<_It>>>;
210 
211 template<class _Fp, class _It>
212 concept indirectly_regular_unary_invocable =
213   indirectly_readable<_It> &&
214   copy_constructible<_Fp> &&
215   regular_invocable<_Fp&, iter_value_t<_It>&> &&
216   regular_invocable<_Fp&, iter_reference_t<_It>> &&
217   regular_invocable<_Fp&, iter_common_reference_t<_It>> &&
218   common_reference_with<
219     invoke_result_t<_Fp&, iter_value_t<_It>&>,
220     invoke_result_t<_Fp&, iter_reference_t<_It>>>;
221 
222 template<class _Fp, class _It>
223 concept indirect_unary_predicate =
224   indirectly_readable<_It> &&
225   copy_constructible<_Fp> &&
226   predicate<_Fp&, iter_value_t<_It>&> &&
227   predicate<_Fp&, iter_reference_t<_It>> &&
228   predicate<_Fp&, iter_common_reference_t<_It>>;
229 
230 template<class _Fp, class _It1, class _It2>
231 concept indirect_binary_predicate =
232   indirectly_readable<_It1> && indirectly_readable<_It2> &&
233   copy_constructible<_Fp> &&
234   predicate<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> &&
235   predicate<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> &&
236   predicate<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> &&
237   predicate<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>> &&
238   predicate<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;
239 
240 template<class _Fp, class _It1, class _It2 = _It1>
241 concept indirect_equivalence_relation =
242   indirectly_readable<_It1> && indirectly_readable<_It2> &&
243   copy_constructible<_Fp> &&
244   equivalence_relation<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> &&
245   equivalence_relation<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> &&
246   equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> &&
247   equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>> &&
248   equivalence_relation<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;
249 
250 template<class _Fp, class _It1, class _It2 = _It1>
251 concept indirect_strict_weak_order =
252   indirectly_readable<_It1> && indirectly_readable<_It2> &&
253   copy_constructible<_Fp> &&
254   strict_weak_order<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> &&
255   strict_weak_order<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> &&
256   strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> &&
257   strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>> &&
258   strict_weak_order<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;
259 
260 template<class _Fp, class... _Its>
261   requires (indirectly_readable<_Its> && ...) && invocable<_Fp, iter_reference_t<_Its>...>
262 using indirect_result_t = invoke_result_t<_Fp, iter_reference_t<_Its>...>;
263 
264 template<class _In, class _Out>
265 concept indirectly_movable =
266   indirectly_readable<_In> &&
267   indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;
268 
269 template<class _In, class _Out>
270 concept indirectly_movable_storable =
271   indirectly_movable<_In, _Out> &&
272   indirectly_writable<_Out, iter_value_t<_In>> &&
273   movable<iter_value_t<_In>> &&
274   constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> &&
275   assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
276 
277 template<class _In, class _Out>
278 concept indirectly_copyable =
279   indirectly_readable<_In> &&
280   indirectly_writable<_Out, iter_reference_t<_In>>;
281 
282 template<class _In, class _Out>
283 concept indirectly_copyable_storable =
284   indirectly_copyable<_In, _Out> &&
285   indirectly_writable<_Out, iter_value_t<_In>&> &&
286   indirectly_writable<_Out, const iter_value_t<_In>&> &&
287   indirectly_writable<_Out, iter_value_t<_In>&&> &&
288   indirectly_writable<_Out, const iter_value_t<_In>&&> &&
289   copyable<iter_value_t<_In>> &&
290   constructible_from<iter_value_t<_In>, iter_reference_t<_In>> &&
291   assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
292 
293 // Note: indirectly_swappable is located in iter_swap.h to prevent a dependency cycle
294 // (both iter_swap and indirectly_swappable require indirectly_readable).
295 
296 #endif // _LIBCPP_STD_VER > 17
297 
298 _LIBCPP_END_NAMESPACE_STD
299 
300 #endif // _LIBCPP___ITERATOR_CONCEPTS_H
301