__cxx03/__iterator/common_iterator.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_COMMON_ITERATOR_H
0011 #define _LIBCPP___CXX03___ITERATOR_COMMON_ITERATOR_H
0012
0013 #include <__cxx03/__assert>
0014 #include <__cxx03/__concepts/assignable.h>
0015 #include <__cxx03/__concepts/constructible.h>
0016 #include <__cxx03/__concepts/convertible_to.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/same_as.h>
0021 #include <__cxx03/__config>
0022 #include <__cxx03/__iterator/concepts.h>
0023 #include <__cxx03/__iterator/incrementable_traits.h>
0024 #include <__cxx03/__iterator/iter_move.h>
0025 #include <__cxx03/__iterator/iter_swap.h>
0026 #include <__cxx03/__iterator/iterator_traits.h>
0027 #include <__cxx03/__iterator/readable_traits.h>
0028 #include <__cxx03/__memory/addressof.h>
0029 #include <__cxx03/__type_traits/is_pointer.h>
0030 #include <__cxx03/__utility/declval.h>
0031 #include <__cxx03/variant>
0032
0033 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0034 #  pragma GCC system_header
0035 #endif
0036
0037 _LIBCPP_PUSH_MACROS
0038 #include <__cxx03/__undef_macros>
0039
0040 _LIBCPP_BEGIN_NAMESPACE_STD
0041
0042 #if _LIBCPP_STD_VER >= 20
0043
0044 template <class _Iter>
0045 concept __can_use_postfix_proxy =
0046     constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> && move_constructible<iter_value_t<_Iter>>;
0047
0048 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
0049   requires(!same_as<_Iter, _Sent> && copyable<_Iter>)
0050 class common_iterator {
0051   struct __proxy {
0052     _LIBCPP_HIDE_FROM_ABI constexpr const iter_value_t<_Iter>* operator->() const noexcept {
0053       return std::addressof(__value_);
0054     }
0055     iter_value_t<_Iter> __value_;
0056   };
0057
0058   struct __postfix_proxy {
0059     _LIBCPP_HIDE_FROM_ABI constexpr const iter_value_t<_Iter>& operator*() const noexcept { return __value_; }
0060     iter_value_t<_Iter> __value_;
0061   };
0062
0063   variant<_Iter, _Sent> __hold_;
0064   template <input_or_output_iterator _OtherIter, sentinel_for<_OtherIter> _OtherSent>
0065     requires(!same_as<_OtherIter, _OtherSent> && copyable<_OtherIter>)
0066   friend class common_iterator;
0067
0068 public:
0069   _LIBCPP_HIDE_FROM_ABI common_iterator()
0070     requires default_initializable<_Iter>
0071   = default;
0072
0073   _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(_Iter __i) : __hold_(in_place_type<_Iter>, std::move(__i)) {}
0074   _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(_Sent __s) : __hold_(in_place_type<_Sent>, std::move(__s)) {}
0075
0076   template <class _I2, class _S2>
0077     requires convertible_to<const _I2&, _Iter> && convertible_to<const _S2&, _Sent>
0078   _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(const common_iterator<_I2, _S2>& __other)
0079       : __hold_([&]() -> variant<_Iter, _Sent> {
0080           _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0081               !__other.__hold_.valueless_by_exception(), "Attempted to construct from a valueless common_iterator");
0082           if (__other.__hold_.index() == 0)
0083             return variant<_Iter, _Sent>{in_place_index<0>, std::__unchecked_get<0>(__other.__hold_)};
0084           return variant<_Iter, _Sent>{in_place_index<1>, std::__unchecked_get<1>(__other.__hold_)};
0085         }()) {}
0086
0087   template <class _I2, class _S2>
0088     requires convertible_to<const _I2&, _Iter> && convertible_to<const _S2&, _Sent> &&
0089              assignable_from<_Iter&, const _I2&> && assignable_from<_Sent&, const _S2&>
0090   _LIBCPP_HIDE_FROM_ABI common_iterator& operator=(const common_iterator<_I2, _S2>& __other) {
0091     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0092         !__other.__hold_.valueless_by_exception(), "Attempted to assign from a valueless common_iterator");
0093
0094     auto __idx       = __hold_.index();
0095     auto __other_idx = __other.__hold_.index();
0096
0097     // If they're the same index, just assign.
0098     if (__idx == 0 && __other_idx == 0)
0099       std::__unchecked_get<0>(__hold_) = std::__unchecked_get<0>(__other.__hold_);
0100     else if (__idx == 1 && __other_idx == 1)
0101       std::__unchecked_get<1>(__hold_) = std::__unchecked_get<1>(__other.__hold_);
0102
0103     // Otherwise replace with the oposite element.
0104     else if (__other_idx == 1)
0105       __hold_.template emplace<1>(std::__unchecked_get<1>(__other.__hold_));
0106     else if (__other_idx == 0)
0107       __hold_.template emplace<0>(std::__unchecked_get<0>(__other.__hold_));
0108
0109     return *this;
0110   }
0111
0112   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() {
0113     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0114         std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator");
0115     return *std::__unchecked_get<_Iter>(__hold_);
0116   }
0117
0118   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const
0119     requires __dereferenceable<const _Iter>
0120   {
0121     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0122         std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator");
0123     return *std::__unchecked_get<_Iter>(__hold_);
0124   }
0125
0126   template <class _I2 = _Iter>
0127   _LIBCPP_HIDE_FROM_ABI auto operator->() const
0128     requires indirectly_readable<const _I2> && (requires(const _I2& __i) {
0129                __i.operator->();
0130              } || is_reference_v<iter_reference_t<_I2>> || constructible_from<iter_value_t<_I2>, iter_reference_t<_I2>>)
0131   {
0132     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0133         std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator");
0134     if constexpr (is_pointer_v<_Iter> || requires(const _Iter& __i) { __i.operator->(); }) {
0135       return std::__unchecked_get<_Iter>(__hold_);
0136     } else if constexpr (is_reference_v<iter_reference_t<_Iter>>) {
0137       auto&& __tmp = *std::__unchecked_get<_Iter>(__hold_);
0138       return std::addressof(__tmp);
0139     } else {
0140       return __proxy{*std::__unchecked_get<_Iter>(__hold_)};
0141     }
0142   }
0143
0144   _LIBCPP_HIDE_FROM_ABI common_iterator& operator++() {
0145     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0146         std::holds_alternative<_Iter>(__hold_), "Attempted to increment a non-dereferenceable common_iterator");
0147     ++std::__unchecked_get<_Iter>(__hold_);
0148     return *this;
0149   }
0150
0151   _LIBCPP_HIDE_FROM_ABI decltype(auto) operator++(int) {
0152     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0153         std::holds_alternative<_Iter>(__hold_), "Attempted to increment a non-dereferenceable common_iterator");
0154     if constexpr (forward_iterator<_Iter>) {
0155       auto __tmp = *this;
0156       ++*this;
0157       return __tmp;
0158     } else if constexpr (requires(_Iter& __i) {
0159                            { *__i++ } -> __can_reference;
0160                          } || !__can_use_postfix_proxy<_Iter>) {
0161       return std::__unchecked_get<_Iter>(__hold_)++;
0162     } else {
0163       auto __p = __postfix_proxy{**this};
0164       ++*this;
0165       return __p;
0166     }
0167   }
0168
0169   template <class _I2, sentinel_for<_Iter> _S2>
0170     requires sentinel_for<_Sent, _I2>
0171   _LIBCPP_HIDE_FROM_ABI friend constexpr bool
0172   operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
0173     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0174         !__x.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator");
0175     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0176         !__y.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator");
0177
0178     auto __x_index = __x.__hold_.index();
0179     auto __y_index = __y.__hold_.index();
0180
0181     if (__x_index == __y_index)
0182       return true;
0183
0184     if (__x_index == 0)
0185       return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_S2>(__y.__hold_);
0186
0187     return std::__unchecked_get<_Sent>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_);
0188   }
0189
0190   template <class _I2, sentinel_for<_Iter> _S2>
0191     requires sentinel_for<_Sent, _I2> && equality_comparable_with<_Iter, _I2>
0192   _LIBCPP_HIDE_FROM_ABI friend constexpr bool
0193   operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
0194     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0195         !__x.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator");
0196     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0197         !__y.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator");
0198
0199     auto __x_index = __x.__hold_.index();
0200     auto __y_index = __y.__hold_.index();
0201
0202     if (__x_index == 1 && __y_index == 1)
0203       return true;
0204
0205     if (__x_index == 0 && __y_index == 0)
0206       return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_);
0207
0208     if (__x_index == 0)
0209       return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_S2>(__y.__hold_);
0210
0211     return std::__unchecked_get<_Sent>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_);
0212   }
0213
0214   template <sized_sentinel_for<_Iter> _I2, sized_sentinel_for<_Iter> _S2>
0215     requires sized_sentinel_for<_Sent, _I2>
0216   _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_I2>
0217   operator-(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
0218     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0219         !__x.__hold_.valueless_by_exception(), "Attempted to subtract from a valueless common_iterator");
0220     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0221         !__y.__hold_.valueless_by_exception(), "Attempted to subtract a valueless common_iterator");
0222
0223     auto __x_index = __x.__hold_.index();
0224     auto __y_index = __y.__hold_.index();
0225
0226     if (__x_index == 1 && __y_index == 1)
0227       return 0;
0228
0229     if (__x_index == 0 && __y_index == 0)
0230       return std::__unchecked_get<_Iter>(__x.__hold_) - std::__unchecked_get<_I2>(__y.__hold_);
0231
0232     if (__x_index == 0)
0233       return std::__unchecked_get<_Iter>(__x.__hold_) - std::__unchecked_get<_S2>(__y.__hold_);
0234
0235     return std::__unchecked_get<_Sent>(__x.__hold_) - std::__unchecked_get<_I2>(__y.__hold_);
0236   }
0237
0238   _LIBCPP_HIDE_FROM_ABI friend constexpr iter_rvalue_reference_t<_Iter>
0239   iter_move(const common_iterator& __i) noexcept(noexcept(ranges::iter_move(std::declval<const _Iter&>())))
0240     requires input_iterator<_Iter>
0241   {
0242     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0243         std::holds_alternative<_Iter>(__i.__hold_), "Attempted to iter_move a non-dereferenceable common_iterator");
0244     return ranges::iter_move(std::__unchecked_get<_Iter>(__i.__hold_));
0245   }
0246
0247   template <indirectly_swappable<_Iter> _I2, class _S2>
0248   _LIBCPP_HIDE_FROM_ABI friend constexpr void
0249   iter_swap(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) noexcept(
0250       noexcept(ranges::iter_swap(std::declval<const _Iter&>(), std::declval<const _I2&>()))) {
0251     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0252         std::holds_alternative<_Iter>(__x.__hold_), "Attempted to iter_swap a non-dereferenceable common_iterator");
0253     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0254         std::holds_alternative<_I2>(__y.__hold_), "Attempted to iter_swap a non-dereferenceable common_iterator");
0255     return ranges::iter_swap(std::__unchecked_get<_Iter>(__x.__hold_), std::__unchecked_get<_I2>(__y.__hold_));
0256   }
0257 };
0258
0259 template <class _Iter, class _Sent>
0260 struct incrementable_traits<common_iterator<_Iter, _Sent>> {
0261   using difference_type = iter_difference_t<_Iter>;
0262 };
0263
0264 template <class _Iter>
0265 concept __denotes_forward_iter = requires {
0266   typename iterator_traits<_Iter>::iterator_category;
0267 } && derived_from<typename iterator_traits<_Iter>::iterator_category, forward_iterator_tag>;
0268
0269 template <class _Iter, class _Sent>
0270 concept __common_iter_has_ptr_op = requires(const common_iterator<_Iter, _Sent>& __a) { __a.operator->(); };
0271
0272 template <class, class>
0273 struct __arrow_type_or_void {
0274   using type = void;
0275 };
0276
0277 template <class _Iter, class _Sent>
0278   requires __common_iter_has_ptr_op<_Iter, _Sent>
0279 struct __arrow_type_or_void<_Iter, _Sent> {
0280   using type = decltype(std::declval<const common_iterator<_Iter, _Sent>&>().operator->());
0281 };
0282
0283 template <input_iterator _Iter, class _Sent>
0284 struct iterator_traits<common_iterator<_Iter, _Sent>> {
0285   using iterator_concept  = _If<forward_iterator<_Iter>, forward_iterator_tag, input_iterator_tag>;
0286   using iterator_category = _If<__denotes_forward_iter<_Iter>, forward_iterator_tag, input_iterator_tag>;
0287   using pointer           = typename __arrow_type_or_void<_Iter, _Sent>::type;
0288   using value_type        = iter_value_t<_Iter>;
0289   using difference_type   = iter_difference_t<_Iter>;
0290   using reference         = iter_reference_t<_Iter>;
0291 };
0292
0293 #endif // _LIBCPP_STD_VER >= 20
0294
0295 _LIBCPP_END_NAMESPACE_STD
0296
0297 _LIBCPP_POP_MACROS
0298
0299 #endif // _LIBCPP___CXX03___ITERATOR_COMMON_ITERATOR_H