libcxx/include/__ranges/lazy_split_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_LAZY_SPLIT_VIEW_H
  11 #define _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H
  12
  13 #include <__algorithm/ranges_find.h>
  14 #include <__algorithm/ranges_mismatch.h>
  15 #include <__assert>
  16 #include <__concepts/constructible.h>
  17 #include <__concepts/convertible_to.h>
  18 #include <__concepts/derived_from.h>
  19 #include <__config>
  20 #include <__functional/bind_back.h>
  21 #include <__functional/ranges_operations.h>
  22 #include <__iterator/concepts.h>
  23 #include <__iterator/default_sentinel.h>
  24 #include <__iterator/incrementable_traits.h>
  25 #include <__iterator/indirectly_comparable.h>
  26 #include <__iterator/iter_move.h>
  27 #include <__iterator/iter_swap.h>
  28 #include <__iterator/iterator_traits.h>
  29 #include <__memory/addressof.h>
  30 #include <__ranges/access.h>
  31 #include <__ranges/all.h>
  32 #include <__ranges/concepts.h>
  33 #include <__ranges/non_propagating_cache.h>
  34 #include <__ranges/range_adaptor.h>
  35 #include <__ranges/single_view.h>
  36 #include <__ranges/subrange.h>
  37 #include <__ranges/view_interface.h>
  38 #include <__type_traits/conditional.h>
  39 #include <__type_traits/decay.h>
  40 #include <__type_traits/is_nothrow_constructible.h>
  41 #include <__type_traits/maybe_const.h>
  42 #include <__type_traits/remove_reference.h>
  43 #include <__utility/forward.h>
  44 #include <__utility/move.h>
  45
  46 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  47 #  pragma GCC system_header
  48 #endif
  49
  50 _LIBCPP_BEGIN_NAMESPACE_STD
  51
  52 #if _LIBCPP_STD_VER >= 20
  53
  54 namespace ranges {
  55
  56 template <auto> struct __require_constant;
  57
  58 template <class _Range>
  59 concept __tiny_range =
  60   sized_range<_Range> &&
  61   requires { typename __require_constant<remove_reference_t<_Range>::size()>; } &&
  62   (remove_reference_t<_Range>::size() <= 1);
  63
  64 template <input_range _View, forward_range _Pattern>
  65   requires view<_View> && view<_Pattern> &&
  66            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> &&
  67            (forward_range<_View> || __tiny_range<_Pattern>)
  68 class lazy_split_view : public view_interface<lazy_split_view<_View, _Pattern>> {
  69
  70   _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
  71   _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
  72
  73   using _MaybeCurrent = _If<!forward_range<_View>, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
  74   _LIBCPP_NO_UNIQUE_ADDRESS _MaybeCurrent __current_ = _MaybeCurrent();
  75
  76   template <bool> struct __outer_iterator;
  77   template <bool> struct __inner_iterator;
  78
  79 public:
  80   _LIBCPP_HIDE_FROM_ABI
  81   lazy_split_view()
  82     requires default_initializable<_View> && default_initializable<_Pattern> = default;
  83
  84   _LIBCPP_HIDE_FROM_ABI
  85   constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 lazy_split_view(_View __base, _Pattern __pattern)
  86     : __base_(std::move(__base)), __pattern_(std::move(__pattern)) {}
  87
  88   template <input_range _Range>
  89     requires constructible_from<_View, views::all_t<_Range>> &&
  90              constructible_from<_Pattern, single_view<range_value_t<_Range>>>
  91   _LIBCPP_HIDE_FROM_ABI
  92   constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 lazy_split_view(_Range&& __r, range_value_t<_Range> __e)
  93     : __base_(views::all(std::forward<_Range>(__r)))
  94     , __pattern_(views::single(std::move(__e))) {}
  95
  96   _LIBCPP_HIDE_FROM_ABI
  97   constexpr _View base() const& requires copy_constructible<_View> { return __base_; }
  98   _LIBCPP_HIDE_FROM_ABI
  99   constexpr _View base() && { return std::move(__base_); }
 100
 101   _LIBCPP_HIDE_FROM_ABI
 102   constexpr auto begin() {
 103     if constexpr (forward_range<_View>) {
 104       return __outer_iterator<__simple_view<_View> && __simple_view<_Pattern>>{*this, ranges::begin(__base_)};
 105     } else {
 106       __current_.__emplace(ranges::begin(__base_));
 107       return __outer_iterator<false>{*this};
 108     }
 109   }
 110
 111   _LIBCPP_HIDE_FROM_ABI
 112   constexpr auto begin() const requires forward_range<_View> && forward_range<const _View> {
 113     return __outer_iterator<true>{*this, ranges::begin(__base_)};
 114   }
 115
 116   _LIBCPP_HIDE_FROM_ABI
 117   constexpr auto end() requires forward_range<_View> && common_range<_View> {
 118     return __outer_iterator<__simple_view<_View> && __simple_view<_Pattern>>{*this, ranges::end(__base_)};
 119   }
 120
 121   _LIBCPP_HIDE_FROM_ABI
 122   constexpr auto end() const {
 123     if constexpr (forward_range<_View> && forward_range<const _View> && common_range<const _View>) {
 124       return __outer_iterator<true>{*this, ranges::end(__base_)};
 125     } else {
 126       return default_sentinel;
 127     }
 128   }
 129
 130 private:
 131
 132   template <class>
 133   struct __outer_iterator_category {};
 134
 135   template <forward_range _Tp>
 136   struct __outer_iterator_category<_Tp> {
 137     using iterator_category = input_iterator_tag;
 138   };
 139
 140   template <bool _Const>
 141   struct __outer_iterator : __outer_iterator_category<__maybe_const<_Const, _View>> {
 142   private:
 143     template <bool>
 144     friend struct __inner_iterator;
 145     friend __outer_iterator<true>;
 146
 147     using _Parent = __maybe_const<_Const, lazy_split_view>;
 148     using _Base = __maybe_const<_Const, _View>;
 149
 150     _Parent* __parent_ = nullptr;
 151     using _MaybeCurrent = _If<forward_range<_View>, iterator_t<_Base>, __empty_cache>;
 152     _LIBCPP_NO_UNIQUE_ADDRESS _MaybeCurrent __current_ = _MaybeCurrent();
 153     bool __trailing_empty_ = false;
 154
 155     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
 156     constexpr auto& __current() noexcept {
 157       if constexpr (forward_range<_View>) {
 158         return __current_;
 159       } else {
 160         return *__parent_->__current_;
 161       }
 162     }
 163
 164     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
 165     constexpr const auto& __current() const noexcept {
 166       if constexpr (forward_range<_View>) {
 167         return __current_;
 168       } else {
 169         return *__parent_->__current_;
 170       }
 171     }
 172
 173     // Workaround for the GCC issue that doesn't allow calling `__parent_->__base_` from friend functions (because
 174     // `__base_` is private).
 175     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
 176     constexpr auto& __parent_base() const noexcept {
 177       return __parent_->__base_;
 178     }
 179
 180   public:
 181     // using iterator_category = inherited;
 182     using iterator_concept = conditional_t<forward_range<_Base>, forward_iterator_tag, input_iterator_tag>;
 183     using difference_type = range_difference_t<_Base>;
 184
 185     struct value_type : view_interface<value_type> {
 186     private:
 187       __outer_iterator __i_ = __outer_iterator();
 188
 189     public:
 190       _LIBCPP_HIDE_FROM_ABI
 191       value_type() = default;
 192       _LIBCPP_HIDE_FROM_ABI
 193       constexpr explicit value_type(__outer_iterator __i)
 194         : __i_(std::move(__i)) {}
 195
 196       _LIBCPP_HIDE_FROM_ABI
 197       constexpr __inner_iterator<_Const> begin() const { return __inner_iterator<_Const>{__i_}; }
 198       _LIBCPP_HIDE_FROM_ABI
 199       constexpr default_sentinel_t end() const noexcept { return default_sentinel; }
 200     };
 201
 202     _LIBCPP_HIDE_FROM_ABI
 203     __outer_iterator() = default;
 204
 205     _LIBCPP_HIDE_FROM_ABI
 206     constexpr explicit __outer_iterator(_Parent& __parent)
 207       requires (!forward_range<_Base>)
 208       : __parent_(std::addressof(__parent)) {}
 209
 210     _LIBCPP_HIDE_FROM_ABI
 211     constexpr __outer_iterator(_Parent& __parent, iterator_t<_Base> __current)
 212       requires forward_range<_Base>
 213       : __parent_(std::addressof(__parent)), __current_(std::move(__current)) {}
 214
 215     _LIBCPP_HIDE_FROM_ABI
 216     constexpr __outer_iterator(__outer_iterator<!_Const> __i)
 217       requires _Const && convertible_to<iterator_t<_View>, iterator_t<_Base>>
 218       : __parent_(__i.__parent_), __current_(std::move(__i.__current_)) {}
 219
 220     _LIBCPP_HIDE_FROM_ABI
 221     constexpr value_type operator*() const { return value_type{*this}; }
 222
 223     _LIBCPP_HIDE_FROM_ABI
 224     constexpr __outer_iterator& operator++() {
 225       const auto __end = ranges::end(__parent_->__base_);
 226       if (__current() == __end) {
 227         __trailing_empty_ = false;
 228         return *this;
 229       }
 230
 231       const auto [__pbegin, __pend] = ranges::subrange{__parent_->__pattern_};
 232       if (__pbegin == __pend) {
 233         // Empty pattern: split on every element in the input range
 234         ++__current();
 235
 236       } else if constexpr (__tiny_range<_Pattern>) {
 237         // One-element pattern: we can use `ranges::find`.
 238         __current() = ranges::find(std::move(__current()), __end, *__pbegin);
 239         if (__current() != __end) {
 240           // Make sure we point to after the separator we just found.
 241           ++__current();
 242           if (__current() == __end)
 243             __trailing_empty_ = true;
 244         }
 245
 246       } else {
 247         // General case for n-element pattern.
 248         do {
 249           const auto [__b, __p] = ranges::mismatch(__current(), __end, __pbegin, __pend);
 250           if (__p == __pend) {
 251             __current() = __b;
 252             if (__current() == __end) {
 253               __trailing_empty_ = true;
 254             }
 255             break; // The pattern matched; skip it.
 256           }
 257         } while (++__current() != __end);
 258       }
 259
 260       return *this;
 261     }
 262
 263     _LIBCPP_HIDE_FROM_ABI
 264     constexpr decltype(auto) operator++(int) {
 265       if constexpr (forward_range<_Base>) {
 266         auto __tmp = *this;
 267         ++*this;
 268         return __tmp;
 269
 270       } else {
 271         ++*this;
 272       }
 273     }
 274
 275     _LIBCPP_HIDE_FROM_ABI
 276     friend constexpr bool operator==(const __outer_iterator& __x, const __outer_iterator& __y)
 277       requires forward_range<_Base> {
 278       return __x.__current_ == __y.__current_ && __x.__trailing_empty_ == __y.__trailing_empty_;
 279     }
 280
 281     _LIBCPP_HIDE_FROM_ABI
 282     friend constexpr bool operator==(const __outer_iterator& __x, default_sentinel_t) {
 283       _LIBCPP_ASSERT_UNCATEGORIZED(__x.__parent_, "Cannot call comparison on a default-constructed iterator.");
 284       return __x.__current() == ranges::end(__x.__parent_base()) && !__x.__trailing_empty_;
 285     }
 286   };
 287
 288   template <class>
 289   struct __inner_iterator_category {};
 290
 291   template <forward_range _Tp>
 292   struct __inner_iterator_category<_Tp> {
 293     using iterator_category = _If<
 294       derived_from<typename iterator_traits<iterator_t<_Tp>>::iterator_category, forward_iterator_tag>,
 295       forward_iterator_tag,
 296       typename iterator_traits<iterator_t<_Tp>>::iterator_category
 297     >;
 298   };
 299
 300   template <bool _Const>
 301   struct __inner_iterator : __inner_iterator_category<__maybe_const<_Const, _View>> {
 302   private:
 303     using _Base = __maybe_const<_Const, _View>;
 304     // Workaround for a GCC issue.
 305     static constexpr bool _OuterConst = _Const;
 306     __outer_iterator<_Const> __i_ = __outer_iterator<_OuterConst>();
 307     bool __incremented_ = false;
 308
 309     // Note: these private functions are necessary because GCC doesn't allow calls to private members of `__i_` from
 310     // free functions that are friends of `inner-iterator`.
 311
 312     _LIBCPP_HIDE_FROM_ABI
 313     constexpr bool __is_done() const {
 314       _LIBCPP_ASSERT_UNCATEGORIZED(__i_.__parent_, "Cannot call comparison on a default-constructed iterator.");
 315
 316       auto [__pcur, __pend] = ranges::subrange{__i_.__parent_->__pattern_};
 317       auto __end = ranges::end(__i_.__parent_->__base_);
 318
 319       if constexpr (__tiny_range<_Pattern>) {
 320         const auto& __cur = __i_.__current();
 321         if (__cur == __end)
 322           return true;
 323         if (__pcur == __pend)
 324           return __incremented_;
 325
 326         return *__cur == *__pcur;
 327
 328       } else {
 329         auto __cur = __i_.__current();
 330         if (__cur == __end)
 331           return true;
 332         if (__pcur == __pend)
 333           return __incremented_;
 334
 335         do {
 336           if (*__cur != *__pcur)
 337             return false;
 338           if (++__pcur == __pend)
 339             return true;
 340         } while (++__cur != __end);
 341
 342         return false;
 343       }
 344     }
 345
 346     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
 347     constexpr auto& __outer_current() noexcept {
 348       return __i_.__current();
 349     }
 350
 351     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
 352     constexpr const auto& __outer_current() const noexcept {
 353       return __i_.__current();
 354     }
 355
 356   public:
 357     // using iterator_category = inherited;
 358     using iterator_concept = typename __outer_iterator<_Const>::iterator_concept;
 359     using value_type = range_value_t<_Base>;
 360     using difference_type = range_difference_t<_Base>;
 361
 362     _LIBCPP_HIDE_FROM_ABI
 363     __inner_iterator() = default;
 364
 365     _LIBCPP_HIDE_FROM_ABI
 366     constexpr explicit __inner_iterator(__outer_iterator<_Const> __i)
 367       : __i_(std::move(__i)) {}
 368
 369     _LIBCPP_HIDE_FROM_ABI
 370     constexpr const iterator_t<_Base>& base() const& noexcept { return __i_.__current(); }
 371     _LIBCPP_HIDE_FROM_ABI
 372     constexpr iterator_t<_Base> base() &&
 373       requires forward_range<_View> { return std::move(__i_.__current()); }
 374
 375     _LIBCPP_HIDE_FROM_ABI
 376     constexpr decltype(auto) operator*() const { return *__i_.__current(); }
 377
 378     _LIBCPP_HIDE_FROM_ABI
 379     constexpr __inner_iterator& operator++() {
 380       __incremented_ = true;
 381
 382       if constexpr (!forward_range<_Base>) {
 383         if constexpr (_Pattern::size() == 0) {
 384           return *this;
 385         }
 386       }
 387
 388       ++__i_.__current();
 389       return *this;
 390     }
 391
 392     _LIBCPP_HIDE_FROM_ABI
 393     constexpr decltype(auto) operator++(int) {
 394       if constexpr (forward_range<_Base>) {
 395         auto __tmp = *this;
 396         ++*this;
 397         return __tmp;
 398
 399       } else {
 400         ++*this;
 401       }
 402     }
 403
 404     _LIBCPP_HIDE_FROM_ABI
 405     friend constexpr bool operator==(const __inner_iterator& __x, const __inner_iterator& __y)
 406       requires forward_range<_Base> {
 407       return __x.__outer_current() == __y.__outer_current();
 408     }
 409
 410     _LIBCPP_HIDE_FROM_ABI
 411     friend constexpr bool operator==(const __inner_iterator& __x, default_sentinel_t) {
 412       return __x.__is_done();
 413     }
 414
 415     _LIBCPP_HIDE_FROM_ABI
 416     friend constexpr decltype(auto) iter_move(const __inner_iterator& __i)
 417         noexcept(noexcept(ranges::iter_move(__i.__outer_current()))) {
 418       return ranges::iter_move(__i.__outer_current());
 419     }
 420
 421     _LIBCPP_HIDE_FROM_ABI
 422     friend constexpr void iter_swap(const __inner_iterator& __x, const __inner_iterator& __y)
 423         noexcept(noexcept(ranges::iter_swap(__x.__outer_current(), __y.__outer_current())))
 424         requires indirectly_swappable<iterator_t<_Base>> {
 425       ranges::iter_swap(__x.__outer_current(), __y.__outer_current());
 426     }
 427   };
 428
 429 };
 430
 431 template <class _Range, class _Pattern>
 432 lazy_split_view(_Range&&, _Pattern&&) -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
 433
 434 template <input_range _Range>
 435 lazy_split_view(_Range&&, range_value_t<_Range>)
 436   -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
 437
 438 namespace views {
 439 namespace __lazy_split_view {
 440 struct __fn : __range_adaptor_closure<__fn> {
 441   template <class _Range, class _Pattern>
 442   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
 443   constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
 444     noexcept(noexcept(lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
 445     -> decltype(      lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))
 446     { return          lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); }
 447
 448   template <class _Pattern>
 449     requires constructible_from<decay_t<_Pattern>, _Pattern>
 450   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
 451   constexpr auto operator()(_Pattern&& __pattern) const
 452       noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
 453     return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
 454   }
 455 };
 456 } // namespace __lazy_split_view
 457
 458 inline namespace __cpo {
 459   inline constexpr auto lazy_split = __lazy_split_view::__fn{};
 460 } // namespace __cpo
 461 } // namespace views
 462
 463 } // namespace ranges
 464
 465 #endif // _LIBCPP_STD_VER >= 20
 466
 467 _LIBCPP_END_NAMESPACE_STD
 468
 469 #endif // _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H