diff --git a/libcxx/include/__iterator/common_iterator.h b/libcxx/include/__iterator/common_iterator.h --- a/libcxx/include/__iterator/common_iterator.h +++ b/libcxx/include/__iterator/common_iterator.h @@ -28,6 +28,7 @@ #if !defined(_LIBCPP_HAS_NO_RANGES) +// REVIEW-NOTE: This is *not* part of the transform_view patch and will be added by a *separate* PR. template concept indirectly_swappable = indirectly_readable<_I1> && @@ -38,63 +39,191 @@ ranges::iter_swap(i2, i1); ranges::iter_swap(i2, i2); }; +// END-REVIEW-NOTE. + +struct default_sentinel_t {}; template _Sent> requires (!same_as<_Iter, _Sent> && copyable<_Iter>) class common_iterator { - union { - _Iter __iter; - _Sent __sent; + union _Hold { + _Iter __iter; // __index == 0; + _Sent __sent; // __index == 1; + + _Hold() = default; + constexpr _Hold(_Iter __iter) : __iter(_VSTD::move(__iter)) {} + constexpr _Hold(_Sent __sent) : __sent(_VSTD::move(__sent)) {} + } __u; + bool __index; + + class __proxy { + friend common_iterator; + + iter_value_t<_Iter> __value; + constexpr __proxy(iter_reference_t<_Iter>&& __x) + : __value(__x) {} + + public: + constexpr const iter_value_t<_Iter>* operator->() const { + return _VSTD::addressof(__value); + } + }; + + class __postfix_proxy { + friend common_iterator; + + iter_value_t<_Iter> __value; + constexpr __postfix_proxy(iter_reference_t<_Iter>&& __x) + : __value(__x) {} + + public: + constexpr const iter_value_t<_Iter>& operator*() const { + return __value; + } }; public: common_iterator() = default; - constexpr common_iterator(_Iter __i); - constexpr common_iterator(_Sent __s); + constexpr common_iterator(_Iter __i) : __u(_VSTD::move(__i)), __index(false) {} + constexpr common_iterator(_Sent __s) : __u(_VSTD::move(__s)), __index(true ) {} template requires convertible_to && convertible_to - common_iterator(const common_iterator<_I2, _S2>& __other); + constexpr common_iterator(const common_iterator<_I2, _S2>& __other) + : __u(__other.__u), __index(__other.__index) {} template requires convertible_to && convertible_to && assignable_from && assignable_from - common_iterator& operator=(const common_iterator<_I2, _S2>& __other); + constexpr common_iterator& operator=(const common_iterator<_I2, _S2>& __other) { + __u = __other.__u; + __index = __other.__index; + } + + constexpr decltype(auto) operator*() { return *__u.__iter; } + constexpr decltype(auto) operator*() const + requires __dereferenceable + { return *__u.__iter; } - decltype(auto) operator*(); - decltype(auto) operator*() const - requires __dereferenceable; - decltype(auto) operator->() const + constexpr decltype(auto) operator->() const requires indirectly_readable && (requires(const _Iter& __i) { __i.operator->(); } || is_reference_v> || - constructible_from, iter_reference_t<_Iter>>); - - common_iterator& operator++(); - decltype(auto) operator++(int); + constructible_from, iter_reference_t<_Iter>>) { + if constexpr (is_pointer_v<_Iter> || requires(const _Iter& __i) { __i.operator->(); }) { + return __u.__iter; + } else if constexpr (is_reference_v>) { + auto&& __tmp = *__u.__iter; + return _VSTD::addressof(__tmp); + } else { + return __proxy(*__u.__iter); + } + } + + constexpr common_iterator& operator++() { ++__u.__iter; return *this; } + constexpr decltype(auto) operator++(int) { + if constexpr (forward_iterator<_Iter>) { + auto __tmp = *this; + ++*this; + return __tmp; + } else if constexpr (requires (_Iter& __i) { { *__i++ } -> __referenceable; } || + !constructible_from, iter_reference_t<_Iter>>) { + return __u.__iter++; + } else { + __postfix_proxy __p(*this); + ++*this; + return __p; + } + } template _S2> requires sentinel_for<_Sent, _I2> - friend bool operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y); + friend constexpr bool operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) { + if (__x.__index == __y.__index) + return true; + + if (__x.__index == 0) + return __x.__u.__iter == __y.__u.__sent; + + return __x.__u.__sent == __y.__u.__iter; + } template _S2> requires sentinel_for<_Sent, _I2> && equality_comparable_with<_Iter, _I2> - friend bool operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y); + friend constexpr bool operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) { + if (__x.__index && __y.__index) + return true; + + if (__x.__index == 0 && __y.__index == 0) + return __x.__u.__iter == __y.__u.__iter; + + if (__x.__index == 0) + return __x.__u.__iter == __y.__u.__sent; + + return __x.__u.__sent == __y.__u.__iter; + } template _I2, sized_sentinel_for<_Iter> _S2> requires sized_sentinel_for<_Sent, _I2> - friend iter_difference_t<_I2> operator-(const common_iterator& __x, const common_iterator<_I2, _S2>& __y); + friend constexpr iter_difference_t<_I2> operator-(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) { + if (__x.__index && __y.__index) + return 0; - friend iter_rvalue_reference_t<_Iter> iter_move(const common_iterator& __i) + if (__x.__index == 0 && __y.__index == 0) + return __x.__u.__iter - __y.__u.__iter; + + if (__x.__index == 0) + return __x.__u.__iter - __y.__u.__sent; + + return __x.__u.__sent - __y.__u.__iter; + } + + friend constexpr iter_rvalue_reference_t<_Iter> iter_move(const common_iterator& __i) noexcept(noexcept(ranges::iter_move(declval()))) - requires input_iterator<_Iter>; + requires input_iterator<_Iter> + { return ranges::iter_move(__i.__u.__iter); } template _I2, class _S2> - friend void iter_swap(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) - noexcept(noexcept(ranges::iter_swap(declval(), declval()))); + friend constexpr void iter_swap(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) + noexcept(noexcept(ranges::iter_swap(declval(), declval()))) + { return ranges::iter_swap(__x.__u.__iter, __y.__u.__iter); } }; +template +struct incrementable_traits> { + using difference_type = iter_difference_t<_Iter>; +}; + +template +concept __denotes_forward_iter = + requires { + typename iterator_traits<_Iter>::iterator_category; + } && + derived_from::iterator_category, forward_iterator_tag>; + +template +concept __common_iter_has_ptr_op = requires(const common_iterator<_Iter, _Sent> __a) { + __a.operator->(); +}; + +template +struct iterator_traits> { + using iterator_concept = conditional_t, + forward_iterator_tag, + input_iterator_tag>; + using iterator_category = conditional_t<__denotes_forward_iter<_Iter>, + forward_iterator_tag, + input_iterator_tag>; + using pointer = conditional_t<__common_iter_has_ptr_op<_Iter, _Sent>, + decltype(declval>().operator->()), + void>; + using value_type = iter_value_t<_Iter>; + using difference_type = iter_difference_t<_Iter>; + using reference = iter_reference_t<_Iter>; +}; + + #endif // !defined(_LIBCPP_HAS_NO_RANGES) _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/test/std/iterators/predef.iterators/iterators.common/common_iterator.pass.cpp b/libcxx/test/std/iterators/predef.iterators/iterators.common/common_iterator.pass.cpp --- a/libcxx/test/std/iterators/predef.iterators/iterators.common/common_iterator.pass.cpp +++ b/libcxx/test/std/iterators/predef.iterators/iterators.common/common_iterator.pass.cpp @@ -18,8 +18,409 @@ #include #include "test_macros.h" +#include "test_iterators.h" + +template +class simple_iterator +{ + It it_; + +public: + typedef std::input_iterator_tag iterator_category; + typedef typename std::iterator_traits::value_type value_type; + typedef typename std::iterator_traits::difference_type difference_type; + typedef It pointer; + typedef typename std::iterator_traits::reference reference; + + constexpr It base() const {return it_;} + + simple_iterator() = default; + explicit constexpr simple_iterator(It it) : it_(it) {} + + constexpr reference operator*() const {return *it_;} + + constexpr simple_iterator& operator++() {++it_; return *this;} + constexpr simple_iterator operator++(int) + {simple_iterator tmp(*this); ++(*this); return tmp;} +}; + +template +class value_iterator +{ + It it_; + +public: + typedef std::input_iterator_tag iterator_category; + typedef typename std::iterator_traits::value_type value_type; + typedef typename std::iterator_traits::difference_type difference_type; + typedef It pointer; + typedef typename std::iterator_traits::reference reference; + + constexpr It base() const {return it_;} + + value_iterator() = default; + explicit constexpr value_iterator(It it) : it_(it) {} + + constexpr value_type operator*() const {return *it_;} + + constexpr value_iterator& operator++() {++it_; return *this;} + constexpr value_iterator operator++(int) + {value_iterator tmp(*this); ++(*this); return tmp;} +}; + + +template +struct sentienl_type { + T base; + + template + friend constexpr bool operator==(const sentienl_type& lhs, const U& rhs) { return lhs.base == rhs.base(); } + template + friend constexpr bool operator==(const U& lhs, const sentienl_type& rhs) { return lhs.base() == rhs.base; } +}; + +template +struct sized_sentienl_type { + T base; + + template + friend constexpr bool operator==(const sized_sentienl_type& lhs, const U& rhs) { return lhs.base - rhs.base(); } + template + friend constexpr bool operator==(const U& lhs, const sized_sentienl_type& rhs) { return lhs.base() - rhs.base; } + template + friend constexpr auto operator- (const sized_sentienl_type& lhs, const U& rhs) { return lhs.base - rhs.base(); } + template + friend constexpr auto operator- (const U& lhs, const sized_sentienl_type& rhs) { return lhs.base() - rhs.base; } +}; + +template +concept ValidCommonIterator = requires { + typename std::common_iterator; +}; + +constexpr void testIteratorTraits() { + { + using Iter = simple_iterator; + using CommonIter = std::common_iterator>; + using IterTraits = std::iterator_traits; + + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + } + { + using Iter = value_iterator; + using CommonIter = std::common_iterator>; + using IterTraits = std::iterator_traits; + + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + // Note: IterTraits::pointer == __proxy. + static_assert(!std::same_as); + static_assert(std::same_as); + } + { + using Iter = cpp17_input_iterator; + using CommonIter = std::common_iterator>; + using IterTraits = std::iterator_traits; + + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); // TODO: is this right? + static_assert(std::same_as); + } + { + using Iter = forward_iterator; + using CommonIter = std::common_iterator>; + using IterTraits = std::iterator_traits; + + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + } + { + using Iter = random_access_iterator; + using CommonIter = std::common_iterator>; + using IterTraits = std::iterator_traits; + + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + } +} + +constexpr void testCtor() { + int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8}; + + static_assert(std::is_default_constructible_v>>); + + // Not copyable: + static_assert(!ValidCommonIterator, sentienl_type>); + // Same iter and sent: + static_assert(!ValidCommonIterator, cpp17_input_iterator>); + + { + auto iter1 = cpp17_input_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sentienl_type{buffer + 8}); + + assert(*iter1 == 1); + assert(*commonIter1 == 1); + assert(commonIter1 != commonSent1); + } + { + auto iter1 = forward_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sentienl_type{buffer + 8}); + + assert(*iter1 == 1); + assert(*commonIter1 == 1); + assert(commonIter1 != commonSent1); + } + { + auto iter1 = random_access_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sentienl_type{buffer + 8}); + + assert(*iter1 == 1); + assert(*commonIter1 == 1); + assert(commonIter1 != commonSent1); + } +} + +constexpr void testMembers() { + int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8}; + + { + auto iter1 = simple_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sentienl_type{buffer + 8}); + + const auto iter2 = simple_iterator(buffer); + const auto commonIter2 = std::common_iterator>(iter1); + const auto commonSent2 = std::common_iterator>(sentienl_type{buffer + 8}); + + assert(*iter1 == 1); + assert(*commonIter1 == 1); + assert(commonIter1 != commonSent1); + assert(commonIter1.operator->() == buffer); + + assert(*iter2 == 1); + assert(*commonIter2 == 1); + assert(commonIter2 != commonSent2); + assert(commonIter2.operator->() == buffer); + + assert(*(commonIter1++) == 1); + assert(*commonIter1 == 2); + assert(*(++commonIter1) == 3); + assert(*commonIter1 == 3); + + for (auto i = 3; commonIter1 != commonSent1; ++i) { + assert(*(commonIter1++) == i); + } + assert(commonIter1 == commonSent1); + } + { + auto iter1 = value_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sentienl_type{buffer + 8}); + + const auto iter2 = value_iterator(buffer); + const auto commonIter2 = std::common_iterator>(iter1); + const auto commonSent2 = std::common_iterator>(sentienl_type{buffer + 8}); + + assert(*iter1 == 1); + assert(*commonIter1 == 1); + assert(commonIter1 != commonSent1); + assert(*commonIter1.operator->().operator->() == 1); + + assert(*iter2 == 1); + assert(*commonIter2 == 1); + assert(commonIter2 != commonSent2); + assert(*commonIter2.operator->().operator->() == 1); + + assert(*(commonIter1++) == 1); + assert(*commonIter1 == 2); + assert(*(++commonIter1) == 3); + assert(*commonIter1 == 3); + + for (auto i = 3; commonIter1 != commonSent1; ++i) { + assert(*(commonIter1++) == i); + } + assert(commonIter1 == commonSent1); + } + { + auto iter1 = cpp17_input_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sentienl_type{buffer + 8}); + + const auto iter2 = cpp17_input_iterator(buffer); + const auto commonIter2 = std::common_iterator>(iter1); + const auto commonSent2 = std::common_iterator>(sentienl_type{buffer + 8}); + + assert(*iter1 == 1); + assert(*commonIter1 == 1); + assert(commonIter1 != commonSent1); + assert(commonIter1.operator->().base() == buffer); + + assert(*iter2 == 1); + assert(*commonIter2 == 1); + assert(commonIter2 != commonSent2); + assert(commonIter2.operator->().base() == buffer); + + assert(*(commonIter1++) == 1); + assert(*commonIter1 == 2); + assert(*(++commonIter1) == 3); + assert(*commonIter1 == 3); + + for (auto i = 3; commonIter1 != commonSent1; ++i) { + assert(*(commonIter1++) == i); + } + assert(commonIter1 == commonSent1); + } + { + auto iter1 = forward_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sentienl_type{buffer + 8}); + + const auto iter2 = forward_iterator(buffer); + const auto commonIter2 = std::common_iterator>(iter1); + const auto commonSent2 = std::common_iterator>(sentienl_type{buffer + 8}); + + assert(*iter1 == 1); + assert(*commonIter1 == 1); + assert(commonIter1 != commonSent1); + assert(commonIter1.operator->().base() == buffer); + + assert(*iter2 == 1); + assert(*commonIter2 == 1); + assert(commonIter2 != commonSent2); + assert(commonIter2.operator->().base() == buffer); + + assert(*(commonIter1++) == 1); + assert(*commonIter1 == 2); + assert(*(++commonIter1) == 3); + assert(*commonIter1 == 3); + + for (auto i = 3; commonIter1 != commonSent1; ++i) { + assert(*(commonIter1++) == i); + } + assert(commonIter1 == commonSent1); + } + { + auto iter1 = random_access_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sentienl_type{buffer + 8}); + + const auto iter2 = random_access_iterator(buffer); + const auto commonIter2 = std::common_iterator>(iter1); + const auto commonSent2 = std::common_iterator>(sentienl_type{buffer + 8}); + + assert(*iter1 == 1); + assert(*commonIter1 == 1); + assert(commonIter1 != commonSent1); + assert(commonIter1.operator->().base() == buffer); + + assert(*iter2 == 1); + assert(*commonIter2 == 1); + assert(commonIter2 != commonSent2); + assert(commonIter2.operator->().base() == buffer); + + assert(*(commonIter1++) == 1); + assert(*commonIter1 == 2); + assert(*(++commonIter1) == 3); + assert(*commonIter1 == 3); + + for (auto i = 3; commonIter1 != commonSent1; ++i) { + assert(*(commonIter1++) == i); + } + assert(commonIter1 == commonSent1); + } + { + auto iter1 = random_access_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonSent1 = std::common_iterator>(sized_sentienl_type{buffer + 8}); + assert(commonIter1 - commonSent1 == -8); + assert(commonSent1 - commonIter1 == 8); + assert(commonIter1 - commonIter1 == 0); + assert(commonSent1 - commonSent1 == 0); + } +} + +constexpr void testCust() { + int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8}; + + { + auto iter1 = cpp17_input_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonIter2 = std::common_iterator>(iter1); + for (auto i = 0; i < 4; ++i) ++commonIter2; + assert(*commonIter2 == 5); + std::ranges::iter_swap(commonIter1, commonIter2); + assert(*commonIter1 == 5); + assert(*commonIter2 == 1); + std::ranges::iter_swap(commonIter2, commonIter1); + } + { + auto iter1 = forward_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonIter2 = std::common_iterator>(iter1); + for (auto i = 0; i < 4; ++i) ++commonIter2; + assert(*commonIter2 == 5); + std::ranges::iter_swap(commonIter1, commonIter2); + assert(*commonIter1 == 5); + assert(*commonIter2 == 1); + std::ranges::iter_swap(commonIter2, commonIter1); + } + { + auto iter1 = random_access_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + auto commonIter2 = std::common_iterator>(iter1); + for (auto i = 0; i < 4; ++i) ++commonIter2; + assert(*commonIter2 == 5); + std::ranges::iter_swap(commonIter1, commonIter2); + assert(*commonIter1 == 5); + assert(*commonIter2 == 1); + std::ranges::iter_swap(commonIter2, commonIter1); + } + { + auto iter1 = cpp17_input_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + assert(std::ranges::iter_move(commonIter1) == 1); + ASSERT_SAME_TYPE(decltype(std::ranges::iter_move(commonIter1)), int&&); + } + { + auto iter1 = forward_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + assert(std::ranges::iter_move(commonIter1) == 1); + ASSERT_SAME_TYPE(decltype(std::ranges::iter_move(commonIter1)), int&&); + } + { + auto iter1 = random_access_iterator(buffer); + auto commonIter1 = std::common_iterator>(iter1); + assert(std::ranges::iter_move(commonIter1) == 1); + ASSERT_SAME_TYPE(decltype(std::ranges::iter_move(commonIter1)), int&&); + } +} constexpr bool test() { + testIteratorTraits(); + testCtor(); + testMembers(); + testCust(); return true; }