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