libcxx/include/__iterator/concepts.h

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