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