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