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