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