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