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