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