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