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