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