v1/__iterator/concepts.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___ITERATOR_CONCEPTS_H
0011 #define _LIBCPP___ITERATOR_CONCEPTS_H
0012
0013 #include <__concepts/arithmetic.h>
0014 #include <__concepts/assignable.h>
0015 #include <__concepts/common_reference_with.h>
0016 #include <__concepts/constructible.h>
0017 #include <__concepts/copyable.h>
0018 #include <__concepts/derived_from.h>
0019 #include <__concepts/equality_comparable.h>
0020 #include <__concepts/invocable.h>
0021 #include <__concepts/movable.h>
0022 #include <__concepts/predicate.h>
0023 #include <__concepts/regular.h>
0024 #include <__concepts/relation.h>
0025 #include <__concepts/same_as.h>
0026 #include <__concepts/semiregular.h>
0027 #include <__concepts/totally_ordered.h>
0028 #include <__config>
0029 #include <__iterator/incrementable_traits.h>
0030 #include <__iterator/iter_move.h>
0031 #include <__iterator/iterator_traits.h>
0032 #include <__iterator/readable_traits.h>
0033 #include <__memory/pointer_traits.h>
0034 #include <__type_traits/add_pointer.h>
0035 #include <__type_traits/common_reference.h>
0036 #include <__type_traits/integral_constant.h>
0037 #include <__type_traits/invoke.h>
0038 #include <__type_traits/is_pointer.h>
0039 #include <__type_traits/is_primary_template.h>
0040 #include <__type_traits/is_reference.h>
0041 #include <__type_traits/remove_cv.h>
0042 #include <__type_traits/remove_cvref.h>
0043 #include <__utility/forward.h>
0044
0045 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0046 #  pragma GCC system_header
0047 #endif
0048
0049 _LIBCPP_BEGIN_NAMESPACE_STD
0050
0051 #if _LIBCPP_STD_VER >= 20
0052
0053 // [iterator.concept.readable]
0054 template <class _In>
0055 concept __indirectly_readable_impl =
0056     requires(const _In __i) {
0057       typename iter_value_t<_In>;
0058       typename iter_reference_t<_In>;
0059       typename iter_rvalue_reference_t<_In>;
0060       { *__i } -> same_as<iter_reference_t<_In>>;
0061       { ranges::iter_move(__i) } -> same_as<iter_rvalue_reference_t<_In>>;
0062     } && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> &&
0063     common_reference_with<iter_reference_t<_In>&&, iter_rvalue_reference_t<_In>&&> &&
0064     common_reference_with<iter_rvalue_reference_t<_In>&&, const iter_value_t<_In>&>;
0065
0066 template <class _In>
0067 concept indirectly_readable = __indirectly_readable_impl<remove_cvref_t<_In>>;
0068
0069 template <class _Tp>
0070 using __projected_iterator_t _LIBCPP_NODEBUG = typename _Tp::__projected_iterator;
0071
0072 template <class _Tp>
0073 using __projected_projection_t _LIBCPP_NODEBUG = typename _Tp::__projected_projection;
0074
0075 template <class _Tp>
0076 concept __specialization_of_projected = requires {
0077   typename __projected_iterator_t<_Tp>;
0078   typename __projected_projection_t<_Tp>;
0079 } && __is_primary_template<_Tp>::value;
0080
0081 template <class _Tp>
0082 struct __indirect_value_t_impl {
0083   using type = iter_value_t<_Tp>&;
0084 };
0085 template <__specialization_of_projected _Tp>
0086 struct __indirect_value_t_impl<_Tp> {
0087   using type = invoke_result_t<__projected_projection_t<_Tp>&,
0088                                typename __indirect_value_t_impl<__projected_iterator_t<_Tp>>::type>;
0089 };
0090
0091 template <indirectly_readable _Tp>
0092 using __indirect_value_t _LIBCPP_NODEBUG = typename __indirect_value_t_impl<_Tp>::type;
0093
0094 template <indirectly_readable _Tp>
0095 using iter_common_reference_t = common_reference_t<iter_reference_t<_Tp>, __indirect_value_t<_Tp>>;
0096
0097 // [iterator.concept.writable]
0098 template <class _Out, class _Tp>
0099 concept indirectly_writable = requires(_Out&& __o, _Tp&& __t) {
0100   *__o                                             = std::forward<_Tp>(__t); // not required to be equality-preserving
0101   *std::forward<_Out>(__o)                         = std::forward<_Tp>(__t); // not required to be equality-preserving
0102   const_cast<const iter_reference_t<_Out>&&>(*__o) = std::forward<_Tp>(__t); // not required to be equality-preserving
0103   const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o)) =
0104       std::forward<_Tp>(__t); // not required to be equality-preserving
0105 };
0106
0107 // [iterator.concept.winc]
0108 template <class _Tp>
0109 concept __integer_like = integral<_Tp> && !same_as<_Tp, bool>;
0110
0111 template <class _Tp>
0112 concept __signed_integer_like = signed_integral<_Tp>;
0113
0114 template <class _Ip>
0115 concept weakly_incrementable =
0116     // TODO: remove this once the clang bug is fixed (bugs.llvm.org/PR48173).
0117     !same_as<_Ip, bool> && // Currently, clang does not handle bool correctly.
0118     movable<_Ip> && requires(_Ip __i) {
0119       typename iter_difference_t<_Ip>;
0120       requires __signed_integer_like<iter_difference_t<_Ip>>;
0121       { ++__i } -> same_as<_Ip&>; // not required to be equality-preserving
0122       __i++;                      // not required to be equality-preserving
0123     };
0124
0125 // [iterator.concept.inc]
0126 template <class _Ip>
0127 concept incrementable = regular<_Ip> && weakly_incrementable<_Ip> && requires(_Ip __i) {
0128   { __i++ } -> same_as<_Ip>;
0129 };
0130
0131 // [iterator.concept.iterator]
0132 template <class _Ip>
0133 concept input_or_output_iterator = requires(_Ip __i) {
0134   { *__i } -> __can_reference;
0135 } && weakly_incrementable<_Ip>;
0136
0137 // [iterator.concept.sentinel]
0138 template <class _Sp, class _Ip>
0139 concept sentinel_for = semiregular<_Sp> && input_or_output_iterator<_Ip> && __weakly_equality_comparable_with<_Sp, _Ip>;
0140
0141 template <class, class>
0142 inline constexpr bool disable_sized_sentinel_for = false;
0143
0144 template <class _Sp, class _Ip>
0145 concept sized_sentinel_for =
0146     sentinel_for<_Sp, _Ip> && !disable_sized_sentinel_for<remove_cv_t<_Sp>, remove_cv_t<_Ip>> &&
0147     requires(const _Ip& __i, const _Sp& __s) {
0148       { __s - __i } -> same_as<iter_difference_t<_Ip>>;
0149       { __i - __s } -> same_as<iter_difference_t<_Ip>>;
0150     };
0151
0152 // [iterator.concept.input]
0153 template <class _Ip>
0154 concept input_iterator = input_or_output_iterator<_Ip> && indirectly_readable<_Ip> && requires {
0155   typename _ITER_CONCEPT<_Ip>;
0156 } && derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>;
0157
0158 // [iterator.concept.output]
0159 template <class _Ip, class _Tp>
0160 concept output_iterator =
0161     input_or_output_iterator<_Ip> && indirectly_writable<_Ip, _Tp> && requires(_Ip __it, _Tp&& __t) {
0162       *__it++ = std::forward<_Tp>(__t); // not required to be equality-preserving
0163     };
0164
0165 // [iterator.concept.forward]
0166 template <class _Ip>
0167 concept forward_iterator =
0168     input_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> && incrementable<_Ip> &&
0169     sentinel_for<_Ip, _Ip>;
0170
0171 // [iterator.concept.bidir]
0172 template <class _Ip>
0173 concept bidirectional_iterator =
0174     forward_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> && requires(_Ip __i) {
0175       { --__i } -> same_as<_Ip&>;
0176       { __i-- } -> same_as<_Ip>;
0177     };
0178
0179 template <class _Ip>
0180 concept random_access_iterator =
0181     bidirectional_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> &&
0182     totally_ordered<_Ip> && sized_sentinel_for<_Ip, _Ip> &&
0183     requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {
0184       { __i += __n } -> same_as<_Ip&>;
0185       { __j + __n } -> same_as<_Ip>;
0186       { __n + __j } -> same_as<_Ip>;
0187       { __i -= __n } -> same_as<_Ip&>;
0188       { __j - __n } -> same_as<_Ip>;
0189       { __j[__n] } -> same_as<iter_reference_t<_Ip>>;
0190     };
0191
0192 template <class _Ip>
0193 concept contiguous_iterator =
0194     random_access_iterator<_Ip> && derived_from<_ITER_CONCEPT<_Ip>, contiguous_iterator_tag> &&
0195     is_lvalue_reference_v<iter_reference_t<_Ip>> && same_as<iter_value_t<_Ip>, remove_cvref_t<iter_reference_t<_Ip>>> &&
0196     requires(const _Ip& __i) {
0197       { std::to_address(__i) } -> same_as<add_pointer_t<iter_reference_t<_Ip>>>;
0198     };
0199
0200 template <class _Ip>
0201 concept __has_arrow = input_iterator<_Ip> && (is_pointer_v<_Ip> || requires(_Ip __i) { __i.operator->(); });
0202
0203 // [indirectcallable.indirectinvocable]
0204 template <class _Fp, class _It>
0205 concept indirectly_unary_invocable =
0206     indirectly_readable<_It> && copy_constructible<_Fp> && invocable<_Fp&, __indirect_value_t<_It>> &&
0207     invocable<_Fp&, iter_reference_t<_It>> &&
0208     common_reference_with< invoke_result_t<_Fp&, __indirect_value_t<_It>>,
0209                            invoke_result_t<_Fp&, iter_reference_t<_It>>>;
0210
0211 template <class _Fp, class _It>
0212 concept indirectly_regular_unary_invocable =
0213     indirectly_readable<_It> && copy_constructible<_Fp> && regular_invocable<_Fp&, __indirect_value_t<_It>> &&
0214     regular_invocable<_Fp&, iter_reference_t<_It>> &&
0215     common_reference_with< invoke_result_t<_Fp&, __indirect_value_t<_It>>,
0216                            invoke_result_t<_Fp&, iter_reference_t<_It>>>;
0217
0218 template <class _Fp, class _It>
0219 concept indirect_unary_predicate =
0220     indirectly_readable<_It> && copy_constructible<_Fp> && predicate<_Fp&, __indirect_value_t<_It>> &&
0221     predicate<_Fp&, iter_reference_t<_It>>;
0222
0223 template <class _Fp, class _It1, class _It2>
0224 concept indirect_binary_predicate =
0225     indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
0226     predicate<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&
0227     predicate<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&
0228     predicate<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&
0229     predicate<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
0230
0231 template <class _Fp, class _It1, class _It2 = _It1>
0232 concept indirect_equivalence_relation =
0233     indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
0234     equivalence_relation<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&
0235     equivalence_relation<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&
0236     equivalence_relation<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&
0237     equivalence_relation<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
0238
0239 template <class _Fp, class _It1, class _It2 = _It1>
0240 concept indirect_strict_weak_order =
0241     indirectly_readable<_It1> && indirectly_readable<_It2> && copy_constructible<_Fp> &&
0242     strict_weak_order<_Fp&, __indirect_value_t<_It1>, __indirect_value_t<_It2>> &&
0243     strict_weak_order<_Fp&, __indirect_value_t<_It1>, iter_reference_t<_It2>> &&
0244     strict_weak_order<_Fp&, iter_reference_t<_It1>, __indirect_value_t<_It2>> &&
0245     strict_weak_order<_Fp&, iter_reference_t<_It1>, iter_reference_t<_It2>>;
0246
0247 template <class _Fp, class... _Its>
0248   requires(indirectly_readable<_Its> && ...) && invocable<_Fp, iter_reference_t<_Its>...>
0249 using indirect_result_t = invoke_result_t<_Fp, iter_reference_t<_Its>...>;
0250
0251 template <class _In, class _Out>
0252 concept indirectly_movable = indirectly_readable<_In> && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;
0253
0254 template <class _In, class _Out>
0255 concept indirectly_movable_storable =
0256     indirectly_movable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>> &&
0257     constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> &&
0258     assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
0259
0260 template <class _In, class _Out>
0261 concept indirectly_copyable = indirectly_readable<_In> && indirectly_writable<_Out, iter_reference_t<_In>>;
0262
0263 template <class _In, class _Out>
0264 concept indirectly_copyable_storable =
0265     indirectly_copyable<_In, _Out> && indirectly_writable<_Out, iter_value_t<_In>&> &&
0266     indirectly_writable<_Out, const iter_value_t<_In>&> && indirectly_writable<_Out, iter_value_t<_In>&&> &&
0267     indirectly_writable<_Out, const iter_value_t<_In>&&> && copyable<iter_value_t<_In>> &&
0268     constructible_from<iter_value_t<_In>, iter_reference_t<_In>> &&
0269     assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
0270
0271 // Note: indirectly_swappable is located in iter_swap.h to prevent a dependency cycle
0272 // (both iter_swap and indirectly_swappable require indirectly_readable).
0273
0274 #endif // _LIBCPP_STD_VER >= 20
0275
0276 template <class _Tp>
0277 using __has_random_access_iterator_category_or_concept _LIBCPP_NODEBUG
0278 #if _LIBCPP_STD_VER >= 20
0279     = integral_constant<bool, random_access_iterator<_Tp>>;
0280 #else  // _LIBCPP_STD_VER < 20
0281     = __has_random_access_iterator_category<_Tp>;
0282 #endif // _LIBCPP_STD_VER
0283
0284 _LIBCPP_END_NAMESPACE_STD
0285
0286 #endif // _LIBCPP___ITERATOR_CONCEPTS_H