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