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]
52template <class _In>
53concept __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    } && 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
64template <class _In>
65concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In>>;
66
67template <indirectly_readable _Tp>
68using iter_common_reference_t = common_reference_t<iter_reference_t<_Tp>, iter_value_t<_Tp>&>;
69
70// [iterator.concept.writable]
71template <class _Out, class _Tp>
72concept 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]
81template <class _Tp>
82concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>;
83
84template <class _Tp>
85concept __signed_integer_like = signed_integral<_Tp>;
86
87template <class _Ip>
88concept 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]
99template <class _Ip>
100concept incrementable = regular<_Ip> && weakly_incrementable<_Ip> && requires(_Ip __i) {
101  { __i++ } -> same_as<_Ip>;
102};
103
104// [iterator.concept.iterator]
105template <class _Ip>
106concept input_or_output_iterator = requires(_Ip __i) {
107  { *__i } -> __can_reference;
108} && weakly_incrementable<_Ip>;
109
110// [iterator.concept.sentinel]
111template <class _Sp, class _Ip>
112concept sentinel_for = semiregular<_Sp> && input_or_output_iterator<_Ip> && __weakly_equality_comparable_with<_Sp, _Ip>;
113
114template <class, class>
115inline constexpr bool disable_sized_sentinel_for = false;
116
117template <class _Sp, class _Ip>
118concept 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]
126template <class _Ip>
127concept 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]
132template <class _Ip, class _Tp>
133concept output_iterator =
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]
139template <class _Ip>
140concept 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]
145template <class _Ip>
146concept bidirectional_iterator =
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
152template <class _Ip>
153concept 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> &&
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
165template <class _Ip>
166concept 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>>> &&
169    requires(const _Ip& __i) {
170      { std::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>;
171    };
172
173template <class _Ip>
174concept __has_arrow = input_iterator<_Ip> && (is_pointer_v<_Ip> || requires(_Ip __i) { __i.operator->(); });
175
176// [indirectcallable.indirectinvocable]
177template <class _Fp, class _It>
178concept indirectly_unary_invocable =
179    indirectly_readable<_It> && copy_constructible<_Fp> && invocable<_Fp&, iter_value_t<_It>&> &&
180    invocable<_Fp&, iter_reference_t<_It>> && invocable<_Fp&, iter_common_reference_t<_It>> &&
181    common_reference_with< invoke_result_t<_Fp&, iter_value_t<_It>&>, invoke_result_t<_Fp&, iter_reference_t<_It>>>;
182
183template <class _Fp, class _It>
184concept 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>> && regular_invocable<_Fp&, iter_common_reference_t<_It>> &&
187    common_reference_with< invoke_result_t<_Fp&, iter_value_t<_It>&>, invoke_result_t<_Fp&, iter_reference_t<_It>>>;
188
189template <class _Fp, class _It>
190concept indirect_unary_predicate =
191    indirectly_readable<_It> && copy_constructible<_Fp> && predicate<_Fp&, iter_value_t<_It>&> &&
192    predicate<_Fp&, iter_reference_t<_It>> && predicate<_Fp&, iter_common_reference_t<_It>>;
193
194template <class _Fp, class _It1, class _It2>
195concept 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    predicate<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;
202
203template <class _Fp, class _It1, class _It2 = _It1>
204concept indirect_equivalence_relation =
205    indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
206    equivalence_relation<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> &&
207    equivalence_relation<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> &&
208    equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> &&
209    equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>> &&
210    equivalence_relation<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;
211
212template <class _Fp, class _It1, class _It2 = _It1>
213concept indirect_strict_weak_order =
214    indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
215    strict_weak_order<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> &&
216    strict_weak_order<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> &&
217    strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> &&
218    strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>> &&
219    strict_weak_order<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>;
220
221template <class _Fp, class... _Its>
222  requires(indirectly_readable<_Its> && ...) && invocable<_Fp, iter_reference_t<_Its>...>
223using indirect_result_t = invoke_result_t<_Fp, iter_reference_t<_Its>...>;
224
225template <class _In, class _Out>
226concept indirectly_movable = indirectly_readable<_In> && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;
227
228template <class _In, class _Out>
229concept indirectly_movable_storable =
230    indirectly_movable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>> &&
231    constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> &&
232    assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
233
234template <class _In, class _Out>
235concept indirectly_copyable = indirectly_readable<_In> && indirectly_writable<_Out, iter_reference_t<_In>>;
236
237template <class _In, class _Out>
238concept indirectly_copyable_storable =
239    indirectly_copyable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>&> &&
240    indirectly_writable<_Out, const iter_value_t<_In>&> && indirectly_writable<_Out, iter_value_t<_In>&&> &&
241    indirectly_writable<_Out, const iter_value_t<_In>&&> && copyable<iter_value_t<_In>> &&
242    constructible_from<iter_value_t<_In>, iter_reference_t<_In>> &&
243    assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
244
245// Note: indirectly_swappable is located in iter_swap.h to prevent a dependency cycle
246// (both iter_swap and indirectly_swappable require indirectly_readable).
247
248#endif // _LIBCPP_STD_VER >= 20
249
250template <class _Tp>
251using __has_random_access_iterator_category_or_concept
252#if _LIBCPP_STD_VER >= 20
253    = integral_constant<bool, random_access_iterator<_Tp>>;
254#else  // _LIBCPP_STD_VER < 20
255    = __has_random_access_iterator_category<_Tp>;
256#endif // _LIBCPP_STD_VER
257
258_LIBCPP_END_NAMESPACE_STD
259
260#endif // _LIBCPP___ITERATOR_CONCEPTS_H
261