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