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_JOIN_VIEW_H
11#define _LIBCPP___RANGES_JOIN_VIEW_H
12
13#include <__concepts/constructible.h>
14#include <__concepts/convertible_to.h>
15#include <__concepts/copyable.h>
16#include <__concepts/derived_from.h>
17#include <__concepts/equality_comparable.h>
18#include <__config>
19#include <__iterator/concepts.h>
20#include <__iterator/iter_move.h>
21#include <__iterator/iter_swap.h>
22#include <__iterator/iterator_traits.h>
23#include <__iterator/iterator_with_data.h>
24#include <__iterator/segmented_iterator.h>
25#include <__memory/addressof.h>
26#include <__optional/comparison.h>
27#include <__optional/optional.h>
28#include <__ranges/access.h>
29#include <__ranges/all.h>
30#include <__ranges/concepts.h>
31#include <__ranges/empty.h>
32#include <__ranges/non_propagating_cache.h>
33#include <__ranges/range_adaptor.h>
34#include <__ranges/view_interface.h>
35#include <__type_traits/common_type.h>
36#include <__type_traits/conditional.h>
37#include <__type_traits/is_reference.h>
38#include <__type_traits/maybe_const.h>
39#include <__type_traits/remove_cvref.h>
40#include <__utility/as_lvalue.h>
41#include <__utility/empty.h>
42#include <__utility/forward.h>
43#include <__utility/move.h>
44
45#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
46# pragma GCC system_header
47#endif
48
49_LIBCPP_PUSH_MACROS
50#include <__undef_macros>
51
52_LIBCPP_BEGIN_NAMESPACE_STD
53
54#if _LIBCPP_STD_VER >= 20
55
56namespace ranges {
57template <class>
58struct __join_view_iterator_category {};
59
60template <class _View>
61 requires is_reference_v<range_reference_t<_View>> && forward_range<_View> && forward_range<range_reference_t<_View>>
62struct __join_view_iterator_category<_View> {
63 using _OuterC _LIBCPP_NODEBUG = typename iterator_traits<iterator_t<_View>>::iterator_category;
64 using _InnerC _LIBCPP_NODEBUG = typename iterator_traits<iterator_t<range_reference_t<_View>>>::iterator_category;
65
66 using iterator_category =
67 _If< derived_from<_OuterC, bidirectional_iterator_tag> && derived_from<_InnerC, bidirectional_iterator_tag> &&
68 common_range<range_reference_t<_View>>,
69 bidirectional_iterator_tag,
70 _If< derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>,
71 forward_iterator_tag,
72 input_iterator_tag > >;
73};
74
75template <input_range _View>
76 requires view<_View> && input_range<range_reference_t<_View>>
77class join_view : public view_interface<join_view<_View>> {
78private:
79 using _InnerRange _LIBCPP_NODEBUG = range_reference_t<_View>;
80
81 template <bool>
82 struct __iterator;
83
84 template <bool>
85 struct __sentinel;
86
87 template <class>
88 friend struct std::__segmented_iterator_traits;
89
90 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
91
92 static constexpr bool _UseOuterCache = !forward_range<_View>;
93 using _OuterCache _LIBCPP_NODEBUG = _If<_UseOuterCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
94 _LIBCPP_NO_UNIQUE_ADDRESS _OuterCache __outer_;
95
96 static constexpr bool _UseInnerCache = !is_reference_v<_InnerRange>;
97 using _InnerCache _LIBCPP_NODEBUG =
98 _If<_UseInnerCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>;
99 _LIBCPP_NO_UNIQUE_ADDRESS _InnerCache __inner_;
100
101public:
102 _LIBCPP_HIDE_FROM_ABI join_view()
103 requires default_initializable<_View>
104 = default;
105
106 _LIBCPP_HIDE_FROM_ABI constexpr explicit join_view(_View __base) : __base_(std::move(__base)) {}
107
108 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
109 requires copy_constructible<_View>
110 {
111 return __base_;
112 }
113
114 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
115
116 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin() {
117 if constexpr (forward_range<_View>) {
118 constexpr bool __use_const = __simple_view<_View> && is_reference_v<range_reference_t<_View>>;
119 return __iterator<__use_const>{*this, ranges::begin(__base_)};
120 } else {
121 __outer_.__emplace(ranges::begin(__base_));
122 return __iterator<false>{*this};
123 }
124 }
125
126 template <class _V2 = _View>
127 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
128 requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&
129 input_range<range_reference_t<const _V2>>
130 {
131 return __iterator<true>{*this, ranges::begin(__base_)};
132 }
133
134 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
135 if constexpr (forward_range<_View> && is_reference_v<_InnerRange> && forward_range<_InnerRange> &&
136 common_range<_View> && common_range<_InnerRange>)
137 return __iterator<__simple_view<_View>>{*this, ranges::end(__base_)};
138 else
139 return __sentinel<__simple_view<_View>>{*this};
140 }
141
142 template <class _V2 = _View>
143 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
144 requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&
145 input_range<range_reference_t<const _V2>>
146 {
147 using _ConstInnerRange = range_reference_t<const _View>;
148 if constexpr (forward_range<_ConstInnerRange> && common_range<const _View> && common_range<_ConstInnerRange>) {
149 return __iterator<true>{*this, ranges::end(__base_)};
150 } else {
151 return __sentinel<true>{*this};
152 }
153 }
154};
155
156template <input_range _View>
157 requires view<_View> && input_range<range_reference_t<_View>>
158template <bool _Const>
159struct join_view<_View>::__sentinel {
160private:
161 template <bool>
162 friend struct __sentinel;
163
164 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, join_view>;
165 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>;
166 sentinel_t<_Base> __end_ = sentinel_t<_Base>();
167
168 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {}
169
170 friend class join_view<_View>;
171
172public:
173 _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
174
175 _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __s)
176 requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
177 : __end_(std::move(__s.__end_)) {}
178
179 template <bool _OtherConst>
180 requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
181 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
182 return __x.__get_outer() == __y.__end_;
183 }
184};
185
186// https://reviews.llvm.org/D142811#inline-1383022
187// To simplify the segmented iterator traits specialization,
188// make the iterator `final`
189template <input_range _View>
190 requires view<_View> && input_range<range_reference_t<_View>>
191template <bool _Const>
192struct join_view<_View>::__iterator final : public __join_view_iterator_category<__maybe_const<_Const, _View>> {
193 friend join_view;
194
195 template <class>
196 friend struct std::__segmented_iterator_traits;
197
198 static constexpr bool __is_join_view_iterator = true;
199
200private:
201 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, join_view<_View>>;
202 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>;
203 using _Outer _LIBCPP_NODEBUG = iterator_t<_Base>;
204 using _Inner _LIBCPP_NODEBUG = iterator_t<range_reference_t<_Base>>;
205 using _InnerRange _LIBCPP_NODEBUG = range_reference_t<_View>;
206
207 static_assert(!_Const || forward_range<_Base>, "Const can only be true when Base models forward_range.");
208
209 static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>;
210
211 static constexpr bool _OuterPresent = forward_range<_Base>;
212 using _OuterType _LIBCPP_NODEBUG = _If<_OuterPresent, _Outer, std::__empty>;
213 _LIBCPP_NO_UNIQUE_ADDRESS _OuterType __outer_ = _OuterType();
214
215 optional<_Inner> __inner_;
216 _Parent* __parent_ = nullptr;
217
218 _LIBCPP_HIDE_FROM_ABI constexpr void __satisfy() {
219 for (; __get_outer() != ranges::end(__parent_->__base_); ++__get_outer()) {
220 auto&& __inner = [this]() -> auto&& {
221 if constexpr (__ref_is_glvalue)
222 return *__get_outer();
223 else
224 return __parent_->__inner_.__emplace_from([&]() -> decltype(auto) { return *__get_outer(); });
225 }();
226 __inner_ = ranges::begin(__inner);
227 if (*__inner_ != ranges::end(__inner))
228 return;
229 }
230
231 if constexpr (__ref_is_glvalue)
232 __inner_.reset();
233 }
234
235 _LIBCPP_HIDE_FROM_ABI constexpr _Outer& __get_outer() {
236 if constexpr (forward_range<_Base>) {
237 return __outer_;
238 } else {
239 return *__parent_->__outer_;
240 }
241 }
242
243 _LIBCPP_HIDE_FROM_ABI constexpr const _Outer& __get_outer() const {
244 if constexpr (forward_range<_Base>) {
245 return __outer_;
246 } else {
247 return *__parent_->__outer_;
248 }
249 }
250
251 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent& __parent, _Outer __outer)
252 requires forward_range<_Base>
253 : __outer_(std::move(__outer)), __parent_(std::addressof(__parent)) {
254 __satisfy();
255 }
256
257 _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(_Parent& __parent)
258 requires(!forward_range<_Base>)
259 : __parent_(std::addressof(__parent)) {
260 __satisfy();
261 }
262
263 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent* __parent, _Outer __outer, _Inner __inner)
264 requires forward_range<_Base>
265 : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {}
266
267public:
268 using iterator_concept =
269 _If< __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
270 common_range<range_reference_t<_Base>>,
271 bidirectional_iterator_tag,
272 _If< __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>,
273 forward_iterator_tag,
274 input_iterator_tag > >;
275
276 using value_type = range_value_t<range_reference_t<_Base>>;
277
278 using difference_type = common_type_t< range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>;
279
280 _LIBCPP_HIDE_FROM_ABI __iterator() = default;
281
282 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i)
283 requires _Const && convertible_to<iterator_t<_View>, _Outer> && convertible_to<iterator_t<_InnerRange>, _Inner>
284 : __outer_(std::move(__i.__outer_)), __inner_(std::move(__i.__inner_)), __parent_(__i.__parent_) {}
285
286 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const { return **__inner_; }
287
288 _LIBCPP_HIDE_FROM_ABI constexpr _Inner operator->() const
289 requires __has_arrow<_Inner> && copyable<_Inner>
290 {
291 return *__inner_;
292 }
293
294 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
295 auto __get_inner_range = [&]() -> decltype(auto) {
296 if constexpr (__ref_is_glvalue)
297 return *__get_outer();
298 else
299 return *__parent_->__inner_;
300 };
301 if (++*__inner_ == ranges::end(std::__as_lvalue(__get_inner_range()))) {
302 ++__get_outer();
303 __satisfy();
304 }
305 return *this;
306 }
307
308 _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; }
309
310 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)
311 requires __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>
312 {
313 auto __tmp = *this;
314 ++*this;
315 return __tmp;
316 }
317
318 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()
319 requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
320 common_range<range_reference_t<_Base>>
321 {
322 if (__outer_ == ranges::end(__parent_->__base_))
323 __inner_ = ranges::end(std::__as_lvalue(*--__outer_));
324
325 // Skip empty inner ranges when going backwards.
326 while (*__inner_ == ranges::begin(std::__as_lvalue(*__outer_))) {
327 __inner_ = ranges::end(std::__as_lvalue(*--__outer_));
328 }
329
330 --*__inner_;
331 return *this;
332 }
333
334 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)
335 requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
336 common_range<range_reference_t<_Base>>
337 {
338 auto __tmp = *this;
339 --*this;
340 return __tmp;
341 }
342
343 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
344 requires __ref_is_glvalue && forward_range<_Base> && equality_comparable<iterator_t<range_reference_t<_Base>>>
345 {
346 return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_;
347 }
348
349 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)
350 iter_move(const __iterator& __i) noexcept(noexcept(ranges::iter_move(*__i.__inner_))) {
351 return ranges::iter_move(*__i.__inner_);
352 }
353
354 _LIBCPP_HIDE_FROM_ABI friend constexpr void
355 iter_swap(const __iterator& __x,
356 const __iterator& __y) noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_)))
357 requires indirectly_swappable<_Inner>
358 {
359 return ranges::iter_swap(*__x.__inner_, *__y.__inner_);
360 }
361};
362
363template <class _Range>
364explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
365
366namespace views {
367namespace __join_view {
368struct __fn : __range_adaptor_closure<__fn> {
369 template <class _Range>
370 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
371 noexcept(noexcept(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))))
372 -> decltype(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))) {
373 return join_view<all_t<_Range&&>>(std::forward<_Range>(__range));
374 }
375};
376} // namespace __join_view
377inline namespace __cpo {
378inline constexpr auto join = __join_view::__fn{};
379} // namespace __cpo
380} // namespace views
381} // namespace ranges
382
383template <class _JoinViewIterator>
384 requires(_JoinViewIterator::__is_join_view_iterator && ranges::common_range<typename _JoinViewIterator::_Parent> &&
385 __has_random_access_iterator_category<typename _JoinViewIterator::_Outer>::value &&
386 __has_random_access_iterator_category<typename _JoinViewIterator::_Inner>::value)
387struct __segmented_iterator_traits<_JoinViewIterator> {
388 using __segment_iterator _LIBCPP_NODEBUG =
389 __iterator_with_data<typename _JoinViewIterator::_Outer, typename _JoinViewIterator::_Parent*>;
390 using __local_iterator _LIBCPP_NODEBUG = typename _JoinViewIterator::_Inner;
391
392 // TODO: Would it make sense to enable the optimization for other iterator types?
393
394 static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) {
395 if (ranges::empty(__iter.__parent_->__base_))
396 return {};
397 if (!__iter.__inner_.has_value())
398 return __segment_iterator(--__iter.__outer_, __iter.__parent_);
399 return __segment_iterator(__iter.__outer_, __iter.__parent_);
400 }
401
402 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) {
403 if (ranges::empty(__iter.__parent_->__base_))
404 return {};
405 if (!__iter.__inner_.has_value())
406 return ranges::end(*--__iter.__outer_);
407 return *__iter.__inner_;
408 }
409
410 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) {
411 return ranges::begin(*__iter.__get_iter());
412 }
413
414 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {
415 return ranges::end(*__iter.__get_iter());
416 }
417
418 static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator
419 __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) {
420 auto&& __parent = std::move(__seg_iter).__get_data();
421 auto&& __outer = std::move(__seg_iter).__get_iter();
422 if (__local_iter == ranges::end(*__outer)) {
423 ++__outer;
424 return _JoinViewIterator(*__parent, __outer);
425 }
426 return _JoinViewIterator(__parent, __outer, std::move(__local_iter));
427 }
428};
429
430#endif // #if _LIBCPP_STD_VER >= 20
431
432_LIBCPP_END_NAMESPACE_STD
433
434_LIBCPP_POP_MACROS
435
436#endif // _LIBCPP___RANGES_JOIN_VIEW_H
437