[AArch64] Add fpext and fpround costs (#119292)
[llvm-project.git] / libcxx / include / __ranges / join_view.h
blob9c2c77995539bd25e01c53d2162ef3fa828a1723
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 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP___RANGES_JOIN_VIEW_H
11 #define _LIBCPP___RANGES_JOIN_VIEW_H
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>
40 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
41 # pragma GCC system_header
42 #endif
44 _LIBCPP_PUSH_MACROS
45 #include <__undef_macros>
47 _LIBCPP_BEGIN_NAMESPACE_STD
49 #if _LIBCPP_STD_VER >= 20
51 namespace ranges {
52 template <class>
53 struct __join_view_iterator_category {};
55 template <class _View>
56 requires is_reference_v<range_reference_t<_View>> && forward_range<_View> && 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;
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 > >;
70 template <input_range _View>
71 requires view<_View> && input_range<range_reference_t<_View>>
72 class join_view : public view_interface<join_view<_View>> {
73 private:
74 using _InnerRange = range_reference_t<_View>;
76 template <bool>
77 struct __iterator;
79 template <bool>
80 struct __sentinel;
82 template <class>
83 friend struct std::__segmented_iterator_traits;
85 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
87 static constexpr bool _UseOuterCache = !forward_range<_View>;
88 using _OuterCache = _If<_UseOuterCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
89 _LIBCPP_NO_UNIQUE_ADDRESS _OuterCache __outer_;
91 static constexpr bool _UseInnerCache = !is_reference_v<_InnerRange>;
92 using _InnerCache = _If<_UseInnerCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>;
93 _LIBCPP_NO_UNIQUE_ADDRESS _InnerCache __inner_;
95 public:
96 _LIBCPP_HIDE_FROM_ABI join_view()
97 requires default_initializable<_View>
98 = default;
100 _LIBCPP_HIDE_FROM_ABI constexpr explicit join_view(_View __base) : __base_(std::move(__base)) {}
102 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
103 requires copy_constructible<_View>
105 return __base_;
108 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
110 _LIBCPP_HIDE_FROM_ABI constexpr auto begin() {
111 if constexpr (forward_range<_View>) {
112 constexpr bool __use_const = __simple_view<_View> && is_reference_v<range_reference_t<_View>>;
113 return __iterator<__use_const>{*this, ranges::begin(__base_)};
114 } else {
115 __outer_.__emplace(ranges::begin(__base_));
116 return __iterator<false>{*this};
120 template <class _V2 = _View>
121 _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
122 requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&
123 input_range<range_reference_t<const _V2>>
125 return __iterator<true>{*this, ranges::begin(__base_)};
128 _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
129 if constexpr (forward_range<_View> && is_reference_v<_InnerRange> && forward_range<_InnerRange> &&
130 common_range<_View> && common_range<_InnerRange>)
131 return __iterator<__simple_view<_View>>{*this, ranges::end(__base_)};
132 else
133 return __sentinel<__simple_view<_View>>{*this};
136 template <class _V2 = _View>
137 _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
138 requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&
139 input_range<range_reference_t<const _V2>>
141 using _ConstInnerRange = range_reference_t<const _View>;
142 if constexpr (forward_range<_ConstInnerRange> && common_range<const _View> && common_range<_ConstInnerRange>) {
143 return __iterator<true>{*this, ranges::end(__base_)};
144 } else {
145 return __sentinel<true>{*this};
150 template <input_range _View>
151 requires view<_View> && input_range<range_reference_t<_View>>
152 template <bool _Const>
153 struct join_view<_View>::__sentinel {
154 private:
155 template <bool>
156 friend struct __sentinel;
158 using _Parent = __maybe_const<_Const, join_view>;
159 using _Base = __maybe_const<_Const, _View>;
160 sentinel_t<_Base> __end_ = sentinel_t<_Base>();
162 public:
163 _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
165 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {}
167 _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __s)
168 requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
169 : __end_(std::move(__s.__end_)) {}
171 template <bool _OtherConst>
172 requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
173 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
174 return __x.__get_outer() == __y.__end_;
178 // https://reviews.llvm.org/D142811#inline-1383022
179 // To simplify the segmented iterator traits specialization,
180 // make the iterator `final`
181 template <input_range _View>
182 requires view<_View> && input_range<range_reference_t<_View>>
183 template <bool _Const>
184 struct join_view<_View>::__iterator final : public __join_view_iterator_category<__maybe_const<_Const, _View>> {
185 friend join_view;
187 template <class>
188 friend struct std::__segmented_iterator_traits;
190 static constexpr bool __is_join_view_iterator = true;
192 private:
193 using _Parent = __maybe_const<_Const, join_view<_View>>;
194 using _Base = __maybe_const<_Const, _View>;
195 using _Outer = iterator_t<_Base>;
196 using _Inner = iterator_t<range_reference_t<_Base>>;
197 using _InnerRange = range_reference_t<_View>;
199 static_assert(!_Const || forward_range<_Base>, "Const can only be true when Base models forward_range.");
201 static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>;
203 static constexpr bool _OuterPresent = forward_range<_Base>;
204 using _OuterType = _If<_OuterPresent, _Outer, std::__empty>;
205 _LIBCPP_NO_UNIQUE_ADDRESS _OuterType __outer_ = _OuterType();
207 optional<_Inner> __inner_;
208 _Parent* __parent_ = nullptr;
210 _LIBCPP_HIDE_FROM_ABI constexpr void __satisfy() {
211 for (; __get_outer() != ranges::end(__parent_->__base_); ++__get_outer()) {
212 auto&& __inner = [this]() -> auto&& {
213 if constexpr (__ref_is_glvalue)
214 return *__get_outer();
215 else
216 return __parent_->__inner_.__emplace_from([&]() -> decltype(auto) { return *__get_outer(); });
217 }();
218 __inner_ = ranges::begin(__inner);
219 if (*__inner_ != ranges::end(__inner))
220 return;
223 if constexpr (__ref_is_glvalue)
224 __inner_.reset();
227 _LIBCPP_HIDE_FROM_ABI constexpr _Outer& __get_outer() {
228 if constexpr (forward_range<_Base>) {
229 return __outer_;
230 } else {
231 return *__parent_->__outer_;
235 _LIBCPP_HIDE_FROM_ABI constexpr const _Outer& __get_outer() const {
236 if constexpr (forward_range<_Base>) {
237 return __outer_;
238 } else {
239 return *__parent_->__outer_;
243 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent& __parent, _Outer __outer)
244 requires forward_range<_Base>
245 : __outer_(std::move(__outer)), __parent_(std::addressof(__parent)) {
246 __satisfy();
249 _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(_Parent& __parent)
250 requires(!forward_range<_Base>)
251 : __parent_(std::addressof(__parent)) {
252 __satisfy();
255 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent* __parent, _Outer __outer, _Inner __inner)
256 requires forward_range<_Base>
257 : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {}
259 public:
260 using iterator_concept =
261 _If< __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
262 common_range<range_reference_t<_Base>>,
263 bidirectional_iterator_tag,
264 _If< __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>,
265 forward_iterator_tag,
266 input_iterator_tag > >;
268 using value_type = range_value_t<range_reference_t<_Base>>;
270 using difference_type = common_type_t< range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>;
272 _LIBCPP_HIDE_FROM_ABI __iterator() = default;
274 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i)
275 requires _Const && convertible_to<iterator_t<_View>, _Outer> && convertible_to<iterator_t<_InnerRange>, _Inner>
276 : __outer_(std::move(__i.__outer_)), __inner_(std::move(__i.__inner_)), __parent_(__i.__parent_) {}
278 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const { return **__inner_; }
280 _LIBCPP_HIDE_FROM_ABI constexpr _Inner operator->() const
281 requires __has_arrow<_Inner> && copyable<_Inner>
283 return *__inner_;
286 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
287 auto __get_inner_range = [&]() -> decltype(auto) {
288 if constexpr (__ref_is_glvalue)
289 return *__get_outer();
290 else
291 return *__parent_->__inner_;
293 if (++*__inner_ == ranges::end(std::__as_lvalue(__get_inner_range()))) {
294 ++__get_outer();
295 __satisfy();
297 return *this;
300 _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; }
302 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)
303 requires __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>
305 auto __tmp = *this;
306 ++*this;
307 return __tmp;
310 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()
311 requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
312 common_range<range_reference_t<_Base>>
314 if (__outer_ == ranges::end(__parent_->__base_))
315 __inner_ = ranges::end(std::__as_lvalue(*--__outer_));
317 // Skip empty inner ranges when going backwards.
318 while (*__inner_ == ranges::begin(std::__as_lvalue(*__outer_))) {
319 __inner_ = ranges::end(std::__as_lvalue(*--__outer_));
322 --*__inner_;
323 return *this;
326 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)
327 requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
328 common_range<range_reference_t<_Base>>
330 auto __tmp = *this;
331 --*this;
332 return __tmp;
335 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
336 requires __ref_is_glvalue && forward_range<_Base> && equality_comparable<iterator_t<range_reference_t<_Base>>>
338 return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_;
341 _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)
342 iter_move(const __iterator& __i) noexcept(noexcept(ranges::iter_move(*__i.__inner_))) {
343 return ranges::iter_move(*__i.__inner_);
346 _LIBCPP_HIDE_FROM_ABI friend constexpr void
347 iter_swap(const __iterator& __x,
348 const __iterator& __y) noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_)))
349 requires indirectly_swappable<_Inner>
351 return ranges::iter_swap(*__x.__inner_, *__y.__inner_);
355 template <class _Range>
356 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
358 namespace views {
359 namespace __join_view {
360 struct __fn : __range_adaptor_closure<__fn> {
361 template <class _Range>
362 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
363 noexcept(noexcept(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))))
364 -> decltype(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))) {
365 return join_view<all_t<_Range&&>>(std::forward<_Range>(__range));
368 } // namespace __join_view
369 inline namespace __cpo {
370 inline constexpr auto join = __join_view::__fn{};
371 } // namespace __cpo
372 } // namespace views
373 } // namespace ranges
375 template <class _JoinViewIterator>
376 requires(_JoinViewIterator::__is_join_view_iterator && ranges::common_range<typename _JoinViewIterator::_Parent> &&
377 __has_random_access_iterator_category<typename _JoinViewIterator::_Outer>::value &&
378 __has_random_access_iterator_category<typename _JoinViewIterator::_Inner>::value)
379 struct __segmented_iterator_traits<_JoinViewIterator> {
380 using __segment_iterator =
381 _LIBCPP_NODEBUG __iterator_with_data<typename _JoinViewIterator::_Outer, typename _JoinViewIterator::_Parent*>;
382 using __local_iterator = typename _JoinViewIterator::_Inner;
384 // TODO: Would it make sense to enable the optimization for other iterator types?
386 static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) {
387 if (ranges::empty(__iter.__parent_->__base_))
388 return {};
389 if (!__iter.__inner_.has_value())
390 return __segment_iterator(--__iter.__outer_, __iter.__parent_);
391 return __segment_iterator(__iter.__outer_, __iter.__parent_);
394 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) {
395 if (ranges::empty(__iter.__parent_->__base_))
396 return {};
397 if (!__iter.__inner_.has_value())
398 return ranges::end(*--__iter.__outer_);
399 return *__iter.__inner_;
402 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) {
403 return ranges::begin(*__iter.__get_iter());
406 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {
407 return ranges::end(*__iter.__get_iter());
410 static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator
411 __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) {
412 return _JoinViewIterator(
413 std::move(__seg_iter).__get_data(), std::move(__seg_iter).__get_iter(), std::move(__local_iter));
417 #endif // #if _LIBCPP_STD_VER >= 20
419 _LIBCPP_END_NAMESPACE_STD
421 _LIBCPP_POP_MACROS
423 #endif // _LIBCPP___RANGES_JOIN_VIEW_H