Run DCE after a LoopFlatten test to reduce spurious output [nfc]
[llvm-project.git] / libcxx / include / __ranges / zip_view.h
blob2fd1fb30475ab34cf2d21fb28bc41adaae59bcbf
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_ZIP_VIEW_H
11 #define _LIBCPP___RANGES_ZIP_VIEW_H
13 #include <__config>
15 #include <__algorithm/ranges_min.h>
16 #include <__compare/three_way_comparable.h>
17 #include <__concepts/convertible_to.h>
18 #include <__concepts/equality_comparable.h>
19 #include <__functional/invoke.h>
20 #include <__functional/operations.h>
21 #include <__iterator/concepts.h>
22 #include <__iterator/incrementable_traits.h>
23 #include <__iterator/iter_move.h>
24 #include <__iterator/iter_swap.h>
25 #include <__iterator/iterator_traits.h>
26 #include <__ranges/access.h>
27 #include <__ranges/all.h>
28 #include <__ranges/concepts.h>
29 #include <__ranges/empty_view.h>
30 #include <__ranges/enable_borrowed_range.h>
31 #include <__ranges/size.h>
32 #include <__ranges/view_interface.h>
33 #include <__type_traits/is_nothrow_move_constructible.h>
34 #include <__type_traits/make_unsigned.h>
35 #include <__utility/declval.h>
36 #include <__utility/forward.h>
37 #include <__utility/integer_sequence.h>
38 #include <__utility/move.h>
39 #include <tuple>
41 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
42 # pragma GCC system_header
43 #endif
45 _LIBCPP_PUSH_MACROS
46 #include <__undef_macros>
48 _LIBCPP_BEGIN_NAMESPACE_STD
50 #if _LIBCPP_STD_VER >= 23
52 namespace ranges {
54 template <class... _Ranges>
55 concept __zip_is_common = (sizeof...(_Ranges) == 1 && (common_range<_Ranges> && ...)) ||
56 (!(bidirectional_range<_Ranges> && ...) && (common_range<_Ranges> && ...)) ||
57 ((random_access_range<_Ranges> && ...) && (sized_range<_Ranges> && ...));
59 template <typename _Tp, typename _Up>
60 auto __tuple_or_pair_test() -> pair<_Tp, _Up>;
62 template <typename... _Types>
63 requires(sizeof...(_Types) != 2)
64 auto __tuple_or_pair_test() -> tuple<_Types...>;
66 template <class... _Types>
67 using __tuple_or_pair = decltype(__tuple_or_pair_test<_Types...>());
69 template <class _Fun, class _Tuple>
70 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_transform(_Fun&& __f, _Tuple&& __tuple) {
71 return std::apply(
72 [&]<class... _Types>(_Types&&... __elements) {
73 return __tuple_or_pair<invoke_result_t<_Fun&, _Types>...>(
74 std::invoke(__f, std::forward<_Types>(__elements))...);
76 std::forward<_Tuple>(__tuple));
79 template <class _Fun, class _Tuple>
80 _LIBCPP_HIDE_FROM_ABI constexpr void __tuple_for_each(_Fun&& __f, _Tuple&& __tuple) {
81 std::apply(
82 [&]<class... _Types>(_Types&&... __elements) {
83 (static_cast<void>(std::invoke(__f, std::forward<_Types>(__elements))), ...);
85 std::forward<_Tuple>(__tuple));
88 template <class _Fun, class _Tuple1, class _Tuple2, size_t... _Indices>
89 _LIBCPP_HIDE_FROM_ABI constexpr __tuple_or_pair<
90 invoke_result_t<_Fun&, typename tuple_element<_Indices, remove_cvref_t<_Tuple1>>::type,
91 typename tuple_element<_Indices, remove_cvref_t<_Tuple2>>::type>...>
92 __tuple_zip_transform(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2, index_sequence<_Indices...>) {
93 return {std::invoke(__f, std::get<_Indices>(std::forward<_Tuple1>(__tuple1)),
94 std::get<_Indices>(std::forward<_Tuple2>(__tuple2)))...};
97 template <class _Fun, class _Tuple1, class _Tuple2>
98 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_zip_transform(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2) {
99 return ranges::__tuple_zip_transform(__f, std::forward<_Tuple1>(__tuple1), std::forward<_Tuple2>(__tuple2),
100 std::make_index_sequence<tuple_size<remove_cvref_t<_Tuple1>>::value>());
103 template <class _Fun, class _Tuple1, class _Tuple2, size_t... _Indices>
104 _LIBCPP_HIDE_FROM_ABI constexpr void __tuple_zip_for_each(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2,
105 index_sequence<_Indices...>) {
106 (std::invoke(__f, std::get<_Indices>(std::forward<_Tuple1>(__tuple1)),
107 std::get<_Indices>(std::forward<_Tuple2>(__tuple2))),
108 ...);
111 template <class _Fun, class _Tuple1, class _Tuple2>
112 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_zip_for_each(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2) {
113 return ranges::__tuple_zip_for_each(__f, std::forward<_Tuple1>(__tuple1), std::forward<_Tuple2>(__tuple2),
114 std::make_index_sequence<tuple_size<remove_cvref_t<_Tuple1>>::value>());
117 template <class _Tuple1, class _Tuple2>
118 _LIBCPP_HIDE_FROM_ABI constexpr bool __tuple_any_equals(const _Tuple1& __tuple1, const _Tuple2& __tuple2) {
119 const auto __equals = ranges::__tuple_zip_transform(std::equal_to<>(), __tuple1, __tuple2);
120 return std::apply([](auto... __bools) { return (__bools || ...); }, __equals);
123 // abs in cstdlib is not constexpr
124 // TODO : remove __abs once P0533R9 is implemented.
125 template <class _Tp>
126 _LIBCPP_HIDE_FROM_ABI constexpr _Tp __abs(_Tp __t) {
127 return __t < 0 ? -__t : __t;
130 template <input_range... _Views>
131 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
132 class zip_view : public view_interface<zip_view<_Views...>> {
134 _LIBCPP_NO_UNIQUE_ADDRESS tuple<_Views...> __views_;
136 template <bool>
137 class __iterator;
139 template <bool>
140 class __sentinel;
142 public:
143 _LIBCPP_HIDE_FROM_ABI
144 zip_view() = default;
146 _LIBCPP_HIDE_FROM_ABI
147 constexpr explicit zip_view(_Views... __views) : __views_(std::move(__views)...) {}
149 _LIBCPP_HIDE_FROM_ABI
150 constexpr auto begin()
151 requires(!(__simple_view<_Views> && ...)) {
152 return __iterator<false>(ranges::__tuple_transform(ranges::begin, __views_));
155 _LIBCPP_HIDE_FROM_ABI
156 constexpr auto begin() const
157 requires(range<const _Views> && ...) {
158 return __iterator<true>(ranges::__tuple_transform(ranges::begin, __views_));
161 _LIBCPP_HIDE_FROM_ABI
162 constexpr auto end()
163 requires(!(__simple_view<_Views> && ...)) {
164 if constexpr (!__zip_is_common<_Views...>) {
165 return __sentinel<false>(ranges::__tuple_transform(ranges::end, __views_));
166 } else if constexpr ((random_access_range<_Views> && ...)) {
167 return begin() + iter_difference_t<__iterator<false>>(size());
168 } else {
169 return __iterator<false>(ranges::__tuple_transform(ranges::end, __views_));
173 _LIBCPP_HIDE_FROM_ABI
174 constexpr auto end() const
175 requires(range<const _Views> && ...) {
176 if constexpr (!__zip_is_common<const _Views...>) {
177 return __sentinel<true>(ranges::__tuple_transform(ranges::end, __views_));
178 } else if constexpr ((random_access_range<const _Views> && ...)) {
179 return begin() + iter_difference_t<__iterator<true>>(size());
180 } else {
181 return __iterator<true>(ranges::__tuple_transform(ranges::end, __views_));
185 _LIBCPP_HIDE_FROM_ABI
186 constexpr auto size()
187 requires(sized_range<_Views> && ...) {
188 return std::apply(
189 [](auto... __sizes) {
190 using _CT = make_unsigned_t<common_type_t<decltype(__sizes)...>>;
191 return ranges::min({_CT(__sizes)...});
193 ranges::__tuple_transform(ranges::size, __views_));
196 _LIBCPP_HIDE_FROM_ABI
197 constexpr auto size() const
198 requires(sized_range<const _Views> && ...) {
199 return std::apply(
200 [](auto... __sizes) {
201 using _CT = make_unsigned_t<common_type_t<decltype(__sizes)...>>;
202 return ranges::min({_CT(__sizes)...});
204 ranges::__tuple_transform(ranges::size, __views_));
208 template <class... _Ranges>
209 zip_view(_Ranges&&...) -> zip_view<views::all_t<_Ranges>...>;
211 template <bool _Const, class... _Views>
212 concept __zip_all_random_access = (random_access_range<__maybe_const<_Const, _Views>> && ...);
214 template <bool _Const, class... _Views>
215 concept __zip_all_bidirectional = (bidirectional_range<__maybe_const<_Const, _Views>> && ...);
217 template <bool _Const, class... _Views>
218 concept __zip_all_forward = (forward_range<__maybe_const<_Const, _Views>> && ...);
220 template <bool _Const, class... _Views>
221 consteval auto __get_zip_view_iterator_tag() {
222 if constexpr (__zip_all_random_access<_Const, _Views...>) {
223 return random_access_iterator_tag();
224 } else if constexpr (__zip_all_bidirectional<_Const, _Views...>) {
225 return bidirectional_iterator_tag();
226 } else if constexpr (__zip_all_forward<_Const, _Views...>) {
227 return forward_iterator_tag();
228 } else {
229 return input_iterator_tag();
233 template <bool _Const, class... _Views>
234 struct __zip_view_iterator_category_base {};
236 template <bool _Const, class... _Views>
237 requires __zip_all_forward<_Const, _Views...>
238 struct __zip_view_iterator_category_base<_Const, _Views...> {
239 using iterator_category = input_iterator_tag;
242 template <input_range... _Views>
243 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
244 template <bool _Const>
245 class zip_view<_Views...>::__iterator : public __zip_view_iterator_category_base<_Const, _Views...> {
247 __tuple_or_pair<iterator_t<__maybe_const<_Const, _Views>>...> __current_;
249 _LIBCPP_HIDE_FROM_ABI
250 constexpr explicit __iterator(__tuple_or_pair<iterator_t<__maybe_const<_Const, _Views>>...> __current)
251 : __current_(std::move(__current)) {}
253 template <bool>
254 friend class zip_view<_Views...>::__iterator;
256 template <bool>
257 friend class zip_view<_Views...>::__sentinel;
259 friend class zip_view<_Views...>;
261 public:
262 using iterator_concept = decltype(__get_zip_view_iterator_tag<_Const, _Views...>());
263 using value_type = __tuple_or_pair<range_value_t<__maybe_const<_Const, _Views>>...>;
264 using difference_type = common_type_t<range_difference_t<__maybe_const<_Const, _Views>>...>;
266 _LIBCPP_HIDE_FROM_ABI
267 __iterator() = default;
269 _LIBCPP_HIDE_FROM_ABI
270 constexpr __iterator(__iterator<!_Const> __i)
271 requires _Const && (convertible_to<iterator_t<_Views>, iterator_t<__maybe_const<_Const, _Views>>> && ...)
272 : __current_(std::move(__i.__current_)) {}
274 _LIBCPP_HIDE_FROM_ABI
275 constexpr auto operator*() const {
276 return ranges::__tuple_transform([](auto& __i) -> decltype(auto) { return *__i; }, __current_);
279 _LIBCPP_HIDE_FROM_ABI
280 constexpr __iterator& operator++() {
281 ranges::__tuple_for_each([](auto& __i) { ++__i; }, __current_);
282 return *this;
285 _LIBCPP_HIDE_FROM_ABI
286 constexpr void operator++(int) { ++*this; }
288 _LIBCPP_HIDE_FROM_ABI
289 constexpr __iterator operator++(int)
290 requires __zip_all_forward<_Const, _Views...> {
291 auto __tmp = *this;
292 ++*this;
293 return __tmp;
296 _LIBCPP_HIDE_FROM_ABI
297 constexpr __iterator& operator--()
298 requires __zip_all_bidirectional<_Const, _Views...> {
299 ranges::__tuple_for_each([](auto& __i) { --__i; }, __current_);
300 return *this;
303 _LIBCPP_HIDE_FROM_ABI
304 constexpr __iterator operator--(int)
305 requires __zip_all_bidirectional<_Const, _Views...> {
306 auto __tmp = *this;
307 --*this;
308 return __tmp;
311 _LIBCPP_HIDE_FROM_ABI
312 constexpr __iterator& operator+=(difference_type __x)
313 requires __zip_all_random_access<_Const, _Views...> {
314 ranges::__tuple_for_each([&]<class _Iter>(_Iter& __i) { __i += iter_difference_t<_Iter>(__x); }, __current_);
315 return *this;
318 _LIBCPP_HIDE_FROM_ABI
319 constexpr __iterator& operator-=(difference_type __x)
320 requires __zip_all_random_access<_Const, _Views...> {
321 ranges::__tuple_for_each([&]<class _Iter>(_Iter& __i) { __i -= iter_difference_t<_Iter>(__x); }, __current_);
322 return *this;
325 _LIBCPP_HIDE_FROM_ABI
326 constexpr auto operator[](difference_type __n) const
327 requires __zip_all_random_access<_Const, _Views...> {
328 return ranges::__tuple_transform(
329 [&]<class _Iter>(_Iter& __i) -> decltype(auto) { return __i[iter_difference_t<_Iter>(__n)]; }, __current_);
332 _LIBCPP_HIDE_FROM_ABI
333 friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
334 requires(equality_comparable<iterator_t<__maybe_const<_Const, _Views>>> && ...) {
335 if constexpr (__zip_all_bidirectional<_Const, _Views...>) {
336 return __x.__current_ == __y.__current_;
337 } else {
338 return ranges::__tuple_any_equals(__x.__current_, __y.__current_);
342 _LIBCPP_HIDE_FROM_ABI
343 friend constexpr bool operator<(const __iterator& __x, const __iterator& __y)
344 requires __zip_all_random_access<_Const, _Views...> {
345 return __x.__current_ < __y.__current_;
348 _LIBCPP_HIDE_FROM_ABI
349 friend constexpr bool operator>(const __iterator& __x, const __iterator& __y)
350 requires __zip_all_random_access<_Const, _Views...> {
351 return __y < __x;
354 _LIBCPP_HIDE_FROM_ABI
355 friend constexpr bool operator<=(const __iterator& __x, const __iterator& __y)
356 requires __zip_all_random_access<_Const, _Views...> {
357 return !(__y < __x);
360 _LIBCPP_HIDE_FROM_ABI
361 friend constexpr bool operator>=(const __iterator& __x, const __iterator& __y)
362 requires __zip_all_random_access<_Const, _Views...> {
363 return !(__x < __y);
366 _LIBCPP_HIDE_FROM_ABI
367 friend constexpr auto operator<=>(const __iterator& __x, const __iterator& __y)
368 requires __zip_all_random_access<_Const, _Views...> &&
369 (three_way_comparable<iterator_t<__maybe_const<_Const, _Views>>> && ...) {
370 return __x.__current_ <=> __y.__current_;
373 _LIBCPP_HIDE_FROM_ABI
374 friend constexpr __iterator operator+(const __iterator& __i, difference_type __n)
375 requires __zip_all_random_access<_Const, _Views...> {
376 auto __r = __i;
377 __r += __n;
378 return __r;
381 _LIBCPP_HIDE_FROM_ABI
382 friend constexpr __iterator operator+(difference_type __n, const __iterator& __i)
383 requires __zip_all_random_access<_Const, _Views...> {
384 return __i + __n;
387 _LIBCPP_HIDE_FROM_ABI
388 friend constexpr __iterator operator-(const __iterator& __i, difference_type __n)
389 requires __zip_all_random_access<_Const, _Views...> {
390 auto __r = __i;
391 __r -= __n;
392 return __r;
395 _LIBCPP_HIDE_FROM_ABI
396 friend constexpr difference_type operator-(const __iterator& __x, const __iterator& __y)
397 requires(sized_sentinel_for<iterator_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_Const, _Views>>> &&
398 ...) {
399 const auto __diffs = ranges::__tuple_zip_transform(minus<>(), __x.__current_, __y.__current_);
400 return std::apply(
401 [](auto... __ds) {
402 return ranges::min({difference_type(__ds)...},
403 [](auto __a, auto __b) { return ranges::__abs(__a) < ranges::__abs(__b); });
405 __diffs);
408 _LIBCPP_HIDE_FROM_ABI
409 friend constexpr auto iter_move(const __iterator& __i) noexcept(
410 (noexcept(ranges::iter_move(std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>())) && ...) &&
411 (is_nothrow_move_constructible_v<range_rvalue_reference_t<__maybe_const<_Const, _Views>>> && ...)) {
412 return ranges::__tuple_transform(ranges::iter_move, __i.__current_);
415 _LIBCPP_HIDE_FROM_ABI
416 friend constexpr void iter_swap(const __iterator& __l, const __iterator& __r) noexcept(
417 (noexcept(ranges::iter_swap(std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>(),
418 std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>())) &&
419 ...))
420 requires(indirectly_swappable<iterator_t<__maybe_const<_Const, _Views>>> && ...) {
421 ranges::__tuple_zip_for_each(ranges::iter_swap, __l.__current_, __r.__current_);
425 template <input_range... _Views>
426 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
427 template <bool _Const>
428 class zip_view<_Views...>::__sentinel {
430 __tuple_or_pair<sentinel_t<__maybe_const<_Const, _Views>>...> __end_;
432 _LIBCPP_HIDE_FROM_ABI
433 constexpr explicit __sentinel(__tuple_or_pair<sentinel_t<__maybe_const<_Const, _Views>>...> __end) : __end_(__end) {}
435 friend class zip_view<_Views...>;
437 // hidden friend cannot access private member of iterator because they are friends of friends
438 template <bool _OtherConst>
439 _LIBCPP_HIDE_FROM_ABI static constexpr decltype(auto)
440 __iter_current(zip_view<_Views...>::__iterator<_OtherConst> const& __it) {
441 return (__it.__current_);
444 public:
445 _LIBCPP_HIDE_FROM_ABI
446 __sentinel() = default;
448 _LIBCPP_HIDE_FROM_ABI
449 constexpr __sentinel(__sentinel<!_Const> __i)
450 requires _Const && (convertible_to<sentinel_t<_Views>, sentinel_t<__maybe_const<_Const, _Views>>> && ...)
451 : __end_(std::move(__i.__end_)) {}
453 template <bool _OtherConst>
454 requires(sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
455 ...)
456 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
457 return ranges::__tuple_any_equals(__iter_current(__x), __y.__end_);
460 template <bool _OtherConst>
461 requires(
462 sized_sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
463 ...)
464 _LIBCPP_HIDE_FROM_ABI friend constexpr common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>
465 operator-(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
466 const auto __diffs = ranges::__tuple_zip_transform(minus<>(), __iter_current(__x), __y.__end_);
467 return std::apply(
468 [](auto... __ds) {
469 using _Diff = common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>;
470 return ranges::min({_Diff(__ds)...},
471 [](auto __a, auto __b) { return ranges::__abs(__a) < ranges::__abs(__b); });
473 __diffs);
476 template <bool _OtherConst>
477 requires(
478 sized_sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
479 ...)
480 _LIBCPP_HIDE_FROM_ABI friend constexpr common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>
481 operator-(const __sentinel& __y, const __iterator<_OtherConst>& __x) {
482 return -(__x - __y);
486 template <class... _Views>
487 inline constexpr bool enable_borrowed_range<zip_view<_Views...>> = (enable_borrowed_range<_Views> && ...);
489 namespace views {
490 namespace __zip {
492 struct __fn {
493 _LIBCPP_HIDE_FROM_ABI constexpr auto operator()() const noexcept { return empty_view<tuple<>>{}; }
495 template <class... _Ranges>
496 _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Ranges&&... __rs) const
497 noexcept(noexcept(zip_view<all_t<_Ranges&&>...>(std::forward<_Ranges>(__rs)...)))
498 -> decltype(zip_view<all_t<_Ranges&&>...>(std::forward<_Ranges>(__rs)...)) {
499 return zip_view<all_t<_Ranges>...>(std::forward<_Ranges>(__rs)...);
503 } // namespace __zip
504 inline namespace __cpo {
505 inline constexpr auto zip = __zip::__fn{};
506 } // namespace __cpo
507 } // namespace views
508 } // namespace ranges
510 #endif // _LIBCPP_STD_VER >= 23
512 _LIBCPP_END_NAMESPACE_STD
514 _LIBCPP_POP_MACROS
516 #endif // _LIBCPP___RANGES_ZIP_VIEW_H