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