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 #ifndef _LIBCPP___RANGES_JOIN_VIEW_H 10 #define _LIBCPP___RANGES_JOIN_VIEW_H 11 12 #include <__concepts/constructible.h> 13 #include <__concepts/convertible_to.h> 14 #include <__concepts/copyable.h> 15 #include <__concepts/derived_from.h> 16 #include <__concepts/equality_comparable.h> 17 #include <__config> 18 #include <__iterator/concepts.h> 19 #include <__iterator/iter_move.h> 20 #include <__iterator/iter_swap.h> 21 #include <__iterator/iterator_traits.h> 22 #include <__ranges/access.h> 23 #include <__ranges/all.h> 24 #include <__ranges/concepts.h> 25 #include <__ranges/non_propagating_cache.h> 26 #include <__ranges/range_adaptor.h> 27 #include <__ranges/view_interface.h> 28 #include <__utility/forward.h> 29 #include <optional> 30 #include <type_traits> 31 32 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 33 # pragma GCC system_header 34 #endif 35 36 _LIBCPP_BEGIN_NAMESPACE_STD 37 38 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 39 40 namespace ranges { 41 template<class> 42 struct __join_view_iterator_category {}; 43 44 template<class _View> 45 requires is_reference_v<range_reference_t<_View>> && 46 forward_range<_View> && 47 forward_range<range_reference_t<_View>> 48 struct __join_view_iterator_category<_View> { 49 using _OuterC = typename iterator_traits<iterator_t<_View>>::iterator_category; 50 using _InnerC = typename iterator_traits<iterator_t<range_reference_t<_View>>>::iterator_category; 51 52 using iterator_category = _If< 53 derived_from<_OuterC, bidirectional_iterator_tag> && derived_from<_InnerC, bidirectional_iterator_tag> && 54 common_range<range_reference_t<_View>>, 55 bidirectional_iterator_tag, 56 _If< 57 derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>, 58 forward_iterator_tag, 59 input_iterator_tag 60 > 61 >; 62 }; 63 64 template<input_range _View> 65 requires view<_View> && input_range<range_reference_t<_View>> 66 class join_view 67 : public view_interface<join_view<_View>> { 68 private: 69 using _InnerRange = range_reference_t<_View>; 70 71 template<bool> struct __iterator; 72 template<bool> struct __sentinel; 73 74 static constexpr bool _UseCache = !is_reference_v<_InnerRange>; 75 using _Cache = _If<_UseCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>; 76 _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cache_; 77 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 78 79 public: 80 _LIBCPP_HIDE_FROM_ABI 81 join_view() requires default_initializable<_View> = default; 82 83 _LIBCPP_HIDE_FROM_ABI 84 constexpr explicit join_view(_View __base) 85 : __base_(std::move(__base)) {} 86 87 _LIBCPP_HIDE_FROM_ABI 88 constexpr _View base() const& requires copy_constructible<_View> { return __base_; } 89 90 _LIBCPP_HIDE_FROM_ABI 91 constexpr _View base() && { return std::move(__base_); } 92 93 _LIBCPP_HIDE_FROM_ABI 94 constexpr auto begin() { 95 constexpr bool __use_const = __simple_view<_View> && 96 is_reference_v<range_reference_t<_View>>; 97 return __iterator<__use_const>{*this, ranges::begin(__base_)}; 98 } 99 100 template<class _V2 = _View> 101 _LIBCPP_HIDE_FROM_ABI 102 constexpr auto begin() const 103 requires input_range<const _V2> && 104 is_reference_v<range_reference_t<const _V2>> 105 { 106 return __iterator<true>{*this, ranges::begin(__base_)}; 107 } 108 109 _LIBCPP_HIDE_FROM_ABI 110 constexpr auto end() { 111 if constexpr (forward_range<_View> && 112 is_reference_v<_InnerRange> && 113 forward_range<_InnerRange> && 114 common_range<_View> && 115 common_range<_InnerRange>) 116 return __iterator<__simple_view<_View>>{*this, ranges::end(__base_)}; 117 else 118 return __sentinel<__simple_view<_View>>{*this}; 119 } 120 121 template<class _V2 = _View> 122 _LIBCPP_HIDE_FROM_ABI 123 constexpr auto end() const 124 requires input_range<const _V2> && 125 is_reference_v<range_reference_t<const _V2>> 126 { 127 using _ConstInnerRange = range_reference_t<const _View>; 128 if constexpr (forward_range<const _View> && 129 is_reference_v<_ConstInnerRange> && 130 forward_range<_ConstInnerRange> && 131 common_range<const _View> && 132 common_range<_ConstInnerRange>) { 133 return __iterator<true>{*this, ranges::end(__base_)}; 134 } else { 135 return __sentinel<true>{*this}; 136 } 137 } 138 }; 139 140 template<input_range _View> 141 requires view<_View> && input_range<range_reference_t<_View>> 142 template<bool _Const> struct join_view<_View>::__sentinel { 143 template<bool> friend struct __sentinel; 144 145 private: 146 using _Parent = __maybe_const<_Const, join_view>; 147 using _Base = __maybe_const<_Const, _View>; 148 sentinel_t<_Base> __end_ = sentinel_t<_Base>(); 149 150 public: 151 _LIBCPP_HIDE_FROM_ABI 152 __sentinel() = default; 153 154 _LIBCPP_HIDE_FROM_ABI 155 constexpr explicit __sentinel(_Parent& __parent) 156 : __end_(ranges::end(__parent.__base_)) {} 157 158 _LIBCPP_HIDE_FROM_ABI 159 constexpr __sentinel(__sentinel<!_Const> __s) 160 requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>> 161 : __end_(std::move(__s.__end_)) {} 162 163 template<bool _OtherConst> 164 requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>> 165 _LIBCPP_HIDE_FROM_ABI 166 friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) { 167 return __x.__outer_ == __y.__end_; 168 } 169 }; 170 171 template<input_range _View> 172 requires view<_View> && input_range<range_reference_t<_View>> 173 template<bool _Const> struct join_view<_View>::__iterator 174 : public __join_view_iterator_category<__maybe_const<_Const, _View>> { 175 176 template<bool> friend struct __iterator; 177 178 private: 179 using _Parent = __maybe_const<_Const, join_view>; 180 using _Base = __maybe_const<_Const, _View>; 181 using _Outer = iterator_t<_Base>; 182 using _Inner = iterator_t<range_reference_t<_Base>>; 183 184 static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>; 185 186 public: 187 _Outer __outer_ = _Outer(); 188 189 private: 190 optional<_Inner> __inner_; 191 _Parent *__parent_ = nullptr; 192 193 _LIBCPP_HIDE_FROM_ABI 194 constexpr void __satisfy() { 195 for (; __outer_ != ranges::end(__parent_->__base_); ++__outer_) { 196 auto&& __inner = [&]() -> auto&& { 197 if constexpr (__ref_is_glvalue) 198 return *__outer_; 199 else 200 return __parent_->__cache_.__emplace_from([&]() -> decltype(auto) { return *__outer_; }); 201 }(); 202 __inner_ = ranges::begin(__inner); 203 if (*__inner_ != ranges::end(__inner)) 204 return; 205 } 206 207 if constexpr (__ref_is_glvalue) 208 __inner_.reset(); 209 } 210 211 public: 212 using iterator_concept = _If< 213 __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> && 214 common_range<range_reference_t<_Base>>, 215 bidirectional_iterator_tag, 216 _If< 217 __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>, 218 forward_iterator_tag, 219 input_iterator_tag 220 > 221 >; 222 223 using value_type = range_value_t<range_reference_t<_Base>>; 224 225 using difference_type = common_type_t< 226 range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>; 227 228 _LIBCPP_HIDE_FROM_ABI 229 __iterator() requires default_initializable<_Outer> = default; 230 231 _LIBCPP_HIDE_FROM_ABI 232 constexpr __iterator(_Parent& __parent, _Outer __outer) 233 : __outer_(std::move(__outer)) 234 , __parent_(std::addressof(__parent)) { 235 __satisfy(); 236 } 237 238 _LIBCPP_HIDE_FROM_ABI 239 constexpr __iterator(__iterator<!_Const> __i) 240 requires _Const && 241 convertible_to<iterator_t<_View>, _Outer> && 242 convertible_to<iterator_t<_InnerRange>, _Inner> 243 : __outer_(std::move(__i.__outer_)) 244 , __inner_(std::move(__i.__inner_)) 245 , __parent_(__i.__parent_) {} 246 247 _LIBCPP_HIDE_FROM_ABI 248 constexpr decltype(auto) operator*() const { 249 return **__inner_; 250 } 251 252 _LIBCPP_HIDE_FROM_ABI 253 constexpr _Inner operator->() const 254 requires __has_arrow<_Inner> && copyable<_Inner> 255 { 256 return *__inner_; 257 } 258 259 _LIBCPP_HIDE_FROM_ABI 260 constexpr __iterator& operator++() { 261 auto&& __inner = [&]() -> auto&& { 262 if constexpr (__ref_is_glvalue) 263 return *__outer_; 264 else 265 return *__parent_->__cache_; 266 }(); 267 if (++*__inner_ == ranges::end(__inner)) { 268 ++__outer_; 269 __satisfy(); 270 } 271 return *this; 272 } 273 274 _LIBCPP_HIDE_FROM_ABI 275 constexpr void operator++(int) { 276 ++*this; 277 } 278 279 _LIBCPP_HIDE_FROM_ABI 280 constexpr __iterator operator++(int) 281 requires __ref_is_glvalue && 282 forward_range<_Base> && 283 forward_range<range_reference_t<_Base>> 284 { 285 auto __tmp = *this; 286 ++*this; 287 return __tmp; 288 } 289 290 _LIBCPP_HIDE_FROM_ABI 291 constexpr __iterator& operator--() 292 requires __ref_is_glvalue && 293 bidirectional_range<_Base> && 294 bidirectional_range<range_reference_t<_Base>> && 295 common_range<range_reference_t<_Base>> 296 { 297 if (__outer_ == ranges::end(__parent_->__base_)) 298 __inner_ = ranges::end(*--__outer_); 299 300 // Skip empty inner ranges when going backwards. 301 while (*__inner_ == ranges::begin(*__outer_)) { 302 __inner_ = ranges::end(*--__outer_); 303 } 304 305 --*__inner_; 306 return *this; 307 } 308 309 _LIBCPP_HIDE_FROM_ABI 310 constexpr __iterator operator--(int) 311 requires __ref_is_glvalue && 312 bidirectional_range<_Base> && 313 bidirectional_range<range_reference_t<_Base>> && 314 common_range<range_reference_t<_Base>> 315 { 316 auto __tmp = *this; 317 --*this; 318 return __tmp; 319 } 320 321 _LIBCPP_HIDE_FROM_ABI 322 friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) 323 requires __ref_is_glvalue && 324 equality_comparable<iterator_t<_Base>> && 325 equality_comparable<iterator_t<range_reference_t<_Base>>> 326 { 327 return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_; 328 } 329 330 _LIBCPP_HIDE_FROM_ABI 331 friend constexpr decltype(auto) iter_move(const __iterator& __i) 332 noexcept(noexcept(ranges::iter_move(*__i.__inner_))) 333 { 334 return ranges::iter_move(*__i.__inner_); 335 } 336 337 _LIBCPP_HIDE_FROM_ABI 338 friend constexpr void iter_swap(const __iterator& __x, const __iterator& __y) 339 noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_))) 340 requires indirectly_swappable<_Inner> 341 { 342 return ranges::iter_swap(*__x.__inner_, *__y.__inner_); 343 } 344 }; 345 346 template<class _Range> 347 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>; 348 349 namespace views { 350 namespace __join_view { 351 struct __fn : __range_adaptor_closure<__fn> { 352 template<class _Range> 353 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 354 constexpr auto operator()(_Range&& __range) const 355 noexcept(noexcept(join_view<all_t<_Range&&>>(std::forward<_Range>(__range)))) 356 -> decltype( join_view<all_t<_Range&&>>(std::forward<_Range>(__range))) 357 { return join_view<all_t<_Range&&>>(std::forward<_Range>(__range)); } 358 }; 359 } // namespace __join_view 360 inline namespace __cpo { 361 inline constexpr auto join = __join_view::__fn{}; 362 } // namespace __cpo 363 } // namespace views 364 } // namespace ranges 365 366 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 367 368 _LIBCPP_END_NAMESPACE_STD 369 370 #endif // _LIBCPP___RANGES_JOIN_VIEW_H 371