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