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