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/primary_template.h>
24#include <__concepts/referenceable.h>
25#include <__concepts/regular.h>
26#include <__concepts/relation.h>
27#include <__concepts/same_as.h>
28#include <__concepts/semiregular.h>
29#include <__concepts/totally_ordered.h>
30#include <__config>
31#include <__iterator/incrementable_traits.h>
32#include <__iterator/iter_move.h>
33#include <__iterator/iterator_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/conditional.h>
38#include <__type_traits/disjunction.h>
39#include <__type_traits/enable_if.h>
40#include <__type_traits/integral_constant.h>
41#include <__type_traits/invoke.h>
42#include <__type_traits/is_pointer.h>
43#include <__type_traits/is_reference.h>
44#include <__type_traits/remove_cv.h>
45#include <__type_traits/remove_cvref.h>
46#include <__utility/forward.h>
47
48#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
49# pragma GCC system_header
50#endif
51
52_LIBCPP_BEGIN_NAMESPACE_STD
53
54#if _LIBCPP_STD_VER >= 20
55
56// [iterator.concept.readable]
57template <class _In>
58concept __indirectly_readable_impl =
59 requires(const _In __i) {
60 typename iter_value_t<_In>;
61 typename iter_reference_t<_In>;
62 typename iter_rvalue_reference_t<_In>;
63 { *__i } -> same_as<iter_reference_t<_In>>;
64 { ranges::iter_move(__i) } -> same_as<iter_rvalue_reference_t<_In>>;
65 } && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> &&
66 common_reference_with<iter_reference_t<_In>&&, iter_rvalue_reference_t<_In>&&> &&
67 common_reference_with<iter_rvalue_reference_t<_In>&&, const iter_value_t<_In>&>;
68
69template <class _In>
70concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In>>;
71
72template <class _Tp>
73using __projected_iterator_t _LIBCPP_NODEBUG = typename _Tp::__projected_iterator;
74
75template <class _Tp>
76using __projected_projection_t _LIBCPP_NODEBUG = typename _Tp::__projected_projection;
77
78template <class _Tp>
79concept __specialization_of_projected = requires {
80 typename __projected_iterator_t<_Tp>;
81 typename __projected_projection_t<_Tp>;
82} && __primary_template<_Tp>;
83
84template <class _Tp>
85struct __indirect_value_t_impl {
86 using type _LIBCPP_NODEBUG = iter_value_t<_Tp>&;
87};
88template <__specialization_of_projected _Tp>
89struct __indirect_value_t_impl<_Tp> {
90 using type _LIBCPP_NODEBUG =
91 invoke_result_t<__projected_projection_t<_Tp>&,
92 typename __indirect_value_t_impl<__projected_iterator_t<_Tp>>::type>;
93};
94
95template <indirectly_readable _Tp>
96using __indirect_value_t _LIBCPP_NODEBUG = typename __indirect_value_t_impl<_Tp>::type;
97
98template <indirectly_readable _Tp>
99using iter_common_reference_t = common_reference_t<iter_reference_t<_Tp>, __indirect_value_t<_Tp>>;
100
101// [iterator.concept.writable]
102template <class _Out, class _Tp>
103concept indirectly_writable = requires(_Out&& __o, _Tp&& __t) {
104 *__o = std::forward<_Tp>(__t); // not required to be equality-preserving
105 *std::forward<_Out>(__o) = std::forward<_Tp>(__t); // not required to be equality-preserving
106 const_cast<const iter_reference_t<_Out>&&>(*__o) = std::forward<_Tp>(__t); // not required to be equality-preserving
107 const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o)) =
108 std::forward<_Tp>(__t); // not required to be equality-preserving
109};
110
111// [iterator.concept.winc]
112template <class _Tp>
113concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>;
114
115template <class _Tp>
116concept __signed_integer_like = signed_integral<_Tp>;
117
118template <class _Ip>
119concept weakly_incrementable = movable<_Ip> && requires(_Ip __i) {
120 typename iter_difference_t<_Ip>;
121 requires __signed_integer_like<iter_difference_t<_Ip>>;
122 { ++__i } -> same_as<_Ip&>; // not required to be equality-preserving
123 __i++; // not required to be equality-preserving
124};
125
126// [iterator.concept.inc]
127template <class _Ip>
128concept incrementable = regular<_Ip> && weakly_incrementable<_Ip> && requires(_Ip __i) {
129 { __i++ } -> same_as<_Ip>;
130};
131
132// [iterator.concept.iterator]
133template <class _Ip>
134concept input_or_output_iterator = requires(_Ip __i) {
135 { *__i } -> __referenceable;
136} && weakly_incrementable<_Ip>;
137
138// [iterator.concept.sentinel]
139template <class _Sp, class _Ip>
140concept sentinel_for = semiregular<_Sp> && input_or_output_iterator<_Ip> && __weakly_equality_comparable_with<_Sp, _Ip>;
141
142template <class, class>
143inline constexpr bool disable_sized_sentinel_for = false;
144
145template <class _Sp, class _Ip>
146concept sized_sentinel_for =
147 sentinel_for<_Sp, _Ip> && !disable_sized_sentinel_for<remove_cv_t<_Sp>, remove_cv_t<_Ip>> &&
148 requires(const _Ip& __i, const _Sp& __s) {
149 { __s - __i } -> same_as<iter_difference_t<_Ip>>;
150 { __i - __s } -> same_as<iter_difference_t<_Ip>>;
151 };
152
153template <class _Iter>
154struct __iter_traits_cache {
155 using type _LIBCPP_NODEBUG = _If<__primary_template<iterator_traits<_Iter> >, _Iter, iterator_traits<_Iter> >;
156};
157template <class _Iter>
158using _ITER_TRAITS _LIBCPP_NODEBUG = typename __iter_traits_cache<_Iter>::type;
159
160struct __iter_concept_concept_test {
161 template <class _Iter>
162 using _Apply _LIBCPP_NODEBUG = typename _ITER_TRAITS<_Iter>::iterator_concept;
163};
164struct __iter_concept_category_test {
165 template <class _Iter>
166 using _Apply _LIBCPP_NODEBUG = typename _ITER_TRAITS<_Iter>::iterator_category;
167};
168struct __iter_concept_random_fallback {
169 template <class _Iter>
170 using _Apply _LIBCPP_NODEBUG = __enable_if_t<__primary_template<iterator_traits<_Iter> >, random_access_iterator_tag>;
171};
172
173template <class _Iter, class _Tester>
174 struct __test_iter_concept : bool_constant < requires {
175 typename _Tester::template _Apply<_Iter>;
176} >, _Tester{};
177
178template <class _Iter>
179struct __iter_concept_cache {
180 using type _LIBCPP_NODEBUG =
181 _Or<__test_iter_concept<_Iter, __iter_concept_concept_test>,
182 __test_iter_concept<_Iter, __iter_concept_category_test>,
183 __test_iter_concept<_Iter, __iter_concept_random_fallback> >;
184};
185
186template <class _Iter>
187using _ITER_CONCEPT _LIBCPP_NODEBUG = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>;
188
189// [iterator.concept.input]
190template <class _Ip>
191concept input_iterator = input_or_output_iterator<_Ip> && indirectly_readable<_Ip> && requires {
192 typename _ITER_CONCEPT<_Ip>;
193} && derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>;
194
195// [iterator.concept.output]
196template <class _Ip, class _Tp>
197concept output_iterator =
198 input_or_output_iterator<_Ip> && indirectly_writable<_Ip, _Tp> && requires(_Ip __it, _Tp&& __t) {
199 *__it++ = std::forward<_Tp>(__t); // not required to be equality-preserving
200 };
201
202// [iterator.concept.forward]
203template <class _Ip>
204concept forward_iterator =
205 input_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> && incrementable<_Ip> &&
206 sentinel_for<_Ip, _Ip>;
207
208// [iterator.concept.bidir]
209template <class _Ip>
210concept bidirectional_iterator =
211 forward_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> && requires(_Ip __i) {
212 { --__i } -> same_as<_Ip&>;
213 { __i-- } -> same_as<_Ip>;
214 };
215
216template <class _Ip>
217concept random_access_iterator =
218 bidirectional_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> &&
219 totally_ordered<_Ip> && sized_sentinel_for<_Ip, _Ip> &&
220 requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {
221 { __i += __n } -> same_as<_Ip&>;
222 { __j + __n } -> same_as<_Ip>;
223 { __n + __j } -> same_as<_Ip>;
224 { __i -= __n } -> same_as<_Ip&>;
225 { __j - __n } -> same_as<_Ip>;
226 { __j[__n] } -> same_as<iter_reference_t<_Ip>>;
227 };
228
229template <class _Ip>
230concept contiguous_iterator =
231 random_access_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> &&
232 is_lvalue_reference_v<iter_reference_t<_Ip>> && same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> &&
233 requires(const _Ip& __i) {
234 { std::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>;
235 };
236
237template <class _Ip>
238concept __has_arrow = input_iterator<_Ip> && (is_pointer_v<_Ip> || requires(_Ip __i) { __i.operator->(); });
239
240// [indirectcallable.indirectinvocable]
241template <class _Fp, class _It>
242concept indirectly_unary_invocable =
243 indirectly_readable<_It> && copy_constructible<_Fp> && invocable<_Fp&, __indirect_value_t<_It>> &&
244 invocable<_Fp&, iter_reference_t<_It>> &&
245 common_reference_with< invoke_result_t<_Fp&, __indirect_value_t<_It>>,
246 invoke_result_t<_Fp&, iter_reference_t<_It>>>;
247
248template <class _Fp, class _It>
249concept indirectly_regular_unary_invocable =
250 indirectly_readable<_It> && copy_constructible<_Fp> && regular_invocable<_Fp&, __indirect_value_t<_It>> &&
251 regular_invocable<_Fp&, iter_reference_t<_It>> &&
252 common_reference_with< invoke_result_t<_Fp&, __indirect_value_t<_It>>,
253 invoke_result_t<_Fp&, iter_reference_t<_It>>>;
254
255template <class _Fp, class _It>
256concept indirect_unary_predicate =
257 indirectly_readable<_It> && copy_constructible<_Fp> && predicate<_Fp&, __indirect_value_t<_It>> &&
258 predicate<_Fp&, iter_reference_t<_It>>;
259
260template <class _Fp, class _It1, class _It2>
261concept indirect_binary_predicate =
262 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
263 predicate<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&
264 predicate<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&
265 predicate<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&
266 predicate<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
267
268template <class _Fp, class _It1, class _It2 = _It1>
269concept indirect_equivalence_relation =
270 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
271 equivalence_relation<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&
272 equivalence_relation<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&
273 equivalence_relation<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&
274 equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
275
276template <class _Fp, class _It1, class _It2 = _It1>
277concept indirect_strict_weak_order =
278 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
279 strict_weak_order<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&
280 strict_weak_order<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&
281 strict_weak_order<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&
282 strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
283
284template <class _Fp, class... _Its>
285 requires(indirectly_readable<_Its> && ...) && invocable<_Fp, iter_reference_t<_Its>...>
286using indirect_result_t = invoke_result_t<_Fp, iter_reference_t<_Its>...>;
287
288template <class _In, class _Out>
289concept indirectly_movable = indirectly_readable<_In> && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;
290
291template <class _In, class _Out>
292concept indirectly_movable_storable =
293 indirectly_movable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>> &&
294 constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> &&
295 assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
296
297template <class _In, class _Out>
298concept indirectly_copyable = indirectly_readable<_In> && indirectly_writable<_Out, iter_reference_t<_In>>;
299
300template <class _In, class _Out>
301concept indirectly_copyable_storable =
302 indirectly_copyable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>&> &&
303 indirectly_writable<_Out, const iter_value_t<_In>&> && indirectly_writable<_Out, iter_value_t<_In>&&> &&
304 indirectly_writable<_Out, const iter_value_t<_In>&&> && copyable<iter_value_t<_In>> &&
305 constructible_from<iter_value_t<_In>, iter_reference_t<_In>> &&
306 assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
307
308// Note: indirectly_swappable is located in iter_swap.h to prevent a dependency cycle
309// (both iter_swap and indirectly_swappable require indirectly_readable).
310
311#endif // _LIBCPP_STD_VER >= 20
312
313template <class _Tp>
314using __has_random_access_iterator_category_or_concept _LIBCPP_NODEBUG
315#if _LIBCPP_STD_VER >= 20
316 = integral_constant<bool, random_access_iterator<_Tp>>;
317#else // _LIBCPP_STD_VER < 20
318 = __has_random_access_iterator_category<_Tp>;
319#endif // _LIBCPP_STD_VER
320
321_LIBCPP_END_NAMESPACE_STD
322
323#endif // _LIBCPP___ITERATOR_CONCEPTS_H
324