include/__ranges/join_view.h

// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___RANGES_JOIN_VIEW_H
#define _LIBCPP___RANGES_JOIN_VIEW_H

#include <__concepts/constructible.h>
#include <__concepts/convertible_to.h>
#include <__concepts/copyable.h>
#include <__concepts/derived_from.h>
#include <__concepts/equality_comparable.h>
#include <__config>
#include <__iterator/concepts.h>
#include <__iterator/iter_move.h>
#include <__iterator/iter_swap.h>
#include <__iterator/iterator_traits.h>
#include <__iterator/iterator_with_data.h>
#include <__iterator/segmented_iterator.h>
#include <__memory/addressof.h>
#include <__ranges/access.h>
#include <__ranges/all.h>
#include <__ranges/concepts.h>
#include <__ranges/empty.h>
#include <__ranges/non_propagating_cache.h>
#include <__ranges/range_adaptor.h>
#include <__ranges/view_interface.h>
#include <__type_traits/common_type.h>
#include <__type_traits/maybe_const.h>
#include <__utility/as_lvalue.h>
#include <__utility/empty.h>
#include <__utility/forward.h>
#include <optional>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_PUSH_MACROS
#include <__undef_macros>

_LIBCPP_BEGIN_NAMESPACE_STD

#if _LIBCPP_STD_VER >= 20

namespace ranges {
template <class>
struct __join_view_iterator_category {};

template <class _View>
  requires is_reference_v<range_reference_t<_View>> && forward_range<_View> && forward_range<range_reference_t<_View>>
struct __join_view_iterator_category<_View> {
  using _OuterC = typename iterator_traits<iterator_t<_View>>::iterator_category;
  using _InnerC = typename iterator_traits<iterator_t<range_reference_t<_View>>>::iterator_category;

  using iterator_category =
      _If< derived_from<_OuterC, bidirectional_iterator_tag> && derived_from<_InnerC, bidirectional_iterator_tag> &&
               common_range<range_reference_t<_View>>,
           bidirectional_iterator_tag,
           _If< derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>,
                forward_iterator_tag,
                input_iterator_tag > >;
};

template <input_range _View>
  requires view<_View> && input_range<range_reference_t<_View>>
class join_view : public view_interface<join_view<_View>> {
private:
  using _InnerRange = range_reference_t<_View>;

  template <bool>
  struct __iterator;

  template <bool>
  struct __sentinel;

  template <class>
  friend struct std::__segmented_iterator_traits;

  _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();

  static constexpr bool _UseOuterCache = !forward_range<_View>;
  using _OuterCache                    = _If<_UseOuterCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
  _LIBCPP_NO_UNIQUE_ADDRESS _OuterCache __outer_;

  static constexpr bool _UseInnerCache = !is_reference_v<_InnerRange>;
  using _InnerCache = _If<_UseInnerCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>;
  _LIBCPP_NO_UNIQUE_ADDRESS _InnerCache __inner_;

public:
  _LIBCPP_HIDE_FROM_ABI join_view()
    requires default_initializable<_View>
  = default;

  _LIBCPP_HIDE_FROM_ABI constexpr explicit join_view(_View __base) : __base_(std::move(__base)) {}

  _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
    requires copy_constructible<_View>
  {
    return __base_;
  }

  _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }

  _LIBCPP_HIDE_FROM_ABI constexpr auto begin() {
    if constexpr (forward_range<_View>) {
      constexpr bool __use_const = __simple_view<_View> && is_reference_v<range_reference_t<_View>>;
      return __iterator<__use_const>{*this, ranges::begin(__base_)};
    } else {
      __outer_.__emplace(ranges::begin(__base_));
      return __iterator<false>{*this};
    }
  }

  template <class _V2 = _View>
  _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
    requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&
             input_range<range_reference_t<const _V2>>
  {
    return __iterator<true>{*this, ranges::begin(__base_)};
  }

  _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
    if constexpr (forward_range<_View> && is_reference_v<_InnerRange> && forward_range<_InnerRange> &&
                  common_range<_View> && common_range<_InnerRange>)
      return __iterator<__simple_view<_View>>{*this, ranges::end(__base_)};
    else
      return __sentinel<__simple_view<_View>>{*this};
  }

  template <class _V2 = _View>
  _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
    requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&
             input_range<range_reference_t<const _V2>>
  {
    using _ConstInnerRange = range_reference_t<const _View>;
    if constexpr (forward_range<_ConstInnerRange> && common_range<const _View> && common_range<_ConstInnerRange>) {
      return __iterator<true>{*this, ranges::end(__base_)};
    } else {
      return __sentinel<true>{*this};
    }
  }
};

template <input_range _View>
  requires view<_View> && input_range<range_reference_t<_View>>
template <bool _Const>
struct join_view<_View>::__sentinel {
private:
  template <bool>
  friend struct __sentinel;

  using _Parent            = __maybe_const<_Const, join_view>;
  using _Base              = __maybe_const<_Const, _View>;
  sentinel_t<_Base> __end_ = sentinel_t<_Base>();

public:
  _LIBCPP_HIDE_FROM_ABI __sentinel() = default;

  _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {}

  _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __s)
    requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
      : __end_(std::move(__s.__end_)) {}

  template <bool _OtherConst>
    requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
  _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
    return __x.__get_outer() == __y.__end_;
  }
};

// https://reviews.llvm.org/D142811#inline-1383022
// To simplify the segmented iterator traits specialization,
// make the iterator `final`
template <input_range _View>
  requires view<_View> && input_range<range_reference_t<_View>>
template <bool _Const>
struct join_view<_View>::__iterator final : public __join_view_iterator_category<__maybe_const<_Const, _View>> {
  friend join_view;

  template <class>
  friend struct std::__segmented_iterator_traits;

  static constexpr bool __is_join_view_iterator = true;

private:
  using _Parent     = __maybe_const<_Const, join_view<_View>>;
  using _Base       = __maybe_const<_Const, _View>;
  using _Outer      = iterator_t<_Base>;
  using _Inner      = iterator_t<range_reference_t<_Base>>;
  using _InnerRange = range_reference_t<_View>;

  static_assert(!_Const || forward_range<_Base>, "Const can only be true when Base models forward_range.");

  static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>;

  static constexpr bool _OuterPresent           = forward_range<_Base>;
  using _OuterType                              = _If<_OuterPresent, _Outer, std::__empty>;
  _LIBCPP_NO_UNIQUE_ADDRESS _OuterType __outer_ = _OuterType();

  optional<_Inner> __inner_;
  _Parent* __parent_ = nullptr;

  _LIBCPP_HIDE_FROM_ABI constexpr void __satisfy() {
    for (; __get_outer() != ranges::end(__parent_->__base_); ++__get_outer()) {
      auto&& __inner = [this]() -> auto&& {
        if constexpr (__ref_is_glvalue)
          return *__get_outer();
        else
          return __parent_->__inner_.__emplace_from([&]() -> decltype(auto) { return *__get_outer(); });
      }();
      __inner_ = ranges::begin(__inner);
      if (*__inner_ != ranges::end(__inner))
        return;
    }

    if constexpr (__ref_is_glvalue)
      __inner_.reset();
  }

  _LIBCPP_HIDE_FROM_ABI constexpr _Outer& __get_outer() {
    if constexpr (forward_range<_Base>) {
      return __outer_;
    } else {
      return *__parent_->__outer_;
    }
  }

  _LIBCPP_HIDE_FROM_ABI constexpr const _Outer& __get_outer() const {
    if constexpr (forward_range<_Base>) {
      return __outer_;
    } else {
      return *__parent_->__outer_;
    }
  }

  _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent& __parent, _Outer __outer)
    requires forward_range<_Base>
      : __outer_(std::move(__outer)), __parent_(std::addressof(__parent)) {
    __satisfy();
  }

  _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(_Parent& __parent)
    requires(!forward_range<_Base>)
      : __parent_(std::addressof(__parent)) {
    __satisfy();
  }

  _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent* __parent, _Outer __outer, _Inner __inner)
    requires forward_range<_Base>
      : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {}

public:
  using iterator_concept =
      _If< __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
               common_range<range_reference_t<_Base>>,
           bidirectional_iterator_tag,
           _If< __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>,
                forward_iterator_tag,
                input_iterator_tag > >;

  using value_type = range_value_t<range_reference_t<_Base>>;

  using difference_type = common_type_t< range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>;

  _LIBCPP_HIDE_FROM_ABI __iterator() = default;

  _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i)
    requires _Const && convertible_to<iterator_t<_View>, _Outer> && convertible_to<iterator_t<_InnerRange>, _Inner>
      : __outer_(std::move(__i.__outer_)), __inner_(std::move(__i.__inner_)), __parent_(__i.__parent_) {}

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

  _LIBCPP_HIDE_FROM_ABI constexpr _Inner operator->() const
    requires __has_arrow<_Inner> && copyable<_Inner>
  {
    return *__inner_;
  }

  _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
    auto __get_inner_range = [&]() -> decltype(auto) {
      if constexpr (__ref_is_glvalue)
        return *__get_outer();
      else
        return *__parent_->__inner_;
    };
    if (++*__inner_ == ranges::end(std::__as_lvalue(__get_inner_range()))) {
      ++__get_outer();
      __satisfy();
    }
    return *this;
  }

  _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; }

  _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)
    requires __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>
  {
    auto __tmp = *this;
    ++*this;
    return __tmp;
  }

  _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()
    requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
             common_range<range_reference_t<_Base>>
  {
    if (__outer_ == ranges::end(__parent_->__base_))
      __inner_ = ranges::end(std::__as_lvalue(*--__outer_));

    // Skip empty inner ranges when going backwards.
    while (*__inner_ == ranges::begin(std::__as_lvalue(*__outer_))) {
      __inner_ = ranges::end(std::__as_lvalue(*--__outer_));
    }

    --*__inner_;
    return *this;
  }

  _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)
    requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
             common_range<range_reference_t<_Base>>
  {
    auto __tmp = *this;
    --*this;
    return __tmp;
  }

  _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
    requires __ref_is_glvalue && forward_range<_Base> && equality_comparable<iterator_t<range_reference_t<_Base>>>
  {
    return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_;
  }

  _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)
  iter_move(const __iterator& __i) noexcept(noexcept(ranges::iter_move(*__i.__inner_))) {
    return ranges::iter_move(*__i.__inner_);
  }

  _LIBCPP_HIDE_FROM_ABI friend constexpr void
  iter_swap(const __iterator& __x,
            const __iterator& __y) noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_)))
    requires indirectly_swappable<_Inner>
  {
    return ranges::iter_swap(*__x.__inner_, *__y.__inner_);
  }
};

template <class _Range>
explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;

namespace views {
namespace __join_view {
struct __fn : __range_adaptor_closure<__fn> {
  template <class _Range>
  [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
      noexcept(noexcept(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))))
          -> decltype(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))) {
    return join_view<all_t<_Range&&>>(std::forward<_Range>(__range));
  }
};
} // namespace __join_view
inline namespace __cpo {
inline constexpr auto join = __join_view::__fn{};
} // namespace __cpo
} // namespace views
} // namespace ranges

template <class _JoinViewIterator>
  requires(_JoinViewIterator::__is_join_view_iterator && ranges::common_range<typename _JoinViewIterator::_Parent> &&
           __has_random_access_iterator_category<typename _JoinViewIterator::_Outer>::value &&
           __has_random_access_iterator_category<typename _JoinViewIterator::_Inner>::value)
struct __segmented_iterator_traits<_JoinViewIterator> {
  using __segment_iterator =
      _LIBCPP_NODEBUG __iterator_with_data<typename _JoinViewIterator::_Outer, typename _JoinViewIterator::_Parent*>;
  using __local_iterator = typename _JoinViewIterator::_Inner;

  // TODO: Would it make sense to enable the optimization for other iterator types?

  static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) {
    if (ranges::empty(__iter.__parent_->__base_))
      return {};
    if (!__iter.__inner_.has_value())
      return __segment_iterator(--__iter.__outer_, __iter.__parent_);
    return __segment_iterator(__iter.__outer_, __iter.__parent_);
  }

  static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) {
    if (ranges::empty(__iter.__parent_->__base_))
      return {};
    if (!__iter.__inner_.has_value())
      return ranges::end(*--__iter.__outer_);
    return *__iter.__inner_;
  }

  static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) {
    return ranges::begin(*__iter.__get_iter());
  }

  static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {
    return ranges::end(*__iter.__get_iter());
  }

  static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator
  __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) {
    return _JoinViewIterator(
        std::move(__seg_iter).__get_data(), std::move(__seg_iter).__get_iter(), std::move(__local_iter));
  }
};

#endif // #if _LIBCPP_STD_VER >= 20

_LIBCPP_END_NAMESPACE_STD

_LIBCPP_POP_MACROS

#endif // _LIBCPP___RANGES_JOIN_VIEW_H