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