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