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