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