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