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