libcxx/include/__iterator/common_iterator.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_COMMON_ITERATOR_H
  11 #define _LIBCPP___ITERATOR_COMMON_ITERATOR_H
  12
  13 #include <__assert>
  14 #include <__concepts/assignable.h>
  15 #include <__concepts/constructible.h>
  16 #include <__concepts/convertible_to.h>
  17 #include <__concepts/copyable.h>
  18 #include <__concepts/derived_from.h>
  19 #include <__concepts/equality_comparable.h>
  20 #include <__concepts/same_as.h>
  21 #include <__config>
  22 #include <__iterator/concepts.h>
  23 #include <__iterator/incrementable_traits.h>
  24 #include <__iterator/iter_move.h>
  25 #include <__iterator/iter_swap.h>
  26 #include <__iterator/iterator_traits.h>
  27 #include <__iterator/readable_traits.h>
  28 #include <__memory/addressof.h>
  29 #include <__type_traits/conditional.h>
  30 #include <__type_traits/is_pointer.h>
  31 #include <__utility/declval.h>
  32 #include <variant>
  33
  34 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  35 #  pragma GCC system_header
  36 #endif
  37
  38 _LIBCPP_PUSH_MACROS
  39 #include <__undef_macros>
  40
  41 _LIBCPP_BEGIN_NAMESPACE_STD
  42
  43 #if _LIBCPP_STD_VER >= 20
  44
  45 template <class _Iter>
  46 concept __can_use_postfix_proxy =
  47     constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> && move_constructible<iter_value_t<_Iter>>;
  48
  49 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
  50   requires(!same_as<_Iter, _Sent> && copyable<_Iter>)
  51 class common_iterator {
  52   struct __proxy {
  53     _LIBCPP_HIDE_FROM_ABI constexpr const iter_value_t<_Iter>* operator->() const noexcept {
  54       return std::addressof(__value_);
  55     }
  56     iter_value_t<_Iter> __value_;
  57   };
  58
  59   struct __postfix_proxy {
  60     _LIBCPP_HIDE_FROM_ABI constexpr const iter_value_t<_Iter>& operator*() const noexcept { return __value_; }
  61     iter_value_t<_Iter> __value_;
  62   };
  63
  64   variant<_Iter, _Sent> __hold_;
  65   template <input_or_output_iterator _OtherIter, sentinel_for<_OtherIter> _OtherSent>
  66     requires(!same_as<_OtherIter, _OtherSent> && copyable<_OtherIter>)
  67   friend class common_iterator;
  68
  69 public:
  70   _LIBCPP_HIDE_FROM_ABI common_iterator()
  71     requires default_initializable<_Iter>
  72   = default;
  73
  74   _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(_Iter __i) : __hold_(in_place_type<_Iter>, std::move(__i)) {}
  75   _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(_Sent __s) : __hold_(in_place_type<_Sent>, std::move(__s)) {}
  76
  77   template <class _I2, class _S2>
  78     requires convertible_to<const _I2&, _Iter> && convertible_to<const _S2&, _Sent>
  79   _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(const common_iterator<_I2, _S2>& __other)
  80       : __hold_([&]() -> variant<_Iter, _Sent> {
  81           _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
  82               !__other.__hold_.valueless_by_exception(), "Attempted to construct from a valueless common_iterator");
  83           if (__other.__hold_.index() == 0)
  84             return variant<_Iter, _Sent>{in_place_index<0>, std::__unchecked_get<0>(__other.__hold_)};
  85           return variant<_Iter, _Sent>{in_place_index<1>, std::__unchecked_get<1>(__other.__hold_)};
  86         }()) {}
  87
  88   template <class _I2, class _S2>
  89     requires convertible_to<const _I2&, _Iter> && convertible_to<const _S2&, _Sent> &&
  90              assignable_from<_Iter&, const _I2&> && assignable_from<_Sent&, const _S2&>
  91   _LIBCPP_HIDE_FROM_ABI common_iterator& operator=(const common_iterator<_I2, _S2>& __other) {
  92     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
  93         !__other.__hold_.valueless_by_exception(), "Attempted to assign from a valueless common_iterator");
  94
  95     auto __idx       = __hold_.index();
  96     auto __other_idx = __other.__hold_.index();
  97
  98     // If they're the same index, just assign.
  99     if (__idx == 0 && __other_idx == 0)
 100       std::__unchecked_get<0>(__hold_) = std::__unchecked_get<0>(__other.__hold_);
 101     else if (__idx == 1 && __other_idx == 1)
 102       std::__unchecked_get<1>(__hold_) = std::__unchecked_get<1>(__other.__hold_);
 103
 104     // Otherwise replace with the oposite element.
 105     else if (__other_idx == 1)
 106       __hold_.template emplace<1>(std::__unchecked_get<1>(__other.__hold_));
 107     else if (__other_idx == 0)
 108       __hold_.template emplace<0>(std::__unchecked_get<0>(__other.__hold_));
 109
 110     return *this;
 111   }
 112
 113   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() {
 114     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 115         std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator");
 116     return *std::__unchecked_get<_Iter>(__hold_);
 117   }
 118
 119   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const
 120     requires __dereferenceable<const _Iter>
 121   {
 122     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 123         std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator");
 124     return *std::__unchecked_get<_Iter>(__hold_);
 125   }
 126
 127   template <class _I2 = _Iter>
 128   _LIBCPP_HIDE_FROM_ABI auto operator->() const
 129     requires indirectly_readable<const _I2> && (requires(const _I2& __i) {
 130                __i.operator->();
 131              } || is_reference_v<iter_reference_t<_I2>> || constructible_from<iter_value_t<_I2>, iter_reference_t<_I2>>)
 132   {
 133     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 134         std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator");
 135     if constexpr (is_pointer_v<_Iter> || requires(const _Iter& __i) { __i.operator->(); }) {
 136       return std::__unchecked_get<_Iter>(__hold_);
 137     } else if constexpr (is_reference_v<iter_reference_t<_Iter>>) {
 138       auto&& __tmp = *std::__unchecked_get<_Iter>(__hold_);
 139       return std::addressof(__tmp);
 140     } else {
 141       return __proxy{*std::__unchecked_get<_Iter>(__hold_)};
 142     }
 143   }
 144
 145   _LIBCPP_HIDE_FROM_ABI common_iterator& operator++() {
 146     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 147         std::holds_alternative<_Iter>(__hold_), "Attempted to increment a non-dereferenceable common_iterator");
 148     ++std::__unchecked_get<_Iter>(__hold_);
 149     return *this;
 150   }
 151
 152   _LIBCPP_HIDE_FROM_ABI decltype(auto) operator++(int) {
 153     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 154         std::holds_alternative<_Iter>(__hold_), "Attempted to increment a non-dereferenceable common_iterator");
 155     if constexpr (forward_iterator<_Iter>) {
 156       auto __tmp = *this;
 157       ++*this;
 158       return __tmp;
 159     } else if constexpr (requires(_Iter& __i) {
 160                            { *__i++ } -> __can_reference;
 161                          } || !__can_use_postfix_proxy<_Iter>) {
 162       return std::__unchecked_get<_Iter>(__hold_)++;
 163     } else {
 164       auto __p = __postfix_proxy{**this};
 165       ++*this;
 166       return __p;
 167     }
 168   }
 169
 170   template <class _I2, sentinel_for<_Iter> _S2>
 171     requires sentinel_for<_Sent, _I2>
 172   _LIBCPP_HIDE_FROM_ABI friend constexpr bool
 173   operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
 174     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 175         !__x.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator");
 176     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 177         !__y.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator");
 178
 179     auto __x_index = __x.__hold_.index();
 180     auto __y_index = __y.__hold_.index();
 181
 182     if (__x_index == __y_index)
 183       return true;
 184
 185     if (__x_index == 0)
 186       return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_S2>(__y.__hold_);
 187
 188     return std::__unchecked_get<_Sent>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_);
 189   }
 190
 191   template <class _I2, sentinel_for<_Iter> _S2>
 192     requires sentinel_for<_Sent, _I2> && equality_comparable_with<_Iter, _I2>
 193   _LIBCPP_HIDE_FROM_ABI friend constexpr bool
 194   operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
 195     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 196         !__x.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator");
 197     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 198         !__y.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator");
 199
 200     auto __x_index = __x.__hold_.index();
 201     auto __y_index = __y.__hold_.index();
 202
 203     if (__x_index == 1 && __y_index == 1)
 204       return true;
 205
 206     if (__x_index == 0 && __y_index == 0)
 207       return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_);
 208
 209     if (__x_index == 0)
 210       return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_S2>(__y.__hold_);
 211
 212     return std::__unchecked_get<_Sent>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_);
 213   }
 214
 215   template <sized_sentinel_for<_Iter> _I2, sized_sentinel_for<_Iter> _S2>
 216     requires sized_sentinel_for<_Sent, _I2>
 217   _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_I2>
 218   operator-(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
 219     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 220         !__x.__hold_.valueless_by_exception(), "Attempted to subtract from a valueless common_iterator");
 221     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 222         !__y.__hold_.valueless_by_exception(), "Attempted to subtract a valueless common_iterator");
 223
 224     auto __x_index = __x.__hold_.index();
 225     auto __y_index = __y.__hold_.index();
 226
 227     if (__x_index == 1 && __y_index == 1)
 228       return 0;
 229
 230     if (__x_index == 0 && __y_index == 0)
 231       return std::__unchecked_get<_Iter>(__x.__hold_) - std::__unchecked_get<_I2>(__y.__hold_);
 232
 233     if (__x_index == 0)
 234       return std::__unchecked_get<_Iter>(__x.__hold_) - std::__unchecked_get<_S2>(__y.__hold_);
 235
 236     return std::__unchecked_get<_Sent>(__x.__hold_) - std::__unchecked_get<_I2>(__y.__hold_);
 237   }
 238
 239   _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)
 240   iter_move(const common_iterator& __i) noexcept(noexcept(ranges::iter_move(std::declval<const _Iter&>())))
 241     requires input_iterator<_Iter>
 242   {
 243     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 244         std::holds_alternative<_Iter>(__i.__hold_), "Attempted to iter_move a non-dereferenceable common_iterator");
 245     return ranges::iter_move(std::__unchecked_get<_Iter>(__i.__hold_));
 246   }
 247
 248   template <indirectly_swappable<_Iter> _I2, class _S2>
 249   _LIBCPP_HIDE_FROM_ABI friend constexpr void
 250   iter_swap(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) noexcept(
 251       noexcept(ranges::iter_swap(std::declval<const _Iter&>(), std::declval<const _I2&>()))) {
 252     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 253         std::holds_alternative<_Iter>(__x.__hold_), "Attempted to iter_swap a non-dereferenceable common_iterator");
 254     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 255         std::holds_alternative<_I2>(__y.__hold_), "Attempted to iter_swap a non-dereferenceable common_iterator");
 256     return ranges::iter_swap(std::__unchecked_get<_Iter>(__x.__hold_), std::__unchecked_get<_I2>(__y.__hold_));
 257   }
 258 };
 259
 260 template <class _Iter, class _Sent>
 261 struct incrementable_traits<common_iterator<_Iter, _Sent>> {
 262   using difference_type = iter_difference_t<_Iter>;
 263 };
 264
 265 template <class _Iter>
 266 concept __denotes_forward_iter = requires {
 267   typename iterator_traits<_Iter>::iterator_category;
 268 } && derived_from<typename iterator_traits<_Iter>::iterator_category, forward_iterator_tag>;
 269
 270 template <class _Iter, class _Sent>
 271 concept __common_iter_has_ptr_op = requires(const common_iterator<_Iter, _Sent>& __a) { __a.operator->(); };
 272
 273 template <class, class>
 274 struct __arrow_type_or_void {
 275   using type = void;
 276 };
 277
 278 template <class _Iter, class _Sent>
 279   requires __common_iter_has_ptr_op<_Iter, _Sent>
 280 struct __arrow_type_or_void<_Iter, _Sent> {
 281   using type = decltype(std::declval<const common_iterator<_Iter, _Sent>&>().operator->());
 282 };
 283
 284 template <input_iterator _Iter, class _Sent>
 285 struct iterator_traits<common_iterator<_Iter, _Sent>> {
 286   using iterator_concept  = _If<forward_iterator<_Iter>, forward_iterator_tag, input_iterator_tag>;
 287   using iterator_category = _If<__denotes_forward_iter<_Iter>, forward_iterator_tag, input_iterator_tag>;
 288   using pointer           = typename __arrow_type_or_void<_Iter, _Sent>::type;
 289   using value_type        = iter_value_t<_Iter>;
 290   using difference_type   = iter_difference_t<_Iter>;
 291   using reference         = iter_reference_t<_Iter>;
 292 };
 293
 294 #endif // _LIBCPP_STD_VER >= 20
 295
 296 _LIBCPP_END_NAMESPACE_STD
 297
 298 _LIBCPP_POP_MACROS
 299
 300 #endif // _LIBCPP___ITERATOR_COMMON_ITERATOR_H