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