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