443 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H11#define _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H12 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_header48#endif49 50_LIBCPP_PUSH_MACROS51#include <__undef_macros>52 53_LIBCPP_BEGIN_NAMESPACE_STD54 55#if _LIBCPP_STD_VER >= 2056 57namespace ranges {58 59template <auto>60struct __require_constant;61 62template <class _Range>63concept __tiny_range = sized_range<_Range> && requires {64 typename __require_constant<remove_reference_t<_Range>::size()>;65} && (remove_reference_t<_Range>::size() <= 1);66 67template <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>)71class 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 84public: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() const115 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 134private: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 (because175 // `__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 range221 ++__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_` from294 // 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 403template <class _Range, class _Pattern>404lazy_split_view(_Range&&, _Pattern&&) -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>;405 406template <input_range _Range>407lazy_split_view(_Range&&,408 range_value_t<_Range>) -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;409 410namespace views {411namespace __lazy_split_view {412struct __fn {413 template <class _Range, class _Pattern>414 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const415 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) const423 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_view428 429inline namespace __cpo {430inline constexpr auto lazy_split = __lazy_split_view::__fn{};431} // namespace __cpo432} // namespace views433 434} // namespace ranges435 436#endif // _LIBCPP_STD_VER >= 20437 438_LIBCPP_END_NAMESPACE_STD439 440_LIBCPP_POP_MACROS441 442#endif // _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H443