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