325 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___ITERATOR_CONCEPTS_H11#define _LIBCPP___ITERATOR_CONCEPTS_H12 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_header51#endif52 53_LIBCPP_BEGIN_NAMESPACE_STD54 55#if _LIBCPP_STD_VER >= 2056 57// [iterator.concept.readable]58template <class _In>59concept __indirectly_readable_impl =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 70template <class _In>71concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In>>;72 73template <class _Tp>74using __projected_iterator_t _LIBCPP_NODEBUG = typename _Tp::__projected_iterator;75 76template <class _Tp>77using __projected_projection_t _LIBCPP_NODEBUG = typename _Tp::__projected_projection;78 79template <class _Tp>80concept __specialization_of_projected = requires {81 typename __projected_iterator_t<_Tp>;82 typename __projected_projection_t<_Tp>;83} && __is_primary_template<_Tp>::value;84 85template <class _Tp>86struct __indirect_value_t_impl {87 using type _LIBCPP_NODEBUG = iter_value_t<_Tp>&;88};89template <__specialization_of_projected _Tp>90struct __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 96template <indirectly_readable _Tp>97using __indirect_value_t _LIBCPP_NODEBUG = typename __indirect_value_t_impl<_Tp>::type;98 99template <indirectly_readable _Tp>100using iter_common_reference_t = common_reference_t<iter_reference_t<_Tp>, __indirect_value_t<_Tp>>;101 102// [iterator.concept.writable]103template <class _Out, class _Tp>104concept indirectly_writable = requires(_Out&& __o, _Tp&& __t) {105 *__o = std::forward<_Tp>(__t); // not required to be equality-preserving106 *std::forward<_Out>(__o) = std::forward<_Tp>(__t); // not required to be equality-preserving107 const_cast<const iter_reference_t<_Out>&&>(*__o) = std::forward<_Tp>(__t); // not required to be equality-preserving108 const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o)) =109 std::forward<_Tp>(__t); // not required to be equality-preserving110};111 112// [iterator.concept.winc]113template <class _Tp>114concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>;115 116template <class _Tp>117concept __signed_integer_like = signed_integral<_Tp>;118 119template <class _Ip>120concept weakly_incrementable = movable<_Ip> && requires(_Ip __i) {121 typename iter_difference_t<_Ip>;122 requires __signed_integer_like<iter_difference_t<_Ip>>;123 { ++__i } -> same_as<_Ip&>; // not required to be equality-preserving124 __i++; // not required to be equality-preserving125};126 127// [iterator.concept.inc]128template <class _Ip>129concept incrementable = regular<_Ip> && weakly_incrementable<_Ip> && requires(_Ip __i) {130 { __i++ } -> same_as<_Ip>;131};132 133// [iterator.concept.iterator]134template <class _Ip>135concept input_or_output_iterator = requires(_Ip __i) {136 { *__i } -> __referenceable;137} && weakly_incrementable<_Ip>;138 139// [iterator.concept.sentinel]140template <class _Sp, class _Ip>141concept sentinel_for = semiregular<_Sp> && input_or_output_iterator<_Ip> && __weakly_equality_comparable_with<_Sp, _Ip>;142 143template <class, class>144inline constexpr bool disable_sized_sentinel_for = false;145 146template <class _Sp, class _Ip>147concept sized_sentinel_for =148 sentinel_for<_Sp, _Ip> && !disable_sized_sentinel_for<remove_cv_t<_Sp>, remove_cv_t<_Ip>> &&149 requires(const _Ip& __i, const _Sp& __s) {150 { __s - __i } -> same_as<iter_difference_t<_Ip>>;151 { __i - __s } -> same_as<iter_difference_t<_Ip>>;152 };153 154template <class _Iter>155struct __iter_traits_cache {156 using type _LIBCPP_NODEBUG =157 _If<__is_primary_template<iterator_traits<_Iter> >::value, _Iter, iterator_traits<_Iter> >;158};159template <class _Iter>160using _ITER_TRAITS _LIBCPP_NODEBUG = typename __iter_traits_cache<_Iter>::type;161 162struct __iter_concept_concept_test {163 template <class _Iter>164 using _Apply _LIBCPP_NODEBUG = typename _ITER_TRAITS<_Iter>::iterator_concept;165};166struct __iter_concept_category_test {167 template <class _Iter>168 using _Apply _LIBCPP_NODEBUG = typename _ITER_TRAITS<_Iter>::iterator_category;169};170struct __iter_concept_random_fallback {171 template <class _Iter>172 using _Apply _LIBCPP_NODEBUG =173 __enable_if_t<__is_primary_template<iterator_traits<_Iter> >::value, random_access_iterator_tag>;174};175 176template <class _Iter, class _Tester>177struct __test_iter_concept : _IsValidExpansion<_Tester::template _Apply, _Iter>, _Tester {};178 179template <class _Iter>180struct __iter_concept_cache {181 using type _LIBCPP_NODEBUG =182 _Or<__test_iter_concept<_Iter, __iter_concept_concept_test>,183 __test_iter_concept<_Iter, __iter_concept_category_test>,184 __test_iter_concept<_Iter, __iter_concept_random_fallback> >;185};186 187template <class _Iter>188using _ITER_CONCEPT _LIBCPP_NODEBUG = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>;189 190// [iterator.concept.input]191template <class _Ip>192concept input_iterator = input_or_output_iterator<_Ip> && indirectly_readable<_Ip> && requires {193 typename _ITER_CONCEPT<_Ip>;194} && derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>;195 196// [iterator.concept.output]197template <class _Ip, class _Tp>198concept output_iterator =199 input_or_output_iterator<_Ip> && indirectly_writable<_Ip, _Tp> && requires(_Ip __it, _Tp&& __t) {200 *__it++ = std::forward<_Tp>(__t); // not required to be equality-preserving201 };202 203// [iterator.concept.forward]204template <class _Ip>205concept forward_iterator =206 input_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> && incrementable<_Ip> &&207 sentinel_for<_Ip, _Ip>;208 209// [iterator.concept.bidir]210template <class _Ip>211concept bidirectional_iterator =212 forward_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> && requires(_Ip __i) {213 { --__i } -> same_as<_Ip&>;214 { __i-- } -> same_as<_Ip>;215 };216 217template <class _Ip>218concept random_access_iterator =219 bidirectional_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> &&220 totally_ordered<_Ip> && sized_sentinel_for<_Ip, _Ip> &&221 requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {222 { __i += __n } -> same_as<_Ip&>;223 { __j + __n } -> same_as<_Ip>;224 { __n + __j } -> same_as<_Ip>;225 { __i -= __n } -> same_as<_Ip&>;226 { __j - __n } -> same_as<_Ip>;227 { __j[__n] } -> same_as<iter_reference_t<_Ip>>;228 };229 230template <class _Ip>231concept contiguous_iterator =232 random_access_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> &&233 is_lvalue_reference_v<iter_reference_t<_Ip>> && same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> &&234 requires(const _Ip& __i) {235 { std::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>;236 };237 238template <class _Ip>239concept __has_arrow = input_iterator<_Ip> && (is_pointer_v<_Ip> || requires(_Ip __i) { __i.operator->(); });240 241// [indirectcallable.indirectinvocable]242template <class _Fp, class _It>243concept indirectly_unary_invocable =244 indirectly_readable<_It> && copy_constructible<_Fp> && invocable<_Fp&, __indirect_value_t<_It>> &&245 invocable<_Fp&, iter_reference_t<_It>> &&246 common_reference_with< invoke_result_t<_Fp&, __indirect_value_t<_It>>,247 invoke_result_t<_Fp&, iter_reference_t<_It>>>;248 249template <class _Fp, class _It>250concept indirectly_regular_unary_invocable =251 indirectly_readable<_It> && copy_constructible<_Fp> && regular_invocable<_Fp&, __indirect_value_t<_It>> &&252 regular_invocable<_Fp&, iter_reference_t<_It>> &&253 common_reference_with< invoke_result_t<_Fp&, __indirect_value_t<_It>>,254 invoke_result_t<_Fp&, iter_reference_t<_It>>>;255 256template <class _Fp, class _It>257concept indirect_unary_predicate =258 indirectly_readable<_It> && copy_constructible<_Fp> && predicate<_Fp&, __indirect_value_t<_It>> &&259 predicate<_Fp&, iter_reference_t<_It>>;260 261template <class _Fp, class _It1, class _It2>262concept indirect_binary_predicate =263 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&264 predicate<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&265 predicate<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&266 predicate<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&267 predicate<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;268 269template <class _Fp, class _It1, class _It2 = _It1>270concept indirect_equivalence_relation =271 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&272 equivalence_relation<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&273 equivalence_relation<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&274 equivalence_relation<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&275 equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;276 277template <class _Fp, class _It1, class _It2 = _It1>278concept indirect_strict_weak_order =279 indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&280 strict_weak_order<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&281 strict_weak_order<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&282 strict_weak_order<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&283 strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;284 285template <class _Fp, class... _Its>286 requires(indirectly_readable<_Its> && ...) && invocable<_Fp, iter_reference_t<_Its>...>287using indirect_result_t = invoke_result_t<_Fp, iter_reference_t<_Its>...>;288 289template <class _In, class _Out>290concept indirectly_movable = indirectly_readable<_In> && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;291 292template <class _In, class _Out>293concept indirectly_movable_storable =294 indirectly_movable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>> &&295 constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> &&296 assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;297 298template <class _In, class _Out>299concept indirectly_copyable = indirectly_readable<_In> && indirectly_writable<_Out, iter_reference_t<_In>>;300 301template <class _In, class _Out>302concept indirectly_copyable_storable =303 indirectly_copyable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>&> &&304 indirectly_writable<_Out, const iter_value_t<_In>&> && indirectly_writable<_Out, iter_value_t<_In>&&> &&305 indirectly_writable<_Out, const iter_value_t<_In>&&> && copyable<iter_value_t<_In>> &&306 constructible_from<iter_value_t<_In>, iter_reference_t<_In>> &&307 assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;308 309// Note: indirectly_swappable is located in iter_swap.h to prevent a dependency cycle310// (both iter_swap and indirectly_swappable require indirectly_readable).311 312#endif // _LIBCPP_STD_VER >= 20313 314template <class _Tp>315using __has_random_access_iterator_category_or_concept _LIBCPP_NODEBUG316#if _LIBCPP_STD_VER >= 20317 = integral_constant<bool, random_access_iterator<_Tp>>;318#else // _LIBCPP_STD_VER < 20319 = __has_random_access_iterator_category<_Tp>;320#endif // _LIBCPP_STD_VER321 322_LIBCPP_END_NAMESPACE_STD323 324#endif // _LIBCPP___ITERATOR_CONCEPTS_H325