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