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