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 > 17 50 51 // [iterator.concept.readable] 52 template<class _In> 53 concept __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 } && 61 common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> && 62 common_reference_with<iter_reference_t<_In>&&, iter_rvalue_reference_t<_In>&&> && 63 common_reference_with<iter_rvalue_reference_t<_In>&&, const iter_value_t<_In>&>; 64 65 template<class _In> 66 concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In>>; 67 68 template<indirectly_readable _Tp> 69 using iter_common_reference_t = common_reference_t<iter_reference_t<_Tp>, iter_value_t<_Tp>&>; 70 71 // [iterator.concept.writable] 72 template<class _Out, class _Tp> 73 concept indirectly_writable = 74 requires(_Out&& __o, _Tp&& __t) { 75 *__o = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 76 *_VSTD::forward<_Out>(__o) = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 77 const_cast<const iter_reference_t<_Out>&&>(*__o) = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 78 const_cast<const iter_reference_t<_Out>&&>(*_VSTD::forward<_Out>(__o)) = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 79 }; 80 81 // [iterator.concept.winc] 82 template<class _Tp> 83 concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>; 84 85 template<class _Tp> 86 concept __signed_integer_like = signed_integral<_Tp>; 87 88 template<class _Ip> 89 concept weakly_incrementable = 90 // TODO: remove this once the clang bug is fixed (bugs.llvm.org/PR48173). 91 !same_as<_Ip, bool> && // Currently, clang does not handle bool correctly. 92 movable<_Ip> && 93 requires(_Ip __i) { 94 typename iter_difference_t<_Ip>; 95 requires __signed_integer_like<iter_difference_t<_Ip>>; 96 { ++__i } -> same_as<_Ip&>; // not required to be equality-preserving 97 __i++; // not required to be equality-preserving 98 }; 99 100 // [iterator.concept.inc] 101 template<class _Ip> 102 concept incrementable = 103 regular<_Ip> && 104 weakly_incrementable<_Ip> && 105 requires(_Ip __i) { 106 { __i++ } -> same_as<_Ip>; 107 }; 108 109 // [iterator.concept.iterator] 110 template<class _Ip> 111 concept input_or_output_iterator = 112 requires(_Ip __i) { 113 { *__i } -> __can_reference; 114 } && 115 weakly_incrementable<_Ip>; 116 117 // [iterator.concept.sentinel] 118 template<class _Sp, class _Ip> 119 concept sentinel_for = 120 semiregular<_Sp> && 121 input_or_output_iterator<_Ip> && 122 __weakly_equality_comparable_with<_Sp, _Ip>; 123 124 template<class, class> 125 inline constexpr bool disable_sized_sentinel_for = false; 126 127 template<class _Sp, class _Ip> 128 concept sized_sentinel_for = 129 sentinel_for<_Sp, _Ip> && 130 !disable_sized_sentinel_for<remove_cv_t<_Sp>, remove_cv_t<_Ip>> && 131 requires(const _Ip& __i, const _Sp& __s) { 132 { __s - __i } -> same_as<iter_difference_t<_Ip>>; 133 { __i - __s } -> same_as<iter_difference_t<_Ip>>; 134 }; 135 136 // [iterator.concept.input] 137 template<class _Ip> 138 concept input_iterator = 139 input_or_output_iterator<_Ip> && 140 indirectly_readable<_Ip> && 141 requires { typename _ITER_CONCEPT<_Ip>; } && 142 derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>; 143 144 // [iterator.concept.output] 145 template<class _Ip, class _Tp> 146 concept output_iterator = 147 input_or_output_iterator<_Ip> && 148 indirectly_writable<_Ip, _Tp> && 149 requires (_Ip __it, _Tp&& __t) { 150 *__it++ = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 151 }; 152 153 // [iterator.concept.forward] 154 template<class _Ip> 155 concept forward_iterator = 156 input_iterator<_Ip> && 157 derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> && 158 incrementable<_Ip> && 159 sentinel_for<_Ip, _Ip>; 160 161 // [iterator.concept.bidir] 162 template<class _Ip> 163 concept bidirectional_iterator = 164 forward_iterator<_Ip> && 165 derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> && 166 requires(_Ip __i) { 167 { --__i } -> same_as<_Ip&>; 168 { __i-- } -> same_as<_Ip>; 169 }; 170 171 template<class _Ip> 172 concept random_access_iterator = 173 bidirectional_iterator<_Ip> && 174 derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> && 175 totally_ordered<_Ip> && 176 sized_sentinel_for<_Ip, _Ip> && 177 requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) { 178 { __i += __n } -> same_as<_Ip&>; 179 { __j + __n } -> same_as<_Ip>; 180 { __n + __j } -> same_as<_Ip>; 181 { __i -= __n } -> same_as<_Ip&>; 182 { __j - __n } -> same_as<_Ip>; 183 { __j[__n] } -> same_as<iter_reference_t<_Ip>>; 184 }; 185 186 template<class _Ip> 187 concept contiguous_iterator = 188 random_access_iterator<_Ip> && 189 derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> && 190 is_lvalue_reference_v<iter_reference_t<_Ip>> && 191 same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> && 192 requires(const _Ip& __i) { 193 { _VSTD::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>; 194 }; 195 196 template<class _Ip> 197 concept __has_arrow = input_iterator<_Ip> && (is_pointer_v<_Ip> || requires(_Ip __i) { __i.operator->(); }); 198 199 // [indirectcallable.indirectinvocable] 200 template<class _Fp, class _It> 201 concept indirectly_unary_invocable = 202 indirectly_readable<_It> && 203 copy_constructible<_Fp> && 204 invocable<_Fp&, iter_value_t<_It>&> && 205 invocable<_Fp&, iter_reference_t<_It>> && 206 invocable<_Fp&, iter_common_reference_t<_It>> && 207 common_reference_with< 208 invoke_result_t<_Fp&, iter_value_t<_It>&>, 209 invoke_result_t<_Fp&, iter_reference_t<_It>>>; 210 211 template<class _Fp, class _It> 212 concept indirectly_regular_unary_invocable = 213 indirectly_readable<_It> && 214 copy_constructible<_Fp> && 215 regular_invocable<_Fp&, iter_value_t<_It>&> && 216 regular_invocable<_Fp&, iter_reference_t<_It>> && 217 regular_invocable<_Fp&, iter_common_reference_t<_It>> && 218 common_reference_with< 219 invoke_result_t<_Fp&, iter_value_t<_It>&>, 220 invoke_result_t<_Fp&, iter_reference_t<_It>>>; 221 222 template<class _Fp, class _It> 223 concept indirect_unary_predicate = 224 indirectly_readable<_It> && 225 copy_constructible<_Fp> && 226 predicate<_Fp&, iter_value_t<_It>&> && 227 predicate<_Fp&, iter_reference_t<_It>> && 228 predicate<_Fp&, iter_common_reference_t<_It>>; 229 230 template<class _Fp, class _It1, class _It2> 231 concept indirect_binary_predicate = 232 indirectly_readable<_It1> && indirectly_readable<_It2> && 233 copy_constructible<_Fp> && 234 predicate<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> && 235 predicate<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> && 236 predicate<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> && 237 predicate<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>> && 238 predicate<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>; 239 240 template<class _Fp, class _It1, class _It2 = _It1> 241 concept indirect_equivalence_relation = 242 indirectly_readable<_It1> && indirectly_readable<_It2> && 243 copy_constructible<_Fp> && 244 equivalence_relation<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> && 245 equivalence_relation<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> && 246 equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> && 247 equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>> && 248 equivalence_relation<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>; 249 250 template<class _Fp, class _It1, class _It2 = _It1> 251 concept indirect_strict_weak_order = 252 indirectly_readable<_It1> && indirectly_readable<_It2> && 253 copy_constructible<_Fp> && 254 strict_weak_order<_Fp&, iter_value_t<_It1>&, iter_value_t<_It2>&> && 255 strict_weak_order<_Fp&, iter_value_t<_It1>&, iter_reference_t<_It2>> && 256 strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_value_t<_It2>&> && 257 strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>> && 258 strict_weak_order<_Fp&, iter_common_reference_t<_It1>, iter_common_reference_t<_It2>>; 259 260 template<class _Fp, class... _Its> 261 requires (indirectly_readable<_Its> && ...) && invocable<_Fp, iter_reference_t<_Its>...> 262 using indirect_result_t = invoke_result_t<_Fp, iter_reference_t<_Its>...>; 263 264 template<class _In, class _Out> 265 concept indirectly_movable = 266 indirectly_readable<_In> && 267 indirectly_writable<_Out, iter_rvalue_reference_t<_In>>; 268 269 template<class _In, class _Out> 270 concept indirectly_movable_storable = 271 indirectly_movable<_In, _Out> && 272 indirectly_writable<_Out, iter_value_t<_In>> && 273 movable<iter_value_t<_In>> && 274 constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> && 275 assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>; 276 277 template<class _In, class _Out> 278 concept indirectly_copyable = 279 indirectly_readable<_In> && 280 indirectly_writable<_Out, iter_reference_t<_In>>; 281 282 template<class _In, class _Out> 283 concept indirectly_copyable_storable = 284 indirectly_copyable<_In, _Out> && 285 indirectly_writable<_Out, iter_value_t<_In>&> && 286 indirectly_writable<_Out, const iter_value_t<_In>&> && 287 indirectly_writable<_Out, iter_value_t<_In>&&> && 288 indirectly_writable<_Out, const iter_value_t<_In>&&> && 289 copyable<iter_value_t<_In>> && 290 constructible_from<iter_value_t<_In>, iter_reference_t<_In>> && 291 assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>; 292 293 // Note: indirectly_swappable is located in iter_swap.h to prevent a dependency cycle 294 // (both iter_swap and indirectly_swappable require indirectly_readable). 295 296 #endif // _LIBCPP_STD_VER > 17 297 298 _LIBCPP_END_NAMESPACE_STD 299 300 #endif // _LIBCPP___ITERATOR_CONCEPTS_H 301