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 <concepts>
20
21#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
22#pragma GCC system_header
23#endif
24
25_LIBCPP_PUSH_MACROS
26#include <__undef_macros>
27
28_LIBCPP_BEGIN_NAMESPACE_STD
29
30#if !defined(_LIBCPP_HAS_NO_RANGES)
31
32// clang-format off
33
34// [iterator.concept.readable]
35template<class _In>
36concept __indirectly_readable_impl =
37  requires(const _In __i) {
38    typename iter_value_t<_In>;
39    typename iter_reference_t<_In>;
40    typename iter_rvalue_reference_t<_In>;
41    { *__i } -> same_as<iter_reference_t<_In> >;
42    { ranges::iter_move(__i) } -> same_as<iter_rvalue_reference_t<_In> >;
43  } &&
44  common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> &&
45  common_reference_with<iter_reference_t<_In>&&, iter_rvalue_reference_t<_In>&&> &&
46  common_reference_with<iter_rvalue_reference_t<_In>&&, const iter_value_t<_In>&>;
47
48template<class _In>
49concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In> >;
50
51// [iterator.concept.writable]
52template<class _Out, class _Tp>
53concept 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]
62template<class _Tp>
63concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>;
64
65template<class _Tp>
66concept __signed_integer_like = signed_integral<_Tp>;
67
68template<class _Ip>
69concept weakly_incrementable =
70  default_initializable<_Ip> &&
71  movable<_Ip> &&
72  requires(_Ip __i) {
73    typename iter_difference_t<_Ip>;
74    requires __signed_integer_like<iter_difference_t<_Ip> >;
75    { ++__i } -> same_as<_Ip&>;   // not required to be equality-preserving
76    __i++;                        // not required to be equality-preserving
77  };
78
79// [iterator.concept.inc]
80template<class _Ip>
81concept incrementable =
82  regular<_Ip> &&
83  weakly_incrementable<_Ip> &&
84  requires(_Ip __i) {
85    { __i++ } -> same_as<_Ip>;
86  };
87
88// [iterator.concept.iterator]
89template<class _Ip>
90concept input_or_output_iterator =
91  requires(_Ip __i) {
92    { *__i } -> __referenceable;
93  } &&
94  weakly_incrementable<_Ip>;
95
96// [iterator.concept.sentinel]
97template<class _Sp, class _Ip>
98concept sentinel_for =
99  semiregular<_Sp> &&
100  input_or_output_iterator<_Ip> &&
101  __weakly_equality_comparable_with<_Sp, _Ip>;
102
103template<class, class>
104inline constexpr bool disable_sized_sentinel_for = false;
105
106template<class _Sp, class _Ip>
107concept sized_sentinel_for =
108  sentinel_for<_Sp, _Ip> &&
109  !disable_sized_sentinel_for<remove_cv_t<_Sp>, remove_cv_t<_Ip> > &&
110  requires(const _Ip& __i, const _Sp& __s) {
111    { __s - __i } -> same_as<iter_difference_t<_Ip> >;
112    { __i - __s } -> same_as<iter_difference_t<_Ip> >;
113  };
114
115// [iterator.concept.input]
116template<class _Ip>
117concept input_iterator =
118  input_or_output_iterator<_Ip> &&
119  indirectly_readable<_Ip> &&
120  requires { typename _ITER_CONCEPT<_Ip>; } &&
121  derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>;
122
123// [iterator.concept.forward]
124template<class _Ip>
125concept forward_iterator =
126  input_iterator<_Ip> &&
127  derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> &&
128  incrementable<_Ip> &&
129  sentinel_for<_Ip, _Ip>;
130
131// [iterator.concept.bidir]
132template<class _Ip>
133concept bidirectional_iterator =
134  forward_iterator<_Ip> &&
135  derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> &&
136  requires(_Ip __i) {
137    { --__i } -> same_as<_Ip&>;
138    { __i-- } -> same_as<_Ip>;
139  };
140
141template<class _Ip>
142concept random_access_iterator =
143  bidirectional_iterator<_Ip> &&
144  derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> &&
145  totally_ordered<_Ip> &&
146  sized_sentinel_for<_Ip, _Ip> &&
147  requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {
148    { __i += __n } -> same_as<_Ip&>;
149    { __j +  __n } -> same_as<_Ip>;
150    { __n +  __j } -> same_as<_Ip>;
151    { __i -= __n } -> same_as<_Ip&>;
152    { __j -  __n } -> same_as<_Ip>;
153    {  __j[__n]  } -> same_as<iter_reference_t<_Ip>>;
154  };
155
156template<class _Ip>
157concept contiguous_iterator =
158  random_access_iterator<_Ip> &&
159  derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> &&
160  is_lvalue_reference_v<iter_reference_t<_Ip>> &&
161  same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> &&
162  (is_pointer_v<_Ip> || requires { sizeof(__pointer_traits_element_type<_Ip>); }) &&
163  requires(const _Ip& __i) {
164    { _VSTD::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>;
165  };
166
167// clang-format on
168
169#endif // !defined(_LIBCPP_HAS_NO_RANGES)
170
171_LIBCPP_END_NAMESPACE_STD
172
173_LIBCPP_POP_MACROS
174
175#endif // _LIBCPP___ITERATOR_CONCEPTS_H
176