[libcxx][ranges] revert join_view::iterator and sentinel to be in-class

[huixie90]

Summary

[libc++][ranges] revert join_view::iterator and sentinel to be in-class

• inside the __iterator, having a member typedef using flag = __iterator and checks same_as<Tp::flag, Tp>. This way we can detect the class is indeed __iterator rather than a derived class.

[huixie90]

CI

[huixie90]

CI

[huixie90]

CI

[huixie90]

CI

[huixie90]

CI

[huixie90]

CI

[philnik]

libcxx/include/__ranges/join_view.h

184

This seems quite complicated. Is there a reason not to use __is_primary_template instead?

[huixie90]

work around Clang 14 bug

[huixie90]

libcxx/include/__ranges/join_view.h

184

I think the idea is exactly the same (the sfinae technique is also exactly the same but I did not know it is abstracted in _IsValidExpansion). but __is_primary_template does not sound the right name

[huixie90]

use _IsValidExpansion

[ldionne]

libcxx/include/__ranges/join_view.h

184

Can't we simply give this a private member called __is_join_view_iterator and check whether that member exists from a befriended class?

[huixie90]

libcxx/include/__ranges/join_view.h

184

@ldionne
That was the first thing I tried.

https://godbolt.org/z/Ws3baE1E1

It did not work because, even though Derived does not have access Base::flag. the friend Checker can still access Derived::flag as the flag is part of the Base sub object.

today I realised that I can make the befriended thing a template and only friend the particular instantiation.
https://godbolt.org/z/771rjzvzq

what do you think?

[ldionne]

libcxx/include/__ranges/join_view.h

184

To be honest, I am not certain that all of these gymnastics are necessary. I don't see why someone would ever inherit from one of these iterators, and if they do, I think it may be reasonable for them to be broken. And if there's a good reason to do that, then we can change our detection of segmented iterators to account for that as a bug fix. So personally, I'd go for the simplest mechanism that doesn't handle derived types properly and I'd call it a day.

The other thing we could do BTW is mark the iterator class as final (which is non-conforming but not by much, and for an arguably good reason), and/or create a LWG issue (or write a paper?) asking for ranges iterators to be marked final. Ranges iterators are somewhat special because they are defined as nested classes, which is not super frequent and creates the ADL difficulties that you noted in the first place. As a result, I think it would make sense to consider this problem for all nested iterator types inside Ranges and I think a paper would probably make sense.

[huixie90]

make the iterator final

[huixie90]

remove unused code

[ldionne]

This looks like a reasonable compromise to me. Let's cherry-pick.

libcxx/include/__ranges/join_view.h

197

Can you add a comment explaining what this final is?

libcxx/include/__ranges/join_view.h

using iterator_category = _If<
       _If<
         derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>,
         forward_iterator_tag,
         input_iterator_tag
       >
     >;
   };
 
-  template <input_range _View, bool _Const>
-    requires view<_View> && input_range<range_reference_t<_View>>
-  struct __join_view_iterator;
-
-  template <input_range _View, bool _Const>
-    requires view<_View> && input_range<range_reference_t<_View>>
-  struct __join_view_sentinel;
-
   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 _Const>
-    using __iterator = __join_view_iterator<_View, _Const>;
-
-    template<bool _Const>
-    using __sentinel = __join_view_sentinel<_View, _Const>;
+    template<bool> struct __iterator;
 
-    template <input_range _View2, bool _Const2>
-      requires view<_View2> && input_range<range_reference_t<_View2>>
-    friend struct __join_view_iterator;
-
-    template <input_range _View2, bool _Const2>
-      requires view<_View2> && input_range<range_reference_t<_View2>>
-    friend struct __join_view_sentinel;
+    template<bool> struct __sentinel;
 
     template <class>
     friend struct std::__segmented_iterator_traits;
 
     static constexpr bool _UseCache = !is_reference_v<_InnerRange>;
     using _Cache = _If<_UseCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>;
     _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cache_;
     _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
constexpr auto end() const
                     common_range<_ConstInnerRange>) {
         return __iterator<true>{*this, ranges::end(__base_)};
       } else {
         return __sentinel<true>{*this};
       }
     }
   };
 
-  template<input_range _View, bool _Const>
+  template<input_range _View>
     requires view<_View> && input_range<range_reference_t<_View>>
-  struct __join_view_sentinel {
-    template<input_range _View2, bool>
-      requires view<_View2> && input_range<range_reference_t<_View2>>
-    friend struct __join_view_sentinel;
+  template<bool _Const>
+  struct join_view<_View>::__sentinel {
+  template<bool>
+    friend struct __sentinel;
 
   private:
     using _Parent = __maybe_const<_Const, join_view<_View>>;
     using _Base = __maybe_const<_Const, _View>;
     sentinel_t<_Base> __end_ = sentinel_t<_Base>();
 
   public:
     _LIBCPP_HIDE_FROM_ABI
-    __join_view_sentinel() = default;
+    __sentinel() = default;
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr explicit __join_view_sentinel(_Parent& __parent)
+    constexpr explicit __sentinel(_Parent& __parent)
       : __end_(ranges::end(__parent.__base_)) {}
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __join_view_sentinel(__join_view_sentinel<_View, !_Const> __s)
+    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 __join_view_iterator<_View, _OtherConst>& __x, const __join_view_sentinel& __y) {
+    friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
       return __x.__outer_ == __y.__end_;
     }
   };
 
-  template<input_range _View, bool _Const>
+  // Make sure that the derived class returns false_type;
+  struct __is_join_view_iterator_checker {
+    template <class _Tp>
+    static typename _Tp::_JoinViewIterType __get_type();
+
+    template <class _Tp>
+    using __check = __enable_if_t<_IsSame<_Tp, decltype(__get_type<_Tp>())>::value>;
+  };
+
+  template <class _Tp>
+  using __is_join_view_iterator = _IsValidExpansion<__is_join_view_iterator_checker::__check, _Tp>;
+
+  template<input_range _View>
     requires view<_View> && input_range<range_reference_t<_View>>
-  struct __join_view_iterator
+  template<bool _Const>
+  struct join_view<_View>::__iterator
     : public __join_view_iterator_category<__maybe_const<_Const, _View>> {
 
-    template<input_range _View2, bool>
-      requires view<_View2> && input_range<range_reference_t<_View2>>
-    friend struct __join_view_iterator;
+    template<bool>
+    friend struct __iterator;
 
     template <class>
     friend struct std::__segmented_iterator_traits;
 
+    friend __is_join_view_iterator_checker;
+
   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>;
+    using _JoinViewIterType = __iterator;
 
     static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>;
 
   public:
     _Outer __outer_ = _Outer();
 
   private:
     optional<_Inner> __inner_;
constexpr void __satisfy() {
         if (*__inner_ != ranges::end(__inner))
           return;
       }
 
       if constexpr (__ref_is_glvalue)
         __inner_.reset();
     }
 
-    _LIBCPP_HIDE_FROM_ABI constexpr __join_view_iterator(_Parent* __parent, _Outer __outer, _Inner __inner)
+    _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent* __parent, _Outer __outer, _Inner __inner)
       : __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
-    __join_view_iterator() requires default_initializable<_Outer> = default;
+    __iterator() requires default_initializable<_Outer> = default;
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __join_view_iterator(_Parent& __parent, _Outer __outer)
+    constexpr __iterator(_Parent& __parent, _Outer __outer)
       : __outer_(std::move(__outer))
       , __parent_(std::addressof(__parent)) {
       __satisfy();
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __join_view_iterator(__join_view_iterator<_View, !_Const> __i)
+    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 __join_view_iterator& operator++() {
+    constexpr __iterator& operator++() {
       auto&& __inner = [&]() -> auto&& {
         if constexpr (__ref_is_glvalue)
           return *__outer_;
         else
           return *__parent_->__cache_;
       }();
       if (++*__inner_ == ranges::end(__inner)) {
         ++__outer_;
         __satisfy();
       }
       return *this;
     }
 
     _LIBCPP_HIDE_FROM_ABI
     constexpr void operator++(int) {
       ++*this;
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __join_view_iterator operator++(int)
+    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 __join_view_iterator& operator--()
+    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(*--__outer_);
 
       // Skip empty inner ranges when going backwards.
       while (*__inner_ == ranges::begin(*__outer_)) {
         __inner_ = ranges::end(*--__outer_);
       }
 
       --*__inner_;
       return *this;
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __join_view_iterator operator--(int)
+    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 __join_view_iterator& __x, const __join_view_iterator& __y)
+    friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
       requires __ref_is_glvalue &&
                equality_comparable<iterator_t<_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 __join_view_iterator& __i)
+    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 __join_view_iterator& __x, const __join_view_iterator& __y)
+    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>

 };
 } // namespace __join_view
 inline namespace __cpo {
   inline constexpr auto join = __join_view::__fn{};
 } // namespace __cpo
 } // namespace views
 } // namespace ranges
 
-template <class _View, bool _Const>
-  requires(ranges::common_range<typename ranges::__join_view_iterator<_View, _Const>::_Parent> &&
-           __is_cpp17_random_access_iterator<typename ranges::__join_view_iterator<_View, _Const>::_Outer>::value &&
-           __is_cpp17_random_access_iterator<typename ranges::__join_view_iterator<_View, _Const>::_Inner>::value)
-struct __segmented_iterator_traits<ranges::__join_view_iterator<_View, _Const>> {
-  using _JoinViewIterator = ranges::__join_view_iterator<_View, _Const>;
+template <class _JoinViewIterator>
+  requires(ranges::__is_join_view_iterator<_JoinViewIterator>::value &&
+           ranges::common_range<typename _JoinViewIterator::_Parent> &&
+           __is_cpp17_random_access_iterator<typename _JoinViewIterator::_Outer>::value &&
+           __is_cpp17_random_access_iterator<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) {

libcxx/test/libcxx/containers/sequences/deque/segmented_iterator.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include <deque>
+
+
+using DequeIterator = typename std::deque<int>::iterator;
+static_assert(std::__is_segmented_iterator<DequeIterator>::value, "");

libcxx/test/libcxx/ranges/range.adaptors/range.join/segmented_iterator.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+#include <ranges>
+#include <vector>
+
+using JoinView = decltype(std::views::join(std::declval<std::vector<std::vector<int>>&>()));
+using JoinIter = std::ranges::iterator_t<JoinView>;
+static_assert(std::__is_segmented_iterator<JoinIter>::value);
+
+struct DerivedIter : JoinIter{};
+
+static_assert(!std::__is_segmented_iterator<DerivedIter>::value);