xref: /freebsd/contrib/llvm-project/libcxx/include/__ranges/lazy_split_view.h (revision 5fb307d29b364982acbde82cbf77db3cae486f8c) 
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
470