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