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_SUBRANGE_H 11 #define _LIBCPP___RANGES_SUBRANGE_H 12 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 <__fwd/get.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/pair_like.h> 33 #include <__tuple/tuple_element.h> 34 #include <__tuple/tuple_size.h> 35 #include <__type_traits/conditional.h> 36 #include <__type_traits/decay.h> 37 #include <__type_traits/is_pointer.h> 38 #include <__type_traits/is_reference.h> 39 #include <__type_traits/make_unsigned.h> 40 #include <__type_traits/remove_const.h> 41 #include <__type_traits/remove_pointer.h> 42 #include <__utility/move.h> 43 #include <cstddef> 44 45 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 46 # pragma GCC system_header 47 #endif 48 49 _LIBCPP_PUSH_MACROS 50 #include <__undef_macros> 51 52 _LIBCPP_BEGIN_NAMESPACE_STD 53 54 #if _LIBCPP_STD_VER >= 20 55 56 namespace ranges { 57 template<class _From, class _To> 58 concept __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 62 template<class _From, class _To> 63 concept __convertible_to_non_slicing = 64 convertible_to<_From, _To> && 65 !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>; 66 67 template<class _Pair, class _Iter, class _Sent> 68 concept __pair_like_convertible_from = 69 !range<_Pair> && __pair_like<_Pair> && 70 constructible_from<_Pair, _Iter, _Sent> && 71 __convertible_to_non_slicing<_Iter, tuple_element_t<0, _Pair>> && 72 convertible_to<_Sent, tuple_element_t<1, _Pair>>; 73 74 template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent = _Iter, 75 subrange_kind _Kind = sized_sentinel_for<_Sent, _Iter> 76 ? subrange_kind::sized 77 : subrange_kind::unsized> 78 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _Iter>) 79 class _LIBCPP_TEMPLATE_VIS subrange 80 : public view_interface<subrange<_Iter, _Sent, _Kind>> 81 { 82 public: 83 // Note: this is an internal implementation detail that is public only for internal usage. 84 static constexpr bool _StoreSize = (_Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>); 85 86 private: 87 static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics 88 struct _Empty { _LIBCPP_HIDE_FROM_ABI constexpr _Empty(auto) noexcept { } }; 89 using _Size = conditional_t<_StoreSize, make_unsigned_t<iter_difference_t<_Iter>>, _Empty>; 90 _LIBCPP_NO_UNIQUE_ADDRESS _Iter __begin_ = _Iter(); 91 _LIBCPP_NO_UNIQUE_ADDRESS _Sent __end_ = _Sent(); 92 _LIBCPP_NO_UNIQUE_ADDRESS _Size __size_ = 0; 93 94 public: 95 _LIBCPP_HIDE_FROM_ABI 96 subrange() requires default_initializable<_Iter> = default; 97 98 _LIBCPP_HIDE_FROM_ABI 99 constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent) 100 requires _MustProvideSizeAtConstruction 101 : __begin_(std::move(__iter)), __end_(std::move(__sent)) 102 { } 103 104 _LIBCPP_HIDE_FROM_ABI 105 constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent, 106 make_unsigned_t<iter_difference_t<_Iter>> __n) 107 requires (_Kind == subrange_kind::sized) 108 : __begin_(std::move(__iter)), __end_(std::move(__sent)), __size_(__n) 109 { 110 if constexpr (sized_sentinel_for<_Sent, _Iter>) 111 _LIBCPP_ASSERT_UNCATEGORIZED((__end_ - __begin_) == static_cast<iter_difference_t<_Iter>>(__n), 112 "std::ranges::subrange was passed an invalid size hint"); 113 } 114 115 template<__different_from<subrange> _Range> 116 requires borrowed_range<_Range> && 117 __convertible_to_non_slicing<iterator_t<_Range>, _Iter> && 118 convertible_to<sentinel_t<_Range>, _Sent> 119 _LIBCPP_HIDE_FROM_ABI 120 constexpr subrange(_Range&& __range) 121 requires (!_StoreSize) 122 : subrange(ranges::begin(__range), ranges::end(__range)) 123 { } 124 125 template<__different_from<subrange> _Range> 126 requires borrowed_range<_Range> && 127 __convertible_to_non_slicing<iterator_t<_Range>, _Iter> && 128 convertible_to<sentinel_t<_Range>, _Sent> 129 _LIBCPP_HIDE_FROM_ABI 130 constexpr subrange(_Range&& __range) 131 requires _StoreSize && sized_range<_Range> 132 : subrange(__range, ranges::size(__range)) 133 { } 134 135 template<borrowed_range _Range> 136 requires __convertible_to_non_slicing<iterator_t<_Range>, _Iter> && 137 convertible_to<sentinel_t<_Range>, _Sent> 138 _LIBCPP_HIDE_FROM_ABI 139 constexpr subrange(_Range&& __range, make_unsigned_t<iter_difference_t<_Iter>> __n) 140 requires (_Kind == subrange_kind::sized) 141 : subrange(ranges::begin(__range), ranges::end(__range), __n) 142 { } 143 144 template<__different_from<subrange> _Pair> 145 requires __pair_like_convertible_from<_Pair, const _Iter&, const _Sent&> 146 _LIBCPP_HIDE_FROM_ABI 147 constexpr operator _Pair() const { 148 return _Pair(__begin_, __end_); 149 } 150 151 _LIBCPP_HIDE_FROM_ABI 152 constexpr _Iter begin() const requires copyable<_Iter> { 153 return __begin_; 154 } 155 156 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() requires (!copyable<_Iter>) { 157 return std::move(__begin_); 158 } 159 160 _LIBCPP_HIDE_FROM_ABI 161 constexpr _Sent end() const { 162 return __end_; 163 } 164 165 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { 166 return __begin_ == __end_; 167 } 168 169 _LIBCPP_HIDE_FROM_ABI 170 constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const 171 requires (_Kind == subrange_kind::sized) 172 { 173 if constexpr (_StoreSize) 174 return __size_; 175 else 176 return std::__to_unsigned_like(__end_ - __begin_); 177 } 178 179 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const& 180 requires forward_iterator<_Iter> 181 { 182 auto __tmp = *this; 183 __tmp.advance(__n); 184 return __tmp; 185 } 186 187 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && { 188 advance(__n); 189 return std::move(*this); 190 } 191 192 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const 193 requires bidirectional_iterator<_Iter> 194 { 195 auto __tmp = *this; 196 __tmp.advance(-__n); 197 return __tmp; 198 } 199 200 _LIBCPP_HIDE_FROM_ABI 201 constexpr subrange& advance(iter_difference_t<_Iter> __n) { 202 if constexpr (bidirectional_iterator<_Iter>) { 203 if (__n < 0) { 204 ranges::advance(__begin_, __n); 205 if constexpr (_StoreSize) 206 __size_ += std::__to_unsigned_like(-__n); 207 return *this; 208 } 209 } 210 211 auto __d = __n - ranges::advance(__begin_, __n, __end_); 212 if constexpr (_StoreSize) 213 __size_ -= std::__to_unsigned_like(__d); 214 return *this; 215 } 216 }; 217 218 template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 219 subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>; 220 221 template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 222 subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) 223 -> subrange<_Iter, _Sent, subrange_kind::sized>; 224 225 template<borrowed_range _Range> 226 subrange(_Range&&) -> subrange<iterator_t<_Range>, sentinel_t<_Range>, 227 (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>) 228 ? subrange_kind::sized : subrange_kind::unsized>; 229 230 template<borrowed_range _Range> 231 subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>) 232 -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>; 233 234 template<size_t _Index, class _Iter, class _Sent, subrange_kind _Kind> 235 requires ((_Index == 0 && copyable<_Iter>) || _Index == 1) 236 _LIBCPP_HIDE_FROM_ABI 237 constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) { 238 if constexpr (_Index == 0) 239 return __subrange.begin(); 240 else 241 return __subrange.end(); 242 } 243 244 template<size_t _Index, class _Iter, class _Sent, subrange_kind _Kind> 245 requires (_Index < 2) 246 _LIBCPP_HIDE_FROM_ABI 247 constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) { 248 if constexpr (_Index == 0) 249 return __subrange.begin(); 250 else 251 return __subrange.end(); 252 } 253 254 template<class _Ip, class _Sp, subrange_kind _Kp> 255 inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true; 256 257 template<range _Rp> 258 using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>; 259 } // namespace ranges 260 261 // [range.subrange.general] 262 263 using ranges::get; 264 265 // [ranges.syn] 266 267 template<class _Ip, class _Sp, ranges::subrange_kind _Kp> 268 struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {}; 269 270 template<class _Ip, class _Sp, ranges::subrange_kind _Kp> 271 struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> { 272 using type = _Ip; 273 }; 274 275 template<class _Ip, class _Sp, ranges::subrange_kind _Kp> 276 struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> { 277 using type = _Sp; 278 }; 279 280 template<class _Ip, class _Sp, ranges::subrange_kind _Kp> 281 struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> { 282 using type = _Ip; 283 }; 284 285 template<class _Ip, class _Sp, ranges::subrange_kind _Kp> 286 struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> { 287 using type = _Sp; 288 }; 289 290 #endif // _LIBCPP_STD_VER >= 20 291 292 _LIBCPP_END_NAMESPACE_STD 293 294 _LIBCPP_POP_MACROS 295 296 #endif // _LIBCPP___RANGES_SUBRANGE_H 297