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