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