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_LAZY_SPLIT_VIEW_H 11 #define _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H 12 13 #include <__algorithm/ranges_find.h> 14 #include <__algorithm/ranges_mismatch.h> 15 #include <__assert> 16 #include <__concepts/constructible.h> 17 #include <__concepts/convertible_to.h> 18 #include <__concepts/derived_from.h> 19 #include <__config> 20 #include <__functional/bind_back.h> 21 #include <__functional/ranges_operations.h> 22 #include <__iterator/concepts.h> 23 #include <__iterator/default_sentinel.h> 24 #include <__iterator/incrementable_traits.h> 25 #include <__iterator/indirectly_comparable.h> 26 #include <__iterator/iter_move.h> 27 #include <__iterator/iter_swap.h> 28 #include <__iterator/iterator_traits.h> 29 #include <__memory/addressof.h> 30 #include <__ranges/access.h> 31 #include <__ranges/all.h> 32 #include <__ranges/concepts.h> 33 #include <__ranges/non_propagating_cache.h> 34 #include <__ranges/range_adaptor.h> 35 #include <__ranges/single_view.h> 36 #include <__ranges/subrange.h> 37 #include <__ranges/view_interface.h> 38 #include <__type_traits/conditional.h> 39 #include <__type_traits/decay.h> 40 #include <__type_traits/is_nothrow_constructible.h> 41 #include <__type_traits/maybe_const.h> 42 #include <__type_traits/remove_reference.h> 43 #include <__utility/forward.h> 44 #include <__utility/move.h> 45 46 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 47 # pragma GCC system_header 48 #endif 49 50 _LIBCPP_BEGIN_NAMESPACE_STD 51 52 #if _LIBCPP_STD_VER >= 20 53 54 namespace ranges { 55 56 template <auto> struct __require_constant; 57 58 template <class _Range> 59 concept __tiny_range = 60 sized_range<_Range> && 61 requires { typename __require_constant<remove_reference_t<_Range>::size()>; } && 62 (remove_reference_t<_Range>::size() <= 1); 63 64 template <input_range _View, forward_range _Pattern> 65 requires view<_View> && view<_Pattern> && 66 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> && 67 (forward_range<_View> || __tiny_range<_Pattern>) 68 class lazy_split_view : public view_interface<lazy_split_view<_View, _Pattern>> { 69 70 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 71 _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern(); 72 73 using _MaybeCurrent = _If<!forward_range<_View>, __non_propagating_cache<iterator_t<_View>>, __empty_cache>; 74 _LIBCPP_NO_UNIQUE_ADDRESS _MaybeCurrent __current_ = _MaybeCurrent(); 75 76 template <bool> struct __outer_iterator; 77 template <bool> struct __inner_iterator; 78 79 public: 80 _LIBCPP_HIDE_FROM_ABI 81 lazy_split_view() 82 requires default_initializable<_View> && default_initializable<_Pattern> = default; 83 84 _LIBCPP_HIDE_FROM_ABI 85 constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 lazy_split_view(_View __base, _Pattern __pattern) 86 : __base_(std::move(__base)), __pattern_(std::move(__pattern)) {} 87 88 template <input_range _Range> 89 requires constructible_from<_View, views::all_t<_Range>> && 90 constructible_from<_Pattern, single_view<range_value_t<_Range>>> 91 _LIBCPP_HIDE_FROM_ABI 92 constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 lazy_split_view(_Range&& __r, range_value_t<_Range> __e) 93 : __base_(views::all(std::forward<_Range>(__r))) 94 , __pattern_(views::single(std::move(__e))) {} 95 96 _LIBCPP_HIDE_FROM_ABI 97 constexpr _View base() const& requires copy_constructible<_View> { return __base_; } 98 _LIBCPP_HIDE_FROM_ABI 99 constexpr _View base() && { return std::move(__base_); } 100 101 _LIBCPP_HIDE_FROM_ABI 102 constexpr auto begin() { 103 if constexpr (forward_range<_View>) { 104 return __outer_iterator<__simple_view<_View> && __simple_view<_Pattern>>{*this, ranges::begin(__base_)}; 105 } else { 106 __current_.__emplace(ranges::begin(__base_)); 107 return __outer_iterator<false>{*this}; 108 } 109 } 110 111 _LIBCPP_HIDE_FROM_ABI 112 constexpr auto begin() const requires forward_range<_View> && forward_range<const _View> { 113 return __outer_iterator<true>{*this, ranges::begin(__base_)}; 114 } 115 116 _LIBCPP_HIDE_FROM_ABI 117 constexpr auto end() requires forward_range<_View> && common_range<_View> { 118 return __outer_iterator<__simple_view<_View> && __simple_view<_Pattern>>{*this, ranges::end(__base_)}; 119 } 120 121 _LIBCPP_HIDE_FROM_ABI 122 constexpr auto end() const { 123 if constexpr (forward_range<_View> && forward_range<const _View> && common_range<const _View>) { 124 return __outer_iterator<true>{*this, ranges::end(__base_)}; 125 } else { 126 return default_sentinel; 127 } 128 } 129 130 private: 131 132 template <class> 133 struct __outer_iterator_category {}; 134 135 template <forward_range _Tp> 136 struct __outer_iterator_category<_Tp> { 137 using iterator_category = input_iterator_tag; 138 }; 139 140 template <bool _Const> 141 struct __outer_iterator : __outer_iterator_category<__maybe_const<_Const, _View>> { 142 private: 143 template <bool> 144 friend struct __inner_iterator; 145 friend __outer_iterator<true>; 146 147 using _Parent = __maybe_const<_Const, lazy_split_view>; 148 using _Base = __maybe_const<_Const, _View>; 149 150 _Parent* __parent_ = nullptr; 151 using _MaybeCurrent = _If<forward_range<_View>, iterator_t<_Base>, __empty_cache>; 152 _LIBCPP_NO_UNIQUE_ADDRESS _MaybeCurrent __current_ = _MaybeCurrent(); 153 bool __trailing_empty_ = false; 154 155 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 156 constexpr auto& __current() noexcept { 157 if constexpr (forward_range<_View>) { 158 return __current_; 159 } else { 160 return *__parent_->__current_; 161 } 162 } 163 164 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 165 constexpr const auto& __current() const noexcept { 166 if constexpr (forward_range<_View>) { 167 return __current_; 168 } else { 169 return *__parent_->__current_; 170 } 171 } 172 173 // Workaround for the GCC issue that doesn't allow calling `__parent_->__base_` from friend functions (because 174 // `__base_` is private). 175 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 176 constexpr auto& __parent_base() const noexcept { 177 return __parent_->__base_; 178 } 179 180 public: 181 // using iterator_category = inherited; 182 using iterator_concept = conditional_t<forward_range<_Base>, forward_iterator_tag, input_iterator_tag>; 183 using difference_type = range_difference_t<_Base>; 184 185 struct value_type : view_interface<value_type> { 186 private: 187 __outer_iterator __i_ = __outer_iterator(); 188 189 public: 190 _LIBCPP_HIDE_FROM_ABI 191 value_type() = default; 192 _LIBCPP_HIDE_FROM_ABI 193 constexpr explicit value_type(__outer_iterator __i) 194 : __i_(std::move(__i)) {} 195 196 _LIBCPP_HIDE_FROM_ABI 197 constexpr __inner_iterator<_Const> begin() const { return __inner_iterator<_Const>{__i_}; } 198 _LIBCPP_HIDE_FROM_ABI 199 constexpr default_sentinel_t end() const noexcept { return default_sentinel; } 200 }; 201 202 _LIBCPP_HIDE_FROM_ABI 203 __outer_iterator() = default; 204 205 _LIBCPP_HIDE_FROM_ABI 206 constexpr explicit __outer_iterator(_Parent& __parent) 207 requires (!forward_range<_Base>) 208 : __parent_(std::addressof(__parent)) {} 209 210 _LIBCPP_HIDE_FROM_ABI 211 constexpr __outer_iterator(_Parent& __parent, iterator_t<_Base> __current) 212 requires forward_range<_Base> 213 : __parent_(std::addressof(__parent)), __current_(std::move(__current)) {} 214 215 _LIBCPP_HIDE_FROM_ABI 216 constexpr __outer_iterator(__outer_iterator<!_Const> __i) 217 requires _Const && convertible_to<iterator_t<_View>, iterator_t<_Base>> 218 : __parent_(__i.__parent_), __current_(std::move(__i.__current_)) {} 219 220 _LIBCPP_HIDE_FROM_ABI 221 constexpr value_type operator*() const { return value_type{*this}; } 222 223 _LIBCPP_HIDE_FROM_ABI 224 constexpr __outer_iterator& operator++() { 225 const auto __end = ranges::end(__parent_->__base_); 226 if (__current() == __end) { 227 __trailing_empty_ = false; 228 return *this; 229 } 230 231 const auto [__pbegin, __pend] = ranges::subrange{__parent_->__pattern_}; 232 if (__pbegin == __pend) { 233 // Empty pattern: split on every element in the input range 234 ++__current(); 235 236 } else if constexpr (__tiny_range<_Pattern>) { 237 // One-element pattern: we can use `ranges::find`. 238 __current() = ranges::find(std::move(__current()), __end, *__pbegin); 239 if (__current() != __end) { 240 // Make sure we point to after the separator we just found. 241 ++__current(); 242 if (__current() == __end) 243 __trailing_empty_ = true; 244 } 245 246 } else { 247 // General case for n-element pattern. 248 do { 249 const auto [__b, __p] = ranges::mismatch(__current(), __end, __pbegin, __pend); 250 if (__p == __pend) { 251 __current() = __b; 252 if (__current() == __end) { 253 __trailing_empty_ = true; 254 } 255 break; // The pattern matched; skip it. 256 } 257 } while (++__current() != __end); 258 } 259 260 return *this; 261 } 262 263 _LIBCPP_HIDE_FROM_ABI 264 constexpr decltype(auto) operator++(int) { 265 if constexpr (forward_range<_Base>) { 266 auto __tmp = *this; 267 ++*this; 268 return __tmp; 269 270 } else { 271 ++*this; 272 } 273 } 274 275 _LIBCPP_HIDE_FROM_ABI 276 friend constexpr bool operator==(const __outer_iterator& __x, const __outer_iterator& __y) 277 requires forward_range<_Base> { 278 return __x.__current_ == __y.__current_ && __x.__trailing_empty_ == __y.__trailing_empty_; 279 } 280 281 _LIBCPP_HIDE_FROM_ABI 282 friend constexpr bool operator==(const __outer_iterator& __x, default_sentinel_t) { 283 _LIBCPP_ASSERT_UNCATEGORIZED(__x.__parent_, "Cannot call comparison on a default-constructed iterator."); 284 return __x.__current() == ranges::end(__x.__parent_base()) && !__x.__trailing_empty_; 285 } 286 }; 287 288 template <class> 289 struct __inner_iterator_category {}; 290 291 template <forward_range _Tp> 292 struct __inner_iterator_category<_Tp> { 293 using iterator_category = _If< 294 derived_from<typename iterator_traits<iterator_t<_Tp>>::iterator_category, forward_iterator_tag>, 295 forward_iterator_tag, 296 typename iterator_traits<iterator_t<_Tp>>::iterator_category 297 >; 298 }; 299 300 template <bool _Const> 301 struct __inner_iterator : __inner_iterator_category<__maybe_const<_Const, _View>> { 302 private: 303 using _Base = __maybe_const<_Const, _View>; 304 // Workaround for a GCC issue. 305 static constexpr bool _OuterConst = _Const; 306 __outer_iterator<_Const> __i_ = __outer_iterator<_OuterConst>(); 307 bool __incremented_ = false; 308 309 // Note: these private functions are necessary because GCC doesn't allow calls to private members of `__i_` from 310 // free functions that are friends of `inner-iterator`. 311 312 _LIBCPP_HIDE_FROM_ABI 313 constexpr bool __is_done() const { 314 _LIBCPP_ASSERT_UNCATEGORIZED(__i_.__parent_, "Cannot call comparison on a default-constructed iterator."); 315 316 auto [__pcur, __pend] = ranges::subrange{__i_.__parent_->__pattern_}; 317 auto __end = ranges::end(__i_.__parent_->__base_); 318 319 if constexpr (__tiny_range<_Pattern>) { 320 const auto& __cur = __i_.__current(); 321 if (__cur == __end) 322 return true; 323 if (__pcur == __pend) 324 return __incremented_; 325 326 return *__cur == *__pcur; 327 328 } else { 329 auto __cur = __i_.__current(); 330 if (__cur == __end) 331 return true; 332 if (__pcur == __pend) 333 return __incremented_; 334 335 do { 336 if (*__cur != *__pcur) 337 return false; 338 if (++__pcur == __pend) 339 return true; 340 } while (++__cur != __end); 341 342 return false; 343 } 344 } 345 346 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 347 constexpr auto& __outer_current() noexcept { 348 return __i_.__current(); 349 } 350 351 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 352 constexpr const auto& __outer_current() const noexcept { 353 return __i_.__current(); 354 } 355 356 public: 357 // using iterator_category = inherited; 358 using iterator_concept = typename __outer_iterator<_Const>::iterator_concept; 359 using value_type = range_value_t<_Base>; 360 using difference_type = range_difference_t<_Base>; 361 362 _LIBCPP_HIDE_FROM_ABI 363 __inner_iterator() = default; 364 365 _LIBCPP_HIDE_FROM_ABI 366 constexpr explicit __inner_iterator(__outer_iterator<_Const> __i) 367 : __i_(std::move(__i)) {} 368 369 _LIBCPP_HIDE_FROM_ABI 370 constexpr const iterator_t<_Base>& base() const& noexcept { return __i_.__current(); } 371 _LIBCPP_HIDE_FROM_ABI 372 constexpr iterator_t<_Base> base() && 373 requires forward_range<_View> { return std::move(__i_.__current()); } 374 375 _LIBCPP_HIDE_FROM_ABI 376 constexpr decltype(auto) operator*() const { return *__i_.__current(); } 377 378 _LIBCPP_HIDE_FROM_ABI 379 constexpr __inner_iterator& operator++() { 380 __incremented_ = true; 381 382 if constexpr (!forward_range<_Base>) { 383 if constexpr (_Pattern::size() == 0) { 384 return *this; 385 } 386 } 387 388 ++__i_.__current(); 389 return *this; 390 } 391 392 _LIBCPP_HIDE_FROM_ABI 393 constexpr decltype(auto) operator++(int) { 394 if constexpr (forward_range<_Base>) { 395 auto __tmp = *this; 396 ++*this; 397 return __tmp; 398 399 } else { 400 ++*this; 401 } 402 } 403 404 _LIBCPP_HIDE_FROM_ABI 405 friend constexpr bool operator==(const __inner_iterator& __x, const __inner_iterator& __y) 406 requires forward_range<_Base> { 407 return __x.__outer_current() == __y.__outer_current(); 408 } 409 410 _LIBCPP_HIDE_FROM_ABI 411 friend constexpr bool operator==(const __inner_iterator& __x, default_sentinel_t) { 412 return __x.__is_done(); 413 } 414 415 _LIBCPP_HIDE_FROM_ABI 416 friend constexpr decltype(auto) iter_move(const __inner_iterator& __i) 417 noexcept(noexcept(ranges::iter_move(__i.__outer_current()))) { 418 return ranges::iter_move(__i.__outer_current()); 419 } 420 421 _LIBCPP_HIDE_FROM_ABI 422 friend constexpr void iter_swap(const __inner_iterator& __x, const __inner_iterator& __y) 423 noexcept(noexcept(ranges::iter_swap(__x.__outer_current(), __y.__outer_current()))) 424 requires indirectly_swappable<iterator_t<_Base>> { 425 ranges::iter_swap(__x.__outer_current(), __y.__outer_current()); 426 } 427 }; 428 429 }; 430 431 template <class _Range, class _Pattern> 432 lazy_split_view(_Range&&, _Pattern&&) -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>; 433 434 template <input_range _Range> 435 lazy_split_view(_Range&&, range_value_t<_Range>) 436 -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>; 437 438 namespace views { 439 namespace __lazy_split_view { 440 struct __fn : __range_adaptor_closure<__fn> { 441 template <class _Range, class _Pattern> 442 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 443 constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const 444 noexcept(noexcept(lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))) 445 -> decltype( lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))) 446 { return lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); } 447 448 template <class _Pattern> 449 requires constructible_from<decay_t<_Pattern>, _Pattern> 450 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 451 constexpr auto operator()(_Pattern&& __pattern) const 452 noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) { 453 return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern))); 454 } 455 }; 456 } // namespace __lazy_split_view 457 458 inline namespace __cpo { 459 inline constexpr auto lazy_split = __lazy_split_view::__fn{}; 460 } // namespace __cpo 461 } // namespace views 462 463 } // namespace ranges 464 465 #endif // _LIBCPP_STD_VER >= 20 466 467 _LIBCPP_END_NAMESPACE_STD 468 469 #endif // _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H 470