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 #ifndef _LIBCPP___RANGES_TAKE_VIEW_H
10 #define _LIBCPP___RANGES_TAKE_VIEW_H
11 
12 #include <__algorithm/min.h>
13 #include <__algorithm/ranges_min.h>
14 #include <__config>
15 #include <__functional/bind_back.h>
16 #include <__fwd/span.h>
17 #include <__fwd/string_view.h>
18 #include <__iterator/concepts.h>
19 #include <__iterator/counted_iterator.h>
20 #include <__iterator/default_sentinel.h>
21 #include <__iterator/distance.h>
22 #include <__iterator/iterator_traits.h>
23 #include <__ranges/access.h>
24 #include <__ranges/all.h>
25 #include <__ranges/concepts.h>
26 #include <__ranges/empty_view.h>
27 #include <__ranges/enable_borrowed_range.h>
28 #include <__ranges/iota_view.h>
29 #include <__ranges/range_adaptor.h>
30 #include <__ranges/size.h>
31 #include <__ranges/subrange.h>
32 #include <__ranges/view_interface.h>
33 #include <__utility/auto_cast.h>
34 #include <__utility/forward.h>
35 #include <__utility/move.h>
36 #include <concepts>
37 #include <type_traits>
38 
39 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
40 #  pragma GCC system_header
41 #endif
42 
43 _LIBCPP_PUSH_MACROS
44 #include <__undef_macros>
45 
46 _LIBCPP_BEGIN_NAMESPACE_STD
47 
48 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
49 
50 namespace ranges {
51 
52 template<view _View>
53 class take_view : public view_interface<take_view<_View>> {
54   _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
55   range_difference_t<_View> __count_ = 0;
56 
57   template<bool> class __sentinel;
58 
59 public:
60   _LIBCPP_HIDE_FROM_ABI
61   take_view() requires default_initializable<_View> = default;
62 
63   _LIBCPP_HIDE_FROM_ABI
64   constexpr take_view(_View __base, range_difference_t<_View> __count)
65     : __base_(std::move(__base)), __count_(__count) {}
66 
67   _LIBCPP_HIDE_FROM_ABI
68   constexpr _View base() const& requires copy_constructible<_View> { return __base_; }
69 
70   _LIBCPP_HIDE_FROM_ABI
71   constexpr _View base() && { return std::move(__base_); }
72 
73   _LIBCPP_HIDE_FROM_ABI
74   constexpr auto begin() requires (!__simple_view<_View>) {
75     if constexpr (sized_range<_View>) {
76       if constexpr (random_access_range<_View>) {
77         return ranges::begin(__base_);
78       } else {
79         using _DifferenceT = range_difference_t<_View>;
80         auto __size = size();
81         return counted_iterator(ranges::begin(__base_), static_cast<_DifferenceT>(__size));
82       }
83     } else {
84       return counted_iterator(ranges::begin(__base_), __count_);
85     }
86   }
87 
88   _LIBCPP_HIDE_FROM_ABI
89   constexpr auto begin() const requires range<const _View> {
90     if constexpr (sized_range<const _View>) {
91       if constexpr (random_access_range<const _View>) {
92         return ranges::begin(__base_);
93       } else {
94         using _DifferenceT = range_difference_t<const _View>;
95         auto __size = size();
96         return counted_iterator(ranges::begin(__base_), static_cast<_DifferenceT>(__size));
97       }
98     } else {
99       return counted_iterator(ranges::begin(__base_), __count_);
100     }
101   }
102 
103   _LIBCPP_HIDE_FROM_ABI
104   constexpr auto end() requires (!__simple_view<_View>) {
105     if constexpr (sized_range<_View>) {
106       if constexpr (random_access_range<_View>) {
107         return ranges::begin(__base_) + size();
108       } else {
109         return default_sentinel;
110       }
111     } else {
112       return __sentinel<false>{ranges::end(__base_)};
113     }
114   }
115 
116   _LIBCPP_HIDE_FROM_ABI
117   constexpr auto end() const requires range<const _View> {
118     if constexpr (sized_range<const _View>) {
119       if constexpr (random_access_range<const _View>) {
120         return ranges::begin(__base_) + size();
121       } else {
122         return default_sentinel;
123       }
124     } else {
125       return __sentinel<true>{ranges::end(__base_)};
126     }
127   }
128 
129   _LIBCPP_HIDE_FROM_ABI
130   constexpr auto size() requires sized_range<_View> {
131     auto __n = ranges::size(__base_);
132     return ranges::min(__n, static_cast<decltype(__n)>(__count_));
133   }
134 
135   _LIBCPP_HIDE_FROM_ABI
136   constexpr auto size() const requires sized_range<const _View> {
137     auto __n = ranges::size(__base_);
138     return ranges::min(__n, static_cast<decltype(__n)>(__count_));
139   }
140 };
141 
142 template<view _View>
143 template<bool _Const>
144 class take_view<_View>::__sentinel {
145   using _Base = __maybe_const<_Const, _View>;
146   template<bool _OtherConst>
147   using _Iter = counted_iterator<iterator_t<__maybe_const<_OtherConst, _View>>>;
148   _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_Base> __end_ = sentinel_t<_Base>();
149 
150   template<bool>
151   friend class take_view<_View>::__sentinel;
152 
153 public:
154   _LIBCPP_HIDE_FROM_ABI
155   __sentinel() = default;
156 
157   _LIBCPP_HIDE_FROM_ABI
158   constexpr explicit __sentinel(sentinel_t<_Base> __end) : __end_(std::move(__end)) {}
159 
160   _LIBCPP_HIDE_FROM_ABI
161   constexpr __sentinel(__sentinel<!_Const> __s)
162     requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
163     : __end_(std::move(__s.__end_)) {}
164 
165   _LIBCPP_HIDE_FROM_ABI
166   constexpr sentinel_t<_Base> base() const { return __end_; }
167 
168   _LIBCPP_HIDE_FROM_ABI
169   friend constexpr bool operator==(const _Iter<_Const>& __lhs, const __sentinel& __rhs) {
170     return __lhs.count() == 0 || __lhs.base() == __rhs.__end_;
171   }
172 
173   template<bool _OtherConst = !_Const>
174     requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
175   _LIBCPP_HIDE_FROM_ABI
176   friend constexpr bool operator==(const _Iter<_Const>& __lhs, const __sentinel& __rhs) {
177     return __lhs.count() == 0 || __lhs.base() == __rhs.__end_;
178   }
179 };
180 
181 template<class _Range>
182 take_view(_Range&&, range_difference_t<_Range>) -> take_view<views::all_t<_Range>>;
183 
184 template<class _Tp>
185 inline constexpr bool enable_borrowed_range<take_view<_Tp>> = enable_borrowed_range<_Tp>;
186 
187 namespace views {
188 namespace __take {
189 
190 template <class _Tp>
191 inline constexpr bool __is_empty_view = false;
192 
193 template <class _Tp>
194 inline constexpr bool __is_empty_view<empty_view<_Tp>> = true;
195 
196 template <class _Tp>
197 inline constexpr bool __is_passthrough_specialization = false;
198 
199 template <class _Tp, size_t _Extent>
200 inline constexpr bool __is_passthrough_specialization<span<_Tp, _Extent>> = true;
201 
202 template <class _CharT, class _Traits>
203 inline constexpr bool __is_passthrough_specialization<basic_string_view<_CharT, _Traits>> = true;
204 
205 template <class _Iter, class _Sent, subrange_kind _Kind>
206 inline constexpr bool __is_passthrough_specialization<subrange<_Iter, _Sent, _Kind>> = true;
207 
208 template <class _Tp>
209 inline constexpr bool __is_iota_specialization = false;
210 
211 template <class _Np, class _Bound>
212 inline constexpr bool __is_iota_specialization<iota_view<_Np, _Bound>> = true;
213 
214 template <class _Tp>
215 struct __passthrough_type;
216 
217 template <class _Tp, size_t _Extent>
218 struct __passthrough_type<span<_Tp, _Extent>> {
219   using type = span<_Tp>;
220 };
221 
222 template <class _CharT, class _Traits>
223 struct __passthrough_type<basic_string_view<_CharT, _Traits>> {
224   using type = basic_string_view<_CharT, _Traits>;
225 };
226 
227 template <class _Iter, class _Sent, subrange_kind _Kind>
228 struct __passthrough_type<subrange<_Iter, _Sent, _Kind>> {
229   using type = subrange<_Iter>;
230 };
231 
232 template <class _Tp>
233 using __passthrough_type_t = typename __passthrough_type<_Tp>::type;
234 
235 struct __fn {
236   // [range.take.overview]: the `empty_view` case.
237   template <class _Range, convertible_to<range_difference_t<_Range>> _Np>
238     requires __is_empty_view<remove_cvref_t<_Range>>
239   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
240   constexpr auto operator()(_Range&& __range, _Np&&) const
241     noexcept(noexcept(_LIBCPP_AUTO_CAST(std::forward<_Range>(__range))))
242     -> decltype(      _LIBCPP_AUTO_CAST(std::forward<_Range>(__range)))
243     { return          _LIBCPP_AUTO_CAST(std::forward<_Range>(__range)); }
244 
245   // [range.take.overview]: the `span | basic_string_view | subrange` case.
246   template <class _Range,
247             convertible_to<range_difference_t<_Range>> _Np,
248             class _RawRange = remove_cvref_t<_Range>,
249             class _Dist = range_difference_t<_Range>>
250     requires (!__is_empty_view<_RawRange> &&
251               random_access_range<_RawRange> &&
252               sized_range<_RawRange> &&
253               __is_passthrough_specialization<_RawRange>)
254   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
255   constexpr auto operator()(_Range&& __rng, _Np&& __n) const
256     noexcept(noexcept(__passthrough_type_t<_RawRange>(
257                               ranges::begin(__rng),
258                               ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))
259                               )))
260     -> decltype(      __passthrough_type_t<_RawRange>(
261                               // Note: deliberately not forwarding `__rng` to guard against double moves.
262                               ranges::begin(__rng),
263                               ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))
264                               ))
265     { return          __passthrough_type_t<_RawRange>(
266                               ranges::begin(__rng),
267                               ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))
268                               ); }
269 
270   // [range.take.overview]: the `iota_view` case.
271   template <class _Range,
272             convertible_to<range_difference_t<_Range>> _Np,
273             class _RawRange = remove_cvref_t<_Range>,
274             class _Dist = range_difference_t<_Range>>
275     requires (!__is_empty_view<_RawRange> &&
276               random_access_range<_RawRange> &&
277               sized_range<_RawRange> &&
278               __is_iota_specialization<_RawRange>)
279   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
280   constexpr auto operator()(_Range&& __rng, _Np&& __n) const
281     noexcept(noexcept(ranges::iota_view(
282                               *ranges::begin(__rng),
283                               *ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))
284                               )))
285     -> decltype(      ranges::iota_view(
286                               // Note: deliberately not forwarding `__rng` to guard against double moves.
287                               *ranges::begin(__rng),
288                               *ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))
289                               ))
290     { return          ranges::iota_view(
291                               *ranges::begin(__rng),
292                               *ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))
293                               ); }
294 
295   // [range.take.overview]: the "otherwise" case.
296   template <class _Range, convertible_to<range_difference_t<_Range>> _Np,
297             class _RawRange = remove_cvref_t<_Range>>
298     // Note: without specifically excluding the other cases, GCC sees this overload as ambiguous with the other
299     // overloads.
300     requires (!(__is_empty_view<_RawRange> ||
301                (__is_iota_specialization<_RawRange> &&
302                 sized_range<_RawRange> &&
303                 random_access_range<_RawRange>) ||
304                (__is_passthrough_specialization<_RawRange> &&
305                 sized_range<_RawRange> &&
306                 random_access_range<_RawRange>)
307              ))
308   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
309   constexpr auto operator()(_Range&& __range, _Np&& __n) const
310     noexcept(noexcept(take_view(std::forward<_Range>(__range), std::forward<_Np>(__n))))
311     -> decltype(      take_view(std::forward<_Range>(__range), std::forward<_Np>(__n)))
312     { return          take_view(std::forward<_Range>(__range), std::forward<_Np>(__n)); }
313 
314   template <class _Np>
315     requires constructible_from<decay_t<_Np>, _Np>
316   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
317   constexpr auto operator()(_Np&& __n) const
318     noexcept(is_nothrow_constructible_v<decay_t<_Np>, _Np>)
319   { return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Np>(__n))); }
320 };
321 
322 } // namespace __take
323 
324 inline namespace __cpo {
325   inline constexpr auto take = __take::__fn{};
326 } // namespace __cpo
327 } // namespace views
328 
329 } // namespace ranges
330 
331 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
332 
333 _LIBCPP_END_NAMESPACE_STD
334 
335 _LIBCPP_POP_MACROS
336 
337 #endif // _LIBCPP___RANGES_TAKE_VIEW_H
338