Compiler Explorer

Source code

#include <fmt/format.h>
#include <fmt/ranges.h>

#include <algorithm>
#include <ranges>

// The existing split implementation, as modified by P2210
namespace std::ranges {

template <input_range _Vp, forward_range _Pattern>
requires view<_Vp> && view<_Pattern> &&
    indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
                          ranges::equal_to> &&
    (forward_range<_Vp> ||
     __detail::__tiny_range<_Pattern>)class lazy_split_view
    : public view_interface<lazy_split_view<_Vp, _Pattern>> {
 private:
  template <bool _Const>
  struct _InnerIter;

template <bool _Const>
  struct _OuterIter {
   private:
    using _Parent = __detail::__maybe_const_t<_Const, lazy_split_view>;
    using _Base = __detail::__maybe_const_t<_Const, _Vp>;

constexpr bool __at_end() const {
      return __current() == ranges::end(_M_parent->_M_base) && !trailing_empty;
    }

// [range.split.outer] p1
    //  Many of the following specifications refer to the notional member
    //  current of outer-iterator.  current is equivalent to current_ if
    //  V models forward_range, and parent_->current_ otherwise.
    constexpr auto& __current() noexcept {
      if constexpr (forward_range<_Vp>)
        return _M_current;
      else
        return _M_parent->_M_current;
    }

constexpr auto& __current() const noexcept {
      if constexpr (forward_range<_Vp>)
        return _M_current;
      else
        return _M_parent->_M_current;
    }

_Parent* _M_parent = nullptr;

// XXX: _M_current is present only if "V models forward_range"
    [[no_unique_address]] __detail::__maybe_present_t<forward_range<_Vp>,
                                                      iterator_t<_Base>>
        _M_current;

// P2210: need this extra member on the outer iterator
    bool trailing_empty = false;

public:
    using iterator_concept =
        conditional_t<forward_range<_Base>, forward_iterator_tag,
                      input_iterator_tag>;
    using iterator_category = input_iterator_tag;
    using difference_type = range_difference_t<_Base>;

struct value_type : view_interface<value_type> {
     private:
      _OuterIter _M_i = _OuterIter();

public:
      value_type() = default;

constexpr explicit value_type(_OuterIter __i) : _M_i(std::move(__i)) {}

constexpr _InnerIter<_Const> begin() const requires copyable<_OuterIter> {
        return _InnerIter<_Const>{_M_i};
      }

constexpr _InnerIter<_Const> begin() requires(!copyable<_OuterIter>) {
        return _InnerIter<_Const>{std::move(_M_i)};
      }

constexpr default_sentinel_t end() const { return default_sentinel; }
    };

_OuterIter() = default;

constexpr explicit _OuterIter(_Parent* __parent) requires(
        !forward_range<_Base>)
        : _M_parent(__parent) {}

constexpr _OuterIter(_Parent* __parent,
                         iterator_t<_Base> __current) requires
        forward_range<_Base> : _M_parent(__parent),
                               _M_current(std::move(__current)) {}

constexpr _OuterIter(_OuterIter<!_Const> __i) requires _Const
        && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
        : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current)) {}

constexpr value_type operator*() const { return value_type{*this}; }

constexpr _OuterIter& operator++() {
      const auto __end = ranges::end(_M_parent->_M_base);
      if (__current() == __end) {
        // LWG3478: there's no trailing empty range (if there was one before)
        trailing_empty = false;
        return *this;
      }

const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
      if (__pbegin == __pend) {
        ++__current();
      } else if constexpr (__detail::__tiny_range<_Pattern>) {
        __current() = ranges::find(std::move(__current()), __end, *__pbegin);
        if (__current() != __end) {
          ++__current();
          // LWG3478: if the delimiter is the last element, we still have one more empty to go
          if (__current() == __end) {
            trailing_empty = true;
          }
        }
      } else {
        do {
          auto [__b, __p] = __detail::mismatch(__current(), __end,
                                               __pbegin, __pend);
          if (__p == __pend) {
            __current() = __b;
            // LWG3478: set trailing_empty to true in this case
            if (__current() == __end) {
              trailing_empty = true;
            }
            break;
          }
        } while (++__current() != __end);
      }
      return *this;
    }

constexpr decltype(auto) operator++(int) {
      if constexpr (forward_range<_Base>) {
        auto __tmp = *this;
        ++*this;
        return __tmp;
      } else
        ++*this;
    }

friend constexpr bool operator==(const _OuterIter& __x,
                                     const _OuterIter& __y) requires
        forward_range<_Base> {
      // P2210: also check trailing_empty
      return __x._M_current == __y._M_current &&
             __x.trailing_empty == __y.trailing_empty;
    }

friend constexpr bool operator==(const _OuterIter& __x,
                                     default_sentinel_t) {
      return __x.__at_end();
    };

friend _OuterIter<!_Const>;
    friend _InnerIter<_Const>;
  };

template <bool _Const>
  struct _InnerIter {
   private:
    using _Base = __detail::__maybe_const_t<_Const, _Vp>;

constexpr bool __at_end() const {
      auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
      auto __end = ranges::end(_M_i._M_parent->_M_base);
      if constexpr (__detail::__tiny_range<_Pattern>) {
        const auto& __cur = _M_i_current();
        if (__cur == __end) return true;
        if (__pcur == __pend) return _M_incremented;
        return *__cur == *__pcur;
      } else {
        auto __cur = _M_i_current();
        if (__cur == __end) return true;
        if (__pcur == __pend) return _M_incremented;
        do {
          if (*__cur != *__pcur) return false;
          if (++__pcur == __pend) return true;
        } while (++__cur != __end);
        return false;
      }
    }

static constexpr auto _S_iter_cat() {
      using _Cat =
          typename iterator_traits<iterator_t<_Base>>::iterator_category;
      if constexpr (derived_from<_Cat, forward_iterator_tag>)
        return forward_iterator_tag{};
      else
        return _Cat{};
    }

constexpr auto& _M_i_current() noexcept { return _M_i.__current(); }

constexpr auto& _M_i_current() const noexcept { return _M_i.__current(); }

_OuterIter<_Const> _M_i = _OuterIter<_Const>();
    bool _M_incremented = false;

public:
    using iterator_concept = typename _OuterIter<_Const>::iterator_concept;
    using iterator_category = decltype(_S_iter_cat());
    using value_type = range_value_t<_Base>;
    using difference_type = range_difference_t<_Base>;

_InnerIter() = default;

constexpr explicit _InnerIter(_OuterIter<_Const> __i)
        : _M_i(std::move(__i)) {}

constexpr decltype(auto) operator*() const { return *_M_i_current(); }

// P2210: add base() to inner iterator
    constexpr iterator_t<_Base> base()
        const& requires copyable<iterator_t<_Base>> {
      return _M_i_current();
    }
    constexpr iterator_t<_Base> base() && { return std::move(_M_i_current()); }

constexpr _InnerIter& operator++() {
      _M_incremented = true;
      if constexpr (!forward_range<_Base>)
        if constexpr (_Pattern::size() == 0) return *this;
      ++_M_i_current();
      return *this;
    }

constexpr decltype(auto) operator++(int) {
      if constexpr (forward_range<_Vp>) {
        auto __tmp = *this;
        ++*this;
        return __tmp;
      } else
        ++*this;
    }

friend constexpr bool operator==(const _InnerIter& __x,
                                     const _InnerIter& __y) requires
        forward_range<_Base> {
      return __x._M_i == __y._M_i;
    }

friend constexpr bool operator==(const _InnerIter& __x,
                                     default_sentinel_t) {
      return __x.__at_end();
    }

friend constexpr decltype(auto) iter_move(const _InnerIter& __i) noexcept(
        noexcept(ranges::iter_move(__i._M_i_current()))) {
      return ranges::iter_move(__i._M_i_current());
    }

friend constexpr void
    iter_swap(const _InnerIter& __x, const _InnerIter& __y) noexcept(noexcept(
        ranges::iter_swap(__x._M_i_current(), __y._M_i_current()))) requires
        indirectly_swappable<iterator_t<_Base>> {
      ranges::iter_swap(__x._M_i_current(), __y._M_i_current());
    }
  };

_Pattern _M_pattern = _Pattern();
  // XXX: _M_current is "present only if !forward_range<V>"
  [[no_unique_address]] __detail::__maybe_present_t<!forward_range<_Vp>,
                                                    iterator_t<_Vp>>
      _M_current;
  _Vp _M_base = _Vp();

public:
  lazy_split_view() = default;

constexpr lazy_split_view(_Vp __base, _Pattern __pattern)
      : _M_pattern(std::move(__pattern)), _M_base(std::move(__base)) {}

template <input_range _Range>
  requires constructible_from<_Vp, views::all_t<_Range>> &&
      constructible_from<_Pattern, single_view<range_value_t<_Range>>>
  constexpr lazy_split_view(_Range&& __r, range_value_t<_Range> __e)
      : _M_pattern(std::move(__e)),
        _M_base(views::all(std::forward<_Range>(__r))) {}

constexpr _Vp base() const& requires copy_constructible<_Vp> {
    return _M_base;
  }

constexpr _Vp base() && { return std::move(_M_base); }

constexpr auto begin() {
    if constexpr (forward_range<_Vp>)
      return _OuterIter<__detail::__simple_view<_Vp>>{this,
                                                      ranges::begin(_M_base)};
    else {
      _M_current = ranges::begin(_M_base);
      return _OuterIter<false>{this};
    }
  }

constexpr auto begin() const requires forward_range<_Vp> &&
      forward_range<const _Vp> {
    return _OuterIter<true>{this, ranges::begin(_M_base)};
  }

constexpr auto end() requires forward_range<_Vp> && common_range<_Vp> {
    return _OuterIter<__detail::__simple_view<_Vp>>{this, ranges::end(_M_base)};
  }

constexpr auto end() const {
    if constexpr (forward_range<_Vp> && forward_range<const _Vp> &&
                  common_range<const _Vp>)
      return _OuterIter<true>{this, ranges::end(_M_base)};
    else
      return default_sentinel;
  }
};

template <typename _Range, typename _Pred>
lazy_split_view(_Range&&, _Pred&&)
    -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pred>>;

template <input_range _Range>
lazy_split_view(_Range&&, range_value_t<_Range>)
    -> lazy_split_view<views::all_t<_Range>,
                       single_view<range_value_t<_Range>>>;

namespace views {
inline constexpr __adaptor::_RangeAdaptor lazy_split =
    []<viewable_range _Range, typename _Fp>(_Range&& __r, _Fp&& __f) {
      return lazy_split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
    };
}  // namespace views
}  // namespace std::ranges

// The new split implementation from P2210, here named split2/split_view2
namespace std::ranges {

template <forward_range V, forward_range Pattern>
requires view<V> && view<Pattern> &&
    indirectly_comparable<iterator_t<V>, iterator_t<Pattern>, ranges::equal_to>
class split_view2 : public view_interface<split_view2<V, Pattern>> {
 private:
  V base_ = V();
  Pattern pattern_ = Pattern();
  struct iterator;
  struct sentinel;

struct iterator {
  private:
    friend sentinel;
    split_view2* parent_ = nullptr;
    iterator_t<V> cur_ = iterator_t<V>();
    subrange<iterator_t<V>> next_ =
        subrange<iterator_t<V>>();
    bool trailing_empty_ = false;

public:
    using iterator_concept = forward_iterator_tag;
    using iterator_category = input_iterator_tag;
    using value_type = subrange<iterator_t<V>>;
    using difference_type = range_difference_t<V>;

iterator() = default;
    constexpr iterator(split_view2& parent, iterator_t<V> current,
                       subrange<iterator_t<V>> next)
        : parent_(&parent), cur_(current), next_(next) {}

constexpr iterator_t<V> base() const { return cur_; }
    constexpr value_type operator*() const { return {cur_, next_.begin()}; }

constexpr iterator& operator++() {
      cur_ = next_.begin();
      if (cur_ != ranges::end(parent_->base_)) {
        cur_ = next_.end();
        if (cur_ == ranges::end(parent_->base_)) {
          trailing_empty_ = true;
          next_ = {cur_, cur_};
        } else {
          next_ = parent_->find_next(cur_);
        }
      } else {
        trailing_empty_ = false;
      }
      return *this;
    }
    constexpr iterator operator++(int) {
      auto tmp = *this;
      ++*this;
      return tmp;
    }

constexpr bool operator==(const iterator& rhs) const {
      return cur_ == rhs.cur_ && trailing_empty_ == rhs.trailing_empty_;
    }
  };

struct sentinel {
  private:
    sentinel_t<V> end_ = sentinel_t<V>();
    
  public:
    sentinel() = default;
    constexpr explicit sentinel(split_view2& parent)
        : end_(ranges::end(parent.base_))
    { }
    
    constexpr bool operator==(const iterator& x) const {
        return x.cur_ == end_ && !x.trailing_empty_;
    }
  };

public:
  split_view2() = default;
  constexpr split_view2(V base, Pattern pattern)
      : base_(std::move(base)), pattern_(std::move(pattern)) {}

template <forward_range R>
  requires constructible_from<V, views::all_t<R>> &&
      constructible_from<Pattern, single_view<range_value_t<R>>>
  constexpr split_view2(R&& r, range_value_t<R> e)
      : base_(views::all(std::forward<R>(r))),
        pattern_(views::single(std::move(e))) {}

constexpr V base() const& requires copyable<V> { return base_; }
  constexpr V base() && { return std::move(base_); }

constexpr iterator begin() {
    return {*this, ranges::begin(base_), find_next(ranges::begin(base_))};
  }

constexpr auto end() {
    if constexpr (common_range<V>) {
      return iterator{*this, ranges::end(base_), {}};
    } else {
      return sentinel{*this};
    }
  }

constexpr subrange<iterator_t<V>> find_next(iterator_t<V> it) {
    auto [b, e] = ranges::search(subrange(it, ranges::end(base_)), pattern_);
    if (b != ranges::end(base_) && ranges::empty(pattern_)) {
      ++b;
      ++e;
    }
    return {b, e};
  }
};

template <class R, class P>
split_view2(R&&, P&&) -> split_view2<views::all_t<R>, views::all_t<P>>;

template <forward_range R>
split_view2(R&&, range_value_t<R>)
    -> split_view2<views::all_t<R>, single_view<range_value_t<R>>>;

namespace views {
inline constexpr __adaptor::_RangeAdaptor split2 =
    []<viewable_range _Range, typename _Fp>(_Range&& __r, _Fp&& __f) {
      return split_view2{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
    };
}
}

struct zstring_sentinel {
    bool operator==(char const* p) const {
        return *p == '\0';
    }
};

struct zstring : std::ranges::view_interface<zstring> {
    char const* p = nullptr;
    zstring() = default;
    zstring(char const* p) : p(p) { }
    auto begin() const { return p; }
    auto end() const { return zstring_sentinel{}; }
};

template <typename R>
concept forward_only_range =
    std::ranges::forward_range<R>
    && !std::ranges::bidirectional_range<R>;

int main() {
  namespace rg = std::ranges;
  static_assert(rg::view<zstring>);
  {
    // the new one is a forward range of contiguous ranges
    using V = rg::split_view2<zstring, rg::single_view<char>>;
    static_assert(rg::view<V>);
    static_assert(forward_only_range<V>);
    static_assert(!rg::common_range<V>);
    static_assert(rg::contiguous_range<rg::range_reference_t<V>>);

// the old one is a forward range of forward ranges
    using LV = rg::lazy_split_view<zstring, rg::single_view<char>>;
    static_assert(rg::view<LV>);
    static_assert(forward_only_range<LV>);
    static_assert(!rg::common_range<LV>);
    static_assert(forward_only_range<rg::range_reference_t<LV>>);
  }

{
    // preserve common
    using V = rg::split_view2<std::string_view, std::string_view>;
    static_assert(forward_only_range<V>);
    static_assert(rg::common_range<V>);
    static_assert(rg::contiguous_range<rg::range_reference_t<V>>);
  }

using namespace std::literals;
  fmt::print("split2\n");
  fmt::print("{}\n", "a b c"sv | std::views::split2(' '));
  fmt::print("{}\n", "a b c "sv | std::views::split2(' '));
  fmt::print("{}\n", "abc"sv | std::views::split2(""sv));
  fmt::print("{}\n", std::views::split2("xxyx"sv, "xy"sv));
  fmt::print("{}\n", zstring{" x  "} | std::views::split2(' '));

fmt::print("lazy_split\n");
  fmt::print("{}\n", "a b c"sv | std::views::lazy_split(' '));
  fmt::print("{}\n", "a b c "sv | std::views::lazy_split(' '));
  fmt::print("{}\n", "abc"sv | std::views::lazy_split(""sv));
  fmt::print("{}\n", std::views::lazy_split("xxyx"sv, "xy"sv));
  fmt::print("{}\n", zstring{" x  "} | std::views::lazy_split(' '));
}