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