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