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