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