461 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___RANGES_JOIN_WITH_VIEW_H11#define _LIBCPP___RANGES_JOIN_WITH_VIEW_H12 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_header47#endif48 49_LIBCPP_PUSH_MACROS50#include <__undef_macros>51 52_LIBCPP_BEGIN_NAMESPACE_STD53 54#if _LIBCPP_STD_VER >= 2355 56namespace ranges {57template <class _Range>58concept __bidirectional_common = bidirectional_range<_Range> && common_range<_Range>;59 60template <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>63class 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 86public:87 _LIBCPP_HIDE_FROM_ABI join_with_view()88 requires default_initializable<_View> && default_initializable<_Pattern>89 = default;90 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>>>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 100 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&101 requires copy_constructible<_View>102 {103 return __base_;104 }105 106 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }107 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 118 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const119 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 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 else132 return __sentinel<__use_const>{*this};133 }134 135 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() const136 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 else144 return __sentinel<true>{*this};145 }146};147 148template <class _Range, class _Pattern>149join_with_view(_Range&&, _Pattern&&) -> join_with_view<views::all_t<_Range>, views::all_t<_Pattern>>;150 151template <input_range _Range>152join_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 155template <class _Base, class _PatternBase, class _InnerBase = range_reference_t<_Base>>156struct __join_with_view_iterator_category {};157 158template <class _Base, class _PatternBase, class _InnerBase>159 requires is_reference_v<_InnerBase> && forward_range<_Base> && forward_range<_InnerBase>160struct __join_with_view_iterator_category<_Base, _PatternBase, _InnerBase> {161private: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 else179 return input_iterator_tag{};180 }181 182public:183 using iterator_category = decltype(__get_iterator_category());184};185 186template <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>189template <bool _Const>190struct join_with_view<_View, _Pattern>::__iterator191 : public __join_with_view_iterator_category<__maybe_const<_Const, _View>, __maybe_const<_Const, _Pattern>> {192private: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 else238 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 else245 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 else252 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 else259 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 else292 return input_iterator_tag{};293 }294 295public: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_glvalue337 && 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 } else351 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 else358 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_glvalue368 && 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 394template <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>397template <bool _Const>398struct join_with_view<_View, _Pattern>::__sentinel {399private: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 414public: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 bool424 operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {425 return __get_outer_of(__x) == __y.__end_;426 }427};428 429namespace views {430namespace __join_with_view {431struct __fn {432 template <class _Range, class _Pattern>433 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const434 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) const442 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_view447 448inline namespace __cpo {449inline constexpr auto join_with = __join_with_view::__fn{};450} // namespace __cpo451} // namespace views452} // namespace ranges453 454#endif // _LIBCPP_STD_VER >= 23455 456_LIBCPP_END_NAMESPACE_STD457 458_LIBCPP_POP_MACROS459 460#endif // _LIBCPP___RANGES_JOIN_WITH_VIEW_H461