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