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