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
57namespace ranges {
58
59template <auto>
60struct __require_constant;
61
62template <class _Range>
63concept __tiny_range = sized_range<_Range> && requires {
64  typename __require_constant<remove_reference_t<_Range>::size()>;
65} && (remove_reference_t<_Range>::size() <= 1);
66
67template <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>)
71class 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
83public:
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
133private:
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
402template <class _Range, class _Pattern>
403lazy_split_view(_Range&&, _Pattern&&) -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
404
405template <input_range _Range>
406lazy_split_view(_Range&&, range_value_t<_Range>)
407    -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
408
409namespace views {
410namespace __lazy_split_view {
411struct __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 __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
424  }
425};
426} // namespace __lazy_split_view
427
428inline namespace __cpo {
429inline 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
442