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_DROP_VIEW_H 11 #define _LIBCPP___RANGES_DROP_VIEW_H 12 13 #include <__algorithm/min.h> 14 #include <__assert> 15 #include <__concepts/constructible.h> 16 #include <__concepts/convertible_to.h> 17 #include <__config> 18 #include <__functional/bind_back.h> 19 #include <__fwd/span.h> 20 #include <__fwd/string_view.h> 21 #include <__iterator/concepts.h> 22 #include <__iterator/distance.h> 23 #include <__iterator/iterator_traits.h> 24 #include <__iterator/next.h> 25 #include <__ranges/access.h> 26 #include <__ranges/all.h> 27 #include <__ranges/concepts.h> 28 #include <__ranges/empty_view.h> 29 #include <__ranges/enable_borrowed_range.h> 30 #include <__ranges/iota_view.h> 31 #include <__ranges/non_propagating_cache.h> 32 #include <__ranges/range_adaptor.h> 33 #include <__ranges/repeat_view.h> 34 #include <__ranges/size.h> 35 #include <__ranges/subrange.h> 36 #include <__ranges/view_interface.h> 37 #include <__type_traits/conditional.h> 38 #include <__type_traits/decay.h> 39 #include <__type_traits/is_nothrow_constructible.h> 40 #include <__type_traits/make_unsigned.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 template<view _View> 60 class drop_view 61 : public view_interface<drop_view<_View>> 62 { 63 // We cache begin() whenever ranges::next is not guaranteed O(1) to provide an 64 // amortized O(1) begin() method. If this is an input_range, then we cannot cache 65 // begin because begin is not equality preserving. 66 // Note: drop_view<input-range>::begin() is still trivially amortized O(1) because 67 // one can't call begin() on it more than once. 68 static constexpr bool _UseCache = forward_range<_View> && !(random_access_range<_View> && sized_range<_View>); 69 using _Cache = _If<_UseCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>; 70 _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cached_begin_ = _Cache(); 71 range_difference_t<_View> __count_ = 0; 72 _View __base_ = _View(); 73 74 public: 75 _LIBCPP_HIDE_FROM_ABI drop_view() requires default_initializable<_View> = default; 76 77 _LIBCPP_HIDE_FROM_ABI 78 constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 drop_view(_View __base, range_difference_t<_View> __count) 79 : __count_(__count) 80 , __base_(std::move(__base)) 81 { 82 _LIBCPP_ASSERT_UNCATEGORIZED(__count_ >= 0, "count must be greater than or equal to zero."); 83 } 84 85 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& requires copy_constructible<_View> { return __base_; } 86 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 87 88 _LIBCPP_HIDE_FROM_ABI 89 constexpr auto begin() 90 requires (!(__simple_view<_View> && 91 random_access_range<const _View> && sized_range<const _View>)) 92 { 93 if constexpr (_UseCache) 94 if (__cached_begin_.__has_value()) 95 return *__cached_begin_; 96 97 auto __tmp = ranges::next(ranges::begin(__base_), __count_, ranges::end(__base_)); 98 if constexpr (_UseCache) 99 __cached_begin_.__emplace(__tmp); 100 return __tmp; 101 } 102 103 _LIBCPP_HIDE_FROM_ABI 104 constexpr auto begin() const 105 requires random_access_range<const _View> && sized_range<const _View> 106 { 107 return ranges::next(ranges::begin(__base_), __count_, ranges::end(__base_)); 108 } 109 110 _LIBCPP_HIDE_FROM_ABI 111 constexpr auto end() 112 requires (!__simple_view<_View>) 113 { return ranges::end(__base_); } 114 115 _LIBCPP_HIDE_FROM_ABI 116 constexpr auto end() const 117 requires range<const _View> 118 { return ranges::end(__base_); } 119 120 _LIBCPP_HIDE_FROM_ABI 121 static constexpr auto __size(auto& __self) { 122 const auto __s = ranges::size(__self.__base_); 123 const auto __c = static_cast<decltype(__s)>(__self.__count_); 124 return __s < __c ? 0 : __s - __c; 125 } 126 127 _LIBCPP_HIDE_FROM_ABI 128 constexpr auto size() 129 requires sized_range<_View> 130 { return __size(*this); } 131 132 _LIBCPP_HIDE_FROM_ABI 133 constexpr auto size() const 134 requires sized_range<const _View> 135 { return __size(*this); } 136 }; 137 138 template<class _Range> 139 drop_view(_Range&&, range_difference_t<_Range>) -> drop_view<views::all_t<_Range>>; 140 141 template<class _Tp> 142 inline constexpr bool enable_borrowed_range<drop_view<_Tp>> = enable_borrowed_range<_Tp>; 143 144 namespace views { 145 namespace __drop { 146 147 template <class _Tp> 148 inline constexpr bool __is_empty_view = false; 149 150 template <class _Tp> 151 inline constexpr bool __is_empty_view<empty_view<_Tp>> = true; 152 153 template <class _Tp> 154 inline constexpr bool __is_passthrough_specialization = false; 155 156 template <class _Tp, size_t _Extent> 157 inline constexpr bool __is_passthrough_specialization<span<_Tp, _Extent>> = true; 158 159 template <class _CharT, class _Traits> 160 inline constexpr bool __is_passthrough_specialization<basic_string_view<_CharT, _Traits>> = true; 161 162 template <class _Np, class _Bound> 163 inline constexpr bool __is_passthrough_specialization<iota_view<_Np, _Bound>> = true; 164 165 template <class _Iter, class _Sent, subrange_kind _Kind> 166 inline constexpr bool __is_passthrough_specialization<subrange<_Iter, _Sent, _Kind>> = 167 !subrange<_Iter, _Sent, _Kind>::_StoreSize; 168 169 template <class _Tp> 170 inline constexpr bool __is_subrange_specialization_with_store_size = false; 171 172 template <class _Iter, class _Sent, subrange_kind _Kind> 173 inline constexpr bool __is_subrange_specialization_with_store_size<subrange<_Iter, _Sent, _Kind>> = 174 subrange<_Iter, _Sent, _Kind>::_StoreSize; 175 176 template <class _Tp> 177 struct __passthrough_type; 178 179 template <class _Tp, size_t _Extent> 180 struct __passthrough_type<span<_Tp, _Extent>> { 181 using type = span<_Tp>; 182 }; 183 184 template <class _CharT, class _Traits> 185 struct __passthrough_type<basic_string_view<_CharT, _Traits>> { 186 using type = basic_string_view<_CharT, _Traits>; 187 }; 188 189 template <class _Np, class _Bound> 190 struct __passthrough_type<iota_view<_Np, _Bound>> { 191 using type = iota_view<_Np, _Bound>; 192 }; 193 194 template <class _Iter, class _Sent, subrange_kind _Kind> 195 struct __passthrough_type<subrange<_Iter, _Sent, _Kind>> { 196 using type = subrange<_Iter, _Sent, _Kind>; 197 }; 198 199 template <class _Tp> 200 using __passthrough_type_t = typename __passthrough_type<_Tp>::type; 201 202 struct __fn { 203 // [range.drop.overview]: the `empty_view` case. 204 template <class _Range, convertible_to<range_difference_t<_Range>> _Np> 205 requires __is_empty_view<remove_cvref_t<_Range>> 206 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 207 constexpr auto operator()(_Range&& __range, _Np&&) const 208 noexcept(noexcept(_LIBCPP_AUTO_CAST(std::forward<_Range>(__range)))) 209 -> decltype( _LIBCPP_AUTO_CAST(std::forward<_Range>(__range))) 210 { return _LIBCPP_AUTO_CAST(std::forward<_Range>(__range)); } 211 212 // [range.drop.overview]: the `span | basic_string_view | iota_view | subrange (StoreSize == false)` case. 213 template <class _Range, 214 convertible_to<range_difference_t<_Range>> _Np, 215 class _RawRange = remove_cvref_t<_Range>, 216 class _Dist = range_difference_t<_Range>> 217 requires (!__is_empty_view<_RawRange> && 218 random_access_range<_RawRange> && 219 sized_range<_RawRange> && 220 __is_passthrough_specialization<_RawRange>) 221 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 222 constexpr auto operator()(_Range&& __rng, _Np&& __n) const 223 noexcept(noexcept(__passthrough_type_t<_RawRange>( 224 ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), 225 ranges::end(__rng) 226 ))) 227 -> decltype( __passthrough_type_t<_RawRange>( 228 // Note: deliberately not forwarding `__rng` to guard against double moves. 229 ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), 230 ranges::end(__rng) 231 )) 232 { return __passthrough_type_t<_RawRange>( 233 ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), 234 ranges::end(__rng) 235 ); } 236 237 // [range.drop.overview]: the `subrange (StoreSize == true)` case. 238 template <class _Range, 239 convertible_to<range_difference_t<_Range>> _Np, 240 class _RawRange = remove_cvref_t<_Range>, 241 class _Dist = range_difference_t<_Range>> 242 requires (!__is_empty_view<_RawRange> && 243 random_access_range<_RawRange> && 244 sized_range<_RawRange> && 245 __is_subrange_specialization_with_store_size<_RawRange>) 246 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 247 constexpr auto operator()(_Range&& __rng, _Np&& __n) const 248 noexcept(noexcept(_RawRange( 249 ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), 250 ranges::end(__rng), 251 std::__to_unsigned_like(ranges::distance(__rng) - 252 std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))) 253 ))) 254 -> decltype( _RawRange( 255 // Note: deliberately not forwarding `__rng` to guard against double moves. 256 ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), 257 ranges::end(__rng), 258 std::__to_unsigned_like(ranges::distance(__rng) - 259 std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))) 260 )) 261 { 262 // Introducing local variables avoids calculating `min` and `distance` twice (at the cost of diverging from the 263 // expression used in the `noexcept` clause and the return statement). 264 auto __dist = ranges::distance(__rng); 265 auto __clamped = std::min<_Dist>(__dist, std::forward<_Np>(__n)); 266 return _RawRange( 267 ranges::begin(__rng) + __clamped, 268 ranges::end(__rng), 269 std::__to_unsigned_like(__dist - __clamped) 270 );} 271 // clang-format off 272 #if _LIBCPP_STD_VER >= 23 273 // [range.drop.overview]: the `repeat_view` "_RawRange models sized_range" case. 274 template <class _Range, 275 convertible_to<range_difference_t<_Range>> _Np, 276 class _RawRange = remove_cvref_t<_Range>, 277 class _Dist = range_difference_t<_Range>> 278 requires (__is_repeat_specialization<_RawRange> && sized_range<_RawRange>) 279 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Np&& __n) const 280 noexcept(noexcept(views::repeat(*__range.__value_, ranges::distance(__range) - std::min<_Dist>(ranges::distance(__range), std::forward<_Np>(__n))))) 281 -> decltype( views::repeat(*__range.__value_, ranges::distance(__range) - std::min<_Dist>(ranges::distance(__range), std::forward<_Np>(__n)))) 282 { return views::repeat(*__range.__value_, ranges::distance(__range) - std::min<_Dist>(ranges::distance(__range), std::forward<_Np>(__n))); } 283 284 // [range.drop.overview]: the `repeat_view` "otherwise" case. 285 template <class _Range, 286 convertible_to<range_difference_t<_Range>> _Np, 287 class _RawRange = remove_cvref_t<_Range>, 288 class _Dist = range_difference_t<_Range>> 289 requires (__is_repeat_specialization<_RawRange> && !sized_range<_RawRange>) 290 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI 291 constexpr auto operator()(_Range&& __range, _Np&&) const 292 noexcept(noexcept(_LIBCPP_AUTO_CAST(std::forward<_Range>(__range)))) 293 -> decltype( _LIBCPP_AUTO_CAST(std::forward<_Range>(__range))) 294 { return _LIBCPP_AUTO_CAST(std::forward<_Range>(__range)); } 295 #endif 296 // clang-format on 297 298 // [range.drop.overview]: the "otherwise" case. 299 template <class _Range, convertible_to<range_difference_t<_Range>> _Np, 300 class _RawRange = remove_cvref_t<_Range>> 301 // Note: without specifically excluding the other cases, GCC sees this overload as ambiguous with the other 302 // overloads. 303 requires (!(__is_empty_view<_RawRange> || 304 #if _LIBCPP_STD_VER >= 23 305 __is_repeat_specialization<_RawRange> || 306 #endif 307 (__is_subrange_specialization_with_store_size<_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(drop_view(std::forward<_Range>(__range), std::forward<_Np>(__n)))) 317 -> decltype( drop_view(std::forward<_Range>(__range), std::forward<_Np>(__n))) 318 { return drop_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 __drop 329 330 inline namespace __cpo { 331 inline constexpr auto drop = __drop::__fn{}; 332 } // namespace __cpo 333 } // namespace views 334 335 } // namespace ranges 336 337 #endif // _LIBCPP_STD_VER >= 20 338 339 _LIBCPP_END_NAMESPACE_STD 340 341 _LIBCPP_POP_MACROS 342 343 #endif // _LIBCPP___RANGES_DROP_VIEW_H 344