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