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