275 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_SUBRANGE_H11#define _LIBCPP___RANGES_SUBRANGE_H12 13#include <__assert>14#include <__concepts/constructible.h>15#include <__concepts/convertible_to.h>16#include <__concepts/copyable.h>17#include <__concepts/derived_from.h>18#include <__concepts/different_from.h>19#include <__config>20#include <__cstddef/size_t.h>21#include <__fwd/subrange.h>22#include <__iterator/advance.h>23#include <__iterator/concepts.h>24#include <__iterator/incrementable_traits.h>25#include <__iterator/iterator_traits.h>26#include <__ranges/access.h>27#include <__ranges/concepts.h>28#include <__ranges/dangling.h>29#include <__ranges/enable_borrowed_range.h>30#include <__ranges/size.h>31#include <__ranges/view_interface.h>32#include <__tuple/tuple_element.h>33#include <__tuple/tuple_like_no_subrange.h>34#include <__tuple/tuple_size.h>35#include <__type_traits/conditional.h>36#include <__type_traits/decay.h>37#include <__type_traits/integral_constant.h>38#include <__type_traits/is_pointer.h>39#include <__type_traits/is_reference.h>40#include <__type_traits/make_unsigned.h>41#include <__type_traits/remove_const.h>42#include <__type_traits/remove_pointer.h>43#include <__utility/move.h>44 45#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)46# pragma GCC system_header47#endif48 49_LIBCPP_PUSH_MACROS50#include <__undef_macros>51 52_LIBCPP_BEGIN_NAMESPACE_STD53 54#if _LIBCPP_STD_VER >= 2055 56namespace ranges {57template <class _From, class _To>58concept __uses_nonqualification_pointer_conversion =59 is_pointer_v<_From> && is_pointer_v<_To> &&60 !convertible_to<remove_pointer_t<_From> (*)[], remove_pointer_t<_To> (*)[]>;61 62template <class _From, class _To>63concept __convertible_to_non_slicing =64 convertible_to<_From, _To> && !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>;65 66template <class _Pair, class _Iter, class _Sent>67concept __pair_like_convertible_from =68 !range<_Pair> && __pair_like_no_subrange<_Pair> && constructible_from<_Pair, _Iter, _Sent> &&69 __convertible_to_non_slicing<_Iter, tuple_element_t<0, _Pair>> && convertible_to<_Sent, tuple_element_t<1, _Pair>>;70 71template <input_or_output_iterator _Iter,72 sentinel_for<_Iter> _Sent = _Iter,73 subrange_kind _Kind = sized_sentinel_for<_Sent, _Iter> ? subrange_kind::sized : subrange_kind::unsized>74 requires(_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _Iter>)75class subrange : public view_interface<subrange<_Iter, _Sent, _Kind>> {76public:77 // Note: this is an internal implementation detail that is public only for internal usage.78 static constexpr bool _StoreSize = (_Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>);79 80private:81 static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics82 struct _Empty {83 _LIBCPP_HIDE_FROM_ABI constexpr _Empty(auto) noexcept {}84 };85 using _Size _LIBCPP_NODEBUG = conditional_t<_StoreSize, make_unsigned_t<iter_difference_t<_Iter>>, _Empty>;86 _LIBCPP_NO_UNIQUE_ADDRESS _Iter __begin_ = _Iter();87 _LIBCPP_NO_UNIQUE_ADDRESS _Sent __end_ = _Sent();88 _LIBCPP_NO_UNIQUE_ADDRESS _Size __size_ = 0;89 90public:91 _LIBCPP_HIDE_FROM_ABI subrange()92 requires default_initializable<_Iter>93 = default;94 95 _LIBCPP_HIDE_FROM_ABI constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent)96 requires _MustProvideSizeAtConstruction97 : __begin_(std::move(__iter)), __end_(std::move(__sent)) {}98 99 _LIBCPP_HIDE_FROM_ABI constexpr subrange(100 __convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent, make_unsigned_t<iter_difference_t<_Iter>> __n)101 requires(_Kind == subrange_kind::sized)102 : __begin_(std::move(__iter)), __end_(std::move(__sent)), __size_(__n) {103 if constexpr (sized_sentinel_for<_Sent, _Iter>)104 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS((__end_ - __begin_) == static_cast<iter_difference_t<_Iter>>(__n),105 "std::ranges::subrange was passed an invalid size hint");106 }107 108 template <__different_from<subrange> _Range>109 requires borrowed_range<_Range> && __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&110 convertible_to<sentinel_t<_Range>, _Sent>111 _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range)112 requires(!_StoreSize)113 : subrange(ranges::begin(__range), ranges::end(__range)) {}114 115 template <__different_from<subrange> _Range>116 requires borrowed_range<_Range> && __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&117 convertible_to<sentinel_t<_Range>, _Sent>118 _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range)119 requires _StoreSize && sized_range<_Range>120 : subrange(__range, ranges::size(__range)) {}121 122 template <borrowed_range _Range>123 requires __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&124 convertible_to<sentinel_t<_Range>, _Sent>125 _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range, make_unsigned_t<iter_difference_t<_Iter>> __n)126 requires(_Kind == subrange_kind::sized)127 : subrange(ranges::begin(__range), ranges::end(__range), __n) {}128 129 template <__pair_like_convertible_from<const _Iter&, const _Sent&> _Pair>130 _LIBCPP_HIDE_FROM_ABI constexpr operator _Pair() const {131 return _Pair(__begin_, __end_);132 }133 134 _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() const135 requires copyable<_Iter>136 {137 return __begin_;138 }139 140 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin()141 requires(!copyable<_Iter>)142 {143 return std::move(__begin_);144 }145 146 _LIBCPP_HIDE_FROM_ABI constexpr _Sent end() const { return __end_; }147 148 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __begin_ == __end_; }149 150 _LIBCPP_HIDE_FROM_ABI constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const151 requires(_Kind == subrange_kind::sized)152 {153 if constexpr (_StoreSize)154 return __size_;155 else156 return std::__to_unsigned_like(__end_ - __begin_);157 }158 159 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const&160 requires forward_iterator<_Iter>161 {162 auto __tmp = *this;163 __tmp.advance(__n);164 return __tmp;165 }166 167 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && {168 advance(__n);169 return std::move(*this);170 }171 172 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const173 requires bidirectional_iterator<_Iter>174 {175 auto __tmp = *this;176 __tmp.advance(-__n);177 return __tmp;178 }179 180 _LIBCPP_HIDE_FROM_ABI constexpr subrange& advance(iter_difference_t<_Iter> __n) {181 if constexpr (bidirectional_iterator<_Iter>) {182 if (__n < 0) {183 ranges::advance(__begin_, __n);184 if constexpr (_StoreSize)185 __size_ += std::__to_unsigned_like(-__n);186 return *this;187 }188 }189 190 auto __d = __n - ranges::advance(__begin_, __n, __end_);191 if constexpr (_StoreSize)192 __size_ -= std::__to_unsigned_like(__d);193 return *this;194 }195};196 197template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>198subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>;199 200template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>201subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) -> subrange<_Iter, _Sent, subrange_kind::sized>;202 203template <borrowed_range _Range>204subrange(_Range&&) -> subrange<iterator_t<_Range>,205 sentinel_t<_Range>,206 (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>)207 ? subrange_kind::sized208 : subrange_kind::unsized>;209 210template <borrowed_range _Range>211subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>)212 -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>;213 214template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>215 requires((_Index == 0 && copyable<_Iter>) || _Index == 1)216_LIBCPP_HIDE_FROM_ABI constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) {217 if constexpr (_Index == 0)218 return __subrange.begin();219 else220 return __subrange.end();221}222 223template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>224 requires(_Index < 2)225_LIBCPP_HIDE_FROM_ABI constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) {226 if constexpr (_Index == 0)227 return __subrange.begin();228 else229 return __subrange.end();230}231 232template <class _Ip, class _Sp, subrange_kind _Kp>233inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true;234 235template <range _Rp>236using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>;237} // namespace ranges238 239// [range.subrange.general]240 241using ranges::get;242 243// [ranges.syn]244 245template <class _Ip, class _Sp, ranges::subrange_kind _Kp>246struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {};247 248template <class _Ip, class _Sp, ranges::subrange_kind _Kp>249struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> {250 using type _LIBCPP_NODEBUG = _Ip;251};252 253template <class _Ip, class _Sp, ranges::subrange_kind _Kp>254struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> {255 using type _LIBCPP_NODEBUG = _Sp;256};257 258template <class _Ip, class _Sp, ranges::subrange_kind _Kp>259struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> {260 using type _LIBCPP_NODEBUG = _Ip;261};262 263template <class _Ip, class _Sp, ranges::subrange_kind _Kp>264struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> {265 using type _LIBCPP_NODEBUG = _Sp;266};267 268#endif // _LIBCPP_STD_VER >= 20269 270_LIBCPP_END_NAMESPACE_STD271 272_LIBCPP_POP_MACROS273 274#endif // _LIBCPP___RANGES_SUBRANGE_H275