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 <concepts> 20 21 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 22 #pragma GCC system_header 23 #endif 24 25 _LIBCPP_PUSH_MACROS 26 #include <__undef_macros> 27 28 _LIBCPP_BEGIN_NAMESPACE_STD 29 30 #if !defined(_LIBCPP_HAS_NO_RANGES) 31 32 // clang-format off 33 34 // [iterator.concept.readable] 35 template<class _In> 36 concept __indirectly_readable_impl = requires(const _In __i)37 requires(const _In __i) { 38 typename iter_value_t<_In>; 39 typename iter_reference_t<_In>; 40 typename iter_rvalue_reference_t<_In>; 41 { *__i } -> same_as<iter_reference_t<_In> >; 42 { ranges::iter_move(__i) } -> same_as<iter_rvalue_reference_t<_In> >; 43 } && 44 common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> && 45 common_reference_with<iter_reference_t<_In>&&, iter_rvalue_reference_t<_In>&&> && 46 common_reference_with<iter_rvalue_reference_t<_In>&&, const iter_value_t<_In>&>; 47 48 template<class _In> 49 concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In> >; 50 51 // [iterator.concept.writable] 52 template<class _Out, class _Tp> 53 concept indirectly_writable = requires(_Out && __o,_Tp && __t)54 requires(_Out&& __o, _Tp&& __t) { 55 *__o = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 56 *_VSTD::forward<_Out>(__o) = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 57 const_cast<const iter_reference_t<_Out>&&>(*__o) = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 58 const_cast<const iter_reference_t<_Out>&&>(*_VSTD::forward<_Out>(__o)) = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving 59 }; 60 61 // [iterator.concept.winc] 62 template<class _Tp> 63 concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>; 64 65 template<class _Tp> 66 concept __signed_integer_like = signed_integral<_Tp>; 67 68 template<class _Ip> 69 concept weakly_incrementable = 70 default_initializable<_Ip> && 71 movable<_Ip> && requires(_Ip __i)72 requires(_Ip __i) { 73 typename iter_difference_t<_Ip>; 74 requires __signed_integer_like<iter_difference_t<_Ip> >; 75 { ++__i } -> same_as<_Ip&>; // not required to be equality-preserving 76 __i++; // not required to be equality-preserving 77 }; 78 79 // [iterator.concept.inc] 80 template<class _Ip> 81 concept incrementable = 82 regular<_Ip> && 83 weakly_incrementable<_Ip> && requires(_Ip __i)84 requires(_Ip __i) { 85 { __i++ } -> same_as<_Ip>; 86 }; 87 88 // [iterator.concept.iterator] 89 template<class _Ip> 90 concept input_or_output_iterator = requires(_Ip __i)91 requires(_Ip __i) { 92 { *__i } -> __referenceable; 93 } && 94 weakly_incrementable<_Ip>; 95 96 // [iterator.concept.sentinel] 97 template<class _Sp, class _Ip> 98 concept sentinel_for = 99 semiregular<_Sp> && 100 input_or_output_iterator<_Ip> && 101 __weakly_equality_comparable_with<_Sp, _Ip>; 102 103 template<class, class> 104 inline constexpr bool disable_sized_sentinel_for = false; 105 106 template<class _Sp, class _Ip> 107 concept sized_sentinel_for = 108 sentinel_for<_Sp, _Ip> && 109 !disable_sized_sentinel_for<remove_cv_t<_Sp>, remove_cv_t<_Ip> > && 110 requires(const _Ip& __i, const _Sp& __s) { 111 { __s - __i } -> same_as<iter_difference_t<_Ip> >; 112 { __i - __s } -> same_as<iter_difference_t<_Ip> >; 113 }; 114 115 // [iterator.concept.input] 116 template<class _Ip> 117 concept input_iterator = 118 input_or_output_iterator<_Ip> && 119 indirectly_readable<_Ip> && 120 requires { typename _ITER_CONCEPT<_Ip>; } && 121 derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>; 122 123 // [iterator.concept.forward] 124 template<class _Ip> 125 concept forward_iterator = 126 input_iterator<_Ip> && 127 derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> && 128 incrementable<_Ip> && 129 sentinel_for<_Ip, _Ip>; 130 131 // [iterator.concept.bidir] 132 template<class _Ip> 133 concept bidirectional_iterator = 134 forward_iterator<_Ip> && 135 derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> && requires(_Ip __i)136 requires(_Ip __i) { 137 { --__i } -> same_as<_Ip&>; 138 { __i-- } -> same_as<_Ip>; 139 }; 140 141 template<class _Ip> 142 concept random_access_iterator = 143 bidirectional_iterator<_Ip> && 144 derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> && 145 totally_ordered<_Ip> && 146 sized_sentinel_for<_Ip, _Ip> && requires(_Ip __i,const _Ip __j,const iter_difference_t<_Ip> __n)147 requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) { 148 { __i += __n } -> same_as<_Ip&>; 149 { __j + __n } -> same_as<_Ip>; 150 { __n + __j } -> same_as<_Ip>; 151 { __i -= __n } -> same_as<_Ip&>; 152 { __j - __n } -> same_as<_Ip>; 153 { __j[__n] } -> same_as<iter_reference_t<_Ip>>; 154 }; 155 156 template<class _Ip> 157 concept contiguous_iterator = 158 random_access_iterator<_Ip> && 159 derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> && 160 is_lvalue_reference_v<iter_reference_t<_Ip>> && 161 same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> && 162 (is_pointer_v<_Ip> || requires { sizeof(__pointer_traits_element_type<_Ip>); }) && requires(const _Ip & __i)163 requires(const _Ip& __i) { 164 { _VSTD::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>; 165 }; 166 167 // clang-format on 168 169 #endif // !defined(_LIBCPP_HAS_NO_RANGES) 170 171 _LIBCPP_END_NAMESPACE_STD 172 173 _LIBCPP_POP_MACROS 174 175 #endif // _LIBCPP___ITERATOR_CONCEPTS_H 176