430 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___RANGES_JOIN_VIEW_H11#define _LIBCPP___RANGES_JOIN_VIEW_H12 13#include <__concepts/constructible.h>14#include <__concepts/convertible_to.h>15#include <__concepts/copyable.h>16#include <__concepts/derived_from.h>17#include <__concepts/equality_comparable.h>18#include <__config>19#include <__iterator/concepts.h>20#include <__iterator/iter_move.h>21#include <__iterator/iter_swap.h>22#include <__iterator/iterator_traits.h>23#include <__iterator/iterator_with_data.h>24#include <__iterator/segmented_iterator.h>25#include <__memory/addressof.h>26#include <__ranges/access.h>27#include <__ranges/all.h>28#include <__ranges/concepts.h>29#include <__ranges/empty.h>30#include <__ranges/non_propagating_cache.h>31#include <__ranges/range_adaptor.h>32#include <__ranges/view_interface.h>33#include <__type_traits/common_type.h>34#include <__type_traits/maybe_const.h>35#include <__utility/as_lvalue.h>36#include <__utility/empty.h>37#include <__utility/forward.h>38#include <optional>39 40#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)41# pragma GCC system_header42#endif43 44_LIBCPP_PUSH_MACROS45#include <__undef_macros>46 47_LIBCPP_BEGIN_NAMESPACE_STD48 49#if _LIBCPP_STD_VER >= 2050 51namespace ranges {52template <class>53struct __join_view_iterator_category {};54 55template <class _View>56 requires is_reference_v<range_reference_t<_View>> && forward_range<_View> && forward_range<range_reference_t<_View>>57struct __join_view_iterator_category<_View> {58 using _OuterC _LIBCPP_NODEBUG = typename iterator_traits<iterator_t<_View>>::iterator_category;59 using _InnerC _LIBCPP_NODEBUG = typename iterator_traits<iterator_t<range_reference_t<_View>>>::iterator_category;60 61 using iterator_category =62 _If< derived_from<_OuterC, bidirectional_iterator_tag> && derived_from<_InnerC, bidirectional_iterator_tag> &&63 common_range<range_reference_t<_View>>,64 bidirectional_iterator_tag,65 _If< derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>,66 forward_iterator_tag,67 input_iterator_tag > >;68};69 70template <input_range _View>71 requires view<_View> && input_range<range_reference_t<_View>>72class join_view : public view_interface<join_view<_View>> {73private:74 using _InnerRange _LIBCPP_NODEBUG = range_reference_t<_View>;75 76 template <bool>77 struct __iterator;78 79 template <bool>80 struct __sentinel;81 82 template <class>83 friend struct std::__segmented_iterator_traits;84 85 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();86 87 static constexpr bool _UseOuterCache = !forward_range<_View>;88 using _OuterCache _LIBCPP_NODEBUG = _If<_UseOuterCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;89 _LIBCPP_NO_UNIQUE_ADDRESS _OuterCache __outer_;90 91 static constexpr bool _UseInnerCache = !is_reference_v<_InnerRange>;92 using _InnerCache _LIBCPP_NODEBUG =93 _If<_UseInnerCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>;94 _LIBCPP_NO_UNIQUE_ADDRESS _InnerCache __inner_;95 96public:97 _LIBCPP_HIDE_FROM_ABI join_view()98 requires default_initializable<_View>99 = default;100 101 _LIBCPP_HIDE_FROM_ABI constexpr explicit join_view(_View __base) : __base_(std::move(__base)) {}102 103 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&104 requires copy_constructible<_View>105 {106 return __base_;107 }108 109 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }110 111 _LIBCPP_HIDE_FROM_ABI constexpr auto begin() {112 if constexpr (forward_range<_View>) {113 constexpr bool __use_const = __simple_view<_View> && is_reference_v<range_reference_t<_View>>;114 return __iterator<__use_const>{*this, ranges::begin(__base_)};115 } else {116 __outer_.__emplace(ranges::begin(__base_));117 return __iterator<false>{*this};118 }119 }120 121 template <class _V2 = _View>122 _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const123 requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&124 input_range<range_reference_t<const _V2>>125 {126 return __iterator<true>{*this, ranges::begin(__base_)};127 }128 129 _LIBCPP_HIDE_FROM_ABI constexpr auto end() {130 if constexpr (forward_range<_View> && is_reference_v<_InnerRange> && forward_range<_InnerRange> &&131 common_range<_View> && common_range<_InnerRange>)132 return __iterator<__simple_view<_View>>{*this, ranges::end(__base_)};133 else134 return __sentinel<__simple_view<_View>>{*this};135 }136 137 template <class _V2 = _View>138 _LIBCPP_HIDE_FROM_ABI constexpr auto end() const139 requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&140 input_range<range_reference_t<const _V2>>141 {142 using _ConstInnerRange = range_reference_t<const _View>;143 if constexpr (forward_range<_ConstInnerRange> && common_range<const _View> && common_range<_ConstInnerRange>) {144 return __iterator<true>{*this, ranges::end(__base_)};145 } else {146 return __sentinel<true>{*this};147 }148 }149};150 151template <input_range _View>152 requires view<_View> && input_range<range_reference_t<_View>>153template <bool _Const>154struct join_view<_View>::__sentinel {155private:156 template <bool>157 friend struct __sentinel;158 159 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, join_view>;160 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>;161 sentinel_t<_Base> __end_ = sentinel_t<_Base>();162 163public:164 _LIBCPP_HIDE_FROM_ABI __sentinel() = default;165 166 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {}167 168 _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __s)169 requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>170 : __end_(std::move(__s.__end_)) {}171 172 template <bool _OtherConst>173 requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>174 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {175 return __x.__get_outer() == __y.__end_;176 }177};178 179// https://reviews.llvm.org/D142811#inline-1383022180// To simplify the segmented iterator traits specialization,181// make the iterator `final`182template <input_range _View>183 requires view<_View> && input_range<range_reference_t<_View>>184template <bool _Const>185struct join_view<_View>::__iterator final : public __join_view_iterator_category<__maybe_const<_Const, _View>> {186 friend join_view;187 188 template <class>189 friend struct std::__segmented_iterator_traits;190 191 static constexpr bool __is_join_view_iterator = true;192 193private:194 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, join_view<_View>>;195 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>;196 using _Outer _LIBCPP_NODEBUG = iterator_t<_Base>;197 using _Inner _LIBCPP_NODEBUG = iterator_t<range_reference_t<_Base>>;198 using _InnerRange _LIBCPP_NODEBUG = range_reference_t<_View>;199 200 static_assert(!_Const || forward_range<_Base>, "Const can only be true when Base models forward_range.");201 202 static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>;203 204 static constexpr bool _OuterPresent = forward_range<_Base>;205 using _OuterType _LIBCPP_NODEBUG = _If<_OuterPresent, _Outer, std::__empty>;206 _LIBCPP_NO_UNIQUE_ADDRESS _OuterType __outer_ = _OuterType();207 208 optional<_Inner> __inner_;209 _Parent* __parent_ = nullptr;210 211 _LIBCPP_HIDE_FROM_ABI constexpr void __satisfy() {212 for (; __get_outer() != ranges::end(__parent_->__base_); ++__get_outer()) {213 auto&& __inner = [this]() -> auto&& {214 if constexpr (__ref_is_glvalue)215 return *__get_outer();216 else217 return __parent_->__inner_.__emplace_from([&]() -> decltype(auto) { return *__get_outer(); });218 }();219 __inner_ = ranges::begin(__inner);220 if (*__inner_ != ranges::end(__inner))221 return;222 }223 224 if constexpr (__ref_is_glvalue)225 __inner_.reset();226 }227 228 _LIBCPP_HIDE_FROM_ABI constexpr _Outer& __get_outer() {229 if constexpr (forward_range<_Base>) {230 return __outer_;231 } else {232 return *__parent_->__outer_;233 }234 }235 236 _LIBCPP_HIDE_FROM_ABI constexpr const _Outer& __get_outer() const {237 if constexpr (forward_range<_Base>) {238 return __outer_;239 } else {240 return *__parent_->__outer_;241 }242 }243 244 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent& __parent, _Outer __outer)245 requires forward_range<_Base>246 : __outer_(std::move(__outer)), __parent_(std::addressof(__parent)) {247 __satisfy();248 }249 250 _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(_Parent& __parent)251 requires(!forward_range<_Base>)252 : __parent_(std::addressof(__parent)) {253 __satisfy();254 }255 256 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent* __parent, _Outer __outer, _Inner __inner)257 requires forward_range<_Base>258 : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {}259 260public:261 using iterator_concept =262 _If< __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&263 common_range<range_reference_t<_Base>>,264 bidirectional_iterator_tag,265 _If< __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>,266 forward_iterator_tag,267 input_iterator_tag > >;268 269 using value_type = range_value_t<range_reference_t<_Base>>;270 271 using difference_type = common_type_t< range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>;272 273 _LIBCPP_HIDE_FROM_ABI __iterator() = default;274 275 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i)276 requires _Const && convertible_to<iterator_t<_View>, _Outer> && convertible_to<iterator_t<_InnerRange>, _Inner>277 : __outer_(std::move(__i.__outer_)), __inner_(std::move(__i.__inner_)), __parent_(__i.__parent_) {}278 279 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const { return **__inner_; }280 281 _LIBCPP_HIDE_FROM_ABI constexpr _Inner operator->() const282 requires __has_arrow<_Inner> && copyable<_Inner>283 {284 return *__inner_;285 }286 287 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {288 auto __get_inner_range = [&]() -> decltype(auto) {289 if constexpr (__ref_is_glvalue)290 return *__get_outer();291 else292 return *__parent_->__inner_;293 };294 if (++*__inner_ == ranges::end(std::__as_lvalue(__get_inner_range()))) {295 ++__get_outer();296 __satisfy();297 }298 return *this;299 }300 301 _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; }302 303 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)304 requires __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>305 {306 auto __tmp = *this;307 ++*this;308 return __tmp;309 }310 311 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()312 requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&313 common_range<range_reference_t<_Base>>314 {315 if (__outer_ == ranges::end(__parent_->__base_))316 __inner_ = ranges::end(std::__as_lvalue(*--__outer_));317 318 // Skip empty inner ranges when going backwards.319 while (*__inner_ == ranges::begin(std::__as_lvalue(*__outer_))) {320 __inner_ = ranges::end(std::__as_lvalue(*--__outer_));321 }322 323 --*__inner_;324 return *this;325 }326 327 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)328 requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&329 common_range<range_reference_t<_Base>>330 {331 auto __tmp = *this;332 --*this;333 return __tmp;334 }335 336 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)337 requires __ref_is_glvalue && forward_range<_Base> && equality_comparable<iterator_t<range_reference_t<_Base>>>338 {339 return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_;340 }341 342 _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)343 iter_move(const __iterator& __i) noexcept(noexcept(ranges::iter_move(*__i.__inner_))) {344 return ranges::iter_move(*__i.__inner_);345 }346 347 _LIBCPP_HIDE_FROM_ABI friend constexpr void348 iter_swap(const __iterator& __x,349 const __iterator& __y) noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_)))350 requires indirectly_swappable<_Inner>351 {352 return ranges::iter_swap(*__x.__inner_, *__y.__inner_);353 }354};355 356template <class _Range>357explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;358 359namespace views {360namespace __join_view {361struct __fn : __range_adaptor_closure<__fn> {362 template <class _Range>363 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const364 noexcept(noexcept(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))))365 -> decltype(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))) {366 return join_view<all_t<_Range&&>>(std::forward<_Range>(__range));367 }368};369} // namespace __join_view370inline namespace __cpo {371inline constexpr auto join = __join_view::__fn{};372} // namespace __cpo373} // namespace views374} // namespace ranges375 376template <class _JoinViewIterator>377 requires(_JoinViewIterator::__is_join_view_iterator && ranges::common_range<typename _JoinViewIterator::_Parent> &&378 __has_random_access_iterator_category<typename _JoinViewIterator::_Outer>::value &&379 __has_random_access_iterator_category<typename _JoinViewIterator::_Inner>::value)380struct __segmented_iterator_traits<_JoinViewIterator> {381 using __segment_iterator _LIBCPP_NODEBUG =382 __iterator_with_data<typename _JoinViewIterator::_Outer, typename _JoinViewIterator::_Parent*>;383 using __local_iterator _LIBCPP_NODEBUG = typename _JoinViewIterator::_Inner;384 385 // TODO: Would it make sense to enable the optimization for other iterator types?386 387 static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) {388 if (ranges::empty(__iter.__parent_->__base_))389 return {};390 if (!__iter.__inner_.has_value())391 return __segment_iterator(--__iter.__outer_, __iter.__parent_);392 return __segment_iterator(__iter.__outer_, __iter.__parent_);393 }394 395 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) {396 if (ranges::empty(__iter.__parent_->__base_))397 return {};398 if (!__iter.__inner_.has_value())399 return ranges::end(*--__iter.__outer_);400 return *__iter.__inner_;401 }402 403 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) {404 return ranges::begin(*__iter.__get_iter());405 }406 407 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {408 return ranges::end(*__iter.__get_iter());409 }410 411 static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator412 __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) {413 auto&& __parent = std::move(__seg_iter).__get_data();414 auto&& __outer = std::move(__seg_iter).__get_iter();415 if (__local_iter == ranges::end(*__outer)) {416 ++__outer;417 return _JoinViewIterator(*__parent, __outer);418 }419 return _JoinViewIterator(__parent, __outer, std::move(__local_iter));420 }421};422 423#endif // #if _LIBCPP_STD_VER >= 20424 425_LIBCPP_END_NAMESPACE_STD426 427_LIBCPP_POP_MACROS428 429#endif // _LIBCPP___RANGES_JOIN_VIEW_H430