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> && !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>; 65 66 template <class _Pair, class _Iter, class _Sent> 67 concept __pair_like_convertible_from = 68 !range<_Pair> && __pair_like<_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 71 template <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>) 75 class _LIBCPP_TEMPLATE_VIS subrange : public view_interface<subrange<_Iter, _Sent, _Kind>> { 76 public: 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 80 private: 81 static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics 82 struct _Empty { 83 _LIBCPP_HIDE_FROM_ABI constexpr _Empty(auto) noexcept {} 84 }; 85 using _Size = 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 90 public: 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 _MustProvideSizeAtConstruction 97 : __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 <__different_from<subrange> _Pair> 130 requires __pair_like_convertible_from<_Pair, const _Iter&, const _Sent&> 131 _LIBCPP_HIDE_FROM_ABI constexpr operator _Pair() const { 132 return _Pair(__begin_, __end_); 133 } 134 135 _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() const 136 requires copyable<_Iter> 137 { 138 return __begin_; 139 } 140 141 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() 142 requires(!copyable<_Iter>) 143 { 144 return std::move(__begin_); 145 } 146 147 _LIBCPP_HIDE_FROM_ABI constexpr _Sent end() const { return __end_; } 148 149 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __begin_ == __end_; } 150 151 _LIBCPP_HIDE_FROM_ABI constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const 152 requires(_Kind == subrange_kind::sized) 153 { 154 if constexpr (_StoreSize) 155 return __size_; 156 else 157 return std::__to_unsigned_like(__end_ - __begin_); 158 } 159 160 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const& 161 requires forward_iterator<_Iter> 162 { 163 auto __tmp = *this; 164 __tmp.advance(__n); 165 return __tmp; 166 } 167 168 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && { 169 advance(__n); 170 return std::move(*this); 171 } 172 173 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const 174 requires bidirectional_iterator<_Iter> 175 { 176 auto __tmp = *this; 177 __tmp.advance(-__n); 178 return __tmp; 179 } 180 181 _LIBCPP_HIDE_FROM_ABI constexpr subrange& advance(iter_difference_t<_Iter> __n) { 182 if constexpr (bidirectional_iterator<_Iter>) { 183 if (__n < 0) { 184 ranges::advance(__begin_, __n); 185 if constexpr (_StoreSize) 186 __size_ += std::__to_unsigned_like(-__n); 187 return *this; 188 } 189 } 190 191 auto __d = __n - ranges::advance(__begin_, __n, __end_); 192 if constexpr (_StoreSize) 193 __size_ -= std::__to_unsigned_like(__d); 194 return *this; 195 } 196 }; 197 198 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 199 subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>; 200 201 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 202 subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) -> subrange<_Iter, _Sent, subrange_kind::sized>; 203 204 template <borrowed_range _Range> 205 subrange(_Range&&) 206 -> subrange<iterator_t<_Range>, 207 sentinel_t<_Range>, 208 (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>) 209 ? subrange_kind::sized 210 : subrange_kind::unsized>; 211 212 template <borrowed_range _Range> 213 subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>) 214 -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>; 215 216 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind> 217 requires((_Index == 0 && copyable<_Iter>) || _Index == 1) 218 _LIBCPP_HIDE_FROM_ABI constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) { 219 if constexpr (_Index == 0) 220 return __subrange.begin(); 221 else 222 return __subrange.end(); 223 } 224 225 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind> 226 requires(_Index < 2) 227 _LIBCPP_HIDE_FROM_ABI constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) { 228 if constexpr (_Index == 0) 229 return __subrange.begin(); 230 else 231 return __subrange.end(); 232 } 233 234 template <class _Ip, class _Sp, subrange_kind _Kp> 235 inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true; 236 237 template <range _Rp> 238 using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>; 239 } // namespace ranges 240 241 // [range.subrange.general] 242 243 using ranges::get; 244 245 // [ranges.syn] 246 247 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 248 struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {}; 249 250 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 251 struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> { 252 using type = _Ip; 253 }; 254 255 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 256 struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> { 257 using type = _Sp; 258 }; 259 260 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 261 struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> { 262 using type = _Ip; 263 }; 264 265 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 266 struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> { 267 using type = _Sp; 268 }; 269 270 #endif // _LIBCPP_STD_VER >= 20 271 272 _LIBCPP_END_NAMESPACE_STD 273 274 _LIBCPP_POP_MACROS 275 276 #endif // _LIBCPP___RANGES_SUBRANGE_H 277