330 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___RANGES_DROP_VIEW_H11#define _LIBCPP___RANGES_DROP_VIEW_H12 13#include <__algorithm/min.h>14#include <__assert>15#include <__concepts/constructible.h>16#include <__concepts/convertible_to.h>17#include <__config>18#include <__cstddef/size_t.h>19#include <__functional/bind_back.h>20#include <__fwd/span.h>21#include <__fwd/string_view.h>22#include <__iterator/concepts.h>23#include <__iterator/distance.h>24#include <__iterator/iterator_traits.h>25#include <__iterator/next.h>26#include <__ranges/access.h>27#include <__ranges/all.h>28#include <__ranges/concepts.h>29#include <__ranges/empty_view.h>30#include <__ranges/enable_borrowed_range.h>31#include <__ranges/iota_view.h>32#include <__ranges/non_propagating_cache.h>33#include <__ranges/range_adaptor.h>34#include <__ranges/repeat_view.h>35#include <__ranges/size.h>36#include <__ranges/subrange.h>37#include <__ranges/view_interface.h>38#include <__type_traits/conditional.h>39#include <__type_traits/decay.h>40#include <__type_traits/is_nothrow_constructible.h>41#include <__type_traits/make_unsigned.h>42#include <__type_traits/remove_cvref.h>43#include <__utility/auto_cast.h>44#include <__utility/forward.h>45#include <__utility/move.h>46 47#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)48# pragma GCC system_header49#endif50 51_LIBCPP_PUSH_MACROS52#include <__undef_macros>53 54_LIBCPP_BEGIN_NAMESPACE_STD55 56#if _LIBCPP_STD_VER >= 2057 58namespace ranges {59template <view _View>60class drop_view : public view_interface<drop_view<_View>> {61 // We cache begin() whenever ranges::next is not guaranteed O(1) to provide an62 // amortized O(1) begin() method. If this is an input_range, then we cannot cache63 // begin because begin is not equality preserving.64 // Note: drop_view<input-range>::begin() is still trivially amortized O(1) because65 // 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 _LIBCPP_NODEBUG = _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 72public:73 _LIBCPP_HIDE_FROM_ABI drop_view()74 requires default_initializable<_View>75 = default;76 77 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX2378 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 83 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&84 requires copy_constructible<_View>85 {86 return __base_;87 }88 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }89 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 107 _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const108 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 114 _LIBCPP_HIDE_FROM_ABI constexpr auto end()115 requires(!__simple_view<_View>)116 {117 return ranges::end(__base_);118 }119 120 _LIBCPP_HIDE_FROM_ABI constexpr auto end() const121 requires range<const _View>122 {123 return ranges::end(__base_);124 }125 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 132 _LIBCPP_HIDE_FROM_ABI constexpr auto size()133 requires sized_range<_View>134 {135 return __size(*this);136 }137 138 _LIBCPP_HIDE_FROM_ABI constexpr auto size() const139 requires sized_range<const _View>140 {141 return __size(*this);142 }143};144 145template <class _Range>146drop_view(_Range&&, range_difference_t<_Range>) -> drop_view<views::all_t<_Range>>;147 148template <class _Tp>149inline constexpr bool enable_borrowed_range<drop_view<_Tp>> = enable_borrowed_range<_Tp>;150 151namespace views {152namespace __drop {153 154template <class _Tp>155inline constexpr bool __is_empty_view = false;156 157template <class _Tp>158inline constexpr bool __is_empty_view<empty_view<_Tp>> = true;159 160template <class _Tp>161inline constexpr bool __is_passthrough_specialization = false;162 163template <class _Tp, size_t _Extent>164inline constexpr bool __is_passthrough_specialization<span<_Tp, _Extent>> = true;165 166template <class _CharT, class _Traits>167inline constexpr bool __is_passthrough_specialization<basic_string_view<_CharT, _Traits>> = true;168 169template <class _Np, class _Bound>170inline constexpr bool __is_passthrough_specialization<iota_view<_Np, _Bound>> = true;171 172template <class _Iter, class _Sent, subrange_kind _Kind>173inline constexpr bool __is_passthrough_specialization<subrange<_Iter, _Sent, _Kind>> =174 !subrange<_Iter, _Sent, _Kind>::_StoreSize;175 176template <class _Tp>177inline constexpr bool __is_subrange_specialization_with_store_size = false;178 179template <class _Iter, class _Sent, subrange_kind _Kind>180inline constexpr bool __is_subrange_specialization_with_store_size<subrange<_Iter, _Sent, _Kind>> =181 subrange<_Iter, _Sent, _Kind>::_StoreSize;182 183template <class _Tp>184struct __passthrough_type;185 186template <class _Tp, size_t _Extent>187struct __passthrough_type<span<_Tp, _Extent>> {188 using type _LIBCPP_NODEBUG = span<_Tp>;189};190 191template <class _CharT, class _Traits>192struct __passthrough_type<basic_string_view<_CharT, _Traits>> {193 using type _LIBCPP_NODEBUG = basic_string_view<_CharT, _Traits>;194};195 196template <class _Np, class _Bound>197struct __passthrough_type<iota_view<_Np, _Bound>> {198 using type _LIBCPP_NODEBUG = iota_view<_Np, _Bound>;199};200 201template <class _Iter, class _Sent, subrange_kind _Kind>202struct __passthrough_type<subrange<_Iter, _Sent, _Kind>> {203 using type _LIBCPP_NODEBUG = subrange<_Iter, _Sent, _Kind>;204};205 206template <class _Tp>207using __passthrough_type_t _LIBCPP_NODEBUG = typename __passthrough_type<_Tp>::type;208 209struct __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&&) const214 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) const227 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 the256 // 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 off262#if _LIBCPP_STD_VER >= 23263 // [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 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Np&& __n) const270 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 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI281 constexpr auto operator()(_Range&& __range, _Np&&) const282 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#endif286 // clang-format on287 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 other291 // overloads.292 requires(!(__is_empty_view<_RawRange> ||293# if _LIBCPP_STD_VER >= 23294 __is_repeat_specialization<_RawRange> ||295# endif296 (__is_subrange_specialization_with_store_size<_RawRange> && sized_range<_RawRange> &&297 random_access_range<_RawRange>) ||298 (__is_passthrough_specialization<_RawRange> && sized_range<_RawRange> &&299 random_access_range<_RawRange>)))300 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Np&& __n) const301 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) const309 noexcept(is_nothrow_constructible_v<decay_t<_Np>, _Np>) {310 return __pipeable(std::__bind_back(*this, std::forward<_Np>(__n)));311 }312};313 314} // namespace __drop315 316inline namespace __cpo {317inline constexpr auto drop = __drop::__fn{};318} // namespace __cpo319} // namespace views320 321} // namespace ranges322 323#endif // _LIBCPP_STD_VER >= 20324 325_LIBCPP_END_NAMESPACE_STD326 327_LIBCPP_POP_MACROS328 329#endif // _LIBCPP___RANGES_DROP_VIEW_H330