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 <__cstddef/size_t.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/tuple_element.h> 33 #include <__tuple/tuple_like_no_subrange.h> 34 #include <__tuple/tuple_size.h> 35 #include <__type_traits/conditional.h> 36 #include <__type_traits/decay.h> 37 #include <__type_traits/integral_constant.h> 38 #include <__type_traits/is_pointer.h> 39 #include <__type_traits/is_reference.h> 40 #include <__type_traits/make_unsigned.h> 41 #include <__type_traits/remove_const.h> 42 #include <__type_traits/remove_pointer.h> 43 #include <__utility/move.h> 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_no_subrange<_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 _LIBCPP_NODEBUG = 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 <__pair_like_convertible_from<const _Iter&, const _Sent&> _Pair> 130 _LIBCPP_HIDE_FROM_ABI constexpr operator _Pair() const { 131 return _Pair(__begin_, __end_); 132 } 133 134 _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() const 135 requires copyable<_Iter> 136 { 137 return __begin_; 138 } 139 140 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() 141 requires(!copyable<_Iter>) 142 { 143 return std::move(__begin_); 144 } 145 146 _LIBCPP_HIDE_FROM_ABI constexpr _Sent end() const { return __end_; } 147 148 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __begin_ == __end_; } 149 150 _LIBCPP_HIDE_FROM_ABI constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const 151 requires(_Kind == subrange_kind::sized) 152 { 153 if constexpr (_StoreSize) 154 return __size_; 155 else 156 return std::__to_unsigned_like(__end_ - __begin_); 157 } 158 159 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const& 160 requires forward_iterator<_Iter> 161 { 162 auto __tmp = *this; 163 __tmp.advance(__n); 164 return __tmp; 165 } 166 167 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && { 168 advance(__n); 169 return std::move(*this); 170 } 171 172 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const 173 requires bidirectional_iterator<_Iter> 174 { 175 auto __tmp = *this; 176 __tmp.advance(-__n); 177 return __tmp; 178 } 179 180 _LIBCPP_HIDE_FROM_ABI constexpr subrange& advance(iter_difference_t<_Iter> __n) { 181 if constexpr (bidirectional_iterator<_Iter>) { 182 if (__n < 0) { 183 ranges::advance(__begin_, __n); 184 if constexpr (_StoreSize) 185 __size_ += std::__to_unsigned_like(-__n); 186 return *this; 187 } 188 } 189 190 auto __d = __n - ranges::advance(__begin_, __n, __end_); 191 if constexpr (_StoreSize) 192 __size_ -= std::__to_unsigned_like(__d); 193 return *this; 194 } 195 }; 196 197 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 198 subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>; 199 200 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 201 subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) -> subrange<_Iter, _Sent, subrange_kind::sized>; 202 203 template <borrowed_range _Range> 204 subrange(_Range&&) -> subrange<iterator_t<_Range>, 205 sentinel_t<_Range>, 206 (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>) 207 ? subrange_kind::sized 208 : subrange_kind::unsized>; 209 210 template <borrowed_range _Range> 211 subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>) 212 -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>; 213 214 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind> 215 requires((_Index == 0 && copyable<_Iter>) || _Index == 1) 216 _LIBCPP_HIDE_FROM_ABI constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) { 217 if constexpr (_Index == 0) 218 return __subrange.begin(); 219 else 220 return __subrange.end(); 221 } 222 223 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind> 224 requires(_Index < 2) 225 _LIBCPP_HIDE_FROM_ABI constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) { 226 if constexpr (_Index == 0) 227 return __subrange.begin(); 228 else 229 return __subrange.end(); 230 } 231 232 template <class _Ip, class _Sp, subrange_kind _Kp> 233 inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true; 234 235 template <range _Rp> 236 using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>; 237 } // namespace ranges 238 239 // [range.subrange.general] 240 241 using ranges::get; 242 243 // [ranges.syn] 244 245 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 246 struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {}; 247 248 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 249 struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> { 250 using type = _Ip; 251 }; 252 253 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 254 struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> { 255 using type = _Sp; 256 }; 257 258 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 259 struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> { 260 using type = _Ip; 261 }; 262 263 template <class _Ip, class _Sp, ranges::subrange_kind _Kp> 264 struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> { 265 using type = _Sp; 266 }; 267 268 #endif // _LIBCPP_STD_VER >= 20 269 270 _LIBCPP_END_NAMESPACE_STD 271 272 _LIBCPP_POP_MACROS 273 274 #endif // _LIBCPP___RANGES_SUBRANGE_H 275