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_WITH_VIEW_H 11 #define _LIBCPP___RANGES_JOIN_WITH_VIEW_H 12 13 #include <__concepts/common_reference_with.h> 14 #include <__concepts/common_with.h> 15 #include <__concepts/constructible.h> 16 #include <__concepts/convertible_to.h> 17 #include <__concepts/derived_from.h> 18 #include <__concepts/equality_comparable.h> 19 #include <__config> 20 #include <__functional/bind_back.h> 21 #include <__iterator/concepts.h> 22 #include <__iterator/incrementable_traits.h> 23 #include <__iterator/iter_move.h> 24 #include <__iterator/iter_swap.h> 25 #include <__iterator/iterator_traits.h> 26 #include <__memory/addressof.h> 27 #include <__ranges/access.h> 28 #include <__ranges/all.h> 29 #include <__ranges/concepts.h> 30 #include <__ranges/non_propagating_cache.h> 31 #include <__ranges/range_adaptor.h> 32 #include <__ranges/single_view.h> 33 #include <__ranges/view_interface.h> 34 #include <__type_traits/conditional.h> 35 #include <__type_traits/decay.h> 36 #include <__type_traits/is_reference.h> 37 #include <__type_traits/maybe_const.h> 38 #include <__utility/as_const.h> 39 #include <__utility/as_lvalue.h> 40 #include <__utility/empty.h> 41 #include <__utility/forward.h> 42 #include <__utility/move.h> 43 #include <variant> 44 45 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 46 # pragma GCC system_header 47 #endif 48 49 _LIBCPP_PUSH_MACROS 50 #include <__undef_macros> 51 52 _LIBCPP_BEGIN_NAMESPACE_STD 53 54 #if _LIBCPP_STD_VER >= 23 55 56 namespace ranges { 57 template <class _Range> 58 concept __bidirectional_common = bidirectional_range<_Range> && common_range<_Range>; 59 60 template <input_range _View, forward_range _Pattern> 61 requires view<_View> && input_range<range_reference_t<_View>> && view<_Pattern> && 62 __concatable<range_reference_t<_View>, _Pattern> 63 class join_with_view : public view_interface<join_with_view<_View, _Pattern>> { 64 using _InnerRng _LIBCPP_NODEBUG = range_reference_t<_View>; 65 66 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 67 68 static constexpr bool _UseOuterItCache = !forward_range<_View>; 69 using _OuterItCache _LIBCPP_NODEBUG = 70 _If<_UseOuterItCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>; 71 _LIBCPP_NO_UNIQUE_ADDRESS _OuterItCache __outer_it_; 72 73 static constexpr bool _UseInnerCache = !is_reference_v<_InnerRng>; 74 using _InnerCache _LIBCPP_NODEBUG = 75 _If<_UseInnerCache, __non_propagating_cache<remove_cvref_t<_InnerRng>>, __empty_cache>; 76 _LIBCPP_NO_UNIQUE_ADDRESS _InnerCache __inner_; 77 78 _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern(); 79 80 template <bool _Const> 81 struct __iterator; 82 83 template <bool _Const> 84 struct __sentinel; 85 86 public: 87 _LIBCPP_HIDE_FROM_ABI join_with_view() 88 requires default_initializable<_View> && default_initializable<_Pattern> 89 = default; 90 join_with_view(_View __base,_Pattern __pattern)91 _LIBCPP_HIDE_FROM_ABI constexpr explicit join_with_view(_View __base, _Pattern __pattern) 92 : __base_(std::move(__base)), __pattern_(std::move(__pattern)) {} 93 94 template <input_range _Range> 95 requires constructible_from<_View, views::all_t<_Range>> && 96 constructible_from<_Pattern, single_view<range_value_t<_InnerRng>>> join_with_view(_Range && __r,range_value_t<_InnerRng> __e)97 _LIBCPP_HIDE_FROM_ABI constexpr explicit join_with_view(_Range&& __r, range_value_t<_InnerRng> __e) 98 : __base_(views::all(std::forward<_Range>(__r))), __pattern_(views::single(std::move(__e))) {} 99 base()100 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& 101 requires copy_constructible<_View> 102 { 103 return __base_; 104 } 105 base()106 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 107 begin()108 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin() { 109 if constexpr (forward_range<_View>) { 110 constexpr bool __use_const = __simple_view<_View> && is_reference_v<_InnerRng> && __simple_view<_Pattern>; 111 return __iterator<__use_const>{*this, ranges::begin(__base_)}; 112 } else { 113 __outer_it_.__emplace(ranges::begin(__base_)); 114 return __iterator<false>{*this}; 115 } 116 } 117 begin()118 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const 119 requires forward_range<const _View> && forward_range<const _Pattern> && 120 is_reference_v<range_reference_t<const _View>> && input_range<range_reference_t<const _View>> && 121 __concatable<range_reference_t<const _View>, const _Pattern> 122 { 123 return __iterator<true>{*this, ranges::begin(__base_)}; 124 } 125 end()126 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() { 127 constexpr bool __use_const = __simple_view<_View> && __simple_view<_Pattern>; 128 if constexpr (forward_range<_View> && is_reference_v<_InnerRng> && forward_range<_InnerRng> && 129 common_range<_View> && common_range<_InnerRng>) 130 return __iterator<__use_const>{*this, ranges::end(__base_)}; 131 else 132 return __sentinel<__use_const>{*this}; 133 } 134 end()135 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() const 136 requires forward_range<const _View> && forward_range<const _Pattern> && 137 is_reference_v<range_reference_t<const _View>> && input_range<range_reference_t<const _View>> && 138 __concatable<range_reference_t<const _View>, const _Pattern> 139 { 140 using _InnerConstRng = range_reference_t<const _View>; 141 if constexpr (forward_range<_InnerConstRng> && common_range<const _View> && common_range<_InnerConstRng>) 142 return __iterator<true>{*this, ranges::end(__base_)}; 143 else 144 return __sentinel<true>{*this}; 145 } 146 }; 147 148 template <class _Range, class _Pattern> 149 join_with_view(_Range&&, _Pattern&&) -> join_with_view<views::all_t<_Range>, views::all_t<_Pattern>>; 150 151 template <input_range _Range> 152 join_with_view(_Range&&, range_value_t<range_reference_t<_Range>>) 153 -> join_with_view<views::all_t<_Range>, single_view<range_value_t<range_reference_t<_Range>>>>; 154 155 template <class _Base, class _PatternBase, class _InnerBase = range_reference_t<_Base>> 156 struct __join_with_view_iterator_category {}; 157 158 template <class _Base, class _PatternBase, class _InnerBase> 159 requires is_reference_v<_InnerBase> && forward_range<_Base> && forward_range<_InnerBase> 160 struct __join_with_view_iterator_category<_Base, _PatternBase, _InnerBase> { 161 private: 162 static consteval auto __get_iterator_category() noexcept { 163 using _OuterC = iterator_traits<iterator_t<_Base>>::iterator_category; 164 using _InnerC = iterator_traits<iterator_t<_InnerBase>>::iterator_category; 165 using _PatternC = iterator_traits<iterator_t<_PatternBase>>::iterator_category; 166 167 if constexpr (!is_reference_v<common_reference_t<iter_reference_t<iterator_t<_InnerBase>>, 168 iter_reference_t<iterator_t<_PatternBase>>>>) 169 return input_iterator_tag{}; 170 else if constexpr (derived_from<_OuterC, bidirectional_iterator_tag> && 171 derived_from<_InnerC, bidirectional_iterator_tag> && 172 derived_from<_PatternC, bidirectional_iterator_tag> && common_range<_InnerBase> && 173 common_range<_PatternBase>) 174 return bidirectional_iterator_tag{}; 175 else if constexpr (derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag> && 176 derived_from<_PatternC, forward_iterator_tag>) 177 return forward_iterator_tag{}; 178 else 179 return input_iterator_tag{}; 180 } 181 182 public: 183 using iterator_category = decltype(__get_iterator_category()); 184 }; 185 186 template <input_range _View, forward_range _Pattern> 187 requires view<_View> && input_range<range_reference_t<_View>> && view<_Pattern> && 188 __concatable<range_reference_t<_View>, _Pattern> 189 template <bool _Const> 190 struct join_with_view<_View, _Pattern>::__iterator 191 : public __join_with_view_iterator_category<__maybe_const<_Const, _View>, __maybe_const<_Const, _Pattern>> { 192 private: 193 friend join_with_view; 194 195 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, join_with_view>; 196 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>; 197 using _InnerBase _LIBCPP_NODEBUG = range_reference_t<_Base>; 198 using _PatternBase _LIBCPP_NODEBUG = __maybe_const<_Const, _Pattern>; 199 200 using _OuterIter _LIBCPP_NODEBUG = iterator_t<_Base>; 201 using _InnerIter _LIBCPP_NODEBUG = iterator_t<_InnerBase>; 202 using _PatternIter _LIBCPP_NODEBUG = iterator_t<_PatternBase>; 203 204 static_assert(!_Const || forward_range<_Base>, "Const can only be true when Base models forward_range."); 205 206 static constexpr bool __ref_is_glvalue = is_reference_v<_InnerBase>; 207 208 _Parent* __parent_ = nullptr; 209 210 static constexpr bool _OuterIterPresent = forward_range<_Base>; 211 using _OuterIterType _LIBCPP_NODEBUG = _If<_OuterIterPresent, _OuterIter, std::__empty>; 212 _LIBCPP_NO_UNIQUE_ADDRESS _OuterIterType __outer_it_ = _OuterIterType(); 213 214 variant<_PatternIter, _InnerIter> __inner_it_; 215 216 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent& __parent, _OuterIter __outer) 217 requires forward_range<_Base> 218 : __parent_(std::addressof(__parent)), __outer_it_(std::move(__outer)) { 219 if (__get_outer() != ranges::end(__parent_->__base_)) { 220 __inner_it_.template emplace<1>(ranges::begin(__update_inner())); 221 __satisfy(); 222 } 223 } 224 225 _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(_Parent& __parent) 226 requires(!forward_range<_Base>) 227 : __parent_(std::addressof(__parent)) { 228 if (__get_outer() != ranges::end(__parent_->__base_)) { 229 __inner_it_.template emplace<1>(ranges::begin(__update_inner())); 230 __satisfy(); 231 } 232 } 233 234 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _OuterIter& __get_outer() { 235 if constexpr (forward_range<_Base>) 236 return __outer_it_; 237 else 238 return *__parent_->__outer_it_; 239 } 240 241 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr const _OuterIter& __get_outer() const { 242 if constexpr (forward_range<_Base>) 243 return __outer_it_; 244 else 245 return *__parent_->__outer_it_; 246 } 247 248 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto& __update_inner() { 249 if constexpr (__ref_is_glvalue) 250 return std::__as_lvalue(*__get_outer()); 251 else 252 return __parent_->__inner_.__emplace_from([this]() -> decltype(auto) { return *__get_outer(); }); 253 } 254 255 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto& __get_inner() { 256 if constexpr (__ref_is_glvalue) 257 return std::__as_lvalue(*__get_outer()); 258 else 259 return *__parent_->__inner_; 260 } 261 262 _LIBCPP_HIDE_FROM_ABI constexpr void __satisfy() { 263 while (true) { 264 if (__inner_it_.index() == 0) { 265 if (std::get<0>(__inner_it_) != ranges::end(__parent_->__pattern_)) 266 break; 267 268 __inner_it_.template emplace<1>(ranges::begin(__update_inner())); 269 } else { 270 if (std::get<1>(__inner_it_) != ranges::end(__get_inner())) 271 break; 272 273 if (++__get_outer() == ranges::end(__parent_->__base_)) { 274 if constexpr (__ref_is_glvalue) 275 __inner_it_.template emplace<0>(); 276 277 break; 278 } 279 280 __inner_it_.template emplace<0>(ranges::begin(__parent_->__pattern_)); 281 } 282 } 283 } 284 285 [[nodiscard]] static consteval auto __get_iterator_concept() noexcept { 286 if constexpr (__ref_is_glvalue && bidirectional_range<_Base> && __bidirectional_common<_InnerBase> && 287 __bidirectional_common<_PatternBase>) 288 return bidirectional_iterator_tag{}; 289 else if constexpr (__ref_is_glvalue && forward_range<_Base> && forward_range<_InnerBase>) 290 return forward_iterator_tag{}; 291 else 292 return input_iterator_tag{}; 293 } 294 295 public: 296 using iterator_concept = decltype(__get_iterator_concept()); 297 using value_type = common_type_t<iter_value_t<_InnerIter>, iter_value_t<_PatternIter>>; 298 using difference_type = 299 common_type_t<iter_difference_t<_OuterIter>, iter_difference_t<_InnerIter>, iter_difference_t<_PatternIter>>; 300 301 _LIBCPP_HIDE_FROM_ABI __iterator() = default; 302 303 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i) 304 requires _Const && convertible_to<iterator_t<_View>, _OuterIter> && 305 convertible_to<iterator_t<_InnerRng>, _InnerIter> && convertible_to<iterator_t<_Pattern>, _PatternIter> 306 : __parent_(__i.__parent_), __outer_it_(std::move(__i.__outer_it_)) { 307 if (__i.__inner_it_.index() == 0) { 308 __inner_it_.template emplace<0>(std::get<0>(std::move(__i.__inner_it_))); 309 } else { 310 __inner_it_.template emplace<1>(std::get<1>(std::move(__i.__inner_it_))); 311 } 312 } 313 314 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const { 315 using __reference = common_reference_t<iter_reference_t<_InnerIter>, iter_reference_t<_PatternIter>>; 316 return std::visit([](auto& __it) -> __reference { return *__it; }, __inner_it_); 317 } 318 319 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { 320 std::visit([](auto& __it) { ++__it; }, __inner_it_); 321 __satisfy(); 322 return *this; 323 } 324 325 _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; } 326 327 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) 328 requires __ref_is_glvalue && forward_iterator<_OuterIter> && forward_iterator<_InnerIter> 329 { 330 __iterator __tmp = *this; 331 ++*this; 332 return __tmp; 333 } 334 335 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--() 336 requires __ref_is_glvalue 337 && bidirectional_range<_Base> && __bidirectional_common<_InnerBase> && __bidirectional_common<_PatternBase> 338 { 339 if (__outer_it_ == ranges::end(__parent_->__base_)) { 340 auto&& __inner = *--__outer_it_; 341 __inner_it_.template emplace<1>(ranges::end(__inner)); 342 } 343 344 while (true) { 345 if (__inner_it_.index() == 0) { 346 auto& __it = std::get<0>(__inner_it_); 347 if (__it == ranges::begin(__parent_->__pattern_)) { 348 auto&& __inner = *--__outer_it_; 349 __inner_it_.template emplace<1>(ranges::end(__inner)); 350 } else 351 break; 352 } else { 353 auto& __it = std::get<1>(__inner_it_); 354 auto&& __inner = *__outer_it_; 355 if (__it == ranges::begin(__inner)) 356 __inner_it_.template emplace<0>(ranges::end(__parent_->__pattern_)); 357 else 358 break; 359 } 360 } 361 362 std::visit([](auto& __it) { --__it; }, __inner_it_); 363 return *this; 364 } 365 366 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int) 367 requires __ref_is_glvalue 368 && bidirectional_range<_Base> && __bidirectional_common<_InnerBase> && __bidirectional_common<_PatternBase> 369 { 370 __iterator __tmp = *this; 371 --*this; 372 return __tmp; 373 } 374 375 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) 376 requires __ref_is_glvalue && forward_range<_Base> && equality_comparable<_InnerIter> 377 { 378 return __x.__outer_it_ == __y.__outer_it_ && __x.__inner_it_ == __y.__inner_it_; 379 } 380 381 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto) iter_move(const __iterator& __x) { 382 using __rvalue_reference = 383 common_reference_t<iter_rvalue_reference_t<_InnerIter>, iter_rvalue_reference_t<_PatternIter>>; 384 return std::visit<__rvalue_reference>(ranges::iter_move, __x.__inner_it_); 385 } 386 387 _LIBCPP_HIDE_FROM_ABI friend constexpr void iter_swap(const __iterator& __x, const __iterator& __y) 388 requires indirectly_swappable<_InnerIter, _PatternIter> 389 { 390 std::visit(ranges::iter_swap, __x.__inner_it_, __y.__inner_it_); 391 } 392 }; 393 394 template <input_range _View, forward_range _Pattern> 395 requires view<_View> && input_range<range_reference_t<_View>> && view<_Pattern> && 396 __concatable<range_reference_t<_View>, _Pattern> 397 template <bool _Const> 398 struct join_with_view<_View, _Pattern>::__sentinel { 399 private: 400 friend join_with_view; 401 402 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, join_with_view>; 403 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>; 404 405 _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_Base> __end_ = sentinel_t<_Base>(); 406 407 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {} 408 409 template <bool _OtherConst> 410 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto& __get_outer_of(const __iterator<_OtherConst>& __x) { 411 return __x.__get_outer(); 412 } 413 414 public: 415 _LIBCPP_HIDE_FROM_ABI __sentinel() = default; 416 417 _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __s) 418 requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>> 419 : __end_(std::move(__s.__end_)) {} 420 421 template <bool _OtherConst> 422 requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>> 423 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr bool 424 operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) { 425 return __get_outer_of(__x) == __y.__end_; 426 } 427 }; 428 429 namespace views { 430 namespace __join_with_view { 431 struct __fn { 432 template <class _Range, class _Pattern> 433 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const 434 noexcept(noexcept(/**/ join_with_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))) 435 -> decltype(/*--*/ join_with_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))) { 436 return /*-------------*/ join_with_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); 437 } 438 439 template <class _Pattern> 440 requires constructible_from<decay_t<_Pattern>, _Pattern> 441 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const 442 noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) { 443 return __pipeable(std::__bind_back(*this, std::forward<_Pattern>(__pattern))); 444 } 445 }; 446 } // namespace __join_with_view 447 448 inline namespace __cpo { 449 inline constexpr auto join_with = __join_with_view::__fn{}; 450 } // namespace __cpo 451 } // namespace views 452 } // namespace ranges 453 454 #endif // _LIBCPP_STD_VER >= 23 455 456 _LIBCPP_END_NAMESPACE_STD 457 458 _LIBCPP_POP_MACROS 459 460 #endif // _LIBCPP___RANGES_JOIN_WITH_VIEW_H 461