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