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