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