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_JOIN_VIEW_H 11 #define _LIBCPP___RANGES_JOIN_VIEW_H 12 13 #include <__concepts/constructible.h> 14 #include <__concepts/convertible_to.h> 15 #include <__concepts/copyable.h> 16 #include <__concepts/derived_from.h> 17 #include <__concepts/equality_comparable.h> 18 #include <__config> 19 #include <__iterator/concepts.h> 20 #include <__iterator/iter_move.h> 21 #include <__iterator/iter_swap.h> 22 #include <__iterator/iterator_traits.h> 23 #include <__iterator/iterator_with_data.h> 24 #include <__iterator/segmented_iterator.h> 25 #include <__memory/addressof.h> 26 #include <__ranges/access.h> 27 #include <__ranges/all.h> 28 #include <__ranges/concepts.h> 29 #include <__ranges/empty.h> 30 #include <__ranges/non_propagating_cache.h> 31 #include <__ranges/range_adaptor.h> 32 #include <__ranges/view_interface.h> 33 #include <__type_traits/common_type.h> 34 #include <__type_traits/maybe_const.h> 35 #include <__utility/forward.h> 36 #include <optional> 37 38 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 39 # pragma GCC system_header 40 #endif 41 42 _LIBCPP_BEGIN_NAMESPACE_STD 43 44 // Note: `join_view` is still marked experimental because there is an ABI-breaking change that affects `join_view` in 45 // the pipeline (https://isocpp.org/files/papers/D2770R0.html). 46 // TODO: make `join_view` non-experimental once D2770 is implemented. 47 #if _LIBCPP_STD_VER >= 20 && defined(_LIBCPP_ENABLE_EXPERIMENTAL) 48 49 namespace ranges { 50 template<class> 51 struct __join_view_iterator_category {}; 52 53 template<class _View> 54 requires is_reference_v<range_reference_t<_View>> && 55 forward_range<_View> && 56 forward_range<range_reference_t<_View>> 57 struct __join_view_iterator_category<_View> { 58 using _OuterC = typename iterator_traits<iterator_t<_View>>::iterator_category; 59 using _InnerC = typename iterator_traits<iterator_t<range_reference_t<_View>>>::iterator_category; 60 61 using iterator_category = _If< 62 derived_from<_OuterC, bidirectional_iterator_tag> && derived_from<_InnerC, bidirectional_iterator_tag> && 63 common_range<range_reference_t<_View>>, 64 bidirectional_iterator_tag, 65 _If< 66 derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>, 67 forward_iterator_tag, 68 input_iterator_tag 69 > 70 >; 71 }; 72 73 template<input_range _View> 74 requires view<_View> && input_range<range_reference_t<_View>> 75 class join_view 76 : public view_interface<join_view<_View>> { 77 private: 78 using _InnerRange = range_reference_t<_View>; 79 80 template<bool> struct __iterator; 81 82 template<bool> struct __sentinel; 83 84 template <class> 85 friend struct std::__segmented_iterator_traits; 86 87 static constexpr bool _UseCache = !is_reference_v<_InnerRange>; 88 using _Cache = _If<_UseCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>; 89 _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cache_; 90 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 91 92 public: 93 _LIBCPP_HIDE_FROM_ABI 94 join_view() requires default_initializable<_View> = default; 95 96 _LIBCPP_HIDE_FROM_ABI 97 constexpr explicit join_view(_View __base) 98 : __base_(std::move(__base)) {} 99 100 _LIBCPP_HIDE_FROM_ABI 101 constexpr _View base() const& requires copy_constructible<_View> { return __base_; } 102 103 _LIBCPP_HIDE_FROM_ABI 104 constexpr _View base() && { return std::move(__base_); } 105 106 _LIBCPP_HIDE_FROM_ABI 107 constexpr auto begin() { 108 constexpr bool __use_const = __simple_view<_View> && 109 is_reference_v<range_reference_t<_View>>; 110 return __iterator<__use_const>{*this, ranges::begin(__base_)}; 111 } 112 113 template<class _V2 = _View> 114 _LIBCPP_HIDE_FROM_ABI 115 constexpr auto begin() const 116 requires input_range<const _V2> && 117 is_reference_v<range_reference_t<const _V2>> 118 { 119 return __iterator<true>{*this, ranges::begin(__base_)}; 120 } 121 122 _LIBCPP_HIDE_FROM_ABI 123 constexpr auto end() { 124 if constexpr (forward_range<_View> && 125 is_reference_v<_InnerRange> && 126 forward_range<_InnerRange> && 127 common_range<_View> && 128 common_range<_InnerRange>) 129 return __iterator<__simple_view<_View>>{*this, ranges::end(__base_)}; 130 else 131 return __sentinel<__simple_view<_View>>{*this}; 132 } 133 134 template<class _V2 = _View> 135 _LIBCPP_HIDE_FROM_ABI 136 constexpr auto end() const 137 requires input_range<const _V2> && 138 is_reference_v<range_reference_t<const _V2>> 139 { 140 using _ConstInnerRange = range_reference_t<const _View>; 141 if constexpr (forward_range<const _View> && 142 is_reference_v<_ConstInnerRange> && 143 forward_range<_ConstInnerRange> && 144 common_range<const _View> && 145 common_range<_ConstInnerRange>) { 146 return __iterator<true>{*this, ranges::end(__base_)}; 147 } else { 148 return __sentinel<true>{*this}; 149 } 150 } 151 }; 152 153 template<input_range _View> 154 requires view<_View> && input_range<range_reference_t<_View>> 155 template<bool _Const> 156 struct join_view<_View>::__sentinel { 157 template<bool> 158 friend struct __sentinel; 159 160 private: 161 using _Parent = __maybe_const<_Const, join_view<_View>>; 162 using _Base = __maybe_const<_Const, _View>; 163 sentinel_t<_Base> __end_ = sentinel_t<_Base>(); 164 165 public: 166 _LIBCPP_HIDE_FROM_ABI 167 __sentinel() = default; 168 169 _LIBCPP_HIDE_FROM_ABI 170 constexpr explicit __sentinel(_Parent& __parent) 171 : __end_(ranges::end(__parent.__base_)) {} 172 173 _LIBCPP_HIDE_FROM_ABI 174 constexpr __sentinel(__sentinel<!_Const> __s) 175 requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>> 176 : __end_(std::move(__s.__end_)) {} 177 178 template<bool _OtherConst> 179 requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>> 180 _LIBCPP_HIDE_FROM_ABI 181 friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) { 182 return __x.__outer_ == __y.__end_; 183 } 184 }; 185 186 // https://reviews.llvm.org/D142811#inline-1383022 187 // To simplify the segmented iterator traits specialization, 188 // make the iterator `final` 189 template<input_range _View> 190 requires view<_View> && input_range<range_reference_t<_View>> 191 template<bool _Const> 192 struct join_view<_View>::__iterator final 193 : public __join_view_iterator_category<__maybe_const<_Const, _View>> { 194 195 template<bool> 196 friend struct __iterator; 197 198 template <class> 199 friend struct std::__segmented_iterator_traits; 200 201 static constexpr bool __is_join_view_iterator = true; 202 203 private: 204 using _Parent = __maybe_const<_Const, join_view<_View>>; 205 using _Base = __maybe_const<_Const, _View>; 206 using _Outer = iterator_t<_Base>; 207 using _Inner = iterator_t<range_reference_t<_Base>>; 208 using _InnerRange = range_reference_t<_View>; 209 210 static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>; 211 212 public: 213 _Outer __outer_ = _Outer(); 214 215 private: 216 optional<_Inner> __inner_; 217 _Parent *__parent_ = nullptr; 218 219 _LIBCPP_HIDE_FROM_ABI 220 constexpr void __satisfy() { 221 for (; __outer_ != ranges::end(__parent_->__base_); ++__outer_) { 222 auto&& __inner = [&]() -> auto&& { 223 if constexpr (__ref_is_glvalue) 224 return *__outer_; 225 else 226 return __parent_->__cache_.__emplace_from([&]() -> decltype(auto) { return *__outer_; }); 227 }(); 228 __inner_ = ranges::begin(__inner); 229 if (*__inner_ != ranges::end(__inner)) 230 return; 231 } 232 233 if constexpr (__ref_is_glvalue) 234 __inner_.reset(); 235 } 236 237 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent* __parent, _Outer __outer, _Inner __inner) 238 : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {} 239 240 public: 241 using iterator_concept = _If< 242 __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> && 243 common_range<range_reference_t<_Base>>, 244 bidirectional_iterator_tag, 245 _If< 246 __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>, 247 forward_iterator_tag, 248 input_iterator_tag 249 > 250 >; 251 252 using value_type = range_value_t<range_reference_t<_Base>>; 253 254 using difference_type = common_type_t< 255 range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>; 256 257 _LIBCPP_HIDE_FROM_ABI 258 __iterator() requires default_initializable<_Outer> = default; 259 260 _LIBCPP_HIDE_FROM_ABI 261 constexpr __iterator(_Parent& __parent, _Outer __outer) 262 : __outer_(std::move(__outer)) 263 , __parent_(std::addressof(__parent)) { 264 __satisfy(); 265 } 266 267 _LIBCPP_HIDE_FROM_ABI 268 constexpr __iterator(__iterator<!_Const> __i) 269 requires _Const && 270 convertible_to<iterator_t<_View>, _Outer> && 271 convertible_to<iterator_t<_InnerRange>, _Inner> 272 : __outer_(std::move(__i.__outer_)) 273 , __inner_(std::move(__i.__inner_)) 274 , __parent_(__i.__parent_) {} 275 276 _LIBCPP_HIDE_FROM_ABI 277 constexpr decltype(auto) operator*() const { 278 return **__inner_; 279 } 280 281 _LIBCPP_HIDE_FROM_ABI 282 constexpr _Inner operator->() const 283 requires __has_arrow<_Inner> && copyable<_Inner> 284 { 285 return *__inner_; 286 } 287 288 _LIBCPP_HIDE_FROM_ABI 289 constexpr __iterator& operator++() { 290 auto&& __inner = [&]() -> auto&& { 291 if constexpr (__ref_is_glvalue) 292 return *__outer_; 293 else 294 return *__parent_->__cache_; 295 }(); 296 if (++*__inner_ == ranges::end(__inner)) { 297 ++__outer_; 298 __satisfy(); 299 } 300 return *this; 301 } 302 303 _LIBCPP_HIDE_FROM_ABI 304 constexpr void operator++(int) { 305 ++*this; 306 } 307 308 _LIBCPP_HIDE_FROM_ABI 309 constexpr __iterator operator++(int) 310 requires __ref_is_glvalue && 311 forward_range<_Base> && 312 forward_range<range_reference_t<_Base>> 313 { 314 auto __tmp = *this; 315 ++*this; 316 return __tmp; 317 } 318 319 _LIBCPP_HIDE_FROM_ABI 320 constexpr __iterator& operator--() 321 requires __ref_is_glvalue && 322 bidirectional_range<_Base> && 323 bidirectional_range<range_reference_t<_Base>> && 324 common_range<range_reference_t<_Base>> 325 { 326 if (__outer_ == ranges::end(__parent_->__base_)) 327 __inner_ = ranges::end(*--__outer_); 328 329 // Skip empty inner ranges when going backwards. 330 while (*__inner_ == ranges::begin(*__outer_)) { 331 __inner_ = ranges::end(*--__outer_); 332 } 333 334 --*__inner_; 335 return *this; 336 } 337 338 _LIBCPP_HIDE_FROM_ABI 339 constexpr __iterator operator--(int) 340 requires __ref_is_glvalue && 341 bidirectional_range<_Base> && 342 bidirectional_range<range_reference_t<_Base>> && 343 common_range<range_reference_t<_Base>> 344 { 345 auto __tmp = *this; 346 --*this; 347 return __tmp; 348 } 349 350 _LIBCPP_HIDE_FROM_ABI 351 friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) 352 requires __ref_is_glvalue && 353 equality_comparable<iterator_t<_Base>> && 354 equality_comparable<iterator_t<range_reference_t<_Base>>> 355 { 356 return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_; 357 } 358 359 _LIBCPP_HIDE_FROM_ABI 360 friend constexpr decltype(auto) iter_move(const __iterator& __i) 361 noexcept(noexcept(ranges::iter_move(*__i.__inner_))) 362 { 363 return ranges::iter_move(*__i.__inner_); 364 } 365 366 _LIBCPP_HIDE_FROM_ABI 367 friend constexpr void iter_swap(const __iterator& __x, const __iterator& __y) 368 noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_))) 369 requires indirectly_swappable<_Inner> 370 { 371 return ranges::iter_swap(*__x.__inner_, *__y.__inner_); 372 } 373 }; 374 375 template<class _Range> 376 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>; 377 378 namespace views { 379 namespace __join_view { 380 struct __fn : __range_adaptor_closure<__fn> { 381 template<class _Range> 382 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 383 constexpr auto operator()(_Range&& __range) const 384 noexcept(noexcept(join_view<all_t<_Range&&>>(std::forward<_Range>(__range)))) 385 -> decltype( join_view<all_t<_Range&&>>(std::forward<_Range>(__range))) 386 { return join_view<all_t<_Range&&>>(std::forward<_Range>(__range)); } 387 }; 388 } // namespace __join_view 389 inline namespace __cpo { 390 inline constexpr auto join = __join_view::__fn{}; 391 } // namespace __cpo 392 } // namespace views 393 } // namespace ranges 394 395 template <class _JoinViewIterator> 396 requires(_JoinViewIterator::__is_join_view_iterator && 397 ranges::common_range<typename _JoinViewIterator::_Parent> && 398 __has_random_access_iterator_category<typename _JoinViewIterator::_Outer>::value && 399 __has_random_access_iterator_category<typename _JoinViewIterator::_Inner>::value) 400 struct __segmented_iterator_traits<_JoinViewIterator> { 401 402 using __segment_iterator = 403 _LIBCPP_NODEBUG __iterator_with_data<typename _JoinViewIterator::_Outer, typename _JoinViewIterator::_Parent*>; 404 using __local_iterator = typename _JoinViewIterator::_Inner; 405 406 // TODO: Would it make sense to enable the optimization for other iterator types? 407 408 static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) { 409 if (ranges::empty(__iter.__parent_->__base_)) 410 return {}; 411 if (!__iter.__inner_.has_value()) 412 return __segment_iterator(--__iter.__outer_, __iter.__parent_); 413 return __segment_iterator(__iter.__outer_, __iter.__parent_); 414 } 415 416 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) { 417 if (ranges::empty(__iter.__parent_->__base_)) 418 return {}; 419 if (!__iter.__inner_.has_value()) 420 return ranges::end(*--__iter.__outer_); 421 return *__iter.__inner_; 422 } 423 424 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) { 425 return ranges::begin(*__iter.__get_iter()); 426 } 427 428 static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) { 429 return ranges::end(*__iter.__get_iter()); 430 } 431 432 static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator 433 __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) { 434 return _JoinViewIterator( 435 std::move(__seg_iter).__get_data(), std::move(__seg_iter).__get_iter(), std::move(__local_iter)); 436 } 437 }; 438 439 #endif // #if _LIBCPP_STD_VER >= 20 && defined(_LIBCPP_ENABLE_EXPERIMENTAL) 440 441 _LIBCPP_END_NAMESPACE_STD 442 443 #endif // _LIBCPP___RANGES_JOIN_VIEW_H 444