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