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 #ifndef _LIBCPP___RANGES_JOIN_VIEW_H
  10 #define _LIBCPP___RANGES_JOIN_VIEW_H
  11
  12 #include <__config>
  13 #include <__iterator/concepts.h>
  14 #include <__iterator/iterator_traits.h>
  15 #include <__ranges/access.h>
  16 #include <__ranges/all.h>
  17 #include <__ranges/concepts.h>
  18 #include <__ranges/non_propagating_cache.h>
  19 #include <__ranges/ref_view.h>
  20 #include <__ranges/subrange.h>
  21 #include <__ranges/view_interface.h>
  22 #include <__utility/declval.h>
  23 #include <__utility/forward.h>
  24 #include <optional>
  25 #include <type_traits>
  26
  27 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  28 #pragma GCC system_header
  29 #endif
  30
  31 _LIBCPP_BEGIN_NAMESPACE_STD
  32
  33 #if !defined(_LIBCPP_HAS_NO_RANGES)
  34
  35 namespace ranges {
  36   template<class>
  37   struct __join_view_iterator_category {};
  38
  39   template<class _View>
  40     requires is_reference_v<range_reference_t<_View>> &&
  41              forward_range<_View> &&
  42              forward_range<range_reference_t<_View>>
  43   struct __join_view_iterator_category<_View> {
  44     using _OuterC = typename iterator_traits<iterator_t<_View>>::iterator_category;
  45     using _InnerC = typename iterator_traits<iterator_t<range_reference_t<_View>>>::iterator_category;
  46
  47     using iterator_category = _If<
  48       derived_from<_OuterC, bidirectional_iterator_tag> && derived_from<_InnerC, bidirectional_iterator_tag>,
  49       bidirectional_iterator_tag,
  50       _If<
  51         derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>,
  52         forward_iterator_tag,
  53         input_iterator_tag
  54       >
  55     >;
  56   };
  57
  58   template<input_range _View>
  59     requires view<_View> && input_range<range_reference_t<_View>>
  60   class join_view
  61     : public view_interface<join_view<_View>> {
  62   private:
  63     using _InnerRange = range_reference_t<_View>;
  64
  65     template<bool> struct __iterator;
  66     template<bool> struct __sentinel;
  67
  68     static constexpr bool _UseCache = !is_reference_v<_InnerRange>;
  69     using _Cache = _If<_UseCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>;
  70     [[no_unique_address]] _Cache __cache_;
  71     _View __base_ = _View(); // TODO: [[no_unique_address]] makes clang crash! File a bug :)
  72
  73   public:
  74     _LIBCPP_HIDE_FROM_ABI
  75     join_view() requires default_initializable<_View> = default;
  76
  77     _LIBCPP_HIDE_FROM_ABI
  78     constexpr explicit join_view(_View __base)
  79       : __base_(_VSTD::move(__base)) {}
  80
  81     _LIBCPP_HIDE_FROM_ABI
  82     constexpr _View base() const& requires copy_constructible<_View> { return __base_; }
  83
  84     _LIBCPP_HIDE_FROM_ABI
  85     constexpr _View base() && { return _VSTD::move(__base_); }
  86
  87     _LIBCPP_HIDE_FROM_ABI
  88     constexpr auto begin() {
  89       constexpr bool __use_const = __simple_view<_View> &&
  90                                    is_reference_v<range_reference_t<_View>>;
  91       return __iterator<__use_const>{*this, ranges::begin(__base_)};
  92     }
  93
  94     template<class _V2 = _View>
  95     _LIBCPP_HIDE_FROM_ABI
  96     constexpr auto begin() const
  97       requires input_range<const _V2> &&
  98                is_reference_v<range_reference_t<const _V2>>
  99     {
 100       return __iterator<true>{*this, ranges::begin(__base_)};
 101     }
 102
 103     _LIBCPP_HIDE_FROM_ABI
 104     constexpr auto end() {
 105       if constexpr (forward_range<_View> &&
 106                     is_reference_v<_InnerRange> &&
 107                     forward_range<_InnerRange> &&
 108                     common_range<_View> &&
 109                     common_range<_InnerRange>)
 110         return __iterator<__simple_view<_View>>{*this, ranges::end(__base_)};
 111       else
 112         return __sentinel<__simple_view<_View>>{*this};
 113     }
 114
 115     template<class _V2 = _View>
 116     _LIBCPP_HIDE_FROM_ABI
 117     constexpr auto end() const
 118       requires input_range<const _V2> &&
 119                is_reference_v<range_reference_t<const _V2>>
 120     {
 121       using _ConstInnerRange = range_reference_t<const _View>;
 122       if constexpr (forward_range<const _View> &&
 123                     is_reference_v<_ConstInnerRange> &&
 124                     forward_range<_ConstInnerRange> &&
 125                     common_range<const _View> &&
 126                     common_range<_ConstInnerRange>) {
 127         return __iterator<true>{*this, ranges::end(__base_)};
 128       } else {
 129         return __sentinel<true>{*this};
 130       }
 131     }
 132   };
 133
 134   template<input_range _View>
 135     requires view<_View> && input_range<range_reference_t<_View>>
 136   template<bool _Const> struct join_view<_View>::__sentinel {
 137     template<bool> friend struct __sentinel;
 138
 139   private:
 140     using _Parent = __maybe_const<_Const, join_view>;
 141     using _Base = __maybe_const<_Const, _View>;
 142     sentinel_t<_Base> __end_ = sentinel_t<_Base>();
 143
 144   public:
 145     _LIBCPP_HIDE_FROM_ABI
 146     __sentinel() = default;
 147
 148     _LIBCPP_HIDE_FROM_ABI
 149     constexpr explicit __sentinel(_Parent& __parent)
 150       : __end_(ranges::end(__parent.__base_)) {}
 151
 152     _LIBCPP_HIDE_FROM_ABI
 153     constexpr __sentinel(__sentinel<!_Const> __s)
 154       requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
 155       : __end_(_VSTD::move(__s.__end_)) {}
 156
 157     template<bool _OtherConst>
 158       requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
 159     _LIBCPP_HIDE_FROM_ABI
 160     friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
 161       return __x.__outer_ == __y.__end_;
 162     }
 163   };
 164
 165   template<input_range _View>
 166     requires view<_View> && input_range<range_reference_t<_View>>
 167   template<bool _Const> struct join_view<_View>::__iterator
 168     : public __join_view_iterator_category<__maybe_const<_Const, _View>> {
 169
 170     template<bool> friend struct __iterator;
 171
 172   private:
 173     using _Parent = __maybe_const<_Const, join_view>;
 174     using _Base = __maybe_const<_Const, _View>;
 175     using _Outer = iterator_t<_Base>;
 176     using _Inner = iterator_t<range_reference_t<_Base>>;
 177
 178     static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>;
 179
 180   public:
 181     _Outer __outer_ = _Outer();
 182
 183   private:
 184     optional<_Inner> __inner_;
 185     _Parent *__parent_ = nullptr;
 186
 187     _LIBCPP_HIDE_FROM_ABI
 188     constexpr void __satisfy() {
 189       for (; __outer_ != ranges::end(__parent_->__base_); ++__outer_) {
 190         auto&& __inner = [&]() -> auto&& {
 191           if constexpr (__ref_is_glvalue)
 192             return *__outer_;
 193           else
 194             return __parent_->__cache_.__emplace_from([&]() -> decltype(auto) { return *__outer_; });
 195         }();
 196         __inner_ = ranges::begin(__inner);
 197         if (*__inner_ != ranges::end(__inner))
 198           return;
 199       }
 200
 201       if constexpr (__ref_is_glvalue)
 202         __inner_.reset();
 203     }
 204
 205   public:
 206     using iterator_concept = _If<
 207       __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>>,
 208       bidirectional_iterator_tag,
 209       _If<
 210         __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>,
 211         forward_iterator_tag,
 212         input_iterator_tag
 213       >
 214     >;
 215
 216     using value_type = range_value_t<range_reference_t<_Base>>;
 217
 218     using difference_type = common_type_t<
 219       range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>;
 220
 221     _LIBCPP_HIDE_FROM_ABI
 222     __iterator() requires default_initializable<_Outer> = default;
 223
 224     _LIBCPP_HIDE_FROM_ABI
 225     constexpr __iterator(_Parent& __parent, _Outer __outer)
 226       : __outer_(_VSTD::move(__outer))
 227       , __parent_(_VSTD::addressof(__parent)) {
 228       __satisfy();
 229     }
 230
 231     _LIBCPP_HIDE_FROM_ABI
 232     constexpr __iterator(__iterator<!_Const> __i)
 233       requires _Const &&
 234                convertible_to<iterator_t<_View>, _Outer> &&
 235                convertible_to<iterator_t<_InnerRange>, _Inner>
 236       : __outer_(_VSTD::move(__i.__outer_))
 237       , __inner_(_VSTD::move(__i.__inner_))
 238       , __parent_(__i.__parent_) {}
 239
 240     _LIBCPP_HIDE_FROM_ABI
 241     constexpr decltype(auto) operator*() const {
 242       return **__inner_;
 243     }
 244
 245     _LIBCPP_HIDE_FROM_ABI
 246     constexpr _Inner operator->() const
 247       requires __has_arrow<_Inner> && copyable<_Inner>
 248     {
 249       return *__inner_;
 250     }
 251
 252     _LIBCPP_HIDE_FROM_ABI
 253     constexpr __iterator& operator++() {
 254       auto&& __inner = [&]() -> auto&& {
 255         if constexpr (__ref_is_glvalue)
 256           return *__outer_;
 257         else
 258           return *__parent_->__cache_;
 259       }();
 260       if (++*__inner_ == ranges::end(__inner)) {
 261         ++__outer_;
 262         __satisfy();
 263       }
 264       return *this;
 265     }
 266
 267     _LIBCPP_HIDE_FROM_ABI
 268     constexpr void operator++(int) {
 269       ++*this;
 270     }
 271
 272     _LIBCPP_HIDE_FROM_ABI
 273     constexpr __iterator operator++(int)
 274       requires __ref_is_glvalue &&
 275                forward_range<_Base> &&
 276                forward_range<range_reference_t<_Base>>
 277     {
 278       auto __tmp = *this;
 279       ++*this;
 280       return __tmp;
 281     }
 282
 283     _LIBCPP_HIDE_FROM_ABI
 284     constexpr __iterator& operator--()
 285       requires __ref_is_glvalue &&
 286                bidirectional_range<_Base> &&
 287                bidirectional_range<range_reference_t<_Base>> &&
 288                common_range<range_reference_t<_Base>>
 289     {
 290       if (__outer_ == ranges::end(__parent_->__base_))
 291         __inner_ = ranges::end(*--__outer_);
 292
 293       // Skip empty inner ranges when going backwards.
 294       while (*__inner_ == ranges::begin(*__outer_)) {
 295         __inner_ = ranges::end(*--__outer_);
 296       }
 297
 298       --*__inner_;
 299       return *this;
 300     }
 301
 302     _LIBCPP_HIDE_FROM_ABI
 303     constexpr __iterator operator--(int)
 304       requires __ref_is_glvalue &&
 305                bidirectional_range<_Base> &&
 306                bidirectional_range<range_reference_t<_Base>> &&
 307                common_range<range_reference_t<_Base>>
 308     {
 309       auto __tmp = *this;
 310       --*this;
 311       return __tmp;
 312     }
 313
 314     _LIBCPP_HIDE_FROM_ABI
 315     friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
 316       requires __ref_is_glvalue &&
 317                equality_comparable<iterator_t<_Base>> &&
 318                equality_comparable<iterator_t<range_reference_t<_Base>>>
 319     {
 320       return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_;
 321     }
 322
 323     _LIBCPP_HIDE_FROM_ABI
 324     friend constexpr decltype(auto) iter_move(const __iterator& __i)
 325       noexcept(noexcept(ranges::iter_move(*__i.__inner_)))
 326     {
 327       return ranges::iter_move(*__i.__inner_);
 328     }
 329
 330     _LIBCPP_HIDE_FROM_ABI
 331     friend constexpr void iter_swap(const __iterator& __x, const __iterator& __y)
 332       noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_)))
 333       requires indirectly_swappable<_Inner>
 334     {
 335       return ranges::iter_swap(*__x.__inner_, *__y.__inner_);
 336     }
 337   };
 338
 339   template<class _Range>
 340   explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
 341
 342 } // namespace ranges
 343
 344 #undef _CONSTEXPR_TERNARY
 345
 346 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 347
 348 _LIBCPP_END_NAMESPACE_STD
 349
 350 #endif // _LIBCPP___RANGES_JOIN_VIEW_H